[PATCH v4 0/7] Additional methods for Vec

[PATCH v4 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 v4:
- Add missing ? in some doc tests.
- Fix safety comment in Vec::push_within_capacity.
- Add panics section to Vec::remove docs.
- Move self.dec_len(1) to end of Vec::remove.
- Add kunit test for Vec::retain.
- Link to v3: https://lore.kernel.org/r/20250422-vec-methods-v3-0-deff5eea568a@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 | 299 +++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 296 insertions(+), 3 deletions(-)
---
base-commit: 88d5d6a38d5161228fbfe017eb94d777d5e8a0e4
change-id: 20250320-vec-methods-adfa41e55311

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

[PATCH v4 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.901.g37484f566f-goog

[PATCH v4 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.901.g37484f566f-goog

[PATCH v4 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.

Reviewed-by: Boqun Feng <boqun.feng@gmail.com>
Signed-off-by: Alice Ryhl <aliceryhl@google.com>
---
 rust/kernel/alloc/kvec.rs | 43 +++++++++++++++++++++++++++++++++++++++----
 1 file changed, 39 insertions(+), 4 deletions(-)

diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
index ebca0cfd31c67f3ce13c4825d7039e34bb54f4d4..78a602e0f00494a52df0e0aa5eedc68967a3011e 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.
+        // SAFETY: By the safety requirements, `spare` is non-empty.
         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.901.g37484f566f-goog

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

[Danilo Krummrich]

On Tue, Apr 29, 2025 at 02:44:23PM +0000, Alice Ryhl wrote:
> 
> +    /// 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();

I'd prefer to make this

	v.push_within_capacity(i).map_err(|_| ENOMEM)?;

instead.

> +    /// }
> +    ///
> +    /// 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.

NIT: Maybe be more specific and say:

"`self.len()` must be less than `self.capacity()`."

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

[Alice Ryhl]

On Wed, Apr 30, 2025 at 05:34:20PM +0200, Danilo Krummrich wrote:
> On Tue, Apr 29, 2025 at 02:44:23PM +0000, Alice Ryhl wrote:
> > 
> > +    /// 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();
> 
> I'd prefer to make this
> 
> 	v.push_within_capacity(i).map_err(|_| ENOMEM)?;
> 
> instead.

Perhaps we could make a new error type for `push_within_capacity`? That
way, you can use it with question mark directly, and you also get a
proper error message if you unwrap() it.

> > +    /// }
> > +    ///
> > +    /// 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.
> 
> NIT: Maybe be more specific and say:
> 
> "`self.len()` must be less than `self.capacity()`."

I try to avoid starting sentences with code, but I can do it if you
prefer that. But saying "the length" and "the capacity" does not seem
ambiguous to me.

Alice

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

[Danilo Krummrich]

On Thu, May 01, 2025 at 11:03:21AM +0000, Alice Ryhl wrote:
> On Wed, Apr 30, 2025 at 05:34:20PM +0200, Danilo Krummrich wrote:
> > On Tue, Apr 29, 2025 at 02:44:23PM +0000, Alice Ryhl wrote:
> > > 
> > > +    /// 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();
> > 
> > I'd prefer to make this
> > 
> > 	v.push_within_capacity(i).map_err(|_| ENOMEM)?;
> > 
> > instead.
> 
> Perhaps we could make a new error type for `push_within_capacity`? That
> way, you can use it with question mark directly, and you also get a
> proper error message if you unwrap() it.

Generally, that sounds good to me. However, I'd like to avoid unwrap() or
anything that panics from doctests, since they also serve as sample code. Hence,
I think we should showcase how to do things the correct way (as much as
possible).

> > > +    /// }
> > > +    ///
> > > +    /// 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.
> > 
> > NIT: Maybe be more specific and say:
> > 
> > "`self.len()` must be less than `self.capacity()`."
> 
> I try to avoid starting sentences with code, but I can do it if you
> prefer that. But saying "the length" and "the capacity" does not seem
> ambiguous to me.

I'll leave that up to you. :)

[PATCH v4 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 | 60 +++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 60 insertions(+)

diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
index 78a602e0f00494a52df0e0aa5eedc68967a3011e..72bc743ec88bf7b91a0a1ffd9f830cfe4f983ffd 100644
--- a/rust/kernel/alloc/kvec.rs
+++ b/rust/kernel/alloc/kvec.rs
@@ -583,6 +583,31 @@ 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);
+    /// # Ok::<(), Error>(())
+    /// ```
+    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 +1095,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.901.g37484f566f-goog

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

[Danilo Krummrich]

On Tue, Apr 29, 2025 at 02:44:24PM +0000, Alice Ryhl wrote:
> 
> +    /// 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);
> +    /// # Ok::<(), Error>(())
> +    /// ```
> +    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) };

Maybe just pass self.len() directly and say that "`By the safety requirements of
`dec_len()`, self.len() is a valid argument".

[PATCH v4 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.

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

diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
index 72bc743ec88bf7b91a0a1ffd9f830cfe4f983ffd..357f5a37c7b1d15b709a10c162292841eed0e376 100644
--- a/rust/kernel/alloc/kvec.rs
+++ b/rust/kernel/alloc/kvec.rs
@@ -608,6 +608,29 @@ 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]);
+    /// # Ok::<(), Error>(())
+    /// ```
+    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> {
@@ -1130,3 +1153,52 @@ fn drop(&mut self) {
         }
     }
 }
