[PATCH v2 0/4] rust: alloc: split `Vec::set_len` into `Vec::{inc,dec}_len`

[PATCH v2 0/4] rust: alloc: split `Vec::set_len` into `Vec::{inc,dec}_len`

[Tamir Duberstein]

This series is the product of a discussion[0] on the safety requirements
of `set_len`.

This series depends on "rust: alloc: add Vec::truncate method" by Andrew
Ballance <andrewjballance@gmail.com> [1] and rewrites `Vec::truncate`
using `Vec::dec_len`.

Link: https://lore.kernel.org/all/20250315154436.65065-1-dakr@kernel.org/ [0]
Link: https://lore.kernel.org/all/20250316111644.154602-2-andrewjballance@gmail.com/ [1]
Signed-off-by: Tamir Duberstein <tamird@gmail.com>
---
Changes in v2:
- Avoid overflow in `set_len`. (Benno Lossin)
- Explained `CString::try_from_fmt` usage of `set_len`. (Benno Lossin,
  Miguel Ojeda, Alice Ryhl)
- Added missing SoB. (Alice Ryhl)
- Prepend a patch documenting `Vec::len() <= Vec::capacity()` invariant.
- Add a patch rewriting `Vec::truncate` in terms of `Vec::dec_len`.
- Link to v1: https://lore.kernel.org/r/20250316-vec-set-len-v1-0-60f98a28723f@gmail.com

---
Tamir Duberstein (4):
      rust: alloc: add Vec::len() <= Vec::capacity invariant
      rust: alloc: add `Vec::dec_len`
      rust: alloc: refactor `Vec::truncate` using `dec_len`
      rust: alloc: replace `Vec::set_len` with `inc_len`

 rust/kernel/alloc/kvec.rs | 87 +++++++++++++++++++++++++++--------------------
 rust/kernel/str.rs        |  2 +-
 rust/kernel/uaccess.rs    |  2 +-
 3 files changed, 53 insertions(+), 38 deletions(-)
---
base-commit: cf25bc61f8aecad9b0c45fe32697e35ea4b13378
change-id: 20250316-vec-set-len-99be6cc48374
prerequisite-patch-id: 85a264a3c7e86025e7b36d91234134f5cc914366

Best regards,
-- 
Tamir Duberstein <tamird@gmail.com>

[PATCH v2 1/4] rust: alloc: add Vec::len() <= Vec::capacity invariant

[Tamir Duberstein]

Document the invariant that the vector's length is always less than or
equal to its capacity. This is already implied by these other
invariants:

- `self.len` always represents the exact number of elements stored in
  the vector.
- `self.layout` represents the absolute number of elements that can be
  stored within the vector without re-allocation.

but it doesn't hurt to spell it out. Note that the language references
`self.capacity` rather than `self.layout.len` as the latter is zero for
a vector of ZSTs.

Signed-off-by: Tamir Duberstein <tamird@gmail.com>
---
 rust/kernel/alloc/kvec.rs | 19 +++++++++++--------
 1 file changed, 11 insertions(+), 8 deletions(-)

diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
index 18bcc59f0b38..ce58ee66c99b 100644
--- a/rust/kernel/alloc/kvec.rs
+++ b/rust/kernel/alloc/kvec.rs
@@ -90,6 +90,8 @@ macro_rules! kvec {
 ///   without re-allocation. For ZSTs `self.layout`'s capacity is zero. However, it is legal for the
 ///   backing buffer to be larger than `layout`.
 ///
+/// - `self.len()` is always less than or equal to `self.capacity()`.
+///
 /// - The `Allocator` type `A` of the vector is the exact same `Allocator` type the backing buffer
 ///   was allocated with (and must be freed with).
 pub struct Vec<T, A: Allocator> {
@@ -259,8 +261,8 @@ pub const fn new() -> Self {
     /// Returns a slice of `MaybeUninit<T>` for the remaining spare capacity of the vector.
     pub fn spare_capacity_mut(&mut self) -> &mut [MaybeUninit<T>] {
         // SAFETY:
-        // - `self.len` is smaller than `self.capacity` and hence, the resulting pointer is
-        //   guaranteed to be part of the same allocated object.
+        // - `self.len` is smaller than `self.capacity` by the type invariant and hence, the
+        //   resulting pointer is guaranteed to be part of the same allocated object.
         // - `self.len` can not overflow `isize`.
         let ptr = unsafe { self.as_mut_ptr().add(self.len) } as *mut MaybeUninit<T>;
 
@@ -286,8 +288,8 @@ pub fn push(&mut self, v: T, flags: Flags) -> Result<(), AllocError> {
         self.reserve(1, flags)?;
 
         // SAFETY:
-        // - `self.len` is smaller than `self.capacity` and hence, the resulting pointer is
-        //   guaranteed to be part of the same allocated object.
+        // - `self.len` is smaller than `self.capacity` by the type invariant and hence, the
+        //   resulting pointer is guaranteed to be part of the same allocated object.
         // - `self.len` can not overflow `isize`.
         let ptr = unsafe { self.as_mut_ptr().add(self.len) };
 
@@ -793,12 +795,13 @@ pub fn collect(self, flags: Flags) -> Vec<T, A> {
             unsafe { ptr::copy(ptr, buf.as_ptr(), len) };
             ptr = buf.as_ptr();
 
-            // SAFETY: `len` is guaranteed to be smaller than `self.layout.len()`.
+            // SAFETY: `len` is guaranteed to be smaller than `self.layout.len()` by the type
+            // invariant.
             let layout = unsafe { ArrayLayout::<T>::new_unchecked(len) };
 
-            // SAFETY: `buf` points to the start of the backing buffer and `len` is guaranteed to be
-            // smaller than `cap`. Depending on `alloc` this operation may shrink the buffer or leaves
-            // it as it is.
+            // SAFETY: `buf` points to the start of the backing buffer and `len` is guaranteed by
+            // the type invariant to be smaller than `cap`. Depending on `alloc` this operation may
+            // shrink the buffer or leaves it as it is.
             ptr = match unsafe {
                 A::realloc(Some(buf.cast()), layout.into(), old_layout.into(), flags)
             } {

-- 
2.48.1

[PATCH v2 2/4] rust: alloc: add `Vec::dec_len`

[Tamir Duberstein]

Add `Vec::dec_len` that reduces the length of the receiver. This method
is intended to be used from methods that remove elements from `Vec` such
as `truncate`, `pop`, `remove`, and others. This method is intentionally
not `pub`.

Signed-off-by: Tamir Duberstein <tamird@gmail.com>
---
 rust/kernel/alloc/kvec.rs | 19 +++++++++++++++++++
 1 file changed, 19 insertions(+)

diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
index ce58ee66c99b..97cc5ab11e2a 100644
--- a/rust/kernel/alloc/kvec.rs
+++ b/rust/kernel/alloc/kvec.rs
@@ -198,6 +198,25 @@ pub unsafe fn set_len(&mut self, new_len: usize) {
         self.len = new_len;
     }
 
+    /// Decreases `self.len` by `count`.
+    ///
+    /// Returns a mutable slice to the elements forgotten by the vector. It is the caller's
+    /// responsibility to drop these elements if necessary.
+    ///
+    /// # Safety
+    ///
+    /// - `count` must be less than or equal to `self.len`.
+    unsafe fn dec_len(&mut self, count: usize) -> &mut [T] {
+        debug_assert!(count <= self.len());
+        // INVARIANT: We relinquish ownership of the elements within the range `[self.len - count,
+        // self.len)`, hence the updated value of `set.len` represents the exact number of elements
+        // stored within `self`.
+        self.len -= count;
+        // SAFETY: The memory after `self.len()` is guaranteed to contain `count` initialized
+        // elements of type `T`.
+        unsafe { slice::from_raw_parts_mut(self.as_mut_ptr().add(self.len), count) }
+    }
+
     /// Returns a slice of the entire vector.
     #[inline]
     pub fn as_slice(&self) -> &[T] {

-- 
2.48.1

[PATCH v2 3/4] rust: alloc: refactor `Vec::truncate` using `dec_len`

[Tamir Duberstein]

Use `checked_sub` to satisfy the safety requirements of `dec_len` and
replace nearly the whole body of `truncate` with a call to `dec_len`.

Signed-off-by: Tamir Duberstein <tamird@gmail.com>
---
 rust/kernel/alloc/kvec.rs | 29 +++++++++++------------------
 1 file changed, 11 insertions(+), 18 deletions(-)

diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
index 97cc5ab11e2a..6f4dc89ef7f8 100644
--- a/rust/kernel/alloc/kvec.rs
+++ b/rust/kernel/alloc/kvec.rs
@@ -489,25 +489,18 @@ pub fn reserve(&mut self, additional: usize, flags: Flags) -> Result<(), AllocEr
     /// # Ok::<(), Error>(())
     /// ```
     pub fn truncate(&mut self, len: usize) {
-        if len >= self.len() {
-            return;
+        match self.len().checked_sub(len) {
+            None => {}
+            Some(count) => {
+                // SAFETY: `count` is `self.len() - len` so it is guaranteed to be less than or
+                // equal to `self.len()`.
+                let tail = unsafe { self.dec_len(count) };
+
+                // SAFETY: the contract of `dec_len` guarantees that the elements in `tail` are
+                // valid elements whose ownership has been transferred to the caller.
+                unsafe { ptr::drop_in_place(ptr) };
+            }
         }
-
-        let drop_range = len..self.len();
-
-        // SAFETY: `drop_range` is a subrange of `[0, len)` by the bounds check above.
-        let ptr: *mut [T] = unsafe { self.get_unchecked_mut(drop_range) };
-
-        // SAFETY:
-        // - this will always shrink the vector because of the above bounds check
-        // - [`new_len`, `self.len`) will be dropped through the call to `drop_in_place` below
-        unsafe { self.set_len(len) };
-
-        // SAFETY:
-        // - the dropped values are valid `T`s by the type invariant
-        // - we are allowed to invalidate [`new_len`, `old_len`) because we just changed the
-        //   len, therefore we have exclusive access to [`new_len`, `old_len`)
-        unsafe { ptr::drop_in_place(ptr) };
     }
 }
 

-- 
2.48.1

[PATCH v2 4/4] rust: alloc: replace `Vec::set_len` with `inc_len`

[Tamir Duberstein]

Rename `set_len` to `inc_len` and simplify its safety contract.

Note that the usage in `CString::try_from_fmt` remains correct as the
receiver is known to have `len == 0`.

Signed-off-by: Tamir Duberstein <tamird@gmail.com>
---
 rust/kernel/alloc/kvec.rs | 20 ++++++++++----------
 rust/kernel/str.rs        |  2 +-
 rust/kernel/uaccess.rs    |  2 +-
 3 files changed, 12 insertions(+), 12 deletions(-)

diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
index 6f4dc89ef7f8..977f6b2e899f 100644
--- a/rust/kernel/alloc/kvec.rs
+++ b/rust/kernel/alloc/kvec.rs
@@ -185,17 +185,17 @@ pub fn len(&self) -> usize {
         self.len
     }
 
-    /// Forcefully sets `self.len` to `new_len`.
+    /// Increments `self.len` by `additional`.
     ///
     /// # Safety
     ///
-    /// - `new_len` must be less than or equal to [`Self::capacity`].
-    /// - If `new_len` is greater than `self.len`, all elements within the interval
-    ///   [`self.len`,`new_len`) must be initialized.
+    /// - `additional` must be less than or equal to `self.capacity - self.len`.
+    /// - All elements within the interval [`self.len`,`self.len + additional`) must be initialized.
     #[inline]
-    pub unsafe fn set_len(&mut self, new_len: usize) {
-        debug_assert!(new_len <= self.capacity());
-        self.len = new_len;
+    pub unsafe fn inc_len(&mut self, additional: usize) {
+        // Guaranteed by the type invariant to never underflow.
+        debug_assert!(additional <= self.capacity() - self.len());
+        self.len += additional;
     }
 
     /// Decreases `self.len` by `count`.
@@ -319,7 +319,7 @@ pub fn push(&mut self, v: T, flags: Flags) -> Result<(), AllocError> {
         // 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.
-        unsafe { self.set_len(self.len() + 1) };
+        unsafe { self.inc_len(1) };
         Ok(())
     }
 
@@ -525,7 +525,7 @@ pub fn extend_with(&mut self, n: usize, value: T, flags: Flags) -> Result<(), Al
         // SAFETY:
         // - `self.len() + n < self.capacity()` due to the call to reserve above,
         // - the loop and the line above initialized the next `n` elements.
-        unsafe { self.set_len(self.len() + n) };
+        unsafe { self.inc_len(n) };
 
         Ok(())
     }
@@ -556,7 +556,7 @@ pub fn extend_from_slice(&mut self, other: &[T], flags: Flags) -> Result<(), All
         //   the length by the same number.
         // - `self.len() + other.len() <= self.capacity()` is guaranteed by the preceding `reserve`
         //   call.
-        unsafe { self.set_len(self.len() + other.len()) };
+        unsafe { self.inc_len(other.len()) };
         Ok(())
     }
 
diff --git a/rust/kernel/str.rs b/rust/kernel/str.rs
index 28e2201604d6..005713839e9e 100644
--- a/rust/kernel/str.rs
+++ b/rust/kernel/str.rs
@@ -840,7 +840,7 @@ pub fn try_from_fmt(args: fmt::Arguments<'_>) -> Result<Self, Error> {
 
         // SAFETY: The number of bytes that can be written to `f` is bounded by `size`, which is
         // `buf`'s capacity. The contents of the buffer have been initialised by writes to `f`.
-        unsafe { buf.set_len(f.bytes_written()) };
+        unsafe { buf.inc_len(f.bytes_written()) };
 
         // Check that there are no `NUL` bytes before the end.
         // SAFETY: The buffer is valid for read because `f.bytes_written()` is bounded by `size`
diff --git a/rust/kernel/uaccess.rs b/rust/kernel/uaccess.rs
index 719b0a48ff55..0aa5455a18be 100644
--- a/rust/kernel/uaccess.rs
+++ b/rust/kernel/uaccess.rs
@@ -291,7 +291,7 @@ pub fn read_all<A: Allocator>(mut self, buf: &mut Vec<u8, A>, flags: Flags) -> R
 
         // SAFETY: Since the call to `read_raw` was successful, so the next `len` bytes of the
         // vector have been initialized.
-        unsafe { buf.set_len(buf.len() + len) };
+        unsafe { buf.inc_len(len) };
         Ok(())
     }
 }

-- 
2.48.1

Re: [PATCH v2 3/4] rust: alloc: refactor `Vec::truncate` using `dec_len`

[Tamir Duberstein]

On Tue, Mar 18, 2025 at 4:14 PM Tamir Duberstein <tamird@gmail.com> wrote:
>
> Use `checked_sub` to satisfy the safety requirements of `dec_len` and
> replace nearly the whole body of `truncate` with a call to `dec_len`.
>
> Signed-off-by: Tamir Duberstein <tamird@gmail.com>
> ---
>  rust/kernel/alloc/kvec.rs | 29 +++++++++++------------------
>  1 file changed, 11 insertions(+), 18 deletions(-)
>
> diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
> index 97cc5ab11e2a..6f4dc89ef7f8 100644
> --- a/rust/kernel/alloc/kvec.rs
> +++ b/rust/kernel/alloc/kvec.rs
> @@ -489,25 +489,18 @@ pub fn reserve(&mut self, additional: usize, flags: Flags) -> Result<(), AllocEr
>      /// # Ok::<(), Error>(())
>      /// ```
>      pub fn truncate(&mut self, len: usize) {
> -        if len >= self.len() {
> -            return;
> +        match self.len().checked_sub(len) {
> +            None => {}
> +            Some(count) => {
> +                // SAFETY: `count` is `self.len() - len` so it is guaranteed to be less than or
> +                // equal to `self.len()`.
> +                let tail = unsafe { self.dec_len(count) };
> +
> +                // SAFETY: the contract of `dec_len` guarantees that the elements in `tail` are
> +                // valid elements whose ownership has been transferred to the caller.
> +                unsafe { ptr::drop_in_place(ptr) };

Whoops, this should be s/ptr/tail/. Will fix on respin if necessary.

> +            }
>          }
> -
> -        let drop_range = len..self.len();
> -
> -        // SAFETY: `drop_range` is a subrange of `[0, len)` by the bounds check above.
> -        let ptr: *mut [T] = unsafe { self.get_unchecked_mut(drop_range) };
> -
> -        // SAFETY:
> -        // - this will always shrink the vector because of the above bounds check
> -        // - [`new_len`, `self.len`) will be dropped through the call to `drop_in_place` below
> -        unsafe { self.set_len(len) };
> -
> -        // SAFETY:
> -        // - the dropped values are valid `T`s by the type invariant
> -        // - we are allowed to invalidate [`new_len`, `old_len`) because we just changed the
> -        //   len, therefore we have exclusive access to [`new_len`, `old_len`)
> -        unsafe { ptr::drop_in_place(ptr) };
>      }
>  }
>
>
> --
> 2.48.1
>

Re: [PATCH v2 3/4] rust: alloc: refactor `Vec::truncate` using `dec_len`

[Alice Ryhl]

On Tue, Mar 18, 2025 at 04:13:55PM -0400, Tamir Duberstein wrote:
> Use `checked_sub` to satisfy the safety requirements of `dec_len` and
> replace nearly the whole body of `truncate` with a call to `dec_len`.
> 
> Signed-off-by: Tamir Duberstein <tamird@gmail.com>
> ---
>  rust/kernel/alloc/kvec.rs | 29 +++++++++++------------------
>  1 file changed, 11 insertions(+), 18 deletions(-)
> 
> diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
> index 97cc5ab11e2a..6f4dc89ef7f8 100644
> --- a/rust/kernel/alloc/kvec.rs
> +++ b/rust/kernel/alloc/kvec.rs
> @@ -489,25 +489,18 @@ pub fn reserve(&mut self, additional: usize, flags: Flags) -> Result<(), AllocEr
>      /// # Ok::<(), Error>(())
>      /// ```
>      pub fn truncate(&mut self, len: usize) {
> -        if len >= self.len() {
> -            return;
> +        match self.len().checked_sub(len) {
> +            None => {}
> +            Some(count) => {

This could be simplified as:
if let Some(count) = self.len().checked_sub(len) {
    // logic here
}

or
let Some(count) = self.len().checked_sub(len) else {
    return;
}
// logic here

> +                // SAFETY: `count` is `self.len() - len` so it is guaranteed to be less than or
> +                // equal to `self.len()`.
> +                let tail = unsafe { self.dec_len(count) };
> +
> +                // SAFETY: the contract of `dec_len` guarantees that the elements in `tail` are
> +                // valid elements whose ownership has been transferred to the caller.
> +                unsafe { ptr::drop_in_place(ptr) };

We have a mutable reference to these elements until after the
`drop_in_place` call, but the elements are invalidated by that call.
This means that we have a mutable reference to invalid values, which
violates the invariants for mutable references.

Consider converting to a raw pointer when creating `tail` instead to
avoid that:

let tail: *mut [T] = unsafe { self.dec_len(count) };
unsafe { ptr::drop_in_place(ptr) };

Alice

Re: [PATCH v2 3/4] rust: alloc: refactor `Vec::truncate` using `dec_len`

[Tamir Duberstein]

On Wed, Mar 19, 2025 at 5:53 AM Alice Ryhl <aliceryhl@google.com> wrote:
>
> On Tue, Mar 18, 2025 at 04:13:55PM -0400, Tamir Duberstein wrote:
> > Use `checked_sub` to satisfy the safety requirements of `dec_len` and
> > replace nearly the whole body of `truncate` with a call to `dec_len`.
> >
> > Signed-off-by: Tamir Duberstein <tamird@gmail.com>
> > ---
> >  rust/kernel/alloc/kvec.rs | 29 +++++++++++------------------
> >  1 file changed, 11 insertions(+), 18 deletions(-)
> >
> > diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
> > index 97cc5ab11e2a..6f4dc89ef7f8 100644
> > --- a/rust/kernel/alloc/kvec.rs
> > +++ b/rust/kernel/alloc/kvec.rs
> > @@ -489,25 +489,18 @@ pub fn reserve(&mut self, additional: usize, flags: Flags) -> Result<(), AllocEr
> >      /// # Ok::<(), Error>(())
> >      /// ```
> >      pub fn truncate(&mut self, len: usize) {
> > -        if len >= self.len() {
> > -            return;
> > +        match self.len().checked_sub(len) {
> > +            None => {}
> > +            Some(count) => {
>
> This could be simplified as:
> if let Some(count) = self.len().checked_sub(len) {
>     // logic here
> }
>
> or
> let Some(count) = self.len().checked_sub(len) else {
>     return;
> }
> // logic here

👍

>
> > +                // SAFETY: `count` is `self.len() - len` so it is guaranteed to be less than or
> > +                // equal to `self.len()`.
> > +                let tail = unsafe { self.dec_len(count) };
> > +
> > +                // SAFETY: the contract of `dec_len` guarantees that the elements in `tail` are
> > +                // valid elements whose ownership has been transferred to the caller.
> > +                unsafe { ptr::drop_in_place(ptr) };
>
> We have a mutable reference to these elements until after the
> `drop_in_place` call, but the elements are invalidated by that call.
> This means that we have a mutable reference to invalid values, which
> violates the invariants for mutable references.
>
> Consider converting to a raw pointer when creating `tail` instead to
> avoid that:
>
> let tail: *mut [T] = unsafe { self.dec_len(count) };
> unsafe { ptr::drop_in_place(ptr) };

👍