rust-for-linux.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
* [PATCH v6] rust: xarray: Add an abstraction for XArray
@ 2024-01-16 15:06 Maíra Canal
  2024-01-16 23:53 ` Boqun Feng
                   ` (2 more replies)
  0 siblings, 3 replies; 7+ messages in thread
From: Maíra Canal @ 2024-01-16 15:06 UTC (permalink / raw)
  To: Asahi Lina, Miguel Ojeda, Alex Gaynor, Wedson Almeida Filho,
	Boqun Feng, Gary Guo, Björn Roy Baron, Benno Lossin,
	Andreas Hindborg, Alice Ryhl, Matthew Wilcox
  Cc: rust-for-linux, kernel-dev, Maíra Canal

From: Asahi Lina <lina@asahilina.net>

The XArray is an abstract data type which behaves like a very large
array of pointers. Add a Rust abstraction for this data type.

The initial implementation uses explicit locking on get operations and
returns a guard which blocks mutation, ensuring that the referenced
object remains alive. To avoid excessive serialization, users are
expected to use an inner type that can be efficiently cloned (such as
Arc<T>), and eagerly clone and drop the guard to unblock other users
after a lookup.

Future variants may support using RCU instead to avoid mutex locking.

This abstraction also introduces a reservation mechanism, which can be
used by alloc-capable XArrays to reserve a free slot without immediately
filling it, and then do so at a later time. If the reservation is
dropped without being filled, the slot is freed again for other users,
which eliminates the need for explicit cleanup code.

Signed-off-by: Asahi Lina <lina@asahilina.net>
Co-developed-by: Maíra Canal <mcanal@igalia.com>
Signed-off-by: Maíra Canal <mcanal@igalia.com>
---

This abstraction is part of the set of dependencies I need to upstream
rustgem, a virtual GEM provider driver in the DRM [1]. Also, this
abstraction will be useful for the upstreaming process of the drm/asahi
driver.

Best Regards,
- Maíra

Changelog
=========

v1 -> v2: https://lore.kernel.org/r/20230224-rust-xarray-v1-1-80f0904ce5d3@asahilina.net

- Added Pin requirement for all XArray operations, to close a
  soundness hole due to the lock in the XArray (locks are not safe to
  move while locked). Creation does not require pinning in place, since
  the lock cannot be acquired at that point.
- Added safety note to Drop impl about why we don't need to do the lock
  unlock dance to ensure soundness in case of a dropped lock guard.
- Downstream drm/asahi driver was also rebased on this version to prove
  it works (previously it was still on a pre-v1 version).
- This still depends on the Error series (v1). v2 of that will need a
  trivial rename of Error::from_kernel_errno -> Error::from_errno. If
  this version of XArray ends up looking good, I'll send a trivial v4 of
  XArray with the rename, after sending the v2 of the Error series.

v2 -> v3: https://lore.kernel.org/r/20230224-rust-xarray-v2-1-4eeb0134944c@asahilina.net

- Updated to the error v2/v3 series API.
- Renamed `err` to `ret` for consistency with the other instance.

v3 -> v4: https://lore.kernel.org/rust-for-linux/20230224-rust-xarray-v3-1-04305b1173a5@asahilina.net/

- Rebase on top of rust-next.

v4 -> v5: https://lore.kernel.org/rust-for-linux/20231126131210.1384490-1-mcanal@igalia.com/T/

- Use Gary's suggestion for the Deref trait - no unsafe code! (Benno Lossin)
- Use NonNull (Benno Lossin)
- Not spelling out the lifetimes (Benno Lossin)
- Change XArray invariants (Benno Lossin)
- Add all SAFETY comments (Benno Lossin)
- Use `kernel::error::to_result` (Benno Lossin)
- s/alloc_limits/alloc_limits_opt (Benno Lossin)
- Split unsafe block (Benno Lossin)
- Make error handling of the function `alloc_limits_opt` through `ScopeGuard` (Benno Lossin)
- Use `ScopeGuard` in the function `get` (Benno Lossin)

v5 -> v6: https://lore.kernel.org/rust-for-linux/20231201195300.1329092-1-mcanal@igalia.com/T/

- Update constants to the new format (RUST_CONST_HELPER)
- Add invariant for `self.0` being a pointer derived from `T::from_foreign` (Benno Lossin)
- Fix the place of the INVARIANT comments (Benno Lossin)
- Use the Pin-Init API (Benno Lossin)
- Remove PhantomPinned from XArray (Benno Lossin)
- Add new requirements for calling `xa_unlock()` (Benno Lossin)
- Improve SAFETY comments (Benno Lossin)
- Split unsafe block (Benno Lossin)
- s/alloc_limits_opt/insert_between (Benno Lossin)
- Specify the target type of the cast (Andreas Hindborg/Trevor Gross)
- Guarantee that T is 4-byte aligned (Andreas Hindborg)
- Add code examples in the code (Boqun Feng)

[1] https://github.com/mairacanal/linux/pull/11

 rust/bindings/bindings_helper.h |  17 ++
 rust/helpers.c                  |  37 +++
 rust/kernel/lib.rs              |   1 +
 rust/kernel/xarray.rs           | 383 ++++++++++++++++++++++++++++++++
 4 files changed, 438 insertions(+)
 create mode 100644 rust/kernel/xarray.rs

diff --git a/rust/bindings/bindings_helper.h b/rust/bindings/bindings_helper.h
index b5714fb69fe3..e8e8187580fc 100644
--- a/rust/bindings/bindings_helper.h
+++ b/rust/bindings/bindings_helper.h
@@ -13,8 +13,25 @@
 #include <linux/wait.h>
 #include <linux/sched.h>
 #include <linux/workqueue.h>
+#include <linux/xarray.h>

 /* `bindgen` gets confused at certain things. */
 const size_t RUST_CONST_HELPER_ARCH_SLAB_MINALIGN = ARCH_SLAB_MINALIGN;
 const gfp_t RUST_CONST_HELPER_GFP_KERNEL = GFP_KERNEL;
 const gfp_t RUST_CONST_HELPER___GFP_ZERO = __GFP_ZERO;
+
+const gfp_t RUST_CONST_HELPER_XA_FLAGS_LOCK_IRQ = XA_FLAGS_LOCK_IRQ;
+const gfp_t RUST_CONST_HELPER_XA_FLAGS_LOCK_BH = XA_FLAGS_LOCK_BH;
+const gfp_t RUST_CONST_HELPER_XA_FLAGS_TRACK_FREE = XA_FLAGS_TRACK_FREE;
+const gfp_t RUST_CONST_HELPER_XA_FLAGS_ZERO_BUSY = XA_FLAGS_ZERO_BUSY;
+const gfp_t RUST_CONST_HELPER_XA_FLAGS_ALLOC_WRAPPED = XA_FLAGS_ALLOC_WRAPPED;
+const gfp_t RUST_CONST_HELPER_XA_FLAGS_ACCOUNT = XA_FLAGS_ACCOUNT;
+const gfp_t RUST_CONST_HELPER_XA_FLAGS_ALLOC = XA_FLAGS_ALLOC;
+const gfp_t RUST_CONST_HELPER_XA_FLAGS_ALLOC1 = XA_FLAGS_ALLOC1;
+
+const xa_mark_t RUST_CONST_HELPER_XA_MARK_0 = XA_MARK_0;
+const xa_mark_t RUST_CONST_HELPER_XA_MARK_1 = XA_MARK_1;
+const xa_mark_t RUST_CONST_HELPER_XA_MARK_2 = XA_MARK_2;
+const xa_mark_t RUST_CONST_HELPER_XA_PRESENT = XA_PRESENT;
+const xa_mark_t RUST_CONST_HELPER_XA_MARK_MAX = XA_MARK_MAX;
+const xa_mark_t RUST_CONST_HELPER_XA_FREE_MARK = XA_FREE_MARK;
diff --git a/rust/helpers.c b/rust/helpers.c
index 70e59efd92bc..72a7f9c596ad 100644
--- a/rust/helpers.c
+++ b/rust/helpers.c
@@ -31,6 +31,7 @@
 #include <linux/spinlock.h>
 #include <linux/wait.h>
 #include <linux/workqueue.h>
