Received-SPF: pass (google.com: domain of linux-kernel+bounces-190494-linux.lists.archive=gmail.com@vger.kernel.org designates 2604:1380:4601:e00::3 as permitted sender) client-ip=2604:1380:4601:e00::3;
Precedence: bulk
MIME-Version: 1.0
References: <20240506-linked-list-v2-0-7b910840c91f@google.com>
 <20240506-linked-list-v2-3-7b910840c91f@google.com> <82220d9b-3f4f-43ba-ad15-412ceb349a56@proton.me>
In-Reply-To: <82220d9b-3f4f-43ba-ad15-412ceb349a56@proton.me>
From: Alice Ryhl <aliceryhl@google.com>
Date: Mon, 27 May 2024 13:42:00 +0200
Message-ID: <CAH5fLghoHiU928pCzMy3DRZzbw7J_HUVMObGXGtX-0ncVJnP3Q@mail.gmail.com>
Subject: Re: [PATCH v2 3/9] rust: list: add struct with prev/next pointers
To: Benno Lossin <benno.lossin@proton.me>
Cc: Miguel Ojeda <ojeda@kernel.org>, Andrew Morton <akpm@linux-foundation.org>, 
	Alex Gaynor <alex.gaynor@gmail.com>, Wedson Almeida Filho <wedsonaf@gmail.com>, 
	Boqun Feng <boqun.feng@gmail.com>, Gary Guo <gary@garyguo.net>, 
	=?UTF-8?Q?Bj=C3=B6rn_Roy_Baron?= <bjorn3_gh@protonmail.com>, 
	Andreas Hindborg <a.hindborg@samsung.com>, Marco Elver <elver@google.com>, 
	Kees Cook <keescook@chromium.org>, Coly Li <colyli@suse.de>, Paolo Abeni <pabeni@redhat.com>, 
	Pierre Gondois <pierre.gondois@arm.com>, Ingo Molnar <mingo@kernel.org>, 
	Jakub Kicinski <kuba@kernel.org>, Wei Yang <richard.weiyang@gmail.com>, 
	Matthew Wilcox <willy@infradead.org>, linux-kernel@vger.kernel.org, 
	rust-for-linux@vger.kernel.org
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

On Mon, May 27, 2024 at 11:58=E2=80=AFAM Benno Lossin <benno.lossin@proton.=
me> wrote:
>
> On 06.05.24 11:53, Alice Ryhl wrote:
> > 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 ar=
e
> > 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 | 116 ++++++++++++++++++++++++++++++++++++++++++++=
++++++++
> >  1 file changed, 116 insertions(+)
> >
> > diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs
> > index c5caa0f6105c..b5cfbb96a392 100644
> > --- a/rust/kernel/list.rs
> > +++ b/rust/kernel/list.rs
> > @@ -4,7 +4,123 @@
> >
> >  //! 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, Tr=
yNewListArc,
> >  };
> > +
> > +/// Implemented by types where a [`ListArc<Self>`] can be inserted int=
o a `List`.
> > +///
> > +/// # Safety
> > +///
> > +/// Implementers must ensure that they provide the guarantees document=
ed on the three methods
>
> I would not mention the number of methods, since it is difficult to
> maintain and doesn't actually provide any value (it already is incorrect =
:)

I will remove the mention of a number.

> > +    /// This is called when an item is inserted into a `List`.
> > +    ///
> > +    /// # Guarantees
> > +    ///
> > +    /// The caller is granted exclusive access to the returned [`ListL=
inks`] 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 v=
alue must alternate.
>
> Are there any synchronization requirements? Am I allowed to call
> `prepare_to_insert` and `post_remove` on different threads without
> synchronizing?

No, if you call them at the same time, then they aren't alternating.

> > +    /// * The caller must own the [`ListArc`] for this value.
> > +    /// * The caller must not give up ownership of the [`ListArc`] unl=
ess `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.
>
> As I read the requirements on `prepare_to_insert`, the caller is not
> required to deconstruct the `ListArc`. For example the caller is allowed
> to `clone_arc()` and then `into_raw()` and then pass that pointer to
> `prepare_to_insert`.
> So I would just remove this sentence.

I will remove it.

> > +    ///
> > +    /// # Safety
> > +    ///
> > +    /// The provided pointer must be the pointer returned by the previ=
ous call to
>
> Does "most recent call" make more sense? I find previous call a bit
> weird. (also in the requirements above)

Sure, I can say "most recent".

Alice

> ---
> Cheers,
> Benno
>
> > +    /// `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 =3D 0> {
> > +    #[allow(dead_code)]
> > +    inner: Opaque<ListLinksFields>,
> > +}
> > +
> > +// SAFETY: The next/prev fields of a ListLinks can be moved across thr=
ead boundaries.
> > +unsafe impl<const ID: u64> Send for ListLinks<ID> {}
> > +// SAFETY: The type is opaque so immutable references to a ListLinks a=
re useless. Therefore, it's
> > +// okay to have immutable access to a ListLinks from several threads a=
t 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 existi=
ng `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.0.rc1.225.g2a3ae87e7f-goog
> >
>
>