Comments + debugging drop

Dependencies

• [2] 73Z2UB3J Cleanup + comments
• [3] XEU2QVLC Debugging after plugging this into Pijul
• [4] MSRWB47Y Deletions at immutable leaves weren't really deleting anything
• [5] Q7DRIBBR Debugging replace (which cannot be del+put)
• [6] WS4ZQM4R Debugging, tests, etc.
• [7] KMT3MF5N Drop a database
• [8] W26CFMAQ Improving safety of cursors
• [9] EAAYH6BQ Debugging put
• [10] OTWDDJE7 Trait/type cleanup
• [11] H3FVSQIQ Unsized pages
• [12] 6UVFCERM Formatting, debugging, etc.
• [13] YWFYZNLZ Cleanup + inter-process concurrency
• [14] OFINGD26 implementing prev() on cursors (+ some cleanup)
• [15] QEUTVAZ4 Splitting btree::page
• [16] ONES3V46 reference counting works for put
• [17] DV4A2LR7 Double-inserts (rebalancing near an internal deletion)
• [18] OP6SVMOD Resetting history
• [19] X3QVVQIS More debugging (del seems to work now)
• [*] T73WR2BX Cleaner RC increments for keys and values containing references + more comments in `del`
• [*] G4JEQLLX Debugging synchronisation
• [*] UAQX27N4 Tests
• [*] KX3WVNZW Testing/debugging "rebalance causes split of the root"

Change contents

• edit in sanakirja-core/src/btree/mod.rs at line 221
  [3.50204]

  [3.3868]
  + /// Represents the result of a merge or rebalance, without touching

  + /// the parent of the merge/rebalance.
• edit in sanakirja-core/src/btree/mod.rs at line 226
  [3.50280]

  [3.50280]
  + // New merged page.
• edit in sanakirja-core/src/btree/mod.rs at line 228
  [3.50303]

  [3.50303]
  + // Pages freed by the merge (0 meaning "no page").
• edit in sanakirja-core/src/btree/mod.rs at line 233
  [3.50398]

  [3.30618]
  + // New middle key.
• edit in sanakirja-core/src/btree/mod.rs at line 235
  [3.30636]

  [3.30636]
  + // New middle value.
• edit in sanakirja-core/src/btree/mod.rs at line 237
  [3.30654]

  [21.168]
  + // Do `k` and `v` come from a page shared with another tree?
• edit in sanakirja-core/src/btree/mod.rs at line 239
  [21.194]

  [3.50436]
  + // New left page.
• edit in sanakirja-core/src/btree/mod.rs at line 241
  [3.50452]

  [3.50452]
  + // New right page.
• edit in sanakirja-core/src/btree/mod.rs at line 243
  [3.50468]

  [3.50468]
  + // Pages freed by the rebalance (0 meaning "no page").
• edit in sanakirja-core/src/btree/mod.rs at line 249
  [3.50527]

  [3.50527]
  + /// Represents a page with modifications from a merge.
• edit in sanakirja-core/src/btree/mod.rs at line 268
  [3.6029]

  [3.14304]
  + // If a rebalance causes a split, we might need to insert an entry

  + // after the replacement.
