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

Signed-off-by: Alice Ryhl <aliceryhl@google.com>
---
 rust/kernel/alloc/kvec.rs | 36 ++++++++++++++++++++++++++++++++++++
 1 file changed, 36 insertions(+)

diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
index 357f5a37c7b1d15b709a10c162292841eed0e376..0682108951675cbee05faa130e5a9ce72fc343ba 100644
--- a/rust/kernel/alloc/kvec.rs
+++ b/rust/kernel/alloc/kvec.rs
@@ -386,6 +386,42 @@ 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) -> T {
+        // INVARIANT: This breaks the invariants by invalidating the value at index `i`, but we
+        // restore the invariants below.
+        // SAFETY: Since `&self[i]` did not result in a panic, the value at index `i` is valid.
+        let value = unsafe { ptr::read(&self[i]) };
+
+        // 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 access at the beginning of this call did not panic, the length is at
+        // least one.
+        unsafe { self.dec_len(1) };
+
+        value
+    }
+
     /// Creates a new [`Vec`] instance with at least the given capacity.
     ///
     /// # Examples

-- 
2.49.0.901.g37484f566f-goog

On Tue, Apr 29, 2025 at 02:44:26PM +0000, Alice Ryhl wrote:
> This is needed by Rust Binder in the range allocator, and by upcoming
> GPU drivers during firmware initialization.
> 
> Signed-off-by: Alice Ryhl <aliceryhl@google.com>
> ---
>  rust/kernel/alloc/kvec.rs | 36 ++++++++++++++++++++++++++++++++++++
>  1 file changed, 36 insertions(+)
> 
> diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
> index 357f5a37c7b1d15b709a10c162292841eed0e376..0682108951675cbee05faa130e5a9ce72fc343ba 100644
> --- a/rust/kernel/alloc/kvec.rs
> +++ b/rust/kernel/alloc/kvec.rs
> @@ -386,6 +386,42 @@ 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.

Let's check for the index and return an error instead. I know we also can't
prevent OOB index access panics for e.g. slices, but here we can control it.

On Wed, Apr 30, 2025 at 06:28:48PM +0200, Danilo Krummrich wrote:
> On Tue, Apr 29, 2025 at 02:44:26PM +0000, Alice Ryhl wrote:
> > This is needed by Rust Binder in the range allocator, and by upcoming
> > GPU drivers during firmware initialization.
> > 
> > Signed-off-by: Alice Ryhl <aliceryhl@google.com>
> > ---
> >  rust/kernel/alloc/kvec.rs | 36 ++++++++++++++++++++++++++++++++++++
> >  1 file changed, 36 insertions(+)
> > 
> > diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
> > index 357f5a37c7b1d15b709a10c162292841eed0e376..0682108951675cbee05faa130e5a9ce72fc343ba 100644
> > --- a/rust/kernel/alloc/kvec.rs
> > +++ b/rust/kernel/alloc/kvec.rs
> > @@ -386,6 +386,42 @@ 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.
> 
> Let's check for the index and return an error instead. I know we also can't
> prevent OOB index access panics for e.g. slices, but here we can control it.

Okay, I will return an `Option<T>`.

Alice

On Thu, May 01, 2025 at 11:10:46AM +0000, Alice Ryhl wrote:
> On Wed, Apr 30, 2025 at 06:28:48PM +0200, Danilo Krummrich wrote:
> > On Tue, Apr 29, 2025 at 02:44:26PM +0000, Alice Ryhl wrote:
> > > This is needed by Rust Binder in the range allocator, and by upcoming
> > > GPU drivers during firmware initialization.
> > > 
> > > Signed-off-by: Alice Ryhl <aliceryhl@google.com>
> > > ---
> > >  rust/kernel/alloc/kvec.rs | 36 ++++++++++++++++++++++++++++++++++++
> > >  1 file changed, 36 insertions(+)
> > > 
> > > diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
> > > index 357f5a37c7b1d15b709a10c162292841eed0e376..0682108951675cbee05faa130e5a9ce72fc343ba 100644
> > > --- a/rust/kernel/alloc/kvec.rs
> > > +++ b/rust/kernel/alloc/kvec.rs
> > > @@ -386,6 +386,42 @@ 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.
> > 
> > Let's check for the index and return an error instead. I know we also can't
> > prevent OOB index access panics for e.g. slices, but here we can control it.
> 
> Okay, I will return an `Option<T>`.

Hm...to me this looks like it is a real error condition rather than something
optional.

What does it mean if remove() returns None? It really means that the given index
is out of bounds, which is never correct behavior for the caller of the API.

So, I'd argue that None is an unexpected return value for a caller and needs to
be handled in an error path, for which returning a Result is much more
ergonomic and correct, since Result can describe the reason, i.e. EINVAL,
whereas with Option a caller would need to pick an error code itself.

On Thu, May 01, 2025 at 01:40:36PM +0200, Danilo Krummrich wrote:
> On Thu, May 01, 2025 at 11:10:46AM +0000, Alice Ryhl wrote:
> > On Wed, Apr 30, 2025 at 06:28:48PM +0200, Danilo Krummrich wrote:
> > > On Tue, Apr 29, 2025 at 02:44:26PM +0000, Alice Ryhl wrote:
> > > > This is needed by Rust Binder in the range allocator, and by upcoming
> > > > GPU drivers during firmware initialization.
> > > > 
> > > > Signed-off-by: Alice Ryhl <aliceryhl@google.com>
> > > > ---
> > > >  rust/kernel/alloc/kvec.rs | 36 ++++++++++++++++++++++++++++++++++++
> > > >  1 file changed, 36 insertions(+)
> > > > 
> > > > diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
> > > > index 357f5a37c7b1d15b709a10c162292841eed0e376..0682108951675cbee05faa130e5a9ce72fc343ba 100644
> > > > --- a/rust/kernel/alloc/kvec.rs
> > > > +++ b/rust/kernel/alloc/kvec.rs
> > > > @@ -386,6 +386,42 @@ 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.
> > > 
> > > Let's check for the index and return an error instead. I know we also can't
> > > prevent OOB index access panics for e.g. slices, but here we can control it.
> > 
> > Okay, I will return an `Option<T>`.
> 
> Hm...to me this looks like it is a real error condition rather than something
> optional.
> 
> What does it mean if remove() returns None? It really means that the given index
> is out of bounds, which is never correct behavior for the caller of the API.
> 
> So, I'd argue that None is an unexpected return value for a caller and needs to
> be handled in an error path, for which returning a Result is much more
> ergonomic and correct, since Result can describe the reason, i.e. EINVAL,
> whereas with Option a caller would need to pick an error code itself.

Fair enough. I think a dedicated error type is probably reasonable here,
but sure.

Alice