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

[PATCH v3] 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).

Reviewed-by: Alice Ryhl <aliceryhl@google.com>
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>
---

V1: https://lore.kernel.org/rust-for-linux/20260728012249.3084154-1-rafael@rcpassos.me/
Changes from V1:
    - remove the "if/else" block checking if the current>prt.
      The cursor_lower_bound function returns the "key" or the next larger.
      This is indeed better, my check was unnecessary.
    - add a comment about this fact before the cursor_lower_bound

V2: https://lore.kernel.org/rust-for-linux/20260731133253.661634-1-rafael@rcpassos.me/
Changes from V2:
    - formatting fixes with rustfmt


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

diff --git a/drivers/android/binder/process.rs b/drivers/android/binder/process.rs
index cdd1a9079726..b74c26f041bf 100644
--- a/drivers/android/binder/process.rs
+++ b/drivers/android/binder/process.rs
@@ -1174,11 +1174,10 @@ fn get_node_debug_info(&self, data: UserSlice) -> Result {
 
         {
             let inner = self.inner.lock();
-            for (node_ptr, node) in &inner.nodes {
-                if *node_ptr > ptr {
-                    node.populate_debug_info(&mut out, &inner);
-                    break;
-                }
+            // cursor_lower_bound retrieves the "key" passed or the next existing larger key
+            if let Some(cursor) = inner.nodes.cursor_lower_bound(&(ptr + 1)) {
+                let (_, node) = cursor.current();
+                node.populate_debug_info(&mut out, &inner);
             }
         }
 
-- 
2.55.0

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

[Rafael Passos]

Hi!

I'm looking for feedback in this patch.
I believe this is a good time,
since the merge window was just closed.
Maybe this could be ready for 7.4 ?

Thanks,
Rafael Passos

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

[Alice Ryhl]

On Thu, Sep 03, 2026 at 10:40:39AM -0300, Rafael Passos wrote:
> Hi!
> 
> I'm looking for feedback in this patch.
> I believe this is a good time,
> since the merge window was just closed.
> Maybe this could be ready for 7.4 ?

You already have my Reviewed-by and it looks like this still applies
cleanly, I believe Greg will pick it up at some point during this cycle.
Thanks.

Alice