[v5] Additional methods for Vec

[PATCH v5 6/7] rust: alloc: add Vec::remove

Posted by Alice Ryhl 7 months, 2 weeks ago

This is needed by Rust Binder in the range allocator, and by upcoming
GPU drivers during firmware initialization.

Panics in the kernel are best avoided when possible, so an error is
returned if the index is out of bounds. An error type is used rather
than just returning Option<T> to let callers handle errors with ?.

Signed-off-by: Alice Ryhl <aliceryhl@google.com>
---
 rust/kernel/alloc/kvec.rs        | 42 +++++++++++++++++++++++++++++++++++++++-
 rust/kernel/alloc/kvec/errors.rs | 15 ++++++++++++++
 2 files changed, 56 insertions(+), 1 deletion(-)

diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
index 3298b3b0f32c70f3fe517fcb7af6b9922fea926b..8845e7694334b672476ff935580f3a9eb94d23fe 100644
--- a/rust/kernel/alloc/kvec.rs
+++ b/rust/kernel/alloc/kvec.rs
@@ -22,7 +22,7 @@
 };
 
 mod errors;
-pub use self::errors::PushError;
+pub use self::errors::{PushError, RemoveError};
 
 /// Create a [`KVec`] containing the arguments.
 ///
@@ -389,6 +389,46 @@ pub fn pop(&mut self) -> Option<T> {
         Some(unsafe { removed.read() })
     }
 
+    /// Removes the element at the given index.
+    ///
+    /// # Panics
+    ///
+    /// Panics if the index is out of bounds.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// let mut v = kernel::kvec![1, 2, 3]?;
+    /// assert_eq!(v.remove(1)?, 2);
+    /// assert_eq!(v, [1, 3]);
+    /// # Ok::<(), Error>(())
+    /// ```
+    pub fn remove(&mut self, i: usize) -> Result<T, RemoveError> {
+        let value = {
+            let value_ref = self.get(i).ok_or(RemoveError)?;
+            // INVARIANT: This breaks the invariants by invalidating the value at index `i`, but we
+            // restore the invariants below.
+            // SAFETY: The value at index `i` is valid, because otherwise we would have already
+            // failed with `RemoveError`.
+            unsafe { ptr::read(value_ref) }
+        };
+
+        // SAFETY: We checked that `i` is in-bounds.
+        let p = unsafe { self.as_mut_ptr().add(i) };
+
+        // INVARIANT: After this call, the invalid value is at the last slot, so the Vec invariants
+        // are restored after the below call to `dec_len(1)`.
+        // SAFETY: `p.add(1).add(self.len - i - 1)` is `i+1+len-i-1 == len` elements after the
+        // beginning of the vector, so this is in-bounds of the vector's allocation.
+        unsafe { ptr::copy(p.add(1), p, self.len - i - 1) };
+
+        // SAFETY: Since the check at the beginning of this call did not fail with `RemoveError`,
+        // the length is at least one.
+        unsafe { self.dec_len(1) };
+
+        Ok(value)
+    }
+
     /// Creates a new [`Vec`] instance with at least the given capacity.
     ///
     /// # Examples
diff --git a/rust/kernel/alloc/kvec/errors.rs b/rust/kernel/alloc/kvec/errors.rs
index 84c96ec5007ddc676283cbce07f4d670c3873c1e..06fe696e8bc6612a5e6aa2f6c28b685033acfa2f 100644
--- a/rust/kernel/alloc/kvec/errors.rs
+++ b/rust/kernel/alloc/kvec/errors.rs
@@ -21,3 +21,18 @@ fn from(_: PushError<T>) -> Error {
         EINVAL
     }
 }
+
+/// Error type for [`Vec::remove`].
+pub struct RemoveError;
+
+impl Debug for RemoveError {
+    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
+        write!(f, "Index out of bounds")
+    }
+}
+
+impl From<RemoveError> for Error {
+    fn from(_: RemoveError) -> Error {
+        EINVAL
+    }
+}

-- 
2.49.0.967.g6a0df3ecc3-goog

Re: [PATCH v5 6/7] rust: alloc: add Vec::remove

Posted by Benno Lossin 7 months, 1 week ago

