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..63e6f6a47964 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 methods provided by
+/// this trait.
+///
+/// [`ListArc<Self>`]: ListArc
+pub unsafe trait ListItem<const ID: u64 = 0>: ListArcSafe<ID> {
+    /// Views the [`ListLinks`] for this value.
+    ///
+    /// # Guarantees
+    ///
+    /// 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.
+    ///
+    /// # 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 most recent 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 most recent call to `prepare_to_insert`, or
+    ///   from a call to `view_links` that happened after the most recent call to
+    ///   `prepare_to_insert`.
+    /// * Since the most recent 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`.
+    ///
+    /// # Safety
+    ///
+    /// The provided pointer must be the pointer returned by the most recent 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.45.2.1089.g2a221341d9-goog

On 23.07.24 10:22, Alice Ryhl wrote:
> +/// 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>,

Do you really need `Opaque`? Or would `UnsafeCell` be enough? (If it is
enough and you change this, be aware that `Opaque` is `!Unpin`, so if
you intend for `ListLinks` to also be `!Unpin`, then you need a
`PhantomPinned`)

> +}
> +
> +// SAFETY: The next/prev fields of a ListLinks can be moved across thread boundaries.

Why? This is not a justification.

> +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.

You don't need to argue via `Opaque`, the type doesn't expose any
`&self` functions, so there are no functions to consider.

---
Cheers,
Benno

> +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.45.2.1089.g2a221341d9-goog
> 

On Wed, Jul 31, 2024 at 8:41 PM Benno Lossin <benno.lossin@proton.me> wrote:
>
> On 23.07.24 10:22, Alice Ryhl wrote:
> > +/// 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>,
>
> Do you really need `Opaque`? Or would `UnsafeCell` be enough? (If it is
> enough and you change this, be aware that `Opaque` is `!Unpin`, so if
> you intend for `ListLinks` to also be `!Unpin`, then you need a
> `PhantomPinned`)

I need the `!Unpin` part for aliasing.

> > +}
> > +
> > +// SAFETY: The next/prev fields of a ListLinks can be moved across thread boundaries.
>
> Why? This is not a justification.

What would you say?

> > +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.
>
> You don't need to argue via `Opaque`, the type doesn't expose any
> `&self` functions, so there are no functions to consider.

I'm not arguing via the `Opaque` type. I'm just using "opaque" as a
normal english word with its normal meaning.

Alice

On 01.08.24 11:42, Alice Ryhl wrote:
> On Wed, Jul 31, 2024 at 8:41 PM Benno Lossin <benno.lossin@proton.me> wrote:
>>
>> On 23.07.24 10:22, Alice Ryhl wrote:
>>> +/// 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>,
>>
>> Do you really need `Opaque`? Or would `UnsafeCell` be enough? (If it is
>> enough and you change this, be aware that `Opaque` is `!Unpin`, so if
>> you intend for `ListLinks` to also be `!Unpin`, then you need a
>> `PhantomPinned`)
> 
> I need the `!Unpin` part for aliasing.

Oh good point, do you mind adding a comment for that?

>>> +}
>>> +
>>> +// SAFETY: The next/prev fields of a ListLinks can be moved across thread boundaries.
>>
>> Why? This is not a justification.
> 
> What would you say?

While trying to come up with a safety comment I thought about the
following: this impl does not depend on the type that is behind the
pointer (ie the type containing the `ListLinks`). Thus this `ListLinks`
will always implement `Send` even if the pointed-to value does not.
What we could do (and what definitely would be correct) is this:
`List` can only be used with `Send` types, then we could implement
`Send` for `ListLinks`. But I haven't actually come up with a problem,
so there might a more permissive solution.
Do you have a use-case where you need `!Send` types in a list?

Here is a part of my reasoning: If the pointed-to value is `!Send`, then
the `List` item type must also be `!Send`. Thus all list operations take
place on the same thread (since the `List` will be `!Send`). Therefore
nobody can access the `prev`/`next` pointers from another thread.

