[PATCH v3 0/7] Additional methods for Vec

[PATCH v3 0/7] Additional methods for Vec

[Alice Ryhl]

This adds various Vec methods. Some of them are needed by Rust Binder,
and others are needed in other places. Each commit explains where it is
needed.

This series is based on top of alloc-next and rust: alloc: split
`Vec::set_len` into `Vec::{inc,dec}_len`
https://lore.kernel.org/rust-for-linux/20250416-vec-set-len-v4-0-112b222604cd@gmail.com/

Signed-off-by: Alice Ryhl <aliceryhl@google.com>
---
Changes in v3:
- Rebase on split `Vec::set_len` into `Vec::{inc,dec}_len`.
- Various modifications to work with inc/dec_len instead of set_len,
  with some Reviewed-by's dropped due to this.
- Move push_within_capacity impl into an unchecked variant.
- Link to v2: https://lore.kernel.org/r/20250321-vec-methods-v2-0-6d9c8a4634cb@google.com

Changes in v2:
- Add two more methods that I needed.
- Introduce some uses of set_len.
- Add example to retain.
- Simplify pop.
- Adjust 11 to 10 in push_within_capacity example.
- Link to v1: https://lore.kernel.org/r/20250320-vec-methods-v1-0-7dff5cf25fe8@google.com

---
Alice Ryhl (7):
      rust: alloc: add Vec::clear
      rust: alloc: add Vec::pop
      rust: alloc: add Vec::push_within_capacity
      rust: alloc: add Vec::drain_all
      rust: alloc: add Vec::retain
      rust: alloc: add Vec::remove
      rust: alloc: add Vec::insert_within_capacity

 rust/kernel/alloc/kvec.rs | 241 +++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 239 insertions(+), 2 deletions(-)
---
base-commit: 1569d07593b986b690eec0bd85a632b6712f4c2e
change-id: 20250320-vec-methods-adfa41e55311

Best regards,
-- 
Alice Ryhl <aliceryhl@google.com>

[PATCH v3 1/7] rust: alloc: add Vec::clear

[Alice Ryhl]

Our custom Vec type is missing the stdlib method `clear`, thus add it.
It will be used in the miscdevice sample.

Reviewed-by: Benno Lossin <benno.lossin@proton.me>
Reviewed-by: Tamir Duberstein <tamird@gmail.com>
Signed-off-by: Alice Ryhl <aliceryhl@google.com>
---
 rust/kernel/alloc/kvec.rs | 20 ++++++++++++++++++++
 1 file changed, 20 insertions(+)

diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
index 5798e2c890a2140a12303706578ffa2a85423167..412a2fe3ce79a0681175bf358e8e0f628e77e875 100644
--- a/rust/kernel/alloc/kvec.rs
+++ b/rust/kernel/alloc/kvec.rs
@@ -413,6 +413,26 @@ pub fn into_raw_parts(self) -> (*mut T, usize, usize) {
         (ptr, len, capacity)
     }
 
+    /// Clears the vector, removing all values.
+    ///
+    /// Note that this method has no effect on the allocated capacity
+    /// of the vector.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// let mut v = kernel::kvec![1, 2, 3]?;
+    ///
+    /// v.clear();
+    ///
+    /// assert!(v.is_empty());
+    /// # Ok::<(), Error>(())
+    /// ```
+    #[inline]
+    pub fn clear(&mut self) {
+        self.truncate(0);
+    }
+
     /// Ensures that the capacity exceeds the length by at least `additional` elements.
     ///
     /// # Examples

-- 
2.49.0.805.g082f7c87e0-goog

[PATCH v3 2/7] rust: alloc: add Vec::pop

[Alice Ryhl]

This introduces a basic method that our custom Vec is missing. I expect
that it will be used in many places, but at the time of writing, Rust
Binder has six calls to Vec::pop.

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

diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
index 412a2fe3ce79a0681175bf358e8e0f628e77e875..ebca0cfd31c67f3ce13c4825d7039e34bb54f4d4 100644
--- a/rust/kernel/alloc/kvec.rs
+++ b/rust/kernel/alloc/kvec.rs
@@ -320,6 +320,37 @@ pub fn push(&mut self, v: T, flags: Flags) -> Result<(), AllocError> {
         Ok(())
     }
 
+    /// Removes the last element from a vector and returns it, or `None` if it is empty.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// let mut v = KVec::new();
+    /// v.push(1, GFP_KERNEL)?;
+    /// v.push(2, GFP_KERNEL)?;
+    /// assert_eq!(&v, &[1, 2]);
+    ///
+    /// assert_eq!(v.pop(), Some(2));
+    /// assert_eq!(v.pop(), Some(1));
+    /// assert_eq!(v.pop(), None);
+    /// # Ok::<(), Error>(())
+    /// ```
+    pub fn pop(&mut self) -> Option<T> {
+        if self.is_empty() {
+            return None;
+        }
+
+        let removed: *mut T = {
+            // SAFETY: We just checked that the length is at least one.
+            let slice = unsafe { self.dec_len(1) };
+            // SAFETY: The argument to `dec_len` was 1 so this returns a slice of length 1.
+            unsafe { slice.get_unchecked_mut(0) }
+        };
+
+        // SAFETY: The guarantees of `dec_len` allow us to take ownership of this value.
+        Some(unsafe { removed.read() })
+    }
+
     /// Creates a new [`Vec`] instance with at least the given capacity.
     ///
     /// # Examples

