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         char data_path[] = "/var/tmp/journal-data-XXXXXX",
 789                 entry_path[] = "/var/tmp/journal-entry-XXXXXX",
 790                 entry_array_path[] = "/var/tmp/journal-entry-array-XXXXXX";
 791         unsigned i;
 792         bool found_last;
 793 #ifdef HAVE_GCRYPT
 794         uint64_t last_tag = 0;
 795 #endif
 796         assert(f);
 797
 798         if (key) {
 799 #ifdef HAVE_GCRYPT
 800                 r = journal_file_parse_verification_key(f, key);
 801                 if (r < 0) {
 802                         log_error("Failed to parse seed.");
 803                         return r;
 804                 }
 805 #else
 806                 return -ENOTSUP;
 807 #endif
 808         } else if (f->seal)
 809                 return -ENOKEY;
 810
 811         data_fd = mkostemp(data_path, O_CLOEXEC);
 812         if (data_fd < 0) {
 813                 log_error("Failed to create data file: %m");
 814                 r = -errno;
 815                 goto fail;
 816         }
 817         unlink(data_path);
 818
 819         entry_fd = mkostemp(entry_path, O_CLOEXEC);
 820         if (entry_fd < 0) {
 821                 log_error("Failed to create entry file: %m");
 822                 r = -errno;
 823                 goto fail;
 824         }
 825         unlink(entry_path);
 826
 827         entry_array_fd = mkostemp(entry_array_path, O_CLOEXEC);
 828         if (entry_array_fd < 0) {
 829                 log_error("Failed to create entry array file: %m");
 830                 r = -errno;
 831                 goto fail;
 832         }
 833         unlink(entry_array_path);
 834
 835 #ifdef HAVE_GCRYPT
 836         if ((le32toh(f->header->compatible_flags) & ~HEADER_COMPATIBLE_SEALED) != 0)
 837 #else
 838         if (f->header->compatible_flags != 0)
 839 #endif
 840         {
 841                 log_error("Cannot verify file with unknown extensions.");
 842                 r = -ENOTSUP;
 843                 goto fail;
 844         }
 845
 846         for (i = 0; i < sizeof(f->header->reserved); i++)
 847                 if (f->header->reserved[i] != 0) {
 848                         log_error("Reserved field in non-zero.");
 849                         r = -EBADMSG;
 850                         goto fail;
 851                 }
 852
 853         /* First iteration: we go through all objects, verify the
 854          * superficial structure, headers, hashes. */
 855
 856         p = le64toh(f->header->header_size);
 857         while (p != 0) {
 858                 if (show_progress)
 859                         draw_progress(0x7FFF * p / le64toh(f->header->tail_object_offset), &last_usec);
 860
 861                 r = journal_file_move_to_object(f, -1, p, &o);
 862                 if (r < 0) {
 863                         log_error("Invalid object at "OFSfmt, p);
 864                         goto fail;
 865                 }
 866
 867                 if (p > le64toh(f->header->tail_object_offset)) {
 868                         log_error("Invalid tail object pointer");
 869                         r = -EBADMSG;
 870                         goto fail;
 871                 }
 872
 873                 if (p == le64toh(f->header->tail_object_offset))
 874                         found_last = true;
 875
 876                 n_objects ++;
 877
 878                 r = journal_file_object_verify(f, p, o);
 879                 if (r < 0) {
 880                         log_error("Invalid object contents at "OFSfmt": %s", p, strerror(-r));
 881                         goto fail;
 882                 }
 883
 884                 if ((o->object.flags & OBJECT_COMPRESSED) && !JOURNAL_HEADER_COMPRESSED(f->header)) {
 885                         log_error("Compressed object in file without compression at "OFSfmt, p);
 886                         r = -EBADMSG;
 887                         goto fail;
 888                 }
 889
 890                 switch (o->object.type) {
 891
 892                 case OBJECT_DATA:
 893                         r = write_uint64(data_fd, p);
 894                         if (r < 0)
 895                                 goto fail;
 896
 897                         n_data++;
 898                         break;
 899
 900                 case OBJECT_FIELD:
 901                         n_fields++;
 902                         break;
 903
 904                 case OBJECT_ENTRY:
 905                         if (JOURNAL_HEADER_SEALED(f->header) && n_tags <= 0) {
 906                                 log_error("First entry before first tag at "OFSfmt, p);
 907                                 r = -EBADMSG;
 908                                 goto fail;
 909                         }
 910
 911                         r = write_uint64(entry_fd, p);
 912                         if (r < 0)
 913                                 goto fail;
 914
 915                         if (le64toh(o->entry.realtime) < last_tag_realtime) {
 916                                 log_error("Older entry after newer tag at "OFSfmt, p);
 917                                 r = -EBADMSG;
 918                                 goto fail;
 919                         }
 920
 921                         if (!entry_seqnum_set &&
 922                             le64toh(o->entry.seqnum) != le64toh(f->header->head_entry_seqnum)) {
 923                                 log_error("Head entry sequence number incorrect at "OFSfmt, p);
 924                                 r = -EBADMSG;
 925                                 goto fail;
 926                         }
 927
 928                         if (entry_seqnum_set &&
 929                             entry_seqnum >= le64toh(o->entry.seqnum)) {
 930                                 log_error("Entry sequence number out of synchronization at "OFSfmt, p);
 931                                 r = -EBADMSG;
 932                                 goto fail;
 933                         }
 934
 935                         entry_seqnum = le64toh(o->entry.seqnum);
 936                         entry_seqnum_set = true;
 937
 938                         if (entry_monotonic_set &&
 939                             sd_id128_equal(entry_boot_id, o->entry.boot_id) &&
 940                             entry_monotonic > le64toh(o->entry.monotonic)) {
 941                                 log_error("Entry timestamp out of synchronization at "OFSfmt, p);
 942                                 r = -EBADMSG;
 943                                 goto fail;
 944                         }
 945
 946                         entry_monotonic = le64toh(o->entry.monotonic);
 947                         entry_boot_id = o->entry.boot_id;
 948                         entry_monotonic_set = true;
 949
 950                         if (!entry_realtime_set &&
 951                             le64toh(o->entry.realtime) != le64toh(f->header->head_entry_realtime)) {
 952                                 log_error("Head entry realtime timestamp incorrect");
 953                                 r = -EBADMSG;
 954                                 goto fail;
 955                         }
 956
 957                         entry_realtime = le64toh(o->entry.realtime);
 958                         entry_realtime_set = true;
 959
 960                         n_entries ++;
 961                         break;
 962
 963                 case OBJECT_DATA_HASH_TABLE:
 964                         if (n_data_hash_tables > 1) {
 965                                 log_error("More than one data hash table at "OFSfmt, p);
 966                                 r = -EBADMSG;
 967                                 goto fail;
 968                         }
 969
 970                         if (le64toh(f->header->data_hash_table_offset) != p + offsetof(HashTableObject, items) ||
 971                             le64toh(f->header->data_hash_table_size) != le64toh(o->object.size) - offsetof(HashTableObject, items)) {
 972                                 log_error("Header fields for data hash table invalid");
 973                                 r = -EBADMSG;
 974                                 goto fail;
 975                         }
 976
 977                         n_data_hash_tables++;
 978                         break;
 979
 980                 case OBJECT_FIELD_HASH_TABLE:
 981                         if (n_field_hash_tables > 1) {
 982                                 log_error("More than one field hash table at "OFSfmt, p);
 983                                 r = -EBADMSG;
 984                                 goto fail;
 985                         }
 986
 987                         if (le64toh(f->header->field_hash_table_offset) != p + offsetof(HashTableObject, items) ||
 988                             le64toh(f->header->field_hash_table_size) != le64toh(o->object.size) - offsetof(HashTableObject, items)) {
 989                                 log_error("Header fields for field hash table invalid");
 990                                 r = -EBADMSG;
 991                                 goto fail;
 992                         }
 993
 994                         n_field_hash_tables++;
 995                         break;
 996
 997                 case OBJECT_ENTRY_ARRAY:
 998                         r = write_uint64(entry_array_fd, p);
 999                         if (r < 0)
1000                                 goto fail;
1001
1002                         if (p == le64toh(f->header->entry_array_offset)) {
1003                                 if (found_main_entry_array) {
1004                                         log_error("More than one main entry array at "OFSfmt, p);
1005                                         r = -EBADMSG;
1006                                         goto fail;
1007                                 }
1008
1009                                 found_main_entry_array = true;
1010                         }
1011
1012                         n_entry_arrays++;
1013                         break;
1014
1015                 case OBJECT_TAG:
1016                         if (!JOURNAL_HEADER_SEALED(f->header)) {
1017                                 log_error("Tag object in file without sealing at "OFSfmt, p);
1018                                 r = -EBADMSG;
1019                                 goto fail;
1020                         }
1021
1022                         if (le64toh(o->tag.seqnum) != n_tags + 1) {
1023                                 log_error("Tag sequence number out of synchronization at "OFSfmt, p);
1024                                 r = -EBADMSG;
1025                                 goto fail;
1026                         }
1027
1028                         if (le64toh(o->tag.epoch) < last_epoch) {
1029                                 log_error("Epoch sequence out of synchronization at "OFSfmt, p);
1030                                 r = -EBADMSG;
1031                                 goto fail;
1032                         }
1033
1034 #ifdef HAVE_GCRYPT
1035                         if (f->seal) {
1036                                 uint64_t q, rt;
1037
1038                                 log_debug("Checking tag %"PRIu64"...", le64toh(o->tag.seqnum));
1039
1040                                 rt = f->fss_start_usec + o->tag.epoch * f->fss_interval_usec;
1041                                 if (entry_realtime_set && entry_realtime >= rt + f->fss_interval_usec) {
1042                                         log_error("Tag/entry realtime timestamp out of synchronization at "OFSfmt, p);
1043                                         r = -EBADMSG;
1044                                         goto fail;
1045                                 }
1046
1047                                 /* OK, now we know the epoch. So let's now set
1048                                  * it, and calculate the HMAC for everything
1049                                  * since the last tag. */
1050                                 r = journal_file_fsprg_seek(f, le64toh(o->tag.epoch));
1051                                 if (r < 0)
1052                                         goto fail;
1053
1054                                 r = journal_file_hmac_start(f);
1055                                 if (r < 0)
1056                                         goto fail;
1057
1058                                 if (last_tag == 0) {
1059                                         r = journal_file_hmac_put_header(f);
1060                                         if (r < 0)
1061                                                 goto fail;
1062
1063                                         q = le64toh(f->header->header_size);
1064                                 } else
1065                                         q = last_tag;
1066
1067                                 while (q <= p) {
1068                                         r = journal_file_move_to_object(f, -1, q, &o);
1069                                         if (r < 0)
1070                                                 goto fail;
1071
1072                                         r = journal_file_hmac_put_object(f, -1, o, q);
1073                                         if (r < 0)
1074                                                 goto fail;
1075
1076                                         q = q + ALIGN64(le64toh(o->object.size));
1077                                 }
1078
1079                                 /* Position might have changed, let's reposition things */
1080                                 r = journal_file_move_to_object(f, -1, p, &o);
1081                                 if (r < 0)
1082                                         goto fail;
1083
1084                                 if (memcmp(o->tag.tag, gcry_md_read(f->hmac, 0), TAG_LENGTH) != 0) {
1085                                         log_error("Tag failed verification at "OFSfmt, p);
1086                                         r = -EBADMSG;
1087                                         goto fail;
1088                                 }
1089
1090                                 f->hmac_running = false;
1091                                 last_tag_realtime = rt;
1092                                 last_sealed_realtime = entry_realtime;
1093                         }
1094
1095                         last_tag = p + ALIGN64(le64toh(o->object.size));
1096 #endif
1097
1098                         last_epoch = le64toh(o->tag.epoch);
1099
1100                         n_tags ++;
1101                         break;
1102
1103                 default:
1104                         n_weird ++;
1105                 }
1106
1107                 if (p == le64toh(f->header->tail_object_offset))
1108                         p = 0;
1109                 else
1110                         p = p + ALIGN64(le64toh(o->object.size));
1111         }
1112
1113         if (!found_last) {
1114                 log_error("Tail object pointer dead");
1115                 r = -EBADMSG;
1116                 goto fail;
1117         }
1118
1119         if (n_objects != le64toh(f->header->n_objects)) {
1120                 log_error("Object number mismatch");
1121                 r = -EBADMSG;
1122                 goto fail;
1123         }
1124
1125         if (n_entries != le64toh(f->header->n_entries)) {
1126                 log_error("Entry number mismatch");
1127                 r = -EBADMSG;
1128                 goto fail;
1129         }
1130
1131         if (JOURNAL_HEADER_CONTAINS(f->header, n_data) &&
1132             n_data != le64toh(f->header->n_data)) {
1133                 log_error("Data number mismatch");
1134                 r = -EBADMSG;
1135                 goto fail;
1136         }
1137
1138         if (JOURNAL_HEADER_CONTAINS(f->header, n_fields) &&
1139             n_fields != le64toh(f->header->n_fields)) {
1140                 log_error("Field number mismatch");
1141                 r = -EBADMSG;
1142                 goto fail;
1143         }
1144
1145         if (JOURNAL_HEADER_CONTAINS(f->header, n_tags) &&
1146             n_tags != le64toh(f->header->n_tags)) {
1147                 log_error("Tag number mismatch");
1148                 r = -EBADMSG;
1149                 goto fail;
1150         }
1151
1152         if (JOURNAL_HEADER_CONTAINS(f->header, n_entry_arrays) &&
1153             n_entry_arrays != le64toh(f->header->n_entry_arrays)) {
1154                 log_error("Entry array number mismatch");
1155                 r = -EBADMSG;
1156                 goto fail;
1157         }
1158
1159         if (n_data_hash_tables != 1) {
1160                 log_error("Missing data hash table");
1161                 r = -EBADMSG;
1162                 goto fail;
1163         }
1164
1165         if (n_field_hash_tables != 1) {
1166                 log_error("Missing field hash table");
1167                 r = -EBADMSG;
1168                 goto fail;
1169         }
1170
1171         if (!found_main_entry_array) {
1172                 log_error("Missing entry array");
1173                 r = -EBADMSG;
1174                 goto fail;
1175         }
1176
1177         if (entry_seqnum_set &&
1178             entry_seqnum != le64toh(f->header->tail_entry_seqnum)) {
1179                 log_error("Invalid tail seqnum");
1180                 r = -EBADMSG;
1181                 goto fail;
1182         }
1183
1184         if (entry_monotonic_set &&
1185             (!sd_id128_equal(entry_boot_id, f->header->boot_id) ||
1186              entry_monotonic != le64toh(f->header->tail_entry_monotonic))) {
1187                 log_error("Invalid tail monotonic timestamp");
1188                 r = -EBADMSG;
1189                 goto fail;
1190         }
1191
1192         if (entry_realtime_set && entry_realtime != le64toh(f->header->tail_entry_realtime)) {
1193                 log_error("Invalid tail realtime timestamp");
1194                 r = -EBADMSG;
1195                 goto fail;
1196         }
1197
1198         /* Second iteration: we follow all objects referenced from the
1199          * two entry points: the object hash table and the entry
1200          * array. We also check that everything referenced (directly
1201          * or indirectly) in the data hash table also exists in the
1202          * entry array, and vice versa. Note that we do not care for
1203          * unreferenced objects. We only care that everything that is
1204          * referenced is consistent. */
1205
1206         r = verify_entry_array(f,
1207                                data_fd, n_data,
1208                                entry_fd, n_entries,
1209                                entry_array_fd, n_entry_arrays,
1210                                &last_usec,
1211                                show_progress);
1212         if (r < 0)
1213                 goto fail;
1214
1215         r = verify_hash_table(f,
1216                               data_fd, n_data,
1217                               entry_fd, n_entries,
1218                               entry_array_fd, n_entry_arrays,
1219                               &last_usec,
1220                               show_progress);
1221         if (r < 0)
1222                 goto fail;
1223
1224         if (show_progress)
1225                 flush_progress();
1226
1227         mmap_cache_close_fd(f->mmap, data_fd);
1228         mmap_cache_close_fd(f->mmap, entry_fd);
1229         mmap_cache_close_fd(f->mmap, entry_array_fd);
1230
1231         close_nointr_nofail(data_fd);
1232         close_nointr_nofail(entry_fd);
1233         close_nointr_nofail(entry_array_fd);
1234
1235         if (first_contained)
1236                 *first_contained = le64toh(f->header->head_entry_realtime);
1237         if (last_validated)
1238                 *last_validated = last_sealed_realtime;
1239         if (last_contained)
1240                 *last_contained = le64toh(f->header->tail_entry_realtime);
1241
1242         return 0;
1243
1244 fail:
1245         if (show_progress)
1246                 flush_progress();
1247
1248         log_error("File corruption detected at %s:"OFSfmt" (of %llu bytes, %"PRIu64"%%).",
1249                   f->path,
1250                   p,
1251                   (unsigned long long) f->last_stat.st_size,
1252                   100 * p / f->last_stat.st_size);
1253
1254         if (data_fd >= 0) {
1255                 mmap_cache_close_fd(f->mmap, data_fd);
1256                 close_nointr_nofail(data_fd);
1257         }
1258
1259         if (entry_fd >= 0) {
1260                 mmap_cache_close_fd(f->mmap, entry_fd);
1261                 close_nointr_nofail(entry_fd);
1262         }
1263
1264         if (entry_array_fd >= 0) {
1265                 mmap_cache_close_fd(f->mmap, entry_array_fd);
1266                 close_nointr_nofail(entry_array_fd);
1267         }
1268
1269         return r;
1270 }