[PATCH v2 0/5] Use Rust Bitmap from Rust Binder driver

[PATCH v2 0/5] Use Rust Bitmap from Rust Binder driver

[Alice Ryhl]

See commit message for rust binder commit for details.

Signed-off-by: Alice Ryhl <aliceryhl@google.com>
---
Changes in v2:
- Use id_pool.
- Link to v1: https://lore.kernel.org/r/20251020-binder-bitmap-v1-0-879bec9cddc1@google.com

---
Alice Ryhl (5):
      rust: bitmap: add MAX_LEN and NO_ALLOC_MAX_LEN constants
      rust: bitmap: add BitmapVec::new_small()
      rust: id_pool: do not supply starting capacity
      rust: id_pool: do not immediately acquire new ids
      rust_binder: use bitmap for allocation of handles

 drivers/android/binder/process.rs | 63 +++++++++++++++++++++++++++-----------
 rust/kernel/bitmap.rs             | 26 +++++++++++++---
 rust/kernel/id_pool.rs            | 64 ++++++++++++++++++++++++++++-----------
 3 files changed, 114 insertions(+), 39 deletions(-)
---
base-commit: 211ddde0823f1442e4ad052a2f30f050145ccada
change-id: 20251007-binder-bitmap-5aa0d966fb1f

Best regards,
-- 
Alice Ryhl <aliceryhl@google.com>

[PATCH v2 1/5] rust: bitmap: add MAX_LEN and NO_ALLOC_MAX_LEN constants

[Alice Ryhl]

To avoid hard-coding these values in drivers, define constants for them
that drivers can reference.

Acked-by: Danilo Krummrich <dakr@kernel.org>
Reviewed-by: Burak Emir <bqe@google.com>
Signed-off-by: Alice Ryhl <aliceryhl@google.com>
---
 rust/kernel/bitmap.rs | 16 +++++++++++-----
 1 file changed, 11 insertions(+), 5 deletions(-)

