Add an Entry API for XArray that provides ergonomic access to array
slots that may be vacant or occupied. The API follows the pattern of
Rust's standard library HashMap entry API, allowing efficient
conditional insertion and modification of entries.
The implementation uses the XArray state API (`xas_*` functions) for
efficient operations without requiring multiple lookups. Helper
functions are added to rust/helpers/xarray.c to wrap C macros that are
not directly accessible from Rust.
Also update MAINTAINERS to cover the new rust files.
Signed-off-by: Andreas Hindborg <a.hindborg@kernel.org>
---
MAINTAINERS | 1 +
rust/helpers/xarray.c | 17 ++
rust/kernel/xarray.rs | 112 +++++++++++++
rust/kernel/xarray/entry.rs | 376 ++++++++++++++++++++++++++++++++++++++++++++
4 files changed, 506 insertions(+)
diff --git a/MAINTAINERS b/MAINTAINERS
index e8f06145fb54c..79d4c9c9b2b63 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -27909,6 +27909,7 @@ B: https://github.com/Rust-for-Linux/linux/issues
C: https://rust-for-linux.zulipchat.com
T: git https://github.com/Rust-for-Linux/linux.git xarray-next
F: rust/kernel/xarray.rs
+F: rust/kernel/xarray/
XBOX DVD IR REMOTE
M: Benjamin Valentin <benpicco@googlemail.com>
diff --git a/rust/helpers/xarray.c b/rust/helpers/xarray.c
index 60b299f11451d..425a6cc494734 100644
--- a/rust/helpers/xarray.c
+++ b/rust/helpers/xarray.c
@@ -26,3 +26,20 @@ void rust_helper_xa_unlock(struct xarray *xa)
{
return xa_unlock(xa);
}
+
+void *rust_helper_xas_result(struct xa_state *xas, void *curr)
+{
+ if (xa_err(xas->xa_node))
+ curr = xas->xa_node;
+ return curr;
+}
+
+void *rust_helper_xa_zero_to_null(void *entry)
+{
+ return xa_is_zero(entry) ? NULL : entry;
+}
+
+int rust_helper_xas_error(const struct xa_state *xas)
+{
+ return xas_error(xas);
+}
diff --git a/rust/kernel/xarray.rs b/rust/kernel/xarray.rs
index 9d4589979fd1d..2b8d56c81e36b 100644
--- a/rust/kernel/xarray.rs
+++ b/rust/kernel/xarray.rs
@@ -13,11 +13,17 @@
NonNull, //
},
};
+pub use entry::{
+ Entry,
+ OccupiedEntry,
+ VacantEntry, //
+};
use kernel::{
alloc,
bindings,
build_assert, //
error::{
+ to_result,
Error,
Result, //
},
@@ -255,6 +261,35 @@ pub fn get_mut(&mut self, index: usize) -> Option<T::BorrowedMut<'_>> {
Some(unsafe { T::borrow_mut(ptr.as_ptr()) })
}
+ /// Gets an entry for the specified index, which can be vacant or occupied.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// # use kernel::{prelude::*, xarray::{AllocKind, XArray, Entry}};
+ /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
+ /// let mut guard = xa.lock();
+ ///
+ /// assert_eq!(guard.contains_index(42), false);
+ ///
+ /// match guard.get_entry(42) {
+ /// Entry::Vacant(entry) => {
+ /// entry.insert(KBox::new(0x1337u32, GFP_KERNEL)?)?;
+ /// }
+ /// Entry::Occupied(_) => unreachable!("We did not insert an entry yet"),
+ /// }
+ ///
+ /// assert_eq!(guard.get(42), Some(&0x1337));
+ ///
+ /// # Ok::<(), kernel::error::Error>(())
+ /// ```
+ pub fn get_entry<'b>(&'b mut self, index: usize) -> Entry<'a, 'b, T> {
+ match self.load(index) {
+ None => Entry::Vacant(VacantEntry::new(self, index)),
+ Some(ptr) => Entry::Occupied(OccupiedEntry::new(self, index, ptr)),
+ }
+ }
+
fn load_next(&self, index: usize) -> Option<(usize, NonNull<c_void>)> {
let mut state = XArrayState::new(self, index);
// SAFETY: `state.state` is always valid by the type invariant of
@@ -320,6 +355,76 @@ pub fn find_next_mut(&mut self, index: usize) -> Option<(usize, T::BorrowedMut<'
.map(move |(index, ptr)| (index, unsafe { T::borrow_mut(ptr.as_ptr()) }))
}
+ /// Finds the next occupied entry starting from the given index.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// # use kernel::{prelude::*, xarray::{AllocKind, XArray}};
+ /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
+ /// let mut guard = xa.lock();
+ ///
+ /// guard.store(10, KBox::new(10u32, GFP_KERNEL)?, GFP_KERNEL)?;
+ /// guard.store(20, KBox::new(20u32, GFP_KERNEL)?, GFP_KERNEL)?;
+ ///
+ /// if let Some(entry) = guard.find_next_entry(5) {
+ /// assert_eq!(entry.index(), 10);
+ /// let value = entry.remove();
+ /// assert_eq!(*value, 10);
+ /// }
+ ///
+ /// assert_eq!(guard.get(10), None);
+ ///
+ /// # Ok::<(), kernel::error::Error>(())
+ /// ```
+ pub fn find_next_entry<'b>(&'b mut self, index: usize) -> Option<OccupiedEntry<'a, 'b, T>> {
+ let mut state = XArrayState::new(self, index);
+
+ // SAFETY: `state.state` is properly initialized by XArrayState::new and the caller holds
+ // the lock.
+ let ptr = NonNull::new(unsafe { bindings::xas_find(&mut state.state, usize::MAX) })?;
+
+ Some(OccupiedEntry { state, ptr })
+ }
+
+ /// Finds the next occupied entry starting at the given index, wrapping around.
+ ///
+ /// Searches for an entry starting at `index` up to the maximum index. If no entry
+ /// is found, wraps around and searches from index 0 up to `index`.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// # use kernel::{prelude::*, xarray::{AllocKind, XArray}};
+ /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
+ /// let mut guard = xa.lock();
+ ///
+ /// guard.store(100, KBox::new(42u32, GFP_KERNEL)?, GFP_KERNEL)?;
+ /// let entry = guard.find_next_entry_circular(101);
+ /// assert_eq!(entry.map(|e| e.index()), Some(100));
+ ///
+ /// # Ok::<(), kernel::error::Error>(())
+ /// ```
+ pub fn find_next_entry_circular<'b>(
+ &'b mut self,
+ index: usize,
+ ) -> Option<OccupiedEntry<'a, 'b, T>> {
+ let mut state = XArrayState::new(self, index);
+
+ // SAFETY: `state.state` is properly initialized by XArrayState::new and the caller holds
+ // the lock.
+ let ptr = NonNull::new(unsafe { bindings::xas_find(&mut state.state, usize::MAX) })
+ .or_else(|| {
+ state.state.xa_node = bindings::XAS_RESTART as *mut bindings::xa_node;
+ state.state.xa_index = 0;
+ // SAFETY: `state.state` is properly initialized and by type invariant, we hold the
+ // xarray lock.
+ NonNull::new(unsafe { bindings::xas_find(&mut state.state, index) })
+ })?;
+
+ Some(OccupiedEntry { state, ptr })
+ }
+
/// Removes and returns the element at the given index.
pub fn remove(&mut self, index: usize) -> Option<T> {
// SAFETY:
@@ -416,8 +521,15 @@ fn new(access: &'b Guard<'a, T>, index: usize) -> Self {
},
}
}
+
+ fn status(&self) -> Result {
+ // SAFETY: `self.state` is properly initialized and valid.
+ to_result(unsafe { bindings::xas_error(&self.state) })
+ }
}
+mod entry;
+
// SAFETY: `XArray<T>` has no shared mutable state so it is `Send` iff `T` is `Send`.
unsafe impl<T: ForeignOwnable + Send> Send for XArray<T> {}
diff --git a/rust/kernel/xarray/entry.rs b/rust/kernel/xarray/entry.rs
new file mode 100644
index 0000000000000..1268dc35bac58
--- /dev/null
+++ b/rust/kernel/xarray/entry.rs
@@ -0,0 +1,376 @@
+// SPDX-License-Identifier: GPL-2.0
+
+use super::{
+ Guard,
+ StoreError,
+ XArrayState, //
+};
+use core::ptr::NonNull;
+use kernel::{
+ prelude::*,
+ types::ForeignOwnable, //
+};
+
+/// Represents either a vacant or occupied entry in an XArray.
+pub enum Entry<'a, 'b, T: ForeignOwnable> {
+ /// A vacant entry that can have a value inserted.
+ Vacant(VacantEntry<'a, 'b, T>),
+ /// An occupied entry containing a value.
+ Occupied(OccupiedEntry<'a, 'b, T>),
+}
+
+impl<T: ForeignOwnable> Entry<'_, '_, T> {
+ /// Returns true if this entry is occupied.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// # use kernel::{prelude::*, xarray::{AllocKind, XArray, Entry}};
+ /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
+ /// let mut guard = xa.lock();
+ ///
+ ///
+ /// let entry = guard.get_entry(42);
+ /// assert_eq!(entry.is_occupied(), false);
+ ///
+ /// guard.store(42, KBox::new(0x1337u32, GFP_KERNEL)?, GFP_KERNEL)?;
+ /// let entry = guard.get_entry(42);
+ /// assert_eq!(entry.is_occupied(), true);
+ ///
+ /// # Ok::<(), kernel::error::Error>(())
+ /// ```
+ pub fn is_occupied(&self) -> bool {
+ matches!(self, Entry::Occupied(_))
+ }
+}
+
+/// A view into a vacant entry in an XArray.
+pub struct VacantEntry<'a, 'b, T: ForeignOwnable> {
+ state: XArrayState<'a, 'b, T>,
+}
+
+impl<'a, 'b, T> VacantEntry<'a, 'b, T>
+where
+ T: ForeignOwnable,
+{
+ pub(crate) fn new(guard: &'b mut Guard<'a, T>, index: usize) -> Self {
+ Self {
+ state: XArrayState::new(guard, index),
+ }
+ }
+
+ fn insert_internal(&mut self, value: T) -> Result<*mut c_void, StoreError<T>> {
+ let new = T::into_foreign(value).cast();
+
+ // SAFETY: `self.state.state` is properly initialized and `new` came from `T::into_foreign`.
+ // We hold the xarray lock.
+ unsafe { bindings::xas_store(&mut self.state.state, new) };
+
+ self.state.status().map(|()| new).map_err(|error| {
+ // SAFETY: `new` came from `T::into_foreign` and `xas_store` does not take ownership of
+ // the value on error.
+ let value = unsafe { T::from_foreign(new) };
+ StoreError { value, error }
+ })
+ }
+
+ /// Inserts a value into this vacant entry.
+ ///
+ /// Returns a reference to the newly inserted value.
+ ///
+ /// - This method will fail if the nodes on the path to the index
+ /// represented by this entry are not present in the XArray.
+ /// - This method will not drop the XArray lock.
+ ///
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// # use kernel::{prelude::*, xarray::{AllocKind, XArray, Entry}};
+ /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
+ /// let mut guard = xa.lock();
+ ///
+ /// assert_eq!(guard.get(42), None);
+ ///
+ /// if let Entry::Vacant(entry) = guard.get_entry(42) {
+ /// let value = KBox::new(0x1337u32, GFP_KERNEL)?;
+ /// let borrowed = entry.insert(value)?;
+ /// assert_eq!(*borrowed, 0x1337);
+ /// }
+ ///
+ /// assert_eq!(guard.get(42).copied(), Some(0x1337));
+ ///
+ /// # Ok::<(), kernel::error::Error>(())
+ /// ```
+ pub fn insert(mut self, value: T) -> Result<T::BorrowedMut<'b>, StoreError<T>> {
+ let new = self.insert_internal(value)?;
+
+ // SAFETY: `new` came from `T::into_foreign`. The entry has exclusive
+ // ownership of `new` as it holds a mutable reference to `Guard`.
+ Ok(unsafe { T::borrow_mut(new) })
+ }
+
+ /// Inserts a value and returns an occupied entry representing the newly inserted value.
+ ///
+ /// - This method will fail if the nodes on the path to the index
+ /// represented by this entry are not present in the XArray.
+ /// - This method will not drop the XArray lock.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// # use kernel::{prelude::*, xarray::{AllocKind, XArray, Entry}};
+ /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
+ /// let mut guard = xa.lock();
+ ///
+ /// assert_eq!(guard.get(42), None);
+ ///
+ /// if let Entry::Vacant(entry) = guard.get_entry(42) {
+ /// let value = KBox::new(0x1337u32, GFP_KERNEL)?;
+ /// let occupied = entry.insert_entry(value)?;
+ /// assert_eq!(occupied.index(), 42);
+ /// }
+ ///
+ /// assert_eq!(guard.get(42).copied(), Some(0x1337));
+ ///
+ /// # Ok::<(), kernel::error::Error>(())
+ /// ```
+ pub fn insert_entry(mut self, value: T) -> Result<OccupiedEntry<'a, 'b, T>, StoreError<T>> {
+ let new = self.insert_internal(value)?;
+
+ Ok(OccupiedEntry::<'a, 'b, T> {
+ state: self.state,
+ // SAFETY: `new` came from `T::into_foreign` and is guaranteed non-null.
+ ptr: unsafe { core::ptr::NonNull::new_unchecked(new) },
+ })
+ }
+
+ /// Returns the index of this vacant entry.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// # use kernel::{prelude::*, xarray::{AllocKind, XArray, Entry}};
+ /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
+ /// let mut guard = xa.lock();
+ ///
+ /// assert_eq!(guard.get(42), None);
+ ///
+ /// if let Entry::Vacant(entry) = guard.get_entry(42) {
+ /// assert_eq!(entry.index(), 42);
+ /// }
+ ///
+ /// # Ok::<(), kernel::error::Error>(())
+ /// ```
+ pub fn index(&self) -> usize {
+ self.state.state.xa_index
+ }
+}
+
+/// A view into an occupied entry in an XArray.
+pub struct OccupiedEntry<'a, 'b, T: ForeignOwnable> {
+ pub(crate) state: XArrayState<'a, 'b, T>,
+ pub(crate) ptr: NonNull<c_void>,
+}
+
+impl<'a, 'b, T> OccupiedEntry<'a, 'b, T>
+where
+ T: ForeignOwnable,
+{
+ pub(crate) fn new(guard: &'b mut Guard<'a, T>, index: usize, ptr: NonNull<c_void>) -> Self {
+ Self {
+ state: XArrayState::new(guard, index),
+ ptr,
+ }
+ }
+
+ /// Removes the value from this occupied entry and returns it, consuming the entry.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// # use kernel::{prelude::*, xarray::{AllocKind, XArray, Entry}};
+ /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
+ /// let mut guard = xa.lock();
+ ///
+ /// guard.store(42, KBox::new(0x1337u32, GFP_KERNEL)?, GFP_KERNEL)?;
+ /// assert_eq!(guard.get(42).copied(), Some(0x1337));
+ ///
+ /// if let Entry::Occupied(entry) = guard.get_entry(42) {
+ /// let value = entry.remove();
+ /// assert_eq!(*value, 0x1337);
+ /// }
+ ///
+ /// assert_eq!(guard.get(42), None);
+ ///
+ /// # Ok::<(), kernel::error::Error>(())
+ /// ```
+ pub fn remove(mut self) -> T {
+ // NOTE: Storing NULL to an occupied slot never fails.
+ // SAFETY: `self.state.state` is properly initialized and valid for XAS operations.
+ let ptr = unsafe {
+ bindings::xas_result(
+ &mut self.state.state,
+ bindings::xa_zero_to_null(bindings::xas_store(
+ &mut self.state.state,
+ core::ptr::null_mut(),
+ )),
+ )
+ };
+
+ // SAFETY: `ptr` is a valid return value from xas_result.
+ let errno = unsafe { bindings::xa_err(ptr) };
+ debug_assert!(errno == 0);
+
+ // SAFETY:
+ // - `ptr` came from `T::into_foreign`.
+ // - As this method takes self by value, the lifetimes of any [`T::Borrowed`] and
+ // [`T::BorrowedMut`] we have created must have ended.
+ unsafe { T::from_foreign(ptr.cast()) }
+ }
+
+ /// Returns the index of this occupied entry.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// # use kernel::{prelude::*, xarray::{AllocKind, XArray, Entry}};
+ /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
+ /// let mut guard = xa.lock();
+ ///
+ /// guard.store(42, KBox::new(0x1337u32, GFP_KERNEL)?, GFP_KERNEL)?;
+ ///
+ /// if let Entry::Occupied(entry) = guard.get_entry(42) {
+ /// assert_eq!(entry.index(), 42);
+ /// }
+ ///
+ /// # Ok::<(), kernel::error::Error>(())
+ /// ```
+ pub fn index(&self) -> usize {
+ self.state.state.xa_index
+ }
+
+ /// Replaces the value in this occupied entry and returns the old value.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// # use kernel::{prelude::*, xarray::{AllocKind, XArray, Entry}};
+ /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
+ /// let mut guard = xa.lock();
+ ///
+ /// guard.store(42, KBox::new(0x1337u32, GFP_KERNEL)?, GFP_KERNEL)?;
+ ///
+ /// if let Entry::Occupied(mut entry) = guard.get_entry(42) {
+ /// let new_value = KBox::new(0x9999u32, GFP_KERNEL)?;
+ /// let old_value = entry.insert(new_value);
+ /// assert_eq!(*old_value, 0x1337);
+ /// }
+ ///
+ /// assert_eq!(guard.get(42).copied(), Some(0x9999));
+ ///
+ /// # Ok::<(), kernel::error::Error>(())
+ /// ```
+ pub fn insert(&mut self, value: T) -> T {
+ // NOTE: Storing to an occupied slot never fails.
+ let new = T::into_foreign(value).cast();
+ // SAFETY: `new` came from `T::into_foreign` and is guaranteed non-null.
+ self.ptr = unsafe { NonNull::new_unchecked(new) };
+
+ // SAFETY: `self.state.state` is properly initialized and valid for XAS operations.
+ let old = unsafe {
+ bindings::xas_result(
+ &mut self.state.state,
+ bindings::xa_zero_to_null(bindings::xas_store(&mut self.state.state, new)),
+ )
+ };
+
+ // SAFETY: `old` is a valid return value from xas_result.
+ let errno = unsafe { bindings::xa_err(old) };
+ debug_assert!(errno == 0);
+
+ // SAFETY:
+ // - `ptr` came from `T::into_foreign`.
+ // - As this method takes self by value, the lifetimes of any [`T::Borrowed`] and
+ // [`T::BorrowedMut`] we have created must have ended.
+ unsafe { T::from_foreign(old) }
+ }
+
+ /// Converts this occupied entry into a mutable reference to the value in the slot represented
+ /// by the entry.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// # use kernel::{prelude::*, xarray::{AllocKind, XArray, Entry}};
+ /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
+ /// let mut guard = xa.lock();
+ ///
+ /// guard.store(42, KBox::new(0x1337u32, GFP_KERNEL)?, GFP_KERNEL)?;
+ ///
+ /// if let Entry::Occupied(entry) = guard.get_entry(42) {
+ /// let value_ref = entry.into_mut();
+ /// *value_ref = 0x9999;
+ /// }
+ ///
+ /// assert_eq!(guard.get(42).copied(), Some(0x9999));
+ ///
+ /// # Ok::<(), kernel::error::Error>(())
+ /// ```
+ pub fn into_mut(self) -> T::BorrowedMut<'b> {
+ // SAFETY: `ptr` came from `T::into_foreign`.
+ unsafe { T::borrow_mut(self.ptr.as_ptr()) }
+ }
+
+ /// Swaps the value in this entry with the provided value.
+ ///
+ /// Returns the old value that was in the entry.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// # use kernel::{prelude::*, xarray::{AllocKind, XArray, Entry}};
+ /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
+ /// let mut guard = xa.lock();
+ ///
+ /// guard.store(42, KBox::new(100u32, GFP_KERNEL)?, GFP_KERNEL)?;
+ ///
+ /// if let Entry::Occupied(mut entry) = guard.get_entry(42) {
+ /// let old_value = entry.swap(200u32);
+ /// assert_eq!(old_value, 100);
+ /// assert_eq!(*entry, 200);
+ /// }
+ ///
+ /// # Ok::<(), kernel::error::Error>(())
+ /// ```
+ pub fn swap<U>(&mut self, mut other: U) -> U
+ where
+ T: for<'c> ForeignOwnable<Borrowed<'c> = &'c U, BorrowedMut<'c> = &'c mut U>,
+ {
+ use core::ops::DerefMut;
+ core::mem::swap(self.deref_mut(), &mut other);
+ other
+ }
+}
+
+impl<T, U> core::ops::Deref for OccupiedEntry<'_, '_, T>
+where
+ T: for<'a> ForeignOwnable<Borrowed<'a> = &'a U, BorrowedMut<'a> = &'a mut U>,
+{
+ type Target = U;
+
+ fn deref(&self) -> &Self::Target {
+ // SAFETY: `ptr` came from `T::into_foreign`.
+ unsafe { T::borrow(self.ptr.as_ptr()) }
+ }
+}
+
+impl<T, U> core::ops::DerefMut for OccupiedEntry<'_, '_, T>
+where
+ T: for<'a> ForeignOwnable<Borrowed<'a> = &'a U, BorrowedMut<'a> = &'a mut U>,
+{
+ fn deref_mut(&mut self) -> &mut Self::Target {
+ // SAFETY: `ptr` came from `T::into_foreign`.
+ unsafe { T::borrow_mut(self.ptr.as_ptr()) }
+ }
+}
--
2.51.2On Wed, Dec 3, 2025 at 5:27 PM Andreas Hindborg <a.hindborg@kernel.org> wrote:
>
> Add an Entry API for XArray that provides ergonomic access to array
> slots that may be vacant or occupied. The API follows the pattern of
> Rust's standard library HashMap entry API, allowing efficient
> conditional insertion and modification of entries.
>
> The implementation uses the XArray state API (`xas_*` functions) for
> efficient operations without requiring multiple lookups. Helper
> functions are added to rust/helpers/xarray.c to wrap C macros that are
> not directly accessible from Rust.
>
> Also update MAINTAINERS to cover the new rust files.
>
> Signed-off-by: Andreas Hindborg <a.hindborg@kernel.org>
> ---
> MAINTAINERS | 1 +
> rust/helpers/xarray.c | 17 ++
> rust/kernel/xarray.rs | 112 +++++++++++++
> rust/kernel/xarray/entry.rs | 376 ++++++++++++++++++++++++++++++++++++++++++++
> 4 files changed, 506 insertions(+)
>
> diff --git a/MAINTAINERS b/MAINTAINERS
> index e8f06145fb54c..79d4c9c9b2b63 100644
> --- a/MAINTAINERS
> +++ b/MAINTAINERS
> @@ -27909,6 +27909,7 @@ B: https://github.com/Rust-for-Linux/linux/issues
> C: https://rust-for-linux.zulipchat.com
> T: git https://github.com/Rust-for-Linux/linux.git xarray-next
> F: rust/kernel/xarray.rs
> +F: rust/kernel/xarray/
>
> XBOX DVD IR REMOTE
> M: Benjamin Valentin <benpicco@googlemail.com>
> diff --git a/rust/helpers/xarray.c b/rust/helpers/xarray.c
> index 60b299f11451d..425a6cc494734 100644
> --- a/rust/helpers/xarray.c
> +++ b/rust/helpers/xarray.c
> @@ -26,3 +26,20 @@ void rust_helper_xa_unlock(struct xarray *xa)
> {
> return xa_unlock(xa);
> }
> +
> +void *rust_helper_xas_result(struct xa_state *xas, void *curr)
> +{
> + if (xa_err(xas->xa_node))
> + curr = xas->xa_node;
> + return curr;
> +}
Instead of this duplication, can we expose `xas_result` from the header?
> +
> +void *rust_helper_xa_zero_to_null(void *entry)
> +{
> + return xa_is_zero(entry) ? NULL : entry;
> +}
> +
> +int rust_helper_xas_error(const struct xa_state *xas)
> +{
> + return xas_error(xas);
> +}
> diff --git a/rust/kernel/xarray.rs b/rust/kernel/xarray.rs
> index 9d4589979fd1d..2b8d56c81e36b 100644
> --- a/rust/kernel/xarray.rs
> +++ b/rust/kernel/xarray.rs
> @@ -13,11 +13,17 @@
> NonNull, //
> },
> };
> +pub use entry::{
> + Entry,
> + OccupiedEntry,
> + VacantEntry, //
> +};
> use kernel::{
> alloc,
> bindings,
> build_assert, //
> error::{
> + to_result,
> Error,
> Result, //
> },
> @@ -255,6 +261,35 @@ pub fn get_mut(&mut self, index: usize) -> Option<T::BorrowedMut<'_>> {
> Some(unsafe { T::borrow_mut(ptr.as_ptr()) })
> }
>
> + /// Gets an entry for the specified index, which can be vacant or occupied.
> + ///
> + /// # Examples
> + ///
> + /// ```
> + /// # use kernel::{prelude::*, xarray::{AllocKind, XArray, Entry}};
> + /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
> + /// let mut guard = xa.lock();
> + ///
> + /// assert_eq!(guard.contains_index(42), false);
> + ///
> + /// match guard.get_entry(42) {
> + /// Entry::Vacant(entry) => {
> + /// entry.insert(KBox::new(0x1337u32, GFP_KERNEL)?)?;
> + /// }
> + /// Entry::Occupied(_) => unreachable!("We did not insert an entry yet"),
> + /// }
> + ///
> + /// assert_eq!(guard.get(42), Some(&0x1337));
> + ///
> + /// # Ok::<(), kernel::error::Error>(())
> + /// ```
> + pub fn get_entry<'b>(&'b mut self, index: usize) -> Entry<'a, 'b, T> {
> + match self.load(index) {
> + None => Entry::Vacant(VacantEntry::new(self, index)),
> + Some(ptr) => Entry::Occupied(OccupiedEntry::new(self, index, ptr)),
> + }
> + }
Why not "entry" like the stdlib collections?
> +
> fn load_next(&self, index: usize) -> Option<(usize, NonNull<c_void>)> {
> let mut state = XArrayState::new(self, index);
> // SAFETY: `state.state` is always valid by the type invariant of
> @@ -320,6 +355,76 @@ pub fn find_next_mut(&mut self, index: usize) -> Option<(usize, T::BorrowedMut<'
> .map(move |(index, ptr)| (index, unsafe { T::borrow_mut(ptr.as_ptr()) }))
> }
>
> + /// Finds the next occupied entry starting from the given index.
> + ///
> + /// # Examples
> + ///
> + /// ```
> + /// # use kernel::{prelude::*, xarray::{AllocKind, XArray}};
> + /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
> + /// let mut guard = xa.lock();
> + ///
> + /// guard.store(10, KBox::new(10u32, GFP_KERNEL)?, GFP_KERNEL)?;
> + /// guard.store(20, KBox::new(20u32, GFP_KERNEL)?, GFP_KERNEL)?;
> + ///
> + /// if let Some(entry) = guard.find_next_entry(5) {
> + /// assert_eq!(entry.index(), 10);
> + /// let value = entry.remove();
> + /// assert_eq!(*value, 10);
> + /// }
> + ///
> + /// assert_eq!(guard.get(10), None);
> + ///
> + /// # Ok::<(), kernel::error::Error>(())
> + /// ```
> + pub fn find_next_entry<'b>(&'b mut self, index: usize) -> Option<OccupiedEntry<'a, 'b, T>> {
> + let mut state = XArrayState::new(self, index);
> +
> + // SAFETY: `state.state` is properly initialized by XArrayState::new and the caller holds
> + // the lock.
> + let ptr = NonNull::new(unsafe { bindings::xas_find(&mut state.state, usize::MAX) })?;
> +
> + Some(OccupiedEntry { state, ptr })
> + }
I'm surprised this doesn't share code with find_next_mut. Can it?
Again, I'd have expected the bulk of the logic to be on XArrayState.
> +
> + /// Finds the next occupied entry starting at the given index, wrapping around.
> + ///
> + /// Searches for an entry starting at `index` up to the maximum index. If no entry
> + /// is found, wraps around and searches from index 0 up to `index`.
> + ///
> + /// # Examples
> + ///
> + /// ```
> + /// # use kernel::{prelude::*, xarray::{AllocKind, XArray}};
> + /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
> + /// let mut guard = xa.lock();
> + ///
> + /// guard.store(100, KBox::new(42u32, GFP_KERNEL)?, GFP_KERNEL)?;
> + /// let entry = guard.find_next_entry_circular(101);
> + /// assert_eq!(entry.map(|e| e.index()), Some(100));
> + ///
> + /// # Ok::<(), kernel::error::Error>(())
> + /// ```
> + pub fn find_next_entry_circular<'b>(
> + &'b mut self,
> + index: usize,
> + ) -> Option<OccupiedEntry<'a, 'b, T>> {
> + let mut state = XArrayState::new(self, index);
> +
> + // SAFETY: `state.state` is properly initialized by XArrayState::new and the caller holds
> + // the lock.
> + let ptr = NonNull::new(unsafe { bindings::xas_find(&mut state.state, usize::MAX) })
> + .or_else(|| {
> + state.state.xa_node = bindings::XAS_RESTART as *mut bindings::xa_node;
> + state.state.xa_index = 0;
> + // SAFETY: `state.state` is properly initialized and by type invariant, we hold the
> + // xarray lock.
> + NonNull::new(unsafe { bindings::xas_find(&mut state.state, index) })
> + })?;
> +
> + Some(OccupiedEntry { state, ptr })
> + }
Instead of this function, can find_next_entry take a Range? Then it
would be simple for the caller to wrap if they want, without bloating
this API.
> +
> /// Removes and returns the element at the given index.
> pub fn remove(&mut self, index: usize) -> Option<T> {
> // SAFETY:
> @@ -416,8 +521,15 @@ fn new(access: &'b Guard<'a, T>, index: usize) -> Self {
> },
> }
> }
> +
> + fn status(&self) -> Result {
> + // SAFETY: `self.state` is properly initialized and valid.
> + to_result(unsafe { bindings::xas_error(&self.state) })
> + }
> }
>
> +mod entry;
> +
> // SAFETY: `XArray<T>` has no shared mutable state so it is `Send` iff `T` is `Send`.
> unsafe impl<T: ForeignOwnable + Send> Send for XArray<T> {}
>
> diff --git a/rust/kernel/xarray/entry.rs b/rust/kernel/xarray/entry.rs
> new file mode 100644
> index 0000000000000..1268dc35bac58
> --- /dev/null
> +++ b/rust/kernel/xarray/entry.rs
> @@ -0,0 +1,376 @@
> +// SPDX-License-Identifier: GPL-2.0
> +
> +use super::{
> + Guard,
> + StoreError,
> + XArrayState, //
> +};
> +use core::ptr::NonNull;
> +use kernel::{
> + prelude::*,
> + types::ForeignOwnable, //
> +};
> +
> +/// Represents either a vacant or occupied entry in an XArray.
> +pub enum Entry<'a, 'b, T: ForeignOwnable> {
> + /// A vacant entry that can have a value inserted.
> + Vacant(VacantEntry<'a, 'b, T>),
> + /// An occupied entry containing a value.
> + Occupied(OccupiedEntry<'a, 'b, T>),
> +}
> +
> +impl<T: ForeignOwnable> Entry<'_, '_, T> {
> + /// Returns true if this entry is occupied.
> + ///
> + /// # Examples
> + ///
> + /// ```
> + /// # use kernel::{prelude::*, xarray::{AllocKind, XArray, Entry}};
> + /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
> + /// let mut guard = xa.lock();
> + ///
> + ///
> + /// let entry = guard.get_entry(42);
> + /// assert_eq!(entry.is_occupied(), false);
> + ///
> + /// guard.store(42, KBox::new(0x1337u32, GFP_KERNEL)?, GFP_KERNEL)?;
> + /// let entry = guard.get_entry(42);
> + /// assert_eq!(entry.is_occupied(), true);
> + ///
> + /// # Ok::<(), kernel::error::Error>(())
> + /// ```
> + pub fn is_occupied(&self) -> bool {
> + matches!(self, Entry::Occupied(_))
> + }
Do we need this? IMO less is more, and even stdlib doesn't have this.
> +}
> +
> +/// A view into a vacant entry in an XArray.
> +pub struct VacantEntry<'a, 'b, T: ForeignOwnable> {
> + state: XArrayState<'a, 'b, T>,
> +}
> +
> +impl<'a, 'b, T> VacantEntry<'a, 'b, T>
> +where
> + T: ForeignOwnable,
> +{
> + pub(crate) fn new(guard: &'b mut Guard<'a, T>, index: usize) -> Self {
> + Self {
> + state: XArrayState::new(guard, index),
> + }
> + }
> +
> + fn insert_internal(&mut self, value: T) -> Result<*mut c_void, StoreError<T>> {
> + let new = T::into_foreign(value).cast();
> +
> + // SAFETY: `self.state.state` is properly initialized and `new` came from `T::into_foreign`.
> + // We hold the xarray lock.
> + unsafe { bindings::xas_store(&mut self.state.state, new) };
Can this please be on XArray?
> +
> + self.state.status().map(|()| new).map_err(|error| {
> + // SAFETY: `new` came from `T::into_foreign` and `xas_store` does not take ownership of
> + // the value on error.
> + let value = unsafe { T::from_foreign(new) };
> + StoreError { value, error }
> + })
> + }
> +
> + /// Inserts a value into this vacant entry.
> + ///
> + /// Returns a reference to the newly inserted value.
> + ///
> + /// - This method will fail if the nodes on the path to the index
> + /// represented by this entry are not present in the XArray.
> + /// - This method will not drop the XArray lock.
> + ///
> + ///
> + /// # Examples
> + ///
> + /// ```
> + /// # use kernel::{prelude::*, xarray::{AllocKind, XArray, Entry}};
> + /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
> + /// let mut guard = xa.lock();
> + ///
> + /// assert_eq!(guard.get(42), None);
> + ///
> + /// if let Entry::Vacant(entry) = guard.get_entry(42) {
> + /// let value = KBox::new(0x1337u32, GFP_KERNEL)?;
> + /// let borrowed = entry.insert(value)?;
> + /// assert_eq!(*borrowed, 0x1337);
> + /// }
> + ///
> + /// assert_eq!(guard.get(42).copied(), Some(0x1337));
> + ///
> + /// # Ok::<(), kernel::error::Error>(())
> + /// ```
> + pub fn insert(mut self, value: T) -> Result<T::BorrowedMut<'b>, StoreError<T>> {
> + let new = self.insert_internal(value)?;
> +
> + // SAFETY: `new` came from `T::into_foreign`.The entry has exclusive
This is knowledge at a distance. There's no comment anywhere that
promises that insert_internal called T::into_foreign.
> + // ownership of `new` as it holds a mutable reference to `Guard`.
> + Ok(unsafe { T::borrow_mut(new) })
> + }
> +
> + /// Inserts a value and returns an occupied entry representing the newly inserted value.
> + ///
> + /// - This method will fail if the nodes on the path to the index
> + /// represented by this entry are not present in the XArray.
> + /// - This method will not drop the XArray lock.
> + ///
> + /// # Examples
> + ///
> + /// ```
> + /// # use kernel::{prelude::*, xarray::{AllocKind, XArray, Entry}};
> + /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
> + /// let mut guard = xa.lock();
> + ///
> + /// assert_eq!(guard.get(42), None);
> + ///
> + /// if let Entry::Vacant(entry) = guard.get_entry(42) {
> + /// let value = KBox::new(0x1337u32, GFP_KERNEL)?;
> + /// let occupied = entry.insert_entry(value)?;
> + /// assert_eq!(occupied.index(), 42);
> + /// }
> + ///
> + /// assert_eq!(guard.get(42).copied(), Some(0x1337));
> + ///
> + /// # Ok::<(), kernel::error::Error>(())
> + /// ```
> + pub fn insert_entry(mut self, value: T) -> Result<OccupiedEntry<'a, 'b, T>, StoreError<T>> {
> + let new = self.insert_internal(value)?;
> +
> + Ok(OccupiedEntry::<'a, 'b, T> {
> + state: self.state,
> + // SAFETY: `new` came from `T::into_foreign` and is guaranteed non-null.
Same.
> + ptr: unsafe { core::ptr::NonNull::new_unchecked(new) },
> + })
> + }
> +
> + /// Returns the index of this vacant entry.
> + ///
> + /// # Examples
> + ///
> + /// ```
> + /// # use kernel::{prelude::*, xarray::{AllocKind, XArray, Entry}};
> + /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
> + /// let mut guard = xa.lock();
> + ///
> + /// assert_eq!(guard.get(42), None);
> + ///
> + /// if let Entry::Vacant(entry) = guard.get_entry(42) {
> + /// assert_eq!(entry.index(), 42);
> + /// }
> + ///
> + /// # Ok::<(), kernel::error::Error>(())
> + /// ```
> + pub fn index(&self) -> usize {
> + self.state.state.xa_index
> + }
> +}
> +
> +/// A view into an occupied entry in an XArray.
> +pub struct OccupiedEntry<'a, 'b, T: ForeignOwnable> {
> + pub(crate) state: XArrayState<'a, 'b, T>,
> + pub(crate) ptr: NonNull<c_void>,
> +}
> +
> +impl<'a, 'b, T> OccupiedEntry<'a, 'b, T>
> +where
> + T: ForeignOwnable,
> +{
> + pub(crate) fn new(guard: &'b mut Guard<'a, T>, index: usize, ptr: NonNull<c_void>) -> Self {
> + Self {
> + state: XArrayState::new(guard, index),
> + ptr,
> + }
> + }
> +
> + /// Removes the value from this occupied entry and returns it, consuming the entry.
> + ///
> + /// # Examples
> + ///
> + /// ```
> + /// # use kernel::{prelude::*, xarray::{AllocKind, XArray, Entry}};
> + /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
> + /// let mut guard = xa.lock();
> + ///
> + /// guard.store(42, KBox::new(0x1337u32, GFP_KERNEL)?, GFP_KERNEL)?;
> + /// assert_eq!(guard.get(42).copied(), Some(0x1337));
> + ///
> + /// if let Entry::Occupied(entry) = guard.get_entry(42) {
> + /// let value = entry.remove();
> + /// assert_eq!(*value, 0x1337);
> + /// }
> + ///
> + /// assert_eq!(guard.get(42), None);
> + ///
> + /// # Ok::<(), kernel::error::Error>(())
> + /// ```
> + pub fn remove(mut self) -> T {
> + // NOTE: Storing NULL to an occupied slot never fails.
Shouldn't this be on the debug assert below? Also, is there a citation?
> + // SAFETY: `self.state.state` is properly initialized and valid for XAS operations.
> + let ptr = unsafe {
> + bindings::xas_result(
> + &mut self.state.state,
> + bindings::xa_zero_to_null(bindings::xas_store(
> + &mut self.state.state,
> + core::ptr::null_mut(),
> + )),
> + )
> + };
> +
> + // SAFETY: `ptr` is a valid return value from xas_result.
> + let errno = unsafe { bindings::xa_err(ptr) };
> + debug_assert!(errno == 0);
> +
> + // SAFETY:
> + // - `ptr` came from `T::into_foreign`.
> + // - As this method takes self by value, the lifetimes of any [`T::Borrowed`] and
> + // [`T::BorrowedMut`] we have created must have ended.
> + unsafe { T::from_foreign(ptr.cast()) }
> + }
> +
> + /// Returns the index of this occupied entry.
> + ///
> + /// # Examples
> + ///
> + /// ```
> + /// # use kernel::{prelude::*, xarray::{AllocKind, XArray, Entry}};
> + /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
> + /// let mut guard = xa.lock();
> + ///
> + /// guard.store(42, KBox::new(0x1337u32, GFP_KERNEL)?, GFP_KERNEL)?;
> + ///
> + /// if let Entry::Occupied(entry) = guard.get_entry(42) {
> + /// assert_eq!(entry.index(), 42);
> + /// }
> + ///
> + /// # Ok::<(), kernel::error::Error>(())
> + /// ```
> + pub fn index(&self) -> usize {
> + self.state.state.xa_index
> + }
> +
> + /// Replaces the value in this occupied entry and returns the old value.
> + ///
> + /// # Examples
> + ///
> + /// ```
> + /// # use kernel::{prelude::*, xarray::{AllocKind, XArray, Entry}};
> + /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
> + /// let mut guard = xa.lock();
> + ///
> + /// guard.store(42, KBox::new(0x1337u32, GFP_KERNEL)?, GFP_KERNEL)?;
> + ///
> + /// if let Entry::Occupied(mut entry) = guard.get_entry(42) {
> + /// let new_value = KBox::new(0x9999u32, GFP_KERNEL)?;
> + /// let old_value = entry.insert(new_value);
> + /// assert_eq!(*old_value, 0x1337);
> + /// }
> + ///
> + /// assert_eq!(guard.get(42).copied(), Some(0x9999));
> + ///
> + /// # Ok::<(), kernel::error::Error>(())
> + /// ```
> + pub fn insert(&mut self, value: T) -> T {
> + // NOTE: Storing to an occupied slot never fails.
Citation?
> + let new = T::into_foreign(value).cast();
> + // SAFETY: `new` came from `T::into_foreign` and is guaranteed non-null.
> + self.ptr = unsafe { NonNull::new_unchecked(new) };
> +
> + // SAFETY: `self.state.state` is properly initialized and valid for XAS operations.
> + let old = unsafe {
> + bindings::xas_result(
> + &mut self.state.state,
> + bindings::xa_zero_to_null(bindings::xas_store(&mut self.state.state, new)),
> + )
> + };
> +
> + // SAFETY: `old` is a valid return value from xas_result.
> + let errno = unsafe { bindings::xa_err(old) };
> + debug_assert!(errno == 0);
> +
> + // SAFETY:
> + // - `ptr` came from `T::into_foreign`.
> + // - As this method takes self by value, the lifetimes of any [`T::Borrowed`] and
> + // [`T::BorrowedMut`] we have created must have ended.
> + unsafe { T::from_foreign(old) }
> + }
> +
> + /// Converts this occupied entry into a mutable reference to the value in the slot represented
> + /// by the entry.
> + ///
> + /// # Examples
> + ///
> + /// ```
> + /// # use kernel::{prelude::*, xarray::{AllocKind, XArray, Entry}};
> + /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
> + /// let mut guard = xa.lock();
> + ///
> + /// guard.store(42, KBox::new(0x1337u32, GFP_KERNEL)?, GFP_KERNEL)?;
> + ///
> + /// if let Entry::Occupied(entry) = guard.get_entry(42) {
> + /// let value_ref = entry.into_mut();
> + /// *value_ref = 0x9999;
> + /// }
> + ///
> + /// assert_eq!(guard.get(42).copied(), Some(0x9999));
> + ///
> + /// # Ok::<(), kernel::error::Error>(())
> + /// ```
> + pub fn into_mut(self) -> T::BorrowedMut<'b> {
> + // SAFETY: `ptr` came from `T::into_foreign`.
> + unsafe { T::borrow_mut(self.ptr.as_ptr()) }
> + }
> +
> + /// Swaps the value in this entry with the provided value.
> + ///
> + /// Returns the old value that was in the entry.
> + ///
> + /// # Examples
> + ///
> + /// ```
> + /// # use kernel::{prelude::*, xarray::{AllocKind, XArray, Entry}};
> + /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
> + /// let mut guard = xa.lock();
> + ///
> + /// guard.store(42, KBox::new(100u32, GFP_KERNEL)?, GFP_KERNEL)?;
> + ///
> + /// if let Entry::Occupied(mut entry) = guard.get_entry(42) {
> + /// let old_value = entry.swap(200u32);
> + /// assert_eq!(old_value, 100);
> + /// assert_eq!(*entry, 200);
> + /// }
> + ///
> + /// # Ok::<(), kernel::error::Error>(())
> + /// ```
> + pub fn swap<U>(&mut self, mut other: U) -> U
> + where
> + T: for<'c> ForeignOwnable<Borrowed<'c> = &'c U, BorrowedMut<'c> = &'c mut U>,
> + {
> + use core::ops::DerefMut;
> + core::mem::swap(self.deref_mut(), &mut other);
> + other
> + }
> +}
Does this need to return anything?
> +
> +impl<T, U> core::ops::Deref for OccupiedEntry<'_, '_, T>
> +where
> + T: for<'a> ForeignOwnable<Borrowed<'a> = &'a U, BorrowedMut<'a> = &'a mut U>,
> +{
> + type Target = U;
> +
> + fn deref(&self) -> &Self::Target {
> + // SAFETY: `ptr` came from `T::into_foreign`.
> + unsafe { T::borrow(self.ptr.as_ptr()) }
> + }
> +}
> +
> +impl<T, U> core::ops::DerefMut for OccupiedEntry<'_, '_, T>
> +where
> + T: for<'a> ForeignOwnable<Borrowed<'a> = &'a U, BorrowedMut<'a> = &'a mut U>,
> +{
> + fn deref_mut(&mut self) -> &mut Self::Target {
> + // SAFETY: `ptr` came from `T::into_foreign`.
> + unsafe { T::borrow_mut(self.ptr.as_ptr()) }
> + }
> +}
>
> --
> 2.51.2
>
>
Tamir Duberstein <tamird@gmail.com> writes:
> On Wed, Dec 3, 2025 at 5:27 PM Andreas Hindborg <a.hindborg@kernel.org> wrote:
>>
>> Add an Entry API for XArray that provides ergonomic access to array
>> slots that may be vacant or occupied. The API follows the pattern of
>> Rust's standard library HashMap entry API, allowing efficient
>> conditional insertion and modification of entries.
>>
>> The implementation uses the XArray state API (`xas_*` functions) for
>> efficient operations without requiring multiple lookups. Helper
>> functions are added to rust/helpers/xarray.c to wrap C macros that are
>> not directly accessible from Rust.
>>
>> Also update MAINTAINERS to cover the new rust files.
>>
>> Signed-off-by: Andreas Hindborg <a.hindborg@kernel.org>
>> ---
>> MAINTAINERS | 1 +
>> rust/helpers/xarray.c | 17 ++
>> rust/kernel/xarray.rs | 112 +++++++++++++
>> rust/kernel/xarray/entry.rs | 376 ++++++++++++++++++++++++++++++++++++++++++++
>> 4 files changed, 506 insertions(+)
>>
>> diff --git a/MAINTAINERS b/MAINTAINERS
>> index e8f06145fb54c..79d4c9c9b2b63 100644
>> --- a/MAINTAINERS
>> +++ b/MAINTAINERS
>> @@ -27909,6 +27909,7 @@ B: https://github.com/Rust-for-Linux/linux/issues
>> C: https://rust-for-linux.zulipchat.com
>> T: git https://github.com/Rust-for-Linux/linux.git xarray-next
>> F: rust/kernel/xarray.rs
>> +F: rust/kernel/xarray/
>>
>> XBOX DVD IR REMOTE
>> M: Benjamin Valentin <benpicco@googlemail.com>
>> diff --git a/rust/helpers/xarray.c b/rust/helpers/xarray.c
>> index 60b299f11451d..425a6cc494734 100644
>> --- a/rust/helpers/xarray.c
>> +++ b/rust/helpers/xarray.c
>> @@ -26,3 +26,20 @@ void rust_helper_xa_unlock(struct xarray *xa)
>> {
>> return xa_unlock(xa);
>> }
>> +
>> +void *rust_helper_xas_result(struct xa_state *xas, void *curr)
>> +{
>> + if (xa_err(xas->xa_node))
>> + curr = xas->xa_node;
>> + return curr;
>> +}
>
> Instead of this duplication, can we expose `xas_result` from the header?
`xas_result` is not currently exported. I'd rather not change that.
>
>> +
>> +void *rust_helper_xa_zero_to_null(void *entry)
>> +{
>> + return xa_is_zero(entry) ? NULL : entry;
>> +}
>> +
>> +int rust_helper_xas_error(const struct xa_state *xas)
>> +{
>> + return xas_error(xas);
>> +}
>> diff --git a/rust/kernel/xarray.rs b/rust/kernel/xarray.rs
>> index 9d4589979fd1d..2b8d56c81e36b 100644
>> --- a/rust/kernel/xarray.rs
>> +++ b/rust/kernel/xarray.rs
>> @@ -13,11 +13,17 @@
>> NonNull, //
>> },
>> };
>> +pub use entry::{
>> + Entry,
>> + OccupiedEntry,
>> + VacantEntry, //
>> +};
>> use kernel::{
>> alloc,
>> bindings,
>> build_assert, //
>> error::{
>> + to_result,
>> Error,
>> Result, //
>> },
>> @@ -255,6 +261,35 @@ pub fn get_mut(&mut self, index: usize) -> Option<T::BorrowedMut<'_>> {
>> Some(unsafe { T::borrow_mut(ptr.as_ptr()) })
>> }
>>
>> + /// Gets an entry for the specified index, which can be vacant or occupied.
>> + ///
>> + /// # Examples
>> + ///
>> + /// ```
>> + /// # use kernel::{prelude::*, xarray::{AllocKind, XArray, Entry}};
>> + /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
>> + /// let mut guard = xa.lock();
>> + ///
>> + /// assert_eq!(guard.contains_index(42), false);
>> + ///
>> + /// match guard.get_entry(42) {
>> + /// Entry::Vacant(entry) => {
>> + /// entry.insert(KBox::new(0x1337u32, GFP_KERNEL)?)?;
>> + /// }
>> + /// Entry::Occupied(_) => unreachable!("We did not insert an entry yet"),
>> + /// }
>> + ///
>> + /// assert_eq!(guard.get(42), Some(&0x1337));
>> + ///
>> + /// # Ok::<(), kernel::error::Error>(())
>> + /// ```
>> + pub fn get_entry<'b>(&'b mut self, index: usize) -> Entry<'a, 'b, T> {
>> + match self.load(index) {
>> + None => Entry::Vacant(VacantEntry::new(self, index)),
>> + Some(ptr) => Entry::Occupied(OccupiedEntry::new(self, index, ptr)),
>> + }
>> + }
>
> Why not "entry" like the stdlib collections?
Right, it has to be `entry`, so says the API naming guidelines.
>
>> +
>> fn load_next(&self, index: usize) -> Option<(usize, NonNull<c_void>)> {
>> let mut state = XArrayState::new(self, index);
>> // SAFETY: `state.state` is always valid by the type invariant of
>> @@ -320,6 +355,76 @@ pub fn find_next_mut(&mut self, index: usize) -> Option<(usize, T::BorrowedMut<'
>> .map(move |(index, ptr)| (index, unsafe { T::borrow_mut(ptras_ptr()) }))
>> }
>>
>> + /// Finds the next occupied entry starting from the given index.
>> + ///
>> + /// # Examples
>> + ///
>> + /// ```
>> + /// # use kernel::{prelude::*, xarray::{AllocKind, XArray}};
>> + /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
>> + /// let mut guard = xa.lock();
>> + ///
>> + /// guard.store(10, KBox::new(10u32, GFP_KERNEL)?, GFP_KERNEL)?;
>> + /// guard.store(20, KBox::new(20u32, GFP_KERNEL)?, GFP_KERNEL)?;
>> + ///
>> + /// if let Some(entry) = guard.find_next_entry(5) {
>> + /// assert_eq!(entry.index(), 10);
>> + /// let value = entry.remove();
>> + /// assert_eq!(*value, 10);
>> + /// }
>> + ///
>> + /// assert_eq!(guard.get(10), None);
>> + ///
>> + /// # Ok::<(), kernel::error::Error>(())
>> + /// ```
>> + pub fn find_next_entry<'b>(&'b mut self, index: usize) -> Option<OccupiedEntry<'a, 'b, T>> {
>> + let mut state = XArrayState::new(self, index);
>> +
>> + // SAFETY: `state.state` is properly initialized by XArrayState::new and the caller holds
>> + // the lock.
>> + let ptr = NonNull::new(unsafe { bindings::xas_find(&mut statestate, usize::MAX) })?;
>> +
>> + Some(OccupiedEntry { state, ptr })
>> + }
>
> I'm surprised this doesn't share code with find_next_mut. Can it?
> Again, I'd have expected the bulk of the logic to be on XArrayState.
I'll try to move the logic and reuse `load_next`.
>
>> +
>> + /// Finds the next occupied entry starting at the given index, wrapping around.
>> + ///
>> + /// Searches for an entry starting at `index` up to the maximum index. If no entry
>> + /// is found, wraps around and searches from index 0 up to `index`.
>> + ///
>> + /// # Examples
>> + ///
>> + /// ```
>> + /// # use kernel::{prelude::*, xarray::{AllocKind, XArray}};
>> + /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
>> + /// let mut guard = xa.lock();
>> + ///
>> + /// guard.store(100, KBox::new(42u32, GFP_KERNEL)?, GFP_KERNEL)?;
>> + /// let entry = guard.find_next_entry_circular(101);
>> + /// assert_eq!(entry.map(|e| e.index()), Some(100));
>> + ///
>> + /// # Ok::<(), kernel::error::Error>(())
>> + /// ```
>> + pub fn find_next_entry_circular<'b>(
>> + &'b mut self,
>> + index: usize,
>> + ) -> Option<OccupiedEntry<'a, 'b, T>> {
>> + let mut state = XArrayState::new(self, index);
>> +
>> + // SAFETY: `state.state` is properly initialized by XArrayState::new and the caller holds
>> + // the lock.
>> + let ptr = NonNull::new(unsafe { bindings::xas_find(&mut statestate, usize::MAX) })
>> + .or_else(|| {
>> + state.state.xa_node = bindings::XAS_RESTART as *mut bindings::xa_node;
>> + state.state.xa_index = 0;
>> + // SAFETY: `state.state` is properly initialized and by type invariant, we hold the
>> + // xarray lock.
>> + NonNull::new(unsafe { bindings::xas_find(&mut state.state, index) })
>> + })?;
>> +
>> + Some(OccupiedEntry { state, ptr })
>> + }
>
> Instead of this function, can find_next_entry take a Range? Then it
> would be simple for the caller to wrap if they want, without bloating
> this API.
We could do that, but I am not sure if it is idiomatic? The range syntax
a..b is considered empty if b<a. But it still produces a valid
`core::ops::Range` that we could use.
>
>> +
>> /// Removes and returns the element at the given index.
>> pub fn remove(&mut self, index: usize) -> Option<T> {
>> // SAFETY:
>> @@ -416,8 +521,15 @@ fn new(access: &'b Guard<'a, T>, index: usize) -> Self {
>> },
>> }
>> }
>> +
>> + fn status(&self) -> Result {
>> + // SAFETY: `self.state` is properly initialized and valid.
>> + to_result(unsafe { bindings::xas_error(&self.state) })
>> + }
>> }
>>
>> +mod entry;
>> +
>> // SAFETY: `XArray<T>` has no shared mutable state so it is `Send` iff `T` is `Send`.
>> unsafe impl<T: ForeignOwnable + Send> Send for XArray<T> {}
>>
>> diff --git a/rust/kernel/xarray/entry.rs b/rust/kernel/xarray/entry.rs
>> new file mode 100644
>> index 0000000000000..1268dc35bac58
>> --- /dev/null
>> +++ b/rust/kernel/xarray/entry.rs
>> @@ -0,0 +1,376 @@
>> +// SPDX-License-Identifier: GPL-2.0
>> +
>> +use super::{
>> + Guard,
>> + StoreError,
>> + XArrayState, //
>> +};
>> +use core::ptr::NonNull;
>> +use kernel::{
>> + prelude::*,
>> + types::ForeignOwnable, //
>> +};
>> +
>> +/// Represents either a vacant or occupied entry in an XArray.
>> +pub enum Entry<'a, 'b, T: ForeignOwnable> {
>> + /// A vacant entry that can have a value inserted.
>> + Vacant(VacantEntry<'a, 'b, T>),
>> + /// An occupied entry containing a value.
>> + Occupied(OccupiedEntry<'a, 'b, T>),
>> +}
>> +
>> +impl<T: ForeignOwnable> Entry<'_, '_, T> {
>> + /// Returns true if this entry is occupied.
>> + ///
>> + /// # Examples
>> + ///
>> + /// ```
>> + /// # use kernel::{prelude::*, xarray::{AllocKind, XArray, Entry}};
>> + /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
>> + /// let mut guard = xa.lock();
>> + ///
>> + ///
>> + /// let entry = guard.get_entry(42);
>> + /// assert_eq!(entry.is_occupied(), false);
>> + ///
>> + /// guard.store(42, KBox::new(0x1337u32, GFP_KERNEL)?, GFP_KERNEL)?;
>> + /// let entry = guard.get_entry(42);
>> + /// assert_eq!(entry.is_occupied(), true);
>> + ///
>> + /// # Ok::<(), kernel::error::Error>(())
>> + /// ```
>> + pub fn is_occupied(&self) -> bool {
>> + matches!(self, Entry::Occupied(_))
>> + }
>
> Do we need this? IMO less is more, and even stdlib doesn't have this.
Similar to `contains_index`, it de-clutters at call sites. I like
if entry.is_occupied() {...}
better than
if matches!(entry, Entry::Occupied(_)) {...}
>
>> +}
>> +
>> +/// A view into a vacant entry in an XArray.
>> +pub struct VacantEntry<'a, 'b, T: ForeignOwnable> {
>> + state: XArrayState<'a, 'b, T>,
>> +}
>> +
>> +impl<'a, 'b, T> VacantEntry<'a, 'b, T>
>> +where
>> + T: ForeignOwnable,
>> +{
>> + pub(crate) fn new(guard: &'b mut Guard<'a, T>, index: usize) -> Self {
>> + Self {
>> + state: XArrayState::new(guard, index),
>> + }
>> + }
>> +
>> + fn insert_internal(&mut self, value: T) -> Result<*mut c_void, StoreError<T>> {
>> + let new = T::into_foreign(value).cast();
>> +
>> + // SAFETY: `self.state.state` is properly initialized and `new` came from `T::into_foreign`.
>> + // We hold the xarray lock.
>> + unsafe { bindings::xas_store(&mut self.state.state, new) };
>
> Can this please be on XArray?
OK.
>
>> +
>> + self.state.status().map(|()| new).map_err(|error| {
>> + // SAFETY: `new` came from `T::into_foreign` and `xas_store` does not take ownership of
>> + // the value on error.
>> + let value = unsafe { T::from_foreign(new) };
>> + StoreError { value, error }
>> + })
>> + }
>> +
>> + /// Inserts a value into this vacant entry.
>> + ///
>> + /// Returns a reference to the newly inserted value.
>> + ///
>> + /// - This method will fail if the nodes on the path to the index
>> + /// represented by this entry are not present in the XArray.
>> + /// - This method will not drop the XArray lock.
>> + ///
>> + ///
>> + /// # Examples
>> + ///
>> + /// ```
>> + /// # use kernel::{prelude::*, xarray::{AllocKind, XArray, Entry}};
>> + /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
>> + /// let mut guard = xa.lock();
>> + ///
>> + /// assert_eq!(guard.get(42), None);
>> + ///
>> + /// if let Entry::Vacant(entry) = guard.get_entry(42) {
>> + /// let value = KBox::new(0x1337u32, GFP_KERNEL)?;
>> + /// let borrowed = entry.insert(value)?;
>> + /// assert_eq!(*borrowed, 0x1337);
>> + /// }
>> + ///
>> + /// assert_eq!(guard.get(42).copied(), Some(0x1337));
>> + ///
>> + /// # Ok::<(), kernel::error::Error>(())
>> + /// ```
>> + pub fn insert(mut self, value: T) -> Result<T::BorrowedMut<'b>, StoreError<T>> {
>> + let new = self.insert_internal(value)?;
>> +
>> + // SAFETY: `new` came from `T::into_foreign`.The entry has exclusive
>
> This is knowledge at a distance. There's no comment anywhere that
> promises that insert_internal called T::into_foreign.
How would you handle this? Add documentation to `insert_internal`?
>
>> + // ownership of `new` as it holds a mutable reference to `Guard`.
>> + Ok(unsafe { T::borrow_mut(new) })
>> + }
>> +
>> + /// Inserts a value and returns an occupied entry representing the newly inserted value.
>> + ///
>> + /// - This method will fail if the nodes on the path to the index
>> + /// represented by this entry are not present in the XArray.
>> + /// - This method will not drop the XArray lock.
>> + ///
>> + /// # Examples
>> + ///
>> + /// ```
>> + /// # use kernel::{prelude::*, xarray::{AllocKind, XArray, Entry}};
>> + /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
>> + /// let mut guard = xa.lock();
>> + ///
>> + /// assert_eq!(guard.get(42), None);
>> + ///
>> + /// if let Entry::Vacant(entry) = guard.get_entry(42) {
>> + /// let value = KBox::new(0x1337u32, GFP_KERNEL)?;
>> + /// let occupied = entry.insert_entry(value)?;
>> + /// assert_eq!(occupied.index(), 42);
>> + /// }
>> + ///
>> + /// assert_eq!(guard.get(42).copied(), Some(0x1337));
>> + ///
>> + /// # Ok::<(), kernel::error::Error>(())
>> + /// ```
>> + pub fn insert_entry(mut self, value: T) -> Result<OccupiedEntry<'a, 'b, T>, StoreError<T>> {
>> + let new = self.insert_internal(value)?;
>> +
>> + Ok(OccupiedEntry::<'a, 'b, T> {
>> + state: self.state,
>> + // SAFETY: `new` came from `T::into_foreign` and is guaranteed non-null.
>
> Same.
>
>> + ptr: unsafe { core::ptr::NonNull::new_unchecked(new) },
>> + })
>> + }
>> +
>> + /// Returns the index of this vacant entry.
>> + ///
>> + /// # Examples
>> + ///
>> + /// ```
>> + /// # use kernel::{prelude::*, xarray::{AllocKind, XArray, Entry}};
>> + /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
>> + /// let mut guard = xa.lock();
>> + ///
>> + /// assert_eq!(guard.get(42), None);
>> + ///
>> + /// if let Entry::Vacant(entry) = guard.get_entry(42) {
>> + /// assert_eq!(entry.index(), 42);
>> + /// }
>> + ///
>> + /// # Ok::<(), kernel::error::Error>(())
>> + /// ```
>> + pub fn index(&self) -> usize {
>> + self.state.state.xa_index
>> + }
>> +}
>> +
>> +/// A view into an occupied entry in an XArray.
>> +pub struct OccupiedEntry<'a, 'b, T: ForeignOwnable> {
>> + pub(crate) state: XArrayState<'a, 'b, T>,
>> + pub(crate) ptr: NonNull<c_void>,
>> +}
>> +
>> +impl<'a, 'b, T> OccupiedEntry<'a, 'b, T>
>> +where
>> + T: ForeignOwnable,
>> +{
>> + pub(crate) fn new(guard: &'b mut Guard<'a, T>, index: usize, ptr: NonNull<c_void>) -> Self {
>> + Self {
>> + state: XArrayState::new(guard, index),
>> + ptr,
>> + }
>> + }
>> +
>> + /// Removes the value from this occupied entry and returns it, consuming the entry.
>> + ///
>> + /// # Examples
>> + ///
>> + /// ```
>> + /// # use kernel::{prelude::*, xarray::{AllocKind, XArray, Entry}};
>> + /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
>> + /// let mut guard = xa.lock();
>> + ///
>> + /// guard.store(42, KBox::new(0x1337u32, GFP_KERNEL)?, GFP_KERNEL)?;
>> + /// assert_eq!(guard.get(42).copied(), Some(0x1337));
>> + ///
>> + /// if let Entry::Occupied(entry) = guard.get_entry(42) {
>> + /// let value = entry.remove();
>> + /// assert_eq!(*value, 0x1337);
>> + /// }
>> + ///
>> + /// assert_eq!(guard.get(42), None);
>> + ///
>> + /// # Ok::<(), kernel::error::Error>(())
>> + /// ```
>> + pub fn remove(mut self) -> T {
>> + // NOTE: Storing NULL to an occupied slot never fails.
>
> Shouldn't this be on the debug assert below? Also, is there a citation?
I'll move it.
I don't think I have a citation for that. This is a consequence of the
data structure design. If the slot is occupied, the node has already
been allocated, and allocation error is the only failure mode for this path.
>
>> + // SAFETY: `self.state.state` is properly initialized and valid for XAS operations.
>> + let ptr = unsafe {
>> + bindings::xas_result(
>> + &mut self.state.state,
>> + bindings::xa_zero_to_null(bindings::xas_store(
>> + &mut self.state.state,
>> + core::ptr::null_mut(),
>> + )),
>> + )
>> + };
>> +
>> + // SAFETY: `ptr` is a valid return value from xas_result.
>> + let errno = unsafe { bindings::xa_err(ptr) };
>> + debug_assert!(errno == 0);
>> +
>> + // SAFETY:
>> + // - `ptr` came from `T::into_foreign`.
>> + // - As this method takes self by value, the lifetimes of any [`T::Borrowed`] and
>> + // [`T::BorrowedMut`] we have created must have ended.
>> + unsafe { T::from_foreign(ptr.cast()) }
>> + }
>> +
>> + /// Returns the index of this occupied entry.
>> + ///
>> + /// # Examples
>> + ///
>> + /// ```
>> + /// # use kernel::{prelude::*, xarray::{AllocKind, XArray, Entry}};
>> + /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
>> + /// let mut guard = xa.lock();
>> + ///
>> + /// guard.store(42, KBox::new(0x1337u32, GFP_KERNEL)?, GFP_KERNEL)?;
>> + ///
>> + /// if let Entry::Occupied(entry) = guard.get_entry(42) {
>> + /// assert_eq!(entry.index(), 42);
>> + /// }
>> + ///
>> + /// # Ok::<(), kernel::error::Error>(())
>> + /// ```
>> + pub fn index(&self) -> usize {
>> + self.state.state.xa_index
>> + }
>> +
>> + /// Replaces the value in this occupied entry and returns the old value.
>> + ///
>> + /// # Examples
>> + ///
>> + /// ```
>> + /// # use kernel::{prelude::*, xarray::{AllocKind, XArray, Entry}};
>> + /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
>> + /// let mut guard = xa.lock();
>> + ///
>> + /// guard.store(42, KBox::new(0x1337u32, GFP_KERNEL)?, GFP_KERNEL)?;
>> + ///
>> + /// if let Entry::Occupied(mut entry) = guard.get_entry(42) {
>> + /// let new_value = KBox::new(0x9999u32, GFP_KERNEL)?;
>> + /// let old_value = entry.insert(new_value);
>> + /// assert_eq!(*old_value, 0x1337);
>> + /// }
>> + ///
>> + /// assert_eq!(guard.get(42).copied(), Some(0x9999));
>> + ///
>> + /// # Ok::<(), kernel::error::Error>(())
>> + /// ```
>> + pub fn insert(&mut self, value: T) -> T {
>> + // NOTE: Storing to an occupied slot never fails.
>
> Citation?
>
>> + let new = T::into_foreign(value).cast();
>> + // SAFETY: `new` came from `T::into_foreign` and is guaranteed non-null.
>> + self.ptr = unsafe { NonNull::new_unchecked(new) };
>> +
>> + // SAFETY: `self.state.state` is properly initialized and valid for XAS operations.
>> + let old = unsafe {
>> + bindings::xas_result(
>> + &mut self.state.state,
>> + bindings::xa_zero_to_null(bindings::xas_store(&mut selfstate.state, new)),
>> + )
>> + };
>> +
>> + // SAFETY: `old` is a valid return value from xas_result.
>> + let errno = unsafe { bindings::xa_err(old) };
>> + debug_assert!(errno == 0);
>> +
>> + // SAFETY:
>> + // - `ptr` came from `T::into_foreign`.
>> + // - As this method takes self by value, the lifetimes of any [`T::Borrowed`] and
>> + // [`T::BorrowedMut`] we have created must have ended.
>> + unsafe { T::from_foreign(old) }
>> + }
>> +
>> + /// Converts this occupied entry into a mutable reference to the value in the slot represented
>> + /// by the entry.
>> + ///
>> + /// # Examples
>> + ///
>> + /// ```
>> + /// # use kernel::{prelude::*, xarray::{AllocKind, XArray, Entry}};
>> + /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
>> + /// let mut guard = xa.lock();
>> + ///
>> + /// guard.store(42, KBox::new(0x1337u32, GFP_KERNEL)?, GFP_KERNEL)?;
>> + ///
>> + /// if let Entry::Occupied(entry) = guard.get_entry(42) {
>> + /// let value_ref = entry.into_mut();
>> + /// *value_ref = 0x9999;
>> + /// }
>> + ///
>> + /// assert_eq!(guard.get(42).copied(), Some(0x9999));
>> + ///
>> + /// # Ok::<(), kernel::error::Error>(())
>> + /// ```
>> + pub fn into_mut(self) -> T::BorrowedMut<'b> {
>> + // SAFETY: `ptr` came from `T::into_foreign`.
>> + unsafe { T::borrow_mut(self.ptr.as_ptr()) }
>> + }
>> +
>> + /// Swaps the value in this entry with the provided value.
>> + ///
>> + /// Returns the old value that was in the entry.
>> + ///
>> + /// # Examples
>> + ///
>> + /// ```
>> + /// # use kernel::{prelude::*, xarray::{AllocKind, XArray, Entry}};
>> + /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
>> + /// let mut guard = xa.lock();
>> + ///
>> + /// guard.store(42, KBox::new(100u32, GFP_KERNEL)?, GFP_KERNEL)?;
>> + ///
>> + /// if let Entry::Occupied(mut entry) = guard.get_entry(42) {
>> + /// let old_value = entry.swap(200u32);
>> + /// assert_eq!(old_value, 100);
>> + /// assert_eq!(*entry, 200);
>> + /// }
>> + ///
>> + /// # Ok::<(), kernel::error::Error>(())
>> + /// ```
>> + pub fn swap<U>(&mut self, mut other: U) -> U
>> + where
>> + T: for<'c> ForeignOwnable<Borrowed<'c> = &'c U, BorrowedMut<'c> = &'c mut U>,
>> + {
>> + use core::ops::DerefMut;
>> + core::mem::swap(self.deref_mut(), &mut other);
>> + other
>> + }
>> +}
>
> Does this need to return anything?
We probably should take `other` by mutable reference to align with
`core::mem::swap`.
Thanks for the comments!
Best regards,
Andreas Hindborg
On Thu, Jan 8, 2026 at 4:25 AM Andreas Hindborg <a.hindborg@kernel.org> wrote:
>
> Tamir Duberstein <tamird@gmail.com> writes:
>
> > On Wed, Dec 3, 2025 at 5:27 PM Andreas Hindborg <a.hindborg@kernel.org> wrote:
> >>
> >> Add an Entry API for XArray that provides ergonomic access to array
> >> slots that may be vacant or occupied. The API follows the pattern of
> >> Rust's standard library HashMap entry API, allowing efficient
> >> conditional insertion and modification of entries.
> >>
> >> The implementation uses the XArray state API (`xas_*` functions) for
> >> efficient operations without requiring multiple lookups. Helper
> >> functions are added to rust/helpers/xarray.c to wrap C macros that are
> >> not directly accessible from Rust.
> >>
> >> Also update MAINTAINERS to cover the new rust files.
> >>
> >> Signed-off-by: Andreas Hindborg <a.hindborg@kernel.org>
> >> ---
> >> MAINTAINERS | 1 +
> >> rust/helpers/xarray.c | 17 ++
> >> rust/kernel/xarray.rs | 112 +++++++++++++
> >> rust/kernel/xarray/entry.rs | 376 ++++++++++++++++++++++++++++++++++++++++++++
> >> 4 files changed, 506 insertions(+)
> >>
> >> diff --git a/MAINTAINERS b/MAINTAINERS
> >> index e8f06145fb54c..79d4c9c9b2b63 100644
> >> --- a/MAINTAINERS
> >> +++ b/MAINTAINERS
> >> @@ -27909,6 +27909,7 @@ B: https://github.com/Rust-for-Linux/linux/issues
> >> C: https://rust-for-linux.zulipchat.com
> >> T: git https://github.com/Rust-for-Linux/linux.git xarray-next
> >> F: rust/kernel/xarray.rs
> >> +F: rust/kernel/xarray/
> >>
> >> XBOX DVD IR REMOTE
> >> M: Benjamin Valentin <benpicco@googlemail.com>
> >> diff --git a/rust/helpers/xarray.c b/rust/helpers/xarray.c
> >> index 60b299f11451d..425a6cc494734 100644
> >> --- a/rust/helpers/xarray.c
> >> +++ b/rust/helpers/xarray.c
> >> @@ -26,3 +26,20 @@ void rust_helper_xa_unlock(struct xarray *xa)
> >> {
> >> return xa_unlock(xa);
> >> }
> >> +
> >> +void *rust_helper_xas_result(struct xa_state *xas, void *curr)
> >> +{
> >> + if (xa_err(xas->xa_node))
> >> + curr = xas->xa_node;
> >> + return curr;
> >> +}
> >
> > Instead of this duplication, can we expose `xas_result` from the header?
>
> `xas_result` is not currently exported. I'd rather not change that.
Why?
>
> >
> >> +
> >> +void *rust_helper_xa_zero_to_null(void *entry)
> >> +{
> >> + return xa_is_zero(entry) ? NULL : entry;
> >> +}
> >> +
> >> +int rust_helper_xas_error(const struct xa_state *xas)
> >> +{
> >> + return xas_error(xas);
> >> +}
> >> diff --git a/rust/kernel/xarray.rs b/rust/kernel/xarray.rs
> >> index 9d4589979fd1d..2b8d56c81e36b 100644
> >> --- a/rust/kernel/xarray.rs
> >> +++ b/rust/kernel/xarray.rs
> >> @@ -13,11 +13,17 @@
> >> NonNull, //
> >> },
> >> };
> >> +pub use entry::{
> >> + Entry,
> >> + OccupiedEntry,
> >> + VacantEntry, //
> >> +};
> >> use kernel::{
> >> alloc,
> >> bindings,
> >> build_assert, //
> >> error::{
> >> + to_result,
> >> Error,
> >> Result, //
> >> },
> >> @@ -255,6 +261,35 @@ pub fn get_mut(&mut self, index: usize) -> Option<T::BorrowedMut<'_>> {
> >> Some(unsafe { T::borrow_mut(ptr.as_ptr()) })
> >> }
> >>
> >> + /// Gets an entry for the specified index, which can be vacant or occupied.
> >> + ///
> >> + /// # Examples
> >> + ///
> >> + /// ```
> >> + /// # use kernel::{prelude::*, xarray::{AllocKind, XArray, Entry}};
> >> + /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
> >> + /// let mut guard = xa.lock();
> >> + ///
> >> + /// assert_eq!(guard.contains_index(42), false);
> >> + ///
> >> + /// match guard.get_entry(42) {
> >> + /// Entry::Vacant(entry) => {
> >> + /// entry.insert(KBox::new(0x1337u32, GFP_KERNEL)?)?;
> >> + /// }
> >> + /// Entry::Occupied(_) => unreachable!("We did not insert an entry yet"),
> >> + /// }
> >> + ///
> >> + /// assert_eq!(guard.get(42), Some(&0x1337));
> >> + ///
> >> + /// # Ok::<(), kernel::error::Error>(())
> >> + /// ```
> >> + pub fn get_entry<'b>(&'b mut self, index: usize) -> Entry<'a, 'b, T> {
> >> + match self.load(index) {
> >> + None => Entry::Vacant(VacantEntry::new(self, index)),
> >> + Some(ptr) => Entry::Occupied(OccupiedEntry::new(self, index, ptr)),
> >> + }
> >> + }
> >
> > Why not "entry" like the stdlib collections?
>
> Right, it has to be `entry`, so says the API naming guidelines.
>
> >
> >> +
> >> fn load_next(&self, index: usize) -> Option<(usize, NonNull<c_void>)> {
> >> let mut state = XArrayState::new(self, index);
> >> // SAFETY: `state.state` is always valid by the type invariant of
> >> @@ -320,6 +355,76 @@ pub fn find_next_mut(&mut self, index: usize) -> Option<(usize, T::BorrowedMut<'
> >> .map(move |(index, ptr)| (index, unsafe { T::borrow_mut(ptras_ptr()) }))
> >> }
> >>
> >> + /// Finds the next occupied entry starting from the given index.
> >> + ///
> >> + /// # Examples
> >> + ///
> >> + /// ```
> >> + /// # use kernel::{prelude::*, xarray::{AllocKind, XArray}};
> >> + /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
> >> + /// let mut guard = xa.lock();
> >> + ///
> >> + /// guard.store(10, KBox::new(10u32, GFP_KERNEL)?, GFP_KERNEL)?;
> >> + /// guard.store(20, KBox::new(20u32, GFP_KERNEL)?, GFP_KERNEL)?;
> >> + ///
> >> + /// if let Some(entry) = guard.find_next_entry(5) {
> >> + /// assert_eq!(entry.index(), 10);
> >> + /// let value = entry.remove();
> >> + /// assert_eq!(*value, 10);
> >> + /// }
> >> + ///
> >> + /// assert_eq!(guard.get(10), None);
> >> + ///
> >> + /// # Ok::<(), kernel::error::Error>(())
> >> + /// ```
> >> + pub fn find_next_entry<'b>(&'b mut self, index: usize) -> Option<OccupiedEntry<'a, 'b, T>> {
> >> + let mut state = XArrayState::new(self, index);
> >> +
> >> + // SAFETY: `state.state` is properly initialized by XArrayState::new and the caller holds
> >> + // the lock.
> >> + let ptr = NonNull::new(unsafe { bindings::xas_find(&mut statestate, usize::MAX) })?;
> >> +
> >> + Some(OccupiedEntry { state, ptr })
> >> + }
> >
> > I'm surprised this doesn't share code with find_next_mut. Can it?
> > Again, I'd have expected the bulk of the logic to be on XArrayState.
>
> I'll try to move the logic and reuse `load_next`.
>
> >
> >> +
> >> + /// Finds the next occupied entry starting at the given index, wrapping around.
> >> + ///
> >> + /// Searches for an entry starting at `index` up to the maximum index. If no entry
> >> + /// is found, wraps around and searches from index 0 up to `index`.
> >> + ///
> >> + /// # Examples
> >> + ///
> >> + /// ```
> >> + /// # use kernel::{prelude::*, xarray::{AllocKind, XArray}};
> >> + /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
> >> + /// let mut guard = xa.lock();
> >> + ///
> >> + /// guard.store(100, KBox::new(42u32, GFP_KERNEL)?, GFP_KERNEL)?;
> >> + /// let entry = guard.find_next_entry_circular(101);
> >> + /// assert_eq!(entry.map(|e| e.index()), Some(100));
> >> + ///
> >> + /// # Ok::<(), kernel::error::Error>(())
> >> + /// ```
> >> + pub fn find_next_entry_circular<'b>(
> >> + &'b mut self,
> >> + index: usize,
> >> + ) -> Option<OccupiedEntry<'a, 'b, T>> {
> >> + let mut state = XArrayState::new(self, index);
> >> +
> >> + // SAFETY: `state.state` is properly initialized by XArrayState::new and the caller holds
> >> + // the lock.
> >> + let ptr = NonNull::new(unsafe { bindings::xas_find(&mut statestate, usize::MAX) })
> >> + .or_else(|| {
> >> + state.state.xa_node = bindings::XAS_RESTART as *mut bindings::xa_node;
> >> + state.state.xa_index = 0;
> >> + // SAFETY: `state.state` is properly initialized and by type invariant, we hold the
> >> + // xarray lock.
> >> + NonNull::new(unsafe { bindings::xas_find(&mut state.state, index) })
> >> + })?;
> >> +
> >> + Some(OccupiedEntry { state, ptr })
> >> + }
> >
> > Instead of this function, can find_next_entry take a Range? Then it
> > would be simple for the caller to wrap if they want, without bloating
> > this API.
>
> We could do that, but I am not sure if it is idiomatic? The range syntax
> a..b is considered empty if b<a. But it still produces a valid
> `core::ops::Range` that we could use.
Can you clearly state your objection?
>
> >
> >> +
> >> /// Removes and returns the element at the given index.
> >> pub fn remove(&mut self, index: usize) -> Option<T> {
> >> // SAFETY:
> >> @@ -416,8 +521,15 @@ fn new(access: &'b Guard<'a, T>, index: usize) -> Self {
> >> },
> >> }
> >> }
> >> +
> >> + fn status(&self) -> Result {
> >> + // SAFETY: `self.state` is properly initialized and valid.
> >> + to_result(unsafe { bindings::xas_error(&self.state) })
> >> + }
> >> }
> >>
> >> +mod entry;
> >> +
> >> // SAFETY: `XArray<T>` has no shared mutable state so it is `Send` iff `T` is `Send`.
> >> unsafe impl<T: ForeignOwnable + Send> Send for XArray<T> {}
> >>
> >> diff --git a/rust/kernel/xarray/entry.rs b/rust/kernel/xarray/entry.rs
> >> new file mode 100644
> >> index 0000000000000..1268dc35bac58
> >> --- /dev/null
> >> +++ b/rust/kernel/xarray/entry.rs
> >> @@ -0,0 +1,376 @@
> >> +// SPDX-License-Identifier: GPL-2.0
> >> +
> >> +use super::{
> >> + Guard,
> >> + StoreError,
> >> + XArrayState, //
> >> +};
> >> +use core::ptr::NonNull;
> >> +use kernel::{
> >> + prelude::*,
> >> + types::ForeignOwnable, //
> >> +};
> >> +
> >> +/// Represents either a vacant or occupied entry in an XArray.
> >> +pub enum Entry<'a, 'b, T: ForeignOwnable> {
> >> + /// A vacant entry that can have a value inserted.
> >> + Vacant(VacantEntry<'a, 'b, T>),
> >> + /// An occupied entry containing a value.
> >> + Occupied(OccupiedEntry<'a, 'b, T>),
> >> +}
> >> +
> >> +impl<T: ForeignOwnable> Entry<'_, '_, T> {
> >> + /// Returns true if this entry is occupied.
> >> + ///
> >> + /// # Examples
> >> + ///
> >> + /// ```
> >> + /// # use kernel::{prelude::*, xarray::{AllocKind, XArray, Entry}};
> >> + /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
> >> + /// let mut guard = xa.lock();
> >> + ///
> >> + ///
> >> + /// let entry = guard.get_entry(42);
> >> + /// assert_eq!(entry.is_occupied(), false);
> >> + ///
> >> + /// guard.store(42, KBox::new(0x1337u32, GFP_KERNEL)?, GFP_KERNEL)?;
> >> + /// let entry = guard.get_entry(42);
> >> + /// assert_eq!(entry.is_occupied(), true);
> >> + ///
> >> + /// # Ok::<(), kernel::error::Error>(())
> >> + /// ```
> >> + pub fn is_occupied(&self) -> bool {
> >> + matches!(self, Entry::Occupied(_))
> >> + }
> >
> > Do we need this? IMO less is more, and even stdlib doesn't have this.
>
> Similar to `contains_index`, it de-clutters at call sites. I like
>
> if entry.is_occupied() {...}
>
> better than
>
> if matches!(entry, Entry::Occupied(_)) {...}
Similar to the discussion on `contains_index` -- discarding
information in this way seems to be a smell, but I can't say without
seeing more code. My suggestion is not to add this until there's a
usage that we can see in the same series.
>
> >
> >> +}
> >> +
> >> +/// A view into a vacant entry in an XArray.
> >> +pub struct VacantEntry<'a, 'b, T: ForeignOwnable> {
> >> + state: XArrayState<'a, 'b, T>,
> >> +}
> >> +
> >> +impl<'a, 'b, T> VacantEntry<'a, 'b, T>
> >> +where
> >> + T: ForeignOwnable,
> >> +{
> >> + pub(crate) fn new(guard: &'b mut Guard<'a, T>, index: usize) -> Self {
> >> + Self {
> >> + state: XArrayState::new(guard, index),
> >> + }
> >> + }
> >> +
> >> + fn insert_internal(&mut self, value: T) -> Result<*mut c_void, StoreError<T>> {
> >> + let new = T::into_foreign(value).cast();
> >> +
> >> + // SAFETY: `self.state.state` is properly initialized and `new` came from `T::into_foreign`.
> >> + // We hold the xarray lock.
> >> + unsafe { bindings::xas_store(&mut self.state.state, new) };
> >
> > Can this please be on XArray?
>
> OK.
>
> >
> >> +
> >> + self.state.status().map(|()| new).map_err(|error| {
> >> + // SAFETY: `new` came from `T::into_foreign` and `xas_store` does not take ownership of
> >> + // the value on error.
> >> + let value = unsafe { T::from_foreign(new) };
> >> + StoreError { value, error }
> >> + })
> >> + }
> >> +
> >> + /// Inserts a value into this vacant entry.
> >> + ///
> >> + /// Returns a reference to the newly inserted value.
> >> + ///
> >> + /// - This method will fail if the nodes on the path to the index
> >> + /// represented by this entry are not present in the XArray.
> >> + /// - This method will not drop the XArray lock.
> >> + ///
> >> + ///
> >> + /// # Examples
> >> + ///
> >> + /// ```
> >> + /// # use kernel::{prelude::*, xarray::{AllocKind, XArray, Entry}};
> >> + /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
> >> + /// let mut guard = xa.lock();
> >> + ///
> >> + /// assert_eq!(guard.get(42), None);
> >> + ///
> >> + /// if let Entry::Vacant(entry) = guard.get_entry(42) {
> >> + /// let value = KBox::new(0x1337u32, GFP_KERNEL)?;
> >> + /// let borrowed = entry.insert(value)?;
> >> + /// assert_eq!(*borrowed, 0x1337);
> >> + /// }
> >> + ///
> >> + /// assert_eq!(guard.get(42).copied(), Some(0x1337));
> >> + ///
> >> + /// # Ok::<(), kernel::error::Error>(())
> >> + /// ```
> >> + pub fn insert(mut self, value: T) -> Result<T::BorrowedMut<'b>, StoreError<T>> {
> >> + let new = self.insert_internal(value)?;
> >> +
> >> + // SAFETY: `new` came from `T::into_foreign`.The entry has exclusive
> >
> > This is knowledge at a distance. There's no comment anywhere that
> > promises that insert_internal called T::into_foreign.
>
> How would you handle this? Add documentation to `insert_internal`?
I think `insert_internal` can return a reference, which would be
cleaner (i.e. call T::borrow_mut *there*).
>
> >
> >> + // ownership of `new` as it holds a mutable reference to `Guard`.
> >> + Ok(unsafe { T::borrow_mut(new) })
> >> + }
> >> +
> >> + /// Inserts a value and returns an occupied entry representing the newly inserted value.
> >> + ///
> >> + /// - This method will fail if the nodes on the path to the index
> >> + /// represented by this entry are not present in the XArray.
> >> + /// - This method will not drop the XArray lock.
> >> + ///
> >> + /// # Examples
> >> + ///
> >> + /// ```
> >> + /// # use kernel::{prelude::*, xarray::{AllocKind, XArray, Entry}};
> >> + /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
> >> + /// let mut guard = xa.lock();
> >> + ///
> >> + /// assert_eq!(guard.get(42), None);
> >> + ///
> >> + /// if let Entry::Vacant(entry) = guard.get_entry(42) {
> >> + /// let value = KBox::new(0x1337u32, GFP_KERNEL)?;
> >> + /// let occupied = entry.insert_entry(value)?;
> >> + /// assert_eq!(occupied.index(), 42);
> >> + /// }
> >> + ///
> >> + /// assert_eq!(guard.get(42).copied(), Some(0x1337));
> >> + ///
> >> + /// # Ok::<(), kernel::error::Error>(())
> >> + /// ```
> >> + pub fn insert_entry(mut self, value: T) -> Result<OccupiedEntry<'a, 'b, T>, StoreError<T>> {
> >> + let new = self.insert_internal(value)?;
> >> +
> >> + Ok(OccupiedEntry::<'a, 'b, T> {
> >> + state: self.state,
> >> + // SAFETY: `new` came from `T::into_foreign` and is guaranteed non-null.
> >
> > Same.
> >
> >> + ptr: unsafe { core::ptr::NonNull::new_unchecked(new) },
> >> + })
> >> + }
> >> +
> >> + /// Returns the index of this vacant entry.
> >> + ///
> >> + /// # Examples
> >> + ///
> >> + /// ```
> >> + /// # use kernel::{prelude::*, xarray::{AllocKind, XArray, Entry}};
> >> + /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
> >> + /// let mut guard = xa.lock();
> >> + ///
> >> + /// assert_eq!(guard.get(42), None);
> >> + ///
> >> + /// if let Entry::Vacant(entry) = guard.get_entry(42) {
> >> + /// assert_eq!(entry.index(), 42);
> >> + /// }
> >> + ///
> >> + /// # Ok::<(), kernel::error::Error>(())
> >> + /// ```
> >> + pub fn index(&self) -> usize {
> >> + self.state.state.xa_index
> >> + }
> >> +}
> >> +
> >> +/// A view into an occupied entry in an XArray.
> >> +pub struct OccupiedEntry<'a, 'b, T: ForeignOwnable> {
> >> + pub(crate) state: XArrayState<'a, 'b, T>,
> >> + pub(crate) ptr: NonNull<c_void>,
> >> +}
> >> +
> >> +impl<'a, 'b, T> OccupiedEntry<'a, 'b, T>
> >> +where
> >> + T: ForeignOwnable,
> >> +{
> >> + pub(crate) fn new(guard: &'b mut Guard<'a, T>, index: usize, ptr: NonNull<c_void>) -> Self {
> >> + Self {
> >> + state: XArrayState::new(guard, index),
> >> + ptr,
> >> + }
> >> + }
> >> +
> >> + /// Removes the value from this occupied entry and returns it, consuming the entry.
> >> + ///
> >> + /// # Examples
> >> + ///
> >> + /// ```
> >> + /// # use kernel::{prelude::*, xarray::{AllocKind, XArray, Entry}};
> >> + /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
> >> + /// let mut guard = xa.lock();
> >> + ///
> >> + /// guard.store(42, KBox::new(0x1337u32, GFP_KERNEL)?, GFP_KERNEL)?;
> >> + /// assert_eq!(guard.get(42).copied(), Some(0x1337));
> >> + ///
> >> + /// if let Entry::Occupied(entry) = guard.get_entry(42) {
> >> + /// let value = entry.remove();
> >> + /// assert_eq!(*value, 0x1337);
> >> + /// }
> >> + ///
> >> + /// assert_eq!(guard.get(42), None);
> >> + ///
> >> + /// # Ok::<(), kernel::error::Error>(())
> >> + /// ```
> >> + pub fn remove(mut self) -> T {
> >> + // NOTE: Storing NULL to an occupied slot never fails.
> >
> > Shouldn't this be on the debug assert below? Also, is there a citation?
>
> I'll move it.
>
> I don't think I have a citation for that. This is a consequence of the
> data structure design. If the slot is occupied, the node has already
> been allocated, and allocation error is the only failure mode for this path.
OK, if there's no citation, then you've got to document your reasoning
for this conclusion, I think.
>
> >
> >> + // SAFETY: `self.state.state` is properly initialized and valid for XAS operations.
> >> + let ptr = unsafe {
> >> + bindings::xas_result(
> >> + &mut self.state.state,
> >> + bindings::xa_zero_to_null(bindings::xas_store(
> >> + &mut self.state.state,
> >> + core::ptr::null_mut(),
> >> + )),
> >> + )
> >> + };
> >> +
> >> + // SAFETY: `ptr` is a valid return value from xas_result.
> >> + let errno = unsafe { bindings::xa_err(ptr) };
> >> + debug_assert!(errno == 0);
> >> +
> >> + // SAFETY:
> >> + // - `ptr` came from `T::into_foreign`.
> >> + // - As this method takes self by value, the lifetimes of any [`T::Borrowed`] and
> >> + // [`T::BorrowedMut`] we have created must have ended.
> >> + unsafe { T::from_foreign(ptr.cast()) }
> >> + }
> >> +
> >> + /// Returns the index of this occupied entry.
> >> + ///
> >> + /// # Examples
> >> + ///
> >> + /// ```
> >> + /// # use kernel::{prelude::*, xarray::{AllocKind, XArray, Entry}};
> >> + /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
> >> + /// let mut guard = xa.lock();
> >> + ///
> >> + /// guard.store(42, KBox::new(0x1337u32, GFP_KERNEL)?, GFP_KERNEL)?;
> >> + ///
> >> + /// if let Entry::Occupied(entry) = guard.get_entry(42) {
> >> + /// assert_eq!(entry.index(), 42);
> >> + /// }
> >> + ///
> >> + /// # Ok::<(), kernel::error::Error>(())
> >> + /// ```
> >> + pub fn index(&self) -> usize {
> >> + self.state.state.xa_index
> >> + }
> >> +
> >> + /// Replaces the value in this occupied entry and returns the old value.
> >> + ///
> >> + /// # Examples
> >> + ///
> >> + /// ```
> >> + /// # use kernel::{prelude::*, xarray::{AllocKind, XArray, Entry}};
> >> + /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
> >> + /// let mut guard = xa.lock();
> >> + ///
> >> + /// guard.store(42, KBox::new(0x1337u32, GFP_KERNEL)?, GFP_KERNEL)?;
> >> + ///
> >> + /// if let Entry::Occupied(mut entry) = guard.get_entry(42) {
> >> + /// let new_value = KBox::new(0x9999u32, GFP_KERNEL)?;
> >> + /// let old_value = entry.insert(new_value);
> >> + /// assert_eq!(*old_value, 0x1337);
> >> + /// }
> >> + ///
> >> + /// assert_eq!(guard.get(42).copied(), Some(0x9999));
> >> + ///
> >> + /// # Ok::<(), kernel::error::Error>(())
> >> + /// ```
> >> + pub fn insert(&mut self, value: T) -> T {
> >> + // NOTE: Storing to an occupied slot never fails.
> >
> > Citation?
> >
> >> + let new = T::into_foreign(value).cast();
> >> + // SAFETY: `new` came from `T::into_foreign` and is guaranteed non-null.
> >> + self.ptr = unsafe { NonNull::new_unchecked(new) };
> >> +
> >> + // SAFETY: `self.state.state` is properly initialized and valid for XAS operations.
> >> + let old = unsafe {
> >> + bindings::xas_result(
> >> + &mut self.state.state,
> >> + bindings::xa_zero_to_null(bindings::xas_store(&mut selfstate.state, new)),
> >> + )
> >> + };
> >> +
> >> + // SAFETY: `old` is a valid return value from xas_result.
> >> + let errno = unsafe { bindings::xa_err(old) };
> >> + debug_assert!(errno == 0);
> >> +
> >> + // SAFETY:
> >> + // - `ptr` came from `T::into_foreign`.
> >> + // - As this method takes self by value, the lifetimes of any [`T::Borrowed`] and
> >> + // [`T::BorrowedMut`] we have created must have ended.
> >> + unsafe { T::from_foreign(old) }
> >> + }
> >> +
> >> + /// Converts this occupied entry into a mutable reference to the value in the slot represented
> >> + /// by the entry.
> >> + ///
> >> + /// # Examples
> >> + ///
> >> + /// ```
> >> + /// # use kernel::{prelude::*, xarray::{AllocKind, XArray, Entry}};
> >> + /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
> >> + /// let mut guard = xa.lock();
> >> + ///
> >> + /// guard.store(42, KBox::new(0x1337u32, GFP_KERNEL)?, GFP_KERNEL)?;
> >> + ///
> >> + /// if let Entry::Occupied(entry) = guard.get_entry(42) {
> >> + /// let value_ref = entry.into_mut();
> >> + /// *value_ref = 0x9999;
> >> + /// }
> >> + ///
> >> + /// assert_eq!(guard.get(42).copied(), Some(0x9999));
> >> + ///
> >> + /// # Ok::<(), kernel::error::Error>(())
> >> + /// ```
> >> + pub fn into_mut(self) -> T::BorrowedMut<'b> {
> >> + // SAFETY: `ptr` came from `T::into_foreign`.
> >> + unsafe { T::borrow_mut(self.ptr.as_ptr()) }
> >> + }
> >> +
> >> + /// Swaps the value in this entry with the provided value.
> >> + ///
> >> + /// Returns the old value that was in the entry.
> >> + ///
> >> + /// # Examples
> >> + ///
> >> + /// ```
> >> + /// # use kernel::{prelude::*, xarray::{AllocKind, XArray, Entry}};
> >> + /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
> >> + /// let mut guard = xa.lock();
> >> + ///
> >> + /// guard.store(42, KBox::new(100u32, GFP_KERNEL)?, GFP_KERNEL)?;
> >> + ///
> >> + /// if let Entry::Occupied(mut entry) = guard.get_entry(42) {
> >> + /// let old_value = entry.swap(200u32);
> >> + /// assert_eq!(old_value, 100);
> >> + /// assert_eq!(*entry, 200);
> >> + /// }
> >> + ///
> >> + /// # Ok::<(), kernel::error::Error>(())
> >> + /// ```
> >> + pub fn swap<U>(&mut self, mut other: U) -> U
> >> + where
> >> + T: for<'c> ForeignOwnable<Borrowed<'c> = &'c U, BorrowedMut<'c> = &'c mut U>,
> >> + {
> >> + use core::ops::DerefMut;
> >> + core::mem::swap(self.deref_mut(), &mut other);
> >> + other
> >> + }
> >> +}
> >
> > Does this need to return anything?
>
> We probably should take `other` by mutable reference to align with
> `core::mem::swap`.
>
> Thanks for the comments!
>
>
> Best regards,
> Andreas Hindborg
>
>
>
"Tamir Duberstein" <tamird@gmail.com> writes:
> On Thu, Jan 8, 2026 at 4:25 AM Andreas Hindborg <a.hindborg@kernel.org> wrote:
>>
>> Tamir Duberstein <tamird@gmail.com> writes:
>>
>> > On Wed, Dec 3, 2025 at 5:27 PM Andreas Hindborg <a.hindborg@kernel.org> wrote:
>> >>
>> >> Add an Entry API for XArray that provides ergonomic access to array
>> >> slots that may be vacant or occupied. The API follows the pattern of
>> >> Rust's standard library HashMap entry API, allowing efficient
>> >> conditional insertion and modification of entries.
>> >>
>> >> The implementation uses the XArray state API (`xas_*` functions) for
>> >> efficient operations without requiring multiple lookups. Helper
>> >> functions are added to rust/helpers/xarray.c to wrap C macros that are
>> >> not directly accessible from Rust.
>> >>
>> >> Also update MAINTAINERS to cover the new rust files.
>> >>
>> >> Signed-off-by: Andreas Hindborg <a.hindborg@kernel.org>
>> >> ---
>> >> MAINTAINERS | 1 +
>> >> rust/helpers/xarray.c | 17 ++
>> >> rust/kernel/xarray.rs | 112 +++++++++++++
>> >> rust/kernel/xarray/entry.rs | 376 ++++++++++++++++++++++++++++++++++++++++++++
>> >> 4 files changed, 506 insertions(+)
>> >>
>> >> diff --git a/MAINTAINERS b/MAINTAINERS
>> >> index e8f06145fb54c..79d4c9c9b2b63 100644
>> >> --- a/MAINTAINERS
>> >> +++ b/MAINTAINERS
>> >> @@ -27909,6 +27909,7 @@ B: https://github.com/Rust-for-Linux/linux/issues
>> >> C: https://rust-for-linux.zulipchat.com
>> >> T: git https://github.com/Rust-for-Linux/linux.git xarray-next
>> >> F: rust/kernel/xarray.rs
>> >> +F: rust/kernel/xarray/
>> >>
>> >> XBOX DVD IR REMOTE
>> >> M: Benjamin Valentin <benpicco@googlemail.com>
>> >> diff --git a/rust/helpers/xarray.c b/rust/helpers/xarray.c
>> >> index 60b299f11451d..425a6cc494734 100644
>> >> --- a/rust/helpers/xarray.c
>> >> +++ b/rust/helpers/xarray.c
>> >> @@ -26,3 +26,20 @@ void rust_helper_xa_unlock(struct xarray *xa)
>> >> {
>> >> return xa_unlock(xa);
>> >> }
>> >> +
>> >> +void *rust_helper_xas_result(struct xa_state *xas, void *curr)
>> >> +{
>> >> + if (xa_err(xas->xa_node))
>> >> + curr = xas->xa_node;
>> >> + return curr;
>> >> +}
>> >
>> > Instead of this duplication, can we expose `xas_result` from the header?
>>
>> `xas_result` is not currently exported. I'd rather not change that.
>
> Why?
Because it requires patching the C code, which has a very long turn
around time. I also assume that the function is private for a reason.
Exposing it in the header file would make it available to the entire kernel.
<cut>
>> >> +
>> >> + /// Finds the next occupied entry starting at the given index, wrapping around.
>> >> + ///
>> >> + /// Searches for an entry starting at `index` up to the maximum index. If no entry
>> >> + /// is found, wraps around and searches from index 0 up to `index`.
>> >> + ///
>> >> + /// # Examples
>> >> + ///
>> >> + /// ```
>> >> + /// # use kernel::{prelude::*, xarray::{AllocKind, XArray}};
>> >> + /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
>> >> + /// let mut guard = xa.lock();
>> >> + ///
>> >> + /// guard.store(100, KBox::new(42u32, GFP_KERNEL)?, GFP_KERNEL)?;
>> >> + /// let entry = guard.find_next_entry_circular(101);
>> >> + /// assert_eq!(entry.map(|e| e.index()), Some(100));
>> >> + ///
>> >> + /// # Ok::<(), kernel::error::Error>(())
>> >> + /// ```
>> >> + pub fn find_next_entry_circular<'b>(
>> >> + &'b mut self,
>> >> + index: usize,
>> >> + ) -> Option<OccupiedEntry<'a, 'b, T>> {
>> >> + let mut state = XArrayState::new(self, index);
>> >> +
>> >> + // SAFETY: `state.state` is properly initialized by XArrayState::new and the caller holds
>> >> + // the lock.
>> >> + let ptr = NonNull::new(unsafe { bindings::xas_find(&mut statestate, usize::MAX) })
>> >> + .or_else(|| {
>> >> + state.state.xa_node = bindings::XAS_RESTART as *mut bindings::xa_node;
>> >> + state.state.xa_index = 0;
>> >> + // SAFETY: `state.state` is properly initialized and by type invariant, we hold the
>> >> + // xarray lock.
>> >> + NonNull::new(unsafe { bindings::xas_find(&mut state.state, index) })
>> >> + })?;
>> >> +
>> >> + Some(OccupiedEntry { state, ptr })
>> >> + }
>> >
>> > Instead of this function, can find_next_entry take a Range? Then it
>> > would be simple for the caller to wrap if they want, without bloating
>> > this API.
>>
>> We could do that, but I am not sure if it is idiomatic? The range syntax
>> a..b is considered empty if b<a. But it still produces a valid
>> `core::ops::Range` that we could use.
>
> Can you clearly state your objection?
- Reverse ranges are considered empty.
- I am unsure if the approach is idiomatic.
>
>>
>> >
>> >> +
>> >> /// Removes and returns the element at the given index.
>> >> pub fn remove(&mut self, index: usize) -> Option<T> {
>> >> // SAFETY:
>> >> @@ -416,8 +521,15 @@ fn new(access: &'b Guard<'a, T>, index: usize) -> Self {
>> >> },
>> >> }
>> >> }
>> >> +
>> >> + fn status(&self) -> Result {
>> >> + // SAFETY: `self.state` is properly initialized and valid.
>> >> + to_result(unsafe { bindings::xas_error(&self.state) })
>> >> + }
>> >> }
>> >>
>> >> +mod entry;
>> >> +
>> >> // SAFETY: `XArray<T>` has no shared mutable state so it is `Send` iff `T` is `Send`.
>> >> unsafe impl<T: ForeignOwnable + Send> Send for XArray<T> {}
>> >>
>> >> diff --git a/rust/kernel/xarray/entry.rs b/rust/kernel/xarray/entry.rs
>> >> new file mode 100644
>> >> index 0000000000000..1268dc35bac58
>> >> --- /dev/null
>> >> +++ b/rust/kernel/xarray/entry.rs
>> >> @@ -0,0 +1,376 @@
>> >> +// SPDX-License-Identifier: GPL-2.0
>> >> +
>> >> +use super::{
>> >> + Guard,
>> >> + StoreError,
>> >> + XArrayState, //
>> >> +};
>> >> +use core::ptr::NonNull;
>> >> +use kernel::{
>> >> + prelude::*,
>> >> + types::ForeignOwnable, //
>> >> +};
>> >> +
>> >> +/// Represents either a vacant or occupied entry in an XArray.
>> >> +pub enum Entry<'a, 'b, T: ForeignOwnable> {
>> >> + /// A vacant entry that can have a value inserted.
>> >> + Vacant(VacantEntry<'a, 'b, T>),
>> >> + /// An occupied entry containing a value.
>> >> + Occupied(OccupiedEntry<'a, 'b, T>),
>> >> +}
>> >> +
>> >> +impl<T: ForeignOwnable> Entry<'_, '_, T> {
>> >> + /// Returns true if this entry is occupied.
>> >> + ///
>> >> + /// # Examples
>> >> + ///
>> >> + /// ```
>> >> + /// # use kernel::{prelude::*, xarray::{AllocKind, XArray, Entry}};
>> >> + /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
>> >> + /// let mut guard = xa.lock();
>> >> + ///
>> >> + ///
>> >> + /// let entry = guard.get_entry(42);
>> >> + /// assert_eq!(entry.is_occupied(), false);
>> >> + ///
>> >> + /// guard.store(42, KBox::new(0x1337u32, GFP_KERNEL)?, GFP_KERNEL)?;
>> >> + /// let entry = guard.get_entry(42);
>> >> + /// assert_eq!(entry.is_occupied(), true);
>> >> + ///
>> >> + /// # Ok::<(), kernel::error::Error>(())
>> >> + /// ```
>> >> + pub fn is_occupied(&self) -> bool {
>> >> + matches!(self, Entry::Occupied(_))
>> >> + }
>> >
>> > Do we need this? IMO less is more, and even stdlib doesn't have this.
>>
>> Similar to `contains_index`, it de-clutters at call sites. I like
>>
>> if entry.is_occupied() {...}
>>
>> better than
>>
>> if matches!(entry, Entry::Occupied(_)) {...}
>
> Similar to the discussion on `contains_index` -- discarding
> information in this way seems to be a smell, but I can't say without
> seeing more code. My suggestion is not to add this until there's a
> usage that we can see in the same series.
I don't have a user for this one at the moment. I guess I can drop it.
<cut>
>> >> +
>> >> + self.state.status().map(|()| new).map_err(|error| {
>> >> + // SAFETY: `new` came from `T::into_foreign` and `xas_store` does not take ownership of
>> >> + // the value on error.
>> >> + let value = unsafe { T::from_foreign(new) };
>> >> + StoreError { value, error }
>> >> + })
>> >> + }
>> >> +
>> >> + /// Inserts a value into this vacant entry.
>> >> + ///
>> >> + /// Returns a reference to the newly inserted value.
>> >> + ///
>> >> + /// - This method will fail if the nodes on the path to the index
>> >> + /// represented by this entry are not present in the XArray.
>> >> + /// - This method will not drop the XArray lock.
>> >> + ///
>> >> + ///
>> >> + /// # Examples
>> >> + ///
>> >> + /// ```
>> >> + /// # use kernel::{prelude::*, xarray::{AllocKind, XArray, Entry}};
>> >> + /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
>> >> + /// let mut guard = xa.lock();
>> >> + ///
>> >> + /// assert_eq!(guard.get(42), None);
>> >> + ///
>> >> + /// if let Entry::Vacant(entry) = guard.get_entry(42) {
>> >> + /// let value = KBox::new(0x1337u32, GFP_KERNEL)?;
>> >> + /// let borrowed = entry.insert(value)?;
>> >> + /// assert_eq!(*borrowed, 0x1337);
>> >> + /// }
>> >> + ///
>> >> + /// assert_eq!(guard.get(42).copied(), Some(0x1337));
>> >> + ///
>> >> + /// # Ok::<(), kernel::error::Error>(())
>> >> + /// ```
>> >> + pub fn insert(mut self, value: T) -> Result<T::BorrowedMut<'b>, StoreError<T>> {
>> >> + let new = self.insert_internal(value)?;
>> >> +
>> >> + // SAFETY: `new` came from `T::into_foreign`.The entry has exclusive
>> >
>> > This is knowledge at a distance. There's no comment anywhere that
>> > promises that insert_internal called T::into_foreign.
>>
>> How would you handle this? Add documentation to `insert_internal`?
>
> I think `insert_internal` can return a reference, which would be
> cleaner (i.e. call T::borrow_mut *there*).
This does not compose well with the implementation of `insert_entry`,
which needs the void pointer type. `T::BorrowedMut<_>` cannot be turned
back into a pointer, because we do not set any bounds on it.
<cut>
>> >> +/// A view into an occupied entry in an XArray.
>> >> +pub struct OccupiedEntry<'a, 'b, T: ForeignOwnable> {
>> >> + pub(crate) state: XArrayState<'a, 'b, T>,
>> >> + pub(crate) ptr: NonNull<c_void>,
>> >> +}
>> >> +
>> >> +impl<'a, 'b, T> OccupiedEntry<'a, 'b, T>
>> >> +where
>> >> + T: ForeignOwnable,
>> >> +{
>> >> + pub(crate) fn new(guard: &'b mut Guard<'a, T>, index: usize, ptr: NonNull<c_void>) -> Self {
>> >> + Self {
>> >> + state: XArrayState::new(guard, index),
>> >> + ptr,
>> >> + }
>> >> + }
>> >> +
>> >> + /// Removes the value from this occupied entry and returns it, consuming the entry.
>> >> + ///
>> >> + /// # Examples
>> >> + ///
>> >> + /// ```
>> >> + /// # use kernel::{prelude::*, xarray::{AllocKind, XArray, Entry}};
>> >> + /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
>> >> + /// let mut guard = xa.lock();
>> >> + ///
>> >> + /// guard.store(42, KBox::new(0x1337u32, GFP_KERNEL)?, GFP_KERNEL)?;
>> >> + /// assert_eq!(guard.get(42).copied(), Some(0x1337));
>> >> + ///
>> >> + /// if let Entry::Occupied(entry) = guard.get_entry(42) {
>> >> + /// let value = entry.remove();
>> >> + /// assert_eq!(*value, 0x1337);
>> >> + /// }
>> >> + ///
>> >> + /// assert_eq!(guard.get(42), None);
>> >> + ///
>> >> + /// # Ok::<(), kernel::error::Error>(())
>> >> + /// ```
>> >> + pub fn remove(mut self) -> T {
>> >> + // NOTE: Storing NULL to an occupied slot never fails.
>> >
>> > Shouldn't this be on the debug assert below? Also, is there a citation?
>>
>> I'll move it.
>>
>> I don't think I have a citation for that. This is a consequence of the
>> data structure design. If the slot is occupied, the node has already
>> been allocated, and allocation error is the only failure mode for this path.
>
> OK, if there's no citation, then you've got to document your reasoning
> for this conclusion, I think.
Ok, I'll expand the NOTE.
Best regards,
Andreas Hindborg
On Fri, Jan 9, 2026 at 5:38 AM Andreas Hindborg <a.hindborg@kernel.org> wrote:
>
> "Tamir Duberstein" <tamird@gmail.com> writes:
>
> > On Thu, Jan 8, 2026 at 4:25 AM Andreas Hindborg <a.hindborg@kernel.org> wrote:
> >>
> >> Tamir Duberstein <tamird@gmail.com> writes:
> >>
> >> > On Wed, Dec 3, 2025 at 5:27 PM Andreas Hindborg <a.hindborg@kernel.org> wrote:
> >> >>
> >> >> Add an Entry API for XArray that provides ergonomic access to array
> >> >> slots that may be vacant or occupied. The API follows the pattern of
> >> >> Rust's standard library HashMap entry API, allowing efficient
> >> >> conditional insertion and modification of entries.
> >> >>
> >> >> The implementation uses the XArray state API (`xas_*` functions) for
> >> >> efficient operations without requiring multiple lookups. Helper
> >> >> functions are added to rust/helpers/xarray.c to wrap C macros that are
> >> >> not directly accessible from Rust.
> >> >>
> >> >> Also update MAINTAINERS to cover the new rust files.
> >> >>
> >> >> Signed-off-by: Andreas Hindborg <a.hindborg@kernel.org>
> >> >> ---
> >> >> MAINTAINERS | 1 +
> >> >> rust/helpers/xarray.c | 17 ++
> >> >> rust/kernel/xarray.rs | 112 +++++++++++++
> >> >> rust/kernel/xarray/entry.rs | 376 ++++++++++++++++++++++++++++++++++++++++++++
> >> >> 4 files changed, 506 insertions(+)
> >> >>
> >> >> diff --git a/MAINTAINERS b/MAINTAINERS
> >> >> index e8f06145fb54c..79d4c9c9b2b63 100644
> >> >> --- a/MAINTAINERS
> >> >> +++ b/MAINTAINERS
> >> >> @@ -27909,6 +27909,7 @@ B: https://github.com/Rust-for-Linux/linux/issues
> >> >> C: https://rust-for-linux.zulipchat.com
> >> >> T: git https://github.com/Rust-for-Linux/linux.git xarray-next
> >> >> F: rust/kernel/xarray.rs
> >> >> +F: rust/kernel/xarray/
> >> >>
> >> >> XBOX DVD IR REMOTE
> >> >> M: Benjamin Valentin <benpicco@googlemail.com>
> >> >> diff --git a/rust/helpers/xarray.c b/rust/helpers/xarray.c
> >> >> index 60b299f11451d..425a6cc494734 100644
> >> >> --- a/rust/helpers/xarray.c
> >> >> +++ b/rust/helpers/xarray.c
> >> >> @@ -26,3 +26,20 @@ void rust_helper_xa_unlock(struct xarray *xa)
> >> >> {
> >> >> return xa_unlock(xa);
> >> >> }
> >> >> +
> >> >> +void *rust_helper_xas_result(struct xa_state *xas, void *curr)
> >> >> +{
> >> >> + if (xa_err(xas->xa_node))
> >> >> + curr = xas->xa_node;
> >> >> + return curr;
> >> >> +}
> >> >
> >> > Instead of this duplication, can we expose `xas_result` from the header?
> >>
> >> `xas_result` is not currently exported. I'd rather not change that.
> >
> > Why?
>
> Because it requires patching the C code, which has a very long turn
> around time. I also assume that the function is private for a reason.
> Exposing it in the header file would make it available to the entire kernel.
Why assume that? It was probably never needed before. As for
turnaround time - I can empathize, but I don't think this is a strong
argument for duplication.
>
> <cut>
>
> >> >> +
> >> >> + /// Finds the next occupied entry starting at the given index, wrapping around.
> >> >> + ///
> >> >> + /// Searches for an entry starting at `index` up to the maximum index. If no entry
> >> >> + /// is found, wraps around and searches from index 0 up to `index`.
> >> >> + ///
> >> >> + /// # Examples
> >> >> + ///
> >> >> + /// ```
> >> >> + /// # use kernel::{prelude::*, xarray::{AllocKind, XArray}};
> >> >> + /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
> >> >> + /// let mut guard = xa.lock();
> >> >> + ///
> >> >> + /// guard.store(100, KBox::new(42u32, GFP_KERNEL)?, GFP_KERNEL)?;
> >> >> + /// let entry = guard.find_next_entry_circular(101);
> >> >> + /// assert_eq!(entry.map(|e| e.index()), Some(100));
> >> >> + ///
> >> >> + /// # Ok::<(), kernel::error::Error>(())
> >> >> + /// ```
> >> >> + pub fn find_next_entry_circular<'b>(
> >> >> + &'b mut self,
> >> >> + index: usize,
> >> >> + ) -> Option<OccupiedEntry<'a, 'b, T>> {
> >> >> + let mut state = XArrayState::new(self, index);
> >> >> +
> >> >> + // SAFETY: `state.state` is properly initialized by XArrayState::new and the caller holds
> >> >> + // the lock.
> >> >> + let ptr = NonNull::new(unsafe { bindings::xas_find(&mut statestate, usize::MAX) })
> >> >> + .or_else(|| {
> >> >> + state.state.xa_node = bindings::XAS_RESTART as *mut bindings::xa_node;
> >> >> + state.state.xa_index = 0;
> >> >> + // SAFETY: `state.state` is properly initialized and by type invariant, we hold the
> >> >> + // xarray lock.
> >> >> + NonNull::new(unsafe { bindings::xas_find(&mut state.state, index) })
> >> >> + })?;
> >> >> +
> >> >> + Some(OccupiedEntry { state, ptr })
> >> >> + }
> >> >
> >> > Instead of this function, can find_next_entry take a Range? Then it
> >> > would be simple for the caller to wrap if they want, without bloating
> >> > this API.
> >>
> >> We could do that, but I am not sure if it is idiomatic? The range syntax
> >> a..b is considered empty if b<a. But it still produces a valid
> >> `core::ops::Range` that we could use.
> >
> > Can you clearly state your objection?
>
> - Reverse ranges are considered empty.
> - I am unsure if the approach is idiomatic.
>
> >
> >>
> >> >
> >> >> +
> >> >> /// Removes and returns the element at the given index.
> >> >> pub fn remove(&mut self, index: usize) -> Option<T> {
> >> >> // SAFETY:
> >> >> @@ -416,8 +521,15 @@ fn new(access: &'b Guard<'a, T>, index: usize) -> Self {
> >> >> },
> >> >> }
> >> >> }
> >> >> +
> >> >> + fn status(&self) -> Result {
> >> >> + // SAFETY: `self.state` is properly initialized and valid.
> >> >> + to_result(unsafe { bindings::xas_error(&self.state) })
> >> >> + }
> >> >> }
> >> >>
> >> >> +mod entry;
> >> >> +
> >> >> // SAFETY: `XArray<T>` has no shared mutable state so it is `Send` iff `T` is `Send`.
> >> >> unsafe impl<T: ForeignOwnable + Send> Send for XArray<T> {}
> >> >>
> >> >> diff --git a/rust/kernel/xarray/entry.rs b/rust/kernel/xarray/entry.rs
> >> >> new file mode 100644
> >> >> index 0000000000000..1268dc35bac58
> >> >> --- /dev/null
> >> >> +++ b/rust/kernel/xarray/entry.rs
> >> >> @@ -0,0 +1,376 @@
> >> >> +// SPDX-License-Identifier: GPL-2.0
> >> >> +
> >> >> +use super::{
> >> >> + Guard,
> >> >> + StoreError,
> >> >> + XArrayState, //
> >> >> +};
> >> >> +use core::ptr::NonNull;
> >> >> +use kernel::{
> >> >> + prelude::*,
> >> >> + types::ForeignOwnable, //
> >> >> +};
> >> >> +
> >> >> +/// Represents either a vacant or occupied entry in an XArray.
> >> >> +pub enum Entry<'a, 'b, T: ForeignOwnable> {
> >> >> + /// A vacant entry that can have a value inserted.
> >> >> + Vacant(VacantEntry<'a, 'b, T>),
> >> >> + /// An occupied entry containing a value.
> >> >> + Occupied(OccupiedEntry<'a, 'b, T>),
> >> >> +}
> >> >> +
> >> >> +impl<T: ForeignOwnable> Entry<'_, '_, T> {
> >> >> + /// Returns true if this entry is occupied.
> >> >> + ///
> >> >> + /// # Examples
> >> >> + ///
> >> >> + /// ```
> >> >> + /// # use kernel::{prelude::*, xarray::{AllocKind, XArray, Entry}};
> >> >> + /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
> >> >> + /// let mut guard = xa.lock();
> >> >> + ///
> >> >> + ///
> >> >> + /// let entry = guard.get_entry(42);
> >> >> + /// assert_eq!(entry.is_occupied(), false);
> >> >> + ///
> >> >> + /// guard.store(42, KBox::new(0x1337u32, GFP_KERNEL)?, GFP_KERNEL)?;
> >> >> + /// let entry = guard.get_entry(42);
> >> >> + /// assert_eq!(entry.is_occupied(), true);
> >> >> + ///
> >> >> + /// # Ok::<(), kernel::error::Error>(())
> >> >> + /// ```
> >> >> + pub fn is_occupied(&self) -> bool {
> >> >> + matches!(self, Entry::Occupied(_))
> >> >> + }
> >> >
> >> > Do we need this? IMO less is more, and even stdlib doesn't have this.
> >>
> >> Similar to `contains_index`, it de-clutters at call sites. I like
> >>
> >> if entry.is_occupied() {...}
> >>
> >> better than
> >>
> >> if matches!(entry, Entry::Occupied(_)) {...}
> >
> > Similar to the discussion on `contains_index` -- discarding
> > information in this way seems to be a smell, but I can't say without
> > seeing more code. My suggestion is not to add this until there's a
> > usage that we can see in the same series.
>
> I don't have a user for this one at the moment. I guess I can drop it.
>
> <cut>
>
> >> >> +
> >> >> + self.state.status().map(|()| new).map_err(|error| {
> >> >> + // SAFETY: `new` came from `T::into_foreign` and `xas_store` does not take ownership of
> >> >> + // the value on error.
> >> >> + let value = unsafe { T::from_foreign(new) };
> >> >> + StoreError { value, error }
> >> >> + })
> >> >> + }
> >> >> +
> >> >> + /// Inserts a value into this vacant entry.
> >> >> + ///
> >> >> + /// Returns a reference to the newly inserted value.
> >> >> + ///
> >> >> + /// - This method will fail if the nodes on the path to the index
> >> >> + /// represented by this entry are not present in the XArray.
> >> >> + /// - This method will not drop the XArray lock.
> >> >> + ///
> >> >> + ///
> >> >> + /// # Examples
> >> >> + ///
> >> >> + /// ```
> >> >> + /// # use kernel::{prelude::*, xarray::{AllocKind, XArray, Entry}};
> >> >> + /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
> >> >> + /// let mut guard = xa.lock();
> >> >> + ///
> >> >> + /// assert_eq!(guard.get(42), None);
> >> >> + ///
> >> >> + /// if let Entry::Vacant(entry) = guard.get_entry(42) {
> >> >> + /// let value = KBox::new(0x1337u32, GFP_KERNEL)?;
> >> >> + /// let borrowed = entry.insert(value)?;
> >> >> + /// assert_eq!(*borrowed, 0x1337);
> >> >> + /// }
> >> >> + ///
> >> >> + /// assert_eq!(guard.get(42).copied(), Some(0x1337));
> >> >> + ///
> >> >> + /// # Ok::<(), kernel::error::Error>(())
> >> >> + /// ```
> >> >> + pub fn insert(mut self, value: T) -> Result<T::BorrowedMut<'b>, StoreError<T>> {
> >> >> + let new = self.insert_internal(value)?;
> >> >> +
> >> >> + // SAFETY: `new` came from `T::into_foreign`.The entry has exclusive
> >> >
> >> > This is knowledge at a distance. There's no comment anywhere that
> >> > promises that insert_internal called T::into_foreign.
> >>
> >> How would you handle this? Add documentation to `insert_internal`?
> >
> > I think `insert_internal` can return a reference, which would be
> > cleaner (i.e. call T::borrow_mut *there*).
>
> This does not compose well with the implementation of `insert_entry`,
> which needs the void pointer type. `T::BorrowedMut<_>` cannot be turned
> back into a pointer, because we do not set any bounds on it.
I confess that this discussion exceeds what I can do in an email. I'll
take a look at this again in the next version and if I can suggest a
refactor, I will.
>
> <cut>
>
> >> >> +/// A view into an occupied entry in an XArray.
> >> >> +pub struct OccupiedEntry<'a, 'b, T: ForeignOwnable> {
> >> >> + pub(crate) state: XArrayState<'a, 'b, T>,
> >> >> + pub(crate) ptr: NonNull<c_void>,
> >> >> +}
> >> >> +
> >> >> +impl<'a, 'b, T> OccupiedEntry<'a, 'b, T>
> >> >> +where
> >> >> + T: ForeignOwnable,
> >> >> +{
> >> >> + pub(crate) fn new(guard: &'b mut Guard<'a, T>, index: usize, ptr: NonNull<c_void>) -> Self {
> >> >> + Self {
> >> >> + state: XArrayState::new(guard, index),
> >> >> + ptr,
> >> >> + }
> >> >> + }
> >> >> +
> >> >> + /// Removes the value from this occupied entry and returns it, consuming the entry.
> >> >> + ///
> >> >> + /// # Examples
> >> >> + ///
> >> >> + /// ```
> >> >> + /// # use kernel::{prelude::*, xarray::{AllocKind, XArray, Entry}};
> >> >> + /// let mut xa = KBox::pin_init(XArray::<KBox<u32>>::new(AllocKind::Alloc), GFP_KERNEL)?;
> >> >> + /// let mut guard = xa.lock();
> >> >> + ///
> >> >> + /// guard.store(42, KBox::new(0x1337u32, GFP_KERNEL)?, GFP_KERNEL)?;
> >> >> + /// assert_eq!(guard.get(42).copied(), Some(0x1337));
> >> >> + ///
> >> >> + /// if let Entry::Occupied(entry) = guard.get_entry(42) {
> >> >> + /// let value = entry.remove();
> >> >> + /// assert_eq!(*value, 0x1337);
> >> >> + /// }
> >> >> + ///
> >> >> + /// assert_eq!(guard.get(42), None);
> >> >> + ///
> >> >> + /// # Ok::<(), kernel::error::Error>(())
> >> >> + /// ```
> >> >> + pub fn remove(mut self) -> T {
> >> >> + // NOTE: Storing NULL to an occupied slot never fails.
> >> >
> >> > Shouldn't this be on the debug assert below? Also, is there a citation?
> >>
> >> I'll move it.
> >>
> >> I don't think I have a citation for that. This is a consequence of the
> >> data structure design. If the slot is occupied, the node has already
> >> been allocated, and allocation error is the only failure mode for this path.
> >
> > OK, if there's no citation, then you've got to document your reasoning
> > for this conclusion, I think.
>
> Ok, I'll expand the NOTE.
>
>
> Best regards,
> Andreas Hindborg
>
>
Thanks!
© 2016 - 2026 Red Hat, Inc.