[PATCH v3 0/2] Arc methods for linked list

[PATCH v3 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.

Link: https://lore.kernel.org/rust-for-linux/20231101-rust-binder-v1-0-08ba9197f637@google.com/ [1]
Signed-off-by: Alice Ryhl <aliceryhl@google.com>
---
Changes in v3:
- No changes to `ArcBorrow::from_raw`, or than adding a Reviewed-by.
- Update SAFETY comment on `refcount_dec_and_test` call.
- Simplify the creation of the `UniqueArc` in `into_unique_or_drop`.
- Link to v2: https://lore.kernel.org/r/20240228-arc-for-list-v2-0-ae93201426b4@google.com

Changes in v2:
- Move raw_to_inner_ptr to ArcInner and rename to container_of.
- Reword safety conditions for raw_to_inner_ptr to match its users.
- Link to v1: https://lore.kernel.org/r/20240219-arc-for-list-v1-0-d98cd92c760b@google.com

---
Alice Ryhl (2):
      rust: sync: add `ArcBorrow::from_raw`
      rust: sync: add `Arc::into_unique_or_drop`

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

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

[PATCH v3 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.

Reviewed-by: Benno Lossin <benno.lossin@proton.me>
Signed-off-by: Alice Ryhl <aliceryhl@google.com>
---
 rust/kernel/sync/arc.rs | 76 +++++++++++++++++++++++++++++++++++++------------
 1 file changed, 58 insertions(+), 18 deletions(-)

diff --git a/rust/kernel/sync/arc.rs b/rust/kernel/sync/arc.rs
index 7d4c4bf58388..53addb8876c2 100644
--- a/rust/kernel/sync/arc.rs
+++ b/rust/kernel/sync/arc.rs
@@ -137,6 +137,39 @@ struct ArcInner<T: ?Sized> {
     data: T,
 }
 
+impl<T: ?Sized> ArcInner<T> {
+    /// Converts a pointer to the contents of an [`Arc`] into a pointer to the [`ArcInner`].
+    ///
+    /// # Safety
+    ///
+    /// `ptr` must have been returned by a previous call to [`Arc::into_raw`], and the `Arc` must
+    /// not yet have been destroyed.
+    unsafe fn container_of(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` on an `Arc` that 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()) }
+    }
+}
+
 // This is to allow [`Arc`] (and variants) to be used as the type of `self`.
 impl<T: ?Sized> core::ops::Receiver for Arc<T> {}
 
@@ -232,27 +265,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 caller promises that this pointer originates from a call to `into_raw` on an
+        // `Arc` that is still valid.
+        let ptr = unsafe { ArcInner::container_of(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`].
@@ -453,6 +472,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 caller promises that this pointer originates from a call to `into_raw` on an
+        // `Arc` that is still valid.
+        let ptr = unsafe { ArcInner::container_of(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.278.ge034bb2e1d-goog

[PATCH v3 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 | 30 ++++++++++++++++++++++++++++++
 1 file changed, 30 insertions(+)

diff --git a/rust/kernel/sync/arc.rs b/rust/kernel/sync/arc.rs
index 53addb8876c2..ef8b520f65a8 100644
--- a/rust/kernel/sync/arc.rs
+++ b/rust/kernel/sync/arc.rs
@@ -290,6 +290,36 @@ 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();
+
+        // 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`.
+        //
+        // SAFETY: We own a refcount, so the pointer is not dangling.
+        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)) };
+
+            // INVARIANT: We own the only refcount to this arc, so we may create a `UniqueArc`. We
+            // must pin the `UniqueArc` because the values was previously in an `Arc`, and they pin
+            // their values.
+            Some(Pin::from(UniqueArc { inner: ManuallyDrop::into_inner(me) }))
+        } else {
+            None
+        }
+    }
 }
 
 impl<T: 'static> ForeignOwnable for Arc<T> {

-- 
2.44.0.278.ge034bb2e1d-goog

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

[Benno Lossin]

On 3/11/24 17:08, Alice Ryhl wrote:
> 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>

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

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

[Boqun Feng]