+#include <linux/xarray.h>

 __noreturn void rust_helper_BUG(void)
 {
@@ -157,6 +158,42 @@ void rust_helper_init_work_with_key(struct work_struct *work, work_func_t func,
 }
 EXPORT_SYMBOL_GPL(rust_helper_init_work_with_key);

+void rust_helper_xa_init_flags(struct xarray *xa, gfp_t flags)
+{
+	xa_init_flags(xa, flags);
+}
+EXPORT_SYMBOL_GPL(rust_helper_xa_init_flags);
+
+bool rust_helper_xa_empty(struct xarray *xa)
+{
+	return xa_empty(xa);
+}
+EXPORT_SYMBOL_GPL(rust_helper_xa_empty);
+
+int rust_helper_xa_alloc(struct xarray *xa, u32 *id, void *entry, struct xa_limit limit, gfp_t gfp)
+{
+	return xa_alloc(xa, id, entry, limit, gfp);
+}
+EXPORT_SYMBOL_GPL(rust_helper_xa_alloc);
+
+void rust_helper_xa_lock(struct xarray *xa)
+{
+	xa_lock(xa);
+}
+EXPORT_SYMBOL_GPL(rust_helper_xa_lock);
+
+void rust_helper_xa_unlock(struct xarray *xa)
+{
+	xa_unlock(xa);
+}
+EXPORT_SYMBOL_GPL(rust_helper_xa_unlock);
+
+int rust_helper_xa_err(void *entry)
+{
+	return xa_err(entry);
+}
+EXPORT_SYMBOL_GPL(rust_helper_xa_err);
+
 /*
  * `bindgen` binds the C `size_t` type as the Rust `usize` type, so we can
  * use it in contexts where Rust expects a `usize` like slice (array) indices.
diff --git a/rust/kernel/lib.rs b/rust/kernel/lib.rs
index e6aff80b521f..1a4372a4e85c 100644
--- a/rust/kernel/lib.rs
+++ b/rust/kernel/lib.rs
@@ -48,6 +48,7 @@
 pub mod task;
 pub mod types;
 pub mod workqueue;
+pub mod xarray;

 #[doc(hidden)]
 pub use bindings;
diff --git a/rust/kernel/xarray.rs b/rust/kernel/xarray.rs
new file mode 100644
index 000000000000..fd2ea8b1a307
--- /dev/null
+++ b/rust/kernel/xarray.rs
@@ -0,0 +1,383 @@
+// SPDX-License-Identifier: GPL-2.0
+
+//! XArray abstraction.
+//!
+//! C header: [`include/linux/xarray.h`](../../include/linux/xarray.h)
+
+use crate::{
+    bindings,
+    error::{to_result, Error, Result},
+    prelude::*,
+    types::{ForeignOwnable, Opaque, ScopeGuard},
+};
+use core::{marker::PhantomData, mem, ops::Deref, ptr::NonNull};
+
+/// Flags passed to `XArray::new` to configure the `XArray`.
+type Flags = bindings::gfp_t;
+
+/// Flag values passed to `XArray::new` to configure the `XArray`.
+pub mod flags {
+    /// Use IRQ-safe locking.
+    pub const LOCK_IRQ: super::Flags = bindings::XA_FLAGS_LOCK_IRQ;
+    /// Use softirq-safe locking.
+    pub const LOCK_BH: super::Flags = bindings::XA_FLAGS_LOCK_BH;
+    /// Track which entries are free (distinct from None).
+    pub const TRACK_FREE: super::Flags = bindings::XA_FLAGS_TRACK_FREE;
+    /// Initialize array index 0 as busy.
+    pub const ZERO_BUSY: super::Flags = bindings::XA_FLAGS_ZERO_BUSY;
+    /// Use GFP_ACCOUNT for internal memory allocations.
+    pub const ACCOUNT: super::Flags = bindings::XA_FLAGS_ACCOUNT;
+    /// Create an allocating `XArray` starting at index 0.
+    pub const ALLOC: super::Flags = bindings::XA_FLAGS_ALLOC;
+    /// Create an allocating `XArray` starting at index 1.
+    pub const ALLOC1: super::Flags = bindings::XA_FLAGS_ALLOC1;
+}
+
+/// Wrapper for a value owned by the `XArray` which holds the `XArray` lock until dropped.
+///
+/// INVARIANT: `Guard` holds a reference (`self.0`) to the underlying value owned by XArray.
+/// You can use the `into_foreign` method to obtain a pointer to the foreign representation
+/// of the owned value, which is valid for the lifetime of the Guard.
+pub struct Guard<'a, T: ForeignOwnable>(NonNull<T>, &'a XArray<T>);
+
+impl<'a, T: ForeignOwnable> Guard<'a, T> {
+    /// Borrow the underlying value wrapped by the `Guard`.
+    ///
+    /// Returns a `T::Borrowed` type for the owned `ForeignOwnable` type.
+    pub fn borrow(&self) -> T::Borrowed<'_> {
+        // SAFETY: The value is owned by the `XArray`, the lifetime it is borrowed for must not
+        // outlive the `XArray` itself, nor the Guard that holds the lock ensuring the value
+        // remains in the `XArray`.
+        //
+        // By the type invariant of `Guard`, we can guarantee that `Guard` holds this reference
+        // (`self.0`).
+        unsafe { T::borrow(self.0.as_ptr().cast()) }
+    }
+}
+
+// Convenience impl for `ForeignOwnable` types whose `Borrowed`
+// form implements Deref.
+impl<'a, T: ForeignOwnable> Deref for Guard<'a, T>
+where
+    T::Borrowed<'a>: Deref,
+    for<'b> T::Borrowed<'b>: Into<&'b <T::Borrowed<'a> as Deref>::Target>,
+{
+    type Target = <T::Borrowed<'a> as Deref>::Target;
+
+    fn deref(&self) -> &Self::Target {
+        self.borrow().into()
+    }
+}
+
+impl<'a, T: ForeignOwnable> Drop for Guard<'a, T> {
+    fn drop(&mut self) {
+        // SAFETY: By the type invariant, we guarantee that we have a reference
+        // that owns the C xarray object.
+        unsafe { bindings::xa_unlock(self.1.xa.get()) };
+    }
+}
+
+/// Represents a reserved slot in an `XArray`, which does not yet have a value but has an assigned
+/// index and may not be allocated by any other user. If the Reservation is dropped without
+/// being filled, the entry is marked as available again.
+///
+/// Users must ensure that reserved slots are not filled by other mechanisms, or otherwise their
+/// contents may be dropped and replaced (which will print a warning).
+pub struct Reservation<'a, T: ForeignOwnable>(&'a XArray<T>, usize, PhantomData<T>);
+
+impl<'a, T: ForeignOwnable> Reservation<'a, T> {
+    /// Stores a value into the reserved slot.
+    pub fn store(self, value: T) -> Result<usize> {
+        if self.0.replace(self.1, value)?.is_some() {
+            crate::pr_err!("XArray: Reservation stored but the entry already had data!\n");
+            // Consider it a success anyway, not much we can do
+        }
+        let index = self.1;
+        // The reservation is now fulfilled, so do not run our destructor.
+        core::mem::forget(self);
+        Ok(index)
+    }
+
+    /// Returns the index of this reservation.
+    pub fn index(&self) -> usize {
+        self.1
+    }
+}
+
+impl<'a, T: ForeignOwnable> Drop for Reservation<'a, T> {
+    fn drop(&mut self) {
+        if self.0.remove(self.1).is_some() {
+            crate::pr_err!("XArray: Reservation dropped but the entry was not empty!\n");
+        }
+    }
+}
+
+/// An array which efficiently maps sparse integer indices to owned objects.
+///
+/// This is similar to a `Vec<Option<T>>`, but more efficient when there are holes in the
+/// index space, and can be efficiently grown.
+///
+/// This structure is expected to often be used with an inner type that
+/// can be efficiently cloned, such as an `Arc<T>`.
+///
+/// INVARIANT: All pointers stored in the array are pointers obtained by
+/// calling `T::into_foreign`.
+#[pin_data(PinnedDrop)]
+pub struct XArray<T: ForeignOwnable> {
+    #[pin]
+    xa: Opaque<bindings::xarray>,
+    _p: PhantomData<T>,
+}
+
+///
+/// # Examples
+///
+/// ```rust
+/// # use kernel::xarray;
+/// # use kernel::prelude::*;
+/// # use kernel::sync::Arc;
+///
+/// # struct Foo {
+/// #     a: u32,
+/// #     b: u32,
+/// # }
+///
+/// let arr = Box::pin_init(xarray::XArray::<Arc<Foo>>::new(xarray::flags::ALLOC1))
+///                                                    .expect("Unable to allocate XArray");
+///
+/// let foo = Arc::try_new(Foo { a : 1, b: 2 }).expect("Unable to allocate Foo");
+/// let index = arr.alloc(foo).expect("Error allocating Index");
+///
+/// if let Some(guard) = arr.get(index) {
+///     assert_eq!(guard.borrow().a, 1);
+///     assert_eq!(guard.borrow().b, 2);
+/// } else {
+///     pr_info!("No value found in index {}", index);
+/// }
+///
+/// let foo = Arc::try_new(Foo { a : 3, b: 4 }).expect("Unable to allocate Foo");
+/// let index = arr.alloc(foo).expect("Error allocating Index");
+///
+/// if let Some(removed_data) = arr.remove(index) {
+///     assert_eq!(removed_data.a, 3);
+///     assert_eq!(removed_data.b, 4);
+/// } else {
+///     pr_info!("No value found in index {}", index);
+/// }
+/// ```
+impl<T: ForeignOwnable> XArray<T> {
+    /// Creates a new `XArray` with the given flags.
+    pub fn new(flags: Flags) -> impl PinInit<Self> {
+        pin_init!(Self {
+            // SAFETY: `xa` is valid while the closure is called.
+            xa <- Opaque::ffi_init(|xa| unsafe {
+                bindings::xa_init_flags(xa, flags)
+            }),
+            _p: PhantomData,
+        })
+    }
+
+    /// Replaces an entry with a new value, returning the old value (if any).
+    pub fn replace(&self, index: usize, value: T) -> Result<Option<T>> {
+        let new = value.into_foreign();
+
+        build_assert!(mem::align_of::<T>() <= 4);
+
+        // SAFETY: `new` just came from into_foreign(), and we dismiss this guard if
+        // the xa_store operation succeeds and takes ownership of the pointer.
+        let guard = ScopeGuard::new(|| unsafe {
+            T::from_foreign(new);
+        });
+
+        // SAFETY: `self.xa` is always valid by the type invariant, and we are storing
+        // a `T::into_foreign()` result which upholds the later invariants.
+        let old = unsafe {
+            bindings::xa_store(
+                self.xa.get(),
+                index.try_into()?,
+                new.cast_mut(),
+                bindings::GFP_KERNEL,
+            )
+        };
+
+        // SAFETY: `xa_store` returns the old entry at this index on success or
+        // a XArray result, which can be turn into an errno through `xa_err`.
+        to_result(unsafe { bindings::xa_err(old) })?;
+        guard.dismiss();
+
+        Ok(if old.is_null() {
+            None
+        } else {
+            // SAFETY: The old value must have been stored by either this function or
+            // `insert_between`, both of which ensure non-NULL entries are valid
+            // ForeignOwnable pointers.
+            Some(unsafe { T::from_foreign(old) })
+        })
+    }
+
+    /// Replaces an entry with a new value, dropping the old value (if any).
+    pub fn set(&self, index: usize, value: T) -> Result {
+        self.replace(index, value)?;
+        Ok(())
+    }
+
+    /// Looks up and returns a reference to an entry in the array, returning a `Guard` if it
+    /// exists.
+    ///
+    /// This guard blocks all other actions on the `XArray`. Callers are expected to drop the
+    /// `Guard` eagerly to avoid blocking other users, such as by taking a clone of the value.
+    pub fn get(&self, index: usize) -> Option<Guard<'_, T>> {
+        // SAFETY: `self.xa` is always valid by the type invariant.
+        unsafe { bindings::xa_lock(self.xa.get()) };
+
+        // SAFETY: `self.xa` is always valid by the type invariant.
+        let guard = ScopeGuard::new(|| unsafe { bindings::xa_unlock(self.xa.get()) });
+
+        // SAFETY: `self.xa` is always valid by the type invariant.
+        //
+        // As we are taking advantage of the lock to protect the data structures
+        // that we are storing in the XArray, we need to call xa_lock() before
+        // calling xa_load(), which we did.
+        let p = unsafe { bindings::xa_load(self.xa.get(), index.try_into().ok()?) };
+
+        NonNull::new(p as *mut T).map(|p| {
+            guard.dismiss();
+            Guard(p, self)
+        })
+    }
+
+    /// Removes and returns an entry, returning it if it existed.
+    pub fn remove(&self, index: usize) -> Option<T> {
+        // SAFETY: `self.xa` is always valid by the type invariant.
+        let p = unsafe { bindings::xa_erase(self.xa.get(), index.try_into().ok()?) };
+        if p.is_null() {
+            None
+        } else {
+            // SAFETY: All pointers stored in the array are pointers obtained by
+            // calling `T::into_foreign`.
+            Some(unsafe { T::from_foreign(p) })
+        }
+    }
+
+    /// Allocates a new index in the array, optionally storing a new value into it, with
+    /// configurable bounds for the index range to allocate from.
+    ///
+    /// If `value` is `None`, then the index is reserved from further allocation but remains
+    /// free for storing a value into it.
+    fn insert_between(&self, value: Option<T>, min: u32, max: u32) -> Result<usize> {
+        let new = value.map_or(core::ptr::null(), |a| a.into_foreign());
+        let mut id: u32 = 0;
+
+        let guard = ScopeGuard::new(|| {
+            if !new.is_null() {
+                // SAFETY: If `new` is not NULL, it came from the `ForeignOwnable` we got
+                // from the caller.
+                unsafe { T::from_foreign(new) };
+            }
+        });
+
+        // SAFETY: `self.xa` is always valid by the type invariant. If this succeeds, it
+        // takes ownership of the passed `T` (if any). If it fails, we must drop the
+        // `T` again.
+        let ret = unsafe {
+            bindings::xa_alloc(
+                self.xa.get(),
+                &mut id,
+                new.cast_mut(),
+                bindings::xa_limit { min, max },
+                bindings::GFP_KERNEL,
+            )
+        };
+
+        if ret < 0 {
+            Err(Error::from_errno(ret))
+        } else {
+            guard.dismiss();
+            Ok(id as usize)
+        }
+    }
+
+    /// Allocates a new index in the array, storing a new value into it, with configurable
+    /// bounds for the index range to allocate from.
+    pub fn alloc_limits(&self, value: T, min: u32, max: u32) -> Result<usize> {
+        self.insert_between(Some(value), min, max)
+    }
+
+    /// Allocates a new index in the array, storing a new value into it.
+    pub fn alloc(&self, value: T) -> Result<usize> {
+        self.alloc_limits(value, 0, u32::MAX)
+    }
+
+    /// Reserves a new index in the array within configurable bounds for the index.
+    ///
+    /// Returns a `Reservation` object, which can then be used to store a value at this index or
+    /// otherwise free it for reuse.
+    pub fn reserve_limits(&self, min: u32, max: u32) -> Result<Reservation<'_, T>> {
+        Ok(Reservation(
+            self,
+            self.insert_between(None, min, max)?,
+            PhantomData,
+        ))
+    }
+
+    /// Reserves a new index in the array.
+    ///
+    /// Returns a `Reservation` object, which can then be used to store a value at this index or
+    /// otherwise free it for reuse.
+    pub fn reserve(&self) -> Result<Reservation<'_, T>> {
+        Ok(Reservation(
+            self,
+            self.insert_between(None, 0, u32::MAX)?,
+            PhantomData,
+        ))
+    }
+}
+
+#[pinned_drop]
+impl<T: ForeignOwnable> PinnedDrop for XArray<T> {
+    fn drop(self: Pin<&mut Self>) {
+        let mut index: core::ffi::c_ulong = 0;
+        let mut entry;
+
+        // SAFETY: `self.xa` is valid by the type invariant, and as we have
+        // the only reference to the `XArray` we can safely iterate its contents
+        // and drop everything.
+        unsafe {
+            entry = bindings::xa_find(
+                self.xa.get(),
+                &mut index,
+                core::ffi::c_ulong::MAX,
+                bindings::XA_PRESENT,
+            );
+        }
+
+        while !entry.is_null() {
+            // SAFETY: All pointers stored in the array are pointers obtained by
+            // calling `T::into_foreign`.
+            unsafe {
+                T::from_foreign(entry);
+            }
+
+            // SAFETY: `self.xa` is valid by the type invariant, and as we have
+            // the only reference to the `XArray` we can safely iterate its contents
+            // and drop everything.
+            unsafe {
+                entry = bindings::xa_find_after(
+                    self.xa.get(),
+                    &mut index,
+                    core::ffi::c_ulong::MAX,
+                    bindings::XA_PRESENT,
+                );
+            }
+        }
+
+        // SAFETY: `xa_destroy()` is guaranteed to acquire the lock anyway.
+        unsafe {
+            bindings::xa_destroy(self.xa.get());
+        }
+    }
+}
+
+// SAFETY: XArray is thread-safe and all mutation operations are internally locked.
+unsafe impl<T: Send + ForeignOwnable> Send for XArray<T> {}
+unsafe impl<T: Sync + ForeignOwnable> Sync for XArray<T> {}
--
2.43.0


^ permalink raw reply related	[flat|nested] 7+ messages in thread

* Re: [PATCH v6] rust: xarray: Add an abstraction for XArray
  2024-01-16 15:06 [PATCH v6] rust: xarray: Add an abstraction for XArray Maíra Canal
@ 2024-01-16 23:53 ` Boqun Feng
  2024-02-05 10:29   ` Andreas Hindborg (Samsung)
  2024-02-09 12:12   ` Alice Ryhl
  2024-02-01 10:48 ` Benno Lossin
  2024-02-09 12:44 ` Alice Ryhl
  2 siblings, 2 replies; 7+ messages in thread
From: Boqun Feng @ 2024-01-16 23:53 UTC (permalink / raw)
  To: Maíra Canal
  Cc: Asahi Lina, Miguel Ojeda, Alex Gaynor, Wedson Almeida Filho,
	Gary Guo, Björn Roy Baron, Benno Lossin, Andreas Hindborg,
	Alice Ryhl, Matthew Wilcox, rust-for-linux, kernel-dev

On Tue, Jan 16, 2024 at 12:06:03PM -0300, Maíra Canal wrote:
> From: Asahi Lina <lina@asahilina.net>
> 
[...]
> v5 -> v6: https://lore.kernel.org/rust-for-linux/20231201195300.1329092-1-mcanal@igalia.com/T/
> 
> - Update constants to the new format (RUST_CONST_HELPER)
> - Add invariant for `self.0` being a pointer derived from `T::from_foreign` (Benno Lossin)
> - Fix the place of the INVARIANT comments (Benno Lossin)
> - Use the Pin-Init API (Benno Lossin)
> - Remove PhantomPinned from XArray (Benno Lossin)
> - Add new requirements for calling `xa_unlock()` (Benno Lossin)
> - Improve SAFETY comments (Benno Lossin)
> - Split unsafe block (Benno Lossin)
> - s/alloc_limits_opt/insert_between (Benno Lossin)
> - Specify the target type of the cast (Andreas Hindborg/Trevor Gross)
> - Guarantee that T is 4-byte aligned (Andreas Hindborg)
> - Add code examples in the code (Boqun Feng)

Thanks!

> 
> [1] https://github.com/mairacanal/linux/pull/11
> 
>  rust/bindings/bindings_helper.h |  17 ++
>  rust/helpers.c                  |  37 +++
>  rust/kernel/lib.rs              |   1 +
>  rust/kernel/xarray.rs           | 383 ++++++++++++++++++++++++++++++++
>  4 files changed, 438 insertions(+)
>  create mode 100644 rust/kernel/xarray.rs
> 

[...]

> +
> +/// Wrapper for a value owned by the `XArray` which holds the `XArray` lock until dropped.
> +///

Although the comment here says that `Guard` represents a *locked* slot
in the xarray, but..

> +/// INVARIANT: `Guard` holds a reference (`self.0`) to the underlying value owned by XArray.
> +/// You can use the `into_foreign` method to obtain a pointer to the foreign representation
> +/// of the owned value, which is valid for the lifetime of the Guard.

nothing about the xa lock is mentioned here in the type invariants. I
think it's better to say:

/// INVARIANT: `Guard` holds a reference (`self.0`) to the underlying
/// value owned by the `XArray` (`self.1`) with its lock held...

and then at the Guard::drop..

> +pub struct Guard<'a, T: ForeignOwnable>(NonNull<T>, &'a XArray<T>);
> +
> +impl<'a, T: ForeignOwnable> Guard<'a, T> {
> +    /// Borrow the underlying value wrapped by the `Guard`.
> +    ///
> +    /// Returns a `T::Borrowed` type for the owned `ForeignOwnable` type.
> +    pub fn borrow(&self) -> T::Borrowed<'_> {
> +        // SAFETY: The value is owned by the `XArray`, the lifetime it is borrowed for must not
> +        // outlive the `XArray` itself, nor the Guard that holds the lock ensuring the value
> +        // remains in the `XArray`.
> +        //
> +        // By the type invariant of `Guard`, we can guarantee that `Guard` holds this reference
> +        // (`self.0`).
> +        unsafe { T::borrow(self.0.as_ptr().cast()) }
> +    }
> +}
> +
> +// Convenience impl for `ForeignOwnable` types whose `Borrowed`
> +// form implements Deref.
> +impl<'a, T: ForeignOwnable> Deref for Guard<'a, T>
> +where
> +    T::Borrowed<'a>: Deref,
> +    for<'b> T::Borrowed<'b>: Into<&'b <T::Borrowed<'a> as Deref>::Target>,
> +{
> +    type Target = <T::Borrowed<'a> as Deref>::Target;
> +
> +    fn deref(&self) -> &Self::Target {
> +        self.borrow().into()
> +    }
> +}
> +
> +impl<'a, T: ForeignOwnable> Drop for Guard<'a, T> {
> +    fn drop(&mut self) {
> +        // SAFETY: By the type invariant, we guarantee that we have a reference
> +        // that owns the C xarray object.

you can (and should) also mention, "by the type invariant, `Guard` is
the owner of the xarray lock, so it's safe to unlock". Justifying the
ownership of lock at unlock point is safety related, since otherwise a
data race may happen.

> +        unsafe { bindings::xa_unlock(self.1.xa.get()) };
> +    }
> +}
> +
> +/// Represents a reserved slot in an `XArray`, which does not yet have a value but has an assigned
> +/// index and may not be allocated by any other user. If the Reservation is dropped without
> +/// being filled, the entry is marked as available again.
> +///
> +/// Users must ensure that reserved slots are not filled by other mechanisms, or otherwise their
> +/// contents may be dropped and replaced (which will print a warning).

I feel like this is a bit weird: instead of dropping and replacing, I
would expect we do nothing if someone steals our unused reservation ;-)
But let's see whether there would be a real user complain ;-)

> +pub struct Reservation<'a, T: ForeignOwnable>(&'a XArray<T>, usize, PhantomData<T>);
> +
> +impl<'a, T: ForeignOwnable> Reservation<'a, T> {
> +    /// Stores a value into the reserved slot.
> +    pub fn store(self, value: T) -> Result<usize> {
> +        if self.0.replace(self.1, value)?.is_some() {
> +            crate::pr_err!("XArray: Reservation stored but the entry already had data!\n");
> +            // Consider it a success anyway, not much we can do
> +        }
> +        let index = self.1;
> +        // The reservation is now fulfilled, so do not run our destructor.
> +        core::mem::forget(self);
> +        Ok(index)
> +    }
> +
> +    /// Returns the index of this reservation.
> +    pub fn index(&self) -> usize {
> +        self.1
> +    }
> +}
> +
> +impl<'a, T: ForeignOwnable> Drop for Reservation<'a, T> {
> +    fn drop(&mut self) {
> +        if self.0.remove(self.1).is_some() {
> +            crate::pr_err!("XArray: Reservation dropped but the entry was not empty!\n");
> +        }
> +    }
> +}
> +
> +/// An array which efficiently maps sparse integer indices to owned objects.
> +///
> +/// This is similar to a `Vec<Option<T>>`, but more efficient when there are holes in the
> +/// index space, and can be efficiently grown.
> +///
> +/// This structure is expected to often be used with an inner type that
> +/// can be efficiently cloned, such as an `Arc<T>`.
> +///
> +/// INVARIANT: All pointers stored in the array are pointers obtained by
> +/// calling `T::into_foreign`.

... or null pointers (considering reserve() cases).

> +#[pin_data(PinnedDrop)]
> +pub struct XArray<T: ForeignOwnable> {
> +    #[pin]
> +    xa: Opaque<bindings::xarray>,
> +    _p: PhantomData<T>,
> +}
> +
> +///
> +/// # Examples
> +///
> +/// ```rust
> +/// # use kernel::xarray;
> +/// # use kernel::prelude::*;
> +/// # use kernel::sync::Arc;
> +///
> +/// # struct Foo {
> +/// #     a: u32,
> +/// #     b: u32,
> +/// # }
> +///
> +/// let arr = Box::pin_init(xarray::XArray::<Arc<Foo>>::new(xarray::flags::ALLOC1))
> +///                                                    .expect("Unable to allocate XArray");
> +///
> +/// let foo = Arc::try_new(Foo { a : 1, b: 2 }).expect("Unable to allocate Foo");
> +/// let index = arr.alloc(foo).expect("Error allocating Index");
> +///
> +/// if let Some(guard) = arr.get(index) {
> +///     assert_eq!(guard.borrow().a, 1);
> +///     assert_eq!(guard.borrow().b, 2);
> +/// } else {
> +///     pr_info!("No value found in index {}", index);
> +/// }
> +///
> +/// let foo = Arc::try_new(Foo { a : 3, b: 4 }).expect("Unable to allocate Foo");
> +/// let index = arr.alloc(foo).expect("Error allocating Index");
> +///
> +/// if let Some(removed_data) = arr.remove(index) {
> +///     assert_eq!(removed_data.a, 3);
> +///     assert_eq!(removed_data.b, 4);
> +/// } else {
> +///     pr_info!("No value found in index {}", index);
> +/// }

Again, thanks!

> +/// ```
> +impl<T: ForeignOwnable> XArray<T> {
> +    /// Creates a new `XArray` with the given flags.
> +    pub fn new(flags: Flags) -> impl PinInit<Self> {
> +        pin_init!(Self {
> +            // SAFETY: `xa` is valid while the closure is called.
> +            xa <- Opaque::ffi_init(|xa| unsafe {
> +                bindings::xa_init_flags(xa, flags)
> +            }),
> +            _p: PhantomData,
> +        })
> +    }
> +
> +    /// Replaces an entry with a new value, returning the old value (if any).
> +    pub fn replace(&self, index: usize, value: T) -> Result<Option<T>> {
> +        let new = value.into_foreign();
> +
> +        build_assert!(mem::align_of::<T>() <= 4);

I know Benno suggested this, but this is not quite right ;-) Sorry I
didn't mention this earlier. Here T is a ForeignOwnable type, e.g.
Box<_>, Arc<_>, while they may be 4-byte aligned but the return pointers
of into_foreign() may not. What we need here is that `new` is at least 4
bytes aligned. Yes, this is a boring difference, but it's a difference..

> +
> +        // SAFETY: `new` just came from into_foreign(), and we dismiss this guard if
> +        // the xa_store operation succeeds and takes ownership of the pointer.
> +        let guard = ScopeGuard::new(|| unsafe {
> +            T::from_foreign(new);
> +        });
> +
> +        // SAFETY: `self.xa` is always valid by the type invariant, and we are storing
> +        // a `T::into_foreign()` result which upholds the later invariants.
> +        let old = unsafe {
> +            bindings::xa_store(
> +                self.xa.get(),
> +                index.try_into()?,
> +                new.cast_mut(),
> +                bindings::GFP_KERNEL,
> +            )
> +        };
> +
> +        // SAFETY: `xa_store` returns the old entry at this index on success or
> +        // a XArray result, which can be turn into an errno through `xa_err`.
> +        to_result(unsafe { bindings::xa_err(old) })?;
> +        guard.dismiss();
> +
> +        Ok(if old.is_null() {
> +            None
> +        } else {
> +            // SAFETY: The old value must have been stored by either this function or
> +            // `insert_between`, both of which ensure non-NULL entries are valid
> +            // ForeignOwnable pointers.

Type invariants can be used here other than functions' behaviors.

> +            Some(unsafe { T::from_foreign(old) })
> +        })
> +    }
> +
> +    /// Replaces an entry with a new value, dropping the old value (if any).
> +    pub fn set(&self, index: usize, value: T) -> Result {
> +        self.replace(index, value)?;
> +        Ok(())
> +    }
> +
> +    /// Looks up and returns a reference to an entry in the array, returning a `Guard` if it
> +    /// exists.
> +    ///
> +    /// This guard blocks all other actions on the `XArray`. Callers are expected to drop the
> +    /// `Guard` eagerly to avoid blocking other users, such as by taking a clone of the value.
> +    pub fn get(&self, index: usize) -> Option<Guard<'_, T>> {
> +        // SAFETY: `self.xa` is always valid by the type invariant.

XArray's type invariant only says: "All pointers stored in the array are
pointers obtained by calling `T::into_foreign`" (plus the null pointer
point I mentioned above). So here the type invariant doesn't guarantee
`self.xa` is always valid, I think you will need to extend the type
invariants with "`self.xa` is always an initialized and valid xarray".

> +        unsafe { bindings::xa_lock(self.xa.get()) };
> +
> +        // SAFETY: `self.xa` is always valid by the type invariant.
> +        let guard = ScopeGuard::new(|| unsafe { bindings::xa_unlock(self.xa.get()) });
> +
> +        // SAFETY: `self.xa` is always valid by the type invariant.
> +        //
> +        // As we are taking advantage of the lock to protect the data structures
> +        // that we are storing in the XArray, we need to call xa_lock() before
> +        // calling xa_load(), which we did.
> +        let p = unsafe { bindings::xa_load(self.xa.get(), index.try_into().ok()?) };
> +
> +        NonNull::new(p as *mut T).map(|p| {
> +            guard.dismiss();
> +            Guard(p, self)
> +        })
> +    }
> +
> +    /// Removes and returns an entry, returning it if it existed.
> +    pub fn remove(&self, index: usize) -> Option<T> {
> +        // SAFETY: `self.xa` is always valid by the type invariant.
> +        let p = unsafe { bindings::xa_erase(self.xa.get(), index.try_into().ok()?) };
> +        if p.is_null() {
> +            None
> +        } else {
> +            // SAFETY: All pointers stored in the array are pointers obtained by
> +            // calling `T::into_foreign`.
> +            Some(unsafe { T::from_foreign(p) })
> +        }


Hmm.. seems we need a:

	pub fn try_from_foreign(...) -> Option<Self>;

to avoid duplicate code. I will add an issue then.

> +    }
> +

[ snip, will take a look at the rest later]

Regards,
Boqun

^ permalink raw reply	[flat|nested] 7+ messages in thread

* Re: [PATCH v6] rust: xarray: Add an abstraction for XArray
  2024-01-16 15:06 [PATCH v6] rust: xarray: Add an abstraction for XArray Maíra Canal
  2024-01-16 23:53 ` Boqun Feng
@ 2024-02-01 10:48 ` Benno Lossin
  2024-02-09 21:14   ` Maíra Canal
  2024-02-09 12:44 ` Alice Ryhl
  2 siblings, 1 reply; 7+ messages in thread
From: Benno Lossin @ 2024-02-01 10:48 UTC (permalink / raw)
  To: Maíra Canal, Asahi Lina, Miguel Ojeda, Alex Gaynor,
	Wedson Almeida Filho, Boqun Feng, Gary Guo, Björn Roy Baron,
	Andreas Hindborg, Alice Ryhl, Matthew Wilcox
  Cc: rust-for-linux, kernel-dev

On 1/16/24 16:06, Maíra Canal wrote:
> From: Asahi Lina <lina@asahilina.net>
> 
> The XArray is an abstract data type which behaves like a very large
> array of pointers. Add a Rust abstraction for this data type.
> 
> The initial implementation uses explicit locking on get operations and
> returns a guard which blocks mutation, ensuring that the referenced
> object remains alive. To avoid excessive serialization, users are
> expected to use an inner type that can be efficiently cloned (such as
> Arc<T>), and eagerly clone and drop the guard to unblock other users
> after a lookup.
> 
> Future variants may support using RCU instead to avoid mutex locking.
> 
> This abstraction also introduces a reservation mechanism, which can be
> used by alloc-capable XArrays to reserve a free slot without immediately
> filling it, and then do so at a later time. If the reservation is
> dropped without being filled, the slot is freed again for other users,
> which eliminates the need for explicit cleanup code.
> 
> Signed-off-by: Asahi Lina <lina@asahilina.net>
> Co-developed-by: Maíra Canal <mcanal@igalia.com>
> Signed-off-by: Maíra Canal <mcanal@igalia.com>
> ---
> 
> This abstraction is part of the set of dependencies I need to upstream
> rustgem, a virtual GEM provider driver in the DRM [1]. Also, this
> abstraction will be useful for the upstreaming process of the drm/asahi
> driver.
> 
> Best Regards,
> - Maíra
> 
> Changelog
> =========
> 
> v1 -> v2: https://lore.kernel.org/r/20230224-rust-xarray-v1-1-80f0904ce5d3@asahilina.net
> 
> - Added Pin requirement for all XArray operations, to close a
>   soundness hole due to the lock in the XArray (locks are not safe to
>   move while locked). Creation does not require pinning in place, since
>   the lock cannot be acquired at that point.
> - Added safety note to Drop impl about why we don't need to do the lock
>   unlock dance to ensure soundness in case of a dropped lock guard.
> - Downstream drm/asahi driver was also rebased on this version to prove
>   it works (previously it was still on a pre-v1 version).
> - This still depends on the Error series (v1). v2 of that will need a
>   trivial rename of Error::from_kernel_errno -> Error::from_errno. If
>   this version of XArray ends up looking good, I'll send a trivial v4 of
>   XArray with the rename, after sending the v2 of the Error series.
> 
> v2 -> v3: https://lore.kernel.org/r/20230224-rust-xarray-v2-1-4eeb0134944c@asahilina.net
> 
> - Updated to the error v2/v3 series API.
> - Renamed `err` to `ret` for consistency with the other instance.
> 
> v3 -> v4: https://lore.kernel.org/rust-for-linux/20230224-rust-xarray-v3-1-04305b1173a5@asahilina.net/
> 
> - Rebase on top of rust-next.
> 
> v4 -> v5: https://lore.kernel.org/rust-for-linux/20231126131210.1384490-1-mcanal@igalia.com/T/
> 
> - Use Gary's suggestion for the Deref trait - no unsafe code! (Benno Lossin)
> - Use NonNull (Benno Lossin)
> - Not spelling out the lifetimes (Benno Lossin)
> - Change XArray invariants (Benno Lossin)
> - Add all SAFETY comments (Benno Lossin)
> - Use `kernel::error::to_result` (Benno Lossin)
> - s/alloc_limits/alloc_limits_opt (Benno Lossin)
> - Split unsafe block (Benno Lossin)
> - Make error handling of the function `alloc_limits_opt` through `ScopeGuard` (Benno Lossin)
> - Use `ScopeGuard` in the function `get` (Benno Lossin)
> 
> v5 -> v6: https://lore.kernel.org/rust-for-linux/20231201195300.1329092-1-mcanal@igalia.com/T/
> 
> - Update constants to the new format (RUST_CONST_HELPER)
> - Add invariant for `self.0` being a pointer derived from `T::from_foreign` (Benno Lossin)
> - Fix the place of the INVARIANT comments (Benno Lossin)
> - Use the Pin-Init API (Benno Lossin)
> - Remove PhantomPinned from XArray (Benno Lossin)
> - Add new requirements for calling `xa_unlock()` (Benno Lossin)
> - Improve SAFETY comments (Benno Lossin)
> - Split unsafe block (Benno Lossin)
> - s/alloc_limits_opt/insert_between (Benno Lossin)
> - Specify the target type of the cast (Andreas Hindborg/Trevor Gross)
> - Guarantee that T is 4-byte aligned (Andreas Hindborg)
> - Add code examples in the code (Boqun Feng)
> 
> [1] https://github.com/mairacanal/linux/pull/11
> 
>  rust/bindings/bindings_helper.h |  17 ++
>  rust/helpers.c                  |  37 +++
>  rust/kernel/lib.rs              |   1 +
>  rust/kernel/xarray.rs           | 383 ++++++++++++++++++++++++++++++++
>  4 files changed, 438 insertions(+)
>  create mode 100644 rust/kernel/xarray.rs
> 
> diff --git a/rust/bindings/bindings_helper.h b/rust/bindings/bindings_helper.h
> index b5714fb69fe3..e8e8187580fc 100644
> --- a/rust/bindings/bindings_helper.h
> +++ b/rust/bindings/bindings_helper.h
> @@ -13,8 +13,25 @@
>  #include <linux/wait.h>
>  #include <linux/sched.h>
>  #include <linux/workqueue.h>
> +#include <linux/xarray.h>
> 
>  /* `bindgen` gets confused at certain things. */
>  const size_t RUST_CONST_HELPER_ARCH_SLAB_MINALIGN = ARCH_SLAB_MINALIGN;
>  const gfp_t RUST_CONST_HELPER_GFP_KERNEL = GFP_KERNEL;
>  const gfp_t RUST_CONST_HELPER___GFP_ZERO = __GFP_ZERO;
> +
> +const gfp_t RUST_CONST_HELPER_XA_FLAGS_LOCK_IRQ = XA_FLAGS_LOCK_IRQ;
> +const gfp_t RUST_CONST_HELPER_XA_FLAGS_LOCK_BH = XA_FLAGS_LOCK_BH;
> +const gfp_t RUST_CONST_HELPER_XA_FLAGS_TRACK_FREE = XA_FLAGS_TRACK_FREE;
> +const gfp_t RUST_CONST_HELPER_XA_FLAGS_ZERO_BUSY = XA_FLAGS_ZERO_BUSY;
> +const gfp_t RUST_CONST_HELPER_XA_FLAGS_ALLOC_WRAPPED = XA_FLAGS_ALLOC_WRAPPED;
> +const gfp_t RUST_CONST_HELPER_XA_FLAGS_ACCOUNT = XA_FLAGS_ACCOUNT;
> +const gfp_t RUST_CONST_HELPER_XA_FLAGS_ALLOC = XA_FLAGS_ALLOC;
> +const gfp_t RUST_CONST_HELPER_XA_FLAGS_ALLOC1 = XA_FLAGS_ALLOC1;
> +
> +const xa_mark_t RUST_CONST_HELPER_XA_MARK_0 = XA_MARK_0;
> +const xa_mark_t RUST_CONST_HELPER_XA_MARK_1 = XA_MARK_1;
> +const xa_mark_t RUST_CONST_HELPER_XA_MARK_2 = XA_MARK_2;
> +const xa_mark_t RUST_CONST_HELPER_XA_PRESENT = XA_PRESENT;
> +const xa_mark_t RUST_CONST_HELPER_XA_MARK_MAX = XA_MARK_MAX;
> +const xa_mark_t RUST_CONST_HELPER_XA_FREE_MARK = XA_FREE_MARK;
> diff --git a/rust/helpers.c b/rust/helpers.c
> index 70e59efd92bc..72a7f9c596ad 100644
> --- a/rust/helpers.c
> +++ b/rust/helpers.c
> @@ -31,6 +31,7 @@
>  #include <linux/spinlock.h>
>  #include <linux/wait.h>
>  #include <linux/workqueue.h>
> +#include <linux/xarray.h>
> 
>  __noreturn void rust_helper_BUG(void)
>  {
> @@ -157,6 +158,42 @@ void rust_helper_init_work_with_key(struct work_struct *work, work_func_t func,
>  }
>  EXPORT_SYMBOL_GPL(rust_helper_init_work_with_key);
> 
> +void rust_helper_xa_init_flags(struct xarray *xa, gfp_t flags)
> +{
> +	xa_init_flags(xa, flags);
> +}
> +EXPORT_SYMBOL_GPL(rust_helper_xa_init_flags);
> +
> +bool rust_helper_xa_empty(struct xarray *xa)
> +{
> +	return xa_empty(xa);
> +}
> +EXPORT_SYMBOL_GPL(rust_helper_xa_empty);
> +
> +int rust_helper_xa_alloc(struct xarray *xa, u32 *id, void *entry, struct xa_limit limit, gfp_t gfp)
> +{
> +	return xa_alloc(xa, id, entry, limit, gfp);
> +}
> +EXPORT_SYMBOL_GPL(rust_helper_xa_alloc);
> +
> +void rust_helper_xa_lock(struct xarray *xa)
> +{
> +	xa_lock(xa);
> +}
> +EXPORT_SYMBOL_GPL(rust_helper_xa_lock);
> +
> +void rust_helper_xa_unlock(struct xarray *xa)
> +{
> +	xa_unlock(xa);
> +}
> +EXPORT_SYMBOL_GPL(rust_helper_xa_unlock);
> +
> +int rust_helper_xa_err(void *entry)
> +{
> +	return xa_err(entry);
> +}
> +EXPORT_SYMBOL_GPL(rust_helper_xa_err);
> +
>  /*
>   * `bindgen` binds the C `size_t` type as the Rust `usize` type, so we can
>   * use it in contexts where Rust expects a `usize` like slice (array) indices.
> diff --git a/rust/kernel/lib.rs b/rust/kernel/lib.rs
> index e6aff80b521f..1a4372a4e85c 100644
> --- a/rust/kernel/lib.rs
> +++ b/rust/kernel/lib.rs
> @@ -48,6 +48,7 @@
>  pub mod task;
>  pub mod types;
>  pub mod workqueue;
> +pub mod xarray;
> 
>  #[doc(hidden)]
>  pub use bindings;
> diff --git a/rust/kernel/xarray.rs b/rust/kernel/xarray.rs
> new file mode 100644
> index 000000000000..fd2ea8b1a307
> --- /dev/null
> +++ b/rust/kernel/xarray.rs
> @@ -0,0 +1,383 @@
> +// SPDX-License-Identifier: GPL-2.0
> +
> +//! XArray abstraction.
> +//!
> +//! C header: [`include/linux/xarray.h`](../../include/linux/xarray.h)
> +
> +use crate::{
> +    bindings,
> +    error::{to_result, Error, Result},
> +    prelude::*,
> +    types::{ForeignOwnable, Opaque, ScopeGuard},
> +};
> +use core::{marker::PhantomData, mem, ops::Deref, ptr::NonNull};
> +
> +/// Flags passed to `XArray::new` to configure the `XArray`.
> +type Flags = bindings::gfp_t;
> +
> +/// Flag values passed to `XArray::new` to configure the `XArray`.
> +pub mod flags {
> +    /// Use IRQ-safe locking.
> +    pub const LOCK_IRQ: super::Flags = bindings::XA_FLAGS_LOCK_IRQ;
> +    /// Use softirq-safe locking.
> +    pub const LOCK_BH: super::Flags = bindings::XA_FLAGS_LOCK_BH;
> +    /// Track which entries are free (distinct from None).
> +    pub const TRACK_FREE: super::Flags = bindings::XA_FLAGS_TRACK_FREE;
> +    /// Initialize array index 0 as busy.
> +    pub const ZERO_BUSY: super::Flags = bindings::XA_FLAGS_ZERO_BUSY;
> +    /// Use GFP_ACCOUNT for internal memory allocations.
> +    pub const ACCOUNT: super::Flags = bindings::XA_FLAGS_ACCOUNT;
> +    /// Create an allocating `XArray` starting at index 0.
> +    pub const ALLOC: super::Flags = bindings::XA_FLAGS_ALLOC;
> +    /// Create an allocating `XArray` starting at index 1.
> +    pub const ALLOC1: super::Flags = bindings::XA_FLAGS_ALLOC1;
> +}
> +
> +/// Wrapper for a value owned by the `XArray` which holds the `XArray` lock until dropped.
> +///
> +/// INVARIANT: `Guard` holds a reference (`self.0`) to the underlying value owned by XArray.

Please use `# Invariant` instead, since this is a rustdoc comment.
`INVARIANT` is used when you establish an invariant similar to `SAFETY`
comments.

> +/// You can use the `into_foreign` method to obtain a pointer to the foreign representation
> +/// of the owned value, which is valid for the lifetime of the Guard.

This should not be part of the invariants section.

> +pub struct Guard<'a, T: ForeignOwnable>(NonNull<T>, &'a XArray<T>);
> +
> +impl<'a, T: ForeignOwnable> Guard<'a, T> {
> +    /// Borrow the underlying value wrapped by the `Guard`.
> +    ///
> +    /// Returns a `T::Borrowed` type for the owned `ForeignOwnable` type.
> +    pub fn borrow(&self) -> T::Borrowed<'_> {
> +        // SAFETY: The value is owned by the `XArray`, the lifetime it is borrowed for must not
> +        // outlive the `XArray` itself, nor the Guard that holds the lock ensuring the value
> +        // remains in the `XArray`.
> +        //
> +        // By the type invariant of `Guard`, we can guarantee that `Guard` holds this reference
> +        // (`self.0`).
> +        unsafe { T::borrow(self.0.as_ptr().cast()) }
> +    }
> +}
> +
> +// Convenience impl for `ForeignOwnable` types whose `Borrowed`
> +// form implements Deref.
> +impl<'a, T: ForeignOwnable> Deref for Guard<'a, T>
> +where
> +    T::Borrowed<'a>: Deref,
> +    for<'b> T::Borrowed<'b>: Into<&'b <T::Borrowed<'a> as Deref>::Target>,
> +{
> +    type Target = <T::Borrowed<'a> as Deref>::Target;
> +
> +    fn deref(&self) -> &Self::Target {
> +        self.borrow().into()
> +    }
> +}
> +
> +impl<'a, T: ForeignOwnable> Drop for Guard<'a, T> {
> +    fn drop(&mut self) {
> +        // SAFETY: By the type invariant, we guarantee that we have a reference
> +        // that owns the C xarray object.
> +        unsafe { bindings::xa_unlock(self.1.xa.get()) };
> +    }
> +}
> +
> +/// Represents a reserved slot in an `XArray`, which does not yet have a value but has an assigned
> +/// index and may not be allocated by any other user. If the Reservation is dropped without
> +/// being filled, the entry is marked as available again.
> +///
> +/// Users must ensure that reserved slots are not filled by other mechanisms, or otherwise their
> +/// contents may be dropped and replaced (which will print a warning).
> +pub struct Reservation<'a, T: ForeignOwnable>(&'a XArray<T>, usize, PhantomData<T>);
> +
> +impl<'a, T: ForeignOwnable> Reservation<'a, T> {
> +    /// Stores a value into the reserved slot.
> +    pub fn store(self, value: T) -> Result<usize> {
> +        if self.0.replace(self.1, value)?.is_some() {
> +            crate::pr_err!("XArray: Reservation stored but the entry already had data!\n");
> +            // Consider it a success anyway, not much we can do
> +        }
> +        let index = self.1;
> +        // The reservation is now fulfilled, so do not run our destructor.
> +        core::mem::forget(self);
> +        Ok(index)
> +    }
> +
> +    /// Returns the index of this reservation.
> +    pub fn index(&self) -> usize {
> +        self.1
> +    }
> +}
> +
> +impl<'a, T: ForeignOwnable> Drop for Reservation<'a, T> {
> +    fn drop(&mut self) {
> +        if self.0.remove(self.1).is_some() {
> +            crate::pr_err!("XArray: Reservation dropped but the entry was not empty!\n");
> +        }
> +    }
> +}
> +
> +/// An array which efficiently maps sparse integer indices to owned objects.
> +///
> +/// This is similar to a `Vec<Option<T>>`, but more efficient when there are holes in the
> +/// index space, and can be efficiently grown.
> +///
> +/// This structure is expected to often be used with an inner type that
> +/// can be efficiently cloned, such as an `Arc<T>`.
> +///
> +/// INVARIANT: All pointers stored in the array are pointers obtained by
> +/// calling `T::into_foreign`.
> +#[pin_data(PinnedDrop)]
> +pub struct XArray<T: ForeignOwnable> {
> +    #[pin]
> +    xa: Opaque<bindings::xarray>,
> +    _p: PhantomData<T>,
> +}

I think it would be better to put this at the top of the file.

> +
> +///
> +/// # Examples
> +///
> +/// ```rust
> +/// # use kernel::xarray;
> +/// # use kernel::prelude::*;
> +/// # use kernel::sync::Arc;
> +///
> +/// # struct Foo {
> +/// #     a: u32,
> +/// #     b: u32,
> +/// # }

I think it's fine to show this.

> +///
> +/// let arr = Box::pin_init(xarray::XArray::<Arc<Foo>>::new(xarray::flags::ALLOC1))

Why not import `XArray` directly? Is this also really how rustfmt
formats this?

> +///                                                    .expect("Unable to allocate XArray");
> +///
> +/// let foo = Arc::try_new(Foo { a : 1, b: 2 }).expect("Unable to allocate Foo");
> +/// let index = arr.alloc(foo).expect("Error allocating Index");
> +///
> +/// if let Some(guard) = arr.get(index) {
> +///     assert_eq!(guard.borrow().a, 1);
> +///     assert_eq!(guard.borrow().b, 2);
> +/// } else {
> +///     pr_info!("No value found in index {}", index);
> +/// }
> +///
> +/// let foo = Arc::try_new(Foo { a : 3, b: 4 }).expect("Unable to allocate Foo");
> +/// let index = arr.alloc(foo).expect("Error allocating Index");
> +///
> +/// if let Some(removed_data) = arr.remove(index) {
> +///     assert_eq!(removed_data.a, 3);
> +///     assert_eq!(removed_data.b, 4);
> +/// } else {
> +///     pr_info!("No value found in index {}", index);
> +/// }
> +/// ```
> +impl<T: ForeignOwnable> XArray<T> {
> +    /// Creates a new `XArray` with the given flags.
> +    pub fn new(flags: Flags) -> impl PinInit<Self> {
> +        pin_init!(Self {
> +            // SAFETY: `xa` is valid while the closure is called.
> +            xa <- Opaque::ffi_init(|xa| unsafe {
> +                bindings::xa_init_flags(xa, flags)
> +            }),
> +            _p: PhantomData,
> +        })
> +    }
> +
> +    /// Replaces an entry with a new value, returning the old value (if any).
> +    pub fn replace(&self, index: usize, value: T) -> Result<Option<T>> {
> +        let new = value.into_foreign();
> +
> +        build_assert!(mem::align_of::<T>() <= 4);
> +
> +        // SAFETY: `new` just came from into_foreign(), and we dismiss this guard if
> +        // the xa_store operation succeeds and takes ownership of the pointer.
> +        let guard = ScopeGuard::new(|| unsafe {
> +            T::from_foreign(new);
> +        });
> +
> +        // SAFETY: `self.xa` is always valid by the type invariant, and we are storing
> +        // a `T::into_foreign()` result which upholds the later invariants.

The "we are storing..." should be in an `INVARIANT` comment.

> +        let old = unsafe {
> +            bindings::xa_store(
> +                self.xa.get(),
> +                index.try_into()?,
> +                new.cast_mut(),
> +                bindings::GFP_KERNEL,
> +            )
> +        };
> +
> +        // SAFETY: `xa_store` returns the old entry at this index on success or
> +        // a XArray result, which can be turn into an errno through `xa_err`.
> +        to_result(unsafe { bindings::xa_err(old) })?;
> +        guard.dismiss();
> +
> +        Ok(if old.is_null() {
> +            None
> +        } else {
> +            // SAFETY: The old value must have been stored by either this function or
> +            // `insert_between`, both of which ensure non-NULL entries are valid
> +            // ForeignOwnable pointers.
> +            Some(unsafe { T::from_foreign(old) })
> +        })
> +    }
> +
> +    /// Replaces an entry with a new value, dropping the old value (if any).
> +    pub fn set(&self, index: usize, value: T) -> Result {
> +        self.replace(index, value)?;
> +        Ok(())
> +    }
> +
> +    /// Looks up and returns a reference to an entry in the array, returning a `Guard` if it
> +    /// exists.
> +    ///
> +    /// This guard blocks all other actions on the `XArray`. Callers are expected to drop the
> +    /// `Guard` eagerly to avoid blocking other users, such as by taking a clone of the value.
> +    pub fn get(&self, index: usize) -> Option<Guard<'_, T>> {

I would not expect `get` to lock the object, perhaps this should be
renamed? Any suggestions?

> +        // SAFETY: `self.xa` is always valid by the type invariant.
> +        unsafe { bindings::xa_lock(self.xa.get()) };
> +
> +        // SAFETY: `self.xa` is always valid by the type invariant.
> +        let guard = ScopeGuard::new(|| unsafe { bindings::xa_unlock(self.xa.get()) });
> +
> +        // SAFETY: `self.xa` is always valid by the type invariant.
> +        //
> +        // As we are taking advantage of the lock to protect the data structures
> +        // that we are storing in the XArray, we need to call xa_lock() before
> +        // calling xa_load(), which we did.

I looked at the C code and `xa_load` states:

/**
 * xa_load() - Load an entry from an XArray.
 * @xa: XArray.
 * @index: index into array.
 *
 * Context: Any context.  Takes and releases the RCU lock.
 * Return: The entry at @index in @xa.
 */

So do you really need the lock before calling load?

> +        let p = unsafe { bindings::xa_load(self.xa.get(), index.try_into().ok()?) };
> +
> +        NonNull::new(p as *mut T).map(|p| {
> +            guard.dismiss();
> +            Guard(p, self)
> +        })
> +    }
> +
> +    /// Removes and returns an entry, returning it if it existed.
> +    pub fn remove(&self, index: usize) -> Option<T> {
> +        // SAFETY: `self.xa` is always valid by the type invariant.
> +        let p = unsafe { bindings::xa_erase(self.xa.get(), index.try_into().ok()?) };
> +        if p.is_null() {
> +            None
> +        } else {
> +            // SAFETY: All pointers stored in the array are pointers obtained by

By the type invariant of `Self`, all pointers...

> +            // calling `T::into_foreign`.
> +            Some(unsafe { T::from_foreign(p) })
> +        }
> +    }
> +
> +    /// Allocates a new index in the array, optionally storing a new value into it, with
> +    /// configurable bounds for the index range to allocate from.
> +    ///
> +    /// If `value` is `None`, then the index is reserved from further allocation but remains
> +    /// free for storing a value into it.
> +    fn insert_between(&self, value: Option<T>, min: u32, max: u32) -> Result<usize> {
> +        let new = value.map_or(core::ptr::null(), |a| a.into_foreign());
> +        let mut id: u32 = 0;
> +
> +        let guard = ScopeGuard::new(|| {
> +            if !new.is_null() {
> +                // SAFETY: If `new` is not NULL, it came from the `ForeignOwnable` we got
> +                // from the caller.
> +                unsafe { T::from_foreign(new) };
> +            }
> +        });
> +
> +        // SAFETY: `self.xa` is always valid by the type invariant. If this succeeds, it
> +        // takes ownership of the passed `T` (if any). If it fails, we must drop the
> +        // `T` again.

The second sentence should not be part of the safety comment (but it
can be a normal comment).

> +        let ret = unsafe {
> +            bindings::xa_alloc(
> +                self.xa.get(),
> +                &mut id,
> +                new.cast_mut(),
> +                bindings::xa_limit { min, max },
> +                bindings::GFP_KERNEL,
> +            )
> +        };
> +
> +        if ret < 0 {
> +            Err(Error::from_errno(ret))
> +        } else {
> +            guard.dismiss();
> +            Ok(id as usize)
> +        }
> +    }
> +
> +    /// Allocates a new index in the array, storing a new value into it, with configurable
> +    /// bounds for the index range to allocate from.
> +    pub fn alloc_limits(&self, value: T, min: u32, max: u32) -> Result<usize> {
> +        self.insert_between(Some(value), min, max)
> +    }
> +
> +    /// Allocates a new index in the array, storing a new value into it.
> +    pub fn alloc(&self, value: T) -> Result<usize> {
> +        self.alloc_limits(value, 0, u32::MAX)
> +    }
> +
> +    /// Reserves a new index in the array within configurable bounds for the index.
> +    ///
> +    /// Returns a `Reservation` object, which can then be used to store a value at this index or
> +    /// otherwise free it for reuse.
> +    pub fn reserve_limits(&self, min: u32, max: u32) -> Result<Reservation<'_, T>> {
> +        Ok(Reservation(
> +            self,
> +            self.insert_between(None, min, max)?,
> +            PhantomData,
> +        ))
> +    }
> +
> +    /// Reserves a new index in the array.
> +    ///
> +    /// Returns a `Reservation` object, which can then be used to store a value at this index or
> +    /// otherwise free it for reuse.
> +    pub fn reserve(&self) -> Result<Reservation<'_, T>> {
> +        Ok(Reservation(
> +            self,
> +            self.insert_between(None, 0, u32::MAX)?,
> +            PhantomData,
> +        ))
> +    }
> +}
> +
> +#[pinned_drop]
> +impl<T: ForeignOwnable> PinnedDrop for XArray<T> {
> +    fn drop(self: Pin<&mut Self>) {
> +        let mut index: core::ffi::c_ulong = 0;
> +        let mut entry;
> +
> +        // SAFETY: `self.xa` is valid by the type invariant, and as we have
> +        // the only reference to the `XArray` we can safely iterate its contents
> +        // and drop everything.

The second part is not needed? Since `xa_find` will take the lock.

-- 
Cheers,
Benno

> +        unsafe {
> +            entry = bindings::xa_find(
> +                self.xa.get(),
> +                &mut index,
> +                core::ffi::c_ulong::MAX,
> +                bindings::XA_PRESENT,
> +            );
> +        }
> +
> +        while !entry.is_null() {
> +            // SAFETY: All pointers stored in the array are pointers obtained by
> +            // calling `T::into_foreign`.
> +            unsafe {
> +                T::from_foreign(entry);
> +            }
> +
> +            // SAFETY: `self.xa` is valid by the type invariant, and as we have
> +            // the only reference to the `XArray` we can safely iterate its contents
> +            // and drop everything.
> +            unsafe {
> +                entry = bindings::xa_find_after(
> +                    self.xa.get(),
> +                    &mut index,
> +                    core::ffi::c_ulong::MAX,
> +                    bindings::XA_PRESENT,
> +                );
> +            }
> +        }
> +
> +        // SAFETY: `xa_destroy()` is guaranteed to acquire the lock anyway.
> +        unsafe {
> +            bindings::xa_destroy(self.xa.get());
> +        }
> +    }
> +}
> +
> +// SAFETY: XArray is thread-safe and all mutation operations are internally locked.
> +unsafe impl<T: Send + ForeignOwnable> Send for XArray<T> {}
> +unsafe impl<T: Sync + ForeignOwnable> Sync for XArray<T> {}
> --
> 2.43.0
> 


