[PATCH 0/2] Arc methods for linked list

[PATCH 0/2] Arc methods for linked list

[Alice Ryhl]

This patchset contains two useful methods for the Arc type. They will be
used in my Rust linked list implementation, which Rust Binder uses. See
the Rust Binder RFC [1] for more information. Both these commits and
the linked list that uses them are present in the branch referenced by
the RFC.

I will send the linked list to the mailing list soon.

This patchset is based on rust-next and depends on [2].

Link: https://lore.kernel.org/rust-for-linux/20231101-rust-binder-v1-0-08ba9197f637@google.com/ [1]
Link: https://lore.kernel.org/all/20240215104601.1267763-1-aliceryhl@google.com/ [2]
Signed-off-by: Alice Ryhl <aliceryhl@google.com>
---
Alice Ryhl (2):
      rust: sync: add `ArcBorrow::from_raw`
      rust: sync: add `Arc::into_unique_or_drop`

 rust/kernel/sync/arc.rs | 103 +++++++++++++++++++++++++++++++++++++++---------
 1 file changed, 85 insertions(+), 18 deletions(-)
---
base-commit: e3c3d34507c7a146de1c5ce01bd0b2c0018b2609
change-id: 20240209-arc-for-list-a2c126c2ad5c

Best regards,
-- 
Alice Ryhl <aliceryhl@google.com>

[PATCH 1/2] rust: sync: add `ArcBorrow::from_raw`

[Alice Ryhl]

Allows access to a value in an `Arc` that is currently held as a raw
pointer due to use of `Arc::into_raw`, without destroying or otherwise
consuming that raw pointer.

This is a dependency of the linked list that Rust Binder uses. The
linked list uses this method when iterating over the linked list.

Signed-off-by: Alice Ryhl <aliceryhl@google.com>
---
 rust/kernel/sync/arc.rs | 72 ++++++++++++++++++++++++++++++++++++-------------
 1 file changed, 54 insertions(+), 18 deletions(-)

diff --git a/rust/kernel/sync/arc.rs b/rust/kernel/sync/arc.rs
index 7d4c4bf58388..a5314df409e7 100644
--- a/rust/kernel/sync/arc.rs
+++ b/rust/kernel/sync/arc.rs
@@ -232,27 +232,13 @@ pub fn into_raw(self) -> *const T {
     /// `ptr` must have been returned by a previous call to [`Arc::into_raw`]. Additionally, it
     /// must not be called more than once for each previous call to [`Arc::into_raw`].
     pub unsafe fn from_raw(ptr: *const T) -> Self {
-        let refcount_layout = Layout::new::<bindings::refcount_t>();
-        // SAFETY: The caller guarantees that the pointer is valid.
-        let val_layout = Layout::for_value(unsafe { &*ptr });
-        // SAFETY: We're computing the layout of a real struct that existed when compiling this
-        // binary, so its layout is not so large that it can trigger arithmetic overflow.
-        let val_offset = unsafe { refcount_layout.extend(val_layout).unwrap_unchecked().1 };
-
-        // Pointer casts leave the metadata unchanged. This is okay because the metadata of `T` and
-        // `ArcInner<T>` is the same since `ArcInner` is a struct with `T` as its last field.
-        //
-        // This is documented at:
-        // <https://doc.rust-lang.org/std/ptr/trait.Pointee.html>.
-        let ptr = ptr as *const ArcInner<T>;
-
-        // SAFETY: The pointer is in-bounds of an allocation both before and after offsetting the
-        // pointer, since it originates from a previous call to `Arc::into_raw` and is still valid.
-        let ptr = unsafe { ptr.byte_sub(val_offset) };
+        // SAFETY: The pointer returned by `into_raw` points at the `data` field of an
+        // `ArcInner<T>`, as promised by the caller.
+        let ptr = unsafe { raw_to_inner_ptr(ptr) };
 
         // SAFETY: By the safety requirements we know that `ptr` came from `Arc::into_raw`, so the
         // reference count held then will be owned by the new `Arc` object.
-        unsafe { Self::from_inner(NonNull::new_unchecked(ptr.cast_mut())) }
+        unsafe { Self::from_inner(ptr) }
     }
 
     /// Returns an [`ArcBorrow`] from the given [`Arc`].
@@ -273,6 +259,35 @@ pub fn ptr_eq(this: &Self, other: &Self) -> bool {
     }
 }
 
