#![deny(unsafe_op_in_unsafe_fn, clippy::undocumented_unsafe_blocks)]
use crate::sync::atomic::{AtomicPtr, AtomicU32, Ordering};
pub(crate) trait Slot: Copy + Eq + std::fmt::Debug {
const NULL: Self;
fn is_null(self) -> bool;
fn is_leaf(self) -> bool;
}
pub(crate) trait AtomicSlot: Send + Sync {
type Raw: Slot;
fn new(v: Self::Raw) -> Self;
fn load(&self, order: Ordering) -> Self::Raw;
fn store(&self, v: Self::Raw, order: Ordering);
fn swap(&self, v: Self::Raw, order: Ordering) -> Self::Raw;
}
#[cfg(not(loom))]
pub(crate) trait ConstNull {
const NULL: Self;
}
#[cfg(not(loom))]
impl ConstNull for AtomicPtr<u8> {
const NULL: Self = AtomicPtr::new(std::ptr::null_mut());
}
#[cfg(not(loom))]
impl ConstNull for AtomicU32 {
const NULL: Self = AtomicU32::new(0);
}
pub(crate) const TAG_LEAF: usize = 0b01;
#[derive(Copy, Clone, PartialEq, Eq, Debug)]
#[repr(transparent)]
pub(crate) struct TaggedPtr {
ptr: *mut u8,
}
impl TaggedPtr {
#[inline(always)]
pub(crate) fn from_leaf<T>(ptr: *mut T) -> Self {
debug_assert_eq!(ptr.addr() & TAG_LEAF, 0, "leaf pointer must be aligned");
Self {
ptr: ptr.cast::<u8>().map_addr(|a| a | TAG_LEAF),
}
}
#[inline(always)]
pub(crate) fn from_inner<T>(ptr: *mut T) -> Self {
debug_assert_eq!(ptr.addr() & TAG_LEAF, 0, "node pointer must be aligned");
Self {
ptr: ptr.cast::<u8>(),
}
}
#[inline(always)]
pub(crate) fn as_leaf_ptr<T>(self) -> *mut T {
debug_assert!(self.is_leaf());
self.ptr.map_addr(|a| a & !TAG_LEAF).cast::<T>()
}
#[inline(always)]
pub(crate) fn as_inner_ptr<T>(self) -> *mut T {
debug_assert!(!self.is_leaf());
self.ptr.cast::<T>()
}
#[inline(always)]
pub(crate) fn as_raw(self) -> *mut u8 {
self.ptr
}
#[inline(always)]
pub(crate) fn from_raw(ptr: *mut u8) -> Self {
Self { ptr }
}
}
impl Slot for TaggedPtr {
const NULL: Self = Self {
ptr: std::ptr::null_mut(),
};
#[inline(always)]
fn is_null(self) -> bool {
self.ptr.is_null()
}
#[inline(always)]
fn is_leaf(self) -> bool {
self.ptr.addr() & TAG_LEAF != 0
}
}
impl AtomicSlot for AtomicPtr<u8> {
type Raw = TaggedPtr;
#[inline(always)]
fn new(v: TaggedPtr) -> Self {
AtomicPtr::new(v.as_raw())
}
#[inline(always)]
fn load(&self, order: Ordering) -> TaggedPtr {
TaggedPtr::from_raw(AtomicPtr::load(self, order))
}
#[inline(always)]
fn store(&self, v: TaggedPtr, order: Ordering) {
AtomicPtr::store(self, v.as_raw(), order)
}
#[inline(always)]
fn swap(&self, v: TaggedPtr, order: Ordering) -> TaggedPtr {
TaggedPtr::from_raw(AtomicPtr::swap(self, v.as_raw(), order))
}
}
unsafe impl Send for TaggedPtr {}
unsafe impl Sync for TaggedPtr {}
pub(crate) const TAG_LEAF_OFFSET: u32 = 0b01;
#[derive(Copy, Clone, PartialEq, Eq, Debug)]
#[repr(transparent)]
pub(crate) struct TaggedOffset(pub(crate) u32);
impl TaggedOffset {
#[inline(always)]
pub(crate) fn from_leaf(offset: u32) -> Self {
debug_assert_eq!(offset & TAG_LEAF_OFFSET, 0, "offset must be aligned");
debug_assert_ne!(offset, 0);
Self(offset | TAG_LEAF_OFFSET)
}
#[inline(always)]
pub(crate) fn from_inner(offset: u32) -> Self {
debug_assert_eq!(offset & TAG_LEAF_OFFSET, 0, "offset must be aligned");
debug_assert_ne!(offset, 0);
Self(offset)
}
#[inline(always)]
pub(crate) fn offset(self) -> u32 {
self.0 & !TAG_LEAF_OFFSET
}
}
impl Slot for TaggedOffset {
const NULL: Self = Self(0);
#[inline(always)]
fn is_null(self) -> bool {
self.0 == 0
}
#[inline(always)]
fn is_leaf(self) -> bool {
self.0 & TAG_LEAF_OFFSET != 0
}
}
impl AtomicSlot for AtomicU32 {
type Raw = TaggedOffset;
#[inline(always)]
fn new(v: TaggedOffset) -> Self {
AtomicU32::new(v.0)
}
#[inline(always)]
fn load(&self, order: Ordering) -> TaggedOffset {
TaggedOffset(AtomicU32::load(self, order))
}
#[inline(always)]
fn store(&self, v: TaggedOffset, order: Ordering) {
AtomicU32::store(self, v.0, order)
}
#[inline(always)]
fn swap(&self, v: TaggedOffset, order: Ordering) -> TaggedOffset {
TaggedOffset(AtomicU32::swap(self, v.0, order))
}
}
#[cfg(all(test, not(loom)))]
mod tests {
use super::*;
#[test]
fn tagged_ptr_round_trips_with_provenance() {
let b = Box::into_raw(Box::new(0xABCD_u64));
let t = TaggedPtr::from_leaf(b);
assert!(t.is_leaf());
assert!(!t.is_null());
assert_eq!(unsafe { *t.as_leaf_ptr::<u64>() }, 0xABCD);
let i = TaggedPtr::from_inner(b);
assert!(!i.is_leaf());
assert_eq!(i.as_inner_ptr::<u64>(), b);
drop(unsafe { Box::from_raw(b) });
assert!(TaggedPtr::NULL.is_null());
}
#[test]
fn tagged_offset() {
let l = TaggedOffset::from_leaf(64);
assert!(l.is_leaf());
assert_eq!(l.offset(), 64);
let n = TaggedOffset::from_inner(128);
assert!(!n.is_leaf());
assert_eq!(n.offset(), 128);
assert!(TaggedOffset::NULL.is_null());
}
}