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-googOn 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
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
© 2016 - 2026 Red Hat, Inc.