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: Windows password security audit tool. GUI, reports in PDF.

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

Message-ID: <aPeMf6C-dRI5OlTE@google.com>
Date: Tue, 21 Oct 2025 13:37:03 +0000
From: Alice Ryhl <aliceryhl@...gle.com>
To: Burak Emir <bqe@...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 05:06:26PM +0200, Burak Emir wrote:
> 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.

No I should be using it in Binder. I forgot to update the code to use
it.

Alice