Cleaner RC increments for keys and values containing references + more comments in `del`

[?]

Feb 10, 2021, 6:22 PM

T73WR2BX2QDQ6APOREBXUKNH52FDLJNBGWPQUYB2TAF2PT7XCL2AC

Dependencies

[2] XEU2QVLC Debugging after plugging this into Pijul
[3] WAKPPBKO Fixing a double-free of roots after deletions (the root was freed both by handle_merge and by update_root)
[4] UUUVNC4D Debugging/cleanup around cursors
[5] X3QVVQIS More debugging (del seems to work now)
[6] OP6SVMOD Resetting history
[7] APPY2E7M Unsized deletions + custom sizes back
[8] WS4ZQM4R Debugging, tests, etc.
[9] EAAYH6BQ Debugging put
[10] 6UVFCERM Formatting, debugging, etc.
[11] KMT3MF5N Drop a database
[12] QEUTVAZ4 Splitting btree::page
[13] W26CFMAQ Improving safety of cursors
[14] OFINGD26 implementing prev() on cursors (+ some cleanup)
[15] OTWDDJE7 Trait/type cleanup
[*] H3FVSQIQ Unsized pages
[*] KX3WVNZW Testing/debugging "rebalance causes split of the root"

Change contents

edit in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 91

[17.24945]

[18.1102]

incr_kv_rc: !m.other_is_mutable,
edit in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 177

[17.26989]

[18.1757]

incr_kv_rc: !m.modified.mutable,
edit in sanakirja-core/src/btree/page/rebalance.rs at line 121

[4.3846]

[18.2839]

incr_kv_rc: !m.other_is_mutable,
edit in sanakirja-core/src/btree/page/rebalance.rs at line 205

[4.5895]

[18.3429]

incr_kv_rc: !m.modified.mutable,
edit in sanakirja-core/src/btree/mod.rs at line 227

[4.30654]

[4.50436]

incr_kv_rc: bool,
replacement in sanakirja-core/src/btree/mod.rs at line 243

[4.30691]→[4.30540:30597](∅→∅)

// Whether the page can be written to (used for RC).

[4.30691]

[4.50760]

// Whether the page is mutable with another tree.
replacement in sanakirja-core/src/btree/del.rs at line 15

[4.53075]→[4.53075:53256](∅→∅)

/// If `value` is `None`, delete one of the bindings associated to
/// `key` from the database (without any specific
/// preference). Else, delete the specified binding if present.

[4.53075]

[4.53256]

/// If `value` is `None`, delete the first entry for `key` from the
/// database, if present. Else, delete the entry for `(key, value)`,
/// if present.
edit in sanakirja-core/src/btree/del.rs at line 38

[4.53703]

[4.53703]

/// Delete the entry pointed to by `cursor`.
replacement in sanakirja-core/src/btree/del.rs at line 61

[4.1260]→[4.1260:1289](∅→∅)

txn.incr_rc(o)?;

[4.1260]

[4.16753]

txn.decr_rc(o)?;
replacement in sanakirja-core/src/btree/del.rs at line 64

[4.16769]→[4.30598:30668](∅→∅),[4.53999]→[4.30598:30668](∅→∅),[4.30668]→[4.16770:16803](∅→∅)

// Find the leftmost page in the right subtree, that is where the
// "replacement" element is.

[4.16769]

[4.54094]

// Find the leftmost page in the right subtree of the deleted
// element, in order to find a replacement.
replacement in sanakirja-core/src/btree/del.rs at line 68

[4.6151]→[4.30694:30765](∅→∅),[4.30765]→[4.16804:16907](∅→∅)

// Mark the replacement for deletion in the leaf, and copy it into
// (k0, v0) if the deletion happens in an internal node (`(k0,
// v0)` is uninitialized else).

[4.6151]

[4.2381]

// In the leaf, mark the replacement for deletion, and keep a
// reference to it in k0v0 if the deletion happens in an internal
// node (k0v0 is `Option::None` else).
edit in sanakirja-core/src/btree/del.rs at line 72

