| Message ID | 20240801000641.1882-17-dakr@kernel.org (mailing list archive) |
|---|---|
| State | New |
| Headers | show |
| Series | Generic `Allocator` support for Rust | expand |
On Thu, Aug 1, 2024 at 2:08 AM Danilo Krummrich <dakr@kernel.org> wrote: > > Implement `IntoIterator` for `Vec`, `Vec`'s `IntoIter` type, as well as > `Iterator` for `IntoIter`. > > `Vec::into_iter` disassembles the `Vec` into its raw parts; additionally, > `IntoIter` keeps track of a separate pointer, which is incremented > correspondingsly as the iterator advances, while the length, or the count > of elements, is decremented. > > This also means that `IntoIter` takes the ownership of the backing > buffer and is responsible to drop the remaining elements and free the > backing buffer, if it's dropped. > > Signed-off-by: Danilo Krummrich <dakr@kernel.org> > --- > rust/kernel/alloc.rs | 1 + > rust/kernel/alloc/kvec.rs | 186 ++++++++++++++++++++++++++++++++++++++ > 2 files changed, 187 insertions(+) > > diff --git a/rust/kernel/alloc.rs b/rust/kernel/alloc.rs > index bd93140f3094..f2998ad57456 100644 > --- a/rust/kernel/alloc.rs > +++ b/rust/kernel/alloc.rs > @@ -19,6 +19,7 @@ > pub use self::kbox::KVBox; > pub use self::kbox::VBox; > > +pub use self::kvec::IntoIter; > pub use self::kvec::KVVec; > pub use self::kvec::KVec; > pub use self::kvec::VVec; > diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs > index 04cc85f7d92c..50e7705e5686 100644 > --- a/rust/kernel/alloc/kvec.rs > +++ b/rust/kernel/alloc/kvec.rs > @@ -12,6 +12,8 @@ > ops::DerefMut, > ops::Index, > ops::IndexMut, > + ptr, > + ptr::NonNull, > slice, > slice::SliceIndex, > }; > @@ -581,3 +583,187 @@ fn eq(&self, other: &$rhs) -> bool { self[..] == other[..] } > __impl_slice_eq! { [A: Allocator] [T], Vec<U, A> } > __impl_slice_eq! { [A: Allocator, const N: usize] Vec<T, A>, [U; N] } > __impl_slice_eq! { [A: Allocator, const N: usize] Vec<T, A>, &[U; N] } > + > +impl<'a, T, A> IntoIterator for &'a Vec<T, A> > +where > + A: Allocator, > +{ > + type Item = &'a T; > + type IntoIter = slice::Iter<'a, T>; > + > + fn into_iter(self) -> Self::IntoIter { > + self.iter() > + } > +} > + > +impl<'a, T, A: Allocator> IntoIterator for &'a mut Vec<T, A> > +where > + A: Allocator, > +{ > + type Item = &'a mut T; > + type IntoIter = slice::IterMut<'a, T>; > + > + fn into_iter(self) -> Self::IntoIter { > + self.iter_mut() > + } > +} > + > +/// An iterator that moves out of a vector. > +/// > +/// This `struct` is created by the `into_iter` method on [`Vec`] (provided by the [`IntoIterator`] > +/// trait). > +/// > +/// # Examples > +/// > +/// ``` > +/// let v = kernel::kvec![0, 1, 2]?; > +/// let iter = v.into_iter(); > +/// > +/// # Ok::<(), Error>(()) > +/// ``` > +pub struct IntoIter<T, A: Allocator> { > + ptr: *mut T, > + buf: NonNull<T>, > + len: usize, > + cap: usize, > + _p: PhantomData<A>, > +} > + > +impl<T, A> IntoIter<T, A> > +where > + A: Allocator, > +{ > + fn as_raw_mut_slice(&mut self) -> *mut [T] { > + ptr::slice_from_raw_parts_mut(self.ptr, self.len) > + } > +} > + > +impl<T, A> Iterator for IntoIter<T, A> > +where > + A: Allocator, > +{ > + type Item = T; > + > + /// # Examples > + /// > + /// ``` > + /// let v = kernel::kvec![1, 2, 3]?; > + /// let mut it = v.into_iter(); > + /// > + /// assert_eq!(it.next(), Some(1)); > + /// assert_eq!(it.next(), Some(2)); > + /// assert_eq!(it.next(), Some(3)); > + /// assert_eq!(it.next(), None); > + /// > + /// # Ok::<(), Error>(()) > + /// ``` > + fn next(&mut self) -> Option<T> { > + if self.len == 0 { > + return None; > + } > + > + let ptr = self.ptr; > + if !Vec::<T, A>::is_zst() { > + // SAFETY: We can't overflow; `end` is guaranteed to mark the end of the buffer. > + unsafe { self.ptr = self.ptr.add(1) }; > + } else { > + // For ZST `ptr` has to stay where it is to remain aligned, so we just reduce `self.len` > + // by 1. > + } > + self.len -= 1; > + > + // SAFETY: `ptr` is guaranteed to point at a valid element within the buffer. > + Some(unsafe { ptr.read() }) > + } > + > + /// # Examples > + /// > + /// ``` > + /// let v: KVec<u32> = kernel::kvec![1, 2, 3]?; > + /// let mut iter = v.into_iter(); > + /// let size = iter.size_hint().0; > + /// > + /// iter.next(); > + /// assert_eq!(iter.size_hint().0, size - 1); > + /// > + /// iter.next(); > + /// assert_eq!(iter.size_hint().0, size - 2); > + /// > + /// iter.next(); > + /// assert_eq!(iter.size_hint().0, size - 3); > + /// > + /// # Ok::<(), Error>(()) > + /// ``` > + fn size_hint(&self) -> (usize, Option<usize>) { > + (self.len, Some(self.len)) > + } > +} > + > +impl<T, A> Drop for IntoIter<T, A> > +where > + A: Allocator, > +{ > + fn drop(&mut self) { > + // SAFETY: Drop the remaining vector's elements in place, before we free the backing > + // memory. > + unsafe { ptr::drop_in_place(self.as_raw_mut_slice()) }; > + > + // If `cap == 0` we never allocated any memory in the first place. > + if self.cap != 0 { > + // SAFETY: `self.buf` was previously allocated with `A`. > + unsafe { A::free(self.buf.cast()) }; > + } Is this ok for ZST? > + } > +} > + > +impl<T, A> IntoIterator for Vec<T, A> > +where > + A: Allocator, > +{ > + type Item = T; > + type IntoIter = IntoIter<T, A>; > + > + /// Creates a consuming iterator, that is, one that moves each value out of > + /// the vector (from start to end). The vector cannot be used after calling > + /// this. > + /// > + /// # Examples > + /// > + /// ``` > + /// let v = kernel::kvec![1, 2]?; > + /// let mut v_iter = v.into_iter(); > + /// > + /// let first_element: Option<u32> = v_iter.next(); > + /// > + /// assert_eq!(first_element, Some(1)); > + /// assert_eq!(v_iter.next(), Some(2)); > + /// assert_eq!(v_iter.next(), None); > + /// > + /// # Ok::<(), Error>(()) > + /// ``` > + /// > + /// ``` > + /// let v = kernel::kvec![]; > + /// let mut v_iter = v.into_iter(); > + /// > + /// let first_element: Option<u32> = v_iter.next(); > + /// > + /// assert_eq!(first_element, None); > + /// > + /// # Ok::<(), Error>(()) > + /// ``` > + #[inline] > + fn into_iter(self) -> Self::IntoIter { > + let (ptr, len, cap) = self.into_raw_parts(); > + > + IntoIter { > + ptr, > + // SAFETY: `ptr` is either a dangling pointer or a pointer to a valid memory > + // allocation, allocated with `A`. > + buf: unsafe { NonNull::new_unchecked(ptr) }, > + len, > + cap, > + _p: PhantomData::<A>, > + } > + } > +} > -- > 2.45.2 >
On Thu, Aug 01, 2024 at 05:07:48PM +0200, Alice Ryhl wrote: > On Thu, Aug 1, 2024 at 2:08 AM Danilo Krummrich <dakr@kernel.org> wrote: > > > > Implement `IntoIterator` for `Vec`, `Vec`'s `IntoIter` type, as well as > > `Iterator` for `IntoIter`. > > > > `Vec::into_iter` disassembles the `Vec` into its raw parts; additionally, > > `IntoIter` keeps track of a separate pointer, which is incremented > > correspondingsly as the iterator advances, while the length, or the count > > of elements, is decremented. > > > > This also means that `IntoIter` takes the ownership of the backing > > buffer and is responsible to drop the remaining elements and free the > > backing buffer, if it's dropped. > > > > Signed-off-by: Danilo Krummrich <dakr@kernel.org> > > --- > > rust/kernel/alloc.rs | 1 + > > rust/kernel/alloc/kvec.rs | 186 ++++++++++++++++++++++++++++++++++++++ > > 2 files changed, 187 insertions(+) > > > > diff --git a/rust/kernel/alloc.rs b/rust/kernel/alloc.rs > > index bd93140f3094..f2998ad57456 100644 > > --- a/rust/kernel/alloc.rs > > +++ b/rust/kernel/alloc.rs > > @@ -19,6 +19,7 @@ > > pub use self::kbox::KVBox; > > pub use self::kbox::VBox; > > > > +pub use self::kvec::IntoIter; > > pub use self::kvec::KVVec; > > pub use self::kvec::KVec; > > pub use self::kvec::VVec; > > diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs > > index 04cc85f7d92c..50e7705e5686 100644 > > --- a/rust/kernel/alloc/kvec.rs > > +++ b/rust/kernel/alloc/kvec.rs > > @@ -12,6 +12,8 @@ > > ops::DerefMut, > > ops::Index, > > ops::IndexMut, > > + ptr, > > + ptr::NonNull, > > slice, > > slice::SliceIndex, > > }; > > @@ -581,3 +583,187 @@ fn eq(&self, other: &$rhs) -> bool { self[..] == other[..] } > > __impl_slice_eq! { [A: Allocator] [T], Vec<U, A> } > > __impl_slice_eq! { [A: Allocator, const N: usize] Vec<T, A>, [U; N] } > > __impl_slice_eq! { [A: Allocator, const N: usize] Vec<T, A>, &[U; N] } > > + > > +impl<'a, T, A> IntoIterator for &'a Vec<T, A> > > +where > > + A: Allocator, > > +{ > > + type Item = &'a T; > > + type IntoIter = slice::Iter<'a, T>; > > + > > + fn into_iter(self) -> Self::IntoIter { > > + self.iter() > > + } > > +} > > + > > +impl<'a, T, A: Allocator> IntoIterator for &'a mut Vec<T, A> > > +where > > + A: Allocator, > > +{ > > + type Item = &'a mut T; > > + type IntoIter = slice::IterMut<'a, T>; > > + > > + fn into_iter(self) -> Self::IntoIter { > > + self.iter_mut() > > + } > > +} > > + > > +/// An iterator that moves out of a vector. > > +/// > > +/// This `struct` is created by the `into_iter` method on [`Vec`] (provided by the [`IntoIterator`] > > +/// trait). > > +/// > > +/// # Examples > > +/// > > +/// ``` > > +/// let v = kernel::kvec![0, 1, 2]?; > > +/// let iter = v.into_iter(); > > +/// > > +/// # Ok::<(), Error>(()) > > +/// ``` > > +pub struct IntoIter<T, A: Allocator> { > > + ptr: *mut T, > > + buf: NonNull<T>, > > + len: usize, > > + cap: usize, > > + _p: PhantomData<A>, > > +} > > + > > +impl<T, A> IntoIter<T, A> > > +where > > + A: Allocator, > > +{ > > + fn as_raw_mut_slice(&mut self) -> *mut [T] { > > + ptr::slice_from_raw_parts_mut(self.ptr, self.len) > > + } > > +} > > + > > +impl<T, A> Iterator for IntoIter<T, A> > > +where > > + A: Allocator, > > +{ > > + type Item = T; > > + > > + /// # Examples > > + /// > > + /// ``` > > + /// let v = kernel::kvec![1, 2, 3]?; > > + /// let mut it = v.into_iter(); > > + /// > > + /// assert_eq!(it.next(), Some(1)); > > + /// assert_eq!(it.next(), Some(2)); > > + /// assert_eq!(it.next(), Some(3)); > > + /// assert_eq!(it.next(), None); > > + /// > > + /// # Ok::<(), Error>(()) > > + /// ``` > > + fn next(&mut self) -> Option<T> { > > + if self.len == 0 { > > + return None; > > + } > > + > > + let ptr = self.ptr; > > + if !Vec::<T, A>::is_zst() { > > + // SAFETY: We can't overflow; `end` is guaranteed to mark the end of the buffer. > > + unsafe { self.ptr = self.ptr.add(1) }; > > + } else { > > + // For ZST `ptr` has to stay where it is to remain aligned, so we just reduce `self.len` > > + // by 1. > > + } > > + self.len -= 1; > > + > > + // SAFETY: `ptr` is guaranteed to point at a valid element within the buffer. > > + Some(unsafe { ptr.read() }) > > + } > > + > > + /// # Examples > > + /// > > + /// ``` > > + /// let v: KVec<u32> = kernel::kvec![1, 2, 3]?; > > + /// let mut iter = v.into_iter(); > > + /// let size = iter.size_hint().0; > > + /// > > + /// iter.next(); > > + /// assert_eq!(iter.size_hint().0, size - 1); > > + /// > > + /// iter.next(); > > + /// assert_eq!(iter.size_hint().0, size - 2); > > + /// > > + /// iter.next(); > > + /// assert_eq!(iter.size_hint().0, size - 3); > > + /// > > + /// # Ok::<(), Error>(()) > > + /// ``` > > + fn size_hint(&self) -> (usize, Option<usize>) { > > + (self.len, Some(self.len)) > > + } > > +} > > + > > +impl<T, A> Drop for IntoIter<T, A> > > +where > > + A: Allocator, > > +{ > > + fn drop(&mut self) { > > + // SAFETY: Drop the remaining vector's elements in place, before we free the backing > > + // memory. > > + unsafe { ptr::drop_in_place(self.as_raw_mut_slice()) }; > > + > > + // If `cap == 0` we never allocated any memory in the first place. > > + if self.cap != 0 { > > + // SAFETY: `self.buf` was previously allocated with `A`. > > + unsafe { A::free(self.buf.cast()) }; > > + } > > Is this ok for ZST? Yes, for ZST `self.cap` is always zero. > > > + } > > +} > > + > > +impl<T, A> IntoIterator for Vec<T, A> > > +where > > + A: Allocator, > > +{ > > + type Item = T; > > + type IntoIter = IntoIter<T, A>; > > + > > + /// Creates a consuming iterator, that is, one that moves each value out of > > + /// the vector (from start to end). The vector cannot be used after calling > > + /// this. > > + /// > > + /// # Examples > > + /// > > + /// ``` > > + /// let v = kernel::kvec![1, 2]?; > > + /// let mut v_iter = v.into_iter(); > > + /// > > + /// let first_element: Option<u32> = v_iter.next(); > > + /// > > + /// assert_eq!(first_element, Some(1)); > > + /// assert_eq!(v_iter.next(), Some(2)); > > + /// assert_eq!(v_iter.next(), None); > > + /// > > + /// # Ok::<(), Error>(()) > > + /// ``` > > + /// > > + /// ``` > > + /// let v = kernel::kvec![]; > > + /// let mut v_iter = v.into_iter(); > > + /// > > + /// let first_element: Option<u32> = v_iter.next(); > > + /// > > + /// assert_eq!(first_element, None); > > + /// > > + /// # Ok::<(), Error>(()) > > + /// ``` > > + #[inline] > > + fn into_iter(self) -> Self::IntoIter { > > + let (ptr, len, cap) = self.into_raw_parts(); > > + > > + IntoIter { > > + ptr, > > + // SAFETY: `ptr` is either a dangling pointer or a pointer to a valid memory > > + // allocation, allocated with `A`. > > + buf: unsafe { NonNull::new_unchecked(ptr) }, > > + len, > > + cap, > > + _p: PhantomData::<A>, > > + } > > + } > > +} > > -- > > 2.45.2 > > >
diff --git a/rust/kernel/alloc.rs b/rust/kernel/alloc.rs index bd93140f3094..f2998ad57456 100644 --- a/rust/kernel/alloc.rs +++ b/rust/kernel/alloc.rs @@ -19,6 +19,7 @@ pub use self::kbox::KVBox; pub use self::kbox::VBox; +pub use self::kvec::IntoIter; pub use self::kvec::KVVec; pub use self::kvec::KVec; pub use self::kvec::VVec; diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs index 04cc85f7d92c..50e7705e5686 100644 --- a/rust/kernel/alloc/kvec.rs +++ b/rust/kernel/alloc/kvec.rs @@ -12,6 +12,8 @@ ops::DerefMut, ops::Index, ops::IndexMut, + ptr, + ptr::NonNull, slice, slice::SliceIndex, }; @@ -581,3 +583,187 @@ fn eq(&self, other: &$rhs) -> bool { self[..] == other[..] } __impl_slice_eq! { [A: Allocator] [T], Vec<U, A> } __impl_slice_eq! { [A: Allocator, const N: usize] Vec<T, A>, [U; N] } __impl_slice_eq! { [A: Allocator, const N: usize] Vec<T, A>, &[U; N] } + +impl<'a, T, A> IntoIterator for &'a Vec<T, A> +where + A: Allocator, +{ + type Item = &'a T; + type IntoIter = slice::Iter<'a, T>; + + fn into_iter(self) -> Self::IntoIter { + self.iter() + } +} + +impl<'a, T, A: Allocator> IntoIterator for &'a mut Vec<T, A> +where + A: Allocator, +{ + type Item = &'a mut T; + type IntoIter = slice::IterMut<'a, T>; + + fn into_iter(self) -> Self::IntoIter { + self.iter_mut() + } +} + +/// An iterator that moves out of a vector. +/// +/// This `struct` is created by the `into_iter` method on [`Vec`] (provided by the [`IntoIterator`] +/// trait). +/// +/// # Examples +/// +/// ``` +/// let v = kernel::kvec![0, 1, 2]?; +/// let iter = v.into_iter(); +/// +/// # Ok::<(), Error>(()) +/// ``` +pub struct IntoIter<T, A: Allocator> { + ptr: *mut T, + buf: NonNull<T>, + len: usize, + cap: usize, + _p: PhantomData<A>, +} + +impl<T, A> IntoIter<T, A> +where + A: Allocator, +{ + fn as_raw_mut_slice(&mut self) -> *mut [T] { + ptr::slice_from_raw_parts_mut(self.ptr, self.len) + } +} + +impl<T, A> Iterator for IntoIter<T, A> +where + A: Allocator, +{ + type Item = T; + + /// # Examples + /// + /// ``` + /// let v = kernel::kvec![1, 2, 3]?; + /// let mut it = v.into_iter(); + /// + /// assert_eq!(it.next(), Some(1)); + /// assert_eq!(it.next(), Some(2)); + /// assert_eq!(it.next(), Some(3)); + /// assert_eq!(it.next(), None); + /// + /// # Ok::<(), Error>(()) + /// ``` + fn next(&mut self) -> Option<T> { + if self.len == 0 { + return None; + } + + let ptr = self.ptr; + if !Vec::<T, A>::is_zst() { + // SAFETY: We can't overflow; `end` is guaranteed to mark the end of the buffer. + unsafe { self.ptr = self.ptr.add(1) }; + } else { + // For ZST `ptr` has to stay where it is to remain aligned, so we just reduce `self.len` + // by 1. + } + self.len -= 1; + + // SAFETY: `ptr` is guaranteed to point at a valid element within the buffer. + Some(unsafe { ptr.read() }) + } + + /// # Examples + /// + /// ``` + /// let v: KVec<u32> = kernel::kvec![1, 2, 3]?; + /// let mut iter = v.into_iter(); + /// let size = iter.size_hint().0; + /// + /// iter.next(); + /// assert_eq!(iter.size_hint().0, size - 1); + /// + /// iter.next(); + /// assert_eq!(iter.size_hint().0, size - 2); + /// + /// iter.next(); + /// assert_eq!(iter.size_hint().0, size - 3); + /// + /// # Ok::<(), Error>(()) + /// ``` + fn size_hint(&self) -> (usize, Option<usize>) { + (self.len, Some(self.len)) + } +} + +impl<T, A> Drop for IntoIter<T, A> +where + A: Allocator, +{ + fn drop(&mut self) { + // SAFETY: Drop the remaining vector's elements in place, before we free the backing + // memory. + unsafe { ptr::drop_in_place(self.as_raw_mut_slice()) }; + + // If `cap == 0` we never allocated any memory in the first place. + if self.cap != 0 { + // SAFETY: `self.buf` was previously allocated with `A`. + unsafe { A::free(self.buf.cast()) }; + } + } +} + +impl<T, A> IntoIterator for Vec<T, A> +where + A: Allocator, +{ + type Item = T; + type IntoIter = IntoIter<T, A>; + + /// Creates a consuming iterator, that is, one that moves each value out of + /// the vector (from start to end). The vector cannot be used after calling + /// this. + /// + /// # Examples + /// + /// ``` + /// let v = kernel::kvec![1, 2]?; + /// let mut v_iter = v.into_iter(); + /// + /// let first_element: Option<u32> = v_iter.next(); + /// + /// assert_eq!(first_element, Some(1)); + /// assert_eq!(v_iter.next(), Some(2)); + /// assert_eq!(v_iter.next(), None); + /// + /// # Ok::<(), Error>(()) + /// ``` + /// + /// ``` + /// let v = kernel::kvec![]; + /// let mut v_iter = v.into_iter(); + /// + /// let first_element: Option<u32> = v_iter.next(); + /// + /// assert_eq!(first_element, None); + /// + /// # Ok::<(), Error>(()) + /// ``` + #[inline] + fn into_iter(self) -> Self::IntoIter { + let (ptr, len, cap) = self.into_raw_parts(); + + IntoIter { + ptr, + // SAFETY: `ptr` is either a dangling pointer or a pointer to a valid memory + // allocation, allocated with `A`. + buf: unsafe { NonNull::new_unchecked(ptr) }, + len, + cap, + _p: PhantomData::<A>, + } + } +}
Implement `IntoIterator` for `Vec`, `Vec`'s `IntoIter` type, as well as `Iterator` for `IntoIter`. `Vec::into_iter` disassembles the `Vec` into its raw parts; additionally, `IntoIter` keeps track of a separate pointer, which is incremented correspondingsly as the iterator advances, while the length, or the count of elements, is decremented. This also means that `IntoIter` takes the ownership of the backing buffer and is responsible to drop the remaining elements and free the backing buffer, if it's dropped. Signed-off-by: Danilo Krummrich <dakr@kernel.org> --- rust/kernel/alloc.rs | 1 + rust/kernel/alloc/kvec.rs | 186 ++++++++++++++++++++++++++++++++++++++ 2 files changed, 187 insertions(+)