From nobody Fri Oct 3 05:28:00 2025 Received: from mailrelay-egress16.pub.mailoutpod3-cph3.one.com (mailrelay-egress16.pub.mailoutpod3-cph3.one.com [46.30.212.3]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id D6068308F0F for ; Thu, 4 Sep 2025 14:26:03 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=46.30.212.3 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1756995969; cv=none; b=prd1eoGNFUzIyrLAapOcmpWWJsYHTVol8b4PjCYwkY0G3St1I5cpC8cFx6nwZnYc9m+yEJ2FimwaTnFDNmadyyKI+j0GH8V/TxLowfstY8VyNY9IqYYZi4pmiUmJW1+eNsgQ7fJBGs8rg0m/M5jnoEk9/pwpcyHQOS2S+g0NqZA= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1756995969; c=relaxed/simple; bh=NSjx2Kev6QLNLP6dJARjwbezFbrgKBKumWXcKOCJjDs=; h=From:To:Cc:Subject:Date:Message-Id:MIME-Version; b=UQS/5GB91vAeuz9cJdJ0lDFfWtO14Q0aNGOiKSnU41uxDgkItI6XUQelzXUsd7U80qbhREL1xVoSisgD0ol7a27sub4C+8hMerlX+jOS2Q8YXzm0kmCiihYIcfpFjwhLS5Y7GMa0ch5MAn77e88Rjwmg9aTns/RaaXxLcsKFpr4= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=konsulko.se; spf=none smtp.mailfrom=konsulko.se; dkim=pass (2048-bit key) header.d=konsulko.se header.i=@konsulko.se header.b=aFAskpAk; dkim=permerror (0-bit key) header.d=konsulko.se header.i=@konsulko.se header.b=ph+ktFDK; arc=none smtp.client-ip=46.30.212.3 Authentication-Results: smtp.subspace.kernel.org; dmarc=none (p=none dis=none) header.from=konsulko.se Authentication-Results: smtp.subspace.kernel.org; spf=none smtp.mailfrom=konsulko.se Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=konsulko.se header.i=@konsulko.se header.b="aFAskpAk"; dkim=permerror (0-bit key) header.d=konsulko.se header.i=@konsulko.se header.b="ph+ktFDK" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; t=1756995962; x=1757600762; d=konsulko.se; s=rsa2; h=content-transfer-encoding:mime-version:message-id:date:subject:cc:to:from: from; bh=deQn3/3HdV7iulRd1+fiM17FbXQhI4PmGc3et3kdUHs=; b=aFAskpAkSTkWoaDGAL364lHzPBDRn5nuzGVAmI7K+FEV76J1RPU0R+YCuiBE7JXGE8EjBdKI22ujU 9LPcCY7kKqVyp+hQrQ8uVFD7293hKFt28FxMSj/1PPZJe/fNCA8dXkfqSjzhFVrFsgsfKV+FnDvmQf YQAxZi+Aq3NmBjYKklnIZZAXH4QJC5exm5InkPc6rXrOsqYJVGsGIY2I7x6OvSYQQRQHee8YW6tir9 lVgm/ksZNfL6O2aUMnfTfCkfI/XaKuK5G9TRknIwHzfnJsKCNhGweuzgrb1OnGvCdnJmv9YvF2iOPn kkkzN3tuh+G3mkxHYWUvD+Y5dxmyI7w== DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; t=1756995962; x=1757600762; d=konsulko.se; s=ed2; h=content-transfer-encoding:mime-version:message-id:date:subject:cc:to:from: from; bh=deQn3/3HdV7iulRd1+fiM17FbXQhI4PmGc3et3kdUHs=; b=ph+ktFDK3BtMLMf6LmZNPFGSKThKnnrw09l3j2JhaTxaoXbD1CFYeZ0/9tDrFxd+NZC6l1laCAGhJ FmzWNo/AA== X-HalOne-ID: 148fa465-899b-11f0-8ae3-632fe8569f3f Received: from localhost.localdomain (host-95-203-16-218.mobileonline.telia.com [95.203.16.218]) by mailrelay2.pub.mailoutpod3-cph3.one.com (Halon) with ESMTPSA id 148fa465-899b-11f0-8ae3-632fe8569f3f; Thu, 04 Sep 2025 14:26:01 +0000 (UTC) From: Vitaly Wool To: rust-for-linux@vger.kernel.org Cc: linux-kernel@vger.kernel.org, Danilo Krummrich , Alice Ryhl , Alex Gaynor , Boqun Feng , Gary Guo , Bjorn Roy Baron , Benno Lossin , Andreas Hindborg , Trevor Gross , =?UTF-8?q?Onur=20=C3=96zkan?= , Vitaly Wool Subject: [PATCH] rust: rbtree: add immutable cursor Date: Thu, 4 Sep 2025 16:25:52 +0200 Message-Id: <20250904142552.2790602-1-vitaly.wool@konsulko.se> X-Mailer: git-send-email 2.39.2 Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Content-Type: text/plain; charset="utf-8" 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. Signed-off-by: Vitaly Wool --- rust/kernel/rbtree.rs | 241 +++++++++++++++++++++++++++++++++++++----- 1 file changed, 217 insertions(+), 24 deletions(-) diff --git a/rust/kernel/rbtree.rs b/rust/kernel/rbtree.rs index b8fe6be6fcc4..3b96d4a24217 100644 --- a/rust/kernel/rbtree.rs +++ b/rust/kernel/rbtree.rs @@ -11,7 +11,7 @@ cmp::{Ord, Ordering}, marker::PhantomData, mem::MaybeUninit, - ptr::{addr_of_mut, from_mut, NonNull}, + ptr::{addr_of, addr_of_mut, from_mut, NonNull}, }; =20 /// A red-black tree with owned nodes. @@ -243,34 +243,64 @@ pub fn values_mut(&mut self) -> impl Iterator { } =20 /// Returns a cursor over the tree nodes, starting with the smallest k= ey. - pub fn cursor_front(&mut self) -> Option> { + pub fn cursor_front_mut(&mut self) -> Option> { let root =3D addr_of_mut!(self.root); // SAFETY: `self.root` is always a valid root node let current =3D unsafe { bindings::rb_first(root) }; NonNull::new(current).map(|current| { // INVARIANT: // - `current` is a valid node in the [`RBTree`] pointed to by= `self`. - Cursor { + CursorMut { current, tree: self, } }) } =20 + /// Returns an unmutable cursor over the tree nodes, starting with the= smallest key. + pub fn cursor_front(&self) -> Option> { + let root =3D addr_of!(self.root); + // SAFETY: `self.root` is always a valid root node + let current =3D unsafe { bindings::rb_first(root) }; + NonNull::new(current).map(|current| { + // INVARIANT: + // - `current` is a valid node in the [`RBTree`] pointed to by= `self`. + Cursor { + current, + _tree: PhantomData, + } + }) + } + /// Returns a cursor over the tree nodes, starting with the largest ke= y. - pub fn cursor_back(&mut self) -> Option> { + pub fn cursor_back_mut(&mut self) -> Option> { let root =3D addr_of_mut!(self.root); // SAFETY: `self.root` is always a valid root node let current =3D unsafe { bindings::rb_last(root) }; NonNull::new(current).map(|current| { // INVARIANT: // - `current` is a valid node in the [`RBTree`] pointed to by= `self`. - Cursor { + CursorMut { current, tree: self, } }) } + + /// Returns a cursor over the tree nodes, starting with the largest ke= y. + pub fn cursor_back(&self) -> Option> { + let root =3D addr_of!(self.root); + // SAFETY: `self.root` is always a valid root node + let current =3D unsafe { bindings::rb_last(root) }; + NonNull::new(current).map(|current| { + // INVARIANT: + // - `current` is a valid node in the [`RBTree`] pointed to by= `self`. + Cursor { + current, + _tree: PhantomData, + } + }) + } } =20 impl RBTree @@ -421,7 +451,7 @@ pub fn remove(&mut self, key: &K) -> Option { /// If the given key exists, the cursor starts there. /// Otherwise it starts with the first larger key in sort order. /// If there is no larger key, it returns [`None`]. - pub fn cursor_lower_bound(&mut self, key: &K) -> Option> + pub fn cursor_lower_bound_mut(&mut self, key: &K) -> Option> where K: Ord, { @@ -470,12 +500,74 @@ pub fn cursor_lower_bound(&mut self, key: &K) -> Opti= on> NonNull::new(links).map(|current| { // INVARIANT: // - `current` is a valid node in the [`RBTree`] pointed to by= `self`. - Cursor { + CursorMut { current, tree: self, } }) } + + /// Returns a cursor over the tree nodes based on the given key. + /// + /// If the given key exists, the cursor starts there. + /// Otherwise it starts with the first larger key in sort order. + /// If there is no larger key, it returns [`None`]. + pub fn cursor_lower_bound(&self, key: &K) -> Option> + where + K: Ord, + { + let mut node =3D self.root.rb_node; + let mut best_match: Option>> =3D None; + while !node.is_null() { + // SAFETY: By the type invariant of `Self`, all non-null `rb_n= ode` pointers stored in + // `self` point to the links field of `Node` objects. + let this =3D unsafe { container_of!(node, Node, links) }; + // SAFETY: `this` is a non-null node so it is valid by the typ= e invariants. + let this_key =3D unsafe { &(*this).key }; + // SAFETY: `node` is a non-null node so it is valid by the typ= e invariants. + let left_child =3D unsafe { (*node).rb_left }; + // SAFETY: `node` is a non-null node so it is valid by the typ= e invariants. + let right_child =3D unsafe { (*node).rb_right }; + match key.cmp(this_key) { + Ordering::Equal =3D> { + best_match =3D NonNull::new(this); + break; + } + Ordering::Greater =3D> { + node =3D right_child; + } + Ordering::Less =3D> { + let is_better_match =3D match best_match { + None =3D> true, + Some(best) =3D> { + // SAFETY: `best` is a non-null node so it is = valid by the type + // invariants. + let best_key =3D unsafe { &(*best.as_ptr()).ke= y }; + best_key > this_key + } + }; + if is_better_match { + best_match =3D NonNull::new(this); + } + node =3D left_child; + } + }; + } + + let best =3D best_match?; + + // SAFETY: `best` is a non-null node so it is valid by the type in= variants. + let links =3D unsafe { addr_of_mut!((*best.as_ptr()).links) }; + + NonNull::new(links).map(|current| { + // INVARIANT: + // - `current` is a valid node in the [`RBTree`] pointed to by= `self`. + Cursor { + current, + _tree: PhantomData, + } + }) + } } =20 impl Default for RBTree { @@ -507,7 +599,7 @@ fn drop(&mut self) { } } =20 -/// A bidirectional cursor over the tree nodes, sorted by key. +/// A bidirectional mutable cursor over the tree nodes, sorted by key. /// /// # Examples /// @@ -526,7 +618,7 @@ fn drop(&mut self) { /// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?; /// /// // Get a cursor to the first element. -/// let mut cursor =3D tree.cursor_front().unwrap(); +/// let mut cursor =3D tree.cursor_front_mut().unwrap(); /// let mut current =3D cursor.current(); /// assert_eq!(current, (&10, &100)); /// @@ -564,7 +656,7 @@ fn drop(&mut self) { /// tree.try_create_and_insert(20, 200, flags::GFP_KERNEL)?; /// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?; /// -/// let mut cursor =3D tree.cursor_back().unwrap(); +/// let mut cursor =3D tree.cursor_back_mut().unwrap(); /// let current =3D cursor.current(); /// assert_eq!(current, (&30, &300)); /// @@ -577,7 +669,7 @@ fn drop(&mut self) { /// use kernel::rbtree::RBTree; /// /// let mut tree: RBTree =3D RBTree::new(); -/// assert!(tree.cursor_front().is_none()); +/// assert!(tree.cursor_front_mut().is_none()); /// /// # Ok::<(), Error>(()) /// ``` @@ -628,7 +720,7 @@ fn drop(&mut self) { /// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?; /// /// // Retrieve a cursor. -/// let mut cursor =3D tree.cursor_front().unwrap(); +/// let mut cursor =3D tree.cursor_front_mut().unwrap(); /// /// // Get a mutable reference to the current value. /// let (k, v) =3D cursor.current_mut(); @@ -655,7 +747,7 @@ fn drop(&mut self) { /// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?; /// /// // Remove the first element. -/// let mut cursor =3D tree.cursor_front().unwrap(); +/// let mut cursor =3D tree.cursor_front_mut().unwrap(); /// let mut current =3D cursor.current(); /// assert_eq!(current, (&10, &100)); /// cursor =3D cursor.remove_current().0.unwrap(); @@ -665,7 +757,7 @@ fn drop(&mut self) { /// assert_eq!(current, (&20, &200)); /// /// // Get a cursor to the last element, and remove it. -/// cursor =3D tree.cursor_back().unwrap(); +/// cursor =3D tree.cursor_back_mut().unwrap(); /// current =3D cursor.current(); /// assert_eq!(current, (&30, &300)); /// @@ -694,7 +786,7 @@ fn drop(&mut self) { /// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?; /// /// // Get a cursor to the first element. -/// let mut cursor =3D tree.cursor_front().unwrap(); +/// let mut cursor =3D tree.cursor_front_mut().unwrap(); /// let mut current =3D cursor.current(); /// assert_eq!(current, (&10, &100)); /// @@ -702,7 +794,7 @@ fn drop(&mut self) { /// assert!(cursor.remove_prev().is_none()); /// /// // Get a cursor to the last element. -/// cursor =3D tree.cursor_back().unwrap(); +/// cursor =3D tree.cursor_back_mut().unwrap(); /// current =3D cursor.current(); /// assert_eq!(current, (&30, &300)); /// @@ -726,19 +818,51 @@ fn drop(&mut self) { /// /// # Invariants /// - `current` points to a node that is in the same [`RBTree`] as `tree`. -pub struct Cursor<'a, K, V> { +pub struct CursorMut<'a, K, V> { tree: &'a mut RBTree, current: NonNull, } =20 -// SAFETY: The [`Cursor`] has exclusive access to both `K` and `V`, so it = is sufficient to require them to be `Send`. -// The cursor only gives out immutable references to the keys, but since i= t has excusive access to those same -// keys, `Send` is sufficient. `Sync` would be okay, but it is more restri= ctive to the user. -unsafe impl<'a, K: Send, V: Send> Send for Cursor<'a, K, V> {} +/// A bidirectional unmutable cursor over the tree nodes, sorted by key. T= his is a simpler +/// variant of CursorMut that is basically providing read only access. +/// +/// # Examples +/// +/// In the following example, we obtain a cursor to the first element in t= he tree. +/// The cursor allows us to iterate bidirectionally over key/value pairs i= n the tree. +/// +/// ``` +/// use kernel::{alloc::flags, rbtree::RBTree}; +/// +/// // Create a new tree. +/// let mut tree =3D RBTree::new(); +/// +/// // Insert three elements. +/// tree.try_create_and_insert(10, 100, flags::GFP_KERNEL)?; +/// tree.try_create_and_insert(20, 200, flags::GFP_KERNEL)?; +/// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?; +/// +/// // Get a cursor to the first element. +/// let cursor =3D tree.cursor_front().unwrap(); +/// let current =3D cursor.current(); +/// assert_eq!(current, (&10, &100)); +/// +/// # Ok::<(), Error>(()) +pub struct Cursor<'a, K, V> { + _tree: PhantomData<&'a RBTree>, + current: NonNull, +} + +// SAFETY: The [`CursorMut`] has exclusive access to both `K` and `V`, so = it is sufficient to +// require them to be `Send`. +// The cursor only gives out immutable references to the keys, but since i= t has excusive access to +// those same keys, `Send` is sufficient. `Sync` would be okay, but it is = more restrictive to the +// user. +unsafe impl<'a, K: Send, V: Send> Send for CursorMut<'a, K, V> {} =20 -// SAFETY: The [`Cursor`] gives out immutable references to K and mutable = references to V, +// SAFETY: The [`CursorMut`] gives out immutable references to K and mutab= le references to V, // so it has the same thread safety requirements as mutable references. -unsafe impl<'a, K: Sync, V: Sync> Sync for Cursor<'a, K, V> {} +unsafe impl<'a, K: Sync, V: Sync> Sync for CursorMut<'a, K, V> {} =20 impl<'a, K, V> Cursor<'a, K, V> { /// The current node @@ -749,6 +873,75 @@ pub fn current(&self) -> (&K, &V) { unsafe { Self::to_key_value(self.current) } } =20 + /// # 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) -> (&'b K= , &'b V) { + // SAFETY: the caller guarantees that `node` is a valid pointer in= an `RBTree`. + let (k, v) =3D unsafe { Self::to_key_value_raw(node) }; + // SAFETY: the caller guarantees immutable access to `node`. + (k, unsafe { &*v }) + } + + /// # 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) -> (&= 'b K, *mut V) { + // SAFETY: By the type invariant of `Self`, all non-null `rb_node`= pointers stored in `self` + // point to the links field of `Node` objects. + let this =3D unsafe { container_of!(node.as_ptr(), Node, lin= ks) }; + // SAFETY: The passed `node` is the current node or a non-null nei= ghbor, + // thus `this` is valid by the type invariants. + let k =3D unsafe { &(*this).key }; + // SAFETY: The passed `node` is the current node or a non-null nei= ghbor, + // thus `this` is valid by the type invariants. + let v =3D unsafe { addr_of_mut!((*this).value) }; + (k, v) + } + + /// Access the previous node without moving the cursor. + pub fn peek_prev(&self) -> Option<(&K, &V)> { + self.peek(Direction::Prev) + } + + /// Access the previous node without moving the cursor. + pub fn peek_next(&self) -> Option<(&K, &V)> { + self.peek(Direction::Next) + } + + fn peek(&self, direction: Direction) -> Option<(&K, &V)> { + self.get_neighbor_raw(direction).map(|neighbor| { + // SAFETY: + // - `neighbor` is a valid tree node. + // - By the function signature, we have an immutable reference= to `self`. + unsafe { Self::to_key_value(neighbor) } + }) + } + + fn get_neighbor_raw(&self, direction: Direction) -> Option> { + // SAFETY: `self.current` is valid by the type invariants. + let neighbor =3D unsafe { + match direction { + Direction::Prev =3D> bindings::rb_prev(self.current.as_ptr= ()), + Direction::Next =3D> bindings::rb_next(self.current.as_ptr= ()), + } + }; + + NonNull::new(neighbor) + } +} + +impl<'a, K, V> CursorMut<'a, K, V> { + /// The current node + pub fn current(&self) -> (&K, &V) { + // SAFETY: + // - `self.current` is a valid node by the type invariants. + // - We have an immutable reference by the function signature. + unsafe { Self::to_key_value(self.current) } + } + /// The current node, with a mutable value pub fn current_mut(&mut self) -> (&K, &mut V) { // SAFETY: @@ -920,7 +1113,7 @@ unsafe fn to_key_value_raw<'b>(node: NonNull) -> (&'b K, *mut } } =20 -/// Direction for [`Cursor`] operations. +/// Direction for [`Cursor`] and [`CursorMut`] operations. enum Direction { /// the node immediately before, in sort order Prev, --=20 2.39.2