rust: alloc: implement `extend` for `Vec`
Subsystems (2)
Alexandre Courbot
reviewerPATCH v2 1/1 rust: alloc: implement `extend` for `Vec`
KVec currently has extend_with and extend_from_slice methods, but no way extend a vector from a regular iterator as provided by the Extend trait.
Due to the need to provide the GFP flags, Extend cannot be implemented directly, so simply define a homonymous method that takes an extra flags argument.
The aforementioned extend_with and extend_from_slice can then be reimplemented as direct invocations of this new method - maybe they can eventually be removed.
---
I was a bit surprised to find no equivalent of the Extend trait for KVec, and while I anticipate to be told the reason for this, I also didn't hit any hard wall trying to come with my own implementation so here it is.
I expect the new extend_with and extend_from_slice to be optimized into something close to their previous implementations, but am not sure how I can simply verify that this is the case - any hint would be appreciated!
---
Changes in v2:
- Changed the diff algorithm to histogram for a more readable patch.
--- rust/kernel/alloc/kvec.rs | 89 +++++++++++++++++++++++++++++------------------ 1 file changed, 56 insertions(+), 33 deletions(-)
rust/kernel/alloc/kvec.rs +56 -33
@@ -454,30 +454,64 @@ pub fn reserve(&mut self, additional: usize, flags: Flags) -> Result<(), AllocEr } } +impl <T ,A :Allocator >Vec <T ,A > { +/// Extends the vector by the elements of `iter`. +/// +/// This uses [`Iterator::size_hint`] to optimize reallocation of memory, but will work even +/// with imprecise implementations - albeit with potentially more memory reallocations. +/// +/// In the kernel most iterators are expected to have a precise `size_hint` implementation, so +/// this should nicely optimize out in most cases. +pub fn extend <I >(&mut self, iter:I , flags:Flags ) ->Result <(),AllocError > +where +I :IntoIterator <Item =T >, + { +let mut iter = iter.into_iter (); + +loop { +let low_bound =match iter.size_hint () { +// No more items expected, we can return. + (0 ,Some (0 )) =>break , +// Possibly more items but not certain, tentatively add one. + (0 , _) =>1 , +// More items pending, reserve space for the lower bound. + (low_bound, _) => low_bound, + }; + + self.reserve (low_bound, flags)?; + +// Number of items we effectively added. +let added_items = self + .spare_capacity_mut () + .into_iter () +// Take a mutable reference to the iterator so we can reuse it in the next +// iteration of the loop if needed. + .zip (&mut iter) + .fold (0 , |count, (dst, src)| { + dst.write (src); + + count +1 + }); + +// SAFETY: +// - `self.len() + added_items <= self.capacity()` due to the call to `reserve` above, +// - items `[self.len()..self.len() + added_items - 1]` are initialized. +unsafe { self.set_len (self.len () + added_items) }; + +// `size_hint` was incorrect and our iterator ended before its advertized low bound. +if added_items < low_bound { +break ; + } + } + +Ok (()) + } +} +impl <T :Clone ,A :Allocator >Vec <T ,A > {/// Extend the vector by `n` clones of `value`. pub fn extend_with (&mut self, n:usize , value:T , flags:Flags ) ->Result <(),AllocError > { -if n ==0 { -return Ok (()); - } - - self.reserve (n, flags)?; - -let spare = self.spare_capacity_mut (); - -for itemin spare.iter_mut ().take (n -1 ) { - item.write (value.clone ()); - } - -// We can write the last element directly without cloning needlessly. - spare[n -1 ].write (value); - -// 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) }; - -Ok (()) + self.extend (core::iter::repeat (value).take (n), flags) }/// Pushes clones of the elements of slice into the [`Vec`] instance.
@@ -496,18 +530,7 @@ pub fn extend_with(&mut self, n: usize, value: T, flags: Flags) -> Result<(), Al/// # Ok::<(), Error>(()) /// ``` pub fn extend_from_slice (&mut self, other: &[T ], flags:Flags ) ->Result <(),AllocError > { - self.reserve (other.len (), flags)?; -for (slot, item)in core::iter::zip (self.spare_capacity_mut (), other) { - slot.write (item.clone ()); - } - -// SAFETY: -// - `other.len()` spare entries have just been initialized, so it is safe to increase -// 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 ()) }; -Ok (()) + self.extend (other.into_iter ().cloned (), flags) }/// Create a new `Vec<T, A>` and extend it by `n` clones of `value`.
---
base-commit: a2cc6ff5ec8f91bc463fd3b0c26b61166a07eb11
change-id: 20250405-vec_extend-4321251acc21
Best regards,
Signature · 1 line
Alexandre Courbot <[email protected]>
Hi Alexandre,
Thanks for the patch.
Quoted 54 lines · Alexandre Courbot
KVec currently has
extend_withandextend_from_slicemethods, but no way extend a vector from a regular iterator as provided by theExtendtrait.Due to the need to provide the GFP flags,
Extendcannot be implemented directly, so simply define a homonymous method that takes an extraflagsargument.The aforementioned
extend_withandextend_from_slicecan then be reimplemented as direct invocations of this new method - maybe they can eventually be removed.Signed-off-by Alexandre Courbot <[email protected]>---
I was a bit surprised to find no equivalent of theExtendtrait for KVec, and while I anticipate to be told the reason for this, I also didn't hit any hard wall trying to come with my own implementation so here it is.I expect the new
extend_withandextend_from_sliceto be optimized into something close to their previous implementations, but am not sure how I can simply verify that this is the case - any hint would be appreciated!
---
Changes in v2:
- Changed the diff algorithm to histogram for a more readable patch.--- rust/kernel/alloc/kvec.rs | 89 +++++++++++++++++++++++++++++------------------ 1 file changed, 56 insertions(+), 33 deletions(-)rust/kernel/alloc/kvec.rs +16
-0@@ -454,30 +454,64 @@ pub fn reserve(&mut self, additional: usize, flags: Flags) -> Result<(), AllocEr } } +impl <T ,A :Allocator >Vec <T ,A > { +/// Extends the vector by the elements of `iter`. +/// +/// This uses [`Iterator::size_hint`] to optimize reallocation of memory, but will work even +/// with imprecise implementations - albeit with potentially more memory reallocations. +/// +/// In the kernel most iterators are expected to have a precise `size_hint` implementation, so +/// this should nicely optimize out in most cases. +pub fn extend <I >(&mut self, iter:I , flags:Flags ) ->Result <(),AllocError > +where +I :IntoIterator <Item =T >, + { +let mut iter = iter.into_iter (); + +loop { + let low_bound = match iter.size_hint() {
rust/kernel/alloc/kvec.rs pub fn reserve(&mut self, additional: usize, flags: Flags) -> Result<(), AllocEr · line 482
Quoted 10 lines
rust/kernel/alloc/kvec.rs +10
-0+// No more items expected, we can return. + (0, Some(0)) => break, +// Possibly more items but not certain, tentatively add one. + (0, _) => 1, +// More items pending, reserve space for the lower bound. + (low_bound, _) => low_bound, + }; + + self.reserve (low_bound, flags)?; +
I want to point out this might cause a behavior change, previously extend_with() and extend_with_slice() do a "all-or-nothing" extension depending on memory allocation, i.e. if there is enough memory for all the new items, do the extension, otherwise do nothing. Your changes here make it that extension can fail in-between due to AllocError, that is, only part of the iter is added. Of course, in practice, both slice::Iter and iter::Take will just return the number of all the items as the low_bound of .size_hint(), but it's not guaranteed.
I don't see a direct correct-or-wrong answer for what behavior is desired, but if we are moving to a new behavior, we need to make sure updating the document of the extend*() function. Plus if failing in-between, should we return the iter so that users can continue do something about the iter?
Quoted 43 lines
rust/kernel/alloc/kvec.rs +28
-12+// Number of items we effectively added. +let added_items = self + .spare_capacity_mut () + .into_iter () +// Take a mutable reference to the iterator so we can reuse it in the next +// iteration of the loop if needed. + .zip (&mut iter) + .fold (0 , |count, (dst, src)| { + dst.write (src); + + count +1 + }); + +// SAFETY: +// - `self.len() + added_items <= self.capacity()` due to the call to `reserve` above, +// - items `[self.len()..self.len() + added_items - 1]` are initialized. +unsafe { self.set_len (self.len () + added_items) }; + +// `size_hint` was incorrect and our iterator ended before its advertized low bound. +if added_items < low_bound { +break ; + } + } + +Ok (()) + } +} +impl <T :Clone ,A :Allocator >Vec <T ,A > {/// Extend the vector by `n` clones of `value`. pub fn extend_with (&mut self, n:usize , value:T , flags:Flags ) ->Result <(),AllocError > { -if n ==0 { -return Ok (()); - } - - self.reserve (n, flags)?; - -let spare = self.spare_capacity_mut (); - -for itemin spare.iter_mut ().take (n -1 ) { - item.write (value.clone ()); - } -
rust/kernel/alloc/kvec.rs pub fn reserve(&mut self, additional: usize, flags: Flags) -> Result<(), AllocEr · line 514
Quoted 10 lines
rust/kernel/alloc/kvec.rs +1
-9-// We can write the last element directly without cloning needlessly. - spare[n -1 ].write (value); - -// 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) }; - -Ok (()) + self.extend (core::iter::repeat (value).take (n), flags)
Would this actually call T::clone() n times instead of n - 1 times?
Regards,
Boqun
Quoted 32 lines
rust/kernel/alloc/kvec.rs +1
-13}/// Pushes clones of the elements of slice into the [`Vec`] instance. @@ -496,18 +530,7 @@ pub fn extend_with(&mut self, n: usize, value: T, flags: Flags) -> Result<(), Al/// # Ok::<(), Error>(()) /// ``` pub fn extend_from_slice (&mut self, other: &[T ], flags:Flags ) ->Result <(),AllocError > { - self.reserve (other.len (), flags)?; -for (slot, item)in core::iter::zip (self.spare_capacity_mut (), other) { - slot.write (item.clone ()); - } - -// SAFETY: -// - `other.len()` spare entries have just been initialized, so it is safe to increase -// 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 ()) }; -Ok (()) + self.extend (other.into_iter ().cloned (), flags) }/// Create a new `Vec<T, A>` and extend it by `n` clones of `value`. ---base-commit:
a2cc6ff5ec8f91bc463fd3b0c26b61166a07eb11
change-id: 20250405-vec_extend-4321251acc21Best regards,
Signature · 1 line
Alexandre Courbot <[email protected]>
Alexandre Courbot
reviewerHi Boqun, thanks for the review!
Quoted 70 lines · Boqun Feng
Hi Alexandre,
Thanks for the patch.
Quoted 54 lines · Alexandre Courbot
KVec currently has
extend_withandextend_from_slicemethods, but no way extend a vector from a regular iterator as provided by theExtendtrait.Due to the need to provide the GFP flags,
Extendcannot be implemented directly, so simply define a homonymous method that takes an extraflagsargument.The aforementioned
extend_withandextend_from_slicecan then be reimplemented as direct invocations of this new method - maybe they can eventually be removed.Signed-off-by Alexandre Courbot <[email protected]>---
I was a bit surprised to find no equivalent of theExtendtrait for KVec, and while I anticipate to be told the reason for this, I also didn't hit any hard wall trying to come with my own implementation so here it is.I expect the new
extend_withandextend_from_sliceto be optimized into something close to their previous implementations, but am not sure how I can simply verify that this is the case - any hint would be appreciated!
---
Changes in v2:
- Changed the diff algorithm to histogram for a more readable patch.--- rust/kernel/alloc/kvec.rs | 89 +++++++++++++++++++++++++++++------------------ 1 file changed, 56 insertions(+), 33 deletions(-)rust/kernel/alloc/kvec.rs +16
-0@@ -454,30 +454,64 @@ pub fn reserve(&mut self, additional: usize, flags: Flags) -> Result<(), AllocEr } } +impl <T ,A :Allocator >Vec <T ,A > { +/// Extends the vector by the elements of `iter`. +/// +/// This uses [`Iterator::size_hint`] to optimize reallocation of memory, but will work even +/// with imprecise implementations - albeit with potentially more memory reallocations. +/// +/// In the kernel most iterators are expected to have a precise `size_hint` implementation, so +/// this should nicely optimize out in most cases. +pub fn extend <I >(&mut self, iter:I , flags:Flags ) ->Result <(),AllocError > +where +I :IntoIterator <Item =T >, + { +let mut iter = iter.into_iter (); + +loop { + let low_bound = match iter.size_hint() {rust/kernel/alloc/kvec.rs pub fn reserve(&mut self, additional: usize, flags: Flags) -> Result<(), AllocEr · line 482
Quoted 10 lines
rust/kernel/alloc/kvec.rs +10
-0+// No more items expected, we can return. + (0, Some(0)) => break, +// Possibly more items but not certain, tentatively add one. + (0, _) => 1, +// More items pending, reserve space for the lower bound. + (low_bound, _) => low_bound, + }; + + self.reserve (low_bound, flags)?; +
Quoted 8 lines
I want to point out this might cause a behavior change, previously
extend_with()andextend_with_slice()do a "all-or-nothing" extension depending on memory allocation, i.e. if there is enough memory for all the new items, do the extension, otherwise do nothing. Your changes here make it that extension can fail in-between due to AllocError, that is, only part of theiteris added. Of course, in practice, bothslice::Iteranditer::Takewill just return the number of all the items as thelow_boundof .size_hint(), but it's not guaranteed.
That's a very valid point, and one of the reasons why I would like to see how the code is actually optimized in extend_with and extend_with_slice. While the method is designed to handle imprecise/incorrect implementations of size_hint, the expectation is that outside of very unusual uses the code should be able to be optimized into a single-allocation, non-loop pass.
We could probably enforce that if we had access to TrustedLen or defined our own equivalent trait for the kernel. The set of iterators that could be passed as arguments would be more limited, but for the same reason as above I don't think that would be a big limitation.
Quoted 5 lines
I don't see a direct correct-or-wrong answer for what behavior is desired, but if we are moving to a new behavior, we need to make sure updating the document of the extend*() function. Plus if failing in-between, should we return the
iterso that users can continue do something about theiter?
I have updated the documentation with more details about the sub-optimal and error cases. I am not sure what use a caller would have from the remaining items - and after all, the currently existing methods also don't return the iterator upon failure. If we want to preserve the current behavior, we can always reduce the size of the vector to its pre-call value on the error path.
Quoted 48 lines
Quoted 48 lines
rust/kernel/alloc/kvec.rs +28
-16+// Number of items we effectively added. +let added_items = self + .spare_capacity_mut () + .into_iter () +// Take a mutable reference to the iterator so we can reuse it in the next +// iteration of the loop if needed. + .zip (&mut iter) + .fold (0 , |count, (dst, src)| { + dst.write (src); + + count +1 + }); + +// SAFETY: +// - `self.len() + added_items <= self.capacity()` due to the call to `reserve` above, +// - items `[self.len()..self.len() + added_items - 1]` are initialized. +unsafe { self.set_len (self.len () + added_items) }; + +// `size_hint` was incorrect and our iterator ended before its advertized low bound. +if added_items < low_bound { +break ; + } + } + +Ok (()) + } +} +impl <T :Clone ,A :Allocator >Vec <T ,A > {/// Extend the vector by `n` clones of `value`. pub fn extend_with (&mut self, n:usize , value:T , flags:Flags ) ->Result <(),AllocError > { -if n ==0 { -return Ok (()); - } - - self.reserve (n, flags)?; - -let spare = self.spare_capacity_mut (); - -for itemin spare.iter_mut ().take (n -1 ) { - item.write (value.clone ()); - } - -// We can write the last element directly without cloning needlessly. - spare[n -1 ].write (value); - -// SAFETY:
Quoted 8 lines
rust/kernel/alloc/kvec.rs pub fn reserve(&mut self, additional: usize, flags: Flags) -> Result<(), AllocEr · line 514
Quoted 6 lines
rust/kernel/alloc/kvec.rs +1
-5-// - `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) }; - -Ok (()) + self.extend (core::iter::repeat (value).take (n), flags)Would this actually call
T::clone()n times instead of n - 1 times?
Indeed - we probably want to use core::iter::repeat_n() here to mimic the original behavior.
Cheers,
Alex.
Alexandre Courbot
reviewerQuoted 100 lines · Alexandre Courbot
Hi Boqun, thanks for the review!
Quoted 70 lines · Boqun Feng
Hi Alexandre,
Thanks for the patch.
Quoted 54 lines · Alexandre Courbot
KVec currently has
extend_withandextend_from_slicemethods, but no way extend a vector from a regular iterator as provided by theExtendtrait.Due to the need to provide the GFP flags,
Extendcannot be implemented directly, so simply define a homonymous method that takes an extraflagsargument.The aforementioned
extend_withandextend_from_slicecan then be reimplemented as direct invocations of this new method - maybe they can eventually be removed.Signed-off-by Alexandre Courbot <[email protected]>---
I was a bit surprised to find no equivalent of theExtendtrait for KVec, and while I anticipate to be told the reason for this, I also didn't hit any hard wall trying to come with my own implementation so here it is.I expect the new
extend_withandextend_from_sliceto be optimized into something close to their previous implementations, but am not sure how I can simply verify that this is the case - any hint would be appreciated!
---
Changes in v2:
- Changed the diff algorithm to histogram for a more readable patch.--- rust/kernel/alloc/kvec.rs | 89 +++++++++++++++++++++++++++++------------------ 1 file changed, 56 insertions(+), 33 deletions(-)rust/kernel/alloc/kvec.rs +16
-0@@ -454,30 +454,64 @@ pub fn reserve(&mut self, additional: usize, flags: Flags) -> Result<(), AllocEr } } +impl <T ,A :Allocator >Vec <T ,A > { +/// Extends the vector by the elements of `iter`. +/// +/// This uses [`Iterator::size_hint`] to optimize reallocation of memory, but will work even +/// with imprecise implementations - albeit with potentially more memory reallocations. +/// +/// In the kernel most iterators are expected to have a precise `size_hint` implementation, so +/// this should nicely optimize out in most cases. +pub fn extend <I >(&mut self, iter:I , flags:Flags ) ->Result <(),AllocError > +where +I :IntoIterator <Item =T >, + { +let mut iter = iter.into_iter (); + +loop { + let low_bound = match iter.size_hint() {rust/kernel/alloc/kvec.rs pub fn reserve(&mut self, additional: usize, flags: Flags) -> Result<(), AllocEr · line 482
Quoted 10 lines
rust/kernel/alloc/kvec.rs +10
-0+// No more items expected, we can return. + (0, Some(0)) => break, +// Possibly more items but not certain, tentatively add one. + (0, _) => 1, +// More items pending, reserve space for the lower bound. + (low_bound, _) => low_bound, + }; + + self.reserve (low_bound, flags)?; +Quoted 8 lines
I want to point out this might cause a behavior change, previously
extend_with()andextend_with_slice()do a "all-or-nothing" extension depending on memory allocation, i.e. if there is enough memory for all the new items, do the extension, otherwise do nothing. Your changes here make it that extension can fail in-between due to AllocError, that is, only part of theiteris added. Of course, in practice, bothslice::Iteranditer::Takewill just return the number of all the items as thelow_boundof .size_hint(), but it's not guaranteed.That's a very valid point, and one of the reasons why I would like to see how the code is actually optimized in
extend_withandextend_with_slice. While the method is designed to handle imprecise/incorrect implementations ofsize_hint, the expectation is that outside of very unusual uses the code should be able to be optimized into a single-allocation, non-loop pass.We could probably enforce that if we had access to
TrustedLenor defined our own equivalent trait for the kernel. The set of iterators that could be passed as arguments would be more limited, but for the same reason as above I don't think that would be a big limitation.Quoted 5 lines
I don't see a direct correct-or-wrong answer for what behavior is desired, but if we are moving to a new behavior, we need to make sure updating the document of the extend*() function. Plus if failing in-between, should we return the
iterso that users can continue do something about theiter?
Quoted 6 lines
I have updated the documentation with more details about the sub-optimal and error cases. I am not sure what use a caller would have from the remaining items - and after all, the currently existing methods also don't return the iterator upon failure. If we want to preserve the current behavior, we can always reduce the size of the vector to its pre-call value on the error path.
Err of course they don't have any iterator to return so that last point is mostly moot, except maybe for extend_with which doesn't return the passed value, which the caller hasn't necessarily kept a clone of.
kernel test robot
build botkernel test robot noticed the following build warnings:
Hi Alexandre,
kernel test robot noticed the following build warnings:
[auto build test WARNING on a2cc6ff5ec8f91bc463fd3b0c26b61166a07eb11]
url: https://github.com/intel-lab-lkp/linux/commits/Alexandre-Courbot/rust-alloc-implement-extend-for-Vec/20250405-215300 base: a2cc6ff5ec8f91bc463fd3b0c26b61166a07eb11 patch link: https://lore.kernel.org/r/20250405-vec_extend-v2-1-e4a85af43cb3%40nvidia.com patch subject: [PATCH v2] rust: alloc: implement `extend` for `Vec` config: x86_64-rhel-9.4-rust (https://download.01.org/0day-ci/archive/20250406/[email protected]/config) compiler: clang version 18.1.8 (https://github.com/llvm/llvm-project 3b5b5c1ec4a3095ab096dd780e84d7ab81f3d7ff) rustc: rustc 1.78.0 (9b00956e5 2024-04-29) reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20250406/[email protected]/reproduce)
If you fix the issue in a separate patch/commit (i.e. not just a new version of the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <[email protected]>
| Closes: https://lore.kernel.org/oe-kbuild-all/[email protected]/
All warnings (new ones prefixed by >>):
>> warning: this `.into_iter()` call is equivalent to `.iter_mut()` and will not consume the `slice`
--> rust/kernel/alloc/kvec.rs:486:18
|
486 | .into_iter()
| ^^^^^^^^^ help: call directly: iter_mut
|
= help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#into_iter_on_ref
= note: -W clippy::into-iter-on-ref implied by -W clippy::all
= help: to override -W clippy::all add #[allow(clippy::into_iter_on_ref)]
--
>> warning: this `.into_iter()` call is equivalent to `.iter()` and will not consume the `slice`
--> rust/kernel/alloc/kvec.rs:533:27
|
533 | self.extend(other.into_iter().cloned(), flags)
| ^^^^^^^^^ help: call directly: iter
|
= help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#into_iter_on_ref
Signature · 2 lines
0-DAY CI Kernel Test Service https://github.com/intel/lkp-tests/wiki