Re: [PATCH v2 2/3] rust: clist: Add basic list infrastructure and head iterator

["Alexandre Courbot" <acourbot@nvidia.com>]

Hi Joel,

This low-level layer looks mostly ok to me, I will have more comments on
the higher layer though.

On Wed Nov 12, 2025 at 2:13 AM JST, Joel Fernandes wrote:
> Add foundational types for working with C's doubly circular linked
> lists (list_head). Provide low-level iteration over list nodes.
>
> Typed iteration over actual items will be added in a follow-up
> commit using the FromListHead trait and ClistLink mechanism.
>
> Signed-off-by: Joel Fernandes <joelagnelf@nvidia.com>
> ---
>  rust/kernel/clist.rs | 190 +++++++++++++++++++++++++++++++++++++++++++
>  rust/kernel/lib.rs   |   1 +
>  2 files changed, 191 insertions(+)
>  create mode 100644 rust/kernel/clist.rs
>
> diff --git a/rust/kernel/clist.rs b/rust/kernel/clist.rs
> new file mode 100644
> index 000000000000..5ea505d463ad
> --- /dev/null
> +++ b/rust/kernel/clist.rs
> @@ -0,0 +1,190 @@
> +// SPDX-License-Identifier: GPL-2.0
> +
> +//! A C doubly circular intrusive linked list interface for rust code.
> +//!
> +//! TODO: Doctest example will be added in later commit in series due to dependencies.

Since it is added in the following patch, I guess we can do without this
very temporary TODO. :)

> +
> +use crate::{
> +    bindings,
> +    types::Opaque, //
> +};
> +
> +/// A C linked list with a sentinel head

Nit: '.' at end of sentence.

> +///
> +/// A sentinel head is one which is not embedded in an item. It represents the entire
> +/// linked list and can be used for add, remove, empty operations etc.
> +///
> +/// # Invariants
> +///
> +/// - `Clist` wraps an allocated and valid C list_head structure that is the sentinel of a list.
> +/// - All the `list_head` nodes in the list are allocated and have valid next/prev pointers.
> +/// - The underlying `list_head` (and entire list) is not modified by C.

These last two ones look more like safety requirements to maintain for
the life of a Clist than invariants.

> +#[repr(transparent)]
> +pub struct Clist(ClistHead);

`ClistHead`'s definition should come before `Clist` for clarity.

> +
> +// SAFETY: `Clist` can be sent to any thread.
> +unsafe impl Send for Clist {}
> +// SAFETY: `Clist` can be shared among threads as it is not modified by C per type invariants.
> +unsafe impl Sync for Clist {}

These explicit impls should not be needed - as `ClistHead` implements
`Send` and `Sync`, they will be automatically derived for `Clist` which
just wraps it.

> +
> +impl Clist {
> +    /// Create a `&Clist` from a raw sentinel `list_head` pointer.
> +    ///
> +    /// # Safety
> +    ///
> +    /// `ptr` must be a valid pointer to an allocated and initialized `list_head` structure
> +    /// representing a list sentinel, and it must remain valid for the lifetime `'a`.
> +    #[inline]
> +    pub unsafe fn from_raw<'a>(ptr: *mut bindings::list_head) -> &'a Self {
> +        // SAFETY:
> +        // - `ClistHead` has same layout as `list_head`.
> +        // - `ptr` is valid for 'a.
> +        unsafe { &*ptr.cast() }

Let's reuse `ClistHead::from_raw` here.

> +    }
> +
> +    /// Get the raw sentinel `list_head` pointer.
> +    #[inline]
> +    pub fn as_raw(&self) -> *mut bindings::list_head {
> +        self.0.as_raw()
> +    }
> +
> +    /// Access the underlying `ClistHead`.
> +    #[inline]
> +    pub fn head(&self) -> &ClistHead {
> +        &self.0
> +    }
> +
> +    /// Check if the list is empty.
> +    #[inline]
> +    pub fn is_empty(&self) -> bool {
> +        self.0.is_empty()
> +    }
> +
> +    /// Create a low-level iterator over `ClistHead` nodes. Caller converts the returned
> +    /// heads into items.
> +    #[inline]
> +    pub fn iter_heads(&self) -> ClistHeadIter<'_> {
> +        ClistHeadIter {
> +            current: &self.0,
> +            head: &self.0,
> +        }
> +    }
> +}
> +
> +/// Wraps a non-sentinel C `list_head` node for use in intrusive linked lists.

This says "non-sentinel", but `Clist` embeds a `ClistHead` which wraps a
sentinel node, so that statement does not seem to be true.

