rust: alloc: split `Vec::set_len` into `Vec::{inc,dec}_len`
Subsystems (2)
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]>
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
@@ -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
Alice Ryhl
maintainerRe: [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.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]>
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
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.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 7 lines
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]>This change has a conflict with the
spare_capacity_mutpatch 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`
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 v3 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
@@ -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
Re: [PATCH v3 3/4] rust: alloc: refactor `Vec::truncate` using `dec_len`
Quoted 4 lines · Tamir Duberstein
Use
checked_subto satisfy the safety requirements ofdec_lenand replace nearly the whole body oftruncatewith a call todec_len.Signed-off-by Tamir Duberstein <[email protected]>
This looks cleaner than my version.
PATCH v3 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`.
@@ -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
@@ -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
Quoted 6 lines · Tamir Duberstein
This series is the product of a discussion[0] on the safety requirements of
set_len.
Oops, dangling reference here. I removed the mention of Andrew's series because it has been merged.
Quoted 11 lines · Tamir Duberstein
Quoted 6 lines · Tamir Duberstein
This series is the product of a discussion[0] on the safety requirements of
set_len.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?
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.
Danilo Krummrich
maintainerQuoted 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.
Reviewed-by Alice Ryhl <[email protected]>
Does this still apply to patch 1 in v4 [1]?
[1] https://lore.kernel.org/rust-for-linux/[email protected]/
Alice Ryhl
maintainerQuoted 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.
Reviewed-by Alice Ryhl <[email protected]>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