Messages in this thread | | | Date | Tue, 02 Apr 2024 12:16:57 +0000 | Subject | [PATCH 0/9] Add Rust linked list for reference counted values | From | Alice Ryhl <> |
| |
This patchset contains a Rust implementation of a doubly-linked list for use with reference counted values. Linked lists are famously hard to implement in Rust [1] given the cyclic nature of the pointers, and indeed, this implementation uses unsafe to get around that.
Linked lists aren't great for cache locality reasons, but it can be hard to avoid them for cases where you need data structures that don't allocate. Most linked lists in Binder are for collections where order matters (usually stacks or queues). There are also a few lists that are just collections, but linked lists are only used for this purpose in cases where the linked list is cold and performance isn't that important. The linked list is chosen over Vec in this case so that I don't have to worry about reducing the capacity of the vector. (Our red/black trees are a much better place to look for improving cache locality of collections in Rust Binder, and the upcoming xarray bindings would help with that.)
Please see the Rust Binder RFC [2] for usage examples.
The linked lists are used all over Rust Binder, but some pointers for where to look for examples:
[PATCH RFC 04/20] rust_binder: add work lists Implements the work lists that store heterogeneous items. Uses the various macros a bunch.
[PATCH RFC 10/20] rust_binder: add death notifications Uses the cursor. Also has objects with multiple prev/next pointer pairs.
[PATCH RFC 15/20] rust_binder: add process freezing Uses the iterator with for loops.
This patchset depends on [3].
Link: https://rust-unofficial.github.io/too-many-lists/ [1] Link: https://lore.kernel.org/rust-for-linux/20231101-rust-binder-v1-0-08ba9197f637@google.com/ [2] Link: https://lore.kernel.org/rust-for-linux/20240311-arc-for-list-v3-0-cba1883c62eb@google.com/ [3] Signed-off-by: Alice Ryhl <aliceryhl@google.com> --- Alice Ryhl (9): rust: list: add ListArc rust: list: add tracking for ListArc rust: list: add struct with prev/next pointers rust: list: add macro for implementing ListItem rust: list: add List rust: list: add iterators rust: list: add cursor rust: list: support heterogeneous lists rust: list: add ListArcField
rust/kernel/lib.rs | 1 + rust/kernel/list.rs | 637 +++++++++++++++++++++++++++++++++ rust/kernel/list/arc.rs | 431 ++++++++++++++++++++++ rust/kernel/list/arc_field.rs | 94 +++++ rust/kernel/list/impl_list_item_mod.rs | 181 ++++++++++ 5 files changed, 1344 insertions(+) --- base-commit: 98ebc2e1c5bd188fd3140a0f812b302bb9c3ad26 change-id: 20240221-linked-list-25169a90a4de
Best regards, -- Alice Ryhl <aliceryhl@google.com>
| |