Skip to contentSkip to conversation

rust: alloc: split `Vec::set_len` into `Vec::{inc,dec}_len`

PATCH Superseded Tamir Duberstein 4 participants 13 messages Apr 7, 2025 – Apr 23, 2025

Subsystems (2)

v3 of 4 Superseded Latest is v4 →

lore
Share & tools
lore
#0 lore raw

v3 cover rust: alloc: split `Vec::set_len` into `Vec::{inc,dec}_len`

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

---
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/[email protected]

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/[email protected]

---
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,

Signature · 1 line
Tamir Duberstein <[email protected]>
#1 lore raw

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

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.

---
 rust/kernel/alloc/kvec.rs | 19 +++++++++++--------
 1 file changed, 11 insertions(+), 8 deletions(-)
rust/kernel/alloc/kvec.rs +11 -8
index 7ebec5c4a277..f8045b6c8976 100644
@@ -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)
             } {
Signature · 1 line
2.49.0
maintainer
#2 lore raw

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

Quoted 14 lines · 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.

Quoted 5 lines

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

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

Alice

#3 lore raw

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

Quoted 16 lines · Alice Ryhl
Quoted 14 lines · 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.

Quoted 7 lines
Quoted 5 lines

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

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.

#4 lore raw

PATCH v3 2/4 rust: alloc: add `Vec::dec_len`

In reply to 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.

---
 rust/kernel/alloc/kvec.rs | 19 +++++++++++++++++++
 1 file changed, 19 insertions(+)
rust/kernel/alloc/kvec.rs +19 -0
index f8045b6c8976..844154d310f0 100644
@@ -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] {
Signature · 1 line
2.49.0
#5 lore raw

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

In reply to 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.

---
 rust/kernel/alloc/kvec.rs | 24 ++++++++----------------
 1 file changed, 8 insertions(+), 16 deletions(-)
rust/kernel/alloc/kvec.rs +8 -16
index 844154d310f0..d0b46aa36169 100644
@@ -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) };
     }
 }
 
Signature · 1 line
2.49.0
#7 lore raw

PATCH v3 4/4 rust: alloc: replace `Vec::set_len` with `inc_len`

In reply to 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.

---
 rust/kernel/alloc/kvec.rs | 25 ++++++++++++-------------
 rust/kernel/str.rs        |  2 +-
 rust/kernel/uaccess.rs    |  2 +-
 3 files changed, 14 insertions(+), 15 deletions(-)
rust/kernel/alloc/kvec.rs +12 -13
index d0b46aa36169..fdfdb77de7f1 100644
@@ -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(())
     }
 
rust/kernel/str.rs +1 -1
index 878111cb77bc..d3b0b00e05fa 100644
@@ -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`
rust/kernel/uaccess.rs +1 -1
index 80a9782b1c6e..e4882f113d79 100644
@@ -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(())
     }
 }
Signature · 1 line
2.49.0
maintainer Reviewed-by on the v3 series
#10 lore raw
In reply to Tamir Duberstein
Quoted 6 lines · Tamir Duberstein

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

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

maintainer
#11 lore raw
Quoted 4 lines · Alice Ryhl
Quoted 3 lines · Tamir Duberstein

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

Quoted 8 lines
Quoted 3 lines

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

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

[1] https://lore.kernel.org/rust-for-linux/[email protected]/

maintainer
#12 lore raw
Quoted 9 lines · Danilo Krummrich
Quoted 8 lines · Alice Ryhl
Quoted 6 lines · Tamir Duberstein

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

Quoted 8 lines
Quoted 4 lines

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

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

[1] https://lore.kernel.org/rust-for-linux/[email protected]/

I replied with a new tag.

Alice