Debugging

[?]

Mar 2, 2021, 5:16 PM

DASFQGORX56YK5E4Y7GGYZSQQQMUXYTZZ4A6IVWSTI3QGRUORLPAC

Dependencies

[2] ACB4A27Z Code coverage
[3] QDTOA3CQ Forgot a file
[4] 6BG65Y2P Cursor::set_last was panicking on empty pages
[5] PRDUE4YA Cleanup + published on crates.io
[6] 5LSYTRQ6 More docs, example, and fixing the free page diagnostic function for mutable transactions
[7] DEKK3RUI Fixing a bug when splitting unsized pages
[8] PPI5ZTZP Rebalance: put can free pages without splitting (compaction)
[9] QEUTVAZ4 Splitting btree::page
[10] RV2L6CZW A few comments
[11] H3FVSQIQ Unsized pages
[12] 6UVFCERM Formatting, debugging, etc.
[13] QYDGYIZR Split trait Representable into its mandatory part and an optional part
[14] CCNPHVQC Cleanup, comments, renaming
[15] UUUVNC4D Debugging/cleanup around cursors
[16] LROAI3NB Two iterators (convenience functions), along with tests to move cursors (put and del still destroy cursors though)
[17] FMN7X4J2 Micro-improvements, now noticeably faster than std::collections::BTreeMap
[18] TSMS6W4D Fully commented implementation of Sized nodes + massive cleanup
[19] W2MIZD5B Single file databases + CRC for the root pages (checking the other pages makes everything very slow)
[20] E4MD6T3L Proofreading and commenting of this crate (massive bug fixes included)
[21] 52X5P7ND Cleaning up the unsized part
[22] ONES3V46 reference counting works for put
[23] L5CVF6UJ Debugging
[24] 6DCQHIFP Minor changes after benchmarking
[25] 6DMPXOAT More debugging
[26] OTWDDJE7 Trait/type cleanup
[27] KX3WVNZW Testing/debugging "rebalance causes split of the root"
[28] 73Z2UB3J Cleanup + comments
[29] YWFYZNLZ Cleanup + inter-process concurrency
[30] LSQ6V7M6 Cleanup + docs
[31] OHUZ73MK Versions
[32] HN6Z5DU4 Cleanup
[33] T7QB6QEP Adding debug.rs
[34] OP6SVMOD Resetting history
[35] WS4ZQM4R Debugging, tests, etc.
[36] S4V4QZ5C Debugging reference-counting for put
[37] X3QVVQIS More debugging (del seems to work now)
[38] YXKP4AIW New file locks, with multiple sets of free pages
[39] GPP7KJSF Version bump
[40] UAQX27N4 Tests
[41] FZBLNBGN Diagnostic tools (add_refs, check_free) + cleanup
[42] T73WR2BX Cleaner RC increments for keys and values containing references + more comments in `del`
[43] DV4A2LR7 Double-inserts (rebalancing near an internal deletion)
[44] EAAYH6BQ Debugging put
[45] ESUI5EUZ Making as_page() unsafe
[46] W26CFMAQ Improving safety of cursors
[47] OFINGD26 implementing prev() on cursors (+ some cleanup)
[48] PXF3R6SV Improving test coverage for btree::cursor
[49] XEU2QVLC Debugging after plugging this into Pijul
[50] APPY2E7M Unsized deletions + custom sizes back

Change contents

file move: sanakirja-core (dxwrx-rx-r) → sanakirja-core (d--r------)

[1.0]

[9.17]
file move: src (dxwrx-rx-r) → src (d--r------)

[9.17]

[9.24]
file move: main.rs (-xw-x--x--) → main.rs (----------)

[9.24]

[9.35]
file move: lib.rs (-xw-x--x--) → lib.rs (----------)

[9.24]

[9.91]
file move: btree (dxwrx-rx-r) → btree (d--r------)

[9.24]

[9.3438]
file move: put.rs (-xw-x--x--) → put.rs (----------)

[9.3438]

[9.3448]
edit in sanakirja-core/src/btree/put.rs at line 4

[9.3963]→[9.106:107](∅→∅)
edit in sanakirja-core/src/btree/put.rs at line 109

[9.5205]→[9.147:175](∅→∅)

let mut last_freed = 0;
replacement in sanakirja-core/src/btree/put.rs at line 123

[9.1603]→[9.1603:1695](∅→∅)

incr_descendants::<T, K, V, P>(txn, cursor, free, freed, &mut last_freed)?;

[9.1603]

[9.1696]

incr_descendants::<T, K, V, P>(txn, cursor, free, freed)?;
replacement in sanakirja-core/src/btree/put.rs at line 142

[9.484]→[9.484:507](∅→∅)

)?

[9.484]

[9.507]

)?;
replacement in sanakirja-core/src/btree/put.rs at line 172

[9.2230]→[9.2230:2323](∅→∅)

incr_descendants::<T, K, V, P>(txn, cursor, free, freed, &mut last_freed)?;

[9.2230]

[9.2323]

incr_descendants::<T, K, V, P>(txn, cursor, free, freed)?;
replacement in sanakirja-core/src/btree/put.rs at line 207

[9.7656]→[9.7656:7672](∅→∅),[9.7672]→[9.2866:2892](∅→∅)

freed: u64,
last_freed: &mut u64,

[9.7656]

[9.7672]

mut freed: u64,
edit in sanakirja-core/src/btree/put.rs at line 209

[9.7700]

[9.872]

// The freed page is on the page below.
edit in sanakirja-core/src/btree/put.rs at line 216

[9.7865]→[9.3054:3172](∅→∅),[9.3172]→[9.919:970](∅→∅),[9.176]→[9.7918:7958](∅→∅),[9.505]→[9.7918:7958](∅→∅),[9.705]→[9.7918:7958](∅→∅),[9.970]→[9.7918:7958](∅→∅),[9.3117]→[9.7918:7958](∅→∅),[9.7918]→[9.7918:7958](∅→∅),[9.7958]→[9.3118:3158](∅→∅),[9.550]→[9.8113:8123](∅→∅),[9.748]→[9.8113:8123](∅→∅),[9.3158]→[9.8113:8123](∅→∅),[9.8113]→[9.8113:8123](∅→∅)