^ permalink raw reply	[flat|nested] 7+ messages in thread

* Re: [PATCH v6] rust: xarray: Add an abstraction for XArray
  2024-01-16 23:53 ` Boqun Feng
@ 2024-02-05 10:29   ` Andreas Hindborg (Samsung)
  2024-02-09 12:12   ` Alice Ryhl
  1 sibling, 0 replies; 7+ messages in thread
From: Andreas Hindborg (Samsung) @ 2024-02-05 10:29 UTC (permalink / raw)
  To: Boqun Feng
  Cc: Maíra Canal, Asahi Lina, Miguel Ojeda, Alex Gaynor,
	Wedson Almeida Filho, Gary Guo, Björn Roy Baron,
	Benno Lossin, Alice Ryhl, Matthew Wilcox, rust-for-linux,
	kernel-dev


Boqun Feng <boqun.feng@gmail.com> writes:

> On Tue, Jan 16, 2024 at 12:06:03PM -0300, Maíra Canal wrote:
>> From: Asahi Lina <lina@asahilina.net>
>> 
> [...]
>> v5 -> v6: https://lore.kernel.org/rust-for-linux/20231201195300.1329092-1-mcanal@igalia.com/T/
>> 
>> - Update constants to the new format (RUST_CONST_HELPER)
>> - Add invariant for `self.0` being a pointer derived from `T::from_foreign` (Benno Lossin)
>> - Fix the place of the INVARIANT comments (Benno Lossin)
>> - Use the Pin-Init API (Benno Lossin)
>> - Remove PhantomPinned from XArray (Benno Lossin)
>> - Add new requirements for calling `xa_unlock()` (Benno Lossin)
>> - Improve SAFETY comments (Benno Lossin)
>> - Split unsafe block (Benno Lossin)
>> - s/alloc_limits_opt/insert_between (Benno Lossin)
>> - Specify the target type of the cast (Andreas Hindborg/Trevor Gross)
>> - Guarantee that T is 4-byte aligned (Andreas Hindborg)
>> - Add code examples in the code (Boqun Feng)
>
> Thanks!
>
>> 
>> [1] https://github.com/mairacanal/linux/pull/11
>> 
>>  rust/bindings/bindings_helper.h |  17 ++
>>  rust/helpers.c                  |  37 +++
>>  rust/kernel/lib.rs              |   1 +
>>  rust/kernel/xarray.rs           | 383 ++++++++++++++++++++++++++++++++
>>  4 files changed, 438 insertions(+)
>>  create mode 100644 rust/kernel/xarray.rs
>> 
>
> [...]
>
>> +
>> +/// Wrapper for a value owned by the `XArray` which holds the `XArray` lock until dropped.
>> +///
>
> Although the comment here says that `Guard` represents a *locked* slot
> in the xarray, but..
>
>> +/// INVARIANT: `Guard` holds a reference (`self.0`) to the underlying value owned by XArray.
>> +/// You can use the `into_foreign` method to obtain a pointer to the foreign representation
>> +/// of the owned value, which is valid for the lifetime of the Guard.
>
> nothing about the xa lock is mentioned here in the type invariants. I
> think it's better to say:
>
> /// INVARIANT: `Guard` holds a reference (`self.0`) to the underlying
> /// value owned by the `XArray` (`self.1`) with its lock held...
>
> and then at the Guard::drop..
>
>> +pub struct Guard<'a, T: ForeignOwnable>(NonNull<T>, &'a XArray<T>);
>> +
>> +impl<'a, T: ForeignOwnable> Guard<'a, T> {
>> +    /// Borrow the underlying value wrapped by the `Guard`.
>> +    ///
>> +    /// Returns a `T::Borrowed` type for the owned `ForeignOwnable` type.
>> +    pub fn borrow(&self) -> T::Borrowed<'_> {
>> +        // SAFETY: The value is owned by the `XArray`, the lifetime it is borrowed for must not
>> +        // outlive the `XArray` itself, nor the Guard that holds the lock ensuring the value
>> +        // remains in the `XArray`.
>> +        //
>> +        // By the type invariant of `Guard`, we can guarantee that `Guard` holds this reference
>> +        // (`self.0`).
>> +        unsafe { T::borrow(self.0.as_ptr().cast()) }
>> +    }
>> +}
>> +
>> +// Convenience impl for `ForeignOwnable` types whose `Borrowed`
>> +// form implements Deref.
>> +impl<'a, T: ForeignOwnable> Deref for Guard<'a, T>
>> +where
>> +    T::Borrowed<'a>: Deref,
>> +    for<'b> T::Borrowed<'b>: Into<&'b <T::Borrowed<'a> as Deref>::Target>,
>> +{
>> +    type Target = <T::Borrowed<'a> as Deref>::Target;
>> +
>> +    fn deref(&self) -> &Self::Target {
>> +        self.borrow().into()
>> +    }
>> +}
>> +
>> +impl<'a, T: ForeignOwnable> Drop for Guard<'a, T> {
>> +    fn drop(&mut self) {
>> +        // SAFETY: By the type invariant, we guarantee that we have a reference
>> +        // that owns the C xarray object.
>
> you can (and should) also mention, "by the type invariant, `Guard` is
> the owner of the xarray lock, so it's safe to unlock". Justifying the
> ownership of lock at unlock point is safety related, since otherwise a
> data race may happen.
>
>> +        unsafe { bindings::xa_unlock(self.1.xa.get()) };
>> +    }
>> +}
>> +
>> +/// Represents a reserved slot in an `XArray`, which does not yet have a value but has an assigned
>> +/// index and may not be allocated by any other user. If the Reservation is dropped without
>> +/// being filled, the entry is marked as available again.
>> +///
>> +/// Users must ensure that reserved slots are not filled by other mechanisms, or otherwise their
>> +/// contents may be dropped and replaced (which will print a warning).
>
> I feel like this is a bit weird: instead of dropping and replacing, I
> would expect we do nothing if someone steals our unused reservation ;-)
> But let's see whether there would be a real user complain ;-)
>
>> +pub struct Reservation<'a, T: ForeignOwnable>(&'a XArray<T>, usize, PhantomData<T>);
>> +
>> +impl<'a, T: ForeignOwnable> Reservation<'a, T> {
>> +    /// Stores a value into the reserved slot.
>> +    pub fn store(self, value: T) -> Result<usize> {
>> +        if self.0.replace(self.1, value)?.is_some() {
>> +            crate::pr_err!("XArray: Reservation stored but the entry already had data!\n");
>> +            // Consider it a success anyway, not much we can do
>> +        }
>> +        let index = self.1;
>> +        // The reservation is now fulfilled, so do not run our destructor.
>> +        core::mem::forget(self);
>> +        Ok(index)
>> +    }
>> +
>> +    /// Returns the index of this reservation.
>> +    pub fn index(&self) -> usize {
>> +        self.1
>> +    }
>> +}
>> +
>> +impl<'a, T: ForeignOwnable> Drop for Reservation<'a, T> {
>> +    fn drop(&mut self) {
>> +        if self.0.remove(self.1).is_some() {
>> +            crate::pr_err!("XArray: Reservation dropped but the entry was not empty!\n");
>> +        }
>> +    }
>> +}
>> +
>> +/// An array which efficiently maps sparse integer indices to owned objects.
>> +///
>> +/// This is similar to a `Vec<Option<T>>`, but more efficient when there are holes in the
>> +/// index space, and can be efficiently grown.
>> +///
>> +/// This structure is expected to often be used with an inner type that
>> +/// can be efficiently cloned, such as an `Arc<T>`.
>> +///
>> +/// INVARIANT: All pointers stored in the array are pointers obtained by
>> +/// calling `T::into_foreign`.
>
> ... or null pointers (considering reserve() cases).
>
>> +#[pin_data(PinnedDrop)]
>> +pub struct XArray<T: ForeignOwnable> {
>> +    #[pin]
>> +    xa: Opaque<bindings::xarray>,
>> +    _p: PhantomData<T>,
>> +}
>> +
>> +///
>> +/// # Examples
>> +///
>> +/// ```rust
>> +/// # use kernel::xarray;
>> +/// # use kernel::prelude::*;
>> +/// # use kernel::sync::Arc;
>> +///
>> +/// # struct Foo {
>> +/// #     a: u32,
>> +/// #     b: u32,
>> +/// # }
>> +///
>> +/// let arr = Box::pin_init(xarray::XArray::<Arc<Foo>>::new(xarray::flags::ALLOC1))
>> +///                                                    .expect("Unable to allocate XArray");
>> +///
>> +/// let foo = Arc::try_new(Foo { a : 1, b: 2 }).expect("Unable to allocate Foo");
>> +/// let index = arr.alloc(foo).expect("Error allocating Index");
>> +///
>> +/// if let Some(guard) = arr.get(index) {
>> +///     assert_eq!(guard.borrow().a, 1);
>> +///     assert_eq!(guard.borrow().b, 2);
>> +/// } else {
>> +///     pr_info!("No value found in index {}", index);
>> +/// }
>> +///
>> +/// let foo = Arc::try_new(Foo { a : 3, b: 4 }).expect("Unable to allocate Foo");
>> +/// let index = arr.alloc(foo).expect("Error allocating Index");
>> +///
>> +/// if let Some(removed_data) = arr.remove(index) {
>> +///     assert_eq!(removed_data.a, 3);
>> +///     assert_eq!(removed_data.b, 4);
>> +/// } else {
>> +///     pr_info!("No value found in index {}", index);
>> +/// }
>
> Again, thanks!
>
>> +/// ```
>> +impl<T: ForeignOwnable> XArray<T> {
>> +    /// Creates a new `XArray` with the given flags.
>> +    pub fn new(flags: Flags) -> impl PinInit<Self> {
>> +        pin_init!(Self {
>> +            // SAFETY: `xa` is valid while the closure is called.
>> +            xa <- Opaque::ffi_init(|xa| unsafe {
>> +                bindings::xa_init_flags(xa, flags)
>> +            }),
>> +            _p: PhantomData,
>> +        })
>> +    }
>> +
>> +    /// Replaces an entry with a new value, returning the old value (if any).
>> +    pub fn replace(&self, index: usize, value: T) -> Result<Option<T>> {
>> +        let new = value.into_foreign();
>> +
>> +        build_assert!(mem::align_of::<T>() <= 4);
>
> I know Benno suggested this, but this is not quite right ;-) Sorry I
> didn't mention this earlier. Here T is a ForeignOwnable type, e.g.
> Box<_>, Arc<_>, while they may be 4-byte aligned but the return pointers
> of into_foreign() may not. What we need here is that `new` is at least 4
> bytes aligned. Yes, this is a boring difference, but it's a difference..

Also, this line would assert that the alignment of `T` is less than or
equal to 4 bytes? So a 2 byte aligned type would be accepted, which is
not what we want. 4, 8, 12, etc. is fine.

Instead of this, we can check that the last two bits of `new` is zero.
But that would not be const 😬

This is the relevant part of documentation:

> Normal pointers may be stored in the XArray directly.  They must be 4-byte
> aligned, which is true for any pointer returned from kmalloc() and
> alloc_page().  It isn't true for arbitrary user-space pointers,
> nor for function pointers.  You can store pointers to statically allocated
> objects, as long as those objects have an alignment of at least 4.

BR Andreas

^ permalink raw reply	[flat|nested] 7+ messages in thread

* Re: [PATCH v6] rust: xarray: Add an abstraction for XArray
  2024-01-16 23:53 ` Boqun Feng
  2024-02-05 10:29   ` Andreas Hindborg (Samsung)
@ 2024-02-09 12:12   ` Alice Ryhl
  1 sibling, 0 replies; 7+ messages in thread
From: Alice Ryhl @ 2024-02-09 12:12 UTC (permalink / raw)
  To: Boqun Feng
  Cc: Maíra Canal, Asahi Lina, Miguel Ojeda, Alex Gaynor,
	Wedson Almeida Filho, Gary Guo, Björn Roy Baron,
	Benno Lossin, Andreas Hindborg, Matthew Wilcox, rust-for-linux,
	kernel-dev

On Wed, Jan 17, 2024 at 12:53 AM Boqun Feng <boqun.feng@gmail.com> wrote:
>
> On Tue, Jan 16, 2024 at 12:06:03PM -0300, Maíra Canal wrote:
> > +    /// Replaces an entry with a new value, returning the old value (if any).
> > +    pub fn replace(&self, index: usize, value: T) -> Result<Option<T>> {
> > +        let new = value.into_foreign();
> > +
> > +        build_assert!(mem::align_of::<T>() <= 4);
>
> I know Benno suggested this, but this is not quite right ;-) Sorry I
> didn't mention this earlier. Here T is a ForeignOwnable type, e.g.
> Box<_>, Arc<_>, while they may be 4-byte aligned but the return pointers
> of into_foreign() may not. What we need here is that `new` is at least 4
> bytes aligned. Yes, this is a boring difference, but it's a difference..

Perhaps we should add a property to the trait?

pub trait ForeignOwnable: Sized {
    /// The alignment of pointers returned by `into_foreign`.
    const FOREIGN_ALIGN: usize;
    type Borrowed<'a>;
    fn into_foreign(self) -> *const core::ffi::c_void;
    unsafe fn borrow<'a>(ptr: *const core::ffi::c_void) -> Self::Borrowed<'a>;
    unsafe fn from_foreign(ptr: *const core::ffi::c_void) -> Self;
}

Then we can write this as:

build_assert!(T::FOREIGN_ALIGN >= 4);

(Note also that it should be >=.)

Alice

^ permalink raw reply	[flat|nested] 7+ messages in thread

* Re: [PATCH v6] rust: xarray: Add an abstraction for XArray
  2024-01-16 15:06 [PATCH v6] rust: xarray: Add an abstraction for XArray Maíra Canal
  2024-01-16 23:53 ` Boqun Feng
  2024-02-01 10:48 ` Benno Lossin
@ 2024-02-09 12:44 ` Alice Ryhl
  2 siblings, 0 replies; 7+ messages in thread
From: Alice Ryhl @ 2024-02-09 12:44 UTC (permalink / raw)
  To: mcanal
  Cc: a.hindborg, alex.gaynor, aliceryhl, benno.lossin, bjorn3_gh,
	boqun.feng, gary, kernel-dev, lina, ojeda, rust-for-linux,
	wedsonaf, willy

> +impl<'a, T: ForeignOwnable> Drop for Guard<'a, T> {
> +    fn drop(&mut self) {
> +        // SAFETY: By the type invariant, we guarantee that we have a reference
> +        // that owns the C xarray object.
> +        unsafe { bindings::xa_unlock(self.1.xa.get()) };
> +    }
> +}

No, we own the lock. We don't own the entire xarray object.

// SAFETY: By the type invariant we own the xarray lock, so we may unlock it here.

> +    /// Looks up and returns a reference to an entry in the array, returning a `Guard` if it
> +    /// exists.
> +    ///
> +    /// This guard blocks all other actions on the `XArray`. Callers are expected to drop the
> +    /// `Guard` eagerly to avoid blocking other users, such as by taking a clone of the value.
> +    pub fn get(&self, index: usize) -> Option<Guard<'_, T>> {

I would rename this function to `get_locked` or something like that. The
name `get` makes more sense for a function that returns an
`Option<Arc<T>>` by incrementing the refcount before releasing the lock.

> +        // SAFETY: `self.xa` is always valid by the type invariant.
> +        //
> +        // As we are taking advantage of the lock to protect the data structures
> +        // that we are storing in the XArray, we need to call xa_lock() before
> +        // calling xa_load(), which we did.
> +        let p = unsafe { bindings::xa_load(self.xa.get(), index.try_into().ok()?) };

The `xa_load` function doesn't require that you hold the lock (but it
does allow you to do so). The reason why you hold the lock is to prevent
`p` from being invalidated by a concurrent call to `set`. I would make
this more explicit.

