[PATCH v2 0/5] Add Rust abstraction for Maple Trees

[PATCH v2 0/5] Add Rust abstraction for Maple Trees

[Alice Ryhl]

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.

[1]: https://lore.kernel.org/r/20250627-tyr-v1-1-cb5f4c6ced46@collabora.com
[2]: https://lore.kernel.org/r/20250405060154.1550858-1-andrewjballance@gmail.com

Signed-off-by: Alice Ryhl <aliceryhl@google.com>
---
Changes in v2:
- Add MaState abstraction. For now it only has a mas_find method. And
  use it in the destructor.
- Duplicate MA_STATE macro in Rust instead of using a C helper.
- Change maple_tree.h so that cast in ma_lock() is no longer needed.
- Add #[must_use] and #[inline] annotations.
- Rename MapleLock to MapleGuard.
- Change errors to use AllocError.
- Add MAINTAINERS file.
- Link to v1: https://lore.kernel.org/r/20250726-maple-tree-v1-0-27a3da7cb8e5@google.com

---
Alice Ryhl (5):
      maple_tree: remove lockdep_map_p typedef
      rust: maple_tree: add MapleTree
      rust: maple_tree: add MapleTree::lock() and load()
      rust: maple_tree: add MapleTreeAlloc
      rust: maple_tree: add MAINTAINERS entry

 MAINTAINERS                |  12 +
 include/linux/maple_tree.h |  11 +-
 rust/helpers/helpers.c     |   1 +
 rust/helpers/maple_tree.c  |   8 +
 rust/kernel/lib.rs         |   1 +
 rust/kernel/maple_tree.rs  | 640 +++++++++++++++++++++++++++++++++++++++++++++
 6 files changed, 669 insertions(+), 4 deletions(-)
---
base-commit: 8f5ae30d69d7543eee0d70083daf4de8fe15d585
change-id: 20250726-maple-tree-1af0803ac524

Best regards,
-- 
Alice Ryhl <aliceryhl@google.com>

[PATCH v2 1/5] maple_tree: remove lockdep_map_p typedef

[Alice Ryhl]

Having the ma_external_lock field exist when CONFIG_LOCKDEP=n isn't used
anywhere, so just get rid of it. This also avoids generating a typedef
called lockdep_map_p that could overlap with typedefs in other header
files.

With this change, bindgen will generate better definitions for this
union, which makes it nicer to use from Rust. This avoids a cast in the
Rust abstractions for the maple tree, ensuring that Rust's type checker
will notice at build-time if ma_lock is changed from spinlock_t to
something else.

Signed-off-by: Alice Ryhl <aliceryhl@google.com>
---
 include/linux/maple_tree.h | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)

diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h
index bafe143b1f783202e27b32567fffee4149e8e266..8244679ba1758235e049acbaedee62aae5c0e226 100644
--- a/include/linux/maple_tree.h
+++ b/include/linux/maple_tree.h
@@ -194,7 +194,6 @@ enum store_type {
 #define MAPLE_RESERVED_RANGE	4096
 
 #ifdef CONFIG_LOCKDEP
-typedef struct lockdep_map *lockdep_map_p;
 #define mt_lock_is_held(mt)                                             \
 	(!(mt)->ma_external_lock || lock_is_held((mt)->ma_external_lock))
 
@@ -207,7 +206,6 @@ typedef struct lockdep_map *lockdep_map_p;
 
 #define mt_on_stack(mt)			(mt).ma_external_lock = NULL
 #else
-typedef struct { /* nothing */ } lockdep_map_p;
 #define mt_lock_is_held(mt)		1
 #define mt_write_lock_is_held(mt)	1
 #define mt_set_external_lock(mt, lock)	do { } while (0)
@@ -230,8 +228,10 @@ typedef struct { /* nothing */ } lockdep_map_p;
  */
 struct maple_tree {
 	union {
-		spinlock_t	ma_lock;
-		lockdep_map_p	ma_external_lock;
+		spinlock_t		ma_lock;
+#ifdef CONFIG_LOCKDEP
+		struct lockdep_map	*ma_external_lock;
+#endif
 	};
 	unsigned int	ma_flags;
 	void __rcu      *ma_root;

-- 
2.51.0.rc1.167.g924127e9c0-goog

[PATCH v2 2/5] rust: maple_tree: add MapleTree

[Alice Ryhl]

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 <andrewjballance@gmail.com>
Signed-off-by: Andrew Ballance <andrewjballance@gmail.com>
Signed-off-by: Alice Ryhl <aliceryhl@google.com>
---
 MAINTAINERS                |   2 +
 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  | 343 +++++++++++++++++++++++++++++++++++++++++++++
 6 files changed, 358 insertions(+)

diff --git a/MAINTAINERS b/MAINTAINERS
index fe168477caa45799dfe07de2f54de6d6a1ce0615..26053163fe5aed2fc4b4e39d47062c93b873ac13 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -16250,7 +16250,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/
 
diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h
index 8244679ba1758235e049acbaedee62aae5c0e226..4af6c5e1a6241e24e3e73b1cc1364b8da77b9bf0 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 7cf7fe95e41dd51717050648d6160bebebdf4b26..c5d42e0f7ce6786c1e96f8c0f27710959ca3362b 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..1dd9ac84a13feed53c0ed5eec6805517081d0673
--- /dev/null
+++ b/rust/helpers/maple_tree.c
@@ -0,0 +1,8 @@
+// SPDX-License-Identifier: GPL-2.0
+
+#include <linux/maple_tree.h>
+
+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..6b0a5689669fa691e366ab3f9d462692c12bd548 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..ea1bd694213b73108732aecc36da95342aeafe04
--- /dev/null
+++ b/rust/kernel/maple_tree.rs
@@ -0,0 +1,343 @@
+// SPDX-License-Identifier: GPL-2.0
+
+//! Maple trees.
+//!
+//! C header: [`include/linux/maple_tree.h`](srctree/include/linux/maple_tree.h)
+//!
+//! Reference: <https://docs.kernel.org/core-api/maple_tree.html>
+
+use core::{
+    marker::PhantomData,
+    ops::{Bound, RangeBounds},
+    ptr,
+};
+
+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<T: ForeignOwnable> {
+    #[pin]
+    tree: Opaque<bindings::maple_tree>,
+    _p: PhantomData<T>,
+}
+
+/// A helper type used for navigating a [`MapleTree`].
+///
+/// # Invariants
+///
+/// For the duration of `'tree`:
+///
+/// * The `ma_state` must reference a valid `MapleTree<T>`.
+/// * 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<T>>,
+}
+
+#[inline]
+fn to_maple_range(range: impl RangeBounds<usize>) -> 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<T: ForeignOwnable> MapleTree<T> {
+    /// Create a new maple tree.
+    ///
+    /// The tree will use the regular implementation with a higher branching factor.
+    #[inline]
+    pub fn new() -> impl PinInit<Self> {
+        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.
+    ///
+    /// 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 = KBox::pin_init(MapleTree::<KBox<i32>>::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<T>> {
+        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.
+    ///
+    /// # Examples
+    ///
+    /// ```
+    /// 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)?;
+    /// 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<R>(&self, range: R, value: T, gfp: Flags) -> Result<(), InsertError<T>>
+    where
+        R: RangeBounds<usize>,
+    {
+        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, 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_range(100..500, ten, GFP_KERNEL)?;
+    /// tree.insert(67, twenty, GFP_KERNEL)?;
+    ///
+    /// let twenty = tree.erase(67).unwrap();
+    /// assert_eq!(*twenty, 20);
+    ///
+    /// let ten = 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<T> {
+        // 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.
+    /// 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 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<T: ForeignOwnable> PinnedDrop for MapleTree<T> {
+    #[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::<T>() {
+            // 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()) };
+    }
+}
+
+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<T>, first: usize, end: usize) -> Self {
+        // INVARIANT:
+        // * Having a reference ensures that the `MapleTree<T>` 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<T> {
+    /// 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.
+    AllocError(kernel::alloc::AllocError),
+    /// The insertion request was invalid.
+    InvalidRequest,
+}
+
+impl From<InsertErrorKind> for Error {
+    #[inline]
+    fn from(kind: InsertErrorKind) -> Error {
+        match kind {
+            InsertErrorKind::Occupied => EEXIST,
+            InsertErrorKind::AllocError(kernel::alloc::AllocError) => ENOMEM,
+            InsertErrorKind::InvalidRequest => EINVAL,
+        }
+    }
+}
+
+impl<T> From<InsertError<T>> for Error {
+    #[inline]
+    fn from(insert_err: InsertError<T>) -> Error {
+        Error::from(insert_err.cause)
+    }
+}

-- 
2.51.0.rc1.167.g924127e9c0-goog

[PATCH v2 3/5] rust: maple_tree: add MapleTree::lock() and load()

[Alice Ryhl]

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

[PATCH v2 4/5] rust: maple_tree: add MapleTreeAlloc

[Alice Ryhl]

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 <aliceryhl@google.com>
---
 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 17e4d8586ebad56aee87a97befdfec5741f147de..1a32960e6e721ca32ca45d8bb63fcffedeae3424 100644
--- a/rust/kernel/maple_tree.rs
+++ b/rust/kernel/maple_tree.rs
@@ -33,6 +33,26 @@ pub struct MapleTree<T: ForeignOwnable> {
     _p: PhantomData<T>,
 }
 
+/// 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<T: ForeignOwnable> {
+    #[pin]
+    tree: MapleTree<T>,
+}
+
+// Make MapleTree methods usable on MapleTreeAlloc.
+impl<T: ForeignOwnable> core::ops::Deref for MapleTreeAlloc<T> {
+    type Target = MapleTree<T>;
+
+    #[inline]
+    fn deref(&self) -> &MapleTree<T> {
+        &self.tree
+    }
+}
+
 /// A helper type used for navigating a [`MapleTree`].
 ///
 /// # Invariants