+/// Converts a pointer to the contents of an [`Arc`] into a pointer to the [`ArcInner`].
+///
+/// # Safety
+///
+/// The provided pointer must point the `data` field of an `ArcInner<T>` value.
+unsafe fn raw_to_inner_ptr<T: ?Sized>(ptr: *const T) -> NonNull<ArcInner<T>> {
+    let refcount_layout = Layout::new::<bindings::refcount_t>();
+    // SAFETY: The caller guarantees that the pointer is valid.
+    let val_layout = Layout::for_value(unsafe { &*ptr });
+    // SAFETY: We're computing the layout of a real struct that existed when compiling this
+    // binary, so its layout is not so large that it can trigger arithmetic overflow.
+    let val_offset = unsafe { refcount_layout.extend(val_layout).unwrap_unchecked().1 };
+
+    // Pointer casts leave the metadata unchanged. This is okay because the metadata of `T` and
+    // `ArcInner<T>` is the same since `ArcInner` is a struct with `T` as its last field.
+    //
+    // This is documented at:
+    // <https://doc.rust-lang.org/std/ptr/trait.Pointee.html>.
+    let ptr = ptr as *const ArcInner<T>;
+
+    // SAFETY: The pointer is in-bounds of an allocation both before and after offsetting the
+    // pointer, since it originates from a previous call to `Arc::into_raw` and is still valid.
+    let ptr = unsafe { ptr.byte_sub(val_offset) };
+
+    // SAFETY: The pointer can't be null since you can't have an `ArcInner<T>` value at the null
+    // address.
+    unsafe { NonNull::new_unchecked(ptr.cast_mut()) }
+}
+
 impl<T: 'static> ForeignOwnable for Arc<T> {
     type Borrowed<'a> = ArcBorrow<'a, T>;
 
@@ -453,6 +468,27 @@ unsafe fn new(inner: NonNull<ArcInner<T>>) -> Self {
             _p: PhantomData,
         }
     }
+
+    /// Creates an [`ArcBorrow`] to an [`Arc`] that has previously been deconstructed with
+    /// [`Arc::into_raw`].
+    ///
+    /// # Safety
+    ///
+    /// * The provided pointer must originate from a call to [`Arc::into_raw`].
+    /// * For the duration of the lifetime annotated on this `ArcBorrow`, the reference count must
+    ///   not hit zero.
+    /// * For the duration of the lifetime annotated on this `ArcBorrow`, there must not be a
+    ///   [`UniqueArc`] reference to this value.
+    pub unsafe fn from_raw(ptr: *const T) -> Self {
+        // SAFETY: The pointer returned by `into_raw` points at the `data` field of an
+        // `ArcInner<T>`.
+        let ptr = unsafe { raw_to_inner_ptr(ptr) };
+
+        // SAFETY: The caller promises that the value remains valid since the reference count must
+        // not hit zero, and no mutable reference will be created since that would involve a
+        // `UniqueArc`.
+        unsafe { Self::new(ptr) }
+    }
 }
 
 impl<T: ?Sized> From<ArcBorrow<'_, T>> for Arc<T> {

-- 
2.44.0.rc0.258.g7320e95886-goog

Re: [PATCH 1/2] rust: sync: add `ArcBorrow::from_raw`

[Boqun Feng]

