Re: [PATCH RFC v6 01/26] rust: clist: Add support to interface with C linked lists

[Joel Fernandes <joelagnelf@nvidia.com>]

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/DEI89VUEYXAJ.1IQQPC3QRLITP@nvidia.com/

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