[PATCH v2 0/4] rust: xarray: abstract xa_alloc and xa_alloc_cyclic

[PATCH v2 0/4] rust: xarray: abstract xa_alloc and xa_alloc_cyclic

[Onur Özkan]

Second version of xa_alloc and xa_alloc_cyclic abstraction
patch series. See the initial version at [1].

[1]: https://lore.kernel.org/all/DDCV43KW9OGL.27I8HP4TSTQ6N@kernel.org/T/#u

This series will also be sent to linux-mm@kvack.org which was not done in
the previous submission.

Changes in v2:
  - Moved the pointer check into the constructor function.
  - Minor updates on the function doc-comments.
  - Minor updates on xa_alloc and xa_alloc_cyclic commit descriptions.
  - Replaced bindings::xa_limit with Range<u32> on xa_alloc_cyclic and
    xa_alloc.
  - Updated how alloc_cyclic handles the next pointer (it no longer
    requires a mutable reference)

Onur Özkan (4):
  rust: xarray: move pointer check into `XArray::new`
  rust: xarray: abstract `xa_alloc`
  rust: xarray: abstract `xa_alloc_cyclic`
  remove completed task from nova-core task list

 Documentation/gpu/nova/core/todo.rst |   8 ---
 rust/kernel/xarray.rs                | 101 +++++++++++++++++++++++++--
 2 files changed, 96 insertions(+), 13 deletions(-)

--
2.51.0

[PATCH v2 1/4] rust: xarray: move pointer check into `XArray::new`

[Onur Özkan]

There will be multiple functions that will store into XArray.
It's not ideal to duplicate this check in all of them. Moving it
into the constructor function will remove the need for duplication.

Signed-off-by: Onur Özkan <work@onurozkan.dev>
---
 rust/kernel/xarray.rs | 10 ++++++----
 1 file changed, 6 insertions(+), 4 deletions(-)

