Provides a safe interface for iterating over C's intrusive linked lists (`list_head` structures). At the moment, supports only read-only iteration. DRM Buddy bindings will use this to iterate over DRM buddy blocks allocated in a linked list.
Signed-off-by: Joel Fernandes <[email protected]> --- rust/helpers/helpers.c | 1 + rust/helpers/list.c | 28 ++++ rust/kernel/clist.rs | 296 +++++++++++++++++++++++++++++++++++++++++ rust/kernel/lib.rs | 1 + 4 files changed, 326 insertions(+) create mode 100644 rust/helpers/list.c create mode 100644 rust/kernel/clist.rs diff --git a/rust/helpers/helpers.c b/rust/helpers/helpers.c index 79c72762ad9c..634fa2386bbb 100644 --- a/rust/helpers/helpers.c +++ b/rust/helpers/helpers.c @@ -32,6 +32,7 @@ #include "io.c" #include "jump_label.c" #include "kunit.c" +#include "list.c" #include "maple_tree.c" #include "mm.c" #include "mutex.c" diff --git a/rust/helpers/list.c b/rust/helpers/list.c new file mode 100644 index 000000000000..74e8f40b7141 --- /dev/null +++ b/rust/helpers/list.c @@ -0,0 +1,28 @@ +// SPDX-License-Identifier: GPL-2.0 + +#include <linux/list.h> + +bool rust_helper_list_empty(const struct list_head *head) +{ + return list_empty(head); +} + +void rust_helper_list_del(struct list_head *entry) +{ + list_del(entry); +} + +void rust_helper_INIT_LIST_HEAD(struct list_head *list) +{ + INIT_LIST_HEAD(list); +} + +void rust_helper_list_add(struct list_head *new, struct list_head *head) +{ + list_add(new, head); +} + +void rust_helper_list_add_tail(struct list_head *new, struct list_head *head) +{ + list_add_tail(new, head); +} 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 +//! 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>, +//! } +//! +//! 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; +} + +/// Iterator over C list items. +/// +/// Uses the [`FromListHead`] trait to convert list_head pointers to +/// Rust types and iterate over them. +/// +/// # Invariants +/// - `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, + } +} + +/// 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) } +} + +/// 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) } +} + +/// 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 +/// - `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 +/// [`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, + } + } + + /// Check if the list is empty. + /// + /// # Examples + /// + /// ```ignore + /// let list = Clist::<Block>::new()?; + /// assert!(list.is_empty()); + /// ``` + #[inline] + pub fn is_empty(&self) -> bool { + // SAFETY: self.head points to valid list_head per invariant. + unsafe { list_empty(self.head) } + } + + /// Iterate over items in the list. + /// + /// # Examples + /// + /// ```ignore + /// for item in list.iter() { + /// // Process item + /// } + /// ``` + pub fn iter(&self) -> ClistIter<'_, T> { + // SAFETY: self.head points to valid list_head per invariant. + unsafe { iter_list_head::<T>(&*self.head) } + } + + /// Get the raw list_head pointer. + /// + /// This is useful when interfacing with C APIs that need the list_head pointer. + pub fn as_raw(&self) -> *mut bindings::list_head { + self.head + } +} + +impl<'a, T: FromListHead> IntoIterator for &'a Clist<T> { + type Item = T; + type IntoIter = ClistIter<'a, T>; + + fn into_iter(self) -> Self::IntoIter { + self.iter() + } +} diff --git a/rust/kernel/lib.rs b/rust/kernel/lib.rs index c2eea9a2a345..b69cc5ed3b59 100644 --- a/rust/kernel/lib.rs +++ b/rust/kernel/lib.rs @@ -72,6 +72,7 @@ pub mod bug; #[doc(hidden)] pub mod build_assert; +pub mod clist; pub mod clk; #[cfg(CONFIG_CONFIGFS_FS)] pub mod configfs; -- 2.34.1
