urcu/stack/
container.rs

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
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
use std::marker::PhantomData;
use std::ops::Deref;
use std::ptr::NonNull;
use std::sync::Arc;

use crate::rcu::DefaultContext;
use crate::rcu::RcuContext;
use crate::stack::iterator::{Iter, IterRef};
use crate::stack::raw::{RawNode, RawStack};
use crate::stack::reference::Ref;
use crate::utility::*;

/// Defines a RCU wait-free stack.
///
/// This stack supports multiple concurrents readers and writers. It is guaranteed to
/// never block on a call.
///
/// # Limitations
///
/// ##### Mutable References
///
/// Because there might always be readers borrowing a node's data, it is impossible
/// to get a mutable references to the data inside the stack. You should design the
/// type stored in the stack with [interior mutabillity] that can be shared between
/// threads.
///
/// [interior mutabillity]: https://doc.rust-lang.org/reference/interior-mutability.html
///
/// ##### List Length
///
/// Because a writer might concurrently modify the stack, the amount of node might change
/// at any moment. To prevent user error (e.g. allocate an array for each node), there is
/// no `.len()` method.
///
/// # Safety
///
/// It is safe to send an `Arc<RcuStack<T>>` to a non-registered RCU thread. A non-registered
/// thread may drop an `RcuStack<T>` without calling any RCU primitives since lifetime rules
/// prevent any other thread from accessing a RCU reference.
pub struct RcuStack<T, C = DefaultContext> {
    raw: RawStack<T>,
    _unsend: PhantomUnsend<(T, C)>,
    _unsync: PhantomUnsync<(T, C)>,
}

impl<T, C> RcuStack<T, C>
where
    C: RcuContext,
{
    /// Creates a new RCU stack.
    pub fn new() -> Arc<Self> {
        Arc::new(RcuStack {
            // SAFETY: All node are pop'ed before dropping.
            raw: unsafe { RawStack::new() },
            _unsend: PhantomData,
            _unsync: PhantomData,
        })
    }

    /// Adds an element to the top of the stack.
    pub fn push(&self, data: T) {
        let node = RawNode::new(data);

        self.raw.push(node);
    }

    /// Removes an element from the top of the stack.
    pub fn pop(&self, guard: &C::Guard<'_>) -> Option<Ref<T, C>>
    where
        T: Send,
    {
        let _ = guard;

        // SAFETY: The RCU critical section is enforced.
        // SAFETY: RCU grace period is enforced.
        let node = unsafe { self.raw.pop() };

        NonNull::new(node).map(Ref::new)
    }

    /// Removes all elements from the stack.
    pub fn pop_all(&self, _guard: &C::Guard<'_>) -> IterRef<T, C>
    where
        T: Send,
    {
        // SAFETY: The RCU critical section is enforced.
        // SAFETY: RCU grace period is enforced.
        IterRef::new(unsafe { self.raw.pop_all() })
    }

    /// Returns a reference to the element on top of the stack.
    pub fn peek<'me, 'ctx, 'guard>(&'me self, _guard: &'guard C::Guard<'ctx>) -> Option<&'guard T>
    where
        'me: 'guard,
    {
        // SAFETY: The RCU critical section is enforced.
        let node = unsafe { self.raw.head() };

        // SAFETY: The pointer can be safely converted to reference.
        unsafe { node.as_ref() }.map(|node| node.deref())
    }

    /// Returns an iterator over the stack.
    ///
    /// The iterator yields all items from top to bottom.
    pub fn iter<'me, 'ctx, 'guard>(
        &'me self,
        guard: &'guard C::Guard<'ctx>,
    ) -> Iter<'ctx, 'guard, T, C>
    where
        'me: 'guard,
    {
        // SAFETY: The RCU critical section is enforced.
        Iter::new(unsafe { self.raw.iter() }, guard)
    }

    /// Returns `true` if there is no node in the stack.
    pub fn is_empty(&self) -> bool {
        self.raw.empty()
    }
}

/// #### Safety
///
/// An [`RcuStack`] can be used to send `T` to another thread.
unsafe impl<T, C> Send for RcuStack<T, C>
where
    T: Send,
    C: RcuContext,
{
}

/// #### Safety
///
/// An [`RcuStack`] can be used to share `T` between threads.
unsafe impl<T, C> Sync for RcuStack<T, C>
where
    T: Sync,
    C: RcuContext,
{
}

impl<T, C> Drop for RcuStack<T, C> {
    fn drop(&mut self) {
        // SAFETY: The RCU read-lock is not needed there are no other writers.
        // SAFETY: The RCU grace period is not needed there are no other readers.
        let mut iter = unsafe { self.raw.pop_all() };

        // SAFETY: The RCU read-lock is not needed there are no other writers.
        while let Some(ptr) = unsafe { iter.next().as_mut() } {
            // SAFETY: The pointer is always non-null and valid.
            drop(unsafe { Box::from_raw(ptr) });
        }
    }
}