rust
/
sled
mirror of https://github.com/spacejam/sled
1
0
Fork 0
Code Issues Releases Wiki Activity
sled/tests/00_regression.rs

1641 lines
57 KiB
Rust
Raw Permalink Blame History

mod common;
mod tree;
use std::alloc::{Layout, System};
use tree::{prop_tree_matches_btreemap, Key, Op::*};
#[global_allocator]
static ALLOCATOR: ShredAllocator = ShredAllocator;
#[derive(Default, Debug, Clone, Copy)]
struct ShredAllocator;
unsafe impl std::alloc::GlobalAlloc for ShredAllocator {
unsafe fn alloc(&self, layout: Layout) -> *mut u8 {
assert!(layout.size() < 1_000_000_000);
let ret = System.alloc(layout);
assert_ne!(ret, std::ptr::null_mut());
std::ptr::write_bytes(ret, 0xa1, layout.size());
ret
}
unsafe fn dealloc(&self, ptr: *mut u8, layout: Layout) {
std::ptr::write_bytes(ptr, 0xde, layout.size());
System.dealloc(ptr, layout)
}
}
#[allow(dead_code)]
const INTENSITY: usize = 10;
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_00() {
// postmortem:
prop_tree_matches_btreemap(vec![Restart], false, 0, 256);
}
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_01() {
// postmortem:
// this was a bug in the snapshot recovery, where
// it led to max_id dropping by 1 after a restart.
// postmortem 2:
// we were stalling here because we had a new log with stable of
// SEG_HEADER_LEN, but when we iterated over it to create a new
// snapshot (snapshot every 1 set in Config), we iterated up until
// that offset. make_stable requires our stable offset to be >=
// the provided one, to deal with 0.
prop_tree_matches_btreemap(
vec![
Set(Key(vec![32]), 9),
Set(Key(vec![195]), 13),
Restart,
Set(Key(vec![164]), 147),
],
true,
0,
256,
);
}
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_02() {
// postmortem:
// this was a bug in the way that the `Materializer`
// was fed data, possibly out of order, if recover
// in the pagecache had to run over log entries
// that were later run through the same `Materializer`
// then the second time (triggered by a snapshot)
// would not pick up on the importance of seeing
// the new root set.
// portmortem 2: when refactoring iterators, failed
// to account for node.hi being empty on the infinity
// shard
prop_tree_matches_btreemap(
vec![
Restart,
Set(Key(vec![215]), 121),
Restart,
Set(Key(vec![216]), 203),
Scan(Key(vec![210]), 4),
],
true,
0,
256,
);
}
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_03() {
// postmortem: the tree was not persisting and recovering root hoists
// postmortem 2: when refactoring the log storage, we failed to restart
// log writing in the proper location.
prop_tree_matches_btreemap(
vec![
Set(Key(vec![113]), 204),
Set(Key(vec![119]), 205),
Set(Key(vec![166]), 88),
Set(Key(vec![23]), 44),
Restart,
Set(Key(vec![226]), 192),
Set(Key(vec![189]), 186),
Restart,
Scan(Key(vec![198]), 11),
],
true,
0,
256,
);
}
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_04() {
// postmortem: pagecache was failing to replace the LogId list
// when it encountered a new Update::Compact.
// postmortem 2: after refactoring log storage, we were not properly
// setting the log tip, and the beginning got clobbered after writing
// after a restart.
prop_tree_matches_btreemap(
vec![
Set(Key(vec![158]), 31),
Set(Key(vec![111]), 134),
Set(Key(vec![230]), 187),
Set(Key(vec![169]), 58),
Set(Key(vec![131]), 10),
Set(Key(vec![108]), 246),
Set(Key(vec![127]), 155),
Restart,
Set(Key(vec![59]), 119),
],
true,
0,
256,
);
}
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_05() {
// postmortem: during recovery, the segment accountant was failing to
// properly set the file's tip.
prop_tree_matches_btreemap(
vec![
Set(Key(vec![231]), 107),
Set(Key(vec![251]), 42),
Set(Key(vec![80]), 81),
Set(Key(vec![178]), 130),
Set(Key(vec![150]), 232),
Restart,
Set(Key(vec![98]), 78),
Set(Key(vec![0]), 45),
],
true,
0,
256,
);
}
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_06() {
// postmortem: after reusing segments, we were failing to checksum reads
// performed while iterating over rewritten segment buffers, and using
// former garbage data. fix: use the crc that's there for catching torn
// writes with high probability, AND zero out buffers.
prop_tree_matches_btreemap(
vec![
Set(Key(vec![162]), 8),
Set(Key(vec![59]), 192),
Set(Key(vec![238]), 83),
Set(Key(vec![151]), 231),
Restart,
Set(Key(vec![30]), 206),
Set(Key(vec![150]), 146),
Set(Key(vec![18]), 34),
],
true,
0,
256,
);
}
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_07() {
// postmortem: the segment accountant was not fully recovered, and thought
// that it could reuse a particular segment that wasn't actually empty
// yet.
prop_tree_matches_btreemap(
vec![
Set(Key(vec![135]), 22),
Set(Key(vec![41]), 36),
Set(Key(vec![101]), 31),
Set(Key(vec![111]), 35),
Restart,
Set(Key(vec![47]), 36),
Set(Key(vec![79]), 114),
Set(Key(vec![64]), 9),
Scan(Key(vec![196]), 25),
],
true,
0,
256,
);
}
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_08() {
// postmortem: failed to properly recover the state in the segment
// accountant that tracked the previously issued segment.
prop_tree_matches_btreemap(
vec![
Set(Key(vec![145]), 151),
Set(Key(vec![155]), 148),
Set(Key(vec![131]), 170),
Set(Key(vec![163]), 60),
Set(Key(vec![225]), 126),
Restart,
Set(Key(vec![64]), 237),
Set(Key(vec![102]), 205),
Restart,
],
true,
0,
256,
);
}
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_09() {
// postmortem 1: was failing to load existing snapshots on initialization.
// would encounter uninitialized segments at the log tip and overwrite
// the first segment (indexed by LSN of 0) in the segment accountant
// ordering, skipping over important updates.
//
// postmortem 2: page size tracking was inconsistent in SA. completely
// removed exact size tracking, and went back to simpler pure-page
// tenancy model.
prop_tree_matches_btreemap(
vec![
Set(Key(vec![189]), 36),
Set(Key(vec![254]), 194),
Set(Key(vec![132]), 50),
Set(Key(vec![91]), 221),
Set(Key(vec![126]), 6),
Set(Key(vec![199]), 183),
Set(Key(vec![71]), 125),
Scan(Key(vec![67]), 16),
Set(Key(vec![190]), 16),
Restart,
],
true,
0,
256,
);
}
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_10() {
// postmortem: after reusing a segment, but not completely writing a
// segment, we were hitting an old LSN and violating an assert, rather
// than just ending.
prop_tree_matches_btreemap(
vec![
Set(Key(vec![152]), 163),
Set(Key(vec![105]), 191),
Set(Key(vec![207]), 217),
Set(Key(vec![128]), 19),
Set(Key(vec![106]), 22),
Scan(Key(vec![20]), 24),
Set(Key(vec![14]), 150),
Set(Key(vec![80]), 43),
Set(Key(vec![174]), 134),
Set(Key(vec![20]), 150),
Set(Key(vec![13]), 171),
Restart,
Scan(Key(vec![240]), 25),
Scan(Key(vec![77]), 37),
Set(Key(vec![153]), 232),
Del(Key(vec![2])),
Set(Key(vec![227]), 169),
Get(Key(vec![232])),
Cas(Key(vec![247]), 151, 70),
Set(Key(vec![78]), 52),
Get(Key(vec![16])),
Del(Key(vec![78])),
Cas(Key(vec![201]), 93, 196),
Set(Key(vec![172]), 84),
],
true,
0,
256,
);
}
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_11() {
// postmortem: a stall was happening because LSNs and LogIds were being
// conflated in calls to make_stable. A higher LogId than any LSN was
// being created, then passed in.
prop_tree_matches_btreemap(
vec![
Set(Key(vec![38]), 148),
Set(Key(vec![176]), 175),
Set(Key(vec![82]), 88),
Set(Key(vec![164]), 85),
Set(Key(vec![139]), 74),
Set(Key(vec![73]), 23),
Cas(Key(vec![34]), 67, 151),
Set(Key(vec![115]), 133),
Set(Key(vec![249]), 138),
Restart,
Set(Key(vec![243]), 6),
],
true,
0,
256,
);
}
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_12() {
// postmortem: was not checking that a log entry's LSN matches its position
// as part of detecting tears / partial rewrites.
prop_tree_matches_btreemap(
vec![
Set(Key(vec![118]), 156),
Set(Key(vec![8]), 63),
Set(Key(vec![165]), 110),
Set(Key(vec![219]), 108),
Set(Key(vec![91]), 61),
Set(Key(vec![18]), 98),
Scan(Key(vec![73]), 6),
Set(Key(vec![240]), 108),
Cas(Key(vec![71]), 28, 189),
Del(Key(vec![199])),
Restart,
Set(Key(vec![30]), 140),
Scan(Key(vec![118]), 13),
Get(Key(vec![180])),
Cas(Key(vec![115]), 151, 116),
Restart,
Set(Key(vec![31]), 95),
Cas(Key(vec![79]), 153, 225),
Set(Key(vec![34]), 161),
Get(Key(vec![213])),
Set(Key(vec![237]), 215),
Del(Key(vec![52])),
Set(Key(vec![56]), 78),
Scan(Key(vec![141]), 2),
Cas(Key(vec![228]), 114, 170),
Get(Key(vec![231])),
Get(Key(vec![223])),
Del(Key(vec![167])),
Restart,
Scan(Key(vec![240]), 31),
Del(Key(vec![54])),
Del(Key(vec![2])),
Set(Key(vec![117]), 165),
Set(Key(vec![223]), 50),
Scan(Key(vec![69]), 4),
Get(Key(vec![156])),
Set(Key(vec![214]), 72),
],
true,
0,
256,
);
}
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_13() {
// postmortem: failed root hoists were being improperly recovered before the
// following free was done on their page, but we treated the written node as
// if it were a successful completed root hoist.
prop_tree_matches_btreemap(
vec![
Set(Key(vec![42]), 10),
Set(Key(vec![137]), 220),
Set(Key(vec![183]), 129),
Set(Key(vec![91]), 145),
Set(Key(vec![126]), 26),
Set(Key(vec![255]), 67),
Set(Key(vec![69]), 18),
Restart,
Set(Key(vec![24]), 92),
Set(Key(vec![193]), 17),
Set(Key(vec![3]), 143),
Cas(Key(vec![50]), 13, 84),
Restart,
Set(Key(vec![191]), 116),
Restart,
Del(Key(vec![165])),
],
true,
0,
256,
);
}
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_14() {
// postmortem: after adding prefix compression, we were not
// handling re-inserts and deletions properly
prop_tree_matches_btreemap(
vec![
Set(Key(vec![107]), 234),
Set(Key(vec![7]), 245),
Set(Key(vec![40]), 77),
Set(Key(vec![171]), 244),
Set(Key(vec![173]), 16),
Set(Key(vec![171]), 176),
Scan(Key(vec![93]), 33),
],
true,
0,
256,
);
}
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_15() {
// postmortem: was not sorting keys properly when binary searching for them
prop_tree_matches_btreemap(
vec![
Set(Key(vec![102]), 165),
Set(Key(vec![91]), 191),
Set(Key(vec![141]), 228),
Set(Key(vec![188]), 124),
Del(Key(vec![141])),
Scan(Key(vec![101]), 26),
],
true,
0,
256,
);
}
/*
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_16() {
// postmortem: the test merge function was not properly adding numbers.
prop_tree_matches_btreemap(
vec![Merge(Key(vec![247]), 162), Scan(Key(vec![209]), 31)],
false,
0,
256
);
}
*/
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_17() {
// postmortem: we were creating a copy of a node leaf during iteration
// before accidentally putting it into a PinnedValue, despite the
// fact that it was not actually part of the node's actual memory!
prop_tree_matches_btreemap(
vec![
Set(Key(vec![194, 215, 103, 0, 138, 11, 248, 131]), 70),
Scan(Key(vec![]), 30),
],
false,
0,
256,
);
}
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_18() {
// postmortem: when implementing get_gt and get_lt, there were some
// issues with getting order comparisons correct.
prop_tree_matches_btreemap(
vec![
Set(Key(vec![]), 19),
Set(Key(vec![78]), 98),
Set(Key(vec![255]), 224),
Set(Key(vec![]), 131),
Get(Key(vec![255])),
GetGt(Key(vec![89])),
],
false,
0,
256,
);
}
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_19() {
// postmortem: we were not seeking properly to the next node
// when we hit a half-split child and were using get_lt
prop_tree_matches_btreemap(
vec![
Set(Key(vec![]), 138),
Set(Key(vec![68]), 113),
Set(Key(vec![155]), 73),
Set(Key(vec![50]), 220),
Set(Key(vec![]), 247),
GetLt(Key(vec![100])),
],
false,
0,
256,
);
}
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_20() {
// postmortem: we were not seeking forward during get_gt
// if path_for_key reached a leaf that didn't include
// a key for our
prop_tree_matches_btreemap(
vec![
Set(Key(vec![]), 10),
Set(Key(vec![56]), 42),
Set(Key(vec![138]), 27),
Set(Key(vec![155]), 73),
Set(Key(vec![]), 251),
GetGt(Key(vec![94])),
],
false,
0,
256,
);
}
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_21() {
// postmortem: more split woes while implementing get_lt
// postmortem 2: failed to properly account for node hi key
// being empty in the view predecessor function
// postmortem 3: when rewriting Iter, failed to account for
// direction of iteration
prop_tree_matches_btreemap(
vec![
Set(Key(vec![176]), 163),
Set(Key(vec![]), 229),
Set(Key(vec![169]), 121),
Set(Key(vec![]), 58),
GetLt(Key(vec![176])),
],
false,
0,
256,
);
}
/*
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_22() {
// postmortem: inclusivity wasn't being properly flipped off after
// the first result during iteration
// postmortem 2: failed to properly check bounds while iterating
prop_tree_matches_btreemap(
vec![
Merge(Key(vec![]), 155),
Merge(Key(vec![56]), 251),
Scan(Key(vec![]), 2),
],
false,
0,
256,
);
}
*/
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_23() {
// postmortem: when rewriting CRC handling code, mis-sized the blob crc
prop_tree_matches_btreemap(
vec![Set(Key(vec![6; 5120]), 92), Restart, Scan(Key(vec![]), 35)],
false,
0,
256,
);
}
/*
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_24() {
// postmortem: get_gt diverged with the Iter impl
prop_tree_matches_btreemap(
vec![
Merge(Key(vec![]), 193),
Del(Key(vec![])),
Del(Key(vec![])),
Set(Key(vec![]), 55),
Set(Key(vec![]), 212),
Merge(Key(vec![]), 236),
Del(Key(vec![])),
Set(Key(vec![]), 192),
Del(Key(vec![])),
Set(Key(vec![94]), 115),
Merge(Key(vec![62]), 34),
GetGt(Key(vec![])),
],
false,
0,
256,
);
}
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_25() {
// postmortem: was not accounting for merges when traversing
// the frag chain and a Del was encountered
prop_tree_matches_btreemap(
vec![Del(Key(vec![])), Merge(Key(vec![]), 84), Get(Key(vec![]))],
false,
0,
256,
);
}
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_26() {
// postmortem:
prop_tree_matches_btreemap(
vec![
Merge(Key(vec![]), 194),
Merge(Key(vec![62]), 114),
Merge(Key(vec![80]), 202),
Merge(Key(vec![]), 169),
Set(Key(vec![]), 197),
Del(Key(vec![])),
Del(Key(vec![])),
Set(Key(vec![]), 215),
Set(Key(vec![]), 164),
Merge(Key(vec![]), 150),
GetGt(Key(vec![])),
GetLt(Key(vec![80])),
],
false,
0,
256,
);
}
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_27() {
// postmortem: was not accounting for the fact that deletions reduce the
// chances of being able to split successfully.
prop_tree_matches_btreemap(
vec![
Del(Key(vec![])),
Merge(
Key(vec![
74, 117, 68, 37, 89, 16, 84, 130, 133, 78, 74, 59, 44, 109,
34, 5, 36, 74, 131, 100, 79, 86, 87, 107, 87, 27, 1, 85,
53, 112, 89, 75, 67, 78, 58, 121, 0, 105, 8, 117, 79, 40,
94, 123, 83, 72, 78, 23, 23, 35, 50, 77, 59, 75, 54, 92,
89, 12, 27, 48, 64, 21, 42, 97, 45, 28, 122, 13, 4, 32, 51,
25, 26, 18, 65, 12, 54, 104, 106, 80, 75, 91, 111, 9, 5,
130, 43, 40, 3, 72, 0, 58, 92, 64, 112, 97, 75, 130, 11,
135, 19, 107, 40, 17, 25, 49, 48, 119, 82, 54, 35, 113, 91,
68, 12, 118, 123, 62, 108, 88, 67, 43, 33, 119, 132, 124,
1, 62, 133, 110, 25, 62, 129, 117, 117, 107, 123, 94, 127,
80, 0, 116, 101, 9, 9, 54, 134, 70, 66, 79, 50, 124, 115,
85, 42, 120, 24, 15, 81, 100, 72, 71, 40, 58, 22, 6, 34,
54, 69, 110, 18, 74, 111, 80, 52, 90, 44, 4, 29, 84, 95,
21, 25, 10, 10, 60, 18, 78, 23, 21, 114, 92, 96, 17, 127,
53, 86, 2, 60, 104, 8, 132, 44, 115, 6, 25, 80, 46, 12, 20,
44, 67, 136, 127, 50, 55, 70, 41, 90, 16, 10, 44, 32, 24,
106, 13, 104,
]),
219,
),
Merge(Key(vec![]), 71),
Del(Key(vec![])),
Set(Key(vec![0]), 146),
Merge(Key(vec![13]), 155),
Merge(Key(vec![]), 14),
Del(Key(vec![])),
Set(Key(vec![]), 150),
Set(
Key(vec![
13, 8, 3, 6, 9, 14, 3, 13, 7, 12, 13, 7, 13, 13, 1, 13, 5,
4, 3, 2, 6, 16, 17, 10, 0, 16, 12, 0, 16, 1, 0, 15, 15, 4,
1, 6, 9, 9, 11, 16, 7, 6, 10, 1, 11, 10, 4, 9, 9, 14, 4,
12, 16, 10, 15, 2, 1, 8, 4,
]),
247,
),
Del(Key(vec![154])),
Del(Key(vec![])),
Del(Key(vec![
0, 24, 24, 31, 40, 23, 10, 30, 16, 41, 30, 23, 14, 25, 21, 19,
18, 7, 17, 41, 11, 5, 14, 42, 11, 22, 4, 8, 4, 38, 33, 31, 3,
30, 40, 22, 40, 39, 5, 40, 1, 41, 11, 26, 25, 33, 12, 38, 4,
35, 30, 42, 19, 26, 23, 22, 39, 18, 29, 4, 1, 24, 14, 38, 0,
36, 27, 11, 27, 34, 16, 15, 38, 0, 20, 37, 22, 31, 12, 26, 16,
4, 22, 25, 4, 34, 4, 33, 37, 28, 18, 4, 41, 15, 8, 16, 27, 3,
20, 26, 40, 31, 15, 15, 17, 15, 5, 13, 22, 37, 7, 13, 35, 14,
6, 28, 21, 26, 13, 35, 1, 10, 8, 34, 23, 27, 29, 8, 14, 42, 36,
31, 34, 12, 31, 24, 5, 8, 11, 36, 29, 24, 38, 8, 12, 18, 22,
36, 21, 28, 11, 24, 0, 41, 37, 39, 42, 25, 13, 41, 27, 8, 24,
22, 30, 17, 2, 4, 20, 33, 5, 24, 33, 6, 29, 5, 0, 17, 9, 20,
26, 15, 23, 22, 16, 23, 16, 1, 20, 0, 28, 16, 34, 30, 19, 5,
36, 40, 28, 6, 39,
])),
Merge(Key(vec![]), 50),
],
false,
0,
256,
);
}
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_28() {
// postmortem:
prop_tree_matches_btreemap(
vec![
Del(Key(vec![])),
Set(Key(vec![]), 65),
Del(Key(vec![])),
Del(Key(vec![])),
Merge(Key(vec![]), 50),
Merge(Key(vec![]), 2),
Del(Key(vec![197])),
Merge(Key(vec![5]), 146),
Set(Key(vec![222]), 224),
Merge(Key(vec![149]), 60),
Scan(Key(vec![178]), 18),
],
false,
0,
256,
);
}
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_29() {
// postmortem: tree merge and split thresholds caused an infinite
// loop while performing updates
prop_tree_matches_btreemap(
vec![
Set(Key(vec![]), 142),
Merge(
Key(vec![
45, 47, 6, 67, 16, 12, 62, 35, 69, 80, 49, 61, 29, 82, 9,
47, 25, 78, 47, 64, 29, 74, 45, 0, 37, 44, 21, 82, 55, 44,
31, 60, 86, 18, 45, 67, 55, 21, 35, 46, 25, 51, 5, 32, 33,
36, 1, 81, 28, 28, 79, 76, 80, 89, 80, 62, 8, 85, 50, 15,
4, 11, 76, 72, 73, 47, 30, 50, 85, 67, 84, 13, 82, 84, 78,
70, 42, 83, 8, 7, 50, 77, 85, 37, 47, 82, 86, 46, 30, 27,
5, 39, 70, 26, 59, 16, 6, 34, 56, 40, 40, 67, 16, 61, 63,
56, 64, 31, 15, 81, 84, 19, 61, 66, 3, 7, 40, 56, 13, 40,
64, 50, 88, 47, 88, 50, 63, 65, 79, 62, 1, 44, 59, 27, 12,
60, 3, 36, 89, 45, 18, 4, 68, 48, 61, 30, 48, 26, 84, 49,
3, 74, 51, 53, 30, 57, 50, 35, 74, 59, 30, 73, 19, 30, 82,
78, 3, 5, 62, 17, 48, 29, 67, 52, 45, 61, 74, 52, 29, 61,
63, 11, 89, 76, 34, 8, 50, 75, 42, 12, 5, 55, 0, 59, 44,
68, 26, 76, 37, 50, 53, 73, 53, 76, 57, 40, 30, 52, 0, 41,
21, 8, 79, 79, 38, 37, 50, 56, 43, 9, 85, 21, 60, 64, 13,
54, 60, 83, 1, 2, 37, 75, 42, 0, 83, 81, 80, 87, 12, 15,
75, 55, 41, 59, 9, 80, 66, 27, 65, 26, 48, 29, 37, 38, 9,
76, 31, 39, 35, 22, 73, 59, 28, 33, 35, 63, 78, 17, 22, 82,
12, 60, 49, 26, 54, 19, 60, 29, 39, 37, 10, 50, 12, 19, 29,
1, 74, 12, 5, 38, 49, 41, 19, 88, 3, 27, 77, 81, 72, 42,
71, 86, 82, 11, 79, 40, 35, 26, 35, 64, 4, 33, 87, 31, 84,
81, 74, 31, 49, 0, 29, 73, 14, 55, 78, 21, 23, 20, 83, 48,
89, 88, 62, 64, 73, 7, 20, 70, 81, 64, 3, 79, 38, 75, 13,
40, 29, 82, 40, 14, 66, 56, 54, 52, 37, 14, 67, 8, 37, 1,
5, 73, 14, 35, 63, 48, 46, 22, 84, 71, 2, 60, 63, 88, 14,
15, 69, 88, 2, 43, 57, 43, 52, 18, 78, 75, 75, 74, 13, 35,
50, 35, 17, 13, 64, 82, 55, 32, 14, 57, 35, 77, 65, 22, 40,
27, 39, 80, 23, 20, 41, 50, 48, 22, 84, 37, 59, 45, 64, 10,
3, 69, 56, 24, 4, 25, 76, 65, 47, 52, 64, 88, 3, 23, 37,
16, 56, 69, 71, 27, 87, 65, 74, 23, 82, 41, 60, 78, 75, 22,
51, 15, 57, 80, 46, 73, 7, 1, 36, 64, 0, 56, 83, 74, 62,
73, 81, 68, 71, 63, 31, 5, 23, 11, 15, 39, 2, 10, 23, 18,
74, 3, 43, 25, 68, 54, 11, 21, 14, 58, 10, 73, 0, 66, 28,
73, 25, 40, 55, 56, 33, 81, 67, 43, 35, 65, 38, 21, 48, 81,
4, 77, 68, 51, 38, 36, 49, 43, 33, 51, 28, 43, 60, 71, 78,
48, 49, 76, 21, 0, 72, 0, 32, 78, 12, 87, 5, 80, 62, 40,
85, 26, 70, 58, 56, 78, 7, 53, 30, 16, 22, 12, 23, 37, 83,
45, 33, 41, 83, 78, 87, 44, 0, 65, 51, 3, 8, 72, 38, 14,
24, 64, 77, 45, 5, 1, 7, 27, 82, 7, 6, 70, 25, 67, 22, 8,
30, 76, 41, 11, 14, 1, 65, 85, 60, 80, 0, 30, 31, 79, 43,
89, 33, 84, 22, 7, 67, 45, 39, 74, 75, 12, 61, 19, 71, 66,
83, 57, 38, 45, 21, 18, 37, 54, 36, 14, 54, 63, 81, 12, 7,
10, 39, 16, 40, 10, 7, 81, 45, 12, 22, 20, 29, 85, 40, 41,
72, 79, 58, 50, 41, 59, 64, 41, 32, 56, 35, 8, 60, 17, 14,
89, 17, 7, 48, 6, 35, 9, 34, 54, 6, 44, 87, 76, 50, 1, 67,
70, 15, 8, 4, 45, 67, 86, 32, 69, 3, 88, 85, 72, 66, 21,
89, 11, 77, 1, 50, 75, 56, 41, 74, 6, 4, 51, 65, 39, 50,
45, 56, 3, 19, 80, 86, 55, 48, 81, 17, 3, 89, 7, 9, 63, 58,
80, 39, 34, 85, 55, 71, 41, 55, 8, 63, 38, 51, 47, 49, 83,
2, 73, 22, 39, 18, 45, 77, 56, 80, 54, 13, 23, 81, 54, 15,
48, 57, 83, 71, 41, 32, 64, 1, 9, 46, 27, 16, 21, 7, 28,
55, 17, 71, 68, 17, 74, 46, 38, 84, 3, 12, 71, 63, 16, 23,
48, 12, 29, 28, 5, 21, 61, 14, 77, 66, 62, 57, 18, 30, 63,
14, 41, 37, 30, 73, 16, 12, 74, 8, 82, 67, 53, 10, 5, 37,
36, 39, 52, 37, 72, 76, 21, 35, 40, 42, 55, 47, 50, 41, 19,
40, 86, 26, 54, 23, 74, 46, 66, 59, 80, 26, 81, 61, 80, 88,
55, 40, 30, 45, 7, 46, 21, 3, 20, 46, 63, 18, 9, 34, 67, 9,
19, 52, 53, 29, 69, 78, 65, 39, 71, 40, 38, 57, 80, 27, 34,
30, 27, 55, 8, 65, 31, 37, 33, 25, 39, 46, 9, 83, 6, 27,
28, 61, 9, 21, 58, 21, 10, 69, 24, 5, 31, 32, 44, 26, 84,
73, 73, 9, 64, 26, 21, 85, 12, 39, 81, 38, 49, 24, 35, 3,
88, 15, 15, 76, 64, 70, 9, 30, 51, 26, 16, 70, 60, 15, 7,
54, 36, 32, 9, 10, 18, 66, 19, 25, 77, 46, 51, 51, 14, 41,
56, 65, 41, 87, 26, 10, 2, 73, 2, 71, 26, 56, 10, 68, 15,
53, 10, 43, 15, 22, 45, 2, 15, 16, 69, 80, 83, 18, 22, 70,
77, 52, 48, 24, 17, 40, 56, 22, 17, 3, 36, 46, 37, 41, 22,
0, 41, 45, 14, 15, 73, 18, 42, 34, 5, 87, 6, 2, 7, 58, 3,
86, 87, 7, 79, 88, 33, 30, 48, 3, 66, 27, 34, 58, 48, 71,
40, 1, 46, 84, 32, 63, 79, 0, 21, 71, 1, 59, 39, 77, 51,
14, 20, 58, 83, 19, 0, 2, 2, 57, 73, 79, 42, 59, 33, 50,
15, 11, 48, 25, 14, 39, 36, 88, 71, 28, 45, 15, 59, 39, 60,
78, 18, 18, 45, 50, 29, 66, 86, 5, 76, 85, 55, 17, 28, 8,
39, 75, 33, 9, 73, 71, 59, 56, 57, 86, 6, 75, 26, 43, 68,
34, 82, 88, 76, 17, 86, 63, 2, 38, 63, 13, 44, 8, 25, 0,
63, 54, 73, 52, 3, 72,
]),
9,
),
Set(Key(vec![]), 35),
Set(
Key(vec![
165, 64, 99, 55, 152, 102, 148, 35, 59, 10, 198, 191, 71,
129, 170, 155, 7, 106, 171, 93, 126,
]),
212,
),
Del(Key(vec![])),
Merge(Key(vec![]), 177),
Merge(
Key(vec![
20, 55, 154, 104, 10, 68, 64, 3, 31, 78, 232, 227, 169,
161, 13, 50, 16, 239, 87, 0, 9, 85, 248, 32, 156, 106, 11,
18, 57, 13, 177, 36, 69, 176, 101, 92, 119, 38, 218, 26, 4,
154, 185, 135, 75, 167, 101, 107, 206, 76, 153, 213, 70,
52, 205, 95, 55, 116, 242, 68, 77, 90, 249, 142, 93, 135,
118, 127, 116, 121, 235, 183, 215, 2, 118, 193, 146, 185,
4, 129, 167, 164, 178, 105, 149, 47, 73, 121, 95, 23, 216,
153, 23, 108, 141, 190, 250, 121, 98, 229, 33, 106, 89,
117, 122, 145, 47, 242, 81, 88, 141, 38, 177, 170, 167, 56,
24, 196, 61, 97, 83, 91, 202, 181, 75, 112, 3, 169, 61, 17,
100, 81, 111, 178, 122, 176, 95, 185, 169, 146, 239, 40,
168, 32, 170, 34, 172, 89, 59, 188, 170, 186, 61, 7, 177,
230, 130, 155, 208, 171, 82, 153, 20, 72, 74, 111, 147,
178, 164, 157, 71, 114, 216, 40, 85, 91, 20, 145, 149, 95,
36, 114, 24, 129, 144, 229, 14, 133, 77, 92, 139, 167, 48,
18, 178, 4, 15, 171, 171, 88, 74, 104, 157, 2, 121, 13,
141, 6, 107, 118, 228, 147, 152, 28, 206, 128, 102, 150, 1,
129, 84, 171, 119, 110, 198, 72, 100, 166, 153, 98, 66,
128, 79, 41, 126,
]),
103,
),
Del(Key(vec![])),
Merge(
Key(vec![
117, 48, 90, 153, 149, 191, 229, 73, 3, 6, 73, 52, 73, 186,
42, 53, 94, 17, 61, 11, 153, 118, 219, 188, 184, 89, 13,
124, 138, 40, 238, 9, 46, 45, 38, 115, 153, 106, 166, 56,
134, 206, 140, 57, 95, 244, 27, 135, 43, 13, 143, 137, 56,
122, 243, 205, 52, 116, 130, 35, 80, 167, 58, 93,
]),
8,
),
Set(Key(vec![145]), 43),
GetLt(Key(vec![229])),
],
false,
0,
256,
);
}
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_30() {
// postmortem:
prop_tree_matches_btreemap(
vec![
Merge(Key(vec![]), 241),
Set(Key(vec![20]), 146),
Merge(
Key(vec![
60, 38, 29, 57, 35, 71, 15, 46, 7, 27, 76, 84, 27, 25, 90,
30, 37, 63, 11, 24, 27, 28, 94, 93, 82, 68, 69, 61, 46, 86,
11, 86, 63, 34, 90, 71, 92, 87, 38, 48, 40, 78, 9, 37, 26,
36, 60, 4, 2, 38, 32, 73, 86, 43, 52, 79, 11, 43, 59, 21,
60, 40, 80, 94, 69, 44, 4, 73, 59, 16, 16, 22, 88, 41, 13,
21, 91, 33, 49, 91, 20, 79, 23, 61, 53, 63, 58, 62, 49, 10,
71, 72, 27, 55, 53, 39, 91, 82, 86, 38, 41, 1, 54, 3, 77,
15, 93, 31, 49, 29, 82, 7, 17, 58, 42, 12, 49, 67, 62, 46,
20, 27, 61, 32, 58, 9, 17, 19, 28, 44, 41, 34, 94, 11, 50,
73, 1, 50, 48, 8, 88, 33, 40, 51, 15, 35, 2, 36, 37, 30,
37, 83, 71, 91, 32, 0, 69, 28, 64, 30, 72, 63, 39, 7, 89,
0, 21, 51, 92, 80, 13, 57, 7, 53, 94, 26, 2, 63, 18, 23,
89, 34, 83, 55, 32, 75, 81, 27, 11, 5, 63, 0, 75, 12, 39,
9, 13, 20, 25, 57, 94, 75, 59, 46, 84, 80, 61, 24, 31, 7,
68, 93, 12, 94, 6, 94, 27, 33, 81, 19, 3, 78, 3, 14, 22,
36, 49, 61, 51, 79, 43, 35, 58, 54, 65, 72, 36, 87, 3, 3,
25, 75, 82, 58, 75, 76, 29, 89, 1, 16, 64, 63, 85, 0, 47,
]),
11,
),
Merge(Key(vec![25]), 245),
Merge(Key(vec![119]), 152),
Scan(Key(vec![]), 31),
],
false,
0,
256,
);
}
*/
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_31() {
// postmortem:
prop_tree_matches_btreemap(
vec![
Set(Key(vec![1]), 212),
Set(Key(vec![12]), 174),
Set(Key(vec![]), 182),
Set(
Key(vec![
12, 55, 46, 38, 40, 34, 44, 32, 19, 15, 28, 49, 35, 40, 55,
35, 61, 9, 62, 18, 3, 58,
]),
86,
),
Scan(Key(vec![]), -18),
],
false,
0,
256,
);
}
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_32() {
// postmortem: the MAX_IVEC that predecessor used in reverse
// iteration was setting the first byte to 0 even though we
// no longer perform per-key prefix encoding.
prop_tree_matches_btreemap(
vec![Set(Key(vec![57]), 141), Scan(Key(vec![]), -40)],
false,
0,
256,
);
}
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_33() {
// postmortem: the split point was being incorrectly
// calculated when using the simplified prefix technique.
prop_tree_matches_btreemap(
vec![
Set(Key(vec![]), 91),
Set(Key(vec![1]), 216),
Set(Key(vec![85, 25]), 78),
Set(Key(vec![85]), 43),
GetLt(Key(vec![])),
],
false,
0,
256,
);
}
/*
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_34() {
// postmortem: a safety check was too aggressive when
// finding predecessors using the new simplified prefix
// encoding technique.
prop_tree_matches_btreemap(
vec![
Set(Key(vec![9, 212]), 100),
Set(Key(vec![9]), 63),
Set(Key(vec![5]), 100),
Merge(Key(vec![]), 16),
Set(Key(vec![9, 70]), 188),
Scan(Key(vec![]), -40),
],
false,
0,
256,
);
}
*/
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_35() {
// postmortem: prefix lengths were being incorrectly
// handled on splits.
prop_tree_matches_btreemap(
vec![
Set(Key(vec![207]), 29),
Set(Key(vec![192]), 218),
Set(Key(vec![121]), 167),
Set(Key(vec![189]), 40),
Set(Key(vec![85]), 197),
Set(Key(vec![185]), 58),
Set(Key(vec![84]), 97),
Set(Key(vec![23]), 34),
Set(Key(vec![47]), 162),
Set(Key(vec![39]), 92),
Set(Key(vec![46]), 173),
Set(Key(vec![33]), 202),
Set(Key(vec![8]), 113),
Set(Key(vec![17]), 228),
Set(Key(vec![8, 49]), 217),
Set(Key(vec![6]), 192),
Set(Key(vec![5]), 47),
Set(Key(vec![]), 5),
Set(Key(vec![0]), 103),
Set(Key(vec![1]), 230),
Set(Key(vec![0, 229]), 117),
Set(Key(vec![]), 112),
],
false,
0,
256,
);
}
/*
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_36() {
// postmortem: suffix truncation caused
// regions to be permanently inaccessible
// when applied to split points on index
// nodes.
prop_tree_matches_btreemap(
vec![
Set(Key(vec![152]), 65),
Set(Key(vec![]), 227),
Set(Key(vec![101]), 23),
Merge(Key(vec![254]), 97),
Set(Key(vec![254, 5]), 207),
Scan(Key(vec![]), -30),
],
false,
0,
256,
);
}
*/
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_37() {
// postmortem: suffix truncation was so
// aggressive that it would cut into
// the prefix in the lo key sometimes.
prop_tree_matches_btreemap(
vec![
Set(Key(vec![]), 82),
Set(Key(vec![2, 0]), 40),
Set(Key(vec![2, 0, 0]), 49),
Set(Key(vec![1]), 187),
Scan(Key(vec![]), 33),
],
false,
0,
256,
);
}
/*
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_38() {
// postmortem: Free pages were not being initialized in the
// pagecache properly.
for _ in 0..10 {
prop_tree_matches_btreemap(
vec![
Set(Key(vec![193]), 73),
Merge(Key(vec![117]), 216),
Set(Key(vec![221]), 176),
GetLt(Key(vec![123])),
Restart,
],
false,
0,
256,
);
}
}
*/
/*
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_39() {
// postmortem:
for _ in 0..100 {
prop_tree_matches_btreemap(
vec![
Set(
Key(vec![
67, 48, 34, 254, 61, 189, 196, 127, 26, 185, 244, 63,
60, 63, 246, 194, 243, 177, 218, 210, 153, 126, 124,
47, 160, 242, 157, 2, 51, 34, 88, 41, 44, 65, 58, 211,
245, 74, 192, 101, 222, 68, 196, 250, 127, 231, 102,
177, 246, 105, 190, 144, 113, 148, 71, 72, 149, 246,
38, 95, 106, 42, 83, 65, 84, 73, 148, 34, 95, 88, 57,
232, 219, 227, 74, 14, 5, 124, 106, 57, 244, 50, 81,
93, 145, 111, 40, 190, 127, 227, 17, 242, 165, 194,
171, 60, 6, 255, 176, 143, 131, 164, 217, 18, 123, 19,
246, 183, 29, 0, 6, 39, 175, 57, 134, 166, 231, 47,
254, 158, 163, 178, 78, 240, 108, 157, 72, 135, 34,
236, 103, 192, 109, 31, 2, 72, 128, 242, 4, 113, 109,
224, 120, 61, 169, 226, 131, 210, 33, 181, 91, 91, 197,
223, 127, 26, 94, 158, 55, 57, 3, 184, 15, 30, 2, 222,
39, 29, 12, 42, 14, 166, 176, 28, 13, 246, 11, 186, 8,
247, 113, 253, 102, 227, 68, 111, 227, 238, 54, 150,
11, 57, 155, 4, 75, 179, 17, 172, 42, 22, 199, 44, 242,
211, 0, 39, 243, 221, 114, 86, 145, 22, 226, 108, 32,
248, 42, 49, 191, 112, 1, 69, 101, 112, 251, 243, 252,
83, 140, 132, 165,
]),
250,
),
Del(Key(vec![
11, 77, 168, 37, 181, 169, 239, 146, 240, 211, 7, 115, 197,
119, 46, 80, 240, 92, 221, 108, 208, 247, 221, 129, 108,
13, 36, 21, 93, 11, 243, 103, 188, 39, 126, 77, 29, 32,
206, 175, 199, 245, 71, 96, 221, 7, 68, 64, 45, 78, 68,
193, 73, 13, 60, 13, 28, 167, 147, 7, 90, 11, 206, 44, 84,
243, 3, 77, 122, 87, 7, 125, 184, 6, 178, 59,
])),
Merge(Key(vec![176]), 123),
Restart,
Merge(
Key(vec![
93, 43, 181, 76, 63, 247, 227, 15, 17, 239, 9, 252,
181, 53, 65, 74, 22, 18, 71, 64, 115, 58, 110, 30, 13,
177, 31, 47, 124, 14, 0, 157, 200, 194, 92, 215, 21,
36, 239, 204, 18, 88, 216, 149, 18, 208, 187, 188, 32,
76, 35, 12, 142, 157, 38, 186, 245, 63, 2, 230, 13, 79,
160, 86, 32, 170, 239, 151, 25, 180, 170, 201, 22, 211,
238, 208, 24, 139, 5, 44, 38, 48, 243, 38, 249, 36, 43,
200, 52, 244, 166, 0, 29, 114, 10, 18, 253, 253, 130,
223, 37, 8, 109, 228, 0, 122, 192, 16, 68, 231, 37,
230, 249, 180, 214, 101, 17,
]),
176,
),
Set(
Key(vec![
153, 217, 142, 179, 255, 74, 1, 20, 254, 1, 38, 28, 66,
244, 81, 101, 210, 58, 18, 107, 12, 116, 74, 188, 95,
56, 248, 9, 204, 128, 24, 239, 143, 83, 83, 213, 17,
32, 135, 73, 217, 8, 241, 44, 57, 131, 107, 139, 122,
32, 194, 225, 136, 148, 227, 196, 196, 121, 97, 81, 74,
]),
42,
),
Set(Key(vec![]), 160),
GetLt(Key(vec![
244, 145, 243, 120, 149, 64, 125, 161, 98, 205, 205, 107,
191, 119, 83, 42, 92, 119, 25, 198, 47, 123, 26, 224, 190,
98, 144, 238, 74, 36, 76, 186, 226, 153, 69, 217, 109, 214,
201, 104, 148, 107, 132, 219, 37, 109, 98, 172, 70, 160,
177, 115, 194, 80, 76, 60, 148, 176, 191, 84, 109, 35, 51,
107, 157, 11, 233, 126, 71, 183, 215, 116, 72, 235, 218,
171, 233, 181, 53, 253, 104, 231, 138, 166, 40,
])),
Set(
Key(vec![
37, 160, 29, 162, 43, 212, 2, 100, 236, 24, 2, 82, 58,
38, 81, 137, 89, 55, 164, 83,
]),
64,
),
Get(Key(vec![
15, 53, 101, 33, 156, 199, 212, 82, 2, 64, 136, 70, 235,
72, 170, 188, 180, 200, 109, 231, 6, 13, 30, 70, 4, 132,
133, 101, 82, 187, 78, 241, 157, 49, 156, 3, 17, 167, 216,
209, 7, 174, 112, 186, 170, 189, 85, 99, 119, 52, 39, 38,
151, 108, 203, 42, 63, 255, 216, 234, 34, 2, 80, 168, 122,
70, 20, 11, 220, 106, 49, 110, 165, 170, 149, 163,
])),
GetLt(Key(vec![])),
Merge(Key(vec![136]), 135),
Cas(Key(vec![177]), 159, 209),
Cas(Key(vec![101]), 143, 240),
Set(Key(vec![226, 62, 34, 63, 172, 96, 162]), 43),
Merge(
Key(vec![
48, 182, 144, 255, 137, 100, 2, 139, 69, 111, 159, 133,
234, 147, 118, 231, 155, 74, 73, 98, 58, 36, 35, 21,
50, 42, 71, 25, 200, 5, 4, 198, 158, 41, 88, 75, 153,
254, 248, 213, 0, 89, 43, 160, 58, 206, 88, 107, 57,
208, 119, 34, 80, 166, 112, 13, 241, 46, 172, 115, 179,
42, 59, 200, 225, 125, 65, 18, 173, 77, 27, 129, 228,
68, 53, 175, 61, 230, 27, 136, 131, 171, 64, 79, 125,
149, 52, 80,
]),
105,
),
Merge(
Key(vec![
126, 109, 165, 43, 2, 82, 97, 81, 59, 78, 243, 142, 37,
105, 109, 178, 25, 73, 50, 103, 107, 129, 213, 193,
158, 16, 63, 108, 160, 204, 78, 83, 2, 43, 66, 2, 18,
11, 147, 47, 106, 106, 141, 82, 65, 101, 99, 171, 178,
68, 106, 7, 190, 159, 105, 132, 155, 240, 155, 95, 66,
254, 239, 202, 168, 26, 207, 213, 116, 215, 141, 77, 7,
245, 174, 144, 39, 28,
]),
122,
),
Del(Key(vec![
13, 152, 171, 90, 130, 131, 232, 51, 173, 103, 255, 225,
156, 192, 146, 141, 94, 84, 39, 171, 152, 114, 133, 20,
125, 68, 57, 27, 33, 175, 37, 164, 40,
])),
Scan(Key(vec![]), -34),
Set(Key(vec![]), 85),
Merge(Key(vec![112]), 104),
Restart,
Restart,
Del(Key(vec![237])),
Set(
Key(vec![
53, 79, 71, 234, 187, 78, 206, 117, 48, 84, 162, 101,
132, 137, 43, 144, 234, 23, 116, 13, 28, 184, 174, 241,
181, 201, 131, 156, 7, 103, 135, 17, 168, 249, 7, 120,
74, 8, 192, 134, 109, 54, 175, 130, 145, 206, 185, 49,
144, 133, 226, 244, 42, 126, 176, 232, 96, 56, 70, 56,
159, 127, 35, 39, 185, 114, 182, 41, 50, 93, 61,
]),
144,
),
Merge(
Key(vec![
10, 58, 6, 62, 17, 15, 26, 29, 79, 34, 77, 12, 93, 65,
87, 71, 19, 57, 25, 40, 53, 73, 57, 2, 81, 49, 67, 62,
78, 14, 34, 70, 86, 49, 86, 84, 16, 33, 24, 7, 87, 49,
58, 50, 13, 14, 35, 46, 7, 39, 76, 51, 21, 76, 9, 53,
45, 21, 71, 48, 16, 73, 68, 1, 63, 34, 12, 42, 11, 85,
79, 19, 11, 77, 90, 0, 62, 56, 37, 33, 10, 69, 20, 64,
15, 51, 64, 90, 69, 15, 7, 41, 53, 71, 52, 21, 45, 45,
49, 3, 59, 15, 90, 7, 12, 62, 30, 81,
]),
131,
),
Get(Key(vec![
79, 28, 48, 41, 5, 70, 54, 56, 36, 32, 59, 15, 26, 42, 61,
23, 53, 6, 71, 44, 61, 65, 4, 17, 23, 15, 65, 64, 46, 66,
27, 63, 51, 44, 35, 1, 8, 70, 7, 1, 13, 10, 40, 6, 36, 64,
68, 52, 8, 0, 46, 53, 48, 32, 9, 52, 69, 41, 8, 57, 27, 31,
79, 27, 12, 70, 72, 33, 6, 22, 47, 37, 11, 38, 32, 7, 31,
37, 45, 23, 74, 22, 46, 1, 3, 74, 72, 56, 52, 65, 78, 28,
5, 68, 30, 36, 5, 43, 7, 2, 48, 75, 16, 53, 31, 40, 9, 3,
49, 71, 70, 20, 24, 6, 23, 76, 49, 21, 12, 60, 54, 43, 7,
79, 74, 62, 53, 20, 46, 11, 74, 29, 31, 43, 20, 27, 22, 22,
15, 59, 12, 21, 61, 11, 8, 28, 5, 78, 70, 22, 11, 36, 62,
56, 44, 49, 25, 39, 37, 24, 72, 65, 67, 22, 48, 16, 50, 5,
10, 13, 36, 65, 29, 3, 26, 74, 15, 73, 78, 36, 14, 36, 30,
42, 19, 73, 65, 75, 2, 25, 1, 32, 38, 43, 58, 19, 37, 37,
48, 23, 72, 77, 34, 24, 1, 4, 42, 11, 68, 54, 23, 34, 0,
48, 20, 20, 23, 61, 65, 72, 64, 24, 63, 3, 21, 48, 63, 57,
40, 36, 46, 48, 8, 20, 62, 7, 69, 35, 79, 38, 45, 74, 7,
16, 48, 59, 56, 31, 13, 13,
])),
Del(Key(vec![176, 58, 119])),
Get(Key(vec![241])),
Get(Key(vec![160])),
Cas(Key(vec![]), 166, 235),
Set(
Key(vec![
64, 83, 151, 149, 100, 93, 5, 18, 91, 58, 84, 156, 127,
108, 99, 168, 54, 51, 169, 185, 174, 101, 178, 148, 28,
91, 25, 138, 14, 133, 170, 97, 138, 180, 157, 131, 174,
22, 91, 108, 59, 165, 52, 28, 17, 175, 44, 95, 112, 38,
141, 46, 124, 49, 116, 55, 39, 109, 73, 181, 104, 86,
81, 150, 95, 149, 69, 110, 110, 102, 22, 62, 180, 60,
87, 127, 127, 136, 12, 139, 109, 165, 34, 181, 158,
156, 102, 38, 6, 149, 183, 69, 129, 98, 161, 175, 82,
51, 47, 93, 136, 16, 118, 65, 152, 139, 8, 30, 10, 100,
47, 13, 47, 179, 87, 19, 109, 78, 116, 20, 111, 89, 28,
0, 86, 39, 139, 7, 111, 40, 145, 155, 107, 45, 36, 90,
143, 154, 135, 36, 13, 98, 61, 150, 65, 128, 16, 52,
100, 128, 11, 5, 49, 143, 56, 78, 48, 62, 86, 50, 86,
41, 153, 53, 139, 89, 164, 33, 136, 83, 182, 53, 132,
144, 177, 105, 104, 55, 9, 174, 30, 65, 76, 33, 163,
172, 80, 169, 175, 54, 165, 173, 109, 24, 70, 25, 158,
135, 76, 130, 76, 9, 56, 20, 13, 133, 33, 168, 160,
153, 43, 80, 58, 56, 171, 28, 97, 122, 162, 32, 164,
11, 112, 177, 63, 47, 25, 0, 66, 87, 169, 118, 173, 27,
154, 79, 72, 107, 140, 126, 150, 60, 174, 184, 111,
155, 22, 32, 185, 149, 95, 60, 146, 165, 103, 34, 131,
91, 92, 85, 6, 102, 172, 131, 178, 141, 76, 84, 121,
49, 19, 66, 127, 45, 23, 159, 33, 138, 47, 36, 106, 39,
83, 164, 83, 16, 126, 126, 118, 84, 171,
]),
143,
),
Scan(Key(vec![165]), -26),
Get(Key(vec![])),
Del(Key(vec![])),
Set(
Key(vec![
197, 224, 20, 219, 111, 246, 70, 138, 190, 237, 9, 202,
187, 160, 47, 10, 231, 14, 2, 131, 30, 202, 95, 48, 44,
21, 192, 155, 172, 51, 101, 155, 73, 5, 22, 140, 137,
11, 37, 79, 79, 92, 25, 107, 82, 145, 39, 45, 155, 136,
242, 8, 43, 71, 28, 70, 94, 79, 151, 20, 144, 53, 100,
196, 74, 140, 27, 224, 59, 1, 143, 136, 132, 85, 114,
166, 103, 242, 156, 183, 168, 148, 2, 33, 29, 201, 7,
96, 13, 33, 102, 172, 21, 96, 27, 1, 86, 149, 150, 119,
208, 118, 148, 51, 143, 54, 245, 89, 216, 145, 145, 72,
105, 51, 19, 14, 15, 18, 34, 16, 101, 172, 133, 32,
173, 106, 157, 15, 48, 194, 27, 55, 204, 110, 145, 99,
9, 37, 195, 206, 13, 246, 161, 100, 222, 235, 184, 12,
64, 103, 50, 158, 242, 163, 198, 61, 224, 130, 226,
187, 158, 175, 135, 54, 110, 33, 9, 59, 127, 135, 47,
204, 109, 105, 0, 161, 48, 247, 140, 101, 141, 81, 157,
80, 135, 228, 102, 44, 74, 53, 121, 116, 17, 56, 26,
112,
]),
22,
),
Set(Key(vec![110]), 222),
Set(Key(vec![94]), 5),
GetGt(Key(vec![
181, 161, 96, 186, 128, 24, 232, 74, 149, 3, 129, 98, 220,
25, 111, 111, 163, 244, 229, 137, 159, 137, 13, 12, 97,
150, 6, 88, 76, 77, 31, 36, 57, 54, 82, 85, 119, 250, 187,
163, 132, 73, 194, 129, 149, 176, 62, 118, 166, 50, 200,
28, 158, 184, 28, 139, 74, 87, 144, 87, 1, 73, 37, 46, 226,
91, 102, 13, 67, 195, 64, 189, 90, 190, 163, 216, 171, 22,
69, 234, 57, 134, 96, 198, 179, 115, 43, 160, 104, 252,
105, 192, 91, 211, 176, 171, 252, 236, 202, 158, 250, 186,
134, 154, 82, 17, 113, 175, 13, 125, 185, 101, 38, 236,
155, 30, 110, 11, 33, 198, 114, 184, 84, 91, 67, 125, 55,
188, 124, 242, 89, 124, 69, 18, 26, 137, 34, 33, 201, 58,
252, 134, 33, 131, 126, 136, 168, 20, 32, 237, 10, 57, 158,
149, 102, 62, 10, 98, 106, 10, 93, 78, 240, 205, 38, 186,
97, 104, 204, 14, 34, 100, 179, 161, 135, 136, 194, 99,
])),
Merge(Key(vec![95]), 253),
GetLt(Key(vec![99])),
Merge(Key(vec![]), 124),
Get(Key(vec![61])),
Restart,
],
false,
0,
256,
);
}
}
*/
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_40() {
// postmortem: deletions of non-existant keys were
// being persisted despite being unneccessary.
prop_tree_matches_btreemap(
vec![Del(Key(vec![99; 111222333]))],
false,
0,
256,
);
}
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_41() {
// postmortem: indexing of values during
// iteration was incorrect.
prop_tree_matches_btreemap(
vec![
Set(Key(vec![]), 131),
Set(Key(vec![17; 1]), 214),
Set(Key(vec![4; 1]), 202),
Set(Key(vec![24; 1]), 79),
Set(Key(vec![26; 1]), 235),
Scan(Key(vec![]), 19),
],
false,
0,
256,
);
}
/*
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_42() {
// postmortem: during refactoring, accidentally
// messed up the index selection for merge destinations.
for _ in 0..100 {
prop_tree_matches_btreemap(
vec![
Merge(Key(vec![]), 112),
Set(Key(vec![110; 1]), 153),
Set(Key(vec![15; 1]), 100),
Del(Key(vec![110; 1])),
GetLt(Key(vec![148; 1])),
],
false,
0,
256,
);
}
}
*/
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_43() {
// postmortem: when changing the PageState to always
// include a base node, we did not account for this
// in the tag + size compressed value. This was not
// caught by the quickcheck tests because PageState's
// Arbitrary implementation would ensure that at least
// one frag was present, which was the invariant before
// the base was extracted away from the vec of frags.
prop_tree_matches_btreemap(
vec![
Set(Key(vec![241; 1]), 199),
Set(Key(vec![]), 198),
Set(Key(vec![72; 108]), 175),
GetLt(Key(vec![])),
Restart,
Restart,
],
false,
0,
288,
);
}
/*
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_44() {
// postmortem: off-by-one bug related to LSN recovery
// where 1 was added to the index when the recovered
// LSN was actually divisible by the segment size
assert!(prop_tree_matches_btreemap(
vec![
Merge(Key(vec![]), 97),
Merge(Key(vec![]), 41),
Merge(Key(vec![]), 241),
Set(Key(vec![21; 1]), 24),
Del(Key(vec![])),
Set(Key(vec![]), 145),
Set(Key(vec![151; 1]), 187),
Get(Key(vec![])),
Restart,
Set(Key(vec![]), 151),
Restart,
],
false,
0,
256
))
}
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_45() {
// postmortem: recovery was not properly accounting for
// the possibility of a segment to be maxed out, similar
// to bug 44.
for _ in 0..10 {
assert!(prop_tree_matches_btreemap(
vec![
Merge(Key(vec![206; 77]), 225),
Set(Key(vec![88; 190]), 40),
Set(Key(vec![162; 1]), 213),
Merge(Key(vec![186; 1]), 175),
Set(Key(vec![105; 16]), 111),
Cas(Key(vec![]), 75, 252),
Restart
],
false,
true,
0,
210
))
}
}
*/
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_46() {
// postmortem: while implementing the heap slab, decompression
// was failing to account for the fact that the slab allocator
// will always write to the end of the slab to be compatible
// with O_DIRECT.
for _ in 0..1 {
assert!(prop_tree_matches_btreemap(vec![Restart], false, 0, 256))
}
}
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_47() {
// postmortem:
assert!(prop_tree_matches_btreemap(
vec![Set(Key(vec![88; 1]), 40), Restart, Get(Key(vec![88; 1]))],
false,
0,
256
))
}
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_48() {
// postmortem: node value buffer calculations were failing to
// account for potential padding added to avoid buffer overreads
// while looking up offsets.
assert!(prop_tree_matches_btreemap(
vec![
Set(Key(vec![23; 1]), 78),
Set(Key(vec![120; 1]), 223),
Set(Key(vec![123; 1]), 235),
Set(Key(vec![60; 1]), 234),
Set(Key(vec![]), 71),
Del(Key(vec![120; 1])),
Scan(Key(vec![]), -9)
],
false,
0,
256
))
}
/*
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_49() {
// postmortem: was incorrectly calculating the child offset while searching
// for a node with omitted keys, where the distance == the stride, and
// as a result we went into an infinite loop trying to apply a parent
// split that was already present
assert!(prop_tree_matches_btreemap(
vec![
Set(Key(vec![39; 1]), 245),
Set(Key(vec![108; 1]), 96),
Set(Key(vec![147; 1]), 44),
Set(Key(vec![102; 1]), 2),
Merge(Key(vec![22; 1]), 160),
Set(Key(vec![36; 1]), 1),
Set(Key(vec![65; 1]), 213),
Set(Key(vec![]), 221),
Set(Key(vec![84; 1]), 20),
Merge(Key(vec![229; 1]), 61),
Set(Key(vec![156; 1]), 69),
Merge(Key(vec![252; 1]), 85),
Set(Key(vec![36; 2]), 57),
Set(Key(vec![245; 1]), 143),
Set(Key(vec![59; 1]), 209),
GetGt(Key(vec![136; 1])),
Set(Key(vec![40; 1]), 96),
GetGt(Key(vec![59; 2]))
],
false,
false,
0,
0
))
}
*/
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_50() {
// postmortem: node value buffer calculations were failing to
// account for potential padding added to avoid buffer overreads
// while looking up offsets.
assert!(prop_tree_matches_btreemap(
vec![
Set(Key(vec![1; 1]), 44),
Set(Key(vec![52; 1]), 108),
Set(Key(vec![80; 1]), 177),
Set(Key(vec![225; 1]), 59),
Set(Key(vec![246; 1]), 34),
Set(Key(vec![51; 1]), 233),
Set(Key(vec![]), 88),
GetLt(Key(vec![1; 1]))
],
false,
0,
0
))
}
#[test]
#[cfg_attr(miri, ignore)]
fn tree_bug_51() {
// postmortem:
prop_tree_matches_btreemap(
vec![Set(Key(vec![]), 135), Restart, Scan(Key(vec![]), -38)],
false,
0,
0,
);
}
Reference in New Issue View Git Blame Copy Permalink