From nobody Mon Feb 9 13:36:41 2026 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 1658679B87 for ; Tue, 2 Apr 2024 12:17:23 +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=1712060246; cv=none; b=TBmXseXURQc2cRt3TVUiaSlRAwrmFjQmTXgIGhuLXMYa6FUdWCn6hIitjw2VCRR8x88JemDf4dYebZSW+K2BT/6DuRSQob4wytgpBMaBgGgZTndhLjvBu79Rh/18tQrSkJQ+8RzyKi3lGJy1oh0hQ5kb/JArLf7asaz1oy5+VBE= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1712060246; c=relaxed/simple; bh=UsgURBv1RSxzn/fF5mwt730A2fCdSeYuA/w0Xn161Pc=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=qZkWzQQN7XpsBfVcjWsKFpzJoFp9kAve7WzW76fIsQxOE39gzWejDjf7FWpZYiTQ2agx8ntVoI70TydunCu7I4Mq9x5UHnnL2XvubhhH/JYRxMnoUOUoxsYzZzSJSmMUH1zzUPEpabPlXvHT/ytH2e57i8NAkKXHKRFi03YbJ8M= 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=bPCbnoQ1; 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="bPCbnoQ1" Received: by mail-lj1-f202.google.com with SMTP id 38308e7fff4ca-2d49fa5dfadso43483081fa.0 for ; Tue, 02 Apr 2024 05:17:23 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1712060242; x=1712665042; 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=wNss3TAREtZqEbxJmtLJ3dGzF3KHzOFkRpA9FxPuLR4=; b=bPCbnoQ1zBRKEbrORJpcuzORrjt394n6BYSEhhPgdtB9XtRmhSM6jmFb7aZxEKzqm2 Q1Bd24AZIY0WRbTcXGvJ4p2kLVdEjWwCbAUhbyYs2sK6pZ49F5NOiw/FQ3HAY7o6YTUb BMNtMAfBhBr9ZasNrzTt83VPncczLeVocieCFg8c9L4Fyy6NFlFNZMn7Nl4emuc4rp+e SEC+LwLS2k4L13W4QrdFlgsQUhWBOrsIp3lNoZIwR1oJjP6HAn/XUt1stJoEXi9R7GKt dF+uZDlRL4dsumEkSIeolLpFLAUOhgedrOQkmOGvNEeKyxavQ9dgjlXdK3G/bZXosbXk yweg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1712060242; x=1712665042; 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=wNss3TAREtZqEbxJmtLJ3dGzF3KHzOFkRpA9FxPuLR4=; b=QVcVtOa5oAMy7Wvqh9KKl7Di+DcbqS18rYyTXCoyUib5VCPV79qqwxODIgVtbwCkih Fj2Pqg61c1LVaQf9TvpcVAEfXYvbiEyN/p6gQospbq2iG8v6oW5IlnSAwJoKqS+v/DRJ oaVSFbHoCBiRnUOPTaVoAADX7qszlrrfr79TsIsLr0m55/wZvWALxRbywP0Do+1oE76x Or7p2k1EOjWoYc3Kk2vSCv5ezD6g7VOlfEbWyqewBMlNSSHV0a7uvRPA1scxCL648cU8 LcKCQaALvOg0BQ9BOv/oY+WUp9nPpWRxPDnhAKJtT105dw6HjtP87gAbSSbu1MOHXpQd cBYw== X-Forwarded-Encrypted: i=1; AJvYcCUPTqkSnhbRfOhd/2eX25ZW+gaohWu9T8ZVpBtcaBrkR41n4AcmFXznSv4Vx/p7S5Xx0PtGTTt2E0jlK5gXYI6yjut/2PfxUzy+DmPZ X-Gm-Message-State: AOJu0Yw26hvZSFaJobKFIn/n9mumxwDlkD7n6tnZhC+U498J98TOIubI Jknm0Wt4jpgaZCIICeT5FyRsFzgygAaUyjvOxmyzWmju/dNM7qUO1jR02GhErzxNW1SgeM/L8Ls I8dRDzD9HVIMUxA== X-Google-Smtp-Source: AGHT+IEHd11XDAbdZqpuVWb0FnsZI5epowbsAfJCgssim6jwtjRT/nyIZKdakENmtvX9/jpYXuHn8ckrpXIqnIs= X-Received: from aliceryhl2.c.googlers.com ([fda3:e722:ac3:cc00:68:949d:c0a8:572]) (user=aliceryhl job=sendgmr) by 2002:a2e:a549:0:b0:2d6:b6d6:e875 with SMTP id e9-20020a2ea549000000b002d6b6d6e875mr15502ljn.0.1712060241964; Tue, 02 Apr 2024 05:17:21 -0700 (PDT) Date: Tue, 02 Apr 2024 12:16:58 +0000 In-Reply-To: <20240402-linked-list-v1-0-b1c59ba7ae3b@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240402-linked-list-v1-0-b1c59ba7ae3b@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=15906; i=aliceryhl@google.com; h=from:subject:message-id; bh=UsgURBv1RSxzn/fF5mwt730A2fCdSeYuA/w0Xn161Pc=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBmC/dIv9x8o4CrN9dBpZXjjPH0S6/VI2E65Rlc1 139E5SuHoaJAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCZgv3SAAKCRAEWL7uWMY5 RsMSD/9ZM3dZdnWP7m9IhyXSA6svrXMYAVDNdkCbdwFk2sIvpKNFwq5SpqRuC5mFRBUmOOBJbbW ylOrzqXmGmpuXCCzSAa9lt8g5xDaAXxJC27kq9dcb7Q4/88WJXWUrDDMrxlQLxyjGakF9hGkCms jeBzPZGY0fPZeRcpXBIrdTfD6UF2U3nhz1CddY8/fsfSfNWJVtAzMibcYnj5J/Zo/95Rq715lz/ jG75JqgQtY4A057D28ChEnt6T6FFhg6QIgLmenjS+ecQ3SGVhtAn2MiKgnusyl3cvJbPugQ8hTO yCET3J1tXxW6CL+pk2YKCX9HqG6swDT1QEeh/fSJl5AkGsR8lw+Z7QpWLIzQ2x439Ldt7AwyqsX fRdGm7xu3mK7aI5rH6/gnMH2TkH6dm1YYoW9YbKBdRR672DhAi3O4V8N0HmXsZDxe62eoRKxhNe I8ExrKZ3RTdlmmC2fXQmEWgU+aAftAy+vIRrTA10jPiAHTcUoGenV7mr9/Ozc/ffP5L/CNM54yr 8Tek67ZLC+vZZPuxBuNfv8UExMYPdBaeigIQCRetGmovfz9K3AYISibHAoeY/xqCWg6eclLhPbl YkWM15TUZNyUPXmASMy3UHWLSMiHM7GOnvPERly8vXP+Ldk9My61t4HGDL3BGCZkJO9vQcCXlDW n12p9lRV8QrTrcQ== X-Mailer: b4 0.13-dev-26615 Message-ID: <20240402-linked-list-v1-1-b1c59ba7ae3b@google.com> Subject: [PATCH 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 | 302 ++++++++++++++++++++++++++++++++++++++++++++= ++++ 3 files changed, 311 insertions(+) diff --git a/rust/kernel/lib.rs b/rust/kernel/lib.rs index be68d5e567b1..30080328b740 100644 --- a/rust/kernel/lib.rs +++ b/rust/kernel/lib.rs @@ -37,6 +37,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..59d43f7a165e --- /dev/null +++ b/rust/kernel/list/arc.rs @@ -0,0 +1,302 @@ +// SPDX-License-Identifier: GPL-2.0 + +// Copyright (C) 2024 Google LLC. + +//! A wrapper around `Arc` for linked lists. + +use crate::error; +use crate::prelude::*; +use crate::sync::{Arc, ArcBorrow, UniqueArc}; +use core::alloc::AllocError; +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(&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(&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`. + pub fn try_new(contents: T) -> Result { + Ok(Self::from_unique(UniqueArc::try_new(contents)?)) + } + + /// Use the given initializer to in-place initialize a `T`. + /// + /// If `T: !Unpin` it will not be able to move afterwards. + pub fn pin_init(init: impl PinInit) -> error::Result + where + Error: From, + { + Ok(Self::from_pin_unique(UniqueArc::pin_init(init)?)) + } +} + +impl ListArc +where + T: ListArcSafe + ?Sized, +{ + /// Convert a [`UniqueArc`] into a [`ListArc`]. + pub fn from_unique(mut unique: UniqueArc) -> Self { + // SAFETY: We have a `UniqueArc`, so there is no `ListArc`. + unsafe { T::on_create_list_arc_from_unique(&mut unique) }; + 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) } + } + + /// Convert a pinned [`UniqueArc`] into a [`ListArc`]. + pub fn from_pin_unique(unique: Pin>) -> Self { + // SAFETY: We continue to treat this pointer as pinned after this = call, since `ListArc` + // implicitly pins its value. + Self::from_unique(unsafe { Pin::into_inner_unchecked(unique) }) + } + + /// Like [`from_unique`], but creates two `ListArcs`. + /// + /// The two ids must be different. + /// + /// [`from_unique`]: ListArc::from_unique + pub fn pair_from_unique(mut unique: UniqueArc) -> (= Self, ListArc) + where + T: ListArcSafe, + { + assert_ne!(ID, ID2); + + // SAFETY: We have a `UniqueArc`, so we can call this method. + unsafe { >::on_create_list_arc_from_unique(&m= ut unique) }; + // SAFETY: We have a `UniqueArc`, so we can call this method. The = two ids are not equal. + unsafe { >::on_create_list_arc_from_unique(&= mut unique) }; + + 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`, + // so we can create a `ListArc`. + unsafe { + ( + Self::transmute_from_arc(arc1), + ListArc::transmute_from_arc(arc2), + ) + } + } + + /// Like [`pair_from_unique`], but uses a pinned arc. + /// + /// The two ids must be different. + /// + /// [`pair_from_unique`]: ListArc::pair_from_unique + pub fn pair_from_pin_unique( + unique: Pin>, + ) -> (Self, ListArc) + where + T: ListArcSafe, + { + // SAFETY: We continue to treat this pointer as pinned after this = call, since `ListArc` + // implicitly pins its value. + Self::pair_from_unique(unsafe { Pin::into_inner_unchecked(unique) = }) + } + + /// 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(me: Arc) -> Self { + // INVARIANT: By the safety requirements, the invariants on `ListA= rc` are satisfied. + // SAFETY: ListArc is repr(transparent). + unsafe { core::mem::transmute(me) } + } + + /// 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.44.0.478.gd926399ef9-goog From nobody Mon Feb 9 13:36:41 2026 Received: from mail-yw1-f201.google.com (mail-yw1-f201.google.com [209.85.128.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 299BD79B8E for ; Tue, 2 Apr 2024 12:17:25 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.201 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1712060248; cv=none; b=C5hxeQ9VGksN0TecjwzR0jrLEWuplVPS3uTimK96VyAG8O1eIf+tbGOAPJvbRyMSA6NpmxvmwcWE2WERYpbf1dDwFuRlee+Qmd/mlRn2zGCIMFdAJdFjtX+N5+pBTNtncw5CIlHidOxribyCCk2Q26FQfTAZ7jpNAeRd/RlzZug= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1712060248; c=relaxed/simple; bh=scYXFXHzop4w5nE1MARFBQtsaiUQ99iycS9q58C08AA=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=MoLIQKMLH96M4VmFkh14917XomPsT269lj5sM4DHIfcjxGBIcnJwNacW3vrHCEeJV4MEqllQ44DUiTl+eaGPZMGjrpqNKKB3PyUH9aQPc+eRsFpsSIMtGtn4J6AVe/lc/G9sllJuVLkBP8dWxxyU8dkayk09HXCjW0JSmc4ZMQc= 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=InAaGKT2; arc=none smtp.client-ip=209.85.128.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="InAaGKT2" Received: by mail-yw1-f201.google.com with SMTP id 00721157ae682-61532249dcbso6012337b3.0 for ; Tue, 02 Apr 2024 05:17:25 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1712060245; x=1712665045; 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=mTRAKoexW03MplbH5ewhSVmvhGBv9gsHa3B5VmzHdqs=; b=InAaGKT2/ZpUbClvDHQ29hNCr1j/JtH8d65km2x67F3a4aguR2NtfkfiIuZC4f6Uok cIAanEa+mvqudbS3fwBOaSCgbiW0aIUy+oxuf1CbZAVcfh7QjXMomifB96GnF43uS6z3 5SP8JcAJARpJfElog6jd9E46jRLARrSjoaNTltx8VY76dffqBxIdAtPKjB7zm358y10y xpuIyvJmNAH1PnC+QDapZvoHIxNjswCIkV69Bmg7kjQr3S5R0mfDjJBtDqwBTa9K8CxI fyA7hq3pH60Ry49j4oEPg/3aiO3eE9LcH/un7tRoy7Lv5GLsL4jw123NgXnUZNQR9mT0 YO8g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1712060245; x=1712665045; 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=mTRAKoexW03MplbH5ewhSVmvhGBv9gsHa3B5VmzHdqs=; b=ZLycWxBOWbtreRRvEdBIGe9ON3VRuk9f9qAfBOzgk0zVK8NAM817jdzFmDC1VQgZF3 ptOKlpCSd2ob7JkNJHFJGWvFSsJtYYwntUl48vCWMWX6Zi8HKnhwGOh6sitM/piQpBqk rA3V8OeTqFKAxfQnkLzo1lMYOVliZeVLnNNzozsDdQA72qPT9+Mqh+VSnNZ/wifnzUvJ Qf7QDLDvR3ieELTbbZGhSQ0OGAkSUPZM+mmRdR2G2fTtkS6qtA1Ms/cwfnoGcwH6SgkB 4+I/B4sHVlBWh1flQXOf4ihA/y1AdhTWUdyxaT53PA45nADDUZAqEjBKUfkqVAWSX8rt 40tA== X-Forwarded-Encrypted: i=1; AJvYcCWBXTOgEdZu+LqnBiE4btpRoo9YFvzoQv9o8BNgZ6iWYpHRayEkjV1Z11iPh2fMaCkQWa/ccIITr5KktB0/pa/a24DuCCQXBplEvblb X-Gm-Message-State: AOJu0YxVS/nMa1/X1RitXLvJ/0n/XAsEdx0IOJt1pKNldlIDGflsqbhS 5x+RZsYGd2gRrUNFS4NeNFoSPoKOR7KjhEoFuKPcLsHOwwoQB5MXC5fPwGeEvEVCY/45pOMs9nl F5ejnXf8i6/z/Wg== X-Google-Smtp-Source: AGHT+IHoICpUitAruU1VmY3bIx+xHFNJYUJhCzek3lJKlsTeF4BVcZqIvLGvurW+TGFj1G8b2zaCgyBpYo72Ypg= X-Received: from aliceryhl2.c.googlers.com ([fda3:e722:ac3:cc00:68:949d:c0a8:572]) (user=aliceryhl job=sendgmr) by 2002:a81:5245:0:b0:615:1b90:d987 with SMTP id g66-20020a815245000000b006151b90d987mr466629ywb.6.1712060245157; Tue, 02 Apr 2024 05:17:25 -0700 (PDT) Date: Tue, 02 Apr 2024 12:16:59 +0000 In-Reply-To: <20240402-linked-list-v1-0-b1c59ba7ae3b@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240402-linked-list-v1-0-b1c59ba7ae3b@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=9552; i=aliceryhl@google.com; h=from:subject:message-id; bh=scYXFXHzop4w5nE1MARFBQtsaiUQ99iycS9q58C08AA=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBmC/dIw1Rwk2A9e1u96NJVmWcgv4TpW8F7lomm0 PeGbEjH7KCJAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCZgv3SAAKCRAEWL7uWMY5 Rg8BD/9+xs82n1gZLGSwbD0q2jLJXjlqJ5lvOAULl3kt6zWXP9e8/5Ut7q4HqLIWtScJszSMSRj dbc9s5OsX2X0HnuSOfwye/Fe8wJEtiP5sJbYMJWJuk2MozTX3eoKsRk3qlaAfrOiSRcSk1imKtb LCNBV44srm5q3h1Maey2keGg1nP4mrt0OS+MvIGsynRUkhiyvIvmI6FZj68ppCRM4zEmdbho/01 TLrPsvyOXysZhOo6Vh6J2XAsRySr6asx7eRbplGuw3ZAr10T4/pYQ3XY1ErDBBYnLvzkWbFVcNv TDaXbokX3cgl228DfIaBxfXoC6EHkn7vG/M8L6xlanLLCCKVb61dyKJRO7hZyUTtmYj//jSsJ+U xWkxoJ58vTjOsx8Vke1d1LJaZ1BfTxAKujavzC4I+Bwfsooxo8pYd3WV+Xk2wVaoHhXV2M/Iiqg qUfY7fb2Su17es1AaUBxfRcMPe7HypSW5JB5QHN3sTfP2uLPuvp3FRLEDyOsAsTG72bBkK5UXtm jYRpfprGornzkJE68z1440bWzmqRkTXT1Kyz34JZ8IHPOCgDn7sdEHahOBO96tTilEUbNbXud6t EGjUGBHI1lryJ8fy0eIOdo23U5hjeSzQv2FEvnFYCtr+0NRP4B5rTJARVjKsPo3c10oAYiuChNp aIHn/E/1lpGzv/Q== X-Mailer: b4 0.13-dev-26615 Message-ID: <20240402-linked-list-v1-2-b1c59ba7ae3b@google.com> Subject: [PATCH 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 | 133 ++++++++++++++++++++++++++++++++++++++++++++= ++-- 2 files changed, 133 insertions(+), 4 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 59d43f7a165e..5c27491a5889 100644 --- a/rust/kernel/list/arc.rs +++ b/rust/kernel/list/arc.rs @@ -8,9 +8,10 @@ use crate::prelude::*; use crate::sync::{Arc, ArcBorrow, UniqueArc}; use core::alloc::AllocError; -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. @@ -33,19 +34,64 @@ 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> { - impl$(<$($generics)*>)? $crate::list::ListArcSafe<$num> for $t { + impl$(<$($generics)*>)? ListArcSafe<$num> for $t { unsafe fn on_create_list_arc_from_unique(&mut self) {} 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)*>)? ListArcSafe<$num> for $t { + unsafe fn on_create_list_arc_from_unique(&mut self) { + let me =3D self as *mut Self; + let field: *mut $fty =3D unsafe { ::core::ptr::addr_of_mut= !((*me).$field) }; + unsafe { <$fty as $crate::list::ListArcSafe<$num>>::on_cre= ate_list_arc_from_unique( + &mut *field + ) }; + } + unsafe fn on_drop_list_arc(&self) { + let me =3D self as *const Self; + let field: *const $fty =3D unsafe { ::core::ptr::addr_of!(= (*me).$field) }; + unsafe { <$fty as $crate::list::ListArcSafe<$num>>::on_dro= p_list_arc(&*field) }; + } + } + unsafe impl$(<$($generics)*>)? TryNewListArc<$num> for $t + where + $fty: TryNewListArc<$num>, + { + fn try_new_list_arc(&self) -> bool { + let me =3D self as *const Self; + let field: *const $fty =3D unsafe { ::core::ptr::addr_of!(= (*me).$field) }; + unsafe { <$fty as $crate::list::TryNewListArc<$num>>::try_= new_list_arc(&*field) } + } + } + $crate::list::impl_list_arc_safe! { $($rest)* } + }; + () =3D> {}; } pub use impl_list_arc_safe; @@ -166,6 +212,36 @@ pub fn pair_from_pin_unique( Self::pair_from_unique(unsafe { Pin::into_inner_unchecked(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`. + /// + /// 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 @@ -300,3 +376,54 @@ 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, + } + } +} + +impl ListArcSafe for AtomicListArcTracker { + unsafe fn on_create_list_arc_from_unique(&mut self) { + // INVARIANT: We just created a ListArc, so the boolean should be = true. + *self.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.44.0.478.gd926399ef9-goog From nobody Mon Feb 9 13:36:41 2026 Received: from mail-yb1-f201.google.com (mail-yb1-f201.google.com [209.85.219.201]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id B5BE27F7EA for ; Tue, 2 Apr 2024 12:17:28 +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=1712060251; cv=none; b=jtrHOjMxVXfWtFjfTF5anGeFHrVNASvhowOKJ/Sn7ebTBEPl7brab5+uuVK7M4LNwi0y3sByHJL+KB+ph04dETKHAky+1M3EIHA38Z6QLTpQK9j68MIo2rNgMkOiTA3oSVQc83+Kf1PCL2sIh2W2AzN4RRNYYC7Iygu+GRgp6Ug= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1712060251; c=relaxed/simple; bh=2PIcpJp9DT7VacmhqXAmL7iXpjNRwDR3ul+Ch/uIEhU=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=E7SSUUDDV8YBSo0kGsFSHHEC5lwXiaGvnEVwqVl692sOvtEv22nQCuXqmqVVCuMNdSYrBoZthMGNxFzzIf/xHfA1/CUu0RNAgYeT8kmgegIiJcKocvlrI/+nGjOY6utWgBI32m8MrZHSHUMVUk/Qp1b5DxAPsXGDtiKChlm0XK4= 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=ydrkxjoa; 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="ydrkxjoa" Received: by mail-yb1-f201.google.com with SMTP id 3f1490d57ef6-dc6b269686aso7108540276.1 for ; Tue, 02 Apr 2024 05:17:28 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1712060248; x=1712665048; 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=Vhv4LxRJZ6OxQtv+kEEl5Wq7dqUJQo6ze35BbQzNlO4=; b=ydrkxjoaY/TlM8e9PL1P0qbWcShjQjKiWS+TL/D17jJRylybrXYKFHByLmyXm3an2M h5n6zthcuCVsjUFVq48N05h4JrmvJOsez9m3TVHS6aeoFKmohhHfADpU+Fg6T717+Jcr 2q0n7Yjy+xWRTvRZcK/M8UKgy/QD69cpxq3/o5ZtJpEnE23W0VFG146ZLvByqv2DOe9L pVitP2skwuYankQ7oPb8dlesEvR4cxWtXHJ+N9jW/wS6Q65eej1BdVACEq0+bMGAHzm5 f6GLSLp1jdVrD9toP6IW6B5ULNpKsGU1ip8Y+qPOLKghtTmGMSr5kONvVBGz9of8XmrG cLvQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1712060248; x=1712665048; 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=Vhv4LxRJZ6OxQtv+kEEl5Wq7dqUJQo6ze35BbQzNlO4=; b=EgGxbRVxL5CdU9z7/rCdVv/2fAA3BwyMMVwwznDP52yG8Z3Eo2TDplqVC9x0FHq4XR Sa8YP3baPs5FTrhycIvsP+IwkN4k9VrqIXmU4DTdqCzCI/de8w9GcyOoarhE3FQlieg7 E5LdeSjK5lu0j4qddJ4THX/ha8L6byVlgC2U7fASBsywe2dspBaSypY8mUmNSfQd0mat /Iky6QeFMRgwAWKZ9jUzUaoabsxs7E4bCMRqtv+FboJ4D8Ydf/Yg1A5C6qW8y1jxOwhO 1RhthTftazDQNlkqaM6GJik6L3n8HGzzj3XUREUoIhddUAtvwEbr8Db5NO1RcAWztb6G FEJA== X-Forwarded-Encrypted: i=1; AJvYcCXQWhYCo2tXjdLjQdiNUX7SMk/jSxfbKynPToWUHXotseTJuoVjjFX2/Xqm7yaW5XKM9mKaX8PN+XGzdTTl3q1TolCVMfikJB1u5l2u X-Gm-Message-State: AOJu0YyCaiMro+lvUDr9fVMjorTXkQ9+8NEKK5sjV8BRJ3SOL7SrfzQY MC0UhdKNN6aUKx0pQkb0v3H8gSYZhQ7QzYjE6dVeM1iaQvf2N3b0CjfMoEVfeJ5F1PCVVVbm5Z7 64qswu9BuwRaeBQ== X-Google-Smtp-Source: AGHT+IFPeL2qwx829ZFPHGJYFkffe6dJwQ4bXNP9dPoxKP7o36b6Dqs5va8TK6Yn0yc6KOKjxZjuDd8dBh5Krq4= X-Received: from aliceryhl2.c.googlers.com ([fda3:e722:ac3:cc00:68:949d:c0a8:572]) (user=aliceryhl job=sendgmr) by 2002:a05:6902:1883:b0:dce:30f5:6bc5 with SMTP id cj3-20020a056902188300b00dce30f56bc5mr954191ybb.4.1712060247742; Tue, 02 Apr 2024 05:17:27 -0700 (PDT) Date: Tue, 02 Apr 2024 12:17:00 +0000 In-Reply-To: <20240402-linked-list-v1-0-b1c59ba7ae3b@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240402-linked-list-v1-0-b1c59ba7ae3b@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=5967; i=aliceryhl@google.com; h=from:subject:message-id; bh=2PIcpJp9DT7VacmhqXAmL7iXpjNRwDR3ul+Ch/uIEhU=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBmC/dJexiium8UT/OewJm7DPd0VgrTKGLZevB6+ tW4etfZDoKJAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCZgv3SQAKCRAEWL7uWMY5 RpazD/4/uDlpm2FRIQJKp/aRWdG4z3cc4Dmds/xdrritb9hgsytKePUaWn43aBKudy+TqUgwywk GLl8g2S675hNtyAfEO8ppFQU3sRVRiGtSouPyeacJzW5hw63j+PLHznz6BP09t+Sl/k8eGpF/oT febc7azfxUrpOV44CT5JAxXeGhca7ebYsQpoO3YlidgHhB5BelV8EFX000wMym4AZKrxtIJUHT+ +WCxUjO9+HE4R1XVqlhZEI8TpTbTYNJ9TzNnzWxnvWgS5RXNMRisaSiC3QMh4jsHRb0nccO7sD3 G8eB7g4I5wf794iKi7K9GflmCAsBV9N/H7dNRydlvvLY6lRrK/epaVGxPcb77MXieVkxDUDVrao 7YyGR0HpsQjqjoapiXpNyAMUNr1jAjHthEmxtO0kWEAGBvps4P+mOvVpOoXNTHYqkG6kiM/kif9 CZ6Zu5ra6Mpvd/CGjYujV43z8srPvbwCFelbZ4tl7XH9FmByJtcvQqZxX+exfkroG51/Uzq+j4P Hu2mmdwBslps6ShnZEQO6gBwL74lBFkKaEcnglZqQk7WUoEOvGs4TjLU+oYgXyr949TPln6cFCP IYWl/aDxUxumQnPwbtiy8Y45H7NIBIQ/Y7F31UJum8wRdW58zIIDcEDNp10cDhhTk9ewm14oK73 qzMwlEqoZ7kITaw== X-Mailer: b4 0.13-dev-26615 Message-ID: <20240402-linked-list-v1-3-b1c59ba7ae3b@google.com> Subject: [PATCH 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 | 115 ++++++++++++++++++++++++++++++++++++++++++++++++= ++++ 1 file changed, 115 insertions(+) diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs index c5caa0f6105c..76597c49fa56 100644 --- a/rust/kernel/list.rs +++ b/rust/kernel/list.rs @@ -4,7 +4,122 @@ =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 currently active call to `prepare_to_insert`, then= this returns the same + /// pointer as the one returned by the currently active call to `pre= pare_to_insert`. + /// * If there is no currently active call to `prepare_to_insert`, the= n 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.44.0.478.gd926399ef9-goog From nobody Mon Feb 9 13:36:41 2026 Received: from mail-lj1-f201.google.com (mail-lj1-f201.google.com [209.85.208.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 58A118289C for ; Tue, 2 Apr 2024 12:17:32 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.208.201 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1712060254; cv=none; b=f4YmDxRNOC7tuup0N1DPWTHFdSxEpYiZh3pzCM+ezc/3QNAYH9Ic+cTwbGMq7G9VnGz3RitbtxNa4kvuGjywvVTlRJhujBNUGqmGppKcunJRTtB/swuy5AoZvQmw449fm3BDMUZEk7K775XjBmcjZPH1Ou8r86+TM275GrgEuGo= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1712060254; c=relaxed/simple; bh=HqTvdg8fzcYf4HPXuYAv/EzwRzpXiMamY7vxsIqyqQI=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=ZOoTWRYuDI/AhxiqvjNLDkX4PFxpTOTZoe9xCwHQr4Pc8ruZzurSLxKgq6PByw4AZ0WLMNI0GLe+21juEyb7KjpnkEyMBFm/NkBGrCCOs9NUm98bVJVqvA/pl7EBrlPyrutXnndmhTYEZkbHcMkmOL5Z8ZMHcuBEz4XNWB36KaA= 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=cyyOvmnG; arc=none smtp.client-ip=209.85.208.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="cyyOvmnG" Received: by mail-lj1-f201.google.com with SMTP id 38308e7fff4ca-2d45c064742so51849351fa.3 for ; Tue, 02 Apr 2024 05:17:32 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1712060250; x=1712665050; 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=VJ5h910JMlBSC/fYAKRLARZ1uSxij9BJ97PB2fg4buc=; b=cyyOvmnGpPASiGWAdjt9Gbavog2RXcsEkEJUtZ6yGwAIZrxQYl4gZ+pA765qa9WkGW 3lvrbTdhwsKgxo3RRSqgAFd9i9Do4mynWhqmfC0bwQ0PcvrRyRO1uu9csWsJ9xu/NK7i nEyNoWlyQQxl2diCEiNSb0cE/DiU4yKTDN/Rg1umsVNyMIhDCzF8bewSH+phtYU3SREX xPaGlwwvqSUD7+sW/UJosKK8ob9uabhjuANsBK6KH9umy1ULF8DMPZUtGrO0lCgjJNBO 5jJ3E9xEs9YGr4Xvuikrnlze1PgcAsOvLDohdXnMNhkPVST6w5G+N/9VmWPyaCElxL3/ 7nbQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1712060250; x=1712665050; 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=VJ5h910JMlBSC/fYAKRLARZ1uSxij9BJ97PB2fg4buc=; b=Is2SiWI/qGmEYWnmpxvMIZy01yYXJl6W/+eHl5ji8ng4C0UiKvyuVxR9H1VLPUJe6r 4Kep2G7KFOnJztzbo0Up+5QqnhNbQa2Acd5vedkRvvff/Cw//ymd6Mg1eZU1hLxNb2RF Yx+fonJ0/iwr0IAs1cH7AR6UFmijOMD64SAb8aKFz3SmzXQ5ta3yfF9KlW303DNjtBkn egPlP082mFHH68wfWWMT2HTswnHAItlF77hU3bgk0SmWhWC3oiUqlFpTkI10v8DYekL0 LKHgqBPCrAgxvU4wvLrhHxqINpGOVmrc92rdRtfYabEgU2omkiMRRZUxzH01jMeInAXv FxVQ== X-Forwarded-Encrypted: i=1; AJvYcCX0Flf9xflca0Tab/rIXZV0+xa39XyGb7quhuVhEdCfu5RI4/gb130R7T3SQvtNxjqbMDgsDF5fSLzqO/KlPwCFp5gVLhXVoCQoCoPS X-Gm-Message-State: AOJu0YziP3X7GzG95VHsQDVIi7I0I5KY66Mh4KYbsrYBnoPw4OcJkzNh 004nMJQUSBRCgEymdfXlnWJ8Y+gBlK2ZI+dGeP3vfngLC8MsxJ4qfV/qE9B3oim6tmQ25SHmmOA Wkj1uWrAlMUewQQ== X-Google-Smtp-Source: AGHT+IGY135rOcGmNuA3jaXeb+vBROjCWlk+6yRzcegrd3BpG/SUap9iAg9KrrmEOxSrp+41hlvbyzovOg7VJTs= X-Received: from aliceryhl2.c.googlers.com ([fda3:e722:ac3:cc00:68:949d:c0a8:572]) (user=aliceryhl job=sendgmr) by 2002:a2e:3814:0:b0:2d4:2b6a:bcd with SMTP id f20-20020a2e3814000000b002d42b6a0bcdmr10846lja.6.1712060250553; Tue, 02 Apr 2024 05:17:30 -0700 (PDT) Date: Tue, 02 Apr 2024 12:17:01 +0000 In-Reply-To: <20240402-linked-list-v1-0-b1c59ba7ae3b@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240402-linked-list-v1-0-b1c59ba7ae3b@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=4778; i=aliceryhl@google.com; h=from:subject:message-id; bh=HqTvdg8fzcYf4HPXuYAv/EzwRzpXiMamY7vxsIqyqQI=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBmC/dJ7YNemYzY7yvbSfEA1iHpsFzU7rZlstsYb O9jWvygNSyJAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCZgv3SQAKCRAEWL7uWMY5 RhjvD/9y5D0AUnLuHOcIgpU790uliJQsxlpZJLrGzlPmYkLNNuCTCPmM5Oj7PsKZ1rPF2fXHpxH dEuiscwI6rhP7+TapPrgvNR9ACM7Liz9eyy/XrdZ1v+tHxjoOoNlfUHm++gw0Dfonrp/h7mYVPi 4EJZlCiHjLWr8R+AIAhi7zUAx4MVm7l0ANjQp/7UbiQeBLHuDtVD/bwsXokLscxubGUYdw5rXe+ blZu9Ue3m4ew7Mi6V4iEMMwtIpEEOGs+5LbJ+ii74ORiNJktmHpX6tUqeuMdgfXrukTLUed5A9F 8FO1OTFJf9wWM1vDV4+a19o+e/JkQQkfPYg2jDjugaxKLROHdtgwY+pe2FoWLVVoTDy16KLsN3X iRAI3nlCQGMCRSTcTJ1dPftYGPR0g/b9Ln+UrGaYCo5rEaGC3KSB+ZCvqgBmT2DUe9Lya4DV2gE wRuAY8kOnoPbM5sNejk2Bk9nCoHjMtC0RcfMm8uUdWciD6zxKoGAprKnOq8GokXxpvPx4fYSuFA t7VdCQTNgef3cJadOmWGRi+kT1qCtQ4MWpZ51m8r6F45jbI4cesuQ1ASgql+55mgP1lCnTdyEX3 X5/dvzc/jhYR1OoJauw9uyRkST6aONgOPDxW13pAQ8E8KbPvnRJQLH7gx04x8vHnnHDl0hSkUDB Sj4Fawr81lUDTlQ== X-Mailer: b4 0.13-dev-26615 Message-ID: <20240402-linked-list-v1-4-b1c59ba7ae3b@google.com> Subject: [PATCH 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 | 98 ++++++++++++++++++++++++++++++= ++++ 2 files changed, 101 insertions(+) diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs index 76597c49fa56..7af5109500f2 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..9e2f6d6d4786 --- /dev/null +++ b/rust/kernel/list/impl_list_item_mod.rs @@ -0,0 +1,98 @@ +// 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. + 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)*})? ListItem<$num:tt> for $t:ty { + using ListLinks; + } $($rest:tt)* + ) =3D> { + unsafe impl$(<$($generics)*>)? ListItem<$num> for $t { + unsafe fn view_links(me: *const Self) -> *mut ListLinks<$num> { + unsafe { + >::raw_get_list_links(me.ca= st_mut()) + } + } + + unsafe fn view_value(me: *mut 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 ListLinks= <$num> { + unsafe { Self::view_links(me) } + } + + unsafe fn post_remove(me: *mut ListLinks<$num>) -> *const Self= { + unsafe { Self::view_value(me) } + } + } + }; +} +pub use impl_list_item; --=20 2.44.0.478.gd926399ef9-goog From nobody Mon Feb 9 13:36:41 2026 Received: from mail-yb1-f202.google.com (mail-yb1-f202.google.com [209.85.219.202]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 6059683CC5 for ; Tue, 2 Apr 2024 12:17:34 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.219.202 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1712060256; cv=none; b=D9QoqMGzLzTLBOobU9bPI5c3FyTFsBF1qnlUeTNW0CCceU5VD1dSX9dY5wLMf6UYzu9UikZpZwgFXCVoSEWfyZ+fpdOrYrkqp+vKymNan2P1Y4/DhSwrPF766ZTql25RGMf/Rc/s0Cy8OTLv490g2eW6LA5ATXisezztKYGxYHk= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1712060256; c=relaxed/simple; bh=yhgZAfXFmRRhY9kBUH0LIo35FjPWeAgq4Ytu4D/AAx8=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=p4i95N5AHUNY5amKzxV6z1pFrUvVeEX7dJrTPzm0OKQCDHTeQsM6fg/jbi0KOylGZvmn7dBUOmNwbhw24XkY0VNsLDj2bNZYCVnVFV17P+FB//f5bH3miGs2O3qV3zxlcCsYJWDZlXTKw/ITA4XVfrMOwgvUYVhrYYBbqoD5BPU= 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=Dsqc/bab; arc=none smtp.client-ip=209.85.219.202 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=flex--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="Dsqc/bab" Received: by mail-yb1-f202.google.com with SMTP id 3f1490d57ef6-dd169dd4183so5656277276.3 for ; Tue, 02 Apr 2024 05:17:34 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1712060253; x=1712665053; 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=qRZU3o4DKcL9Cdkic23o3zfbWrM7i4Tw/HmtgQ9VyFw=; b=Dsqc/babMYDQ+SmGKCuqW+LwYYpey5UORQfKON1IoOY1vP5ciguiH/k2O7B35gzQzG +dTZwALmlEFmd4h4ERfCghZ4qiFmaBcwttqNlq+B2XLxJHOM1qzTrLRTBz0XOI+JfcFj KvIql+CSnPKBtUGn5/V3XRjppkdGugDxlQM43+deEnCnxTBJUgPj7/GDkpjdaI7mSVmR YVsWt0juO9rpaB9Dy8nX6jesuNingzz7YvtJd1F/jQwRtOJLLTuXe2c/HsdxcrCyfq2O xqgrz7kYHJDv8futEQ9CMVB4VLRgf9uezYK1cymJbHeTMPy/mtCZ/q8pIfuaxmYOTjTP 9Qpw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1712060253; x=1712665053; 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=qRZU3o4DKcL9Cdkic23o3zfbWrM7i4Tw/HmtgQ9VyFw=; b=te7hN2FiDDlRmmyHykjMMWmaVa3gtRXspLtL1EZuRisAO14cfKatTs3Tl/NscPa+Xd NN9fDSvvgNV2ouitInZU3X74zd0/ReAUIsRAgOg0XpEigY2NAZTeieLFt2XXETGmXAB0 +x+xVI6mM+Pob+tYFs9GYjd3omfvpWjxbetSEEk/6oF2xKKNc21dE7buFeYmWVQglxKZ hlvX7Ce4IfgrTzCBLWSXQckAWvDJfQ0x8ljMPufjjKJZzG4RwPoIqNoHoNU57Jis/It1 cLuZ17Sq/6uZeU5QKP0UOV61ymkRCTIYt9n0LmngVgtMXvz5PBVwBowudih4Vj2m5w0T hB/w== X-Forwarded-Encrypted: i=1; AJvYcCXidu3g/KttTxHIEZEGD1Rh/fP2VApVyc31AN8vro7Ol9EUuNQX/fWLmLjN7hclbbSJy6PT2IAaEaWB8+FhETcAeIcyVpXPKyMOyozm X-Gm-Message-State: AOJu0Yzy6wN4zs+VMKt7J/8wp8SOv+WCKhRkV+jGiBGc2CJiLCHOVl6N zBJuypqyHQhM8l4bjFMTeZDpFjtYSPUYMvbWEDMqZlLITyOn8SVhY5wpIcDu6ehe3Vd/ucz5eH4 hOwUjK/XnuzKYGw== X-Google-Smtp-Source: AGHT+IGCqPzyxAi6FIXF9R1ausIFuDEPd2XSTC0WaKC4DpSSQtAJQ6GYlkF8SRn8d3AmtpLXRoKNsKL3jKnYJRU= X-Received: from aliceryhl2.c.googlers.com ([fda3:e722:ac3:cc00:68:949d:c0a8:572]) (user=aliceryhl job=sendgmr) by 2002:a05:6902:2481:b0:dd9:2a64:e98a with SMTP id ds1-20020a056902248100b00dd92a64e98amr818915ybb.9.1712060253479; Tue, 02 Apr 2024 05:17:33 -0700 (PDT) Date: Tue, 02 Apr 2024 12:17:02 +0000 In-Reply-To: <20240402-linked-list-v1-0-b1c59ba7ae3b@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240402-linked-list-v1-0-b1c59ba7ae3b@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=16615; i=aliceryhl@google.com; h=from:subject:message-id; bh=yhgZAfXFmRRhY9kBUH0LIo35FjPWeAgq4Ytu4D/AAx8=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBmC/dKbNhyFwGhIGVrySb84b1KR3gVYhZyT+sLt of7HI5cO7aJAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCZgv3SgAKCRAEWL7uWMY5 RoC1D/9ZnyLoMsrue/lXIR4SwwvULPd+ZkoZRlzVmON1QPCPUspiFDmtVgdf60yNzm17H3t25Jn BHHvVLxXUJWEfw/qJ5y1N+B2ukTfZhEkwgwvCFc+1cKR2Oc3n3fSmdGbBVyCn+NGbSNeAlKECfx 8lX2wEP0QwDx/nWViY9Eso1dP8Hk6UGKURG1EuPVZiZDBicz9HRERcZhaewxp/Beyz7ucX8qDfZ xj0WCzJ+a+GdGxAXqUvN03ydyQgccgQeRXZW/99sHxmXzBDmhKtct3NIbFMX5KINi0Eb4TBBYbA 6MKbmMmjalDE0qxM2nK3FqQR6MoGi5tN7q9UULx0jEYc4zFrNVW3c1H2jI4BinMha6o9TLmIsFR Xm8JdQZKmUQW8ekX9VfiWnNQhpJicftcgUshOtgiQLgHEsMnEKXLaPKXvsKkx2jbJYLkSdpl7Pt t6UrLpQp6AOJuXVRSWBEgX3YfZdLEUAyz7GDORyT4hr+mZxJQ2YydNfyvA0o40oJjMxdmKUhsti VsPqnTPAFtlcNsqq4iPB/HmepkwI880IUqW1VzlraahA2DAlK8uv8TqEnTrdP4ckZHP9Glk5cs8 bCb/gjKW+k3Ak6o86/+58pK2/VheLVKcazUUt9HRArBZdoEIWlLfjgrTKRI0kCL7ZxIjOGH4sjK 8aLSy+hXRPo/UVg== X-Mailer: b4 0.13-dev-26615 Message-ID: <20240402-linked-list-v1-5-b1c59ba7ae3b@google.com> Subject: [PATCH 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 | 294 ++++++++++++++++++++++++++++++++++++++++++++= +++- rust/kernel/list/arc.rs | 6 +- 2 files changed, 295 insertions(+), 5 deletions(-) diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs index 7af5109500f2..7e9ed802b26b 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,41 @@ 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, it points at th= e links field of the +/// first element of this list. The prev/next pointers of items in the lis= t will always form a +/// cycle. This means that prev/next pointers for an item in a list are ne= ver null and never +/// dangling. +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 /// @@ -56,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 /// @@ -103,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 @@ -125,4 +159,258 @@ pub fn new() -> impl PinInit { }), } } + + /// # Safety + /// + /// The pointer 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 + /// + /// The pointer 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 item =3D unsafe { ListLinks::fields(T::prepare_to_insert(ListA= rc::into_raw(item))) }; + + 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: 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; + } + } + } + + /// Add the provided item to the front of the list. + pub fn push_front(&mut self, item: ListArc) { + let item =3D unsafe { ListLinks::fields(T::prepare_to_insert(ListA= rc::into_raw(item))) }; + + 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. + /// + /// # Safety + /// + /// The provided item must not be in a different linked list. + 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 items in the list, and prev= /next pointers are + // never null 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 + // due to the writes to `item` below. + unsafe { + (*next).prev =3D prev; + (*prev).next =3D next; + } + // SAFETY: We have exclusive access to items in the list. + // INVARIANT: The item is no longer in a list, so the pointers sho= uld be null. + 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` field of an item in a list is never dang= ling. + self.first =3D unsafe { (*prev).next }; + } + + // SAFETY: We just removed a `ListArc` from the list, so we can tu= rn it back into a + // `ListArc`. + unsafe { ListArc::from_raw(T::post_remove(ListLinks::from_fields(i= tem))) } + } + + /// 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> 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 5c27491a5889..fb433a2cd253 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.44.0.478.gd926399ef9-goog From nobody Mon Feb 9 13:36:41 2026 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 2C94A84037 for ; Tue, 2 Apr 2024 12:17:38 +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=1712060259; cv=none; b=I2DxLaezplxtaAsWuju6Emz5WTJ4hSRuqjXzCMRCbUfkEdtyskYcgfnhh6xWyuCZEv9vVTI9njbDTb/EugFEIq7HLoCCypUP6h1/rbTkStV87ELBeVNex+yI8x4qNtLz8+8XPa6DMiEwXGTw4C4tDsjJfA52/IwRw/JX9oNqYpM= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1712060259; c=relaxed/simple; bh=tl0YF8G31hlpsx1yxv+0P/semrPgJkUCNi2Z3V8+6S4=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=IvZzgSVqZFZcJPVXI82QLNHToKeYgsk5P2EbkM1UZlVqYQYU/8c2osRdy/OS9/ixediowK60lyOUxGcRjd29EzpiDEEL/XqUuv3HrobdHaeJGkR+BZPBpNxSB1Vnl3Vrgcx6InAo/l48gBHo00wpFdANimesXW8RknUbE97/7FM= 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=WOn/ak45; 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="WOn/ak45" Received: by mail-lj1-f202.google.com with SMTP id 38308e7fff4ca-2d499513d62so43179791fa.0 for ; Tue, 02 Apr 2024 05:17:37 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1712060256; x=1712665056; 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=OHvJpyspEd5owonTerg9v2PB8rekG9Ag8roT35f7WSw=; b=WOn/ak45lBzd/cHmYziJ/GOz5+h6w1CFbWVfNMfMV2z97KS3pllw4K06tCmA5exlEI UR2l2IloYZ/Tg4YIuLsP5XXfqgtsXLm51gyJvp48wAJOUa1Ia5/mVKKG8NmA9eQ5R7sq xtOCYbnTrjFmLfQ2CDHHl8GhPxq6FAOMuKfXOtE1HK5xhvUdLkAuT8VIrtWx4JChaNJs XpmI2oOwOIVWYz+zqMmZnbq6LbWNhdBn1kdbyRfNj4IcNf9aILXrY1zjqJqazrsDjvG8 9eJOiDuN3QOfrNtP7XvSlJhprM+J75XYmT2dKvN5NslMGiGEBAG5aKrl5TXk5JCt3Nge gxLQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1712060256; x=1712665056; 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=OHvJpyspEd5owonTerg9v2PB8rekG9Ag8roT35f7WSw=; b=oDf41KESSsRyvZBgmiYCpENlL4GL102Ol8rdtHXdWNt8DyfxHto7CJVKEbYQoY2Di8 MdaqkZKnjtjH6aeCfjA3z0uwp8+28WWsk5JyzvBhLdjYGtiYwNkv2pl61RNf+uWfiJZr RZMG0GVYKfSP6bYu/Nq7Y1LWGRwWIP029xGvx/9nLuc8+6aVpXXd9/2y1OVY2VHboG8G DADE2RCFclvHnzKO8CFiPG9jVLh3OSoSeRdyU4O8PxVJuf9Fj4f+rMwX84/H8vvpWIWn Bw+/e2hmmhvYd0XZKavOFbVnVBvjLNmmWwcyljz33R0zfASekmzd4gMYfMA4Shgezv3w 8tnA== X-Forwarded-Encrypted: i=1; AJvYcCUJQFo9PQaYizV8gqcmidepC49MII8wxxnKv63hCspXfp7V/REh3jXVIMxx4uhc5pxWnDco7Pl6mL64uToNuvldtg8NfyW5U5aJCY7P X-Gm-Message-State: AOJu0Yxo5FomkpdHvnuC37U1dTstzfKvTpRW3MY4pivHgqizXBK3mTCc VMwM9wN57qnneMa90xAdFmsf6AJ/gF4cb0uxvDpZATg81ToiDDUpef9oFfJPAbek87XBdGyIlIb OZ4tQpoX+ncLvxA== X-Google-Smtp-Source: AGHT+IHQcweqPWnQDgxPlcTnQ03DbxUqb6QIzmGBYSz4zzRinM+vysej/8JddXLZidGUm8vCJq4wLA/avKwfIVw= X-Received: from aliceryhl2.c.googlers.com ([fda3:e722:ac3:cc00:68:949d:c0a8:572]) (user=aliceryhl job=sendgmr) by 2002:a2e:b24f:0:b0:2d6:87ab:255d with SMTP id n15-20020a2eb24f000000b002d687ab255dmr11456ljm.3.1712060256408; Tue, 02 Apr 2024 05:17:36 -0700 (PDT) Date: Tue, 02 Apr 2024 12:17:03 +0000 In-Reply-To: <20240402-linked-list-v1-0-b1c59ba7ae3b@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240402-linked-list-v1-0-b1c59ba7ae3b@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=4960; i=aliceryhl@google.com; h=from:subject:message-id; bh=tl0YF8G31hlpsx1yxv+0P/semrPgJkUCNi2Z3V8+6S4=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBmC/dKo5hvnIsyLPwPScT3d6UA+GaTaJPrAEJfb APdtc+EVZqJAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCZgv3SgAKCRAEWL7uWMY5 RtfXEACBrJXrx04vXmhwnOrt0jVRgCF7XbBsJXFj1oR0C/pOlQUV1z7UI/ucnWLz2HKH2mKDpVm 9BXP6pisrxMfn+FjBnQ+y5Bau5Mn4SiRPNYVM9RW2wklu089c/9o6ikD9a3I8f1AS4D0uHk7FF7 p43TxR4SJ3idVH0G2v9FZxZabL4TD4bzJ7GbWRmdnBNfn3LagCsbl2UPxqYEvaEt0y4U4m0/3+2 yFQF1beR4eFMM4ezmH5g370N0oJ3WaEzccjKcSuML0e1+GJ4EhXBI8EpgH3OX+E0sO1DvM3TEoL 5xaIbCklcq8gvmEKiv7vQJymwGhy9btsHD9ajUK5l9fnI/ka4IYLc0TbKiRIvnX+trNwW4OdShT 5+uMj8mlJbvjXqaXEsiuEHjxqkJ61EkDTtkIycMxoa40vbs8SgyePX8rMCabw/xyXiAHKTV78kp QTCC9RgqEY47J77w7bUazzGzzqSoLF+8XyaoozaGcy0CA7jTnoAclkX6PWCUna4FcaZ7m+YuJrz v0tCJtedgslQZwqSw5TdX3iBPZ1XX0K8xzYEp0nd9nT0AC/1ix6kKYPMNG8cNYESC1ovZlLDAoc 8H+0U1ZEeOVN/V+D+1klgmB9rdEV7ndcmOKTUGkqBEvDG5mvpkEterS1kNA5MJavzOBDDEOS7HE 7XG9bA/utGTRkTw== X-Mailer: b4 0.13-dev-26615 Message-ID: <20240402-linked-list-v1-6-b1c59ba7ae3b@google.com> Subject: [PATCH 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 --- rust/kernel/list.rs | 102 ++++++++++++++++++++++++++++++++++++++++++++++++= ++++ 1 file changed, 102 insertions(+) diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs index 7e9ed802b26b..892705dd0571 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 @@ -405,6 +407,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> Drop for List { @@ -414,3 +427,92 @@ fn drop(&mut self) { } } } + +/// An iterator into a [`List`]. +/// +/// # Invariants +/// +/// The `current` pointer points at a value in a list, or it is null if th= e iterator has reached +/// the end of the list. The `stop` pointer points at the first value in t= he same list, or it is +/// null if the list is empty. +#[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 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.44.0.478.gd926399ef9-goog From nobody Mon Feb 9 13:36:41 2026 Received: from mail-yw1-f201.google.com (mail-yw1-f201.google.com [209.85.128.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 DD82F84A46 for ; Tue, 2 Apr 2024 12:17:39 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.201 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1712060261; cv=none; b=ezCnJGRX4mF8y+x3Y6jC/h0JDS/b1k80CS25dBnr9xhfgaumGCSxq6xkTu/ovOiVlOBktWZnB8fz39qZYeTFRW5CCwZFaR9yxaz9ceiY0i5iKi1727KkFVt3yefEd2x/aOVbh6NJ/swWyyeP/6hOBeEi23cteAi0j/Fznoyl+wU= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1712060261; c=relaxed/simple; bh=tqKfHUsK7hCm2PyXAc01Acvxq8K23vU+ihnAX4wTfEY=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=TQr3i7VcsSoy2guiCbojLRgTZvl1pBnVELG2PGm6IVoe+/4GD76y/G0GQhP1kpf+PbBOTMYB6ExQfLt3LeIh3ytQZowRDAvuUDgvflhzA/LolKaoMBjHhy2vXv0kB/8/Y/+LXNHVrNY7/CajE4E3h/tn3G7HPE9b7/zj3dApgj0= 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=371+VrPc; arc=none smtp.client-ip=209.85.128.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="371+VrPc" Received: by mail-yw1-f201.google.com with SMTP id 00721157ae682-60ff1816749so76049277b3.3 for ; Tue, 02 Apr 2024 05:17:39 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1712060259; x=1712665059; 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=v5M3wjItaw9nmj3Ef5ma10UWkj1Gr7gU+bmHLCZel5M=; b=371+VrPcmk1wNlPimIzv2POHOkz5TAUrgCJYTXlsLfjkQilq4apsibFAfI6mA5KYix Z37APHz6wvjHvJGKHlYzL2DLT4tslTtFgtlrAVxEGdlN/djWahr6dTK7GZAUrYOOArtG DBG70COq/0vLPfpU2YeBlDlES2GdM++bS0n4OnSJaefDpBzybYRdKGtEclCX3AkV6eKe MbWks6k335gNpTFgB4mhJTmKo0r0+OPUU7Nj/wzDz7A9O3s9B0jNjOUMhxufetsp+Pke fR6laq9Vf9Bf4jefc3XQLYtufb3yB8gNjNcc5RKc5xaOnqyVB6bQ7UOknbfG47Ertmui 8cIg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1712060259; x=1712665059; 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=v5M3wjItaw9nmj3Ef5ma10UWkj1Gr7gU+bmHLCZel5M=; b=pAcijICK5HDgqBbAtcfZ+lork04wFnPf9q2GprJvYVyGPNHPiYbsnG2+WGLbCxEyTn r25MlSwhkU31qer0IQmMC2jm+yFAqD1bJGepLS6h+pn9NUqqkGAte51L6xBrVuZ3x3Y8 Q88DoxOup3tVLjqvj3yDs1FoerhkHwOI+mpbH3Y0CkTAHb2TbJw/rSZC9D0+kYJVya/X jFxwI6BjfMi/ziYDfNSQjP+zj/Rpyf68AQWseAacP0JK4KSKDUHXetYSpW7iRekPFDhw c+qhjALv/tyrD5jlE3Rjsq7B0iiy3NwSFYSFI0HHJVgygGjsshTnWsDhS8947RB3j3U3 WiTQ== X-Forwarded-Encrypted: i=1; AJvYcCWKvdKF4QPzAK1z5DD8ZDJgu9yIFkYjYmG8aezDPYD75Y74wb8HCCD0w/Eyy7/25NNzawIOCHEvyUSqrHriulIc47ES/YL11FxvdFxZ X-Gm-Message-State: AOJu0YywBCCIDni6t72BioPZT7lIk+5kEpCO/OsU8uqZ9bt3lkUEPnMb kaNwHIOrw25nNRImCaJTRtqOcl3KtwUfUNG9lpDU5K4AG/TZMjtkGOw7fck6LTmT0JR4/MBCS5u yKya/UHAoPzEm6w== X-Google-Smtp-Source: AGHT+IEfxM1QhUDajOiqFEwCHOge6DqGjO/6OvMxe/W8PULhlDwniReD7xGp7I78PzSDEGFZCTdn7btB+Sga0po= X-Received: from aliceryhl2.c.googlers.com ([fda3:e722:ac3:cc00:68:949d:c0a8:572]) (user=aliceryhl job=sendgmr) by 2002:a05:690c:dc2:b0:614:ad33:3980 with SMTP id db2-20020a05690c0dc200b00614ad333980mr1527148ywb.7.1712060259166; Tue, 02 Apr 2024 05:17:39 -0700 (PDT) Date: Tue, 02 Apr 2024 12:17:04 +0000 In-Reply-To: <20240402-linked-list-v1-0-b1c59ba7ae3b@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240402-linked-list-v1-0-b1c59ba7ae3b@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=4931; i=aliceryhl@google.com; h=from:subject:message-id; bh=tqKfHUsK7hCm2PyXAc01Acvxq8K23vU+ihnAX4wTfEY=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBmC/dLuBvX9MumdW30vLBOIlm75XUIiZApX/FvV tZzfsjLOh+JAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCZgv3SwAKCRAEWL7uWMY5 RuLrD/9f3LnikwyS9dHTIT4bCldMF4qIjjOooOvRqBMOtgrJ5xqxjOq85aEeRx1IN0LrfKbaW9D GIAlVHGGlXEIQsshjrgHRD9dMT7pd5MGqw2hajy+LhZs758v1luXfxyo77PuTqDUNCKu+fDlTpf m2ly4J8GEzBIYCizZkLvQgXOycIJ23Qusi42yMOpekO+msjnhcbSKBqlkMiqGIVCFw9VOylVxp5 Hnp7mYWHCcD25zCKzUVJpjH4aZygNbd3rXIFYILdslby0FjmvTeT7uU6kyT/SPOTqrRVNEzXW2d duQJbeqe87uGv7qsoOSDFWm4J4HphQIjhEpkoiLCs5YGs6vg5B0bXM2x7ZvuIVXp0AbCsiXpkI2 ZgpK+uJcbWprA5x9TS4rzoDoxc63JlEkidZEJbmPs4qVBXv7UGL74v9Y+q6KiPR88Fsu05rXriL MrAeWetM6qp3bhKn4Ur6efe2gmTyUsc6sVbuzDq5n6i9oauhvwox8VX23BfLgfXeC3oBy5fON1r LRKWfLc9zuTUQZZMdXOvw5NOd7fOHS6rpUwxUbqu07STgwuHifJUq+HS19sXKqRP65f2gbo+aDV w2q9Svamn40a4OXp1tqluSOOOvNPtY0qk7icE7Ly3pkdkAVMvsnyt8nG/knPEQhjVnV64gBVaPO AuSScaXfCUKB5TQ== X-Mailer: b4 0.13-dev-26615 Message-ID: <20240402-linked-list-v1-7-b1c59ba7ae3b@google.com> Subject: [PATCH 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 --- rust/kernel/list.rs | 77 +++++++++++++++++++++++++++++++++++++++++++++++++= ++++ 1 file changed, 77 insertions(+) diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs index 892705dd0571..47e52818c7bd 100644 --- a/rust/kernel/list.rs +++ b/rust/kernel/list.rs @@ -408,6 +408,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 @@ -476,6 +490,69 @@ 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 an immutable borrow on the= list, so any such + // mutable access requires first releasing the immutable borrow = on the cursor. + // * Values in a list never have a `UniqueArc` reference. + 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 { + 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 { + 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.44.0.478.gd926399ef9-goog From nobody Mon Feb 9 13:36:41 2026 Received: from mail-yb1-f202.google.com (mail-yb1-f202.google.com [209.85.219.202]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 9E9A984FC5 for ; Tue, 2 Apr 2024 12:17:42 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.219.202 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1712060264; cv=none; b=R8DjyLSm6sbT2ZDg/5OPsKourTLyM81ciJiUylfjXfk65/VHSkroEQyTZdvh8fTK4FKIk1cKdgJQDqg/I7QgKlNUdO84yxC00WYaasrwCN5RrRsm8SdxNSSSXai+ClqHKaNmJh+c+xEI65VKHldqg3dV1sWJCHjyMyDWumDiuSs= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1712060264; c=relaxed/simple; bh=J0Jh3hYB6HWSSdkv+IspL6k5u56qOC9WzYHDNcC68vs=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=LJFWg6ZCWG79bS6fd10yzhKd/Q1HdZCxJA/VXyxjrM4feyETfsicd6BHbeH5CTx51Ejj6YUUPWPm8slCPsMlGxWKx2kmuV/r1SRSUvwPIZPq+M++KUfpCry/6YSeAN1TENYFVaU+8HVKwi5RQGlVNbpYzYCPU3+26esUsfTL08M= 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=uaDFyCPa; arc=none smtp.client-ip=209.85.219.202 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=flex--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="uaDFyCPa" Received: by mail-yb1-f202.google.com with SMTP id 3f1490d57ef6-ddaf165a8d9so8104074276.1 for ; Tue, 02 Apr 2024 05:17:42 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1712060262; x=1712665062; 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=7Tyr94/cMd+89WcGierBr9QiSC3Rmvpo4zWfjcOluIM=; b=uaDFyCPapW25sUfJwYT/W9NYNw9PPwOFbjTKDEjy0dbnZse24dI9mdW+pc48I4o2vT Q5Mz+Q3Dc0HzArwB48/BhpRY7esTvGoy6rH93BcN/ysTrOEd5j7c0dzEBAyjKFk/G2f7 kVxxVy6jgQ16iOwiWuSvFBDoYkTPMvpxuyS36UiHQ5eoex0mwE1KrA9sr6cAB4RdiS3A 5CDOX/K0LGhWruo0s9xONj4BCnomufzxZwNINPDzH5jlcL8A38E5B7nNAT7EJ0KcdNbL to1mUoIuywl7h+C/gs1HAtgERWaaprA3FLYKzqCTktXhpQWSbnlyh4wvAgtIF571Ol5X V9uA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1712060262; x=1712665062; 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=7Tyr94/cMd+89WcGierBr9QiSC3Rmvpo4zWfjcOluIM=; b=cpHAWriUC/lS6MP6VoKSn5G6Gv+NDXu7bWQ4g4fyZ//4OpLZWSozubbKOZ1zV5G3yZ zf4rOdfmVU2sxMirMJRwflSjjTVPuDHdxFy0QeG/MfblL+yb+zBeWiqBHQmTHBg4Cs+4 7UbLiuVegbIWkLpd+a1wKcnCNfhG4FPhiz4OQrovxhWX1tMh97TuKM86H7QEdJEB3duC DSloqIwfP+VezDpuPuY4s64jlqo3EgW2eKEnwbUiuJN/UPG39MVTEF9XFPKVQr88rlTH /2DBN37a9y+T2IhucFfwItRCoShltplqNdrhe/lgCu6K61DJlw2WN2cJZo6YgDwY7sTv fIgw== X-Forwarded-Encrypted: i=1; AJvYcCWPzQr1kEQmTjfW9cKVTnWJbrWdrbeaDJ2TM4jasblRAs6D3C8BC/+9loWM3YeEhlS0kZ2cLtRhmZ2WwbFWMbTkpnfd35qXRD4b41Sz X-Gm-Message-State: AOJu0Yy6eBUzteYBKfQHkoHE6Dm0J0h9wc1sg7n+V6q0GiT5VX4398Vg X4HzXWJ9Ys5pkduZb3IO4g+jFRw1qo/jpiKBbjoW+OqZfEyWMlxBt0/7cm4v5HPTBRXCXRQ1Zdq jXcxeJkqiO9hZyg== X-Google-Smtp-Source: AGHT+IFTjzoYfa2x4oO3N22MhhWPdj/upe9zDI7L9XGf4fVbRKO6R5U6EdgVaucUFmhRDxL4+GKl20rl8ONfse4= X-Received: from aliceryhl2.c.googlers.com ([fda3:e722:ac3:cc00:68:949d:c0a8:572]) (user=aliceryhl job=sendgmr) by 2002:a05:6902:e0f:b0:dc6:44d4:bee0 with SMTP id df15-20020a0569020e0f00b00dc644d4bee0mr991972ybb.7.1712060261782; Tue, 02 Apr 2024 05:17:41 -0700 (PDT) Date: Tue, 02 Apr 2024 12:17:05 +0000 In-Reply-To: <20240402-linked-list-v1-0-b1c59ba7ae3b@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240402-linked-list-v1-0-b1c59ba7ae3b@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=7586; i=aliceryhl@google.com; h=from:subject:message-id; bh=J0Jh3hYB6HWSSdkv+IspL6k5u56qOC9WzYHDNcC68vs=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBmC/dMPX59PXbjId2FA6AFETGnwlkw0cpkapDjK 7yxuRg1V7eJAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCZgv3TAAKCRAEWL7uWMY5 RqC6D/4sLGpfyiHscoXLi7CCpfZVNzQ+XWMmRNgwBreVPgN45xNW8B3nwmF2caStb/6WORMtBnI h9uwIlCZmyHFQSldUINrosPNVunUypZUXXFwNn6iD1jQ1LSQzfu/sf6k7ILz8XgsOJBmA2Y5vAV miaTdlyD6egr/oVXjVpbyVhtTOJ548D6ojK1VQF63lIAqNx6J+r+HjiVPeWIMDiQFm5Vw3ydIol Z54v70887rmChqHllNlAjVQN4aasrf4W0PL5U4jPppK0iDyin6q2NQ838/3t9TGxE/xSuI9Z6ZW +0XjHMJjA4XdltV0YpFqD2e0DONXSjh100rOGs/czlwZhE+3ED/BUB5nUoXJsiSgMkeHCRNsCMO vB13lxBVQZWtTaIRqNY6fLgDDIxu/lTD6APZercjAc85IapVp40i6QgmK4fI5LNQSMflSkoNOzU PvWtiyVIYhzxgiB7kLLyWcTIvGxrQgfs5dh3deEDGU2WuQVbVO/iIKu2+7HF0kdaoXvl7FRNoAx U0b0VJPzY+JUq6cyUKUZe+iJ8euuAPnnM3/pCtmsOQeGe6XFDNpEkYqC3IHGBahfCBYgYFdiTuo nfIYJu/rhtHACDzqXDSbIOyXh4xeypyqFcMs4u0UIFOshcfI0HJDhnBDNf/HxRJr9QGJHKZlXN0 zlVnkXh5oSNVNeg== X-Mailer: b4 0.13-dev-26615 Message-ID: <20240402-linked-list-v1-8-b1c59ba7ae3b@google.com> Subject: [PATCH 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 | 41 ++++++++++++++++- rust/kernel/list/impl_list_item_mod.rs | 83 ++++++++++++++++++++++++++++++= ++++ 2 files changed, 123 insertions(+), 1 deletion(-) diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs index 47e52818c7bd..68d03b100863 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,41 @@ 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>, +} + +unsafe impl Send for ListLinksSelfPtr {} +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 9e2f6d6d4786..6884d8a3e710 100644 --- a/rust/kernel/list/impl_list_item_mod.rs +++ b/rust/kernel/list/impl_list_item_mod.rs @@ -61,6 +61,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`]. @@ -94,5 +137,45 @@ unsafe fn post_remove(me: *mut ListLinks<$num>) -> *con= st Self { } } }; + + ( + impl$({$($generics:tt)*})? ListItem<$num:tt> for $t:ty { + using ListLinksSelfPtr; + } $($rest:tt)* + ) =3D> { + unsafe impl$(<$($generics)*>)? ListItem<$num> for $t { + unsafe fn prepare_to_insert(me: *const Self) -> *mut ListLinks= <$num> { + let links_field =3D unsafe { Self::view_links(me) }; + + let spoff =3D ListLinksSelfPtr::::LIST_LINKS_S= ELF_PTR_OFFSET; + 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); + + unsafe { ::core::ptr::write(cell_inner, me) }; + links_field + } + + unsafe fn view_links(me: *const Self) -> *mut ListLinks<$num> { + unsafe { + >::raw_get_list_links(me.ca= st_mut()) + } + } + + unsafe fn view_value(links_field: *mut ListLinks<$num>) -> *co= nst Self { + let spoff =3D ListLinksSelfPtr::::LIST_LINKS_S= ELF_PTR_OFFSET; + 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); + unsafe { + ::core::ptr::read(cell_inner) + } + } + + unsafe fn post_remove(me: *mut ListLinks<$num>) -> *const Self= { + unsafe { Self::view_value(me) } + } + } + }; } pub use impl_list_item; --=20 2.44.0.478.gd926399ef9-goog From nobody Mon Feb 9 13:36:41 2026 Received: from mail-lj1-f201.google.com (mail-lj1-f201.google.com [209.85.208.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 1126B85639 for ; Tue, 2 Apr 2024 12:17:45 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.208.201 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1712060267; cv=none; b=qQLiqohta6wmL4K0tejDVGPoAnQdkE3ox+jD74Dki1soqmpR3zjBJbjYx7wCaDkftKTB1zzo9/aERt7hx+zuYnGvwThCaMI7nxhTtMnimX7+gxMd3VTHL+BuxSHvmWsuQj98di/nyfUO+FRFGgg1hoOja/A4bjHjnBswTm59raI= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1712060267; c=relaxed/simple; bh=SGw/IWmpTfH/F2q/Ud6VR5TfFDIRo7fTaxFXe3yUsnk=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=ebfD6O9ayLJLZb+qvyJRaFWqB/twmRA8p6TQ6SIzuNLI0j9zzqOvQgytxVR5jMsdI3lNdO9Q7kdo0fsOz/nBPVwmxPcYeZpQmCb/bjye6E4UQ5cR2ypoEpORimMfAlG4c9glfWyEze1VqwtJ62R/21McHJwJj8/pBfR5IHNEu1o= 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=LAPHypQm; arc=none smtp.client-ip=209.85.208.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="LAPHypQm" Received: by mail-lj1-f201.google.com with SMTP id 38308e7fff4ca-2d827143440so8048361fa.0 for ; Tue, 02 Apr 2024 05:17:45 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1712060264; x=1712665064; 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=Vgz9mY70v5CNK64cYxyt3hg7fzBLiQ2+bMaSc0psi2g=; b=LAPHypQmPxiB/Q0VgZq7IWxUnq3PtIAxQje8F9P980JBAHZh8sh4TO9vQUmsV8sj1v HQA/ff+KbjFVDTaAF2cgZbnzfbOBtRsBVkQb3ZiQPLQNYECRjb8wa+GmRdMncPn6pJyU OYwlPdkbQiecD0STMnaJXZnNLzPEo5hbiUCrhrW+fSS80SLfwTjs+WPCOBaSvv5y0QJW wwsYmVgzfPjehCTVK2/wmEVfrflorhJt/exLjIOH5MIxAxIOVNGA9tKhqwdcy1Jtacf6 yWk7RZphnOMktumZhLFq7PGFWVyhPmVl5TjPyFuISbqxK1jZF0MK7ys0GJLxrU0puc/O ooWg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1712060264; x=1712665064; 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=Vgz9mY70v5CNK64cYxyt3hg7fzBLiQ2+bMaSc0psi2g=; b=Ne3+GB9hy3lkNDSocGCAf2+1opidTFnbSbnGPqUBEV+Tpy08yPq/dahdhZcLa0HsUo V9BUXkUFvLFbaEMETNEFfqVa3IS+1AhS1+WFkGObXnYnwqW2ybwLyzw2oVlqSrAvQdho 7BTlxzwEGRaETcbpETMrR7ymb8UJkWXYziHSCK7AbpfCims3FhrnRZVD5pURBoxc/8yq mpaxXx5Byf50xJYrcMT/broA3A0M9faF+yBSL0AzyZbcKnxHF65IxDyZnD+FJJLKTVwM LXpDQ9DvYJXdnY26VPf3mIov94tLZBZFDoNtB7fy4fsN5fiocHFXB1e4CHMcG/Z+Cmk9 SisQ== X-Forwarded-Encrypted: i=1; AJvYcCXIExTiADyd1ZeXNjGkSvf5DcUHd9zwgRrqsyarBtPhKKckRChWeAVlOICz69dA0AAR14w828zBemsbicXU0St4kGFZsVsmka59v/+y X-Gm-Message-State: AOJu0YzC7u/cqK+Pg+47uQofnnRAG4dsMq/KWRPDKFBN5VQ5Yy4HC4Es tFQAGbUtVYx9NzZHzF4VWKxGugU6XhqKhkk9Hxa42PwMNK+c1qDnJMrAFdWgXkw2FWmH+UWVe6t dlac3Co14z8STCA== X-Google-Smtp-Source: AGHT+IHzIcMUK/ZnVKq3qkpniEnzh8eCGMqdXergN7OK1gAzwOA0dYo8VsQtWLJ7tC7T7IZcGuzKV0g2HBkQDuU= X-Received: from aliceryhl2.c.googlers.com ([fda3:e722:ac3:cc00:68:949d:c0a8:572]) (user=aliceryhl job=sendgmr) by 2002:a2e:380a:0:b0:2d4:6d84:e5a1 with SMTP id f10-20020a2e380a000000b002d46d84e5a1mr11044lja.6.1712060264327; Tue, 02 Apr 2024 05:17:44 -0700 (PDT) Date: Tue, 02 Apr 2024 12:17:06 +0000 In-Reply-To: <20240402-linked-list-v1-0-b1c59ba7ae3b@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240402-linked-list-v1-0-b1c59ba7ae3b@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=5215; i=aliceryhl@google.com; h=from:subject:message-id; bh=SGw/IWmpTfH/F2q/Ud6VR5TfFDIRo7fTaxFXe3yUsnk=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBmC/dMaviC2qcjVgb/qXVtUFOZ3+y+j8AdAra2j fs1cpydcVGJAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCZgv3TAAKCRAEWL7uWMY5 RgZvD/47HsxN1WCEK09/gmnzGcvdEwCuuF6bNSIKzOhsWL/GHKSimQ0dvAUolIsJDgzoIKzC8o5 q1MgUQDzH+SFVYM5lR9c3bccY10dH/4ZExtiM6bmoB634KrEPanSUu5raYyQCrrUp9y/fqKC7Xq HF1EU+O9hOZJ5EB9ofcil1X0ePqJzoIE/SwhY8+2eFI1Tgb5+w5Un60Y2v2j3xJ49mBu1HixNI0 RvCkdi1lSEwrKugTA2HBoNK2LK9CRqjSfjrs7BDnq9WQ3HT4ahi0n68iws6wZrJx/8VaWlrDU36 haiWrBzYFFjpnzbOaiQ5wsT/PFECUPAitQyX0CJjjba7d12vg74q7Rs+97pB3/9yx2eEQAm4/a+ PEqYP5Ujg2USZdlKP8xuL/q+53bA9XTRKBqmS+i273Jv8IBRrhJE9Mki+qG4l4xT63hqEydNB+P lV+BSg8EE/wwBGEan2zjkR+Trxhry3ssKWyz6s5pMEKVgql9Yl39lC70HndInMWbFasXq4Mslbi FFIMmynMvzEmjZMK2laB2EAMVKgmNL3BNw00W5clXvLKcxBAL2Gry8Kj/pjZbDaPcur45PuQfzR 8W7Q5oZ01XPAnkgFwVxgQvDfq1OEE567HecVKB4Rqdw0/i3HxFiMr3Ze5WAbikwfJUn1QCBZ1RP EuMxQL79JKjOF6w== X-Mailer: b4 0.13-dev-26615 Message-ID: <20240402-linked-list-v1-9-b1c59ba7ae3b@google.com> Subject: [PATCH 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 --- rust/kernel/list.rs | 3 ++ rust/kernel/list/arc_field.rs | 94 +++++++++++++++++++++++++++++++++++++++= ++++ 2 files changed, 97 insertions(+) diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs index 68d03b100863..a59b35b67e9b 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..936fd97bc5ac --- /dev/null +++ b/rust/kernel/list/arc_field.rs @@ -0,0 +1,94 @@ +// 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`. +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. +#[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.44.0.478.gd926399ef9-goog