From nobody Thu Sep 19 16:35:01 2024 Received: from mail-wr1-f74.google.com (mail-wr1-f74.google.com [209.85.221.74]) (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 EA4581422AB for ; Wed, 14 Aug 2024 08:06:05 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.221.74 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723622767; cv=none; b=puHHUp1kPm+loDcPwBKrnwMhZSAj6YEetUIL8Eb73R/JGwWh/9n+MvIboYdHM32i7WCjdwlfn/AP+Q5Q4WZgw6QKckW3ZSfPz3gBK6uu3oZYq/iHWKVZKqfVvclL86osUrYDw8C6Fzuot3qWEAbKD/Bw+QCtDRrctOuxv3k42XY= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723622767; c=relaxed/simple; bh=xnc/YeHBMoQaOvOzlunHyZEPrhxk1PkpkgFQgdA3Xak=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=olUXgv+zr/0DQCJSOmpcCDx2xbbQvAGM8+dmg72ZPnH/FDQQaUrMa499jjliL64CVby7vHoRHGASbUmwxNcj2NykK/2y41nQkIZajn5TKVg3NY74/linxVU5i1+9m1wx/pZl2Tov4kzyeCTPVD/xbCn/n4VEuo6hUKRueUVEgks= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com; spf=pass smtp.mailfrom=flex--aliceryhl.bounces.google.com; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b=V2DlGWkq; arc=none smtp.client-ip=209.85.221.74 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--aliceryhl.bounces.google.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="V2DlGWkq" Received: by mail-wr1-f74.google.com with SMTP id ffacd0b85a97d-368448dfe12so320645f8f.1 for ; Wed, 14 Aug 2024 01:06:05 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1723622764; x=1724227564; 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=yi9Z6wpf5ind79uw6LrrGYLWeY0/HZjpQZjY71BcRmQ=; b=V2DlGWkqGhVW5NUfgw5t9d+Ge/iS9ilbIZvkr5XBiG7rdq3YIcfEJ/WJxZ4EwfFyrN PPcNgYkcS2stRkqt/j/edqQdVp5CspNguTUOHnfqWdkAUpSXx7H02xIKVYjBwynLgYDz dcFsepe+mvMGfPfCroRjiqENe9LvnCaltkoeh4ltqHcrd1g718z97Cc8bMkZpJhppd1N i2F4DX7zH0EVl0f5xEDMHgzjSAf3D2E5OdKnAhP4RPLJ+ge66igHO6VQ042EtnIMfemC 2eHLYN/jMaQBpCvKmnmsBKtJt3xBvM0jFA4W4LitTSEf5dnq4RnO81TVpSLq1u3NSZFz AMSw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1723622764; x=1724227564; 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=yi9Z6wpf5ind79uw6LrrGYLWeY0/HZjpQZjY71BcRmQ=; b=ei2Qju/VEdRtpkFdNcTGB7l9etY/zAfWmO6zyFxMoQswluQXRdV2okhqffQKJJb3v+ SNRsVViI2crGBURy/5hGU457mxR9dodBmfFHMooD3pl3Koz1T510GfF9+BSmCQi5vCjz MH0IcdsyE81w9eDaXQreQ5O/iy8dc/7+9kKvQXlPW32shP8ACMbdpQOrUgQHGr/NNajL dPBlRP21LjhtI/f8Xd5gyzbLP+omQElSielHOXi1arxORqWYQNlElEGk9DB6SPM898jh YnpRnE3KGI4IaU9raHtz/oX9mD4lB1P+MADavZjPEyZg14H1p/Nd4gRAfmifBf2sUfWT jSOA== X-Forwarded-Encrypted: i=1; AJvYcCV4l0YRT7j2pbUacGr4GsjIltC3K6dF9kNc8Pi2u3Nzc8JOecizzTFK6I5UPobyEyoVRbaeQ3l5Ja/8y6rqmWGx4xZqDppfCn71fcrs X-Gm-Message-State: AOJu0YwOA49ZWFs4xT3TEBEqTe5mipWLG0zoh0P5M+9J3el6+3EfbeFY qYpdF5tKSJa17My61VH7GKRlmkh/wGKgBU3FU5sz3jrY2ap6cfkvQX9b97EwM8LF1tXXYXFIuay xyv+ZNMEm59w7Gw== X-Google-Smtp-Source: AGHT+IHg8hpTvx6+/E6ZhSBhsl3XwfPesWpPswCzOXnR31xIWDBQuWw4nDBknyWEM/jxePL4xjTv4zXk9/uCJpg= X-Received: from aliceryhl.c.googlers.com ([fda3:e722:ac3:cc00:28:9cb1:c0a8:35bd]) (user=aliceryhl job=sendgmr) by 2002:a5d:5889:0:b0:364:75ab:b06b with SMTP id ffacd0b85a97d-37177585517mr9993f8f.3.1723622764111; Wed, 14 Aug 2024 01:06:04 -0700 (PDT) Date: Wed, 14 Aug 2024 08:05:22 +0000 In-Reply-To: <20240814-linked-list-v5-0-f5f5e8075da0@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240814-linked-list-v5-0-f5f5e8075da0@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=11298; i=aliceryhl@google.com; h=from:subject:message-id; bh=xnc/YeHBMoQaOvOzlunHyZEPrhxk1PkpkgFQgdA3Xak=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBmvGVdKp3WgXP+fHa2JhwCKV+E3D8kgibsK6/co piN3hNG4bOJAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCZrxlXQAKCRAEWL7uWMY5 RlhPD/9A+iTf+Od3oxGeulQdMZzfo8L9cbdHiRrW83gXYjIzY/PI7hK1bh/QC9cleg8fCeShwyv U/vGp+kdPGRNNq3m5fWzWcsXGK60NK4ptbxocS7f0H8DNqDs4/BOhArY5HR0QycGPc5DA0yCsSz /ATuWoBW+AWYFjh1BNCWklBWFWczdRIG4M6Bsccx2/Gksqo3LSRTOZ5J1S17GN6GIgfdHnEjEza SdmHzwDDqMa87XRsnKwZQ53Fbale+m7JaYvm9ip4hsdVO+FuR3/lwjxyNhqqIyR071fzfn5bmUF 5dZS19Z/7ha81QDuxuj6/7hCr7Xx92MYeVhdVi5BzcRyJhzlqS00BMjJEjF24R573gJLUu+fk9J gb5fdIx32iNkg4mpbyAxcq21nNChU3VPD4MjCiqm7jwdQwLsIhoCQcda/AgDpHvaTTwQJrkcH0G iRyUe2OhpTAxTQoqLkUCuhCKqDa94Ac40nLrtSyEF6qzV5WLpKna7fRyIm1PI69uBgbKy6/lmvk gUI5z6oOyhKc5yccXeLs37g2qZa1UgH941vjEILX0Yeb4bhO/SVUGzVAHyXY/lSi1cZmnIcZYFY oczer3iFht74SgQh20pM21nNIQRACD5WaqB23S+Frjzbeg7LhMh75HufVSEos6MiAc2jNC45Nl+ Jr+HXljoeNCTF8A== X-Mailer: b4 0.13.0 Message-ID: <20240814-linked-list-v5-3-f5f5e8075da0@google.com> Subject: [PATCH v5 03/10] rust: list: add tracking for ListArc From: Alice Ryhl To: Miguel Ojeda , Andrew Morton Cc: Alex Gaynor , Wedson Almeida Filho , Boqun Feng , Gary Guo , "=?utf-8?q?Bj=C3=B6rn_Roy_Baron?=" , Benno Lossin , Andreas Hindborg , Marco Elver , Coly Li , Paolo Abeni , Pierre Gondois , Ingo Molnar , Jakub Kicinski , Wei Yang , Matthew Wilcox , linux-kernel@vger.kernel.org, rust-for-linux@vger.kernel.org, Alice Ryhl , Kees Cook Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Add the ability to track whether a ListArc exists for a given value, allowing for the creation of ListArcs without going through UniqueArc. The `impl_list_arc_safe!` macro is extended with a `tracked_by` strategy that defers the tracking of ListArcs to a field of the struct. Additionally, the AtomicListArcTracker type is introduced, which can track whether a ListArc exists using an atomic. By deferring the tracking to a field of type AtomicListArcTracker, structs gain the ability to create ListArcs without going through a UniqueArc. Rust Binder uses this for some objects where we want to be able to insert them into a linked list at any time. Using the AtomicListArcTracker, we are able to check whether an item is already in the list, and if not, we can create a `ListArc` and push it. The macro has the ability to defer the tracking of ListArcs to a field, using whatever strategy that field has. Since we don't add any strategies other than AtomicListArcTracker, another similar option would be to hard-code that the field should be an AtomicListArcTracker. However, Rust Binder has a case where the AtomicListArcTracker is not stored directly in the struct, but in a sub-struct. Furthermore, the outer struct is generic: struct Wrapper { links: ListLinks, inner: T, } Here, the Wrapper struct implements ListArcSafe with `tracked_by inner`, and then the various types used with `inner` also uses the macro to implement ListArcSafe. Some of them use the untracked strategy, and some of them use tracked_by with an AtomicListArcTracker. This way, Wrapper just inherits whichever choice `inner` has made. Reviewed-by: Benno Lossin Signed-off-by: Alice Ryhl --- rust/kernel/list.rs | 2 +- rust/kernel/list/arc.rs | 171 ++++++++++++++++++++++++++++++++++++++++++++= +++- 2 files changed, 170 insertions(+), 3 deletions(-) diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs index fb16ea43b2ba..8e1533ee987b 100644 --- a/rust/kernel/list.rs +++ b/rust/kernel/list.rs @@ -5,4 +5,4 @@ //! A linked list implementation. =20 mod arc; -pub use self::arc::{impl_list_arc_safe, ListArc, ListArcSafe}; +pub use self::arc::{impl_list_arc_safe, AtomicTracker, ListArc, ListArcSaf= e, TryNewListArc}; diff --git a/rust/kernel/list/arc.rs b/rust/kernel/list/arc.rs index 966076da4a75..c5921a7d5966 100644 --- a/rust/kernel/list/arc.rs +++ b/rust/kernel/list/arc.rs @@ -7,9 +7,10 @@ use crate::alloc::{AllocError, Flags}; use crate::prelude::*; use crate::sync::{Arc, ArcBorrow, UniqueArc}; -use core::marker::Unsize; +use core::marker::{PhantomPinned, Unsize}; use core::ops::Deref; use core::pin::Pin; +use core::sync::atomic::{AtomicBool, Ordering}; =20 /// Declares that this type has some way to ensure that there is exactly o= ne `ListArc` instance for /// this id. @@ -48,9 +49,38 @@ pub trait ListArcSafe { unsafe fn on_drop_list_arc(&self); } =20 +/// Declares that this type is able to safely attempt to create `ListArc`s= at any time. +/// +/// # Safety +/// +/// The guarantees of `try_new_list_arc` must be upheld. +pub unsafe trait TryNewListArc: ListArcSafe { + /// Attempts to convert an `Arc` into an `ListArc`. Return= s `true` if the + /// conversion was successful. + /// + /// This method should not be called directly. Use [`ListArc::try_from= _arc`] instead. + /// + /// # Guarantees + /// + /// If this call returns `true`, then there is no [`ListArc`] pointing= to this value. + /// Additionally, this call will have transitioned the tracking inside= `Self` from not thinking + /// that a [`ListArc`] exists, to thinking that a [`ListArc`] exists. + fn try_new_list_arc(&self) -> bool; +} + /// Declares that this type supports [`ListArc`]. /// -/// When using this macro, it will only be possible to create a [`ListArc`= ] from a [`UniqueArc`]. +/// This macro supports a few different strategies for implementing the tr= acking inside the type: +/// +/// * The `untracked` strategy does not actually keep track of whether a [= `ListArc`] exists. When +/// using this strategy, the only way to create a [`ListArc`] is using a= [`UniqueArc`]. +/// * The `tracked_by` strategy defers the tracking to a field of the stru= ct. The user much specify +/// which field to defer the tracking to. The field must implement [`Lis= tArcSafe`]. If the field +/// implements [`TryNewListArc`], then the type will also implement [`Tr= yNewListArc`]. +/// +/// The `tracked_by` strategy is usually used by deferring to a field of t= ype +/// [`AtomicTracker`]. However, it is also possible to defer the tracking = to another struct +/// using also using this macro. #[macro_export] macro_rules! impl_list_arc_safe { (impl$({$($generics:tt)*})? ListArcSafe<$num:tt> for $t:ty { untracked= ; } $($rest:tt)*) =3D> { @@ -61,6 +91,39 @@ unsafe fn on_drop_list_arc(&self) {} $crate::list::impl_list_arc_safe! { $($rest)* } }; =20 + (impl$({$($generics:tt)*})? ListArcSafe<$num:tt> for $t:ty { + tracked_by $field:ident : $fty:ty; + } $($rest:tt)*) =3D> { + impl$(<$($generics)*>)? $crate::list::ListArcSafe<$num> for $t { + unsafe fn on_create_list_arc_from_unique(self: ::core::pin::Pi= n<&mut Self>) { + $crate::assert_pinned!($t, $field, $fty, inline); + + // SAFETY: This field is structurally pinned as per the ab= ove assertion. + let field =3D unsafe { + ::core::pin::Pin::map_unchecked_mut(self, |me| &mut me= .$field) + }; + // SAFETY: The caller promises that there is no `ListArc`. + unsafe { + <$fty as $crate::list::ListArcSafe<$num>>::on_create_l= ist_arc_from_unique(field) + }; + } + unsafe fn on_drop_list_arc(&self) { + // SAFETY: The caller promises that there is no `ListArc` = reference, and also + // promises that the tracking thinks there is a `ListArc` = reference. + unsafe { <$fty as $crate::list::ListArcSafe<$num>>::on_dro= p_list_arc(&self.$field) }; + } + } + unsafe impl$(<$($generics)*>)? $crate::list::TryNewListArc<$num> f= or $t + where + $fty: TryNewListArc<$num>, + { + fn try_new_list_arc(&self) -> bool { + <$fty as $crate::list::TryNewListArc<$num>>::try_new_list_= arc(&self.$field) + } + } + $crate::list::impl_list_arc_safe! { $($rest)* } + }; + () =3D> {}; } pub use impl_list_arc_safe; @@ -205,6 +268,52 @@ pub fn pair_from_pin_unique( } } =20 + /// Try to create a new `ListArc`. + /// + /// This fails if this value already has a `ListArc`. + pub fn try_from_arc(arc: Arc) -> Result> + where + T: TryNewListArc, + { + if arc.try_new_list_arc() { + // SAFETY: The `try_new_list_arc` method returned true, so we = made the tracking think + // that a `ListArc` exists. This lets us create a `ListArc`. + Ok(unsafe { Self::transmute_from_arc(arc) }) + } else { + Err(arc) + } + } + + /// Try to create a new `ListArc`. + /// + /// This fails if this value already has a `ListArc`. + pub fn try_from_arc_borrow(arc: ArcBorrow<'_, T>) -> Option + where + T: TryNewListArc, + { + if arc.try_new_list_arc() { + // SAFETY: The `try_new_list_arc` method returned true, so we = made the tracking think + // that a `ListArc` exists. This lets us create a `ListArc`. + Some(unsafe { Self::transmute_from_arc(Arc::from(arc)) }) + } else { + None + } + } + + /// Try to create a new `ListArc`. + /// + /// If it's not possible to create a new `ListArc`, then the `Arc` is = dropped. This will never + /// run the destructor of the value. + pub fn try_from_arc_or_drop(arc: Arc) -> Option + where + T: TryNewListArc, + { + match Self::try_from_arc(arc) { + Ok(list_arc) =3D> Some(list_arc), + Err(arc) =3D> Arc::into_unique_or_drop(arc).map(Self::from), + } + } + /// Transmutes an [`Arc`] into a `ListArc` without updating the tracki= ng inside `T`. /// /// # Safety @@ -350,3 +459,61 @@ impl core::ops::DispatchFromDyn> for ListArc U: ListArcSafe + ?Sized, { } + +/// A utility for tracking whether a [`ListArc`] exists using an atomic. +/// +/// # Invariant +/// +/// If the boolean is `false`, then there is no [`ListArc`] for this value. +#[repr(transparent)] +pub struct AtomicTracker { + inner: AtomicBool, + // This value needs to be pinned to justify the INVARIANT: comment in = `AtomicTracker::new`. + _pin: PhantomPinned, +} + +impl AtomicTracker { + /// Creates a new initializer for this type. + pub fn new() -> impl PinInit { + // INVARIANT: Pin-init initializers can't be used on an existing `= Arc`, so this value will + // not be constructed in an `Arc` that already has a `ListArc`. + Self { + inner: AtomicBool::new(false), + _pin: PhantomPinned, + } + } + + fn project_inner(self: Pin<&mut Self>) -> &mut AtomicBool { + // SAFETY: The `inner` field is not structurally pinned, so we may= obtain a mutable + // reference to it even if we only have a pinned reference to `sel= f`. + unsafe { &mut Pin::into_inner_unchecked(self).inner } + } +} + +impl ListArcSafe for AtomicTracker { + unsafe fn on_create_list_arc_from_unique(self: Pin<&mut Self>) { + // INVARIANT: We just created a ListArc, so the boolean should be = true. + *self.project_inner().get_mut() =3D true; + } + + unsafe fn on_drop_list_arc(&self) { + // INVARIANT: We just dropped a ListArc, so the boolean should be = false. + self.inner.store(false, Ordering::Release); + } +} + +// SAFETY: If this method returns `true`, then by the type invariant there= is no `ListArc` before +// this call, so it is okay to create a new `ListArc`. +// +// The acquire ordering will synchronize with the release store from the d= estruction of any +// previous `ListArc`, so if there was a previous `ListArc`, then the dest= ruction of the previous +// `ListArc` happens-before the creation of the new `ListArc`. +unsafe impl TryNewListArc for AtomicTracker { + fn try_new_list_arc(&self) -> bool { + // INVARIANT: If this method returns true, then the boolean used t= o be false, and is no + // longer false, so it is okay for the caller to create a new [`Li= stArc`]. + self.inner + .compare_exchange(false, true, Ordering::Acquire, Ordering::Re= laxed) + .is_ok() + } +} --=20 2.46.0.76.ge559c4bf1a-goog