psx_cache/
lib.rs

1// SPDX-License-Identifier: GPL-2.0-or-later
2//! A generic, fixed-capacity slot cache for `no_std`/no-heap targets (PS1).
3//!
4//! This captures the shape shared by every residency pool in the engine (the
5//! room stream scheduler, VRAM texture slots, asset residency): a small set of
6//! slots, a dense key->slot reverse map for O(1) lookup, least-recently-used
7//! eviction, and pinning to protect the in-use working set. It owns the *index*
8//! (which key lives in which slot, and the slot's load state); the caller owns
9//! the *memory* the value points at. Keep variable-size allocation (VRAM
10//! rectangles, CD byte ranges) in a separate allocator layer.
11//!
12//! - `V` is the per-slot payload (`Copy`); typically a small handle/metadata.
13//! - `N` is the slot capacity (how many values can be resident at once).
14//! - `MAX_KEY` is the key space; keys are `u16` in `0..MAX_KEY`, used to index
15//!   the reverse map. Pick the smallest bound that covers your id space.
16//!
17//! Slots move `Empty -> Loading -> Ready`. Synchronous consumers use
18//! [`SlotCache::get_or_insert_with`]; consumers whose creation is asynchronous
19//! (streaming a room off the CD over several frames) use [`SlotCache::begin_load`]
20//! then [`SlotCache::finish_load`] when the load completes.
21
22#![cfg_attr(not(test), no_std)]
23#![forbid(unsafe_code)]
24
25/// Sentinel stored in the reverse map for "no slot".
26const NONE: u16 = u16::MAX;
27
28/// Load state of a slot.
29#[derive(Copy, Clone, PartialEq, Eq, Debug)]
30pub enum SlotState {
31    /// Free; holds no key or value.
32    Empty,
33    /// Reserved for a key; a value is being produced (async load in flight).
34    Loading,
35    /// Holds a usable value for its key.
36    Ready,
37}
38
39/// A slot reserved for a key by [`SlotCache::begin_load`], to be completed by
40/// [`SlotCache::finish_load`]. It remembers the key as well as the slot, so a
41/// load that finishes after its slot was evicted and reused is refused instead
42/// of storing its value under another key.
43#[derive(Copy, Clone, PartialEq, Eq, Debug)]
44pub struct Reservation {
45    slot: u16,
46    key: u16,
47}
48
49impl Reservation {
50    fn new(slot: usize, key: u16) -> Self {
51        // `begin_load` only builds this from a slot index below `N`, which the
52        // cache keeps under `u16::MAX`.
53        Self {
54            slot: slot as u16,
55            key,
56        }
57    }
58
59    /// The reserved slot index.
60    pub const fn slot(&self) -> usize {
61        self.slot as usize
62    }
63
64    /// The key the slot was reserved for.
65    pub const fn key(&self) -> u16 {
66        self.key
67    }
68}
69
70/// [`SlotCache::finish_load`] refused a reservation whose key no longer owns
71/// its slot.
72#[derive(Copy, Clone, PartialEq, Eq, Debug)]
73pub struct Stale;
74
75#[derive(Copy, Clone)]
76struct Slot<V: Copy> {
77    key: u16,
78    value: Option<V>,
79    state: SlotState,
80    /// Epoch of the last `get`/touch; the LRU eviction key.
81    last_used: u32,
82    /// Pinned slots are never chosen for eviction.
83    pinned: bool,
84}
85
86/// Keyed, fixed-capacity cache with LRU eviction and pinning.
87pub struct SlotCache<V: Copy, const N: usize, const MAX_KEY: usize> {
88    slots: [Slot<V>; N],
89    key_to_slot: [u16; MAX_KEY],
90    epoch: u32,
91}
92
93impl<V: Copy, const N: usize, const MAX_KEY: usize> Default for SlotCache<V, N, MAX_KEY> {
94    fn default() -> Self {
95        Self::new()
96    }
97}
98
99impl<V: Copy, const N: usize, const MAX_KEY: usize> SlotCache<V, N, MAX_KEY> {
100    /// An empty cache. `const` so it can back a `static`.
101    pub const fn new() -> Self {
102        Self {
103            slots: [Slot {
104                key: NONE,
105                value: None,
106                state: SlotState::Empty,
107                last_used: 0,
108                pinned: false,
109            }; N],
110            key_to_slot: [NONE; MAX_KEY],
111            epoch: 0,
112        }
113    }
114
115    /// Slot capacity.
116    pub const fn capacity(&self) -> usize {
117        N
118    }
119
120    /// Advance the LRU clock. Call once per cache cycle (e.g. per frame) so
121    /// `get` touches and eviction comparisons share a monotonic timeline.
122    /// Never returns 0, so a freshly touched slot always beats the initial
123    /// `last_used` of an untouched one.
124    pub fn bump_epoch(&mut self) {
125        self.epoch = self.epoch.wrapping_add(1).max(1);
126    }
127
128    /// The current epoch (the value `get` stamps into `last_used`).
129    pub const fn epoch(&self) -> u32 {
130        self.epoch
131    }
132
133    fn key_ok(key: u16) -> bool {
134        (key as usize) < MAX_KEY && key != NONE
135    }
136
137    /// Slot index currently mapped to `key` in any non-empty state, validated
138    /// against the forward store (so a stale reverse entry never lies).
139    pub fn slot_of(&self, key: u16) -> Option<usize> {
140        if !Self::key_ok(key) {
141            return None;
142        }
143        let raw = self.key_to_slot[key as usize];
144        if raw == NONE {
145            return None;
146        }
147        let s = raw as usize;
148        if s < N && self.slots[s].state != SlotState::Empty && self.slots[s].key == key {
149            Some(s)
150        } else {
151            None
152        }
153    }
154
155    /// Is `key` resident and usable (`Ready`)?
156    pub fn contains_ready(&self, key: u16) -> bool {
157        self.slot_of(key)
158            .is_some_and(|s| self.slots[s].state == SlotState::Ready)
159    }
160
161    /// Is `key` reserved with a load in flight (`Loading`)?
162    pub fn is_loading(&self, key: u16) -> bool {
163        self.slot_of(key)
164            .is_some_and(|s| self.slots[s].state == SlotState::Loading)
165    }
166
167    /// Load state of `key`, or `Empty` if absent.
168    pub fn state_of(&self, key: u16) -> SlotState {
169        match self.slot_of(key) {
170            Some(s) => self.slots[s].state,
171            None => SlotState::Empty,
172        }
173    }
174
175    /// Get a `Ready` value, marking it most-recently-used. Returns `None` for an
176    /// absent or still-`Loading` key.
177    pub fn get(&mut self, key: u16) -> Option<&V> {
178        let s = self.slot_of(key)?;
179        if self.slots[s].state != SlotState::Ready {
180            return None;
181        }
182        self.slots[s].last_used = self.epoch;
183        self.slots[s].value.as_ref()
184    }
185
186    /// Like [`get`](Self::get) but without touching the LRU clock.
187    pub fn peek(&self, key: u16) -> Option<&V> {
188        let s = self.slot_of(key)?;
189        if self.slots[s].state != SlotState::Ready {
190            return None;
191        }
192        self.slots[s].value.as_ref()
193    }
194
195    /// Reserve a slot for `key` and mark it `Loading`, evicting the
196    /// least-recently-used unpinned `Ready` slot if the cache is full. Returns
197    /// a [`Reservation`] for the caller to complete with
198    /// [`finish_load`](Self::finish_load), or `None` if `key` is out of range
199    /// or every slot is pinned or already loading. If `key` already has a
200    /// slot, a reservation for that slot is returned unchanged (no duplicate
201    /// load is started).
202    pub fn begin_load(&mut self, key: u16) -> Option<Reservation> {
203        if !Self::key_ok(key) {
204            return None;
205        }
206        if let Some(s) = self.slot_of(key) {
207            return Some(Reservation::new(s, key));
208        }
209        let s = self.alloc_slot()?;
210        self.detach(s);
211        self.slots[s] = Slot {
212            key,
213            value: None,
214            state: SlotState::Loading,
215            last_used: self.epoch,
216            pinned: false,
217        };
218        self.key_to_slot[key as usize] = s as u16;
219        Some(Reservation::new(s, key))
220    }
221
222    /// Complete a [`begin_load`](Self::begin_load): store the value and mark
223    /// the slot `Ready` and most-recently-used. Returns [`Stale`] when the
224    /// reservation's key no longer owns its slot (it was evicted, and the slot
225    /// may now be loading another key), and stores nothing.
226    pub fn finish_load(&mut self, reservation: Reservation, value: V) -> Result<(), Stale> {
227        let slot = reservation.slot();
228        if slot < N
229            && self.slots[slot].state != SlotState::Empty
230            && self.slots[slot].key == reservation.key
231        {
232            self.slots[slot].value = Some(value);
233            self.slots[slot].state = SlotState::Ready;
234            self.slots[slot].last_used = self.epoch;
235            Ok(())
236        } else {
237            Err(Stale)
238        }
239    }
240
241    /// Renamed to [`begin_load`](Self::begin_load), which returns the key with
242    /// the slot so a stale completion can be told from a live one.
243    #[deprecated(note = "renamed to `begin_load`")]
244    pub fn reserve(&mut self, key: u16) -> Option<usize> {
245        self.begin_load(key).map(|r| r.slot())
246    }
247
248    /// Renamed to [`finish_load`](Self::finish_load). A bare slot index cannot
249    /// tell that the slot was evicted and reused for another key since
250    /// [`reserve`](Self::reserve), so a late completion stores its value under
251    /// the wrong key; this keeps that behaviour for one stage.
252    #[deprecated(note = "renamed to `finish_load`, which checks the key still owns the slot")]
253    pub fn mark_ready(&mut self, slot: usize, value: V) {
254        if slot < N && self.slots[slot].state != SlotState::Empty {
255            self.slots[slot].value = Some(value);
256            self.slots[slot].state = SlotState::Ready;
257            self.slots[slot].last_used = self.epoch;
258        }
259    }
260
261    /// Return the cached value for `key`, or synchronously build and insert it.
262    /// Evicts LRU on a miss when full. If `build` returns `None` the reservation
263    /// is released and this returns `None`.
264    pub fn get_or_insert_with<F>(&mut self, key: u16, build: F) -> Option<&V>
265    where
266        F: FnOnce() -> Option<V>,
267    {
268        if self.contains_ready(key) {
269            return self.get(key);
270        }
271        let r = self.begin_load(key)?;
272        let s = r.slot();
273        match build() {
274            Some(v) => {
275                // A fresh reservation owns its slot, so this cannot be stale.
276                let _ = self.finish_load(r, v);
277                self.slots[s].value.as_ref()
278            }
279            None => {
280                self.evict_slot(s);
281                None
282            }
283        }
284    }
285
286    /// Pin `key`'s slot so it is never evicted. No-op if absent.
287    pub fn pin(&mut self, key: u16) {
288        if let Some(s) = self.slot_of(key) {
289            self.slots[s].pinned = true;
290        }
291    }
292
293    /// Clear all pins.
294    pub fn unpin_all(&mut self) {
295        for s in self.slots.iter_mut() {
296            s.pinned = false;
297        }
298    }
299
300    /// Replace the pin set: unpin everything, then pin each present key in
301    /// `keys`. This is the "declare the working set" call a streaming reconcile
302    /// makes each cycle.
303    pub fn set_pinned(&mut self, keys: &[u16]) {
304        self.unpin_all();
305        for &k in keys {
306            self.pin(k);
307        }
308    }
309
310    /// Evict `key` (any state) back to `Empty`. No-op if absent.
311    pub fn evict(&mut self, key: u16) {
312        if let Some(s) = self.slot_of(key) {
313            self.evict_slot(s);
314        }
315    }
316
317    /// Evict every `Ready`, unpinned slot whose key is not in `keep`. Used by a
318    /// reconcile to drop rooms that left the desired set while protecting the
319    /// pinned working set. Returns the number evicted.
320    pub fn evict_ready_outside(&mut self, keep: &[u16]) -> usize {
321        let mut evicted = 0;
322        for s in 0..N {
323            if self.slots[s].state == SlotState::Ready
324                && !self.slots[s].pinned
325                && !keep.contains(&self.slots[s].key)
326            {
327                self.evict_slot(s);
328                evicted += 1;
329            }
330        }
331        evicted
332    }
333
334    /// Number of `Ready` slots.
335    pub fn ready_len(&self) -> usize {
336        self.slots
337            .iter()
338            .filter(|s| s.state == SlotState::Ready)
339            .count()
340    }
341
342    /// Number of occupied (`Loading` or `Ready`) slots.
343    pub fn len(&self) -> usize {
344        self.slots
345            .iter()
346            .filter(|s| s.state != SlotState::Empty)
347            .count()
348    }
349
350    /// Whether no slot is occupied.
351    pub fn is_empty(&self) -> bool {
352        self.len() == 0
353    }
354
355    /// Pick a slot to (re)use: first any `Empty`, else the least-recently-used
356    /// unpinned `Ready` slot. `Loading` and pinned slots are never taken, so an
357    /// in-flight load or the protected working set is never clobbered.
358    fn alloc_slot(&mut self) -> Option<usize> {
359        let mut victim: Option<usize> = None;
360        for s in 0..N {
361            match self.slots[s].state {
362                SlotState::Empty => return Some(s),
363                SlotState::Ready if !self.slots[s].pinned => {
364                    let better = match victim {
365                        None => true,
366                        Some(v) => self.slots[s].last_used < self.slots[v].last_used,
367                    };
368                    if better {
369                        victim = Some(s);
370                    }
371                }
372                _ => {}
373            }
374        }
375        victim
376    }
377
378    /// Drop a slot's reverse-map entry if it still points here.
379    fn detach(&mut self, slot: usize) {
380        let s = &self.slots[slot];
381        if s.state != SlotState::Empty {
382            let k = s.key as usize;
383            if k < MAX_KEY && self.key_to_slot[k] == slot as u16 {
384                self.key_to_slot[k] = NONE;
385            }
386        }
387    }
388
389    fn evict_slot(&mut self, slot: usize) {
390        self.detach(slot);
391        self.slots[slot] = Slot {
392            key: NONE,
393            value: None,
394            state: SlotState::Empty,
395            last_used: 0,
396            pinned: false,
397        };
398    }
399}
400
401#[cfg(test)]
402mod tests {
403    use super::*;
404
405    type Cache = SlotCache<u32, 3, 16>;
406
407    /// Build and `Ready` a key in one step.
408    fn put(c: &mut Cache, key: u16, val: u32) {
409        let r = c.begin_load(key).expect("begin_load");
410        c.finish_load(r, val).unwrap();
411    }
412
413    #[test]
414    fn empty_start() {
415        let c = Cache::new();
416        assert!(c.is_empty());
417        assert_eq!(c.ready_len(), 0);
418        assert!(!c.contains_ready(0));
419    }
420
421    #[test]
422    fn insert_then_get_roundtrips_and_slot_is_stable() {
423        let mut c = Cache::new();
424        let r = c.begin_load(5).unwrap();
425        let s = r.slot();
426        assert!(c.is_loading(5));
427        c.finish_load(r, 500).unwrap();
428        assert!(c.contains_ready(5));
429        assert_eq!(c.get(5), Some(&500));
430        assert_eq!(c.slot_of(5), Some(s));
431        // re-reserving an existing key returns the same slot, no second load
432        assert_eq!(c.begin_load(5), Some(r));
433    }
434
435    #[test]
436    fn a_load_that_finishes_after_its_slot_was_reused_is_refused() {
437        // The async case: a CD load for key 1 is in flight, key 1 is evicted,
438        // key 2 takes the slot, then key 1's load completes.
439        let mut c = SlotCache::<u32, 1, 16>::new();
440        let stale = c.begin_load(1).unwrap();
441        c.evict(1);
442        let live = c.begin_load(2).unwrap();
443        assert_eq!(live.slot(), stale.slot(), "the one slot is reused");
444
445        assert_eq!(c.finish_load(stale, 111), Err(Stale));
446        // Key 2 is still loading and holds nothing of key 1's.
447        assert!(c.is_loading(2));
448        assert_eq!(c.get(2), None);
449
450        c.finish_load(live, 222).unwrap();
451        assert_eq!(c.get(2), Some(&222));
452        assert!(!c.contains_ready(1));
453    }
454
455    #[test]
456    fn finishing_a_reservation_whose_slot_was_emptied_is_refused() {
457        let mut c = Cache::new();
458        let r = c.begin_load(3).unwrap();
459        c.evict(3);
460        assert_eq!(c.finish_load(r, 30), Err(Stale));
461        assert!(c.is_empty());
462    }
463
464    /// The deprecated pair keeps the old behaviour for one stage: a bare slot
465    /// index cannot tell the slot changed hands, so key 2 reads key 1's value.
466    #[allow(deprecated)]
467    #[test]
468    fn the_deprecated_pair_still_stores_under_the_wrong_key() {
469        let mut c = SlotCache::<u32, 1, 16>::new();
470        let slot = c.reserve(1).unwrap();
471        c.evict(1);
472        assert_eq!(c.reserve(2), Some(slot));
473        c.mark_ready(slot, 111);
474        assert_eq!(c.get(2), Some(&111));
475    }
476
477    #[test]
478    fn get_or_insert_builds_on_miss_returns_on_hit() {
479        let mut c = Cache::new();
480        let mut builds = 0;
481        let v = *c
482            .get_or_insert_with(7, || {
483                builds += 1;
484                Some(70)
485            })
486            .unwrap();
487        assert_eq!(v, 70);
488        // hit: the build closure must NOT run; the cached value is returned
489        let v2 = *c
490            .get_or_insert_with(7, || {
491                builds += 1;
492                Some(999)
493            })
494            .unwrap();
495        assert_eq!(v2, 70);
496        assert_eq!(builds, 1, "build runs only on a miss");
497    }
498
499    #[test]
500    fn get_or_insert_build_failure_leaves_slot_empty() {
501        let mut c = Cache::new();
502        assert_eq!(c.get_or_insert_with(3, || None), None);
503        assert!(!c.contains_ready(3));
504        assert!(c.is_empty());
505    }
506
507    #[test]
508    fn lru_evicts_least_recently_used() {
509        let mut c = Cache::new();
510        put(&mut c, 1, 10);
511        c.bump_epoch();
512        put(&mut c, 2, 20);
513        c.bump_epoch();
514        put(&mut c, 3, 30);
515        // touch 1 and 3 so 2 becomes the LRU
516        c.bump_epoch();
517        let _ = c.get(1);
518        let _ = c.get(3);
519        // inserting a 4th evicts key 2
520        c.bump_epoch();
521        put(&mut c, 4, 40);
522        assert!(!c.contains_ready(2), "LRU victim should be evicted");
523        assert!(c.contains_ready(1) && c.contains_ready(3) && c.contains_ready(4));
524        assert_eq!(c.slot_of(2), None);
525    }
526
527    #[test]
528    fn pin_protects_from_eviction() {
529        let mut c = Cache::new();
530        put(&mut c, 1, 10);
531        put(&mut c, 2, 20);
532        put(&mut c, 3, 30);
533        // pin the otherwise-oldest key
534        c.bump_epoch();
535        let _ = c.get(2);
536        let _ = c.get(3);
537        c.pin(1); // 1 is LRU but pinned
538        c.bump_epoch();
539        put(&mut c, 4, 40);
540        assert!(c.contains_ready(1), "pinned key must survive");
541        assert!(
542            !c.contains_ready(2),
543            "an unpinned key is the victim instead"
544        );
545    }
546
547    #[test]
548    fn reserve_fails_when_all_slots_pinned() {
549        let mut c = Cache::new();
550        put(&mut c, 1, 10);
551        put(&mut c, 2, 20);
552        put(&mut c, 3, 30);
553        c.set_pinned(&[1, 2, 3]);
554        assert_eq!(c.begin_load(4), None, "no evictable slot");
555        assert!(!c.contains_ready(4));
556    }
557
558    #[test]
559    fn evict_ready_outside_keeps_listed_and_pinned() {
560        let mut c = Cache::new();
561        put(&mut c, 1, 10);
562        put(&mut c, 2, 20);
563        put(&mut c, 3, 30);
564        c.pin(3);
565        let evicted = c.evict_ready_outside(&[1]);
566        assert_eq!(evicted, 1); // only 2 leaves
567        assert!(c.contains_ready(1)); // in keep list
568        assert!(!c.contains_ready(2)); // dropped
569        assert!(c.contains_ready(3)); // pinned
570    }
571
572    #[test]
573    fn reverse_map_stays_consistent_across_reuse() {
574        let mut c = Cache::new();
575        put(&mut c, 1, 10);
576        put(&mut c, 2, 20);
577        put(&mut c, 3, 30);
578        c.bump_epoch();
579        put(&mut c, 4, 40); // evicts LRU (1), reuses its slot
580        assert_eq!(c.slot_of(1), None, "evicted key has no slot");
581        assert!(c.contains_ready(4));
582        // the slot 4 took must not still answer for 1
583        let s4 = c.slot_of(4).unwrap();
584        assert_ne!(c.slot_of(2), Some(s4));
585    }
586
587    #[test]
588    fn out_of_range_key_is_rejected() {
589        let mut c = Cache::new();
590        assert_eq!(c.begin_load(16), None); // == MAX_KEY
591        assert_eq!(c.begin_load(NONE), None);
592        assert!(!c.contains_ready(16));
593    }
594}
psx_cache/lib.rs

psx_cache/
lib.rs
