From ffb88bc3cd441a48be519566430a944f481bef82 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 23 Oct 2026 09:47:45 +0530 Subject: [PATCH 1/3] =?UTF-8?q?fix(wal):=20replay=20WAL=20entries=20of=20m?= =?UTF-8?q?ore=20than=201,000,000=20facts=20(#686)=20=E2=80=94=20backport?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Replay took an entry of more than 1,000,000 facts as damage, and the writer's tail cut at open removed it and every later entry, so a transact, retract or WriteTransaction commit of that size, and every later one, was lost after a crash or close without a checkpoint. A fact count is now damage only when the bytes after it cannot hold that many facts (each has at least its 4-byte length), checked before the count is converted to usize. Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_0169pNQsLcCEn48te9X9WuZW --- CHANGELOG.md | 1 + CLAUDE.md | 2 +- docs/TEST_COVERAGE.md | 5 ++-- src/wal.rs | 65 ++++++++++++++++++++++++++++++++++--------- 4 files changed, 57 insertions(+), 16 deletions(-) diff --git a/CHANGELOG.md b/CHANGELOG.md index 204f20b56d..cad5396fd5 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -9,6 +9,7 @@ and this project adheres to [Semantic Versioning](https://semver.org/spec/v2.0.0 ### Fixed +- **WAL entries of more than 1,000,000 facts replay** (#686), backported from v3.0.0. A `transact`, `retract` or `WriteTransaction` commit of more than 1,000,000 facts wrote a WAL entry that replay took as damage: replay stopped there, and the next open cut the WAL off at that entry, so after a crash, kill or close without a checkpoint that transaction and every later one in the WAL were lost, though each had reported success. Replay now takes an entry's fact count as damage only when the bytes after it cannot hold that many facts. A checkpoint before the crash kept the facts. Present since v0.5.0. - **Prepared queries use the database's rule limits** (#679), backported from v3.0.0. `PreparedQuery::execute` ran a rule query with the default `max_derived_facts` and `max_results` of 1,000,000 whatever `OpenOptions` set, so a lower limit set to stop a runaway recursive rule did not apply to prepared queries, and a higher one set for a large derivation failed with `INT-020` where `execute` of the same query succeeded. It now uses the database's limits, as `execute` does. `:max-derived-facts` and `:max-results` written in the query text were always applied. Present since v0.19.0. ### Tests diff --git a/CLAUDE.md b/CLAUDE.md index f7b7eae21b..4366ca40a0 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -179,7 +179,7 @@ Auto-migrates v1/v2/v3/v4/v5/v6 → v7 on open/checkpoint. ## Test Coverage -**1321 tests** (1312 passing, 9 ignored; unit + integration + doc). +**1322 tests** (1313 passing, 9 ignored; unit + integration + doc). See `docs/TEST_COVERAGE.md` for the full per-file breakdown. **Testing conventions** — see the Testing Conventions section below before writing any tests. diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index 92aadb690f..4140304e55 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -2,9 +2,9 @@ ## v2.0.9 Coverage Summary -**Verified**: 2026-10-21 with `cargo test` +**Verified**: 2026-10-23 with `cargo test` -**Result**: 1,309 passing tests and 9 ignored tests (1,318 total), including the golden-file corpus (#391) +**Result**: 1,313 passing tests and 9 ignored tests (1,322 total), including the golden-file corpus (#391) For v2.0.5, `tests/edge_cases_test.rs` checks that a file of 1 to 4,095 bytes is `STG-045`, unchanged and with no WAL, when it is a database cut below one page or foreign bytes, and opens as a new database that takes a write and reads it back after reopen when it is a prefix of the initial header or all zeros (#506). Rule-body tests in `tests/recursive_rules_test.rs` check that a `:db/valid-at` pattern in a rule definition, in its `not` and `not-join` bodies and in its `or` branches binds the query's valid time, on the semi-naive, stratified and magic-sets paths (#617). @@ -35,6 +35,7 @@ The v2.0.9 suite covers the public database API, the Datalog engine, storage and - **Core database behavior**: in-memory and file-backed operation, transactions, checkpoints, retractions, bi-temporal queries, recursive rules, prepared statements, aggregation, expressions, disjunction, window functions, UDFs, and magic-sets evaluation. - **Storage correctness**: packed pages, B+tree indexes and range scans, cache behavior, file-header validation, migration, WAL replay, checksums, corruption handling, and fault injection. - **Reliability and concurrency**: concurrent reads and writes, rollback behavior, same-process handle exclusion, cross-process locking, PID namespaces, NFS and container lock behavior, and SIGKILL recovery, and queries seeing each concurrent transaction whole and reading one state for all their patterns, also during a checkpoint (`tests/snapshot_atomicity_test.rs`, #554, #555, #558). +- **WAL entries of any size** (`src/wal.rs`, 2 tests, 1 replacing the 1,000,000-fact cap test; #686): an entry of 1,000,001 facts and the entries after it replay, and reopening the writer cuts none of them off; a fact count the bytes after it cannot hold (one more than a quarter of them, or `u64::MAX`) ends replay at that entry, and reopening the writer cuts the WAL off there. - **Kani proofs of the value encoding** (#627; not `#[test]`s, run by `cargo kani` and `.github/workflows/kani.yml`): 5 harnesses in `src/storage/index/verification.rs` prove, for every input, that `encode_value` (the `value_bytes` of the v7 indexes) writes `Null` as `[0x00]` and each of `Boolean`, `Integer`, `Float` and `Ref` with its own type byte and in its own order (non-NaN floats by IEEE total order, so `-0.0` before `0.0`), and every NaN to the same bytes. Each harness fails when its encoder is broken on purpose. Where NaN sorts is not asserted (#688). Strings, keywords, decoders, fact pages and the WAL are left out: the model checker does not finish on them, so the fuzz and property tests cover them. v3.0.0 adds proofs of its key encoders. - **Public diagnostics**: structured parser, query, storage, WAL, API, and internal error codes; the error-code registry is checked against [`ERROR_REFERENCE.md`](ERROR_REFERENCE.md). - **Compatibility and quality**: golden-file corpus of released file formats, cross-platform format compatibility, property-based tests, long-haul smoke coverage, a weekly soak at 10M facts with a 5-hour churn (#392), XTDB/Datomic semantic compatibility, grammar conformance, and rustdoc examples. diff --git a/src/wal.rs b/src/wal.rs index 3e07812d3f..3e9e20d2b5 100644 --- a/src/wal.rs +++ b/src/wal.rs @@ -330,6 +330,7 @@ impl WalReader { /// or corrupt one or at EOF. Also returns the offset where the valid entries /// end: the end of the header if there are none. fn scan_entries(file: &mut File) -> Result<(Vec, u64)> { + let file_len = file.metadata()?.len(); file.seek(SeekFrom::Start(WAL_HEADER_SIZE as u64))?; let mut entries = Vec::new(); let mut valid_end = WAL_HEADER_SIZE as u64; @@ -356,14 +357,14 @@ fn scan_entries(file: &mut File) -> Result<(Vec, u64)> { if file.read_exact(&mut num_facts_buf).is_err() { break; // truncated } - let num_facts = usize::try_from(u64::from_le_bytes(num_facts_buf)) - .map_err(|_| err_coded!(ErrorCode::Wal005))?; - - // Sanity cap: no legitimate entry has more than 1M facts - const MAX_FACTS_PER_ENTRY: usize = 1_000_000; - if num_facts > MAX_FACTS_PER_ENTRY { + // Every fact takes at least its 4-byte length, so a count the bytes + // left cannot hold is damage. Entries have no count limit (#686). + let num_facts = u64::from_le_bytes(num_facts_buf); + let left = file_len.saturating_sub(file.stream_position()?); + if num_facts > left / 4 { break; // treat as corrupt entry } + let num_facts = usize::try_from(num_facts).map_err(|_| err_coded!(ErrorCode::Wal005))?; // Maximum fact size to prevent memory exhaustion from large facts const MAX_FACT_SIZE: usize = 10 * 1024 * 1024; // 10MB @@ -857,24 +858,62 @@ mod tests { assert!(reader.read_entries().unwrap().is_empty()); } + /// A `num_facts` too large for the bytes after it (each fact has at least + /// its 4-byte length) is damage: replay ends at that entry. #[test] - fn test_wal_entry_with_too_many_facts_ends_replay() { + fn test_wal_entry_with_more_facts_than_bytes_left_ends_replay() { let dir = tempfile::tempdir().unwrap(); let path = dir.path().join("test.wal"); - wal_with_entries(&path, 2); + let bytes = wal_with_entries(&path, 2); let one_len = { let p = dir.path().join("one.wal"); wal_with_entries(&p, 1).len() }; // Entry 2's num_facts, after its checksum and tx_count. - let mut file = std::fs::OpenOptions::new().write(true).open(&path).unwrap(); - file.seek(std::io::SeekFrom::Start(one_len as u64 + 12)) - .unwrap(); - file.write_all(&1_000_001u64.to_le_bytes()).unwrap(); - drop(file); + let count_at = one_len as u64 + 12; + let left = bytes.len() as u64 - (count_at + 8); + for num_facts in [left / 4 + 1, u64::MAX] { + let mut file = std::fs::OpenOptions::new().write(true).open(&path).unwrap(); + file.seek(std::io::SeekFrom::Start(count_at)).unwrap(); + file.write_all(&num_facts.to_le_bytes()).unwrap(); + drop(file); + assert_eq!(tx_counts(&path), [1]); + } + + // Reopening the writer cuts the WAL off at that entry. + drop(WalWriter::open_or_create(&path, SyncMode::Full).unwrap()); + assert_eq!(std::fs::metadata(&path).unwrap().len(), one_len as u64); assert_eq!(tx_counts(&path), [1]); } + /// An entry of more than 1,000,000 facts replays, and so do the entries + /// after it; the writer's tail cut at open keeps them (#686). + #[test] + fn test_wal_entry_of_more_than_a_million_facts_replays() { + const N: usize = 1_000_001; + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("test.wal"); + let mut writer = WalWriter::open_or_create(&path, SyncMode::Full).unwrap(); + let fact = make_fact(Uuid::new_v4(), ":n", Value::Integer(1), 1); + writer.append_entry(1, &vec![fact; N]).unwrap(); + let fact = make_fact(Uuid::new_v4(), ":n", Value::Integer(2), 2); + writer.append_entry(2, &[fact]).unwrap(); + drop(writer); + let len = std::fs::metadata(&path).unwrap().len(); + + // Reopening cuts off nothing, and an append lands after both. + let mut writer = WalWriter::open_or_create(&path, SyncMode::Full).unwrap(); + assert_eq!(std::fs::metadata(&path).unwrap().len(), len); + let fact = make_fact(Uuid::new_v4(), ":n", Value::Integer(3), 3); + writer.append_entry(3, &[fact]).unwrap(); + drop(writer); + + let entries = WalReader::open(&path).unwrap().read_entries().unwrap(); + let counts: Vec = entries.iter().map(|e| e.tx_count).collect(); + assert_eq!(counts, [1, 2, 3]); + assert_eq!(entries[0].facts.len(), N); + } + #[test] fn test_wal_writer_open_fails_in_a_missing_directory() { let dir = tempfile::tempdir().unwrap(); From a2d617c4b9cf72e29c90e135cbe2f22d25782ab0 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 23 Oct 2026 10:15:02 +0530 Subject: [PATCH 2/3] fix(wal): bound the entry count without new error branches (#686) Take the entry's offset from valid_end rather than stream_position, and fall back to no bound when the file length is unavailable (a corrupt count still ends at EOF), so the coverage gate's branch floor holds. Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_0169pNQsLcCEn48te9X9WuZW --- src/wal.rs | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-) diff --git a/src/wal.rs b/src/wal.rs index 3e9e20d2b5..d09cbdefd1 100644 --- a/src/wal.rs +++ b/src/wal.rs @@ -330,7 +330,8 @@ impl WalReader { /// or corrupt one or at EOF. Also returns the offset where the valid entries /// end: the end of the header if there are none. fn scan_entries(file: &mut File) -> Result<(Vec, u64)> { - let file_len = file.metadata()?.len(); + // Without the length, a corrupt count still ends at EOF, only later. + let file_len = file.metadata().map_or(u64::MAX, |m| m.len()); file.seek(SeekFrom::Start(WAL_HEADER_SIZE as u64))?; let mut entries = Vec::new(); let mut valid_end = WAL_HEADER_SIZE as u64; @@ -360,7 +361,8 @@ fn scan_entries(file: &mut File) -> Result<(Vec, u64)> { // Every fact takes at least its 4-byte length, so a count the bytes // left cannot hold is damage. Entries have no count limit (#686). let num_facts = u64::from_le_bytes(num_facts_buf); - let left = file_len.saturating_sub(file.stream_position()?); + // The entry starts at `valid_end`; its facts after 20 header bytes. + let left = file_len.saturating_sub(valid_end.saturating_add(20)); if num_facts > left / 4 { break; // treat as corrupt entry } From a72b2d9eb008a8fd20509d8b885f237401dc6b78 Mon Sep 17 00:00:00 2001 From: Aditya Mukhopadhyay Date: Fri, 23 Oct 2026 10:25:16 +0530 Subject: [PATCH 3/3] test(wal): entries whose facts are cut short end replay (#686) The byte bound now stops the truncated-entry tests before the fact loop; cover the loop's two truncation exits directly. Co-Authored-By: Claude Opus 5.5 Claude-Session: https://claude.ai/code/session_0169pNQsLcCEn48te9X9WuZW --- CLAUDE.md | 2 +- docs/TEST_COVERAGE.md | 4 ++-- src/wal.rs | 24 ++++++++++++++++++++++++ 3 files changed, 27 insertions(+), 3 deletions(-) diff --git a/CLAUDE.md b/CLAUDE.md index 4366ca40a0..e63be2df29 100644 --- a/CLAUDE.md +++ b/CLAUDE.md @@ -179,7 +179,7 @@ Auto-migrates v1/v2/v3/v4/v5/v6 → v7 on open/checkpoint. ## Test Coverage -**1322 tests** (1313 passing, 9 ignored; unit + integration + doc). +**1323 tests** (1314 passing, 9 ignored; unit + integration + doc). See `docs/TEST_COVERAGE.md` for the full per-file breakdown. **Testing conventions** — see the Testing Conventions section below before writing any tests. diff --git a/docs/TEST_COVERAGE.md b/docs/TEST_COVERAGE.md index 4140304e55..92da77bfab 100644 --- a/docs/TEST_COVERAGE.md +++ b/docs/TEST_COVERAGE.md @@ -4,7 +4,7 @@ **Verified**: 2026-10-23 with `cargo test` -**Result**: 1,313 passing tests and 9 ignored tests (1,322 total), including the golden-file corpus (#391) +**Result**: 1,314 passing tests and 9 ignored tests (1,323 total), including the golden-file corpus (#391) For v2.0.5, `tests/edge_cases_test.rs` checks that a file of 1 to 4,095 bytes is `STG-045`, unchanged and with no WAL, when it is a database cut below one page or foreign bytes, and opens as a new database that takes a write and reads it back after reopen when it is a prefix of the initial header or all zeros (#506). Rule-body tests in `tests/recursive_rules_test.rs` check that a `:db/valid-at` pattern in a rule definition, in its `not` and `not-join` bodies and in its `or` branches binds the query's valid time, on the semi-naive, stratified and magic-sets paths (#617). @@ -35,7 +35,7 @@ The v2.0.9 suite covers the public database API, the Datalog engine, storage and - **Core database behavior**: in-memory and file-backed operation, transactions, checkpoints, retractions, bi-temporal queries, recursive rules, prepared statements, aggregation, expressions, disjunction, window functions, UDFs, and magic-sets evaluation. - **Storage correctness**: packed pages, B+tree indexes and range scans, cache behavior, file-header validation, migration, WAL replay, checksums, corruption handling, and fault injection. - **Reliability and concurrency**: concurrent reads and writes, rollback behavior, same-process handle exclusion, cross-process locking, PID namespaces, NFS and container lock behavior, and SIGKILL recovery, and queries seeing each concurrent transaction whole and reading one state for all their patterns, also during a checkpoint (`tests/snapshot_atomicity_test.rs`, #554, #555, #558). -- **WAL entries of any size** (`src/wal.rs`, 2 tests, 1 replacing the 1,000,000-fact cap test; #686): an entry of 1,000,001 facts and the entries after it replay, and reopening the writer cuts none of them off; a fact count the bytes after it cannot hold (one more than a quarter of them, or `u64::MAX`) ends replay at that entry, and reopening the writer cuts the WAL off there. +- **WAL entries of any size** (`src/wal.rs`, 3 tests, 1 replacing the 1,000,000-fact cap test; #686): an entry of 1,000,001 facts and the entries after it replay, and reopening the writer cuts none of them off; a fact count the bytes after it cannot hold (one more than a quarter of them, or `u64::MAX`) ends replay at that entry, and reopening the writer cuts the WAL off there. A count the bytes could hold whose facts are cut short, at a fact's length or inside its bytes, also ends replay there. - **Kani proofs of the value encoding** (#627; not `#[test]`s, run by `cargo kani` and `.github/workflows/kani.yml`): 5 harnesses in `src/storage/index/verification.rs` prove, for every input, that `encode_value` (the `value_bytes` of the v7 indexes) writes `Null` as `[0x00]` and each of `Boolean`, `Integer`, `Float` and `Ref` with its own type byte and in its own order (non-NaN floats by IEEE total order, so `-0.0` before `0.0`), and every NaN to the same bytes. Each harness fails when its encoder is broken on purpose. Where NaN sorts is not asserted (#688). Strings, keywords, decoders, fact pages and the WAL are left out: the model checker does not finish on them, so the fuzz and property tests cover them. v3.0.0 adds proofs of its key encoders. - **Public diagnostics**: structured parser, query, storage, WAL, API, and internal error codes; the error-code registry is checked against [`ERROR_REFERENCE.md`](ERROR_REFERENCE.md). - **Compatibility and quality**: golden-file corpus of released file formats, cross-platform format compatibility, property-based tests, long-haul smoke coverage, a weekly soak at 10M facts with a 5-hour churn (#392), XTDB/Datomic semantic compatibility, grammar conformance, and rustdoc examples. diff --git a/src/wal.rs b/src/wal.rs index d09cbdefd1..ac2f16b24a 100644 --- a/src/wal.rs +++ b/src/wal.rs @@ -888,6 +888,30 @@ mod tests { assert_eq!(tx_counts(&path), [1]); } + /// A count the bytes after it could hold, whose facts are cut short, ends + /// replay at that entry: at a fact's length or inside its bytes. + #[test] + fn test_wal_entry_with_facts_cut_short_ends_replay() { + let dir = tempfile::tempdir().unwrap(); + let path = dir.path().join("test.wal"); + let one_len = { + let p = dir.path().join("one.wal"); + wal_with_entries(&p, 1).len() as u64 + }; + + // Entry 2 claims a second fact; the file ends where its length would be. + let bytes = wal_with_entries(&path, 2); + let mut file = std::fs::OpenOptions::new().write(true).open(&path).unwrap(); + file.seek(std::io::SeekFrom::Start(one_len + 12)).unwrap(); + file.write_all(&2u64.to_le_bytes()).unwrap(); + drop(file); + assert_eq!(tx_counts(&path), [1]); + + // Entry 2's only fact loses its last bytes. + std::fs::write(&path, &bytes[..bytes.len() - 3]).unwrap(); + assert_eq!(tx_counts(&path), [1]); + } + /// An entry of more than 1,000,000 facts replays, and so do the entries /// after it; the writer's tail cut at open keeps them (#686). #[test]