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

Link: https://lore.kernel.org/rust-for-linux/20231101-rust-binder-v1-0-08ba9197f637@google.com/ [1]
Signed-off-by: Matt Gilbride <mattgilbride@google.com>
---
Changes in v12:
- Address feedback from v11 (superfluous INVARIANT comments in patch 4)
- Link to v11: https://lore.kernel.org/r/20240821-b4-rbtree-v11-0-2ddc66f26972@google.com

Changes in v11:
- Address feedback from v10
- Link to v10: https://lore.kernel.org/r/20240819-b4-rbtree-v10-0-3b3b2c4d73af@google.com

Changes in v10:
- Rebase on top of rust-for-linux/rust-next (e26fa546042add70944d018b930530d16b3cf626)
  - Adapt to changes from "rust: kbuild: split up helpers.c"
    (876346536c1b59a5b1b5e44477b1b3ece77647fd)
- Rebase on top of "rust: kernel: add `drop_contents` to `BoxExt`" instead of including it in the patch series
  - https://lore.kernel.org/all/CAH5fLgj2urZ6OD2ki6E=6EuPqW3Z8BGg8jd6Bgo4OOrNiptnDw@mail.gmail.com/
- Link to v9: https://lore.kernel.org/r/20240816-b4-rbtree-v9-0-425b442af7e5@google.com

Changes in v9:
- Rebase on top of Linux 6.11-rc2
- Address feedback from v8
- Link to v8: https://lore.kernel.org/r/20240727-b4-rbtree-v8-0-951600ada434@google.com

Changes in v8:
- Fix small style nit (use ? operator)
- Fix doc comment pointing at a private item
- Link to v7: https://lore.kernel.org/r/20240726-b4-rbtree-v7-0-aee88caaf97c@google.com

Changes in v7:
- make `RawVacantEntry.rbtree` a raw pointer like
  `RawVacantEntry.child_field_of_parent`, since the latter can
  technically point at a field of the former. We prefer that the
  implementation be explicit about the safety guarantees of both because
  of the relationship between them.
- Link to v6: https://lore.kernel.org/r/20240711-b4-rbtree-v6-0-14bef1a8cdba@google.com

Changes in v6:
- Minimize usage of `*mut bindings::rb_node`, replacing with
  `NonNull<bindings::rb_node>`. Specifically, changing
  `RBTreeCursor.current` to be `NonNull<bindings::rb_node>` and updating
  the corresponding functions.
- Update `RBTreeCursor:to_key_value` helpers to have their own lifetime
  (they are not instance methods, using a different lifetime than that
  of the `impl` block they are in makes things more clear.
- Fix misplaced semicolon in `cursor_lower_bound`.
- Link to v5: https://lore.kernel.org/r/20240606-b4-rbtree-v5-0-96fe1a0e97c0@google.com

Changes in v5:
- Used `Box::write` in `RBTreeNodeReservation::into_node`, removing
  unnecessary `unsafe` blocks.
- Updated `RBTreeCursor::remove_current` to return the removed node.
- Link to v4: https://lore.kernel.org/r/20240603-b4-rbtree-v4-0-308e43d6abfc@google.com

Changes in v4:
- rebased onto the tip of rust-for-linux/rust-next (97ab3e8eec0ce79d9e265e6c9e4c480492180409)
- addressed comments from draft PR on GitHub: https://github.com/Rust-for-Linux/linux/pull/1081
- Link to v3: https://lore.kernel.org/r/20240418-b4-rbtree-v3-0-323e134390ce@google.com

Changes in v3:
- Address various feedback re: SAFETY and INVARIANT comments from v2.
- Update variable naming and add detailed comments for the `RBTree::insert` (later moved to
  `RBTree::raw_entry`) implementation.
- Link to v2: https://lore.kernel.org/r/20240219-b4-rbtree-v2-0-0b113aab330d@google.com

Changes in v2:
- Update documentation link to the C header file
- Use `core::convert::Infallible` in try_reserve_node
- Link to v1: https://lore.kernel.org/r/20240205-b4-rbtree-v1-0-995e3eee38c0@google.com

---
Alice Ryhl (1):
      rust: rbtree: add `RBTree::entry`

Matt Gilbride (1):
      rust: rbtree: add cursor

Wedson Almeida Filho (3):
      rust: rbtree: add red-black tree implementation backed by the C version
      rust: rbtree: add iterator
      rust: rbtree: add mutable iterator

 rust/helpers/helpers.c |    1 +
 rust/helpers/rbtree.c  |    9 +
 rust/kernel/lib.rs     |    1 +
 rust/kernel/rbtree.rs  | 1279 ++++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 1290 insertions(+)
---
base-commit: 68ad5e31ad2ccab128468e829f53191cf60f601f
change-id: 20231205-b4-rbtree-abb1a016f0a0

Best regards,
-- 
Matt Gilbride <mattgilbride@google.com>

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

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

On Thu, Aug 22, 2024 at 6:38 PM Matt Gilbride <mattgilbride@google.com> wrote:
>
> This patchset contains the red-black tree abstractions needed by the Rust
> implementation of the Binder driver.

Applied to `rust-next` -- thanks everyone!

    [ Updated link to docs.kernel.org. - Miguel ]

Cheers,
Miguel