cs431_homework/hazard_pointer/
hazard.rs

1use core::ptr::{self, NonNull};
2#[cfg(not(feature = "check-loom"))]
3use core::sync::atomic::{AtomicBool, AtomicPtr, AtomicUsize, Ordering, fence};
4use std::collections::HashSet;
5use std::fmt;
6
7#[cfg(feature = "check-loom")]
8use loom::sync::atomic::{AtomicBool, AtomicPtr, AtomicUsize, Ordering, fence};
9
10use super::HAZARDS;
11
12/// Represents the ownership of a hazard pointer slot.
13pub struct Shield {
14    slot: NonNull<HazardSlot>,
15}
16
17impl Shield {
18    /// Creates a new shield for hazard pointer.
19    pub fn new(hazards: &HazardBag) -> Self {
20        let slot = hazards.acquire_slot().into();
21        Self { slot }
22    }
23
24    /// Store `pointer` to the hazard slot.
25    pub fn set<T>(&self, pointer: *mut T) {
26        todo!()
27    }
28
29    /// Clear the hazard slot.
30    pub fn clear(&self) {
31        self.set(ptr::null_mut::<()>())
32    }
33
34    /// Check if `src` still points to `pointer`. If not, returns the current value.
35    ///
36    /// For a pointer `p`, if "`src` still pointing to `pointer`" implies that `p` is not retired,
37    /// then `Ok(())` means that shields set to `p` are validated.
38    pub fn validate<T>(pointer: *mut T, src: &AtomicPtr<T>) -> Result<(), *mut T> {
39        todo!()
40    }
41
42    /// Try protecting `pointer` obtained from `src`. If not, returns the current value.
43    ///
44    /// If "`src` still pointing to `pointer`" implies that `pointer` is not retired, then `Ok(())`
45    /// means that this shield is validated.
46    pub fn try_protect<T>(&self, pointer: *mut T, src: &AtomicPtr<T>) -> Result<(), *mut T> {
47        self.set(pointer);
48        Self::validate(pointer, src).inspect_err(|_| self.clear())
49    }
50
51    /// Get a protected pointer from `src`.
52    ///
53    /// See `try_protect()`.
54    pub fn protect<T>(&self, src: &AtomicPtr<T>) -> *mut T {
55        let mut pointer = src.load(Ordering::Relaxed);
56        while let Err(new) = self.try_protect(pointer, src) {
57            pointer = new;
58            #[cfg(feature = "check-loom")]
59            loom::sync::atomic::spin_loop_hint();
60        }
61        pointer
62    }
63}
64
65impl Default for Shield {
66    fn default() -> Self {
67        Self::new(&HAZARDS)
68    }
69}
70
71impl Drop for Shield {
72    /// Clear and release the ownership of the hazard slot.
73    fn drop(&mut self) {
74        todo!()
75    }
76}
77
78impl fmt::Debug for Shield {
79    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
80        f.debug_struct("Shield")
81            .field("slot address", &self.slot)
82            .field("slot data", unsafe { self.slot.as_ref() })
83            .finish()
84    }
85}
86
87/// Global bag (multiset) of hazards pointers.
88/// `HazardBag.head` and `HazardSlot.next` form a grow-only list of all hazard slots. Slots are
89/// never removed from this list. Instead, it gets deactivated and recycled for other `Shield`s.
90#[derive(Debug)]
91pub struct HazardBag {
92    head: AtomicPtr<HazardSlot>,
93}
94
95/// See `HazardBag`
96#[derive(Debug)]
97struct HazardSlot {
98    // Whether this slot is occupied by a `Shield`.
99    active: AtomicBool,
100    // Machine representation of the hazard pointer.
101    hazard: AtomicPtr<()>,
102    // Immutable pointer to the next slot in the bag.
103    next: *const HazardSlot,
104}
105
106impl HazardSlot {
107    fn new() -> Self {
108        todo!()
109    }
110}
111
112impl HazardBag {
113    #[cfg(not(feature = "check-loom"))]
114    /// Creates a new global hazard set.
115    pub const fn new() -> Self {
116        Self {
117            head: AtomicPtr::new(ptr::null_mut()),
118        }
119    }
120
121    #[cfg(feature = "check-loom")]
122    /// Creates a new global hazard set.
123    pub fn new() -> Self {
124        Self {
125            head: AtomicPtr::new(ptr::null_mut()),
126        }
127    }
128
129    /// Acquires a slot in the hazard set, either by recycling an inactive slot or allocating a new
130    /// slot.
131    fn acquire_slot(&self) -> &HazardSlot {
132        todo!()
133    }
134
135    /// Find an inactive slot and activate it.
136    fn try_acquire_inactive(&self) -> Option<&HazardSlot> {
137        todo!()
138    }
139
140    /// Returns all the hazards in the set.
141    pub fn all_hazards(&self) -> HashSet<*mut ()> {
142        todo!()
143    }
144}
145
146impl Default for HazardBag {
147    fn default() -> Self {
148        Self::new()
149    }
150}
151
152impl Drop for HazardBag {
153    /// Frees all slots.
154    fn drop(&mut self) {
155        todo!()
156    }
157}
158
159unsafe impl Send for HazardSlot {}
160unsafe impl Sync for HazardSlot {}
161
162#[cfg(all(test, not(feature = "check-loom")))]
163mod tests {
164    use std::collections::HashSet;
165    use std::ops::Range;
166    use std::sync::Arc;
167    use std::sync::atomic::AtomicPtr;
168    use std::{mem, thread};
169
170    use super::{HazardBag, Shield};
171
172    const THREADS: usize = 8;
173    const VALUES: Range<usize> = 1..1024;
174
175    // `all_hazards` should return hazards protected by shield(s).
176    #[test]
177    fn all_hazards_protected() {
178        let hazard_bag = Arc::new(HazardBag::new());
179        (0..THREADS)
180            .map(|_| {
181                let hazard_bag = hazard_bag.clone();
182                thread::spawn(move || {
183                    for data in VALUES {
184                        let src = AtomicPtr::new(data as *mut ());
185                        let shield = Shield::new(&hazard_bag);
186                        let _ = shield.protect(&src);
187                        // leak the shield so that it is not unprotected.
188                        mem::forget(shield);
189                    }
190                })
191            })
192            .collect::<Vec<_>>()
193            .into_iter()
194            .for_each(|th| th.join().unwrap());
195        let all = hazard_bag.all_hazards();
196        let values = VALUES.map(|data| data as *mut ()).collect();
197        assert!(all.is_superset(&values))
198    }
199
200    // `all_hazards` should not return values that are no longer protected.
201    #[test]
202    fn all_hazards_unprotected() {
203        let hazard_bag = Arc::new(HazardBag::new());
204        (0..THREADS)
205            .map(|_| {
206                let hazard_bag = hazard_bag.clone();
207                thread::spawn(move || {
208                    for data in VALUES {
209                        let src = AtomicPtr::new(data as *mut ());
210                        let shield = Shield::new(&hazard_bag);
211                        let _ = shield.protect(&src);
212                    }
213                })
214            })
215            .collect::<Vec<_>>()
216            .into_iter()
217            .for_each(|th| th.join().unwrap());
218        let all = hazard_bag.all_hazards();
219        let values = VALUES.map(|data| data as *mut ()).collect();
220        let intersection: HashSet<_> = all.intersection(&values).collect();
221        assert!(intersection.is_empty())
222    }
223
224    // `acquire_slot` should recycle existing slots.
225    #[test]
226    fn recycle_slots() {
227        let hazard_bag = HazardBag::new();
228        // allocate slots
229        let shields = (0..1024)
230            .map(|_| Shield::new(&hazard_bag))
231            .collect::<Vec<_>>();
232        // slot addresses
233        let old_slots = shields
234            .iter()
235            .map(|s| s.slot.as_ptr() as usize)
236            .collect::<HashSet<_>>();
237        // release the slots
238        drop(shields);
239
240        let shields = (0..128)
241            .map(|_| Shield::new(&hazard_bag))
242            .collect::<Vec<_>>();
243        let new_slots = shields
244            .iter()
245            .map(|s| s.slot.as_ptr() as usize)
246            .collect::<HashSet<_>>();
247
248        // no new slots should've been created
249        assert!(new_slots.is_subset(&old_slots));
250    }
251}
cs431_homework/hazard_pointer/hazard.rs

cs431_homework/hazard_pointer/
hazard.rs
