psx_residency/
pool.rs

1//! Contiguous-run page allocation with generation handles.
2//!
3//! Lifted from the retired grid streamer's `StreamedRoomPages` (PSoXide-editor
4//! `psx-game-runtime`), split in two: [`PagePool`] here is only the allocation
5//! map (which pages belong to which allocation), so it works for RAM pages,
6//! VRAM texture slots and SPU RAM blocks alike; the bytes of RAM pages live in
7//! [`crate::PageBuffer`]. What carried over: each allocation is one contiguous
8//! run (a CD transfer lands in its final place), a [`Handle`] carries the slot
9//! and a generation so a stale handle stops resolving the moment its run is
10//! freed or reused, and compaction slides runs toward page 0. What is new:
11//! first-fit or best-fit placement, locked runs that compaction and callers
12//! must not move, one compaction step at a time (so it fits a CPU budget), and
13//! fragmentation statistics.
14
15/// Bytes in one page: one CD-ROM Mode 1 sector.
16pub const PAGE_BYTES: usize = 2048;
17
18/// A run of pages: `page_count` pages starting at `first_page`.
19#[derive(Copy, Clone, Debug, PartialEq, Eq)]
20pub struct PageRun {
21    /// Index of the first page.
22    pub first_page: u32,
23    /// Number of pages.
24    pub page_count: u32,
25}
26
27impl PageRun {
28    /// Index one past the last page.
29    pub const fn end_page(self) -> u32 {
30        self.first_page + self.page_count
31    }
32
33    /// Capacity of the run in bytes, for pages of [`PAGE_BYTES`].
34    pub const fn capacity_bytes(self) -> usize {
35        self.page_count as usize * PAGE_BYTES
36    }
37}
38
39/// Generation-checked identity of one allocation. It stops resolving as soon
40/// as its allocation is freed, even if the slot is reused for another run.
41#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
42pub struct Handle {
43    pool: u8,
44    slot: u16,
45    generation: u32,
46}
47
48impl Handle {
49    /// A handle that is never current, for filling buffers.
50    pub const NONE: Handle = Handle {
51        pool: u8::MAX,
52        slot: u16::MAX,
53        generation: 0,
54    };
55
56    /// Pool number the handle was allocated from.
57    pub const fn pool(self) -> u8 {
58        self.pool
59    }
60
61    /// Allocation slot inside that pool.
62    pub const fn slot(self) -> u16 {
63        self.slot
64    }
65
66    /// Generation of the slot when the handle was issued.
67    pub const fn generation(self) -> u32 {
68        self.generation
69    }
70}
71
72/// Which free gap a new run goes into.
73#[derive(Copy, Clone, Debug, PartialEq, Eq)]
74pub enum Placement {
75    /// The lowest-addressed gap that is large enough.
76    FirstFit,
77    /// The smallest gap that is large enough (ties go to the lowest address).
78    BestFit,
79}
80
81/// Free-space shape of a pool, for fragmentation reports.
82#[derive(Copy, Clone, Debug, Default, PartialEq, Eq)]
83pub struct Fragmentation {
84    /// Free pages in total.
85    pub free_pages: u32,
86    /// Pages in the largest free run.
87    pub largest_free_run: u32,
88    /// Number of separate free runs.
89    pub free_run_count: u32,
90}
91
92impl Fragmentation {
93    /// Share of free space that is not in the largest run, in permille
94    /// (0 when all free space is one run, or there is none).
95    pub const fn permille(self) -> u32 {
96        if self.free_pages == 0 {
97            return 0;
98        }
99        // 32-bit only: scale huge pools down so the product cannot overflow.
100        let mut free = self.free_pages;
101        let mut largest = self.largest_free_run;
102        while free > u32::MAX / 1000 {
103            free >>= 1;
104            largest >>= 1;
105        }
106        1000 - largest * 1000 / free
107    }
108}
109
110/// One run moved by [`PagePool::compact_step`].
111#[derive(Copy, Clone, Debug, PartialEq, Eq)]
112pub struct Moved {
113    /// The moved allocation (its handle stays valid).
114    pub handle: Handle,
115    /// Where it was.
116    pub from: PageRun,
117    /// First page it occupies now.
118    pub to_page: u32,
119}
120
121#[derive(Copy, Clone)]
122struct Run {
123    first: u32,
124    /// Zero means the slot is free.
125    count: u32,
126    generation: u32,
127    locked: bool,
128}
129
130const FREE_RUN: Run = Run {
131    first: 0,
132    count: 0,
133    generation: 0,
134    locked: false,
135};
136
137/// Allocation map of `capacity_pages` pages shared by up to `SLOTS` runs.
138///
139/// Pure bookkeeping: the pool never touches page contents. All state is plain
140/// integers, so a static pool can live in `.bss`.
141pub struct PagePool<const SLOTS: usize> {
142    pool: u8,
143    capacity_pages: u32,
144    placement: Placement,
145    runs: [Run; SLOTS],
146    /// Live slots sorted by first page; only `order[..live]` is meaningful.
147    order: [u16; SLOTS],
148    live: usize,
149    used_pages: u32,
150    layout_generation: u32,
151}
152
153impl<const SLOTS: usize> PagePool<SLOTS> {
154    /// An empty pool numbered `pool` (stamped into its handles) of
155    /// `capacity_pages` pages.
156    pub const fn new(pool: u8, capacity_pages: u32, placement: Placement) -> Self {
157        Self {
158            pool,
159            capacity_pages,
160            placement,
161            runs: [FREE_RUN; SLOTS],
162            order: [0; SLOTS],
163            live: 0,
164            used_pages: 0,
165            layout_generation: 0,
166        }
167    }
168
169    /// Total pages in the pool.
170    pub const fn capacity_pages(&self) -> u32 {
171        self.capacity_pages
172    }
173
174    /// Pages held by live allocations.
175    pub const fn used_pages(&self) -> u32 {
176        self.used_pages
177    }
178
179    /// Pages not held by any allocation (possibly scattered).
180    pub const fn free_pages(&self) -> u32 {
181        self.capacity_pages - self.used_pages
182    }
183
184    /// Number of live allocations.
185    pub const fn live_count(&self) -> usize {
186        self.live
187    }
188
189    /// Placement policy for new runs.
190    pub const fn placement(&self) -> Placement {
191        self.placement
192    }
193
194    /// Change the placement policy; existing runs stay where they are.
195    pub fn set_placement(&mut self, placement: Placement) {
196        self.placement = placement;
197    }
198
199    /// Bumped every time compaction moves a run. A byte view taken before a
200    /// bump may point at the wrong pages: re-resolve it.
201    pub const fn layout_generation(&self) -> u32 {
202        self.layout_generation
203    }
204
205    /// Allocate a contiguous run of `page_count` pages, or `None` when no gap
206    /// is large enough or every slot is taken. Never moves another run.
207    pub fn allocate(&mut self, page_count: u32) -> Option<(Handle, PageRun)> {
208        if page_count == 0 {
209            return None;
210        }
211        let slot = self.runs.iter().position(|run| run.count == 0)?;
212        let first = self.find_fit(page_count)?;
213        let generation = self.runs[slot].generation.wrapping_add(1);
214        self.runs[slot] = Run {
215            first,
216            count: page_count,
217            generation,
218            locked: false,
219        };
220        let mut position = self.live;
221        while position > 0 && self.runs[self.order[position - 1] as usize].first > first {
222            self.order[position] = self.order[position - 1];
223            position -= 1;
224        }
225        self.order[position] = slot as u16;
226        self.live += 1;
227        self.used_pages += page_count;
228        Some((
229            Handle {
230                pool: self.pool,
231                slot: slot as u16,
232                generation,
233            },
234            PageRun {
235                first_page: first,
236                page_count,
237            },
238        ))
239    }
240
241    /// First page of the gap a run of `page_count` pages would get.
242    pub fn find_fit(&self, page_count: u32) -> Option<u32> {
243        if page_count == 0 || page_count > self.free_pages() {
244            return None;
245        }
246        let mut best: Option<(u32, u32)> = None;
247        for (start, length) in self.gaps() {
248            if length < page_count {
249                continue;
250            }
251            match self.placement {
252                Placement::FirstFit => return Some(start),
253                Placement::BestFit => {
254                    if best.is_none_or(|(_, best_length)| length < best_length) {
255                        best = Some((start, length));
256                    }
257                }
258            }
259        }
260        best.map(|(start, _)| start)
261    }
262
263    /// Free `handle`. `false` (and no change) when the handle is stale.
264    pub fn free(&mut self, handle: Handle) -> bool {
265        if !self.is_current(handle) {
266            return false;
267        }
268        let slot = handle.slot as usize;
269        let position = self.order[..self.live]
270            .iter()
271            .position(|&s| s as usize == slot)
272            .expect("a live run is always in the order table");
273        self.order.copy_within(position + 1..self.live, position);
274        self.live -= 1;
275        self.used_pages -= self.runs[slot].count;
276        self.runs[slot] = Run {
277            generation: self.runs[slot].generation.wrapping_add(1),
278            ..FREE_RUN
279        };
280        true
281    }
282
283    /// Whether `handle` still names the allocation it was issued for.
284    pub fn is_current(&self, handle: Handle) -> bool {
285        handle.pool == self.pool
286            && self
287                .runs
288                .get(handle.slot as usize)
289                .is_some_and(|run| run.count > 0 && run.generation == handle.generation)
290    }
291
292    /// The pages `handle` names, or `None` when it is stale.
293    pub fn try_run(&self, handle: Handle) -> Option<PageRun> {
294        if !self.is_current(handle) {
295            return None;
296        }
297        let run = self.runs[handle.slot as usize];
298        Some(PageRun {
299            first_page: run.first,
300            page_count: run.count,
301        })
302    }
303
304    /// Lock or unlock the run. A locked run is never moved by
305    /// [`PagePool::compact_step`] (a transfer is landing in it, or a consumer
306    /// holds a raw view of it). `false` when the handle is stale.
307    pub fn set_locked(&mut self, handle: Handle, locked: bool) -> bool {
308        if !self.is_current(handle) {
309            return false;
310        }
311        self.runs[handle.slot as usize].locked = locked;
312        true
313    }
314
315    /// Whether the run is locked (`false` for a stale handle).
316    pub fn is_locked(&self, handle: Handle) -> bool {
317        self.is_current(handle) && self.runs[handle.slot as usize].locked
318    }
319
320    /// Live allocations in address order as `(slot, run, locked)`.
321    pub fn iter_runs(&self) -> impl Iterator<Item = (u16, PageRun, bool)> + '_ {
322        self.order[..self.live].iter().map(move |&slot| {
323            let run = self.runs[slot as usize];
324            (
325                slot,
326                PageRun {
327                    first_page: run.first,
328                    page_count: run.count,
329                },
330                run.locked,
331            )
332        })
333    }
334
335    /// Handle of the live allocation in `slot`.
336    pub fn handle_of_slot(&self, slot: u16) -> Option<Handle> {
337        let run = self.runs.get(slot as usize)?;
338        (run.count > 0).then_some(Handle {
339            pool: self.pool,
340            slot,
341            generation: run.generation,
342        })
343    }
344
345    /// Free gaps in address order as `(first_page, page_count)`.
346    pub fn gaps(&self) -> impl Iterator<Item = (u32, u32)> + '_ {
347        let mut cursor = 0u32;
348        let mut position = 0usize;
349        let mut done = false;
350        core::iter::from_fn(move || {
351            while !done {
352                let (end, next_cursor) = if position < self.live {
353                    let run = self.runs[self.order[position] as usize];
354                    position += 1;
355                    (run.first, run.first + run.count)
356                } else {
357                    done = true;
358                    (self.capacity_pages, self.capacity_pages)
359                };
360                let start = cursor;
361                cursor = next_cursor;
362                if end > start {
363                    return Some((start, end - start));
364                }
365            }
366            None
367        })
368    }
369
370    /// Shape of the free space.
371    pub fn fragmentation(&self) -> Fragmentation {
372        let mut result = Fragmentation::default();
373        for (_, length) in self.gaps() {
374            result.free_pages += length;
375            result.free_run_count += 1;
376            result.largest_free_run = result.largest_free_run.max(length);
377        }
378        result
379    }
380
381    /// Slide the lowest unlocked run that has free space below it down to the
382    /// lowest page it can reach, calling `copy(from, to_page)` so the owner of
383    /// the bytes moves them (the destination may overlap the source; copy as
384    /// `memmove`). Locked runs stay put and act as barriers. One run per call,
385    /// so a caller can spend a CPU budget on it. `None` when nothing can move.
386    pub fn compact_step(&mut self, mut copy: impl FnMut(PageRun, u32)) -> Option<Moved> {
387        let mut cursor = 0u32;
388        for position in 0..self.live {
389            let slot = self.order[position] as usize;
390            let run = self.runs[slot];
391            if !run.locked && run.first > cursor {
392                let from = PageRun {
393                    first_page: run.first,
394                    page_count: run.count,
395                };
396                copy(from, cursor);
397                self.runs[slot].first = cursor;
398                self.layout_generation = self.layout_generation.wrapping_add(1);
399                return Some(Moved {
400                    handle: Handle {
401                        pool: self.pool,
402                        slot: slot as u16,
403                        generation: run.generation,
404                    },
405                    from,
406                    to_page: cursor,
407                });
408            }
409            cursor = run.first + run.count;
410        }
411        None
412    }
413
414    /// Check the structural invariants (host tests and debug assertions).
415    #[cfg(any(test, debug_assertions))]
416    pub fn check_invariants(&self) {
417        let mut used = 0u32;
418        let mut previous_end = 0u32;
419        for position in 0..self.live {
420            let run = self.runs[self.order[position] as usize];
421            assert!(run.count > 0, "order lists a free slot");
422            assert!(run.first >= previous_end, "runs overlap or are unsorted");
423            previous_end = run.first + run.count;
424            assert!(previous_end <= self.capacity_pages, "run past capacity");
425            used += run.count;
426        }
427        assert_eq!(used, self.used_pages, "used_pages out of step");
428        let live = self.runs.iter().filter(|run| run.count > 0).count();
429        assert_eq!(live, self.live, "live count out of step");
430    }
431}
432
433#[cfg(test)]
434mod tests {
435    use super::*;
436
437    #[test]
438    fn charges_exact_page_count() {
439        let mut pool = PagePool::<3>::new(0, 8, Placement::FirstFit);
440        let (_, a) = pool.allocate(1).unwrap();
441        let (_, b) = pool.allocate(2).unwrap();
442        assert_eq!(a.page_count, 1);
443        assert_eq!(b.page_count, 2);
444        assert_eq!(pool.free_pages(), 5);
445        pool.check_invariants();
446    }
447
448    #[test]
449    fn released_or_reused_slot_invalidates_old_handle() {
450        let mut pool = PagePool::<1>::new(0, 4, Placement::FirstFit);
451        let (first, _) = pool.allocate(1).unwrap();
452        assert!(pool.try_run(first).is_some());
453        assert!(pool.free(first));
454        assert!(pool.try_run(first).is_none());
455        assert!(!pool.free(first), "double free is refused");
456        let (second, _) = pool.allocate(1).unwrap();
457        assert_eq!(first.slot(), second.slot());
458        assert_ne!(first.generation(), second.generation());
459        assert!(pool.try_run(first).is_none(), "reuse must not revive it");
460    }
461
462    #[test]
463    fn handle_from_another_pool_is_stale() {
464        let mut a = PagePool::<2>::new(0, 4, Placement::FirstFit);
465        let b = PagePool::<2>::new(1, 4, Placement::FirstFit);
466        let (handle, _) = a.allocate(1).unwrap();
467        assert!(!b.is_current(handle));
468    }
469
470    #[test]
471    fn placement_policies_choose_different_gaps() {
472        // Layout: [A 2][gap 4][B 1][gap 2][C 1]; capacity 10.
473        let build = |placement| {
474            let mut pool = PagePool::<8>::new(0, 10, placement);
475            let (a, _) = pool.allocate(2).unwrap();
476            let (gap1, _) = pool.allocate(4).unwrap();
477            let (b, _) = pool.allocate(1).unwrap();
478            let (gap2, _) = pool.allocate(2).unwrap();
479            let (c, _) = pool.allocate(1).unwrap();
480            pool.free(gap1);
481            pool.free(gap2);
482            (pool, [a, b, c])
483        };
484        let (first_fit, _) = build(Placement::FirstFit);
485        let (best_fit, _) = build(Placement::BestFit);
486        assert_eq!(first_fit.find_fit(2), Some(2));
487        assert_eq!(best_fit.find_fit(2), Some(7));
488        assert_eq!(best_fit.find_fit(4), Some(2));
489        assert_eq!(best_fit.find_fit(5), None);
490    }
491
492    #[test]
493    fn fragmented_pool_compacts_and_keeps_handles() {
494        let mut pool = PagePool::<4>::new(0, 8, Placement::FirstFit);
495        let (a, _) = pool.allocate(2).unwrap();
496        let (b, _) = pool.allocate(2).unwrap();
497        let (c, _) = pool.allocate(2).unwrap();
498        pool.free(b);
499        assert_eq!(pool.find_fit(4), None);
500        assert_eq!(pool.fragmentation().free_run_count, 2);
501        let before = pool.layout_generation();
502        let mut copies = [None; 2];
503        let mut count = 0;
504        while let Some(moved) = pool.compact_step(|from, to| {
505            copies[count] = Some((from.first_page, to));
506        }) {
507            assert_eq!(moved.handle, c);
508            count += 1;
509        }
510        assert_eq!(copies[0], Some((4, 2)));
511        assert_ne!(pool.layout_generation(), before);
512        assert_eq!(pool.try_run(a).unwrap().first_page, 0);
513        assert_eq!(pool.try_run(c).unwrap().first_page, 2);
514        assert_eq!(pool.find_fit(4), Some(4));
515        pool.check_invariants();
516    }
517
518    #[test]
519    fn locked_run_is_a_compaction_barrier() {
520        let mut pool = PagePool::<5>::new(0, 12, Placement::FirstFit);
521        let (a, _) = pool.allocate(2).unwrap();
522        let (b, _) = pool.allocate(2).unwrap();
523        let (c, _) = pool.allocate(2).unwrap();
524        let (d, _) = pool.allocate(2).unwrap();
525        pool.free(a);
526        pool.free(c);
527        assert!(pool.set_locked(b, true));
528        assert!(pool.is_locked(b));
529        // Layout: [gap 0..2][b locked 2..4][gap 4..6][d 6..8]. d slides to 4,
530        // b stays, and nothing jumps over b into the first gap.
531        let moved = pool.compact_step(|_, _| {}).unwrap();
532        assert_eq!(moved.handle, d);
533        assert_eq!(moved.to_page, 4);
534        assert!(pool.compact_step(|_, _| {}).is_none());
535        assert_eq!(pool.try_run(b).unwrap().first_page, 2);
536        assert_eq!(pool.try_run(d).unwrap().first_page, 4);
537        pool.check_invariants();
538    }
539
540    #[test]
541    fn free_space_shape_is_reported() {
542        let mut pool = PagePool::<4>::new(0, 10, Placement::FirstFit);
543        let (a, _) = pool.allocate(3).unwrap();
544        let (_b, _) = pool.allocate(3).unwrap();
545        pool.free(a);
546        let shape = pool.fragmentation();
547        assert_eq!(shape.free_pages, 7);
548        assert_eq!(shape.largest_free_run, 4);
549        assert_eq!(shape.free_run_count, 2);
550        assert_eq!(shape.permille(), 1000 - 4 * 1000 / 7);
551    }
552
553    #[test]
554    fn full_slot_table_refuses_even_when_pages_are_free() {
555        let mut pool = PagePool::<2>::new(0, 100, Placement::FirstFit);
556        pool.allocate(1).unwrap();
557        pool.allocate(1).unwrap();
558        assert!(pool.allocate(1).is_none());
559        assert!(pool.allocate(0).is_none());
560    }
561}
psx_residency/pool.rs

psx_residency/
pool.rs