// SAFETY: `self.xa` is always valid by the type invariant.
//
// We currently hold the xa_lock, which is allowed by xa_load. The
// returned pointer `p` is only valid until we release the lock, which
// is okay here, since the returned `Guard` ensures that the pointer can
// only be used while the lock is still held.

> +        NonNull::new(p as *mut T).map(|p| {
> +            guard.dismiss();
> +            Guard(p, self)
> +        })

I find this confusing. How about this?

let p = NonNull::new(p.cast::<T>())?;
guard.dismiss();
// INVARIANT: We just dismissed the `guard`, so we can pass ownership of
// the lock to the returned `Guard`.
Some(Guard(p, self))

> +        let old = unsafe {
> +            bindings::xa_store(
> +                self.xa.get(),
> +                index.try_into()?,
> +                new.cast_mut(),
> +                bindings::GFP_KERNEL,
> +            )
> +        };
> [..]
> +        let p = unsafe { bindings::xa_load(self.xa.get(), index.try_into().ok()?) };
> [..]
> +        let p = unsafe { bindings::xa_erase(self.xa.get(), index.try_into().ok()?) };

I find these conversions of the index problematic. The type is `unsigned
long`, which is always the same as `usize` in the kernel. I recommend
introducing a method like this:

fn to_index(i: usize) -> c_ulong {
	build_assert!(size_of::<usize>() == size_of::<c_ulong>());
	i as c_ulong
}

