metrale_storage/
eviction.rs

1// SPDX-License-Identifier: MIT OR Apache-2.0
2
3//! 2026-09-25: Eviction order for the high-speed-swap scratch slots: which
4//! resident slot a newly needed block overwrites. `rank` orders the unpinned
5//! slots by (recorded predictor score, last access epoch), ascending.
6//!
7//! Owner: metrale-storage high-speed swap.
8//! Invariants: none beyond the types.
9
10use std::collections::HashSet;
11
12#[derive(Debug)]
13pub struct EvictionPolicy {
14    /// 2026-09-25: Per-slot epoch of the last `touch`; 0 when never touched.
15    last_access: Vec<u64>,
16    /// 2026-09-25: Per-slot score from `record_score`; -inf until one is
17    /// recorded.
18    last_score: Vec<f32>,
19    /// 2026-09-25: The epoch the next `touch` records; it starts at 1.
20    epoch: u64,
21}
22
23impl EvictionPolicy {
24    pub fn new(num_slots: u32) -> Self {
25        Self {
26            last_access: vec![0; num_slots as usize],
27            last_score: vec![f32::NEG_INFINITY; num_slots as usize],
28            epoch: 1,
29        }
30    }
31
32    pub fn capacity(&self) -> u32 {
33        self.last_access.len() as u32
34    }
35
36    /// 2026-09-25: Record an access to `slot` at the current epoch.
37    pub fn touch(&mut self, slot: u32) {
38        self.last_access[slot as usize] = self.epoch;
39        self.epoch = self.epoch.wrapping_add(1);
40    }
41
42    pub fn record_score(&mut self, slot: u32, score: f32) {
43        self.last_score[slot as usize] = score;
44    }
45
46    /// 2026-09-25: Return to the state `new` creates.
47    pub fn reset(&mut self) {
48        for v in self.last_access.iter_mut() {
49            *v = 0;
50        }
51        for v in self.last_score.iter_mut() {
52            *v = f32::NEG_INFINITY;
53        }
54        self.epoch = 1;
55    }
56
57    /// 2026-09-25: Slot indices, most evictable first, without `pinned`.
58    /// Scores that do not compare (NaN) count as equal.
59    pub fn rank(&self, pinned: &[u32]) -> Vec<u32> {
60        let pinned_set: HashSet<u32> = pinned.iter().copied().collect();
61        let mut candidates: Vec<u32> = (0..self.capacity())
62            .filter(|s| !pinned_set.contains(s))
63            .collect();
64        candidates.sort_by(|a, b| {
65            let ai = *a as usize;
66            let bi = *b as usize;
67            self.last_score[ai]
68                .partial_cmp(&self.last_score[bi])
69                .unwrap_or(std::cmp::Ordering::Equal)
70                .then(self.last_access[ai].cmp(&self.last_access[bi]))
71        });
72        candidates
73    }
74}
75
76#[cfg(test)]
77mod tests {
78    use super::*;
79
80    #[test]
81    fn lowest_score_evicts_first() {
82        let mut p = EvictionPolicy::new(4);
83        p.record_score(0, 10.0);
84        p.record_score(1, 1.0);
85        p.record_score(2, 5.0);
86        p.record_score(3, 100.0);
87        let order = p.rank(&[]);
88        assert_eq!(order[0], 1, "lowest score should evict first: {order:?}");
89        assert_eq!(order.last(), Some(&3));
90    }
91
92    #[test]
93    fn ties_break_to_oldest_access() {
94        let mut p = EvictionPolicy::new(3);
95        p.record_score(0, 5.0);
96        p.record_score(1, 5.0);
97        p.record_score(2, 5.0);
98        p.touch(2);
99        p.touch(0);
100        let order = p.rank(&[]);
101        assert_eq!(order[0], 1, "oldest should win the tie: {order:?}");
102        assert_eq!(order[1], 2);
103        assert_eq!(order[2], 0);
104    }
105
106    #[test]
107    fn pinned_slots_excluded() {
108        let mut p = EvictionPolicy::new(4);
109        p.record_score(0, 1.0);
110        p.record_score(1, 2.0);
111        p.record_score(2, 3.0);
112        p.record_score(3, 4.0);
113        let order = p.rank(&[0, 1]);
114        assert_eq!(order, vec![2, 3]);
115    }
116
117    #[test]
118    fn reset_clears_state() {
119        let mut p = EvictionPolicy::new(2);
120        p.record_score(0, 1.0);
121        p.record_score(1, 2.0);
122        p.touch(0);
123        p.touch(1);
124        p.reset();
125        assert_eq!(p.last_score, vec![f32::NEG_INFINITY; 2]);
126        assert_eq!(p.last_access, vec![0; 2]);
127        assert_eq!(p.epoch, 1);
128    }
129}
metrale_storage/eviction.rs

metrale_storage/
eviction.rs
