From nobody Fri Dec 19 19:07:43 2025 Received: from mail-wr1-f74.google.com (mail-wr1-f74.google.com [209.85.221.74]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id BD4871D54E9 for ; Tue, 6 Aug 2024 13:59:31 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.221.74 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1722952773; cv=none; b=SrGW/MJ5W09Hn4qLAuMyRoNXDXdSMES09JAZpCI68GjXT6EQgiYhsH4sIVp3zn87sUxqTVPLfBJHgsapOGf/jS5gf1m/WVFIYZtDtBirUoALrpaGQjpuWSjZNaJzAQmBecRNSlq47y/nIhUKyKbLK73NS/h5osvweHhYcB68XKc= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1722952773; c=relaxed/simple; bh=jnKF/oyQeugfAQVgW4W1AV60+aM1DDIejGLFKTFwAuQ=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=Hp+W0oiw0y3uNwPZM4RwykhpyXAHqWI33J22V1BIJOQxpZ1U4s0LUHmNOxbrXgCaWpFOEiCaq7HKb43xlr7X58izbHbPFugMwpvBu1lJckDnA4yPheFAwG9nkpdq9SYR4GME83XBOafEgJE3qjglDxvFlEdrukRo3ToTOVC0WGs= 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=10MjEgrc; arc=none smtp.client-ip=209.85.221.74 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=flex--aliceryhl.bounces.google.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="10MjEgrc" Received: by mail-wr1-f74.google.com with SMTP id ffacd0b85a97d-367990b4beeso461801f8f.2 for ; Tue, 06 Aug 2024 06:59:31 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1722952770; x=1723557570; 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=7zBzNoBly2krqneRSwSfI4JKOiFR4iaU7/3GH2+Nyg0=; b=10MjEgrcECydPaSJOTViZTV+Zv9yMCcS81nuN87bzGyBOQg4JT7WKJYR+cQqOSx+bH /UN4P1nA4FcQXRwJ4/6KlU8fd3yXrhORMmvo5GlLQ4SMsYYU8rJHKvstWnWi/Ib/hLRN d1Tl0gFO0djNherVzW4e/Jl58yb03yKSZPZr2k2XvUy7D+XPnkrcFbH2SUhRJ+z+AynY Gb/ckWtjTv5LsYHjJea/S/awzaDUpYHXXLWnmq41UqZg9xfllzl99Vuk9182u7D5DBz0 rQFF3SQqnTyVbJTxtElusBK/c+64C3Sqeu6OvnfJ/4O/YfzPUBEnCl8YMcC9tYsmjoeo qi2A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1722952770; x=1723557570; 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=7zBzNoBly2krqneRSwSfI4JKOiFR4iaU7/3GH2+Nyg0=; b=q0FZmT21/4LLZgB8kZ5OKNih7x/AnepidYWcgw2pyqja7J/qfG4hdBMvo1r6rtrsha l2zWbwUOI1w0HS2LzMF3H117OgM4wlJgmJVb7+BnLsGCMdf1Bv+FHihX6u9IqU7AEX91 J3+vk9xB0fbQ8i8xyvMXfeGj7jntgXnZnWG+yJieXpSsoQ/246oey7ttaTYEUwYAuaY9 vpfkMqYXnJqdZrla/5lDAomwhnN+QYMHTUHqqXNWhZ7aJPS8d4ad2Kjrnhurhij24rhJ qcXQ/BSGBuLGgbvuX21W8JFOXH3fJpZC0/0I3CN5jufj9DPtc7jVK6pXSHO7mUgHKGHo Gp6A== X-Forwarded-Encrypted: i=1; AJvYcCX6KbXRQZ8jo+oHFNg2F3zv8nghCy0DWaBt+SjenjLldauvJl+iyJOKM+j7YHW04k7ArWGosjwizPhX95IjRh3gtLRYR7OuxHrjE+Dt X-Gm-Message-State: AOJu0Yw6MDcCxT7EVIDI4jGVGWUvNpuHK6HtFT6V5a7g+65WFiUniMFZ DsSw2BXQMQOPtU+xMv3tdwsJpUCByzv7LydSvS/R+PpoASLnSCGYDHW7Rtme8XB69CV4TztZ5R/ c2ULu8GqB71hbtg== X-Google-Smtp-Source: AGHT+IHfyggQAHCMo1H+VuH8fYUdZIKW7TfKe3NVrHO6BjZxNT1rGo7TVK6+tCqJfI/7xJPbJKrteuHkqeyr4V8= X-Received: from aliceryhl.c.googlers.com ([fda3:e722:ac3:cc00:28:9cb1:c0a8:35bd]) (user=aliceryhl job=sendgmr) by 2002:a5d:452f:0:b0:36b:bb7b:923a with SMTP id ffacd0b85a97d-36bbc1882femr21659f8f.12.1722952770169; Tue, 06 Aug 2024 06:59:30 -0700 (PDT) Date: Tue, 06 Aug 2024 13:58:53 +0000 In-Reply-To: <20240806-linked-list-v4-0-23efc510ec92@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240806-linked-list-v4-0-23efc510ec92@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=4065; i=aliceryhl@google.com; h=from:subject:message-id; bh=qZ9J/+0vw2xQYmgGbraO8iTE7yockKbb9UgUTf5VFEA=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBmsiw3YHCMsmdQSF7z4EpNqK59qiwpSqxeizLeX fV5hcUDSS2JAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCZrIsNwAKCRAEWL7uWMY5 RhG+EAC7hBj+whdtRkvtrucxncYoTz33F9resFfUqJUsEQuOurAvoRVfgeDkNJYbBPbTAMIkMML hdkMJ5Sh8ZLlTUEmHErIsUYWKsnZF6qHRjlNNcYNZMcqjW7vZ5vYM1vYkAnz/Ez5O7I88eBOQQW JeSLYLa1258RDhqsdVGYSP7tzta1Mljj/e0Twr/wLXYkkFulmqePcP9kg6f6Kxzc1/w8GFzrvlB tAkbW9dDl/TvkC1AU9DNEi22iqqIvAQaFWXMMbQ93/i80oGAgBDmG41XR4gzlls6IAOvteQFnDL LeKhjvyZLP+SjtG2WhNWDUjySiV3gsIBfQ9Iqpf6s1oo/vmVfys79mmz29v4xIG5xJ6kzVhkY1t kAnro5FgZIDzmNdUGc3lL4CwBqfGhc6e5R+x+BWGcIyEVnfppIKqWpRkaVHRk+rs2m2JGR+MLtH Y7iOZDZCnqttfLnpWJdWgmypZSpecwan9xlUuEQHiFZ9Me16BfGZN5IVkMJjByQac+Aq9TREVNz iZ89p5WUQ7TdZH+D9y0VIS+rA3Kibz9T3nRRB8HDYgSzAuaiJEEdXwuRfaz16dPPgknm+Jw1pMS 8uof4s7J7aM9GwxiUVIG5Y4Uhyh6+lcqJseanrWSUUeEE/Tg9mLkvDg2nHDfSYPt/E5QnoCjMFj 7ilSFS672vZZ80A== X-Mailer: b4 0.13.0 Message-ID: <20240806-linked-list-v4-1-23efc510ec92@google.com> Subject: [PATCH v4 01/10] rust: init: add `assert_pinned` macro From: Alice Ryhl To: Miguel Ojeda , Andrew Morton Cc: Alex Gaynor , Wedson Almeida Filho , Boqun Feng , Gary Guo , "=?utf-8?q?Bj=C3=B6rn_Roy_Baron?=" , Benno Lossin , Andreas Hindborg , Marco Elver , Coly Li , Paolo Abeni , Pierre Gondois , Ingo Molnar , Jakub Kicinski , Wei Yang , Matthew Wilcox , linux-kernel@vger.kernel.org, rust-for-linux@vger.kernel.org, Alice Ryhl , Kees Cook Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable From: Benno Lossin Add a macro to statically check if a field of a struct is marked with `#[pin]` ie that it is structurally pinned. This can be used when `unsafe` code needs to rely on fields being structurally pinned. The macro has a special "inline" mode for the case where the type depends on generic parameters from the surrounding scope. Signed-off-by: Benno Lossin Co-developed-by: Alice Ryhl Signed-off-by: Alice Ryhl --- rust/kernel/init.rs | 67 ++++++++++++++++++++++++++++++++++++++= ++++ rust/kernel/init/__internal.rs | 29 ++++++++++++++++++ 2 files changed, 96 insertions(+) diff --git a/rust/kernel/init.rs b/rust/kernel/init.rs index 495c09ebe3a3..1263f486abc4 100644 --- a/rust/kernel/init.rs +++ b/rust/kernel/init.rs @@ -742,6 +742,73 @@ macro_rules! try_init { }; } =20 +/// Asserts that a field on a struct using `#[pin_data]` is marked with `#= [pin]` ie. that it is +/// structurally pinned. +/// +/// # Example +/// +/// This will succeed: +/// ``` +/// use kernel::assert_pinned; +/// #[pin_data] +/// struct MyStruct { +/// #[pin] +/// some_field: u64, +/// } +/// +/// assert_pinned!(MyStruct, some_field, u64); +/// ``` +/// +/// This will fail: +/// ```compile_fail +/// use kernel::assert_pinned; +/// #[pin_data] +/// struct MyStruct { +/// some_field: u64, +/// } +/// +/// assert_pinned!(MyStruct, some_field, u64); +/// ``` +/// +/// Some uses of the macro may trigger the `can't use generic parameters f= rom outer item` error. To +/// work around this, you may pass the `inline` parameter to the macro. Th= e `inline` parameter can +/// only be used when the macro is invoked from a function body. +/// ``` +/// use kernel::assert_pinned; +/// #[pin_data] +/// struct Foo { +/// #[pin] +/// elem: T, +/// } +/// +/// impl Foo { +/// pub fn project(self: Pin<&mut Self>) -> Pin<&mut T> { +/// assert_pinned!(Foo, elem, T, inline); +/// +/// // SAFETY: The field is structurally pinned. +/// unsafe { self.map_unchecked_mut(|me| &mut me.elem) } +/// } +/// } +/// ``` +#[macro_export] +macro_rules! assert_pinned { + ($ty:ty, $field:ident, $field_ty:ty, inline) =3D> { + let _ =3D move |ptr: *mut $field_ty| { + // SAFETY: This code is unreachable. + let data =3D unsafe { <$ty as $crate::init::__internal::HasPin= Data>::__pin_data() }; + let init =3D $crate::init::__internal::AlwaysFail::<$field_ty>= ::new(); + // SAFETY: This code is unreachable. + unsafe { data.$field(ptr, init) }.ok(); + }; + }; + + ($ty:ty, $field:ident, $field_ty:ty) =3D> { + const _: () =3D { + $crate::assert_pinned!($ty, $field, $field_ty, inline); + }; + }; +} + /// A pin-initializer for the type `T`. /// /// To use this initializer, you will need a suitable memory location that= can hold a `T`. This can diff --git a/rust/kernel/init/__internal.rs b/rust/kernel/init/__internal.rs index db3372619ecd..13cefd37512f 100644 --- a/rust/kernel/init/__internal.rs +++ b/rust/kernel/init/__internal.rs @@ -228,3 +228,32 @@ pub unsafe fn new() -> Self { Self(()) } } + +/// Initializer that always fails. +/// +/// Used by [`assert_pinned!`]. +/// +/// [`assert_pinned!`]: crate::assert_pinned +pub struct AlwaysFail { + _t: PhantomData, +} + +impl AlwaysFail { + /// Creates a new initializer that always fails. + pub fn new() -> Self { + Self { _t: PhantomData } + } +} + +impl Default for AlwaysFail { + fn default() -> Self { + Self::new() + } +} + +// SAFETY: `__pinned_init` always fails, which is always okay. +unsafe impl PinInit for AlwaysFail { + unsafe fn __pinned_init(self, _slot: *mut T) -> Result<(), ()> { + Err(()) + } +} --=20 2.46.0.rc2.264.g509ed76dc8-goog From nobody Fri Dec 19 19:07:43 2025 Received: from mail-wm1-f74.google.com (mail-wm1-f74.google.com [209.85.128.74]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 1BDFF1E7A5F for ; Tue, 6 Aug 2024 13:59:33 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.74 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1722952777; cv=none; b=e2H2D3SFcmihVyIuVZXHrgE/2NyBjgrKN1g5RXRk78sAMThMSqCLqCuqmRtykmW/FpY5I8QX6yzVuG8IQT/kZ5sN7yTYrUgvRrYo7xxJaBr797nY8UzD/Jq13kXUpX4yLaNZczju3XnCdEH7F/qs2m/S6iFr1RY4RWZhSRGnXbg= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1722952777; c=relaxed/simple; bh=JVosXDN3SpVRQ/+0zppKL/7SkJYUfcf7jvmkD80O084=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=dTnU5LNP9gSsiliFc41JGZge9IoVxe7GpkqRLdIKw6j9gBOVQ+d/jhA9U4Wbfi5bLUbjthhp0NBkutcg0Mbowkt/8lUEIYvULLvzR+IM5DFLWKPiCRqjd0MHlakbXJs2dJ1tYymcOTRfo0Rkm83brJbdQQCGD0yxwPdmPFC32Jk= 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=oGrtRExL; arc=none smtp.client-ip=209.85.128.74 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=flex--aliceryhl.bounces.google.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="oGrtRExL" Received: by mail-wm1-f74.google.com with SMTP id 5b1f17b1804b1-4280cf2be19so5706855e9.3 for ; Tue, 06 Aug 2024 06:59:33 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1722952772; x=1723557572; 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=17AMWTa6hYVVRqhZAZZCkooxhjEaCq6cxN+9B6hH6F4=; b=oGrtRExLuBQ3xWUcWrIXwbBf11+QSDmTdduLFyKlNkzeDnfj2OXJVFcrQlPo60+2n5 g2IvrT7t3ptsCLlJf12x76ywU05ueqUNa1xNJz5gYfgIvgzcDlQDmKxIq7A2RhnlRMgP YohSZfJ7WR6gyJk9ZrFjIxqIitUM+5EGvaaIgYg+SSCzUx7l9fFC/P76CHs22YPjUUqL ccajHsFHuDSwufnwNobKWhxkzim+UquXbCTSF23qyQ02Z3KP98F4LIjMCWvXzrmMRPdx GS3ainXX5rJyYCl4o5h7P/uznv2qU/Fb4sFGxS+p968hsM37gcPCdtB2sLwr+7vYJMhx HRRA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1722952772; x=1723557572; 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=17AMWTa6hYVVRqhZAZZCkooxhjEaCq6cxN+9B6hH6F4=; b=Kuo1Desr6kMypKJuWNf/sxHx6fAKJCF1oNmqST+s5uKRuJnN7+JgX3mhyOePeiU3ma jbIdA1uUrvHjw/I1ogsNnZRssXZ62fc3eOS3ALJsJh5JqRN0JhDe8NqTQuBWzET6xPnk 60f2sHnIMjqtOEpcJ3+yLXQzw6lrCo8+cMBXFgKtFYudMm8qutSJTt6OiDSGSI+WztRM Vk5LPFhzc2Nn+kCyqTkZTUhmfx9qt2bbYXf9syGUqoZ2Bpb6qkXWswxBPQviRZktF9q8 2mGufSAuhXwwW47WUZAo689OxS81EsBmlk98YuWGT8Q+KJ9fRQtCVUJvLLI3RAMYL1gx jw+A== X-Forwarded-Encrypted: i=1; AJvYcCUT8afj8PbD3Lr/b0HKERfGej/nTT5T6lS0OLV204dxOyK32NeuRZ4neBGT+EEphGlWbIZVNlzFaW8NFuLgNA8PGIWGgHE+Jt0pC8qB X-Gm-Message-State: AOJu0Yz8EN/4lohKuXneMPROaYF0aOixIeeIqFRlJgGCqzC9mHczhNh9 bwrmTlTVcxDtXAytdRcLU4zZg4kho9nFCz1i6AuuYdqSWhTyayx8NY5B81/MbGax3WsCDY9EVB4 PLvZ8sYSnEp5waA== X-Google-Smtp-Source: AGHT+IFSDvpm7UR3VV05mU/mykSm2w2atzvPPZhYHV1M2i99LttQ9dstvbKPBbKYh9BFPKxejkz0QSJNh/w272k= X-Received: from aliceryhl.c.googlers.com ([fda3:e722:ac3:cc00:28:9cb1:c0a8:35bd]) (user=aliceryhl job=sendgmr) by 2002:a05:600c:c13:b0:425:3084:ca1 with SMTP id 5b1f17b1804b1-428e6bae4c5mr804395e9.5.1722952772446; Tue, 06 Aug 2024 06:59:32 -0700 (PDT) Date: Tue, 06 Aug 2024 13:58:54 +0000 In-Reply-To: <20240806-linked-list-v4-0-23efc510ec92@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240806-linked-list-v4-0-23efc510ec92@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=17977; i=aliceryhl@google.com; h=from:subject:message-id; bh=JVosXDN3SpVRQ/+0zppKL/7SkJYUfcf7jvmkD80O084=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBmsiw3FT8pTJY+HfkVy6EtRK10fhDZGys5y92rJ AoCz1QS7sOJAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCZrIsNwAKCRAEWL7uWMY5 RqKPD/9FidqdU0eCJ6ks6AnKj8DcIsDW9LixOjKt0TACpSTDJSTCuiFkjktVbFPZDb+pSHEOzTI 8XyWe/WEah2zevTudvvUWXpUFiORQnjBSIDJd6wE6rYinaoEHpIgviGITVkqrpF1osfRLF5FC0E gixot7ErHBYyk7R2uYL63YBLUVjwMqblyb7bOQ2rYv9D7UYCyxb0B8OuX+aBYruYBf2qY1GC3t+ kffskAxnlar0qsEJ4vOMAVlOOru6rO80YsZ2Q9G8hHPuiX27Qglx0XstA0eD135fM88SDUsi1GB b5PgvWsoJ5LwEkK3WqCjR26T7SZyM+ZLfAybjhToy3IznsjM87U0pTIR6Cjf8YxrX+iar3IY3pF k8bSjqzDHTBItT+jC+UwJKkqjAFhdDYPyrfi2lbKFock4ky0l2i1a6Aq1vit7vFW5HLC9aqUkt1 ur4RrmHjK2y4RcgmXzpWcGlqMqV4R1FPk3svcxRkOW0eOrnXt9FZJVNFvAFUaIfbaSnGoekPPMx Oo0tUXalNMb3qat29DqnR+5LNKdySmASoYRobwYpcMBp8emY3FfcRLaHDloM2BxIv2fwtFtaqWy EzNKXl8m3SI3s0k9fXD2ajZFSnYrAhK9nbW4Jdp2IowWgoAfs5GcpSQglxp7yW0GjeK/IwSIvdY SnUVozQn7AuyhnQ== X-Mailer: b4 0.13.0 Message-ID: <20240806-linked-list-v4-2-23efc510ec92@google.com> Subject: [PATCH v4 02/10] 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 , Coly Li , Paolo Abeni , Pierre Gondois , Ingo Molnar , Jakub Kicinski , Wei Yang , Matthew Wilcox , linux-kernel@vger.kernel.org, rust-for-linux@vger.kernel.org, Alice Ryhl , Kees Cook Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable 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. Only the latter situation can lead to memory safety issues. 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. Reviewed-by: Benno Lossin Signed-off-by: Alice Ryhl --- rust/kernel/lib.rs | 1 + rust/kernel/list.rs | 8 ++ rust/kernel/list/arc.rs | 352 ++++++++++++++++++++++++++++++++++++++++++++= ++++ 3 files changed, 361 insertions(+) diff --git a/rust/kernel/lib.rs b/rust/kernel/lib.rs index 274bdc1b0a82..9baea9e9ee1a 100644 --- a/rust/kernel/lib.rs +++ b/rust/kernel/lib.rs @@ -38,6 +38,7 @@ pub mod ioctl; #[cfg(CONFIG_KUNIT)] pub mod kunit; +pub mod list; #[cfg(CONFIG_NET)] pub mod net; pub mod page; 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..966076da4a75 --- /dev/null +++ b/rust/kernel/list/arc.rs @@ -0,0 +1,352 @@ +// SPDX-License-Identifier: GPL-2.0 + +// Copyright (C) 2024 Google LLC. + +//! A wrapper around `Arc` for linked lists. + +use crate::alloc::{AllocError, Flags}; +use crate::prelude::*; +use crate::sync::{Arc, ArcBorrow, UniqueArc}; +use core::marker::Unsize; +use core::ops::Deref; +use core::pin::Pin; + +/// Declares that this type has some way to ensure that there is exactly o= ne `ListArc` instance for +/// this id. +/// +/// Types that implement this trait should include some kind of logic for = keeping track of whether +/// a [`ListArc`] exists or not. We refer to this logic as "the tracking i= nside `T`". +/// +/// We allow the case where the tracking inside `T` thinks that a [`ListAr= c`] exists, but actually, +/// there isn't a [`ListArc`]. However, we do not allow the opposite situa= tion 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, wher= eas the latter can result +/// in the creation of two [`ListArc`] references. Only the latter situati= on can lead to memory +/// safety issues. +/// +/// A consequence of the above is that you may implement the tracking insi= de `T` by not actually +/// keeping track of anything. To do this, you always claim that a [`ListA= rc`] exists, even if +/// there isn't one. This implementation is allowed by the above rule, but= it means that +/// [`ListArc`] references can only be created if you have ownership of *a= ll* references to the +/// refcounted object, as you otherwise have no way of knowing whether a [= `ListArc`] exists. +pub trait ListArcSafe { + /// Informs the tracking inside this type that it now has a [`ListArc`= ] reference. + /// + /// This method may be called even if the tracking inside this type th= inks that a `ListArc` + /// reference exists. (But only if that's not actually the case.) + /// + /// # Safety + /// + /// Must not be called if a [`ListArc`] already exist for this value. + unsafe fn on_create_list_arc_from_unique(self: Pin<&mut Self>); + + /// Informs the tracking inside this type that there is no [`ListArc`]= reference anymore. + /// + /// # Safety + /// + /// Must only be called if there is no [`ListArc`] reference, but the = tracking thinks there is. + unsafe fn on_drop_list_arc(&self); +} + +/// Declares that this type supports [`ListArc`]. +/// +/// When using this macro, it will only be possible to create a [`ListArc`= ] from a [`UniqueArc`]. +#[macro_export] +macro_rules! impl_list_arc_safe { + (impl$({$($generics:tt)*})? ListArcSafe<$num:tt> for $t:ty { untracked= ; } $($rest:tt)*) =3D> { + impl$(<$($generics)*>)? $crate::list::ListArcSafe<$num> for $t { + unsafe fn on_create_list_arc_from_unique(self: ::core::pin::Pi= n<&mut Self>) {} + unsafe fn on_drop_list_arc(&self) {} + } + $crate::list::impl_list_arc_safe! { $($rest)* } + }; + + () =3D> {}; +} +pub use impl_list_arc_safe; + +/// A wrapper around [`Arc`] that's guaranteed unique for the given id. +/// +/// The `ListArc` type can be thought of as a special reference to a refco= unted object that owns the +/// permission to manipulate the `next`/`prev` pointers stored in the refc= ounted object. By ensuring +/// that each object has only one `ListArc` reference, the owner of that r= eference is assured +/// exclusive access to the `next`/`prev` pointers. When a `ListArc` is in= serted into a `List`, the +/// `List` takes ownership of the `ListArc` reference. +/// +/// There are various strategies to ensuring that a value has only one `Li= stArc` reference. The +/// simplest is to convert a [`UniqueArc`] into a `ListArc`. However, the = refcounted object could +/// also keep track of whether a `ListArc` exists using a boolean, which c= ould allow for the +/// creation of new `ListArc` references from an [`Arc`] reference. Whatev= er strategy is used, the +/// relevant tracking is referred to as "the tracking inside `T`", and the= [`ListArcSafe`] trait +/// (and its subtraits) are used to update the tracking when a `ListArc` i= s created or destroyed. +/// +/// Note that we allow the case where the tracking inside `T` thinks that = a `ListArc` exists, but +/// actually, there isn't a `ListArc`. However, we do not allow the opposi= te situation where a +/// `ListArc` exists, but the tracking thinks it doesn't. This is because = the former can at most +/// result in us failing to create a `ListArc` when the operation could su= cceed, whereas the latter +/// can result in the creation of two `ListArc` references. +/// +/// While this `ListArc` is unique for the given id, there still might exi= st normal `Arc` +/// references to the object. +/// +/// # Invariants +/// +/// * Each reference counted object has at most one `ListArc` for each val= ue of `ID`. +/// * The tracking inside `T` is aware that a `ListArc` reference exists. +#[repr(transparent)] +pub struct ListArc +where + T: ListArcSafe + ?Sized, +{ + arc: Arc, +} + +impl, const ID: u64> ListArc { + /// Constructs a new reference counted instance of `T`. + #[inline] + pub fn new(contents: T, flags: Flags) -> Result { + Ok(Self::from(UniqueArc::new(contents, flags)?)) + } + + /// Use the given initializer to in-place initialize a `T`. + /// + /// If `T: !Unpin` it will not be able to move afterwards. + // We don't implement `InPlaceInit` because `ListArc` is implicitly pi= nned. This is similar to + // what we do for `Arc`. + #[inline] + pub fn pin_init(init: impl PinInit, flags: Flags) -> Result + where + E: From, + { + Ok(Self::from(UniqueArc::try_pin_init(init, flags)?)) + } + + /// Use the given initializer to in-place initialize a `T`. + /// + /// This is equivalent to [`ListArc::pin_init`], since a [`ListArc`= ] is always pinned. + #[inline] + pub fn init(init: impl Init, flags: Flags) -> Result + where + E: From, + { + Ok(Self::from(UniqueArc::try_init(init, flags)?)) + } +} + +impl From> for ListArc +where + T: ListArcSafe + ?Sized, +{ + /// Convert a [`UniqueArc`] into a [`ListArc`]. + #[inline] + fn from(unique: UniqueArc) -> Self { + Self::from(Pin::from(unique)) + } +} + +impl From>> for ListArc +where + T: ListArcSafe + ?Sized, +{ + /// Convert a pinned [`UniqueArc`] into a [`ListArc`]. + #[inline] + fn from(mut unique: Pin>) -> Self { + // SAFETY: We have a `UniqueArc`, so there is no `ListArc`. + unsafe { T::on_create_list_arc_from_unique(unique.as_mut()) }; + let arc =3D Arc::from(unique); + // SAFETY: We just called `on_create_list_arc_from_unique` on an a= rc without a `ListArc`, + // so we can create a `ListArc`. + unsafe { Self::transmute_from_arc(arc) } + } +} + +impl ListArc +where + T: ListArcSafe + ?Sized, +{ + /// Creates two `ListArc`s from a [`UniqueArc`]. + /// + /// The two ids must be different. + #[inline] + pub fn pair_from_unique(unique: UniqueArc) -> (Self= , ListArc) + where + T: ListArcSafe, + { + Self::pair_from_pin_unique(Pin::from(unique)) + } + + /// Creates two `ListArc`s from a pinned [`UniqueArc`]. + /// + /// The two ids must be different. + #[inline] + pub fn pair_from_pin_unique( + mut unique: Pin>, + ) -> (Self, ListArc) + where + T: ListArcSafe, + { + build_assert!(ID !=3D ID2); + + // SAFETY: We have a `UniqueArc`, so there is no `ListArc`. + unsafe { >::on_create_list_arc_from_unique(un= ique.as_mut()) }; + // SAFETY: We have a `UniqueArc`, so there is no `ListArc`. + unsafe { >::on_create_list_arc_from_unique(u= nique.as_mut()) }; + + let arc1 =3D Arc::from(unique); + let arc2 =3D Arc::clone(&arc1); + + // SAFETY: We just called `on_create_list_arc_from_unique` on an a= rc without a `ListArc` + // for both IDs (which are different), so we can create two `ListA= rc`s. + unsafe { + ( + Self::transmute_from_arc(arc1), + ListArc::transmute_from_arc(arc2), + ) + } + } + + /// Transmutes an [`Arc`] into a `ListArc` without updating the tracki= ng inside `T`. + /// + /// # Safety + /// + /// * The value must not already have a `ListArc` reference. + /// * The tracking inside `T` must think that there is a `ListArc` ref= erence. + #[inline] + unsafe fn transmute_from_arc(arc: Arc) -> Self { + // INVARIANT: By the safety requirements, the invariants on `ListA= rc` are satisfied. + Self { arc } + } + + /// Transmutes a `ListArc` into an [`Arc`] without updating the tracki= ng inside `T`. + /// + /// After this call, the tracking inside `T` will still think that the= re is a `ListArc` + /// reference. + #[inline] + fn transmute_to_arc(self) -> Arc { + // Use a transmute to skip destructor. + // + // 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) }; + } +} + +impl AsRef> for ListArc +where + T: ListArcSafe + ?Sized, +{ + #[inline] + fn as_ref(&self) -> &Arc { + self.as_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.46.0.rc2.264.g509ed76dc8-goog From nobody Fri Dec 19 19:07:43 2025 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 099C61EB49E for ; Tue, 6 Aug 2024 13:59:35 +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=1722952780; cv=none; b=IF7tjHIffe5V74nmlcDqzGoe5Bpg5ko2V2HRPUN0o4Yf79jigXHml2uQjdz6n20bn/aqFLkRA7BQhl7NqeatLlys4dmW91mtBDIpkuzHb3L0e1Vx2mTYuCuQWNqSRz7jo5HBf81314+wfCKahtG4qFcg81EbpLxoywwD/UJWDwg= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1722952780; c=relaxed/simple; bh=24+zPg1hM+JfZs8SjokP0Q5m1qxn5IqRmOm2SzNaij0=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=skQjvQXYNLgVWyLpa4gJ0G0S+56EYHMBuuApENEuLbRdbDQdj4QZOEKw93qW6wrTbfnVbAw5lA7QZ7azLM+ECwLAT1SA7MJNrrtYpuBiDmQip+03tjF+7IXrcjB2qBsnVXD753KSspa2NA1GeaQzcPtkvqcpYErCukVxz23zTqc= 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=LveUpjO1; 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="LveUpjO1" Received: by mail-yb1-f202.google.com with SMTP id 3f1490d57ef6-e05e3938a37so1034326276.2 for ; Tue, 06 Aug 2024 06:59:35 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1722952775; x=1723557575; 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=mjKIRQEP0h51pKM/XyArnFXlqwAOBzE7RmnKZZV9HO4=; b=LveUpjO1zTC3JS9KBse/n0VRsDi9t+KVlxqszN0Y0jh0skmB17yILqQnlA1AL1ek0j 90Yx63/KK5DMlr4S1aeaDMh9EY2q1eFy1x8isTt3zsRL/+rTD+UQPJi5TNOBpehPZfTI 7Tn3MIIIwPBokyMU1OzBxK4KxiDAoSkhmswWPBE3DADd3zLoEfkrokdxq6BZmPJjVhEw 5cgWgMHcF34rDxo3ZSw1oTZWSPJFB6sw8QWYxg0yPmsESlytuGri4IGvHkYyk5a53pXd JIjLV3jZRxYAaQCDZu/RmHJ8pnsPEyPJBq/4KJm4c6mzTuyhCSXQhELQ/io8XziAAEv8 IWOQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1722952775; x=1723557575; 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=mjKIRQEP0h51pKM/XyArnFXlqwAOBzE7RmnKZZV9HO4=; b=gFsQUkskcwpdjMpOECI3zgrZKyDPQL7RylVZeJkqnKAFtkFL6EYSWtK/NPgUtqzO3P lRkgbGJ2Tf06aOVUQ60gYmErAN+zyjL6mMfEjz7Wj4ThcsaqiniK2ibKzFDeXuDiPcqH 8Wz00dudEVIF1rAfyF6tfveEuMBOGt+A1Bt8qevvkFLa4dZpATE8DjVf/FuFK3vSBNWH WIpHk6PU5B53oSY3sXNnSuoCxuG1KAlN4OzXg8hz2feWCQ0Ck4K2t3OILfrdYdUEAOYa LLu6LSTHrPgLXOStfEGRwuYHqFGKDWP2rlPO9jrIwDY/0Uy1xPS5s7xnaNWjXzE68MTT tdIA== X-Forwarded-Encrypted: i=1; AJvYcCWkB44DUbsKppvmoRKaH5JUwJAB6jXf2TIKAqOaZ2CgwjJ0OSZqpCzfMhf3NpOCOOhVjzBMgVlmBIpEsPe3hh7uYFQdot6DhpklKV5C X-Gm-Message-State: AOJu0YyxiNDYb9El6+kq6XUB5oNuDQY89uZGKgSJJuD1YVyGWZg/YuWt Yz67Exfb/S0YjrXELRhJF9Ioe2aCeJXOVjv69+5TwcptIFMLhnimhj5+PyGQRFNH3YQqIfUbkMq Xgeq4qLKyBBbEpw== X-Google-Smtp-Source: AGHT+IHI9fqZyX8w3wgfTrqWljUctuk7nUi2QibBgVq4K8JVS9b/OWAEOK0LTxJdeRJdaULpx3tJ0FBFdMvYylw= X-Received: from aliceryhl.c.googlers.com ([fda3:e722:ac3:cc00:28:9cb1:c0a8:35bd]) (user=aliceryhl job=sendgmr) by 2002:a05:6902:1881:b0:e0e:4841:3a7e with SMTP id 3f1490d57ef6-e0e48413c8cmr168660276.7.1722952774866; Tue, 06 Aug 2024 06:59:34 -0700 (PDT) Date: Tue, 06 Aug 2024 13:58:55 +0000 In-Reply-To: <20240806-linked-list-v4-0-23efc510ec92@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240806-linked-list-v4-0-23efc510ec92@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=11251; i=aliceryhl@google.com; h=from:subject:message-id; bh=24+zPg1hM+JfZs8SjokP0Q5m1qxn5IqRmOm2SzNaij0=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBmsiw4VpObni12GwUGWximtmn7bTqGGSyX0QD5j jWE6wi1eo2JAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCZrIsOAAKCRAEWL7uWMY5 Ro5xEACj6c+vvzJxEs3sAIz/Oi1ZWPE1ZnHnTzkpbTDpmb269S43jwwCfaILhq5GOSWZLitBafA XAMOSQkh4Vro/E6ygI2e7w+AjDE8GcpkMfKcaPzNbkordA5TBAVlWQZGq8ppXXbBKqLdNTEHmQb LE8EPjGNbwqn6J/TAC1640Us8ckbWhg4N22cZF3sQWpsjLni2UVIsBAzB+d3Bl1eK60hf3x8Is3 jZ83VnE/2CZF/Irt+ghFN8nmaK0fq/VjiAMBjT7BD/AWsCryh2la7a7gfoZsF52on2m13xiNbnt qEvDzqL/3GZc89lUNTkhj6Dy1XAG2xkDbBNIl2rpWZcxrYQrSTNv4AGU4HDXXNCQJl0UaevtiVc FRMyGLPiwVLU+rqfU75amHD6pTAcZmfrAMYA3YuzYdivHM32x9UIkuJHNbMfLosrAaLP20GX4WY wx75cqlwMPIcWGJkxUp6H4p7BNQMzX0w2KQHOuZzRQSVn8t+j49VpEexoEVF6HaY19vSYBmJ2Ug VUYsv1KCo28z/t2+jLpikaOjBmpR02YhFlEPnQtRUH00gOhbYmVltQAd8TJTqhTJZIbNDhXXLlz OZLYKl36Tckz9/1h1l8wIs5wfQE+/9DQbL7SuD39VXtrSS1EpHEKYW+LRe9hHkn4qSFeFMK6atA e+H6v0wggKgn1gg== X-Mailer: b4 0.13.0 Message-ID: <20240806-linked-list-v4-3-23efc510ec92@google.com> Subject: [PATCH v4 03/10] rust: list: add tracking for ListArc From: Alice Ryhl To: Miguel Ojeda , Andrew Morton Cc: Alex Gaynor , Wedson Almeida Filho , Boqun Feng , Gary Guo , "=?utf-8?q?Bj=C3=B6rn_Roy_Baron?=" , Benno Lossin , Andreas Hindborg , Marco Elver , Coly Li , Paolo Abeni , Pierre Gondois , Ingo Molnar , Jakub Kicinski , Wei Yang , Matthew Wilcox , linux-kernel@vger.kernel.org, rust-for-linux@vger.kernel.org, Alice Ryhl , Kees Cook Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Add the ability to track whether a ListArc exists for a given value, allowing for the creation of ListArcs without going through UniqueArc. The `impl_list_arc_safe!` macro is extended with a `tracked_by` strategy that defers the tracking of ListArcs to a field of the struct. Additionally, the AtomicListArcTracker type is introduced, which can track whether a ListArc exists using an atomic. By deferring the tracking to a field of type AtomicListArcTracker, structs gain the ability to create ListArcs without going through a UniqueArc. Rust Binder uses this for some objects where we want to be able to insert them into a linked list at any time. Using the AtomicListArcTracker, we are able to check whether an item is already in the list, and if not, we can create a `ListArc` and push it. The macro has the ability to defer the tracking of ListArcs to a field, using whatever strategy that field has. Since we don't add any strategies other than AtomicListArcTracker, another similar option would be to hard-code that the field should be an AtomicListArcTracker. However, Rust Binder has a case where the AtomicListArcTracker is not stored directly in the struct, but in a sub-struct. Furthermore, the outer struct is generic: struct Wrapper { links: ListLinks, inner: T, } Here, the Wrapper struct implements ListArcSafe with `tracked_by inner`, and then the various types used with `inner` also uses the macro to implement ListArcSafe. Some of them use the untracked strategy, and some of them use tracked_by with an AtomicListArcTracker. This way, Wrapper just inherits whichever choice `inner` has made. Signed-off-by: Alice Ryhl Reviewed-by: Benno Lossin --- rust/kernel/list.rs | 2 +- rust/kernel/list/arc.rs | 171 ++++++++++++++++++++++++++++++++++++++++++++= +++- 2 files changed, 170 insertions(+), 3 deletions(-) diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs index fb16ea43b2ba..8e1533ee987b 100644 --- a/rust/kernel/list.rs +++ b/rust/kernel/list.rs @@ -5,4 +5,4 @@ //! A linked list implementation. =20 mod arc; -pub use self::arc::{impl_list_arc_safe, ListArc, ListArcSafe}; +pub use self::arc::{impl_list_arc_safe, AtomicTracker, ListArc, ListArcSaf= e, TryNewListArc}; diff --git a/rust/kernel/list/arc.rs b/rust/kernel/list/arc.rs index 966076da4a75..c5921a7d5966 100644 --- a/rust/kernel/list/arc.rs +++ b/rust/kernel/list/arc.rs @@ -7,9 +7,10 @@ use crate::alloc::{AllocError, Flags}; use crate::prelude::*; use crate::sync::{Arc, ArcBorrow, UniqueArc}; -use core::marker::Unsize; +use core::marker::{PhantomPinned, Unsize}; use core::ops::Deref; use core::pin::Pin; +use core::sync::atomic::{AtomicBool, Ordering}; =20 /// Declares that this type has some way to ensure that there is exactly o= ne `ListArc` instance for /// this id. @@ -48,9 +49,38 @@ pub trait ListArcSafe { unsafe fn on_drop_list_arc(&self); } =20 +/// Declares that this type is able to safely attempt to create `ListArc`s= at any time. +/// +/// # Safety +/// +/// The guarantees of `try_new_list_arc` must be upheld. +pub unsafe trait TryNewListArc: ListArcSafe { + /// Attempts to convert an `Arc` into an `ListArc`. Return= s `true` if the + /// conversion was successful. + /// + /// This method should not be called directly. Use [`ListArc::try_from= _arc`] instead. + /// + /// # Guarantees + /// + /// If this call returns `true`, then there is no [`ListArc`] pointing= to this value. + /// Additionally, this call will have transitioned the tracking inside= `Self` from not thinking + /// that a [`ListArc`] exists, to thinking that a [`ListArc`] exists. + fn try_new_list_arc(&self) -> bool; +} + /// Declares that this type supports [`ListArc`]. /// -/// When using this macro, it will only be possible to create a [`ListArc`= ] from a [`UniqueArc`]. +/// This macro supports a few different strategies for implementing the tr= acking inside the type: +/// +/// * The `untracked` strategy does not actually keep track of whether a [= `ListArc`] exists. When +/// using this strategy, the only way to create a [`ListArc`] is using a= [`UniqueArc`]. +/// * The `tracked_by` strategy defers the tracking to a field of the stru= ct. The user much specify +/// which field to defer the tracking to. The field must implement [`Lis= tArcSafe`]. If the field +/// implements [`TryNewListArc`], then the type will also implement [`Tr= yNewListArc`]. +/// +/// The `tracked_by` strategy is usually used by deferring to a field of t= ype +/// [`AtomicTracker`]. However, it is also possible to defer the tracking = to another struct +/// using also using this macro. #[macro_export] macro_rules! impl_list_arc_safe { (impl$({$($generics:tt)*})? ListArcSafe<$num:tt> for $t:ty { untracked= ; } $($rest:tt)*) =3D> { @@ -61,6 +91,39 @@ unsafe fn on_drop_list_arc(&self) {} $crate::list::impl_list_arc_safe! { $($rest)* } }; =20 + (impl$({$($generics:tt)*})? ListArcSafe<$num:tt> for $t:ty { + tracked_by $field:ident : $fty:ty; + } $($rest:tt)*) =3D> { + impl$(<$($generics)*>)? $crate::list::ListArcSafe<$num> for $t { + unsafe fn on_create_list_arc_from_unique(self: ::core::pin::Pi= n<&mut Self>) { + $crate::assert_pinned!($t, $field, $fty, inline); + + // SAFETY: This field is structurally pinned as per the ab= ove assertion. + let field =3D unsafe { + ::core::pin::Pin::map_unchecked_mut(self, |me| &mut me= .$field) + }; + // SAFETY: The caller promises that there is no `ListArc`. + unsafe { + <$fty as $crate::list::ListArcSafe<$num>>::on_create_l= ist_arc_from_unique(field) + }; + } + unsafe fn on_drop_list_arc(&self) { + // SAFETY: The caller promises that there is no `ListArc` = reference, and also + // promises that the tracking thinks there is a `ListArc` = reference. + unsafe { <$fty as $crate::list::ListArcSafe<$num>>::on_dro= p_list_arc(&self.$field) }; + } + } + unsafe impl$(<$($generics)*>)? $crate::list::TryNewListArc<$num> f= or $t + where + $fty: TryNewListArc<$num>, + { + fn try_new_list_arc(&self) -> bool { + <$fty as $crate::list::TryNewListArc<$num>>::try_new_list_= arc(&self.$field) + } + } + $crate::list::impl_list_arc_safe! { $($rest)* } + }; + () =3D> {}; } pub use impl_list_arc_safe; @@ -205,6 +268,52 @@ pub fn pair_from_pin_unique( } } =20 + /// Try to create a new `ListArc`. + /// + /// This fails if this value already has a `ListArc`. + pub fn try_from_arc(arc: Arc) -> Result> + where + T: TryNewListArc, + { + if arc.try_new_list_arc() { + // SAFETY: The `try_new_list_arc` method returned true, so we = made the tracking think + // that a `ListArc` exists. This lets us create a `ListArc`. + Ok(unsafe { Self::transmute_from_arc(arc) }) + } else { + Err(arc) + } + } + + /// Try to create a new `ListArc`. + /// + /// This fails if this value already has a `ListArc`. + pub fn try_from_arc_borrow(arc: ArcBorrow<'_, T>) -> Option + where + T: TryNewListArc, + { + if arc.try_new_list_arc() { + // SAFETY: The `try_new_list_arc` method returned true, so we = made the tracking think + // that a `ListArc` exists. This lets us create a `ListArc`. + Some(unsafe { Self::transmute_from_arc(Arc::from(arc)) }) + } else { + None + } + } + + /// Try to create a new `ListArc`. + /// + /// If it's not possible to create a new `ListArc`, then the `Arc` is = dropped. This will never + /// run the destructor of the value. + pub fn try_from_arc_or_drop(arc: Arc) -> Option + where + T: TryNewListArc, + { + match Self::try_from_arc(arc) { + Ok(list_arc) =3D> Some(list_arc), + Err(arc) =3D> Arc::into_unique_or_drop(arc).map(Self::from), + } + } + /// Transmutes an [`Arc`] into a `ListArc` without updating the tracki= ng inside `T`. /// /// # Safety @@ -350,3 +459,61 @@ impl core::ops::DispatchFromDyn> for ListArc U: ListArcSafe + ?Sized, { } + +/// A utility for tracking whether a [`ListArc`] exists using an atomic. +/// +/// # Invariant +/// +/// If the boolean is `false`, then there is no [`ListArc`] for this value. +#[repr(transparent)] +pub struct AtomicTracker { + inner: AtomicBool, + // This value needs to be pinned to justify the INVARIANT: comment in = `AtomicTracker::new`. + _pin: PhantomPinned, +} + +impl AtomicTracker { + /// Creates a new initializer for this type. + pub fn new() -> impl PinInit { + // INVARIANT: Pin-init initializers can't be used on an existing `= Arc`, so this value will + // not be constructed in an `Arc` that already has a `ListArc`. + Self { + inner: AtomicBool::new(false), + _pin: PhantomPinned, + } + } + + fn project_inner(self: Pin<&mut Self>) -> &mut AtomicBool { + // SAFETY: The `inner` field is not structurally pinned, so we may= obtain a mutable + // reference to it even if we only have a pinned reference to `sel= f`. + unsafe { &mut Pin::into_inner_unchecked(self).inner } + } +} + +impl ListArcSafe for AtomicTracker { + unsafe fn on_create_list_arc_from_unique(self: Pin<&mut Self>) { + // INVARIANT: We just created a ListArc, so the boolean should be = true. + *self.project_inner().get_mut() =3D true; + } + + unsafe fn on_drop_list_arc(&self) { + // INVARIANT: We just dropped a ListArc, so the boolean should be = false. + self.inner.store(false, Ordering::Release); + } +} + +// SAFETY: If this method returns `true`, then by the type invariant there= is no `ListArc` before +// this call, so it is okay to create a new `ListArc`. +// +// The acquire ordering will synchronize with the release store from the d= estruction of any +// previous `ListArc`, so if there was a previous `ListArc`, then the dest= ruction of the previous +// `ListArc` happens-before the creation of the new `ListArc`. +unsafe impl TryNewListArc for AtomicTracker { + fn try_new_list_arc(&self) -> bool { + // INVARIANT: If this method returns true, then the boolean used t= o be false, and is no + // longer false, so it is okay for the caller to create a new [`Li= stArc`]. + self.inner + .compare_exchange(false, true, Ordering::Acquire, Ordering::Re= laxed) + .is_ok() + } +} --=20 2.46.0.rc2.264.g509ed76dc8-goog From nobody Fri Dec 19 19:07:43 2025 Received: from mail-wm1-f74.google.com (mail-wm1-f74.google.com [209.85.128.74]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id E3ABC20127B for ; Tue, 6 Aug 2024 13:59:38 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.74 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1722952780; cv=none; b=co7KFq3c49scCuT5L0Dd3Ju7subokLJ5DEOeYfnpj9aolZalLxhEUOZF+KzEMsfBPhnKs/tWNIN3kWgcmHHTpR/y6islwhmm3rkp2nWdx+YYEjZiEE5Gn1erKBKrw23n0su806+OqPPvdyBTethzeQIDogVbZXWzZWiL/w/l/Bo= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1722952780; c=relaxed/simple; bh=r7zuSn6T8aiTDmoxN80zggpcp4KnpOuTv4p3Sl1rO74=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=l5OnkbmZLGPsNJjDfOw+mGOposzIS335hXgQNmJXKws7GnfgAMt5Bllm6WeYEpVcwJqPYiY2tggIJOcLdvNKf9w3aCAcpNdj38h0Y87VQqHKuEiv6k1SPi0ST4IVtx1XawID2995RZJqV3VdNO9s6wrdcDm1iC72VT1Mdhdr/uo= 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=J1TfrAna; arc=none smtp.client-ip=209.85.128.74 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=flex--aliceryhl.bounces.google.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="J1TfrAna" Received: by mail-wm1-f74.google.com with SMTP id 5b1f17b1804b1-4280a39ecebso32632235e9.0 for ; Tue, 06 Aug 2024 06:59:38 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1722952777; x=1723557577; 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=ldHWvt49sDIe8d9GqRkvJXWy/GtTjHwVlzeV5qEa4J4=; b=J1TfrAnaQiaLvD0+hE70hAB9UDCSCnIE8jFct4RzJbNDUvC0+vqVVQL/JzXBbZ5RqG CqCBTi5u0JMd/il9YscYTUk3xaplCwHKtmkBBNvfuGP0a1MHlmaIeQ+oeJufMk7UuxDd 82StvrRMe9kXgwCyWGrppEWe6zjvAaSRgQlmBDRKa1bpYg27/JxQa8Q2oQAYt6ogK1Me MTQ84023VPj4iiJXrjY99Z/RXXweuK57OGuAubZ1BwfD8TH5Gkc5IK91s8hk7pdF5saJ aqhOrDulxe2fLf7o9bGsE6aFXne+VcISGLNGKD/QudCizkpVWEtBtaW7b7MYbXNk2hT1 lXbQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1722952777; x=1723557577; 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=ldHWvt49sDIe8d9GqRkvJXWy/GtTjHwVlzeV5qEa4J4=; b=KpnLhYvJxgEoBRTxEMi4bwnE4eGweMZr3etYJI8o474zQBXO9n2t0ea9E0X2cAIyzM XPNybhwVGLtj8oSS0Uewe/MJugsJLeHcJNhcdbGkUN10VCRGQV6i8HCqlPgCFl2KVAWY pG1woCA0myUzfh3WKLCiaBdDqHVDbGDJIAgW36CD/GGPQPptEBdsra/eSM8CmyxokpYC yFzt9r6S+Yaen/mc/tGQRckQtpryo1xFu3/ds4ZhdX3oHwJyFMhs0JsIGvg3vhfFqW9e 4+vGqhuQzCe4WFpJk0ONd3A7YjTrSimVtsmOaMWWf9KNOT/OFUKQdIG4oretB8z2VJ60 2qYQ== X-Forwarded-Encrypted: i=1; AJvYcCVznVi2bbTeMgPJ2lJYEYdCf+gkwkLuUBdu1KjnTtRtowEpk7Za+Rh5yKM3nwqF8LQw0E3PVIX4V9wEW53wBhUHcmlesNEVHEh0HyZR X-Gm-Message-State: AOJu0Ywv14NioRagXIu/YVHgzbgi98EMh81nOFKCRUacki+kBJs6DnIo GrYfHanmIhLfUMdllXce0eoHxpX8T4R9jVD+Cn06eJDD4kF/TFPh5z8pV/41+Lqa12aMiKhSdJ9 H888pHESbaB2FqQ== X-Google-Smtp-Source: AGHT+IEqaacVkLJfCD8zsGz5kCmDhyXK1FewElTfbchv5QMQEDf0xI/Y7xoF2Umo7xl+OIrm6tI9BSIhh77wwco= X-Received: from aliceryhl.c.googlers.com ([fda3:e722:ac3:cc00:28:9cb1:c0a8:35bd]) (user=aliceryhl job=sendgmr) by 2002:a05:600c:4928:b0:426:67d8:e09b with SMTP id 5b1f17b1804b1-428e47092dcmr406325e9.1.1722952777212; Tue, 06 Aug 2024 06:59:37 -0700 (PDT) Date: Tue, 06 Aug 2024 13:58:56 +0000 In-Reply-To: <20240806-linked-list-v4-0-23efc510ec92@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240806-linked-list-v4-0-23efc510ec92@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=6227; i=aliceryhl@google.com; h=from:subject:message-id; bh=r7zuSn6T8aiTDmoxN80zggpcp4KnpOuTv4p3Sl1rO74=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBmsiw5+GHJ/klVk72FhCBbbiwKSOukj+m07VUKr 8BBoW+QcgOJAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCZrIsOQAKCRAEWL7uWMY5 Rn0MD/9SUxhdpoaP2ThrHhwSTWvEobJYYQ4Wu1Jej80IAWM6W/OcJ8HkoyL5v2MTpnuyTxWm09V gvtlUN5g2ytfLn+HkSwqB3Qz2USLEEESEMAwgXKPoWMEP+1gJFjiUOqxBLGUYuE2oOOdEaZDcyE Irp4blK1rAq8mIB8OGiYhWD18AXeYys0sZCu/J51JGIZ7jwWdC7h956N3bD0ExOYE3fPTT6/Vsl D+TNb9B2ix8YydSC4RFaWYyg6yY4uInP8F4xfuHL1H9ofhUfqzUH4Yv5vN5vV50aPxEF0ywVbGP 8aaG/+1n6lO8GWCjlJVDp7k31SEOKolH0Uukq0GVB/yA587VtSUQ14E7CK9FJ1M5cB4xplAaZuk eHXjuLFWYTLonodni8euSHXd8c2/s0tOt7etGDLjzGmdRJurES0XidFZqkrmyUjuShKxier7Lmh XJ07UJCzDqdw6xFgrDb50p0tfU/A+10W0DFjiD2tPL3JdoWpvGE1XmvWeJTzFuZuTPBUW2VgEDs 3v+YbRwd6ttoYCTU/foce0sExuH/k2NsHm1KPnyr0vjpiPOnUKU6IIpi9EZ5ENNXv4E8nPE7Xm9 JN2J3n8R3kmpOFfI+Wio0d3YqJWApFcEzH5S+4xKYpGx5dGgZcjsPWMrLWd/ToTJPNMSXyCo+/H am5nPHjNQ1ONVRw== X-Mailer: b4 0.13.0 Message-ID: <20240806-linked-list-v4-4-23efc510ec92@google.com> Subject: [PATCH v4 04/10] 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 , Coly Li , Paolo Abeni , Pierre Gondois , Ingo Molnar , Jakub Kicinski , Wei Yang , Matthew Wilcox , linux-kernel@vger.kernel.org, rust-for-linux@vger.kernel.org, Alice Ryhl , Kees Cook Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable 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 Reviewed-by: Benno Lossin --- rust/kernel/list.rs | 119 ++++++++++++++++++++++++++++++++++++++++++++++++= ++++ 1 file changed, 119 insertions(+) diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs index 8e1533ee987b..074ae863ff5a 100644 --- a/rust/kernel/list.rs +++ b/rust/kernel/list.rs @@ -4,5 +4,124 @@ =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, AtomicTracker, ListArc, ListArcSaf= e, TryNewListArc}; + +/// Implemented by types where a [`ListArc`] can be inserted into a = `List`. +/// +/// # Safety +/// +/// Implementers must ensure that they provide the guarantees documented o= n methods provided by +/// this trait. +/// +/// [`ListArc`]: ListArc +pub unsafe trait ListItem: ListArcSafe { + /// Views the [`ListLinks`] for this value. + /// + /// # Guarantees + /// + /// If there is a previous call to `prepare_to_insert` and there is no= call to `post_remove` + /// since the most recent such call, then this returns the same pointe= r as the one returned by + /// the most recent call to `prepare_to_insert`. + /// + /// Otherwise, the returned pointer points at a read-only [`ListLinks`= ] with two null pointers. + /// + /// # Safety + /// + /// The provided pointer must point at a valid value. (It need not be = in an `Arc`.) + unsafe fn view_links(me: *const Self) -> *mut ListLinks; + + /// View the full value given its [`ListLinks`] field. + /// + /// Can only be used when the value is in a list. + /// + /// # Guarantees + /// + /// * Returns the same pointer as the one passed to the most recent ca= ll 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 most recent call to= `prepare_to_insert`, or + /// from a call to `view_links` that happened after the most recent = call to + /// `prepare_to_insert`. + /// * Since the most recent call to `prepare_to_insert`, the `post_rem= ove` 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`. + /// + /// # Safety + /// + /// The provided pointer must be the pointer returned by the most rece= nt 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 { + // This type is `!Unpin` for aliasing reasons as the pointers are part= of an intrusive linked + // list. + #[allow(dead_code)] + inner: Opaque, +} + +// SAFETY: The only way to access/modify the pointers inside of `ListLinks= ` is via holding the +// associated `ListArc`. Since that type correctly implements `Send= `, it is impossible to +// move this an instance of this type to a different thread if the pointee= s are `!Send`. +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.46.0.rc2.264.g509ed76dc8-goog From nobody Fri Dec 19 19:07:43 2025 Received: from mail-wm1-f73.google.com (mail-wm1-f73.google.com [209.85.128.73]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 5C64D205E24 for ; Tue, 6 Aug 2024 13:59:41 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.73 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1722952783; cv=none; b=A0QQRHaCRgSltblLZGqhMxFkb7lgvtEoiodZfBobkrKWssf8BJARTFbWFuhsO5Xew7Rblf2LtWq0Mnk4DmSXoyWPtVmAO3/dn7Io2amiRFFzXffENjtKsg+uARIdt5W8t77zcH3h+7hijq6nudlw1fn8V86R8uoUqN03RGAbD1Q= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1722952783; c=relaxed/simple; bh=rtZ/Cz0nmdTIH2ZRYlFWyz7pI2Orl32ZaW2okmlCPYA=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=fqbAQeK3aIkmvOl/Ln1xTAlgeuic0u38aCCQAq8LkGneBPZ9GIe9rxLOadUXwZVy/Z98SPNYUR/RGKUsISj5Nq5cttZgxXBchIIq8z6li3LIxisJ+dn7sFTD93SgjIJLOsHYbZTyr8FA1gWn7dpBDSHsIccWs0ZsmauaFPMwLuw= 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=xgeC2B6E; arc=none smtp.client-ip=209.85.128.73 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=flex--aliceryhl.bounces.google.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="xgeC2B6E" Received: by mail-wm1-f73.google.com with SMTP id 5b1f17b1804b1-42808685ef0so4046405e9.2 for ; Tue, 06 Aug 2024 06:59:41 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1722952780; x=1723557580; 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=OPK5aP9P7TQo98Jo6W3QAlh4MbCdd1UBTLXW9ITb2R0=; b=xgeC2B6Es9XE4T1rMCXbgIWWvB/UvS0ECujZQvOLOGCDmDWJ5Xpcp8sMsqbn8HUQfE IeSOTkIjf9ObCHLGsJ8Q4ZM7p5Ybsz8WkDK2D1OGvdEzmoue3lHMqGLGbHI2qEK+7CbH YSkBneCRjoO/obkhiPt+cA8U3xYIcAhwbO6y4GosdfGQAyvHhJ4lxgdpSmsh7pbWygXT ItOnQh5bVN/GPFu3bfeDYjnKGuiqlrta70PB0KK4vMxhgBCHZXWmaAxcNuaCYalR4nmm PSgbwDqmDch8A7y8zBe+kNepfBIYhUAApTB/wNdn5OGniLnyzo9ECdTVjPX9NRnwn+AY 2w9w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1722952780; x=1723557580; 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=OPK5aP9P7TQo98Jo6W3QAlh4MbCdd1UBTLXW9ITb2R0=; b=RViEhYCFucNpRlt5bqtYsUFNtAO6tPJyrmnL3SJxEnI+DXi8JItd5gw4jR1U673usI L8W1rf67IiSLtd0CzMX8rvcjcw1MRBWQYv8vveL6iv+x6TidNECmWRdb5B1plp9DLM3D yNR0h/nvLu61xG38DDEQ+wImWaAfF1A507EraK7+28pMA5SSGOvC2I+p+vKLviCpK12e XzvSmybhLpqizHd7NAA++1eEqXa98ieOwbbgW+8U0OmKXoqRkO0pKqNl9yWlgHwsdP1G 9fyTXeoalMtqkg7Q7SYrAZJcdzTHbfPisr8zEY4DLVa0xXQGDqV0iYSLLYiE9N/UxNhn /g7g== X-Forwarded-Encrypted: i=1; AJvYcCXkX0NYLVcvOeJWwKokLXvtAQIpf2g/9tipoQkanXgoGK3ituoHsKWxw3Mc4nrp/X6zT6vfeWmgdMAIu8ZagTw8WfgVTDq1C6psd/Zn X-Gm-Message-State: AOJu0Yxfd2Szm0PfFOabitRbhL7ueyotVUdsedU9KkeTGISyRy84XmHl IXcpkM1SkSuK70FMoOXpSuak9ddEkvimByLQYHft3TT8Tr12gkZGhICj77zNi5VhbwyL9Jao6NM 7CtpZ7+lOoZG0NA== X-Google-Smtp-Source: AGHT+IHV8qNwHdDlfHIWoDVm4mlg7YXGKo/s4jvnPCT3nJds1Vw7MEM9rwkMUaiAlAZh/jygn45OMFsoMIFT9Gc= X-Received: from aliceryhl.c.googlers.com ([fda3:e722:ac3:cc00:28:9cb1:c0a8:35bd]) (user=aliceryhl job=sendgmr) by 2002:a05:600c:5108:b0:428:192f:c99e with SMTP id 5b1f17b1804b1-428f59a1389mr220005e9.4.1722952779639; Tue, 06 Aug 2024 06:59:39 -0700 (PDT) Date: Tue, 06 Aug 2024 13:58:57 +0000 In-Reply-To: <20240806-linked-list-v4-0-23efc510ec92@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240806-linked-list-v4-0-23efc510ec92@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=8482; i=aliceryhl@google.com; h=from:subject:message-id; bh=rtZ/Cz0nmdTIH2ZRYlFWyz7pI2Orl32ZaW2okmlCPYA=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBmsiw5GcWX+66OuYPUTv78Aag/LHFwoDBvQ58sO qO4duJRgPOJAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCZrIsOQAKCRAEWL7uWMY5 Rn7/D/48VM+WdeuVsx+cTPqhRwnpbdew/l3fa+6gNcqpNQScWs9H9Dkvi+f99caoq+tNaWXiHDD GOzoXd8ZqabQk5P98nEBwapAeRs+/1fzJHroBb7RtmfkJRsIiZhNpB6eVdkmrOiAVt8RRGc0/3x 3QRZrLOZVGJRokoBzUHmO3KbNpze5MJMQAl4BQMJof5ReFA/JmOkbjuz+04f/t/sqoRv6iwbBTr 937Hww9DNztnOKZlfEk07qMQhaEOrXpigAwIsOoc2VaZWZkE5aDo9ySZ3czGlE7iyCbDqCyt1G2 b0lGJ1wE9FxtPxhRirn3wo1EwQsvzlvTofP05ysEVHftVqk5jiufJObUVzLTy3r/6LfvIQI5o11 2LcLWzOi7960pP+7+Jg+zmOd9TBjDRVyztvPBG3+RYsi+yQBBrudd61AaIJvo1iaiZrq99QyTye FahV+AP6i+THdCPsc1vH4zl/mTMgx3cu2KMHkZ5/p0nHQaK+jF5PAEiE9PJOq57pJ/onCUTWg02 LoLVB/PLe7USLZ12dCYw5EszmWv3aYQ2mTBGoZx3Sw/7Ld1VJZYH0H6i1YltTEY+fqNVVLox6Mo QdKVnXAn1Eb6e785ROQeIzo9QDpZ2r4Uos1RyoQY+aw2Zu3Ve+iR/YrfB9aB4g99zs27PlG3xHM JVJkLK0lzzZBmZQ== X-Mailer: b4 0.13.0 Message-ID: <20240806-linked-list-v4-5-23efc510ec92@google.com> Subject: [PATCH v4 05/10] 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 , Coly Li , Paolo Abeni , Pierre Gondois , Ingo Molnar , Jakub Kicinski , Wei Yang , Matthew Wilcox , linux-kernel@vger.kernel.org, rust-for-linux@vger.kernel.org, Alice Ryhl , Kees Cook Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable 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 Reviewed-by: Benno Lossin --- rust/kernel/list.rs | 3 + rust/kernel/list/impl_list_item_mod.rs | 143 +++++++++++++++++++++++++++++= ++++ 2 files changed, 146 insertions(+) diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs index 074ae863ff5a..670d53989b8f 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, AtomicTracker, ListArc, ListArcSaf= e, TryNewListArc}; =20 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..30886e64b8ef --- /dev/null +++ b/rust/kernel/list/impl_list_item_mod.rs @@ -0,0 +1,143 @@ +// 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. Use the [`impl_has_list_links= !`] macro to implement +/// this trait. +/// +/// # Safety +/// +/// All values of this type must have a `ListLinks` field at the given= offset. +/// +/// The implementation of `raw_get_list_links` must not be changed. +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_list_links!` to be correct. + #[inline] + unsafe fn raw_get_list_links(ptr: *mut Self) -> *mut ListLinks { + // SAFETY: The caller promises that the pointer is valid. The impl= ementer promises that the + // `OFFSET` constant is correct. + unsafe { (ptr as *mut u8).add(Self::OFFSET) as *mut ListLinks } + } +} + +/// Implements the [`HasListLinks`] trait for the given type. +#[macro_export] +macro_rules! impl_has_list_links { + ($(impl$(<$($implarg:ident),*>)? + HasListLinks$(<$id:tt>)? + for $self:ident $(<$($selfarg:ty),*>)? + { self$(.$field:ident)* } + )*) =3D> {$( + // SAFETY: The implementation of `raw_get_list_links` only compile= s if the field has the + // right type. + // + // The implementation of `raw_get_list_links` is not changed since= the `addr_of_mut!` macro + // is equivalent to the pointer offset operation in the trait defi= nition. + 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. We know that this + // expression doesn't follow any pointers, as the `offset_= of!` invocation above + // would otherwise not compile. + unsafe { ::core::ptr::addr_of_mut!((*ptr)$(.$field)*) } + } + } + )*}; +} +pub use impl_has_list_links; + +/// Implements the [`ListItem`] trait for the given type. +/// +/// Requires that the type implements [`HasListLinks`]. Use the [`impl_has= _list_links!`] macro to +/// implement that trait. +/// +/// [`ListItem`]: crate::list::ListItem +#[macro_export] +macro_rules! impl_list_item { + ( + $(impl$({$($generics:tt)*})? ListItem<$num:tt> for $t:ty { + using ListLinks; + })* + ) =3D> {$( + // SAFETY: See GUARANTEES comment on each method. + unsafe impl$(<$($generics)*>)? $crate::list::ListItem<$num> for $t= { + // GUARANTEES: + // * This returns the same pointer as `prepare_to_insert` beca= use `prepare_to_insert` + // is implemented in terms of `view_links`. + // * By the type invariants of `ListLinks`, the `ListLinks` ha= s two null pointers when + // this value is not in a list. + unsafe fn view_links(me: *const Self) -> *mut $crate::list::Li= stLinks<$num> { + // SAFETY: The caller guarantees that `me` points at a val= id value of type `Self`. + unsafe { + >::raw_get_li= st_links(me.cast_mut()) + } + } + + // GUARANTEES: + // * `me` originates from the most recent call to `prepare_to_= insert`, which just added + // `offset` to the pointer passed to `prepare_to_insert`. Th= is method subtracts + // `offset` from `me` so it returns the pointer originally p= assed to + // `prepare_to_insert`. + // * The pointer remains valid until the next call to `post_re= move` because the caller + // of the most recent call to `prepare_to_insert` promised t= o retain ownership of the + // `ListArc` containing `Self` until the next call to `post_= remove`. The value cannot + // be destroyed while a `ListArc` reference exists. + unsafe fn view_value(me: *mut $crate::list::ListLinks<$num>) -= > *const Self { + let offset =3D >:= :OFFSET; + // SAFETY: `me` originates from the most recent call to `p= repare_to_insert`, so it + // points at the field at offset `offset` in a value of ty= pe `Self`. Thus, + // subtracting `offset` from `me` is still in-bounds of th= e allocation. + unsafe { (me as *const u8).sub(offset) as *const Self } + } + + // GUARANTEES: + // This implementation of `ListItem` will not give out exclusi= ve access to the same + // `ListLinks` several times because calls to `prepare_to_inse= rt` and `post_remove` + // must alternate and exclusive access is given up when `post_= remove` is called. + // + // Other invocations of `impl_list_item!` also cannot give out= exclusive access to the + // same `ListLinks` because you can only implement `ListItem` = once for each value of + // `ID`, and the `ListLinks` fields only work with the specifi= ed `ID`. + unsafe fn prepare_to_insert(me: *const Self) -> *mut $crate::l= ist::ListLinks<$num> { + // SAFETY: The caller promises that `me` points at a valid= value. + unsafe { >::view_link= s(me) } + } + + // GUARANTEES: + // * `me` originates from the most recent call to `prepare_to_= insert`, which just added + // `offset` to the pointer passed to `prepare_to_insert`. Th= is method subtracts + // `offset` from `me` so it returns the pointer originally p= assed to + // `prepare_to_insert`. + unsafe fn post_remove(me: *mut $crate::list::ListLinks<$num>) = -> *const Self { + let offset =3D >:= :OFFSET; + // SAFETY: `me` originates from the most recent call to `p= repare_to_insert`, so it + // points at the field at offset `offset` in a value of ty= pe `Self`. Thus, + // subtracting `offset` from `me` is still in-bounds of th= e allocation. + unsafe { (me as *const u8).sub(offset) as *const Self } + } + } + )*}; +} +pub use impl_list_item; --=20 2.46.0.rc2.264.g509ed76dc8-goog From nobody Fri Dec 19 19:07:43 2025 Received: from mail-wm1-f74.google.com (mail-wm1-f74.google.com [209.85.128.74]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 2F1E42139BC for ; Tue, 6 Aug 2024 13:59:44 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.74 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1722952786; cv=none; b=qmJG61Jx7zd4T3wy/zUAYes6PGPHpm9JoHSZBlNVaSqo7FwF3bqwQbtg2p4lLSXAzB2EjrYp3GyYqkFwjGWjpYbZbiZ/4BcMdknznP4/mFgnWgONMmhEiiL5yB6Ej2TCd/VcrcvktjTrJgssd6Nf2U5BjcHk1FVnRrZvKbpi1Hw= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1722952786; c=relaxed/simple; bh=c5AkhSVrQRDw1j8hEGOBc9pmNBbeQXlceVNzb/bliCA=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=Qql0IVNU3zZcNKCxdv+eCnE/nKVj5SsHj0WCwXGQlDmmPi0j5H6CnqqosyB1U3jxbK6E2LgtY2116ynK9JgZ4N4myaOfsuUDTXHd0A5Velc7EDpoIDyIwqdLjpGb+BXmcPlZi8KxdnFQSRHq3f3RMzXpknMDDSS/ehrRy+iTqzM= 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=eZMlbNUY; arc=none smtp.client-ip=209.85.128.74 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=flex--aliceryhl.bounces.google.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="eZMlbNUY" Received: by mail-wm1-f74.google.com with SMTP id 5b1f17b1804b1-4280b119a74so5270915e9.3 for ; Tue, 06 Aug 2024 06:59:43 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1722952782; x=1723557582; 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=F1Ky0L3ZI2Mg5QJNRJzDBJDO4ZesXRpUBFoGaK3+3Eg=; b=eZMlbNUYmL7tpQVqcuxnCoqme/z7tpwyuCcDhHAgBmmqc/KX0sgUST7aWV5P34ZO+i IHFCK/v11crxlX96R4jgQP0SeiCqqr0QB4ImLENQklve/j8vn19P0ZY11yswzuWE1V1o 0QjNZvi7F+zPex3SMhEzHs0n8hK1q5+w++z27+SGqXv1iJJtv52iMXymoJHGM/6aS52z 5GKTqYNj8/cDkuPr05G2bxnXa5hqY7lKxoyNhSn+BJuL+uodJ0DW45ez/4E2DhWbcCNu SanlzwDFiLeoXInNpNhx/w6L7j5qbhIrW3Z/SbVmUPJazXKFKBW6/yvP4rXVwuWzXI9C /fDg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1722952782; x=1723557582; 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=F1Ky0L3ZI2Mg5QJNRJzDBJDO4ZesXRpUBFoGaK3+3Eg=; b=WPBNUbJrX5zV8R14j3rwgwxT9J1Da3fZyhipbShRV5IWJBDXx0/I97wvunMN1egHon SRBu1+54bmxA0suFlvDoUERVi4OAjL0RH5natMLNS1kEaks3OwyBwyg053vtgoKx+Jpo OMq5/DTo90NhRn1rDYmuLyR6s9aLwNJKRffl1jvygXvNCW0PfVOZ39E6H01UbephNrwZ PyyewxP5aZZgLzgyyIlA6xNgrt7MXd12VHYD50ddsc9rIDN3pjWHUrXB5j97iQdZCS6p T1DmSdecSRHs6hsuIwCL65ZYgZidrfT4Hn1MUPL5GTiuBDSd/V0AJ8ahCDtoPOLewgh+ tjXQ== X-Forwarded-Encrypted: i=1; AJvYcCUbcYoMLMwOLGOpTm+l5C3liOOlOefmTksfoGJLz/s046C7sZ13wyVuaoU3jfDdWFkVNDUVYQnYt9WpWDG+fIwEouSQRtlDfxa6Oua4 X-Gm-Message-State: AOJu0YzvE42Ztm8QH4NYFQQKrUzC1Ny28AIEghQD0v65Ww0BQ0+0O2j2 ImnUp138hcctae/Kwc5p/LXt9mvrbwoHeGZTmP/o496lgifSGPwTyELHD130LoH7tV55O/oEONL /jz+DImM8eDI51A== X-Google-Smtp-Source: AGHT+IECMSWUY54BHOLVEZmRPMxOrJK1p/JvlEyZNu82fABMq8ZG3Oy9GqkyOgYW3BQgAkCML7RHwtIcGDkT4iQ= X-Received: from aliceryhl.c.googlers.com ([fda3:e722:ac3:cc00:28:9cb1:c0a8:35bd]) (user=aliceryhl job=sendgmr) by 2002:a05:600c:34d1:b0:427:b8e2:7b95 with SMTP id 5b1f17b1804b1-428e6ba2a80mr1929765e9.4.1722952782437; Tue, 06 Aug 2024 06:59:42 -0700 (PDT) Date: Tue, 06 Aug 2024 13:58:58 +0000 In-Reply-To: <20240806-linked-list-v4-0-23efc510ec92@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240806-linked-list-v4-0-23efc510ec92@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=19055; i=aliceryhl@google.com; h=from:subject:message-id; bh=c5AkhSVrQRDw1j8hEGOBc9pmNBbeQXlceVNzb/bliCA=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBmsiw6tVxKe1PQvKmO9afXUExDYeCOdF7WX/r2j 3ftzDzOUoWJAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCZrIsOgAKCRAEWL7uWMY5 Ro7wD/9XSPoxq/C+WHARG9XcP4+L8F5/CQFJ2lcvBNwZlB5aEiWbjVoLZcnhE6nowPiTkAHZFMZ p3WcO1jCoiQF5WkCs+X5Fuy6zirCsNfvoEj0w1gPKO6C59IBuCpAYVsUwqnO8NzIMAwJM8N+yV+ aDKHzPaO4N58bo2Pe7xKInuDqbU2KYPAQ/2FviMcmWjOGYJfg+eEg9j3ttqSySJKXkI2J7QRZcy jcg8vM/KsL9lzeDjd2YGdFLkV+ygtgmlzOJJfGtb13V21O41IdfUeqKPaZNQWgC54Ru2U5AtVgy 0Bf5sQb1S0MEizM4h93f5MGgSjK5pAlYmIqA1PzesQHD4LZedEC1P5G63aPIyj5nSEYZRm1Guh9 9gnco+BhCWOS82v16lOdkTQyWy9i90nlZd1Svhx+TK70rnwv5T4KgWt47AkSKTPSLHcFhXxSfmw qoNRS069HK4nkFMkbrxnh/X6Mb1Cu0evpRJJLbevQue7KYbGvx9JTDX4YHiPyVsEAPfTVkky7Kt +pLZcRGkY0Lgpb4WcsNPhjdWog6fm2ZGBg4djmHmlep9MyNzLSEvsJW9ukUsW9Whb2Qb9UZigpR csd5UOB6SFsqZMYVGilku/Q5YBuNBMy5XRiQr4/q0u/QVbHK7BFa2nnycb4M1tvn7OJAfFJ4HhM bItTYfUmnp0bXwQ== X-Mailer: b4 0.13.0 Message-ID: <20240806-linked-list-v4-6-23efc510ec92@google.com> Subject: [PATCH v4 06/10] 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 , Coly Li , Paolo Abeni , Pierre Gondois , Ingo Molnar , Jakub Kicinski , Wei Yang , Matthew Wilcox , linux-kernel@vger.kernel.org, rust-for-linux@vger.kernel.org, Alice Ryhl , Kees Cook Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Add the 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.) A future patch in this series will introduce support for cursors that can be used to remove arbitrary items without unsafe code. Signed-off-by: Alice Ryhl Reviewed-by: Benno Lossin --- rust/kernel/list.rs | 330 ++++++++++++++++++++++++++++++++++++++++++++= +++- rust/kernel/list/arc.rs | 6 +- 2 files changed, 331 insertions(+), 5 deletions(-) diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs index 670d53989b8f..551c46a2401b 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; @@ -14,7 +15,42 @@ mod arc; pub use self::arc::{impl_list_arc_safe, AtomicTracker, ListArc, ListArcSaf= e, TryNewListArc}; =20 -/// Implemented by types where a [`ListArc`] can be inserted into a = `List`. +/// A linked list. +/// +/// All elements in this linked list will be [`ListArc`] references to the= value. Since a value can +/// only have one `ListArc` (for each pair of prev/next pointers), this en= sures that the same +/// prev/next pointers are not used for several linked lists. +/// +/// # Invariants +/// +/// * If the list is empty, then `first` is null. Otherwise, `first` point= s at the `ListLinks` +/// field of the first element in the list. +/// * All prev/next pointers in `ListLinks` fields of items in the list ar= e valid and form a cycle. +/// * For every item in the list, the list owns the associated [`ListArc`]= reference and has +/// exclusive access to the `ListLinks` field. +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 +92,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 +139,6 @@ struct ListLinksFields { pub struct ListLinks { // This type is `!Unpin` for aliasing reasons as the pointers are part= of an intrusive linked // list. - #[allow(dead_code)] inner: Opaque, } =20 @@ -127,4 +162,293 @@ pub fn new() -> impl PinInit { }), } } + + /// # Safety + /// + /// `me` must be dereferencable. + #[inline] + unsafe fn fields(me: *mut Self) -> *mut ListLinksFields { + // SAFETY: The caller promises that the pointer is valid. + unsafe { Opaque::raw_get(ptr::addr_of!((*me).inner)) } + } + + /// # Safety + /// + /// `me` must be dereferencable. + #[inline] + unsafe fn from_fields(me: *mut ListLinksFields) -> *mut Self { + me.cast() + } +} + +impl, const ID: u64> List { + /// Creates a new empty list. + pub const fn new() -> Self { + Self { + first: ptr::null_mut(), + _ty: PhantomData, + } + } + + /// Returns whether this list is empty. + pub fn is_empty(&self) -> bool { + self.first.is_null() + } + + /// Add the provided item to the back of the list. + pub fn push_back(&mut self, item: ListArc) { + let raw_item =3D ListArc::into_raw(item); + // SAFETY: + // * We just got `raw_item` from a `ListArc`, so it's in an `Arc`. + // * Since we have ownership of the `ListArc`, `post_remove` must = have been called after + // the most recent call to `prepare_to_insert`, if any. + // * We own the `ListArc`. + // * Removing items from this list is always done using `remove_in= ternal_inner`, which + // calls `post_remove` before giving up ownership. + let list_links =3D unsafe { T::prepare_to_insert(raw_item) }; + // SAFETY: We have not yet called `post_remove`, so `list_links` i= s still valid. + let item =3D unsafe { ListLinks::fields(list_links) }; + + if self.first.is_null() { + self.first =3D item; + // SAFETY: The caller just gave us ownership of these fields. + // INVARIANT: A linked list with one item should be cyclic. + unsafe { + (*item).next =3D item; + (*item).prev =3D item; + } + } else { + let next =3D self.first; + // SAFETY: By the type invariant, this pointer is valid or nul= l. We just checked that + // it's not null, so it must be valid. + let prev =3D unsafe { (*next).prev }; + // SAFETY: Pointers in a linked list are never dangling, and t= he caller just gave us + // ownership of the fields on `item`. + // INVARIANT: This correctly inserts `item` between `prev` and= `next`. + unsafe { + (*item).next =3D next; + (*item).prev =3D prev; + (*prev).next =3D item; + (*next).prev =3D item; + } + } + } + + /// Add the provided item to the front of the list. + pub fn push_front(&mut self, item: ListArc) { + let raw_item =3D ListArc::into_raw(item); + // SAFETY: + // * We just got `raw_item` from a `ListArc`, so it's in an `Arc`. + // * If this requirement is violated, then the previous caller of = `prepare_to_insert` + // violated the safety requirement that they can't give up owner= ship of the `ListArc` + // until they call `post_remove`. + // * We own the `ListArc`. + // * Removing items] from this list is always done using `remove_i= nternal_inner`, which + // calls `post_remove` before giving up ownership. + let list_links =3D unsafe { T::prepare_to_insert(raw_item) }; + // SAFETY: We have not yet called `post_remove`, so `list_links` i= s still valid. + let item =3D unsafe { ListLinks::fields(list_links) }; + + if self.first.is_null() { + // SAFETY: The caller just gave us ownership of these fields. + // INVARIANT: A linked list with one item should be cyclic. + unsafe { + (*item).next =3D item; + (*item).prev =3D item; + } + } else { + let next =3D self.first; + // SAFETY: We just checked that `next` is non-null. + let prev =3D unsafe { (*next).prev }; + // SAFETY: Pointers in a linked list are never dangling, and t= he caller just gave us + // ownership of the fields on `item`. + // INVARIANT: This correctly inserts `item` between `prev` and= `next`. + unsafe { + (*item).next =3D next; + (*item).prev =3D prev; + (*prev).next =3D item; + (*next).prev =3D item; + } + } + self.first =3D item; + } + + /// Removes the last item from this list. + pub fn pop_back(&mut self) -> Option> { + if self.first.is_null() { + return None; + } + + // SAFETY: We just checked that the list is not empty. + let last =3D unsafe { (*self.first).prev }; + // SAFETY: The last item of this list is in this list. + Some(unsafe { self.remove_internal(last) }) + } + + /// Removes the first item from this list. + pub fn pop_front(&mut self) -> Option> { + if self.first.is_null() { + return None; + } + + // SAFETY: The first item of this list is in this list. + Some(unsafe { self.remove_internal(self.first) }) + } + + /// Removes the provided item from this list and returns it. + /// + /// This returns `None` if the item is not in the list. (Note that by = the safety requirements, + /// this means that the item is not in any list.) + /// + /// # Safety + /// + /// `item` must not be in a different linked list (with the same id). + pub unsafe fn remove(&mut self, item: &T) -> Option> { + let mut item =3D unsafe { ListLinks::fields(T::view_links(item)) }; + // SAFETY: The user provided a reference, and reference are never = dangling. + // + // As for why this is not a data race, there are two cases: + // + // * If `item` is not in any list, then these fields are read-onl= y and null. + // * If `item` is in this list, then we have exclusive access to = these fields since we + // have a mutable reference to the list. + // + // In either case, there's no race. + let ListLinksFields { next, prev } =3D unsafe { *item }; + + debug_assert_eq!(next.is_null(), prev.is_null()); + if !next.is_null() { + // This is really a no-op, but this ensures that `item` is a r= aw pointer that was + // obtained without going through a pointer->reference->pointe= r conversion rountrip. + // This ensures that the list is valid under the more restrict= ive strict provenance + // ruleset. + // + // SAFETY: We just checked that `next` is not null, and it's n= ot dangling by the + // list invariants. + unsafe { + debug_assert_eq!(item, (*next).prev); + item =3D (*next).prev; + } + + // SAFETY: We just checked that `item` is in a list, so the ca= ller guarantees that it + // is in this list. The pointers are in the right order. + Some(unsafe { self.remove_internal_inner(item, next, prev) }) + } else { + None + } + } + + /// Removes the provided item from the list. + /// + /// # Safety + /// + /// `item` must point at an item in this list. + unsafe fn remove_internal(&mut self, item: *mut ListLinksFields) -> Li= stArc { + // SAFETY: The caller promises that this pointer is not dangling, = and there's no data race + // since we have a mutable reference to the list containing `item`. + let ListLinksFields { next, prev } =3D unsafe { *item }; + // SAFETY: The pointers are ok and in the right order. + unsafe { self.remove_internal_inner(item, next, prev) } + } + + /// Removes the provided item from the list. + /// + /// # Safety + /// + /// The `item` pointer must point at an item in this list, and we must= have `(*item).next =3D=3D + /// next` and `(*item).prev =3D=3D prev`. + unsafe fn remove_internal_inner( + &mut self, + item: *mut ListLinksFields, + next: *mut ListLinksFields, + prev: *mut ListLinksFields, + ) -> ListArc { + // SAFETY: We have exclusive access to the pointers of items in th= e list, and the prev/next + // pointers are always valid for items in a list. + // + // INVARIANT: There are three cases: + // * If the list has at least three items, then after removing th= e item, `prev` and `next` + // will be next to each other. + // * If the list has two items, then the remaining item will poin= t at itself. + // * If the list has one item, then `next =3D=3D prev =3D=3D item= `, so these writes have no + // effect. The list remains unchanged and `item` is still in th= e list for now. + unsafe { + (*next).prev =3D prev; + (*prev).next =3D next; + } + // SAFETY: We have exclusive access to items in the list. + // INVARIANT: `item` is being removed, so the pointers should be n= ull. + unsafe { + (*item).prev =3D ptr::null_mut(); + (*item).next =3D ptr::null_mut(); + } + // INVARIANT: There are three cases: + // * If `item` was not the first item, then `self.first` should r= emain unchanged. + // * If `item` was the first item and there is another item, then= we just updated + // `prev->next` to `next`, which is the new first item, and set= ting `item->next` to null + // did not modify `prev->next`. + // * If `item` was the only item in the list, then `prev =3D=3D i= tem`, and we just set + // `item->next` to null, so this correctly sets `first` to null= now that the list is + // empty. + if self.first =3D=3D item { + // SAFETY: The `prev` pointer is the value that `item->prev` h= ad when it was in this + // list, so it must be valid. There is no race since `prev` is= still in the list and we + // still have exclusive access to the list. + self.first =3D unsafe { (*prev).next }; + } + + // SAFETY: `item` used to be in the list, so it is dereferencable = by the type invariants + // of `List`. + let list_links =3D unsafe { ListLinks::from_fields(item) }; + // SAFETY: Any pointer in the list originates from a `prepare_to_i= nsert` call. + let raw_item =3D unsafe { T::post_remove(list_links) }; + // SAFETY: The above call to `post_remove` guarantees that we can = recreate the `ListArc`. + unsafe { ListArc::from_raw(raw_item) } + } + + /// Moves all items from `other` into `self`. + /// + /// The items of `other` are added to the back of `self`, so the last = item of `other` becomes + /// the last item of `self`. + pub fn push_all_back(&mut self, other: &mut List) { + // First, we insert the elements into `self`. At the end, we make = `other` empty. + if self.is_empty() { + // INVARIANT: All of the elements in `other` become elements o= f `self`. + self.first =3D other.first; + } else if !other.is_empty() { + let other_first =3D other.first; + // SAFETY: The other list is not empty, so this pointer is val= id. + let other_last =3D unsafe { (*other_first).prev }; + let self_first =3D self.first; + // SAFETY: The self list is not empty, so this pointer is vali= d. + let self_last =3D unsafe { (*self_first).prev }; + + // SAFETY: We have exclusive access to both lists, so we can u= pdate the pointers. + // INVARIANT: This correctly sets the pointers to merge both l= ists. We do not need to + // update `self.first` because the first element of `self` doe= s not change. + unsafe { + (*self_first).prev =3D other_last; + (*other_last).next =3D self_first; + (*self_last).next =3D other_first; + (*other_first).prev =3D self_last; + } + } + + // INVARIANT: The other list is now empty, so update its pointer. + other.first =3D ptr::null_mut(); + } +} + +impl, const ID: u64> Default for List { + fn default() -> Self { + List::new() + } +} + +impl, const ID: u64> Drop for List { + fn drop(&mut self) { + while let Some(item) =3D self.pop_front() { + drop(item); + } + } } diff --git a/rust/kernel/list/arc.rs b/rust/kernel/list/arc.rs index c5921a7d5966..d801b9dc6291 100644 --- a/rust/kernel/list/arc.rs +++ b/rust/kernel/list/arc.rs @@ -133,8 +133,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 @@ -156,6 +156,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.46.0.rc2.264.g509ed76dc8-goog From nobody Fri Dec 19 19:07:43 2025 Received: from mail-wm1-f74.google.com (mail-wm1-f74.google.com [209.85.128.74]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 863BB1EB49E for ; Tue, 6 Aug 2024 13:59:46 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.74 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1722952789; cv=none; b=oYt6mM/wihzQKsuCj+A0NVqH6taDVNsIVNfkTWSP+o98mj05HIJ1oN6gqydU/Udzd61/IjYTE+W+gt8OPFiZx4aWTuC0DMxcDTSh4OKI9Z87TpahpSqEprwOOxD2wwpMBWopj7v8vurxJazSsOvdeQkB2T0h7oWod6/F37C+s3g= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1722952789; c=relaxed/simple; bh=5Auobud/qkfPgqEK9dIDGdnYH2b2+TiVd76QFukYtuo=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=MLunIek8OrAOgvpB8XCle+CwsAS2J7Qojogs2a6wNG8EjiKjoPCrH4hOiQ0z2dPihqgVcspJtIBTFjC/dJ86HcJ9R2EJ+eTSyzTXJq4nCFAVCb4AVNvxuRuNhYkBLfRWkqg7j+zz5ZMnXdHw8ox79Kb5zQs3l169SgD5Htun0EI= 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=hE2xQx4s; arc=none smtp.client-ip=209.85.128.74 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=flex--aliceryhl.bounces.google.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="hE2xQx4s" Received: by mail-wm1-f74.google.com with SMTP id 5b1f17b1804b1-4280d8e685eso5704015e9.1 for ; Tue, 06 Aug 2024 06:59:46 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1722952785; x=1723557585; 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=mBtLq8vMW6E0NPD2YscCzJYeLwsvhgk+uQjC+zS8n/A=; b=hE2xQx4sIRttx0tPcfu8GAShAcHEStbeUykwcTns2QeKFj1n48rvfc5DAO0za087oG UcCKpdGs0adhmT8mCt3EV/vkG0c27Bxw48KNi2ddbkesdHfwxjvSHPzMEyzS2UPijJlx vA3QJxEpAQHboslORuPNKqcNOLfTIjc9ZDywYrnsShKtRhJZ0/Jr2Gxz+tJWfDWGj/oK i7EmZSTpzQP3lczVnpoJbye7nD0eu/mqh3qHLlnLkBDjw5DQvRwwbNRgj3ZHuwROve+t pZDljORFqEcbe+zwQX2GNP77GyR1d/2xxfqXmuU8EYOUpYubP5TWC59lonBcDzCNjlpP U7AQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1722952785; x=1723557585; 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=mBtLq8vMW6E0NPD2YscCzJYeLwsvhgk+uQjC+zS8n/A=; b=uzLQVs+khi9ZpqJU+ks4jIO3K6HGcuR7H820+vlAn16oFRfJg8FMWy+1jZkwsrP4n4 19QKOZBD2Pnn98wZWnMkWgcNBt+ViAKRjvm/aSvFPLunGHDtM4TmI3WFQymNxsLUyevx V6YUEpFSDvIdYdWCVYrgkJZOspiEeSLatdyqKNWDRVlDeY616UvDrzotBpHrA/1ThGIM J4LQI02ZlQEoj+B7pPTE6KgZqJ50qI8EDf/D8swpYhItM2EZ1zN/IlyNAwXgpXUX9q1F G/Gpch9e0NWaG3k8A6G8JOSPF2AQKqXogqyVtXUbeqqC/iCTPp3dEbkDvCLD9cEivXvO RNCQ== X-Forwarded-Encrypted: i=1; AJvYcCXt1dKgZeuOKeEhO7r3/qmDwzjqEKvwT6veZpvC5hqgWboazFaan/M9/pNe+LL3CDElpiWF5f2nki3Hpb1LiOMC77UeLj688+CA318h X-Gm-Message-State: AOJu0Yxoky5kOAM23xb289NJojhj1ZBbH35Zs3qQic1fn8jKDQ2aCM10 oF61gmklEaCVsW4/7Ez0AttIH6YIWzjIou13fmNyms14ytQRmWzNVk8SNYOO7Q5jyO/MMt7zXx2 3WxIjnJw9WhKXUQ== X-Google-Smtp-Source: AGHT+IFEqJ0FlEIEvxMSETiYqlJJ0W522Nh4qV0BfqtWSXzyR9SKwiyAjstR3yqNxweYjHzyIs8dujHwU7UEhh4= X-Received: from aliceryhl.c.googlers.com ([fda3:e722:ac3:cc00:28:9cb1:c0a8:35bd]) (user=aliceryhl job=sendgmr) by 2002:a05:600c:6986:b0:424:a3d1:bdc5 with SMTP id 5b1f17b1804b1-428e6a603a4mr651055e9.0.1722952784877; Tue, 06 Aug 2024 06:59:44 -0700 (PDT) Date: Tue, 06 Aug 2024 13:58:59 +0000 In-Reply-To: <20240806-linked-list-v4-0-23efc510ec92@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240806-linked-list-v4-0-23efc510ec92@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=5030; i=aliceryhl@google.com; h=from:subject:message-id; bh=5Auobud/qkfPgqEK9dIDGdnYH2b2+TiVd76QFukYtuo=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBmsiw7FowwYrZejcypbzdQRWrZDJ2Ax/ZGPWDpJ Qipg8CgP5SJAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCZrIsOwAKCRAEWL7uWMY5 Rn6fD/4qX5qT6tv/rYHGx4RP6YWw0w8sZR44fApGeEeHWpXtRigu0T1OvVbFCZUBAy/rPOpa+CF kBple4Bk0B7EoOXu05JfFWU+WAIPPb6kMFRUqXJZ58LViN2tFoRSPjW5e2WEqpJh5JL0iCypaSs CDnF02W4KE1GnWwOBrQ7taTGm5U69NAgqvKDdKJ9UFcOgQc8osbqulMRP3wGiidcroV2u6SuJDm Nczfm0yTwmLVmT9pOsVw8tR6ZeK0CIozQkn+TZBs7qmfsBeb+efhz/TKxnNj1NuFc0l7qaJGtI4 YcaelbKk2MpiaAG+i8k5Nfx2NyUxmNuq1y08VpcS7V1okVMxTS5e8lS6Zme4zQlf2G5esiQHHNM TqsgA+BebfDFT0ObUhH71yZzDABmkQ3Yn633zYmkwTLyBB+iCzPcDmSwWsb2DNX+SQNK8xCaX7k ydN7RpprqLpCkrg/KXMraHy553zMzGLoXXU5KXZj2brOR/ytT1HUhhQEFpduCHJHIJX/BP+UgJV xRiTouCNDmO9GCH3YSgtVQ+2yfmaupc8DLk21g5OZfRPDayll8mUCNy3l5oLSZn7bYhzNzJd03M ZgWXlWduCrV370Zo3QXezg+yx44hwOhTwhREmnH2vfUNUIquNtoECYO8hJ6kIaNI1CUPeXulyfg 4IVyAlEANyb/Dag== X-Mailer: b4 0.13.0 Message-ID: <20240806-linked-list-v4-7-23efc510ec92@google.com> Subject: [PATCH v4 07/10] 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 , Coly Li , Paolo Abeni , Pierre Gondois , Ingo Molnar , Jakub Kicinski , Wei Yang , Matthew Wilcox , linux-kernel@vger.kernel.org, rust-for-linux@vger.kernel.org, Alice Ryhl , Kees Cook Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Rust Binder has lists containing stuff such as all contexts or all processes, and sometimes needs 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. Reviewed-by: Benno Lossin 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 551c46a2401b..0d680156b8b1 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 @@ -437,6 +439,17 @@ pub fn push_all_back(&mut self, other: &mut List) { // INVARIANT: The other list is now empty, so update its pointer. other.first =3D ptr::null_mut(); } + + /// Creates an iterator over the list. + pub fn iter(&self) -> Iter<'_, T, ID> { + // INVARIANT: If the list is empty, both pointers are null. Otherw= ise, both pointers point + // at the first element of the same list. + Iter { + current: self.first, + stop: self.first, + _ty: PhantomData, + } + } } =20 impl, const ID: u64> Default for List { @@ -452,3 +465,92 @@ fn drop(&mut self) { } } } + +/// An iterator over a [`List`]. +/// +/// # Invariants +/// +/// * There must be a [`List`] that is immutably borrowed for the duration= of `'a`. +/// * The `current` pointer is null or points at a value in that [`List`]. +/// * The `stop` pointer is equal to the `first` field of that [`List`]. +#[derive(Clone)] +pub struct Iter<'a, T: ?Sized + ListItem, const ID: u64 =3D 0> { + current: *mut ListLinksFields, + stop: *mut ListLinksFields, + _ty: PhantomData<&'a ListArc>, +} + +impl<'a, T: ?Sized + ListItem, const ID: u64> Iterator for Iter<'a, T,= ID> { + type Item =3D ArcBorrow<'a, T>; + + fn next(&mut self) -> Option> { + if self.current.is_null() { + return None; + } + + let current =3D self.current; + + // SAFETY: We just checked that `current` is not null, so it is in= a list, and hence not + // dangling. There's no race because the iterator holds an immutab= le borrow to the list. + let next =3D unsafe { (*current).next }; + // INVARIANT: If `current` was the last element of the list, then = this updates it to null. + // Otherwise, we update it to the next element. + self.current =3D if next !=3D self.stop { + next + } else { + ptr::null_mut() + }; + + // SAFETY: The `current` pointer points at a value in the list. + let item =3D unsafe { T::view_value(ListLinks::from_fields(current= )) }; + // SAFETY: + // * All values in a list are stored in an `Arc`. + // * The value cannot be removed from the list for the duration of= the lifetime annotated + // on the returned `ArcBorrow`, because removing it from the lis= t would require mutable + // access to the list. However, the `ArcBorrow` is annotated wit= h the iterator's + // lifetime, and the list is immutably borrowed for that lifetim= e. + // * Values in a list never have a `UniqueArc` reference. + Some(unsafe { ArcBorrow::from_raw(item) }) + } +} + +impl<'a, T: ?Sized + ListItem, const ID: u64> FusedIterator for Iter<'= a, T, ID> {} + +impl<'a, T: ?Sized + ListItem, const ID: u64> IntoIterator for &'a Lis= t { + type IntoIter =3D Iter<'a, T, ID>; + type Item =3D ArcBorrow<'a, T>; + + fn into_iter(self) -> Iter<'a, T, ID> { + self.iter() + } +} + +/// An owning iterator into a [`List`]. +pub struct IntoIter, const ID: u64 =3D 0> { + list: List, +} + +impl, const ID: u64> Iterator for IntoIter= { + type Item =3D ListArc; + + fn next(&mut self) -> Option> { + self.list.pop_front() + } +} + +impl, const ID: u64> FusedIterator for IntoIter {} + +impl, const ID: u64> DoubleEndedIterator for Into= Iter { + fn next_back(&mut self) -> Option> { + self.list.pop_back() + } +} + +impl, const ID: u64> IntoIterator for List= { + type IntoIter =3D IntoIter; + type Item =3D ListArc; + + fn into_iter(self) -> IntoIter { + IntoIter { list: self } + } +} --=20 2.46.0.rc2.264.g509ed76dc8-goog From nobody Fri Dec 19 19:07:43 2025 Received: from mail-wr1-f73.google.com (mail-wr1-f73.google.com [209.85.221.73]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 32DF721C168 for ; Tue, 6 Aug 2024 13:59:49 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.221.73 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1722952791; cv=none; b=PtuGMhpF94vmQffHwwBcCl3X0CVCAd1I1XIluXMcL1hzZ1ueMzA+6TLXT4Kaa3PU93+DDHPRkSqzTQlTvdafZY+C0Mfq61QWPFpylFCH3Dk0TiziUhg32HhsLHEUqNPKU2I4cnQKLgmJGPVTEDmOP7XhoGf4QVYKzOriUQdmk2U= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1722952791; c=relaxed/simple; bh=U1OnWrBrlP25BFBpzAVCMr4UKIx3mPzoMhcGTN/whpk=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=FHZgzCOVoDWU+cN6eXu3v6MWWAmOfnx1vSz3llpcwXaiMFrBSK0p4WsxzWGIGGBbZXNEDc/I5jsiJUhkZko5wxHSeRoomutmkm+8QJdWj1dkR3DgKwJsXlIEqe/wxWUyNSNrJrc88r6KQweFZoxXEgsVNQF/oROR0toQfdXzzqM= 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=kM/xj0Fz; arc=none smtp.client-ip=209.85.221.73 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=flex--aliceryhl.bounces.google.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="kM/xj0Fz" Received: by mail-wr1-f73.google.com with SMTP id ffacd0b85a97d-3685bbd6dfbso401008f8f.0 for ; Tue, 06 Aug 2024 06:59:48 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1722952787; x=1723557587; 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=JZA3G4fqGlTDhQpwTk3AIW/gAya/39uBmQnmVK3DEuM=; b=kM/xj0FzW7fPFD62FlnNCDSEoOI6Xdm+nriltfgIEU40rDJqAUHdV7h4CzC6UjfQE6 tcovJNvxY6aVELpuOb5yJY9/fVVvMwPLofQw/s4jP6QLuJqd+5dx0b5ctiw0jmQycMB1 97knkNfHNgu8v5uvMx9bmteoJB+pK2t6J3AwMLnjT+8tlW/cnFyiLW6oRfEQVY6GAC1B AMEW1ygG760ZDaSdwJxh/X+CkOaKJNvjQnk3iDAxZNl3ucwOk1g8JXMPwAj4YZ/8sLYr Mz/ZFZBQEUAMhrTKK0WGdMdxnLYDS4AGCGXn8lO11O/U8NOeZi1Vk9FDD/C37HmR5EdV 0FWQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1722952787; x=1723557587; 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=JZA3G4fqGlTDhQpwTk3AIW/gAya/39uBmQnmVK3DEuM=; b=D6dIjamHuTy8Ad+nO1lgEdYtB6Ex9QvMKVeBEsP237jj/W45oLRCIQOf9Xx1G98Fko q/h0IasdY+TJIQrZ8xWNIuYNj+Iiv1jLGPn3bxP0DHuWuoCu+coplY7QbqpPQ+TIXcV/ 9e5tTBBWKr5TAKdnQ3tYKe0hdLb5amdQ9SqPi7gnGTiz2Wmdg65gk0RaY9srZ5GH6450 WH9JI77oow7X0FZ08utrffXuT9oYiGqz4qcFN1y08DQkBLyBpjadeRLiAzPDOZ47KrVk hyPF+UYamrR1l0sXA/aq3ow6gnfgQlnWyKfNHydW0ZWSLDuIr8F6ca4j3tg1c0+bxEv0 Mieg== X-Forwarded-Encrypted: i=1; AJvYcCVg/cYnlXX81jzcP9NH17xFUDkUj7waE/DGI7ecj0paiDV8c9YnJohf8LCqH3iQvd0abkUUD2K7P7F6jnpx3l5DNcNb/CWP5si8lSne X-Gm-Message-State: AOJu0YwRl0Y1EcNK3meq4bFb1R8xEyzadHknw+D09f8Em6M7o/MeOeBt CoktezQuvGtYXEOi2q6k5kXqeJJuNI2o87g4Eeivv97FXm53boq/q5RFevk3NIe8p5R5inWgTYz 5tazF57GbGwuZaw== X-Google-Smtp-Source: AGHT+IFUqpa4kYAE0Jai9LGsZ0iw7NZR2G2lA87l7DR81DoK1l123eiFEiwOmx62rjwtr4W8x+V71Okc703Z0nc= X-Received: from aliceryhl.c.googlers.com ([fda3:e722:ac3:cc00:28:9cb1:c0a8:35bd]) (user=aliceryhl job=sendgmr) by 2002:a05:6000:d91:b0:366:e9fa:36e with SMTP id ffacd0b85a97d-36bbc189d6cmr19674f8f.10.1722952787295; Tue, 06 Aug 2024 06:59:47 -0700 (PDT) Date: Tue, 06 Aug 2024 13:59:00 +0000 In-Reply-To: <20240806-linked-list-v4-0-23efc510ec92@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240806-linked-list-v4-0-23efc510ec92@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=5338; i=aliceryhl@google.com; h=from:subject:message-id; bh=U1OnWrBrlP25BFBpzAVCMr4UKIx3mPzoMhcGTN/whpk=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBmsiw7q/7R3ylIYLWLyhQ0XS4gH2HMmHo5fhP7t gxuqwODVoeJAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCZrIsOwAKCRAEWL7uWMY5 RjaEEACX6cOLmwlkrkiRLI3de7L2WvmTFxaR2EO3aLbIt+2BXuKyjikAESx3gX00+bqSGdO9INF 3gl6+2zERiaD9v/wVpktV45bSQNEfT+cmGxU883lU6mTYwd6XKxIfwtIvsyDnMCqsOKtov1zFXP GBM7XAKs8RVfTZv/4hzIo7WG+zp81Y6xRi99/Z9C4yzffrQ+BET+IlssD3eaIzwZFbxDmYE35VJ 1eH6WsU6cyVsnfbqZxkio+Wkfsd1SlB3IPs8/FiJjQy4NEutHCoq43KPcrRoDQeMk962OmzU5b/ DS5UwUrAjJ1qcM20g6Nuls5DA+hjWP8GnHeJudq6Tx3WHMud3OLw8qCflWBPdxUKBBCqI/BWAVW XZMfUYgFgce9XnGc5kfVqBZkkT50t5NCTPU6oYdb0IP1ywmPlHHFZTwaKlmoE1x58Gu3qHDtpIT ksjDl+EdgUZwUPYcJusw18taaktSy3cGkI0tORjkatxPsg/zvZbIt/NdyTpFpqhC3b558xMRiSZ 2oYdM1y5cDPhf4ifBgA8IqtqjObEVufHrjdzACMQ8P4nzf9VxIBDsquOFCG2yndyybC0a+TdCbc ogQF9KBOwY6gwLeIZ0Y4ek8VTjsaNT1PE/+uDtPHSG+1AzsA2PWFOD4TnMGzk3rCOHtFMB80r/B cRqyBJP6oGfCphw== X-Mailer: b4 0.13.0 Message-ID: <20240806-linked-list-v4-8-23efc510ec92@google.com> Subject: [PATCH v4 08/10] 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 , Coly Li , Paolo Abeni , Pierre Gondois , Ingo Molnar , Jakub Kicinski , Wei Yang , Matthew Wilcox , linux-kernel@vger.kernel.org, rust-for-linux@vger.kernel.org, Alice Ryhl , Kees Cook Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable 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. Reviewed-by: Benno Lossin Signed-off-by: Alice Ryhl --- rust/kernel/list.rs | 82 +++++++++++++++++++++++++++++++++++++++++++++++++= ++++ 1 file changed, 82 insertions(+) diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs index 0d680156b8b1..904cfa454dff 100644 --- a/rust/kernel/list.rs +++ b/rust/kernel/list.rs @@ -440,6 +440,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 @@ -514,6 +528,74 @@ fn next(&mut self) -> Option> { } } =20 +/// A cursor into a [`List`]. +/// +/// # Invariants +/// +/// The `current` pointer points a value in `list`. +pub struct Cursor<'a, T: ?Sized + ListItem, const ID: u64 =3D 0> { + current: *mut ListLinksFields, + list: &'a mut List, +} + +impl<'a, T: ?Sized + ListItem, const ID: u64> Cursor<'a, T, ID> { + /// Access the current element of this cursor. + pub fn current(&self) -> ArcBorrow<'_, T> { + // SAFETY: The `current` pointer points a value in the list. + let me =3D unsafe { T::view_value(ListLinks::from_fields(self.curr= ent)) }; + // SAFETY: + // * All values in a list are stored in an `Arc`. + // * The value cannot be removed from the list for the duration of= the lifetime annotated + // on the returned `ArcBorrow`, because removing it from the lis= t would require mutable + // access to the cursor or the list. However, the `ArcBorrow` ho= lds an immutable borrow + // on the cursor, which in turn holds a mutable borrow on the li= st, so any such + // mutable access requires first releasing the immutable borrow = on the cursor. + // * Values in a list never have a `UniqueArc` reference, because = the list has a `ListArc` + // reference, and `UniqueArc` references must be unique. + unsafe { ArcBorrow::from_raw(me) } + } + + /// Move the cursor to the next element. + pub fn next(self) -> Option> { + // SAFETY: The `current` field is always in a list. + let next =3D unsafe { (*self.current).next }; + + if next =3D=3D self.list.first { + None + } else { + // INVARIANT: Since `self.current` is in the `list`, its `next= ` pointer is also in the + // `list`. + Some(Cursor { + current: next, + list: self.list, + }) + } + } + + /// Move the cursor to the previous element. + pub fn prev(self) -> Option> { + // SAFETY: The `current` field is always in a list. + let prev =3D unsafe { (*self.current).prev }; + + if self.current =3D=3D self.list.first { + None + } else { + // INVARIANT: Since `self.current` is in the `list`, its `prev= ` pointer is also in the + // `list`. + Some(Cursor { + current: prev, + list: self.list, + }) + } + } + + /// Remove the current element from the list. + pub fn remove(self) -> ListArc { + // SAFETY: The `current` pointer always points at a member of the = list. + unsafe { self.list.remove_internal(self.current) } + } +} + impl<'a, T: ?Sized + ListItem, const ID: u64> FusedIterator for Iter<'= a, T, ID> {} =20 impl<'a, T: ?Sized + ListItem, const ID: u64> IntoIterator for &'a Lis= t { --=20 2.46.0.rc2.264.g509ed76dc8-goog From nobody Fri Dec 19 19:07:43 2025 Received: from mail-wm1-f74.google.com (mail-wm1-f74.google.com [209.85.128.74]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 42F4A21C198 for ; Tue, 6 Aug 2024 13:59:51 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=209.85.128.74 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1722952793; cv=none; b=BCe05XNA43+e3y4vlpJTLvrkBeE2ZrVEGgeGr2ekrYkoySR/Qy1iNJUzSrprfxEiEHwKDmIuDlubaydZhQKLIGGQskQ6xPAhRuY9Gkei/oNcTQInyqPWU84Xw8eXxyp0MtetjjQ800mw6NwQ5VOi1nZtJtDUwlLL89HqmF+OqLY= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1722952793; c=relaxed/simple; bh=DWn7jfpTLBRlhpcytJudwcfEhzJZIMi+Im52RQQpm8o=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=DP2f0ef7mhz5xak6REhYfso6YuCKjTjN1qgQ3GB5CqIrAXS9rAT3nopeOiNPIs0xNna1DiUBj1voihgxEYG+nHq//mAHP0XdXgreT2/xFcmI/AsX0GPQH/i8xIXWjUJiB4II53UEHv7KSobXn2IStY3e0NuoFK7QT3W+7b47xes= 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=ELLNBUG+; arc=none smtp.client-ip=209.85.128.74 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=reject dis=none) header.from=google.com Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=flex--aliceryhl.bounces.google.com Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=google.com header.i=@google.com header.b="ELLNBUG+" Received: by mail-wm1-f74.google.com with SMTP id 5b1f17b1804b1-4281b7196bbso5798315e9.0 for ; Tue, 06 Aug 2024 06:59:51 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1722952790; x=1723557590; 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=ZGFrtitg8gPy3R8NAtg653rpOeRPL0RQ8pJtbADQFYM=; b=ELLNBUG+wuWd1BmEEO6J3HmDv2z9cYb5LN6RaqUis7oS3gSNPtnWYlPC4osAlibPJ5 e9MjRKm8evuMpSd+mS+P+NY4n2eyRIrqajz4EK3zacCEmhSnFMIZBTOcOlH2vooFCxXp LZpekx8WvrW1gowzGAZsuvQzymuCqFm03uAlCDyL2cJGxLb80F03Q0qwK7AiApKUWmot 2kirp7dTJzoMlZo53XMm6iFBTHzoHVnC+VyJhFPrZFKOCxki8ackmFjlmpgMRs6jQP8w Acl35CAfCi+LkaE6wgj+H3avwWPFWy0DplYyCMN2rdtrVRGlvPzciGC745rmZ3a6qs5T k28w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1722952790; x=1723557590; 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=ZGFrtitg8gPy3R8NAtg653rpOeRPL0RQ8pJtbADQFYM=; b=MbMypM+MrDk5MVvBvdr+JBRqpdfiYU5Who0/6T7kMJ1UeuJCTaTmborkRFbYeZdec8 a0aEP9yeYQP+3KcUzEhnKEcH9kyXtMjzNXv62enAW04Mi+maNWSechlBc4uzE5OeaV7L HU1GyL32HO6RoOptViLQX83u6p0b9T6mGL/w23ap0dzpz0kBQFvEbvYNLHU5WgDaKkOz SXL9k1YNoRHztw9AEW+3dYXHIJ/FbTiMdBAdYaH4DcgxseAV966kCdbthwU242GG26EM aKnRKYC0K+X7DMYpkuMh754fI5nDhQ3zEpCqP5N2wWHNUXbZbGH7dg2BDcN6s1qrrZKs W+Cw== X-Forwarded-Encrypted: i=1; AJvYcCW75uf/RGWe3vxo/gMB4QZmDW3msH2xnXyNwPbBB1O7ugkh7qFJx66eMMCicjOazZP4ffIVu0OnzY8p6WxrUGUFSUn7J1xXRNEaXhF1 X-Gm-Message-State: AOJu0YxuVgDheMdU4U0HMnNmsNrCiuNqJqNUZ7/3IDa5uTDawHAEfXNq WXb0C1DNYkI/kLpXnEtAzkp6v7vsPi+CvzvLRk8f0GPMiV0HkttYie19y2SXGyPpaE3U+0l1Tuq pshp1JhyN81yR0Q== X-Google-Smtp-Source: AGHT+IFMEkiTrLYVlGwRErNqUfwoDA5zE0L6LG+0tqFbLkqJ2OL6U+Bbd7Qnd82dro7+NlgDM08smzyCo7K43R0= X-Received: from aliceryhl.c.googlers.com ([fda3:e722:ac3:cc00:28:9cb1:c0a8:35bd]) (user=aliceryhl job=sendgmr) by 2002:a05:600c:a085:b0:428:197f:2407 with SMTP id 5b1f17b1804b1-428e6cc2a2dmr638185e9.5.1722952789849; Tue, 06 Aug 2024 06:59:49 -0700 (PDT) Date: Tue, 06 Aug 2024 13:59:01 +0000 In-Reply-To: <20240806-linked-list-v4-0-23efc510ec92@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240806-linked-list-v4-0-23efc510ec92@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=11925; i=aliceryhl@google.com; h=from:subject:message-id; bh=DWn7jfpTLBRlhpcytJudwcfEhzJZIMi+Im52RQQpm8o=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBmsiw8eo7wc3L2etqxaS+zGJn80d3m1Tet5RCE2 b4yY8dC5+aJAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCZrIsPAAKCRAEWL7uWMY5 Rh6iD/9K0rfxdSmtprEvtl+EqbMkPLGoj7FkIFcjLwN8UlTy0oH/mqYEbTcGElPwVpPmrZR8Fdi 9gHCd9ur/rPakWBAV9bSz8rC0guLgWwmdKnEUejjuAL4bR+uXWxz0qFE22IqHETdkxniC1Vx+By KGBqzlj789RWwwYXCAyBSzSfFV0vxylrjTNxPForhMSL8SJTFuJty3u7VChOUvAJ03bQsLvIyVX LuCNRwXDGZwcJ7ePomCn20i4eqrqEjiZN+UyYccLPoY9zDF4IiUXy+dx+meUurJoMz7uWZJIZ2B XrSv1OKg8/AFP62pvmXj4ywpZrAM+dFUqFTilmRqvy2DtSCocIQ/0lx/GYMZEw4YTt2v9Eo/jWg Ct3KBlEPo+CWXokG5iOjY+ZVWZVuwbpwwWbl/raXOXiD8xssfx9LWKRH5dPABwIw9nrkhLLTZeT kDK9zzjz3bscTvYstVFOGluQRudD7EYZ03MjBcbnb47J/PZeb3mYLDveSLQEq+z1fr02zwedUkc UuSNwv/kK3obHuoq4rsPy32ZcdjN7/Bk1Ky0zf6s+rOmiet80ZhZBzzoZTyULXka+5f5/Hjapso xNDbhPf2BRdpJEYZ1lM698GSXa1Kyoe+yRiQgeJei63eZcK58m3oXmWkMTCtsTBiErc3+weOH0V IMOcl/GISw1rrXg== X-Mailer: b4 0.13.0 Message-ID: <20240806-linked-list-v4-9-23efc510ec92@google.com> Subject: [PATCH v4 09/10] 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 , Coly Li , Paolo Abeni , Pierre Gondois , Ingo Molnar , Jakub Kicinski , Wei Yang , Matthew Wilcox , linux-kernel@vger.kernel.org, rust-for-linux@vger.kernel.org, Alice Ryhl , Kees Cook Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Support linked lists that can hold 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 Reviewed-by: Benno Lossin --- rust/kernel/list.rs | 47 +++++++++++- rust/kernel/list/impl_list_item_mod.rs | 131 +++++++++++++++++++++++++++++= ++++ 2 files changed, 177 insertions(+), 1 deletion(-) diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs index 904cfa454dff..cf26fec37c1e 100644 --- a/rust/kernel/list.rs +++ b/rust/kernel/list.rs @@ -12,7 +12,9 @@ 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::{impl_list_arc_safe, AtomicTracker, ListArc, ListArcSaf= e, TryNewListArc}; @@ -183,6 +185,49 @@ 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, + // UnsafeCell is not enough here because we need `Opaque::zeroed` as a= dummy value, and + // `ptr::null()` doesn't work for `T: ?Sized`. + self_ptr: Opaque<*const T>, +} + +// SAFETY: The fields of a ListLinksSelfPtr can be moved across thread bou= ndaries. +unsafe impl Send for ListLinksSelfPtr {} +// SAFETY: The type is opaque so immutable references to a ListLinksSelfPt= r are useless. Therefore, +// it's okay to have immutable access to a ListLinks from several threads = at once. +// +// Note that `inner` being a public field does not prevent this type from = being opaque, since +// `inner` is a opaque type. +unsafe impl Sync for ListLinksSelfPtr {} + +impl ListLinksSelfPtr { + /// The offset from the [`ListLinks`] to the self pointer field. + pub const LIST_LINKS_SELF_PTR_OFFSET: usize =3D core::mem::offset_of!(= Self, self_ptr); + + /// Creates a new initializer for this type. + pub fn new() -> impl PinInit { + // INVARIANT: Pin-init initializers can't be used on an existing `= Arc`, so this value will + // not be constructed in an `Arc` that already has a `ListArc`. + Self { + inner: ListLinks { + inner: Opaque::new(ListLinksFields { + prev: ptr::null_mut(), + next: ptr::null_mut(), + }), + }, + self_ptr: Opaque::uninit(), + } + } +} + 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 30886e64b8ef..2dbbc648045f 100644 --- a/rust/kernel/list/impl_list_item_mod.rs +++ b/rust/kernel/list/impl_list_item_mod.rs @@ -68,6 +68,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. /// /// Requires that the type implements [`HasListLinks`]. Use the [`impl_has= _list_links!`] macro to @@ -139,5 +182,93 @@ unsafe fn post_remove(me: *mut $crate::list::ListLinks= <$num>) -> *const Self { } } )*}; + + ( + $(impl$({$($generics:tt)*})? ListItem<$num:tt> for $t:ty { + using ListLinksSelfPtr; + })* + ) =3D> {$( + // SAFETY: See GUARANTEES comment on each method. + unsafe impl$(<$($generics)*>)? $crate::list::ListItem<$num> for $t= { + // GUARANTEES: + // This implementation of `ListItem` will not give out exclusi= ve access to the same + // `ListLinks` several times because calls to `prepare_to_inse= rt` and `post_remove` + // must alternate and exclusive access is given up when `post_= remove` is called. + // + // Other invocations of `impl_list_item!` also cannot give out= exclusive access to the + // same `ListLinks` because you can only implement `ListItem` = once for each value of + // `ID`, and the `ListLinks` fields only work with the specifi= ed `ID`. + unsafe fn prepare_to_insert(me: *const Self) -> *mut $crate::l= ist::ListLinks<$num> { + // SAFETY: The caller promises that `me` points at a valid= value of type `Self`. + let links_field =3D unsafe { >::view_links(me) }; + + let spoff =3D $crate::list::ListLinksSelfPtr::= ::LIST_LINKS_SELF_PTR_OFFSET; + // Goes via the offset as the field is private. + // + // SAFETY: The constant is equal to `offset_of!(ListLinksS= elfPtr, self_ptr)`, so + // the pointer stays in bounds of the allocation. + let self_ptr =3D unsafe { (links_field as *const u8).add(s= poff) } + as *const $crate::types::Opaque<*const Self>; + let cell_inner =3D $crate::types::Opaque::raw_get(self_ptr= ); + + // SAFETY: This value is not accessed in any other places = than `prepare_to_insert`, + // `post_remove`, or `view_value`. By the safety requireme= nts of those methods, + // none of these three methods may be called in parallel w= ith this call to + // `prepare_to_insert`, so this write will not race with a= ny other access to the + // value. + unsafe { ::core::ptr::write(cell_inner, me) }; + + links_field + } + + // GUARANTEES: + // * This returns the same pointer as `prepare_to_insert` beca= use `prepare_to_insert` + // returns the return value of `view_links`. + // * By the type invariants of `ListLinks`, the `ListLinks` ha= s two null pointers when + // this value is not in a list. + unsafe fn view_links(me: *const Self) -> *mut $crate::list::Li= stLinks<$num> { + // SAFETY: The caller promises that `me` points at a valid= value of type `Self`. + unsafe { >::raw_get_list_links(= me.cast_mut()) } + } + + // This function is also used as the implementation of `post_r= emove`, so the caller + // may choose to satisfy the safety requirements of `post_remo= ve` instead of the safety + // requirements for `view_value`. + // + // GUARANTEES: (always) + // * This returns the same pointer as the one passed to the mo= st recent call to + // `prepare_to_insert` since that call wrote that pointer to= this location. The value + // is only modified in `prepare_to_insert`, so it has not be= en modified since the + // most recent call. + // + // GUARANTEES: (only when using the `view_value` safety requir= ements) + // * The pointer remains valid until the next call to `post_re= move` because the caller + // of the most recent call to `prepare_to_insert` promised t= o retain ownership of the + // `ListArc` containing `Self` until the next call to `post_= remove`. The value cannot + // be destroyed while a `ListArc` reference exists. + unsafe fn view_value(links_field: *mut $crate::list::ListLinks= <$num>) -> *const Self { + let spoff =3D $crate::list::ListLinksSelfPtr::= ::LIST_LINKS_SELF_PTR_OFFSET; + // SAFETY: The constant is equal to `offset_of!(ListLinksS= elfPtr, self_ptr)`, so + // the pointer stays in bounds of the allocation. + let self_ptr =3D unsafe { (links_field as *const u8).add(s= poff) } + as *const ::core::cell::UnsafeCell<*const Self>; + let cell_inner =3D ::core::cell::UnsafeCell::raw_get(self_= ptr); + // SAFETY: This is not a data race, because the only funct= ion that writes to this + // value is `prepare_to_insert`, but by the safety require= ments the + // `prepare_to_insert` method may not be called in paralle= l with `view_value` or + // `post_remove`. + unsafe { ::core::ptr::read(cell_inner) } + } + + // GUARANTEES: + // The first guarantee of `view_value` is exactly what `post_r= emove` guarantees. + unsafe fn post_remove(me: *mut $crate::list::ListLinks<$num>) = -> *const Self { + // SAFETY: This specific implementation of `view_value` al= lows the caller to + // promise the safety requirements of `post_remove` instea= d of the safety + // requirements for `view_value`. + unsafe { >::view_valu= e(me) } + } + } + )*}; } pub use impl_list_item; --=20 2.46.0.rc2.264.g509ed76dc8-goog From nobody Fri Dec 19 19:07:43 2025 Received: from mail-yb1-f201.google.com (mail-yb1-f201.google.com [209.85.219.201]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 62D3B3DABF6 for ; Tue, 6 Aug 2024 13:59:53 +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=1722952795; cv=none; b=b6BCfg44059dmVhAX4NNvASNP8d0Hny+ByNDUvJsyXaEa3+Fz1QYlLHFST7gbCnMIOF/YAthVbdxIQIjBYqbSp5toqp+WgtvqvKamSLNMEz8Ne06+oKumRd8BRuJ8vs7ijXO50eIH1CfJ7WYLdrdLjdZFSJB70oLSo8d7PqVuyI= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1722952795; c=relaxed/simple; bh=sjs5+cx5RsK4I10owZyIhjJWj92izcNKjyfWK0eU9GU=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=YfePQom6W9zD9Qe6IjHk+RbD6Jny6d7PDlMSzCp6WvlM3PkXDutwjl9uw8cvNTp4DWk3NT3NHEyvRu+c66ddBt1XFjLfmVriw7S0HZayEUGG9psgiS2Zdfz9y4rXYCcjqsd7yVCkhqshzrFIi8vW6xf21CYAjmz86RCLabl3rFw= 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=T4E2xdi6; 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="T4E2xdi6" Received: by mail-yb1-f201.google.com with SMTP id 3f1490d57ef6-e03b3f48c65so1096605276.0 for ; Tue, 06 Aug 2024 06:59:53 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1722952792; x=1723557592; 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=RSHT3FWCrBiqXPsNuRM6ONtDFcAm4Iow/SptrIyizP4=; b=T4E2xdi6Q5R+BtLok+JhEqhGqm0MmbvQWxG7K2qdHrndumOwWJylWqkaayQOUUf3uG 31Bzf2g/RU4RbPaAKdKWcJhTodj2TmWSqyw4QjqC1yN2yQPk/eT+hN7fmxJHgqBoRFe4 HweWxt9xb9PTV61M0ammgNXiGlkL2gUFJ7r1PNo0M/SDRdYmmfKC9Ai1+lgLirBNAZ9L W2DiSuam4qrv91E4aCAIOCLEge0nzQTRr59vT1GZyUn7UOC1+YZweQSfY3r7el++wLxx cDtdaLe4pw+YeeE4eBL1ti6abucdDa4Ferv1oq9O4SXGRAZO6AxzQUDKUGzYQnNcosYl nhUg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1722952792; x=1723557592; 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=RSHT3FWCrBiqXPsNuRM6ONtDFcAm4Iow/SptrIyizP4=; b=vvbbQOpLmnfXvsLHpGiNNh1JXX/I95Q4hKRHyAL39YArachUZAMHFigNb0iVCoGVhL gbuFDY+xi6SQCHsfTPjjjvuZNNwHIrtxwidAxfOhVo1rfmLmhh6gDBHm6hS8ftFEgpCZ NHAEd2H+H4V3pZ0wg1VtbKGI2jYWwid0R1i+YFLQecWT3Mm5gMf/SzA/2xV14tizLla4 LX+3z7uH8pqXsj0fg69P7V6MwP0UDhl0N7ryGsbGqJNodn6yUTsUMmg1zcHuUQs6w4kK FSvjSc6kNTuy8RjsxPGifXoMkk4OSLERtA/SWrGEbB91uwtgjSnNhin9L36uDVa0tK1o IDCA== X-Forwarded-Encrypted: i=1; AJvYcCWTHSsr5p2/3E5Zic2xFcWR1BE5GSR77iWNz1PEHf/7n6YICaCd1clRsD4/c0A3EemYB0oRYOrXMsRaTYNzt2/l1JbrzQBhwmuf+BQe X-Gm-Message-State: AOJu0Yz1Q33TRCMCTRyOPXVpePUTrxjuXHAsUfXO1YjEKnPSZSVuwvr8 /+yE+r+IkT33eNEtOGC/zq986FpREbZe7ARSffQSdwzpMQolBv7MAiFoCnWzRVwH/caM7cfLTDo v6qiBjICBwhx1vg== X-Google-Smtp-Source: AGHT+IGK3CoPkJd39xnjiPgyg29UTNJbe2DuQKHixP3ZF4Qqay5YuUYU3D+U0KziAQa4gcAj3c6RtdIOIt3h0tw= X-Received: from aliceryhl.c.googlers.com ([fda3:e722:ac3:cc00:28:9cb1:c0a8:35bd]) (user=aliceryhl job=sendgmr) by 2002:a05:6902:2483:b0:e03:a0b2:f73 with SMTP id 3f1490d57ef6-e0bde2f3cdbmr112477276.6.1722952792116; Tue, 06 Aug 2024 06:59:52 -0700 (PDT) Date: Tue, 06 Aug 2024 13:59:02 +0000 In-Reply-To: <20240806-linked-list-v4-0-23efc510ec92@google.com> Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240806-linked-list-v4-0-23efc510ec92@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=5366; i=aliceryhl@google.com; h=from:subject:message-id; bh=sjs5+cx5RsK4I10owZyIhjJWj92izcNKjyfWK0eU9GU=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBmsiw95qN0U65sxn3WNBTslbzyWYYlxLIS2QYlL KrVxm0wgvWJAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCZrIsPQAKCRAEWL7uWMY5 RknPD/95GFWviEvAvGiqrlvWy9Dct+g9YPZ7uZx4exk0nGLduAyqEWEKPkGX01jgDxTSRxAV5eV Ed7LOHsvGXL7tBqehry6mzHyqwNRjdAjZwJvsfFTPZXU6nRaarN5bnlMo7YP5p91QlorWU5b2VX 8OK6kqM7qGoni+IOoYoPmbJ9Qk9FhdZxjSoj7c/wlAmf4D42z0zd7u+JFkqOL9K+TOpdqfGkze0 SvmmB6RV0HdNYOTGLWMzGz76SQMb+xjkwEK4JefF2sEXyvAAPPbKfPvpWqnc6U+7spKSTKRoKig F1wi9ZRNt51Jkwd+DMQPaDXZcBgl3DonqbQbhiqB+IcfdvSYunqPRCcjaK46nco9oxrfeqBbmHI nQMKoKLBSFZBiM4EX+HRkySBEXTObAVDkd7cOv/2ukt8vHLoSCSnTPeFmChapaeNNLIJBzH4auL xg1OYcslvWZ97ah+kTsbCR0ZaFgVuI5AU7soFuQIsd4tJ3T3GUHi1MCEiNQrHckMqO8u5BNLgcO rOfd8II2QxJPFjgE4VJyMtOKF9URrnXSf0zaeLe9NrR9uZgFjcHQHHCGQwsiwHE8DPJGFAY+i9x r+c/lXGWLYvr/EEYT2Xxt1oP6CID4hxaG2X6P3NTJ8hl3ka5rXDih6wyskm9vVpidJKNBCXzAEw FYMJPL6lhGT6IsA== X-Mailer: b4 0.13.0 Message-ID: <20240806-linked-list-v4-10-23efc510ec92@google.com> Subject: [PATCH v4 10/10] 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 , Coly Li , Paolo Abeni , Pierre Gondois , Ingo Molnar , Jakub Kicinski , Wei Yang , Matthew Wilcox , linux-kernel@vger.kernel.org, rust-for-linux@vger.kernel.org, Alice Ryhl , Kees Cook Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable 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. Reviewed-by: Benno Lossin Signed-off-by: Alice Ryhl --- rust/kernel/list.rs | 3 ++ rust/kernel/list/arc_field.rs | 96 +++++++++++++++++++++++++++++++++++++++= ++++ 2 files changed, 99 insertions(+) diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs index cf26fec37c1e..e4cefac0f390 100644 --- a/rust/kernel/list.rs +++ b/rust/kernel/list.rs @@ -19,6 +19,9 @@ mod arc; pub use self::arc::{impl_list_arc_safe, AtomicTracker, ListArc, ListArcSaf= e, TryNewListArc}; =20 +mod arc_field; +pub use self::arc_field::{define_list_arc_field_getter, ListArcField}; + /// A linked list. /// /// All elements in this linked list will be [`ListArc`] references to the= value. Since a value can diff --git a/rust/kernel/list/arc_field.rs b/rust/kernel/list/arc_field.rs new file mode 100644 index 000000000000..2330f673427a --- /dev/null +++ b/rust/kernel/list/arc_field.rs @@ -0,0 +1,96 @@ +// SPDX-License-Identifier: GPL-2.0 + +// Copyright (C) 2024 Google LLC. + +//! A field that is exclusively owned by a [`ListArc`]. +//! +//! This can be used to have reference counted struct where one of the ref= erence counted pointers +//! has exclusive access to a field of the struct. +//! +//! [`ListArc`]: crate::list::ListArc + +use core::cell::UnsafeCell; + +/// A field owned by a specific [`ListArc`]. +/// +/// [`ListArc`]: crate::list::ListArc +pub struct ListArcField { + value: UnsafeCell, +} + +// SAFETY: If the inner type is thread-safe, then it's also okay for `List= Arc` to be thread-safe. +unsafe impl Send for ListArcField {} +// SAFETY: If the inner type is thread-safe, then it's also okay for `List= Arc` to be thread-safe. +unsafe impl Sync for ListArcField {} + +impl ListArcField { + /// Creates a new `ListArcField`. + pub fn new(value: T) -> Self { + Self { + value: UnsafeCell::new(value), + } + } + + /// Access the value when we have exclusive access to the `ListArcFiel= d`. + /// + /// This allows access to the field using an `UniqueArc` instead of a = `ListArc`. + pub fn get_mut(&mut self) -> &mut T { + self.value.get_mut() + } + + /// Unsafely assert that you have shared access to the `ListArc` for t= his field. + /// + /// # Safety + /// + /// The caller must have shared access to the `ListArc` containing= the struct with this + /// field for the duration of the returned reference. + pub unsafe fn assert_ref(&self) -> &T { + // SAFETY: The caller has shared access to the `ListArc`, so they = also have shared access + // to this field. + unsafe { &*self.value.get() } + } + + /// Unsafely assert that you have mutable access to the `ListArc` for = this field. + /// + /// # Safety + /// + /// The caller must have mutable access to the `ListArc` containin= g the struct with this + /// field for the duration of the returned reference. + #[allow(clippy::mut_from_ref)] + pub unsafe fn assert_mut(&self) -> &mut T { + // SAFETY: The caller has exclusive access to the `ListArc`, so th= ey also have exclusive + // access to this field. + unsafe { &mut *self.value.get() } + } +} + +/// Defines getters for a [`ListArcField`]. +#[macro_export] +macro_rules! define_list_arc_field_getter { + ($pub:vis fn $name:ident(&self $(<$id:tt>)?) -> &$typ:ty { $field:iden= t } + $($rest:tt)* + ) =3D> { + $pub fn $name<'a>(self: &'a $crate::list::ListArc)= -> &'a $typ { + let field =3D &(&**self).$field; + // SAFETY: We have a shared reference to the `ListArc`. + unsafe { $crate::list::ListArcField::<$typ $(, $id)?>::assert_= ref(field) } + } + + $crate::list::define_list_arc_field_getter!($($rest)*); + }; + + ($pub:vis fn $name:ident(&mut self $(<$id:tt>)?) -> &mut $typ:ty { $fi= eld:ident } + $($rest:tt)* + ) =3D> { + $pub fn $name<'a>(self: &'a mut $crate::list::ListArc) -> &'a mut $typ { + let field =3D &(&**self).$field; + // SAFETY: We have a mutable reference to the `ListArc`. + unsafe { $crate::list::ListArcField::<$typ $(, $id)?>::assert_= mut(field) } + } + + $crate::list::define_list_arc_field_getter!($($rest)*); + }; + + () =3D> {}; +} +pub use define_list_arc_field_getter; --=20 2.46.0.rc2.264.g509ed76dc8-goog