[PATCH v2] rust: binder: Use lower bound for node debug lookup

[nenkov2004]

From: Hristos Nenkov <nenkov2004@xxxxxxxxx>

The Binder node debug lookup currently walks the process node RBTree
from the beginning until it finds the first node pointer greater than
the requested pointer.

Use RBTree::cursor_lower_bound() to start the lookup at the relevant
tree position instead. When the lower-bound key is equal to the
requested pointer, inspect the next node to preserve the existing
strictly-greater-than semantics.

This changes the tree lookup from a linear scan to an O(log n) search
without changing the returned node semantics.

Suggested-by: Alice Ryhl <aliceryhl@xxxxxxxxxx>
Link: https://github.com/Rust-for-Linux/linux/issues/1249
Signed-off-by: Hristos Nenkov <nenkov2004@xxxxxxxxx>
---
 drivers/android/binder/process.rs | 8 ++++++--
 1 file changed, 6 insertions(+), 2 deletions(-)

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

base-commit: cee9395acd8043be0644b25c34bfa86623f2b935
-- 
2.43.0