[PATCH] rust_binder: speed up get_node_debug_info using lower_bound iter

[PATCH] rust_binder: speed up get_node_debug_info using lower_bound iter

[Rafael Passos]

Finding the next node in the RBTree can be done more efficiently using
the cursor_lower_bound, as it reduces cost from O(n) to O(log n).

Link: https://github.com/Rust-for-Linux/linux/issues/1249
Suggested-by: Alice Ryhl <aliceryhl@google.com>
Signed-off-by: Rafael Passos <rafael@rcpassos.me>
---

(Sorry for the resend, my script missed the list)

Hi, I decided to use the peek_next semantic instead of a loop/break.
Since the iterator should land directly on ptr or greater, I think this
is more elegant this way. But I can change it otherwise.

Thanks,
Rafael


 drivers/android/binder/process.rs | 9 +++++++--
 1 file changed, 7 insertions(+), 2 deletions(-)

diff --git a/drivers/android/binder/process.rs b/drivers/android/binder/process.rs
index cdd1a90797266..c0c2112aca1c6 100644
--- a/drivers/android/binder/process.rs
+++ b/drivers/android/binder/process.rs
@@ -1174,10 +1174,15 @@ fn get_node_debug_info(&self, data: UserSlice) -> Result {
 
         {
             let inner = self.inner.lock();
-            for (node_ptr, node) in &inner.nodes {
+            let cursor = inner.nodes.cursor_lower_bound(&ptr);
+            if let Some(c) = cursor {
+                let (node_ptr, node) = c.current();
                 if *node_ptr > ptr {
                     node.populate_debug_info(&mut out, &inner);
-                    break;
+                } else if *node_ptr == ptr {
+                    if let Some((_, next_node)) = c.peek_next() {
+                        next_node.populate_debug_info(&mut out, &inner);
+                    }
                 }
             }
         }
-- 
2.53.0

Re: [PATCH] rust_binder: speed up get_node_debug_info using lower_bound iter

[Onur Özkan]

On Mon, 27 Jul 2026 22:22:18 -0300
Rafael Passos <rafael@rcpassos.me> wrote:

> Finding the next node in the RBTree can be done more efficiently using
> the cursor_lower_bound, as it reduces cost from O(n) to O(log n).
> 
> Link: https://github.com/Rust-for-Linux/linux/issues/1249
> Suggested-by: Alice Ryhl <aliceryhl@google.com>
> Signed-off-by: Rafael Passos <rafael@rcpassos.me>
> ---
> 
> (Sorry for the resend, my script missed the list)
> 
> Hi, I decided to use the peek_next semantic instead of a loop/break.
> Since the iterator should land directly on ptr or greater, I think this
> is more elegant this way. But I can change it otherwise.
> 
> Thanks,
> Rafael
> 
> 
>  drivers/android/binder/process.rs | 9 +++++++--
>  1 file changed, 7 insertions(+), 2 deletions(-)
> 
> diff --git a/drivers/android/binder/process.rs b/drivers/android/binder/process.rs
> index cdd1a90797266..c0c2112aca1c6 100644
> --- a/drivers/android/binder/process.rs
> +++ b/drivers/android/binder/process.rs
> @@ -1174,10 +1174,15 @@ fn get_node_debug_info(&self, data: UserSlice) -> Result {
>  
>          {
>              let inner = self.inner.lock();
> -            for (node_ptr, node) in &inner.nodes {
> +            let cursor = inner.nodes.cursor_lower_bound(&ptr);
> +            if let Some(c) = cursor {

Why not "if let Some(cursor) = inner.nodes.cursor_lower_bound..." ?

> +                let (node_ptr, node) = c.current();
>                  if *node_ptr > ptr {
>                      node.populate_debug_info(&mut out, &inner);
> -                    break;
> +                } else if *node_ptr == ptr {
> +                    if let Some((_, next_node)) = c.peek_next() {
> +                        next_node.populate_debug_info(&mut out, &inner);
> +                    }
>                  }
>              }
>          }
> -- 
> 2.53.0
> 

Re: [PATCH] rust_binder: speed up get_node_debug_info using lower_bound iter

[Alice Ryhl]

On Mon, Jul 27, 2026 at 10:22:18PM -0300, Rafael Passos wrote:
> Finding the next node in the RBTree can be done more efficiently using
> the cursor_lower_bound, as it reduces cost from O(n) to O(log n).
> 
> Link: https://github.com/Rust-for-Linux/linux/issues/1249
> Suggested-by: Alice Ryhl <aliceryhl@google.com>
> Signed-off-by: Rafael Passos <rafael@rcpassos.me>
> ---
> 
> (Sorry for the resend, my script missed the list)
> 
> Hi, I decided to use the peek_next semantic instead of a loop/break.
> Since the iterator should land directly on ptr or greater, I think this
> is more elegant this way. But I can change it otherwise.
> 
> Thanks,
> Rafael
> 
> 
>  drivers/android/binder/process.rs | 9 +++++++--
>  1 file changed, 7 insertions(+), 2 deletions(-)
> 
> diff --git a/drivers/android/binder/process.rs b/drivers/android/binder/process.rs
> index cdd1a90797266..c0c2112aca1c6 100644
> --- a/drivers/android/binder/process.rs
> +++ b/drivers/android/binder/process.rs
> @@ -1174,10 +1174,15 @@ fn get_node_debug_info(&self, data: UserSlice) -> Result {
>  
>          {
>              let inner = self.inner.lock();
> -            for (node_ptr, node) in &inner.nodes {
> +            let cursor = inner.nodes.cursor_lower_bound(&ptr);
> +            if let Some(c) = cursor {
> +                let (node_ptr, node) = c.current();
>                  if *node_ptr > ptr {
>                      node.populate_debug_info(&mut out, &inner);
> -                    break;
> +                } else if *node_ptr == ptr {
> +                    if let Some((_, next_node)) = c.peek_next() {
> +                        next_node.populate_debug_info(&mut out, &inner);
> +                    }
>                  }
>              }
>          }
> -- 
> 2.53.0
> 

This would be a lot simpler if you just did `cursor_lower_bound(ptr+1)`
so that you go straight to the right target node, instead of doing this
if/else logic.

Alice

Re: [PATCH] rust_binder: speed up get_node_debug_info using lower_bound iter

[Rafael Passos]

Hi Greg and Alice,

On Tue, Jul 28, 2026 at 6:54 AM Greg KH <gregkh@linuxfoundation.org> wrote:
>
> On Mon, Jul 27, 2026 at 10:03:21PM -0300, Rafael Passos wrote:
> > Finding the next node in the RBTree can be done more efficiently using
> > the cursor_lower_bound, as it reduces cost from O(n) to O(log n).
> >
> > Link: https://github.com/Rust-for-Linux/linux/issues/1249
> > Suggested-by: Alice Ryhl <aliceryhl@google.com>
> > Signed-off-by: Rafael Passos <rafael@rcpassos.me>
> > ---
>
> Does this actually speed anything up in the binder benchmark tools?

I want to run these benchmarks! I searched and this "Performance testing"
page [1] in android docs was the closest match. Am I correct?

I'm learning more about binder, watching the talks, reading posts etc.
It's really interesting. Any recommendations on how to run in VMs and in
Hardware ? Is the Cuttlefish emulator the recommended setup ?

On Tue Jul 28, 2026 at 2:47 AM -03, Alice Ryhl wrote:
> I don't think I got the email for this patch?

Sorry for the confusion. I had to send it twice because I missed the
list in the first email. The second send is in lore [2].
I will send a v2 with suggestions. This message might reach both
threads (if I manipulated the headers correctly ;P)

[1] Android Performance testing https://source.android.com/docs/core/tests/vts/performance
[2] patch resend https://lore.kernel.org/rust-for-linux/amhHBxSfuat8WZ8R@google.com/T/#t

Thanks,
Rafael Passos