lilos_list/lib.rs
1//! A no-allocation wait-list and associated utility code.
2//!
3//! This crates provides a doubly-linked intrusive list for tracking timers or
4//! wait queues without using dynamic memory allocation. To achieve a safe Rust
5//! API, the interface is a bit unusual.
6//!
7//! See the [`List`] type for details.
8//!
9//! This list is used internally by [`lilos`] but may also be useful for
10//! applications or crates implementing new synchronization primitives. Because
11//! `lilos`'s internal use of this list is not exposed, it's not important to
12//! use exactly the same version, except to conserve flash space.
13//!
14//! [`lilos`]: https://docs.rs/lilos/latest/lilos/
15
16// IMPLEMENTATION NOTE: for shorthand and to avoid repeating ourselves, the
17// safety comments below refer to something called the Link Valid Invariant.
18// This invariant is:
19//
20// Once a List has been pinned, all nodes reachable from it -- its direct head
21// and tail pointers, plus nodes connected to the next/prev pointers of other
22// nodes reachable transitively -- must also be pinned and valid.
23//
24// In addition, a node's list pointer must also be valid or set to `None`.
25//
26// The operations below are careful to maintain this so that the pointer
27// dereferencing is sound.
28
29#![cfg_attr(not(test), no_std)]
30#![warn(
31 elided_lifetimes_in_paths,
32 explicit_outlives_requirements,
33 missing_debug_implementations,
34 missing_docs,
35 semicolon_in_expressions_from_macros,
36 single_use_lifetimes,
37 trivial_casts,
38 trivial_numeric_casts,
39 unreachable_pub,
40 unsafe_op_in_unsafe_fn,
41 unused_qualifications
42)]
43#![warn(clippy::undocumented_unsafe_blocks)]
44
45use core::future::Future;
46use core::{
47 cell::Cell,
48 marker::PhantomPinned,
49 pin::Pin,
50 ptr::NonNull,
51 task::{Poll, Waker},
52};
53
54use pin_project::{pin_project, pinned_drop};
55
56/// A list that records concurrent processes waiting for events of some sort.
57///
58/// This is a very specialized doubly-linked list, designed to implement timer
59/// lists and wait queues without dynamic memory allocation, while also passing
60/// soundness checks.
61///
62/// The list only supports the following operations:
63///
64/// - [`join`][List::join], which produces a `Future` that will register a new
65/// node on the list and resolve when it has been triggered by `wake_*`.
66///
67/// - [`wake_head_if`][List::wake_head_if], which looks at the head node of the
68/// list and triggers its owning `Future` if it passes a predicate,
69///
70/// - And a handful of other wake-related operations that can be expressed in
71/// terms of `wake_head_if`: [`wake_while`][List::wake_while],
72/// [`wake_all`][List::wake_all], [`wake_one`][List::wake_one].
73///
74/// In particular, there is no way for the owner of the list to get direct
75/// access to any of the nodes in the list -- only act upon them by waking them.
76/// The wake operation _does not_ return a reference to the node that is woken.
77///
78/// This property is critical to ensuring the soundness of an otherwise tricky
79/// data structure in Rust.
80///
81///
82/// # The contents type `T`
83///
84/// Each node in the list has associated with it a value of type `T`. `T` must
85/// implement `PartialOrd`, because nodes are kept sorted according to the order
86/// defined by `T`'s `PartialOrd` impl, from the smallest at the head to the
87/// largest at the tail.
88///
89/// Using a timestamp type allows the list to act as a timer queue, efficiently
90/// waking all nodes waiting for a certain time or lower.
91///
92/// By using `()` for `T`, you can turn the list into one that simply keeps
93/// track of insertion order. This is useful for wait queues for things like
94/// mutexes.
95///
96/// In some niche cases, it can be useful to associate additional information
97/// with a node, without having it considered for sorting purposes. You can do
98/// this by using a type that contains information but _does not_ use that
99/// information in its `PartialOrd` implementation. See [`Meta`] for a utility
100/// type that wraps some data and stops it from being sorted, or
101/// [`OrderAndMeta`] for a type that lets you have some data used for
102/// sorting, and some data simply stored.
103///
104///
105/// # Operation complexity
106///
107/// This is a doubly-linked list and its operations scale as you'd expect for
108/// that data structure:
109///
110/// - Inserting in a sorted list takes time linear in the size of the list
111/// (`O(n)`).
112///
113/// - Inserting in an unsorted list takes constant time (`O(1)`).
114///
115/// - Waking the head node takes constant time (`O(1)`).
116///
117/// - Waking a series of nodes takes time linear in the length of that sequence
118/// (`O(m)`).
119///
120/// - Detaching an arbitrary node (by dropping its owning `Future`) takes
121/// constant time (`O(1)`).
122#[derive(Default)]
123pub struct List<T> {
124 /// Links to the head and tail of the list, if the list is non-empty, or
125 /// `None` if it's empty.
126 root: Cell<Option<Root<T>>>,
127 _marker: PhantomPinned,
128}
129
130impl<T> List<T> {
131 /// Creates a new empty `List`.
132 ///
133 /// The `List` needs to be pinned before use, so this call often appears as
134 /// `pin!(List::new())`.
135 pub const fn new() -> Self {
136 Self {
137 root: Cell::new(None),
138 _marker: PhantomPinned,
139 }
140 }
141
142 /// Checks if the list is empty (i.e. contains zero nodes).
143 pub fn is_empty(&self) -> bool {
144 self.root.get().is_none()
145 }
146
147 /// Starting at the head, wakes nodes with contents that that satisfy `pred`
148 /// (that is, where `pred(n.contents)` returns `true`) until it finds one
149 /// that doesn't.
150 ///
151 /// Returns `true` if any nodes were awoken, `false` if none were (either
152 /// because the list is empty, or because the first node failed the
153 /// predicate).
154 pub fn wake_while(
155 self: Pin<&Self>,
156 mut pred: impl FnMut(&T) -> bool,
157 ) -> bool {
158 let mut any = false;
159 loop {
160 if !self.wake_head_if(&mut pred) {
161 break;
162 }
163 any = true;
164 }
165 any
166 }
167
168 /// Wakes all nodes in the list in order from head to tail.
169 ///
170 /// Returns `true` if any nodes were awoken, `false` if the list was empty.
171 pub fn wake_all(self: Pin<&Self>) -> bool {
172 self.wake_while(|_| true)
173 }
174
175 /// Wakes the head of the list, but only if it satisfies `pred` (that is, if
176 /// `pred(head.contents)` returns `true`).
177 ///
178 /// Returns `true` if there was a head node and it passed, `false` if it
179 /// didn't pass or didn't exist.
180 pub fn wake_head_if(
181 self: Pin<&Self>,
182 pred: impl FnOnce(&T) -> bool,
183 ) -> bool {
184 let Some(root) = self.root.get() else {
185 return false;
186 };
187
188 let node_ptr = root.head;
189 // Safety: dereferencing and pinning the head pointer is safe per the
190 // Link Valid Invariant.
191 let node = unsafe { Pin::new_unchecked(&*node_ptr.as_ptr()) };
192
193 debug_assert_eq!(node.list.get(), Some(NonNull::from(&*self)));
194
195 // This node is the head, it should not have a previous node.
196 debug_assert!(node.prev.get().is_none());
197
198 if !pred(&node.contents) {
199 return false;
200 }
201
202 if node_ptr == root.tail {
203 // This node is the _only_ node in the list.
204 debug_assert_eq!(node.next.get(), None,
205 "list thinks node @{node_ptr:?} is tail, \
206 node thinks it has a next");
207 self.root.set(None);
208 } else {
209 // Unlink this node from its neighbor.
210 let Some(next_ptr) = node.next.take() else {
211 panic!()
212 };
213 // Safety: dereferencing and pinning the neighbor pointer is safe
214 // per the Link Valid Invariant.
215 let next = unsafe { Pin::new_unchecked(next_ptr.as_ref()) };
216 next.prev.set(None);
217 self.root.set(Some(Root {
218 head: next_ptr,
219 ..root
220 }));
221 }
222
223 node.list.take();
224 if let Some(waker) = node.waker.take() {
225 waker.wake();
226 } else {
227 panic!();
228 }
229
230 true
231 }
232
233 /// Wakes the head of the list unconditionally.
234 ///
235 /// Returns `true` if the list was non-empty, `false` if it was empty.
236 pub fn wake_one(self: Pin<&Self>) -> bool {
237 self.wake_head_if(|_| true)
238 }
239
240 /// Returns a future that will create a node containing `contents` and
241 /// insert it into this list at the appropriate position, and then resolve
242 /// only when the node is awoken by a `wake` operation.
243 ///
244 /// This waiter will appear in the list _after_ all nodes `n` where
245 /// `n.contents <= contents`. If `T` is effectively unordered (such as `()`)
246 /// this means the waiter just gets tacked onto the end of the list.
247 ///
248 /// This operation does nothing until the future is polled. This is
249 /// important: we need proof that the returned future has been pinned before
250 /// it's safe to link it into the list, and polling the future provides that
251 /// proof.
252 ///
253 /// `contents` is consumed by this operation, because it's generally `Copy`
254 /// like a timestamp or a `()`.
255 ///
256 /// # Cancellation
257 ///
258 /// Dropping the future before it resolves loses its place in line. If there
259 /// are other nodes that are equal to `contents`, dropping and recreating
260 /// the future will move this waiter after those other nodes.
261 pub fn join(
262 self: Pin<&Self>,
263 contents: T,
264 ) -> impl Future<Output = ()> + Captures<&'_ Self>
265 where
266 T: PartialOrd,
267 {
268 WaitForDetach {
269 list: Some(self),
270 node: Node {
271 prev: Cell::new(None),
272 next: Cell::new(None),
273 waker: Cell::new(None),
274 list: Cell::new(None),
275 contents,
276 _marker: PhantomPinned,
277 },
278 }
279 }
280
281 /// Returns a future that does the same thing as [`List::join`], but with
282 /// additional behavior if it's dropped in a specific time window.
283 ///
284 /// Specifically: if the future has inserted its node into the list, then
285 /// been awoken, and then gets dropped before being polled again. In that
286 /// very narrow circumstance, the future will execute `cleanup` on its way
287 /// toward oblivion.
288 ///
289 /// This is important for synchronization primitives like mutexes, where
290 /// ownership gets passed to the next waiter in the queue without
291 /// unlocking/relocking (since that could allow races). The cleanup action
292 /// gives a waiter on such a queue an opportunity to wake the _next_ node on
293 /// the list.
294 ///
295 /// # Cancellation
296 ///
297 /// Dropping the future before it resolves loses its place in line. If there
298 /// are other nodes that are equal to `contents`, dropping and recreating
299 /// the future will move this waiter after those other nodes.
300 ///
301 /// In addition, dropping the future _after it has been triggered by a wake
302 /// operation_ (but before it's been polled to observe that)
303 pub fn join_with_cleanup(
304 self: Pin<&Self>,
305 contents: T,
306 cleanup: impl FnOnce(),
307 ) -> impl Future<Output = ()> + Captures<Pin<&'_ Self>>
308 where
309 T: PartialOrd,
310 {
311 let inner = WaitForDetach {
312 list: Some(self),
313 node: Node {
314 prev: Cell::new(None),
315 next: Cell::new(None),
316 waker: Cell::new(None),
317 list: Cell::new(None),
318 contents,
319 _marker: PhantomPinned,
320 },
321 };
322 WaitWithCleanup {
323 inner,
324 cleanup: Some(cleanup),
325 }
326 }
327}
328
329/// Internal future produced by the `join` operation.
330#[pin_project]
331struct WaitForDetach<'list, T> {
332 /// A pointer to the list we're attempting to attach to. Initialized to
333 /// `Some` on creation, then changed to `None` when we attach successfully.
334 list: Option<Pin<&'list List<T>>>,
335 /// The actual node.
336 #[pin]
337 node: Node<T>,
338}
339
340impl<T: PartialOrd> Future for WaitForDetach<'_, T> {
341 type Output = ();
342
343 fn poll(
344 self: Pin<&mut Self>,
345 cx: &mut core::task::Context<'_>,
346 ) -> Poll<Self::Output> {
347 let p = self.project();
348 let node = p.node.into_ref();
349 let node_ptr = NonNull::from(&*node);
350
351 if let Some(list) = p.list.take() {
352 // We haven't yet attached to a list. We need to complete attachment
353 // now because we've taken the list field.
354 if let Some(mut root) = list.root.get() {
355 // The list is not empty.
356 //
357 // Traverse from the tail to the head looking for the
358 // right insertion position.
359 let mut maybe_cand = Some(root.tail);
360 while let Some(cand_ptr) = maybe_cand {
361 // Safety: dereferencing and pinning the node pointer is
362 // safe per the Link Valid Invariant.
363 let candidate =
364 unsafe { Pin::new_unchecked(cand_ptr.as_ref()) };
365
366 if candidate.contents <= node.contents {
367 // This is the right place for it. `candidate` will
368 // become `node`'s new `prev`.
369 let old_next = candidate.next.replace(Some(node_ptr));
370 if let Some(next_ptr) = old_next {
371 // Safety: dereferencing and pinning the node
372 // pointer is safe per the Link Valid Invariant.
373 let next = unsafe {
374 Pin::new_unchecked(next_ptr.as_ref())
375 };
376 next.prev.set(Some(node_ptr));
377 }
378 node.next.set(old_next);
379 node.prev.set(Some(cand_ptr));
380 if cand_ptr == root.tail {
381 root.tail = node_ptr;
382 list.root.set(Some(root));
383 }
384 break;
385 }
386
387 maybe_cand = candidate.prev.get();
388 }
389
390 if maybe_cand.is_none() {
391 // node is becoming the new head of the list!
392 // Safety: dereferencing and pinning the head pointer is
393 // safe per the Link Valid Invariant.
394 let old_head =
395 unsafe { Pin::new_unchecked(root.head.as_ref()) };
396 old_head.prev.set(Some(node_ptr));
397 node.next.set(Some(root.head));
398 root.head = node_ptr;
399 list.root.set(Some(root));
400 }
401 } else {
402 // The list is currently empty. This node will become the only
403 // node in the list.
404 list.root.set(Some(Root {
405 head: node_ptr,
406 tail: node_ptr,
407 }));
408 }
409
410 // Update the node to reflect that it's in a list now.
411 node.list.set(Some(NonNull::from(&*list)));
412 node.waker.set(Some(cx.waker().clone()));
413
414 Poll::Pending
415 } else {
416 // We've already attached
417 // See if we've detached.
418 if node.list.get().is_none() {
419 // The node is not attached to any list, so we can resolve. Note
420 // that this means the future is "fused" -- it will keep
421 // returning ready if repeatedly polled.
422 Poll::Ready(())
423 } else {
424 // The node remains attached to the list. While unlikely,
425 // it's possible that the waker has changed. Update it.
426 node.waker.set(Some(cx.waker().clone()));
427 Poll::Pending
428 }
429 }
430 }
431}
432
433/// Internal future returned by `join_with_cleanup`.
434#[pin_project(PinnedDrop)]
435struct WaitWithCleanup<'list, T, F: FnOnce()> {
436 #[pin]
437 inner: WaitForDetach<'list, T>,
438 cleanup: Option<F>,
439}
440
441#[pinned_drop]
442impl<T, F: FnOnce()> PinnedDrop for WaitWithCleanup<'_, T, F> {
443 fn drop(self: Pin<&mut Self>) {
444 let p = self.project();
445 let pi = p.inner.project();
446 let node = pi.node.into_ref();
447
448 if pi.list.is_none() && node.list.get().is_none() {
449 // Process cleanup if it hasn't already been done.
450 if let Some(cleanup) = p.cleanup.take() {
451 cleanup();
452 }
453 }
454 }
455}
456
457impl<T: PartialOrd, F: FnOnce()> Future for WaitWithCleanup<'_, T, F> {
458 type Output = ();
459
460 fn poll(
461 self: Pin<&mut Self>,
462 cx: &mut core::task::Context<'_>,
463 ) -> Poll<Self::Output> {
464 let p = self.project();
465 if p.inner.poll(cx).is_ready() {
466 // The inner future has resolved -- we no longer need the cleanup
467 // action to hang around.
468 p.cleanup.take();
469 Poll::Ready(())
470 } else {
471 Poll::Pending
472 }
473 }
474}
475
476impl<T> core::fmt::Debug for List<T> {
477 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
478 f.debug_struct("List").field("root", &self.root).finish()
479 }
480}
481
482#[cfg(debug_assertions)]
483impl<T> Drop for List<T> {
484 fn drop(&mut self) {
485 debug_assert!(self.root.get().is_none());
486 }
487}
488
489struct Root<T> {
490 head: NonNull<Node<T>>,
491 tail: NonNull<Node<T>>,
492}
493
494impl<T> Copy for Root<T> {}
495impl<T> Clone for Root<T> {
496 fn clone(&self) -> Self {
497 *self
498 }
499}
500
501impl<T> core::fmt::Debug for Root<T> {
502 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
503 f.debug_struct("Root")
504 .field("head", &self.head)
505 .field("tail", &self.tail)
506 .finish()
507 }
508}
509
510struct Node<T> {
511 /// Previous node in the list, or `None` if this is the head.
512 ///
513 /// This field may be changed by neighboring nodes, and thus through a
514 /// shared reference, so it's in a `Cell`.
515 prev: Cell<Option<NonNull<Self>>>,
516 /// Next node in the list, or `None` if this is the tail.
517 ///
518 /// This field may be changed by neighboring nodes, and thus through a
519 /// shared reference, so it's in a `Cell`.
520 next: Cell<Option<NonNull<Self>>>,
521 /// Waker that should be poked if this node is detached from a list. This
522 /// does double-duty as the "attached" flag.
523 ///
524 /// The waker gets triggered by the list, rather than the node's owner, when
525 /// the node leaves the list. This means we act on it through a shared
526 /// reference. Because Waker is not Copy, and because Clone requires a
527 /// second virtual dispatch, this is in an `Option<Cell<>>` so we can `take`
528 /// it even through a shared reference.
529 waker: Cell<Option<Waker>>,
530 /// Data borne by the node to assist in ordering of newly inserted nodes. To
531 /// associate data that does not participate in ordering, use a type with a
532 /// partialeq impl that ignores part of its contents.
533 contents: T,
534 /// Pointer to the list this node is associated with.
535 ///
536 /// This field is filled in when the node joins a list, so it can be used as
537 /// an "attached" indicator: `Some` if attached, `None` if not.
538 list: Cell<Option<NonNull<List<T>>>>,
539
540 _marker: PhantomPinned,
541}
542
543impl<T> Drop for Node<T> {
544 fn drop(&mut self) {
545 if let Some(list_ptr) = self.list.take() {
546 // We are still attached to the list. Detach.
547 // Safety: dereferencing and pinning our pointer to the list is safe
548 // per the Link Valid Invariant.
549 let list = unsafe { Pin::new_unchecked(list_ptr.as_ref()) };
550 // Patch up previous node, if any.
551 if let Some(prev_ptr) = self.prev.get() {
552 // Safety: dereferencing and pinning our pointer to our neighbor
553 // is safe per the Link Valid Invariant.
554 let prev = unsafe { Pin::new_unchecked(prev_ptr.as_ref()) };
555 prev.next.set(self.next.get());
556 }
557 // Patch up next self, if any.
558 if let Some(next_ptr) = self.next.get() {
559 // Safety: dereferencing and pinning our pointer to our neighbor
560 // is safe per the Link Valid Invariant.
561 let next = unsafe { Pin::new_unchecked(next_ptr.as_ref()) };
562 next.prev.set(self.prev.get());
563 }
564
565 match (self.prev.get(), self.next.get()) {
566 (None, None) => {
567 // This was the only node in the list.
568 list.root.set(None);
569 }
570 (Some(prev_ptr), None) => {
571 // This was the tail of the list.
572 list.root.set(Some(Root {
573 tail: prev_ptr,
574 ..list.root.get().unwrap()
575 }));
576 }
577 (None, Some(next_ptr)) => {
578 // This was the head of the list.
579 list.root.set(Some(Root {
580 head: next_ptr,
581 ..list.root.get().unwrap()
582 }));
583 }
584 (Some(_), Some(_)) => {
585 // boring middle of list
586 }
587 }
588 }
589 debug_assert_eq!(self.list.get(), None);
590 }
591}
592
593/// Combines an ordering type `T` with an arbitrary metadata type `M` for use in
594/// a [`List`].
595///
596/// A [`List`] keeps its contents ordered by a type, which must implement
597/// `PartialOrd`. That's all well and good, but sometimes you need to store
598/// additional metadata in the list node that should not affect ordering -- such
599/// as requested access level in a read-write lock, for instance.
600///
601/// `OrderAndMeta` combines some piece of data `T` that implements `PartialOrd`,
602/// with another piece of data `M` that is ignored for comparisons, so that you
603/// can have a list that stays sorted but also carries arbitrary additional
604/// data.
605///
606/// If you don't care about the sorting part, have a look at [`Meta`] instead.
607#[derive(Copy, Clone, Debug)]
608pub struct OrderAndMeta<T, M>(pub T, pub M);
609
610impl<T: PartialEq, M> PartialEq for OrderAndMeta<T, M> {
611 fn eq(&self, other: &Self) -> bool {
612 self.0.eq(&other.0)
613 }
614}
615
616impl<T: PartialOrd, M> PartialOrd for OrderAndMeta<T, M> {
617 fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
618 self.0.partial_cmp(&other.0)
619 }
620}
621
622/// A wrapper type for including some arbitrary metadata `M` in a [`List`].
623///
624/// A [`List`] keeps its contents ordered by a type, which must implement
625/// `PartialOrd`. Many lists don't need special sorting, and just want to record
626/// the order of insertion of the nodes. In those cases, it's common to use
627/// `List<()>` to disable the sorting.
628///
629/// But what if you want the insertion-only-ordering of `()` but also need to
630/// include some data in each list node? `Meta` wraps the data of your choice
631/// and _blocks access to its `PartialOrd` impl,_ if it even has one to begin
632/// with. That is, all `Meta<M>`s look the same to the list, even if the `M`
633/// they contain are different.
634///
635/// If you'd like to store metadata that isn't used for sorting, but _do_ want
636/// to sort the list by some other data, see [`OrderAndMeta`].
637#[derive(Copy, Clone, Debug)]
638pub struct Meta<M>(pub M);
639
640impl<M> PartialEq for Meta<M> {
641 fn eq(&self, _other: &Self) -> bool {
642 true
643 }
644}
645
646impl<M> PartialOrd for Meta<M> {
647 fn partial_cmp(&self, _other: &Self) -> Option<core::cmp::Ordering> {
648 Some(core::cmp::Ordering::Equal)
649 }
650}
651
652/// Marker trait implementing the "Captures Trick" from Rust RFC 3498, ensuring
653/// that we do lifetime capturing right in the 2021 edition.
654///
655/// TODO: revisit this when we can switch to the 2024 edition, where the default
656/// behavior makes this less necessary.
657pub trait Captures<T> {}
658
659impl<U: ?Sized, T> Captures<T> for U {}
660
661#[cfg(test)]
662mod tests {
663 #![allow(clippy::bool_assert_comparison)]
664 #![allow(clippy::undocumented_unsafe_blocks)]
665
666 use core::{
667 cell::Cell,
668 future::Future,
669 mem::forget,
670 pin::pin,
671 sync::atomic::{AtomicUsize, Ordering},
672 task::{Context, RawWaker, RawWakerVTable, Waker},
673 };
674 use std::sync::Arc;
675
676 use crate::List;
677
678 /// VTable for the spy waker.
679 static VTABLE: RawWakerVTable = RawWakerVTable::new(
680 // clone
681 |p| {
682 let arc = unsafe { Arc::from_raw(p as *const AtomicUsize) };
683 let second_arc = Arc::clone(&arc);
684 forget(arc);
685 RawWaker::new(Arc::into_raw(second_arc) as *const (), &VTABLE)
686 },
687 // wake
688 |p| {
689 let arc = unsafe { Arc::from_raw(p as *const AtomicUsize) };
690 arc.fetch_add(1, Ordering::Relaxed);
691 // drop it to release our count.
692 },
693 // wake_by_ref
694 |p| {
695 let arc = unsafe { Arc::from_raw(p as *const AtomicUsize) };
696 arc.fetch_add(1, Ordering::Relaxed);
697 forget(arc);
698 },
699 // drop
700 |p| {
701 let _arc = unsafe { Arc::from_raw(p as *const AtomicUsize) };
702 },
703 );
704
705 /// Produces a `Waker` and also a shared `AtomicUsize` that counts how many
706 /// times the waker is actually used.
707 fn spy_waker() -> (Arc<AtomicUsize>, Waker) {
708 let count = Arc::new(AtomicUsize::new(0));
709 let second_count = Arc::clone(&count);
710 (count, unsafe {
711 Waker::from_raw(RawWaker::new(
712 Arc::into_raw(second_count) as *const (),
713 &VTABLE,
714 ))
715 })
716 }
717
718 #[test]
719 fn test_create_drop() {
720 // It'd be real bad if this didn't work, eh?
721 List::<()>::new();
722 }
723
724 #[test]
725 fn test_single_node_wait_resume() {
726 let list = pin!(List::<()>::new());
727 let list = list.as_ref();
728
729 let (wake_count, waker) = spy_waker();
730 let mut ctx = Context::from_waker(&waker);
731
732 let mut wait_fut = pin!(list.join(()));
733
734 assert!(list.is_empty());
735
736 assert!(wait_fut.as_mut().poll(&mut ctx).is_pending());
737 assert_eq!(wake_count.load(Ordering::Relaxed), 0);
738
739 assert!(!list.is_empty());
740
741 assert!(wait_fut.as_mut().poll(&mut ctx).is_pending());
742 assert!(wait_fut.as_mut().poll(&mut ctx).is_pending());
743
744 assert!(list.wake_head_if(|_| true));
745 assert_eq!(wake_count.load(Ordering::Relaxed), 1);
746 assert!(list.is_empty());
747
748 assert!(wait_fut.poll(&mut ctx).is_ready());
749 assert_eq!(wake_count.load(Ordering::Relaxed), 1);
750 }
751
752 #[test]
753 fn test_single_node_drop_while_in_list() {
754 let list = pin!(List::<()>::new());
755 let list = list.as_ref();
756
757 let (wake_count, waker) = spy_waker();
758 let mut ctx = Context::from_waker(&waker);
759
760 {
761 let mut wait_fut = pin!(list.join(()));
762 assert!(wait_fut.as_mut().poll(&mut ctx).is_pending());
763 assert!(!list.is_empty());
764 }
765 assert!(list.is_empty());
766 assert_eq!(wake_count.load(Ordering::Relaxed), 0);
767 }
768
769 #[test]
770 fn test_wake_while_insert_order() {
771 let list = pin!(List::new());
772 let list = list.into_ref();
773
774 let (wake_count, waker) = spy_waker();
775 let mut ctx = Context::from_waker(&waker);
776
777 // Insert a series of nodes:
778 let mut fut_a = pin!(list.join(()));
779 assert!(fut_a.as_mut().poll(&mut ctx).is_pending());
780
781 let mut fut_b = pin!(list.join(()));
782 assert!(fut_b.as_mut().poll(&mut ctx).is_pending());
783
784 let mut fut_c = pin!(list.join(()));
785 assert!(fut_c.as_mut().poll(&mut ctx).is_pending());
786
787 let mut fut_d = pin!(list.join(()));
788 assert!(fut_d.as_mut().poll(&mut ctx).is_pending());
789
790 // (Ab)use wake_while to only wake up two of them.
791 let mut check_count = 0;
792 let changes = list.wake_while(|_n| {
793 check_count += 1;
794 check_count <= 2
795 });
796 assert!(changes);
797 assert_eq!(check_count, 3);
798 assert_eq!(wake_count.load(Ordering::Relaxed), 2);
799
800 // We must have woken nodes A and B:
801 assert!(fut_a.as_mut().poll(&mut ctx).is_ready());
802 assert!(fut_b.as_mut().poll(&mut ctx).is_ready());
803 // ...and not nodes C and D:
804 assert!(fut_c.as_mut().poll(&mut ctx).is_pending());
805 assert!(fut_d.as_mut().poll(&mut ctx).is_pending());
806 }
807
808 #[test]
809 fn test_insert_and_wait_cancel_behavior() {
810 let list = pin!(List::new());
811 let list = list.into_ref();
812
813 // Let's check my assertion about cancel behavior, shall we?
814 let fut = list.join(());
815 drop(fut); // never polled, never woken
816
817 // And just for funsies
818 {
819 let (_, waker) = spy_waker();
820 let mut ctx = Context::from_waker(&waker);
821 let fut = pin!(list.join(()));
822 let _ = fut.poll(&mut ctx); // polled exactly once but not woken
823 }
824 }
825
826 #[test]
827 fn test_iawwc_no_fire_if_never_polled() {
828 let list = pin!(List::new());
829 let list = list.into_ref();
830
831 let cleanup_called = Cell::new(false);
832
833 let fut = list.join_with_cleanup((), || cleanup_called.set(true));
834 assert!(!cleanup_called.get());
835 drop(fut);
836 // Should not be called if the node was detached at drop.
837 assert!(!cleanup_called.get());
838 }
839
840 #[test]
841 fn test_iawwc_no_fire_if_polled_after_detach() {
842 let list = pin!(List::new());
843 let list = list.into_ref();
844
845 let (_, waker) = spy_waker();
846 let mut ctx = Context::from_waker(&waker);
847
848 let cleanup_called = Cell::new(false);
849
850 {
851 let mut fut =
852 pin!(list.join_with_cleanup((), || cleanup_called.set(true),));
853 assert!(!cleanup_called.get());
854 // Poll so that the node attaches itself.
855 let _ = fut.as_mut().poll(&mut ctx);
856 // Cause the node to become detached...
857 assert!(list.wake_one());
858 // ...and make it aware of this.
859 let _ = fut.poll(&mut ctx);
860 // dropped
861 }
862 // Should not be called if the node was polled after detach.
863 assert!(!cleanup_called.get());
864 }
865
866 #[test]
867 fn test_iawwc_fire() {
868 let list = pin!(List::new());
869 let list = list.into_ref();
870
871 let (_, waker) = spy_waker();
872 let mut ctx = Context::from_waker(&waker);
873
874 let cleanup_called = Cell::new(false);
875
876 // Testing the cleanup behavior is slightly subtle: we need to activate
877 // the logic for the case where...
878 // - The node has successfully been inserted
879 // - And then detached
880 // - But hasn't been polled to discover this.
881 //
882 // Once the node has been pinned it becomes hard to drop explicitly, but
883 // we can do it with a scope:
884 {
885 let mut fut =
886 pin!(list.join_with_cleanup((), || cleanup_called.set(true),));
887
888 // Poll the insert future to cause the node to link up.
889 let _ = fut.as_mut().poll(&mut ctx);
890 assert_eq!(cleanup_called.get(), false); // not yet
891
892 // Detach it from the list.
893 assert!(list.wake_one());
894
895 assert_eq!(cleanup_called.get(), false); // not yet
896
897 // dropped without poll
898 }
899 assert_eq!(cleanup_called.get(), true); // now
900 }
901}