[PATCH v7 15/26] rust: alloc: implement `collect` for `IntoIter`

Danilo Krummrich
2024-09-11T22:56:20Z

Currently, we can't implement `FromIterator`. There are a couple of
issues with this trait in the kernel, namely:

- Rust's specialization feature is unstable. This prevents us to
optimze for the special case where `I::IntoIter` equals `Vec`'s
`IntoIter` type.
- We also can't use `I::IntoIter`'s type ID either to work around this,
since `FromIterator` doesn't require this type to be `'static`.
- `FromIterator::from_iter` does return `Self` instead of
`Result<Self, AllocError>`, hence we can't properly handle allocation
failures.
- Neither `Iterator::collect` nor `FromIterator::from_iter` can handle
additional allocation flags.

Instead, provide `IntoIter::collect`, such that we can at least convert
`IntoIter` into a `Vec` again.

Reviewed-by: Alice Ryhl <aliceryhl@google.com>
Signed-off-by: Danilo Krummrich <dakr@kernel.org>
---
rust/kernel/alloc/kvec.rs | 86 +++++++++++++++++++++++++++++++++++++++
1 file changed, 86 insertions(+)

diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
index e91761c5c52d..686e969463f8 100644
--- a/rust/kernel/alloc/kvec.rs
+++ b/rust/kernel/alloc/kvec.rs
@@ -690,6 +690,92 @@ impl<T, A> IntoIter<T, A>
fn as_raw_mut_slice(&mut self) -> *mut [T] {
ptr::slice_from_raw_parts_mut(self.ptr, self.len)
}
+
+ fn into_raw_parts(self) -> (*mut T, NonNull<T>, usize, usize) {
+ let me = ManuallyDrop::new(self);
+ let ptr = me.ptr;
+ let buf = me.buf;
+ let len = me.len;
+ let cap = me.cap;
+ (ptr, buf, len, cap)
+ }
+
+ /// Same as `Iterator::collect` but specialized for `Vec`'s `IntoIter`.
+ ///
+ /// # Examples
+ ///
+ /// ```
+ /// let v = kernel::kvec![1, 2, 3]?;
+ /// let mut it = v.into_iter();
+ ///
+ /// assert_eq!(it.next(), Some(1));
+ ///
+ /// let v = it.collect(GFP_KERNEL);
+ /// assert_eq!(v, [2, 3]);
+ ///
+ /// # Ok::<(), Error>(())
+ /// ```
+ /// # Implementation Details
+ ///
+ /// Currently, we can't implement `FromIterator`. There are a couple of issues with this trait
+ /// in the kernel, namely:
+ ///
+ /// - Rust's specialization feature is unstable. This prevents us to optimze for the special
+ /// case where `I::IntoIter` equals `Vec`'s `IntoIter` type.
+ /// - We also can't use `I::IntoIter`'s type ID either to work around this, since `FromIterator`
+ /// doesn't require this type to be `'static`.
+ /// - `FromIterator::from_iter` does return `Self` instead of `Result<Self, AllocError>`, hence
+ /// we can't properly handle allocation failures.
+ /// - Neither `Iterator::collect` nor `FromIterator::from_iter` can handle additional allocation
+ /// flags.
+ ///
+ /// Instead, provide `IntoIter::collect`, such that we can at least convert a `IntoIter` into a
+ /// `Vec` again.
+ ///
+ /// Note that `IntoIter::collect` doesn't require `Flags`, since it re-uses the existing backing
+ /// buffer. However, this backing buffer may be shrunk to the actual count of elements.
+ pub fn collect(self, flags: Flags) -> Vec<T, A> {
+ let (mut ptr, buf, len, mut cap) = self.into_raw_parts();
+ let has_advanced = ptr != buf.as_ptr();
+
+ if has_advanced {
+ // Copy the contents we have advanced to at the beginning of the buffer.
+ //
+ // SAFETY:
+ // - `ptr` is valid for reads of `len * size_of::<T>()` bytes,
+ // - `buf.as_ptr()` is valid for writes of `len * size_of::<T>()` bytes,
+ // - `ptr` and `buf.as_ptr()` are not be subject to aliasing restrictions relative to
+ // each other,
+ // - both `ptr` and `buf.ptr()` are properly aligned.
+ unsafe { ptr::copy(ptr, buf.as_ptr(), len) };
+ ptr = buf.as_ptr();
+ }
+
+ // This can never fail, `len` is guaranteed to be smaller than `cap`.
+ let layout = core::alloc::Layout::array::<T>(len).unwrap();
+
+ // 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.
+ ptr = match unsafe { A::realloc(Some(buf.cast()), layout, flags) } {
+ // If we fail to shrink, which likely can't even happen, continue with the existing
+ // buffer.
+ Err(_) => ptr,
+ Ok(ptr) => {
+ cap = len;
+ ptr.as_ptr().cast()
+ }
+ };
+
+ // SAFETY: If the iterator has been advanced, the advanced elements have been copied to
+ // the beginning of the buffer and `len` has been adjusted accordingly.
+ //
+ // - `ptr` is guaranteed to point to the start of the backing buffer.
+ // - `cap` is either the original capacity or, after shrinking the buffer, equal to `len`.
+ // - `alloc` is guaranteed to be unchanged since `into_iter` has been called on the original
+ // `Vec`.
+ unsafe { Vec::from_raw_parts(ptr, len, cap) }
+ }
}

impl<T, A> Iterator for IntoIter<T, A>
--
2.46.0