Skip to contentSkip to conversation

Add Rust abstraction for Maple Trees

PATCH Superseded Alice Ryhl 6 participants 32 messages Aug 19, 2025 – Aug 25, 2025

Subsystems (4)

v2 of 3 Superseded Latest is v3 →

lore
Share & tools
lore

Alice Ryhl

author reviewer
#0 lore raw

v2 cover Add Rust abstraction for Maple Trees

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/[email protected]
[2]: https://lore.kernel.org/r/[email protected]

---
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/[email protected]

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

Signature · 1 line
Alice Ryhl <[email protected]>
author reviewer
#1 lore raw

PATCH v2 1/5 maple_tree: remove lockdep_map_p typedef

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.

---
 include/linux/maple_tree.h | 8 ++++----
 1 file changed, 4 insertions(+), 4 deletions(-)
include/linux/maple_tree.h +4 -4
index bafe143b1f783202e27b32567fffee4149e8e266..8244679ba1758235e049acbaedee62aae5c0e226 100644
@@ -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;
Signature · 1 line
2.51.0.rc1.167.g924127e9c0-goog
reviewer Reviewed-by on v2 1/5
#2 lore raw

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

Quoted 5 lines · 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.

Quoted 7 lines

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.

author reviewer
#3 lore raw

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

In reply to Alice Ryhl
Quoted 5 lines · 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.

Quoted 7 lines

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.

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

author reviewer
#4 lore raw

PATCH v2 2/5 rust: maple_tree: add MapleTree

In reply to 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.

---
 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(+)
MAINTAINERS +2 -0
index fe168477caa45799dfe07de2f54de6d6a1ce0615..26053163fe5aed2fc4b4e39d47062c93b873ac13 100644
@@ -16250,7 +16250,9 @@ L:	[email protected]
 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/
 
include/linux/maple_tree.h +3 -0
index 8244679ba1758235e049acbaedee62aae5c0e226..4af6c5e1a6241e24e3e73b1cc1364b8da77b9bf0 100644
@@ -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,						\
rust/helpers/helpers.c +1 -0
index 7cf7fe95e41dd51717050648d6160bebebdf4b26..c5d42e0f7ce6786c1e96f8c0f27710959ca3362b 100644
@@ -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"
rust/helpers/maple_tree.c new file +8 -0
new file mode 100644
index 0000000000000000000000000000000000000000..1dd9ac84a13feed53c0ed5eec6805517081d0673
@@ -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);
+}
rust/kernel/lib.rs +1 -0
index ed53169e795c0badf548025a57f946fa18bc73e3..6b0a5689669fa691e366ab3f9d462692c12bd548 100644
@@ -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)]
rust/kernel/maple_tree.rs new file +343 -0

343 lines not on this page · raw message

Signature · 1 line
2.51.0.rc1.167.g924127e9c0-goog
#5 lore raw

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

MAINTAINERS L: [email protected] · line 16257

Quoted 13 lines · Alice Ryhl
MAINTAINERS +2 -0
index fe168477caa45799dfe07de2f54de6d6a1ce0615..26053163fe5aed2fc4b4e39d47062c93b873ac13 100644
@@ -16250,7 +16250,9 @@ L:	[email protected]
 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?

Quoted 13 lines
rust/kernel/maple_tree.rs new file +7 -0
new file mode 100644
index 0000000000000000000000000000000000000000..ea1bd694213b73108732aecc36da95342aeafe04
@@ -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>

rust/kernel/maple_tree.rs line 17

Quoted 10 lines
rust/kernel/maple_tree.rs new file +10 -0
+
+use core::{
+    marker::PhantomData,
+    ops::{Bound, RangeBounds},
+    ptr,
+};
+
+use kernel::{
+    alloc::Flags,
+    error::code::{EEXIST, ENOMEM},

I think they're covered by prelude already.

Quoted 15 lines
rust/kernel/maple_tree.rs new file +15 -0
+    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>,

rust/kernel/maple_tree.rs line 42

Quoted 10 lines
rust/kernel/maple_tree.rs new file +10 -0
+    _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.

Quoted 21 lines
rust/kernel/maple_tree.rs new file +21 -0
+/// * 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 {

rust/kernel/maple_tree.rs line 73

Quoted 10 lines
rust/kernel/maple_tree.rs new file +10 -0
+        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?

rust/kernel/maple_tree.rs line 86

Quoted 13 lines
rust/kernel/maple_tree.rs new file +13 -0
+    #[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?

Quoted 9 lines
rust/kernel/maple_tree.rs new file +9 -0
+    ///
+    /// # 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)?;

rust/kernel/maple_tree.rs line 105

Quoted 10 lines
rust/kernel/maple_tree.rs new file +10 -0
+    /// 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.

Quoted 4 lines
rust/kernel/maple_tree.rs new file +4 -0
+    ///     InsertErrorKind::Occupied,
+    /// );
+    /// # Ok::<_, Error>(())
+    /// ```

rust/kernel/maple_tree.rs line 119

Quoted 10 lines
rust/kernel/maple_tree.rs new file +10 -0
+    #[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.

Quoted 33 lines
rust/kernel/maple_tree.rs new file +33 -0
+    /// # 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>>
author reviewer
#6 lore raw

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

Quoted 16 lines · Danilo Krummrich

MAINTAINERS L: [email protected] · line 16257

Quoted 13 lines · Alice Ryhl
MAINTAINERS +2 -0
index fe168477caa45799dfe07de2f54de6d6a1ce0615..26053163fe5aed2fc4b4e39d47062c93b873ac13 100644
@@ -16250,7 +16250,9 @@ L:	[email protected]
 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.

Quoted 10 lines

MAINTAINERS L: [email protected]

Quoted 4 lines
MAINTAINERS +4 -0
+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.

Quoted 48 lines

MAINTAINERS

Quoted 13 lines
MAINTAINERS +13 -0
+    #[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?

Quoted 9 lines
MAINTAINERS +9 -0
+    ///
+    /// # 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)?;

MAINTAINERS

Quoted 10 lines
MAINTAINERS +10 -0
+    /// 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

Quoted 6 lines
	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

#7 lore raw

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

Quoted 25 lines · Alice Ryhl
Quoted 16 lines · Danilo Krummrich

MAINTAINERS L: [email protected] · line 16257

Quoted 13 lines · Alice Ryhl
MAINTAINERS +2 -0
index fe168477caa45799dfe07de2f54de6d6a1ce0615..26053163fe5aed2fc4b4e39d47062c93b873ac13 100644
@@ -16250,7 +16250,9 @@ L:	[email protected]
 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.

Quoted 5 lines
Quoted 4 lines
MAINTAINERS +4 -0
+impl<T: ForeignOwnable> MapleTree<T> {
+    /// Create a new maple tree.
+    ///
+    /// The tree will use the regular implementation with a higher branching factor.
Quoted 8 lines
Quoted 5 lines

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.

Quoted 53 lines
Quoted 53 lines

MAINTAINERS

Quoted 13 lines
MAINTAINERS +13 -0
+    #[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?

Quoted 9 lines
MAINTAINERS +9 -0
+    ///
+    /// # 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)?;

MAINTAINERS

Quoted 10 lines
MAINTAINERS +10 -0
+    /// 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();
Quoted 4 lines
Quoted 1 line

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.

#8 lore raw

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

Quoted 5 lines · Danilo Krummrich

I'd just

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

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

#9 lore raw

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

Quoted 2 lines · Miguel Ojeda

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.

Quoted 3 lines

, 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

#10 lore raw

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

Quoted 2 lines · Danilo Krummrich

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.

Quoted 5 lines

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

#11 lore raw

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

Quoted 6 lines · Miguel Ojeda
Quoted 2 lines · Danilo Krummrich

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.

Quoted 11 lines
Quoted 5 lines

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().

Quoted 6 lines

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.

Quoted 3 lines

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. :)

#12 lore raw

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

Quoted 4 lines · Danilo Krummrich

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.

Quoted 4 lines

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.

Quoted 2 lines

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 expected.

Cheers,
Miguel

[1]

rust/kernel/kunit.rs +0 -0
index 41efd87595d6..86ea37319f7b 100644
@@ -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);
#13 lore raw

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

Quoted 5 lines · Miguel Ojeda

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.

Quoted 8 lines
Quoted 4 lines

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. :)

Quoted 9 lines
Quoted 2 lines

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.

Quoted 7 lines

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.

Quoted 1 line

What I like about the Clippy approach is that it can be locally expected.

Agreed!

#14 lore raw

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

Quoted 5 lines · Danilo Krummrich

As for

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

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

#15 lore raw

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

In reply to Alice Ryhl

Hi Alice,

