sync: refactor intrusive linked list (#2279)

Allow storing the intrusive linked-list pointers in an arbitrary
location in the node. This is in preparation for using the linked list
in the scheduler.

In order to make using the intrusive linked list more flexible, a trait
is introduced to abstract mapping an entry to raw pointers and the next
/ prev pointers. This also pushes more unsafety onto the user.

1 files changed, 204 insertions, 177 deletions

diff --git a/tokio/src/util/linked_list.rs b/tokio/src/util/linked_list.rs
index 2e4d8d2d..57540c4a 100644
--- a/tokio/src/util/linked_list.rs
+++ b/tokio/src/util/linked_list.rs
@@ -4,95 +4,116 @@
 //! structure's APIs are `unsafe` as they require the caller to ensure the
 //! specified node is actually contained by the list.
 
-use core::cell::UnsafeCell;
-use core::marker::PhantomPinned;
-use core::pin::Pin;
 use core::ptr::NonNull;
 
-/// An intrusive linked list of nodes, where each node carries associated data
-/// of type `T`.
+/// An intrusive linked list.
+///
+/// Currently, the list is not emptied on drop. It is the caller's
+/// responsibility to ensure the list is empty before dropping it.
 #[derive(Debug)]
-pub(crate) struct LinkedList<T> {
-    head: Option<NonNull<Entry<T>>>,
-    tail: Option<NonNull<Entry<T>>>,
+pub(crate) struct LinkedList<T: Link> {
+    /// Linked list head
+    head: Option<NonNull<T::Target>>,
+
+    /// Linked list tail
+    tail: Option<NonNull<T::Target>>,
 }
 
-unsafe impl<T: Send> Send for LinkedList<T> {}
-unsafe impl<T: Sync> Sync for LinkedList<T> {}
+unsafe impl<T: Link> Send for LinkedList<T> where T::Target: Send {}
+unsafe impl<T: Link> Sync for LinkedList<T> where T::Target: Sync {}
+
+/// Defines how a type is tracked within a linked list.
+///
+/// In order to support storing a single type within multiple lists, accessing
+/// the list pointers is decoupled from the entry type.
+///
+/// # Safety
+///
+/// Implementations must guarantee that `Target` types are pinned in memory. In
+/// other words, when a node is inserted, the value will not be moved as long as
+/// it is stored in the list.
+pub(crate) unsafe trait Link {
+    /// Handle to the list entry.
+    ///
+    /// This is usually a pointer-ish type.
+    type Handle;
+
+    /// Node type
+    type Target;
+
+    /// Convert the handle to a raw pointer
+    ///
+    /// Consumes ownership of the handle.
+    fn to_raw(handle: Self::Handle) -> NonNull<Self::Target>;
+
+    /// Convert the raw pointer to a handle
+    unsafe fn from_raw(ptr: NonNull<Self::Target>) -> Self::Handle;
+
+    /// Return the pointers for a node
+    unsafe fn pointers(target: NonNull<Self::Target>) -> NonNull<Pointers<Self::Target>>;
+}
 
-/// A node which carries data of type `T` and is stored in an intrusive list.
+/// Previous / next pointers
 #[derive(Debug)]
-pub(crate) struct Entry<T> {
+pub(crate) struct Pointers<T> {
     /// The previous node in the list. null if there is no previous node.
-    prev: Option<NonNull<Entry<T>>>,
+    prev: Option<NonNull<T>>,
 
     /// The next node in the list. null if there is no previous node.
-    next: Option<NonNull<Entry<T>>>,
-
-    /// The data which is associated to this list item
-    data: UnsafeCell<T>,
-
-    /// Prevents `Entry`s from being `Unpin`. They may never be moved, since
-    /// the list semantics require addresses to be stable.
-    _pin: PhantomPinned,
+    next: Option<NonNull<T>>,
 }
 
-unsafe impl<T: Send> Send for Entry<T> {}
-unsafe impl<T: Sync> Sync for Entry<T> {}
+unsafe impl<T: Send> Send for Pointers<T> {}
+unsafe impl<T: Sync> Sync for Pointers<T> {}
 
-impl<T> LinkedList<T> {
+// ===== impl LinkedList =====
+
+impl<T: Link> LinkedList<T> {
     /// Creates an empty linked list
-    pub(crate) fn new() -> Self {
+    pub(crate) fn new() -> LinkedList<T> {
         LinkedList {
             head: None,
             tail: None,
         }
     }
 
-    /// Adds an item to the back of the linked list.
-    ///
-    /// # Safety
-    ///
-    /// The function is only safe as long as valid pointers are stored inside
-    /// the linked list.
-    pub(crate) unsafe fn push_front(&mut self, entry: Pin<&mut Entry<T>>) {
-        let mut entry: NonNull<Entry<T>> = entry.get_unchecked_mut().into();
+    /// Adds an element first in the list.
+    pub(crate) fn push_front(&mut self, val: T::Handle) {
+        let ptr = T::to_raw(val);
 
-        entry.as_mut().next = self.head;
-        entry.as_mut().prev = None;
+        unsafe {
+            T::pointers(ptr).as_mut().next = self.head;
+            T::pointers(ptr).as_mut().prev = None;
 
-        if let Some(head) = &mut self.head {
-            head.as_mut().prev = Some(entry);
-        }
+            if let Some(head) = self.head {
+                T::pointers(head).as_mut().prev = Some(ptr);
+            }
 
-        self.head = Some(entry);
+            self.head = Some(ptr);
 
-        if self.tail.is_none() {
-            self.tail = Some(entry);
+            if self.tail.is_none() {
+                self.tail = Some(ptr);
+            }
         }
     }
 
-    /// Removes the first element and returns it, or `None` if the list is empty.
-    ///
-    /// The function is safe as the lifetime of the entry is bound to `&mut
-    /// self`.
-    pub(crate) fn pop_back(&mut self) -> Option<Pin<&mut T>> {
+    /// Removes the last element from a list and returns it, or None if it is
+    /// empty.
+    pub(crate) fn pop_back(&mut self) -> Option<T::Handle> {
         unsafe {
-            let mut last = self.tail?;
-            self.tail = last.as_ref().prev;
+            let last = self.tail?;
+            self.tail = T::pointers(last).as_ref().prev;
 
-            if let Some(mut prev) = last.as_mut().prev {
-                prev.as_mut().next = None;
+            if let Some(prev) = T::pointers(last).as_ref().prev {
+                T::pointers(prev).as_mut().next = None;
             } else {
                 self.head = None
             }
 
-            last.as_mut().prev = None;
-            last.as_mut().next = None;
+            T::pointers(last).as_mut().prev = None;
+            T::pointers(last).as_mut().next = None;
 
-            let val = &mut *last.as_mut().data.get();
-
-            Some(Pin::new_unchecked(val))
+            Some(T::from_raw(last))
         }
     }
 
@@ -106,60 +127,53 @@ impl<T> LinkedList<T> {
         true
     }
 
-    /// Removes the given item from the linked list.
+    /// Removes the specified node from the list
     ///
     /// # Safety
     ///
-    /// The caller **must** ensure that `entry` is currently contained by
-    /// `self`.
-    pub(crate) unsafe fn remove(&mut self, entry: Pin<&mut Entry<T>>) -> bool {
-        let mut entry = NonNull::from(entry.get_unchecked_mut());
-
-        if let Some(mut prev) = entry.as_mut().prev {
-            debug_assert_eq!(prev.as_ref().next, Some(entry));
-            prev.as_mut().next = entry.as_ref().next;
+    /// The caller **must** ensure that `node` is currently contained by
+    /// `self` or not contained by any other list.
+    pub(crate) unsafe fn remove(&mut self, node: NonNull<T::Target>) -> bool {
+        if let Some(prev) = T::pointers(node).as_ref().prev {
+            debug_assert_eq!(T::pointers(prev).as_ref().next, Some(node));
+            T::pointers(prev).as_mut().next = T::pointers(node).as_ref().next;
         } else {
-            if self.head != Some(entry) {
+            if self.head != Some(node) {
                 return false;
             }
 
-            self.head = entry.as_ref().next;
+            self.head = T::pointers(node).as_ref().next;
         }
 
-        if let Some(mut next) = entry.as_mut().next {
-            debug_assert_eq!(next.as_ref().prev, Some(entry));
-            next.as_mut().prev = entry.as_ref().prev;
+        if let Some(next) = T::pointers(node).as_ref().next {
+            debug_assert_eq!(T::pointers(next).as_ref().prev, Some(node));
+            T::pointers(next).as_mut().prev = T::pointers(node).as_ref().prev;
         } else {
             // This might be the last item in the list
-            if self.tail != Some(entry) {
+            if self.tail != Some(node) {
                 return false;
             }
 
-            self.tail = entry.as_ref().prev;
+            self.tail = T::pointers(node).as_ref().prev;
         }
 
-        entry.as_mut().next = None;
-        entry.as_mut().prev = None;
+        T::pointers(node).as_mut().next = None;
+        T::pointers(node).as_mut().prev = None;
 
         true
     }
 }
 
-impl<T> Entry<T> {
-    /// Creates a new node with the associated data
-    pub(crate) fn new(data: T) -> Entry<T> {
-        Entry {
+// ===== impl Pointers =====
+
+impl<T> Pointers<T> {
+    /// Create a new set of empty pointers
+    pub(crate) fn new() -> Pointers<T> {
+        Pointers {
             prev: None,
             next: None,
-            data: UnsafeCell::new(data),
-            _pin: PhantomPinned,
         }
     }
-
-    /// Get a raw pointer to the inner data
-    pub(crate) fn get(&self) -> *mut T {
-        self.data.get()
-    }
 }
 
 #[cfg(test)]
@@ -167,53 +181,84 @@ impl<T> Entry<T> {
 mod tests {
     use super::*;
 
-    fn collect_list<T: Copy>(list: &mut LinkedList<T>) -> Vec<T> {
+    use std::pin::Pin;
+
+    struct Entry {
+        pointers: Pointers<Entry>,
+        val: i32,
+    }
+
+    unsafe impl<'a> Link for &'a Entry {
+        type Handle = Pin<&'a Entry>;
+        type Target = Entry;
+
+        fn to_raw(handle: Pin<&'_ Entry>) -> NonNull<Entry> {
+            NonNull::from(handle.get_ref())
+        }
+
+        unsafe fn from_raw(ptr: NonNull<Entry>) -> Pin<&'a Entry> {
+            Pin::new(&*ptr.as_ptr())
+        }
+
+        unsafe fn pointers(mut target: NonNull<Entry>) -> NonNull<Pointers<Entry>> {
+            NonNull::from(&mut target.as_mut().pointers)
+        }
+    }
+
+    fn entry(val: i32) -> Pin<Box<Entry>> {
+        Box::pin(Entry {
+            pointers: Pointers::new(),
+            val,
+        })
+    }
+
+    fn ptr(r: &Pin<Box<Entry>>) -> NonNull<Entry> {
+        r.as_ref().get_ref().into()
+    }
+
+    fn collect_list(list: &mut LinkedList<&'_ Entry>) -> Vec<i32> {
         let mut ret = vec![];
 
-        while let Some(v) = list.pop_back() {
-            ret.push(*v);
+        while let Some(entry) = list.pop_back() {
+            ret.push(entry.val);
         }
 
         ret
     }
 
-    unsafe fn push_all(list: &mut LinkedList<i32>, entries: &mut [Pin<&mut Entry<i32>>]) {
-        for entry in entries.iter_mut() {
-            list.push_front(entry.as_mut());
+    fn push_all<'a>(list: &mut LinkedList<&'a Entry>, entries: &[Pin<&'a Entry>]) {
+        for entry in entries.iter() {
+            list.push_front(*entry);
         }
     }
 
     macro_rules! assert_clean {
         ($e:ident) => {{
-            assert!($e.next.is_none());
-            assert!($e.prev.is_none());
+            assert!($e.pointers.next.is_none());
+            assert!($e.pointers.prev.is_none());
         }};
     }
 
     macro_rules! assert_ptr_eq {
         ($a:expr, $b:expr) => {{
             // Deal with mapping a Pin<&mut T> -> Option<NonNull<T>>
-            assert_eq!(Some($a.as_mut().get_unchecked_mut().into()), $b)
+            assert_eq!(Some($a.as_ref().get_ref().into()), $b)
         }};
     }
 
     #[test]
     fn push_and_drain() {
-        pin! {
-            let a = Entry::new(5);
-            let b = Entry::new(7);
-            let c = Entry::new(31);
-        }
+        let a = entry(5);
+        let b = entry(7);
+        let c = entry(31);
 
         let mut list = LinkedList::new();
         assert!(list.is_empty());
 
-        unsafe {
-            list.push_front(a);
-            assert!(!list.is_empty());
-            list.push_front(b);
-            list.push_front(c);
-        }
+        list.push_front(a.as_ref());
+        assert!(!list.is_empty());
+        list.push_front(b.as_ref());
+        list.push_front(c.as_ref());
 
         let items: Vec<i32> = collect_list(&mut list);
         assert_eq!([5, 7, 31].to_vec(), items);
@@ -223,27 +268,21 @@ mod tests {
 
     #[test]
     fn push_pop_push_pop() {
-        pin! {
-            let a = Entry::new(5);
-            let b = Entry::new(7);
-        }
+        let a = entry(5);
+        let b = entry(7);
 
-        let mut list = LinkedList::new();
+        let mut list = LinkedList::<&Entry>::new();
 
-        unsafe {
-            list.push_front(a);
-        }
+        list.push_front(a.as_ref());
 
-        let v = list.pop_back().unwrap();
-        assert_eq!(5, *v);
+        let entry = list.pop_back().unwrap();
+        assert_eq!(5, entry.val);
         assert!(list.is_empty());
 
-        unsafe {
-            list.push_front(b);
-        }
+        list.push_front(b.as_ref());
 
-        let v = list.pop_back().unwrap();
-        assert_eq!(7, *v);
+        let entry = list.pop_back().unwrap();
+        assert_eq!(7, entry.val);
 
         assert!(list.is_empty());
         assert!(list.pop_back().is_none());
@@ -251,33 +290,31 @@ mod tests {
 
     #[test]
     fn remove_by_address() {
-        pin! {
-            let a = Entry::new(5);
-            let b = Entry::new(7);
-            let c = Entry::new(31);
-        }
+        let a = entry(5);
+        let b = entry(7);
+        let c = entry(31);
 
         unsafe {
             // Remove first
             let mut list = LinkedList::new();
 
-            push_all(&mut list, &mut [c.as_mut(), b.as_mut(), a.as_mut()]);
-            assert!(list.remove(a.as_mut()));
+            push_all(&mut list, &[c.as_ref(), b.as_ref(), a.as_ref()]);
+            assert!(list.remove(ptr(&a)));
             assert_clean!(a);
             // `a` should be no longer there and can't be removed twice
-            assert!(!list.remove(a.as_mut()));
+            assert!(!list.remove(ptr(&a)));
             assert!(!list.is_empty());
 
-            assert!(list.remove(b.as_mut()));
+            assert!(list.remove(ptr(&b)));
             assert_clean!(b);
             // `b` should be no longer there and can't be removed twice
-            assert!(!list.remove(b.as_mut()));
+            assert!(!list.remove(ptr(&b)));
             assert!(!list.is_empty());
 
-            assert!(list.remove(c.as_mut()));
+            assert!(list.remove(ptr(&c)));
             assert_clean!(c);
             // `b` should be no longer there and can't be removed twice
-            assert!(!list.remove(c.as_mut()));
+            assert!(!list.remove(ptr(&c)));
             assert!(list.is_empty());
         }
 
@@ -285,14 +322,14 @@ mod tests {
             // Remove middle
             let mut list = LinkedList::new();
 
-            push_all(&mut list, &mut [c.as_mut(), b.as_mut(), a.as_mut()]);
+            push_all(&mut list, &[c.as_ref(), b.as_ref(), a.as_ref()]);
 
-            assert!(list.remove(a.as_mut()));
+            assert!(list.remove(ptr(&a)));
             assert_clean!(a);
 
             assert_ptr_eq!(b, list.head);
-            assert_ptr_eq!(c, b.next);
-            assert_ptr_eq!(b, c.prev);
+            assert_ptr_eq!(c, b.pointers.next);
+            assert_ptr_eq!(b, c.pointers.prev);
 
             let items = collect_list(&mut list);
             assert_eq!([31, 7].to_vec(), items);
@@ -302,13 +339,13 @@ mod tests {
             // Remove middle
             let mut list = LinkedList::new();
 
-            push_all(&mut list, &mut [c.as_mut(), b.as_mut(), a.as_mut()]);
+            push_all(&mut list, &[c.as_ref(), b.as_ref(), a.as_ref()]);
 
-            assert!(list.remove(b.as_mut()));
+            assert!(list.remove(ptr(&b)));
             assert_clean!(b);
 
-            assert_ptr_eq!(c, a.next);
-            assert_ptr_eq!(a, c.prev);
+            assert_ptr_eq!(c, a.pointers.next);
+            assert_ptr_eq!(a, c.pointers.prev);
 
             let items = collect_list(&mut list);
             assert_eq!([31, 5].to_vec(), items);
@@ -319,12 +356,12 @@ mod tests {
             // Remove middle
             let mut list = LinkedList::new();
 
-            push_all(&mut list, &mut [c.as_mut(), b.as_mut(), a.as_mut()]);
+            push_all(&mut list, &[c.as_ref(), b.as_ref(), a.as_ref()]);
 
-            assert!(list.remove(c.as_mut()));
+            assert!(list.remove(ptr(&c)));
             assert_clean!(c);
 
-            assert!(b.next.is_none());
+            assert!(b.pointers.next.is_none());
             assert_ptr_eq!(b, list.tail);
 
             let items = collect_list(&mut list);
@@ -335,20 +372,20 @@ mod tests {
             // Remove first of two
             let mut list = LinkedList::new();
 
-            push_all(&mut list, &mut [b.as_mut(), a.as_mut()]);
+            push_all(&mut list, &[b.as_ref(), a.as_ref()]);
 
-            assert!(list.remove(a.as_mut()));
+            assert!(list.remove(ptr(&a)));
 
             assert_clean!(a);
 
             // a should be no longer there and can't be removed twice
-            assert!(!list.remove(a.as_mut()));
+            assert!(!list.remove(ptr(&a)));
 
             assert_ptr_eq!(b, list.head);
             assert_ptr_eq!(b, list.tail);
 
-            assert!(b.next.is_none());
-            assert!(b.prev.is_none());
+            assert!(b.pointers.next.is_none());
+            assert!(b.pointers.prev.is_none());
 
             let items = collect_list(&mut list);
             assert_eq!([7].to_vec(), items);
@@ -358,17 +395,17 @@ mod tests {
             // Remove last of two
             let mut list = LinkedList::new();
 
-            push_all(&mut list, &mut [b.as_mut(), a.as_mut()]);
+            push_all(&mut list, &[b.as_ref(), a.as_ref()]);
 
-            assert!(list.remove(b.as_mut()));
+            assert!(list.remove(ptr(&b)));
 
             assert_clean!(b);
 
             assert_ptr_eq!(a, list.head);
             assert_ptr_eq!(a, list.tail);
 
-            assert!(a.next.is_none());
-            assert!(a.prev.is_none());
+            assert!(a.pointers.next.is_none());
+            assert!(a.pointers.prev.is_none());
 
             let items = collect_list(&mut list);
             assert_eq!([5].to_vec(), items);
@@ -378,9 +415,9 @@ mod tests {
             // Remove last item
             let mut list = LinkedList::new();
 
-            push_all(&mut list, &mut [a.as_mut()]);
+            push_all(&mut list, &[a.as_ref()]);
 
-            assert!(list.remove(a.as_mut()));
+            assert!(list.remove(ptr(&a)));
             assert_clean!(a);
 
             assert!(list.head.is_none());
@@ -391,12 +428,12 @@ mod tests {
 
         unsafe {
             // Remove missing
-            let mut list = LinkedList::new();
+            let mut list = LinkedList::<&Entry>::new();
 
-            list.push_front(b.as_mut());
-            list.push_front(a.as_mut());
+            list.push_front(b.as_ref());
+            list.push_front(a.as_ref());
 
-            assert!(!list.remove(c.as_mut()));
+            assert!(!list.remove(ptr(&c)));
         }
     }
 
@@ -427,23 +464,18 @@ mod tests {
             })
             .collect::<Vec<_>>();
 
-        let mut next = 0;
-        let mut ll = LinkedList::new();
-        let mut entries = VecDeque::new();
+        let mut ll = LinkedList::<&Entry>::new();
         let mut reference = VecDeque::new();
 
-        for op in ops {
+        let entries: Vec<_> = (0..ops.len()).map(|i| entry(i as i32)).collect();
+
+        for (i, op) in ops.iter().enumerate() {
             match op {
                 Op::Push => {
-                    let v = next;
-                    next += 1;
+                    reference.push_front(i as i32);
+                    assert_eq!(entries[i].val, i as i32);
 
-                    reference.push_front(v);
-                    entries.push_front(Box::pin(Entry::new(v)));
-
-                    unsafe {
-                        ll.push_front(entries.front_mut().unwrap().as_mut());
-                    }
+                    ll.push_front(entries[i].as_ref());
                 }
                 Op::Pop => {
                     if reference.is_empty() {
@@ -452,8 +484,7 @@ mod tests {
                     }
 
                     let v = reference.pop_back();
-                    assert_eq!(v, ll.pop_back().map(|v| *v));
-                    entries.pop_back();
+                    assert_eq!(v, ll.pop_back().map(|v| v.val));
                 }
                 Op::Remove(n) => {
                     if reference.is_empty() {
@@ -462,15 +493,11 @@ mod tests {
                     }
 
                     let idx = n % reference.len();
+                    let v = reference.remove(idx).unwrap();
 
                     unsafe {
-                        assert!(ll.remove(entries[idx].as_mut()));
+                        assert!(ll.remove(ptr(&entries[v as usize])));
                     }
-
-                    let v = reference.remove(idx).unwrap();
-                    assert_eq!(v, unsafe { *entries[idx].get() });
-
-                    entries.remove(idx);
                 }
             }
         }