1. Patchew
  2. linux
  3. View series

[PATCH] rust: bitmap: encourage using xarray/maple_tree instead of id_pool

Alice Ryhl posted 1 patch 2 weeks ago 
MAINTAINERS                         |  2 +-
drivers/android/binder/process.rs   |  2 +-
rust/kernel/bitmap.rs               |  2 ++
rust/kernel/{ => bitmap}/id_pool.rs | 26 +++++++++++++++++++-------
rust/kernel/lib.rs                  |  1 -
5 files changed, 23 insertions(+), 10 deletions(-)
[PATCH] rust: bitmap: encourage using xarray/maple_tree instead of id_pool
Posted by Alice Ryhl 2 weeks ago 
The id_pool.rs file was added for use in the Binder driver, which is
using a bitmap rather than the normal IDR implementation due its
specialized needs and performance/spinlock requirements. However, its
current name as kernel::id_pool encourages using it over other IDR
solutions.

To discourage choosing this pool when you don't need it, move it to
kernel::bitmap and add a comment recommending the xarray or maple tree
for generic IDR use-cases.

Please see the below links for the discussion that prompted moving this
file.

Link: https://lore.kernel.org/rust-for-linux/2026070334-dollar-hexagram-e49c@gregkh/
Link: https://lore.kernel.org/rust-for-linux/84bc8bd2-e292-4b84-9580-a1b5df4c5bdc@nvidia.com/
Link: https://lore.kernel.org/rust-for-linux/20260711063602.426311-1-ynorov@nvidia.com/
Signed-off-by: Alice Ryhl <aliceryhl@google.com>
---
 MAINTAINERS                         |  2 +-
 drivers/android/binder/process.rs   |  2 +-
 rust/kernel/bitmap.rs               |  2 ++
 rust/kernel/{ => bitmap}/id_pool.rs | 26 +++++++++++++++++++-------
 rust/kernel/lib.rs                  |  1 -
 5 files changed, 23 insertions(+), 10 deletions(-)

diff --git a/MAINTAINERS b/MAINTAINERS
index 4a8b0fd665ce..d80377d06c3a 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -4639,7 +4639,7 @@ R:	Yury Norov <yury.norov@gmail.com>
 S:	Maintained
 F:	lib/find_bit_benchmark_rust.rs
 F:	rust/kernel/bitmap.rs
-F:	rust/kernel/id_pool.rs
+F:	rust/kernel/bitmap/
 
 BITOPS API
 M:	Yury Norov <yury.norov@gmail.com>
