Message-Id: <F5FF6A15-B1EE-4D2C-97F4-FCBC4A8404F7@konsulko.se>
Date: Fri, 5 Sep 2025 16:32:27 +0200
From: Vitaly Wool <vitaly.wool@...sulko.se>
To: Onur Özkan <work@...rozkan.dev>
Cc: rust-for-linux <rust-for-linux@...r.kernel.org>,
 LKML <linux-kernel@...r.kernel.org>,
 Danilo Krummrich <dakr@...nel.org>,
 Alice Ryhl <aliceryhl@...gle.com>,
 Alex Gaynor <alex.gaynor@...il.com>,
 Boqun Feng <boqun.feng@...il.com>,
 Gary Guo <gary@...yguo.net>,
 Bjorn Roy Baron <bjorn3_gh@...tonmail.com>,
 Benno Lossin <lossin@...nel.org>,
 Andreas Hindborg <a.hindborg@...nel.org>,
 Trevor Gross <tmgross@...ch.edu>
Subject: Re: [PATCH] rust: rbtree: add immutable cursor



> On Sep 4, 2025, at 6:32 PM, Onur Özkan <work@...rozkan.dev> wrote:
> 
> On Thu,  4 Sep 2025 16:25:52 +0200
> Vitaly Wool <vitaly.wool@...sulko.se> wrote:
> 
>> 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 <vitaly.wool@...sulko.se>
>> ---
>> 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},
>> };
>> 
>> /// A red-black tree with owned nodes.
>> @@ -243,34 +243,64 @@ pub fn values_mut(&mut self) -> impl
>> Iterator<Item = &'_ mut V> { }
>> 
>>     /// Returns a cursor over the tree nodes, starting with the
>> smallest key.
>> -    pub fn cursor_front(&mut self) -> Option<Cursor<'_, K, V>> {
>> +    pub fn cursor_front_mut(&mut self) -> Option<CursorMut<'_, K,
>> V>> { let root = addr_of_mut!(self.root);
>>         // SAFETY: `self.root` is always a valid root node
>>         let current = 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,
>>             }
>>         })
>>     }
>> 
>> +    /// Returns an unmutable cursor over the tree nodes, starting
> 
> This should be "Returns an immutable...".

Thanks, will fix here and in the other place.

