rust_binder: use bitmap for allocation of handles

To find an unused Binder handle, Rust Binder currently iterates the
red/black tree from the beginning until it finds a gap in the keys. This
is extremely slow.

To improve the performance, add a bitmap that keeps track of which
indices are actually in use. This allows us to quickly find an unused
key in the red/black tree.

For a benchmark, please see the below numbers that were obtained from
modifying binderThroughputTest to send a node with each transaction and
stashing it in the server. This results in the number of nodes
increasing by one for every transaction sent. I got the following table
of roundtrip latencies (in µs):

Transaction Range │ Baseline (Rust) │ Bitmap (Rust) │ Comparison (C)
0 - 10,000        │          176.88 │         92.93 │          99.41
10,000 - 20,000   │          437.37 │         87.74 │          98.55
20,000 - 30,000   │          677.49 │         76.24 │          96.37
30,000 - 40,000   │          901.76 │         83.39 │          96.73
40,000 - 50,000   │         1126.62 │        100.44 │          94.57
50,000 - 60,000   │         1288.98 │         94.38 │          96.64
60,000 - 70,000   │         1588.74 │         88.27 │          96.36
70,000 - 80,000   │         1812.97 │         93.97 │          91.24
80,000 - 90,000   │         2062.95 │         92.22 │         102.01
90,000 - 100,000  │         2330.03 │         97.18 │         100.31

It should be clear that the current Rust code becomes linearly slower
per insertion as the number of calls to rb_next() per transaction
increases. After this change, the time to find an ID number appears
constant. (Technically it is not constant-time as both insertion and
removal scan the entire bitmap. However, quick napkin math shows that
scanning the entire bitmap with N=100k takes ~1.5µs, which is neglible
in a benchmark where the rountrip latency is 100µs.)

I've included a comparison to the C driver, which uses the same bitmap
algorithm as this patch since commit 15d9da3f818c ("binder: use bitmap
for faster descriptor lookup").

This currently checks if the bitmap should be shrunk after every
removal. One potential future change is introducing a shrinker to make
this operation O(1), but based on the benchmark above this does not seem
required at this time.

Reviewed-by: Burak Emir <bqe@google.com>
Reviewed-by: Yury Norov (NVIDIA) <yury.norov@gmail.com>
Acked-by: Carlos Llamas <cmllamas@google.com>
Signed-off-by: Alice Ryhl <aliceryhl@google.com>
Signed-off-by: Yury Norov (NVIDIA) <yury.norov@gmail.com>

0 files changed, 0 insertions, 0 deletions