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

[Shu Han]

On Wed, Oct 9, 2024 at 4:58 AM Carlos Llamas <cmllamas@xxxxxxxxxx> 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.