> 
>> with the smallest key.
>> +    pub fn cursor_front(&self) -> Option<Cursor<'_, K, V>> {
>> +        let root = addr_of!(self.root);
>> +        // SAFETY: `self.root` is always a valid root node
>> +        let current = 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 key.
>> -    pub fn cursor_back(&mut self) -> Option<Cursor<'_, K, V>> {
>> +    pub fn cursor_back_mut(&mut self) -> Option<CursorMut<'_, K, V>>
>> { let root = addr_of_mut!(self.root);
>>         // SAFETY: `self.root` is always a valid root node
>>         let current = 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 key.
>> +    pub fn cursor_back(&self) -> Option<Cursor<'_, K, V>> {
>> +        let root = addr_of!(self.root);
>> +        // SAFETY: `self.root` is always a valid root node
>> +        let current = 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,
>> +            }
>> +        })
>> +    }
>> }
>> 
>> impl<K, V> RBTree<K, V>
>> @@ -421,7 +451,7 @@ pub fn remove(&mut self, key: &K) -> Option<V> {
>>     /// 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<Cursor<'_, K, V>>
>> +    pub fn cursor_lower_bound_mut(&mut self, key: &K) ->
>> Option<CursorMut<'_, K, V>> where
>>         K: Ord,
>>     {
>> @@ -470,12 +500,74 @@ pub fn cursor_lower_bound(&mut self, key: &K)
>> -> Option<Cursor<'_, K, V>> 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<Cursor<'_,
>> K, V>>
>> +    where
>> +        K: Ord,
>> +    {
>> +        let mut node = self.root.rb_node;
>> +        let mut best_match: Option<NonNull<Node<K, V>>> = None;
>> +        while !node.is_null() {
>> +            // SAFETY: By the type invariant of `Self`, all non-null
>> `rb_node` pointers stored in
>> +            // `self` point to the links field of `Node<K, V>`
>> objects.
>> +            let this = unsafe { container_of!(node, Node<K, V>,
>> links) };
>> +            // SAFETY: `this` is a non-null node so it is valid by
>> the type invariants.
>> +            let this_key = unsafe { &(*this).key };
>> +            // SAFETY: `node` is a non-null node so it is valid by
>> the type invariants.
>> +            let left_child = unsafe { (*node).rb_left };
>> +            // SAFETY: `node` is a non-null node so it is valid by
>> the type invariants.
>> +            let right_child = unsafe { (*node).rb_right };
>> +            match key.cmp(this_key) {
>> +                Ordering::Equal => {
>> +                    best_match = NonNull::new(this);
>> +                    break;
>> +                }
>> +                Ordering::Greater => {
>> +                    node = right_child;
>> +                }
>> +                Ordering::Less => {
>> +                    let is_better_match = match best_match {
>> +                        None => true,
>> +                        Some(best) => {
>> +                            // SAFETY: `best` is a non-null node so
>> it is valid by the type
>> +                            // invariants.
>> +                            let best_key = unsafe {
>> &(*best.as_ptr()).key };
>> +                            best_key > this_key
>> +                        }
>> +                    };
>> +                    if is_better_match {
>> +                        best_match = NonNull::new(this);
>> +                    }
>> +                    node = left_child;
>> +                }
>> +            };
>> +        }
>> +
>> +        let best = best_match?;
>> +
>> +        // SAFETY: `best` is a non-null node so it is valid by the
>> type invariants.
>> +        let links = unsafe { addr_of_mut!((*best.as_ptr()).links) };
> 
> Shouldn't we use `addr_of!` here?

NonNull::new() expects a mutable reference, so I would argue that the existing variant is correct.

Best regards,
Vitaly

> 
>> +
>> +        NonNull::new(links).map(|current| {
>> +            // INVARIANT:
>> +            // - `current` is a valid node in the [`RBTree`] pointed
>> to by `self`.
>> +            Cursor {
>> +                current,
>> +                _tree: PhantomData,
>> +            }
>> +        })
>> +    }
>> }
>> 
>> impl<K, V> Default for RBTree<K, V> {
>> @@ -507,7 +599,7 @@ fn drop(&mut self) {
>>     }
>> }
>> 
>> -/// 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 = tree.cursor_front().unwrap();
>> +/// let mut cursor = tree.cursor_front_mut().unwrap();
>> /// let mut current = 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 = tree.cursor_back().unwrap();
>> +/// let mut cursor = tree.cursor_back_mut().unwrap();
>> /// let current = cursor.current();
>> /// assert_eq!(current, (&30, &300));
>> ///
>> @@ -577,7 +669,7 @@ fn drop(&mut self) {
>> /// use kernel::rbtree::RBTree;
>> ///
>> /// let mut tree: RBTree<u16, u16> = 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 = tree.cursor_front().unwrap();
>> +/// let mut cursor = tree.cursor_front_mut().unwrap();
>> ///
>> /// // Get a mutable reference to the current value.
>> /// let (k, v) = 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 = tree.cursor_front().unwrap();
>> +/// let mut cursor = tree.cursor_front_mut().unwrap();
>> /// let mut current = cursor.current();
>> /// assert_eq!(current, (&10, &100));
>> /// cursor = 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 = tree.cursor_back().unwrap();
>> +/// cursor = tree.cursor_back_mut().unwrap();
>> /// current = 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 = tree.cursor_front().unwrap();
>> +/// let mut cursor = tree.cursor_front_mut().unwrap();
>> /// let mut current = 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 = tree.cursor_back().unwrap();
>> +/// cursor = tree.cursor_back_mut().unwrap();
>> /// current = 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<K, V>,
>>     current: NonNull<bindings::rb_node>,
>> }
>> 
>> -// 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 it 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 Cursor<'a, K, V> {} +/// A bidirectional
>> unmutable cursor over the tree nodes, sorted by key. This is a
> 
> Same here, should be "A bidirectional immutable...".
> 
> --
> 
> Regards,
> Onur
> 
>> 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 the tree. +/// The cursor allows us to iterate
>> bidirectionally over key/value pairs in the tree. +///
>> +/// ```
>> +/// use kernel::{alloc::flags, rbtree::RBTree};
>> +///
>> +/// // Create a new tree.
>> +/// let mut tree = 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 = tree.cursor_front().unwrap();
>> +/// let current = cursor.current();
>> +/// assert_eq!(current, (&10, &100));
>> +///
>> +/// # Ok::<(), Error>(())
>> +pub struct Cursor<'a, K, V> {
>> +    _tree: PhantomData<&'a RBTree<K, V>>,
>> +    current: NonNull<bindings::rb_node>,
>> +}
>> +
>> +// 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 it 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 [`Cursor`] gives out immutable references to K and
>> mutable references to V, +// SAFETY: The [`CursorMut`] gives out
>> immutable references to K and mutable 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> {} 
>> 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) }
>>     }
>> 
>> +    /// # 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) {
>> +        // SAFETY: the caller guarantees that `node` is a valid
>> pointer in an `RBTree`.
>> +        let (k, v) = 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<bindings::rb_node>)
>> -> (&'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<K, V>` objects.
>> +        let this = unsafe { container_of!(node.as_ptr(), Node<K, V>,
>> links) };
>> +        // SAFETY: The passed `node` is the current node or a
>> non-null neighbor,
>> +        // thus `this` is valid by the type invariants.
>> +        let k = unsafe { &(*this).key };
>> +        // SAFETY: The passed `node` is the current node or a
>> non-null neighbor,
>> +        // thus `this` is valid by the type invariants.
>> +        let v = 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<NonNull<bindings::rb_node>> {
>> +        // SAFETY: `self.current` is valid by the type invariants.
>> +        let neighbor = unsafe {
>> +            match direction {
>> +                Direction::Prev =>
>> bindings::rb_prev(self.current.as_ptr()),
>> +                Direction::Next =>
>> 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<bindings::rb_node>) -> (&'b K, *mut }
>> }
>> 
>> -/// Direction for [`Cursor`] operations.
>> +/// Direction for [`Cursor`] and [`CursorMut`] operations.
>> enum Direction {
>>     /// the node immediately before, in sort order
>>     Prev,

Powered by blists - more mailing lists