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