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.
Link: https://rust-unofficial.github.io/too-many-lists/ [1]
Link: https://lore.kernel.org/rust-for-linux/[email protected]/ [2]
Signed-off-by: Alice Ryhl <[email protected]>
---
Changes in v2:
- Rebase on top of the new allocation APIs.
- Implement Default for List.
- `on_create_list_arc_from_unique` now takes `Pin<&mut Self>`
- from_unique now calls from_pin_unique instead of the other way around
- Add #[inline] markers.
- Use build_assert in pair_from_unique.
- Simplify transmute_from_arc
- Make macros consistently use full paths.
- Many improvements to safety comments.
- Link to v1: https://lore.kernel.org/r/[email protected]
---
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 | 684 +++++++++++++++++++++++++++++++++
rust/kernel/list/arc.rs | 467 ++++++++++++++++++++++
rust/kernel/list/arc_field.rs | 96 +++++
rust/kernel/list/impl_list_item_mod.rs | 204 ++++++++++
5 files changed, 1452 insertions(+)
---
base-commit: 56f64b370612d8967df2c2e0cead805444d4e71a
change-id: 20240221-linked-list-25169a90a4de
Best regards,
--
Alice Ryhl <[email protected]>