fastskip 0.1.1

Lock-free arena-backed skip list memtable for LSM-tree storage engines
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

//! Loom-based concurrency verification.
//!
//! Tests the atomic invariants of the seal flag and live_count
//! using loom's exhaustive thread-interleaving exploration.
//!
//! Run with: `RUSTFLAGS="--cfg loom" cargo test --test loom`

#![cfg(loom)]

use loom::sync::atomic::{AtomicBool, AtomicUsize, Ordering};
use loom::sync::Arc;
use loom::thread;

/// Verifies the seal flag invariant: once sealed, no operation should
/// appear to succeed (insert returns false, delete returns false).
#[test]
fn loom_seal_flag_prevents_writes() {
    loom::model(|| {
        let sealed = Arc::new(AtomicBool::new(false));

        let s1 = Arc::clone(&sealed);
        let writer = thread::spawn(move || {
            if s1.load(Ordering::Acquire) {
                return false;
            }
            true
        });

        let s2 = Arc::clone(&sealed);
        let sealer = thread::spawn(move || {
            s2.store(true, Ordering::Release);
        });

        let write_ok = writer.join().unwrap();
        sealer.join().unwrap();

        // Both orderings are valid. The invariant is that if
        // sealed=true was observed, insert must reject.
        let _ = write_ok;
    });
}

/// Verifies the live_count invariant: under concurrent inserts, the final
/// count equals the number of successful inserts (no lost updates).
#[test]
fn loom_live_count_no_lost_updates() {
    loom::model(|| {
        let count = Arc::new(AtomicUsize::new(0));

        let c1 = Arc::clone(&count);
        let t1 = thread::spawn(move || {
            c1.fetch_add(1, Ordering::Relaxed);
        });

        let c2 = Arc::clone(&count);
        let t2 = thread::spawn(move || {
            c2.fetch_add(1, Ordering::Relaxed);
        });

        t1.join().unwrap();
        t2.join().unwrap();

        assert_eq!(count.load(Ordering::Relaxed), 2);
    });
}

/// Verifies the sealed + count interaction: sealing doesn't corrupt
/// the live_count that was accumulated before sealing.
#[test]
fn loom_seal_preserves_count() {
    loom::model(|| {
        let count = Arc::new(AtomicUsize::new(0));
        let sealed = Arc::new(AtomicBool::new(false));

        let c1 = Arc::clone(&count);
        let writer = thread::spawn(move || {
            c1.fetch_add(1, Ordering::Relaxed);
        });

        let s1 = Arc::clone(&sealed);
        let sealer = thread::spawn(move || {
            s1.store(true, Ordering::Release);
        });

        let c2 = Arc::clone(&count);
        let s2 = Arc::clone(&sealed);
        let reader = thread::spawn(move || {
            let s = s2.load(Ordering::Acquire);
            let c = c2.load(Ordering::Relaxed);
            (s, c)
        });

        writer.join().unwrap();
        sealer.join().unwrap();
        let (_, c) = reader.join().unwrap();

        assert!(c <= 1, "count corrupted: {}", c);
    });
}

/// Verifies the snapshot sequence invariant: the sequence counter
/// only increases (monotonic), and fetch_add returns unique values.
#[test]
fn loom_seq_monotonic() {
    loom::model(|| {
        let seq = Arc::new(AtomicUsize::new(1));

        let s1 = Arc::clone(&seq);
        let t1 = thread::spawn(move || s1.fetch_add(1, Ordering::Relaxed));

        let s2 = Arc::clone(&seq);
        let t2 = thread::spawn(move || s2.fetch_add(1, Ordering::Relaxed));

        let v1 = t1.join().unwrap();
        let v2 = t2.join().unwrap();

        assert_ne!(v1, v2, "duplicate seq: {} == {}", v1, v2);
        assert_eq!(seq.load(Ordering::Relaxed), 3);
    });
}