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

[PATCH v3 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`.

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 v3:
- Fix compilation (s/ptr/tail/) in "refactor `Vec::truncate` using
  `dec_len`".
- Fix grammar and s/alloc/realloc/ in a safety comment touched by "rust:
  alloc: add Vec::len() <= Vec::capacity invariant".
- Use `if let`. (Alice Ryhl).
- Avoid mutable reference after `drop_in_place`. (Alice Ryhl).
- Rebase on rust/alloc-next.
- Remove dependency on the `Vec::truncate` series which has been merged.
- Link to v2: https://lore.kernel.org/r/20250318-vec-set-len-v2-0-293d55f82d18@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 | 85 +++++++++++++++++++++++++++--------------------
 rust/kernel/str.rs        |  2 +-
 rust/kernel/uaccess.rs    |  2 +-
 3 files changed, 51 insertions(+), 38 deletions(-)
---
base-commit: 1679b7159379d11100e4ab7d1de23c8cd7765aa1
change-id: 20250316-vec-set-len-99be6cc48374

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

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

Update a safety comment touched by this patch to correctly reference
`realloc` rather than `alloc` and replace "leaves" with "leave" to
improve grammar.

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 7ebec5c4a277..f8045b6c8976 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> {
@@ -262,8 +264,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>;
 
@@ -289,8 +291,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) };
 
@@ -822,12 +824,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 `realloc` this operation
+            // may shrink the buffer or leave it as it is.
             ptr = match unsafe {
                 A::realloc(Some(buf.cast()), layout.into(), old_layout.into(), flags)
             } {

-- 
2.49.0

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

[Alice Ryhl]

On Mon, Apr 7, 2025 at 4:52 PM Tamir Duberstein <tamird@gmail.com> wrote:
>
> 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.
>
> Update a safety comment touched by this patch to correctly reference
> `realloc` rather than `alloc` and replace "leaves" with "leave" to
> improve grammar.
>
> Signed-off-by: Tamir Duberstein <tamird@gmail.com>

This change has a conflict with the spare_capacity_mut patch in alloc-next.

Alice

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

[Tamir Duberstein]

On Wed, Apr 16, 2025 at 10:41 AM Alice Ryhl <aliceryhl@google.com> wrote:
>
> On Mon, Apr 7, 2025 at 4:52 PM Tamir Duberstein <tamird@gmail.com> wrote:
> >
> > 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.
> >
> > Update a safety comment touched by this patch to correctly reference
> > `realloc` rather than `alloc` and replace "leaves" with "leave" to
> > improve grammar.
> >
> > Signed-off-by: Tamir Duberstein <tamird@gmail.com>
>
> This change has a conflict with the spare_capacity_mut patch in alloc-next.

Indeed. I have resolved it locally but was holding off until some
reviews arrived. I guess I'll respin now.

[PATCH v3 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 f8045b6c8976..844154d310f0 100644
--- a/rust/kernel/alloc/kvec.rs
+++ b/rust/kernel/alloc/kvec.rs
@@ -201,6 +201,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.49.0

[PATCH v3 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 | 24 ++++++++----------------
 1 file changed, 8 insertions(+), 16 deletions(-)

diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
index 844154d310f0..d0b46aa36169 100644
--- a/rust/kernel/alloc/kvec.rs
+++ b/rust/kernel/alloc/kvec.rs
@@ -493,23 +493,15 @@ 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;
+        if let Some(count) = self.len().checked_sub(len) {
+            // SAFETY: `count` is `self.len() - len` so it is guaranteed to be less than or
+            // equal to `self.len()`.
+            let ptr: *mut [T] = unsafe { self.dec_len(count) };
+
+            // SAFETY: the contract of `dec_len` guarantees that the elements in `ptr` 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: By the above bounds check, it is guaranteed that `len < self.capacity()`.
-        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.49.0

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

[Andrew Ballance]

On Mon, Apr 07, 2025 at 10:52:33AM -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>

This looks cleaner than  my version.

Reviewed-by: Andrew Ballance <andrewjballance@gmail.com>

[PATCH v3 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 | 25 ++++++++++++-------------
 rust/kernel/str.rs        |  2 +-
 rust/kernel/uaccess.rs    |  2 +-
 3 files changed, 14 insertions(+), 15 deletions(-)

diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
index d0b46aa36169..fdfdb77de7f1 100644
--- a/rust/kernel/alloc/kvec.rs
+++ b/rust/kernel/alloc/kvec.rs
@@ -185,20 +185,19 @@ 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());
-
-        // INVARIANT: By the safety requirements of this method `new_len` represents the exact
-        // number of elements stored within `self`.
-        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());
+        // INVARIANT: By the safety requirements of this method this represents the exact number of
+        // elements stored within `self`.
+        self.len += additional;
     }
 
     /// Decreases `self.len` by `count`.
@@ -322,7 +321,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(())
     }
 
@@ -526,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(())
     }
@@ -557,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 878111cb77bc..d3b0b00e05fa 100644
--- a/rust/kernel/str.rs
+++ b/rust/kernel/str.rs
@@ -886,7 +886,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 80a9782b1c6e..e4882f113d79 100644
--- a/rust/kernel/uaccess.rs
+++ b/rust/kernel/uaccess.rs
@@ -290,7 +290,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.49.0

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

[Tamir Duberstein]

On Mon, Apr 7, 2025 at 10:52 AM Tamir Duberstein <tamird@gmail.com> wrote:
>
> This series is the product of a discussion[0] on the safety requirements
> of `set_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]

