kevy_alloc/
heap_claims.rs

1//! The claimed-word layer of [`Heap`] (child module via `#[path]`, the
2//! house pattern) — the far-line amortizer for small-allocation churn.
3//! One segment-header round-trip claims up to 64 slots; handout and
4//! same-word recycling are heap-local. Split from `heap.rs` for the
5//! 500-LOC ceiling; the seam is real: everything here is the claim
6//! lifecycle, nothing else in the heap touches a claim's fields.
7
8use core::ptr::NonNull;
9
10use crate::class::{self, NCLASSES};
11use crate::segment::Segment;
12
13use super::Heap;
14
15/// One claimed word of one span, held heap-locally. `base` is the
16/// span's data base, precomputed so the handout path performs no
17/// segment-header access at all.
18#[derive(Clone, Copy)]
19pub(crate) struct Claim {
20    pub(crate) seg: NonNull<Segment>,
21    pub(crate) span_ix: u8,
22    pub(crate) word: u8,
23    pub(crate) claimed: u64,
24    pub(crate) taken: u64,
25    pub(crate) base: *mut u8,
26}
27
28impl Heap {
29    /// Hand out the lowest available bit of the claimed word. Fully
30    /// heap-local: no segment-header access on this path.
31    pub(super) fn pop_claimed(&mut self, c: usize) -> Option<NonNull<u8>> {
32        let cl = self.claims[c].as_mut()?;
33        let avail = cl.claimed & !cl.taken;
34        if avail == 0 {
35            return None;
36        }
37        let b = avail.trailing_zeros();
38        cl.taken |= 1u64 << b;
39        let i = u32::from(cl.word) * 64 + b;
40        NonNull::new(cl.base.wrapping_add(i as usize * class::size_of(c)))
41    }
42
43    /// Retire any outstanding claim, then claim the lowest holed word
44    /// of the class's current span. `None` = the span is full (the
45    /// slow path takes over) or there is no current span.
46    pub(super) fn refill_claim(&mut self, c: usize) -> Option<()> {
47        self.retire_claim(c);
48        let (seg, span_ix) = self.partial[c]?;
49        // SAFETY: partial entries are spans this heap assigned and has
50        // not released; the segment header outlives them.
51        let meta = unsafe { &mut (*seg.as_ptr()).spans[span_ix as usize] };
52        let Some((word, claimed)) = meta.claim_word() else {
53            self.partial[c] = None;
54            return None;
55        };
56        // Claimed bits may land in returned pages; a fresh allocation
57        // owes nothing to its contents, only the bookkeeping notices.
58        if meta.discarded != 0 {
59            let slot_size = class::size_of(c);
60            let lo = u32::from(word) * 64 + claimed.trailing_zeros();
61            let hi = u32::from(word) * 64 + (63 - claimed.leading_zeros());
62            let (pa, _) = crate::pagemap::pages_of_slot(lo, slot_size);
63            let (_, pb) = crate::pagemap::pages_of_slot(hi, slot_size);
64            for p in pa..=pb {
65                meta.discarded &= !(1u16 << p);
66            }
67        }
68        // SAFETY: same header liveness as above.
69        let base = unsafe { seg.as_ref() }.span_base(span_ix as usize);
70        self.claims[c] = Some(Claim { seg, span_ix, word, claimed, taken: 0, base });
71        Some(())
72    }
73
74    /// Write a claim's unused bits back to its span. The span regains
75    /// its holes and the hint walks back; a formerly-full span is
76    /// findable again through `adopt_partial`'s scan (the partial ring
77    /// is an optimization, not the source of truth).
78    pub(super) fn retire_claim(&mut self, c: usize) {
79        let Some(cl) = self.claims[c].take() else { return };
80        let unused = cl.claimed & !cl.taken;
81        if unused == 0 {
82            return;
83        }
84        // SAFETY: claims only reference spans of this heap's live
85        // segments; the header outlives the claim.
86        let meta = unsafe { &mut (*cl.seg.as_ptr()).spans[cl.span_ix as usize] };
87        meta.retire_word(cl.word, unused);
88    }
89
90    /// Retire every class's claim — the write-back before anything
91    /// that reads span occupancy as truth (reclaim's page sweep, drop).
92    pub fn flush_claims(&mut self) {
93        for c in 0..NCLASSES {
94            self.retire_claim(c);
95        }
96    }
97
98    /// Bytes sitting claimed-but-unused across every class — from the
99    /// span's view they are live (the claim pins them), from the
100    /// heap's they are allocatable. The snapshot folds them into
101    /// `span_free` so the accounting identity balances without a
102    /// flush.
103    pub(crate) fn claims_unused_bytes(&self) -> u64 {
104        let mut sum = 0u64;
105        for (c, cl) in self.claims.iter().enumerate() {
106            if let Some(cl) = cl {
107                sum += u64::from((cl.claimed & !cl.taken).count_ones()) * class::size_of(c) as u64;
108            }
109        }
110        sum
111    }
112}
kevy_alloc/heap_claims.rs

kevy_alloc/
heap_claims.rs
