From nobody Sat Feb 7 07:10:20 2026 Received: from mail-yb1-f201.google.com (mail-yb1-f201.google.com [209.85.219.201]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id DE0AB13A899 for ; Fri, 16 Aug 2024 20:48:04 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.219.201 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723841286; cv=none; b=LSVHZRM8If1StyWKM6k/GYiiJHfLAfj7bMl7MvvzlR2PcSx/CX201wRpmfO6h+1NI2BrVsp4pPEqUvmXH6WOjLNCw0BnTUs4PssQHudwonO8iZx0DU8W/JBoEDk+zvPbhmVK9DqIAtdW9kNXwz1U1b8Z1xjc/KCy0217gvS1urU= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723841286; c=relaxed/simple; bh=BI8PHNJTfXcLO+UUAm58BuWx0Vjek3ATKPy+xwLajGs=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=BfI7gBcmH1QbyTyC1ySGL94vKOCOgM7bLvFZw8w5tmGs7oG5PTkNhQIUCOOj9uSb/ykWmHLp2PL/+dJcPKYxg8RRh7HedawX0nt63d0ngxZnKWZUtXX4hvoAjHKZFULn5Q9cWpIxg2s/D3vIx7xa86wzplrwxCfkzqXEbD1X7z8= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com; spf=pass smtp.mailfrom=flex--mattgilbride.bounces.google.com; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b=car5xSHF; arc=none smtp.client-ip=209.85.219.201 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=flex--mattgilbride.bounces.google.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="car5xSHF" Received: by mail-yb1-f201.google.com with SMTP id 3f1490d57ef6-e1159fb161fso3517515276.1 for ; Fri, 16 Aug 2024 13:48:04 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1723841284; x=1724446084; darn=vger.kernel.org; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=6UpT8wOwNJORmlebbf/8Uat6NCTU+oJ243lKTzUmD5Y=; b=car5xSHFH3i0Cq7jF+LWSeABplesvyugBes6LyAKkfoRBX8TS0UGHRdTDTA/f41dil +6auscWedm984lycttAQaMZVGgpyVmTEReicovmu+R6dIlLwVavp8pwloSle66fn+Vlz aMyrPURvIPKpGk3qsPqs3kNkrd0Uwd1EucsSplDTkWZ+I8x8JjK7e5dvpnkZG6qgNqd5 3YvCqf19v9K/u5RzHw5brXurXc2trRkyvZFKUxjswmzCji6eZoT3/z7NYEQ7k/rqKPya xqZZuiEt42Jx4Vx0mbPHBGGYkZbk9gRU56s4d3ZUXz8zgkLkXKDA8eeQefRD7Ffbm72d Ybvw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1723841284; x=1724446084; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=6UpT8wOwNJORmlebbf/8Uat6NCTU+oJ243lKTzUmD5Y=; b=aQyHeaUKocjN7amRrykrpuiB5GfKvD7KuAmmHejPIp9MdzEFcT9tAoctAiFPrG6GTO M4IVf5/J20FgyA2aD70+zkRY3k6TSQPqoha5BB1VnYA6HYwisC7FYddKB0BYbOy/MHjM b3wfllqOpPnzLNFydQytQM6Bqmr7xBGxvoNWzl4qfxKbNzOxJwQj6+dEN6OiR1/jzla8 NBkoNAQ4gEIhW+YvrJ2NBtlYjhJSvFsjYpm/bwsY2iKv6fCMZq1HsWouat1dsKo+pIeJ j+cr6eb/PgVbYU1631n8gr9hQHgA1ZUG3yg/ppScmc8oKrMnPFZFJb+7r0zl/i6Y6ZWI qWQw== X-Forwarded-Encrypted: i=1; AJvYcCUmaDQI9GLma8ff9btHvxHSqIxC/NeZYvKD6Ao825j9xN0BHdk17MhicgsExwrEr3bo/4NWGw+qJtjgLZI=@vger.kernel.org X-Gm-Message-State: AOJu0YxMXVlk2+cVqMliQpRE30O+BgicihzV7Z+EpQTU/d0qRcjVzi0T LDSCNBaVcb3LNcuv2zBbLXhthsg5tJZHBkivw82QlwlSc7DYMzbQPSeI32nwYBdpl7eAizOtJJj qeL7BA0DbZyKZD3hLseK/wqW49A== X-Google-Smtp-Source: AGHT+IELGeBoRm8VfWBBL2EoMJHsshIWLt/5bDCdxr1SXybvD7gnLyzHvlUcyMT2Y8qs0F5lik0YliPldIynDvQbPT0= X-Received: from mattgilbride.c.googlers.com ([fda3:e722:ac3:cc00:2b:7d90:c0a8:2ac5]) (user=mattgilbride job=sendgmr) by 2002:a25:910e:0:b0:e03:59e2:e82 with SMTP id 3f1490d57ef6-e1180fb2b4dmr6070276.10.1723841283714; Fri, 16 Aug 2024 13:48:03 -0700 (PDT) Date: Fri, 16 Aug 2024 20:47:58 +0000 In-Reply-To: <20240816-b4-rbtree-v9-0-425b442af7e5@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240816-b4-rbtree-v9-0-425b442af7e5@google.com> X-Mailer: b4 0.13.0 Message-ID: <20240816-b4-rbtree-v9-1-425b442af7e5@google.com> Subject: [PATCH v9 1/6] rust: kernel: add `drop_contents` to `BoxExt` From: Matt Gilbride To: Miguel Ojeda , Alex Gaynor , Wedson Almeida Filho , Boqun Feng , Gary Guo , "=?utf-8?q?Bj=C3=B6rn_Roy_Baron?=" , Benno Lossin , Andreas Hindborg , Alice Ryhl , Greg Kroah-Hartman , "=?utf-8?q?Arve_Hj=C3=B8nnev=C3=A5g?=" , Todd Kjos , Martijn Coenen , Joel Fernandes , Carlos Llamas , Suren Baghdasaryan , Christian Brauner Cc: Rob Landley , Davidlohr Bueso , Michel Lespinasse , rust-for-linux@vger.kernel.org, linux-kernel@vger.kernel.org, Matt Gilbride Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable From: Benno Lossin Sometimes (see [1]) it is necessary to drop the value inside of a `Box`, but retain the allocation. For example to reuse the allocation in the future. Introduce a new function `drop_contents` that turns a `Box` into `Box>` by dropping the value. Signed-off-by: Benno Lossin Link: https://lore.kernel.org/rust-for-linux/20240418-b4-rbtree-v3-5-323e13= 4390ce@google.com/ [1] Reviewed-by: Boqun Feng Reviewed-by: Alice Ryhl --- rust/kernel/alloc/box_ext.rs | 22 ++++++++++++++++++++++ 1 file changed, 22 insertions(+) diff --git a/rust/kernel/alloc/box_ext.rs b/rust/kernel/alloc/box_ext.rs index 829cb1c1cf9e..6cf79f96d6c7 100644 --- a/rust/kernel/alloc/box_ext.rs +++ b/rust/kernel/alloc/box_ext.rs @@ -5,6 +5,8 @@ use super::{AllocError, Flags}; use alloc::boxed::Box; use core::mem::MaybeUninit; +use core::ptr; +use core::result::Result; =20 /// Extensions to [`Box`]. pub trait BoxExt: Sized { @@ -17,6 +19,18 @@ pub trait BoxExt: Sized { /// /// The allocation may fail, in which case an error is returned. fn new_uninit(flags: Flags) -> Result>, AllocError>; + + /// Drops the contents, but keeps the allocation. + /// + /// # Examples + /// + /// ``` + /// let value =3D Box::new([0; 32], flags::GFP_KERNEL) + /// let value =3D value.drop_contents(); + /// // Now we can re-use `value`: + /// Box::write(value, [1; 32]); + /// ``` + fn drop_contents(self) -> Box>; } =20 impl BoxExt for Box { @@ -53,4 +67,12 @@ fn new_uninit(flags: Flags) -> Result= >, AllocError> { // zero-sized types, we use `NonNull::dangling`. Ok(unsafe { Box::from_raw(ptr) }) } + + fn drop_contents(self) -> Box> { + let ptr =3D Box::into_raw(self); + // SAFETY: `ptr` is valid, because it came from `Box::into_raw`. + unsafe { ptr::drop_in_place(ptr) }; + // SAFETY: `ptr` is valid, because it came from `Box::into_raw`. + unsafe { Box::from_raw(ptr.cast()) } + } } --=20 2.46.0.184.g6999bdac58-goog From nobody Sat Feb 7 07:10:20 2026 Received: from mail-yb1-f201.google.com (mail-yb1-f201.google.com [209.85.219.201]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id EBFBA13C3C2 for ; Fri, 16 Aug 2024 20:48:05 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.219.201 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723841289; cv=none; b=mzapJWfyXO08kx9X1FKuN7/7IN/nGHavQcl0q9guklNoh5de2q0EqI2y6bXnH7xzTolkKkgoGA+6atJm9RNb9nBxm3NB53uR+7DmKrkedWciWZZOqTahggDz0JkmTZu02Nz2ShZUoAeLK79qqLH8hZo2mlYGOeFg1jqOoe6KMlM= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723841289; c=relaxed/simple; bh=ycf9jnVXZOkjKcGuG7M/np1cL8NIMP+wQB1MYVBbCA0=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=kS2uP1QlvhsK/auO3Brf7HYUK8II5SEMoc0eL+Q+k15y1inG6l2DKg3erRK2psop+oR8D3akxKQceEBBFqAAhhVblLUTwf7GZsMufbyaVqTwKhGRRx6WdDXBB37ntU9X7MQWHs5J8K5IGSXydUgJwzCMInc5VSxdZwa5wh5YYSA= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com; spf=pass smtp.mailfrom=flex--mattgilbride.bounces.google.com; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b=UHDXh8+q; arc=none smtp.client-ip=209.85.219.201 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=flex--mattgilbride.bounces.google.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="UHDXh8+q" Received: by mail-yb1-f201.google.com with SMTP id 3f1490d57ef6-e117c61d98cso2184446276.0 for ; Fri, 16 Aug 2024 13:48:05 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1723841285; x=1724446085; darn=vger.kernel.org; h=content-transfer-encoding:cc:to:from:subject:message-id:references :mime-version:in-reply-to:date:from:to:cc:subject:date:message-id :reply-to; bh=xkVcJJSJKH+YanAREyQ8OB0VaWFK5xzuUXkf1xWmYj0=; b=UHDXh8+qLuJazSvJcbEOIzWEkr/ALpmY+1+S+moQj8boFNiAj7LPC/wDTmVLuCY+bE PuoIix/Q6FTqk9prXgtkS8VtrvuxNJORi2O+GiauJq/2urx5wBInhSVg1GyDzg63f/7U Gpr74mfo4pD0soXbqTFNsQiJvkWTUCmG3wwaogQhVnp+pFXEIroTcKRiB+XRAfud/v5h lBGOvbETTtzhzy1PCNKVsUNs2SbiBQYmDSf+rmLEN/YXg2LImP6S7SfcKRoUDPg5to1k P6tORRaNqa3UozAwYv9DWaA7/KUz+g++ckcYtOtF/DzF41jPSD1+uiMDu9FBa4adMhLG 0Fiw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1723841285; x=1724446085; h=content-transfer-encoding:cc:to:from:subject:message-id:references :mime-version:in-reply-to:date:x-gm-message-state:from:to:cc:subject :date:message-id:reply-to; bh=xkVcJJSJKH+YanAREyQ8OB0VaWFK5xzuUXkf1xWmYj0=; b=Lj1u1HDu1rSC7UEx4WB+GCACYxgt4PSiFM26CfSdWm6aBCzs9vfBONBm1rNFq6Ko1t tkKXe5p/5YqkXg2gSLrNngJ5qcxE7vTmpVNDYCMdcGeuyi92pzKxVlk6QlXmhmXiEOQS OqgtSP5fiu1L1ufu8VBEkGLZS5pUs32jo8HNLrch1KceczTluKMISQH2UIGEhbSLZYjz zJEU0igeRhzbSRQRo3p2Q1OXI5kYATC5xnS3jLlF73iAZ3WGi+qO93NcjqOe4Ap1K63h uwHIJfu4UwTSPO4uXN8UUA9gRXzHVtWMWGkxJU3sV90XuBnaTk7RIccIeZCfaHI3wKrm qvFA== X-Forwarded-Encrypted: i=1; AJvYcCVtF+ZQ3CPlMj+ewSS8Ovnq4Xrwfj2xj+cIkmqwr6nOZqe4iQyvMEIvu+7amrb6RyPSFhM9cF/k9SSn57uSiI8by8j7570bRyQpyZeT X-Gm-Message-State: AOJu0YxqfKw+7g3fEmQRAbnwPWET6K6IaR09a9Wqg+P20utttH65JG0G p+ZGbXl3kh76/PNPd4N9CGp4K0aKQla42/ttkXB/ShzJteRJtzwXqmNYtJ8Pn0jnNlowzJuGRw/ QhKQQnDv8OlEVz2xawRbhrcvDbQ== X-Google-Smtp-Source: AGHT+IF26W2wQ0/2i4e8c4ugGbw5CxoGIZVeiTLH0OzBWaPCrwuZA5b5v+DHqziZhZmvWPJ5VUDXdbqwDXP9gaAMt6s= X-Received: from mattgilbride.c.googlers.com ([fda3:e722:ac3:cc00:2b:7d90:c0a8:2ac5]) (user=mattgilbride job=sendgmr) by 2002:a05:6902:8d:b0:e11:5d3e:83c5 with SMTP id 3f1490d57ef6-e1180f74e4dmr7034276.11.1723841284708; Fri, 16 Aug 2024 13:48:04 -0700 (PDT) Date: Fri, 16 Aug 2024 20:47:59 +0000 In-Reply-To: <20240816-b4-rbtree-v9-0-425b442af7e5@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240816-b4-rbtree-v9-0-425b442af7e5@google.com> X-Mailer: b4 0.13.0 Message-ID: <20240816-b4-rbtree-v9-2-425b442af7e5@google.com> Subject: [PATCH v9 2/6] rust: rbtree: add red-black tree implementation backed by the C version From: Matt Gilbride To: Miguel Ojeda , Alex Gaynor , Wedson Almeida Filho , Boqun Feng , Gary Guo , "=?utf-8?q?Bj=C3=B6rn_Roy_Baron?=" , Benno Lossin , Andreas Hindborg , Alice Ryhl , Greg Kroah-Hartman , "=?utf-8?q?Arve_Hj=C3=B8nnev=C3=A5g?=" , Todd Kjos , Martijn Coenen , Joel Fernandes , Carlos Llamas , Suren Baghdasaryan , Christian Brauner Cc: Rob Landley , Davidlohr Bueso , Michel Lespinasse , rust-for-linux@vger.kernel.org, linux-kernel@vger.kernel.org, Matt Gilbride Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable From: Wedson Almeida Filho The rust rbtree exposes a map-like interface over keys and values, backed by the kernel red-black tree implementation. Values can be inserted, deleted, and retrieved from a `RBTree` by key. This base abstraction is used by binder to store key/value pairs and perform lookups, for example the patch "[PATCH RFC 03/20] rust_binder: add threading support" in the binder RFC [1]. Link: https://lore.kernel.org/rust-for-linux/20231101-rust-binder-v1-3-08ba= 9197f637@google.com/ [1] Signed-off-by: Wedson Almeida Filho Reviewed-by: Alice Ryhl Tested-by: Alice Ryhl Reviewed-by: Boqun Feng Reviewed-by: Benno Lossin Signed-off-by: Matt Gilbride --- rust/helpers.c | 6 + rust/kernel/alloc/box_ext.rs | 4 +- rust/kernel/lib.rs | 1 + rust/kernel/rbtree.rs | 432 +++++++++++++++++++++++++++++++++++++++= ++++ 4 files changed, 442 insertions(+), 1 deletion(-) diff --git a/rust/helpers.c b/rust/helpers.c index 92d3c03ae1bd..3be13ec7f222 100644 --- a/rust/helpers.c +++ b/rust/helpers.c @@ -199,6 +199,12 @@ rust_helper_krealloc(const void *objp, size_t new_size= , gfp_t flags) return krealloc(objp, new_size, flags); } EXPORT_SYMBOL_GPL(rust_helper_krealloc); +void rust_helper_rb_link_node(struct rb_node *node, struct rb_node *parent, + struct rb_node **rb_link) +{ + rb_link_node(node, parent, rb_link); +} +EXPORT_SYMBOL_GPL(rust_helper_rb_link_node); =20 /* * `bindgen` binds the C `size_t` type as the Rust `usize` type, so we can diff --git a/rust/kernel/alloc/box_ext.rs b/rust/kernel/alloc/box_ext.rs index 6cf79f96d6c7..141d2ef9eaa3 100644 --- a/rust/kernel/alloc/box_ext.rs +++ b/rust/kernel/alloc/box_ext.rs @@ -25,7 +25,9 @@ pub trait BoxExt: Sized { /// # Examples /// /// ``` - /// let value =3D Box::new([0; 32], flags::GFP_KERNEL) + /// use kernel::alloc::flags; + /// + /// let value =3D Box::new([0; 32], flags::GFP_KERNEL).unwrap(); /// let value =3D value.drop_contents(); /// // Now we can re-use `value`: /// Box::write(value, [1; 32]); diff --git a/rust/kernel/lib.rs b/rust/kernel/lib.rs index 274bdc1b0a82..80bdf2b1016d 100644 --- a/rust/kernel/lib.rs +++ b/rust/kernel/lib.rs @@ -43,6 +43,7 @@ pub mod page; pub mod prelude; pub mod print; +pub mod rbtree; mod static_assert; #[doc(hidden)] pub mod std_vendor; diff --git a/rust/kernel/rbtree.rs b/rust/kernel/rbtree.rs new file mode 100644 index 000000000000..51c53a25bc7d --- /dev/null +++ b/rust/kernel/rbtree.rs @@ -0,0 +1,432 @@ +// SPDX-License-Identifier: GPL-2.0 + +//! Red-black trees. +//! +//! C header: [`include/linux/rbtree.h`](srctree/include/linux/rbtree.h) +//! +//! Reference: + +use crate::{alloc::Flags, bindings, container_of, error::Result, prelude::= *}; +use alloc::boxed::Box; +use core::{ + cmp::{Ord, Ordering}, + marker::PhantomData, + mem::MaybeUninit, + ptr::{addr_of_mut, NonNull}, +}; + +/// A red-black tree with owned nodes. +/// +/// It is backed by the kernel C red-black trees. +/// +/// # Examples +/// +/// In the example below we do several operations on a tree. We note that = insertions may fail if +/// the system is out of memory. +/// +/// ``` +/// use kernel::{alloc::flags, rbtree::{RBTree, RBTreeNode, RBTreeNodeRese= rvation}}; +/// +/// // Create a new tree. +/// let mut tree =3D RBTree::new(); +/// +/// // Insert three elements. +/// tree.try_create_and_insert(20, 200, flags::GFP_KERNEL)?; +/// tree.try_create_and_insert(10, 100, flags::GFP_KERNEL)?; +/// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?; +/// +/// // Check the nodes we just inserted. +/// { +/// assert_eq!(tree.get(&10).unwrap(), &100); +/// assert_eq!(tree.get(&20).unwrap(), &200); +/// assert_eq!(tree.get(&30).unwrap(), &300); +/// } +/// +/// // Replace one of the elements. +/// tree.try_create_and_insert(10, 1000, flags::GFP_KERNEL)?; +/// +/// // Check that the tree reflects the replacement. +/// { +/// assert_eq!(tree.get(&10).unwrap(), &1000); +/// assert_eq!(tree.get(&20).unwrap(), &200); +/// assert_eq!(tree.get(&30).unwrap(), &300); +/// } +/// +/// // Change the value of one of the elements. +/// *tree.get_mut(&30).unwrap() =3D 3000; +/// +/// // Check that the tree reflects the update. +/// { +/// assert_eq!(tree.get(&10).unwrap(), &1000); +/// assert_eq!(tree.get(&20).unwrap(), &200); +/// assert_eq!(tree.get(&30).unwrap(), &3000); +/// } +/// +/// // Remove an element. +/// tree.remove(&10); +/// +/// // Check that the tree reflects the removal. +/// { +/// assert_eq!(tree.get(&10), None); +/// assert_eq!(tree.get(&20).unwrap(), &200); +/// assert_eq!(tree.get(&30).unwrap(), &3000); +/// } +/// +/// # Ok::<(), Error>(()) +/// ``` +/// +/// In the example below, we first allocate a node, acquire a spinlock, th= en insert the node into +/// the tree. This is useful when the insertion context does not allow sle= eping, for example, when +/// holding a spinlock. +/// +/// ``` +/// use kernel::{alloc::flags, rbtree::{RBTree, RBTreeNode}, sync::SpinLoc= k}; +/// +/// fn insert_test(tree: &SpinLock>) -> Result { +/// // Pre-allocate node. This may fail (as it allocates memory). +/// let node =3D RBTreeNode::new(10, 100, flags::GFP_KERNEL)?; +/// +/// // Insert node while holding the lock. It is guaranteed to succeed= with no allocation +/// // attempts. +/// let mut guard =3D tree.lock(); +/// guard.insert(node); +/// Ok(()) +/// } +/// ``` +/// +/// In the example below, we reuse an existing node allocation from an ele= ment we removed. +/// +/// ``` +/// use kernel::{alloc::flags, rbtree::{RBTree, RBTreeNodeReservation}}; +/// +/// // Create a new tree. +/// let mut tree =3D RBTree::new(); +/// +/// // Insert three elements. +/// tree.try_create_and_insert(20, 200, flags::GFP_KERNEL)?; +/// tree.try_create_and_insert(10, 100, flags::GFP_KERNEL)?; +/// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?; +/// +/// // Check the nodes we just inserted. +/// { +/// assert_eq!(tree.get(&10).unwrap(), &100); +/// assert_eq!(tree.get(&20).unwrap(), &200); +/// assert_eq!(tree.get(&30).unwrap(), &300); +/// } +/// +/// // Remove a node, getting back ownership of it. +/// let existing =3D tree.remove(&30).unwrap(); +/// +/// // Check that the tree reflects the removal. +/// { +/// assert_eq!(tree.get(&10).unwrap(), &100); +/// assert_eq!(tree.get(&20).unwrap(), &200); +/// assert_eq!(tree.get(&30), None); +/// } +/// +/// // Create a preallocated reservation that we can re-use later. +/// let reservation =3D RBTreeNodeReservation::new(flags::GFP_KERNEL)?; +/// +/// // Insert a new node into the tree, reusing the previous allocation. T= his is guaranteed to +/// // succeed (no memory allocations). +/// tree.insert(reservation.into_node(15, 150)); +/// +/// // Check that the tree reflect the new insertion. +/// { +/// assert_eq!(tree.get(&10).unwrap(), &100); +/// assert_eq!(tree.get(&15).unwrap(), &150); +/// assert_eq!(tree.get(&20).unwrap(), &200); +/// } +/// +/// # Ok::<(), Error>(()) +/// ``` +/// +/// # Invariants +/// +/// Non-null parent/children pointers stored in instances of the `rb_node`= C struct are always +/// valid, and pointing to a field of our internal representation of a nod= e. +pub struct RBTree { + root: bindings::rb_root, + _p: PhantomData>, +} + +// SAFETY: An [`RBTree`] allows the same kinds of access to its values tha= t a struct allows to its +// fields, so we use the same Send condition as would be used for a struct= with K and V fields. +unsafe impl Send for RBTree {} + +// SAFETY: An [`RBTree`] allows the same kinds of access to its values tha= t a struct allows to its +// fields, so we use the same Sync condition as would be used for a struct= with K and V fields. +unsafe impl Sync for RBTree {} + +impl RBTree { + /// Creates a new and empty tree. + pub fn new() -> Self { + Self { + // INVARIANT: There are no nodes in the tree, so the invariant= holds vacuously. + root: bindings::rb_root::default(), + _p: PhantomData, + } + } +} + +impl RBTree +where + K: Ord, +{ + /// Tries to insert a new value into the tree. + /// + /// It overwrites a node if one already exists with the same key and r= eturns it (containing the + /// key/value pair). Returns [`None`] if a node with the same key didn= 't already exist. + /// + /// Returns an error if it cannot allocate memory for the new node. + pub fn try_create_and_insert( + &mut self, + key: K, + value: V, + flags: Flags, + ) -> Result>> { + Ok(self.insert(RBTreeNode::new(key, value, flags)?)) + } + + /// Inserts a new node into the tree. + /// + /// It overwrites a node if one already exists with the same key and r= eturns it (containing the + /// key/value pair). Returns [`None`] if a node with the same key didn= 't already exist. + /// + /// This function always succeeds. + pub fn insert(&mut self, RBTreeNode { node }: RBTreeNode) -> Opt= ion> { + let node =3D Box::into_raw(node); + // SAFETY: `node` is valid at least until we call `Box::from_raw`,= which only happens when + // the node is removed or replaced. + let node_links =3D unsafe { addr_of_mut!((*node).links) }; + + // The parameters of `bindings::rb_link_node` are as follows: + // - `node`: A pointer to an uninitialized node being inserted. + // - `parent`: A pointer to an existing node in the tree. One of i= ts child pointers must be + // null, and `node` will become a child of `parent` by re= placing that child pointer + // with a pointer to `node`. + // - `rb_link`: A pointer to either the left-child or right-child = field of `parent`. This + // specifies which child of `parent` should hold `node` a= fter this call. The + // value of `*rb_link` must be null before the call to `r= b_link_node`. If the + // red/black tree is empty, then it=E2=80=99s also possib= le for `parent` to be null. In + // this case, `rb_link` is a pointer to the `root` field = of the red/black tree. + // + // We will traverse the tree looking for a node that has a null po= inter as its child, + // representing an empty subtree where we can insert our new node.= We need to make sure + // that we preserve the ordering of the nodes in the tree. In each= iteration of the loop + // we store `parent` and `child_field_of_parent`, and the new `nod= e` will go somewhere + // in the subtree of `parent` that `child_field_of_parent` points = at. Once + // we find an empty subtree, we can insert the new node using `rb_= link_node`. + let mut parent =3D core::ptr::null_mut(); + let mut child_field_of_parent: &mut *mut bindings::rb_node =3D &mu= t self.root.rb_node; + while !child_field_of_parent.is_null() { + parent =3D *child_field_of_parent; + + // We need to determine whether `node` should be the left or r= ight child of `parent`, + // so we will compare with the `key` field of `parent` a.k.a. = `this` below. + // + // SAFETY: By the type invariant of `Self`, all non-null `rb_n= ode` pointers stored in `self` + // point to the links field of `Node` objects. + let this =3D unsafe { container_of!(parent, Node, links)= }; + + // SAFETY: `this` is a non-null node so it is valid by the typ= e invariants. `node` is + // valid until the node is removed. + match unsafe { (*node).key.cmp(&(*this).key) } { + // We would like `node` to be the left child of `parent`. = Move to this child to check + // whether we can use it, or continue searching, at the ne= xt iteration. + // + // SAFETY: `parent` is a non-null node so it is valid by t= he type invariants. + Ordering::Less =3D> child_field_of_parent =3D unsafe { &mu= t (*parent).rb_left }, + // We would like `node` to be the right child of `parent`.= Move to this child to check + // whether we can use it, or continue searching, at the ne= xt iteration. + // + // SAFETY: `parent` is a non-null node so it is valid by t= he type invariants. + Ordering::Greater =3D> child_field_of_parent =3D unsafe { = &mut (*parent).rb_right }, + Ordering::Equal =3D> { + // There is an existing node in the tree with this key= , and that node is + // `parent`. Thus, we are replacing parent with a new = node. + // + // INVARIANT: We are replacing an existing node with a= new one, which is valid. + // It remains valid because we "forgot" it with `Box::= into_raw`. + // SAFETY: All pointers are non-null and valid. + unsafe { bindings::rb_replace_node(parent, node_links,= &mut self.root) }; + + // INVARIANT: The node is being returned and the calle= r may free it, however, + // it was removed from the tree. So the invariants sti= ll hold. + return Some(RBTreeNode { + // SAFETY: `this` was a node in the tree, so it is= valid. + node: unsafe { Box::from_raw(this.cast_mut()) }, + }); + } + } + } + + // INVARIANT: We are linking in a new node, which is valid. It rem= ains valid because we + // "forgot" it with `Box::into_raw`. + // SAFETY: All pointers are non-null and valid (`*child_field_of_p= arent` is null, but `child_field_of_parent` is a + // mutable reference). + unsafe { bindings::rb_link_node(node_links, parent, child_field_of= _parent) }; + + // SAFETY: All pointers are valid. `node` has just been inserted i= nto the tree. + unsafe { bindings::rb_insert_color(node_links, &mut self.root) }; + None + } + + /// Returns a node with the given key, if one exists. + fn find(&self, key: &K) -> Option>> { + let mut node =3D self.root.rb_node; + while !node.is_null() { + // SAFETY: By the type invariant of `Self`, all non-null `rb_n= ode` pointers stored in `self` + // point to the links field of `Node` objects. + let this =3D unsafe { container_of!(node, Node, links) }; + // SAFETY: `this` is a non-null node so it is valid by the typ= e invariants. + node =3D match key.cmp(unsafe { &(*this).key }) { + // SAFETY: `node` is a non-null node so it is valid by the= type invariants. + Ordering::Less =3D> unsafe { (*node).rb_left }, + // SAFETY: `node` is a non-null node so it is valid by the= type invariants. + Ordering::Greater =3D> unsafe { (*node).rb_right }, + Ordering::Equal =3D> return NonNull::new(this.cast_mut()), + } + } + None + } + + /// Returns a reference to the value corresponding to the key. + pub fn get(&self, key: &K) -> Option<&V> { + // SAFETY: The `find` return value is a node in the tree, so it is= valid. + self.find(key).map(|node| unsafe { &node.as_ref().value }) + } + + /// Returns a mutable reference to the value corresponding to the key. + pub fn get_mut(&mut self, key: &K) -> Option<&mut V> { + // SAFETY: The `find` return value is a node in the tree, so it is= valid. + self.find(key) + .map(|mut node| unsafe { &mut node.as_mut().value }) + } + + /// Removes the node with the given key from the tree. + /// + /// It returns the node that was removed if one exists, or [`None`] ot= herwise. + fn remove_node(&mut self, key: &K) -> Option> { + let mut node =3D self.find(key)?; + + // SAFETY: The `find` return value is a node in the tree, so it is= valid. + unsafe { bindings::rb_erase(&mut node.as_mut().links, &mut self.ro= ot) }; + + // INVARIANT: The node is being returned and the caller may free i= t, however, it was + // removed from the tree. So the invariants still hold. + Some(RBTreeNode { + // SAFETY: The `find` return value was a node in the tree, so = it is valid. + node: unsafe { Box::from_raw(node.as_ptr()) }, + }) + } + + /// Removes the node with the given key from the tree. + /// + /// It returns the value that was removed if one exists, or [`None`] o= therwise. + pub fn remove(&mut self, key: &K) -> Option { + self.remove_node(key).map(|node| node.node.value) + } +} + +impl Default for RBTree { + fn default() -> Self { + Self::new() + } +} + +impl Drop for RBTree { + fn drop(&mut self) { + // SAFETY: `root` is valid as it's embedded in `self` and we have = a valid `self`. + let mut next =3D unsafe { bindings::rb_first_postorder(&self.root)= }; + + // INVARIANT: The loop invariant is that all tree nodes from `next= ` in postorder are valid. + while !next.is_null() { + // SAFETY: All links fields we create are in a `Node`. + let this =3D unsafe { container_of!(next, Node, links) }; + + // Find out what the next node is before disposing of the curr= ent one. + // SAFETY: `next` and all nodes in postorder are still valid. + next =3D unsafe { bindings::rb_next_postorder(next) }; + + // INVARIANT: This is the destructor, so we break the type inv= ariant during clean-up, + // but it is not observable. The loop invariant is still maint= ained. + + // SAFETY: `this` is valid per the loop invariant. + unsafe { drop(Box::from_raw(this.cast_mut())) }; + } + } +} + +/// A memory reservation for a red-black tree node. +/// +/// +/// It contains the memory needed to hold a node that can be inserted into= a red-black tree. One +/// can be obtained by directly allocating it ([`RBTreeNodeReservation::ne= w`]). +pub struct RBTreeNodeReservation { + node: Box>>, +} + +impl RBTreeNodeReservation { + /// Allocates memory for a node to be eventually initialised and inser= ted into the tree via a + /// call to [`RBTree::insert`]. + pub fn new(flags: Flags) -> Result> { + Ok(RBTreeNodeReservation { + node: as BoxExt<_>>::new_uninit(flags)?, + }) + } +} + +// SAFETY: This doesn't actually contain K or V, and is just a memory allo= cation. Those can always +// be moved across threads. +unsafe impl Send for RBTreeNodeReservation {} + +// SAFETY: This doesn't actually contain K or V, and is just a memory allo= cation. +unsafe impl Sync for RBTreeNodeReservation {} + +impl RBTreeNodeReservation { + /// Initialises a node reservation. + /// + /// It then becomes an [`RBTreeNode`] that can be inserted into a tree. + pub fn into_node(self, key: K, value: V) -> RBTreeNode { + let node =3D Box::write( + self.node, + Node { + key, + value, + links: bindings::rb_node::default(), + }, + ); + RBTreeNode { node } + } +} + +/// A red-black tree node. +/// +/// The node is fully initialised (with key and value) and can be inserted= into a tree without any +/// extra allocations or failure paths. +pub struct RBTreeNode { + node: Box>, +} + +impl RBTreeNode { + /// Allocates and initialises a node that can be inserted into the tre= e via + /// [`RBTree::insert`]. + pub fn new(key: K, value: V, flags: Flags) -> Result>= { + Ok(RBTreeNodeReservation::new(flags)?.into_node(key, value)) + } +} + +// SAFETY: If K and V can be sent across threads, then it's also okay to s= end [`RBTreeNode`] across +// threads. +unsafe impl Send for RBTreeNode {} + +// SAFETY: If K and V can be accessed without synchronization, then it's a= lso okay to access +// [`RBTreeNode`] without synchronization. +unsafe impl Sync for RBTreeNode {} + +struct Node { + links: bindings::rb_node, + key: K, + value: V, +} --=20 2.46.0.184.g6999bdac58-goog From nobody Sat Feb 7 07:10:20 2026 Received: from mail-yb1-f202.google.com (mail-yb1-f202.google.com [209.85.219.202]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 010C91C5789 for ; Fri, 16 Aug 2024 20:48:06 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.219.202 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723841288; cv=none; b=CJpsq3tROl7dOlV7DpWjspMw9mZdconhoq/ZwBlC8itG90yHaf29hEyy4Ao8E09m9eKP4hsTG09O0Pg3v1d2rqlVQRJlLzfp0I70wMKpRb5R7mGi9T3G+g2KZ0EyNQarzJMAmfZ8kLJ2WdY9c5g0mSO6TIEA91v0gWHYkjEZr6Q= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723841288; c=relaxed/simple; bh=prbzF9A7rp/G33IcXNJKm6tZRhmAfexWxJAHcXVXlYc=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=DL4JHz9TZZXSZrP5KlQVeGYFN4e/uGI7Vwpc4DbbhRE3C+iX13fuFKlGTMv8giuqE8SXHCWrOknXih6HQQWDPeDKB4nE/3T0S+174VJH8dCfMKxlFnfBuEIu6uFBUebnVH7oTS1gHZlgEUwVT+C/u+Qg0rfNIUXEkQ1f0d9TQ+s= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com; spf=pass smtp.mailfrom=flex--mattgilbride.bounces.google.com; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b=baI+I4R0; arc=none smtp.client-ip=209.85.219.202 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=flex--mattgilbride.bounces.google.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="baI+I4R0" Received: by mail-yb1-f202.google.com with SMTP id 3f1490d57ef6-e0353b731b8so3926324276.2 for ; Fri, 16 Aug 2024 13:48:06 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1723841286; x=1724446086; darn=vger.kernel.org; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=CYBGbx/uYLeIyT2X3cGbSQ5xZpFImUAaykVOvmQ6VX8=; b=baI+I4R01PsdkegUxkNazl1CABmqY9nnlYaKkd5AvJb3ydYQx7B0SUbJugVj5z6Uu2 +A67UwpDbUGrzioFRPhM8r4iwpSEZjKuoLWxx0++V+sZ6tz18tyFFjwAadQer7QIqMxv QtxptYWb4w4qchF3Me4kDyuDmbd5Usl/M2d+UOGnci6MIRSVr7t3FVRrhXJuKcMmKncW ojUKRgzlLvpr2SlBcSfxvJDaZiHf1bqhf6R6ORK+K/qBtZGYB9yQqovkOEfzUekhP6zb dpdRi4KYFiMAVwlLDZ/GdwOQtrWsjMhsGu2aIVmVDbx3gX2oQUEasVzhNVscAf8UBvdg AuHQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1723841286; x=1724446086; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=CYBGbx/uYLeIyT2X3cGbSQ5xZpFImUAaykVOvmQ6VX8=; b=n0z8CAv9o0BkKNi45bvLIWjIIImRhsNl1WN1FZgGIGT+wI7FHpP3kumORykL6ONPfb 9wactkdAxZFNta6hLQo6w4j153GCdirCnSqNRLIFnJ2Jus/G2PlHOkZvtRcI8F64uO3n I7OQ7o68qU7PH27EVpljJdf71ANZjpS/z2fPlyOa8jBtTejuvXu4lrCxXbR+xXtJFIaU Ehbos2AM+LQN88vXESkPblkOujrygKNqeINrVH3T1SM0rWhuEvjN9lQPvi2DUOe6iSFS vGS1IetYFHS40jy+7FAW8v11rvlj+QPSvCZoTtmLTQ1tDjgtF7ur9ka4UgDDBrmmAQES jeow== X-Forwarded-Encrypted: i=1; AJvYcCUwXve8AgDjhLvGw23NR4VzBV7Dt1fY8Ek8B3E1OC1pt9qJGgZ8GDIO9X49Ax1GG4IbZtd54TLE3Gnpy/nHGVkaYDu9OrGc6pLVQrgK X-Gm-Message-State: AOJu0YzvOAXPLAOiFggahWBK7WWOWqFgxZqJ6B3xlqBSCCufut509Rtg fTwWA6VozkHEdI/5iC2UIYbgcPvINihGknGnaZ4BbtwwvtQdra/yXHI5YUeDcrdOz29UuYk4yWH 7dQq/K+FzELJ/d52XitzEl8lTKA== X-Google-Smtp-Source: AGHT+IFGWGXjPlapIMI+q0beoMNWHOobKuxJEyRVUKqmyxFq7ot/YtLvcJBUC5HMMYGbEzKfcgJGUbQ/06ts1TaSr/A= X-Received: from mattgilbride.c.googlers.com ([fda3:e722:ac3:cc00:2b:7d90:c0a8:2ac5]) (user=mattgilbride job=sendgmr) by 2002:a25:b206:0:b0:e0b:fa7e:8cbe with SMTP id 3f1490d57ef6-e1180fa581fmr5533276.11.1723841285901; Fri, 16 Aug 2024 13:48:05 -0700 (PDT) Date: Fri, 16 Aug 2024 20:48:00 +0000 In-Reply-To: <20240816-b4-rbtree-v9-0-425b442af7e5@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240816-b4-rbtree-v9-0-425b442af7e5@google.com> X-Mailer: b4 0.13.0 Message-ID: <20240816-b4-rbtree-v9-3-425b442af7e5@google.com> Subject: [PATCH v9 3/6] rust: rbtree: add iterator From: Matt Gilbride To: Miguel Ojeda , Alex Gaynor , Wedson Almeida Filho , Boqun Feng , Gary Guo , "=?utf-8?q?Bj=C3=B6rn_Roy_Baron?=" , Benno Lossin , Andreas Hindborg , Alice Ryhl , Greg Kroah-Hartman , "=?utf-8?q?Arve_Hj=C3=B8nnev=C3=A5g?=" , Todd Kjos , Martijn Coenen , Joel Fernandes , Carlos Llamas , Suren Baghdasaryan , Christian Brauner Cc: Rob Landley , Davidlohr Bueso , Michel Lespinasse , rust-for-linux@vger.kernel.org, linux-kernel@vger.kernel.org, Matt Gilbride Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable From: Wedson Almeida Filho - Add Iterator implementation for `RBTree`, allowing iteration over (key, value) pairs in key order. - Add individual `keys()` and `values()` functions to iterate over keys or values alone. - Update doctests to use iteration instead of explicitly getting items. Iteration is needed by the binder driver to enumerate all values in a tree for oneway spam detection [1]. Link: https://lore.kernel.org/rust-for-linux/20231101-rust-binder-v1-17-08b= a9197f637@google.com/ [1] Signed-off-by: Wedson Almeida Filho Reviewed-by: Alice Ryhl Tested-by: Alice Ryhl Reviewed-by: Benno Lossin Reviewed-by: Boqun Feng Signed-off-by: Matt Gilbride --- rust/kernel/rbtree.rs | 130 +++++++++++++++++++++++++++++++++++++++++++---= ---- 1 file changed, 112 insertions(+), 18 deletions(-) diff --git a/rust/kernel/rbtree.rs b/rust/kernel/rbtree.rs index 51c53a25bc7d..29e7a0795266 100644 --- a/rust/kernel/rbtree.rs +++ b/rust/kernel/rbtree.rs @@ -42,14 +42,30 @@ /// assert_eq!(tree.get(&30).unwrap(), &300); /// } /// +/// // Iterate over the nodes we just inserted. +/// { +/// let mut iter =3D tree.iter(); +/// assert_eq!(iter.next().unwrap(), (&10, &100)); +/// assert_eq!(iter.next().unwrap(), (&20, &200)); +/// assert_eq!(iter.next().unwrap(), (&30, &300)); +/// assert!(iter.next().is_none()); +/// } +/// +/// // Print all elements. +/// for (key, value) in &tree { +/// pr_info!("{} =3D {}\n", key, value); +/// } +/// /// // Replace one of the elements. /// tree.try_create_and_insert(10, 1000, flags::GFP_KERNEL)?; /// /// // Check that the tree reflects the replacement. /// { -/// assert_eq!(tree.get(&10).unwrap(), &1000); -/// assert_eq!(tree.get(&20).unwrap(), &200); -/// assert_eq!(tree.get(&30).unwrap(), &300); +/// let mut iter =3D tree.iter(); +/// assert_eq!(iter.next().unwrap(), (&10, &1000)); +/// assert_eq!(iter.next().unwrap(), (&20, &200)); +/// assert_eq!(iter.next().unwrap(), (&30, &300)); +/// assert!(iter.next().is_none()); /// } /// /// // Change the value of one of the elements. @@ -57,9 +73,11 @@ /// /// // Check that the tree reflects the update. /// { -/// assert_eq!(tree.get(&10).unwrap(), &1000); -/// assert_eq!(tree.get(&20).unwrap(), &200); -/// assert_eq!(tree.get(&30).unwrap(), &3000); +/// let mut iter =3D tree.iter(); +/// assert_eq!(iter.next().unwrap(), (&10, &1000)); +/// assert_eq!(iter.next().unwrap(), (&20, &200)); +/// assert_eq!(iter.next().unwrap(), (&30, &3000)); +/// assert!(iter.next().is_none()); /// } /// /// // Remove an element. @@ -67,9 +85,10 @@ /// /// // Check that the tree reflects the removal. /// { -/// assert_eq!(tree.get(&10), None); -/// assert_eq!(tree.get(&20).unwrap(), &200); -/// assert_eq!(tree.get(&30).unwrap(), &3000); +/// let mut iter =3D tree.iter(); +/// assert_eq!(iter.next().unwrap(), (&20, &200)); +/// assert_eq!(iter.next().unwrap(), (&30, &3000)); +/// assert!(iter.next().is_none()); /// } /// /// # Ok::<(), Error>(()) @@ -109,9 +128,11 @@ /// /// // Check the nodes we just inserted. /// { -/// assert_eq!(tree.get(&10).unwrap(), &100); -/// assert_eq!(tree.get(&20).unwrap(), &200); -/// assert_eq!(tree.get(&30).unwrap(), &300); +/// let mut iter =3D tree.iter(); +/// assert_eq!(iter.next().unwrap(), (&10, &100)); +/// assert_eq!(iter.next().unwrap(), (&20, &200)); +/// assert_eq!(iter.next().unwrap(), (&30, &300)); +/// assert!(iter.next().is_none()); /// } /// /// // Remove a node, getting back ownership of it. @@ -119,9 +140,10 @@ /// /// // Check that the tree reflects the removal. /// { -/// assert_eq!(tree.get(&10).unwrap(), &100); -/// assert_eq!(tree.get(&20).unwrap(), &200); -/// assert_eq!(tree.get(&30), None); +/// let mut iter =3D tree.iter(); +/// assert_eq!(iter.next().unwrap(), (&10, &100)); +/// assert_eq!(iter.next().unwrap(), (&20, &200)); +/// assert!(iter.next().is_none()); /// } /// /// // Create a preallocated reservation that we can re-use later. @@ -133,9 +155,11 @@ /// /// // Check that the tree reflect the new insertion. /// { -/// assert_eq!(tree.get(&10).unwrap(), &100); -/// assert_eq!(tree.get(&15).unwrap(), &150); -/// assert_eq!(tree.get(&20).unwrap(), &200); +/// let mut iter =3D tree.iter(); +/// assert_eq!(iter.next().unwrap(), (&10, &100)); +/// assert_eq!(iter.next().unwrap(), (&15, &150)); +/// assert_eq!(iter.next().unwrap(), (&20, &200)); +/// assert!(iter.next().is_none()); /// } /// /// # Ok::<(), Error>(()) @@ -167,6 +191,26 @@ pub fn new() -> Self { _p: PhantomData, } } + + /// Returns an iterator over the tree nodes, sorted by key. + pub fn iter(&self) -> Iter<'_, K, V> { + // INVARIANT: `bindings::rb_first` returns a valid pointer to a tr= ee node given a valid pointer to a tree root. + Iter { + _tree: PhantomData, + // SAFETY: `self.root` is a valid pointer to the tree root. + next: unsafe { bindings::rb_first(&self.root) }, + } + } + + /// Returns an iterator over the keys of the nodes in the tree, in sor= ted order. + pub fn keys(&self) -> impl Iterator { + self.iter().map(|(k, _)| k) + } + + /// Returns an iterator over the values of the nodes in the tree, sort= ed by key. + pub fn values(&self) -> impl Iterator { + self.iter().map(|(_, v)| v) + } } =20 impl RBTree @@ -358,6 +402,56 @@ fn drop(&mut self) { } } =20 +impl<'a, K, V> IntoIterator for &'a RBTree { + type Item =3D (&'a K, &'a V); + type IntoIter =3D Iter<'a, K, V>; + + fn into_iter(self) -> Self::IntoIter { + self.iter() + } +} + +/// An iterator over the nodes of a [`RBTree`]. +/// +/// Instances are created by calling [`RBTree::iter`]. +/// +/// # Invariants +/// - `self.next` is a valid pointer. +/// - `self.next` points to a node stored inside of a valid `RBTree`. +pub struct Iter<'a, K, V> { + _tree: PhantomData<&'a RBTree>, + next: *mut bindings::rb_node, +} + +// SAFETY: The [`Iter`] gives out immutable references to K and V, so it h= as the same +// thread safety requirements as immutable references. +unsafe impl<'a, K: Sync, V: Sync> Send for Iter<'a, K, V> {} + +// SAFETY: The [`Iter`] gives out immutable references to K and V, so it h= as the same +// thread safety requirements as immutable references. +unsafe impl<'a, K: Sync, V: Sync> Sync for Iter<'a, K, V> {} + +impl<'a, K, V> Iterator for Iter<'a, K, V> { + type Item =3D (&'a K, &'a V); + + fn next(&mut self) -> Option { + if self.next.is_null() { + return None; + } + + // SAFETY: By the type invariant of `Iter`, `self.next` is a valid= node in an `RBTree`, + // and by the type invariant of `RBTree`, all nodes point to the l= inks field of `Node` objects. + let cur =3D unsafe { container_of!(self.next, Node, links) }; + + // SAFETY: `self.next` is a valid tree node by the type invariants. + self.next =3D unsafe { bindings::rb_next(self.next) }; + + // SAFETY: By the same reasoning above, it is safe to dereference = the node. Additionally, + // it is ok to return a reference to members because the iterator = must outlive it. + Some(unsafe { (&(*cur).key, &(*cur).value) }) + } +} + /// A memory reservation for a red-black tree node. /// /// --=20 2.46.0.184.g6999bdac58-goog From nobody Sat Feb 7 07:10:20 2026 Received: from mail-yb1-f202.google.com (mail-yb1-f202.google.com [209.85.219.202]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id D1D6F1C57AA for ; Fri, 16 Aug 2024 20:48:07 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.219.202 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723841289; cv=none; b=YnAjxTcPR//0MD+WDybdTeIRZHaCB8DAPr6v+Wv7iBUKiZUrnkVPY/ehQFLon6OEcoMdRKyylS/rKPJquCWbm/9f98F/H8mZdV+cT5ZqfqQHqV1YxXTvYT5F6s2wwRK5gW3/mx4Tfiu73vgVt40vQdH0hD/HDFtieidFSswEM3g= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723841289; c=relaxed/simple; bh=bY3uwhAdqdUeCxk8YovfoOJpj6gAoBiYhX2fhlfpqY4=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=THjFUTcaGUX3TUoioAlZrSZBV6jQWEHTIDykczL7CALT8jiWOvfyBAszNF1sxrUp0kgPoxZNj4EefvUgCb5dCouzwkxUE0rftqfLILSkXZwVXYFFXuXWEuwTGXo8UwkvfWLlXwKa3s20WzYsILTIcN1jNr7VP3OF5P4p1gpa4GY= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com; spf=pass smtp.mailfrom=flex--mattgilbride.bounces.google.com; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b=V6LYW95j; arc=none smtp.client-ip=209.85.219.202 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=flex--mattgilbride.bounces.google.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="V6LYW95j" Received: by mail-yb1-f202.google.com with SMTP id 3f1490d57ef6-e1173581259so3041087276.2 for ; Fri, 16 Aug 2024 13:48:07 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1723841287; x=1724446087; darn=vger.kernel.org; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=85UzCaGowEZwuxuV5kMmpUWk+b/7cJAuTQ/iw0RGtwQ=; b=V6LYW95jwciTJjFDvXI829RIb4zn6+DUA+/w43S/u0tv+oEzk72lU2wbDF2tWBd28J i9hQyNZl3mB0jmLIeQfbdWND7Yi5bjeXj/CuijlvcefT/DIIvWS1zb3Csgdy8hYQXD5I 054e2vZJs448l985N2hn7tSwycNZ9D6Fvm6vH61WnS7g1Jl03oWr67I+5yEFNhj8eDeE k7iGvUJX61AP/6q7AkA0rJLrQRjXpwfArhxDOs6J8htlgcnXuR6hLb00asyRnKmn6vOw W/TaAlL5A/1kq3tobXNeJibexGxfKP1wkyuLGNYtRCpIl7VQNoG+1zgeFlEhdC9GP2KX 1lhA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1723841287; x=1724446087; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=85UzCaGowEZwuxuV5kMmpUWk+b/7cJAuTQ/iw0RGtwQ=; b=RxPcSuQwwJwQDqaYUkflG89j68SDxuFdsLN0fYYhaVgi/SjZkqsDK74b2dPd66k5/0 mfqGDNSbUpY7JzjXXZXj9u7q/3J4lF0VjjTFAn0zXzGCTWBkwP3oXcFJvFHo7fICvmPt ymwKH61syGk3rK0Pgq3h6CMHfH1StHNf0Z/lddmMuZVcl7cs6K+6xa+jiPF8Kg7xw7Y2 fr331US9SV8HBKDf2RF8Np0TqnDKtNCCeuwb5P+1Cxw8zNHukj9aQ2ea5SK+CrtrG8bI CuUrZLUPVVhI5K8lSLK1hQe9tA0BnMqgWc0o2n0NbpU3X/yI2cBoAaAc1e1WQzFe23Ej nYZg== X-Forwarded-Encrypted: i=1; AJvYcCUIJ1fl39Mqoa06aEcqly4Mf7UXGEdKgiF/pYDyCK17HOf/NrI5jZHg6xVfkAthS/m7B9X5ey30eQHttCCt1fj2+TIzXWYTnpCJoLXj X-Gm-Message-State: AOJu0YxC7TpQSL6s1QvS2KVMVO4qJjNZ/ub53Nt4JWzQWpCo1+thM2F5 q2YOkQRrOe6BjkvHVpDZs0q7aU95T8FIjb4MP1VbZaRxuVJxJAQ8DkHBfEvwWmEUW9I94W83tRv owKBtrDfix/g7TB5TeMrxFocgTQ== X-Google-Smtp-Source: AGHT+IEpVi+7weJZuzse+CvCW18k10JcXLaoNK+bFag9nfLLoD0F+VpBnt8nL67pEI1q2tcnpiQNdaMuixBwtV3YY3M= X-Received: from mattgilbride.c.googlers.com ([fda3:e722:ac3:cc00:2b:7d90:c0a8:2ac5]) (user=mattgilbride job=sendgmr) by 2002:a5b:b92:0:b0:e0b:4dd5:3995 with SMTP id 3f1490d57ef6-e1180f69be9mr6247276.7.1723841286811; Fri, 16 Aug 2024 13:48:06 -0700 (PDT) Date: Fri, 16 Aug 2024 20:48:01 +0000 In-Reply-To: <20240816-b4-rbtree-v9-0-425b442af7e5@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240816-b4-rbtree-v9-0-425b442af7e5@google.com> X-Mailer: b4 0.13.0 Message-ID: <20240816-b4-rbtree-v9-4-425b442af7e5@google.com> Subject: [PATCH v9 4/6] rust: rbtree: add mutable iterator From: Matt Gilbride To: Miguel Ojeda , Alex Gaynor , Wedson Almeida Filho , Boqun Feng , Gary Guo , "=?utf-8?q?Bj=C3=B6rn_Roy_Baron?=" , Benno Lossin , Andreas Hindborg , Alice Ryhl , Greg Kroah-Hartman , "=?utf-8?q?Arve_Hj=C3=B8nnev=C3=A5g?=" , Todd Kjos , Martijn Coenen , Joel Fernandes , Carlos Llamas , Suren Baghdasaryan , Christian Brauner Cc: Rob Landley , Davidlohr Bueso , Michel Lespinasse , rust-for-linux@vger.kernel.org, linux-kernel@vger.kernel.org, Matt Gilbride Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable From: Wedson Almeida Filho Add mutable Iterator implementation for `RBTree`, allowing iteration over (key, value) pairs in key order. Only values are mutable, as mutating keys implies modifying a node's position in the tree. Mutable iteration is used by the binder driver during shutdown to clean up the tree maintained by the "range allocator" [1]. Link: https://lore.kernel.org/rust-for-linux/20231101-rust-binder-v1-6-08ba= 9197f637@google.com/ [1] Signed-off-by: Wedson Almeida Filho Reviewed-by: Alice Ryhl Tested-by: Alice Ryhl Reviewed-by: Boqun Feng Signed-off-by: Matt Gilbride --- rust/kernel/rbtree.rs | 104 +++++++++++++++++++++++++++++++++++++++++++---= ---- 1 file changed, 90 insertions(+), 14 deletions(-) diff --git a/rust/kernel/rbtree.rs b/rust/kernel/rbtree.rs index 29e7a0795266..6c9a8f0a00e6 100644 --- a/rust/kernel/rbtree.rs +++ b/rust/kernel/rbtree.rs @@ -12,7 +12,7 @@ cmp::{Ord, Ordering}, marker::PhantomData, mem::MaybeUninit, - ptr::{addr_of_mut, NonNull}, + ptr::{addr_of_mut, from_mut, NonNull}, }; =20 /// A red-black tree with owned nodes. @@ -194,11 +194,31 @@ pub fn new() -> Self { =20 /// Returns an iterator over the tree nodes, sorted by key. pub fn iter(&self) -> Iter<'_, K, V> { - // INVARIANT: `bindings::rb_first` returns a valid pointer to a tr= ee node given a valid pointer to a tree root. Iter { _tree: PhantomData, - // SAFETY: `self.root` is a valid pointer to the tree root. - next: unsafe { bindings::rb_first(&self.root) }, + // INVARIANT: + // - `self.root` is a valid pointer to a tree root. + // - `bindings::rb_first` produces a valid pointer to a node= given `root` is valid. + iter_raw: IterRaw { + // SAFETY: by the invariants, all pointers are valid. + next: unsafe { bindings::rb_first(&self.root) }, + _phantom: PhantomData, + }, + } + } + + /// Returns a mutable iterator over the tree nodes, sorted by key. + pub fn iter_mut(&mut self) -> IterMut<'_, K, V> { + IterMut { + _tree: PhantomData, + // INVARIANT: + // - `self.root` is a valid pointer to a tree root. + // - `bindings::rb_first` produces a valid pointer to a node= given `root` is valid. + iter_raw: IterRaw { + // SAFETY: by the invariants, all pointers are valid. + next: unsafe { bindings::rb_first(from_mut(&mut self.root)= ) }, + _phantom: PhantomData, + }, } } =20 @@ -211,6 +231,11 @@ pub fn keys(&self) -> impl Iterator { pub fn values(&self) -> impl Iterator { self.iter().map(|(_, v)| v) } + + /// Returns a mutable iterator over the values of the nodes in the tre= e, sorted by key. + pub fn values_mut(&mut self) -> impl Iterator { + self.iter_mut().map(|(_, v)| v) + } } =20 impl RBTree @@ -414,13 +439,9 @@ fn into_iter(self) -> Self::IntoIter { /// An iterator over the nodes of a [`RBTree`]. /// /// Instances are created by calling [`RBTree::iter`]. -/// -/// # Invariants -/// - `self.next` is a valid pointer. -/// - `self.next` points to a node stored inside of a valid `RBTree`. pub struct Iter<'a, K, V> { _tree: PhantomData<&'a RBTree>, - next: *mut bindings::rb_node, + iter_raw: IterRaw, } =20 // SAFETY: The [`Iter`] gives out immutable references to K and V, so it h= as the same @@ -434,21 +455,76 @@ unsafe impl<'a, K: Sync, V: Sync> Sync for Iter<'a, K= , V> {} impl<'a, K, V> Iterator for Iter<'a, K, V> { type Item =3D (&'a K, &'a V); =20 + fn next(&mut self) -> Option { + // SAFETY: Due to `self._tree`, `k` and `v` are valid for the life= time of `'a`. + self.iter_raw.next().map(|(k, v)| unsafe { (&*k, &*v) }) + } +} + +impl<'a, K, V> IntoIterator for &'a mut RBTree { + type Item =3D (&'a K, &'a mut V); + type IntoIter =3D IterMut<'a, K, V>; + + fn into_iter(self) -> Self::IntoIter { + self.iter_mut() + } +} + +/// A mutable iterator over the nodes of a [`RBTree`]. +/// +/// Instances are created by calling [`RBTree::iter_mut`]. +pub struct IterMut<'a, K, V> { + _tree: PhantomData<&'a mut RBTree>, + iter_raw: IterRaw, +} + +// SAFETY: The [`IterMut`] has exclusive access to both `K` and `V`, so it= is sufficient to require them to be `Send`. +// The iterator only gives out immutable references to the keys, but since= the iterator has excusive access to those same +// keys, `Send` is sufficient. `Sync` would be okay, but it is more restri= ctive to the user. +unsafe impl<'a, K: Send, V: Send> Send for IterMut<'a, K, V> {} + +// SAFETY: The [`IterMut`] gives out immutable references to K and mutable= references to V, so it has the same +// thread safety requirements as mutable references. +unsafe impl<'a, K: Sync, V: Sync> Sync for IterMut<'a, K, V> {} + +impl<'a, K, V> Iterator for IterMut<'a, K, V> { + type Item =3D (&'a K, &'a mut V); + + fn next(&mut self) -> Option { + self.iter_raw.next().map(|(k, v)| + // SAFETY: Due to `&mut self`, we have exclusive access to `k`= and `v`, for the lifetime of `'a`. + unsafe { (&*k, &mut *v) }) + } +} + +/// A raw iterator over the nodes of a [`RBTree`]. +/// +/// # Invariants +/// - `self.next` is a valid pointer. +/// - `self.next` points to a node stored inside of a valid `RBTree`. +struct IterRaw { + next: *mut bindings::rb_node, + _phantom: PhantomData (K, V)>, +} + +impl Iterator for IterRaw { + type Item =3D (*mut K, *mut V); + fn next(&mut self) -> Option { if self.next.is_null() { return None; } =20 - // SAFETY: By the type invariant of `Iter`, `self.next` is a valid= node in an `RBTree`, + // SAFETY: By the type invariant of `IterRaw`, `self.next` is a va= lid node in an `RBTree`, // and by the type invariant of `RBTree`, all nodes point to the l= inks field of `Node` objects. - let cur =3D unsafe { container_of!(self.next, Node, links) }; + let cur: *mut Node =3D + unsafe { container_of!(self.next, Node, links) }.cast_mu= t(); =20 // SAFETY: `self.next` is a valid tree node by the type invariants. self.next =3D unsafe { bindings::rb_next(self.next) }; =20 - // SAFETY: By the same reasoning above, it is safe to dereference = the node. Additionally, - // it is ok to return a reference to members because the iterator = must outlive it. - Some(unsafe { (&(*cur).key, &(*cur).value) }) + // SAFETY: By the same reasoning above, it is safe to dereference = the node. + Some(unsafe { (addr_of_mut!((*cur).key), addr_of_mut!((*cur).value= )) }) } } =20 --=20 2.46.0.184.g6999bdac58-goog From nobody Sat Feb 7 07:10:20 2026 Received: from mail-yb1-f201.google.com (mail-yb1-f201.google.com [209.85.219.201]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 03FD71C689A for ; Fri, 16 Aug 2024 20:48:08 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.219.201 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723841291; cv=none; b=twlRaPs0zBuEqTnjYo7Fye8Al4lP+k4Tfh3DIRq/Ay+7HQcwEhivm7Rervo49gp/IuCigPPhxSkKQMWcNllG19SvjNLG0YpQl3QfeZ1WPANoFyGHZiaCVJ0bKExIePqkjQAp2cXNnvC8aFbh9g2S5VD6hDrxHXDcnnfZrGJ378c= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723841291; c=relaxed/simple; bh=QJWOJkpl6KXRAe09TwBaSwnXuTWF1R+OnUVxqnwmS+Y=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=oKpltuigXj1EoDEuk9a0sSJgVaT+hCvC5y2lW1Arz5TEAlQlpW+RNyd5GZ98W9XhAn0mq8tvy8H4301hj4tX+HliPo2ahJ3kkLHH9LsXmhk+C9YCsDwPnrLvA8BzqHKvGllmWtx9SL2r+7+8L0jQt0Os2/+lTErCX49P2uT9398= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com; spf=pass smtp.mailfrom=flex--mattgilbride.bounces.google.com; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b=CxMeDWk6; arc=none smtp.client-ip=209.85.219.201 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=flex--mattgilbride.bounces.google.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="CxMeDWk6" Received: by mail-yb1-f201.google.com with SMTP id 3f1490d57ef6-e1159fb1669so3698482276.2 for ; Fri, 16 Aug 2024 13:48:08 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1723841288; x=1724446088; darn=vger.kernel.org; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=9Ergg2PDCx3y6F+ITkJKGedswdbKauEfjSNh9WRyxoQ=; b=CxMeDWk6GIUReCiChj3IhnvgDQDOIP8VFknE4zlQZeorZ0SJ05OiLrngQKUb5e5ckb ONU1tl+difKIEi7lG8OAGnTnvtEj03o7FSwjRshW2tumjDwGhCV++j8rKZdqDVWrjcg7 YWRYQGrYCQaUGSfRiDHnu9UX38yxcgPLjprmpFlUEh591USla/p2kd6xc7FePpzy30VM LgN8FQk3V1fVboTvSHpmDVbz0+TzDKh3Nj5MQbKKg7rdJ1D0/dzmmkSdAUiFesxTzRcX LcVF6SdDvHPqWP4NmhHJiQEkRQio/TYAmEtKTlQ9VoyzzQKQFywlvPReoA2PGNSsQqBE mPjw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1723841288; x=1724446088; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=9Ergg2PDCx3y6F+ITkJKGedswdbKauEfjSNh9WRyxoQ=; b=NMgZdXm9UNzQ++ZzEqX0m+CGDCWUYWjzrhA1z2lV7+Cr5GkO6fymK5bvHj7l7dA5n4 czqc6WFpvnquXeR3xN2AVK5zj4zxSAfLnB7E+FsSfe30OzKM7Pmj7vdiaWt2oBiGPPK9 CkiuTx2Ul2s+TEaAaXgJSdnJCl74v3UQ+0b4JoXHAkwpbe/n8Gv/AEQODqw0baQtMZQl 6+zxziiqAWHfpuXgARU98oqULvwU7EEFoJVz6Rcy+ufOi6MgBtQ3mFvUD/XwVEqbz0Yt +wBP0q4HP1c+SuOrVICYwEiCjFS3E/cn93lfAvuMn4/jBjkG+Uv9gT4dgT5GWB4cqlY0 Jfmw== X-Forwarded-Encrypted: i=1; AJvYcCWQggqDyUpyAUL13gTjhobkwoNJIAzhC6dIPEyzA0jzxRczCUPpf6LZOHTj80M0pYSjQfQ83+yq2+A3anscfknPnM6U7BQeEXhjRUH5 X-Gm-Message-State: AOJu0Yy9kLrX3/2/M64a0EtC1vbbG6dtM2yCyK8/hGCUZYlaAWiSv5Vb wRfa6NJaVLO8a4ywzBlroVmdCRrZq+8gl1W6bGcmtfJzN2MglY7b1dwbMxKHlDTWULDPW3CYALx 0eNGv3kWqp7OkawzVGvzGMkscTA== X-Google-Smtp-Source: AGHT+IHenAAP2harMW6zipnTUP9tnim/e+ps7twxCpeMqDJOrbuHJnV4oHjxAPHYzlg6qk2KbLeqB3pcUOf52Vu+ot8= X-Received: from mattgilbride.c.googlers.com ([fda3:e722:ac3:cc00:2b:7d90:c0a8:2ac5]) (user=mattgilbride job=sendgmr) by 2002:a25:8609:0:b0:e0e:cf00:d70b with SMTP id 3f1490d57ef6-e1180e4a7edmr6786276.2.1723841287813; Fri, 16 Aug 2024 13:48:07 -0700 (PDT) Date: Fri, 16 Aug 2024 20:48:02 +0000 In-Reply-To: <20240816-b4-rbtree-v9-0-425b442af7e5@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240816-b4-rbtree-v9-0-425b442af7e5@google.com> X-Mailer: b4 0.13.0 Message-ID: <20240816-b4-rbtree-v9-5-425b442af7e5@google.com> Subject: [PATCH v9 5/6] rust: rbtree: add cursor From: Matt Gilbride To: Miguel Ojeda , Alex Gaynor , Wedson Almeida Filho , Boqun Feng , Gary Guo , "=?utf-8?q?Bj=C3=B6rn_Roy_Baron?=" , Benno Lossin , Andreas Hindborg , Alice Ryhl , Greg Kroah-Hartman , "=?utf-8?q?Arve_Hj=C3=B8nnev=C3=A5g?=" , Todd Kjos , Martijn Coenen , Joel Fernandes , Carlos Llamas , Suren Baghdasaryan , Christian Brauner Cc: Rob Landley , Davidlohr Bueso , Michel Lespinasse , rust-for-linux@vger.kernel.org, linux-kernel@vger.kernel.org, Matt Gilbride Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Add a cursor interface to `RBTree`, supporting the following use cases: - Inspect the current node pointed to by the cursor, inspect/move to it's neighbors in sort order (bidirectionally). - Mutate the tree itself by removing the current node pointed to by the cursor, or one of its neighbors. Add functions to obtain a cursor to the tree by key: - The node with the smallest key - The node with the largest key - The node matching the given key, or the one with the next larger key The cursor abstraction is needed by the binder driver to efficiently search for nodes and (conditionally) modify them, as well as their neighbors [1]. Link: https://lore.kernel.org/rust-for-linux/20231101-rust-binder-v1-6-08ba= 9197f637@google.com/ [1] Co-developed-by: Alice Ryhl Signed-off-by: Alice Ryhl Reviewed-by: Alice Ryhl Tested-by: Alice Ryhl Reviewed-by: Boqun Feng Signed-off-by: Matt Gilbride --- rust/kernel/rbtree.rs | 541 ++++++++++++++++++++++++++++++++++++++++++++++= ++++ 1 file changed, 541 insertions(+) diff --git a/rust/kernel/rbtree.rs b/rust/kernel/rbtree.rs index 6c9a8f0a00e6..754af0db86b5 100644 --- a/rust/kernel/rbtree.rs +++ b/rust/kernel/rbtree.rs @@ -236,6 +236,40 @@ pub fn values(&self) -> impl Iterator { pub fn values_mut(&mut self) -> impl Iterator { self.iter_mut().map(|(_, v)| v) } + + /// Returns a cursor over the tree nodes, starting with the smallest k= ey. + pub fn cursor_front(&mut self) -> Option> { + let root =3D addr_of_mut!(self.root); + // SAFETY: `self.root` is always a valid root node + let current =3D unsafe { bindings::rb_first(root) }; + NonNull::new(current).map(|current| { + // INVARIANT: + // - `current` is a valid node in the [`RBTree`] pointed to by= `self`. + // - Due to the type signature of this function, the returned = [`Cursor`] + // borrows mutably from `self`. + Cursor { + current, + tree: self, + } + }) + } + + /// Returns a cursor over the tree nodes, starting with the largest ke= y. + pub fn cursor_back(&mut self) -> Option> { + let root =3D addr_of_mut!(self.root); + // SAFETY: `self.root` is always a valid root node + let current =3D unsafe { bindings::rb_last(root) }; + NonNull::new(current).map(|current| { + // INVARIANT: + // - `current` is a valid node in the [`RBTree`] pointed to by= `self`. + // - Due to the type signature of this function, the returned = [`Cursor`] + // borrows mutably from `self`. + Cursor { + current, + tree: self, + } + }) + } } =20 impl RBTree @@ -396,6 +430,75 @@ fn remove_node(&mut self, key: &K) -> Option> { pub fn remove(&mut self, key: &K) -> Option { self.remove_node(key).map(|node| node.node.value) } + + /// Returns a cursor over the tree nodes based on the given key. + /// + /// If the given key exists, the cursor starts there. + /// Otherwise it starts with the first larger key in sort order. + /// If there is no larger key, it returns [`None`]. + pub fn cursor_lower_bound(&mut self, key: &K) -> Option> + where + K: Ord, + { + let mut node =3D self.root.rb_node; + let mut best_match: Option>> =3D None; + while !node.is_null() { + // SAFETY: By the type invariant of `Self`, all non-null `rb_n= ode` pointers stored in `self` + // point to the links field of `Node` objects. + let this =3D unsafe { container_of!(node, Node, links) }= .cast_mut(); + // SAFETY: `this` is a non-null node so it is valid by the typ= e invariants. + let this_key =3D unsafe { &(*this).key }; + // SAFETY: `node` is a non-null node so it is valid by the typ= e invariants. + let left_child =3D unsafe { (*node).rb_left }; + // SAFETY: `node` is a non-null node so it is valid by the typ= e invariants. + let right_child =3D unsafe { (*node).rb_right }; + if key =3D=3D this_key { + return NonNull::new(node).map(|current| { + // INVARIANT: + // - `node` is a valid node in the [`RBTree`] pointed = to by `self`. + // - Due to the type signature of this function, the r= eturned [`Cursor`] + // borrows mutably from `self`. + Cursor { + current, + tree: self, + } + }); + } else { + node =3D if key > this_key { + right_child + } else { + let is_better_match =3D match best_match { + None =3D> true, + Some(best) =3D> { + // SAFETY: `best` is a non-null node so it is = valid by the type invariants. + let best_key =3D unsafe { &(*best.as_ptr()).ke= y }; + best_key > this_key + } + }; + if is_better_match { + best_match =3D NonNull::new(this); + } + left_child + }; + } + } + + let best =3D best_match?; + + // SAFETY: `best` is a non-null node so it is valid by the type in= variants. + let links =3D unsafe { addr_of_mut!((*best.as_ptr()).links) }; + + NonNull::new(links).map(|current| { + // INVARIANT: + // - `current` is a valid node in the [`RBTree`] pointed to by= `self`. + // - Due to the type signature of this function, the returned = [`Cursor`] + // borrows mutably from `self`. + Cursor { + current, + tree: self, + } + }) + } } =20 impl Default for RBTree { @@ -427,6 +530,439 @@ fn drop(&mut self) { } } =20 +/// A bidirectional cursor over the tree nodes, sorted by key. +/// +/// # Examples +/// +/// In the following example, we obtain a cursor to the first element in t= he tree. +/// The cursor allows us to iterate bidirectionally over key/value pairs i= n the tree. +/// +/// ``` +/// use kernel::{alloc::flags, rbtree::RBTree}; +/// +/// // Create a new tree. +/// let mut tree =3D RBTree::new(); +/// +/// // Insert three elements. +/// tree.try_create_and_insert(10, 100, flags::GFP_KERNEL)?; +/// tree.try_create_and_insert(20, 200, flags::GFP_KERNEL)?; +/// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?; +/// +/// // Get a cursor to the first element. +/// let mut cursor =3D tree.cursor_front().unwrap(); +/// let mut current =3D cursor.current(); +/// assert_eq!(current, (&10, &100)); +/// +/// // Move the cursor, updating it to the 2nd element. +/// cursor =3D cursor.move_next().unwrap(); +/// current =3D cursor.current(); +/// assert_eq!(current, (&20, &200)); +/// +/// // Peek at the next element without impacting the cursor. +/// let next =3D cursor.peek_next().unwrap(); +/// assert_eq!(next, (&30, &300)); +/// current =3D cursor.current(); +/// assert_eq!(current, (&20, &200)); +/// +/// // Moving past the last element causes the cursor to return [`None`]. +/// cursor =3D cursor.move_next().unwrap(); +/// current =3D cursor.current(); +/// assert_eq!(current, (&30, &300)); +/// let cursor =3D cursor.move_next(); +/// assert!(cursor.is_none()); +/// +/// # Ok::<(), Error>(()) +/// ``` +/// +/// A cursor can also be obtained at the last element in the tree. +/// +/// ``` +/// use kernel::{alloc::flags, rbtree::RBTree}; +/// +/// // Create a new tree. +/// let mut tree =3D RBTree::new(); +/// +/// // Insert three elements. +/// tree.try_create_and_insert(10, 100, flags::GFP_KERNEL)?; +/// tree.try_create_and_insert(20, 200, flags::GFP_KERNEL)?; +/// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?; +/// +/// let mut cursor =3D tree.cursor_back().unwrap(); +/// let current =3D cursor.current(); +/// assert_eq!(current, (&30, &300)); +/// +/// # Ok::<(), Error>(()) +/// ``` +/// +/// Obtaining a cursor returns [`None`] if the tree is empty. +/// +/// ``` +/// use kernel::rbtree::RBTree; +/// +/// let mut tree: RBTree =3D RBTree::new(); +/// assert!(tree.cursor_front().is_none()); +/// +/// # Ok::<(), Error>(()) +/// ``` +/// +/// [`RBTree::cursor_lower_bound`] can be used to start at an arbitrary no= de in the tree. +/// +/// ``` +/// use kernel::{alloc::flags, rbtree::RBTree}; +/// +/// // Create a new tree. +/// let mut tree =3D RBTree::new(); +/// +/// // Insert five elements. +/// tree.try_create_and_insert(10, 100, flags::GFP_KERNEL)?; +/// tree.try_create_and_insert(20, 200, flags::GFP_KERNEL)?; +/// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?; +/// tree.try_create_and_insert(40, 400, flags::GFP_KERNEL)?; +/// tree.try_create_and_insert(50, 500, flags::GFP_KERNEL)?; +/// +/// // If the provided key exists, a cursor to that key is returned. +/// let cursor =3D tree.cursor_lower_bound(&20).unwrap(); +/// let current =3D cursor.current(); +/// assert_eq!(current, (&20, &200)); +/// +/// // If the provided key doesn't exist, a cursor to the first larger ele= ment in sort order is returned. +/// let cursor =3D tree.cursor_lower_bound(&25).unwrap(); +/// let current =3D cursor.current(); +/// assert_eq!(current, (&30, &300)); +/// +/// // If there is no larger key, [`None`] is returned. +/// let cursor =3D tree.cursor_lower_bound(&55); +/// assert!(cursor.is_none()); +/// +/// # Ok::<(), Error>(()) +/// ``` +/// +/// The cursor allows mutation of values in the tree. +/// +/// ``` +/// use kernel::{alloc::flags, rbtree::RBTree}; +/// +/// // Create a new tree. +/// let mut tree =3D RBTree::new(); +/// +/// // Insert three elements. +/// tree.try_create_and_insert(10, 100, flags::GFP_KERNEL)?; +/// tree.try_create_and_insert(20, 200, flags::GFP_KERNEL)?; +/// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?; +/// +/// // Retrieve a cursor. +/// let mut cursor =3D tree.cursor_front().unwrap(); +/// +/// // Get a mutable reference to the current value. +/// let (k, v) =3D cursor.current_mut(); +/// *v =3D 1000; +/// +/// // The updated value is reflected in the tree. +/// let updated =3D tree.get(&10).unwrap(); +/// assert_eq!(updated, &1000); +/// +/// # Ok::<(), Error>(()) +/// ``` +/// +/// It also allows node removal. The following examples demonstrate the be= havior of removing the current node. +/// +/// ``` +/// use kernel::{alloc::flags, rbtree::RBTree}; +/// +/// // Create a new tree. +/// let mut tree =3D RBTree::new(); +/// +/// // Insert three elements. +/// tree.try_create_and_insert(10, 100, flags::GFP_KERNEL)?; +/// tree.try_create_and_insert(20, 200, flags::GFP_KERNEL)?; +/// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?; +/// +/// // Remove the first element. +/// let mut cursor =3D tree.cursor_front().unwrap(); +/// let mut current =3D cursor.current(); +/// assert_eq!(current, (&10, &100)); +/// cursor =3D cursor.remove_current().0.unwrap(); +/// +/// // If a node exists after the current element, it is returned. +/// current =3D cursor.current(); +/// assert_eq!(current, (&20, &200)); +/// +/// // Get a cursor to the last element, and remove it. +/// cursor =3D tree.cursor_back().unwrap(); +/// current =3D cursor.current(); +/// assert_eq!(current, (&30, &300)); +/// +/// // Since there is no next node, the previous node is returned. +/// cursor =3D cursor.remove_current().0.unwrap(); +/// current =3D cursor.current(); +/// assert_eq!(current, (&20, &200)); +/// +/// // Removing the last element in the tree returns [`None`]. +/// assert!(cursor.remove_current().0.is_none()); +/// +/// # Ok::<(), Error>(()) +/// ``` +/// +/// Nodes adjacent to the current node can also be removed. +/// +/// ``` +/// use kernel::{alloc::flags, rbtree::RBTree}; +/// +/// // Create a new tree. +/// let mut tree =3D RBTree::new(); +/// +/// // Insert three elements. +/// tree.try_create_and_insert(10, 100, flags::GFP_KERNEL)?; +/// tree.try_create_and_insert(20, 200, flags::GFP_KERNEL)?; +/// tree.try_create_and_insert(30, 300, flags::GFP_KERNEL)?; +/// +/// // Get a cursor to the first element. +/// let mut cursor =3D tree.cursor_front().unwrap(); +/// let mut current =3D cursor.current(); +/// assert_eq!(current, (&10, &100)); +/// +/// // Calling `remove_prev` from the first element returns [`None`]. +/// assert!(cursor.remove_prev().is_none()); +/// +/// // Get a cursor to the last element. +/// cursor =3D tree.cursor_back().unwrap(); +/// current =3D cursor.current(); +/// assert_eq!(current, (&30, &300)); +/// +/// // Calling `remove_prev` removes and returns the middle element. +/// assert_eq!(cursor.remove_prev().unwrap().to_key_value(), (20, 200)); +/// +/// // Calling `remove_next` from the last element returns [`None`]. +/// assert!(cursor.remove_next().is_none()); +/// +/// // Move to the first element +/// cursor =3D cursor.move_prev().unwrap(); +/// current =3D cursor.current(); +/// assert_eq!(current, (&10, &100)); +/// +/// // Calling `remove_next` removes and returns the last element. +/// assert_eq!(cursor.remove_next().unwrap().to_key_value(), (30, 300)); +/// +/// # Ok::<(), Error>(()) +/// +/// ``` +/// +/// # Invariants +/// - `current` points to a node that is in the same [`RBTree`] as `tree`. +pub struct Cursor<'a, K, V> { + tree: &'a mut RBTree, + current: NonNull, +} + +// SAFETY: The [`Cursor`] has exclusive access to both `K` and `V`, so it = is sufficient to require them to be `Send`. +// The cursor only gives out immutable references to the keys, but since i= t has excusive access to those same +// keys, `Send` is sufficient. `Sync` would be okay, but it is more restri= ctive to the user. +unsafe impl<'a, K: Send, V: Send> Send for Cursor<'a, K, V> {} + +// SAFETY: The [`Cursor`] gives out immutable references to K and mutable = references to V, +// so it has the same thread safety requirements as mutable references. +unsafe impl<'a, K: Sync, V: Sync> Sync for Cursor<'a, K, V> {} + +impl<'a, K, V> Cursor<'a, K, V> { + /// The current node + pub fn current(&self) -> (&K, &V) { + // SAFETY: + // - `self.current` is a valid node by the type invariants. + // - We have an immutable reference by the function signature. + unsafe { Self::to_key_value(self.current) } + } + + /// The current node, with a mutable value + pub fn current_mut(&mut self) -> (&K, &mut V) { + // SAFETY: + // - `self.current` is a valid node by the type invariants. + // - We have an mutable reference by the function signature. + unsafe { Self::to_key_value_mut(self.current) } + } + + /// Remove the current node from the tree. + /// + /// Returns a tuple where the first element is a cursor to the next no= de, if it exists, + /// else the previous node, else [`None`] (if the tree becomes empty).= The second element + /// is the removed node. + pub fn remove_current(self) -> (Option, RBTreeNode) { + let prev =3D self.get_neighbor_raw(Direction::Prev); + let next =3D self.get_neighbor_raw(Direction::Next); + // SAFETY: By the type invariant of `Self`, all non-null `rb_node`= pointers stored in `self` + // point to the links field of `Node` objects. + let this =3D unsafe { container_of!(self.current.as_ptr(), Node, links) }.cast_mut(); + // SAFETY: `this` is valid by the type invariants as described abo= ve. + let node =3D unsafe { Box::from_raw(this) }; + let node =3D RBTreeNode { node }; + // SAFETY: The reference to the tree used to create the cursor out= lives the cursor, so + // the tree cannot change. By the tree invariant, all nodes are va= lid. + unsafe { bindings::rb_erase(&mut (*this).links, addr_of_mut!(self.= tree.root)) }; + + let current =3D match (prev, next) { + (_, Some(next)) =3D> next, + (Some(prev), None) =3D> prev, + (None, None) =3D> { + return (None, node); + } + }; + + ( + // INVARIANT: + // - `current` is a valid node in the [`RBTree`] pointed to by= `self.tree`. + // - Due to the function signature, `self` is an owned [`Curso= r`], + // and [`Cursor`]s are only created via functions with a mut= able reference + // to an [`RBTree`]. + Some(Self { + current, + tree: self.tree, + }), + node, + ) + } + + /// Remove the previous node, returning it if it exists. + pub fn remove_prev(&mut self) -> Option> { + self.remove_neighbor(Direction::Prev) + } + + /// Remove the next node, returning it if it exists. + pub fn remove_next(&mut self) -> Option> { + self.remove_neighbor(Direction::Next) + } + + fn remove_neighbor(&mut self, direction: Direction) -> Option> { + if let Some(neighbor) =3D self.get_neighbor_raw(direction) { + let neighbor =3D neighbor.as_ptr(); + // SAFETY: The reference to the tree used to create the cursor= outlives the cursor, so + // the tree cannot change. By the tree invariant, all nodes ar= e valid. + unsafe { bindings::rb_erase(neighbor, addr_of_mut!(self.tree.r= oot)) }; + // SAFETY: By the type invariant of `Self`, all non-null `rb_n= ode` pointers stored in `self` + // point to the links field of `Node` objects. + let this =3D unsafe { container_of!(neighbor, Node, link= s) }.cast_mut(); + // SAFETY: `this` is valid by the type invariants as described= above. + let node =3D unsafe { Box::from_raw(this) }; + return Some(RBTreeNode { node }); + } + None + } + + /// Move the cursor to the previous node, returning [`None`] if it doe= sn't exist. + pub fn move_prev(self) -> Option { + self.mv(Direction::Prev) + } + + /// Move the cursor to the next node, returning [`None`] if it doesn't= exist. + pub fn move_next(self) -> Option { + self.mv(Direction::Next) + } + + fn mv(self, direction: Direction) -> Option { + // INVARIANT: + // - `neighbor` is a valid node in the [`RBTree`] pointed to by `s= elf.tree`. + // - Due to the function signature, `self` is an owned [`Cursor`], + // and [`Cursor`]s are only created via functions with a mutable= reference + // to an [`RBTree`]. + self.get_neighbor_raw(direction).map(|neighbor| Self { + tree: self.tree, + current: neighbor, + }) + } + + /// Access the previous node without moving the cursor. + pub fn peek_prev(&self) -> Option<(&K, &V)> { + self.peek(Direction::Prev) + } + + /// Access the previous node without moving the cursor. + pub fn peek_next(&self) -> Option<(&K, &V)> { + self.peek(Direction::Next) + } + + fn peek(&self, direction: Direction) -> Option<(&K, &V)> { + self.get_neighbor_raw(direction).map(|neighbor| { + // SAFETY: + // - `neighbor` is a valid tree node. + // - By the function signature, we have an immutable reference= to `self`. + unsafe { Self::to_key_value(neighbor) } + }) + } + + /// Access the previous node mutably without moving the cursor. + pub fn peek_prev_mut(&mut self) -> Option<(&K, &mut V)> { + self.peek_mut(Direction::Prev) + } + + /// Access the next node mutably without moving the cursor. + pub fn peek_next_mut(&mut self) -> Option<(&K, &mut V)> { + self.peek_mut(Direction::Next) + } + + fn peek_mut(&mut self, direction: Direction) -> Option<(&K, &mut V)> { + self.get_neighbor_raw(direction).map(|neighbor| { + // SAFETY: + // - `neighbor` is a valid tree node. + // - By the function signature, we have a mutable reference to= `self`. + unsafe { Self::to_key_value_mut(neighbor) } + }) + } + + fn get_neighbor_raw(&self, direction: Direction) -> Option> { + // SAFETY: `self.current` is valid by the type invariants. + let neighbor =3D unsafe { + match direction { + Direction::Prev =3D> bindings::rb_prev(self.current.as_ptr= ()), + Direction::Next =3D> bindings::rb_next(self.current.as_ptr= ()), + } + }; + + NonNull::new(neighbor) + } + + /// SAFETY: + /// - `node` must be a valid pointer to a node in an [`RBTree`]. + /// - The caller has immutable access to `node` for the duration of 'b. + unsafe fn to_key_value<'b>(node: NonNull) -> (&'b K= , &'b V) { + // SAFETY: the caller guarantees that `node` is a valid pointer in= an `RBTree`. + let (k, v) =3D unsafe { Self::to_key_value_raw(node) }; + // SAFETY: the caller guarantees immutable access to `node`. + (k, unsafe { &*v }) + } + + /// SAFETY: + /// - `node` must be a valid pointer to a node in an [`RBTree`]. + /// - The caller has mutable access to `node` for the duration of 'b. + unsafe fn to_key_value_mut<'b>(node: NonNull) -> (&= 'b K, &'b mut V) { + // SAFETY: the caller guarantees that `node` is a valid pointer in= an `RBTree`. + let (k, v) =3D unsafe { Self::to_key_value_raw(node) }; + // SAFETY: the caller guarantees mutable access to `node`. + (k, unsafe { &mut *v }) + } + + /// SAFETY: + /// - `node` must be a valid pointer to a node in an [`RBTree`]. + /// - The caller has immutable access to the key for the duration of '= b. + unsafe fn to_key_value_raw<'b>(node: NonNull) -> (&= 'b K, *mut V) { + // SAFETY: By the type invariant of `Self`, all non-null `rb_node`= pointers stored in `self` + // point to the links field of `Node` objects. + let this =3D unsafe { container_of!(node.as_ptr(), Node, lin= ks) }.cast_mut(); + // SAFETY: The passed `node` is the current node or a non-null nei= ghbor, + // thus `this` is valid by the type invariants. + let k =3D unsafe { &(*this).key }; + // SAFETY: The passed `node` is the current node or a non-null nei= ghbor, + // thus `this` is valid by the type invariants. + let v =3D unsafe { addr_of_mut!((*this).value) }; + (k, v) + } +} + +/// Direction for [`Cursor`] operations. +enum Direction { + /// the node immediately before, in sort order + Prev, + /// the node immediately after, in sort order + Next, +} + impl<'a, K, V> IntoIterator for &'a RBTree { type Item =3D (&'a K, &'a V); type IntoIter =3D Iter<'a, K, V>; @@ -585,6 +1121,11 @@ impl RBTreeNode { pub fn new(key: K, value: V, flags: Flags) -> Result>= { Ok(RBTreeNodeReservation::new(flags)?.into_node(key, value)) } + + /// Get the key and value from inside the node. + pub fn to_key_value(self) -> (K, V) { + (self.node.key, self.node.value) + } } =20 // SAFETY: If K and V can be sent across threads, then it's also okay to s= end [`RBTreeNode`] across --=20 2.46.0.184.g6999bdac58-goog From nobody Sat Feb 7 07:10:20 2026 Received: from mail-qt1-f202.google.com (mail-qt1-f202.google.com [209.85.160.202]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 195FC1C7B68 for ; Fri, 16 Aug 2024 20:48:09 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.160.202 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723841292; cv=none; b=h+yGAnEv3T5+EyQ7q00YFBQSP1I0XtahJoqen7lF84xDX+gIru3ngpQVO03wm21tFrDPjLyW+bmwA3jX5PxDOcwedewqaZ37rNi13qg4AetAh120wgWEJdAhFI+6EVb3cbw/Sd6LBfcBLxYuvLjzNEnxiQnLlxqCEtnbDN1Vsg0= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723841292; c=relaxed/simple; bh=yULzxhgqabfFUTtoN2cYbJ23pCpjO4bznnV2x8i2jxY=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=S1pUD4WQdoAmIJBdb099dT7ptgY91vBM9eQ6IYA6xJxL4+vI88kmYm4PguVZwPGkg0emNdkthGWrarTqCHCHSEXFVvv8pl4v0QgJ9dmloCu/Soihv8CkZDXONNQ879+m/iN58fJHutdTP+Bmwl31xxPMoBmnDm06t855GkQ0xhg= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com; spf=pass smtp.mailfrom=flex--mattgilbride.bounces.google.com; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b=PmAsoPfd; arc=none smtp.client-ip=209.85.160.202 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=flex--mattgilbride.bounces.google.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="PmAsoPfd" Received: by mail-qt1-f202.google.com with SMTP id d75a77b69052e-44fe49fa389so26305091cf.1 for ; Fri, 16 Aug 2024 13:48:09 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1723841289; x=1724446089; darn=vger.kernel.org; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:from:to:cc:subject:date:message-id:reply-to; bh=ho9lWkBHrnP95w04SuuVC92kMJhRKmYkeES5lEDr4BM=; b=PmAsoPfdLorZxvR7xXpVEyzlByXFqovFBYs4KylYr+GGvLjApUosYGNrDF6740QOWq Um8k6ivl8/si6ZuTYWvbvDbC1OChuWODHMntz5c6xtPIb2pINqR3LysjprxLlXl8TdWB fqtw3dwJflElX85r+THYLKyZUw7wWBH6ZTgwjMxILcT9Iwai/8u3drH4YEMdHxQQgEvZ wlNJjjsxHOulf0pnx03EIaOevZ0fDHq1dWx3lggLjZ2J2bIrSvcYvoyOkBBzbHMI/UjK IHQ7cqbXW8jYJM/ufD7/lMMFQO4CceE0192zpzilicdiShPvdvMKuO5RZo4/SljSDEI1 n6nQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1723841289; x=1724446089; h=cc:to:from:subject:message-id:references:mime-version:in-reply-to :date:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to; bh=ho9lWkBHrnP95w04SuuVC92kMJhRKmYkeES5lEDr4BM=; b=jDS5qlMiezA0rJoqwtnhEMNzjBEjIJUxY5gJNjEU29pou4n94HfOfHQ5+kEQ2BXIOi MNM4G1NXzwrUv/A5BkLLEleYe1i51d5N3vE68YtnrMr3M9Z4J+9lu9IxwezJb8ZV4hpp M+O15YQxoAe58vsvjMVJfnnrgAio4mglpnLifwoISNpGzHFwyG57lnSQjze4sonPK3Zd xz8fyq3HHA7Ag7mBRmPNNKlm0VCzfDDBOGdF1xTRo2WyKjcRULOklBwf4j4NkEc9+3pi xIvgnAaE2LUEG/LDlPVynHyFkgDhQYJS6M5/5/tpuRusBdEiacfjJYj3DmK1LScJ7z2x 9lxQ== X-Forwarded-Encrypted: i=1; AJvYcCVM3Ptfw1zwh4YXzlMSYeU+HUlN9cjcMwEFwKsjHN5TcUaG09qUUoUi5HxAEkD8XmOfhXWoje+yoMlFNv0=@vger.kernel.org X-Gm-Message-State: AOJu0Ywv5cJwEExBLZ+DiyYcjUeFB2mJpPlsFdA90yM7lZvY9bEh50GT MeYGU5N4yEgj8SmoPj3bVn2KocVCutM6ErmljZ+IW4QIkGC0i+X63zlg5VFbm4D/NrgLA12bqT9 J8EGhKdhtaN5fMZcv9e8p2hyqCA== X-Google-Smtp-Source: AGHT+IGzibue8TsIUWRL+qhi6B5W05Dd47mKDrVidFplIuoWqSwdC9qTzWn4M7P5Eb4ln4v8Ax+ffaT4L+6NmYuMAww= X-Received: from mattgilbride.c.googlers.com ([fda3:e722:ac3:cc00:2b:7d90:c0a8:2ac5]) (user=mattgilbride job=sendgmr) by 2002:ac8:7450:0:b0:451:cf70:4a28 with SMTP id d75a77b69052e-45374271414mr69511cf.9.1723841289005; Fri, 16 Aug 2024 13:48:09 -0700 (PDT) Date: Fri, 16 Aug 2024 20:48:03 +0000 In-Reply-To: <20240816-b4-rbtree-v9-0-425b442af7e5@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240816-b4-rbtree-v9-0-425b442af7e5@google.com> X-Mailer: b4 0.13.0 Message-ID: <20240816-b4-rbtree-v9-6-425b442af7e5@google.com> Subject: [PATCH v9 6/6] rust: rbtree: add `RBTree::entry` From: Matt Gilbride To: Miguel Ojeda , Alex Gaynor , Wedson Almeida Filho , Boqun Feng , Gary Guo , "=?utf-8?q?Bj=C3=B6rn_Roy_Baron?=" , Benno Lossin , Andreas Hindborg , Alice Ryhl , Greg Kroah-Hartman , "=?utf-8?q?Arve_Hj=C3=B8nnev=C3=A5g?=" , Todd Kjos , Martijn Coenen , Joel Fernandes , Carlos Llamas , Suren Baghdasaryan , Christian Brauner Cc: Rob Landley , Davidlohr Bueso , Michel Lespinasse , rust-for-linux@vger.kernel.org, linux-kernel@vger.kernel.org, Matt Gilbride Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable From: Alice Ryhl This mirrors the entry API [1] from the Rust standard library on `RBTree`. This API can be used to access the entry at a specific key and make modifications depending on whether the key is vacant or occupied. This API is useful because it can often be used to avoid traversing the tree multiple times. This is used by binder to look up and conditionally access or insert a value, depending on whether it is there or not [2]. Link: https://doc.rust-lang.org/stable/std/collections/btree_map/enum.Entry= .html [1] Link: https://android-review.googlesource.com/c/kernel/common/+/2849906 [2] Signed-off-by: Alice Ryhl Tested-by: Alice Ryhl Reviewed-by: Boqun Feng Signed-off-by: Matt Gilbride --- rust/kernel/rbtree.rs | 310 ++++++++++++++++++++++++++++++++++++++--------= ---- 1 file changed, 235 insertions(+), 75 deletions(-) diff --git a/rust/kernel/rbtree.rs b/rust/kernel/rbtree.rs index 754af0db86b5..db185b6b3c65 100644 --- a/rust/kernel/rbtree.rs +++ b/rust/kernel/rbtree.rs @@ -297,12 +297,19 @@ pub fn try_create_and_insert( /// key/value pair). Returns [`None`] if a node with the same key didn= 't already exist. /// /// This function always succeeds. - pub fn insert(&mut self, RBTreeNode { node }: RBTreeNode) -> Opt= ion> { - let node =3D Box::into_raw(node); - // SAFETY: `node` is valid at least until we call `Box::from_raw`,= which only happens when - // the node is removed or replaced. - let node_links =3D unsafe { addr_of_mut!((*node).links) }; + pub fn insert(&mut self, node: RBTreeNode) -> Option> { + match self.raw_entry(&node.node.key) { + RawEntry::Occupied(entry) =3D> Some(entry.replace(node)), + RawEntry::Vacant(entry) =3D> { + entry.insert(node); + None + } + } + } =20 + fn raw_entry(&mut self, key: &K) -> RawEntry<'_, K, V> { + let raw_self: *mut RBTree =3D self; + // The returned `RawEntry` is used to call either `rb_link_node` o= r `rb_replace_node`. // The parameters of `bindings::rb_link_node` are as follows: // - `node`: A pointer to an uninitialized node being inserted. // - `parent`: A pointer to an existing node in the tree. One of i= ts child pointers must be @@ -321,62 +328,56 @@ pub fn insert(&mut self, RBTreeNode { node }: RBTreeN= ode) -> Option`. + let node =3D unsafe { container_of!(curr, Node, links) }; =20 - // We need to determine whether `node` should be the left or r= ight child of `parent`, - // so we will compare with the `key` field of `parent` a.k.a. = `this` below. - // - // SAFETY: By the type invariant of `Self`, all non-null `rb_n= ode` pointers stored in `self` - // point to the links field of `Node` objects. - let this =3D unsafe { container_of!(parent, Node, links)= }; - - // SAFETY: `this` is a non-null node so it is valid by the typ= e invariants. `node` is - // valid until the node is removed. - match unsafe { (*node).key.cmp(&(*this).key) } { - // We would like `node` to be the left child of `parent`. = Move to this child to check - // whether we can use it, or continue searching, at the ne= xt iteration. - // - // SAFETY: `parent` is a non-null node so it is valid by t= he type invariants. - Ordering::Less =3D> child_field_of_parent =3D unsafe { &mu= t (*parent).rb_left }, - // We would like `node` to be the right child of `parent`.= Move to this child to check - // whether we can use it, or continue searching, at the ne= xt iteration. - // - // SAFETY: `parent` is a non-null node so it is valid by t= he type invariants. - Ordering::Greater =3D> child_field_of_parent =3D unsafe { = &mut (*parent).rb_right }, + // SAFETY: `node` is a non-null node so it is valid by the typ= e invariants. + match key.cmp(unsafe { &(*node).key }) { + // SAFETY: `curr` is a non-null node so it is valid by the= type invariants. + Ordering::Less =3D> child_field_of_parent =3D unsafe { &mu= t (*curr).rb_left }, + // SAFETY: `curr` is a non-null node so it is valid by the= type invariants. + Ordering::Greater =3D> child_field_of_parent =3D unsafe { = &mut (*curr).rb_right }, Ordering::Equal =3D> { - // There is an existing node in the tree with this key= , and that node is - // `parent`. Thus, we are replacing parent with a new = node. - // - // INVARIANT: We are replacing an existing node with a= new one, which is valid. - // It remains valid because we "forgot" it with `Box::= into_raw`. - // SAFETY: All pointers are non-null and valid. - unsafe { bindings::rb_replace_node(parent, node_links,= &mut self.root) }; - - // INVARIANT: The node is being returned and the calle= r may free it, however, - // it was removed from the tree. So the invariants sti= ll hold. - return Some(RBTreeNode { - // SAFETY: `this` was a node in the tree, so it is= valid. - node: unsafe { Box::from_raw(this.cast_mut()) }, - }); + return RawEntry::Occupied(OccupiedEntry { + rbtree: self, + node_links: curr, + }) } } + parent =3D curr; } =20 - // INVARIANT: We are linking in a new node, which is valid. It rem= ains valid because we - // "forgot" it with `Box::into_raw`. - // SAFETY: All pointers are non-null and valid (`*child_field_of_p= arent` is null, but `child_field_of_parent` is a - // mutable reference). - unsafe { bindings::rb_link_node(node_links, parent, child_field_of= _parent) }; + RawEntry::Vacant(RawVacantEntry { + rbtree: raw_self, + parent, + child_field_of_parent, + _phantom: PhantomData, + }) + } =20 - // SAFETY: All pointers are valid. `node` has just been inserted i= nto the tree. - unsafe { bindings::rb_insert_color(node_links, &mut self.root) }; - None + /// Gets the given key's corresponding entry in the map for in-place m= anipulation. + pub fn entry(&mut self, key: K) -> Entry<'_, K, V> { + match self.raw_entry(&key) { + RawEntry::Occupied(entry) =3D> Entry::Occupied(entry), + RawEntry::Vacant(entry) =3D> Entry::Vacant(VacantEntry { raw: = entry, key }), + } } =20 - /// Returns a node with the given key, if one exists. - fn find(&self, key: &K) -> Option>> { + /// Used for accessing the given node, if it exists. + pub fn find_mut(&mut self, key: &K) -> Option>= { + match self.raw_entry(key) { + RawEntry::Occupied(entry) =3D> Some(entry), + RawEntry::Vacant(_entry) =3D> None, + } + } + + /// Returns a reference to the value corresponding to the key. + pub fn get(&self, key: &K) -> Option<&V> { let mut node =3D self.root.rb_node; while !node.is_null() { // SAFETY: By the type invariant of `Self`, all non-null `rb_n= ode` pointers stored in `self` @@ -388,47 +389,30 @@ fn find(&self, key: &K) -> Option>= > { Ordering::Less =3D> unsafe { (*node).rb_left }, // SAFETY: `node` is a non-null node so it is valid by the= type invariants. Ordering::Greater =3D> unsafe { (*node).rb_right }, - Ordering::Equal =3D> return NonNull::new(this.cast_mut()), + // SAFETY: `node` is a non-null node so it is valid by the= type invariants. + Ordering::Equal =3D> return Some(unsafe { &(*this).value }= ), } } None } =20 - /// Returns a reference to the value corresponding to the key. - pub fn get(&self, key: &K) -> Option<&V> { - // SAFETY: The `find` return value is a node in the tree, so it is= valid. - self.find(key).map(|node| unsafe { &node.as_ref().value }) - } - /// Returns a mutable reference to the value corresponding to the key. pub fn get_mut(&mut self, key: &K) -> Option<&mut V> { - // SAFETY: The `find` return value is a node in the tree, so it is= valid. - self.find(key) - .map(|mut node| unsafe { &mut node.as_mut().value }) + self.find_mut(key).map(|node| node.into_mut()) } =20 /// Removes the node with the given key from the tree. /// /// It returns the node that was removed if one exists, or [`None`] ot= herwise. - fn remove_node(&mut self, key: &K) -> Option> { - let mut node =3D self.find(key)?; - - // SAFETY: The `find` return value is a node in the tree, so it is= valid. - unsafe { bindings::rb_erase(&mut node.as_mut().links, &mut self.ro= ot) }; - - // INVARIANT: The node is being returned and the caller may free i= t, however, it was - // removed from the tree. So the invariants still hold. - Some(RBTreeNode { - // SAFETY: The `find` return value was a node in the tree, so = it is valid. - node: unsafe { Box::from_raw(node.as_ptr()) }, - }) + pub fn remove_node(&mut self, key: &K) -> Option> { + self.find_mut(key).map(OccupiedEntry::remove_node) } =20 /// Removes the node with the given key from the tree. /// /// It returns the value that was removed if one exists, or [`None`] o= therwise. pub fn remove(&mut self, key: &K) -> Option { - self.remove_node(key).map(|node| node.node.value) + self.find_mut(key).map(OccupiedEntry::remove) } =20 /// Returns a cursor over the tree nodes based on the given key. @@ -1136,6 +1120,182 @@ unsafe impl Send for RBTreeNode {} // [`RBTreeNode`] without synchronization. unsafe impl Sync for RBTreeNode {} =20 +impl RBTreeNode { + /// Drop the key and value, but keep the allocation. + /// + /// It then becomes a reservation that can be re-initialised into a di= fferent node (i.e., with + /// a different key and/or value). + /// + /// The existing key and value are dropped in-place as part of this op= eration, that is, memory + /// may be freed (but only for the key/value; memory for the node itse= lf is kept for reuse). + pub fn into_reservation(self) -> RBTreeNodeReservation { + RBTreeNodeReservation { + node: Box::drop_contents(self.node), + } + } +} + +/// A view into a single entry in a map, which may either be vacant or occ= upied. +/// +/// This enum is constructed from the [`RBTree::entry`]. +/// +/// [`entry`]: fn@RBTree::entry +pub enum Entry<'a, K, V> { + /// This [`RBTree`] does not have a node with this key. + Vacant(VacantEntry<'a, K, V>), + /// This [`RBTree`] already has a node with this key. + Occupied(OccupiedEntry<'a, K, V>), +} + +/// Like [`Entry`], except that it doesn't have ownership of the key. +enum RawEntry<'a, K, V> { + Vacant(RawVacantEntry<'a, K, V>), + Occupied(OccupiedEntry<'a, K, V>), +} + +/// A view into a vacant entry in a [`RBTree`]. It is part of the [`Entry`= ] enum. +pub struct VacantEntry<'a, K, V> { + key: K, + raw: RawVacantEntry<'a, K, V>, +} + +/// Like [`VacantEntry`], but doesn't hold on to the key. +/// +/// # Invariants +/// - `parent` may be null if the new node becomes the root. +/// - `child_field_of_parent` is a valid pointer to the left-child or righ= t-child of `parent`. If `parent` is +/// null, it is a pointer to the root of the [`RBTree`]. +struct RawVacantEntry<'a, K, V> { + rbtree: *mut RBTree, + /// The node that will become the parent of the new node if we insert = one. + parent: *mut bindings::rb_node, + /// This points to the left-child or right-child field of `parent`, or= `root` if `parent` is + /// null. + child_field_of_parent: *mut *mut bindings::rb_node, + _phantom: PhantomData<&'a mut RBTree>, +} + +impl<'a, K, V> RawVacantEntry<'a, K, V> { + /// Inserts the given node into the [`RBTree`] at this entry. + /// + /// The `node` must have a key such that inserting it here does not br= eak the ordering of this + /// [`RBTree`]. + fn insert(self, node: RBTreeNode) -> &'a mut V { + let node =3D Box::into_raw(node.node); + + // SAFETY: `node` is valid at least until we call `Box::from_raw`,= which only happens when + // the node is removed or replaced. + let node_links =3D unsafe { addr_of_mut!((*node).links) }; + + // INVARIANT: We are linking in a new node, which is valid. It rem= ains valid because we + // "forgot" it with `Box::into_raw`. + // SAFETY: The type invariants of `RawVacantEntry` are exactly the= safety requirements of `rb_link_node`. + unsafe { bindings::rb_link_node(node_links, self.parent, self.chil= d_field_of_parent) }; + + // SAFETY: All pointers are valid. `node` has just been inserted i= nto the tree. + unsafe { bindings::rb_insert_color(node_links, addr_of_mut!((*self= .rbtree).root)) }; + + // SAFETY: The node is valid until we remove it from the tree. + unsafe { &mut (*node).value } + } +} + +impl<'a, K, V> VacantEntry<'a, K, V> { + /// Inserts the given node into the [`RBTree`] at this entry. + pub fn insert(self, value: V, reservation: RBTreeNodeReservation= ) -> &'a mut V { + self.raw.insert(reservation.into_node(self.key, value)) + } +} + +/// A view into an occupied entry in a [`RBTree`]. It is part of the [`Ent= ry`] enum. +/// +/// # Invariants +/// - `node_links` is a valid, non-null pointer to a tree node in `self.rb= tree` +pub struct OccupiedEntry<'a, K, V> { + rbtree: &'a mut RBTree, + /// The node that this entry corresponds to. + node_links: *mut bindings::rb_node, +} + +impl<'a, K, V> OccupiedEntry<'a, K, V> { + /// Gets a reference to the value in the entry. + pub fn get(&self) -> &V { + // SAFETY: + // - `self.node_links` is a valid pointer to a node in the tree. + // - We have shared access to the underlying tree, and can thus gi= ve out a shared reference. + unsafe { &(*container_of!(self.node_links, Node, links)).val= ue } + } + + /// Gets a mutable reference to the value in the entry. + pub fn get_mut(&mut self) -> &mut V { + // SAFETY: + // - `self.node_links` is a valid pointer to a node in the tree. + // - We have exclusive access to the underlying tree, and can thus= give out a mutable reference. + unsafe { + &mut (*(container_of!(self.node_links, Node, links) as *= mut Node)).value + } + } + + /// Converts the entry into a mutable reference to its value. + /// + /// If you need multiple references to the `OccupiedEntry`, see [`self= #get_mut`]. + pub fn into_mut(self) -> &'a mut V { + // SAFETY: + // - `self.node_links` is a valid pointer to a node in the tree. + // - This consumes the `&'a mut RBTree`, therefore it can gi= ve out a mutable reference that lives for `'a`. + unsafe { + &mut (*(container_of!(self.node_links, Node, links) as *= mut Node)).value + } + } + + /// Remove this entry from the [`RBTree`]. + pub fn remove_node(self) -> RBTreeNode { + // SAFETY: The node is a node in the tree, so it is valid. + unsafe { bindings::rb_erase(self.node_links, &mut self.rbtree.root= ) }; + + // INVARIANT: The node is being returned and the caller may free i= t, however, it was + // removed from the tree. So the invariants still hold. + RBTreeNode { + // SAFETY: The node was a node in the tree, but we removed it,= so we can convert it + // back into a box. + node: unsafe { + Box::from_raw(container_of!(self.node_links, Node, l= inks) as *mut Node) + }, + } + } + + /// Takes the value of the entry out of the map, and returns it. + pub fn remove(self) -> V { + self.remove_node().node.value + } + + /// Swap the current node for the provided node. + /// + /// The key of both nodes must be equal. + fn replace(self, node: RBTreeNode) -> RBTreeNode { + let node =3D Box::into_raw(node.node); + + // SAFETY: `node` is valid at least until we call `Box::from_raw`,= which only happens when + // the node is removed or replaced. + let new_node_links =3D unsafe { addr_of_mut!((*node).links) }; + + // SAFETY: This updates the pointers so that `new_node_links` is i= n the tree where + // `self.node_links` used to be. + unsafe { + bindings::rb_replace_node(self.node_links, new_node_links, &mu= t self.rbtree.root) + }; + + // SAFETY: + // - `self.node_ptr` produces a valid pointer to a node in the tre= e. + // - Now that we removed this entry from the tree, we can convert = the node to a box. + let old_node =3D unsafe { + Box::from_raw(container_of!(self.node_links, Node, links= ) as *mut Node) + }; + + RBTreeNode { node: old_node } + } +} + struct Node { links: bindings::rb_node, key: K, --=20 2.46.0.184.g6999bdac58-goog