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}