CINXE.COM
LKML: Alexandre Courbot: [PATCH v3] rust: alloc: implement `extend` for `Vec`
<?xml version="1.0" encoding="UTF-8" standalone="yes"?> <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>LKML: Alexandre Courbot: [PATCH v3] rust: alloc: implement `extend` for `Vec`</title><link href="/css/message.css" rel="stylesheet" type="text/css" /><link href="/css/wrap.css" rel="alternate stylesheet" type="text/css" title="wrap" /><link href="/css/nowrap.css" rel="stylesheet" type="text/css" title="nowrap" /><link href="/favicon.ico" rel="shortcut icon" /><script src="/js/simple-calendar.js" type="text/javascript"></script><script src="/js/styleswitcher.js" type="text/javascript"></script><link rel="alternate" type="application/rss+xml" title="lkml.org : last 100 messages" href="/rss.php" /><link rel="alternate" type="application/rss+xml" title="lkml.org : last messages by Alexandre Courbot" href="/groupie.php?aid=" /><!--Matomo--><script> var _paq = window._paq = window._paq || []; /* tracker methods like "setCustomDimension" should be called before "trackPageView" */ _paq.push(["setDoNotTrack", true]); _paq.push(["disableCookies"]); _paq.push(['trackPageView']); _paq.push(['enableLinkTracking']); (function() { var u="//m.lkml.org/"; _paq.push(['setTrackerUrl', u+'matomo.php']); _paq.push(['setSiteId', '1']); var d=document, g=d.createElement('script'), s=d.getElementsByTagName('script')[0]; g.async=true; g.src=u+'matomo.js'; s.parentNode.insertBefore(g,s); })(); </script><!--End Matomo Code--></head><body onload="es.jasper.simpleCalendar.init();" itemscope="itemscope" itemtype="http://schema.org/BlogPosting"><table border="0" cellpadding="0" cellspacing="0"><tr><td width="180" align="center"><a href="/"><img style="border:0;width:135px;height:32px" src="/images/toprowlk.gif" alt="lkml.org" /></a></td><td width="32">聽</td><td class="nb"><div><a class="nb" href="/lkml"> [lkml]</a> 聽 <a class="nb" href="/lkml/2025"> [2025]</a> 聽 <a class="nb" href="/lkml/2025/4"> [Apr]</a> 聽 <a class="nb" href="/lkml/2025/4/6"> [6]</a> 聽 <a class="nb" href="/lkml/last100"> [last100]</a> 聽 <a href="/rss.php"><img src="/images/rss-or.gif" border="0" alt="RSS Feed" /></a></div><div>Views: <a href="#" class="nowrap" onclick="setActiveStyleSheet('wrap');return false;">[wrap]</a><a href="#" class="wrap" onclick="setActiveStyleSheet('nowrap');return false;">[no wrap]</a> 聽 <a class="nb" href="/lkml/mheaders/2025/4/6/137" onclick="this.href='/lkml/headers'+'/2025/4/6/137';">[headers]</a>聽 <a href="/lkml/bounce/2025/4/6/137">[forward]</a>聽 </div></td><td width="32">聽</td></tr><tr><td valign="top"><div class="es-jasper-simpleCalendar" baseurl="/lkml/"></div><div class="threadlist">Messages in this thread</div><ul class="threadlist"><li class="root"><a href="/lkml/2025/4/6/137">First message in thread</a></li><li class="origin"><a href="/lkml/2025/4/7/865">Alexandre Courbot</a><ul><li><a href="/lkml/2025/4/7/865">Danilo Krummrich</a><ul><li><a href="/lkml/2025/4/8/1223">"Alexandre Courbot"</a></li></ul></li></ul></li></ul><div class="threadlist">Patch in this message</div><ul class="threadlist"><li><a href="/lkml/diff/2025/4/6/137/1">Get diff 1</a></li></ul></td><td width="32" rowspan="2" class="c" valign="top"><img src="/images/icornerl.gif" width="32" height="32" alt="/" /></td><td class="c" rowspan="2" valign="top" style="padding-top: 1em"><table><tr><td><table><tr><td class="lp">From</td><td class="rp" itemprop="author">Alexandre Courbot <></td></tr><tr><td class="lp">Date</td><td class="rp" itemprop="datePublished">Sun, 06 Apr 2025 22:01:55 +0900</td></tr><tr><td class="lp">Subject</td><td class="rp" itemprop="name">[PATCH v3] rust: alloc: implement `extend` for `Vec`</td></tr></table></td><td></td></tr></table><pre itemprop="articleBody">KVec currently has `extend_with` and `extend_from_slice` methods, but no<br />way extend a vector from a regular iterator as provided by the `Extend`<br />trait.<br /><br />Due to the need to provide the GFP flags, `Extend` cannot be implemented<br />directly, so simply define a homonymous method that takes an extra<br />`flags` argument.<br /><br />The aforementioned `extend_with` and `extend_from_slice` can then be<br />reimplemented as direct invocations of this new method - maybe they can<br />eventually be removed.<br /><br />Signed-off-by: Alexandre Courbot <acourbot@nvidia.com><br />---<br />I was a bit surprised to find no equivalent of the `Extend` trait for<br />KVec, and while I anticipate to be told the reason for this, I also<br />didn't hit any hard wall trying to come with my own implementation so<br />here it is.<br /><br />I expect the new `extend_with` and `extend_from_slice` to be optimized<br />into something close to their previous implementations, but am not sure<br />how I can simply verify that this is the case - any hint would be<br />appreciated!<br />---<br />Changes in v3:<br />- Use repeat_n() instead of repeat() for extend_with() in order to avoid<br /> an extra clone of the value.<br />- Be more precise about the cases where extend() will perform optimally<br /> or not in its documentation, and how the vector might be modified even<br /> in case of an error.<br />- Replace into_iter() with iter() and iter_mut() where suggested by the<br /> kernel test robot.<br />- Link to v2: <a href="https://lore.kernel.org/r/20250405-vec_extend-v2-1-e4a85af43cb3@nvidia.com">https://lore.kernel.org/r/20250405-vec_extend-v2-1-e4a85af43cb3@nvidia.com</a><br /><br />Changes in v2:<br />- Changed the diff algorithm to histogram for a more readable patch.<br />---<br /> rust/kernel/alloc/kvec.rs | 111 ++++++++++++++++++++++++++++++++--------------<br /> 1 file changed, 78 insertions(+), 33 deletions(-)<br /><br />diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs<br />index ae9d072741cedbb34bed0be0c20cc75472aa53be..b3c4227e232cca3b5c17930abc63810240b9c4da 100644<br />--- a/rust/kernel/alloc/kvec.rs<br />+++ b/rust/kernel/alloc/kvec.rs<br />@@ -454,30 +454,86 @@ pub fn reserve(&mut self, additional: usize, flags: Flags) -> Result<(), AllocEr<br /> }<br /> }<br /> <br />+impl<T, A: Allocator> Vec<T, A> {<br />+ /// Extends the vector by the elements of `iter`.<br />+ ///<br />+ /// This uses [`Iterator::size_hint`] to optimize memory reallocations, but will work even with<br />+ /// imprecise implementations - albeit in a non-optimal way.<br />+ ///<br />+ /// This method returns an error if a memory reallocation required to accommodate the new items<br />+ /// failed. In this case, callers must assume that some (but not all) elements of `iter` might<br />+ /// have been added to the vector.<br />+ ///<br />+ /// # Note on optimal behavior and correctness<br />+ ///<br />+ /// The efficiency of this method depends on how reliable the [`Iterator::size_hint`]<br />+ /// implementation of the `iter` is.<br />+ ///<br />+ /// It performs optimally with at most a single memory reallocation if the lower bound of<br />+ /// `size_hint` is the exact number of items actually yielded.<br />+ ///<br />+ /// If `size_hint` is more vague, there may be as many memory reallocations as necessary to<br />+ /// cover the whole iterator from the successive lower bounds returned by `size_hint`.<br />+ ///<br />+ /// If `size_hint` signals more items than actually yielded by the iterator, some unused memory<br />+ /// might be reserved.<br />+ ///<br />+ /// Finally, whenever `size_hint` returns `(0, Some(0))`, the method assumes that no more items<br />+ /// are yielded by the iterator and returns. This may result in some items not being added if<br />+ /// there were still some remaining.<br />+ ///<br />+ /// In the kernel most iterators are expected to have a precise and correct `size_hint`<br />+ /// implementation, so this should nicely optimize out for these cases.<br />+ pub fn extend<I>(&mut self, iter: I, flags: Flags) -> Result<(), AllocError><br />+ where<br />+ I: IntoIterator<Item = T>,<br />+ {<br />+ let mut iter = iter.into_iter();<br />+<br />+ loop {<br />+ let low_bound = match iter.size_hint() {<br />+ // No more items expected, we can return.<br />+ (0, Some(0)) => break,<br />+ // Possibly more items but not certain, tentatively add one.<br />+ (0, _) => 1,<br />+ // More items pending, reserve space for the lower bound.<br />+ (low_bound, _) => low_bound,<br />+ };<br />+<br />+ self.reserve(low_bound, flags)?;<br />+<br />+ // Number of items we actually added.<br />+ let added_items = self<br />+ .spare_capacity_mut()<br />+ .iter_mut()<br />+ // Take a mutable reference to the iterator so we can reuse it in the next<br />+ // iteration of the loop if needed.<br />+ .zip(&mut iter)<br />+ .fold(0, |count, (dst, src)| {<br />+ dst.write(src);<br />+<br />+ count + 1<br />+ });<br />+<br />+ // SAFETY:<br />+ // - `self.len() + added_items <= self.capacity()` due to the call to `reserve` above,<br />+ // - items `[self.len()..self.len() + added_items - 1]` are initialized.<br />+ unsafe { self.set_len(self.len() + added_items) };<br />+<br />+ // `size_hint` was incorrect and our iterator ended before its advertized lower bound.<br />+ if added_items < low_bound {<br />+ break;<br />+ }<br />+ }<br />+<br />+ Ok(())<br />+ }<br />+}<br />+<br /> impl<T: Clone, A: Allocator> Vec<T, A> {<br /> /// Extend the vector by `n` clones of `value`.<br /> pub fn extend_with(&mut self, n: usize, value: T, flags: Flags) -> Result<(), AllocError> {<br />- if n == 0 {<br />- return Ok(());<br />- }<br />-<br />- self.reserve(n, flags)?;<br />-<br />- let spare = self.spare_capacity_mut();<br />-<br />- for item in spare.iter_mut().take(n - 1) {<br />- item.write(value.clone());<br />- }<br />-<br />- // We can write the last element directly without cloning needlessly.<br />- spare[n - 1].write(value);<br />-<br />- // SAFETY:<br />- // - `self.len() + n < self.capacity()` due to the call to reserve above,<br />- // - the loop and the line above initialized the next `n` elements.<br />- unsafe { self.set_len(self.len() + n) };<br />-<br />- Ok(())<br />+ self.extend(core::iter::repeat_n(value, n), flags)<br /> }<br /> <br /> /// Pushes clones of the elements of slice into the [`Vec`] instance.<br />@@ -496,18 +552,7 @@ pub fn extend_with(&mut self, n: usize, value: T, flags: Flags) -> Result<(), Al<br /> /// # Ok::<(), Error>(())<br /> /// ```<br /> pub fn extend_from_slice(&mut self, other: &[T], flags: Flags) -> Result<(), AllocError> {<br />- self.reserve(other.len(), flags)?;<br />- for (slot, item) in core::iter::zip(self.spare_capacity_mut(), other) {<br />- slot.write(item.clone());<br />- }<br />-<br />- // SAFETY:<br />- // - `other.len()` spare entries have just been initialized, so it is safe to increase<br />- // the length by the same number.<br />- // - `self.len() + other.len() <= self.capacity()` is guaranteed by the preceding `reserve`<br />- // call.<br />- unsafe { self.set_len(self.len() + other.len()) };<br />- Ok(())<br />+ self.extend(other.iter().cloned(), flags)<br /> }<br /> <br /> /// Create a new `Vec<T, A>` and extend it by `n` clones of `value`.<br />---<br />base-commit: a2cc6ff5ec8f91bc463fd3b0c26b61166a07eb11<br />change-id: 20250405-vec_extend-4321251acc21<br />Best regards,<br />-- <br />Alexandre Courbot <acourbot@nvidia.com><br /><br /><br /></pre></td><td width="32" rowspan="2" class="c" valign="top"><img src="/images/icornerr.gif" width="32" height="32" alt="\" /></td></tr><tr><td align="right" valign="bottom"> 聽 </td></tr><tr><td align="right" valign="bottom">聽</td><td class="c" valign="bottom" style="padding-bottom: 0px"><img src="/images/bcornerl.gif" width="32" height="32" alt="\" /></td><td class="c">聽</td><td class="c" valign="bottom" style="padding-bottom: 0px"><img src="/images/bcornerr.gif" width="32" height="32" alt="/" /></td></tr><tr><td align="right" valign="top" colspan="2"> 聽 </td><td class="lm">Last update: 2025-04-06 15:03 聽聽 [W:0.067 / U:0.190 seconds]<br />漏2003-2020 <a href="http://blog.jasper.es/"><span itemprop="editor">Jasper Spaans</span></a>|hosted at <a href="https://www.digitalocean.com/?refcode=9a8e99d24cf9">Digital Ocean</a> and my Meterkast|<a href="http://blog.jasper.es/categories.html#lkml-ref">Read the blog</a></td><td>聽</td></tr></table><script language="javascript" src="/js/styleswitcher.js" type="text/javascript"></script></body></html>