Hello, Gary,
On 1/20/2026 6:48 PM, Gary Guo wrote:
> On Tue Jan 20, 2026 at 8:42 PM GMT, Joel Fernandes wrote:
>> Add a new module `clist` for working with C's doubly circular linked
>> lists. Provide low-level iteration over list nodes.
>>
>> Typed iteration over actual items is provided with a `clist_create`
>> macro to assist in creation of the `Clist` type.
>
> This should read "CList".
Sure, will fix.
>
> I was quite dubious about the patch just from the title (everybody knows how
> easy a linked list is in Rust), but it turns out it is not as concerning as I
> expected, mostly due to the read-only nature of the particular implementation
> (a lot of the safety comments would be much more difficult to justify, say, if
> it's mutable). That said, still a lot of feedbacks below.
Sure, the reason for requiring this is interfacing with lists coming from C
code. I'd see a future where we may want it mutable too (example, Rust code
adding elements to the existing). At which point, the invariants/safety
reasoning may change.
> I think something like is okay in the short term. However, there's an growing
> interest in getting our Rust list API improved, so it could be ideal if
> eventually the Rust list can be capable of handling FFI lists, too.
Yeah we looked into that, if you see old threads, the conclusion was it is not a
good fit for existing rust list abstractions. TLDR; it does not fit into their
ownership/borrowing model.
[...]
>> +
>> +/// Initialize a `list_head` object to point to itself.
>> +///
>> +/// # Safety
>> +///
>> +/// `list` must be a valid pointer to a `list_head` object.
>> +#[inline]
>> +pub unsafe fn init_list_head(list: *mut bindings::list_head) {
>> + // SAFETY: Caller guarantees `list` is a valid pointer to a `list_head`.
>> + unsafe {
>> + (*list).next = list;
>> + (*list).prev = list;
>
> This needs to be an atomic write or it'll depart from the C implementation.
I am curious what you mean by atomic write, can you define it? Does rust
compiler have load/store fusing, invented stores, etc, like C does? Sorry I am
only familiar with these concepts on C. Could you provide example of a race
condition in Rust that can happen?
Also I did this addition based on feedback from past review:
https://lore.kernel.org/all/[email protected]/
There was some concerns around pointless function call overhead when the rust
implementation is already quite intertwined with internals of the C linked list
implementation. I do agree with that point of view too.
Also see my other reply to Zhi on this helper topic, lets discuss there too, if
that's Ok.
>> + }
>> +}
>
> I don't think we want to publicly expose this! I've not found a user in the
> subsequent patch, too.
There are 2 users:
pub fn try_init<E>(
and the self-tests:
//! # let head = head.as_mut_ptr();
//! # // SAFETY: head and all the items are test objects allocated in [..]
//! # unsafe { init_list_head(head) };
//! #
>
>> +
>> +/// Wraps a `list_head` object for use in intrusive linked lists.
>> +///
>> +/// # Invariants
>> +///
>> +/// - [`CListHead`] represents an allocated and valid `list_head` structure.
>> +/// - Once a [`CListHead`] is created in Rust, it will not be modified by
>> non-Rust code.
>> +/// - All `list_head` for individual items are not modified for the
>> lifetime of [`CListHead`].
>> +#[repr(transparent)]
>> +pub struct CListHead(Opaque<bindings::list_head>);
>> +
>> +impl CListHead {
>> + /// Create a `&CListHead` reference from a raw `list_head` pointer.
>> + ///
>> + /// # Safety
>> + ///
>> + /// - `ptr` must be a valid pointer to an allocated and initialized
>> `list_head` structure.
>> + /// - `ptr` must remain valid and unmodified for the lifetime `'a`.
>> + #[inline]
>> + pub unsafe fn from_raw<'a>(ptr: *mut bindings::list_head) -> &'a Self {
>> + // SAFETY:
>> + // - [`CListHead`] has same layout as `list_head`.
>> + // - `ptr` is valid and unmodified for 'a.
>> + unsafe { &*ptr.cast() }
>> + }
>> +
>> + /// Get the raw `list_head` pointer.
>> + #[inline]
>> + pub fn as_raw(&self) -> *mut bindings::list_head {
>> + self.0.get()
>> + }
>> +
>> + /// Get the next [`CListHead`] in the list.
>> + #[inline]
>> + pub fn next(&self) -> &Self {
>> + let raw = self.as_raw();
>> + // SAFETY:
>> + // - `self.as_raw()` is valid per type invariants.
>> + // - The `next` pointer is guaranteed to be non-NULL.
>> + unsafe { Self::from_raw((*raw).next) }
>> + }
>> +
>> + /// Get the previous [`CListHead`] in the list.
>> + #[inline]
>> + pub fn prev(&self) -> &Self {
>> + let raw = self.as_raw();
>> + // SAFETY:
>> + // - self.as_raw() is valid per type invariants.
>> + // - The `prev` pointer is guaranteed to be non-NULL.
>> + unsafe { Self::from_raw((*raw).prev) }
>> + }
>> +
>> + /// Check if this node is linked in a list (not isolated).
>> + #[inline]
>> + pub fn is_linked(&self) -> bool {
>> + let raw = self.as_raw();
>> + // SAFETY: self.as_raw() is valid per type invariants.
>> + unsafe { (*raw).next != raw && (*raw).prev != raw }
>
> While is this checking both prev and next? `list_empty` is just
> `READ_ONCE(head->next) == head`.
Sure, I can optimize to just check ->next, that makes sense. Will do.
>
>> + }
>> +
>> + /// Fallible pin-initializer that initializes and then calls user
>> closure.
>> + ///
>> + /// Initializes the list head first, then passes `&CListHead` to the
>> closure.
>> + /// This hides the raw FFI pointer from the user.
>> + pub fn try_init<E>(
>> + init_func: impl FnOnce(&CListHead) -> Result<(), E>,
>> + ) -> impl PinInit<Self, E> {
>> + // SAFETY: init_list_head initializes the list_head to point to
>> itself.
>> + // After initialization, we create a reference to pass to the
>> closure.
>> + unsafe {
>> + pin_init::pin_init_from_closure(move |slot: *mut Self| {
>> + init_list_head(slot.cast());
>> + // SAFETY: slot is now initialized, safe to create
>> reference.
>> + init_func(&*slot)
>
> Why is this callback necessary? The user can just create the list head and
> then reference it later? I don't see what this specifically gains over just
> doing
>
> fn new() -> impl PinInit<Self>;
>
> and have user-side
>
> list <- CListHead::new(),
> _: {
> do_want_ever(&list)
> }
The list initialization can fail, see the GPU buddy patch:
// Create pin-initializer that initializes list and allocates blocks.
let init = try_pin_init!(AllocatedBlocks {
list <- CListHead::try_init(|list| {
// Lock while allocating to serialize with concurrent frees.
let guard = buddy_arc.lock();
// SAFETY: guard provides exclusive access, list is initialized.
to_result(unsafe {
bindings::gpu_buddy_alloc_blocks(
guard.as_raw(),
params.start_range_address,
params.end_range_address,
params.size_bytes,
params.min_block_size_bytes,
list.as_raw(),
params.buddy_flags.as_raw(),
)
})
}),
buddy: Arc::clone(&buddy_arc),
flags: params.buddy_flags,
});
>
>
>> + })
>> + }
>> + }
>> +}
>> +
>> +// SAFETY: [`CListHead`] can be sent to any thread.
>> +unsafe impl Send for CListHead {}
>> +
>> +// SAFETY: [`CListHead`] can be shared among threads as it is not modified
>> +// by non-Rust code per type invariants.
>> +unsafe impl Sync for CListHead {}
>> +
>> +impl PartialEq for CListHead {
>> + fn eq(&self, other: &Self) -> bool {
>> + self.as_raw() == other.as_raw()
>
> Or just `core::ptr::eq(self, other)`
Sure, will fix.
>
>> + }
>> +}
>> +
>> +impl Eq for CListHead {}
>> +
>> +/// Low-level iterator over `list_head` nodes.
>> +///
>> +/// An iterator used to iterate over a C intrusive linked list
>> (`list_head`). Caller has to
>> +/// perform conversion of returned [`CListHead`] to an item (using
>> `container_of` macro or similar).
>> +///
>> +/// # Invariants
>> +///
>> +/// [`CListHeadIter`] is iterating over an allocated, initialized and valid
>> list.
>> +struct CListHeadIter<'a> {
>> + current_head: &'a CListHead,
>> + list_head: &'a CListHead,
>> +}
>> +
>> +impl<'a> Iterator for CListHeadIter<'a> {
>> + type Item = &'a CListHead;
>> +
>> + #[inline]
>> + fn next(&mut self) -> Option<Self::Item> {
>> + // Advance to next node.
>> + let next = self.current_head.next();
>> +
>> + // Check if we've circled back to the sentinel head.
>> + if next == self.list_head {
>> + None
>> + } else {
>> + self.current_head = next;
>> + Some(self.current_head)
>> + }
>
> I think this could match the C iterator behaviour. When the iterator is
> created,
> a `next` is done first, and then subsequently you only need to check if
> `current_head` is `list_head`.
>
> This is slightly better because the condition check does not need to
> dereference
> a pointer.
Sure, I can change it to that.
>> +impl<'a> FusedIterator for CListHeadIter<'a> {}
>> +
>> +/// A typed C linked list with a sentinel head.
>> +///
>> +/// A sentinel head represents the entire linked list and can be used for
>> +/// iteration over items of type `T`, it is not associated with a specific
>> item.
>> +///
>> +/// The const generic `OFFSET` specifies the byte offset of the `list_head`
>> field within
>> +/// the struct that `T` wraps.
>> +///
>> +/// # Invariants
>> +///
>> +/// - `head` is an allocated and valid C `list_head` structure that is the
>> list's sentinel.
>> +/// - `OFFSET` is the byte offset of the `list_head` field within the
>> struct that `T` wraps.
>> +/// - All the list's `list_head` nodes are allocated and have valid
>> next/prev pointers.
>> +/// - The underlying `list_head` (and entire list) is not modified for the
>> lifetime `'a`.
>> +pub struct CList<'a, T, const OFFSET: usize> {
>> + head: &'a CListHead,
>> + _phantom: PhantomData<&'a T>,
>> +}
>
> Is there a reason that this is not
>
> #[repr(transparent)]
> struct CList(CListHead)
>
> ? We typically want to avoid putting reference inside the struct if it can be
> on
> the outside. This allows `&self` to be a single level of reference, not too.
>
> It also means that you can just write `&CList<_>` in many cases, and doesn't
> need
> `CList<'_, T>` (plus all the benefits of a reference).
Sure! Will change to this. I am guessing you mean the following, but please let
me know if you meant something else:
pub struct CList<T, const OFFSET: usize>(
CListHead,
PhantomData<T>,
);
I don't see any issues with my code using that, at the moment. Will let you know
how it goes.
>> +impl<'a, T, const OFFSET: usize> CList<'a, T, OFFSET> {
>> + /// Create a typed [`CList`] from a raw sentinel `list_head` pointer.
>> + ///
>> + /// # Safety
>> + ///
>> + /// - `ptr` must be a valid pointer to an allocated and initialized
>> `list_head` structure
>> + /// representing a list sentinel.
>> + /// - `ptr` must remain valid and unmodified for the lifetime `'a`.
>> + /// - The list must contain items where the `list_head` field is at
>> byte offset `OFFSET`.
>> + /// - `T` must be `#[repr(transparent)]` over the C struct.
>> + #[inline]
>> + pub unsafe fn from_raw(ptr: *mut bindings::list_head) -> Self {
>> + Self {
>> + // SAFETY: Caller guarantees `ptr` is a valid, sentinel
>> `list_head` object.
>> + head: unsafe { CListHead::from_raw(ptr) },
>> + _phantom: PhantomData,
>> + }
>> + }
>> +
>> + /// Get the raw sentinel `list_head` pointer.
>> + #[inline]
>> + pub fn as_raw(&self) -> *mut bindings::list_head {
>> + self.head.as_raw()
>> + }
>> +
>> + /// Check if the list is empty.
>> + #[inline]
>> + pub fn is_empty(&self) -> bool {
>> + let raw = self.as_raw();
>> + // SAFETY: self.as_raw() is valid per type invariants.
>> + unsafe { (*raw).next == raw }
>
> `self.head.is_linked()`?
I'd considered `is_linked()` to be something that makes sense to call only on
`ClistHead` objects that belong to a particular "item" node, not a sentinel
node, so that was deliberate.
Though, I am Ok with doing it the way you are suggesting too
(`self.head.is_linked()`), since it is functionally equivalent.
>> + }
>> +
>> + /// Create an iterator over typed items.
>> + #[inline]
>> + pub fn iter(&self) -> CListIter<'a, T, OFFSET> {
>> + CListIter {
>> + head_iter: CListHeadIter {
>> + current_head: self.head,
>> + list_head: self.head,
>> + },
>> + _phantom: PhantomData,
>> + }
>> + }
>> +}
>> +
>> +/// High-level iterator over typed list items.
>> +pub struct CListIter<'a, T, const OFFSET: usize> {
>> + head_iter: CListHeadIter<'a>,
>> + _phantom: PhantomData<&'a T>,
>> +}
>> +
>> +impl<'a, T, const OFFSET: usize> Iterator for CListIter<'a, T, OFFSET> {
>> + type Item = &'a T;
>> +
>> + fn next(&mut self) -> Option<Self::Item> {
>> + let head = self.head_iter.next()?;
>> +
>> + // Convert to item using OFFSET.
>> + // SAFETY: `item_ptr` calculation from `OFFSET` (calculated using
>> offset_of!)
>> + // is valid per invariants.
>> + Some(unsafe { &*head.as_raw().byte_sub(OFFSET).cast::<T>() })
>> + }
>> +}
>> +
>> +impl<'a, T, const OFFSET: usize> FusedIterator for CListIter<'a, T, OFFSET>
>> {}
>> +
>> +/// Create a C doubly-circular linked list interface [`CList`] from a raw
>> `list_head` pointer.
>> +///
>> +/// This macro creates a [`CList<T, OFFSET>`] that can iterate over items
>> of type `$rust_type`
>> +/// linked via the `$field` field in the underlying C struct `$c_type`.
>> +///
>> +/// # Arguments
>> +///
>> +/// - `$head`: Raw pointer to the sentinel `list_head` object (`*mut
>> bindings::list_head`).
>> +/// - `$rust_type`: Each item's rust wrapper type.
>> +/// - `$c_type`: Each item's C struct type that contains the embedded
>> `list_head`.
>> +/// - `$field`: The name of the `list_head` field within the C struct.
>> +///
>> +/// # Safety
>> +///
>> +/// The caller must ensure:
>> +/// - `$head` is a valid, initialized sentinel `list_head` pointing to a
>> list that remains
>> +/// unmodified for the lifetime of the rust [`CList`].
>> +/// - The list contains items of type `$c_type` linked via an embedded
>> `$field`.
>> +/// - `$rust_type` is `#[repr(transparent)]` over `$c_type` or has
>> compatible layout.
>> +/// - The macro is called from an unsafe block.
>
> This is not a safe requirement, probably lift it up and say "This is an unsafe
> macro.".
Sure, so like this then:
/// This is an unsafe macro. The caller must ensure:
/// - `$head` is a valid, initialized sentinel `list_head`...
>> +///
>> +/// # Examples
>> +///
>> +/// Refer to the examples in the [`crate::clist`] module documentation.
>> +#[macro_export]
>> +macro_rules! clist_create {
>> + ($head:expr, $rust_type:ty, $c_type:ty, $($field:tt).+) => {{
>> + // Compile-time check that field path is a list_head.
>> + let _: fn(*const $c_type) -> *const $crate::bindings::list_head =
>> + |p| ::core::ptr::addr_of!((*p).$($field).+);
>
> `&raw const` is preferred now.
Sure, will fix.
>
>> +
>> + // Calculate offset and create `CList`.
>> + const OFFSET: usize = ::core::mem::offset_of!($c_type, $($field).+);
>> + $crate::clist::CList::<$rust_type, OFFSET>::from_raw($head)
>> + }};
>> +}
>> diff --git a/rust/kernel/lib.rs b/rust/kernel/lib.rs
>> index f812cf120042..cd7e6a1055b0 100644
>> --- a/rust/kernel/lib.rs
>> +++ b/rust/kernel/lib.rs
>> @@ -75,6 +75,7 @@
>> pub mod bug;
>> #[doc(hidden)]
>> pub mod build_assert;
>> +pub mod clist;
>
> Can we keep this pub(crate)?
Yes, will do.
--
Joel Fernandes
