Message-Id: <20251030190613.1224287-2-joelagnelf@nvidia.com>
Date: Thu, 30 Oct 2025 15:06:10 -0400
From: Joel Fernandes <joelagnelf@...dia.com>
To: linux-kernel@...r.kernel.org,
	rust-for-linux@...r.kernel.org,
	dri-devel@...ts.freedesktop.org,
	dakr@...nel.org,
	David Airlie <airlied@...il.com>
Cc: acourbot@...dia.com,
	Alistair Popple <apopple@...dia.com>,
	Miguel Ojeda <ojeda@...nel.org>,
	Alex Gaynor <alex.gaynor@...il.com>,
	Boqun Feng <boqun.feng@...il.com>,
	Gary Guo <gary@...yguo.net>,
	bjorn3_gh@...tonmail.com,
	Benno Lossin <lossin@...nel.org>,
	Andreas Hindborg <a.hindborg@...nel.org>,
	Alice Ryhl <aliceryhl@...gle.com>,
	Trevor Gross <tmgross@...ch.edu>,
	Simona Vetter <simona@...ll.ch>,
	Maarten Lankhorst <maarten.lankhorst@...ux.intel.com>,
	Maxime Ripard <mripard@...nel.org>,
	Thomas Zimmermann <tzimmermann@...e.de>,
	John Hubbard <jhubbard@...dia.com>,
	Joel Fernandes <joelagnelf@...dia.com>,
	Timur Tabi <ttabi@...dia.com>,
	joel@...lfernandes.org,
	Elle Rhumsaa <elle@...thered-steel.dev>,
	Daniel Almeida <daniel.almeida@...labora.com>,
	Andrea Righi <arighi@...dia.com>,
	Philipp Stanner <phasta@...nel.org>,
	nouveau@...ts.freedesktop.org
Subject: [PATCH RFC 1/4] rust: clist: Add abstraction for iterating over C linked lists

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 <joelagnelf@...dia.com>
---
 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

Powered by blists - more mailing lists