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
//! Whether an allocation is worth moving (child module via `#[path]`,
//! the house pattern).
//!
//! A heap cannot move what it hands out — only the owner of a pointer can
//! — but it can say which pointers a move would help, and it decides where
//! the copy lands. The rule is jemalloc's defrag hint: a slot is worth
//! moving when its span holds fewer live slots than its class does on
//! average, and the class has at least a span's worth of holes to take
//! it. Allocation fills the fullest span first, so the copy lands in a
//! denser span than the one it left, and a span drained this way goes back
//! whole at the next reclaim. Under uniform occupancy half the spans sit
//! below average, which is what lets a heap of evenly scattered holes
//! converge rather than stay as it is.
use core::ptr::NonNull;
use crate::class;
use crate::segment;
use super::Heap;
impl Heap {
/// Whether the allocation at `ptr`, made with `size` and `align`,
/// would leave a sparser span than the one a fresh allocation of the
/// same shape would land in.
///
/// `false` for anything that is not a small slot of this heap: a
/// direct mapping has nowhere denser to go, and another heap's slot is
/// that heap's to move. Any address may be asked about: the owner tree
/// is consulted before any header is read, and `ptr` itself never is.
///
/// # Examples
///
/// ```
/// # use kevy_alloc::Heap;
/// let mut heap = Heap::new(7);
/// let held: Vec<_> = (0..4_000).map(|_| heap.alloc(900, 8)).collect::<Option<_>>().ok_or("no mapping")?;
/// // free most of the first spans' slots: those spans fall below average
/// for p in &held[..1_000] {
/// // SAFETY: each came from this heap with this size and alignment.
/// unsafe { heap.dealloc(*p, 900, 8) };
/// }
/// assert!(heap.should_move(held[1_010].as_ptr(), 900, 8), "a sparse span's survivor moves");
/// assert!(!heap.should_move(held[3_999].as_ptr(), 900, 8), "the span being filled stays");
/// assert!(!heap.should_move(&0u8, 1, 1), "not this heap's");
/// for p in &held[1_000..] {
/// // SAFETY: as above.
/// unsafe { heap.dealloc(*p, 900, 8) };
/// }
/// # Ok::<(), &str>(())
/// ```
#[must_use]
pub fn should_move(&self, ptr: *const u8, size: usize, align: usize) -> bool {
let Some(c) = class::index_of(size, align) else { return false };
if self.token == 0 || crate::rtree::owner(ptr as usize) != self.token {
return false;
}
// SAFETY: the owner tree says a segment of this heap is mapped at
// this address's segment base, so its header is live and ours.
let seg = unsafe { segment::segment_of(NonNull::new_unchecked(ptr.cast_mut())) };
// SAFETY: as above.
let s = unsafe { seg.as_ref() };
// SAFETY: as above; the index is derived from the address alone.
let ix = segment::span_index_of(unsafe { NonNull::new_unchecked(ptr.cast_mut()) });
let meta = &s.spans[ix];
if ix < segment::FIRST_DATA_SPAN
|| usize::from(meta.class) != c
|| self.partial[c] == Some((seg, ix as u8))
{
return false;
}
// empty spans held through the purge delay are room for the copy,
// but not part of the average a span is judged against: counting
// them would make every span look dense while the delay runs
let spans = u64::from(self.spans_in_class[c]);
let occupied = spans - u64::from(self.empty_in_class[c]);
let (cap, class_live) = (u64::from(meta.capacity()), u64::from(self.class_live[c]));
spans * cap >= class_live + cap && u64::from(meta.live) * occupied < class_live
}
}
#[cfg(test)]
mod tests {
use super::*;
fn xorshift(x: &mut u64) -> u64 {
*x ^= *x << 13;
*x ^= *x >> 7;
*x ^= *x << 17;
*x
}
#[test]
fn moving_what_the_hint_names_packs_the_class_into_the_fewest_spans() {
let mut heap = Heap::new(3);
let (size, n) = (900usize, 6_000usize);
let mut held: Vec<NonNull<u8>> = (0..n).map(|_| heap.alloc(size, 8).unwrap()).collect();
let mut x = 0x2545_F491_4F6C_DD1Du64;
// scatter the holes: every span loses about 30% of its slots
held.retain(|p| {
let drop = xorshift(&mut x) % 10 < 3;
// SAFETY: from this heap with this shape
drop.then(|| unsafe { heap.dealloc(*p, size, 8) }).is_none()
});
let c = class::index_of(size, 8).unwrap();
let per_span = class::slots_per_span(c);
let spans_before = heap.spans_in_class[c];
// a reclaim between rounds, as the shard tick runs one; emptied
// spans no longer count toward the class's average, which raises
// it and names the next sparsest spans
for _ in 0..8 {
heap.reclaim();
for p in &mut held {
if heap.should_move(p.as_ptr(), size, 8) {
let q = heap.alloc(size, 8).unwrap();
// SAFETY: both live and of `size` bytes, distinct slots
unsafe { core::ptr::copy_nonoverlapping(p.as_ptr(), q.as_ptr(), size) };
// SAFETY: from this heap with this shape; replaced by `q`
unsafe { heap.dealloc(*p, size, 8) };
*p = q;
}
}
}
// the spans the moves emptied go back once the purge delay ends
for _ in 0..=crate::PURGE_DELAY {
heap.reclaim();
}
let need = held.len().div_ceil(per_span) as u32;
let after = heap.spans_in_class[c];
assert!(after <= need + 1, "{spans_before} spans before, {after} after, {need} needed");
assert!(heap.snapshot().balanced());
for p in held {
// SAFETY: as above
unsafe { heap.dealloc(p, size, 8) };
}
}
#[test]
fn a_direct_mapping_is_never_named_for_a_move() {
let mut heap = Heap::new(6);
let size = class::MAX_SMALL + 1;
let p = heap.alloc(size, 8).unwrap();
assert!(!heap.should_move(p.as_ptr(), size, 8));
// SAFETY: from this heap with this shape
unsafe { heap.dealloc(p, size, 8) };
}
#[test]
fn another_heaps_slot_and_a_class_without_a_spare_span_stay() {
let (mut a, b) = (Heap::new(4), Heap::new(5));
let held: Vec<NonNull<u8>> = (0..500).map(|_| a.alloc(900, 8).unwrap()).collect();
assert!(!b.should_move(held[0].as_ptr(), 900, 8), "`b` does not own it");
// SAFETY: from `a` with this shape
unsafe { a.dealloc(held[3], 900, 8) };
// one hole in the whole class: nowhere denser to go
assert!(!a.should_move(held[4].as_ptr(), 900, 8));
for (i, p) in held.into_iter().enumerate() {
if i != 3 {
// SAFETY: from `a` with this shape
unsafe { a.dealloc(p, 900, 8) };
}
}
}
}