Alexandre Courbot
2025-Nov-01 03:51 UTC
[PATCH RFC 1/4] rust: clist: Add abstraction for iterating over C linked lists
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 > +//! > +//! ```ignoreExamples 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. > +/// > +/// # InvariantsMissing 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. > +/// > +/// # InvariantsMissing 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 SafetyHere 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`?
Joel Fernandes
2025-Nov-04 00:58 UTC
[PATCH RFC 1/4] rust: clist: Add abstraction for iterating over C linked lists
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
Danilo Krummrich
2025-Nov-04 13:49 UTC
[PATCH RFC 1/4] rust: clist: Add abstraction for iterating over C linked lists
On 11/1/25 4:51 AM, Alexandre Courbot wrote:> 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`?I think eventually we will have a bunch of iterator types, e.g for list_for_each_entry_{safe,reverse,continue}() etc. (see also [1]). Hence, CList has to provide a couple of methods providing different iterator types. [1] https://lore.kernel.org/lkml/DDVYV1VT441A.11L5C11F8R7C9 at kernel.org/