But this does not justify that `ListLinks` can be made `Send`. (although
there isn't actually a problem)

>>> +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.
>>
>> You don't need to argue via `Opaque`, the type doesn't expose any
>> `&self` functions, so there are no functions to consider.
> 
> I'm not arguing via the `Opaque` type. I'm just using "opaque" as a
> normal english word with its normal meaning.

Oh I see, then it's fine.

---
Cheers,
Benno

On Thu, Aug 1, 2024 at 12:45 PM Benno Lossin <benno.lossin@proton.me> wrote:
>
> On 01.08.24 11:42, Alice Ryhl wrote:
> > On Wed, Jul 31, 2024 at 8:41 PM Benno Lossin <benno.lossin@proton.me> wrote:
> >>
> >> On 23.07.24 10:22, Alice Ryhl wrote:
> >>> +/// 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>,
> >>
> >> Do you really need `Opaque`? Or would `UnsafeCell` be enough? (If it is
> >> enough and you change this, be aware that `Opaque` is `!Unpin`, so if
> >> you intend for `ListLinks` to also be `!Unpin`, then you need a
> >> `PhantomPinned`)
> >
> > I need the `!Unpin` part for aliasing.
>
> Oh good point, do you mind adding a comment for that?
>
> >>> +}
> >>> +
> >>> +// SAFETY: The next/prev fields of a ListLinks can be moved across thread boundaries.
> >>
> >> Why? This is not a justification.
> >
> > What would you say?
>
> While trying to come up with a safety comment I thought about the
> following: this impl does not depend on the type that is behind the
> pointer (ie the type containing the `ListLinks`). Thus this `ListLinks`
> will always implement `Send` even if the pointed-to value does not.
> What we could do (and what definitely would be correct) is this:
> `List` can only be used with `Send` types, then we could implement
> `Send` for `ListLinks`. But I haven't actually come up with a problem,
> so there might a more permissive solution.
> Do you have a use-case where you need `!Send` types in a list?
>
> Here is a part of my reasoning: If the pointed-to value is `!Send`, then
> the `List` item type must also be `!Send`. Thus all list operations take
> place on the same thread (since the `List` will be `!Send`). Therefore
> nobody can access the `prev`/`next` pointers from another thread.
>
> But this does not justify that `ListLinks` can be made `Send`. (although
> there isn't actually a problem)

I don't think there's any reason to forbid lists with !Send types. The
List just becomes !Send too.

Alice

On 01.08.24 14:51, Alice Ryhl wrote:
> On Thu, Aug 1, 2024 at 12:45 PM Benno Lossin <benno.lossin@proton.me> wrote:
>>
>> On 01.08.24 11:42, Alice Ryhl wrote:
>>> On Wed, Jul 31, 2024 at 8:41 PM Benno Lossin <benno.lossin@proton.me> wrote:
>>>>
>>>> On 23.07.24 10:22, Alice Ryhl wrote:
>>>>> +/// 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>,
>>>>
>>>> Do you really need `Opaque`? Or would `UnsafeCell` be enough? (If it is
>>>> enough and you change this, be aware that `Opaque` is `!Unpin`, so if
>>>> you intend for `ListLinks` to also be `!Unpin`, then you need a
>>>> `PhantomPinned`)
>>>
>>> I need the `!Unpin` part for aliasing.
>>
>> Oh good point, do you mind adding a comment for that?
>>
>>>>> +}
>>>>> +
>>>>> +// SAFETY: The next/prev fields of a ListLinks can be moved across thread boundaries.
>>>>
>>>> Why? This is not a justification.
>>>
>>> What would you say?
>>
>> While trying to come up with a safety comment I thought about the
>> following: this impl does not depend on the type that is behind the
>> pointer (ie the type containing the `ListLinks`). Thus this `ListLinks`
>> will always implement `Send` even if the pointed-to value does not.
>> What we could do (and what definitely would be correct) is this:
>> `List` can only be used with `Send` types, then we could implement
>> `Send` for `ListLinks`. But I haven't actually come up with a problem,
>> so there might a more permissive solution.
>> Do you have a use-case where you need `!Send` types in a list?
>>
>> Here is a part of my reasoning: If the pointed-to value is `!Send`, then
>> the `List` item type must also be `!Send`. Thus all list operations take
>> place on the same thread (since the `List` will be `!Send`). Therefore
>> nobody can access the `prev`/`next` pointers from another thread.
>>
>> But this does not justify that `ListLinks` can be made `Send`. (although
>> there isn't actually a problem)

I think I confused myself. The paragraph above actually explains why we
are allowed to make `ListLinks: Send`. What do you think of the
following comment:

// SAFETY: The only way to access/modify the pointers inside of `ListLinks<ID>` is via holding the
// associated `ListArc<T, ID>`. Since that type correctly implements `Send`, it is impossible to
// move this an instance of this type to a different thread if the pointees are `!Send`.

> I don't think there's any reason to forbid lists with !Send types. The
> List just becomes !Send too.

Yes, but that doesn't explain why `ListLinks` is allowed to be `Send`.

---
Cheers,
Benno

On Thu, Aug 1, 2024 at 3:46 PM Benno Lossin <benno.lossin@proton.me> wrote:
>
> On 01.08.24 14:51, Alice Ryhl wrote:
> > On Thu, Aug 1, 2024 at 12:45 PM Benno Lossin <benno.lossin@proton.me> wrote:
> >>
> >> On 01.08.24 11:42, Alice Ryhl wrote:
> >>> On Wed, Jul 31, 2024 at 8:41 PM Benno Lossin <benno.lossin@proton.me> wrote:
> >>>>
> >>>> On 23.07.24 10:22, Alice Ryhl wrote:
> >>>>> +/// 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>,
> >>>>
> >>>> Do you really need `Opaque`? Or would `UnsafeCell` be enough? (If it is
> >>>> enough and you change this, be aware that `Opaque` is `!Unpin`, so if
> >>>> you intend for `ListLinks` to also be `!Unpin`, then you need a
> >>>> `PhantomPinned`)
> >>>
> >>> I need the `!Unpin` part for aliasing.
> >>
> >> Oh good point, do you mind adding a comment for that?
> >>
> >>>>> +}
> >>>>> +
> >>>>> +// SAFETY: The next/prev fields of a ListLinks can be moved across thread boundaries.
> >>>>
> >>>> Why? This is not a justification.
> >>>
> >>> What would you say?
> >>
> >> While trying to come up with a safety comment I thought about the
> >> following: this impl does not depend on the type that is behind the
> >> pointer (ie the type containing the `ListLinks`). Thus this `ListLinks`
> >> will always implement `Send` even if the pointed-to value does not.
> >> What we could do (and what definitely would be correct) is this:
> >> `List` can only be used with `Send` types, then we could implement
> >> `Send` for `ListLinks`. But I haven't actually come up with a problem,
> >> so there might a more permissive solution.
> >> Do you have a use-case where you need `!Send` types in a list?
> >>
> >> Here is a part of my reasoning: If the pointed-to value is `!Send`, then
> >> the `List` item type must also be `!Send`. Thus all list operations take
> >> place on the same thread (since the `List` will be `!Send`). Therefore
> >> nobody can access the `prev`/`next` pointers from another thread.
> >>
> >> But this does not justify that `ListLinks` can be made `Send`. (although
> >> there isn't actually a problem)
>
> I think I confused myself. The paragraph above actually explains why we
> are allowed to make `ListLinks: Send`. What do you think of the
> following comment:
>
> // SAFETY: The only way to access/modify the pointers inside of `ListLinks<ID>` is via holding the
> // associated `ListArc<T, ID>`. Since that type correctly implements `Send`, it is impossible to
> // move this an instance of this type to a different thread if the pointees are `!Send`.

I will use that, thanks.

Alice