* Re: [PATCH] rust: bitmap: encourage using xarray/maple_tree instead of id_pool
2026-07-11 13:13 [PATCH] rust: bitmap: encourage using xarray/maple_tree instead of id_pool Alice Ryhl
@ 2026-07-18 21:16 ` Burak Emir
2026-07-19 14:24 ` Yury Norov
1 sibling, 0 replies; 3+ messages in thread
From: Burak Emir @ 2026-07-18 21:16 UTC (permalink / raw)
To: Alice Ryhl
Cc: Liam R . Howlett, Andreas Hindborg, Andrew Ballance,
Eliot Courtney, Greg Kroah-Hartman, John Hubbard, Matthew Wilcox,
Tamir Duberstein, Yury Norov, Alexandre Courbot, Andrew Morton,
Benno Lossin, Björn Roy Baron, Boqun Feng, Carlos Llamas,
Daniel Almeida, Danilo Krummrich, Gary Guo, Lorenzo Stoakes,
Miguel Ojeda, Onur Özkan, Trevor Gross, linux-kernel,
linux-mm, rust-for-linux
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
^ permalink raw reply [flat|nested] 3+ messages in thread
* Re: [PATCH] rust: bitmap: encourage using xarray/maple_tree instead of id_pool
2026-07-11 13:13 [PATCH] rust: bitmap: encourage using xarray/maple_tree instead of id_pool Alice Ryhl
2026-07-18 21:16 ` Burak Emir
@ 2026-07-19 14:24 ` Yury Norov
1 sibling, 0 replies; 3+ messages in thread
From: Yury Norov @ 2026-07-19 14:24 UTC (permalink / raw)
To: Alice Ryhl
Cc: Liam R . Howlett, Andreas Hindborg, Andrew Ballance, Burak Emir,
Eliot Courtney, Greg Kroah-Hartman, John Hubbard, Matthew Wilcox,
Tamir Duberstein, Yury Norov, Alexandre Courbot, Andrew Morton,
Benno Lossin, Björn Roy Baron, Boqun Feng, Carlos Llamas,
Daniel Almeida, Danilo Krummrich, Gary Guo, Lorenzo Stoakes,
Miguel Ojeda, Onur Özkan, Trevor Gross, linux-kernel,
linux-mm, rust-for-linux
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>
^ permalink raw reply [flat|nested] 3+ messages in thread