// 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 [`ListLinks`] as the type of the intrusive field.////// ```/// 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(())/// ```////// Use [`ListLinksSelfPtr`] as the type of the intrusive field. This allows a list of trait object/// type.////// ```/// use kernel::list::*;////// trait Foo {///     fn foo(&self) -> (&'static str, i32);/// }////// #[pin_data]/// struct DTWrap<T: ?Sized> {///     #[pin]///     links: ListLinksSelfPtr<DTWrap<dyn Foo>>,///     value: T,/// }////// impl<T> DTWrap<T> {///     fn new(value: T) -> Result<ListArc<Self>> {///         ListArc::pin_init(try_pin_init!(Self {///             value,///             links <- ListLinksSelfPtr::new(),///         }), GFP_KERNEL)///     }/// }////// impl_list_arc_safe! {///     impl{T: ?Sized} ListArcSafe<0> for DTWrap<T> { untracked; }/// }/// impl_list_item! {///     impl ListItem<0> for DTWrap<dyn Foo> { using ListLinksSelfPtr { self.links }; }/// }////// // Create a new empty list./// let mut list = List::<DTWrap<dyn Foo>>::new();/// {///     assert!(list.is_empty());/// }////// struct A(i32);/// // `A` returns the inner value for `foo`./// impl Foo for A { fn foo(&self) -> (&'static str, i32) { ("a", self.0) } }////// struct B;/// // `B` always returns 42./// impl Foo for B { fn foo(&self) -> (&'static str, i32) { ("b", 42) } }////// // Insert 3 element using `push_back()`./// list.push_back(DTWrap::new(A(15))?);/// list.push_back(DTWrap::new(A(32))?);/// list.push_back(DTWrap::new(B)?);////// // Iterate over the list to verify the nodes were inserted correctly./// // [A(15), A(32), B]/// {///     let mut iter = list.iter();///     assert_eq!(iter.next().ok_or(EINVAL)?.value.foo(), ("a", 15));///     assert_eq!(iter.next().ok_or(EINVAL)?.value.foo(), ("a", 32));///     assert_eq!(iter.next().ok_or(EINVAL)?.value.foo(), ("b", 42));///     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.foo(), ("b", 42));///     assert_eq!(list.pop_back().ok_or(EINVAL)?.value.foo(), ("a", 32));///     assert_eq!(list.pop_back().ok_or(EINVAL)?.value.foo(), ("a", 15));/// }////// // Insert 3 elements using `push_front()`./// list.push_front(DTWrap::new(A(15))?);/// list.push_front(DTWrap::new(A(32))?);/// list.push_front(DTWrap::new(B)?);////// // Iterate over the list to verify the nodes were inserted correctly./// // [B, A(32), A(15)]/// {///     let mut iter = list.iter();///     assert_eq!(iter.next().ok_or(EINVAL)?.value.foo(), ("b", 42));///     assert_eq!(iter.next().ok_or(EINVAL)?.value.foo(), ("a", 32));///     assert_eq!(iter.next().ok_or(EINVAL)?.value.foo(), ("a", 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_back().ok_or(EINVAL)?.value.foo(), ("a", 15));///     assert_eq!(list.pop_back().ok_or(EINVAL)?.value.foo(), ("a", 32));/// }////// // Push `list2` to `list` through `push_all_back()`./// // list: [B]/// // list2: [B, A(25)]/// {///     let mut list2 = List::<DTWrap<dyn Foo>>::new();///     list2.push_back(DTWrap::new(B)?);///     list2.push_back(DTWrap::new(A(25))?);//////     list.push_all_back(&mut list2);//////     // list: [B, B, A(25)]///     // list2: []///     let mut iter = list.iter();///     assert_eq!(iter.next().ok_or(EINVAL)?.value.foo(), ("b", 42));///     assert_eq!(iter.next().ok_or(EINVAL)?.value.foo(), ("b", 42));///     assert_eq!(iter.next().ok_or(EINVAL)?.value.foo(), ("a", 25));///     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

Lines 1–500 of 1206. Load more