[PATCH v6 0/6] Use Rust Bitmap from Rust Binder driver

[PATCH v6 0/6] 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 v6:
- Fix rebase mixups.
- Include benchmark in commit message.
- Link to v5: https://lore.kernel.org/r/20251112-binder-bitmap-v5-0-8b9d7c7eca82@google.com

Changes in v5:
- Rename NO_ALLOC_MAX_LEN to MAX_INLINE_LEN.
- Update all uses of MAX_LEN/MAX_INLINE_LEN to reference the new
  constants.
- Link to v4: https://lore.kernel.org/r/20251110-binder-bitmap-v4-0-5ed8a7fab1b9@google.com

Changes in v4:
- Keep existing IdPool constructor (renamed to with_capacity).
- Undo docs changes that were due to the removal of the existing IdPool
  constructor.
- List id < pool.map.len() as invariant for UnusedId and mention it in
  as_u32() comment.
- Fix [`acquire`] docs links.
- Link to v3: https://lore.kernel.org/r/20251028-binder-bitmap-v3-0-32822d4b3207@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 (6):
      rust: bitmap: add MAX_LEN and MAX_INLINE_LEN constants
      rust: bitmap: add BitmapVec::new_inline()
      rust: id_pool: rename IdPool::new() to with_capacity()
      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 |  64 +++++++++++++-----
 rust/kernel/bitmap.rs             |  43 ++++++++----
 rust/kernel/id_pool.rs            | 139 ++++++++++++++++++++++++++++----------
 3 files changed, 180 insertions(+), 66 deletions(-)
---
base-commit: 211ddde0823f1442e4ad052a2f30f050145ccada
change-id: 20251007-binder-bitmap-5aa0d966fb1f

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

[PATCH v6 1/6] rust: bitmap: add MAX_LEN and MAX_INLINE_LEN constants

[Alice Ryhl]

To avoid hard-coding these values in drivers, define constants for them
that drivers can reference. Also, update all instances in bitmap.rs and
id_pool.rs that use these values to use the new constants.

Signed-off-by: Alice Ryhl <aliceryhl@google.com>
---
 rust/kernel/bitmap.rs  | 33 +++++++++++++++++++--------------
 rust/kernel/id_pool.rs | 39 ++++++++++++++++++++++-----------------
 2 files changed, 41 insertions(+), 31 deletions(-)

diff --git a/rust/kernel/bitmap.rs b/rust/kernel/bitmap.rs
index aa8fc7bf06fc99865ae755d8694e4bec3dc8e7f0..0705646c6251a49f213a45f1f013cb9eb2ed81de 100644
--- a/rust/kernel/bitmap.rs
+++ b/rust/kernel/bitmap.rs
@@ -12,8 +12,6 @@
 use crate::pr_err;
 use core::ptr::NonNull;
 
-const BITS_PER_LONG: usize = bindings::BITS_PER_LONG as usize;
-
 /// Represents a C bitmap. Wraps underlying C bitmap API.
 ///
 /// # Invariants
@@ -149,14 +147,14 @@ macro_rules! bitmap_assert_return {
 ///
 /// # Invariants
 ///
-/// * `nbits` is `<= i32::MAX` and never changes.
-/// * if `nbits <= bindings::BITS_PER_LONG`, then `repr` is a `usize`.
+/// * `nbits` is `<= MAX_LEN`.
+/// * if `nbits <= MAX_INLINE_LEN`, 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,
 }
 
