cordyceps/stack.rs
1//! [Intrusive], singly-linked first-in, first-out (FIFO) stacks.
2//!
3//! See the documentation for the [`Stack`] and [`TransferStack`] types for
4//! details.
5//!
6//! [intrusive]: crate#intrusive-data-structures
7#![warn(missing_debug_implementations)]
8
9use crate::{loom::cell::UnsafeCell, Linked};
10use core::{fmt, marker::PhantomPinned, ptr::NonNull};
11
12#[cfg(target_has_atomic = "ptr")]
13pub use has_cas_atomics::*;
14
15/// Items exclusive to targets with CAS atomics
16#[cfg(target_has_atomic = "ptr")]
17mod has_cas_atomics {
18 use core::{
19 fmt,
20 ptr::{self, NonNull},
21 };
22
23 use crate::{
24 loom::sync::atomic::{AtomicPtr, Ordering::*},
25 Linked,
26 };
27
28 use super::{Links, Stack};
29
30 /// An [intrusive] lock-free singly-linked FIFO stack, where all entries
31 /// currently in the stack are consumed in a single atomic operation.
32 ///
33 /// A transfer stack is perhaps the world's simplest lock-free concurrent data
34 /// structure. It provides two primary operations:
35 ///
36 /// - [`TransferStack::push`], which appends an element to the end of the
37 /// transfer stack,
38 ///
39 /// - [`TransferStack::take_all`], which atomically takes all elements currently
40 /// on the transfer stack and returns them as a new mutable [`Stack`].
41 ///
42 /// These are both *O*(1) operations, although `push` performs a
43 /// compare-and-swap loop that may be retried if another producer concurrently
44 /// pushed an element.
45 ///
46 /// In order to be part of a `TransferStack`, a type `T` must implement
47 /// the [`Linked`] trait for [`stack::Links<T>`](Links).
48 ///
49 /// Pushing elements into a `TransferStack` takes ownership of those elements
50 /// through an owning [`Handle` type](Linked::Handle). Dropping a
51 /// [`TransferStack`] drops all elements currently linked into the stack.
52 ///
53 /// A transfer stack is often useful in cases where a large number of resources
54 /// must be efficiently transferred from several producers to a consumer, such
55 /// as for reuse or cleanup. For example, a [`TransferStack`] can be used as the
56 /// "thread" (shared) free list in a [`mimalloc`-style sharded
57 /// allocator][mimalloc], with a mutable [`Stack`] used as the local
58 /// (unsynchronized) free list. When an allocation is freed from the same CPU
59 /// core that it was allocated on, it is pushed to the local free list, using an
60 /// unsynchronized mutable [`Stack::push`] operation. If an allocation is freed
61 /// from a different thread, it is instead pushed to that thread's shared free
62 /// list, a [`TransferStack`], using an atomic [`TransferStack::push`]
63 /// operation. New allocations are popped from the local unsynchronized free
64 /// list, and if the local free list is empty, the entire shared free list is
65 /// moved onto the local free list. This allows objects which do not leave the
66 /// CPU core they were allocated on to be both allocated and deallocated using
67 /// unsynchronized operations, and new allocations only perform an atomic
68 /// operation when the local free list is empty.
69 ///
70 /// [intrusive]: crate#intrusive-data-structures
71 /// [mimalloc]: https://www.microsoft.com/en-us/research/uploads/prod/2019/06/mimalloc-tr-v1.pdf
72 pub struct TransferStack<T: Linked<Links<T>>> {
73 head: AtomicPtr<T>,
74 }
75
76 // === impl TransferStack ===
77 impl<T> TransferStack<T>
78 where
79 T: Linked<Links<T>>,
80 {
81 /// Returns a new `TransferStack` with no elements.
82 #[cfg(not(loom))]
83 #[must_use]
84 pub const fn new() -> Self {
85 Self {
86 head: AtomicPtr::new(ptr::null_mut()),
87 }
88 }
89
90 /// Returns a new `TransferStack` with no elements.
91 #[cfg(loom)]
92 #[must_use]
93 pub fn new() -> Self {
94 Self {
95 head: AtomicPtr::new(ptr::null_mut()),
96 }
97 }
98
99 /// Pushes `element` onto the end of this `TransferStack`, taking ownership
100 /// of it.
101 ///
102 /// This is an *O*(1) operation, although it performs a compare-and-swap
103 /// loop that may repeat if another producer is concurrently calling `push`
104 /// on the same `TransferStack`.
105 ///
106 /// This takes ownership over `element` through its [owning `Handle`
107 /// type](Linked::Handle). If the `TransferStack` is dropped before the
108 /// pushed `element` is removed from the stack, the `element` will be dropped.
109 #[inline]
110 pub fn push(&self, element: T::Handle) {
111 self.push_was_empty(element);
112 }
113
114 /// Pushes `element` onto the end of this `TransferStack`, taking ownership
115 /// of it. Returns `true` if the stack was previously empty (the previous
116 /// head was null).
117 ///
118 /// This is an *O*(1) operation, although it performs a compare-and-swap
119 /// loop that may repeat if another producer is concurrently calling `push`
120 /// on the same `TransferStack`.
121 ///
122 /// This takes ownership over `element` through its [owning `Handle`
123 /// type](Linked::Handle). If the `TransferStack` is dropped before the
124 /// pushed `element` is removed from the stack, the `element` will be dropped.
125 pub fn push_was_empty(&self, element: T::Handle) -> bool {
126 let ptr = T::into_ptr(element);
127 test_trace!(?ptr, "TransferStack::push");
128 let links = unsafe { T::links(ptr).as_mut() };
129 debug_assert!(links.next.with(|next| unsafe { (*next).is_none() }));
130
131 let mut head = self.head.load(Relaxed);
132 loop {
133 test_trace!(?ptr, ?head, "TransferStack::push");
134 links.next.with_mut(|next| unsafe {
135 *next = NonNull::new(head);
136 });
137
138 match self
139 .head
140 .compare_exchange_weak(head, ptr.as_ptr(), AcqRel, Acquire)
141 {
142 Ok(old) => {
143 let was_empty = old.is_null();
144 test_trace!(?ptr, ?head, was_empty, "TransferStack::push -> pushed");
145 return was_empty;
146 }
147 Err(actual) => head = actual,
148 }
149 }
150 }
151
152 /// Takes all elements *currently* in this `TransferStack`, returning a new
153 /// mutable [`Stack`] containing those elements.
154 ///
155 /// This is an *O*(1) operation which does not allocate memory. It will
156 /// never loop and does not spin.
157 #[must_use]
158 pub fn take_all(&self) -> Stack<T> {
159 let head = self.head.swap(ptr::null_mut(), AcqRel);
160 let head = NonNull::new(head);
161 Stack { head }
162 }
163
164 /// Returns `true` if this `TransferStack` is empty.
165 ///
166 /// Unlike [`take_all`], this only loads the head pointer, so a consumer
167 /// polling a usually-empty stack can skip the read-modify-write. The
168 /// load is `Relaxed` and the result is a snapshot: a producer may
169 /// [`push`] the instant it returns, and a `false` result still has to be
170 /// followed by [`take_all`], whose `AcqRel` swap is what synchronizes
171 /// with the pushes it takes.
172 ///
173 /// [`take_all`]: Self::take_all
174 /// [`push`]: Self::push
175 #[inline]
176 #[must_use]
177 pub fn is_empty(&self) -> bool {
178 self.head.load(Relaxed).is_null()
179 }
180 }
181
182 impl<T> Drop for TransferStack<T>
183 where
184 T: Linked<Links<T>>,
185 {
186 fn drop(&mut self) {
187 // The stack owns any entries that are still in the stack; ensure they
188 // are dropped before dropping the stack.
189 for entry in self.take_all() {
190 drop(entry);
191 }
192 }
193 }
194
195 impl<T> fmt::Debug for TransferStack<T>
196 where
197 T: Linked<Links<T>>,
198 {
199 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
200 let Self { head } = self;
201 f.debug_struct("TransferStack").field("head", head).finish()
202 }
203 }
204
205 impl<T> Default for TransferStack<T>
206 where
207 T: Linked<Links<T>>,
208 {
209 fn default() -> Self {
210 Self::new()
211 }
212 }
213}
214
215/// An [intrusive] singly-linked mutable FIFO stack.
216///
217/// This is a very simple implementation of a linked `Stack`, which provides
218/// *O*(1) [`push`](Self::push) and [`pop`](Self::pop) operations. Items are
219/// popped from the stack in the opposite order that they were pushed in.
220///
221/// A [`Stack`] also implements the [`Iterator`] trait, with the
222/// [`Iterator::next`] method popping elements from the end of the stack.
223///
224/// In order to be part of a `Stack`, a type `T` must implement
225/// the [`Linked`] trait for [`stack::Links<T>`](Links).
226///
227/// Pushing elements into a `Stack` takes ownership of those elements
228/// through an owning [`Handle` type](Linked::Handle). Dropping a
229/// `Stack` drops all elements currently linked into the stack.
230///
231/// [intrusive]: crate#intrusive-data-structures
232pub struct Stack<T: Linked<Links<T>>> {
233 pub(crate) head: Option<NonNull<T>>,
234}
235
236/// Singly-linked-list linkage
237///
238/// Links to other nodes in a [`TransferStack`], [`Stack`], or [`SortedList`].
239///
240/// In order to be part of a [`TransferStack`], [`Stack`], or [`SortedList`],
241/// a type must contain an instance of this type, and must implement the
242/// [`Linked`] trait for `Links<Self>`.
243///
244/// [`SortedList`]: crate::SortedList
245//
246// TODO(AJM): In the next breaking change, we might want to specifically have
247// a `SingleLinks` and `DoubleLinks` type to make the relationship more clear,
248// instead of "stack" being singly-flavored and "list" being doubly-flavored
249pub struct Links<T> {
250 /// The next node in the queue.
251 pub(crate) next: UnsafeCell<Option<NonNull<T>>>,
252
253 /// Linked list links must always be `!Unpin`, in order to ensure that they
254 /// never recieve LLVM `noalias` annotations; see also
255 /// <https://github.com/rust-lang/rust/issues/63818>.
256 _unpin: PhantomPinned,
257}
258
259// === impl Stack ===
260
261impl<T> Stack<T>
262where
263 T: Linked<Links<T>>,
264{
265 /// Returns a new `Stack` with no elements in it.
266 #[must_use]
267 pub const fn new() -> Self {
268 Self { head: None }
269 }
270
271 /// Pushes `element` onto the end of this `Stack`, taking ownership
272 /// of it.
273 ///
274 /// Returns `true` if the stack was previously empty, and `false` if the stack
275 /// contained at least one other element.
276 ///
277 /// This is an *O*(1) operation that does not allocate memory. It will never
278 /// loop.
279 ///
280 /// This takes ownership over `element` through its [owning `Handle`
281 /// type](Linked::Handle). If the `Stack` is dropped before the
282 /// pushed `element` is [`pop`](Self::pop)pped from the stack, the `element`
283 /// will be dropped.
284 pub fn push_was_empty(&mut self, element: T::Handle) -> bool {
285 let ptr = T::into_ptr(element);
286 test_trace!(?ptr, ?self.head, "Stack::push_was_empty");
287 unsafe {
288 // Safety: we have exclusive mutable access to the stack, and
289 // therefore can also mutate the stack's entries.
290 let links = T::links(ptr).as_mut();
291 links.next.with_mut(|next| {
292 debug_assert!((*next).is_none());
293 *next = self.head.replace(ptr);
294 (*next).is_none()
295 })
296 }
297 }
298
299 /// Pushes `element` onto the end of this `Stack`, taking ownership
300 /// of it.
301 ///
302 /// This is an *O*(1) operation that does not allocate memory. It will never
303 /// loop.
304 ///
305 /// This takes ownership over `element` through its [owning `Handle`
306 /// type](Linked::Handle). If the `Stack` is dropped before the
307 /// pushed `element` is [`pop`](Self::pop)pped from the stack, the `element`
308 /// will be dropped.
309 ///
310 /// For a variant of this method that returns a `bool` indicating if the
311 /// list was empty, see [`Stack::push_was_empty`].
312 #[inline]
313 pub fn push(&mut self, element: T::Handle) {
314 self.push_was_empty(element);
315 }
316
317 /// Returns the element most recently [push](Self::push)ed to this `Stack`,
318 /// or `None` if the stack is empty.
319 ///
320 /// This is an *O*(1) operation which does not allocate memory. It will
321 /// never loop and does not spin.
322 #[must_use]
323 pub fn pop(&mut self) -> Option<T::Handle> {
324 test_trace!(?self.head, "Stack::pop");
325 let head = self.head.take()?;
326 unsafe {
327 // Safety: we have exclusive ownership over this chunk of stack.
328
329 // advance the head link to the next node after the current one (if
330 // there is one).
331 self.head = T::links(head).as_mut().next.with_mut(|next| (*next).take());
332
333 test_trace!(?self.head, "Stack::pop -> popped");
334
335 // return the current node
336 Some(T::from_ptr(head))
337 }
338 }
339
340 /// Takes all elements *currently* in this `Stack`, returning a new
341 /// mutable `Stack` containing those elements.
342 ///
343 /// This is an *O*(1) operation which does not allocate memory. It will
344 /// never loop and does not spin.
345 #[must_use]
346 pub fn take_all(&mut self) -> Self {
347 Self {
348 head: self.head.take(),
349 }
350 }
351
352 /// Returns `true` if this `Stack` is empty.
353 #[inline]
354 #[must_use]
355 pub fn is_empty(&self) -> bool {
356 self.head.is_none()
357 }
358}
359
360impl<T> Drop for Stack<T>
361where
362 T: Linked<Links<T>>,
363{
364 fn drop(&mut self) {
365 // The stack owns any entries that are still in the stack; ensure they
366 // are dropped before dropping the stack.
367 for entry in self {
368 drop(entry);
369 }
370 }
371}
372
373impl<T> fmt::Debug for Stack<T>
374where
375 T: Linked<Links<T>>,
376{
377 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
378 let Self { head } = self;
379 f.debug_struct("Stack").field("head", head).finish()
380 }
381}
382
383impl<T> Iterator for Stack<T>
384where
385 T: Linked<Links<T>>,
386{
387 type Item = T::Handle;
388
389 fn next(&mut self) -> Option<Self::Item> {
390 self.pop()
391 }
392}
393
394impl<T> Default for Stack<T>
395where
396 T: Linked<Links<T>>,
397{
398 fn default() -> Self {
399 Self::new()
400 }
401}
402
403/// # Safety
404///
405/// A `Stack` is `Send` if `T` is send, because moving it across threads
406/// also implicitly moves any `T`s in the stack.
407unsafe impl<T> Send for Stack<T>
408where
409 T: Send,
410 T: Linked<Links<T>>,
411{
412}
413
414unsafe impl<T> Sync for Stack<T>
415where
416 T: Sync,
417 T: Linked<Links<T>>,
418{
419}
420
421// === impl Links ===
422
423impl<T> Links<T> {
424 /// Returns new [`TransferStack`] links.
425 #[cfg(not(loom))]
426 #[must_use]
427 pub const fn new() -> Self {
428 Self {
429 next: UnsafeCell::new(None),
430 _unpin: PhantomPinned,
431 }
432 }
433
434 /// Returns new [`TransferStack`] links.
435 #[cfg(loom)]
436 #[must_use]
437 pub fn new() -> Self {
438 Self {
439 next: UnsafeCell::new(None),
440 _unpin: PhantomPinned,
441 }
442 }
443}
444
445/// # Safety
446///
447/// Types containing [`Links`] may be `Send`: the pointers within the `Links` may
448/// mutably alias another value, but the links can only be _accessed_ by the
449/// owner of the [`TransferStack`] itself, because the pointers are private. As
450/// long as [`TransferStack`] upholds its own invariants, `Links` should not
451/// make a type `!Send`.
452unsafe impl<T: Send> Send for Links<T> {}
453
454/// # Safety
455///
456/// Types containing [`Links`] may be `Send`: the pointers within the `Links` may
457/// mutably alias another value, but the links can only be _accessed_ by the
458/// owner of the [`TransferStack`] itself, because the pointers are private. As
459/// long as [`TransferStack`] upholds its own invariants, `Links` should not
460/// make a type `!Send`.
461unsafe impl<T: Sync> Sync for Links<T> {}
462
463impl<T> fmt::Debug for Links<T> {
464 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
465 f.write_str("transfer_stack::Links { ... }")
466 }
467}
468
469impl<T> Default for Links<T> {
470 fn default() -> Self {
471 Self::new()
472 }
473}
474
475#[cfg(test)]
476mod loom {
477 use super::*;
478 use crate::loom::{
479 self,
480 sync::{
481 atomic::{AtomicUsize, Ordering},
482 Arc,
483 },
484 thread,
485 };
486 use test_util::Entry;
487
488 #[test]
489 fn multithreaded_push() {
490 const PUSHES: i32 = 2;
491 loom::model(|| {
492 let stack = Arc::new(TransferStack::new());
493 let threads = Arc::new(AtomicUsize::new(2));
494 let thread1 = thread::spawn({
495 let stack = stack.clone();
496 let threads = threads.clone();
497 move || {
498 Entry::push_all(&stack, 1, PUSHES);
499 threads.fetch_sub(1, Ordering::Relaxed);
500 }
501 });
502
503 let thread2 = thread::spawn({
504 let stack = stack.clone();
505 let threads = threads.clone();
506 move || {
507 Entry::push_all(&stack, 2, PUSHES);
508 threads.fetch_sub(1, Ordering::Relaxed);
509 }
510 });
511
512 let mut seen = Vec::new();
513
514 loop {
515 seen.extend(stack.take_all().map(|entry| entry.val));
516
517 if threads.load(Ordering::Relaxed) == 0 {
518 break;
519 }
520
521 thread::yield_now();
522 }
523
524 seen.extend(stack.take_all().map(|entry| entry.val));
525
526 seen.sort();
527 assert_eq!(seen, vec![10, 11, 20, 21]);
528
529 thread1.join().unwrap();
530 thread2.join().unwrap();
531 })
532 }
533
534 #[test]
535 fn multithreaded_pop() {
536 const PUSHES: i32 = 2;
537 loom::model(|| {
538 let stack = Arc::new(TransferStack::new());
539 let thread1 = thread::spawn({
540 let stack = stack.clone();
541 move || Entry::push_all(&stack, 1, PUSHES)
542 });
543
544 let thread2 = thread::spawn({
545 let stack = stack.clone();
546 move || Entry::push_all(&stack, 2, PUSHES)
547 });
548
549 let thread3 = thread::spawn({
550 let stack = stack.clone();
551 move || stack.take_all().map(|entry| entry.val).collect::<Vec<_>>()
552 });
553
554 let seen_thread0 = stack.take_all().map(|entry| entry.val).collect::<Vec<_>>();
555 let seen_thread3 = thread3.join().unwrap();
556
557 thread1.join().unwrap();
558 thread2.join().unwrap();
559
560 let seen_thread0_final = stack.take_all().map(|entry| entry.val).collect::<Vec<_>>();
561
562 let mut all = dbg!(seen_thread0);
563 all.extend(dbg!(seen_thread3));
564 all.extend(dbg!(seen_thread0_final));
565
566 all.sort();
567 assert_eq!(all, vec![10, 11, 20, 21]);
568 })
569 }
570
571 #[test]
572 fn doesnt_leak() {
573 const PUSHES: i32 = 2;
574 loom::model(|| {
575 let stack = Arc::new(TransferStack::new());
576 let thread1 = thread::spawn({
577 let stack = stack.clone();
578 move || Entry::push_all(&stack, 1, PUSHES)
579 });
580
581 let thread2 = thread::spawn({
582 let stack = stack.clone();
583 move || Entry::push_all(&stack, 2, PUSHES)
584 });
585
586 tracing::info!("dropping stack");
587 drop(stack);
588
589 thread1.join().unwrap();
590 thread2.join().unwrap();
591 })
592 }
593
594 #[test]
595 fn take_all_doesnt_leak() {
596 const PUSHES: i32 = 2;
597 loom::model(|| {
598 let stack = Arc::new(TransferStack::new());
599 let thread1 = thread::spawn({
600 let stack = stack.clone();
601 move || Entry::push_all(&stack, 1, PUSHES)
602 });
603
604 let thread2 = thread::spawn({
605 let stack = stack.clone();
606 move || Entry::push_all(&stack, 2, PUSHES)
607 });
608
609 thread1.join().unwrap();
610 thread2.join().unwrap();
611
612 let take_all = stack.take_all();
613
614 tracing::info!("dropping stack");
615 drop(stack);
616
617 tracing::info!("dropping take_all");
618 drop(take_all);
619 })
620 }
621
622 #[test]
623 fn take_all_doesnt_leak_racy() {
624 const PUSHES: i32 = 2;
625 loom::model(|| {
626 let stack = Arc::new(TransferStack::new());
627 let thread1 = thread::spawn({
628 let stack = stack.clone();
629 move || Entry::push_all(&stack, 1, PUSHES)
630 });
631
632 let thread2 = thread::spawn({
633 let stack = stack.clone();
634 move || Entry::push_all(&stack, 2, PUSHES)
635 });
636
637 let take_all = stack.take_all();
638
639 thread1.join().unwrap();
640 thread2.join().unwrap();
641
642 tracing::info!("dropping stack");
643 drop(stack);
644
645 tracing::info!("dropping take_all");
646 drop(take_all);
647 })
648 }
649
650 #[test]
651 fn unsync() {
652 loom::model(|| {
653 let mut stack = Stack::<Entry>::new();
654 stack.push(Entry::new(1));
655 stack.push(Entry::new(2));
656 stack.push(Entry::new(3));
657 let mut take_all = stack.take_all();
658
659 for i in (1..=3).rev() {
660 assert_eq!(take_all.next().unwrap().val, i);
661 stack.push(Entry::new(10 + i));
662 }
663
664 let mut i = 11;
665 for entry in stack.take_all() {
666 assert_eq!(entry.val, i);
667 i += 1;
668 }
669 })
670 }
671
672 #[test]
673 fn unsync_doesnt_leak() {
674 loom::model(|| {
675 let mut stack = Stack::<Entry>::new();
676 stack.push(Entry::new(1));
677 stack.push(Entry::new(2));
678 stack.push(Entry::new(3));
679 })
680 }
681
682 #[test]
683 fn transfer_stack_is_empty() {
684 loom::model(|| {
685 let stack = TransferStack::<Entry>::new();
686 assert!(stack.is_empty(), "a new stack is empty");
687
688 stack.push(Entry::new(1));
689 assert!(!stack.is_empty(), "a stack with one element is not empty");
690
691 stack.push(Entry::new(2));
692 assert!(!stack.is_empty(), "a stack with two elements is not empty");
693
694 let taken = stack.take_all();
695 assert!(stack.is_empty(), "the stack is empty after `take_all`");
696 assert_eq!(taken.into_iter().count(), 2, "`take_all` took both elements");
697 })
698 }
699}
700
701#[cfg(test)]
702mod test {
703 use super::{test_util::Entry, *};
704
705 #[test]
706 fn stack_is_send_sync() {
707 crate::util::assert_send_sync::<TransferStack<Entry>>()
708 }
709
710 #[test]
711 fn links_are_send_sync() {
712 crate::util::assert_send_sync::<Links<Entry>>()
713 }
714}
715
716#[cfg(test)]
717pub(crate) mod test_util {
718 use super::*;
719 use crate::loom::alloc;
720 use core::pin::Pin;
721 use core::ptr;
722
723 #[pin_project::pin_project]
724 pub(crate) struct Entry {
725 #[pin]
726 links: Links<Entry>,
727 pub(crate) val: i32,
728 track: alloc::Track<()>,
729 }
730
731 // ----------------------------------------------------------------------
732 // Helper impls for `sorted_list`
733 impl PartialEq for Entry {
734 fn eq(&self, other: &Self) -> bool {
735 self.val.eq(&other.val)
736 }
737 }
738
739 impl Eq for Entry {}
740
741 impl PartialOrd for Entry {
742 fn partial_cmp(&self, other: &Self) -> Option<core::cmp::Ordering> {
743 Some(self.cmp(other))
744 }
745 }
746
747 impl Ord for Entry {
748 fn cmp(&self, other: &Self) -> core::cmp::Ordering {
749 self.val.cmp(&other.val)
750 }
751 }
752 // ----------------------------------------------------------------------
753
754 unsafe impl Linked<Links<Self>> for Entry {
755 type Handle = Pin<Box<Entry>>;
756
757 fn into_ptr(handle: Pin<Box<Entry>>) -> NonNull<Self> {
758 unsafe { NonNull::from(Box::leak(Pin::into_inner_unchecked(handle))) }
759 }
760
761 unsafe fn from_ptr(ptr: NonNull<Self>) -> Self::Handle {
762 // Safety: if this function is only called by the linked list
763 // implementation (and it is not intended for external use), we can
764 // expect that the `NonNull` was constructed from a reference which
765 // was pinned.
766 //
767 // If other callers besides `List`'s internals were to call this on
768 // some random `NonNull<Entry>`, this would not be the case, and
769 // this could be constructing an erroneous `Pin` from a referent
770 // that may not be pinned!
771 Pin::new_unchecked(Box::from_raw(ptr.as_ptr()))
772 }
773
774 unsafe fn links(target: NonNull<Self>) -> NonNull<Links<Self>> {
775 let links = ptr::addr_of_mut!((*target.as_ptr()).links);
776 // Safety: it's fine to use `new_unchecked` here; if the pointer that we
777 // offset to the `links` field is not null (which it shouldn't be, as we
778 // received it as a `NonNull`), the offset pointer should therefore also
779 // not be null.
780 NonNull::new_unchecked(links)
781 }
782 }
783
784 impl Entry {
785 pub(crate) fn new(val: i32) -> Pin<Box<Entry>> {
786 Box::pin(Entry {
787 links: Links::new(),
788 val,
789 track: alloc::Track::new(()),
790 })
791 }
792
793 pub(super) fn push_all(stack: &TransferStack<Self>, thread: i32, n: i32) {
794 for i in 0..n {
795 let entry = Self::new((thread * 10) + i);
796 stack.push(entry);
797 }
798 }
799 }
800}