use core::ptr::NonNull;
use crate::heap::Heap;
use crate::segment::{FIRST_DATA_SPAN, NO_CLASS, SEGMENT_BYTES, SPANS_PER_SEGMENT, Segment};
pub(crate) const BINS: usize = 4;
const FREE: u8 = u8::MAX;
#[derive(Debug, Clone, Copy)]
pub(crate) struct SpanLink {
prev: usize,
next: usize,
list: u8,
pub(crate) wheel: crate::purge::WheelLink,
}
impl SpanLink {
pub(crate) const NONE: Self =
Self { prev: 0, next: 0, list: 0, wheel: crate::purge::WheelLink::NONE };
}
#[inline]
pub(crate) fn pack(seg: NonNull<Segment>, ix: usize) -> usize {
seg.as_ptr() as usize | ix
}
#[inline]
pub(crate) fn unpack(r: usize) -> (NonNull<Segment>, usize) {
let base = (r & !(SEGMENT_BYTES - 1)) as *mut Segment;
(unsafe { NonNull::new_unchecked(base) }, r & (SEGMENT_BYTES - 1))
}
#[inline]
pub(crate) unsafe fn link_of<'a>(r: usize) -> &'a mut SpanLink {
let (seg, ix) = unpack(r);
unsafe { &mut (*seg.as_ptr()).links[ix] }
}
#[inline]
pub(crate) fn bin_of(live: u32, cap: u32) -> usize {
(live as usize * BINS / cap as usize).min(BINS - 1)
}
impl Heap {
fn head_mut(&mut self, list: u8, class: u8) -> &mut usize {
if list == FREE {
&mut self.free_spans
} else {
&mut self.bins[class as usize][list as usize - 1]
}
}
unsafe fn push_front(&mut self, r: usize, list: u8, class: u8) {
let head = *self.head_mut(list, class);
if head != 0 {
unsafe { link_of(head) }.prev = r;
}
let l = unsafe { link_of(r) };
(l.prev, l.next, l.list) = (0, head, list);
*self.head_mut(list, class) = r;
}
unsafe fn unlink(&mut self, r: usize, class: u8) {
let SpanLink { prev, next, list, .. } = *unsafe { link_of(r) };
if prev == 0 {
*self.head_mut(list, class) = next;
} else {
unsafe { link_of(prev) }.next = next;
}
if next != 0 {
unsafe { link_of(next) }.prev = prev;
}
let l = unsafe { link_of(r) };
(l.prev, l.next, l.list) = (0, 0, 0);
}
pub(crate) fn file_span(&mut self, seg: NonNull<Segment>, ix: usize) {
let r = pack(seg, ix);
let meta = unsafe { &(*seg.as_ptr()).spans[ix] };
let have = unsafe { link_of(r) }.list;
if have == FREE || meta.class == NO_CLASS {
return;
}
let (live, cap) = (u32::from(meta.live), meta.capacity());
let current = self.partial[meta.class as usize] == Some((seg, ix as u8));
let want = if current || live >= cap { 0 } else { bin_of(live, cap) as u8 + 1 };
if have == want {
return;
}
let class = meta.class;
unsafe {
if have != 0 {
self.unlink(r, class);
}
if want != 0 {
self.push_front(r, want, class);
}
}
}
pub(crate) fn take_densest(&mut self, c: usize) -> Option<(NonNull<Segment>, usize)> {
for b in (0..BINS).rev() {
let r = self.bins[c][b];
if r != 0 {
unsafe { self.unlink(r, c as u8) };
return Some(unpack(r));
}
}
None
}
pub(crate) fn pop_free_span(&mut self) -> Option<(NonNull<Segment>, usize)> {
let r = self.free_spans;
if r == 0 {
return None;
}
unsafe { self.unlink(r, NO_CLASS) };
Some(unpack(r))
}
pub(crate) fn push_free_span(&mut self, seg: NonNull<Segment>, ix: usize) {
unsafe { self.push_front(pack(seg, ix), FREE, NO_CLASS) };
}
pub(crate) fn file_new_segment(&mut self, seg: NonNull<Segment>) {
for ix in (FIRST_DATA_SPAN..SPANS_PER_SEGMENT).rev() {
self.push_free_span(seg, ix);
}
}
pub(crate) fn delist_span(&mut self, seg: NonNull<Segment>, ix: usize) {
let r = pack(seg, ix);
let link = *unsafe { link_of(r) };
if link.list != 0 {
let class = unsafe { (*seg.as_ptr()).spans[ix].class };
unsafe { self.unlink(r, class) };
}
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::class::NCLASSES;
fn check(h: &Heap) {
let mut listed = std::collections::HashMap::new();
let mut walk = |head: usize, list: u8, class: Option<usize>| {
let (mut r, mut prev) = (head, 0usize);
while r != 0 {
let l = *unsafe { link_of(r) };
assert_eq!(l.prev, prev, "back link");
assert_eq!(l.list, list, "list id");
if let Some(c) = class {
let (seg, ix) = unpack(r);
assert_eq!(usize::from(unsafe { (*seg.as_ptr()).spans[ix].class }), c);
}
assert!(listed.insert(r, list).is_none(), "a span on two lists");
(prev, r) = (r, l.next);
}
};
for c in 0..NCLASSES {
for b in 0..BINS {
walk(h.bins[c][b], b as u8 + 1, Some(c));
}
}
walk(h.free_spans, FREE, None);
let mut seg = h.segments;
while !seg.is_null() {
let s = unsafe { &*seg };
for ix in FIRST_DATA_SPAN..SPANS_PER_SEGMENT {
let r = pack(unsafe { NonNull::new_unchecked(seg) }, ix);
let m = &s.spans[ix];
let want = if m.class == NO_CLASS {
FREE
} else if h.partial[m.class as usize].is_some_and(|(p, i)| pack(p, i.into()) == r)
|| u32::from(m.live) >= m.capacity()
{
0
} else {
bin_of(m.live.into(), m.capacity()) as u8 + 1
};
assert_eq!(listed.get(&r).copied().unwrap_or(0), want, "span {ix}: {m:?}");
}
seg = s.next;
}
}
#[test]
fn churn_across_classes_and_heaps_keeps_every_span_on_its_list() {
let (mut a, mut b) = (Heap::new(1), Heap::new(2));
let sizes = [24usize, 400, 912, 4_000, 20_000];
let mut held: Vec<(core::ptr::NonNull<u8>, usize)> = Vec::new();
let mut x = 0x9E37_79B9_7F4A_7C15u64;
let mut next = || {
x ^= x << 13;
x ^= x >> 7;
x ^= x << 17;
x
};
for step in 0..20_000 {
let r = next();
match r % 10 {
0..=4 => {
let size = sizes[(r >> 8) as usize % sizes.len()];
held.push((a.alloc(size, 8).expect("mapped"), size));
}
5..=7 if !held.is_empty() => {
let (p, size) = held.swap_remove((r >> 8) as usize % held.len());
unsafe { a.dealloc(p, size, 8) };
}
8 if !held.is_empty() => {
let (p, size) = held.swap_remove((r >> 8) as usize % held.len());
unsafe { b.dealloc(p, size, 8) };
}
_ => match (r >> 8) % 3 {
0 => a.drain_foreign(),
1 => b.reclaim(),
_ => a.reclaim(),
},
}
if step % 7 == 0 {
check(&a);
}
}
for (p, size) in held.drain(..) {
unsafe { a.dealloc(p, size, 8) };
}
b.reclaim();
a.reclaim();
check(&a);
assert_eq!(a.snapshot().live, 0);
}
#[test]
fn the_grades_split_occupancy_in_quarters() {
assert_eq!(bin_of(0, 100), 0);
assert_eq!(bin_of(24, 100), 0);
assert_eq!(bin_of(25, 100), 1);
assert_eq!(bin_of(74, 100), 2);
assert_eq!(bin_of(99, 100), 3);
assert_eq!(bin_of(1, 2), 2);
}
}