diff --git a/rust/kernel/bitmap.rs b/rust/kernel/bitmap.rs
index aa8fc7bf06fc99865ae755d8694e4bec3dc8e7f0..15fa23b45054b9272415fcc000e3e3b52c74d7c1 100644
--- a/rust/kernel/bitmap.rs
+++ b/rust/kernel/bitmap.rs
@@ -149,14 +149,14 @@ macro_rules! bitmap_assert_return {
 ///
 /// # Invariants
 ///
-/// * `nbits` is `<= i32::MAX` and never changes.
+/// * `nbits` is `<= MAX_LEN`.
 /// * if `nbits <= bindings::BITS_PER_LONG`, then `repr` is a `usize`.
 /// * otherwise, `repr` holds a non-null pointer to an initialized
 ///   array of `unsigned long` that is large enough to hold `nbits` bits.
 pub struct BitmapVec {
     /// Representation of bitmap.
     repr: BitmapRepr,
-    /// Length of this bitmap. Must be `<= i32::MAX`.
+    /// Length of this bitmap. Must be `<= MAX_LEN`.
     nbits: usize,
 }
 
@@ -226,10 +226,16 @@ fn drop(&mut self) {
 }
 
 impl BitmapVec {
+    /// The maximum possible length of a `BitmapVec`.
+    pub const MAX_LEN: usize = i32::MAX as usize;
+
+    /// The maximum length that avoids allocating.
+    pub const NO_ALLOC_MAX_LEN: usize = BITS_PER_LONG;
+
     /// Constructs a new [`BitmapVec`].
     ///
     /// Fails with [`AllocError`] when the [`BitmapVec`] could not be allocated. This
-    /// includes the case when `nbits` is greater than `i32::MAX`.
+    /// includes the case when `nbits` is greater than `MAX_LEN`.
     #[inline]
     pub fn new(nbits: usize, flags: Flags) -> Result<Self, AllocError> {
         if nbits <= BITS_PER_LONG {
@@ -238,11 +244,11 @@ pub fn new(nbits: usize, flags: Flags) -> Result<Self, AllocError> {
                 nbits,
             });
         }
-        if nbits > i32::MAX.try_into().unwrap() {
+        if nbits > Self::MAX_LEN {
             return Err(AllocError);
         }
         let nbits_u32 = u32::try_from(nbits).unwrap();
-        // SAFETY: `BITS_PER_LONG < nbits` and `nbits <= i32::MAX`.
+        // SAFETY: `BITS_PER_LONG < nbits` and `nbits <= MAX_LEN`.
         let ptr = unsafe { bindings::bitmap_zalloc(nbits_u32, flags.as_raw()) };
         let ptr = NonNull::new(ptr).ok_or(AllocError)?;
         // INVARIANT: `ptr` returned by C `bitmap_zalloc` and `nbits` checked.

-- 
2.51.0.869.ge66316f041-goog

[PATCH v2 2/5] rust: bitmap: add BitmapVec::new_small()

[Alice Ryhl]

This constructor is useful when you just want to create a BitmapVec
without allocating but don't care how large it is.

Signed-off-by: Alice Ryhl <aliceryhl@google.com>
---
 rust/kernel/bitmap.rs | 10 ++++++++++
 1 file changed, 10 insertions(+)

diff --git a/rust/kernel/bitmap.rs b/rust/kernel/bitmap.rs
index 15fa23b45054b9272415fcc000e3e3b52c74d7c1..4ffe9eb0f208a3d62016e00297f5a0800aa33336 100644
--- a/rust/kernel/bitmap.rs
+++ b/rust/kernel/bitmap.rs
@@ -232,6 +232,16 @@ impl BitmapVec {
     /// The maximum length that avoids allocating.
     pub const NO_ALLOC_MAX_LEN: usize = BITS_PER_LONG;
 
+    /// Constructs a new [`BitmapVec`] without allocating.
+    #[inline]
+    pub fn new_small() -> Self {
+        // INVARIANT: `nbits <= NO_ALLOC_MAX_LEN`, so an inline bitmap is the right repr.
+        BitmapVec {
+            repr: BitmapRepr { bitmap: 0 },
+            nbits: BitmapVec::NO_ALLOC_MAX_LEN,
+        }
+    }
+
     /// Constructs a new [`BitmapVec`].
     ///
     /// Fails with [`AllocError`] when the [`BitmapVec`] could not be allocated. This

-- 
2.51.0.869.ge66316f041-goog

Re: [PATCH v2 2/5] rust: bitmap: add BitmapVec::new_small()

[Burak Emir]

On Tue, Oct 21, 2025 at 3:33 PM Alice Ryhl <aliceryhl@google.com> wrote:
>
> This constructor is useful when you just want to create a BitmapVec
> without allocating but don't care how large it is.
>
> Signed-off-by: Alice Ryhl <aliceryhl@google.com>
Reviewed-by: Burak Emir <bqe@google.com>

Re: [PATCH v2 2/5] rust: bitmap: add BitmapVec::new_small()

[Yury Norov]

On Tue, Oct 21, 2025 at 01:32:44PM +0000, Alice Ryhl wrote:
> This constructor is useful when you just want to create a BitmapVec
> without allocating but don't care how large it is.
> 
> Signed-off-by: Alice Ryhl <aliceryhl@google.com>
> ---
>  rust/kernel/bitmap.rs | 10 ++++++++++
>  1 file changed, 10 insertions(+)
> 
> diff --git a/rust/kernel/bitmap.rs b/rust/kernel/bitmap.rs
> index 15fa23b45054b9272415fcc000e3e3b52c74d7c1..4ffe9eb0f208a3d62016e00297f5a0800aa33336 100644
> --- a/rust/kernel/bitmap.rs
> +++ b/rust/kernel/bitmap.rs
> @@ -232,6 +232,16 @@ impl BitmapVec {
>      /// The maximum length that avoids allocating.
>      pub const NO_ALLOC_MAX_LEN: usize = BITS_PER_LONG;
>  
> +    /// Constructs a new [`BitmapVec`] without allocating.
> +    #[inline]
> +    pub fn new_small() -> Self {

Nit: maybe:

        /// Construct a longest possible inline [`BitmapVec`].
        #[inline]
        pub fn new_inline() ...

This 'small vs large' lingo is internal to bitmaps. I don't think it
is worth to expose it in the interfaces. 'Inline' or 'inplace' sounds
better to me.

With that,

Acked-by: Yury Norov (NVIDIA) <yury.norov@gmail.com>

> +        // INVARIANT: `nbits <= NO_ALLOC_MAX_LEN`, so an inline bitmap is the right repr.
> +        BitmapVec {
> +            repr: BitmapRepr { bitmap: 0 },
> +            nbits: BitmapVec::NO_ALLOC_MAX_LEN,

A side note: after merging bitfields, we may switch inline bitmaps to to

        bitfield!() {
                0:31    nbits;
                32:64   bitmap;
        }

Thanks,
Yury

> +        }
> +    }
> +
>      /// Constructs a new [`BitmapVec`].
>      ///
>      /// Fails with [`AllocError`] when the [`BitmapVec`] could not be allocated. This
> 
> -- 
> 2.51.0.869.ge66316f041-goog

Re: [PATCH v2 2/5] rust: bitmap: add BitmapVec::new_small()

[Alice Ryhl]

On Thu, Oct 23, 2025 at 01:33:03PM -0400, Yury Norov wrote:
> On Tue, Oct 21, 2025 at 01:32:44PM +0000, Alice Ryhl wrote:
> > This constructor is useful when you just want to create a BitmapVec
> > without allocating but don't care how large it is.
> > 
> > Signed-off-by: Alice Ryhl <aliceryhl@google.com>
> > ---
> >  rust/kernel/bitmap.rs | 10 ++++++++++
> >  1 file changed, 10 insertions(+)
> > 
> > diff --git a/rust/kernel/bitmap.rs b/rust/kernel/bitmap.rs
> > index 15fa23b45054b9272415fcc000e3e3b52c74d7c1..4ffe9eb0f208a3d62016e00297f5a0800aa33336 100644
> > --- a/rust/kernel/bitmap.rs
> > +++ b/rust/kernel/bitmap.rs
> > @@ -232,6 +232,16 @@ impl BitmapVec {
> >      /// The maximum length that avoids allocating.
> >      pub const NO_ALLOC_MAX_LEN: usize = BITS_PER_LONG;
> >  
> > +    /// Constructs a new [`BitmapVec`] without allocating.
> > +    #[inline]
> > +    pub fn new_small() -> Self {
> 
> Nit: maybe:
> 
>         /// Construct a longest possible inline [`BitmapVec`].
>         #[inline]
>         pub fn new_inline() ...
> 
> This 'small vs large' lingo is internal to bitmaps. I don't think it
> is worth to expose it in the interfaces. 'Inline' or 'inplace' sounds
> better to me.
> 
> With that,
> 
> Acked-by: Yury Norov (NVIDIA) <yury.norov@gmail.com>

Makes sense. Will reword to 'inline', thanks!

> > +        // INVARIANT: `nbits <= NO_ALLOC_MAX_LEN`, so an inline bitmap is the right repr.
> > +        BitmapVec {
> > +            repr: BitmapRepr { bitmap: 0 },
> > +            nbits: BitmapVec::NO_ALLOC_MAX_LEN,
> 
> A side note: after merging bitfields, we may switch inline bitmaps to to
> 
>         bitfield!() {
>                 0:31    nbits;
>                 32:64   bitmap;
>         }

Personally I think I would prefer to keep the union only on the `repr`
field like it is now.

Alice

[PATCH v2 3/5] rust: id_pool: do not supply starting capacity

[Alice Ryhl]

When creating the initial IdPool, Rust Binder simply wants the largest
value that does not allocate. Having to handle allocating error failures
that cannot happen is inconvenient, so make the constructor infallible
by removing the size argument.

Signed-off-by: Alice Ryhl <aliceryhl@google.com>
---
 rust/kernel/id_pool.rs | 20 +++++++++++---------
 1 file changed, 11 insertions(+), 9 deletions(-)

diff --git a/rust/kernel/id_pool.rs b/rust/kernel/id_pool.rs
index a41a3404213ca92d53b14c80101afff6ac8c416e..126e57f34c3407cb1dab3169417f01917e172dee 100644
--- a/rust/kernel/id_pool.rs
+++ b/rust/kernel/id_pool.rs
@@ -96,16 +96,11 @@ pub fn realloc(&self, flags: Flags) -> Result<PoolResizer, AllocError> {
 
 impl IdPool {
     /// Constructs a new [`IdPool`].
-    ///
-    /// A capacity below [`BITS_PER_LONG`] is adjusted to
-    /// [`BITS_PER_LONG`].
-    ///
-    /// [`BITS_PER_LONG`]: srctree/include/asm-generic/bitsperlong.h
     #[inline]
-    pub fn new(num_ids: usize, flags: Flags) -> Result<Self, AllocError> {
-        let num_ids = core::cmp::max(num_ids, BITS_PER_LONG);
-        let map = BitmapVec::new(num_ids, flags)?;
-        Ok(Self { map })
+    pub fn new() -> Self {
+        Self {
+            map: BitmapVec::new_small(),
+        }
     }
 
     /// Returns how many IDs this pool can currently have.
@@ -224,3 +219,10 @@ pub fn release_id(&mut self, id: usize) {
         self.map.clear_bit(id);
     }
 }
+
+impl Default for IdPool {
+    #[inline]
+    fn default() -> Self {
+        Self::new()
+    }
+}

-- 
2.51.0.869.ge66316f041-goog

Re: [PATCH v2 3/5] rust: id_pool: do not supply starting capacity

[Burak Emir]

On Tue, Oct 21, 2025 at 3:33 PM Alice Ryhl <aliceryhl@google.com> wrote:
>
> When creating the initial IdPool, Rust Binder simply wants the largest
> value that does not allocate. Having to handle allocating error failures
> that cannot happen is inconvenient, so make the constructor infallible
> by removing the size argument.
>
> Signed-off-by: Alice Ryhl <aliceryhl@google.com>
Reviewed-by: Burak Emir <bqe@google.com>

Since Binder is the one use case we made this abstraction is for, it
makes sense to me.

cheers,
Burak

Re: [PATCH v2 3/5] rust: id_pool: do not supply starting capacity

[Yury Norov]

On Tue, Oct 21, 2025 at 01:32:45PM +0000, Alice Ryhl wrote:
> When creating the initial IdPool, Rust Binder simply wants the largest
> value that does not allocate. Having to handle allocating error failures

That "value that does not allocate" wording is pretty confusing.
Maybe:
        Rust binder is initially created with an arbitrary capacity
        such that the underlying bitmap is held inplace.

Regardless:

Acked-by: Yury Norov (NVIDIA) <yury.norov@gmail.com>

> that cannot happen is inconvenient, so make the constructor infallible
> by removing the size argument.
> 
> Signed-off-by: Alice Ryhl <aliceryhl@google.com>
> ---
>  rust/kernel/id_pool.rs | 20 +++++++++++---------
>  1 file changed, 11 insertions(+), 9 deletions(-)
> 
> diff --git a/rust/kernel/id_pool.rs b/rust/kernel/id_pool.rs
> index a41a3404213ca92d53b14c80101afff6ac8c416e..126e57f34c3407cb1dab3169417f01917e172dee 100644
> --- a/rust/kernel/id_pool.rs
> +++ b/rust/kernel/id_pool.rs
> @@ -96,16 +96,11 @@ pub fn realloc(&self, flags: Flags) -> Result<PoolResizer, AllocError> {
>  
>  impl IdPool {
>      /// Constructs a new [`IdPool`].
> -    ///
> -    /// A capacity below [`BITS_PER_LONG`] is adjusted to
> -    /// [`BITS_PER_LONG`].
> -    ///
> -    /// [`BITS_PER_LONG`]: srctree/include/asm-generic/bitsperlong.h
>      #[inline]
> -    pub fn new(num_ids: usize, flags: Flags) -> Result<Self, AllocError> {
> -        let num_ids = core::cmp::max(num_ids, BITS_PER_LONG);
> -        let map = BitmapVec::new(num_ids, flags)?;
> -        Ok(Self { map })
> +    pub fn new() -> Self {
> +        Self {
> +            map: BitmapVec::new_small(),
> +        }
>      }
>  
>      /// Returns how many IDs this pool can currently have.
> @@ -224,3 +219,10 @@ pub fn release_id(&mut self, id: usize) {
>          self.map.clear_bit(id);
>      }
>  }
> +
> +impl Default for IdPool {
> +    #[inline]
> +    fn default() -> Self {
> +        Self::new()
> +    }
> +}
> 
> -- 
> 2.51.0.869.ge66316f041-goog

Re: [PATCH v2 3/5] rust: id_pool: do not supply starting capacity

[Alice Ryhl]

On Thu, Oct 23, 2025 at 01:37:05PM -0400, Yury Norov wrote:
> On Tue, Oct 21, 2025 at 01:32:45PM +0000, Alice Ryhl wrote:
> > When creating the initial IdPool, Rust Binder simply wants the largest
> > value that does not allocate. Having to handle allocating error failures
> 
> That "value that does not allocate" wording is pretty confusing.
> Maybe:
>         Rust binder is initially created with an arbitrary capacity
>         such that the underlying bitmap is held inplace.
> 
> Regardless:
> 
> Acked-by: Yury Norov (NVIDIA) <yury.norov@gmail.com>

How about this?

Rust Binder wants to use inline bitmaps whenever possible to avoid
allocations, so introduce a constructor for an IdPool with arbitrary
capacity that stores the bitmap inline.

Alice

[PATCH v2 4/5] rust: id_pool: do not immediately acquire new ids

[Alice Ryhl]

When Rust Binder assigns a new ID, it performs various fallible
operations before it "commits" to actually using the new ID. To support
this pattern, change acquire_next_id() so that it does not immediately
call set_bit(), but instead returns an object that may be used to call
set_bit() later.

The UnusedId type holds a exclusive reference to the IdPool, so it's
guaranteed that nobody else can call find_unused_id() while the UnusedId
object is live.

Signed-off-by: Alice Ryhl <aliceryhl@google.com>
---
 rust/kernel/id_pool.rs | 44 ++++++++++++++++++++++++++++++++++++--------
 1 file changed, 36 insertions(+), 8 deletions(-)

diff --git a/rust/kernel/id_pool.rs b/rust/kernel/id_pool.rs
index 126e57f34c3407cb1dab3169417f01917e172dee..053ca417e8513fc33afc84c194d7899eafac8fec 100644
--- a/rust/kernel/id_pool.rs
+++ b/rust/kernel/id_pool.rs
@@ -199,18 +199,16 @@ pub fn grow(&mut self, mut resizer: PoolResizer) {
         self.map = resizer.new;
     }
 
-    /// Acquires a new ID by finding and setting the next zero bit in the
-    /// bitmap.
+    /// Finds an unused ID in the bitmap.
     ///
     /// Upon success, returns its index. Otherwise, returns [`None`]
     /// to indicate that a [`Self::grow_request`] is needed.
     #[inline]
-    pub fn acquire_next_id(&mut self, offset: usize) -> Option<usize> {
-        let next_zero_bit = self.map.next_zero_bit(offset);
-        if let Some(nr) = next_zero_bit {
-            self.map.set_bit(nr);
-        }
-        next_zero_bit
+    pub fn find_unused_id(&mut self, offset: usize) -> Option<UnusedId<'_>> {
+        Some(UnusedId {
+            id: self.map.next_zero_bit(offset)?,
+            pool: self,
+        })
     }
 
     /// Releases an ID.
@@ -220,6 +218,36 @@ pub fn release_id(&mut self, id: usize) {
     }
 }
 
+/// Represents an unused id in an [`IdPool`].
+pub struct UnusedId<'pool> {
+    id: usize,
+    pool: &'pool mut IdPool,
+}
+
+impl<'pool> UnusedId<'pool> {
+    /// Get the unused id as an usize.
+    ///
+    /// Be aware that the id has not yet been acquired in the pool. The
+    /// [`acquire`] method must be called to prevent others from taking the id.
+    pub fn as_usize(&self) -> usize {
+        self.id
+    }
+
+    /// Get the unused id as an u32.
+    ///
+    /// Be aware that the id has not yet been acquired in the pool. The
+    /// [`acquire`] method must be called to prevent others from taking the id.
+    pub fn as_u32(&self) -> u32 {
+        // CAST: The maximum possible value in an IdPool is i32::MAX.
+        self.id as u32
+    }
+
+    /// Acquire the unused id.
+    pub fn acquire(self) {
+        self.pool.map.set_bit(self.id);
+    }
+}
+
 impl Default for IdPool {
     #[inline]
     fn default() -> Self {

-- 
2.51.0.869.ge66316f041-goog

Re: [PATCH v2 4/5] rust: id_pool: do not immediately acquire new ids

[Burak Emir]

On Tue, Oct 21, 2025 at 3:33 PM Alice Ryhl <aliceryhl@google.com> wrote:
>
> When Rust Binder assigns a new ID, it performs various fallible
> operations before it "commits" to actually using the new ID. To support
> this pattern, change acquire_next_id() so that it does not immediately
> call set_bit(), but instead returns an object that may be used to call
> set_bit() later.
>
> The UnusedId type holds a exclusive reference to the IdPool, so it's
> guaranteed that nobody else can call find_unused_id() while the UnusedId
> object is live.
>
> Signed-off-by: Alice Ryhl <aliceryhl@google.com>
Reviewed-by: Burak Emir <bqe@google.com>

Re: [PATCH v2 4/5] rust: id_pool: do not immediately acquire new ids

[kernel test robot]

Hi Alice,

kernel test robot noticed the following build errors:

[auto build test ERROR on 211ddde0823f1442e4ad052a2f30f050145ccada]

url:    https://github.com/intel-lab-lkp/linux/commits/Alice-Ryhl/rust-bitmap-add-MAX_LEN-and-NO_ALLOC_MAX_LEN-constants/20251021-213620
base:   211ddde0823f1442e4ad052a2f30f050145ccada
patch link:    https://lore.kernel.org/r/20251021-binder-bitmap-v2-4-e652d172c62b%40google.com
patch subject: [PATCH v2 4/5] rust: id_pool: do not immediately acquire new ids
config: x86_64-rhel-9.4-rust (https://download.01.org/0day-ci/archive/20251023/202510230839.DJZaY5US-lkp@intel.com/config)
compiler: clang version 20.1.8 (https://github.com/llvm/llvm-project 87f0227cb60147a26a1eeb4fb06e3b505e9c7261)
rustc: rustc 1.88.0 (6b00bc388 2025-06-23)
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20251023/202510230839.DJZaY5US-lkp@intel.com/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of
the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <lkp@intel.com>
| Closes: https://lore.kernel.org/oe-kbuild-all/202510230839.DJZaY5US-lkp@intel.com/

All errors (new ones prefixed by >>):

>> error[E0599]: no method named `acquire_next_id` found for struct `Guard<'_, IdPool, SpinLockBackend>` in the current scope
   --> rust/doctests_kernel_generated.rs:6515:20
   |
   6515 |         match pool.acquire_next_id(0) {
   |                    ^^^^^^^^^^^^^^^ method not found in `Guard<'_, IdPool, SpinLockBackend>`

-- 
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki

[PATCH v2 5/5] rust_binder: use bitmap for allocation of handles

[Alice Ryhl]

To find an unused Binder handle, Rust Binder currently iterates the
red/black tree from the beginning until it finds a gap in the keys. This
is extremely slow.

To improve the performance, add a bitmap that keeps track of which
indices are actually in use. This allows us to quickly find an unused
key in the red/black tree.

This logic matches the approach used by C Binder. It was chosen
partially because it's the most memory efficient solution.

Signed-off-by: Alice Ryhl <aliceryhl@google.com>
---
 drivers/android/binder/process.rs | 63 ++++++++++++++++++++++++++++-----------
 1 file changed, 46 insertions(+), 17 deletions(-)

diff --git a/drivers/android/binder/process.rs b/drivers/android/binder/process.rs
index f13a747e784c84a0fb09cbf47442712106eba07c..933b0f737b38ffac536b19c9330dfc63ffc72f2b 100644
--- a/drivers/android/binder/process.rs
+++ b/drivers/android/binder/process.rs
@@ -19,6 +19,7 @@
     cred::Credential,
     error::Error,
     fs::file::{self, File},
+    id_pool::IdPool,
     list::{List, ListArc, ListArcField, ListLinks},
     mm,
     prelude::*,
@@ -367,6 +368,8 @@ impl ListItem<{Self::LIST_NODE}> for NodeRefInfo {
 struct ProcessNodeRefs {
     /// Used to look up nodes using the 32-bit id that this process knows it by.
     by_handle: RBTree<u32, ListArc<NodeRefInfo, { NodeRefInfo::LIST_PROC }>>,
+    /// Used to quickly find unused ids in `by_handle`.
+    handle_is_present: IdPool,
     /// Used to look up nodes without knowing their local 32-bit id. The usize is the address of
     /// the underlying `Node` struct as returned by `Node::global_id`.
     by_node: RBTree<usize, u32>,
@@ -381,6 +384,7 @@ impl ProcessNodeRefs {
     fn new() -> Self {
         Self {
             by_handle: RBTree::new(),
+            handle_is_present: IdPool::new(),
             by_node: RBTree::new(),
             freeze_listeners: RBTree::new(),
         }
@@ -775,7 +779,7 @@ pub(crate) fn get_node(
     pub(crate) fn insert_or_update_handle(
         self: ArcBorrow<'_, Process>,
         node_ref: NodeRef,
-        is_mananger: bool,
+        is_manager: bool,
     ) -> Result<u32> {
         {
             let mut refs = self.node_refs.lock();
@@ -794,7 +798,32 @@ pub(crate) fn insert_or_update_handle(
         let reserve2 = RBTreeNodeReservation::new(GFP_KERNEL)?;
         let info = UniqueArc::new_uninit(GFP_KERNEL)?;
 
-        let mut refs = self.node_refs.lock();
+        let mut refs_lock = self.node_refs.lock();
+        let mut refs = &mut *refs_lock;
+
+        let (unused_id, by_handle_slot) = loop {
+            // ID 0 may only be used by the manager.
+            let start = if is_manager { 0 } else { 1 };
+
+            if let Some(res) = refs.handle_is_present.find_unused_id(start) {
+                match refs.by_handle.entry(res.as_u32()) {
+                    rbtree::Entry::Vacant(entry) => break (res, entry),
+                    rbtree::Entry::Occupied(_) => {
+                        pr_err!("Detected mismatch between handle_is_present and by_handle");
+                        res.acquire();
+                        continue;
+                    }
+                }
+            }
+
+            let grow_request = refs.handle_is_present.grow_request().ok_or(ENOMEM)?;
+            drop(refs_lock);
+            let resizer = grow_request.realloc(GFP_KERNEL)?;
+            refs_lock = self.node_refs.lock();
+            refs = &mut *refs_lock;
+            refs.handle_is_present.grow(resizer);
+        };
+        let handle = unused_id.as_u32();
 
         // Do a lookup again as node may have been inserted before the lock was reacquired.
         if let Some(handle_ref) = refs.by_node.get(&node_ref.node.global_id()) {
@@ -804,20 +833,9 @@ pub(crate) fn insert_or_update_handle(
             return Ok(handle);
         }
 
-        // Find id.
-        let mut target: u32 = if is_mananger { 0 } else { 1 };
-        for handle in refs.by_handle.keys() {
-            if *handle > target {
-                break;
-            }
-            if *handle == target {
-                target = target.checked_add(1).ok_or(ENOMEM)?;
-            }
-        }
-
         let gid = node_ref.node.global_id();
         let (info_proc, info_node) = {
-            let info_init = NodeRefInfo::new(node_ref, target, self.into());
+            let info_init = NodeRefInfo::new(node_ref, handle, self.into());
             match info.pin_init_with(info_init) {
                 Ok(info) => ListArc::pair_from_pin_unique(info),
                 // error is infallible
@@ -838,9 +856,10 @@ pub(crate) fn insert_or_update_handle(
         // `info_node` into the right node's `refs` list.
         unsafe { info_proc.node_ref2().node.insert_node_info(info_node) };
 
-        refs.by_node.insert(reserve1.into_node(gid, target));
-        refs.by_handle.insert(reserve2.into_node(target, info_proc));
-        Ok(target)
+        refs.by_node.insert(reserve1.into_node(gid, handle));
+        by_handle_slot.insert(info_proc, reserve2);
+        unused_id.acquire();
+        Ok(handle)
     }
 
     pub(crate) fn get_transaction_node(&self, handle: u32) -> BinderResult<NodeRef> {
@@ -905,6 +924,16 @@ pub(crate) fn update_ref(
                 let id = info.node_ref().node.global_id();
                 refs.by_handle.remove(&handle);
                 refs.by_node.remove(&id);
+                refs.handle_is_present.release_id(handle as usize);
+
+                if let Some(shrink) = refs.handle_is_present.shrink_request() {
+                    drop(refs);
+                    // This intentionally ignores allocation failures.
+                    if let Ok(new_bitmap) = shrink.realloc(GFP_KERNEL) {
+                        refs = self.node_refs.lock();
+                        refs.handle_is_present.shrink(new_bitmap);
+                    }
+                }
             }
         } else {
             // All refs are cleared in process exit, so this warning is expected in that case.

-- 
2.51.0.869.ge66316f041-goog

Re: [PATCH v2 5/5] rust_binder: use bitmap for allocation of handles

[Burak Emir]

On Tue, Oct 21, 2025 at 3:33 PM Alice Ryhl <aliceryhl@google.com> wrote:
>
> To find an unused Binder handle, Rust Binder currently iterates the
> red/black tree from the beginning until it finds a gap in the keys. This
> is extremely slow.
>
> To improve the performance, add a bitmap that keeps track of which
> indices are actually in use. This allows us to quickly find an unused
> key in the red/black tree.
>
> This logic matches the approach used by C Binder. It was chosen
> partially because it's the most memory efficient solution.
>
> Signed-off-by: Alice Ryhl <aliceryhl@google.com>
Reviewed-by: Burak Emir <bqe@google.com>