use core::ptr::NonNull;
use core::sync::atomic::{AtomicPtr, AtomicUsize, Ordering};
use crate::os;
use crate::segment::SEGMENT_BYTES;
const SEG_SHIFT: u32 = SEGMENT_BYTES.trailing_zeros();
#[cfg(target_pointer_width = "64")]
const ADDR_BITS: u32 = 48;
#[cfg(not(target_pointer_width = "64"))]
const ADDR_BITS: u32 = usize::BITS;
const KEY_BITS: u32 = ADDR_BITS - SEG_SHIFT;
const ROOT_BITS: u32 = KEY_BITS / 2;
const LEAF_BITS: u32 = KEY_BITS - ROOT_BITS;
const LEAF_LEN: usize = 1 << LEAF_BITS;
const LEAF_BYTES: usize = LEAF_LEN * core::mem::size_of::<AtomicUsize>();
type Leaf = [AtomicUsize; LEAF_LEN];
static ROOT: [AtomicPtr<Leaf>; 1 << ROOT_BITS] =
[const { AtomicPtr::new(core::ptr::null_mut()) }; 1 << ROOT_BITS];
static NEXT_TOKEN: AtomicUsize = AtomicUsize::new(1);
pub(crate) fn new_token() -> usize {
NEXT_TOKEN.fetch_add(1, Ordering::Relaxed)
}
fn key(addr: usize) -> Option<(usize, usize)> {
if ADDR_BITS < usize::BITS && addr >> ADDR_BITS != 0 {
return None;
}
let k = addr >> SEG_SHIFT;
Some((k >> LEAF_BITS, k & (LEAF_LEN - 1)))
}
fn leaf(r: usize, create: bool) -> Option<&'static Leaf> {
let p = ROOT[r].load(Ordering::Acquire);
if !p.is_null() {
return Some(unsafe { &*p });
}
if !create {
return None;
}
let fresh = os::map_aligned(LEAF_BYTES.next_multiple_of(os::PAGE), os::PAGE)?;
let fresh = fresh.as_ptr().cast::<Leaf>();
match ROOT[r].compare_exchange(
core::ptr::null_mut(),
fresh,
Ordering::AcqRel,
Ordering::Acquire,
) {
Ok(_) => Some(unsafe { &*fresh }),
Err(won) => {
unsafe {
os::unmap(
NonNull::new_unchecked(fresh.cast()),
LEAF_BYTES.next_multiple_of(os::PAGE),
)
};
Some(unsafe { &*won })
}
}
}
pub(crate) fn set(base: usize, token: usize) -> bool {
let Some((r, i)) = key(base) else { return false };
let Some(l) = leaf(r, token != 0) else { return token == 0 };
l[i].store(token, Ordering::Release);
true
}
pub(crate) fn owner(addr: usize) -> usize {
let Some((r, i)) = key(addr) else { return 0 };
leaf(r, false).map_or(0, |l| l[i].load(Ordering::Acquire))
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn an_address_answers_its_segments_owner_and_nothing_else() {
let base = 7 * SEGMENT_BYTES;
let t = new_token();
assert!(set(base, t));
assert_eq!(owner(base + 12_345), t);
assert_eq!(owner(base + SEGMENT_BYTES), 0, "the next segment is nobody's");
assert_eq!(owner(usize::MAX), 0, "past the covered width");
assert!(set(base, 0));
assert_eq!(owner(base), 0);
}
#[test]
fn a_region_no_segment_ever_used_answers_nobody_and_clears_without_a_leaf() {
let r = (1 << ROOT_BITS) - 1;
let far = r << (SEG_SHIFT + LEAF_BITS);
assert_eq!(owner(far + 12_345), 0);
assert!(set(far, 0), "clearing an absent entry succeeds");
assert!(ROOT[r].load(Ordering::Acquire).is_null(), "a clear maps no leaf");
}
#[cfg(target_pointer_width = "64")]
#[test]
fn a_segment_past_the_covered_width_cannot_be_recorded() {
assert!(!set(1 << ADDR_BITS, new_token()));
}
}