On Mon, Feb 19, 2024 at 02:54:11PM +0000, Alice Ryhl wrote:
> Allows access to a value in an `Arc` that is currently held as a raw
> pointer due to use of `Arc::into_raw`, without destroying or otherwise
> consuming that raw pointer.
> 
> This is a dependency of the linked list that Rust Binder uses. The
> linked list uses this method when iterating over the linked list.
> 
> Signed-off-by: Alice Ryhl <aliceryhl@google.com>
> ---
>  rust/kernel/sync/arc.rs | 72 ++++++++++++++++++++++++++++++++++++-------------
>  1 file changed, 54 insertions(+), 18 deletions(-)
> 
> diff --git a/rust/kernel/sync/arc.rs b/rust/kernel/sync/arc.rs
> index 7d4c4bf58388..a5314df409e7 100644
> --- a/rust/kernel/sync/arc.rs
> +++ b/rust/kernel/sync/arc.rs
> @@ -232,27 +232,13 @@ pub fn into_raw(self) -> *const T {
>      /// `ptr` must have been returned by a previous call to [`Arc::into_raw`]. Additionally, it
>      /// must not be called more than once for each previous call to [`Arc::into_raw`].
>      pub unsafe fn from_raw(ptr: *const T) -> Self {
> -        let refcount_layout = Layout::new::<bindings::refcount_t>();
> -        // SAFETY: The caller guarantees that the pointer is valid.
> -        let val_layout = Layout::for_value(unsafe { &*ptr });
> -        // SAFETY: We're computing the layout of a real struct that existed when compiling this
> -        // binary, so its layout is not so large that it can trigger arithmetic overflow.
> -        let val_offset = unsafe { refcount_layout.extend(val_layout).unwrap_unchecked().1 };
> -
> -        // Pointer casts leave the metadata unchanged. This is okay because the metadata of `T` and
> -        // `ArcInner<T>` is the same since `ArcInner` is a struct with `T` as its last field.
> -        //
> -        // This is documented at:
> -        // <https://doc.rust-lang.org/std/ptr/trait.Pointee.html>.
> -        let ptr = ptr as *const ArcInner<T>;
> -
> -        // SAFETY: The pointer is in-bounds of an allocation both before and after offsetting the
> -        // pointer, since it originates from a previous call to `Arc::into_raw` and is still valid.
> -        let ptr = unsafe { ptr.byte_sub(val_offset) };
> +        // SAFETY: The pointer returned by `into_raw` points at the `data` field of an
> +        // `ArcInner<T>`, as promised by the caller.
> +        let ptr = unsafe { raw_to_inner_ptr(ptr) };
>  
>          // SAFETY: By the safety requirements we know that `ptr` came from `Arc::into_raw`, so the
>          // reference count held then will be owned by the new `Arc` object.
> -        unsafe { Self::from_inner(NonNull::new_unchecked(ptr.cast_mut())) }
> +        unsafe { Self::from_inner(ptr) }
>      }
>  
>      /// Returns an [`ArcBorrow`] from the given [`Arc`].
> @@ -273,6 +259,35 @@ pub fn ptr_eq(this: &Self, other: &Self) -> bool {
>      }
>  }
>  
> +/// Converts a pointer to the contents of an [`Arc`] into a pointer to the [`ArcInner`].
> +///
> +/// # Safety
> +///
> +/// The provided pointer must point the `data` field of an `ArcInner<T>` value.
> +unsafe fn raw_to_inner_ptr<T: ?Sized>(ptr: *const T) -> NonNull<ArcInner<T>> {

Nit: put this into an `impl<T:?Sized> ArcInner<T>` block maybe?

> +    let refcount_layout = Layout::new::<bindings::refcount_t>();
> +    // SAFETY: The caller guarantees that the pointer is valid.
> +    let val_layout = Layout::for_value(unsafe { &*ptr });
> +    // SAFETY: We're computing the layout of a real struct that existed when compiling this
> +    // binary, so its layout is not so large that it can trigger arithmetic overflow.
> +    let val_offset = unsafe { refcount_layout.extend(val_layout).unwrap_unchecked().1 };
> +
> +    // Pointer casts leave the metadata unchanged. This is okay because the metadata of `T` and
> +    // `ArcInner<T>` is the same since `ArcInner` is a struct with `T` as its last field.
> +    //
> +    // This is documented at:
> +    // <https://doc.rust-lang.org/std/ptr/trait.Pointee.html>.
> +    let ptr = ptr as *const ArcInner<T>;
> +
> +    // SAFETY: The pointer is in-bounds of an allocation both before and after offsetting the
> +    // pointer, since it originates from a previous call to `Arc::into_raw` and is still valid.

"since it originate from a previous call to `Arc::into_raw`" is the
safety requirement of `Arc::from_raw`, since the safety requirement of
`raw_to_inner_ptr` is different, so I think we should say "since the
function safety requirement guarantees `ptr` points to `data` field,
which is exactly `val_offset` away from the beginning of `ArcInner<T>`".
Thoughts?

BTW, in fat pointer cases, by "must point the `data` field of an
`ArcInner<T>` value", it means both the address and the metadata should
be the same as the original object in `ArcInner<T>`, right? In other
words, the following code should not be safe, i.e. the
raw_to_inner_ptr() safety requirement is not satisfied.

	let x: Arc<[u8]> // assume x.len() == 4

	let y = &(x[0..1]) as *const [u8] // y has the same address of
					  // the `data` field of `x`.
	
	let inner = unsafe { raw_to_inner_ptr(y) };
	// ^^^ the safety requirement is not satisfied???

This may not be important since the users of `raw_to_inner_ptr` all have
stronger safey guarantees ("`ptr` must come from `Arc::into_raw()`"),
and `raw_to_inner_ptr` is not a pub function, but I just wonder whether
we need to improve the current safety requirements, or "point" means
both address and metadata for fat pointers?

Regards,
Boqun

> +    let ptr = unsafe { ptr.byte_sub(val_offset) };
> +
> +    // SAFETY: The pointer can't be null since you can't have an `ArcInner<T>` value at the null
> +    // address.
> +    unsafe { NonNull::new_unchecked(ptr.cast_mut()) }
> +}
> +
>  impl<T: 'static> ForeignOwnable for Arc<T> {
>      type Borrowed<'a> = ArcBorrow<'a, T>;
>  
> @@ -453,6 +468,27 @@ unsafe fn new(inner: NonNull<ArcInner<T>>) -> Self {
>              _p: PhantomData,
>          }
>      }
> +
> +    /// Creates an [`ArcBorrow`] to an [`Arc`] that has previously been deconstructed with
> +    /// [`Arc::into_raw`].
> +    ///
> +    /// # Safety
> +    ///
> +    /// * The provided pointer must originate from a call to [`Arc::into_raw`].
> +    /// * For the duration of the lifetime annotated on this `ArcBorrow`, the reference count must
> +    ///   not hit zero.
> +    /// * For the duration of the lifetime annotated on this `ArcBorrow`, there must not be a
> +    ///   [`UniqueArc`] reference to this value.
> +    pub unsafe fn from_raw(ptr: *const T) -> Self {
> +        // SAFETY: The pointer returned by `into_raw` points at the `data` field of an
> +        // `ArcInner<T>`.
> +        let ptr = unsafe { raw_to_inner_ptr(ptr) };
> +
> +        // SAFETY: The caller promises that the value remains valid since the reference count must
> +        // not hit zero, and no mutable reference will be created since that would involve a
> +        // `UniqueArc`.
> +        unsafe { Self::new(ptr) }
> +    }
>  }
>  
>  impl<T: ?Sized> From<ArcBorrow<'_, T>> for Arc<T> {
> 
> -- 
> 2.44.0.rc0.258.g7320e95886-goog
> 

