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

[PATCH v3 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 v3:
- Also update documentation to fix compile errors.
- Use new_inline() instead of new_small().
- Reword commit message of "rust: id_pool: do not supply starting capacity"
- Change UnusedId::acquire() to return usize.
- Link to v2: https://lore.kernel.org/r/20251021-binder-bitmap-v2-0-e652d172c62b@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_inline()
      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            | 109 +++++++++++++++++++++++---------------
 3 files changed, 134 insertions(+), 64 deletions(-)
---
base-commit: 211ddde0823f1442e4ad052a2f30f050145ccada
change-id: 20251007-binder-bitmap-5aa0d966fb1f

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

[PATCH v3 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.1.838.g19442a804e-goog

[PATCH v3 2/5] rust: bitmap: add BitmapVec::new_inline()

[Alice Ryhl]

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

Acked-by: Yury Norov (NVIDIA) <yury.norov@gmail.com>
Reviewed-by: Burak Emir <bqe@google.com>
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..f385a539a90ba87a7b9f6d686e150e95e358bbef 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;
 
+    /// Construct a longest possible inline [`BitmapVec`].
+    #[inline]
+    pub fn new_inline() -> 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.1.838.g19442a804e-goog

Re: [PATCH v3 2/5] rust: bitmap: add BitmapVec::new_inline()

[Danilo Krummrich]

On 10/28/25 11:55 AM, 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.
> 
> Acked-by: Yury Norov (NVIDIA) <yury.norov@gmail.com>
> Reviewed-by: Burak Emir <bqe@google.com>
> Signed-off-by: Alice Ryhl <aliceryhl@google.com>

Reviewed-by: Danilo Krummrich <dakr@kernel.org>

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

[Alice Ryhl]

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.

The existing constructor could be renamed to with_capacity() to match
constructors for other similar types, but it is removed as there is
currently no user for it.

Acked-by: Yury Norov (NVIDIA) <yury.norov@gmail.com>
Reviewed-by: Burak Emir <bqe@google.com>
Signed-off-by: Alice Ryhl <aliceryhl@google.com>
---
 rust/kernel/id_pool.rs | 46 ++++++++++++++++++----------------------------
 1 file changed, 18 insertions(+), 28 deletions(-)

diff --git a/rust/kernel/id_pool.rs b/rust/kernel/id_pool.rs
index a41a3404213ca92d53b14c80101afff6ac8c416e..d53628a357ed84a6e00ef9dfd03a75e85a87532c 100644
--- a/rust/kernel/id_pool.rs
+++ b/rust/kernel/id_pool.rs
@@ -28,19 +28,21 @@
 /// use kernel::alloc::{AllocError, flags::GFP_KERNEL};
 /// use kernel::id_pool::IdPool;
 ///
-/// let mut pool = IdPool::new(64, GFP_KERNEL)?;
-/// for i in 0..64 {
+/// let mut pool = IdPool::new();
+/// let cap = pool.capacity();
+///
+/// for i in 0..cap {
 ///     assert_eq!(i, pool.acquire_next_id(i).ok_or(ENOSPC)?);
 /// }
 ///
-/// pool.release_id(23);
-/// assert_eq!(23, pool.acquire_next_id(0).ok_or(ENOSPC)?);
+/// pool.release_id(5);
+/// assert_eq!(5, pool.acquire_next_id(0).ok_or(ENOSPC)?);
 ///
 /// assert_eq!(None, pool.acquire_next_id(0));  // time to realloc.
 /// let resizer = pool.grow_request().ok_or(ENOSPC)?.realloc(GFP_KERNEL)?;
 /// pool.grow(resizer);
 ///
-/// assert_eq!(pool.acquire_next_id(0), Some(64));
+/// assert_eq!(pool.acquire_next_id(0), Some(cap));
 /// # Ok::<(), Error>(())
 /// ```
 ///
@@ -96,16 +98,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_inline(),
+        }
     }
 
     /// Returns how many IDs this pool can currently have.