+
+#[macros::kunit_tests(rust_kvec_kunit)]
+mod tests {
+    use super::*;
+    use crate::prelude::*;
+
+    #[test]
+    fn test_kvec_retain() {
+        /// Verify correctness for one specific function.
+        #[expect(clippy::needless_range_loop)]
+        fn verify(c: &[bool]) {
+            let mut vec1: KVec<usize> = KVec::with_capacity(c.len(), GFP_KERNEL).unwrap();
+            let mut vec2: KVec<usize> = KVec::with_capacity(c.len(), GFP_KERNEL).unwrap();
+
+            for i in 0..c.len() {
+                vec1.push_within_capacity(i).unwrap();
+                if c[i] {
+                    vec2.push_within_capacity(i).unwrap();
+                }
+            }
+
+            vec1.retain(|i| c[*i]);
+
+            assert_eq!(vec1, vec2);
+        }
+
+        /// Add one to a binary integer represented as a boolean array.
+        fn add(value: &mut [bool]) {
+            let mut carry = true;
+            for v in value {
+                let new_v = carry != *v;
+                carry = carry && *v;
+                *v = new_v;
+            }
+        }
+
+        // This boolean array represents a function from index to boolean. We check that `retain`
+        // behaves correctly for all possible boolean arrays of every possible length less than
+        // ten.
+        let mut func = KVec::with_capacity(10, GFP_KERNEL).unwrap();
+        for len in 0..10 {
+            for _ in 0u32..1u32 << len {
+                verify(&func);
+                add(&mut func);
+            }
+            func.push_within_capacity(false).unwrap();
+        }
+    }
+}

-- 
2.49.0.901.g37484f566f-goog

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

[Danilo Krummrich]

On Tue, Apr 29, 2025 at 02:44:25PM +0000, Alice Ryhl wrote:
> 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.
> 
> Signed-off-by: Alice Ryhl <aliceryhl@google.com>
> ---
>  rust/kernel/alloc/kvec.rs | 72 +++++++++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 72 insertions(+)
> 
> diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
> index 72bc743ec88bf7b91a0a1ffd9f830cfe4f983ffd..357f5a37c7b1d15b709a10c162292841eed0e376 100644
> --- a/rust/kernel/alloc/kvec.rs
> +++ b/rust/kernel/alloc/kvec.rs
> @@ -608,6 +608,29 @@ 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);

NIT: What about making this `v.retain(|&mut i| i % 2 == 0)`?

