[PATCH 0/2] Use Rust Bitmap from Rust Binder driver

[PATCH 0/2] 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>
---
Alice Ryhl (2):
      rust: bitmap: add MAX_LEN and NO_ALLOC_MAX_LEN constants
      rust_binder: use bitmap for allocation of handles

 drivers/android/binder/process.rs | 110 +++++++++++++++++++++++++++++++-------
 rust/kernel/bitmap.rs             |  16 ++++--
 2 files changed, 101 insertions(+), 25 deletions(-)
---
base-commit: 211ddde0823f1442e4ad052a2f30f050145ccada
change-id: 20251007-binder-bitmap-5aa0d966fb1f

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

[PATCH 1/2] 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.

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

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

-- 
2.51.0.915.g61a8936c21-goog

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

[Alice Ryhl]

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

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

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

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

diff --git a/drivers/android/binder/process.rs b/drivers/android/binder/process.rs
index f13a747e784c84a0fb09cbf47442712106eba07c..357ba1b577c73ad3f2b525a8573424420577e92d 100644
--- a/drivers/android/binder/process.rs
+++ b/drivers/android/binder/process.rs
@@ -16,6 +16,7 @@
 
 use kernel::{
     bindings,
+    bitmap::BitmapVec,
     cred::Credential,
     error::Error,
     fs::file::{self, File},
@@ -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_present: BitmapVec,
     /// 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>,
@@ -378,13 +381,56 @@ struct ProcessNodeRefs {
 }
 
 impl ProcessNodeRefs {
-    fn new() -> Self {
-        Self {
+    fn new() -> Result<Self> {
+        Ok(Self {
             by_handle: RBTree::new(),
+            handle_present: BitmapVec::new(BitmapVec::NO_ALLOC_MAX_LEN, GFP_KERNEL)?,
             by_node: RBTree::new(),
             freeze_listeners: RBTree::new(),
+        })
+    }
+
+    fn bitmap_shrink_len(&self) -> Option<usize> {
+        let nbits = self.handle_present.len();
+
+        if nbits <= BitmapVec::NO_ALLOC_MAX_LEN {
+            return None;
+        }
+
+        match self.handle_present.last_bit() {
+            Some(bit) if bit < nbits >> 2 => Some(nbits >> 1),
+            None => Some(BitmapVec::NO_ALLOC_MAX_LEN),
+            _ => None,
+        }
+    }
+
+    fn bitmap_grow_len(&self) -> Option<usize> {
+        let new_len = self
+            .handle_present
+            .len()
+            .checked_mul(2)
+            .unwrap_or(BitmapVec::MAX_LEN)
+            .min(BitmapVec::MAX_LEN);
+
+        if new_len > self.handle_present.len() {
+            Some(new_len)
+        } else {
+            None
+        }
+    }
+
+    fn try_shrink_bitmap(&mut self, new_map: BitmapVec) {
+        if let Some(target_len) = self.bitmap_shrink_len() {
+            if new_map.len() == target_len {
+                self.replace_bitmap(new_map);
+            }
         }
     }
+
+    fn replace_bitmap(&mut self, mut new_map: BitmapVec) {
+        new_map.copy_and_extend(&self.handle_present);
+        self.handle_present = new_map;
+    }
 }
 
 /// A process using binder.
@@ -471,7 +517,7 @@ fn new(ctx: Arc<Context>, cred: ARef<Credential>) -> Result<Arc<Self>> {
                 cred,
                 inner <- kernel::new_spinlock!(ProcessInner::new(), "Process::inner"),
                 pages <- ShrinkablePageRange::new(&super::BINDER_SHRINKER),
-                node_refs <- kernel::new_mutex!(ProcessNodeRefs::new(), "Process::node_refs"),
+                node_refs <- kernel::new_mutex!(ProcessNodeRefs::new()?, "Process::node_refs"),
                 freeze_wait <- kernel::new_condvar!("Process::freeze_wait"),
                 task: current.group_leader().into(),
                 defer_work <- kernel::new_work!("Process::defer_work"),
@@ -775,7 +821,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 +840,34 @@ 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 (handle, by_handle_slot) = loop {
+            // ID 0 may only be used by the manager.
+            let start = if is_manager { 0 } else { 1 };
+
+            if let Some(handle) = refs.handle_present.next_zero_bit(start) {
+                let handle_u32 = u32::try_from(handle).map_err(|_| ENOMEM)?;
+                match refs.by_handle.entry(handle_u32) {
+                    rbtree::Entry::Vacant(entry) => break (handle_u32, entry),
+                    rbtree::Entry::Occupied(_) => {
+                        pr_err!("Detected mismatch between handle_present and by_handle");
+                        refs.handle_present.set_bit(handle);
+                        continue;
+                    }
+                }
+            }
+
+            let new_len = refs.bitmap_grow_len().ok_or(ENOMEM)?;
+            drop(refs_lock);
+            let new_bitmap = BitmapVec::new(new_len, GFP_KERNEL)?;
+            refs_lock = self.node_refs.lock();
+            refs = &mut *refs_lock;
+            if refs.handle_present.len() < new_len {
+                refs.replace_bitmap(new_bitmap);
+            }
+        };
 
         // 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 +877,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 +900,9 @@ 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);
+        Ok(handle)
     }
 
     pub(crate) fn get_transaction_node(&self, handle: u32) -> BinderResult<NodeRef> {
@@ -905,6 +967,14 @@ 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_present.clear_bit(handle as usize);
+
+                if let Some(shrink_len) = refs.bitmap_shrink_len() {
+                    drop(refs);
+                    let new_bitmap = BitmapVec::new(shrink_len, GFP_KERNEL)?;
+                    refs = self.node_refs.lock();
+                    refs.try_shrink_bitmap(new_bitmap);
+                }
             }
         } else {
             // All refs are cleared in process exit, so this warning is expected in that case.

-- 
2.51.0.915.g61a8936c21-goog

Re: [PATCH 1/2] rust: bitmap: add MAX_LEN and NO_ALLOC_MAX_LEN constants

[Burak Emir]

On Mon, Oct 20, 2025 at 3:33 PM Alice Ryhl <aliceryhl@google.com> wrote:
>
> To avoid hard-coding these values in drivers, define constants for them
> that drivers can reference.
>
> Signed-off-by: Alice Ryhl <aliceryhl@google.com>
Reviewed-by: Burak Emir <bqe@google.com>

Re: [PATCH 1/2] rust: bitmap: add MAX_LEN and NO_ALLOC_MAX_LEN constants

[Danilo Krummrich]

On 10/20/25 3:33 PM, Alice Ryhl wrote:
> To avoid hard-coding these values in drivers, define constants for them
> that drivers can reference.
> 
> Signed-off-by: Alice Ryhl <aliceryhl@google.com>

Yes, please! :)

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

> @@ -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();

Can we also get rid of this please? :)

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

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

[Burak Emir]

On Mon, Oct 20, 2025 at 3:33 PM Alice Ryhl <aliceryhl@google.com> wrote:
>
> To find an unused Binder handle, Rust Binder currently iterates the
> red/black tree from the beginning until it finds a gap in the keys. This
> is extremely slow.
>
> To improve the performance, add a bitmap that keeps track of which
> indices are actually in use. This allows us to quickly find an unused
> key in the red/black tree.
>
> This logic matches the approach used by C Binder. It was chosen
> partially because it's the most memory efficient solution.
>
> Signed-off-by: Alice Ryhl <aliceryhl@google.com>
> ---
>  drivers/android/binder/process.rs | 110 +++++++++++++++++++++++++++++++-------
>  1 file changed, 90 insertions(+), 20 deletions(-)
>
> diff --git a/drivers/android/binder/process.rs b/drivers/android/binder/process.rs
> index f13a747e784c84a0fb09cbf47442712106eba07c..357ba1b577c73ad3f2b525a8573424420577e92d 100644
> --- a/drivers/android/binder/process.rs
> +++ b/drivers/android/binder/process.rs
> @@ -16,6 +16,7 @@
>
>  use kernel::{
>      bindings,
> +    bitmap::BitmapVec,
>      cred::Credential,
>      error::Error,
>      fs::file::{self, File},
> @@ -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_present: BitmapVec,

Are you going to delete rust/kernel/id_pool.rs, too?

I have no opinion on whether having an abstraction vs inlining the
functionality is worth it. I mean just in order to avoid id_pool.rs
hanging around as dead code.

Cheers,
Burak

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

[Alice Ryhl]

On Mon, Oct 20, 2025 at 05:06:26PM +0200, Burak Emir wrote:
> On Mon, Oct 20, 2025 at 3:33 PM Alice Ryhl <aliceryhl@google.com> wrote:
> >
> > To find an unused Binder handle, Rust Binder currently iterates the
> > red/black tree from the beginning until it finds a gap in the keys. This
> > is extremely slow.
> >
> > To improve the performance, add a bitmap that keeps track of which
> > indices are actually in use. This allows us to quickly find an unused
> > key in the red/black tree.
> >
> > This logic matches the approach used by C Binder. It was chosen
> > partially because it's the most memory efficient solution.
> >
> > Signed-off-by: Alice Ryhl <aliceryhl@google.com>
> > ---
> >  drivers/android/binder/process.rs | 110 +++++++++++++++++++++++++++++++-------
> >  1 file changed, 90 insertions(+), 20 deletions(-)
> >
> > diff --git a/drivers/android/binder/process.rs b/drivers/android/binder/process.rs
> > index f13a747e784c84a0fb09cbf47442712106eba07c..357ba1b577c73ad3f2b525a8573424420577e92d 100644
> > --- a/drivers/android/binder/process.rs
> > +++ b/drivers/android/binder/process.rs
> > @@ -16,6 +16,7 @@
> >
> >  use kernel::{
> >      bindings,
> > +    bitmap::BitmapVec,
> >      cred::Credential,
> >      error::Error,
> >      fs::file::{self, File},
> > @@ -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_present: BitmapVec,
> 
> Are you going to delete rust/kernel/id_pool.rs, too?
> 
> I have no opinion on whether having an abstraction vs inlining the
> functionality is worth it. I mean just in order to avoid id_pool.rs
> hanging around as dead code.

No I should be using it in Binder. I forgot to update the code to use
it.

Alice