Message-ID: <Z5HkZGoYgrMu8I1M@boqun-archlinux>
Date: Wed, 22 Jan 2025 22:40:36 -0800
From: Boqun Feng <boqun.feng@...il.com>
To: Alice Ryhl <aliceryhl@...gle.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 v3 1/2] rust: list: extract common code for insertion

On Wed, Jan 22, 2025 at 03:00:17PM +0000, Alice Ryhl wrote:
> To prepare for a new cursor API that has the ability to insert elements
> into the list, extract the common code needed for this operation into a
> new `insert_inner` method.
> 
> Both `push_back` and `push_front` are updated to use the new function.
> 
> Reviewed-by: Andreas Hindborg <a.hindborg@...nel.org>
> Signed-off-by: Alice Ryhl <aliceryhl@...gle.com>

Reviewed-by: Boqun Feng <boqun.feng@...il.com>

Regards,
Boqun

> ---
>  rust/kernel/list.rs | 70 ++++++++++++++++++++++++-----------------------------
>  1 file changed, 32 insertions(+), 38 deletions(-)
> 
> diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs
> index fb93330f4af4..97b3599b7207 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,27 @@ 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) };
> +        // * `self.first` is null or in the list.
> +        // * `self.first` is only null if the list is empty.
> +        let new_elem = unsafe { self.insert_inner(item, self.first) };
>  
> -        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;
> +        // INVARIANT: `new_elem` is in the list because we just inserted it.
> +        self.first = new_elem;
>      }
>  
>      /// Removes the last item from this list.
> 
> -- 
> 2.48.0.rc2.279.g1de40edade-goog
> 

Powered by blists - more mailing lists