Nouveau - Nov 2025 - [PATCH v2 2/3] rust: clist: Add basic list infrastructure and head iterator

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 at 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.
+
+use crate::{
+    bindings,
+    types::Opaque, //
+};
+
+/// A C linked list with a sentinel head
+///
+/// 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.
+#[repr(transparent)]
+pub struct Clist(ClistHead);
+
+// 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 {}
+
+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() }
+    }
+
+    /// 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.
+///
+/// # 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();
+            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
+        }
+    }
+}
+
+/// 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,
+}
+
+// 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<'_> {}
+
+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() {
+            return None;
+        }
+
+        Some(self.current)
+    }
+}
diff --git a/rust/kernel/lib.rs b/rust/kernel/lib.rs
index c2eea9a2a345..b69cc5ed3b59 100644
--- a/rust/kernel/lib.rs
+++ b/rust/kernel/lib.rs
@@ -72,6 +72,7 @@
 pub mod bug;
 #[doc(hidden)]
 pub mod build_assert;
+pub mod clist;
 pub mod clk;
 #[cfg(CONFIG_CONFIGFS_FS)]
 pub mod configfs;
-- 
2.34.1

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 at 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.