From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail-4316.protonmail.ch (mail-4316.protonmail.ch [185.70.43.16]) (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 A8FDD152526 for ; Thu, 25 Apr 2024 21:58:16 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=185.70.43.16 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714082298; cv=none; b=CR5hNpzcLPD5exY5fiH0NAvuTpzxFguPMfIJIOWHTT7Km8+IT2aGmDIWueF6rNe9iiK2de4GzMc/yjeQqYhfOIyuxqU1rjqLlnMmuSVfb5/GcluFkAES/4qdPAvZFeAGwXQLlMFs24tYd4Mpx8wM4BriPLpFmk+KZv/cH0+alz0= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714082298; c=relaxed/simple; bh=KgIjecV6C7Nk07SLdfHCvsEa6tmgp+Vm85Nrr1SnqGU=; h=Date:To:From:Cc:Subject:Message-ID:In-Reply-To:References: MIME-Version:Content-Type; b=cJKLbJ9t6C7ytO+AqYL+Axg7+k5f5dFZ6JrD5TGcv7KKit9LHMHtGxBGS4xvqdJWp/UNoBT1C9yqUXRT/9SICztLwZo4wMb7unzONnp7sO+YDCe4uJwaz6K+Kc8lww+EmYdneQzVCYX3T8qtcdDEufWD/HzobvM8+CMDZoQLmz8= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dmarc=pass (p=quarantine dis=none) header.from=proton.me; spf=pass smtp.mailfrom=proton.me; dkim=pass (2048-bit key) header.d=proton.me header.i=@proton.me header.b=jyyf58Bg; arc=none smtp.client-ip=185.70.43.16 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=quarantine dis=none) header.from=proton.me Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=proton.me Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=proton.me header.i=@proton.me header.b="jyyf58Bg" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=proton.me; s=protonmail; t=1714082294; x=1714341494; bh=X4GK0qT25GBqVlUpxE1T+oiI6ffMY6kIFUz9p2N2THk=; h=Date:To:From:Cc:Subject:Message-ID:In-Reply-To:References: Feedback-ID:From:To:Cc:Date:Subject:Reply-To:Feedback-ID: Message-ID:BIMI-Selector; b=jyyf58Bg0cq4jXXMO3vLB/DwWO+rUR1zjGnZv1baRXXTPt+jFYEx9h5pzExB0BhdK CqYNx8U91c7MNF5pjVk8FnkSOScXuQGvpoolKe1qM6cAn135dEn0oPqpj1IuMCL1LB EcnG5xKepZY0VcW+lb/44fOJfiiwHl16o/lcw3Apn+0bWFP37ArflQ0Mej5N7nIYpn f/kZfitOMSjtotySOlibLHWwPfQTvQ61PgRrCT8Nt4nq5i4rWkqdR7RggDdjH4QzY7 +YxbKGU3hmHya1gnmyjxqoq2c01X7IN+lUnexp8gG2N57GewzlmzytpPD8jvG0Zbmd vi5oXgaCask1w== Date: Thu, 25 Apr 2024 21:58:09 +0000 To: Matt Gilbride , Miguel Ojeda , Alex Gaynor , Wedson Almeida Filho , Boqun Feng , Gary Guo , =?utf-8?Q?Bj=C3=B6rn_Roy_Baron?= , Andreas Hindborg , Alice Ryhl , Greg Kroah-Hartman , =?utf-8?Q?Arve_Hj=C3=B8nnev=C3=A5g?= , Todd Kjos , Martijn Coenen , Joel Fernandes , Carlos Llamas , Suren Baghdasaryan , Christian Brauner From: Benno Lossin Cc: Rob Landley , Davidlohr Bueso , Michel Lespinasse , rust-for-linux@vger.kernel.org, linux-kernel@vger.kernel.org Subject: Re: [PATCH v3 3/5] rust: rbtree: add `RBTreeIteratorMut` Message-ID: In-Reply-To: <20240418-b4-rbtree-v3-3-323e134390ce@google.com> References: <20240418-b4-rbtree-v3-0-323e134390ce@google.com> <20240418-b4-rbtree-v3-3-323e134390ce@google.com> Feedback-ID: 71780778:user:proton X-Pm-Message-ID: d84f15a7d28ce27feb45bee2c48c45d49781f864 Precedence: bulk X-Mailing-List: rust-for-linux@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable On 18.04.24 16:15, Matt Gilbride wrote: > From: Wedson Almeida Filho >=20 > Add mutable Iterator implementation (`RBTreeIteratorMut`) for `RBTree`, > allowing iteration over (key, value) pairs in key order. Only values are > mutable, as mutating keys implies modifying a node's position in the tree= . >=20 > Mutable iteration is used by the binder driver during shutdown to > clean up the tree maintained by the "range allocator" [1]. >=20 > Link: https://lore.kernel.org/rust-for-linux/20231101-rust-binder-v1-6-08= ba9197f637@google.com/ [1] > Signed-off-by: Wedson Almeida Filho > Signed-off-by: Matt Gilbride > Reviewed-by: Alice Ryhl > Tested-by: Alice Ryhl > --- > rust/kernel/rbtree.rs | 64 +++++++++++++++++++++++++++++++++++++++++++++= ++++++ > 1 file changed, 64 insertions(+) >=20 > diff --git a/rust/kernel/rbtree.rs b/rust/kernel/rbtree.rs > index 2f836be7bdbe..50d440c9926d 100644 > --- a/rust/kernel/rbtree.rs > +++ b/rust/kernel/rbtree.rs > @@ -222,6 +222,15 @@ pub fn iter(&self) -> RBTreeIterator<'_, K, V> { > } > } >=20 > + /// Returns a mutable iterator over the tree nodes, sorted by key. > + pub fn iter_mut(&mut self) -> RBTreeIteratorMut<'_, K, V> { > + RBTreeIteratorMut { This is missing an INVARIANT comment. > + _tree: PhantomData, > + // SAFETY: `root` is valid as it's embedded in `self` and we= have a valid `self`. > + next: unsafe { bindings::rb_first(&self.root) }, > + } > + } > + > /// Returns an iterator over the keys of the nodes in the tree, in s= orted order. > pub fn keys(&self) -> impl Iterator { > self.iter().map(|(k, _)| k) > @@ -231,6 +240,11 @@ pub fn keys(&self) -> impl Iterator = { > pub fn values(&self) -> impl Iterator { > self.iter().map(|(_, v)| v) > } > + > + /// Returns a mutable iterator over the values of the nodes in the t= ree, sorted by key. > + pub fn values_mut(&mut self) -> impl Iterator { > + self.iter_mut().map(|(_, v)| v) > + } > } >=20 > impl RBTree > @@ -466,6 +480,56 @@ fn next(&mut self) -> Option { > } > } >=20 > +impl<'a, K, V> IntoIterator for &'a mut RBTree { > + type Item =3D (&'a K, &'a mut V); > + type IntoIter =3D RBTreeIteratorMut<'a, K, V>; > + > + fn into_iter(self) -> Self::IntoIter { > + self.iter_mut() > + } > +} > + > +/// A mutable iterator over the nodes of a [`RBTree`]. > +/// > +/// Instances are created by calling [`RBTree::iter_mut`]. > +/// > +/// # Invariants > +/// - `self.next` is a valid pointer. > +/// - `self.next` points to a node stored inside of a valid `RBTree`. > +pub struct RBTreeIteratorMut<'a, K, V> { I think the names `Iter` and `IterMut` are more natural. That is what the collections in `std::collections` do. These are in the module `rbtree`, so you can refer to them as `rbtree::Iter`. > + _tree: PhantomData<&'a RBTree>, This should have the type `PhantomData<&'a mut RBTree>`. > + next: *mut bindings::rb_node, > +} You could create a common iterator type, since both `RBTreeIterator` and `RBTreeIteratorMut` are very similar. How about a (private) `RawIter`: struct RawIter { next: *mut bindings::rb_node, _phantom: PhantomData (K, V)>, } And implement `Iterator` with `Item =3D (*mut K, *mut V)` for `RawIter`. Then you can change `Iter` to be: pub struct Iter<'a, K, V> { raw_iter: RawIter, _tree: PhantomData<&'a RBTree>, } --=20 Cheers, Benno > + > +// SAFETY: The [`RBTreeIterator`] gives out mutable references to K and = V, so it has the same > +// thread safety requirements as mutable references. > +unsafe impl<'a, K: Send, V: Send> Send for RBTreeIteratorMut<'a, K, V> {= } > + > +// SAFETY: The [`RBTreeIterator`] gives out mutable references to K and = V, so it has the same > +// thread safety requirements as mutable references. > +unsafe impl<'a, K: Sync, V: Sync> Sync for RBTreeIteratorMut<'a, K, V> {= } > + > +impl<'a, K, V> Iterator for RBTreeIteratorMut<'a, K, V> { > + type Item =3D (&'a K, &'a mut V); > + > + fn next(&mut self) -> Option { > + if self.next.is_null() { > + return None; > + } > + > + // SAFETY: By the type invariant of `Self`, all non-null `rb_nod= e` pointers stored in `self` > + // point to the links field of `Node` objects. > + let cur =3D unsafe { container_of!(self.next, Node, links)= }.cast_mut(); > + > + // SAFETY: `self.next` is a valid tree node by the type invarian= ts. > + 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, &mut (*cur).value) }) > + } > +} > + > /// A memory reservation for a red-black tree node. > /// > /// It contains the memory needed to hold a node that can be inserted in= to a red-black tree. One >=20 > -- > 2.44.0.769.g3c40516874-goog >=20