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