From nobody Mon Oct 6 01:21:08 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 555A8254846 for ; Sat, 26 Jul 2025 13:23:40 +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=1753536222; cv=none; b=sIot850dUbZXAgDK5V8JXSD49jNyAYECApLg4uBuUDx9rJr5F0hz32gftZWzdf3+DxFV/AiA0TDx5pph/HMYji/pKiyb8xU6OYQo9QsBV8/R2+Xja5TptRmoSxNeByazsV9KHXOsnnCsn2JJkEQkjZfj7/neqyVusVe3tStRMB4= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1753536222; c=relaxed/simple; bh=/s6gfSpqDdCSnaheBqpAoG2Dm6F494kNwuGs999ee7s=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=C9dhwyldamBBnVoDhGVwgDSB/7KfUUWDas03Wd+8/pRRQefdIYIFm3CB/ufDLgkJjeOHryZZ2zbUVdNnrRPJBXjLL0ZiqeR5ckxKaro/Pfc2a6HdeA1LVDk8CIkm5dtOG0p2apk7hm8n7hbHlPL/k1VfEpir3spj7OrxYIq17gE= 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=fW+77Udt; 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="fW+77Udt" Received: by mail-wm1-f73.google.com with SMTP id 5b1f17b1804b1-4560b81ff9eso17582155e9.1 for ; Sat, 26 Jul 2025 06:23:40 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1753536218; x=1754141018; 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=mOgrqjxNs+ME3TRVLi3Dz5HUWyMBAvnljc5iO01PwNw=; b=fW+77Udt8QL39PIfJ9y9YuvXAHSXGooj4GlLxD3n6LeKBAv9pV+mR8HTgOmHSQZKz9 5i19wrqPJ6zsSCOEn0HngGmjrkKxjbzP/t7+yG77NhtMPgo2owViOA4q1ZIXCLWQqKrO fGzS8UAq7r+hwzCJc+lAYFu/d5IrvVwA1QfaYttG29D4OEKnByQeZ5zBFD0Zi4ZuYoCP DZ1xFfmNWiVe5bT6duW40S8Let1oPHz2640CaEfPYSFPLi7FuojYjMD91FiEw3f0YR4t 6md5lZT7epIWhFbdQs4jv3ch3/wvAddy/k9nEfc0KiU6LbxT+pxJqMu9HcpfhAxeWK6P cUgw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1753536218; x=1754141018; 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=mOgrqjxNs+ME3TRVLi3Dz5HUWyMBAvnljc5iO01PwNw=; b=PiKgmBMDOCmoWVxR+fPVWEXPVFbMffG1xOXcC3JCp1eehOkmB4McNDQsUTiEd6LneI AOB++JzuR8187kIwaYjMi4WrqGLGUOoqOAbV2pM6GDKh8iWmJ2oyoltCRhr76pZ6ur8N cLHeqaH2XSmYUKkRr80UWbybJG4ElfwgRt1bpVbJGAYaCTk4LeFVYrzlYZYsbXwzQeOw +zdRc5KqBSryWnSglritt56SCdda18Stz8K4wqlVdPBvAJdYzdOm06gKcAnPJNHNnyyj I2TBVrFfuOGUCGhDDfHhop8B2DBekkQ6BWrgyAlmKfaxAgQ8/JvTMj0xz001hIaJHH7m 7eyQ== X-Forwarded-Encrypted: i=1; AJvYcCWHQDUk6cctr6cCXDr4nw1UKaTRYVhFZHBpbR1hIclESVuD7vzUokHSojAa+AY9zBUJjLjF5lG9M8T7JAE=@vger.kernel.org X-Gm-Message-State: AOJu0YyGcWXmgmfIiKs/YY5FT1peoEjbjyxU3CE7e1vdJrhj1JV8kUSJ MMmx26hgofKh3ry0YE1BCDxbQDbSZO2F4izSMh5Yt3xXqNDuzFlFIPzt2DlMk8ozLsh0r1hXc+c A5aPuzLz4gW0ZzV3BUA== X-Google-Smtp-Source: AGHT+IFW+sosLpBC3hAiy/WbKUPwUhqAUUKGCza0DLkkmUdeskkFQ5j/yn0WWMqf/jLDp+Yh/wNPw6HRQCEhSGo= X-Received: from wmbes24.prod.google.com ([2002:a05:600c:8118:b0:456:fa0:e0ba]) (user=aliceryhl job=prod-delivery.src-stubby-dispatcher) by 2002:a05:600c:6286:b0:43d:42b:e186 with SMTP id 5b1f17b1804b1-45876306fd4mr48948825e9.8.1753536218717; Sat, 26 Jul 2025 06:23:38 -0700 (PDT) Date: Sat, 26 Jul 2025 13:23:22 +0000 In-Reply-To: <20250726-maple-tree-v1-0-27a3da7cb8e5@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20250726-maple-tree-v1-0-27a3da7cb8e5@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=12995; i=aliceryhl@google.com; h=from:subject:message-id; bh=/s6gfSpqDdCSnaheBqpAoG2Dm6F494kNwuGs999ee7s=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBohNbXJfFTN7BatwxcEg0q0vZgUlLfKhZS3re5w Zc/eUhAeP2JAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCaITW1wAKCRAEWL7uWMY5 RlVNEACPzUnzhOS4na+O8N6i5c+BFIkyyxJuzR2ikLHXluax6sslQTsBpePSiTe2cjrm6LIjhMa IBhIuaJKDH9mtzjopgVrLUlwySZRed8M/8vUak2xUk/wLHWz6pORFNT/XbJx7QdQlINwSSpgcUN pg+yiYb1uRVc5o7NarNfz6VlLsGbx8G/D9YwpeWrep9FchHbUdyIJDHqT4BL9tI5g61hotn8aS/ b7sgqPvFY5oJUPzEqQV3gYmBIDNyZB7Vucy/3xJgZsWZSGeLdPr/jY5ltfDMZFS0C7PhPJarJsE MP606QlWXLE4TgvXXvOHYSGum3fsFhL4dKixVe/gOmUrL9S5YjJEok2CzGYutbNQGELaE02DwKU BDB9aVH+m8Vx5tvjDaXo6dgvinaCzJoMZaExg5B+katfcfXIzLsgrDvBvTYEkoY9F3AsCY5ohv0 TqlFbYjU1GWxHMDTkoLyyeHLIYZ3oWvhfSmwgXhu3wOLaII7ZpMU7Eni8TNeIPCsxpsptMwaBYM 9ATsyKeifVlWeO+75VOFuIHVpSiuHXZb8tOmsK57zcWdw8ukoCI3SuHJ2y3YYaFZd8dD5Cvt7J+ HY3jPwm2YSOlIaAvOfUAKnUs7PP9GDbaIhxlY5lj7+vGs0Viqy4UIZRjLVCd/oxFrTsftS9eHi9 0+ocYIZa205uVfQ== X-Mailer: b4 0.14.2 Message-ID: <20250726-maple-tree-v1-1-27a3da7cb8e5@google.com> Subject: [PATCH 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 | 2 + rust/helpers/helpers.c | 1 + rust/helpers/maple_tree.c | 14 +++ rust/kernel/lib.rs | 1 + rust/kernel/maple_tree.rs | 286 ++++++++++++++++++++++++++++++++++++++++++= ++++ 5 files changed, 304 insertions(+) diff --git a/MAINTAINERS b/MAINTAINERS index dd810da5261b5d664ef9750f66ec022412e8014b..b7e7308ce07c050239c14c4f3a0= fd89bdd8e8796 100644 --- a/MAINTAINERS +++ b/MAINTAINERS @@ -15956,7 +15956,9 @@ L: rust-for-linux@vger.kernel.org S: Maintained W: http://www.linux-mm.org T: git git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm +F: rust/helpers/maple_tree.c F: rust/helpers/mm.c +F: rust/kernel/maple_tree.rs F: rust/kernel/mm.rs F: rust/kernel/mm/ =20 diff --git a/rust/helpers/helpers.c b/rust/helpers/helpers.c index 0683fffdbde25b89d285e3b0d8e6d8f7f5fd7474..ed7888a2661ad91f0fb78023311= b3a266d30615c 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 "page.c" diff --git a/rust/helpers/maple_tree.c b/rust/helpers/maple_tree.c new file mode 100644 index 0000000000000000000000000000000000000000..119665846e8e8b018f8dc791a22= fe20ace8e9c2c --- /dev/null +++ b/rust/helpers/maple_tree.c @@ -0,0 +1,14 @@ +// 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); +} + +struct ma_state rust_helper_MA_STATE(struct maple_tree *mt, unsigned long = start, unsigned long end) +{ + MA_STATE(mas, mt, start, end); + return mas; +} diff --git a/rust/kernel/lib.rs b/rust/kernel/lib.rs index 11a6461e98daab597e1eb2b513c5123686a1bb73..6cc152090a2f1986781800897ad= 48947c2d02e40 100644 --- a/rust/kernel/lib.rs +++ b/rust/kernel/lib.rs @@ -88,6 +88,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..0f26c173eedc7c79bb8e2b56fe8= 5e8a266b3ae0c --- /dev/null +++ b/rust/kernel/maple_tree.rs @@ -0,0 +1,286 @@ +// 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}, +}; + +use kernel::{ + alloc::Flags, + error::code::{EEXIST, ENOMEM}, + 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. + #[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. + /// + /// If the maple tree already contains a range using the given index, = then this call will fail. + /// + /// # Examples + /// + /// ``` + /// use kernel::maple_tree::{MapleTree, InsertErrorKind}; + /// + /// 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. + /// + /// # Examples + /// + /// ``` + /// use kernel::maple_tree::{MapleTree, InsertErrorKind}; + /// + /// 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::Nomem + } 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, InsertErrorKind}; + /// + /// 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)?; + /// + /// let twenty =3D tree.erase(67).unwrap(); + /// assert_eq!(*twenty, 20); + /// + /// let ten =3D tree.erase(275).unwrap(); + /// assert_eq!(*ten, 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. + /// The caller must ensure that no reference that remains in the maple= tree is used incorrectly + /// after this call. + unsafe fn free_all_entries(self: Pin<&mut Self>) { + // SAFETY: The pointer references a valid maple tree. + let ma_state =3D unsafe { Opaque::new(bindings::MA_STATE(self.tree= .get(), 0, usize::MAX)) }; + + loop { + // SAFETY: The maple tree is valid. This call to `free_all_ent= ries` has exclusive + // access to the maple tree, so no further synchronization is = required. + let ptr =3D unsafe { bindings::mas_find(ma_state.get(), 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. + unsafe { drop(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 have a destructor. + if core::mem::needs_drop::() { + // SAFETY: The tree is valid, and other than the below `mtree_= destroy` call, it 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()) }; + } +} + +/// 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)] +pub enum InsertErrorKind { + /// There is already a value in the requested range. + Occupied, + /// Failure to allocate memory. + Nomem, + /// The insertion request was invalid. + InvalidRequest, +} + +impl From for Error { + #[inline] + fn from(kind: InsertErrorKind) -> Error { + match kind { + InsertErrorKind::Occupied =3D> EEXIST, + InsertErrorKind::Nomem =3D> ENOMEM, + InsertErrorKind::InvalidRequest =3D> EINVAL, + } + } +} + +impl From> for Error { + #[inline] + fn from(insert_err: InsertError) -> Error { + Error::from(insert_err.cause) + } +} --=20 2.50.1.470.g6ba607880d-goog From nobody Mon Oct 6 01:21:08 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 D4CBD28640D for ; Sat, 26 Jul 2025 13:23:41 +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=1753536223; cv=none; b=sDTock5d78It/ToAHplFi4ymA8kQxzlttd2UY9gB/cdDbtGt8CqP23o2tVI8aw+iyHzg55jroWi+B4CV43O0EWlYYfN9sKVLet+WvGry2qsuGe77kow8DMR/RNi2Phxdkjvce0nnFXU2mlEOKpoSIu9t5RLu6thCK9h0AYzP1Gs= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1753536223; c=relaxed/simple; bh=jbvUxSZMSHeAOtb+L6zXp20Ut43R/IhAlazvT1nIoks=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=CGxaWvxdgHxieqYvy1szl9GG+M+HeyAjtLM1hqPje38LSgQP7D9GXoIqTiznj0wgGu2VRmHL/cx/ZR7uaOMBempsCHpFjEQlRYrKy2enZuF2IG7EHZ2dqhUYNZodtYzydfHIb116k3YvWD5s57Ogy5SBF0bhEEgk/9NdPeUxfSg= 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=gAfSDroJ; 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="gAfSDroJ" Received: by mail-wm1-f74.google.com with SMTP id 5b1f17b1804b1-4561bc2f477so16105075e9.0 for ; Sat, 26 Jul 2025 06:23:41 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1753536220; x=1754141020; 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=l1PlHNrbkB2wLR+NzxgcoFHAW2vBd+j3ocXDrnNRVwo=; b=gAfSDroJEUNSY1IrfPbc1Wd0aIIA4RoLA5tx4tbl7rN83+iS1ar6dvDus1sGWCvjZQ aDg9cJ7wiBKJlMCMYNy18Me4zctOJdD2Wj4rg+0JgmzKgJVOOgk5OEKti5oV5mJoy6bl uz41ThA8lYhRvrDp+RTNV8OD9W4Us2I6nmnBkmJ3dwKGTjYtsNY2ZCqgXk5pI9G2/ads 6IKxY0A1bGs8kvcY2PIDHken9L8v6bMzo7H/4GVc1wFLGq2KZlGA5ElUldwhZZpZs01P sW2FuR8KQ1s17igKfjGKNt1YpcqycOk6JiboRkr9PDGMuQLfHoDpR9BrQV1TKX0oEbSG pnBA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1753536220; x=1754141020; 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=l1PlHNrbkB2wLR+NzxgcoFHAW2vBd+j3ocXDrnNRVwo=; b=qQJD12SUIrzTemztjS+p7Dp1M6u9wCWLM0xxhS/03iXSNyXBZ9oEosoivXQpTLR3Qs YfZweyTTQLyVysdwQO0w9gW2H170klGLB9iU6goE/sEdv8+RnPkFwaHMuuthiZWKsxT9 WlVd5L8FuVSpi2ryPVrNOwd99cJcYBqkmdPiOFZ7wD3qSKkvAhR8qf80yY3OmXBGPaTI KAqYu1PfQRfBdHLa04hNym6f7hlxbbj33EklVzvrdzt8dvUzjuOeVJLPkFMTMHieibmh OWUBBPJePY3rbELw7uwAKP33lCx25uewbuOLtGq//HTeyc14wE4MgK6QgSRmaoAy+UUN s69A== X-Forwarded-Encrypted: i=1; AJvYcCV8ymqZAhTko+1HBZZTiszy2+5vS2P1wIdxG12A+6backujCn3kdeinv81slHIWCYwdtBaa9k1AEEC7bXQ=@vger.kernel.org X-Gm-Message-State: AOJu0Yx9gYJ7fPZw9UH7cCfWGFYRtHRrvpMXgyDh+OFha0rffTBiX0Pl 2k8vYmQQ+gwJZbXKLVy7G1vWynP6U0Lx9ES9MrfgvD3fb9vFYQ9PbrZbjFCmRVhwJfqWZ7QjQ/S mYkSN9sNNRdXdpPD95w== X-Google-Smtp-Source: AGHT+IFa549WAC7/2Zp9TH9mHT9emec8EXGjR72hnwYKEZwIZ25eOt8v3XNuQSi0cp2BViD6aiA8OSHxVl/jLO8= X-Received: from wmqb14.prod.google.com ([2002:a05:600c:4e0e:b0:456:1a41:f922]) (user=aliceryhl job=prod-delivery.src-stubby-dispatcher) by 2002:a05:600c:3593:b0:458:6733:fb69 with SMTP id 5b1f17b1804b1-4587631d56bmr51203715e9.14.1753536220088; Sat, 26 Jul 2025 06:23:40 -0700 (PDT) Date: Sat, 26 Jul 2025 13:23:23 +0000 In-Reply-To: <20250726-maple-tree-v1-0-27a3da7cb8e5@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20250726-maple-tree-v1-0-27a3da7cb8e5@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=4561; i=aliceryhl@google.com; h=from:subject:message-id; bh=jbvUxSZMSHeAOtb+L6zXp20Ut43R/IhAlazvT1nIoks=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBohNbX9xMhZIlJ7rkwetRISa3iC5gQelXgC17we wNz5SyM+veJAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCaITW1wAKCRAEWL7uWMY5 RtQSD/9fnIIPodnb4V7IIC8dqWxmhAl1Zv62fgVPQaZH8+6jJ4Er1tViiWorbrQZKd8PhLYsI7w kITZA/5FirCmkjdSb7+f/ykUoj/gz/Svop7nwIrzKM+FYGGolvD4ewQScbJ7m2gn7hoTJ98FXiE s6FaJFL8tXS6BwdKEaxyBo+IK0N08muXCFvEtcs7OEKFd8j+AX9dPVeAMHP45dksiAwaMRhGkO7 QVvoK+s4E+/czByctOVFeh6TxbHnym1BAL0sA9SK5z+UzWxlns7l38ftBeWdA+Mz7u/OkAf632N JVDHVpJ3tv/xq7wa97vRJ9kT21KRBuB62EdvgCfoPA7iPwB5oPMDW0rAV/bYrTz9M7p03+egRBB B2a9MbPNh0sqlnBQTwQEAUb0+iQwTXBf7AzQDenfy4xn5pk8yaBrxKQa0DhAysOiFrB/v7PmZTk 4BIV59I+qbvoSv8bY64FrviEadvmn85BiLari+ikH5nBRbY1bzgcNjknOousTZKyEXn8dIIWtVp hNkuzn1/PQJ98y9F1O2VFQNlv6XubDrxpJdKcLB6LkUachb5cqqVPuzoIzovJXPr5xyFM/RABnF Ore52VsW4ws1Op+KYRmC0sbFNPEFqaLwk5Qw7yP5g3n3BiNGeMvj5Be4rJ3S18/LBA0vSQ3CRMO ifZxDBCwEkJksFQ== X-Mailer: b4 0.14.2 Message-ID: <20250726-maple-tree-v1-2-27a3da7cb8e5@google.com> Subject: [PATCH 2/3] rust: maple_tree: add MapleTree::lock() and load() 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. Co-developed-by: Andrew Ballance Signed-off-by: Andrew Ballance Signed-off-by: Alice Ryhl Reviewed-by: Andrew Ballance --- rust/kernel/maple_tree.rs | 94 +++++++++++++++++++++++++++++++++++++++++++= ++++ 1 file changed, 94 insertions(+) diff --git a/rust/kernel/maple_tree.rs b/rust/kernel/maple_tree.rs index 0f26c173eedc7c79bb8e2b56fe85e8a266b3ae0c..c7ef504a9c78065b3d5752b4f53= 37fb6277182d1 100644 --- a/rust/kernel/maple_tree.rs +++ b/rust/kernel/maple_tree.rs @@ -206,6 +206,23 @@ pub fn erase(&self, index: usize) -> Option { unsafe { T::try_from_foreign(ret) } } =20 + /// Lock the internal spinlock. + #[inline] + pub fn lock(&self) -> MapleLock<'_, 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. + MapleLock(self) + } + + #[inline] + fn ma_lock(&self) -> *mut bindings::spinlock_t { + // SAFETY: This pointer offset operation stays in-bounds. + let lock =3D unsafe { &raw mut (*self.tree.get()).__bindgen_anon_1= .ma_lock }; + lock.cast() + } + /// Free all `T` instances in this tree. /// /// # Safety @@ -248,6 +265,83 @@ 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. +pub struct MapleLock<'tree, T: ForeignOwnable>(&'tree MapleTree); + +impl<'tree, T: ForeignOwnable> Drop for MapleLock<'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> MapleLock<'tree, T> { + /// Load the value at the given index. + /// + /// # Examples + /// + /// Read the value while holding the spinlock. + /// + /// ``` + /// use kernel::maple_tree::{MapleTree, InsertErrorKind}; + /// + /// 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), Some(&mut 10)); + /// assert_eq!(lock.load(200), Some(&mut 20)); + /// assert_eq!(lock.load(300), None); + /// # Ok::<_, Error>(()) + /// ``` + /// + /// Increment refcount while holding spinlock and read afterwards. + /// + /// ``` + /// use kernel::maple_tree::{MapleTree, InsertErrorKind}; + /// 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 Arc::from(tree.lock().load(100).unwrap()); + /// + /// // 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, 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) }) + } +} + /// Error type for failure to insert a new value. pub struct InsertError { /// The value that could not be inserted. --=20 2.50.1.470.g6ba607880d-goog From nobody Mon Oct 6 01:21:08 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 0166E28688D for ; Sat, 26 Jul 2025 13:23:42 +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=1753536225; cv=none; b=cBRhG1f3jzQtHhYEH4FlDgM7Hu5Mys3SAYpjSwT9UeX9bKYjtWzwWEolv5R9T/ZMA47zvaVUq31ciOmrcREELCDV89FzDNa4s0uu8yVETK+jUY7Y5HL9icPUurg198FCP4lEFQ1JkSV3rm+AHoMYt8Q/t5/fiwD1xdyPWeBdLg8= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1753536225; c=relaxed/simple; bh=XDv7xqVzGr3tjiLDY2GZay8L0P/ScjmmwU5AHWOuiak=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=LGTetFd5YPfUS7QxkRwJHtN7otHNAGdo8MLj4Txd0NDh2W+iAqEdg2b7ZmIeqUF6SYwLBtHgX3AgXev++jD7LhgV09QYHFogFxKUKNijrWnwDdomuoJe4rZupur6Mpihji2NYWXB8nWnOdAiDFitg4kdbSePxI3pvBV5DNX7jBs= 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=kWBh80nv; 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="kWBh80nv" Received: by mail-wm1-f73.google.com with SMTP id 5b1f17b1804b1-45867ac308dso15229965e9.2 for ; Sat, 26 Jul 2025 06:23:42 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1753536221; x=1754141021; 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=kgwHbCr2ZvmYKCAvZ6Jo8foujNnaH3MRKvB5fhzEjBk=; b=kWBh80nvzE/Q2sFVpC/QNk4GdlfznGqhraCjw9Uc/LwPdL5M9UHflZKJiJb4/T1TWX QugZ47gB51ME1OhrJJXV+UarEav7cdEUPsEsGfYyP3Vj8CabwbjIk/zW7yC5UXQ3QE1t KHaxITjOqvHbvo3I0mRut3xpOOxOeQ8g5+gkOUVKFloKVtwb1BLymdz/iHI4rPWZu/ub UW5w4PtSKtrs6szGQgjpQNIaMQ/so4YAR2lSbZ8fQddMTX9jHlU+TDRO+o27GwoNZXz6 RPf1CZ/+WG5xPU/E1xmo953VX7argB8axBqYdVNrhEPUjDAJjGZ7yQxcDXWpRGmjcpwS rqWg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1753536221; x=1754141021; 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=kgwHbCr2ZvmYKCAvZ6Jo8foujNnaH3MRKvB5fhzEjBk=; b=l0dkbNe1GccFfRbInnq7krTLuw9ZNObnDpfV76xH2yyAw9JjtE7heb+w5V+OerzWjW 6Bkdydo/5s+uo2pBb4wNCsfoavTLvrXK0HQ9U7C5xnJz8GpiY2oDo6VgKyFr7Up+E88F kI6fCOiYPCyo/1XGXSK2p+HArgRMj9An/0rIPCtlpdlaBkuF8QrVcgigWtz+VD8jaAea Qmu3EWEBREElQFJiUGOrf2N47PVUWCdutmLBAFY0YJzcaHd/JWCGHX9K457BboKTnlF1 XlSu8VClRENI4bq9/8wVf1DFgLbLSiMW/rHvEbhc1A/3wXMD5Ru5iZYobRM9vQ5dSuG8 LJRw== X-Forwarded-Encrypted: i=1; AJvYcCVmt6hD7EjA13X0I1vKbIgnREX3LOeuTvm781vbKcaZiOi9tzHZ9vq4plLwVjAmOya/XKhHchLW0JI3E9Y=@vger.kernel.org X-Gm-Message-State: AOJu0YyXkMFWl2yJf1S5+8im7qUglLw5sa3Sp8SVJvvKftdY9WMTaLpz McnaVomRgUQMeIMZwpWzrm0h/Se2qrN1K8DEpC2aH0gZyVZFJeIXSjJm3tHp5+iuxHquulpzu0v KgUUN2bUCJWtOKTBJCA== X-Google-Smtp-Source: AGHT+IHK0oinGXcTRpIRR9GkmcUt0z0luOQdU/wKAKEP5Mdo9w8BMXUuDfOXSr1dZ2NTcmmdHQ/ztKHyo4udlFU= X-Received: from wmsd5.prod.google.com ([2002:a05:600c:3ac5:b0:456:134a:a210]) (user=aliceryhl job=prod-delivery.src-stubby-dispatcher) by 2002:a05:600c:548a:b0:450:d30e:ff96 with SMTP id 5b1f17b1804b1-4587631c069mr50085215e9.0.1753536221362; Sat, 26 Jul 2025 06:23:41 -0700 (PDT) Date: Sat, 26 Jul 2025 13:23:24 +0000 In-Reply-To: <20250726-maple-tree-v1-0-27a3da7cb8e5@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20250726-maple-tree-v1-0-27a3da7cb8e5@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=6486; i=aliceryhl@google.com; h=from:subject:message-id; bh=XDv7xqVzGr3tjiLDY2GZay8L0P/ScjmmwU5AHWOuiak=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBohNbXyRmF2zytMMMrm4rFmcdjquo0alEVhk3Vl CXdwtTdF7iJAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCaITW1wAKCRAEWL7uWMY5 RhWDD/9l1MeQpBGr+HV7JMdLIjd2i9o0iNLwnnm6xX7E0mrEmHWsUQ5bRH0W+p/8tudSkN9xG0o PTt0cR7RIw42ZpHN3ewphysCo5tvFzedmCj+Mxz6r64n7QQvm46pl3bksPmndh+E3pMGnNABAr+ 9nY3OJkCOCjZK9X0Fu/hRgntpDkqMfs2Ux9LkDUtAf125aDF931odgruaYhLUZD9Le6lyjeFC5R vydFnAf0zHh+03ZkMMM/SR0WKJmwN5NytueHgJa1A1qxgkefT6K37nVGklV/UvrE0E8ESoVbeqM xP1vbvwjUZcWtafW3oOzZTXAeslkFn0AEV8Hc9+HWWoO9esbZrL8KG6+zTsrIuXE2z2RtNbWr0r hM+ViSO2TX+ZbZXFIkxErX2QrpETKvcNp6VpWVoi2Cy7oTwoMvV+Yuhustg88E9k8BnEqTLzVWT HzuxHgOJHIPMP6J5pGq99NS7CA90Jz/S6LNabFVKICycYiWoFeYktvnmwSND0UAUvcmCCqSVnFM 3QUo53DympxOQ0nk48KweRmq31fKIabyZKncDdq2/nYJ8n1AHNCItDDgTt1XL0s0MgC0ohN2Ew5 AmBdjifFMO443CQjeqSsc1Cbu8e8D4lKI1T0JC7a6xloZHxBzpsjznPz+qada3iRteJq4rWPwAT NBEBElt7effAZPQ== X-Mailer: b4 0.14.2 Message-ID: <20250726-maple-tree-v1-3-27a3da7cb8e5@google.com> Subject: [PATCH 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 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. 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 c7ef504a9c78065b3d5752b4f5337fb6277182d1..8c025d2c395b6d57f1fb16214b4= e87d4e7942d6f 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() { @@ -342,6 +362,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::Nomem + } else if err =3D=3D EBUSY { + AllocErrorKind::Busy + } else { + AllocErrorKind::InvalidRequest + }; + Err(AllocError { value, cause }) + } else { + Ok(index) + } + } +} + /// Error type for failure to insert a new value. pub struct InsertError { /// The value that could not be inserted. @@ -378,3 +499,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. + Nomem, + /// The insertion request was invalid. + InvalidRequest, +} + +impl From for Error { + #[inline] + fn from(kind: AllocErrorKind) -> Error { + match kind { + AllocErrorKind::Busy =3D> EBUSY, + AllocErrorKind::Nomem =3D> ENOMEM, + AllocErrorKind::InvalidRequest =3D> EINVAL, + } + } +} + +impl From> for Error { + #[inline] + fn from(insert_err: AllocError) -> Error { + Error::from(insert_err.cause) + } +} --=20 2.50.1.470.g6ba607880d-goog