[PATCH v2 2/3] rust: clist: Add basic list infrastructure and head iterator

[Joel Fernandes]

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 <joelagnelf@xxxxxxxxxx>
---
 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.
+
+use crate::{
+    bindings,
+    types::Opaque, //
+};
+
+/// A C linked list with a sentinel head
+///
+/// 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.
+#[repr(transparent)]
+pub struct Clist(ClistHead);
+
+// 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 {}
+
+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() }
+    }
+
+    /// 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.
+///
+/// # 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();
+            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
+        }
+    }
+}
+
+/// 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,
+}
+
+// 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<'_> {}
+
+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() {
+            return None;
+        }
+
+        Some(self.current)
+    }
+}
diff --git a/rust/kernel/lib.rs b/rust/kernel/lib.rs
index c2eea9a2a345..b69cc5ed3b59 100644
--- a/rust/kernel/lib.rs
+++ b/rust/kernel/lib.rs
@@ -72,6 +72,7 @@
 pub mod bug;
 #[doc(hidden)]
 pub mod build_assert;
+pub mod clist;
 pub mod clk;
 #[cfg(CONFIG_CONFIGFS_FS)]
 pub mod configfs;
-- 
2.34.1