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
//! The reclaim sweep — where pages actually go back.
//!
//! Split from `heap.rs` for the file-size rule at the seam that makes
//! sense: everything here runs on the shard tick, nothing on the
//! allocation fast path. `reclaim` walks the segments; whole spans with
//! nothing live are unassigned and discarded (v1 behaviour, with the
//! per-sweep hysteresis), and spans that still hold live slots get the
//! v2 treatment: every page no live slot overlaps is handed back
//! individually, which is the structure M3 forced (RFC §5.1).
use core::ptr::NonNull;
use crate::class;
use crate::class::SPAN_BYTES;
use crate::heap::{EMPTY_SPAN_HYSTERESIS, Heap};
use crate::os;
use crate::segment::{FIRST_DATA_SPAN, NO_CLASS, SPANS_PER_SEGMENT, Segment};
impl Heap {
/// Return free pages to the OS — whole spans where nothing is live,
/// and *individual pages* inside spans that still are. The second
/// half is v2 (RFC §5.1): M3 measured the whole-span rule returning
/// 3 % because a span only empties when all its slots die together,
/// while glibc works at page granularity. Now so do we.
///
/// Drains foreign frees first: slots parked by other shards pin
/// their pages exactly as live slots do, so sweeping before
/// draining under-returns for no reason.
///
/// The retained count is per sweep rather than cumulative. A running
/// counter looked equivalent and was not: it only ever grew, so the
/// second sweep found it already past the threshold and returned
/// everything, which made the hysteresis vanish after one call.
pub fn reclaim(&mut self) {
self.reclaim_with(os::page_size_matches());
}
/// [`Self::reclaim`] with the platform's answer supplied.
///
/// Only one value of `can_discard` is possible on any given machine,
/// so the other side of every branch below is unreachable where it
/// runs — and the unreachable one is the interesting one: it is the
/// case in which page-granular reclaim does nothing at all, which is
/// every Apple Silicon Mac. Taking it as an argument is what lets a
/// test drive both, and it is asked once per sweep rather than once
/// per span.
pub(crate) fn reclaim_with(&mut self, can_discard: bool) {
// Claimed-word bits pin their pages exactly as live slots do;
// write them back first so the sweep sees true occupancy.
self.flush_claims();
// Retained large mappings go back each tick: retention beyond a
// tick requires sustained traffic to re-earn, and idle memory
// stays bounded by the tick length rather than the pool size.
crate::large::pool_drain();
// Ship pending foreign frees home before sweeping: they pin
// pages on OTHER heaps' segments, and the tick is the latency
// bound on how long a batch may sit.
if !self.outbound.is_empty() {
self.outbound.flush();
}
self.drain_foreign();
let mut kept: u16 = 0;
let mut seg = self.segments;
while !seg.is_null() {
// SAFETY: live header from our own list.
let s = unsafe { &mut *seg };
for ix in FIRST_DATA_SPAN..SPANS_PER_SEGMENT {
if s.spans[ix].class == NO_CLASS {
continue;
}
if s.spans[ix].live != 0 {
Self::discard_free_pages(s, ix, can_discard);
continue;
}
if kept < EMPTY_SPAN_HYSTERESIS {
kept += 1;
continue;
}
// SAFETY: `seg` is the segment being walked in this loop; it came
// from the live span list, so it is a real segment address and
// never null.
self.retire_empty_span(unsafe { NonNull::new_unchecked(seg) }, s, ix, can_discard);
}
seg = s.next;
}
}
/// Unhook an empty span from its class and hand its pages back.
///
/// Three steps that have to happen together and in this order: drop
/// the class's cached pointer to it (a `partial` entry naming a span
/// that has been reset would hand out slots from a span with no
/// class), decrement the class's span count, and only then reset the
/// metadata.
fn retire_empty_span(
&mut self,
seg: NonNull<Segment>,
s: &mut Segment,
ix: usize,
can_discard: bool,
) {
let c = s.spans[ix].class as usize;
if self.partial[c] == Some((seg, ix as u8)) {
self.partial[c] = None;
}
self.spans_in_class[c] -= 1;
s.spans[ix].reset(crate::pagemap::NO_CLASS);
// Emptied and handed back, which is not the same unassigned as
// never-assigned: this span's pages were touched. The snapshot
// needs the difference to tell `returned` from `virgin`.
s.spans[ix].retired = true;
// Refused on a system whose page size is not `os::PAGE`: see
// `discard_free_pages` for why reporting a return that did not
// happen is worse than not returning. The span then stays
// resident and is accounted as `hysteresis`, which is what it
// is — held, not released.
if can_discard {
let base = s.span_base(ix);
// SAFETY: nothing is live in this span, and the range is
// page-aligned and inside a live mapping.
unsafe {
os::discard(NonNull::new_unchecked(base), SPAN_BYTES);
}
s.spans[ix].discarded = crate::pagemap::ALL_PAGES_DISCARDED;
}
}
/// Hand back every page of a *live* span that no live slot overlaps.
///
/// The page rule, exactly: below the high-water byte (never-touched
/// pages are already non-resident — discarding them is a wasted
/// syscall), not already discarded, and no live slot overlapping.
/// Contiguous runs go to the OS in one call.
fn discard_free_pages(s: &mut Segment, ix: usize, can_discard: bool) {
use crate::pagemap::{PAGES_PER_SPAN, slots_of_page};
// The page rule is arithmetic at `os::PAGE`, and on a system
// whose pages are larger those ranges are not page-aligned.
// macOS answers 0 to such a `madvise` and reclaims nothing, so
// running on would set `discarded`, count the pages in
// `returned`, and lower `predicted_resident()` for memory the
// kernel still holds — the accounting would read as a success.
// Refusing keeps the seven-term identity true about the world.
if !can_discard {
return;
}
let meta = &mut s.spans[ix];
let slot = class::size_of(meta.class as usize);
let cap = meta.capacity();
let hw_bytes = meta.high_water as usize * slot;
let base = s.span_base(ix);
let mut run: Option<usize> = None;
for p in 0..PAGES_PER_SPAN {
let meta = &mut s.spans[ix];
let fresh = meta.discarded & (1u16 << p) == 0 && p * os::PAGE < hw_bytes && {
let (a, b) = slots_of_page(p, slot, cap);
!meta.range_has_live(a, b)
};
if fresh {
meta.discarded |= 1u16 << p;
run.get_or_insert(p);
} else if let Some(r0) = run.take() {
// SAFETY: pages r0..p hold no live slot and no metadata
// (the bitmap lives in the header — the whole point).
unsafe {
os::discard(
NonNull::new_unchecked(base.wrapping_add(r0 * os::PAGE)),
(p - r0) * os::PAGE,
);
}
}
}
if let Some(r0) = run {
// SAFETY: as above, through the end of the span.
unsafe {
os::discard(
NonNull::new_unchecked(base.wrapping_add(r0 * os::PAGE)),
(PAGES_PER_SPAN - r0) * os::PAGE,
);
}
}
}
}