diff options
| author | Joonas Lahtinen <joonas.lahtinen@linux.intel.com> | 2026-05-12 11:16:35 +0300 |
|---|---|---|
| committer | Joonas Lahtinen <joonas.lahtinen@linux.intel.com> | 2026-05-12 11:16:35 +0300 |
| commit | 8edf8b09fc44990977b3fbcb708035b1740d0b7e (patch) | |
| tree | 0069cfbd4a05bd6c4c6057c3a36d0849f8a7414c /rust/kernel/alloc | |
| parent | 5ba54393dcd7adf75a9f39f5a933b1538349cad5 (diff) | |
| parent | f96538285cfdbb3acf5e3356e0bb88c38815790b (diff) | |
Merge drm/drm-next into drm-intel-gt-next
Backmerging to pull in commit 5401b9adebc9 ("i915: don't use
a vma that didn't match the context VM") to revert it.
Signed-off-by: Joonas Lahtinen <joonas.lahtinen@linux.intel.com>
Diffstat (limited to 'rust/kernel/alloc')
| -rw-r--r-- | rust/kernel/alloc/allocator.rs | 165 | ||||
| -rw-r--r-- | rust/kernel/alloc/allocator/iter.rs | 96 | ||||
| -rw-r--r-- | rust/kernel/alloc/allocator_test.rs | 124 | ||||
| -rw-r--r-- | rust/kernel/alloc/kbox.rs | 165 | ||||
| -rw-r--r-- | rust/kernel/alloc/kvec.rs | 291 | ||||
| -rw-r--r-- | rust/kernel/alloc/kvec/errors.rs | 17 | ||||
| -rw-r--r-- | rust/kernel/alloc/layout.rs | 7 |
7 files changed, 662 insertions, 203 deletions
diff --git a/rust/kernel/alloc/allocator.rs b/rust/kernel/alloc/allocator.rs index 2692cf90c948..63bfb91b3671 100644 --- a/rust/kernel/alloc/allocator.rs +++ b/rust/kernel/alloc/allocator.rs @@ -13,9 +13,14 @@ use core::alloc::Layout; use core::ptr; use core::ptr::NonNull; -use crate::alloc::{AllocError, Allocator}; +use crate::alloc::{AllocError, Allocator, NumaNode}; use crate::bindings; -use crate::pr_warn; +use crate::page; + +const ARCH_KMALLOC_MINALIGN: usize = bindings::ARCH_KMALLOC_MINALIGN; + +mod iter; +pub use self::iter::VmallocPageIter; /// The contiguous kernel allocator. /// @@ -45,20 +50,26 @@ pub struct KVmalloc; /// # Invariants /// -/// One of the following: `krealloc`, `vrealloc`, `kvrealloc`. +/// One of the following: `krealloc_node_align`, `vrealloc_node_align`, `kvrealloc_node_align`. struct ReallocFunc( - unsafe extern "C" fn(*const crate::ffi::c_void, usize, u32) -> *mut crate::ffi::c_void, + unsafe extern "C" fn( + *const crate::ffi::c_void, + usize, + crate::ffi::c_ulong, + u32, + crate::ffi::c_int, + ) -> *mut crate::ffi::c_void, ); impl ReallocFunc { - // INVARIANT: `krealloc` satisfies the type invariants. - const KREALLOC: Self = Self(bindings::krealloc); + // INVARIANT: `krealloc_node_align` satisfies the type invariants. + const KREALLOC: Self = Self(bindings::krealloc_node_align); - // INVARIANT: `vrealloc` satisfies the type invariants. - const VREALLOC: Self = Self(bindings::vrealloc); + // INVARIANT: `vrealloc_node_align` satisfies the type invariants. + const VREALLOC: Self = Self(bindings::vrealloc_node_align); - // INVARIANT: `kvrealloc` satisfies the type invariants. - const KVREALLOC: Self = Self(bindings::kvrealloc); + // INVARIANT: `kvrealloc_node_align` satisfies the type invariants. + const KVREALLOC: Self = Self(bindings::kvrealloc_node_align); /// # Safety /// @@ -76,6 +87,7 @@ impl ReallocFunc { layout: Layout, old_layout: Layout, flags: Flags, + nid: NumaNode, ) -> Result<NonNull<[u8]>, AllocError> { let size = layout.size(); let ptr = match ptr { @@ -99,7 +111,7 @@ impl ReallocFunc { // - Those functions provide the guarantees of this function. let raw_ptr = unsafe { // If `size == 0` and `ptr != NULL` the memory behind the pointer is freed. - self.0(ptr.cast(), size, flags.0).cast() + self.0(ptr.cast(), size, layout.align(), flags.0, nid.0).cast() }; let ptr = if size == 0 { @@ -128,17 +140,68 @@ impl Kmalloc { // - passing a pointer to a valid memory allocation is OK, // - `realloc` satisfies the guarantees, since `ReallocFunc::call` has the same. unsafe impl Allocator for Kmalloc { + const MIN_ALIGN: usize = ARCH_KMALLOC_MINALIGN; + #[inline] unsafe fn realloc( ptr: Option<NonNull<u8>>, layout: Layout, old_layout: Layout, flags: Flags, + nid: NumaNode, ) -> Result<NonNull<[u8]>, AllocError> { let layout = Kmalloc::aligned_layout(layout); // SAFETY: `ReallocFunc::call` has the same safety requirements as `Allocator::realloc`. - unsafe { ReallocFunc::KREALLOC.call(ptr, layout, old_layout, flags) } + unsafe { ReallocFunc::KREALLOC.call(ptr, layout, old_layout, flags, nid) } + } +} + +impl Vmalloc { + /// Convert a pointer to a [`Vmalloc`] allocation to a [`page::BorrowedPage`]. + /// + /// # Examples + /// + /// ``` + /// # use core::ptr::{NonNull, from_mut}; + /// # use kernel::{page, prelude::*}; + /// use kernel::alloc::allocator::Vmalloc; + /// + /// let mut vbox = VBox::<[u8; page::PAGE_SIZE]>::new_uninit(GFP_KERNEL)?; + /// + /// { + /// // SAFETY: By the type invariant of `Box` the inner pointer of `vbox` is non-null. + /// let ptr = unsafe { NonNull::new_unchecked(from_mut(&mut *vbox)) }; + /// + /// // SAFETY: + /// // `ptr` is a valid pointer to a `Vmalloc` allocation. + /// // `ptr` is valid for the entire lifetime of `page`. + /// let page = unsafe { Vmalloc::to_page(ptr.cast()) }; + /// + /// // SAFETY: There is no concurrent read or write to the same page. + /// unsafe { page.fill_zero_raw(0, page::PAGE_SIZE)? }; + /// } + /// # Ok::<(), Error>(()) + /// ``` + /// + /// # Safety + /// + /// - `ptr` must be a valid pointer to a [`Vmalloc`] allocation. + /// - `ptr` must remain valid for the entire duration of `'a`. + pub unsafe fn to_page<'a>(ptr: NonNull<u8>) -> page::BorrowedPage<'a> { + // SAFETY: `ptr` is a valid pointer to `Vmalloc` memory. + let page = unsafe { bindings::vmalloc_to_page(ptr.as_ptr().cast()) }; + + // SAFETY: `vmalloc_to_page` returns a valid pointer to a `struct page` for a valid pointer + // to `Vmalloc` memory. + let page = unsafe { NonNull::new_unchecked(page) }; + + // SAFETY: + // - `page` is a valid pointer to a `struct page`, given that by the safety requirements of + // this function `ptr` is a valid pointer to a `Vmalloc` allocation. + // - By the safety requirements of this function `ptr` is valid for the entire lifetime of + // `'a`. + unsafe { page::BorrowedPage::from_raw(page) } } } @@ -147,22 +210,19 @@ unsafe impl Allocator for Kmalloc { // - passing a pointer to a valid memory allocation is OK, // - `realloc` satisfies the guarantees, since `ReallocFunc::call` has the same. unsafe impl Allocator for Vmalloc { + const MIN_ALIGN: usize = kernel::page::PAGE_SIZE; + #[inline] unsafe fn realloc( ptr: Option<NonNull<u8>>, layout: Layout, old_layout: Layout, flags: Flags, + nid: NumaNode, ) -> Result<NonNull<[u8]>, AllocError> { - // TODO: Support alignments larger than PAGE_SIZE. - if layout.align() > bindings::PAGE_SIZE { - pr_warn!("Vmalloc does not support alignments larger than PAGE_SIZE yet.\n"); - return Err(AllocError); - } - // SAFETY: If not `None`, `ptr` is guaranteed to point to valid memory, which was previously // allocated with this `Allocator`. - unsafe { ReallocFunc::VREALLOC.call(ptr, layout, old_layout, flags) } + unsafe { ReallocFunc::VREALLOC.call(ptr, layout, old_layout, flags, nid) } } } @@ -171,25 +231,78 @@ unsafe impl Allocator for Vmalloc { // - passing a pointer to a valid memory allocation is OK, // - `realloc` satisfies the guarantees, since `ReallocFunc::call` has the same. unsafe impl Allocator for KVmalloc { + const MIN_ALIGN: usize = ARCH_KMALLOC_MINALIGN; + #[inline] unsafe fn realloc( ptr: Option<NonNull<u8>>, layout: Layout, old_layout: Layout, flags: Flags, + nid: NumaNode, ) -> Result<NonNull<[u8]>, AllocError> { // `KVmalloc` may use the `Kmalloc` backend, hence we have to enforce a `Kmalloc` // compatible layout. let layout = Kmalloc::aligned_layout(layout); - // TODO: Support alignments larger than PAGE_SIZE. - if layout.align() > bindings::PAGE_SIZE { - pr_warn!("KVmalloc does not support alignments larger than PAGE_SIZE yet.\n"); - return Err(AllocError); - } - // SAFETY: If not `None`, `ptr` is guaranteed to point to valid memory, which was previously // allocated with this `Allocator`. - unsafe { ReallocFunc::KVREALLOC.call(ptr, layout, old_layout, flags) } + unsafe { ReallocFunc::KVREALLOC.call(ptr, layout, old_layout, flags, nid) } + } +} + +#[macros::kunit_tests(rust_allocator)] +mod tests { + use super::*; + use core::mem::MaybeUninit; + use kernel::prelude::*; + + #[test] + fn test_alignment() -> Result { + const TEST_SIZE: usize = 1024; + const TEST_LARGE_ALIGN_SIZE: usize = kernel::page::PAGE_SIZE * 4; + + // These two structs are used to test allocating aligned memory. + // they don't need to be accessed, so they're marked as dead_code. + #[expect(dead_code)] + #[repr(align(128))] + struct Blob([u8; TEST_SIZE]); + #[expect(dead_code)] + #[repr(align(8192))] + struct LargeAlignBlob([u8; TEST_LARGE_ALIGN_SIZE]); + + struct TestAlign<T, A: Allocator>(Box<MaybeUninit<T>, A>); + impl<T, A: Allocator> TestAlign<T, A> { + fn new() -> Result<Self> { + Ok(Self(Box::<_, A>::new_uninit(GFP_KERNEL)?)) + } + + fn is_aligned_to(&self, align: usize) -> bool { + assert!(align.is_power_of_two()); + + let addr = self.0.as_ptr() as usize; + addr & (align - 1) == 0 + } + } + + let ta = TestAlign::<Blob, Kmalloc>::new()?; + assert!(ta.is_aligned_to(128)); + + let ta = TestAlign::<LargeAlignBlob, Kmalloc>::new()?; + assert!(ta.is_aligned_to(8192)); + + let ta = TestAlign::<Blob, Vmalloc>::new()?; + assert!(ta.is_aligned_to(128)); + + let ta = TestAlign::<LargeAlignBlob, Vmalloc>::new()?; + assert!(ta.is_aligned_to(8192)); + + let ta = TestAlign::<Blob, KVmalloc>::new()?; + assert!(ta.is_aligned_to(128)); + + let ta = TestAlign::<LargeAlignBlob, KVmalloc>::new()?; + assert!(ta.is_aligned_to(8192)); + + Ok(()) } } diff --git a/rust/kernel/alloc/allocator/iter.rs b/rust/kernel/alloc/allocator/iter.rs new file mode 100644 index 000000000000..e0a70b7a744a --- /dev/null +++ b/rust/kernel/alloc/allocator/iter.rs @@ -0,0 +1,96 @@ +// SPDX-License-Identifier: GPL-2.0 + +use super::Vmalloc; +use crate::page; +use core::marker::PhantomData; +use core::ptr::NonNull; + +/// An [`Iterator`] of [`page::BorrowedPage`] items owned by a [`Vmalloc`] allocation. +/// +/// # Guarantees +/// +/// The pages iterated by the [`Iterator`] appear in the order as they are mapped in the CPU's +/// virtual address space ascendingly. +/// +/// # Invariants +/// +/// - `buf` is a valid and [`page::PAGE_SIZE`] aligned pointer into a [`Vmalloc`] allocation. +/// - `size` is the number of bytes from `buf` until the end of the [`Vmalloc`] allocation `buf` +/// points to. +pub struct VmallocPageIter<'a> { + /// The base address of the [`Vmalloc`] buffer. + buf: NonNull<u8>, + /// The size of the buffer pointed to by `buf` in bytes. + size: usize, + /// The current page index of the [`Iterator`]. + index: usize, + _p: PhantomData<page::BorrowedPage<'a>>, +} + +impl<'a> Iterator for VmallocPageIter<'a> { + type Item = page::BorrowedPage<'a>; + + fn next(&mut self) -> Option<Self::Item> { + let offset = self.index.checked_mul(page::PAGE_SIZE)?; + + // Even though `self.size()` may be smaller than `Self::page_count() * page::PAGE_SIZE`, it + // is always a number between `(Self::page_count() - 1) * page::PAGE_SIZE` and + // `Self::page_count() * page::PAGE_SIZE`, hence the check below is sufficient. + if offset < self.size() { + self.index += 1; + } else { + return None; + } + + // SAFETY: `offset` is in the interval `[0, (self.page_count() - 1) * page::PAGE_SIZE]`, + // hence the resulting pointer is guaranteed to be within the same allocation. + let ptr = unsafe { self.buf.add(offset) }; + + // SAFETY: + // - `ptr` is a valid pointer to a `Vmalloc` allocation. + // - `ptr` is valid for the duration of `'a`. + Some(unsafe { Vmalloc::to_page(ptr) }) + } + + fn size_hint(&self) -> (usize, Option<usize>) { + let remaining = self.page_count().saturating_sub(self.index); + + (remaining, Some(remaining)) + } +} + +impl<'a> VmallocPageIter<'a> { + /// Creates a new [`VmallocPageIter`] instance. + /// + /// # Safety + /// + /// - `buf` must be a [`page::PAGE_SIZE`] aligned pointer into a [`Vmalloc`] allocation. + /// - `buf` must be valid for at least the lifetime of `'a`. + /// - `size` must be the number of bytes from `buf` until the end of the [`Vmalloc`] allocation + /// `buf` points to. + pub unsafe fn new(buf: NonNull<u8>, size: usize) -> Self { + // INVARIANT: By the safety requirements, `buf` is a valid and `page::PAGE_SIZE` aligned + // pointer into a [`Vmalloc`] allocation. + Self { + buf, + size, + index: 0, + _p: PhantomData, + } + } + + /// Returns the size of the backing [`Vmalloc`] allocation in bytes. + /// + /// Note that this is the size the [`Vmalloc`] allocation has been allocated with. Hence, this + /// number may be smaller than `[`Self::page_count`] * [`page::PAGE_SIZE`]`. + #[inline] + pub fn size(&self) -> usize { + self.size + } + + /// Returns the number of pages owned by the backing [`Vmalloc`] allocation. + #[inline] + pub fn page_count(&self) -> usize { + self.size().div_ceil(page::PAGE_SIZE) + } +} diff --git a/rust/kernel/alloc/allocator_test.rs b/rust/kernel/alloc/allocator_test.rs deleted file mode 100644 index 90dd987d40e4..000000000000 --- a/rust/kernel/alloc/allocator_test.rs +++ /dev/null @@ -1,124 +0,0 @@ -// SPDX-License-Identifier: GPL-2.0 - -//! So far the kernel's `Box` and `Vec` types can't be used by userspace test cases, since all users -//! of those types (e.g. `CString`) use kernel allocators for instantiation. -//! -//! In order to allow userspace test cases to make use of such types as well, implement the -//! `Cmalloc` allocator within the `allocator_test` module and type alias all kernel allocators to -//! `Cmalloc`. The `Cmalloc` allocator uses libc's `realloc()` function as allocator backend. - -#![allow(missing_docs)] - -use super::{flags::*, AllocError, Allocator, Flags}; -use core::alloc::Layout; -use core::cmp; -use core::ptr; -use core::ptr::NonNull; - -/// The userspace allocator based on libc. -pub struct Cmalloc; - -pub type Kmalloc = Cmalloc; -pub type Vmalloc = Kmalloc; -pub type KVmalloc = Kmalloc; - -impl Cmalloc { - /// Returns a [`Layout`] that makes [`Kmalloc`] fulfill the requested size and alignment of - /// `layout`. - pub fn aligned_layout(layout: Layout) -> Layout { - // Note that `layout.size()` (after padding) is guaranteed to be a multiple of - // `layout.align()` which together with the slab guarantees means that `Kmalloc` will return - // a properly aligned object (see comments in `kmalloc()` for more information). - layout.pad_to_align() - } -} - -extern "C" { - #[link_name = "aligned_alloc"] - fn libc_aligned_alloc(align: usize, size: usize) -> *mut crate::ffi::c_void; - - #[link_name = "free"] - fn libc_free(ptr: *mut crate::ffi::c_void); -} - -// SAFETY: -// - memory remains valid until it is explicitly freed, -// - passing a pointer to a valid memory allocation created by this `Allocator` is always OK, -// - `realloc` provides the guarantees as provided in the `# Guarantees` section. -unsafe impl Allocator for Cmalloc { - unsafe fn realloc( - ptr: Option<NonNull<u8>>, - layout: Layout, - old_layout: Layout, - flags: Flags, - ) -> Result<NonNull<[u8]>, AllocError> { - let src = match ptr { - Some(src) => { - if old_layout.size() == 0 { - ptr::null_mut() - } else { - src.as_ptr() - } - } - None => ptr::null_mut(), - }; - - if layout.size() == 0 { - // SAFETY: `src` is either NULL or was previously allocated with this `Allocator` - unsafe { libc_free(src.cast()) }; - - return Ok(NonNull::slice_from_raw_parts( - crate::alloc::dangling_from_layout(layout), - 0, - )); - } - - // ISO C (ISO/IEC 9899:2011) defines `aligned_alloc`: - // - // > The value of alignment shall be a valid alignment supported by the implementation - // [...]. - // - // As an example of the "supported by the implementation" requirement, POSIX.1-2001 (IEEE - // 1003.1-2001) defines `posix_memalign`: - // - // > The value of alignment shall be a power of two multiple of sizeof (void *). - // - // and POSIX-based implementations of `aligned_alloc` inherit this requirement. At the time - // of writing, this is known to be the case on macOS (but not in glibc). - // - // Satisfy the stricter requirement to avoid spurious test failures on some platforms. - let min_align = core::mem::size_of::<*const crate::ffi::c_void>(); - let layout = layout.align_to(min_align).map_err(|_| AllocError)?; - let layout = layout.pad_to_align(); - - // SAFETY: Returns either NULL or a pointer to a memory allocation that satisfies or - // exceeds the given size and alignment requirements. - let dst = unsafe { libc_aligned_alloc(layout.align(), layout.size()) }.cast::<u8>(); - let dst = NonNull::new(dst).ok_or(AllocError)?; - - if flags.contains(__GFP_ZERO) { - // SAFETY: The preceding calls to `libc_aligned_alloc` and `NonNull::new` - // guarantee that `dst` points to memory of at least `layout.size()` bytes. - unsafe { dst.as_ptr().write_bytes(0, layout.size()) }; - } - - if !src.is_null() { - // SAFETY: - // - `src` has previously been allocated with this `Allocator`; `dst` has just been - // newly allocated, hence the memory regions do not overlap. - // - both` src` and `dst` are properly aligned and valid for reads and writes - unsafe { - ptr::copy_nonoverlapping( - src, - dst.as_ptr(), - cmp::min(layout.size(), old_layout.size()), - ) - }; - } - - // SAFETY: `src` is either NULL or was previously allocated with this `Allocator` - unsafe { libc_free(src.cast()) }; - - Ok(NonNull::slice_from_raw_parts(dst, layout.size())) - } -} diff --git a/rust/kernel/alloc/kbox.rs b/rust/kernel/alloc/kbox.rs index 856d05aa60f1..bd6da02c7ab8 100644 --- a/rust/kernel/alloc/kbox.rs +++ b/rust/kernel/alloc/kbox.rs @@ -3,11 +3,10 @@ //! Implementation of [`Box`]. #[allow(unused_imports)] // Used in doc comments. -use super::allocator::{KVmalloc, Kmalloc, Vmalloc}; -use super::{AllocError, Allocator, Flags}; +use super::allocator::{KVmalloc, Kmalloc, Vmalloc, VmallocPageIter}; +use super::{AllocError, Allocator, Flags, NumaNode}; use core::alloc::Layout; use core::borrow::{Borrow, BorrowMut}; -use core::fmt; use core::marker::PhantomData; use core::mem::ManuallyDrop; use core::mem::MaybeUninit; @@ -17,7 +16,9 @@ use core::ptr::NonNull; use core::result::Result; use crate::ffi::c_void; +use crate::fmt; use crate::init::InPlaceInit; +use crate::page::AsPageIter; use crate::types::ForeignOwnable; use pin_init::{InPlaceWrite, Init, PinInit, ZeroableOption}; @@ -76,33 +77,8 @@ use pin_init::{InPlaceWrite, Init, PinInit, ZeroableOption}; /// `self.0` is always properly aligned and either points to memory allocated with `A` or, for /// zero-sized types, is a dangling, well aligned pointer. #[repr(transparent)] -#[cfg_attr(CONFIG_RUSTC_HAS_COERCE_POINTEE, derive(core::marker::CoercePointee))] -pub struct Box<#[cfg_attr(CONFIG_RUSTC_HAS_COERCE_POINTEE, pointee)] T: ?Sized, A: Allocator>( - NonNull<T>, - PhantomData<A>, -); - -// This is to allow coercion from `Box<T, A>` to `Box<U, A>` if `T` can be converted to the -// dynamically-sized type (DST) `U`. -#[cfg(not(CONFIG_RUSTC_HAS_COERCE_POINTEE))] -impl<T, U, A> core::ops::CoerceUnsized<Box<U, A>> for Box<T, A> -where - T: ?Sized + core::marker::Unsize<U>, - U: ?Sized, - A: Allocator, -{ -} - -// This is to allow `Box<U, A>` to be dispatched on when `Box<T, A>` can be coerced into `Box<U, -// A>`. -#[cfg(not(CONFIG_RUSTC_HAS_COERCE_POINTEE))] -impl<T, U, A> core::ops::DispatchFromDyn<Box<U, A>> for Box<T, A> -where - T: ?Sized + core::marker::Unsize<U>, - U: ?Sized, - A: Allocator, -{ -} +#[derive(core::marker::CoercePointee)] +pub struct Box<#[pointee] T: ?Sized, A: Allocator>(NonNull<T>, PhantomData<A>); /// Type alias for [`Box`] with a [`Kmalloc`] allocator. /// @@ -273,7 +249,7 @@ where /// ``` pub fn new_uninit(flags: Flags) -> Result<Box<MaybeUninit<T>, A>, AllocError> { let layout = Layout::new::<MaybeUninit<T>>(); - let ptr = A::alloc(layout, flags)?; + let ptr = A::alloc(layout, flags, NumaNode::NO_NODE)?; // INVARIANT: `ptr` is either a dangling pointer or points to memory allocated with `A`, // which is sufficient in size and alignment for storing a `T`. @@ -290,6 +266,83 @@ where Ok(Self::new(x, flags)?.into()) } + /// Construct a pinned slice of elements `Pin<Box<[T], A>>`. + /// + /// This is a convenient means for creation of e.g. slices of structrures containing spinlocks + /// or mutexes. + /// + /// # Examples + /// + /// ``` + /// use kernel::sync::{new_spinlock, SpinLock}; + /// + /// struct Inner { + /// a: u32, + /// b: u32, + /// } + /// + /// #[pin_data] + /// struct Example { + /// c: u32, + /// #[pin] + /// d: SpinLock<Inner>, + /// } + /// + /// impl Example { + /// fn new() -> impl PinInit<Self, Error> { + /// try_pin_init!(Self { + /// c: 10, + /// d <- new_spinlock!(Inner { a: 20, b: 30 }), + /// }) + /// } + /// } + /// + /// // Allocate a boxed slice of 10 `Example`s. + /// let s = KBox::pin_slice( + /// | _i | Example::new(), + /// 10, + /// GFP_KERNEL + /// )?; + /// + /// assert_eq!(s[5].c, 10); + /// assert_eq!(s[3].d.lock().a, 20); + /// # Ok::<(), Error>(()) + /// ``` + pub fn pin_slice<Func, Item, E>( + mut init: Func, + len: usize, + flags: Flags, + ) -> Result<Pin<Box<[T], A>>, E> + where + Func: FnMut(usize) -> Item, + Item: PinInit<T, E>, + E: From<AllocError>, + { + let mut buffer = super::Vec::<T, A>::with_capacity(len, flags)?; + for i in 0..len { + let ptr = buffer.spare_capacity_mut().as_mut_ptr().cast(); + // SAFETY: + // - `ptr` is a valid pointer to uninitialized memory. + // - `ptr` is not used if an error is returned. + // - `ptr` won't be moved until it is dropped, i.e. it is pinned. + unsafe { init(i).__pinned_init(ptr)? }; + + // SAFETY: + // - `i + 1 <= len`, hence we don't exceed the capacity, due to the call to + // `with_capacity()` above. + // - The new value at index buffer.len() + 1 is the only element being added here, and + // it has been initialized above by `init(i).__pinned_init(ptr)`. + unsafe { buffer.inc_len(1) }; + } + + let (ptr, _, _) = buffer.into_raw_parts(); + let slice = core::ptr::slice_from_raw_parts_mut(ptr, len); + + // SAFETY: `slice` points to an allocation allocated with `A` (`buffer`) and holds a valid + // `[T]`. + Ok(Pin::from(unsafe { Box::from_raw(slice) })) + } + /// Convert a [`Box<T,A>`] to a [`Pin<Box<T,A>>`]. If `T` does not implement /// [`Unpin`], then `x` will be pinned in memory and can't be moved. pub fn into_pin(this: Self) -> Pin<Self> { @@ -401,12 +454,17 @@ where } // SAFETY: The pointer returned by `into_foreign` comes from a well aligned -// pointer to `T`. +// pointer to `T` allocated by `A`. unsafe impl<T: 'static, A> ForeignOwnable for Box<T, A> where A: Allocator, { - const FOREIGN_ALIGN: usize = core::mem::align_of::<T>(); + const FOREIGN_ALIGN: usize = if core::mem::align_of::<T>() < A::MIN_ALIGN { + A::MIN_ALIGN + } else { + core::mem::align_of::<T>() + }; + type Borrowed<'a> = &'a T; type BorrowedMut<'a> = &'a mut T; @@ -435,12 +493,12 @@ where } // SAFETY: The pointer returned by `into_foreign` comes from a well aligned -// pointer to `T`. +// pointer to `T` allocated by `A`. unsafe impl<T: 'static, A> ForeignOwnable for Pin<Box<T, A>> where A: Allocator, { - const FOREIGN_ALIGN: usize = core::mem::align_of::<T>(); + const FOREIGN_ALIGN: usize = <Box<T, A> as ForeignOwnable>::FOREIGN_ALIGN; type Borrowed<'a> = Pin<&'a T>; type BorrowedMut<'a> = Pin<&'a mut T>; @@ -598,3 +656,40 @@ where unsafe { A::free(self.0.cast(), layout) }; } } + +/// # Examples +/// +/// ``` +/// # use kernel::prelude::*; +/// use kernel::alloc::allocator::VmallocPageIter; +/// use kernel::page::{AsPageIter, PAGE_SIZE}; +/// +/// let mut vbox = VBox::new((), GFP_KERNEL)?; +/// +/// assert!(vbox.page_iter().next().is_none()); +/// +/// let mut vbox = VBox::<[u8; PAGE_SIZE]>::new_uninit(GFP_KERNEL)?; +/// +/// let page = vbox.page_iter().next().expect("At least one page should be available.\n"); +/// +/// // SAFETY: There is no concurrent read or write to the same page. +/// unsafe { page.fill_zero_raw(0, PAGE_SIZE)? }; +/// # Ok::<(), Error>(()) +/// ``` +impl<T> AsPageIter for VBox<T> { + type Iter<'a> + = VmallocPageIter<'a> + where + T: 'a; + + fn page_iter(&mut self) -> Self::Iter<'_> { + let ptr = self.0.cast(); + let size = core::mem::size_of::<T>(); + + // SAFETY: + // - `ptr` is a valid pointer to the beginning of a `Vmalloc` allocation. + // - `ptr` is guaranteed to be valid for the lifetime of `'a`. + // - `size` is the size of the `Vmalloc` allocation `ptr` points to. + unsafe { VmallocPageIter::new(ptr, size) } + } +} diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs index 3c72e0bdddb8..6438385e4322 100644 --- a/rust/kernel/alloc/kvec.rs +++ b/rust/kernel/alloc/kvec.rs @@ -3,13 +3,19 @@ //! Implementation of [`Vec`]. use super::{ - allocator::{KVmalloc, Kmalloc, Vmalloc}, + allocator::{KVmalloc, Kmalloc, Vmalloc, VmallocPageIter}, layout::ArrayLayout, - AllocError, Allocator, Box, Flags, + AllocError, Allocator, Box, Flags, NumaNode, +}; +use crate::{ + fmt, + page::{ + AsPageIter, + PAGE_SIZE, // + }, }; use core::{ borrow::{Borrow, BorrowMut}, - fmt, marker::PhantomData, mem::{ManuallyDrop, MaybeUninit}, ops::Deref, @@ -175,7 +181,7 @@ where /// Returns the number of elements that can be stored within the vector without allocating /// additional memory. - pub fn capacity(&self) -> usize { + pub const fn capacity(&self) -> usize { if const { Self::is_zst() } { usize::MAX } else { @@ -185,7 +191,7 @@ where /// Returns the number of elements stored within the vector. #[inline] - pub fn len(&self) -> usize { + pub const fn len(&self) -> usize { self.len } @@ -196,7 +202,7 @@ where /// - `additional` must be less than or equal to `self.capacity - self.len`. /// - All elements within the interval [`self.len`,`self.len + additional`) must be initialized. #[inline] - pub unsafe fn inc_len(&mut self, additional: usize) { + pub const unsafe fn inc_len(&mut self, additional: usize) { // Guaranteed by the type invariant to never underflow. debug_assert!(additional <= self.capacity() - self.len()); // INVARIANT: By the safety requirements of this method this represents the exact number of @@ -224,6 +230,16 @@ where } /// Returns a slice of the entire vector. + /// + /// # Examples + /// + /// ``` + /// let mut v = KVec::new(); + /// v.push(1, GFP_KERNEL)?; + /// v.push(2, GFP_KERNEL)?; + /// assert_eq!(v.as_slice(), &[1, 2]); + /// # Ok::<(), Error>(()) + /// ``` #[inline] pub fn as_slice(&self) -> &[T] { self @@ -245,7 +261,7 @@ where /// Returns a raw pointer to the vector's backing buffer, or, if `T` is a ZST, a dangling raw /// pointer. #[inline] - pub fn as_ptr(&self) -> *const T { + pub const fn as_ptr(&self) -> *const T { self.ptr.as_ptr() } @@ -261,7 +277,7 @@ where /// assert!(!v.is_empty()); /// ``` #[inline] - pub fn is_empty(&self) -> bool { + pub const fn is_empty(&self) -> bool { self.len() == 0 } @@ -634,6 +650,7 @@ where layout.into(), self.layout.into(), flags, + NumaNode::NO_NODE, )? }; @@ -720,6 +737,115 @@ where self.truncate(num_kept); } } +// TODO: This is a temporary KVVec-specific implementation. It should be replaced with a generic +// `shrink_to()` for `impl<T, A: Allocator> Vec<T, A>` that uses `A::realloc()` once the +// underlying allocators properly support shrinking via realloc. +impl<T> Vec<T, KVmalloc> { + /// Shrinks the capacity of the vector with a lower bound. + /// + /// The capacity will remain at least as large as both the length and the supplied value. + /// If the current capacity is less than the lower limit, this is a no-op. + /// + /// For `kmalloc` allocations, this delegates to `realloc()`, which decides whether + /// shrinking is worthwhile. For `vmalloc` allocations, shrinking only occurs if the + /// operation would free at least one page of memory, and performs a deep copy since + /// `vrealloc` does not yet support in-place shrinking. + /// + /// # Examples + /// + /// ``` + /// // Allocate enough capacity to span multiple pages. + /// let elements_per_page = kernel::page::PAGE_SIZE / core::mem::size_of::<u32>(); + /// let mut v = KVVec::with_capacity(elements_per_page * 4, GFP_KERNEL)?; + /// v.push(1, GFP_KERNEL)?; + /// v.push(2, GFP_KERNEL)?; + /// + /// v.shrink_to(0, GFP_KERNEL)?; + /// # Ok::<(), Error>(()) + /// ``` + pub fn shrink_to(&mut self, min_capacity: usize, flags: Flags) -> Result<(), AllocError> { + let target_cap = core::cmp::max(self.len(), min_capacity); + + if self.capacity() <= target_cap { + return Ok(()); + } + + if Self::is_zst() { + return Ok(()); + } + + // For kmalloc allocations, delegate to realloc() and let the allocator decide + // whether shrinking is worthwhile. + // + // SAFETY: `self.ptr` points to a valid `KVmalloc` allocation. + if !unsafe { bindings::is_vmalloc_addr(self.ptr.as_ptr().cast()) } { + let new_layout = ArrayLayout::<T>::new(target_cap).map_err(|_| AllocError)?; + + // SAFETY: + // - `self.ptr` is valid and was previously allocated with `KVmalloc`. + // - `self.layout` matches the `ArrayLayout` of the preceding allocation. + let ptr = unsafe { + KVmalloc::realloc( + Some(self.ptr.cast()), + new_layout.into(), + self.layout.into(), + flags, + NumaNode::NO_NODE, + )? + }; + + self.ptr = ptr.cast(); + self.layout = new_layout; + return Ok(()); + } + + // Only shrink if we would free at least one page. + let current_size = self.capacity() * core::mem::size_of::<T>(); + let target_size = target_cap * core::mem::size_of::<T>(); + let current_pages = current_size.div_ceil(PAGE_SIZE); + let target_pages = target_size.div_ceil(PAGE_SIZE); + + if current_pages <= target_pages { + return Ok(()); + } + + if target_cap == 0 { + if !self.layout.is_empty() { + // SAFETY: + // - `self.ptr` was previously allocated with `KVmalloc`. + // - `self.layout` matches the `ArrayLayout` of the preceding allocation. + unsafe { KVmalloc::free(self.ptr.cast(), self.layout.into()) }; + } + self.ptr = NonNull::dangling(); + self.layout = ArrayLayout::empty(); + return Ok(()); + } + + // SAFETY: `target_cap <= self.capacity()` and original capacity was valid. + let new_layout = unsafe { ArrayLayout::<T>::new_unchecked(target_cap) }; + + let new_ptr = KVmalloc::alloc(new_layout.into(), flags, NumaNode::NO_NODE)?; + + // SAFETY: + // - `self.as_ptr()` is valid for reads of `self.len()` elements of `T`. + // - `new_ptr` is valid for writes of at least `target_cap >= self.len()` elements. + // - The two allocations do not overlap since `new_ptr` is freshly allocated. + // - Both pointers are properly aligned for `T`. + unsafe { + ptr::copy_nonoverlapping(self.as_ptr(), new_ptr.as_ptr().cast::<T>(), self.len()) + }; + + // SAFETY: + // - `self.ptr` was previously allocated with `KVmalloc`. + // - `self.layout` matches the `ArrayLayout` of the preceding allocation. + unsafe { KVmalloc::free(self.ptr.cast(), self.layout.into()) }; + + self.ptr = new_ptr.cast::<T>(); + self.layout = new_layout; + + Ok(()) + } +} impl<T: Clone, A: Allocator> Vec<T, A> { /// Extend the vector by `n` clones of `value`. @@ -1017,6 +1143,43 @@ where } } +/// # Examples +/// +/// ``` +/// # use kernel::prelude::*; +/// use kernel::alloc::allocator::VmallocPageIter; +/// use kernel::page::{AsPageIter, PAGE_SIZE}; +/// +/// let mut vec = VVec::<u8>::new(); +/// +/// assert!(vec.page_iter().next().is_none()); +/// +/// vec.reserve(PAGE_SIZE, GFP_KERNEL)?; +/// +/// let page = vec.page_iter().next().expect("At least one page should be available.\n"); +/// +/// // SAFETY: There is no concurrent read or write to the same page. +/// unsafe { page.fill_zero_raw(0, PAGE_SIZE)? }; +/// # Ok::<(), Error>(()) +/// ``` +impl<T> AsPageIter for VVec<T> { + type Iter<'a> + = VmallocPageIter<'a> + where + T: 'a; + + fn page_iter(&mut self) -> Self::Iter<'_> { + let ptr = self.ptr.cast(); + let size = self.layout.size(); + + // SAFETY: + // - `ptr` is a valid pointer to the beginning of a `Vmalloc` allocation. + // - `ptr` is guaranteed to be valid for the lifetime of `'a`. + // - `size` is the size of the `Vmalloc` allocation `ptr` points to. + unsafe { VmallocPageIter::new(ptr, size) } + } +} + /// An [`Iterator`] implementation for [`Vec`] that moves elements out of a vector. /// /// This structure is created by the [`Vec::into_iter`] method on [`Vec`] (provided by the @@ -1111,7 +1274,13 @@ where // the type invariant to be smaller than `cap`. Depending on `realloc` this operation // may shrink the buffer or leave it as it is. ptr = match unsafe { - A::realloc(Some(buf.cast()), layout.into(), old_layout.into(), flags) + A::realloc( + Some(buf.cast()), + layout.into(), + old_layout.into(), + flags, + NumaNode::NO_NODE, + ) } { // If we fail to shrink, which likely can't even happen, continue with the existing // buffer. @@ -1294,7 +1463,7 @@ impl<'vec, T> Drop for DrainAll<'vec, T> { } } -#[macros::kunit_tests(rust_kvec_kunit)] +#[macros::kunit_tests(rust_kvec)] mod tests { use super::*; use crate::prelude::*; @@ -1341,4 +1510,106 @@ mod tests { func.push_within_capacity(false).unwrap(); } } + + #[test] + fn test_kvvec_shrink_to() { + use crate::page::PAGE_SIZE; + + // Create a vector with capacity spanning multiple pages. + let mut v = KVVec::<u8>::with_capacity(PAGE_SIZE * 4, GFP_KERNEL).unwrap(); + + // Add a few elements. + v.push(1, GFP_KERNEL).unwrap(); + v.push(2, GFP_KERNEL).unwrap(); + v.push(3, GFP_KERNEL).unwrap(); + + let initial_capacity = v.capacity(); + assert!(initial_capacity >= PAGE_SIZE * 4); + + // Shrink to a capacity that would free at least one page. + v.shrink_to(PAGE_SIZE, GFP_KERNEL).unwrap(); + + // Capacity should have been reduced. + assert!(v.capacity() < initial_capacity); + assert!(v.capacity() >= PAGE_SIZE); + + // Elements should be preserved. + assert_eq!(v.len(), 3); + assert_eq!(v[0], 1); + assert_eq!(v[1], 2); + assert_eq!(v[2], 3); + + // Shrink to zero (should shrink to len). + v.shrink_to(0, GFP_KERNEL).unwrap(); + + // Capacity should be at least the length. + assert!(v.capacity() >= v.len()); + + // Elements should still be preserved. + assert_eq!(v.len(), 3); + assert_eq!(v[0], 1); + assert_eq!(v[1], 2); + assert_eq!(v[2], 3); + } + + #[test] + fn test_kvvec_shrink_to_empty() { + use crate::page::PAGE_SIZE; + + // Create a vector with large capacity but no elements. + let mut v = KVVec::<u8>::with_capacity(PAGE_SIZE * 4, GFP_KERNEL).unwrap(); + + assert!(v.is_empty()); + + // Shrink empty vector to zero. + v.shrink_to(0, GFP_KERNEL).unwrap(); + + // Should have freed the allocation. + assert_eq!(v.capacity(), 0); + assert!(v.is_empty()); + } + + #[test] + fn test_kvvec_shrink_to_no_op() { + use crate::page::PAGE_SIZE; + + // Create a small vector. + let mut v = KVVec::<u8>::with_capacity(PAGE_SIZE, GFP_KERNEL).unwrap(); + v.push(1, GFP_KERNEL).unwrap(); + + let capacity_before = v.capacity(); + + // Try to shrink to a capacity larger than current - should be no-op. + v.shrink_to(capacity_before + 100, GFP_KERNEL).unwrap(); + + assert_eq!(v.capacity(), capacity_before); + assert_eq!(v.len(), 1); + assert_eq!(v[0], 1); + } + + #[test] + fn test_kvvec_shrink_to_respects_min_capacity() { + use crate::page::PAGE_SIZE; + + // Create a vector with large capacity. + let mut v = KVVec::<u8>::with_capacity(PAGE_SIZE * 4, GFP_KERNEL).unwrap(); + + // Add some elements. + for i in 0..10u8 { + v.push(i, GFP_KERNEL).unwrap(); + } + + // Shrink to a min_capacity larger than length. + let min_cap = PAGE_SIZE * 2; + v.shrink_to(min_cap, GFP_KERNEL).unwrap(); + + // Capacity should be at least min_capacity. + assert!(v.capacity() >= min_cap); + + // All elements preserved. + assert_eq!(v.len(), 10); + for i in 0..10u8 { + assert_eq!(v[i as usize], i); + } + } } diff --git a/rust/kernel/alloc/kvec/errors.rs b/rust/kernel/alloc/kvec/errors.rs index 348b8d27e102..985c5f2c3962 100644 --- a/rust/kernel/alloc/kvec/errors.rs +++ b/rust/kernel/alloc/kvec/errors.rs @@ -2,19 +2,20 @@ //! Errors for the [`Vec`] type. -use core::fmt::{self, Debug, Formatter}; +use kernel::fmt; use kernel::prelude::*; /// Error type for [`Vec::push_within_capacity`]. pub struct PushError<T>(pub T); -impl<T> Debug for PushError<T> { - fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result { +impl<T> fmt::Debug for PushError<T> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { write!(f, "Not enough capacity") } } impl<T> From<PushError<T>> for Error { + #[inline] fn from(_: PushError<T>) -> Error { // Returning ENOMEM isn't appropriate because the system is not out of memory. The vector // is just full and we are refusing to resize it. @@ -25,13 +26,14 @@ impl<T> From<PushError<T>> for Error { /// Error type for [`Vec::remove`]. pub struct RemoveError; -impl Debug for RemoveError { - fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result { +impl fmt::Debug for RemoveError { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { write!(f, "Index out of bounds") } } impl From<RemoveError> for Error { + #[inline] fn from(_: RemoveError) -> Error { EINVAL } @@ -45,8 +47,8 @@ pub enum InsertError<T> { OutOfCapacity(T), } -impl<T> Debug for InsertError<T> { - fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result { +impl<T> fmt::Debug for InsertError<T> { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { match self { InsertError::IndexOutOfBounds(_) => write!(f, "Index out of bounds"), InsertError::OutOfCapacity(_) => write!(f, "Not enough capacity"), @@ -55,6 +57,7 @@ impl<T> Debug for InsertError<T> { } impl<T> From<InsertError<T>> for Error { + #[inline] fn from(_: InsertError<T>) -> Error { EINVAL } diff --git a/rust/kernel/alloc/layout.rs b/rust/kernel/alloc/layout.rs index 93ed514f7cc7..9f8be72feb7a 100644 --- a/rust/kernel/alloc/layout.rs +++ b/rust/kernel/alloc/layout.rs @@ -80,7 +80,7 @@ impl<T> ArrayLayout<T> { /// # Safety /// /// `len` must be a value, for which `len * size_of::<T>() <= isize::MAX` is true. - pub unsafe fn new_unchecked(len: usize) -> Self { + pub const unsafe fn new_unchecked(len: usize) -> Self { // INVARIANT: By the safety requirements of this function // `len * size_of::<T>() <= isize::MAX`. Self { @@ -98,6 +98,11 @@ impl<T> ArrayLayout<T> { pub const fn is_empty(&self) -> bool { self.len == 0 } + + /// Returns the size of the [`ArrayLayout`] in bytes. + pub const fn size(&self) -> usize { + self.len() * core::mem::size_of::<T>() + } } impl<T> From<ArrayLayout<T>> for Layout { |
