[PATCH v5 0/7] Additional methods for Vec

[PATCH v5 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 v5:
- Replace panics with errors.
- Avoid variable for length in drain_all.
- Link to v4: https://lore.kernel.org/r/20250429-vec-methods-v4-0-dad4436ff82d@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        | 315 ++++++++++++++++++++++++++++++++++++++-
 rust/kernel/alloc/kvec/errors.rs |  61 ++++++++
 2 files changed, 373 insertions(+), 3 deletions(-)
---
base-commit: 88d5d6a38d5161228fbfe017eb94d777d5e8a0e4
change-id: 20250320-vec-methods-adfa41e55311

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

[PATCH v5 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.967.g6a0df3ecc3-goog

[PATCH v5 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.967.g6a0df3ecc3-goog

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

Panics in the kernel are best avoided when possible, so an error is
returned if the vector does not have sufficient capacity. An error type
is used rather than just returning Result<(),T> to make it more
convenient for callers (i.e. they can use ? or unwrap).

Signed-off-by: Alice Ryhl <aliceryhl@google.com>
---
 rust/kernel/alloc/kvec.rs        | 46 ++++++++++++++++++++++++++++++++++++----
 rust/kernel/alloc/kvec/errors.rs | 23 ++++++++++++++++++++
 2 files changed, 65 insertions(+), 4 deletions(-)

diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
index ebca0cfd31c67f3ce13c4825d7039e34bb54f4d4..e9bf4c97a5a78fc9b54751b57f15a33c716c607b 100644
--- a/rust/kernel/alloc/kvec.rs
+++ b/rust/kernel/alloc/kvec.rs
@@ -21,6 +21,9 @@
     slice::SliceIndex,
 };
 
+mod errors;
+pub use self::errors::PushError;
+
 /// Create a [`KVec`] containing the arguments.
 ///
 /// New memory is allocated with `GFP_KERNEL`.
@@ -307,17 +310,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)?;
+    /// }
+    ///
+    /// assert!(v.push_within_capacity(10).is_err());
+    /// # Ok::<(), Error>(())
+    /// ```
+    pub fn push_within_capacity(&mut self, v: T) -> Result<(), PushError<T>> {
+        if self.len() < self.capacity() {
+            // SAFETY: The length is less than the capacity.
+            unsafe { self.push_within_capacity_unchecked(v) };
+            Ok(())
+        } else {
+            Err(PushError(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.
diff --git a/rust/kernel/alloc/kvec/errors.rs b/rust/kernel/alloc/kvec/errors.rs
new file mode 100644
index 0000000000000000000000000000000000000000..84c96ec5007ddc676283cbce07f4d670c3873c1e
--- /dev/null
+++ b/rust/kernel/alloc/kvec/errors.rs
@@ -0,0 +1,23 @@
+// SPDX-License-Identifier: GPL-2.0
+
+//! Errors for the [`Vec`] type.
+
+use core::fmt::{self, Debug, Formatter};
+use kernel::prelude::*;
+
+/// Error type for [`Vec::push_within_capacity`].
+pub struct PushError<T>(pub T);
+
+impl<T> Debug for PushError<T> {
+    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
+        write!(f, "Not enough capacity")
+    }
+}
+
+impl<T> From<PushError<T>> for Error {
+    fn from(_: PushError<T>) -> Error {
+        // Returning ENOMEM isn't appropriate because the system is not out of memory. The vector
+        // is just full and we are refusing to resize it.
+        EINVAL
+    }
+}

-- 
2.49.0.967.g6a0df3ecc3-goog

[PATCH v5 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 e9bf4c97a5a78fc9b54751b57f15a33c716c607b..7f75f3174ccb85daa3a9546d7b110da97f46063f 100644
--- a/rust/kernel/alloc/kvec.rs
+++ b/rust/kernel/alloc/kvec.rs
@@ -586,6 +586,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);
+    /// # Ok::<(), Error>(())
+    /// ```
+    pub fn drain_all(&mut self) -> DrainAll<'_, T> {
+        // SAFETY: This does not underflow the length.
+        let elems = unsafe { self.dec_len(self.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> {
@@ -1073,3 +1097,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.967.g6a0df3ecc3-goog

[PATCH v5 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 7f75f3174ccb85daa3a9546d7b110da97f46063f..3298b3b0f32c70f3fe517fcb7af6b9922fea926b 100644
--- a/rust/kernel/alloc/kvec.rs
+++ b/rust/kernel/alloc/kvec.rs
@@ -610,6 +610,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> {
@@ -1132,3 +1155,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.967.g6a0df3ecc3-goog

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

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

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

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

-- 
2.49.0.967.g6a0df3ecc3-goog

[PATCH v5 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        | 51 +++++++++++++++++++++++++++++++++++++++-
 rust/kernel/alloc/kvec/errors.rs | 23 ++++++++++++++++++
 2 files changed, 73 insertions(+), 1 deletion(-)

diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
index 8845e7694334b672476ff935580f3a9eb94d23fe..d2f3669c5417422dddaebcc7348543d3576b9ba8 100644
--- a/rust/kernel/alloc/kvec.rs
+++ b/rust/kernel/alloc/kvec.rs
@@ -22,7 +22,7 @@
 };
 
 mod errors;
-pub use self::errors::{PushError, RemoveError};
+pub use self::errors::{InsertError, PushError, RemoveError};
 
 /// Create a [`KVec`] containing the arguments.
 ///
@@ -358,6 +358,55 @@ 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
+    ///
+    /// ```
+    /// use kernel::alloc::kvec::InsertError;
+    ///
+    /// let mut v = KVec::with_capacity(5, GFP_KERNEL)?;
+    /// for i in 0..5 {
+    ///     v.insert_within_capacity(0, i)?;
+    /// }
+    ///
+    /// assert!(matches!(v.insert_within_capacity(0, 5), Err(InsertError::OutOfCapacity(_))));
+    /// assert!(matches!(v.insert_within_capacity(1000, 5), Err(InsertError::IndexOutOfBounds(_))));
+    /// assert_eq!(v, [4, 3, 2, 1, 0]);
+    /// # Ok::<(), Error>(())
+    /// ```
+    pub fn insert_within_capacity(
+        &mut self,
+        index: usize,
+        element: T,
+    ) -> Result<(), InsertError<T>> {
+        let len = self.len();
+        if index > len {
+            return Err(InsertError::IndexOutOfBounds(element));
+        }
+
+        if len >= self.capacity() {
+            return Err(InsertError::OutOfCapacity(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
diff --git a/rust/kernel/alloc/kvec/errors.rs b/rust/kernel/alloc/kvec/errors.rs
index 06fe696e8bc6612a5e6aa2f6c28b685033acfa2f..348b8d27e102ca34a0d6194ae9d00b12c11547b4 100644
--- a/rust/kernel/alloc/kvec/errors.rs
+++ b/rust/kernel/alloc/kvec/errors.rs
@@ -36,3 +36,26 @@ fn from(_: RemoveError) -> Error {
         EINVAL
     }
 }
+
+/// Error type for [`Vec::insert_within_capacity`].
+pub enum InsertError<T> {
+    /// The value could not be inserted because the index is out of bounds.
+    IndexOutOfBounds(T),
+    /// The value could not be inserted because the vector is out of capacity.
+    OutOfCapacity(T),
+}
+
+impl<T> Debug for InsertError<T> {
+    fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
+        match self {
+            InsertError::IndexOutOfBounds(_) => write!(f, "Index out of bounds"),
+            InsertError::OutOfCapacity(_) => write!(f, "Not enough capacity"),
+        }
+    }
+}
+
+impl<T> From<InsertError<T>> for Error {
+    fn from(_: InsertError<T>) -> Error {
+        EINVAL
+    }
+}

-- 
2.49.0.967.g6a0df3ecc3-goog

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

[Greg KH]

On Fri, May 02, 2025 at 01:19:31PM +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.
> 
> Panics in the kernel are best avoided when possible, so an error is
> returned if the vector does not have sufficient capacity. An error type
> is used rather than just returning Result<(),T> to make it more
> convenient for callers (i.e. they can use ? or unwrap).
> 
> Signed-off-by: Alice Ryhl <aliceryhl@google.com>
> ---
>  rust/kernel/alloc/kvec.rs        | 46 ++++++++++++++++++++++++++++++++++++----
>  rust/kernel/alloc/kvec/errors.rs | 23 ++++++++++++++++++++
>  2 files changed, 65 insertions(+), 4 deletions(-)
> 
> diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
> index ebca0cfd31c67f3ce13c4825d7039e34bb54f4d4..e9bf4c97a5a78fc9b54751b57f15a33c716c607b 100644
> --- a/rust/kernel/alloc/kvec.rs
> +++ b/rust/kernel/alloc/kvec.rs
> @@ -21,6 +21,9 @@
>      slice::SliceIndex,
>  };
>  
> +mod errors;
> +pub use self::errors::PushError;
> +
>  /// Create a [`KVec`] containing the arguments.
>  ///
>  /// New memory is allocated with `GFP_KERNEL`.
> @@ -307,17 +310,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)?;
> +    /// }
> +    ///
> +    /// assert!(v.push_within_capacity(10).is_err());
> +    /// # Ok::<(), Error>(())
> +    /// ```
> +    pub fn push_within_capacity(&mut self, v: T) -> Result<(), PushError<T>> {
> +        if self.len() < self.capacity() {
> +            // SAFETY: The length is less than the capacity.
> +            unsafe { self.push_within_capacity_unchecked(v) };
> +            Ok(())
> +        } else {
> +            Err(PushError(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) {

Why does this have to be public?  Does binder need to call this instead
of just push_within_capacity()?

thanks,

greg k-h

Re: [PATCH v5 0/7] Additional methods for Vec

[Greg KH]

On Fri, May 02, 2025 at 01:19:28PM +0000, Alice Ryhl wrote:
> 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>

I had one tiny question, but it's not really an issue, over looks great:

Reviewed-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>

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

[Alice Ryhl]

On Fri, May 2, 2025 at 4:07 PM Greg KH <gregkh@linuxfoundation.org> wrote:
>
> On Fri, May 02, 2025 at 01:19:31PM +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.
> >
> > Panics in the kernel are best avoided when possible, so an error is
> > returned if the vector does not have sufficient capacity. An error type
> > is used rather than just returning Result<(),T> to make it more
> > convenient for callers (i.e. they can use ? or unwrap).
> >
> > 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) {
>
> Why does this have to be public?  Does binder need to call this instead
> of just push_within_capacity()?

It does not need to be public.

Alice

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

[Danilo Krummrich]

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

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

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

[Danilo Krummrich]

On Fri, May 02, 2025 at 04:25:01PM +0200, Alice Ryhl wrote:
> On Fri, May 2, 2025 at 4:07 PM Greg KH <gregkh@linuxfoundation.org> wrote:
> >
> > On Fri, May 02, 2025 at 01:19:31PM +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.
> > >
> > > Panics in the kernel are best avoided when possible, so an error is
> > > returned if the vector does not have sufficient capacity. An error type
> > > is used rather than just returning Result<(),T> to make it more
> > > convenient for callers (i.e. they can use ? or unwrap).
> > >
> > > 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) {
> >
> > Why does this have to be public?  Does binder need to call this instead
> > of just push_within_capacity()?
> 
> It does not need to be public.

Gonna fix when I apply the series.

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

[Alexandre Courbot]

Hi Alice,

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

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

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

[Alexandre Courbot]

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

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

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

[Alice Ryhl]

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

Thanks for taking a look!

Alice

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

[Benno Lossin]

On Fri May 2, 2025 at 3:19 PM CEST, Alice Ryhl 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>

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

---
Cheers,
Benno

> ---
>  rust/kernel/alloc/kvec.rs | 31 +++++++++++++++++++++++++++++++
>  1 file changed, 31 insertions(+)

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

[Benno Lossin]

On Fri May 2, 2025 at 3:19 PM CEST, 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.
>
> Panics in the kernel are best avoided when possible, so an error is
> returned if the vector does not have sufficient capacity. An error type
> is used rather than just returning Result<(),T> to make it more
> convenient for callers (i.e. they can use ? or unwrap).
>
> Signed-off-by: Alice Ryhl <aliceryhl@google.com>

One small nit below, with or without:

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

[...]

> +    /// Appends an element to the back of the [`Vec`] instance without reallocating.
> +    ///
> +    /// # Safety
> +    ///
> +    /// The length must be less than the capacity.

I would have written:

    - `self.len() < self.capacity()`

---
Cheers,
Benno

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

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

[Benno Lossin]

On Fri May 2, 2025 at 3:19 PM CEST, Alice Ryhl wrote:
> 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>

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

---
Cheers,
Benno

> ---
>  rust/kernel/alloc/kvec.rs | 59 +++++++++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 59 insertions(+)

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

[Benno Lossin]

On Fri May 2, 2025 at 3:19 PM CEST, 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>

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

---
Cheers,
Benno

> ---
>  rust/kernel/alloc/kvec.rs | 72 +++++++++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 72 insertions(+)

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

[Benno Lossin]

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

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

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

[...]

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

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

---
Cheers,
Benno

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

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

[Benno Lossin]

On Fri May 2, 2025 at 3:19 PM CEST, 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>

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

---
Cheers,
Benno

> ---
>  rust/kernel/alloc/kvec.rs        | 51 +++++++++++++++++++++++++++++++++++++++-
>  rust/kernel/alloc/kvec/errors.rs | 23 ++++++++++++++++++
>  2 files changed, 73 insertions(+), 1 deletion(-)

Re: [PATCH v5 0/7] Additional methods for Vec

[Danilo Krummrich]

On Fri, May 02, 2025 at 01:19:28PM +0000, Alice Ryhl wrote:
> 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.

Applied to alloc-next, thanks!

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

[Alice Ryhl]

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

Thanks!

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

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

Alice