Diagnostic tools (add_refs, check_free) + cleanup

[?]

Feb 21, 2021, 7:07 PM

FZBLNBGNQPNTLBNPNZ2C6DJ5323MZQ2PH54F6ZEKPFCK7TGJFGWAC

Dependencies

[2] 52X5P7ND Cleaning up the unsized part
[3] E4MD6T3L Proofreading and commenting of this crate (massive bug fixes included)
[4] S4V4QZ5C Debugging reference-counting for put
[5] 6DMPXOAT More debugging
[6] H3FVSQIQ Unsized pages
[7] XEU2QVLC Debugging after plugging this into Pijul
[8] TSMS6W4D Fully commented implementation of Sized nodes + massive cleanup
[9] W2MIZD5B Single file databases + CRC for the root pages (checking the other pages makes everything very slow)
[10] AFKBHYVE Comparing the two implementations of leaves (sized/unsized). Sized are faster for writes, slower for reads.
[11] RV2L6CZW A few comments
[12] 73Z2UB3J Cleanup + comments
[13] X3QVVQIS More debugging (del seems to work now)
[14] Q7DRIBBR Debugging replace (which cannot be del+put)
[15] DV4A2LR7 Double-inserts (rebalancing near an internal deletion)
[16] EHJFNMB2 Debugging
[17] QYDGYIZR Split trait Representable into its mandatory part and an optional part
[18] WS4ZQM4R Debugging, tests, etc.
[19] YWFYZNLZ Cleanup + inter-process concurrency
[20] OP6SVMOD Resetting history
[21] 6UVFCERM Formatting, debugging, etc.
[22] UUUVNC4D Debugging/cleanup around cursors
[23] EYNN7RLS Tests++ (including UUID)
[24] QEUTVAZ4 Splitting btree::page
[25] OFINGD26 implementing prev() on cursors (+ some cleanup)
[26] UAQX27N4 Tests
[27] AOX2XQIS Actually, with the correct functions, Unsized pages are always slower than Sized pages (especially for writing)
[28] LROAI3NB Two iterators (convenience functions), along with tests to move cursors (put and del still destroy cursors though)
[29] NXMFNPZ7 Comments + debugging drop
[30] OTWDDJE7 Trait/type cleanup
[31] D53GTMT3 Fixing a bug when cloning unsized pages, where insertions in leaves were not always added to the list of offsets
[32] ESUI5EUZ Making as_page() unsafe
[33] YXKP4AIW New file locks, with multiple sets of free pages
[34] 6DCQHIFP Minor changes after benchmarking
[35] G4JEQLLX Debugging synchronisation
[36] MSRWB47Y Deletions at immutable leaves weren't really deleting anything
[37] HN6Z5DU4 Cleanup
[38] FMN7X4J2 Micro-improvements, now noticeably faster than std::collections::BTreeMap
[39] LSQ6V7M6 Cleanup + docs
[40] KM3JAFGP Adding a test for next/prev
[*] T7QB6QEP Adding debug.rs

Change contents

edit in sanakirja-core/src/btree/put.rs at line 41

[4.4317]→[2.0:41](∅→∅)

debug!("put {:?} {:?}", key, value);
edit in sanakirja-core/src/btree/put.rs at line 126

[4.1695]→[2.42:109](∅→∅)

debug!("Split {:?} {:?}", split_key, split_value);
edit in sanakirja-core/src/btree/put.rs at line 172

[4.7298]→[2.110:140](∅→∅)

debug!("Ok");
edit in sanakirja-core/src/btree/page_unsized.rs at line 716

[2.20708]→[2.20708:20709](∅→∅)
replacement in sanakirja-core/src/btree/page_unsized/alloc.rs at line 44

[2.33217]→[2.33217:33261](∅→∅)

type Offset: Into<(u64, usize)> + Copy;

[2.33217]

[2.33261]

type Offset: Into<(u64, usize)> + Copy + core::fmt::Debug;
edit in sanakirja-core/src/btree/page.rs at line 71

[4.297]→[4.0:12](∅→∅),[4.8638]→[4.0:12](∅→∅)

use log::*;
edit in sanakirja-core/src/btree/page/put.rs at line 121

[4.9502]→[4.8058:8097](∅→∅)

debug!("u = {:?} k = {:?}", u, k);
edit in sanakirja-core/src/btree/mod.rs at line 25

[4.50142]→[4.8415:8427](∅→∅)

use log::*;
edit in sanakirja-core/src/btree/mod.rs at line 44

[4.8659]→[4.8659:8699](∅→∅)

debug!("cursor_first {:?}", c);
edit in sanakirja-core/src/btree/mod.rs at line 45

