linux-kernel - Re: [PATCH] binder: use augmented rb-tree for faster descriptor lookup

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: <ZuyQ8ECy0ypuOStg@google.com>
Date: Thu, 19 Sep 2024 21:00:32 +0000
From: Carlos Llamas <cmllamas@...gle.com>
To: Shu Han <ebpqwerty472123@...il.com>
Cc: gregkh@...uxfoundation.org, arve@...roid.com, tkjos@...roid.com,
	maco@...roid.com, joel@...lfernandes.org, brauner@...nel.org,
	surenb@...gle.com, linux-kernel@...r.kernel.org,
	aliceryhl@...gle.com
Subject: Re: [PATCH] binder: use augmented rb-tree for faster descriptor
 lookup

On Tue, Sep 17, 2024 at 11:02:03AM +0800, Shu Han wrote:
> The advantages of accelerating descriptor lookup were explained in the
> commit 15d9da3f818c ("binder: use bitmap for faster descriptor lookup").
> However, the time complexity of the bitmap is still O(n), and performance
> can still be slow when there are too many references. In addition,
> additional allocation/free calls are required.
> Since there is already an rb-tree with the key 'desc' on 'binder_proc', an
> augmented rb-tree with a subtree-size field can easily search for the
> smallest non-existent 'desc' in O(logn) time. This lookup can be merged
> with the subsequent rb-tree lookup for insertion, so there is no
> additional overhead except for maintaining the size field. And there is no
> need to maintain the fast path and slow path at the same time since this
> method is good enough for all cases.
> The core idea of this algorithm is to maintain the count of nodes whose
> descriptor is smaller than the current node, except the left subtree of
> the current node, when searching downwards from the root. To achieve this,
> simply add the size of the left subtree and the current node itself to the
> maintained value before moving to the right child. If the count of nodes
> whose descriptor is smaller than the current node (the sum of maintained
> value and the size of the left subtree of the current node) reaches the
> current node's descriptor, it means that there are no descriptors smaller
> than the current node waiting for allocation, so we should move to the
> right subtree. Otherwise, we should move to the left subtree.
> In order to be compatible with the behavior that only the context manager
> can be assigned by 0, an additional bool value is maintained on the proc
> to indicate whether there is a ref assigned as 0 and some adjustments to
> the search algorithm made.
> Another consideration is that as the descriptor allocation speed
> increases, integer overflow may become feasible.
> 
> Signed-off-by: Shu Han <ebpqwerty472123@...il.com>
> ---

Thanks for you patch.

I remeber discussing this exact approach with Alice sometime ago but I
don't recall why I decided not to go with it. I'll have a closer look
at your patch and will try to remember more details next week. Most
folks are currently at LPC right now.

Cheers,
Carlos Llamas