[RFC PATCH 0/2] rust: list: Add examples for linked list

[RFC PATCH 0/2] rust: list: Add examples for linked list

[I Hsin Cheng]

This patch series introduce runnable examples for linked list. They also
serve as the unit tests for the methods for "List".
A new initialized method is also introduced for "ListLinks", in order to
provide the ability to create a new "ListLinks" instance, and provide
simplicity for the examples.

If there exists a convenient and proper way to handle the return type
of "ListLinks::new()", e.g. "ListLinks::try_pin_init()" , then the
method won't be needed.

I Hsin Cheng (2):
  rust: list: Implement normal initializer for ListLinks
  rust: list: Add examples for linked list

 rust/kernel/list.rs | 100 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 100 insertions(+)

-- 
2.43.0

[RFC PATCH 1/2] rust: list: Implement normal initializer for ListLinks

[I Hsin Cheng]

Currently ListLinks only supports to create an initializer through
"new()", which will need further initialization because the return type
of "new()" is "impl Pininit<Self>". Not even "ListLinksSlefPtr" use the
method to create a new instance of "ListLinks".

Implement a normal method to create a new instance of type "ListLinks".
This may be redundant as long as there exist a convenient and proper way
to deal with "ListLinks::new()".

For now it's introduce for the simplicity of examples in the following
patches.

Signed-off-by: I Hsin Cheng <richard120310@gmail.com>
---
 rust/kernel/list.rs | 10 ++++++++++
 1 file changed, 10 insertions(+)

diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs
index fb93330f4af4..57d75ca16434 100644
--- a/rust/kernel/list.rs
+++ b/rust/kernel/list.rs
@@ -158,6 +158,16 @@ unsafe impl<const ID: u64> Send for ListLinks<ID> {}
 unsafe impl<const ID: u64> Sync for ListLinks<ID> {}
 
 impl<const ID: u64> ListLinks<ID> {
+    /// Create a new instance of this type.
+    pub fn new_link() -> Self {
+        ListLinks {
+            inner: Opaque::new(ListLinksFields {
+                prev: ptr::null_mut(),
+                next: ptr::null_mut(),
+            }),
+        }
+    }
+
     /// Creates a new initializer for this type.
     pub fn new() -> impl PinInit<Self> {
         // INVARIANT: Pin-init initializers can't be used on an existing `Arc`, so this value will
-- 
2.43.0

[RFC PATCH 2/2] rust: list: Add examples for linked list

[I Hsin Cheng]

Add basic examples for the structure "List". They also serve as the unit
tests for basic list methods. A simple "struct MyData" is used here to
serve as the data to form the list, the members are trivial and naive
for the simplicity of examples.

The trait "ListArcSafe<ID>" isn't tracked here, dicussions are needed to
see whether a tracker is necessary.

Link: https://github.com/Rust-for-Linux/linux/issues/1121
Signed-off-by: I Hsin Cheng <richard120310@gmail.com>
---
 rust/kernel/list.rs | 90 +++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 90 insertions(+)

diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs
index 57d75ca16434..d1954c403f67 100644
--- a/rust/kernel/list.rs
+++ b/rust/kernel/list.rs
@@ -35,6 +35,96 @@
 /// * All prev/next pointers in `ListLinks` fields of items in the list are valid and form a cycle.
 /// * For every item in the list, the list owns the associated [`ListArc`] reference and has
 ///   exclusive access to the `ListLinks` field.
+///
+/// # Examples
+///
+/// ```
+/// use kernel::list::*;
+///
+/// struct MyData { value: i32, link: ListLinks<0> };
+///
+/// impl_list_arc_safe! {
+///     impl ListArcSafe<0> for MyData { untracked; }
+/// }
+/// impl_has_list_links! {
+///     impl HasListLinks<0> for MyData { self.link }
+/// }
+/// impl_list_item! {
+///     impl ListItem<0> for MyData { using ListLinks; }
+/// }
+///
+/// let mut my_list = List::<MyData, 0>::new();
+///
+/// // The list should be empty at the moment.
+/// assert!(my_list.is_empty());
+///
+/// let item_1 = ListArc::<MyData, 0>::new(
+///     MyData {
+///         value: 10,
+///         link: ListLinks::<0>::new_link(),
+///     }, GFP_KERNEL
+/// ).unwrap();
+///
+/// let item_2 = ListArc::<MyData, 0>::new(
+///     MyData {
+///         value: 20,
+///         link: ListLinks::<0>::new_link(),
+///     }, GFP_KERNEL
+/// ).unwrap();
+///
+/// let item_3 = ListArc::<MyData, 0>::new(
+///     MyData {
+///         value: 30,
+///         link: ListLinks::<0>::new_link(),
+///     }, GFP_KERNEL
+/// ).unwrap();
+///
+/// // Append the nodes using push_back()
+/// my_list.push_back(item_1);
+/// my_list.push_back(item_2);
+/// my_list.push_back(item_3);
+///
+/// // Verify the length of the list.
+/// assert_eq!(my_list.iter().count(), 3);
+///
+/// // Iterater over the list and verify
+/// // the nodes were inserted correctly.
+/// let mut counter = 10;
+/// for item in my_list.iter() {
+///     assert_eq!(item.value, counter);
+///     counter += 10;
+/// }
+///
+/// // Pop the items out from the list and
+/// // verify their content.
+/// let item_3 = my_list.pop_back().unwrap();
+/// let item_1 = my_list.pop_front().unwrap();
+/// let item_2 = my_list.pop_front().unwrap();
+/// assert_eq!(item_1.value, 10);
+/// assert_eq!(item_2.value, 20);
+/// assert_eq!(item_3.value, 30);
+/// assert!(my_list.is_empty());
+///
+/// // Append the nodes using push_front()
+/// my_list.push_front(item_1);
+/// my_list.push_front(item_2);
+/// my_list.push_front(item_3);
+/// assert_eq!(my_list.iter().count(), 3);
+///
+/// // Use Cursor to verify the nodes were
+/// // inserted correctly.
+///
+/// let mut cursor = my_list.cursor_front().unwrap();
+/// assert_eq!(cursor.current().value, 30);
+/// cursor = cursor.next().unwrap();
+/// assert_eq!(cursor.current().value, 20);
+/// cursor = cursor.next().unwrap();
+/// assert_eq!(cursor.current().value, 10);
+/// assert!(cursor.next().is_none());
+///
+/// # Ok::<(), Error>(())
+/// ```
+///
 pub struct List<T: ?Sized + ListItem<ID>, const ID: u64 = 0> {
     first: *mut ListLinksFields,
     _ty: PhantomData<ListArc<T, ID>>,
-- 
2.43.0

Re: [RFC PATCH 1/2] rust: list: Implement normal initializer for ListLinks

[Alice Ryhl]

On Mon, Mar 10, 2025 at 03:30:39PM +0800, I Hsin Cheng wrote:
> Currently ListLinks only supports to create an initializer through
> "new()", which will need further initialization because the return type
> of "new()" is "impl Pininit<Self>". Not even "ListLinksSlefPtr" use the
> method to create a new instance of "ListLinks".
> 
> Implement a normal method to create a new instance of type "ListLinks".
> This may be redundant as long as there exist a convenient and proper way
> to deal with "ListLinks::new()".
> 
> For now it's introduce for the simplicity of examples in the following
> patches.
> 
> Signed-off-by: I Hsin Cheng <richard120310@gmail.com>

This change is not good. The ListLinks type has an invariant about when
the pointers are null. The existing constructor argues that the
invariant is satisfied because pin-init initializers can't be used in an
existing Arc. Why is that satisfied here?

Alice

Re: [RFC PATCH 1/2] rust: list: Implement normal initializer for ListLinks

[I Hsin Cheng]

On Mon, Mar 10, 2025 at 09:44:41AM +0000, Alice Ryhl wrote:
> On Mon, Mar 10, 2025 at 03:30:39PM +0800, I Hsin Cheng wrote:
> > Currently ListLinks only supports to create an initializer through
> > "new()", which will need further initialization because the return type
> > of "new()" is "impl Pininit<Self>". Not even "ListLinksSlefPtr" use the
> > method to create a new instance of "ListLinks".
> > 
> > Implement a normal method to create a new instance of type "ListLinks".
> > This may be redundant as long as there exist a convenient and proper way
> > to deal with "ListLinks::new()".
> > 
> > For now it's introduce for the simplicity of examples in the following
> > patches.
> > 
> > Signed-off-by: I Hsin Cheng <richard120310@gmail.com>
> 
> This change is not good. The ListLinks type has an invariant about when
> the pointers are null. The existing constructor argues that the
> invariant is satisfied because pin-init initializers can't be used in an
> existing Arc. Why is that satisfied here?
> 
> Alice

Hi Alice,

Thanks for your kindly review. Indeed , I was trying to find a way to
cope with "ListLinks::new()", wondering if there's any macros like
"ListLinks::try_pin_init!()" to help us deal with "impl PinInit", so I
try to send a RFC patch for it.

Sorry I overlooked "commit 52ae96f"[1], it demonstrate a good way to
handle the basic structure for "List", I'll fix the patch and send a v2
as soon as possible.

Still I would love to ask why don't we provide "ListLinks::pin_init" or
"ListLinks::try_pin_init" to support for the pin-init initializer
returned by "ListLink::new()" ? Maybe there're special reasons behind
the pin-init initializer here ? I would love to learn if that's
possible.

I tried "Kbox::pint_init" but it
wouldn't give variable of type "ListLinks".

Best regards,
I Hsin Cheng

Re: [RFC PATCH 1/2] rust: list: Implement normal initializer for ListLinks

[Alice Ryhl]

On Mon, Mar 10, 2025 at 12:14 PM I Hsin Cheng <richard120310@gmail.com> wrote:
>
> On Mon, Mar 10, 2025 at 09:44:41AM +0000, Alice Ryhl wrote:
> > On Mon, Mar 10, 2025 at 03:30:39PM +0800, I Hsin Cheng wrote:
> > > Currently ListLinks only supports to create an initializer through
> > > "new()", which will need further initialization because the return type
> > > of "new()" is "impl Pininit<Self>". Not even "ListLinksSlefPtr" use the
> > > method to create a new instance of "ListLinks".
> > >
> > > Implement a normal method to create a new instance of type "ListLinks".
> > > This may be redundant as long as there exist a convenient and proper way
> > > to deal with "ListLinks::new()".
> > >
> > > For now it's introduce for the simplicity of examples in the following
> > > patches.
> > >
> > > Signed-off-by: I Hsin Cheng <richard120310@gmail.com>
> >
> > This change is not good. The ListLinks type has an invariant about when
> > the pointers are null. The existing constructor argues that the
> > invariant is satisfied because pin-init initializers can't be used in an
> > existing Arc. Why is that satisfied here?
> >
> > Alice
>
> Hi Alice,
>
> Thanks for your kindly review. Indeed , I was trying to find a way to
> cope with "ListLinks::new()", wondering if there's any macros like
> "ListLinks::try_pin_init!()" to help us deal with "impl PinInit", so I
> try to send a RFC patch for it.
>
> Sorry I overlooked "commit 52ae96f"[1], it demonstrate a good way to
> handle the basic structure for "List", I'll fix the patch and send a v2
> as soon as possible.
>
> Still I would love to ask why don't we provide "ListLinks::pin_init" or
> "ListLinks::try_pin_init" to support for the pin-init initializer
> returned by "ListLink::new()" ? Maybe there're special reasons behind
> the pin-init initializer here ? I would love to learn if that's
> possible.
>
> I tried "Kbox::pint_init" but it
> wouldn't give variable of type "ListLinks".

Please see the examples from:
https://lore.kernel.org/rust-for-linux/20250210-cursor-between-v7-2-36f0215181ed@google.com/

Alice