Re: [PATCH 1/2] rust: sync: add `ArcBorrow::from_raw`

[Alice Ryhl]

On Tue, Feb 20, 2024 at 6:36 AM Boqun Feng <boqun.feng@gmail.com> wrote:
>
> On Mon, Feb 19, 2024 at 02:54:11PM +0000, Alice Ryhl wrote:
> > Allows access to a value in an `Arc` that is currently held as a raw
> > pointer due to use of `Arc::into_raw`, without destroying or otherwise
> > consuming that raw pointer.
> >
> > This is a dependency of the linked list that Rust Binder uses. The
> > linked list uses this method when iterating over the linked list.
> >
> > Signed-off-by: Alice Ryhl <aliceryhl@google.com>
> > ---
> >  rust/kernel/sync/arc.rs | 72 ++++++++++++++++++++++++++++++++++++-------------
> >  1 file changed, 54 insertions(+), 18 deletions(-)
> >
> > diff --git a/rust/kernel/sync/arc.rs b/rust/kernel/sync/arc.rs
> > index 7d4c4bf58388..a5314df409e7 100644
> > --- a/rust/kernel/sync/arc.rs
> > +++ b/rust/kernel/sync/arc.rs
> > @@ -232,27 +232,13 @@ pub fn into_raw(self) -> *const T {
> >      /// `ptr` must have been returned by a previous call to [`Arc::into_raw`]. Additionally, it
> >      /// must not be called more than once for each previous call to [`Arc::into_raw`].
> >      pub unsafe fn from_raw(ptr: *const T) -> Self {
> > -        let refcount_layout = Layout::new::<bindings::refcount_t>();
> > -        // SAFETY: The caller guarantees that the pointer is valid.
> > -        let val_layout = Layout::for_value(unsafe { &*ptr });
> > -        // SAFETY: We're computing the layout of a real struct that existed when compiling this
> > -        // binary, so its layout is not so large that it can trigger arithmetic overflow.
> > -        let val_offset = unsafe { refcount_layout.extend(val_layout).unwrap_unchecked().1 };
> > -
> > -        // Pointer casts leave the metadata unchanged. This is okay because the metadata of `T` and
> > -        // `ArcInner<T>` is the same since `ArcInner` is a struct with `T` as its last field.
> > -        //
> > -        // This is documented at:
> > -        // <https://doc.rust-lang.org/std/ptr/trait.Pointee.html>.
> > -        let ptr = ptr as *const ArcInner<T>;
> > -
> > -        // SAFETY: The pointer is in-bounds of an allocation both before and after offsetting the
> > -        // pointer, since it originates from a previous call to `Arc::into_raw` and is still valid.
> > -        let ptr = unsafe { ptr.byte_sub(val_offset) };
> > +        // SAFETY: The pointer returned by `into_raw` points at the `data` field of an
> > +        // `ArcInner<T>`, as promised by the caller.
> > +        let ptr = unsafe { raw_to_inner_ptr(ptr) };
> >
> >          // SAFETY: By the safety requirements we know that `ptr` came from `Arc::into_raw`, so the
> >          // reference count held then will be owned by the new `Arc` object.
> > -        unsafe { Self::from_inner(NonNull::new_unchecked(ptr.cast_mut())) }
> > +        unsafe { Self::from_inner(ptr) }
> >      }
> >
> >      /// Returns an [`ArcBorrow`] from the given [`Arc`].
> > @@ -273,6 +259,35 @@ pub fn ptr_eq(this: &Self, other: &Self) -> bool {
> >      }
> >  }
> >
> > +/// Converts a pointer to the contents of an [`Arc`] into a pointer to the [`ArcInner`].
> > +///
> > +/// # Safety
> > +///
> > +/// The provided pointer must point the `data` field of an `ArcInner<T>` value.
> > +unsafe fn raw_to_inner_ptr<T: ?Sized>(ptr: *const T) -> NonNull<ArcInner<T>> {
>
> Nit: put this into an `impl<T:?Sized> ArcInner<T>` block maybe?
>
> > +    let refcount_layout = Layout::new::<bindings::refcount_t>();
> > +    // SAFETY: The caller guarantees that the pointer is valid.
> > +    let val_layout = Layout::for_value(unsafe { &*ptr });
> > +    // SAFETY: We're computing the layout of a real struct that existed when compiling this
> > +    // binary, so its layout is not so large that it can trigger arithmetic overflow.
> > +    let val_offset = unsafe { refcount_layout.extend(val_layout).unwrap_unchecked().1 };
> > +
> > +    // Pointer casts leave the metadata unchanged. This is okay because the metadata of `T` and
> > +    // `ArcInner<T>` is the same since `ArcInner` is a struct with `T` as its last field.
> > +    //
> > +    // This is documented at:
> > +    // <https://doc.rust-lang.org/std/ptr/trait.Pointee.html>.
> > +    let ptr = ptr as *const ArcInner<T>;
> > +
> > +    // SAFETY: The pointer is in-bounds of an allocation both before and after offsetting the
> > +    // pointer, since it originates from a previous call to `Arc::into_raw` and is still valid.
>
> "since it originate from a previous call to `Arc::into_raw`" is the
> safety requirement of `Arc::from_raw`, since the safety requirement of
> `raw_to_inner_ptr` is different, so I think we should say "since the
> function safety requirement guarantees `ptr` points to `data` field,
> which is exactly `val_offset` away from the beginning of `ArcInner<T>`".
> Thoughts?
>
> BTW, in fat pointer cases, by "must point the `data` field of an
> `ArcInner<T>` value", it means both the address and the metadata should
> be the same as the original object in `ArcInner<T>`, right? In other
> words, the following code should not be safe, i.e. the
> raw_to_inner_ptr() safety requirement is not satisfied.
>
>         let x: Arc<[u8]> // assume x.len() == 4
>
>         let y = &(x[0..1]) as *const [u8] // y has the same address of
>                                           // the `data` field of `x`.
>
>         let inner = unsafe { raw_to_inner_ptr(y) };
>         // ^^^ the safety requirement is not satisfied???
>
> This may not be important since the users of `raw_to_inner_ptr` all have
> stronger safey guarantees ("`ptr` must come from `Arc::into_raw()`"),
> and `raw_to_inner_ptr` is not a pub function, but I just wonder whether
> we need to improve the current safety requirements, or "point" means
> both address and metadata for fat pointers?

I mean, really, the same problem arises for Sized pointers where the
pointer points at the first field of a struct.

We may have to take inspiration from the std Arc::from_raw. It says
that the pointee must have the same size and alignment as what was
used when you called Arc::into_raw, and then it further says that if
the pointer type is not exactly the same, then you are effectively
performing a transmute.

Alice

[PATCH 2/2] rust: sync: add `Arc::into_unique_or_drop`

[Alice Ryhl]

Decrement the refcount of an `Arc`, but handle the case where it hits
zero by taking ownership of the now-unique `Arc`, instead of destroying
and deallocating it.

This is a dependency of the linked list that Rust Binder uses. The
linked list uses this method as part of its `ListArc` abstraction.

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

diff --git a/rust/kernel/sync/arc.rs b/rust/kernel/sync/arc.rs
index a5314df409e7..a7e7f7ccace4 100644
--- a/rust/kernel/sync/arc.rs
+++ b/rust/kernel/sync/arc.rs
@@ -257,6 +257,37 @@ pub fn as_arc_borrow(&self) -> ArcBorrow<'_, T> {
     pub fn ptr_eq(this: &Self, other: &Self) -> bool {
         core::ptr::eq(this.ptr.as_ptr(), other.ptr.as_ptr())
     }
+
+    /// Converts this [`Arc`] into a [`UniqueArc`], or destroys it if it is not unique.
+    ///
+    /// When this destroys the `Arc`, it does so while properly avoiding races. This means that
+    /// this method will never call the destructor of the value.
+    pub fn into_unique_or_drop(self) -> Option<Pin<UniqueArc<T>>> {
+        // We will manually manage the refcount in this method, so we disable the destructor.
+        let me = ManuallyDrop::new(self);
+        // SAFETY: We own a refcount, so the pointer is still valid.
+        let refcount = unsafe { me.ptr.as_ref() }.refcount.get();
+
+        // SAFETY: If the refcount reaches a non-zero value, then we have destroyed this `Arc` and
+        // will return without further touching the `Arc`. If the refcount reaches zero, then there
+        // are no other arcs, and we can create a `UniqueArc`.
+        let is_zero = unsafe { bindings::refcount_dec_and_test(refcount) };
+        if is_zero {
+            // SAFETY: We have exclusive access to the arc, so we can perform unsynchronized
+            // accesses to the refcount.
+            unsafe { core::ptr::write(refcount, bindings::REFCOUNT_INIT(1)) };
+
+            // SAFETY: We own one refcount, so we can create a `UniqueArc`. It needs to be pinned,
+            // since an `Arc` is pinned.
+            unsafe {
+                Some(Pin::new_unchecked(UniqueArc {
+                    inner: Arc::from_inner(me.ptr),
+                }))
+            }
+        } else {
+            None
+        }
+    }
 }
 
 /// Converts a pointer to the contents of an [`Arc`] into a pointer to the [`ArcInner`].

-- 
2.44.0.rc0.258.g7320e95886-goog