Re: [PATCH RFC 1/4] rust: clist: Add abstraction for iterating over C linked lists

[Joel Fernandes <joelagnelf@nvidia.com>]

On Sat, Nov 01, 2025 at 12:51:32PM +0900, Alexandre Courbot wrote:
> Hi Joel,
> 
> On Fri Oct 31, 2025 at 4:06 AM JST, Joel Fernandes wrote:
> <snip>
> > diff --git a/rust/kernel/clist.rs b/rust/kernel/clist.rs
> > new file mode 100644
> > index 000000000000..e6a46974b1ba
> > --- /dev/null
> > +++ b/rust/kernel/clist.rs
> > @@ -0,0 +1,296 @@
> > +// SPDX-License-Identifier: GPL-2.0
> > +
> > +//! List processing module for C list_head linked lists.
> > +//!
> > +//! C header: [`include/linux/list.h`](srctree/include/linux/list.h)
> > +//!
> > +//! Provides a safe interface for iterating over C's intrusive `list_head` structures.
> > +//! At the moment, supports only read-only iteration.
> > +//!
> > +//! # Examples
> > +//!
> > +//! ```ignore
> 
> Examples pull double-duty as unit tests, and making them build and run
> ensures that they never fall out-of-date as the code evolves. Please
> make sure that they can be built and run. Supporting code that you don't
> want to show in the doc can be put behind `#`.

Sure, the reason I didn't do it was there are a couple of challenges:

1. For clist, there is a "C language" component" as well in the
sample, as these are lists coming from C. I am not sure how to do that as a
doc example, I might have to emulate a C struct containing a list_head in
Rust itself. Is that something we're Ok with? After all the purpose of a
sample, is to show how this could be used to interface with lists coming from
actual C code.

2. For DRM buddy, #1 is not an issue, however CONFIG_DRM_BUDDY has to be
enabled for the test to work. I have to figure out how to make a doc test be
kernel CONFIG dependent. What if the CONFIG required is disabled, is there a
standard way to make doc tests not fail for features that are disabled? Are the
doc tests skipped in such a situation? Just something I have to figure out.
Perhaps wrapping it is #cfg is sufficient.
Btw, I also realize my patch 3 introducing buddy.rs is not dependent on
CONFIG_DRM_BUDDY, which it should be. I was testing with CONFIG_DRM_BUDDY
always enabled, which is probably why I didn't catch this.

> > +//! use core::ptr::NonNull;
> > +//! use kernel::{
> > +//!     bindings,
> > +//!     clist,
> > +//!     container_of,
> > +//!     prelude::*, //
> > +//! };
> > +//!
> > +//! // Example C-side struct (typically from C bindings):
> > +//! // struct c_item {
> > +//! //     u64 offset;
> > +//! //     struct list_head link;
> > +//! //     /* ... other fields ... */
> > +//! // };
> > +//!
> > +//! // Rust-side struct to hold pointer to C-side struct.
> > +//! struct Item {
> > +//!     ptr: NonNull<bindings::c_item>,
> > +//! }
> 
> As Danilo suggested, using a e.g. `Entry` structure that just wraps
> `Self` inside an `Opaque` would allow capturing the lifetime as well.
> Look at how `SGEntry` and its `from_raw` method are done, it should look
> very similar.

Great ideas. I will look at SGEntry, at first look it seems a perfect fit
indeed.

> Doing so would also spare users the trouble of having to define a
> dedicated type.

True!

