Received-SPF: pass (google.com: domain of linux-kernel+bounces-103566-linux.lists.archive=gmail.com@vger.kernel.org designates 2604:1380:40f1:3f00::1 as permitted sender) client-ip=2604:1380:40f1:3f00::1;
Date: Thu, 14 Mar 2024 16:24:23 +0000
To: Matt Gilbride <mattgilbride@google.com>, Miguel Ojeda <ojeda@kernel.org>, Alex Gaynor <alex.gaynor@gmail.com>, Wedson Almeida Filho <wedsonaf@gmail.com>, Boqun Feng <boqun.feng@gmail.com>, Gary Guo <gary@garyguo.net>, =?utf-8?Q?Bj=C3=B6rn_Roy_Baron?= <bjorn3_gh@protonmail.com>, Andreas Hindborg <a.hindborg@samsung.com>, Alice Ryhl <aliceryhl@google.com>, Greg Kroah-Hartman <gregkh@linuxfoundation.org>, =?utf-8?Q?Arve_Hj=C3=B8nnev=C3=A5g?= <arve@android.com>, Todd Kjos <tkjos@android.com>, Martijn Coenen <maco@android.com>, Joel Fernandes <joel@joelfernandes.org>, Carlos Llamas <cmllamas@google.com>, Suren Baghdasaryan <surenb@google.com>, Christian Brauner <brauner@kernel.org>
From: Benno Lossin <benno.lossin@proton.me>
Cc: Rob Landley <rob@landley.net>, Davidlohr Bueso <dave@stgolabs.net>, Michel Lespinasse <michel@lespinasse.org>, rust-for-linux@vger.kernel.org, linux-kernel@vger.kernel.org
Subject: Re: [PATCH v2 3/6] rust: rbtree: add `RBTreeIterator`
Message-ID: <00178dbe-6dfc-48f5-9712-b0b7361d14e4@proton.me>
In-Reply-To: <20240219-b4-rbtree-v2-3-0b113aab330d@google.com>
References: <20240219-b4-rbtree-v2-0-0b113aab330d@google.com> <20240219-b4-rbtree-v2-3-0b113aab330d@google.com>
Feedback-ID: 71780778:user:proton
Precedence: bulk
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable

On 2/19/24 12:48, Matt Gilbride wrote:
> @@ -350,6 +393,52 @@ fn drop(&mut self) {
>       }
>   }
>=20
> +impl<'a, K, V> IntoIterator for &'a RBTree<K, V> {
> +    type Item =3D (&'a K, &'a V);
> +    type IntoIter =3D 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 t=
hat a struct allows to its
> +// fields, so we use the same Send condition as would be used for a stru=
ct 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 t=
hat a struct allows to its
> +// fields, so we use the same Sync condition as would be used for a stru=
ct 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 =3D (&'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 =3D 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)

--=20
Cheers,
Benno

> +        self.next =3D unsafe { bindings::rb_next(self.next) };
> +
> +        // SAFETY: By the same reasoning above, it is safe to dereferenc=
e the node. Additionally,
> +        // it is ok to return a reference to members because the iterato=
r 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 i=
nto a red-black tree. One
>=20
> --
> 2.44.0.rc0.258.g7320e95886-goog
>=20