diff --git a/rust/kernel/xarray.rs b/rust/kernel/xarray.rs
index a49d6db28845..90e27cd5197e 100644
--- a/rust/kernel/xarray.rs
+++ b/rust/kernel/xarray.rs
@@ -87,6 +87,12 @@ pub enum AllocKind {
 impl<T: ForeignOwnable> XArray<T> {
     /// Creates a new initializer for this type.
     pub fn new(kind: AllocKind) -> impl PinInit<Self> {
+        // Ensure pointers stored in XArray are suitably aligned.
+        build_assert!(
+            T::FOREIGN_ALIGN >= 4,
+            "pointers stored in XArray must be 4-byte aligned"
+        );
+
         let flags = match kind {
             AllocKind::Alloc => bindings::XA_FLAGS_ALLOC,
             AllocKind::Alloc1 => bindings::XA_FLAGS_ALLOC1,
@@ -230,10 +236,6 @@ pub fn store(
         value: T,
         gfp: alloc::Flags,
     ) -> Result<Option<T>, StoreError<T>> {
-        build_assert!(
-            T::FOREIGN_ALIGN >= 4,
-            "pointers stored in XArray must be 4-byte aligned"
-        );
         let new = value.into_foreign();

         let old = {
--
2.51.0

[PATCH v2 2/4] rust: xarray: abstract `xa_alloc`

[Onur Özkan]

Implements `alloc` function to `XArray<T>` that wraps
`xa_alloc` safely, which will be used to generate the
auxiliary device IDs.

Resolves a task from the nova/core task list under the "XArray
bindings [XARR]" section in "Documentation/gpu/nova/core/todo.rst"
file.

Signed-off-by: Onur Özkan <work@onurozkan.dev>
---
 rust/kernel/xarray.rs | 41 ++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 40 insertions(+), 1 deletion(-)

diff --git a/rust/kernel/xarray.rs b/rust/kernel/xarray.rs
index 90e27cd5197e..0711ccf99fb4 100644
--- a/rust/kernel/xarray.rs
+++ b/rust/kernel/xarray.rs
@@ -10,7 +10,7 @@
     ffi::c_void,
     types::{ForeignOwnable, NotThreadSafe, Opaque},
 };
-use core::{iter, marker::PhantomData, pin::Pin, ptr::NonNull};
+use core::{iter, marker::PhantomData, ops::Range, pin::Pin, ptr::NonNull};
 use pin_init::{pin_data, pin_init, pinned_drop, PinInit};

 /// An array which efficiently maps sparse integer indices to owned objects.
@@ -268,6 +268,45 @@ pub fn store(
             Ok(unsafe { T::try_from_foreign(old) })
         }
     }
+
+    /// Allocates an empty slot within the given `limit` and stores `value` there.
+    ///
+    /// May drop the lock if needed to allocate memory, and then reacquire it afterwards.
+    ///
+    /// On success, returns the allocated index.
+    ///
+    /// On failure, returns the element which was attempted to be stored.
+    pub fn alloc(
+        &mut self,
+        limit: Range<u32>,
+        value: T,
+        gfp: alloc::Flags,
+    ) -> Result<u32, StoreError<T>> {
+        let new = value.into_foreign();
+        let mut id: u32 = 0;
+
+        let limit = bindings::xa_limit {
+            min: limit.start,
+            max: limit.end,
+        };
+
+        // SAFETY:
+        // - `self.xa.xa` is valid by the type invariant.
+        // - `new` came from `T::into_foreign`.
+        let ret =
+            unsafe { bindings::__xa_alloc(self.xa.xa.get(), &mut id, new, limit, gfp.as_raw()) };
+
+        if ret < 0 {
+            // SAFETY: `__xa_alloc` doesn't take ownership on error.
+            let value = unsafe { T::from_foreign(new) };
+            return Err(StoreError {
+                value,
+                error: Error::from_errno(ret),
+            });
+        }
+
+        Ok(id)
+    }
 }

 // SAFETY: `XArray<T>` has no shared mutable state so it is `Send` iff `T` is `Send`.
--
2.51.0

Re: [PATCH v2 2/4] rust: xarray: abstract `xa_alloc`

[Alice Ryhl]

On Wed, Oct 08, 2025 at 03:46:17PM +0300, Onur Özkan wrote:
> Implements `alloc` function to `XArray<T>` that wraps
> `xa_alloc` safely, which will be used to generate the
> auxiliary device IDs.
> 
> Resolves a task from the nova/core task list under the "XArray
> bindings [XARR]" section in "Documentation/gpu/nova/core/todo.rst"
> file.
> 
> Signed-off-by: Onur Özkan <work@onurozkan.dev>
> ---
>  rust/kernel/xarray.rs | 41 ++++++++++++++++++++++++++++++++++++++++-
>  1 file changed, 40 insertions(+), 1 deletion(-)
> 
> diff --git a/rust/kernel/xarray.rs b/rust/kernel/xarray.rs
> index 90e27cd5197e..0711ccf99fb4 100644
> --- a/rust/kernel/xarray.rs
> +++ b/rust/kernel/xarray.rs
> @@ -10,7 +10,7 @@
>      ffi::c_void,
>      types::{ForeignOwnable, NotThreadSafe, Opaque},
>  };
> -use core::{iter, marker::PhantomData, pin::Pin, ptr::NonNull};
> +use core::{iter, marker::PhantomData, ops::Range, pin::Pin, ptr::NonNull};
>  use pin_init::{pin_data, pin_init, pinned_drop, PinInit};
> 
>  /// An array which efficiently maps sparse integer indices to owned objects.
> @@ -268,6 +268,45 @@ pub fn store(
>              Ok(unsafe { T::try_from_foreign(old) })
>          }
>      }
> +
> +    /// Allocates an empty slot within the given `limit` and stores `value` there.
> +    ///
> +    /// May drop the lock if needed to allocate memory, and then reacquire it afterwards.
> +    ///
> +    /// On success, returns the allocated index.
> +    ///
> +    /// On failure, returns the element which was attempted to be stored.
> +    pub fn alloc(
> +        &mut self,
> +        limit: Range<u32>,

The Range type is inclusive/exclusive but xa_limit is
inclusive/inclusive. They should match to avoid confusion.

Alice

Re: [PATCH v2 2/4] rust: xarray: abstract `xa_alloc`

[Matthew Wilcox]

On Wed, Oct 08, 2025 at 01:04:11PM +0000, Alice Ryhl wrote:
> > +        limit: Range<u32>,
> 
> The Range type is inclusive/exclusive but xa_limit is
> inclusive/inclusive. They should match to avoid confusion.

... and xa_limit is inclusive at the top end to be sure that we can
actually allocate 2^32-1.  Or does Range handle that by using 0 to mean
that 2^32-1 is allowed?
> 

Re: [PATCH v2 2/4] rust: xarray: abstract `xa_alloc`

[Alice Ryhl]

On Wed, Oct 8, 2025 at 3:40 PM Matthew Wilcox <willy@infradead.org> wrote:
>
> On Wed, Oct 08, 2025 at 01:04:11PM +0000, Alice Ryhl wrote:
> > > +        limit: Range<u32>,
> >
> > The Range type is inclusive/exclusive but xa_limit is
> > inclusive/inclusive. They should match to avoid confusion.
>
> ... and xa_limit is inclusive at the top end to be sure that we can
> actually allocate 2^32-1.  Or does Range handle that by using 0 to mean
> that 2^32-1 is allowed?

Rust has multiple range types for inclusive and exclusive cases. The
Range type is usually used for indexing arrays where the length fits
in the integer type. To include 2^32-1, you have to use RangeInclusive
instead of Range. It should be possible to write code that handles all
of the range types without repetition.

Alice

Re: [PATCH v2 2/4] rust: xarray: abstract `xa_alloc`

[Tamir Duberstein]

On Wed, Oct 8, 2025 at 6:05 AM Onur Özkan <work@onurozkan.dev> wrote:
>
> Implements `alloc` function to `XArray<T>` that wraps
> `xa_alloc` safely, which will be used to generate the
> auxiliary device IDs.
>
> Resolves a task from the nova/core task list under the "XArray
> bindings [XARR]" section in "Documentation/gpu/nova/core/todo.rst"
> file.
>
> Signed-off-by: Onur Özkan <work@onurozkan.dev>
> ---
>  rust/kernel/xarray.rs | 41 ++++++++++++++++++++++++++++++++++++++++-
>  1 file changed, 40 insertions(+), 1 deletion(-)
>
> diff --git a/rust/kernel/xarray.rs b/rust/kernel/xarray.rs
> index 90e27cd5197e..0711ccf99fb4 100644
> --- a/rust/kernel/xarray.rs
> +++ b/rust/kernel/xarray.rs
> @@ -10,7 +10,7 @@
>      ffi::c_void,
>      types::{ForeignOwnable, NotThreadSafe, Opaque},
>  };
> -use core::{iter, marker::PhantomData, pin::Pin, ptr::NonNull};
> +use core::{iter, marker::PhantomData, ops::Range, pin::Pin, ptr::NonNull};
>  use pin_init::{pin_data, pin_init, pinned_drop, PinInit};
>
>  /// An array which efficiently maps sparse integer indices to owned objects.
> @@ -268,6 +268,45 @@ pub fn store(
>              Ok(unsafe { T::try_from_foreign(old) })
>          }
>      }
> +
> +    /// Allocates an empty slot within the given `limit` and stores `value` there.
> +    ///
> +    /// May drop the lock if needed to allocate memory, and then reacquire it afterwards.
> +    ///
> +    /// On success, returns the allocated index.

