From 01db99b272318da75a1aa5a81f75adb9d32f676e Mon Sep 17 00:00:00 2001 From: Benno Lossin Date: Mon, 19 Aug 2024 11:24:35 +0000 Subject: rust: kernel: add `drop_contents` to `BoxExt` Sometimes (see [1]) it is necessary to drop the value inside of a `Box`, but retain the allocation. For example to reuse the allocation in the future. Introduce a new function `drop_contents` that turns a `Box` into `Box>` by dropping the value. Link: https://lore.kernel.org/rust-for-linux/20240418-b4-rbtree-v3-5-323e134390ce@google.com/ [1] Signed-off-by: Benno Lossin Reviewed-by: Boqun Feng Reviewed-by: Alice Ryhl Link: https://lore.kernel.org/r/20240819112415.99810-1-benno.lossin@proton.me Signed-off-by: Miguel Ojeda --- rust/kernel/alloc/box_ext.rs | 31 ++++++++++++++++++++++++++++++- 1 file changed, 30 insertions(+), 1 deletion(-) (limited to 'rust/kernel/alloc') diff --git a/rust/kernel/alloc/box_ext.rs b/rust/kernel/alloc/box_ext.rs index 829cb1c1cf9e..b68ade26a42d 100644 --- a/rust/kernel/alloc/box_ext.rs +++ b/rust/kernel/alloc/box_ext.rs @@ -4,7 +4,7 @@ use super::{AllocError, Flags}; use alloc::boxed::Box; -use core::mem::MaybeUninit; +use core::{mem::MaybeUninit, ptr, result::Result}; /// Extensions to [`Box`]. pub trait BoxExt: Sized { @@ -17,6 +17,22 @@ pub trait BoxExt: Sized { /// /// The allocation may fail, in which case an error is returned. fn new_uninit(flags: Flags) -> Result>, AllocError>; + + /// Drops the contents, but keeps the allocation. + /// + /// # Examples + /// + /// ``` + /// use kernel::alloc::{flags, box_ext::BoxExt}; + /// let value = Box::new([0; 32], flags::GFP_KERNEL)?; + /// assert_eq!(*value, [0; 32]); + /// let value = Box::drop_contents(value); + /// // Now we can re-use `value`: + /// let value = Box::write(value, [1; 32]); + /// assert_eq!(*value, [1; 32]); + /// # Ok::<(), Error>(()) + /// ``` + fn drop_contents(this: Self) -> Box>; } impl BoxExt for Box { @@ -53,4 +69,17 @@ impl BoxExt for Box { // zero-sized types, we use `NonNull::dangling`. Ok(unsafe { Box::from_raw(ptr) }) } + + fn drop_contents(this: Self) -> Box> { + let ptr = Box::into_raw(this); + // SAFETY: `ptr` is valid, because it came from `Box::into_raw`. + unsafe { ptr::drop_in_place(ptr) }; + + // CAST: `MaybeUninit` is a transparent wrapper of `T`. + let ptr = ptr.cast::>(); + + // SAFETY: `ptr` is valid for writes, because it came from `Box::into_raw` and it is valid for + // reads, since the pointer came from `Box::into_raw` and the type is `MaybeUninit`. + unsafe { Box::from_raw(ptr) } + } } -- cgit v1.2.3 From 0903b9e2a46cb6252a13d6b19d0502da9be191cf Mon Sep 17 00:00:00 2001 From: Jubilee Young Date: Thu, 22 Aug 2024 22:03:59 -0700 Subject: rust: alloc: eschew `Box>::write` Upstream Rust's libs-api team has consensus for stabilizing some of `feature(new_uninit)`, but not for `Box>::write`. Instead, we can use `MaybeUninit::write`, so Rust for Linux can drop the feature after stabilization. That will happen after merging, as the FCP has completed [1]. This is required before stabilization because remaining-unstable API will be divided into new features. This code doesn't know about those yet. It can't: they haven't landed, as the relevant PR is blocked on rustc's CI testing Rust-for-Linux without this patch. [ The PR has landed [2] and will be released in Rust 1.82.0 (expected on 2024-10-17), so we could conditionally enable the new unstable feature (`box_uninit_write` [3]) instead, but just for a single `unsafe` block it is probably not worth it. For the time being, I added it to the "nice to have" section of our unstable features list. - Miguel ] Link: https://github.com/rust-lang/rust/issues/63291#issuecomment-2183022955 [1] Link: https://github.com/rust-lang/rust/pull/129416 [2] Link: https://github.com/rust-lang/rust/issues/129397 [3] Signed-off-by: Jubilee Young Reviewed-by: Alice Ryhl Reviewed-by: Trevor Gross [ Reworded slightly. - Miguel ] Signed-off-by: Miguel Ojeda --- rust/kernel/alloc/box_ext.rs | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-) (limited to 'rust/kernel/alloc') diff --git a/rust/kernel/alloc/box_ext.rs b/rust/kernel/alloc/box_ext.rs index 829cb1c1cf9e..9f1c1c489189 100644 --- a/rust/kernel/alloc/box_ext.rs +++ b/rust/kernel/alloc/box_ext.rs @@ -21,8 +21,10 @@ pub trait BoxExt: Sized { impl BoxExt for Box { fn new(x: T, flags: Flags) -> Result { - let b = >::new_uninit(flags)?; - Ok(Box::write(b, x)) + let mut b = >::new_uninit(flags)?; + b.write(x); + // SAFETY: We just wrote to it. + Ok(unsafe { b.assume_init() }) } #[cfg(any(test, testlib))] -- cgit v1.2.3 From ab309b6e084c70a29f9fa3cee797572bd2340901 Mon Sep 17 00:00:00 2001 From: Miguel Ojeda Date: Wed, 4 Sep 2024 16:42:29 +0200 Subject: rust: avoid `box_uninit_write` feature Like commit 0903b9e2a46c ("rust: alloc: eschew `Box>::write`"), but for the new `rbtree` and `alloc` code. That is, `feature(new_uninit)` [1] got partially stabilized [2] for Rust 1.82.0 (expected to be released on 2024-10-17), but it did not include `Box>::write`, which got split into `feature(box_uninit_write)` [3]. To avoid relying on a new unstable feature, rewrite the `write` + `assume_init` pair manually. Link: https://github.com/rust-lang/rust/issues/63291 [1] Link: https://github.com/rust-lang/rust/pull/129401 [2] Link: https://github.com/rust-lang/rust/issues/129397 [3] Reviewed-by: Alice Ryhl Reviewed-by: Matt Gilbride Link: https://lore.kernel.org/r/20240904144229.18592-1-ojeda@kernel.org Signed-off-by: Miguel Ojeda --- rust/kernel/alloc/box_ext.rs | 6 ++++-- 1 file changed, 4 insertions(+), 2 deletions(-) (limited to 'rust/kernel/alloc') diff --git a/rust/kernel/alloc/box_ext.rs b/rust/kernel/alloc/box_ext.rs index b68ade26a42d..5b1550d620fd 100644 --- a/rust/kernel/alloc/box_ext.rs +++ b/rust/kernel/alloc/box_ext.rs @@ -26,9 +26,11 @@ pub trait BoxExt: Sized { /// use kernel::alloc::{flags, box_ext::BoxExt}; /// let value = Box::new([0; 32], flags::GFP_KERNEL)?; /// assert_eq!(*value, [0; 32]); - /// let value = Box::drop_contents(value); + /// let mut value = Box::drop_contents(value); /// // Now we can re-use `value`: - /// let value = Box::write(value, [1; 32]); + /// value.write([1; 32]); + /// // SAFETY: We just wrote to it. + /// let value = unsafe { value.assume_init() }; /// assert_eq!(*value, [1; 32]); /// # Ok::<(), Error>(()) /// ``` -- cgit v1.2.3 From db4f72c904cb116e2bf56afdd67fc5167a607a7b Mon Sep 17 00:00:00 2001 From: Miguel Ojeda Date: Wed, 4 Sep 2024 22:43:32 +0200 Subject: rust: enable `clippy::undocumented_unsafe_blocks` lint Checking that we are not missing any `// SAFETY` comments in our `unsafe` blocks is something we have wanted to do for a long time, as well as cleaning up the remaining cases that were not documented [1]. Back when Rust for Linux started, this was something that could have been done via a script, like Rust's `tidy`. Soon after, in Rust 1.58.0, Clippy implemented the `undocumented_unsafe_blocks` lint [2]. Even though the lint has a few false positives, e.g. in some cases where attributes appear between the comment and the `unsafe` block [3], there are workarounds and the lint seems quite usable already. Thus enable the lint now. We still have a few cases to clean up, so just allow those for the moment by writing a `TODO` comment -- some of those may be good candidates for new contributors. Link: https://github.com/Rust-for-Linux/linux/issues/351 [1] Link: https://rust-lang.github.io/rust-clippy/master/#/undocumented_unsafe_blocks [2] Link: https://github.com/rust-lang/rust-clippy/issues/13189 [3] Reviewed-by: Alice Ryhl Reviewed-by: Trevor Gross Tested-by: Gary Guo Reviewed-by: Gary Guo Link: https://lore.kernel.org/r/20240904204347.168520-5-ojeda@kernel.org Signed-off-by: Miguel Ojeda --- rust/kernel/alloc/allocator.rs | 2 ++ 1 file changed, 2 insertions(+) (limited to 'rust/kernel/alloc') diff --git a/rust/kernel/alloc/allocator.rs b/rust/kernel/alloc/allocator.rs index e6ea601f38c6..91216b36af69 100644 --- a/rust/kernel/alloc/allocator.rs +++ b/rust/kernel/alloc/allocator.rs @@ -31,6 +31,7 @@ pub(crate) unsafe fn krealloc_aligned(ptr: *mut u8, new_layout: Layout, flags: F unsafe { bindings::krealloc(ptr as *const core::ffi::c_void, size, flags.0) as *mut u8 } } +// SAFETY: TODO. unsafe impl GlobalAlloc for KernelAllocator { unsafe fn alloc(&self, layout: Layout) -> *mut u8 { // SAFETY: `ptr::null_mut()` is null and `layout` has a non-zero size by the function safety @@ -39,6 +40,7 @@ unsafe impl GlobalAlloc for KernelAllocator { } unsafe fn dealloc(&self, ptr: *mut u8, _layout: Layout) { + // SAFETY: TODO. unsafe { bindings::kfree(ptr as *const core::ffi::c_void); } -- cgit v1.2.3 From a654a6e09644266e38ac05415ef7737d299c4497 Mon Sep 17 00:00:00 2001 From: Danilo Krummrich Date: Fri, 4 Oct 2024 17:41:06 +0200 Subject: rust: alloc: separate `aligned_size` from `krealloc_aligned` Separate `aligned_size` from `krealloc_aligned`. Subsequent patches implement `Allocator` derivates, such as `Kmalloc`, that require `aligned_size` and replace the original `krealloc_aligned`. Reviewed-by: Alice Ryhl Reviewed-by: Benno Lossin Reviewed-by: Gary Guo Signed-off-by: Danilo Krummrich Link: https://lore.kernel.org/r/20241004154149.93856-3-dakr@kernel.org Signed-off-by: Miguel Ojeda --- rust/kernel/alloc/allocator.rs | 19 ++++++++++++------- 1 file changed, 12 insertions(+), 7 deletions(-) (limited to 'rust/kernel/alloc') diff --git a/rust/kernel/alloc/allocator.rs b/rust/kernel/alloc/allocator.rs index 91216b36af69..765f72d5bc21 100644 --- a/rust/kernel/alloc/allocator.rs +++ b/rust/kernel/alloc/allocator.rs @@ -8,6 +8,17 @@ use core::ptr; struct KernelAllocator; +/// Returns a proper size to alloc a new object aligned to `new_layout`'s alignment. +fn aligned_size(new_layout: Layout) -> usize { + // Customized layouts from `Layout::from_size_align()` can have size < align, so pad first. + let layout = new_layout.pad_to_align(); + + // Note that `layout.size()` (after padding) is guaranteed to be a multiple of `layout.align()` + // which together with the slab guarantees means the `krealloc` will return a properly aligned + // object (see comments in `kmalloc()` for more information). + layout.size() +} + /// Calls `krealloc` with a proper size to alloc a new object aligned to `new_layout`'s alignment. /// /// # Safety @@ -15,13 +26,7 @@ struct KernelAllocator; /// - `ptr` can be either null or a pointer which has been allocated by this allocator. /// - `new_layout` must have a non-zero size. pub(crate) unsafe fn krealloc_aligned(ptr: *mut u8, new_layout: Layout, flags: Flags) -> *mut u8 { - // Customized layouts from `Layout::from_size_align()` can have size < align, so pad first. - let layout = new_layout.pad_to_align(); - - // Note that `layout.size()` (after padding) is guaranteed to be a multiple of `layout.align()` - // which together with the slab guarantees means the `krealloc` will return a properly aligned - // object (see comments in `kmalloc()` for more information). - let size = layout.size(); + let size = aligned_size(new_layout); // SAFETY: // - `ptr` is either null or a pointer returned from a previous `k{re}alloc()` by the -- cgit v1.2.3 From 941e65531446c1eb5d573c5d30172117ebe96112 Mon Sep 17 00:00:00 2001 From: Danilo Krummrich Date: Fri, 4 Oct 2024 17:41:07 +0200 Subject: rust: alloc: rename `KernelAllocator` to `Kmalloc` Subsequent patches implement `Vmalloc` and `KVmalloc` allocators, hence align `KernelAllocator` to this naming scheme. Reviewed-by: Alice Ryhl Reviewed-by: Benno Lossin Reviewed-by: Gary Guo Signed-off-by: Danilo Krummrich Link: https://lore.kernel.org/r/20241004154149.93856-4-dakr@kernel.org Signed-off-by: Miguel Ojeda --- rust/kernel/alloc/allocator.rs | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'rust/kernel/alloc') diff --git a/rust/kernel/alloc/allocator.rs b/rust/kernel/alloc/allocator.rs index 765f72d5bc21..3b1c735ba409 100644 --- a/rust/kernel/alloc/allocator.rs +++ b/rust/kernel/alloc/allocator.rs @@ -6,7 +6,7 @@ use super::{flags::*, Flags}; use core::alloc::{GlobalAlloc, Layout}; use core::ptr; -struct KernelAllocator; +struct Kmalloc; /// Returns a proper size to alloc a new object aligned to `new_layout`'s alignment. fn aligned_size(new_layout: Layout) -> usize { @@ -37,7 +37,7 @@ pub(crate) unsafe fn krealloc_aligned(ptr: *mut u8, new_layout: Layout, flags: F } // SAFETY: TODO. -unsafe impl GlobalAlloc for KernelAllocator { +unsafe impl GlobalAlloc for Kmalloc { unsafe fn alloc(&self, layout: Layout) -> *mut u8 { // SAFETY: `ptr::null_mut()` is null and `layout` has a non-zero size by the function safety // requirement. @@ -74,7 +74,7 @@ unsafe impl GlobalAlloc for KernelAllocator { } #[global_allocator] -static ALLOCATOR: KernelAllocator = KernelAllocator; +static ALLOCATOR: Kmalloc = Kmalloc; // See . #[no_mangle] -- cgit v1.2.3 From 8a799831fc63c988eec90d334fdd68ff5f2c7eb5 Mon Sep 17 00:00:00 2001 From: Danilo Krummrich Date: Fri, 4 Oct 2024 17:41:08 +0200 Subject: rust: alloc: implement `ReallocFunc` `ReallocFunc` is an abstraction for the kernel's realloc derivates, such as `krealloc`, `vrealloc` and `kvrealloc`. All of the named functions share the same function signature and implement the same semantics. The `ReallocFunc` abstractions provides a generalized wrapper around those, to trivialize the implementation of `Kmalloc`, `Vmalloc` and `KVmalloc` in subsequent patches. Reviewed-by: Benno Lossin Reviewed-by: Gary Guo Signed-off-by: Danilo Krummrich Link: https://lore.kernel.org/r/20241004154149.93856-5-dakr@kernel.org [ Added temporary `allow(dead_code)` for `dangling_from_layout` to clean warning in `rusttest` target as discussed in the list (but it is needed earlier, i.e. in this patch already). Added colon. - Miguel ] Signed-off-by: Miguel Ojeda --- rust/kernel/alloc/allocator.rs | 70 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 70 insertions(+) (limited to 'rust/kernel/alloc') diff --git a/rust/kernel/alloc/allocator.rs b/rust/kernel/alloc/allocator.rs index 3b1c735ba409..9ed122401e8a 100644 --- a/rust/kernel/alloc/allocator.rs +++ b/rust/kernel/alloc/allocator.rs @@ -1,10 +1,20 @@ // SPDX-License-Identifier: GPL-2.0 //! Allocator support. +//! +//! Documentation for the kernel's memory allocators can found in the "Memory Allocation Guide" +//! linked below. For instance, this includes the concept of "get free page" (GFP) flags and the +//! typical application of the different kernel allocators. +//! +//! Reference: use super::{flags::*, Flags}; use core::alloc::{GlobalAlloc, Layout}; use core::ptr; +use core::ptr::NonNull; + +use crate::alloc::AllocError; +use crate::bindings; struct Kmalloc; @@ -36,6 +46,66 @@ pub(crate) unsafe fn krealloc_aligned(ptr: *mut u8, new_layout: Layout, flags: F unsafe { bindings::krealloc(ptr as *const core::ffi::c_void, size, flags.0) as *mut u8 } } +/// # Invariants +/// +/// One of the following: `krealloc`, `vrealloc`, `kvrealloc`. +struct ReallocFunc( + unsafe extern "C" fn(*const core::ffi::c_void, usize, u32) -> *mut core::ffi::c_void, +); + +#[expect(dead_code)] +impl ReallocFunc { + /// # Safety + /// + /// This method has the same safety requirements as [`Allocator::realloc`]. + /// + /// # Guarantees + /// + /// This method has the same guarantees as `Allocator::realloc`. Additionally + /// - it accepts any pointer to a valid memory allocation allocated by this function. + /// - memory allocated by this function remains valid until it is passed to this function. + unsafe fn call( + &self, + ptr: Option>, + layout: Layout, + old_layout: Layout, + flags: Flags, + ) -> Result, AllocError> { + let size = aligned_size(layout); + let ptr = match ptr { + Some(ptr) => { + if old_layout.size() == 0 { + ptr::null() + } else { + ptr.as_ptr() + } + } + None => ptr::null(), + }; + + // SAFETY: + // - `self.0` is one of `krealloc`, `vrealloc`, `kvrealloc` and thus only requires that + // `ptr` is NULL or valid. + // - `ptr` is either NULL or valid by the safety requirements of this function. + // + // GUARANTEE: + // - `self.0` is one of `krealloc`, `vrealloc`, `kvrealloc`. + // - 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() + }; + + let ptr = if size == 0 { + crate::alloc::dangling_from_layout(layout) + } else { + NonNull::new(raw_ptr).ok_or(AllocError)? + }; + + Ok(NonNull::slice_from_raw_parts(ptr, size)) + } +} + // SAFETY: TODO. unsafe impl GlobalAlloc for Kmalloc { unsafe fn alloc(&self, layout: Layout) -> *mut u8 { -- cgit v1.2.3 From a34822d1c4c93085f635b922441a017bd7e959b0 Mon Sep 17 00:00:00 2001 From: Danilo Krummrich Date: Fri, 4 Oct 2024 17:41:10 +0200 Subject: rust: alloc: implement `Allocator` for `Kmalloc` Implement `Allocator` for `Kmalloc`, the kernel's default allocator, typically used for objects smaller than page size. All memory allocations made with `Kmalloc` end up in `krealloc()`. It serves as allocator for the subsequently introduced types `KBox` and `KVec`. Reviewed-by: Benno Lossin Reviewed-by: Gary Guo Signed-off-by: Danilo Krummrich Link: https://lore.kernel.org/r/20241004154149.93856-7-dakr@kernel.org Signed-off-by: Miguel Ojeda --- rust/kernel/alloc/allocator.rs | 31 ++++++++++++++++++++++++++++--- 1 file changed, 28 insertions(+), 3 deletions(-) (limited to 'rust/kernel/alloc') diff --git a/rust/kernel/alloc/allocator.rs b/rust/kernel/alloc/allocator.rs index 9ed122401e8a..272c581e24a0 100644 --- a/rust/kernel/alloc/allocator.rs +++ b/rust/kernel/alloc/allocator.rs @@ -13,10 +13,16 @@ use core::alloc::{GlobalAlloc, Layout}; use core::ptr; use core::ptr::NonNull; -use crate::alloc::AllocError; +use crate::alloc::{AllocError, Allocator}; use crate::bindings; -struct Kmalloc; +/// The contiguous kernel allocator. +/// +/// `Kmalloc` is typically used for physically contiguous allocations up to page size, but also +/// supports larger allocations up to `bindings::KMALLOC_MAX_SIZE`, which is hardware specific. +/// +/// For more details see [self]. +pub struct Kmalloc; /// Returns a proper size to alloc a new object aligned to `new_layout`'s alignment. fn aligned_size(new_layout: Layout) -> usize { @@ -53,8 +59,10 @@ struct ReallocFunc( unsafe extern "C" fn(*const core::ffi::c_void, usize, u32) -> *mut core::ffi::c_void, ); -#[expect(dead_code)] impl ReallocFunc { + // INVARIANT: `krealloc` satisfies the type invariants. + const KREALLOC: Self = Self(bindings::krealloc); + /// # Safety /// /// This method has the same safety requirements as [`Allocator::realloc`]. @@ -106,6 +114,23 @@ impl ReallocFunc { } } +// SAFETY: `realloc` delegates to `ReallocFunc::call`, which guarantees that +// - memory remains valid until it is explicitly freed, +// - 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 { + #[inline] + unsafe fn realloc( + ptr: Option>, + layout: Layout, + old_layout: Layout, + flags: Flags, + ) -> Result, AllocError> { + // SAFETY: `ReallocFunc::call` has the same safety requirements as `Allocator::realloc`. + unsafe { ReallocFunc::KREALLOC.call(ptr, layout, old_layout, flags) } + } +} + // SAFETY: TODO. unsafe impl GlobalAlloc for Kmalloc { unsafe fn alloc(&self, layout: Layout) -> *mut u8 { -- cgit v1.2.3 From 5a888c28e3b4ff6f54a53fca33951537d135e7f1 Mon Sep 17 00:00:00 2001 From: Danilo Krummrich Date: Fri, 4 Oct 2024 17:41:11 +0200 Subject: rust: alloc: add module `allocator_test` `Allocator`s, such as `Kmalloc`, will be used by e.g. `Box` and `Vec` in subsequent patches, and hence this dependency propagates throughout the whole kernel. Add the `allocator_test` module that provides an empty implementation for all `Allocator`s in the kernel, such that we don't break the `rusttest` make target in subsequent patches. Reviewed-by: Alice Ryhl Reviewed-by: Benno Lossin Reviewed-by: Gary Guo Signed-off-by: Danilo Krummrich Link: https://lore.kernel.org/r/20241004154149.93856-8-dakr@kernel.org [ Added missing `_old_layout` parameter as discussed. - Miguel ] Signed-off-by: Miguel Ojeda --- rust/kernel/alloc/allocator_test.rs | 20 ++++++++++++++++++++ 1 file changed, 20 insertions(+) create mode 100644 rust/kernel/alloc/allocator_test.rs (limited to 'rust/kernel/alloc') diff --git a/rust/kernel/alloc/allocator_test.rs b/rust/kernel/alloc/allocator_test.rs new file mode 100644 index 000000000000..c5d325506f0c --- /dev/null +++ b/rust/kernel/alloc/allocator_test.rs @@ -0,0 +1,20 @@ +// SPDX-License-Identifier: GPL-2.0 + +#![allow(missing_docs)] + +use super::{AllocError, Allocator, Flags}; +use core::alloc::Layout; +use core::ptr::NonNull; + +pub struct Kmalloc; + +unsafe impl Allocator for Kmalloc { + unsafe fn realloc( + _ptr: Option>, + _layout: Layout, + _old_layout: Layout, + _flags: Flags, + ) -> Result, AllocError> { + panic!(); + } +} -- cgit v1.2.3 From 61c004781d6b928443052e7a6cf84b35d4f61401 Mon Sep 17 00:00:00 2001 From: Danilo Krummrich Date: Fri, 4 Oct 2024 17:41:12 +0200 Subject: rust: alloc: implement `Vmalloc` allocator Implement `Allocator` for `Vmalloc`, the kernel's virtually contiguous allocator, typically used for larger objects, (much) larger than page size. All memory allocations made with `Vmalloc` end up in `vrealloc()`. Reviewed-by: Alice Ryhl Reviewed-by: Benno Lossin Reviewed-by: Gary Guo Signed-off-by: Danilo Krummrich Link: https://lore.kernel.org/r/20241004154149.93856-9-dakr@kernel.org Signed-off-by: Miguel Ojeda --- rust/kernel/alloc/allocator.rs | 37 +++++++++++++++++++++++++++++++++++++ rust/kernel/alloc/allocator_test.rs | 1 + 2 files changed, 38 insertions(+) (limited to 'rust/kernel/alloc') diff --git a/rust/kernel/alloc/allocator.rs b/rust/kernel/alloc/allocator.rs index 272c581e24a0..ee4c828cbd58 100644 --- a/rust/kernel/alloc/allocator.rs +++ b/rust/kernel/alloc/allocator.rs @@ -15,6 +15,7 @@ use core::ptr::NonNull; use crate::alloc::{AllocError, Allocator}; use crate::bindings; +use crate::pr_warn; /// The contiguous kernel allocator. /// @@ -24,6 +25,15 @@ use crate::bindings; /// For more details see [self]. pub struct Kmalloc; +/// The virtually contiguous kernel allocator. +/// +/// `Vmalloc` allocates pages from the page level allocator and maps them into the contiguous kernel +/// virtual space. It is typically used for large allocations. The memory allocated with this +/// allocator is not physically contiguous. +/// +/// For more details see [self]. +pub struct Vmalloc; + /// Returns a proper size to alloc a new object aligned to `new_layout`'s alignment. fn aligned_size(new_layout: Layout) -> usize { // Customized layouts from `Layout::from_size_align()` can have size < align, so pad first. @@ -63,6 +73,9 @@ impl ReallocFunc { // INVARIANT: `krealloc` satisfies the type invariants. const KREALLOC: Self = Self(bindings::krealloc); + // INVARIANT: `vrealloc` satisfies the type invariants. + const VREALLOC: Self = Self(bindings::vrealloc); + /// # Safety /// /// This method has the same safety requirements as [`Allocator::realloc`]. @@ -168,6 +181,30 @@ unsafe impl GlobalAlloc for Kmalloc { } } +// SAFETY: `realloc` delegates to `ReallocFunc::call`, which guarantees that +// - memory remains valid until it is explicitly freed, +// - 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 { + #[inline] + unsafe fn realloc( + ptr: Option>, + layout: Layout, + old_layout: Layout, + flags: Flags, + ) -> Result, 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) } + } +} + #[global_allocator] static ALLOCATOR: Kmalloc = Kmalloc; diff --git a/rust/kernel/alloc/allocator_test.rs b/rust/kernel/alloc/allocator_test.rs index c5d325506f0c..32a1450c4d39 100644 --- a/rust/kernel/alloc/allocator_test.rs +++ b/rust/kernel/alloc/allocator_test.rs @@ -7,6 +7,7 @@ use core::alloc::Layout; use core::ptr::NonNull; pub struct Kmalloc; +pub type Vmalloc = Kmalloc; unsafe impl Allocator for Kmalloc { unsafe fn realloc( -- cgit v1.2.3 From 8362c2608ba1be635ffa22a256dfcfe51c6238cc Mon Sep 17 00:00:00 2001 From: Danilo Krummrich Date: Fri, 4 Oct 2024 17:41:13 +0200 Subject: rust: alloc: implement `KVmalloc` allocator Implement `Allocator` for `KVmalloc`, an `Allocator` that tries to allocate memory with `kmalloc` first and, on failure, falls back to `vmalloc`. All memory allocations made with `KVmalloc` end up in `kvrealloc_noprof()`; all frees in `kvfree()`. Reviewed-by: Alice Ryhl Reviewed-by: Benno Lossin Reviewed-by: Gary Guo Signed-off-by: Danilo Krummrich Link: https://lore.kernel.org/r/20241004154149.93856-10-dakr@kernel.org [ Reworded typo. - Miguel ] Signed-off-by: Miguel Ojeda --- rust/kernel/alloc/allocator.rs | 36 ++++++++++++++++++++++++++++++++++++ rust/kernel/alloc/allocator_test.rs | 1 + 2 files changed, 37 insertions(+) (limited to 'rust/kernel/alloc') diff --git a/rust/kernel/alloc/allocator.rs b/rust/kernel/alloc/allocator.rs index ee4c828cbd58..f8a1f0feb25d 100644 --- a/rust/kernel/alloc/allocator.rs +++ b/rust/kernel/alloc/allocator.rs @@ -34,6 +34,15 @@ pub struct Kmalloc; /// For more details see [self]. pub struct Vmalloc; +/// The kvmalloc kernel allocator. +/// +/// `KVmalloc` attempts to allocate memory with `Kmalloc` first, but falls back to `Vmalloc` upon +/// failure. This allocator is typically used when the size for the requested allocation is not +/// known and may exceed the capabilities of `Kmalloc`. +/// +/// For more details see [self]. +pub struct KVmalloc; + /// Returns a proper size to alloc a new object aligned to `new_layout`'s alignment. fn aligned_size(new_layout: Layout) -> usize { // Customized layouts from `Layout::from_size_align()` can have size < align, so pad first. @@ -76,6 +85,9 @@ impl ReallocFunc { // INVARIANT: `vrealloc` satisfies the type invariants. const VREALLOC: Self = Self(bindings::vrealloc); + // INVARIANT: `kvrealloc` satisfies the type invariants. + const KVREALLOC: Self = Self(bindings::kvrealloc); + /// # Safety /// /// This method has the same safety requirements as [`Allocator::realloc`]. @@ -205,6 +217,30 @@ unsafe impl Allocator for Vmalloc { } } +// SAFETY: `realloc` delegates to `ReallocFunc::call`, which guarantees that +// - memory remains valid until it is explicitly freed, +// - 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 { + #[inline] + unsafe fn realloc( + ptr: Option>, + layout: Layout, + old_layout: Layout, + flags: Flags, + ) -> Result, AllocError> { + // 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) } + } +} + #[global_allocator] static ALLOCATOR: Kmalloc = Kmalloc; diff --git a/rust/kernel/alloc/allocator_test.rs b/rust/kernel/alloc/allocator_test.rs index 32a1450c4d39..bd0cbcd93e52 100644 --- a/rust/kernel/alloc/allocator_test.rs +++ b/rust/kernel/alloc/allocator_test.rs @@ -8,6 +8,7 @@ use core::ptr::NonNull; pub struct Kmalloc; pub type Vmalloc = Kmalloc; +pub type KVmalloc = Kmalloc; unsafe impl Allocator for Kmalloc { unsafe fn realloc( -- cgit v1.2.3 From c8cfa8d0c0b10be216861fe904ea68978b1dcc97 Mon Sep 17 00:00:00 2001 From: Danilo Krummrich Date: Fri, 4 Oct 2024 17:41:15 +0200 Subject: rust: alloc: implement kernel `Box` `Box` provides the simplest way to allocate memory for a generic type with one of the kernel's allocators, e.g. `Kmalloc`, `Vmalloc` or `KVmalloc`. In contrast to Rust's `Box` type, the kernel `Box` type considers the kernel's GFP flags for all appropriate functions, always reports allocation failures through `Result<_, AllocError>` and remains independent from unstable features. Reviewed-by: Benno Lossin Reviewed-by: Gary Guo Signed-off-by: Danilo Krummrich Link: https://lore.kernel.org/r/20241004154149.93856-12-dakr@kernel.org [ Added backticks, fixed typos. - Miguel ] Signed-off-by: Miguel Ojeda --- rust/kernel/alloc/kbox.rs | 456 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 456 insertions(+) create mode 100644 rust/kernel/alloc/kbox.rs (limited to 'rust/kernel/alloc') diff --git a/rust/kernel/alloc/kbox.rs b/rust/kernel/alloc/kbox.rs new file mode 100644 index 000000000000..d69c32496b86 --- /dev/null +++ b/rust/kernel/alloc/kbox.rs @@ -0,0 +1,456 @@ +// SPDX-License-Identifier: GPL-2.0 + +//! Implementation of [`Box`]. + +#[allow(unused_imports)] // Used in doc comments. +use super::allocator::{KVmalloc, Kmalloc, Vmalloc}; +use super::{AllocError, Allocator, Flags}; +use core::alloc::Layout; +use core::fmt; +use core::marker::PhantomData; +use core::mem::ManuallyDrop; +use core::mem::MaybeUninit; +use core::ops::{Deref, DerefMut}; +use core::pin::Pin; +use core::ptr::NonNull; +use core::result::Result; + +use crate::init::{InPlaceInit, InPlaceWrite, Init, PinInit}; +use crate::types::ForeignOwnable; + +/// The kernel's [`Box`] type -- a heap allocation for a single value of type `T`. +/// +/// This is the kernel's version of the Rust stdlib's `Box`. There are several differences, +/// for example no `noalias` attribute is emitted and partially moving out of a `Box` is not +/// supported. There are also several API differences, e.g. `Box` always requires an [`Allocator`] +/// implementation to be passed as generic, page [`Flags`] when allocating memory and all functions +/// that may allocate memory are fallible. +/// +/// `Box` works with any of the kernel's allocators, e.g. [`Kmalloc`], [`Vmalloc`] or [`KVmalloc`]. +/// There are aliases for `Box` with these allocators ([`KBox`], [`VBox`], [`KVBox`]). +/// +/// When dropping a [`Box`], the value is also dropped and the heap memory is automatically freed. +/// +/// # Examples +/// +/// ``` +/// let b = KBox::::new(24_u64, GFP_KERNEL)?; +/// +/// assert_eq!(*b, 24_u64); +/// # Ok::<(), Error>(()) +/// ``` +/// +/// ``` +/// # use kernel::bindings; +/// const SIZE: usize = bindings::KMALLOC_MAX_SIZE as usize + 1; +/// struct Huge([u8; SIZE]); +/// +/// assert!(KBox::::new_uninit(GFP_KERNEL | __GFP_NOWARN).is_err()); +/// ``` +/// +/// ``` +/// # use kernel::bindings; +/// const SIZE: usize = bindings::KMALLOC_MAX_SIZE as usize + 1; +/// struct Huge([u8; SIZE]); +/// +/// assert!(KVBox::::new_uninit(GFP_KERNEL).is_ok()); +/// ``` +/// +/// # Invariants +/// +/// `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)] +pub struct Box(NonNull, PhantomData); + +/// Type alias for [`Box`] with a [`Kmalloc`] allocator. +/// +/// # Examples +/// +/// ``` +/// let b = KBox::new(24_u64, GFP_KERNEL)?; +/// +/// assert_eq!(*b, 24_u64); +/// # Ok::<(), Error>(()) +/// ``` +pub type KBox = Box; + +/// Type alias for [`Box`] with a [`Vmalloc`] allocator. +/// +/// # Examples +/// +/// ``` +/// let b = VBox::new(24_u64, GFP_KERNEL)?; +/// +/// assert_eq!(*b, 24_u64); +/// # Ok::<(), Error>(()) +/// ``` +pub type VBox = Box; + +/// Type alias for [`Box`] with a [`KVmalloc`] allocator. +/// +/// # Examples +/// +/// ``` +/// let b = KVBox::new(24_u64, GFP_KERNEL)?; +/// +/// assert_eq!(*b, 24_u64); +/// # Ok::<(), Error>(()) +/// ``` +pub type KVBox = Box; + +// SAFETY: `Box` is `Send` if `T` is `Send` because the `Box` owns a `T`. +unsafe impl Send for Box +where + T: Send + ?Sized, + A: Allocator, +{ +} + +// SAFETY: `Box` is `Sync` if `T` is `Sync` because the `Box` owns a `T`. +unsafe impl Sync for Box +where + T: Sync + ?Sized, + A: Allocator, +{ +} + +impl Box +where + T: ?Sized, + A: Allocator, +{ + /// Creates a new `Box` from a raw pointer. + /// + /// # Safety + /// + /// For non-ZSTs, `raw` must point at an allocation allocated with `A` that is sufficiently + /// aligned for and holds a valid `T`. The caller passes ownership of the allocation to the + /// `Box`. + /// + /// For ZSTs, `raw` must be a dangling, well aligned pointer. + #[inline] + pub const unsafe fn from_raw(raw: *mut T) -> Self { + // INVARIANT: Validity of `raw` is guaranteed by the safety preconditions of this function. + // SAFETY: By the safety preconditions of this function, `raw` is not a NULL pointer. + Self(unsafe { NonNull::new_unchecked(raw) }, PhantomData) + } + + /// Consumes the `Box` and returns a raw pointer. + /// + /// This will not run the destructor of `T` and for non-ZSTs the allocation will stay alive + /// indefinitely. Use [`Box::from_raw`] to recover the [`Box`], drop the value and free the + /// allocation, if any. + /// + /// # Examples + /// + /// ``` + /// let x = KBox::new(24, GFP_KERNEL)?; + /// let ptr = KBox::into_raw(x); + /// // SAFETY: `ptr` comes from a previous call to `KBox::into_raw`. + /// let x = unsafe { KBox::from_raw(ptr) }; + /// + /// assert_eq!(*x, 24); + /// # Ok::<(), Error>(()) + /// ``` + #[inline] + pub fn into_raw(b: Self) -> *mut T { + ManuallyDrop::new(b).0.as_ptr() + } + + /// Consumes and leaks the `Box` and returns a mutable reference. + /// + /// See [`Box::into_raw`] for more details. + #[inline] + pub fn leak<'a>(b: Self) -> &'a mut T { + // SAFETY: `Box::into_raw` always returns a properly aligned and dereferenceable pointer + // which points to an initialized instance of `T`. + unsafe { &mut *Box::into_raw(b) } + } +} + +impl Box, A> +where + A: Allocator, +{ + /// Converts a `Box, A>` to a `Box`. + /// + /// It is undefined behavior to call this function while the value inside of `b` is not yet + /// fully initialized. + /// + /// # Safety + /// + /// Callers must ensure that the value inside of `b` is in an initialized state. + pub unsafe fn assume_init(self) -> Box { + let raw = Self::into_raw(self); + + // SAFETY: `raw` comes from a previous call to `Box::into_raw`. By the safety requirements + // of this function, the value inside the `Box` is in an initialized state. Hence, it is + // safe to reconstruct the `Box` as `Box`. + unsafe { Box::from_raw(raw.cast()) } + } + + /// Writes the value and converts to `Box`. + pub fn write(mut self, value: T) -> Box { + (*self).write(value); + + // SAFETY: We've just initialized `b`'s value. + unsafe { self.assume_init() } + } +} + +impl Box +where + A: Allocator, +{ + /// Creates a new `Box` and initializes its contents with `x`. + /// + /// New memory is allocated with `A`. The allocation may fail, in which case an error is + /// returned. For ZSTs no memory is allocated. + pub fn new(x: T, flags: Flags) -> Result { + let b = Self::new_uninit(flags)?; + Ok(Box::write(b, x)) + } + + /// Creates a new `Box` with uninitialized contents. + /// + /// New memory is allocated with `A`. The allocation may fail, in which case an error is + /// returned. For ZSTs no memory is allocated. + /// + /// # Examples + /// + /// ``` + /// let b = KBox::::new_uninit(GFP_KERNEL)?; + /// let b = KBox::write(b, 24); + /// + /// assert_eq!(*b, 24_u64); + /// # Ok::<(), Error>(()) + /// ``` + pub fn new_uninit(flags: Flags) -> Result, A>, AllocError> { + let layout = Layout::new::>(); + let ptr = A::alloc(layout, flags)?; + + // 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`. + Ok(Box(ptr.cast(), PhantomData)) + } + + /// Constructs a new `Pin>`. If `T` does not implement [`Unpin`], then `x` will be + /// pinned in memory and can't be moved. + #[inline] + pub fn pin(x: T, flags: Flags) -> Result>, AllocError> + where + A: 'static, + { + Ok(Self::new(x, flags)?.into()) + } + + /// Forgets the contents (does not run the destructor), but keeps the allocation. + fn forget_contents(this: Self) -> Box, A> { + let ptr = Self::into_raw(this); + + // SAFETY: `ptr` is valid, because it came from `Box::into_raw`. + unsafe { Box::from_raw(ptr.cast()) } + } + + /// Drops the contents, but keeps the allocation. + /// + /// # Examples + /// + /// ``` + /// let value = KBox::new([0; 32], GFP_KERNEL)?; + /// assert_eq!(*value, [0; 32]); + /// let value = KBox::drop_contents(value); + /// // Now we can re-use `value`: + /// let value = KBox::write(value, [1; 32]); + /// assert_eq!(*value, [1; 32]); + /// # Ok::<(), Error>(()) + /// ``` + pub fn drop_contents(this: Self) -> Box, A> { + let ptr = this.0.as_ptr(); + + // SAFETY: `ptr` is valid, because it came from `this`. After this call we never access the + // value stored in `this` again. + unsafe { core::ptr::drop_in_place(ptr) }; + + Self::forget_contents(this) + } + + /// Moves the `Box`'s value out of the `Box` and consumes the `Box`. + pub fn into_inner(b: Self) -> T { + // SAFETY: By the type invariant `&*b` is valid for `read`. + let value = unsafe { core::ptr::read(&*b) }; + let _ = Self::forget_contents(b); + value + } +} + +impl From> for Pin> +where + T: ?Sized, + A: Allocator, +{ + /// Converts a `Box` into a `Pin>`. If `T` does not implement [`Unpin`], then + /// `*b` will be pinned in memory and can't be moved. + /// + /// This moves `b` into `Pin` without moving `*b` or allocating and copying any memory. + fn from(b: Box) -> Self { + // SAFETY: The value wrapped inside a `Pin>` cannot be moved or replaced as long + // as `T` does not implement `Unpin`. + unsafe { Pin::new_unchecked(b) } + } +} + +impl InPlaceWrite for Box, A> +where + A: Allocator + 'static, +{ + type Initialized = Box; + + fn write_init(mut self, init: impl Init) -> Result { + let slot = self.as_mut_ptr(); + // SAFETY: When init errors/panics, slot will get deallocated but not dropped, + // slot is valid. + unsafe { init.__init(slot)? }; + // SAFETY: All fields have been initialized. + Ok(unsafe { Box::assume_init(self) }) + } + + fn write_pin_init(mut self, init: impl PinInit) -> Result, E> { + let slot = self.as_mut_ptr(); + // SAFETY: When init errors/panics, slot will get deallocated but not dropped, + // slot is valid and will not be moved, because we pin it later. + unsafe { init.__pinned_init(slot)? }; + // SAFETY: All fields have been initialized. + Ok(unsafe { Box::assume_init(self) }.into()) + } +} + +impl InPlaceInit for Box +where + A: Allocator + 'static, +{ + type PinnedSelf = Pin; + + #[inline] + fn try_pin_init(init: impl PinInit, flags: Flags) -> Result, E> + where + E: From, + { + Box::<_, A>::new_uninit(flags)?.write_pin_init(init) + } + + #[inline] + fn try_init(init: impl Init, flags: Flags) -> Result + where + E: From, + { + Box::<_, A>::new_uninit(flags)?.write_init(init) + } +} + +impl ForeignOwnable for Box +where + A: Allocator, +{ + type Borrowed<'a> = &'a T; + + fn into_foreign(self) -> *const core::ffi::c_void { + Box::into_raw(self) as _ + } + + unsafe fn from_foreign(ptr: *const core::ffi::c_void) -> Self { + // SAFETY: The safety requirements of this function ensure that `ptr` comes from a previous + // call to `Self::into_foreign`. + unsafe { Box::from_raw(ptr as _) } + } + + unsafe fn borrow<'a>(ptr: *const core::ffi::c_void) -> &'a T { + // SAFETY: The safety requirements of this method ensure that the object remains alive and + // immutable for the duration of 'a. + unsafe { &*ptr.cast() } + } +} + +impl ForeignOwnable for Pin> +where + A: Allocator, +{ + type Borrowed<'a> = Pin<&'a T>; + + fn into_foreign(self) -> *const core::ffi::c_void { + // SAFETY: We are still treating the box as pinned. + Box::into_raw(unsafe { Pin::into_inner_unchecked(self) }) as _ + } + + unsafe fn from_foreign(ptr: *const core::ffi::c_void) -> Self { + // SAFETY: The safety requirements of this function ensure that `ptr` comes from a previous + // call to `Self::into_foreign`. + unsafe { Pin::new_unchecked(Box::from_raw(ptr as _)) } + } + + unsafe fn borrow<'a>(ptr: *const core::ffi::c_void) -> Pin<&'a T> { + // SAFETY: The safety requirements for this function ensure that the object is still alive, + // so it is safe to dereference the raw pointer. + // The safety requirements of `from_foreign` also ensure that the object remains alive for + // the lifetime of the returned value. + let r = unsafe { &*ptr.cast() }; + + // SAFETY: This pointer originates from a `Pin>`. + unsafe { Pin::new_unchecked(r) } + } +} + +impl Deref for Box +where + T: ?Sized, + A: Allocator, +{ + type Target = T; + + fn deref(&self) -> &T { + // SAFETY: `self.0` is always properly aligned, dereferenceable and points to an initialized + // instance of `T`. + unsafe { self.0.as_ref() } + } +} + +impl DerefMut for Box +where + T: ?Sized, + A: Allocator, +{ + fn deref_mut(&mut self) -> &mut T { + // SAFETY: `self.0` is always properly aligned, dereferenceable and points to an initialized + // instance of `T`. + unsafe { self.0.as_mut() } + } +} + +impl fmt::Debug for Box +where + T: ?Sized + fmt::Debug, + A: Allocator, +{ + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + fmt::Debug::fmt(&**self, f) + } +} + +impl Drop for Box +where + T: ?Sized, + A: Allocator, +{ + fn drop(&mut self) { + let layout = Layout::for_value::(self); + + // SAFETY: The pointer in `self.0` is guaranteed to be valid by the type invariant. + unsafe { core::ptr::drop_in_place::(self.deref_mut()) }; + + // SAFETY: + // - `self.0` was previously allocated with `A`. + // - `layout` is equal to the `Layout´ `self.0` was allocated with. + unsafe { A::free(self.0.cast(), layout) }; + } +} -- cgit v1.2.3 From e8c6ccdbcaaf31f26c0fffd4073edd0b0147cdc6 Mon Sep 17 00:00:00 2001 From: Danilo Krummrich Date: Fri, 4 Oct 2024 17:41:17 +0200 Subject: rust: alloc: remove extension of std's `Box` Now that all existing `Box` users were moved to the kernel `Box` type, remove the `BoxExt` extension and all other related extensions. Reviewed-by: Alice Ryhl Reviewed-by: Benno Lossin Reviewed-by: Gary Guo Signed-off-by: Danilo Krummrich Link: https://lore.kernel.org/r/20241004154149.93856-14-dakr@kernel.org Signed-off-by: Miguel Ojeda --- rust/kernel/alloc/box_ext.rs | 89 -------------------------------------------- 1 file changed, 89 deletions(-) delete mode 100644 rust/kernel/alloc/box_ext.rs (limited to 'rust/kernel/alloc') diff --git a/rust/kernel/alloc/box_ext.rs b/rust/kernel/alloc/box_ext.rs deleted file mode 100644 index 7009ad78d4e0..000000000000 --- a/rust/kernel/alloc/box_ext.rs +++ /dev/null @@ -1,89 +0,0 @@ -// SPDX-License-Identifier: GPL-2.0 - -//! Extensions to [`Box`] for fallible allocations. - -use super::{AllocError, Flags}; -use alloc::boxed::Box; -use core::{mem::MaybeUninit, ptr, result::Result}; - -/// Extensions to [`Box`]. -pub trait BoxExt: Sized { - /// Allocates a new box. - /// - /// The allocation may fail, in which case an error is returned. - fn new(x: T, flags: Flags) -> Result; - - /// Allocates a new uninitialised box. - /// - /// The allocation may fail, in which case an error is returned. - fn new_uninit(flags: Flags) -> Result>, AllocError>; - - /// Drops the contents, but keeps the allocation. - /// - /// # Examples - /// - /// ``` - /// use kernel::alloc::{flags, box_ext::BoxExt}; - /// let value = Box::new([0; 32], flags::GFP_KERNEL)?; - /// assert_eq!(*value, [0; 32]); - /// let mut value = Box::drop_contents(value); - /// // Now we can re-use `value`: - /// value.write([1; 32]); - /// // SAFETY: We just wrote to it. - /// let value = unsafe { value.assume_init() }; - /// assert_eq!(*value, [1; 32]); - /// # Ok::<(), Error>(()) - /// ``` - fn drop_contents(this: Self) -> Box>; -} - -impl BoxExt for Box { - fn new(x: T, flags: Flags) -> Result { - let mut b = >::new_uninit(flags)?; - b.write(x); - // SAFETY: We just wrote to it. - Ok(unsafe { b.assume_init() }) - } - - #[cfg(any(test, testlib))] - fn new_uninit(_flags: Flags) -> Result>, AllocError> { - Ok(Box::new_uninit()) - } - - #[cfg(not(any(test, testlib)))] - fn new_uninit(flags: Flags) -> Result>, AllocError> { - let ptr = if core::mem::size_of::>() == 0 { - core::ptr::NonNull::<_>::dangling().as_ptr() - } else { - let layout = core::alloc::Layout::new::>(); - - // SAFETY: Memory is being allocated (first arg is null). The only other source of - // safety issues is sleeping on atomic context, which is addressed by klint. Lastly, - // the type is not a SZT (checked above). - let ptr = - unsafe { super::allocator::krealloc_aligned(core::ptr::null_mut(), layout, flags) }; - if ptr.is_null() { - return Err(AllocError); - } - - ptr.cast::>() - }; - - // SAFETY: For non-zero-sized types, we allocate above using the global allocator. For - // zero-sized types, we use `NonNull::dangling`. - Ok(unsafe { Box::from_raw(ptr) }) - } - - fn drop_contents(this: Self) -> Box> { - let ptr = Box::into_raw(this); - // SAFETY: `ptr` is valid, because it came from `Box::into_raw`. - unsafe { ptr::drop_in_place(ptr) }; - - // CAST: `MaybeUninit` is a transparent wrapper of `T`. - let ptr = ptr.cast::>(); - - // SAFETY: `ptr` is valid for writes, because it came from `Box::into_raw` and it is valid for - // reads, since the pointer came from `Box::into_raw` and the type is `MaybeUninit`. - unsafe { Box::from_raw(ptr) } - } -} -- cgit v1.2.3 From 9e7bbfa182767f638ba61dba3518ff78da9f31ff Mon Sep 17 00:00:00 2001 From: Benno Lossin Date: Fri, 4 Oct 2024 17:41:19 +0200 Subject: rust: alloc: introduce `ArrayLayout` When allocating memory for arrays using allocators, the `Layout::array` function is typically used. It returns a result, since the given size might be too big. However, `Vec` and its iterators store their allocated capacity and thus they already did check that the size is not too big. The `ArrayLayout` type provides this exact behavior, as it can be infallibly converted into a `Layout`. Instead of a `usize` capacity, `Vec` and other similar array-storing types can use `ArrayLayout` instead. Reviewed-by: Gary Guo Signed-off-by: Benno Lossin Signed-off-by: Danilo Krummrich Link: https://lore.kernel.org/r/20241004154149.93856-16-dakr@kernel.org [ Formatted a few comments. - Miguel ] Signed-off-by: Miguel Ojeda --- rust/kernel/alloc/layout.rs | 91 +++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 91 insertions(+) create mode 100644 rust/kernel/alloc/layout.rs (limited to 'rust/kernel/alloc') diff --git a/rust/kernel/alloc/layout.rs b/rust/kernel/alloc/layout.rs new file mode 100644 index 000000000000..7e0c2f46157b --- /dev/null +++ b/rust/kernel/alloc/layout.rs @@ -0,0 +1,91 @@ +// SPDX-License-Identifier: GPL-2.0 + +//! Memory layout. +//! +//! Custom layout types extending or improving [`Layout`]. + +use core::{alloc::Layout, marker::PhantomData}; + +/// Error when constructing an [`ArrayLayout`]. +pub struct LayoutError; + +/// A layout for an array `[T; n]`. +/// +/// # Invariants +/// +/// - `len * size_of::() <= isize::MAX`. +pub struct ArrayLayout { + len: usize, + _phantom: PhantomData T>, +} + +impl Clone for ArrayLayout { + fn clone(&self) -> Self { + *self + } +} +impl Copy for ArrayLayout {} + +const ISIZE_MAX: usize = isize::MAX as usize; + +impl ArrayLayout { + /// Creates a new layout for `[T; 0]`. + pub const fn empty() -> Self { + // INVARIANT: `0 * size_of::() <= isize::MAX`. + Self { + len: 0, + _phantom: PhantomData, + } + } + + /// Creates a new layout for `[T; len]`. + /// + /// # Errors + /// + /// When `len * size_of::()` overflows or when `len * size_of::() > isize::MAX`. + pub const fn new(len: usize) -> Result { + match len.checked_mul(core::mem::size_of::()) { + Some(len) if len <= ISIZE_MAX => { + // INVARIANT: We checked above that `len * size_of::() <= isize::MAX`. + Ok(Self { + len, + _phantom: PhantomData, + }) + } + _ => Err(LayoutError), + } + } + + /// Creates a new layout for `[T; len]`. + /// + /// # Safety + /// + /// `len` must be a value, for which `len * size_of::() <= isize::MAX` is true. + pub unsafe fn new_unchecked(len: usize) -> Self { + // INVARIANT: By the safety requirements of this function + // `len * size_of::() <= isize::MAX`. + Self { + len, + _phantom: PhantomData, + } + } + + /// Returns the number of array elements represented by this layout. + pub const fn len(&self) -> usize { + self.len + } + + /// Returns `true` when no array elements are represented by this layout. + pub const fn is_empty(&self) -> bool { + self.len == 0 + } +} + +impl From> for Layout { + fn from(value: ArrayLayout) -> Self { + let res = Layout::array::(value.len); + // SAFETY: By the type invariant of `ArrayLayout` we have + // `len * size_of::() <= isize::MAX` and thus the result must be `Ok`. + unsafe { res.unwrap_unchecked() } + } +} -- cgit v1.2.3 From 2aac4cd7dae3d7bb0e0ddec2561b2ee4cbe6c8f6 Mon Sep 17 00:00:00 2001 From: Danilo Krummrich Date: Fri, 4 Oct 2024 17:41:20 +0200 Subject: rust: alloc: implement kernel `Vec` type `Vec` provides a contiguous growable array type with contents allocated with the kernel's allocators (e.g. `Kmalloc`, `Vmalloc` or `KVmalloc`). In contrast to Rust's stdlib `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. [ This patch starts using a new unstable feature, `inline_const`, but it was stabilized in Rust 1.79.0, i.e. the next version after the minimum one, thus it will not be an issue. - Miguel ] Reviewed-by: Benno Lossin Reviewed-by: Gary Guo Signed-off-by: Danilo Krummrich Link: https://lore.kernel.org/r/20241004154149.93856-17-dakr@kernel.org [ Cleaned `rustdoc` unescaped backtick warning, added a couple more backticks elsewhere, fixed typos, sorted `feature`s, rewrapped documentation lines. - Miguel ] Signed-off-by: Miguel Ojeda --- rust/kernel/alloc/kvec.rs | 648 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 648 insertions(+) create mode 100644 rust/kernel/alloc/kvec.rs (limited to 'rust/kernel/alloc') diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs new file mode 100644 index 000000000000..8a1d8f414955 --- /dev/null +++ b/rust/kernel/alloc/kvec.rs @@ -0,0 +1,648 @@ +// SPDX-License-Identifier: GPL-2.0 + +//! Implementation of [`Vec`]. + +use super::{ + allocator::{KVmalloc, Kmalloc, Vmalloc}, + layout::ArrayLayout, + AllocError, Allocator, Box, Flags, +}; +use core::{ + fmt, + marker::PhantomData, + mem::{ManuallyDrop, MaybeUninit}, + ops::Deref, + ops::DerefMut, + ops::Index, + ops::IndexMut, + ptr, + ptr::NonNull, + slice, + slice::SliceIndex, +}; + +/// Create a [`KVec`] containing the arguments. +/// +/// New memory is allocated with `GFP_KERNEL`. +/// +/// # Examples +/// +/// ``` +/// let mut v = kernel::kvec![]; +/// v.push(1, GFP_KERNEL)?; +/// assert_eq!(v, [1]); +/// +/// let mut v = kernel::kvec![1; 3]?; +/// v.push(4, GFP_KERNEL)?; +/// assert_eq!(v, [1, 1, 1, 4]); +/// +/// let mut v = kernel::kvec![1, 2, 3]?; +/// v.push(4, GFP_KERNEL)?; +/// assert_eq!(v, [1, 2, 3, 4]); +/// +/// # Ok::<(), Error>(()) +/// ``` +#[macro_export] +macro_rules! kvec { + () => ( + $crate::alloc::KVec::new() + ); + ($elem:expr; $n:expr) => ( + $crate::alloc::KVec::from_elem($elem, $n, GFP_KERNEL) + ); + ($($x:expr),+ $(,)?) => ( + match $crate::alloc::KBox::new_uninit(GFP_KERNEL) { + Ok(b) => Ok($crate::alloc::KVec::from($crate::alloc::KBox::write(b, [$($x),+]))), + Err(e) => Err(e), + } + ); +} + +/// The kernel's [`Vec`] type. +/// +/// A contiguous growable array type with contents allocated with the kernel's allocators (e.g. +/// [`Kmalloc`], [`Vmalloc`] or [`KVmalloc`]), written `Vec`. +/// +/// 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), its length +/// (the number of elements that are currently stored in the vector) and the `Allocator` type used +/// to allocate (and free) the backing buffer. +/// +/// A [`Vec`] can be deconstructed into and (re-)constructed from its previously named raw parts +/// and manually modified. +/// +/// [`Vec`]'s backing buffer gets, if required, automatically increased (re-allocated) when elements +/// are added to the vector. +/// +/// # Invariants +/// +/// - `self.ptr` is always properly aligned and either points to memory allocated with `A` or, for +/// zero-sized types, is a dangling, well aligned pointer. +/// +/// - `self.len` always represents the exact number of elements stored in the vector. +/// +/// - `self.layout` represents the absolute number of elements that can be stored within the vector +/// without re-allocation. For ZSTs `self.layout`'s capacity is zero. However, it is legal for the +/// backing buffer to be larger than `layout`. +/// +/// - The `Allocator` type `A` of the vector is the exact same `Allocator` type the backing buffer +/// was allocated with (and must be freed with). +pub struct Vec { + ptr: NonNull, + /// Represents the actual buffer size as `cap` times `size_of::` bytes. + /// + /// Note: This isn't quite the same as `Self::capacity`, which in contrast returns the number of + /// elements we can still store without reallocating. + layout: ArrayLayout, + 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; + +// SAFETY: `Vec` is `Send` if `T` is `Send` because `Vec` owns its elements. +unsafe impl Send for Vec +where + T: Send, + A: Allocator, +{ +} + +// SAFETY: `Vec` is `Sync` if `T` is `Sync` because `Vec` owns its elements. +unsafe impl Sync for Vec +where + T: Sync, + A: Allocator, +{ +} + +impl Vec +where + A: Allocator, +{ + #[inline] + const fn is_zst() -> bool { + core::mem::size_of::() == 0 + } + + /// Returns the number of elements that can be stored within the vector without allocating + /// additional memory. + pub fn capacity(&self) -> usize { + if const { Self::is_zst() } { + usize::MAX + } else { + self.layout.len() + } + } + + /// Returns the number of elements stored within the vector. + #[inline] + pub fn len(&self) -> usize { + self.len + } + + /// Forcefully sets `self.len` to `new_len`. + /// + /// # Safety + /// + /// - `new_len` must be less than or equal to [`Self::capacity`]. + /// - If `new_len` is greater than `self.len`, all elements within the interval + /// [`self.len`,`new_len`) must be initialized. + #[inline] + pub unsafe fn set_len(&mut self, new_len: usize) { + debug_assert!(new_len <= self.capacity()); + self.len = new_len; + } + + /// Returns a slice of the entire vector. + #[inline] + pub fn as_slice(&self) -> &[T] { + self + } + + /// Returns a mutable slice of the entire vector. + #[inline] + pub fn as_mut_slice(&mut self) -> &mut [T] { + self + } + + /// Returns a mutable raw pointer to the vector's backing buffer, or, if `T` is a ZST, a + /// dangling raw pointer. + #[inline] + pub fn as_mut_ptr(&mut self) -> *mut T { + self.ptr.as_ptr() + } + + /// 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 { + self.ptr.as_ptr() + } + + /// Returns `true` if the vector contains no elements, `false` otherwise. + /// + /// # 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 + } + + /// Creates a new, empty `Vec`. + /// + /// This method does not allocate by itself. + #[inline] + pub const fn new() -> Self { + // INVARIANT: Since this is a new, empty `Vec` with no backing memory yet, + // - `ptr` is a properly aligned dangling pointer for type `T`, + // - `layout` is an empty `ArrayLayout` (zero capacity) + // - `len` is zero, since no elements can be or have been stored, + // - `A` is always valid. + Self { + ptr: NonNull::dangling(), + layout: ArrayLayout::empty(), + len: 0, + _p: PhantomData::, + } + } + + /// Returns a slice of `MaybeUninit` for the remaining spare capacity of the vector. + pub fn spare_capacity_mut(&mut self) -> &mut [MaybeUninit] { + // SAFETY: + // - `self.len` is smaller than `self.capacity` and hence, the resulting pointer is + // guaranteed to be part of the same allocated object. + // - `self.len` can not overflow `isize`. + let ptr = unsafe { self.as_mut_ptr().add(self.len) } as *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(ptr, 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> { + self.reserve(1, flags)?; + + // SAFETY: + // - `self.len` is smaller than `self.capacity` and hence, the resulting pointer is + // guaranteed to be part of the same allocated object. + // - `self.len` can not overflow `isize`. + let ptr = unsafe { self.as_mut_ptr().add(self.len) }; + + // SAFETY: + // - `ptr` is properly aligned and valid for writes. + unsafe { core::ptr::write(ptr, v) }; + + // 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(); + + v.reserve(capacity, flags)?; + + Ok(v) + } + + /// Creates a `Vec` from a pointer, a length and a capacity using the allocator `A`. + /// + /// # Examples + /// + /// ``` + /// let mut v = kernel::kvec![1, 2, 3]?; + /// v.reserve(1, GFP_KERNEL)?; + /// + /// let (mut ptr, mut len, cap) = v.into_raw_parts(); + /// + /// // SAFETY: We've just reserved memory for another element. + /// unsafe { ptr.add(len).write(4) }; + /// len += 1; + /// + /// // SAFETY: We only wrote an additional element at the end of the `KVec`'s buffer and + /// // correspondingly increased the length of the `KVec` by one. Otherwise, we construct it + /// // from the exact same raw parts. + /// let v = unsafe { KVec::from_raw_parts(ptr, len, cap) }; + /// + /// assert_eq!(v, [1, 2, 3, 4]); + /// + /// # Ok::<(), Error>(()) + /// ``` + /// + /// # Safety + /// + /// If `T` is a ZST: + /// + /// - `ptr` must be a dangling, well aligned pointer. + /// + /// Otherwise: + /// + /// - `ptr` must have been allocated with the allocator `A`. + /// - `ptr` must satisfy or exceed the alignment requirements of `T`. + /// - `ptr` must point to memory with a size of at least `size_of::() * capacity` bytes. + /// - The allocated size in bytes must not be larger than `isize::MAX`. + /// - `length` must be less than or equal to `capacity`. + /// - The first `length` elements must be initialized values of type `T`. + /// + /// It is also valid to create an empty `Vec` passing a dangling pointer for `ptr` and zero for + /// `cap` and `len`. + pub unsafe fn from_raw_parts(ptr: *mut T, length: usize, capacity: usize) -> Self { + let layout = if Self::is_zst() { + ArrayLayout::empty() + } else { + // SAFETY: By the safety requirements of this function, `capacity * size_of::()` is + // smaller than `isize::MAX`. + unsafe { ArrayLayout::new_unchecked(capacity) } + }; + + // INVARIANT: For ZSTs, we store an empty `ArrayLayout`, all other type invariants are + // covered by the safety requirements of this function. + Self { + // SAFETY: By the safety requirements, `ptr` is either dangling or pointing to a valid + // memory allocation, allocated with `A`. + ptr: unsafe { NonNull::new_unchecked(ptr) }, + layout, + len: length, + _p: PhantomData::, + } + } + + /// Consumes the `Vec` and returns its raw components `pointer`, `length` and `capacity`. + /// + /// This will not run the destructor of the contained elements and for non-ZSTs the allocation + /// will stay alive indefinitely. Use [`Vec::from_raw_parts`] to recover the [`Vec`], drop the + /// elements and free the allocation, if any. + pub fn into_raw_parts(self) -> (*mut T, usize, usize) { + let mut me = ManuallyDrop::new(self); + let len = me.len(); + let capacity = me.capacity(); + let ptr = me.as_mut_ptr(); + (ptr, len, capacity) + } + + /// 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 ZSTs, we can't go higher. + return Err(AllocError); + } + + // We know that `cap <= isize::MAX` because of the type invariants of `Self`. 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 = ArrayLayout::new(new_cap).map_err(|_| AllocError)?; + + // SAFETY: + // - `ptr` is valid because it's either `None` or comes from a previous call to + // `A::realloc`. + // - `self.layout` matches the `ArrayLayout` of the preceding allocation. + let ptr = unsafe { + A::realloc( + Some(self.ptr.cast()), + layout.into(), + self.layout.into(), + flags, + )? + }; + + // INVARIANT: + // - `layout` is some `ArrayLayout::`, + // - `ptr` has been created by `A::realloc` from `layout`. + self.ptr = ptr.cast(); + self.layout = layout; + + 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> { + if n == 0 { + return Ok(()); + } + + self.reserve(n, flags)?; + + let spare = self.spare_capacity_mut(); + + for item in spare.iter_mut().take(n - 1) { + item.write(value.clone()); + } + + // We can write the last element directly without cloning needlessly. + spare[n - 1].write(value); + + // SAFETY: + // - `self.len() + n < self.capacity()` due to the call to reserve above, + // - the loop and the line above initialized the next `n` elements. + unsafe { self.set_len(self.len() + n) }; + + Ok(()) + } + + /// 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> { + self.reserve(other.len(), flags)?; + for (slot, item) in core::iter::zip(self.spare_capacity_mut(), other) { + slot.write(item.clone()); + } + + // SAFETY: + // - `other.len()` spare entries have just been initialized, so it is safe to increase + // the length by the same number. + // - `self.len() + other.len() <= self.capacity()` is guaranteed by the preceding `reserve` + // call. + unsafe { self.set_len(self.len() + other.len()) }; + Ok(()) + } + + /// 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: `self.as_mut_ptr` is guaranteed to be valid by the type invariant. + unsafe { + ptr::drop_in_place(core::ptr::slice_from_raw_parts_mut( + self.as_mut_ptr(), + self.len, + )) + }; + + // SAFETY: + // - `self.ptr` was previously allocated with `A`. + // - `self.layout` matches the `ArrayLayout` of the preceding allocation. + unsafe { A::free(self.ptr.cast(), self.layout.into()) }; + } +} + +impl From> for Vec +where + A: Allocator, +{ + fn from(b: Box<[T; N], A>) -> Vec { + let len = b.len(); + let ptr = Box::into_raw(b); + + // SAFETY: + // - `b` has been allocated with `A`, + // - `ptr` fulfills the alignment requirements for `T`, + // - `ptr` points to memory with at least a size of `size_of::() * len`, + // - all elements within `b` are initialized values of `T`, + // - `len` does not exceed `isize::MAX`. + unsafe { Vec::from_raw_parts(ptr as _, len, len) } + } +} + +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,)*) => { + $( + impl PartialEq<$rhs> for $lhs + where + T: PartialEq, + { + #[inline] + fn eq(&self, other: &$rhs) -> bool { self[..] == other[..] } + } + )* + } +} + +impl_slice_eq! { + [A1: Allocator, A2: Allocator] Vec, Vec, + [A: Allocator] Vec, &[U], + [A: Allocator] Vec, &mut [U], + [A: Allocator] &[T], Vec, + [A: Allocator] &mut [T], Vec, + [A: Allocator] Vec, [U], + [A: Allocator] [T], Vec, + [A: Allocator, const N: usize] Vec, [U; N], + [A: Allocator, const N: usize] Vec, &[U; N], +} -- cgit v1.2.3 From 1d1d223aa3b37c34271aefc2706340d0843bfcb2 Mon Sep 17 00:00:00 2001 From: Danilo Krummrich Date: Fri, 4 Oct 2024 17:41:21 +0200 Subject: rust: alloc: implement `IntoIterator` for `Vec` Implement `IntoIterator` for `Vec`, `Vec`'s `IntoIter` type, as well as `Iterator` for `IntoIter`. `Vec::into_iter` disassembles the `Vec` into its raw parts; additionally, `IntoIter` keeps track of a separate pointer, which is incremented correspondingly as the iterator advances, while the length, or the count of elements, is decremented. This also means that `IntoIter` takes the ownership of the backing buffer and is responsible to drop the remaining elements and free the backing buffer, if it's dropped. Reviewed-by: Alice Ryhl Reviewed-by: Benno Lossin Reviewed-by: Gary Guo Signed-off-by: Danilo Krummrich Link: https://lore.kernel.org/r/20241004154149.93856-18-dakr@kernel.org [ Fixed typos. - Miguel ] Signed-off-by: Miguel Ojeda --- rust/kernel/alloc/kvec.rs | 170 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 170 insertions(+) (limited to 'rust/kernel/alloc') diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs index 8a1d8f414955..4ddc2ca6cd32 100644 --- a/rust/kernel/alloc/kvec.rs +++ b/rust/kernel/alloc/kvec.rs @@ -646,3 +646,173 @@ impl_slice_eq! { [A: Allocator, const N: usize] Vec, [U; N], [A: Allocator, const N: usize] Vec, &[U; N], } + +impl<'a, T, A> IntoIterator for &'a Vec +where + A: Allocator, +{ + type Item = &'a T; + type IntoIter = slice::Iter<'a, T>; + + fn into_iter(self) -> Self::IntoIter { + self.iter() + } +} + +impl<'a, T, A: Allocator> IntoIterator for &'a mut Vec +where + A: Allocator, +{ + type Item = &'a mut T; + type IntoIter = slice::IterMut<'a, T>; + + fn into_iter(self) -> Self::IntoIter { + self.iter_mut() + } +} + +/// An [`Iterator`] 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 +/// [`IntoIterator`] trait). +/// +/// # Examples +/// +/// ``` +/// let v = kernel::kvec![0, 1, 2]?; +/// let iter = v.into_iter(); +/// +/// # Ok::<(), Error>(()) +/// ``` +pub struct IntoIter { + ptr: *mut T, + buf: NonNull, + len: usize, + layout: ArrayLayout, + _p: PhantomData, +} + +impl Iterator for IntoIter +where + A: Allocator, +{ + type Item = T; + + /// # Examples + /// + /// ``` + /// let v = kernel::kvec![1, 2, 3]?; + /// let mut it = v.into_iter(); + /// + /// assert_eq!(it.next(), Some(1)); + /// assert_eq!(it.next(), Some(2)); + /// assert_eq!(it.next(), Some(3)); + /// assert_eq!(it.next(), None); + /// + /// # Ok::<(), Error>(()) + /// ``` + fn next(&mut self) -> Option { + if self.len == 0 { + return None; + } + + let current = self.ptr; + + // SAFETY: We can't overflow; decreasing `self.len` by one every time we advance `self.ptr` + // by one guarantees that. + unsafe { self.ptr = self.ptr.add(1) }; + + self.len -= 1; + + // SAFETY: `current` is guaranteed to point at a valid element within the buffer. + Some(unsafe { current.read() }) + } + + /// # Examples + /// + /// ``` + /// let v: KVec = kernel::kvec![1, 2, 3]?; + /// let mut iter = v.into_iter(); + /// let size = iter.size_hint().0; + /// + /// iter.next(); + /// assert_eq!(iter.size_hint().0, size - 1); + /// + /// iter.next(); + /// assert_eq!(iter.size_hint().0, size - 2); + /// + /// iter.next(); + /// assert_eq!(iter.size_hint().0, size - 3); + /// + /// # Ok::<(), Error>(()) + /// ``` + fn size_hint(&self) -> (usize, Option) { + (self.len, Some(self.len)) + } +} + +impl Drop for IntoIter +where + A: Allocator, +{ + fn drop(&mut self) { + // SAFETY: `self.ptr` is guaranteed to be valid by the type invariant. + unsafe { ptr::drop_in_place(ptr::slice_from_raw_parts_mut(self.ptr, self.len)) }; + + // SAFETY: + // - `self.buf` was previously allocated with `A`. + // - `self.layout` matches the `ArrayLayout` of the preceding allocation. + unsafe { A::free(self.buf.cast(), self.layout.into()) }; + } +} + +impl IntoIterator for Vec +where + A: Allocator, +{ + type Item = T; + type IntoIter = IntoIter; + + /// Consumes the `Vec` and creates an `Iterator`, which moves each value out of the + /// vector (from start to end). + /// + /// # Examples + /// + /// ``` + /// let v = kernel::kvec![1, 2]?; + /// let mut v_iter = v.into_iter(); + /// + /// let first_element: Option = v_iter.next(); + /// + /// assert_eq!(first_element, Some(1)); + /// assert_eq!(v_iter.next(), Some(2)); + /// assert_eq!(v_iter.next(), None); + /// + /// # Ok::<(), Error>(()) + /// ``` + /// + /// ``` + /// let v = kernel::kvec![]; + /// let mut v_iter = v.into_iter(); + /// + /// let first_element: Option = v_iter.next(); + /// + /// assert_eq!(first_element, None); + /// + /// # Ok::<(), Error>(()) + /// ``` + #[inline] + fn into_iter(self) -> Self::IntoIter { + let buf = self.ptr; + let layout = self.layout; + let (ptr, len, _) = self.into_raw_parts(); + + IntoIter { + ptr, + buf, + len, + layout, + _p: PhantomData::, + } + } +} -- cgit v1.2.3 From 93e602310f87b7b515b86a8f919cc0799387e5c3 Mon Sep 17 00:00:00 2001 From: Danilo Krummrich Date: Fri, 4 Oct 2024 17:41:22 +0200 Subject: rust: alloc: implement `collect` for `IntoIter` Currently, we can't implement `FromIterator`. There are a couple of issues with this trait in the kernel, namely: - Rust's specialization feature is unstable. This prevents us to optimize for the special case where `I::IntoIter` equals `Vec`'s `IntoIter` type. - We also can't use `I::IntoIter`'s type ID either to work around this, since `FromIterator` doesn't require this type to be `'static`. - `FromIterator::from_iter` does return `Self` instead of `Result`, hence we can't properly handle allocation failures. - Neither `Iterator::collect` nor `FromIterator::from_iter` can handle additional allocation flags. Instead, provide `IntoIter::collect`, such that we can at least convert `IntoIter` into a `Vec` again. Reviewed-by: Alice Ryhl Reviewed-by: Benno Lossin Signed-off-by: Danilo Krummrich Link: https://lore.kernel.org/r/20241004154149.93856-19-dakr@kernel.org [ Added newline in documentation, changed case of section to be consistent with an existing one, fixed typo. - Miguel ] Signed-off-by: Miguel Ojeda --- rust/kernel/alloc/kvec.rs | 95 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 95 insertions(+) (limited to 'rust/kernel/alloc') diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs index 4ddc2ca6cd32..ae9d072741ce 100644 --- a/rust/kernel/alloc/kvec.rs +++ b/rust/kernel/alloc/kvec.rs @@ -692,6 +692,101 @@ pub struct IntoIter { _p: PhantomData, } +impl IntoIter +where + A: Allocator, +{ + fn into_raw_parts(self) -> (*mut T, NonNull, usize, usize) { + let me = ManuallyDrop::new(self); + let ptr = me.ptr; + let buf = me.buf; + let len = me.len; + let cap = me.layout.len(); + (ptr, buf, len, cap) + } + + /// Same as `Iterator::collect` but specialized for `Vec`'s `IntoIter`. + /// + /// # Examples + /// + /// ``` + /// let v = kernel::kvec![1, 2, 3]?; + /// let mut it = v.into_iter(); + /// + /// assert_eq!(it.next(), Some(1)); + /// + /// let v = it.collect(GFP_KERNEL); + /// assert_eq!(v, [2, 3]); + /// + /// # Ok::<(), Error>(()) + /// ``` + /// + /// # Implementation details + /// + /// Currently, we can't implement `FromIterator`. There are a couple of issues with this trait + /// in the kernel, namely: + /// + /// - Rust's specialization feature is unstable. This prevents us to optimize for the special + /// case where `I::IntoIter` equals `Vec`'s `IntoIter` type. + /// - We also can't use `I::IntoIter`'s type ID either to work around this, since `FromIterator` + /// doesn't require this type to be `'static`. + /// - `FromIterator::from_iter` does return `Self` instead of `Result`, hence + /// we can't properly handle allocation failures. + /// - Neither `Iterator::collect` nor `FromIterator::from_iter` can handle additional allocation + /// flags. + /// + /// Instead, provide `IntoIter::collect`, such that we can at least convert a `IntoIter` into a + /// `Vec` again. + /// + /// Note that `IntoIter::collect` doesn't require `Flags`, since it re-uses the existing backing + /// buffer. However, this backing buffer may be shrunk to the actual count of elements. + pub fn collect(self, flags: Flags) -> Vec { + let old_layout = self.layout; + let (mut ptr, buf, len, mut cap) = self.into_raw_parts(); + let has_advanced = ptr != buf.as_ptr(); + + if has_advanced { + // Copy the contents we have advanced to at the beginning of the buffer. + // + // SAFETY: + // - `ptr` is valid for reads of `len * size_of::()` bytes, + // - `buf.as_ptr()` is valid for writes of `len * size_of::()` bytes, + // - `ptr` and `buf.as_ptr()` are not be subject to aliasing restrictions relative to + // each other, + // - both `ptr` and `buf.ptr()` are properly aligned. + unsafe { ptr::copy(ptr, buf.as_ptr(), len) }; + ptr = buf.as_ptr(); + + // SAFETY: `len` is guaranteed to be smaller than `self.layout.len()`. + let layout = unsafe { ArrayLayout::::new_unchecked(len) }; + + // SAFETY: `buf` points to the start of the backing buffer and `len` is guaranteed to be + // smaller than `cap`. Depending on `alloc` this operation may shrink the buffer or leaves + // it as it is. + ptr = match unsafe { + A::realloc(Some(buf.cast()), layout.into(), old_layout.into(), flags) + } { + // If we fail to shrink, which likely can't even happen, continue with the existing + // buffer. + Err(_) => ptr, + Ok(ptr) => { + cap = len; + ptr.as_ptr().cast() + } + }; + } + + // SAFETY: If the iterator has been advanced, the advanced elements have been copied to + // the beginning of the buffer and `len` has been adjusted accordingly. + // + // - `ptr` is guaranteed to point to the start of the backing buffer. + // - `cap` is either the original capacity or, after shrinking the buffer, equal to `len`. + // - `alloc` is guaranteed to be unchanged since `into_iter` has been called on the original + // `Vec`. + unsafe { Vec::from_raw_parts(ptr, len, cap) } + } +} + impl Iterator for IntoIter where A: Allocator, -- cgit v1.2.3 From 405966efc789888c3e1a53cd09d2c2b338064438 Mon Sep 17 00:00:00 2001 From: Danilo Krummrich Date: Fri, 4 Oct 2024 17:41:24 +0200 Subject: rust: alloc: remove `VecExt` extension Now that all existing `Vec` users were moved to the kernel `Vec` type, remove the `VecExt` extension. Reviewed-by: Alice Ryhl Reviewed-by: Benno Lossin Reviewed-by: Gary Guo Signed-off-by: Danilo Krummrich Link: https://lore.kernel.org/r/20241004154149.93856-21-dakr@kernel.org Signed-off-by: Miguel Ojeda --- rust/kernel/alloc/vec_ext.rs | 185 ------------------------------------------- 1 file changed, 185 deletions(-) delete mode 100644 rust/kernel/alloc/vec_ext.rs (limited to 'rust/kernel/alloc') diff --git a/rust/kernel/alloc/vec_ext.rs b/rust/kernel/alloc/vec_ext.rs deleted file mode 100644 index 1297a4be32e8..000000000000 --- a/rust/kernel/alloc/vec_ext.rs +++ /dev/null @@ -1,185 +0,0 @@ -// SPDX-License-Identifier: GPL-2.0 - -//! Extensions to [`Vec`] for fallible allocations. - -use super::{AllocError, Flags}; -use alloc::vec::Vec; - -/// Extensions to [`Vec`]. -pub trait VecExt: Sized { - /// Creates a new [`Vec`] instance with at least the given capacity. - /// - /// # Examples - /// - /// ``` - /// let v = Vec::::with_capacity(20, GFP_KERNEL)?; - /// - /// assert!(v.capacity() >= 20); - /// # Ok::<(), Error>(()) - /// ``` - fn with_capacity(capacity: usize, flags: Flags) -> Result; - - /// Appends an element to the back of the [`Vec`] instance. - /// - /// # Examples - /// - /// ``` - /// let mut v = Vec::new(); - /// v.push(1, GFP_KERNEL)?; - /// assert_eq!(&v, &[1]); - /// - /// v.push(2, GFP_KERNEL)?; - /// assert_eq!(&v, &[1, 2]); - /// # Ok::<(), Error>(()) - /// ``` - fn push(&mut self, v: T, flags: Flags) -> Result<(), AllocError>; - - /// Pushes clones of the elements of slice into the [`Vec`] instance. - /// - /// # Examples - /// - /// ``` - /// let mut v = Vec::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>(()) - /// ``` - fn extend_from_slice(&mut self, other: &[T], flags: Flags) -> Result<(), AllocError> - where - T: Clone; - - /// Ensures that the capacity exceeds the length by at least `additional` elements. - /// - /// # Examples - /// - /// ``` - /// let mut v = Vec::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>(()) - /// ``` - fn reserve(&mut self, additional: usize, flags: Flags) -> Result<(), AllocError>; -} - -impl VecExt for Vec { - fn with_capacity(capacity: usize, flags: Flags) -> Result { - let mut v = Vec::new(); - >::reserve(&mut v, capacity, flags)?; - Ok(v) - } - - fn push(&mut self, v: T, flags: Flags) -> Result<(), AllocError> { - >::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(()) - } - - fn extend_from_slice(&mut self, other: &[T], flags: Flags) -> Result<(), AllocError> - where - T: Clone, - { - >::reserve(self, 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(()) - } - - #[cfg(any(test, testlib))] - fn reserve(&mut self, additional: usize, _flags: Flags) -> Result<(), AllocError> { - Vec::reserve(self, additional); - Ok(()) - } - - #[cfg(not(any(test, testlib)))] - 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 core::mem::size_of::() == 0 { - // 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)?; - - let (old_ptr, len, cap) = destructure(self); - - // We need to make sure that `ptr` is either NULL or comes from a previous call to - // `krealloc_aligned`. 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 { - core::ptr::null_mut() - } else { - old_ptr - }; - - // SAFETY: `ptr` is valid because it's either NULL or comes from a previous call to - // `krealloc_aligned`. We also verified that the type is not a ZST. - let new_ptr = unsafe { super::allocator::krealloc_aligned(ptr.cast(), layout, flags) }; - if new_ptr.is_null() { - // SAFETY: We are just rebuilding the existing `Vec` with no changes. - unsafe { rebuild(self, old_ptr, len, cap) }; - Err(AllocError) - } else { - // SAFETY: `ptr` has been reallocated with the layout for `new_cap` elements. New cap - // is greater than `cap`, so it continues to be >= `len`. - unsafe { rebuild(self, new_ptr.cast::(), len, new_cap) }; - Ok(()) - } - } -} - -#[cfg(not(any(test, testlib)))] -fn destructure(v: &mut Vec) -> (*mut T, usize, usize) { - let mut tmp = Vec::new(); - core::mem::swap(&mut tmp, v); - let mut tmp = core::mem::ManuallyDrop::new(tmp); - let len = tmp.len(); - let cap = tmp.capacity(); - (tmp.as_mut_ptr(), len, cap) -} - -/// Rebuilds a `Vec` from a pointer, length, and capacity. -/// -/// # Safety -/// -/// The same as [`Vec::from_raw_parts`]. -#[cfg(not(any(test, testlib)))] -unsafe fn rebuild(v: &mut Vec, ptr: *mut T, len: usize, cap: usize) { - // SAFETY: The safety requirements from this function satisfy those of `from_raw_parts`. - let mut tmp = unsafe { Vec::from_raw_parts(ptr, len, cap) }; - core::mem::swap(&mut tmp, v); -} -- cgit v1.2.3 From dd09538fb4093176a818fcecd45114430cc5840f Mon Sep 17 00:00:00 2001 From: Danilo Krummrich Date: Fri, 4 Oct 2024 17:41:29 +0200 Subject: rust: alloc: implement `Cmalloc` in module allocator_test 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. Reviewed-by: Benno Lossin Reviewed-by: Gary Guo Signed-off-by: Danilo Krummrich Link: https://lore.kernel.org/r/20241004154149.93856-26-dakr@kernel.org [ Removed the temporary `allow(dead_code)` as discussed in the list and fixed typo, added backticks. - Miguel ] Signed-off-by: Miguel Ojeda --- rust/kernel/alloc/allocator_test.rs | 89 +++++++++++++++++++++++++++++++++---- 1 file changed, 81 insertions(+), 8 deletions(-) (limited to 'rust/kernel/alloc') diff --git a/rust/kernel/alloc/allocator_test.rs b/rust/kernel/alloc/allocator_test.rs index bd0cbcd93e52..54ca85964d4a 100644 --- a/rust/kernel/alloc/allocator_test.rs +++ b/rust/kernel/alloc/allocator_test.rs @@ -1,22 +1,95 @@ // 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::{AllocError, Allocator, Flags}; +use super::{flags::*, AllocError, Allocator, Flags}; use core::alloc::Layout; +use core::cmp; +use core::ptr; use core::ptr::NonNull; -pub struct Kmalloc; +/// The userspace allocator based on libc. +pub struct Cmalloc; + +pub type Kmalloc = Cmalloc; pub type Vmalloc = Kmalloc; pub type KVmalloc = Kmalloc; -unsafe impl Allocator for Kmalloc { +extern "C" { + #[link_name = "aligned_alloc"] + fn libc_aligned_alloc(align: usize, size: usize) -> *mut core::ffi::c_void; + + #[link_name = "free"] + fn libc_free(ptr: *mut core::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>, - _layout: Layout, - _old_layout: Layout, - _flags: Flags, + ptr: Option>, + layout: Layout, + old_layout: Layout, + flags: Flags, ) -> Result, AllocError> { - panic!(); + 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, + )); + } + + // 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()) } as *mut 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())) } } -- cgit v1.2.3 From 392e34b6bc22077ef63abf62387ea3e9f39418c1 Mon Sep 17 00:00:00 2001 From: Danilo Krummrich Date: Fri, 4 Oct 2024 17:41:32 +0200 Subject: kbuild: rust: remove the `alloc` crate and `GlobalAlloc` Now that we have our own `Allocator`, `Box` and `Vec` types we can remove Rust's `alloc` crate and the `new_uninit` unstable feature. Also remove `Kmalloc`'s `GlobalAlloc` implementation -- we can't remove this in a separate patch, since the `alloc` crate requires a `#[global_allocator]` to set, that implements `GlobalAlloc`. Signed-off-by: Danilo Krummrich Link: https://lore.kernel.org/r/20241004154149.93856-29-dakr@kernel.org Signed-off-by: Miguel Ojeda --- rust/kernel/alloc/allocator.rs | 65 ++---------------------------------------- 1 file changed, 2 insertions(+), 63 deletions(-) (limited to 'rust/kernel/alloc') diff --git a/rust/kernel/alloc/allocator.rs b/rust/kernel/alloc/allocator.rs index f8a1f0feb25d..a041bbfdabec 100644 --- a/rust/kernel/alloc/allocator.rs +++ b/rust/kernel/alloc/allocator.rs @@ -8,8 +8,8 @@ //! //! Reference: -use super::{flags::*, Flags}; -use core::alloc::{GlobalAlloc, Layout}; +use super::Flags; +use core::alloc::Layout; use core::ptr; use core::ptr::NonNull; @@ -54,23 +54,6 @@ fn aligned_size(new_layout: Layout) -> usize { layout.size() } -/// Calls `krealloc` with a proper size to alloc a new object aligned to `new_layout`'s alignment. -/// -/// # Safety -/// -/// - `ptr` can be either null or a pointer which has been allocated by this allocator. -/// - `new_layout` must have a non-zero size. -pub(crate) unsafe fn krealloc_aligned(ptr: *mut u8, new_layout: Layout, flags: Flags) -> *mut u8 { - let size = aligned_size(new_layout); - - // SAFETY: - // - `ptr` is either null or a pointer returned from a previous `k{re}alloc()` by the - // function safety requirement. - // - `size` is greater than 0 since it's from `layout.size()` (which cannot be zero according - // to the function safety requirement) - unsafe { bindings::krealloc(ptr as *const core::ffi::c_void, size, flags.0) as *mut u8 } -} - /// # Invariants /// /// One of the following: `krealloc`, `vrealloc`, `kvrealloc`. @@ -156,43 +139,6 @@ unsafe impl Allocator for Kmalloc { } } -// SAFETY: TODO. -unsafe impl GlobalAlloc for Kmalloc { - unsafe fn alloc(&self, layout: Layout) -> *mut u8 { - // SAFETY: `ptr::null_mut()` is null and `layout` has a non-zero size by the function safety - // requirement. - unsafe { krealloc_aligned(ptr::null_mut(), layout, GFP_KERNEL) } - } - - unsafe fn dealloc(&self, ptr: *mut u8, _layout: Layout) { - // SAFETY: TODO. - unsafe { - bindings::kfree(ptr as *const core::ffi::c_void); - } - } - - unsafe fn realloc(&self, ptr: *mut u8, layout: Layout, new_size: usize) -> *mut u8 { - // SAFETY: - // - `new_size`, when rounded up to the nearest multiple of `layout.align()`, will not - // overflow `isize` by the function safety requirement. - // - `layout.align()` is a proper alignment (i.e. not zero and must be a power of two). - let layout = unsafe { Layout::from_size_align_unchecked(new_size, layout.align()) }; - - // SAFETY: - // - `ptr` is either null or a pointer allocated by this allocator by the function safety - // requirement. - // - the size of `layout` is not zero because `new_size` is not zero by the function safety - // requirement. - unsafe { krealloc_aligned(ptr, layout, GFP_KERNEL) } - } - - unsafe fn alloc_zeroed(&self, layout: Layout) -> *mut u8 { - // SAFETY: `ptr::null_mut()` is null and `layout` has a non-zero size by the function safety - // requirement. - unsafe { krealloc_aligned(ptr::null_mut(), layout, GFP_KERNEL | __GFP_ZERO) } - } -} - // SAFETY: `realloc` delegates to `ReallocFunc::call`, which guarantees that // - memory remains valid until it is explicitly freed, // - passing a pointer to a valid memory allocation is OK, @@ -240,10 +186,3 @@ unsafe impl Allocator for KVmalloc { unsafe { ReallocFunc::KVREALLOC.call(ptr, layout, old_layout, flags) } } } - -#[global_allocator] -static ALLOCATOR: Kmalloc = Kmalloc; - -// See . -#[no_mangle] -static __rust_no_alloc_shim_is_unstable: u8 = 0; -- cgit v1.2.3 From d072acda4862f095ec9056979b654cc06a22cc68 Mon Sep 17 00:00:00 2001 From: Gary Guo Date: Fri, 13 Sep 2024 22:29:23 +0100 Subject: rust: use custom FFI integer types Currently FFI integer types are defined in libcore. This commit creates the `ffi` crate and asks bindgen to use that crate for FFI integer types instead of `core::ffi`. This commit is preparatory and no type changes are made in this commit yet. Signed-off-by: Gary Guo Link: https://lore.kernel.org/r/20240913213041.395655-4-gary@garyguo.net [ Added `rustdoc`, `rusttest` and KUnit tests support. Rebased on top of `rust-next` (e.g. migrated more `core::ffi` cases). Reworded crate docs slightly and formatted. - Miguel ] Signed-off-by: Miguel Ojeda --- rust/kernel/alloc/allocator.rs | 2 +- rust/kernel/alloc/allocator_test.rs | 4 ++-- rust/kernel/alloc/kbox.rs | 12 ++++++------ 3 files changed, 9 insertions(+), 9 deletions(-) (limited to 'rust/kernel/alloc') diff --git a/rust/kernel/alloc/allocator.rs b/rust/kernel/alloc/allocator.rs index a041bbfdabec..439985e29fbc 100644 --- a/rust/kernel/alloc/allocator.rs +++ b/rust/kernel/alloc/allocator.rs @@ -58,7 +58,7 @@ fn aligned_size(new_layout: Layout) -> usize { /// /// One of the following: `krealloc`, `vrealloc`, `kvrealloc`. struct ReallocFunc( - unsafe extern "C" fn(*const core::ffi::c_void, usize, u32) -> *mut core::ffi::c_void, + unsafe extern "C" fn(*const crate::ffi::c_void, usize, u32) -> *mut crate::ffi::c_void, ); impl ReallocFunc { diff --git a/rust/kernel/alloc/allocator_test.rs b/rust/kernel/alloc/allocator_test.rs index 54ca85964d4a..e3240d16040b 100644 --- a/rust/kernel/alloc/allocator_test.rs +++ b/rust/kernel/alloc/allocator_test.rs @@ -24,10 +24,10 @@ pub type KVmalloc = Kmalloc; extern "C" { #[link_name = "aligned_alloc"] - fn libc_aligned_alloc(align: usize, size: usize) -> *mut core::ffi::c_void; + fn libc_aligned_alloc(align: usize, size: usize) -> *mut crate::ffi::c_void; #[link_name = "free"] - fn libc_free(ptr: *mut core::ffi::c_void); + fn libc_free(ptr: *mut crate::ffi::c_void); } // SAFETY: diff --git a/rust/kernel/alloc/kbox.rs b/rust/kernel/alloc/kbox.rs index d69c32496b86..9ce414361c2c 100644 --- a/rust/kernel/alloc/kbox.rs +++ b/rust/kernel/alloc/kbox.rs @@ -355,17 +355,17 @@ where { type Borrowed<'a> = &'a T; - fn into_foreign(self) -> *const core::ffi::c_void { + fn into_foreign(self) -> *const crate::ffi::c_void { Box::into_raw(self) as _ } - unsafe fn from_foreign(ptr: *const core::ffi::c_void) -> Self { + unsafe fn from_foreign(ptr: *const crate::ffi::c_void) -> Self { // SAFETY: The safety requirements of this function ensure that `ptr` comes from a previous // call to `Self::into_foreign`. unsafe { Box::from_raw(ptr as _) } } - unsafe fn borrow<'a>(ptr: *const core::ffi::c_void) -> &'a T { + unsafe fn borrow<'a>(ptr: *const crate::ffi::c_void) -> &'a T { // SAFETY: The safety requirements of this method ensure that the object remains alive and // immutable for the duration of 'a. unsafe { &*ptr.cast() } @@ -378,18 +378,18 @@ where { type Borrowed<'a> = Pin<&'a T>; - fn into_foreign(self) -> *const core::ffi::c_void { + fn into_foreign(self) -> *const crate::ffi::c_void { // SAFETY: We are still treating the box as pinned. Box::into_raw(unsafe { Pin::into_inner_unchecked(self) }) as _ } - unsafe fn from_foreign(ptr: *const core::ffi::c_void) -> Self { + unsafe fn from_foreign(ptr: *const crate::ffi::c_void) -> Self { // SAFETY: The safety requirements of this function ensure that `ptr` comes from a previous // call to `Self::into_foreign`. unsafe { Pin::new_unchecked(Box::from_raw(ptr as _)) } } - unsafe fn borrow<'a>(ptr: *const core::ffi::c_void) -> Pin<&'a T> { + unsafe fn borrow<'a>(ptr: *const crate::ffi::c_void) -> Pin<&'a T> { // SAFETY: The safety requirements for this function ensure that the object is still alive, // so it is safe to dereference the raw pointer. // The safety requirements of `from_foreign` also ensure that the object remains alive for -- cgit v1.2.3 From b7ed2b6f4e8d7f64649795e76ee9db67300de8eb Mon Sep 17 00:00:00 2001 From: Asahi Lina Date: Sat, 23 Nov 2024 19:29:38 +0900 Subject: rust: alloc: Fix `ArrayLayout` allocations We were accidentally allocating a layout for the *square* of the object size due to a variable shadowing mishap. Fixes memory bloat and page allocation failures in drm/asahi. Reported-by: Janne Grunau Fixes: 9e7bbfa18276 ("rust: alloc: introduce `ArrayLayout`") Signed-off-by: Asahi Lina Acked-by: Danilo Krummrich Reviewed-by: Neal Gompa Link: https://lore.kernel.org/r/20241123-rust-fix-arraylayout-v1-1-197e64c95bd4@asahilina.net Signed-off-by: Miguel Ojeda --- rust/kernel/alloc/layout.rs | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'rust/kernel/alloc') diff --git a/rust/kernel/alloc/layout.rs b/rust/kernel/alloc/layout.rs index 7e0c2f46157b..4b3cd7fdc816 100644 --- a/rust/kernel/alloc/layout.rs +++ b/rust/kernel/alloc/layout.rs @@ -45,7 +45,7 @@ impl ArrayLayout { /// When `len * size_of::()` overflows or when `len * size_of::() > isize::MAX`. pub const fn new(len: usize) -> Result { match len.checked_mul(core::mem::size_of::()) { - Some(len) if len <= ISIZE_MAX => { + Some(size) if size <= ISIZE_MAX => { // INVARIANT: We checked above that `len * size_of::() <= isize::MAX`. Ok(Self { len, -- cgit v1.2.3