rust: helpers: Add list helpers for C linked list operations
PATCH v2 1/3 rust: helpers: Add list helpers for C linked list operations
Add Rust helper functions for common C linked list operations that are implemented as macros or inline functions and thus not directly accessible from Rust.
--- rust/helpers/helpers.c | 1 + rust/helpers/list.c | 32 ++++++++++++++++++++++++++++++++ 2 files changed, 33 insertions(+) create mode 100644 rust/helpers/list.c
rust/helpers/helpers.c +1 -0
@@ -32,6 +32,7 @@#include "io.c" #include "jump_label.c" #include "kunit.c" +#include "list.c" #include "maple_tree.c" #include "mm.c" #include "mutex.c"
rust/helpers/list.c new file +32 -0
@@ -0,0 +1,32 @@ +// SPDX-License-Identifier: GPL-2.0 + +/* +* Helpers for C Circular doubly linked list implementation. +*/ + +#include <linux/list.h> + +bool rust_helper_list_empty (const struct list_head *head) +{ +return list_empty (head); +} + +void rust_helper_list_del (struct list_head *entry) +{ +list_del (entry); +} + +void rust_helper_INIT_LIST_HEAD (struct list_head *list) +{ +INIT_LIST_HEAD (list); +} + +void rust_helper_list_add (struct list_head *new,struct list_head *head) +{ +list_add (new, head); +} + +void rust_helper_list_add_tail (struct list_head *new,struct list_head *head) +{ +list_add_tail (new, head); +}
Signature · 1 line
2.34.1
PATCH v2 2/3 rust: clist: Add basic list infrastructure and head iterator
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.
--- rust/kernel/clist.rs | 190 +++++++++++++++++++++++++++++++++++++++++++ rust/kernel/lib.rs | 1 + 2 files changed, 191 insertions(+) create mode 100644 rust/kernel/clist.rs
rust/kernel/clist.rs new file +190 -0
@@ -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 ) -> &'aSelf { +// 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 ) -> &'aSelf { +// 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: &'aClistHead , + head: &'aClistHead , +} + +// 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 = &'aClistHead ; + +#[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) + } +}
rust/kernel/lib.rs +1 -0
@@ -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;
Signature · 1 line
2.34.1
Alexandre Courbot
reviewerRe: [PATCH v2 2/3] rust: clist: Add basic list infrastructure and head iterator
Hi Joel,
This low-level layer looks mostly ok to me, I will have more comments on the higher layer though.
Quoted 19 lines · 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 <[email protected]>--- rust/kernel/clist.rs | 190 +++++++++++++++++++++++++++++++++++++++++++ rust/kernel/lib.rs | 1 + 2 files changed, 191 insertions(+) create mode 100644 rust/kernel/clist.rsrust/kernel/clist.rs new file +0
-0
rust/kernel/clist.rs line 5
Quoted 5 lines
rust/kernel/clist.rs new file +5
-0@@ -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. :)
rust/kernel/clist.rs line 12
Quoted 7 lines
rust/kernel/clist.rs new file +7
-0+ +use crate ::{ + bindings, + types::Opaque ,// +}; + +/// A C linked list with a sentinel head
Nit: '.' at end of sentence.
rust/kernel/clist.rs line 21
Quoted 9 lines
rust/kernel/clist.rs new file +9
-0+/// +/// 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.
rust/kernel/clist.rs line 23
Quoted 2 lines
rust/kernel/clist.rs new file +2
-0+#[repr(transparent)] +pub struct Clist (ClistHead );
ClistHead's definition should come before Clist for clarity.
rust/kernel/clist.rs line 28
Quoted 5 lines
rust/kernel/clist.rs new file +5
-0+ +// 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.
Quoted 4 lines
rust/kernel/clist.rs new file +4
-0+ +impl Clist { +/// Create a `&Clist` from a raw sentinel `list_head` pointer. +///
rust/kernel/clist.rs line 42
Quoted 10 lines
rust/kernel/clist.rs new file +10
-0+/// # 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 ) -> &'aSelf { +// SAFETY: +// - `ClistHead` has same layout as `list_head`. +// - `ptr` is valid for 'a. +unsafe { &*ptr.cast () }
Let's reuse ClistHead::from_raw here.
Quoted 22 lines
rust/kernel/clist.rs new file +22
-0+ } + +/// 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.
rust/kernel/clist.rs line 74
Quoted 10 lines
rust/kernel/clist.rs new file +10
-0+#[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.
Quoted 32 lines
rust/kernel/clist.rs new file +32
-0+/// +/// # 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 ) -> &'aSelf { +// 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 ()
rust/kernel/clist.rs line 116
Quoted 10 lines
rust/kernel/clist.rs new file +10
-0+ } + +/// 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).
Quoted 25 lines
rust/kernel/clist.rs new file +25
-0+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 + } + }
rust/kernel/clist.rs line 151
Quoted 10 lines
rust/kernel/clist.rs new file +10
-0+ +/// 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().
rust/kernel/clist.rs line 164
Quoted 13 lines
rust/kernel/clist.rs new file +13
-0+} + +/// 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: &'aClistHead , + head: &'aClistHead ,
IIUC head should probably be a Clist?
rust/kernel/clist.rs line 173
Quoted 9 lines
rust/kernel/clist.rs new file +9
-0+} + +// 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.
rust/kernel/clist.rs line 184
Quoted 11 lines
rust/kernel/clist.rs new file +11
-0+ +impl <'a>Iterator for ClistHeadIter <'a> { +type Item = &'aClistHead ; + +#[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.
Re: [PATCH v2 2/3] rust: clist: Add basic list infrastructure and head iterator
Hi Alex,
(I agree with all the suggestions, I will reply to the ones where I have comments in a few emails if that's Ok.).
Replied to one below:
Quoted 16 lines · Alexandre Courbot
Quoted 16 lines
rust/kernel/clist.rs new file +16
-0+ } + +/// 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.
Quoted 8 lines
rust/kernel/clist.rs line 151
Quoted 5 lines
rust/kernel/clist.rs new file +5
-0+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?
Yes it does, will move it.
Quoted 4 lines
I am also wondering what the difference is with
is_in_list. Ifraw.next == raw, then on a valid listraw.prev == rawas well, so it seems to be thatis_in_list()is equivalent to!is_empty().
Yes, this is a good thing for me to refactor. We can keep is_in_list() in ClistHead and move ClistHead::Empty() to Clist. Though I would probably directly compare the pointers instead of calling is_in_list() because it seems weird to check with a sentinel list_head about whether it is in the list :) After all, it IS the list :-D. I will rearrange it, thanks for the suggestion!
- Joel
Re: [PATCH v2 2/3] rust: clist: Add basic list infrastructure and head iterator
In reply to Alexandre CourbotQuoted 7 lines · Alexandre Courbot
Quoted 7 lines
rust/kernel/clist.rs new file +7
-0+} + +/// 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). +///
Quoted 8 lines
rust/kernel/clist.rs line 164
Quoted 6 lines
rust/kernel/clist.rs new file +6
-0+/// # Invariants +/// +/// `ClistHeadIter` is iterating over an allocated, initialized and valid `Clist`. +pub struct ClistHeadIter <'a> { + current: &'aClistHead , + head: &'aClistHead ,IIUC
headshould probably be aClist?
Sure, but then I would rename it from 'head' to 'list' then, if that's Ok.
The iterator holds the list, and the current position, which makes sense to me.
thanks,
- Joel
- Joel
Daniel Almeida
reviewerRe: [PATCH v2 2/3] rust: clist: Add basic list infrastructure and head iterator
In reply to Joel FernandesHi Joel,
Quoted 26 lines · 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 <[email protected]>---
rust/kernel/clist.rs| 190 +++++++++++++++++++++++++++++++++++++++++++rust/kernel/lib.rs| 1 +2 files changed, 191 insertions(+)create mode 100644
rust/kernel/clist.rsrust/kernel/clist.rs new file +5
-0@@ -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.
rust/kernel/clist.rs line 15
Quoted 10 lines
rust/kernel/clist.rs new file +10
-0+ +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.
nit: IMHO, the phrasing can improve here.
rust/kernel/clist.rs line 28
Quoted 13 lines
rust/kernel/clist.rs new file +13
-0+/// +/// # 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 {}
Please keep "struct Foo" and "impl Foo” adjacent to the extent possible.
rust/kernel/clist.rs line 30
Quoted 2 lines
rust/kernel/clist.rs new file +2
-0+ +impl Clist {
IMHO, we should capitalize the L as well, i.e.: CList.
rust/kernel/clist.rs line 36
Quoted 6 lines
rust/kernel/clist.rs new file +6
-0+/// 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`.
Rust reference rules must also be upheld for ‘a. i.e.: nobody else can mutate through this pointer, including the C code.
Quoted 32 lines
rust/kernel/clist.rs new file +32
-0+#[inline] +pub unsafe fn from_raw <'a>(ptr: *mut bindings::list_head ) -> &'aSelf { +// 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 ,
rust/kernel/clist.rs line 78
Quoted 10 lines
rust/kernel/clist.rs new file +10
-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.
Perhaps a blank here?
rust/kernel/clist.rs line 86
Quoted 8 lines
rust/kernel/clist.rs new file +8
-0+/// - 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 {}
Same comment here about Foo and impl Foo.
Quoted 39 lines
rust/kernel/clist.rs new file +39
-0+ +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 ) -> &'aSelf { +// 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.
rust/kernel/clist.rs line 135
Quoted 10 lines
rust/kernel/clist.rs new file +10
-0+// - 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 {
is_linked()?
Quoted 71 lines
rust/kernel/clist.rs new file +55
-0+// 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: &'aClistHead , + head: &'aClistHead , +} + +// 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 = &'aClistHead ; + +#[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) + } +}rust/kernel/lib.rs +1
-0@@ -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;Signature · 1 line
2.34.1
PATCH v2 3/3 rust: clist: Add typed iteration with FromListHead trait
In reply to Joel FernandesAdd an iteration layer on top of the basic list infrastructure, enabling iteration over the actual container items.
Enables users to iterate over actual items without manually performing container_of operations. Provide macros to make caller's life easier.
--- rust/kernel/clist.rs | 210 ++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 207 insertions(+), 3 deletions(-)
rust/kernel/clist.rs +207 -3
@@ -2,17 +2,104 @@//! 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. +//! # Examples +//! +//! ``` +//! use kernel::{bindings, clist::Clist, clist_iterate, impl_from_list_head, types::Opaque}; +//! # // Create test list with values (0, 10, 20) - normally done by C code but it is +//! # // emulated here for doctests using the C bindings. +//! # use core::mem::MaybeUninit; +//! # +//! # /// C struct with embedded list_head (typically will be allocated by C code). +//! # #[repr(C)] +//! # pub(crate) struct SampleItemC { +//! # pub value: i32, +//! # pub link: bindings::list_head, +//! # } +//! # +//! # let mut head = MaybeUninit::<bindings::list_head>::uninit(); +//! # +//! # // SAFETY: head and all the items are test objects allocated in this scope. +//! # unsafe { bindings::INIT_LIST_HEAD(head.as_mut_ptr()) }; +//! # // SAFETY: head is a test object allocated in this scope. +//! # let mut head = unsafe { head.assume_init() }; +//! # let mut items = [ +//! # MaybeUninit::<SampleItemC>::uninit(), +//! # MaybeUninit::<SampleItemC>::uninit(), +//! # MaybeUninit::<SampleItemC>::uninit(), +//! # ]; +//! # +//! # for (i, item) in items.iter_mut().enumerate() { +//! # let ptr = item.as_mut_ptr(); +//! # // SAFETY: pointers are to allocated test objects with a list_head field. +//! # unsafe { +//! # (*ptr).value = i as i32 * 10; +//! # bindings::INIT_LIST_HEAD(&mut (*ptr).link); +//! # bindings::list_add_tail(&mut (*ptr).link, &mut head); +//! # } +//! # } +//! +//! // Rust wrapper for the C struct. +//! // The list item struct in this example is defined in C code as: +//! // struct SampleItemC { +//! // int value; +//! // struct list_head link; +//! // }; +//! // +//! #[repr(transparent)] +//! pub(crate) struct Item(Opaque<SampleItemC>); +//! +//! // Generate the link type. +//! impl_from_list_head!(pub(crate), Item, SampleItemC, link); +//! +//! impl Item { +//! pub(crate) fn value(&self) -> i32 { +//! // SAFETY: Item has same layout as SampleItemC. +//! unsafe { (*self.0.get()).value } +//! } +//! } +//! +//! // Create Clist (from a sentinel head). +//! // SAFETY: head is allocated by test code and Clist has the same layout. +//! let list = unsafe { Clist::from_raw(&mut head) }; +//! +//! // Now iterate using clist_iterate! macro. +//! let mut found_0 = false; +//! let mut found_10 = false; +//! let mut found_20 = false; +//! +//! for item in clist_iterate!(list, Item, link) { +//! let val = item.value(); +//! if val == 0 { found_0 = true; } +//! if val == 10 { found_10 = true; } +//! if val == 20 { found_20 = true; } +//! } +//! +//! assert!(found_0 && found_10 && found_20); +//! ``` use crate ::{ bindings, types::Opaque ,// }; +use core::marker::PhantomData ; + +/// Trait for associating a link type with its container item type. +/// +/// Implemented by "field link types" that are `list_head` links embedded in intrusive +/// C linked lists. Each link type is unique to a specific item type and its `list_head` field, +/// making it possible for an item to be added to multiple lists. +pub trait ClistLink { +/// The item type that contains the `list_head` field linking to other items in the list. +type Item :FromListHead <Self > +where +Self :Sized ; +}/// 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. +/// Represents the entire linked list and can be used for add, remove, empty operations etc. +/// A sentinel head is one which is not embedded in an item. /// /// # Invariants ///
@@ -69,6 +156,15 @@ pub fn iter_heads(&self) -> ClistHeadIter<'_> { head: &self.0, } } + +/// Create a high-level iterator over typed items. +#[inline] +pub fn iter <L :ClistLink >(&self) ->ClistIter <'_,L > { +ClistIter { + head_iter: self.iter_heads (), + _phantom:PhantomData , + } + } }/// Wraps a non-sentinel C `list_head` node for use in intrusive linked lists.
@@ -188,3 +284,111 @@ fn next(&mut self) -> Option<Self::Item> {Some (self.current) } } + +/// High-level iterator over typed list items. +pub struct ClistIter <'a,L :ClistLink > { + head_iter:ClistHeadIter <'a>, + +/// The iterator yields immutable references to `L::Item`. + _phantom:PhantomData <&'aL ::Item >, +} + +// SAFETY: ClistIter yields `&L::Item`, which is Send when `L::Item: Send`. +unsafe impl <L :ClistLink >Send for ClistIter <'_,L >where L ::Item :Send {} + +// SAFETY: ClistIter yields &L::Item, which is Sync when `L::Item: Sync`. +unsafe impl <L :ClistLink >Sync for ClistIter <'_,L >where L ::Item :Sync {} + +impl <'a,L :ClistLink >Iterator for ClistIter <'a,L > +where +L ::Item : 'a, +{ +type Item = &'aL ::Item ; + +fn next (&mut self) ->Option <Self ::Item > { +// Get next ClistHead. +let head = self.head_iter.next ()?; + +// Convert to item using trait. +// SAFETY: FromListHead impl guarantees valid conversion. +Some (unsafe {L ::Item ::from_list_head (head) }) + } +} + +/// Trait for converting a `ClistHead` to an item reference. +pub trait FromListHead <Link >:Sized { +/// Convert a `ClistHead` node reference to an item reference. +/// +/// # Safety +/// +/// `head` must be a valid reference to an allocated and initialized `ClistHead` structure +/// valid for the lifetime `'a`. +unsafe fn from_list_head <'a>(head: &'aClistHead ) -> &'aSelf ; +} + +/// Macro to generate `FromListHead` implementations for C list integration. +/// +/// `FromListHead` trait is required to iterate over a C linked list using the `clist_iterate!` +/// macro which yields immutable references to the Rust item wrapper type. +/// +/// Also generates a link type named `Clist<ItemType><field>` implementing the `ClistLink` trait +/// that associates the list node with the item. The link type is used to iterate over the list +/// using the `clist_iterate!` macro. +/// +/// # Arguments +/// +/// - `$vis`: The visibility of the generated link type (e.g., `pub`, `pub(crate)`). +/// - `$item_type`: The Rust wrapper type for items in the list. +/// - `$c_type`: The C struct type that contains the embedded `list_head`. +/// - `$field`: The name of the `list_head` field within the C struct that links items. +/// +/// # Examples +/// +/// Refer to the comprehensive example in the [crate::clist] module documentation. +#[macro_export] +macro_rules! impl_from_list_head { + ($vis:vis, $item_type:ident, $c_type:ty, $field:ident) => { + $crate::macros::paste! { +/// Link type for associating list nodes with items. + $visstruct [<Clist $item_type $field>]; + +// Implement ClistLink trait to associate the link with its item type. +impl $crate ::clist::ClistLink for [<Clist $item_type $field>] { +type Item = $item_type; + } + +impl $crate ::clist::FromListHead <[<Clist $item_type $field>]>for $item_type { +unsafe fn from_list_head <'a>( + head: &'a $crate ::clist::ClistHead , + ) -> &'aSelf { +let ptr = $crate ::container_of!(head.as_raw (), $c_type, $field); +// SAFETY: repr(transparent) makes item_type have same layout as c_type. +// Caller guarantees the container_of calculation is correct. +unsafe { &*ptr.cast ::<Self >() } + } + } + } + }; +} + +/// Macro to assist with iterating over a C linked list. +/// +/// Returns a `ClistIter` iterator which yields immutable references to the `item_type` type. +/// +/// # Arguments +/// +/// - `$list`: The `Clist` instance to iterate over. +/// - `$item_type`: The Rust type of the item in the list with list_head embedded. +/// - `$field`: The name of the field in the `item_type` that links it to the list. +/// +/// # Examples +/// +/// Refer to the comprehensive example in the [crate::clist] module documentation. +#[macro_export] +macro_rules! clist_iterate { + ($list:expr, $item_type:ident, $field:ident) => { + $crate::macros::paste! { + $list.iter::<[<Clist $item_type $field>]>() + } + }; +}
Signature · 1 line
2.34.1
Alexandre Courbot
reviewerRe: [PATCH v2 3/3] rust: clist: Add typed iteration with FromListHead trait
Quoted 91 lines · Joel Fernandes
Add an iteration layer on top of the basic list infrastructure, enabling iteration over the actual container items.
Enables users to iterate over actual items without manually performing
container_ofoperations. Provide macros to make caller's life easier.Signed-off-by Joel Fernandes <[email protected]>--- rust/kernel/clist.rs | 210 ++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 207 insertions(+), 3 deletions(-)rust/kernel/clist.rs +71
-1@@ -2,17 +2,104 @@//! 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. +//! # Examples +//! +//! ``` +//! use kernel::{bindings, clist::Clist, clist_iterate, impl_from_list_head, types::Opaque}; +//! # // Create test list with values (0, 10, 20) - normally done by C code but it is +//! # // emulated here for doctests using the C bindings. +//! # use core::mem::MaybeUninit; +//! # +//! # /// C struct with embedded list_head (typically will be allocated by C code). +//! # #[repr(C)] +//! # pub(crate) struct SampleItemC { +//! # pub value: i32, +//! # pub link: bindings::list_head, +//! # } +//! # +//! # let mut head = MaybeUninit::<bindings::list_head>::uninit(); +//! # +//! # // SAFETY: head and all the items are test objects allocated in this scope. +//! # unsafe { bindings::INIT_LIST_HEAD(head.as_mut_ptr()) }; +//! # // SAFETY: head is a test object allocated in this scope. +//! # let mut head = unsafe { head.assume_init() }; +//! # let mut items = [ +//! # MaybeUninit::<SampleItemC>::uninit(), +//! # MaybeUninit::<SampleItemC>::uninit(), +//! # MaybeUninit::<SampleItemC>::uninit(), +//! # ]; +//! # +//! # for (i, item) in items.iter_mut().enumerate() { +//! # let ptr = item.as_mut_ptr(); +//! # // SAFETY: pointers are to allocated test objects with a list_head field. +//! # unsafe { +//! # (*ptr).value = i as i32 * 10; +//! # bindings::INIT_LIST_HEAD(&mut (*ptr).link); +//! # bindings::list_add_tail(&mut (*ptr).link, &mut head); +//! # } +//! # } +//! +//! // Rust wrapper for the C struct. +//! // The list item struct in this example is defined in C code as: +//! // struct SampleItemC { +//! // int value; +//! // struct list_head link; +//! // }; +//! // +//! #[repr(transparent)] +//! pub(crate) struct Item(Opaque<SampleItemC>); +//! +//! // Generate the link type. +//! impl_from_list_head!(pub(crate), Item, SampleItemC, link); +//! +//! impl Item { +//! pub(crate) fn value(&self) -> i32 { +//! // SAFETY: Item has same layout as SampleItemC. +//! unsafe { (*self.0.get()).value } +//! } +//! } +//! +//! // Create Clist (from a sentinel head). +//! // SAFETY: head is allocated by test code and Clist has the same layout. +//! let list = unsafe { Clist::from_raw(&mut head) }; +//! +//! // Now iterate using clist_iterate! macro. +//! let mut found_0 = false; +//! let mut found_10 = false; +//! let mut found_20 = false; +//! +//! for item in clist_iterate!(list, Item, link) { +//! let val = item.value(); +//! if val == 0 { found_0 = true; } +//! if val == 10 { found_10 = true; } +//! if val == 20 { found_20 = true; }
rust/kernel/clist.rs line 85
Quoted 10 lines
rust/kernel/clist.rs +5
-0+//! } +//! +//! assert!(found_0 && found_10 && found_20); +//! ``` use crate ::{ bindings, types::Opaque ,// }; +use core::marker::PhantomData ;
IIUC the typical order of imports is core, then kernel, then crate (here crate == kernel though), with a space between them.
Quoted 9 lines
rust/kernel/clist.rs +9
-0+ +/// Trait for associating a link type with its container item type. +/// +/// Implemented by "field link types" that are `list_head` links embedded in intrusive +/// C linked lists. Each link type is unique to a specific item type and its `list_head` field, +/// making it possible for an item to be added to multiple lists. +pub trait ClistLink { +/// The item type that contains the `list_head` field linking to other items in the list. +type Item :FromListHead <Self >
rust/kernel/clist.rs line 102
Quoted 10 lines
rust/kernel/clist.rs +5
-2+ where + Self: Sized; +}/// 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. +/// Represents the entire linked list and can be used for add, remove, empty operations etc. +/// A sentinel head is one which is not embedded in an item.
This comment changes, but its substance remains the same - let's get its final form in the previous patch?
Quoted 6 lines
rust/kernel/clist.rs +0
-0/// /// # Invariants /// @@ -69,6 +156,15 @@ pub fn iter_heads(&self) -> ClistHeadIter<'_> { head: &self.0, }
rust/kernel/clist.rs pub fn iter_heads(&self) -> ClistHeadIter<'_> { · line 167
Quoted 10 lines
rust/kernel/clist.rs +9
-0} + +/// Create a high-level iterator over typed items. +#[inline] +pub fn iter <L :ClistLink >(&self) ->ClistIter <'_,L > { +ClistIter { + head_iter: self.iter_heads (), + _phantom:PhantomData , + } + }
This looks very dangerous, as it gives any caller the freedom to specify the type they want to upcast the Clist to, without using unsafe code. One could easily invoke this with the wrong type and get no build error or warning whatsoever.
A safer version would have the Clist generic over the kind of conversion that needs to be performed, using e.g. a closure:
pub struct Clist<'a, T, C: Fn(*mut bindings::list_head) -> *mut T> {
head: &'a ClistHead,
conv: C,
}from_raw would also take the closure as argument, which forces the creator of the list to both specify what that list is for, and use an unsafe statement for unsafe code. Here is a dummy example:
let head: bindings::list_head = ...;
// SAFETY: list_head always corresponds to the `list` member of
// `type_embedding_list_head`.
let conv = |head: *mut bindings::list_head| unsafe {
crate::container_of!(head, type_embedding_list_head, list)
};
// SAFETY: ...
unsafe { Clist::from_raw(head, conv) }Then conv would be passed down to the ClistIter so it can return references to the correct type.
By doing so you can remove the ClinkList and FromListHead traits, the impl_from_list_head and clist_iterate macros, as well as the hidden ad-hoc types these create. And importantly, all unsafe code must be explicitly specified in an unsafe block, nothing is hidden by macros.
This approach works better imho because each list_head is unique in how it has to be iterated: there is no benefit in implementing things using types and traits that will only ever be used in a single place anyway. And if there was, we could always create a newtype for that.
Also as I suspected in v1 Clist appears to do very little apart from providing an iterator, so I'm more convinced that the front type for this should be ClistHead.
Quoted 11 lines
rust/kernel/clist.rs +4
-0}/// Wraps a non-sentinel C `list_head` node for use in intrusive linked lists. @@ -188,3 +284,111 @@ fn next(&mut self) -> Option<Self::Item> {Some (self.current) } } + +/// High-level iterator over typed list items. +pub struct ClistIter <'a,L :ClistLink > { + head_iter:ClistHeadIter <'a>,
rust/kernel/clist.rs fn next(&mut self) -> Option<Self::Item> { · line 300
Quoted 10 lines
rust/kernel/clist.rs +10
-0+ +/// The iterator yields immutable references to `L::Item`. + _phantom: PhantomData<&'a L::Item>, +} + +// SAFETY: ClistIter yields `&L::Item`, which is Send when `L::Item: Send`. +unsafe impl <L :ClistLink >Send for ClistIter <'_,L >where L ::Item :Send {} + +// SAFETY: ClistIter yields &L::Item, which is Sync when `L::Item: Sync`. +unsafe impl <L :ClistLink >Sync for ClistIter <'_,L >where L ::Item :Sync {}
These implementations should also be automatic.
rust/kernel/clist.rs fn next(&mut self) -> Option<Self::Item> { · line 306
Quoted 6 lines
rust/kernel/clist.rs +6
-0+ +impl <'a,L :ClistLink >Iterator for ClistIter <'a,L > +where +L ::Item : 'a, +{ +type Item = &'aL ::Item ;
This is going to work well when we want to parse lists read-only. But I've also seen in some comments that you were considering supporting addition and deletion of items?
In that case we will probably want to return some sort of guard type that derefs to Item (similar to a mutex guard), while also providing list management operations. We will probably also want distinct types for read-only and read-modify behavior. I think this can be done later, but better to keep this in mind when designing things.
rust/kernel/clist.rs fn next(&mut self) -> Option<Self::Item> { · line 314
Quoted 8 lines
rust/kernel/clist.rs +8
-0+ +fn next (&mut self) ->Option <Self ::Item > { +// Get next ClistHead. +let head = self.head_iter.next ()?; + +// Convert to item using trait. +// SAFETY: FromListHead impl guarantees valid conversion. +Some (unsafe {L ::Item ::from_list_head (head) })
More idiomatic proposal:
self.head_iter.next().map(|head| {
// SAFETY: The FromListHead impl guarantees valid conversion.
unsafe { L::Item::from_list_head(head) }
})Note that since kernel lists are bi-directional, you can also implement DoubleEndedIterator!
Re: [PATCH v2 3/3] rust: clist: Add typed iteration with FromListHead trait
Hi Alex,
Quoted 53 lines · Alexandre Courbot
Quoted 6 lines
///
/// # Invariants
///rust/kernel/clist.rs +0
-0@@ -69,6 +156,15 @@ pub fn iter_heads(&self) -> ClistHeadIter<'_> { head: &self.0, }rust/kernel/clist.rs pub fn iter_heads(&self) -> ClistHeadIter<'_> { · line 167
Quoted 10 lines
rust/kernel/clist.rs +9
-0} + +/// Create a high-level iterator over typed items. +#[inline] +pub fn iter <L :ClistLink >(&self) ->ClistIter <'_,L > { +ClistIter { + head_iter: self.iter_heads (), + _phantom:PhantomData , + } + }This looks very dangerous, as it gives any caller the freedom to specify the type they want to upcast the
Clistto, without using unsafe code. One could easily invoke this with the wrong type and get no build error or warning whatsoever.A safer version would have the
Clistgeneric over the kind of conversion that needs to be performed, using e.g. a closure:pub struct Clist<'a, T, C: Fn(*mut bindings::list_head) -> *mut T> { head: &'a ClistHead, conv: C, }
from_rawwould also take the closure as argument, which forces the creator of the list to both specify what that list is for, and use anunsafestatement for unsafe code. Here is a dummy example:let head: bindings::list_head = ...; // SAFETY: list_head always corresponds to the `list` member of // `type_embedding_list_head`. let conv = |head: *mut bindings::list_head| unsafe { crate::container_of!(head, type_embedding_list_head, list) }; // SAFETY: ... unsafe { Clist::from_raw(head, conv) }Then
convwould be passed down to theClistIterso it can return references to the correct type.By doing so you can remove the
ClinkListandFromListHeadtraits, theimpl_from_list_headandclist_iteratemacros, as well as the hidden ad-hoc types these create. And importantly, all unsafe code must be explicitly specified in anunsafeblock, nothing is hidden by macros.
Quoted 4 lines
This approach works better imho because each
list_headis unique in how it has to be iterated: there is no benefit in implementing things using types and traits that will only ever be used in a single place anyway. And if there was, we could always create a newtype for that.
I agree with your safety concerns, indeed it is possible without any safety comments to build iterators yielding objects of random type. I think the conv function is a good idea and with the addition of unsafe blocks within the conv.
One thing I am concerned is with the user interface. I would like to keep the user interface as simple as possible. I am hoping that with implementing your idea here on this with the closure, we can still keep it simple, perhaps getting the assistance of macros. I will give it a try.
Quoted 3 lines
Also as I suspected in v1
Clistappears to do very little apart from providing an iterator, so I'm more convinced that the front type for this should beClistHead.
This part I don't agree with. I prefer to keep it as Clist which wraps a sentinel list head. A random ClistHead is not necessarily a sentinel.
thanks,
- Joel
Alexandre Courbot
reviewerRe: [PATCH v2 3/3] rust: clist: Add typed iteration with FromListHead trait
Quoted 61 lines · Joel Fernandes
Hi Alex,
Quoted 53 lines · Alexandre Courbot
Quoted 6 lines
///
/// # Invariants
///rust/kernel/clist.rs +0
-0@@ -69,6 +156,15 @@ pub fn iter_heads(&self) -> ClistHeadIter<'_> { head: &self.0, }rust/kernel/clist.rs pub fn iter_heads(&self) -> ClistHeadIter<'_> { · line 167
Quoted 10 lines
rust/kernel/clist.rs +9
-0} + +/// Create a high-level iterator over typed items. +#[inline] +pub fn iter <L :ClistLink >(&self) ->ClistIter <'_,L > { +ClistIter { + head_iter: self.iter_heads (), + _phantom:PhantomData , + } + }This looks very dangerous, as it gives any caller the freedom to specify the type they want to upcast the
Clistto, without using unsafe code. One could easily invoke this with the wrong type and get no build error or warning whatsoever.A safer version would have the
Clistgeneric over the kind of conversion that needs to be performed, using e.g. a closure:pub struct Clist<'a, T, C: Fn(*mut bindings::list_head) -> *mut T> { head: &'a ClistHead, conv: C, }
from_rawwould also take the closure as argument, which forces the creator of the list to both specify what that list is for, and use anunsafestatement for unsafe code. Here is a dummy example:let head: bindings::list_head = ...; // SAFETY: list_head always corresponds to the `list` member of // `type_embedding_list_head`. let conv = |head: *mut bindings::list_head| unsafe { crate::container_of!(head, type_embedding_list_head, list) }; // SAFETY: ... unsafe { Clist::from_raw(head, conv) }Then
convwould be passed down to theClistIterso it can return references to the correct type.By doing so you can remove the
ClinkListandFromListHeadtraits, theimpl_from_list_headandclist_iteratemacros, as well as the hidden ad-hoc types these create. And importantly, all unsafe code must be explicitly specified in anunsafeblock, nothing is hidden by macros.Quoted 4 lines
This approach works better imho because each
list_headis unique in how it has to be iterated: there is no benefit in implementing things using types and traits that will only ever be used in a single place anyway. And if there was, we could always create a newtype for that.
Quoted 8 lines
I agree with your safety concerns, indeed it is possible without any safety comments to build iterators yielding objects of random type. I think the conv function is a good idea and with the addition of unsafe blocks within the conv.
One thing I am concerned is with the user interface. I would like to keep the user interface as simple as possible. I am hoping that with implementing your idea here on this with the closure, we can still keep it simple, perhaps getting the assistance of macros. I will give it a try.
We should be able to build more convenient interfaces on top of this closure-based design (hopefully without the help of macros).
But first, one needs to recognize that this Clist interface is not your regular, easy-to-use Rust interface - it is designed for specific cases where we need to interact with C code and do unsafe things anyway.
Still, the most common (maybe even the only?) conversion pattern will be "substract an offset from the address of this list_head and cast to this type". Instead of expressing this through a closure using container_of, maybe we can have a dedicated constructor for these cases:
pub unsafe from_raw_and_offset<const LIST_OFFSET: usize>(ptr: *mut bindings::list_head) -> Clist<'a, T, ...>
LIST_OFFSET could be specified by callers using the offset_of macro. This method would then call the more generic from_raw constructor, passing the right closure. And with that you have a more convenient interface. :)
Quoted 7 lines
Quoted 4 lines
Also as I suspected in v1
Clistappears to do very little apart from providing an iterator, so I'm more convinced that the front type for this should beClistHead.This part I don't agree with. I prefer to keep it as
Clistwhich wraps a sentinel list head. A randomClistHeadis not necessarily a sentinel.
I expressed myself poorly - what I meant of that ClistHead should be the only type you need for the low-level iteration (which should not be public).
And if Clist ends up just being a provider for a ClistIterator, you might just as well return a ClistIterator from the beginning. Anyway, collapsing the two types into one can be done after the design matures if it turns out to be the right thing to do, so feel free to keep both for now.
Re: [PATCH v2 3/3] rust: clist: Add typed iteration with FromListHead trait
Quoted 88 lines · Alexandre Courbot
Quoted 61 lines · Joel Fernandes
Hi Alex,
Quoted 53 lines · Alexandre Courbot
Quoted 6 lines
///
/// # Invariants
///rust/kernel/clist.rs +0
-0@@ -69,6 +156,15 @@ pub fn iter_heads(&self) -> ClistHeadIter<'_> { head: &self.0, }rust/kernel/clist.rs pub fn iter_heads(&self) -> ClistHeadIter<'_> { · line 167
Quoted 10 lines
rust/kernel/clist.rs +9
-0} + +/// Create a high-level iterator over typed items. +#[inline] +pub fn iter <L :ClistLink >(&self) ->ClistIter <'_,L > { +ClistIter { + head_iter: self.iter_heads (), + _phantom:PhantomData , + } + }This looks very dangerous, as it gives any caller the freedom to specify the type they want to upcast the
Clistto, without using unsafe code. One could easily invoke this with the wrong type and get no build error or warning whatsoever.A safer version would have the
Clistgeneric over the kind of conversion that needs to be performed, using e.g. a closure:pub struct Clist<'a, T, C:
Fn(*mut bindings::list_head)-> *mut T> {
head: &'a ClistHead,
conv: C,
}
from_rawwould also take the closure as argument, which forces the creator of the list to both specify what that list is for, and use anunsafestatement for unsafe code. Here is a dummy example:let head: bindings::list_head = ...; // SAFETY: list_head always corresponds to the `list` member of // `type_embedding_list_head`. let conv = |head: *mut bindings::list_head| unsafe { crate::container_of!(head, type_embedding_list_head, list) };// SAFETY: ... unsafe { Clist::from_raw(head, conv) }Then
convwould be passed down to theClistIterso it can return references to the correct type.By doing so you can remove the
ClinkListandFromListHeadtraits, theimpl_from_list_headandclist_iteratemacros, as well as the hidden ad-hoc types these create. And importantly, all unsafe code must be explicitly specified in anunsafeblock, nothing is hidden by macros.Quoted 4 lines
This approach works better imho because each
list_headis unique in how it has to be iterated: there is no benefit in implementing things using types and traits that will only ever be used in a single place anyway. And if there was, we could always create a newtype for that.Quoted 8 lines
I agree with your safety concerns, indeed it is possible without any safety comments to build iterators yielding objects of random type. I think the conv function is a good idea and with the addition of unsafe blocks within the conv.
One thing I am concerned is with the user interface. I would like to keep the user interface as simple as possible. I am hoping that with implementing your idea here on this with the closure, we can still keep it simple, perhaps getting the assistance of macros. I will give it a try.
We should be able to build more convenient interfaces on top of this closure-based design (hopefully without the help of macros).
But first, one needs to recognize that this Clist interface is not your regular, easy-to-use Rust interface - it is designed for specific cases where we need to interact with C code and do unsafe things anyway.
Still, the most common (maybe even the only?) conversion pattern will be "substract an offset from the address of this
list_headand cast to this type". Instead of expressing this through a closure usingcontainer_of, maybe we can have a dedicated constructor for these cases:
Quoted 6 lines
pub unsafe from_raw_and_offset<const
LIST_OFFSET: usize>(ptr: *mutbindings::list_head) -> Clist<'a, T, ...>
LIST_OFFSETcould be specified by callers using theoffset_ofmacro. This method would then call the more genericfrom_rawconstructor, passing the right closure. And with that you have a more convenient interface. :)
Great! This makes it easy to use. I will do it this way then - I am assuming everyone is ok baking in this kind of usecase assumed (subtraction of offset). If anyone is not, please raise your concern.
Quoted 6 lines
Quoted 6 lines
Quoted 5 lines
Also as I suspected in v1
Clistappears to do very little apart from providing an iterator, so I'm more convinced that the front type for this should beClistHead.
Quoted 6 lines
Quoted 2 lines
This part I don't agree with. I prefer to keep it as
Clistwhich wraps a sentinel list head. A randomClistHeadis not necessarily a sentinel.I expressed myself poorly - what I meant of that
ClistHeadshould be the only type you need for the low-level iteration (which should not be public).
For low level iteration it is already via that type. There are 2 iterators. The higher level uses the lower level one. I could make it even simpler and collapse bother iterators into one - that yields the final type T.
Quoted 6 lines
And if Clist ends up just being a provider for a ClistIterator, you might just as well return a ClistIterator from the beginning. Anyway, collapsing the two types into one can be done after the design matures if it turns out to be the right thing to do, so feel free to keep both for now.
I prefer to generate the iterator separately as a second step in case we have to extend it to do something other than iteration later, makes it more future ready and better separation of concerns IMO, a list can be more than just iterating, and as you said, we can collapse it later if needed.
Thanks.
Alexandre Courbot
reviewerRe: [PATCH v2 3/3] rust: clist: Add typed iteration with FromListHead trait
Quoted 103 lines · Joel Fernandes
Quoted 88 lines · Alexandre Courbot
Quoted 61 lines · Joel Fernandes
Hi Alex,
Quoted 53 lines · Alexandre Courbot
Quoted 6 lines
///
/// # Invariants
///rust/kernel/clist.rs +0
-0@@ -69,6 +156,15 @@ pub fn iter_heads(&self) -> ClistHeadIter<'_> { head: &self.0, }rust/kernel/clist.rs pub fn iter_heads(&self) -> ClistHeadIter<'_> { · line 167
Quoted 10 lines
rust/kernel/clist.rs +9
-0} + +/// Create a high-level iterator over typed items. +#[inline] +pub fn iter <L :ClistLink >(&self) ->ClistIter <'_,L > { +ClistIter { + head_iter: self.iter_heads (), + _phantom:PhantomData , + } + }This looks very dangerous, as it gives any caller the freedom to specify the type they want to upcast the
Clistto, without using unsafe code. One could easily invoke this with the wrong type and get no build error or warning whatsoever.A safer version would have the
Clistgeneric over the kind of conversion that needs to be performed, using e.g. a closure:pub struct Clist<'a, T, C:
Fn(*mut bindings::list_head)-> *mut T> {
head: &'a ClistHead,
conv: C,
}
from_rawwould also take the closure as argument, which forces the creator of the list to both specify what that list is for, and use anunsafestatement for unsafe code. Here is a dummy example:let head: bindings::list_head = ...; // SAFETY: list_head always corresponds to the `list` member of // `type_embedding_list_head`. let conv = |head: *mut bindings::list_head| unsafe { crate::container_of!(head, type_embedding_list_head, list) };// SAFETY: ... unsafe { Clist::from_raw(head, conv) }Then
convwould be passed down to theClistIterso it can return references to the correct type.By doing so you can remove the
ClinkListandFromListHeadtraits, theimpl_from_list_headandclist_iteratemacros, as well as the hidden ad-hoc types these create. And importantly, all unsafe code must be explicitly specified in anunsafeblock, nothing is hidden by macros.Quoted 4 lines
This approach works better imho because each
list_headis unique in how it has to be iterated: there is no benefit in implementing things using types and traits that will only ever be used in a single place anyway. And if there was, we could always create a newtype for that.Quoted 8 lines
I agree with your safety concerns, indeed it is possible without any safety comments to build iterators yielding objects of random type. I think the conv function is a good idea and with the addition of unsafe blocks within the conv.
One thing I am concerned is with the user interface. I would like to keep the user interface as simple as possible. I am hoping that with implementing your idea here on this with the closure, we can still keep it simple, perhaps getting the assistance of macros. I will give it a try.
We should be able to build more convenient interfaces on top of this closure-based design (hopefully without the help of macros).
But first, one needs to recognize that this Clist interface is not your regular, easy-to-use Rust interface - it is designed for specific cases where we need to interact with C code and do unsafe things anyway.
Still, the most common (maybe even the only?) conversion pattern will be "substract an offset from the address of this
list_headand cast to this type". Instead of expressing this through a closure usingcontainer_of, maybe we can have a dedicated constructor for these cases:Quoted 6 lines
pub unsafe from_raw_and_offset<const
LIST_OFFSET: usize>(ptr: *mutbindings::list_head) -> Clist<'a, T, ...>
LIST_OFFSETcould be specified by callers using theoffset_ofmacro. This method would then call the more genericfrom_rawconstructor, passing the right closure. And with that you have a more convenient interface. :)Great! This makes it easy to use. I will do it this way then - I am assuming everyone is ok baking in this kind of usecase assumed (subtraction of offset). If anyone is not, please raise your concern.
Quoted 6 lines
Quoted 6 lines
Quoted 5 lines
Also as I suspected in v1
Clistappears to do very little apart from providing an iterator, so I'm more convinced that the front type for this should beClistHead.
Quoted 8 lines
Quoted 6 lines
Quoted 2 lines
This part I don't agree with. I prefer to keep it as
Clistwhich wraps a sentinel list head. A randomClistHeadis not necessarily a sentinel.I expressed myself poorly - what I meant of that
ClistHeadshould be the only type you need for the low-level iteration (which should not be public).For low level iteration it is already via that type. There are 2 iterators. The higher level uses the lower level one. I could make it even simpler and collapse bother iterators into one - that yields the final type T.
I think the current 2 iterators design is elegant: the lower-level one taking care of going through the list, and the higher-level one building on top of that and adding upcasting. Maybe the lower-level one can be made private, but I'd keep it in any case.
Re: [PATCH v2 3/3] rust: clist: Add typed iteration with FromListHead trait
Quoted 12 lines
Quoted 12 lines
Quoted 11 lines
Quoted 7 lines
Quoted 4 lines
Also as I suspected in v1
Clistappears to do very little apart from providing an iterator, so I'm more convinced that the front type for this should beClistHead.This part I don't agree with. I prefer to keep it as
Clistwhich wraps a sentinel list head. A randomClistHeadis not necessarily a sentinel.I expressed myself poorly - what I meant of that
ClistHeadshould be the only type you need for the low-level iteration (which should not be public).
Quoted 7 lines
Quoted 1 line
For low level iteration it is already via that type. There are 2 iterators. The higher level uses the lower level one. I could make it even simpler and collapse bother iterators into one - that yields the final type T.
I think the current 2 iterators design is elegant: the lower-level one taking care of going through the list, and the higher-level one building on top of that and adding upcasting. Maybe the lower-level one can be made private, but I'd keep it in any case.
Yeah, I kept it split for that purpose but had a nagging feeling if it was required. But ok, I will leave that part alone then. Making it private sgtm.
Thanks.
v2 cover rust: Introduce support for C linked list interfacing
In reply to Joel FernandesChanges from RFC to v2:
- Dropped the DRM buddy allocator patches from this series. This series now focuses solely on the C linked list interfacing infrastructure (clist module). The DRM buddy allocator bindings will be sent separately once we agree on the clist abstraction.
- Dropped samples and added doctests.
- Added proper lifetime management similar to scatterlist.
The git tree with all patches can be found at the tag:git://git.kernel.org/pub/scm/linux/kernel/git/jfern/linux.git (tag: clist-v2-checkpoint-6)
Introduction
============
This patchset introduces an interface to iterate over doubly circular linked lists used in the kernel (allocated by C kernel code). The main usecase is iterating over the list of blocks provided by the DRM buddy allocator but there will certainly be others in the future.
This series introduces a new rust module called clist with the necessary helpers and abstractions for safe iteration over C-allocated linked lists.
Notes from earlier series:
A question may arise: Why not use rust list.rs for this?
=========================================================
Rust's list.rs is used to provide safe intrusive lists for Rust-allocated items. In doing so, it takes ownership of the items in the list and the links between list items. However, the usecase for DRM buddy allocator bindings, the C side allocates the items in the list, and also links the list together. Due to this, there is an ownership conflict making list.rs not the best abstraction for this usecase. What we need is a view of the list, not ownership of it. Further, the list links in a bindings usecase may come from C allocated objects, not from the Rust side.
Other comments
==============
I already presented the idea in Zulip and it seemed it mostly got agreements there. I rebased the patches on linux-next. I can also add MAINTAINER entries in a future version, if folks agree this should have its own MAINTAINER record.
Link to RFC: https://lore.kernel.org/all/[email protected]/
Joel Fernandes (3):
rust: helpers: Add list helpers for C linked list operations
rust: clist: Add basic list infrastructure and head iterator
rust: clist: Add typed iteration with FromListHead trait
rust/helpers/helpers.c | 1 + rust/helpers/list.c | 32 ++++ rust/kernel/clist.rs | 394 +++++++++++++++++++++++++++++++++++++++++ rust/kernel/lib.rs | 1 + 4 files changed, 428 insertions(+) create mode 100644 rust/helpers/list.c create mode 100644 rust/kernel/clist.rs
Signature · 1 line
2.34.1
Re: [PATCH v2 0/3] rust: Introduce support for C linked list interfacing
Quoted 4 lines · Joel Fernandes
there. I rebased the patches on linux-next. I can also add MAINTAINER entries in a future version, if folks agree this should have its own MAINTAINER record.
Yes, it sounds good to me to add one. Please do -- thanks!
Cheers,
Miguel
Re: [PATCH v2 0/3] rust: Introduce support for C linked list interfacing
Quoted 7 lines · Miguel Ojeda
Quoted 4 lines · Joel Fernandes
there. I rebased the patches on linux-next. I can also add MAINTAINER entries in a future version, if folks agree this should have its own MAINTAINER record.
Yes, it sounds good to me to add one. Please do -- thanks!
Ok, will do. Thanks!
- Joel
Alexandre Courbot
reviewerQuoted 51 lines · Joel Fernandes
Add Rust helper functions for common C linked list operations that are implemented as macros or inline functions and thus not directly accessible from Rust.
Signed-off-by Joel Fernandes <[email protected]>--- rust/helpers/helpers.c | 1 + rust/helpers/list.c | 32 ++++++++++++++++++++++++++++++++ 2 files changed, 33 insertions(+) create mode 100644 rust/helpers/list.crust/helpers/helpers.c +1
-0@@ -32,6 +32,7 @@#include "io.c" #include "jump_label.c" #include "kunit.c" +#include "list.c" #include "maple_tree.c" #include "mm.c" #include "mutex.c" rust/helpers/list.c new file +22
-0@@ -0,0 +1,32 @@ +// SPDX-License-Identifier: GPL-2.0 + +/* +* Helpers for C Circular doubly linked list implementation. +*/ + +#include <linux/list.h> + +bool rust_helper_list_empty (const struct list_head *head) +{ +return list_empty (head); +} + +void rust_helper_list_del (struct list_head *entry) +{ +list_del (entry); +} + +void rust_helper_INIT_LIST_HEAD (struct list_head *list) +{ +INIT_LIST_HEAD (list); +}
rust/helpers/list.c line 32
Quoted 10 lines
rust/helpers/list.c new file +10
-0+ +void rust_helper_list_add (struct list_head *new,struct list_head *head) +{ +list_add (new, head); +} + +void rust_helper_list_add_tail (struct list_head *new,struct list_head *head) +{ +list_add_tail (new, head); +}
Just noticed, but of these helpers only INIT_LIST_HEAD and list_add_tail seem to be used (in doccomments).
Quoted 61 lines · Alexandre Courbot
Quoted 56 lines · Joel Fernandes
Add Rust helper functions for common C linked list operations that are implemented as macros or inline functions and thus not directly accessible from Rust.
Signed-off-by Joel Fernandes <[email protected]>---
rust/helpers/helpers.c| 1 +rust/helpers/list.c| 32 ++++++++++++++++++++++++++++++++2 files changed, 33 insertions(+)create mode 100644
rust/helpers/list.crust/helpers/helpers.c +1
-0@@ -32,6 +32,7 @@#include "io.c" #include "jump_label.c" #include "kunit.c" +#include "list.c" #include "maple_tree.c" #include "mm.c" #include "mutex.c" rust/helpers/list.c new file +27
-0@@ -0,0 +1,32 @@ +// SPDX-License-Identifier: GPL-2.0 + +/* +* Helpers for C Circular doubly linked list implementation. +*/ + +#include <linux/list.h> + +bool rust_helper_list_empty (const struct list_head *head) +{ +return list_empty (head); +} + +void rust_helper_list_del (struct list_head *entry) +{ +list_del (entry); +} + +void rust_helper_INIT_LIST_HEAD (struct list_head *list) +{ +INIT_LIST_HEAD (list); +} + +void rust_helper_list_add (struct list_head *new,struct list_head *head) +{ +list_add (new, head); +}
Quoted 8 lines
rust/helpers/list.c line 32
Quoted 5 lines
rust/helpers/list.c new file +5
-0+ +void rust_helper_list_add_tail (struct list_head *new,struct list_head *head) +{ +list_add_tail (new, head); +}Just noticed, but of these helpers only
INIT_LIST_HEADandlist_add_tailseem to be used (in doccomments).
Correct, but it makes sense to add the most obvious/common ones (also to make it clear that using these are supported).
Thanks.
Quoted 2 lines · Joel Fernandes
Quoted 2 lines · Alexandre Courbot
On Wed Nov 12, 2025 at 2:13 AM JST, Joel Fernandes wrote:
...
Quoted 5 lines
Quoted 2 lines
Just noticed, but of these helpers only
INIT_LIST_HEADandlist_add_tailseem to be used (in doccomments).Correct, but it makes sense to add the most obvious/common ones (also to make it clear that using these are supported).
It's important to exercise the code. Let's please add that coverage, seeing as how it is quite easy to do, right?
thanks,
Signature · 1 line
John Hubbard
Quoted 4 lines · John Hubbard
Quoted 2 lines · Joel Fernandes
Quoted 2 lines · Alexandre Courbot
On Wed Nov 12, 2025 at 2:13 AM JST, Joel Fernandes wrote:
...
Quoted 8 lines
Quoted 5 lines
Quoted 2 lines
Just noticed, but of these helpers only
INIT_LIST_HEADandlist_add_tailseem to be used (in doccomments).Correct, but it makes sense to add the most obvious/common ones (also to make it clear that using these are supported).
It's important to exercise the code. Let's please add that coverage, seeing as how it is quite easy to do, right?
Sure, I will add that.
Thanks.
Alexandre Courbot
reviewerQuoted 70 lines · Joel Fernandes
Quoted 61 lines · Alexandre Courbot
Quoted 56 lines · Joel Fernandes
Add Rust helper functions for common C linked list operations that are implemented as macros or inline functions and thus not directly accessible from Rust.
Signed-off-by Joel Fernandes <[email protected]>---
rust/helpers/helpers.c| 1 +rust/helpers/list.c| 32 ++++++++++++++++++++++++++++++++2 files changed, 33 insertions(+)create mode 100644
rust/helpers/list.crust/helpers/helpers.c +1
-0@@ -32,6 +32,7 @@#include "io.c" #include "jump_label.c" #include "kunit.c" +#include "list.c" #include "maple_tree.c" #include "mm.c" #include "mutex.c" rust/helpers/list.c new file +27
-0@@ -0,0 +1,32 @@ +// SPDX-License-Identifier: GPL-2.0 + +/* +* Helpers for C Circular doubly linked list implementation. +*/ + +#include <linux/list.h> + +bool rust_helper_list_empty (const struct list_head *head) +{ +return list_empty (head); +} + +void rust_helper_list_del (struct list_head *entry) +{ +list_del (entry); +} + +void rust_helper_INIT_LIST_HEAD (struct list_head *list) +{ +INIT_LIST_HEAD (list); +} + +void rust_helper_list_add (struct list_head *new,struct list_head *head) +{ +list_add (new, head); +}Quoted 8 lines
rust/helpers/list.c line 32
Quoted 5 lines
rust/helpers/list.c new file +5
-0+ +void rust_helper_list_add_tail (struct list_head *new,struct list_head *head) +{ +list_add_tail (new, head); +}Just noticed, but of these helpers only
INIT_LIST_HEADandlist_add_tailseem to be used (in doccomments).
Quoted 1 line
Correct, but it makes sense to add the most obvious/common ones (also to make it clear that using these are supported).
"It makes sense" is subjective, and in this case I am confident it is not the right intuition to add dead code just for the sake of it.
Each of these helpers adds a potential breakage point from the C API should the latter change, so we should only add them if they are indeed necessary.
Actually, some of these helpers are not used when they could have been - you have a is_empty method that rewrites the C function instead of calling the helper. The only helpers that are unjustified as of now as list_add and list_del, and these are easy to add when they become necessary.
But this raises an interesting dilemma: these helpers cannot be inlined and add the overhead of a function call. On the other hand, the definition of list_head is so excessively simple that manipulating it directly is virtually as intuitive as invoking the helper - and doesn't bear the overhead. So should we double-down on these helpers, or just drop them completely and re-implement the list functionality we need for increased performance?
Quoted 3 lines · Alexandre Courbot
Quoted 2 lines · Joel Fernandes
Quoted 2 lines · Alexandre Courbot
On Wed Nov 12, 2025 at 2:13 AM JST, Joel Fernandes wrote:
...
Quoted 4 lines
Quoted 1 line
Correct, but it makes sense to add the most obvious/common ones (also to make it clear that using these are supported).
"It makes sense" is subjective, and in this case I am confident it is not the right intuition to add dead code just for the sake of it.
Yes. I am increasingly uneasy with the Rust for Linux approach, and now the Nova approach, of adding in "things we might need".
The kernel, for example linux-mm, is usually quite fiercely pushing for "prove you need this, by adding in the calling code as part of your series".
Drifting away from this makes it hard to know how the calling code *actually* looks.
Quoted 5 lines
Each of these helpers adds a potential breakage point from the C API should the latter change, so we should only add them if they are indeed necessary.
Yes please! Just add what you need. Other goodies can come later.
Quoted 6 lines
Actually, some of these helpers are not used when they could have been - you have a
is_emptymethod that rewrites the C function instead of calling the helper. The only helpers that are unjustified as of now aslist_addandlist_del, and these are easy to add when they become necessary.
Quoted 7 lines
But this raises an interesting dilemma: these helpers cannot be inlined and add the overhead of a function call. On the other hand, the definition of
list_headis so excessively simple that manipulating it directly is virtually as intuitive as invoking the helper - and doesn't bear the overhead. So should we double-down on these helpers, or just drop them completely and re-implement the list functionality we need for increased performance?
Do the "it runs faster" thing. :)
thanks,
Signature · 1 line
John Hubbard
Quoted 3 lines · John Hubbard
Yes. I am increasingly uneasy with the Rust for Linux approach, and now the Nova approach, of adding in "things we might need".
Excuse me, what "Rust for Linux approach"?
No, we do not add dead code unless justified, just like everywhere else in the Linux kernel.
Yes, there are a few exceptional cases, but it is just that, exceptional.
Cheers,
Miguel
Quoted 5 lines · Miguel Ojeda
Quoted 3 lines · John Hubbard
Yes. I am increasingly uneasy with the Rust for Linux approach, and now the Nova approach, of adding in "things we might need".
Quoted 7 lines
Excuse me, what "Rust for Linux approach"?
No, we do not add dead code unless justified, just like everywhere else in the Linux kernel.
Yes, there are a few exceptional cases, but it is just that, exceptional.
I stand corrected (and relieved)! :)
Thanks, Miguel.
thanks,
Signature · 1 line
John Hubbard
Quoted 90 lines · Alexandre Courbot
Quoted 70 lines · Joel Fernandes
Quoted 61 lines
Quoted 3 lines · Alexandre Courbot
Quoted 56 lines · Joel Fernandes
Add Rust helper functions for common C linked list operations that are implemented as macros or inline functions and thus not directly accessible from Rust.
Signed-off-by Joel Fernandes <[email protected]>---
rust/helpers/helpers.c| 1 +rust/helpers/list.c| 32 ++++++++++++++++++++++++++++++++2 files changed, 33 insertions(+)create mode 100644
rust/helpers/list.crust/helpers/helpers.c +1
-0@@ -32,6 +32,7 @@#include "io.c" #include "jump_label.c" #include "kunit.c" +#include "list.c" #include "maple_tree.c" #include "mm.c" #include "mutex.c" rust/helpers/list.c new file +27
-0@@ -0,0 +1,32 @@ +// SPDX-License-Identifier: GPL-2.0 + +/* +* Helpers for C Circular doubly linked list implementation. +*/ + +#include <linux/list.h> + +bool rust_helper_list_empty (const struct list_head *head) +{ +return list_empty (head); +} + +void rust_helper_list_del (struct list_head *entry) +{ +list_del (entry); +} + +void rust_helper_INIT_LIST_HEAD (struct list_head *list) +{ +INIT_LIST_HEAD (list); +} + +void rust_helper_list_add (struct list_head *new,struct list_head *head) +{ +list_add (new, head); +}Quoted 8 lines
rust/helpers/list.c line 32
Quoted 5 lines
rust/helpers/list.c new file +5
-0+ +void rust_helper_list_add_tail (struct list_head *new,struct list_head *head) +{ +list_add_tail (new, head); +}Just noticed, but of these helpers only
INIT_LIST_HEADandlist_add_tailseem to be used (in doccomments).Quoted 1 line
Correct, but it makes sense to add the most obvious/common ones (also to make it clear that using these are supported).
"It makes sense" is subjective, and in this case I am confident it is not the right intuition to add dead code just for the sake of it.
Each of these helpers adds a potential breakage point from the C API should the latter change, so we should only add them if they are indeed necessary.
Actually, some of these helpers are not used when they could have been - you have a
is_emptymethod that rewrites the C function instead of calling the helper. The only helpers that are unjustified as of now aslist_addandlist_del, and these are easy to add when they become necessary.
Quoted 7 lines
But this raises an interesting dilemma: these helpers cannot be inlined and add the overhead of a function call. On the other hand, the definition of
list_headis so excessively simple that manipulating it directly is virtually as intuitive as invoking the helper - and doesn't bear the overhead. So should we double-down on these helpers, or just drop them completely and re-implement the list functionality we need for increased performance?
You do have a point that we have an abstraction leak anyway, so the question is do we need helpers at all.
I am torn on this. On the one hand, if someone changes how list_head api works, then the rust side breaks (though that is easy to flag though via doc tests). On the other hand, we have the function call overhead you pointed and we are dealing with the pointers in rust directly anyway in some cases.
Plus more often than not, new separate list variations (like hlist) are added for new use case than modifying existing ones, so it is just a small risk to directly reimplement list helpers in rust.
I do like your idea though because it makes it a bit easier to add support for other list variants if needed (hlist, llist, RCU lists etc) since we don’t need wrappers per-se.
Ok I guess I will drop all the helpers then unless there is a good reason to still keep them and see what it looks like. Some of them might have debugging code that’s on the side C that we may not want to skip. The RCU list api certainly does.
Thanks.
Quoted 4 lines · Joel Fernandes
Quoted 4 lines · Alexandre Courbot
Quoted 2 lines · Joel Fernandes
Quoted 2 lines
Quoted 1 line · Alexandre Courbot
On Wed Nov 12, 2025 at 2:13 AM JST, Joel Fernandes wrote:
...
Quoted 2 lines
You do have a point that we have an abstraction leak anyway, so the question is do we need helpers at all.
I'm writing this in order to suggest a stance in this area, for future feature tradeoffs. If this is somehow "off", I'll upgrade my thinking, but at the moment I'm very comfortable making the following claims:
Quoted 1 line
I am torn on this. On the one hand, if someone changes how
list_headapi works, then the rust side breaks
OK, this is not going to happen, at list not without a truly epic, long-term effort, accompanied by *lots* of publicity. The list_head API is just too foundational to change easily.
It's been stable since *at least* 2006. The only change since then has been to add WRITE_ONCE() wrappers to the INIT_LIST_HEAD implementation--and that is not an API change.
Anything is possible, but this is sufficiently far out there that it should not count for much here.
(though that is easy to flag though via doc tests). On the other hand, we have the function call overhead you pointed and we are dealing with the pointers in rust directly anyway in some cases.
Whereas this is very significant! We really, really do not want to accept a performance loss vs. C, without an excellent justification.
So I think you've made the right decision. The above is just to help solidify the reasons why.
thanks,
Signature · 1 line
John Hubbard
Quoted 13 lines · John Hubbard
Quoted 2 lines
I am torn on this. On the one hand, if someone changes how
list_headapi works, then the rust side breaksOK, this is not going to happen, at list not without a truly epic, long-term effort, accompanied by *lots* of publicity. The
list_headAPI is just too foundational to change easily.It's been stable since *at least* 2006. The only change since then has been to add
WRITE_ONCE()wrappers to theINIT_LIST_HEADimplementation--and that is not an API change.Anything is possible, but this is sufficiently far out there that it should not count for much here.
Quoted 7 lines
(though that is easy to flag though via doc tests). On the other hand, we have the function call overhead you pointed and we are dealing with the pointers in rust directly anyway in some cases.
Whereas this is very significant! We really, really do not want to accept a performance loss vs. C, without an excellent justification.
So I think you've made the right decision. The above is just to help solidify the reasons why.
Yeah, these are good points. Thanks John.
- Joel
Alexandre Courbot
reviewerQuoted 18 lines · Joel Fernandes
Quoted 15 lines · John Hubbard
Quoted 2 lines
I am torn on this. On the one hand, if someone changes how
list_headapi works, then the rust side breaksOK, this is not going to happen, at list not without a truly epic, long-term effort, accompanied by *lots* of publicity. The
list_headAPI is just too foundational to change easily.It's been stable since *at least* 2006. The only change since then has been to add
WRITE_ONCE()wrappers to theINIT_LIST_HEADimplementation--and that is not an API change.Anything is possible, but this is sufficiently far out there that it should not count for much here.
(though that is easy to flag though via doc tests). On the other hand, we have the function call overhead you pointed and we are dealing with the pointers in rust directly anyway in some cases.
Quoted 7 lines
Quoted 5 lines
Whereas this is very significant! We really, really do not want to accept a performance loss vs. C, without an excellent justification.
So I think you've made the right decision. The above is just to help solidify the reasons why.
Yeah, these are good points. Thanks John.
There is also at least one precedent: the Rust page_align() does not call a C helper that wraps PAGE_ALIGN(), it just reimplements it. I think list_head is a quite similar situation, but ultimately that's for the core team to say.
Quoted 25 lines · Alexandre Courbot
Quoted 24 lines · Joel Fernandes
Quoted 20 lines · John Hubbard
Quoted 2 lines
I am torn on this. On the one hand, if someone changes how
list_headapi works, then the rust side breaksOK, this is not going to happen, at list not without a truly epic, long-term effort, accompanied by *lots* of publicity. The
list_headAPI is just too foundational to change easily.It's been stable since *at least* 2006. The only change since then has been to add
WRITE_ONCE()wrappers to theINIT_LIST_HEADimplementation--and that is not an API change.Anything is possible, but this is sufficiently far out there that it should not count for much here.
(though that is easy to flag though via doc tests). On the other hand, we have the function call overhead you pointed and we are dealing with the pointers in rust directly anyway in some cases.
Whereas this is very significant! We really, really do not want to accept a performance loss vs. C, without an excellent justification.
So I think you've made the right decision. The above is just to help solidify the reasons why.
Quoted 6 lines
Quoted 1 line
Yeah, these are good points. Thanks John.
There is also at least one precedent: the Rust
page_align()does not call a C helper that wrapsPAGE_ALIGN(), it just reimplements it. I thinklist_headis a quite similar situation, but ultimately that's for the core team to say.
I don't think a one size/rule fits all will apply for this. We need carefully do it on a case-by-case basis, for example - if we implement list_add directly in rust, we'd miss out on CONFIG_LIST_HARDENED. So for that, I will still use the bindings. For INIT_LIST_HEAD and iteration, it should be Ok, though. So I'll add that directly in Rust without bindings.
Thanks.
Quoted 2 lines · Joel Fernandes
Quoted 1 line · Alexandre Courbot
On Thu Nov 27, 2025 at 2:10 PM JST, Joel Fernandes wrote:
...
Quoted 6 lines
Quoted 4 lines
There is also at least one precedent: the Rust
page_align()does not call a C helper that wrapsPAGE_ALIGN(), it just reimplements it. I thinklist_headis a quite similar situation, but ultimately that's for the core team to say.I don't think a one size/rule fits all will apply for this. We need carefully do
Case-by-case is certainly a good way to evaluate these things, yes.
Quoted 4 lines
it on a case-by-case basis, for example - if we implement
list_adddirectly in rust, we'd miss out onCONFIG_LIST_HARDENED. So for that, I will still use the bindings. ForINIT_LIST_HEADand iteration, it should be Ok, though. So I'll add that directly in Rust without bindings.
Here, I'm not so sure that even this case is a solid one. Because CONFIG_LIST_HARDENED is a way for C code to help protect against list corruption--which is generally going to come from the C side, not the Rust side, for the most part.
Let the C code have its extra checks, but on the Rust side we can either add them, or skip them--but I don't think we need to *invoke* them via the C code.
thanks,
Signature · 1 line
John Hubbard
Quoted 21 lines · John Hubbard
Quoted 2 lines · Joel Fernandes
Quoted 2 lines · Alexandre Courbot
On Thu Nov 27, 2025 at 2:10 PM JST, Joel Fernandes wrote:
...
Quoted 5 lines
Quoted 4 lines
There is also at least one precedent: the Rust
page_align()does not call a C helper that wrapsPAGE_ALIGN(), it just reimplements it. I thinklist_headis a quite similar situation, but ultimately that's for the core team to say.I don't think a one size/rule fits all will apply for this. We need carefully do
Case-by-case is certainly a good way to evaluate these things, yes.
Quoted 4 lines
it on a case-by-case basis, for example - if we implement
list_adddirectly in rust, we'd miss out onCONFIG_LIST_HARDENED. So for that, I will still use the bindings. ForINIT_LIST_HEADand iteration, it should be Ok, though. So I'll add that directly in Rust without bindings.
Quoted 8 lines
Here, I'm not so sure that even this case is a solid one. Because
CONFIG_LIST_HARDENEDis a way for C code to help protect against list corruption--which is generally going to come from the C side, not the Rust side, for the most part.Let the C code have its extra checks, but on the Rust side we can either add them, or skip them--but I don't think we need to *invoke* them via the C code.
I think we do. This is a C list abstraction (rust interacting with C-side code, the list_head comes from C bindings). If we want a pure rust list, we should not be using clist in the first place. There is list.rs for that.
Imagine C and rust both adding items to a C list but one is having debugging code but the other does not. That is really weird.
Thanks.
Quoted 7 lines
thanks,
--
John Hubbard
Daniel Almeida
reviewerQuoted 28 lines · John Hubbard
Quoted 4 lines · Joel Fernandes
Quoted 4 lines · Alexandre Courbot
Quoted 2 lines · Joel Fernandes
Quoted 2 lines
Quoted 1 line · Alexandre Courbot
On Wed Nov 12, 2025 at 2:13 AM JST, Joel Fernandes wrote:
...
Quoted 2 lines
You do have a point that we have an abstraction leak anyway, so the question is do we need helpers at all.
I'm writing this in order to suggest a stance in this area, for future feature tradeoffs. If this is somehow "off", I'll upgrade my thinking, but at the moment I'm very comfortable making the following claims:
Quoted 1 line
I am torn on this. On the one hand, if someone changes how
list_headapi works, then the rust side breaksOK, this is not going to happen, at list not without a truly epic, long-term effort, accompanied by *lots* of publicity. The
list_headAPI is just too foundational to change easily.It's been stable since *at least* 2006. The only change since then has been to add
WRITE_ONCE()wrappers to theINIT_LIST_HEADimplementation--and that is not an API change.
Quoted 7 lines
Anything is possible, but this is sufficiently far out there that it should not count for much here.
(though that is easy to flag though via doc tests). On the other hand, we have the function call overhead you pointed and we are dealing with the pointers in rust directly anyway in some cases.
Whereas this is very significant! We really, really do not want to accept a performance loss vs. C, without an excellent justification.
JFYI, and let me preface this by saying I know little about NVIDIA hardware: this overhead had very little impact on the Rust Arm Mali driver.
Quoted 10 lines
So I think you've made the right decision. The above is just to help solidify the reasons why.
thanks,
Signature · 1 line
John Hubbard
— Daniel
Daniel Almeida
reviewerQuoted 90 lines · Alexandre Courbot
Quoted 70 lines · Joel Fernandes
Quoted 61 lines · Alexandre Courbot
Quoted 56 lines · Joel Fernandes
Add Rust helper functions for common C linked list operations that are implemented as macros or inline functions and thus not directly accessible from Rust.
Signed-off-by Joel Fernandes <[email protected]>---
rust/helpers/helpers.c| 1 +rust/helpers/list.c| 32 ++++++++++++++++++++++++++++++++2 files changed, 33 insertions(+)create mode 100644
rust/helpers/list.crust/helpers/helpers.c +1
-0@@ -32,6 +32,7 @@#include "io.c" #include "jump_label.c" #include "kunit.c" +#include "list.c" #include "maple_tree.c" #include "mm.c" #include "mutex.c" rust/helpers/list.c new file +27
-0@@ -0,0 +1,32 @@ +// SPDX-License-Identifier: GPL-2.0 + +/* +* Helpers for C Circular doubly linked list implementation. +*/ + +#include <linux/list.h> + +bool rust_helper_list_empty (const struct list_head *head) +{ +return list_empty (head); +} + +void rust_helper_list_del (struct list_head *entry) +{ +list_del (entry); +} + +void rust_helper_INIT_LIST_HEAD (struct list_head *list) +{ +INIT_LIST_HEAD (list); +} + +void rust_helper_list_add (struct list_head *new,struct list_head *head) +{ +list_add (new, head); +}Quoted 8 lines
rust/helpers/list.c line 32
Quoted 5 lines
rust/helpers/list.c new file +5
-0+ +void rust_helper_list_add_tail (struct list_head *new,struct list_head *head) +{ +list_add_tail (new, head); +}Just noticed, but of these helpers only
INIT_LIST_HEADandlist_add_tailseem to be used (in doccomments).Quoted 1 line
Correct, but it makes sense to add the most obvious/common ones (also to make it clear that using these are supported).
"It makes sense" is subjective, and in this case I am confident it is not the right intuition to add dead code just for the sake of it.
Each of these helpers adds a potential breakage point from the C API should the latter change, so we should only add them if they are indeed necessary.
Actually, some of these helpers are not used when they could have been - you have a
is_emptymethod that rewrites the C function instead of calling the helper. The only helpers that are unjustified as of now aslist_addandlist_del, and these are easy to add when they become necessary.
Quoted 7 lines
But this raises an interesting dilemma: these helpers cannot be inlined and add the overhead of a function call. On the other hand, the definition of
list_headis so excessively simple that manipulating it directly is virtually as intuitive as invoking the helper - and doesn't bear the overhead. So should we double-down on these helpers, or just drop them completely and re-implement the list functionality we need for increased performance?
IIRC, there is someone working to fix this overhead by working on LTO support, or at least I remember this talk at some iteration of Kangrejos.
If you use the helpers, you’ll be covered in the future.
— Daniel
Alexandre Courbot
reviewerQuoted 98 lines · Daniel Almeida
Quoted 90 lines · Alexandre Courbot
Quoted 70 lines · Joel Fernandes
Quoted 61 lines · Alexandre Courbot
Quoted 56 lines · Joel Fernandes
Add Rust helper functions for common C linked list operations that are implemented as macros or inline functions and thus not directly accessible from Rust.
Signed-off-by Joel Fernandes <[email protected]>---
rust/helpers/helpers.c| 1 +rust/helpers/list.c| 32 ++++++++++++++++++++++++++++++++2 files changed, 33 insertions(+)create mode 100644
rust/helpers/list.crust/helpers/helpers.c +1
-0@@ -32,6 +32,7 @@#include "io.c" #include "jump_label.c" #include "kunit.c" +#include "list.c" #include "maple_tree.c" #include "mm.c" #include "mutex.c" rust/helpers/list.c new file +27
-0@@ -0,0 +1,32 @@ +// SPDX-License-Identifier: GPL-2.0 + +/* +* Helpers for C Circular doubly linked list implementation. +*/ + +#include <linux/list.h> + +bool rust_helper_list_empty (const struct list_head *head) +{ +return list_empty (head); +} + +void rust_helper_list_del (struct list_head *entry) +{ +list_del (entry); +} + +void rust_helper_INIT_LIST_HEAD (struct list_head *list) +{ +INIT_LIST_HEAD (list); +} + +void rust_helper_list_add (struct list_head *new,struct list_head *head) +{ +list_add (new, head); +}Quoted 8 lines
rust/helpers/list.c line 32
Quoted 5 lines
rust/helpers/list.c new file +5
-0+ +void rust_helper_list_add_tail (struct list_head *new,struct list_head *head) +{ +list_add_tail (new, head); +}Just noticed, but of these helpers only
INIT_LIST_HEADandlist_add_tailseem to be used (in doccomments).Quoted 1 line
Correct, but it makes sense to add the most obvious/common ones (also to make it clear that using these are supported).
"It makes sense" is subjective, and in this case I am confident it is not the right intuition to add dead code just for the sake of it.
Each of these helpers adds a potential breakage point from the C API should the latter change, so we should only add them if they are indeed necessary.
Actually, some of these helpers are not used when they could have been - you have a
is_emptymethod that rewrites the C function instead of calling the helper. The only helpers that are unjustified as of now aslist_addandlist_del, and these are easy to add when they become necessary.Quoted 7 lines
But this raises an interesting dilemma: these helpers cannot be inlined and add the overhead of a function call. On the other hand, the definition of
list_headis so excessively simple that manipulating it directly is virtually as intuitive as invoking the helper - and doesn't bear the overhead. So should we double-down on these helpers, or just drop them completely and re-implement the list functionality we need for increased performance?
Quoted 4 lines
IIRC, there is someone working to fix this overhead by working on LTO support, or at least I remember this talk at some iteration of Kangrejos.
If you use the helpers, you’ll be covered in the future.
Looks like the series has just been posted:
https://lore.kernel.org/all/[email protected]/
... which I guess means we can/should use helpers whenever they are available then. Joel, please ignore my rant above (except the part about unused helpers) and feel free to use the C helpers whenever relevant. I think the argument about the structure of list_head not changing can also apply to the helper API.