linux/rust/kernel/rbtree.rs, branch v6.16

rust: retain pointer mut-ness in `container_of!`

2025-05-28T16:54:09Z

Avoid casting the input pointer to `*const _`, allowing the output pointer to be `*mut` if the input is `*mut`. This allows a number of `*const` to `*mut` conversions to be removed at the cost of slightly worse ergonomics when the macro is used with a reference rather than a pointer; the only example of this was in the macro's own doctest. Reviewed-by: Benno Lossin Reviewed-by: Alice Ryhl Signed-off-by: Tamir Duberstein Reviewed-by: Andreas Hindborg Link: https://lore.kernel.org/r/20250409-container-of-mutness-v1-1-64f472b94534@gmail.com Signed-off-by: Miguel Ojeda

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

2025-03-23T18:43:02Z

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 Reviewed-by: Benno Lossin Reviewed-by: Alice Ryhl Link: https://lore.kernel.org/r/20250315-rbtree-comment-fixes-v1-1-51f72c420ff0@posteo.net Signed-off-by: Miguel Ojeda

rust: improve lifetimes markup

2025-03-08T22:04:38Z

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 Link: https://lore.kernel.org/r/20250207142437.112435-1-borys.tyran@protonmail.com [ Reworded and changed Closes tag to Link. - Miguel ] Signed-off-by: Miguel Ojeda

rust: rbtree: fix overindented list item

2025-02-12T22:26:55Z

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 Cc: stable@vger.kernel.org # 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 Reviewed-by: Yutaro Ohno Link: https://lore.kernel.org/r/20250206232022.599998-1-ojeda@kernel.org [ There are a few other cases, so updated message. - Miguel ] Signed-off-by: Miguel Ojeda

rust: rbtree: remove unwrap in asserts

2025-01-13T22:44:29Z

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 Reviewed-by: Alice Ryhl Link: https://lore.kernel.org/r/20241123095033.41240-3-daniel@sedlak.dev [ Reworded title slightly. - Miguel ] Signed-off-by: Miguel Ojeda

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

2024-10-15T20:56:59Z

Now that we got the kernel `Box` type in place, convert all existing `Box` users to make use of it. Reviewed-by: Alice Ryhl Reviewed-by: Benno Lossin Reviewed-by: Gary Guo Signed-off-by: Danilo Krummrich Link: https://lore.kernel.org/r/20241004154149.93856-13-dakr@kernel.org Signed-off-by: Miguel Ojeda

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

2024-10-07T19:39:05Z

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 Reviewed-by: Alice Ryhl Tested-by: Gary Guo Reviewed-by: Gary Guo Link: https://lore.kernel.org/r/20240904204347.168520-14-ojeda@kernel.org Signed-off-by: Miguel Ojeda

rust: avoid `box_uninit_write` feature

2024-09-04T21:11:31Z

Like commit 0903b9e2a46c ("rust: alloc: eschew `Box>::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>::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 Reviewed-by: Matt Gilbride Link: https://lore.kernel.org/r/20240904144229.18592-1-ojeda@kernel.org Signed-off-by: Miguel Ojeda

rust: rbtree: add `RBTree::entry`

2024-08-31T15:36:20Z

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 Tested-by: Alice Ryhl Reviewed-by: Boqun Feng Reviewed-by: Benno Lossin Signed-off-by: Matt Gilbride Link: https://lore.kernel.org/r/20240822-b4-rbtree-v12-5-014561758a57@google.com Signed-off-by: Miguel Ojeda

rust: rbtree: add cursor

2024-08-31T15:36:20Z

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/20231101-rust-binder-v1-6-08ba9197f637@google.com/ [1] Co-developed-by: Alice Ryhl Signed-off-by: Alice Ryhl Tested-by: Alice Ryhl Reviewed-by: Boqun Feng Reviewed-by: Benno Lossin Signed-off-by: Matt Gilbride Link: https://lore.kernel.org/r/20240822-b4-rbtree-v12-4-014561758a57@google.com Signed-off-by: Miguel Ojeda