Add an iteration layer on top of the basic list infrastructure, enabling iteration over the actual container items.
Enables users to iterate over actual items without manually performing container_of operations. Provide macros to make caller's life easier. Signed-off-by: Joel Fernandes <[email protected]> --- rust/kernel/clist.rs | 210 ++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 207 insertions(+), 3 deletions(-) diff --git a/rust/kernel/clist.rs b/rust/kernel/clist.rs index 5ea505d463ad..01b78ba157a1 100644 --- a/rust/kernel/clist.rs +++ b/rust/kernel/clist.rs @@ -2,17 +2,104 @@ //! 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. +//! # Examples +//! +//! ``` +//! use kernel::{bindings, clist::Clist, clist_iterate, impl_from_list_head, types::Opaque}; +//! # // Create test list with values (0, 10, 20) - normally done by C code but it is +//! # // emulated here for doctests using the C bindings. +//! # use core::mem::MaybeUninit; +//! # +//! # /// C struct with embedded list_head (typically will be allocated by C code). +//! # #[repr(C)] +//! # pub(crate) struct SampleItemC { +//! # pub value: i32, +//! # pub link: bindings::list_head, +//! # } +//! # +//! # let mut head = MaybeUninit::<bindings::list_head>::uninit(); +//! # +//! # // SAFETY: head and all the items are test objects allocated in this scope. +//! # unsafe { bindings::INIT_LIST_HEAD(head.as_mut_ptr()) }; +//! # // SAFETY: head is a test object allocated in this scope. +//! # let mut head = unsafe { head.assume_init() }; +//! # let mut items = [ +//! # MaybeUninit::<SampleItemC>::uninit(), +//! # MaybeUninit::<SampleItemC>::uninit(), +//! # MaybeUninit::<SampleItemC>::uninit(), +//! # ]; +//! # +//! # for (i, item) in items.iter_mut().enumerate() { +//! # let ptr = item.as_mut_ptr(); +//! # // SAFETY: pointers are to allocated test objects with a list_head field. +//! # unsafe { +//! # (*ptr).value = i as i32 * 10; +//! # bindings::INIT_LIST_HEAD(&mut (*ptr).link); +//! # bindings::list_add_tail(&mut (*ptr).link, &mut head); +//! # } +//! # } +//! +//! // Rust wrapper for the C struct. +//! // The list item struct in this example is defined in C code as: +//! // struct SampleItemC { +//! // int value; +//! // struct list_head link; +//! // }; +//! // +//! #[repr(transparent)] +//! pub(crate) struct Item(Opaque<SampleItemC>); +//! +//! // Generate the link type. +//! impl_from_list_head!(pub(crate), Item, SampleItemC, link); +//! +//! impl Item { +//! pub(crate) fn value(&self) -> i32 { +//! // SAFETY: Item has same layout as SampleItemC. +//! unsafe { (*self.0.get()).value } +//! } +//! } +//! +//! // Create Clist (from a sentinel head). +//! // SAFETY: head is allocated by test code and Clist has the same layout. +//! let list = unsafe { Clist::from_raw(&mut head) }; +//! +//! // Now iterate using clist_iterate! macro. +//! let mut found_0 = false; +//! let mut found_10 = false; +//! let mut found_20 = false; +//! +//! for item in clist_iterate!(list, Item, link) { +//! let val = item.value(); +//! if val == 0 { found_0 = true; } +//! if val == 10 { found_10 = true; } +//! if val == 20 { found_20 = true; } +//! } +//! +//! assert!(found_0 && found_10 && found_20); +//! ``` use crate::{ bindings, types::Opaque, // }; +use core::marker::PhantomData; + +/// Trait for associating a link type with its container item type. +/// +/// Implemented by "field link types" that are `list_head` links embedded in intrusive +/// C linked lists. Each link type is unique to a specific item type and its `list_head` field, +/// making it possible for an item to be added to multiple lists. +pub trait ClistLink { + /// The item type that contains the `list_head` field linking to other items in the list. + type Item: FromListHead<Self> + where + Self: Sized; +} /// 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. +/// Represents the entire linked list and can be used for add, remove, empty operations etc. +/// A sentinel head is one which is not embedded in an item. /// /// # Invariants /// @@ -69,6 +156,15 @@ pub fn iter_heads(&self) -> ClistHeadIter<'_> { head: &self.0, } } + + /// Create a high-level iterator over typed items. + #[inline] + pub fn iter<L: ClistLink>(&self) -> ClistIter<'_, L> { + ClistIter { + head_iter: self.iter_heads(), + _phantom: PhantomData, + } + } } /// Wraps a non-sentinel C `list_head` node for use in intrusive linked lists. @@ -188,3 +284,111 @@ fn next(&mut self) -> Option<Self::Item> { Some(self.current) } } + +/// High-level iterator over typed list items. +pub struct ClistIter<'a, L: ClistLink> { + head_iter: ClistHeadIter<'a>, + + /// The iterator yields immutable references to `L::Item`. + _phantom: PhantomData<&'a L::Item>, +} + +// SAFETY: ClistIter yields `&L::Item`, which is Send when `L::Item: Send`. +unsafe impl<L: ClistLink> Send for ClistIter<'_, L> where L::Item: Send {} + +// SAFETY: ClistIter yields &L::Item, which is Sync when `L::Item: Sync`. +unsafe impl<L: ClistLink> Sync for ClistIter<'_, L> where L::Item: Sync {} + +impl<'a, L: ClistLink> Iterator for ClistIter<'a, L> +where + L::Item: 'a, +{ + type Item = &'a L::Item; + + fn next(&mut self) -> Option<Self::Item> { + // Get next ClistHead. + let head = self.head_iter.next()?; + + // Convert to item using trait. + // SAFETY: FromListHead impl guarantees valid conversion. + Some(unsafe { L::Item::from_list_head(head) }) + } +} + +/// Trait for converting a `ClistHead` to an item reference. +pub trait FromListHead<Link>: Sized { + /// Convert a `ClistHead` node reference to an item reference. + /// + /// # Safety + /// + /// `head` must be a valid reference to an allocated and initialized `ClistHead` structure + /// valid for the lifetime `'a`. + unsafe fn from_list_head<'a>(head: &'a ClistHead) -> &'a Self; +} + +/// Macro to generate `FromListHead` implementations for C list integration. +/// +/// `FromListHead` trait is required to iterate over a C linked list using the `clist_iterate!` +/// macro which yields immutable references to the Rust item wrapper type. +/// +/// Also generates a link type named `Clist<ItemType><field>` implementing the `ClistLink` trait +/// that associates the list node with the item. The link type is used to iterate over the list +/// using the `clist_iterate!` macro. +/// +/// # Arguments +/// +/// - `$vis`: The visibility of the generated link type (e.g., `pub`, `pub(crate)`). +/// - `$item_type`: The Rust wrapper type for items in the list. +/// - `$c_type`: The C struct type that contains the embedded `list_head`. +/// - `$field`: The name of the `list_head` field within the C struct that links items. +/// +/// # Examples +/// +/// Refer to the comprehensive example in the [crate::clist] module documentation. +#[macro_export] +macro_rules! impl_from_list_head { + ($vis:vis, $item_type:ident, $c_type:ty, $field:ident) => { + $crate::macros::paste! { + /// Link type for associating list nodes with items. + $vis struct [<Clist $item_type $field>]; + + // Implement ClistLink trait to associate the link with its item type. + impl $crate::clist::ClistLink for [<Clist $item_type $field>] { + type Item = $item_type; + } + + impl $crate::clist::FromListHead<[<Clist $item_type $field>]> for $item_type { + unsafe fn from_list_head<'a>( + head: &'a $crate::clist::ClistHead, + ) -> &'a Self { + let ptr = $crate::container_of!(head.as_raw(), $c_type, $field); + // SAFETY: repr(transparent) makes item_type have same layout as c_type. + // Caller guarantees the container_of calculation is correct. + unsafe { &*ptr.cast::<Self>() } + } + } + } + }; +} + +/// Macro to assist with iterating over a C linked list. +/// +/// Returns a `ClistIter` iterator which yields immutable references to the `item_type` type. +/// +/// # Arguments +/// +/// - `$list`: The `Clist` instance to iterate over. +/// - `$item_type`: The Rust type of the item in the list with list_head embedded. +/// - `$field`: The name of the field in the `item_type` that links it to the list. +/// +/// # Examples +/// +/// Refer to the comprehensive example in the [crate::clist] module documentation. +#[macro_export] +macro_rules! clist_iterate { + ($list:expr, $item_type:ident, $field:ident) => { + $crate::macros::paste! { + $list.iter::<[<Clist $item_type $field>]>() + } + }; +} -- 2.34.1
