Skip to contentSkip to conversation

rust: bitmap: encourage using xarray/maple_tree instead of id_pool

PATCH In review Alice Ryhl 4 participants 5 messages Jul 11 – Jul 21

Subsystems (4)
lore
Share & tools
lore

Alice Ryhl

author maintainer
#0 lore raw

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

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.

---
 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(-)
MAINTAINERS +1 -1
index 4a8b0fd665ce..d80377d06c3a 100644
@@ -4639,7 +4639,7 @@ R:	Yury Norov <[email protected]>
 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 <[email protected]>
drivers/android/binder/process.rs +1 -1
index 96b8440ceac6..eec417604806 100644
@@ -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::*,
rust/kernel/bitmap.rs +2 -0
index b27e0ec80d64..ecf8f194cf3a 100644
@@ -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
rust/kernel/bitmap/id_pool.rs renamed from rust/kernel/id_pool.rs +19 -7
similarity index 93%
rename from rust/kernel/id_pool.rs
rename to rust/kernel/bitmap/id_pool.rs
index 384753fe0e44..d6440ec8f60f 100644
@@ -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,
     ///     },
     /// };
     ///
rust/kernel/lib.rs +0 -1
index 9512af7156df..8e7717bb8b9f 100644
@@ -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,

Signature · 1 line
Alice Ryhl <[email protected]>
maintainer Reviewed-by on v1 1/1
#1 lore raw
Quoted 11 lines · Alice Ryhl

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.

Quoted 7 lines

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

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

cheers,
Burak

#2 lore raw
In reply to Alice Ryhl
Quoted 10 lines · Alice Ryhl

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.

Quoted 6 lines

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

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

Quoted 132 lines
---
 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(-)
MAINTAINERS +1 -1
index 4a8b0fd665ce..d80377d06c3a 100644
@@ -4639,7 +4639,7 @@ R:	Yury Norov <[email protected]>
 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 <[email protected]>
drivers/android/binder/process.rs +1 -1
index 96b8440ceac6..eec417604806 100644
@@ -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::*,
rust/kernel/bitmap.rs +2 -0
index b27e0ec80d64..ecf8f194cf3a 100644
@@ -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
rust/kernel/bitmap/id_pool.rs renamed from rust/kernel/id_pool.rs +19 -7
similarity index 93%
rename from rust/kernel/id_pool.rs
rename to rust/kernel/bitmap/id_pool.rs
index 384753fe0e44..d6440ec8f60f 100644
@@ -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,
     ///     },
     /// };
     ///
rust/kernel/lib.rs +0 -2
index 9512af7156df..8e7717bb8b9f 100644
@@ -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,

Signature · 1 line
Alice Ryhl <[email protected]>
#3 lore raw
Quoted 5 lines · Yury Norov

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

maintainer
#4 lore raw
Quoted 11 lines · Miguel Ojeda
Quoted 5 lines · Yury Norov

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".

Quoted 3 lines

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