@@ -364,6 +384,107 @@ pub fn load(&mut self, index: usize) -> Option<T::BorrowedMut<'_>> {
     }
 }
 
+impl<T: ForeignOwnable> MapleTreeAlloc<T> {
+    /// Create a new allocation tree.
+    pub fn new() -> impl PinInit<Self> {
+        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::<KBox<i32>>::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<R>(
+        &self,
+        size: usize,
+        value: T,
+        range: R,
+        gfp: Flags,
+    ) -> Result<usize, AllocError<T>>
+    where
+        R: RangeBounds<usize>,
+    {
+        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)
+        }
+    }
+}
+
 impl<'tree, T: ForeignOwnable> MaState<'tree, T> {
     /// Initialize a new `MaState` with the given tree.
     ///
@@ -480,3 +601,40 @@ fn from(insert_err: InsertError<T>) -> Error {
         Error::from(insert_err.cause)
     }
 }
+
+/// Error type for failure to insert a new value.
+pub struct AllocError<T> {
+    /// 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<AllocErrorKind> for Error {
+    #[inline]
+    fn from(kind: AllocErrorKind) -> Error {
+        match kind {
+            AllocErrorKind::Busy => EBUSY,
+            AllocErrorKind::AllocError(kernel::alloc::AllocError) => ENOMEM,
+            AllocErrorKind::InvalidRequest => EINVAL,
+        }
+    }
+}
+
+impl<T> From<AllocError<T>> for Error {
+    #[inline]
+    fn from(insert_err: AllocError<T>) -> Error {
+        Error::from(insert_err.cause)
+    }
+}

-- 
2.51.0.rc1.167.g924127e9c0-goog

[PATCH v2 5/5] rust: maple_tree: add MAINTAINERS entry

[Alice Ryhl]

Similar to and just below the existing MAPLE TREE entry.

Signed-off-by: Alice Ryhl <aliceryhl@google.com>
---
Liam: I'm not sure what you prefer for the MAINTAINERS entry, so let me
know if you want anything changed. There are also a few other options,
for example, I could just add the files under the existing MAPLE TREE
entry? The get_maintainers script should still send any relevant patches
my way because they also match the RUST entry that has a wildcard on the
rust/ directory.

Which tree does maple tree patches usually land through?

Andrew Ballance: You mentioned being interested in being listed here as
well?
---
 MAINTAINERS | 10 ++++++++++
 1 file changed, 10 insertions(+)

diff --git a/MAINTAINERS b/MAINTAINERS
index 26053163fe5aed2fc4b4e39d47062c93b873ac13..4a52d884e36eafe1c819227207123c51caf02ee5 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -14674,6 +14674,16 @@ F:	lib/test_maple_tree.c
 F:	tools/testing/radix-tree/maple.c
 F:	tools/testing/shared/linux/maple_tree.h
 
+MAPLE TREE [RUST]
+M:	Liam R. Howlett <Liam.Howlett@oracle.com>
+M:	Alice Ryhl <aliceryhl@google.com>
+L:	maple-tree@lists.infradead.org
+L:	linux-mm@kvack.org
+L:	rust-for-linux@vger.kernel.org
+S:	Supported
+F:	rust/helpers/maple_tree.c
+F:	rust/kernel/maple_tree.rs
+
 MARDUK (CREATOR CI40) DEVICE TREE SUPPORT
 M:	Rahul Bedarkar <rahulbedarkar89@gmail.com>
 L:	linux-mips@vger.kernel.org

-- 
2.51.0.rc1.167.g924127e9c0-goog

Re: [PATCH v2 1/5] maple_tree: remove lockdep_map_p typedef

[Danilo Krummrich]

On Tue Aug 19, 2025 at 12:34 PM CEST, Alice Ryhl wrote:
> Having the ma_external_lock field exist when CONFIG_LOCKDEP=n isn't used
> anywhere, so just get rid of it. This also avoids generating a typedef
> called lockdep_map_p that could overlap with typedefs in other header
> files.
>
> With this change, bindgen will generate better definitions for this
> union, which makes it nicer to use from Rust. This avoids a cast in the
> Rust abstractions for the maple tree, ensuring that Rust's type checker
> will notice at build-time if ma_lock is changed from spinlock_t to
> something else.
>
> Signed-off-by: Alice Ryhl <aliceryhl@google.com>

Reviewed-by: Danilo Krummrich <dakr@kernel.org>

Re: [PATCH v2 2/5] rust: maple_tree: add MapleTree

[Danilo Krummrich]

On Tue Aug 19, 2025 at 12:34 PM CEST, Alice Ryhl wrote:
> diff --git a/MAINTAINERS b/MAINTAINERS
> index fe168477caa45799dfe07de2f54de6d6a1ce0615..26053163fe5aed2fc4b4e39d47062c93b873ac13 100644
> --- a/MAINTAINERS
> +++ b/MAINTAINERS
> @@ -16250,7 +16250,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/

A later patch adds a separate entry; is this intended?

