Re: [PATCH 2/2] rust_binder: use bitmap for allocation of handles

Burak Emir
2025-10-20T15:06:39Z

On Mon, Oct 20, 2025 at 3:33 PM Alice Ryhl <aliceryhl@google.com> wrote:
>
> 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.
>
> This logic matches the approach used by C Binder. It was chosen
> partially because it's the most memory efficient solution.
>
> Signed-off-by: Alice Ryhl <aliceryhl@google.com>
> ---
> drivers/android/binder/process.rs | 110 +++++++++++++++++++++++++++++++-------
> 1 file changed, 90 insertions(+), 20 deletions(-)
>
> diff --git a/drivers/android/binder/process.rs b/drivers/android/binder/process.rs
> index f13a747e784c84a0fb09cbf47442712106eba07c..357ba1b577c73ad3f2b525a8573424420577e92d 100644
> --- a/drivers/android/binder/process.rs
> +++ b/drivers/android/binder/process.rs
> @@ -16,6 +16,7 @@
>
> use kernel::{
> bindings,
> + bitmap::BitmapVec,
> cred::Credential,
> error::Error,
> fs::file::{self, File},
> @@ -367,6 +368,8 @@ impl ListItem<{Self::LIST_NODE}> for NodeRefInfo {
> struct ProcessNodeRefs {
> /// Used to look up nodes using the 32-bit id that this process knows it by.
> by_handle: RBTree<u32, ListArc<NodeRefInfo, { NodeRefInfo::LIST_PROC }>>,
> + /// Used to quickly find unused ids in `by_handle`.
> + handle_present: BitmapVec,

Are you going to delete rust/kernel/id_pool.rs, too?

I have no opinion on whether having an abstraction vs inlining the
functionality is worth it. I mean just in order to avoid id_pool.rs
hanging around as dead code.

Cheers,
Burak