[PATCH v3 1/3] rust: maple_tree: add MapleTree

[Danilo Krummrich]

On Tue Sep 2, 2025 at 10:35 AM CEST, Alice Ryhl wrote:
> The maple tree will be used in the Tyr driver to allocate and keep track
> of GPU allocations created internally (i.e. not by userspace). It will
> likely also be used in the Nova driver eventually.
>
> This adds the simplest methods for additional and removal that do not
> require any special care with respect to concurrency.
>
> This implementation is based on the RFC by Andrew but with significant
> changes to simplify the implementation.
>
> Co-developed-by: Andrew Ballance <andrewjballance at gmail.com>
> Signed-off-by: Andrew Ballance <andrewjballance at gmail.com>
> Signed-off-by: Alice Ryhl <aliceryhl at google.com>

One nit below, otherwise:

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

> +    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(())
> +        }
> +    }

	// SAFETY: The tree is valid, and we are passing a pointer to an owned instance of `T`.
	to_result(unsafe {
	    bindings::mtree_insert_range(self.tree.get(), first, last, ptr, gfp.as_raw())
	}).map_err(|err| {
	    // 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 })
	})

I think that's a bit cleaner than the above (not compile tested).