Re: [PATCH v12 0/5] Red-black tree abstraction needed by Rust Binder

["David Rheinsberg" <david@readahead.eu>]

Hi

On Thu, Aug 22, 2024, at 6:37 PM, Matt Gilbride wrote:
> This patchset contains the red-black tree abstractions needed by the Rust
> implementation of the Binder driver.
>
> Binder driver benefits from O(log n) search/insertion/deletion of
> key/value mappings in various places, including `process.rs` and
> `range_alloc.rs`.  In `range_alloc.rs`, the ability to store and
> search by a generic key type is also useful.
>
> Please see the Rust Binder RFC for usage examples [1]. Note that
> the `container_of` macro is currently used only by `rbtree` itself.
>
> Users of "rust: rbtree: add red-black tree implementation backed by the 
> C version"
>     [PATCH RFC 03/20] rust_binder: add threading support
>     [PATCH RFC 05/20] rust_binder: add nodes and context managers
>     [PATCH RFC 06/20] rust_binder: add oneway transactions
>
> Users of "rust: rbtree: add iterator"
>     [PATCH RFC 17/20] rust_binder: add oneway spam detection
>
> Users of "rust: rbtree: add mutable iterator"
>     [PATCH RFC 06/20] rust_binder: add oneway transactions
>
> Users of "rust: rbtree: add `RBTreeCursor`"
>     [PATCH RFC 06/20] rust_binder: add oneway transactions
>
> Users of "rust: rbtree: add RBTree::entry"
>     Not used in the original RFC, but introduced after further
>     code review.  See: https://r.android.com/2849906
>
> The Rust Binder RFC addresses the upstream deprecation of red-black
> tree. Quoted here for convenience:
>
> "This RFC uses the kernel's red-black tree for key/value mappings, but we
> are aware that the red-black tree is deprecated. We did this to make the
> performance comparison more fair, since C binder also uses rbtree for
> this. We intend to replace these with XArrays instead. That said, we
> don't think that XArray is a good fit for the range allocator, and we
> propose to continue using the red-black tree for the range allocator."

(I might have missed this in previous versions of the patchset, so let me know if this has been answered before.)

1) Have you had any chance to compare this (performance wise) to the intrusive version used by the C Binder implementation? I assume the allocations are negligible, but tree-traversal should be significantly faster with intrusive trees when keys are next to the rb-node (e.g., binder range allocator, or ref/node lookup based on u64). With the allocating style, you likely double the number of cache-lines you load during a traversal, don't you?
We have been trying hard to keep the intrusive style, but never really measured the performance. So in case you do have numbers / experience, I would love to hear about it.

2) Similar to 1), what is the reason to avoid the intrusive style? Is this just to simplify the API and keep it close to what rust-std does? Is the intention of this RFC to move towards an allocating style, or is work on the intrusive abstraction still welcome? I guess for compatibility to C-code, we still need the intrusive helpers, and likely for a long time.

3) I know that Matthew has spent significant time converting users to xarray, yet I have not seen any real deprecation of rbtrees. Especially when keys are user controlled or sparse, I do not see how xarray is a suitable replacement. Did I miss some discussions there? Or are you just referring to the general recommendation to consider xarray?

Thanks a lot for the series!
David