• replacement in sanakirja-core/src/btree/mod.rs at line 277
  [3.51195]→[3.9500:9583](∅→∅),[3.50706]→[3.14799:14829](∅→∅),[3.9583]→[3.14799:14829](∅→∅),[3.14799]→[3.14799:14829](∅→∅),[3.30855]→[3.51307:51424](∅→∅),[3.14829]→[3.51307:51424](∅→∅),[3.51307]→[3.51307:51424](∅→∅),[3.51424]→[2.11616:11651](∅→∅),[2.11651]→[3.51471:51481](∅→∅),[3.30912]→[3.51471:51481](∅→∅),[3.51471]→[3.51471:51481](∅→∅),[3.51481]→[3.5696:5817](∅→∅),[3.5817]→[3.9584:9735](∅→∅),[3.51481]→[3.9584:9735](∅→∅),[3.31032]→[3.51582:51660](∅→∅),[3.9735]→[3.51582:51660](∅→∅),[3.51582]→[3.51582:51660](∅→∅)
  − impl<'a, K: Representable + ?Sized, V: Representable + ?Sized, P: BTreePage<K, V>>

  − ModifiedPage<'a, K, V, P>

  − {

  − pub fn single_child(&self) -> Option<u64> {

  − let mut c1 = self.c1.clone();

  − if self.skip_first {

  − P::move_next(&mut c1);

  − }

  − debug!(

  − "single_child: {:?} {:?} {:?} {:?}",

  − self.page, self.c0, c1, self.ins

  − );

  − if P::is_empty(self.page.as_page(), &self.c0)

  − && self.ins.is_none()

  − && P::is_empty(self.page.as_page(), &c1)

  − {

  − Some(self.l)

  − } else {

  − None

  − }

  − }

  − }

  −
  [3.51195]

  [3.51660]
  + /// Represents the concatenation of a modified page and one of its

  + /// sibling (left or right).
• edit in sanakirja-core/src/btree/mod.rs at line 281
  [3.9834]

  [3.31033]
  + /// Modified page.

  + pub modified: ModifiedPage<'a, K, V, P>,

  + /// Middle element.
• replacement in sanakirja-core/src/btree/mod.rs at line 285
  [3.31062]→[3.14909:14954](∅→∅)
  − pub modified: ModifiedPage<'a, K, V, P>,
  [3.31062]

  [3.31110]
  + /// Sibling of the modified page.
• replacement in sanakirja-core/src/btree/mod.rs at line 287
  [3.31134]→[3.51883:51969](∅→∅),[3.51883]→[3.51883:51969](∅→∅)
  − // Is the modified field on the left or on the right of the

  − // concatenation?
  [3.31134]

  [3.51969]
  + /// Is the modified field on the left or on the right of the

  + /// concatenation?
• edit in sanakirja-core/src/btree/mod.rs at line 290
  [3.51996]

  [3.5818]
  + /// Is the other page owned by this tree? If not, it means `other`

  + /// is shared with another tree, and hence we need to increase the

  + /// reference count of entries coming from `other`.
• edit in sanakirja-core/src/btree/mod.rs at line 296
  [3.51999]

  [3.51999]
  + /// A database, which is essentially just a page offset along with markers.
• edit in sanakirja-core/src/btree/mod.rs at line 305
  [3.9181]

  [3.9181]
  + /// A database of sized values.
• edit in sanakirja-core/src/btree/mod.rs at line 308
  [3.52188]

  [22.127]
  + /// A database of unsized values.

  + pub type UDb<K, V> = Db_<K, V, page_unsized::Page<K, V>>;

  +
• edit in sanakirja-core/src/btree/mod.rs at line 312
  [22.221]

  [3.9231]
  + /// Load a database from a page offset.
• edit in sanakirja-core/src/btree/mod.rs at line 323
  [22.440]

  [3.183]
  + /// Create a database with an arbitrary page implementation.
• edit in sanakirja-core/src/btree/mod.rs at line 342
  [3.3887]

  [3.259]
  + /// Create a database for sized keys and values.
• replacement in sanakirja-core/src/btree/mod.rs at line 353
  [3.501]→[3.501:518](∅→∅)
  − pub fn fork_db_<
  [3.501]

  [3.3903]
  + /// Fork a database.

  + pub fn fork_db<