-- 
2.49.0.805.g082f7c87e0-goog

Re: [PATCH v3 2/7] rust: alloc: add Vec::pop

[Tamir Duberstein]

On Tue, Apr 22, 2025 at 5:53 AM Alice Ryhl <aliceryhl@google.com> wrote:
>
> This introduces a basic method that our custom Vec is missing. I expect
> that it will be used in many places, but at the time of writing, Rust
> Binder has six calls to Vec::pop.
>
> Signed-off-by: Alice Ryhl <aliceryhl@google.com>

Could this be written in terms of `remove`?

Re: [PATCH v3 2/7] rust: alloc: add Vec::pop

[Alice Ryhl]

On Wed, Apr 23, 2025 at 11:42:52AM -0400, Tamir Duberstein wrote:
> On Tue, Apr 22, 2025 at 5:53 AM Alice Ryhl <aliceryhl@google.com> wrote:
> >
> > This introduces a basic method that our custom Vec is missing. I expect
> > that it will be used in many places, but at the time of writing, Rust
> > Binder has six calls to Vec::pop.
> >
> > Signed-off-by: Alice Ryhl <aliceryhl@google.com>
> 
> Could this be written in terms of `remove`?

The `remove` method has a lot of logic to move around elements, so I'm
not sure we would want to do that.

Alice

Re: [PATCH v3 2/7] rust: alloc: add Vec::pop

[Tamir Duberstein]

On Thu, Apr 24, 2025 at 7:48 AM Alice Ryhl <aliceryhl@google.com> wrote:
>
> On Wed, Apr 23, 2025 at 11:42:52AM -0400, Tamir Duberstein wrote:
> > On Tue, Apr 22, 2025 at 5:53 AM Alice Ryhl <aliceryhl@google.com> wrote:
> > >
> > > This introduces a basic method that our custom Vec is missing. I expect
> > > that it will be used in many places, but at the time of writing, Rust
> > > Binder has six calls to Vec::pop.
> > >
> > > Signed-off-by: Alice Ryhl <aliceryhl@google.com>
> >
> > Could this be written in terms of `remove`?
>
> The `remove` method has a lot of logic to move around elements, so I'm
> not sure we would want to do that.

Wouldn't we want `remove(len-1)` to avoid that logic anyhow?

[PATCH v3 3/7] rust: alloc: add Vec::push_within_capacity

[Alice Ryhl]

This introduces a new method called `push_within_capacity` for appending
to a vector without attempting to allocate if the capacity is full. Rust
Binder will use this in various places to safely push to a vector while
holding a spinlock.

The implementation is moved to a push_within_capacity_unchecked method.
This is preferred over having push() call push_within_capacity()
followed by an unwrap_unchecked() for simpler unsafe.

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

diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
index ebca0cfd31c67f3ce13c4825d7039e34bb54f4d4..a005a295262cb1e8b7c118125ffa07ae252e257c 100644
--- a/rust/kernel/alloc/kvec.rs
+++ b/rust/kernel/alloc/kvec.rs
@@ -307,17 +307,52 @@ pub fn spare_capacity_mut(&mut self) -> &mut [MaybeUninit<T>] {
     /// ```
     pub fn push(&mut self, v: T, flags: Flags) -> Result<(), AllocError> {
         self.reserve(1, flags)?;
+        // SAFETY: The call to `reserve` was successful, so the capacity is at least one greater
+        // than the length.
+        unsafe { self.push_within_capacity_unchecked(v) };
+        Ok(())
+    }
+
+    /// Appends an element to the back of the [`Vec`] instance without reallocating.
+    ///
+    /// Fails if the vector does not have capacity for the new element.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// let mut v = KVec::with_capacity(10, GFP_KERNEL);
+    /// for i in 0..10 {
+    ///     v.push_within_capacity(i).unwrap();
+    /// }
+    ///
+    /// assert!(v.push_within_capacity(10).is_err());
+    /// # Ok::<(), Error>(())
+    /// ```
+    pub fn push_within_capacity(&mut self, v: T) -> Result<(), T> {
+        if self.len() < self.capacity() {
+            // SAFETY: The length is less than the capacity.
+            unsafe { self.push_within_capacity_unchecked(v) };
+            Ok(())
+        } else {
+            Err(v)
+        }
+    }
 
+    /// Appends an element to the back of the [`Vec`] instance without reallocating.
+    ///
+    /// # Safety
+    ///
+    /// The length must be less than the capacity.
+    pub unsafe fn push_within_capacity_unchecked(&mut self, v: T) {
         let spare = self.spare_capacity_mut();
 
         // SAFETY: The call to `reserve` was successful so the spare capacity is at least 1.
         unsafe { spare.get_unchecked_mut(0) }.write(v);
 
         // SAFETY: We just initialised the first spare entry, so it is safe to increase the length
-        // by 1. We also know that the new length is <= capacity because of the previous call to
-        // `reserve` above.
+        // by 1. We also know that the new length is <= capacity because the caller guarantees that
+        // the length is less than the capacity at the beginning of this function.
         unsafe { self.inc_len(1) };
-        Ok(())
     }
 
     /// Removes the last element from a vector and returns it, or `None` if it is empty.

-- 
2.49.0.805.g082f7c87e0-goog

Re: [PATCH v3 3/7] rust: alloc: add Vec::push_within_capacity

[Boqun Feng]

On Tue, Apr 22, 2025 at 09:52:18AM +0000, Alice Ryhl wrote:
> This introduces a new method called `push_within_capacity` for appending
> to a vector without attempting to allocate if the capacity is full. Rust
> Binder will use this in various places to safely push to a vector while
> holding a spinlock.
> 
> The implementation is moved to a push_within_capacity_unchecked method.
> This is preferred over having push() call push_within_capacity()
> followed by an unwrap_unchecked() for simpler unsafe.
> 
> Signed-off-by: Alice Ryhl <aliceryhl@google.com>
> ---
>  rust/kernel/alloc/kvec.rs | 41 ++++++++++++++++++++++++++++++++++++++---
>  1 file changed, 38 insertions(+), 3 deletions(-)
> 
> diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
> index ebca0cfd31c67f3ce13c4825d7039e34bb54f4d4..a005a295262cb1e8b7c118125ffa07ae252e257c 100644
> --- a/rust/kernel/alloc/kvec.rs
> +++ b/rust/kernel/alloc/kvec.rs
> @@ -307,17 +307,52 @@ pub fn spare_capacity_mut(&mut self) -> &mut [MaybeUninit<T>] {
>      /// ```
>      pub fn push(&mut self, v: T, flags: Flags) -> Result<(), AllocError> {
>          self.reserve(1, flags)?;
> +        // SAFETY: The call to `reserve` was successful, so the capacity is at least one greater
> +        // than the length.
> +        unsafe { self.push_within_capacity_unchecked(v) };
> +        Ok(())
> +    }
> +
> +    /// Appends an element to the back of the [`Vec`] instance without reallocating.
> +    ///
> +    /// Fails if the vector does not have capacity for the new element.
> +    ///
> +    /// # Examples
> +    ///
> +    /// ```
> +    /// let mut v = KVec::with_capacity(10, GFP_KERNEL);

Should be:

    /// let mut v = KVec::with_capacity(10, GFP_KERNEL)?;

, right? I.e. a question mark is missing.

The rest looks good to me.

Regards,
Boqun

> +    /// for i in 0..10 {
> +    ///     v.push_within_capacity(i).unwrap();
> +    /// }
> +    ///
> +    /// assert!(v.push_within_capacity(10).is_err());
> +    /// # Ok::<(), Error>(())
> +    /// ```
> +    pub fn push_within_capacity(&mut self, v: T) -> Result<(), T> {
> +        if self.len() < self.capacity() {
> +            // SAFETY: The length is less than the capacity.
> +            unsafe { self.push_within_capacity_unchecked(v) };
> +            Ok(())
> +        } else {
> +            Err(v)
> +        }
> +    }
>  
> +    /// Appends an element to the back of the [`Vec`] instance without reallocating.
> +    ///
> +    /// # Safety
> +    ///
> +    /// The length must be less than the capacity.
> +    pub unsafe fn push_within_capacity_unchecked(&mut self, v: T) {
>          let spare = self.spare_capacity_mut();
>  
>          // SAFETY: The call to `reserve` was successful so the spare capacity is at least 1.
>          unsafe { spare.get_unchecked_mut(0) }.write(v);
>  
>          // SAFETY: We just initialised the first spare entry, so it is safe to increase the length
> -        // by 1. We also know that the new length is <= capacity because of the previous call to
> -        // `reserve` above.
> +        // by 1. We also know that the new length is <= capacity because the caller guarantees that
> +        // the length is less than the capacity at the beginning of this function.
>          unsafe { self.inc_len(1) };
> -        Ok(())
>      }
>  
>      /// Removes the last element from a vector and returns it, or `None` if it is empty.
> 
> -- 
> 2.49.0.805.g082f7c87e0-goog
> 
> 

Re: [PATCH v3 3/7] rust: alloc: add Vec::push_within_capacity

[Alice Ryhl]

On Tue, Apr 22, 2025 at 02:29:53PM -0700, Boqun Feng wrote:
> On Tue, Apr 22, 2025 at 09:52:18AM +0000, Alice Ryhl wrote:
> > This introduces a new method called `push_within_capacity` for appending
> > to a vector without attempting to allocate if the capacity is full. Rust
> > Binder will use this in various places to safely push to a vector while
> > holding a spinlock.
> > 
> > The implementation is moved to a push_within_capacity_unchecked method.
> > This is preferred over having push() call push_within_capacity()
> > followed by an unwrap_unchecked() for simpler unsafe.
> > 
> > Signed-off-by: Alice Ryhl <aliceryhl@google.com>
> > ---
> >  rust/kernel/alloc/kvec.rs | 41 ++++++++++++++++++++++++++++++++++++++---
> >  1 file changed, 38 insertions(+), 3 deletions(-)
> > 
> > diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
> > index ebca0cfd31c67f3ce13c4825d7039e34bb54f4d4..a005a295262cb1e8b7c118125ffa07ae252e257c 100644
> > --- a/rust/kernel/alloc/kvec.rs
> > +++ b/rust/kernel/alloc/kvec.rs
> > @@ -307,17 +307,52 @@ pub fn spare_capacity_mut(&mut self) -> &mut [MaybeUninit<T>] {
> >      /// ```
> >      pub fn push(&mut self, v: T, flags: Flags) -> Result<(), AllocError> {
> >          self.reserve(1, flags)?;
> > +        // SAFETY: The call to `reserve` was successful, so the capacity is at least one greater
> > +        // than the length.
> > +        unsafe { self.push_within_capacity_unchecked(v) };
> > +        Ok(())
> > +    }
> > +
> > +    /// Appends an element to the back of the [`Vec`] instance without reallocating.
> > +    ///
> > +    /// Fails if the vector does not have capacity for the new element.
> > +    ///
> > +    /// # Examples
> > +    ///
> > +    /// ```
> > +    /// let mut v = KVec::with_capacity(10, GFP_KERNEL);
> 
> Should be:
> 
>     /// let mut v = KVec::with_capacity(10, GFP_KERNEL)?;
> 
> , right? I.e. a question mark is missing.
> 
> The rest looks good to me.

Will be fixed in the next version. Let me know if you want me to add
your Reviewed-by tag with this fixed?

Alice

Re: [PATCH v3 3/7] rust: alloc: add Vec::push_within_capacity

[Boqun Feng]

On Wed, Apr 23, 2025 at 08:55:34AM +0000, Alice Ryhl wrote:
> On Tue, Apr 22, 2025 at 02:29:53PM -0700, Boqun Feng wrote:
> > On Tue, Apr 22, 2025 at 09:52:18AM +0000, Alice Ryhl wrote:
> > > This introduces a new method called `push_within_capacity` for appending
> > > to a vector without attempting to allocate if the capacity is full. Rust
> > > Binder will use this in various places to safely push to a vector while
> > > holding a spinlock.
> > > 
> > > The implementation is moved to a push_within_capacity_unchecked method.
> > > This is preferred over having push() call push_within_capacity()
> > > followed by an unwrap_unchecked() for simpler unsafe.
> > > 
> > > Signed-off-by: Alice Ryhl <aliceryhl@google.com>
> > > ---
> > >  rust/kernel/alloc/kvec.rs | 41 ++++++++++++++++++++++++++++++++++++++---
> > >  1 file changed, 38 insertions(+), 3 deletions(-)
> > > 
> > > diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
> > > index ebca0cfd31c67f3ce13c4825d7039e34bb54f4d4..a005a295262cb1e8b7c118125ffa07ae252e257c 100644
> > > --- a/rust/kernel/alloc/kvec.rs
> > > +++ b/rust/kernel/alloc/kvec.rs
> > > @@ -307,17 +307,52 @@ pub fn spare_capacity_mut(&mut self) -> &mut [MaybeUninit<T>] {
> > >      /// ```
> > >      pub fn push(&mut self, v: T, flags: Flags) -> Result<(), AllocError> {
> > >          self.reserve(1, flags)?;
> > > +        // SAFETY: The call to `reserve` was successful, so the capacity is at least one greater
> > > +        // than the length.
> > > +        unsafe { self.push_within_capacity_unchecked(v) };
> > > +        Ok(())
> > > +    }
> > > +
> > > +    /// Appends an element to the back of the [`Vec`] instance without reallocating.
> > > +    ///
> > > +    /// Fails if the vector does not have capacity for the new element.
> > > +    ///
> > > +    /// # Examples
> > > +    ///
> > > +    /// ```
> > > +    /// let mut v = KVec::with_capacity(10, GFP_KERNEL);
> > 
> > Should be:
> > 
> >     /// let mut v = KVec::with_capacity(10, GFP_KERNEL)?;
> > 
> > , right? I.e. a question mark is missing.
> > 
> > The rest looks good to me.
> 
> Will be fixed in the next version. Let me know if you want me to add
> your Reviewed-by tag with this fixed?
> 

Sure, feel free to add

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

Regards,
Boqun

> Alice

Re: [PATCH v3 3/7] rust: alloc: add Vec::push_within_capacity

[Tamir Duberstein]

On Tue, Apr 22, 2025 at 5:53 AM Alice Ryhl <aliceryhl@google.com> wrote:
>
> This introduces a new method called `push_within_capacity` for appending
> to a vector without attempting to allocate if the capacity is full. Rust
> Binder will use this in various places to safely push to a vector while
> holding a spinlock.
>
> The implementation is moved to a push_within_capacity_unchecked method.
> This is preferred over having push() call push_within_capacity()
> followed by an unwrap_unchecked() for simpler unsafe.
>
> Signed-off-by: Alice Ryhl <aliceryhl@google.com>
> ---
>  rust/kernel/alloc/kvec.rs | 41 ++++++++++++++++++++++++++++++++++++++---
>  1 file changed, 38 insertions(+), 3 deletions(-)
>
> diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
> index ebca0cfd31c67f3ce13c4825d7039e34bb54f4d4..a005a295262cb1e8b7c118125ffa07ae252e257c 100644
> --- a/rust/kernel/alloc/kvec.rs
> +++ b/rust/kernel/alloc/kvec.rs
> @@ -307,17 +307,52 @@ pub fn spare_capacity_mut(&mut self) -> &mut [MaybeUninit<T>] {
>      /// ```
>      pub fn push(&mut self, v: T, flags: Flags) -> Result<(), AllocError> {
>          self.reserve(1, flags)?;
> +        // SAFETY: The call to `reserve` was successful, so the capacity is at least one greater
> +        // than the length.
> +        unsafe { self.push_within_capacity_unchecked(v) };
> +        Ok(())
> +    }
> +
> +    /// Appends an element to the back of the [`Vec`] instance without reallocating.
> +    ///
> +    /// Fails if the vector does not have capacity for the new element.
> +    ///
> +    /// # Examples
> +    ///
> +    /// ```
> +    /// let mut v = KVec::with_capacity(10, GFP_KERNEL);
> +    /// for i in 0..10 {
> +    ///     v.push_within_capacity(i).unwrap();
> +    /// }
> +    ///
> +    /// assert!(v.push_within_capacity(10).is_err());
> +    /// # Ok::<(), Error>(())
> +    /// ```
> +    pub fn push_within_capacity(&mut self, v: T) -> Result<(), T> {
> +        if self.len() < self.capacity() {
> +            // SAFETY: The length is less than the capacity.
> +            unsafe { self.push_within_capacity_unchecked(v) };
> +            Ok(())
> +        } else {
> +            Err(v)
> +        }
> +    }
>
> +    /// Appends an element to the back of the [`Vec`] instance without reallocating.
> +    ///
> +    /// # Safety
> +    ///
> +    /// The length must be less than the capacity.
> +    pub unsafe fn push_within_capacity_unchecked(&mut self, v: T) {

Did you intend for this to be pub? The commit message doesn't
obviously indicate it.

>          let spare = self.spare_capacity_mut();
>
>          // SAFETY: The call to `reserve` was successful so the spare capacity is at least 1.

What call to reserve?

>          unsafe { spare.get_unchecked_mut(0) }.write(v);
>
>          // SAFETY: We just initialised the first spare entry, so it is safe to increase the length
> -        // by 1. We also know that the new length is <= capacity because of the previous call to
> -        // `reserve` above.
> +        // by 1. We also know that the new length is <= capacity because the caller guarantees that
> +        // the length is less than the capacity at the beginning of this function.
>          unsafe { self.inc_len(1) };
> -        Ok(())
>      }
>
>      /// Removes the last element from a vector and returns it, or `None` if it is empty.
>
> --
> 2.49.0.805.g082f7c87e0-goog
>
>

Re: [PATCH v3 3/7] rust: alloc: add Vec::push_within_capacity

[Alice Ryhl]

On Wed, Apr 23, 2025 at 11:38:28AM -0400, Tamir Duberstein wrote:
> On Tue, Apr 22, 2025 at 5:53 AM Alice Ryhl <aliceryhl@google.com> wrote:
> >
> > This introduces a new method called `push_within_capacity` for appending
> > to a vector without attempting to allocate if the capacity is full. Rust
> > Binder will use this in various places to safely push to a vector while
> > holding a spinlock.
> >
> > The implementation is moved to a push_within_capacity_unchecked method.
> > This is preferred over having push() call push_within_capacity()
> > followed by an unwrap_unchecked() for simpler unsafe.
> >
> > Signed-off-by: Alice Ryhl <aliceryhl@google.com>
> > +    /// Appends an element to the back of the [`Vec`] instance without reallocating.
> > +    ///
> > +    /// # Safety
> > +    ///
> > +    /// The length must be less than the capacity.
> > +    pub unsafe fn push_within_capacity_unchecked(&mut self, v: T) {
> 
> Did you intend for this to be pub? The commit message doesn't
> obviously indicate it.

Well, I don't think it hurts.

> >          let spare = self.spare_capacity_mut();
> >
> >          // SAFETY: The call to `reserve` was successful so the spare capacity is at least 1.
> 
> What call to reserve?

I have to update this comment, thanks.

> >          unsafe { spare.get_unchecked_mut(0) }.write(v);
> >
> >          // SAFETY: We just initialised the first spare entry, so it is safe to increase the length
> > -        // by 1. We also know that the new length is <= capacity because of the previous call to
> > -        // `reserve` above.
> > +        // by 1. We also know that the new length is <= capacity because the caller guarantees that
> > +        // the length is less than the capacity at the beginning of this function.
> >          unsafe { self.inc_len(1) };
> > -        Ok(())
> >      }

Alice

[PATCH v3 4/7] rust: alloc: add Vec::drain_all

[Alice Ryhl]

This is like the stdlib method drain, except that it's hard-coded to use
the entire vector's range. Rust Binder uses it in the range allocator to
take ownership of everything in a vector in a case where reusing the
vector is desirable.

Implementing `DrainAll` in terms of `slice::IterMut` lets us reuse some
nice optimizations in core for the case where T is a ZST.

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

diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
index a005a295262cb1e8b7c118125ffa07ae252e257c..4a29ca6e7dedc3e93a58830938f3a51619c270ed 100644
--- a/rust/kernel/alloc/kvec.rs
+++ b/rust/kernel/alloc/kvec.rs
@@ -583,6 +583,30 @@ pub fn truncate(&mut self, len: usize) {
             unsafe { ptr::drop_in_place(ptr) };
         }
     }
+
+    /// Takes ownership of all items in this vector without consuming the allocation.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// let mut v = kernel::kvec![0, 1, 2, 3]?;
+    ///
+    /// for (i, j) in v.drain_all().enumerate() {
+    ///     assert_eq!(i, j);
+    /// }
+    ///
+    /// assert!(v.capacity() >= 4);
+    /// ```
+    pub fn drain_all(&mut self) -> DrainAll<'_, T> {
+        let len = self.len();
+        // SAFETY: The length is not greater than the length.
+        let elems = unsafe { self.dec_len(len) };
+        // INVARIANT: The first `len` elements of the spare capacity are valid values, and as we
+        // just set the length to zero, we may transfer ownership to the `DrainAll` object.
+        DrainAll {
+            elements: elems.iter_mut(),
+        }
+    }
 }
 
 impl<T: Clone, A: Allocator> Vec<T, A> {
@@ -1070,3 +1094,38 @@ fn into_iter(self) -> Self::IntoIter {
         }
     }
 }
+
+/// An iterator that owns all items in a vector, but does not own its allocation.
+///
+/// # Invariants
+///
+/// Every `&mut T` returned by the iterator references a `T` that the iterator may take ownership
+/// of.
+pub struct DrainAll<'vec, T> {
+    elements: slice::IterMut<'vec, T>,
+}
+
+impl<'vec, T> Iterator for DrainAll<'vec, T> {
+    type Item = T;
+
+    fn next(&mut self) -> Option<T> {
+        let elem: *mut T = self.elements.next()?;
+        // SAFETY: By the type invariants, we may take ownership of this value.
+        Some(unsafe { elem.read() })
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.elements.size_hint()
+    }
+}
+
+impl<'vec, T> Drop for DrainAll<'vec, T> {
+    fn drop(&mut self) {
+        if core::mem::needs_drop::<T>() {
+            let iter = core::mem::take(&mut self.elements);
+            let ptr: *mut [T] = iter.into_slice();
+            // SAFETY: By the type invariants, we own these values so we may destroy them.
+            unsafe { ptr::drop_in_place(ptr) };
+        }
+    }
+}

