From nobody Tue Sep 9 21:33:45 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 E06312F546E for ; Mon, 8 Sep 2025 12:53:56 +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=1757336041; cv=none; b=Z6IJoR6iHxT7SQ9HJaoUfyVtE4tpIElk/lIklT8MCPtAjtB53yP7PXKynoizJuJQfGsb4lyUQQ6wIypieomBCbDeUakgbMttv0d4b2XeGI16mL+lc3357NYUF9Ym7GIEck3YE248hP0wUcgKWUmwcQYyfsMUONfSI+92SKAWspc= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1757336041; c=relaxed/simple; bh=iKAmeuBxB3bNnvnYIjcIkoXm6DjZCDgogLrBRYx0E+g=; h=From:To:Cc:Subject:Date:Message-Id:MIME-Version; b=EYijFlFrbCFhwnuFBNX6PdsxVWfogcwRAPKDg6SOUavd1UI594bPoTbqOahscZR3Oo13X7qptnhJv2Q/g48jPwmJAxfw0fulVD1sLcwe7k6lJoLaSakkZxOudYYfd6jRihdqbXrQCvFHnMUKWrnS08Uhelj9DH/dPpzwiWGUrBo= 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=dIXTNaO1; dkim=permerror (0-bit key) header.d=konsulko.se header.i=@konsulko.se header.b=t2DBBgI1; 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="dIXTNaO1"; dkim=permerror (0-bit key) header.d=konsulko.se header.i=@konsulko.se header.b="t2DBBgI1" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; t=1757336029; x=1757940829; d=konsulko.se; s=rsa2; h=content-transfer-encoding:mime-version:message-id:date:subject:cc:to:from: from; bh=Re/adqzdJp9wv8PgBSnhZ6WM0KVHzZkJImFLEzhiYCA=; b=dIXTNaO1m1lVtSQ28PRegbT9Mxb8cZrJgrH1m6I7lw4KkSblJru4Y6aSIYloYdTc6RvOLOah5hb2v HIPnFukaZjgWp+LmEs0WnwIKOTB34gKiOY8AGt+iJEoW8yR1ggqfww8DWRT58h9hkTDifr61NwbMSm TRXStqffKoNTDfBnBZWk/PhRC24wcFKkJugPp9MrhsLjtehZ3ij9oPnx0SCjbDNDglVhe+dtNlmiuR UGPvzINLOioCVJ+VRwhzKkFJXFeVX+2I0fKLF1sMtV8m/AWz0oCGWBEz8wDCRt7n7bdN2ETQ61ZHAr BPdpC9FGUjM6SAWFmt6IbaGIpv7gH8Q== DKIM-Signature: v=1; a=ed25519-sha256; c=relaxed/relaxed; t=1757336029; x=1757940829; d=konsulko.se; s=ed2; h=content-transfer-encoding:mime-version:message-id:date:subject:cc:to:from: from; bh=Re/adqzdJp9wv8PgBSnhZ6WM0KVHzZkJImFLEzhiYCA=; b=t2DBBgI1BbVjg3/SjbOYH+9qh5LDqfa3HllrPo4VR5f71lERSlgGznR8mEhndhOXF1MtQ+PkoDLy1 7tGN1giAQ== X-HalOne-ID: dbe9f07d-8cb2-11f0-9ef2-85eb291bc831 Received: from slottsdator.home (host-95-203-16-218.mobileonline.telia.com [95.203.16.218]) by mailrelay5.pub.mailoutpod2-cph3.one.com (Halon) with ESMTPSA id dbe9f07d-8cb2-11f0-9ef2-85eb291bc831; Mon, 08 Sep 2025 12:53:48 +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 v3] rust: rbtree: add immutable cursor Date: Mon, 8 Sep 2025 14:53:39 +0200 Message-Id: <20250908125339.3313777-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 --- Changelog: --------- v1 -> v2: * corrected grammar hiccups * logic for cursor_lower_bound[_mut] variants put into a separate * function * to_key_value_raw() removed from the immutable cursor implementation v2 -> v3: * find_best_match() modified to directly return links * safety comments corrected for Send/Sync rust/kernel/rbtree.rs | 240 ++++++++++++++++++++++++++++++++++-------- 1 file changed, 196 insertions(+), 44 deletions(-) diff --git a/rust/kernel/rbtree.rs b/rust/kernel/rbtree.rs index b8fe6be6fcc4..fc8b368e293e 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 immutable 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,12 +451,47 @@ 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, + { + let best =3D self.find_best_match(key)?; + + NonNull::new(best.as_ptr()).map(|current| { + // INVARIANT: + // - `current` is a valid node in the [`RBTree`] pointed to by= `self`. + 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 best =3D self.find_best_match(key)?; + + NonNull::new(best.as_ptr()).map(|current| { + // INVARIANT: + // - `current` is a valid node in the [`RBTree`] pointed to by= `self`. + Cursor { + current, + _tree: PhantomData, + } + }) + } + + fn find_best_match(&self, key: &K) -> Option> { let mut node =3D self.root.rb_node; - let mut best_match: Option>> =3D None; + let mut best_key: Option<&K> =3D None; + let mut best_links: 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. @@ -439,42 +504,30 @@ pub fn cursor_lower_bound(&mut self, key: &K) -> Opti= on> let right_child =3D unsafe { (*node).rb_right }; match key.cmp(this_key) { Ordering::Equal =3D> { - best_match =3D NonNull::new(this); + // SAFETY: `this` is a non-null node so it is valid by= the type invariants. + best_links =3D Some(unsafe { NonNull::new_unchecked(&m= ut (*this).links) }); break; } Ordering::Greater =3D> { node =3D right_child; } Ordering::Less =3D> { - let is_better_match =3D match best_match { + let is_better_match =3D match best_key { 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 + best > this_key } }; if is_better_match { - best_match =3D NonNull::new(this); + best_key =3D Some(this_key); + // SAFETY: `this` is a non-null node so it is vali= d by the type invariants. + best_links =3D Some(unsafe { NonNull::new_unchecke= d(&mut (*this).links) }); } 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: self, - } - }) + best_links } } =20 @@ -507,7 +560,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 +579,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 +617,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 +630,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 +681,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 +708,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 +718,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 +747,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 +755,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,18 +779,47 @@ 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 immutable 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, +} =20 -// SAFETY: The [`Cursor`] gives out immutable references to K and mutable = references to V, -// so it has the same thread safety requirements as mutable references. +// SAFETY: The immutable cursor gives out shared access to `K` and `V` so = if `K` and `V` can be +// shared across threads, then it's safe to share the cursor. +unsafe impl<'a, K: Sync, V: Sync> Send for Cursor<'a, K, V> {} + +// SAFETY: The immutable cursor gives out shared access to `K` and `V` so = if `K` and `V` can be +// shared across threads, then it's safe to share the cursor. unsafe impl<'a, K: Sync, V: Sync> Sync for Cursor<'a, K, V> {} =20 impl<'a, K, V> Cursor<'a, K, V> { @@ -749,6 +831,76 @@ 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: 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 { &(*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) + } +} + +// 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> {} + +// 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 CursorMut<'a, K, V> {} + + +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 +1072,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