1#![cfg(crossbeam_loom)]
2
3use crossbeam_epoch as epoch;
4use loom_crate as loom;
5
6use epoch::*;
7use epoch::{Atomic, Owned};
8use loom::sync::atomic::Ordering::{self, Acquire, Relaxed, Release};
9use loom::sync::Arc;
10use loom::thread::spawn;
11use std::mem::ManuallyDrop;
12use std::ptr;
13
14#[test]
15fn 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]
49fn 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}
158