Oops, dangling reference here. I removed the mention of Andrew's
series because it has been merged.

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

[Tamir Duberstein]

On Mon, Apr 7, 2025 at 10:53 AM Tamir Duberstein <tamird@gmail.com> wrote:
>
> On Mon, Apr 7, 2025 at 10:52 AM Tamir Duberstein <tamird@gmail.com> wrote:
> >
> > This series is the product of a discussion[0] on the safety requirements
> > of `set_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]
>
> Oops, dangling reference here. I removed the mention of Andrew's
> series because it has been merged.

Benno, Alice: did you folks want to take a look?

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

[Alice Ryhl]

On Mon, Apr 07, 2025 at 10:52:30AM -0400, Tamir Duberstein wrote:
> This series is the product of a discussion[0] on the safety requirements
> of `set_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>

I'm still wondering if the divergence from upstream alloc is worth it...
but the code is okay.

Reviewed-by: Alice Ryhl <aliceryhl@google.com>

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

[Danilo Krummrich]

On 4/16/25 3:28 PM, Alice Ryhl wrote:
> On Mon, Apr 07, 2025 at 10:52:30AM -0400, Tamir Duberstein wrote:
>> This series is the product of a discussion[0] on the safety requirements
>> of `set_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>
> 
> I'm still wondering if the divergence from upstream alloc is worth it...
> but the code is okay.
> 
> Reviewed-by: Alice Ryhl <aliceryhl@google.com>

Does this still apply to patch 1 in v4 [1]?

[1] 
https://lore.kernel.org/rust-for-linux/20250416-vec-set-len-v4-1-112b222604cd@gmail.com/

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

[Alice Ryhl]

On Tue, Apr 22, 2025 at 05:42:24PM +0200, Danilo Krummrich wrote:
> On 4/16/25 3:28 PM, Alice Ryhl wrote:
> > On Mon, Apr 07, 2025 at 10:52:30AM -0400, Tamir Duberstein wrote:
> > > This series is the product of a discussion[0] on the safety requirements
> > > of `set_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>
> > 
> > I'm still wondering if the divergence from upstream alloc is worth it...
> > but the code is okay.
> > 
> > Reviewed-by: Alice Ryhl <aliceryhl@google.com>
> 
> Does this still apply to patch 1 in v4 [1]?
> 
> [1] https://lore.kernel.org/rust-for-linux/20250416-vec-set-len-v4-1-112b222604cd@gmail.com/

I replied with a new tag.

Alice