Returning the index is not a very good abstraction. Would the
reservation API meet your needs?

https://lore.kernel.org/all/20250713-xarray-insert-reserve-v2-3-b939645808a2@gmail.com/

If yes, I would appreciate your tags there.

Re: [PATCH v2 2/4] rust: xarray: abstract `xa_alloc`

[Onur Özkan]

On Wed, 8 Oct 2025 09:59:12 -0700
Tamir Duberstein <tamird@gmail.com> wrote:

> On Wed, Oct 8, 2025 at 6:05 AM Onur Özkan <work@onurozkan.dev> wrote:
> >
> > Implements `alloc` function to `XArray<T>` that wraps
> > `xa_alloc` safely, which will be used to generate the
> > auxiliary device IDs.
> >
> > Resolves a task from the nova/core task list under the "XArray
> > bindings [XARR]" section in "Documentation/gpu/nova/core/todo.rst"
> > file.
> >
> > Signed-off-by: Onur Özkan <work@onurozkan.dev>
> > ---
> >  rust/kernel/xarray.rs | 41
> > ++++++++++++++++++++++++++++++++++++++++- 1 file changed, 40
> > insertions(+), 1 deletion(-)
> >
> > diff --git a/rust/kernel/xarray.rs b/rust/kernel/xarray.rs
> > index 90e27cd5197e..0711ccf99fb4 100644
> > --- a/rust/kernel/xarray.rs
> > +++ b/rust/kernel/xarray.rs
> > @@ -10,7 +10,7 @@
> >      ffi::c_void,
> >      types::{ForeignOwnable, NotThreadSafe, Opaque},
> >  };
> > -use core::{iter, marker::PhantomData, pin::Pin, ptr::NonNull};
> > +use core::{iter, marker::PhantomData, ops::Range, pin::Pin,
> > ptr::NonNull}; use pin_init::{pin_data, pin_init, pinned_drop,
> > PinInit};
> >
> >  /// An array which efficiently maps sparse integer indices to
> > owned objects. @@ -268,6 +268,45 @@ pub fn store(
> >              Ok(unsafe { T::try_from_foreign(old) })
> >          }
> >      }
> > +
> > +    /// Allocates an empty slot within the given `limit` and
> > stores `value` there.
> > +    ///
> > +    /// May drop the lock if needed to allocate memory, and then
> > reacquire it afterwards.
> > +    ///
> > +    /// On success, returns the allocated index.
> 
> Returning the index is not a very good abstraction. Would the
> reservation API meet your needs?
> 
> https://lore.kernel.org/all/20250713-xarray-insert-reserve-v2-3-b939645808a2@gmail.com/
> 
> If yes, I would appreciate your tags there.

