Toolchain and infrastructure:
- Add '__rust_helper' annotation to the C helpers.
This is needed to inline these helpers into Rust code.
- Remove imports available via the prelude, treewide.
This was possible thanks to a new lint in Klint that Gary has
implemented -- more Klint-related changes, including initial upstream
support, are coming.
- Deduplicate pin-init flags.
'kernel' crate:
- Add support for calling a function exactly once with the new
'do_once_lite!' macro (and 'OnceLite' type).
Based on this, add 'pr_*_once!' macros to print only once.
- Add 'impl_flags!' macro for defining common bitflags operations:
impl_flags!(
/// Represents multiple permissions.
#[derive(Debug, Clone, Default, Copy, PartialEq, Eq)]
pub struct Permissions(u32);
/// Represents a single permission.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Permission {
/// Read permission.
Read = 1 << 0,
/// Write permission.
Write = 1 << 1,
/// Execute permission.
Execute = 1 << 2,
}
);
let mut f: Permissions = Permission::Read | Permission::Write;
assert!(f.contains(Permission::Read));
assert!(!f.contains(Permission::Execute));
f |= Permission::Execute;
assert!(f.contains(Permission::Execute));
let f2: Permissions = Permission::Write | Permission::Execute;
assert!((f ^ f2).contains(Permission::Read));
assert!(!(f ^ f2).contains(Permission::Write));
- 'bug' module: support 'CONFIG_DEBUG_BUGVERBOSE_DETAILED' in the
'warn_on!' macro in order to show the evaluated condition alongside
the file path:
------------[ cut here ]------------
WARNING: [val == 1] linux/samples/rust/rust_minimal.rs:27 at ...
Modules linked in: rust_minimal(+)
- Add safety module with 'unsafe_precondition_assert!' macro, currently
a wrapper for 'debug_assert!', intended to mark the validation of
safety preconditions where possible:
/// # Safety
///
/// The caller must ensure that `index` is less than `N`.
unsafe fn set_unchecked(&mut self, index: usize, value: T) {
unsafe_precondition_assert!(
index < N,
"set_unchecked() requires index ({index}) < N ({N})"
);
...
}
- Add instructions to 'build_assert!' documentation requesting to
always inline functions when used with function arguments.
- 'ptr' module: replace 'build_assert!' with a 'const' one.
- 'rbtree' module: reduce unsafe blocks on pointer derefs.
- 'transmute' module: implement 'FromBytes' and 'AsBytes' for
inhabited ZSTs, and use it in Nova.
- More treewide replacements of 'c_str!' with C string literals.
'macros' crate:
- Rewrite most procedural macros ('module!', 'concat_idents!',
'#[export]', '#[vtable]', '#[kunit_tests]') to use the 'syn' parsing
library which we introduced last cycle, with better diagnostics.
This also allows to support '#[cfg]' properly in the '#[vtable]'
macro, to support arbitrary types in 'module!' macro (not just an
identifier) and to remove several custom parsing helpers we had.
- Use 'quote!' from the recently vendored 'quote' library and remove
our custom one.
The vendored one also allows us to avoid quoting '"' and '{}' inside
the template anymore and editors can now highlight it. In addition,
it improves robustness as it eliminates the need for string quoting
and escaping.
- Use 'pin_init::zeroed()' to simplify KUnit code.
'pin-init' crate:
- Rewrite all procedural macros ('[pin_]init!', '#[pin_data]',
'#[pinned_drop]', 'derive([Maybe]Zeroable)') to use the 'syn' parsing
library which we introduced last cycle, with better diagnostics.
- Implement 'InPlaceWrite' for '&'static mut MaybeUninit<T>'. This
enables users to use external allocation mechanisms such as
'static_cell'.
- Support tuple structs in 'derive([Maybe]Zeroable)'.
- Support attributes on fields in '[pin_]init!' (such as
'#[cfg(...)]').
- Add a '#[default_error(<type>)]' attribute to '[pin_]init!' to
override the default error (when no '? Error' is specified).
- Support packed structs in '[pin_]init!' with
'#[disable_initialized_field_access]'.
- Remove 'try_[pin_]init!' in favor of merging their feature
with '[pin_]init!'. Update the kernel's own 'try_[pin_]init!'
macros to use the 'default_error' attribute.
- Correct 'T: Sized' bounds to 'T: ?Sized' in the generated
'PinnedDrop' check by '#[pin_data]'.
Documentation:
- Conclude the Rust experiment.
MAINTAINERS:
- Add "RUST [RUST-ANALYZER]" entry for the rust-analyzer support. Tamir
and Jesung will take care of it. They have both been active around it
for a while. The new tree will flow through the Rust one.
- Add Gary as maintainer for "RUST [PIN-INIT]".
- Update Boqun and Tamir emails to their kernel.org accounts.
And a few other cleanups and improvements.
-----BEGIN PGP SIGNATURE-----
iQIzBAABCgAdFiEEPjU5OPd5QIZ9jqqOGXyLc2htIW0FAmmIeIwACgkQGXyLc2ht
IW13gg//ZW9kgIILHRbyLtLA9luNukD75pYigg0sigeKfZq5SIbDVepOtDGIsXId
fJwYme297u81nf+TWySGPKEwCPFX9NNwrN6JiIKTxxkpfIYNd+cA57QN141xm2y4
4+cG0Zw7yj2PitTKl5nzjRr4dfdfG+t63zLa29O4D5XqMtKs+yeawMLmYpNJLcfJ
/RDRt+p/GX84xgP7fFRPi6zG4sD48ZktmLOe2H7st/mQKxjtqXdMVSqKENhdriGm
h6IdKPs38fxA953+xHE1jO+XygbevnBmWD/E+/7ns5nNajoHU8KKkKMUUyzGqcQK
0tgnOW5Pn5zdZ2Tf+CYGEjo04aA1rDtAUTtjr74uGiUtJR63E3TcGaRr1sY9Hye2
tqKC1MVnj+UFzaZw57OJI9s8At6HBz7NXx4ZZ/MrkKp3jaV5BFhz11rWPAF9SM2E
DqMyIXSrKLCeLr1LocizvrTvNQFGQSdmlbnywnJ2PP679JbJsZz714igxTOvdQBt
M4AGRl/BnC6ZUJV3+/cdpRfqUAi0TPYxouphQ5ynm0zuIG0VjCYhSWM/w9k3LiZD
pamQYOVdBCUrIcPyXMyEt6DszZM5qlt+4syCygcYfdr3PklFrTxeqF9mhetEuJRR
UcOEXAdknHFcPFUnMakAYrL9PBnVyb2INsdsRpOj2GTb/neJKPg=
=en99
-----END PGP SIGNATURE-----
Merge tag 'rust-6.20-7.0' of git://git.kernel.org/pub/scm/linux/kernel/git/ojeda/linux
Pull rust updates from Miguel Ojeda:
"Toolchain and infrastructure:
- Add '__rust_helper' annotation to the C helpers
This is needed to inline these helpers into Rust code
- Remove imports available via the prelude, treewide
This was possible thanks to a new lint in Klint that Gary has
implemented -- more Klint-related changes, including initial
upstream support, are coming
- Deduplicate pin-init flags
'kernel' crate:
- Add support for calling a function exactly once with the new
'do_once_lite!' macro (and 'OnceLite' type)
Based on this, add 'pr_*_once!' macros to print only once
- Add 'impl_flags!' macro for defining common bitflags operations:
impl_flags!(
/// Represents multiple permissions.
#[derive(Debug, Clone, Default, Copy, PartialEq, Eq)]
pub struct Permissions(u32);
/// Represents a single permission.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum Permission {
/// Read permission.
Read = 1 << 0,
/// Write permission.
Write = 1 << 1,
/// Execute permission.
Execute = 1 << 2,
}
);
let mut f: Permissions = Permission::Read | Permission::Write;
assert!(f.contains(Permission::Read));
assert!(!f.contains(Permission::Execute));
f |= Permission::Execute;
assert!(f.contains(Permission::Execute));
let f2: Permissions = Permission::Write | Permission::Execute;
assert!((f ^ f2).contains(Permission::Read));
assert!(!(f ^ f2).contains(Permission::Write));
- 'bug' module: support 'CONFIG_DEBUG_BUGVERBOSE_DETAILED' in the
'warn_on!' macro in order to show the evaluated condition alongside
the file path:
------------[ cut here ]------------
WARNING: [val == 1] linux/samples/rust/rust_minimal.rs:27 at ...
Modules linked in: rust_minimal(+)
- Add safety module with 'unsafe_precondition_assert!' macro,
currently a wrapper for 'debug_assert!', intended to mark the
validation of safety preconditions where possible:
/// # Safety
///
/// The caller must ensure that `index` is less than `N`.
unsafe fn set_unchecked(&mut self, index: usize, value: T) {
unsafe_precondition_assert!(
index < N,
"set_unchecked() requires index ({index}) < N ({N})"
);
...
}
- Add instructions to 'build_assert!' documentation requesting to
always inline functions when used with function arguments
- 'ptr' module: replace 'build_assert!' with a 'const' one
- 'rbtree' module: reduce unsafe blocks on pointer derefs
- 'transmute' module: implement 'FromBytes' and 'AsBytes' for
inhabited ZSTs, and use it in Nova
- More treewide replacements of 'c_str!' with C string literals
'macros' crate:
- Rewrite most procedural macros ('module!', 'concat_idents!',
'#[export]', '#[vtable]', '#[kunit_tests]') to use the 'syn'
parsing library which we introduced last cycle, with better
diagnostics
This also allows to support '#[cfg]' properly in the '#[vtable]'
macro, to support arbitrary types in 'module!' macro (not just an
identifier) and to remove several custom parsing helpers we had
- Use 'quote!' from the recently vendored 'quote' library and remove
our custom one
The vendored one also allows us to avoid quoting '"' and '{}'
inside the template anymore and editors can now highlight it. In
addition, it improves robustness as it eliminates the need for
string quoting and escaping
- Use 'pin_init::zeroed()' to simplify KUnit code
'pin-init' crate:
- Rewrite all procedural macros ('[pin_]init!', '#[pin_data]',
'#[pinned_drop]', 'derive([Maybe]Zeroable)') to use the 'syn'
parsing library which we introduced last cycle, with better
diagnostics
- Implement 'InPlaceWrite' for '&'static mut MaybeUninit<T>'. This
enables users to use external allocation mechanisms such as
'static_cell'
- Support tuple structs in 'derive([Maybe]Zeroable)'
- Support attributes on fields in '[pin_]init!' (such as
'#[cfg(...)]')
- Add a '#[default_error(<type>)]' attribute to '[pin_]init!' to
override the default error (when no '? Error' is specified)
- Support packed structs in '[pin_]init!' with
'#[disable_initialized_field_access]'
- Remove 'try_[pin_]init!' in favor of merging their feature with
'[pin_]init!'. Update the kernel's own 'try_[pin_]init!' macros to
use the 'default_error' attribute
- Correct 'T: Sized' bounds to 'T: ?Sized' in the generated
'PinnedDrop' check by '#[pin_data]'
Documentation:
- Conclude the Rust experiment
MAINTAINERS:
- Add "RUST [RUST-ANALYZER]" entry for the rust-analyzer support.
Tamir and Jesung will take care of it. They have both been active
around it for a while. The new tree will flow through the Rust one
- Add Gary as maintainer for "RUST [PIN-INIT]"
- Update Boqun and Tamir emails to their kernel.org accounts
And a few other cleanups and improvements"
* tag 'rust-6.20-7.0' of git://git.kernel.org/pub/scm/linux/kernel/git/ojeda/linux: (59 commits)
rust: safety: introduce `unsafe_precondition_assert!` macro
rust: add `impl_flags!` macro for defining common bitflag operations
rust: print: Add pr_*_once macros
rust: bug: Support DEBUG_BUGVERBOSE_DETAILED option
rust: print: Add support for calling a function exactly once
rust: kbuild: deduplicate pin-init flags
gpu: nova-core: remove imports available via prelude
rust: clk: replace `kernel::c_str!` with C-Strings
MAINTAINERS: Update my email address to @kernel.org
rust: macros: support `#[cfg]` properly in `#[vtable]` macro.
rust: kunit: use `pin_init::zeroed` instead of custom null value
rust: macros: rearrange `#[doc(hidden)]` in `module!` macro
rust: macros: allow arbitrary types to be used in `module!` macro
rust: macros: convert `#[kunit_tests]` macro to use `syn`
rust: macros: convert `concat_idents!` to use `syn`
rust: macros: convert `#[export]` to use `syn`
rust: macros: use `quote!` for `module!` macro
rust: macros: use `syn` to parse `module!` macro
rust: macros: convert `#[vtable]` macro to use `syn`
rust: macros: use `quote!` from vendored crate
...
Refactors parts of the get() and find_best_match()
traversal logic to minimize the scope of unsafe blocks
and avoid duplicating same safety comments.
One of the removed comments was also misleading:
// SAFETY: `node` is a non-null node...
Ordering::Equal => return Some(unsafe { &(*this).value }),
as `node` should have been `this`.
No functional changes intended; this is purely a safety
improvement that reduces the amount of unsafe blocks
while keeping all invariants intact.
[ Alice writes:
"One consequence of creating a &_ to the bindings::rb_node struct means
that we assert immutability for the entire struct and not just the
rb_left/rb_right fields, but I have verified that this is ok."
- Miguel ]
Signed-off-by: Onur Özkan <work@onurozkan.dev>
Reviewed-by: Charalampos Mitrodimas <charmitro@posteo.net>
Reviewed-by: Alice Ryhl <aliceryhl@google.com>
Link: https://patch.msgid.link/20251113144547.502-1-work@onurozkan.dev
[ Reworded title and replaced `cursor_lower_bound()` with
`find_best_match()` in message. - Miguel ]
Signed-off-by: Miguel Ojeda <ojeda@kernel.org>
The peek_next method's doc comment incorrectly stated it accesses the
"previous" node when it actually accesses the next node.
Fix the documentation to accurately reflect the method's behavior.
Fixes: 98c14e40e0 ("rust: rbtree: add cursor")
Reviewed-by: Alice Ryhl <aliceryhl@google.com>
Signed-off-by: Hang Shu <m18080292938@163.com>
Reported-by: Miguel Ojeda <ojeda@kernel.org>
Closes: https://github.com/Rust-for-Linux/linux/issues/1205
Cc: stable@vger.kernel.org
Reviewed-by: Gary Guo <gary@garyguo.net>
Link: https://patch.msgid.link/20251107093921.3379954-1-m18080292938@163.com
[ Reworded slightly. - Miguel ]
Signed-off-by: Miguel Ojeda <ojeda@kernel.org>
Fix a typo in a comment to improve clarity and readability.
Suggested-by: Miguel Ojeda <ojeda@kernel.org>
Link: https://github.com/Rust-for-Linux/linux/issues/1206
Signed-off-by: Atharv Dubey <atharvd440@gmail.com>
Reviewed-by: Alice Ryhl <aliceryhl@google.com>
Link: https://patch.msgid.link/20251201165601.31484-1-atharvd440@gmail.com
[ Removed one of the cases that is gone now. Reworded accordingly
(and to avoid mentioning 'documentation', since it is just
a comment). - Miguel ]
Signed-off-by: Miguel Ojeda <ojeda@kernel.org>
Sometimes we may need to iterate over, or find an element in a read
only (or read mostly) red-black tree, and in that case we don't need a
mutable reference to the tree, which we'll however have to take to be
able to use the current (mutable) cursor implementation.
This patch adds a simple immutable cursor implementation to RBTree,
which enables us to use an immutable tree reference. The existing
(fully featured) cursor implementation is renamed to CursorMut,
while retaining its functionality.
The only existing user of the [mutable] cursor for RBTrees (binder) is
updated to match the changes.
Signed-off-by: Vitaly Wool <vitaly.wool@konsulko.se>
Reviewed-by: Alice Ryhl <aliceryhl@google.com>
Link: https://patch.msgid.link/20251014123339.2492210-1-vitaly.wool@konsulko.se
[ Applied `rustfmt`. Added intra-doc link. Fixed unclosed example.
Fixed docs description. Fixed typo and other formatting nits.
- Miguel ]
Signed-off-by: Miguel Ojeda <ojeda@kernel.org>
The previous version used a verbose `match` to get
`current`, which may be slightly confusing at first
glance.
This change makes it shorter and more clearly expresses
the intent: prefer `next` if available, otherwise fall
back to `prev`.
Signed-off-by: Onur Özkan <work@onurozkan.dev>
Reviewed-by: Alice Ryhl <aliceryhl@google.com>
Reviewed-by: Alexandre Courbot <acourbot@nvidia.com>
Link: https://lore.kernel.org/r/20250708075850.25789-1-work@onurozkan.dev
Signed-off-by: Miguel Ojeda <ojeda@kernel.org>
In Rust Binder I need to be able to determine whether a red/black tree
is empty. Thus, add a method for that operation to replace
rbtree.iter().next().is_none()
This is terrible, so add a method for this purpose. We do not add a
RBTree::len method because computing the number of elements requires
iterating the entire tree, but checking whether it is empty can be done
cheaply.
Signed-off-by: Alice Ryhl <aliceryhl@google.com>
Reviewed-by: Benno Lossin <lossin@kernel.org>
Link: https://lore.kernel.org/r/20250616-rbtree-is-empty-v1-1-61f7cfb012e3@google.com
[ Adjusted title. - Miguel ]
Signed-off-by: Miguel Ojeda <ojeda@kernel.org>
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 <benno.lossin@proton.me>
Reviewed-by: Alice Ryhl <aliceryhl@google.com>
Signed-off-by: Tamir Duberstein <tamird@gmail.com>
Reviewed-by: Andreas Hindborg <a.hindborg@kernel.org>
Link: https://lore.kernel.org/r/20250409-container-of-mutness-v1-1-64f472b94534@gmail.com
Signed-off-by: Miguel Ojeda <ojeda@kernel.org>
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: 8373147ce4 ("rust: treewide: switch to our kernel `Box` type")
Signed-off-by: Charalampos Mitrodimas <charmitro@posteo.net>
Reviewed-by: Benno Lossin <benno.lossin@proton.me>
Reviewed-by: Alice Ryhl <aliceryhl@google.com>
Link: https://lore.kernel.org/r/20250315-rbtree-comment-fixes-v1-1-51f72c420ff0@posteo.net
Signed-off-by: Miguel Ojeda <ojeda@kernel.org>
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 0c5928dead ("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 <yutaro.ono.418@gmail.com>
Cc: stable@vger.kernel.org # Needed in 6.12.y and 6.13.y only (Rust is pinned in older LTSs).
Fixes: a335e95914 ("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 <aliceryhl@google.com>
Reviewed-by: Yutaro Ohno <yutaro.ono.418@gmail.com>
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 <ojeda@kernel.org>
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 <daniel@sedlak.dev>
Reviewed-by: Alice Ryhl <aliceryhl@google.com>
Link: https://lore.kernel.org/r/20241123095033.41240-3-daniel@sedlak.dev
[ Reworded title slightly. - Miguel ]
Signed-off-by: Miguel Ojeda <ojeda@kernel.org>
Now that we got the kernel `Box` type in place, convert all existing
`Box` users to make use of it.
Reviewed-by: Alice Ryhl <aliceryhl@google.com>
Reviewed-by: Benno Lossin <benno.lossin@proton.me>
Reviewed-by: Gary Guo <gary@garyguo.net>
Signed-off-by: Danilo Krummrich <dakr@kernel.org>
Link: https://lore.kernel.org/r/20241004154149.93856-13-dakr@kernel.org
Signed-off-by: Miguel Ojeda <ojeda@kernel.org>
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: 98c14e40e0 ("rust: rbtree: add cursor")
Reviewed-by: Trevor Gross <tmgross@umich.edu>
Reviewed-by: Alice Ryhl <aliceryhl@google.com>
Tested-by: Gary Guo <gary@garyguo.net>
Reviewed-by: Gary Guo <gary@garyguo.net>
Link: https://lore.kernel.org/r/20240904204347.168520-14-ojeda@kernel.org
Signed-off-by: Miguel Ojeda <ojeda@kernel.org>
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 <aliceryhl@google.com>
Tested-by: Alice Ryhl <aliceryhl@google.com>
Reviewed-by: Boqun Feng <boqun.feng@gmail.com>
Reviewed-by: Benno Lossin <benno.lossin@proton.me>
Signed-off-by: Matt Gilbride <mattgilbride@google.com>
Link: https://lore.kernel.org/r/20240822-b4-rbtree-v12-5-014561758a57@google.com
Signed-off-by: Miguel Ojeda <ojeda@kernel.org>
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 <aliceryhl@google.com>
Signed-off-by: Alice Ryhl <aliceryhl@google.com>
Tested-by: Alice Ryhl <aliceryhl@google.com>
Reviewed-by: Boqun Feng <boqun.feng@gmail.com>
Reviewed-by: Benno Lossin <benno.lossin@proton.me>
Signed-off-by: Matt Gilbride <mattgilbride@google.com>
Link: https://lore.kernel.org/r/20240822-b4-rbtree-v12-4-014561758a57@google.com
Signed-off-by: Miguel Ojeda <ojeda@kernel.org>
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/20231101-rust-binder-v1-6-08ba9197f637@google.com/ [1]
Signed-off-by: Wedson Almeida Filho <wedsonaf@gmail.com>
Reviewed-by: Alice Ryhl <aliceryhl@google.com>
Tested-by: Alice Ryhl <aliceryhl@google.com>
Reviewed-by: Boqun Feng <boqun.feng@gmail.com>
Reviewed-by: Benno Lossin <benno.lossin@proton.me>
Signed-off-by: Matt Gilbride <mattgilbride@google.com>
Link: https://lore.kernel.org/r/20240822-b4-rbtree-v12-3-014561758a57@google.com
Signed-off-by: Miguel Ojeda <ojeda@kernel.org>
- 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/20231101-rust-binder-v1-17-08ba9197f637@google.com/ [1]
Signed-off-by: Wedson Almeida Filho <wedsonaf@gmail.com>
Reviewed-by: Alice Ryhl <aliceryhl@google.com>
Tested-by: Alice Ryhl <aliceryhl@google.com>
Reviewed-by: Benno Lossin <benno.lossin@proton.me>
Reviewed-by: Boqun Feng <boqun.feng@gmail.com>
Signed-off-by: Matt Gilbride <mattgilbride@google.com>
Link: https://lore.kernel.org/r/20240822-b4-rbtree-v12-2-014561758a57@google.com
Signed-off-by: Miguel Ojeda <ojeda@kernel.org>
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/20231101-rust-binder-v1-3-08ba9197f637@google.com/ [1]
Signed-off-by: Wedson Almeida Filho <wedsonaf@gmail.com>
Reviewed-by: Alice Ryhl <aliceryhl@google.com>
Tested-by: Alice Ryhl <aliceryhl@google.com>
Reviewed-by: Boqun Feng <boqun.feng@gmail.com>
Reviewed-by: Benno Lossin <benno.lossin@proton.me>
Signed-off-by: Matt Gilbride <mattgilbride@google.com>
Link: https://lore.kernel.org/r/20240822-b4-rbtree-v12-1-014561758a57@google.com
[ Updated link to docs.kernel.org. - Miguel ]
Signed-off-by: Miguel Ojeda <ojeda@kernel.org>
