]>
Commit | Line | Data |
---|---|---|
6a06907d XL |
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 | } |