linux-kernel - Re: [PATCH] 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] [thread-next>] [day] [month] [year] [list]

Message-ID: <CAH5fLginoFU38HbRjtOY8wAOo9uu5LJD7AKzduRkL0RcT6BUvw@mail.gmail.com>
Date: Mon, 20 Jan 2025 16:52:50 +0100
From: Alice Ryhl <aliceryhl@...gle.com>
To: Andreas Hindborg <a.hindborg@...nel.org>
Cc: Miguel Ojeda <ojeda@...nel.org>, Alex Gaynor <alex.gaynor@...il.com>, 
	Boqun Feng <boqun.feng@...il.com>, Gary Guo <gary@...yguo.net>, 
	Björn Roy Baron <bjorn3_gh@...tonmail.com>, 
	Benno Lossin <benno.lossin@...ton.me>, Trevor Gross <tmgross@...ch.edu>, 
	rust-for-linux@...r.kernel.org, linux-kernel@...r.kernel.org
Subject: Re: [PATCH] rust: list: make the cursor point between elements

On Mon, Jan 20, 2025 at 12:55 PM Andreas Hindborg <a.hindborg@...nel.org> wrote:
>
> Hi Alice,
>
> This looks like a nice improvement!

Thanks!

> This looks like a refactor of `push_front`, `push_back`. It looks like
> it is unrelated to the cursor change. Can you split this out into a
> separate patch?

I don't think it's unrelated. It extracts out common code that
previously only push_front/push_back have, but that the cursor now
also needs. Of course, it could still make sense to extract
insert_inner out in a separate patch.

> > @@ -489,17 +480,21 @@ pub fn push_all_back(&mut self, other: &mut List<T, ID>) {
> >          other.first = ptr::null_mut();
> >      }
> >
> > -    /// Returns a cursor to the first element of the list.
> > -    ///
> > -    /// If the list is empty, this returns `None`.
> > -    pub fn cursor_front(&mut self) -> Option<Cursor<'_, T, ID>> {
> > -        if self.first.is_null() {
> > -            None
> > -        } else {
> > -            Some(Cursor {
> > -                current: self.first,
> > -                list: self,
> > -            })
> > -        }
> > -    }
> > +    /// Returns a cursor that points before the first element of the list.
> > +    pub fn cursor_front(&mut self) -> Cursor<'_, T, ID> {
> > +        // INVARIANT: `self.first` is in this list.
> > +        Cursor {
> > +            next: self.first,
> > +            list: self,
> > +        }
> > +    }
> > +
> > +    /// Returns a cursor that points after the last element in the list.
> > +    pub fn cursor_back(&mut self) -> Cursor<'_, T, ID> {
> > +        // INVARIANT: `next` is allowed to be null.
> > +        Cursor {
> > +            next: core::ptr::null_mut(),
>
> I am slightly confused about why you need to track the beginning and end
> of the list. The cursor movement operations circle have wrapping
> semantics and the lists are circular. Could you remove some code by
> using this property?

I think the current API is much more intuitive. Yes, the list is
implemented in a circular manner, but you're not intended to think of
it that way. The linked list is a list of elements. With elements ABC
and cursors pointing between them, it makes sense that the cursor can
be |ABC, A|BC, AB|C, ABC|. In each case, you can add an element before
or after the cursor. To iterate the list, you keep calling `move_next`
until `next` returns `None`. That also makes sense. If the cursor
becomes circular, then you iterate by calling `next` until the next
element is the first element? Seems confusing to me.

I also don't think it's much less code. You still need to handle null
pointers because the list might be empty.

> > +            list: self,
> > +        }
> > +    }
> >
> > @@ -579,69 +574,211 @@ fn next(&mut self) -> Option<ArcBorrow<'a, T>> {
> >
> >  /// A cursor into a [`List`].
> >  ///
> > +/// A cursor always rests between two elements in the list. This means that a cursor has a previous
> > +/// and next element, but no current element. It also means that it's possible to have a cursor
> > +/// into an empty list.
> > +///
> >  /// # Invariants
> >  ///
> > -/// The `current` pointer points a value in `list`.
> > +/// The `next` pointer is null or points a value in `list`.
>
> Could you add an example of how to use this struct?
>
> Unrelated, but since you are at it, could you update the safety comment
> on first line in the `List::remove` function?

Okay, will look at this.

Alice