Define the ListLinks struct, which wraps the prev/next pointers that
will be used to insert values into a List in a future patch. Also
define the ListItem trait, which is implemented by structs that have a
ListLinks field.

The ListItem trait provides four different methods that are all
essentially container_of or the reverse of container_of. Two of them are
used before inserting/after removing an item from the list, and the two
others are used when looking at a value without changing whether it is
in a list. This distinction is introduced because it is needed for the
patch that adds support for heterogeneous lists, which are implemented
by adding a third pointer field with a fat pointer to the full struct.
When inserting into the heterogeneous list, the pointer-to-self is
updated to have the right vtable, and the container_of operation is
implemented by just returning that pointer instead of using the real
container_of operation.

Signed-off-by: Alice Ryhl <aliceryhl@google.com>
---
 rust/kernel/list.rs | 115 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 115 insertions(+)

diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs
index c5caa0f6105c..76597c49fa56 100644
--- a/rust/kernel/list.rs
+++ b/rust/kernel/list.rs
@@ -4,7 +4,122 @@
 
 //! A linked list implementation.
 
+use crate::init::PinInit;
+use crate::types::Opaque;
+use core::ptr;
+
 mod arc;
 pub use self::arc::{
     impl_list_arc_safe, AtomicListArcTracker, ListArc, ListArcSafe, TryNewListArc,
 };
+
+/// Implemented by types where a [`ListArc<Self>`] can be inserted into a `List`.
+///
+/// # Safety
+///
+/// Implementers must ensure that they provide the guarantees documented on the three methods
+/// below.
+///
+/// [`ListArc<Self>`]: ListArc
+pub unsafe trait ListItem<const ID: u64 = 0>: ListArcSafe<ID> {
+    /// Views the [`ListLinks`] for this value.
+    ///
+    /// # Guarantees
+    ///
+    /// * If there is a currently active call to `prepare_to_insert`, then this returns the same
+    ///   pointer as the one returned by the currently active call to `prepare_to_insert`.
+    /// * If there is no currently active call to `prepare_to_insert`, then the returned pointer
+    ///   points at a read-only [`ListLinks`] with two null pointers.
+    ///
+    /// # Safety
+    ///
+    /// The provided pointer must point at a valid value. (It need not be in an `Arc`.)
+    unsafe fn view_links(me: *const Self) -> *mut ListLinks<ID>;
+
+    /// View the full value given its [`ListLinks`] field.
+    ///
+    /// Can only be used when the value is in a list.
+    ///
+    /// # Guarantees
+    ///
+    /// * Returns the same pointer as the one passed to the previous call to `prepare_to_insert`.
+    /// * The returned pointer is valid until the next call to `post_remove`.
+    ///
+    /// # Safety
+    ///
+    /// * The provided pointer must originate from the previous call to `prepare_to_insert`, or
+    ///   from a call to `view_links` that happened after the previous call to `prepare_to_insert`.
+    /// * Since the previous call to `prepare_to_insert`, the `post_remove` method must not have
+    ///   been called.
+    unsafe fn view_value(me: *mut ListLinks<ID>) -> *const Self;
+
+    /// This is called when an item is inserted into a `List`.
+    ///
+    /// # Guarantees
+    ///
+    /// The caller is granted exclusive access to the returned [`ListLinks`] until `post_remove` is
+    /// called.
+    ///
+    /// # Safety
+    ///
+    /// * The provided pointer must point at a valid value in an [`Arc`].
+    /// * Calls to `prepare_to_insert` and `post_remove` on the same value must alternate.
+    /// * The caller must own the [`ListArc`] for this value.
+    /// * The caller must not give up ownership of the [`ListArc`] unless `post_remove` has been
+    ///   called after this call to `prepare_to_insert`.
+    ///
+    /// [`Arc`]: crate::sync::Arc
+    unsafe fn prepare_to_insert(me: *const Self) -> *mut ListLinks<ID>;
+
+    /// This undoes a previous call to `prepare_to_insert`.
+    ///
+    /// # Guarantees
+    ///
+    /// The returned pointer is the pointer that was originally passed to `prepare_to_insert`.
+    ///
+    /// The caller is free to recreate the `ListArc` after this call.
+    ///
+    /// # Safety
+    ///
+    /// The provided pointer must be the pointer returned by the previous call to
+    /// `prepare_to_insert`.
+    unsafe fn post_remove(me: *mut ListLinks<ID>) -> *const Self;
+}
+
+#[repr(C)]
+#[derive(Copy, Clone)]
+struct ListLinksFields {
+    next: *mut ListLinksFields,
+    prev: *mut ListLinksFields,
+}
+
+/// The prev/next pointers for an item in a linked list.
+///
+/// # Invariants
+///
+/// The fields are null if and only if this item is not in a list.
+#[repr(transparent)]
+pub struct ListLinks<const ID: u64 = 0> {
+    #[allow(dead_code)]
+    inner: Opaque<ListLinksFields>,
+}
+
+// SAFETY: The next/prev fields of a ListLinks can be moved across thread boundaries.
+unsafe impl<const ID: u64> Send for ListLinks<ID> {}
+// SAFETY: The type is opaque so immutable references to a ListLinks are useless. Therefore, it's
+// okay to have immutable access to a ListLinks from several threads at once.
+unsafe impl<const ID: u64> Sync for ListLinks<ID> {}
+
+impl<const ID: u64> ListLinks<ID> {
+    /// 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
+        // not be constructed in an `Arc` that already has a `ListArc`.
+        ListLinks {
+            inner: Opaque::new(ListLinksFields {
+                prev: ptr::null_mut(),
+                next: ptr::null_mut(),
+            }),
+        }
+    }
+}

