dualcache_ff/componant/
cache_tier.rs

1use super::slot::Slot;
2use super::qsbr;
3use super::arena::{self, Arena};
4use super::policy::{EvictionPolicy, DefaultEvictionPolicy};
5
6/// Represents a single cache tier (e.g., T0, T1, T2) using Set-Associative Lock-Free arrays.
7#[repr(C, align(64))]
8pub struct CacheTier<K, V, P: EvictionPolicy = DefaultEvictionPolicy, const CAPACITY: usize = 0, const WAYS: usize = 8> {
9    slots: [Slot<K, V>; CAPACITY],
10    policy: P,
11}
12
13impl<K, V, P: EvictionPolicy, const CAPACITY: usize, const WAYS: usize> CacheTier<K, V, P, CAPACITY, WAYS> {
14    /// Create a new `CacheTier`.
15    #[must_use]
16    pub const fn new(policy: P) -> Self {
17        assert!(CAPACITY > 0, "CAPACITY must be greater than 0");
18        assert!(CAPACITY.is_multiple_of(WAYS), "CAPACITY must be a multiple of WAYS");
19
20        Self { 
21            slots: [const { Slot::new() }; CAPACITY],
22            policy,
23        }
24    }
25
26    /// Retrieve the set of slots for a given hash.
27    #[inline(always)]
28    pub fn get_set(&self, hash: usize) -> &[Slot<K, V>] {
29        let num_sets = CAPACITY / WAYS;
30        let index = hash % num_sets;
31        let start = index * WAYS;
32        unsafe {
33            self.slots.get_unchecked(start..start + WAYS)
34        }
35    }
36
37    /// Touch a slot by hash to prevent it from being evicted (Prefetch hint)
38    #[inline(always)]
39    pub fn fetch_hint<const N: usize>(&self, hash: usize, arena: &super::arena::Arena<K, V, N>, guard: &super::qsbr::Guard) -> Option<(K, V)>
40    where
41        K: Clone,
42        V: Clone,
43    {
44        let set = self.get_set(hash);
45        for slot in set {
46            let (slot_hash, idx) = slot.read(guard);
47            if slot_hash == hash && idx != super::arena::NULL_INDEX {
48                let node = unsafe { arena.get(idx as usize) };
49                return Some((node.key.clone(), node.value.clone()));
50            }
51        }
52        None
53    }
54
55    /// Retrieve a slot if the key exists in this tier.
56    #[inline(always)]
57    pub fn get_slot<const N: usize>(&self, arena: &Arena<K, V, N>, hash: usize, key: &K, guard: &qsbr::Guard) -> Option<&Slot<K, V>>
58    where
59        K: PartialEq,
60    {
61        let set = self.get_set(hash);
62        for slot in set {
63            let (slot_hash, idx) = slot.read(guard);
64            if slot_hash == hash && idx != arena::NULL_INDEX {
65                let node = unsafe { arena.get(idx as usize) };
66                if node.key == *key {
67                    return Some(slot);
68                }
69            }
70        }
71        None
72    }
73
74    /// Insert a key and value into the tier using the provided eviction policy.
75    pub fn insert<const N: usize>(&self, arena: &Arena<K, V, N>, hash: usize, key: K, value: V, node: *mut super::qsbr::ThreadStateNode)
76    where
77        K: PartialEq,
78    {
79        let set = self.get_set(hash);
80        let guard = qsbr::pin(node);
81        
82        // 1. Try to find an empty slot or overwrite the exact matching key
83        for slot in set {
84            let (slot_hash, idx) = slot.read(&guard);
85            if idx == arena::NULL_INDEX {
86                slot.insert(arena, hash, key, value, node);
87                return;
88            }
89            if slot_hash == hash {
90                let node_data = unsafe { arena.get(idx as usize) };
91                if node_data.key == key {
92                    slot.insert(arena, hash, key, value, node);
93                    return;
94                }
95            }
96        }
97        
98        // 2. Use EvictionPolicy to find victim and perform decay
99        let victim_slot = self.policy.find_victim(set, hash);
100
101        // 3. Evict the victim
102        victim_slot.insert(arena, hash, key, value, node);
103    }
104}
105
106impl<K, V, const CAPACITY: usize, const WAYS: usize> Default for CacheTier<K, V, DefaultEvictionPolicy, CAPACITY, WAYS> {
107    fn default() -> Self {
108        Self::new(DefaultEvictionPolicy::new())
109    }
110}
111
112
113
114
115/// A direct-mapped (1-way) fast tier optimized for T0 zero-cost lookups.
116/// It uses exactly 1 atomic load for maximum throughput.
117#[repr(C, align(64))]
118pub struct FastTier<const CAPACITY: usize> {
119    slots: [::core::sync::atomic::AtomicU32; CAPACITY],
120}
121
122impl<const CAPACITY: usize> Default for FastTier<CAPACITY> {
123    fn default() -> Self {
124        Self::new()
125    }
126}
127
128impl<const CAPACITY: usize> FastTier<CAPACITY> {
129    pub const fn new() -> Self {
130        assert!(CAPACITY > 0 && CAPACITY.is_power_of_two(), "CAPACITY must be a power of two");
131        let slots = [const { ::core::sync::atomic::AtomicU32::new(super::arena::NULL_INDEX) }; CAPACITY];
132        Self { slots }
133    }
134
135    #[inline(always)]
136    pub fn get_slot_idx(&self, hash: usize) -> u32 {
137        let mask = CAPACITY - 1;
138        let idx = hash & mask;
139        self.slots[idx].load(::core::sync::atomic::Ordering::Acquire)
140    }
141
142    #[inline(always)]
143    pub fn insert_idx(&self, hash: usize, node_idx: u32) -> u32 {
144        let mask = CAPACITY - 1;
145        let idx = hash & mask;
146        self.slots[idx].swap(node_idx, ::core::sync::atomic::Ordering::Release)
147    }
148
149    /// # Safety
150    /// The caller must ensure that `node` is a valid pointer to a ThreadStateNode
151    /// and that the thread state is active.
152    pub unsafe fn insert_promote<K, V, const N: usize>(&self, arena: &super::arena::Arena<K, V, N>, hash: usize, key: K, value: V, node: *mut super::qsbr::ThreadStateNode) {
153        if let Some(new_idx) = arena.alloc(key, value, node) {
154            let old_idx = self.insert_idx(hash, new_idx as u32);
155            if old_idx != super::arena::NULL_INDEX {
156                unsafe {
157                    let local_free = &mut *(*node).local_free.get();
158                    if !local_free.push(old_idx) {
159                        arena.free(old_idx as usize);
160                    }
161                }
162            }
163        }
164    }
165    
166    pub fn clear(&self) {
167        for slot in self.slots.iter() {
168            slot.store(super::arena::NULL_INDEX, ::core::sync::atomic::Ordering::Relaxed);
169        }
170    }
171}
172
173#[cfg(test)]
174mod tests {
175    use super::*;
176    use crate::componant::arena::Arena;
177    use crate::componant::qsbr;
178
179    #[test]
180    fn test_cache_tier_eviction() {
181        // CAPACITY=8, WAYS=8 means 1 set, 8 slots.
182        let tier = CacheTier::<u64, u64, crate::componant::policy::DefaultEvictionPolicy, 8, 8>::new(crate::componant::policy::DefaultEvictionPolicy::new());
183        let arena = Arena::<u64, u64, 16>::new();
184        let node = {
185            let node = std::boxed::Box::into_raw(std::boxed::Box::new(crate::componant::qsbr::ThreadStateNode::new()));
186            crate::componant::qsbr::register_node(node, 0, ::core::ptr::null(), None);
187            node
188        };
189        let guard = qsbr::pin(node);
190
191        // Fill all 8 slots
192        for i in 0..8 {
193            tier.insert(&arena, i as usize, i, i * 10, node);
194        }
195
196        // Insert 9th item to trigger eviction
197        tier.insert(&arena, 8, 8, 80, node);
198
199        // One of the first 8 should be evicted. Let's check how many remain.
200        let mut count = 0;
201        for i in 0..9 {
202            if tier.get_slot(&arena, i as usize, &i, &guard).is_some() {
203                count += 1;
204            }
205        }
206        assert_eq!(count, 8); // One was evicted, leaving 8.
207    }
208    #[test]
209    fn test_cache_tier_default() {
210        let tier: CacheTier<u64, u64, crate::componant::policy::DefaultEvictionPolicy, 8, 8> = CacheTier::default();
211        let set = tier.get_set(0);
212        assert_eq!(set.len(), 8);
213    }
214}
dualcache_ff/componant/cache_tier.rs

dualcache_ff/componant/
cache_tier.rs
