crossbeam-epoch/src/sync/list.rs
Line | Count | Source (jump to first uncovered line) |
1 | | //! Lock-free intrusive linked list. |
2 | | //! |
3 | | //! Ideas from Michael. High Performance Dynamic Lock-Free Hash Tables and List-Based Sets. SPAA |
4 | | //! 2002. <http://dl.acm.org/citation.cfm?id=564870.564881> |
5 | | |
6 | | use core::marker::PhantomData; |
7 | | use core::sync::atomic::Ordering::{Acquire, Relaxed, Release}; |
8 | | |
9 | | use crate::{unprotected, Atomic, Guard, Shared}; |
10 | | |
11 | | /// An entry in a linked list. |
12 | | /// |
13 | | /// An Entry is accessed from multiple threads, so it would be beneficial to put it in a different |
14 | | /// cache-line than thread-local data in terms of performance. |
15 | 0 | #[derive(Debug)] |
16 | | pub(crate) struct Entry { |
17 | | /// The next entry in the linked list. |
18 | | /// If the tag is 1, this entry is marked as deleted. |
19 | | next: Atomic<Entry>, |
20 | | } |
21 | | |
22 | | /// Implementing this trait asserts that the type `T` can be used as an element in the intrusive |
23 | | /// linked list defined in this module. `T` has to contain (or otherwise be linked to) an instance |
24 | | /// of `Entry`. |
25 | | /// |
26 | | /// # Example |
27 | | /// |
28 | | /// ```ignore |
29 | | /// struct A { |
30 | | /// entry: Entry, |
31 | | /// data: usize, |
32 | | /// } |
33 | | /// |
34 | | /// impl IsElement<A> for A { |
35 | | /// fn entry_of(a: &A) -> &Entry { |
36 | | /// let entry_ptr = ((a as usize) + offset_of!(A, entry)) as *const Entry; |
37 | | /// unsafe { &*entry_ptr } |
38 | | /// } |
39 | | /// |
40 | | /// unsafe fn element_of(entry: &Entry) -> &T { |
41 | | /// let elem_ptr = ((entry as usize) - offset_of!(A, entry)) as *const T; |
42 | | /// &*elem_ptr |
43 | | /// } |
44 | | /// |
45 | | /// unsafe fn finalize(entry: &Entry, guard: &Guard) { |
46 | | /// guard.defer_destroy(Shared::from(Self::element_of(entry) as *const _)); |
47 | | /// } |
48 | | /// } |
49 | | /// ``` |
50 | | /// |
51 | | /// This trait is implemented on a type separate from `T` (although it can be just `T`), because |
52 | | /// one type might be placeable into multiple lists, in which case it would require multiple |
53 | | /// implementations of `IsElement`. In such cases, each struct implementing `IsElement<T>` |
54 | | /// represents a distinct `Entry` in `T`. |
55 | | /// |
56 | | /// For example, we can insert the following struct into two lists using `entry1` for one |
57 | | /// and `entry2` for the other: |
58 | | /// |
59 | | /// ```ignore |
60 | | /// struct B { |
61 | | /// entry1: Entry, |
62 | | /// entry2: Entry, |
63 | | /// data: usize, |
64 | | /// } |
65 | | /// ``` |
66 | | /// |
67 | | pub(crate) trait IsElement<T> { |
68 | | /// Returns a reference to this element's `Entry`. |
69 | | fn entry_of(_: &T) -> &Entry; |
70 | | |
71 | | /// Given a reference to an element's entry, returns that element. |
72 | | /// |
73 | | /// ```ignore |
74 | | /// let elem = ListElement::new(); |
75 | | /// assert_eq!(elem.entry_of(), |
76 | | /// unsafe { ListElement::element_of(elem.entry_of()) } ); |
77 | | /// ``` |
78 | | /// |
79 | | /// # Safety |
80 | | /// |
81 | | /// The caller has to guarantee that the `Entry` is called with was retrieved from an instance |
82 | | /// of the element type (`T`). |
83 | | unsafe fn element_of(_: &Entry) -> &T; |
84 | | |
85 | | /// The function that is called when an entry is unlinked from list. |
86 | | /// |
87 | | /// # Safety |
88 | | /// |
89 | | /// The caller has to guarantee that the `Entry` is called with was retrieved from an instance |
90 | | /// of the element type (`T`). |
91 | | unsafe fn finalize(_: &Entry, _: &Guard); |
92 | | } |
93 | | |
94 | | /// A lock-free, intrusive linked list of type `T`. |
95 | 0 | #[derive(Debug)] |
96 | | pub(crate) struct List<T, C: IsElement<T> = T> { |
97 | | /// The head of the linked list. |
98 | | head: Atomic<Entry>, |
99 | | |
100 | | /// The phantom data for using `T` and `C`. |
101 | | _marker: PhantomData<(T, C)>, |
102 | | } |
103 | | |
104 | | /// An iterator used for retrieving values from the list. |
105 | | pub(crate) struct Iter<'g, T, C: IsElement<T>> { |
106 | | /// The guard that protects the iteration. |
107 | | guard: &'g Guard, |
108 | | |
109 | | /// Pointer from the predecessor to the current entry. |
110 | | pred: &'g Atomic<Entry>, |
111 | | |
112 | | /// The current entry. |
113 | | curr: Shared<'g, Entry>, |
114 | | |
115 | | /// The list head, needed for restarting iteration. |
116 | | head: &'g Atomic<Entry>, |
117 | | |
118 | | /// Logically, we store a borrow of an instance of `T` and |
119 | | /// use the type information from `C`. |
120 | | _marker: PhantomData<(&'g T, C)>, |
121 | | } |
122 | | |
123 | | /// An error that occurs during iteration over the list. |
124 | 0 | #[derive(PartialEq, Debug)] |
125 | | pub(crate) enum IterError { |
126 | | /// A concurrent thread modified the state of the list at the same place that this iterator |
127 | | /// was inspecting. Subsequent iteration will restart from the beginning of the list. |
128 | | Stalled, |
129 | | } |
130 | | |
131 | | impl Default for Entry { |
132 | | /// Returns the empty entry. |
133 | 8.40k | fn default() -> Self { |
134 | 8.40k | Self { |
135 | 8.40k | next: Atomic::null(), |
136 | 8.40k | } |
137 | 8.40k | } <crossbeam_epoch::sync::list::Entry as core::default::Default>::default Line | Count | Source | 133 | 146 | fn default() -> Self { | 134 | 146 | Self { | 135 | 146 | next: Atomic::null(), | 136 | 146 | } | 137 | 146 | } |
<crossbeam_epoch::sync::list::Entry as core::default::Default>::default Line | Count | Source | 133 | 8.26k | fn default() -> Self { | 134 | 8.26k | Self { | 135 | 8.26k | next: Atomic::null(), | 136 | 8.26k | } | 137 | 8.26k | } |
|
138 | | } |
139 | | |
140 | | impl Entry { |
141 | | /// Marks this entry as deleted, deferring the actual deallocation to a later iteration. |
142 | | /// |
143 | | /// # Safety |
144 | | /// |
145 | | /// The entry should be a member of a linked list, and it should not have been deleted. |
146 | | /// It should be safe to call `C::finalize` on the entry after the `guard` is dropped, where `C` |
147 | | /// is the associated helper for the linked list. |
148 | 7.68k | pub(crate) unsafe fn delete(&self, guard: &Guard) { |
149 | 7.68k | self.next.fetch_or(1, Release, guard); |
150 | 7.68k | } <crossbeam_epoch::sync::list::Entry>::delete Line | Count | Source | 148 | 146 | pub(crate) unsafe fn delete(&self, guard: &Guard) { | 149 | 146 | self.next.fetch_or(1, Release, guard); | 150 | 146 | } |
<crossbeam_epoch::sync::list::Entry>::delete Line | Count | Source | 148 | 7.53k | pub(crate) unsafe fn delete(&self, guard: &Guard) { | 149 | 7.53k | self.next.fetch_or(1, Release, guard); | 150 | 7.53k | } |
|
151 | | } |
152 | | |
153 | | impl<T, C: IsElement<T>> List<T, C> { |
154 | | /// Returns a new, empty linked list. |
155 | 63 | pub(crate) fn new() -> Self { |
156 | 63 | Self { |
157 | 63 | head: Atomic::null(), |
158 | 63 | _marker: PhantomData, |
159 | 63 | } |
160 | 63 | } <crossbeam_epoch::sync::list::List<crossbeam_epoch::internal::Local>>::new Line | Count | Source | 155 | 43 | pub(crate) fn new() -> Self { | 156 | 43 | Self { | 157 | 43 | head: Atomic::null(), | 158 | 43 | _marker: PhantomData, | 159 | 43 | } | 160 | 43 | } |
<crossbeam_epoch::sync::list::List<crossbeam_epoch::sync::list::Entry>>::new Line | Count | Source | 155 | 4 | pub(crate) fn new() -> Self { | 156 | 4 | Self { | 157 | 4 | head: Atomic::null(), | 158 | 4 | _marker: PhantomData, | 159 | 4 | } | 160 | 4 | } |
<crossbeam_epoch::sync::list::List<crossbeam_epoch::internal::Local>>::new Line | Count | Source | 155 | 16 | pub(crate) fn new() -> Self { | 156 | 16 | Self { | 157 | 16 | head: Atomic::null(), | 158 | 16 | _marker: PhantomData, | 159 | 16 | } | 160 | 16 | } |
|
161 | | |
162 | | /// Inserts `entry` into the head of the list. |
163 | | /// |
164 | | /// # Safety |
165 | | /// |
166 | | /// You should guarantee that: |
167 | | /// |
168 | | /// - `container` is not null |
169 | | /// - `container` is immovable, e.g. inside an `Owned` |
170 | | /// - the same `Entry` is not inserted more than once |
171 | | /// - the inserted object will be removed before the list is dropped |
172 | 8.26k | pub(crate) unsafe fn insert<'g>(&'g self, container: Shared<'g, T>, guard: &'g Guard) { |
173 | 8.26k | // Insert right after head, i.e. at the beginning of the list. |
174 | 8.26k | let to = &self.head; |
175 | 8.26k | // Get the intrusively stored Entry of the new element to insert. |
176 | 8.26k | let entry: &Entry = C::entry_of(container.deref()); |
177 | 8.26k | // Make a Shared ptr to that Entry. |
178 | 8.26k | let entry_ptr = Shared::from(entry as *const _); |
179 | 8.26k | // Read the current successor of where we want to insert. |
180 | 8.26k | let mut next = to.load(Relaxed, guard); |
181 | | |
182 | 10.8k | loop { |
183 | 10.8k | // Set the Entry of the to-be-inserted element to point to the previous successor of |
184 | 10.8k | // `to`. |
185 | 10.8k | entry.next.store(next, Relaxed); |
186 | 10.8k | match to.compare_exchange_weak(next, entry_ptr, Release, Relaxed, guard) { |
187 | 10.8k | Ok(_) => break8.26k , |
188 | | // We lost the race or weak CAS failed spuriously. Update the successor and try |
189 | | // again. |
190 | 2.56k | Err(err) => next = err.current, |
191 | | } |
192 | | } |
193 | 8.26k | } <crossbeam_epoch::sync::list::List<crossbeam_epoch::internal::Local>>::insert Line | Count | Source | 172 | 146 | pub(crate) unsafe fn insert<'g>(&'g self, container: Shared<'g, T>, guard: &'g Guard) { | 173 | 146 | // Insert right after head, i.e. at the beginning of the list. | 174 | 146 | let to = &self.head; | 175 | 146 | // Get the intrusively stored Entry of the new element to insert. | 176 | 146 | let entry: &Entry = C::entry_of(container.deref()); | 177 | 146 | // Make a Shared ptr to that Entry. | 178 | 146 | let entry_ptr = Shared::from(entry as *const _); | 179 | 146 | // Read the current successor of where we want to insert. | 180 | 146 | let mut next = to.load(Relaxed, guard); | 181 | | | 182 | 146 | loop { | 183 | 146 | // Set the Entry of the to-be-inserted element to point to the previous successor of | 184 | 146 | // `to`. | 185 | 146 | entry.next.store(next, Relaxed); | 186 | 146 | match to.compare_exchange_weak(next, entry_ptr, Release, Relaxed, guard) { | 187 | 146 | Ok(_) => break, | 188 | | // We lost the race or weak CAS failed spuriously. Update the successor and try | 189 | | // again. | 190 | 0 | Err(err) => next = err.current, | 191 | | } | 192 | | } | 193 | 146 | } |
<crossbeam_epoch::sync::list::List<crossbeam_epoch::sync::list::Entry>>::insert Line | Count | Source | 172 | 8.04k | pub(crate) unsafe fn insert<'g>(&'g self, container: Shared<'g, T>, guard: &'g Guard) { | 173 | 8.04k | // Insert right after head, i.e. at the beginning of the list. | 174 | 8.04k | let to = &self.head; | 175 | 8.04k | // Get the intrusively stored Entry of the new element to insert. | 176 | 8.04k | let entry: &Entry = C::entry_of(container.deref()); | 177 | 8.04k | // Make a Shared ptr to that Entry. | 178 | 8.04k | let entry_ptr = Shared::from(entry as *const _); | 179 | 8.04k | // Read the current successor of where we want to insert. | 180 | 8.04k | let mut next = to.load(Relaxed, guard); | 181 | | | 182 | 10.6k | loop { | 183 | 10.6k | // Set the Entry of the to-be-inserted element to point to the previous successor of | 184 | 10.6k | // `to`. | 185 | 10.6k | entry.next.store(next, Relaxed); | 186 | 10.6k | match to.compare_exchange_weak(next, entry_ptr, Release, Relaxed, guard) { | 187 | 10.6k | Ok(_) => break8.04k , | 188 | | // We lost the race or weak CAS failed spuriously. Update the successor and try | 189 | | // again. | 190 | 2.56k | Err(err) => next = err.current, | 191 | | } | 192 | | } | 193 | 8.04k | } |
<crossbeam_epoch::sync::list::List<crossbeam_epoch::internal::Local>>::insert Line | Count | Source | 172 | 70 | pub(crate) unsafe fn insert<'g>(&'g self, container: Shared<'g, T>, guard: &'g Guard) { | 173 | 70 | // Insert right after head, i.e. at the beginning of the list. | 174 | 70 | let to = &self.head; | 175 | 70 | // Get the intrusively stored Entry of the new element to insert. | 176 | 70 | let entry: &Entry = C::entry_of(container.deref()); | 177 | 70 | // Make a Shared ptr to that Entry. | 178 | 70 | let entry_ptr = Shared::from(entry as *const _); | 179 | 70 | // Read the current successor of where we want to insert. | 180 | 70 | let mut next = to.load(Relaxed, guard); | 181 | | | 182 | 70 | loop { | 183 | 70 | // Set the Entry of the to-be-inserted element to point to the previous successor of | 184 | 70 | // `to`. | 185 | 70 | entry.next.store(next, Relaxed); | 186 | 70 | match to.compare_exchange_weak(next, entry_ptr, Release, Relaxed, guard) { | 187 | 70 | Ok(_) => break, | 188 | | // We lost the race or weak CAS failed spuriously. Update the successor and try | 189 | | // again. | 190 | 0 | Err(err) => next = err.current, | 191 | | } | 192 | | } | 193 | 70 | } |
|
194 | | |
195 | | /// Returns an iterator over all objects. |
196 | | /// |
197 | | /// # Caveat |
198 | | /// |
199 | | /// Every object that is inserted at the moment this function is called and persists at least |
200 | | /// until the end of iteration will be returned. Since this iterator traverses a lock-free |
201 | | /// linked list that may be concurrently modified, some additional caveats apply: |
202 | | /// |
203 | | /// 1. If a new object is inserted during iteration, it may or may not be returned. |
204 | | /// 2. If an object is deleted during iteration, it may or may not be returned. |
205 | | /// 3. The iteration may be aborted when it lost in a race condition. In this case, the winning |
206 | | /// thread will continue to iterate over the same list. |
207 | 3.71M | pub(crate) fn iter<'g>(&'g self, guard: &'g Guard) -> Iter<'g, T, C> { |
208 | 3.71M | Iter { |
209 | 3.71M | guard, |
210 | 3.71M | pred: &self.head, |
211 | 3.71M | curr: self.head.load(Acquire, guard), |
212 | 3.71M | head: &self.head, |
213 | 3.71M | _marker: PhantomData, |
214 | 3.71M | } |
215 | 3.71M | } <crossbeam_epoch::sync::list::List<crossbeam_epoch::internal::Local>>::iter Line | Count | Source | 207 | 9.72k | pub(crate) fn iter<'g>(&'g self, guard: &'g Guard) -> Iter<'g, T, C> { | 208 | 9.72k | Iter { | 209 | 9.72k | guard, | 210 | 9.72k | pred: &self.head, | 211 | 9.72k | curr: self.head.load(Acquire, guard), | 212 | 9.72k | head: &self.head, | 213 | 9.72k | _marker: PhantomData, | 214 | 9.72k | } | 215 | 9.72k | } |
<crossbeam_epoch::sync::list::List<crossbeam_epoch::internal::Local>>::iter Line | Count | Source | 207 | 3.70M | pub(crate) fn iter<'g>(&'g self, guard: &'g Guard) -> Iter<'g, T, C> { | 208 | 3.70M | Iter { | 209 | 3.70M | guard, | 210 | 3.70M | pred: &self.head, | 211 | 3.70M | curr: self.head.load(Acquire, guard), | 212 | 3.70M | head: &self.head, | 213 | 3.70M | _marker: PhantomData, | 214 | 3.70M | } | 215 | 3.70M | } |
<crossbeam_epoch::sync::list::List<crossbeam_epoch::sync::list::Entry>>::iter Line | Count | Source | 207 | 13 | pub(crate) fn iter<'g>(&'g self, guard: &'g Guard) -> Iter<'g, T, C> { | 208 | 13 | Iter { | 209 | 13 | guard, | 210 | 13 | pred: &self.head, | 211 | 13 | curr: self.head.load(Acquire, guard), | 212 | 13 | head: &self.head, | 213 | 13 | _marker: PhantomData, | 214 | 13 | } | 215 | 13 | } |
|
216 | | } |
217 | | |
218 | | impl<T, C: IsElement<T>> Drop for List<T, C> { |
219 | 21 | fn drop(&mut self) { |
220 | | unsafe { |
221 | 21 | let guard = unprotected(); |
222 | 21 | let mut curr = self.head.load(Relaxed, guard); |
223 | 41 | while let Some(c20 ) = curr.as_ref() { |
224 | 20 | let succ = c.next.load(Relaxed, guard); |
225 | | // Verify that all elements have been removed from the list. |
226 | 20 | assert_eq!(succ.tag(), 1); |
227 | | |
228 | 20 | C::finalize(curr.deref(), guard); |
229 | 20 | curr = succ; |
230 | | } |
231 | | } |
232 | 21 | } <crossbeam_epoch::sync::list::List<crossbeam_epoch::internal::Local> as core::ops::drop::Drop>::drop Line | Count | Source | 219 | 2 | fn drop(&mut self) { | 220 | | unsafe { | 221 | 2 | let guard = unprotected(); | 222 | 2 | let mut curr = self.head.load(Relaxed, guard); | 223 | 4 | while let Some(c2 ) = curr.as_ref() { | 224 | 2 | let succ = c.next.load(Relaxed, guard); | 225 | | // Verify that all elements have been removed from the list. | 226 | 2 | assert_eq!(succ.tag(), 1); | 227 | | | 228 | 2 | C::finalize(curr.deref(), guard); | 229 | 2 | curr = succ; | 230 | | } | 231 | | } | 232 | 2 | } |
<crossbeam_epoch::sync::list::List<crossbeam_epoch::sync::list::Entry> as core::ops::drop::Drop>::drop Line | Count | Source | 219 | 4 | fn drop(&mut self) { | 220 | | unsafe { | 221 | 4 | let guard = unprotected(); | 222 | 4 | let mut curr = self.head.load(Relaxed, guard); | 223 | 7 | while let Some(c3 ) = curr.as_ref() { | 224 | 3 | let succ = c.next.load(Relaxed, guard); | 225 | | // Verify that all elements have been removed from the list. | 226 | 3 | assert_eq!(succ.tag(), 1); | 227 | | | 228 | 3 | C::finalize(curr.deref(), guard); | 229 | 3 | curr = succ; | 230 | | } | 231 | | } | 232 | 4 | } |
<crossbeam_epoch::sync::list::List<crossbeam_epoch::internal::Local> as core::ops::drop::Drop>::drop Line | Count | Source | 219 | 15 | fn drop(&mut self) { | 220 | | unsafe { | 221 | 15 | let guard = unprotected(); | 222 | 15 | let mut curr = self.head.load(Relaxed, guard); | 223 | 30 | while let Some(c15 ) = curr.as_ref() { | 224 | 15 | let succ = c.next.load(Relaxed, guard); | 225 | | // Verify that all elements have been removed from the list. | 226 | 15 | assert_eq!(succ.tag(), 1); | 227 | | | 228 | 15 | C::finalize(curr.deref(), guard); | 229 | 15 | curr = succ; | 230 | | } | 231 | | } | 232 | 15 | } |
|
233 | | } |
234 | | |
235 | | impl<'g, T: 'g, C: IsElement<T>> Iterator for Iter<'g, T, C> { |
236 | | type Item = Result<&'g T, IterError>; |
237 | | |
238 | 10.5M | fn next(&mut self) -> Option<Self::Item> { |
239 | 10.5M | while let Some(c10.2M ) = unsafe { self.curr.as_ref() } { |
240 | 10.2M | let succ = c.next.load(Acquire, self.guard); |
241 | 10.2M | |
242 | 10.2M | if succ.tag() == 1 { |
243 | | // This entry was removed. Try unlinking it from the list. |
244 | 18.4E | let succ = succ.with_tag(0); |
245 | | |
246 | | // The tag should always be zero, because removing a node after a logically deleted |
247 | | // node leaves the list in an invalid state. |
248 | 8.31k | debug_assert!(self.curr.tag() == 0); |
249 | | |
250 | | // Try to unlink `curr` from the list, and get the new value of `self.pred`. |
251 | 18.4E | let succ = match self |
252 | 18.4E | .pred |
253 | 18.4E | .compare_exchange(self.curr, succ, Acquire, Acquire, self.guard) |
254 | 18.4E | { |
255 | 18.4E | Ok(_) => { |
256 | | // We succeeded in unlinking `curr`, so we have to schedule |
257 | | // deallocation. Deferred drop is okay, because `list.delete()` can only be |
258 | | // called if `T: 'static`. |
259 | 18.4E | unsafe { |
260 | 18.4E | C::finalize(self.curr.deref(), self.guard); |
261 | 18.4E | } |
262 | 18.4E | |
263 | 18.4E | // `succ` is the new value of `self.pred`. |
264 | 18.4E | succ |
265 | | } |
266 | 8 | Err(e) => { |
267 | 8 | // `e.current` is the current value of `self.pred`. |
268 | 8 | e.current |
269 | | } |
270 | | }; |
271 | | |
272 | | // If the predecessor node is already marked as deleted, we need to restart from |
273 | | // `head`. |
274 | 18.4E | if succ.tag() != 0 { |
275 | 0 | self.pred = self.head; |
276 | 0 | self.curr = self.head.load(Acquire, self.guard); |
277 | 0 |
|
278 | 0 | return Some(Err(IterError::Stalled)); |
279 | 8.32k | } |
280 | 8.32k | |
281 | 8.32k | // Move over the removed by only advancing `curr`, not `pred`. |
282 | 8.32k | self.curr = succ; |
283 | | continue; |
284 | 10.5M | } |
285 | 10.5M | |
286 | 10.5M | // Move one step forward. |
287 | 10.5M | self.pred = &c.next; |
288 | 10.5M | self.curr = succ; |
289 | 10.5M | |
290 | 10.5M | return Some(Ok(unsafe { C::element_of(c) })); |
291 | | } |
292 | | |
293 | | // We reached the end of the list. |
294 | 249k | None |
295 | 10.8M | } <crossbeam_epoch::sync::list::Iter<crossbeam_epoch::internal::Local, crossbeam_epoch::internal::Local> as core::iter::traits::iterator::Iterator>::next Line | Count | Source | 238 | 88.3k | fn next(&mut self) -> Option<Self::Item> { | 239 | 88.4k | while let Some(c85.9k ) = unsafe { self.curr.as_ref() } { | 240 | 85.9k | let succ = c.next.load(Acquire, self.guard); | 241 | 85.9k | | 242 | 85.9k | if succ.tag() == 1 { | 243 | | // This entry was removed. Try unlinking it from the list. | 244 | 18.4E | let succ = succ.with_tag(0); | 245 | | | 246 | | // The tag should always be zero, because removing a node after a logically deleted | 247 | | // node leaves the list in an invalid state. | 248 | 99 | debug_assert!(self.curr.tag() == 0); | 249 | | | 250 | | // Try to unlink `curr` from the list, and get the new value of `self.pred`. | 251 | 18.4E | let succ = match self | 252 | 18.4E | .pred | 253 | 18.4E | .compare_exchange(self.curr, succ, Acquire, Acquire, self.guard) | 254 | 18.4E | { | 255 | 18.4E | Ok(_) => { | 256 | | // We succeeded in unlinking `curr`, so we have to schedule | 257 | | // deallocation. Deferred drop is okay, because `list.delete()` can only be | 258 | | // called if `T: 'static`. | 259 | 18.4E | unsafe { | 260 | 18.4E | C::finalize(self.curr.deref(), self.guard); | 261 | 18.4E | } | 262 | 18.4E | | 263 | 18.4E | // `succ` is the new value of `self.pred`. | 264 | 18.4E | succ | 265 | | } | 266 | 2 | Err(e) => { | 267 | 2 | // `e.current` is the current value of `self.pred`. | 268 | 2 | e.current | 269 | | } | 270 | | }; | 271 | | | 272 | | // If the predecessor node is already marked as deleted, we need to restart from | 273 | | // `head`. | 274 | 18.4E | if succ.tag() != 0 { | 275 | 0 | self.pred = self.head; | 276 | 0 | self.curr = self.head.load(Acquire, self.guard); | 277 | 0 |
| 278 | 0 | return Some(Err(IterError::Stalled)); | 279 | 99 | } | 280 | 99 | | 281 | 99 | // Move over the removed by only advancing `curr`, not `pred`. | 282 | 99 | self.curr = succ; | 283 | | continue; | 284 | 86.2k | } | 285 | 86.2k | | 286 | 86.2k | // Move one step forward. | 287 | 86.2k | self.pred = &c.next; | 288 | 86.2k | self.curr = succ; | 289 | 86.2k | | 290 | 86.2k | return Some(Ok(unsafe { C::element_of(c) })); | 291 | | } | 292 | | | 293 | | // We reached the end of the list. | 294 | 2.55k | None | 295 | 88.8k | } |
<crossbeam_epoch::sync::list::Iter<crossbeam_epoch::internal::Local, crossbeam_epoch::internal::Local> as core::iter::traits::iterator::Iterator>::next Line | Count | Source | 238 | 10.4M | fn next(&mut self) -> Option<Self::Item> { | 239 | 10.4M | while let Some(c10.1M ) = unsafe { self.curr.as_ref() } { | 240 | 10.1M | let succ = c.next.load(Acquire, self.guard); | 241 | 10.1M | | 242 | 10.1M | if succ.tag() == 1 { | 243 | | // This entry was removed. Try unlinking it from the list. | 244 | 18.4E | let succ = succ.with_tag(0); | 245 | | | 246 | | // The tag should always be zero, because removing a node after a logically deleted | 247 | | // node leaves the list in an invalid state. | 248 | 55 | debug_assert!(self.curr.tag() == 0); | 249 | | | 250 | | // Try to unlink `curr` from the list, and get the new value of `self.pred`. | 251 | 18.4E | let succ = match self | 252 | 18.4E | .pred | 253 | 18.4E | .compare_exchange(self.curr, succ, Acquire, Acquire, self.guard) | 254 | 18.4E | { | 255 | 18.4E | Ok(_) => { | 256 | | // We succeeded in unlinking `curr`, so we have to schedule | 257 | | // deallocation. Deferred drop is okay, because `list.delete()` can only be | 258 | | // called if `T: 'static`. | 259 | 18.4E | unsafe { | 260 | 18.4E | C::finalize(self.curr.deref(), self.guard); | 261 | 18.4E | } | 262 | 18.4E | | 263 | 18.4E | // `succ` is the new value of `self.pred`. | 264 | 18.4E | succ | 265 | | } | 266 | 6 | Err(e) => { | 267 | 6 | // `e.current` is the current value of `self.pred`. | 268 | 6 | e.current | 269 | | } | 270 | | }; | 271 | | | 272 | | // If the predecessor node is already marked as deleted, we need to restart from | 273 | | // `head`. | 274 | 18.4E | if succ.tag() != 0 { | 275 | 0 | self.pred = self.head; | 276 | 0 | self.curr = self.head.load(Acquire, self.guard); | 277 | 0 |
| 278 | 0 | return Some(Err(IterError::Stalled)); | 279 | 57 | } | 280 | 57 | | 281 | 57 | // Move over the removed by only advancing `curr`, not `pred`. | 282 | 57 | self.curr = succ; | 283 | | continue; | 284 | 10.4M | } | 285 | 10.4M | | 286 | 10.4M | // Move one step forward. | 287 | 10.4M | self.pred = &c.next; | 288 | 10.4M | self.curr = succ; | 289 | 10.4M | | 290 | 10.4M | return Some(Ok(unsafe { C::element_of(c) })); | 291 | | } | 292 | | | 293 | | // We reached the end of the list. | 294 | 246k | None | 295 | 10.7M | } |
<crossbeam_epoch::sync::list::Iter<crossbeam_epoch::sync::list::Entry, crossbeam_epoch::sync::list::Entry> as core::iter::traits::iterator::Iterator>::next Line | Count | Source | 238 | 3.72k | fn next(&mut self) -> Option<Self::Item> { | 239 | 11.8k | while let Some(c11.8k ) = unsafe { self.curr.as_ref() } { | 240 | 11.8k | let succ = c.next.load(Acquire, self.guard); | 241 | 11.8k | | 242 | 11.8k | if succ.tag() == 1 { | 243 | | // This entry was removed. Try unlinking it from the list. | 244 | 8.20k | let succ = succ.with_tag(0); | 245 | | | 246 | | // The tag should always be zero, because removing a node after a logically deleted | 247 | | // node leaves the list in an invalid state. | 248 | 8.15k | debug_assert!(self.curr.tag() == 0); | 249 | | | 250 | | // Try to unlink `curr` from the list, and get the new value of `self.pred`. | 251 | 8.20k | let succ = match self | 252 | 8.20k | .pred | 253 | 8.20k | .compare_exchange(self.curr, succ, Acquire, Acquire, self.guard) | 254 | 8.20k | { | 255 | 8.20k | Ok(_) => { | 256 | | // We succeeded in unlinking `curr`, so we have to schedule | 257 | | // deallocation. Deferred drop is okay, because `list.delete()` can only be | 258 | | // called if `T: 'static`. | 259 | 8.20k | unsafe { | 260 | 8.20k | C::finalize(self.curr.deref(), self.guard); | 261 | 8.20k | } | 262 | 8.20k | | 263 | 8.20k | // `succ` is the new value of `self.pred`. | 264 | 8.20k | succ | 265 | | } | 266 | 0 | Err(e) => { | 267 | 0 | // `e.current` is the current value of `self.pred`. | 268 | 0 | e.current | 269 | | } | 270 | | }; | 271 | | | 272 | | // If the predecessor node is already marked as deleted, we need to restart from | 273 | | // `head`. | 274 | 8.20k | if succ.tag() != 0 { | 275 | 0 | self.pred = self.head; | 276 | 0 | self.curr = self.head.load(Acquire, self.guard); | 277 | 0 |
| 278 | 0 | return Some(Err(IterError::Stalled)); | 279 | 8.16k | } | 280 | 8.16k | | 281 | 8.16k | // Move over the removed by only advancing `curr`, not `pred`. | 282 | 8.16k | self.curr = succ; | 283 | | continue; | 284 | 3.67k | } | 285 | 3.67k | | 286 | 3.67k | // Move one step forward. | 287 | 3.67k | self.pred = &c.next; | 288 | 3.67k | self.curr = succ; | 289 | 3.67k | | 290 | 3.67k | return Some(Ok(unsafe { C::element_of(c) })); | 291 | | } | 292 | | | 293 | | // We reached the end of the list. | 294 | 5 | None | 295 | 3.68k | } |
|
296 | | } |
297 | | |
298 | | #[cfg(all(test, not(loom_crossbeam)))] |
299 | | mod tests { |
300 | | use super::*; |
301 | | use crate::{Collector, Owned}; |
302 | | use crossbeam_utils::thread; |
303 | | use std::sync::Barrier; |
304 | | |
305 | | impl IsElement<Entry> for Entry { |
306 | 7.92k | fn entry_of(entry: &Entry) -> &Entry { |
307 | 7.92k | entry |
308 | 7.92k | } |
309 | | |
310 | 11.7k | unsafe fn element_of(entry: &Entry) -> &Entry { |
311 | 11.7k | entry |
312 | 11.7k | } |
313 | | |
314 | 8.16k | unsafe fn finalize(entry: &Entry, guard: &Guard) { |
315 | 8.16k | guard.defer_destroy(Shared::from(Self::element_of(entry) as *const _)); |
316 | 8.16k | } |
317 | | } |
318 | | |
319 | | /// Checks whether the list retains inserted elements |
320 | | /// and returns them in the correct order. |
321 | | #[test] |
322 | 1 | fn insert() { crossbeam_epoch::sync::list::tests::insert::{closure#0} Line | Count | Source | 322 | 1 | fn insert() { |
|
323 | 1 | let collector = Collector::new(); |
324 | 1 | let handle = collector.register(); |
325 | 1 | let guard = handle.pin(); |
326 | 1 | |
327 | 1 | let l: List<Entry> = List::new(); |
328 | 1 | |
329 | 1 | let e1 = Owned::new(Entry::default()).into_shared(&guard); |
330 | 1 | let e2 = Owned::new(Entry::default()).into_shared(&guard); |
331 | 1 | let e3 = Owned::new(Entry::default()).into_shared(&guard); |
332 | 1 | |
333 | 1 | unsafe { |
334 | 1 | l.insert(e1, &guard); |
335 | 1 | l.insert(e2, &guard); |
336 | 1 | l.insert(e3, &guard); |
337 | 1 | } |
338 | 1 | |
339 | 1 | let mut iter = l.iter(&guard); |
340 | 1 | let maybe_e3 = iter.next(); |
341 | 1 | assert!(maybe_e3.is_some()); |
342 | 1 | assert!(maybe_e3.unwrap().unwrap() as *const Entry == e3.as_raw()); |
343 | 1 | let maybe_e2 = iter.next(); |
344 | 1 | assert!(maybe_e2.is_some()); |
345 | 1 | assert!(maybe_e2.unwrap().unwrap() as *const Entry == e2.as_raw()); |
346 | 1 | let maybe_e1 = iter.next(); |
347 | 1 | assert!(maybe_e1.is_some()); |
348 | 1 | assert!(maybe_e1.unwrap().unwrap() as *const Entry == e1.as_raw()); |
349 | 1 | assert!(iter.next().is_none()); |
350 | | |
351 | 1 | unsafe { |
352 | 1 | e1.as_ref().unwrap().delete(&guard); |
353 | 1 | e2.as_ref().unwrap().delete(&guard); |
354 | 1 | e3.as_ref().unwrap().delete(&guard); |
355 | 1 | } |
356 | 1 | } crossbeam_epoch::sync::list::tests::insert Line | Count | Source | 322 | 1 | fn insert() { | 323 | 1 | let collector = Collector::new(); | 324 | 1 | let handle = collector.register(); | 325 | 1 | let guard = handle.pin(); | 326 | 1 | | 327 | 1 | let l: List<Entry> = List::new(); | 328 | 1 | | 329 | 1 | let e1 = Owned::new(Entry::default()).into_shared(&guard); | 330 | 1 | let e2 = Owned::new(Entry::default()).into_shared(&guard); | 331 | 1 | let e3 = Owned::new(Entry::default()).into_shared(&guard); | 332 | 1 | | 333 | 1 | unsafe { | 334 | 1 | l.insert(e1, &guard); | 335 | 1 | l.insert(e2, &guard); | 336 | 1 | l.insert(e3, &guard); | 337 | 1 | } | 338 | 1 | | 339 | 1 | let mut iter = l.iter(&guard); | 340 | 1 | let maybe_e3 = iter.next(); | 341 | 1 | assert!(maybe_e3.is_some()); | 342 | 1 | assert!(maybe_e3.unwrap().unwrap() as *const Entry == e3.as_raw()); | 343 | 1 | let maybe_e2 = iter.next(); | 344 | 1 | assert!(maybe_e2.is_some()); | 345 | 1 | assert!(maybe_e2.unwrap().unwrap() as *const Entry == e2.as_raw()); | 346 | 1 | let maybe_e1 = iter.next(); | 347 | 1 | assert!(maybe_e1.is_some()); | 348 | 1 | assert!(maybe_e1.unwrap().unwrap() as *const Entry == e1.as_raw()); | 349 | 1 | assert!(iter.next().is_none()); | 350 | | | 351 | 1 | unsafe { | 352 | 1 | e1.as_ref().unwrap().delete(&guard); | 353 | 1 | e2.as_ref().unwrap().delete(&guard); | 354 | 1 | e3.as_ref().unwrap().delete(&guard); | 355 | 1 | } | 356 | 1 | } |
|
357 | | |
358 | | /// Checks whether elements can be removed from the list and whether |
359 | | /// the correct elements are removed. |
360 | | #[test] |
361 | 1 | fn delete() { crossbeam_epoch::sync::list::tests::delete::{closure#0} Line | Count | Source | 361 | 1 | fn delete() { |
|
362 | 1 | let collector = Collector::new(); |
363 | 1 | let handle = collector.register(); |
364 | 1 | let guard = handle.pin(); |
365 | 1 | |
366 | 1 | let l: List<Entry> = List::new(); |
367 | 1 | |
368 | 1 | let e1 = Owned::new(Entry::default()).into_shared(&guard); |
369 | 1 | let e2 = Owned::new(Entry::default()).into_shared(&guard); |
370 | 1 | let e3 = Owned::new(Entry::default()).into_shared(&guard); |
371 | 1 | unsafe { |
372 | 1 | l.insert(e1, &guard); |
373 | 1 | l.insert(e2, &guard); |
374 | 1 | l.insert(e3, &guard); |
375 | 1 | e2.as_ref().unwrap().delete(&guard); |
376 | 1 | } |
377 | 1 | |
378 | 1 | let mut iter = l.iter(&guard); |
379 | 1 | let maybe_e3 = iter.next(); |
380 | 1 | assert!(maybe_e3.is_some()); |
381 | 1 | assert!(maybe_e3.unwrap().unwrap() as *const Entry == e3.as_raw()); |
382 | 1 | let maybe_e1 = iter.next(); |
383 | 1 | assert!(maybe_e1.is_some()); |
384 | 1 | assert!(maybe_e1.unwrap().unwrap() as *const Entry == e1.as_raw()); |
385 | 1 | assert!(iter.next().is_none()); |
386 | | |
387 | 1 | unsafe { |
388 | 1 | e1.as_ref().unwrap().delete(&guard); |
389 | 1 | e3.as_ref().unwrap().delete(&guard); |
390 | 1 | } |
391 | 1 | |
392 | 1 | let mut iter = l.iter(&guard); |
393 | 1 | assert!(iter.next().is_none()); |
394 | 1 | } crossbeam_epoch::sync::list::tests::delete Line | Count | Source | 361 | 1 | fn delete() { | 362 | 1 | let collector = Collector::new(); | 363 | 1 | let handle = collector.register(); | 364 | 1 | let guard = handle.pin(); | 365 | 1 | | 366 | 1 | let l: List<Entry> = List::new(); | 367 | 1 | | 368 | 1 | let e1 = Owned::new(Entry::default()).into_shared(&guard); | 369 | 1 | let e2 = Owned::new(Entry::default()).into_shared(&guard); | 370 | 1 | let e3 = Owned::new(Entry::default()).into_shared(&guard); | 371 | 1 | unsafe { | 372 | 1 | l.insert(e1, &guard); | 373 | 1 | l.insert(e2, &guard); | 374 | 1 | l.insert(e3, &guard); | 375 | 1 | e2.as_ref().unwrap().delete(&guard); | 376 | 1 | } | 377 | 1 | | 378 | 1 | let mut iter = l.iter(&guard); | 379 | 1 | let maybe_e3 = iter.next(); | 380 | 1 | assert!(maybe_e3.is_some()); | 381 | 1 | assert!(maybe_e3.unwrap().unwrap() as *const Entry == e3.as_raw()); | 382 | 1 | let maybe_e1 = iter.next(); | 383 | 1 | assert!(maybe_e1.is_some()); | 384 | 1 | assert!(maybe_e1.unwrap().unwrap() as *const Entry == e1.as_raw()); | 385 | 1 | assert!(iter.next().is_none()); | 386 | | | 387 | 1 | unsafe { | 388 | 1 | e1.as_ref().unwrap().delete(&guard); | 389 | 1 | e3.as_ref().unwrap().delete(&guard); | 390 | 1 | } | 391 | 1 | | 392 | 1 | let mut iter = l.iter(&guard); | 393 | 1 | assert!(iter.next().is_none()); | 394 | 1 | } |
|
395 | | |
396 | | const THREADS: usize = 8; |
397 | | const ITERS: usize = 512; |
398 | | |
399 | | /// Contends the list on insert and delete operations to make sure they can run concurrently. |
400 | | #[test] |
401 | 1 | fn insert_delete_multi() { crossbeam_epoch::sync::list::tests::insert_delete_multi::{closure#0} Line | Count | Source | 401 | 1 | fn insert_delete_multi() { |
|
402 | 1 | let collector = Collector::new(); |
403 | 1 | |
404 | 1 | let l: List<Entry> = List::new(); |
405 | 1 | let b = Barrier::new(THREADS); |
406 | 1 | |
407 | 1 | thread::scope(|s| { |
408 | 9 | for _8 in 0..THREADS { |
409 | 8 | s.spawn(|_| { |
410 | 8 | b.wait(); |
411 | 8 | |
412 | 8 | let handle = collector.register(); |
413 | 8 | let guard: Guard = handle.pin(); |
414 | 8 | let mut v = Vec::with_capacity(ITERS); |
415 | | |
416 | 4.10k | for _4.09k in 0..ITERS { |
417 | 4.09k | let e = Owned::new(Entry::default()).into_shared(&guard); |
418 | 4.09k | v.push(e); |
419 | 4.09k | unsafe { |
420 | 4.09k | l.insert(e, &guard); |
421 | 4.09k | } |
422 | | } |
423 | | |
424 | 3.60k | for e in v { |
425 | 3.60k | unsafe { |
426 | 3.60k | e.as_ref().unwrap().delete(&guard); |
427 | 3.60k | } |
428 | | } |
429 | 8 | }); |
430 | 8 | } |
431 | 1 | }) |
432 | 1 | .unwrap(); |
433 | 1 | |
434 | 1 | let handle = collector.register(); |
435 | 1 | let guard = handle.pin(); |
436 | 1 | |
437 | 1 | let mut iter = l.iter(&guard); |
438 | 1 | assert!(iter.next().is_none()); |
439 | 1 | } crossbeam_epoch::sync::list::tests::insert_delete_multi Line | Count | Source | 401 | 1 | fn insert_delete_multi() { | 402 | 1 | let collector = Collector::new(); | 403 | 1 | | 404 | 1 | let l: List<Entry> = List::new(); | 405 | 1 | let b = Barrier::new(THREADS); | 406 | 1 | | 407 | 1 | thread::scope(|s| { | 408 | | for _ in 0..THREADS { | 409 | | s.spawn(|_| { | 410 | | b.wait(); | 411 | | | 412 | | let handle = collector.register(); | 413 | | let guard: Guard = handle.pin(); | 414 | | let mut v = Vec::with_capacity(ITERS); | 415 | | | 416 | | for _ in 0..ITERS { | 417 | | let e = Owned::new(Entry::default()).into_shared(&guard); | 418 | | v.push(e); | 419 | | unsafe { | 420 | | l.insert(e, &guard); | 421 | | } | 422 | | } | 423 | | | 424 | | for e in v { | 425 | | unsafe { | 426 | | e.as_ref().unwrap().delete(&guard); | 427 | | } | 428 | | } | 429 | | }); | 430 | | } | 431 | 1 | }) | 432 | 1 | .unwrap(); | 433 | 1 | | 434 | 1 | let handle = collector.register(); | 435 | 1 | let guard = handle.pin(); | 436 | 1 | | 437 | 1 | let mut iter = l.iter(&guard); | 438 | 1 | assert!(iter.next().is_none()); | 439 | 1 | } |
|
440 | | |
441 | | /// Contends the list on iteration to make sure that it can be iterated over concurrently. |
442 | | #[test] |
443 | 1 | fn iter_multi() { crossbeam_epoch::sync::list::tests::iter_multi::{closure#0} Line | Count | Source | 443 | 1 | fn iter_multi() { |
|
444 | 1 | let collector = Collector::new(); |
445 | 1 | |
446 | 1 | let l: List<Entry> = List::new(); |
447 | 1 | let b = Barrier::new(THREADS); |
448 | 1 | |
449 | 1 | thread::scope(|s| { |
450 | 9 | for _8 in 0..THREADS { |
451 | 8 | s.spawn(|_| { |
452 | 8 | b.wait(); |
453 | 8 | |
454 | 8 | let handle = collector.register(); |
455 | 8 | let guard: Guard = handle.pin(); |
456 | 8 | let mut v = Vec::with_capacity(ITERS); |
457 | | |
458 | 4.10k | for _4.09k in 0..ITERS { |
459 | 4.09k | let e = Owned::new(Entry::default()).into_shared(&guard); |
460 | 4.09k | v.push(e); |
461 | 4.09k | unsafe { |
462 | 4.09k | l.insert(e, &guard); |
463 | 4.09k | } |
464 | | } |
465 | | |
466 | 8 | let mut iter = l.iter(&guard); |
467 | 3.65k | for _3.64k in 0..ITERS { |
468 | 3.64k | assert!(iter.next().is_some()); |
469 | | } |
470 | | |
471 | 3.85k | for e in v { |
472 | 3.85k | unsafe { |
473 | 3.85k | e.as_ref().unwrap().delete(&guard); |
474 | 3.85k | } |
475 | | } |
476 | 8 | }); |
477 | 8 | } |
478 | 1 | }) |
479 | 1 | .unwrap(); |
480 | 1 | |
481 | 1 | let handle = collector.register(); |
482 | 1 | let guard = handle.pin(); |
483 | 1 | |
484 | 1 | let mut iter = l.iter(&guard); |
485 | 1 | assert!(iter.next().is_none()); |
486 | 1 | } crossbeam_epoch::sync::list::tests::iter_multi Line | Count | Source | 443 | 1 | fn iter_multi() { | 444 | 1 | let collector = Collector::new(); | 445 | 1 | | 446 | 1 | let l: List<Entry> = List::new(); | 447 | 1 | let b = Barrier::new(THREADS); | 448 | 1 | | 449 | 1 | thread::scope(|s| { | 450 | | for _ in 0..THREADS { | 451 | | s.spawn(|_| { | 452 | | b.wait(); | 453 | | | 454 | | let handle = collector.register(); | 455 | | let guard: Guard = handle.pin(); | 456 | | let mut v = Vec::with_capacity(ITERS); | 457 | | | 458 | | for _ in 0..ITERS { | 459 | | let e = Owned::new(Entry::default()).into_shared(&guard); | 460 | | v.push(e); | 461 | | unsafe { | 462 | | l.insert(e, &guard); | 463 | | } | 464 | | } | 465 | | | 466 | | let mut iter = l.iter(&guard); | 467 | | for _ in 0..ITERS { | 468 | | assert!(iter.next().is_some()); | 469 | | } | 470 | | | 471 | | for e in v { | 472 | | unsafe { | 473 | | e.as_ref().unwrap().delete(&guard); | 474 | | } | 475 | | } | 476 | | }); | 477 | | } | 478 | 1 | }) | 479 | 1 | .unwrap(); | 480 | 1 | | 481 | 1 | let handle = collector.register(); | 482 | 1 | let guard = handle.pin(); | 483 | 1 | | 484 | 1 | let mut iter = l.iter(&guard); | 485 | 1 | assert!(iter.next().is_none()); | 486 | 1 | } |
|
487 | | } |