dualcache_ff/core/
engine.rs

1use crate::componant::arena::Arena;
2use crate::componant::cache_tier::{CacheTier, FastTier};
3use crate::componant::config::{CachePolicy, DefaultExponentialPolicy};
4use crate::componant::qsbr::Guard;
5use ahash::RandomState;
6use core::hash::Hash;
7
8/// The independent orchestrator that glues T0, T1, and T2 together.
9/// Designed for `no_std` environments.
10#[repr(align(64))]
11pub struct DualCacheCore<
12    K,
13    V,
14    P: CachePolicy = DefaultExponentialPolicy,
15    const T0_CAP: usize = 64,
16    const T1_CAP: usize = 4096,
17    const T2_CAP: usize = 262144,
18    const TOTAL_CAP: usize = { 64 + 4096 + 262144 },
19> {
20    pub arena: Arena<K, V, TOTAL_CAP>,
21    pub t0: FastTier<T0_CAP>,
22    pub t1: FastTier<T1_CAP>,
23    pub t2: CacheTier<K, V, P::Evict, T2_CAP, 8>,
24    pub blackjack: crate::core::blackjack::PackedBlackjack,
25    hash_builder: RandomState,
26    _marker: core::marker::PhantomData<P>,
27}
28
29/// A default configured Bottom-Up Anchoring DualCacheCore
30pub type BottomUpCache<K, V> =
31    DualCacheCore<K, V, DefaultExponentialPolicy, 64, 4096, 262144, { 64 + 4096 + 262144 }>;
32
33impl<
34    K,
35    V,
36    P: CachePolicy,
37    const T0_CAP: usize,
38    const T1_CAP: usize,
39    const T2_CAP: usize,
40    const TOTAL_CAP: usize,
41> DualCacheCore<K, V, P, T0_CAP, T1_CAP, T2_CAP, TOTAL_CAP>
42where
43    K: Clone + Eq + Hash,
44    V: Clone,
45{
46    pub const fn new(eviction: P::Evict) -> Self {
47        Self {
48            arena: Arena::new(),
49            t0: FastTier::new(),
50            t1: FastTier::new(),
51            t2: CacheTier::new(eviction),
52            blackjack: crate::core::blackjack::PackedBlackjack::new(
53                P::T0_THRESHOLD,
54                P::T1_THRESHOLD,
55                P::T2_THRESHOLD,
56                256,
57            ),
58            hash_builder: ahash::RandomState::with_seeds(
59                0x1234567890ABCDEF,
60                0xFEDCBA0987654321,
61                0x13579BDF02468ACE,
62                0xECA86420FDB97531,
63            ),
64            _marker: core::marker::PhantomData,
65        }
66    }
67
68    #[inline(always)]
69    pub fn hash_key(&self, key: &K) -> usize {
70        self.hash_builder.hash_one(key) as usize
71    }
72
73    #[inline(always)]
74    pub fn get_t0<'g>(&self, hash: usize, key: &K, _guard: &'g Guard, _op_count: u32) -> Option<&'g V> {
75        let node_idx = self.t0.get_slot_idx(hash);
76        if node_idx != crate::componant::arena::NULL_INDEX {
77            let node = unsafe { self.arena.get(node_idx as usize) };
78            if node.key == *key {
79                return Some(unsafe { &*(&node.value as *const V) });
80            }
81        }
82        None
83    }
84
85    #[inline(always)]
86    pub fn get_t1<'g>(&self, hash: usize, key: &K, _guard: &'g Guard, _op_count: u32) -> Option<&'g V> {
87        let node_idx = self.t1.get_slot_idx(hash);
88        if node_idx != crate::componant::arena::NULL_INDEX {
89            let node = unsafe { self.arena.get(node_idx as usize) };
90            if node.key == *key {
91                return Some(unsafe { &*(&node.value as *const V) });
92            }
93        }
94        None
95    }
96
97    #[inline(always)]
98    #[allow(clippy::type_complexity)]
99    pub fn get_t2<'g>(&'g self, hash: usize, key: &K, guard: &'g crate::componant::qsbr::Guard, op_count: u32) -> Option<(&'g V, u8, Option<(K, V)>)> {
100        let (_t0_thresh, t1_thresh, _, _) = self.blackjack.load_params();
101
102        // T0
103        if let Some(val) = self.get_t0(hash, key, guard, op_count) {
104            return Some((val, 0, None));
105        }
106
107        // T1
108        let t1_idx = self.t1.get_slot_idx(hash);
109        if t1_idx != crate::componant::arena::NULL_INDEX {
110            let node = unsafe { self.arena.get(t1_idx as usize) };
111            if node.key == *key {
112                return Some((unsafe { &*(&node.value as *const V) }, 1, None));
113            }
114        }
115
116        // T2
117        if let Some(slot) = self.t2.get_slot(&self.arena, hash, key, guard) {
118            let (old_hits, new_hits) = slot.record_hit(op_count);
119            let hint = slot.prefetch_hint.load(::core::sync::atomic::Ordering::Relaxed);
120            let hint_kv = if hint != 0 {
121                self.t2.fetch_hint(hint, &self.arena, guard)
122            } else {
123                None
124            };
125            
126            let node = unsafe { self.arena.get(slot.read(guard).1 as usize) };
127            if old_hits < t1_thresh && new_hits >= t1_thresh {
128                // Promote to T1
129                unsafe {
130                    self.t1.insert_promote(&self.arena, hash, key.clone(), node.value.clone(), guard.node());
131                }
132            }
133            return Some((unsafe { &*(&node.value as *const V) }, 2, hint_kv));
134        }
135        None
136    }
137
138    #[inline(never)]
139    #[allow(clippy::type_complexity)]
140    pub fn get<'g>(&'g self, key: &K, guard: &'g Guard, op_count: u32) -> Option<(&'g V, u8, Option<(K, V)>)> {
141        #[repr(align(64))]
142        struct CachePadded;
143        let _pad = CachePadded;
144
145        mod core {
146            pub mod intrinsics {
147                pub use crate::utils::likely;
148                
149            }
150        }
151
152        let hash = self.hash_key(key);
153        let res = self.get_t2(hash, key, guard, op_count);
154        
155        if core::intrinsics::likely(res.is_some()) {
156            return res;
157        }
158        None
159    }
160
161    #[allow(clippy::not_unsafe_ptr_arg_deref)]
162    pub fn put_t0(&self, key: K, value: V, node: *mut crate::componant::qsbr::ThreadStateNode) {
163        if crate::utils::likely(true) {
164            let hash = self.hash_key(&key);
165            unsafe {
166                self.t0.insert_promote(&self.arena, hash, key, value, node);
167            }
168        }
169    }
170
171    #[allow(clippy::not_unsafe_ptr_arg_deref)]
172    pub fn put_t1(&self, key: K, value: V, node: *mut crate::componant::qsbr::ThreadStateNode) {
173        if crate::utils::likely(true) {
174            let hash = self.hash_key(&key);
175            unsafe {
176                self.t1.insert_promote(&self.arena, hash, key, value, node);
177            }
178        }
179    }
180
181    pub fn put(&self, key: K, value: V, node: *mut crate::componant::qsbr::ThreadStateNode) {
182        if crate::utils::likely(true) {
183            let hash = self.hash_key(&key);
184            self.t2.insert(&self.arena, hash, key, value, node);
185        }
186    }
187
188    pub fn try_reclaim(&self, _node: *mut crate::componant::qsbr::ThreadStateNode) {
189        // Reclamation is now handled exclusively by the Daemon using daemon_reclaim closure
190    }
191
192    /// Synchronous inline reclamation for Lock-based caches (e.g., StaticDualCache)
193    /// that do not have a background daemon thread. MUST ONLY be called when protected
194    /// by a Mutex to avoid data races on the single-consumer QSBR garbage queues.
195    pub fn sync_reclaim(&self) {
196        crate::componant::qsbr::daemon_reclaim(|batch| {
197            if batch.is_empty() { return; }
198            unsafe {
199                for i in 0..batch.len() {
200                    let idx = batch[i];
201                    self.arena.drop_node(idx as usize);
202                    if i < batch.len() - 1 {
203                        self.arena.set_next_free(idx, batch[i + 1]);
204                    }
205                }
206                self.arena.free_batch(batch[0], batch[batch.len() - 1]);
207            }
208        });
209    }
210
211    /// Record a remote hit for an item based on its hash.
212    /// Used by the Daemon to propagate TLS hits into the global T2 cache.
213    pub fn record_remote_hit(&self, hash: usize, _weight: u8) {
214        let set = self.t2.get_set(hash);
215        for i in 0..8 {
216            let slot = unsafe { set.get_unchecked(i) };
217            if slot.hash.load(::core::sync::atomic::Ordering::Relaxed) == hash {
218                let old_hits = slot.hits.load(::core::sync::atomic::Ordering::Relaxed);
219                let new_hits = old_hits.saturating_add(_weight as u16);
220                slot.hits
221                    .store(new_hits, ::core::sync::atomic::Ordering::Relaxed);
222                break;
223            }
224        }
225    }
226
227    pub fn set_prefetch_hint(&self, hash: usize, next_hash: usize) {
228        let set = self.t2.get_set(hash);
229        for i in 0..8 {
230            let slot = unsafe { set.get_unchecked(i) };
231            if slot.hash.load(::core::sync::atomic::Ordering::Relaxed) == hash {
232                slot.prefetch_hint.store(next_hash, ::core::sync::atomic::Ordering::Relaxed);
233                break;
234            }
235        }
236    }
237}
238
239impl<
240    K,
241    V,
242    P: CachePolicy,
243    const T0_CAP: usize,
244    const T1_CAP: usize,
245    const T2_CAP: usize,
246    const TOTAL_CAP: usize,
247> Default for DualCacheCore<K, V, P, T0_CAP, T1_CAP, T2_CAP, TOTAL_CAP>
248where
249    K: Clone + Eq + Hash,
250    V: Clone,
251{
252    fn default() -> Self {
253        Self::new(P::Evict::default())
254    }
255}
256
257#[cfg(test)]
258mod tests {
259    use super::*;
260    use crate::componant::config::CachePolicy;
261    use crate::componant::qsbr;
262
263    // A test policy that forces 2^n thresholds but smaller values for quick testing
264    struct TestPolicy;
265    impl CachePolicy for TestPolicy {
266        type Evict = crate::componant::policy::DefaultEvictionPolicy;
267        const T2_THRESHOLD: u16 = 2;
268        const T1_THRESHOLD: u16 = 4;
269        const T0_THRESHOLD: u16 = 8;
270    }
271
272    #[test]
273    fn test_comprehensive_cache_flow() {
274        let core = DualCacheCore::<u64, u64, TestPolicy, 8, 8, 8, 24>::default();
275        static mut TEST_NODE: qsbr::ThreadStateNode = qsbr::ThreadStateNode::new();
276        let thread_node = {
277            let node = &raw mut TEST_NODE as *mut _;
278            qsbr::register_node(node, 0, ::core::ptr::null(), None);
279            node
280        };
281        let guard = qsbr::pin(thread_node);
282
283        assert_eq!(core.get(&100, &guard, 0), None);
284
285        core.put(100, 200, thread_node);
286        assert_eq!(core.get(&100, &guard, 0), Some((&200, 2, None)));
287
288        core.put_t1(300, 400, thread_node);
289        assert_eq!(core.get(&300, &guard, 0), Some((&400, 1, None)));
290
291        core.put_t0(500, 600, thread_node);
292        assert_eq!(core.get(&500, &guard, 0), Some((&600, 0, None)));
293    }
294
295    #[test]
296    fn test_t0_promotion_flow() {
297        let core = DualCacheCore::<u64, u64, TestPolicy, 8, 8, 8, 24>::default();
298        static mut TEST_NODE: qsbr::ThreadStateNode = qsbr::ThreadStateNode::new();
299        let thread_node = {
300            let node = &raw mut TEST_NODE as *mut _;
301            qsbr::register_node(node, 0, ::core::ptr::null(), None);
302            node
303        };
304        let guard = qsbr::pin(thread_node);
305
306        assert_eq!(core.get(&99, &guard, 0), None);
307
308        core.put(300, 400, thread_node);
309        core.record_remote_hit(core.hash_key(&300), 10);
310        assert_eq!(core.get(&300, &guard, 0), Some((&400, 2, None)));
311
312        core.put_t0(500, 600, thread_node);
313        assert_eq!(core.get(&500, &guard, 0), Some((&600, 0, None)));
314    }
315
316    #[test]
317    fn test_tier_fallbacks() {
318        let core = DualCacheCore::<u64, u64, TestPolicy, 8, 8, 8, 24>::default();
319        static mut TEST_NODE: qsbr::ThreadStateNode = qsbr::ThreadStateNode::new();
320        let thread_node = {
321            let node = &raw mut TEST_NODE as *mut _;
322            qsbr::register_node(node, 0, ::core::ptr::null(), None);
323            node
324        };
325        let guard = qsbr::pin(thread_node);
326
327        let hash1 = core.hash_key(&1000);
328        unsafe {
329            core.t1.insert_promote(&core.arena, hash1, 1000, 2000, thread_node);
330        }
331        assert_eq!(core.get(&1000, &guard, 0), Some((&2000, 1, None)));
332
333        let hash0 = core.hash_key(&3000);
334        unsafe {
335            core.t0.insert_promote(&core.arena, hash0, 3000, 4000, thread_node);
336        }
337        assert_eq!(core.get(&3000, &guard, 0), Some((&4000, 0, None)));
338
339        let idx = core.t1.get_slot_idx(hash1);
340        assert_ne!(idx, crate::componant::arena::NULL_INDEX);
341    }
342}
dualcache_ff/core/engine.rs

dualcache_ff/core/
engine.rs
