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