diff options
author | Linus Torvalds <torvalds@linux-foundation.org> | 2024-11-26 14:00:26 -0800 |
---|---|---|
committer | Linus Torvalds <torvalds@linux-foundation.org> | 2024-11-26 14:00:26 -0800 |
commit | 798bb342e0416d846cf67f4725a3428f39bfb96b (patch) | |
tree | 66a4eda8cba9d7c6b0f535bb85760ef8bf3d2a49 /rust/kernel/rbtree.rs | |
parent | e68ce9474a1dac72ea9b1eab25bcd7a5b28adc79 (diff) | |
parent | b7ed2b6f4e8d7f64649795e76ee9db67300de8eb (diff) | |
download | lwn-798bb342e0416d846cf67f4725a3428f39bfb96b.tar.gz lwn-798bb342e0416d846cf67f4725a3428f39bfb96b.zip |
Merge tag 'rust-6.13' of https://github.com/Rust-for-Linux/linux
Pull rust updates from Miguel Ojeda:
"Toolchain and infrastructure:
- Enable a series of lints, including safety-related ones, e.g. the
compiler will now warn about missing safety comments, as well as
unnecessary ones. How safety documentation is organized is a
frequent source of review comments, thus having the compiler guide
new developers on where they are expected (and where not) is very
nice.
- Start using '#[expect]': an interesting feature in Rust (stabilized
in 1.81.0) that makes the compiler warn if an expected warning was
_not_ emitted. This is useful to avoid forgetting cleaning up
locally ignored diagnostics ('#[allow]'s).
- Introduce '.clippy.toml' configuration file for Clippy, the Rust
linter, which will allow us to tweak its behaviour. For instance,
our first use cases are declaring a disallowed macro and, more
importantly, enabling the checking of private items.
- Lints-related fixes and cleanups related to the items above.
- Migrate from 'receiver_trait' to 'arbitrary_self_types': to get the
kernel into stable Rust, one of the major pieces of the puzzle is
the support to write custom types that can be used as 'self', i.e.
as receivers, since the kernel needs to write types such as 'Arc'
that common userspace Rust would not. 'arbitrary_self_types' has
been accepted to become stable, and this is one of the steps
required to get there.
- Remove usage of the 'new_uninit' unstable feature.
- Use custom C FFI types. Includes a new 'ffi' crate to contain our
custom mapping, instead of using the standard library 'core::ffi'
one. The actual remapping will be introduced in a later cycle.
- Map '__kernel_{size_t,ssize_t,ptrdiff_t}' to 'usize'/'isize'
instead of 32/64-bit integers.
- Fix 'size_t' in bindgen generated prototypes of C builtins.
- Warn on bindgen < 0.69.5 and libclang >= 19.1 due to a double issue
in the projects, which we managed to trigger with the upcoming
tracepoint support. It includes a build test since some
distributions backported the fix (e.g. Debian -- thanks!). All
major distributions we list should be now OK except Ubuntu non-LTS.
'macros' crate:
- Adapt the build system to be able run the doctests there too; and
clean up and enable the corresponding doctests.
'kernel' crate:
- Add 'alloc' module with generic kernel allocator support and remove
the dependency on the Rust standard library 'alloc' and the
extension traits we used to provide fallible methods with flags.
Add the 'Allocator' trait and its implementations '{K,V,KV}malloc'.
Add the 'Box' type (a heap allocation for a single value of type
'T' that is also generic over an allocator and considers the
kernel's GFP flags) and its shorthand aliases '{K,V,KV}Box'. Add
'ArrayLayout' type. Add 'Vec' (a contiguous growable array type)
and its shorthand aliases '{K,V,KV}Vec', including iterator
support.
For instance, now we may write code such as:
let mut v = KVec::new();
v.push(1, GFP_KERNEL)?;
assert_eq!(&v, &[1]);
Treewide, move as well old users to these new types.
- 'sync' module: add global lock support, including the
'GlobalLockBackend' trait; the 'Global{Lock,Guard,LockedBy}' types
and the 'global_lock!' macro. Add the 'Lock::try_lock' method.
- 'error' module: optimize 'Error' type to use 'NonZeroI32' and make
conversion functions public.
- 'page' module: add 'page_align' function.
- Add 'transmute' module with the existing 'FromBytes' and 'AsBytes'
traits.
- 'block::mq::request' module: improve rendered documentation.
- 'types' module: extend 'Opaque' type documentation and add simple
examples for the 'Either' types.
drm/panic:
- Clean up a series of Clippy warnings.
Documentation:
- Add coding guidelines for lints and the '#[expect]' feature.
- Add Ubuntu to the list of distributions in the Quick Start guide.
MAINTAINERS:
- Add Danilo Krummrich as maintainer of the new 'alloc' module.
And a few other small cleanups and fixes"
* tag 'rust-6.13' of https://github.com/Rust-for-Linux/linux: (82 commits)
rust: alloc: Fix `ArrayLayout` allocations
docs: rust: remove spurious item in `expect` list
rust: allow `clippy::needless_lifetimes`
rust: warn on bindgen < 0.69.5 and libclang >= 19.1
rust: use custom FFI integer types
rust: map `__kernel_size_t` and friends also to usize/isize
rust: fix size_t in bindgen prototypes of C builtins
rust: sync: add global lock support
rust: macros: enable the rest of the tests
rust: macros: enable paste! use from macro_rules!
rust: enable macros::module! tests
rust: kbuild: expand rusttest target for macros
rust: types: extend `Opaque` documentation
rust: block: fix formatting of `kernel::block::mq::request` module
rust: macros: fix documentation of the paste! macro
rust: kernel: fix THIS_MODULE header path in ThisModule doc comment
rust: page: add Rust version of PAGE_ALIGN
rust: helpers: remove unnecessary header includes
rust: exports: improve grammar in commentary
drm/panic: allow verbose version check
...
Diffstat (limited to 'rust/kernel/rbtree.rs')
-rw-r--r-- | rust/kernel/rbtree.rs | 58 |
1 files changed, 33 insertions, 25 deletions
diff --git a/rust/kernel/rbtree.rs b/rust/kernel/rbtree.rs index 25eb36fd1cdc..cb4415a12258 100644 --- a/rust/kernel/rbtree.rs +++ b/rust/kernel/rbtree.rs @@ -7,7 +7,6 @@ //! Reference: <https://docs.kernel.org/core-api/rbtree.html> use crate::{alloc::Flags, bindings, container_of, error::Result, prelude::*}; -use alloc::boxed::Box; use core::{ cmp::{Ord, Ordering}, marker::PhantomData, @@ -497,7 +496,7 @@ impl<K, V> Drop for RBTree<K, V> { // but it is not observable. The loop invariant is still maintained. // SAFETY: `this` is valid per the loop invariant. - unsafe { drop(Box::from_raw(this.cast_mut())) }; + unsafe { drop(KBox::from_raw(this.cast_mut())) }; } } } @@ -764,7 +763,7 @@ impl<'a, K, V> Cursor<'a, K, V> { // point to the links field of `Node<K, V>` objects. let this = unsafe { container_of!(self.current.as_ptr(), Node<K, V>, links) }.cast_mut(); // SAFETY: `this` is valid by the type invariants as described above. - let node = unsafe { Box::from_raw(this) }; + let node = unsafe { KBox::from_raw(this) }; let node = RBTreeNode { node }; // SAFETY: The reference to the tree used to create the cursor outlives the cursor, so // the tree cannot change. By the tree invariant, all nodes are valid. @@ -809,7 +808,7 @@ impl<'a, K, V> Cursor<'a, K, V> { // point to the links field of `Node<K, V>` objects. let this = unsafe { container_of!(neighbor, Node<K, V>, links) }.cast_mut(); // SAFETY: `this` is valid by the type invariants as described above. - let node = unsafe { Box::from_raw(this) }; + let node = unsafe { KBox::from_raw(this) }; return Some(RBTreeNode { node }); } None @@ -884,7 +883,8 @@ impl<'a, K, V> Cursor<'a, K, V> { NonNull::new(neighbor) } - /// SAFETY: + /// # Safety + /// /// - `node` must be a valid pointer to a node in an [`RBTree`]. /// - The caller has immutable access to `node` for the duration of 'b. unsafe fn to_key_value<'b>(node: NonNull<bindings::rb_node>) -> (&'b K, &'b V) { @@ -894,7 +894,8 @@ impl<'a, K, V> Cursor<'a, K, V> { (k, unsafe { &*v }) } - /// SAFETY: + /// # Safety + /// /// - `node` must be a valid pointer to a node in an [`RBTree`]. /// - The caller has mutable access to `node` for the duration of 'b. unsafe fn to_key_value_mut<'b>(node: NonNull<bindings::rb_node>) -> (&'b K, &'b mut V) { @@ -904,7 +905,8 @@ impl<'a, K, V> Cursor<'a, K, V> { (k, unsafe { &mut *v }) } - /// SAFETY: + /// # Safety + /// /// - `node` must be a valid pointer to a node in an [`RBTree`]. /// - The caller has immutable access to the key for the duration of 'b. unsafe fn to_key_value_raw<'b>(node: NonNull<bindings::rb_node>) -> (&'b K, *mut V) { @@ -1035,7 +1037,7 @@ impl<K, V> Iterator for IterRaw<K, V> { /// It contains the memory needed to hold a node that can be inserted into a red-black tree. One /// can be obtained by directly allocating it ([`RBTreeNodeReservation::new`]). pub struct RBTreeNodeReservation<K, V> { - node: Box<MaybeUninit<Node<K, V>>>, + node: KBox<MaybeUninit<Node<K, V>>>, } impl<K, V> RBTreeNodeReservation<K, V> { @@ -1043,7 +1045,7 @@ impl<K, V> RBTreeNodeReservation<K, V> { /// call to [`RBTree::insert`]. pub fn new(flags: Flags) -> Result<RBTreeNodeReservation<K, V>> { Ok(RBTreeNodeReservation { - node: <Box<_> as BoxExt<_>>::new_uninit(flags)?, + node: KBox::new_uninit(flags)?, }) } } @@ -1059,14 +1061,15 @@ impl<K, V> RBTreeNodeReservation<K, V> { /// Initialises a node reservation. /// /// It then becomes an [`RBTreeNode`] that can be inserted into a tree. - pub fn into_node(mut self, key: K, value: V) -> RBTreeNode<K, V> { - self.node.write(Node { - key, - value, - links: bindings::rb_node::default(), - }); - // SAFETY: We just wrote to it. - let node = unsafe { self.node.assume_init() }; + pub fn into_node(self, key: K, value: V) -> RBTreeNode<K, V> { + let node = KBox::write( + self.node, + Node { + key, + value, + links: bindings::rb_node::default(), + }, + ); RBTreeNode { node } } } @@ -1076,7 +1079,7 @@ impl<K, V> RBTreeNodeReservation<K, V> { /// The node is fully initialised (with key and value) and can be inserted into a tree without any /// extra allocations or failure paths. pub struct RBTreeNode<K, V> { - node: Box<Node<K, V>>, + node: KBox<Node<K, V>>, } impl<K, V> RBTreeNode<K, V> { @@ -1088,7 +1091,9 @@ impl<K, V> RBTreeNode<K, V> { /// Get the key and value from inside the node. pub fn to_key_value(self) -> (K, V) { - (self.node.key, self.node.value) + let node = KBox::into_inner(self.node); + + (node.key, node.value) } } @@ -1110,7 +1115,7 @@ impl<K, V> RBTreeNode<K, V> { /// may be freed (but only for the key/value; memory for the node itself is kept for reuse). pub fn into_reservation(self) -> RBTreeNodeReservation<K, V> { RBTreeNodeReservation { - node: Box::drop_contents(self.node), + node: KBox::drop_contents(self.node), } } } @@ -1161,7 +1166,7 @@ impl<'a, K, V> RawVacantEntry<'a, K, V> { /// The `node` must have a key such that inserting it here does not break the ordering of this /// [`RBTree`]. fn insert(self, node: RBTreeNode<K, V>) -> &'a mut V { - let node = Box::into_raw(node.node); + let node = KBox::into_raw(node.node); // SAFETY: `node` is valid at least until we call `Box::from_raw`, which only happens when // the node is removed or replaced. @@ -1235,21 +1240,24 @@ impl<'a, K, V> OccupiedEntry<'a, K, V> { // SAFETY: The node was a node in the tree, but we removed it, so we can convert it // back into a box. node: unsafe { - Box::from_raw(container_of!(self.node_links, Node<K, V>, links).cast_mut()) + KBox::from_raw(container_of!(self.node_links, Node<K, V>, links).cast_mut()) }, } } /// Takes the value of the entry out of the map, and returns it. pub fn remove(self) -> V { - self.remove_node().node.value + let rb_node = self.remove_node(); + let node = KBox::into_inner(rb_node.node); + + node.value } /// Swap the current node for the provided node. /// /// The key of both nodes must be equal. fn replace(self, node: RBTreeNode<K, V>) -> RBTreeNode<K, V> { - let node = Box::into_raw(node.node); + let node = KBox::into_raw(node.node); // SAFETY: `node` is valid at least until we call `Box::from_raw`, which only happens when // the node is removed or replaced. @@ -1265,7 +1273,7 @@ impl<'a, K, V> OccupiedEntry<'a, K, V> { // - `self.node_ptr` produces a valid pointer to a node in the tree. // - Now that we removed this entry from the tree, we can convert the node to a box. let old_node = - unsafe { Box::from_raw(container_of!(self.node_links, Node<K, V>, links).cast_mut()) }; + unsafe { KBox::from_raw(container_of!(self.node_links, Node<K, V>, links).cast_mut()) }; RBTreeNode { node: old_node } } |