A few minor nits below, but overall LGTM

Quoted 136 lines · 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.

---

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(+)
MAINTAINERS +0 -0
index fe168477caa45799dfe07de2f54de6d6a1ce0615..26053163fe5aed2fc4b4e39d47062c93b873ac13 100644
@@ -16250,7 +16250,9 @@ L: [email protected]

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/

include/linux/maple_tree.h +3 -0
index 8244679ba1758235e049acbaedee62aae5c0e226..4af6c5e1a6241e24e3e73b1cc1364b8da77b9bf0 100644
@@ -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, \
rust/helpers/helpers.c +1 -0
index 7cf7fe95e41dd51717050648d6160bebebdf4b26..c5d42e0f7ce6786c1e96f8c0f27710959ca3362b 100644
@@ -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"
rust/helpers/maple_tree.c new file +8 -0
new file mode 100644
index 0000000000000000000000000000000000000000..1dd9ac84a13feed53c0ed5eec6805517081d0673
@@ -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);
+}
rust/kernel/lib.rs +1 -0
index ed53169e795c0badf548025a57f946fa18bc73e3..6b0a5689669fa691e366ab3f9d462692c12bd548 100644
@@ -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)]
rust/kernel/maple_tree.rs new file +40 -0
new file mode 100644
index 0000000000000000000000000000000000000000..ea1bd694213b73108732aecc36da95342aeafe04
@@ -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`:

rust/kernel/maple_tree.rs line 50

Quoted 10 lines
rust/kernel/maple_tree.rs new file +10 -0
+///
+/// * 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.

Quoted 169 lines
rust/kernel/maple_tree.rs new file +169 -0
+    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.

rust/kernel/maple_tree.rs line 229

Quoted 10 lines
rust/kernel/maple_tree.rs new file +10 -0
+        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?

Quoted 15 lines
rust/kernel/maple_tree.rs new file +15 -0
+    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.

rust/kernel/maple_tree.rs line 254

Quoted 10 lines
rust/kernel/maple_tree.rs new file +10 -0
+            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

rust/kernel/maple_tree.rs line 266

Quoted 12 lines
rust/kernel/maple_tree.rs new file +12 -0
+        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?

Quoted 82 lines
rust/kernel/maple_tree.rs new file +77 -0
+    /// 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)
+    }
+}
Signature · 2 lines
-- 
2.51.0.rc1.167.g924127e9c0-goog
author reviewer
#16 lore raw

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

In reply to 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.

---
 rust/kernel/maple_tree.rs | 139 ++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 139 insertions(+)
rust/kernel/maple_tree.rs +139 -0
index ea1bd694213b73108732aecc36da95342aeafe04..17e4d8586ebad56aee87a97befdfec5741f147de 100644
@@ -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.
Signature · 1 line
2.51.0.rc1.167.g924127e9c0-goog
reviewer Reviewed-by on v2 3/5
#17 lore raw

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

Quoted 9 lines · 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.

Quoted 4 lines

Without the unwrap() calls in the examples,

#18 lore raw

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

In reply to Alice Ryhl

Hi Alice,

Overall LGTM, a few comments below,

Quoted 139 lines · 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.

---
rust/kernel/maple_tree.rs | 139 ++++++++++++++++++++++++++++++++++++++++++++++

1 file changed, 139 insertions(+)
rust/kernel/maple_tree.rs +101 -0
index ea1bd694213b73108732aecc36da95342aeafe04..17e4d8586ebad56aee87a97befdfec5741f147de 100644
@@ -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.
    ///

rust/kernel/maple_tree.rs fn mas_find_raw(&mut self, max: usize) -> *mut c_void { · line 408

Quoted 5 lines
rust/kernel/maple_tree.rs +2 -0
@@ -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.

Quoted 16 lines
rust/kernel/maple_tree.rs +16 -0
+    ///
+    /// # 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)?;
+    ///

rust/kernel/maple_tree.rs fn mas_find_raw(&mut self, max: usize) -> *mut c_void { · line 434

Quoted 10 lines
rust/kernel/maple_tree.rs +10 -0
+    /// 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.

Quoted 18 lines
rust/kernel/maple_tree.rs +10 -0
+        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.
Signature · 2 lines
-- 
2.51.0.rc1.167.g924127e9c0-goog
#19 lore raw

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

Ah, something else,

[…]

Quoted 16 lines
Quoted 16 lines
rust/kernel/maple_tree.rs +16 -0
+    /// 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)?;
+    ///
Quoted 8 lines

rust/kernel/maple_tree.rs fn drop(mut self: Pin<&mut Self>) { · line 329

Quoted 8 lines
rust/kernel/maple_tree.rs +8 -0
+    /// 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.

#20 lore raw

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

In reply to Daniel Almeida
Quoted 178 lines · Daniel Almeida

Hi Alice,

Overall LGTM, a few comments below,

Quoted 139 lines · 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.

---
rust/kernel/maple_tree.rs | 139 ++++++++++++++++++++++++++++++++++++++++++++++

1 file changed, 139 insertions(+)
rust/kernel/maple_tree.rs +101 -0
index ea1bd694213b73108732aecc36da95342aeafe04..17e4d8586ebad56aee87a97befdfec5741f147de 100644
@@ -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.
    ///

rust/kernel/maple_tree.rs fn mas_find_raw(&mut self, max: usize) -> *mut c_void { · line 408

Quoted 5 lines
rust/kernel/maple_tree.rs +2 -0
@@ -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.

Quoted 16 lines
rust/kernel/maple_tree.rs +16 -0
+    ///
+    /// # 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)?;
+    ///

rust/kernel/maple_tree.rs fn mas_find_raw(&mut self, max: usize) -> *mut c_void { · line 434

Quoted 10 lines
rust/kernel/maple_tree.rs +10 -0
+    /// 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<'_>> {
Quoted 1 line

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?

Quoted 20 lines
Quoted 19 lines
rust/kernel/maple_tree.rs +10 -0
+        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.
Signature · 2 lines
-- 
2.51.0.rc1.167.g924127e9c0-goog
#21 lore raw

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

Hi Liam,

[…]

Quoted 28 lines
Quoted 28 lines
Quoted 27 lines
rust/kernel/maple_tree.rs +26 -0
+    ///
+    /// # 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<'_>> {
Quoted 6 lines
Quoted 1 line

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

author reviewer
#22 lore raw

PATCH v2 4/5 rust: maple_tree: add MapleTreeAlloc

In reply to 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.

---
 rust/kernel/maple_tree.rs | 158 ++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 158 insertions(+)
rust/kernel/maple_tree.rs +158 -0
index 17e4d8586ebad56aee87a97befdfec5741f147de..1a32960e6e721ca32ca45d8bb63fcffedeae3424 100644
@@ -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)
+    }
+}
Signature · 1 line
2.51.0.rc1.167.g924127e9c0-goog
reviewer Reviewed-by on v2 4/5
#23 lore raw

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

Quoted 8 lines · 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.

Without the unwrap() calls in the examples,

reviewer Reviewed-by on v2 4/5
#24 lore raw

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

In reply to Alice Ryhl
Quoted 102 lines · 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.

---
rust/kernel/maple_tree.rs | 158 ++++++++++++++++++++++++++++++++++++++++++++++

1 file changed, 158 insertions(+)
rust/kernel/maple_tree.rs +71 -0
index 17e4d8586ebad56aee87a97befdfec5741f147de..1a32960e6e721ca32ca45d8bb63fcffedeae3424 100644
@@ -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>(

rust/kernel/maple_tree.rs pub fn load(&mut self, index: usize) -> Option<T::BorrowedMut<'_>> { · line 447

Quoted 10 lines
rust/kernel/maple_tree.rs +10 -0
+        &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.

Quoted 89 lines
rust/kernel/maple_tree.rs +77 -0
+            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)
+    }
+}
Signature · 2 lines
-- 
2.51.0.rc1.167.g924127e9c0-goog
author reviewer
#25 lore raw

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

In reply to Alice Ryhl

Similar to and just below the existing MAPLE TREE entry.

---
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(+)
MAINTAINERS +10 -0
index 26053163fe5aed2fc4b4e39d47062c93b873ac13..4a52d884e36eafe1c819227207123c51caf02ee5 100644
@@ -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 <[email protected]>
+M:	Alice Ryhl <[email protected]>
+L:	[email protected]
+L:	[email protected]
+L:	[email protected]
+S:	Supported
+F:	rust/helpers/maple_tree.c
+F:	rust/kernel/maple_tree.rs
+
 MARDUK (CREATOR CI40) DEVICE TREE SUPPORT
 M:	Rahul Bedarkar <[email protected]>
 L:	[email protected]
Signature · 1 line
2.51.0.rc1.167.g924127e9c0-goog
#26 lore raw

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

Quoted 10 lines · Alice Ryhl

Similar to and just below the existing MAPLE TREE entry.

---
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/[email protected]/

Quoted 32 lines

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(+)
MAINTAINERS +10 -0
index 26053163fe5aed2fc4b4e39d47062c93b873ac13..4a52d884e36eafe1c819227207123c51caf02ee5 100644
@@ -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 <[email protected]>
+M:	Alice Ryhl <[email protected]>
+L:	[email protected]
+L:	[email protected]
+L:	[email protected]
+S:	Supported
+F:	rust/helpers/maple_tree.c
+F:	rust/kernel/maple_tree.rs
+
 MARDUK (CREATOR CI40) DEVICE TREE SUPPORT
 M:	Rahul Bedarkar <[email protected]>
 L:	[email protected]
Signature · 2 lines
-- 
2.51.0.rc1.167.g924127e9c0-goog
author reviewer
#27 lore raw

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

Quoted 18 lines · Danilo Krummrich
Quoted 10 lines · Alice Ryhl

Similar to and just below the existing MAPLE TREE entry.

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

Quoted 5 lines

> 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/ ?

Quoted 5 lines

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

#28 lore raw

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

In reply to Danilo Krummrich
Quoted 24 lines · Danilo Krummrich
Quoted 10 lines · Alice Ryhl

Similar to and just below the existing MAPLE TREE entry.

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

Quoted 5 lines

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.

Quoted 37 lines

[1] https://lore.kernel.org/all/[email protected]/

Quoted 32 lines

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(+)
MAINTAINERS +10 -0
index 26053163fe5aed2fc4b4e39d47062c93b873ac13..4a52d884e36eafe1c819227207123c51caf02ee5 100644
@@ -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 <[email protected]>
+M:	Alice Ryhl <[email protected]>
+L:	[email protected]
+L:	[email protected]
+L:	[email protected]
+S:	Supported
+F:	rust/helpers/maple_tree.c
+F:	rust/kernel/maple_tree.rs
+
 MARDUK (CREATOR CI40) DEVICE TREE SUPPORT
 M:	Rahul Bedarkar <[email protected]>
 L:	[email protected]
Signature · 2 lines
-- 
2.51.0.rc1.167.g924127e9c0-goog
#29 lore raw

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

Quoted 25 lines · Liam R. Howlett
Quoted 24 lines · Danilo Krummrich
Quoted 10 lines · Alice Ryhl

Similar to and just below the existing MAPLE TREE entry.

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

Quoted 8 lines
Quoted 5 lines

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.

Quoted 1 line

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. :)

Quoted 1 line
Quoted 1 line

[1] https://lore.kernel.org/all/[email protected]/

author reviewer
#30 lore raw

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

In reply to Liam R. Howlett
Quoted 29 lines · Liam R. Howlett
Quoted 28 lines · Danilo Krummrich
Quoted 10 lines · Alice Ryhl

Similar to and just below the existing MAPLE TREE entry.

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

Quoted 6 lines
Quoted 1 line

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 <[email protected]>
+R: Alice Ryhl <[email protected]>
+R: Andrew Ballance <[email protected]>
L: [email protected]
L: [email protected]
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

#31 lore raw

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

In reply to Alice Ryhl
Quoted 11 lines · Alice Ryhl

Similar to and just below the existing MAPLE TREE entry.

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

Quoted 4 lines

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.

Quoted 16 lines
---
  MAINTAINERS | 10 ++++++++++
  1 file changed, 10 insertions(+)
MAINTAINERS +3 -0
index 26053163fe5aed2fc4b4e39d47062c93b873ac13..4a52d884e36eafe1c819227207123c51caf02ee5 100644
@@ -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 <[email protected]>
+M:	Alice Ryhl <[email protected]>

MAINTAINERS F: lib/test_maple_tree.c · line 14689

Quoted 10 lines
MAINTAINERS +7 -0
+L:	[email protected]
+L:	[email protected]
+L:	[email protected]
+S:	Supported
+F:	rust/helpers/maple_tree.c
+F:	rust/kernel/maple_tree.rs
+
  MARDUK (CREATOR CI40) DEVICE TREE SUPPORT
  M:	Rahul Bedarkar <[email protected]>
  L:	[email protected]

Best Regards,
Andrew Ballance