And then use this method instead of the `index.try_into().ok()?` stuff.

> +    /// Removes and returns an entry, returning it if it existed.
> +    pub fn remove(&self, index: usize) -> Option<T> {
> +        // SAFETY: `self.xa` is always valid by the type invariant.
> +        let p = unsafe { bindings::xa_erase(self.xa.get(), index.try_into().ok()?) };
> +        if p.is_null() {
> +            None
> +        } else {
> +            // SAFETY: All pointers stored in the array are pointers obtained by
> +            // calling `T::into_foreign`.
> +            Some(unsafe { T::from_foreign(p) })
> +        }
> +    }

Not sure what the status on that patch is, but this could use the new
`ForeignOwnable::try_from_foreign` method.

https://lore.kernel.org/all/0100018d53f737f8-80c1fe97-0019-40d7-ab69-b1b192785cd7-000000@email.amazonses.com/

> +        let guard = ScopeGuard::new(|| {
> +            if !new.is_null() {
> +                // SAFETY: If `new` is not NULL, it came from the `ForeignOwnable` we got
> +                // from the caller.
> +                unsafe { T::from_foreign(new) };
> +            }
> +        });

I would prefer if you always used `drop(T::from_foreign(new))` whenever
you are immediately dropping it.

> +            // SAFETY: All pointers stored in the array are pointers obtained by
> +            // calling `T::into_foreign`.
> +            unsafe {
> +                T::from_foreign(entry);
> +            }