@@ -164,7 +162,7 @@ impl core::ops::Deref for BitmapVec {
     type Target = Bitmap;
 
     fn deref(&self) -> &Bitmap {
-        let ptr = if self.nbits <= BITS_PER_LONG {
+        let ptr = if self.nbits <= BitmapVec::MAX_INLINE_LEN {
             // SAFETY: Bitmap is represented inline.
             #[allow(unused_unsafe, reason = "Safe since Rust 1.92.0")]
             unsafe {
@@ -183,7 +181,7 @@ fn deref(&self) -> &Bitmap {
 
 impl core::ops::DerefMut for BitmapVec {
     fn deref_mut(&mut self) -> &mut Bitmap {
-        let ptr = if self.nbits <= BITS_PER_LONG {
+        let ptr = if self.nbits <= BitmapVec::MAX_INLINE_LEN {
             // SAFETY: Bitmap is represented inline.
             #[allow(unused_unsafe, reason = "Safe since Rust 1.92.0")]
             unsafe {
@@ -213,7 +211,7 @@ unsafe impl Sync for BitmapVec {}
 
 impl Drop for BitmapVec {
     fn drop(&mut self) {
-        if self.nbits <= BITS_PER_LONG {
+        if self.nbits <= BitmapVec::MAX_INLINE_LEN {
             return;
         }
         // SAFETY: `self.ptr` was returned by the C `bitmap_zalloc`.
@@ -226,23 +224,29 @@ 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 uses the inline representation.
+    pub const MAX_INLINE_LEN: usize = usize::BITS as usize;
+
     /// 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 {
+        if nbits <= BitmapVec::MAX_INLINE_LEN {
             return Ok(BitmapVec {
                 repr: BitmapRepr { bitmap: 0 },
                 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: `MAX_INLINE_LEN < 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.
@@ -495,9 +499,10 @@ mod tests {
     #[test]
     fn bitmap_borrow() {
         let fake_bitmap: [usize; 2] = [0, 0];
+        let fake_bitmap_len = 2 * usize::BITS as usize;
         // SAFETY: `fake_c_bitmap` is an array of expected length.
-        let b = unsafe { Bitmap::from_raw(fake_bitmap.as_ptr(), 2 * BITS_PER_LONG) };
-        assert_eq!(2 * BITS_PER_LONG, b.len());
+        let b = unsafe { Bitmap::from_raw(fake_bitmap.as_ptr(), fake_bitmap_len) };
+        assert_eq!(fake_bitmap_len, b.len());
         assert_eq!(None, b.next_bit(0));
     }
 
diff --git a/rust/kernel/id_pool.rs b/rust/kernel/id_pool.rs
index a41a3404213ca92d53b14c80101afff6ac8c416e..0b1f720a1f7df8766a8481f3c0b332d4cff3b4ad 100644
--- a/rust/kernel/id_pool.rs
+++ b/rust/kernel/id_pool.rs
@@ -7,8 +7,6 @@
 use crate::alloc::{AllocError, Flags};
 use crate::bitmap::BitmapVec;
 
-const BITS_PER_LONG: usize = bindings::BITS_PER_LONG as usize;
-
 /// Represents a dynamic ID pool backed by a [`BitmapVec`].
 ///
 /// Clients acquire and release IDs from unset bits in a bitmap.
@@ -97,13 +95,12 @@ 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`].
+    /// A capacity below [`MAX_INLINE_LEN`] is adjusted to [`MAX_INLINE_LEN`].
     ///
-    /// [`BITS_PER_LONG`]: srctree/include/asm-generic/bitsperlong.h
+    /// [`MAX_INLINE_LEN`]: BitmapVec::MAX_INLINE_LEN
     #[inline]
     pub fn new(num_ids: usize, flags: Flags) -> Result<Self, AllocError> {
-        let num_ids = core::cmp::max(num_ids, BITS_PER_LONG);
+        let num_ids = usize::max(num_ids, BitmapVec::MAX_INLINE_LEN);
         let map = BitmapVec::new(num_ids, flags)?;
         Ok(Self { map })
     }
@@ -116,28 +113,34 @@ pub fn capacity(&self) -> usize {
 
     /// Returns a [`ReallocRequest`] if the [`IdPool`] can be shrunk, [`None`] otherwise.
     ///
-    /// The capacity of an [`IdPool`] cannot be shrunk below [`BITS_PER_LONG`].
+    /// The capacity of an [`IdPool`] cannot be shrunk below [`MAX_INLINE_LEN`].
     ///
-    /// [`BITS_PER_LONG`]: srctree/include/asm-generic/bitsperlong.h
+    /// [`MAX_INLINE_LEN`]: BitmapVec::MAX_INLINE_LEN
     ///
     /// # Examples
     ///
     /// ```
-    /// use kernel::alloc::{AllocError, flags::GFP_KERNEL};
-    /// use kernel::id_pool::{ReallocRequest, IdPool};
+    /// use kernel::{
+    ///     alloc::AllocError,
+    ///     bitmap::BitmapVec,
+    ///     id_pool::{
+    ///         IdPool,
+    ///         ReallocRequest,
+    ///     },
+    /// };
     ///
     /// 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);
+    /// assert_eq!(pool.capacity(), BitmapVec::MAX_INLINE_LEN);
     /// # Ok::<(), AllocError>(())
     /// ```
     #[inline]
     pub fn shrink_request(&self) -> Option<ReallocRequest> {
         let cap = self.capacity();
-        // Shrinking below [`BITS_PER_LONG`] is never possible.
-        if cap <= BITS_PER_LONG {
+        // Shrinking below `MAX_INLINE_LEN` is never possible.
+        if cap <= BitmapVec::MAX_INLINE_LEN {
             return None;
         }
         // Determine if the bitmap can shrink based on the position of
@@ -146,13 +149,13 @@ pub fn shrink_request(&self) -> Option<ReallocRequest> {
         // bitmap should shrink to half its current size.
         let Some(bit) = self.map.last_bit() else {
             return Some(ReallocRequest {
-                num_ids: BITS_PER_LONG,
+                num_ids: BitmapVec::MAX_INLINE_LEN,
             });
         };
         if bit >= (cap / 4) {
             return None;
         }
-        let num_ids = usize::max(BITS_PER_LONG, cap / 2);
+        let num_ids = usize::max(BitmapVec::MAX_INLINE_LEN, cap / 2);
         Some(ReallocRequest { num_ids })
     }
 
@@ -177,11 +180,13 @@ pub fn shrink(&mut self, mut resizer: PoolResizer) {
 
     /// Returns a [`ReallocRequest`] for growing this [`IdPool`], if possible.
     ///
-    /// The capacity of an [`IdPool`] cannot be grown above [`i32::MAX`].
+    /// The capacity of an [`IdPool`] cannot be grown above [`MAX_LEN`].
+    ///
+    /// [`MAX_LEN`]: BitmapVec::MAX_LEN
     #[inline]
     pub fn grow_request(&self) -> Option<ReallocRequest> {
         let num_ids = self.capacity() * 2;
-        if num_ids > i32::MAX.try_into().unwrap() {
+        if num_ids > BitmapVec::MAX_LEN {
             return None;
         }
         Some(ReallocRequest { num_ids })

-- 
2.52.0.460.gd25c4c69ec-goog

Re: [PATCH v6 1/6] rust: bitmap: add MAX_LEN and MAX_INLINE_LEN constants

[Burak Emir]

On Tue, Nov 25, 2025 at 2:59 PM Alice Ryhl <aliceryhl@google.com> wrote:
>
> To avoid hard-coding these values in drivers, define constants for them
> that drivers can reference. Also, update all instances in bitmap.rs and
> id_pool.rs that use these values to use the new constants.
>
> Signed-off-by: Alice Ryhl <aliceryhl@google.com>

Reviewed-by: Burak Emir <bqe@google.com>

[PATCH v6 2/6] 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>
Reviewed-by: Danilo Krummrich <dakr@kernel.org>
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 0705646c6251a49f213a45f1f013cb9eb2ed81de..83d7dea99137ded7cba47ec5a3bf10bb7e13f2d2 100644
--- a/rust/kernel/bitmap.rs
+++ b/rust/kernel/bitmap.rs
@@ -230,6 +230,16 @@ impl BitmapVec {
     /// The maximum length that uses the inline representation.
     pub const MAX_INLINE_LEN: usize = usize::BITS as usize;
 
+    /// Construct a longest possible inline [`BitmapVec`].
+    #[inline]
+    pub fn new_inline() -> Self {
+        // INVARIANT: `nbits <= MAX_INLINE_LEN`, so an inline bitmap is the right repr.
+        BitmapVec {
+            repr: BitmapRepr { bitmap: 0 },
+            nbits: BitmapVec::MAX_INLINE_LEN,
+        }
+    }
+
     /// Constructs a new [`BitmapVec`].
     ///
     /// Fails with [`AllocError`] when the [`BitmapVec`] could not be allocated. This

-- 
2.52.0.460.gd25c4c69ec-goog

[PATCH v6 3/6] rust: id_pool: rename IdPool::new() to with_capacity()

[Alice Ryhl]

We want to change ::new() to take no parameters and produce a pool that
is as large as possible while also being inline because that is the
constructor that Rust Binder actually needs.

However, to avoid complications in examples, we still need the current
constructor. So rename it to with_capacity(), which is the idiomatic
Rust name for this kind constructor.

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

diff --git a/rust/kernel/id_pool.rs b/rust/kernel/id_pool.rs
index 0b1f720a1f7df8766a8481f3c0b332d4cff3b4ad..7968b6c5566bf7022b865b5f59deaf46c96f747d 100644
--- a/rust/kernel/id_pool.rs
+++ b/rust/kernel/id_pool.rs
@@ -26,7 +26,7 @@
 /// use kernel::alloc::{AllocError, flags::GFP_KERNEL};
 /// use kernel::id_pool::IdPool;
 ///
-/// let mut pool = IdPool::new(64, GFP_KERNEL)?;
+/// let mut pool = IdPool::with_capacity(64, GFP_KERNEL)?;
 /// for i in 0..64 {
 ///     assert_eq!(i, pool.acquire_next_id(i).ok_or(ENOSPC)?);
 /// }
@@ -93,13 +93,13 @@ pub fn realloc(&self, flags: Flags) -> Result<PoolResizer, AllocError> {
 }
 
 impl IdPool {
-    /// Constructs a new [`IdPool`].
+    /// Constructs a new [`IdPool`] with space for a specific number of bits.
     ///
     /// A capacity below [`MAX_INLINE_LEN`] is adjusted to [`MAX_INLINE_LEN`].
     ///
     /// [`MAX_INLINE_LEN`]: BitmapVec::MAX_INLINE_LEN
     #[inline]
-    pub fn new(num_ids: usize, flags: Flags) -> Result<Self, AllocError> {
+    pub fn with_capacity(num_ids: usize, flags: Flags) -> Result<Self, AllocError> {
         let num_ids = usize::max(num_ids, BitmapVec::MAX_INLINE_LEN);
         let map = BitmapVec::new(num_ids, flags)?;
         Ok(Self { map })
@@ -129,7 +129,7 @@ pub fn capacity(&self) -> usize {
     ///     },
     /// };
     ///
-    /// let mut pool = IdPool::new(1024, GFP_KERNEL)?;
+    /// let mut pool = IdPool::with_capacity(1024, GFP_KERNEL)?;
     /// let alloc_request = pool.shrink_request().ok_or(AllocError)?;
     /// let resizer = alloc_request.realloc(GFP_KERNEL)?;
     /// pool.shrink(resizer);

-- 
2.52.0.460.gd25c4c69ec-goog

[PATCH v6 4/6] 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>
Reviewed-by: Danilo Krummrich <dakr@kernel.org>
Signed-off-by: Alice Ryhl <aliceryhl@google.com>
---
 rust/kernel/id_pool.rs | 19 +++++++++++++++++++
 1 file changed, 19 insertions(+)

diff --git a/rust/kernel/id_pool.rs b/rust/kernel/id_pool.rs
index 7968b6c5566bf7022b865b5f59deaf46c96f747d..1adec2c6fdb0b80515f9b64c67218efa864ce580 100644
--- a/rust/kernel/id_pool.rs
+++ b/rust/kernel/id_pool.rs
@@ -93,6 +93,18 @@ pub fn realloc(&self, flags: Flags) -> Result<PoolResizer, AllocError> {
 }
 
 impl IdPool {
+    /// Constructs a new [`IdPool`].
+    ///
+    /// The pool will have a capacity of [`NO_ALLOC_MAX_LEN`].
+    ///
+    /// [`NO_ALLOC_MAX_LEN`]: BitmapVec::NO_ALLOC_MAX_LEN
+    #[inline]
+    pub fn new() -> Self {
+        Self {
+            map: BitmapVec::new_inline(),
+        }
+    }
+
     /// Constructs a new [`IdPool`] with space for a specific number of bits.
     ///
     /// A capacity below [`MAX_INLINE_LEN`] is adjusted to [`MAX_INLINE_LEN`].
@@ -229,3 +241,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.52.0.460.gd25c4c69ec-goog

[PATCH v6 5/6] 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.

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

diff --git a/rust/kernel/id_pool.rs b/rust/kernel/id_pool.rs
index 1adec2c6fdb0b80515f9b64c67218efa864ce580..a4c37d6a0971699d1ea42facc68aa3dd2b44a0ca 100644
--- a/rust/kernel/id_pool.rs
+++ b/rust/kernel/id_pool.rs
@@ -23,8 +23,8 @@
 /// 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::with_capacity(64, GFP_KERNEL)?;
 /// for i in 0..64 {
@@ -32,13 +32,13 @@
 /// }
 ///
 /// pool.release_id(23);
-/// assert_eq!(23, pool.acquire_next_id(0).ok_or(ENOSPC)?);
+/// assert_eq!(23, 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(64));
+/// assert_eq!(pool.find_unused_id(0).ok_or(ENOSPC)?.acquire(), 64);
 /// # Ok::<(), Error>(())
 /// ```
 ///
@@ -52,8 +52,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);
@@ -221,18 +221,18 @@ 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<'_>> {
+        // INVARIANT: `next_zero_bit()` returns None or an integer less than `map.len()`
+        Some(UnusedId {
+            id: self.map.next_zero_bit(offset)?,
+            pool: self,
+        })
     }
 
     /// Releases an ID.
@@ -242,6 +242,51 @@ pub fn release_id(&mut self, id: usize) {
     }
 }
 
+/// Represents an unused id in an [`IdPool`].
+///
+/// # Invariants
+///
+/// The value of `id` is less than `pool.map.len()`.
+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.
+    ///
+    /// [`acquire`]: UnusedId::acquire()
+    #[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.
+    ///
+    /// [`acquire`]: UnusedId::acquire()
+    #[inline]
+    #[must_use]
+    pub fn as_u32(&self) -> u32 {
+        // CAST: By the type invariants:
+        // `self.id < pool.map.len() <= BitmapVec::MAX_LEN = 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.52.0.460.gd25c4c69ec-goog

[PATCH v6 6/6] 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.

For a benchmark, please see the below numbers that were obtained from
modifying binderThroughputTest to send a node with each transaction and
stashing it in the server. This results in the number of nodes
increasing by one for every transaction sent. I got the following table
of roundtrip latencies (in µs):

Transaction Range │ Baseline (Rust) │ Bitmap (Rust) │ Comparison (C)
0 - 10,000        │          176.88 │         92.93 │          99.41
10,000 - 20,000   │          437.37 │         87.74 │          98.55
20,000 - 30,000   │          677.49 │         76.24 │          96.37
30,000 - 40,000   │          901.76 │         83.39 │          96.73
40,000 - 50,000   │         1126.62 │        100.44 │          94.57
50,000 - 60,000   │         1288.98 │         94.38 │          96.64
60,000 - 70,000   │         1588.74 │         88.27 │          96.36
70,000 - 80,000   │         1812.97 │         93.97 │          91.24
80,000 - 90,000   │         2062.95 │         92.22 │         102.01
90,000 - 100,000  │         2330.03 │         97.18 │         100.31

It should be clear that the current Rust code becomes linearly slower
per insertion as the number of calls to rb_next() per transaction
increases. After this change, the time to find an ID number appears
constant. (Technically it is not constant-time as both insertion and
removal scan the entire bitmap. However, quick napkin math shows that
scanning the entire bitmap with N=100k takes ~1.5µs, which is neglible
in a benchmark where the rountrip latency is 100µs.)

I've included a comparison to the C driver, which uses the same bitmap
algorithm as this patch since commit 15d9da3f818c ("binder: use bitmap
for faster descriptor lookup").

This currently checks if the bitmap should be shrunk after every
removal. One potential future change is introducing a shrinker to make
this operation O(1), but based on the benchmark above this does not seem
required at this time.

Reviewed-by: Burak Emir <bqe@google.com>
Acked-by: Carlos Llamas <cmllamas@google.com>
Signed-off-by: Alice Ryhl <aliceryhl@google.com>
---
 drivers/android/binder/process.rs | 64 ++++++++++++++++++++++++++++-----------
 1 file changed, 47 insertions(+), 17 deletions(-)

diff --git a/drivers/android/binder/process.rs b/drivers/android/binder/process.rs
index f13a747e784c84a0fb09cbf47442712106eba07c..9264961fd92b33c07fcd5353740cc0b1ec978afd 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,33 @@ 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();
+                        kernel::warn_on!(true);
+                        return Err(EINVAL);
+                    }
+                }
+            }
+
+            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 +834,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 +857,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 +925,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.52.0.460.gd25c4c69ec-goog

Re: [PATCH v6 6/6] rust_binder: use bitmap for allocation of handles

[Yury Norov]

On Tue, Nov 25, 2025 at 01:59:42PM +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.
> 
> For a benchmark, please see the below numbers that were obtained from
> modifying binderThroughputTest to send a node with each transaction and
> stashing it in the server. This results in the number of nodes
> increasing by one for every transaction sent. I got the following table
> of roundtrip latencies (in µs):
> 
> Transaction Range │ Baseline (Rust) │ Bitmap (Rust) │ Comparison (C)
> 0 - 10,000        │          176.88 │         92.93 │          99.41
> 10,000 - 20,000   │          437.37 │         87.74 │          98.55
> 20,000 - 30,000   │          677.49 │         76.24 │          96.37
> 30,000 - 40,000   │          901.76 │         83.39 │          96.73
> 40,000 - 50,000   │         1126.62 │        100.44 │          94.57
> 50,000 - 60,000   │         1288.98 │         94.38 │          96.64
> 60,000 - 70,000   │         1588.74 │         88.27 │          96.36
> 70,000 - 80,000   │         1812.97 │         93.97 │          91.24
> 80,000 - 90,000   │         2062.95 │         92.22 │         102.01
> 90,000 - 100,000  │         2330.03 │         97.18 │         100.31
> 
> It should be clear that the current Rust code becomes linearly slower
> per insertion as the number of calls to rb_next() per transaction
> increases. After this change, the time to find an ID number appears
> constant. (Technically it is not constant-time as both insertion and
> removal scan the entire bitmap. However, quick napkin math shows that
> scanning the entire bitmap with N=100k takes ~1.5µs, which is neglible
> in a benchmark where the rountrip latency is 100µs.)
> 
> I've included a comparison to the C driver, which uses the same bitmap
> algorithm as this patch since commit 15d9da3f818c ("binder: use bitmap
> for faster descriptor lookup").

Thanks for the solid numbers!

> This currently checks if the bitmap should be shrunk after every
> removal. One potential future change is introducing a shrinker to make
> this operation O(1), but based on the benchmark above this does not seem
> required at this time.
> 
> Reviewed-by: Burak Emir <bqe@google.com>
> Acked-by: Carlos Llamas <cmllamas@google.com>
> Signed-off-by: Alice Ryhl <aliceryhl@google.com>
> ---
>  drivers/android/binder/process.rs | 64 ++++++++++++++++++++++++++++-----------
>  1 file changed, 47 insertions(+), 17 deletions(-)
> 
> diff --git a/drivers/android/binder/process.rs b/drivers/android/binder/process.rs
> index f13a747e784c84a0fb09cbf47442712106eba07c..9264961fd92b33c07fcd5353740cc0b1ec978afd 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,33 @@ 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();
> +                        kernel::warn_on!(true);
> +                        return Err(EINVAL);

EINVAL means that user provides a wrong parameter. Here's a data
corruption. Maybe EFAULT?

> +                    }
> +                }
> +            }
> +
> +            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);

This continues puzzling me. Refs_lock protects refs, and the spec
says:

    a reference’s scope starts from where it is introduced and
    continues through the last time that reference is used.

https://doc.rust-lang.org/book/ch04-02-references-and-borrowing.html

The last usage of refs is at .grow_request() line, because later it's
reused with the new value. 

If my reading of the spec is correct, after dropping the refs_lock,
you may get rescheduled, and another thread may follow the same path.
Because refs_lock is dropped explicitly and refs - implicitly, the
concurrent thread can grab both and follow with resizing the id map.

When your first thread will get back, you'll end up resizing the
already resized map.

I asked your AI, and it says that this race is indeed possible for
exactly that reason. But it doesn't break memory safety, so the
compiler is happy about it...

> +        };
> +        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 +834,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 +857,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 +925,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.52.0.460.gd25c4c69ec-goog

Re: [PATCH v6 6/6] rust_binder: use bitmap for allocation of handles

[Burak Emir]

> > +
> > +            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);
>
> This continues puzzling me. Refs_lock protects refs, and the spec
> says:
>
>     a reference’s scope starts from where it is introduced and
>     continues through the last time that reference is used.
>
> https://doc.rust-lang.org/book/ch04-02-references-and-borrowing.html
>
> The last usage of refs is at .grow_request() line, because later it's
> reused with the new value.
>
> If my reading of the spec is correct, after dropping the refs_lock,
> you may get rescheduled, and another thread may follow the same path.
> Because refs_lock is dropped explicitly and refs - implicitly, the
> concurrent thread can grab both and follow with resizing the id map.
>
> When your first thread will get back, you'll end up resizing the
> already resized map.
>
> I asked your AI, and it says that this race is indeed possible for
> exactly that reason. But it doesn't break memory safety, so the
> compiler is happy about it...

Yes - the writes to the map field are synchronized.
So there is no data race (= unsynchronized {read, write} / write
conflict) and corruption cannot happen.
Never mind that there is a race involving data : )

The scenario you describe is why id_pool grow() and shrink()
double-check before doing copying.
So the thread that loses the race has allocated a new array for
nothing, but things move on.

Re: [PATCH v6 6/6] rust_binder: use bitmap for allocation of handles

[Alice Ryhl]

On Tue, Nov 25, 2025 at 09:26:46PM -0500, Yury Norov wrote:
> On Tue, Nov 25, 2025 at 01:59:42PM +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.
> > 
> > For a benchmark, please see the below numbers that were obtained from
> > modifying binderThroughputTest to send a node with each transaction and
> > stashing it in the server. This results in the number of nodes
> > increasing by one for every transaction sent. I got the following table
> > of roundtrip latencies (in µs):
> > 
> > Transaction Range │ Baseline (Rust) │ Bitmap (Rust) │ Comparison (C)
> > 0 - 10,000        │          176.88 │         92.93 │          99.41
> > 10,000 - 20,000   │          437.37 │         87.74 │          98.55
> > 20,000 - 30,000   │          677.49 │         76.24 │          96.37
> > 30,000 - 40,000   │          901.76 │         83.39 │          96.73
> > 40,000 - 50,000   │         1126.62 │        100.44 │          94.57
> > 50,000 - 60,000   │         1288.98 │         94.38 │          96.64
> > 60,000 - 70,000   │         1588.74 │         88.27 │          96.36
> > 70,000 - 80,000   │         1812.97 │         93.97 │          91.24
> > 80,000 - 90,000   │         2062.95 │         92.22 │         102.01
> > 90,000 - 100,000  │         2330.03 │         97.18 │         100.31
> > 
> > It should be clear that the current Rust code becomes linearly slower
> > per insertion as the number of calls to rb_next() per transaction
> > increases. After this change, the time to find an ID number appears
> > constant. (Technically it is not constant-time as both insertion and
> > removal scan the entire bitmap. However, quick napkin math shows that
> > scanning the entire bitmap with N=100k takes ~1.5µs, which is neglible
> > in a benchmark where the rountrip latency is 100µs.)
> > 
> > I've included a comparison to the C driver, which uses the same bitmap
> > algorithm as this patch since commit 15d9da3f818c ("binder: use bitmap
> > for faster descriptor lookup").
> 
> Thanks for the solid numbers!
> 
> > This currently checks if the bitmap should be shrunk after every
> > removal. One potential future change is introducing a shrinker to make
> > this operation O(1), but based on the benchmark above this does not seem
> > required at this time.
> > 
> > Reviewed-by: Burak Emir <bqe@google.com>
> > Acked-by: Carlos Llamas <cmllamas@google.com>
> > Signed-off-by: Alice Ryhl <aliceryhl@google.com>
> > ---
> >  drivers/android/binder/process.rs | 64 ++++++++++++++++++++++++++++-----------
> >  1 file changed, 47 insertions(+), 17 deletions(-)
> > 
> > diff --git a/drivers/android/binder/process.rs b/drivers/android/binder/process.rs
> > index f13a747e784c84a0fb09cbf47442712106eba07c..9264961fd92b33c07fcd5353740cc0b1ec978afd 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,33 @@ 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();
> > +                        kernel::warn_on!(true);
> > +                        return Err(EINVAL);
> 
> EINVAL means that user provides a wrong parameter. Here's a data
> corruption. Maybe EFAULT?

Hmm ... EFAULT is used when the user passes a dangling pointer that
copy_from_user() refuses to use. I would like to avoid confusion with
that as well. Is there a third option?

> > +                    }
> > +                }
> > +            }
> > +
> > +            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);
> 
> This continues puzzling me. Refs_lock protects refs, and the spec
> says:
> 
>     a reference’s scope starts from where it is introduced and
>     continues through the last time that reference is used.
> 
> https://doc.rust-lang.org/book/ch04-02-references-and-borrowing.html
> 
> The last usage of refs is at .grow_request() line, because later it's
> reused with the new value. 
> 
> If my reading of the spec is correct, after dropping the refs_lock,
> you may get rescheduled, and another thread may follow the same path.
> Because refs_lock is dropped explicitly and refs - implicitly, the
> concurrent thread can grab both and follow with resizing the id map.
> 
> When your first thread will get back, you'll end up resizing the
> already resized map.
> 
> I asked your AI, and it says that this race is indeed possible for
> exactly that reason. But it doesn't break memory safety, so the
> compiler is happy about it...

You're right that since we release the mutex, someone else may have
resized the map in the meantime. That's why we implemented grow() to do
nothing if it was already resized:

	pub fn grow(&mut self, mut resizer: PoolResizer) {
	    // Between request to grow that led to allocation of `resizer` and now,
	    // another thread may have already grown the capacity.
	    // In this case, do nothing, drop `resizer` and move on.
	    if resizer.new.len() <= self.capacity() {
	        return;
	    }
	
	    resizer.new.copy_and_extend(&self.map);
	    self.map = resizer.new;
	}

Alice

Re: [PATCH v6 6/6] rust_binder: use bitmap for allocation of handles

[Yury Norov]

On Wed, Nov 26, 2025 at 08:35:55AM +0000, Alice Ryhl wrote:
> On Tue, Nov 25, 2025 at 09:26:46PM -0500, Yury Norov wrote:
> > On Tue, Nov 25, 2025 at 01:59:42PM +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.
> > > 
> > > For a benchmark, please see the below numbers that were obtained from
> > > modifying binderThroughputTest to send a node with each transaction and
> > > stashing it in the server. This results in the number of nodes
> > > increasing by one for every transaction sent. I got the following table
> > > of roundtrip latencies (in µs):
> > > 
> > > Transaction Range │ Baseline (Rust) │ Bitmap (Rust) │ Comparison (C)
> > > 0 - 10,000        │          176.88 │         92.93 │          99.41
> > > 10,000 - 20,000   │          437.37 │         87.74 │          98.55
> > > 20,000 - 30,000   │          677.49 │         76.24 │          96.37
> > > 30,000 - 40,000   │          901.76 │         83.39 │          96.73
> > > 40,000 - 50,000   │         1126.62 │        100.44 │          94.57
> > > 50,000 - 60,000   │         1288.98 │         94.38 │          96.64
> > > 60,000 - 70,000   │         1588.74 │         88.27 │          96.36
> > > 70,000 - 80,000   │         1812.97 │         93.97 │          91.24
> > > 80,000 - 90,000   │         2062.95 │         92.22 │         102.01
> > > 90,000 - 100,000  │         2330.03 │         97.18 │         100.31
> > > 
> > > It should be clear that the current Rust code becomes linearly slower
> > > per insertion as the number of calls to rb_next() per transaction
> > > increases. After this change, the time to find an ID number appears
> > > constant. (Technically it is not constant-time as both insertion and
> > > removal scan the entire bitmap. However, quick napkin math shows that
> > > scanning the entire bitmap with N=100k takes ~1.5µs, which is neglible
> > > in a benchmark where the rountrip latency is 100µs.)
> > > 
> > > I've included a comparison to the C driver, which uses the same bitmap
> > > algorithm as this patch since commit 15d9da3f818c ("binder: use bitmap
> > > for faster descriptor lookup").
> > 
> > Thanks for the solid numbers!
> > 
> > > This currently checks if the bitmap should be shrunk after every
> > > removal. One potential future change is introducing a shrinker to make
> > > this operation O(1), but based on the benchmark above this does not seem
> > > required at this time.
> > > 
> > > Reviewed-by: Burak Emir <bqe@google.com>
> > > Acked-by: Carlos Llamas <cmllamas@google.com>
> > > Signed-off-by: Alice Ryhl <aliceryhl@google.com>
> > > ---
> > >  drivers/android/binder/process.rs | 64 ++++++++++++++++++++++++++++-----------
> > >  1 file changed, 47 insertions(+), 17 deletions(-)
> > > 
> > > diff --git a/drivers/android/binder/process.rs b/drivers/android/binder/process.rs
> > > index f13a747e784c84a0fb09cbf47442712106eba07c..9264961fd92b33c07fcd5353740cc0b1ec978afd 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,33 @@ 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();
> > > +                        kernel::warn_on!(true);
> > > +                        return Err(EINVAL);
> > 
> > EINVAL means that user provides a wrong parameter. Here's a data
> > corruption. Maybe EFAULT?
> 
> Hmm ... EFAULT is used when the user passes a dangling pointer that
> copy_from_user() refuses to use. I would like to avoid confusion with
> that as well. Is there a third option?
> 
> > > +                    }
> > > +                }
> > > +            }
> > > +
> > > +            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);
> > 
> > This continues puzzling me. Refs_lock protects refs, and the spec
> > says:
> > 
> >     a reference’s scope starts from where it is introduced and
> >     continues through the last time that reference is used.
> > 
> > https://doc.rust-lang.org/book/ch04-02-references-and-borrowing.html
> > 
> > The last usage of refs is at .grow_request() line, because later it's
> > reused with the new value. 
> > 
> > If my reading of the spec is correct, after dropping the refs_lock,
> > you may get rescheduled, and another thread may follow the same path.
> > Because refs_lock is dropped explicitly and refs - implicitly, the
> > concurrent thread can grab both and follow with resizing the id map.
> > 
> > When your first thread will get back, you'll end up resizing the
> > already resized map.
> > 
> > I asked your AI, and it says that this race is indeed possible for
> > exactly that reason. But it doesn't break memory safety, so the
> > compiler is happy about it...
> 
> You're right that since we release the mutex, someone else may have
> resized the map in the meantime. That's why we implemented grow() to do
> nothing if it was already resized:
> 
> 	pub fn grow(&mut self, mut resizer: PoolResizer) {
> 	    // Between request to grow that led to allocation of `resizer` and now,
> 	    // another thread may have already grown the capacity.
> 	    // In this case, do nothing, drop `resizer` and move on.
> 	    if resizer.new.len() <= self.capacity() {
> 	        return;
> 	    }
> 	
> 	    resizer.new.copy_and_extend(&self.map);
> 	    self.map = resizer.new;
> 	}

OK, I see...

I expected that you'll switch the pool state to 'growing' before
dropping the ref_lock. This way, the concurrent thread would be able
to go straight to the new iteration.

Something like:
        
        if let Some(res) = refs.handle_is_present.find_unused_id(start) {
                ...
        }

        if refs.is_growing() {
                drop(refs_lock);
                continue;
        }
        let grow_request = refs.handle_is_present.grow_request().ok_or(ENOMEM)?;
        refs.set_growing()
        drop(refs_lock);
        let resizer = grow_request.realloc(GFP_KERNEL)?;
        ...

Your approach also works, assuming you're OK with a useless alloc/free
bitmaps in the case of collision.

So, I can take this series as is, or I can wait for v7 if you prefer.

Please advise.

Thanks,
Yury

Re: [PATCH v6 6/6] rust_binder: use bitmap for allocation of handles

[Alice Ryhl]

On Wed, Nov 26, 2025 at 10:31:03AM -0500, Yury Norov wrote:
> On Wed, Nov 26, 2025 at 08:35:55AM +0000, Alice Ryhl wrote:
> > On Tue, Nov 25, 2025 at 09:26:46PM -0500, Yury Norov wrote:
> > > On Tue, Nov 25, 2025 at 01:59:42PM +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.
> > > > 
> > > > For a benchmark, please see the below numbers that were obtained from
> > > > modifying binderThroughputTest to send a node with each transaction and
> > > > stashing it in the server. This results in the number of nodes
> > > > increasing by one for every transaction sent. I got the following table
> > > > of roundtrip latencies (in µs):
> > > > 
> > > > Transaction Range │ Baseline (Rust) │ Bitmap (Rust) │ Comparison (C)
> > > > 0 - 10,000        │          176.88 │         92.93 │          99.41
> > > > 10,000 - 20,000   │          437.37 │         87.74 │          98.55
> > > > 20,000 - 30,000   │          677.49 │         76.24 │          96.37
> > > > 30,000 - 40,000   │          901.76 │         83.39 │          96.73
> > > > 40,000 - 50,000   │         1126.62 │        100.44 │          94.57
> > > > 50,000 - 60,000   │         1288.98 │         94.38 │          96.64
> > > > 60,000 - 70,000   │         1588.74 │         88.27 │          96.36
> > > > 70,000 - 80,000   │         1812.97 │         93.97 │          91.24
> > > > 80,000 - 90,000   │         2062.95 │         92.22 │         102.01
> > > > 90,000 - 100,000  │         2330.03 │         97.18 │         100.31
> > > > 
> > > > It should be clear that the current Rust code becomes linearly slower
> > > > per insertion as the number of calls to rb_next() per transaction
> > > > increases. After this change, the time to find an ID number appears
> > > > constant. (Technically it is not constant-time as both insertion and
> > > > removal scan the entire bitmap. However, quick napkin math shows that
> > > > scanning the entire bitmap with N=100k takes ~1.5µs, which is neglible
> > > > in a benchmark where the rountrip latency is 100µs.)
> > > > 
> > > > I've included a comparison to the C driver, which uses the same bitmap
> > > > algorithm as this patch since commit 15d9da3f818c ("binder: use bitmap
> > > > for faster descriptor lookup").
> > > 
> > > Thanks for the solid numbers!
> > > 
> > > > This currently checks if the bitmap should be shrunk after every
> > > > removal. One potential future change is introducing a shrinker to make
> > > > this operation O(1), but based on the benchmark above this does not seem
> > > > required at this time.
> > > > 
> > > > Reviewed-by: Burak Emir <bqe@google.com>
> > > > Acked-by: Carlos Llamas <cmllamas@google.com>
> > > > Signed-off-by: Alice Ryhl <aliceryhl@google.com>
> > > > ---
> > > >  drivers/android/binder/process.rs | 64 ++++++++++++++++++++++++++++-----------
> > > >  1 file changed, 47 insertions(+), 17 deletions(-)
> > > > 
> > > > diff --git a/drivers/android/binder/process.rs b/drivers/android/binder/process.rs
> > > > index f13a747e784c84a0fb09cbf47442712106eba07c..9264961fd92b33c07fcd5353740cc0b1ec978afd 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,33 @@ 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();
> > > > +                        kernel::warn_on!(true);
> > > > +                        return Err(EINVAL);
> > > 
> > > EINVAL means that user provides a wrong parameter. Here's a data
> > > corruption. Maybe EFAULT?
> > 
> > Hmm ... EFAULT is used when the user passes a dangling pointer that
> > copy_from_user() refuses to use. I would like to avoid confusion with
> > that as well. Is there a third option?
> > 
> > > > +                    }
> > > > +                }
> > > > +            }
> > > > +
> > > > +            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);
> > > 
> > > This continues puzzling me. Refs_lock protects refs, and the spec
> > > says:
> > > 
> > >     a reference’s scope starts from where it is introduced and
> > >     continues through the last time that reference is used.
> > > 
> > > https://doc.rust-lang.org/book/ch04-02-references-and-borrowing.html
> > > 
> > > The last usage of refs is at .grow_request() line, because later it's
> > > reused with the new value. 
> > > 
> > > If my reading of the spec is correct, after dropping the refs_lock,
> > > you may get rescheduled, and another thread may follow the same path.
> > > Because refs_lock is dropped explicitly and refs - implicitly, the
> > > concurrent thread can grab both and follow with resizing the id map.
> > > 
> > > When your first thread will get back, you'll end up resizing the
> > > already resized map.
> > > 
> > > I asked your AI, and it says that this race is indeed possible for
> > > exactly that reason. But it doesn't break memory safety, so the
> > > compiler is happy about it...
> > 
> > You're right that since we release the mutex, someone else may have
> > resized the map in the meantime. That's why we implemented grow() to do
> > nothing if it was already resized:
> > 
> > 	pub fn grow(&mut self, mut resizer: PoolResizer) {
> > 	    // Between request to grow that led to allocation of `resizer` and now,
> > 	    // another thread may have already grown the capacity.
> > 	    // In this case, do nothing, drop `resizer` and move on.
> > 	    if resizer.new.len() <= self.capacity() {
> > 	        return;
> > 	    }
> > 	
> > 	    resizer.new.copy_and_extend(&self.map);
> > 	    self.map = resizer.new;
> > 	}
> 
> OK, I see...
> 
> I expected that you'll switch the pool state to 'growing' before
> dropping the ref_lock. This way, the concurrent thread would be able
> to go straight to the new iteration.
> 
> Something like:
>         
>         if let Some(res) = refs.handle_is_present.find_unused_id(start) {
>                 ...
>         }
> 
>         if refs.is_growing() {
>                 drop(refs_lock);
>                 continue;
>         }
>         let grow_request = refs.handle_is_present.grow_request().ok_or(ENOMEM)?;
>         refs.set_growing()
>         drop(refs_lock);
>         let resizer = grow_request.realloc(GFP_KERNEL)?;
>         ...
> 
> Your approach also works, assuming you're OK with a useless alloc/free
> bitmaps in the case of collision.

Hmm, having the extra ones just repeatedly lock/unlock also isn't great.
I guess one alternate option could be to have a separate mutex that you
take while allocating, but ehh I think the current logic is fine.

> So, I can take this series as is, or I can wait for v7 if you prefer.
> 
> Please advise.

Sure, go ahead! And thanks for the reviews!

Alice

Re: [PATCH v6 6/6] rust_binder: use bitmap for allocation of handles

[Yury Norov]

On Wed, Nov 26, 2025 at 03:56:17PM +0000, Alice Ryhl wrote:
> On Wed, Nov 26, 2025 at 10:31:03AM -0500, Yury Norov wrote:
> > On Wed, Nov 26, 2025 at 08:35:55AM +0000, Alice Ryhl wrote:
> > > On Tue, Nov 25, 2025 at 09:26:46PM -0500, Yury Norov wrote:
> > > > On Tue, Nov 25, 2025 at 01:59:42PM +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.
> > > > > 
> > > > > For a benchmark, please see the below numbers that were obtained from
> > > > > modifying binderThroughputTest to send a node with each transaction and
> > > > > stashing it in the server. This results in the number of nodes
> > > > > increasing by one for every transaction sent. I got the following table
> > > > > of roundtrip latencies (in µs):
> > > > > 
> > > > > Transaction Range │ Baseline (Rust) │ Bitmap (Rust) │ Comparison (C)
> > > > > 0 - 10,000        │          176.88 │         92.93 │          99.41
> > > > > 10,000 - 20,000   │          437.37 │         87.74 │          98.55
> > > > > 20,000 - 30,000   │          677.49 │         76.24 │          96.37
> > > > > 30,000 - 40,000   │          901.76 │         83.39 │          96.73
> > > > > 40,000 - 50,000   │         1126.62 │        100.44 │          94.57
> > > > > 50,000 - 60,000   │         1288.98 │         94.38 │          96.64
> > > > > 60,000 - 70,000   │         1588.74 │         88.27 │          96.36
> > > > > 70,000 - 80,000   │         1812.97 │         93.97 │          91.24
> > > > > 80,000 - 90,000   │         2062.95 │         92.22 │         102.01
> > > > > 90,000 - 100,000  │         2330.03 │         97.18 │         100.31
> > > > > 
> > > > > It should be clear that the current Rust code becomes linearly slower
> > > > > per insertion as the number of calls to rb_next() per transaction
> > > > > increases. After this change, the time to find an ID number appears
> > > > > constant. (Technically it is not constant-time as both insertion and
> > > > > removal scan the entire bitmap. However, quick napkin math shows that
> > > > > scanning the entire bitmap with N=100k takes ~1.5µs, which is neglible
> > > > > in a benchmark where the rountrip latency is 100µs.)
> > > > > 
> > > > > I've included a comparison to the C driver, which uses the same bitmap
> > > > > algorithm as this patch since commit 15d9da3f818c ("binder: use bitmap
> > > > > for faster descriptor lookup").
> > > > 
> > > > Thanks for the solid numbers!
> > > > 
> > > > > This currently checks if the bitmap should be shrunk after every
> > > > > removal. One potential future change is introducing a shrinker to make
> > > > > this operation O(1), but based on the benchmark above this does not seem
> > > > > required at this time.
> > > > > 
> > > > > Reviewed-by: Burak Emir <bqe@google.com>
> > > > > Acked-by: Carlos Llamas <cmllamas@google.com>
> > > > > Signed-off-by: Alice Ryhl <aliceryhl@google.com>
> > > > > ---
> > > > >  drivers/android/binder/process.rs | 64 ++++++++++++++++++++++++++++-----------
> > > > >  1 file changed, 47 insertions(+), 17 deletions(-)
> > > > > 
> > > > > diff --git a/drivers/android/binder/process.rs b/drivers/android/binder/process.rs
> > > > > index f13a747e784c84a0fb09cbf47442712106eba07c..9264961fd92b33c07fcd5353740cc0b1ec978afd 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,33 @@ 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();
> > > > > +                        kernel::warn_on!(true);
> > > > > +                        return Err(EINVAL);
> > > > 
> > > > EINVAL means that user provides a wrong parameter. Here's a data
> > > > corruption. Maybe EFAULT?
> > > 
> > > Hmm ... EFAULT is used when the user passes a dangling pointer that
> > > copy_from_user() refuses to use. I would like to avoid confusion with
> > > that as well. Is there a third option?
> > > 
> > > > > +                    }
> > > > > +                }
> > > > > +            }
> > > > > +
> > > > > +            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);
> > > > 
> > > > This continues puzzling me. Refs_lock protects refs, and the spec
> > > > says:
> > > > 
> > > >     a reference’s scope starts from where it is introduced and
> > > >     continues through the last time that reference is used.
> > > > 
> > > > https://doc.rust-lang.org/book/ch04-02-references-and-borrowing.html
> > > > 
> > > > The last usage of refs is at .grow_request() line, because later it's
> > > > reused with the new value. 
> > > > 
> > > > If my reading of the spec is correct, after dropping the refs_lock,
> > > > you may get rescheduled, and another thread may follow the same path.
> > > > Because refs_lock is dropped explicitly and refs - implicitly, the
> > > > concurrent thread can grab both and follow with resizing the id map.
> > > > 
> > > > When your first thread will get back, you'll end up resizing the
> > > > already resized map.
> > > > 
> > > > I asked your AI, and it says that this race is indeed possible for
> > > > exactly that reason. But it doesn't break memory safety, so the
> > > > compiler is happy about it...
> > > 
> > > You're right that since we release the mutex, someone else may have
> > > resized the map in the meantime. That's why we implemented grow() to do
> > > nothing if it was already resized:
> > > 
> > > 	pub fn grow(&mut self, mut resizer: PoolResizer) {
> > > 	    // Between request to grow that led to allocation of `resizer` and now,
> > > 	    // another thread may have already grown the capacity.
> > > 	    // In this case, do nothing, drop `resizer` and move on.
> > > 	    if resizer.new.len() <= self.capacity() {
> > > 	        return;
> > > 	    }
> > > 	
> > > 	    resizer.new.copy_and_extend(&self.map);
> > > 	    self.map = resizer.new;
> > > 	}
> > 
> > OK, I see...
> > 
> > I expected that you'll switch the pool state to 'growing' before
> > dropping the ref_lock. This way, the concurrent thread would be able
> > to go straight to the new iteration.
> > 
> > Something like:
> >         
> >         if let Some(res) = refs.handle_is_present.find_unused_id(start) {
> >                 ...
> >         }
> > 
> >         if refs.is_growing() {
> >                 drop(refs_lock);
> >                 continue;
> >         }
> >         let grow_request = refs.handle_is_present.grow_request().ok_or(ENOMEM)?;
> >         refs.set_growing()
> >         drop(refs_lock);
> >         let resizer = grow_request.realloc(GFP_KERNEL)?;
> >         ...
> > 
> > Your approach also works, assuming you're OK with a useless alloc/free
> > bitmaps in the case of collision.
> 
> Hmm, having the extra ones just repeatedly lock/unlock also isn't great.
> I guess one alternate option could be to have a separate mutex that you
> take while allocating, but ehh I think the current logic is fine.

Not sure I understand... In case you've found nothing and need to
grow, you anyways have to lock and unlock, at least to allocate a
bigger bitmap.

But this doesn't look critical to me because probability of such event
decreases exponentially as the ID pool grows. So either approach works.
 
> > So, I can take this series as is, or I can wait for v7 if you prefer.
> > 
> > Please advise.
> 
> Sure, go ahead! And thanks for the reviews!

OK, will do.

Thanks,
Yury

Re: [PATCH v6 6/6] rust_binder: use bitmap for allocation of handles

[Alice Ryhl]

On Wed, Nov 26, 2025 at 5:13 PM Yury Norov <yury.norov@gmail.com> wrote:
>
> On Wed, Nov 26, 2025 at 03:56:17PM +0000, Alice Ryhl wrote:
> > On Wed, Nov 26, 2025 at 10:31:03AM -0500, Yury Norov wrote:
> > > On Wed, Nov 26, 2025 at 08:35:55AM +0000, Alice Ryhl wrote:
> > > > On Tue, Nov 25, 2025 at 09:26:46PM -0500, Yury Norov wrote:
> > > > > On Tue, Nov 25, 2025 at 01:59:42PM +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.
> > > > > >
> > > > > > For a benchmark, please see the below numbers that were obtained from
> > > > > > modifying binderThroughputTest to send a node with each transaction and
> > > > > > stashing it in the server. This results in the number of nodes
> > > > > > increasing by one for every transaction sent. I got the following table
> > > > > > of roundtrip latencies (in µs):
> > > > > >
> > > > > > Transaction Range │ Baseline (Rust) │ Bitmap (Rust) │ Comparison (C)
> > > > > > 0 - 10,000        │          176.88 │         92.93 │          99.41
> > > > > > 10,000 - 20,000   │          437.37 │         87.74 │          98.55
> > > > > > 20,000 - 30,000   │          677.49 │         76.24 │          96.37
> > > > > > 30,000 - 40,000   │          901.76 │         83.39 │          96.73
> > > > > > 40,000 - 50,000   │         1126.62 │        100.44 │          94.57
> > > > > > 50,000 - 60,000   │         1288.98 │         94.38 │          96.64
> > > > > > 60,000 - 70,000   │         1588.74 │         88.27 │          96.36
> > > > > > 70,000 - 80,000   │         1812.97 │         93.97 │          91.24
> > > > > > 80,000 - 90,000   │         2062.95 │         92.22 │         102.01
> > > > > > 90,000 - 100,000  │         2330.03 │         97.18 │         100.31
> > > > > >
> > > > > > It should be clear that the current Rust code becomes linearly slower
> > > > > > per insertion as the number of calls to rb_next() per transaction
> > > > > > increases. After this change, the time to find an ID number appears
> > > > > > constant. (Technically it is not constant-time as both insertion and
> > > > > > removal scan the entire bitmap. However, quick napkin math shows that
> > > > > > scanning the entire bitmap with N=100k takes ~1.5µs, which is neglible
> > > > > > in a benchmark where the rountrip latency is 100µs.)
> > > > > >
> > > > > > I've included a comparison to the C driver, which uses the same bitmap
> > > > > > algorithm as this patch since commit 15d9da3f818c ("binder: use bitmap
> > > > > > for faster descriptor lookup").
> > > > >
> > > > > Thanks for the solid numbers!
> > > > >
> > > > > > This currently checks if the bitmap should be shrunk after every
> > > > > > removal. One potential future change is introducing a shrinker to make
> > > > > > this operation O(1), but based on the benchmark above this does not seem
> > > > > > required at this time.
> > > > > >
> > > > > > Reviewed-by: Burak Emir <bqe@google.com>
> > > > > > Acked-by: Carlos Llamas <cmllamas@google.com>
> > > > > > Signed-off-by: Alice Ryhl <aliceryhl@google.com>
> > > > > > ---
> > > > > >  drivers/android/binder/process.rs | 64 ++++++++++++++++++++++++++++-----------
> > > > > >  1 file changed, 47 insertions(+), 17 deletions(-)
> > > > > >
> > > > > > diff --git a/drivers/android/binder/process.rs b/drivers/android/binder/process.rs
> > > > > > index f13a747e784c84a0fb09cbf47442712106eba07c..9264961fd92b33c07fcd5353740cc0b1ec978afd 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,33 @@ 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();
> > > > > > +                        kernel::warn_on!(true);
> > > > > > +                        return Err(EINVAL);
> > > > >
> > > > > EINVAL means that user provides a wrong parameter. Here's a data
> > > > > corruption. Maybe EFAULT?
> > > >
> > > > Hmm ... EFAULT is used when the user passes a dangling pointer that
> > > > copy_from_user() refuses to use. I would like to avoid confusion with
> > > > that as well. Is there a third option?
> > > >
> > > > > > +                    }
> > > > > > +                }
> > > > > > +            }
> > > > > > +
> > > > > > +            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);
> > > > >
> > > > > This continues puzzling me. Refs_lock protects refs, and the spec
> > > > > says:
> > > > >
> > > > >     a reference’s scope starts from where it is introduced and
> > > > >     continues through the last time that reference is used.
> > > > >
> > > > > https://doc.rust-lang.org/book/ch04-02-references-and-borrowing.html
> > > > >
> > > > > The last usage of refs is at .grow_request() line, because later it's
> > > > > reused with the new value.
> > > > >
> > > > > If my reading of the spec is correct, after dropping the refs_lock,
> > > > > you may get rescheduled, and another thread may follow the same path.
> > > > > Because refs_lock is dropped explicitly and refs - implicitly, the
> > > > > concurrent thread can grab both and follow with resizing the id map.
> > > > >
> > > > > When your first thread will get back, you'll end up resizing the
> > > > > already resized map.
> > > > >
> > > > > I asked your AI, and it says that this race is indeed possible for
> > > > > exactly that reason. But it doesn't break memory safety, so the
> > > > > compiler is happy about it...
> > > >
> > > > You're right that since we release the mutex, someone else may have
> > > > resized the map in the meantime. That's why we implemented grow() to do
> > > > nothing if it was already resized:
> > > >
> > > >   pub fn grow(&mut self, mut resizer: PoolResizer) {
> > > >       // Between request to grow that led to allocation of `resizer` and now,
> > > >       // another thread may have already grown the capacity.
> > > >       // In this case, do nothing, drop `resizer` and move on.
> > > >       if resizer.new.len() <= self.capacity() {
> > > >           return;
> > > >       }
> > > >
> > > >       resizer.new.copy_and_extend(&self.map);
> > > >       self.map = resizer.new;
> > > >   }
> > >
> > > OK, I see...
> > >
> > > I expected that you'll switch the pool state to 'growing' before
> > > dropping the ref_lock. This way, the concurrent thread would be able
> > > to go straight to the new iteration.
> > >
> > > Something like:
> > >
> > >         if let Some(res) = refs.handle_is_present.find_unused_id(start) {
> > >                 ...
> > >         }
> > >
> > >         if refs.is_growing() {
> > >                 drop(refs_lock);
> > >                 continue;
> > >         }
> > >         let grow_request = refs.handle_is_present.grow_request().ok_or(ENOMEM)?;
> > >         refs.set_growing()
> > >         drop(refs_lock);
> > >         let resizer = grow_request.realloc(GFP_KERNEL)?;
> > >         ...
> > >
> > > Your approach also works, assuming you're OK with a useless alloc/free
> > > bitmaps in the case of collision.
> >
> > Hmm, having the extra ones just repeatedly lock/unlock also isn't great.
> > I guess one alternate option could be to have a separate mutex that you
> > take while allocating, but ehh I think the current logic is fine.
>
> Not sure I understand... In case you've found nothing and need to
> grow, you anyways have to lock and unlock, at least to allocate a
> bigger bitmap.

I'm mostly concerned that it's going to unlock/lock many many many
times while the other thread is busy allocating.

Alice

> But this doesn't look critical to me because probability of such event
> decreases exponentially as the ID pool grows. So either approach works.
>
> > > So, I can take this series as is, or I can wait for v7 if you prefer.
> > >
> > > Please advise.
> >
> > Sure, go ahead! And thanks for the reviews!
>
> OK, will do.
>
> Thanks,
> Yury