From nobody Wed Dec 17 17:23:06 2025 Received: from mail-lj1-f202.google.com (mail-lj1-f202.google.com [209.85.208.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 643AC142E80 for ; Mon, 6 May 2024 09:53:51 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.208.202 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714989233; cv=none; b=qvtzbA/GOI6S5JvaFrXIPZI/sPznPgF7BkCvzf25A7z0cBmB58MjN1/Xz0kQLHJfAqqbLm2pizOfG+Omhe94uYOClV5dQc3jiq0BFriYX8K+syee6EbMhQSZZ4/VKgMCU6hg5YgcNaeJDQtqOt2Xxpn2E+n0/7Y3dwzdkQTbD+Q= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714989233; c=relaxed/simple; bh=vHnMYoARsaSwT4DBkFiei47dRFIRkgVi3GBnqZ7Fb1o=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=cRdHI9EBZ74+bouLeG80MND1TArvrS5k9dZM0yFLARRgiWwe0Uh+67C8Bp5DmjjDXzCzwogTdtCobIYWKpaP/6B9U+Z8A4iSSdKiYr60YVuExrmXfAeouXFy34OTdKPm8essFegQY4rmz45tmtvUkIGiz+2hIaAwi8y2a7RiXdo= 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=sV8frdUW; arc=none smtp.client-ip=209.85.208.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--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="sV8frdUW" Received: by mail-lj1-f202.google.com with SMTP id 38308e7fff4ca-2e1f38cb631so17535601fa.1 for ; Mon, 06 May 2024 02:53:51 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1714989229; x=1715594029; 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=IvEL2vDi6KBnvXakxenmg+ioXoslEEuGEzVw09QDssg=; b=sV8frdUWghkhT9OtYi5oVlclWG4DKg+bph/aJQ9D1PeXreXyvBqeCwUlUxObLq+jNN ubXE/0YWXTkRayTO7pyoAWFB+d0u0j2SD5CEzkHAOHzQR5XRU8/WfkvL/ldAgOIf/pN1 bMhCZ/u9Vz9ONPwwV1fIMrmOFR+4EQYF0FXnuq1tYFO5d+fvcVn9n2L1qk9akoJbJK4I qc30CR3Cw1zY3Uhe1iMJMe0DzRMSEr2ag/eZ/Z++et/PCnT1fp06XbPRDxa2/0y8FLok USKFNru8XphnNfsu//VA/oiripVkntGdTMekNTfJtjRze64cgpFJvE+OuVUZIa7mhajv c/Dg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1714989229; x=1715594029; 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=IvEL2vDi6KBnvXakxenmg+ioXoslEEuGEzVw09QDssg=; b=irrRu5OpiiNTeg08RGulcElZZ9rE/KpZYO7qGl1gRSrU2AoZsGh/3IbBUxX1XAhmxY mxr354GYKUwLnJ6vlo/VSVRcNmO1cbhgpwpxwQKUWKMnKPN51bahrlH+nQMPfnRvOAv+ oJ7Q+VsiUbXqKlEuxz0KxSiHK6+joNg3RfMmvyBTU8MHWaZixc+VSTFCrd3W2RuX6D9U aghMJcWfHr7uXg/lGO5hSP6bVXAzamb3ORiGOmkYwK9qXfcOVtuoUc8jFXb3GcOIOncK Xb/tsXANo9G+252YXeqvfLgjb7Y1UqNWk7KUHQQpduMNr6PgLrxMs0PJb0EeLk9phFjW CgeQ== X-Forwarded-Encrypted: i=1; AJvYcCWaUbvJyWVfC+03cEeGYQYdXaR8VaB37NBMBfAvAmzpBJFNLn97fUXdHzkQt3W9nuHBym1WxOsI2dmou+JASWkO3HWKycwjBsUBtP6s X-Gm-Message-State: AOJu0YxsdU+07b2za/HGE11feINZFPrnF0Ak2T8FwMLFS8rZcK/sFMF7 UChHzMVbjvoh1Ten0M/yb/lHOc9KoT/LHq5mywMDanoPSiXty+B9HkgbTXLp/CTywkrUQupI36c rzHzaUIUGUFSbKA== X-Google-Smtp-Source: AGHT+IE/oSzVgMcC4kNH2suZnzNw5/b25lli3XqL0pN4PbmbDnGAC3sRdslzfO4l49/NkAHW6PR9czmnLadXzC4= X-Received: from aliceryhl2.c.googlers.com ([fda3:e722:ac3:cc00:68:949d:c0a8:572]) (user=aliceryhl job=sendgmr) by 2002:ac2:5f5a:0:b0:51c:f898:60c7 with SMTP id 26-20020ac25f5a000000b0051cf89860c7mr9433lfz.2.1714989229548; Mon, 06 May 2024 02:53:49 -0700 (PDT) Date: Mon, 06 May 2024 09:53:22 +0000 In-Reply-To: <20240506-linked-list-v2-0-7b910840c91f@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240506-linked-list-v2-0-7b910840c91f@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=16225; i=aliceryhl@google.com; h=from:subject:message-id; bh=vHnMYoARsaSwT4DBkFiei47dRFIRkgVi3GBnqZ7Fb1o=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBmOKii9/z6QHpyaVxFSspJkvrMaPZ96AW1Gljrv 9wCTEpUG26JAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCZjioogAKCRAEWL7uWMY5 RjjnEAC6QgXCJfcFEPJXzUmNrSQ1qzDpfSmQGgwDSt+dPpsh+fZHv3cqPjj8da8nqSvCrcl4bnD h/eHUGG0wToYyditiT7C5Yz7sVVmuzjxMjLsYMkHyseLHx4QH1G6MFkEhLiTMTJ1vegz/ekBfMC zSkQ3KK90ix/BWWjsnT+AGWR3spr/td+DF1Rwy3Q0qYScbh48Dg5+s9qWCkCZvoN8FGDSujeCQ2 cJLHvCMb+jtJSD6Oh9Rj+YNSaCanyVo66w9KzIb4fozuKEcbGlhPgcYZdh3E7UxnHrGd77Z1xDp 0W3sHxc4wzhPhyymyZW71vgMczveXWrQJe+wuI522qGPR7FmNfc9a7fBFt4Zm6hdQzuadcVYQM2 eKlTgE3a0raDADTRWC5wnFkTb3O1L9rX8UNbujo2ok4VwFg7YBVagoYoJ8vN2ktrQe1ncVCpR7I SBYsRfD587lfXubbRDHELeL7cSwlI4m+kPTDYX41Xhn8zZiQHSV6YtySsvmG1IqUydi24pBdhg/ dnzTg/rdunBO7Cu29SuOs78N/Vdn2C27sjXDd90AO9LM8WUJV0AP/QDIoi/yUyIJyGPwJ6yhy97 B0rAFj55Bf9ovMZTIQnera3OWdUrJZDkxloljG1Vm3Mb88zkG44CfZ4CP3SsNmFkqxEAEmMiojZ MH6Rx5Q+2o3wQOg== X-Mailer: b4 0.13-dev-26615 Message-ID: <20240506-linked-list-v2-1-7b910840c91f@google.com> Subject: [PATCH v2 1/9] rust: list: add 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 , Kees Cook , 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 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable The `ListArc` type can be thought of as a special reference to a refcounted object that owns the permission to manipulate the `next`/`prev` pointers stored in the refcounted object. By ensuring that each object has only one `ListArc` reference, the owner of that reference is assured exclusive access to the `next`/`prev` pointers. When a `ListArc` is inserted into a `List`, the `List` takes ownership of the `ListArc` reference. There are various strategies for ensuring that a value has only one `ListArc` reference. The simplest is to convert a `UniqueArc` into a `ListArc`. However, the refcounted object could also keep track of whether a `ListArc` exists using a boolean, which could allow for the creation of new `ListArc` references from an `Arc` reference. Whatever strategy is used, the relevant tracking is referred to as "the tracking inside `T`", and the `ListArcSafe` trait (and its subtraits) are used to update the tracking when a `ListArc` is created or destroyed. Note that we allow the case where the tracking inside `T` thinks that a `ListArc` exists, but actually, there isn't a `ListArc`. However, we do not allow the opposite situation where a `ListArc` exists, but the tracking thinks it doesn't. This is because the former can at most result in us failing to create a `ListArc` when the operation could succeed, whereas the latter can result in the creation of two `ListArc` references. This patch introduces the `impl_list_arc_safe!` macro that allows you to implement `ListArcSafe` for types using the strategy where a `ListArc` can only be created from a `UniqueArc`. Other strategies are introduced in later patches. This is part of the linked list that Rust Binder will use for many different things. The strategy where a `ListArc` can only be created from a `UniqueArc` is actually sufficient for most of the objects that Rust Binder needs to insert into linked lists. Usually, these are todo items that are created and then immediately inserted into a queue. The const generic ID allows objects to have several prev/next pointer pairs so that the same object can be inserted into several different lists. You are able to have several `ListArc` references as long as they correspond to different pointer pairs. The ID itself is purely a compile-time concept and will not be present in the final binary. Both the `List` and the `ListArc` will need to agree on the ID for them to work together. Rust Binder uses this in a few places (e.g. death recipients) where the same object can be inserted into both generic todo lists and some other lists for tracking the status of the object. The ID is a const generic rather than a type parameter because the `pair_from_unique` method needs to be able to assert that the two ids are different. There's no easy way to assert that when using types instead of integers. Signed-off-by: Alice Ryhl --- rust/kernel/lib.rs | 1 + rust/kernel/list.rs | 8 ++ rust/kernel/list/arc.rs | 315 ++++++++++++++++++++++++++++++++++++++++++++= ++++ 3 files changed, 324 insertions(+) diff --git a/rust/kernel/lib.rs b/rust/kernel/lib.rs index 9a943d99c71a..51d007e031b2 100644 --- a/rust/kernel/lib.rs +++ b/rust/kernel/lib.rs @@ -33,6 +33,7 @@ pub mod ioctl; #[cfg(CONFIG_KUNIT)] pub mod kunit; +pub mod list; #[cfg(CONFIG_NET)] pub mod net; pub mod prelude; diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs new file mode 100644 index 000000000000..fb16ea43b2ba --- /dev/null +++ b/rust/kernel/list.rs @@ -0,0 +1,8 @@ +// SPDX-License-Identifier: GPL-2.0 + +// Copyright (C) 2024 Google LLC. + +//! A linked list implementation. + +mod arc; +pub use self::arc::{impl_list_arc_safe, ListArc, ListArcSafe}; diff --git a/rust/kernel/list/arc.rs b/rust/kernel/list/arc.rs new file mode 100644 index 000000000000..560ff07fe9b7 --- /dev/null +++ b/rust/kernel/list/arc.rs @@ -0,0 +1,315 @@ +// SPDX-License-Identifier: GPL-2.0 + +// Copyright (C) 2024 Google LLC. + +//! A wrapper around `Arc` for linked lists. + +use crate::alloc::{AllocError, Flags}; +use crate::prelude::*; +use crate::sync::{Arc, ArcBorrow, UniqueArc}; +use core::marker::Unsize; +use core::ops::Deref; +use core::pin::Pin; + +/// Declares that this type has some way to ensure that there is exactly o= ne `ListArc` instance for +/// this id. +pub trait ListArcSafe { + /// Informs the tracking inside this type that it now has a [`ListArc`= ] reference. + /// + /// This method may be called even if the tracking inside this type th= inks that a `ListArc` + /// reference exists. (But only if that's not actually the case.) + /// + /// # Safety + /// + /// Must not be called if a [`ListArc`] already exist for this value. + unsafe fn on_create_list_arc_from_unique(self: Pin<&mut Self>); + + /// Informs the tracking inside this type that there is no [`ListArc`]= reference anymore. + /// + /// # Safety + /// + /// Must only be called if there is no [`ListArc`] reference, but the = tracking thinks there is. + unsafe fn on_drop_list_arc(&self); +} + +/// Declares that this type supports [`ListArc`]. +/// +/// When using this macro, it will only be possible to create a [`ListArc`= ] from a [`UniqueArc`]. +#[macro_export] +macro_rules! impl_list_arc_safe { + (impl$({$($generics:tt)*})? ListArcSafe<$num:tt> for $t:ty { untracked= ; } $($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>) {} + unsafe fn on_drop_list_arc(&self) {} + } + $crate::list::impl_list_arc_safe! { $($rest)* } + }; + + () =3D> {}; +} +pub use impl_list_arc_safe; + +/// A wrapper around [`Arc`] that's guaranteed unique for the given id. +/// +/// The `ListArc` type can be thought of as a special reference to a refco= unted object that owns the +/// permission to manipulate the `next`/`prev` pointers stored in the refc= ounted object. By ensuring +/// that each object has only one `ListArc` reference, the owner of that r= eference is assured +/// exclusive access to the `next`/`prev` pointers. When a `ListArc` is in= serted into a `List`, the +/// `List` takes ownership of the `ListArc` reference. +/// +/// There are various strategies to ensuring that a value has only one `Li= stArc` reference. The +/// simplest is to convert a [`UniqueArc`] into a `ListArc`. However, the = refcounted object could +/// also keep track of whether a `ListArc` exists using a boolean, which c= ould allow for the +/// creation of new `ListArc` references from an [`Arc`] reference. Whatev= er strategy is used, the +/// relevant tracking is referred to as "the tracking inside `T`", and the= [`ListArcSafe`] trait +/// (and its subtraits) are used to update the tracking when a `ListArc` i= s created or destroyed. +/// +/// Note that we allow the case where the tracking inside `T` thinks that = a `ListArc` exists, but +/// actually, there isn't a `ListArc`. However, we do not allow the opposi= te situation where a +/// `ListArc` exists, but the tracking thinks it doesn't. This is because = the former can at most +/// result in us failing to create a `ListArc` when the operation could su= cceed, whereas the latter +/// can result in the creation of two `ListArc` references. +/// +/// # Invariants +/// +/// * Each reference counted object has at most one `ListArc` for each val= ue of `ID`. +/// * The tracking inside `T` is aware that a `ListArc` reference exists. +#[repr(transparent)] +pub struct ListArc +where + T: ListArcSafe + ?Sized, +{ + arc: Arc, +} + +impl, const ID: u64> ListArc { + /// Constructs a new reference counted instance of `T`. + #[inline] + pub fn new(contents: T, flags: Flags) -> Result { + Ok(Self::from_unique(UniqueArc::new(contents, flags)?)) + } + + /// Use the given initializer to in-place initialize a `T`. + /// + /// If `T: !Unpin` it will not be able to move afterwards. + // We don't implement `InPlaceInit` because `ListArc` is implicitly pi= nned. This is similar to + // what we do for `Arc`. + #[inline] + pub fn pin_init(init: impl PinInit, flags: Flags) -> Result + where + E: From, + { + Ok(Self::from_pin_unique(UniqueArc::try_pin_init(init, flags)?)) + } + + /// Use the given initializer to in-place initialize a `T`. + /// + /// This is equivalent to [`ListArc::pin_init`], since a [`ListArc`= ] is always pinned. + #[inline] + pub fn init(init: impl Init, flags: Flags) -> Result + where + E: From, + { + Ok(Self::from_unique(UniqueArc::try_init(init, flags)?)) + } +} + +impl ListArc +where + T: ListArcSafe + ?Sized, +{ + /// Convert a [`UniqueArc`] into a [`ListArc`]. + #[inline] + pub fn from_unique(unique: UniqueArc) -> Self { + Self::from_pin_unique(Pin::from(unique)) + } + + /// Convert a pinned [`UniqueArc`] into a [`ListArc`]. + #[inline] + pub fn from_pin_unique(mut unique: Pin>) -> Self { + // SAFETY: We have a `UniqueArc`, so there is no `ListArc`. + unsafe { T::on_create_list_arc_from_unique(unique.as_mut()) }; + let arc =3D Arc::from(unique); + // SAFETY: We just called `on_create_list_arc_from_unique` on an a= rc without a `ListArc`, + // so we can create a `ListArc`. + unsafe { Self::transmute_from_arc(arc) } + } + + /// Like [`from_unique`], but creates two `ListArcs`. + /// + /// The two ids must be different. + /// + /// [`from_unique`]: ListArc::from_unique + #[inline] + pub fn pair_from_unique(unique: UniqueArc) -> (Self= , ListArc) + where + T: ListArcSafe, + { + Self::pair_from_pin_unique(Pin::from(unique)) + } + + /// Like [`pair_from_unique`], but uses a pinned arc. + /// + /// The two ids must be different. + /// + /// [`pair_from_unique`]: ListArc::pair_from_unique + #[inline] + pub fn pair_from_pin_unique( + mut unique: Pin>, + ) -> (Self, ListArc) + where + T: ListArcSafe, + { + build_assert!(ID !=3D ID2); + + // SAFETY: We have a `UniqueArc`, so there is no `ListArc`. + unsafe { >::on_create_list_arc_from_unique(un= ique.as_mut()) }; + // SAFETY: We have a `UniqueArc`, so there is no `ListArc`. + unsafe { >::on_create_list_arc_from_unique(u= nique.as_mut()) }; + + let arc1 =3D Arc::from(unique); + let arc2 =3D Arc::clone(&arc1); + + // SAFETY: We just called `on_create_list_arc_from_unique` on an a= rc without a `ListArc` + // for both IDs (which are different), so we can create two `ListA= rc`s. + unsafe { + ( + Self::transmute_from_arc(arc1), + ListArc::transmute_from_arc(arc2), + ) + } + } + + /// Transmutes an [`Arc`] into a `ListArc` without updating the tracki= ng inside `T`. + /// + /// # Safety + /// + /// * The value must not already have a `ListArc` reference. + /// * The tracking inside `T` must think that there is a `ListArc` ref= erence. + #[inline] + unsafe fn transmute_from_arc(arc: Arc) -> Self { + // INVARIANT: By the safety requirements, the invariants on `ListA= rc` are satisfied. + Self { arc } + } + + /// Transmutes a `ListArc` into an [`Arc`] without updating the tracki= ng inside `T`. + /// + /// After this call, the tracking inside `T` will still think that the= re is a `ListArc` + /// reference. + #[inline] + fn transmute_to_arc(self) -> Arc { + // SAFETY: ListArc is repr(transparent). + unsafe { core::mem::transmute(self) } + } + + /// Convert ownership of this `ListArc` into a raw pointer. + /// + /// The returned pointer is indistinguishable from pointers returned b= y [`Arc::into_raw`]. The + /// tracking inside `T` will still think that a `ListArc` exists after= this call. + #[inline] + pub fn into_raw(self) -> *const T { + Arc::into_raw(Self::transmute_to_arc(self)) + } + + /// Take ownership of the `ListArc` from a raw pointer. + /// + /// # Safety + /// + /// * `ptr` must satisfy the safety requirements of [`Arc::from_raw`]. + /// * The value must not already have a `ListArc` reference. + /// * The tracking inside `T` must think that there is a `ListArc` ref= erence. + #[inline] + pub unsafe fn from_raw(ptr: *const T) -> Self { + // SAFETY: The pointer satisfies the safety requirements for `Arc:= :from_raw`. + let arc =3D unsafe { Arc::from_raw(ptr) }; + // SAFETY: The value doesn't already have a `ListArc` reference, b= ut the tracking thinks it + // does. + unsafe { Self::transmute_from_arc(arc) } + } + + /// Converts the `ListArc` into an [`Arc`]. + #[inline] + pub fn into_arc(self) -> Arc { + let arc =3D Self::transmute_to_arc(self); + // SAFETY: There is no longer a `ListArc`, but the tracking thinks= there is. + unsafe { T::on_drop_list_arc(&arc) }; + arc + } + + /// Clone a `ListArc` into an [`Arc`]. + #[inline] + pub fn clone_arc(&self) -> Arc { + self.arc.clone() + } + + /// Returns a reference to an [`Arc`] from the given [`ListArc`]. + /// + /// This is useful when the argument of a function call is an [`&Arc`]= (e.g., in a method + /// receiver), but we have a [`ListArc`] instead. + /// + /// [`&Arc`]: Arc + #[inline] + pub fn as_arc(&self) -> &Arc { + &self.arc + } + + /// Returns an [`ArcBorrow`] from the given [`ListArc`]. + /// + /// This is useful when the argument of a function call is an [`ArcBor= row`] (e.g., in a method + /// receiver), but we have an [`Arc`] instead. Getting an [`ArcBorrow`= ] is free when optimised. + #[inline] + pub fn as_arc_borrow(&self) -> ArcBorrow<'_, T> { + self.arc.as_arc_borrow() + } + + /// Compare whether two [`ListArc`] pointers reference the same underl= ying object. + #[inline] + pub fn ptr_eq(this: &Self, other: &Self) -> bool { + Arc::ptr_eq(&this.arc, &other.arc) + } +} + +impl Deref for ListArc +where + T: ListArcSafe + ?Sized, +{ + type Target =3D T; + + #[inline] + fn deref(&self) -> &Self::Target { + self.arc.deref() + } +} + +impl Drop for ListArc +where + T: ListArcSafe + ?Sized, +{ + #[inline] + fn drop(&mut self) { + // SAFETY: There is no longer a `ListArc`, but the tracking thinks= there is by the type + // invariants on `Self`. + unsafe { T::on_drop_list_arc(&self.arc) }; + } +} + +// This is to allow [`ListArc`] (and variants) to be used as the type of `= self`. +impl core::ops::Receiver for ListArc where T: Lis= tArcSafe + ?Sized {} + +// This is to allow coercion from `ListArc` to `ListArc` if `T` can = be converted to the +// dynamically-sized type (DST) `U`. +impl core::ops::CoerceUnsized> for Lis= tArc +where + T: ListArcSafe + Unsize + ?Sized, + U: ListArcSafe + ?Sized, +{ +} + +// This is to allow `ListArc` to be dispatched on when `ListArc` can= be coerced into +// `ListArc`. +impl core::ops::DispatchFromDyn> for L= istArc +where + T: ListArcSafe + Unsize + ?Sized, + U: ListArcSafe + ?Sized, +{ +} --=20 2.45.0.rc1.225.g2a3ae87e7f-goog From nobody Wed Dec 17 17:23:06 2025 Received: from mail-lf1-f73.google.com (mail-lf1-f73.google.com [209.85.167.73]) (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 017411428ED for ; Mon, 6 May 2024 09:53:53 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.167.73 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714989237; cv=none; b=Wa5uzgubDOKUf0LY6NPVpMWa2NA7kO6GlGgF08p1FH+Mqn8fzW/XDX5Abqxu8OG40OCVybeaX0CQY6gBhlBzOUnF2+DJDKxeD8SQLWIiTbQgRZ+mQ2whSakoEzfGM29hr7/rhQw4UDbP2x78D1QILmlicaQpZEsqT+ZK+oLYo44= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714989237; c=relaxed/simple; bh=wEG/4LvM1FI/4ihCHGAieLrKEgeQtI2G5Vod3tjzD4o=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=Nf1gllDF8mJLtArRncQTu65Fd9aoI0IkqzNgqjtx4nEs+zRxfJBD6qnZYPjrWCYswe5mS+PtPc+28QD0VF7QMKmLl+AO3qEj2cShBRamBHFAOnuVOigIMz634F4Mj3JCOAULiiAVUT1+rQ0zdRQ23Edk4dKvMDUJR1d74K7+S7c= 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=UAASI9gp; arc=none smtp.client-ip=209.85.167.73 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="UAASI9gp" Received: by mail-lf1-f73.google.com with SMTP id 2adb3069b0e04-51faceb0569so1315750e87.0 for ; Mon, 06 May 2024 02:53:53 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1714989232; x=1715594032; 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=sBucNw+Aee/R2s0jMV10I00Gxph4SAVWU7MXoG8D4tk=; b=UAASI9gpzr7nHvYXROaviRRih+MjD9MY6xVggCJyIXFMVNv5/5fFO+6Z3YgqgfytlJ lT8VoR/sFX8UvLftAsSSYgtYv7zjuZxgyKoKYNNgWMtAYG29tRAK9ltfWTdwjFPl2gea GtYhJOh4GDHB+u+BG8GVDtv+5u2/BDy2HiSpHD2hlFwQKYTr7lc/4N6hABAI69vbbvTE 4tEPkfnmJQIxIEPeUKKgC/7FiPXhrQjkPk/7vLcga0nzz5bq88+9Vk/FBCtppXUeOTOe 66xRlEl/GVP/tYnyqJMaUCb01Ro1bYm7IL5KzMWGDVMIvie10GRrL4u6iZqk2FV48XI6 nIgQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1714989232; x=1715594032; 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=sBucNw+Aee/R2s0jMV10I00Gxph4SAVWU7MXoG8D4tk=; b=pHcwB8JUDEb7G0keJjVfNJIw/MONy2XEwdl94YYCIl7DHDRYjsEZmegdBQ+eFWUaET Sj8kPySCUlMyCGMx9GyEDpQsMv42iLjnjLXT8VgQ9rpGlZtaDv4MqpJsUnmxqzf4IWte MQdKZP0brx5CKULR+bjsV9vI6GyZweUj4Br8lLKsMZsaSReLFQxNQ5bBfAHy8mskjB/P ZNLPvj5mHyZVR2iyDQ4cMCGCI1gyzGGs0m4BkABGMIJhZlBow2qR+ejpvKPR34adp0i7 WpkvhDI9918+ShUe7tiO5uOU/1B94lkXaw4wMOwx1wRKy5S4EX5I72V/+rEHtiiwkaaj O8xw== X-Forwarded-Encrypted: i=1; AJvYcCVSmpQQ4YO7uSmg36Zt5XnD1EYYy6LQ8Tllq0IDAo+mF0bOGvlKXXIPSYkVrDnCKg5Ix7sZnzIHokKwoMlMZbAIsSnvjGabLWSE4uDm X-Gm-Message-State: AOJu0YzM434j7pu9AnfE9GFN/xZ0kB8Yxu1WVAPdWwFjg07JNIxWcvIg uzCWRj2h1jXpbAd+YkVHw2DW9fQr1qhF9efpU6cb850Rr4zSbphYAR4pBFM9bbynZOtHY/1C6gg U7ORt7ZDw8GpNGQ== X-Google-Smtp-Source: AGHT+IGki79q6OvvlZmNS3ZbPOCMYVp/BCeI8OikYiJ7CZF8m6HgC3jU4faWa1+VYJknEc8hSDElMRrazQGQGsY= X-Received: from aliceryhl2.c.googlers.com ([fda3:e722:ac3:cc00:68:949d:c0a8:572]) (user=aliceryhl job=sendgmr) by 2002:ac2:47e4:0:b0:51c:58b0:88c7 with SMTP id b4-20020ac247e4000000b0051c58b088c7mr8790lfp.7.1714989232282; Mon, 06 May 2024 02:53:52 -0700 (PDT) Date: Mon, 06 May 2024 09:53:23 +0000 In-Reply-To: <20240506-linked-list-v2-0-7b910840c91f@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240506-linked-list-v2-0-7b910840c91f@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=10280; i=aliceryhl@google.com; h=from:subject:message-id; bh=wEG/4LvM1FI/4ihCHGAieLrKEgeQtI2G5Vod3tjzD4o=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBmOKij3g4OFT2vjHtirVw93Wukb7vYghJioTnxF oCSYdMeoOaJAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCZjioowAKCRAEWL7uWMY5 RvYyD/9PL8DfWduNHmw+Y+m9V/9YiNHtFIkqzLxmcybWkzVE5ST4lhnrE3Hn8FU6TnlXNTLm+dx HBBGfvhYzPOQfrMfuIiEsPa62+ZW2o946w79uZBuSlawfG+0DTg72sErwBxaPI8PtyoUqwmfmzU ch1y9fyPdhh77DzzK9ZwFQDF564vQMVS+Q6cg8SA1hQ1+RlBLb5FX4mJBtM8z+XW9hnZG+eB4rl aNIRGeiNgAqH9Z1qMEIwjn6Vrdqd78AY1UkR2Bs5XFHEK71ZR8IWAhRNP9OhMMxfdKlcFehbasf OQPhuhbd///bOOzcAfNVr5QNyMOD5nyfo2gLmKIX4+AKN1kirul9lmQIyeL30H/sTeSAjvEyGtw GzALJMqyouP5CiWtRCCAwGd0bW1o8nskjnfj9ezoFIgcXQVFY7QqdcBvzObGCwCq3nbSZJujZXC aaZZvb0yHE5qCdWlAz7mwzH1eWXKkcxZsBSh0eC0K3/Oed+pfT47a1t4Vz/yZ3DGcjqa/KIDiup bZUuzkqPv9BSPfEbDWNBH+BER83aJQKqmn9r7Tzhc0Rs7TdGL3CYEJlzWGJbXtXrLG815JhnWVk fWKxjoAac8i5rjVqi5DhWrxGNCzhmz99JBDdYfN7W/ca6Vy3SpnnZmjWK5FgO5OVZuQFlrxfofC opaBMp7AOQrvJ/w== X-Mailer: b4 0.13-dev-26615 Message-ID: <20240506-linked-list-v2-2-7b910840c91f@google.com> Subject: [PATCH v2 2/9] 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 , Kees Cook , 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 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. Signed-off-by: Alice Ryhl --- rust/kernel/list.rs | 4 +- rust/kernel/list/arc.rs | 154 ++++++++++++++++++++++++++++++++++++++++++++= +++- 2 files changed, 155 insertions(+), 3 deletions(-) diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs index fb16ea43b2ba..c5caa0f6105c 100644 --- a/rust/kernel/list.rs +++ b/rust/kernel/list.rs @@ -5,4 +5,6 @@ //! 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, AtomicListArcTracker, ListArc, ListArcSafe, TryNew= ListArc, +}; diff --git a/rust/kernel/list/arc.rs b/rust/kernel/list/arc.rs index 560ff07fe9b7..4c2e33f40597 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. @@ -32,9 +33,24 @@ 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 +/// +/// Implementers must ensure that `try_new_list_arc` does not return `true= ` if a `ListArc` already +/// exists. +pub unsafe trait TryNewListArc: ListArcSafe { + /// Attempts to convert an `Arc` into an `ListArc`. Return= s `true` if the + /// conversion was successful. + 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`]. +/// When using this macro, you may choose between the `untracked` strategy= where it is not tracked +/// whether a [`ListArc`] exists, and the `tracked_by` strategy where the = tracking is deferred to a +/// field of the struct. The `tracked_by` strategy can be combined with a = field of type +/// [`AtomicListArcTracker`] to track whether a [`ListArc`] exists. #[macro_export] macro_rules! impl_list_arc_safe { (impl$({$($generics:tt)*})? ListArcSafe<$num:tt> for $t:ty { untracked= ; } $($rest:tt)*) =3D> { @@ -45,6 +61,37 @@ 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>) { + // SAFETY: This field is structurally pinned. + 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; @@ -180,6 +227,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 the= tracking now thinks that + // a `ListArc` exists, so we can create one. + 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 the= tracking now thinks that + // a `ListArc` exists, so we can create one. + 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_pin= _unique), + } + } + /// Transmutes an [`Arc`] into a `ListArc` without updating the tracki= ng inside `T`. /// /// # Safety @@ -313,3 +406,60 @@ 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 AtomicListArcTracker { + inner: AtomicBool, + _pin: PhantomPinned, +} + +impl AtomicListArcTracker { + /// 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 AtomicListArcTracker { + 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 AtomicListArcTracker { + 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.45.0.rc1.225.g2a3ae87e7f-goog From nobody Wed Dec 17 17:23:06 2025 Received: from mail-yw1-f202.google.com (mail-yw1-f202.google.com [209.85.128.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 D2AEA143899 for ; Mon, 6 May 2024 09:53:55 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.202 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714989238; cv=none; b=R+ZCfQO9eQJbr8ah0Eq0YZPU2ulObAa1adVnG8QtIQtQMWgh+QiS+mxeTClIFmWyR5FCSgb8Z61l3E8+aQKCrvRMZSu3X800YowHAgsIUuIcImEnIfND3vhntg9HJc7PqNJ0Jz+Qg9GQwaDaiTesSBAdwz4TfdNcbg8dlRBWIMQ= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714989238; c=relaxed/simple; bh=TkDDAEioQS5e03PClrJNkUWgCunwLczUs3+Rw4vQtIE=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=kBqdIo0UMWRcXLgasYolTq64edawas3DZ3GiS8xYrEN8ZQxmyMekynVpOP0LV3mhJIdBABAWcWyKXBfH7S2YtIwwJhUUOBKQif4pJsaBfpfeVog5xtcU6FPSnHgAbzcYxQCxTKpGAYif1H0nfZ8lu0ZTwbMD+zcp+QkXVNOBwZw= 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=UteJOBMW; arc=none smtp.client-ip=209.85.128.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--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="UteJOBMW" Received: by mail-yw1-f202.google.com with SMTP id 00721157ae682-61b1200cc92so33646967b3.0 for ; Mon, 06 May 2024 02:53:55 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1714989235; x=1715594035; 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=lqcGn7n9nLKSxOtaoBrT7a751lVSlam8EM5dcqR6dvA=; b=UteJOBMWma9UiHRkM93Z/0/P2llsNgTGaswPhVt7Fqw4qzFtBis4yio7R3tEiR+eXl GeecBPnO3ojr+JeNXNqj3wO0Sh1tIHnS/NwaFZy3fK4oIS75MrYQ04LZES+7mgXinQx0 dJF4D4Yx32LKpT9nIZlcvIsu3bZ8otPm5x9zo9VgmjYelHvpODxaztAzqxu0c0Tc67Ek 0QHR2DW5AcSfL6S3bn8IzIXPIzjlt4od5TfBe8HNh1ltoPkEm66ndZSsfTX3ZNzir8X4 WYRCS+FKAraXiMCu0mpXoqf1gnqflyQJrw0BqW65auhiK8/FL6Yg+MXNVtieIemVK6gi HyEw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1714989235; x=1715594035; 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=lqcGn7n9nLKSxOtaoBrT7a751lVSlam8EM5dcqR6dvA=; b=H5Qvk2Vdz3MYMnzc40MweV00qb2ZmaQJvL7DI9brZEnDiRmrV976sVk3tGu+jvaRX9 VUxo5N5GJD5CM4x5R8G69Fep3gFh2Q3JPd2nrkHS0YPB8Yl8BWRuA8+wwq+0aB4ksGVV /gIC2vU6pb0t4tUDMvF3qLCi71wYMMqQdbggMT0H7S3FrN/Y89tUN7P8R7X7N//xYPux BCltbjiJI9hldKV/aDqPyswJcBPCxIva1dWdJOEA2uJqeWaiBM0NUavVQ0nRIIHGoMTy 9pjNozrZGTmuKEAIsBhM04NarkwGVO0h4RJG1KR21nY8o2cgYPJ2NM1DYVw1+TV9wkfv IoOQ== X-Forwarded-Encrypted: i=1; AJvYcCXLalVbqUpi41t6/a0OH1Mwc3BsK2Ywnpw+0ldVb/k9zmkpa3+1ymBLNbu1woYaDfofMpWQIehgX3Fre/RP0d4qb47I85Z1zUPGcJmH X-Gm-Message-State: AOJu0Yxivvbu9dXNR74DP6fcmczg6MgAGO06fb6cd2PDtvJr7/hvRxXu LZ3CujCzxQUOvx7T5Uhs8a8ismXkQYyAJac9DfT4ic6EU1VwktV/ca9ipx+sEFUFRlWWPaJNaGC 39lgQ+0CbudLCbg== X-Google-Smtp-Source: AGHT+IH8VHArxLC8vBNsOdEy5JvL2q153l3s3tin9/zAezvqCYlbXmRLADvQwGaR+3klAMQbvFTzSioQ3TQs8Zw= X-Received: from aliceryhl2.c.googlers.com ([fda3:e722:ac3:cc00:68:949d:c0a8:572]) (user=aliceryhl job=sendgmr) by 2002:a0d:e2cb:0:b0:61b:ec66:b8e6 with SMTP id l194-20020a0de2cb000000b0061bec66b8e6mr2665283ywe.8.1714989234921; Mon, 06 May 2024 02:53:54 -0700 (PDT) Date: Mon, 06 May 2024 09:53:24 +0000 In-Reply-To: <20240506-linked-list-v2-0-7b910840c91f@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240506-linked-list-v2-0-7b910840c91f@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=5975; i=aliceryhl@google.com; h=from:subject:message-id; bh=TkDDAEioQS5e03PClrJNkUWgCunwLczUs3+Rw4vQtIE=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBmOKijC6Aiz2Bj0crXUAGLYj/j/lO6i+M8dlMoo AKkJhs/eziJAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCZjioowAKCRAEWL7uWMY5 RmuVD/0ZKaaI3qmhkVGuDCwOk0UTE7IoWyqZ19QsGRYIZm5kZJCL5CaHA5LOsGLT431L5dCMCJa lCchL7/vssNV07q5Lu+NaFTScSLnmORzEwLB2WpE6TVnrVOiiG/+g/tLURyIV1TR8L2KpvjCaJy 1qtgof3wBfz+h5QAyKgbLjLRCAntmlMEFCGUG+Rw4NG4lMpctJxkGOno2QQ3+ADsWFBX0LEInhe Xp6L0hTg2j2wLIYBlRhxb4ObWSnWGTREXTDNVzqJ+SywnQlqfAKEFiRDO8+uSM7Oc/zDAd4kaIu sy6ApTEtZhlTF7ZS8SC5tRgpPLzj6zg313b6mmRJX04RlAuiI/InUs+WwKWPVqq3AAwNZDKIIBi WXvCnR29c+XmZDb8o5h3eMQx8c/L5hriGibwcnrJ0ot3giYKsQpZpLCpItdRlpJoMUKn9pydTZw xEiChaw5Ek9k6/c0dgs+NcxwEooKiKRWqegwvI4znDDhqs47kGGGyesEH52LFoYWabEXgBElkck OL3zCqER5qoUDCDiBKoyGfvT2sC6D0uxwa7YPkSXNa2Z6rPdGj/rqDYTnF3H1qnDA4rrDWX9p2d 0VEudKxejsAH/kgg3fORoUc7CJd9RebNqJmhc8jfsRWR7gH1I1LWkhV3M5esdQ+Js4rcVrskmjG iZw+mvS+4aiEaFQ== X-Mailer: b4 0.13-dev-26615 Message-ID: <20240506-linked-list-v2-3-7b910840c91f@google.com> Subject: [PATCH v2 3/9] rust: list: add struct with prev/next pointers 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 , Kees Cook , 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 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Define the ListLinks struct, which wraps the prev/next pointers that will be used to insert values into a List in a future patch. Also define the ListItem trait, which is implemented by structs that have a ListLinks field. The ListItem trait provides four different methods that are all essentially container_of or the reverse of container_of. Two of them are used before inserting/after removing an item from the list, and the two others are used when looking at a value without changing whether it is in a list. This distinction is introduced because it is needed for the patch that adds support for heterogeneous lists, which are implemented by adding a third pointer field with a fat pointer to the full struct. When inserting into the heterogeneous list, the pointer-to-self is updated to have the right vtable, and the container_of operation is implemented by just returning that pointer instead of using the real container_of operation. Signed-off-by: Alice Ryhl --- rust/kernel/list.rs | 116 ++++++++++++++++++++++++++++++++++++++++++++++++= ++++ 1 file changed, 116 insertions(+) diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs index c5caa0f6105c..b5cfbb96a392 100644 --- a/rust/kernel/list.rs +++ b/rust/kernel/list.rs @@ -4,7 +4,123 @@ =20 //! A linked list implementation. =20 +use crate::init::PinInit; +use crate::types::Opaque; +use core::ptr; + mod arc; pub use self::arc::{ impl_list_arc_safe, AtomicListArcTracker, ListArc, ListArcSafe, TryNew= ListArc, }; + +/// Implemented by types where a [`ListArc`] can be inserted into a = `List`. +/// +/// # Safety +/// +/// Implementers must ensure that they provide the guarantees documented o= n the three methods +/// below. +/// +/// [`ListArc`]: ListArc +pub unsafe trait ListItem: ListArcSafe { + /// Views the [`ListLinks`] for this value. + /// + /// # Guarantees + /// + /// If there is a previous call to `prepare_to_insert` and there is no= call to `post_remove` + /// since the most recent such call, then this returns the same pointe= r as the one returned by + /// the most recent call to `prepare_to_insert`. + /// + /// Otherwise, the returned pointer points at a read-only [`ListLinks`= ] with two null pointers. + /// + /// # Safety + /// + /// The provided pointer must point at a valid value. (It need not be = in an `Arc`.) + unsafe fn view_links(me: *const Self) -> *mut ListLinks; + + /// View the full value given its [`ListLinks`] field. + /// + /// Can only be used when the value is in a list. + /// + /// # Guarantees + /// + /// * Returns the same pointer as the one passed to the previous call = to `prepare_to_insert`. + /// * The returned pointer is valid until the next call to `post_remov= e`. + /// + /// # Safety + /// + /// * The provided pointer must originate from the previous call to `p= repare_to_insert`, or + /// from a call to `view_links` that happened after the previous cal= l to `prepare_to_insert`. + /// * Since the previous call to `prepare_to_insert`, the `post_remove= ` method must not have + /// been called. + unsafe fn view_value(me: *mut ListLinks) -> *const Self; + + /// This is called when an item is inserted into a `List`. + /// + /// # Guarantees + /// + /// The caller is granted exclusive access to the returned [`ListLinks= `] until `post_remove` is + /// called. + /// + /// # Safety + /// + /// * The provided pointer must point at a valid value in an [`Arc`]. + /// * Calls to `prepare_to_insert` and `post_remove` on the same value= must alternate. + /// * The caller must own the [`ListArc`] for this value. + /// * The caller must not give up ownership of the [`ListArc`] unless = `post_remove` has been + /// called after this call to `prepare_to_insert`. + /// + /// [`Arc`]: crate::sync::Arc + unsafe fn prepare_to_insert(me: *const Self) -> *mut ListLinks; + + /// This undoes a previous call to `prepare_to_insert`. + /// + /// # Guarantees + /// + /// The returned pointer is the pointer that was originally passed to = `prepare_to_insert`. + /// + /// The caller is free to recreate the `ListArc` after this call. + /// + /// # Safety + /// + /// The provided pointer must be the pointer returned by the previous = call to + /// `prepare_to_insert`. + unsafe fn post_remove(me: *mut ListLinks) -> *const Self; +} + +#[repr(C)] +#[derive(Copy, Clone)] +struct ListLinksFields { + next: *mut ListLinksFields, + prev: *mut ListLinksFields, +} + +/// The prev/next pointers for an item in a linked list. +/// +/// # Invariants +/// +/// The fields are null if and only if this item is not in a list. +#[repr(transparent)] +pub struct ListLinks { + #[allow(dead_code)] + inner: Opaque, +} + +// SAFETY: The next/prev fields of a ListLinks can be moved across thread = boundaries. +unsafe impl Send for ListLinks {} +// SAFETY: The type is opaque so immutable references to a ListLinks are u= seless. Therefore, it's +// okay to have immutable access to a ListLinks from several threads at on= ce. +unsafe impl Sync for ListLinks {} + +impl ListLinks { + /// 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`. + ListLinks { + inner: Opaque::new(ListLinksFields { + prev: ptr::null_mut(), + next: ptr::null_mut(), + }), + } + } +} --=20 2.45.0.rc1.225.g2a3ae87e7f-goog From nobody Wed Dec 17 17:23:06 2025 Received: from mail-lj1-f202.google.com (mail-lj1-f202.google.com [209.85.208.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 B47B1143C72 for ; Mon, 6 May 2024 09:53:59 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.208.202 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714989241; cv=none; b=bEg9TZx7lqTOHnZHMPH8kXpQ2VtvcI90u/rvVxvlaOqcsb3XFLEWVg1cMT3zzHhJFYeJqdFV7mpnmZYXIdzDGR6ndytt5Jw8xQRzm0b0N/KfMf5c+/jsflRY+yqQwY6E5sG0m1QeLv/q9XXsAkYXa2S9UEHzvSWuC7BxVU2vJBo= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714989241; c=relaxed/simple; bh=AQhfweFhnbUEdO8w4wLgrf3c6x33991wxbRZ8aSauR0=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=l2aWBu+LNV8YOi1M7Xo77jwUkZt2tct2fZcH6var8R6KIMHRTSryAB3wI05NN4wpD+hPS9P6r1fdsWGOW3Jw3Ce4EgRcyKMTy0OJmCX5TjM751VKpmR6PWL6rgJTWhNhGpConaQEbnu5eCnRVRus/u6dlRsze1lmfB07LNSQ+mk= 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=PyL+KxPI; arc=none smtp.client-ip=209.85.208.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--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="PyL+KxPI" Received: by mail-lj1-f202.google.com with SMTP id 38308e7fff4ca-2e0b27cc8adso14906171fa.2 for ; Mon, 06 May 2024 02:53:59 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1714989238; x=1715594038; 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=0HDgKyqrf1g6QA5xH2PIc9zQKl9yIACvI9lzt3McvSs=; b=PyL+KxPIMQuvxhVyf4+G7MAxJwbI6mDXKNBzTRjquudc5+Db3mUIrNPqRB6NTuPdT1 JJwsiyeRMW81rZHs2A4tafeyQEpBz9lj4AQ9zy9m7Q+LQG/UkBl5M6Cfd9qID4iv1DX6 LY8iU5GfxCXMTiAXfoM9Vk1LlkgVO6cAF4MiqPJS6VVHXa51CduY+SW5LohS7KUUDKtt K11QigP2CrOYemHHryCulGspLAnJ3mvEnYMDWXVS001TpMEXkMNkfRb/IIXSntwXX3VC Ry2t8KXpxG6ZLbITx8IlU6UTgEIB6EMMEy5XWOFecq6THoDNXZ9+lqsAuspvIWDCYBlm HMwg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1714989238; x=1715594038; 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=0HDgKyqrf1g6QA5xH2PIc9zQKl9yIACvI9lzt3McvSs=; b=GkOUdJIhY0pYuBhA4TDf2LBq0eJrg03CNpJZ8HpWNgVrk/Z5bCJonsQ4g//M0Q2Ffn t2/9r6agjZH2++8au7x2fG99LNcly38AN7tEAB196okZtxj+zX2lEMcY0ob9DPWijt5I E78hrH5rrlMucL2Ouqr95N1TDQMiiB6K3Tf6QC8JSEsxxETHteMrPV299W7Lp9TLpeHY VXIsr5/Im939APSgTOe6CQI4vG9hfcY1R7x79AAWNVEl2mNmYqMBdGb6NxR8H4z/d2YH TSE6RUULoXDuKEgwkFH1erZl0Icv9xb7tC54AKQOjeVi8erRengbw5L+XZqmt2rrE39H X3yQ== X-Forwarded-Encrypted: i=1; AJvYcCUgxQpDyYbRBW/wTapLLEgwGVq+wOaYxQ/EWL146zgwbNf/SNsngvqPCB3/Tggi2Ud0wGRIFUx3JxyHhib9yecwArjhI6OOHojpAgci X-Gm-Message-State: AOJu0YzUg5hDFJDfuRGgyFl/yNBS69PDGDyorRw4Jjf4bJ+X3kHHrSnu PSgkM7NH17uccXFwWaJSpsA5DTw2KawqBDRn2icyetOhpIhUBz+5Dp5X1+Erbimyx81rymztgDY 7TwejIrKRUeqA6A== X-Google-Smtp-Source: AGHT+IGNkPUvZDfv8Muh0vJIt7Qzvxw4vZDYmCbaL7a0TKZS5EwrL7++O9rgzIs5//mviQFixGJmJKJl7nRtNGE= X-Received: from aliceryhl2.c.googlers.com ([fda3:e722:ac3:cc00:68:949d:c0a8:572]) (user=aliceryhl job=sendgmr) by 2002:a2e:874f:0:b0:2e2:a85f:f232 with SMTP id q15-20020a2e874f000000b002e2a85ff232mr5284ljj.1.1714989237613; Mon, 06 May 2024 02:53:57 -0700 (PDT) Date: Mon, 06 May 2024 09:53:25 +0000 In-Reply-To: <20240506-linked-list-v2-0-7b910840c91f@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240506-linked-list-v2-0-7b910840c91f@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=5039; i=aliceryhl@google.com; h=from:subject:message-id; bh=AQhfweFhnbUEdO8w4wLgrf3c6x33991wxbRZ8aSauR0=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBmOKikDG5fFa1vHK0LfQrvwgWciUW8TFr1x2Kk7 v7KeahV8muJAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCZjiopAAKCRAEWL7uWMY5 Rs9xD/0R8N8eEZPros8IjHgRQIWEHkiNNlUd7igWD9IBbfnkALm7gfUMrH2IW+u3XET8IATQoE7 3LV38vurNu3Kvce25pDQY9P72MYAOtDWuYt+OgxzTwSg0NCpWJBHljdjrezy9eOxXa5eSnslfsz LntlV7zuncAJNPVcPLGoH0QSx/UeybxjsUXA/CV6R0XS/PBXRd7ymfc1MqTv6dEmDR0H0XS9Gsx VV3T2hY7gsxdHPtvwYc0opJewYGqnBwzaGaBgJCMdHbLI2DkSBufqviq1j+fc6CNOnsjxR1uFQn UTnwXi/26INj4vZD/g8N349nL1A4EXrTdop2Pp8/Rd+RjLjZw9w11YCKLa84fj2JtKe6mFLO98H zOqoe+pUwQCSxsBXHEMR9mc6bnIIFQ0UxUHn7c+lYk0UiND4qqtKx5gONDjA1XNanpSiJfoYDRn C24kIfNtVjxxEtX+kgK/avwtf34neLv7sSmCcEYQ4BdQVwuDb3yMcWe7qxze8qMm8lb13L7uBp4 yvvEGCSeTx6jlpSw0wCuOuLW29kKQSTV5WpmKHeTebQNSC0AqeCH9ThfdcYM1o+VwlasLzJSWdb dwZT3CGiCU9g5JUxGA0TAE8REB9Wa0YKXFYXtI65+TXNjt2sSwLuJXOxTIZtcrAahMiy0ac/DN4 yVaTGpI12GkDxfQ== X-Mailer: b4 0.13-dev-26615 Message-ID: <20240506-linked-list-v2-4-7b910840c91f@google.com> Subject: [PATCH v2 4/9] rust: list: add macro for implementing ListItem 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 , Kees Cook , 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 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Adds a macro for safely implementing the ListItem trait. As part of the implementation of the macro, we also provide a HasListLinks trait similar to the workqueue's HasWorkItem trait. The HasListLinks trait is only necessary if you are implementing ListItem using the impl_list_item macro. Signed-off-by: Alice Ryhl --- rust/kernel/list.rs | 3 ++ rust/kernel/list/impl_list_item_mod.rs | 99 ++++++++++++++++++++++++++++++= ++++ 2 files changed, 102 insertions(+) diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs index b5cfbb96a392..f2eca542e090 100644 --- a/rust/kernel/list.rs +++ b/rust/kernel/list.rs @@ -8,6 +8,9 @@ use crate::types::Opaque; use core::ptr; =20 +mod impl_list_item_mod; +pub use self::impl_list_item_mod::{impl_has_list_links, impl_list_item, Ha= sListLinks}; + mod arc; pub use self::arc::{ impl_list_arc_safe, AtomicListArcTracker, ListArc, ListArcSafe, TryNew= ListArc, diff --git a/rust/kernel/list/impl_list_item_mod.rs b/rust/kernel/list/impl= _list_item_mod.rs new file mode 100644 index 000000000000..3ff483be89d1 --- /dev/null +++ b/rust/kernel/list/impl_list_item_mod.rs @@ -0,0 +1,99 @@ +// SPDX-License-Identifier: GPL-2.0 + +// Copyright (C) 2024 Google LLC. + +//! Helpers for implementing list traits safely. + +use crate::list::ListLinks; + +/// Declares that this type has a `ListLinks` field at a fixed offset. +/// +/// This trait is only used to help implement `ListItem` safely. If `ListI= tem` is implemented +/// manually, then this trait is not needed. +/// +/// # Safety +/// +/// All values of this type must have a `ListLinks` field at the given= offset. +pub unsafe trait HasListLinks { + /// The offset of the `ListLinks` field. + const OFFSET: usize; + + /// Returns a pointer to the [`ListLinks`] field. + /// + /// # Safety + /// + /// The provided pointer must point at a valid struct of type `Self`. + /// + /// [`ListLinks`]: ListLinks + // We don't really need this method, but it's necessary for the implem= entation of + // `impl_has_work!` to be correct. + #[inline] + unsafe fn raw_get_list_links(ptr: *mut Self) -> *mut ListLinks { + // SAFETY: The caller promises that the pointer is valid. The impl= ementer promises that the + // `OFFSET` constant is correct. + unsafe { (ptr as *mut u8).add(Self::OFFSET) as *mut ListLinks } + } +} + +/// Implements the [`HasListLinks`] trait for the given type. +#[macro_export] +macro_rules! impl_has_list_links { + ($(impl$(<$($implarg:ident),*>)? + HasListLinks$(<$id:tt>)? + for $self:ident $(<$($selfarg:ty),*>)? + { self$(.$field:ident)* } + )*) =3D> {$( + // SAFETY: The implementation of `raw_get_list_links` only compile= s if the field has the + // right type. + unsafe impl$(<$($implarg),*>)? $crate::list::HasListLinks$(<$id>)?= for + $self $(<$($selfarg),*>)? + { + const OFFSET: usize =3D ::core::mem::offset_of!(Self, $($field= ).*) as usize; + + #[inline] + unsafe fn raw_get_list_links(ptr: *mut Self) -> *mut $crate::l= ist::ListLinks$(<$id>)? { + // SAFETY: The caller promises that the pointer is not dan= gling. + unsafe { + ::core::ptr::addr_of_mut!((*ptr)$(.$field)*) + } + } + } + )*}; +} +pub use impl_has_list_links; + +/// Implements the [`ListItem`] trait for the given type. +/// +/// Assumes that the type implements [`HasListLinks`]. +/// +/// [`ListItem`]: crate::list::ListItem +#[macro_export] +macro_rules! impl_list_item { + ( + impl$({$($generics:tt)*})? $crate::list::ListItem<$num:tt> for $t:= ty { + using ListLinks; + } $($rest:tt)* + ) =3D> { + unsafe impl$(<$($generics)*>)? $crate::list::ListItem<$num> for $t= { + unsafe fn view_links(me: *const Self) -> *mut $crate::list::Li= stLinks<$num> { + unsafe { + >::raw_get_li= st_links(me.cast_mut()) + } + } + + unsafe fn view_value(me: *mut $crate::list::ListLinks<$num>) -= > *const Self { + let offset =3D >:= :OFFSET; + unsafe { (me as *const u8).sub(offset) as *const Self } + } + + unsafe fn prepare_to_insert(me: *const Self) -> *mut $crate::l= ist::ListLinks<$num> { + unsafe { >::view_link= s(me) } + } + + unsafe fn post_remove(me: *mut $crate::list::ListLinks<$num>) = -> *const Self { + unsafe { >::view_valu= e(me) } + } + } + }; +} +pub use impl_list_item; --=20 2.45.0.rc1.225.g2a3ae87e7f-goog From nobody Wed Dec 17 17:23:06 2025 Received: from mail-lf1-f73.google.com (mail-lf1-f73.google.com [209.85.167.73]) (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 7EDFF144313 for ; Mon, 6 May 2024 09:54:02 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.167.73 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714989244; cv=none; b=ehbMu9A/rRwL45xp/eje2lRuxrrNJXT7j4+PEoEDsvdzGQmjLHRG3YhEO6MtMLBbjvzuTNr+4L0je3hzWd1lwI+bvDSzCKrjD5paKv9qpBAaK4MbuOfTyvUOGVBNkDmPNZVIZQbNel9FKSKv//jlcp7aU1VPK3X92FOt9SrWfTI= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714989244; c=relaxed/simple; bh=L5UFSlBhqwQO+d3A4n2UzNrPer5KrDqp0xRe83Kkd9Y=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=Qsh2YLyNikeljEB3ocTP/gwQbqsA4AzvqE1NM0QOmwRnAPTSv7X3gQxMiqWmZQnUUxrBqbWDdBKfFWlXlA17kOvPl3MOyqNX0M6wIjcufAnEmt7n4LWH09nG+XxjcQkAIc8mnSGJLwyJY3xwQioj2LoiaRhVhaxtHKjgxjXkjBY= 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=PfkUORsV; arc=none smtp.client-ip=209.85.167.73 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="PfkUORsV" Received: by mail-lf1-f73.google.com with SMTP id 2adb3069b0e04-51f8cf57f17so1238559e87.1 for ; Mon, 06 May 2024 02:54:02 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1714989241; x=1715594041; 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=9/hIlTV0Cti9dUdSzkNL3rnm4RrYlyBh4GBegjEt7JM=; b=PfkUORsVQRlg2BXxJgWyknxSktQdF+BHliP/ukBvOSTPHUyGOM77raFEkasreIP3GZ ruVogJHyqjeCfWPO2HLxyFsFDLYat2/u/4Qcp+YZ6l7uqtEB90YDAIhFN+Zy92BHsKdn BLj8bSDWh6SU7FjmG0o79kDSRfYoyn0p6t1knjcTkZV4saPCtAH1GcY5ZMs3DVTEEhTZ oEzLpqY4xAkc88kXC0UaO4Gfx35go3gnbUNXUBoSR8tZOBxQ5QwuN4XbwWTyYLf+uScr SJrByejyUsNrAvKtPtM9pxJwbZjRDavWY6TPZHeeFUNi7TvHKYm/fkkomTruv9TOZ2oG Sd8A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1714989241; x=1715594041; 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=9/hIlTV0Cti9dUdSzkNL3rnm4RrYlyBh4GBegjEt7JM=; b=Yo3QzjcNsLxHka24pfgRuBsGF0p8y8+XCwXuolDhx9EDA7oaiqqkMSwouC7mXbkhd8 wmCStO+mxagv3fOLepkRIN2hDbEkr7/FAqSJCJY6NNqKIoCwAejLbaZZKF1eO/U5JOpH p366NZcFbji4K5zaD1/h9UdEYrxeCsnM5puW51UAhgWBxJmJUhTE8bifZyShfHxIDBqj RTlZ55WF4Dex1bWz9Fk85pL3i18B4InksSvcgxUmwBaVVMcMSrRCMErUQOVtBqHtC8ep qz2UFRCIn72O4h0hoI7ZI26rranP/cc7UhJe1YyUaoIa2g6Hw4rZb8OspwRq/YmEjqPw 0/nQ== X-Forwarded-Encrypted: i=1; AJvYcCXFtk80SFqNquxTfhU2XnwS5T2qj/JAT1/sL3AgYzg0pHugfiWKSuv8279fDwujsTXBQtVZ+zP11pV0IZ7qqrLohPYAfLxwxMOEOAL7 X-Gm-Message-State: AOJu0Yyfaw5yaysdBk6M+lpds/b1tHogND8JXV6BwRfbhoJQVkMaD/ax e8IBVj3DbPscGXwgoTfFGR/zpMU0DJWG+GOAZTu9W9OkdfU7v7rN0b20APvjPW+EtqmOEFOj2eN GiM9uKKDA17Ey2A== X-Google-Smtp-Source: AGHT+IEWh+aqbvkbADDKXhGpa1qPZiaehDx0ZtZmmOgj77WAY8+UW+giS2V39r0x2uqJGwSYlkfBShhy1sNQB7k= X-Received: from aliceryhl2.c.googlers.com ([fda3:e722:ac3:cc00:68:949d:c0a8:572]) (user=aliceryhl job=sendgmr) by 2002:a05:6512:4008:b0:51d:5d23:3ea8 with SMTP id br8-20020a056512400800b0051d5d233ea8mr9316lfb.6.1714989240682; Mon, 06 May 2024 02:54:00 -0700 (PDT) Date: Mon, 06 May 2024 09:53:26 +0000 In-Reply-To: <20240506-linked-list-v2-0-7b910840c91f@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240506-linked-list-v2-0-7b910840c91f@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=18797; i=aliceryhl@google.com; h=from:subject:message-id; bh=L5UFSlBhqwQO+d3A4n2UzNrPer5KrDqp0xRe83Kkd9Y=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBmOKilbVysmzce52eUOaFAKrk3RP1luXmGGAb7s RrIV9Buf02JAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCZjiopQAKCRAEWL7uWMY5 Rv9hD/9XbFFx9f6Cv0K18UeqAV6fOt+MuFg2q8FZ+lP5lJIZrN5PERgTFybT5OLfCHRi9xQ8lIQ BYzx9Ssr1cWG6YDiPoqJKZdpfg0ZwgdUeLsXwg96sNtzoKh4h6X7qONVRzzDoGbT6o3iScfg6lA 5fuRwy7bN3X23SDIDlsLjrmxFvkMd2ZmM2QEQuMZpEoyNZ7MQ4aggq6/K8YZ8xV64FCVHzHKOhy 4spv8LsERKR43K0T1Aue3nEpUFC7ZQ2YfXMbHepsIhwCMdmjdTbMYRGHzHspa2IsMUcKUesZzKb DTRLtPaKFcsro/6EufmW3U//HYUtuprbwyfNEhYa9C+b+mHcNSy3QMy1FxftagU3JcNltVMegXz eN/9RzmnmAWowbhy9i2GtdG/3yZPgPOr5yWxLZp+Decbh39PZ4WVQdQDUJMjjxLwbf9tCBVZBN6 y+6D/D7xbzTjRDFxLpsGLF9fXzwSI9pfl0u112nc1OD+vsvtyHMo0G4WZgjsq+icqXlYEoVhD+U Co3pksMtK9Eq3zMUTvHF7/mzIXyFnoiS1rdG1NYpnEN41+xDhbyMPKTCz97Zh/lKmkiInpQRFvk 3R4UX/vbAhInWbx2NsmatIxBw/gx9+0Wwcu0SYL1ki8gswxz4VyL809f0YsHuLQYssL5P0dGVIW VFCoemhEjS/jWRQ== X-Mailer: b4 0.13-dev-26615 Message-ID: <20240506-linked-list-v2-5-7b910840c91f@google.com> Subject: [PATCH v2 5/9] rust: list: add List 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 , Kees Cook , 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 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Add the actual linked list itself. The linked list uses the following design: The List type itself just has a single pointer to the first element of the list. And the actual list items then form a cycle. So the last item is `first->prev`. This is slightly different from the usual kernel linked list. Matching that exactly would amount to giving List two pointers, and having it be part of the cycle of items. This alternate design has the advantage that the cycle is never completely empty, which can reduce the number of branches in some cases. However, it also has the disadvantage that List must be pinned, which this design is trying to avoid. Having the list items form a cycle rather than having null pointers at the beginning/end is convenient for several reasons. For one, it lets us store only one pointer in List, and it simplifies the implementation of several functions. Unfortunately, the `remove` function that removes an arbitrary element from the list has to be unsafe. This is needed because there is no way to handle the case where you pass an element from the wrong list. For example, if it is the first element of some other list, then that other list's `first` pointer would not be updated. Similarly, it could be a data race if you try to remove it from two different lists in parallel. (There's no problem with passing `remove` an item that's not in any list. Additionally, other removal methods such as `pop_front` need not be unsafe, as they can't be used to remove items from another list.) Signed-off-by: Alice Ryhl --- rust/kernel/list.rs | 329 ++++++++++++++++++++++++++++++++++++++++++++= +++- rust/kernel/list/arc.rs | 6 +- 2 files changed, 330 insertions(+), 5 deletions(-) diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs index f2eca542e090..d0ff29a3e5d1 100644 --- a/rust/kernel/list.rs +++ b/rust/kernel/list.rs @@ -6,6 +6,7 @@ =20 use crate::init::PinInit; use crate::types::Opaque; +use core::marker::PhantomData; use core::ptr; =20 mod impl_list_item_mod; @@ -16,7 +17,40 @@ impl_list_arc_safe, AtomicListArcTracker, ListArc, ListArcSafe, TryNew= ListArc, }; =20 -/// Implemented by types where a [`ListArc`] can be inserted into a = `List`. +/// A linked list. +/// +/// All elements in this linked list will be [`ListArc`] references to the= value. Since a value can +/// only have one `ListArc` (for each pair of prev/next pointers), this en= sures that the same +/// prev/next pointers are not used for several linked lists. +/// +/// # Invariants +/// +/// * If the list is empty, then `first` is null. Otherwise, `first` point= s at the links field of +/// the first element in the list. +/// * All prev/next pointers of items in the list are valid and form a cyc= le. +pub struct List, const ID: u64 =3D 0> { + first: *mut ListLinksFields, + _ty: PhantomData>, +} + +// SAFETY: This is a container of `ListArc`, and access to the cont= ainer allows the same +// type of access to the `ListArc` elements. +unsafe impl Send for List +where + ListArc: Send, + T: ?Sized + ListItem, +{ +} +// SAFETY: This is a container of `ListArc`, and access to the cont= ainer allows the same +// type of access to the `ListArc` elements. +unsafe impl Sync for List +where + ListArc: Sync, + T: ?Sized + ListItem, +{ +} + +/// Implemented by types where a [`ListArc`] can be inserted into a = [`List`]. /// /// # Safety /// @@ -57,7 +91,7 @@ pub unsafe trait ListItem: ListArcSa= fe { /// been called. unsafe fn view_value(me: *mut ListLinks) -> *const Self; =20 - /// This is called when an item is inserted into a `List`. + /// This is called when an item is inserted into a [`List`]. /// /// # Guarantees /// @@ -104,7 +138,6 @@ struct ListLinksFields { /// The fields are null if and only if this item is not in a list. #[repr(transparent)] pub struct ListLinks { - #[allow(dead_code)] inner: Opaque, } =20 @@ -126,4 +159,294 @@ pub fn new() -> impl PinInit { }), } } + + /// # Safety + /// + /// `me` must be dereferencable. + #[inline] + unsafe fn fields(me: *mut Self) -> *mut ListLinksFields { + // SAFETY: The caller promises that the pointer is valid. + unsafe { Opaque::raw_get(ptr::addr_of!((*me).inner)) } + } + + /// # Safety + /// + /// `me` must be dereferencable. + #[inline] + unsafe fn from_fields(me: *mut ListLinksFields) -> *mut Self { + me.cast() + } +} + +impl, const ID: u64> List { + /// Creates a new empty list. + pub const fn new() -> Self { + Self { + first: ptr::null_mut(), + _ty: PhantomData, + } + } + + /// Returns whether this list is empty. + pub fn is_empty(&self) -> bool { + self.first.is_null() + } + + /// Add the provided item to the back of the list. + pub fn push_back(&mut self, item: ListArc) { + let raw_item =3D ListArc::into_raw(item); + // SAFETY: + // * We just got `raw_item` from a `ListArc`, so it's in an `Arc`. + // * If this requirement is violated, then the previous caller of = `prepare_to_insert` + // violated the safety requirement that they can't give up owner= ship of the `ListArc` + // until they call `post_remove`. + // * We own the `ListArc`. + // * Removing items from this list is always done using `remove_in= ternal_inner`, which + // calls `post_remove` before giving up ownership. + let list_links =3D unsafe { T::prepare_to_insert(raw_item) }; + // SAFETY: We have not yet called `post_remove`, so `list_links` i= s still valid. + let item =3D unsafe { ListLinks::fields(list_links) }; + + if self.first.is_null() { + self.first =3D item; + // SAFETY: The caller just gave us ownership of these fields. + // INVARIANT: A linked list with one item should be cyclic. + unsafe { + (*item).next =3D item; + (*item).prev =3D item; + } + } else { + let next =3D self.first; + // SAFETY: By the type invariant, this pointer is valid or nul= l. We just checked that + // it's not null, so it must be valid. + let prev =3D unsafe { (*next).prev }; + // SAFETY: Pointers in a linked list are never dangling, and t= he caller just gave us + // ownership of the fields on `item`. + // INVARIANT: This correctly inserts `item` between `prev` and= `next`. + unsafe { + (*item).next =3D next; + (*item).prev =3D prev; + (*prev).next =3D item; + (*next).prev =3D item; + } + } + } + + /// Add the provided item to the front of the list. + pub fn push_front(&mut self, item: ListArc) { + let raw_item =3D ListArc::into_raw(item); + // SAFETY: + // * We just got `raw_item` from a `ListArc`, so it's in an `Arc`. + // * If this requirement is violated, then the previous caller of = `prepare_to_insert` + // violated the safety requirement that they can't give up owner= ship of the `ListArc` + // until they call `post_remove`. + // * We own the `ListArc`. + // * Removing items from this list is always done using `remove_in= ternal_inner`, which + // calls `post_remove` before giving up ownership. + let list_links =3D unsafe { T::prepare_to_insert(raw_item) }; + // SAFETY: We have not yet called `post_remove`, so `list_links` i= s still valid. + let item =3D unsafe { ListLinks::fields(list_links) }; + + if self.first.is_null() { + // SAFETY: The caller just gave us ownership of these fields. + // INVARIANT: A linked list with one item should be cyclic. + unsafe { + (*item).next =3D item; + (*item).prev =3D item; + } + } else { + let next =3D self.first; + // SAFETY: We just checked that `next` is non-null. + let prev =3D unsafe { (*next).prev }; + // SAFETY: Pointers in a linked list are never dangling, and t= he caller just gave us + // ownership of the fields on `item`. + // INVARIANT: This correctly inserts `item` between `prev` and= `next`. + unsafe { + (*item).next =3D next; + (*item).prev =3D prev; + (*prev).next =3D item; + (*next).prev =3D item; + } + } + self.first =3D item; + } + + /// Removes the last item from this list. + pub fn pop_back(&mut self) -> Option> { + if self.first.is_null() { + return None; + } + + // SAFETY: We just checked that the list is not empty. + let last =3D unsafe { (*self.first).prev }; + // SAFETY: The last item of this list is in this list. + Some(unsafe { self.remove_internal(last) }) + } + + /// Removes the first item from this list. + pub fn pop_front(&mut self) -> Option> { + if self.first.is_null() { + return None; + } + + // SAFETY: The first item of this list is in this list. + Some(unsafe { self.remove_internal(self.first) }) + } + + /// Removes the provided item from this list and returns it. + /// + /// This returns `None` if the item is not in the list. (Note that by = the safety requirements, + /// this means that the item is not in any list.) + /// + /// # Safety + /// + /// The provided item must not be in a different linked list (with the= same id). + pub unsafe fn remove(&mut self, item: &T) -> Option> { + let mut item =3D unsafe { ListLinks::fields(T::view_links(item)) }; + // SAFETY: The user provided a reference, and reference are never = dangling. + // + // As for why this is not a data race, there are two cases: + // + // * If `item` is not in any list, then these fields are read-onl= y and null. + // * If `item` is in this list, then we have exclusive access to = these fields since we + // have a mutable reference to the list. + // + // In either case, there's no race. + let ListLinksFields { next, prev } =3D unsafe { *item }; + + debug_assert_eq!(next.is_null(), prev.is_null()); + if !next.is_null() { + // This is really a no-op, but this ensures that `item` is a r= aw pointer that was + // obtained without going through a pointer->reference->pointe= r conversion rountrip. + // This ensures that the list is valid under the more restrict= ive strict provenance + // ruleset. + // + // SAFETY: We just checked that `next` is not null, and it's n= ot dangling by the + // list invariants. + unsafe { + debug_assert_eq!(item, (*next).prev); + item =3D (*next).prev; + } + + // SAFETY: We just checked that `item` is in a list, so the ca= ller guarantees that it + // is in this list. The pointers are in the right order. + Some(unsafe { self.remove_internal_inner(item, next, prev) }) + } else { + None + } + } + + /// Removes the provided item from the list. + /// + /// # Safety + /// + /// The pointer must point at an item in this list. + unsafe fn remove_internal(&mut self, item: *mut ListLinksFields) -> Li= stArc { + // SAFETY: The caller promises that this pointer is not dangling, = and there's no data race + // since we have a mutable reference to the list containing `item`. + let ListLinksFields { next, prev } =3D unsafe { *item }; + // SAFETY: The pointers are ok and in the right order. + unsafe { self.remove_internal_inner(item, next, prev) } + } + + /// Removes the provided item from the list. + /// + /// # Safety + /// + /// The `item` pointer must point at an item in this list, and we must= have `(*item).next =3D=3D + /// next` and `(*item).prev =3D=3D prev`. + unsafe fn remove_internal_inner( + &mut self, + item: *mut ListLinksFields, + next: *mut ListLinksFields, + prev: *mut ListLinksFields, + ) -> ListArc { + // SAFETY: We have exclusive access to the pointers of items in th= e list, and the prev/next + // pointers are always valid for items in a list. + // + // INVARIANT: There are three cases: + // * If the list has at least three items, then after removing th= e item, `prev` and `next` + // will be next to each other. + // * If the list has two items, then the remaining item will poin= t at itself. + // * If the list has one item, then `next =3D=3D prev =3D=3D item= `, so these writes have no + // effect. The list remains unchanged and `item` is still in th= e list for now. + unsafe { + (*next).prev =3D prev; + (*prev).next =3D next; + } + // SAFETY: We have exclusive access to items in the list. + // INVARIANT: `item` is being removed, so the pointers should be n= ull. + unsafe { + (*item).prev =3D ptr::null_mut(); + (*item).next =3D ptr::null_mut(); + } + // INVARIANT: There are three cases: + // * If `item` was not the first item, then `self.first` should r= emain unchanged. + // * If `item` was the first item and there is another item, then= we just updated + // `prev->next` to `next`, which is the new first item, and set= ting `item->next` to null + // did not modify `prev->next`. + // * If `item` was the only item in the list, then `prev =3D=3D i= tem`, and we just set + // `item->next` to null, so this correctly sets `first` to null= now that the list is + // empty. + if self.first =3D=3D item { + // SAFETY: The `prev` pointer is the value that `item->prev` h= ad when it was in this + // list, so it must be valid. There is no race since `prev` is= still in the list and we + // still have exclusive access to the list. + self.first =3D unsafe { (*prev).next }; + } + + // SAFETY: `item` used to be in the list, so it is dereferencable = by the type invariants + // of `List`. + let list_links =3D unsafe { ListLinks::from_fields(item) }; + // SAFETY: Any pointer in the list originates from a `prepare_to_i= nsert` call. + let raw_item =3D unsafe { T::post_remove(list_links) }; + // SAFETY: The above call to `post_remove` guarantees that we can = recreate the `ListArc`. + unsafe { ListArc::from_raw(raw_item) } + } + + /// Moves all items from `other` into `self`. + /// + /// The items of `other` are added to the back of `self`, so the last = item of `other` becomes + /// the last item of `self`. + pub fn push_all_back(&mut self, other: &mut List) { + // First, we insert the elements into `self`. At the end, we make = `other` empty. + if self.is_empty() { + // INVARIANT: All of the elements in `other` become elements o= f `self`. + self.first =3D other.first; + } else if !other.is_empty() { + let other_first =3D other.first; + // SAFETY: The other list is not empty, so this pointer is val= id. + let other_last =3D unsafe { (*other_first).prev }; + let self_first =3D self.first; + // SAFETY: The self list is not empty, so this pointer is vali= d. + let self_last =3D unsafe { (*self_first).prev }; + + // SAFETY: We have exclusive access to both lists, so we can u= pdate the pointers. + // INVARIANT: This correctly sets the pointers to merge both l= ists. We do not need to + // update `self.first` because the first element of `self` doe= s not change. + unsafe { + (*self_first).prev =3D other_last; + (*other_last).next =3D self_first; + (*self_last).next =3D other_first; + (*other_first).prev =3D self_last; + } + } + + // INVARIANT: The other list is now empty, so update its pointer. + other.first =3D ptr::null_mut(); + } +} + +impl, const ID: u64> Default for List { + fn default() -> Self { + List::new() + } +} + +impl, const ID: u64> Drop for List { + fn drop(&mut self) { + while let Some(item) =3D self.pop_front() { + drop(item); + } + } } diff --git a/rust/kernel/list/arc.rs b/rust/kernel/list/arc.rs index 4c2e33f40597..180ec8902705 100644 --- a/rust/kernel/list/arc.rs +++ b/rust/kernel/list/arc.rs @@ -101,8 +101,8 @@ fn try_new_list_arc(&self) -> bool { /// The `ListArc` type can be thought of as a special reference to a refco= unted object that owns the /// permission to manipulate the `next`/`prev` pointers stored in the refc= ounted object. By ensuring /// that each object has only one `ListArc` reference, the owner of that r= eference is assured -/// exclusive access to the `next`/`prev` pointers. When a `ListArc` is in= serted into a `List`, the -/// `List` takes ownership of the `ListArc` reference. +/// exclusive access to the `next`/`prev` pointers. When a `ListArc` is in= serted into a [`List`], +/// the [`List`] takes ownership of the `ListArc` reference. /// /// There are various strategies to ensuring that a value has only one `Li= stArc` reference. The /// simplest is to convert a [`UniqueArc`] into a `ListArc`. However, the = refcounted object could @@ -121,6 +121,8 @@ fn try_new_list_arc(&self) -> bool { /// /// * Each reference counted object has at most one `ListArc` for each val= ue of `ID`. /// * The tracking inside `T` is aware that a `ListArc` reference exists. +/// +/// [`List`]: crate::list::List #[repr(transparent)] pub struct ListArc where --=20 2.45.0.rc1.225.g2a3ae87e7f-goog From nobody Wed Dec 17 17:23:06 2025 Received: from mail-lj1-f202.google.com (mail-lj1-f202.google.com [209.85.208.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 965AA1448E2 for ; Mon, 6 May 2024 09:54:05 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.208.202 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714989247; cv=none; b=qSFzDjGwNOhI2kNIE/KUXR9RFco1NDtfppxS6DJXq/wgU4arbJqzdlNED0qwvKNx7uhZOB41GoALZDp/C6S3Y9FXx7cSG+YSA4r3EDCnk9mnu5lrwj5AINWE6jq0oPJnHVZcQ6cVVFjsHCSIIfR+8bG/xbs3AKFCMKIDtUrVS7I= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714989247; c=relaxed/simple; bh=TputigRZUR00q1xN1sbsYsPUvr9lDRrYeB9O4vnOPD0=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=r2s+ss3O6YiQvSrZhfgUNtL5MzZuNTtjud1zYK/dyzRf97jMLmbP3U6PVa/R8A6TIIC4JH/rRw/aT/dnaR7jGxQBl29me2czjvojtKhnIXtFlwSQHDk2Dhu27SzdGKoyQmvkp8j9yKwfg4vhUhtUvyv6s5fcvso+afn65PXXMyE= 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=gqzn0fww; arc=none smtp.client-ip=209.85.208.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--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="gqzn0fww" Received: by mail-lj1-f202.google.com with SMTP id 38308e7fff4ca-2e31652ed62so5509821fa.0 for ; Mon, 06 May 2024 02:54:05 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1714989244; x=1715594044; 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=ga8rU6TTAMlW0eYro+OQUU98vsuNjWANwmXQ6mKFv4I=; b=gqzn0fwwCVnBIasKIp6/KwRLc9njsxfxmfI7U2ZbFYJ3d4nqRfN9+qIVnwXRZPJV9W 0Rh9m8Dmac0hUG7leJ0937MIvBVsihNqDaLvHhJdO4HKPuYTRkyG4vlJXAkAnjPtNb/Q J3TSm2ShUCEkSkWUoa0TMxYD+4nPxnjozZRBesuy5GdYKLR6NCnjcquyk1VCmqUc6rp5 +sDn9d4QYaF/tdv+3ToJe1sk+PAhX+dzYKB2C3f2oDsRiTED4LTojgyj+Ex2rYWydyBe g/kwWSG7NrPWZIKL5WpIadrMxQWgCcA9ueXUNtA31D0rNphZUYx3jrz3OYI/6stS0763 6lPw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1714989244; x=1715594044; 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=ga8rU6TTAMlW0eYro+OQUU98vsuNjWANwmXQ6mKFv4I=; b=DI+L7xQ2VUEF5IkpOLuJkvneMe/Ir/DrrUD75nUhUvL5vIl/4B7dc+osqV39FxHpQ9 XIxCk4m+OVSJjBYz6oQmyzT6BzhnHMNx766EsY/WbNRPTzKYtlkfqOvGKSq3Ww+IKiDZ 054ilyezECMK1LyYapr/flELdsMUl94MT9Y4bWQH1l0reVflN9sRMdh012jokBX37Sfr f8Hq7C2RRbWGpqokk2sPtQgRX7c1QFLpQqH3XSKvP1jzYp6RAyuFU5eeZRMyf1UWi3z2 OkeIpzz2uQouzAg6eBA2bPLAkrVTmXZ9sDxg2muf7z2lirqeqa+0NgOMjNHVlyjkarDU W0JA== X-Forwarded-Encrypted: i=1; AJvYcCXKXskV2G1OgFDnijZ86TYd6Otd8WdKixSbOhM85rF7mWA1PrqDZAyNMNgk+e5nQ95lvK1T61RRMX4206EGwjDmRXuSuthAtEK5YiDZ X-Gm-Message-State: AOJu0YxB2RCwoL5W6hvN6aUYON/TA9AVa3MRBputehajElrivduJGgKz 0/gNtaOueL1FDveGaG6RbP3l1oL5HXR4TWs6AEynZQbx05NjxGX/k+xRNWJguHAtxsgiPWpp4Kd MBZEsMQthTG+gcg== X-Google-Smtp-Source: AGHT+IHDpeEadcL9TpEMMczWSvQ8JpUf0k+ea4Le7z8CDI+TIQBGNZarotBKM+O9RL+vD+YiNEO4MtxIgHfb1Ak= X-Received: from aliceryhl2.c.googlers.com ([fda3:e722:ac3:cc00:68:949d:c0a8:572]) (user=aliceryhl job=sendgmr) by 2002:a2e:bcc3:0:b0:2e3:6e32:7a31 with SMTP id z3-20020a2ebcc3000000b002e36e327a31mr2111ljp.0.1714989243811; Mon, 06 May 2024 02:54:03 -0700 (PDT) Date: Mon, 06 May 2024 09:53:27 +0000 In-Reply-To: <20240506-linked-list-v2-0-7b910840c91f@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240506-linked-list-v2-0-7b910840c91f@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=4976; i=aliceryhl@google.com; h=from:subject:message-id; bh=TputigRZUR00q1xN1sbsYsPUvr9lDRrYeB9O4vnOPD0=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBmOKilpgrg2auL4BQjpffqhEAv7iAtgfTAjZkfx 0OxrRlZXACJAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCZjiopQAKCRAEWL7uWMY5 Rkr+EACWvky+6jgSOyKwmOCDFtl45pa6K6XUS0Ui/1xL619TmIohZRkC8/Q4pp+For0qr0Czs2i H+Gxc+VmLaxNJKqz7bzo8Egd1cLGuxH58jYd5fp7ZVG4lZcDMDiuQgL33U7ntJxEn0iDfyRY5Vd r0I647mwFEDv09XJvKR641WdhLMkfU5UpFa65feb2wJQS0J3xCvBWsin7WKUJrhveVazV58fANN v+3Ati/rTgrwYM5bKqvRNpLtjG1Z+3v5mtaD7v6dmrF3BUBcsQGQFaXLD2y+b8vQG86Y5ghECYv t5J+pJIqCSZfQAXHpnWtJaXWQLYHmr1psZ0+A9G0qAW7Yt84sRG9HuoTFOCeyopkpm9wmpux5Ew TNPbbpfba3/6LqnCiyCnsknrY3ZMZ/LHQ3NxtbuB9zmTHTO/eRB7jHX8HiSmWMAZ7AGU3GhRc7e t++bhn1UX0DGbB4UzcFrsdL9+DINaSItUCqf7+wytGMXNfY6RtfKqeyYaPA1VG10MCXsX1pIavL 3QOWaSr7lfOZMSJrIFZ0lhqLK6DE3qL7J4CiG3lF+bNjgt77eIWUGhf4NoD/Xu7t8ya11hYvjD0 8Pua9x+rhgnTzOqwWkTM40agJ3XEg9M8nAO5UQifCq8yQKAb2ZOsdO9J8+6lehcdZYeglBtcocQ 24d3V3TFgZ021bw== X-Mailer: b4 0.13-dev-26615 Message-ID: <20240506-linked-list-v2-6-7b910840c91f@google.com> Subject: [PATCH v2 6/9] rust: list: add iterators 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 , Kees Cook , 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 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Rust Binder has lists containing stuff such as all contexts or all processes, and sometimes need to iterate over them. This patch enables Rust Binder to do that using a normal for loop. The iterator returns the ArcBorrow type, so it is possible to grab a refcount to values while iterating. Signed-off-by: Alice Ryhl Reviewed-by: Benno Lossin --- rust/kernel/list.rs | 102 ++++++++++++++++++++++++++++++++++++++++++++++++= ++++ 1 file changed, 102 insertions(+) diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs index d0ff29a3e5d1..e36afc7ee44a 100644 --- a/rust/kernel/list.rs +++ b/rust/kernel/list.rs @@ -5,7 +5,9 @@ //! A linked list implementation. =20 use crate::init::PinInit; +use crate::sync::ArcBorrow; use crate::types::Opaque; +use core::iter::{DoubleEndedIterator, FusedIterator}; use core::marker::PhantomData; use core::ptr; =20 @@ -435,6 +437,17 @@ pub fn push_all_back(&mut self, other: &mut List) { // INVARIANT: The other list is now empty, so update its pointer. other.first =3D ptr::null_mut(); } + + /// Creates an iterator over the list. + pub fn iter(&self) -> Iter<'_, T, ID> { + // INVARIANT: If the list is empty, both pointers are null. Otherw= ise, both pointers point + // at the first element of the same list. + Iter { + current: self.first, + stop: self.first, + _ty: PhantomData, + } + } } =20 impl, const ID: u64> Default for List { @@ -450,3 +463,92 @@ fn drop(&mut self) { } } } + +/// An iterator into a [`List`]. +/// +/// # Invariants +/// +/// * There must be a [`List`] that is immutably borrowed for the duration= of `'a`. +/// * The `current` pointer is null or points at a value in that [`List`]. +/// * The `stop` pointer is equal to the `first` field of the [`List`]. +#[derive(Clone)] +pub struct Iter<'a, T: ?Sized + ListItem, const ID: u64 =3D 0> { + current: *mut ListLinksFields, + stop: *mut ListLinksFields, + _ty: PhantomData<&'a ListArc>, +} + +impl<'a, T: ?Sized + ListItem, const ID: u64> Iterator for Iter<'a, T,= ID> { + type Item =3D ArcBorrow<'a, T>; + + fn next(&mut self) -> Option> { + if self.current.is_null() { + return None; + } + + let current =3D self.current; + + // SAFETY: We just checked that `current` is not null, so it is in= a list, and hence not + // dangling. There's no race because the iterator holds an immutab= le borrow to the list. + let next =3D unsafe { (*current).next }; + // INVARIANT: If `current` was the last element of the list, then = this updates it to null. + // Otherwise, we update it to the next element. + self.current =3D if next !=3D self.stop { + next + } else { + ptr::null_mut() + }; + + // SAFETY: The `current` pointer points at a value in the list. + let item =3D unsafe { T::view_value(ListLinks::from_fields(current= )) }; + // SAFETY: + // * All values in a list are stored in an `Arc`. + // * The value cannot be removed from the list for the duration of= the lifetime annotated + // on the returned `ArcBorrow`, because removing it from the lis= t would require mutable + // access to the list. However, the `ArcBorrow` is annotated wit= h the iterator's + // lifetime, and the list is immutably borrowed for that lifetim= e. + // * Values in a list never have a `UniqueArc` reference. + Some(unsafe { ArcBorrow::from_raw(item) }) + } +} + +impl<'a, T: ?Sized + ListItem, const ID: u64> FusedIterator for Iter<'= a, T, ID> {} + +impl<'a, T: ?Sized + ListItem, const ID: u64> IntoIterator for &'a Lis= t { + type IntoIter =3D Iter<'a, T, ID>; + type Item =3D ArcBorrow<'a, T>; + + fn into_iter(self) -> Iter<'a, T, ID> { + self.iter() + } +} + +/// An owning iterator into a [`List`]. +pub struct IntoIter, const ID: u64 =3D 0> { + list: List, +} + +impl, const ID: u64> Iterator for IntoIter= { + type Item =3D ListArc; + + fn next(&mut self) -> Option> { + self.list.pop_front() + } +} + +impl, const ID: u64> FusedIterator for IntoIter {} + +impl, const ID: u64> DoubleEndedIterator for Into= Iter { + fn next_back(&mut self) -> Option> { + self.list.pop_back() + } +} + +impl, const ID: u64> IntoIterator for List= { + type IntoIter =3D IntoIter; + type Item =3D ListArc; + + fn into_iter(self) -> IntoIter { + IntoIter { list: self } + } +} --=20 2.45.0.rc1.225.g2a3ae87e7f-goog From nobody Wed Dec 17 17:23:06 2025 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 CBF5C1448F3 for ; Mon, 6 May 2024 09:54:07 +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=1714989249; cv=none; b=ulzW28/dpPzcRFp5FNhB7okz61f2IaDe6/w2f9UA1p5qHOf9luqWVOWFsl1D9bShI7k2tnmRCwk23LKqmKpBGejxNZxD0YeJg7PFksWGb4/edyFo6ADGQowhmOZv4B9p2FXkCKWbk8dxS+d6BSI9uKHYTZXCaUaLj8AfncQwXPA= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714989249; c=relaxed/simple; bh=8K9lvD/I7hdBOtJBKpQy5+wPSZSIbLWW5XJdQOsddxI=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=qsKWIn1bc4e2RlXuKiUE8Jd5bwsPhJXKbCFahIo3oz1Gd34BdZE9YIQp7JVGTYAtIkfNlnOo8jmDye7ejP4XpndjMgGUtAvfH7klVfUgnnNaPu9D03NrndtaA53xSVXEuyFCJM46tTByXXV1mdzbMVhyWE7e7p1hA5+BUs2+uEg= 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=r5s6YMPu; 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--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="r5s6YMPu" Received: by mail-yb1-f201.google.com with SMTP id 3f1490d57ef6-de615257412so3740552276.0 for ; Mon, 06 May 2024 02:54:07 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1714989247; x=1715594047; 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=ezJm3dIadEEPgM9AdRrLvcNCS5JPWxEP25Hxucwcvt8=; b=r5s6YMPuJewDzHD1BPG11DPogD22jkgCA2aBwcG623xn9fNvkBMMGbJgw7enuQma6N iyluknt/cSX1TnyTDuLmYJQsecKh/pS8K/3p4mT/eE1GrC/SVxRN/AWBnloRdrwC3RTk WJg4/pIX3T2qjCPDzUCvzRFSIQd2OdgTEDhNj7bhHA9ntlJFZ4cOdk+AHfvG8pzFlzGg ZehbuXSsdni2M3+EsX480f7EJGMRGfWVcmo1cuEWUQ/hY1RZXBF5RkaE2Y7gBLYZ/nRh ja/ukwu5N9SRQ90PHPEhmTd88fJWRZ9XGHE8NcrwQE7WCNYfaFX1itwf6A+EBYdKf+2V UaFg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1714989247; x=1715594047; 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=ezJm3dIadEEPgM9AdRrLvcNCS5JPWxEP25Hxucwcvt8=; b=OSJNr+oYZ79eO1WL8t2oK2om4CsDa1Gna3gMUH59aCaHTmr9R/pnme1CT3Zt4UdLiL 1/PhD4mvXizvQnLPRdr2ZDaprP2XOSXybM9u8cDaZE4ejWDyf9pAanEyiLYOzMaoCIgj vWglrD/oOYmTwYd+xxy/2G7Lm9mZeffkyBsIf3mBoRSLzXLiev5Gf/IlUQ20olur2DLA CISOrRIpr1lhMOgxAJi+JQP4o3mZnGHuGEiOaWdIjCHgl89NLcTrklZ7IXe61FYwQTd9 iz5LEgKv4Yfhxl79PZGnP+L/t5g9sGXMzKBeUmHQ9MkD/kXHUurUOJ6PnRhNvL2eam8S hcZg== X-Forwarded-Encrypted: i=1; AJvYcCVJhikArHsxMIVhqwghIOGa7uVWi/iZNmX7TckpWmhk8ILkysqdUQbFucyemPmIRnkBZTjRPu8C5Gv5HR5P9/ZXg0tEjeyLZzF8rZ0w X-Gm-Message-State: AOJu0YzDUq9Pgo7y/ttxMweFPF2HukSq8ijPq3u+6zaRNBInlSaHEIQ5 nIg9pGQIU6gBqeQ+kG4mQZ8II9I6P+dOP53HRKl3nvMDDK1O9IVfEKkcEYrGu9IaTd+ZjR/cEoj m1vlPAzBbrWFnSw== X-Google-Smtp-Source: AGHT+IEBI67b/rlR/RdZhzJYKewslwa1JtIus+jos+eEpIsCwHVg5LbTZzENK6W+28QXdTWd3W+eYA2jlbLqs9g= X-Received: from aliceryhl2.c.googlers.com ([fda3:e722:ac3:cc00:68:949d:c0a8:572]) (user=aliceryhl job=sendgmr) by 2002:a05:6902:c01:b0:de5:3003:4b7b with SMTP id fs1-20020a0569020c0100b00de530034b7bmr3531670ybb.1.1714989246988; Mon, 06 May 2024 02:54:06 -0700 (PDT) Date: Mon, 06 May 2024 09:53:28 +0000 In-Reply-To: <20240506-linked-list-v2-0-7b910840c91f@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240506-linked-list-v2-0-7b910840c91f@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=5286; i=aliceryhl@google.com; h=from:subject:message-id; bh=8K9lvD/I7hdBOtJBKpQy5+wPSZSIbLWW5XJdQOsddxI=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBmOKimeotMCAb/jQAq50Zc0JLzfCpOkfdGvoLEt plupjKUheyJAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCZjiopgAKCRAEWL7uWMY5 RnZgEACvgLng6XYGSmoMrTF4EohLNct1liNo8X0AoAwOxEw+XDWef8P8u5iqebkPBEMRlcJQnwl vUSgi9vD9ImBMfgNvXk7x1gzlMxbrivvYY6lbmfVALcji5zSIyIoyFhlLQRcneOcjbGu0xJo9zG DY9Jet6bjWLt+17ebpFFO/DR2dF0sPBJceiFIR8DV/WD0HkgLr+A/Ezp3Db++zJullZpXt3pDF1 QD5X96ylzPodZgt+EaTgY6ssA89o5kFyXTZsv9QYAk+YML9V0ghC9QU/7B0ax2DyGMRYLYZUQhF ynE80SaUDEsgIM2C3mBTxo9LO98iL+rhFXXmA8RULghlXhrOSCu/0JqE41utp9cHLxkQihto41M o8sINgaqu41MAsdW7JZAAUkHZc3mUnQ0hu5lUot7Fw78N8XR0CImErFJnB2TB+lih6vBJKdd5Ej UhhlPoJ4JioMccgnWlnpKFiyhEXsecNK/rwM8ziKinbJmkx+e3IGrTKKRPi6yoiPrYaULlddrj4 Xe5L03V4gjX2Hs6uftmgPlIk0lcdHouMca6m5gUUOzoAhEOwrrEteLz29wMLuECi/Pghl8c92KU +2ldRgyWLB+tzIaFJIYnu5OMYOnvDbr4S7gbd482WsSWsDWNm2RGFPF06ZZp7DzqcJfYhbbkD11 lGSsBZrrc8cMU7Q== X-Mailer: b4 0.13-dev-26615 Message-ID: <20240506-linked-list-v2-7-7b910840c91f@google.com> Subject: [PATCH v2 7/9] rust: list: add cursor 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 , Kees Cook , 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 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable The cursor is very similar to the list iterator, but it has one important feature that the iterator doesn't: it can be used to remove items from the linked list. This feature cannot be added to the iterator because the references you get from the iterator are considered borrows of the original list, rather than borrows of the iterator. This means that there's no way to prevent code like this: let item =3D iter.next(); iter.remove(); use(item); If `iter` was a cursor instead of an iterator, then `item` will be considered a borrow of `iter`. Since `remove` destroys `iter`, this means that the borrow-checker will prevent uses of `item` after the call to `remove`. So there is a trade-off between supporting use in traditional for loops, and supporting removal of elements as you iterate. Iterators and cursors represents two different choices on that spectrum. Rust Binder needs cursors for the list of death notifications that a process is currently handling. When userspace tells Binder that it has finished processing the death notification, Binder will iterate the list to search for the relevant item and remove it. Signed-off-by: Alice Ryhl Reviewed-by: Benno Lossin --- rust/kernel/list.rs | 82 +++++++++++++++++++++++++++++++++++++++++++++++++= ++++ 1 file changed, 82 insertions(+) diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs index e36afc7ee44a..641b434e3841 100644 --- a/rust/kernel/list.rs +++ b/rust/kernel/list.rs @@ -438,6 +438,20 @@ pub fn push_all_back(&mut self, other: &mut List) { other.first =3D ptr::null_mut(); } =20 + /// Returns a cursor to the first element of the list. + /// + /// If the list is empty, this returns `None`. + pub fn cursor_front(&mut self) -> Option> { + if self.first.is_null() { + None + } else { + Some(Cursor { + current: self.first, + list: self, + }) + } + } + /// Creates an iterator over the list. pub fn iter(&self) -> Iter<'_, T, ID> { // INVARIANT: If the list is empty, both pointers are null. Otherw= ise, both pointers point @@ -512,6 +526,74 @@ fn next(&mut self) -> Option> { } } =20 +/// A cursor into a [`List`]. +/// +/// # Invariants +/// +/// The `current` pointer points a value in `list`. +pub struct Cursor<'a, T: ?Sized + ListItem, const ID: u64 =3D 0> { + current: *mut ListLinksFields, + list: &'a mut List, +} + +impl<'a, T: ?Sized + ListItem, const ID: u64> Cursor<'a, T, ID> { + /// Access the current element of this cursor. + pub fn current(&self) -> ArcBorrow<'_, T> { + // SAFETY: The `current` pointer points a value in the list. + let me =3D unsafe { T::view_value(ListLinks::from_fields(self.curr= ent)) }; + // SAFETY: + // * All values in a list are stored in an `Arc`. + // * The value cannot be removed from the list for the duration of= the lifetime annotated + // on the returned `ArcBorrow`, because removing it from the lis= t would require mutable + // access to the cursor or the list. However, the `ArcBorrow` ho= lds an immutable borrow + // on the cursor, which in turn holds a mutable borrow on the li= st, so any such + // mutable access requires first releasing the immutable borrow = on the cursor. + // * Values in a list never have a `UniqueArc` reference, because = the list has a `ListArc` + // reference, and `UniqueArc` references must be unique. + unsafe { ArcBorrow::from_raw(me) } + } + + /// Move the cursor to the next element. + pub fn next(self) -> Option> { + // SAFETY: The `current` field is always in a list. + let next =3D unsafe { (*self.current).next }; + + if next =3D=3D self.list.first { + None + } else { + // INVARIANT: Since `self.current` is in the `list`, its `next= ` pointer is also in the + // `list`. + Some(Cursor { + current: next, + list: self.list, + }) + } + } + + /// Move the cursor to the previous element. + pub fn prev(self) -> Option> { + // SAFETY: The `current` field is always in a list. + let prev =3D unsafe { (*self.current).prev }; + + if self.current =3D=3D self.list.first { + None + } else { + // INVARIANT: Since `self.current` is in the `list`, its `prev= ` pointer is also in the + // `list`. + Some(Cursor { + current: prev, + list: self.list, + }) + } + } + + /// Remove the current element from the list. + pub fn remove(self) -> ListArc { + // SAFETY: The `current` pointer always points at a member of the = list. + unsafe { self.list.remove_internal(self.current) } + } +} + impl<'a, T: ?Sized + ListItem, const ID: u64> FusedIterator for Iter<'= a, T, ID> {} =20 impl<'a, T: ?Sized + ListItem, const ID: u64> IntoIterator for &'a Lis= t { --=20 2.45.0.rc1.225.g2a3ae87e7f-goog From nobody Wed Dec 17 17:23:06 2025 Received: from mail-lf1-f73.google.com (mail-lf1-f73.google.com [209.85.167.73]) (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 04A5414532E for ; Mon, 6 May 2024 09:54:11 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.167.73 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714989253; cv=none; b=MXu/QIACcgZuVGMthFxxEXXbMatqvDrupqnQSavw8JYajXMGEcJgvPPCuoUOgSbQHl2ApQWFM6wyCszxiC58SSgouq83sx/SzxmFdTm8v5lTA4FmxWg5OcvCh8+d9Yw6JpvXihhJ4QyPPiyaIXoDYXpGi+ejSe7T9CTuo+IDKtc= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714989253; c=relaxed/simple; bh=Ut9pc7UnK/ZLhjyeKL4QL6legRdAKj0mXCzKnKTUcy4=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=O2tRKhlwBuT/l0czSdck+RtTpennBo8rwPNLEuRG8LjNRbbtoutP14fe8EAEZbmwgaH7ra9Dxc+HWqlJCBwZ0357308/i+QWzCvhBlyib1HQfj3IqXwqT2/N2tdeGDvoT+tJlwRW26WYEITZAfvLnj2QTKyz/0EUdJc+0fa4Ncg= 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=Sml947SM; arc=none smtp.client-ip=209.85.167.73 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="Sml947SM" Received: by mail-lf1-f73.google.com with SMTP id 2adb3069b0e04-51f7c8c7d85so1145410e87.2 for ; Mon, 06 May 2024 02:54:11 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1714989250; x=1715594050; 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=IfFNNPf+Z0+9z9blRE9xu/wRB+nVh4d9kT8iySlhYHI=; b=Sml947SMVAnL5nVuoJRcCzTqwkhGUngf5H/wPb5EVttV+ICM/DD2kylgoZ62Kj2ch6 kaMW2bCCE3NYBC3Eg0T+/485SK/ousI15zGR9328QI5DhEFU53oV7r8tSuDOhJcTIv2a gCMUfIv3cC8Ndn/ue5HZgXOiHb19vpo0MURNCfQL6yOMmkoh0mQJGvbRF23fPG1gRmKV 0CVP9hZ7zG4JUuLp62ZuyJKcufAu90lLzJcLKu1g8w88bDw/ocHh15tYSVWZNJfKv/qx JV3uS86kVAv685iKLq1IZ92TcxaQWSVs3KauW6IIX6T2l70rJ8iA6rRj52D6+Fm424LN wJjg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1714989250; x=1715594050; 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=IfFNNPf+Z0+9z9blRE9xu/wRB+nVh4d9kT8iySlhYHI=; b=qZ9Nbqk4947wHsaFqqUwb0w1P1tEAb1lKTg2mJKl85m9ULUEK/MOpQHEev4Nvxdd4F Q3K6W8FfVftemmaE3zpA7b+Cf6LFjGk0xzXrInmggTo87pKbQAPyVm/XGoJ4tNlddVQF 9l2BWtPeFvbgIBD3ejOT/M2L+6C8uAQp9X7W5f6aZ/+u7VBbOse7Icg54vRUdupOIqU3 AsFyGQF3JE4BvOWK7eh1meLMIeuXbSrOdzbKV1CLcpF/09vvn1ElJZXdF8duM1994tZ1 Tv+ROXZBv/fwN99PFSWEDNaTBOUvYR2hWJ0yJdWf4Wd/Nq3mnaSjzB7FcNE99AQ8csvv kJFw== X-Forwarded-Encrypted: i=1; AJvYcCXM6J0RfhTNl2u9O5KKxjijVlDIASgzs9OSpDeoA6pK2+K88wxVXW6e2MG7ohxzh9b81UoI2XDscDo5T0I1j76AQsMNyMZxIV5gGtFG X-Gm-Message-State: AOJu0YwY4/CLLZf4wmly996dVq0NaePZnq9Mld+G8hBAq5OxKAVhYFzv k9IRWOKJcph5YVS8eXa2nemBOdYHgHwPoPKCqtoh/SQc82f7iLVJFHQ55eG7ConEnyS9RXSuU09 IpoUPX6tL2/7mdA== X-Google-Smtp-Source: AGHT+IEIiU5srimAu61wpVuiQ73nCqqEVfVL9ZMjs6eaUNS9JsY4zXGhb0qE0I0mdt847qn6BvJ4STQf1QI7oDg= X-Received: from aliceryhl2.c.googlers.com ([fda3:e722:ac3:cc00:68:949d:c0a8:572]) (user=aliceryhl job=sendgmr) by 2002:ac2:43bc:0:b0:51c:db00:d8ac with SMTP id t28-20020ac243bc000000b0051cdb00d8acmr8885lfl.4.1714989250005; Mon, 06 May 2024 02:54:10 -0700 (PDT) Date: Mon, 06 May 2024 09:53:29 +0000 In-Reply-To: <20240506-linked-list-v2-0-7b910840c91f@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240506-linked-list-v2-0-7b910840c91f@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=10137; i=aliceryhl@google.com; h=from:subject:message-id; bh=Ut9pc7UnK/ZLhjyeKL4QL6legRdAKj0mXCzKnKTUcy4=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBmOKimJcgo5x/r/jpVzu97yu6NLP309aNRbBReV 05j16WbRJSJAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCZjiopgAKCRAEWL7uWMY5 Rl1yEACG1DVHT7Wgv9VEBDkJZklxRP/Z732G2d0TSo1518CQ9I8cWeDvmdy6+KPJAFO8Y2a8sN2 2veAX3A4aGf8bSJsSxkZ9bgq78XyGX9vd8ubySrnWFX7nnOeOu9XVNGpzzva5BCrHJtfroHk9sS qUte0+DQAwXkEjnz4KrWaiN0qv4tFk8W6TZvzqb35BC0WfBLFDFBeKMD87USt5+nCMpyQ4JXAcA ZE3aRAvvyohFZKLVzIYg3DKSoQHjhgtFxdCV8tyvxJK/1frc+NJPeR8V2EL9Pk/kffR6GYw26hM mTEgBno/9IIluY8iFzTUFZ1saCih5sS/o/4wle/SGyENywhkB7GPJZCw1SllJwpd3jBPVWH7Ykf EhGJ0MJs3ynpTq22V57SBDmB/6uRdRTn5wRrt8viZHt+w1FuC/LZ8qQ4lpFpMbmP7BrX0vOmyOk dphz2fQN2EZpe/e1bDhJgCRqMs4QujPFzbmgnxrzGXA3yZjqMNFwKyj1MfZEcxKr7ZKYZTyYZMp EmG/QdXZ3UsRsjjEUhJekIl2OfnsctfJ2tKcVYmmrkE4wmvZHRjXo1tYxmkLFZWzecrDvbwElQC BjGJLOW3U3mMaijMkQ3nmYFQYg/RN+OhjRv44IR5ociynbZqlexht66jguiybCezhg/mTh0KLnr fmn6FbyH6h5UmOQ== X-Mailer: b4 0.13-dev-26615 Message-ID: <20240506-linked-list-v2-8-7b910840c91f@google.com> Subject: [PATCH v2 8/9] rust: list: support heterogeneous lists 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 , Kees Cook , 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 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Support linked lists that can have many different structs at once. This is generally done using trait objects. The main challenge is figuring what the struct is given only a pointer to the ListLinks. We do this by storing a pointer to the struct next to the ListLinks field. The container_of operation will then just read that pointer. When the type is a trait object, that pointer will be a fat pointer whose metadata is a vtable that tells you what kind of struct it is. Heterogeneous lists are heavily used by Rust Binder. There are a lot of so-called todo lists containing various events that need to be delivered to userspace next time userspace calls into the driver. And there are quite a few different todo item types: incoming transaction, changes to refcounts, death notifications, and more. Signed-off-by: Alice Ryhl --- rust/kernel/list.rs | 47 ++++++++++++++- rust/kernel/list/impl_list_item_mod.rs | 105 +++++++++++++++++++++++++++++= ++++ 2 files changed, 151 insertions(+), 1 deletion(-) diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs index 641b434e3841..3e687401c6d3 100644 --- a/rust/kernel/list.rs +++ b/rust/kernel/list.rs @@ -7,12 +7,16 @@ use crate::init::PinInit; use crate::sync::ArcBorrow; use crate::types::Opaque; +use core::cell::UnsafeCell; use core::iter::{DoubleEndedIterator, FusedIterator}; use core::marker::PhantomData; +use core::mem::MaybeUninit; use core::ptr; =20 mod impl_list_item_mod; -pub use self::impl_list_item_mod::{impl_has_list_links, impl_list_item, Ha= sListLinks}; +pub use self::impl_list_item_mod::{ + impl_has_list_links, impl_has_list_links_self_ptr, impl_list_item, Has= ListLinks, HasSelfPtr, +}; =20 mod arc; pub use self::arc::{ @@ -180,6 +184,47 @@ unsafe fn from_fields(me: *mut ListLinksFields) -> *mu= t Self { } } =20 +/// Similar to [`ListLinks`], but also contains a pointer to the full valu= e. +/// +/// This type can be used instead of [`ListLinks`] to support lists with t= rait objects. +#[repr(C)] +pub struct ListLinksSelfPtr { + /// The `ListLinks` field inside this value. + /// + /// This is public so that it can be used with `impl_has_list_links!`. + pub inner: ListLinks, + self_ptr: UnsafeCell>, +} + +// SAFETY: The fields of a ListLinksSelfPtr can be moved across thread bou= ndaries. +unsafe impl Send for ListLinksSelfPtr {} +// SAFETY: The type is opaque so immutable references to a ListLinksSelfPt= r are useless. Therefore, +// it's okay to have immutable access to a ListLinks from several threads = at once. +// +// Note that `inner` being a public field does not prevent this type from = being opaque, since +// `inner` is a opaque type. +unsafe impl Sync for ListLinksSelfPtr {} + +impl ListLinksSelfPtr { + /// The offset from the [`ListLinks`] to the self pointer field. + pub const LIST_LINKS_SELF_PTR_OFFSET: usize =3D core::mem::offset_of!(= Self, self_ptr); + + /// 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: ListLinks { + inner: Opaque::new(ListLinksFields { + prev: ptr::null_mut(), + next: ptr::null_mut(), + }), + }, + self_ptr: UnsafeCell::new(MaybeUninit::zeroed()), + } + } +} + impl, const ID: u64> List { /// Creates a new empty list. pub const fn new() -> Self { diff --git a/rust/kernel/list/impl_list_item_mod.rs b/rust/kernel/list/impl= _list_item_mod.rs index 3ff483be89d1..96e90c0ec587 100644 --- a/rust/kernel/list/impl_list_item_mod.rs +++ b/rust/kernel/list/impl_list_item_mod.rs @@ -62,6 +62,49 @@ unsafe fn raw_get_list_links(ptr: *mut Self) -> *mut $cr= ate::list::ListLinks$(<$ } pub use impl_has_list_links; =20 +/// Declares that the `ListLinks` field in this struct is inside a `Li= stLinksSelfPtr`. +/// +/// # Safety +/// +/// The `ListLinks` field of this struct at the offset `HasListLinks::OFFSET` must be +/// inside a `ListLinksSelfPtr`. +pub unsafe trait HasSelfPtr +where + Self: HasListLinks, +{ +} + +/// Implements the [`HasListLinks`] and [`HasSelfPtr`] traits for the give= n type. +#[macro_export] +macro_rules! impl_has_list_links_self_ptr { + ($(impl$({$($implarg:tt)*})? + HasSelfPtr<$item_type:ty $(, $id:tt)?> + for $self:ident $(<$($selfarg:ty),*>)? + { self.$field:ident } + )*) =3D> {$( + // SAFETY: The implementation of `raw_get_list_links` only compile= s if the field has the + // right type. + unsafe impl$(<$($implarg)*>)? $crate::list::HasSelfPtr<$item_type = $(, $id)?> for + $self $(<$($selfarg),*>)? + {} + + unsafe impl$(<$($implarg)*>)? $crate::list::HasListLinks$(<$id>)? = for + $self $(<$($selfarg),*>)? + { + const OFFSET: usize =3D ::core::mem::offset_of!(Self, $field) = as usize; + + #[inline] + unsafe fn raw_get_list_links(ptr: *mut Self) -> *mut $crate::l= ist::ListLinks$(<$id>)? { + // SAFETY: The caller promises that the pointer is not dan= gling. + let ptr: *mut $crate::list::ListLinksSelfPtr<$item_type $(= , $id)?> =3D + unsafe { ::core::ptr::addr_of_mut!((*ptr).$field) }; + ptr.cast() + } + } + )*}; +} +pub use impl_has_list_links_self_ptr; + /// Implements the [`ListItem`] trait for the given type. /// /// Assumes that the type implements [`HasListLinks`]. @@ -95,5 +138,67 @@ unsafe fn post_remove(me: *mut $crate::list::ListLinks<= $num>) -> *const Self { } } }; + + ( + impl$({$($generics:tt)*})? ListItem<$num:tt> for $t:ty { + using ListLinksSelfPtr; + } $($rest:tt)* + ) =3D> { + unsafe impl$(<$($generics)*>)? $crate::list::ListItem<$num> for $t= { + unsafe fn prepare_to_insert(me: *const Self) -> *mut $crate::l= ist::ListLinks<$num> { + // SAFETY: The caller promises that `me` points at a valid= value of type `Self`. + let links_field =3D unsafe { >::view_links(me) }; + + let spoff =3D $crate::list::ListLinksSelfPtr::= ::LIST_LINKS_SELF_PTR_OFFSET; + // SAFETY: The constant is equal to `offset_of!(ListLinksS= elfPtr, self_ptr)`, so + // the pointer stays in bounds of the allocation. + let self_ptr =3D unsafe { (links_field as *const u8).add(s= poff) } + as *const ::core::cell::UnsafeCell<*const Self>; + let cell_inner =3D ::core::cell::UnsafeCell::raw_get(self_= ptr); + + // SAFETY: This value is not accessed in any other places = than `prepare_to_insert`, + // `post_remove`, or `view_value`. By the safety requireme= nts of those methods, + // none of these three methods may be called in parallel w= ith this call to + // `prepare_to_insert`, so this write will not race with a= ny other access to the + // value. + unsafe { ::core::ptr::write(cell_inner, me) }; + + links_field + } + + unsafe fn view_links(me: *const Self) -> *mut $crate::list::Li= stLinks<$num> { + // SAFETY: The caller promises that `me` points at a valid= value of type `Self`. + unsafe { >::raw_get_list_links(= me.cast_mut()) } + } + + // This function is also used as the implementation of `post_r= emove`, so the caller + // may choose to satisfy the safety requirements of `post_remo= ve` instead of the safety + // requirements for `view_value`. + unsafe fn view_value(links_field: *mut $crate::list::ListLinks= <$num>) -> *const Self { + let spoff =3D $crate::list::ListLinksSelfPtr::= ::LIST_LINKS_SELF_PTR_OFFSET; + // SAFETY: The constant is equal to `offset_of!(ListLinksS= elfPtr, self_ptr)`, so + // the pointer stays in bounds of the allocation. + let self_ptr =3D unsafe { (links_field as *const u8).add(s= poff) } + as *const ::core::cell::UnsafeCell<*const Self>; + let cell_inner =3D ::core::cell::UnsafeCell::raw_get(self_= ptr); + // This returns the same pointer as the one passes to the = previous call to + // `prepare_to_insert` since that previous call wrote that= pointer to this + // location, and the value has not been modified since. + // + // SAFETY: This is not a data race, because the only funct= ion that writes to this + // value is `prepare_to_insert`, but by the safety require= ments the + // `prepare_to_insert` method may not be called in paralle= l with `view_value` or + // `post_remove`. + unsafe { ::core::ptr::read(cell_inner) } + } + + unsafe fn post_remove(me: *mut $crate::list::ListLinks<$num>) = -> *const Self { + // SAFETY: This specific implementation of `view_value` al= lows the caller to + // promise the safety requirements of `post_remove` instea= d of the safety + // requirements for `view_value`. + unsafe { >::view_valu= e(me) } + } + } + }; } pub use impl_list_item; --=20 2.45.0.rc1.225.g2a3ae87e7f-goog From nobody Wed Dec 17 17:23:06 2025 Received: from mail-lf1-f73.google.com (mail-lf1-f73.google.com [209.85.167.73]) (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 A1D03145340 for ; Mon, 6 May 2024 09:54:14 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.167.73 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714989256; cv=none; b=KY3oSFW7IM+ZxDxWlgJj7K1QYIlWYkBB5BDRJ1Jy4nWfH+pqOkI56D80QOEIYftx7WG7f95f8Uh5i2p0qmhzagEAN3yVfZzgt6gvhIiQbjZOVGKCLvMedWt1e/eJ6hfIOF13qUkFcshNikutn8CZdd1pVZrIBaOIJHUCdskm/JQ= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1714989256; c=relaxed/simple; bh=W+uP1Xzo0QGwIGIjvgjEQaM3hRC9GEBc2dTf6jeCEAQ=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=GlE/HUwJSnogdMwnjy120//PdIonSyVF431EUTWh2aSn0ifddES/6oY9NBic4wqaFuyParkrCx477bN6lYTDZD2JWwRPbj6bKqjALLWxjiYgxR77U1E+ODnArn5dA5C55Z5720T2ms0/zPaihB+owZDGaRP7ZEzcVChmoWQwhH8= 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=yhsmoglW; arc=none smtp.client-ip=209.85.167.73 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="yhsmoglW" Received: by mail-lf1-f73.google.com with SMTP id 2adb3069b0e04-52025c91485so1089468e87.0 for ; Mon, 06 May 2024 02:54:14 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1714989253; x=1715594053; 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=EFhgl6guD2GoA3y7AQJ34n3OZOg5tBWu3g1w/ea5Ugc=; b=yhsmoglWa9q17WtS+AYhoBJlnhnMi4QliF5yuowiSK1UqDs2Pf9dyJscjelGG339vd 8XKuGroW56oLYystTSgqAN4hDunYHNO/fFwlDzjbQT2dPHuaZkuhNZS7fJwlucTdq7t3 TW2r19KMOonE9DSE+3W3vviJHD24BlUhq0scMDpLK5G2sku8+XfZASOpPrRT+T4zR6MW 6iCSQ5gUdUO9B7K8adWrUtv/ka+DOA5Wwq+IkDovl/66WbW7wpo4ele/eRbTo8xLZPdD zeqHy+OxhqLAJFPWIpQKEJT5HroO/o9Axs5uFXOTmULwRPXvu47pUR2GHKGoPr9x2UIV AcxQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1714989253; x=1715594053; 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=EFhgl6guD2GoA3y7AQJ34n3OZOg5tBWu3g1w/ea5Ugc=; b=BtMluvJERK9dCjYfsF3+phZZwI/H4kzev3O9FWWXQChRZ3tmPwJNyLuNxvF0c+mcEI q/4tQT5wUpq861py6wx39qWfKcQCaHzN+Djdqe+5UquJwSJ2JcGi0MdPmuAdhaP6pnZB OMPdapFNvqQ1tjRoR3iM5F2/VtAdC4uXnsle1kIQ76KrzYhhHOG3P6PlU4wkr5yBRwk4 wmXIfnlZgigZ7lT/eC669NNRBpGDboycXsAhxYJu0DL9wuDoSuCINCZBuLakzfFXnZT9 bGs2OlzzDrvT7hr4/zW2WBqCZBNaVjMN8fsjMySDmeF8SuNhmXcoYv0CjgU/zihfsE9b KUNA== X-Forwarded-Encrypted: i=1; AJvYcCXNd9ycyLXgbFoBZO6lWfWGN9GkJC3wEWRQqZGZ3W6utIKlyj6EZH3m1PyiCvyFCRRX+/75YIpVQslv9XWALjga/WH4b6Vr81Wc9XdF X-Gm-Message-State: AOJu0YzC27wuk9x8T60spUccdiarDZtDf8PGORkzfrP4h4A8dOHB/XrO UFR1CIUiX+aBxKe9838oauzfF5UoIJO7HoiMp5YaFrsP7JMRAcrJ1/cZtHyhnbuLtpcmRO64gjP Qh5A3W4efKxOJBA== X-Google-Smtp-Source: AGHT+IFxQtIkICEgPtZHYPEZWh098J61GE/MO3Oo4IR5rCHuzox04WC7mgPH8Mbq6LEd/92R9vCy0D7WDptcaes= X-Received: from aliceryhl2.c.googlers.com ([fda3:e722:ac3:cc00:68:949d:c0a8:572]) (user=aliceryhl job=sendgmr) by 2002:a05:6512:481d:b0:51e:2f65:6343 with SMTP id eo29-20020a056512481d00b0051e2f656343mr9707lfb.1.1714989252940; Mon, 06 May 2024 02:54:12 -0700 (PDT) Date: Mon, 06 May 2024 09:53:30 +0000 In-Reply-To: <20240506-linked-list-v2-0-7b910840c91f@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240506-linked-list-v2-0-7b910840c91f@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=5298; i=aliceryhl@google.com; h=from:subject:message-id; bh=W+uP1Xzo0QGwIGIjvgjEQaM3hRC9GEBc2dTf6jeCEAQ=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBmOKinNQFA7Dt4Jiu7iDKcG5Nh1AAMez0H+o1lT 97GWD9bPgOJAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCZjiopwAKCRAEWL7uWMY5 Rrs/D/9LmjqabenKG3DQxazA8r5i8/Q6QDUsEsQreqaefgXZmOy82aw0Mm5kjM0qKE7KEozdvna 7TmcuMq3p7FkN27/RBZFFVZhlAC28DbrowKAOhKltU5U+DHdsWhWBQu7iMf5EBY7/tO+99JsVIh dHXbWnP0m+clnh2dVFsjxHfGvsg1HsUtiNl/8e6LOYO8cSdvN68aiLbvlpRXshA2VOruETq5DKD 4mo6P3f7VXTXn2GKuMLS/4ccQ2B+JtB1Ek9lNH1T13y19hlfiXY2sA0/AQnmywQst9Wq3T30w6z hJ2PTrvq6fSxstTjSERdKZzltPylLb6dlbdSrAxg32fS0PKehnHEO9ijSvTtC1Gvo6VLGWGlgd1 ZeEmK5O2zGXOOxRghCs2qMLCUIDutdHiptG4vuI90sqOby2y+jmtwn8Tm3odmb5OdGvFg0WfyAS 6Vo8EjW5uuqyN+hvf7bsfDgegDScTjyN27WimpBVqCLfDnnGLpYAddj9/CzNukVoNSHXRMeaJvP ZhHz9QsIPzyfY3QYczA6XEIDFRilurvWB1iMzzJoLmiuKNo7mlcbzU5/dIA0MfI9HCNL0NuTJe8 dGUwcFxeYAFPmC1FRfug9M3a6pjVRmvnv+cdXXhBm0dSdTGDNPY+MOCIl3PMwm6tQ84wJufaViU YhF9Jz3YQI8y6Pw== X-Mailer: b4 0.13-dev-26615 Message-ID: <20240506-linked-list-v2-9-7b910840c91f@google.com> Subject: [PATCH v2 9/9] rust: list: add ListArcField 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 , Kees Cook , 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 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable One way to explain what `ListArc` does is that it controls exclusive access to the prev/next pointer field in a refcounted object. The feature of having a special reference to a refcounted object with exclusive access to specific fields is useful for other things, so provide a general utility for that. This is used by Rust Binder to keep track of which processes have a reference to a given node. This involves an object for each process/node pair, that is referenced by both the process and the node. For some fields in this object, only the process's reference needs to access them (and it needs mutable access), so Binder uses a ListArc to give the process's reference exclusive access. Signed-off-by: Alice Ryhl Reviewed-by: Benno Lossin --- rust/kernel/list.rs | 3 ++ rust/kernel/list/arc_field.rs | 96 +++++++++++++++++++++++++++++++++++++++= ++++ 2 files changed, 99 insertions(+) diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs index 3e687401c6d3..d88a4c0f5c31 100644 --- a/rust/kernel/list.rs +++ b/rust/kernel/list.rs @@ -23,6 +23,9 @@ impl_list_arc_safe, AtomicListArcTracker, ListArc, ListArcSafe, TryNew= ListArc, }; =20 +mod arc_field; +pub use self::arc_field::{define_list_arc_field_getter, ListArcField}; + /// A linked list. /// /// All elements in this linked list will be [`ListArc`] references to the= value. Since a value can diff --git a/rust/kernel/list/arc_field.rs b/rust/kernel/list/arc_field.rs new file mode 100644 index 000000000000..2330f673427a --- /dev/null +++ b/rust/kernel/list/arc_field.rs @@ -0,0 +1,96 @@ +// SPDX-License-Identifier: GPL-2.0 + +// Copyright (C) 2024 Google LLC. + +//! A field that is exclusively owned by a [`ListArc`]. +//! +//! This can be used to have reference counted struct where one of the ref= erence counted pointers +//! has exclusive access to a field of the struct. +//! +//! [`ListArc`]: crate::list::ListArc + +use core::cell::UnsafeCell; + +/// A field owned by a specific [`ListArc`]. +/// +/// [`ListArc`]: crate::list::ListArc +pub struct ListArcField { + value: UnsafeCell, +} + +// SAFETY: If the inner type is thread-safe, then it's also okay for `List= Arc` to be thread-safe. +unsafe impl Send for ListArcField {} +// SAFETY: If the inner type is thread-safe, then it's also okay for `List= Arc` to be thread-safe. +unsafe impl Sync for ListArcField {} + +impl ListArcField { + /// Creates a new `ListArcField`. + pub fn new(value: T) -> Self { + Self { + value: UnsafeCell::new(value), + } + } + + /// Access the value when we have exclusive access to the `ListArcFiel= d`. + /// + /// This allows access to the field using an `UniqueArc` instead of a = `ListArc`. + pub fn get_mut(&mut self) -> &mut T { + self.value.get_mut() + } + + /// Unsafely assert that you have shared access to the `ListArc` for t= his field. + /// + /// # Safety + /// + /// The caller must have shared access to the `ListArc` containing= the struct with this + /// field for the duration of the returned reference. + pub unsafe fn assert_ref(&self) -> &T { + // SAFETY: The caller has shared access to the `ListArc`, so they = also have shared access + // to this field. + unsafe { &*self.value.get() } + } + + /// Unsafely assert that you have mutable access to the `ListArc` for = this field. + /// + /// # Safety + /// + /// The caller must have mutable access to the `ListArc` containin= g the struct with this + /// field for the duration of the returned reference. + #[allow(clippy::mut_from_ref)] + pub unsafe fn assert_mut(&self) -> &mut T { + // SAFETY: The caller has exclusive access to the `ListArc`, so th= ey also have exclusive + // access to this field. + unsafe { &mut *self.value.get() } + } +} + +/// Defines getters for a [`ListArcField`]. +#[macro_export] +macro_rules! define_list_arc_field_getter { + ($pub:vis fn $name:ident(&self $(<$id:tt>)?) -> &$typ:ty { $field:iden= t } + $($rest:tt)* + ) =3D> { + $pub fn $name<'a>(self: &'a $crate::list::ListArc)= -> &'a $typ { + let field =3D &(&**self).$field; + // SAFETY: We have a shared reference to the `ListArc`. + unsafe { $crate::list::ListArcField::<$typ $(, $id)?>::assert_= ref(field) } + } + + $crate::list::define_list_arc_field_getter!($($rest)*); + }; + + ($pub:vis fn $name:ident(&mut self $(<$id:tt>)?) -> &mut $typ:ty { $fi= eld:ident } + $($rest:tt)* + ) =3D> { + $pub fn $name<'a>(self: &'a mut $crate::list::ListArc) -> &'a mut $typ { + let field =3D &(&**self).$field; + // SAFETY: We have a mutable reference to the `ListArc`. + unsafe { $crate::list::ListArcField::<$typ $(, $id)?>::assert_= mut(field) } + } + + $crate::list::define_list_arc_field_getter!($($rest)*); + }; + + () =3D> {}; +} +pub use define_list_arc_field_getter; --=20 2.45.0.rc1.225.g2a3ae87e7f-goog