rust-for-linux.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
* [PATCH 0/6] Red-black tree abstraction needed by Rust Binder
@ 2024-02-05 15:50 mattgilbride
  2024-02-05 15:50 ` [PATCH 1/6] rust: add `container_of!` macro mattgilbride
                   ` (5 more replies)
  0 siblings, 6 replies; 15+ messages in thread
From: mattgilbride @ 2024-02-05 15:50 UTC (permalink / raw)
  To: Miguel Ojeda, Alex Gaynor, Wedson Almeida Filho, Boqun Feng,
	Gary Guo, Björn Roy Baron, Benno Lossin, Andreas Hindborg,
	Alice Ryhl, Greg Kroah-Hartman, Arve Hjønnevåg,
	Todd Kjos, Martijn Coenen, Joel Fernandes, Carlos Llamas,
	Suren Baghdasaryan, Christian Brauner
  Cc: Rob Landley, Davidlohr Bueso, Michel Lespinasse, rust-for-linux,
	linux-kernel, Matt Gilbride, Matt Gilbride

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 `RBTreeIterator`"
    [PATCH RFC 17/20] rust_binder: add oneway spam detection

Users of "rust: rbtree: add `RBTreeIteratorMut`"
    [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>
---
Alice Ryhl (1):
      rust: rbtree: add `RBTree::entry`

Matt Gilbride (1):
      rust: rbtree: add `RBTreeCursor`

Wedson Almeida Filho (4):
      rust: add `container_of!` macro
      rust: rbtree: add red-black tree implementation backed by the C version
      rust: rbtree: add `RBTreeIterator`
      rust: rbtree: add `RBTreeIteratorMut`

 rust/helpers.c        |    7 +
 rust/kernel/lib.rs    |   33 ++
 rust/kernel/rbtree.rs | 1213 +++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 1253 insertions(+)
---
base-commit: 41bccc98fb7931d63d03f326a746ac4d429c1dd3
change-id: 20231205-b4-rbtree-abb1a016f0a0

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


^ permalink raw reply	[flat|nested] 15+ messages in thread

end of thread, other threads:[~2024-02-12  9:56 UTC | newest]

Thread overview: 15+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2024-02-05 15:50 [PATCH 0/6] Red-black tree abstraction needed by Rust Binder mattgilbride
2024-02-05 15:50 ` [PATCH 1/6] rust: add `container_of!` macro mattgilbride
2024-02-09 13:10   ` Alice Ryhl
2024-02-10  8:05   ` Trevor Gross
2024-02-12  9:56     ` Alice Ryhl
2024-02-05 15:50 ` [PATCH 2/6] rust: rbtree: add red-black tree implementation backed by the C version mattgilbride
2024-02-09 13:04   ` Alice Ryhl
2024-02-05 15:50 ` [PATCH 3/6] rust: rbtree: add `RBTreeIterator` mattgilbride
2024-02-09 13:06   ` Alice Ryhl
2024-02-05 15:50 ` [PATCH 4/6] rust: rbtree: add `RBTreeIteratorMut` mattgilbride
2024-02-09 13:06   ` Alice Ryhl
2024-02-05 15:50 ` [PATCH 5/6] rust: rbtree: add `RBTreeCursor` mattgilbride
2024-02-09 13:06   ` Alice Ryhl
2024-02-05 15:50 ` [PATCH 6/6] rust: rbtree: add `RBTree::entry` mattgilbride
2024-02-09 13:07   ` Alice Ryhl

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).