• replacement in sanakirja-core/src/btree/mod.rs at line 372
  [3.604]→[3.604:657](∅→∅),[3.657]→[3.15516:15598](∅→∅),[3.15598]→[3.745:765](∅→∅),[3.745]→[3.745:765](∅→∅),[3.765]→[3.15599:15652](∅→∅),[3.15652]→[3.824:846](∅→∅),[3.824]→[3.824:846](∅→∅),[3.846]→[3.404:407](∅→∅),[3.4199]→[3.404:407](∅→∅)
  − pub fn fork_db<

  − T: AllocPage + core::fmt::Debug,

  − K: Representable + core::fmt::Debug,

  − V: Representable + core::fmt::Debug,

  − >(

  − txn: &mut T,

  − db: &Db<K, V>,

  − ) -> Result<Db<K, V>, T::Error> {

  − fork_db_(txn, db)

  − }

  −
  [3.604]

  [3.10053]
  + /// Get the first entry of a database greater than or equal to `k` (or

  + /// to `(k, v)` if `v.is_some()`).
• edit in sanakirja-core/src/btree/mod.rs at line 410
  [3.318]

  [3.650]
  + /// Drop a database recursively, dropping all referenced keys and

  + /// values that aren't shared with other databases.
• replacement in sanakirja-core/src/btree/mod.rs at line 421
  [3.837]→[3.9429:9491](∅→∅),[3.9491]→[3.4199:4201](∅→∅),[3.517]→[3.4199:4201](∅→∅),[3.1543]→[3.4199:4201](∅→∅),[3.4199]→[3.4199:4201](∅→∅)
  − drop_::<T, K, V, P>(txn, txn.load_page(db.db)?.as_page())

  − }
  [3.837]

  [3.518]
  + use core::mem::MaybeUninit;
