1 /*-*- Mode: C; c-basic-offset: 8; indent-tabs-mode: nil -*-*/
4 This file is part of systemd.
6 Copyright 2012 Lennart Poettering
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.
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.
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/>.
28 #include "journal-def.h"
29 #include "journal-file.h"
30 #include "journal-authenticate.h"
31 #include "journal-verify.h"
38 * - write bit mucking test
39 * - evolve key even if nothing happened in regular intervals
41 * - Allow building without libgcrypt
47 static int journal_file_object_verify(JournalFile *f, Object *o) {
53 /* This does various superficial tests about the length an
54 * possible field values. It does not follow any references to
57 if ((o->object.flags & OBJECT_COMPRESSED) &&
58 o->object.type != OBJECT_DATA)
61 switch (o->object.type) {
66 if (le64toh(o->data.entry_offset) <= 0 ||
67 le64toh(o->data.n_entries) <= 0)
70 if (le64toh(o->object.size) - offsetof(DataObject, payload) <= 0)
73 h1 = le64toh(o->data.hash);
75 if (o->object.flags & OBJECT_COMPRESSED) {
77 uint64_t alloc = 0, b_size;
79 if (!uncompress_blob(o->data.payload,
80 le64toh(o->object.size) - offsetof(Object, data.payload),
84 h2 = hash64(b, b_size);
87 h2 = hash64(o->data.payload, le64toh(o->object.size) - offsetof(Object, data.payload));
92 if (!VALID64(o->data.next_hash_offset) ||
93 !VALID64(o->data.next_field_offset) ||
94 !VALID64(o->data.entry_offset) ||
95 !VALID64(o->data.entry_array_offset))
102 if (le64toh(o->object.size) - offsetof(FieldObject, payload) <= 0)
105 if (!VALID64(o->field.next_hash_offset) ||
106 !VALID64(o->field.head_data_offset))
111 if ((le64toh(o->object.size) - offsetof(EntryObject, items)) % sizeof(EntryItem) != 0)
114 if ((le64toh(o->object.size) - offsetof(EntryObject, items)) / sizeof(EntryItem) <= 0)
117 if (le64toh(o->entry.seqnum) <= 0 ||
118 le64toh(o->entry.realtime) <= 0)
121 for (i = 0; i < journal_file_entry_n_items(o); i++) {
122 if (o->entry.items[i].object_offset == 0 ||
123 !VALID64(o->entry.items[i].object_offset))
129 case OBJECT_DATA_HASH_TABLE:
130 case OBJECT_FIELD_HASH_TABLE:
131 if ((le64toh(o->object.size) - offsetof(HashTableObject, items)) % sizeof(HashItem) != 0)
134 if ((le64toh(o->object.size) - offsetof(HashTableObject, items)) / sizeof(HashItem) <= 0)
139 case OBJECT_ENTRY_ARRAY:
140 if ((le64toh(o->object.size) - offsetof(EntryArrayObject, items)) % sizeof(le64_t) != 0)
143 if ((le64toh(o->object.size) - offsetof(EntryArrayObject, items)) / sizeof(le64_t) <= 0)
146 if (!VALID64(o->entry_array.next_entry_array_offset))
152 if (le64toh(o->object.size) != sizeof(TagObject))
160 static void draw_progress(uint64_t p, usec_t *last_usec) {
164 if (!isatty(STDOUT_FILENO))
167 z = now(CLOCK_MONOTONIC);
170 if (x != 0 && x + 40 * USEC_PER_MSEC > z)
175 n = (3 * columns()) / 4;
176 j = (n * (unsigned) p) / 65535ULL;
179 fputs("\r\x1B[?25l" ANSI_HIGHLIGHT_GREEN_ON, stdout);
181 for (i = 0; i < j; i++)
182 fputs("\xe2\x96\x88", stdout);
184 fputs(ANSI_HIGHLIGHT_OFF, stdout);
186 for (i = 0; i < k; i++)
187 fputs("\xe2\x96\x91", stdout);
189 printf(" %3lu%%", 100LU * (unsigned long) p / 65535LU);
191 fputs("\r\x1B[?25h", stdout);
195 static void flush_progress(void) {
198 if (!isatty(STDOUT_FILENO))
201 n = (3 * columns()) / 4;
205 for (i = 0; i < n + 5; i++)
212 static int write_uint64(int fd, uint64_t p) {
215 k = write(fd, &p, sizeof(p));
224 static int contains_uint64(MMapCache *m, int fd, uint64_t n, uint64_t p) {
239 r = mmap_cache_get(m, fd, PROT_READ|PROT_WRITE, 0, c * sizeof(uint64_t), sizeof(uint64_t), (void **) &z);
255 static int entry_points_to_data(
268 assert(entry_fd >= 0);
270 if (!contains_uint64(f->mmap, entry_fd, n_entries, entry_p)) {
271 log_error("Data object references invalid entry at %llu", (unsigned long long) data_p);
275 r = journal_file_move_to_object(f, OBJECT_ENTRY, entry_p, &o);
279 n = journal_file_entry_n_items(o);
280 for (i = 0; i < n; i++)
281 if (le64toh(o->entry.items[i].object_offset) == data_p) {
287 log_error("Data object not referenced by linked entry at %llu", (unsigned long long) data_p);
291 /* Check if this entry is also in main entry array. Since the
292 * main entry array has already been verified we can rely on
295 n = le64toh(f->header->n_entries);
296 a = le64toh(f->header->entry_array_offset);
302 r = journal_file_move_to_object(f, OBJECT_ENTRY_ARRAY, a, &o);
306 m = journal_file_entry_array_n_items(o);
307 for (j = 0; i < n && j < m; i++, j++)
308 if (le64toh(o->entry_array.items[j]) == entry_p)
311 a = le64toh(o->entry_array.next_entry_array_offset);
317 static int verify_data(
319 Object *o, uint64_t p,
320 int entry_fd, uint64_t n_entries,
321 int entry_array_fd, uint64_t n_entry_arrays) {
323 uint64_t i, n, a, last, q;
328 assert(entry_fd >= 0);
329 assert(entry_array_fd >= 0);
331 n = le64toh(o->data.n_entries);
332 a = le64toh(o->data.entry_array_offset);
334 /* We already checked this earlier */
337 last = q = le64toh(o->data.entry_offset);
338 r = entry_points_to_data(f, entry_fd, n_entries, q, p);
347 log_error("Array chain too short at %llu", (unsigned long long) p);
351 if (!contains_uint64(f->mmap, entry_array_fd, n_entry_arrays, a)) {
352 log_error("Invalid array at %llu", (unsigned long long) p);
356 r = journal_file_move_to_object(f, OBJECT_ENTRY_ARRAY, a, &o);
360 next = le64toh(o->entry_array.next_entry_array_offset);
361 if (next != 0 && next <= a) {
362 log_error("Array chain has cycle at %llu", (unsigned long long) p);
366 m = journal_file_entry_array_n_items(o);
367 for (j = 0; i < n && j < m; i++, j++) {
369 q = le64toh(o->entry_array.items[j]);
371 log_error("Data object's entry array not sorted at %llu", (unsigned long long) p);
376 r = entry_points_to_data(f, entry_fd, n_entries, q, p);
380 /* Pointer might have moved, reposition */
381 r = journal_file_move_to_object(f, OBJECT_ENTRY_ARRAY, a, &o);
392 static int verify_hash_table(
394 int data_fd, uint64_t n_data,
395 int entry_fd, uint64_t n_entries,
396 int entry_array_fd, uint64_t n_entry_arrays,
403 assert(data_fd >= 0);
404 assert(entry_fd >= 0);
405 assert(entry_array_fd >= 0);
408 n = le64toh(f->header->data_hash_table_size) / sizeof(HashItem);
409 for (i = 0; i < n; i++) {
410 uint64_t last = 0, p;
412 draw_progress(0xC000 + (0x3FFF * i / n), last_usec);
414 p = le64toh(f->data_hash_table[i].head_hash_offset);
419 if (!contains_uint64(f->mmap, data_fd, n_data, p)) {
420 log_error("Invalid data object at hash entry %llu of %llu",
421 (unsigned long long) i, (unsigned long long) n);
425 r = journal_file_move_to_object(f, OBJECT_DATA, p, &o);
429 next = le64toh(o->data.next_hash_offset);
430 if (next != 0 && next <= p) {
431 log_error("Hash chain has a cycle in hash entry %llu of %llu",
432 (unsigned long long) i, (unsigned long long) n);
436 if (le64toh(o->data.hash) % n != i) {
437 log_error("Hash value mismatch in hash entry %llu of %llu",
438 (unsigned long long) i, (unsigned long long) n);
442 r = verify_data(f, o, p, entry_fd, n_entries, entry_array_fd, n_entry_arrays);
450 if (last != le64toh(f->data_hash_table[i].tail_hash_offset)) {
451 log_error("Tail hash pointer mismatch in hash table");
459 static int data_object_in_hash_table(JournalFile *f, uint64_t hash, uint64_t p) {
464 n = le64toh(f->header->data_hash_table_size) / sizeof(HashItem);
467 q = le64toh(f->data_hash_table[h].head_hash_offset);
474 r = journal_file_move_to_object(f, OBJECT_DATA, q, &o);
478 q = le64toh(o->data.next_hash_offset);
484 static int verify_entry(
486 Object *o, uint64_t p,
487 int data_fd, uint64_t n_data) {
494 assert(data_fd >= 0);
496 n = journal_file_entry_n_items(o);
497 for (i = 0; i < n; i++) {
501 q = le64toh(o->entry.items[i].object_offset);
502 h = le64toh(o->entry.items[i].hash);
504 if (!contains_uint64(f->mmap, data_fd, n_data, q)) {
505 log_error("Invalid data object at entry %llu",
506 (unsigned long long) p);
510 r = journal_file_move_to_object(f, OBJECT_DATA, q, &u);
514 if (le64toh(u->data.hash) != h) {
515 log_error("Hash mismatch for data object at entry %llu",
516 (unsigned long long) p);
520 r = data_object_in_hash_table(f, h, q);
524 log_error("Data object missing from hash at entry %llu",
525 (unsigned long long) p);
533 static int verify_entry_array(
535 int data_fd, uint64_t n_data,
536 int entry_fd, uint64_t n_entries,
537 int entry_array_fd, uint64_t n_entry_arrays,
540 uint64_t i = 0, a, n, last = 0;
544 assert(data_fd >= 0);
545 assert(entry_fd >= 0);
546 assert(entry_array_fd >= 0);
549 n = le64toh(f->header->n_entries);
550 a = le64toh(f->header->entry_array_offset);
555 draw_progress(0x8000 + (0x3FFF * i / n), last_usec);
558 log_error("Array chain too short at %llu of %llu",
559 (unsigned long long) i, (unsigned long long) n);
563 if (!contains_uint64(f->mmap, entry_array_fd, n_entry_arrays, a)) {
564 log_error("Invalid array at %llu of %llu",
565 (unsigned long long) i, (unsigned long long) n);
569 r = journal_file_move_to_object(f, OBJECT_ENTRY_ARRAY, a, &o);
573 next = le64toh(o->entry_array.next_entry_array_offset);
574 if (next != 0 && next <= a) {
575 log_error("Array chain has cycle at %llu of %llu",
576 (unsigned long long) i, (unsigned long long) n);
580 m = journal_file_entry_array_n_items(o);
581 for (j = 0; i < n && j < m; i++, j++) {
584 p = le64toh(o->entry_array.items[j]);
586 log_error("Entry array not sorted at %llu of %llu",
587 (unsigned long long) i, (unsigned long long) n);
592 if (!contains_uint64(f->mmap, entry_fd, n_entries, p)) {
593 log_error("Invalid array entry at %llu of %llu",
594 (unsigned long long) i, (unsigned long long) n);
598 r = journal_file_move_to_object(f, OBJECT_ENTRY, p, &o);
602 r = verify_entry(f, o, p, data_fd, n_data);
606 /* Pointer might have moved, reposition */
607 r = journal_file_move_to_object(f, OBJECT_ENTRY_ARRAY, a, &o);
618 static int journal_file_parse_verification_key(JournalFile *f, const char *key) {
623 unsigned long long start, interval;
625 seed_size = FSPRG_RECOMMENDED_SEEDLEN;
626 seed = malloc(seed_size);
631 for (c = 0; c < seed_size; c++) {
650 seed[c] = (uint8_t) (x * 16 + y);
659 r = sscanf(k, "%llx-%llx", &start, &interval);
665 f->fsprg_seed = seed;
666 f->fsprg_seed_size = seed_size;
668 f->fss_start_usec = start * interval;
669 f->fss_interval_usec = interval;
674 int journal_file_verify(
677 usec_t *first_validated, usec_t *last_validated, usec_t *last_contained) {
680 uint64_t p = 0, last_tag = 0, last_epoch = 0, last_tag_realtime = 0;
681 uint64_t entry_seqnum = 0, entry_monotonic = 0, entry_realtime = 0;
682 sd_id128_t entry_boot_id;
683 bool entry_seqnum_set = false, entry_monotonic_set = false, entry_realtime_set = false, found_main_entry_array = false;
684 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;
685 usec_t last_usec = 0;
686 int data_fd = -1, entry_fd = -1, entry_array_fd = -1;
687 char data_path[] = "/var/tmp/journal-data-XXXXXX",
688 entry_path[] = "/var/tmp/journal-entry-XXXXXX",
689 entry_array_path[] = "/var/tmp/journal-entry-array-XXXXXX";
694 r = journal_file_parse_verification_key(f, key);
696 log_error("Failed to parse seed.");
701 data_fd = mkostemp(data_path, O_CLOEXEC);
703 log_error("Failed to create data file: %m");
709 entry_fd = mkostemp(entry_path, O_CLOEXEC);
711 log_error("Failed to create entry file: %m");
717 entry_array_fd = mkostemp(entry_array_path, O_CLOEXEC);
718 if (entry_array_fd < 0) {
719 log_error("Failed to create entry array file: %m");
723 unlink(entry_array_path);
725 /* First iteration: we go through all objects, verify the
726 * superficial structure, headers, hashes. */
728 p = le64toh(f->header->header_size);
730 draw_progress(0x7FFF * p / le64toh(f->header->tail_object_offset), &last_usec);
732 r = journal_file_move_to_object(f, -1, p, &o);
734 log_error("Invalid object at %llu", (unsigned long long) p);
738 if (le64toh(f->header->tail_object_offset) < p) {
739 log_error("Invalid tail object pointer");
746 r = journal_file_object_verify(f, o);
748 log_error("Invalid object contents at %llu", (unsigned long long) p);
752 if (o->object.flags & OBJECT_COMPRESSED &&
753 !(le32toh(f->header->incompatible_flags) & HEADER_INCOMPATIBLE_COMPRESSED)) {
754 log_error("Compressed object in file without compression at %llu", (unsigned long long) p);
759 switch (o->object.type) {
762 r = write_uint64(data_fd, p);
774 if ((le32toh(f->header->compatible_flags) & HEADER_COMPATIBLE_SEALED) && n_tags <= 0) {
775 log_error("First entry before first tag at %llu", (unsigned long long) p);
780 r = write_uint64(entry_fd, p);
784 if (last_tag_realtime > le64toh(o->entry.realtime)) {
785 log_error("Older entry after newer tag at %llu", (unsigned long long) p);
790 if (!entry_seqnum_set &&
791 le64toh(o->entry.seqnum) != le64toh(f->header->head_entry_seqnum)) {
792 log_error("Head entry sequence number incorrect at %llu", (unsigned long long) p);
797 if (entry_seqnum_set &&
798 entry_seqnum >= le64toh(o->entry.seqnum)) {
799 log_error("Entry sequence number out of synchronization at %llu", (unsigned long long) p);
804 entry_seqnum = le64toh(o->entry.seqnum);
805 entry_seqnum_set = true;
807 if (entry_monotonic_set &&
808 sd_id128_equal(entry_boot_id, o->entry.boot_id) &&
809 entry_monotonic > le64toh(o->entry.monotonic)) {
810 log_error("Entry timestamp out of synchronization at %llu", (unsigned long long) p);
815 entry_monotonic = le64toh(o->entry.monotonic);
816 entry_boot_id = o->entry.boot_id;
817 entry_monotonic_set = true;
819 if (!entry_realtime_set &&
820 le64toh(o->entry.realtime) != le64toh(f->header->head_entry_realtime)) {
821 log_error("Head entry realtime timestamp incorrect");
826 entry_realtime = le64toh(o->entry.realtime);
827 entry_realtime_set = true;
832 case OBJECT_DATA_HASH_TABLE:
833 if (n_data_hash_tables > 1) {
834 log_error("More than one data hash table at %llu", (unsigned long long) p);
839 if (le64toh(f->header->data_hash_table_offset) != p + offsetof(HashTableObject, items) ||
840 le64toh(f->header->data_hash_table_size) != le64toh(o->object.size) - offsetof(HashTableObject, items)) {
841 log_error("Header fields for data hash table invalid");
846 n_data_hash_tables++;
849 case OBJECT_FIELD_HASH_TABLE:
850 if (n_field_hash_tables > 1) {
851 log_error("More than one field hash table at %llu", (unsigned long long) p);
856 if (le64toh(f->header->field_hash_table_offset) != p + offsetof(HashTableObject, items) ||
857 le64toh(f->header->field_hash_table_size) != le64toh(o->object.size) - offsetof(HashTableObject, items)) {
858 log_error("Header fields for field hash table invalid");
863 n_field_hash_tables++;
866 case OBJECT_ENTRY_ARRAY:
867 r = write_uint64(entry_array_fd, p);
871 if (p == le64toh(f->header->entry_array_offset)) {
872 if (found_main_entry_array) {
873 log_error("More than one main entry array at %llu", (unsigned long long) p);
878 found_main_entry_array = true;
887 if (!(le32toh(f->header->compatible_flags) & HEADER_COMPATIBLE_SEALED)) {
888 log_error("Tag object in file without sealing at %llu", (unsigned long long) p);
893 log_debug("Checking tag %llu..", (unsigned long long) le64toh(o->tag.seqnum));
895 if (le64toh(o->tag.seqnum) != n_tags + 1) {
896 log_error("Tag sequence number out of synchronization at %llu", (unsigned long long) p);
901 if (le64toh(o->tag.epoch) < last_epoch) {
902 log_error("Epoch sequence out of synchronization at %llu", (unsigned long long) p);
907 rt = (o->tag.epoch + 1) * f->fss_interval_usec + f->fss_start_usec;
908 if (entry_realtime_set && entry_realtime >= rt) {
909 log_error("Tag/entry realtime timestamp out of synchronization at %llu", (unsigned long long) p);
914 /* OK, now we know the epoch. So let's now set
915 * it, and calculate the HMAC for everything
916 * since the last tag. */
917 r = journal_file_fsprg_seek(f, le64toh(o->tag.epoch));
921 r = journal_file_hmac_start(f);
926 r = journal_file_hmac_put_header(f);
930 q = le64toh(f->header->header_size);
935 r = journal_file_move_to_object(f, -1, q, &o);
939 r = journal_file_hmac_put_object(f, -1, q);
943 q = q + ALIGN64(le64toh(o->object.size));
946 /* Position might have changed, let's reposition things */
947 r = journal_file_move_to_object(f, -1, p, &o);
951 if (memcmp(o->tag.tag, gcry_md_read(f->hmac, 0), TAG_LENGTH) != 0) {
952 log_error("Tag failed verification at %llu", (unsigned long long) p);
957 f->hmac_running = false;
959 last_tag = p + ALIGN64(le64toh(o->object.size));
960 last_tag_realtime = rt;
970 if (p == le64toh(f->header->tail_object_offset))
973 p = p + ALIGN64(le64toh(o->object.size));
976 if (n_objects != le64toh(f->header->n_objects)) {
977 log_error("Object number mismatch");
982 if (n_entries != le64toh(f->header->n_entries)) {
983 log_error("Entry number mismatch");
988 if (JOURNAL_HEADER_CONTAINS(f->header, n_data) &&
989 n_data != le64toh(f->header->n_data)) {
990 log_error("Data number mismatch");
995 if (JOURNAL_HEADER_CONTAINS(f->header, n_fields) &&
996 n_fields != le64toh(f->header->n_fields)) {
997 log_error("Field number mismatch");
1002 if (JOURNAL_HEADER_CONTAINS(f->header, n_tags) &&
1003 n_tags != le64toh(f->header->n_tags)) {
1004 log_error("Tag number mismatch");
1009 if (JOURNAL_HEADER_CONTAINS(f->header, n_entry_arrays) &&
1010 n_entry_arrays != le64toh(f->header->n_entry_arrays)) {
1011 log_error("Entry array number mismatch");
1016 if (n_data_hash_tables != 1) {
1017 log_error("Missing data hash table");
1022 if (n_field_hash_tables != 1) {
1023 log_error("Missing field hash table");
1028 if (!found_main_entry_array) {
1029 log_error("Missing entry array");
1034 if (entry_seqnum_set &&
1035 entry_seqnum != le64toh(f->header->tail_entry_seqnum)) {
1036 log_error("Invalid tail seqnum");
1041 if (entry_monotonic_set &&
1042 (!sd_id128_equal(entry_boot_id, f->header->boot_id) ||
1043 entry_monotonic != le64toh(f->header->tail_entry_monotonic))) {
1044 log_error("Invalid tail monotonic timestamp");
1049 if (entry_realtime_set && entry_realtime != le64toh(f->header->tail_entry_realtime)) {
1050 log_error("Invalid tail realtime timestamp");
1055 /* Second iteration: we follow all objects referenced from the
1056 * two entry points: the object hash table and the entry
1057 * array. We also check that everything referenced (directly
1058 * or indirectly) in the data hash table also exists in the
1059 * entry array, and vice versa. Note that we do not care for
1060 * unreferenced objects. We only care that everything that is
1061 * referenced is consistent. */
1063 r = verify_entry_array(f,
1065 entry_fd, n_entries,
1066 entry_array_fd, n_entry_arrays,
1071 r = verify_hash_table(f,
1073 entry_fd, n_entries,
1074 entry_array_fd, n_entry_arrays,
1081 mmap_cache_close_fd(f->mmap, data_fd);
1082 mmap_cache_close_fd(f->mmap, entry_fd);
1083 mmap_cache_close_fd(f->mmap, entry_array_fd);
1085 close_nointr_nofail(data_fd);
1086 close_nointr_nofail(entry_fd);
1087 close_nointr_nofail(entry_array_fd);
1089 if (first_validated)
1090 *first_validated = le64toh(f->header->head_entry_realtime);
1092 *last_validated = last_tag_realtime;
1094 *last_contained = le64toh(f->header->tail_entry_realtime);
1101 log_error("File corruption detected at %s:%llu (of %llu, %llu%%).",
1103 (unsigned long long) p,
1104 (unsigned long long) f->last_stat.st_size,
1105 (unsigned long long) (100 * p / f->last_stat.st_size));
1108 mmap_cache_close_fd(f->mmap, data_fd);
1109 close_nointr_nofail(data_fd);
1112 if (entry_fd >= 0) {
1113 mmap_cache_close_fd(f->mmap, entry_fd);
1114 close_nointr_nofail(entry_fd);
1117 if (entry_array_fd >= 0) {
1118 mmap_cache_close_fd(f->mmap, entry_array_fd);
1119 close_nointr_nofail(entry_array_fd);