linux-kernel - Re: [PATCH v8 5/6] rust: rbtree: add `RBTreeCursor`

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: <CAH5fLgjiqOcu0JVgLze76LQDUD3KTQv9WrBy-GkMbCgVWn0xzA@mail.gmail.com>
Date: Tue, 6 Aug 2024 11:04:52 +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 5/6] rust: rbtree: add `RBTreeCursor`

On Tue, Aug 6, 2024 at 11:01 AM Benno Lossin <benno.lossin@...ton.me> wrote:
>
> On 06.08.24 10:24, Alice Ryhl wrote:
> > On Mon, Aug 5, 2024 at 9:35 PM Benno Lossin <benno.lossin@...ton.me> wrote:
> >> On 27.07.24 22:30, Matt Gilbride wrote:
> >>> +        // SAFETY: `best` is a non-null node so it is valid by the type invariants.
> >>> +        let links = unsafe { addr_of_mut!((*best.as_ptr()).links) };
> >>> +
> >>> +        NonNull::new(links).map(|current| {
> >>
> >> Why would `links` be a null pointer? AFAIK it just came from `best`
> >> which is non-null. (I don't know if we want to use `new_unchecked`
> >> instead, but wanted to mention it)
> >
> > It's never a null pointer in this branch. Do you prefer an extra
> > unsafe block to call new_unchecked?
>
> No need, doesn't seem like this part is hot and this is something that
> field projections could solve.
>
> >>> +            // INVARIANT:
> >>> +            // - `current` is a valid node in the [`RBTree`] pointed to by `self`.
> >>> +            // - Due to the type signature of this function, the returned [`RBTreeCursor`]
> >>> +            //   borrows mutably from `self`.
> >>> +            RBTreeCursor {
> >>> +                current,
> >>> +                tree: self,
> >>> +            }
> >>> +        })
> >>> +    }
> >>
> >> [...]
> >>
> >>> +/// // Calling `remove_next` removes and returns the last element.
> >>> +/// assert_eq!(cursor.remove_next().unwrap().to_key_value(), (30, 300));
> >>> +///
> >>> +/// # Ok::<(), Error>(())
> >>> +/// ```
> >>
> >> I would put a newline here.
> >
> > Ok.
> >
> >>> +/// # Invariants
> >>> +/// - `current` points to a node that is in the same [`RBTree`] as `tree`.
> >>> +pub struct RBTreeCursor<'a, K, V> {
> >>
> >> I think we can name it just `Cursor`, since one can refer to it as
> >> `rbtree::Cursor` and then it also follows the naming scheme for `Iter`
> >> etc.
> >
> > You are welcome to submit that as a follow-up change.
> >
> >>> +    tree: &'a mut RBTree<K, V>,
> >>> +    current: NonNull<bindings::rb_node>,
> >>> +}
> >>> +
> >>> +// SAFETY: The [`RBTreeCursor`] gives out immutable references to K and mutable references to V,
> >>> +// so it has the same thread safety requirements as mutable references.
> >>> +unsafe impl<'a, K: Send, V: Send> Send for RBTreeCursor<'a, K, V> {}
> >>
> >> Again, do we want to use `K: Sync` here instead?
> >
> > In this case, `K: Send` and `K: Sync` are both sufficient conditions,
> > but `K: Send` will generally be less restrictive for the user.
>
> What if `K = struct(RefCell<i32>, i32)` where only the second i32 is
> used in `(Partial)Ord`? Then you can send `RBTreeCursor` to another
> thread and call `borrow` there, even though `K: !Sync` (and the value
> still lives on another thread).

In that scenario, all immutable references to the key would be on the
same thread as the cursor. The cursor borrows the tree mutably, so
there can only be one cursor.

When using `K: Send`, it's basically like having `RBTreeCursor` store
mutable references to the key, but with an API that downgrades to
immutable reference when giving out access to the key.

Alice