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

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

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 `#`.

> +//! 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.

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

> +//!
> +//! 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>;

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.

> +
> +/// 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.

> +/// - `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.

> +
> +/// 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.

> +
> +/// 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.

> +
> +/// 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.

> +/// - `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.

> +/// [`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`?