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

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

[nenkov2004]

From: ChrisX101010 <nenkov2004@gmail.com>

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@google.com>
Link: https://github.com/Rust-for-Linux/linux/issues/1249
Signed-off-by: ChrisX101010 <nenkov2004@gmail.com>
---
 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

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

[Greg Kroah-Hartman]

On Mon, Aug 31, 2026 at 07:26:35AM +0200, nenkov2004@gmail.com wrote:
> From: ChrisX101010 <nenkov2004@gmail.com>

We need a real name, thanks.

greg k-h

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

[nenkov2004]

From: Hristos Nenkov <nenkov2004@gmail.com>

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@google.com>
Link: https://github.com/Rust-for-Linux/linux/issues/1249
Signed-off-by: Hristos Nenkov <nenkov2004@gmail.com>
---
 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

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

[Alice Ryhl]

On Mon, Aug 31, 2026 at 07:26:35AM +0200, nenkov2004@gmail.com wrote:
> From: ChrisX101010 <nenkov2004@gmail.com>
> 
> 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@google.com>
> Link: https://github.com/Rust-for-Linux/linux/issues/1249
> Signed-off-by: ChrisX101010 <nenkov2004@gmail.com>

This is a duplicate:

https://lore.kernel.org/all/20260814215145.2050599-1-rafael@rcpassos.me/

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

[Greg Kroah-Hartman]

On Mon, Aug 31, 2026 at 07:49:20AM +0200, nenkov2004@gmail.com wrote:
> From: Hristos Nenkov <nenkov2004@gmail.com>
> 
> 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@google.com>
> Link: https://github.com/Rust-for-Linux/linux/issues/1249
> Signed-off-by: Hristos Nenkov <nenkov2004@gmail.com>
> ---
>  drivers/android/binder/process.rs | 8 ++++++--
>  1 file changed, 6 insertions(+), 2 deletions(-)

This does not apply to the char-misc-testing branch :(

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

[Alice Ryhl]

On Thu, Oct 1, 2026 at 2:38 PM Greg Kroah-Hartman
<gregkh@linuxfoundation.org> wrote:
>
> On Mon, Aug 31, 2026 at 07:49:20AM +0200, nenkov2004@gmail.com wrote:
> > From: Hristos Nenkov <nenkov2004@gmail.com>
> >
> > 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@google.com>
> > Link: https://github.com/Rust-for-Linux/linux/issues/1249
> > Signed-off-by: Hristos Nenkov <nenkov2004@gmail.com>
> > ---
> >  drivers/android/binder/process.rs | 8 ++++++--
> >  1 file changed, 6 insertions(+), 2 deletions(-)
>
> This does not apply to the char-misc-testing branch :(

Please check this instead:
https://lore.kernel.org/all/20260814215145.2050599-1-rafael@rcpassos.me/

This one is a duplicate, and I prefer the other one.

Alice

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

[Greg Kroah-Hartman]

On Thu, Oct 01, 2026 at 03:43:25PM +0200, Alice Ryhl wrote:
> On Thu, Oct 1, 2026 at 2:38 PM Greg Kroah-Hartman
> <gregkh@linuxfoundation.org> wrote:
> >
> > On Mon, Aug 31, 2026 at 07:49:20AM +0200, nenkov2004@gmail.com wrote:
> > > From: Hristos Nenkov <nenkov2004@gmail.com>
> > >
> > > 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@google.com>
> > > Link: https://github.com/Rust-for-Linux/linux/issues/1249
> > > Signed-off-by: Hristos Nenkov <nenkov2004@gmail.com>
> > > ---
> > >  drivers/android/binder/process.rs | 8 ++++++--
> > >  1 file changed, 6 insertions(+), 2 deletions(-)
> >
> > This does not apply to the char-misc-testing branch :(
> 
> Please check this instead:
> https://lore.kernel.org/all/20260814215145.2050599-1-rafael@rcpassos.me/
> 
> This one is a duplicate, and I prefer the other one.

Ah good, I already took that one :)

thanks,

greg k-h