To find an unused Binder handle, Rust Binder currently iterates the
red/black tree from the beginning until it finds a gap in the keys. This
is extremely slow.
To improve the performance, add a bitmap that keeps track of which
indices are actually in use. This allows us to quickly find an unused
key in the red/black tree.
This logic matches the approach used by C Binder. It was chosen
partially because it's the most memory efficient solution.
Reviewed-by: Burak Emir <bqe@google.com>
Acked-by: Carlos Llamas <cmllamas@google.com>
Signed-off-by: Alice Ryhl <aliceryhl@google.com>
---
drivers/android/binder/process.rs | 63 ++++++++++++++++++++++++++++-----------
1 file changed, 46 insertions(+), 17 deletions(-)
diff --git a/drivers/android/binder/process.rs b/drivers/android/binder/process.rs
index f13a747e784c84a0fb09cbf47442712106eba07c..933b0f737b38ffac536b19c9330dfc63ffc72f2b 100644
--- a/drivers/android/binder/process.rs
+++ b/drivers/android/binder/process.rs
@@ -19,6 +19,7 @@
cred::Credential,
error::Error,
fs::file::{self, File},
+ id_pool::IdPool,
list::{List, ListArc, ListArcField, ListLinks},
mm,
prelude::*,
@@ -367,6 +368,8 @@ impl ListItem<{Self::LIST_NODE}> for NodeRefInfo {
struct ProcessNodeRefs {
/// Used to look up nodes using the 32-bit id that this process knows it by.
by_handle: RBTree<u32, ListArc<NodeRefInfo, { NodeRefInfo::LIST_PROC }>>,
+ /// Used to quickly find unused ids in `by_handle`.
+ handle_is_present: IdPool,
/// Used to look up nodes without knowing their local 32-bit id. The usize is the address of
/// the underlying `Node` struct as returned by `Node::global_id`.
by_node: RBTree<usize, u32>,
@@ -381,6 +384,7 @@ impl ProcessNodeRefs {
fn new() -> Self {
Self {
by_handle: RBTree::new(),
+ handle_is_present: IdPool::new(),
by_node: RBTree::new(),
freeze_listeners: RBTree::new(),
}
@@ -775,7 +779,7 @@ pub(crate) fn get_node(
pub(crate) fn insert_or_update_handle(
self: ArcBorrow<'_, Process>,
node_ref: NodeRef,
- is_mananger: bool,
+ is_manager: bool,
) -> Result<u32> {
{
let mut refs = self.node_refs.lock();
@@ -794,7 +798,32 @@ pub(crate) fn insert_or_update_handle(
let reserve2 = RBTreeNodeReservation::new(GFP_KERNEL)?;
let info = UniqueArc::new_uninit(GFP_KERNEL)?;
- let mut refs = self.node_refs.lock();
+ let mut refs_lock = self.node_refs.lock();
+ let mut refs = &mut *refs_lock;
+
+ let (unused_id, by_handle_slot) = loop {
+ // ID 0 may only be used by the manager.
+ let start = if is_manager { 0 } else { 1 };
+
+ if let Some(res) = refs.handle_is_present.find_unused_id(start) {
+ match refs.by_handle.entry(res.as_u32()) {
+ rbtree::Entry::Vacant(entry) => break (res, entry),
+ rbtree::Entry::Occupied(_) => {
+ pr_err!("Detected mismatch between handle_is_present and by_handle");
+ res.acquire();
+ continue;
+ }
+ }
+ }
+
+ let grow_request = refs.handle_is_present.grow_request().ok_or(ENOMEM)?;
+ drop(refs_lock);
+ let resizer = grow_request.realloc(GFP_KERNEL)?;
+ refs_lock = self.node_refs.lock();
+ refs = &mut *refs_lock;
+ refs.handle_is_present.grow(resizer);
+ };
+ let handle = unused_id.as_u32();
// Do a lookup again as node may have been inserted before the lock was reacquired.
if let Some(handle_ref) = refs.by_node.get(&node_ref.node.global_id()) {
@@ -804,20 +833,9 @@ pub(crate) fn insert_or_update_handle(
return Ok(handle);
}
- // Find id.
- let mut target: u32 = if is_mananger { 0 } else { 1 };
- for handle in refs.by_handle.keys() {
- if *handle > target {
- break;
- }
- if *handle == target {
- target = target.checked_add(1).ok_or(ENOMEM)?;
- }
- }
-
let gid = node_ref.node.global_id();
let (info_proc, info_node) = {
- let info_init = NodeRefInfo::new(node_ref, target, self.into());
+ let info_init = NodeRefInfo::new(node_ref, handle, self.into());
match info.pin_init_with(info_init) {
Ok(info) => ListArc::pair_from_pin_unique(info),
// error is infallible
@@ -838,9 +856,10 @@ pub(crate) fn insert_or_update_handle(
// `info_node` into the right node's `refs` list.
unsafe { info_proc.node_ref2().node.insert_node_info(info_node) };
- refs.by_node.insert(reserve1.into_node(gid, target));
- refs.by_handle.insert(reserve2.into_node(target, info_proc));
- Ok(target)
+ refs.by_node.insert(reserve1.into_node(gid, handle));
+ by_handle_slot.insert(info_proc, reserve2);
+ unused_id.acquire();
+ Ok(handle)
}
pub(crate) fn get_transaction_node(&self, handle: u32) -> BinderResult<NodeRef> {
@@ -905,6 +924,16 @@ pub(crate) fn update_ref(
let id = info.node_ref().node.global_id();
refs.by_handle.remove(&handle);
refs.by_node.remove(&id);
+ refs.handle_is_present.release_id(handle as usize);
+
+ if let Some(shrink) = refs.handle_is_present.shrink_request() {
+ drop(refs);
+ // This intentionally ignores allocation failures.
+ if let Ok(new_bitmap) = shrink.realloc(GFP_KERNEL) {
+ refs = self.node_refs.lock();
+ refs.handle_is_present.shrink(new_bitmap);
+ }
+ }
}
} else {
// All refs are cleared in process exit, so this warning is expected in that case.
--
2.51.2.1041.gc1ab5b90ca-googOn Wed, Nov 12, 2025 at 12:47:24PM +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.
Can you share performance numbers?
> 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.
That inaccurate. You are adding a new data structure (bitmap), advocating
it with an improvement on search side, and that makes sense.
But now you're saying it's also a more memory efficient approach, which
doesn't sound trivial because the most memory efficient solution is to
bring no new data structures at all.
I guess you meant that bitmap is the most efficient data structure to
index used/unused nodes. If so, can you please rephrase the sentence?
> 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 | 63 ++++++++++++++++++++++++++++-----------
> 1 file changed, 46 insertions(+), 17 deletions(-)
>
> diff --git a/drivers/android/binder/process.rs b/drivers/android/binder/process.rs
> index f13a747e784c84a0fb09cbf47442712106eba07c..933b0f737b38ffac536b19c9330dfc63ffc72f2b 100644
> --- a/drivers/android/binder/process.rs
> +++ b/drivers/android/binder/process.rs
> @@ -19,6 +19,7 @@
> cred::Credential,
> error::Error,
> fs::file::{self, File},
> + id_pool::IdPool,
> list::{List, ListArc, ListArcField, ListLinks},
> mm,
> prelude::*,
> @@ -367,6 +368,8 @@ impl ListItem<{Self::LIST_NODE}> for NodeRefInfo {
> struct ProcessNodeRefs {
> /// Used to look up nodes using the 32-bit id that this process knows it by.
> by_handle: RBTree<u32, ListArc<NodeRefInfo, { NodeRefInfo::LIST_PROC }>>,
> + /// Used to quickly find unused ids in `by_handle`.
> + handle_is_present: IdPool,
> /// Used to look up nodes without knowing their local 32-bit id. The usize is the address of
> /// the underlying `Node` struct as returned by `Node::global_id`.
> by_node: RBTree<usize, u32>,
> @@ -381,6 +384,7 @@ impl ProcessNodeRefs {
> fn new() -> Self {
> Self {
> by_handle: RBTree::new(),
> + handle_is_present: IdPool::new(),
> by_node: RBTree::new(),
> freeze_listeners: RBTree::new(),
> }
> @@ -775,7 +779,7 @@ pub(crate) fn get_node(
> pub(crate) fn insert_or_update_handle(
> self: ArcBorrow<'_, Process>,
> node_ref: NodeRef,
> - is_mananger: bool,
> + is_manager: bool,
> ) -> Result<u32> {
> {
> let mut refs = self.node_refs.lock();
> @@ -794,7 +798,32 @@ pub(crate) fn insert_or_update_handle(
> let reserve2 = RBTreeNodeReservation::new(GFP_KERNEL)?;
> let info = UniqueArc::new_uninit(GFP_KERNEL)?;
>
> - let mut refs = self.node_refs.lock();
> + let mut refs_lock = self.node_refs.lock();
> + let mut refs = &mut *refs_lock;
> +
> + let (unused_id, by_handle_slot) = loop {
> + // ID 0 may only be used by the manager.
> + let start = if is_manager { 0 } else { 1 };
> +
> + if let Some(res) = refs.handle_is_present.find_unused_id(start) {
> + match refs.by_handle.entry(res.as_u32()) {
> + rbtree::Entry::Vacant(entry) => break (res, entry),
> + rbtree::Entry::Occupied(_) => {
> + pr_err!("Detected mismatch between handle_is_present and by_handle");
> + res.acquire();
> + continue;
At this point you've detected mismatch between two linked data
structures. It means that one of them or both are corrupted. To
me it looks fatal, and your pr_err() confirms it. How could you
continue then?
> + }
> + }
> + }
> +
> + 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);
Is it possible to turn this block into a less wordy statement? Maybe a
wrapper function for it? Ideally, the grow request should be handled
transparently in .find_unused_id().
> + };
> + let handle = unused_id.as_u32();
>
> // Do a lookup again as node may have been inserted before the lock was reacquired.
> if let Some(handle_ref) = refs.by_node.get(&node_ref.node.global_id()) {
> @@ -804,20 +833,9 @@ pub(crate) fn insert_or_update_handle(
> return Ok(handle);
> }
>
> - // Find id.
> - let mut target: u32 = if is_mananger { 0 } else { 1 };
> - for handle in refs.by_handle.keys() {
> - if *handle > target {
> - break;
> - }
> - if *handle == target {
> - target = target.checked_add(1).ok_or(ENOMEM)?;
> - }
> - }
> -
> let gid = node_ref.node.global_id();
> let (info_proc, info_node) = {
> - let info_init = NodeRefInfo::new(node_ref, target, self.into());
> + let info_init = NodeRefInfo::new(node_ref, handle, self.into());
> match info.pin_init_with(info_init) {
> Ok(info) => ListArc::pair_from_pin_unique(info),
> // error is infallible
> @@ -838,9 +856,10 @@ pub(crate) fn insert_or_update_handle(
> // `info_node` into the right node's `refs` list.
> unsafe { info_proc.node_ref2().node.insert_node_info(info_node) };
>
> - refs.by_node.insert(reserve1.into_node(gid, target));
> - refs.by_handle.insert(reserve2.into_node(target, info_proc));
> - Ok(target)
> + refs.by_node.insert(reserve1.into_node(gid, handle));
> + by_handle_slot.insert(info_proc, reserve2);
> + unused_id.acquire();
> + Ok(handle)
> }
>
> pub(crate) fn get_transaction_node(&self, handle: u32) -> BinderResult<NodeRef> {
> @@ -905,6 +924,16 @@ pub(crate) fn update_ref(
> let id = info.node_ref().node.global_id();
> refs.by_handle.remove(&handle);
> refs.by_node.remove(&id);
> + refs.handle_is_present.release_id(handle as usize);
> +
> + if let Some(shrink) = refs.handle_is_present.shrink_request() {
This is questionable. Shrinking is usually the very slow path, and we
don't shrink unless we're really close or even inside the OOM condition.
In this case, shrink_request() on average returns false, but it's
O(N), which makes _every_ release_id() O(N), while it should be O(1).
Consider a very realistic case: you're destroying every object, and thus
removing every ID in the associate ID pool, doing it in LIFO order. That
way you will need to call shrink_request() about O(log(N)) times, making
the whole complexity ~O(N*log(N)); and you'll have to make log(N)
realloc()s for nothing. If you release IDs in FIFO order, you don't
call realloc(), but your shrink_request() total complexity will be O(N^2).
Can you compare performance numbers with and without shrinking under a
typical payload? Is there any mechanism to inspect the ID pools at runtime,
like expose via procfs?
Can you make your shrinking logic conditional on some reasonable OOM
heuristics, maybe OOM event driven?
And even without OOM, you can safely skip shrinking if the number of IDs in
use is greater than 1/4 of the capacity, or there's any used ID with
the index greater than the 1/2 capacity.
> + drop(refs);
> + // This intentionally ignores allocation failures.
> + if let Ok(new_bitmap) = shrink.realloc(GFP_KERNEL) {
> + refs = self.node_refs.lock();
> + refs.handle_is_present.shrink(new_bitmap);
> + }
> + }
> }
> } else {
> // All refs are cleared in process exit, so this warning is expected in that case.
>
> --
> 2.51.2.1041.gc1ab5b90ca-goog
On Wed, Nov 12, 2025 at 02:09:19PM -0500, Yury Norov wrote:
> On Wed, Nov 12, 2025 at 12:47:24PM +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.
>
> Can you share performance numbers?
I have not benchmarked it in the Rust driver, but it replaces
potentially thousands of calls to rb_next() with a single call to
find_unused_id(), so I'm feeling good about the performance. And the
equivalent change in the C driver was done because this particular piece
of code was causing contention issues by holding the spinlock for a long
time.
The characteristics of this collection is that there is one per process
using the driver. Most processes have only a few entries in this bitmap,
so the inline representation will apply in most cases. However, there
are a few processes that have a large number of entries in the 4 to
maybe 5 figures range. Those processes are what caused the contention
issue mentioned above.
> > 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.
>
> That inaccurate. You are adding a new data structure (bitmap), advocating
> it with an improvement on search side, and that makes sense.
>
> But now you're saying it's also a more memory efficient approach, which
> doesn't sound trivial because the most memory efficient solution is to
> bring no new data structures at all.
>
> I guess you meant that bitmap is the most efficient data structure to
> index used/unused nodes. If so, can you please rephrase the sentence?
Yes I can rephrase.
Adding more data is of course always less memory efficient. What I meant
is that this is more memory efficient than the competing solution of
using an augmented rbtree that Carlos mentioned here:
https://lore.kernel.org/p/aC1PQ7tmcqMSmbHc@google.com
> > + if let Some(res) = refs.handle_is_present.find_unused_id(start) {
> > + match refs.by_handle.entry(res.as_u32()) {
> > + rbtree::Entry::Vacant(entry) => break (res, entry),
> > + rbtree::Entry::Occupied(_) => {
> > + pr_err!("Detected mismatch between handle_is_present and by_handle");
> > + res.acquire();
> > + continue;
>
> At this point you've detected mismatch between two linked data
> structures. It means that one of them or both are corrupted. To
> me it looks fatal, and your pr_err() confirms it. How could you
> continue then?
Although we should never hit this codepath in real code, I don't think
we need to kill the kernel. We can treat the r/b tree as source of truth
and adjust the bitmap when mismathces are detected.
I could add a kernel warning, though. That shouldn't kill an Android
device.
> > + }
> > + }
> > + }
> > +
> > + 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);
>
> Is it possible to turn this block into a less wordy statement? Maybe a
> wrapper function for it? Ideally, the grow request should be handled
> transparently in .find_unused_id().
I can extract this block into a separate function, but I think it would
be tricky to move the entire logic inside .find_unused_id() because of
the mutex lock/unlock situation.
> > @@ -905,6 +924,16 @@ pub(crate) fn update_ref(
> > let id = info.node_ref().node.global_id();
> > refs.by_handle.remove(&handle);
> > refs.by_node.remove(&id);
> > + refs.handle_is_present.release_id(handle as usize);
> > +
> > + if let Some(shrink) = refs.handle_is_present.shrink_request() {
>
> This is questionable. Shrinking is usually the very slow path, and we
> don't shrink unless we're really close or even inside the OOM condition.
>
> In this case, shrink_request() on average returns false, but it's
> O(N), which makes _every_ release_id() O(N), while it should be O(1).
The current implementation of shrink_request() will refuse to shrink the
pool unless the largest bit is less than 1/4 of the capacity, so it
should not perform the expensive operation very often.
That said, it does call find_last_bit() each time, which I guess is
O(N). But my assumption was that find_last_bit() is cheap enough that it
wouldn't be a problem.
> Consider a very realistic case: you're destroying every object, and thus
> removing every ID in the associate ID pool, doing it in LIFO order. That
> way you will need to call shrink_request() about O(log(N)) times, making
> the whole complexity ~O(N*log(N)); and you'll have to make log(N)
> realloc()s for nothing. If you release IDs in FIFO order, you don't
> call realloc(), but your shrink_request() total complexity will be O(N^2).
Even if we end up making log(N) reallocs, the total complexity of the
reallocs is O(N) because the amount of data being reallocd halves each
time. So the total number of bytes copied by reallocs ends up being:
1 + 2 + 4 + 8 + ... + 2^log(N) <= 2^(1+log(N)) = 2*N
which is O(N).
Of course, deleting the corresponding entry from the red/black tree is
O(log N), so it's still O(N*log(N)) for the N deletions from the rb
tree.
> Can you compare performance numbers with and without shrinking under a
> typical payload? Is there any mechanism to inspect the ID pools at runtime,
> like expose via procfs?
We expose the contents of the red/black tree via the binder_logs
mechanism, but that doesn't show the *capacity* of the bitmap. Only the
index of the largest set bit.
> Can you make your shrinking logic conditional on some reasonable OOM
> heuristics, maybe OOM event driven?
>
> And even without OOM, you can safely skip shrinking if the number of IDs in
> use is greater than 1/4 of the capacity, or there's any used ID with
> the index greater than the 1/2 capacity.
I guess we could register a shrinker, but I don't think it's worth it.
Thanks for the review!
Alice
On Wed, Nov 12, 2025 at 11:35:07PM +0000, Alice Ryhl wrote:
> On Wed, Nov 12, 2025 at 02:09:19PM -0500, Yury Norov wrote:
> > On Wed, Nov 12, 2025 at 12:47:24PM +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.
> >
> > Can you share performance numbers?
>
> I have not benchmarked it in the Rust driver, but it replaces
> potentially thousands of calls to rb_next() with a single call to
> find_unused_id(), so I'm feeling good about the performance. And the
Feelings are good, but numbers are better. In the original dbitmap
patch, Carlos shared the experiment details and rough numbers, and
it's enough for me. Can you just reproduce his steps?
> equivalent change in the C driver was done because this particular piece
> of code was causing contention issues by holding the spinlock for a long
> time.
>
> The characteristics of this collection is that there is one per process
> using the driver. Most processes have only a few entries in this bitmap,
> so the inline representation will apply in most cases. However, there
> are a few processes that have a large number of entries in the 4 to
> maybe 5 figures range. Those processes are what caused the contention
> issue mentioned above.
>
> > > 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.
> >
> > That inaccurate. You are adding a new data structure (bitmap), advocating
> > it with an improvement on search side, and that makes sense.
> >
> > But now you're saying it's also a more memory efficient approach, which
> > doesn't sound trivial because the most memory efficient solution is to
> > bring no new data structures at all.
> >
> > I guess you meant that bitmap is the most efficient data structure to
> > index used/unused nodes. If so, can you please rephrase the sentence?
>
> Yes I can rephrase.
>
> Adding more data is of course always less memory efficient. What I meant
> is that this is more memory efficient than the competing solution of
> using an augmented rbtree that Carlos mentioned here:
>
> https://lore.kernel.org/p/aC1PQ7tmcqMSmbHc@google.com
>
> > > + if let Some(res) = refs.handle_is_present.find_unused_id(start) {
> > > + match refs.by_handle.entry(res.as_u32()) {
> > > + rbtree::Entry::Vacant(entry) => break (res, entry),
> > > + rbtree::Entry::Occupied(_) => {
> > > + pr_err!("Detected mismatch between handle_is_present and by_handle");
> > > + res.acquire();
> > > + continue;
> >
> > At this point you've detected mismatch between two linked data
> > structures. It means that one of them or both are corrupted. To
> > me it looks fatal, and your pr_err() confirms it. How could you
> > continue then?
>
> Although we should never hit this codepath in real code, I don't think
> we need to kill the kernel. We can treat the r/b tree as source of truth
> and adjust the bitmap when mismathces are detected.
There's no such thing like a 'source of truth', and rb-tree is not even
close to that.
You add bitmap for performance reasons, but with that you also bring
some redundancy. Now, you cross-check two data structures and see
discrepancy. At this point you can only say that either one of them
or both are corrupted.
Relying on rb-tree over bitmap is simply wrong. Statistically
speaking, there's more chances to corrupt rb-tree - just because it
is scattered and takes more memory.
> I could add a kernel warning, though. That shouldn't kill an Android
> device.
Assuming, you're talking about WARN(), I agree. But it looks like my
reasoning differs.
You never hit this path during a normal operation, as you said. So if
you're there, it means that something is already going wrong. If you
issue WARN(), you let those focused on system integrity to leverage
panic_on_warn and shut the system down to minimize any possible damage.
With that precaution, you're free to do whatever you find practical to
'recover', or even do nothing. But please avoid referring rb-tree as a
source of truth - it's a misleading and dangerous misconception.
> > > + }
> > > + }
> > > + }
> > > +
> > > + 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);
> >
> > Is it possible to turn this block into a less wordy statement? Maybe a
> > wrapper function for it? Ideally, the grow request should be handled
> > transparently in .find_unused_id().
>
> I can extract this block into a separate function, but I think it would
> be tricky to move the entire logic inside .find_unused_id() because of
> the mutex lock/unlock situation.
>
> > > @@ -905,6 +924,16 @@ pub(crate) fn update_ref(
> > > let id = info.node_ref().node.global_id();
> > > refs.by_handle.remove(&handle);
> > > refs.by_node.remove(&id);
> > > + refs.handle_is_present.release_id(handle as usize);
> > > +
> > > + if let Some(shrink) = refs.handle_is_present.shrink_request() {
> >
> > This is questionable. Shrinking is usually the very slow path, and we
> > don't shrink unless we're really close or even inside the OOM condition.
> >
> > In this case, shrink_request() on average returns false, but it's
> > O(N), which makes _every_ release_id() O(N), while it should be O(1).
>
> The current implementation of shrink_request() will refuse to shrink the
> pool unless the largest bit is less than 1/4 of the capacity, so it
> should not perform the expensive operation very often.
>
> That said, it does call find_last_bit() each time, which I guess is
> O(N). But my assumption was that find_last_bit() is cheap enough that it
> wouldn't be a problem.
It's O(N), while the expectation for release_id() is to be O(1). But if
you think it's OK for you - I'm OK as well. Can you explicitly mention
it in function description?
> > Consider a very realistic case: you're destroying every object, and thus
> > removing every ID in the associate ID pool, doing it in LIFO order. That
> > way you will need to call shrink_request() about O(log(N)) times, making
> > the whole complexity ~O(N*log(N)); and you'll have to make log(N)
> > realloc()s for nothing. If you release IDs in FIFO order, you don't
> > call realloc(), but your shrink_request() total complexity will be O(N^2).
>
> Even if we end up making log(N) reallocs, the total complexity of the
> reallocs is O(N) because the amount of data being reallocd halves each
> time. So the total number of bytes copied by reallocs ends up being:
>
> 1 + 2 + 4 + 8 + ... + 2^log(N) <= 2^(1+log(N)) = 2*N
>
> which is O(N).
OK, I trust your math better than mine. :)
> Of course, deleting the corresponding entry from the red/black tree is
> O(log N), so it's still O(N*log(N)) for the N deletions from the rb
> tree.
>
> > Can you compare performance numbers with and without shrinking under a
> > typical payload? Is there any mechanism to inspect the ID pools at runtime,
> > like expose via procfs?
>
> We expose the contents of the red/black tree via the binder_logs
> mechanism, but that doesn't show the *capacity* of the bitmap. Only the
> index of the largest set bit.
>
> > Can you make your shrinking logic conditional on some reasonable OOM
> > heuristics, maybe OOM event driven?
> >
> > And even without OOM, you can safely skip shrinking if the number of IDs in
> > use is greater than 1/4 of the capacity, or there's any used ID with
> > the index greater than the 1/2 capacity.
>
> I guess we could register a shrinker, but I don't think it's worth it.
OK, if you're fine with O(N) for release_id() - I'm fine as well. Can
you mention OOM-driven shrinking as a possible alternative for the
following improvements?
Thanks,
Yury
On Thu, Nov 13, 2025 at 12:50:37PM -0500, Yury Norov wrote:
> On Wed, Nov 12, 2025 at 11:35:07PM +0000, Alice Ryhl wrote:
> > On Wed, Nov 12, 2025 at 02:09:19PM -0500, Yury Norov wrote:
> > > On Wed, Nov 12, 2025 at 12:47:24PM +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.
> > >
> > > Can you share performance numbers?
> >
> > I have not benchmarked it in the Rust driver, but it replaces
> > potentially thousands of calls to rb_next() with a single call to
> > find_unused_id(), so I'm feeling good about the performance. And the
>
> Feelings are good, but numbers are better. In the original dbitmap
> patch, Carlos shared the experiment details and rough numbers, and
> it's enough for me. Can you just reproduce his steps?
Unfortunately Carlos doesn't have his benchmark files anymore, but I
made my own benchmark. It's a test where a client repeatedly sends a
transaction containing a node to a server, and the server stashes it
forever. This way, the number of nodes keeps growing forever. (Up to
100k nodes.)
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
The numbers measure the roundtrip latency in microseconds that it takes
to send the transaction containing the node, and to receive the
response.
I would not necessarily trust the precise numbers. Rust seems slightly
better here, but I ran it on an emulator so it may be noisy. Regardless,
I think it's pretty clear that an improvement has happened.
> > equivalent change in the C driver was done because this particular piece
> > of code was causing contention issues by holding the spinlock for a long
> > time.
> >
> > The characteristics of this collection is that there is one per process
> > using the driver. Most processes have only a few entries in this bitmap,
> > so the inline representation will apply in most cases. However, there
> > are a few processes that have a large number of entries in the 4 to
> > maybe 5 figures range. Those processes are what caused the contention
> > issue mentioned above.
> >
> > > > 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.
> > >
> > > That inaccurate. You are adding a new data structure (bitmap), advocating
> > > it with an improvement on search side, and that makes sense.
> > >
> > > But now you're saying it's also a more memory efficient approach, which
> > > doesn't sound trivial because the most memory efficient solution is to
> > > bring no new data structures at all.
> > >
> > > I guess you meant that bitmap is the most efficient data structure to
> > > index used/unused nodes. If so, can you please rephrase the sentence?
> >
> > Yes I can rephrase.
> >
> > Adding more data is of course always less memory efficient. What I meant
> > is that this is more memory efficient than the competing solution of
> > using an augmented rbtree that Carlos mentioned here:
> >
> > https://lore.kernel.org/p/aC1PQ7tmcqMSmbHc@google.com
> >
> > > > + if let Some(res) = refs.handle_is_present.find_unused_id(start) {
> > > > + match refs.by_handle.entry(res.as_u32()) {
> > > > + rbtree::Entry::Vacant(entry) => break (res, entry),
> > > > + rbtree::Entry::Occupied(_) => {
> > > > + pr_err!("Detected mismatch between handle_is_present and by_handle");
> > > > + res.acquire();
> > > > + continue;
> > >
> > > At this point you've detected mismatch between two linked data
> > > structures. It means that one of them or both are corrupted. To
> > > me it looks fatal, and your pr_err() confirms it. How could you
> > > continue then?
> >
> > Although we should never hit this codepath in real code, I don't think
> > we need to kill the kernel. We can treat the r/b tree as source of truth
> > and adjust the bitmap when mismathces are detected.
>
> There's no such thing like a 'source of truth', and rb-tree is not even
> close to that.
>
> You add bitmap for performance reasons, but with that you also bring
> some redundancy. Now, you cross-check two data structures and see
> discrepancy. At this point you can only say that either one of them
> or both are corrupted.
>
> Relying on rb-tree over bitmap is simply wrong. Statistically
> speaking, there's more chances to corrupt rb-tree - just because it
> is scattered and takes more memory.
>
> > I could add a kernel warning, though. That shouldn't kill an Android
> > device.
>
> Assuming, you're talking about WARN(), I agree. But it looks like my
> reasoning differs.
>
> You never hit this path during a normal operation, as you said. So if
> you're there, it means that something is already going wrong. If you
> issue WARN(), you let those focused on system integrity to leverage
> panic_on_warn and shut the system down to minimize any possible damage.
>
> With that precaution, you're free to do whatever you find practical to
> 'recover', or even do nothing. But please avoid referring rb-tree as a
> source of truth - it's a misleading and dangerous misconception.
Ok.
I picked the rb-tree because using the bitmap isn't possible - it
doesn't store the auxiliary data that we need.
> > > > + }
> > > > + }
> > > > + }
> > > > +
> > > > + 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);
> > >
> > > Is it possible to turn this block into a less wordy statement? Maybe a
> > > wrapper function for it? Ideally, the grow request should be handled
> > > transparently in .find_unused_id().
> >
> > I can extract this block into a separate function, but I think it would
> > be tricky to move the entire logic inside .find_unused_id() because of
> > the mutex lock/unlock situation.
> >
> > > > @@ -905,6 +924,16 @@ pub(crate) fn update_ref(
> > > > let id = info.node_ref().node.global_id();
> > > > refs.by_handle.remove(&handle);
> > > > refs.by_node.remove(&id);
> > > > + refs.handle_is_present.release_id(handle as usize);
> > > > +
> > > > + if let Some(shrink) = refs.handle_is_present.shrink_request() {
> > >
> > > This is questionable. Shrinking is usually the very slow path, and we
> > > don't shrink unless we're really close or even inside the OOM condition.
> > >
> > > In this case, shrink_request() on average returns false, but it's
> > > O(N), which makes _every_ release_id() O(N), while it should be O(1).
> >
> > The current implementation of shrink_request() will refuse to shrink the
> > pool unless the largest bit is less than 1/4 of the capacity, so it
> > should not perform the expensive operation very often.
> >
> > That said, it does call find_last_bit() each time, which I guess is
> > O(N). But my assumption was that find_last_bit() is cheap enough that it
> > wouldn't be a problem.
>
> It's O(N), while the expectation for release_id() is to be O(1). But if
> you think it's OK for you - I'm OK as well. Can you explicitly mention
> it in function description?
Sure I will mention it.
> > > Consider a very realistic case: you're destroying every object, and thus
> > > removing every ID in the associate ID pool, doing it in LIFO order. That
> > > way you will need to call shrink_request() about O(log(N)) times, making
> > > the whole complexity ~O(N*log(N)); and you'll have to make log(N)
> > > realloc()s for nothing. If you release IDs in FIFO order, you don't
> > > call realloc(), but your shrink_request() total complexity will be O(N^2).
> >
> > Even if we end up making log(N) reallocs, the total complexity of the
> > reallocs is O(N) because the amount of data being reallocd halves each
> > time. So the total number of bytes copied by reallocs ends up being:
> >
> > 1 + 2 + 4 + 8 + ... + 2^log(N) <= 2^(1+log(N)) = 2*N
> >
> > which is O(N).
>
> OK, I trust your math better than mine. :)
>
> > Of course, deleting the corresponding entry from the red/black tree is
> > O(log N), so it's still O(N*log(N)) for the N deletions from the rb
> > tree.
> >
> > > Can you compare performance numbers with and without shrinking under a
> > > typical payload? Is there any mechanism to inspect the ID pools at runtime,
> > > like expose via procfs?
> >
> > We expose the contents of the red/black tree via the binder_logs
> > mechanism, but that doesn't show the *capacity* of the bitmap. Only the
> > index of the largest set bit.
> >
> > > Can you make your shrinking logic conditional on some reasonable OOM
> > > heuristics, maybe OOM event driven?
> > >
> > > And even without OOM, you can safely skip shrinking if the number of IDs in
> > > use is greater than 1/4 of the capacity, or there's any used ID with
> > > the index greater than the 1/2 capacity.
> >
> > I guess we could register a shrinker, but I don't think it's worth it.
>
> OK, if you're fine with O(N) for release_id() - I'm fine as well. Can
> you mention OOM-driven shrinking as a possible alternative for the
> following improvements?
Sure.
Alice
On Thu, Nov 13, 2025 at 12:35 AM Alice Ryhl <aliceryhl@google.com> wrote: > > Although we should never hit this codepath in real code, I don't think > we need to kill the kernel. We can treat the r/b tree as source of truth > and adjust the bitmap when mismathces are detected. > > I could add a kernel warning, though. That shouldn't kill an Android > device. I guess you mean warning in the sense of `pr_warn!` instead of `warn_on!`, right? If so, could you please add as well a `debug_assert!(false)` on that path? Thanks! I will create a first issue for the combination, since I hope we can use it more and more. Cheers, Miguel
On Thu, Nov 13, 2025 at 09:32:10AM +0100, Miguel Ojeda wrote: > On Thu, Nov 13, 2025 at 12:35 AM Alice Ryhl <aliceryhl@google.com> wrote: > > > > Although we should never hit this codepath in real code, I don't think > > we need to kill the kernel. We can treat the r/b tree as source of truth > > and adjust the bitmap when mismathces are detected. > > > > I could add a kernel warning, though. That shouldn't kill an Android > > device. > > I guess you mean warning in the sense of `pr_warn!` instead of > `warn_on!`, right? I was thinking of warn_on!. There is already a pr_err call. > If so, could you please add as well a `debug_assert!(false)` on that path? > > Thanks! > > I will create a first issue for the combination, since I hope we can > use it more and more. > > Cheers, > Miguel
On Thu, Nov 13, 2025 at 10:14 AM Alice Ryhl <aliceryhl@google.com> wrote: > > I was thinking of warn_on!. There is already a pr_err call. I see -- if you end up not adding the `warn_on!`, then please add the `debug_assert!` instead. That should help and it also makes it even more clear that it is something that should never ever happen. Cheers, Miguel
© 2016 - 2026 Red Hat, Inc.