Same here. Also, we generally put the ; outside the unsafe block, since
that formats more nicely.

> +        // SAFETY: `xa_destroy()` is guaranteed to acquire the lock anyway.
> +        unsafe {
> +            bindings::xa_destroy(self.xa.get());
> +        }

This safety comment doesn't make sense to me. Why is the lock relevant?
I would say something along the lines of:

// SAFETY: By the type invariants, we have ownership of the xarray, and
// we don't use it after this call, so we can destroy it.

> +// SAFETY: XArray is thread-safe and all mutation operations are internally locked.
> +unsafe impl<T: Send + ForeignOwnable> Send for XArray<T> {}
> +unsafe impl<T: Sync + ForeignOwnable> Sync for XArray<T> {}

This is wrong. If I have a `!Send + Sync` type, then the XArray will be
`Sync`, so I can use the `&self` methods `set` and `remove` to transfer
ownership of the value to another thread.

Instead, both impls should require `T: Send`. You don't actually need
`Sync` since you currently don't provide any APIs that allow concurrent
access to values in the xarray. However, it still might make sense to
require `T: Send + Sync` in case someone adds such a method in the
future.

Alice

^ permalink raw reply	[flat|nested] 7+ messages in thread

* Re: [PATCH v6] rust: xarray: Add an abstraction for XArray
  2024-02-01 10:48 ` Benno Lossin
@ 2024-02-09 21:14   ` Maíra Canal
  0 siblings, 0 replies; 7+ messages in thread
