From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail-4322.protonmail.ch (mail-4322.protonmail.ch [185.70.43.22]) (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 AE662153812 for ; Thu, 25 Apr 2024 21:26:31 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=185.70.43.22 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714080393; cv=none; b=SaGpAjyMwie5lUuJFbi1A82Fht+dKBiW27WfMdQb9va83QLXF5+7Narb3JGhQrHIBXAik9Y/dRG7BuwUOuFeco315Uvu33vXydKjBn0IxoBn04jaa3YQbvOqvlGd+VG02urdSWsYzlrmiu4xJQAJ+vSWFhFWjCFuGtoM8xovig0= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714080393; c=relaxed/simple; bh=OGJY41svwj1KsHB2NXgqa3jKEspKo9hZFX1N8pEPz5w=; h=Date:To:From:Cc:Subject:Message-ID:In-Reply-To:References: MIME-Version:Content-Type; b=MmjT7JX2LRMsr3LkJwRAEWmmihqH1dvZK5td6P+GhwHpPK0z5uN6A2CQOvks+R4fkkdiu6saRcKNaX6BSJ78OqvaN8uor2kgBpnRKX6IP9tc+B1P0vKqsZ23sK5sHP0mfZbnc1LgvutHRENnninl9gtVp6kl2p+ZRJB/2EkbO8k= 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=Kut+xywb; arc=none smtp.client-ip=185.70.43.22 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="Kut+xywb" DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=proton.me; s=wywttca6drde7ebdbqx56qtb3y.protonmail; t=1714080389; x=1714339589; bh=/Q06pgsNCa5kGWP4sxOXcijGesvZMcptNNSOERHlzig=; 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=Kut+xywbD7k7ruUp+Gy90oThj9UAz/gqifxOi9BgUXC7H6GqiRzqox/SvMlioPgH2 6xL5hWsaqLN8SzDVkE1Je0eX6oLLXxLOpmEdJWevDD9AyPLHPx4TJWOXQq6y3Okt8E hP9NvfvES+ckn/GP6hDewEQBmXeVLK+4GVQB0PlkXg+isPf4REi8BQ0DOK8agfeXtY wlDrxTcf/eFPFIKCS2zpZgOu2CKRPho5o7KfFChwXPgPSNjW+Verp91Od5ZMt+hhuG hf+dmbD7YWD7fv4QReLorvARyelt6LX3gySzTk23sRr5LzKPlGo2WsIYT+LxCnYrKU av4mQ1SEZpILQ== Date: Thu, 25 Apr 2024 21:26:25 +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 1/5] rust: rbtree: add red-black tree implementation backed by the C version Message-ID: In-Reply-To: <20240418-b4-rbtree-v3-1-323e134390ce@google.com> References: <20240418-b4-rbtree-v3-0-323e134390ce@google.com> <20240418-b4-rbtree-v3-1-323e134390ce@google.com> Feedback-ID: 71780778:user:proton X-Pm-Message-ID: 48befda4b3564fcd9a079aaa74e9d878b90c3123 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: > diff --git a/rust/kernel/rbtree.rs b/rust/kernel/rbtree.rs > new file mode 100644 > index 000000000000..ad406fc32d67 > --- /dev/null > +++ b/rust/kernel/rbtree.rs > @@ -0,0 +1,425 @@ > +// SPDX-License-Identifier: GPL-2.0 > + > +//! Red-black trees. > +//! > +//! C header: [`include/linux/rbtree.h`](srctree/include/linux/rbtree.h) > +//! > +//! Reference: > + > +use crate::{bindings, container_of, error::Result, prelude::*}; > +use alloc::boxed::Box; > +use core::{ > + cmp::{Ord, Ordering}, > + convert::Infallible, > + marker::PhantomData, > + mem::MaybeUninit, > + ptr::{addr_of_mut, NonNull}, > +}; > + > +struct Node { > + links: bindings::rb_node, > + key: K, > + value: V, > +} Personal preference: I prefer putting items that give a high-level overview of the module to the top. I don't feel like I gain anything from seeing the definition of the `Node` type this early. [...] > +impl RBTree { > + /// Creates a new and empty tree. > + pub fn new() -> Self { > + Self { > + // INVARIANT: There are no nodes in the tree, so the invaria= nt holds vacuously. > + root: bindings::rb_root::default(), > + _p: PhantomData, > + } > + } > + > + /// Allocates memory for a node to be eventually initialised and ins= erted into the tree via a > + /// call to [`RBTree::insert`]. > + pub fn try_reserve_node() -> Result> { This function creates a `RBTreeNodeReservation`, I think it would make sense to move it to that type and just name this function `new`. > + Ok(RBTreeNodeReservation { > + node: Box::init::(crate::init::uninit())?, `Box::new_uninit()` probably makes more sense here. (what you did is not wrong, but I think the intent is better captured by `new_uninit`) > + }) > + } > + > + /// Allocates and initialises a node that can be inserted into the t= ree via > + /// [`RBTree::insert`]. > + pub fn try_allocate_node(key: K, value: V) -> Result> { Same with this function, I would move it to `RBTreeNode` and call it `new`. > + Ok(Self::try_reserve_node()?.into_node(key, value)) > + } > +} > + > +impl RBTree > +where > + K: Ord, Citing the rust docs [1] on the requirements that implementations of the `Ord` trait need to satsify: "[...] Violating these requirements is a logic error. The behavior resulting from a logic error is not specified, but users of the trait must ensure that such logic errors do not result in undefined behavior. This means that `unsafe` code **must not** rely on the correctness of these methods." I haven't yet fully checked this, since I would have to delve into the C side. But I wanted to ask if you have given any thought to this issue. In particular this means that you must not rely on `<` (or `cmp`) being eg transitive in `unsafe` code. From what I have seen in this patch, I think there are no issues with the way you use `Ord`. [1]: https://doc.rust-lang.org/core/cmp/trait.Ord.html > +{ [...] > +impl RBTreeNodeReservation { > + /// Initialises a node reservation. > + /// > + /// It then becomes an [`RBTreeNode`] that can be inserted into a tr= ee. > + pub fn into_node(mut self, key: K, value: V) -> RBTreeNode { > + let node_ptr =3D self.node.as_mut_ptr(); > + // SAFETY: `node_ptr` is valid, and so are its fields. > + unsafe { addr_of_mut!((*node_ptr).links).write(bindings::rb_node= ::default()) }; > + // SAFETY: `node_ptr` is valid, and so are its fields. > + unsafe { addr_of_mut!((*node_ptr).key).write(key) }; > + // SAFETY: `node_ptr` is valid, and so are its fields. > + unsafe { addr_of_mut!((*node_ptr).value).write(value) }; > + RBTreeNode { > + // SAFETY: The pointer came from a `MaybeUninit` whose= fields have all been > + // initialised. Additionally, it has the same layout as `Nod= e`. > + node: unsafe { Box::>::assume_init(self.node)= }, > + } I really dislike the verbosity of this function. Also what will ensure that you really did initialize all fields? I think I have a way to improve this using a new function on `Box`: impl Box> { fn re_init(self, init: impl Init) -> Result, E>; } Then you could do this instead: pub fn into_node(mut self, key: K, value: V) -> RBTreeNode { let node =3D init!(Node { key, value, links: bindings::rb_node::default(), }); RBTreeNode { node: self.node.re_init(node) } } All the `unsafe` vanishes! I think this is useful in general, so I am going to send a patch with the above mentioned method. In addition to that I am also going to extend `Box` to allow converting `Box -> Box>` to simplify `into_reservation` from patch 5. --=20 Cheers, Benno > + } > +} > + > +/// A red-black tree node. > +/// > +/// The node is fully initialised (with key and value) and can be insert= ed into a tree without any > +/// extra allocations or failure paths. > +pub struct RBTreeNode { > + node: Box>, > +} > + > +// SAFETY: If K and V can be sent across threads, then it's also okay to= send [`RBTreeNode`] across > +// threads. > +unsafe impl Send for RBTreeNode {} > + > +// SAFETY: If K and V can be accessed without synchronization, then it's= also okay to access > +// [`RBTreeNode`] without synchronization. > +unsafe impl Sync for RBTreeNode {} >=20 > -- > 2.44.0.769.g3c40516874-goog >=20