use crate::class::{self, SPAN_BYTES};
use crate::os::PAGE;
pub const PAGES_PER_SPAN: usize = SPAN_BYTES / PAGE;
pub const ALL_PAGES_DISCARDED: u16 = ((1u32 << PAGES_PER_SPAN) - 1) as u16;
pub const BITMAP_WORDS: usize = SPAN_BYTES / 16 / 64;
pub const NO_CLASS: u8 = 0xFF;
#[derive(Debug, Clone, Copy)]
pub struct SpanMeta {
pub(crate) class: u8,
hint: u8,
pub(crate) live: u16,
pub(crate) high_water: u16,
pub(crate) discarded: u16,
pub(crate) returned_slots: u16,
pub(crate) retired: bool,
bitmap: [u64; BITMAP_WORDS],
}
impl SpanMeta {
#[must_use]
pub fn class(&self) -> u8 {
self.class
}
#[must_use]
pub fn live(&self) -> u16 {
self.live
}
#[must_use]
pub fn high_water(&self) -> u16 {
self.high_water
}
#[must_use]
pub fn discarded(&self) -> u16 {
self.discarded
}
#[must_use]
pub fn retired(&self) -> bool {
self.retired
}
pub(crate) const fn new() -> Self {
Self {
class: NO_CLASS,
hint: 0,
live: 0,
high_water: 0,
discarded: 0,
returned_slots: 0,
retired: false,
bitmap: [0; BITMAP_WORDS],
}
}
pub fn reset(&mut self, class: u8) {
debug_assert_eq!(self.live, 0, "resetting a span with live slots");
*self = Self { class, ..Self::new() };
}
#[must_use]
pub fn capacity(&self) -> u32 {
if self.class == NO_CLASS {
return 0;
}
class::slots_per_span(self.class as usize) as u32
}
pub fn alloc_slot(&mut self) -> Option<u32> {
let n = self.capacity();
let words = (n as usize).div_ceil(64);
for w in (self.hint as usize)..words {
let holes = !self.bitmap[w];
if holes == 0 {
continue;
}
let i = (w as u32) * 64 + holes.trailing_zeros();
if i >= n {
return None;
}
self.bitmap[w] |= 1u64 << (i % 64);
self.hint = w as u8;
self.live += 1;
if i as u16 >= self.high_water {
self.high_water = i as u16 + 1;
}
return Some(i);
}
None
}
pub fn claim_word(&mut self) -> Option<(u8, u64)> {
let n = self.capacity();
let words = (n as usize).div_ceil(64);
for w in (self.hint as usize)..words {
let valid = if (w + 1) * 64 <= n as usize {
!0u64
} else {
(1u64 << (n as usize - w * 64)) - 1
};
let holes = !self.bitmap[w] & valid;
if holes == 0 {
continue;
}
self.bitmap[w] |= holes;
self.live += holes.count_ones() as u16;
let hi = (w as u32) * 64 + (63 - holes.leading_zeros());
if hi as u16 >= self.high_water {
self.high_water = hi as u16 + 1;
}
self.hint = w as u8;
return Some((w as u8, holes));
}
None
}
pub fn retire_word(&mut self, w: u8, unused: u64) {
debug_assert_eq!(
self.bitmap[w as usize] & unused,
unused,
"retiring bits that were not claimed"
);
self.bitmap[w as usize] &= !unused;
self.live -= unused.count_ones() as u16;
if w < self.hint {
self.hint = w;
}
}
pub fn free_slot(&mut self, i: u32) {
let w = (i / 64) as usize;
let m = 1u64 << (i % 64);
debug_assert!(self.bitmap[w] & m != 0, "double free of slot {i}");
self.bitmap[w] &= !m;
self.live -= 1;
if (w as u8) < self.hint {
self.hint = w as u8;
}
}
#[must_use]
pub fn is_live(&self, i: u32) -> bool {
self.bitmap[(i / 64) as usize] & (1u64 << (i % 64)) != 0
}
#[must_use]
pub fn range_has_live(&self, first: u32, last: u32) -> bool {
let (fw, lw) = ((first / 64) as usize, (last / 64) as usize);
for w in fw..=lw {
let mut mask = !0u64;
if w == fw {
mask &= !0u64 << (first % 64);
}
if w == lw {
mask &= !0u64 >> (63 - (last % 64));
}
if self.bitmap[w] & mask != 0 {
return true;
}
}
false
}
}
#[must_use]
pub fn pages_of_slot(i: u32, slot_size: usize) -> (usize, usize) {
let start = i as usize * slot_size;
let end = start + slot_size - 1;
(start / PAGE, end / PAGE)
}
#[must_use]
pub fn slots_of_page(p: usize, slot_size: usize, nslots: u32) -> (u32, u32) {
let first = (p * PAGE / slot_size) as u32;
let last = (((p + 1) * PAGE - 1) / slot_size) as u32;
(first.min(nslots - 1), last.min(nslots - 1))
}
#[cfg(test)]
#[path = "pagemap_tests.rs"]
mod tests;