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

[Yury Norov]

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@xxxxxxxxxx/
> Link: https://lore.kernel.org/rust-for-linux/20260711063602.426311-1-ynorov@xxxxxxxxxx/

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@xxxxxxxxxx>
> ---
>  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@xxxxxxxxx>
>  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@xxxxxxxxx>
> 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@xxxxxxxxxx>