Re: [PATCH v3 02/10] rust: list: add ListArc

[Benno Lossin]

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.

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

> +///
> +/// 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").

> +#[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`?

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

> +        // 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?)


Aside from my docs nits, this looks good:

Reviewed-by: Benno Lossin <benno.lossin@xxxxxxxxx>

(feel free to discuss any changes, I am not set on the exact phrasing)

---
Cheers,
Benno