Message-ID: <CAJ-ks9kfsrNzBU5fL=rxhc_vRvoz+R0o=1DsWzo+k+BF5-xbSg@mail.gmail.com>
Date: Fri, 9 Jan 2026 11:00:59 -0500
From: Tamir Duberstein <tamird@...il.com>
To: Andreas Hindborg <a.hindborg@...nel.org>
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

On Fri, Jan 9, 2026 at 5:38 AM Andreas Hindborg <a.hindborg@...nel.org> wrote:
>
> "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.

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!

Powered by blists - more mailing lists