dualcache_ff/componant/
storage.rs

1use std::{boxed::Box, vec::Vec};
2
3use ::core::sync::atomic::{AtomicU64, AtomicPtr, Ordering};
4use core::ptr;
5
6/// A single cached entry. Stored in the Arena node pool.
7pub struct Node<K, V> {
8    pub key: K,
9    pub value: V,
10    /// Epoch at which this node expires (0 = no expiry).
11    pub expire_at: u32,
12    /// Index into the Arena / Cache node arrays.
13    pub g_idx: u32,
14}
15
16/// L3 lock-free hash index + node pointer array.
17///
18/// `index` is a flat open-addressed array of packed `u64` entries:
19///   bits[63:48] = 16-bit tag (hash >> 48)
20///   bits[47:0]  = Arena slot index
21/// Sentinel values: 0 = empty, u64::MAX = tombstone.
22pub struct Cache<K, V> {
23    pub(crate) index_mask: usize,
24    pub(crate) index: Box<[AtomicU64]>,
25    pub(crate) nodes: Box<[AtomicPtr<Node<K, V>>]>,
26}
27
28unsafe impl<K: Send, V: Send> Send for Cache<K, V> {}
29unsafe impl<K: Send + Sync, V: Send + Sync> Sync for Cache<K, V> {}
30
31impl<K, V> Cache<K, V> {
32    pub fn new(capacity: usize) -> Self {
33        let index_size = (capacity * 2).next_power_of_two();
34        let mut index = Vec::with_capacity(index_size);
35        for _ in 0..index_size {
36            index.push(AtomicU64::new(0));
37        }
38
39        let mut nodes = Vec::with_capacity(capacity);
40        for _ in 0..capacity {
41            nodes.push(AtomicPtr::new(ptr::null_mut()));
42        }
43
44        Self {
45            index_mask: index_size - 1,
46            index: index.into_boxed_slice(),
47            nodes: nodes.into_boxed_slice(),
48        }
49    }
50
51    #[inline(always)]
52    pub fn index_probe(&self, hash: u64, tag: u16) -> Option<usize> {
53        let mut idx = hash as usize & self.index_mask;
54        for _ in 0..16 {
55            let entry = self.index[idx].load(Ordering::Acquire);
56            if entry == 0 {
57                return None;
58            }
59            if entry != u64::MAX && (entry >> 48) as u16 == tag {
60                return Some((entry & 0x0000_FFFF_FFFF_FFFF) as usize);
61            }
62            idx = (idx + 1) & self.index_mask;
63        }
64        None
65    }
66
67    #[inline(always)]
68    pub fn index_store(&self, hash: u64, tag: u16, entry: u64) {
69        let mut idx = hash as usize & self.index_mask;
70        for i in 0..16 {
71            let prev = self.index[idx].load(Ordering::Acquire);
72            if prev == 0 || prev == u64::MAX || (prev >> 48) == (tag as u64) {
73                self.index[idx].store(entry, Ordering::Release);
74                return;
75            }
76            if i == 15 {
77                self.index[hash as usize & self.index_mask].store(entry, Ordering::Release);
78            }
79            idx = (idx + 1) & self.index_mask;
80        }
81    }
82
83    #[inline(always)]
84    pub fn index_remove(&self, hash: u64, tag: u16, g_idx: usize) {
85        let mut idx = hash as usize & self.index_mask;
86        for _ in 0..16 {
87            let entry = self.index[idx].load(Ordering::Acquire);
88            if entry == 0 {
89                return;
90            }
91            if entry != u64::MAX
92                && (entry >> 48) as u16 == tag
93                && (entry & 0x0000_FFFF_FFFF_FFFF) == (g_idx as u64)
94            {
95                self.index[idx].store(u64::MAX, Ordering::Release);
96                return;
97            }
98            idx = (idx + 1) & self.index_mask;
99        }
100    }
101
102    #[inline(always)]
103    pub fn index_clear_at(&self, idx: usize) {
104        self.index[idx].store(0, Ordering::Relaxed);
105    }
106
107    #[inline(always)]
108    pub fn index_len(&self) -> usize {
109        self.index.len()
110    }
111
112    #[inline(always)]
113    pub fn node_get_full(&self, idx: usize, key: &K, current_epoch: u32) -> Option<V>
114    where
115        K: Eq,
116        V: Clone,
117    {
118        let ptr = self.nodes[idx].load(Ordering::Acquire);
119        if ptr.is_null() {
120            return None;
121        }
122        // Safety: QSBR guarantees pointer is valid during check-in.
123        let node = unsafe { &*ptr };
124        if node.key == *key {
125            if node.expire_at > 0 && node.expire_at < current_epoch {
126                return None;
127            }
128            Some(node.value.clone())
129        } else {
130            None
131        }
132    }
133
134    pub fn clear(&self) {
135        for i in 0..self.index.len() {
136            self.index[i].store(0, Ordering::Relaxed);
137        }
138        for i in 0..self.nodes.len() {
139            self.nodes[i].store(ptr::null_mut(), Ordering::Release);
140        }
141    }
142}
143
144impl<K, V> Drop for Cache<K, V> {
145    fn drop(&mut self) {
146        for node_ptr in self.nodes.iter() {
147            let ptr = node_ptr.swap(ptr::null_mut(), Ordering::Relaxed);
148            if !ptr.is_null() {
149                unsafe {
150                    let _ = Box::from_raw(ptr);
151                }
152            }
153        }
154    }
155}
dualcache_ff/componant/storage.rs

dualcache_ff/componant/
storage.rs
