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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-ID: <CACQBu=VLPGq0nx6PJSnw3YBhMe4QKHiiFG0k9_Kwayj9w6nfLQ@mail.gmail.com>
Date: Mon, 20 Oct 2025 17:06:26 +0200
From: Burak Emir <bqe@...gle.com>
To: Alice Ryhl <aliceryhl@...gle.com>
Cc: Greg Kroah-Hartman <gregkh@...uxfoundation.org>, Yury Norov <yury.norov@...il.com>, 
	Arve Hjønnevåg <arve@...roid.com>, 
	Todd Kjos <tkjos@...roid.com>, Martijn Coenen <maco@...roid.com>, 
	Joel Fernandes <joelagnelf@...dia.com>, Christian Brauner <brauner@...nel.org>, 
	Carlos Llamas <cmllamas@...gle.com>, Suren Baghdasaryan <surenb@...gle.com>, Miguel Ojeda <ojeda@...nel.org>, 
	Boqun Feng <boqun.feng@...il.com>, Gary Guo <gary@...yguo.net>, 
	Björn Roy Baron <bjorn3_gh@...tonmail.com>, 
	Benno Lossin <lossin@...nel.org>, Andreas Hindborg <a.hindborg@...nel.org>, 
	Trevor Gross <tmgross@...ch.edu>, Danilo Krummrich <dakr@...nel.org>, rust-for-linux@...r.kernel.org, 
	linux-kernel@...r.kernel.org
Subject: Re: [PATCH 2/2] rust_binder: use bitmap for allocation of handles

On Mon, Oct 20, 2025 at 3:33 PM Alice Ryhl <aliceryhl@...gle.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@...gle.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