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

["Gary Guo" <gary@garyguo.net>]

On Wed Jan 21, 2026 at 7:50 PM GMT, Joel Fernandes wrote:
> 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.

Definitely not with the existing one that we have, as it handles only `Arc`.
But the existing abstraction is also not good enough if you want to insert
`Box`...

>
> [...]
>>> +
>>> +/// 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?

Oh yes, this would definitely happen. It's down to LLVM to compile anyway. If
you create a reference, there'll be even more freedom to do these.

>
> 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.

Overall our practice is to not duplicate code. Even `ERR_PTR` is calling into
helpers.

For performance, it's a valid concern. However Alice and I have series out there
that enable you to inline the helpers. I'd say unless there's an absolute need,
we should do the helpers. Especially with caveats like WRITE_ONCE in this case.

>
> 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:

This is not really a public user. It's hidden in the doc test too, you could
initialize using try_init too.

>
> //! # 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.
>

The important part is to make sure we don't deviate from C implementation. A
copy is already not good, and difference is worse.

>> 
>>> +    }
>>> +
>>> +    /// 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,
>         });

The list initialization doesn't fail? It's the subsequent action you did that
failed.

You can put failing things in the `_: { ... }` block too.

>
>> 
>> 
>>> +            })
>>> +        }
>>> +    }
>>> +}
>>> +
>>> +// 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.

Yes, with `#[repr(transparent)]`.

>>> +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`...

Yes.

Best,
Gary

>
>>> +///
>>> +/// # 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.