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