| 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
| ||
|
Message-ID: <87h65tem30.fsf@kernel.org>
Date: Mon, 20 Jan 2025 12:55:31 +0100
From: Andreas Hindborg <a.hindborg@...nel.org>
To: "Alice Ryhl" <aliceryhl@...gle.com>
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
Hi Alice,
This looks like a nice improvement!
"Alice Ryhl" <aliceryhl@...gle.com> writes:
> I've been using the linked list cursor for a few different things, and I
> find it inconvenient to use because all of the functions have signatures
> along the lines of `Self -> Option<Self>`. The root cause of these
> signatures is that the cursor points *at* an element, rather than
> *between* two elements.
>
> Thus, change the cursor API to point between two elements. This is
> inspired by the stdlib linked list (well, really by this guy [1]), which
> also uses cursors that point between elements.
>
> The `peek_*` methods returns a helper that lets you look at and
> optionally remove the element, as one common use-case of cursors is to
> iterate a list to look for an element, then remove that element.
>
> Another advantage is that this means you can now have a cursor into an
> empty list.
>
> Link: https://rust-unofficial.github.io/too-many-lists/sixth-cursors-intro.html [1]
> Signed-off-by: Alice Ryhl <aliceryhl@...gle.com>
> ---
> rust/kernel/list.rs | 325 +++++++++++++++++++++++++++++++-------------
> 1 file changed, 231 insertions(+), 94 deletions(-)
>
> diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs
> index fb93330f4af4..328d3e369d57 100644
> --- a/rust/kernel/list.rs
> +++ b/rust/kernel/list.rs
> @@ -245,8 +245,20 @@ pub fn is_empty(&self) -> bool {
> self.first.is_null()
> }
>
> - /// Add the provided item to the back of the list.
> - pub fn push_back(&mut self, item: ListArc<T, ID>) {
> + /// Inserts `item` before `next` in the cycle.
> + ///
> + /// Returns a pointer to the newly inserted element. Never changes `self.first` unless the list
> + /// is empty.
> + ///
> + /// # Safety
> + ///
> + /// * `next` must be an element in this list or null.
> + /// * if `next` is null, then the list must be empty.
> + unsafe fn insert_inner(
> + &mut self,
> + item: ListArc<T, ID>,
> + next: *mut ListLinksFields,
> + ) -> *mut ListLinksFields {
> let raw_item = ListArc::into_raw(item);
> // SAFETY:
> // * We just got `raw_item` from a `ListArc`, so it's in an `Arc`.
> @@ -259,16 +271,16 @@ pub fn push_back(&mut self, item: ListArc<T, ID>) {
> // SAFETY: We have not yet called `post_remove`, so `list_links` is still valid.
> let item = unsafe { ListLinks::fields(list_links) };
>
> - if self.first.is_null() {
> - self.first = item;
> + // Check if the list is empty.
> + if next.is_null() {
> // SAFETY: The caller just gave us ownership of these fields.
> // INVARIANT: A linked list with one item should be cyclic.
> unsafe {
> (*item).next = item;
> (*item).prev = item;
> }
> + self.first = item;
> } else {
> - let next = self.first;
> // SAFETY: By the type invariant, this pointer is valid or null. We just checked that
> // it's not null, so it must be valid.
> let prev = unsafe { (*next).prev };
> @@ -282,45 +294,24 @@ pub fn push_back(&mut self, item: ListArc<T, ID>) {
> (*next).prev = item;
> }
> }
> +
> + item
> }
>
> + /// Add the provided item to the back of the list.
> + pub fn push_back(&mut self, item: ListArc<T, ID>) {
> + // SAFETY:
> + // * `self.first` is null or in the list.
> + // * `self.first` is only null if the list is empty.
> + unsafe { self.insert_inner(item, self.first) };
> + }
> +
> /// Add the provided item to the front of the list.
> pub fn push_front(&mut self, item: ListArc<T, ID>) {
> - let raw_item = ListArc::into_raw(item);
> - // SAFETY:
> - // * We just got `raw_item` from a `ListArc`, so it's in an `Arc`.
> - // * If this requirement is violated, then the previous caller of `prepare_to_insert`
> - // violated the safety requirement that they can't give up ownership of the `ListArc`
> - // until they call `post_remove`.
> - // * We own the `ListArc`.
> - // * Removing items] from this list is always done using `remove_internal_inner`, which
> - // calls `post_remove` before giving up ownership.
> - let list_links = unsafe { T::prepare_to_insert(raw_item) };
> - // SAFETY: We have not yet called `post_remove`, so `list_links` is still valid.
> - let item = unsafe { ListLinks::fields(list_links) };
> -
> - if self.first.is_null() {
> - // SAFETY: The caller just gave us ownership of these fields.
> - // INVARIANT: A linked list with one item should be cyclic.
> - unsafe {
> - (*item).next = item;
> - (*item).prev = item;
> - }
> - } else {
> - let next = self.first;
> - // SAFETY: We just checked that `next` is non-null.
> - let prev = unsafe { (*next).prev };
> - // SAFETY: Pointers in a linked list are never dangling, and the caller just gave us
> - // ownership of the fields on `item`.
> - // INVARIANT: This correctly inserts `item` between `prev` and `next`.
> - unsafe {
> - (*item).next = next;
> - (*item).prev = prev;
> - (*prev).next = item;
> - (*next).prev = item;
> - }
> - }
> - self.first = item;
> + // SAFETY:
> + // * `self.first` is null or in the list.
> + // * `self.first` is only null if the list is empty.
> + self.first = unsafe { self.insert_inner(item, self.first) };
> }
>
> /// Removes the last item from this list.
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?
> @@ -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?
> + 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?
Best regards,
Andreas Hindborg
Powered by blists - more mailing lists