From 7760b6421b6c1b49550885ecdfa9cf720ead6eed Mon Sep 17 00:00:00 2001 From: Vitaly Wool Date: Wed, 6 Aug 2025 14:55:22 +0200 Subject: rust: add support for NUMA ids in allocations Add a new type to support specifying NUMA identifiers in Rust allocators and extend the allocators to have NUMA id as a parameter. Thus, modify ReallocFunc to use the new extended realloc primitives from the C side of the kernel (i.e. k[v]realloc_node_align/vrealloc_node_align) and add the new function alloc_node to the Allocator trait while keeping the existing one (alloc) for backward compatibility. This will allow to specify node to use for allocation of e. g. {KV}Box, as well as for future NUMA aware users of the API. [ojeda@kernel.org: fix missing import needed for `rusttest`] Link: https://lkml.kernel.org/r/20250816210214.2729269-1-ojeda@kernel.org Link: https://lkml.kernel.org/r/20250806125522.1726992-1-vitaly.wool@konsulko.se Signed-off-by: Vitaly Wool Signed-off-by: Miguel Ojeda Acked-by: Danilo Krummrich Acked-by: Alice Ryhl Cc: Herbert Xu Cc: Jann Horn Cc: Kent Overstreet Cc: Liam Howlett Cc: Lorenzo Stoakes Cc: Uladzislau Rezki (Sony) Cc: Vlastimil Babka Cc: Miguel Ojeda Signed-off-by: Andrew Morton --- rust/kernel/alloc.rs | 54 +++++++++++++++++++++++++++++++++---- rust/kernel/alloc/allocator.rs | 35 +++++++++++++++--------- rust/kernel/alloc/allocator_test.rs | 3 ++- rust/kernel/alloc/kbox.rs | 4 +-- rust/kernel/alloc/kvec.rs | 11 ++++++-- 5 files changed, 84 insertions(+), 23 deletions(-) (limited to 'rust/kernel') diff --git a/rust/kernel/alloc.rs b/rust/kernel/alloc.rs index a2c49e5494d3..b39c279236f5 100644 --- a/rust/kernel/alloc.rs +++ b/rust/kernel/alloc.rs @@ -28,6 +28,8 @@ pub use self::kvec::Vec; /// Indicates an allocation error. #[derive(Copy, Clone, PartialEq, Eq, Debug)] pub struct AllocError; + +use crate::error::{code::EINVAL, Result}; use core::{alloc::Layout, ptr::NonNull}; /// Flags to be used when allocating memory. @@ -115,6 +117,31 @@ pub mod flags { pub const __GFP_NOWARN: Flags = Flags(bindings::__GFP_NOWARN); } +/// Non Uniform Memory Access (NUMA) node identifier. +#[derive(Clone, Copy, PartialEq)] +pub struct NumaNode(i32); + +impl NumaNode { + /// Create a new NUMA node identifier (non-negative integer). + /// + /// Returns [`EINVAL`] if a negative id or an id exceeding [`bindings::MAX_NUMNODES`] is + /// specified. + pub fn new(node: i32) -> Result { + // MAX_NUMNODES never exceeds 2**10 because NODES_SHIFT is 0..10. + if node < 0 || node >= bindings::MAX_NUMNODES as i32 { + return Err(EINVAL); + } + Ok(Self(node)) + } +} + +/// Specify necessary constant to pass the information to Allocator that the caller doesn't care +/// about the NUMA node to allocate memory from. +impl NumaNode { + /// No node preference. + pub const NO_NODE: NumaNode = NumaNode(bindings::NUMA_NO_NODE); +} + /// The kernel's [`Allocator`] trait. /// /// An implementation of [`Allocator`] can allocate, re-allocate and free memory buffers described @@ -137,7 +164,7 @@ pub mod flags { /// - Implementers must ensure that all trait functions abide by the guarantees documented in the /// `# Guarantees` sections. pub unsafe trait Allocator { - /// Allocate memory based on `layout` and `flags`. + /// Allocate memory based on `layout`, `flags` and `nid`. /// /// On success, returns a buffer represented as `NonNull<[u8]>` that satisfies the layout /// constraints (i.e. minimum size and alignment as specified by `layout`). @@ -153,13 +180,21 @@ pub unsafe trait Allocator { /// /// Additionally, `Flags` are honored as documented in /// . - fn alloc(layout: Layout, flags: Flags) -> Result, AllocError> { + fn alloc(layout: Layout, flags: Flags, nid: NumaNode) -> Result, AllocError> { // SAFETY: Passing `None` to `realloc` is valid by its safety requirements and asks for a // new memory allocation. - unsafe { Self::realloc(None, layout, Layout::new::<()>(), flags) } + unsafe { Self::realloc(None, layout, Layout::new::<()>(), flags, nid) } } - /// Re-allocate an existing memory allocation to satisfy the requested `layout`. + /// Re-allocate an existing memory allocation to satisfy the requested `layout` and + /// a specific NUMA node request to allocate the memory for. + /// + /// Systems employing a Non Uniform Memory Access (NUMA) architecture contain collections of + /// hardware resources including processors, memory, and I/O buses, that comprise what is + /// commonly known as a NUMA node. + /// + /// `nid` stands for NUMA id, i. e. NUMA node identifier, which is a non-negative integer + /// if a node needs to be specified, or [`NumaNode::NO_NODE`] if the caller doesn't care. /// /// If the requested size is zero, `realloc` behaves equivalent to `free`. /// @@ -196,6 +231,7 @@ pub unsafe trait Allocator { layout: Layout, old_layout: Layout, flags: Flags, + nid: NumaNode, ) -> Result, AllocError>; /// Free an existing memory allocation. @@ -211,7 +247,15 @@ pub unsafe trait Allocator { // SAFETY: The caller guarantees that `ptr` points at a valid allocation created by this // allocator. We are passing a `Layout` with the smallest possible alignment, so it is // smaller than or equal to the alignment previously used with this allocation. - let _ = unsafe { Self::realloc(Some(ptr), Layout::new::<()>(), layout, Flags(0)) }; + let _ = unsafe { + Self::realloc( + Some(ptr), + Layout::new::<()>(), + layout, + Flags(0), + NumaNode::NO_NODE, + ) + }; } } diff --git a/rust/kernel/alloc/allocator.rs b/rust/kernel/alloc/allocator.rs index 2692cf90c948..14510a9e4502 100644 --- a/rust/kernel/alloc/allocator.rs +++ b/rust/kernel/alloc/allocator.rs @@ -13,7 +13,7 @@ use core::alloc::Layout; use core::ptr; use core::ptr::NonNull; -use crate::alloc::{AllocError, Allocator}; +use crate::alloc::{AllocError, Allocator, NumaNode}; use crate::bindings; use crate::pr_warn; @@ -45,20 +45,25 @@ pub struct KVmalloc; /// # Invariants /// -/// One of the following: `krealloc`, `vrealloc`, `kvrealloc`. +/// One of the following: `krealloc_node`, `vrealloc_node`, `kvrealloc_node`. struct ReallocFunc( - unsafe extern "C" fn(*const crate::ffi::c_void, usize, u32) -> *mut crate::ffi::c_void, + unsafe extern "C" fn( + *const crate::ffi::c_void, + usize, + u32, + crate::ffi::c_int, + ) -> *mut crate::ffi::c_void, ); impl ReallocFunc { - // INVARIANT: `krealloc` satisfies the type invariants. - const KREALLOC: Self = Self(bindings::krealloc); + // INVARIANT: `krealloc_node` satisfies the type invariants. + const KREALLOC: Self = Self(bindings::krealloc_node); - // INVARIANT: `vrealloc` satisfies the type invariants. - const VREALLOC: Self = Self(bindings::vrealloc); + // INVARIANT: `vrealloc_node` satisfies the type invariants. + const VREALLOC: Self = Self(bindings::vrealloc_node); - // INVARIANT: `kvrealloc` satisfies the type invariants. - const KVREALLOC: Self = Self(bindings::kvrealloc); + // INVARIANT: `kvrealloc_node` satisfies the type invariants. + const KVREALLOC: Self = Self(bindings::kvrealloc_node); /// # Safety /// @@ -76,6 +81,7 @@ impl ReallocFunc { layout: Layout, old_layout: Layout, flags: Flags, + nid: NumaNode, ) -> Result, AllocError> { let size = layout.size(); let ptr = match ptr { @@ -99,7 +105,7 @@ impl ReallocFunc { // - Those functions provide the guarantees of this function. let raw_ptr = unsafe { // If `size == 0` and `ptr != NULL` the memory behind the pointer is freed. - self.0(ptr.cast(), size, flags.0).cast() + self.0(ptr.cast(), size, flags.0, nid.0).cast() }; let ptr = if size == 0 { @@ -134,11 +140,12 @@ unsafe impl Allocator for Kmalloc { layout: Layout, old_layout: Layout, flags: Flags, + nid: NumaNode, ) -> Result, AllocError> { let layout = Kmalloc::aligned_layout(layout); // SAFETY: `ReallocFunc::call` has the same safety requirements as `Allocator::realloc`. - unsafe { ReallocFunc::KREALLOC.call(ptr, layout, old_layout, flags) } + unsafe { ReallocFunc::KREALLOC.call(ptr, layout, old_layout, flags, nid) } } } @@ -153,6 +160,7 @@ unsafe impl Allocator for Vmalloc { layout: Layout, old_layout: Layout, flags: Flags, + nid: NumaNode, ) -> Result, AllocError> { // TODO: Support alignments larger than PAGE_SIZE. if layout.align() > bindings::PAGE_SIZE { @@ -162,7 +170,7 @@ unsafe impl Allocator for Vmalloc { // SAFETY: If not `None`, `ptr` is guaranteed to point to valid memory, which was previously // allocated with this `Allocator`. - unsafe { ReallocFunc::VREALLOC.call(ptr, layout, old_layout, flags) } + unsafe { ReallocFunc::VREALLOC.call(ptr, layout, old_layout, flags, nid) } } } @@ -177,6 +185,7 @@ unsafe impl Allocator for KVmalloc { layout: Layout, old_layout: Layout, flags: Flags, + nid: NumaNode, ) -> Result, AllocError> { // `KVmalloc` may use the `Kmalloc` backend, hence we have to enforce a `Kmalloc` // compatible layout. @@ -190,6 +199,6 @@ unsafe impl Allocator for KVmalloc { // SAFETY: If not `None`, `ptr` is guaranteed to point to valid memory, which was previously // allocated with this `Allocator`. - unsafe { ReallocFunc::KVREALLOC.call(ptr, layout, old_layout, flags) } + unsafe { ReallocFunc::KVREALLOC.call(ptr, layout, old_layout, flags, nid) } } } diff --git a/rust/kernel/alloc/allocator_test.rs b/rust/kernel/alloc/allocator_test.rs index 90dd987d40e4..2e61cdbd2303 100644 --- a/rust/kernel/alloc/allocator_test.rs +++ b/rust/kernel/alloc/allocator_test.rs @@ -9,7 +9,7 @@ #![allow(missing_docs)] -use super::{flags::*, AllocError, Allocator, Flags}; +use super::{flags::*, AllocError, Allocator, Flags, NumaNode}; use core::alloc::Layout; use core::cmp; use core::ptr; @@ -51,6 +51,7 @@ unsafe impl Allocator for Cmalloc { layout: Layout, old_layout: Layout, flags: Flags, + _nid: NumaNode, ) -> Result, AllocError> { let src = match ptr { Some(src) => { diff --git a/rust/kernel/alloc/kbox.rs b/rust/kernel/alloc/kbox.rs index 856d05aa60f1..1fef9beb57c8 100644 --- a/rust/kernel/alloc/kbox.rs +++ b/rust/kernel/alloc/kbox.rs @@ -4,7 +4,7 @@ #[allow(unused_imports)] // Used in doc comments. use super::allocator::{KVmalloc, Kmalloc, Vmalloc}; -use super::{AllocError, Allocator, Flags}; +use super::{AllocError, Allocator, Flags, NumaNode}; use core::alloc::Layout; use core::borrow::{Borrow, BorrowMut}; use core::fmt; @@ -273,7 +273,7 @@ where /// ``` pub fn new_uninit(flags: Flags) -> Result, A>, AllocError> { let layout = Layout::new::>(); - let ptr = A::alloc(layout, flags)?; + let ptr = A::alloc(layout, flags, NumaNode::NO_NODE)?; // INVARIANT: `ptr` is either a dangling pointer or points to memory allocated with `A`, // which is sufficient in size and alignment for storing a `T`. diff --git a/rust/kernel/alloc/kvec.rs b/rust/kernel/alloc/kvec.rs index 3c72e0bdddb8..92d0ed3f302e 100644 --- a/rust/kernel/alloc/kvec.rs +++ b/rust/kernel/alloc/kvec.rs @@ -5,7 +5,7 @@ use super::{ allocator::{KVmalloc, Kmalloc, Vmalloc}, layout::ArrayLayout, - AllocError, Allocator, Box, Flags, + AllocError, Allocator, Box, Flags, NumaNode, }; use core::{ borrow::{Borrow, BorrowMut}, @@ -634,6 +634,7 @@ where layout.into(), self.layout.into(), flags, + NumaNode::NO_NODE, )? }; @@ -1111,7 +1112,13 @@ where // the type invariant to be smaller than `cap`. Depending on `realloc` this operation // may shrink the buffer or leave it as it is. ptr = match unsafe { - A::realloc(Some(buf.cast()), layout.into(), old_layout.into(), flags) + A::realloc( + Some(buf.cast()), + layout.into(), + old_layout.into(), + flags, + NumaNode::NO_NODE, + ) } { // If we fail to shrink, which likely can't even happen, continue with the existing // buffer. -- cgit v1.2.3 From 1738796994a439b0ea796847e3ceb8688dacd93d Mon Sep 17 00:00:00 2001 From: Vitaly Wool Date: Wed, 6 Aug 2025 14:55:52 +0200 Subject: rust: support large alignments in allocations Add support for large (> PAGE_SIZE) alignments in Rust allocators. All the preparations on the C side are already done, we just need to add bindings for _node_align() functions and start using those. Link: https://lkml.kernel.org/r/20250806125552.1727073-1-vitaly.wool@konsulko.se Signed-off-by: Vitaly Wool Acked-by: Danilo Krummrich Acked-by: Alice Ryhl Cc: Herbert Xu Cc: Jann Horn Cc: Kent Overstreet Cc: Liam Howlett Cc: Lorenzo Stoakes Cc: Uladzislau Rezki (Sony) Cc: Vlastimil Babka Signed-off-by: Andrew Morton --- rust/helpers/slab.c | 10 ++++++---- rust/helpers/vmalloc.c | 5 +++-- rust/kernel/alloc/allocator.rs | 30 +++++++++--------------------- 3 files changed, 18 insertions(+), 27 deletions(-) (limited to 'rust/kernel') diff --git a/rust/helpers/slab.c b/rust/helpers/slab.c index 8472370a4338..7fac958907b0 100644 --- a/rust/helpers/slab.c +++ b/rust/helpers/slab.c @@ -3,13 +3,15 @@ #include void * __must_check __realloc_size(2) -rust_helper_krealloc_node(const void *objp, size_t new_size, gfp_t flags, int node) +rust_helper_krealloc_node_align(const void *objp, size_t new_size, unsigned long align, + gfp_t flags, int node) { - return krealloc_node(objp, new_size, flags, node); + return krealloc_node_align(objp, new_size, align, flags, node); } void * __must_check __realloc_size(2) -rust_helper_kvrealloc_node(const void *p, size_t size, gfp_t flags, int node) +rust_helper_kvrealloc_node_align(const void *p, size_t size, unsigned long align, + gfp_t flags, int node) { - return kvrealloc_node(p, size, flags, node); + return kvrealloc_node_align(p, size, align, flags, node); } diff --git a/rust/helpers/vmalloc.c b/rust/helpers/vmalloc.c index 62d30db9a1a6..7d7f7336b3d2 100644 --- a/rust/helpers/vmalloc.c +++ b/rust/helpers/vmalloc.c @@ -3,7 +3,8 @@ #include void * __must_check __realloc_size(2) -rust_helper_vrealloc_node(const void *p, size_t size, gfp_t flags, int node) +rust_helper_vrealloc_node_align(const void *p, size_t size, unsigned long align, + gfp_t flags, int node) { - return vrealloc_node(p, size, flags, node); + return vrealloc_node_align(p, size, align, flags, node); } diff --git a/rust/kernel/alloc/allocator.rs b/rust/kernel/alloc/allocator.rs index 14510a9e4502..f4ae0cf0a594 100644 --- a/rust/kernel/alloc/allocator.rs +++ b/rust/kernel/alloc/allocator.rs @@ -15,7 +15,6 @@ use core::ptr::NonNull; use crate::alloc::{AllocError, Allocator, NumaNode}; use crate::bindings; -use crate::pr_warn; /// The contiguous kernel allocator. /// @@ -45,25 +44,26 @@ pub struct KVmalloc; /// # Invariants /// -/// One of the following: `krealloc_node`, `vrealloc_node`, `kvrealloc_node`. +/// One of the following: `krealloc_node_align`, `vrealloc_node_align`, `kvrealloc_node_align`. struct ReallocFunc( unsafe extern "C" fn( *const crate::ffi::c_void, usize, + crate::ffi::c_ulong, u32, crate::ffi::c_int, ) -> *mut crate::ffi::c_void, ); impl ReallocFunc { - // INVARIANT: `krealloc_node` satisfies the type invariants. - const KREALLOC: Self = Self(bindings::krealloc_node); + // INVARIANT: `krealloc_node_align` satisfies the type invariants. + const KREALLOC: Self = Self(bindings::krealloc_node_align); - // INVARIANT: `vrealloc_node` satisfies the type invariants. - const VREALLOC: Self = Self(bindings::vrealloc_node); + // INVARIANT: `vrealloc_node_align` satisfies the type invariants. + const VREALLOC: Self = Self(bindings::vrealloc_node_align); - // INVARIANT: `kvrealloc_node` satisfies the type invariants. - const KVREALLOC: Self = Self(bindings::kvrealloc_node); + // INVARIANT: `kvrealloc_node_align` satisfies the type invariants. + const KVREALLOC: Self = Self(bindings::kvrealloc_node_align); /// # Safety /// @@ -105,7 +105,7 @@ impl ReallocFunc { // - Those functions provide the guarantees of this function. let raw_ptr = unsafe { // If `size == 0` and `ptr != NULL` the memory behind the pointer is freed. - self.0(ptr.cast(), size, flags.0, nid.0).cast() + self.0(ptr.cast(), size, layout.align(), flags.0, nid.0).cast() }; let ptr = if size == 0 { @@ -162,12 +162,6 @@ unsafe impl Allocator for Vmalloc { flags: Flags, nid: NumaNode, ) -> 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, nid) } @@ -191,12 +185,6 @@ unsafe impl Allocator for KVmalloc { // compatible layout. let layout = Kmalloc::aligned_layout(layout); - // TODO: Support alignments larger than PAGE_SIZE. - if layout.align() > bindings::PAGE_SIZE { - pr_warn!("KVmalloc does not support alignments larger than PAGE_SIZE yet.\n"); - return Err(AllocError); - } - // SAFETY: If not `None`, `ptr` is guaranteed to point to valid memory, which was previously // allocated with this `Allocator`. unsafe { ReallocFunc::KVREALLOC.call(ptr, layout, old_layout, flags, nid) } -- cgit v1.2.3 From 868ade323e9deff67b8be3e93876596e4d2c71d3 Mon Sep 17 00:00:00 2001 From: Hui Zhu Date: Thu, 31 Jul 2025 10:50:05 +0800 Subject: rust: allocator: add KUnit tests for alignment guarantees MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Add a test module to verify memory alignment guarantees for Rust kernel allocators. The tests cover `Kmalloc`, `Vmalloc` and `KVmalloc` allocators with both standard and large page-aligned allocations. Key features of the tests: 1. Creates alignment-constrained types: - 128-byte aligned `Blob` - 8192-byte (4-page) aligned `LargeAlignBlob` 2. Validates allocators using `TestAlign` helper which: - Checks address alignment masks - Supports uninitialized allocations 3. Tests all three allocators with both alignment requirements: - Kmalloc with 128B and 8192B - Vmalloc with 128B and 8192B - KVmalloc with 128B and 8192B Link: https://lkml.kernel.org/r/d2e3d6454c1435713be0fe3c0dc444d2c60bba51.1753929369.git.zhuhui@kylinos.cn Co-developed-by: Geliang Tang Signed-off-by: Geliang Tang Signed-off-by: Hui Zhu Reviewed-by: Kunwu Chan Acked-by: Danilo Krummrich Cc: Alex Gaynor Cc: Alice Ryhl Cc: Andreas Hindborg Cc: Björn Roy Baron Cc: Boqun Feng Cc: Gary Guo Cc: Liam Howlett Cc: Lorenzo Stoakes Cc: Miguel Ojeda Cc: Trevor Gross Cc: "Uladzislau Rezki (Sony)" Cc: Vlastimil Babka Signed-off-by: Andrew Morton --- rust/kernel/alloc/allocator.rs | 56 ++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 56 insertions(+) (limited to 'rust/kernel') diff --git a/rust/kernel/alloc/allocator.rs b/rust/kernel/alloc/allocator.rs index f4ae0cf0a594..b561e7a57bb8 100644 --- a/rust/kernel/alloc/allocator.rs +++ b/rust/kernel/alloc/allocator.rs @@ -190,3 +190,59 @@ unsafe impl Allocator for KVmalloc { unsafe { ReallocFunc::KVREALLOC.call(ptr, layout, old_layout, flags, nid) } } } + +#[macros::kunit_tests(rust_allocator)] +mod tests { + use super::*; + use core::mem::MaybeUninit; + use kernel::prelude::*; + + #[test] + fn test_alignment() -> Result { + const TEST_SIZE: usize = 1024; + const TEST_LARGE_ALIGN_SIZE: usize = kernel::page::PAGE_SIZE * 4; + + // These two structs are used to test allocating aligned memory. + // they don't need to be accessed, so they're marked as dead_code. + #[expect(dead_code)] + #[repr(align(128))] + struct Blob([u8; TEST_SIZE]); + #[expect(dead_code)] + #[repr(align(8192))] + struct LargeAlignBlob([u8; TEST_LARGE_ALIGN_SIZE]); + + struct TestAlign(Box, A>); + impl TestAlign { + fn new() -> Result { + Ok(Self(Box::<_, A>::new_uninit(GFP_KERNEL)?)) + } + + fn is_aligned_to(&self, align: usize) -> bool { + assert!(align.is_power_of_two()); + + let addr = self.0.as_ptr() as usize; + addr & (align - 1) == 0 + } + } + + let ta = TestAlign::::new()?; + assert!(ta.is_aligned_to(128)); + + let ta = TestAlign::::new()?; + assert!(ta.is_aligned_to(8192)); + + let ta = TestAlign::::new()?; + assert!(ta.is_aligned_to(128)); + + let ta = TestAlign::::new()?; + assert!(ta.is_aligned_to(8192)); + + let ta = TestAlign::::new()?; + assert!(ta.is_aligned_to(128)); + + let ta = TestAlign::::new()?; + assert!(ta.is_aligned_to(8192)); + + Ok(()) + } +} -- cgit v1.2.3 From 9907e1df31c0f4bdcebe16de809121baa754e5b5 Mon Sep 17 00:00:00 2001 From: Shankari Anand Date: Wed, 16 Jul 2025 14:41:58 +0530 Subject: rust: mm: update ARef and AlwaysRefCounted imports from sync::aref MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Update call sites in the mm subsystem to import `ARef` and `AlwaysRefCounted` from `sync::aref` instead of `types`. This aligns with the ongoing effort to move `ARef` and `AlwaysRefCounted` to sync. Link: https://lkml.kernel.org/r/20250716091158.812860-1-shankari.ak0208@gmail.com Signed-off-by: Shankari Anand Suggested-by: Benno Lossin Link: https://github.com/Rust-for-Linux/linux/issues/1173 Acked-by: Alice Ryhl Cc: Alex Gaynor Cc: Andreas Hindborg Cc: Björn Roy Baron Cc: Boqun Feng Cc: Danilo Krummrich Cc: Gary Guo Cc: Liam Howlett Cc: Lorenzo Stoakes Cc: Miguel Ojeda Cc: Trevor Gross Signed-off-by: Andrew Morton --- rust/kernel/mm.rs | 3 ++- rust/kernel/mm/mmput_async.rs | 2 +- 2 files changed, 3 insertions(+), 2 deletions(-) (limited to 'rust/kernel') diff --git a/rust/kernel/mm.rs b/rust/kernel/mm.rs index 43f525c0d16c..4764d7b68f2a 100644 --- a/rust/kernel/mm.rs +++ b/rust/kernel/mm.rs @@ -13,7 +13,8 @@ use crate::{ bindings, - types::{ARef, AlwaysRefCounted, NotThreadSafe, Opaque}, + sync::aref::{ARef, AlwaysRefCounted}, + types::{NotThreadSafe, Opaque}, }; use core::{ops::Deref, ptr::NonNull}; diff --git a/rust/kernel/mm/mmput_async.rs b/rust/kernel/mm/mmput_async.rs index 9289e05f7a67..b8d2f051225c 100644 --- a/rust/kernel/mm/mmput_async.rs +++ b/rust/kernel/mm/mmput_async.rs @@ -10,7 +10,7 @@ use crate::{ bindings, mm::MmWithUser, - types::{ARef, AlwaysRefCounted}, + sync::aref::{ARef, AlwaysRefCounted}, }; use core::{ops::Deref, ptr::NonNull}; -- cgit v1.2.3 From da939ef4c494246bc2102ecb628bbcc71d650410 Mon Sep 17 00:00:00 2001 From: Alice Ryhl Date: Tue, 2 Sep 2025 08:35:11 +0000 Subject: rust: maple_tree: add MapleTree MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Patch series "Add Rust abstraction for Maple Trees", v3. This will be used in the Tyr driver [1] to allocate from the GPU's VA space that is not owned by userspace, but by the kernel, for kernel GPU mappings. Danilo tells me that in nouveau, the maple tree is used for keeping track of "VM regions" on top of GPUVM, and that he will most likely end up doing the same in the Rust Nova driver as well. These abstractions intentionally do not expose any way to make use of external locking. You are required to use the internal spinlock. For now, we do not support loads that only utilize rcu for protection. This contains some parts taken from Andrew Ballance's RFC [2] from April. However, it has also been reworked significantly compared to that RFC taking the use-cases in Tyr into account. This patch (of 3): The maple tree will be used in the Tyr driver to allocate and keep track of GPU allocations created internally (i.e. not by userspace). It will likely also be used in the Nova driver eventually. This adds the simplest methods for additional and removal that do not require any special care with respect to concurrency. This implementation is based on the RFC by Andrew but with significant changes to simplify the implementation. [ojeda@kernel.org: fix intra-doc links] Link: https://lkml.kernel.org/r/20250910140212.997771-1-ojeda@kernel.org Link: https://lkml.kernel.org/r/20250902-maple-tree-v3-0-fb5c8958fb1e@google.com Link: https://lkml.kernel.org/r/20250902-maple-tree-v3-1-fb5c8958fb1e@google.com Link: https://lore.kernel.org/r/20250627-tyr-v1-1-cb5f4c6ced46@collabora.com [1] Link: https://lore.kernel.org/r/20250405060154.1550858-1-andrewjballance@gmail.com [2] Co-developed-by: Andrew Ballance Signed-off-by: Andrew Ballance Signed-off-by: Alice Ryhl Reviewed-by: Danilo Krummrich Cc: Andreas Hindborg Cc: Björn Roy Baron Cc: Boqun Feng Cc: Daniel Almeida Cc: Gary Guo Cc: Liam Howlett Cc: Lorenzo Stoakes Cc: Miguel Ojeda Cc: Trevor Gross Signed-off-by: Andrew Morton --- MAINTAINERS | 4 + include/linux/maple_tree.h | 3 + rust/helpers/helpers.c | 1 + rust/helpers/maple_tree.c | 8 ++ rust/kernel/lib.rs | 1 + rust/kernel/maple_tree.rs | 349 +++++++++++++++++++++++++++++++++++++++++++++ 6 files changed, 366 insertions(+) create mode 100644 rust/helpers/maple_tree.c create mode 100644 rust/kernel/maple_tree.rs (limited to 'rust/kernel') diff --git a/MAINTAINERS b/MAINTAINERS index a7e123ddf05a..68d29f0220fc 100644 --- a/MAINTAINERS +++ b/MAINTAINERS @@ -14672,6 +14672,8 @@ F: net/mctp/ MAPLE TREE M: Liam R. Howlett +R: Alice Ryhl +R: Andrew Ballance L: maple-tree@lists.infradead.org L: linux-mm@kvack.org S: Supported @@ -14680,6 +14682,8 @@ F: include/linux/maple_tree.h F: include/trace/events/maple_tree.h F: lib/maple_tree.c F: lib/test_maple_tree.c +F: rust/helpers/maple_tree.c +F: rust/kernel/maple_tree.rs F: tools/testing/radix-tree/maple.c F: tools/testing/shared/linux/maple_tree.h diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index 41e633264e51..05730171d201 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -481,6 +481,9 @@ struct ma_wr_state { #define MA_ERROR(err) \ ((struct maple_enode *)(((unsigned long)err << 2) | 2UL)) +/* + * When changing MA_STATE, remember to also change rust/kernel/maple_tree.rs + */ #define MA_STATE(name, mt, first, end) \ struct ma_state name = { \ .tree = mt, \ diff --git a/rust/helpers/helpers.c b/rust/helpers/helpers.c index 7cf7fe95e41d..c5d42e0f7ce6 100644 --- a/rust/helpers/helpers.c +++ b/rust/helpers/helpers.c @@ -26,6 +26,7 @@ #include "io.c" #include "jump_label.c" #include "kunit.c" +#include "maple_tree.c" #include "mm.c" #include "mutex.c" #include "of.c" diff --git a/rust/helpers/maple_tree.c b/rust/helpers/maple_tree.c new file mode 100644 index 000000000000..1dd9ac84a13f --- /dev/null +++ b/rust/helpers/maple_tree.c @@ -0,0 +1,8 @@ +// SPDX-License-Identifier: GPL-2.0 + +#include + +void rust_helper_mt_init_flags(struct maple_tree *mt, unsigned int flags) +{ + mt_init_flags(mt, flags); +} diff --git a/rust/kernel/lib.rs b/rust/kernel/lib.rs index ed53169e795c..6b0a5689669f 100644 --- a/rust/kernel/lib.rs +++ b/rust/kernel/lib.rs @@ -96,6 +96,7 @@ pub mod jump_label; #[cfg(CONFIG_KUNIT)] pub mod kunit; pub mod list; +pub mod maple_tree; pub mod miscdevice; pub mod mm; #[cfg(CONFIG_NET)] diff --git a/rust/kernel/maple_tree.rs b/rust/kernel/maple_tree.rs new file mode 100644 index 000000000000..319772878b89 --- /dev/null +++ b/rust/kernel/maple_tree.rs @@ -0,0 +1,349 @@ +// SPDX-License-Identifier: GPL-2.0 + +//! Maple trees. +//! +//! C header: [`include/linux/maple_tree.h`](srctree/include/linux/maple_tree.h) +//! +//! Reference: + +use core::{ + marker::PhantomData, + ops::{Bound, RangeBounds}, + ptr, +}; + +use kernel::{ + alloc::Flags, + error::to_result, + prelude::*, + types::{ForeignOwnable, Opaque}, +}; + +/// A maple tree optimized for storing non-overlapping ranges. +/// +/// # Invariants +/// +/// Each range in the maple tree owns an instance of `T`. +#[pin_data(PinnedDrop)] +#[repr(transparent)] +pub struct MapleTree { + #[pin] + tree: Opaque, + _p: PhantomData, +} + +#[inline] +fn to_maple_range(range: impl RangeBounds) -> Option<(usize, usize)> { + let first = match range.start_bound() { + Bound::Included(start) => *start, + Bound::Excluded(start) => start.checked_add(1)?, + Bound::Unbounded => 0, + }; + + let last = match range.end_bound() { + Bound::Included(end) => *end, + Bound::Excluded(end) => end.checked_sub(1)?, + Bound::Unbounded => usize::MAX, + }; + + if last < first { + return None; + } + + Some((first, last)) +} + +impl MapleTree { + /// Create a new maple tree. + /// + /// The tree will use the regular implementation with a higher branching factor, rather than + /// the allocation tree. + #[inline] + pub fn new() -> impl PinInit { + pin_init!(MapleTree { + // SAFETY: This initializes a maple tree into a pinned slot. The maple tree will be + // destroyed in Drop before the memory location becomes invalid. + tree <- Opaque::ffi_init(|slot| unsafe { bindings::mt_init_flags(slot, 0) }), + _p: PhantomData, + }) + } + + /// Insert the value at the given index. + /// + /// # Errors + /// + /// If the maple tree already contains a range using the given index, then this call will + /// return an [`InsertErrorKind::Occupied`]. It may also fail if memory allocation fails. + /// + /// # Examples + /// + /// ``` + /// use kernel::maple_tree::{InsertErrorKind, MapleTree}; + /// + /// let tree = KBox::pin_init(MapleTree::>::new(), GFP_KERNEL)?; + /// + /// let ten = KBox::new(10, GFP_KERNEL)?; + /// let twenty = KBox::new(20, GFP_KERNEL)?; + /// let the_answer = KBox::new(42, GFP_KERNEL)?; + /// + /// // These calls will succeed. + /// tree.insert(100, ten, GFP_KERNEL)?; + /// tree.insert(101, twenty, GFP_KERNEL)?; + /// + /// // This will fail because the index is already in use. + /// assert_eq!( + /// tree.insert(100, the_answer, GFP_KERNEL).unwrap_err().cause, + /// InsertErrorKind::Occupied, + /// ); + /// # Ok::<_, Error>(()) + /// ``` + #[inline] + pub fn insert(&self, index: usize, value: T, gfp: Flags) -> Result<(), InsertError> { + self.insert_range(index..=index, value, gfp) + } + + /// Insert a value to the specified range, failing on overlap. + /// + /// This accepts the usual types of Rust ranges using the `..` and `..=` syntax for exclusive + /// and inclusive ranges respectively. The range must not be empty, and must not overlap with + /// any existing range. + /// + /// # Errors + /// + /// If the maple tree already contains an overlapping range, then this call will return an + /// [`InsertErrorKind::Occupied`]. It may also fail if memory allocation fails or if the + /// requested range is invalid (e.g. empty). + /// + /// # Examples + /// + /// ``` + /// use kernel::maple_tree::{InsertErrorKind, MapleTree}; + /// + /// let tree = KBox::pin_init(MapleTree::>::new(), GFP_KERNEL)?; + /// + /// let ten = KBox::new(10, GFP_KERNEL)?; + /// let twenty = KBox::new(20, GFP_KERNEL)?; + /// let the_answer = KBox::new(42, GFP_KERNEL)?; + /// let hundred = KBox::new(100, GFP_KERNEL)?; + /// + /// // Insert the value 10 at the indices 100 to 499. + /// tree.insert_range(100..500, ten, GFP_KERNEL)?; + /// + /// // Insert the value 20 at the indices 500 to 1000. + /// tree.insert_range(500..=1000, twenty, GFP_KERNEL)?; + /// + /// // This will fail due to overlap with the previous range on index 1000. + /// assert_eq!( + /// tree.insert_range(1000..1200, the_answer, GFP_KERNEL).unwrap_err().cause, + /// InsertErrorKind::Occupied, + /// ); + /// + /// // When using .. to specify the range, you must be careful to ensure that the range is + /// // non-empty. + /// assert_eq!( + /// tree.insert_range(72..72, hundred, GFP_KERNEL).unwrap_err().cause, + /// InsertErrorKind::InvalidRequest, + /// ); + /// # Ok::<_, Error>(()) + /// ``` + pub fn insert_range(&self, range: R, value: T, gfp: Flags) -> Result<(), InsertError> + where + R: RangeBounds, + { + let Some((first, last)) = to_maple_range(range) else { + return Err(InsertError { + value, + cause: InsertErrorKind::InvalidRequest, + }); + }; + + let ptr = T::into_foreign(value); + + // SAFETY: The tree is valid, and we are passing a pointer to an owned instance of `T`. + let res = to_result(unsafe { + bindings::mtree_insert_range(self.tree.get(), first, last, ptr, gfp.as_raw()) + }); + + if let Err(err) = res { + // SAFETY: As `mtree_insert_range` failed, it is safe to take back ownership. + let value = unsafe { T::from_foreign(ptr) }; + + let cause = if err == ENOMEM { + InsertErrorKind::AllocError(kernel::alloc::AllocError) + } else if err == EEXIST { + InsertErrorKind::Occupied + } else { + InsertErrorKind::InvalidRequest + }; + Err(InsertError { value, cause }) + } else { + Ok(()) + } + } + + /// Erase the range containing the given index. + /// + /// # Examples + /// + /// ``` + /// use kernel::maple_tree::MapleTree; + /// + /// let tree = KBox::pin_init(MapleTree::>::new(), GFP_KERNEL)?; + /// + /// let ten = KBox::new(10, GFP_KERNEL)?; + /// let twenty = KBox::new(20, GFP_KERNEL)?; + /// + /// tree.insert_range(100..500, ten, GFP_KERNEL)?; + /// tree.insert(67, twenty, GFP_KERNEL)?; + /// + /// assert_eq!(tree.erase(67).map(|v| *v), Some(20)); + /// assert_eq!(tree.erase(275).map(|v| *v), Some(10)); + /// + /// // The previous call erased the entire range, not just index 275. + /// assert!(tree.erase(127).is_none()); + /// # Ok::<_, Error>(()) + /// ``` + #[inline] + pub fn erase(&self, index: usize) -> Option { + // SAFETY: `self.tree` contains a valid maple tree. + let ret = unsafe { bindings::mtree_erase(self.tree.get(), index) }; + + // SAFETY: If the pointer is not null, then we took ownership of a valid instance of `T` + // from the tree. + unsafe { T::try_from_foreign(ret) } + } + + /// Free all `T` instances in this tree. + /// + /// # Safety + /// + /// This frees Rust data referenced by the maple tree without removing it from the maple tree, + /// leaving it in an invalid state. The caller must ensure that this invalid state cannot be + /// observed by the end-user. + unsafe fn free_all_entries(self: Pin<&mut Self>) { + // SAFETY: The caller provides exclusive access to the entire maple tree, so we have + // exclusive access to the entire maple tree despite not holding the lock. + let mut ma_state = unsafe { MaState::new_raw(self.into_ref().get_ref(), 0, usize::MAX) }; + + loop { + // This uses the raw accessor because we're destroying pointers without removing them + // from the maple tree, which is only valid because this is the destructor. + let ptr = ma_state.mas_find_raw(usize::MAX); + if ptr.is_null() { + break; + } + // SAFETY: By the type invariants, this pointer references a valid value of type `T`. + // By the safety requirements, it is okay to free it without removing it from the maple + // tree. + drop(unsafe { T::from_foreign(ptr) }); + } + } +} + +#[pinned_drop] +impl PinnedDrop for MapleTree { + #[inline] + fn drop(mut self: Pin<&mut Self>) { + // We only iterate the tree if the Rust value has a destructor. + if core::mem::needs_drop::() { + // SAFETY: Other than the below `mtree_destroy` call, the tree will not be accessed + // after this call. + unsafe { self.as_mut().free_all_entries() }; + } + + // SAFETY: The tree is valid, and will not be accessed after this call. + unsafe { bindings::mtree_destroy(self.tree.get()) }; + } +} + +/// A helper type used for navigating a [`MapleTree`]. +/// +/// # Invariants +/// +/// For the duration of `'tree`: +/// +/// * The `ma_state` references a valid `MapleTree`. +/// * The `ma_state` has read/write access to the tree. +pub struct MaState<'tree, T: ForeignOwnable> { + state: bindings::ma_state, + _phantom: PhantomData<&'tree mut MapleTree>, +} + +impl<'tree, T: ForeignOwnable> MaState<'tree, T> { + /// Initialize a new `MaState` with the given tree. + /// + /// # Safety + /// + /// The caller must ensure that this `MaState` has read/write access to the maple tree. + #[inline] + unsafe fn new_raw(mt: &'tree MapleTree, first: usize, end: usize) -> Self { + // INVARIANT: + // * Having a reference ensures that the `MapleTree` is valid for `'tree`. + // * The caller ensures that we have read/write access. + Self { + state: bindings::ma_state { + tree: mt.tree.get(), + index: first, + last: end, + node: ptr::null_mut(), + status: bindings::maple_status_ma_start, + min: 0, + max: usize::MAX, + alloc: ptr::null_mut(), + mas_flags: 0, + store_type: bindings::store_type_wr_invalid, + ..Default::default() + }, + _phantom: PhantomData, + } + } + + #[inline] + fn as_raw(&mut self) -> *mut bindings::ma_state { + &raw mut self.state + } + + #[inline] + fn mas_find_raw(&mut self, max: usize) -> *mut c_void { + // SAFETY: By the type invariants, the `ma_state` is active and we have read/write access + // to the tree. + unsafe { bindings::mas_find(self.as_raw(), max) } + } +} + +/// Error type for failure to insert a new value. +pub struct InsertError { + /// The value that could not be inserted. + pub value: T, + /// The reason for the failure to insert. + pub cause: InsertErrorKind, +} + +/// The reason for the failure to insert. +#[derive(PartialEq, Eq, Copy, Clone, Debug)] +pub enum InsertErrorKind { + /// There is already a value in the requested range. + Occupied, + /// Failure to allocate memory. + AllocError(kernel::alloc::AllocError), + /// The insertion request was invalid. + InvalidRequest, +} + +impl From for Error { + #[inline] + fn from(kind: InsertErrorKind) -> Error { + match kind { + InsertErrorKind::Occupied => EEXIST, + InsertErrorKind::AllocError(kernel::alloc::AllocError) => ENOMEM, + InsertErrorKind::InvalidRequest => EINVAL, + } + } +} + +impl From> for Error { + #[inline] + fn from(insert_err: InsertError) -> Error { + Error::from(insert_err.cause) + } +} -- cgit v1.2.3 From 01422da19cbeb4b044649322968265464991368e Mon Sep 17 00:00:00 2001 From: Alice Ryhl Date: Tue, 2 Sep 2025 08:35:12 +0000 Subject: rust: maple_tree: add lock guard for maple tree MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit To load a value, one must be careful to hold the lock while accessing it. To enable this, we add a lock() method so that you can perform operations on the value before the spinlock is released. This adds a MapleGuard type without using the existing SpinLock type. This ensures that the MapleGuard type is not unnecessarily large, and that it is easy to swap out the type of lock in case the C maple tree is changed to use a different kind of lock. There are two ways of using the lock guard: You can call load() directly to load a value under the lock, or you can create an MaState to iterate the tree with find(). The find() method does not have the mas_ prefix since it's a method on MaState, and being a method on that struct serves a similar purpose to the mas_ prefix in C. Link: https://lkml.kernel.org/r/20250902-maple-tree-v3-2-fb5c8958fb1e@google.com Co-developed-by: Andrew Ballance Signed-off-by: Andrew Ballance Reviewed-by: Andrew Ballance Reviewed-by: Danilo Krummrich Signed-off-by: Alice Ryhl Cc: Andreas Hindborg Cc: Björn Roy Baron Cc: Boqun Feng Cc: Daniel Almeida Cc: Gary Guo Cc: Liam Howlett Cc: Lorenzo Stoakes Cc: Miguel Ojeda Cc: Trevor Gross Signed-off-by: Andrew Morton --- rust/kernel/maple_tree.rs | 140 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 140 insertions(+) (limited to 'rust/kernel') diff --git a/rust/kernel/maple_tree.rs b/rust/kernel/maple_tree.rs index 319772878b89..7acb8478d1d9 100644 --- a/rust/kernel/maple_tree.rs +++ b/rust/kernel/maple_tree.rs @@ -213,6 +213,23 @@ impl MapleTree { unsafe { T::try_from_foreign(ret) } } + /// Lock the internal spinlock. + #[inline] + pub fn lock(&self) -> MapleGuard<'_, T> { + // SAFETY: It's safe to lock the spinlock in a maple tree. + unsafe { bindings::spin_lock(self.ma_lock()) }; + + // INVARIANT: We just took the spinlock. + MapleGuard(self) + } + + #[inline] + fn ma_lock(&self) -> *mut bindings::spinlock_t { + // SAFETY: This pointer offset operation stays in-bounds. + let lock_ptr = unsafe { &raw mut (*self.tree.get()).__bindgen_anon_1.ma_lock }; + lock_ptr.cast() + } + /// Free all `T` instances in this tree. /// /// # Safety @@ -256,6 +273,91 @@ impl PinnedDrop for MapleTree { } } +/// A reference to a [`MapleTree`] that owns the inner lock. +/// +/// # Invariants +/// +/// This guard owns the inner spinlock. +#[must_use = "if unused, the lock will be immediately unlocked"] +pub struct MapleGuard<'tree, T: ForeignOwnable>(&'tree MapleTree); + +impl<'tree, T: ForeignOwnable> Drop for MapleGuard<'tree, T> { + #[inline] + fn drop(&mut self) { + // SAFETY: By the type invariants, we hold this spinlock. + unsafe { bindings::spin_unlock(self.0.ma_lock()) }; + } +} + +impl<'tree, T: ForeignOwnable> MapleGuard<'tree, T> { + /// Create a [`MaState`] protected by this lock guard. + pub fn ma_state(&mut self, first: usize, end: usize) -> MaState<'_, T> { + // SAFETY: The `MaState` borrows this `MapleGuard`, so it can also borrow the `MapleGuard`s + // read/write permissions to the maple tree. + unsafe { MaState::new_raw(self.0, first, end) } + } + + /// Load the value at the given index. + /// + /// # Examples + /// + /// Read the value while holding the spinlock. + /// + /// ``` + /// use kernel::maple_tree::MapleTree; + /// + /// let tree = KBox::pin_init(MapleTree::>::new(), GFP_KERNEL)?; + /// + /// let ten = KBox::new(10, GFP_KERNEL)?; + /// let twenty = KBox::new(20, GFP_KERNEL)?; + /// tree.insert(100, ten, GFP_KERNEL)?; + /// tree.insert(200, twenty, GFP_KERNEL)?; + /// + /// let mut lock = tree.lock(); + /// assert_eq!(lock.load(100).map(|v| *v), Some(10)); + /// assert_eq!(lock.load(200).map(|v| *v), Some(20)); + /// assert_eq!(lock.load(300).map(|v| *v), None); + /// # Ok::<_, Error>(()) + /// ``` + /// + /// Increment refcount under the lock, to keep value alive afterwards. + /// + /// ``` + /// use kernel::maple_tree::MapleTree; + /// use kernel::sync::Arc; + /// + /// let tree = KBox::pin_init(MapleTree::>::new(), GFP_KERNEL)?; + /// + /// let ten = Arc::new(10, GFP_KERNEL)?; + /// let twenty = Arc::new(20, GFP_KERNEL)?; + /// tree.insert(100, ten, GFP_KERNEL)?; + /// tree.insert(200, twenty, GFP_KERNEL)?; + /// + /// // Briefly take the lock to increment the refcount. + /// let value = tree.lock().load(100).map(Arc::from); + /// + /// // At this point, another thread might remove the value. + /// tree.erase(100); + /// + /// // But we can still access it because we took a refcount. + /// assert_eq!(value.map(|v| *v), Some(10)); + /// # Ok::<_, Error>(()) + /// ``` + #[inline] + pub fn load(&mut self, index: usize) -> Option> { + // SAFETY: `self.tree` contains a valid maple tree. + let ret = unsafe { bindings::mtree_load(self.0.tree.get(), index) }; + if ret.is_null() { + return None; + } + + // SAFETY: If the pointer is not null, then it references a valid instance of `T`. It is + // safe to borrow the instance mutably because the signature of this function enforces that + // the mutable borrow is not used after the spinlock is dropped. + Some(unsafe { T::borrow_mut(ret) }) + } +} + /// A helper type used for navigating a [`MapleTree`]. /// /// # Invariants @@ -309,6 +411,44 @@ impl<'tree, T: ForeignOwnable> MaState<'tree, T> { // to the tree. unsafe { bindings::mas_find(self.as_raw(), max) } } + + /// Find the next entry in the maple tree. + /// + /// # Examples + /// + /// Iterate the maple tree. + /// + /// ``` + /// use kernel::maple_tree::MapleTree; + /// use kernel::sync::Arc; + /// + /// let tree = KBox::pin_init(MapleTree::>::new(), GFP_KERNEL)?; + /// + /// let ten = Arc::new(10, GFP_KERNEL)?; + /// let twenty = Arc::new(20, GFP_KERNEL)?; + /// tree.insert(100, ten, GFP_KERNEL)?; + /// tree.insert(200, twenty, GFP_KERNEL)?; + /// + /// let mut ma_lock = tree.lock(); + /// let mut iter = ma_lock.ma_state(0, usize::MAX); + /// + /// assert_eq!(iter.find(usize::MAX).map(|v| *v), Some(10)); + /// assert_eq!(iter.find(usize::MAX).map(|v| *v), Some(20)); + /// assert!(iter.find(usize::MAX).is_none()); + /// # Ok::<_, Error>(()) + /// ``` + #[inline] + pub fn find(&mut self, max: usize) -> Option> { + let ret = self.mas_find_raw(max); + if ret.is_null() { + return None; + } + + // SAFETY: If the pointer is not null, then it references a valid instance of `T`. It's + // safe to access it mutably as the returned reference borrows this `MaState`, and the + // `MaState` has read/write access to the maple tree. + Some(unsafe { T::borrow_mut(ret) }) + } } /// Error type for failure to insert a new value. -- cgit v1.2.3 From 56b1852e82bd5550c8987bb381a3d930f27b4058 Mon Sep 17 00:00:00 2001 From: Alice Ryhl Date: Tue, 2 Sep 2025 08:35:13 +0000 Subject: rust: maple_tree: add MapleTreeAlloc MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit To support allocation trees, we introduce a new type MapleTreeAlloc for the case where the tree is created using MT_FLAGS_ALLOC_RANGE. To ensure that you can only call mtree_alloc_range on an allocation tree, we restrict thta method to the new MapleTreeAlloc type. However, all methods on MapleTree remain accessible to MapleTreeAlloc as allocation trees can use the other methods without issues. Link: https://lkml.kernel.org/r/20250902-maple-tree-v3-3-fb5c8958fb1e@google.com Signed-off-by: Alice Ryhl Reviewed-by: Daniel Almeida Reviewed-by: Danilo Krummrich Cc: Andreas Hindborg Cc: Andrew Ballance Cc: Björn Roy Baron Cc: Boqun Feng Cc: Gary Guo Cc: Liam Howlett Cc: Lorenzo Stoakes Cc: Miguel Ojeda Cc: Trevor Gross Signed-off-by: Andrew Morton --- rust/kernel/maple_tree.rs | 158 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 158 insertions(+) (limited to 'rust/kernel') diff --git a/rust/kernel/maple_tree.rs b/rust/kernel/maple_tree.rs index 7acb8478d1d9..e72eec56bf57 100644 --- a/rust/kernel/maple_tree.rs +++ b/rust/kernel/maple_tree.rs @@ -32,6 +32,26 @@ pub struct MapleTree { _p: PhantomData, } +/// A maple tree with `MT_FLAGS_ALLOC_RANGE` set. +/// +/// All methods on [`MapleTree`] are also accessible on this type. +#[pin_data] +#[repr(transparent)] +pub struct MapleTreeAlloc { + #[pin] + tree: MapleTree, +} + +// Make MapleTree methods usable on MapleTreeAlloc. +impl core::ops::Deref for MapleTreeAlloc { + type Target = MapleTree; + + #[inline] + fn deref(&self) -> &MapleTree { + &self.tree + } +} + #[inline] fn to_maple_range(range: impl RangeBounds) -> Option<(usize, usize)> { let first = match range.start_bound() { @@ -358,6 +378,107 @@ impl<'tree, T: ForeignOwnable> MapleGuard<'tree, T> { } } +impl MapleTreeAlloc { + /// Create a new allocation tree. + pub fn new() -> impl PinInit { + let tree = pin_init!(MapleTree { + // SAFETY: This initializes a maple tree into a pinned slot. The maple tree will be + // destroyed in Drop before the memory location becomes invalid. + tree <- Opaque::ffi_init(|slot| unsafe { + bindings::mt_init_flags(slot, bindings::MT_FLAGS_ALLOC_RANGE) + }), + _p: PhantomData, + }); + + pin_init!(MapleTreeAlloc { tree <- tree }) + } + + /// Insert an entry with the given size somewhere in the given range. + /// + /// The maple tree will search for a location in the given range where there is space to insert + /// the new range. If there is not enough available space, then an error will be returned. + /// + /// The index of the new range is returned. + /// + /// # Examples + /// + /// ``` + /// use kernel::maple_tree::{MapleTreeAlloc, AllocErrorKind}; + /// + /// let tree = KBox::pin_init(MapleTreeAlloc::>::new(), GFP_KERNEL)?; + /// + /// let ten = KBox::new(10, GFP_KERNEL)?; + /// let twenty = KBox::new(20, GFP_KERNEL)?; + /// let thirty = KBox::new(30, GFP_KERNEL)?; + /// let hundred = KBox::new(100, GFP_KERNEL)?; + /// + /// // Allocate three ranges. + /// let idx1 = tree.alloc_range(100, ten, ..1000, GFP_KERNEL)?; + /// let idx2 = tree.alloc_range(100, twenty, ..1000, GFP_KERNEL)?; + /// let idx3 = tree.alloc_range(100, thirty, ..1000, GFP_KERNEL)?; + /// + /// assert_eq!(idx1, 0); + /// assert_eq!(idx2, 100); + /// assert_eq!(idx3, 200); + /// + /// // This will fail because the remaining space is too small. + /// assert_eq!( + /// tree.alloc_range(800, hundred, ..1000, GFP_KERNEL).unwrap_err().cause, + /// AllocErrorKind::Busy, + /// ); + /// # Ok::<_, Error>(()) + /// ``` + pub fn alloc_range( + &self, + size: usize, + value: T, + range: R, + gfp: Flags, + ) -> Result> + where + R: RangeBounds, + { + let Some((min, max)) = to_maple_range(range) else { + return Err(AllocError { + value, + cause: AllocErrorKind::InvalidRequest, + }); + }; + + let ptr = T::into_foreign(value); + let mut index = 0; + + // SAFETY: The tree is valid, and we are passing a pointer to an owned instance of `T`. + let res = to_result(unsafe { + bindings::mtree_alloc_range( + self.tree.tree.get(), + &mut index, + ptr, + size, + min, + max, + gfp.as_raw(), + ) + }); + + if let Err(err) = res { + // SAFETY: As `mtree_alloc_range` failed, it is safe to take back ownership. + let value = unsafe { T::from_foreign(ptr) }; + + let cause = if err == ENOMEM { + AllocErrorKind::AllocError(kernel::alloc::AllocError) + } else if err == EBUSY { + AllocErrorKind::Busy + } else { + AllocErrorKind::InvalidRequest + }; + Err(AllocError { value, cause }) + } else { + Ok(index) + } + } +} + /// A helper type used for navigating a [`MapleTree`]. /// /// # Invariants @@ -487,3 +608,40 @@ impl From> for Error { Error::from(insert_err.cause) } } + +/// Error type for failure to insert a new value. +pub struct AllocError { + /// The value that could not be inserted. + pub value: T, + /// The reason for the failure to insert. + pub cause: AllocErrorKind, +} + +/// The reason for the failure to insert. +#[derive(PartialEq, Eq, Copy, Clone)] +pub enum AllocErrorKind { + /// There is not enough space for the requested allocation. + Busy, + /// Failure to allocate memory. + AllocError(kernel::alloc::AllocError), + /// The insertion request was invalid. + InvalidRequest, +} + +impl From for Error { + #[inline] + fn from(kind: AllocErrorKind) -> Error { + match kind { + AllocErrorKind::Busy => EBUSY, + AllocErrorKind::AllocError(kernel::alloc::AllocError) => ENOMEM, + AllocErrorKind::InvalidRequest => EINVAL, + } + } +} + +impl From> for Error { + #[inline] + fn from(insert_err: AllocError) -> Error { + Error::from(insert_err.cause) + } +} -- cgit v1.2.3