From nobody Fri Oct 3 11:25:00 2025 Received: from mail-wm1-f73.google.com (mail-wm1-f73.google.com [209.85.128.73]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 4D16D2E8B97 for ; Tue, 2 Sep 2025 08:35:26 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.73 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1756802128; cv=none; b=VgcMaq5NPDHiA2sVGKb/gA0+51p/F3wQAHGtjIQbpI5z/2YsnGtuO3zij4DE1q8uPLfq8+pbTNNIAlpMC5D6DbwQjCBnefnPGUv9nwj0npg56sYZfQxg9i1es4YPzsbGvtNdg0zrpecjj8U3O2PSJs9fve6LrOMBjHFUx98mDHs= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1756802128; c=relaxed/simple; bh=wjtWPgW/UysnPZ4giaD8bZKnCDWu3P89mJEt/I/Q07Y=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=qBPO1/guQ2vHj0wRRgbt03OMGJhFwCOuaNqNz2f3BUDzICs7WcInqRbKDNcAL5jaEFaCYSjj7mNY/L5OqKJWaqRYKpAfxrK4zqEzIpTyrJV94tjHkqG0nw7YL93BcIPOlRODMzRiW4NfcwYQIYkXGL/Fnbz7idXiDNjPtQT1fhI= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com; spf=pass smtp.mailfrom=flex--aliceryhl.bounces.google.com; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b=EnrQtA0s; arc=none smtp.client-ip=209.85.128.73 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=flex--aliceryhl.bounces.google.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="EnrQtA0s" Received: by mail-wm1-f73.google.com with SMTP id 5b1f17b1804b1-45b99c18484so1600255e9.1 for ; Tue, 02 Sep 2025 01:35:25 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1756802124; x=1757406924; darn=vger.kernel.org; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=p6IknaUGSNpWDYBqLgrpS5f057vYmeQH2aMiOoUU0cY=; b=EnrQtA0s7pySBoayVlUqKyqT/vBiMZjZBiWJvqpyeQ+GS0Y1agsuth8VNaZsLKo3dd H5vPiWGd/re6z0Xg4JNSoq09eDvik2A44LstCNgDdS1L9IC0K/BGlLygCloaumgIQFo1 dGrS4dZsNJaJP363KPRQWXX5i+IRZLyYq+KmQMCIKH1MYs1jgAIiVCxwvzFYykk+dqic jFmTiYK5cwj1pnanaPnIPxtNESo9zHbu9S2AW0Ts03ifjL2Ra6t5U2j63f0GUK6JHhs/ EM6yj6/mqSfbz57PUcg5GOkfBMsEzELxtx9iwNlAHrJqbAaDMp9H4psOmVCUOi8WlBox 6gkA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1756802124; x=1757406924; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=p6IknaUGSNpWDYBqLgrpS5f057vYmeQH2aMiOoUU0cY=; b=HUdubFyr2bse9JapG2hQUYHPZIA2ELjv3HYDEis47C2ZcGeUxhPhWNHAXmgNFSCS3m uvY0vsg4hfzdY7/siAewhwYyDTyv6xOkuFmGzc1Us/yOZDd9XfRett672l2VcjGjh4js vPpYqpxW+L32ridu4GfC+4nw1hu4IuV6eJd5/MTTRQsoHMirAmNXfH290ne5ZfEW4rJ0 /h2dYziBVhNw0zi+tqop5R6SIX8xzz5iE+1sOsjqMqG6GtwrWrl6Ub9Mql5imLNlSbYh DC41VTdBeW+hQbfiW7vxuS4sqAe55rQuPHiyxFbz9DPeJ1vQ0Ipa+JWBxeACJClyY1g4 kcTA== X-Forwarded-Encrypted: i=1; AJvYcCUkrNVRQJ1p+46zjuVRIMIB/JnoCVeiUJTQFljOCUbvPM73kdk77a6nZyRYCEKruihQSqWbvrQYMjQ3uxg=@vger.kernel.org X-Gm-Message-State: AOJu0YwbiRL9I7cX0zfkLzWpEij5bMuRyNRsbtTR2Jab5abwgm1ER2oe SWKjdwWHXyAFf2KBV8IPkAwePQTFff8wFH+HV3kxwbaUWiNXLVDjPEJd89eB6UZ4Q9/AQVdIj+v xrRiR2noFfe/Zo32fDg== X-Google-Smtp-Source: AGHT+IGYbHyJ9GAqNLshEvU+n8ntrU34uDmin8xaf3GjY/SbM9BkTgPMVRDnOWGVZmjOnqa+VFEFoo0JEzit4dc= X-Received: from wmth8.prod.google.com ([2002:a05:600c:8b68:b0:45a:2855:e836]) (user=aliceryhl job=prod-delivery.src-stubby-dispatcher) by 2002:a05:600c:6383:b0:45b:880a:8fd3 with SMTP id 5b1f17b1804b1-45b880a91a7mr74193275e9.7.1756802124681; Tue, 02 Sep 2025 01:35:24 -0700 (PDT) Date: Tue, 02 Sep 2025 08:35:11 +0000 In-Reply-To: <20250902-maple-tree-v3-0-fb5c8958fb1e@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20250902-maple-tree-v3-0-fb5c8958fb1e@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=16139; i=aliceryhl@google.com; h=from:subject:message-id; bh=wjtWPgW/UysnPZ4giaD8bZKnCDWu3P89mJEt/I/Q07Y=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBotqxKN0FxiILltf6yXjPY90o9PJQMY3QVkcD70 Dgf5mpb0eiJAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCaLasSgAKCRAEWL7uWMY5 Rs61D/wJjsHil7kWhGoA2OFOzsK0cP6byAnxg1h3XJnDsMTqNsayDvw4177EVpydO7JqqLkC4Jv mDsAXXc8XPVFqdXpFINGu0cAFbcxC7RfTe+BsAva680Qcv91Mv6Nd4gsVPaYf+UKMTgm2Hw8G1/ kM292bfeB0axxxkJOP8b1TsEG4GRvu6hcMWI5socituE/COTp/NzVpDUso7sdzdESTDzHh1DskK TrzfM/IdOHFZQuPxnxeZehyO9n8zkygLTnTjtA8mOXh53jZujwm43YrZvbvhgcQuAfJhJURH+// TpjzCM3Pc8EUG474jgT5z2iXbuTdJiAYQbmmcK9JgewxKE8gCiwoOuIgFIOYsGMgZjyZQq4dbHB xE0762W1atTPYvQBnWag8QKdWansaqhWeRs31SlA+hnmOpJ3qE+ZDF75BqZ4tLy1Kz34sqFX66q so8t6RXwe1dFKpcgQPDsa+jtY1UAqo4a33GCgzf4VPYUl+o4M+tO+OeJkM+Dla+zvK2uuXOh687 o8e+u6esZ0uYzKPdHtjb67pB/2Y7G8b4XfweYHETp3lnVQTmtPsZ84R4k7wyoACqTAc/WJFcCYR 3xfOrSQYOVB1aGUs3w6nztiPrgRCXx+yhMFSej14plJHNEfz3BbVfWamWAyAu2XDdW0KEeTxeN+ 9QgArwKMcOd6YhA== X-Mailer: b4 0.14.2 Message-ID: <20250902-maple-tree-v3-1-fb5c8958fb1e@google.com> Subject: [PATCH v3 1/3] rust: maple_tree: add MapleTree From: Alice Ryhl To: Andrew Morton , "Liam R. Howlett" , Lorenzo Stoakes , Miguel Ojeda , Andrew Ballance Cc: Boqun Feng , Gary Guo , "=?utf-8?q?Bj=C3=B6rn_Roy_Baron?=" , Benno Lossin , Andreas Hindborg , Trevor Gross , Danilo Krummrich , linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, rust-for-linux@vger.kernel.org, linux-mm@kvack.org, Alice Ryhl Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable 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. Co-developed-by: Andrew Ballance Signed-off-by: Andrew Ballance Signed-off-by: Alice Ryhl --- 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 | 350 +++++++++++++++++++++++++++++++++++++++++= ++++ 6 files changed, 367 insertions(+) diff --git a/MAINTAINERS b/MAINTAINERS index fed6cd812d796a08cebc0c1fd540c8901d1bf448..c076f034562dd3d6b3679e8c2cd= 390adb312d483 100644 --- a/MAINTAINERS +++ b/MAINTAINERS @@ -14672,6 +14672,8 @@ F: net/mctp/ =20 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 =20 diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index bafe143b1f783202e27b32567fffee4149e8e266..879cd5f24be49548d5fd9d6b19b= f069e33c334a1 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)) =20 +/* + * When changing MA_STATE, remember to also change rust/kernel/maple_tree.= rs + */ #define MA_STATE(name, mt, first, end) \ struct ma_state name =3D { \ .tree =3D mt, \ diff --git a/rust/helpers/helpers.c b/rust/helpers/helpers.c index 7cf7fe95e41dd51717050648d6160bebebdf4b26..c5d42e0f7ce6786c1e96f8c0f27= 710959ca3362b 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 0000000000000000000000000000000000000000..1dd9ac84a13feed53c0ed5eec68= 05517081d0673 --- /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 ed53169e795c0badf548025a57f946fa18bc73e3..6b0a5689669fa691e366ab3f9d4= 62692c12bd548 100644 --- a/rust/kernel/lib.rs +++ b/rust/kernel/lib.rs @@ -96,6 +96,7 @@ #[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 0000000000000000000000000000000000000000..92930b408e9683b6615080a5380= 0f1a393c5f31e --- /dev/null +++ b/rust/kernel/maple_tree.rs @@ -0,0 +1,350 @@ +// SPDX-License-Identifier: GPL-2.0 + +//! Maple trees. +//! +//! C header: [`include/linux/maple_tree.h`](srctree/include/linux/maple_t= ree.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 =3D match range.start_bound() { + Bound::Included(start) =3D> *start, + Bound::Excluded(start) =3D> start.checked_add(1)?, + Bound::Unbounded =3D> 0, + }; + + let last =3D match range.end_bound() { + Bound::Included(end) =3D> *end, + Bound::Excluded(end) =3D> end.checked_sub(1)?, + Bound::Unbounded =3D> 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 branchi= ng 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. T= he maple tree will be + // destroyed in Drop before the memory location becomes invali= d. + tree <- Opaque::ffi_init(|slot| unsafe { bindings::mt_init_fla= gs(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 [`InsertError`] with the [`Occupied`] kind. It may also = fail if memory + /// allocation fails. + /// + /// # Examples + /// + /// ``` + /// use kernel::maple_tree::{InsertErrorKind, MapleTree}; + /// + /// let tree =3D KBox::pin_init(MapleTree::>::new(), GFP_KER= NEL)?; + /// + /// let ten =3D KBox::new(10, GFP_KERNEL)?; + /// let twenty =3D KBox::new(20, GFP_KERNEL)?; + /// let the_answer =3D 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..=3Dindex, value, gfp) + } + + /// Insert a value to the specified range, failing on overlap. + /// + /// This accepts the usual types of Rust ranges using the `..` and `..= =3D` syntax for exclusive + /// and inclusive ranges respectively. The range must not be empty, an= d must not overlap with + /// any existing range. + /// + /// # Errors + /// + /// If the maple tree already contains an overlapping range, then this= call will return an + /// [`InsertError`] with the [`Occupied`] kind. It may also fail if me= mory allocation fails + /// or if the requested range is invalid (e.g. empty). + /// + /// # Examples + /// + /// ``` + /// use kernel::maple_tree::{InsertErrorKind, MapleTree}; + /// + /// let tree =3D KBox::pin_init(MapleTree::>::new(), GFP_KER= NEL)?; + /// + /// let ten =3D KBox::new(10, GFP_KERNEL)?; + /// let twenty =3D KBox::new(20, GFP_KERNEL)?; + /// let the_answer =3D KBox::new(42, GFP_KERNEL)?; + /// let hundred =3D 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..=3D1000, 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_e= rr().cause, + /// InsertErrorKind::Occupied, + /// ); + /// + /// // When using .. to specify the range, you must be careful to ensu= re that the range is + /// // non-empty. + /// assert_eq!( + /// tree.insert_range(72..72, hundred, GFP_KERNEL).unwrap_err().ca= use, + /// InsertErrorKind::InvalidRequest, + /// ); + /// # Ok::<_, Error>(()) + /// ``` + pub fn insert_range(&self, range: R, value: T, gfp: Flags) -> Resul= t<(), InsertError> + where + R: RangeBounds, + { + let Some((first, last)) =3D to_maple_range(range) else { + return Err(InsertError { + value, + cause: InsertErrorKind::InvalidRequest, + }); + }; + + let ptr =3D T::into_foreign(value); + + // SAFETY: The tree is valid, and we are passing a pointer to an o= wned instance of `T`. + let res =3D to_result(unsafe { + bindings::mtree_insert_range(self.tree.get(), first, last, ptr= , gfp.as_raw()) + }); + + if let Err(err) =3D res { + // SAFETY: As `mtree_insert_range` failed, it is safe to take = back ownership. + let value =3D unsafe { T::from_foreign(ptr) }; + + let cause =3D if err =3D=3D ENOMEM { + InsertErrorKind::AllocError(kernel::alloc::AllocError) + } else if err =3D=3D 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 =3D KBox::pin_init(MapleTree::>::new(), GFP_KER= NEL)?; + /// + /// let ten =3D KBox::new(10, GFP_KERNEL)?; + /// let twenty =3D 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 =3D 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 i= nvalid 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 mapl= e tree, so we have + // exclusive access to the entire maple tree despite not holding t= he lock. + let mut ma_state =3D unsafe { MaState::new_raw(self.into_ref().get= _ref(), 0, usize::MAX) }; + + loop { + // This uses the raw accessor because we're destroying pointer= s without removing them + // from the maple tree, which is only valid because this is th= e destructor. + let ptr =3D ma_state.mas_find_raw(usize::MAX); + if ptr.is_null() { + break; + } + // SAFETY: By the type invariants, this pointer references a v= alid value of type `T`. + // By the safety requirements, it is okay to free it without r= emoving 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 t= o 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 f= or `'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 =3D> EEXIST, + InsertErrorKind::AllocError(kernel::alloc::AllocError) =3D> EN= OMEM, + InsertErrorKind::InvalidRequest =3D> EINVAL, + } + } +} + +impl From> for Error { + #[inline] + fn from(insert_err: InsertError) -> Error { + Error::from(insert_err.cause) + } +} --=20 2.51.0.338.gd7d06c2dae-goog From nobody Fri Oct 3 11:25:00 2025 Received: from mail-wm1-f74.google.com (mail-wm1-f74.google.com [209.85.128.74]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id BAF882E3376 for ; Tue, 2 Sep 2025 08:35:27 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.74 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1756802129; cv=none; b=gZI8i6awWfJT+ge5Wto6yR6EvDwGyrG1MYHU3r3MjN+AUUcVlpDiobIz6Boi6i+i7DqNGYfOgA4BbxGpDfEi1yM7AZHlV05PJcMB9nUpRVF77+ya+ybQK3XUb7cAso7h0nL9AeSX3ZRrW+7aR8F3YCbTjb7JXOu/NiIWWyp4fzA= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1756802129; c=relaxed/simple; bh=nJ4NJu0LybzY2zkJ2emxxPlNYEf0DKlu/x4dn5/0JEM=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=rpRW0UeveOvTMxQ7PE4k7Y58EjEOhKgWoJjg4VB0ad8H+PLKmuwfTk6I9Kl7TpihcP9Q1rPpB3fKFJ/u9dusCBVaOmiGYy8k7+5jq+6IAP97C/y1jEJPF4Iwb8NFD2zoJoxOBDq3MQxCP8oBICJ/LNypq3ttcHCFYDrzBuaOuBw= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com; spf=pass smtp.mailfrom=flex--aliceryhl.bounces.google.com; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b=Jw4ijs7+; arc=none smtp.client-ip=209.85.128.74 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=flex--aliceryhl.bounces.google.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="Jw4ijs7+" Received: by mail-wm1-f74.google.com with SMTP id 5b1f17b1804b1-45b8a307c12so10513945e9.2 for ; Tue, 02 Sep 2025 01:35:27 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1756802126; x=1757406926; darn=vger.kernel.org; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=yU/qze8dnCVYV9LdgeGw8Qx81Z2zaCpIf3GwmuTVni8=; b=Jw4ijs7+S9EOlwmNmNnK9jL2RmOmVfWzMdBuiTVn+8vtv4o8kgWKFHiXZxML3rh7EU krb40QbVkwG1x0ZDoQSH05VCtHPU6hzRGKtC9QkRBVI9fcu70gDo0FqI/vPEvGCXgz/j 5J4jOgSoBvfddz5vuNQNNmKWYtMdGh/gVUS4Q2R+ksAMisx/rae/NM9k7VoPvz+/PvUV MEKPuRnymaDhPRf8U9w7nX69I/1gTAVEOyXDlQ1jvWZ9MbEk1MhDQ7z0TFj0h+RQ079I K1yDoSY4ykXLIfYSfqtl2mWeQ1NVFNcurj2YPCjCxdAKjWxCK5+gLNR6HV5mHb7nacDH Nsqw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1756802126; x=1757406926; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=yU/qze8dnCVYV9LdgeGw8Qx81Z2zaCpIf3GwmuTVni8=; b=AzIdH5M0FPE4SQE6gadM5xpiItg9qaiP3sz8R7pnCTDNhHFar426qNMAPN311Yz92E X28EhprD6AoyZdBIyboRlTUNDGBdvDuePqDzZx+sB1UeEFr0hVBgZMGYOighpIBRJSTF dSbuyJmaasa38Byrn1JjO6CZmCmE3L3vdaBKZGxEduqY9sHafLrg4PUirv5fHX89a+YT s46dy6U6gWwSeGDZUW3nWM0Y/rFul46IFfLighrqDumpQcVvmwg7j4cHYcnIDMs1E2Rx X0wx0bUFsfHOqS/8v6/qO8Q5vBjJvUR2etYi5NsDycm/O5vkRmaSL3VVLuwwhGDsS0Jf VhgQ== X-Forwarded-Encrypted: i=1; AJvYcCXMqrex3IIcQtFY5D7EhWoA+FKg9JCJTooRY4s5Ix84GeWP71qL8DkQlez9xXyZxgwehVp+DCevg3EJugc=@vger.kernel.org X-Gm-Message-State: AOJu0YwD5JZJa9g0de3j+lelC+2zooJJyQKYrNPWbnpMl4QUOu+sk5IU 9gnI2lFg4W5CQt+wwtSd0kNz0Os+fdkWKoUgeZZE1jg7hAB6tDZVHNNSNdiccxKGqBXKIX0BCZd qc2QShG6wW3FvtCtnHQ== X-Google-Smtp-Source: AGHT+IF9928G/RDg2POiXYCI34J+xuTtH6eAcRQJR35jKk9M8durBru7tDsICbW5x3aIHL35LsHQddUk2mV3/BQ= X-Received: from wmbji5.prod.google.com ([2002:a05:600c:a345:b0:45b:6337:ab6b]) (user=aliceryhl job=prod-delivery.src-stubby-dispatcher) by 2002:a05:600c:3b10:b0:45b:8f38:8d36 with SMTP id 5b1f17b1804b1-45b8f388f6bmr46148565e9.30.1756802125863; Tue, 02 Sep 2025 01:35:25 -0700 (PDT) Date: Tue, 02 Sep 2025 08:35:12 +0000 In-Reply-To: <20250902-maple-tree-v3-0-fb5c8958fb1e@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20250902-maple-tree-v3-0-fb5c8958fb1e@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=7291; i=aliceryhl@google.com; h=from:subject:message-id; bh=nJ4NJu0LybzY2zkJ2emxxPlNYEf0DKlu/x4dn5/0JEM=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBotqxKQ+d3ZZgeyrKEU5/GOWnEUUFAc5xT7zm4Q O8tyRrg2oKJAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCaLasSgAKCRAEWL7uWMY5 RnkpD/0TBPpWD3MjV+voZaXzEqa7zbKJ9DhcwELxJRxNJcjje1sdHMNeDDMB037HLZ9R5Ov+UK8 3hPPN4VvrZNLAacgug22uk78Nt8iKt6vyKESlYNMeEcdws0fJBv4EhPPrPhaGDnEENDqUjbyA3r 5cRrs55j/1zntPUsfEFzxCcQ0j77AqS0Wtsq7WjWotnXreo6Yd9B8BHEM7l5FghQkNY6/9gitZT YwtInur31cI9a/NNpWUO08M5J4Ts3LVi6byLc+F0irXsopiYvZLq9AxJ17h6nfncYt73pJ33A5a 4D7pnAfokEm6lxVXLqumsnqvvMTHtQnKHO7uGW/UP3pl/ME5EdtIhODxEqBE7re0iAGIziZVyf3 z2oeOzMgNSn2iOb3JkWcOfrojE3d6/2E6ZWLXnpbReqYdwer+P2kczv309G/VTNQXwz2cmz+CTi EyAtDplm87xrTkgQKfxksIb7ETtQc0LrwQjR8r82ebxqdhY1A829fibWbHJ8IUIm1OWsAQe1iW3 5ere3lQc3ZmojOh4JmT3j42X8okZfFhWPh2YcefcAoElVEWqnmRTtzp+WfaqDhrFqOS6aHwkHJc 0w3t09uagfg7KRhSZodLY32hdckfc5uJJsb8coEUGQkp3sV0oSEj1vG2XFww6+DG4WZKTJhgY7U UKXWhPpsWvXHzUQ== X-Mailer: b4 0.14.2 Message-ID: <20250902-maple-tree-v3-2-fb5c8958fb1e@google.com> Subject: [PATCH v3 2/3] rust: maple_tree: add lock guard for maple tree From: Alice Ryhl To: Andrew Morton , "Liam R. Howlett" , Lorenzo Stoakes , Miguel Ojeda , Andrew Ballance Cc: Boqun Feng , Gary Guo , "=?utf-8?q?Bj=C3=B6rn_Roy_Baron?=" , Benno Lossin , Andreas Hindborg , Trevor Gross , Danilo Krummrich , linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, rust-for-linux@vger.kernel.org, linux-mm@kvack.org, Alice Ryhl Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable 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. Co-developed-by: Andrew Ballance Signed-off-by: Andrew Ballance Reviewed-by: Andrew Ballance Reviewed-by: Danilo Krummrich Signed-off-by: Alice Ryhl --- rust/kernel/maple_tree.rs | 140 ++++++++++++++++++++++++++++++++++++++++++= ++++ 1 file changed, 140 insertions(+) diff --git a/rust/kernel/maple_tree.rs b/rust/kernel/maple_tree.rs index 92930b408e9683b6615080a53800f1a393c5f31e..24b674ce07d0481702eccd86a79= 20f94ca000108 100644 --- a/rust/kernel/maple_tree.rs +++ b/rust/kernel/maple_tree.rs @@ -214,6 +214,23 @@ pub fn erase(&self, index: usize) -> Option { unsafe { T::try_from_foreign(ret) } } =20 + /// 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 =3D unsafe { &raw mut (*self.tree.get()).__bindgen_an= on_1.ma_lock }; + lock_ptr.cast() + } + /// Free all `T` instances in this tree. /// /// # Safety @@ -257,6 +274,91 @@ fn drop(mut self: Pin<&mut Self>) { } } =20 +/// A reference to a [`MapleTree`] that owns the inner lock. +/// +/// # Invariants +/// +/// This guard owns the inner spinlock. +#[must_use =3D "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 =3D KBox::pin_init(MapleTree::>::new(), GFP_KER= NEL)?; + /// + /// let ten =3D KBox::new(10, GFP_KERNEL)?; + /// let twenty =3D KBox::new(20, GFP_KERNEL)?; + /// tree.insert(100, ten, GFP_KERNEL)?; + /// tree.insert(200, twenty, GFP_KERNEL)?; + /// + /// let mut lock =3D 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 =3D KBox::pin_init(MapleTree::>::new(), GFP_KERN= EL)?; + /// + /// let ten =3D Arc::new(10, GFP_KERNEL)?; + /// let twenty =3D 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 =3D 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 =3D 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 th= is 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 @@ -310,6 +412,44 @@ fn mas_find_raw(&mut self, max: usize) -> *mut c_void { // 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 =3D KBox::pin_init(MapleTree::>::new(), GFP_KERN= EL)?; + /// + /// let ten =3D Arc::new(10, GFP_KERNEL)?; + /// let twenty =3D Arc::new(20, GFP_KERNEL)?; + /// tree.insert(100, ten, GFP_KERNEL)?; + /// tree.insert(200, twenty, GFP_KERNEL)?; + /// + /// let mut ma_lock =3D tree.lock(); + /// let mut iter =3D 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 =3D 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 thi= s `MaState`, and the + // `MaState` has read/write access to the maple tree. + Some(unsafe { T::borrow_mut(ret) }) + } } =20 /// Error type for failure to insert a new value. --=20 2.51.0.338.gd7d06c2dae-goog From nobody Fri Oct 3 11:25:00 2025 Received: from mail-wm1-f73.google.com (mail-wm1-f73.google.com [209.85.128.73]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id BFB162EA179 for ; Tue, 2 Sep 2025 08:35:28 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.73 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1756802131; cv=none; b=leisqngpfN8pAHJhaj/SDZbimGRtjk68gxmJLj8szWxTEmzOsBIarUNtpm+cJ5Wpa4Rhi3yUaf1IgKy7drhtkaQHswlL6CTAgjiYblFXa1pDZMF4elSvBrKgSG525sEEgSsTqSBXyGJQ4mlHzp57tnAkoaVX6ji5fmQLxo5kxZc= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1756802131; c=relaxed/simple; bh=4uYv4Iubagq9TjaCiZNut2UuDeIkZERacgR6dwoufHI=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=jj3V5TTA7tvUm1LZYDFCzVNhnhmTqaNdazGaqOMyqefZJkdaMHUMbmXCjcxKzigJld7EbP6MG6Ysrw9IjNXgaYcnhkdbMwrc2gatjq1WUb3UfZN+LJiB+4HdzPSdFF7bl6y7H/orWDuaQezyyjs25UMpdxcXwqJOTKD6BM2UWlw= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com; spf=pass smtp.mailfrom=flex--aliceryhl.bounces.google.com; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b=Rqzi1AEL; arc=none smtp.client-ip=209.85.128.73 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=flex--aliceryhl.bounces.google.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="Rqzi1AEL" Received: by mail-wm1-f73.google.com with SMTP id 5b1f17b1804b1-45b71fe31ffso30461745e9.2 for ; Tue, 02 Sep 2025 01:35:28 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1756802127; x=1757406927; darn=vger.kernel.org; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=aIl0NUntKEgDp6p26JUsJurVmE5xFk9G5xfjA7uAipw=; b=Rqzi1AELg3NGZPHalg1oYXqgbzc0B2hplCl3+i3N41eT3OOO1TB8CIRYgGPGFCF/bD dGeaztOohnYKF/JqE/5PPSpCGU0wRD2MwN68P8Hcpt9pKGNuguhIFUhGh1itUnQNUFNE Iq8w0rHRLUSt2oTZBwQ70yQjSj8m+XQKNuZlNkZnB1IiAPioaqlMpdOFDrYaU9bu37TR FT70nNvcIOU0Za9dJGdnS/opnU3T1LTv/r+K6LlGPi2b+S/CSFkZ+se/975YWKlG8ZSy n7Vyp00/3IpyPjhY+ONPJ4rpp2Eyd8BWsAJNWlU7gFod5NLomLHmm3sIUHC4mH8VHaDI AnqA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1756802127; x=1757406927; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=aIl0NUntKEgDp6p26JUsJurVmE5xFk9G5xfjA7uAipw=; b=XR7h6N3APxsx4KI8o5LCWmKyNir5oB8QU5m8FVUHc9gLUNXW+LGEAMyv/i8YfqCU6f OolVcXqoeo6+aRJw4oAjB42CZPw0xy9hQiytNNw5u8yZX0O/abRBAItOoc0d6/hRRweD HpiW30I52mDvfsxa/i6rT59KuCfcFKkPxljfl8Bx4IeByaCLN+QE84tRfNE9xJT+QUvQ puIbKeIn0MexnuR6p58WPbmeee0GVLTyc2xT1PEmj2EmdXn3hcPdruZcwxH24aVp6/cy gXFlDrEEKVjUH9GHt3lquhjAWRJmBIcpPQ3rmzpgGUnx+HKKv+hkdBandcoW/mzY5APd nKHA== X-Forwarded-Encrypted: i=1; AJvYcCXdBgszQIvIL4lh1ogVWMYx+T5sSCT9zvX/3Ejr9ZaTpv8BLwh+zZPzTM1WBz0ziEKE4WEy5jYR/Uc0yXo=@vger.kernel.org X-Gm-Message-State: AOJu0Yxpbp2C/u6U9U4wZUyuQa+h4eHFaFevcKsqeY0+BQT/CaLM/aa9 YCcv4IsgBbNQ/YUAABQaKTJHDreYDGeYG94OUIOIDXrKF/k1O2nsLg+22a9b4lS2w77MSI8xgqs qkVLiQoQ/7EphiHzXCw== X-Google-Smtp-Source: AGHT+IEUSQM7nZXMzj+AIYbd6XN4GdZq1gsDpWixNjdGWvgeC8W+TzZqnS/0jc0vD0/bKpKJe9KRqMdH7F9ulyU= X-Received: from wmsr6.prod.google.com ([2002:a05:600c:8b06:b0:45b:7a6f:5dc0]) (user=aliceryhl job=prod-delivery.src-stubby-dispatcher) by 2002:a05:600c:1f84:b0:45b:7ce0:fb8a with SMTP id 5b1f17b1804b1-45b8559bd2fmr85044535e9.35.1756802127114; Tue, 02 Sep 2025 01:35:27 -0700 (PDT) Date: Tue, 02 Sep 2025 08:35:13 +0000 In-Reply-To: <20250902-maple-tree-v3-0-fb5c8958fb1e@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20250902-maple-tree-v3-0-fb5c8958fb1e@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=6643; i=aliceryhl@google.com; h=from:subject:message-id; bh=4uYv4Iubagq9TjaCiZNut2UuDeIkZERacgR6dwoufHI=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBotqxK9LELnU0l7nr6Ds+UR7jzifKGecSBsFYX6 GjCSHj4OhKJAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCaLasSgAKCRAEWL7uWMY5 RivPEACozBYZQe8keKEhBEblZVlxG9uN6kQfOkkFjspfe41X5Ikn0hBIloZvsK5jq/peLsY7xzj Vw2Zl8ahbagtvMbHy2iUIzRw/vGBBGV93VmxtQPOxL31NMi7YzBBpvEQlx3sZbL1qEOqJAgfx/t CCtGcH08JoB2YdIHYWn6etDM21QIeJav8mVBfSemvZ6IYmd9V8WJJFrULQ2orZzgU8cvtnGBTMl 7pffN32gyEbvwwEKLTjk1bOYbJUORkRf0Av5CW9P9HOVBPxqxB2tlv1pftqT8Qy9uEcEDg6BSUx VvR6qFyD+QoNkLk3mUdgdFiIV9cKZLyI7cA80dnpvlYtqeWMRhBPaQsj8tj47t7P5Vh0bEuFSou SkFGv78+4CdvMMd3CwQxUPPx3P+qc5ZB57Tf0GucXv2u6fiDljO40HTMbLgHZrJ4u8jy8wIbM5g u864horwELA7jXzvTdEZQ2+KlFo9rPwuWxCNiL7zx/+bFfyb6tG3GSJR9AxJQXS24fJLWq8QSXY Xou4vc+3SJUwsF8DClEyudG2FhB9+pYRY3k0RQt6zggxrfw3yjk1BU4mtpYb2qWaXF3k3qc0SYY CFZWL+apaExJqC3X2pVAdvqBfoEo9OPKgdaMVSihvO0A7sQyz0P1RjyFHLGxbd4x6AcxU83/RAz pkLtbiY3v7g59fw== X-Mailer: b4 0.14.2 Message-ID: <20250902-maple-tree-v3-3-fb5c8958fb1e@google.com> Subject: [PATCH v3 3/3] rust: maple_tree: add MapleTreeAlloc From: Alice Ryhl To: Andrew Morton , "Liam R. Howlett" , Lorenzo Stoakes , Miguel Ojeda , Andrew Ballance Cc: Boqun Feng , Gary Guo , "=?utf-8?q?Bj=C3=B6rn_Roy_Baron?=" , Benno Lossin , Andreas Hindborg , Trevor Gross , Danilo Krummrich , linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, rust-for-linux@vger.kernel.org, linux-mm@kvack.org, Alice Ryhl , Daniel Almeida Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable 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. Reviewed-by: Daniel Almeida Reviewed-by: Danilo Krummrich Signed-off-by: Alice Ryhl --- rust/kernel/maple_tree.rs | 158 ++++++++++++++++++++++++++++++++++++++++++= ++++ 1 file changed, 158 insertions(+) diff --git a/rust/kernel/maple_tree.rs b/rust/kernel/maple_tree.rs index 24b674ce07d0481702eccd86a7920f94ca000108..31b6c13d08efab23f7fb20bf97e= 36c33bf9f6ad9 100644 --- a/rust/kernel/maple_tree.rs +++ b/rust/kernel/maple_tree.rs @@ -32,6 +32,26 @@ pub struct MapleTree { _p: PhantomData, } =20 +/// 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 =3D MapleTree; + + #[inline] + fn deref(&self) -> &MapleTree { + &self.tree + } +} + #[inline] fn to_maple_range(range: impl RangeBounds) -> Option<(usize, usize)= > { let first =3D match range.start_bound() { @@ -359,6 +379,107 @@ pub fn load(&mut self, index: usize) -> Option> { } } =20 +impl MapleTreeAlloc { + /// Create a new allocation tree. + pub fn new() -> impl PinInit { + let tree =3D pin_init!(MapleTree { + // SAFETY: This initializes a maple tree into a pinned slot. T= he maple tree will be + // destroyed in Drop before the memory location becomes invali= d. + tree <- Opaque::ffi_init(|slot| unsafe { + bindings::mt_init_flags(slot, bindings::MT_FLAGS_ALLOC_RAN= GE) + }), + _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 err= or will be returned. + /// + /// The index of the new range is returned. + /// + /// # Examples + /// + /// ``` + /// use kernel::maple_tree::{MapleTreeAlloc, AllocErrorKind}; + /// + /// let tree =3D KBox::pin_init(MapleTreeAlloc::>::new(), GF= P_KERNEL)?; + /// + /// let ten =3D KBox::new(10, GFP_KERNEL)?; + /// let twenty =3D KBox::new(20, GFP_KERNEL)?; + /// let thirty =3D KBox::new(30, GFP_KERNEL)?; + /// let hundred =3D KBox::new(100, GFP_KERNEL)?; + /// + /// // Allocate three ranges. + /// let idx1 =3D tree.alloc_range(100, ten, ..1000, GFP_KERNEL)?; + /// let idx2 =3D tree.alloc_range(100, twenty, ..1000, GFP_KERNEL)?; + /// let idx3 =3D 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)) =3D to_maple_range(range) else { + return Err(AllocError { + value, + cause: AllocErrorKind::InvalidRequest, + }); + }; + + let ptr =3D T::into_foreign(value); + let mut index =3D 0; + + // SAFETY: The tree is valid, and we are passing a pointer to an o= wned instance of `T`. + let res =3D to_result(unsafe { + bindings::mtree_alloc_range( + self.tree.tree.get(), + &mut index, + ptr, + size, + min, + max, + gfp.as_raw(), + ) + }); + + if let Err(err) =3D res { + // SAFETY: As `mtree_alloc_range` failed, it is safe to take b= ack ownership. + let value =3D unsafe { T::from_foreign(ptr) }; + + let cause =3D if err =3D=3D ENOMEM { + AllocErrorKind::AllocError(kernel::alloc::AllocError) + } else if err =3D=3D EBUSY { + AllocErrorKind::Busy + } else { + AllocErrorKind::InvalidRequest + }; + Err(AllocError { value, cause }) + } else { + Ok(index) + } + } +} + /// A helper type used for navigating a [`MapleTree`]. /// /// # Invariants @@ -488,3 +609,40 @@ fn from(insert_err: InsertError) -> 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 =3D> EBUSY, + AllocErrorKind::AllocError(kernel::alloc::AllocError) =3D> ENO= MEM, + AllocErrorKind::InvalidRequest =3D> EINVAL, + } + } +} + +impl From> for Error { + #[inline] + fn from(insert_err: AllocError) -> Error { + Error::from(insert_err.cause) + } +} --=20 2.51.0.338.gd7d06c2dae-goog