> > +//!
> > +//! impl clist::FromListHead for Item {
> > +//!     unsafe fn from_list_head(link: *const bindings::list_head) -> Self {
> > +//!         let item_ptr = container_of!(link, bindings::c_item, link) as *mut _;
> > +//!         Item { ptr: NonNull::new_unchecked(item_ptr) }
> > +//!     }
> > +//! }
> > +//!
> > +//! impl Item {
> > +//!     fn offset(&self) -> u64 {
> > +//!         unsafe { (*self.ptr.as_ptr()).offset }
> > +//!     }
> > +//! }
> > +//!
> > +//! // Get the list head from C code.
> > +//! let c_list_head = unsafe { bindings::get_item_list() };
> > +//!
> > +//! // Rust wraps and iterates over the list.
> > +//! let list = unsafe { clist::Clist::<Item>::new(c_list_head) };
> > +//!
> > +//! // Check if empty.
> > +//! if list.is_empty() {
> > +//!     pr_info!("List is empty\n");
> > +//! }
> > +//!
> > +//! // Iterate over items.
> > +//! for item in list.iter() {
> > +//!     pr_info!("Item offset: {}\n", item.offset());
> > +//! }
> > +//! ```
> > +
> > +use crate::bindings;
> > +use core::marker::PhantomData;
> > +
> > +/// Trait for types that can be constructed from a C list_head pointer.
> > +///
> > +/// This typically encapsulates `container_of` logic, allowing iterators to
> > +/// work with high-level types without knowing about C struct layout details.
> > +///
> > +/// # Safety
> > +///
> > +/// Implementors must ensure that `from_list_head` correctly converts the
> > +/// `list_head` pointer to the containing struct pointer using proper offset
> > +/// calculations (typically via container_of! macro).
> > +///
> > +/// # Examples
> > +///
> > +/// ```ignore
> > +/// impl FromListHead for MyItem {
> > +///     unsafe fn from_list_head(link: *const bindings::list_head) -> Self {
> > +///         let item_ptr = container_of!(link, bindings::my_c_struct, link_field) as *mut _;
> > +///         MyItem { ptr: NonNull::new_unchecked(item_ptr) }
> > +///     }
> > +/// }
> > +/// ```
> > +pub trait FromListHead: Sized {
> > +    /// Create instance from list_head pointer embedded in containing struct.
> > +    ///
> > +    /// # Safety
> > +    ///
> > +    /// Caller must ensure `link` points to a valid list_head embedded in the
> > +    /// containing struct, and that the containing struct is valid for the
> > +    /// lifetime of the returned instance.
> > +    unsafe fn from_list_head(link: *const bindings::list_head) -> Self;
> > +}
> 
> If we go with the `Entry` thing, this method would thus become:
> 
>     unsafe fn from_list_head<'a>(link: *const bindings::list_head) -> &'a Entry<Self>;

Sure.

> But that leaves an open question: how do we support items that have
> several lists embedded in them? This is a pretty common pattern. Maybe
> we can add a const parameter to `Entry` (with a default value) to
> discriminate them.

Ah, good point! as you mentioned, we could make it a parameter.

> > +
> > +/// Iterator over C list items.
> > +///
> > +/// Uses the [`FromListHead`] trait to convert list_head pointers to
> > +/// Rust types and iterate over them.
> > +///
> > +/// # Invariants
> 
> Missing empty line.

Ack.

> > +/// - `head` points to a valid, initialized list_head.
> > +/// - `current` points to a valid node in the list.
> > +/// - The list is not modified during iteration.
> > +///
> > +/// # Examples
> > +///
> > +/// ```ignore
> > +/// // Iterate over blocks in a C list_head
> > +/// for block in clist::iter_list_head::<Block>(&list_head) {
> > +///     // Process block
> > +/// }
> > +/// ```
> > +pub struct ClistIter<'a, T: FromListHead> {
> > +    current: *const bindings::list_head,
> > +    head: *const bindings::list_head,
> > +    _phantom: PhantomData<&'a T>,
> > +}
> > +
> > +// SAFETY: Safe to send iterator if T is Send.
> > +unsafe impl<'a, T: FromListHead + Send> Send for ClistIter<'a, T> {}
> > +
> > +impl<'a, T: FromListHead> Iterator for ClistIter<'a, T> {
> > +    type Item = T;
> > +
> > +    fn next(&mut self) -> Option<Self::Item> {
> > +        // SAFETY: Pointers are valid per the type's invariants. The list
> > +        // structure is valid and we traverse according to kernel list semantics.
> > +        unsafe {
> > +            self.current = (*self.current).next;
> > +
> > +            if self.current == self.head {
> > +                return None;
> > +            }
> > +
> > +            // Use the trait to convert list_head to T.
> > +            Some(T::from_list_head(self.current))
> > +        }
> > +    }
> > +}
> > +
> > +/// Create a read-only iterator over a C list_head.
> > +///
> > +/// This is a convenience function for creating iterators directly
> > +/// from a list_head reference.
> > +///
> > +/// # Safety
> > +///
> > +/// Caller must ensure:
> > +/// - `head` is a valid, initialized list_head.
> > +/// - All items in the list are valid instances that can be converted via [`FromListHead`].
> > +/// - The list is not modified during iteration.
> > +///
> > +/// # Examples
> > +///
> > +/// ```ignore
> > +/// // Iterate over items in a C list.
> > +/// for item in clist::iter_list_head::<Item>(&c_list_head) {
> > +///     // Process item
> > +/// }
> > +/// ```
> > +pub fn iter_list_head<'a, T: FromListHead>(head: &'a bindings::list_head) -> ClistIter<'a, T> {
> > +    ClistIter {
> > +        current: head as *const _,
> > +        head: head as *const _,
> > +        _phantom: PhantomData,
> > +    }
> > +}
> 
> Why do we need a function for this? The correct way to iterate should be
> through `CList`, so I'd just move its code to `CList::iter` and make all
> the examples use that.