-- 
2.49.0.805.g082f7c87e0-goog

[PATCH v3 5/7] rust: alloc: add Vec::retain

[Alice Ryhl]

This adds a common Vec method called `retain` that removes all elements
that don't match a certain condition. Rust Binder uses it to find all
processes that match a given pid.

The stdlib retain method takes &T rather than &mut T and has a separate
retain_mut for the &mut T case. However, this is considered an API
mistake that can't be fixed now due to backwards compatibility. There's
no reason for us to repeat that mistake.

To verify the correctness of this implementation, you may run the
following program in userspace:

    fn retain<T>(vec: &mut Vec<T>, f: impl Fn(&T) -> bool) {
        let mut num_kept = 0;
        let mut next_to_check = 0;
        while let Some(to_check) = vec.get_mut(next_to_check) {
            if f(to_check) {
                vec.swap(num_kept, next_to_check);
                num_kept += 1;
            }
            next_to_check += 1;
        }
        vec.truncate(num_kept);
    }

    fn verify(c: &[bool]) {
        let mut vec1: Vec<usize> = (0..c.len()).collect();
        let mut vec2: Vec<usize> = (0..c.len()).collect();

        vec1.retain(|i| c[*i]);
        retain(&mut vec2, |i| c[*i]);

        assert_eq!(vec1, vec2);
    }

    // Used to loop through all 2^n bit vectors.
    fn add(value: &mut [bool]) -> bool {
        let mut carry = true;
        for v in value {
            let new_v = carry != *v;
            carry = carry && *v;
            *v = new_v;
        }
        carry
    }

    fn main() {
        for len in 0..10 {
            let mut retain = vec![false; len];
            while !add(&mut retain) {
                verify(&retain);
            }
        }
        println!("ok!");
    }

