{"header":{"message":"Shrinking files while a reader is alive","description":null,"timestamp":"2026-07-06T14:22:26.760608928Z","authors":[{}]},"hash":"I3DFXXQDTV3PVRKFIEQ62BBZQIFPDGWQIWXQRCG6BIS3QCMKGDRQC","authors":[{"login":"pmeunier","key":"AAAAC3NzaC1lZDI1NTE5AAAAILagOJFgwaMNhBWQINinKOXmqS4Gh5NgxgriXwdOoINJ"}],"deps":{"hashes":[["I3DFXXQDTV3PVRKFIEQ62BBZQIFPDGWQIWXQRCG6BIS3QCMKGDRQC","Shrinking files while a reader is alive"],["AA",null],["OP6SVMOD2GTQ7VNJ4E5KYFG4MIYA7HBMXJTADALMZH4PY7OQRMZQC","Resetting history"],["WTXLZDYIS2AQZFOO7WCSFGRK235NR2VSOI2LOCORWF5WRS3E76UAC","Fixing bus errors on a full disk"],["OHG5NX6KVGKNA7S7SU3MTPOZCN4RRZK2SGZWZ5LIRXUMCYIPUHIAC","Refactoring, drop and the Check trait"],["RLVQDUPYOWVNHTVFCHKNIQYNBRLOFY2UGIJPLD6U5S22AMEF5YSAC","Fixing a double-free error introduced in 1.2.13"],["5NBCUZRB6HQHE4CMVI4QJKXNBYON5OGOVGAOJPDV3WGJVVQ55UKAC","More efficient free list: avoid extending the file when updating the list of free pages"],["UYU2LIYDNJAN54C3O4BM3IC7TFZWUM35QP32WQVQTHY5V46JW6CAC","Subtransactions"],["VGZVSYBLU3X47MUCQ5PAYALP45RSLPAKDZL5AR6OOQDUGGA3HYNQC","Formatting + version bump"],["IVPI4DG7J5G2WOEJ6TS44UG5AFNGHP4CGF5STNO7LQK5H3L46A6QC","Shrink files as needed"],["RYZJBN5ZBHV66V6PEIHBN3B632MUPSHJSQGGJPDKGWUHXJFSQC5AC","Version bump"],["UYOLCVPCH3QPN33MQLH7RPGKSUAZJ55KSWIVUA7JEKKWCRJYZGTAC","Shrink files: don't pop all pages"],["HMWFIUDS5LITLG5AB2LL6KIHFF6W3Y4LCB4JLZBWIYIIV74PSXQAC","Support for large values + endianness bugs"],["UAQX27N4PI4LHEW6LSHJETIE5MV7JTEMPLTJFYUBMYVPC43H7VOAC","Tests"]],"deps":["OP6SVMOD2GTQ7VNJ4E5KYFG4MIYA7HBMXJTADALMZH4PY7OQRMZQC","WTXLZDYIS2AQZFOO7WCSFGRK235NR2VSOI2LOCORWF5WRS3E76UAC","OHG5NX6KVGKNA7S7SU3MTPOZCN4RRZK2SGZWZ5LIRXUMCYIPUHIAC","RLVQDUPYOWVNHTVFCHKNIQYNBRLOFY2UGIJPLD6U5S22AMEF5YSAC","5NBCUZRB6HQHE4CMVI4QJKXNBYON5OGOVGAOJPDV3WGJVVQ55UKAC","UYU2LIYDNJAN54C3O4BM3IC7TFZWUM35QP32WQVQTHY5V46JW6CAC","VGZVSYBLU3X47MUCQ5PAYALP45RSLPAKDZL5AR6OOQDUGGA3HYNQC","IVPI4DG7J5G2WOEJ6TS44UG5AFNGHP4CGF5STNO7LQK5H3L46A6QC","RYZJBN5ZBHV66V6PEIHBN3B632MUPSHJSQGGJPDKGWUHXJFSQC5AC","UYOLCVPCH3QPN33MQLH7RPGKSUAZJ55KSWIVUA7JEKKWCRJYZGTAC"],"known":["HMWFIUDS5LITLG5AB2LL6KIHFF6W3Y4LCB4JLZBWIYIIV74PSXQAC"]},"hunks":[{"Edit":{"inode":{"change":14,"pos":11},"path":"sanakirja/src/tests.rs","line":1560,"atom":{"NewVertex":{"up_context":[{"change":8,"pos":5846}],"down_context":[],"flag":"BLOCK","start":0,"end":9212,"inode":{"change":14,"pos":11}}},"contents":[{"Add":""},{"Add":"/// Regression (found via palimpsest / the pijul pristine, which uses a"},{"Add":"/// file-backed `Env::new(path, 1 << 20, 2)`): after a few commits that"},{"Add":"/// grow and then shrink the file, a **read-only** transaction fails to"},{"Add":"/// read a page a mutable transaction reads fine, with"},{"Add":"/// `Error::Corrupt(offset)` — \"offset is past the end of the file\"."},{"Add":"///"},{"Add":"/// `Txn::load_page` bounds-checks offsets against the `length` stored"},{"Add":"/// in the committed root's header, so this means a commit wrote a"},{"Add":"/// `length` smaller than the offset of a page still alive in that very"},{"Add":"/// generation. The scenario that triggers it: a small, long-lived"},{"Add":"/// table gets relocated upwards by copy-on-write during a transaction"},{"Add":"/// that also grew the file, and a later transaction frees the large"},{"Add":"/// block below/above it, letting the end-of-file trimming loop shrink"},{"Add":"/// `length` past the relocated table's pages."},{"Add":"#[test]"},{"Add":"fn read_txn_after_shrink() {"},{"Add":" unsafe {"},{"Add":" env_logger::try_init().unwrap_or(());"},{"Add":" let path = tempfile::tempdir().unwrap();"},{"Add":" let path = path.path().join(\"db\");"},{"Add":" // Same parameters as the pijul pristine."},{"Add":" let env = Env::new(&path, 1 << 20, 2).unwrap();"},{"Add":""},{"Add":" // Commit 1: a small long-lived table (\"channels\"), on low pages."},{"Add":" {"},{"Add":" let mut txn = Env::mut_txn_begin(&env).unwrap();"},{"Add":" let mut chan = create_db::, u64, u64>(&mut txn).unwrap();"},{"Add":" put(&mut txn, &mut chan, &0, &0).unwrap();"},{"Add":" txn.set_root(0, chan.db.into());"},{"Add":" txn.commit().unwrap();"},{"Add":" }"},{"Add":""},{"Add":" let read_all = |round: usize, phase: &str| {"},{"Add":" let rtxn = Env::txn_begin(&env).unwrap();"},{"Add":" // `rtxn.size` is the `length` header of the root this"},{"Add":" // read-only transaction opened — the bound its"},{"Add":" // `load_page` enforces."},{"Add":" let bound = rtxn.size;"},{"Add":" let chan: Db = rtxn.root_db(0).unwrap();"},{"Add":" for x in iter(&rtxn, &chan, None).unwrap() {"},{"Add":" if let Err(e) = x {"},{"Add":" panic!("},{"Add":" \"round {} ({}): read-only txn cannot read the small \\"},{"Add":" table: {} (file is {} pages, committed root says \\"},{"Add":" length = {} pages)\","},{"Add":" round,"},{"Add":" phase,"},{"Add":" e,"},{"Add":" std::fs::metadata(&path).unwrap().len() >> 12,"},{"Add":" bound >> 12"},{"Add":" );"},{"Add":" }"},{"Add":" }"},{"Add":" let big: Option> = rtxn.root_db(1);"},{"Add":" if let Some(big) = big {"},{"Add":" for x in iter(&rtxn, &big, None).unwrap() {"},{"Add":" if let Err(e) = x {"},{"Add":" panic!("},{"Add":" \"round {} ({}): read-only txn cannot read the big \\"},{"Add":" table: {} (file is {} pages, committed root says \\"},{"Add":" length = {} pages)\","},{"Add":" round,"},{"Add":" phase,"},{"Add":" e,"},{"Add":" std::fs::metadata(&path).unwrap().len() >> 12,"},{"Add":" bound >> 12"},{"Add":" );"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":" };"},{"Add":""},{"Add":" let n = 20_000u64;"},{"Add":" for round in 0..8 {"},{"Add":" // Grow: fill a big table, and *touch the small one* so"},{"Add":" // copy-on-write relocates it into the newly grown region."},{"Add":" {"},{"Add":" let mut txn = Env::mut_txn_begin(&env).unwrap();"},{"Add":" let mut big = if let Some(db) = txn.root_db(1) {"},{"Add":" db"},{"Add":" } else {"},{"Add":" create_db::, u64, u64>(&mut txn).unwrap()"},{"Add":" };"},{"Add":" for i in 0..n {"},{"Add":" put(&mut txn, &mut big, &i, &i).unwrap();"},{"Add":" }"},{"Add":" let mut chan: Db = txn.root_db(0).unwrap();"},{"Add":" put(&mut txn, &mut chan, &(round as u64 + 1), &0).unwrap();"},{"Add":" txn.set_root(0, chan.db.into());"},{"Add":" txn.set_root(1, big.db.into());"},{"Add":" txn.commit().unwrap();"},{"Add":" }"},{"Add":" read_all(round, \"after growth\");"},{"Add":""},{"Add":" // Shrink: empty the big table; the commit trims the file."},{"Add":" {"},{"Add":" let mut txn = Env::mut_txn_begin(&env).unwrap();"},{"Add":" let mut big: Db = txn.root_db(1).unwrap();"},{"Add":" for i in 0..n {"},{"Add":" del(&mut txn, &mut big, &i, None).unwrap();"},{"Add":" }"},{"Add":" txn.set_root(1, big.db.into());"},{"Add":" txn.commit().unwrap();"},{"Add":" }"},{"Add":" read_all(round, \"after shrink\");"},{"Add":" }"},{"Add":" }"},{"Add":"}"},{"Add":""},{"Add":"/// Adversarial variant of `read_txn_after_shrink`: a single"},{"Add":"/// transaction that begins by trimming (the previous transaction"},{"Add":"/// freed everything), then does *several* cycles of growing back into"},{"Add":"/// the trimmed region and freeing a few of the re-extended pages."},{"Add":"/// After commit, the free db must describe exactly the final state:"},{"Add":"/// no stale entry for a re-extended page that stayed alive, exactly"},{"Add":"/// one entry for a re-extended page freed again, and the committed"},{"Add":"/// `length` must cover every page reachable from the root — checked"},{"Add":"/// both with a full read-only iteration and with the"},{"Add":"/// `check_free`/`check_refs` consistency walkers."},{"Add":"#[test]"},{"Add":"fn read_txn_after_shrink_regrow_cycles() {"},{"Add":" unsafe {"},{"Add":" env_logger::try_init().unwrap_or(());"},{"Add":" let path = tempfile::tempdir().unwrap();"},{"Add":" let path = path.path().join(\"db\");"},{"Add":" let env = Env::new(&path, 1 << 20, 2).unwrap();"},{"Add":""},{"Add":" // Commit 1: create the table."},{"Add":" {"},{"Add":" let mut txn = Env::mut_txn_begin(&env).unwrap();"},{"Add":" let db = create_db::, u64, u64>(&mut txn).unwrap();"},{"Add":" txn.set_root(0, db.db.into());"},{"Add":" txn.commit().unwrap();"},{"Add":" }"},{"Add":""},{"Add":" let n = 20_000u64;"},{"Add":" for round in 0..6 {"},{"Add":" // Grow: fill the table (several hundred pages)."},{"Add":" {"},{"Add":" let mut txn = Env::mut_txn_begin(&env).unwrap();"},{"Add":" let mut db: Db = txn.root_db(0).unwrap();"},{"Add":" for i in 0..n {"},{"Add":" put(&mut txn, &mut db, &i, &i).unwrap();"},{"Add":" }"},{"Add":" txn.set_root(0, db.db.into());"},{"Add":" txn.commit().unwrap();"},{"Add":" }"},{"Add":" // Shrink: free (almost) everything, so the *next* begin trims."},{"Add":" {"},{"Add":" let mut txn = Env::mut_txn_begin(&env).unwrap();"},{"Add":" let mut db: Db = txn.root_db(0).unwrap();"},{"Add":" for i in 0..n {"},{"Add":" del(&mut txn, &mut db, &i, None).unwrap();"},{"Add":" }"},{"Add":" txn.set_root(0, db.db.into());"},{"Add":" txn.commit().unwrap();"},{"Add":" }"},{"Add":" // The adversarial transaction: begins with a trim, then"},{"Add":" // several cycles of growing back into the trimmed region"},{"Add":" // and freeing a few of the freshly re-extended pages."},{"Add":" {"},{"Add":" let mut txn = Env::mut_txn_begin(&env).unwrap();"},{"Add":" let mut db: Db = txn.root_db(0).unwrap();"},{"Add":" let mut next = 0u64;"},{"Add":" for _cycle in 0..5 {"},{"Add":" // Grow: a few thousand entries extend the file"},{"Add":" // into (and past) the trimmed region."},{"Add":" for i in next..next + 4_000 {"},{"Add":" put(&mut txn, &mut db, &i, &i).unwrap();"},{"Add":" }"},{"Add":" // Free a few of the pages just allocated."},{"Add":" for i in next..next + 500 {"},{"Add":" del(&mut txn, &mut db, &i, None).unwrap();"},{"Add":" }"},{"Add":" next += 4_000;"},{"Add":" }"},{"Add":" txn.set_root(0, db.db.into());"},{"Add":" txn.commit().unwrap();"},{"Add":" }"},{"Add":""},{"Add":" // A read-only transaction must be able to read everything."},{"Add":" {"},{"Add":" let rtxn = Env::txn_begin(&env).unwrap();"},{"Add":" let bound = rtxn.size;"},{"Add":" let db: Db = rtxn.root_db(0).unwrap();"},{"Add":" for x in iter(&rtxn, &db, None).unwrap() {"},{"Add":" if let Err(e) = x {"},{"Add":" panic!("},{"Add":" \"round {}: read-only txn failed: {} (file {} pages, \\"},{"Add":" committed length {} pages)\","},{"Add":" round,"},{"Add":" e,"},{"Add":" std::fs::metadata(&path).unwrap().len() >> 12,"},{"Add":" bound >> 12"},{"Add":" );"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":""},{"Add":" // And the free db + references must be consistent: every"},{"Add":" // page is either reachable, free, or trimmed — no page"},{"Add":" // both alive and free, none lost."},{"Add":" {"},{"Add":" let mut txn = Env::mut_txn_begin(&env).unwrap();"},{"Add":" let mut refs = BTreeMap::new();"},{"Add":" let db: Db = txn.root_db(0).unwrap();"},{"Add":" add_refs(&txn, &db, &mut refs).unwrap();"},{"Add":" add_free_refs_mut(&txn, &mut refs).unwrap();"},{"Add":" check_free_mut(&mut txn, &refs);"},{"Add":" check_refs(&txn, &refs);"},{"Add":" }"},{"Add":" }"},{"Add":" }"},{"Add":"}"}]}},{"Edit":{"inode":{"change":2,"pos":80166},"path":"sanakirja/src/environment/muttxn.rs","line":179,"atom":{"NewVertex":{"up_context":[{"change":7,"pos":8788}],"down_context":[{"change":7,"pos":8788}],"flag":"BLOCK","start":9213,"end":9776,"inode":{"change":2,"pos":80166}}},"contents":[{"Add":" // Trimmed pages re-allocated by this subtransaction's file"},{"Add":" // extensions: the subtransaction can't pop its parent's"},{"Add":" // `to_delete` when allocating, so apply the same accounting as"},{"Add":" // `MutTxn::alloc_page_` now that the parent's `length` has"},{"Add":" // caught up."},{"Add":" while self"},{"Add":" .parent"},{"Add":" .to_delete"},{"Add":" .last()"},{"Add":" .map_or(false, |&p| p < self.parent.length)"},{"Add":" {"},{"Add":" let p = self.parent.to_delete.pop().unwrap();"},{"Add":" self.parent.initial_allocated.push(p);"},{"Add":" }"},{"Add":""}]}},{"Edit":{"inode":{"change":2,"pos":80166},"path":"sanakirja/src/environment/muttxn.rs","line":449,"atom":{"EdgeMap":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":9,"pos":1922},"to":{"change":9,"start":1922,"end":2556},"introduced_by":9},{"previous":"","flag":"DELETED","from":{"change":5,"pos":1344},"to":{"change":4,"start":9293,"end":9333},"introduced_by":5},{"previous":"","flag":"DELETED","from":{"change":9,"pos":2556},"to":{"change":4,"start":9293,"end":9333},"introduced_by":9},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":9293},"to":{"change":4,"start":9293,"end":9333},"introduced_by":4},{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":4,"pos":9333},"to":{"change":9,"start":2557,"end":2558},"introduced_by":9}],"inode":{"change":2,"pos":80166}}},"contents":[{"Del":" // Pages resulting from the shrinking at the beginning\n // of the transaction. We can't do it at any other\n // time in order not to break the invariants between\n // initial_free, free, free_owned on the one hand, and\n // `free_db` on the other. This is because `del`\n // (including on `free_db` itself) inserts pages into\n // these Vecs.\n for p in std::mem::take(&mut self.to_delete) {\n if p >= self.length {\n btree::del(&mut self, &mut free_db, &L64(p.to_le()), None)?;\n"},{"Del":" }\n }\n"},{"Del":"\n"}]}},{"Edit":{"inode":{"change":2,"pos":80166},"path":"sanakirja/src/environment/muttxn.rs","line":453,"atom":{"NewVertex":{"up_context":[{"change":6,"pos":172}],"down_context":[{"change":6,"pos":172}],"flag":"BLOCK","start":9777,"end":11221,"inode":{"change":2,"pos":80166}}},"contents":[{"Add":""},{"Add":" // Pages resulting from the shrinking at the"},{"Add":" // beginning of the transaction: they still have an"},{"Add":" // entry in the tree of free pages, which must go."},{"Add":" // This runs inside the fix point (and `to_delete`"},{"Add":" // stays live) because these `del`s — like any edit"},{"Add":" // below — may themselves allocate by extending the"},{"Add":" // file, re-acquiring trimmed pages: the allocator"},{"Add":" // then pops them off the *back* of `to_delete`"},{"Add":" // (they are the smallest, and extension is"},{"Add":" // contiguous from `length`) into"},{"Add":" // `initial_allocated`, while we consume the"},{"Add":" // beyond-end-of-file ones from the *front*"},{"Add":" // (largest first). See"},{"Add":" // `tests::read_txn_after_shrink` and"},{"Add":" // `tests::read_txn_after_shrink_regrow_cycles`."},{"Add":" let cut = self"},{"Add":" .to_delete"},{"Add":" .iter()"},{"Add":" .take_while(|&&p| p >= self.length)"},{"Add":" .count();"},{"Add":" let dels: Vec = self.to_delete.drain(..cut).collect();"},{"Add":" for p in dels {"},{"Add":" btree::del(&mut self, &mut free_db, &L64(p.to_le()), None)?;"},{"Add":" changed = true;"},{"Add":" }"}]}},{"Edit":{"inode":{"change":2,"pos":80166},"path":"sanakirja/src/environment/muttxn.rs","line":504,"atom":{"NewVertex":{"up_context":[{"change":2,"pos":85039}],"down_context":[{"change":5,"pos":2478}],"flag":"BLOCK","start":11222,"end":11479,"inode":{"change":2,"pos":80166}}},"contents":[{"Add":" // Every trimmed page was either consumed above"},{"Add":" // (beyond the end of the file) or re-allocated by"},{"Add":" // extension (and popped into `initial_allocated`)."},{"Add":" debug_assert!(self.to_delete.is_empty());"}]}},{"Edit":{"inode":{"change":2,"pos":80166},"path":"sanakirja/src/environment/muttxn.rs","line":729,"atom":{"NewVertex":{"up_context":[{"change":2,"pos":88161}],"down_context":[{"change":3,"pos":318}],"flag":"BLOCK","start":11480,"end":12420,"inode":{"change":2,"pos":80166}}},"contents":[{"Add":" // If this offset was trimmed off the end of the file at"},{"Add":" // the beginning of the transaction, it is now being"},{"Add":" // re-allocated: take it out of `to_delete`. Since"},{"Add":" // `to_delete` is sorted in decreasing order (it was"},{"Add":" // filled by a reverse iteration over the contiguous"},{"Add":" // trailing run of free pages), the only candidate is"},{"Add":" // its last element. The page also joins"},{"Add":" // `initial_allocated`: it still has a (stale) entry in"},{"Add":" // the tree of free pages, which the commit removes for"},{"Add":" // all of `initial_allocated` — this also covers pages"},{"Add":" // re-allocated by the commit's own edits to that tree."},{"Add":" if self.to_delete.last() == Some(&offset) {"},{"Add":" self.to_delete.pop();"},{"Add":" self.initial_allocated.push(offset);"},{"Add":" }"}]}},{"Replacement":{"inode":{"change":2,"pos":108835},"path":"Cargo.toml","line":6,"ins":{"up_context":[{"change":10,"pos":391}],"down_context":[{"change":10,"pos":416}],"flag":"BLOCK","start":12421,"end":12446,"inode":{"change":2,"pos":108835}},"del":{"edges":[{"previous":"BLOCK","flag":"BLOCK | DELETED","from":{"change":10,"pos":391},"to":{"change":11,"start":43,"end":68},"introduced_by":11}],"inode":{"change":2,"pos":108835}},"ins_contents":[{"Add":"version = \"2.0.0-beta.3\""}],"del_contents":[{"Del":"version = \"2.0.0-beta.2\"\n"}]}}],"owner":"pijul","repo":"sanakirja","token":"CCBSnLID1ynCQajus3OJQOwIwavdpSajph5tUAiE1g4=","login":null}

…

Dependencies

Change contents