use core::ptr::NonNull;
use crate::class;
use crate::os;
use crate::pagemap::PAGES_PER_SPAN;
use crate::segment::Segment;
use crate::spanlist::{link_of, pack, unpack};
use crate::heap::Heap;
pub const PURGE_DELAY: u32 = 10;
const _: () = assert!(PURGE_DELAY as usize + 2 <= WHEEL);
pub(crate) const WHEEL: usize = 16;
#[derive(Debug, Clone, Copy)]
pub(crate) struct WheelLink {
prev: usize,
next: usize,
due: u32,
queued: bool,
}
impl WheelLink {
pub(crate) const NONE: Self = Self { prev: 0, next: 0, due: 0, queued: false };
}
#[repr(C, align(64))]
#[derive(Debug, Clone, Copy)]
pub(crate) struct Stamps(pub(crate) [u32; PAGES_PER_SPAN]);
impl Stamps {
pub(crate) const NEW: Self = Self([0; PAGES_PER_SPAN]);
}
impl Heap {
#[inline]
pub(crate) fn note_free(&mut self, seg: NonNull<Segment>, ix: usize) {
let due = self.epoch.wrapping_add(1);
let r = pack(seg, ix);
let w = unsafe { link_of(r) }.wheel;
if w.queued && w.due == due {
return;
}
if w.queued {
self.wheel_unlink(r);
}
self.wheel_push(r, due);
}
pub(crate) fn stamp_claim(&self, seg: NonNull<Segment>, ix: usize, word: u8, claimed: u64) {
let slot = class::size_of(
unsafe { (*seg.as_ptr()).spans[ix].class } as usize,
);
let lo = u32::from(word) * 64 + claimed.trailing_zeros();
let hi = u32::from(word) * 64 + (63 - claimed.leading_zeros());
let (pa, _) = crate::pagemap::pages_of_slot(lo, slot);
let (_, pb) = crate::pagemap::pages_of_slot(hi, slot);
let stamps = unsafe { &mut (*seg.as_ptr()).stamps[ix].0 };
for s in &mut stamps[pa..=pb.min(PAGES_PER_SPAN - 1)] {
*s = self.epoch;
}
}
pub(crate) fn sweep_due(&mut self, can_discard: bool) {
let mut r = core::mem::take(&mut self.wheel[self.epoch as usize % WHEEL]);
while r != 0 {
let link = unsafe { link_of(r) };
let next = link.wheel.next;
debug_assert_eq!(link.wheel.due, self.epoch, "a span sat in the wrong bucket");
link.wheel = WheelLink::NONE;
let (seg, ix) = unpack(r);
if let Some(due) = self.purge_span(seg, ix, can_discard) {
self.wheel_push(r, due);
}
r = next;
}
}
fn purge_span(&mut self, seg: NonNull<Segment>, ix: usize, can_discard: bool) -> Option<u32> {
let s = unsafe { &mut *seg.as_ptr() };
let meta = &s.spans[ix];
if meta.live != 0 {
return self.discard_and_tally(s, ix, can_discard);
}
let slot = class::size_of(meta.class as usize);
let touched = (usize::from(meta.high_water) * slot).div_ceil(os::PAGE);
let ages = s.stamps[ix].0[..touched.min(PAGES_PER_SPAN)].iter();
let youngest = ages.map(|&t| self.epoch.wrapping_sub(t)).min();
match youngest {
Some(age) if age <= self.purge_delay => Some(self.due_after(age)),
_ => {
self.retire_empty_span(seg, s, ix, can_discard);
None
}
}
}
pub(crate) fn due_after(&self, age: u32) -> u32 {
self.epoch.wrapping_add(self.purge_delay + 1 - age)
}
fn wheel_push(&mut self, r: usize, due: u32) {
let b = due as usize % WHEEL;
let head = self.wheel[b];
if head != 0 {
unsafe { link_of(head) }.wheel.prev = r;
}
unsafe { link_of(r) }.wheel = WheelLink { prev: 0, next: head, due, queued: true };
self.wheel[b] = r;
}
fn wheel_unlink(&mut self, r: usize) {
let WheelLink { prev, next, due, .. } = unsafe { link_of(r) }.wheel;
if prev == 0 {
self.wheel[due as usize % WHEEL] = next;
} else {
unsafe { link_of(prev) }.wheel.next = next;
}
if next != 0 {
unsafe { link_of(next) }.wheel.prev = prev;
}
unsafe { link_of(r) }.wheel = WheelLink::NONE;
}
}
#[cfg(test)]
#[path = "purge_tests.rs"]
mod tests;