scc 0.5.8

A collection of building blocks for concurrent programming.
Documentation 
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

use std::mem::ManuallyDrop;
use std::ops::Deref;
use std::sync::atomic::AtomicUsize;
use std::sync::atomic::Ordering::Relaxed;

/// [`Underlying`] stores an instance of type `T`, and a link to the next [`Underlying`].
pub(super) struct Underlying<T> {
    next_or_refcnt: LinkOrRefCnt,
    instance: T,
}

impl<T> Underlying<T> {
    // Creates a new underlying instance.
    #[inline]
    pub(super) fn new(t: T) -> Underlying<T> {
        Underlying {
            next_or_refcnt: LinkOrRefCnt::default(),
            instance: t,
        }
    }

    /// Tries to add a strong reference to the underlying instance.
    #[inline]
    pub(super) fn try_add_ref(&self) -> bool {
        self.ref_cnt()
            .fetch_update(Relaxed, Relaxed, |r| {
                if r % 2 == 1 {
                    Some(r + 2)
                } else {
                    None
                }
            })
            .is_ok()
    }

    /// Returns a mutable reference to the instance if it is owned exclusively.
    #[inline]
    pub(super) fn get_mut(&mut self) -> Option<&mut T> {
        if self.ref_cnt().load(Relaxed) == 1 {
            Some(&mut self.instance)
        } else {
            None
        }
    }

    /// Adds a strong reference to the underlying instance.
    #[inline]
    pub(super) fn add_ref(&self) {
        let mut current = self.ref_cnt().load(Relaxed);
        debug_assert_eq!(current % 2, 1);
        if current > usize::MAX - 2 {
            panic!("reference count overflow");
        }
        while let Err(actual) =
            self.ref_cnt()
                .compare_exchange(current, current + 2, Relaxed, Relaxed)
        {
            current = actual;
        }
    }

    /// Drops a strong reference to the underlying instance.
    ///
    /// It returns `true` if it the last reference was dropped.
    #[inline]
    pub(super) fn drop_ref(&self) -> bool {
        // It does not have to be a load-acquire as everything's synchronized via the global
        // epoch. In addition to that, it also does not have to be read-modify-write as a
        // reference count increment is guaranteed to be observed by the one that decrements
        // the last reference.
        let mut current = self.ref_cnt().load(Relaxed);
        debug_assert_ne!(current, 0);
        loop {
            let new = if current <= 1 { 0 } else { current - 2 };
            if let Err(actual) = self
                .ref_cnt()
                .compare_exchange(current, new, Relaxed, Relaxed)
            {
                current = actual;
            } else {
                break;
            }
        }
        current == 1
    }

    /// Returns a reference to its reference count.
    #[inline]
    pub(super) fn ref_cnt(&self) -> &AtomicUsize {
        unsafe { &self.next_or_refcnt.refcnt.0 }
    }
}

impl<T> Deref for Underlying<T> {
    type Target = T;

    #[inline]
    fn deref(&self) -> &Self::Target {
        &self.instance
    }
}

impl<T> Link for Underlying<T> {
    fn set(&mut self, next_ptr: *const dyn Link) {
        self.next_or_refcnt.next = next_ptr;
    }
    fn free(&mut self) -> *mut dyn Link {
        let next = unsafe { self.next_or_refcnt.next as *mut dyn Link };
        unsafe { Box::from_raw(self as *mut Underlying<T>) };
        next
    }
}

/// The [`Link`] trait defines necessary methods for an instance to be reclaimed by the EBR
/// garbage collector.
pub(super) trait Link {
    /// Sets the next [`Link`] instance.
    fn set(&mut self, next_ptr: *const dyn Link);

    /// Drops itself, frees the memory, and returns the next [`Link`] attached to it.
    fn free(&mut self) -> *mut dyn Link;
}

/// [`LinkOrRefCnt`] is a union of a dynamic pointer to [`Link`] and a reference count.
pub(super) union LinkOrRefCnt {
    next: *const dyn Link,
    refcnt: ManuallyDrop<(AtomicUsize, usize)>,
}

impl Default for LinkOrRefCnt {
    #[inline]
    fn default() -> Self {
        LinkOrRefCnt {
            refcnt: ManuallyDrop::new((AtomicUsize::new(1), 0)),
        }
    }
}