rust: alloc: split `Vec::set_len` into `Vec::{inc,dec}_len`
Subsystems (2)
v4 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 v4:
- Rebase on rust/alloc-next to resolve conflict with "rust: alloc: use spare_capacity_mut to reduce unsafe".
- Link: https://lore.kernel.org/all/[email protected]/
- Link to v3: https://lore.kernel.org/r/[email protected]
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 | 81 +++++++++++++++++++++++++++-------------------- rust/kernel/str.rs | 2 +- rust/kernel/uaccess.rs | 2 +- 3 files changed, 49 insertions(+), 36 deletions(-)
---
base-commit: c3152988c047a7b6abb10d4dc5e24fafbabe8b7e
change-id: 20250316-vec-set-len-99be6cc48374
Best regards,
Signature · 1 line
Tamir Duberstein <[email protected]>
PATCH v4 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 | 15 +++++++++------ 1 file changed, 9 insertions(+), 6 deletions(-)
rust/kernel/alloc/kvec.rs +9 -6
@@ -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 >;
@@ -817,12 +819,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
Re: [PATCH v4 1/4] rust: alloc: add Vec::len() <= Vec::capacity invariant
Quoted 13 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.lenalways represents the exact number of elements stored in the vector.
-self.layoutrepresents 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.capacityrather thanself.layout.lenas the latter is zero for a vector of ZSTs.
Quoted 5 lines
Update a safety comment touched by this patch to correctly reference
reallocrather thanallocand replace "leaves" with "leave" to improve grammar.Signed-off-by Tamir Duberstein <[email protected]>
PATCH v4 2/4 rust: alloc: add `Vec::dec_len`
In reply to Tamir DubersteinAdd 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
@@ -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
PATCH v4 3/4 rust: alloc: refactor `Vec::truncate` using `dec_len`
In reply to Tamir DubersteinUse 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
@@ -488,23 +488,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
PATCH v4 4/4 rust: alloc: replace `Vec::set_len` with `inc_len`
In reply to Tamir DubersteinRename 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
@@ -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`.
@@ -317,7 +316,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 (()) }
@@ -521,7 +520,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 (()) }
@@ -552,7 +551,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
@@ -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
@@ -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
Danilo Krummrich
maintainerQuoted 2 lines · Tamir Duberstein
This series is the product of a discussion[0] on the safety requirements of
set_len.
With the following changes, applied to alloc-next, thanks!
* Temporarily add #[expect(unused)] to dec_len() to avoid a compiler warning.
- Danilo