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] [day] [month] [year] [list]

Message-ID: <4a1b6a7a-9d0c-4089-bc14-0fe629a56d3e@proton.me>
Date: Tue, 06 Aug 2024 09:27:29 +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 11:04, Alice Ryhl wrote:
> 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:
>>>>> +    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.

Ah that's true.

---
Cheers,
Benno