Skip to main content

kevy_alloc/
stats.rs

1//! The accounting contract, as a type.
2//!
3//! The accounting contract fixed these fields before this
4//! crate existed, because both v5 RFCs state their ceiling as a
5//! decomposition and a gate that cannot assert *"these terms sum to the
6//! observed gap"* cannot check the only claim that matters.
7//!
8//! # The identity
9//!
10//! ```text
11//! mapped == live + rounding + cache + span_free + virgin
12//!         + hysteresis + segment_overhead
13//! ```
14//!
15//! Exact, with no tolerance. Every mapped byte is in exactly one of
16//! those states by construction, so a mismatch means something is
17//! miscounted — and unexplained bytes are precisely where glibc's 2.24×
18//! was hiding.
19//!
20//! # Two terms the contract did not have at T0
21//!
22//! T0 fixed five terms. Building the geometry showed the partition was
23//! not a partition, so two were added — declared here with the reason,
24//! which is what the contract requires (silently widening it is what is
25//! banned, not changing it):
26//!
27//! - **`virgin`** — spans hand out slots by bumping a cursor, so the
28//!   region above the cursor is *mapped but never touched*, and
29//!   therefore not resident. Folding it into slack would have made the
30//!   slack term look like memory when it is only address space. This
31//!   split is the difference between a number that predicts RSS and one
32//!   that does not.
33//! - **`segment_overhead`** — one span per segment holds the header.
34//!   1.6 % of every segment, structural and knowable, so it is named
35//!   rather than absorbed into a neighbour.
36//!
37//! # Examples
38//!
39//! ```
40//! use kevy_alloc::Heap;
41//! let mut heap = Heap::new(0);
42//! let p = heap.alloc(400, 8).ok_or("no mapping")?;
43//! let s = heap.snapshot();
44//! // the identity: every mapped byte sits in exactly one term
45//! assert_eq!(s.mapped, s.accounted());
46//! // SAFETY: `p` came from this heap with this size and alignment.
47//! unsafe { heap.dealloc(p, 400, 8) };
48//! # Ok::<(), &str>(())
49//! ```
50
51/// A snapshot of where every mapped byte is.
52///
53/// # Examples
54///
55/// ```
56/// use kevy_alloc::{Heap, Stats};
57/// let mut heap = Heap::new(0);
58/// let p = heap.alloc(100, 8).ok_or("no mapping")?;
59/// let s: Stats = heap.snapshot();
60/// assert_eq!(s.live, 100);
61/// assert!(s.balanced());
62/// // SAFETY: `p` came from this heap with this size and alignment.
63/// unsafe { heap.dealloc(p, 100, 8) };
64/// # Ok::<(), &str>(())
65/// ```
66#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
67#[non_exhaustive]
68pub struct Stats {
69    /// Total bytes mapped from the OS. The anchor.
70    ///
71    /// # Examples
72    ///
73    /// ```
74    /// # use kevy_alloc::Heap;
75    /// use kevy_alloc::segment::SEGMENT_BYTES;
76    /// let mut heap = Heap::new(0);
77    /// assert_eq!(heap.snapshot().mapped, 0);
78    /// let p = heap.alloc(100, 8).ok_or("no mapping")?;
79    /// // the first allocation maps one whole segment
80    /// assert_eq!(heap.snapshot().mapped, SEGMENT_BYTES as u64);
81    /// // SAFETY: `p` came from this heap with this size and alignment.
82    /// unsafe { heap.dealloc(p, 100, 8) };
83    /// # Ok::<(), &str>(())
84    /// ```
85    pub mapped: u64,
86    /// Sum of `Layout::size()` over live allocations — what callers
87    /// actually asked for, unrounded.
88    ///
89    /// # Examples
90    ///
91    /// ```
92    /// # use kevy_alloc::Heap;
93    /// let mut heap = Heap::new(0);
94    /// let p = heap.alloc(100, 8).ok_or("no mapping")?;
95    /// assert_eq!(heap.snapshot().live, 100);
96    /// // SAFETY: `p` came from this heap with this size and alignment.
97    /// unsafe { heap.dealloc(p, 100, 8) };
98    /// assert_eq!(heap.snapshot().live, 0);
99    /// # Ok::<(), &str>(())
100    /// ```
101    pub live: u64,
102    /// Sum of (slot size − requested size) over live allocations.
103    ///
104    /// # Examples
105    ///
106    /// ```
107    /// # use kevy_alloc::Heap;
108    /// let mut heap = Heap::new(0);
109    /// // 100 bytes are served from the 104-byte class
110    /// let p = heap.alloc(100, 8).ok_or("no mapping")?;
111    /// assert_eq!(heap.snapshot().rounding, 4);
112    /// // SAFETY: `p` came from this heap with this size and alignment.
113    /// unsafe { heap.dealloc(p, 100, 8) };
114    /// # Ok::<(), &str>(())
115    /// ```
116    pub rounding: u64,
117    /// Bytes parked on foreign-free lists, waiting to be drained home.
118    ///
119    /// # Examples
120    ///
121    /// ```
122    /// # use kevy_alloc::Heap;
123    /// let mut owner = Heap::new(1);
124    /// let mut other = Heap::new(2);
125    /// let p = owner.alloc(100, 8).ok_or("no mapping")?;
126    /// // SAFETY: `p` came from `owner` with this size and alignment; freeing
127    /// // it through another heap is the cross-shard path.
128    /// unsafe { other.dealloc(p, 100, 8) };
129    /// other.reclaim(); // ships the freed slot home
130    /// assert_eq!(owner.snapshot().cache, 104);
131    /// owner.drain_foreign();
132    /// assert_eq!(owner.snapshot().cache, 0);
133    /// # Ok::<(), &str>(())
134    /// ```
135    pub cache: u64,
136    /// Free slots in spans that were handed out before and returned to
137    /// the free pool: touched, therefore resident.
138    ///
139    /// # Examples
140    ///
141    /// ```
142    /// # use kevy_alloc::Heap;
143    /// let mut heap = Heap::new(0);
144    /// let a = heap.alloc(100, 8).ok_or("no mapping")?;
145    /// let before = heap.snapshot().span_free;
146    /// // SAFETY: `a` came from this heap with this size and alignment.
147    /// unsafe { heap.dealloc(a, 100, 8) };
148    /// // the freed slot stays mapped and touched, ready for the next request
149    /// assert_eq!(heap.snapshot().span_free, before + 104);
150    /// # Ok::<(), &str>(())
151    /// ```
152    pub span_free: u64,
153    /// Bytes whose pages have been handed back to the OS — mapped, not
154    /// resident. The v2 term: this is what page-granular reclaim
155    /// produces, and it did not exist while the reclaim unit was the
156    /// whole span.
157    ///
158    /// Two shapes, both genuinely returned: free slots inside a span
159    /// that is still live, and whole spans emptied and retired. The
160    /// second used to be filed under `hysteresis`, so this read 0 while
161    /// most of the map had in fact gone back.
162    ///
163    /// # Examples
164    ///
165    /// ```
166    /// # use kevy_alloc::Heap;
167    /// let mut heap = Heap::new(0);
168    /// let held: Vec<_> = (0..16_384).map(|_| heap.alloc(64, 8)).collect::<Option<_>>().ok_or("no mapping")?;
169    /// for p in held {
170    ///     // SAFETY: each came from this heap with this size and alignment.
171    ///     unsafe { heap.dealloc(p, 64, 8) };
172    /// }
173    /// // once they have gone unused for the purge delay
174    /// for _ in 0..=kevy_alloc::PURGE_DELAY {
175    ///     heap.reclaim();
176    /// }
177    /// let s = heap.snapshot();
178    /// // pages go back only where the system page matches the span geometry
179    /// assert_eq!(s.returned > 0, kevy_alloc::os::page_size_matches());
180    /// # Ok::<(), &str>(())
181    /// ```
182    pub returned: u64,
183    /// Mapped and never touched, therefore not resident: span bytes at
184    /// or above the bump cursor, and whole spans carved with their
185    /// segment that no class has ever claimed.
186    ///
187    /// # Examples
188    ///
189    /// ```
190    /// # use kevy_alloc::Heap;
191    /// let mut heap = Heap::new(0);
192    /// let p = heap.alloc(100, 8).ok_or("no mapping")?;
193    /// let s = heap.snapshot();
194    /// // most of a fresh segment has never been touched
195    /// assert!(s.virgin > s.mapped / 2);
196    /// // SAFETY: `p` came from this heap with this size and alignment.
197    /// unsafe { heap.dealloc(p, 100, 8) };
198    /// # Ok::<(), &str>(())
199    /// ```
200    pub virgin: u64,
201    /// Retained rather than released, and therefore still resident:
202    /// empty spans held for their class through the purge delay, spans
203    /// whose discard the platform refused, and large mappings parked in
204    /// the process-wide retention pool.
205    ///
206    /// Every byte here is one the allocator chose to keep. A byte that
207    /// went back to the OS belongs in [`Self::returned`] — the two are
208    /// opposites, and for the whole v5 arc they were the same number.
209    ///
210    /// # Examples
211    ///
212    /// ```
213    /// # use kevy_alloc::Heap;
214    /// let mut heap = Heap::new(0);
215    /// let held: Vec<_> = (0..16_384).map(|_| heap.alloc(64, 8)).collect::<Option<_>>().ok_or("no mapping")?;
216    /// for p in held {
217    ///     // SAFETY: each came from this heap with this size and alignment.
218    ///     unsafe { heap.dealloc(p, 64, 8) };
219    /// }
220    /// heap.reclaim();
221    /// // inside the purge delay the emptied spans stay with their class
222    /// assert!(heap.snapshot().hysteresis > 0);
223    /// # Ok::<(), &str>(())
224    /// ```
225    pub hysteresis: u64,
226    /// Segment headers.
227    ///
228    /// # Examples
229    ///
230    /// ```
231    /// # use kevy_alloc::Heap;
232    /// use kevy_alloc::class::SPAN_BYTES;
233    /// let mut heap = Heap::new(0);
234    /// let p = heap.alloc(100, 8).ok_or("no mapping")?;
235    /// // one span of the segment holds its header
236    /// assert_eq!(heap.snapshot().segment_overhead, SPAN_BYTES as u64);
237    /// // SAFETY: `p` came from this heap with this size and alignment.
238    /// unsafe { heap.dealloc(p, 100, 8) };
239    /// # Ok::<(), &str>(())
240    /// ```
241    pub segment_overhead: u64,
242    /// Live allocations served by direct mapping rather than a class.
243    ///
244    /// # Examples
245    ///
246    /// ```
247    /// # use kevy_alloc::Heap;
248    /// let mut heap = Heap::new(0);
249    /// let p = heap.alloc(1 << 20, 8).ok_or("no mapping")?;
250    /// // large blocks are counted process-wide, not per heap
251    /// assert_eq!(heap.snapshot().large_count, 0);
252    /// assert!(kevy_alloc::large_stats().large_count >= 1);
253    /// // SAFETY: `p` came from this heap with this size and alignment.
254    /// unsafe { heap.dealloc(p, 1 << 20, 8) };
255    /// # Ok::<(), &str>(())
256    /// ```
257    pub large_count: u64,
258    /// Spans currently assigned to a size class. Exported because "did
259    /// we keep claiming fresh spans past reusable ones" is not visible
260    /// in any byte count — the identity balances either way.
261    ///
262    /// # Examples
263    ///
264    /// ```
265    /// # use kevy_alloc::Heap;
266    /// let mut heap = Heap::new(0);
267    /// let a = heap.alloc(100, 8).ok_or("no mapping")?;
268    /// let b = heap.alloc(4000, 8).ok_or("no mapping")?;
269    /// // two classes in use, one span each
270    /// assert_eq!(heap.snapshot().spans_assigned, 2);
271    /// // SAFETY: both came from this heap with these sizes and alignment.
272    /// unsafe {
273    ///     heap.dealloc(a, 100, 8);
274    ///     heap.dealloc(b, 4000, 8);
275    /// }
276    /// # Ok::<(), &str>(())
277    /// ```
278    pub spans_assigned: u64,
279}
280
281impl Stats {
282    /// The sum the identity asserts. Kept separate from [`Self::mapped`]
283    /// so a test can compare the two rather than trusting one.
284    /// # Examples
285    ///
286    /// ```
287    /// use kevy_alloc::Stats;
288    /// // The identity this exists to check: every mapped byte is in
289    /// // exactly one bucket, so the sum is comparable to `mapped`
290    /// // rather than derived from it.
291    /// let s = Stats::default();
292    /// assert_eq!(s.accounted(), 0);
293    /// assert_eq!(s.mapped, 0);
294    /// ```
295    #[must_use]
296    pub fn accounted(&self) -> u64 {
297        self.live
298            + self.rounding
299            + self.cache
300            + self.span_free
301            + self.returned
302            + self.virgin
303            + self.hysteresis
304            + self.segment_overhead
305    }
306
307    /// Whether the identity holds exactly.
308    ///
309    /// # Examples
310    ///
311    /// ```
312    /// # use kevy_alloc::Heap;
313    /// let mut heap = Heap::new(0);
314    /// let p = heap.alloc(3000, 8).ok_or("no mapping")?;
315    /// assert!(heap.snapshot().balanced());
316    /// // SAFETY: `p` came from this heap with this size and alignment.
317    /// unsafe { heap.dealloc(p, 3000, 8) };
318    /// assert!(heap.snapshot().balanced());
319    /// # Ok::<(), &str>(())
320    /// ```
321    #[must_use]
322    pub fn balanced(&self) -> bool {
323        self.mapped == self.accounted()
324    }
325
326    /// Bytes we expect to be resident: everything mapped except what was
327    /// never touched or has been handed back to the OS.
328    ///
329    /// An estimate by construction — the kernel decides residency, not
330    /// us — so it is named as a prediction and compared against real RSS
331    /// by the gate rather than substituted for it.
332    ///
333    /// `hysteresis` is NOT subtracted, and used to be. That term is what
334    /// the policy is deliberately holding — empty spans kept for their
335    /// class, large mappings parked in the retention pool — and holding
336    /// is the opposite of handing back. Subtracting it made this
337    /// prediction fall by exactly the amount the retention pool grew,
338    /// which is the one direction it cannot be right in.
339    ///
340    /// # Examples
341    ///
342    /// ```
343    /// # use kevy_alloc::Heap;
344    /// let mut heap = Heap::new(0);
345    /// let p = heap.alloc(100, 8).ok_or("no mapping")?;
346    /// let s = heap.snapshot();
347    /// // untouched bytes are mapped but not expected to be resident
348    /// assert_eq!(s.predicted_resident(), s.mapped - s.virgin - s.returned);
349    /// assert!(s.predicted_resident() < s.mapped);
350    /// // SAFETY: `p` came from this heap with this size and alignment.
351    /// unsafe { heap.dealloc(p, 100, 8) };
352    /// # Ok::<(), &str>(())
353    /// ```
354    #[must_use]
355    pub fn predicted_resident(&self) -> u64 {
356        self.mapped - self.virgin - self.returned
357    }
358
359    /// Add another heap's snapshot. Shards report separately; a process
360    /// figure is their sum.
361    ///
362    /// # Examples
363    ///
364    /// ```
365    /// # use kevy_alloc::{Heap, Stats};
366    /// let (mut a, mut b) = (Heap::new(1), Heap::new(2));
367    /// let pa = a.alloc(100, 8).ok_or("no mapping")?;
368    /// let pb = b.alloc(200, 8).ok_or("no mapping")?;
369    /// let mut total = Stats::default();
370    /// total.merge(&a.snapshot());
371    /// total.merge(&b.snapshot());
372    /// assert_eq!(total.live, 300);
373    /// assert!(total.balanced());
374    /// // SAFETY: each came from its own heap with this size and alignment.
375    /// unsafe {
376    ///     a.dealloc(pa, 100, 8);
377    ///     b.dealloc(pb, 200, 8);
378    /// }
379    /// # Ok::<(), &str>(())
380    /// ```
381    pub fn merge(&mut self, other: &Stats) {
382        self.mapped += other.mapped;
383        self.live += other.live;
384        self.rounding += other.rounding;
385        self.cache += other.cache;
386        self.span_free += other.span_free;
387        self.returned += other.returned;
388        self.virgin += other.virgin;
389        self.hysteresis += other.hysteresis;
390        self.segment_overhead += other.segment_overhead;
391        self.large_count += other.large_count;
392        self.spans_assigned += other.spans_assigned;
393    }
394}
395
396#[cfg(test)]
397mod tests {
398    use super::*;
399
400    #[test]
401    fn an_empty_heap_balances() {
402        assert!(Stats::default().balanced());
403    }
404
405    #[test]
406    fn merge_is_additive_in_every_term() {
407        let a = Stats { mapped: 10, live: 4, virgin: 6, ..Stats::default() };
408        let mut sum = a;
409        sum.merge(&a);
410        assert_eq!(sum.mapped, 20);
411        assert_eq!(sum.live, 8);
412        assert_eq!(sum.virgin, 12);
413        assert!(sum.balanced());
414    }
415
416    #[test]
417    fn an_imbalance_is_visible() {
418        let bad = Stats { mapped: 100, live: 1, ..Stats::default() };
419        assert!(!bad.balanced());
420        assert_eq!(bad.accounted(), 1);
421    }
422}