It should be "allocated key", I misdocumented it. I don't have a
use-case for this implementation, I am just trying to help on the nova
task list:
    https://docs.kernel.org/gpu/nova/core/todo.html#xarray-bindings-xarr

The task mentions "generate the auxiliary device IDs", which should be
the returned key, right?

There is also this reference [1] that shows that the returned key will
be useful.

[1]: https://lore.kernel.org/all/aOTyVzpJNDOaxxs6@google.com/

Regards,
Onur

Re: [PATCH v2 2/4] rust: xarray: abstract `xa_alloc`

[Tamir Duberstein]

On Wed, Oct 8, 2025 at 12:50 PM Onur Özkan <work@onurozkan.dev> wrote:
>
> On Wed, 8 Oct 2025 09:59:12 -0700
> Tamir Duberstein <tamird@gmail.com> wrote:
>
> > On Wed, Oct 8, 2025 at 6:05 AM Onur Özkan <work@onurozkan.dev> wrote:
> > >
> > > Implements `alloc` function to `XArray<T>` that wraps
> > > `xa_alloc` safely, which will be used to generate the
> > > auxiliary device IDs.
> > >
> > > Resolves a task from the nova/core task list under the "XArray
> > > bindings [XARR]" section in "Documentation/gpu/nova/core/todo.rst"
> > > file.
> > >
> > > Signed-off-by: Onur Özkan <work@onurozkan.dev>
> > > ---
> > >  rust/kernel/xarray.rs | 41
> > > ++++++++++++++++++++++++++++++++++++++++- 1 file changed, 40
> > > insertions(+), 1 deletion(-)
> > >
> > > diff --git a/rust/kernel/xarray.rs b/rust/kernel/xarray.rs
> > > index 90e27cd5197e..0711ccf99fb4 100644
> > > --- a/rust/kernel/xarray.rs
> > > +++ b/rust/kernel/xarray.rs
> > > @@ -10,7 +10,7 @@
> > >      ffi::c_void,
> > >      types::{ForeignOwnable, NotThreadSafe, Opaque},
> > >  };
> > > -use core::{iter, marker::PhantomData, pin::Pin, ptr::NonNull};
> > > +use core::{iter, marker::PhantomData, ops::Range, pin::Pin,
> > > ptr::NonNull}; use pin_init::{pin_data, pin_init, pinned_drop,
> > > PinInit};
> > >
> > >  /// An array which efficiently maps sparse integer indices to
> > > owned objects. @@ -268,6 +268,45 @@ pub fn store(
> > >              Ok(unsafe { T::try_from_foreign(old) })
> > >          }
> > >      }
> > > +
> > > +    /// Allocates an empty slot within the given `limit` and
> > > stores `value` there.
> > > +    ///
> > > +    /// May drop the lock if needed to allocate memory, and then
> > > reacquire it afterwards.
> > > +    ///
> > > +    /// On success, returns the allocated index.
> >
> > Returning the index is not a very good abstraction. Would the
> > reservation API meet your needs?
> >
> > https://lore.kernel.org/all/20250713-xarray-insert-reserve-v2-3-b939645808a2@gmail.com/
> >
> > If yes, I would appreciate your tags there.
>
> It should be "allocated key", I misdocumented it. I don't have a
> use-case for this implementation, I am just trying to help on the nova
> task list:
>     https://docs.kernel.org/gpu/nova/core/todo.html#xarray-bindings-xarr

