Something went wrong. Try again.
Realtime safe, waitfree, concurrency library
Something went wrong. Try again.
7.9 kB · 243 lines
Rust
at main
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244// SPDX-FileCopyrightText: 2025 Lucas Baumann// SPDX-FileCopyrightText: Lucas Baumann//// SPDX-License-Identifier: Apache-2.0// SPDX-License-Identifier: MIT
use core::{ cell::UnsafeCell, mem::MaybeUninit, ptr::NonNull, sync::atomic::{self, AtomicU8, Ordering},};
use alloc::boxed::Box;
#[derive(Clone, Copy, Debug)]#[repr(u8)]pub(crate) enum Ptr { Value1 = 0, Value2 = 0b1000,}
impl Ptr { pub(crate) fn switch(&mut self) { *self = match *self { Ptr::Value1 => Self::Value2, Ptr::Value2 => Self::Value1, }; }}
#[repr(transparent)]#[derive(Debug, Clone, Copy)]struct State(u8);
impl State { /// - Read Ptr: Value 1, /// - No Read /// - Unique const INITIAL: u8 = 0b0000;
const VALUE1_READ: u8 = 0b0010; const VALUE2_READ: u8 = 0b0100; const READ_MASK: u8 = 0b0110; const NOREAD_MASK: u8 = 0b1001; const UNIQUE_MASK: u8 = 0b0001; const INV_UNIQUE_MASK: u8 = 0b1110; const READ_PTR_MASK: u8 = 0b1000; const INV_READ_PTR: u8 = 0b0111;
// only does debug tests that state is valid // could be turned into assert_uncheckeds as they are still checkd in debug fn new(value: u8) -> Self { debug_assert!( (value & Self::READ_MASK).count_ones() <= 1, "max 1 read. value: {value:b}" ); debug_assert!( value & 0b1111_0000 == 0, "only lower 4 bits used. value: {value:b}" ); Self(value) }
fn is_unique(self) -> bool { self.0 & Self::UNIQUE_MASK == 0 }
fn read_ptr(self) -> Ptr { // mask out everything except the read ptr if self.0 & Self::READ_PTR_MASK == 0 { Ptr::Value1 } else { Ptr::Value2 } }
fn with_read(self, ptr: Ptr) -> Self { debug_assert_eq!(self.0 & Self::READ_MASK, 0, "No read currently"); let mask = match ptr { Ptr::Value1 => Self::VALUE1_READ, Ptr::Value2 => Self::VALUE2_READ, };
Self(self.0 | mask) }
fn can_write(self, ptr: Ptr) -> bool { #[expect( clippy::match_like_matches_macro, reason = "i think it's more readable like this" )] match (self.0 & Self::READ_MASK, ptr) { (Self::VALUE1_READ, Ptr::Value1) => false, (Self::VALUE2_READ, Ptr::Value2) => false, _ => true, } }}
#[derive(Debug)]pub(crate) struct Shared<T> { pub(crate) value_1: UnsafeCell<T>, pub(crate) value_2: UnsafeCell<T>, /// ### Bits from low to high /// | bit | meaning | /// |---|---| /// | 0 | 0: unique, 1: second object exists | /// | 1 | is value 1 being read | /// | 2 | is value 2 being read | /// | 3 | which value should be read next (0: value 1, 1: value 2) | /// /// This mixed use doesn't lead to more contention because there are only two threads max. state: AtomicU8,}
impl<T> Shared<T> { pub(crate) fn lock_read(&self) -> &UnsafeCell<T> { // fetch update loop could be replaced with: // - set read state to both // - read read ptr // - set read state to only that // this would need to be synchronized correctly and is probably not faster than this let result = self .state .fetch_update(Ordering::Relaxed, Ordering::Acquire, |value| { let state = State::new(value); let ptr = state.read_ptr(); Some(state.with_read(ptr).0) }); // SAFETY: fetch_update closure always returns Some, so the result is alwyays Ok let result = unsafe { result.unwrap_unchecked() }; // result is the previous value, so the read_state isn't set, only the read_ptr let ptr = State::new(result).read_ptr(); self.get_value(ptr) }
pub(crate) fn release_read_lock(&self) { self.state.fetch_and(State::NOREAD_MASK, Ordering::Release); }
/// tries to get the write lock to the ptr. pub(crate) fn lock_write(&self, ptr: Ptr) -> Result<(), ()> { let state = State::new(self.state.load(Ordering::Relaxed)); if state.can_write(ptr) { // only need to synchronize with another thread when locking was successfull atomic::fence(Ordering::Acquire); Ok(()) } else { Err(()) } }
/// Releases the read lock pub(crate) fn set_read_ptr(&self, ptr: Ptr) { let value = match ptr { Ptr::Value1 => self.state.fetch_and(State::INV_READ_PTR, Ordering::Release), Ptr::Value2 => self.state.fetch_or(State::READ_PTR_MASK, Ordering::Release), }; State::new(value); }
pub(crate) fn new(value: T, second_value: fn(&T) -> T) -> (NonNull<Self>, Ptr) { // make sure that the first value gets dropped if the constructor of the second panics struct DropGuard<T>(*mut T); impl<T> Drop for DropGuard<T> { fn drop(&mut self) { unsafe { self.0.drop_in_place() } } }
let mut this: Box<MaybeUninit<Self>> = Box::new_uninit(); let this_ptr = this.as_mut_ptr(); let this = unsafe { let state_ptr = &raw mut (*this_ptr).state; let value_1_ptr = UnsafeCell::raw_get(&raw mut (*this_ptr).value_1); let value_2_ptr = UnsafeCell::raw_get(&raw mut (*this_ptr).value_2);
state_ptr.write(AtomicU8::new(State::INITIAL)); value_1_ptr.write(value); let guard = DropGuard(value_1_ptr); value_2_ptr.write(second_value(&*value_1_ptr)); // after this nothing can panic, so nothing can leak the value core::mem::forget(guard); this.assume_init() }; // SAFETY: Box is valid, so not Null ( unsafe { NonNull::new_unchecked(Box::into_raw(this)) }, Ptr::Value2, ) }
pub(crate) fn get_value(&self, ptr: Ptr) -> &UnsafeCell<T> { match ptr { Ptr::Value1 => &self.value_1, Ptr::Value2 => &self.value_2, } }
/// SAFETY: needs to have synchronized shared access to the ptr. /// If the access is not unique T needs to be Sync pub(crate) unsafe fn get_value_ref(&self, ptr: Ptr) -> &T { // SAFETY: requirements on the function make it safe unsafe { &*self.get_value(ptr).get() } }
/// If self is unique increase the count and returns true. /// Otherwise returns false. /// /// If this returns true another smart pointer has to be created otherwise memory will be leaked pub(crate) unsafe fn set_shared(&self) { self.state.fetch_or(State::UNIQUE_MASK, Ordering::Relaxed); }
pub(crate) fn is_unique(&self) -> bool { State::new(self.state.load(Ordering::Acquire)).is_unique() }
/// SAFETY: this needs to be valid. this can't be used after this function anymore. pub(crate) unsafe fn drop(this: NonNull<Self>) { // SAFETY: function SAFETY precondition let old_state = unsafe { this.as_ref() } .state .fetch_and(State::INV_UNIQUE_MASK, Ordering::Release);
if State::new(old_state).is_unique() { // see std Arc atomic::fence(Ordering::Acquire);
drop(Box::from_raw(this.as_ptr())); } }}
/// SAFETY: same as `SyncUnsafeCell`. Synchronisation done by Reader and Writer////// Isn't actually needed for the library as the public types have their own Send & Sync impls/// which are needed as they have a ptr to Shared./// Clarifies that multithreaded refs are fine.////// Send is autoimplemented, because `UnsafeCell` is Send if T: Sendunsafe impl<T: Sync> Sync for Shared<T> {}