On Mon, Mar 11, 2024 at 04:08:19PM +0000, Alice Ryhl wrote:
> 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 | 30 ++++++++++++++++++++++++++++++
>  1 file changed, 30 insertions(+)
> 
> diff --git a/rust/kernel/sync/arc.rs b/rust/kernel/sync/arc.rs
> index 53addb8876c2..ef8b520f65a8 100644
> --- a/rust/kernel/sync/arc.rs
> +++ b/rust/kernel/sync/arc.rs
> @@ -290,6 +290,36 @@ 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();
> +
> +        // 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`.
> +        //
> +        // SAFETY: We own a refcount, so the pointer is not dangling.
> +        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)) };
> +
> +            // INVARIANT: We own the only refcount to this arc, so we may create a `UniqueArc`. We
> +            // must pin the `UniqueArc` because the values was previously in an `Arc`, and they pin
> +            // their values.
> +            Some(Pin::from(UniqueArc { inner: ManuallyDrop::into_inner(me) }))
> +        } else {
> +            None
> +        }
> +    }
>  }
>  
>  impl<T: 'static> ForeignOwnable for Arc<T> {
> 

The code looks good, and FWIW, I added the Examples section for the
function since I at least need something to run when queuing it to
rust-dev branch ;-) And I think it's overall good to have examples for
every `pub` function. If there is a next version (which is unlikely),
feel free to fold it. I can also send it alone once Miguel put your
patches into the rust-next branch.

Regards,
Boqun

--------------------------------------------------->8
From 7d26d1177a2788ba96c607fd9dc45baf469fb439 Mon Sep 17 00:00:00 2001
From: Boqun Feng <boqun.feng@gmail.com>
Date: Tue, 12 Mar 2024 10:03:39 -0700
Subject: [PATCH] kernel: sync: Add "Examples" section for
 Arc::into_unique_or_drop()

These examples provide better documentation and can serve as unit tests
as well, so add them.

Signed-off-by: Boqun Feng <boqun.feng@gmail.com>
---
 rust/kernel/sync/arc.rs | 30 ++++++++++++++++++++++++++++++
 1 file changed, 30 insertions(+)

diff --git a/rust/kernel/sync/arc.rs b/rust/kernel/sync/arc.rs
index fda737f5b1e9..7cf066cfb321 100644
--- a/rust/kernel/sync/arc.rs
+++ b/rust/kernel/sync/arc.rs
@@ -295,6 +295,36 @@ pub fn ptr_eq(this: &Self, other: &Self) -> bool {
     ///
     /// 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.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// use kernel::sync::{Arc, UniqueArc};
+    ///
+    /// let arc = Arc::try_new(42)?;
+    /// let unique_arc = arc.into_unique_or_drop();
+    ///
+    /// // The above conversion should succeed since refcount of `arc` is 1.
+    /// assert!(unique_arc.is_some());
+    ///
+    /// assert_eq!(*(unique_arc.unwrap()), 42);
+    ///
+    /// # Ok::<(), Error>(())
+    /// ```
+    ///
+    /// ```
+    /// use kernel::sync::{Arc, UniqueArc};
+    ///
+    /// let arc = Arc::try_new(42)?;
+    /// let another = arc.clone();
+    ///
+    /// let unique_arc = arc.into_unique_or_drop();
+    ///
+    /// // The above conversion should fail since refcount of `arc` is >1.
+    /// assert!(unique_arc.is_none());
+    ///
+    /// # Ok::<(), Error>(())
+    /// ```
     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);
-- 
2.44.0

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

[Alice Ryhl]

Boqun Feng <boqun.feng@gmail.com> writes:
> The code looks good, and FWIW, I added the Examples section for the
> function since I at least need something to run when queuing it to
> rust-dev branch ;-) And I think it's overall good to have examples for
> every `pub` function. If there is a next version (which is unlikely),
> feel free to fold it. I can also send it alone once Miguel put your
> patches into the rust-next branch.

Thanks! If you have reviewed it, could I have your Reviewed-by tag?

> From 7d26d1177a2788ba96c607fd9dc45baf469fb439 Mon Sep 17 00:00:00 2001
> From: Boqun Feng <boqun.feng@gmail.com>
> Date: Tue, 12 Mar 2024 10:03:39 -0700
> Subject: [PATCH] kernel: sync: Add "Examples" section for
>  Arc::into_unique_or_drop()
> 
> These examples provide better documentation and can serve as unit tests
> as well, so add them.
> 
> Signed-off-by: Boqun Feng <boqun.feng@gmail.com>

