| 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
| ||
|
Message-ID: <CAH5fLgjHzYJAeZBA7JjK0_dw_m_XL+gU9x6M4Jv0tRzAH40+Pg@mail.gmail.com>
Date: Tue, 6 Aug 2024 10:41:29 +0200
From: Alice Ryhl <aliceryhl@...gle.com>
To: Benno Lossin <benno.lossin@...ton.me>
Cc: 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>, 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>, 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 v8 2/6] rust: rbtree: add red-black tree implementation
backed by the C version
On Mon, Aug 5, 2024 at 9:02 PM Benno Lossin <benno.lossin@...ton.me> wrote:
>
> On 27.07.24 22:30, Matt Gilbride wrote:
> > diff --git a/rust/kernel/rbtree.rs b/rust/kernel/rbtree.rs
> > new file mode 100644
> > index 000000000000..74c53e4d5c00
> > --- /dev/null
> > +++ b/rust/kernel/rbtree.rs
> > @@ -0,0 +1,432 @@
> > +// SPDX-License-Identifier: GPL-2.0
> > +
> > +//! Red-black trees.
> > +//!
> > +//! C header: [`include/linux/rbtree.h`](srctree/include/linux/rbtree.h)
> > +//!
> > +//! Reference: <https://www.kernel.org/doc/html/latest/core-api/rbtree.html>
> > +
> > +use crate::{alloc::Flags, bindings, container_of, error::Result, prelude::*};
> > +use alloc::boxed::Box;
> > +use core::{
> > + cmp::{Ord, Ordering},
> > + marker::PhantomData,
> > + mem::MaybeUninit,
> > + ptr::{addr_of_mut, NonNull},
> > +};
> > +
> > +/// A red-black tree with owned nodes.
> > +///
> > +/// It is backed by the kernel C red-black trees.
> > +///
> > +/// # Invariants
> > +///
> > +/// Non-null parent/children pointers stored in instances of the `rb_node` C struct are always
> > +/// valid, and pointing to a field of our internal representation of a node.
>
> I think we should standardize that `Invariants` and `Safety` sections
> are put last. This is because people reading the HTML version are
> probably not interested in the inner workings. This also makes it
> possible to have the invariants and the struct definition on the same
> screen.
We can reorder.
> > +/// ```
> > +pub struct RBTree<K, V> {
> > + root: bindings::rb_root,
>
> It has been a while, so I might have already asked this, but do we need
> `Opaque` here? We would need it, if C changes anything inside `root`
> while Rust holds a `&RBTree` or `&mut RBTree`.
> I don't think that this is the case (ie we don't need `Opaque`), but I
> am not sure.
It's not needed.
> > + _p: PhantomData<Node<K, V>>,
> > +}
> > +
>
> [...]
>
> > + /// Inserts a new node into the tree.
> > + ///
> > + /// It overwrites a node if one already exists with the same key and returns it (containing the
> > + /// key/value pair). Returns [`None`] if a node with the same key didn't already exist.
> > + ///
> > + /// This function always succeeds.
> > + pub fn insert(&mut self, RBTreeNode { node }: RBTreeNode<K, V>) -> Option<RBTreeNode<K, V>> {
> > + let node = Box::into_raw(node);
> > + // SAFETY: `node` is valid at least until we call `Box::from_raw`, which only happens when
> > + // the node is removed or replaced.
> > + let node_links = unsafe { addr_of_mut!((*node).links) };
> > +
> > + // The parameters of `rb_link_node` are as follows:
>
> Can you write `bindings::rb_link_node`?
Ok.
> > + // - `node`: A pointer to an uninitialized node being inserted.
> > + // - `parent`: A pointer to an existing node in the tree. One of its child pointers must be
> > + // null, and `node` will become a child of `parent` by replacing that child pointer
> > + // with a pointer to `node`.
> > + // - `rb_link`: A pointer to either the left-child or right-child field of `parent`. This
> > + // specifies which child of `parent` should hold `node` after this call. The
> > + // value of `*rb_link` must be null before the call to `rb_link_node`. If the
> > + // red/black tree is empty, then it’s also possible for `parent` to be null. In
> > + // this case, `rb_link` is a pointer to the `root` field of the red/black tree.
> > + //
> > + // We will traverse the tree looking for a node that has a null pointer as its child,
> > + // representing an empty subtree where we can insert our new node. We need to make sure
> > + // that we preserve the ordering of the nodes in the tree. In each iteration of the loop
> > + // we store `parent` and `child_field_of_parent`, and the new `node` will go somewhere
> > + // in the subtree of `parent` that `child_field_of_parent` points at. Once
> > + // we find an empty subtree, we can insert the new node using `rb_link_node`.
> > + let mut parent = core::ptr::null_mut();
> > + let mut child_field_of_parent: &mut *mut bindings::rb_node = &mut self.root.rb_node;
> > + while !child_field_of_parent.is_null() {
> > + parent = *child_field_of_parent;
> > +
> > + // We need to determine whether `node` should be the left or right child of `parent`,
> > + // so we will compare with the `key` field of `parent` a.k.a. `this` below.
> > + //
> > + // 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!(parent, Node<K, V>, links) };
> > +
> > + // SAFETY: `this` is a non-null node so it is valid by the type invariants. `node` is
> > + // valid until the node is removed.
> > + match unsafe { (*node).key.cmp(&(*this).key) } {
> > + // We would like `node` to be the left child of `parent`. Move to this child to check
> > + // whether we can use it, or continue searching, at the next iteration.
> > + //
> > + // SAFETY: `parent` is a non-null node so it is valid by the type invariants.
> > + Ordering::Less => child_field_of_parent = unsafe { &mut (*parent).rb_left },
> > + // We would like `node` to be the right child of `parent`. Move to this child to check
> > + // whether we can use it, or continue searching, at the next iteration.
> > + //
> > + // SAFETY: `parent` is a non-null node so it is valid by the type invariants.
> > + Ordering::Greater => child_field_of_parent = unsafe { &mut (*parent).rb_right },
> > + Ordering::Equal => {
> > + // There is an existing node in the tree with this key, and that node is
> > + // parent. Thus, we are replacing parent with a new node.
>
> Missing `` around "parent", double space after '.'.
Ok.
> > + //
> > + // INVARIANT: We are replacing an existing node with a new one, which is valid.
> > + // It remains valid because we "forgot" it with `Box::into_raw`.
> > + // SAFETY: All pointers are non-null and valid.
> > + unsafe { bindings::rb_replace_node(parent, node_links, &mut self.root) };
> > +
> > + // INVARIANT: The node is being returned and the caller may free it, however,
> > + // it was removed from the tree. So the invariants still hold.
> > + return Some(RBTreeNode {
> > + // SAFETY: `this` was a node in the tree, so it is valid.
> > + node: unsafe { Box::from_raw(this.cast_mut()) },
> > + });
> > + }
> > + }
> > + }
>
> [...]
>
> > +struct Node<K, V> {
> > + links: bindings::rb_node,
>
> Same question as with `rb_root`, do we need `Opaque`?
No.
> Otherwise the patch looks good.
Will you give a Reviewed-by conditional on the above changes?
Alice
Powered by blists - more mailing lists