dualcache-ff 1.0.0

A wait-free, high-performance concurrent cache optimized for extreme read-to-write ratios.
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

use ::core::sync::atomic::Ordering;
use super::qsbr;
use super::arena::{self, Arena};

/// A Slot in the CacheTier.
#[repr(align(64))]
pub struct Slot<K, V> {
    pub hash: ::core::sync::atomic::AtomicUsize,
    pub hits: ::core::sync::atomic::AtomicU16,
    pub node_idx: ::core::sync::atomic::AtomicU32,
    pub prefetch_hint: ::core::sync::atomic::AtomicUsize,
    _marker: core::marker::PhantomData<(K, V)>,
}

impl<K, V> Slot<K, V> {
    #[inline(always)]
    pub const fn new() -> Self {
        Self {
            hash: ::core::sync::atomic::AtomicUsize::new(0),
            hits: ::core::sync::atomic::AtomicU16::new(0),
            node_idx: ::core::sync::atomic::AtomicU32::new(arena::NULL_INDEX),
            prefetch_hint: ::core::sync::atomic::AtomicUsize::new(0),
            _marker: core::marker::PhantomData,
        }
    }

    /// Read the slot. The caller MUST be holding a QSBR Guard.
    /// Returns the hash and the node index.
    #[inline(always)]
    pub fn read(&self, _guard: &qsbr::Guard) -> (usize, u32) {
        let hash = self.hash.load(Ordering::Relaxed);
        let idx = self.node_idx.load(Ordering::Acquire);
        (hash, idx)
    }

    /// Record a cache hit atomically and return (old_hits, new_hits).
    #[inline(always)]
    pub fn record_hit(&self, op_count: u32) -> (u16, u16) {
        let old_hits = self.hits.load(Ordering::Relaxed);
        const PROB_N: u32 = 100;
        if !op_count.is_multiple_of(PROB_N) {
            return (old_hits, old_hits);
        }
        let new_hits = old_hits.saturating_add(PROB_N as u16);
        self.hits.store(new_hits, Ordering::Relaxed);
        (old_hits, new_hits)
    }

    /// Insert a new node into the slot, retiring the old one safely using QSBR.
    pub fn insert<const N: usize>(&self, arena: &Arena<K, V, N>, hash: usize, key: K, value: V, node: *mut crate::componant::qsbr::ThreadStateNode) {
        let new_idx = arena.alloc(key, value, node).expect("Arena OOM!");
        self.hash.store(hash, Ordering::Relaxed);
        self.hits.store(8, Ordering::Relaxed);
        let old_idx = self.node_idx.swap(new_idx as u32, Ordering::Release);
        if old_idx != arena::NULL_INDEX {
            crate::componant::qsbr::retire(old_idx as usize, node, |idx| unsafe { arena.free(idx as usize) });
        }
    }
}

impl<K, V> Default for Slot<K, V> {
    fn default() -> Self {
        Self::new()
    }
}


#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_slot_default() {
        let slot: Slot<u64, u64> = Slot::default();
        let node = {
            static mut TEST_NODE: crate::componant::qsbr::ThreadStateNode = crate::componant::qsbr::ThreadStateNode::new();
            let n = &raw mut TEST_NODE as *mut _;
            crate::componant::qsbr::register_node(n);
            n
        };
        let guard = crate::componant::qsbr::pin(node);
        assert_eq!(slot.read(&guard), (0, super::super::arena::NULL_INDEX));
    }
    #[test]
    fn test_slot_insert_replace() {
        let arena = crate::componant::arena::Arena::<u64, u64, 4>::new();
        let slot = Slot::<u64, u64>::default();
        let node = {
            static mut TEST_NODE: crate::componant::qsbr::ThreadStateNode = crate::componant::qsbr::ThreadStateNode::new();
            let n = &raw mut TEST_NODE as *mut _;
            crate::componant::qsbr::register_node(n);
            n
        };
        let guard = crate::componant::qsbr::pin(node);
        
        slot.insert(&arena, 100, 10, 20, node);
        assert_eq!(slot.read(&guard).0, 100);
        
        let (old_hits, new_hits) = slot.record_hit(100);
        assert_eq!(old_hits, 8);
        assert_eq!(new_hits, 108);
        
        // Re-insert to trigger retirement of old_idx
        slot.insert(&arena, 200, 30, 40, node);
        assert_eq!(slot.read(&guard).0, 200);
    }
}