rust: rbtree: fix comments referring to Box instead of KBox

Several safety comments in the RBTree implementation still refer to
"Box::from_raw" and "Box::into_raw", but the code actually uses KBox.

rust: rbtree: fix comments referring to Box instead of KBox

Several safety comments in the RBTree implementation still refer to
"Box::from_raw" and "Box::into_raw", but the code actually uses KBox.
These comments were not updated when the implementation transitioned
from using Box to KBox.

Fixes: 8373147ce496 ("rust: treewide: switch to our kernel `Box` type")
Signed-off-by: Charalampos Mitrodimas <[email protected]>
Reviewed-by: Benno Lossin <[email protected]>
Reviewed-by: Alice Ryhl <[email protected]>
Link: https://lore.kernel.org/r/[email protected]
Signed-off-by: Miguel Ojeda <[email protected]>

show more ...

rust: improve lifetimes markup

Improve lifetimes markup; e.g. from:

/// ... 'a ...

to:

/// ... `'a` ...

This will make lifetimes display as code span with Markdown and make it
more consi

rust: improve lifetimes markup

Improve lifetimes markup; e.g. from:

/// ... 'a ...

to:

/// ... `'a` ...

This will make lifetimes display as code span with Markdown and make it
more consistent with rest of the docs.

Link: https://github.com/Rust-for-Linux/linux/issues/1138
Signed-off-by: Borys Tyran <[email protected]>
Link: https://lore.kernel.org/r/[email protected]
[ Reworded and changed Closes tag to Link. - Miguel ]
Signed-off-by: Miguel Ojeda <[email protected]>

show more ...

rust: rbtree: fix overindented list item

Starting with Rust 1.86.0 (to be released 2025-04-03), Clippy will have
a new lint, `doc_overindented_list_items` [1], which catches cases of
overindented li

rust: rbtree: fix overindented list item

Starting with Rust 1.86.0 (to be released 2025-04-03), Clippy will have
a new lint, `doc_overindented_list_items` [1], which catches cases of
overindented list items.