Unfortunately this can't be a kunit test because it uses the upstream
Rust implementation of Vec::retain as a comparison, which we can't call
from a kunit test.

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

diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
index 4a29ca6e7dedc3e93a58830938f3a51619c270ed..2f894eac02212d15d902fe6702d6155f3128997c 100644
--- a/rust/kernel/alloc/kvec.rs
+++ b/rust/kernel/alloc/kvec.rs
@@ -607,6 +607,28 @@ pub fn drain_all(&mut self) -> DrainAll<'_, T> {
             elements: elems.iter_mut(),
         }
     }
+
+    /// Removes all elements that don't match the provided closure.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// let mut v = kernel::kvec![1, 2, 3, 4]?;
+    /// v.retain(|i| i % 2 == 0);
+    /// assert_eq!(v, [2, 4]);
+    /// ```
+    pub fn retain(&mut self, mut f: impl FnMut(&mut T) -> bool) {
+        let mut num_kept = 0;
+        let mut next_to_check = 0;
+        while let Some(to_check) = self.get_mut(next_to_check) {
+            if f(to_check) {
+                self.swap(num_kept, next_to_check);
+                num_kept += 1;
+            }
+            next_to_check += 1;
+        }
+        self.truncate(num_kept);
+    }
 }
 
 impl<T: Clone, A: Allocator> Vec<T, A> {

-- 
2.49.0.805.g082f7c87e0-goog

Re: [PATCH v3 5/7] rust: alloc: add Vec::retain

[Danilo Krummrich]

On 4/22/25 11:52 AM, Alice Ryhl wrote:
> Unfortunately this can't be a kunit test because it uses the upstream
> Rust implementation of Vec::retain as a comparison, which we can't call
> from a kunit test.

Would it work from the rusttest target? We can use our kernel Vec type from 
there, but I don't remember if we still can use std Vec from there.

Re: [PATCH v3 5/7] rust: alloc: add Vec::retain

[Alice Ryhl]

On Wed, Apr 23, 2025 at 02:14:11PM +0200, Danilo Krummrich wrote:
> On 4/22/25 11:52 AM, Alice Ryhl wrote:
> > Unfortunately this can't be a kunit test because it uses the upstream
> > Rust implementation of Vec::retain as a comparison, which we can't call
> > from a kunit test.
> 
> Would it work from the rusttest target? We can use our kernel Vec type from
> there, but I don't remember if we still can use std Vec from there.

My guess is no, but I don't know for sure.

Alice

Re: [PATCH v3 5/7] rust: alloc: add Vec::retain

[Tamir Duberstein]

On Thu, Apr 24, 2025 at 7:46 AM Alice Ryhl <aliceryhl@google.com> wrote:
>
> On Wed, Apr 23, 2025 at 02:14:11PM +0200, Danilo Krummrich wrote:
> > On 4/22/25 11:52 AM, Alice Ryhl wrote:
> > > Unfortunately this can't be a kunit test because it uses the upstream
> > > Rust implementation of Vec::retain as a comparison, which we can't call
> > > from a kunit test.
> >
> > Would it work from the rusttest target? We can use our kernel Vec type from
> > there, but I don't remember if we still can use std Vec from there.
>
> My guess is no, but I don't know for sure.

Isn't it possible to write a test without needing std's implementation?

Re: [PATCH v3 5/7] rust: alloc: add Vec::retain

[Alice Ryhl]

On Thu, Apr 24, 2025 at 09:49:18AM -0400, Tamir Duberstein wrote:
> On Thu, Apr 24, 2025 at 7:46 AM Alice Ryhl <aliceryhl@google.com> wrote:
> >
> > On Wed, Apr 23, 2025 at 02:14:11PM +0200, Danilo Krummrich wrote:
> > > On 4/22/25 11:52 AM, Alice Ryhl wrote:
> > > > Unfortunately this can't be a kunit test because it uses the upstream
> > > > Rust implementation of Vec::retain as a comparison, which we can't call
> > > > from a kunit test.
> > >
> > > Would it work from the rusttest target? We can use our kernel Vec type from
> > > there, but I don't remember if we still can use std Vec from there.
> >
> > My guess is no, but I don't know for sure.
> 
> Isn't it possible to write a test without needing std's implementation?

I could probably come up with a different test.

Alice

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

[Alice Ryhl]

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 | 31 +++++++++++++++++++++++++++++++
 1 file changed, 31 insertions(+)

diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
index 2f894eac02212d15d902fe6702d6155f3128997c..2f28fda793e13841b59e83f34681e71ac815aff2 100644
--- a/rust/kernel/alloc/kvec.rs
+++ b/rust/kernel/alloc/kvec.rs
@@ -386,6 +386,37 @@ pub fn pop(&mut self) -> Option<T> {
         Some(unsafe { removed.read() })
     }
 
+    /// Removes the element at the given index.
+    ///
+    /// # 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: Since the above access did not panic, the length is at least one.
+        unsafe { self.dec_len(1) };
+
+        // SAFETY: We checked that `i` is in-bounds.
+        let p = unsafe { self.as_mut_ptr().add(i) };
+
+        // INVARIANT: This restores the Vec invariants by moving the valid values into the region
+        // that is required to hold valid values.
+        // 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.
+        unsafe { ptr::copy(p.add(1), p, self.len - i - 1) };
+
+        value
+    }
+
     /// Creates a new [`Vec`] instance with at least the given capacity.
     ///
     /// # Examples