> +///
> +/// # Invariants
> +///
> +/// - `ClistHead` represents an allocated and valid non-sentinel `list_head` structure.
> +/// - The underlying `list_head` (and entire list) is not modified by C.
> +#[repr(transparent)]
> +pub struct ClistHead(Opaque<bindings::list_head>);
> +
> +// SAFETY: `ClistHead` can be sent to any thread.
> +unsafe impl Send for ClistHead {}
> +// SAFETY: `ClistHead` can be shared among threads as it is not modified by C per type invariants.
> +unsafe impl Sync for ClistHead {}
> +
> +impl ClistHead {
> +    /// Create a `&ClistHead` reference from a raw `list_head` pointer.
> +    ///
> +    /// # Safety
> +    ///
> +    /// `ptr` must be a valid pointer to an allocated and initialized `list_head` structure,
> +    /// and it must remain valid for the lifetime `'a`.
> +    #[inline]
> +    pub unsafe fn from_raw<'a>(ptr: *mut bindings::list_head) -> &'a Self {
> +        // SAFETY:
> +        // - `ClistHead` has same layout as `list_head`.
> +        // - `ptr` is valid for 'a.
> +        unsafe { &*ptr.cast() }
> +    }
> +
> +    /// Get the raw `list_head` pointer.
> +    #[inline]
> +    pub fn as_raw(&self) -> *mut bindings::list_head {
> +        self.0.get()
> +    }
> +
> +    /// Get the next `ClistHead` in the list.
> +    #[inline]
> +    pub fn next(&self) -> &Self {
> +        // SAFETY:
> +        // - `self.as_raw()` is valid per type invariants.
> +        // - The `next` pointer is guaranteed to be non-NULL.
> +        unsafe {
> +            let raw = self.as_raw();

This line doesn't need to be in the `unsafe` block (also applies to
other methods).

> +            Self::from_raw((*raw).next)
> +        }
> +    }
> +
> +    /// Get the previous `ClistHead` in the list.
> +    #[inline]
> +    pub fn prev(&self) -> &Self {
> +        // SAFETY:
> +        // - self.as_raw() is valid per type invariants.
> +        // - The `prev` pointer is guaranteed to be non-NULL.
> +        unsafe {
> +            let raw = self.as_raw();
> +            Self::from_raw((*raw).prev)
> +        }
> +    }
> +
> +    /// Check if this node is linked in a list (not isolated).
> +    #[inline]
> +    pub fn is_in_list(&self) -> bool {
> +        // SAFETY: self.as_raw() is valid per type invariants.
> +        unsafe {
> +            let raw = self.as_raw();
> +            (*raw).next != raw && (*raw).prev != raw
> +        }
> +    }
> +
> +    /// Check if the list is empty.
> +    #[inline]
> +    pub fn is_empty(&self) -> bool {
> +        // SAFETY: self.as_raw() is valid per type invariants.
> +        unsafe {
> +            let raw = self.as_raw();
> +            (*raw).next == raw
> +        }
> +    }

Does this method also apply to non-sentinel nodes? If not, should we
move it to `Clist`?

I am also wondering what the difference is with `is_in_list`. If
`raw.next == raw`, then on a valid list `raw.prev == raw` as well, so
it seems to be that `is_in_list()` is equivalent to `!is_empty()`.

> +}
> +
> +/// Low-level iterator over `list_head` nodes.
> +///
> +/// An iterator used to iterate over a C intrusive linked list (`list_head`). Caller has to
> +/// perform conversion of returned `ClistHead` to an item (typically using `container_of` macro).
> +///
> +/// # Invariants
> +///
> +/// `ClistHeadIter` is iterating over an allocated, initialized and valid `Clist`.
> +pub struct ClistHeadIter<'a> {
> +    current: &'a ClistHead,
> +    head: &'a ClistHead,

IIUC `head` should probably be a `Clist`?

> +}
> +
> +// SAFETY: ClistHeadIter gives out immutable references to ClistHead,
> +// which is Send.
> +unsafe impl Send for ClistHeadIter<'_> {}
> +
> +// SAFETY: ClistHeadIter gives out immutable references to ClistHead,
> +// which is Sync.
> +unsafe impl Sync for ClistHeadIter<'_> {}

`Send` and `Sync` will also be auto-implemented here.

> +
> +impl<'a> Iterator for ClistHeadIter<'a> {
> +    type Item = &'a ClistHead;
> +
> +    #[inline]
> +    fn next(&mut self) -> Option<Self::Item> {
> +        // Advance to next node.
> +        self.current = self.current.next();
> +
> +        // Check if we've circled back to HEAD.
> +        if self.current.as_raw() == self.head.as_raw() {

Maybe derive/implement `PartialEq` so we can avoid calling `as_raw`
when comparing nodes.