The lint has been added by Yutaro Ohno, based on feedback from the kernel
[2] on a patch that fixed a similar case -- commit 0c5928deada1 ("rust:
block: fix formatting in GenDisk doc").

Clippy reports a few cases in the kernel, apart from the one already
fixed in the commit above. One is this one:

error: doc list item overindented
--> rust/kernel/rbtree.rs:1152:5
|
1152 | /// null, it is a pointer to the root of the [`RBTree`].
| ^^^^ help: try using ` ` (2 spaces)
|
= help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#doc_overindented_list_items
= note: `-D clippy::doc-overindented-list-items` implied by `-D warnings`
= help: to override `-D warnings` add `#[allow(clippy::doc_overindented_list_items)]`

Thus clean it up.

Cc: Yutaro Ohno <[email protected]>
Cc: [email protected] # Needed in 6.12.y and 6.13.y only (Rust is pinned in older LTSs).
Fixes: a335e9591404 ("rust: rbtree: add `RBTree::entry`")
Link: https://github.com/rust-lang/rust-clippy/pull/13711 [1]
Link: https://github.com/rust-lang/rust-clippy/issues/13601 [2]
Reviewed-by: Alice Ryhl <[email protected]>
Reviewed-by: Yutaro Ohno <[email protected]>
Link: https://lore.kernel.org/r/[email protected]
[ There are a few other cases, so updated message. - Miguel ]
Signed-off-by: Miguel Ojeda <[email protected]>

show more ...

rust: rbtree: remove unwrap in asserts

Remove `unwrap` in asserts and replace it with `Option::Some`
matching. By doing it this way, the examples are more
descriptive, so it disambiguates the return

rust: rbtree: remove unwrap in asserts

Remove `unwrap` in asserts and replace it with `Option::Some`
matching. By doing it this way, the examples are more
descriptive, so it disambiguates the return type of
the `get(...)` and `next(...)`, because the `unwrap(...)`
can also be called on `Result`.

Signed-off-by: Daniel Sedlak <[email protected]>
Reviewed-by: Alice Ryhl <[email protected]>
Link: https://lore.kernel.org/r/[email protected]
[ Reworded title slightly. - Miguel ]
Signed-off-by: Miguel Ojeda <[email protected]>

show more ...

rust: treewide: switch to our kernel `Box` type

Now that we got the kernel `Box` type in place, convert all existing
`Box` users to make use of it.

Reviewed-by: Alice Ryhl <[email protected]>
Re

rust: treewide: switch to our kernel `Box` type

Now that we got the kernel `Box` type in place, convert all existing
`Box` users to make use of it.

Reviewed-by: Alice Ryhl <[email protected]>
Reviewed-by: Benno Lossin <[email protected]>
Reviewed-by: Gary Guo <[email protected]>
Signed-off-by: Danilo Krummrich <[email protected]>
Link: https://lore.kernel.org/r/[email protected]
Signed-off-by: Miguel Ojeda <[email protected]>

show more ...

rust: rbtree: fix `SAFETY` comments that should be `# Safety` sections

The tag `SAFETY` is used for safety comments, i.e. `// SAFETY`, while a
`Safety` section is used for safety preconditions in co

rust: rbtree: fix `SAFETY` comments that should be `# Safety` sections

The tag `SAFETY` is used for safety comments, i.e. `// SAFETY`, while a
`Safety` section is used for safety preconditions in code documentation,
i.e. `/// # Safety`.

Fix the three instances recently added in `rbtree` that Clippy would
have normally caught in a public item, so that we can enable checking
of private items in one of the following commits.

Fixes: 98c14e40e07a ("rust: rbtree: add cursor")
Reviewed-by: Trevor Gross <[email protected]>
Reviewed-by: Alice Ryhl <[email protected]>
Tested-by: Gary Guo <[email protected]>
Reviewed-by: Gary Guo <[email protected]>
Link: https://lore.kernel.org/r/[email protected]
Signed-off-by: Miguel Ojeda <[email protected]>

show more ...

rust: avoid `box_uninit_write` feature

Like commit 0903b9e2a46c ("rust: alloc: eschew
`Box<MaybeUninit<T>>::write`"), but for the new `rbtree` and `alloc` code.

That is, `feature(new_uninit)` [1] g

rust: avoid `box_uninit_write` feature

Like commit 0903b9e2a46c ("rust: alloc: eschew
`Box<MaybeUninit<T>>::write`"), but for the new `rbtree` and `alloc` code.

That is, `feature(new_uninit)` [1] got partially stabilized [2]
for Rust 1.82.0 (expected to be released on 2024-10-17), but it
did not include `Box<MaybeUninit<T>>::write`, which got split into
`feature(box_uninit_write)` [3].

To avoid relying on a new unstable feature, rewrite the `write` +
`assume_init` pair manually.

Link: https://github.com/rust-lang/rust/issues/63291 [1]
Link: https://github.com/rust-lang/rust/pull/129401 [2]
Link: https://github.com/rust-lang/rust/issues/129397 [3]
Reviewed-by: Alice Ryhl <[email protected]>
Reviewed-by: Matt Gilbride <[email protected]>
Link: https://lore.kernel.org/r/[email protected]
Signed-off-by: Miguel Ojeda <[email protected]>

show more ...

rust: rbtree: add `RBTree::entry`

This mirrors the entry API [1] from the Rust standard library on
`RBTree`. This API can be used to access the entry at a specific key and
make modifications dependi

rust: rbtree: add `RBTree::entry`

This mirrors the entry API [1] from the Rust standard library on
`RBTree`. This API can be used to access the entry at a specific key and
make modifications depending on whether the key is vacant or occupied.
This API is useful because it can often be used to avoid traversing the
tree multiple times.

This is used by binder to look up and conditionally access or insert a
value, depending on whether it is there or not [2].

Link: https://doc.rust-lang.org/stable/std/collections/btree_map/enum.Entry.html [1]
Link: https://android-review.googlesource.com/c/kernel/common/+/2849906 [2]
Signed-off-by: Alice Ryhl <[email protected]>
Tested-by: Alice Ryhl <[email protected]>
Reviewed-by: Boqun Feng <[email protected]>
Reviewed-by: Benno Lossin <[email protected]>
Signed-off-by: Matt Gilbride <[email protected]>
Link: https://lore.kernel.org/r/[email protected]
Signed-off-by: Miguel Ojeda <[email protected]>

show more ...

rust: rbtree: add cursor

Add a cursor interface to `RBTree`, supporting the following use cases:
- Inspect the current node pointed to by the cursor, inspect/move to
it's neighbors in sort order (

rust: rbtree: add cursor

Add a cursor interface to `RBTree`, supporting the following use cases:
- Inspect the current node pointed to by the cursor, inspect/move to
it's neighbors in sort order (bidirectionally).
- Mutate the tree itself by removing the current node pointed to by the
cursor, or one of its neighbors.

Add functions to obtain a cursor to the tree by key:
- The node with the smallest key
- The node with the largest key
- The node matching the given key, or the one with the next larger key

The cursor abstraction is needed by the binder driver to efficiently
search for nodes and (conditionally) modify them, as well as their
neighbors [1].

Link: https://lore.kernel.org/rust-for-linux/[email protected]/ [1]
Co-developed-by: Alice Ryhl <[email protected]>
Signed-off-by: Alice Ryhl <[email protected]>
Tested-by: Alice Ryhl <[email protected]>
Reviewed-by: Boqun Feng <[email protected]>
Reviewed-by: Benno Lossin <[email protected]>
Signed-off-by: Matt Gilbride <[email protected]>
Link: https://lore.kernel.org/r/[email protected]
Signed-off-by: Miguel Ojeda <[email protected]>

show more ...

rust: rbtree: add mutable iterator

Add mutable Iterator implementation for `RBTree`,
allowing iteration over (key, value) pairs in key order. Only values are
mutable, as mutating keys implies modify

rust: rbtree: add mutable iterator

Add mutable Iterator implementation for `RBTree`,
allowing iteration over (key, value) pairs in key order. Only values are
mutable, as mutating keys implies modifying a node's position in the tree.

Mutable iteration is used by the binder driver during shutdown to
clean up the tree maintained by the "range allocator" [1].

Link: https://lore.kernel.org/rust-for-linux/[email protected]/ [1]
Signed-off-by: Wedson Almeida Filho <[email protected]>
Reviewed-by: Alice Ryhl <[email protected]>
Tested-by: Alice Ryhl <[email protected]>
Reviewed-by: Boqun Feng <[email protected]>
Reviewed-by: Benno Lossin <[email protected]>
Signed-off-by: Matt Gilbride <[email protected]>
Link: https://lore.kernel.org/r/[email protected]
Signed-off-by: Miguel Ojeda <[email protected]>

show more ...

rust: rbtree: add iterator

- Add Iterator implementation for `RBTree`, allowing
iteration over (key, value) pairs in key order.
- Add individual `keys()` and `values()` functions to iterate over k

rust: rbtree: add iterator

- Add Iterator implementation for `RBTree`, allowing
iteration over (key, value) pairs in key order.
- Add individual `keys()` and `values()` functions to iterate over keys
or values alone.
- Update doctests to use iteration instead of explicitly getting items.

Iteration is needed by the binder driver to enumerate all values in a
tree for oneway spam detection [1].

Link: https://lore.kernel.org/rust-for-linux/[email protected]/ [1]
Signed-off-by: Wedson Almeida Filho <[email protected]>
Reviewed-by: Alice Ryhl <[email protected]>
Tested-by: Alice Ryhl <[email protected]>
Reviewed-by: Benno Lossin <[email protected]>
Reviewed-by: Boqun Feng <[email protected]>
Signed-off-by: Matt Gilbride <[email protected]>
Link: https://lore.kernel.org/r/[email protected]
Signed-off-by: Miguel Ojeda <[email protected]>

show more ...

rust: rbtree: add red-black tree implementation backed by the C version

The rust rbtree exposes a map-like interface over keys and values,
backed by the kernel red-black tree implementation. Values

rust: rbtree: add red-black tree implementation backed by the C version

The rust rbtree exposes a map-like interface over keys and values,
backed by the kernel red-black tree implementation. Values can be
inserted, deleted, and retrieved from a `RBTree` by key.

This base abstraction is used by binder to store key/value
pairs and perform lookups, for example the patch
"[PATCH RFC 03/20] rust_binder: add threading support"
in the binder RFC [1].

Link: https://lore.kernel.org/rust-for-linux/[email protected]/ [1]
Signed-off-by: Wedson Almeida Filho <[email protected]>
Reviewed-by: Alice Ryhl <[email protected]>
Tested-by: Alice Ryhl <[email protected]>
Reviewed-by: Boqun Feng <[email protected]>
Reviewed-by: Benno Lossin <[email protected]>
Signed-off-by: Matt Gilbride <[email protected]>
Link: https://lore.kernel.org/r/[email protected]
[ Updated link to docs.kernel.org. - Miguel ]
Signed-off-by: Miguel Ojeda <[email protected]>

show more ...