-- 
2.49.0.805.g082f7c87e0-goog

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

[Boqun Feng]

On Tue, Apr 22, 2025 at 09:52:21AM +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 | 31 +++++++++++++++++++++++++++++++
>  1 file changed, 31 insertions(+)
> 
> diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
> index 2f894eac02212d15d902fe6702d6155f3128997c..2f28fda793e13841b59e83f34681e71ac815aff2 100644
> --- a/rust/kernel/alloc/kvec.rs
> +++ b/rust/kernel/alloc/kvec.rs
> @@ -386,6 +386,37 @@ pub fn pop(&mut self) -> Option<T> {
>          Some(unsafe { removed.read() })
>      }
>  
> +    /// Removes the element at the given index.
> +    ///
> +    /// # 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.

So a out-of-bound `i` would result into a panic? Then I think we need a
"# Panics" section?

> +        let value = unsafe { ptr::read(&self[i]) };
> +
> +        // SAFETY: Since the above access did not panic, the length is at least one.
> +        unsafe { self.dec_len(1) };
> +

I think you need to move this line after the `ptr::copy()`, right?
Otherwise, you're using the *new* length to calculate how many elements
you are copying. (For example, in your above example, self.len is 2
after self.dec_len(), and the the following copy would be copy(p.add(1),
p, 2 - 1 - 1), which copies zero data, but it would be wrong.) 

