use core::ptr::NonNull;
use std::collections::HashMap;
use crate::class;
use crate::heap::Heap;
use crate::os::{self, PAGE};
use crate::pagemap::{NO_CLASS, PAGES_PER_SPAN, slots_of_page};
use crate::segment::{self, FIRST_DATA_SPAN, SPANS_PER_SEGMENT};
use super::PURGE_DELAY;
const SIZES: [usize; 8] = [16, 24, 100, 400, 912, 4_000, 20_000, 32_768];
struct Rng(u64);
impl Rng {
fn next(&mut self) -> u64 {
self.0 ^= self.0 << 13;
self.0 ^= self.0 >> 7;
self.0 ^= self.0 << 17;
self.0
}
}
fn agree(h: &Heap, what: &str) {
let (fast, walked) = (h.snapshot(), h.snapshot_walked());
assert_eq!(fast, walked, "after {what}");
assert!(fast.balanced(), "after {what}: {fast:?}");
}
fn tick(a: &mut Heap, b: &mut Heap) {
b.reclaim_with(true);
a.reclaim_with(true);
agree(a, "a's sweep");
agree(b, "b's sweep");
assert_eq!(a.snapshot().cache, 0, "a foreign free shipped home was not drained");
nothing_old_held(a);
nothing_old_held(b);
}
fn steady(delay: u32, ticks: usize) -> u64 {
let (mut a, mut b) = (Heap::new(1), Heap::new(2));
(a.purge_delay, b.purge_delay) = (delay, delay);
let mut rng = Rng(0x9E37_79B9_7F4A_7C15);
let base: Vec<_> = (0..3_000)
.map(|i| {
let size = SIZES[i % SIZES.len()];
(a.alloc(size, 8).expect("mapped"), size)
})
.collect();
let mut carried: Vec<(NonNull<u8>, usize)> = Vec::new();
let mut used: HashMap<usize, u32> = HashMap::new();
let mut warm = 0;
for t in 0..ticks {
let mut fresh: Vec<(NonNull<u8>, usize)> = Vec::new();
for &size in &SIZES {
for _ in 0..40 {
let p = a.alloc(size, 8).expect("mapped");
let start = p.as_ptr() as usize & !(PAGE - 1);
for page in (start..p.as_ptr() as usize + size).step_by(PAGE) {
used.insert(page, a.epoch);
}
fresh.push((p, size));
}
}
for (p, size) in carried.drain(..) {
unsafe { a.dealloc(p, size, 8) };
}
let (keep, mut gone): (Vec<_>, Vec<_>) =
fresh.into_iter().enumerate().partition(|(i, _)| i % 2 == 0);
carried = keep.into_iter().map(|(_, x)| x).collect();
for i in (1..gone.len()).rev() {
gone.swap(i, rng.next() as usize % (i + 1));
}
for (i, (_, (p, size))) in gone.into_iter().enumerate() {
unsafe { if i % 5 == 0 { b.dealloc(p, size, 8) } else { a.dealloc(p, size, 8) } }
}
tick(&mut a, &mut b);
nothing_young_returned(&a, &used);
if t == delay as usize + 2 {
warm = a.discards;
}
}
for (p, size) in carried.into_iter().chain(base) {
unsafe { a.dealloc(p, size, 8) };
}
a.discards - warm
}
#[test]
fn a_steady_working_set_returns_no_page_after_warm_up() {
if !os::available() {
return;
}
assert_eq!(steady(PURGE_DELAY, 40), 0);
}
#[test]
fn without_the_delay_the_same_traffic_returns_pages_every_tick() {
if !os::available() {
return;
}
assert!(steady(0, 40) >= 25, "the steady test cannot tell the delay from none");
}
fn nothing_young_returned(h: &Heap, used: &HashMap<usize, u32>) {
for (&page, &at) in used {
if h.epoch.wrapping_sub(at) > h.purge_delay {
continue;
}
let seg = unsafe { segment::segment_of(NonNull::new_unchecked(page as *mut u8)).as_ref() };
let ix = (page & (segment::SEGMENT_BYTES - 1)) / class::SPAN_BYTES;
let p = (page & (class::SPAN_BYTES - 1)) / PAGE;
let m = &seg.spans()[ix];
assert_ne!(m.class(), NO_CLASS, "span of a page used at {at} retired at {}", h.epoch);
assert_eq!(m.discarded() & (1 << p), 0, "page used at {at} returned at {}", h.epoch);
}
}
fn held_only(h: &Heap, may_hold: impl Fn(u32) -> bool) {
let mut seg = h.segments;
while !seg.is_null() {
let s = unsafe { &*seg };
for ix in FIRST_DATA_SPAN..SPANS_PER_SEGMENT {
let m = &s.spans[ix];
if m.class == NO_CLASS {
continue;
}
let slot = class::size_of(m.class as usize);
let touched = (usize::from(m.high_water) * slot).div_ceil(PAGE);
let age = |p: usize| h.epoch.wrapping_sub(s.stamps[ix].0[p]);
if m.live == 0 {
let youngest = (0..touched).map(age).min().unwrap_or(u32::MAX);
assert!(may_hold(youngest), "span {ix} held empty at age {youngest}");
continue;
}
for p in 0..PAGES_PER_SPAN {
let (lo, hi) = slots_of_page(p, slot, m.capacity());
let free = p < touched && !m.range_has_live(lo, hi) && m.discarded & (1 << p) == 0;
assert!(!free || may_hold(age(p)), "span {ix} page {p} held at age {}", age(p));
}
}
seg = s.next;
}
}
fn nothing_old_held(h: &Heap) {
held_only(h, |age| age <= h.purge_delay);
}
fn decay(seed: u64, delay: u32) {
let (mut a, mut b) = (Heap::new(1), Heap::new(2));
(a.purge_delay, b.purge_delay) = (delay, delay);
let mut rng = Rng(seed);
let mut held: Vec<(NonNull<u8>, usize)> = Vec::new();
let mut used: HashMap<usize, u32> = HashMap::new();
for _ in 0..30 {
for _ in 0..(rng.next() % 400) {
let r = rng.next();
if !r.is_multiple_of(3) || held.is_empty() {
let size = SIZES[(r >> 8) as usize % SIZES.len()] - (r >> 16) as usize % 8;
let p = a.alloc(size, 8).expect("mapped");
let start = p.as_ptr() as usize & !(PAGE - 1);
for page in (start..p.as_ptr() as usize + size).step_by(PAGE) {
used.insert(page, a.epoch);
}
held.push((p, size));
} else {
let (p, size) = held.swap_remove((r >> 8) as usize % held.len());
unsafe {
if r.is_multiple_of(7) { b.dealloc(p, size, 8) } else { a.dealloc(p, size, 8) }
}
}
}
tick(&mut a, &mut b);
nothing_young_returned(&a, &used);
}
let bound = a.epoch + delay.max(1);
for (i, (p, size)) in held.into_iter().enumerate() {
if i % 3 == 0 {
unsafe { a.dealloc(p, size, 8) };
}
}
while a.epoch < bound {
tick(&mut a, &mut b);
nothing_young_returned(&a, &used);
}
held_only(&a, |_| false);
}
#[test]
fn once_churn_stops_everything_free_goes_within_the_delay_and_nothing_sooner() {
if !os::available() {
return;
}
for seed in [0x9E37_79B9_7F4A_7C15, 0xD1B5_4A32_D192_ED03, 0x2545_F491_4F6C_DD1D, 7] {
for delay in [0, 1, 3, PURGE_DELAY] {
decay(seed, delay);
}
}
}
#[test]
fn a_settled_heap_leaves_the_sweep_nothing_to_visit() {
if !os::available() {
return;
}
let (mut a, mut b) = (Heap::new(1), Heap::new(2));
let held: Vec<_> = (0..8_000).map(|_| a.alloc(4_000, 8).expect("mapped")).collect();
for (i, p) in held.iter().enumerate() {
if i % 2 == 0 {
unsafe { if i % 4 == 0 { b.dealloc(*p, 4_000, 8) } else { a.dealloc(*p, 4_000, 8) } }
}
}
assert!(a.tally.segments > 4, "the heap should span several segments");
for _ in 0..=PURGE_DELAY + 1 {
tick(&mut a, &mut b);
}
assert!(a.wheel.iter().all(|&r| r == 0), "spans still scheduled after the delay");
let mut queued = 0;
unsafe { &*a.parked }.drain_pending(|_, _| queued += 1);
assert_eq!(queued, 0, "a segment stayed queued with nothing to drain");
}