From: Maíra Canal @ 2024-02-09 21:14 UTC (permalink / raw)
  To: Benno Lossin, Asahi Lina, Miguel Ojeda, Alex Gaynor,
	Wedson Almeida Filho, Boqun Feng, Gary Guo, Björn Roy Baron,
	Andreas Hindborg, Alice Ryhl, Matthew Wilcox
  Cc: rust-for-linux, kernel-dev

On 2/1/24 07:48, Benno Lossin wrote:
> On 1/16/24 16:06, Maíra Canal wrote:
>> From: Asahi Lina <lina@asahilina.net>
>>

[...]

>> +        let old = unsafe {
>> +            bindings::xa_store(
>> +                self.xa.get(),
>> +                index.try_into()?,
>> +                new.cast_mut(),
>> +                bindings::GFP_KERNEL,
>> +            )
>> +        };
>> +
>> +        // SAFETY: `xa_store` returns the old entry at this index on success or
>> +        // a XArray result, which can be turn into an errno through `xa_err`.
>> +        to_result(unsafe { bindings::xa_err(old) })?;
>> +        guard.dismiss();
>> +
>> +        Ok(if old.is_null() {
>> +            None
>> +        } else {
>> +            // SAFETY: The old value must have been stored by either this function or
>> +            // `insert_between`, both of which ensure non-NULL entries are valid
>> +            // ForeignOwnable pointers.
>> +            Some(unsafe { T::from_foreign(old) })
>> +        })
>> +    }
>> +
>> +    /// Replaces an entry with a new value, dropping the old value (if any).
>> +    pub fn set(&self, index: usize, value: T) -> Result {
>> +        self.replace(index, value)?;
>> +        Ok(())
>> +    }
>> +
>> +    /// Looks up and returns a reference to an entry in the array, returning a `Guard` if it
>> +    /// exists.
>> +    ///
>> +    /// This guard blocks all other actions on the `XArray`. Callers are expected to drop the
>> +    /// `Guard` eagerly to avoid blocking other users, such as by taking a clone of the value.
>> +    pub fn get(&self, index: usize) -> Option<Guard<'_, T>> {
> 
> I would not expect `get` to lock the object, perhaps this should be
> renamed? Any suggestions?