@@ -119,20 +116,6 @@ pub fn capacity(&self) -> usize {
     /// The capacity of an [`IdPool`] cannot be shrunk below [`BITS_PER_LONG`].
     ///
     /// [`BITS_PER_LONG`]: srctree/include/asm-generic/bitsperlong.h
-    ///
-    /// # Examples
-    ///
-    /// ```
-    /// use kernel::alloc::{AllocError, flags::GFP_KERNEL};
-    /// use kernel::id_pool::{ReallocRequest, IdPool};
-    ///
-    /// let mut pool = IdPool::new(1024, GFP_KERNEL)?;
-    /// let alloc_request = pool.shrink_request().ok_or(AllocError)?;
-    /// let resizer = alloc_request.realloc(GFP_KERNEL)?;
-    /// pool.shrink(resizer);
-    /// assert_eq!(pool.capacity(), kernel::bindings::BITS_PER_LONG as usize);
-    /// # Ok::<(), AllocError>(())
-    /// ```
     #[inline]
     pub fn shrink_request(&self) -> Option<ReallocRequest> {
         let cap = self.capacity();
@@ -224,3 +207,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.1.838.g19442a804e-goog

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

[Danilo Krummrich]

On 10/28/25 11:55 AM, Alice Ryhl wrote:
> 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.
> 
> The existing constructor could be renamed to with_capacity() to match
> constructors for other similar types, but it is removed as there is
> currently no user for it.
> 
> Acked-by: Yury Norov (NVIDIA) <yury.norov@gmail.com>
> Reviewed-by: Burak Emir <bqe@google.com>
> Signed-off-by: Alice Ryhl <aliceryhl@google.com>

Reviewed-by: Danilo Krummrich <dakr@kernel.org>

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

[Alexandre Courbot]

On Tue Oct 28, 2025 at 7:55 PM JST, Alice Ryhl wrote:
> 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.
>
> The existing constructor could be renamed to with_capacity() to match
> constructors for other similar types, but it is removed as there is
> currently no user for it.
>
> Acked-by: Yury Norov (NVIDIA) <yury.norov@gmail.com>
> Reviewed-by: Burak Emir <bqe@google.com>
> Signed-off-by: Alice Ryhl <aliceryhl@google.com>
> ---
>  rust/kernel/id_pool.rs | 46 ++++++++++++++++++----------------------------
>  1 file changed, 18 insertions(+), 28 deletions(-)
>
> diff --git a/rust/kernel/id_pool.rs b/rust/kernel/id_pool.rs
> index a41a3404213ca92d53b14c80101afff6ac8c416e..d53628a357ed84a6e00ef9dfd03a75e85a87532c 100644
> --- a/rust/kernel/id_pool.rs
> +++ b/rust/kernel/id_pool.rs
> @@ -28,19 +28,21 @@
>  /// use kernel::alloc::{AllocError, flags::GFP_KERNEL};
>  /// use kernel::id_pool::IdPool;
>  ///
> -/// let mut pool = IdPool::new(64, GFP_KERNEL)?;
> -/// for i in 0..64 {
> +/// let mut pool = IdPool::new();
> +/// let cap = pool.capacity();
> +///
> +/// for i in 0..cap {
>  ///     assert_eq!(i, pool.acquire_next_id(i).ok_or(ENOSPC)?);
>  /// }
>  ///
> -/// pool.release_id(23);
> -/// assert_eq!(23, pool.acquire_next_id(0).ok_or(ENOSPC)?);
> +/// pool.release_id(5);
> +/// assert_eq!(5, pool.acquire_next_id(0).ok_or(ENOSPC)?);
>  ///
>  /// assert_eq!(None, pool.acquire_next_id(0));  // time to realloc.
>  /// let resizer = pool.grow_request().ok_or(ENOSPC)?.realloc(GFP_KERNEL)?;
>  /// pool.grow(resizer);
>  ///
> -/// assert_eq!(pool.acquire_next_id(0), Some(64));
> +/// assert_eq!(pool.acquire_next_id(0), Some(cap));
>  /// # Ok::<(), Error>(())
>  /// ```
>  ///
> @@ -96,16 +98,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

A word about the capacity of this pool would be helpful here IMHO -
without anything one could assume it is 0, which is not the case.

>      #[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_inline(),
> +        }
>      }
>  
>      /// Returns how many IDs this pool can currently have.
> @@ -119,20 +116,6 @@ pub fn capacity(&self) -> usize {
>      /// The capacity of an [`IdPool`] cannot be shrunk below [`BITS_PER_LONG`].
>      ///
>      /// [`BITS_PER_LONG`]: srctree/include/asm-generic/bitsperlong.h
> -    ///
> -    /// # Examples
> -    ///
> -    /// ```
> -    /// use kernel::alloc::{AllocError, flags::GFP_KERNEL};
> -    /// use kernel::id_pool::{ReallocRequest, IdPool};
> -    ///
> -    /// let mut pool = IdPool::new(1024, GFP_KERNEL)?;
> -    /// let alloc_request = pool.shrink_request().ok_or(AllocError)?;
> -    /// let resizer = alloc_request.realloc(GFP_KERNEL)?;
> -    /// pool.shrink(resizer);
> -    /// assert_eq!(pool.capacity(), kernel::bindings::BITS_PER_LONG as usize);
> -    /// # Ok::<(), AllocError>(())

Is this test deleted because the old constructor has been removed? If so
I'd say that justifies keeping it around, having tests is valuable in
itself and the example is quite helpful to understand how the
not-so-obvious resizing process works.

[PATCH v3 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 | 67 ++++++++++++++++++++++++++++++++++++++------------
 1 file changed, 51 insertions(+), 16 deletions(-)

diff --git a/rust/kernel/id_pool.rs b/rust/kernel/id_pool.rs
index d53628a357ed84a6e00ef9dfd03a75e85a87532c..e5651162db084f5dc7c16a493aa69ee253fe4885 100644
--- a/rust/kernel/id_pool.rs
+++ b/rust/kernel/id_pool.rs
@@ -25,24 +25,24 @@
 /// Basic usage
 ///
 /// ```
-/// use kernel::alloc::{AllocError, flags::GFP_KERNEL};
-/// use kernel::id_pool::IdPool;
+/// use kernel::alloc::AllocError;
+/// use kernel::id_pool::{IdPool, UnusedId};
 ///
 /// let mut pool = IdPool::new();
 /// let cap = pool.capacity();
 ///
 /// for i in 0..cap {
-///     assert_eq!(i, pool.acquire_next_id(i).ok_or(ENOSPC)?);
+///     assert_eq!(i, pool.find_unused_id(i).ok_or(ENOSPC)?.acquire());
 /// }
 ///
 /// pool.release_id(5);
-/// assert_eq!(5, pool.acquire_next_id(0).ok_or(ENOSPC)?);
+/// assert_eq!(5, pool.find_unused_id(0).ok_or(ENOSPC)?.acquire());
 ///
-/// assert_eq!(None, pool.acquire_next_id(0));  // time to realloc.
+/// assert!(pool.find_unused_id(0).is_none());  // time to realloc.
 /// let resizer = pool.grow_request().ok_or(ENOSPC)?.realloc(GFP_KERNEL)?;
 /// pool.grow(resizer);
 ///
-/// assert_eq!(pool.acquire_next_id(0), Some(cap));
+/// assert_eq!(pool.find_unused_id(0).ok_or(ENOSPC)?.acquire(), cap);
 /// # Ok::<(), Error>(())
 /// ```
 ///
@@ -56,8 +56,8 @@
 /// fn get_id_maybe_realloc(guarded_pool: &SpinLock<IdPool>) -> Result<usize, AllocError> {
 ///     let mut pool = guarded_pool.lock();
 ///     loop {
-///         match pool.acquire_next_id(0) {
-///             Some(index) => return Ok(index),
+///         match pool.find_unused_id(0) {
+///             Some(index) => return Ok(index.acquire()),
 ///             None => {
 ///                 let alloc_request = pool.grow_request();
 ///                 drop(pool);
@@ -187,18 +187,17 @@ 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
+    #[must_use]
+    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.
@@ -208,6 +207,42 @@ 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.
+    #[inline]
+    #[must_use]
+    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.
+    #[inline]
+    #[must_use]
+    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.
+    #[inline]
+    pub fn acquire(self) -> usize {
+        self.pool.map.set_bit(self.id);
+        self.id
+    }
+}
+
 impl Default for IdPool {
     #[inline]
     fn default() -> Self {

-- 
2.51.1.838.g19442a804e-goog

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

[Yury Norov]

On Tue, Oct 28, 2025 at 10:55:17AM +0000, Alice Ryhl 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.

Hi Alice,

I'm not sure about this change, but it looks like a lock wrapping
acquire_next_id().

If so, we don't protect functions with locks, we protect data
structures.

If the above is wrong, and this new UnusedId type serializes all
accesses to a bitmap (lock-like), or write-accesses (rw-lock like),
then this is still questionable.

Bitmaps are widely adopted as a lockless data structure among the
kernel. If you modify bitmaps with set_bit() and clear_bit() only,
with some precautions you are running race-proof. The kernel lacks
for atomic bit-aquire function, but you can implement it youself.

I actually proposed atomic acquire API, but it was rejected:

https://lore.kernel.org/all/20240620175703.605111-2-yury.norov@gmail.com/

You can check the above series for a number of examples.

Bitmaps are widely used because they allow to implement lockless data
access so cheap with just set_bit() and clear_bit(). There's nothing
wrong to allocate a bit and release it shortly in case of some error
just because it's really cheap.

So, with all the above said, I've nothing against this UnusedId,
but if you need it to only serialize the access to an underlying
bitmap, can you explain in more details what's wrong with the existing
pattern? If you have a performance impact in mind, can you show any
numbers?

Thanks,
Yury

> Signed-off-by: Alice Ryhl <aliceryhl@google.com>
> ---
>  rust/kernel/id_pool.rs | 67 ++++++++++++++++++++++++++++++++++++++------------
>  1 file changed, 51 insertions(+), 16 deletions(-)
> 
> diff --git a/rust/kernel/id_pool.rs b/rust/kernel/id_pool.rs
> index d53628a357ed84a6e00ef9dfd03a75e85a87532c..e5651162db084f5dc7c16a493aa69ee253fe4885 100644
> --- a/rust/kernel/id_pool.rs
> +++ b/rust/kernel/id_pool.rs
> @@ -25,24 +25,24 @@
>  /// Basic usage
>  ///
>  /// ```
> -/// use kernel::alloc::{AllocError, flags::GFP_KERNEL};
> -/// use kernel::id_pool::IdPool;
> +/// use kernel::alloc::AllocError;
> +/// use kernel::id_pool::{IdPool, UnusedId};
>  ///
>  /// let mut pool = IdPool::new();
>  /// let cap = pool.capacity();
>  ///
>  /// for i in 0..cap {
> -///     assert_eq!(i, pool.acquire_next_id(i).ok_or(ENOSPC)?);
> +///     assert_eq!(i, pool.find_unused_id(i).ok_or(ENOSPC)?.acquire());
>  /// }
>  ///
>  /// pool.release_id(5);
> -/// assert_eq!(5, pool.acquire_next_id(0).ok_or(ENOSPC)?);
> +/// assert_eq!(5, pool.find_unused_id(0).ok_or(ENOSPC)?.acquire());
>  ///
> -/// assert_eq!(None, pool.acquire_next_id(0));  // time to realloc.
> +/// assert!(pool.find_unused_id(0).is_none());  // time to realloc.
>  /// let resizer = pool.grow_request().ok_or(ENOSPC)?.realloc(GFP_KERNEL)?;
>  /// pool.grow(resizer);
>  ///
> -/// assert_eq!(pool.acquire_next_id(0), Some(cap));
> +/// assert_eq!(pool.find_unused_id(0).ok_or(ENOSPC)?.acquire(), cap);
>  /// # Ok::<(), Error>(())
>  /// ```
>  ///
> @@ -56,8 +56,8 @@
>  /// fn get_id_maybe_realloc(guarded_pool: &SpinLock<IdPool>) -> Result<usize, AllocError> {
>  ///     let mut pool = guarded_pool.lock();
>  ///     loop {
> -///         match pool.acquire_next_id(0) {
> -///             Some(index) => return Ok(index),
> +///         match pool.find_unused_id(0) {
> +///             Some(index) => return Ok(index.acquire()),
>  ///             None => {
>  ///                 let alloc_request = pool.grow_request();
>  ///                 drop(pool);
> @@ -187,18 +187,17 @@ 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
> +    #[must_use]
> +    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.
> @@ -208,6 +207,42 @@ 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.
> +    #[inline]
> +    #[must_use]
> +    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.
> +    #[inline]
> +    #[must_use]
> +    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.
> +    #[inline]
> +    pub fn acquire(self) -> usize {
> +        self.pool.map.set_bit(self.id);
> +        self.id
> +    }
> +}
> +
>  impl Default for IdPool {
>      #[inline]
>      fn default() -> Self {
> 
> -- 
> 2.51.1.838.g19442a804e-goog

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

[Danilo Krummrich]

On Tue Oct 28, 2025 at 7:42 PM CET, Yury Norov wrote:
> I'm not sure about this change, but it looks like a lock wrapping
> acquire_next_id().

It leverages the borrow concept of Rust [1].

The Rust compiler ensures that a mutable reference is exclusive, so there can't
be two independent mutable borrows at a time.

This means that if an object A has a mutable reference of another object B, the
compiler prevents a third object C to have a (mutable) reference of B as well.

So what this ensures is that object A has exclusive access to object B within
the same task -- no concurrency involved.

The way this is connected with concurrency and locks is that if an object is
shared between tasks, you would need a lock to obtain a mutable reference, i.e.
the lock provides the precondition for exclusive access.

So, (mutable) references are about ownership, not synchronization.

I sketched up a simplified and runnable example of the idea behind Alice' code
in [2] to play with, in case you are interested -- I think that clarifies it
best. :)

[1] https://play.rust-lang.org/?version=stable&mode=debug&edition=2024&gist=5e67f1ea36b7e4561bcf5b41137284ec
[2] https://doc.rust-lang.org/book/ch04-02-references-and-borrowing.html

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

[Alice Ryhl]

On Tue, Oct 28, 2025 at 02:42:13PM -0400, Yury Norov wrote:
> On Tue, Oct 28, 2025 at 10:55:17AM +0000, Alice Ryhl 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.
> 
> Hi Alice,
> 
> I'm not sure about this change, but it looks like a lock wrapping
> acquire_next_id().
> 
> If so, we don't protect functions with locks, we protect data
> structures.
> 
> If the above is wrong, and this new UnusedId type serializes all
> accesses to a bitmap (lock-like), or write-accesses (rw-lock like),
> then this is still questionable.
> 
> Bitmaps are widely adopted as a lockless data structure among the
> kernel. If you modify bitmaps with set_bit() and clear_bit() only,
> with some precautions you are running race-proof. The kernel lacks
> for atomic bit-aquire function, but you can implement it youself.
> 
> I actually proposed atomic acquire API, but it was rejected:
> 
> https://lore.kernel.org/all/20240620175703.605111-2-yury.norov@gmail.com/
> 
> You can check the above series for a number of examples.
> 
> Bitmaps are widely used because they allow to implement lockless data
> access so cheap with just set_bit() and clear_bit(). There's nothing
> wrong to allocate a bit and release it shortly in case of some error
> just because it's really cheap.
> 
> So, with all the above said, I've nothing against this UnusedId,
> but if you need it to only serialize the access to an underlying
> bitmap, can you explain in more details what's wrong with the existing
> pattern? If you have a performance impact in mind, can you show any
> numbers?
> 
> Thanks,
> Yury

Hi Yury,

This does not change the locking requirements of IdPool at all. Both
before and after this change, acquiring a bit from the pool uses the
signature &mut self, which means that the caller of the method is
required to enforce exclusive access to the entire IdPool (doesn't have
to be a lock - the caller may use any exclusion mechanism of its
choosing). In the case of Rust Binder, exclusive access is enforced
using a spinlock. In the case of the examples in IdPool docs, exclusive
access is enforced by having the IdPool be stored in a local variable
that has not been shared with anyone.

It's true that the underlying bitmap supports lockless/atomic operations
by using the methods set_bit_atomic() and similar. Those methods are
&self rather than &mut self because they do not require exclusive access
to the entire Bitmap. But IdPool can't provide &self methods. The
existing acquire_next_id() method has a race condition if you tried to
perform two calls in parallel. But even if we changed it to perform a
correct atomic bit-acquire, the fact that IdPool is resizable also
incurs a locking requirement.

The only purpose of this UnusedId change is to make use of RAII to
automatically clean up the acquired ID in error paths. I avoided
setting the bit right away for simplicity, but setting the bit and
unsetting it in error paths via RAII would also work. But there would
still be a lock in Rust Binder that protects the bitmap without this
change.

Alice

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

[Yury Norov]

On Tue, Oct 28, 2025 at 09:48:04PM +0000, Alice Ryhl wrote:
> On Tue, Oct 28, 2025 at 02:42:13PM -0400, Yury Norov wrote:
> > On Tue, Oct 28, 2025 at 10:55:17AM +0000, Alice Ryhl 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.
> > 
> > Hi Alice,
> > 
> > I'm not sure about this change, but it looks like a lock wrapping
> > acquire_next_id().
> > 
> > If so, we don't protect functions with locks, we protect data
> > structures.
> > 
> > If the above is wrong, and this new UnusedId type serializes all
> > accesses to a bitmap (lock-like), or write-accesses (rw-lock like),
> > then this is still questionable.
> > 
> > Bitmaps are widely adopted as a lockless data structure among the
> > kernel. If you modify bitmaps with set_bit() and clear_bit() only,
> > with some precautions you are running race-proof. The kernel lacks
> > for atomic bit-aquire function, but you can implement it youself.
> > 
> > I actually proposed atomic acquire API, but it was rejected:
> > 
> > https://lore.kernel.org/all/20240620175703.605111-2-yury.norov@gmail.com/
> > 
> > You can check the above series for a number of examples.
> > 
> > Bitmaps are widely used because they allow to implement lockless data
> > access so cheap with just set_bit() and clear_bit(). There's nothing
> > wrong to allocate a bit and release it shortly in case of some error
> > just because it's really cheap.
> > 
> > So, with all the above said, I've nothing against this UnusedId,
> > but if you need it to only serialize the access to an underlying
> > bitmap, can you explain in more details what's wrong with the existing
> > pattern? If you have a performance impact in mind, can you show any
> > numbers?
> > 
> > Thanks,
> > Yury
> 
> Hi Yury,
> 
> This does not change the locking requirements of IdPool at all. Both
> before and after this change, acquiring a bit from the pool uses the
> signature &mut self, which means that the caller of the method is
> required to enforce exclusive access to the entire IdPool (doesn't have
> to be a lock - the caller may use any exclusion mechanism of its
> choosing). In the case of Rust Binder, exclusive access is enforced
> using a spinlock. In the case of the examples in IdPool docs, exclusive
> access is enforced by having the IdPool be stored in a local variable
> that has not been shared with anyone.
> 
> It's true that the underlying bitmap supports lockless/atomic operations
> by using the methods set_bit_atomic() and similar. Those methods are
> &self rather than &mut self because they do not require exclusive access
> to the entire Bitmap. But IdPool can't provide &self methods. The
> existing acquire_next_id() method has a race condition if you tried to
> perform two calls in parallel.

You can use test_and_set_bit(), so that even if multiple threads will
find the same bit, only one will actually acquire it.

> But even if we changed it to perform a
> correct atomic bit-acquire, the fact that IdPool is resizable also
> incurs a locking requirement.

To address resizing, you can use RCU engine, so that resize is
possible only during grace period.
 
> The only purpose of this UnusedId change is to make use of RAII to
> automatically clean up the acquired ID in error paths. I avoided
> setting the bit right away for simplicity, but setting the bit and
> unsetting it in error paths via RAII would also work. But there would
> still be a lock in Rust Binder that protects the bitmap without this
> change.

OK then.

There's still no real users for the IdPool, so the above performance
hints make no practical reasons. Are there any plans to actually start
using IdPool in the mainline kernel?

Thanks,
Yury

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

[Alice Ryhl]

On Mon, Nov 3, 2025 at 10:21 PM Yury Norov <yury.norov@gmail.com> wrote:
>
> On Tue, Oct 28, 2025 at 09:48:04PM +0000, Alice Ryhl wrote:
> > On Tue, Oct 28, 2025 at 02:42:13PM -0400, Yury Norov wrote:
> > > On Tue, Oct 28, 2025 at 10:55:17AM +0000, Alice Ryhl 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.
> > >
> > > Hi Alice,
> > >
> > > I'm not sure about this change, but it looks like a lock wrapping
> > > acquire_next_id().
> > >
> > > If so, we don't protect functions with locks, we protect data
> > > structures.
> > >
> > > If the above is wrong, and this new UnusedId type serializes all
> > > accesses to a bitmap (lock-like), or write-accesses (rw-lock like),
> > > then this is still questionable.
> > >
> > > Bitmaps are widely adopted as a lockless data structure among the
> > > kernel. If you modify bitmaps with set_bit() and clear_bit() only,
> > > with some precautions you are running race-proof. The kernel lacks
> > > for atomic bit-aquire function, but you can implement it youself.
> > >
> > > I actually proposed atomic acquire API, but it was rejected:
> > >
> > > https://lore.kernel.org/all/20240620175703.605111-2-yury.norov@gmail.com/
> > >
> > > You can check the above series for a number of examples.
> > >
> > > Bitmaps are widely used because they allow to implement lockless data
> > > access so cheap with just set_bit() and clear_bit(). There's nothing
> > > wrong to allocate a bit and release it shortly in case of some error
> > > just because it's really cheap.
> > >
> > > So, with all the above said, I've nothing against this UnusedId,
> > > but if you need it to only serialize the access to an underlying
> > > bitmap, can you explain in more details what's wrong with the existing
> > > pattern? If you have a performance impact in mind, can you show any
> > > numbers?
> > >
> > > Thanks,
> > > Yury
> >
> > Hi Yury,
> >
> > This does not change the locking requirements of IdPool at all. Both
> > before and after this change, acquiring a bit from the pool uses the
> > signature &mut self, which means that the caller of the method is
> > required to enforce exclusive access to the entire IdPool (doesn't have
> > to be a lock - the caller may use any exclusion mechanism of its
> > choosing). In the case of Rust Binder, exclusive access is enforced
> > using a spinlock. In the case of the examples in IdPool docs, exclusive
> > access is enforced by having the IdPool be stored in a local variable
> > that has not been shared with anyone.
> >
> > It's true that the underlying bitmap supports lockless/atomic operations
> > by using the methods set_bit_atomic() and similar. Those methods are
> > &self rather than &mut self because they do not require exclusive access
> > to the entire Bitmap. But IdPool can't provide &self methods. The
> > existing acquire_next_id() method has a race condition if you tried to
> > perform two calls in parallel.
>
> You can use test_and_set_bit(), so that even if multiple threads will
> find the same bit, only one will actually acquire it.
>
> > But even if we changed it to perform a
> > correct atomic bit-acquire, the fact that IdPool is resizable also
> > incurs a locking requirement.
>
> To address resizing, you can use RCU engine, so that resize is
> possible only during grace period.

Considering that the actual use-case for this already needs a spinlock
to protect related resources when it touches the bitmap, introducing
rcu seems unnecessary.

> > The only purpose of this UnusedId change is to make use of RAII to
> > automatically clean up the acquired ID in error paths. I avoided
> > setting the bit right away for simplicity, but setting the bit and
> > unsetting it in error paths via RAII would also work. But there would
> > still be a lock in Rust Binder that protects the bitmap without this
> > change.
>
> OK then.
>
> There's still no real users for the IdPool, so the above performance
> hints make no practical reasons. Are there any plans to actually start
> using IdPool in the mainline kernel?

Patch 5 in this series introduces a user in the mainline kernel.

Alice

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

[Danilo Krummrich]

On 10/28/25 11:55 AM, Alice Ryhl wrote:
> +/// 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.
> +    #[inline]
> +    #[must_use]
> +    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.
> +    #[inline]
> +    #[must_use]
> +    pub fn as_u32(&self) -> u32 {
> +        // CAST: The maximum possible value in an IdPool is i32::MAX.

I think this should rather be an invariant of `UnusedId`.

Reviewed-by: Danilo Krummrich <dakr@kernel.org>

> +        self.id as u32
> +    }

[PATCH v3 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.

Reviewed-by: Burak Emir <bqe@google.com>
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.1.838.g19442a804e-goog

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

[Carlos Llamas]

On Tue, Oct 28, 2025 at 10:55:18AM +0000, Alice Ryhl 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.
> 
> Reviewed-by: Burak Emir <bqe@google.com>
> Signed-off-by: Alice Ryhl <aliceryhl@google.com>
> ---

LGTM,

Acked-by: Carlos Llamas <cmllamas@google.com>