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/20231101-rust-binder-v1-0-08ba9197f637@google.com/ [2]
Signed-off-by: Alice Ryhl <aliceryhl@google.com>
---
Changes in v5:
- Reword: "must not change implementation" -> "must not change behavior".
- Fix mixup between zeroed and uninit.
- Now all patches have a Reviewed-by from Benno.
- Link to v4: https://lore.kernel.org/r/20240806-linked-list-v4-0-23efc510ec92@google.com

Changes in v4:
- Support several impl blocks inside `impl_list_item!`.
- Link to v3: https://lore.kernel.org/r/20240723-linked-list-v3-0-89db92c7dbf4@google.com

Changes in v3:
- Add `assert_pinned!` macro and use it to ensure that the field is
  structurally pinned when using the tracked_by strategy.
- Improve ListArcSafe docs.
- Use From trait for UniqueArc->ListArc conversions.
- Implement AsRef<Arc> for ListArc.
- Improve safety documentation related to ListItem.
- Improve invariants of List.
- Other minor docs improvements.
- Add Reviewed-by tags
- Link to v2: https://lore.kernel.org/r/20240506-linked-list-v2-0-7b910840c91f@google.com

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/20240402-linked-list-v1-0-b1c59ba7ae3b@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

Benno Lossin (1):
      rust: init: add `assert_pinned` macro

 rust/kernel/init.rs                    |  67 ++++
 rust/kernel/init/__internal.rs         |  29 ++
 rust/kernel/lib.rs                     |   1 +
 rust/kernel/list.rs                    | 686 +++++++++++++++++++++++++++++++++
 rust/kernel/list/arc.rs                | 521 +++++++++++++++++++++++++
 rust/kernel/list/arc_field.rs          |  96 +++++
 rust/kernel/list/impl_list_item_mod.rs | 274 +++++++++++++
 7 files changed, 1674 insertions(+)
---
base-commit: 7c626ce4bae1ac14f60076d00eafe71af30450ba
change-id: 20240221-linked-list-25169a90a4de

Best regards,
-- 
Alice Ryhl <aliceryhl@google.com>

On Wed, Aug 14, 2024 at 10:06 AM Alice Ryhl <aliceryhl@google.com> wrote:
>
> 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/20231101-rust-binder-v1-0-08ba9197f637@google.com/ [2]
> Signed-off-by: Alice Ryhl <aliceryhl@google.com>

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

    [ Replaced `compile_fail` with `ignore` and a TODO note. Removed
      `pub` from example to clean `unreachable_pub` lint. - Miguel ]

    [ Fixed a few typos. - Miguel ]

Cheers,
Miguel