From a93be359aef53b62aa90dd49640272eabce1b0a7 Mon Sep 17 00:00:00 2001 From: Yu Watanabe Date: Mon, 27 Nov 2023 11:55:49 +0900 Subject: [PATCH] sd-journal: fix corrupted journal handling of generic_array_bisect() Let's consider the following case: - the direction is down, - no cached entry, - the array has 5 entry objects, - the function test_object() reutns TEST_LEFT for the 1st object, - the 2nd, 3rd, and 4th objects are broken, so generic_array_bisect_step() returns TEST_RIGHT for the object. Then, previously, generic_array_bisect_step() updated the values like the following: 0th: (m = 5, left = 0, right = 4, i = 4) -> (m = 4, left = 0, right = 3, RIGHT) 1st: (m = 4, left = 0, right = 3, i = 1) -> (m = 4, left = 2, right = 3, LEFT) 2nd: (m = 4, left = 2, right = 3, i = 2) -> (m = 2, left = 2, right = 1, RIGHT) <- ouch!! So, assert(left < right) in generic_array_bisect() was triggered. See issue #30210. In such situation, there is no matching entry in the array. By returning TEST_GOTO_PREVIOUS, generic_array_bisect() handles the result so. Fixes a bug introduced by ab8f553d1e09088fb1f633e014299e7bf6c30c9e. Fixes #30210. --- src/libsystemd/sd-journal/journal-file.c | 41 ++++++++++++++++++++++++++++---- test/units/testsuite-04.journal.sh | 2 +- 2 files changed, 38 insertions(+), 5 deletions(-) diff --git a/src/libsystemd/sd-journal/journal-file.c b/src/libsystemd/sd-journal/journal-file.c index e402cb3..2812eb3 100644 --- a/src/libsystemd/sd-journal/journal-file.c +++ b/src/libsystemd/sd-journal/journal-file.c @@ -2913,9 +2913,19 @@ static int generic_array_bisect_step( if (IN_SET(r, -EBADMSG, -EADDRNOTAVAIL)) { log_debug_errno(r, "Encountered invalid entry while bisecting, cutting algorithm short."); - /* The first entry in the array is corrupted, let's go back to the previous array. */ - if (i == 0) + if (i == *left) { + /* This happens on two situations: + * + * a) i == 0 (hence, *left == 0): + * The first entry in the array is corrupted, let's go back to the previous array. + * + * b) *right == *left or *left + 1, and we are going to downwards: + * In that case, the (i-1)-th object has been already tested in the previous call, + * which returned TEST_LEFT. See below. So, there is no matching entry in this + * array nor in the whole entry array chain. */ + assert(i == 0 || (*right - *left <= 1 && direction == DIRECTION_DOWN)); return TEST_GOTO_PREVIOUS; + } /* Otherwise, cutting the array short. So, here we limit the number of elements we will see * in this array, and set the right boundary to the last possibly non-corrupted object. */ @@ -3022,14 +3032,14 @@ static int generic_array_bisect( } while (a > 0) { - uint64_t left, right, k, m; + uint64_t left, right, k, m, m_original; r = journal_file_move_to_object(f, OBJECT_ENTRY_ARRAY, a, &array); if (r < 0) return r; k = journal_file_entry_array_n_items(f, array); - m = MIN(k, n); + m = m_original = MIN(k, n); if (m <= 0) return 0; @@ -3080,6 +3090,27 @@ static int generic_array_bisect( for (;;) { if (left == right) { + /* We found one or more corrupted entries in generic_array_bisect_step(). + * In that case, the entry pointed by 'right' may not be tested. + * + * When we are going to downwards, the entry object pointed by 'left' + * has not been tested yet, Hence, even if left == right, we still + * have to check the final entry to see if it actually matches. + * + * On the other hand, when we are going to upwards, the entry pointed + * by 'left' is always tested, So, it is not necessary to test the + * final entry again. */ + if (m != m_original && direction == DIRECTION_DOWN) { + r = generic_array_bisect_step(f, array, left, needle, test_object, direction, &m, &left, &right); + if (r < 0) + return r; + if (IN_SET(r, TEST_GOTO_PREVIOUS, TEST_GOTO_NEXT)) + return 0; /* The entry does not pass the test, or is corrupted */ + + assert(TEST_RIGHT); + assert(left == right); + } + i = left; goto found; } @@ -3092,6 +3123,8 @@ static int generic_array_bisect( return r; if (r == TEST_GOTO_PREVIOUS) goto previous; + if (r == TEST_GOTO_NEXT) + return 0; /* Found a corrupt entry, and the array was cut short. */ } } diff --git a/test/units/testsuite-04.journal.sh b/test/units/testsuite-04.journal.sh index 6ea4cc4..3efac61 100755 --- a/test/units/testsuite-04.journal.sh +++ b/test/units/testsuite-04.journal.sh @@ -238,6 +238,6 @@ done < <(find /test-journals/no-rtc -name "*.zst") journalctl --directory="$JOURNAL_DIR" --list-boots --output=json >/tmp/lb1 diff -u /tmp/lb1 - <<'EOF' -[{"index":-3,"boot_id":"5ea5fc4f82a14186b5332a788ef9435e","first_entry":1666569600994371,"last_entry":1666584266223608},{"index":-2,"boot_id":"bea6864f21ad4c9594c04a99d89948b0","first_entry":1666569601005945,"last_entry":1666584347230411},{"index":-1,"boot_id":"4c708e1fd0744336be16f3931aa861fb","first_entry":1666584293354007,"last_entry":1666584354649355},{"index":0,"boot_id":"35e8501129134edd9df5267c49f744a4","first_entry":1666569601009823,"last_entry":1666584438086856}] +[{"index":-3,"boot_id":"5ea5fc4f82a14186b5332a788ef9435e","first_entry":1666569600994371,"last_entry":1666584266223608},{"index":-2,"boot_id":"bea6864f21ad4c9594c04a99d89948b0","first_entry":1666569601005945,"last_entry":1666584347230411},{"index":-1,"boot_id":"4c708e1fd0744336be16f3931aa861fb","first_entry":1666569601017222,"last_entry":1666584354649355},{"index":0,"boot_id":"35e8501129134edd9df5267c49f744a4","first_entry":1666569601009823,"last_entry":1666584438086856}] EOF rm -rf "$JOURNAL_DIR" /tmp/lb1 -- 2.7.4