> diff --git a/rust/kernel/maple_tree.rs b/rust/kernel/maple_tree.rs
> new file mode 100644
> index 0000000000000000000000000000000000000000..ea1bd694213b73108732aecc36da95342aeafe04
> --- /dev/null
> +++ b/rust/kernel/maple_tree.rs
> @@ -0,0 +1,343 @@
> +// SPDX-License-Identifier: GPL-2.0
> +
> +//! Maple trees.
> +//!
> +//! C header: [`include/linux/maple_tree.h`](srctree/include/linux/maple_tree.h)
> +//!
> +//! Reference: <https://docs.kernel.org/core-api/maple_tree.html>
> +
> +use core::{
> +    marker::PhantomData,
> +    ops::{Bound, RangeBounds},
> +    ptr,
> +};
> +
> +use kernel::{
> +    alloc::Flags,
> +    error::code::{EEXIST, ENOMEM},

I think they're covered by prelude already.

> +    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<T: ForeignOwnable> {
> +    #[pin]
> +    tree: Opaque<bindings::maple_tree>,
> +    _p: PhantomData<T>,
> +}
> +
> +/// A helper type used for navigating a [`MapleTree`].
> +///
> +/// # Invariants
> +///
> +/// For the duration of `'tree`:
> +///
> +/// * The `ma_state` must reference a valid `MapleTree<T>`.

I'd say ""`ma_state` references a valid `MapleTree<T>`", other wise it sounds
like a requirement.

> +/// * 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<T>>,
> +}
> +
> +#[inline]
> +fn to_maple_range(range: impl RangeBounds<usize>) -> 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<T: ForeignOwnable> MapleTree<T> {
> +    /// Create a new maple tree.
> +    ///
> +    /// The tree will use the regular implementation with a higher branching factor.

What do you mean with "regular implementation" and what is "a higher branching
factor" in this context?

Do you mean that the maple tree has a higher branching factor than a regular RB
tree, or something else?

> +    #[inline]
> +    pub fn new() -> impl PinInit<Self> {
> +        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.
> +    ///
> +    /// If the maple tree already contains a range using the given index, then this call will fail.

Maybe add an error section for this?

> +    ///
> +    /// # Examples
> +    ///
> +    /// ```
> +    /// 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)?;
> +    /// 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,

A lot of the examples, including the ones in subsequent patches contain variants
of unwrap().

I think we should avoid this and instead handle errors gracefully -- even if it
bloats the examples a bit.

My concern is that it otherwise creates the impression that using unwrap() is a
reasonable thing to do.

Especially for people new to the kernel or Rust (or both) it might not be
obvious that unwrap() is equivalent to

	if (!ret)
		do_something();
	else
		panic();

or the fact that this is something we should only do as absolute last resort.

> +    ///     InsertErrorKind::Occupied,
> +    /// );
> +    /// # Ok::<_, Error>(())
> +    /// ```
> +    #[inline]
> +    pub fn insert(&self, index: usize, value: T, gfp: Flags) -> Result<(), InsertError<T>> {
> +        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.

Same as above to the "failing on overlap" part.

> +    /// # Examples
> +    ///
> +    /// ```
> +    /// 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)?;
> +    /// 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<R>(&self, range: R, value: T, gfp: Flags) -> Result<(), InsertError<T>>

Re: [PATCH v2 3/5] rust: maple_tree: add MapleTree::lock() and load()

[Danilo Krummrich]

On Tue Aug 19, 2025 at 12:34 PM CEST, Alice Ryhl wrote:
> 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>

Without the unwrap() calls in the examples,

Reviewed-by: Danilo Krummrich <dakr@kernel.org>

Re: [PATCH v2 4/5] rust: maple_tree: add MapleTreeAlloc

[Danilo Krummrich]

On Tue Aug 19, 2025 at 12:34 PM CEST, Alice Ryhl wrote:
> 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 <aliceryhl@google.com>

Without the unwrap() calls in the examples,

Reviewed-by: Danilo Krummrich <dakr@kernel.org>

Re: [PATCH v2 5/5] rust: maple_tree: add MAINTAINERS entry

[Danilo Krummrich]

On Tue Aug 19, 2025 at 12:34 PM CEST, Alice Ryhl wrote:
> Similar to and just below the existing MAPLE TREE entry.
>
> Signed-off-by: Alice Ryhl <aliceryhl@google.com>
> ---
> Liam: I'm not sure what you prefer for the MAINTAINERS entry, so let me
> know if you want anything changed. There are also a few other options,
> for example, I could just add the files under the existing MAPLE TREE
> entry? The get_maintainers script should still send any relevant patches
> my way because they also match the RUST entry that has a wildcard on the
> rust/ directory.

From v1 [1]:

	>> We should have another section for the maple tree, since it's not just
	>> used for mm.  Your stated plan is to use it for GPU allocations and the
	>> code doesn't live in mm/, wdyt?
	
	> Sure, I can add a new section if you prefer that.

Maple tree is already used outside of mm, e.g. for regmap stuff and I also use
it in nouveau. Hence, I read this as moving maple tree to e.g. lib/ adjusting
the existing entry.

I personally think that - of course unless the affected people prefer otherwise
- it is usually best to keep a single maintainers entry for the C and the Rust
code. Maybe Alice can simply be added to the existing maintainers entry?

What do you think?

[1] https://lore.kernel.org/all/aJW3L3SEVUl_AVvN@google.com/

> Which tree does maple tree patches usually land through?
>
> Andrew Ballance: You mentioned being interested in being listed here as
> well?
> ---
>  MAINTAINERS | 10 ++++++++++
>  1 file changed, 10 insertions(+)
>
> diff --git a/MAINTAINERS b/MAINTAINERS
> index 26053163fe5aed2fc4b4e39d47062c93b873ac13..4a52d884e36eafe1c819227207123c51caf02ee5 100644
> --- a/MAINTAINERS
> +++ b/MAINTAINERS
> @@ -14674,6 +14674,16 @@ F:	lib/test_maple_tree.c
>  F:	tools/testing/radix-tree/maple.c
>  F:	tools/testing/shared/linux/maple_tree.h
>  
> +MAPLE TREE [RUST]
> +M:	Liam R. Howlett <Liam.Howlett@oracle.com>
> +M:	Alice Ryhl <aliceryhl@google.com>
> +L:	maple-tree@lists.infradead.org
> +L:	linux-mm@kvack.org
> +L:	rust-for-linux@vger.kernel.org
> +S:	Supported
> +F:	rust/helpers/maple_tree.c
> +F:	rust/kernel/maple_tree.rs
> +
>  MARDUK (CREATOR CI40) DEVICE TREE SUPPORT
>  M:	Rahul Bedarkar <rahulbedarkar89@gmail.com>
>  L:	linux-mips@vger.kernel.org
>
> -- 
> 2.51.0.rc1.167.g924127e9c0-goog

Re: [PATCH v2 1/5] maple_tree: remove lockdep_map_p typedef

[Alice Ryhl]

On Tue, Aug 19, 2025 at 10:34:42AM +0000, Alice Ryhl wrote:
> Having the ma_external_lock field exist when CONFIG_LOCKDEP=n isn't used
> anywhere, so just get rid of it. This also avoids generating a typedef
> called lockdep_map_p that could overlap with typedefs in other header
> files.
> 
> With this change, bindgen will generate better definitions for this
> union, which makes it nicer to use from Rust. This avoids a cast in the
> Rust abstractions for the maple tree, ensuring that Rust's type checker
> will notice at build-time if ma_lock is changed from spinlock_t to
> something else.
> 
> Signed-off-by: Alice Ryhl <aliceryhl@google.com>

Ah ... this didn't work. There's still a configuration where I get the
error:

ERROR:root:error[E0308]: mismatched types
   --> ../rust/kernel/maple_tree.rs:256:18
    |
254 |     fn ma_lock(&self) -> *mut bindings::spinlock_t {
    |                          ------------------------- expected `*mut bindings::spinlock` because of return type
255 |         // SAFETY: This pointer offset operation stays in-bounds.
256 |         unsafe { &raw mut (*self.tree.get()).__bindgen_anon_1.ma_lock }
    |                  ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected `*mut spinlock`, found `*mut __BindgenUnionField<spinlock>`
    |                                                                               
    = note: expected raw pointer `*mut bindings::spinlock`
               found raw pointer `*mut bindings::__BindgenUnionField<bindings::spinlock>`

Alice

Re: [PATCH v2 2/5] rust: maple_tree: add MapleTree

[Alice Ryhl]

On Tue, Aug 19, 2025 at 01:30:30PM +0200, Danilo Krummrich wrote:
> On Tue Aug 19, 2025 at 12:34 PM CEST, Alice Ryhl wrote:
> > diff --git a/MAINTAINERS b/MAINTAINERS
> > index fe168477caa45799dfe07de2f54de6d6a1ce0615..26053163fe5aed2fc4b4e39d47062c93b873ac13 100644
> > --- a/MAINTAINERS
> > +++ b/MAINTAINERS
> > @@ -16250,7 +16250,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/
> 
> A later patch adds a separate entry; is this intended?

Ah, no, this isn't intended.

> > +impl<T: ForeignOwnable> MapleTree<T> {
> > +    /// Create a new maple tree.
> > +    ///
> > +    /// The tree will use the regular implementation with a higher branching factor.
> 
> What do you mean with "regular implementation" and what is "a higher branching
> factor" in this context?
> 
> Do you mean that the maple tree has a higher branching factor than a regular RB
> tree, or something else?

This is compared to the alloc variant of the maple tree from the last
patch in this series.

> > +    #[inline]
> > +    pub fn new() -> impl PinInit<Self> {
> > +        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.
> > +    ///
> > +    /// If the maple tree already contains a range using the given index, then this call will fail.
> 
> Maybe add an error section for this?
> 
> > +    ///
> > +    /// # Examples
> > +    ///
> > +    /// ```
> > +    /// 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)?;
> > +    /// 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,
> 
> A lot of the examples, including the ones in subsequent patches contain variants
> of unwrap().
> 
> I think we should avoid this and instead handle errors gracefully -- even if it
> bloats the examples a bit.
> 
> My concern is that it otherwise creates the impression that using unwrap() is a
> reasonable thing to do.
> 
> Especially for people new to the kernel or Rust (or both) it might not be
> obvious that unwrap() is equivalent to
> 
> 	if (!ret)
> 		do_something();
> 	else
> 		panic();
> 
> or the fact that this is something we should only do as absolute last resort.

How would you write it? The way you write it in normal code is an
if/else where you handle both cases, but that doesn't map nicely.

Alice

Re: [PATCH v2 5/5] rust: maple_tree: add MAINTAINERS entry

[Alice Ryhl]

On Tue, Aug 19, 2025 at 01:49:27PM +0200, Danilo Krummrich wrote:
> On Tue Aug 19, 2025 at 12:34 PM CEST, Alice Ryhl wrote:
> > Similar to and just below the existing MAPLE TREE entry.
> >
> > Signed-off-by: Alice Ryhl <aliceryhl@google.com>
> > ---
> > Liam: I'm not sure what you prefer for the MAINTAINERS entry, so let me
> > know if you want anything changed. There are also a few other options,
> > for example, I could just add the files under the existing MAPLE TREE
> > entry? The get_maintainers script should still send any relevant patches
> > my way because they also match the RUST entry that has a wildcard on the
> > rust/ directory.
> 
> From v1 [1]:
> 
> 	>> We should have another section for the maple tree, since it's not just
> 	>> used for mm.  Your stated plan is to use it for GPU allocations and the
> 	>> code doesn't live in mm/, wdyt?
> 	
> 	> Sure, I can add a new section if you prefer that.
> 
> Maple tree is already used outside of mm, e.g. for regmap stuff and I also use
> it in nouveau. Hence, I read this as moving maple tree to e.g. lib/ adjusting
> the existing entry.

It's already in lib/ ?

> I personally think that - of course unless the affected people prefer otherwise
> - it is usually best to keep a single maintainers entry for the C and the Rust
> code. Maybe Alice can simply be added to the existing maintainers entry?
> 
> What do you think?

That works for me too.

Alice

Re: [PATCH v2 2/5] rust: maple_tree: add MapleTree

[Danilo Krummrich]

On Tue Aug 19, 2025 at 2:45 PM CEST, Alice Ryhl wrote:
> On Tue, Aug 19, 2025 at 01:30:30PM +0200, Danilo Krummrich wrote:
>> On Tue Aug 19, 2025 at 12:34 PM CEST, Alice Ryhl wrote:
>> > diff --git a/MAINTAINERS b/MAINTAINERS
>> > index fe168477caa45799dfe07de2f54de6d6a1ce0615..26053163fe5aed2fc4b4e39d47062c93b873ac13 100644
>> > --- a/MAINTAINERS
>> > +++ b/MAINTAINERS
>> > @@ -16250,7 +16250,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/
>> 
>> A later patch adds a separate entry; is this intended?
>
> Ah, no, this isn't intended.
>
>> > +impl<T: ForeignOwnable> MapleTree<T> {
>> > +    /// Create a new maple tree.
>> > +    ///
>> > +    /// The tree will use the regular implementation with a higher branching factor.
>> 
>> What do you mean with "regular implementation" and what is "a higher branching
>> factor" in this context?
>> 
>> Do you mean that the maple tree has a higher branching factor than a regular RB
>> tree, or something else?
>
> This is compared to the alloc variant of the maple tree from the last
> patch in this series.

I think it'd be good to mention this. You could add the corresponding comment
and link when you introduce the type in the subsequent patch.

>> > +    #[inline]
>> > +    pub fn new() -> impl PinInit<Self> {
>> > +        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.
>> > +    ///
>> > +    /// If the maple tree already contains a range using the given index, then this call will fail.
>> 
>> Maybe add an error section for this?
>> 
>> > +    ///
>> > +    /// # Examples
>> > +    ///
>> > +    /// ```
>> > +    /// 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)?;
>> > +    /// 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,
>> 
>> A lot of the examples, including the ones in subsequent patches contain variants
>> of unwrap().
>> 
>> I think we should avoid this and instead handle errors gracefully -- even if it
>> bloats the examples a bit.
>> 
>> My concern is that it otherwise creates the impression that using unwrap() is a
>> reasonable thing to do.
>> 
>> Especially for people new to the kernel or Rust (or both) it might not be
>> obvious that unwrap() is equivalent to
>> 
>> 	if (!ret)
>> 		do_something();
>> 	else
>> 		panic();
>> 
>> or the fact that this is something we should only do as absolute last resort.
>
> How would you write it? The way you write it in normal code is an
> if/else where you handle both cases, but that doesn't map nicely.

I'd just

	assert!(tree.insert(100, the_answer, GFP_KERNEL).is_err());

and if you want to test that the error you'd expect is actually returned, I'd
suggest a regular kunit test, rather than a doc-test.

I think doc-tests should mostly illustrate idiomatic usage, especially now that
we have good and easily accessible kunit support.

I say "mostly" because I think tests to the degree of where they stay within
reasonable bounds of illustrating idiomatic usage are fine of course.

Re: [PATCH v2 5/5] rust: maple_tree: add MAINTAINERS entry

[Liam R. Howlett]

* Danilo Krummrich <dakr@kernel.org> [250819 07:49]:
> On Tue Aug 19, 2025 at 12:34 PM CEST, Alice Ryhl wrote:
> > Similar to and just below the existing MAPLE TREE entry.
> >
> > Signed-off-by: Alice Ryhl <aliceryhl@google.com>
> > ---
> > Liam: I'm not sure what you prefer for the MAINTAINERS entry, so let me
> > know if you want anything changed. There are also a few other options,
> > for example, I could just add the files under the existing MAPLE TREE
> > entry? The get_maintainers script should still send any relevant patches
> > my way because they also match the RUST entry that has a wildcard on the
> > rust/ directory.
> 
> From v1 [1]:
> 
> 	>> We should have another section for the maple tree, since it's not just
> 	>> used for mm.  Your stated plan is to use it for GPU allocations and the
> 	>> code doesn't live in mm/, wdyt?
> 	
> 	> Sure, I can add a new section if you prefer that.
> 
> Maple tree is already used outside of mm, e.g. for regmap stuff and I also use
> it in nouveau. Hence, I read this as moving maple tree to e.g. lib/ adjusting
> the existing entry.
> 
> I personally think that - of course unless the affected people prefer otherwise
> - it is usually best to keep a single maintainers entry for the C and the Rust
> code. Maybe Alice can simply be added to the existing maintainers entry?
> 
> What do you think?

I'm not sure what you mean by lib/ since the lib files are spread into
other entries by the looks of it?

I'm okay with the entry below or adjusting the existing one.

> 
> [1] https://lore.kernel.org/all/aJW3L3SEVUl_AVvN@google.com/
> 
> > Which tree does maple tree patches usually land through?
> >
> > Andrew Ballance: You mentioned being interested in being listed here as
> > well?
> > ---
> >  MAINTAINERS | 10 ++++++++++
> >  1 file changed, 10 insertions(+)
> >
> > diff --git a/MAINTAINERS b/MAINTAINERS
> > index 26053163fe5aed2fc4b4e39d47062c93b873ac13..4a52d884e36eafe1c819227207123c51caf02ee5 100644
> > --- a/MAINTAINERS
> > +++ b/MAINTAINERS
> > @@ -14674,6 +14674,16 @@ F:	lib/test_maple_tree.c
> >  F:	tools/testing/radix-tree/maple.c
> >  F:	tools/testing/shared/linux/maple_tree.h
> >  
> > +MAPLE TREE [RUST]
> > +M:	Liam R. Howlett <Liam.Howlett@oracle.com>
> > +M:	Alice Ryhl <aliceryhl@google.com>
> > +L:	maple-tree@lists.infradead.org
> > +L:	linux-mm@kvack.org
> > +L:	rust-for-linux@vger.kernel.org
> > +S:	Supported
> > +F:	rust/helpers/maple_tree.c
> > +F:	rust/kernel/maple_tree.rs
> > +
> >  MARDUK (CREATOR CI40) DEVICE TREE SUPPORT
> >  M:	Rahul Bedarkar <rahulbedarkar89@gmail.com>
> >  L:	linux-mips@vger.kernel.org
> >
> > -- 
> > 2.51.0.rc1.167.g924127e9c0-goog
> 
> 

Re: [PATCH v2 2/5] rust: maple_tree: add MapleTree

[Daniel Almeida]

Hi Alice,

A few minor nits below, but overall LGTM

> On 19 Aug 2025, at 07:34, Alice Ryhl <aliceryhl@google.com> wrote:
> 
> 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 <andrewjballance@gmail.com>
> Signed-off-by: Andrew Ballance <andrewjballance@gmail.com>
> Signed-off-by: Alice Ryhl <aliceryhl@google.com>
> ---
> MAINTAINERS                |   2 +
> 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  | 343 +++++++++++++++++++++++++++++++++++++++++++++
> 6 files changed, 358 insertions(+)
> 
> diff --git a/MAINTAINERS b/MAINTAINERS
> index fe168477caa45799dfe07de2f54de6d6a1ce0615..26053163fe5aed2fc4b4e39d47062c93b873ac13 100644
> --- a/MAINTAINERS
> +++ b/MAINTAINERS
> @@ -16250,7 +16250,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/
> 
> diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h
> index 8244679ba1758235e049acbaedee62aae5c0e226..4af6c5e1a6241e24e3e73b1cc1364b8da77b9bf0 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 7cf7fe95e41dd51717050648d6160bebebdf4b26..c5d42e0f7ce6786c1e96f8c0f27710959ca3362b 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..1dd9ac84a13feed53c0ed5eec6805517081d0673
> --- /dev/null
> +++ b/rust/helpers/maple_tree.c
> @@ -0,0 +1,8 @@
> +// SPDX-License-Identifier: GPL-2.0
> +
> +#include <linux/maple_tree.h>
> +
> +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..6b0a5689669fa691e366ab3f9d462692c12bd548 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..ea1bd694213b73108732aecc36da95342aeafe04
> --- /dev/null
> +++ b/rust/kernel/maple_tree.rs
> @@ -0,0 +1,343 @@
> +// SPDX-License-Identifier: GPL-2.0
> +
> +//! Maple trees.
> +//!
> +//! C header: [`include/linux/maple_tree.h`](srctree/include/linux/maple_tree.h)
> +//!
> +//! Reference: <https://docs.kernel.org/core-api/maple_tree.html>
> +
> +use core::{
> +    marker::PhantomData,
> +    ops::{Bound, RangeBounds},
> +    ptr,
> +};
> +
> +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<T: ForeignOwnable> {
> +    #[pin]
> +    tree: Opaque<bindings::maple_tree>,
> +    _p: PhantomData<T>,
> +}
> +
> +/// A helper type used for navigating a [`MapleTree`].
> +///
> +/// # Invariants
> +///
> +/// For the duration of `'tree`:
> +///
> +/// * The `ma_state` must reference a valid `MapleTree<T>`.
> +/// * 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<T>>,
> +}
> +
> +#[inline]
> +fn to_maple_range(range: impl RangeBounds<usize>) -> Option<(usize, usize)> {

nit: Do you plan to use this function more than once? That's because, IMHO,  we
should try to avoid tuples unless they're exceedingly clear.  It's much more
explicit to have this:

struct Range {
  begin: usize,
  end: usize,
}

vs having to manually do this:

let (begin, end) = to_maple_range(...);

By the way, the names here do not match the names you used to destructure the
the tuple later in the patch.


> +    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<T: ForeignOwnable> MapleTree<T> {
> +    /// Create a new maple tree.
> +    ///
> +    /// The tree will use the regular implementation with a higher branching factor.
> +    #[inline]
> +    pub fn new() -> impl PinInit<Self> {
> +        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.
> +    ///
> +    /// 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 = KBox::pin_init(MapleTree::<KBox<i32>>::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<T>> {
> +        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.
> +    ///
> +    /// # Examples
> +    ///
> +    /// ```
> +    /// 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)?;
> +    /// 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<R>(&self, range: R, value: T, gfp: Flags) -> Result<(), InsertError<T>>
> +    where
> +        R: RangeBounds<usize>,
> +    {
> +        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, 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_range(100..500, ten, GFP_KERNEL)?;
> +    /// tree.insert(67, twenty, GFP_KERNEL)?;
> +    ///
> +    /// let twenty = tree.erase(67).unwrap();
> +    /// assert_eq!(*twenty, 20);
> +    ///
> +    /// let ten = 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<T> {
> +        // 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.
> +    /// The caller must ensure that no reference that remains in the maple tree is used incorrectly
> +    /// after this call.

Perhaps mention that this can only be called by the destructor?

> +    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<T: ForeignOwnable> PinnedDrop for MapleTree<T> {
> +    #[inline]
> +    fn drop(mut self: Pin<&mut Self>) {
> +        // We only iterate the tree if the Rust value have a destructor.

has

> +        if core::mem::needs_drop::<T>() {
> +            // 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()) };
> +    }
> +}
> +
> +impl<'tree, T: ForeignOwnable> MaState<'tree, T> {

Could you please place the impl block next to the struct?

> +    /// 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<T>, first: usize, end: usize) -> Self {
> +        // INVARIANT:
> +        // * Having a reference ensures that the `MapleTree<T>` 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<T> {
> +    /// 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.
> +    AllocError(kernel::alloc::AllocError),
> +    /// The insertion request was invalid.
> +    InvalidRequest,
> +}
> +
> +impl From<InsertErrorKind> for Error {
> +    #[inline]
> +    fn from(kind: InsertErrorKind) -> Error {
> +        match kind {
> +            InsertErrorKind::Occupied => EEXIST,
> +            InsertErrorKind::AllocError(kernel::alloc::AllocError) => ENOMEM,
> +            InsertErrorKind::InvalidRequest => EINVAL,
> +        }
> +    }
> +}
> +
> +impl<T> From<InsertError<T>> for Error {
> +    #[inline]
> +    fn from(insert_err: InsertError<T>) -> Error {
> +        Error::from(insert_err.cause)
> +    }
> +}
> 
> -- 
> 2.51.0.rc1.167.g924127e9c0-goog
> 
> 

Re: [PATCH v2 3/5] rust: maple_tree: add MapleTree::lock() and load()

[Daniel Almeida]

Hi Alice,

Overall LGTM, a few comments below,

> On 19 Aug 2025, at 07:34, Alice Ryhl <aliceryhl@google.com> wrote:
> 
> 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.

This is not in the commit title.

> +    ///
> +    /// # 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<'_>> {

Should we drop the “mas” prefix here? I think that “find()” is fine.

> +        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
> 
> 

Re: [PATCH v2 3/5] rust: maple_tree: add MapleTree::lock() and load()

[Daniel Almeida]

Ah, something else,

[…]

>> +    /// 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.

This sentence can be improved.

Re: [PATCH v2 4/5] rust: maple_tree: add MapleTreeAlloc

[Daniel Almeida]

> On 19 Aug 2025, at 07:34, Alice Ryhl <aliceryhl@google.com> wrote:
> 
> 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 <aliceryhl@google.com>
> ---
> 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 17e4d8586ebad56aee87a97befdfec5741f147de..1a32960e6e721ca32ca45d8bb63fcffedeae3424 100644
> --- a/rust/kernel/maple_tree.rs
> +++ b/rust/kernel/maple_tree.rs
> @@ -33,6 +33,26 @@ pub struct MapleTree<T: ForeignOwnable> {
>     _p: PhantomData<T>,
> }
> 
> +/// 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<T: ForeignOwnable> {
> +    #[pin]
> +    tree: MapleTree<T>,
> +}
> +
> +// Make MapleTree methods usable on MapleTreeAlloc.
> +impl<T: ForeignOwnable> core::ops::Deref for MapleTreeAlloc<T> {
> +    type Target = MapleTree<T>;
> +
> +    #[inline]
> +    fn deref(&self) -> &MapleTree<T> {
> +        &self.tree
> +    }
> +}
> +
> /// A helper type used for navigating a [`MapleTree`].
> ///
> /// # Invariants
> @@ -364,6 +384,107 @@ pub fn load(&mut self, index: usize) -> Option<T::BorrowedMut<'_>> {
>     }
> }
> 
> +impl<T: ForeignOwnable> MapleTreeAlloc<T> {
> +    /// Create a new allocation tree.
> +    pub fn new() -> impl PinInit<Self> {
> +        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::<KBox<i32>>::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<R>(
> +        &self,
> +        size: usize,
> +        value: T,
> +        range: R,
> +        gfp: Flags,
> +    ) -> Result<usize, AllocError<T>>
> +    where
> +        R: RangeBounds<usize>,
> +    {
> +        let Some((min, max)) = to_maple_range(range) else {

Ok, I see that the returned range can mean multiple things, depending on
context. Fine, you can disregard my previous comment about this function.

> +            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)
> +        }
> +    }
> +}
> +
> impl<'tree, T: ForeignOwnable> MaState<'tree, T> {
>     /// Initialize a new `MaState` with the given tree.
>     ///
> @@ -480,3 +601,40 @@ fn from(insert_err: InsertError<T>) -> Error {
>         Error::from(insert_err.cause)
>     }
> }
> +
> +/// Error type for failure to insert a new value.
> +pub struct AllocError<T> {
> +    /// 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<AllocErrorKind> for Error {
> +    #[inline]
> +    fn from(kind: AllocErrorKind) -> Error {
> +        match kind {
> +            AllocErrorKind::Busy => EBUSY,
> +            AllocErrorKind::AllocError(kernel::alloc::AllocError) => ENOMEM,
> +            AllocErrorKind::InvalidRequest => EINVAL,
> +        }
> +    }
> +}
> +
> +impl<T> From<AllocError<T>> for Error {
> +    #[inline]
> +    fn from(insert_err: AllocError<T>) -> Error {
> +        Error::from(insert_err.cause)
> +    }
> +}
> 
> -- 
> 2.51.0.rc1.167.g924127e9c0-goog
> 
> 

Reviewed-by: Daniel Almeida <daniel.almeida@collabora.com>

Re: [PATCH v2 5/5] rust: maple_tree: add MAINTAINERS entry

[Danilo Krummrich]

On Tue Aug 19, 2025 at 3:36 PM CEST, Liam R. Howlett wrote:
> * Danilo Krummrich <dakr@kernel.org> [250819 07:49]:
>> On Tue Aug 19, 2025 at 12:34 PM CEST, Alice Ryhl wrote:
>> > Similar to and just below the existing MAPLE TREE entry.
>> >
>> > Signed-off-by: Alice Ryhl <aliceryhl@google.com>
>> > ---
>> > Liam: I'm not sure what you prefer for the MAINTAINERS entry, so let me
>> > know if you want anything changed. There are also a few other options,
>> > for example, I could just add the files under the existing MAPLE TREE
>> > entry? The get_maintainers script should still send any relevant patches
>> > my way because they also match the RUST entry that has a wildcard on the
>> > rust/ directory.
>> 
>> From v1 [1]:
>> 
>> 	>> We should have another section for the maple tree, since it's not just
>> 	>> used for mm.  Your stated plan is to use it for GPU allocations and the
>> 	>> code doesn't live in mm/, wdyt?
>> 	
>> 	> Sure, I can add a new section if you prefer that.
>> 
>> Maple tree is already used outside of mm, e.g. for regmap stuff and I also use
>> it in nouveau. Hence, I read this as moving maple tree to e.g. lib/ adjusting
>> the existing entry.
>> 
>> I personally think that - of course unless the affected people prefer otherwise
>> - it is usually best to keep a single maintainers entry for the C and the Rust
>> code. Maybe Alice can simply be added to the existing maintainers entry?
>> 
>> What do you think?
>
> I'm not sure what you mean by lib/ since the lib files are spread into
> other entries by the looks of it?

I think I misunderstood your comment from [1] above, and, despite knowing
better, mistakenly assumed otherwise -- just ignore this comment.

> I'm okay with the entry below or adjusting the existing one.

If you're both fine with either, I suggest to keep a single entry for both.

In general I think it's better if we try to avoid to differentiate between Rust
and C code of a single subsystem (or component) maintenance wise unless there
are specific reasons.

Even though sometimes it's just a formality, I think it can help to bring people
together and learn from each other. There more good examples we can set up for
this, the better. :)

>> [1] https://lore.kernel.org/all/aJW3L3SEVUl_AVvN@google.com/

Re: [PATCH v2 5/5] rust: maple_tree: add MAINTAINERS entry

[Andrew Ballance]

On 8/19/25 5:34 AM, Alice Ryhl wrote:
> Similar to and just below the existing MAPLE TREE entry.
> 
> Signed-off-by: Alice Ryhl <aliceryhl@google.com>
> ---
> Liam: I'm not sure what you prefer for the MAINTAINERS entry, so let me
> know if you want anything changed. There are also a few other options,
> for example, I could just add the files under the existing MAPLE TREE
> entry? The get_maintainers script should still send any relevant patches
> my way because they also match the RUST entry that has a wildcard on the
> rust/ directory.
> 
> Which tree does maple tree patches usually land through?
> 
> Andrew Ballance: You mentioned being interested in being listed here as
> well?

Yes, please add me as a maintainer.

In regards to the discussion about the maintainers entry,
personally I would prefer that the entries for the rust and
c were separate, just like the version in this patch.

> ---
>   MAINTAINERS | 10 ++++++++++
>   1 file changed, 10 insertions(+)
> 
> diff --git a/MAINTAINERS b/MAINTAINERS
> index 26053163fe5aed2fc4b4e39d47062c93b873ac13..4a52d884e36eafe1c819227207123c51caf02ee5 100644
> --- a/MAINTAINERS
> +++ b/MAINTAINERS
> @@ -14674,6 +14674,16 @@ F:	lib/test_maple_tree.c
>   F:	tools/testing/radix-tree/maple.c
>   F:	tools/testing/shared/linux/maple_tree.h
>   
> +MAPLE TREE [RUST]
> +M:	Liam R. Howlett <Liam.Howlett@oracle.com>
> +M:	Alice Ryhl <aliceryhl@google.com>
> +L:	maple-tree@lists.infradead.org
> +L:	linux-mm@kvack.org
> +L:	rust-for-linux@vger.kernel.org
> +S:	Supported
> +F:	rust/helpers/maple_tree.c
> +F:	rust/kernel/maple_tree.rs
> +
>   MARDUK (CREATOR CI40) DEVICE TREE SUPPORT
>   M:	Rahul Bedarkar <rahulbedarkar89@gmail.com>
>   L:	linux-mips@vger.kernel.org
> 

Best Regards,
Andrew Ballance

Re: [PATCH v2 2/5] rust: maple_tree: add MapleTree

[Miguel Ojeda]

On Tue, Aug 19, 2025 at 2:58 PM Danilo Krummrich <dakr@kernel.org> wrote:
>
> I'd just
>
>         assert!(tree.insert(100, the_answer, GFP_KERNEL).is_err());
>
> and if you want to test that the error you'd expect is actually returned, I'd
> suggest a regular kunit test, rather than a doc-test.
>
> I think doc-tests should mostly illustrate idiomatic usage, especially now that
> we have good and easily accessible kunit support.
>
> I say "mostly" because I think tests to the degree of where they stay within
> reasonable bounds of illustrating idiomatic usage are fine of course.

I agree that we should try to show idiomatic code as much as possible.
At the same time, sometimes it is instructive to show in an example
where a concrete error would be returned (if the error is documented,
i.e. not an implementation detail).

So I think that, as long as it is clear the call/line is "broken" on
purpose (i.e. as long as it is clear it is not real code) -- for
instance because it is within an `assert!` and/or has a comment to
that effect -- then it should be fine and that allows us to have those
instructive lines too.

So, as a rule of thumb, probably we don't want to show `unwrap()`s in
examples if the code could have been written "properly" instead, but
`unwrap_err()`s (i.e. error ones) within an `assert!` are likely fine
if the example would be better with it.

Cheers,
Miguel

Re: [PATCH v2 2/5] rust: maple_tree: add MapleTree

[Danilo Krummrich]

On Fri Aug 22, 2025 at 3:40 AM CEST, Miguel Ojeda wrote:
> So, as a rule of thumb, probably we don't want to show `unwrap()`s in
> examples if the code could have been written "properly" instead

I think we never want to use unwrap(). Even in cases where we relly want to
panic the kernel (because we reached a point where otherwise it is impossible
to prevent undefined behavior) we should make the panic() explicit.

I see it fairly often in reviews that an unwrap() sneaked its way into the code
for things that can easily be handled gracefully, such as simple range checks,
etc.

We should probably check if we can get a clippy warning in place for this.

> , but
> `unwrap_err()`s (i.e. error ones) within an `assert!` are likely fine
> if the example would be better with it.

I agree, for obvious reasons unwrap_err() is much less of a concern.

Yet, it might be read as a pointer in the wrong direction, i.e. read as "unwraps
are OK".

If we want to check for a specific error type (or cause) in doc-tests I think we
should just use is_err_and() instead.

For instance, instead of

	assert_eq!(
	    tree.insert(100, the_answer, GFP_KERNEL).unwrap_err().cause,
	    InsertErrorKind::Occupied,
	);

we could also write

	assert!(tree
	    .insert(100, the_answer, GFP_KERNEL)
	    .is_err_and(|e| e.cause == InsertErrorKind::Occupied));

which is exactly the pattern also shown in the example of is_err_and() [1] and
entirely avoid any unwrap() calls.

[1] https://doc.rust-lang.org/std/result/enum.Result.html#method.is_err_and

Re: [PATCH v2 2/5] rust: maple_tree: add MapleTree

[Miguel Ojeda]

On Fri, Aug 22, 2025 at 1:05 PM Danilo Krummrich <dakr@kernel.org> wrote:
>
> We should probably check if we can get a clippy warning in place for this.

There is https://rust-lang.github.io/rust-clippy/master/index.html#unwrap_used,
which covers all cases.

> we could also write
>
>         assert!(tree
>             .insert(100, the_answer, GFP_KERNEL)
>             .is_err_and(|e| e.cause == InsertErrorKind::Occupied));

If we want to use the Clippy lint, i.e. go hard on avoiding all kinds
of `unwrap()`s, then that is fine.

But I wouldn't do it just for the sake of avoiding a few
`unwrap_err()`s within `assert!`s -- I don't think there is going to
be a problem of having a lot of people concluding it is OK to panic
the kernel in general just because they see an `unwrap_err()` within
an `assert!` -- the `assert!` itself could be also understood as
panicking, after all, and we really don't want to ban `assert!`s on
examples.

Now, if we do get something else out of it, like enforcing no
`unwrap()`s (still bypassable with `allow` etc. if needed) and thus
removing a class of errors, then that sounds worthier to me.

Thanks!

Cheers,
Miguel

Re: [PATCH v2 2/5] rust: maple_tree: add MapleTree

[Danilo Krummrich]

On Fri Aug 22, 2025 at 1:26 PM CEST, Miguel Ojeda wrote:
> On Fri, Aug 22, 2025 at 1:05 PM Danilo Krummrich <dakr@kernel.org> wrote:
>>
>> We should probably check if we can get a clippy warning in place for this.
>
> There is https://rust-lang.github.io/rust-clippy/master/index.html#unwrap_used,
> which covers all cases.

Great! I think there's a lot of value in getting this enabled.

>> we could also write
>>
>>         assert!(tree
>>             .insert(100, the_answer, GFP_KERNEL)
>>             .is_err_and(|e| e.cause == InsertErrorKind::Occupied));
>
> If we want to use the Clippy lint, i.e. go hard on avoiding all kinds
> of `unwrap()`s, then that is fine.
>
> But I wouldn't do it just for the sake of avoiding a few
> `unwrap_err()`s within `assert!`s

Why not? I mean, the above is cleaner and more idiomatic with or without the
lint enabled. As mentioned, it's even the showcase that has been picked for the
documentation of Result::is_err_and().

> I don't think there is going to
> be a problem of having a lot of people concluding it is OK to panic
> the kernel in general just because they see an `unwrap_err()` within
> an `assert!` -- the `assert!` itself could be also understood as
> panicking, after all, and we really don't want to ban `assert!`s on
> examples.

I didn't mean to say that people conclude it's OK to panic the kernel.

But especially people new to the kernel starting to write Rust drivers may not
even be aware of this fact. If they see some unwrap_err() calls in examples they
might not even thing about it a lot before starting to use them, e.g. because
they're used to it from userspace projects anyways.

> Now, if we do get something else out of it, like enforcing no
> `unwrap()`s (still bypassable with `allow` etc. if needed) and thus
> removing a class of errors, then that sounds worthier to me.

I think we should do this; I really think otherwise we gonna see a lot of them
once we get more drivers. It's just too convinient. :)

Re: [PATCH v2 3/5] rust: maple_tree: add MapleTree::lock() and load()

[Liam R. Howlett]

* Daniel Almeida <daniel.almeida@collabora.com> [250819 13:08]:
> Hi Alice,
> 
> Overall LGTM, a few comments below,
> 
> > On 19 Aug 2025, at 07:34, Alice Ryhl <aliceryhl@google.com> wrote:
> > 
> > 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.
> 
> This is not in the commit title.
> 
> > +    ///
> > +    /// # 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<'_>> {
> 
> Should we drop the “mas” prefix here? I think that “find()” is fine.

The maple tree has two interfaces, the advanced one which starts with
mas_ and the simple on that uses mt_.  This is probably why the mas_ is
here?

> 
> > +        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
> > 
> > 
> 

Re: [PATCH v2 3/5] rust: maple_tree: add MapleTree::lock() and load()

[Daniel Almeida]

Hi Liam,

[…]

>> 
>>> +    ///
>>> +    /// # 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<'_>> {
>> 
>> Should we drop the “mas” prefix here? I think that “find()” is fine.
> 
> The maple tree has two interfaces, the advanced one which starts with
> mas_ and the simple on that uses mt_.  This is probably why the mas_ is
> here?
> 

Yeah but we should probably not expose this nomenclature directly in Rust, or
at least not in the function name itself. Perhaps we can implement the mt_* API
as a separate type, with its own find() function?

— Daniel

Re: [PATCH v2 2/5] rust: maple_tree: add MapleTree

[Miguel Ojeda]

On Fri, Aug 22, 2025 at 1:44 PM Danilo Krummrich <dakr@kernel.org> wrote:
>
> Why not? I mean, the above is cleaner and more idiomatic with or without the
> lint enabled. As mentioned, it's even the showcase that has been picked for the
> documentation of Result::is_err_and().

Is it idiomatic, though? The example you mention comes from the method
itself, which is of course the obvious use case for the method, but it
doesn't imply other ways are now not idiomatic anymore or that people
have stopped using `assert_eq!` or `unwrap_err()`.

It has just been 2 years in Rust, after all. And, from a quick grep in
the Rust repo, it doesn't seem they have migrated what they had to the
new one in that time.

Also, do we expect to use that method in normal code, and not just
within asserts? We haven't used it yet

As for being clearer, what we want to assert is that the cause is a
given one, so `assert_eq!` seems like a natural choice (and it isn't a
case like `is_none()` where there is an advantage). Plus it means it
is able to show both sides if it fails. So it is not a clear win-win
in my eyes.

> But especially people new to the kernel starting to write Rust drivers may not
> even be aware of this fact. If they see some unwrap_err() calls in examples they
> might not even thing about it a lot before starting to use them, e.g. because
> they're used to it from userspace projects anyways.

We still have the issue that they will see the `assert!` anyway and
thus can easily think panics are OK. I understand what you are saying:
you want to minimize those cases anyway.

> I think we should do this; I really think otherwise we gonna see a lot of them
> once we get more drivers. It's just too convinient. :)

A potential middle ground is to apply the lint in normal code, but not
in examples.

Or, even better, we can actually only allow it within `assert!`s,
since it is a custom macro I wrote for KUnit and not the real one,
i.e. enforcing what I suggested above [1].

Another one is a lint that just affects `unwrap()` and not
`unwrap_err()` -- I think the Clippy one doesn't allow it now, but we
could request it. It could be combined with the above so that only
`unwrap_err()` is allowed within `assert!`s.

We could also go the C way, warning in `checkpatch.pl` about it like
it does `BUG_ON`.

What I like about the Clippy approach is that it can be locally `expect`ed.

Cheers,
Miguel

[1]

diff --git a/rust/kernel/kunit.rs b/rust/kernel/kunit.rs
index 41efd87595d6..86ea37319f7b 100644
--- a/rust/kernel/kunit.rs
+++ b/rust/kernel/kunit.rs
@@ -160,6 +160,7 @@ unsafe impl Sync for UnaryAssert {}
 #[macro_export]
 macro_rules! kunit_assert_eq {
     ($name:literal, $file:literal, $diff:expr, $left:expr,
$right:expr $(,)?) => {{
+        #![allow(clippy::unwrap_used)]
         // For the moment, we just forward to the expression assert
because, for binary asserts,
         // KUnit supports only a few types (e.g. integers).
         $crate::kunit_assert!($name, $file, $diff, $left == $right);

Re: [PATCH v2 2/5] rust: maple_tree: add MapleTree

[Danilo Krummrich]

On Fri Aug 22, 2025 at 11:22 PM CEST, Miguel Ojeda wrote:
> As for being clearer, what we want to assert is that the cause is a
> given one, so `assert_eq!` seems like a natural choice (and it isn't a
> case like `is_none()` where there is an advantage). Plus it means it
> is able to show both sides if it fails. So it is not a clear win-win
> in my eyes.

As for

	assert_eq!(foo().unwrap_err().kind(), ErrorKind::NotFound);

vs.

	assert!(foo().is_err_and(|e| x.kind() == ErrorKind::NotFound));

the only thing I can think of is that the former fails differently for when
foo() is Ok() vs. the error kind does not match. I assume that's what you mean?

If so, I agree it's indeed a downside.

>> But especially people new to the kernel starting to write Rust drivers may not
>> even be aware of this fact. If they see some unwrap_err() calls in examples they
>> might not even thing about it a lot before starting to use them, e.g. because
>> they're used to it from userspace projects anyways.
>
> We still have the issue that they will see the `assert!` anyway and
> thus can easily think panics are OK. I understand what you are saying:
> you want to minimize those cases anyway.

Yeah, exactly. Another reason I'm less concernt about the assert!() is that I
think it's generally more more associated with test cases than unwrap(). But
this one might also be just my perception. :)

>> I think we should do this; I really think otherwise we gonna see a lot of them
>> once we get more drivers. It's just too convinient. :)
>
> A potential middle ground is to apply the lint in normal code, but not
> in examples.
>
> Or, even better, we can actually only allow it within `assert!`s,
> since it is a custom macro I wrote for KUnit and not the real one,
> i.e. enforcing what I suggested above [1].

I think this would be a great solution; thanks for pointing this out.

> Another one is a lint that just affects `unwrap()` and not
> `unwrap_err()` -- I think the Clippy one doesn't allow it now, but we
> could request it. It could be combined with the above so that only
> `unwrap_err()` is allowed within `assert!`s.
>
> We could also go the C way, warning in `checkpatch.pl` about it like
> it does `BUG_ON`.

I think your suggestion above is perfect, whereas I think this one is likely to
still slip through.

> What I like about the Clippy approach is that it can be locally `expect`ed.

Agreed!

Re: [PATCH v2 2/5] rust: maple_tree: add MapleTree

[Miguel Ojeda]

On Fri, Aug 22, 2025 at 11:49 PM Danilo Krummrich <dakr@kernel.org> wrote:
>
> As for
>
>         assert_eq!(foo().unwrap_err().kind(), ErrorKind::NotFound);
>
> vs.
>
>         assert!(foo().is_err_and(|e| x.kind() == ErrorKind::NotFound));
>
> the only thing I can think of is that the former fails differently for when
> foo() is Ok() vs. the error kind does not match. I assume that's what you mean?
>
> If so, I agree it's indeed a downside.

Yeah, the former checks independently the not-`Ok` part; plus we could
make `assert_eq!` print the actual values when it is the error code
part that fails like the real one.

Cheers,
Miguel

Re: [PATCH v2 5/5] rust: maple_tree: add MAINTAINERS entry

[Alice Ryhl]

On Tue, Aug 19, 2025 at 09:36:10AM -0400, Liam R. Howlett wrote:
> * Danilo Krummrich <dakr@kernel.org> [250819 07:49]:
> > On Tue Aug 19, 2025 at 12:34 PM CEST, Alice Ryhl wrote:
> > > Similar to and just below the existing MAPLE TREE entry.
> > >
> > > Signed-off-by: Alice Ryhl <aliceryhl@google.com>
> > > ---
> > > Liam: I'm not sure what you prefer for the MAINTAINERS entry, so let me
> > > know if you want anything changed. There are also a few other options,
> > > for example, I could just add the files under the existing MAPLE TREE
> > > entry? The get_maintainers script should still send any relevant patches
> > > my way because they also match the RUST entry that has a wildcard on the
> > > rust/ directory.
> > 
> > From v1 [1]:
> > 
> > 	>> We should have another section for the maple tree, since it's not just
> > 	>> used for mm.  Your stated plan is to use it for GPU allocations and the
> > 	>> code doesn't live in mm/, wdyt?
> > 	
> > 	> Sure, I can add a new section if you prefer that.
> > 
> > Maple tree is already used outside of mm, e.g. for regmap stuff and I also use
> > it in nouveau. Hence, I read this as moving maple tree to e.g. lib/ adjusting
> > the existing entry.
> > 
> > I personally think that - of course unless the affected people prefer otherwise
> > - it is usually best to keep a single maintainers entry for the C and the Rust
> > code. Maybe Alice can simply be added to the existing maintainers entry?
> > 
> > What do you think?
> 
> I'm not sure what you mean by lib/ since the lib files are spread into
> other entries by the looks of it?
> 
> I'm okay with the entry below or adjusting the existing one.

In that case, I suggest we do this:

 MAPLE TREE
 M:	Liam R. Howlett <Liam.Howlett@oracle.com>
+R:	Alice Ryhl <aliceryhl@google.com>
+R:	Andrew Ballance <andrewjballance@gmail.com>
 L:	maple-tree@lists.infradead.org
 L:	linux-mm@kvack.org
 S:	Supported
 F:	Documentation/core-api/maple_tree.rst
 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

Optionally we could add (RUST) similar to the LOCKING PRIMITIVES
maintainers entry.

Thoughts?

Alice