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

[Carlos Llamas <cmllamas@google.com>]

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@gmail.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