From: Alice Ryhl <aliceryhl@google.com>
To: Andrew Morton <akpm@linux-foundation.org>,
"Liam R. Howlett" <Liam.Howlett@oracle.com>,
Lorenzo Stoakes <lorenzo.stoakes@oracle.com>,
Miguel Ojeda <ojeda@kernel.org>,
Andrew Ballance <andrewjballance@gmail.com>
Cc: "Boqun Feng" <boqun.feng@gmail.com>,
"Gary Guo" <gary@garyguo.net>,
"Björn Roy Baron" <bjorn3_gh@protonmail.com>,
"Benno Lossin" <lossin@kernel.org>,
"Andreas Hindborg" <a.hindborg@kernel.org>,
"Trevor Gross" <tmgross@umich.edu>,
"Danilo Krummrich" <dakr@kernel.org>,
linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org,
rust-for-linux@vger.kernel.org, linux-mm@kvack.org,
"Alice Ryhl" <aliceryhl@google.com>
Subject: [PATCH v2 3/5] rust: maple_tree: add MapleTree::lock() and load()
Date: Tue, 19 Aug 2025 10:34:44 +0000 [thread overview]
Message-ID: <20250819-maple-tree-v2-3-229b48657bab@google.com> (raw)
In-Reply-To: <20250819-maple-tree-v2-0-229b48657bab@google.com>
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.
Co-developed-by: Andrew Ballance <andrewjballance@gmail.com>
Signed-off-by: Andrew Ballance <andrewjballance@gmail.com>
Reviewed-by: Andrew Ballance <andrewjballance@gmail.com>
Signed-off-by: Alice Ryhl <aliceryhl@google.com>
---
rust/kernel/maple_tree.rs | 139 ++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 139 insertions(+)
diff --git a/rust/kernel/maple_tree.rs b/rust/kernel/maple_tree.rs
index ea1bd694213b73108732aecc36da95342aeafe04..17e4d8586ebad56aee87a97befdfec5741f147de 100644
--- a/rust/kernel/maple_tree.rs
+++ b/rust/kernel/maple_tree.rs
@@ -220,6 +220,22 @@ pub fn erase(&self, index: usize) -> Option<T> {
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.
+ unsafe { &raw mut (*self.tree.get()).__bindgen_anon_1.ma_lock }
+ }
+
/// Free all `T` instances in this tree.
///
/// # Safety
@@ -263,6 +279,91 @@ fn drop(mut self: Pin<&mut Self>) {
}
}
+/// 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<T>);
+
+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, InsertErrorKind};
+ ///
+ /// let tree = KBox::pin_init(MapleTree::<KBox<i32>>::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), 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 = KBox::pin_init(MapleTree::<Arc<i32>>::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 = 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<T::BorrowedMut<'_>> {
+ // 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) })
+ }
+}
+
impl<'tree, T: ForeignOwnable> MaState<'tree, T> {
/// Initialize a new `MaState` with the given tree.
///
@@ -303,6 +404,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, InsertErrorKind};
+ /// use kernel::sync::Arc;
+ ///
+ /// let tree = KBox::pin_init(MapleTree::<Arc<i32>>::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.mas_find(usize::MAX).unwrap(), 10);
+ /// assert_eq!(*iter.mas_find(usize::MAX).unwrap(), 20);
+ /// assert!(iter.mas_find(usize::MAX).is_none());
+ /// # Ok::<_, Error>(())
+ /// ```
+ #[inline]
+ pub fn mas_find(&mut self, max: usize) -> Option<T::BorrowedMut<'_>> {
+ 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.
--
2.51.0.rc1.167.g924127e9c0-goog
next prev parent reply other threads:[~2025-08-19 10:34 UTC|newest]
Thread overview: 32+ messages / expand[flat|nested] mbox.gz Atom feed top
2025-08-19 10:34 [PATCH v2 0/5] Add Rust abstraction for Maple Trees Alice Ryhl
2025-08-19 10:34 ` [PATCH v2 1/5] maple_tree: remove lockdep_map_p typedef Alice Ryhl
2025-08-19 10:49 ` Danilo Krummrich
2025-08-19 12:41 ` Alice Ryhl
2025-08-19 10:34 ` [PATCH v2 2/5] rust: maple_tree: add MapleTree Alice Ryhl
2025-08-19 11:30 ` Danilo Krummrich
2025-08-19 12:45 ` Alice Ryhl
2025-08-19 12:58 ` Danilo Krummrich
2025-08-22 1:40 ` Miguel Ojeda
2025-08-22 11:05 ` Danilo Krummrich
2025-08-22 11:26 ` Miguel Ojeda
2025-08-22 11:44 ` Danilo Krummrich
2025-08-22 21:22 ` Miguel Ojeda
2025-08-22 21:49 ` Danilo Krummrich
2025-08-24 12:00 ` Miguel Ojeda
2025-08-19 16:34 ` Daniel Almeida
2025-08-19 10:34 ` Alice Ryhl [this message]
2025-08-19 11:36 ` [PATCH v2 3/5] rust: maple_tree: add MapleTree::lock() and load() Danilo Krummrich
2025-08-19 17:07 ` Daniel Almeida
2025-08-19 17:22 ` Daniel Almeida
2025-08-22 15:31 ` Liam R. Howlett
2025-08-22 15:43 ` Daniel Almeida
2025-08-19 10:34 ` [PATCH v2 4/5] rust: maple_tree: add MapleTreeAlloc Alice Ryhl
2025-08-19 11:38 ` Danilo Krummrich
2025-08-19 17:26 ` Daniel Almeida
2025-08-19 10:34 ` [PATCH v2 5/5] rust: maple_tree: add MAINTAINERS entry Alice Ryhl
2025-08-19 11:49 ` Danilo Krummrich
2025-08-19 12:47 ` Alice Ryhl
2025-08-19 13:36 ` Liam R. Howlett
2025-08-19 17:53 ` Danilo Krummrich
2025-08-25 12:30 ` Alice Ryhl
2025-08-19 20:53 ` Andrew Ballance
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20250819-maple-tree-v2-3-229b48657bab@google.com \
--to=aliceryhl@google.com \
--cc=Liam.Howlett@oracle.com \
--cc=a.hindborg@kernel.org \
--cc=akpm@linux-foundation.org \
--cc=andrewjballance@gmail.com \
--cc=bjorn3_gh@protonmail.com \
--cc=boqun.feng@gmail.com \
--cc=dakr@kernel.org \
--cc=gary@garyguo.net \
--cc=linux-kernel@vger.kernel.org \
--cc=linux-mm@kvack.org \
--cc=lorenzo.stoakes@oracle.com \
--cc=lossin@kernel.org \
--cc=maple-tree@lists.infradead.org \
--cc=ojeda@kernel.org \
--cc=rust-for-linux@vger.kernel.org \
--cc=tmgross@umich.edu \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).