diff mbox series

[v2,16/23] rust: alloc: implement `collect` for `IntoIter`

Message ID 20240723181024.21168-17-dakr@kernel.org (mailing list archive)
State New
Headers show
Series Generic `Allocator` support for Rust | expand

Commit Message

Danilo Krummrich July 23, 2024, 6:10 p.m. UTC
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.

Signed-off-by: Danilo Krummrich <dakr@kernel.org>
---
 rust/kernel/alloc/kvec.rs | 80 ++++++++++++++++++++++++++++++++++++++-
 1 file changed, 79 insertions(+), 1 deletion(-)

Comments

Heghedus Razvan July 24, 2024, 2:35 p.m. UTC | #1
On Tue Jul 23, 2024 at 9:10 PM EEST, Danilo Krummrich wrote:
> 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.
Well that's a shame, so I guess collecting a Filter or Map is not possible.

>
> Instead, provide `IntoIter::collect`, such that we can at least convert
> `IntoIter` into a `Vec` again.
>
> Signed-off-by: Danilo Krummrich <dakr@kernel.org>
> ---
>  rust/kernel/alloc/kvec.rs | 80 ++++++++++++++++++++++++++++++++++++++-
>  1 file changed, 79 insertions(+), 1 deletion(-)
>
> diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
> index fbfb755b252d..5c317931e14c 100644
> --- a/rust/kernel/alloc/kvec.rs
> +++ b/rust/kernel/alloc/kvec.rs
> @@ -2,7 +2,7 @@
>
>  //! Implementation of [`Vec`].
>
> -use super::{AllocError, Allocator, Flags};
> +use super::{flags::*, AllocError, Allocator, Flags};
>  use crate::types::Unique;
>  use core::{
>      fmt,
> @@ -633,6 +633,84 @@ 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`.
> +    ///
> +    /// 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.
> +    ///
> +    /// # Examples
> +    ///
> +    /// ```
> +    /// let v = kernel::kvec![1, 2, 3]?;
> +    /// let mut it = v.into_iter();
> +    ///
> +    /// assert_eq!(it.next(), Some(1));
> +    ///
> +    /// let v = it.collect();
> +    /// assert_eq!(v, [2, 3]);
> +    ///
> +    /// # Ok::<(), Error>(())
> +    /// ```
> +    pub fn collect(self) -> Vec<T, A> {
> +        let (mut ptr, buf, len, mut cap) = self.into_raw_parts();
> +        let has_advanced = ptr != buf.as_ptr();
> +
> +        if has_advanced {
> +            // SAFETY: Copy the contents we have advanced to at the beginning of the buffer.
> +            // `ptr` is guaranteed to be between `buf` and `buf.add(cap)` and `ptr.add(len)` is
> +            // guaranteed to be smaller than `buf.add(cap)`.
> +            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, GFP_KERNEL) } {
Here you use `GFP_KERNEL` flag directly. Shouldn't this be an argument of `collect` function? 

> +            // 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.45.2
Danilo Krummrich July 24, 2024, 8:32 p.m. UTC | #2
On Wed, Jul 24, 2024 at 02:35:46PM +0000, Heghedus Razvan wrote:
> On Tue Jul 23, 2024 at 9:10 PM EEST, Danilo Krummrich wrote:
> > 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.
> Well that's a shame, so I guess collecting a Filter or Map is not possible.

Not with the Rust's `FromIterator` trait, unfortunately. However, once we have
other collectable data structures in place, we can come up with a kernel
compatible version of the `FromIterator` trait and implement against it.

> 
> >
> > Instead, provide `IntoIter::collect`, such that we can at least convert
> > `IntoIter` into a `Vec` again.
> >
> > Signed-off-by: Danilo Krummrich <dakr@kernel.org>
> > ---
> >  rust/kernel/alloc/kvec.rs | 80 ++++++++++++++++++++++++++++++++++++++-
> >  1 file changed, 79 insertions(+), 1 deletion(-)
> >
> > diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
> > index fbfb755b252d..5c317931e14c 100644
> > --- a/rust/kernel/alloc/kvec.rs
> > +++ b/rust/kernel/alloc/kvec.rs
> > @@ -2,7 +2,7 @@
> >
> >  //! Implementation of [`Vec`].
> >
> > -use super::{AllocError, Allocator, Flags};
> > +use super::{flags::*, AllocError, Allocator, Flags};
> >  use crate::types::Unique;
> >  use core::{
> >      fmt,
> > @@ -633,6 +633,84 @@ 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`.
> > +    ///
> > +    /// 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.
> > +    ///
> > +    /// # Examples
> > +    ///
> > +    /// ```
> > +    /// let v = kernel::kvec![1, 2, 3]?;
> > +    /// let mut it = v.into_iter();
> > +    ///
> > +    /// assert_eq!(it.next(), Some(1));
> > +    ///
> > +    /// let v = it.collect();
> > +    /// assert_eq!(v, [2, 3]);
> > +    ///
> > +    /// # Ok::<(), Error>(())
> > +    /// ```
> > +    pub fn collect(self) -> Vec<T, A> {
> > +        let (mut ptr, buf, len, mut cap) = self.into_raw_parts();
> > +        let has_advanced = ptr != buf.as_ptr();
> > +
> > +        if has_advanced {
> > +            // SAFETY: Copy the contents we have advanced to at the beginning of the buffer.
> > +            // `ptr` is guaranteed to be between `buf` and `buf.add(cap)` and `ptr.add(len)` is
> > +            // guaranteed to be smaller than `buf.add(cap)`.
> > +            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, GFP_KERNEL) } {
> Here you use `GFP_KERNEL` flag directly. Shouldn't this be an argument of `collect` function? 

Even though we only ever ask the allocator to shrink the buffer (or keep it as
it is), it should be, good catch!

> 
> > +            // 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.45.2
> 
>
diff mbox series

Patch

diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
index fbfb755b252d..5c317931e14c 100644
--- a/rust/kernel/alloc/kvec.rs
+++ b/rust/kernel/alloc/kvec.rs
@@ -2,7 +2,7 @@ 
 
 //! Implementation of [`Vec`].
 
-use super::{AllocError, Allocator, Flags};
+use super::{flags::*, AllocError, Allocator, Flags};
 use crate::types::Unique;
 use core::{
     fmt,
@@ -633,6 +633,84 @@  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`.
+    ///
+    /// 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.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// let v = kernel::kvec![1, 2, 3]?;
+    /// let mut it = v.into_iter();
+    ///
+    /// assert_eq!(it.next(), Some(1));
+    ///
+    /// let v = it.collect();
+    /// assert_eq!(v, [2, 3]);
+    ///
+    /// # Ok::<(), Error>(())
+    /// ```
+    pub fn collect(self) -> Vec<T, A> {
+        let (mut ptr, buf, len, mut cap) = self.into_raw_parts();
+        let has_advanced = ptr != buf.as_ptr();
+
+        if has_advanced {
+            // SAFETY: Copy the contents we have advanced to at the beginning of the buffer.
+            // `ptr` is guaranteed to be between `buf` and `buf.add(cap)` and `ptr.add(len)` is
+            // guaranteed to be smaller than `buf.add(cap)`.
+            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, GFP_KERNEL) } {
+            // 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>