Rust Binder has lists containing stuff such as all contexts or all
processes, and sometimes need to iterate over them. This patch enables
Rust Binder to do that using a normal for loop.
The iterator returns the ArcBorrow type, so it is possible to grab a
refcount to values while iterating.
Signed-off-by: Alice Ryhl <aliceryhl@google.com>
---
rust/kernel/list.rs | 102 ++++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 102 insertions(+)
diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs
index 7e9ed802b26b..892705dd0571 100644
--- a/rust/kernel/list.rs
+++ b/rust/kernel/list.rs
@@ -5,7 +5,9 @@
//! A linked list implementation.
use crate::init::PinInit;
+use crate::sync::ArcBorrow;
use crate::types::Opaque;
+use core::iter::{DoubleEndedIterator, FusedIterator};
use core::marker::PhantomData;
use core::ptr;
@@ -405,6 +407,17 @@ pub fn push_all_back(&mut self, other: &mut List<T, ID>) {
// 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<T: ?Sized + ListItem<ID>, const ID: u64> Drop for List<T, ID> {
@@ -414,3 +427,92 @@ fn drop(&mut self) {
}
}
}
+
+/// An iterator into a [`List`].
+///
+/// # Invariants
+///
+/// The `current` pointer points at a value in a list, or it is null if the iterator has reached
+/// the end of the list. The `stop` pointer points at the first value in the same list, or it is
+/// null if the list is empty.
+#[derive(Clone)]
+pub struct Iter<'a, T: ?Sized + ListItem<ID>, const ID: u64 = 0> {
+ current: *mut ListLinksFields,
+ stop: *mut ListLinksFields,
+ _ty: PhantomData<&'a ListArc<T, ID>>,
+}
+
+impl<'a, T: ?Sized + ListItem<ID>, const ID: u64> Iterator for Iter<'a, T, ID> {
+ type Item = ArcBorrow<'a, T>;
+
+ fn next(&mut self) -> Option<ArcBorrow<'a, T>> {
+ 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 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<ID>, const ID: u64> FusedIterator for Iter<'a, T, ID> {}
+
+impl<'a, T: ?Sized + ListItem<ID>, const ID: u64> IntoIterator for &'a List<T, ID> {
+ 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<T: ?Sized + ListItem<ID>, const ID: u64 = 0> {
+ list: List<T, ID>,
+}
+
+impl<T: ?Sized + ListItem<ID>, const ID: u64> Iterator for IntoIter<T, ID> {
+ type Item = ListArc<T, ID>;
+
+ fn next(&mut self) -> Option<ListArc<T, ID>> {
+ self.list.pop_front()
+ }
+}
+
+impl<T: ?Sized + ListItem<ID>, const ID: u64> FusedIterator for IntoIter<T, ID> {}
+
+impl<T: ?Sized + ListItem<ID>, const ID: u64> DoubleEndedIterator for IntoIter<T, ID> {
+ fn next_back(&mut self) -> Option<ListArc<T, ID>> {
+ self.list.pop_back()
+ }
+}
+
+impl<T: ?Sized + ListItem<ID>, const ID: u64> IntoIterator for List<T, ID> {
+ type IntoIter = IntoIter<T, ID>;
+ type Item = ListArc<T, ID>;
+
+ fn into_iter(self) -> IntoIter<T, ID> {
+ IntoIter { list: self }
+ }
+}
--
2.44.0.478.gd926399ef9-googOn 02.04.24 14:17, Alice Ryhl wrote:
> @@ -414,3 +427,92 @@ fn drop(&mut self) {
> }
> }
> }
> +
> +/// An iterator into a [`List`].
> +///
> +/// # Invariants
> +///
> +/// The `current` pointer points at a value in a list, or it is null if the iterator has reached
I think "list" should link to [`List`].
> +/// the end of the list. The `stop` pointer points at the first value in the same list, or it is
> +/// null if the list is empty.
> +#[derive(Clone)]
> +pub struct Iter<'a, T: ?Sized + ListItem<ID>, const ID: u64 = 0> {
> + current: *mut ListLinksFields,
> + stop: *mut ListLinksFields,
> + _ty: PhantomData<&'a ListArc<T, ID>>,
> +}
> +
> +impl<'a, T: ?Sized + ListItem<ID>, const ID: u64> Iterator for Iter<'a, T, ID> {
> + type Item = ArcBorrow<'a, T>;
> +
> + fn next(&mut self) -> Option<ArcBorrow<'a, T>> {
> + 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.
This (that the iterator holds an immutable borrow) is not true (there
is no `&List` field in `Iter`), but you can make that an invariant
instead.
> + 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 a value in the list.
Typo: "points a value" -> "points at a value"
I think you should also use consistent naming when referring to the
elements/items/values of a list.
--
Cheers,
Benno
> + 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) })
> + }
> +}
On Thu, Apr 4, 2024 at 4:36 PM Benno Lossin <benno.lossin@proton.me> wrote:
>
> On 02.04.24 14:17, Alice Ryhl wrote:
> > +/// the end of the list. The `stop` pointer points at the first value in the same list, or it is
> > +/// null if the list is empty.
> > +#[derive(Clone)]
> > +pub struct Iter<'a, T: ?Sized + ListItem<ID>, const ID: u64 = 0> {
> > + current: *mut ListLinksFields,
> > + stop: *mut ListLinksFields,
> > + _ty: PhantomData<&'a ListArc<T, ID>>,
> > +}
> > +
> > +impl<'a, T: ?Sized + ListItem<ID>, const ID: u64> Iterator for Iter<'a, T, ID> {
> > + type Item = ArcBorrow<'a, T>;
> > +
> > + fn next(&mut self) -> Option<ArcBorrow<'a, T>> {
> > + 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.
>
> This (that the iterator holds an immutable borrow) is not true (there
> is no `&List` field in `Iter`), but you can make that an invariant
> instead.
What I mean is that the borrow-checker will consider the `List` to be
borrowed by `Iter`. Whether or not there is a real reference or not
doesn't matter.
Alice
On 04.04.24 16:41, Alice Ryhl wrote:
> On Thu, Apr 4, 2024 at 4:36 PM Benno Lossin <benno.lossin@proton.me> wrote:
>>
>> On 02.04.24 14:17, Alice Ryhl wrote:
>>> +/// the end of the list. The `stop` pointer points at the first value in the same list, or it is
>>> +/// null if the list is empty.
>>> +#[derive(Clone)]
>>> +pub struct Iter<'a, T: ?Sized + ListItem<ID>, const ID: u64 = 0> {
>>> + current: *mut ListLinksFields,
>>> + stop: *mut ListLinksFields,
>>> + _ty: PhantomData<&'a ListArc<T, ID>>,
>>> +}
>>> +
>>> +impl<'a, T: ?Sized + ListItem<ID>, const ID: u64> Iterator for Iter<'a, T, ID> {
>>> + type Item = ArcBorrow<'a, T>;
>>> +
>>> + fn next(&mut self) -> Option<ArcBorrow<'a, T>> {
>>> + 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.
>>
>> This (that the iterator holds an immutable borrow) is not true (there
>> is no `&List` field in `Iter`), but you can make that an invariant
>> instead.
>
> What I mean is that the borrow-checker will consider the `List` to be
> borrowed by `Iter`. Whether or not there is a real reference or not
> doesn't matter.
Yes, but that is implementation detail of the safe function
`List::iter`, so I think it must also be captured by an invariant.
--
Cheers,
Benno
On Thu, Apr 4, 2024 at 4:52 PM Benno Lossin <benno.lossin@proton.me> wrote:
>
> On 04.04.24 16:41, Alice Ryhl wrote:
> > On Thu, Apr 4, 2024 at 4:36 PM Benno Lossin <benno.lossin@proton.me> wrote:
> >>
> >> On 02.04.24 14:17, Alice Ryhl wrote:
> >>> +/// the end of the list. The `stop` pointer points at the first value in the same list, or it is
> >>> +/// null if the list is empty.
> >>> +#[derive(Clone)]
> >>> +pub struct Iter<'a, T: ?Sized + ListItem<ID>, const ID: u64 = 0> {
> >>> + current: *mut ListLinksFields,
> >>> + stop: *mut ListLinksFields,
> >>> + _ty: PhantomData<&'a ListArc<T, ID>>,
> >>> +}
> >>> +
> >>> +impl<'a, T: ?Sized + ListItem<ID>, const ID: u64> Iterator for Iter<'a, T, ID> {
> >>> + type Item = ArcBorrow<'a, T>;
> >>> +
> >>> + fn next(&mut self) -> Option<ArcBorrow<'a, T>> {
> >>> + 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.
> >>
> >> This (that the iterator holds an immutable borrow) is not true (there
> >> is no `&List` field in `Iter`), but you can make that an invariant
> >> instead.
> >
> > What I mean is that the borrow-checker will consider the `List` to be
> > borrowed by `Iter`. Whether or not there is a real reference or not
> > doesn't matter.
>
> Yes, but that is implementation detail of the safe function
> `List::iter`, so I think it must also be captured by an invariant.
I will add an invariant.
© 2016 - 2026 Red Hat, Inc.