rust: bitmap: encourage using xarray/maple_tree instead of id_pool
Subsystems (4)
Alice Ryhl
maintainerPATCH 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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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]>
Quoted 11 lines · Alice Ryhl
The
id_pool.rsfile 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 askernel::id_poolencourages using it over other IDR solutions.To discourage choosing this pool when you don't need it, move it to
kernel::bitmapand 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
Quoted 10 lines · Alice Ryhl
The
id_pool.rsfile 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 askernel::id_poolencourages using it over other IDR solutions.To discourage choosing this pool when you don't need it, move it to
kernel::bitmapand 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
Signed-off-by Alice Ryhl <[email protected]>--- 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@@ -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@@ -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@@ -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@@ -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@@ -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-5b0dc0d2befcBest regards,
Signature · 1 line
Alice Ryhl <[email protected]>
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
Burak Emir
maintainerQuoted 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_poolas part ofbitmap, 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