[4.9358]→[4.8735:8775](∅→∅),[4.8735]→[4.8735:8775](∅→∅)

debug!("cursor_first {:?}", c);
edit in sanakirja-core/Cargo.toml at line 38

[4.70978]→[4.1880:1892](∅→∅)

log = "0.4"
edit in sanakirja/src/tests.rs at line 2

[4.24]→[4.24:64](∅→∅)

use std::collections::btree_map::Entry;
edit in sanakirja/src/tests.rs at line 4

[4.97]

[4.97]

use crate::debug::*;
use crate::environment::*;
edit in sanakirja/src/tests.rs at line 9

[4.177]→[4.177:205](∅→∅)

use crate::environment::*;
replacement in sanakirja/src/tests.rs at line 60

[4.1952]→[4.1404:1459](∅→∅)

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

[4.1952]

[4.1952]

debug(&txn, &[&db], "debug0", true);
replacement in sanakirja/src/tests.rs at line 85

[4.2931]→[4.14827:14882](∅→∅)

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

[4.2931]

[4.14882]

debug(&txn, &[&db], "debug0", true);
edit in sanakirja/src/tests.rs at line 148

[4.1860]

[4.5674]

}

#[test]
pub fn empty_last_cursor() {
env_logger::try_init().unwrap_or(());
let env = Env::new_anon(409600000, 1).unwrap();
let mut txn = Env::mut_txn_begin(&env).unwrap();
let db: Db<u64, ()> = create_db(&mut txn).unwrap();
let mut curs = btree::cursor::Cursor::new(&txn, &db).unwrap();
assert!(curs.set_last(&txn).unwrap().is_none());
replacement in sanakirja/src/tests.rs at line 220

[4.11639]→[4.13253:13307](∅→∅)

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

[4.11639]

[4.13307]

debug(&txn, &[&db], "debug", true);
replacement in sanakirja/src/tests.rs at line 223

[4.772]→[4.20956:21017](∅→∅)

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

[4.772]

[4.11640]

debug(&txn, &[&db, &db2], "debug1", true);
replacement in sanakirja/src/tests.rs at line 230

[4.11810]→[4.11810:11877](∅→∅)

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

[4.11810]

[4.772]

debug(&txn, &[&db, &db2, &db3], "debug2", true);
edit in sanakirja/src/tests.rs at line 239

[4.9943]→[4.441:479](∅→∅)

type B = btree::page::Page<u64, ()>;
replacement in sanakirja/src/tests.rs at line 258

[4.6386]→[4.21042:21103](∅→∅)

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

[4.6386]

[4.1460]

debug(&txn, &[&db, &db2], "debug0", true);
replacement in sanakirja/src/tests.rs at line 267

[4.6527]→[4.21104:21165](∅→∅)

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

[4.6527]

[4.6527]

debug(&txn, &[&db, &db2], "debug1", true);
replacement in sanakirja/src/tests.rs at line 290

[4.164]→[4.164:225](∅→∅)

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

[4.164]

[4.26205]

debug(&txn, &[&db, &db2], "debug0", true);
replacement in sanakirja/src/tests.rs at line 295

[4.26345]→[4.26345:26406](∅→∅)

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

[4.26345]

[4.248]

debug(&txn, &[&db, &db2], "debug1", true);
replacement in sanakirja/src/tests.rs at line 298

[4.9628]→[4.11900:11980](∅→∅)

crate::debug::debug(&txn, &[&db, &db2], &format!("debug-{}", i), true);

[4.9628]

[4.11980]

debug(&txn, &[&db, &db2], &format!("debug-{}", i), true);
replacement in sanakirja/src/tests.rs at line 306

[4.392]→[4.9772:9833](∅→∅)

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

[4.392]

[4.2188]

debug(&txn, &[&db, &db2], "debug3", true);
replacement in sanakirja/src/tests.rs at line 330

[4.7458]→[4.480:513](∅→∅)

check_free(&mut txn, &refs);

[4.7458]

[4.513]

add_free_refs_mut(&txn, &mut refs).unwrap();
check_free_mut(&mut txn, &refs);
edit in sanakirja/src/tests.rs at line 333

[4.539]→[4.539:615](∅→∅),[4.615]→[4.15223:15245](∅→∅),[4.15245]→[4.7487:7540](∅→∅),[4.7487]→[4.7487:7540](∅→∅),[4.7540]→[4.51963:52086](∅→∅),[4.52086]→[4.7586:7597](∅→∅),[4.7586]→[4.7586:7597](∅→∅),[4.7597]→[3.267:359](∅→∅),[4.15365]→[4.7693:7726](∅→∅),[3.359]→[4.7693:7726](∅→∅),[4.26968]→[4.7693:7726](∅→∅),[4.7693]→[4.7693:7726](∅→∅),[4.7726]→[4.616:675](∅→∅),[4.675]→[4.7790:7827](∅→∅),[4.7790]→[4.7790:7827](∅→∅),[4.7827]→[4.676:719](∅→∅),[4.719]→[4.7827:7843](∅→∅),[4.7827]→[4.7827:7843](∅→∅),[4.7843]→[4.720:791](∅→∅)

}

