Message-ID: <CAH5fLgj3VNyw054Bw9OrPp3QLKTv+k8+_LWCdQTuCPxV2Vg6Rw@mail.gmail.com>
Date: Tue, 6 Aug 2024 15:16:47 +0200
From: Alice Ryhl <aliceryhl@...gle.com>
To: Benno Lossin <benno.lossin@...ton.me>
Cc: Miguel Ojeda <ojeda@...nel.org>, Andrew Morton <akpm@...ux-foundation.org>, 
	Alex Gaynor <alex.gaynor@...il.com>, Wedson Almeida Filho <wedsonaf@...il.com>, 
	Boqun Feng <boqun.feng@...il.com>, Gary Guo <gary@...yguo.net>, 
	Björn Roy Baron <bjorn3_gh@...tonmail.com>, 
	Andreas Hindborg <a.hindborg@...sung.com>, Marco Elver <elver@...gle.com>, Coly Li <colyli@...e.de>, 
	Paolo Abeni <pabeni@...hat.com>, Pierre Gondois <pierre.gondois@....com>, 
	Ingo Molnar <mingo@...nel.org>, Jakub Kicinski <kuba@...nel.org>, Wei Yang <richard.weiyang@...il.com>, 
	Matthew Wilcox <willy@...radead.org>, linux-kernel@...r.kernel.org, 
	rust-for-linux@...r.kernel.org, Kees Cook <kees@...nel.org>
Subject: Re: [PATCH v3 02/10] rust: list: add ListArc

On Wed, Jul 31, 2024 at 6:47 PM Benno Lossin <benno.lossin@...ton.me> wrote:
>
> On 23.07.24 10:22, Alice Ryhl wrote:
> > The `ListArc` type can be thought of as a special reference to a
> > refcounted object that owns the permission to manipulate the
> > `next`/`prev` pointers stored in the refcounted object. By ensuring that
> > each object has only one `ListArc` reference, the owner of that
> > reference is assured exclusive access to the `next`/`prev` pointers.
> > When a `ListArc` is inserted into a `List`, the `List` takes ownership
> > of the `ListArc` reference.
> >
> > There are various strategies for ensuring that a value has only one
> > `ListArc` reference. The simplest is to convert a `UniqueArc` into a
> > `ListArc`. However, the refcounted object could also keep track of
> > whether a `ListArc` exists using a boolean, which could allow for the
> > creation of new `ListArc` references from an `Arc` reference. Whatever
> > strategy is used, the relevant tracking is referred to as "the tracking
> > inside `T`", and the `ListArcSafe` trait (and its subtraits) are used to
> > update the tracking when a `ListArc` is created or destroyed.
> >
> > Note that we allow the case where the tracking inside `T` thinks that a
> > `ListArc` exists, but actually, there isn't a `ListArc`. However, we do
> > not allow the opposite situation where a `ListArc` exists, but the
> > tracking thinks it doesn't. This is because the former can at most
> > result in us failing to create a `ListArc` when the operation could
> > succeed, whereas the latter can result in the creation of two `ListArc`
> > references.
>
> You could add at the end of this paragraph that the latter is a
> soundness issue and could lead to memory bugs, but the former cannot.

Will do.

> > This patch introduces the `impl_list_arc_safe!` macro that allows you to
> > implement `ListArcSafe` for types using the strategy where a `ListArc`
> > can only be created from a `UniqueArc`. Other strategies are introduced
> > in later patches.
>
> [...]
>
> > diff --git a/rust/kernel/list/arc.rs b/rust/kernel/list/arc.rs
> > new file mode 100644
> > index 000000000000..3b7072e58256
> > --- /dev/null
> > +++ b/rust/kernel/list/arc.rs
> > @@ -0,0 +1,348 @@
> > +// SPDX-License-Identifier: GPL-2.0
> > +
> > +// Copyright (C) 2024 Google LLC.
> > +
> > +//! A wrapper around `Arc` for linked lists.
> > +
> > +use crate::alloc::{AllocError, Flags};
> > +use crate::prelude::*;
> > +use crate::sync::{Arc, ArcBorrow, UniqueArc};
> > +use core::marker::Unsize;
> > +use core::ops::Deref;
> > +use core::pin::Pin;
> > +
> > +/// Declares that this type has some way to ensure that there is exactly one `ListArc` instance for
> > +/// this id.
> > +///
> > +/// Types that implement this trait should include some kind of logic for keeping track of whether
> > +/// a [`ListArc`] exists or not. We refer to this logic as "the tracking inside `T`".
> > +///
> > +/// We allow the case where the tracking inside `T` thinks that a [`ListArc`] exists, but actually,
> > +/// there isn't a [`ListArc`]. However, we do not allow the opposite situation where a [`ListArc`]
> > +/// exists, but the tracking thinks it doesn't. This is because the former can at most result in us
> > +/// failing to create a [`ListArc`] when the operation could succeed, whereas the latter can result
> > +/// in the creation of two [`ListArc`] references.
>
> Would be good to also add it here.

