Message-ID: <CAH5fLgjXDOGbmtkhfiytAGVtT7njuiHQsqVcf0hMQtbyeUY-fg@mail.gmail.com>
Date: Mon, 26 Aug 2024 11:56:59 +0200
From: Alice Ryhl <aliceryhl@...gle.com>
To: David Rheinsberg <david@...dahead.eu>
Cc: Matt Gilbride <mattgilbride@...gle.com>, Miguel Ojeda <ojeda@...nel.org>, 
	Alex Gaynor <alex.gaynor@...il.com>, Wedson Almeida Filho <wedsonaf@...il.com>, 
	Boqun Feng <boqun.feng@...il.com>, Gary Guo <gary@...yguo.net>, 
	Björn Roy Baron <bjorn3_gh@...tonmail.com>, 
	Benno Lossin <benno.lossin@...ton.me>, Andreas Hindborg <a.hindborg@...sung.com>, 
	Greg Kroah-Hartman <gregkh@...uxfoundation.org>, Arve Hjønnevåg <arve@...roid.com>, 
	Todd Kjos <tkjos@...roid.com>, Martijn Coenen <maco@...roid.com>, 
	Joel Fernandes <joel@...lfernandes.org>, Carlos Llamas <cmllamas@...gle.com>, 
	Suren Baghdasaryan <surenb@...gle.com>, Christian Brauner <brauner@...nel.org>, Rob Landley <rob@...dley.net>, 
	Davidlohr Bueso <dave@...olabs.net>, Michel Lespinasse <michel@...pinasse.org>, 
	rust-for-linux@...r.kernel.org, linux-kernel@...r.kernel.org
Subject: Re: [PATCH v12 0/5] Red-black tree abstraction needed by Rust Binder

On Mon, Aug 26, 2024 at 11:15 AM David Rheinsberg <david@...dahead.eu> wrote:
>
> 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.

The performance numbers are okay, see the linked RFC for numbers. But
it's a known area of improvement.

For Rust Binder I have an implementation using a fast-path/slow-path
idea where the range allocator is stored in a flat array instead. It
falls back to rb-tree if the number of allocations gets too large.
However the RFC predates this optimization.

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

Ultimately, the reason is that the red/black tree is one of the very
first abstractions that were written in the Rust for Linux project. We
had not yet figured out how to correctly do intrusive structures at
the time, and I have not taken the time to rewrite it with intrusive
support. That said, we do know how to do it now: see the workqueue [1]
and the linked list [2] for examples of how to do intrusive data
structures.

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

Ah yes, the xarray doesn't work for every case. But I believe we can
replace the red/black tree with a hash table instead in those cases.
There are cases where xarray is a good fit, e.g. when the key is a
thread id. Also for the u32 ids of remote nodes, as their values are
controlled by the kernel. But for locally owned nodes, we would want a
hash table instead.

There's only really one case where I don't see any replacement to the
red/black tree, and that is the range allocator. In C Binder, it uses
a complex data structure where the nodes are intertwined between two
rb trees and a linked list. Rust Binder also uses red/black trees
here.

[1]: https://lore.kernel.org/rust-for-linux/20230828104807.1581592-1-aliceryhl@google.com/
[2]: https://lore.kernel.org/all/20240814-linked-list-v5-0-f5f5e8075da0@google.com/

Powered by blists - more mailing lists