fn check_free(txn: &mut MutTxn<&Env, ()>, refs: &BTreeMap<u64, usize>) {
if txn.free > 0 {
let db_free = Db {
db: txn.free,
k: std::marker::PhantomData,
v: std::marker::PhantomData,
p: std::marker::PhantomData,
};
let mut curs: Cursor<_, _, B> = btree::cursor::Cursor::new(txn, &db_free).unwrap();
debug!("{:?}", db_free);
while let Some((k, _)) = curs.next(txn).unwrap() {
debug!("free: {:?}", k);
assert!(refs.get(k).is_none())
}
}
for (r, _) in refs.iter() {
assert!(*r < txn.length)
}
edit in sanakirja/src/tests.rs at line 335

[4.7872]→[4.13355:13427](∅→∅),[4.13427]→[4.7963:7976](∅→∅),[4.27051]→[4.7963:7976](∅→∅),[4.7963]→[4.7963:7976](∅→∅),[4.7976]→[4.27052:27075](∅→∅),[4.1694]→[4.8001:8067](∅→∅),[4.27075]→[4.8001:8067](∅→∅),[4.8001]→[4.8001:8067](∅→∅),[4.8067]→[4.15366:15409](∅→∅),[4.15409]→[4.8067:8138](∅→∅),[4.27126]→[4.8067:8138](∅→∅),[4.8067]→[4.8067:8138](∅→∅),[4.8138]→[4.27127:27161](∅→∅),[4.27161]→[4.15410:15441](∅→∅),[4.15441]→[4.8176:8239](∅→∅),[4.8176]→[4.8176:8239](∅→∅),[4.8239]→[4.15442:15485](∅→∅),[4.15485]→[4.21195:21244](∅→∅),[4.15543]→[4.8297:8353](∅→∅),[4.21244]→[4.8297:8353](∅→∅),[4.8297]→[4.8297:8353](∅→∅),[4.8353]→[4.27162:27201](∅→∅),[4.27201]→[4.8353:8380](∅→∅),[4.8353]→[4.8353:8380](∅→∅),[4.8380]→[4.15544:15579](∅→∅),[4.15579]→[4.27202:27333](∅→∅),[4.8431]→[4.27202:27333](∅→∅),[4.27333]→[4.15580:15619](∅→∅),[4.15619]→[4.8564:8658](∅→∅),[4.8564]→[4.8564:8658](∅→∅),[4.8658]→[4.27334:27375](∅→∅),[4.27375]→[4.8658:8740](∅→∅),[4.8658]→[4.8658:8740](∅→∅),[4.8740]→[4.1695:1696](∅→∅)

fn add_refs<T: LoadPage, K: Storable, V: Storable, P: BTreePage<K, V>>(
txn: &T,
db: &Db_<K, V, P>,
pages: &mut BTreeMap<u64, usize>,
) -> Result<(), T::Error> {
debug!("------ add_refs {:?}", db.db);
let mut stack = vec![db.db];
while let Some(p) = stack.pop() {
debug!("-- p = {:?}", p);
match pages.entry(p) {
Entry::Vacant(e) => {
e.insert(1);
let p = txn.load_page(p)?;
let mut c = P::cursor_first(&p);
let l = P::left_child(p.as_page(), &c);
debug!("l = {:?}", l);
if l > 0 {
stack.push(l);
while let Some((_, _, r)) = P::next(txn, p.as_page(), &mut c) {
debug!("r = {:?}", r);
stack.push(r);
}
}
}
Entry::Occupied(mut e) => {
debug!("already there");
e.insert(e.get() + 1);
}
}
}
Ok(())
}
replacement in sanakirja/src/tests.rs at line 504

[4.2624]→[4.2624:2657](∅→∅)

check_free(&mut txn, &refs);

[4.2624]

[4.2354]

check_free_mut(&mut txn, &refs);
replacement in sanakirja/src/tests.rs at line 531

[4.3005]→[4.3005:3038](∅→∅)

check_free(&mut txn, &refs);

[4.3005]

[4.1063]

check_free_mut(&mut txn, &refs);
replacement in sanakirja/src/tests.rs at line 562

[4.2045]→[2.45410:45468](∅→∅)

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

[4.2045]

[4.2045]

debug(&txn, &[&db], "debug", true);
replacement in sanakirja/src/tests.rs at line 575

[4.2592]→[4.10147:10205](∅→∅)

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

[4.2592]

[4.2592]

debug(&txn, &[&db], "debug", true);
replacement in sanakirja/src/tests.rs at line 856

[4.1140]→[4.4830:4884](∅→∅)

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

[4.1140]

[4.1140]

debug(&txn, &[&db], "debug", true);
replacement in sanakirja/src/tests.rs at line 881

[4.5193]→[4.5193:5247](∅→∅)

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

[4.5193]

[4.5247]

debug(&txn, &[&db], "debug", true);
replacement in sanakirja/src/tests.rs at line 940

[4.11740]→[4.11740:11795](∅→∅)

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

[4.11740]

[4.11795]

debug(&txn, &[&db], "debug0", true);
replacement in sanakirja/src/tests.rs at line 945

[4.11891]→[4.11891:11952](∅→∅)

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

[4.11891]

[4.11959]

debug(&txn, &[&db, &db2], "debug1", true);
replacement in sanakirja/src/tests.rs at line 967

[4.12683]→[4.12683:12716](∅→∅)

check_free(&mut txn, &refs);

[4.12683]

[4.12716]

add_free_refs_mut(&txn, &mut refs).unwrap();
check_free_mut(&mut txn, &refs);
replacement in sanakirja/src/tests.rs at line 989

[4.4338]→[4.4338:4399](∅→∅)

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

[4.4338]

[4.4399]

debug(&txn, &[&db, &db2], "debug1", true);
replacement in sanakirja/src/tests.rs at line 991

[4.4433]→[4.4433:4488](∅→∅)

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

[4.4433]

[4.4488]

debug(&txn, &[&db], "debug2", true);
edit in sanakirja/src/environment/mod.rs at line 103

[4.2028]→[4.94481:94614](∅→∅),[4.94481]→[4.94481:94614](∅→∅),[4.94614]→[4.4622:4666](∅→∅),[4.4666]→[4.94709:94716](∅→∅),[4.94709]→[4.94709:94716](∅→∅)

/// std::fs::File size of the database path, if it exists.
pub fn file_size<P: AsRef<Path>>(path: P) -> Result<u64, Error> {
Ok(std::fs::metadata(&path)?.len())
}
replacement in sanakirja/src/environment/mod.rs at line 237

[3.26074]→[4.99665:99728](∅→∅),[4.99665]→[4.99665:99728](∅→∅),[4.99728]→[4.3260:3295](∅→∅)

/// Initialize an environment. `length` must be a strictly
/// positive multiple of 4096.

[3.26074]

[4.3295]

/// Initialize an environment. If `length` is not a multiple of
/// `4096`, it is rounded to the next multiple of the page size
/// (4096 bytes).
///
/// The `n_roots` parameter is the maximum number of versions that
/// can be alive at the same time, before `mut_txn_begin` must
/// wait for old readers to stop.
replacement in sanakirja/src/environment/mod.rs at line 245

[4.3303]→[4.3303:3554](∅→∅)

/// The `n_roots` parameter is the maximum number of mutable
/// transactions that can commit during a single immutable
/// transaction, and must be at most 255. If it is 1, mutable
/// transactions exclude all immutable transactions.

[4.3303]

[4.99844]

/// If `n_roots` is 1, mutable transactions exclude all readers.
replacement in sanakirja/src/environment/mod.rs at line 441

[3.29195]→[3.29195:29207](∅→∅)

env: E,

[3.29195]

[3.29207]

pub(crate) env: E,
edit in sanakirja/src/debug.rs at line 1

[42.11]

[42.39]

use log::*;
edit in sanakirja/src/debug.rs at line 122

[42.3066]

[42.3066]

}
}

