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

Gary Guo
2026-01-22T13:38:43Z

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.