Reviewed-by: Alice Ryhl <aliceryhl@google.com>

Alice

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

[Boqun Feng]

On Wed, Mar 13, 2024 at 09:50:59AM +0000, Alice Ryhl wrote:
> Boqun Feng <boqun.feng@gmail.com> writes:
> > The code looks good, and FWIW, I added the Examples section for the
> > function since I at least need something to run when queuing it to
> > rust-dev branch ;-) And I think it's overall good to have examples for
> > every `pub` function. If there is a next version (which is unlikely),
> > feel free to fold it. I can also send it alone once Miguel put your
> > patches into the rust-next branch.
> 
> Thanks! If you have reviewed it, could I have your Reviewed-by tag?
> 

Done.

> > From 7d26d1177a2788ba96c607fd9dc45baf469fb439 Mon Sep 17 00:00:00 2001
> > From: Boqun Feng <boqun.feng@gmail.com>
> > Date: Tue, 12 Mar 2024 10:03:39 -0700
> > Subject: [PATCH] kernel: sync: Add "Examples" section for
> >  Arc::into_unique_or_drop()
> > 
> > These examples provide better documentation and can serve as unit tests
> > as well, so add them.
> > 
> > Signed-off-by: Boqun Feng <boqun.feng@gmail.com>
> 
> Reviewed-by: Alice Ryhl <aliceryhl@google.com>
> 

Thanks! I will add it.

Regards,
Boqun

> Alice

Re: [PATCH v3 0/2] Arc methods for linked list

[Boqun Feng]

On Mon, Mar 11, 2024 at 04:08:17PM +0000, Alice Ryhl wrote:
> 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.
> 

For the whole series:

Reviewed-by: Boqun Feng <boqun.feng@gmail.com>

Note there's a nit for rustfmt fix of patch #2 (which is reported by
Miguel):

diff --git a/rust/kernel/sync/arc.rs b/rust/kernel/sync/arc.rs
index 7cf066cfb321..c9773d0050c2 100644
--- a/rust/kernel/sync/arc.rs
+++ b/rust/kernel/sync/arc.rs
@@ -345,7 +345,9 @@ pub fn into_unique_or_drop(self) -> Option<Pin<UniqueArc<T>>> {
             // INVARIANT: We own the only refcount to this arc, so we may create a `UniqueArc`. We
             // must pin the `UniqueArc` because the values was previously in an `Arc`, and they pin
             // their values.
-            Some(Pin::from(UniqueArc { inner: ManuallyDrop::into_inner(me) }))
+            Some(Pin::from(UniqueArc {
+                inner: ManuallyDrop::into_inner(me),
+            }))
         } else {
             None
         }

Regards,
Boqun

> Link: https://lore.kernel.org/rust-for-linux/20231101-rust-binder-v1-0-08ba9197f637@google.com/ [1]
> Signed-off-by: Alice Ryhl <aliceryhl@google.com>
> ---
> Changes in v3:
> - No changes to `ArcBorrow::from_raw`, or than adding a Reviewed-by.
> - Update SAFETY comment on `refcount_dec_and_test` call.
> - Simplify the creation of the `UniqueArc` in `into_unique_or_drop`.
> - Link to v2: https://lore.kernel.org/r/20240228-arc-for-list-v2-0-ae93201426b4@google.com
> 
> Changes in v2:
> - Move raw_to_inner_ptr to ArcInner and rename to container_of.
> - Reword safety conditions for raw_to_inner_ptr to match its users.
> - Link to v1: https://lore.kernel.org/r/20240219-arc-for-list-v1-0-d98cd92c760b@google.com
> 
> ---
> Alice Ryhl (2):
>       rust: sync: add `ArcBorrow::from_raw`
>       rust: sync: add `Arc::into_unique_or_drop`
> 
>  rust/kernel/sync/arc.rs | 106 ++++++++++++++++++++++++++++++++++++++++--------
>  1 file changed, 88 insertions(+), 18 deletions(-)
> ---
> base-commit: 768409cff6cc89fe1194da880537a09857b6e4db
> change-id: 20240209-arc-for-list-a2c126c2ad5c
> 
> Best regards,
> -- 
> Alice Ryhl <aliceryhl@google.com>
>