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 for Android: free password hash cracker in your pocket

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <4ef9616f-a35a-4aa2-993c-9b67f50a46ee@proton.me>
Date: Tue, 06 Aug 2024 09:01:09 +0000
From: Benno Lossin <benno.lossin@...ton.me>
To: Alice Ryhl <aliceryhl@...gle.com>
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 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).

---
Cheers,
Benno