1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
//! The free side of [`Heap`] (child module via `#[path]`, the house
//! pattern) — claims-first recycling, the small free's routing, the
//! local bitmap free, the foreign-free drain, and teardown. Split from
//! `heap.rs` for the 500-LOC ceiling; the seam is real: everything here
//! runs on release paths, nothing on allocation.
use core::ptr::NonNull;
use crate::class;
use crate::os;
use crate::segment::{self, NO_CLASS, SEGMENT_BYTES, Segment};
use super::Heap;
impl Heap {
/// The claims-first free: when the pointer lands in the class's
/// claimed word, recycle the bit without reading the segment header
/// at all. The match itself proves ownership — a claim's range is a
/// piece of one of this heap's own spans — so the owner check would
/// confirm what the compare already did. One unsigned compare
/// against the range replaces matching segment, span and word, and
/// because the range stops at the span's end the offset is one the
/// reciprocal divides exactly. 99.86 % of collection-write frees take
/// this path (branch-rate probe, hset storm), and the header read
/// was the fast path's single foreign cache line.
#[inline]
fn try_free_claimed(&mut self, ptr: NonNull<u8>, c: usize) -> bool {
let Some(cl) = &mut self.claims[c] else { return false };
let off = (ptr.as_ptr() as usize).wrapping_sub(cl.lo as usize);
if off >= cl.len {
return false;
}
let bit = 1u64 << class::slot_of_offset(off, c);
if cl.taken & bit == 0 {
return false;
}
cl.taken &= !bit;
true
}
/// # Safety
/// See [`Heap::dealloc`].
#[inline]
pub(crate) unsafe fn dealloc_small(&mut self, ptr: NonNull<u8>, c: usize, size: usize) {
if self.try_free_claimed(ptr, c) {
self.live_bytes -= size as u64;
return;
}
// SAFETY: a small allocation always lies inside a segment.
let seg = unsafe { segment::segment_of(ptr) };
// SAFETY: same contract, passed through.
unsafe { self.dealloc_unclaimed(seg, ptr, c, size) };
}
/// A small free that missed the claimed word: back to its span, or
/// out to its owner. Out of line so the claimed-word hit stays small.
///
/// # Safety
/// See [`Heap::dealloc`]; `seg` is `ptr`'s segment.
#[inline(never)]
unsafe fn dealloc_unclaimed(
&mut self,
seg: NonNull<Segment>,
ptr: NonNull<u8>,
c: usize,
size: usize,
) {
// SAFETY: the mask lands on a live header for our own pointers.
let seg_ref = unsafe { seg.as_ref() };
debug_assert!(seg_ref.is_valid(), "pointer did not come from kevy-alloc");
if seg_ref.owner == self.id {
self.live_bytes -= size as u64;
// SAFETY: our own segment; exclusive access.
unsafe { self.free_local(seg, ptr, c) };
} else {
// Not ours to decrement. The bytes were counted on the
// allocating thread's heap, and a non-atomic counter over
// there is exactly what this design refuses to reach across
// for — the owner settles when it drains.
//
// Nor ours to touch the owner's segment per-op: M1 measured
// that bill at 18–39 % of cross-shard KV. The free lands in
// the local outbound ring — two plain stores — and crosses
// cores only when a whole batch ships.
if !self.outbound.push(ptr, size, c) {
self.outbound.flush();
let ok = self.outbound.push(ptr, size, c);
debug_assert!(ok, "a freshly flushed ring cannot be full");
}
}
}
/// Move every slot other shards freed back onto its own span's list.
///
/// Visits only the segments a splice queued, so the cost follows the
/// foreign frees waiting rather than the size of the heap.
pub fn drain_foreign(&mut self) {
if self.parked.is_null() {
return;
}
// SAFETY: set with the first segment, whose header outlives
// every segment that could have held a foreign free.
let tally = unsafe { &*self.parked };
let (mut live, mut bytes) = (0usize, 0usize);
tally.drain_pending(|seg, mut node| {
let seg = seg.as_ptr();
while !node.is_null() {
// SAFETY: foreign entries are slot addresses of this
// segment, linked through their first word.
let next = unsafe { node.cast::<*mut u8>().read() };
// SAFETY: non-null in this branch.
let p = unsafe { NonNull::new_unchecked(node) };
// SAFETY: still queued and untouched, so the size the
// freeing thread recorded is still there.
let requested = unsafe { segment::foreign_requested(p) };
let ix = segment::span_index_of(p);
// SAFETY: the span index came from the address itself.
let cls = unsafe { (*seg).spans[ix].class };
if cls != NO_CLASS {
let c = cls as usize;
live += requested;
bytes += class::size_of(c);
self.live_bytes -= requested as u64;
// SAFETY: our segment, exclusive access here.
unsafe { self.free_local(NonNull::new_unchecked(seg), p, c) };
}
node = next;
}
});
if bytes != 0 {
tally.settle(live, bytes);
}
}
/// Mark a slot free in its span's bitmap. Nothing is written into
/// the slot itself — that absence is what makes its pages
/// returnable. The span moves to the list its new occupancy grades
/// it on, so the slow path finds it in O(1).
///
/// # Safety
/// `seg` must own `ptr`, and the caller must have exclusive access.
pub(crate) unsafe fn free_local(&mut self, seg: NonNull<Segment>, ptr: NonNull<u8>, c: usize) {
let ix = segment::span_index_of(ptr);
let slot = segment::slot_index_of(ptr, c);
// A free landing inside the class's claimed word recycles the
// bit heap-locally — no header touch at all. Collection writes
// are exactly this shape (several short-lived small allocations
// per op), which is where the far-line residual lived.
if let Some(cl) = &mut self.claims[c]
&& cl.seg == seg
&& usize::from(cl.span_ix) == ix
&& slot / 64 == u32::from(cl.word)
{
let bit = 1u64 << (slot % 64);
if cl.taken & bit != 0 {
cl.taken &= !bit;
return;
}
}
// SAFETY: caller holds exclusive access to this segment.
let meta = unsafe { &mut (*seg.as_ptr()).spans[ix] };
meta.free_slot(slot);
if meta.live == 0 {
self.tally.span_emptied(meta, c);
self.empty_in_class[c] += 1;
}
self.class_live[c] -= 1;
self.file_span(seg, ix);
self.note_free(seg, ix);
}
}
impl Drop for Heap {
fn drop(&mut self) {
// Claims hold no memory of their own — the segments they point
// into are unmapped below — but retiring them keeps the
// debug-assert bookkeeping (live counts) honest for any
// instrumented teardown that walks spans first.
self.flush_claims();
// The retention pool is process-wide and bounded, so a heap's
// death owes it nothing — but the fuzzer's tight RSS limit
// watches every iteration, and draining here keeps single-heap
// lifecycles (tests, fuzz) at zero retained bytes. Its per-heap
// ancestor forgot the equivalent and leaked a mapping per heap.
crate::large::pool_drain();
let mut seg = self.segments;
while !seg.is_null() {
// SAFETY: live header from our own list; read `next` before
// the mapping goes away.
let next = unsafe { (*seg).next };
crate::rtree::set(seg as usize, 0);
// SAFETY: this heap mapped it and is the only owner.
unsafe {
os::unmap(NonNull::new_unchecked(seg.cast::<u8>()), SEGMENT_BYTES);
}
seg = next;
}
}
}