I think implementing things without understanding the use-case is a
good way to build the wrong thing.

> The task mentions "generate the auxiliary device IDs", which should be
> the returned key, right?

I dunno.

> There is also this reference [1] that shows that the returned key will
> be useful.
>
> [1]: https://lore.kernel.org/all/aOTyVzpJNDOaxxs6@google.com/

Sure, it's useful - the reservation API also exposes it. But it is not
a proper abstraction.

Cheers.

Tamir

Re: [PATCH v2 2/4] rust: xarray: abstract `xa_alloc`

[Onur Özkan]

On Wed, 8 Oct 2025 13:45:53 -0700
Tamir Duberstein <tamird@gmail.com> wrote:

> On Wed, Oct 8, 2025 at 12:50 PM Onur Özkan <work@onurozkan.dev> wrote:
> >
> > On Wed, 8 Oct 2025 09:59:12 -0700
> > Tamir Duberstein <tamird@gmail.com> wrote:
> >
> > > On Wed, Oct 8, 2025 at 6:05 AM Onur Özkan <work@onurozkan.dev>
> > > wrote:
> > > >
> > > > Implements `alloc` function to `XArray<T>` that wraps
> > > > `xa_alloc` safely, which will be used to generate the
> > > > auxiliary device IDs.
> > > >
> > > > Resolves a task from the nova/core task list under the "XArray
> > > > bindings [XARR]" section in
> > > > "Documentation/gpu/nova/core/todo.rst" file.
> > > >
> > > > Signed-off-by: Onur Özkan <work@onurozkan.dev>
> > > > ---
> > > >  rust/kernel/xarray.rs | 41
> > > > ++++++++++++++++++++++++++++++++++++++++- 1 file changed, 40
> > > > insertions(+), 1 deletion(-)
> > > >
> > > > diff --git a/rust/kernel/xarray.rs b/rust/kernel/xarray.rs
> > > > index 90e27cd5197e..0711ccf99fb4 100644
> > > > --- a/rust/kernel/xarray.rs
> > > > +++ b/rust/kernel/xarray.rs
> > > > @@ -10,7 +10,7 @@
> > > >      ffi::c_void,
> > > >      types::{ForeignOwnable, NotThreadSafe, Opaque},
> > > >  };
> > > > -use core::{iter, marker::PhantomData, pin::Pin, ptr::NonNull};
> > > > +use core::{iter, marker::PhantomData, ops::Range, pin::Pin,
> > > > ptr::NonNull}; use pin_init::{pin_data, pin_init, pinned_drop,
> > > > PinInit};
> > > >
> > > >  /// An array which efficiently maps sparse integer indices to
> > > > owned objects. @@ -268,6 +268,45 @@ pub fn store(
> > > >              Ok(unsafe { T::try_from_foreign(old) })
> > > >          }
> > > >      }
> > > > +
> > > > +    /// Allocates an empty slot within the given `limit` and
> > > > stores `value` there.
> > > > +    ///
> > > > +    /// May drop the lock if needed to allocate memory, and
> > > > then reacquire it afterwards.
> > > > +    ///
> > > > +    /// On success, returns the allocated index.
> > >
> > > Returning the index is not a very good abstraction. Would the
> > > reservation API meet your needs?
> > >
> > > https://lore.kernel.org/all/20250713-xarray-insert-reserve-v2-3-b939645808a2@gmail.com/
> > >
> > > If yes, I would appreciate your tags there.
> >
> > It should be "allocated key", I misdocumented it. I don't have a
> > use-case for this implementation, I am just trying to help on the
> > nova task list:
> >     https://docs.kernel.org/gpu/nova/core/todo.html#xarray-bindings-xarr
> 
> I think implementing things without understanding the use-case is a
> good way to build the wrong thing.
> 

