pub(crate) const PAGE_SHIFT: u32 = 12;
pub(crate) const PAGE_COUNT: usize = 1 << (32 - PAGE_SHIFT);
const INDEX_WORDS: usize = PAGE_COUNT / 64;
#[derive(Debug, Default, Clone)]
pub(crate) struct PageIndex {
words: Option<Box<[u64]>>,
}
impl PageIndex {
#[inline]
pub(crate) fn unmarked_span(&self, address: u32) -> Option<std::ops::Range<u64>> {
let page = (address >> PAGE_SHIFT) as usize;
let index = page / 64;
let word = self.words.as_deref().map_or(0, |words| words[index]);
let bit = 1u64 << (page % 64);
if word & bit != 0 {
return None;
}
let below = word & (bit - 1);
let above = word & !(bit - 1);
let first = index * 64 + (64 - below.leading_zeros() as usize);
let end = index * 64 + above.trailing_zeros() as usize;
Some((first as u64) << PAGE_SHIFT..(end as u64) << PAGE_SHIFT)
}
pub(crate) fn mark(&mut self, start: u64, end: u64) {
if end <= start {
return;
}
let words = self
.words
.get_or_insert_with(|| vec![0u64; INDEX_WORDS].into_boxed_slice());
let first = (start >> PAGE_SHIFT) as usize;
let last = ((end - 1) >> PAGE_SHIFT) as usize;
let last = last.min(PAGE_COUNT - 1);
for page in first..=last {
words[page / 64] |= 1u64 << (page % 64);
}
}
#[inline]
pub(crate) fn may_overlap(&self, start: u64, end: u64) -> bool {
let Some(words) = self.words.as_deref() else {
return false;
};
if end <= start {
return false;
}
let first = (start >> PAGE_SHIFT) as usize;
let last = (((end - 1) >> PAGE_SHIFT) as usize).min(PAGE_COUNT - 1);
let (first_word, last_word) = (first / 64, last / 64);
let head_mask = u64::MAX << (first % 64);
let tail_mask = u64::MAX >> (63 - last % 64);
if first_word == last_word {
return words[first_word] & head_mask & tail_mask != 0;
}
words[first_word] & head_mask != 0
|| words[last_word] & tail_mask != 0
|| words[first_word + 1..last_word].iter().any(|word| *word != 0)
}
}
#[cfg(test)]
mod tests {
use super::{PageIndex, PAGE_SHIFT};
const PAGE: u64 = 1 << PAGE_SHIFT;
#[test]
fn unmarked_spans_stop_at_marked_pages_and_bitmap_word_edges() {
let mut index = PageIndex::default();
for page in [3, 63, 64, 127] {
index.mark(page * PAGE, page * PAGE + 1);
}
for (page, first, end) in [(0, 0, 3), (2, 0, 3), (4, 4, 63), (62, 4, 63), (65, 65, 127)] {
let span = index.unmarked_span((page * PAGE) as u32).unwrap();
assert_eq!(span, first * PAGE..end * PAGE);
assert!(!index.may_overlap(span.start, span.end));
}
for page in [3, 63, 64, 127] {
assert_eq!(index.unmarked_span((page * PAGE) as u32), None);
}
assert_eq!(
index.unmarked_span(128 * PAGE as u32),
Some(128 * PAGE..192 * PAGE)
);
}
#[test]
fn empty_span_proofs_cover_arbitrary_bit_patterns_and_address_space_edges() {
for pattern in [
0,
u64::MAX,
1,
1 << 63,
0xaaaa_aaaa_aaaa_aaaa,
0x0100_0000_0000_0080,
] {
let mut index = PageIndex::default();
for page in 0..64 {
if pattern & (1 << page) != 0 {
index.mark(page * PAGE, page * PAGE + 1);
}
}
for page in 0..64 {
match index.unmarked_span((page * PAGE) as u32) {
Some(span) => {
assert_eq!(pattern & (1 << page), 0);
assert!(span.start <= page * PAGE && (page + 1) * PAGE <= span.end);
assert!(span.end <= 64 * PAGE);
assert!(!index.may_overlap(span.start, span.end));
}
None => assert_ne!(pattern & (1 << page), 0),
}
}
}
let index = PageIndex::default();
assert_eq!(index.unmarked_span(0), Some(0..64 * PAGE));
assert_eq!(
index.unmarked_span(u32::MAX),
Some((1u64 << 32) - 64 * PAGE..1u64 << 32)
);
assert!(index.words.is_none());
}
#[test]
fn empty_index_rejects_every_range() {
let index = PageIndex::default();
assert!(!index.may_overlap(0, 1));
assert!(!index.may_overlap(0, 1 << 32));
}
#[test]
fn page_index_reports_marked_pages_only() {
let mut index = PageIndex::default();
index.mark(8 * PAGE, 8 * PAGE + 16);
assert!(index.may_overlap(8 * PAGE, 8 * PAGE + 1));
assert!(index.may_overlap(8 * PAGE + 4000, 8 * PAGE + 4004));
assert!(!index.may_overlap(7 * PAGE, 8 * PAGE));
assert!(!index.may_overlap(9 * PAGE, 9 * PAGE + 4));
assert!(index.may_overlap(7 * PAGE, 8 * PAGE + 1));
assert!(index.may_overlap(8 * PAGE + 4095, 9 * PAGE + 1));
}
#[test]
fn page_index_spans_word_boundaries() {
let mut index = PageIndex::default();
index.mark(200 * PAGE, 201 * PAGE);
assert!(index.may_overlap(200 * PAGE, 200 * PAGE + 4));
assert!(index.may_overlap(0, 1 << 32));
assert!(index.may_overlap(199 * PAGE, 400 * PAGE));
assert!(index.may_overlap(64 * PAGE, 201 * PAGE));
assert!(index.may_overlap(200 * PAGE, 4096 * PAGE));
assert!(!index.may_overlap(201 * PAGE, 400 * PAGE));
assert!(!index.may_overlap(0, 200 * PAGE));
}
#[test]
fn page_index_clamps_the_top_of_the_address_space() {
let mut index = PageIndex::default();
index.mark((1 << 32) - PAGE, (1 << 32) + 4096);
assert!(index.may_overlap((1 << 32) - 4, 1 << 32));
assert!(!index.may_overlap(0, (1 << 32) - PAGE));
}
#[test]
fn an_empty_range_allocates_no_bitmap() {
let mut index = PageIndex::default();
index.mark(16 * PAGE, 16 * PAGE);
assert!(index.words.is_none());
}
}