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: <CAHQche-rZODDsxbf6b3uagLfM52YtcoUuaeW0NxXcPTFFNcsZA@mail.gmail.com>
Date: Wed, 2 Oct 2024 20:24:34 +0800
From: Shu Han <ebpqwerty472123@...il.com>
To: Carlos Llamas <cmllamas@...gle.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

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@google.com/
[1]

Best regards.

Carlos Llamas <cmllamas@...gle.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@...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