Regards,
Boqun

> +        // SAFETY: We checked that `i` is in-bounds.
> +        let p = unsafe { self.as_mut_ptr().add(i) };
> +
> +        // INVARIANT: This restores the Vec invariants by moving the valid values into the region
> +        // that is required to hold valid values.
> +        // 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.
> +        unsafe { ptr::copy(p.add(1), p, self.len - i - 1) };
> +
> +        value
> +    }
> +
>      /// Creates a new [`Vec`] instance with at least the given capacity.
>      ///
>      /// # Examples
> 
> -- 
> 2.49.0.805.g082f7c87e0-goog
> 
> 

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

[Alice Ryhl]

On Wed, Apr 23, 2025 at 12:24 AM Boqun Feng <boqun.feng@gmail.com> wrote:
>
> On Tue, Apr 22, 2025 at 09:52:21AM +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 | 31 +++++++++++++++++++++++++++++++
> >  1 file changed, 31 insertions(+)
> >
> > diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
> > index 2f894eac02212d15d902fe6702d6155f3128997c..2f28fda793e13841b59e83f34681e71ac815aff2 100644
> > --- a/rust/kernel/alloc/kvec.rs
> > +++ b/rust/kernel/alloc/kvec.rs
> > @@ -386,6 +386,37 @@ pub fn pop(&mut self) -> Option<T> {
> >          Some(unsafe { removed.read() })
> >      }
> >
> > +    /// Removes the element at the given index.
> > +    ///
> > +    /// # 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.
>
> So a out-of-bound `i` would result into a panic? Then I think we need a
> "# Panics" section?

