src/journal/journal-verify.c

   1 /*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
   2
   3 /***
   4   This file is part of systemd.
   5
   6   Copyright 2012 Lennart Poettering
   7
   8   systemd is free software; you can redistribute it and/or modify it
   9   under the terms of the GNU Lesser General Public License as published by
  10   the Free Software Foundation; either version 2.1 of the License, or
  11   (at your option) any later version.
  12
  13   systemd is distributed in the hope that it will be useful, but
  14   WITHOUT ANY WARRANTY; without even the implied warranty of
  15   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  16   Lesser General Public License for more details.
  17
  18   You should have received a copy of the GNU Lesser General Public License
  19   along with systemd; If not, see <http://www.gnu.org/licenses/>.
  20 ***/
  21
  22 #include <unistd.h>
  23 #include <sys/mman.h>
  24 #include <fcntl.h>
  25 #include <stddef.h>
  26
  27 #include "util.h"
  28 #include "macro.h"
  29 #include "journal-def.h"
  30 #include "journal-file.h"
  31 #include "journal-authenticate.h"
  32 #include "journal-verify.h"
  33 #include "lookup3.h"
  34 #include "compress.h"
  35 #include "fsprg.h"
  36
  37 static int journal_file_object_verify(JournalFile *f, uint64_t offset, Object *o) {
  38         uint64_t i;
  39
  40         assert(f);
  41         assert(offset);
  42         assert(o);
  43
  44         /* This does various superficial tests about the length an
  45          * possible field values. It does not follow any references to
  46          * other objects. */
  47
  48         if ((o->object.flags & OBJECT_COMPRESSED) &&
  49             o->object.type != OBJECT_DATA)
  50                 return -EBADMSG;
  51
  52         switch (o->object.type) {
  53
  54         case OBJECT_DATA: {
  55                 uint64_t h1, h2;
  56
  57                 if (le64toh(o->data.entry_offset) == 0)
  58                         log_warning(OFSfmt": unused data (entry_offset==0)", offset);
  59
  60                 if ((le64toh(o->data.entry_offset) == 0) ^ (le64toh(o->data.n_entries) == 0)) {
  61                         log_error(OFSfmt": bad n_entries: %"PRIu64, offset, o->data.n_entries);
  62                         return -EBADMSG;
  63                 }
  64
  65                 if (le64toh(o->object.size) - offsetof(DataObject, payload) <= 0) {
  66                         log_error(OFSfmt": bad object size (<= %zu): %"PRIu64,
  67                                   offset,
  68                                   offsetof(DataObject, payload),
  69                                   le64toh(o->object.size));
  70                         return -EBADMSG;
  71                 }
  72
  73                 h1 = le64toh(o->data.hash);
  74
  75                 if (o->object.flags & OBJECT_COMPRESSED) {
  76 #ifdef HAVE_XZ
  77                         void *b = NULL;
  78                         uint64_t alloc = 0, b_size;
  79
  80                         if (!uncompress_blob(o->data.payload,
  81                                              le64toh(o->object.size) - offsetof(Object, data.payload),
  82                                              &b, &alloc, &b_size, 0)) {
  83                                 log_error(OFSfmt": uncompression failed", offset);
  84                                 return -EBADMSG;
  85                         }
  86
  87                         h2 = hash64(b, b_size);
  88                         free(b);
  89 #else
  90                         log_error("Compression is not supported");
  91                         return -EPROTONOSUPPORT;
  92 #endif
  93                 } else
  94                         h2 = hash64(o->data.payload, le64toh(o->object.size) - offsetof(Object, data.payload));
  95
  96                 if (h1 != h2) {
  97                         log_error(OFSfmt": invalid hash (%08"PRIx64" vs. %08"PRIx64, offset, h1, h2);
  98                         return -EBADMSG;
  99                 }
 100
 101                 if (!VALID64(o->data.next_hash_offset) ||
 102                     !VALID64(o->data.next_field_offset) ||
 103                     !VALID64(o->data.entry_offset) ||
 104                     !VALID64(o->data.entry_array_offset)) {
 105                         log_error(OFSfmt": invalid offset (next_hash_offset="OFSfmt", next_field_offset="OFSfmt", entry_offset="OFSfmt", entry_array_offset="OFSfmt,
 106                                   offset,
 107                                   o->data.next_hash_offset,
 108                                   o->data.next_field_offset,
 109                                   o->data.entry_offset,
 110                                   o->data.entry_array_offset);
 111                         return -EBADMSG;
 112                 }
 113
 114                 break;
 115         }
 116
 117         case OBJECT_FIELD:
 118                 if (le64toh(o->object.size) - offsetof(FieldObject, payload) <= 0) {
 119                         log_error(OFSfmt": bad field size (<= %zu): %"PRIu64,
 120                                   offset,
 121                                   offsetof(FieldObject, payload),
 122                                   le64toh(o->object.size));
 123                         return -EBADMSG;
 124                 }
 125
 126                 if (!VALID64(o->field.next_hash_offset) ||
 127                     !VALID64(o->field.head_data_offset)) {
 128                         log_error(OFSfmt": invalid offset (next_hash_offset="OFSfmt", head_data_offset="OFSfmt,
 129                                   offset,
 130                                   o->field.next_hash_offset,
 131                                   o->field.head_data_offset);
 132                         return -EBADMSG;
 133                 }
 134                 break;
 135
 136         case OBJECT_ENTRY:
 137                 if ((le64toh(o->object.size) - offsetof(EntryObject, items)) % sizeof(EntryItem) != 0) {
 138                         log_error(OFSfmt": bad entry size (<= %zu): %"PRIu64,
 139                                   offset,
 140                                   offsetof(EntryObject, items),
 141                                   le64toh(o->object.size));
 142                         return -EBADMSG;
 143                 }
 144
 145                 if ((le64toh(o->object.size) - offsetof(EntryObject, items)) / sizeof(EntryItem) <= 0) {
 146                         log_error(OFSfmt": invalid number items in entry: %"PRIu64,
 147                                   offset,
 148                                   (le64toh(o->object.size) - offsetof(EntryObject, items)) / sizeof(EntryItem));
 149                         return -EBADMSG;
 150                 }
 151
 152                 if (le64toh(o->entry.seqnum) <= 0) {
 153                         log_error(OFSfmt": invalid entry seqnum: %"PRIx64,
 154                                   offset,
 155                                   le64toh(o->entry.seqnum));
 156                         return -EBADMSG;
 157                 }
 158
 159                 if (!VALID_REALTIME(le64toh(o->entry.realtime))) {
 160                         log_error(OFSfmt": invalid entry realtime timestamp: %"PRIu64,
 161                                   offset,
 162                                   le64toh(o->entry.realtime));
 163                         return -EBADMSG;
 164                 }
 165
 166                 if (!VALID_MONOTONIC(le64toh(o->entry.monotonic))) {
 167                         log_error(OFSfmt": invalid entry monotonic timestamp: %"PRIu64,
 168                                   offset,
 169                                   le64toh(o->entry.monotonic));
 170                         return -EBADMSG;
 171                 }
 172
 173                 for (i = 0; i < journal_file_entry_n_items(o); i++) {
 174                         if (o->entry.items[i].object_offset == 0 ||
 175                             !VALID64(o->entry.items[i].object_offset)) {
 176                                 log_error(OFSfmt": invalid entry item (%"PRIu64"/%"PRIu64" offset: "OFSfmt,
 177                                           offset,
 178                                           i, journal_file_entry_n_items(o),
 179                                           o->entry.items[i].object_offset);
 180                                 return -EBADMSG;
 181                         }
 182                 }
 183
 184                 break;
 185
 186         case OBJECT_DATA_HASH_TABLE:
 187         case OBJECT_FIELD_HASH_TABLE:
 188                 if ((le64toh(o->object.size) - offsetof(HashTableObject, items)) % sizeof(HashItem) != 0 ||
 189                     (le64toh(o->object.size) - offsetof(HashTableObject, items)) / sizeof(HashItem) <= 0) {
 190                         log_error(OFSfmt": invalid %s hash table size: %"PRIu64,
 191                                   offset,
 192                                   o->object.type == OBJECT_DATA_HASH_TABLE ? "data" : "field",
 193                                   le64toh(o->object.size));
 194                         return -EBADMSG;
 195                 }
 196
 197                 for (i = 0; i < journal_file_hash_table_n_items(o); i++) {
 198                         if (o->hash_table.items[i].head_hash_offset != 0 &&
 199                             !VALID64(le64toh(o->hash_table.items[i].head_hash_offset))) {
 200                                 log_error(OFSfmt": invalid %s hash table item (%"PRIu64"/%"PRIu64") head_hash_offset: "OFSfmt,
 201                                           offset,
 202                                           o->object.type == OBJECT_DATA_HASH_TABLE ? "data" : "field",
 203                                           i, journal_file_hash_table_n_items(o),
 204                                           le64toh(o->hash_table.items[i].head_hash_offset));
 205                                 return -EBADMSG;
 206                         }
 207                         if (o->hash_table.items[i].tail_hash_offset != 0 &&
 208                             !VALID64(le64toh(o->hash_table.items[i].tail_hash_offset))) {
 209                                 log_error(OFSfmt": invalid %s hash table item (%"PRIu64"/%"PRIu64") tail_hash_offset: "OFSfmt,
 210                                           offset,
 211                                           o->object.type == OBJECT_DATA_HASH_TABLE ? "data" : "field",
 212                                           i, journal_file_hash_table_n_items(o),
 213                                           le64toh(o->hash_table.items[i].tail_hash_offset));
 214                                 return -EBADMSG;
 215                         }
 216
 217                         if ((o->hash_table.items[i].head_hash_offset != 0) !=
 218                             (o->hash_table.items[i].tail_hash_offset != 0)) {
 219                                 log_error(OFSfmt": invalid %s hash table item (%"PRIu64"/%"PRIu64"): head_hash_offset="OFSfmt" tail_hash_offset="OFSfmt,
 220                                           offset,
 221                                           o->object.type == OBJECT_DATA_HASH_TABLE ? "data" : "field",
 222                                           i, journal_file_hash_table_n_items(o),
 223                                           le64toh(o->hash_table.items[i].head_hash_offset),
 224                                           le64toh(o->hash_table.items[i].tail_hash_offset));
 225                                 return -EBADMSG;
 226                         }
 227                 }
 228
 229                 break;
 230
 231         case OBJECT_ENTRY_ARRAY:
 232                 if ((le64toh(o->object.size) - offsetof(EntryArrayObject, items)) % sizeof(le64_t) != 0 ||
 233                     (le64toh(o->object.size) - offsetof(EntryArrayObject, items)) / sizeof(le64_t) <= 0) {
 234                         log_error(OFSfmt": invalid object entry array size: %"PRIu64,
 235                                   offset,
 236                                   le64toh(o->object.size));
 237                         return -EBADMSG;
 238                 }
 239
 240                 if (!VALID64(o->entry_array.next_entry_array_offset)) {
 241                         log_error(OFSfmt": invalid object entry array next_entry_array_offset: "OFSfmt,
 242                                   offset,
 243                                   o->entry_array.next_entry_array_offset);
 244                         return -EBADMSG;
 245                 }
 246
 247                 for (i = 0; i < journal_file_entry_array_n_items(o); i++)
 248                         if (le64toh(o->entry_array.items[i]) != 0 &&
 249                             !VALID64(le64toh(o->entry_array.items[i]))) {
 250                                 log_error(OFSfmt": invalid object entry array item (%"PRIu64"/%"PRIu64"): "OFSfmt,
 251                                           offset,
 252                                           i, journal_file_entry_array_n_items(o),
 253                                           le64toh(o->entry_array.items[i]));
 254                                 return -EBADMSG;
 255                         }
 256
 257                 break;
 258
 259         case OBJECT_TAG:
 260                 if (le64toh(o->object.size) != sizeof(TagObject)) {
 261                         log_error(OFSfmt": invalid object tag size: %"PRIu64,
 262                                   offset,
 263                                   le64toh(o->object.size));
 264                         return -EBADMSG;
 265                 }
 266
 267                 if (!VALID_EPOCH(o->tag.epoch)) {
 268                         log_error(OFSfmt": invalid object tag epoch: %"PRIu64,
 269                                   offset,
 270                                   o->tag.epoch);
 271                         return -EBADMSG;
 272                 }
 273
 274                 break;
 275         }
 276
 277         return 0;
 278 }
 279
 280 static void draw_progress(uint64_t p, usec_t *last_usec) {
 281         unsigned n, i, j, k;
 282         usec_t z, x;
 283
 284         if (!on_tty())
 285                 return;
 286
 287         z = now(CLOCK_MONOTONIC);
 288         x = *last_usec;
 289
 290         if (x != 0 && x + 40 * USEC_PER_MSEC > z)
 291                 return;
 292
 293         *last_usec = z;
 294
 295         n = (3 * columns()) / 4;
 296         j = (n * (unsigned) p) / 65535ULL;
 297         k = n - j;
 298
 299         fputs("\r\x1B[?25l" ANSI_HIGHLIGHT_GREEN_ON, stdout);
 300
 301         for (i = 0; i < j; i++)
 302                 fputs("\xe2\x96\x88", stdout);
 303
 304         fputs(ANSI_HIGHLIGHT_OFF, stdout);
 305
 306         for (i = 0; i < k; i++)
 307                 fputs("\xe2\x96\x91", stdout);
 308
 309         printf(" %3"PRIu64"%%", 100U * p / 65535U);
 310
 311         fputs("\r\x1B[?25h", stdout);
 312         fflush(stdout);
 313 }
 314
 315 static void flush_progress(void) {
 316         unsigned n, i;
 317
 318         if (!on_tty())
 319                 return;
 320
 321         n = (3 * columns()) / 4;
 322
 323         putchar('\r');
 324
 325         for (i = 0; i < n + 5; i++)
 326                 putchar(' ');
 327
 328         putchar('\r');
 329         fflush(stdout);
 330 }
 331
 332 static int write_uint64(int fd, uint64_t p) {
 333         ssize_t k;
 334
 335         k = write(fd, &p, sizeof(p));
 336         if (k < 0)
 337                 return -errno;
 338         if (k != sizeof(p))
 339                 return -EIO;
 340
 341         return 0;
 342 }
 343
 344 static int contains_uint64(MMapCache *m, int fd, uint64_t n, uint64_t p) {
 345         uint64_t a, b;
 346         int r;
 347
 348         assert(m);
 349         assert(fd >= 0);
 350
 351         /* Bisection ... */
 352
 353         a = 0; b = n;
 354         while (a < b) {
 355                 uint64_t c, *z;
 356
 357                 c = (a + b) / 2;
 358
 359                 r = mmap_cache_get(m, fd, PROT_READ|PROT_WRITE, 0, false, c * sizeof(uint64_t), sizeof(uint64_t), NULL, (void **) &z);
 360                 if (r < 0)
 361                         return r;
 362
 363                 if (*z == p)
 364                         return 1;
 365
 366                 if (a + 1 >= b)
 367                         return 0;
 368
 369                 if (p < *z)
 370                         b = c;
 371                 else
 372                         a = c;
 373         }
 374
 375         return 0;
 376 }
 377
 378 static int entry_points_to_data(
 379                 JournalFile *f,
 380                 int entry_fd,
 381                 uint64_t n_entries,
 382                 uint64_t entry_p,
 383                 uint64_t data_p) {
 384
 385         int r;
 386         uint64_t i, n, a;
 387         Object *o;
 388         bool found = false;
 389
 390         assert(f);
 391         assert(entry_fd >= 0);
 392
 393         if (!contains_uint64(f->mmap, entry_fd, n_entries, entry_p)) {
 394                 log_error("Data object references invalid entry at %"PRIu64, data_p);
 395                 return -EBADMSG;
 396         }
 397
 398         r = journal_file_move_to_object(f, OBJECT_ENTRY, entry_p, &o);
 399         if (r < 0)
 400                 return r;
 401
 402         n = journal_file_entry_n_items(o);
 403         for (i = 0; i < n; i++)
 404                 if (le64toh(o->entry.items[i].object_offset) == data_p) {
 405                         found = true;
 406                         break;
 407                 }
 408
 409         if (!found) {
 410                 log_error("Data object not referenced by linked entry at %"PRIu64, data_p);
 411                 return -EBADMSG;
 412         }
 413
 414         /* Check if this entry is also in main entry array. Since the
 415          * main entry array has already been verified we can rely on
 416          * its consistency.*/
 417
 418         i = 0;
 419         n = le64toh(f->header->n_entries);
 420         a = le64toh(f->header->entry_array_offset);
 421
 422         while (i < n) {
 423                 uint64_t m, u;
 424
 425                 r = journal_file_move_to_object(f, OBJECT_ENTRY_ARRAY, a, &o);
 426                 if (r < 0)
 427                         return r;
 428
 429                 m = journal_file_entry_array_n_items(o);
 430                 u = MIN(n - i, m);
 431
 432                 if (entry_p <= le64toh(o->entry_array.items[u-1])) {
 433                         uint64_t x, y, z;
 434
 435                         x = 0;
 436                         y = u;
 437
 438                         while (x < y) {
 439                                 z = (x + y) / 2;
 440
 441                                 if (le64toh(o->entry_array.items[z]) == entry_p)
 442                                         return 0;
 443
 444                                 if (x + 1 >= y)
 445                                         break;
 446
 447                                 if (entry_p < le64toh(o->entry_array.items[z]))
 448                                         y = z;
 449                                 else
 450                                         x = z;
 451                         }
 452
 453                         log_error("Entry object doesn't exist in main entry array at %"PRIu64, entry_p);
 454                         return -EBADMSG;
 455                 }
 456
 457                 i += u;
 458                 a = le64toh(o->entry_array.next_entry_array_offset);
 459         }
 460
 461         return 0;
 462 }
 463
 464 static int verify_data(
 465                 JournalFile *f,
 466                 Object *o, uint64_t p,
 467                 int entry_fd, uint64_t n_entries,
 468                 int entry_array_fd, uint64_t n_entry_arrays) {
 469
 470         uint64_t i, n, a, last, q;
 471         int r;
 472
 473         assert(f);
 474         assert(o);
 475         assert(entry_fd >= 0);
 476         assert(entry_array_fd >= 0);
 477
 478         n = le64toh(o->data.n_entries);
 479         a = le64toh(o->data.entry_array_offset);
 480
 481         /* Entry array means at least two objects */
 482         if (a && n < 2) {
 483                 log_error("Entry array present (entry_array_offset=%"PRIu64", but n_entries=%"PRIu64,
 484                           a, n);
 485                 return -EBADMSG;
 486         }
 487
 488         if (n == 0)
 489                 return 0;
 490
 491         /* We already checked that earlier */
 492         assert(o->data.entry_offset);
 493
 494         last = q = le64toh(o->data.entry_offset);
 495         r = entry_points_to_data(f, entry_fd, n_entries, q, p);
 496         if (r < 0)
 497                 return r;
 498
 499         i = 1;
 500         while (i < n) {
 501                 uint64_t next, m, j;
 502
 503                 if (a == 0) {
 504                         log_error("Array chain too short at %"PRIu64, p);
 505                         return -EBADMSG;
 506                 }
 507
 508                 if (!contains_uint64(f->mmap, entry_array_fd, n_entry_arrays, a)) {
 509                         log_error("Invalid array at %"PRIu64, p);
 510                         return -EBADMSG;
 511                 }
 512
 513                 r = journal_file_move_to_object(f, OBJECT_ENTRY_ARRAY, a, &o);
 514                 if (r < 0)
 515                         return r;
 516
 517                 next = le64toh(o->entry_array.next_entry_array_offset);
 518                 if (next != 0 && next <= a) {
 519                         log_error("Array chain has cycle at %"PRIu64, p);
 520                         return -EBADMSG;
 521                 }
 522
 523                 m = journal_file_entry_array_n_items(o);
 524                 for (j = 0; i < n && j < m; i++, j++) {
 525
 526                         q = le64toh(o->entry_array.items[j]);
 527                         if (q <= last) {
 528                                 log_error("Data object's entry array not sorted at %"PRIu64, p);
 529                                 return -EBADMSG;
 530                         }
 531                         last = q;
 532
 533                         r = entry_points_to_data(f, entry_fd, n_entries, q, p);
 534                         if (r < 0)
 535                                 return r;
 536
 537                         /* Pointer might have moved, reposition */
 538                         r = journal_file_move_to_object(f, OBJECT_ENTRY_ARRAY, a, &o);
 539                         if (r < 0)
 540                                 return r;
 541                 }
 542
 543                 a = next;
 544         }
 545
 546         return 0;
 547 }
 548
 549 static int verify_hash_table(
 550                 JournalFile *f,
 551                 int data_fd, uint64_t n_data,
 552                 int entry_fd, uint64_t n_entries,
 553                 int entry_array_fd, uint64_t n_entry_arrays,
 554                 usec_t *last_usec,
 555                 bool show_progress) {
 556
 557         uint64_t i, n;
 558         int r;
 559
 560         assert(f);
 561         assert(data_fd >= 0);
 562         assert(entry_fd >= 0);
 563         assert(entry_array_fd >= 0);
 564         assert(last_usec);
 565
 566         n = le64toh(f->header->data_hash_table_size) / sizeof(HashItem);
 567         for (i = 0; i < n; i++) {
 568                 uint64_t last = 0, p;
 569
 570                 if (show_progress)
 571                         draw_progress(0xC000 + (0x3FFF * i / n), last_usec);
 572
 573                 p = le64toh(f->data_hash_table[i].head_hash_offset);
 574                 while (p != 0) {
 575                         Object *o;
 576                         uint64_t next;
 577
 578                         if (!contains_uint64(f->mmap, data_fd, n_data, p)) {
 579                                 log_error("Invalid data object at hash entry %"PRIu64" of %"PRIu64,
 580                                           i, n);
 581                                 return -EBADMSG;
 582                         }
 583
 584                         r = journal_file_move_to_object(f, OBJECT_DATA, p, &o);
 585                         if (r < 0)
 586                                 return r;
 587
 588                         next = le64toh(o->data.next_hash_offset);
 589                         if (next != 0 && next <= p) {
 590                                 log_error("Hash chain has a cycle in hash entry %"PRIu64" of %"PRIu64,
 591                                           i, n);
 592                                 return -EBADMSG;
 593                         }
 594
 595                         if (le64toh(o->data.hash) % n != i) {
 596                                 log_error("Hash value mismatch in hash entry %"PRIu64" of %"PRIu64,
 597                                           i, n);
 598                                 return -EBADMSG;
 599                         }
 600
 601                         r = verify_data(f, o, p, entry_fd, n_entries, entry_array_fd, n_entry_arrays);
 602                         if (r < 0)
 603                                 return r;
 604
 605                         last = p;
 606                         p = next;
 607                 }
 608
 609                 if (last != le64toh(f->data_hash_table[i].tail_hash_offset)) {
 610                         log_error("Tail hash pointer mismatch in hash table");
 611                         return -EBADMSG;
 612                 }
 613         }
 614
 615         return 0;
 616 }
 617
 618 static int data_object_in_hash_table(JournalFile *f, uint64_t hash, uint64_t p) {
 619         uint64_t n, h, q;
 620         int r;
 621         assert(f);
 622
 623         n = le64toh(f->header->data_hash_table_size) / sizeof(HashItem);
 624         h = hash % n;
 625
 626         q = le64toh(f->data_hash_table[h].head_hash_offset);
 627         while (q != 0) {
 628                 Object *o;
 629
 630                 if (p == q)
 631                         return 1;
 632
 633                 r = journal_file_move_to_object(f, OBJECT_DATA, q, &o);
 634                 if (r < 0)
 635                         return r;
 636
 637                 q = le64toh(o->data.next_hash_offset);
 638         }
 639
 640         return 0;
 641 }
 642
 643 static int verify_entry(
 644                 JournalFile *f,
 645                 Object *o, uint64_t p,
 646                 int data_fd, uint64_t n_data) {
 647
 648         uint64_t i, n;
 649         int r;
 650
 651         assert(f);
 652         assert(o);
 653         assert(data_fd >= 0);
 654
 655         n = journal_file_entry_n_items(o);
 656         for (i = 0; i < n; i++) {
 657                 uint64_t q, h;
 658                 Object *u;
 659
 660                 q = le64toh(o->entry.items[i].object_offset);
 661                 h = le64toh(o->entry.items[i].hash);
 662
 663                 if (!contains_uint64(f->mmap, data_fd, n_data, q)) {
 664                         log_error("Invalid data object at entry %"PRIu64, p);
 665                                 return -EBADMSG;
 666                         }
 667
 668                 r = journal_file_move_to_object(f, OBJECT_DATA, q, &u);
 669                 if (r < 0)
 670                         return r;
 671
 672                 if (le64toh(u->data.hash) != h) {
 673                         log_error("Hash mismatch for data object at entry %"PRIu64, p);
 674                         return -EBADMSG;
 675                 }
 676
 677                 r = data_object_in_hash_table(f, h, q);
 678                 if (r < 0)
 679                         return r;
 680                 if (r == 0) {
 681                         log_error("Data object missing from hash at entry %"PRIu64, p);
 682                         return -EBADMSG;
 683                 }
 684         }
 685
 686         return 0;
 687 }
 688
 689 static int verify_entry_array(
 690                 JournalFile *f,
 691                 int data_fd, uint64_t n_data,
 692                 int entry_fd, uint64_t n_entries,
 693                 int entry_array_fd, uint64_t n_entry_arrays,
 694                 usec_t *last_usec,
 695                 bool show_progress) {
 696
 697         uint64_t i = 0, a, n, last = 0;
 698         int r;
 699
 700         assert(f);
 701         assert(data_fd >= 0);
 702         assert(entry_fd >= 0);
 703         assert(entry_array_fd >= 0);
 704         assert(last_usec);
 705
 706         n = le64toh(f->header->n_entries);
 707         a = le64toh(f->header->entry_array_offset);
 708         while (i < n) {
 709                 uint64_t next, m, j;
 710                 Object *o;
 711
 712                 if (show_progress)
 713                         draw_progress(0x8000 + (0x3FFF * i / n), last_usec);
 714
 715                 if (a == 0) {
 716                         log_error("Array chain too short at %"PRIu64" of %"PRIu64, i, n);
 717                         return -EBADMSG;
 718                 }
 719
 720                 if (!contains_uint64(f->mmap, entry_array_fd, n_entry_arrays, a)) {
 721                         log_error("Invalid array at %"PRIu64" of %"PRIu64, i, n);
 722                         return -EBADMSG;
 723                 }
 724
 725                 r = journal_file_move_to_object(f, OBJECT_ENTRY_ARRAY, a, &o);
 726                 if (r < 0)
 727                         return r;
 728
 729                 next = le64toh(o->entry_array.next_entry_array_offset);
 730                 if (next != 0 && next <= a) {
 731                         log_error("Array chain has cycle at %"PRIu64" of %"PRIu64, i, n);
 732                         return -EBADMSG;
 733                 }
 734
 735                 m = journal_file_entry_array_n_items(o);
 736                 for (j = 0; i < n && j < m; i++, j++) {
 737                         uint64_t p;
 738
 739                         p = le64toh(o->entry_array.items[j]);
 740                         if (p <= last) {
 741                                 log_error("Entry array not sorted at %"PRIu64" of %"PRIu64,
 742                                           i, n);
 743                                 return -EBADMSG;
 744                         }
 745                         last = p;
 746
 747                         if (!contains_uint64(f->mmap, entry_fd, n_entries, p)) {
 748                                 log_error("Invalid array entry at %"PRIu64" of %"PRIu64,
 749                                           i, n);
 750                                 return -EBADMSG;
 751                         }
 752
 753                         r = journal_file_move_to_object(f, OBJECT_ENTRY, p, &o);
 754                         if (r < 0)
 755                                 return r;
 756
 757                         r = verify_entry(f, o, p, data_fd, n_data);
 758                         if (r < 0)
 759                                 return r;
 760
 761                         /* Pointer might have moved, reposition */
 762                         r = journal_file_move_to_object(f, OBJECT_ENTRY_ARRAY, a, &o);
 763                         if (r < 0)
 764                                 return r;
 765                 }
 766
 767                 a = next;
 768         }
 769
 770         return 0;
 771 }
 772
 773 int journal_file_verify(
 774                 JournalFile *f,
 775                 const char *key,
 776                 usec_t *first_contained, usec_t *last_validated, usec_t *last_contained,
 777                 bool show_progress) {
 778         int r;
 779         Object *o;
 780         uint64_t p = 0, last_epoch = 0, last_tag_realtime = 0, last_sealed_realtime = 0;
 781
 782         uint64_t entry_seqnum = 0, entry_monotonic = 0, entry_realtime = 0;
 783         sd_id128_t entry_boot_id;
 784         bool entry_seqnum_set = false, entry_monotonic_set = false, entry_realtime_set = false, found_main_entry_array = false;
 785         uint64_t n_weird = 0, n_objects = 0, n_entries = 0, n_data = 0, n_fields = 0, n_data_hash_tables = 0, n_field_hash_tables = 0, n_entry_arrays = 0, n_tags = 0;
 786         usec_t last_usec = 0;
 787         int data_fd = -1, entry_fd = -1, entry_array_fd = -1;
 788         unsigned i;
 789         bool found_last;
 790 #ifdef HAVE_GCRYPT
 791         uint64_t last_tag = 0;
 792 #endif
 793         assert(f);
 794
 795         if (key) {
 796 #ifdef HAVE_GCRYPT
 797                 r = journal_file_parse_verification_key(f, key);
 798                 if (r < 0) {
 799                         log_error("Failed to parse seed.");
 800                         return r;
 801                 }
 802 #else
 803                 return -ENOTSUP;
 804 #endif
 805         } else if (f->seal)
 806                 return -ENOKEY;
 807
 808         data_fd = open_tmpfile("/var/tmp", O_RDWR | O_CLOEXEC);
 809         if (data_fd < 0) {
 810                 log_error("Failed to create data file: %m");
 811                 r = -errno;
 812                 goto fail;
 813         }
 814
 815         entry_fd = open_tmpfile("/var/tmp", O_RDWR | O_CLOEXEC);
 816         if (entry_fd < 0) {
 817                 log_error("Failed to create entry file: %m");
 818                 r = -errno;
 819                 goto fail;
 820         }
 821
 822         entry_array_fd = open_tmpfile("/var/tmp", O_RDWR | O_CLOEXEC);
 823         if (entry_array_fd < 0) {
 824                 log_error("Failed to create entry array file: %m");
 825                 r = -errno;
 826                 goto fail;
 827         }
 828
 829 #ifdef HAVE_GCRYPT
 830         if ((le32toh(f->header->compatible_flags) & ~HEADER_COMPATIBLE_SEALED) != 0)
 831 #else
 832         if (f->header->compatible_flags != 0)
 833 #endif
 834         {
 835                 log_error("Cannot verify file with unknown extensions.");
 836                 r = -ENOTSUP;
 837                 goto fail;
 838         }
 839
 840         for (i = 0; i < sizeof(f->header->reserved); i++)
 841                 if (f->header->reserved[i] != 0) {
 842                         log_error("Reserved field in non-zero.");
 843                         r = -EBADMSG;
 844                         goto fail;
 845                 }
 846
 847         /* First iteration: we go through all objects, verify the
 848          * superficial structure, headers, hashes. */
 849
 850         p = le64toh(f->header->header_size);
 851         while (p != 0) {
 852                 if (show_progress)
 853                         draw_progress(0x7FFF * p / le64toh(f->header->tail_object_offset), &last_usec);
 854
 855                 r = journal_file_move_to_object(f, -1, p, &o);
 856                 if (r < 0) {
 857                         log_error("Invalid object at "OFSfmt, p);
 858                         goto fail;
 859                 }
 860
 861                 if (p > le64toh(f->header->tail_object_offset)) {
 862                         log_error("Invalid tail object pointer");
 863                         r = -EBADMSG;
 864                         goto fail;
 865                 }
 866
 867                 if (p == le64toh(f->header->tail_object_offset))
 868                         found_last = true;
 869
 870                 n_objects ++;
 871
 872                 r = journal_file_object_verify(f, p, o);
 873                 if (r < 0) {
 874                         log_error("Invalid object contents at "OFSfmt": %s", p, strerror(-r));
 875                         goto fail;
 876                 }
 877
 878                 if ((o->object.flags & OBJECT_COMPRESSED) && !JOURNAL_HEADER_COMPRESSED(f->header)) {
 879                         log_error("Compressed object in file without compression at "OFSfmt, p);
 880                         r = -EBADMSG;
 881                         goto fail;
 882                 }
 883
 884                 switch (o->object.type) {
 885
 886                 case OBJECT_DATA:
 887                         r = write_uint64(data_fd, p);
 888                         if (r < 0)
 889                                 goto fail;
 890
 891                         n_data++;
 892                         break;
 893
 894                 case OBJECT_FIELD:
 895                         n_fields++;
 896                         break;
 897
 898                 case OBJECT_ENTRY:
 899                         if (JOURNAL_HEADER_SEALED(f->header) && n_tags <= 0) {
 900                                 log_error("First entry before first tag at "OFSfmt, p);
 901                                 r = -EBADMSG;
 902                                 goto fail;
 903                         }
 904
 905                         r = write_uint64(entry_fd, p);
 906                         if (r < 0)
 907                                 goto fail;
 908
 909                         if (le64toh(o->entry.realtime) < last_tag_realtime) {
 910                                 log_error("Older entry after newer tag at "OFSfmt, p);
 911                                 r = -EBADMSG;
 912                                 goto fail;
 913                         }
 914
 915                         if (!entry_seqnum_set &&
 916                             le64toh(o->entry.seqnum) != le64toh(f->header->head_entry_seqnum)) {
 917                                 log_error("Head entry sequence number incorrect at "OFSfmt, p);
 918                                 r = -EBADMSG;
 919                                 goto fail;
 920                         }
 921
 922                         if (entry_seqnum_set &&
 923                             entry_seqnum >= le64toh(o->entry.seqnum)) {
 924                                 log_error("Entry sequence number out of synchronization at "OFSfmt, p);
 925                                 r = -EBADMSG;
 926                                 goto fail;
 927                         }
 928
 929                         entry_seqnum = le64toh(o->entry.seqnum);
 930                         entry_seqnum_set = true;
 931
 932                         if (entry_monotonic_set &&
 933                             sd_id128_equal(entry_boot_id, o->entry.boot_id) &&
 934                             entry_monotonic > le64toh(o->entry.monotonic)) {
 935                                 log_error("Entry timestamp out of synchronization at "OFSfmt, p);
 936                                 r = -EBADMSG;
 937                                 goto fail;
 938                         }
 939
 940                         entry_monotonic = le64toh(o->entry.monotonic);
 941                         entry_boot_id = o->entry.boot_id;
 942                         entry_monotonic_set = true;
 943
 944                         if (!entry_realtime_set &&
 945                             le64toh(o->entry.realtime) != le64toh(f->header->head_entry_realtime)) {
 946                                 log_error("Head entry realtime timestamp incorrect");
 947                                 r = -EBADMSG;
 948                                 goto fail;
 949                         }
 950
 951                         entry_realtime = le64toh(o->entry.realtime);
 952                         entry_realtime_set = true;
 953
 954                         n_entries ++;
 955                         break;
 956
 957                 case OBJECT_DATA_HASH_TABLE:
 958                         if (n_data_hash_tables > 1) {
 959                                 log_error("More than one data hash table at "OFSfmt, p);
 960                                 r = -EBADMSG;
 961                                 goto fail;
 962                         }
 963
 964                         if (le64toh(f->header->data_hash_table_offset) != p + offsetof(HashTableObject, items) ||
 965                             le64toh(f->header->data_hash_table_size) != le64toh(o->object.size) - offsetof(HashTableObject, items)) {
 966                                 log_error("Header fields for data hash table invalid");
 967                                 r = -EBADMSG;
 968                                 goto fail;
 969                         }
 970
 971                         n_data_hash_tables++;
 972                         break;
 973
 974                 case OBJECT_FIELD_HASH_TABLE:
 975                         if (n_field_hash_tables > 1) {
 976                                 log_error("More than one field hash table at "OFSfmt, p);
 977                                 r = -EBADMSG;
 978                                 goto fail;
 979                         }
 980
 981                         if (le64toh(f->header->field_hash_table_offset) != p + offsetof(HashTableObject, items) ||
 982                             le64toh(f->header->field_hash_table_size) != le64toh(o->object.size) - offsetof(HashTableObject, items)) {
 983                                 log_error("Header fields for field hash table invalid");
 984                                 r = -EBADMSG;
 985                                 goto fail;
 986                         }
 987
 988                         n_field_hash_tables++;
 989                         break;
 990
 991                 case OBJECT_ENTRY_ARRAY:
 992                         r = write_uint64(entry_array_fd, p);
 993                         if (r < 0)
 994                                 goto fail;
 995
 996                         if (p == le64toh(f->header->entry_array_offset)) {
 997                                 if (found_main_entry_array) {
 998                                         log_error("More than one main entry array at "OFSfmt, p);
 999                                         r = -EBADMSG;
1000                                         goto fail;
1001                                 }
1002
1003                                 found_main_entry_array = true;
1004                         }
1005
1006                         n_entry_arrays++;
1007                         break;
1008
1009                 case OBJECT_TAG:
1010                         if (!JOURNAL_HEADER_SEALED(f->header)) {
1011                                 log_error("Tag object in file without sealing at "OFSfmt, p);
1012                                 r = -EBADMSG;
1013                                 goto fail;
1014                         }
1015
1016                         if (le64toh(o->tag.seqnum) != n_tags + 1) {
1017                                 log_error("Tag sequence number out of synchronization at "OFSfmt, p);
1018                                 r = -EBADMSG;
1019                                 goto fail;
1020                         }
1021
1022                         if (le64toh(o->tag.epoch) < last_epoch) {
1023                                 log_error("Epoch sequence out of synchronization at "OFSfmt, p);
1024                                 r = -EBADMSG;
1025                                 goto fail;
1026                         }
1027
1028 #ifdef HAVE_GCRYPT
1029                         if (f->seal) {
1030                                 uint64_t q, rt;
1031
1032                                 log_debug("Checking tag %"PRIu64"...", le64toh(o->tag.seqnum));
1033
1034                                 rt = f->fss_start_usec + o->tag.epoch * f->fss_interval_usec;
1035                                 if (entry_realtime_set && entry_realtime >= rt + f->fss_interval_usec) {
1036                                         log_error("Tag/entry realtime timestamp out of synchronization at "OFSfmt, p);
1037                                         r = -EBADMSG;
1038                                         goto fail;
1039                                 }
1040
1041                                 /* OK, now we know the epoch. So let's now set
1042                                  * it, and calculate the HMAC for everything
1043                                  * since the last tag. */
1044                                 r = journal_file_fsprg_seek(f, le64toh(o->tag.epoch));
1045                                 if (r < 0)
1046                                         goto fail;
1047
1048                                 r = journal_file_hmac_start(f);
1049                                 if (r < 0)
1050                                         goto fail;
1051
1052                                 if (last_tag == 0) {
1053                                         r = journal_file_hmac_put_header(f);
1054                                         if (r < 0)
1055                                                 goto fail;
1056
1057                                         q = le64toh(f->header->header_size);
1058                                 } else
1059                                         q = last_tag;
1060
1061                                 while (q <= p) {
1062                                         r = journal_file_move_to_object(f, -1, q, &o);
1063                                         if (r < 0)
1064                                                 goto fail;
1065
1066                                         r = journal_file_hmac_put_object(f, -1, o, q);
1067                                         if (r < 0)
1068                                                 goto fail;
1069
1070                                         q = q + ALIGN64(le64toh(o->object.size));
1071                                 }
1072
1073                                 /* Position might have changed, let's reposition things */
1074                                 r = journal_file_move_to_object(f, -1, p, &o);
1075                                 if (r < 0)
1076                                         goto fail;
1077
1078                                 if (memcmp(o->tag.tag, gcry_md_read(f->hmac, 0), TAG_LENGTH) != 0) {
1079                                         log_error("Tag failed verification at "OFSfmt, p);
1080                                         r = -EBADMSG;
1081                                         goto fail;
1082                                 }
1083
1084                                 f->hmac_running = false;
1085                                 last_tag_realtime = rt;
1086                                 last_sealed_realtime = entry_realtime;
1087                         }
1088
1089                         last_tag = p + ALIGN64(le64toh(o->object.size));
1090 #endif
1091
1092                         last_epoch = le64toh(o->tag.epoch);
1093
1094                         n_tags ++;
1095                         break;
1096
1097                 default:
1098                         n_weird ++;
1099                 }
1100
1101                 if (p == le64toh(f->header->tail_object_offset))
1102                         p = 0;
1103                 else
1104                         p = p + ALIGN64(le64toh(o->object.size));
1105         }
1106
1107         if (!found_last) {
1108                 log_error("Tail object pointer dead");
1109                 r = -EBADMSG;
1110                 goto fail;
1111         }
1112
1113         if (n_objects != le64toh(f->header->n_objects)) {
1114                 log_error("Object number mismatch");
1115                 r = -EBADMSG;
1116                 goto fail;
1117         }
1118
1119         if (n_entries != le64toh(f->header->n_entries)) {
1120                 log_error("Entry number mismatch");
1121                 r = -EBADMSG;
1122                 goto fail;
1123         }
1124
1125         if (JOURNAL_HEADER_CONTAINS(f->header, n_data) &&
1126             n_data != le64toh(f->header->n_data)) {
1127                 log_error("Data number mismatch");
1128                 r = -EBADMSG;
1129                 goto fail;
1130         }
1131
1132         if (JOURNAL_HEADER_CONTAINS(f->header, n_fields) &&
1133             n_fields != le64toh(f->header->n_fields)) {
1134                 log_error("Field number mismatch");
1135                 r = -EBADMSG;
1136                 goto fail;
1137         }
1138
1139         if (JOURNAL_HEADER_CONTAINS(f->header, n_tags) &&
1140             n_tags != le64toh(f->header->n_tags)) {
1141                 log_error("Tag number mismatch");
1142                 r = -EBADMSG;
1143                 goto fail;
1144         }
1145
1146         if (JOURNAL_HEADER_CONTAINS(f->header, n_entry_arrays) &&
1147             n_entry_arrays != le64toh(f->header->n_entry_arrays)) {
1148                 log_error("Entry array number mismatch");
1149                 r = -EBADMSG;
1150                 goto fail;
1151         }
1152
1153         if (n_data_hash_tables != 1) {
1154                 log_error("Missing data hash table");
1155                 r = -EBADMSG;
1156                 goto fail;
1157         }
1158
1159         if (n_field_hash_tables != 1) {
1160                 log_error("Missing field hash table");
1161                 r = -EBADMSG;
1162                 goto fail;
1163         }
1164
1165         if (!found_main_entry_array) {
1166                 log_error("Missing entry array");
1167                 r = -EBADMSG;
1168                 goto fail;
1169         }
1170
1171         if (entry_seqnum_set &&
1172             entry_seqnum != le64toh(f->header->tail_entry_seqnum)) {
1173                 log_error("Invalid tail seqnum");
1174                 r = -EBADMSG;
1175                 goto fail;
1176         }
1177
1178         if (entry_monotonic_set &&
1179             (!sd_id128_equal(entry_boot_id, f->header->boot_id) ||
1180              entry_monotonic != le64toh(f->header->tail_entry_monotonic))) {
1181                 log_error("Invalid tail monotonic timestamp");
1182                 r = -EBADMSG;
1183                 goto fail;
1184         }
1185
1186         if (entry_realtime_set && entry_realtime != le64toh(f->header->tail_entry_realtime)) {
1187                 log_error("Invalid tail realtime timestamp");
1188                 r = -EBADMSG;
1189                 goto fail;
1190         }
1191
1192         /* Second iteration: we follow all objects referenced from the
1193          * two entry points: the object hash table and the entry
1194          * array. We also check that everything referenced (directly
1195          * or indirectly) in the data hash table also exists in the
1196          * entry array, and vice versa. Note that we do not care for
1197          * unreferenced objects. We only care that everything that is
1198          * referenced is consistent. */
1199
1200         r = verify_entry_array(f,
1201                                data_fd, n_data,
1202                                entry_fd, n_entries,
1203                                entry_array_fd, n_entry_arrays,
1204                                &last_usec,
1205                                show_progress);
1206         if (r < 0)
1207                 goto fail;
1208
1209         r = verify_hash_table(f,
1210                               data_fd, n_data,
1211                               entry_fd, n_entries,
1212                               entry_array_fd, n_entry_arrays,
1213                               &last_usec,
1214                               show_progress);
1215         if (r < 0)
1216                 goto fail;
1217
1218         if (show_progress)
1219                 flush_progress();
1220
1221         mmap_cache_close_fd(f->mmap, data_fd);
1222         mmap_cache_close_fd(f->mmap, entry_fd);
1223         mmap_cache_close_fd(f->mmap, entry_array_fd);
1224
1225         safe_close(data_fd);
1226         safe_close(entry_fd);
1227         safe_close(entry_array_fd);
1228
1229         if (first_contained)
1230                 *first_contained = le64toh(f->header->head_entry_realtime);
1231         if (last_validated)
1232                 *last_validated = last_sealed_realtime;
1233         if (last_contained)
1234                 *last_contained = le64toh(f->header->tail_entry_realtime);
1235
1236         return 0;
1237
1238 fail:
1239         if (show_progress)
1240                 flush_progress();
1241
1242         log_error("File corruption detected at %s:"OFSfmt" (of %llu bytes, %"PRIu64"%%).",
1243                   f->path,
1244                   p,
1245                   (unsigned long long) f->last_stat.st_size,
1246                   100 * p / f->last_stat.st_size);
1247
1248         if (data_fd >= 0) {
1249                 mmap_cache_close_fd(f->mmap, data_fd);
1250                 safe_close(data_fd);
1251         }
1252
1253         if (entry_fd >= 0) {
1254                 mmap_cache_close_fd(f->mmap, entry_fd);
1255                 safe_close(entry_fd);
1256         }
1257
1258         if (entry_array_fd >= 0) {
1259                 mmap_cache_close_fd(f->mmap, entry_array_fd);
1260                 safe_close(entry_array_fd);
1261         }
1262
1263         return r;
1264 }