Will do.

> > +///
> > +/// A consequence of the above is that you may implement the tracking inside `T` by not actually
> > +/// keeping track of anything. To do this, you always claim that a [`ListArc`] exists, even if
> > +/// there isn't one. This implementation is allowed by the above rule, but it means that
> > +/// [`ListArc`] references can only be created if you have ownership of *all* references to the
> > +/// refcounted object, as you otherwise have no way of knowing whether a [`ListArc`] exists.
> > +pub trait ListArcSafe<const ID: u64 = 0> {
> > +    /// Informs the tracking inside this type that it now has a [`ListArc`] reference.
> > +    ///
> > +    /// This method may be called even if the tracking inside this type thinks that a `ListArc`
> > +    /// reference exists. (But only if that's not actually the case.)
> > +    ///
> > +    /// # Safety
> > +    ///
> > +    /// Must not be called if a [`ListArc`] already exist for this value.
> > +    unsafe fn on_create_list_arc_from_unique(self: Pin<&mut Self>);
> > +
> > +    /// Informs the tracking inside this type that there is no [`ListArc`] reference anymore.
> > +    ///
> > +    /// # Safety
> > +    ///
> > +    /// Must only be called if there is no [`ListArc`] reference, but the tracking thinks there is.
> > +    unsafe fn on_drop_list_arc(&self);
> > +}
> > +
> > +/// Declares that this type supports [`ListArc`].
> > +///
> > +/// When using this macro, it will only be possible to create a [`ListArc`] from a [`UniqueArc`].
> > +#[macro_export]
> > +macro_rules! impl_list_arc_safe {
> > +    (impl$({$($generics:tt)*})? ListArcSafe<$num:tt> for $t:ty { untracked; } $($rest:tt)*) => {
> > +        impl$(<$($generics)*>)? $crate::list::ListArcSafe<$num> for $t {
> > +            unsafe fn on_create_list_arc_from_unique(self: ::core::pin::Pin<&mut Self>) {}
> > +            unsafe fn on_drop_list_arc(&self) {}
> > +        }
> > +        $crate::list::impl_list_arc_safe! { $($rest)* }
> > +    };
> > +
> > +    () => {};
> > +}
> > +pub use impl_list_arc_safe;
> > +
> > +/// A wrapper around [`Arc`] that's guaranteed unique for the given id.
> > +///
> > +/// The `ListArc` type can be thought of as a special reference to a refcounted object that owns the
> > +/// permission to manipulate the `next`/`prev` pointers stored in the refcounted object. By ensuring
> > +/// that each object has only one `ListArc` reference, the owner of that reference is assured
> > +/// exclusive access to the `next`/`prev` pointers. When a `ListArc` is inserted into a `List`, the
> > +/// `List` takes ownership of the `ListArc` reference.
> > +///
> > +/// There are various strategies to ensuring that a value has only one `ListArc` reference. The
> > +/// simplest is to convert a [`UniqueArc`] into a `ListArc`. However, the refcounted object could
> > +/// also keep track of whether a `ListArc` exists using a boolean, which could allow for the
> > +/// creation of new `ListArc` references from an [`Arc`] reference. Whatever strategy is used, the
> > +/// relevant tracking is referred to as "the tracking inside `T`", and the [`ListArcSafe`] trait
> > +/// (and its subtraits) are used to update the tracking when a `ListArc` is created or destroyed.
> > +///
> > +/// Note that we allow the case where the tracking inside `T` thinks that a `ListArc` exists, but
> > +/// actually, there isn't a `ListArc`. However, we do not allow the opposite situation where a
> > +/// `ListArc` exists, but the tracking thinks it doesn't. This is because the former can at most
> > +/// result in us failing to create a `ListArc` when the operation could succeed, whereas the latter
> > +/// can result in the creation of two `ListArc` references.
> > +///
> > +/// # Invariants
> > +///
> > +/// * Each reference counted object has at most one `ListArc` for each value of `ID`.
> > +/// * The tracking inside `T` is aware that a `ListArc` reference exists.
>
> I am not entirely sure where to put this, but I think it might be good
> as the first paragraph or directly after the first:
>
>     While this `ListArc` is unique for the given id, there still might
>     exist normal `Arc` references to the object.
>
> Feel free to modify it (I am not really happy with "object").

