| 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 |
} |