• replacement in sanakirja-core/src/btree/mod.rs at line 423
  [3.519]→[3.838:994](∅→∅),[3.994]→[3.660:798](∅→∅),[3.660]→[3.660:798](∅→∅),[3.798]→[3.9492:9590](∅→∅),[3.9590]→[3.894:922](∅→∅),[3.894]→[3.894:922](∅→∅),[3.922]→[3.995:1022](∅→∅),[3.1022]→[3.948:1194](∅→∅),[3.948]→[3.948:1194](∅→∅)
  − fn drop_<T: AllocPage, K: Representable + ?Sized, V: Representable + ?Sized, P: BTreePage<K, V>>(

  − txn: &mut T,

  − p: Page,

  − ) -> Result<(), T::Error> {

  − let rc = if P::is_dirty(p) {

  − txn.decr_rc_owned(p.offset)?

  − } else {

  − txn.decr_rc(p.offset)?

  − };

  − if rc == 0 {

  − let mut cursor = P::cursor_before(p);

  − let left_page = P::right_child(p, &cursor);

  − if left_page == 0 {

  − return Ok(());

  − }

  − drop_::<T, K, V, P>(txn, txn.load_page(left_page)?.as_page())?;

  − while let Some((k, v, r)) = P::next(txn, p, &mut cursor) {

  − for o in k.page_offsets().chain(v.page_offsets()) {

  − txn.decr_rc(o)?;
  [3.519]

  [3.1194]
  + let mut stack: [MaybeUninit<cursor::PageCursor<K, V, P>>; cursor::N_CURSORS] =

  + [MaybeUninit::uninit(); cursor::N_CURSORS];

  + let page = txn.load_page(db.db)?;

  + stack[0] = MaybeUninit::new(cursor::PageCursor {

  + page,

  + cursor: P::cursor_before(page.as_page()),

  + });

  + let mut ptr = 0;

  + loop {

  + let cur = unsafe { &mut *stack[ptr].as_mut_ptr() };

  + let rc = txn.rc(cur.page.offset)?;

  + if rc <= 1 {

  + if let Some((k, v, _)) = P::current(txn, cur.page.as_page(), &cur.cursor) {

  + for o in k.page_offsets().chain(v.page_offsets()) {

  + txn.decr_rc(o)?;

  + }
• replacement in sanakirja-core/src/btree/mod.rs at line 440
  [3.1208]→[3.1208:1276](∅→∅)
  − drop_::<T, K, V, P>(txn, txn.load_page(r)?.as_page())?;
  [3.1208]

  [3.1276]
  + if P::move_next(&mut cur.cursor) {

  + let r = P::left_child(cur.page.as_page(), &cur.cursor);

  + if r > 0 {

  + ptr += 1;

  + let page = txn.load_page(r)?;

  + stack[ptr] = MaybeUninit::new(cursor::PageCursor {

  + page,

  + cursor: P::cursor_before(page.as_page()),

  + })

  + }

  + continue

  + }
• edit in sanakirja-core/src/btree/mod.rs at line 453
  [3.1286]

  [3.1286]
  + if P::is_dirty(cur.page.as_page()) {

  + txn.decr_rc_owned(cur.page.offset)?;

  + } else {

  + txn.decr_rc(cur.page.offset)?;

  + }

  + if ptr == 0 {

  + break

  + } else {

  + ptr -= 1;

  + }
• replacement in sanakirja-core/src/btree/del.rs at line 523
  [3.23598]→[3.23598:23644](∅→∅)
  − if let Some(d) = last_op.single_child() {
  [3.38597]

  [3.23644]
  + if let Some(d) = single_child(&last_op) {
• edit in sanakirja-core/src/btree/del.rs at line 591
  [2.12290]

  [2.12290]
  + fn single_child<K: Representable+?Sized, V: Representable+?Sized, P: BTreeMutPage<K, V>>(m: &ModifiedPage<K, V, P>) -> Option<u64> {

  + let mut c1 = m.c1.clone();

  + if m.skip_first {

  + P::move_next(&mut c1);

  + }

  + debug!(

  + "single_child: {:?} {:?} {:?} {:?}",

  + m.page,

  + m.c0, c1, m.ins

  + );

  + if P::is_empty(m.page.as_page(), &m.c0)

  + && m.ins.is_none()

  + && P::is_empty(m.page.as_page(), &c1)

  + {

  + Some(m.l)

  + } else {

  + None

  + }

  + }

  +

  +
• replacement in sanakirja/src/tests.rs at line 172
  [3.10997]→[3.10997:11044](∅→∅)
  − let db2 = fork_db(&mut txn, &db).unwrap();
  [3.10997]

  [3.11044]
  + let _db2 = fork_db(&mut txn, &db).unwrap();
• edit in sanakirja/src/tests.rs at line 942
  [24.5523]
  +

  + #[test]

  + pub fn fork_drop() {

  + env_logger::try_init().unwrap_or(());

  + let env = Env::new_anon(409600000, 1).unwrap();

  + let mut txn = Env::mut_txn_begin(&env).unwrap();

  + let mut db: Db<u64, u64> = create_db(&mut txn).unwrap();

  + let n = 1000 as u64;

  + let i0 = 10 as u64;

  + let mut values = Vec::with_capacity(n as usize);

  + for i in 0..n {

  + put(&mut txn, &mut db, &i, &i).unwrap();

  + if i != i0 {

  + values.push(i);

  + }

  + }

  + let db2 = fork_db(&mut txn, &db).unwrap();

  + put(&mut txn, &mut db, &n, &n).unwrap();

  + crate::debug::debug(&txn, &[&db, &db2], "debug1", true);

  + drop(&mut txn, db2).unwrap();

  + crate::debug::debug(&txn, &[&db], "debug2", true);

  +

  + let mut refs = BTreeMap::new();

  + add_refs(&txn, &db, &mut refs).unwrap();

  + let mut err = 0;

  + for (p, r) in refs.iter() {

  + println!("{:?} {:?}", p, r);

  + if *r >= 2 {

  + error!("{:?} {:?} {:?}", p, txn.rc(*p).unwrap(), *r);

  + err += 1;

  + } else {

  + if txn.rc(*p).unwrap() != 0 {

  + error!("{:?} {:?} 0", p, txn.rc(*p).unwrap());

  + err += 1;

  + }

  + }

  + }

  + assert_eq!(err, 0);

  + }