Message-ID: <87qzrzf4ya.fsf@t14s.mail-host-address-is-not-set>
Date: Fri, 09 Jan 2026 11:36:29 +0100
From: Andreas Hindborg <a.hindborg@...nel.org>
To: Tamir Duberstein <tamird@...il.com>
Cc: Miguel Ojeda <ojeda@...nel.org>, Alex Gaynor <alex.gaynor@...il.com>,
 Boqun Feng <boqun.feng@...il.com>, Gary Guo <gary@...yguo.net>,
 Björn Roy
 Baron <bjorn3_gh@...tonmail.com>, Benno Lossin <lossin@...nel.org>, Alice
 Ryhl <aliceryhl@...gle.com>, Trevor Gross <tmgross@...ch.edu>, Danilo
 Krummrich <dakr@...nel.org>, Daniel Gomez <da.gomez@...nel.org>,
 rust-for-linux@...r.kernel.org, linux-kernel@...r.kernel.org
Subject: Re: [PATCH 08/10] rust: xarray: add entry API

"Tamir Duberstein" <tamird@...il.com> writes:

> On Thu, Jan 8, 2026 at 4:25 AM Andreas Hindborg <a.hindborg@...nel.org> wrote:
>>
>> Tamir Duberstein <tamird@...il.com> writes:
>>
>> > On Wed, Dec 3, 2025 at 5:27 PM Andreas Hindborg <a.hindborg@...nel.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@...nel.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@...glemail.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

Powered by blists - more mailing lists