From mboxrd@z Thu Jan 1 00:00:00 1970 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 33D2F1487EA for ; Wed, 14 Aug 2024 08:06:15 +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=1723622778; cv=none; b=DIgKLC96y2hHhXhTzIU/CVwzU+JANof+YOTQTeVIWg2CcpqzsybR5OpALWNj+QdS8ojcKqPgGD5EA+yYBnPlcewm7gohQvz5MjhOZTqAs9jKYap9QzV68xchuOBtbrtzK0E5TCGqB22bCkA5KBm2uPrH+S/qEmmz6s7FO0Cwfu4= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1723622778; c=relaxed/simple; bh=dGtWLeCSuTNEwUugDyA1XdJqmUZPsl32zsHFqetb4/k=; h=Date:In-Reply-To:Mime-Version:References:Message-ID:Subject:From: To:Cc:Content-Type; b=BzEN9TkvwpItaGkRiLEVRyOeX2AsxWDbTZT4PKNQ0j0G1AQXT4fX53d60y/LSeO7tKmz19tILeEq0k80lGB8tq/0mpAx6sEet3xPrpAx2sPMEotUgzIJ4IOqMgHVCS24ZEe8txVPw/kDv1hy6ErCI5uvK9AMK4ggX6Omq8oT3uE= 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=zpfk77cQ; 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="zpfk77cQ" Received: by mail-wr1-f73.google.com with SMTP id ffacd0b85a97d-3685a5a765fso3712979f8f.1 for ; Wed, 14 Aug 2024 01:06:15 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20230601; t=1723622774; x=1724227574; 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=Zzj0Y8qT0OVh2xjwyqiYL1BRt2Dsmc+jX/UXC6YevlE=; b=zpfk77cQBe7hAw3WPNQdnv6eiqaaDTRRUP6Y8irQvybs+J4/PvhEDDNrsg0nijaCci Yl9Vf6sEOO/XqJUxUtP99gYFalzq1Q339Lq+SkMfJFuH8kCZT9Dl7j/pZPD9Yy/OM9zw XdEti1EGa8jN1EOA7VwYmQd632Di8T3Ant0TlDiZo/NiZsnKG5fhpYEqgXzy2YuzrfM7 DNmzJcfw34/vJNWYQlB7Q2PGfiLt+Neqf8WKgxLgSPoVpPru7+baUwF7a3dw0DqgQIY4 iRQQPVwyCCHQeuCpOdTuXnuSdgrCfeHTzTcPYsZ6/kmA+iTp1xFty85AqAvHTaKwqWT5 K50w== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1723622774; x=1724227574; 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=Zzj0Y8qT0OVh2xjwyqiYL1BRt2Dsmc+jX/UXC6YevlE=; b=TM580Yu/isymbz3Hm4J5O0p2s2k2c+YlX5EfqBmJ2sFyQr3GB5o9PQYd2fU4wFbO+8 HKaLAJrvL9mRQg+NI3qYE1LWnQeyQYzDWfDDixvtUiGj+VnZagpIbVb1tzLcbfJ4k1dC E9s6via+DomJp70SNX6mOFEAglfgm7WZLL3C6jo/uE8hZ7xSlWt/GmLQJrxVyP/Nimrf CS3hLb3ksXaoti+AbeUlDiaHj/Y204p+68c5PT/mEAOjrmZaNjPllqoJO4+Rh5SBA4LN Unpx+WxPeLJ2Smbz3IjM/XjUUJi3RU0JV27KjYnrM5Y/RLTiy3jnIRdl3jw5HMddU6ko 8JFQ== X-Forwarded-Encrypted: i=1; AJvYcCXKHHb+avGvCWt9SnA5J/2qgK2Q3oboB5Rl1Mj0kyarqeCgNEb0YS3iCIUkZRagmWd3QAzRBXYB3M0+b+1QFER0S14qVoHWhMcWfeoKDe0= X-Gm-Message-State: AOJu0YxRWJ5q8Wg1yYyc58kpHgOifTmwr4x42V+wDlzmE97q1UdzFazp HYbFbSXBFNyF/ITFr+27v/eL9i628nZQ8Ld1pt4U9tkgxp2c38rL4BLdWNQMME+uq8/31jxPHRr nvj+opbeJmp8nlg== X-Google-Smtp-Source: AGHT+IEf6YoaCDMsRG7GznUzLKEpOLTGCT7RvZ7lwGKcm+8duQ7/MuPCrVm/1WBElrLQn5b0njZpo7YqRmyRpeU= X-Received: from aliceryhl.c.googlers.com ([fda3:e722:ac3:cc00:28:9cb1:c0a8:35bd]) (user=aliceryhl job=sendgmr) by 2002:a5d:69d1:0:b0:368:4910:16ed with SMTP id ffacd0b85a97d-37177785b92mr3218f8f.5.1723622774225; Wed, 14 Aug 2024 01:06:14 -0700 (PDT) Date: Wed, 14 Aug 2024 08:05:26 +0000 In-Reply-To: <20240814-linked-list-v5-0-f5f5e8075da0@google.com> Precedence: bulk X-Mailing-List: rust-for-linux@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: Mime-Version: 1.0 References: <20240814-linked-list-v5-0-f5f5e8075da0@google.com> X-Developer-Key: i=aliceryhl@google.com; a=openpgp; fpr=49F6C1FAA74960F43A5B86A1EE7A392FDE96209F X-Developer-Signature: v=1; a=openpgp-sha256; l=5025; i=aliceryhl@google.com; h=from:subject:message-id; bh=dGtWLeCSuTNEwUugDyA1XdJqmUZPsl32zsHFqetb4/k=; b=owEBbQKS/ZANAwAKAQRYvu5YxjlGAcsmYgBmvGVfrIu15K142PsJ8dJR1RWGMccf7FITauuV3 Vl9RoE+XTmJAjMEAAEKAB0WIQSDkqKUTWQHCvFIvbIEWL7uWMY5RgUCZrxlXwAKCRAEWL7uWMY5 RhVtEACGLqSckv4oIE7zO1/sZxd7rQeK2aK1hlpaKAXO8Bw+JXv3aWCbb+yhvbVUBkYwdUyJPYJ oGk3TdXMTywqJhEiXBj6KcPVnlCS2KFgsRwFHonPf7SSiQ0RshD4tW85bs2TuXQUg84P3giB0SH XOM4Mt/LGwrrmLZBjP9X63kZIeKDb4pZ2UF1VK6Npuoxh8PSjuo03K2NaJZlrjC/W1fuT4t+E2K o9SfBSdnyWjEcSt+Mpl8tHd7vjinLDfWJG74bd07S5KniIyNcgJs5VSJljsS4JqG53lOBd9GdSB tYromwxGF0ZHCrj4uTQU4V6e+AOZ+uLAE9Gt7WQs8MezM85a+CaVhCcl1cYZxDfjPDlo7tvAGnF cestm4A7rsQUeZB9m70zyHxHZIVGuzNpcfsMndQzZxnu6DRgSPnBxgN5PuxnWczKKxawuML+rXR qiJVmFYgpYGNswepnc2sr8FzKop7jAAW3yTj74UCyNvV0guiXUvdaXVcn209mx+EwBkvBknxPx3 lJHHvcEMZSW1QAh26lQ86eSNi10b8QEGDwMXR5Qz150VSuC4UtF3qpvrhTkQOJZFRXEWbsanXD1 nyEXjnlHUVr6mJECdbi9L2F+pBxxXWUH18KP3Q225jkxOebQhs8vfOOhFEVzxpadyItNiVSwFB2 G1urdF+GicwxfXg== X-Mailer: b4 0.13.0 Message-ID: <20240814-linked-list-v5-7-f5f5e8075da0@google.com> Subject: [PATCH v5 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" 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. use crate::init::PinInit; +use crate::sync::ArcBorrow; use crate::types::Opaque; +use core::iter::{DoubleEndedIterator, FusedIterator}; use core::marker::PhantomData; use core::ptr; @@ -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 = 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. Otherwise, both pointers point + // at the first element of the same list. + Iter { + current: self.first, + stop: self.first, + _ty: PhantomData, + } + } } 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 = 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 = ArcBorrow<'a, T>; + + fn next(&mut self) -> Option> { + if self.current.is_null() { + return None; + } + + let current = 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 immutable borrow to the list. + let next = 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 = if next != self.stop { + next + } else { + ptr::null_mut() + }; + + // SAFETY: The `current` pointer points at a value in the list. + let item = 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 list would require mutable + // access to the list. However, the `ArcBorrow` is annotated with the iterator's + // lifetime, and the list is immutably borrowed for that lifetime. + // * 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 List { + type IntoIter = Iter<'a, T, ID>; + type Item = 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 = 0> { + list: List, +} + +impl, const ID: u64> Iterator for IntoIter { + type Item = ListArc; + + fn next(&mut self) -> Option> { + self.list.pop_front() + } +} + +impl, const ID: u64> FusedIterator for IntoIter {} + +impl, const ID: u64> DoubleEndedIterator for IntoIter { + fn next_back(&mut self) -> Option> { + self.list.pop_back() + } +} + +impl, const ID: u64> IntoIterator for List { + type IntoIter = IntoIter; + type Item = ListArc; + + fn into_iter(self) -> IntoIter { + IntoIter { list: self } + } +} -- 2.46.0.76.ge559c4bf1a-goog