1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

// #![cfg_attr(not(feature = "std"), no_std)]
#![deny(clippy::undocumented_unsafe_blocks)]

//! Arc based Rcu implementation based on my implementation in [mthom/scryer-prolog#1980](https://github.com/mthom/scryer-prolog/pull/1980)
//!
//! ```text
//! Arc
//!  Rcu
//! Arcu
//! ```

extern crate alloc;

pub mod epoch_counters;

use alloc::sync::Arc;
use epoch_counters::EpochCounterPool;

use crate::epoch_counters::EpochCounter;

pub mod atomic;
pub mod rwlock;

pub mod rcu_ref;

pub trait Rcu {
    type Item;
    type Pool: EpochCounterPool;

    fn new(initial: impl Into<Arc<Self::Item>>, epoch_counter_pool: Self::Pool) -> Self;

    /// Read the value of the Rcu for the current epoch
    ///
    /// ## Blocking
    /// The initial read on each thread may block while registering the epoch counter.
    /// Further read on the same thread won't block even for different Rcu.
    ///
    /// ## Procedure
    ///
    /// 1. Register the Epoch Counter (only done once per thread, may block)
    /// 2. atomically increment the epoch counter (by one from even to odd)
    /// 3. atomically load the arc pointer
    /// 4. atomically increment the arc strong count
    /// 5. atomically increment the epoch counter (by one from odd back to even)
    #[cfg(feature = "thread_local_counter")]
    fn read(&self) -> rcu_ref::RcuRef<Self::Item, Self::Item>
    where
        Self: Rcu<Pool = epoch_counters::GlobalEpochCounterPool>,
    {
        let arc = crate::epoch_counters::with_thread_local_epoch_counter(|epoch_counter| {
            // Safety:
            // - we just registered the epoch counter
            // - this is a thread local epoch counter that is only used here, so there can't be a concurrent use
            unsafe { self.raw_read(epoch_counter) }
        });

        rcu_ref::RcuRef::<Self::Item, Self::Item>::new(arc)
    }

    /// Replace the Rcu's content with a new value
    ///
    /// This does not synchronize writes and the last to update the active_value pointer wins.
    ///
    /// all writes that do not win will be lost, though not leaked.
    /// This will block until the old value can be reclaimed,
    /// i.e. all threads witnessed to be in the read critical sections
    /// have been witnessed to have left the critical section at least once
    fn replace(&self, new_value: impl Into<Arc<Self::Item>>) -> Arc<Self::Item>;

    /// Update the Rcu using the provided update function
    /// Retries when the Rcu has been updated/replaced between reading the old value and writing the new value
    /// Aborts when the update function returns None
    #[cfg(feature = "thread_local_counter")]
    fn try_update<F, R>(&self, mut update: F) -> Option<Arc<Self::Item>>
    where
        Self: Rcu<Pool = epoch_counters::GlobalEpochCounterPool>,
        F: FnMut(&Self::Item) -> Option<R>,
        R: Into<Arc<Self::Item>>,
    {
        // Safety:
        // epoch_counter is thread local and as such can't be in use concurrently
        // get_epoch_counters returns the list of all registered epoch counters
        crate::epoch_counters::with_thread_local_epoch_counter(|epoch_counter| unsafe {
            self.raw_try_update(move |old| update(old).map(Into::into), epoch_counter)
        })
    }

    /// ## Safety
    /// - The epoch counter must not be used concurrently
    /// - The epoch counter must belong to the EpochCounterPool of this Rcu
    unsafe fn raw_read(&self, epoch_counter: &EpochCounter) -> Arc<Self::Item>;

    /// Update the Rcu using the provided update function
    /// Retries when the Rcu has been updated/replaced between reading the old value and writing the new value
    /// Aborts when the update function returns None
    ///
    /// ## Safety
    /// - The epoch counter must not be used concurrently
    /// - The epoch counter must belong to the EpochCounterPool of this Rcu
    unsafe fn raw_try_update(
        &self,
        update: impl FnMut(&Self::Item) -> Option<Arc<Self::Item>>,
        epoch_counter: &EpochCounter,
    ) -> Option<Arc<Self::Item>>;
}