Skip to contentSkip to conversation

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

PATCH Superseded Tamir Duberstein 2 participants 8 messages Mar 18, 2025 – Mar 19, 2025

Subsystems (2)

v2 of 4 Superseded Latest is v4 →

lore
Share & tools
lore
#0 lore raw

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

This series depends on "rust: alloc: add Vec::truncate method" by Andrew Ballance <[email protected]> [1] and rewrites Vec::truncate using Vec::dec_len.

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

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

PATCH v2 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.

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

PATCH v2 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 ce58ee66c99b..97cc5ab11e2a 100644
@@ -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] {
Signature · 1 line
2.48.1
#3 lore raw

PATCH v2 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 | 29 +++++++++++------------------
 1 file changed, 11 insertions(+), 18 deletions(-)
rust/kernel/alloc/kvec.rs +11 -18
index 97cc5ab11e2a..6f4dc89ef7f8 100644
@@ -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) };
     }
 }
 
Signature · 1 line
2.48.1
#4 lore raw

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

Quoted 19 lines · 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 | 29 +++++++++++------------------
 1 file changed, 11 insertions(+), 18 deletions(-)
rust/kernel/alloc/kvec.rs +0 -2
index 97cc5ab11e2a..6f4dc89ef7f8 100644
@@ -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;

rust/kernel/alloc/kvec.rs pub fn reserve(&mut self, additional: usize, flags: Flags) -> Result<(), AllocEr · line 501

Quoted 10 lines
rust/kernel/alloc/kvec.rs +10 -0
+        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.

Quoted 25 lines
rust/kernel/alloc/kvec.rs +1 -17
+            }
         }
-
-        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

maintainer
#5 lore raw

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

In reply to Tamir Duberstein
Quoted 13 lines · 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 | 29 +++++++++++------------------
 1 file changed, 11 insertions(+), 18 deletions(-)
rust/kernel/alloc/kvec.rs +0 -0
index 97cc5ab11e2a..6f4dc89ef7f8 100644

rust/kernel/alloc/kvec.rs pub fn reserve(&mut self, additional: usize, flags: Flags) -> Result<(), AllocEr · line 494

Quoted 8 lines
rust/kernel/alloc/kvec.rs +3 -2
@@ -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

rust/kernel/alloc/kvec.rs pub fn reserve(&mut self, additional: usize, flags: Flags) -> Result<(), AllocEr · line 501

Quoted 7 lines
rust/kernel/alloc/kvec.rs +7 -0
+                // 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

#6 lore raw

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

Quoted 29 lines · Alice Ryhl
Quoted 13 lines · 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 | 29 +++++++++++------------------
 1 file changed, 11 insertions(+), 18 deletions(-)
rust/kernel/alloc/kvec.rs +0 -0
index 97cc5ab11e2a..6f4dc89ef7f8 100644

rust/kernel/alloc/kvec.rs pub fn reserve(&mut self, additional: usize, flags: Flags) -> Result<(), AllocEr · line 494

Quoted 8 lines
rust/kernel/alloc/kvec.rs +3 -2
@@ -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
}
Quoted 5 lines

or

let Some(count) = self.len().checked_sub(len) else {
    return;
}

// logic here

👍

Quoted 14 lines

rust/kernel/alloc/kvec.rs pub fn reserve(&mut self, additional: usize, flags: Flags) -> Result<(), AllocEr · line 501

Quoted 8 lines
rust/kernel/alloc/kvec.rs +7 -0
+                // 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.

Quoted 5 lines

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) };

👍

#7 lore raw

PATCH v2 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 | 20 ++++++++++----------
 rust/kernel/str.rs        |  2 +-
 rust/kernel/uaccess.rs    |  2 +-
 3 files changed, 12 insertions(+), 12 deletions(-)
rust/kernel/alloc/kvec.rs +10 -10
index 6f4dc89ef7f8..977f6b2e899f 100644
@@ -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(())
     }
 
rust/kernel/str.rs +1 -1
index 28e2201604d6..005713839e9e 100644
@@ -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`
rust/kernel/uaccess.rs +1 -1
index 719b0a48ff55..0aa5455a18be 100644
@@ -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(())
     }
 }
Signature · 1 line
2.48.1