-- 
2.44.0.478.gd926399ef9-goog

On 02.04.24 14:17, Alice Ryhl wrote:
> +impl<const ID: u64> ListLinks<ID> {
> +    /// 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
> +        // not be constructed in an `Arc` that already has a `ListArc`.
> +        ListLinks {
> +            inner: Opaque::new(ListLinksFields {
> +                prev: ptr::null_mut(),
> +                next: ptr::null_mut(),
> +            }),

You might want to implement `Zeroable` (using the derive macro) for this
struct, since then you could just return `init::zeroed()`.
You can also use that for the `ListLinksSelfPtr` in the other patch.

-- 
Cheers,
Benno

> +        }
> +    }
> +}
> 
> --
> 2.44.0.478.gd926399ef9-goog
> 

On Fri, Apr 5, 2024 at 11:47 AM Benno Lossin <benno.lossin@proton.me> wrote:
>
> On 02.04.24 14:17, Alice Ryhl wrote:
> > +impl<const ID: u64> ListLinks<ID> {
> > +    /// 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
> > +        // not be constructed in an `Arc` that already has a `ListArc`.
> > +        ListLinks {
> > +            inner: Opaque::new(ListLinksFields {
> > +                prev: ptr::null_mut(),
> > +                next: ptr::null_mut(),
> > +            }),
>
> You might want to implement `Zeroable` (using the derive macro) for this
> struct, since then you could just return `init::zeroed()`.
> You can also use that for the `ListLinksSelfPtr` in the other patch.

Sure, that makes sense to me. I'll go for that.

Alice

On 02.04.24 14:17, Alice Ryhl wrote:
> +/// Implemented by types where a [`ListArc<Self>`] can be inserted into a `List`.
> +///
> +/// # Safety
> +///
> +/// Implementers must ensure that they provide the guarantees documented on the three methods
> +/// below.
> +///
> +/// [`ListArc<Self>`]: ListArc
> +pub unsafe trait ListItem<const ID: u64 = 0>: ListArcSafe<ID> {
> +    /// Views the [`ListLinks`] for this value.
> +    ///
> +    /// # Guarantees
> +    ///
> +    /// * If there is a currently active call to `prepare_to_insert`, then this returns the same
> +    ///   pointer as the one returned by the currently active call to `prepare_to_insert`.

I was a bit confused by the term "active call to `prepare_to_insert`",
since I thought that the function would need to be executed at this
moment. I inferred from below that you mean by this that there has been
a `prepare_to_insert` call, but not yet a corresponding `post_remove`
call.
I did not yet find a better way to phrase this.

I like putting the guarantees on the functions very much.

-- 
Cheers,
Benno

On Wed, Apr 3, 2024 at 5:57 PM Benno Lossin <benno.lossin@proton.me> wrote:
>
> On 02.04.24 14:17, Alice Ryhl wrote:
> > +/// Implemented by types where a [`ListArc<Self>`] can be inserted into a `List`.
> > +///
> > +/// # Safety
> > +///
> > +/// Implementers must ensure that they provide the guarantees documented on the three methods
> > +/// below.
> > +///
> > +/// [`ListArc<Self>`]: ListArc
> > +pub unsafe trait ListItem<const ID: u64 = 0>: ListArcSafe<ID> {
> > +    /// Views the [`ListLinks`] for this value.
> > +    ///
> > +    /// # Guarantees
> > +    ///
> > +    /// * If there is a currently active call to `prepare_to_insert`, then this returns the same
> > +    ///   pointer as the one returned by the currently active call to `prepare_to_insert`.
>
> I was a bit confused by the term "active call to `prepare_to_insert`",
> since I thought that the function would need to be executed at this
> moment. I inferred from below that you mean by this that there has been
> a `prepare_to_insert` call, but not yet a corresponding `post_remove`
> call.
> I did not yet find a better way to phrase this.
>
> I like putting the guarantees on the functions very much.

How about this?

If there is a previous call to `prepare_to_insert` and there is no
call to `post_remove` since the most recent such call, then this
returns the same pointer as the one returned by the most recent call
to `prepare_to_insert`.

Otherwise, the returned pointer points at a read-only [`ListLinks`]
with two null pointers.

Alice

On 04.04.24 16:03, Alice Ryhl wrote:
> On Wed, Apr 3, 2024 at 5:57 PM Benno Lossin <benno.lossin@proton.me> wrote:
>>
>> On 02.04.24 14:17, Alice Ryhl wrote:
>>> +/// Implemented by types where a [`ListArc<Self>`] can be inserted into a `List`.
>>> +///
>>> +/// # Safety
>>> +///
>>> +/// Implementers must ensure that they provide the guarantees documented on the three methods
>>> +/// below.
>>> +///
>>> +/// [`ListArc<Self>`]: ListArc
>>> +pub unsafe trait ListItem<const ID: u64 = 0>: ListArcSafe<ID> {
>>> +    /// Views the [`ListLinks`] for this value.
>>> +    ///
>>> +    /// # Guarantees
>>> +    ///
>>> +    /// * If there is a currently active call to `prepare_to_insert`, then this returns the same
>>> +    ///   pointer as the one returned by the currently active call to `prepare_to_insert`.
>>
>> I was a bit confused by the term "active call to `prepare_to_insert`",
>> since I thought that the function would need to be executed at this
>> moment. I inferred from below that you mean by this that there has been
>> a `prepare_to_insert` call, but not yet a corresponding `post_remove`
>> call.
>> I did not yet find a better way to phrase this.
>>
>> I like putting the guarantees on the functions very much.
> 
> How about this?
> 
> If there is a previous call to `prepare_to_insert` and there is no
> call to `post_remove` since the most recent such call, then this
> returns the same pointer as the one returned by the most recent call
> to `prepare_to_insert`.
> 
> Otherwise, the returned pointer points at a read-only [`ListLinks`]
> with two null pointers.
Sounds good.

-- 
Cheers,
Benno