Messages in this thread | | | Date | Thu, 18 Apr 2024 14:15:39 +0000 | Subject | [PATCH v3 0/5] Red-black tree abstraction needed by Rust Binder | From | 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> --- 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 `RBTreeCursor`
Wedson Almeida Filho (3): 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 | 1 + rust/kernel/rbtree.rs | 1275 +++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 1283 insertions(+) --- base-commit: 768409cff6cc89fe1194da880537a09857b6e4db change-id: 20231205-b4-rbtree-abb1a016f0a0
Best regards, -- Matt Gilbride <mattgilbride@google.com>
| |