From patchwork Sat Apr 5 06:01:54 2025 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Andrew Ballance X-Patchwork-Id: 14039085 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by smtp.lore.kernel.org (Postfix) with ESMTP id 3411EC36010 for ; Sat, 5 Apr 2025 06:03:44 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 666916B000D; Sat, 5 Apr 2025 02:03:43 -0400 (EDT) Received: by kanga.kvack.org (Postfix, from userid 40) id 6158D6B000E; Sat, 5 Apr 2025 02:03:43 -0400 (EDT) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 469246B0010; Sat, 5 Apr 2025 02:03:43 -0400 (EDT) X-Delivered-To: linux-mm@kvack.org Received: from relay.hostedemail.com (smtprelay0010.hostedemail.com [216.40.44.10]) by kanga.kvack.org (Postfix) with ESMTP id 23E9B6B000D for ; Sat, 5 Apr 2025 02:03:43 -0400 (EDT) Received: from smtpin08.hostedemail.com (a10.router.float.18 [10.200.18.1]) by unirelay01.hostedemail.com (Postfix) with ESMTP id EA5751CC8FD for ; Sat, 5 Apr 2025 06:03:42 +0000 (UTC) X-FDA: 83298948684.08.41FFAAA Received: from mail-oi1-f175.google.com (mail-oi1-f175.google.com [209.85.167.175]) by imf10.hostedemail.com (Postfix) with ESMTP id 0CAFFC0007 for ; Sat, 5 Apr 2025 06:03:40 +0000 (UTC) Authentication-Results: imf10.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=CuOFr8wI; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf10.hostedemail.com: domain of andrewjballance@gmail.com designates 209.85.167.175 as permitted sender) smtp.mailfrom=andrewjballance@gmail.com ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=hostedemail.com; s=arc-20220608; t=1743833021; h=from:from:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:cc:mime-version:mime-version: content-type:content-transfer-encoding:content-transfer-encoding: in-reply-to:in-reply-to:references:references:dkim-signature; bh=PVaPbNy61o/PSrVGDQktsWce5aWxOHJZx7fHMyJpHr0=; b=bryTCbe8Lq2keBFA1gGYldHdlKtkQUQix9n8kyA42KsT0Q/GHt6pET+Co3mGDx0VPBdQpK SFjWg781A3EKCeHvARIOoQZVu/2l1ugAlD2jBh5WUqg+GoxJcxDf569Jg7pnlFVCfJKZVo 4lPhXhpuDZSXBNBRYTi6CpP/6ENDfMc= ARC-Authentication-Results: i=1; imf10.hostedemail.com; dkim=pass header.d=gmail.com header.s=20230601 header.b=CuOFr8wI; dmarc=pass (policy=none) header.from=gmail.com; spf=pass (imf10.hostedemail.com: domain of andrewjballance@gmail.com designates 209.85.167.175 as permitted sender) smtp.mailfrom=andrewjballance@gmail.com ARC-Seal: i=1; s=arc-20220608; d=hostedemail.com; t=1743833021; a=rsa-sha256; cv=none; b=nyCxkWmypI0op4Y54xhb1cZNT4drKQhrffUkL7UwMQAQ0WM4FZQlXGkdrDwacwwjDAgzVk ibwmVWYK9hCysDE5rjdyrKqYM46DaT1yWrifQy29nWCzpRl5zkYwRb6Bb5WwXwuQ3dwh0c RPcOzkz40ALBFmTEagoPYyu14fb/OaM= Received: by mail-oi1-f175.google.com with SMTP id 5614622812f47-3fa58dc37c5so1875656b6e.1 for ; Fri, 04 Apr 2025 23:03:40 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1743833020; x=1744437820; darn=kvack.org; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:from:to:cc:subject:date :message-id:reply-to; bh=PVaPbNy61o/PSrVGDQktsWce5aWxOHJZx7fHMyJpHr0=; b=CuOFr8wIRB13VWXtjWI8+siYEdfWAoOXFyW/DGu2U8VpfHVg8902q31YLkM70ji+y2 8PUpF9yqKrOqScUWaR0hnCwL5G3VkvgAIixbBS1qC80H3xkEUVJkrXbvFwLx7ShLyEDi NhKFVjl3SQTg10hq4LPdPfDkvcx/t9qYf9xIagdZaXSrdk5cxii+jW5fMF282bcHUcYC OFLKuoy12H2cT+ILqbZApCta1pkhpjf9Qks2wGeExzes0v4qPNer21x3RO1xCo3us98j 1knpHhYjINDKMcE+89IkDU3otCMkw+Xq+Ux15XbDWY2BCzQMtpFGt+wgkVdmONmT+UyE nr5w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1743833020; x=1744437820; h=content-transfer-encoding:mime-version:references:in-reply-to :message-id:date:subject:cc:to:from:x-gm-message-state:from:to:cc :subject:date:message-id:reply-to; bh=PVaPbNy61o/PSrVGDQktsWce5aWxOHJZx7fHMyJpHr0=; b=SI6bOi6AZwiZa74Mbm9grJfmXtr5ioXy9Kq4r418M65jSWgVg6tA3qgJ2UaBif+d6A R/xyfGkWryOnJURaVnHaJ332kher92m17SWxpoB+UBuYGcFnlCalaN+XXNR/NVUrs5Ob DoU6bvSp9uG8FwebpouspOkQy/gyKB5Jq64/U42J0oA/PJfDacliZSFIl015HcbV+ybh 6jRoi1H1yomThju2NJy+Q/Ze0GfUkfpbR1PgiEX9OoT0cG7jZIQPkKU6oQ9P4jORjwDj dXT6/5ae/AlpB1t3+2c6GCvYnH5HXqKmNxtL25gjgbfWKEVo5MY9XLdfHzy8H18tuP+k ds6A== X-Forwarded-Encrypted: i=1; AJvYcCUJ6gGLbqdg0tZq9UdK5QAHQqHeWyJCVbIDpXFNhnEgmMLHWGX7CZxRbFQkNzFRfjymxTdpFd0FEw==@kvack.org X-Gm-Message-State: AOJu0Yx87kYwjn3n/OhgZu8kzlpEs5jxfRzcF/WCQcRe9msrbi0+dhlZ Q0jRwusKPcFpaFPJuU/uU0OGWKxgvnNI4KcXlouMCpfD4vHv4N3T X-Gm-Gg: ASbGncuMj5qa6q0Exzy93Hv9awWreDa2+rf2sBrgRthStKMv/OqnzSbyu1JZxwg1W+z V1NlD28QZ4HVdFdEA1xNra0A4f5M3HtY34KTwgFksVSsOjwIjs26o5zx4vxptYu0lEloXAdNwJ6 /9hyg0s2ynZ8H9mTgcepAsP/NtURatromw145Ym/ZsS2eqORHtZVqAIK68a06AVhlLh6tlgdoY2 zZpIEa+4d+mwIjrF6qz0+ImxD2WBfVWf9kw91/ZuRPBBcaKi9z7v5L0RUj61tyhk6eeHqt/OyjV O9dvNVvFpGN88ugrvrnqNbCUGhYBYeDL8XmGPyLDtq4RNtNvb0soHDwXK2MskKTrn6GGYreU+B/ sMJOHfTQlNQ4k2IN6 X-Google-Smtp-Source: AGHT+IEFMWdDsMam+Sj5FrfEtfi4U1OQeF2Bo3YyiOkiewnPGN6P2mqGKczzlfITtEY5tkjjyjhiDw== X-Received: by 2002:a05:6808:ec8:b0:3f6:7091:d297 with SMTP id 5614622812f47-4003d58de03mr4975447b6e.18.1743833019947; Fri, 04 Apr 2025 23:03:39 -0700 (PDT) Received: from my-computer.lan (c-73-76-29-249.hsd1.tx.comcast.net. [73.76.29.249]) by smtp.googlemail.com with ESMTPSA id 5614622812f47-40040080a15sm926565b6e.34.2025.04.04.23.03.35 (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 04 Apr 2025 23:03:39 -0700 (PDT) From: Andrew Ballance To: Liam.Howlett@oracle.com, ojeda@kernel.org, alex.gaynor@gmail.com, boqun.feng@gmail.com, gary@garyguo.net, bjorn3_gh@protonmail.com, benno.lossin@proton.me, a.hindborg@kernel.org, aliceryhl@google.com, tmgross@umich.edu, dakr@kernel.org Cc: akpm@linux-foundation.org, gregkh@linuxfoundation.org, wedsonaf@gmail.com, brauner@kernel.org, andrewjballance@gmail.com, dingxiangfei2009@gmail.com, linux-kernel@vger.kernel.org, maple-tree@lists.infradead.org, linux-mm@kvack.org, rust-for-linux@vger.kernel.org Subject: [RFC PATCH 2/2] rust: add maple tree abstractions Date: Sat, 5 Apr 2025 01:01:54 -0500 Message-ID: <20250405060154.1550858-3-andrewjballance@gmail.com> X-Mailer: git-send-email 2.49.0 In-Reply-To: <20250405060154.1550858-1-andrewjballance@gmail.com> References: <20250405060154.1550858-1-andrewjballance@gmail.com> MIME-Version: 1.0 X-Rspamd-Server: rspam11 X-Rspamd-Queue-Id: 0CAFFC0007 X-Stat-Signature: bsm9fzkq6gyeknx4hct9bc1byrnqyiz4 X-Rspam-User: X-HE-Tag: 1743833020-291733 X-HE-Meta: U2FsdGVkX1/F9YS3pqkJfx0PxDIJ7Cl8AoOyw8eJZ1LsW5jT2P3XaKZUL8nyiTKm0xbRA7391whXD5Ph3KctpyQK0uTk27KHsnheeqf7+Va429TWwb2GclxLvzdoYHw3xKky80V2Z6J1cWSY8fU8hFEdBV9qnoCwqKRfXd9TMKsTG30Tx3gWQm2Zwz+gG6Eld4+gEGGvhD5zuGoMEPqbTpLFddMCiamnNvLjDSAdbL8IxPMMg0iwcmdwGKl3MmRv9qoc2OBxcQ3jWdbDAwxAF3asfcS06ZqD4D4Z3HD2s6GZNhIf7DdloMP3JywhFmr5abxl2ayP+6UQTqvjRveSWz+hGaq/wrYQY55bTre2suDaG41Dmges9WXSnafmRdxNymOQl49DDTAVSdQrU2h2UJXl4OGSH32PgJJ61lvWDgTyVrcgB75Cz4CY2fl6gmnDPfXRX1k2hV08B9w3CSBc6ZmsEth47vbGoAPj8GxBYjrXelwKgEF+Q59ZIqDS8txoq3MsKicqsUeXMZugYAPmrSXy50BRw08RD0w+hOvh7PGjyDpbSCumMdHUY+zmM3ElIqTt0Bn0xMgb8tLCuwzvFQitoQy01hLy5ZrQlw8Mdg1sJFrEDIHmbSqsEPqw5EFHnSAcjpzO7RjjSD9RbdwoQsHzzWkum1tumJNNTiSPrQHhyS8cjKJ1QvIV1qu/WM4rdTEHcfBWBwupjhz/pTe/0BNzQGml2n45JQSfJW7N7zdMAXKlOyVsaB4yQ9OzJjHNFD+xTbJU8KGRabBIl+ZauyQLrznVGPfRurfBdFaIHmna+wW7MusDGhS2UOVMuURvPBwRajZuzM2FL8yVNWGp1VwdubygvDjRYUMaheQMJ/RUdYG17rRuBrxEQSD9L2Q0RFiqycPUVFXeRc7dqYnWFV21H5c03Plb62YnbMP7I/2pE45PSf0VIaRrsbG1Wsz+26ee1J+SuRmWZpilLXW KqGUDSxj 1dI3YZgmj1pswiOuDTttggaABBIkY9r4gglBPkImE0LB12MSqCHEG6eci4NfeuCi3Y7ZF+V3fLO5oCQXAtbpNwvwvEfmSE5M2cLHAOb4HfveTJD3RhLoBZXfkFGGInb1+n9OysV97ugb76Hu2oNY4t6evCFtroIQFugBb5gUb3fNp6m0K9LwhEhHI0/q3qekvNVKzcQdHQlEkrcrzCoopRFNCkS8LpGrGJIrFqGi9vygFRWf0ctCv5M61FfUnkaSF1xATh5uakNzzPP7gez7g8fflp33CVQb9dwH5tFfMtuZOvvqI6OkpTwBU3C4mpKeXbW90VclpluhCtPs9bFi6ghslfqKKOuesvdzkYDAKU0Kos1+YRLiGSet+hVH3S2dgc0GgeK+bJ5/9dEF+d8E3DGnLSRKeCQe3YvxAXcxHIKUxyIjL6Oo8dwr4hFoejVJILCj5XjoJvzKy11x0faumsbrcmuLL5lQcI5dgOFvDR0BJVoxSeCasMwTHAg== X-Bogosity: Ham, tests=bogofilter, spamicity=0.019002, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: List-Subscribe: List-Unsubscribe: maple trees are sparse array like data structure that maps non-overlapping ranges to pointers. implements basic abstractions for maple trees in rust. Link: https://docs.kernel.org/core-api/maple_tree.html Signed-off-by: Andrew Ballance --- rust/helpers/helpers.c | 1 + rust/helpers/maple_tree.c | 25 +++ rust/kernel/lib.rs | 1 + rust/kernel/maple_tree.rs | 340 ++++++++++++++++++++++++++++++++++++++ 4 files changed, 367 insertions(+) create mode 100644 rust/helpers/maple_tree.c create mode 100644 rust/kernel/maple_tree.rs diff --git a/rust/helpers/helpers.c b/rust/helpers/helpers.c index 0640b7e115be..6bac5ffe1684 100644 --- a/rust/helpers/helpers.c +++ b/rust/helpers/helpers.c @@ -18,6 +18,7 @@ #include "io.c" #include "jump_label.c" #include "kunit.c" +#include "maple_tree.c" #include "mutex.c" #include "page.c" #include "platform.c" diff --git a/rust/helpers/maple_tree.c b/rust/helpers/maple_tree.c new file mode 100644 index 000000000000..3e70db431616 --- /dev/null +++ b/rust/helpers/maple_tree.c @@ -0,0 +1,25 @@ +// SPDX-License-Identifier: GPL-2.0 + +#include + + +void rust_helper_mt_init_flags(struct maple_tree *mt, unsigned int flags) +{ + mt_init_flags(mt, flags); +} + +void rust_helper_mtree_lock(struct maple_tree *mt) +{ + mtree_lock(mt); +} + +void rust_helper_mtree_unlock(struct maple_tree *mt) +{ + mtree_unlock(mt); +} + +struct ma_state rust_helper_MA_STATE(struct maple_tree *mt, unsigned long start, unsigned long end) +{ + MA_STATE(mas, mt, start, end); + return mas; +} diff --git a/rust/kernel/lib.rs b/rust/kernel/lib.rs index 7697c60b2d1a..e84538d7e643 100644 --- a/rust/kernel/lib.rs +++ b/rust/kernel/lib.rs @@ -57,6 +57,7 @@ #[cfg(CONFIG_KUNIT)] pub mod kunit; pub mod list; +pub mod maple_tree; pub mod miscdevice; #[cfg(CONFIG_NET)] pub mod net; diff --git a/rust/kernel/maple_tree.rs b/rust/kernel/maple_tree.rs new file mode 100644 index 000000000000..be107e11a3dc --- /dev/null +++ b/rust/kernel/maple_tree.rs @@ -0,0 +1,340 @@ +// SPDX-License-Identifier: GPL-2.0 + +//! Maple trees. +//! +//! C header: [`include/linux/maple_tree.h`](srctree/include/linux/maple_tree.h) +//! +//! Reference: +//! +//! # Examples +//! ``` +//! # use kernel::maple_tree::*; +//! # use kernel::alloc::{KBox, flags::GFP_KERNEL}; +//! let mtree = KBox::pin_init(MapleTree::new(flags::DEFAULT_TREE), GFP_KERNEL)?; +//! let mut guard = mtree.lock(); +//! let entry = KBox::new(5, GFP_KERNEL)?; +//! guard.insert_range(0, 10, entry, GFP_KERNEL); +//! +//! for i in 0..=10 { +//! assert_eq!(guard.get(i), Some(&5)); +//! } +//! +//! guard.remove(2); +//! +//! for i in 0..=10 { +//! assert_eq!(guard.get(i), None); +//! } +//! +//! # Ok::<(), Error>(()) +//! ``` + +// TODO and missing features +// - the C version suports external locking this only supports the internal spinlock +// - this version can only have one reader because the safety requirements +// means that we need to hold the lock +// - there is currently no api for the functionality enabled by alloc_trees +// - future work may use rcu to enable lockless operation. +// - add a way to iter through ranges +// +// SAFETY: +// we cannot derefrence any pointers without holding the spinlock because +// all returned pointers are guaranteed to have been inserted by the user +// but the pointers are not guaranteed to be still be valid +// another thread may have already removed and dropped the pointers +// so to safely deref the returned pointers the user must +// have exclusive write access to the `MapleTree` +// or rcu_read_lock() is held and updater side uses a synchronize_rcu() + +use core::{ffi::c_void, marker::PhantomData, pin::Pin, ptr::NonNull}; + +use macros::pin_data; +use macros::pinned_drop; + +use crate::error::code; +use crate::prelude::PinInit; + +use crate::{ + alloc, bindings, + error::{self, Error}, + pin_init, + types::{ForeignOwnable, NotThreadSafe, Opaque}, +}; + +/// A `MapleTree` is a tree like data structure that is optimized for storing +/// non-overlaping ranges and mapping them to pointers. +/// They use rcu locks and an internal spinlock to syncronise access. +/// +/// Note that maple tree ranges are range inclusive. +// # Invariants +// self.root is always a valid and initialized `bindings::maple_tree` +// +// all values inserted into the tree come from `T::into_foreign` +#[pin_data(PinnedDrop)] +pub struct MapleTree { + #[pin] + root: Opaque, + _p: PhantomData, +} + +impl MapleTree { + /// creates a new `MapleTree` with the specified `flags` + /// + /// see [`flags`] for the list of flags and their usage + pub fn new(flags: Flags) -> impl PinInit { + pin_init!( + Self{ + // SAFETY: + // - mt is valid because of ffi_init + // - maple_tree contains a lock which should be pinned + root <- Opaque::ffi_init(|mt| unsafe { + bindings::mt_init_flags(mt, flags.as_raw()) + }), + _p: PhantomData + } + + ) + } + + /// helper for internal use. + /// returns an iterator through the maple tree + /// # Safety + /// - the user must ensure that it has exclusive access to the tree if no locks are held + /// - if the internal lock is held it is safe to deref the returned pointers + /// - if the rcu lock is held the pointers will be a value that was inserted + /// by the user but possibly may be invalid + unsafe fn iter_no_lock(&self) -> IterNoLock<'_, T> { + // SAFETY: + // self.root.get() will allways point to a valid maple_tree + // by the invariants of MapleTree + let ma_state = unsafe { Opaque::new(bindings::MA_STATE(self.root.get(), 0, usize::MAX)) }; + IterNoLock { + ma_state, + _p: PhantomData, + } + } + + /// locks the `Mapletree`'s internal spinlock and returns a [`Guard`]. + /// When the `Guard` is dropped, the internal spinlock is unlocked + /// if the lock is already held by the current thread this will deadlock + pub fn lock(&self) -> Guard<'_, T> { + // SAFETY: + // self.root.get() will allways point to a valid maple_tree + // by the invariants of MapleTree + unsafe { bindings::mtree_lock(self.root.get()) }; + Guard { + tree: self, + _not_send: NotThreadSafe, + } + } +} + +#[pinned_drop] +impl PinnedDrop for MapleTree { + fn drop(self: Pin<&mut Self>) { + // SAFETY: + // - we have exclusive access to self because we should have + // exclussive access whenever drop is called + // if drop is called multiple times an invariant is already violated + for i in unsafe { self.iter_no_lock() } { + //SAFETY: + // - we can call from_foreign because all values inserted into a MapleTree + // come from T::into_foreign + // - i.as_ptr is guaranteed to not be null because of the invariant of NonNull + // - we have exclusive access to self because we should have + // exclussive access whenever drop is called + let original = unsafe { T::from_foreign(i.as_ptr()) }; + drop(original); + } + // SAFETY: + // - self.root.get() will allways point to a valid maple_tree + // by the invariants of MapleTree + // - we can call this without taking the spinlock because we should have + // exclusive access whenever drop is called + unsafe { + bindings::__mt_destroy(self.root.get()); + } + } +} + +// SAFETY: `MapleTree` has no shared mutable state so it is `Send` iff `T` is `Send`. +// MapleTree is still pin_init so it still cannot be moved but this means that types like +// Box> can be sent between threads +unsafe impl Send for MapleTree {} + +// SAFETY: `MapleTree` has interior mutability so it is `Sync` iff `T` is `Send`. +unsafe impl Sync for MapleTree {} + +/// an iterator over all of the values in a [`MapleTree`]. +/// this intentionally does not hold the rcu lock or the internal lock +/// the user must ensure that it exclusive access to the tree if no locks are held +/// if the internal lock is held it is safe to deref the returned pointers +/// if the rcu lock is held the pointers will be a value that was inserted +/// by the user but possibly may be invalid +struct IterNoLock<'a, T: ForeignOwnable> { + ma_state: Opaque, + _p: PhantomData<&'a MapleTree>, +} + +impl<'a, T: ForeignOwnable> Iterator for IterNoLock<'a, T> { + type Item = NonNull; + fn next(&mut self) -> Option { + // SAFETY: + // self.ma_state.get() will allways point to a valid ma_state by the invariants of Iter + let ptr: *mut c_void = unsafe { bindings::mas_find(self.ma_state.get(), usize::MAX) }; + NonNull::new(ptr) + } +} + +/// A lock guard for a [`MapleTree`]'s internal spinlock +/// +/// The lock is unlocked when the guard goes out of scope +// # Invariants +// +// `tree` is always a valid reference to a locked `MapleTree` +// `tree` is unlocked when the guard is dropped +pub struct Guard<'a, T: ForeignOwnable> { + tree: &'a MapleTree, + _not_send: NotThreadSafe, +} + +impl<'a, T: ForeignOwnable> Guard<'a, T> { + /// Removes a value at the specified index. + /// if there is no value at the index returns `None`. + /// if there is a value at the index returns it and unmaps the entire range + pub fn remove(&mut self, index: usize) -> Option { + // SAFETY: + // - we can safely call MA_STATE because self.tree.root.get() will be valid + // by the invariants of guard + // - we can safely call mas_erase because the lock is held and mas is valid + // - we can call try_from_foreign because all values inserted into a MapleTree + // come from T::into_foreign + unsafe { + let mas = Opaque::new(bindings::MA_STATE(self.tree.root.get(), index, index)); + let removed = bindings::mas_erase(mas.get()); + T::try_from_foreign(removed) + } + } + + /// Returns a reference to the `T` at `index` if it exists, + /// otherwise returns `None` + pub fn get(&self, index: usize) -> Option> { + // SAFETY: + // self.tree.root.get() will always be valid because of the invariants of MapleTree + let ptr = unsafe { bindings::mtree_load(self.tree.root.get(), index) }; + if ptr.is_null() { + return None; + } + // SAFETY: + // - we can safely call borrow because all values inserted into a MapleTree + // come from T::into_foreign + // - ptr is not null by the check above + Some(unsafe { T::borrow(ptr) }) + } + + /// Returns a mut reference to the `T` at `index` if it exists, + /// otherwise returns `None` + pub fn get_mut(&mut self, index: usize) -> Option> { + // SAFETY: + // self.tree.root.get() will always be valid because of the invariants of MapleTree + let ptr = unsafe { bindings::mtree_load(self.tree.root.get(), index) }; + if ptr.is_null() { + return None; + } + // SAFETY: + // - we can safely call borrowmut because all values inserted into a MapleTree + // come from T::into_foreign + // - ptr is not null by the check above + // - we have exclusive ownership becauce this function takes `&mut self` + Some(unsafe { T::borrow_mut(ptr) }) + } + + /// a convenience alias for [`Self::insert_range`] where `start == end` + pub fn insert(&mut self, index: usize, value: T, gfp: alloc::Flags) -> Result<(), (T, Error)> { + self.insert_range(index, index, value, gfp) + } + + /// Maps the range `[start, end]` to `value` in the MapleTree. + /// if `[start, end]` overlaps with any range already inserted, then `value` will + /// not be inserted. + /// + /// * Returns `Ok(())` if insertion is successful + /// + /// * Returns `Err((value, EINVAL))` if `T::into_foreign` is `NULL` + /// or is in [0, 4096] with the bottom two bits set to `10` (ie 2, 6, 10 .. 4094) + /// or `start` > `end`. + /// + /// * Returns `Err((value, EEXISTS))` if there is any entry already within the range. + /// + /// * Returns `Err((value, ENOMEM))` if allocation failed. + pub fn insert_range( + &mut self, + start: usize, + end: usize, + value: T, + gfp: alloc::Flags, + ) -> Result<(), (T, Error)> { + let ptr = value.into_foreign(); + // a insertion of NULL will succeed even if there are values stored there (i tested this) + // this may remove values that we do not want to remove + // and any stored T that gets overwritten will not be dropped + // which we do not want to happen + // so return early if ptr is NULL + if ptr.is_null() { + // SAFETY: + // ptr is from T::into_foreign so we can safely convert it back + let original = unsafe { T::from_foreign(ptr) }; + return Err((original, code::EINVAL)); + } + + // SAFETY: + // - we can call __mtree_insert_range because we hold the lock because of the + // invariants of self + // - self.tree.root.get() will always be valid because of the invariants of MapleTree + let errno = unsafe { + bindings::__mtree_insert_range(self.tree.root.get(), start, end, ptr, gfp.as_raw()) + }; + + let err = error::to_result(errno); + // SAFETY: + // - we can call from_foreign because all values inserted into a MapleTree + // come from T::into_foreign + // - we have exclusive ownership of ptr because if err is an error then, ptr was + // not inserted into the MapleTree + // + err.map_err(|e| unsafe { (T::from_foreign(ptr), e) }) + } +} + +impl Drop for Guard<'_, T> { + fn drop(&mut self) { + // SAFETY: + // - unlock the MapleTree because the guard is being dropped + // - self.tree.root.get() will always be valid because of the invariants of MapleTree + unsafe { bindings::mtree_unlock(self.tree.root.get()) }; + } +} + +#[derive(Clone, Copy, PartialEq)] +/// flags to be used with [`MapleTree::new`]. +/// +/// values can used from the [`flags`] module. +pub struct Flags(u32); + +impl Flags { + pub(crate) fn as_raw(self) -> u32 { + self.0 + } +} + +/// flags to be used with [`MapleTree::new`] +pub mod flags { + use super::Flags; + + /// Creates a default MapleTree + pub const DEFAULT_TREE: Flags = Flags(0); + + /// if a `MapleTree` is created with ALLOC_TREE the `MapleTree` will be a alloc tree. + /// alloc trees have a lower branching factor but allows the user to search + /// for a gap of a given size. + pub const ALLOC_TREE: Flags = Flags(bindings::MT_FLAGS_ALLOC_RANGE); +}