From patchwork Thu Aug 1 00:02:14 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: Danilo Krummrich X-Patchwork-Id: 13749354 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id A3408C3DA7F for ; Thu, 1 Aug 2024 00:08:21 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 307A36B00AE; Wed, 31 Jul 2024 20:08:21 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 2B7536B00B0; Wed, 31 Jul 2024 20:08:21 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 0E2EB6B00B1; Wed, 31 Jul 2024 20:08:21 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0011.hostedemail.com [216.40.44.11]) by kanga.kvack.org (Postfix) with ESMTP id DB2246B00AE for ; Wed, 31 Jul 2024 20:08:20 -0400 (EDT) Received: from smtpin03.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay08.hostedemail.com (Postfix) with ESMTP id A13C814081A for ; Thu, 1 Aug 2024 00:08:20 +0000 (UTC) X-FDA: 82401739560.03.977FAAE Received: from sin.source.kernel.org (sin.source.kernel.org [145.40.73.55]) by imf29.hostedemail.com (Postfix) with ESMTP id 52E18120025 for ; Thu, 1 Aug 2024 00:08:17 +0000 (UTC) Authentication-Results: imf29.hostedemail.com; dkim=pass header.d=kernel.org header.s=k20201202 header.b=UMT+LlkR; spf=pass (imf29.hostedemail.com: domain of dakr@kernel.org designates 145.40.73.55 as permitted sender) smtp.mailfrom=dakr@kernel.org; dmarc=pass (policy=none) header.from=kernel.org ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1722470842; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-type: content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=EMIh51YGiTqxs0wjeSGkI2mLiiBxT82IBTGi6t1uFkI=; b=iKJEkgXS49vzJR+hz+Qv4LvzUbXPClv/T3odYnELb6STOzykASXObZXru7Wx8SYHprfVw1 wZBr7Ev/ogzaoPVwuoboyU7TlCPs3fTCzyrs4JUVfUJzMg7l2W6DQDPfU+Qc42Xw4dFauf wnd/VTLRds2Rsolqq0HEhhiOs9MoqPs= ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1722470842; a=rsa-sha256; cv=none; b=uNcxzPLhN9xFXbi6X0mfxoDwQMW0xEolTFNCGvY/H4cYZiDc/3E3i7ThzxlZIzPJXWs1fK jsvwXk6bMKtQHB4BNeQhQJUN0pahs0375JEf7xJ5jTBAh7vQS9bMMEB/2K042p7UPE029/ H9X/hqIcF/QhrFF8jIHemm+t0hxjwqg= ARC-Authentication-Results: i=1; imf29.hostedemail.com; dkim=pass header.d=kernel.org header.s=k20201202 header.b=UMT+LlkR; spf=pass (imf29.hostedemail.com: domain of dakr@kernel.org designates 145.40.73.55 as permitted sender) smtp.mailfrom=dakr@kernel.org; dmarc=pass (policy=none) header.from=kernel.org Received: from smtp.kernel.org (transwarp.subspace.kernel.org [100.75.92.58]) by sin.source.kernel.org (Postfix) with ESMTP id 8D4F9CE1846; Thu, 1 Aug 2024 00:08:15 +0000 (UTC) Received: by smtp.kernel.org (Postfix) with ESMTPSA id CEB8BC4AF0F; Thu, 1 Aug 2024 00:08:09 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1722470894; bh=qJH0b+zT7Zd9g/zzdC5BDkCk/Fs04Tglg+wahllGbls=; h=From:To:Cc:Subject:Date:In-Reply-To:References:From; b=UMT+LlkRiSD0Es7ekiX8WZrbf5T1T9+elhxsrIKw0Gde7zOp+HWpXyuYLRKzIaEWh SudV2hR/kX64WlvlQ0EG7HlvjI77NayAtDzOryv2DLwVFDMhBt01vvDnUN3ijhrTC0 zgMEUUQnkEIvEZW7iEvNL8+FTpZLTSBtMHrBPWc10Ht8NmjYKQE8CzlrvH4h/f7/+b Ki37Lqc1yp7v1zebkeFdPMjeyjMBiH06o19/gpplvfV8j+7IdexsqmHJjKpR6cO54v e0PtuTE3KoRJS4lC/5IwGiww19Jrtcu51+5L2otyzjfXTKEprkgKgndmAfpBAbq2fy L/WLjffZdjbmQ== From: Danilo Krummrich To: 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, aliceryhl@google.com, akpm@linux-foundation.org Cc: 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, Danilo Krummrich Subject: [PATCH v3 15/25] rust: alloc: implement kernel `Vec` type Date: Thu, 1 Aug 2024 02:02:14 +0200 Message-ID: <20240801000641.1882-16-dakr@kernel.org> X-Mailer: git-send-email 2.45.2 In-Reply-To: <20240801000641.1882-1-dakr@kernel.org> References: <20240801000641.1882-1-dakr@kernel.org> MIME-Version: 1.0 X-Rspam-User: X-Rspamd-Server: rspam04 X-Rspamd-Queue-Id: 52E18120025 X-Stat-Signature: h66gwi57oys5os7i9phh1aowix9fzehr X-HE-Tag: 1722470897-268403 X-HE-Meta: U2FsdGVkX19fzGhgrsz/GJTC0Ttr6Iu26X84r7FvCoYnadFOU1vlZwljay4mVcIR8ZIAbDmW8ULOC8vFfgyaidX3zX/UpDS4KSMG/+lcU8JAp94YRB26JsWkMaWPzqkcckw3pTdlgAg9VEoAgKskc7+bfDaPDteg7yKpdX59rLkBDAY3xy2ph8LYITglzeLNXZM3H063ETnydna5DeQCzjgUJrbY3VvcDdGarmhm575XyxzQqyJiri31MoFsqrR/hegtjlp9wpbJWapqCodqKC9UV0OctHSKYIHvL9HMSjmlPoT4LGgjVq8jkNHT4srAS0apKmWAeII6fPFQWdExfV5G05rMPgzIxvNHngK3E5BdzEtGKUSptOVhhb249X1LHmUhO2LQTKsRFMtNS2P2/kxKermOLm4ApHvgJq193WgWm1+DdUl3zjf5euJbCpiavhiPCeFWgtmSmzeXvo0yE7jfE+YmxdtJ4wQajHBGQaKoZEbkluGS5/wNsiozOAwofmd+nc27NCazYc0We/+w0+X9rrr9Wwq2I+9uh13y4Jxe/uTnOe2Cxi63U1b0wmcze8Rff8wbYt8Wpx7b8o5hl+O+qeHxOv6ndRQskmGGVvgKhQHzjoqsJBJsaVxRnnUUdfaonCW5Gl7cTcU8A6spkvaofiPJVzCgCZJhMzhclbqwWADzX5Adj/yNNv4vAohljqdjjp43DkUj7HUtScwTP87a0JUTuKIJ6e/NpfCaJRl9xZ6guyZSKrkyJnZY2sRkAydw+c/iB5Iks6OXPyfgWe8yspZOG0Lmr9TmBT6w6Ztd1ibSP4rZ1L2XY7QbQUiDwy/LmxQ08uemWacCivOHfVA6M3DIw4xOFKDcon7W0ALB7s5kC6sfYO62Pimu6eBPyyqSnzpx+DymoROCzDtCl3MgHfv6V6JTylLyB6LZfJi77OZyKhRxIEFlrl9xYPG9QQJOc5Pa6bXTsjgGjR3 5cy7YnTM ZlYPyphU9tfKLtKck8fv7SEEvydVYURGap6K4g9aon7xjoPnZgWbVJVDkW3jOpBEjydwvY622uhAmh5UiPTCNNc5rabToUmPcWWFGth1K7Noei4NyjAzI78fhzOYo+WppHNzbkeCOGnR8uCB4SXcNW0b4jJNMYnIEZlihDVRapwrJ+X6WwZOY8avASaloSBl6Bp/gdHXklQpyrx8JQQGA76IwWu+wQMN966WI7+39ijGe0vUPhdVGJ+tuM6wWuxYJWcO7mlFQPgWX4dI3551OI9Zht3hVt4KZ7d6eBwVQObjR+JPuAYI2+HWqr9yywwpTgbuNpIBUa+9USOezM6UrgUtU7Q== X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: `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 { + let len = b.len(); + unsafe { + let ptr = 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 = 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([$($x),+], GFP_KERNEL) { + Ok(b) => Ok($crate::alloc::KBox::into_vec(b)), + 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`. +/// +/// 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. +/// +/// 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 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` 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 +/// +/// 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 pointer. +/// +/// The length of the vector always represents the exact number of elements 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 for 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 return usize::MAX in that case. + /// + /// # Safety + /// + /// `cap` must be in the `0..=isize::MAX` range. + cap: usize, + len: usize, + _p: PhantomData, +} + +/// Type alias for `Vec` with a `Kmalloc` allocator. +/// +/// # Examples +/// +/// ``` +/// let mut v = KVec::new(); +/// v.push(1, GFP_KERNEL)?; +/// assert_eq!(&v, &[1]); +/// +/// # Ok::<(), Error>(()) +/// ``` +pub type KVec = Vec; + +/// Type alias for `Vec` with a `Vmalloc` allocator. +/// +/// # Examples +/// +/// ``` +/// let mut v = VVec::new(); +/// v.push(1, GFP_KERNEL)?; +/// assert_eq!(&v, &[1]); +/// +/// # Ok::<(), Error>(()) +/// ``` +pub type VVec = Vec; + +/// Type alias for `Vec` with a `KVmalloc` allocator. +/// +/// # Examples +/// +/// ``` +/// let mut v = KVVec::new(); +/// v.push(1, GFP_KERNEL)?; +/// assert_eq!(&v, &[1]); +/// +/// # Ok::<(), Error>(()) +/// ``` +pub type KVVec = Vec; + +impl Vec +where + A: Allocator, +{ + #[inline] + fn is_zst() -> bool { + core::mem::size_of::() == 0 + } + + /// Returns the total number of elements the vector can hold without + /// reallocating. + pub fn capacity(&self) -> usize { + if Self::is_zst() { + usize::MAX + } else { + self.cap + } + } + + /// 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 = 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 = KVec::new(); + /// assert!(v.is_empty()); + /// + /// v.push(1, GFP_KERNEL); + /// assert!(!v.is_empty()); + /// ``` + #[inline] + pub fn is_empty(&self) -> bool { + self.len() == 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 slice 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, + self.capacity() - self.len, + ) + } + } + + /// 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)?; + let s = 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 <= 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::::with_capacity(20, GFP_KERNEL)?; + /// + /// assert!(v.capacity() >= 20); + /// # Ok::<(), Error>(()) + /// ``` + pub fn with_capacity(capacity: usize, flags: Flags) -> Result { + 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, + { + 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 entries, so it is safe to increase + // the length by the same amount. We also know that the new length is <= 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 capacity, and an allocator. + /// + /// # Safety + /// + /// This is highly unsafe, due to the number of invariants that aren’t checked: + /// + /// - `ptr` must be currently allocated via the given allocator `A`. + /// - `T` needs to have the same alignment as what `ptr` was allocated with. (`T` having a less + /// strict alignment is not sufficient, the alignment really needs to be equal to satisfy the + /// `dealloc` requirement that memory must be allocated and deallocated with the same layout.) + /// - The size of `T` times the `capacity` (i.e. the allocated size 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 values 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 = 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>(()) + /// ``` + 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 { 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 = ManuallyDrop::new(self); + let len = me.len(); + let capacity = me.capacity(); + let ptr = me.as_mut_ptr(); + (ptr, len, capacity) + } + + /// Ensures that the capacity exceeds the length by at least `additional` elements. + /// + /// # Examples + /// + /// ``` + /// let mut v = KVec::new(); + /// v.push(1, GFP_KERNEL)?; + /// + /// v.reserve(10, GFP_KERNEL)?; + /// let cap = v.capacity(); + /// assert!(cap >= 10); + /// + /// v.reserve(10, GFP_KERNEL)?; + /// let new_cap = v.capacity(); + /// assert_eq!(new_cap, cap); + /// + /// # Ok::<(), Error>(()) + /// ``` + pub fn reserve(&mut self, additional: usize, flags: Flags) -> Result<(), AllocError> { + let len = self.len(); + let cap = self.capacity(); + + if cap - len >= 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 <= `isize::MAX` because `Layout::array` fails if the resulting byte size + // is greater than `isize::MAX`. So the multiplication by two won't overflow. + let new_cap = core::cmp::max(cap * 2, len.checked_add(additional).ok_or(AllocError)?); + let layout = core::alloc::Layout::array::(new_cap).map_err(|_| AllocError)?; + + // We need to make sure that `ptr` is either NULL or comes from a previous call to + // `realloc_flags`. A `Vec`'s `ptr` value is not guaranteed 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 = if cap == 0 { + None + } else { + Some(self.ptr.as_non_null().cast()) + }; + + // SAFETY: `ptr` is valid because it's either `None` or comes from a previous call to + // `A::realloc`. We also verified that the type is not a ZST. + let ptr = unsafe { A::realloc(ptr, layout, flags)? }; + + self.ptr = ptr.cast().into(); + self.cap = 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 = self.spare_capacity_mut(); + + for i in 0..spare.len() - 1 { + spare[i].write(value.clone()); + } + + // We can write the last element directly without cloning needlessly + spare[spare.len() - 1].write(value); + + // SAFETY: `self.reserve` not bailing out with an error guarantees 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 `value`. + pub fn from_elem(value: T, n: usize, flags: Flags) -> Result { + let mut v = 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, before 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 == 0` we never allocated any memory in the first place. + if self.cap != 0 { + // SAFETY: `self.ptr` was previously allocated with `A`. + unsafe { A::free(self.ptr.as_non_null().cast()) }; + } + } +} + +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 = [T]; + + #[inline] + fn deref(&self) -> &[T] { + // SAFETY: The memory behind `self.as_ptr()` is guaranteed to 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 to contain `self.len` + // initialized elements of type `T`. + unsafe { slice::from_raw_parts_mut(self.as_mut_ptr(), self.len) } + } +} + +impl Eq for Vec where A: Allocator {} + +impl, A> Index for Vec +where + A: Allocator, +{ + type Output = 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)?) => { + impl PartialEq<$rhs> for $lhs + where + T: PartialEq, + $($ty: $bound)? + { + #[inline] + fn eq(&self, other: &$rhs) -> bool { self[..] == other[..] } + } + } +} + +__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;