I believe that `get` is pretty convenient and ergonomic. I thought about 
`locked_get` or `get_locked`, but it sounds weird.

> 
>> +        // SAFETY: `self.xa` is always valid by the type invariant.
>> +        unsafe { bindings::xa_lock(self.xa.get()) };
>> +
>> +        // SAFETY: `self.xa` is always valid by the type invariant.
>> +        let guard = ScopeGuard::new(|| unsafe { bindings::xa_unlock(self.xa.get()) });
>> +
>> +        // SAFETY: `self.xa` is always valid by the type invariant.
>> +        //
>> +        // As we are taking advantage of the lock to protect the data structures
>> +        // that we are storing in the XArray, we need to call xa_lock() before
>> +        // calling xa_load(), which we did.
> 
> I looked at the C code and `xa_load` states:
> 
> /**
>   * xa_load() - Load an entry from an XArray.
>   * @xa: XArray.
>   * @index: index into array.
>   *
>   * Context: Any context.  Takes and releases the RCU lock.
>   * Return: The entry at @index in @xa.
>   */
> 
> So do you really need the lock before calling load?

"If you want to take advantage of the lock to protect the data 
structures that you are storing in the XArray, you can call xa_lock() 
before calling xa_load(), then take a reference count on the object you 
have found before calling xa_unlock(). This will prevent stores from 
removing the object from the array between looking up the object and 
incrementing the refcount. You can also use RCU to avoid dereferencing 
freed memory, but an explanation of that is beyond the scope of this 
document."

 From https://docs.kernel.org/core-api/xarray.html

Best Regards,
- Maíra

> 
>> +        let p = unsafe { bindings::xa_load(self.xa.get(), index.try_into().ok()?) };
>> +
>> +        NonNull::new(p as *mut T).map(|p| {
>> +            guard.dismiss();
>> +            Guard(p, self)
>> +        })
>> +    }
>> +
>> +    /// Removes and returns an entry, returning it if it existed.
>> +    pub fn remove(&self, index: usize) -> Option<T> {
>> +        // SAFETY: `self.xa` is always valid by the type invariant.
>> +        let p = unsafe { bindings::xa_erase(self.xa.get(), index.try_into().ok()?) };
>> +        if p.is_null() {
>> +            None
>> +        } else {
>> +            // SAFETY: All pointers stored in the array are pointers obtained by
> 
> By the type invariant of `Self`, all pointers...
> 
>> +            // calling `T::into_foreign`.
>> +            Some(unsafe { T::from_foreign(p) })
>> +        }
>> +    }
>> +
>> +    /// Allocates a new index in the array, optionally storing a new value into it, with
>> +    /// configurable bounds for the index range to allocate from.
>> +    ///
>> +    /// If `value` is `None`, then the index is reserved from further allocation but remains
>> +    /// free for storing a value into it.
>> +    fn insert_between(&self, value: Option<T>, min: u32, max: u32) -> Result<usize> {
>> +        let new = value.map_or(core::ptr::null(), |a| a.into_foreign());
>> +        let mut id: u32 = 0;
>> +
>> +        let guard = ScopeGuard::new(|| {
>> +            if !new.is_null() {
>> +                // SAFETY: If `new` is not NULL, it came from the `ForeignOwnable` we got
>> +                // from the caller.
>> +                unsafe { T::from_foreign(new) };
>> +            }
>> +        });
>> +
>> +        // SAFETY: `self.xa` is always valid by the type invariant. If this succeeds, it
>> +        // takes ownership of the passed `T` (if any). If it fails, we must drop the
>> +        // `T` again.
> 
> The second sentence should not be part of the safety comment (but it
> can be a normal comment).
> 
>> +        let ret = unsafe {
>> +            bindings::xa_alloc(
>> +                self.xa.get(),
>> +                &mut id,
>> +                new.cast_mut(),
>> +                bindings::xa_limit { min, max },
>> +                bindings::GFP_KERNEL,
>> +            )
>> +        };
>> +
>> +        if ret < 0 {
>> +            Err(Error::from_errno(ret))
>> +        } else {
>> +            guard.dismiss();
>> +            Ok(id as usize)
>> +        }
>> +    }
>> +
>> +    /// Allocates a new index in the array, storing a new value into it, with configurable
>> +    /// bounds for the index range to allocate from.
>> +    pub fn alloc_limits(&self, value: T, min: u32, max: u32) -> Result<usize> {
>> +        self.insert_between(Some(value), min, max)
>> +    }
>> +
>> +    /// Allocates a new index in the array, storing a new value into it.
>> +    pub fn alloc(&self, value: T) -> Result<usize> {
>> +        self.alloc_limits(value, 0, u32::MAX)
>> +    }
>> +
>> +    /// Reserves a new index in the array within configurable bounds for the index.
>> +    ///
>> +    /// Returns a `Reservation` object, which can then be used to store a value at this index or
>> +    /// otherwise free it for reuse.
>> +    pub fn reserve_limits(&self, min: u32, max: u32) -> Result<Reservation<'_, T>> {
>> +        Ok(Reservation(
>> +            self,
>> +            self.insert_between(None, min, max)?,
>> +            PhantomData,
>> +        ))
>> +    }
>> +
>> +    /// Reserves a new index in the array.
>> +    ///
>> +    /// Returns a `Reservation` object, which can then be used to store a value at this index or
>> +    /// otherwise free it for reuse.
>> +    pub fn reserve(&self) -> Result<Reservation<'_, T>> {
>> +        Ok(Reservation(
>> +            self,
>> +            self.insert_between(None, 0, u32::MAX)?,
>> +            PhantomData,
>> +        ))
>> +    }
>> +}
>> +
>> +#[pinned_drop]
>> +impl<T: ForeignOwnable> PinnedDrop for XArray<T> {
>> +    fn drop(self: Pin<&mut Self>) {
>> +        let mut index: core::ffi::c_ulong = 0;
>> +        let mut entry;
>> +
>> +        // SAFETY: `self.xa` is valid by the type invariant, and as we have
>> +        // the only reference to the `XArray` we can safely iterate its contents
>> +        // and drop everything.
> 
> The second part is not needed? Since `xa_find` will take the lock.
> 

^ permalink raw reply	[flat|nested] 7+ messages in thread

end of thread, other threads:[~2024-02-09 21:14 UTC | newest]

Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2024-01-16 15:06 [PATCH v6] rust: xarray: Add an abstraction for XArray Maíra Canal
2024-01-16 23:53 ` Boqun Feng
2024-02-05 10:29   ` Andreas Hindborg (Samsung)
2024-02-09 12:12   ` Alice Ryhl
2024-02-01 10:48 ` Benno Lossin
2024-02-09 21:14   ` Maíra Canal
2024-02-09 12:44 ` Alice Ryhl

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).