[4.2442]

[4.55545]

modify_rc(txn, &last_op, cursor.pointer(), cursor.first_rc_level)?;
replacement in sanakirja-core/src/btree/del.rs at line 90

[4.17603]→[4.17603:17624](∅→∅)

// outcomes.

[4.17603]

[4.4202]

// outcomes. This mutates or clones the children page,
// i.e. the page at level `cursor.pointer + 1`, returning an
// `Op` describing what happened (between update, merge,
// rebalance and split).
replacement in sanakirja-core/src/btree/del.rs at line 98

[4.17696]→[4.17696:17789](∅→∅)

// to be performed at the current level (i.e. at level
// `cursor.pointer`).

[4.17696]

[4.30987]

// to be performed at level `p` (i.e. at level
// `cursor.pointer`), without mutating/cloning that page.
edit in sanakirja-core/src/btree/del.rs at line 102

[4.2591]

[4.59591]

// Update the reference counts, potentially freeing the page
// at the current level.
modify_rc(txn, &last_op, cursor.pointer(), cursor.first_rc_level)?;
replacement in sanakirja-core/src/btree/del.rs at line 121

[4.18161]→[4.60770:60797](∅→∅),[4.60770]→[4.60770:60797](∅→∅)

for p in free.iter() {

[4.18161]

[4.60797]

for (n, p) in free.iter().enumerate() {
debug!("freeing at level {:?}: {:?}", n, p);
edit in sanakirja-core/src/btree/del.rs at line 137

[4.61107]

[4.61107]

/// Follow the leftmost pages of each page until the leftmost leaf of
/// the subtree starting at `cursor.pointer()`, and set `cursor` to
/// point to the leftmost element of that subtree.
edit in sanakirja-core/src/btree/del.rs at line 151

[4.9813]→[4.31432:31480](∅→∅),[4.32463]→[4.31432:31480](∅→∅),[4.31480]→[4.1364:1426](∅→∅),[4.1426]→[4.31524:31531](∅→∅),[4.31524]→[4.31524:31531](∅→∅)

debug!(
"find_min: {:?} {:?} {:?}",
cur.page,
cursor.pointer(),
left_page
);
edit in sanakirja-core/src/btree/del.rs at line 157

[4.61776]→[4.1461:1526](∅→∅)

debug!("find_min: cursor.pointer = {:?}", cursor.pointer());
edit in sanakirja-core/src/btree/del.rs at line 160

[4.31535]

[4.31535]

/// Preparing a modified page for the leaf.
replacement in sanakirja-core/src/btree/del.rs at line 177

[4.9998]→[4.1675:1690](∅→∅),[4.32069]→[4.1675:1690](∅→∅),[4.1690]→[4.32269:32388](∅→∅),[4.32269]→[4.32269:32388](∅→∅),[4.32388]→[4.18675:18824](∅→∅),[4.18824]→[4.32527:32664](∅→∅),[4.32527]→[4.32527:32664](∅→∅)

if is_rc {
let mut c0 = c0.clone();
let mut c1 = c1.clone();
P::move_next(curs0.page.as_page(), &mut c1);
while let Some((k, v, _)) = P::next(txn, curs0.page.as_page(), &mut c0)
.or_else(|| P::next(txn, curs0.page.as_page(), &mut c1))
{
for o in k.page_offsets().chain(v.page_offsets()) {
txn.incr_rc(o)?;
}
}
}

[4.9998]

[4.18825]
replacement in sanakirja-core/src/btree/del.rs at line 180

[4.1716]→[4.32819:32866](∅→∅),[4.32819]→[4.32819:32866](∅→∅),[4.32866]→[4.9999:10027](∅→∅)

// increase the RC of the replacement.
debug!("{:?}", c0);

[4.1716]

[4.10027]

// In this case, we need to save the replacement. If the
// replacement has references, we will increment them later,
// when updating the page where the deletion happens.
replacement in sanakirja-core/src/btree/del.rs at line 185

[4.1825]→[4.1825:1897](∅→∅)

for o in (&*k).page_offsets().chain((&*v).page_offsets()) {

[4.1825]

[4.1897]

for o in k.page_offsets().chain(v.page_offsets()) {
replacement in sanakirja-core/src/btree/del.rs at line 194

[4.33374]→[4.1989:2052](∅→∅)

mutable: cursor.pointer() < cursor.first_rc_level,

[4.33374]

[4.33435]

mutable: !is_rc,
edit in sanakirja-core/src/btree/del.rs at line 207

[4.61790]

[4.61790]

/// From a cursor at level `p = cursor.pointer()`, form the
/// concatenation of `last_op` (which is a modified page at level p +
/// 1`, and its left or right sibling, depending on the case.
replacement in sanakirja-core/src/btree/del.rs at line 224

[4.2083]→[2.5908:5946](∅→∅)

let rc_l = cursor.first_rc_level;

[4.2083]

[4.33754]

let rc_level = cursor.first_rc_level;
replacement in sanakirja-core/src/btree/del.rs at line 226

[4.33791]→[4.10105:10151](∅→∅)

// let c = curs.cursor.as_mut().unwrap();

[4.33791]

[4.33792]
replacement in sanakirja-core/src/btree/del.rs at line 228

[4.33809]→[4.2983:3071](∅→∅),[4.3071]→[4.10152:10242](∅→∅),[4.10242]→[2.5947:6014](∅→∅)

if let Some(s) = k0v0 {
let (k0, v0) = unsafe { P::from_saved(s) };
let other = txn.load_page(P::left_child(curs.page.as_page(), &curs.cursor))?;
let other_is_rced = if p > rc_l {
true

[4.33809]

[2.6014]

// Here, p == p0, meaning that we're deleting at an internal
// node. If that's the case, k0v0 is `Some`, hence we can
// safely unwrap the replacement.
let (k0, v0) = unsafe { P::from_saved(k0v0.as_ref().unwrap()) };

// Since we've picked the leftmost entry of the right child of
// the deleted entry, the other page to consider in the
// concatenation is the left child of the deleted entry.
let other = txn.load_page(P::left_child(curs.page.as_page(), &curs.cursor))?;
// Then, if the page at level `p` or one of its ancestor, is
// pointed at least twice (i.e. if `p >= rc_level`, or
// alternatively if `other` is itself pointed at least twice,
// the page is immutable, meaning that we can't delete on it
// when rebalancing.
let other_is_mutable = (p < rc_level) && txn.rc(other.offset)? < 2;
Ok(Concat {
modified: last_op,
mid: (k0, v0),
other,
mod_is_left: false,
other_is_mutable,
})
} else {
// Here, `p` is not a leaf (but `last_op` might be), and does
// not contain the deleted entry.

// In this case, the visited page at level `p+1` is always on
// the left-hand side of the cursor at level `p` (this is an
// invariant of cursors). However, if the cursor at level `p`
// is past the end of the page, we need to move one step back
// to find a middle element for the concatenation, in which
// case the visited page becomes the right-hand side of the
// cursor.
let ((k, v, r), mod_is_left) =
if let Some(x) = P::current(txn, curs.page.as_page(), &curs.cursor) {
// Not the last element of the page.
(x, true)
replacement in sanakirja-core/src/btree/del.rs at line 266

[2.6035]→[2.6035:6078](∅→∅)

txn.rc(other.offset)? >= 2

[2.6035]

[2.6078]

// Last element of the page.
let (k, v, _) = P::prev(txn, curs.page.as_page(), &mut curs.cursor).unwrap();
let l = P::left_child(curs.page.as_page(), &curs.cursor);
((k, v, l), false)
edit in sanakirja-core/src/btree/del.rs at line 271

[4.10242]→[4.19655:19804](∅→∅),[2.6093]→[4.19655:19804](∅→∅),[4.19655]→[4.19655:19804](∅→∅),[4.19804]→[2.6094:6144](∅→∅),[2.6144]→[4.19804:19873](∅→∅),[4.19804]→[4.19804:19873](∅→∅),[4.19873]→[4.62564:62577](∅→∅),[4.62564]→[4.62564:62577](∅→∅),[4.62577]→[4.33035:33071](∅→∅),[4.33071]→[4.10243:10337](∅→∅),[4.10337]→[4.8793:8842](∅→∅),[4.19957]→[4.8793:8842](∅→∅),[4.33149]→[4.8793:8842](∅→∅),[4.8842]→[4.33149:33180](∅→∅),[4.33149]→[4.33149:33180](∅→∅),[4.33180]→[4.8843:8884](∅→∅),[4.8884]→[4.33180:33213](∅→∅),[4.33180]→[4.33180:33213](∅→∅),[4.33213]→[4.10338:10498](∅→∅),[4.10498]→[4.33342:33412](∅→∅),[4.33342]→[4.33342:33412](∅→∅)

Ok(Concat {
modified: last_op,
mid: (k0, v0),
other,
mod_is_left: false,
other_is_mutable: !other_is_rced,
})
} else {
unreachable!()
}
} else {
let mut mod_is_left = true;
let (k, v, r) = if let Some(x) = P::current(txn, curs.page.as_page(), &curs.cursor) {
// Not the last element of the page.
x
} else {
// Last element of the page.
mod_is_left = false;
let (k, v, _) = P::prev(txn, curs.page.as_page(), &mut curs.cursor).unwrap();
let l = P::left_child(curs.page.as_page(), &curs.cursor);
debug!("prev: {:?}", l);
(k, v, l)
};
replacement in sanakirja-core/src/btree/del.rs at line 272

[4.62688]→[2.6145:6271](∅→∅)

let other_is_rced = if p > rc_l {
true
} else {
txn.rc(other.offset)? >= 2
};

[4.62688]

[4.62688]

let other_is_mutable = (p < rc_level) && txn.rc(other.offset)? < 2;
replacement in sanakirja-core/src/btree/del.rs at line 278

[4.33518]→[2.6272:6318](∅→∅)

other_is_mutable: !other_is_rced,

[4.33518]

[4.62814]

other_is_mutable,
edit in sanakirja-core/src/btree/del.rs at line 283

[4.33961]

[4.33961]

/// Prepare a modified version of the page at the current level `p =
/// cursor.pointer()`.
edit in sanakirja-core/src/btree/del.rs at line 316

[4.34844]

[4.34844]

// Here, we match on `merge`, the operation that just happened at
// level `cursor.pointer() + 1`, and build the modification plan
// for the page at the current level (i.e. at level
// `cursor.pointer()`).
replacement in sanakirja-core/src/btree/del.rs at line 332

[4.35183]→[4.35183:35233](∅→∅)

Op::Rebalanced { k, v, l, r, freed } => {

[4.35183]

[4.35233]

Op::Rebalanced {
k,
v,
l,
r,
freed,
incr_kv_rc,
} => {
edit in sanakirja-core/src/btree/del.rs at line 345

[4.35444]

[4.35444]

if incr_kv_rc {
// Here, note that the rebalancing element cannot
// possibly be the replacement element, so since it is
// copied, we need to increment its RC (the
// replacement entry has its RC incremented at
// deletion).
for o in k.page_offsets().chain(v.page_offsets()) {
txn.incr_rc(o)?;
}
}
edit in sanakirja-core/src/btree/del.rs at line 362

[4.2185]

[4.3165]

// We have already incremented the references of the
// replacement at the leaf.
replacement in sanakirja-core/src/btree/del.rs at line 389

[4.36543]→[4.2186:2226](∅→∅)

if cursor.pointer() == p0 {

[4.36543]

[4.36581]

let split_key_is_k0 = if cursor.pointer() == p0 {
replacement in sanakirja-core/src/btree/del.rs at line 396

[4.3432]→[4.36817:36879](∅→∅),[4.20320]→[4.36817:36879](∅→∅),[4.36817]→[4.36817:36879](∅→∅)

last_op.ins2 = Some((split_key, split_value))

[4.3432]

[4.36879]

last_op.ins2 = Some((split_key, split_value));
false
replacement in sanakirja-core/src/btree/del.rs at line 400

[4.36962]→[4.36962:37019](∅→∅)

last_op.skip_first = false
}

[4.36962]

[4.37019]

last_op.skip_first = false;
// If the split key is the replacement element, we have
// already increased its counter when we deleted it from
// its original position at the bottom of the tree.
//
// This can happen if we replaced an element and that
// replacement caused a split with the replacement as the
// middle element.
if let Some(k0v0) = k0v0 {
assert!(cursor.pointer() < p0);
let (k0, _) = unsafe { P::from_saved(k0v0) };
core::ptr::eq(k0, split_key)
} else {
false
}
};
edit in sanakirja-core/src/btree/del.rs at line 420

[4.37212]→[4.37212:37595](∅→∅),[4.37595]→[4.3433:3556](∅→∅),[4.3556]→[4.20385:20503](∅→∅),[4.20385]→[4.20385:20503](∅→∅)

// If the split key is the replacement element, we have
// already increased its counter when we deleted it from
// its original position at the bottom of the tree.
//
// This can happen if we replaced an element and that
// replacement caused a split with the replacement as the
// middle element.
let split_key_is_k0 = if let Some(k0v0) = k0v0 {
let (k0, _) = unsafe { P::from_saved(k0v0) };
(k0 as *const K) == (split_key as *const K)
} else {
false
};
edit in sanakirja-core/src/btree/del.rs at line 433

[3.110]

[4.2311]

// Free the page(s) at level `cursor.pointer() + 1` if it isn't
// shared with another tree, or if it is the first level shared
// with another tree.
replacement in sanakirja-core/src/btree/del.rs at line 437

[4.2361]→[3.111:151](∅→∅)

free[cursor.pointer()] = freed;

[4.2361]

[4.62825]

free[cursor.pointer() + 1] = freed;
edit in sanakirja-core/src/btree/del.rs at line 439

[4.62831]→[4.2402:2474](∅→∅)

modify_rc(txn, &last_op, cursor.pointer(), cursor.first_rc_level)?;
edit in sanakirja-core/src/btree/del.rs at line 457

[4.63036]→[4.20992:21065](∅→∅)

if p == first_rc_level {
txn.decr_rc(m.page.offset)?;
}
edit in sanakirja-core/src/btree/del.rs at line 460

[4.33576]→[4.21066:21091](∅→∅)

assert_ne!(left, 0);
replacement in sanakirja-core/src/btree/del.rs at line 465

[4.21309]→[4.21309:21374](∅→∅)

assert_ne!(left, 0);
txn.incr_rc(left)?;

[4.21309]

[4.21374]

if left != 0 {
txn.incr_rc(left)?;
}
replacement in sanakirja-core/src/btree/del.rs at line 470

[4.63351]→[4.63351:63357](∅→∅),[4.63357]→[4.21397:22199](∅→∅),[4.22199]→[4.63460:63466](∅→∅),[4.63460]→[4.63460:63466](∅→∅),[4.63466]→[4.22200:22229](∅→∅)

}
// The insertions come from pages strictly below the page at
// cursor.pointer, so if `incr_ins`, we increment them here,
// except the replacement, already incremented in `leaf_delete`
// above
if p + 1 >= first_rc_level {
if let Some((k, v)) = m.ins {
// If this is the replacement, it has already been
// incremented in `leaf_delete`, so we don't need to
// increment it again.
if m.skip_first {
for o in k.page_offsets().chain(v.page_offsets()) {
txn.incr_rc(o)?;
}
}
if let Some((k, v)) = m.ins2 {
for o in k.page_offsets().chain(v.page_offsets()) {
txn.incr_rc(o)?;
}
}
}
}
if p >= first_rc_level {

[4.63305]

[4.22229]

// The insertions are taken care of in `handle_merge` above,
// so we can directly move to the `c1` part of the
// modification.
replacement in sanakirja-core/src/btree/del.rs at line 479

[4.22450]→[4.22450:22515](∅→∅)

assert_ne!(left, 0);
txn.incr_rc(left)?;

[4.22450]

[4.22515]

if left != 0 {
txn.incr_rc(left)?;
}
replacement in sanakirja-core/src/btree/del.rs at line 484

[4.22526]→[4.22526:22705](∅→∅)

// Moving on to the first non-deleted element of `c1`: if we
// are not updating the right child of the first element,
// increment that right child's RC.

[4.22526]

[4.22705]

// If we are not updating the right child of the first
// element of `c1`, increment that right child's RC.
replacement in sanakirja-core/src/btree/del.rs at line 490

[4.22891]→[4.22891:22951](∅→∅)

if m.r == 0 {
assert_ne!(r, 0);

[4.22891]

[4.22951]

if m.r == 0 && r != 0 {
edit in sanakirja-core/src/btree/del.rs at line 500

[4.23290]→[4.23290:23324](∅→∅)

assert_ne!(r, 0);
replacement in sanakirja-core/src/btree/del.rs at line 528

[2.6508]→[2.6508:6748](∅→∅)

if !is_rc {
if P::is_dirty(last_op.page.as_page()) {
txn.decr_rc_owned(last_op.page.offset)?;
} else {
txn.decr_rc(last_op.page.offset)?;
}

[2.6508]

[2.6748]

if P::is_dirty(last_op.page.as_page()) {
txn.decr_rc_owned(last_op.page.offset)?;
} else {
txn.decr_rc(last_op.page.offset)?;
replacement in sanakirja-core/src/btree/del.rs at line 549

[4.24052]→[4.24052:24095](∅→∅),[4.24095]→[4.38597:38633](∅→∅),[4.38597]→[4.38597:38633](∅→∅)

// Else, we execute the last operation
debug!("modify {:?}", last_op);

[4.24052]

[4.38633]

// Else, the last operation `last_op` was relative to the root,
// but it hasn't been applied yet. We apply it now:
replacement in sanakirja-core/src/btree/del.rs at line 552

[4.38675]→[3.152:211](∅→∅)

Put::Ok(Ok { page, .. }) => db.db = page.0.offset,

[4.38675]

[4.38785]

Put::Ok(Ok { page, freed }) => {
free[0][0] = freed;
db.db = page.0.offset
}
replacement in sanakirja-core/src/btree/del.rs at line 557

[4.38806]→[4.38806:38891](∅→∅),[4.38891]→[3.212:227](∅→∅)

split_key,
split_value,
left,
right,
..

[4.38806]

[4.38910]

split_key: k,
split_value: v,
left: l,
right: r,
freed,
edit in sanakirja-core/src/btree/del.rs at line 563

[4.38925]

[4.38957]

free[0][0] = freed;
replacement in sanakirja-core/src/btree/del.rs at line 568

[4.10738]→[4.39035:39122](∅→∅),[4.39035]→[4.39035:39122](∅→∅),[4.39122]→[4.10739:10759](∅→∅),[4.10759]→[4.39174:39331](∅→∅),[4.39174]→[4.39174:39331](∅→∅)

P::put(
txn,
page.0,
true,
&c,
split_key,
split_value,
None,
left.0.offset,
right.0.offset,
)?;

[4.10738]

[4.3820]

P::put(txn, page.0, true, &c, k, v, None, l.0.offset, r.0.offset)?;
replacement in sanakirja-core/src/btree/del.rs at line 571

[4.3947]→[4.24160:24220](∅→∅),[4.24160]→[4.24160:24220](∅→∅)

(k0 as *const K) == (split_key as *const K)

[4.3947]

[4.24220]

(k0 as *const K) == (k as *const K)
replacement in sanakirja-core/src/btree/del.rs at line 576

[4.24321]→[4.39396:39482](∅→∅),[4.39396]→[4.39396:39482](∅→∅)

for o in split_key.page_offsets().chain(split_value.page_offsets()) {

[4.24321]

[4.39482]

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