type B = btree::page::Page<u64, ()>;

pub fn check_free_mut(
txn: &crate::MutTxn<&crate::Env, ()>,
refs: &std::collections::BTreeMap<u64, usize>,
) {
let db_free = if txn.free > 0 {
let db_free = Db::from_page(txn.free);
let mut curs: Cursor<_, _, B> = btree::cursor::Cursor::new(txn, &db_free).unwrap();
while let Some((k, _)) = curs.next(txn).unwrap() {
assert!(refs.get(k).is_none())
}
Some(db_free)
} else {
None
};
debug!("{:?}", db_free);
for (r, _) in refs.iter() {
assert!(*r < txn.length)
}
let env = txn.env;
let len = txn.length;

for i in env.roots.len() as u64..(len >> 12) {
let page = i << 12;
if refs.contains_key(&page) {
continue;
} else if let Some(ref f) = db_free {
if let Some((x, _)) = get(txn, f, &page, None).unwrap() {
if *x == page {
continue;
}
}
}
panic!("page not found: 0x{:x} (total length 0x{:x})", page, len);
}
}

pub fn check_free<B: std::borrow::Borrow<crate::Env>>(
txn: &crate::Txn<B>,
refs: &std::collections::BTreeMap<u64, usize>,
) {
let env = txn.env.borrow();
let (db_free, length): (Option<Db<u64, ()>>, _) = unsafe {
let hdr = &*(env.mmaps.lock()[0].ptr.add(txn.root * PAGE_SIZE)
as *const crate::environment::GlobalHeader);
(
if hdr.free_db != 0 {
Some(Db::from_page(u64::from_le(hdr.free_db)))
} else {
None
},
u64::from_le(hdr.length),
)
};
debug!("db_free: {:?}", db_free);
for (r, _) in refs.iter() {
debug!("r = 0x{:x}, length = 0x{:x}", r, length);
assert!(*r < length)
}
for i in env.roots.len() as u64..(length >> 12) {
let page = i << 12;
if refs.contains_key(&page) {
continue;
} else if let Some(ref f) = db_free {
if let Some((x, _)) = get(txn, f, &page, None).unwrap() {
if *x == page {
continue;
}
}
}
panic!("page not found: 0x{:x} (total length 0x{:x})", page, length);
}
}

