summaryrefslogtreecommitdiff
path: root/rust/kernel/rbtree.rs
diff options
context:
space:
mode:
authorLinus Torvalds <torvalds@linux-foundation.org>2024-11-26 14:00:26 -0800
committerLinus Torvalds <torvalds@linux-foundation.org>2024-11-26 14:00:26 -0800
commit798bb342e0416d846cf67f4725a3428f39bfb96b (patch)
tree66a4eda8cba9d7c6b0f535bb85760ef8bf3d2a49 /rust/kernel/rbtree.rs
parente68ce9474a1dac72ea9b1eab25bcd7a5b28adc79 (diff)
parentb7ed2b6f4e8d7f64649795e76ee9db67300de8eb (diff)
downloadlwn-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.rs58
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 }
}