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

[Carlos Llamas <cmllamas@google.com>]

On Wed, Oct 02, 2024 at 08:24:34PM +0800, Shu Han wrote:
> Thanks for reply.

Ok, I'll have a look at your patch now.

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

I honestly don't remember. It might have been that we required to expand
the 'struct binder_ref' size. This issue starts to be a problem when we
have thousands of references e.g. 30,000. Adding 4 bytes to each one of
them might not be worth it. But let me check...

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

Yeah, I think it would look cleaner if we do a revert of the previous
patches though. This way we can remove the noise and see the actual
changes. I'll do this locally for now, no need to send a v2 just yet.

> 
> 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@google.com/
> [1]
> 
> Best regards.
> 
> Carlos Llamas <cmllamas@google.com> 于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@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

Cheers,
Carlos Llamas