pub fn add_refs<T: LoadPage, K: Storable + ?Sized, V: Storable + ?Sized, P: BTreePage<K, V>>(
txn: &T,
db: &Db_<K, V, P>,
pages: &mut std::collections::BTreeMap<u64, usize>,
) -> Result<(), T::Error> {
use std::collections::btree_map::Entry;
let mut stack = vec![db.db];
while let Some(p) = stack.pop() {
match pages.entry(p) {
Entry::Vacant(e) => {
debug!("add_refs: 0x{:x}", p);
e.insert(1);
let p = txn.load_page(p)?;
let mut c = P::cursor_first(&p);
let l = P::left_child(p.as_page(), &c);
if l > 0 {
stack.push(l);
while let Some((_, _, r)) = P::next(txn, p.as_page(), &mut c) {
stack.push(r);
}
}
}
Entry::Occupied(mut e) => {
e.insert(e.get() + 1);
}
}
edit in sanakirja/src/debug.rs at line 227

[42.3072]

[42.3072]

Ok(())
edit in sanakirja/src/debug.rs at line 229

[42.3074]

pub fn add_free_refs<B: std::borrow::Borrow<crate::Env>>(
txn: &crate::Txn<B>,
pages: &mut std::collections::BTreeMap<u64, usize>,
) -> Result<(), crate::Error> {
let env = txn.env.borrow();
unsafe {
let p = &*(env.mmaps.lock()[0].ptr.add(txn.root * PAGE_SIZE)
as *const crate::environment::GlobalHeader);
if p.free_db != 0 {
debug!("add_free_refs: free = 0x{:x}", p.free_db);
let free_db: Db<u64, ()> = btree::Db::from_page(p.free_db);
add_refs(txn, &free_db, pages)?;
}
if p.rc_db != 0 {
debug!("add_free_refs: rc = 0x{:x}", p.rc_db);
let rc_db: Db<u64, ()> = btree::Db::from_page(p.rc_db);
add_refs(txn, &rc_db, pages)?;
}
};
Ok(())
}

pub fn add_free_refs_mut<B: std::borrow::Borrow<crate::Env>, T>(
txn: &crate::MutTxn<B, T>,
pages: &mut std::collections::BTreeMap<u64, usize>,
) -> Result<(), crate::Error> {
let env = txn.env.borrow();
unsafe {
let p = &*(env.mmaps.lock()[0].ptr.add(txn.root * PAGE_SIZE)
as *const crate::environment::GlobalHeader);
if p.free_db != 0 {
debug!("add_free_refs: free = 0x{:x}", p.free_db);
let free_db: Db<u64, ()> = btree::Db::from_page(p.free_db);
add_refs(txn, &free_db, pages)?;
}
if p.rc_db != 0 {
debug!("add_free_refs: rc = 0x{:x}", p.rc_db);
let rc_db: Db<u64, ()> = btree::Db::from_page(p.rc_db);
add_refs(txn, &rc_db, pages)?;
}
};
Ok(())
}