From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mail-lf1-f52.google.com (mail-lf1-f52.google.com [209.85.167.52]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 43C8F1B1505 for ; Thu, 1 Aug 2024 15:32:04 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.167.52 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1722526327; cv=none; b=gZ/VztnnAahip6RofiVzwDyL0xta7TTAhEj/MZOfKkB8nXoOeOm/u2mo0t4esyvzK1rIqm+YRV2TwrdXkuPTJcdM2bHGI2181lQFGiJDVr/TQnGljxfBM1ul5LketxLQwepptL3V0eysSk4e45cAhzL0/8CjPLUpUMcIESE7Fp8= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1722526327; c=relaxed/simple; bh=UD56E68ENmLEk0wiRbMmZL8yoLmQDWgah36mnTBCwG0=; h=MIME-Version:References:In-Reply-To:From:Date:Message-ID:Subject: To:Cc:Content-Type; b=GOQ9l62ux0NSsmLRbxcvAesaQNpQrIlYWaMtHCLzV8xwMqGJ4BveSKnDKiYESMtVTGXGXfZbkvRgKVpH5/lwiW5q0MHIKUKIcZwrQEY0EW3VKiQ2/JSlYiRmbE0v5tr8W/A+UdeM/mC7fFNxnZZUbtLLwneprBQFvQR7DGOBP4A= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com; spf=pass smtp.mailfrom=google.com; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b=ejMAEu1H; arc=none smtp.client-ip=209.85.167.52 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=google.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="ejMAEu1H" Received: by mail-lf1-f52.google.com with SMTP id 2adb3069b0e04-52f01afa11cso10610508e87.0 for ; Thu, 01 Aug 2024 08:32:04 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1722526322; x=1723131122; darn=vger.kernel.org; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:from:to:cc:subject:date :message-id:reply-to; bh=8q/+QE5zTjhWt8FFsg2XMcr5XXnvtPlKL5CAoEjThw8=; b=ejMAEu1HNHi9prkuX/kS6EoAnCBTGw57QBTSGe0FRaHcP7Wv2BMgFB4U9Oosqs9EMl Z6DCgSsbmW0/7VeQ9X6LuuUQVFUcotM0cfl0cHo9JxH8ne7LpTejWqgDzI6NpVbSm3jQ 4PJMIjkfn8INSOxcwrZohhKDZhU1sa/rpWPYLM5U3859AAuTYi8/anblrfTuY3JWrNWs WHSleN2zeTBHUuNo0m2Rq6mlOM3w39G9GrZZg8DH+nO1xQtEcw6iRgGXNjJUHBYtB4Vs xcHP+fQsBQVh+cUC1FqovPqIYIL50qWYg1iBUVEQ6SWVL+Tto2c4OaxgyQyo8EPrg0lK oT+A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1722526322; x=1723131122; h=content-transfer-encoding:cc:to:subject:message-id:date:from :in-reply-to:references:mime-version:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=8q/+QE5zTjhWt8FFsg2XMcr5XXnvtPlKL5CAoEjThw8=; b=CwFuMsQbW1T0T7XbS53w0ls/JHbXCsoL0c1nXLW5Ok8e45pIH20JVxydqUZ3h8oU2h fbe7Tbqu4Uw3jzuJimPSJB8v/uOPemDx3owiZhc37aUxpoztDBJK6+z+n5HBxIK6SkMz 94a5Q5BJFBr6sJ8myYFHWtSwarbN2yA+Xep98Haea0PkJHozo2pa+mZy3JS7XrDCvXHo xFdmAqWCTkQaaC8JlS0Fwt/ZbB+XocZVPGN2eZ1mQ5Q90QOsmdW+ff0V8DZSJnFn3cf9 SEM7HaREhQVBcA2ZrLWwie6r1LGXY129xUx6TIM+TjU3D7oHR2NlSieN4YYWkouvRLzg +URA== X-Forwarded-Encrypted: i=1; AJvYcCVt2DYzLqWsepuiPcA4Bb60gK/44vr/uuRBfFlG1nqo7x9krKUk+jPPy0H0Cl8fbwFX4g3aNMfHRDhHQVcl+IAOCAdu9DSYJmP/c7BUdho= X-Gm-Message-State: AOJu0YzimbrCrPiZwoJWOqe2884drwrpEoQv4EVm/G6EdIdOnRSB4kiw AYt42YEqSyPs3q7udpJOh9KaOH52Nir8Z09/8YNVMMBvGxE3v4OxHaSy3u9bo8ExyDaNmE7vS9X 3asrkDB3wI+gAYAYduCdG8ZE+bKibX5gXfz5z X-Google-Smtp-Source: AGHT+IH3ZhzaItjlGYNK09lPZ0p1tSUqcrC4pfTDXEkR6MDVsQs/AfxamBOeBKST0JHzXPEBeU3xhL/aP+UuurvXJq8= X-Received: by 2002:a05:6512:b1f:b0:52e:9d6c:4462 with SMTP id 2adb3069b0e04-530bb3797d6mr253447e87.23.1722526321788; Thu, 01 Aug 2024 08:32:01 -0700 (PDT) Precedence: bulk X-Mailing-List: rust-for-linux@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 References: <20240801000641.1882-1-dakr@kernel.org> <20240801000641.1882-16-dakr@kernel.org> In-Reply-To: From: Alice Ryhl Date: Thu, 1 Aug 2024 17:31:48 +0200 Message-ID: Subject: Re: [PATCH v3 15/25] rust: alloc: implement kernel `Vec` type To: Danilo Krummrich Cc: ojeda@kernel.org, alex.gaynor@gmail.com, wedsonaf@gmail.com, boqun.feng@gmail.com, gary@garyguo.net, bjorn3_gh@protonmail.com, benno.lossin@proton.me, a.hindborg@samsung.com, akpm@linux-foundation.org, daniel.almeida@collabora.com, faith.ekstrand@collabora.com, boris.brezillon@collabora.com, lina@asahilina.net, mcanal@igalia.com, zhiw@nvidia.com, acurrid@nvidia.com, cjia@nvidia.com, jhubbard@nvidia.com, airlied@redhat.com, ajanulgu@redhat.com, lyude@redhat.com, linux-kernel@vger.kernel.org, rust-for-linux@vger.kernel.org, linux-mm@kvack.org Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable On Thu, Aug 1, 2024 at 5:28=E2=80=AFPM Danilo Krummrich w= rote: > > On Thu, Aug 01, 2024 at 05:05:41PM +0200, Alice Ryhl wrote: > > On Thu, Aug 1, 2024 at 2:08=E2=80=AFAM Danilo Krummrich wrote: > > > > > > `Vec` provides a contiguous growable array type (such as `Vec`) with > > > contents allocated with the kernel's allocators (e.g. `Kmalloc`, > > > `Vmalloc` or `KVmalloc`). > > > > > > In contrast to Rust's `Vec` type, the kernel `Vec` type considers the > > > kernel's GFP flags for all appropriate functions, always reports > > > allocation failures through `Result<_, AllocError>` and remains > > > independent from unstable features. > > > > > > Signed-off-by: Danilo Krummrich > > > --- > > > rust/kernel/alloc.rs | 6 + > > > rust/kernel/alloc/kbox.rs | 16 +- > > > rust/kernel/alloc/kvec.rs | 583 ++++++++++++++++++++++++++++++++++++= ++ > > > rust/kernel/prelude.rs | 2 +- > > > 4 files changed, 605 insertions(+), 2 deletions(-) > > > create mode 100644 rust/kernel/alloc/kvec.rs > > > > > > diff --git a/rust/kernel/alloc.rs b/rust/kernel/alloc.rs > > > index 4bddd023aa7f..bd93140f3094 100644 > > > --- a/rust/kernel/alloc.rs > > > +++ b/rust/kernel/alloc.rs > > > @@ -5,6 +5,7 @@ > > > #[cfg(not(any(test, testlib)))] > > > pub mod allocator; > > > pub mod kbox; > > > +pub mod kvec; > > > pub mod vec_ext; > > > > > > #[cfg(any(test, testlib))] > > > @@ -18,6 +19,11 @@ > > > pub use self::kbox::KVBox; > > > pub use self::kbox::VBox; > > > > > > +pub use self::kvec::KVVec; > > > +pub use self::kvec::KVec; > > > +pub use self::kvec::VVec; > > > +pub use self::kvec::Vec; > > > + > > > /// Indicates an allocation error. > > > #[derive(Copy, Clone, PartialEq, Eq, Debug)] > > > pub struct AllocError; > > > diff --git a/rust/kernel/alloc/kbox.rs b/rust/kernel/alloc/kbox.rs > > > index 7074f00e07bc..39feaed4a8f8 100644 > > > --- a/rust/kernel/alloc/kbox.rs > > > +++ b/rust/kernel/alloc/kbox.rs > > > @@ -2,7 +2,7 @@ > > > > > > //! Implementation of [`Box`]. > > > > > > -use super::{AllocError, Allocator, Flags}; > > > +use super::{AllocError, Allocator, Flags, Vec}; > > > use core::fmt; > > > use core::marker::PhantomData; > > > use core::mem::ManuallyDrop; > > > @@ -169,6 +169,20 @@ pub fn into_pin(b: Self) -> Pin > > > } > > > } > > > > > > +impl Box<[T; N], A> > > > +where > > > + A: Allocator, > > > +{ > > > + /// Convert a `Box<[T], A>` to a `Vec`. > > > + pub fn into_vec(b: Self) -> Vec { > > > > This doc-comment seems wrong. [T] and [T; N] are not the same thing. > > Indeed, gonna fix. > > > > > > + let len =3D b.len(); > > > + unsafe { > > > + let ptr =3D Self::into_raw(b); > > > + Vec::from_raw_parts(ptr as _, len, len) > > > + } > > > + } > > > +} > > > + > > > impl Box, A> > > > where > > > A: Allocator, > > > diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs > > > new file mode 100644 > > > index 000000000000..04cc85f7d92c > > > --- /dev/null > > > +++ b/rust/kernel/alloc/kvec.rs > > > @@ -0,0 +1,583 @@ > > > +// SPDX-License-Identifier: GPL-2.0 > > > + > > > +//! Implementation of [`Vec`]. > > > + > > > +use super::{AllocError, Allocator, Flags}; > > > +use crate::types::Unique; > > > +use core::{ > > > + fmt, > > > + marker::PhantomData, > > > + mem::{ManuallyDrop, MaybeUninit}, > > > + ops::Deref, > > > + ops::DerefMut, > > > + ops::Index, > > > + ops::IndexMut, > > > + slice, > > > + slice::SliceIndex, > > > +}; > > > + > > > +/// Create a [`Vec`] containing the arguments. > > > +/// > > > +/// # Examples > > > +/// > > > +/// ``` > > > +/// let mut v =3D kernel::kvec![]; > > > +/// v.push(1, GFP_KERNEL)?; > > > +/// assert_eq!(v, [1]); > > > +/// > > > +/// let mut v =3D kernel::kvec![1; 3]?; > > > +/// v.push(4, GFP_KERNEL)?; > > > +/// assert_eq!(v, [1, 1, 1, 4]); > > > +/// > > > +/// let mut v =3D kernel::kvec![1, 2, 3]?; > > > +/// v.push(4, GFP_KERNEL)?; > > > +/// assert_eq!(v, [1, 2, 3, 4]); > > > +/// > > > +/// # Ok::<(), Error>(()) > > > +/// ``` > > > +#[macro_export] > > > +macro_rules! kvec { > > > + () =3D> ( > > > + { > > > + $crate::alloc::KVec::new() > > > + } > > > + ); > > > + ($elem:expr; $n:expr) =3D> ( > > > + { > > > + $crate::alloc::KVec::from_elem($elem, $n, GFP_KERNEL) > > > + } > > > + ); > > > + ($($x:expr),+ $(,)?) =3D> ( > > > + { > > > + match $crate::alloc::KBox::new([$($x),+], GFP_KERNEL) { > > > + Ok(b) =3D> Ok($crate::alloc::KBox::into_vec(b)), > > > + Err(e) =3D> Err(e), > > > + } > > > + } > > > + ); > > > +} > > > + > > > +/// The kernel's [`Vec`] type. > > > +/// > > > +/// A contiguous growable array type with contents allocated with th= e kernel's allocators (e.g. > > > +/// `Kmalloc`, `Vmalloc` or `KVmalloc`, written `Vec`. > > > > A closing bracket is missing in this sentence. > > Gonna fix. > > > > > > +/// For non-zero-sized values, a [`Vec`] will use the given allocato= r `A` for its allocation. For > > > +/// the most common allocators the type aliases `KVec`, `VVec` and `= KVVec` exist. > > > +/// > > > +/// For zero-sized types the [`Vec`]'s pointer must be `dangling_mut= ::`; no memory is allocated. > > > +/// > > > +/// Generally, [`Vec`] consists of a pointer that represents the vec= tor's backing buffer, the > > > +/// capacity of the vector (the number of elements that currently fi= t into the vector), it's length > > > +/// (the number of elements that are currently stored in the vector)= and the `Allocator` 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 increa= sed (re-allocated) when elements > > > +/// are added to the vector. > > > +/// > > > +/// # Invariants > > > +/// > > > +/// The [`Vec`] backing buffer's pointer always properly aligned and= either points to memory > > > +/// allocated with `A` or, for zero-sized types, is a dangling point= er. > > > +/// > > > +/// The length of the vector always represents the exact number of e= lements stored in the vector. > > > +/// > > > +/// The capacity of the vector always represents the absolute number= of elements that can be stored > > > +/// within the vector without re-allocation. However, it is legal fo= r the backing buffer to be > > > +/// larger than `size_of` times the capacity. > > > +/// > > > +/// The `Allocator` of the vector is the exact allocator the backing= buffer was allocated with (and > > > +/// must be freed with). > > > +pub struct Vec { > > > + ptr: Unique, > > > + /// Never used for ZSTs; it's `capacity()`'s responsibility to r= eturn usize::MAX in that case. > > > + /// > > > + /// # Safety > > > + /// > > > + /// `cap` must be in the `0..=3Disize::MAX` range. > > > + cap: usize, > > > > This section header should say Invariants, not Safety. > > Agreed. > > > > > > + len: usize, > > > + _p: PhantomData, > > > +} > > > + > > > +/// Type alias for `Vec` with a `Kmalloc` allocator. > > > +/// > > > +/// # Examples > > > +/// > > > +/// ``` > > > +/// let mut v =3D KVec::new(); > > > +/// v.push(1, GFP_KERNEL)?; > > > +/// assert_eq!(&v, &[1]); > > > +/// > > > +/// # Ok::<(), Error>(()) > > > +/// ``` > > > +pub type KVec =3D Vec; > > > + > > > +/// Type alias for `Vec` with a `Vmalloc` allocator. > > > +/// > > > +/// # Examples > > > +/// > > > +/// ``` > > > +/// let mut v =3D VVec::new(); > > > +/// v.push(1, GFP_KERNEL)?; > > > +/// assert_eq!(&v, &[1]); > > > +/// > > > +/// # Ok::<(), Error>(()) > > > +/// ``` > > > +pub type VVec =3D Vec; > > > + > > > +/// Type alias for `Vec` with a `KVmalloc` allocator. > > > +/// > > > +/// # Examples > > > +/// > > > +/// ``` > > > +/// let mut v =3D KVVec::new(); > > > +/// v.push(1, GFP_KERNEL)?; > > > +/// assert_eq!(&v, &[1]); > > > +/// > > > +/// # Ok::<(), Error>(()) > > > +/// ``` > > > +pub type KVVec =3D Vec; > > > + > > > +impl Vec > > > +where > > > + A: Allocator, > > > +{ > > > + #[inline] > > > + fn is_zst() -> bool { > > > + core::mem::size_of::() =3D=3D 0 > > > + } > > > + > > > + /// Returns the total number of elements the vector can hold wit= hout > > > + /// reallocating. > > > + pub fn capacity(&self) -> usize { > > > + if Self::is_zst() { > > > + usize::MAX > > > + } else { > > > + self.cap > > > + } > > > + } > > > > I would consider always storing usize::MAX in the capacity field for zs= t types? > > This wouldn't work. `self.cap` is supposed to represent the actual capaci= ty of > the vector, which for ZSTs is zero. Storing usize::MAX values of a zero-sized type takes up zero bytes, and your vector has space for zero bytes. Seems sensible to me to use usize::MAX. Anyway, it's up to you. I'm ok either way. > > > + > > > + /// Returns the number of elements in the vector, also referred = to > > > + /// as its 'length'. > > > + #[inline] > > > + pub fn len(&self) -> usize { > > > + self.len > > > + } > > > + > > > + /// Forces the length of the vector to new_len. > > > + /// > > > + /// # Safety > > > + /// > > > + /// - `new_len` must be less than or equal to [`Self::capacity()= `]. > > > + /// - The elements at `old_len..new_len` must be initialized. > > > + #[inline] > > > + pub unsafe fn set_len(&mut self, new_len: usize) { > > > + self.len =3D new_len; > > > + } > > > + > > > + /// Extracts a slice containing the entire vector. > > > + /// > > > + /// Equivalent to `&s[..]`. > > > + #[inline] > > > + pub fn as_slice(&self) -> &[T] { > > > + self > > > + } > > > + > > > + /// Extracts a mutable slice of the entire vector. > > > + /// > > > + /// Equivalent to `&mut s[..]`. > > > + #[inline] > > > + pub fn as_mut_slice(&mut self) -> &mut [T] { > > > + self > > > + } > > > + > > > + /// Returns an unsafe mutable pointer to the vector's buffer, or= a dangling > > > + /// raw pointer valid for zero sized reads if the vector didn't = allocate. > > > + #[inline] > > > + pub fn as_mut_ptr(&self) -> *mut T { > > > + self.ptr.as_ptr() > > > + } > > > + > > > + /// Returns a raw pointer to the slice's buffer. > > > + #[inline] > > > + pub fn as_ptr(&self) -> *const T { > > > + self.as_mut_ptr() > > > + } > > > + > > > + /// Returns `true` if the vector contains no elements. > > > + /// > > > + /// # Examples > > > + /// > > > + /// ``` > > > + /// let mut v =3D KVec::new(); > > > + /// assert!(v.is_empty()); > > > + /// > > > + /// v.push(1, GFP_KERNEL); > > > + /// assert!(!v.is_empty()); > > > + /// ``` > > > + #[inline] > > > + pub fn is_empty(&self) -> bool { > > > + self.len() =3D=3D 0 > > > + } > > > + > > > + /// Constructs a new, empty Vec. > > > + /// > > > + /// This method does not allocate by itself. > > > + #[inline] > > > + pub const fn new() -> Self { > > > + Self { > > > + ptr: Unique::dangling(), > > > + cap: 0, > > > + len: 0, > > > + _p: PhantomData::, > > > + } > > > + } > > > + > > > + /// Returns the remaining spare capacity of the vector as a slic= e of `MaybeUninit`. > > > + pub fn spare_capacity_mut(&mut self) -> &mut [MaybeUninit] { > > > + // SAFETY: The memory between `self.len` and `self.capacity`= is guaranteed to be allocated > > > + // and valid, but uninitialized. > > > + unsafe { > > > + slice::from_raw_parts_mut( > > > + self.as_mut_ptr().add(self.len) as *mut MaybeUninit<= T>, > > > + self.capacity() - self.len, > > > + ) > > > + } > > > > Is this correct for ZSTs? > > Yes, it gives us a slice of ZSTs with the maximum possible length usize::= MAX. > > > > > > + } > > > + > > > + /// Appends an element to the back of the [`Vec`] instance. > > > + /// > > > + /// # Examples > > > + /// > > > + /// ``` > > > + /// let mut v =3D 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<(), AllocEr= ror> { > > > + Vec::reserve(self, 1, flags)?; > > > + let s =3D self.spare_capacity_mut(); > > > + s[0].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 <=3D capacity b= ecause 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 capac= ity. > > > + /// > > > + /// # Examples > > > + /// > > > + /// ``` > > > + /// let v =3D KVec::::with_capacity(20, GFP_KERNEL)?; > > > + /// > > > + /// assert!(v.capacity() >=3D 20); > > > + /// # Ok::<(), Error>(()) > > > + /// ``` > > > + pub fn with_capacity(capacity: usize, flags: Flags) -> Result { > > > + let mut v =3D Vec::new(); > > > + > > > + Self::reserve(&mut v, capacity, flags)?; > > > + > > > + Ok(v) > > > + } > > > + > > > + /// Pushes clones of the elements of slice into the [`Vec`] inst= ance. > > > + /// > > > + /// # Examples > > > + /// > > > + /// ``` > > > + /// let mut v =3D 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, > > > + { > > > + self.reserve(other.len(), flags)?; > > > + for (slot, item) in core::iter::zip(self.spare_capacity_mut(= ), other) { > > > + slot.write(item.clone()); > > > + } > > > + > > > + // SAFETY: We just initialised the `other.len()` spare entri= es, so it is safe to increase > > > + // the length by the same amount. We also know that the new = length is <=3D capacity because > > > + // of the previous call to `reserve` above. > > > + unsafe { self.set_len(self.len() + other.len()) }; > > > + Ok(()) > > > + } > > > + > > > + /// Creates a Vec directly from a pointer, a length, a cap= acity, and an allocator. > > > + /// > > > + /// # Safety > > > + /// > > > + /// This is highly unsafe, due to the number of invariants that = aren=E2=80=99t checked: > > > + /// > > > + /// - `ptr` must be currently allocated via the given allocator = `A`. > > > + /// - `T` needs to have the same alignment as what `ptr` was all= ocated with. (`T` having a less > > > + /// strict alignment is not sufficient, the alignment really n= eeds to be equal to satisfy the > > > + /// `dealloc` requirement that memory must be allocated and de= allocated with the same layout.) > > > + /// - The size of `T` times the `capacity` (i.e. the allocated s= ize in bytes) needs to be > > > + /// smaller or equal the size the pointer was allocated with. > > > + /// - `length` needs to be less than or equal to `capacity`. > > > + /// - The first `length` values must be properly initialized val= ues of type `T`. > > > + /// - The allocated size in bytes must be no larger than `isize:= :MAX`. See the safety > > > + /// documentation of `pointer::offset`. > > > + /// > > > + /// It is also valid to create an empty `Vec` passing a dangling= pointer for `ptr` and zero for > > > + /// `cap` and `len`. > > > + /// > > > + /// # Examples > > > + /// > > > + /// ``` > > > + /// let mut v =3D kernel::kvec![1, 2, 3]?; > > > + /// v.reserve(1, GFP_KERNEL)?; > > > + /// > > > + /// let (mut ptr, mut len, cap) =3D v.into_raw_parts(); > > > + /// > > > + /// // SAFETY: We've just reserved memory for another element. > > > + /// unsafe { ptr.add(len).write(4) }; > > > + /// len +=3D 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 =3D unsafe { KVec::from_raw_parts(ptr, len, cap) }; > > > + /// > > > + /// assert_eq!(v, [1, 2, 3, 4]); > > > + /// > > > + /// # Ok::<(), Error>(()) > > > + /// ``` > > > + pub unsafe fn from_raw_parts(ptr: *mut T, length: usize, capacit= y: usize) -> Self { > > > + let cap =3D if Self::is_zst() { 0 } else { capacity }; > > > + > > > + Self { > > > + // SAFETY: By the safety requirements, `ptr` is either d= angling or pointing to a valid > > > + // memory allocation, allocated with `A`. > > > + ptr: unsafe { Unique::new_unchecked(ptr) }, > > > + cap, > > > + len: length, > > > + _p: PhantomData::, > > > + } > > > + } > > > + > > > + /// Decomposes a `Vec` into its raw components: (`pointer`= , `length`, `capacity`). > > > + pub fn into_raw_parts(self) -> (*mut T, usize, usize) { > > > + let me =3D ManuallyDrop::new(self); > > > + let len =3D me.len(); > > > + let capacity =3D me.capacity(); > > > + let ptr =3D me.as_mut_ptr(); > > > + (ptr, len, capacity) > > > + } > > > + > > > + /// Ensures that the capacity exceeds the length by at least `ad= ditional` elements. > > > + /// > > > + /// # Examples > > > + /// > > > + /// ``` > > > + /// let mut v =3D KVec::new(); > > > + /// v.push(1, GFP_KERNEL)?; > > > + /// > > > + /// v.reserve(10, GFP_KERNEL)?; > > > + /// let cap =3D v.capacity(); > > > + /// assert!(cap >=3D 10); > > > + /// > > > + /// v.reserve(10, GFP_KERNEL)?; > > > + /// let new_cap =3D v.capacity(); > > > + /// assert_eq!(new_cap, cap); > > > + /// > > > + /// # Ok::<(), Error>(()) > > > + /// ``` > > > + pub fn reserve(&mut self, additional: usize, flags: Flags) -> Re= sult<(), AllocError> { > > > + let len =3D self.len(); > > > + let cap =3D self.capacity(); > > > + > > > + if cap - len >=3D additional { > > > + return Ok(()); > > > + } > > > + > > > + if Self::is_zst() { > > > + // The capacity is already `usize::MAX` for SZTs, we can= 't go higher. > > > + return Err(AllocError); > > > + } > > > + > > > + // We know cap is <=3D `isize::MAX` because `Layout::array` = fails if the resulting byte size > > > + // is greater than `isize::MAX`. So the multiplication by tw= o won't overflow. > > > > You know it won't overflow because of the type invariants. The thing > > about Layout::array should instead be used to argue why setting > > self.cap below does not break the invariants. > > Good point, I will reword it. > > > > > > + let new_cap =3D core::cmp::max(cap * 2, len.checked_add(addi= tional).ok_or(AllocError)?); > > > + let layout =3D core::alloc::Layout::array::(new_cap).map_= err(|_| AllocError)?; > > > + > > > + // We need to make sure that `ptr` is either NULL or comes f= rom a previous call to > > > + // `realloc_flags`. A `Vec`'s `ptr` value is not guara= nteed to be NULL and might be > > > + // dangling after being created with `Vec::new`. Instead, we= can rely on `Vec`'s > > > + // capacity to be zero if no memory has been allocated yet. > > > + let ptr =3D if cap =3D=3D 0 { > > > + None > > > + } else { > > > + Some(self.ptr.as_non_null().cast()) > > > + }; > > > + > > > + // SAFETY: `ptr` is valid because it's either `None` or come= s from a previous call to > > > + // `A::realloc`. We also verified that the type is not a ZST= . > > > + let ptr =3D unsafe { A::realloc(ptr, layout, flags)? }; > > > + > > > + self.ptr =3D ptr.cast().into(); > > > + self.cap =3D new_cap; > > > + > > > + Ok(()) > > > + } > > > +} > > > + > > > +impl Vec { > > > + /// Extend the vector by `n` clones of value. > > > + pub fn extend_with(&mut self, n: usize, value: T, flags: Flags) = -> Result<(), AllocError> { > > > + self.reserve(n, flags)?; > > > + > > > + let spare =3D self.spare_capacity_mut(); > > > + > > > + for i in 0..spare.len() - 1 { > > > + spare[i].write(value.clone()); > > > + } > > > > Minus one? Shouldn't this instead loop for `0..n`? > > We can indeed just use `n` instead of `slice::len` here. But `spare.len()` could be longer than `n`? > > Minus one, because we create clones for the first n - 1 elements and for = the > last one we just use the value itself. > > > > > > + > > > + // We can write the last element directly without cloning ne= edlessly > > > + spare[spare.len() - 1].write(value); > > > > spare[n-1].write(value); > > Yep, works too. > > > > > > + > > > + // SAFETY: `self.reserve` not bailing out with an error guar= antees that we're not > > > + // exceeding the capacity of this `Vec`. > > > + unsafe { self.set_len(self.len() + n) }; > > > + > > > + Ok(()) > > > + } > > > + > > > + /// Create a new `Vec and extend it by `n` clones of `valu= e`. > > > + pub fn from_elem(value: T, n: usize, flags: Flags) -> Result { > > > + let mut v =3D Self::with_capacity(n, flags)?; > > > + > > > + v.extend_with(n, value, flags)?; > > > + > > > + Ok(v) > > > + } > > > +} > > > + > > > +impl Drop for Vec > > > +where > > > + A: Allocator, > > > +{ > > > + fn drop(&mut self) { > > > + // SAFETY: We need to drop the vector's elements in place, b= efore we free the backing > > > + // memory. > > > + unsafe { > > > + core::ptr::drop_in_place(core::ptr::slice_from_raw_parts= _mut( > > > + self.as_mut_ptr(), > > > + self.len, > > > + )) > > > + }; > > > + > > > + // If `cap =3D=3D 0` we never allocated any memory in the fi= rst place. > > > + if self.cap !=3D 0 { > > > + // SAFETY: `self.ptr` was previously allocated with `A`. > > > + unsafe { A::free(self.ptr.as_non_null().cast()) }; > > > > Do you need a ZST check here? > > No, for ZST `self.cap` is always zero. > > > > > > + } > > > + } > > > +} > > > + > > > +impl Default for KVec { > > > + #[inline] > > > + fn default() -> Self { > > > + Self::new() > > > + } > > > +} > > > + > > > +impl fmt::Debug for Vec { > > > + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { > > > + fmt::Debug::fmt(&**self, f) > > > + } > > > +} > > > + > > > +impl Deref for Vec > > > +where > > > + A: Allocator, > > > +{ > > > + type Target =3D [T]; > > > + > > > + #[inline] > > > + fn deref(&self) -> &[T] { > > > + // SAFETY: The memory behind `self.as_ptr()` is guaranteed t= o contain `self.len` > > > + // initialized elements of type `T`. > > > + unsafe { slice::from_raw_parts(self.as_ptr(), self.len) } > > > + } > > > +} > > > + > > > +impl DerefMut for Vec > > > +where > > > + A: Allocator, > > > +{ > > > + #[inline] > > > + fn deref_mut(&mut self) -> &mut [T] { > > > + // SAFETY: The memory behind `self.as_ptr()` is guaranteed t= o contain `self.len` > > > + // initialized elements of type `T`. > > > + unsafe { slice::from_raw_parts_mut(self.as_mut_ptr(), self.l= en) } > > > + } > > > +} > > > + > > > +impl Eq for Vec where A: Allocator {} > > > + > > > +impl, A> Index for Vec > > > +where > > > + A: Allocator, > > > +{ > > > + type Output =3D I::Output; > > > + > > > + #[inline] > > > + fn index(&self, index: I) -> &Self::Output { > > > + Index::index(&**self, index) > > > + } > > > +} > > > + > > > +impl, A> IndexMut for Vec > > > +where > > > + A: Allocator, > > > +{ > > > + #[inline] > > > + fn index_mut(&mut self, index: I) -> &mut Self::Output { > > > + IndexMut::index_mut(&mut **self, index) > > > + } > > > +} > > > + > > > +macro_rules! __impl_slice_eq { > > > + ([$($vars:tt)*] $lhs:ty, $rhs:ty $(where $ty:ty: $bound:ident)?)= =3D> { > > > + impl PartialEq<$rhs> for $lhs > > > + where > > > + T: PartialEq, > > > + $($ty: $bound)? > > > + { > > > + #[inline] > > > + fn eq(&self, other: &$rhs) -> bool { self[..] =3D=3D oth= er[..] } > > > + } > > > + } > > > +} > > > + > > > +__impl_slice_eq! { [A1: Allocator, A2: Allocator] Vec, Vec } > > > +__impl_slice_eq! { [A: Allocator] Vec, &[U] } > > > +__impl_slice_eq! { [A: Allocator] Vec, &mut [U] } > > > +__impl_slice_eq! { [A: Allocator] &[T], Vec } > > > +__impl_slice_eq! { [A: Allocator] &mut [T], Vec } > > > +__impl_slice_eq! { [A: Allocator] Vec, [U] } > > > +__impl_slice_eq! { [A: Allocator] [T], Vec } > > > +__impl_slice_eq! { [A: Allocator, const N: usize] Vec, [U; N] = } > > > +__impl_slice_eq! { [A: Allocator, const N: usize] Vec, &[U; N]= } > > > diff --git a/rust/kernel/prelude.rs b/rust/kernel/prelude.rs > > > index 6bf77577eae7..bb80a43d20fb 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.45.2 > > > > >