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