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: <CAHQche8v5CTW0L2cJGCDWOJ---KRv9wxWAk=eUaK1+k9UTcpHA@mail.gmail.com>
Date: Wed, 9 Oct 2024 23:08:42 +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

On Wed, Oct 9, 2024 at 4:58 AM Carlos Llamas <cmllamas@...gle.com> wrote:

Thank you for your patient reply.

> 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 didn't consider memory overhead before...
That's indeed an important point.

Fortunately, after checking, I found that this patch does not occupy any
additional memory for `struct binder_ref`.

In a modern 64-bit platform, the size of `struct binder_ref` is 104 bytes.
If we add a 4-byte field into it, the size will be 112 bytes(aligned by
long). And both of them occupy a 128-byte slab(aligned by kmalloc_index).
So the memory cost won't be increased, if there isn't a pending change
that needs exactly 24 bytes in `struct binder_ref`.

In Rust, a rbtree::Node costs 40 bytes, 4 of 40 are used for alignment,
adding a 4-byte field won't change the size of the struct.

In a 32-bit platform, the number is from 60 bytes to 64 bytes, a 64-byte
slab, exactly 4 bytes.(very close to the slab bound)

Perhaps it's caused by introducing augmented rbtree into Rust which
requires considerable effort. But personally, I think it's not bad to just
introduce augmented rbtree into C (Rust and C are already quite different
here).

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

Great point. thanks.

Best regards.