Repository navigation
fix(storage): B+tree cursor refuses non-increasing keys; fuzz guard counts partial bindings (#597) - #599
Merged
Conversation
The nightly btree_page fuzz run pointed an internal node's rightmost child back at the node. A scan resumes each batch with a new cursor seeked past the last key it read, so the cycle handed back leaves already read: every batch returned the same keys, the depth guard was never reached, and the query never finished, growing until out of memory. LeafCursor now requires the first key of each leaf it moves to to be greater than the last key of the leaf it left and not below its start or last seek target, and refuses an empty leaf below an internal node (only an empty tree has one, as its root). Each fails with INT-049. A seek to a key at or before the end of the current leaf no longer moves the cursor. The checks run once per leaf. Tests: cursor through a cycle, a seek target past a stale leaf, an empty leaf below the root (unit); every internal node of a checkpointed file redirected to itself fails or answers within 60 s (integration). The fuzz input is added as a seed. Refs #597 Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_014v6aUco55yj3UScjL28mUP
The guard skipped inputs whose patterns join to more than 50,000 rows but counted only the rows after the last pattern. A not-join body still runs on the executor pattern by pattern in text order, so the nightly's 120-pattern body built hundreds of thousands of partial bindings before its last pattern matched nothing, and timed out after 60 s. That is the known #575 limit (streaming engine, #546 for negation), not a new bug. The guard now counts the bindings after every pattern. On the v3 corpus (4,783 inputs) coverage drops from 9,719 to 9,712 edges. The input is added as a seed. Refs #597 Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_014v6aUco55yj3UScjL28mUP
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_014v6aUco55yj3UScjL28mUP
On a damaged file the engine and the executor read different pages: for [?e ?a ?v] the executor builds whole facts and looks up each tx timestamp in the DICT, which the engine never reads. With the cycle on that DICT path the executor fails with INT-049 while the engine answers, and the oracle panics. The test still runs in the normal suite. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com> Claude-Session: https://claude.ai/code/session_014v6aUco55yj3UScjL28mUP
Codecov Report❌ Patch coverage is
📢 Thoughts on this report? Let us know! |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Two failures from the nightly fuzz run in #597.
btree_page: out-of-memory, a scan that never finishes (fixed)Input
80 10 04 01 00 05sets an internal node's rightmost child to a page on its own path.live_walkresumes every batch with a newLeafCursorseeked past the last triple, so the cycle kept handing back leaves already read. Each batch returned the same keys, the cursor's 32-level depth guard was never reached, and the query ran until out of memory.LeafCursornow enforces key order (INT-049 otherwise), once per leaf:build_btree/cow_insertnever write one).A seek to a key at or before the end of the current leaf no longer moves the cursor.
verify()already reported such trees.Tests:
storage::btree: cycle, stale leaf after a seek, empty leaf. All 3 fail without the fix.tests/integrity_test.rs: redirects each internal node of a checkpointed 3,000-fact file to itself, and each query must fail or answer within 60 s. Without the fix it times out.test-oracle. On a damaged file the engine and the executor read different pages: the executor also looks up each fact's tx timestamp in the DICT. So the executor can fail withINT-049where the engine answers, and the oracle panics on that. This is expected on corrupt data, not an engine bug.The input is added as a seed.
datalog_eval: timeout (harness)The input is a
not-joinwith a 120-pattern body. Negation bodies still run on the executor pattern by pattern in text order. The body builds hundreds of thousands of partial bindings before its last pattern (:__magic…) matches nothing, so it takes 65 s on currentv3. This is the known #575 limit (streaming engine; #546 for negation), not a new bug. The guard counted only rows after the last pattern, which here is 0. It now counts the bindings after every pattern. Corpus coverage goes from 9,719 to 9,712 edges over 4,783 inputs. The input is added as a seed and now runs in about 140 ms.mainhas the same guard; the harness change goes there as a separate PR. The cursor fix applies to v8 only, so there's nomainbackport.Checks
cargo test: 1507 tests (1497 passing, 10 ignored)cargo test --features test-oracle --no-fail-fast: 1496 passing, 11 ignoredcargo clippy --all-features -- -D warnings: cleanRefs #597
🤖 Generated with Claude Code
https://claude.ai/code/session_014v6aUco55yj3UScjL28mUP