linux-kernel - Re: [PATCH v2 3/6] rust: rbtree: add `RBTreeIterator`

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <00178dbe-6dfc-48f5-9712-b0b7361d14e4@proton.me>
Date: Thu, 14 Mar 2024 16:24:23 +0000
From: Benno Lossin <benno.lossin@...ton.me>
To: Matt Gilbride <mattgilbride@...gle.com>, Miguel Ojeda <ojeda@...nel.org>, Alex Gaynor <alex.gaynor@...il.com>, Wedson Almeida Filho <wedsonaf@...il.com>, Boqun Feng <boqun.feng@...il.com>, Gary Guo <gary@...yguo.net>, Björn Roy Baron <bjorn3_gh@...tonmail.com>, Andreas Hindborg <a.hindborg@...sung.com>, Alice Ryhl <aliceryhl@...gle.com>, Greg Kroah-Hartman <gregkh@...uxfoundation.org>, Arve Hjønnevåg <arve@...roid.com>, Todd Kjos <tkjos@...roid.com>, Martijn Coenen <maco@...roid.com>, Joel Fernandes <joel@...lfernandes.org>, Carlos Llamas <cmllamas@...gle.com>, Suren Baghdasaryan <surenb@...gle.com>, Christian Brauner <brauner@...nel.org>
Cc: Rob Landley <rob@...dley.net>, Davidlohr Bueso <dave@...olabs.net>, Michel Lespinasse <michel@...pinasse.org>, rust-for-linux@...r.kernel.org, linux-kernel@...r.kernel.org
Subject: Re: [PATCH v2 3/6] rust: rbtree: add `RBTreeIterator`

On 2/19/24 12:48, Matt Gilbride wrote:
> @@ -350,6 +393,52 @@ fn drop(&mut self) {
>       }
>   }
> 
> +impl<'a, K, V> IntoIterator for &'a RBTree<K, V> {
> +    type Item = (&'a K, &'a V);
> +    type IntoIter = RBTreeIterator<'a, K, V>;
> +
> +    fn into_iter(self) -> Self::IntoIter {
> +        self.iter()
> +    }
> +}
> +
> +/// An iterator over the nodes of a [`RBTree`].
> +///
> +/// Instances are created by calling [`RBTree::iter`].

There probably should be some invariants here, like
- `self.next` is a valid pointer
- `self.next` points to a node stored inside of a valid `RBtree`

> +pub struct RBTreeIterator<'a, K, V> {
> +    _tree: PhantomData<&'a RBTree<K, V>>,
> +    next: *mut bindings::rb_node,
> +}
> +
> +// SAFETY: An [`RBTree`] allows the same kinds of access to its values that a struct allows to its
> +// fields, so we use the same Send condition as would be used for a struct with K and V fields.
> +unsafe impl<'a, K: Send, V: Send> Send for RBTreeIterator<'a, K, V> {}
> +
> +// SAFETY: An [`RBTree`] allows the same kinds of access to its values that a struct allows to its
> +// fields, so we use the same Sync condition as would be used for a struct with K and V fields.
> +unsafe impl<'a, K: Sync, V: Sync> Sync for RBTreeIterator<'a, K, V> {}

These comments should also be updated.

> +
> +impl<'a, K, V> Iterator for RBTreeIterator<'a, K, V> {
> +    type Item = (&'a K, &'a V);
> +
> +    fn next(&mut self) -> Option<Self::Item> {
> +        if self.next.is_null() {
> +            return None;
> +        }
> +
> +        // SAFETY: All links fields we create are in a `Node<K, V>`.

See my suggestion on patch 2.

> +        let cur = unsafe { crate::container_of!(self.next, Node<K, V>, links) };
> +
> +        // SAFETY: The reference to the tree used to create the iterator outlives the iterator, so
> +        // the tree cannot change. By the tree invariant, all nodes are valid.

Why does the pointer come from a tree to begin with? (ie you need the
invariants I stated above)

-- 
Cheers,
Benno

> +        self.next = unsafe { bindings::rb_next(self.next) };
> +
> +        // SAFETY: By the same reasoning above, it is safe to dereference the node. Additionally,
> +        // it is ok to return a reference to members because the iterator must outlive it.
> +        Some(unsafe { (&(*cur).key, &(*cur).value) })
> +    }
> +}
> +
>   /// A memory reservation for a red-black tree node.
>   ///
>   /// It contains the memory needed to hold a node that can be inserted into a red-black tree. One
> 
> --
> 2.44.0.rc0.258.g7320e95886-goog
>