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

[Shu Han]

Thanks for reply.

Could you please let me know why this approach is not being used?

I think it looks simple, with minimal modifications and
better performance.

It is also suitable for possible future migration to XArray[1],
as XArray is also a data structure with
built-in ID allocation method(xa_alloc).

Link: https://lore.kernel.org/all/20231101-rust-binder-v1-0-08ba9197f637@xxxxxxxxxx/
[1]

Best regards.

Carlos Llamas <cmllamas@xxxxxxxxxx> 于2024年9月20日周五 05:00写道：
>
> 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@xxxxxxxxx>
> > ---
>
> 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