Sure, I will move this function there. Are you saying we should also merge
`Clist` and `ClistIter` too or just move the function? I think we still want
to keep the 2 types separate as `ClistIter` stores the interation state
(current/head pointers).

> > +
> > +/// Check if a C list is empty.
> > +///
> > +/// # Safety
> > +///
> > +/// Caller must ensure `head` points to a valid, initialized list_head.
> > +#[inline]
> > +pub unsafe fn list_empty(head: *const bindings::list_head) -> bool {
> > +    // SAFETY: Caller ensures head is valid and initialized.
> > +    unsafe { bindings::list_empty(head) }
> > +}
> 
> Why not call `bindings::list_empty` directly from `is_empty`? I don't
> see what having an extra public function brings here.

Ok sure, yeah no reason not to do so :).

> > +
> > +/// Initialize a C list_head to an empty list.
> > +///
> > +/// # Safety
> > +///
> > +/// Caller must ensure `head` points to valid memory for a list_head.
> > +#[inline]
> > +pub unsafe fn init_list_head(head: *mut bindings::list_head) {
> > +    // SAFETY: Caller ensures head points to valid memory for a list_head.
> > +    unsafe { bindings::INIT_LIST_HEAD(head) }
> > +}
> 
> Since this patch adds read-only support, what do we need this function
> for? It also doesn't appear to be used anywhere in this series.

Ah, yes. I directly called the bindings in the DRM patch, instead of using
the wrapper. hmm from a readability PoV, bindings::INIT_LIST_HEAD() is itself
Ok so I'll just get rid of this function as well then.

> > +
> > +/// An interface to C list_head structures.
> > +///
> > +/// This provides an iterator-based interface for traversing C's intrusive
> > +/// linked lists. Items must implement the [`FromListHead`] trait.
> > +///
> > +/// Designed for iterating over lists created and managed by C code (e.g.,
> > +/// drm_buddy block lists). [`Clist`] does not own the `list_head` or the items.
> > +/// It's a non-owning view for iteration.
> > +///
> > +/// # Invariants
> 
> Missing empty line.

Ack.

> > +/// - `head` points to a valid, initialized list_head.
> > +/// - All items in the list are valid instances of `T`.
> > +/// - The list is not modified while iterating.
> > +///
> > +/// # Thread Safety
> 
> Here as well.

Ack.

> > +/// [`Clist`] can have its ownership transferred between threads ([`Send`]) if `T: Send`.
> > +/// But its never [`Sync`] - concurrent Rust threads with `&Clist` could call C FFI unsafely.
> > +/// For concurrent access, wrap in a `Mutex` or other synchronization primitive.
> > +///
> > +/// # Examples
> > +///
> > +/// ```ignore
> > +/// use kernel::clist::Clist;
> > +///
> > +/// // C code provides the populated list_head.
> > +/// let list = unsafe { Clist::<Item>::new(c_list_head) };
> > +///
> > +/// // Iterate over items.
> > +/// for item in list.iter() {
> > +///     // Process item.
> > +/// }
> > +/// ```
> > +pub struct Clist<T: FromListHead> {
> > +    head: *mut bindings::list_head,
> > +    _phantom: PhantomData<T>,
> > +}
> > +
> > +// SAFETY: Safe to send Clist if T is Send (pointer moves, C data stays in place).
> > +unsafe impl<T: FromListHead + Send> Send for Clist<T> {}
> > +
> > +impl<T: FromListHead> Clist<T> {
> > +    /// Wrap an existing C list_head pointer without taking ownership.
> > +    ///
> > +    /// # Safety
> > +    ///
> > +    /// Caller must ensure:
> > +    /// - `head` points to a valid, initialized list_head.
> > +    /// - `head` remains valid for the lifetime of the returned [`Clist`].
> > +    /// - The list is not modified by C code while [`Clist`] exists. Caller must
> > +    ///   implement mutual exclusion algorithms if required, to coordinate with C.
> > +    /// - Caller is responsible for requesting or working with C to free `head` if needed.
> > +    pub unsafe fn new(head: *mut bindings::list_head) -> Self {
> > +        // SAFETY: Caller ensures head is valid and initialized
> > +        Self {
> > +            head,
> > +            _phantom: PhantomData,
> > +        }
> > +    }
> 
> I am wondering whether `CList` serves an actual purpose beyond providing
> ` CListIter` to iterate on... Would it make sense to merge both types
> into a single one that implements `Iterator`?
> 

It would force us to store iteration state into `Clist`, I think for that
reason it would be great to keep them separate IMO.

thanks,

 - Joel