> +    /// assert_eq!(v, [2, 4]);
> +    /// # Ok::<(), Error>(())
> +    /// ```
> +    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> {
> @@ -1130,3 +1153,52 @@ fn drop(&mut self) {
>          }
>      }
>  }
> +
> +#[macros::kunit_tests(rust_kvec_kunit)]
> +mod tests {
> +    use super::*;
> +    use crate::prelude::*;
> +
> +    #[test]
> +    fn test_kvec_retain() {

Can we have this return a Result, like doctests can do?

> +        /// Verify correctness for one specific function.
> +        #[expect(clippy::needless_range_loop)]
> +        fn verify(c: &[bool]) {
> +            let mut vec1: KVec<usize> = KVec::with_capacity(c.len(), GFP_KERNEL).unwrap();
> +            let mut vec2: KVec<usize> = KVec::with_capacity(c.len(), GFP_KERNEL).unwrap();
> +
> +            for i in 0..c.len() {
> +                vec1.push_within_capacity(i).unwrap();
> +                if c[i] {
> +                    vec2.push_within_capacity(i).unwrap();
> +                }
> +            }
> +
> +            vec1.retain(|i| c[*i]);
> +
> +            assert_eq!(vec1, vec2);

Don't we have macros around kunit_assert!() and kunit_assert_eq() outside of
doctests (i.e. dedicated kunit tests)?

I much prefer their output over the kernel panic we get with the "normal"
asserts, unwraps, etc.

Consistently sticking to the same output on failure makes it easier to catch and
easier to setup CI environments.

> +        }
> +
> +        /// Add one to a binary integer represented as a boolean array.
> +        fn add(value: &mut [bool]) {
> +            let mut carry = true;
> +            for v in value {
> +                let new_v = carry != *v;
> +                carry = carry && *v;
> +                *v = new_v;
> +            }
> +        }
> +
> +        // This boolean array represents a function from index to boolean. We check that `retain`
> +        // behaves correctly for all possible boolean arrays of every possible length less than
> +        // ten.
> +        let mut func = KVec::with_capacity(10, GFP_KERNEL).unwrap();
> +        for len in 0..10 {
> +            for _ in 0u32..1u32 << len {
> +                verify(&func);
> +                add(&mut func);
> +            }
> +            func.push_within_capacity(false).unwrap();
> +        }
> +    }
> +}
> 
> -- 
> 2.49.0.901.g37484f566f-goog
> 

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

[Alice Ryhl]

