Hi Joel, This low-level layer looks mostly ok to me, I will have more comments on the higher layer though.
On Wed Nov 12, 2025 at 2:13 AM JST, Joel Fernandes wrote: > Add foundational types for working with C's doubly circular linked > lists (list_head). Provide low-level iteration over list nodes. > > Typed iteration over actual items will be added in a follow-up > commit using the FromListHead trait and ClistLink mechanism. > > Signed-off-by: Joel Fernandes <[email protected]> > --- > rust/kernel/clist.rs | 190 +++++++++++++++++++++++++++++++++++++++++++ > rust/kernel/lib.rs | 1 + > 2 files changed, 191 insertions(+) > create mode 100644 rust/kernel/clist.rs > > diff --git a/rust/kernel/clist.rs b/rust/kernel/clist.rs > new file mode 100644 > index 000000000000..5ea505d463ad > --- /dev/null > +++ b/rust/kernel/clist.rs > @@ -0,0 +1,190 @@ > +// SPDX-License-Identifier: GPL-2.0 > + > +//! A C doubly circular intrusive linked list interface for rust code. > +//! > +//! TODO: Doctest example will be added in later commit in series due to > dependencies. Since it is added in the following patch, I guess we can do without this very temporary TODO. :) > + > +use crate::{ > + bindings, > + types::Opaque, // > +}; > + > +/// A C linked list with a sentinel head Nit: '.' at end of sentence. > +/// > +/// A sentinel head is one which is not embedded in an item. It represents > the entire > +/// linked list and can be used for add, remove, empty operations etc. > +/// > +/// # Invariants > +/// > +/// - `Clist` wraps an allocated and valid C list_head structure that is the > sentinel of a list. > +/// - All the `list_head` nodes in the list are allocated and have valid > next/prev pointers. > +/// - The underlying `list_head` (and entire list) is not modified by C. These last two ones look more like safety requirements to maintain for the life of a Clist than invariants. > +#[repr(transparent)] > +pub struct Clist(ClistHead); `ClistHead`'s definition should come before `Clist` for clarity. > + > +// SAFETY: `Clist` can be sent to any thread. > +unsafe impl Send for Clist {} > +// SAFETY: `Clist` can be shared among threads as it is not modified by C > per type invariants. > +unsafe impl Sync for Clist {} These explicit impls should not be needed - as `ClistHead` implements `Send` and `Sync`, they will be automatically derived for `Clist` which just wraps it. > + > +impl Clist { > + /// Create a `&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, and it must remain valid 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 for 'a. > + unsafe { &*ptr.cast() } Let's reuse `ClistHead::from_raw` here. > + } > + > + /// Get the raw sentinel `list_head` pointer. > + #[inline] > + pub fn as_raw(&self) -> *mut bindings::list_head { > + self.0.as_raw() > + } > + > + /// Access the underlying `ClistHead`. > + #[inline] > + pub fn head(&self) -> &ClistHead { > + &self.0 > + } > + > + /// Check if the list is empty. > + #[inline] > + pub fn is_empty(&self) -> bool { > + self.0.is_empty() > + } > + > + /// Create a low-level iterator over `ClistHead` nodes. Caller converts > the returned > + /// heads into items. > + #[inline] > + pub fn iter_heads(&self) -> ClistHeadIter<'_> { > + ClistHeadIter { > + current: &self.0, > + head: &self.0, > + } > + } > +} > + > +/// Wraps a non-sentinel C `list_head` node for use in intrusive linked > lists. This says "non-sentinel", but `Clist` embeds a `ClistHead` which wraps a sentinel node, so that statement does not seem to be true. > +/// > +/// # Invariants > +/// > +/// - `ClistHead` represents an allocated and valid non-sentinel `list_head` > structure. > +/// - The underlying `list_head` (and entire list) is not modified by C. > +#[repr(transparent)] > +pub struct ClistHead(Opaque<bindings::list_head>); > + > +// 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 > C per type invariants. > +unsafe impl Sync for ClistHead {} > + > +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, > + /// and it must remain valid 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 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 { > + // SAFETY: > + // - `self.as_raw()` is valid per type invariants. > + // - The `next` pointer is guaranteed to be non-NULL. > + unsafe { > + let raw = self.as_raw(); This line doesn't need to be in the `unsafe` block (also applies to other methods). > + Self::from_raw((*raw).next) > + } > + } > + > + /// Get the previous `ClistHead` in the list. > + #[inline] > + pub fn prev(&self) -> &Self { > + // SAFETY: > + // - self.as_raw() is valid per type invariants. > + // - The `prev` pointer is guaranteed to be non-NULL. > + unsafe { > + let raw = self.as_raw(); > + Self::from_raw((*raw).prev) > + } > + } > + > + /// Check if this node is linked in a list (not isolated). > + #[inline] > + pub fn is_in_list(&self) -> bool { > + // SAFETY: self.as_raw() is valid per type invariants. > + unsafe { > + let raw = self.as_raw(); > + (*raw).next != raw && (*raw).prev != raw > + } > + } > + > + /// Check if the list is empty. > + #[inline] > + pub fn is_empty(&self) -> bool { > + // SAFETY: self.as_raw() is valid per type invariants. > + unsafe { > + let raw = self.as_raw(); > + (*raw).next == raw > + } > + } Does this method also apply to non-sentinel nodes? If not, should we move it to `Clist`? I am also wondering what the difference is with `is_in_list`. If `raw.next == raw`, then on a valid list `raw.prev == raw` as well, so it seems to be that `is_in_list()` is equivalent to `!is_empty()`. > +} > + > +/// 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 (typically using > `container_of` macro). > +/// > +/// # Invariants > +/// > +/// `ClistHeadIter` is iterating over an allocated, initialized and valid > `Clist`. > +pub struct ClistHeadIter<'a> { > + current: &'a ClistHead, > + head: &'a ClistHead, IIUC `head` should probably be a `Clist`? > +} > + > +// SAFETY: ClistHeadIter gives out immutable references to ClistHead, > +// which is Send. > +unsafe impl Send for ClistHeadIter<'_> {} > + > +// SAFETY: ClistHeadIter gives out immutable references to ClistHead, > +// which is Sync. > +unsafe impl Sync for ClistHeadIter<'_> {} `Send` and `Sync` will also be auto-implemented here. > + > +impl<'a> Iterator for ClistHeadIter<'a> { > + type Item = &'a ClistHead; > + > + #[inline] > + fn next(&mut self) -> Option<Self::Item> { > + // Advance to next node. > + self.current = self.current.next(); > + > + // Check if we've circled back to HEAD. > + if self.current.as_raw() == self.head.as_raw() { Maybe derive/implement `PartialEq` so we can avoid calling `as_raw` when comparing nodes.
