// SPDX-License-Identifier: GPL-2.0 // Copyright (C) 2024 Google LLC. //! A linked list implementation. use crate::sync::ArcBorrow;use crate::types::Opaque;use core::iter::{DoubleEndedIterator, FusedIterator};use core::marker::PhantomData;use core::ptr;use pin_init::PinInit; mod impl_list_item_mod;pub use self::impl_list_item_mod::{ impl_has_list_links, impl_has_list_links_self_ptr, impl_list_item, HasListLinks, HasSelfPtr,}; mod arc;pub use self::arc::{impl_list_arc_safe, AtomicTracker, ListArc, ListArcSafe, TryNewListArc}; mod arc_field;pub use self::arc_field::{define_list_arc_field_getter, ListArcField}; /// A linked list.////// All elements in this linked list will be [`ListArc`] references to the value. Since a value can/// only have one `ListArc` (for each pair of prev/next pointers), this ensures that the same/// prev/next pointers are not used for several linked lists.////// # Invariants////// * If the list is empty, then `first` is null. Otherwise, `first` points at the `ListLinks`/// field of the first element in the list./// * All prev/next pointers in `ListLinks` fields of items in the list are valid and form a cycle./// * For every item in the list, the list owns the associated [`ListArc`] reference and has/// exclusive access to the `ListLinks` field.////// # Examples////// ```/// use kernel::list::*;////// #[pin_data]/// struct BasicItem {/// value: i32,/// #[pin]/// links: ListLinks,/// }////// impl BasicItem {/// fn new(value: i32) -> Result<ListArc<Self>> {/// ListArc::pin_init(try_pin_init!(Self {/// value,/// links <- ListLinks::new(),/// }), GFP_KERNEL)/// }/// }////// impl_list_arc_safe! {/// impl ListArcSafe<0> for BasicItem { untracked; }/// }/// impl_list_item! {/// impl ListItem<0> for BasicItem { using ListLinks { self.links }; }/// }////// // Create a new empty list./// let mut list = List::new();/// {/// assert!(list.is_empty());/// }////// // Insert 3 elements using `push_back()`./// list.push_back(BasicItem::new(15)?);/// list.push_back(BasicItem::new(10)?);/// list.push_back(BasicItem::new(30)?);////// // Iterate over the list to verify the nodes were inserted correctly./// // [15, 10, 30]/// {/// let mut iter = list.iter();/// assert_eq!(iter.next().ok_or(EINVAL)?.value, 15);/// assert_eq!(iter.next().ok_or(EINVAL)?.value, 10);/// assert_eq!(iter.next().ok_or(EINVAL)?.value, 30);/// assert!(iter.next().is_none());////// // Verify the length of the list./// assert_eq!(list.iter().count(), 3);/// }////// // Pop the items from the list using `pop_back()` and verify the content./// {/// assert_eq!(list.pop_back().ok_or(EINVAL)?.value, 30);/// assert_eq!(list.pop_back().ok_or(EINVAL)?.value, 10);/// assert_eq!(list.pop_back().ok_or(EINVAL)?.value, 15);/// }////// // Insert 3 elements using `push_front()`./// list.push_front(BasicItem::new(15)?);/// list.push_front(BasicItem::new(10)?);/// list.push_front(BasicItem::new(30)?);////// // Iterate over the list to verify the nodes were inserted correctly./// // [30, 10, 15]/// {/// let mut iter = list.iter();/// assert_eq!(iter.next().ok_or(EINVAL)?.value, 30);/// assert_eq!(iter.next().ok_or(EINVAL)?.value, 10);/// assert_eq!(iter.next().ok_or(EINVAL)?.value, 15);/// assert!(iter.next().is_none());////// // Verify the length of the list./// assert_eq!(list.iter().count(), 3);/// }////// // Pop the items from the list using `pop_front()` and verify the content./// {/// assert_eq!(list.pop_front().ok_or(EINVAL)?.value, 30);/// assert_eq!(list.pop_front().ok_or(EINVAL)?.value, 10);/// }////// // Push `list2` to `list` through `push_all_back()`./// // list: [15]/// // list2: [25, 35]/// {/// let mut list2 = List::new();/// list2.push_back(BasicItem::new(25)?);/// list2.push_back(BasicItem::new(35)?);////// list.push_all_back(&mut list2);////// // list: [15, 25, 35]/// // list2: []/// let mut iter = list.iter();/// assert_eq!(iter.next().ok_or(EINVAL)?.value, 15);/// assert_eq!(iter.next().ok_or(EINVAL)?.value, 25);/// assert_eq!(iter.next().ok_or(EINVAL)?.value, 35);/// assert!(iter.next().is_none());/// assert!(list2.is_empty());/// }/// # Result::<(), Error>::Ok(())/// ```pub struct List<T: ?Sized + ListItem<ID>, const ID: u64 = 0> { first: *mut ListLinksFields, _ty: PhantomData<ListArc<T, ID>>,} // SAFETY: This is a container of `ListArc<T, ID>`, and access to the container allows the same// type of access to the `ListArc<T, ID>` elements.unsafe impl<T, const ID: u64> Send for List<T, ID>where ListArc<T, ID>: Send, T: ?Sized + ListItem<ID>,{}// SAFETY: This is a container of `ListArc<T, ID>`, and access to the container allows the same// type of access to the `ListArc<T, ID>` elements.unsafe impl<T, const ID: u64> Sync for List<T, ID>where ListArc<T, ID>: Sync, T: ?Sized + ListItem<ID>,{} /// Implemented by types where a [`ListArc<Self>`] can be inserted into a [`List`].////// # Safety////// Implementers must ensure that they provide the guarantees documented on methods provided by/// this trait.////// [`ListArc<Self>`]: ListArcpub unsafe trait ListItem<const ID: u64 = 0>: ListArcSafe<ID> { /// Views the [`ListLinks`] for this value. /// /// # Guarantees /// /// If there is a previous call to `prepare_to_insert` and there is no call to `post_remove` /// since the most recent such call, then this returns the same pointer as the one returned by /// the most recent call to `prepare_to_insert`. /// /// Otherwise, the returned pointer points at a read-only [`ListLinks`] with two null pointers. /// /// # Safety /// /// The provided pointer must point at a valid value. (It need not be in an `Arc`.) unsafe fn view_links(me: *const Self) -> *mut ListLinks<ID>; /// View the full value given its [`ListLinks`] field. /// /// Can only be used when the value is in a list. /// /// # Guarantees /// /// * Returns the same pointer as the one passed to the most recent call to `prepare_to_insert`. /// * The returned pointer is valid until the next call to `post_remove`. /// /// # Safety /// /// * The provided pointer must originate from the most recent call to `prepare_to_insert`, or /// from a call to `view_links` that happened after the most recent call to /// `prepare_to_insert`. /// * Since the most recent call to `prepare_to_insert`, the `post_remove` method must not have /// been called. unsafe fn view_value(me: *mut ListLinks<ID>) -> *const Self; /// This is called when an item is inserted into a [`List`]. /// /// # Guarantees /// /// The caller is granted exclusive access to the returned [`ListLinks`] until `post_remove` is /// called. /// /// # Safety /// /// * The provided pointer must point at a valid value in an [`Arc`]. /// * Calls to `prepare_to_insert` and `post_remove` on the same value must alternate. /// * The caller must own the [`ListArc`] for this value. /// * The caller must not give up ownership of the [`ListArc`] unless `post_remove` has been /// called after this call to `prepare_to_insert`. /// /// [`Arc`]: crate::sync::Arc unsafe fn prepare_to_insert(me: *const Self) -> *mut ListLinks<ID>; /// This undoes a previous call to `prepare_to_insert`. /// /// # Guarantees /// /// The returned pointer is the pointer that was originally passed to `prepare_to_insert`. /// /// # Safety /// /// The provided pointer must be the pointer returned by the most recent call to /// `prepare_to_insert`. unsafe fn post_remove(me: *mut ListLinks<ID>) -> *const Self;} #[repr(C)]#[derive(Copy, Clone)]struct ListLinksFields { next: *mut ListLinksFields, prev: *mut ListLinksFields,} /// The prev/next pointers for an item in a linked list.////// # Invariants////// The fields are null if and only if this item is not in a list.#[repr(transparent)]pub struct ListLinks<const ID: u64 = 0> { // This type is `!Unpin` for aliasing reasons as the pointers are part of an intrusive linked // list. inner: Opaque<ListLinksFields>,} // SAFETY: The only way to access/modify the pointers inside of `ListLinks<ID>` is via holding the// associated `ListArc<T, ID>`. Since that type correctly implements `Send`, it is impossible to// move this an instance of this type to a different thread if the pointees are `!Send`.unsafe impl<const ID: u64> Send for ListLinks<ID> {}// SAFETY: The type is opaque so immutable references to a ListLinks are useless. Therefore, it's// okay to have immutable access to a ListLinks from several threads at once.unsafe impl<const ID: u64> Sync for ListLinks<ID> {} impl<const ID: u64> ListLinks<ID> { /// Creates a new initializer for this type. pub fn new() -> impl PinInit<Self> { // INVARIANT: Pin-init initializers can't be used on an existing `Arc`, so this value will // not be constructed in an `Arc` that already has a `ListArc`. ListLinks { inner: Opaque::new(ListLinksFields { prev: ptr::null_mut(), next: ptr::null_mut(), }), } } /// # Safety /// /// `me` must be dereferenceable. #[inline] unsafe fn fields(me: *mut Self) -> *mut ListLinksFields { // SAFETY: The caller promises that the pointer is valid. unsafe { Opaque::cast_into(ptr::addr_of!((*me).inner)) } } /// # Safety /// /// `me` must be dereferenceable. #[inline] unsafe fn from_fields(me: *mut ListLinksFields) -> *mut Self { me.cast() }} /// Similar to [`ListLinks`], but also contains a pointer to the full value.////// This type can be used instead of [`ListLinks`] to support lists with trait objects.#[repr(C)]pub struct ListLinksSelfPtr<T: ?Sized, const ID: u64 = 0> { /// The `ListLinks` field inside this value. /// /// This is public so that it can be used with `impl_has_list_links!`. pub inner: ListLinks<ID>, // UnsafeCell is not enough here because we use `Opaque::uninit` as a dummy value, and // `ptr::null()` doesn't work for `T: ?Sized`. self_ptr: Opaque<*const T>,} // SAFETY: The fields of a ListLinksSelfPtr can be moved across thread boundaries.unsafe impl<T: ?Sized + Send, const ID: u64> Send for ListLinksSelfPtr<T, ID> {}// SAFETY: The type is opaque so immutable references to a ListLinksSelfPtr are useless. Therefore,// it's okay to have immutable access to a ListLinks from several threads at once.//// Note that `inner` being a public field does not prevent this type from being opaque, since// `inner` is a opaque type.unsafe impl<T: ?Sized + Sync, const ID: u64> Sync for ListLinksSelfPtr<T, ID> {} impl<T: ?Sized, const ID: u64> ListLinksSelfPtr<T, ID> { /// Creates a new initializer for this type. pub fn new() -> impl PinInit<Self> { // INVARIANT: Pin-init initializers can't be used on an existing `Arc`, so this value will // not be constructed in an `Arc` that already has a `ListArc`. Self { inner: ListLinks { inner: Opaque::new(ListLinksFields { prev: ptr::null_mut(), next: ptr::null_mut(), }), }, self_ptr: Opaque::uninit(), } } /// Returns a pointer to the self pointer. /// /// # Safety /// /// The provided pointer must point at a valid struct of type `Self`. pub unsafe fn raw_get_self_ptr(me: *const Self) -> *const Opaque<*const T> { // SAFETY: The caller promises that the pointer is valid. unsafe { ptr::addr_of!((*me).self_ptr) } }} impl<T: ?Sized + ListItem<ID>, const ID: u64> List<T, ID> { /// Creates a new empty list. pub const fn new() -> Self { Self { first: ptr::null_mut(), _ty: PhantomData, } } /// Returns whether this list is empty. pub fn is_empty(&self) -> bool { self.first.is_null() } /// Inserts `item` before `next` in the cycle. /// /// Returns a pointer to the newly inserted element. Never changes `self.first` unless the list /// is empty. /// /// # Safety /// /// * `next` must be an element in this list or null. /// * if `next` is null, then the list must be empty. unsafe fn insert_inner( &mut self, item: ListArc<T, ID>, next: *mut ListLinksFields, ) -> *mut ListLinksFields { let raw_item = ListArc::into_raw(item); // SAFETY: // * We just got `raw_item` from a `ListArc`, so it's in an `Arc`. // * Since we have ownership of the `ListArc`, `post_remove` must have been called after // the most recent call to `prepare_to_insert`, if any. // * We own the `ListArc`. // * Removing items from this list is always done using `remove_internal_inner`, which // calls `post_remove` before giving up ownership. let list_links = unsafe { T::prepare_to_insert(raw_item) }; // SAFETY: We have not yet called `post_remove`, so `list_links` is still valid. let item = unsafe { ListLinks::fields(list_links) }; // Check if the list is empty. if next.is_null() { // SAFETY: The caller just gave us ownership of these fields. // INVARIANT: A linked list with one item should be cyclic. unsafe { (*item).next = item; (*item).prev = item; } self.first = item; } else { // SAFETY: By the type invariant, this pointer is valid or null. We just checked that // it's not null, so it must be valid. let prev = unsafe { (*next).prev }; // SAFETY: Pointers in a linked list are never dangling, and the caller just gave us // ownership of the fields on `item`. // INVARIANT: This correctly inserts `item` between `prev` and `next`. unsafe { (*item).next = next; (*item).prev = prev; (*prev).next = item; (*next).prev = item; } } item } /// Add the provided item to the back of the list. pub fn push_back(&mut self, item: ListArc<T, ID>) { // SAFETY: // * `self.first` is null or in the list. // * `self.first` is only null if the list is empty. unsafe { self.insert_inner(item, self.first) }; } /// Add the provided item to the front of the list. pub fn push_front(&mut self, item: ListArc<T, ID>) { // SAFETY: // * `self.first` is null or in the list. // * `self.first` is only null if the list is empty. let new_elem = unsafe { self.insert_inner(item, self.first) }; // INVARIANT: `new_elem` is in the list because we just inserted it. self.first = new_elem; } /// Removes the last item from this list. pub fn pop_back(&mut self) -> Option<ListArc<T, ID>> { if self.is_empty() { return None; } // SAFETY: We just checked that the list is not empty. let last = unsafe { (*self.first).prev }; // SAFETY: The last item of this list is in this list. Some(unsafe { self.remove_internal(last) }) } /// Removes the first item from this list. pub fn pop_front(&mut self) -> Option<ListArc<T, ID>> { if self.is_empty() { return None; } // SAFETY: The first item of this list is in this list. Some(unsafe { self.remove_internal(self.first) }) } /// Removes the provided item from this list and returns it. /// /// This returns `None` if the item is not in the list. (Note that by the safety requirements, /// this means that the item is not in any list.) /// /// # Safety /// /// `item` must not be in a different linked list (with the same id). pub unsafe fn remove(&mut self, item: &T) -> Option<ListArc<T, ID>> { // SAFETY: TODO. let mut item = unsafe { ListLinks::fields(T::view_links(item)) }; // SAFETY: The user provided a reference, and reference are never dangling. // // As for why this is not a data race, there are two cases: // // * If `item` is not in any list, then these fields are read-only and null. // * If `item` is in this list, then we have exclusive access to these fields since we // have a mutable reference to the list. // // In either case, there's no race. let ListLinksFields { next, prev } = unsafe { *item }; debug_assert_eq!(next.is_null(), prev.is_null()); if !next.is_null() { // This is really a no-op, but this ensures that `item` is a raw pointer that was // obtained without going through a pointer->reference->pointer conversion roundtrip. // This ensures that the list is valid under the more restrictive strict provenance // ruleset. // // SAFETY: We just checked that `next` is not null, and it's not dangling by the // list invariants. unsafe { debug_assert_eq!(item, (*next).prev); item = (*next).prev; } // SAFETY: We just checked that `item` is in a list, so the caller guarantees that it // is in this list. The pointers are in the right order. Some(unsafe { self.remove_internal_inner(item, next, prev) }) } else { None } } /// Removes the provided item from the list. /// /// # SafetyLines 1–500 of 1083. Load more
// SPDX-License-Identifier: GPL-2.0 // Copyright (C) 2024 Google LLC. //! A linked list implementation. use crate::sync::ArcBorrow; use crate::types::Opaque; use core::iter::{DoubleEndedIterator, FusedIterator}; use core::marker::PhantomData; use core::ptr; use pin_init::PinInit; mod impl_list_item_mod; pub use self::impl_list_item_mod::{ impl_has_list_links, impl_has_list_links_self_ptr, impl_list_item, HasListLinks, HasSelfPtr, }; mod arc; pub use self::arc::{impl_list_arc_safe, AtomicTracker, ListArc, ListArcSafe, TryNewListArc}; mod arc_field; pub use self::arc_field::{define_list_arc_field_getter, ListArcField}; /// A linked list. /// /// All elements in this linked list will be [`ListArc`] references to the value. Since a value can /// only have one `ListArc` (for each pair of prev/next pointers), this ensures that the same /// prev/next pointers are not used for several linked lists. /// /// # Invariants /// /// * If the list is empty, then `first` is null. Otherwise, `first` points at the `ListLinks` /// field of the first element in the list. /// * All prev/next pointers in `ListLinks` fields of items in the list are valid and form a cycle. /// * For every item in the list, the list owns the associated [`ListArc`] reference and has /// exclusive access to the `ListLinks` field. /// /// # Examples /// /// ``` /// use kernel::list::*; /// /// #[pin_data] /// struct BasicItem { /// value: i32, /// #[pin] /// links: ListLinks, /// } /// /// impl BasicItem { /// fn new(value: i32) -> Result<ListArc<Self>> { /// ListArc::pin_init(try_pin_init!(Self { /// value, /// links <- ListLinks::new(), /// }), GFP_KERNEL) /// } /// } /// /// impl_list_arc_safe! { /// impl ListArcSafe<0> for BasicItem { untracked; } /// } /// impl_list_item! { /// impl ListItem<0> for BasicItem { using ListLinks { self.links }; } /// } /// /// // Create a new empty list. /// let mut list = List::new(); /// { /// assert!(list.is_empty()); /// } /// /// // Insert 3 elements using `push_back()`. /// list.push_back(BasicItem::new(15)?); /// list.push_back(BasicItem::new(10)?); /// list.push_back(BasicItem::new(30)?); /// /// // Iterate over the list to verify the nodes were inserted correctly. /// // [15, 10, 30] /// { /// let mut iter = list.iter(); /// assert_eq!(iter.next().ok_or(EINVAL)?.value, 15); /// assert_eq!(iter.next().ok_or(EINVAL)?.value, 10); /// assert_eq!(iter.next().ok_or(EINVAL)?.value, 30); /// assert!(iter.next().is_none()); /// /// // Verify the length of the list. /// assert_eq!(list.iter().count(), 3); /// } /// /// // Pop the items from the list using `pop_back()` and verify the content. /// { /// assert_eq!(list.pop_back().ok_or(EINVAL)?.value, 30); /// assert_eq!(list.pop_back().ok_or(EINVAL)?.value, 10); /// assert_eq!(list.pop_back().ok_or(EINVAL)?.value, 15); /// } /// /// // Insert 3 elements using `push_front()`. /// list.push_front(BasicItem::new(15)?); /// list.push_front(BasicItem::new(10)?); /// list.push_front(BasicItem::new(30)?); /// /// // Iterate over the list to verify the nodes were inserted correctly. /// // [30, 10, 15] /// { /// let mut iter = list.iter(); /// assert_eq!(iter.next().ok_or(EINVAL)?.value, 30); /// assert_eq!(iter.next().ok_or(EINVAL)?.value, 10); /// assert_eq!(iter.next().ok_or(EINVAL)?.value, 15); /// assert!(iter.next().is_none()); /// /// // Verify the length of the list. /// assert_eq!(list.iter().count(), 3); /// } /// /// // Pop the items from the list using `pop_front()` and verify the content. /// { /// assert_eq!(list.pop_front().ok_or(EINVAL)?.value, 30); /// assert_eq!(list.pop_front().ok_or(EINVAL)?.value, 10); /// } /// /// // Push `list2` to `list` through `push_all_back()`. /// // list: [15] /// // list2: [25, 35] /// { /// let mut list2 = List::new(); /// list2.push_back(BasicItem::new(25)?); /// list2.push_back(BasicItem::new(35)?); /// /// list.push_all_back(&mut list2); /// /// // list: [15, 25, 35] /// // list2: [] /// let mut iter = list.iter(); /// assert_eq!(iter.next().ok_or(EINVAL)?.value, 15); /// assert_eq!(iter.next().ok_or(EINVAL)?.value, 25); /// assert_eq!(iter.next().ok_or(EINVAL)?.value, 35); /// assert!(iter.next().is_none()); /// assert!(list2.is_empty()); /// } /// # Result::<(), Error>::Ok(()) /// ``` pub struct List<T: ?Sized + ListItem<ID>, const ID: u64 = 0> { first: *mut ListLinksFields, _ty: PhantomData<ListArc<T, ID>>, } // SAFETY: This is a container of `ListArc<T, ID>`, and access to the container allows the same // type of access to the `ListArc<T, ID>` elements. unsafe impl<T, const ID: u64> Send for List<T, ID> where ListArc<T, ID>: Send, T: ?Sized + ListItem<ID>, { } // SAFETY: This is a container of `ListArc<T, ID>`, and access to the container allows the same // type of access to the `ListArc<T, ID>` elements. unsafe impl<T, const ID: u64> Sync for List<T, ID> where ListArc<T, ID>: Sync, T: ?Sized + ListItem<ID>, { } /// Implemented by types where a [`ListArc<Self>`] can be inserted into a [`List`]. /// /// # Safety /// /// Implementers must ensure that they provide the guarantees documented on methods provided by /// this trait. /// /// [`ListArc<Self>`]: ListArc pub unsafe trait ListItem<const ID: u64 = 0>: ListArcSafe<ID> { /// Views the [`ListLinks`] for this value. /// /// # Guarantees /// /// If there is a previous call to `prepare_to_insert` and there is no call to `post_remove` /// since the most recent such call, then this returns the same pointer as the one returned by /// the most recent call to `prepare_to_insert`. /// /// Otherwise, the returned pointer points at a read-only [`ListLinks`] with two null pointers. /// /// # Safety /// /// The provided pointer must point at a valid value. (It need not be in an `Arc`.) unsafe fn view_links(me: *const Self) -> *mut ListLinks<ID>; /// View the full value given its [`ListLinks`] field. /// /// Can only be used when the value is in a list. /// /// # Guarantees /// /// * Returns the same pointer as the one passed to the most recent call to `prepare_to_insert`. /// * The returned pointer is valid until the next call to `post_remove`. /// /// # Safety /// /// * The provided pointer must originate from the most recent call to `prepare_to_insert`, or /// from a call to `view_links` that happened after the most recent call to /// `prepare_to_insert`. /// * Since the most recent call to `prepare_to_insert`, the `post_remove` method must not have /// been called. unsafe fn view_value(me: *mut ListLinks<ID>) -> *const Self; /// This is called when an item is inserted into a [`List`]. /// /// # Guarantees /// /// The caller is granted exclusive access to the returned [`ListLinks`] until `post_remove` is /// called. /// /// # Safety /// /// * The provided pointer must point at a valid value in an [`Arc`]. /// * Calls to `prepare_to_insert` and `post_remove` on the same value must alternate. /// * The caller must own the [`ListArc`] for this value. /// * The caller must not give up ownership of the [`ListArc`] unless `post_remove` has been /// called after this call to `prepare_to_insert`. /// /// [`Arc`]: crate::sync::Arc unsafe fn prepare_to_insert(me: *const Self) -> *mut ListLinks<ID>; /// This undoes a previous call to `prepare_to_insert`. /// /// # Guarantees /// /// The returned pointer is the pointer that was originally passed to `prepare_to_insert`. /// /// # Safety /// /// The provided pointer must be the pointer returned by the most recent call to /// `prepare_to_insert`. unsafe fn post_remove(me: *mut ListLinks<ID>) -> *const Self; } #[repr(C)] #[derive(Copy, Clone)] struct ListLinksFields { next: *mut ListLinksFields, prev: *mut ListLinksFields, } /// The prev/next pointers for an item in a linked list. /// /// # Invariants /// /// The fields are null if and only if this item is not in a list. #[repr(transparent)] pub struct ListLinks<const ID: u64 = 0> { // This type is `!Unpin` for aliasing reasons as the pointers are part of an intrusive linked // list. inner: Opaque<ListLinksFields>, } // SAFETY: The only way to access/modify the pointers inside of `ListLinks<ID>` is via holding the // associated `ListArc<T, ID>`. Since that type correctly implements `Send`, it is impossible to // move this an instance of this type to a different thread if the pointees are `!Send`. unsafe impl<const ID: u64> Send for ListLinks<ID> {} // SAFETY: The type is opaque so immutable references to a ListLinks are useless. Therefore, it's // okay to have immutable access to a ListLinks from several threads at once. unsafe impl<const ID: u64> Sync for ListLinks<ID> {} impl<const ID: u64> ListLinks<ID> { /// Creates a new initializer for this type. pub fn new() -> impl PinInit<Self> { // INVARIANT: Pin-init initializers can't be used on an existing `Arc`, so this value will // not be constructed in an `Arc` that already has a `ListArc`. ListLinks { inner: Opaque::new(ListLinksFields { prev: ptr::null_mut(), next: ptr::null_mut(), }), } } /// # Safety /// /// `me` must be dereferenceable. #[inline] unsafe fn fields(me: *mut Self) -> *mut ListLinksFields { // SAFETY: The caller promises that the pointer is valid. unsafe { Opaque::cast_into(ptr::addr_of!((*me).inner)) } } /// # Safety /// /// `me` must be dereferenceable. #[inline] unsafe fn from_fields(me: *mut ListLinksFields) -> *mut Self { me.cast() } } /// Similar to [`ListLinks`], but also contains a pointer to the full value. /// /// This type can be used instead of [`ListLinks`] to support lists with trait objects. #[repr(C)] pub struct ListLinksSelfPtr<T: ?Sized, const ID: u64 = 0> { /// The `ListLinks` field inside this value. /// /// This is public so that it can be used with `impl_has_list_links!`. pub inner: ListLinks<ID>, // UnsafeCell is not enough here because we use `Opaque::uninit` as a dummy value, and // `ptr::null()` doesn't work for `T: ?Sized`. self_ptr: Opaque<*const T>, } // SAFETY: The fields of a ListLinksSelfPtr can be moved across thread boundaries. unsafe impl<T: ?Sized + Send, const ID: u64> Send for ListLinksSelfPtr<T, ID> {} // SAFETY: The type is opaque so immutable references to a ListLinksSelfPtr are useless. Therefore, // it's okay to have immutable access to a ListLinks from several threads at once. // // Note that `inner` being a public field does not prevent this type from being opaque, since // `inner` is a opaque type. unsafe impl<T: ?Sized + Sync, const ID: u64> Sync for ListLinksSelfPtr<T, ID> {} impl<T: ?Sized, const ID: u64> ListLinksSelfPtr<T, ID> { /// Creates a new initializer for this type. pub fn new() -> impl PinInit<Self> { // INVARIANT: Pin-init initializers can't be used on an existing `Arc`, so this value will // not be constructed in an `Arc` that already has a `ListArc`. Self { inner: ListLinks { inner: Opaque::new(ListLinksFields { prev: ptr::null_mut(), next: ptr::null_mut(), }), }, self_ptr: Opaque::uninit(), } } /// Returns a pointer to the self pointer. /// /// # Safety /// /// The provided pointer must point at a valid struct of type `Self`. pub unsafe fn raw_get_self_ptr(me: *const Self) -> *const Opaque<*const T> { // SAFETY: The caller promises that the pointer is valid. unsafe { ptr::addr_of!((*me).self_ptr) } } } impl<T: ?Sized + ListItem<ID>, const ID: u64> List<T, ID> { /// Creates a new empty list. pub const fn new() -> Self { Self { first: ptr::null_mut(), _ty: PhantomData, } } /// Returns whether this list is empty. pub fn is_empty(&self) -> bool { self.first.is_null() } /// Inserts `item` before `next` in the cycle. /// /// Returns a pointer to the newly inserted element. Never changes `self.first` unless the list /// is empty. /// /// # Safety /// /// * `next` must be an element in this list or null. /// * if `next` is null, then the list must be empty. unsafe fn insert_inner( &mut self, item: ListArc<T, ID>, next: *mut ListLinksFields, ) -> *mut ListLinksFields { let raw_item = ListArc::into_raw(item); // SAFETY: // * We just got `raw_item` from a `ListArc`, so it's in an `Arc`. // * Since we have ownership of the `ListArc`, `post_remove` must have been called after // the most recent call to `prepare_to_insert`, if any. // * We own the `ListArc`. // * Removing items from this list is always done using `remove_internal_inner`, which // calls `post_remove` before giving up ownership. let list_links = unsafe { T::prepare_to_insert(raw_item) }; // SAFETY: We have not yet called `post_remove`, so `list_links` is still valid. let item = unsafe { ListLinks::fields(list_links) }; // Check if the list is empty. if next.is_null() { // SAFETY: The caller just gave us ownership of these fields. // INVARIANT: A linked list with one item should be cyclic. unsafe { (*item).next = item; (*item).prev = item; } self.first = item; } else { // SAFETY: By the type invariant, this pointer is valid or null. We just checked that // it's not null, so it must be valid. let prev = unsafe { (*next).prev }; // SAFETY: Pointers in a linked list are never dangling, and the caller just gave us // ownership of the fields on `item`. // INVARIANT: This correctly inserts `item` between `prev` and `next`. unsafe { (*item).next = next; (*item).prev = prev; (*prev).next = item; (*next).prev = item; } } item } /// Add the provided item to the back of the list. pub fn push_back(&mut self, item: ListArc<T, ID>) { // SAFETY: // * `self.first` is null or in the list. // * `self.first` is only null if the list is empty. unsafe { self.insert_inner(item, self.first) }; } /// Add the provided item to the front of the list. pub fn push_front(&mut self, item: ListArc<T, ID>) { // SAFETY: // * `self.first` is null or in the list. // * `self.first` is only null if the list is empty. let new_elem = unsafe { self.insert_inner(item, self.first) }; // INVARIANT: `new_elem` is in the list because we just inserted it. self.first = new_elem; } /// Removes the last item from this list. pub fn pop_back(&mut self) -> Option<ListArc<T, ID>> { if self.is_empty() { return None; } // SAFETY: We just checked that the list is not empty. let last = unsafe { (*self.first).prev }; // SAFETY: The last item of this list is in this list. Some(unsafe { self.remove_internal(last) }) } /// Removes the first item from this list. pub fn pop_front(&mut self) -> Option<ListArc<T, ID>> { if self.is_empty() { return None; } // SAFETY: The first item of this list is in this list. Some(unsafe { self.remove_internal(self.first) }) } /// Removes the provided item from this list and returns it. /// /// This returns `None` if the item is not in the list. (Note that by the safety requirements, /// this means that the item is not in any list.) /// /// # Safety /// /// `item` must not be in a different linked list (with the same id). pub unsafe fn remove(&mut self, item: &T) -> Option<ListArc<T, ID>> { // SAFETY: TODO. let mut item = unsafe { ListLinks::fields(T::view_links(item)) }; // SAFETY: The user provided a reference, and reference are never dangling. // // As for why this is not a data race, there are two cases: // // * If `item` is not in any list, then these fields are read-only and null. // * If `item` is in this list, then we have exclusive access to these fields since we // have a mutable reference to the list. // // In either case, there's no race. let ListLinksFields { next, prev } = unsafe { *item }; debug_assert_eq!(next.is_null(), prev.is_null()); if !next.is_null() { // This is really a no-op, but this ensures that `item` is a raw pointer that was // obtained without going through a pointer->reference->pointer conversion roundtrip. // This ensures that the list is valid under the more restrictive strict provenance // ruleset. // // SAFETY: We just checked that `next` is not null, and it's not dangling by the // list invariants. unsafe { debug_assert_eq!(item, (*next).prev); item = (*next).prev; } // SAFETY: We just checked that `item` is in a list, so the caller guarantees that it // is in this list. The pointers are in the right order. Some(unsafe { self.remove_internal_inner(item, next, prev) }) } else { None } } /// Removes the provided item from the list. /// /// # Safety