// Else, the "freed" page is shared with another tree, and
// hence we just need to decrement its RC.
if cursor.len() == cursor.first_rc_len() {
debug_assert_ne!(freed, 0);
free[cursor.len()] = freed;
}
replacement in sanakirja-core/src/btree/put.rs at line 220

[9.798]→[9.8123:8159](∅→∅),[9.3422]→[9.8123:8159](∅→∅),[9.8123]→[9.8123:8159](∅→∅)

let cur = cursor.current();

[9.3422]

[9.3423]

let cur = cursor.cur();
replacement in sanakirja-core/src/btree/put.rs at line 227

[9.173]→[9.3668:3714](∅→∅),[9.3217]→[9.3668:3714](∅→∅),[9.1125]→[9.3668:3714](∅→∅),[9.883]→[9.8290:8322](∅→∅),[9.3714]→[9.8290:8322](∅→∅),[9.8290]→[9.8290:8322](∅→∅)

if left != 0 && left != *last_freed {
txn.incr_rc(left)?;

[9.3217]

[9.8322]

if left != 0 {
if left != (freed & !1) {
txn.incr_rc(left)?;
} else if cursor.len() == cursor.first_rc_len() {
freed = 0
}
replacement in sanakirja-core/src/btree/put.rs at line 241

[9.8508]→[9.3888:3932](∅→∅),[9.967]→[9.8536:8569](∅→∅),[9.3932]→[9.8536:8569](∅→∅),[9.8536]→[9.8536:8569](∅→∅)

if r != 0 && r != *last_freed {
txn.incr_rc(r)?;

[9.8508]

[9.8569]

if r != 0 {
if r != (freed & !1) {
txn.incr_rc(r)?;
} else if cursor.len() == cursor.first_rc_len() {
freed = 0
}
edit in sanakirja-core/src/btree/put.rs at line 248

[9.8583]

[9.8583]

}
// Else, the "freed" page is shared with another tree, and
// hence we just need to decrement its RC.
if freed > 0 && cursor.len() == cursor.first_rc_len() {
free[cursor.len()] = freed;
edit in sanakirja-core/src/btree/put.rs at line 255

[9.8599]→[9.3933:4262](∅→∅)

// Finally, update the last freed page to be the page we just
// freed (the `&!1` is here because `freed` might have its LSB set
// to indicate that `freed` was allocated by the current
// transaction, but that bit isn't set in references to page
// `freed` on the parent page).
*last_freed = freed & !1;
file move: page_unsized.rs (-xw-x--x--) → page_unsized.rs (----------)

[9.3438]

[9.2014]
replacement in sanakirja-core/src/btree/page_unsized.rs at line 143

[9.4407]→[9.4407:4507](∅→∅)

unsafe { *(page.data.as_ptr().add((HDR + c.cur as usize * 8) - 8) as *const u64) };

[9.4407]

[9.4507]

unsafe { *(page.data.as_ptr().offset(HDR as isize + c.cur * 8 - 8) as *const u64) };
replacement in sanakirja-core/src/btree/page_unsized.rs at line 153

[9.4811]→[9.4811:4911](∅→∅)

let off = unsafe { *(page.data.as_ptr().add(HDR + c.cur as usize * 8) as *const u64) };

[9.4811]

[9.4911]

let off = unsafe { *(page.data.as_ptr().offset(HDR as isize + c.cur * 8) as *const u64) };
edit in sanakirja-core/src/btree/page_unsized.rs at line 632

[9.17973]

[9.3472]

fn set_left_child(new: &mut MutPage, n: isize, l: u64);
edit in sanakirja-core/src/btree/page_unsized.rs at line 642

[9.19232]→[9.18173:18267](∅→∅)

// This is the exact same implementation as in the sized
// module. I'm not convinced
edit in sanakirja-core/src/btree/page_unsized.rs at line 665

[9.20056]

[9.20056]

if l != 0 {
// The while loop above didn't run, i.e. the insertion
// happened at the end of the page. In this case, we haven't
// had a chance to update the left page, so do it now.
L::set_left_child(new, *n, l)
}
replacement in sanakirja-core/src/btree/page_unsized.rs at line 685

[9.19079]→[9.19079:19413](∅→∅)

// This algorithm is probably a bit naive, especially for leaves,
// where if the left page is mutable, we can copy the other page
// onto it.

// Indeed, we first allocate a page, then clone both pages onto
// it, in a different order depending on whether the modified page
// is the left or the right child.

[9.19079]

[9.19413]

// Here, we first allocate a page, then clone both pages onto it,
// in a different order depending on whether the modified page is
// the left or the right child.
//
// Note that in the case that this merge happens immediately after
// a put that reallocated the two sides of the merge in order to
// split (not all splits do that), we could be slightly more
// efficient, but with considerably more code.
file move: page_unsized (dxwrx-rx-r) → page_unsized (d--r------)

[9.3438]

[9.22910]
file move: rebalance.rs (-xw-x--x--) → rebalance.rs (----------)

[9.22910]

[9.22926]
edit in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 79

[9.994]

[9.1166]
replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 84

[9.1414]→[9.1414:1565](∅→∅)

if let Put::Ok(Ok { freed, page }) = <Page<K, V>>::put(
txn, page.0, true, false, &lc, m.mid.0, m.mid.1, None, 0, rl,
)? {

[9.1414]

[8.135]

if let Put::Ok(Ok { freed, page }) =
<Page<K, V>>::put(txn, page.0, true, false, &lc, m.mid.0, m.mid.1, None, 0, rl)?
{
edit in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 95

[9.1670]→[9.1670:1671](∅→∅)
replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 102

[9.2044]→[9.2044:2141](∅→∅)

txn, m.modified.page, m.modified.mutable, false, &lc, m.mid.0, m.mid.1, None, 0, rl,

[9.2044]

[9.2141]

txn,
m.modified.page,
m.modified.mutable,
false,
&lc,
m.mid.0,
m.mid.1,
None,
0,
rl,
edit in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 113

[9.2154]

[9.2154]

if m.modified.l > 0 {
assert_eq!(m.modified.r, 0);
unsafe {
let off = (page.0.data.add(HDR) as *mut u64).offset(m.modified.c1.cur - 1);
*off = (m.modified.l | (u64::from_le(*off) & 0xfff)).to_le();
}
} else if m.modified.r > 0 {
unsafe {
let off = (page.0.data.add(HDR) as *mut u64).offset(m.modified.c1.cur);
*off = (m.modified.r | (u64::from_le(*off) & 0xfff)).to_le();
}
}
edit in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 153

[9.22673]→[9.0:41](∅→∅),[9.24945]→[9.0:41](∅→∅)

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

[9.23054]→[9.23054:23148](∅→∅)

pub(crate) fn rebalance_right<'a, T: AllocPage, K: ?Sized, V: ?Sized, P: BTreeMutPage<K, V>>(

[9.23054]

[9.25144]

pub(crate) fn rebalance_right<
'a,
T: AllocPage,
K: ?Sized,
V: ?Sized,
P: BTreeMutPage<K, V, Cursor = super::PageCursor>,
>(
edit in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 182

[9.2032]→[9.25475:25516](∅→∅),[9.4746]→[9.25475:25516](∅→∅),[9.5676]→[9.25475:25516](∅→∅),[9.23290]→[9.25475:25516](∅→∅),[9.25475]→[9.25475:25516](∅→∅),[9.25516]→[9.23291:23399](∅→∅)

// First element of the right page.
let rc = P::cursor_first(&m.modified.page);
let rl = P::left_child(m.modified.page.as_page(), &rc);
edit in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 211

[9.2837]

[9.2837]

// First element of the right page (after potential
// modification by `put` above).
let rc = P::cursor_first(&new_right.0);
let rl = P::left_child(new_right.0.as_page(), &rc);
replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 247

[9.3303]→[9.3303:3395](∅→∅)

// mutable, since we just modified it (hence the
// `assert_eq!(freed, 0)`.

[9.3303]

[9.3395]

// mutable, since we just modified it. Moreover, if it is
// compacted by the `put` below, we know that the `del` didn't
// free anything, hence we can reuse the slot 0..

// First element of the right page (after potential
// modification by `del` above).
let rc = P::cursor_first(&page.0);
let rl = P::left_child(page.0.as_page(), &rc);
replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 256

[9.3448]→[9.3448:3631](∅→∅)

txn,
page.0,
true,
false,
&rc,
m.mid.0,
m.mid.1,
None,
r0,
rl,

[9.3448]

[9.3631]

txn, page.0, true, false, &rc, m.mid.0, m.mid.1, None, r0, rl,
replacement in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 258

[9.3644]→[9.3644:3684](∅→∅)

debug_assert_eq!(freed, 0);

[9.3644]

[9.3684]

if freed > 0 {
freed_[0] = if is_dirty { freed | 1 } else { freed };
}
edit in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 267

[9.3807]

[9.3807]

let rc = P::cursor_first(&m.modified.page);
let rl = P::left_child(m.modified.page.as_page(), &rc);
edit in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 281

[9.4079]

[9.4079]

// Update the left and right offsets. We know that at
// least one of them is 0, but it can be either one (or
// both), depending on what happened on the page below.
//
// Since we inserted an entry at the beginning of the
// page, we need to add 1 to the index given by
// `m.modified.c1.cur`.
if m.modified.l > 0 {
assert_eq!(m.modified.r, 0);
unsafe {
let off = (page.0.data.add(HDR) as *mut u64).offset(m.modified.c1.cur);
*off = (m.modified.l | (u64::from_le(*off) & 0xfff)).to_le();
}
} else if m.modified.r > 0 {
unsafe {
let off = (page.0.data.add(HDR) as *mut u64).offset(m.modified.c1.cur + 1);
*off = (m.modified.r | (u64::from_le(*off) & 0xfff)).to_le();
}
}
edit in sanakirja-core/src/btree/page_unsized/rebalance.rs at line 325

[9.6322]→[9.42:83](∅→∅),[9.26989]→[9.42:83](∅→∅)

incr_kv_rc: !m.modified.mutable,
file move: put.rs (-xw-x--x--) → put.rs (----------)

[9.22910]

[9.27023]
file move: header.rs (-xw-x--x--) → header.rs (----------)

[9.22910]

[9.15503]
file move: cursor.rs (-xw-x--x--) → cursor.rs (----------)

[9.22910]

[3.12]
file move: alloc.rs (-xw-x--x--) → alloc.rs (----------)

[9.22910]

[9.33822]
edit in sanakirja-core/src/btree/page_unsized/alloc.rs at line 184

[9.35633]

[9.35633]

}
fn set_left_child(_new: &mut MutPage, _n: isize, l: u64) {
debug_assert_eq!(l, 0);
edit in sanakirja-core/src/btree/page_unsized/alloc.rs at line 193

[9.35880]

[9.35880]

}
fn set_left_child(new: &mut MutPage, n: isize, l: u64) {
if l > 0 {
Internal::set_right_child(new, n - 1, l);
}
file move: page.rs (-xw-x--x--) → page.rs (----------)

[9.3438]

[9.8623]
edit in sanakirja-core/src/btree/page.rs at line 200

[9.7655]→[9.7655:7656](∅→∅)
replacement in sanakirja-core/src/btree/page.rs at line 665

[9.4687]→[9.18538:18616](∅→∅)

assert!(off as usize + core::mem::size_of::<Tuple<K, V>>() <= PAGE_SIZE);

[9.4687]

[9.18616]

if off as usize + core::mem::size_of::<Tuple<K, V>>() > PAGE_SIZE {
panic!("off = {:?}, size = {:?}", off, core::mem::size_of::<Tuple<K, V>>());
}
replacement in sanakirja-core/src/btree/page.rs at line 775

[9.8856]→[9.6982:7039](∅→∅)

let a = core::mem::size_of::<Tuple<K, V>>();

[9.8856]

[9.39520]

let a = core::mem::align_of::<Tuple<K, V>>();
file move: page (dxwrx-rx-r) → page (d--r------)

[9.3438]

[9.371]
file move: rebalance.rs (-xw-x--x--) → rebalance.rs (----------)

[9.371]

[9.387]
edit in sanakirja-core/src/btree/page/rebalance.rs at line 68

[9.5415]

[9.9205]

// Looking at module `super::del`, the only way we can be in
// this case
edit in sanakirja-core/src/btree/page/rebalance.rs at line 107

[9.6200]

[9.6200]

if m.modified.l > 0 {
assert_eq!(m.modified.r, 0);
unsafe {
let off = (page.0.data.add(HDR) as *mut u64).offset(m.modified.c1.cur - 1);
*off = (m.modified.l | (u64::from_le(*off) & 0xfff)).to_le();
}
} else if m.modified.r > 0 {
unsafe {
let off = (page.0.data.add(HDR) as *mut u64).offset(m.modified.c1.cur);
*off = (m.modified.r | (u64::from_le(*off) & 0xfff)).to_le();
}
}
edit in sanakirja-core/src/btree/page/rebalance.rs at line 190

[9.9826]→[9.84:125](∅→∅),[9.3846]→[9.84:125](∅→∅)

incr_kv_rc: !m.other_is_mutable,
file move: put.rs (-xw-x--x--) → put.rs (----------)

[9.371]

[9.5929]
edit in sanakirja-core/src/btree/page/put.rs at line 161

[9.10040]

[9.10092]

<Page<K, V> as BTreeMutPage<K, V>>::init(&mut left);
edit in sanakirja-core/src/btree/page/put.rs at line 163

[9.10119]

[9.12021]

L::set_right_child(&mut left, -1, hdr.left_page() & !0xfff);
file move: alloc.rs (-xw-x--x--) → alloc.rs (----------)

[9.371]

[9.17232]
edit in sanakirja-core/src/btree/page/alloc.rs at line 308

[9.43967]

[9.43967]

}
fn set_left_child(new: &mut MutPage, n: isize, l: u64) {
if l > 0 {
Internal::set_right_child(new, n - 1, l);
}
edit in sanakirja-core/src/btree/page/alloc.rs at line 319

[9.44206]

[9.44206]

}
fn set_left_child(_new: &mut MutPage, _n: isize, l: u64) {
debug_assert_eq!(l, 0);
file move: mod.rs (-xw-x--x--) → mod.rs (----------)

[9.3438]

[9.45735]
file move: del.rs (-xw-x--x--) → del.rs (----------)

[9.3438]

[9.52511]
edit in sanakirja-core/src/btree/del.rs at line 23

[9.35374]→[9.35374:35469](∅→∅)

// Do `k` and `v` come from a page shared with another tree?
incr_kv_rc: bool,
replacement in sanakirja-core/src/btree/del.rs at line 80

[9.31281]→[9.11700:11745](∅→∅)

K: Storable + ?Sized + core::fmt::Debug,

[9.31281]

[9.11745]

K: Storable + ?Sized + core::fmt::Debug + PartialEq,
replacement in sanakirja-core/src/btree/del.rs at line 107

[9.31418]→[9.11791:11836](∅→∅)

K: Storable + ?Sized + core::fmt::Debug,

[9.31418]

[9.11836]

K: Storable + ?Sized + core::fmt::Debug + PartialEq,
replacement in sanakirja-core/src/btree/del.rs at line 127

[9.1094]→[9.16469:16509](∅→∅),[9.9668]→[9.16469:16509](∅→∅),[9.16469]→[9.16469:16509](∅→∅)

let cur = cursor.current();

[9.9668]

[9.13566]

let cur = cursor.cur();
replacement in sanakirja-core/src/btree/del.rs at line 137

[9.594]→[9.7962:7994](∅→∅)

let cur = cursor.current();

[9.594]

[9.37470]

let cur = cursor.cur();
edit in sanakirja-core/src/btree/del.rs at line 168

[9.14600]

[9.17538]

let incr_page = if !concat.other_is_mutable {
Some(CowPage {
offset: concat.other.offset,
data: concat.other.data,
})
} else {
None
};
let incr_mid = if cursor.len() >= cursor.first_rc_len() {
Some(concat.mid)
} else {
None
};
edit in sanakirja-core/src/btree/del.rs at line 189

[9.14975]→[9.17625:17626](∅→∅),[9.7002]→[9.17625:17626](∅→∅)
replacement in sanakirja-core/src/btree/del.rs at line 191

[9.15103]→[9.2511:2591](∅→∅),[9.31025]→[9.2511:2591](∅→∅),[9.2591]→[9.1201:1202](∅→∅)

last_op = handle_merge(txn, cursor, p0, &k0v0, mil, merge, &mut free)?;

[9.15103]

[9.8567]

last_op = handle_merge(txn, cursor, p0, &k0v0, incr_page, incr_mid, mil, merge, &mut free)?;
replacement in sanakirja-core/src/btree/del.rs at line 228

[9.31559]→[9.31559:31607](∅→∅),[9.31607]→[9.11882:11972](∅→∅),[9.2755]→[9.18370:18421](∅→∅),[9.11972]→[9.18370:18421](∅→∅),[9.18370]→[9.18370:18421](∅→∅)

T: AllocPage + LoadPage + core::fmt::Debug,
K: Storable + ?Sized + core::fmt::Debug,
V: Storable + ?Sized + core::fmt::Debug,
P: BTreeMutPage<K, V> + core::fmt::Debug + 'a,

[9.31559]

[9.31744]

T: AllocPage + LoadPage,
K: Storable + ?Sized,
V: Storable + ?Sized,
P: BTreeMutPage<K, V> + 'a,
edit in sanakirja-core/src/btree/del.rs at line 241

[9.11699]→[9.1714:1715](∅→∅),[9.9998]→[9.1714:1715](∅→∅)
replacement in sanakirja-core/src/btree/del.rs at line 361

[9.34015]→[9.12026:12052](∅→∅)

K: Storable + ?Sized,

[9.34015]

[9.12052]

K: Storable + ?Sized + PartialEq,
replacement in sanakirja-core/src/btree/del.rs at line 363

[9.3134]→[9.20078:20124](∅→∅),[9.12078]→[9.20078:20124](∅→∅),[9.20078]→[9.20078:20124](∅→∅)

P: BTreeMutPage<K, V> + core::fmt::Debug,

[9.12078]

[9.34114]

P: BTreeMutPage<K, V>,
edit in sanakirja-core/src/btree/del.rs at line 369

[9.3164]

[9.34236]

incr_other: Option<CowPage>,
incr_mid: Option<(&K, &V)>,
edit in sanakirja-core/src/btree/del.rs at line 393

[9.34844]

[9.4540]

// For merges and rebalances, take care of the reference counts of
// pages and key/values.
match merge {
Op::Merged {.. } | Op::Rebalanced { .. } => {
// Increase the RC of the "other page's" descendants. In
// the case of a rebalance, this has the effect of
// increasing the RC of the new middle entry if that entry
// comes from a shared page, which is what we want.
if let Some(other) = incr_other {
let mut curs = P::cursor_first(&other);
let left = P::left_child(other.as_page(), &curs);
txn.incr_rc(left)?;
while let Some((k0, v0, r)) = P::next(txn, other.as_page(), &mut curs) {
for o in k0.page_references().chain(v0.page_references()) {
txn.incr_rc(o)?;
}
if r != 0 {
txn.incr_rc(r)?;
}
}
}

// If the middle element comes from a shared page,
// increment its references.
if let Some((ref k, ref v)) = incr_mid {
for o in k.page_references().chain(v.page_references()) {
txn.incr_rc(o)?;
}
}
}
_ => {}
}
edit in sanakirja-core/src/btree/del.rs at line 449

[9.4868]→[9.4868:4892](∅→∅)

incr_kv_rc,
edit in sanakirja-core/src/btree/del.rs at line 455

[9.35444]→[9.4908:5226](∅→∅),[9.5226]→[9.3565:3639](∅→∅),[9.3639]→[9.5294:5363](∅→∅),[9.5294]→[9.5294:5363](∅→∅)

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_references().chain(v.page_references()) {
txn.incr_rc(o)?;
}
}
replacement in sanakirja-core/src/btree/del.rs at line 589

[9.23008]→[9.10800:10832](∅→∅)

if m.r == 0 && r != 0 {

[9.23008]

[9.10832]

// If `m.skip_first`, we have already skipped the entry above,
// so this `r` has nothing to do with any update.
//
// Else, if we aren't skipping, but also aren't updating the
// right child of the current entry, also increase the RC.
if (m.skip_first || m.r == 0) && r != 0 {
file move: cursor.rs (-xw-x--x--) → cursor.rs (----------)

[9.3438]

[9.63682]
replacement in sanakirja-core/src/btree/cursor.rs at line 36

[9.65195]→[9.6965:7049](∅→∅)

impl<K: ?Sized + core::fmt::Debug, V: ?Sized, P: BTreePage<K, V>> Cursor<K, V, P> {

[9.65195]

[9.38975]

impl<K: ?Sized + Storable, V: ?Sized + Storable, P: BTreePage<K, V>> Cursor<K, V, P> {
replacement in sanakirja-core/src/btree/cursor.rs at line 92

[9.12677]→[9.7485:7544](∅→∅),[9.11210]→[9.7485:7544](∅→∅)

pub(super) fn current(&self) -> &PageCursor<K, V, P> {

[9.65654]

[9.18376]

pub(super) fn cur(&self) -> &PageCursor<K, V, P> {
replacement in sanakirja-core/src/btree/cursor.rs at line 204

[9.11288]→[9.11288:11340](∅→∅),[9.67858]→[9.67858:67886](∅→∅)

) -> Result<Option<(&'a K, &'a V)>, T::Error> {
let mut last_match;

[9.11288]

[9.19537]

) -> Result<(), T::Error> {
replacement in sanakirja-core/src/btree/cursor.rs at line 207

[9.19637]→[9.15527:15583](∅→∅),[9.11427]→[9.15527:15583](∅→∅)

current.cursor = P::cursor_last(&current.page);

[9.19637]

[9.67886]

current.cursor = P::cursor_after(&current.page);
edit in sanakirja-core/src/btree/cursor.rs at line 212

[9.19850]

[9.68121]

}
let l = P::left_child(current.page.as_page(), &current.cursor);
if l > 0 {
let page = txn.load_page(l)?;
self.push(PageCursor {
cursor: P::cursor_after(&page),
page,
})
} else {
break;
replacement in sanakirja-core/src/btree/cursor.rs at line 223

[9.68135]→[4.0:423](∅→∅)

if let Some((k, v, r)) = P::current(txn, current.page.as_page(), &mut current.cursor) {
last_match = Some((k, v));
if r > 0 {
let page = txn.load_page(r)?;
self.push(PageCursor {
cursor: P::cursor_last(&page),
page,
})
} else {
break;

[9.68135]

[4.423]

}
Ok(())
}

/// Return the current position of the cursor.
pub fn current<'a, T: LoadPage>(
&mut self,
txn: &'a T,
) -> Result<Option<(&'a K, &'a V)>, T::Error> {
loop {
let current = unsafe { &mut *self.stack[self.len - 1].as_mut_ptr() };
if P::is_init(&current.cursor) {
// The cursor hasn't been set.
return Ok(None)
} else if let Some((k, v, _)) = P::current(txn, current.page.as_page(), &current.cursor)
{
unsafe {
return Ok(Some((core::mem::transmute(k), core::mem::transmute(v))));
edit in sanakirja-core/src/btree/cursor.rs at line 242

[4.441]

[9.68672]

} else if self.len > 1 {
self.len -= 1
replacement in sanakirja-core/src/btree/cursor.rs at line 245

[9.68693]→[4.442:820](∅→∅)

// The page is empty, meaning there's no right or left child.
debug_assert!(P::is_init(&current.cursor));
// Assert we're looking at the root.
debug_assert_eq!(self.len, 1);
// And the root has no child.
debug_assert_eq!(P::right_child(current.page.as_page(), &current.cursor), 0);

[9.68693]

[4.820]

// We're past the last element at the root.
edit in sanakirja-core/src/btree/cursor.rs at line 249

[9.68740]→[9.35119:35218](∅→∅)

Ok(last_match.map(|(k, v)| unsafe { (core::mem::transmute(k), core::mem::transmute(v)) }))
replacement in sanakirja-core/src/btree/cursor.rs at line 291

[9.13211]→[9.41177:41255](∅→∅)

/// Move the cursor to the previous entry, and return that
/// entry.

[9.13211]

[9.41255]

/// Move the cursor to the previous entry, and return the current
/// entry. If the cursor is initially after all the entries, this
/// moves it back by two steps.
edit in sanakirja-core/src/btree/cursor.rs at line 309

[9.2716]

[9.13461]

// We are at a leaf.
file move: Cargo.toml (-xw-x--x--) → Cargo.toml (----------)

[9.17]

[9.70777]
replacement in sanakirja-core/Cargo.toml at line 3

[9.70812]→[7.55:73](∅→∅)

version = "1.0.2"

[9.70812]

[9.70847]

version = "1.1.0"
replacement in sanakirja-core/Cargo.toml at line 38

[9.1892]→[9.1892:1966](∅→∅)

crc32fast = { version = "1.2", optional = true, default-features = false }

[9.70978]

crc32fast = { version = "1.2", optional = true, default-features = false }
file move: sanakirja (dxwrx-rx-r) → sanakirja (d--r------)

[1.0]

[9.71001]
file move: src (dxwrx-rx-r) → src (d--r------)

[9.71001]

[9.71008]
file move: tests.rs (-xw-x--x--) → tests.rs (----------)

[9.71008]

[9.11]
edit in sanakirja/src/tests.rs at line 38

[9.2558]

[9.2558]

}

#[derive(Eq, PartialEq, PartialOrd, Ord, Hash, Clone, Copy)]
struct U([u64; 3]);
direct_repr!(U);

#[derive(Eq, PartialEq, PartialOrd, Ord, Hash, Clone, Copy)]
struct V([u64; 5]);
direct_repr!(V);

impl std::fmt::Debug for U {
fn fmt(&self, fmt: &mut std::fmt::Formatter) -> std::fmt::Result {
write!(fmt, "U({})", self.0[0])
}
}

impl std::fmt::Debug for V {
fn fmt(&self, fmt: &mut std::fmt::Formatter) -> std::fmt::Result {
write!(fmt, "V")
}
}

#[test]
pub fn random_scenario_sized_fork() {
let path = "/home/pe/bla/db";
let l0 = 1 << 20;
std::fs::remove_file(path).unwrap_or(());
let env = Env::new(&path, l0, 1).unwrap();
let mut txn = Env::mut_txn_begin(&env).unwrap();
let mut db = create_db::<MutTxn<&Env, ()>, U, V>(&mut txn).unwrap();
use rand::{Rng, SeedableRng};
let mut rng = rand::rngs::SmallRng::from_seed(*b"rc',.snjcg'sthomw,.vbw,.p84fcxjw");
let mut ve: Vec<(U, V)> = Vec::with_capacity(100_000);
use std::collections::HashMap;
let mut h: HashMap<U, V> = HashMap::with_capacity(100_000);

let mut refs = BTreeMap::new();
let mut dbs = Vec::new();

for i in 0.. {
let do_debug = i > 5618; // i % 1_000_000 == 0;
if do_debug {
env_logger::try_init().unwrap_or(());
info!("========== i = {:?} {:?}", i, db.db);
}
dbs.push(fork_db(&mut txn, &db).unwrap());
if rng.gen_range(0..4) == 3 {
if let Some((k, v)) = ve.pop() {
if do_debug {
debug!("del {:?} {:?}", k.0[0], v.0[0]);
}
assert!(del(&mut txn, &mut db, &k, Some(&v)).unwrap())
}
} else {
let k = U([rng.gen(), rng.gen(), rng.gen()]);
let v = V([rng.gen(), rng.gen(), rng.gen(), rng.gen(), rng.gen()]);
if do_debug {
debug!("put {:?} {:?}", k.0[0], v.0[0]);
}
put(&mut txn, &mut db, &k, &v).unwrap();
ve.push((k, v));
h.insert(k, v);
}
if do_debug {
debug(&txn, &[&db], format!("debug_{}", i), true);
for (i, (k, v)) in ve.iter().enumerate() {
if get(&txn, &db, k, None).unwrap() != Some((k, v)) {
panic!("test {:?} {:?} {:?}", i, k.0[0], v.0[0]);
}
}
for x in iter(&txn, &db, None).unwrap() {
let (k, v) = x.unwrap();
if h.get(k) != Some(v) {
panic!("test {:?}", k);
}
}
refs.clear();
add_refs(&txn, &db, &mut refs).unwrap();
for db in dbs.iter() {
add_refs(&txn, db, &mut refs).unwrap();
}
add_free_refs_mut(&txn, &mut refs).unwrap();
check_free_mut(&mut txn, &refs);
if let Some(ref rc) = txn.rc {
let mut last = 0;
for r in iter(&txn, rc, None).unwrap() {
let (r, _) = r.unwrap();
if last > 0 && last == (r & !0xfff) {
panic!("r = {:?} last = {:?}", r, last);
}
last = r & !0xfff;
}
}
let mut n = Vec::new();
for (p, r) in refs.iter() {
if *r >= 2 {
let rc = txn.rc(*p).unwrap();
if rc != *r as u64 {
n.push((p, *r, rc))
}
} else {
assert_eq!(txn.rc(*p).unwrap(), 0);
}
}
if !n.is_empty() {
panic!("n = {:?} {:?}", n, n.len());
}
}
}
}

#[test]
pub fn random_scenario_sized_test() {
let path = "/home/pe/bla/db";
let l0 = 1 << 20;
std::fs::remove_file(path).unwrap_or(());
let env = Env::new(&path, l0, 1).unwrap();
let mut txn = Env::mut_txn_begin(&env).unwrap();
let mut db = create_db::<MutTxn<&Env, ()>, U, V>(&mut txn).unwrap();
use rand::{Rng, SeedableRng};
let mut rng = rand::rngs::SmallRng::from_seed(*b"rc',.snjcg'sthomw,.vbw,.p84fcxjw");
let mut ve: Vec<(U, V)> = Vec::with_capacity(100_000);
use std::collections::HashMap;
let mut h: HashMap<U, V> = HashMap::with_capacity(100_000);

let mut refs = BTreeMap::new();

for i in 0.. {
let do_debug = i % 10_000_000 == 0;
if do_debug {
env_logger::try_init().unwrap_or(());
info!("========== i = {:?} {:?}", i, db.db);
}
if rng.gen_range(0..4) == 3 {
if let Some((k, v)) = ve.pop() {
if do_debug {
debug!("del {:?} {:?}", k.0[0], v.0[0]);
}
assert!(del(&mut txn, &mut db, &k, Some(&v)).unwrap())
}
} else {
let k = U([rng.gen(), rng.gen(), rng.gen()]);
let v = V([rng.gen(), rng.gen(), rng.gen(), rng.gen(), rng.gen()]);
if do_debug {
debug!("put {:?} {:?}", k.0[0], v.0[0]);
}
put(&mut txn, &mut db, &k, &v).unwrap();
ve.push((k, v));
h.insert(k, v);
}
if do_debug {
for (i, (k, v)) in ve.iter().enumerate() {
if get(&txn, &db, k, None).unwrap() != Some((k, v)) {
panic!("test {:?} {:?} {:?}", i, k.0[0], v.0[0]);
}
}
for x in iter(&txn, &db, None).unwrap() {
let (k, v) = x.unwrap();
if h.get(k) != Some(v) {
panic!("test {:?}", k);
}
}
refs.clear();
add_refs(&txn, &db, &mut refs).unwrap();
check_free_mut(&mut txn, &refs);
for (p, r) in refs.iter() {
if *r >= 2 {
let rc = txn.rc(*p).unwrap();
if rc != *r as u64 {
panic!("p {:?} r {:?} {:?}", p, r, rc);
}
} else {
assert_eq!(txn.rc(*p).unwrap(), 0);
}
}
}
}
}

#[test]
pub fn random_scenario_unsized_test() {
let path = "/home/pe/bla/udb";
let l0 = 1 << 20;
std::fs::remove_file(path).unwrap_or(());
let env = Env::new(&path, l0, 1).unwrap();
let mut txn = Env::mut_txn_begin(&env).unwrap();
let mut db = create_db_::<MutTxn<&Env, ()>, U, V, btree::page_unsized::Page<U, V>>(&mut txn).unwrap();
use rand::{Rng, SeedableRng};
let mut rng = rand::rngs::SmallRng::from_seed(*b"rc',.snjcg'sthomw,.vbw,.p84fcxjw");
let mut ve: Vec<(U, V)> = Vec::with_capacity(100_000);
use std::collections::HashMap;
let mut h: HashMap<U, V> = HashMap::with_capacity(100_000);

let mut refs = BTreeMap::new();

for i in 0.. {
let do_debug = true; // i % 10_000_000 == 0;
if do_debug {
env_logger::try_init().unwrap_or(());
info!("========== i = {:?} {:?}", i, db.db);
}
if rng.gen_range(0..4) == 3 {
if let Some((k, v)) = ve.pop() {
if do_debug {
debug!("del {:?} {:?}", k.0[0], v.0[0]);
}
assert!(del(&mut txn, &mut db, &k, Some(&v)).unwrap())
}
} else {
let k = U([rng.gen(), rng.gen(), rng.gen()]);
let v = V([rng.gen(), rng.gen(), rng.gen(), rng.gen(), rng.gen()]);
if do_debug {
debug!("put {:?} {:?}", k.0[0], v.0[0]);
}
put(&mut txn, &mut db, &k, &v).unwrap();
ve.push((k, v));
h.insert(k, v);
}
if do_debug {
for (i, (k, v)) in ve.iter().enumerate() {
if get(&txn, &db, k, None).unwrap() != Some((k, v)) {
panic!("test {:?} {:?} {:?}", i, k.0[0], v.0[0]);
}
}
for x in iter(&txn, &db, None).unwrap() {
let (k, v) = x.unwrap();
if h.get(k) != Some(v) {
panic!("test {:?}", k);
}
}
refs.clear();
add_refs(&txn, &db, &mut refs).unwrap();
check_free_mut(&mut txn, &refs);
for (p, r) in refs.iter() {
if *r >= 2 {
let rc = txn.rc(*p).unwrap();
if rc != *r as u64 {
panic!("p {:?} r {:?} {:?}", p, r, rc);
}
} else {
assert_eq!(txn.rc(*p).unwrap(), 0);
}
}
}
}
edit in sanakirja/src/tests.rs at line 289

[9.2560]

[9.978]
edit in sanakirja/src/tests.rs at line 316

[9.154]→[9.1952:1953](∅→∅),[9.1459]→[9.1952:1953](∅→∅),[9.1952]→[9.1952:1953](∅→∅)
file move: lib.rs (-xw-x--x--) → lib.rs (----------)

[9.71008]

[9.79574]
file move: environment (dxwrx-rx-r) → environment (d--r------)

[9.71008]

[9.80153]
file move: muttxn.rs (-xw-x--x--) → muttxn.rs (----------)

[9.80153]

[9.80166]
edit in sanakirja/src/environment/muttxn.rs at line 2

[9.80181]→[9.80181:80193](∅→∅)

use log::*;
replacement in sanakirja/src/environment/muttxn.rs at line 353

[9.86200]→[9.13026:13077](∅→∅)

debug!("FREEING OWNED PAGE {:?}", offset);

[9.86200]

[9.7050]

debug!("FREEING OWNED PAGE {:?} {:x}", offset, offset);
replacement in sanakirja/src/environment/muttxn.rs at line 362

[9.86294]→[9.13078:13123](∅→∅)

debug!("FREEING PAGE {:?}", offset);

[9.86294]

[9.7082]

debug!("FREEING PAGE {:?} {:x}", offset, offset);
replacement in sanakirja/src/environment/muttxn.rs at line 375

[9.16305]→[9.16610:16676](∅→∅)

let mut f = if let Some((f, ())) = curs.set_last(self)? {

[9.16305]

[9.86826]

curs.set_last(self)?;
let mut f = if let Some((f, ())) = curs.prev(self)? {
replacement in sanakirja/src/environment/muttxn.rs at line 395

[9.17097]→[9.42002:42064](∅→∅),[9.86898]→[9.42002:42064](∅→∅)

btree::del::del_at_cursor(self, &mut db, &mut curs)?;

[9.17097]

[9.86955]

assert!(btree::del::del(self, &mut db, &f, None)?);
replacement in sanakirja/src/environment/muttxn.rs at line 475

[9.16374]→[9.18996:19070](∅→∅)

let rc = if let Some((rc, _)) = curs.set(self, &off, None)? {

[9.16374]

[9.38483]

curs.set(self, &off, None)?;
let rc = if let Some((rc, _)) = curs.current(self)? {
edit in sanakirja/src/environment/muttxn.rs at line 488

[9.89127]

[9.19176]

debug!("incr rc {:?} {:?}", off, rc+1);
file move: mod.rs (-xw-x--x--) → mod.rs (----------)

[9.80153]

[9.91606]
edit in sanakirja/src/environment/mod.rs at line 17

[9.1533]

[9.91760]

use log::*;
replacement in sanakirja/src/environment/mod.rs at line 167

[9.24505]→[9.24505:24588](∅→∅)

GlobalHeader::from_le(&*(map as *const GlobalHeader)).n_roots as usize

[9.24505]

[9.24588]

let g = &*(map as *const GlobalHeader);
assert_eq!(g.version, CURRENT_VERSION);
g.n_roots as usize
edit in sanakirja/src/environment/mod.rs at line 343

[9.104214]

[9.104214]

info!("find_offset, i = {:?}/{:?}, extending, offset = {:?}, length0 = {:?}", i, mmaps.len(), offset, length0);
replacement in sanakirja/src/environment/mod.rs at line 379

[9.27561]→[9.27561:27948](∅→∅)

let page_ptr = maps[0].ptr.add(root * PAGE_SIZE);
let crc = (&*(page_ptr as *const GlobalHeader)).crc;
let root_page = std::slice::from_raw_parts(page_ptr.add(8), PAGE_SIZE - 8);
let mut h = HASHER.clone();
h.update(root_page);
if h.finalize() != crc {
return Err(crate::CRCError {});
}

[9.27561]

[9.105565]

check_crc(maps[0].ptr.add(root * PAGE_SIZE))
edit in sanakirja/src/environment/mod.rs at line 381

[9.105575]→[9.27949:27964](∅→∅)

Ok(())
edit in sanakirja/src/environment/mod.rs at line 432

[9.29123]

[9.29123]

debug!("SETTING CRC {:?}", (&*globptr).crc);
edit in sanakirja/src/environment/mod.rs at line 528

[9.106534]→[9.106534:106564](∅→∅)

check_crc(data)?;
replacement in sanakirja/src/environment/mod.rs at line 575

[9.106794]→[9.106794:106842](∅→∅)

let crc = u32::from_le(*(p as *const u32));

[9.106794]

[9.106842]

let globptr = p as *mut GlobalHeader;
let crc = u32::from_le((&*globptr).crc);
replacement in sanakirja/src/environment/mod.rs at line 578

[9.106884]→[9.106884:106955](∅→∅)

let data = std::slice::from_raw_parts(p.offset(4), PAGE_SIZE - 4);

[9.106884]

[9.106955]

let data = std::slice::from_raw_parts(p.offset(8), PAGE_SIZE - 8);
edit in sanakirja/src/environment/mod.rs at line 581

[9.107004]

[9.107004]

debug!("CHECKING CRC {:?} {:?}", crc_, crc);
edit in sanakirja/src/environment/mod.rs at line 588

[9.107086]→[9.107086:107198](∅→∅)

#[cfg(not(feature = "crc32"))]
unsafe fn check_crc(_: *const u8) -> Result<(), crate::CRCError> {
Ok(())
}
file move: global_header.rs (-xw-x--x--) → global_header.rs (----------)

[9.80153]

[9.107218]
file move: debug.rs (-xw-x--x--) → debug.rs (----------)

[9.71008]

[9.11]
edit in sanakirja/src/debug.rs at line 100

[9.2481]

[9.21592]

debug!("CURSOR: {:?} {:?}", p.offset, cursor);
file move: Cargo.toml (-xw-x--x--) → Cargo.toml (----------)

[9.71001]

[9.108411]
replacement in sanakirja/Cargo.toml at line 3

[9.108441]→[6.2062:2080](∅→∅)

version = "1.0.1"

[9.108441]

[9.108459]

version = "1.1.2"
replacement in sanakirja/Cargo.toml at line 29

[9.84]→[5.390:457](∅→∅)

sanakirja-core = { path = "../sanakirja-core", version = "1.0.1" }

[9.84]

[9.5528]

sanakirja-core = { path = "../sanakirja-core", version = "1.1.0" }
replacement in sanakirja/Cargo.toml at line 40

[9.213]→[9.213:226](∅→∅)

rand = "0.8"

[9.213]

[9.226]

rand = {version = "0.8", features = [ "small_rng" ] }
file move: cover (-xwrx-rx-r) → cover (---r------)

[1.0]

[2.8]
file move: Cargo.toml (-xw-x--x--) → Cargo.toml (----------)

[1.0]

[9.108835]