regolith 0.1.0

ACID, performance oriented, embedded key-value database engine for edge systems
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

//! Model of invariant A5: an arena outlives every [`crate::DbSlice`]
//! taken from it.
//!
//! The memtable hands out values by reference-counting the arena rather
//! than by copying, so the question "may this chunk go back to the pool"
//! is answered by an `Arc<Arena>` refcount and nothing else. The model
//! makes the last memtable handle die on one thread while another still
//! holds a slice, which is the ordering the refcount exists for.

use loom::sync::Arc;

use super::{explore, memtable, memtable_with_budget, probe};

/// Arena budget for the chunk-growth model. One 256-byte chunk holds the
/// seeded entry, and a whole-budget value cannot fit beside it, so the
/// writer's single insert is guaranteed to reserve a second chunk.
const SMALL_BUDGET: usize = 256;

/// A slice keeps reading correctly after every memtable handle is gone,
/// including when a concurrent writer grows the arena underneath it.
///
/// Loom decides which thread runs the last `Arc<MemTable>` drop and
/// where the writer's insert lands relative to it, and checks at the end
/// of every execution that no reference count was leaked. The witness is
/// the schedule that matters: the reader itself holding the last
/// memtable handle, so its own `drop` is what would retire the arena if
/// the slice were not counted.
pub fn a_slice_outlives_every_memtable_handle() {
    explore(
        "a_slice_outlives_every_memtable_handle",
        256,
        8,
        |witness| {
            let mt = Arc::new(memtable());
            mt.put(probe(b"k").prefixed_user_key(), b"pinned", 1);

            let reader = {
                let mt = Arc::clone(&mt);
                let witness = witness.clone();
                loom::thread::spawn(move || {
                    let (_, value) = mt.get(&probe(b"k")).expect("`k` was seeded");
                    let value = value.expect("`k` is a live value");
                    // A5: dropping the last handle this thread owns must not
                    // be able to retire the chunk the slice points into.
                    let last = Arc::strong_count(&mt) == 1;
                    drop(mt);
                    assert_eq!(value.as_slice(), b"pinned");
                    if last {
                        witness.record();
                    }
                })
            };
            let writer = {
                let mt = Arc::clone(&mt);
                loom::thread::spawn(move || {
                    mt.put(probe(b"z").prefixed_user_key(), b"later", 2);
                    drop(mt);
                })
            };

            drop(mt);
            reader.join().expect("reader");
            writer.join().expect("writer");
        },
    );
}

/// Invariants A2, A3 and A5 across a chunk boundary: a slice taken from
/// the arena's first chunk keeps reading while a writer forces a second
/// one.
///
/// This is the case the single-chunk model above cannot reach. Growing
/// the arena pushes onto `ArenaState::chunks`, which reallocates the
/// handle vector and moves every `ChunkHandle`; the bytes a published
/// node occupies do not move with them, and the reader's raw pointer is
/// into those bytes rather than into the vector. The writer's entry is a
/// whole budget wide, so it cannot fit beside the seeded one and the
/// second chunk is forced rather than hoped for - the witness is the
/// schedule where the reader observes the growth before it reads.
pub fn a_slice_survives_the_arena_growing_a_new_chunk() {
    explore(
        "a_slice_survives_the_arena_growing_a_new_chunk",
        64,
        8,
        |witness| {
            let mt = Arc::new(memtable_with_budget(SMALL_BUDGET));
            mt.put(probe(b"k").prefixed_user_key(), b"pinned", 1);
            let reserved_before = mt.reserved_size();
            assert!(reserved_before > 0, "the seed took the arena's first chunk");

            let reader = {
                let mt = Arc::clone(&mt);
                let witness = witness.clone();
                loom::thread::spawn(move || {
                    let (_, value) = mt.get(&probe(b"k")).expect("`k` was seeded");
                    let value = value.expect("`k` is a live value");
                    let grew = mt.reserved_size() > reserved_before;
                    drop(mt);
                    assert_eq!(
                        value.as_slice(),
                        b"pinned",
                        "A2, A3, A5: a pinned slice reads its own chunk's bytes"
                    );
                    if grew {
                        witness.record();
                    }
                })
            };
            let writer = {
                let mt = Arc::clone(&mt);
                loom::thread::spawn(move || {
                    mt.put(probe(b"big").prefixed_user_key(), &[0xab; SMALL_BUDGET], 2);
                    drop(mt);
                })
            };

            drop(mt);
            reader.join().expect("reader");
            writer.join().expect("writer");
        },
    );
}