diff --git a/drivers/android/binder/process.rs b/drivers/android/binder/process.rs
index 96b8440ceac6..eec417604806 100644
--- a/drivers/android/binder/process.rs
+++ b/drivers/android/binder/process.rs
@@ -16,10 +16,10 @@
 
 use kernel::{
     bindings,
+    bitmap::id_pool::IdPool,
     cred::Credential,
     error::Error,
     fs::file::{self, File},
-    id_pool::IdPool,
     list::{List, ListArc, ListArcField, ListLinks},
     mm,
     prelude::*,
diff --git a/rust/kernel/bitmap.rs b/rust/kernel/bitmap.rs
index b27e0ec80d64..ecf8f194cf3a 100644
--- a/rust/kernel/bitmap.rs
+++ b/rust/kernel/bitmap.rs
@@ -12,6 +12,8 @@
 use crate::pr_err;
 use core::ptr::NonNull;
 
+pub mod id_pool;
+
 /// Represents a C bitmap. Wraps underlying C bitmap API.
 ///
 /// # Invariants
diff --git a/rust/kernel/id_pool.rs b/rust/kernel/bitmap/id_pool.rs
similarity index 93%
rename from rust/kernel/id_pool.rs
rename to rust/kernel/bitmap/id_pool.rs
index 384753fe0e44..d6440ec8f60f 100644
--- a/rust/kernel/id_pool.rs
+++ b/rust/kernel/bitmap/id_pool.rs
@@ -3,6 +3,14 @@
 // Copyright (C) 2025 Google LLC.
 
 //! Rust API for an ID pool backed by a [`BitmapVec`].
+//!
+//! The id pool provided by this file is designed for specialized use-cases
+//! that need an implementation backed by a bitmap. If you just want a generic
+//! ID allocator, please use [`XArray`] instead. Or for use-cases that require
+//! contiguous ranges of IDs, use the [`MapleTree`].
+//!
+//! [`XArray`]: crate::xarray::XArray
+//! [`MapleTree`]: crate::maple_tree::MapleTree
 
 use crate::alloc::{AllocError, Flags};
 use crate::bitmap::BitmapVec;
@@ -23,8 +31,10 @@
 /// Basic usage
 ///
 /// ```
-/// use kernel::alloc::AllocError;
-/// use kernel::id_pool::{IdPool, UnusedId};
+/// use kernel::{
+///     alloc::AllocError,
+///     bitmap::id_pool::{IdPool, UnusedId},
+/// };
 ///
 /// let mut pool = IdPool::with_capacity(64, GFP_KERNEL)?;
 /// for i in 0..64 {
@@ -47,7 +57,7 @@
 /// ```no_run
 /// use kernel::alloc::{AllocError, flags::GFP_KERNEL};
 /// use kernel::sync::{new_spinlock, SpinLock};
-/// use kernel::id_pool::IdPool;
+/// use kernel::bitmap::id_pool::IdPool;
 ///
 /// fn get_id_maybe_realloc(guarded_pool: &SpinLock<IdPool>) -> Result<usize, AllocError> {
 ///     let mut pool = guarded_pool.lock();
@@ -134,10 +144,12 @@ pub fn capacity(&self) -> usize {
     /// ```
     /// use kernel::{
     ///     alloc::AllocError,
-    ///     bitmap::BitmapVec,
-    ///     id_pool::{
-    ///         IdPool,
-    ///         ReallocRequest,
+    ///     bitmap::{
+    ///         id_pool::{
+    ///             IdPool,
+    ///             ReallocRequest,
+    ///         },
+    ///         BitmapVec,
     ///     },
     /// };
     ///
diff --git a/rust/kernel/lib.rs b/rust/kernel/lib.rs
index 9512af7156df..8e7717bb8b9f 100644
--- a/rust/kernel/lib.rs
+++ b/rust/kernel/lib.rs
@@ -77,7 +77,6 @@
 pub mod gpu;
 #[cfg(CONFIG_I2C = "y")]
 pub mod i2c;
-pub mod id_pool;
 #[doc(hidden)]
 pub mod impl_flags;
 pub mod init;

---
base-commit: 8cdeaa50eae8dad34885515f62559ee83e7e8dda
change-id: 20260711-id-pool-move-bitmap-5b0dc0d2befc

Best regards,
-- 
Alice Ryhl <aliceryhl@google.com>
Re: [PATCH] rust: bitmap: encourage using xarray/maple_tree instead of id_pool
Posted by Yury Norov 6 days, 8 hours ago 
On Sat, Jul 11, 2026 at 01:13:05PM +0000, Alice Ryhl wrote:
> The id_pool.rs file was added for use in the Binder driver, which is
> using a bitmap rather than the normal IDR implementation due its
> specialized needs and performance/spinlock requirements. However, its
> current name as kernel::id_pool encourages using it over other IDR
> solutions.
> 
> To discourage choosing this pool when you don't need it, move it to
> kernel::bitmap and add a comment recommending the xarray or maple tree
> for generic IDR use-cases.
> 
> Please see the below links for the discussion that prompted moving this
> file.
> 
> Link: https://lore.kernel.org/rust-for-linux/2026070334-dollar-hexagram-e49c@gregkh/
> Link: https://lore.kernel.org/rust-for-linux/84bc8bd2-e292-4b84-9580-a1b5df4c5bdc@nvidia.com/
> Link: https://lore.kernel.org/rust-for-linux/20260711063602.426311-1-ynorov@nvidia.com/

So, the 1st link explains why id_pool needs bitmaps, the 2nd one
explains why NOVA needs bitmaps, and the 3rd one is my non-rust test
that just provide numbers.

None of them explain why bitmap needs id_pool, neither that id_pool
is the part of bitmap. Because it's not.

ID pool is a user of bitmaps, not a part of it. If we move every
random user to the bitmap directory, that would be an immediate
maintenance burden on you, Burak and me. Not sure I'm a fan of
this idea.

I think, rust needs the lib/ directory, similar to the kernel's one.
Bitmap API should go there alongside with the cpumasks, bug.rs, bits
and bitfields, maple_tree and everything that normally lives in lib.

That would address your id_pool vs other IDRs concern, because it will
make id_pool just another API under lib.

In the mother kernel, we have a flat hierarchy of the lib, because the
corresponding API is exported via the better structured headers. We've
got no headers in Rust, so I think it would be reasonable to create a
structure for the lib where the close APIs are grouped together:

        rust/lib/bit/bitfield.rs
        rust/lib/bit/bitmap.rs
        rust/lib/bit/bits.rs  
        rust/tree/maple.rs
        rust/tree/rb.rs
        rust/lib/cpumask.rs  
        rust/lib/id_pool.rs  
                        
Thanks,
Yury

> Signed-off-by: Alice Ryhl <aliceryhl@google.com>
> ---
>  MAINTAINERS                         |  2 +-
>  drivers/android/binder/process.rs   |  2 +-
>  rust/kernel/bitmap.rs               |  2 ++
>  rust/kernel/{ => bitmap}/id_pool.rs | 26 +++++++++++++++++++-------
>  rust/kernel/lib.rs                  |  1 -
>  5 files changed, 23 insertions(+), 10 deletions(-)
> 
> diff --git a/MAINTAINERS b/MAINTAINERS
> index 4a8b0fd665ce..d80377d06c3a 100644
> --- a/MAINTAINERS
> +++ b/MAINTAINERS
> @@ -4639,7 +4639,7 @@ R:	Yury Norov <yury.norov@gmail.com>
>  S:	Maintained
>  F:	lib/find_bit_benchmark_rust.rs
>  F:	rust/kernel/bitmap.rs
> -F:	rust/kernel/id_pool.rs
> +F:	rust/kernel/bitmap/
>  
>  BITOPS API
>  M:	Yury Norov <yury.norov@gmail.com>
> diff --git a/drivers/android/binder/process.rs b/drivers/android/binder/process.rs
> index 96b8440ceac6..eec417604806 100644
> --- a/drivers/android/binder/process.rs
> +++ b/drivers/android/binder/process.rs
> @@ -16,10 +16,10 @@
>  
>  use kernel::{
>      bindings,
> +    bitmap::id_pool::IdPool,
>      cred::Credential,
>      error::Error,
>      fs::file::{self, File},
> -    id_pool::IdPool,
>      list::{List, ListArc, ListArcField, ListLinks},
>      mm,
>      prelude::*,
> diff --git a/rust/kernel/bitmap.rs b/rust/kernel/bitmap.rs
> index b27e0ec80d64..ecf8f194cf3a 100644
> --- a/rust/kernel/bitmap.rs
> +++ b/rust/kernel/bitmap.rs
> @@ -12,6 +12,8 @@
>  use crate::pr_err;
>  use core::ptr::NonNull;
>  
> +pub mod id_pool;
> +
>  /// Represents a C bitmap. Wraps underlying C bitmap API.
>  ///
>  /// # Invariants
> diff --git a/rust/kernel/id_pool.rs b/rust/kernel/bitmap/id_pool.rs
> similarity index 93%
> rename from rust/kernel/id_pool.rs
> rename to rust/kernel/bitmap/id_pool.rs
> index 384753fe0e44..d6440ec8f60f 100644
> --- a/rust/kernel/id_pool.rs
> +++ b/rust/kernel/bitmap/id_pool.rs
> @@ -3,6 +3,14 @@
>  // Copyright (C) 2025 Google LLC.
>  
>  //! Rust API for an ID pool backed by a [`BitmapVec`].
> +//!
> +//! The id pool provided by this file is designed for specialized use-cases
> +//! that need an implementation backed by a bitmap. If you just want a generic
> +//! ID allocator, please use [`XArray`] instead. Or for use-cases that require
> +//! contiguous ranges of IDs, use the [`MapleTree`].
> +//!
> +//! [`XArray`]: crate::xarray::XArray
> +//! [`MapleTree`]: crate::maple_tree::MapleTree
>  
>  use crate::alloc::{AllocError, Flags};
>  use crate::bitmap::BitmapVec;
> @@ -23,8 +31,10 @@
>  /// Basic usage
>  ///
>  /// ```
> -/// use kernel::alloc::AllocError;
> -/// use kernel::id_pool::{IdPool, UnusedId};
> +/// use kernel::{
> +///     alloc::AllocError,
> +///     bitmap::id_pool::{IdPool, UnusedId},
> +/// };
>  ///
>  /// let mut pool = IdPool::with_capacity(64, GFP_KERNEL)?;
>  /// for i in 0..64 {
> @@ -47,7 +57,7 @@
>  /// ```no_run
>  /// use kernel::alloc::{AllocError, flags::GFP_KERNEL};
>  /// use kernel::sync::{new_spinlock, SpinLock};
> -/// use kernel::id_pool::IdPool;
> +/// use kernel::bitmap::id_pool::IdPool;
>  ///
>  /// fn get_id_maybe_realloc(guarded_pool: &SpinLock<IdPool>) -> Result<usize, AllocError> {
>  ///     let mut pool = guarded_pool.lock();
> @@ -134,10 +144,12 @@ pub fn capacity(&self) -> usize {
>      /// ```
>      /// use kernel::{
>      ///     alloc::AllocError,
> -    ///     bitmap::BitmapVec,
> -    ///     id_pool::{
> -    ///         IdPool,
> -    ///         ReallocRequest,
> +    ///     bitmap::{
> +    ///         id_pool::{
> +    ///             IdPool,
> +    ///             ReallocRequest,
> +    ///         },
> +    ///         BitmapVec,
>      ///     },
>      /// };
>      ///
> diff --git a/rust/kernel/lib.rs b/rust/kernel/lib.rs
> index 9512af7156df..8e7717bb8b9f 100644
> --- a/rust/kernel/lib.rs
> +++ b/rust/kernel/lib.rs
> @@ -77,7 +77,6 @@
>  pub mod gpu;
>  #[cfg(CONFIG_I2C = "y")]
>  pub mod i2c;
> -pub mod id_pool;
>  #[doc(hidden)]
>  pub mod impl_flags;
>  pub mod init;
> 
> ---
> base-commit: 8cdeaa50eae8dad34885515f62559ee83e7e8dda
> change-id: 20260711-id-pool-move-bitmap-5b0dc0d2befc
> 
> Best regards,
> -- 
> Alice Ryhl <aliceryhl@google.com>
Re: [PATCH] rust: bitmap: encourage using xarray/maple_tree instead of id_pool
Posted by Miguel Ojeda 4 days, 13 hours ago 
On Sun, Jul 19, 2026 at 4:24 PM Yury Norov <ynorov@nvidia.com> wrote:
>
> ID pool is a user of bitmaps, not a part of it. If we move every
> random user to the bitmap directory, that would be an immediate
> maintenance burden on you, Burak and me. Not sure I'm a fan of
> this idea.

Splitting things into more independent modules is usually fine, yeah.

I don't see why we would need a `lib/`, though.

Hmm... If what we want is to avoid having `id_pool` as part of
`bitmap`, then can we add the documentation paragraph added here
instead?

Thanks!

Cheers,
Miguel
Re: [PATCH] rust: bitmap: encourage using xarray/maple_tree instead of id_pool
Posted by Burak Emir 4 days, 11 hours ago 
On Tue, Jul 21, 2026 at 12:08 PM Miguel Ojeda
<miguel.ojeda.sandonis@gmail.com> wrote:
>
> On Sun, Jul 19, 2026 at 4:24 PM Yury Norov <ynorov@nvidia.com> wrote:
> >
> > ID pool is a user of bitmaps, not a part of it. If we move every
> > random user to the bitmap directory, that would be an immediate
> > maintenance burden on you, Burak and me. Not sure I'm a fan of
> > this idea.
>
> Splitting things into more independent modules is usually fine, yeah.

> I don't see why we would need a `lib/`, though.

My read of Yury's comment is that this proposes to organize Rust files
using C include file conventions.

@Yury, the Rust compiler expects files and directories to follow the
module structure. Module structure governs how stuff is accessed in
source (kind of like c++ namespaces, but done right), crates act as
top-level modules. If you create a lib directory, you would have to
have a lib module. Everyone would have to mention lib when importing
types and functions from there, which seems redundant.

My thoughts:
- there seems to be precedent for nesting modules under kernel.

- agree that ID pool is a user (depends on) bitmap, but it is not a
random user. We do not want every user of bitmap to go into the bitmap
module, but apparently there is more than use-case for the
abstraction.

- even if ID pool depends on bitmap, nothing prevents us from putting
it into bitmap module as a nested module. Everything is part of the
kernel crate and built together anyways.

- The idea of this series is to make clear that using ID pool is a
commitment to bitmap. This addresses the recurring discussion "why
isn't this IDR/IDA/xarray/maple tree etc".

> Hmm... If what we want is to avoid having `id_pool` as part of
> `bitmap`, then can we add the documentation paragraph added here
> instead?

Added where? You mean not moving it under bitmap but just adding
documentation to IdPool in its current place?

I don't have a strong opinion on module structure. I just think it is
easy to miss documentation, and it could convey that this ID pool is
intentionally strongly coupled with bitmap.

Cheers,
Burak
Re: [PATCH] rust: bitmap: encourage using xarray/maple_tree instead of id_pool
Posted by Burak Emir 1 week ago 
On Sat, Jul 11, 2026 at 3:13 PM Alice Ryhl <aliceryhl@google.com> wrote:
>
> The id_pool.rs file was added for use in the Binder driver, which is
> using a bitmap rather than the normal IDR implementation due its
> specialized needs and performance/spinlock requirements. However, its
> current name as kernel::id_pool encourages using it over other IDR
> solutions.
>
> To discourage choosing this pool when you don't need it, move it to
> kernel::bitmap and add a comment recommending the xarray or maple tree
> for generic IDR use-cases.
>
> Please see the below links for the discussion that prompted moving this
> file.
>
> Link: https://lore.kernel.org/rust-for-linux/2026070334-dollar-hexagram-e49c@gregkh/
> Link: https://lore.kernel.org/rust-for-linux/84bc8bd2-e292-4b84-9580-a1b5df4c5bdc@nvidia.com/
> Link: https://lore.kernel.org/rust-for-linux/20260711063602.426311-1-ynorov@nvidia.com/
> Signed-off-by: Alice Ryhl <aliceryhl@google.com>

Reviewed-by: Burak Emir <burak.emir@gmail.com>

Looks good. I built, ran the tests and checked the rustdoc.

cheers,
Burak

Patchew 2.1-devel-ea86937

© 2016 - 2026 Red Hat, Inc.