I was thinking I would get some review notes from people who actually
need this if something wasn't right. Maybe Alexandre can clarify what
the expected outcome was, since he created the task.

Onur

> > The task mentions "generate the auxiliary device IDs", which should
> > be the returned key, right?
> 
> I dunno.
> 
> > There is also this reference [1] that shows that the returned key
> > will be useful.
> >
> > [1]: https://lore.kernel.org/all/aOTyVzpJNDOaxxs6@google.com/
> 
> Sure, it's useful - the reservation API also exposes it. But it is not
> a proper abstraction.
> 
> Cheers.
> 
> Tamir

[PATCH v2 3/4] rust: xarray: abstract `xa_alloc_cyclic`

[Onur Özkan]

Implements `alloc_cyclic` function to `XArray<T>` that
wraps `xa_alloc_cyclic` safely, which will be used to
generate the auxiliary device IDs.

Resolves a task from the nova/core task list under the "XArray
bindings [XARR]" section in "Documentation/gpu/nova/core/todo.rst"
file.

Signed-off-by: Onur Özkan <work@onurozkan.dev>
---
 rust/kernel/xarray.rs | 50 +++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 50 insertions(+)

diff --git a/rust/kernel/xarray.rs b/rust/kernel/xarray.rs
index 0711ccf99fb4..8ac7210afd6b 100644
--- a/rust/kernel/xarray.rs
+++ b/rust/kernel/xarray.rs
@@ -307,6 +307,56 @@ pub fn alloc(

         Ok(id)
     }
+
+    /// Allocates an empty slot within the given `limit`, storing `value` and cycling from `*next`.
+    ///
+    /// May drop the lock if needed to allocate memory, and then reacquire it afterwards.
+    ///
+    /// On success, returns the allocated index and the next pointer respectively.
+    ///
+    /// On failure, returns the element which was attempted to be stored.
+    pub fn alloc_cyclic(
+        &mut self,
+        limit: Range<u32>,
+        mut next: u32,
+        value: T,
+        gfp: alloc::Flags,
+    ) -> Result<(u32, u32), StoreError<T>> {
+        let new = value.into_foreign();
+
+        let limit = bindings::xa_limit {
+            min: limit.start,
+            max: limit.end,
+        };
+
+        // `__xa_alloc_cyclic` overwrites this.
+        let mut id: u32 = 0;
+
+        // SAFETY:
+        // - `self.xa.xa` is valid by the type invariant.
+        // - `new` came from `T::into_foreign`.
+        let ret = unsafe {
+            bindings::__xa_alloc_cyclic(
+                self.xa.xa.get(),
+                &mut id,
+                new,
+                limit,
+                &mut next,
+                gfp.as_raw(),
+            )
+        };
+
+        if ret < 0 {
+            // SAFETY: `__xa_alloc_cyclic` doesn't take ownership on error.
+            let value = unsafe { T::from_foreign(new) };
+            return Err(StoreError {
+                value,
+                error: Error::from_errno(ret),
+            });
+        }
+
+        Ok((id, next))
+    }
 }

 // SAFETY: `XArray<T>` has no shared mutable state so it is `Send` iff `T` is `Send`.
--
2.51.0

[PATCH v2 4/4] remove completed task from nova-core task list

[Onur Özkan]

The task is completed in this series.

Signed-off-by: Onur Özkan <work@onurozkan.dev>
---
 Documentation/gpu/nova/core/todo.rst | 8 --------
 1 file changed, 8 deletions(-)

diff --git a/Documentation/gpu/nova/core/todo.rst b/Documentation/gpu/nova/core/todo.rst
index 0972cb905f7a..de70a857fcfd 100644
--- a/Documentation/gpu/nova/core/todo.rst
+++ b/Documentation/gpu/nova/core/todo.rst
@@ -210,14 +210,6 @@ capability, MSI API abstractions.

 | Complexity: Beginner

-XArray bindings [XARR]
-----------------------
-
-We need bindings for `xa_alloc`/`xa_alloc_cyclic` in order to generate the
-auxiliary device IDs.
-
-| Complexity: Intermediate
-
 Debugfs abstractions
 --------------------

--
2.51.0