Joel Galenson | 0d44092 | 2021-04-01 15:34:31 -0700 | [diff] [blame] | 1 | #![cfg(crossbeam_loom)] |
| 2 | |
| 3 | use crossbeam_epoch as epoch; |
| 4 | use loom_crate as loom; |
| 5 | |
| 6 | use epoch::*; |
| 7 | use epoch::{Atomic, Owned}; |
| 8 | use loom::sync::atomic::Ordering::{self, Acquire, Relaxed, Release}; |
| 9 | use loom::sync::Arc; |
| 10 | use loom::thread::spawn; |
| 11 | use std::mem::ManuallyDrop; |
| 12 | use std::ptr; |
| 13 | |
| 14 | #[test] |
| 15 | fn it_works() { |
| 16 | loom::model(|| { |
| 17 | let collector = Collector::new(); |
| 18 | let item: Atomic<String> = Atomic::from(Owned::new(String::from("boom"))); |
| 19 | let item2 = item.clone(); |
| 20 | let collector2 = collector.clone(); |
| 21 | let guard = collector.register().pin(); |
| 22 | |
| 23 | let jh = loom::thread::spawn(move || { |
| 24 | let guard = collector2.register().pin(); |
| 25 | guard.defer(move || { |
| 26 | // this isn't really safe, since other threads may still have pointers to the |
| 27 | // value, but in this limited test scenario it's okay, since we know the test won't |
| 28 | // access item after all the pins are released. |
| 29 | let mut item = unsafe { item2.into_owned() }; |
| 30 | // mutate it as a second measure to make sure the assert_eq below would fail |
| 31 | item.retain(|c| c == 'o'); |
| 32 | drop(item); |
| 33 | }); |
| 34 | }); |
| 35 | |
| 36 | let item = item.load(Ordering::SeqCst, &guard); |
| 37 | // we pinned strictly before the call to defer_destroy, |
| 38 | // so item cannot have been dropped yet |
| 39 | assert_eq!(*unsafe { item.deref() }, "boom"); |
| 40 | drop(guard); |
| 41 | |
| 42 | jh.join().unwrap(); |
| 43 | |
| 44 | drop(collector); |
| 45 | }) |
| 46 | } |
| 47 | |
| 48 | #[test] |
| 49 | fn treiber_stack() { |
| 50 | /// Treiber's lock-free stack. |
| 51 | /// |
| 52 | /// Usable with any number of producers and consumers. |
| 53 | #[derive(Debug)] |
| 54 | pub struct TreiberStack<T> { |
| 55 | head: Atomic<Node<T>>, |
| 56 | } |
| 57 | |
| 58 | #[derive(Debug)] |
| 59 | struct Node<T> { |
| 60 | data: ManuallyDrop<T>, |
| 61 | next: Atomic<Node<T>>, |
| 62 | } |
| 63 | |
| 64 | impl<T> TreiberStack<T> { |
| 65 | /// Creates a new, empty stack. |
| 66 | pub fn new() -> TreiberStack<T> { |
| 67 | TreiberStack { |
| 68 | head: Atomic::null(), |
| 69 | } |
| 70 | } |
| 71 | |
| 72 | /// Pushes a value on top of the stack. |
| 73 | pub fn push(&self, t: T) { |
| 74 | let mut n = Owned::new(Node { |
| 75 | data: ManuallyDrop::new(t), |
| 76 | next: Atomic::null(), |
| 77 | }); |
| 78 | |
| 79 | let guard = epoch::pin(); |
| 80 | |
| 81 | loop { |
| 82 | let head = self.head.load(Relaxed, &guard); |
| 83 | n.next.store(head, Relaxed); |
| 84 | |
| 85 | match self |
| 86 | .head |
| 87 | .compare_exchange(head, n, Release, Relaxed, &guard) |
| 88 | { |
| 89 | Ok(_) => break, |
| 90 | Err(e) => n = e.new, |
| 91 | } |
| 92 | } |
| 93 | } |
| 94 | |
| 95 | /// Attempts to pop the top element from the stack. |
| 96 | /// |
| 97 | /// Returns `None` if the stack is empty. |
| 98 | pub fn pop(&self) -> Option<T> { |
| 99 | let guard = epoch::pin(); |
| 100 | loop { |
| 101 | let head = self.head.load(Acquire, &guard); |
| 102 | |
| 103 | match unsafe { head.as_ref() } { |
| 104 | Some(h) => { |
| 105 | let next = h.next.load(Relaxed, &guard); |
| 106 | |
| 107 | if self |
| 108 | .head |
| 109 | .compare_exchange(head, next, Relaxed, Relaxed, &guard) |
| 110 | .is_ok() |
| 111 | { |
| 112 | unsafe { |
| 113 | guard.defer_destroy(head); |
| 114 | return Some(ManuallyDrop::into_inner(ptr::read(&(*h).data))); |
| 115 | } |
| 116 | } |
| 117 | } |
| 118 | None => return None, |
| 119 | } |
| 120 | } |
| 121 | } |
| 122 | |
| 123 | /// Returns `true` if the stack is empty. |
| 124 | pub fn is_empty(&self) -> bool { |
| 125 | let guard = epoch::pin(); |
| 126 | self.head.load(Acquire, &guard).is_null() |
| 127 | } |
| 128 | } |
| 129 | |
| 130 | impl<T> Drop for TreiberStack<T> { |
| 131 | fn drop(&mut self) { |
| 132 | while self.pop().is_some() {} |
| 133 | } |
| 134 | } |
| 135 | |
| 136 | loom::model(|| { |
| 137 | let stack1 = Arc::new(TreiberStack::new()); |
| 138 | let stack2 = Arc::clone(&stack1); |
| 139 | |
| 140 | // use 5 since it's greater than the 4 used for the sanitize feature |
| 141 | let jh = spawn(move || { |
| 142 | for i in 0..5 { |
| 143 | stack2.push(i); |
| 144 | assert!(stack2.pop().is_some()); |
| 145 | } |
| 146 | }); |
| 147 | |
| 148 | for i in 0..5 { |
| 149 | stack1.push(i); |
| 150 | assert!(stack1.pop().is_some()); |
| 151 | } |
| 152 | |
| 153 | jh.join().unwrap(); |
| 154 | assert!(stack1.pop().is_none()); |
| 155 | assert!(stack1.is_empty()); |
| 156 | }); |
| 157 | } |