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

Alexandre Courbot
2025-11-01T03:51:44Z

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`?