I added something about that above the heading.

> > +#[repr(transparent)]
> > +pub struct ListArc<T, const ID: u64 = 0>
> > +where
> > +    T: ListArcSafe<ID> + ?Sized,
> > +{
> > +    arc: Arc<T>,
> > +}
>
> [...]
>
> > +    /// Transmutes an [`Arc`] into a `ListArc` without updating the tracking inside `T`.
> > +    ///
> > +    /// # Safety
> > +    ///
> > +    /// * The value must not already have a `ListArc` reference.
> > +    /// * The tracking inside `T` must think that there is a `ListArc` reference.
> > +    #[inline]
> > +    unsafe fn transmute_from_arc(arc: Arc<T>) -> Self {
>
> I think the name is inaccurate now, since it is no longer a transmute,
> so maybe `from_arc_unchecked`?

I think it's fine to keep the transmute name. It gives the right connotations.

> > +        // INVARIANT: By the safety requirements, the invariants on `ListArc` are satisfied.
> > +        Self { arc }
> > +    }
> > +
> > +    /// Transmutes a `ListArc` into an [`Arc`] without updating the tracking inside `T`.
> > +    ///
> > +    /// After this call, the tracking inside `T` will still think that there is a `ListArc`
> > +    /// reference.
> > +    #[inline]
> > +    fn transmute_to_arc(self) -> Arc<T> {
>
> Maybe also change this then to be consistent, since the name `transmute`
> carries a "dangerous" feel to it, but this is actually totally safe.

I want it to carry a dangerous feel! Yes, it's safe to leak the
ListArc, but you don't want people to think it's a generic ListArc ->
Arc conversion function.

> > +        // Use a transmute to skip destructor.
> > +        //
> > +        // SAFETY: ListArc is repr(transparent).
> > +        unsafe { core::mem::transmute(self) }
> > +    }
>
> [...]
>
> > +// This is to allow [`ListArc`] (and variants) to be used as the type of `self`.
> > +impl<T, const ID: u64> core::ops::Receiver for ListArc<T, ID> where T: ListArcSafe<ID> + ?Sized {}
> > +
> > +// This is to allow coercion from `ListArc<T>` to `ListArc<U>` if `T` can be converted to the
> > +// dynamically-sized type (DST) `U`.
> > +impl<T, U, const ID: u64> core::ops::CoerceUnsized<ListArc<U, ID>> for ListArc<T, ID>
> > +where
> > +    T: ListArcSafe<ID> + Unsize<U> + ?Sized,
> > +    U: ListArcSafe<ID> + ?Sized,
> > +{
> > +}
> > +
> > +// This is to allow `ListArc<U>` to be dispatched on when `ListArc<T>` can be coerced into
> > +// `ListArc<U>`.
> > +impl<T, U, const ID: u64> core::ops::DispatchFromDyn<ListArc<U, ID>> for ListArc<T, ID>
> > +where
> > +    T: ListArcSafe<ID> + Unsize<U> + ?Sized,
> > +    U: ListArcSafe<ID> + ?Sized,
> > +{
> > +}
>
> Can we start using `feature(derive_smart_pointer)` on new enough
> compiler versions? (I guess you probably want it as a separate patch
> series to avoid delaying this in case it needs anything [eg the new
> build system])
> Do we need any Makefile modifications for that or could we just do
> `#[cfg_attr(compiler-is-new-enough, derive(SmartPointer))` on the struct
> and then cfg these impls away? (and what would "compiler-is-new-enough"
> be?)

That probably won't be until 1.83 or something like that. It will have
to be a follow-up.

> Aside from my docs nits, this looks good:
>
> Reviewed-by: Benno Lossin <benno.lossin@...ton.me>

Thanks!

Alice

Powered by blists - more mailing lists