I can add a section.

> > +        let value = unsafe { ptr::read(&self[i]) };
> > +
> > +        // SAFETY: Since the above access did not panic, the length is at least one.
> > +        unsafe { self.dec_len(1) };
> > +
>
> I think you need to move this line after the `ptr::copy()`, right?
> Otherwise, you're using the *new* length to calculate how many elements
> you are copying. (For example, in your above example, self.len is 2
> after self.dec_len(), and the the following copy would be copy(p.add(1),
> p, 2 - 1 - 1), which copies zero data, but it would be wrong.)

Good catch, thanks.

Alice

[PATCH v3 7/7] rust: alloc: add Vec::insert_within_capacity

[Alice Ryhl]

This adds a variant of Vec::insert that does not allocate memory. This
makes it safe to use this function while holding a spinlock. Rust Binder
uses it for the range allocator fast path.

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

diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
index 2f28fda793e13841b59e83f34681e71ac815aff2..d96de01a7ab3c808f5aded067ad6f1e3ba8029ce 100644
--- a/rust/kernel/alloc/kvec.rs
+++ b/rust/kernel/alloc/kvec.rs
@@ -355,6 +355,45 @@ pub unsafe fn push_within_capacity_unchecked(&mut self, v: T) {
         unsafe { self.inc_len(1) };
     }
 
+    /// Inserts an element at the given index in the [`Vec`] instance.
+    ///
+    /// Fails if the vector does not have capacity for the new element. Panics if the index is out
+    /// of bounds.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// let mut v = KVec::with_capacity(10, GFP_KERNEL);
+    /// for i in 0..10 {
+    ///     v.push_within_capacity(i).unwrap();
+    /// }
+    ///
+    /// assert!(v.push_within_capacity(10).is_err());
+    /// # Ok::<(), Error>(())
+    /// ```
+    pub fn insert_within_capacity(&mut self, index: usize, element: T) -> Result<(), T> {
+        let len = self.len();
+        assert!(index <= len);
+
+        if len >= self.capacity() {
+            return Err(element);
+        }
+
+        // SAFETY: This is in bounds since `index <= len < capacity`.
+        let p = unsafe { self.as_mut_ptr().add(index) };
+        // INVARIANT: This breaks the Vec invariants by making `index` contain an invalid element,
+        // but we restore the invariants below.
+        // SAFETY: Both the src and dst ranges end no later than one element after the length.
+        // Since the length is less than the capacity, both ranges are in bounds of the allocation.
+        unsafe { ptr::copy(p, p.add(1), len - index) };
+        // INVARIANT: This restores the Vec invariants.
+        // SAFETY: The pointer is in-bounds of the allocation.
+        unsafe { ptr::write(p, element) };
+        // SAFETY: Index `len` contains a valid element due to the above copy and write.
+        unsafe { self.inc_len(1) };
+        Ok(())
+    }
+
     /// Removes the last element from a vector and returns it, or `None` if it is empty.
     ///
     /// # Examples

-- 
2.49.0.805.g082f7c87e0-goog