On Fri May 2, 2025 at 3:19 PM CEST, Alice Ryhl wrote:
> This is needed by Rust Binder in the range allocator, and by upcoming
> GPU drivers during firmware initialization.
>
> Panics in the kernel are best avoided when possible, so an error is
> returned if the index is out of bounds. An error type is used rather
> than just returning Option<T> to let callers handle errors with ?.
>
> Signed-off-by: Alice Ryhl <aliceryhl@google.com>

One follow-up comment below. With the `# Panics` section removed:

Reviewed-by: Benno Lossin <lossin@kernel.org>

[...]

> diff --git a/rust/kernel/alloc/kvec/errors.rs b/rust/kernel/alloc/kvec/errors.rs
> index 84c96ec5007ddc676283cbce07f4d670c3873c1e..06fe696e8bc6612a5e6aa2f6c28b685033acfa2f 100644
> --- a/rust/kernel/alloc/kvec/errors.rs
> +++ b/rust/kernel/alloc/kvec/errors.rs
> @@ -21,3 +21,18 @@ fn from(_: PushError<T>) -> Error {
>          EINVAL
>      }
>  }
> +
> +/// Error type for [`Vec::remove`].
> +pub struct RemoveError;

Would it make sense as a follow-up to store the index that was accessed?

---
Cheers,
Benno

> +
> +impl Debug for RemoveError {
> +    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
> +        write!(f, "Index out of bounds")
> +    }
> +}
> +
> +impl From<RemoveError> for Error {
> +    fn from(_: RemoveError) -> Error {
> +        EINVAL
> +    }
> +}

Re: [PATCH v5 6/7] rust: alloc: add Vec::remove

Posted by Alice Ryhl 7 months, 1 week ago

On Wed, May 07, 2025 at 01:44:30PM +0200, Benno Lossin wrote:
> On Fri May 2, 2025 at 3:19 PM CEST, Alice Ryhl wrote:
> > This is needed by Rust Binder in the range allocator, and by upcoming
> > GPU drivers during firmware initialization.
> >
> > Panics in the kernel are best avoided when possible, so an error is
> > returned if the index is out of bounds. An error type is used rather
> > than just returning Option<T> to let callers handle errors with ?.
> >
> > Signed-off-by: Alice Ryhl <aliceryhl@google.com>
> 
> One follow-up comment below. With the `# Panics` section removed:
> 
> Reviewed-by: Benno Lossin <lossin@kernel.org>

Thanks!

> > diff --git a/rust/kernel/alloc/kvec/errors.rs b/rust/kernel/alloc/kvec/errors.rs
> > index 84c96ec5007ddc676283cbce07f4d670c3873c1e..06fe696e8bc6612a5e6aa2f6c28b685033acfa2f 100644
> > --- a/rust/kernel/alloc/kvec/errors.rs
> > +++ b/rust/kernel/alloc/kvec/errors.rs
> > @@ -21,3 +21,18 @@ fn from(_: PushError<T>) -> Error {
> >          EINVAL
> >      }
> >  }
> > +
> > +/// Error type for [`Vec::remove`].
> > +pub struct RemoveError;
> 
> Would it make sense as a follow-up to store the index that was accessed?

Usually I think we would only store the information that the caller
doesn't already know?

Alice

Re: [PATCH v5 6/7] rust: alloc: add Vec::remove

Posted by Alexandre Courbot 7 months, 2 weeks ago

Hi Alice,

On Fri May 2, 2025 at 10:19 PM JST, Alice Ryhl wrote:
> This is needed by Rust Binder in the range allocator, and by upcoming
> GPU drivers during firmware initialization.
>
> Panics in the kernel are best avoided when possible, so an error is
> returned if the index is out of bounds. An error type is used rather
> than just returning Option<T> to let callers handle errors with ?.
>
> Signed-off-by: Alice Ryhl <aliceryhl@google.com>
> ---
>  rust/kernel/alloc/kvec.rs        | 42 +++++++++++++++++++++++++++++++++++++++-
>  rust/kernel/alloc/kvec/errors.rs | 15 ++++++++++++++
>  2 files changed, 56 insertions(+), 1 deletion(-)
>
> diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
> index 3298b3b0f32c70f3fe517fcb7af6b9922fea926b..8845e7694334b672476ff935580f3a9eb94d23fe 100644
> --- a/rust/kernel/alloc/kvec.rs
> +++ b/rust/kernel/alloc/kvec.rs
> @@ -22,7 +22,7 @@
>  };
>  
>  mod errors;
> -pub use self::errors::PushError;
> +pub use self::errors::{PushError, RemoveError};
>  
>  /// Create a [`KVec`] containing the arguments.
>  ///
> @@ -389,6 +389,46 @@ pub fn pop(&mut self) -> Option<T> {
>          Some(unsafe { removed.read() })
>      }
>  
> +    /// Removes the element at the given index.
> +    ///
> +    /// # Panics
> +    ///
> +    /// Panics if the index is out of bounds.

