linux-kernel - Re: [PATCH v2 2/2] rust: list: make the cursor point between elements

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: <CAH5fLgi=WbkcAcqbZRozJP0XQvQLdAtihEMZz3Qzyf1MJbjHhQ@mail.gmail.com>
Date: Wed, 22 Jan 2025 11:02:19 +0100
From: Alice Ryhl <aliceryhl@...gle.com>
To: Boqun Feng <boqun.feng@...il.com>
Cc: Miguel Ojeda <ojeda@...nel.org>, Alex Gaynor <alex.gaynor@...il.com>, Gary Guo <gary@...yguo.net>, 
	Björn Roy Baron <bjorn3_gh@...tonmail.com>, 
	Benno Lossin <benno.lossin@...ton.me>, Andreas Hindborg <a.hindborg@...nel.org>, 
	Trevor Gross <tmgross@...ch.edu>, rust-for-linux@...r.kernel.org, 
	linux-kernel@...r.kernel.org
Subject: Re: [PATCH v2 2/2] rust: list: make the cursor point between elements

On Tue, Jan 21, 2025 at 10:15 PM Boqun Feng <boqun.feng@...il.com> wrote:
>
> On Tue, Jan 21, 2025 at 10:14:24AM +0000, Alice Ryhl wrote:
> [...]
> > +/// References the element in the list next to the cursor.
> > +///
> > +/// # Invariants
> > +///
> > +/// * `ptr` is an element in `self.cursor.list`.
> > +/// * `ISNEXT == (self.ptr == self.cursor.next)`.
> > +pub struct CursorPeek<'a, 'b, T: ?Sized + ListItem<ID>, const ISNEXT: bool, const ID: u64> {
> > +    cursor: &'a mut Cursor<'b, T, ID>,
> > +    ptr: *mut ListLinksFields,
> > +}
> > +
> > +impl<'a, 'b, T: ?Sized + ListItem<ID>, const ISNEXT: bool, const ID: u64>
> > +    CursorPeek<'a, 'b, T, ISNEXT, ID>
> > +{
> > +    /// Remove the element from the list.
> >      pub fn remove(self) -> ListArc<T, ID> {
> > -        // SAFETY: The `current` pointer always points at a member of the list.
> > -        unsafe { self.list.remove_internal(self.current) }
> > +        if ISNEXT {
> > +            self.cursor.move_next();
> > +        }
> > +
> > +        // INVARIANT: `self.ptr` is not equal to `self.cursor.next` due to the above `move_next`
> > +        // call.
> > +        // SAFETY: By the type invariants of `Self`, `next` is not null, so `next` is an element of
> > +        // `self.cursor.list` by the type invariants of `Cursor`.
> > +        unsafe { self.cursor.list.remove_internal(self.ptr) }
> > +    }
> > +
> > +    /// Access this value as an [`ArcBorrow`].
> > +    pub fn arc(&self) -> ArcBorrow<'_, T> {
> > +        // SAFETY: `self.ptr` points at an element in `self.cursor.list`.
> > +        let me = unsafe { T::view_value(ListLinks::from_fields(self.ptr)) };
> > +        // SAFETY:
> > +        // * All values in a list are stored in an `Arc`.
> > +        // * The value cannot be removed from the list for the duration of the lifetime annotated
> > +        //   on the returned `ArcBorrow`, because removing it from the list would require mutable
> > +        //   access to the `CursorPeek`, the `Cursor` or the `List`. However, the `ArcBorrow` holds
> > +        //   an immutable borrow on the `CursorPeek`, which in turn holds a mutable borrow on the
> > +        //   `Cursor`, which in turn holds a mutable borrow on the `List`, so any such mutable
> > +        //   access requires first releasing the immutable borrow on the `CursorPeek`.
> > +        // * Values in a list never have a `UniqueArc` reference, because the list has a `ListArc`
> > +        //   reference, and `UniqueArc` references must be unique.
> > +        unsafe { ArcBorrow::from_raw(me) }
> > +    }
> > +}
> > +
> > +impl<'a, 'b, T: ?Sized + ListItem<ID>, const ISNEXT: bool, const ID: u64> core::ops::Deref
> > +    for CursorPeek<'a, 'b, T, ISNEXT, ID>
> > +{
> > +    // This can't use `ArcBorrow<'a, T>` as the target type because 'a is too long. It would let
> > +    // you obtain an `ArcBorrow<'a, T>` and then call `CursorPeek::remove` without giving up the
> > +    // `ArcBorrow<'a, T>`.
>
> I'm not sure whether we want to mention `ArcBorrow<'a, T>` here, because
> `ArcBorrow<'a, T>` is a (smart) pointer type, which should never be used
> as a `Deref::Target`, otherwise CursorPeek::deref() would return a
> &ArcBorrow<'a, T>, which doesn't make sense, and a bit challenging to
> implement I think?

A previous implementation of this struct used ArcBorrow as the type of
`self.ptr`, but I had to abandon that because it wasn't helpful. I
wrote this comment to document that I couldn't get it to work. I can
remove it if you don't think it's useful.

> > +    type Target = T;
> > +
> > +    fn deref(&self) -> &T {
> > +        // SAFETY: `self.ptr` points at an element in `self.cursor.list`.
> > +        let me = unsafe { T::view_value(ListLinks::from_fields(self.cursor.next)) };
>
> Shouldn't this be `self.ptr` instead of `self.cursor.next`?

Excellent point, thanks.

Alice