On Wed, Apr 30, 2025 at 06:26:05PM +0200, Danilo Krummrich wrote:
> On Tue, Apr 29, 2025 at 02:44:25PM +0000, Alice Ryhl wrote:
> > 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.
> >
> > Signed-off-by: Alice Ryhl <aliceryhl@google.com>
> > ---
> >  rust/kernel/alloc/kvec.rs | 72 +++++++++++++++++++++++++++++++++++++++++++++++
> >  1 file changed, 72 insertions(+)
> >
> > diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
> > index 72bc743ec88bf7b91a0a1ffd9f830cfe4f983ffd..357f5a37c7b1d15b709a10c162292841eed0e376 100644
> > --- a/rust/kernel/alloc/kvec.rs
> > +++ b/rust/kernel/alloc/kvec.rs
> > @@ -608,6 +608,29 @@ 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);
>
> NIT: What about making this `v.retain(|&mut i| i % 2 == 0)`?
>
> > +    /// assert_eq!(v, [2, 4]);
> > +    /// # Ok::<(), Error>(())
> > +    /// ```
> > +    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> {
> > @@ -1130,3 +1153,52 @@ fn drop(&mut self) {
> >          }
> >      }
> >  }
> > +
> > +#[macros::kunit_tests(rust_kvec_kunit)]
> > +mod tests {
> > +    use super::*;
> > +    use crate::prelude::*;
> > +
> > +    #[test]
> > +    fn test_kvec_retain() {
>
> Can we have this return a Result, like doctests can do?

I get warning when I try that:

warning: unused `core::result::Result` that must be used
    --> rust/kernel/alloc/kvec.rs:1232:1
     |
1232 | #[macros::kunit_tests(rust_kvec_kunit)]
     | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
     |
     = note: this `Result` may be an `Err` variant, which should be handled
     = note: `#[warn(unused_must_use)]` on by default
     = note: this warning originates in the attribute macro `macros::kunit_tests`
             (in Nightly builds, run with -Z macro-backtrace for more info)

> > +        /// Verify correctness for one specific function.
> > +        #[expect(clippy::needless_range_loop)]
> > +        fn verify(c: &[bool]) {
> > +            let mut vec1: KVec<usize> = KVec::with_capacity(c.len(), GFP_KERNEL).unwrap();
> > +            let mut vec2: KVec<usize> = KVec::with_capacity(c.len(), GFP_KERNEL).unwrap();
> > +
> > +            for i in 0..c.len() {
> > +                vec1.push_within_capacity(i).unwrap();
> > +                if c[i] {
> > +                    vec2.push_within_capacity(i).unwrap();
> > +                }
> > +            }
> > +
> > +            vec1.retain(|i| c[*i]);
> > +
> > +            assert_eq!(vec1, vec2);
>
> Don't we have macros around kunit_assert!() and kunit_assert_eq() outside of
> doctests (i.e. dedicated kunit tests)?
>
> I much prefer their output over the kernel panic we get with the "normal"
> asserts, unwraps, etc.
>
> Consistently sticking to the same output on failure makes it easier to catch and
> easier to setup CI environments.

The documentation for those macros says "Public but hidden since it
should only be used from generated tests." so I don't think I'm supposed
to use them.

Alice

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

[Danilo Krummrich]

On Thu, May 01, 2025 at 11:10:12AM +0000, Alice Ryhl wrote:
> On Wed, Apr 30, 2025 at 06:26:05PM +0200, Danilo Krummrich wrote:
> > On Tue, Apr 29, 2025 at 02:44:25PM +0000, Alice Ryhl wrote:
> > > 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.
> > >
> > > Signed-off-by: Alice Ryhl <aliceryhl@google.com>
> > > ---
> > >  rust/kernel/alloc/kvec.rs | 72 +++++++++++++++++++++++++++++++++++++++++++++++
> > >  1 file changed, 72 insertions(+)
> > >
> > > diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
> > > index 72bc743ec88bf7b91a0a1ffd9f830cfe4f983ffd..357f5a37c7b1d15b709a10c162292841eed0e376 100644
> > > --- a/rust/kernel/alloc/kvec.rs
> > > +++ b/rust/kernel/alloc/kvec.rs
> > > @@ -608,6 +608,29 @@ 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);
> >
> > NIT: What about making this `v.retain(|&mut i| i % 2 == 0)`?
> >
> > > +    /// assert_eq!(v, [2, 4]);
> > > +    /// # Ok::<(), Error>(())
> > > +    /// ```
> > > +    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> {
> > > @@ -1130,3 +1153,52 @@ fn drop(&mut self) {
> > >          }
> > >      }
> > >  }
> > > +
> > > +#[macros::kunit_tests(rust_kvec_kunit)]
> > > +mod tests {
> > > +    use super::*;
> > > +    use crate::prelude::*;
> > > +
> > > +    #[test]
> > > +    fn test_kvec_retain() {
> >
> > Can we have this return a Result, like doctests can do?
> 
> I get warning when I try that:
> 
> warning: unused `core::result::Result` that must be used
>     --> rust/kernel/alloc/kvec.rs:1232:1
>      |
> 1232 | #[macros::kunit_tests(rust_kvec_kunit)]
>      | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
>      |
>      = note: this `Result` may be an `Err` variant, which should be handled
>      = note: `#[warn(unused_must_use)]` on by default
>      = note: this warning originates in the attribute macro `macros::kunit_tests`
>              (in Nightly builds, run with -Z macro-backtrace for more info)

Yes, I'm aware, I tried playing with that myself. I really meant the question as
I wrote, not as "Can you please change that?". :-) Sorry for the confusion.

> > > +        /// Verify correctness for one specific function.
> > > +        #[expect(clippy::needless_range_loop)]
> > > +        fn verify(c: &[bool]) {
> > > +            let mut vec1: KVec<usize> = KVec::with_capacity(c.len(), GFP_KERNEL).unwrap();
> > > +            let mut vec2: KVec<usize> = KVec::with_capacity(c.len(), GFP_KERNEL).unwrap();
> > > +
> > > +            for i in 0..c.len() {
> > > +                vec1.push_within_capacity(i).unwrap();
> > > +                if c[i] {
> > > +                    vec2.push_within_capacity(i).unwrap();
> > > +                }
> > > +            }
> > > +
> > > +            vec1.retain(|i| c[*i]);
> > > +
> > > +            assert_eq!(vec1, vec2);
> >
> > Don't we have macros around kunit_assert!() and kunit_assert_eq() outside of
> > doctests (i.e. dedicated kunit tests)?
> >
> > I much prefer their output over the kernel panic we get with the "normal"
> > asserts, unwraps, etc.
> >
> > Consistently sticking to the same output on failure makes it easier to catch and
> > easier to setup CI environments.
> 
> The documentation for those macros says "Public but hidden since it
> should only be used from generated tests." so I don't think I'm supposed
> to use them.

Same here, that's more a fundamental question, rather than something for you to
change right away.

I really like the way doctests implement the assert macros and how they appear
in the kernel log compared to panics through the "real" assert ones, unwraps,
etc.

I also think that avoiding things that directly panic in doctests (i.e. example
code) is the correct thing to do. For KUnit tests it's probably less important,
since they don't directly serve as sample code.

So, I wonder what's our take on that. Do we want to have KUnit and doctests
aligned? I think that'd be a good thing.

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

[Alice Ryhl]

On Thu, May 01, 2025 at 01:30:20PM +0200, Danilo Krummrich wrote:
> On Thu, May 01, 2025 at 11:10:12AM +0000, Alice Ryhl wrote:
> > On Wed, Apr 30, 2025 at 06:26:05PM +0200, Danilo Krummrich wrote:
> > > On Tue, Apr 29, 2025 at 02:44:25PM +0000, Alice Ryhl wrote:
> > > > +#[macros::kunit_tests(rust_kvec_kunit)]
> > > > +mod tests {
> > > > +    use super::*;
> > > > +    use crate::prelude::*;
> > > > +
> > > > +    #[test]
> > > > +    fn test_kvec_retain() {
> > >
> > > Can we have this return a Result, like doctests can do?
> > 
> > I get warning when I try that:
> > 
> > warning: unused `core::result::Result` that must be used
> >     --> rust/kernel/alloc/kvec.rs:1232:1
> >      |
> > 1232 | #[macros::kunit_tests(rust_kvec_kunit)]
> >      | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
> >      |
> >      = note: this `Result` may be an `Err` variant, which should be handled
> >      = note: `#[warn(unused_must_use)]` on by default
> >      = note: this warning originates in the attribute macro `macros::kunit_tests`
> >              (in Nightly builds, run with -Z macro-backtrace for more info)
> 
> Yes, I'm aware, I tried playing with that myself. I really meant the question as
> I wrote, not as "Can you please change that?". :-) Sorry for the confusion.

One downside is that returning a Result doesn't show the line of code
where it failed.

> > > > +        /// Verify correctness for one specific function.
> > > > +        #[expect(clippy::needless_range_loop)]
> > > > +        fn verify(c: &[bool]) {
> > > > +            let mut vec1: KVec<usize> = KVec::with_capacity(c.len(), GFP_KERNEL).unwrap();
> > > > +            let mut vec2: KVec<usize> = KVec::with_capacity(c.len(), GFP_KERNEL).unwrap();
> > > > +
> > > > +            for i in 0..c.len() {
> > > > +                vec1.push_within_capacity(i).unwrap();
> > > > +                if c[i] {
> > > > +                    vec2.push_within_capacity(i).unwrap();
> > > > +                }
> > > > +            }
> > > > +
> > > > +            vec1.retain(|i| c[*i]);
> > > > +
> > > > +            assert_eq!(vec1, vec2);
> > >
> > > Don't we have macros around kunit_assert!() and kunit_assert_eq() outside of
> > > doctests (i.e. dedicated kunit tests)?
> > >
> > > I much prefer their output over the kernel panic we get with the "normal"
> > > asserts, unwraps, etc.
> > >
> > > Consistently sticking to the same output on failure makes it easier to catch and
> > > easier to setup CI environments.
> > 
> > The documentation for those macros says "Public but hidden since it
> > should only be used from generated tests." so I don't think I'm supposed
> > to use them.
> 
> Same here, that's more a fundamental question, rather than something for you to
> change right away.
> 
> I really like the way doctests implement the assert macros and how they appear
> in the kernel log compared to panics through the "real" assert ones, unwraps,
> etc.
> 
> I also think that avoiding things that directly panic in doctests (i.e. example
> code) is the correct thing to do. For KUnit tests it's probably less important,
> since they don't directly serve as sample code.
> 
> So, I wonder what's our take on that. Do we want to have KUnit and doctests
> aligned? I think that'd be a good thing.

I think that both of these would be reasonable to fix. Also the fact
that I had to do #[macros::kunit_tests()] instead of just #[kunit_tests()].

Alice

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

[Miguel Ojeda]

On Thu, May 1, 2025 at 1:30 PM Danilo Krummrich <dakr@kernel.org> wrote:
>
> I really like the way doctests implement the assert macros and how they appear
> in the kernel log compared to panics through the "real" assert ones, unwraps,
> etc.
>
> I also think that avoiding things that directly panic in doctests (i.e. example
> code) is the correct thing to do. For KUnit tests it's probably less important,
> since they don't directly serve as sample code.

I hadn't seen these earlier messages -- thanks, I am glad people like
the doctests support :)

Yeah, doing the same for `#[test]`s was planned (see PR), but we
decided to merge roughly what we had from the original author and then
build on top of that (Cc David).

Anyway, I sent it -- hopefully it will mean more people writing lots of tests!

    https://lore.kernel.org/rust-for-linux/20250502215133.1923676-1-ojeda@kernel.org/

Cheers,
Miguel

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

[Miguel Ojeda]

On Wed, 30 Apr 2025 18:26:05 +0200 Danilo Krummrich <dakr@kernel.org> wrote:
>
> Can we have this return a Result, like doctests can do?
>
> Don't we have macros around kunit_assert!() and kunit_assert_eq() outside of
> doctests (i.e. dedicated kunit tests)?

The initial KUnit `#[test]` support that landed was very basic:

    https://lore.kernel.org/rust-for-linux/20250330170535.546869-1-ojeda@kernel.org/

The missing `assert*!`s support is definitely annoying. I took a quick look,
and it is not too bad to add the support. The `Result` is then easy on top too.

So I will send the support for both already since I suspect others will hit this
quite soon.

I hope that helps.

Cheers,
Miguel

[PATCH v4 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 | 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

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

[Danilo Krummrich]

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.

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

[Alice Ryhl]

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

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

[Danilo Krummrich]

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.

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

[Alice Ryhl]

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

[PATCH v4 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 0682108951675cbee05faa130e5a9ce72fc343ba..998afdcde47bec94b2c9d990ba3afbb3488ea99e 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.901.g37484f566f-goog

Re: [PATCH v4 7/7] rust: alloc: add Vec::insert_within_capacity

[Greg KH]

On Tue, Apr 29, 2025 at 02:44:27PM +0000, Alice Ryhl wrote:
> 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 0682108951675cbee05faa130e5a9ce72fc343ba..998afdcde47bec94b2c9d990ba3afbb3488ea99e 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.

Why panic and why not just return an error instead?

thanks,

greg k-h

Re: [PATCH v4 7/7] rust: alloc: add Vec::insert_within_capacity

[Alice Ryhl]

On Tue, Apr 29, 2025 at 05:30:06PM +0200, Greg KH wrote:
> On Tue, Apr 29, 2025 at 02:44:27PM +0000, Alice Ryhl wrote:
> > 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 0682108951675cbee05faa130e5a9ce72fc343ba..998afdcde47bec94b2c9d990ba3afbb3488ea99e 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.
> 
> Why panic and why not just return an error instead?

It's for consistency with stdlib. Illegal use is panic, expected error
conditions are errors.

Alice

Re: [PATCH v4 7/7] rust: alloc: add Vec::insert_within_capacity

[Greg KH]

On Wed, Apr 30, 2025 at 11:24:23AM +0000, Alice Ryhl wrote:
> On Tue, Apr 29, 2025 at 05:30:06PM +0200, Greg KH wrote:
> > On Tue, Apr 29, 2025 at 02:44:27PM +0000, Alice Ryhl wrote:
> > > 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 0682108951675cbee05faa130e5a9ce72fc343ba..998afdcde47bec94b2c9d990ba3afbb3488ea99e 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.
> > 
> > Why panic and why not just return an error instead?
> 
> It's for consistency with stdlib. Illegal use is panic, expected error
> conditions are errors.

But this is the kernel, not userspace :)

As you can return an error, why not?  Rebooting a box should be a "last
resort" type of thing when you can not recover from an error.  You can
easily not overflow and return an error here, so why do you want to just
give up and cause all data to be lost?

And I don't see any other panics happening in this file, so would this
be the first one?

thanks,

greg k-h

Re: [PATCH v4 7/7] rust: alloc: add Vec::insert_within_capacity

[Alice Ryhl]

On Wed, Apr 30, 2025 at 01:39:03PM +0200, Greg KH wrote:
> On Wed, Apr 30, 2025 at 11:24:23AM +0000, Alice Ryhl wrote:
> > On Tue, Apr 29, 2025 at 05:30:06PM +0200, Greg KH wrote:
> > > On Tue, Apr 29, 2025 at 02:44:27PM +0000, Alice Ryhl wrote:
> > > > 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 0682108951675cbee05faa130e5a9ce72fc343ba..998afdcde47bec94b2c9d990ba3afbb3488ea99e 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.
> > > 
> > > Why panic and why not just return an error instead?
> > 
> > It's for consistency with stdlib. Illegal use is panic, expected error
> > conditions are errors.
> 
> But this is the kernel, not userspace :)
> 
> As you can return an error, why not?  Rebooting a box should be a "last
> resort" type of thing when you can not recover from an error.  You can
> easily not overflow and return an error here, so why do you want to just
> give up and cause all data to be lost?
> 
> And I don't see any other panics happening in this file, so would this
> be the first one?

I don't feel strongly about this method, but it's not the first panic.
The vector type has an indexing operator vec[i] that panics if you index
out-of-bounds.

Alice

Re: [PATCH v4 7/7] rust: alloc: add Vec::insert_within_capacity

[Danilo Krummrich]

On Wed, Apr 30, 2025 at 12:15:14PM +0000, Alice Ryhl wrote:
> On Wed, Apr 30, 2025 at 01:39:03PM +0200, Greg KH wrote:
> > On Wed, Apr 30, 2025 at 11:24:23AM +0000, Alice Ryhl wrote:
> > > On Tue, Apr 29, 2025 at 05:30:06PM +0200, Greg KH wrote:
> > > > On Tue, Apr 29, 2025 at 02:44:27PM +0000, Alice Ryhl wrote:
> > > > > 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 0682108951675cbee05faa130e5a9ce72fc343ba..998afdcde47bec94b2c9d990ba3afbb3488ea99e 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.
> > > > 
> > > > Why panic and why not just return an error instead?
> > > 
> > > It's for consistency with stdlib. Illegal use is panic, expected error
> > > conditions are errors.
> > 
> > But this is the kernel, not userspace :)
> > 
> > As you can return an error, why not?  Rebooting a box should be a "last
> > resort" type of thing when you can not recover from an error.  You can
> > easily not overflow and return an error here, so why do you want to just
> > give up and cause all data to be lost?
> > 
> > And I don't see any other panics happening in this file, so would this
> > be the first one?
> 
> I don't feel strongly about this method, but it's not the first panic.
> The vector type has an indexing operator vec[i] that panics if you index
> out-of-bounds.

This is because core::ops::Index isn't fallible and even if we wouldn't
implement Index for Vec, we'd get a slice through Deref, where it is exactly the
same.

In this case though, we can easily avoid the panic by checking the index and
return an error instead, which is what we should do.