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

[PATCH v2] 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>
---

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


It took me a while to get the AOSP + Cuttlefish setup running, and
using the rust binder module. I got it working, and ran:
libhwbinder_benchmark libbinder_benchmark, hwbinderThroughputTest
            libhwbinder_latency and binderThroughputTest benches.
But apparently none of them used the function I touched (I added log).
Also, the "hw" variants like hwbinderThroughputTest kept logging a
 "worker_fx:217 condition:service->isRemote() failed" message.
I decided to send the v2 anyway.

I am thinking about writing a benchmark focused on node scaling
    (test N iterations with X nodes), and run with small and larger Xs.)
Would such a benchmark be welcome here in upstream mainline ?
It would be in either C or Rust (the AOSP ones are in C++).
Would it live under `tools/perf` ?

I looked at the kunit tests (`drivers/android/tests`) and they dont
cover the rust binder either. That's another thing I could try to add.


I'd love some feedback regarding next steps :)
Thanks,
Rafael Passos


 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 cdd1a90797266..68c9384fbf69f 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.53.0

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

[Alice Ryhl]

On Fri, Jul 31, 2026 at 10:31:03AM -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>

This looks fine to me.

Reviewed-by: Alice Ryhl <aliceryhl@google.com>

> It took me a while to get the AOSP + Cuttlefish setup running, and
> using the rust binder module. I got it working, and ran:
> libhwbinder_benchmark libbinder_benchmark, hwbinderThroughputTest
>             libhwbinder_latency and binderThroughputTest benches.
> But apparently none of them used the function I touched (I added log).
> Also, the "hw" variants like hwbinderThroughputTest kept logging a
>  "worker_fx:217 condition:service->isRemote() failed" message.
> I decided to send the v2 anyway.
> 
> I am thinking about writing a benchmark focused on node scaling
>     (test N iterations with X nodes), and run with small and larger Xs.)
> Would such a benchmark be welcome here in upstream mainline ?
> It would be in either C or Rust (the AOSP ones are in C++).
> Would it live under `tools/perf` ?
> 
> I looked at the kunit tests (`drivers/android/tests`) and they dont
> cover the rust binder either. That's another thing I could try to add.

In Android this is used by libmemunreachable when checking whether a
process has a memory leak. The perf matters because if the number of
nodes is very large, invoking the ioctl repeatedly many times could take
a seriously large amount of time. Seconds or even more.

Alice

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

[kernel test robot]

Hi Rafael,

kernel test robot noticed the following build errors:

[auto build test ERROR on staging/staging-testing]
[also build test ERROR on staging/staging-next staging/staging-linus linus/master v7.2-rc7 next-20260810]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]

url:    https://github.com/intel-lab-lkp/linux/commits/Rafael-Passos/rust_binder-speed-up-get_node_debug_info-using-lower_bound-iter/20260806-233902
base:   staging/staging-testing
patch link:    https://lore.kernel.org/r/20260731133253.661634-1-rafael%40rcpassos.me
patch subject: [PATCH v2] rust_binder: speed up get_node_debug_info using lower_bound iter
config: x86_64-rhel-9.4-rust (https://download.01.org/0day-ci/archive/20260810/202608102134.Dygd1Kx3-lkp@intel.com/config)
compiler: clang version 22.1.8 (https://github.com/llvm/llvm-project ca7933e47d3a3451d81e72ac174dcb5aa28b59d1)
rustc: rustc 1.96.0 (ac68faa20 2026-05-25)
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20260810/202608102134.Dygd1Kx3-lkp@intel.com/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of
the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <lkp@intel.com>
| Closes: https://lore.kernel.org/oe-kbuild-all/202608102134.Dygd1Kx3-lkp@intel.com/

All errors (new ones prefixed by >>):

   PATH=/opt/cross/clang-22/bin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin
   INFO PATH=/opt/cross/rustc-1.96.0-bindgen-0.72.1/cargo/bin:/opt/cross/clang-22/bin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin
   /usr/bin/timeout -k 100 12h /usr/bin/make KCFLAGS=\ -fno-crash-diagnostics\ -Wno-error=return-type\ -Wreturn-type\ -funsigned-char\ -Wundef\ -falign-functions=64 W=1 --keep-going LLVM=1 -j384 -C source O=/kbuild/obj/consumer/x86_64-rhel-9.4-rust ARCH=x86_64 SHELL=/bin/bash rustfmtcheck 
   make: Entering directory '/kbuild/src'
   make[1]: Entering directory '/kbuild/obj/consumer/x86_64-rhel-9.4-rust'
>> Diff in drivers/android/binder/process.rs:1175:
            {
                let inner = self.inner.lock();
                // cursor_lower_bound retrieves the "key" passed or the next existing larger key
   -            if let Some(cursor) = inner.nodes.cursor_lower_bound(&(ptr+1)){
   +            if let Some(cursor) = inner.nodes.cursor_lower_bound(&(ptr + 1)) {
                    let (_, node) = cursor.current();
                    node.populate_debug_info(&mut out, &inner);
                }
>> Diff in drivers/android/binder/process.rs:1175:
            {
                let inner = self.inner.lock();
                // cursor_lower_bound retrieves the "key" passed or the next existing larger key
   -            if let Some(cursor) = inner.nodes.cursor_lower_bound(&(ptr+1)){
   +            if let Some(cursor) = inner.nodes.cursor_lower_bound(&(ptr + 1)) {
                    let (_, node) = cursor.current();
                    node.populate_debug_info(&mut out, &inner);
                }
   make[2]: *** [Makefile:1998: rustfmt] Error 123
   make[1]: Leaving directory '/kbuild/obj/consumer/x86_64-rhel-9.4-rust'
   make[1]: *** [Makefile:248: __sub-make] Error 2
   make[2]: Target 'rustfmtcheck' not remade because of errors.
   make[1]: Target 'rustfmtcheck' not remade because of errors.
   make: *** [Makefile:248: __sub-make] Error 2
   make: Target 'rustfmtcheck' not remade because of errors.
   make: Leaving directory '/kbuild/src'

--
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki