Message-ID: <1a06b767-ca02-41ec-840a-47e73f7876d8@proton.me>
Date: Thu, 26 Sep 2024 13:47:04 +0000
From: Benno Lossin <benno.lossin@...ton.me>
To: Danilo Krummrich <dakr@...nel.org>, ojeda@...nel.org, alex.gaynor@...il.com, wedsonaf@...il.com, boqun.feng@...il.com, gary@...yguo.net, bjorn3_gh@...tonmail.com, a.hindborg@...sung.com, aliceryhl@...gle.com, akpm@...ux-foundation.org
Cc: daniel.almeida@...labora.com, faith.ekstrand@...labora.com, boris.brezillon@...labora.com, lina@...hilina.net, mcanal@...lia.com, zhiw@...dia.com, cjia@...dia.com, jhubbard@...dia.com, airlied@...hat.com, ajanulgu@...hat.com, lyude@...hat.com, linux-kernel@...r.kernel.org, rust-for-linux@...r.kernel.org, linux-mm@...ck.org
Subject: Re: [PATCH v7 13/26] rust: alloc: implement kernel `Vec` type

On 12.09.24 00:52, Danilo Krummrich wrote:
> diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs
> new file mode 100644
> index 000000000000..631a44e19f35
> --- /dev/null
> +++ b/rust/kernel/alloc/kvec.rs
> @@ -0,0 +1,638 @@
> +// SPDX-License-Identifier: GPL-2.0
> +
> +//! Implementation of [`Vec`].
> +
> +use super::{
> +    allocator::{KVmalloc, Kmalloc, Vmalloc},
> +    AllocError, Allocator, Box, Flags,
> +};
> +use core::{
> +    fmt,
> +    marker::PhantomData,
> +    mem::{ManuallyDrop, MaybeUninit},
> +    ops::Deref,
> +    ops::DerefMut,
> +    ops::Index,
> +    ops::IndexMut,
> +    ptr::NonNull,
> +    slice,
> +    slice::SliceIndex,
> +};
> +
> +/// Create a [`Vec`] containing the arguments.

I would change this to [`KVec`].

> +///
> +/// # Examples
> +///
> +/// ```
> +/// let mut v = kernel::kvec![];
> +/// v.push(1, GFP_KERNEL)?;
> +/// assert_eq!(v, [1]);
> +///
> +/// let mut v = kernel::kvec![1; 3]?;
> +/// v.push(4, GFP_KERNEL)?;
> +/// assert_eq!(v, [1, 1, 1, 4]);
> +///
> +/// let mut v = kernel::kvec![1, 2, 3]?;
> +/// v.push(4, GFP_KERNEL)?;
> +/// assert_eq!(v, [1, 2, 3, 4]);
> +///
> +/// # Ok::<(), Error>(())
> +/// ```
> +#[macro_export]
> +macro_rules! kvec {
> +    () => (
> +        $crate::alloc::KVec::new()
> +    );
> +    ($elem:expr; $n:expr) => (
> +        $crate::alloc::KVec::from_elem($elem, $n, GFP_KERNEL)
> +    );
> +    ($($x:expr),+ $(,)?) => (
> +        match $crate::alloc::KBox::new_uninit(GFP_KERNEL) {
> +            Ok(b) => Ok($crate::alloc::KVec::from($crate::alloc::KBox::write(b, [$($x),+]))),
> +            Err(e) => Err(e),
> +        }
> +    );
> +}
> +
> +/// The kernel's [`Vec`] type.
> +///
> +/// A contiguous growable array type with contents allocated with the kernel's allocators (e.g.
> +/// `Kmalloc`, `Vmalloc` or `KVmalloc`), written `Vec<T, A>`.

Can you turn these into links?

> +///
> +/// For non-zero-sized values, a [`Vec`] will use the given allocator `A` for its allocation. For
> +/// the most common allocators the type aliases `KVec`, `VVec` and `KVVec` exist.

Ditto.

> +///
> +/// For zero-sized types the [`Vec`]'s pointer must be `dangling_mut::<T>`; no memory is allocated.
> +///
> +/// Generally, [`Vec`] consists of a pointer that represents the vector's backing buffer, the
> +/// capacity of the vector (the number of elements that currently fit into the vector), it's length
> +/// (the number of elements that are currently stored in the vector) and the `Allocator` type used
> +/// to allocate (and free) the backing buffer.
> +///
> +/// A [`Vec`] can be deconstructed into and (re-)constructed from it's previously named raw parts
> +/// and manually modified.
> +///
> +/// [`Vec`]'s backing buffer gets, if required, automatically increased (re-allocated) when elements
> +/// are added to the vector.
> +///
> +/// # Invariants
> +///
> +/// - `self.ptr` is always properly aligned and either points to memory allocated with `A` or, for
> +///   zero-sized types, is a dangling, well aligned pointer.
> +///
> +/// - `self.len` always represents the exact number of elements stored in the vector.
> +///
> +/// - `self.cap` represents the absolute number of elements that can be stored within the vector
> +///   without re-allocation. However, it is legal for the backing buffer to be larger than
> +///   `size_of<T>` times the capacity.
> +///
> +/// - The `Allocator` type `A` of the vector is the exact same `Allocator` type the backing buffer
> +///   was allocated with (and must be freed with).
> +pub struct Vec<T, A: Allocator> {
> +    ptr: NonNull<T>,
> +    /// Represents the actual buffer size as `cap` times `size_of::<T>` bytes.
> +    ///
> +    /// Note: This isn't quite the same as `Self::capacity`, which in contrast returns the number of
> +    /// elements we can still store without reallocating.
> +    ///
> +    /// # Invariants
> +    ///
> +    /// `cap` must be in the `0..=isize::MAX` range.
> +    cap: usize,
> +    len: usize,
> +    _p: PhantomData<A>,
> +}

[...]

> +    /// Appends an element to the back of the [`Vec`] instance.
> +    ///
> +    /// # Examples
> +    ///
> +    /// ```
> +    /// let mut v = KVec::new();
> +    /// v.push(1, GFP_KERNEL)?;
> +    /// assert_eq!(&v, &[1]);
> +    ///
> +    /// v.push(2, GFP_KERNEL)?;
> +    /// assert_eq!(&v, &[1, 2]);
> +    /// # Ok::<(), Error>(())
> +    /// ```
> +    pub fn push(&mut self, v: T, flags: Flags) -> Result<(), AllocError> {
> +        Vec::reserve(self, 1, flags)?;
> +
> +        // SAFETY:
> +        // - `self.len` is smaller than `self.capacity` and hence, the resulting pointer is
> +        //   guaranteed to be part of the same allocated object.
> +        // - `self.len` can not overflow `isize`.
> +        let ptr = unsafe { self.as_mut_ptr().add(self.len) };
> +
> +        // SAFETY:
> +        // - `ptr` is properly aligned and valid for writes.
> +        unsafe { core::ptr::write(ptr, v) };

Why not use `self.spare_capacity_mut()[0].write(v);`?

If you want to avoid the bounds check, you can do

    let first = self.spare_capacity_mut().first();
    // SAFETY: the call to `Vec::reserve` above ensures that `spare_capacity_mut()` is non-empty.
    unsafe { first.unwrap_unchecked() }.write(v);

> +
> +        // SAFETY: We just initialised the first spare entry, so it is safe to increase the length
> +        // by 1. We also know that the new length is <= capacity because of the previous call to
> +        // `reserve` above.
> +        unsafe { self.set_len(self.len() + 1) };
> +        Ok(())
> +    }
> +
> +    /// Creates a new [`Vec`] instance with at least the given capacity.
> +    ///
> +    /// # Examples
> +    ///
> +    /// ```
> +    /// let v = KVec::<u32>::with_capacity(20, GFP_KERNEL)?;
> +    ///
> +    /// assert!(v.capacity() >= 20);
> +    /// # Ok::<(), Error>(())
> +    /// ```
> +    pub fn with_capacity(capacity: usize, flags: Flags) -> Result<Self, AllocError> {
> +        let mut v = Vec::new();
> +
> +        Self::reserve(&mut v, capacity, flags)?;
> +
> +        Ok(v)
> +    }
> +
> +    /// Pushes clones of the elements of slice into the [`Vec`] instance.
> +    ///
> +    /// # Examples
> +    ///
> +    /// ```
> +    /// let mut v = KVec::new();
> +    /// v.push(1, GFP_KERNEL)?;
> +    ///
> +    /// v.extend_from_slice(&[20, 30, 40], GFP_KERNEL)?;
> +    /// assert_eq!(&v, &[1, 20, 30, 40]);
> +    ///
> +    /// v.extend_from_slice(&[50, 60], GFP_KERNEL)?;
> +    /// assert_eq!(&v, &[1, 20, 30, 40, 50, 60]);
> +    /// # Ok::<(), Error>(())
> +    /// ```
> +    pub fn extend_from_slice(&mut self, other: &[T], flags: Flags) -> Result<(), AllocError>
> +    where
> +        T: Clone,

This method can be moved into the other impl block below, it already has
the `T: Clone` bound.

> +    {
> +        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(())
> +    }
> +
> +    /// Creates a Vec<T, A> from a pointer, a length and a capacity using the allocator `A`.
> +    ///
> +    /// # Examples
> +    ///
> +    /// ```
> +    /// let mut v = kernel::kvec![1, 2, 3]?;
> +    /// v.reserve(1, GFP_KERNEL)?;
> +    ///
> +    /// let (mut ptr, mut len, cap) = v.into_raw_parts();
> +    ///
> +    /// // SAFETY: We've just reserved memory for another element.
> +    /// unsafe { ptr.add(len).write(4) };
> +    /// len += 1;
> +    ///
> +    /// // SAFETY: We only wrote an additional element at the end of the `KVec`'s buffer and
> +    /// // correspondingly increased the length of the `KVec` by one. Otherwise, we construct it
> +    /// // from the exact same raw parts.
> +    /// let v = unsafe { KVec::from_raw_parts(ptr, len, cap) };
> +    ///
> +    /// assert_eq!(v, [1, 2, 3, 4]);
> +    ///
> +    /// # Ok::<(), Error>(())
> +    /// ```
> +    ///
> +    /// # Safety
> +    ///
> +    /// If `T` is a ZST:
> +    ///
> +    /// - `ptr` must be a dangling, well aligned pointer.
> +    ///
> +    /// Otherwise:
> +    ///
> +    /// - `ptr` must have been allocated with the allocator `A`.
> +    /// - `ptr` must satisfy or exceed the alignment requirements of `T`.
> +    /// - `ptr` must point to memory with a size of at least `size_of::<T>() * capacity`.
> +    ///    bytes.
> +    /// - The allocated size in bytes must not be larger than `isize::MAX`.
> +    /// - `length` must be less than or equal to `capacity`.
> +    /// - The first `length` elements must be initialized values of type `T`.
> +    ///
> +    /// It is also valid to create an empty `Vec` passing a dangling pointer for `ptr` and zero for
> +    /// `cap` and `len`.
> +    pub unsafe fn from_raw_parts(ptr: *mut T, length: usize, capacity: usize) -> Self {
> +        let cap = if Self::is_zst() { 0 } else { capacity };
> +
> +        Self {
> +            // SAFETY: By the safety requirements, `ptr` is either dangling or pointing to a valid
> +            // memory allocation, allocated with `A`.
> +            ptr: unsafe { NonNull::new_unchecked(ptr) },
> +            cap,
> +            len: length,
> +            _p: PhantomData::<A>,
> +        }

Would be nice to have `debug_assert!(length <= capacity)` here. But feel
free to make that a good-first-issue instead of including it in the next
version. (there are probably more asserts elsewhere)

> +    }
> +
> +    /// Consumes the `Vec<T, A>` and returns its raw components `pointer`, `length` and `capacity`.
> +    ///
> +    /// This will not run the destructor of the contained elements and for non-ZSTs the allocation
> +    /// will stay alive indefinitely. Use [`Vec::from_raw_parts`] to recover the [`Vec`], drop the
> +    /// elements and free the allocation, if any.
> +    pub fn into_raw_parts(self) -> (*mut T, usize, usize) {
> +        let mut me = ManuallyDrop::new(self);
> +        let len = me.len();
> +        let capacity = me.capacity();
> +        let ptr = me.as_mut_ptr();
> +        (ptr, len, capacity)
> +    }

[...]

> +macro_rules! impl_slice_eq {
> +    ([$($vars:tt)*] $lhs:ty, $rhs:ty) => {

You could wrap the entire pattern in "$()*", same for the entire body
and then...

> +        impl<T, U, $($vars)*> PartialEq<$rhs> for $lhs
> +        where
> +            T: PartialEq<U>,
> +        {
> +            #[inline]
> +            fn eq(&self, other: &$rhs) -> bool { self[..] == other[..] }
> +        }
> +    }
> +}
> +
> +impl_slice_eq! { [A1: Allocator, A2: Allocator] Vec<T, A1>, Vec<U, A2> }
> +impl_slice_eq! { [A: Allocator] Vec<T, A>, &[U] }
> +impl_slice_eq! { [A: Allocator] Vec<T, A>, &mut [U] }
> +impl_slice_eq! { [A: Allocator] &[T], Vec<U, A> }
> +impl_slice_eq! { [A: Allocator] &mut [T], Vec<U, A> }
> +impl_slice_eq! { [A: Allocator] Vec<T, A>, [U] }
> +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] }

...we could have a single `impl_slice_eq` invocation here:

    impl_slice_eq! {
        [A1: Allocator, A2: Allocator] Vec<T, A1>, Vec<U, A2>
        [A: Allocator] Vec<T, A>, &[U]
        [A: Allocator] Vec<T, A>, &mut [U]
        [A: Allocator] &[T], Vec<U, A>
        [A: Allocator] &mut [T], Vec<U, A>
        [A: Allocator] Vec<T, A>, [U]
        [A: Allocator] [T], Vec<U, A>
        [A: Allocator, const N: usize] Vec<T, A>, [U; N]
        [A: Allocator, const N: usize] Vec<T, A>, &[U; N]
    }

Not a huge improvement, but I think it makes it a bit nicer to read.

---
Cheers,
Benno

> diff --git a/rust/kernel/prelude.rs b/rust/kernel/prelude.rs
> index d5f2fe42d093..80223cdaa485 100644
> --- a/rust/kernel/prelude.rs
> +++ b/rust/kernel/prelude.rs
> @@ -14,7 +14,7 @@
>  #[doc(no_inline)]
>  pub use core::pin::Pin;
> 
> -pub use crate::alloc::{flags::*, vec_ext::VecExt, Box, KBox, KVBox, VBox};
> +pub use crate::alloc::{flags::*, vec_ext::VecExt, Box, KBox, KVBox, KVVec, KVec, VBox, VVec};
> 
>  #[doc(no_inline)]
>  pub use alloc::vec::Vec;
> --
> 2.46.0
> 

Powered by blists - more mailing lists