Additional methods for Vec
Subsystems (2)
Alice Ryhl
maintainercover Additional methods for Vec
This adds various Vec methods. Some of them are needed by Rust Binder, and others are needed in other places. Each commit explains where it is needed.
I'm not sure what we concluded on the set_len / dec_len changes, so I don't depend on that series for now.
This series is based on top of Vec::truncate from
https://lore.kernel.org/rust-for-linux/[email protected]/
---
Alice Ryhl (5):
rust: alloc: add Vec::clear
rust: alloc: add Vec::pop
rust: alloc: add Vec::push_within_capacity
rust: alloc: add Vec::drain_all
rust: alloc: add Vec::retain
rust/kernel/alloc/kvec.rs | 147 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 147 insertions(+)
---
base-commit: a337a03281efc4553191b432d757d4c04884bf4c
change-id: 20250320-vec-methods-adfa41e55311
Best regards,
Signature · 1 line
Alice Ryhl <[email protected]>
Alice Ryhl
maintainerPATCH 1/5 rust: alloc: add Vec::clear
Our custom Vec type is missing the stdlib method clear, thus add it. It will be used in the miscdevice sample.
--- rust/kernel/alloc/kvec.rs | 20 ++++++++++++++++++++ 1 file changed, 20 insertions(+)
rust/kernel/alloc/kvec.rs +20 -0
@@ -395,6 +395,26 @@ pub fn into_raw_parts(self) -> (*mut T, usize, usize) { (ptr, len, capacity) } +/// Clears the vector, removing all values. +/// +/// Note that this method has no effect on the allocated capacity +/// of the vector. +/// +/// # Examples +/// +/// ``` +/// let mut v = kernel::kvec![1, 2, 3]?; +/// +/// v.clear(); +/// +/// assert!(v.is_empty()); +/// # Ok::<(), Error>(()) +/// ``` +#[inline] +pub fn clear (&mut self) { + self.truncate (0 ); + } +/// Ensures that the capacity exceeds the length by at least `additional` elements. /// /// # Examples
Signature · 1 line
2.49.0.rc1.451.g8f38331e32-goog
Re: [PATCH 1/5] rust: alloc: add Vec::clear
Quoted 4 lines · Alice Ryhl
Our custom Vec type is missing the stdlib method
clear, thus add it. It will be used in the miscdevice sample.Signed-off-by Alice Ryhl <[email protected]>
---
Cheers,
Benno
Quoted 35 lines
--- rust/kernel/alloc/kvec.rs | 20 ++++++++++++++++++++ 1 file changed, 20 insertions(+)rust/kernel/alloc/kvec.rs +20
-0@@ -395,6 +395,26 @@ pub fn into_raw_parts(self) -> (*mut T, usize, usize) { (ptr, len, capacity) } +/// Clears the vector, removing all values. +/// +/// Note that this method has no effect on the allocated capacity +/// of the vector. +/// +/// # Examples +/// +/// ``` +/// let mut v = kernel::kvec![1, 2, 3]?; +/// +/// v.clear(); +/// +/// assert!(v.is_empty()); +/// # Ok::<(), Error>(()) +/// ``` +#[inline] +pub fn clear (&mut self) { + self.truncate (0 ); + } +/// Ensures that the capacity exceeds the length by at least `additional` elements. /// /// # Examples
Re: [PATCH 1/5] rust: alloc: add Vec::clear
In reply to Alice RyhlQuoted 5 lines · Alice Ryhl
Our custom Vec type is missing the stdlib method
clear, thus add it. It will be used in the miscdevice sample.Signed-off-by Alice Ryhl <[email protected]>
Alice Ryhl
maintainerPATCH 2/5 rust: alloc: add Vec::pop
In reply to Alice RyhlThis introduces a basic method that our custom Vec is missing. I expect that it will be used in many places, but at the time of writing, Rust Binder has six calls to Vec::pop.
--- rust/kernel/alloc/kvec.rs | 31 +++++++++++++++++++++++++++++++ 1 file changed, 31 insertions(+)
rust/kernel/alloc/kvec.rs +31 -0
@@ -302,6 +302,37 @@ pub fn push(&mut self, v: T, flags: Flags) -> Result<(), AllocError> {Ok (()) } +/// Removes the last element from a vector and returns it, or `None` if it is empty. +/// +/// # Examples +/// +/// ``` +/// let mut v = KVec::new(); +/// v.push(1, GFP_KERNEL)?; +/// v.push(2, GFP_KERNEL)?; +/// assert_eq!(&v, &[1, 2]); +/// +/// assert_eq!(v.pop(), Some(2)); +/// assert_eq!(v.pop(), Some(1)); +/// assert_eq!(v.pop(), None); +/// # Ok::<(), Error>(()) +/// ``` +pub fn pop (&mut self) ->Option <T > { +let Some (len_sub_1) = self.len.checked_sub (1 )else { +return None ; + }; + +// INVARIANT: If the first `len` elements are valid, then the first `len-1` elements are +// valid. + self.len = len_sub_1; + +// INVARIANT: This invalidates a value in this vector's allocation, but the Vec invariants +// do not require it to be valid because `self.len <= len_sub_1`. +// SAFETY: Since `len_sub_1` is less than the value `self.len` had at the beginning of +// `pop`, this index holds a valid value. +Some (unsafe { self.as_mut_ptr ().add (len_sub_1).read () }) + } +/// Creates a new [`Vec`] instance with at least the given capacity. /// /// # Examples
Signature · 1 line
2.49.0.rc1.451.g8f38331e32-goog
Alice Ryhl
maintainerPATCH 3/5 rust: alloc: add Vec::push_within_capacity
In reply to Alice RyhlThis introduces a new method called push_within_capacity for appending to a vector without attempting to allocate if the capacity is full. Rust Binder will use this in various places to safely push to a vector while holding a spinlock.
The existing Vec::push method is reimplemented in terms of the new method.
--- rust/kernel/alloc/kvec.rs | 25 +++++++++++++++++++++++++ 1 file changed, 25 insertions(+)
rust/kernel/alloc/kvec.rs +25 -0
@@ -284,6 +284,31 @@ pub fn spare_capacity_mut(&mut self) -> &mut [MaybeUninit<T>] {/// ``` pub fn push (&mut self, v:T , flags:Flags ) ->Result <(),AllocError > { self.reserve (1 , flags)?; +let err = self.push_within_capacity (v); +// SAFETY: The call to `reserve` was successful, so `push_within_capacity` cannot fail. +unsafe { err.unwrap_unchecked () }; +Ok (()) + } + +/// Appends an element to the back of the [`Vec`] instance. +/// +/// Fails if the vector does not have capacity for the new element. +/// +/// # Examples +/// +/// ``` +/// let mut v = KVec::with_capacity(10, GFP_KERNEL); +/// for i in 0..10 { +/// v.push_within_capacity(i).unwrap(); +/// } +/// +/// assert!(v.push_within_capacity(11).is_err()); +/// # Ok::<(), Error>(()) +/// ``` +pub fn push_within_capacity (&mut self, v:T ) ->Result <(),T > { +if self.len () >= self.capacity () { +return Err (v); + }// SAFETY: // - `self.len` is smaller than `self.capacity` and hence, the resulting pointer is
Signature · 1 line
2.49.0.rc1.451.g8f38331e32-goog
Re: [PATCH 3/5] rust: alloc: add Vec::push_within_capacity
Quoted 9 lines · Alice Ryhl
This introduces a new method called
push_within_capacityfor appending to a vector without attempting to allocate if the capacity is full. Rust Binder will use this in various places to safely push to a vector while holding a spinlock.The existing
Vec::pushmethod is reimplemented in terms of the new method.Signed-off-by Alice Ryhl <[email protected]>
---
Cheers,
Benno
Quoted 3 lines
--- rust/kernel/alloc/kvec.rs | 25 +++++++++++++++++++++++++ 1 file changed, 25 insertions(+)
Re: [PATCH 3/5] rust: alloc: add Vec::push_within_capacity
In reply to Alice RyhlQuoted 19 lines · Alice Ryhl
This introduces a new method called
push_within_capacityfor appending to a vector without attempting to allocate if the capacity is full. Rust Binder will use this in various places to safely push to a vector while holding a spinlock.The existing
Vec::pushmethod is reimplemented in terms of the new method.Signed-off-by Alice Ryhl <[email protected]>--- rust/kernel/alloc/kvec.rs | 25 +++++++++++++++++++++++++ 1 file changed, 25 insertions(+)rust/kernel/alloc/kvec.rs +0
-0
rust/kernel/alloc/kvec.rs pub fn spare_capacity_mut(&mut self) -> &mut [MaybeUninit<T>] { · line 289
Quoted 6 lines
rust/kernel/alloc/kvec.rs +3
-0@@ -284,6 +284,31 @@ pub fn spare_capacity_mut(&mut self) -> &mut [MaybeUninit<T>] {/// ``` pub fn push (&mut self, v:T , flags:Flags ) ->Result <(),AllocError > { self.reserve (1 , flags)?; +let err = self.push_within_capacity (v); +// SAFETY: The call to `reserve` was successful, so `push_within_capacity` cannot fail. +unsafe { err.unwrap_unchecked () };
I'd prefer an unsafe inner helper to this unwrap_unchecked call -- this safety comment is actually describing the semantics of a safe function which can change without necessarily triggering scrutiny of its callers.
Quoted 10 lines
rust/kernel/alloc/kvec.rs +10
-0+Ok (()) + } + +/// Appends an element to the back of the [`Vec`] instance. +/// +/// Fails if the vector does not have capacity for the new element. +/// +/// # Examples +/// +/// ```
rust/kernel/alloc/kvec.rs pub fn spare_capacity_mut(&mut self) -> &mut [MaybeUninit<T>] { · line 309
Quoted 10 lines
rust/kernel/alloc/kvec.rs +10
-0+/// let mut v = KVec::with_capacity(10, GFP_KERNEL); +/// for i in 0..10 { +/// v.push_within_capacity(i).unwrap(); +/// } +/// +/// assert!(v.push_within_capacity(11).is_err()); +/// # Ok::<(), Error>(()) +/// ``` +pub fn push_within_capacity (&mut self, v:T ) ->Result <(),T > { +if self.len () >= self.capacity () {
len() > capacity() should be impossible by the (implied until
https://lore.kernel.org/rust-for-linux/[email protected]/)
type invariant.
Quoted 10 lines
rust/kernel/alloc/kvec.rs +2
-1+return Err (v); + }// SAFETY: // - `self.len` is smaller than `self.capacity` and hence, the resulting pointer is --2.49.0.rc1.451.g8f38331e32-goog
Alice Ryhl
maintainerPATCH 4/5 rust: alloc: add Vec::drain_all
In reply to Alice RyhlThis is like the stdlib method drain, except that it's hard-coded to use the entire vector's range. Rust Binder uses it in the range allocator to take ownership of everything in a vector in a case where reusing the vector is desirable.
Implementing DrainAll in terms of slice::IterMut lets us reuse some nice optimizations in core for the case where T is a ZST.
--- rust/kernel/alloc/kvec.rs | 57 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 57 insertions(+)
rust/kernel/alloc/kvec.rs +57 -0
@@ -564,6 +564,30 @@ pub fn truncate(&mut self, len: usize) {// len, therefore we have exclusive access to [`new_len`, `old_len`) unsafe { ptr::drop_in_place (ptr) }; } + +/// Takes ownership of all items in this vector without consuming the allocation. +/// +/// # Examples +/// +/// ``` +/// let mut v = kernel::kvec![0, 1, 2, 3]?; +/// +/// for (i, j) in v.drain_all().enumerate() { +/// assert_eq!(i, j); +/// } +/// +/// assert!(v.capacity() >= 4); +/// ``` +pub fn drain_all (&mut self) ->DrainAll <'_,T > { +let len = self.len (); +// INVARIANT: The first 0 elements are valid. + self.len =0 ; +// INVARIANT: The first `len` elements of the spare capacity are valid values, and as we +// just set the length to zero, we may transfer ownership to the `DrainAll` object. +DrainAll { + elements: self.spare_capacity_mut ()[..len].iter_mut (), + } + } }impl <T :Clone ,A :Allocator >Vec <T ,A > {
@@ -1049,3 +1073,36 @@ fn into_iter(self) -> Self::IntoIter { } } } + +/// An iterator that owns all items in a vector, but does not own its allocation. +/// +/// # Invariants +/// +/// Every `&mut MaybeUninit<T>` returned by the iterator contains a valid `T` owned by this +/// `DrainAll`. +pub struct DrainAll <'vec,T > { + elements: slice::IterMut <'vec,MaybeUninit <T >>, +} + +impl <'vec,T >Iterator for DrainAll <'vec,T > { +type Item =T ; + +fn next (&mut self) ->Option <T > { +let elem = self.elements.next ()?; +// SAFETY: By the type invariants, we may take ownership of the value in this +// `MaybeUninit<T>`. +Some (unsafe { elem.assume_init_read () }) + } + +fn size_hint (&self) -> (usize ,Option <usize >) { + self.elements.size_hint () + } +} + +impl <'vec,T >Drop for DrainAll <'vec,T > { +fn drop (&mut self) { +if core::mem::needs_drop ::<T >() { +while self.next ().is_some () {} + } + } +}
Signature · 1 line
2.49.0.rc1.451.g8f38331e32-goog
Re: [PATCH 4/5] rust: alloc: add Vec::drain_all
Quoted 30 lines · Alice Ryhl
This is like the stdlib method drain, except that it's hard-coded to use the entire vector's range. Rust Binder uses it in the range allocator to take ownership of everything in a vector in a case where reusing the vector is desirable.
Implementing
DrainAllin terms ofslice::IterMutlets us reuse some nice optimizations in core for the case where T is a ZST.Signed-off-by Alice Ryhl <[email protected]>--- rust/kernel/alloc/kvec.rs | 57 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 57 insertions(+)rust/kernel/alloc/kvec.rs +8
-0@@ -564,6 +564,30 @@ pub fn truncate(&mut self, len: usize) {// len, therefore we have exclusive access to [`new_len`, `old_len`) unsafe { ptr::drop_in_place (ptr) }; } + +/// Takes ownership of all items in this vector without consuming the allocation. +/// +/// # Examples +/// +/// ``` +/// let mut v = kernel::kvec![0, 1, 2, 3]?; +///
rust/kernel/alloc/kvec.rs pub fn truncate(&mut self, len: usize) { · line 584
Quoted 10 lines
rust/kernel/alloc/kvec.rs +10
-0+/// for (i, j) in v.drain_all().enumerate() { +/// assert_eq!(i, j); +/// } +/// +/// assert!(v.capacity() >= 4); +/// ``` +pub fn drain_all (&mut self) ->DrainAll <'_,T > { +let len = self.len (); +// INVARIANT: The first 0 elements are valid. + self.len =0 ;
Could you use self.dec_len(self.len) here? Then you'd have a &mut
[T] rather than MaybeUninit. Provided you agree dec_len is sound, of course.
Alice Ryhl
maintainerRe: [PATCH 4/5] rust: alloc: add Vec::drain_all
Quoted 37 lines · Tamir Duberstein
Quoted 36 lines · Alice Ryhl
This is like the stdlib method drain, except that it's hard-coded to use the entire vector's range. Rust Binder uses it in the range allocator to take ownership of everything in a vector in a case where reusing the vector is desirable.
Implementing
DrainAllin terms ofslice::IterMutlets us reuse some nice optimizations in core for the case where T is a ZST.Signed-off-by Alice Ryhl <[email protected]>--- rust/kernel/alloc/kvec.rs | 57 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 57 insertions(+)rust/kernel/alloc/kvec.rs +14
-0@@ -564,6 +564,30 @@ pub fn truncate(&mut self, len: usize) {// len, therefore we have exclusive access to [`new_len`, `old_len`) unsafe { ptr::drop_in_place (ptr) }; } + +/// Takes ownership of all items in this vector without consuming the allocation. +/// +/// # Examples +/// +/// ``` +/// let mut v = kernel::kvec![0, 1, 2, 3]?; +/// +/// for (i, j) in v.drain_all().enumerate() { +/// assert_eq!(i, j); +/// } +/// +/// assert!(v.capacity() >= 4); +/// ```
Quoted 8 lines
rust/kernel/alloc/kvec.rs pub fn truncate(&mut self, len: usize) { · line 584
Quoted 4 lines
rust/kernel/alloc/kvec.rs +4
-0+pub fn drain_all (&mut self) ->DrainAll <'_,T > { +let len = self.len (); +// INVARIANT: The first 0 elements are valid. + self.len =0 ;Could you use
self.dec_len(self.len)here? Then you'd have a &mut
[T] rather thanMaybeUninit. Provided you agreedec_lenis sound, of course.
I think that &mut MaybeUninit<T> is better in this case. Calling assume_init_read on a &mut MaybeUninit<T> does not leave the MaybeUninit in an invalid state in the same way that calling ptr::read on an &mut T does.
Alice
Alice Ryhl
maintainerPATCH 5/5 rust: alloc: add Vec::retain
In reply to Alice RyhlThis adds a common Vec method called retain that removes all elements that don't match a certain condition. Rust Binder uses it to find all processes that match a given pid.
The stdlib retain method takes &T rather than &mut T and has a separate retain_mut for the &mut T case. However, this is considered an API mistake that can't be fixed now due to backwards compatibility. There's no reason for us to repeat that mistake.
To verify the correctness of this implementation, you may run the following program in userspace:
fn retain<T>(vec: &mut Vec<T>, f: impl Fn(&T) -> bool) {
let mut num_kept = 0;
let mut next_to_check = 0;
while let Some(to_check) = vec.get_mut(next_to_check) {
if f(to_check) {
vec.swap(num_kept, next_to_check);
num_kept += 1;
}
next_to_check += 1;
}
vec.truncate(num_kept);
}
fn verify(c: &[bool]) {
let mut vec1: Vec<usize> = (0..c.len()).collect();
let mut vec2: Vec<usize> = (0..c.len()).collect();
vec1.retain(|i| c[*i]);
retain(&mut vec2, |i| c[*i]);
assert_eq!(vec1, vec2);
}
// Used to loop through all 2^n bit vectors.
fn add(value: &mut [bool]) -> bool {
let mut carry = true;
for v in value {
let new_v = carry != *v;
carry = carry && *v;
*v = new_v;
}
carry
}
fn main() {
for len in 0..10 {
let mut retain = vec![false; len];
while !add(&mut retain) {
verify(&retain);
}
}
println!("ok!");
}--- rust/kernel/alloc/kvec.rs | 14 ++++++++++++++ 1 file changed, 14 insertions(+)
rust/kernel/alloc/kvec.rs +14 -0
@@ -588,6 +588,20 @@ pub fn drain_all(&mut self) -> DrainAll<'_, T> { elements: self.spare_capacity_mut()[..len].iter_mut(), } } + +/// Removes all elements that don't match the provided closure. +pub fn retain (&mut self,mut f:impl FnMut (&mut T ) ->bool ) { +let mut num_kept =0 ; +let mut next_to_check =0 ; +while let Some (to_check) = self.get_mut (next_to_check) { +if f (to_check) { + self.swap (num_kept, next_to_check); + num_kept +=1 ; + } + next_to_check +=1 ; + } + self.truncate (num_kept); + } }impl <T :Clone ,A :Allocator >Vec <T ,A > {
Signature · 1 line
2.49.0.rc1.451.g8f38331e32-goog
Re: [PATCH 5/5] rust: alloc: add Vec::retain
Quoted 48 lines · Alice Ryhl
This adds a common Vec method called
retainthat removes all elements that don't match a certain condition. Rust Binder uses it to find all processes that match a given pid.The stdlib retain method takes &T rather than &mut T and has a separate
retain_mutfor the &mut T case. However, this is considered an API mistake that can't be fixed now due to backwards compatibility. There's no reason for us to repeat that mistake.To verify the correctness of this implementation, you may run the following program in userspace:
fn retain<T>(vec: &mut Vec<T>, f: impl Fn(&T) -> bool) { let mut num_kept = 0; let mut next_to_check = 0; while let Some(to_check) = vec.get_mut(next_to_check) { if f(to_check) { vec.swap(num_kept, next_to_check); num_kept += 1; } next_to_check += 1; } vec.truncate(num_kept); } fn verify(c: &[bool]) { let mut vec1: Vec<usize> = (0..c.len()).collect(); let mut vec2: Vec<usize> = (0..c.len()).collect(); vec1.retain(|i| c[*i]); retain(&mut vec2, |i| c[*i]); assert_eq!(vec1, vec2); } // Used to loop through all 2^n bit vectors. fn add(value: &mut [bool]) -> bool { let mut carry = true; for v in value { let new_v = carry != *v; carry = carry && *v; *v = new_v; } carry } fn main() {
Quoted 8 lines
for len in 0..10 {
let mut retain = vec![false; len];
while !add(&mut retain) {
verify(&retain);
}
}
println!("ok!");
}Now that we have kunit in rust-next, should we make this into a test?
Alice Ryhl
maintainerRe: [PATCH 5/5] rust: alloc: add Vec::retain
Quoted 1 line · Tamir Duberstein
Now that we have kunit in rust-next, should we make this into a test?
Unfortunately, the test uses the Vec::retain from upstream alloc, which we can't call from a kunit test.
Alice
Alice Ryhl
maintainerQuoted 20 lines · Alice Ryhl
This adds various Vec methods. Some of them are needed by Rust Binder, and others are needed in other places. Each commit explains where it is needed.
I'm not sure what we concluded on the
set_len/dec_lenchanges, so I don't depend on that series for now.This series is based on top of
Vec::truncatefrom
https://lore.kernel.org/rust-for-linux/[email protected]/Signed-off-by Alice Ryhl <[email protected]>---
Alice Ryhl (5):
rust: alloc: addVec::clear
rust: alloc: addVec::pop
rust: alloc: addVec::push_within_capacity
rust: alloc: addVec::drain_all
rust: alloc: addVec::retain
Quoted 2 lines
rust/kernel/alloc/kvec.rs | 147 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 147 insertions(+)
I went ahead and sent a new version now. It's a bit quicker than I would normally do, but I wanted to get it out before I go on vacation.
Alice