path: root/rust/kernel/list.rs

// SPDX-License-Identifier: GPL-2.0

// Copyright (C) 2024 Google LLC.

//! A linked list implementation.

use crate::init::PinInit;
use crate::sync::ArcBorrow;
use crate::types::Opaque;
use core::iter::{DoubleEndedIterator, FusedIterator};
use core::marker::PhantomData;
use core::ptr;

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.
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::raw_get(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> {
    /// The offset from the [`ListLinks`] to the self pointer field.
    pub const LIST_LINKS_SELF_PTR_OFFSET: usize = core::mem::offset_of!(Self, self_ptr);

    /// 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(),
        }
    }
}

impl<T: ?Sized + ListItem<ID>, const</