According to the commit log (and the code of the method) I think this
panic section is not valid anymore?

Re: [PATCH v5 6/7] rust: alloc: add Vec::remove

Posted by Alexandre Courbot 7 months, 2 weeks ago

On Wed May 7, 2025 at 2:30 PM JST, Alexandre Courbot wrote:
> Hi Alice,
>
> On Fri May 2, 2025 at 10:19 PM JST, Alice Ryhl wrote:
>> This is needed by Rust Binder in the range allocator, and by upcoming
>> GPU drivers during firmware initialization.
>>
>> Panics in the kernel are best avoided when possible, so an error is
>> returned if the index is out of bounds. An error type is used rather
>> than just returning Option<T> to let callers handle errors with ?.
>>
>> Signed-off-by: Alice Ryhl <aliceryhl@google.com>
>> ---
>>  rust/kernel/alloc/kvec.rs        | 42 +++++++++++++++++++++++++++++++++++++++-
>>  rust/kernel/alloc/kvec/errors.rs | 15 ++++++++++++++
>>  2 files changed, 56 insertions(+), 1 deletion(-)
>>
>> diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
>> index 3298b3b0f32c70f3fe517fcb7af6b9922fea926b..8845e7694334b672476ff935580f3a9eb94d23fe 100644
>> --- a/rust/kernel/alloc/kvec.rs
>> +++ b/rust/kernel/alloc/kvec.rs
>> @@ -22,7 +22,7 @@
>>  };
>>  
>>  mod errors;
>> -pub use self::errors::PushError;
>> +pub use self::errors::{PushError, RemoveError};
>>  
>>  /// Create a [`KVec`] containing the arguments.
>>  ///
>> @@ -389,6 +389,46 @@ pub fn pop(&mut self) -> Option<T> {
>>          Some(unsafe { removed.read() })
>>      }
>>  
>> +    /// Removes the element at the given index.
>> +    ///
>> +    /// # Panics
>> +    ///
>> +    /// Panics if the index is out of bounds.
>
> According to the commit log (and the code of the method) I think this
> panic section is not valid anymore?

Oops never mind, I didn't notice Danilo already pointed this out. >_<

Re: [PATCH v5 6/7] rust: alloc: add Vec::remove'

Posted by Alice Ryhl 7 months, 2 weeks ago

On Wed, May 07, 2025 at 02:32:10PM +0900, Alexandre Courbot wrote:
> On Wed May 7, 2025 at 2:30 PM JST, Alexandre Courbot wrote:
> > On Fri May 2, 2025 at 10:19 PM JST, Alice Ryhl wrote:
> >> +    /// Removes the element at the given index.
> >> +    ///
> >> +    /// # Panics
> >> +    ///
> >> +    /// Panics if the index is out of bounds.
> >
> > According to the commit log (and the code of the method) I think this
> > panic section is not valid anymore?
> 
> Oops never mind, I didn't notice Danilo already pointed this out. >_<

Thanks for taking a look!

Alice

Re: [PATCH v5 6/7] rust: alloc: add Vec::remove

Posted by Danilo Krummrich 7 months, 2 weeks ago

On Fri, May 02, 2025 at 01:19:34PM +0000, Alice Ryhl wrote:
> +    /// Removes the element at the given index.
> +    ///
> +    /// # Panics
> +    ///
> +    /// Panics if the index is out of bounds.

This isn't the case anymore. Unless you send a new version, I'll fix it up when
I apply the series.