This patchset contains a Rust implementation of a doubly-linked list for
use with reference counted values. Linked lists are famously hard to
implement in Rust [1] given the cyclic nature of the pointers, and
indeed, this implementation uses unsafe to get around that.
Linked lists aren't great for cache locality reasons, but it can be hard
to avoid them for cases where you need data structures that don't
allocate. Most linked lists in Binder are for collections where order
matters (usually stacks or queues). There are also a few lists that are
just collections, but linked lists are only used for this purpose in
cases where the linked list is cold and performance isn't that
important. The linked list is chosen over Vec in this case so that I
don't have to worry about reducing the capacity of the vector. (Our
red/black trees are a much better place to look for improving cache
locality of collections in Rust Binder, and the upcoming xarray bindings
would help with that.)
Please see the Rust Binder RFC [2] for usage examples.
The linked lists are used all over Rust Binder, but some pointers for
where to look for examples:
[PATCH RFC 04/20] rust_binder: add work lists
Implements the work lists that store heterogeneous items. Uses the
various macros a bunch.
[PATCH RFC 10/20] rust_binder: add death notifications
Uses the cursor. Also has objects with multiple prev/next pointer pairs.
[PATCH RFC 15/20] rust_binder: add process freezing
Uses the iterator with for loops.
This patchset depends on [3].
Link: https://rust-unofficial.github.io/too-many-lists/ [1]
Link: https://lore.kernel.org/rust-for-linux/[email protected]/ [2]
Link: https://lore.kernel.org/rust-for-linux/[email protected]/ [3]
Signed-off-by: Alice Ryhl <[email protected]>
---
Alice Ryhl (9):
rust: list: add ListArc
rust: list: add tracking for ListArc
rust: list: add struct with prev/next pointers
rust: list: add macro for implementing ListItem
rust: list: add List
rust: list: add iterators
rust: list: add cursor
rust: list: support heterogeneous lists
rust: list: add ListArcField
rust/kernel/lib.rs | 1 +
rust/kernel/list.rs | 637 +++++++++++++++++++++++++++++++++
rust/kernel/list/arc.rs | 431 ++++++++++++++++++++++
rust/kernel/list/arc_field.rs | 94 +++++
rust/kernel/list/impl_list_item_mod.rs | 181 ++++++++++
5 files changed, 1344 insertions(+)
---
base-commit: 98ebc2e1c5bd188fd3140a0f812b302bb9c3ad26
change-id: 20240221-linked-list-25169a90a4de
Best regards,
--
Alice Ryhl <[email protected]>
The `ListArc` type can be thought of as a special reference to a
refcounted object that owns the permission to manipulate the
`next`/`prev` pointers stored in the refcounted object. By ensuring that
each object has only one `ListArc` reference, the owner of that
reference is assured exclusive access to the `next`/`prev` pointers.
When a `ListArc` is inserted into a `List`, the `List` takes ownership
of the `ListArc` reference.
There are various strategies for ensuring that a value has only one
`ListArc` reference. The simplest is to convert a `UniqueArc` into a
`ListArc`. However, the refcounted object could also keep track of
whether a `ListArc` exists using a boolean, which could allow for the
creation of new `ListArc` references from an `Arc` reference. Whatever
strategy is used, the relevant tracking is referred to as "the tracking
inside `T`", and the `ListArcSafe` trait (and its subtraits) are used to
update the tracking when a `ListArc` is created or destroyed.
Note that we allow the case where the tracking inside `T` thinks that a
`ListArc` exists, but actually, there isn't a `ListArc`. However, we do
not allow the opposite situation where a `ListArc` exists, but the
tracking thinks it doesn't. This is because the former can at most
result in us failing to create a `ListArc` when the operation could
succeed, whereas the latter can result in the creation of two `ListArc`
references.
This patch introduces the `impl_list_arc_safe!` macro that allows you to
implement `ListArcSafe` for types using the strategy where a `ListArc`
can only be created from a `UniqueArc`. Other strategies are introduced
in later patches.
This is part of the linked list that Rust Binder will use for many
different things. The strategy where a `ListArc` can only be created
from a `UniqueArc` is actually sufficient for most of the objects that
Rust Binder needs to insert into linked lists. Usually, these are todo
items that are created and then immediately inserted into a queue.
The const generic ID allows objects to have several prev/next pointer
pairs so that the same object can be inserted into several different
lists. You are able to have several `ListArc` references as long as they
correspond to different pointer pairs. The ID itself is purely a
compile-time concept and will not be present in the final binary. Both
the `List` and the `ListArc` will need to agree on the ID for them to
work together. Rust Binder uses this in a few places (e.g. death
recipients) where the same object can be inserted into both generic todo
lists and some other lists for tracking the status of the object.
The ID is a const generic rather than a type parameter because the
`pair_from_unique` method needs to be able to assert that the two ids
are different. There's no easy way to assert that when using types
instead of integers.
Signed-off-by: Alice Ryhl <[email protected]>
---
rust/kernel/lib.rs | 1 +
rust/kernel/list.rs | 8 ++
rust/kernel/list/arc.rs | 302 ++++++++++++++++++++++++++++++++++++++++++++++++
3 files changed, 311 insertions(+)
diff --git a/rust/kernel/lib.rs b/rust/kernel/lib.rs
index be68d5e567b1..30080328b740 100644
--- a/rust/kernel/lib.rs
+++ b/rust/kernel/lib.rs
@@ -37,6 +37,7 @@
pub mod ioctl;
#[cfg(CONFIG_KUNIT)]
pub mod kunit;
+pub mod list;
#[cfg(CONFIG_NET)]
pub mod net;
pub mod prelude;
diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs
new file mode 100644
index 000000000000..fb16ea43b2ba
--- /dev/null
+++ b/rust/kernel/list.rs
@@ -0,0 +1,8 @@
+// SPDX-License-Identifier: GPL-2.0
+
+// Copyright (C) 2024 Google LLC.
+
+//! A linked list implementation.
+
+mod arc;
+pub use self::arc::{impl_list_arc_safe, ListArc, ListArcSafe};
diff --git a/rust/kernel/list/arc.rs b/rust/kernel/list/arc.rs
new file mode 100644
index 000000000000..59d43f7a165e
--- /dev/null
+++ b/rust/kernel/list/arc.rs
@@ -0,0 +1,302 @@
+// SPDX-License-Identifier: GPL-2.0
+
+// Copyright (C) 2024 Google LLC.
+
+//! A wrapper around `Arc` for linked lists.
+
+use crate::error;
+use crate::prelude::*;
+use crate::sync::{Arc, ArcBorrow, UniqueArc};
+use core::alloc::AllocError;
+use core::marker::Unsize;
+use core::ops::Deref;
+use core::pin::Pin;
+
+/// Declares that this type has some way to ensure that there is exactly one `ListArc` instance for
+/// this id.
+pub trait ListArcSafe<const ID: u64 = 0> {
+ /// 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 thinks that a `ListArc`
+ /// reference exists. (But only if that's not actually the case.)
+ ///
+ /// # Safety
+ ///
+ /// Must not be called if a [`ListArc`] already exist for this value.
+ unsafe fn on_create_list_arc_from_unique(&mut self);
+
+ /// Informs the tracking inside this type that there is no [`ListArc`] reference anymore.
+ ///
+ /// # Safety
+ ///
+ /// Must only be called if there is no [`ListArc`] reference, but the tracking thinks there is.
+ unsafe fn on_drop_list_arc(&self);
+}
+
+/// Declares that this type supports [`ListArc`].
+///
+/// When using this macro, it will only be possible to create a [`ListArc`] from a [`UniqueArc`].
+#[macro_export]
+macro_rules! impl_list_arc_safe {
+ (impl$({$($generics:tt)*})? ListArcSafe<$num:tt> for $t:ty { untracked; } $($rest:tt)*) => {
+ impl$(<$($generics)*>)? $crate::list::ListArcSafe<$num> for $t {
+ unsafe fn on_create_list_arc_from_unique(&mut self) {}
+ unsafe fn on_drop_list_arc(&self) {}
+ }
+ $crate::list::impl_list_arc_safe! { $($rest)* }
+ };
+
+ () => {};
+}
+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 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 to 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.
+///
+/// # Invariants
+///
+/// * Each reference counted object has at most one `ListArc` for each value of `ID`.
+/// * The tracking inside `T` is aware that a `ListArc` reference exists.
+#[repr(transparent)]
+pub struct ListArc<T, const ID: u64 = 0>
+where
+ T: ListArcSafe<ID> + ?Sized,
+{
+ arc: Arc<T>,
+}
+
+impl<T: ListArcSafe<ID>, const ID: u64> ListArc<T, ID> {
+ /// Constructs a new reference counted instance of `T`.
+ pub fn try_new(contents: T) -> Result<Self, AllocError> {
+ Ok(Self::from_unique(UniqueArc::try_new(contents)?))
+ }
+
+ /// Use the given initializer to in-place initialize a `T`.
+ ///
+ /// If `T: !Unpin` it will not be able to move afterwards.
+ pub fn pin_init<E>(init: impl PinInit<T, E>) -> error::Result<Self>
+ where
+ Error: From<E>,
+ {
+ Ok(Self::from_pin_unique(UniqueArc::pin_init(init)?))
+ }
+}
+
+impl<T, const ID: u64> ListArc<T, ID>
+where
+ T: ListArcSafe<ID> + ?Sized,
+{
+ /// Convert a [`UniqueArc`] into a [`ListArc`].
+ pub fn from_unique(mut unique: UniqueArc<T>) -> Self {
+ // SAFETY: We have a `UniqueArc`, so there is no `ListArc`.
+ unsafe { T::on_create_list_arc_from_unique(&mut unique) };
+ let arc = Arc::from(unique);
+ // SAFETY: We just called `on_create_list_arc_from_unique` on an arc without a `ListArc`,
+ // so we can create a `ListArc`.
+ unsafe { Self::transmute_from_arc(arc) }
+ }
+
+ /// Convert a pinned [`UniqueArc`] into a [`ListArc`].
+ pub fn from_pin_unique(unique: Pin<UniqueArc<T>>) -> Self {
+ // SAFETY: We continue to treat this pointer as pinned after this call, since `ListArc`
+ // implicitly pins its value.
+ Self::from_unique(unsafe { Pin::into_inner_unchecked(unique) })
+ }
+
+ /// Like [`from_unique`], but creates two `ListArcs`.
+ ///
+ /// The two ids must be different.
+ ///
+ /// [`from_unique`]: ListArc::from_unique
+ pub fn pair_from_unique<const ID2: u64>(mut unique: UniqueArc<T>) -> (Self, ListArc<T, ID2>)
+ where
+ T: ListArcSafe<ID2>,
+ {
+ assert_ne!(ID, ID2);
+
+ // SAFETY: We have a `UniqueArc`, so we can call this method.
+ unsafe { <T as ListArcSafe<ID>>::on_create_list_arc_from_unique(&mut unique) };
+ // SAFETY: We have a `UniqueArc`, so we can call this method. The two ids are not equal.
+ unsafe { <T as ListArcSafe<ID2>>::on_create_list_arc_from_unique(&mut unique) };
+
+ let arc1 = Arc::from(unique);
+ let arc2 = Arc::clone(&arc1);
+
+ // SAFETY: We just called `on_create_list_arc_from_unique` on an arc without a `ListArc`,
+ // so we can create a `ListArc`.
+ unsafe {
+ (
+ Self::transmute_from_arc(arc1),
+ ListArc::transmute_from_arc(arc2),
+ )
+ }
+ }
+
+ /// Like [`pair_from_unique`], but uses a pinned arc.
+ ///
+ /// The two ids must be different.
+ ///
+ /// [`pair_from_unique`]: ListArc::pair_from_unique
+ pub fn pair_from_pin_unique<const ID2: u64>(
+ unique: Pin<UniqueArc<T>>,
+ ) -> (Self, ListArc<T, ID2>)
+ where
+ T: ListArcSafe<ID2>,
+ {
+ // SAFETY: We continue to treat this pointer as pinned after this call, since `ListArc`
+ // implicitly pins its value.
+ Self::pair_from_unique(unsafe { Pin::into_inner_unchecked(unique) })
+ }
+
+ /// Transmutes an [`Arc`] into a `ListArc` without updating the tracking inside `T`.
+ ///
+ /// # Safety
+ ///
+ /// * The value must not already have a `ListArc` reference.
+ /// * The tracking inside `T` must think that there is a `ListArc` reference.
+ #[inline]
+ unsafe fn transmute_from_arc(me: Arc<T>) -> Self {
+ // INVARIANT: By the safety requirements, the invariants on `ListArc` are satisfied.
+ // SAFETY: ListArc is repr(transparent).
+ unsafe { core::mem::transmute(me) }
+ }
+
+ /// Transmutes a `ListArc` into an [`Arc`] without updating the tracking inside `T`.
+ ///
+ /// After this call, the tracking inside `T` will still think that there is a `ListArc`
+ /// reference.
+ #[inline]
+ fn transmute_to_arc(self) -> Arc<T> {
+ // 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 by [`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` reference.
+ #[inline]
+ pub unsafe fn from_raw(ptr: *const T) -> Self {
+ // SAFETY: The pointer satisfies the safety requirements for `Arc::from_raw`.
+ let arc = unsafe { Arc::from_raw(ptr) };
+ // SAFETY: The value doesn't already have a `ListArc` reference, but the tracking thinks it
+ // does.
+ unsafe { Self::transmute_from_arc(arc) }
+ }
+
+ /// Converts the `ListArc` into an [`Arc`].
+ #[inline]
+ pub fn into_arc(self) -> Arc<T> {
+ let arc = 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<T> {
+ 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<T> {
+ &self.arc
+ }
+
+ /// Returns an [`ArcBorrow`] from the given [`ListArc`].
+ ///
+ /// This is useful when the argument of a function call is an [`ArcBorrow`] (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 underlying object.
+ #[inline]
+ pub fn ptr_eq(this: &Self, other: &Self) -> bool {
+ Arc::ptr_eq(&this.arc, &other.arc)
+ }
+}
+
+impl<T, const ID: u64> Deref for ListArc<T, ID>
+where
+ T: ListArcSafe<ID> + ?Sized,
+{
+ type Target = T;
+
+ #[inline]
+ fn deref(&self) -> &Self::Target {
+ self.arc.deref()
+ }
+}
+
+impl<T, const ID: u64> Drop for ListArc<T, ID>
+where
+ T: ListArcSafe<ID> + ?Sized,
+{
+ #[inline]
+ fn drop(&mut self) {
+ // SAFETY: There is no longer a `ListArc`, but the tracking thinks there is by the type
+ // invariants on `Self`.
+ unsafe { T::on_drop_list_arc(&self.arc) };
+ }
+}
+
+// This is to allow [`ListArc`] (and variants) to be used as the type of `self`.
+impl<T, const ID: u64> core::ops::Receiver for ListArc<T, ID> where T: ListArcSafe<ID> + ?Sized {}
+
+// This is to allow coercion from `ListArc<T>` to `ListArc<U>` if `T` can be converted to the
+// dynamically-sized type (DST) `U`.
+impl<T, U, const ID: u64> core::ops::CoerceUnsized<ListArc<U, ID>> for ListArc<T, ID>
+where
+ T: ListArcSafe<ID> + Unsize<U> + ?Sized,
+ U: ListArcSafe<ID> + ?Sized,
+{
+}
+
+// This is to allow `ListArc<U>` to be dispatched on when `ListArc<T>` can be coerced into
+// `ListArc<U>`.
+impl<T, U, const ID: u64> core::ops::DispatchFromDyn<ListArc<U, ID>> for ListArc<T, ID>
+where
+ T: ListArcSafe<ID> + Unsize<U> + ?Sized,
+ U: ListArcSafe<ID> + ?Sized,
+{
+}
--
2.44.0.478.gd926399ef9-goog
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<T: ?Sized> {
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 <[email protected]>
---
rust/kernel/list.rs | 4 +-
rust/kernel/list/arc.rs | 133 ++++++++++++++++++++++++++++++++++++++++++++++--
2 files changed, 133 insertions(+), 4 deletions(-)
diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs
index fb16ea43b2ba..c5caa0f6105c 100644
--- a/rust/kernel/list.rs
+++ b/rust/kernel/list.rs
@@ -5,4 +5,6 @@
//! A linked list implementation.
mod arc;
-pub use self::arc::{impl_list_arc_safe, ListArc, ListArcSafe};
+pub use self::arc::{
+ impl_list_arc_safe, AtomicListArcTracker, ListArc, ListArcSafe, TryNewListArc,
+};
diff --git a/rust/kernel/list/arc.rs b/rust/kernel/list/arc.rs
index 59d43f7a165e..5c27491a5889 100644
--- a/rust/kernel/list/arc.rs
+++ b/rust/kernel/list/arc.rs
@@ -8,9 +8,10 @@
use crate::prelude::*;
use crate::sync::{Arc, ArcBorrow, UniqueArc};
use core::alloc::AllocError;
-use core::marker::Unsize;
+use core::marker::{PhantomPinned, Unsize};
use core::ops::Deref;
use core::pin::Pin;
+use core::sync::atomic::{AtomicBool, Ordering};
/// Declares that this type has some way to ensure that there is exactly one `ListArc` instance for
/// this id.
@@ -33,19 +34,64 @@ pub trait ListArcSafe<const ID: u64 = 0> {
unsafe fn on_drop_list_arc(&self);
}
+/// Declares that this type is able to safely attempt to create `ListArc`s at any time.
+///
+/// # Safety
+///
+/// Implementers must ensure that `try_new_list_arc` does not return `true` if a `ListArc` already
+/// exists.
+pub unsafe trait TryNewListArc<const ID: u64 = 0>: ListArcSafe<ID> {
+ /// Attempts to convert an `Arc<Self>` into an `ListArc<Self>`. Returns `true` if the
+ /// conversion was successful.
+ fn try_new_list_arc(&self) -> bool;
+}
+
/// Declares that this type supports [`ListArc`].
///
-/// When using this macro, it will only be possible to create a [`ListArc`] from a [`UniqueArc`].
+/// When using this macro, you may choose between the `untracked` strategy where it is not tracked
+/// whether a [`ListArc`] exists, and the `tracked_by` strategy where the tracking is deferred to a
+/// field of the struct. The `tracked_by` strategy can be combined with a field of type
+/// [`AtomicListArcTracker`] to track whether a [`ListArc`] exists.
#[macro_export]
macro_rules! impl_list_arc_safe {
(impl$({$($generics:tt)*})? ListArcSafe<$num:tt> for $t:ty { untracked; } $($rest:tt)*) => {
- impl$(<$($generics)*>)? $crate::list::ListArcSafe<$num> for $t {
+ impl$(<$($generics)*>)? ListArcSafe<$num> for $t {
unsafe fn on_create_list_arc_from_unique(&mut self) {}
unsafe fn on_drop_list_arc(&self) {}
}
$crate::list::impl_list_arc_safe! { $($rest)* }
};
+ (impl$({$($generics:tt)*})? ListArcSafe<$num:tt> for $t:ty {
+ tracked_by $field:ident : $fty:ty;
+ } $($rest:tt)*) => {
+ impl$(<$($generics)*>)? ListArcSafe<$num> for $t {
+ unsafe fn on_create_list_arc_from_unique(&mut self) {
+ let me = self as *mut Self;
+ let field: *mut $fty = unsafe { ::core::ptr::addr_of_mut!((*me).$field) };
+ unsafe { <$fty as $crate::list::ListArcSafe<$num>>::on_create_list_arc_from_unique(
+ &mut *field
+ ) };
+ }
+ unsafe fn on_drop_list_arc(&self) {
+ let me = self as *const Self;
+ let field: *const $fty = unsafe { ::core::ptr::addr_of!((*me).$field) };
+ unsafe { <$fty as $crate::list::ListArcSafe<$num>>::on_drop_list_arc(&*field) };
+ }
+ }
+ unsafe impl$(<$($generics)*>)? TryNewListArc<$num> for $t
+ where
+ $fty: TryNewListArc<$num>,
+ {
+ fn try_new_list_arc(&self) -> bool {
+ let me = self as *const Self;
+ let field: *const $fty = unsafe { ::core::ptr::addr_of!((*me).$field) };
+ unsafe { <$fty as $crate::list::TryNewListArc<$num>>::try_new_list_arc(&*field) }
+ }
+ }
+ $crate::list::impl_list_arc_safe! { $($rest)* }
+ };
+
() => {};
}
pub use impl_list_arc_safe;
@@ -166,6 +212,36 @@ pub fn pair_from_pin_unique<const ID2: u64>(
Self::pair_from_unique(unsafe { Pin::into_inner_unchecked(unique) })
}
+ /// Try to create a new `ListArc`.
+ ///
+ /// This fails if this value already has a `ListArc`.
+ pub fn try_from_arc(arc: Arc<T>) -> Result<Self, Arc<T>>
+ where
+ T: TryNewListArc<ID>,
+ {
+ if arc.try_new_list_arc() {
+ // SAFETY: The `try_new_list_arc` method returned true, so the tracking now thinks that
+ // a `ListArc` exists, so we can create one.
+ Ok(unsafe { Self::transmute_from_arc(arc) })
+ } else {
+ Err(arc)
+ }
+ }
+
+ /// Try to create a new `ListArc`.
+ ///
+ /// If it's not possible to create a new `ListArc`, then the `Arc` is dropped. This will never
+ /// run the destructor of the value.
+ pub fn try_from_arc_or_drop(arc: Arc<T>) -> Option<Self>
+ where
+ T: TryNewListArc<ID>,
+ {
+ match Self::try_from_arc(arc) {
+ Ok(list_arc) => Some(list_arc),
+ Err(arc) => Arc::into_unique_or_drop(arc).map(Self::from_pin_unique),
+ }
+ }
+
/// Transmutes an [`Arc`] into a `ListArc` without updating the tracking inside `T`.
///
/// # Safety
@@ -300,3 +376,54 @@ impl<T, U, const ID: u64> core::ops::DispatchFromDyn<ListArc<U, ID>> for ListArc
U: ListArcSafe<ID> + ?Sized,
{
}
+
+/// A utility for tracking whether a [`ListArc`] exists using an atomic.
+///
+/// # Invariant
+///
+/// If the boolean is `false`, then there is no [`ListArc`] for this value.
+#[repr(transparent)]
+pub struct AtomicListArcTracker<const ID: u64 = 0> {
+ inner: AtomicBool,
+ _pin: PhantomPinned,
+}
+
+impl<const ID: u64> AtomicListArcTracker<ID> {
+ /// Creates a new initializer for this type.
+ pub fn new() -> impl PinInit<Self> {
+ // INVARIANT: Pin-init initializers can't be used on an existing `Arc`, so this value will
+ // not be constructed in an `Arc` that already has a `ListArc`.
+ Self {
+ inner: AtomicBool::new(false),
+ _pin: PhantomPinned,
+ }
+ }
+}
+
+impl<const ID: u64> ListArcSafe<ID> for AtomicListArcTracker<ID> {
+ unsafe fn on_create_list_arc_from_unique(&mut self) {
+ // INVARIANT: We just created a ListArc, so the boolean should be true.
+ *self.inner.get_mut() = 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 destruction of any
+// previous `ListArc`, so if there was a previous `ListArc`, then the destruction of the previous
+// `ListArc` happens-before the creation of the new `ListArc`.
+unsafe impl<const ID: u64> TryNewListArc<ID> for AtomicListArcTracker<ID> {
+ fn try_new_list_arc(&self) -> bool {
+ // INVARIANT: If this method returns true, then the boolean used to be false, and is no
+ // longer false, so it is okay for the caller to create a new [`ListArc`].
+ self.inner
+ .compare_exchange(false, true, Ordering::Acquire, Ordering::Relaxed)
+ .is_ok()
+ }
+}
--
2.44.0.478.gd926399ef9-goog
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 <[email protected]>
---
rust/kernel/list.rs | 115 ++++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 115 insertions(+)
diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs
index c5caa0f6105c..76597c49fa56 100644
--- a/rust/kernel/list.rs
+++ b/rust/kernel/list.rs
@@ -4,7 +4,122 @@
//! A linked list implementation.
+use crate::init::PinInit;
+use crate::types::Opaque;
+use core::ptr;
+
mod arc;
pub use self::arc::{
impl_list_arc_safe, AtomicListArcTracker, ListArc, ListArcSafe, TryNewListArc,
};
+
+/// Implemented by types where a [`ListArc<Self>`] can be inserted into a `List`.
+///
+/// # Safety
+///
+/// Implementers must ensure that they provide the guarantees documented on the three methods
+/// below.
+///
+/// [`ListArc<Self>`]: ListArc
+pub unsafe trait ListItem<const ID: u64 = 0>: ListArcSafe<ID> {
+ /// Views the [`ListLinks`] for this value.
+ ///
+ /// # Guarantees
+ ///
+ /// * If there is a currently active call to `prepare_to_insert`, then this returns the same
+ /// pointer as the one returned by the currently active call to `prepare_to_insert`.
+ /// * If there is no currently active call to `prepare_to_insert`, then 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<ID>;
+
+ /// View the full value given its [`ListLinks`] field.
+ ///
+ /// Can only be used when the value is in a list.
+ ///
+ /// # Guarantees
+ ///
+ /// * Returns the same pointer as the one passed to the previous call to `prepare_to_insert`.
+ /// * The returned pointer is valid until the next call to `post_remove`.
+ ///
+ /// # Safety
+ ///
+ /// * The provided pointer must originate from the previous call to `prepare_to_insert`, or
+ /// from a call to `view_links` that happened after the previous call to `prepare_to_insert`.
+ /// * Since the previous call to `prepare_to_insert`, the `post_remove` method must not have
+ /// been called.
+ unsafe fn view_value(me: *mut ListLinks<ID>) -> *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<ID>;
+
+ /// This undoes a previous call to `prepare_to_insert`.
+ ///
+ /// # Guarantees
+ ///
+ /// The returned pointer is the pointer that was originally passed to `prepare_to_insert`.
+ ///
+ /// The caller is free to recreate the `ListArc` after this call.
+ ///
+ /// # Safety
+ ///
+ /// The provided pointer must be the pointer returned by the previous call to
+ /// `prepare_to_insert`.
+ unsafe fn post_remove(me: *mut ListLinks<ID>) -> *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<const ID: u64 = 0> {
+ #[allow(dead_code)]
+ inner: Opaque<ListLinksFields>,
+}
+
+// SAFETY: The next/prev fields of a ListLinks can be moved across thread boundaries.
+unsafe impl<const ID: u64> Send for ListLinks<ID> {}
+// SAFETY: The type is opaque so immutable references to a ListLinks are useless. Therefore, it's
+// okay to have immutable access to a ListLinks from several threads at once.
+unsafe impl<const ID: u64> Sync for ListLinks<ID> {}
+
+impl<const ID: u64> ListLinks<ID> {
+ /// Creates a new initializer for this type.
+ pub fn new() -> impl PinInit<Self> {
+ // 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(),
+ }),
+ }
+ }
+}
--
2.44.0.478.gd926399ef9-goog
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 <[email protected]>
---
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-goog
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 = iter.next();
iter.remove();
use(item);
If `iter` was a cursor instead of an iterator, then `item` will be
considered a borrow of `iter`. Since `remove` destroys `iter`, this
means that the borrow-checker will prevent uses of `item` after the call
to `remove`.
So there is a trade-off between supporting use in traditional for loops,
and supporting removal of elements as you iterate. Iterators and cursors
represents two different choices on that spectrum.
Rust Binder needs cursors for the list of death notifications that a
process is currently handling. When userspace tells Binder that it has
finished processing the death notification, Binder will iterate the list
to search for the relevant item and remove it.
Signed-off-by: Alice Ryhl <[email protected]>
---
rust/kernel/list.rs | 77 +++++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 77 insertions(+)
diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs
index 892705dd0571..47e52818c7bd 100644
--- a/rust/kernel/list.rs
+++ b/rust/kernel/list.rs
@@ -408,6 +408,20 @@ pub fn push_all_back(&mut self, other: &mut List<T, ID>) {
other.first = ptr::null_mut();
}
+ /// 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<Cursor<'_, T, ID>> {
+ 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. Otherwise, both pointers point
@@ -476,6 +490,69 @@ fn next(&mut self) -> Option<ArcBorrow<'a, T>> {
}
}
+/// A cursor into a [`List`].
+///
+/// # Invariants
+///
+/// The `current` pointer points a value in `list`.
+pub struct Cursor<'a, T: ?Sized + ListItem<ID>, const ID: u64 = 0> {
+ current: *mut ListLinksFields,
+ list: &'a mut List<T, ID>,
+}
+
+impl<'a, T: ?Sized + ListItem<ID>, 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 = unsafe { T::view_value(ListLinks::from_fields(self.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 cursor or the list. However, the `ArcBorrow` holds an immutable borrow
+ // on the cursor, which in turn holds an immutable borrow on the list, so any such
+ // mutable access requires first releasing the immutable borrow on the cursor.
+ // * Values in a list never have a `UniqueArc` reference.
+ unsafe { ArcBorrow::from_raw(me) }
+ }
+
+ /// Move the cursor to the next element.
+ pub fn next(self) -> Option<Cursor<'a, T, ID>> {
+ // SAFETY: The `current` field is always in a list.
+ let next = unsafe { (*self.current).next };
+
+ if next == self.list.first {
+ None
+ } else {
+ Some(Cursor {
+ current: next,
+ list: self.list,
+ })
+ }
+ }
+
+ /// Move the cursor to the previous element.
+ pub fn prev(self) -> Option<Cursor<'a, T, ID>> {
+ // SAFETY: The `current` field is always in a list.
+ let prev = unsafe { (*self.current).prev };
+
+ if self.current == self.list.first {
+ None
+ } else {
+ Some(Cursor {
+ current: prev,
+ list: self.list,
+ })
+ }
+ }
+
+ /// Remove the current element from the list.
+ pub fn remove(self) -> ListArc<T, ID> {
+ // SAFETY: The `current` pointer always points at a member of the list.
+ unsafe { self.list.remove_internal(self.current) }
+ }
+}
+
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> {
--
2.44.0.478.gd926399ef9-goog
Support linked lists that can have many different structs at once. This
is generally done using trait objects. The main challenge is figuring
what the struct is given only a pointer to the ListLinks.
We do this by storing a pointer to the struct next to the ListLinks
field. The container_of operation will then just read that pointer. When
the type is a trait object, that pointer will be a fat pointer whose
metadata is a vtable that tells you what kind of struct it is.
Heterogeneous lists are heavily used by Rust Binder. There are a lot of
so-called todo lists containing various events that need to be delivered
to userspace next time userspace calls into the driver. And there are
quite a few different todo item types: incoming transaction, changes to
refcounts, death notifications, and more.
Signed-off-by: Alice Ryhl <[email protected]>
---
rust/kernel/list.rs | 41 ++++++++++++++++-
rust/kernel/list/impl_list_item_mod.rs | 83 ++++++++++++++++++++++++++++++++++
2 files changed, 123 insertions(+), 1 deletion(-)
diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs
index 47e52818c7bd..68d03b100863 100644
--- a/rust/kernel/list.rs
+++ b/rust/kernel/list.rs
@@ -7,12 +7,16 @@
use crate::init::PinInit;
use crate::sync::ArcBorrow;
use crate::types::Opaque;
+use core::cell::UnsafeCell;
use core::iter::{DoubleEndedIterator, FusedIterator};
use core::marker::PhantomData;
+use core::mem::MaybeUninit;
use core::ptr;
mod impl_list_item_mod;
-pub use self::impl_list_item_mod::{impl_has_list_links, impl_list_item, HasListLinks};
+pub use self::impl_list_item_mod::{
+ impl_has_list_links, impl_has_list_links_self_ptr, impl_list_item, HasListLinks, HasSelfPtr,
+};
mod arc;
pub use self::arc::{
@@ -180,6 +184,41 @@ unsafe fn from_fields(me: *mut ListLinksFields) -> *mut Self {
}
}
+/// Similar to [`ListLinks`], but also contains a pointer to the full value.
+///
+/// This type can be used instead of [`ListLinks`] to support lists with trait objects.
+#[repr(C)]
+pub struct ListLinksSelfPtr<T: ?Sized, const ID: u64 = 0> {
+ /// The `ListLinks` field inside this value.
+ ///
+ /// This is public so that it can be used with `impl_has_list_links!`.
+ pub inner: ListLinks<ID>,
+ self_ptr: UnsafeCell<MaybeUninit<*const T>>,
+}
+
+unsafe impl<T: ?Sized + Send, const ID: u64> Send for ListLinksSelfPtr<T, ID> {}
+unsafe impl<T: ?Sized + Sync, const ID: u64> Sync for ListLinksSelfPtr<T, ID> {}
+
+impl<T: ?Sized, const ID: u64> ListLinksSelfPtr<T, ID> {
+ /// The offset from the [`ListLinks`] to the self pointer field.
+ pub const LIST_LINKS_SELF_PTR_OFFSET: usize = core::mem::offset_of!(Self, self_ptr);
+
+ /// Creates a new initializer for this type.
+ pub fn new() -> impl PinInit<Self> {
+ // INVARIANT: Pin-init initializers can't be used on an existing `Arc`, so this value will
+ // not be constructed in an `Arc` that already has a `ListArc`.
+ Self {
+ inner: ListLinks {
+ inner: Opaque::new(ListLinksFields {
+ prev: ptr::null_mut(),
+ next: ptr::null_mut(),
+ }),
+ },
+ self_ptr: UnsafeCell::new(MaybeUninit::zeroed()),
+ }
+ }
+}
+
impl<T: ?Sized + ListItem<ID>, const ID: u64> List<T, ID> {
/// Creates a new empty list.
pub const fn new() -> Self {
diff --git a/rust/kernel/list/impl_list_item_mod.rs b/rust/kernel/list/impl_list_item_mod.rs
index 9e2f6d6d4786..6884d8a3e710 100644
--- a/rust/kernel/list/impl_list_item_mod.rs
+++ b/rust/kernel/list/impl_list_item_mod.rs
@@ -61,6 +61,49 @@ unsafe fn raw_get_list_links(ptr: *mut Self) -> *mut $crate::list::ListLinks$(<$
}
pub use impl_has_list_links;
+/// Declares that the `ListLinks<ID>` field in this struct is inside a `ListLinksSelfPtr<T, ID>`.
+///
+/// # Safety
+///
+/// The `ListLinks<ID>` field of this struct at the offset `HasListLinks<ID>::OFFSET` must be
+/// inside a `ListLinksSelfPtr<T, ID>`.
+pub unsafe trait HasSelfPtr<T: ?Sized, const ID: u64 = 0>
+where
+ Self: HasListLinks<ID>,
+{
+}
+
+/// Implements the [`HasListLinks`] and [`HasSelfPtr`] traits for the given 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 }
+ )*) => {$(
+ // SAFETY: The implementation of `raw_get_list_links` only compiles 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 = ::core::mem::offset_of!(Self, $field) as usize;
+
+ #[inline]
+ unsafe fn raw_get_list_links(ptr: *mut Self) -> *mut $crate::list::ListLinks$(<$id>)? {
+ // SAFETY: The caller promises that the pointer is not dangling.
+ let ptr: *mut $crate::list::ListLinksSelfPtr<$item_type $(, $id)?> =
+ unsafe { ::core::ptr::addr_of_mut!((*ptr).$field) };
+ ptr.cast()
+ }
+ }
+ )*};
+}
+pub use impl_has_list_links_self_ptr;
+
/// Implements the [`ListItem`] trait for the given type.
///
/// Assumes that the type implements [`HasListLinks`].
@@ -94,5 +137,45 @@ unsafe fn post_remove(me: *mut ListLinks<$num>) -> *const Self {
}
}
};
+
+ (
+ impl$({$($generics:tt)*})? ListItem<$num:tt> for $t:ty {
+ using ListLinksSelfPtr;
+ } $($rest:tt)*
+ ) => {
+ unsafe impl$(<$($generics)*>)? ListItem<$num> for $t {
+ unsafe fn prepare_to_insert(me: *const Self) -> *mut ListLinks<$num> {
+ let links_field = unsafe { Self::view_links(me) };
+
+ let spoff = ListLinksSelfPtr::<Self, $num>::LIST_LINKS_SELF_PTR_OFFSET;
+ let self_ptr = unsafe { (links_field as *const u8).add(spoff)
+ as *const ::core::cell::UnsafeCell<*const Self> };
+ let cell_inner = ::core::cell::UnsafeCell::raw_get(self_ptr);
+
+ unsafe { ::core::ptr::write(cell_inner, me) };
+ links_field
+ }
+
+ unsafe fn view_links(me: *const Self) -> *mut ListLinks<$num> {
+ unsafe {
+ <Self as HasListLinks<$num>>::raw_get_list_links(me.cast_mut())
+ }
+ }
+
+ unsafe fn view_value(links_field: *mut ListLinks<$num>) -> *const Self {
+ let spoff = ListLinksSelfPtr::<Self, $num>::LIST_LINKS_SELF_PTR_OFFSET;
+ let self_ptr = unsafe { (links_field as *const u8).add(spoff)
+ as *const ::core::cell::UnsafeCell<*const Self> };
+ let cell_inner = ::core::cell::UnsafeCell::raw_get(self_ptr);
+ unsafe {
+ ::core::ptr::read(cell_inner)
+ }
+ }
+
+ unsafe fn post_remove(me: *mut ListLinks<$num>) -> *const Self {
+ unsafe { Self::view_value(me) }
+ }
+ }
+ };
}
pub use impl_list_item;
--
2.44.0.478.gd926399ef9-goog
One way to explain what `ListArc` does is that it controls exclusive
access to the prev/next pointer field in a refcounted object. The
feature of having a special reference to a refcounted object with
exclusive access to specific fields is useful for other things, so
provide a general utility for that.
This is used by Rust Binder to keep track of which processes have a
reference to a given node. This involves an object for each process/node
pair, that is referenced by both the process and the node. For some
fields in this object, only the process's reference needs to access
them (and it needs mutable access), so Binder uses a ListArc to give the
process's reference exclusive access.
Signed-off-by: Alice Ryhl <[email protected]>
---
rust/kernel/list.rs | 3 ++
rust/kernel/list/arc_field.rs | 94 +++++++++++++++++++++++++++++++++++++++++++
2 files changed, 97 insertions(+)
diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs
index 68d03b100863..a59b35b67e9b 100644
--- a/rust/kernel/list.rs
+++ b/rust/kernel/list.rs
@@ -23,6 +23,9 @@
impl_list_arc_safe, AtomicListArcTracker, ListArc, ListArcSafe, TryNewListArc,
};
+mod arc_field;
+pub use self::arc_field::{define_list_arc_field_getter, ListArcField};
+
/// A linked list.
///
/// All elements in this linked list will be [`ListArc`] references to the value. Since a value can
diff --git a/rust/kernel/list/arc_field.rs b/rust/kernel/list/arc_field.rs
new file mode 100644
index 000000000000..936fd97bc5ac
--- /dev/null
+++ b/rust/kernel/list/arc_field.rs
@@ -0,0 +1,94 @@
+// SPDX-License-Identifier: GPL-2.0
+
+// Copyright (C) 2024 Google LLC.
+
+//! A field that is exclusively owned by a [`ListArc`].
+//!
+//! This can be used to have reference counted struct where one of the reference counted pointers
+//! has exclusive access to a field of the struct.
+//!
+//! [`ListArc`]: crate::list::ListArc
+
+use core::cell::UnsafeCell;
+
+/// A field owned by a specific `ListArc`.
+pub struct ListArcField<T, const ID: u64 = 0> {
+ value: UnsafeCell<T>,
+}
+
+// SAFETY: If the inner type is thread-safe, then it's also okay for `ListArc` to be thread-safe.
+unsafe impl<T: Send + Sync, const ID: u64> Send for ListArcField<T, ID> {}
+// SAFETY: If the inner type is thread-safe, then it's also okay for `ListArc` to be thread-safe.
+unsafe impl<T: Send + Sync, const ID: u64> Sync for ListArcField<T, ID> {}
+
+impl<T, const ID: u64> ListArcField<T, ID> {
+ /// 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 `ListArcField`.
+ ///
+ /// 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 this field.
+ ///
+ /// # Safety
+ ///
+ /// The caller must have shared access to the `ListArc<ID>` 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<ID>` containing 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 they also have exclusive
+ // access to this field.
+ unsafe { &mut *self.value.get() }
+ }
+}
+
+/// Defines.
+#[macro_export]
+macro_rules! define_list_arc_field_getter {
+ ($pub:vis fn $name:ident(&self $(<$id:tt>)?) -> &$typ:ty { $field:ident }
+ $($rest:tt)*
+ ) => {
+ $pub fn $name<'a>(self: &'a $crate::list::ListArc<Self $(, $id)?>) -> &'a $typ {
+ let field = &(&**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 { $field:ident }
+ $($rest:tt)*
+ ) => {
+ $pub fn $name<'a>(self: &'a mut $crate::list::ListArc<Self $(, $id)?>) -> &'a mut $typ {
+ let field = &(&**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)*);
+ };
+
+ () => {};
+}
+pub use define_list_arc_field_getter;
--
2.44.0.478.gd926399ef9-goog
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 <[email protected]>
---
rust/kernel/list.rs | 3 ++
rust/kernel/list/impl_list_item_mod.rs | 98 ++++++++++++++++++++++++++++++++++
2 files changed, 101 insertions(+)
diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs
index 76597c49fa56..7af5109500f2 100644
--- a/rust/kernel/list.rs
+++ b/rust/kernel/list.rs
@@ -8,6 +8,9 @@
use crate::types::Opaque;
use core::ptr;
+mod impl_list_item_mod;
+pub use self::impl_list_item_mod::{impl_has_list_links, impl_list_item, HasListLinks};
+
mod arc;
pub use self::arc::{
impl_list_arc_safe, AtomicListArcTracker, ListArc, ListArcSafe, TryNewListArc,
diff --git a/rust/kernel/list/impl_list_item_mod.rs b/rust/kernel/list/impl_list_item_mod.rs
new file mode 100644
index 000000000000..9e2f6d6d4786
--- /dev/null
+++ b/rust/kernel/list/impl_list_item_mod.rs
@@ -0,0 +1,98 @@
+// SPDX-License-Identifier: GPL-2.0
+
+// Copyright (C) 2024 Google LLC.
+
+//! Helpers for implementing list traits safely.
+
+use crate::list::ListLinks;
+
+/// Declares that this type has a `ListLinks<ID>` field at a fixed offset.
+///
+/// This trait is only used to help implement `ListItem` safely. If `ListItem` is implemented
+/// manually, then this trait is not needed.
+///
+/// # Safety
+///
+/// All values of this type must have a `ListLinks<ID>` field at the given offset.
+pub unsafe trait HasListLinks<const ID: u64 = 0> {
+ /// The offset of the `ListLinks` field.
+ const OFFSET: usize;
+
+ /// Returns a pointer to the [`ListLinks<T, ID>`] field.
+ ///
+ /// # Safety
+ ///
+ /// The provided pointer must point at a valid struct of type `Self`.
+ ///
+ /// [`ListLinks<T, ID>`]: ListLinks
+ // We don't really need this method, but it's necessary for the implementation of
+ // `impl_has_work!` to be correct.
+ #[inline]
+ unsafe fn raw_get_list_links(ptr: *mut Self) -> *mut ListLinks<ID> {
+ // SAFETY: The caller promises that the pointer is valid.
+ unsafe { (ptr as *mut u8).add(Self::OFFSET) as *mut ListLinks<ID> }
+ }
+}
+
+/// 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)* }
+ )*) => {$(
+ // SAFETY: The implementation of `raw_get_list_links` only compiles if the field has the
+ // right type.
+ unsafe impl$(<$($implarg),*>)? $crate::list::HasListLinks$(<$id>)? for
+ $self $(<$($selfarg),*>)?
+ {
+ const OFFSET: usize = ::core::mem::offset_of!(Self, $($field).*) as usize;
+
+ #[inline]
+ unsafe fn raw_get_list_links(ptr: *mut Self) -> *mut $crate::list::ListLinks$(<$id>)? {
+ // SAFETY: The caller promises that the pointer is not dangling.
+ unsafe {
+ ::core::ptr::addr_of_mut!((*ptr)$(.$field)*)
+ }
+ }
+ }
+ )*};
+}
+pub use impl_has_list_links;
+
+/// Implements the [`ListItem`] trait for the given type.
+///
+/// Assumes that the type implements [`HasListLinks`].
+///
+/// [`ListItem`]: crate::list::ListItem
+#[macro_export]
+macro_rules! impl_list_item {
+ (
+ impl$({$($generics:tt)*})? ListItem<$num:tt> for $t:ty {
+ using ListLinks;
+ } $($rest:tt)*
+ ) => {
+ unsafe impl$(<$($generics)*>)? ListItem<$num> for $t {
+ unsafe fn view_links(me: *const Self) -> *mut ListLinks<$num> {
+ unsafe {
+ <Self as HasListLinks<$num>>::raw_get_list_links(me.cast_mut())
+ }
+ }
+
+ unsafe fn view_value(me: *mut ListLinks<$num>) -> *const Self {
+ let offset = <Self as HasListLinks<$num>>::OFFSET;
+ unsafe { (me as *const u8).sub(offset) as *const Self }
+ }
+
+ unsafe fn prepare_to_insert(me: *const Self) -> *mut ListLinks<$num> {
+ unsafe { Self::view_links(me) }
+ }
+
+ unsafe fn post_remove(me: *mut ListLinks<$num>) -> *const Self {
+ unsafe { Self::view_value(me) }
+ }
+ }
+ };
+}
+pub use impl_list_item;
--
2.44.0.478.gd926399ef9-goog
Add the actual linked list itself.
The linked list uses the following design: The List type itself just has
a single pointer to the first element of the list. And the actual list
items then form a cycle. So the last item is `first->prev`.
This is slightly different from the usual kernel linked list. Matching
that exactly would amount to giving List two pointers, and having it be
part of the cycle of items. This alternate design has the advantage that
the cycle is never completely empty, which can reduce the number of
branches in some cases. However, it also has the disadvantage that List
must be pinned, which this design is trying to avoid.
Having the list items form a cycle rather than having null pointers at
the beginning/end is convenient for several reasons. For one, it lets us
store only one pointer in List, and it simplifies the implementation of
several functions.
Unfortunately, the `remove` function that removes an arbitrary element
from the list has to be unsafe. This is needed because there is no way
to handle the case where you pass an element from the wrong list. For
example, if it is the first element of some other list, then that other
list's `first` pointer would not be updated. Similarly, it could be a
data race if you try to remove it from two different lists in parallel.
(There's no problem with passing `remove` an item that's not in any
list. Additionally, other removal methods such as `pop_front` need not
be unsafe, as they can't be used to remove items from another list.)
Signed-off-by: Alice Ryhl <[email protected]>
---
rust/kernel/list.rs | 294 +++++++++++++++++++++++++++++++++++++++++++++++-
rust/kernel/list/arc.rs | 6 +-
2 files changed, 295 insertions(+), 5 deletions(-)
diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs
index 7af5109500f2..7e9ed802b26b 100644
--- a/rust/kernel/list.rs
+++ b/rust/kernel/list.rs
@@ -6,6 +6,7 @@
use crate::init::PinInit;
use crate::types::Opaque;
+use core::marker::PhantomData;
use core::ptr;
mod impl_list_item_mod;
@@ -16,7 +17,41 @@
impl_list_arc_safe, AtomicListArcTracker, ListArc, ListArcSafe, TryNewListArc,
};
-/// Implemented by types where a [`ListArc<Self>`] 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 ensures that the same
+/// prev/next pointers are not used for several linked lists.
+///
+/// # Invariants
+///
+/// If the list is empty, then `first` is null. Otherwise, it points at the links field of the
+/// first element of this list. The prev/next pointers of items in the list will always form a
+/// cycle. This means that prev/next pointers for an item in a list are never null and never
+/// dangling.
+pub struct List<T: ?Sized + ListItem<ID>, const ID: u64 = 0> {
+ first: *mut ListLinksFields,
+ _ty: PhantomData<ListArc<T, ID>>,
+}
+
+// SAFETY: This is a container of `ListArc<T, ID>`, and access to the container allows the same
+// type of access to the `ListArc<T, ID>` elements.
+unsafe impl<T, const ID: u64> Send for List<T, ID>
+where
+ ListArc<T, ID>: Send,
+ T: ?Sized + ListItem<ID>,
+{
+}
+// SAFETY: This is a container of `ListArc<T, ID>`, and access to the container allows the same
+// type of access to the `ListArc<T, ID>` elements.
+unsafe impl<T, const ID: u64> Sync for List<T, ID>
+where
+ ListArc<T, ID>: Sync,
+ T: ?Sized + ListItem<ID>,
+{
+}
+
+/// Implemented by types where a [`ListArc<Self>`] can be inserted into a [`List`].
///
/// # Safety
///
@@ -56,7 +91,7 @@ pub unsafe trait ListItem<const ID: u64 = 0>: ListArcSafe<ID> {
/// been called.
unsafe fn view_value(me: *mut ListLinks<ID>) -> *const Self;
- /// This is called when an item is inserted into a `List`.
+ /// This is called when an item is inserted into a [`List`].
///
/// # Guarantees
///
@@ -103,7 +138,6 @@ struct ListLinksFields {
/// The fields are null if and only if this item is not in a list.
#[repr(transparent)]
pub struct ListLinks<const ID: u64 = 0> {
- #[allow(dead_code)]
inner: Opaque<ListLinksFields>,
}
@@ -125,4 +159,258 @@ pub fn new() -> impl PinInit<Self> {
}),
}
}
+
+ /// # Safety
+ ///
+ /// The pointer must be dereferencable.
+ #[inline]
+ unsafe fn fields(me: *mut Self) -> *mut ListLinksFields {
+ // SAFETY: The caller promises that the pointer is valid.
+ unsafe { Opaque::raw_get(ptr::addr_of!((*me).inner)) }
+ }
+
+ /// # Safety
+ ///
+ /// The pointer must be dereferencable.
+ #[inline]
+ unsafe fn from_fields(me: *mut ListLinksFields) -> *mut Self {
+ me.cast()
+ }
+}
+
+impl<T: ?Sized + ListItem<ID>, const ID: u64> List<T, ID> {
+ /// 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<T, ID>) {
+ let item = unsafe { ListLinks::fields(T::prepare_to_insert(ListArc::into_raw(item))) };
+
+ if self.first.is_null() {
+ self.first = item;
+ // SAFETY: The caller just gave us ownership of these fields.
+ // INVARIANT: A linked list with one item should be cyclic.
+ unsafe {
+ (*item).next = item;
+ (*item).prev = item;
+ }
+ } else {
+ let next = self.first;
+ // SAFETY: We just checked that `next` is non-null.
+ let prev = unsafe { (*next).prev };
+ // SAFETY: Pointers in a linked list are never dangling, and the caller just gave us
+ // ownership of the fields on `item`.
+ // INVARIANT: This correctly inserts `item` between `prev` and `next`.
+ unsafe {
+ (*item).next = next;
+ (*item).prev = prev;
+ (*prev).next = item;
+ (*next).prev = item;
+ }
+ }
+ }
+
+ /// Add the provided item to the front of the list.
+ pub fn push_front(&mut self, item: ListArc<T, ID>) {
+ let item = unsafe { ListLinks::fields(T::prepare_to_insert(ListArc::into_raw(item))) };
+
+ if self.first.is_null() {
+ // SAFETY: The caller just gave us ownership of these fields.
+ // INVARIANT: A linked list with one item should be cyclic.
+ unsafe {
+ (*item).next = item;
+ (*item).prev = item;
+ }
+ } else {
+ let next = self.first;
+ // SAFETY: We just checked that `next` is non-null.
+ let prev = unsafe { (*next).prev };
+ // SAFETY: Pointers in a linked list are never dangling, and the caller just gave us
+ // ownership of the fields on `item`.
+ // INVARIANT: This correctly inserts `item` between `prev` and `next`.
+ unsafe {
+ (*item).next = next;
+ (*item).prev = prev;
+ (*prev).next = item;
+ (*next).prev = item;
+ }
+ }
+ self.first = item;
+ }
+
+ /// Removes the last item from this list.
+ pub fn pop_back(&mut self) -> Option<ListArc<T, ID>> {
+ if self.first.is_null() {
+ return None;
+ }
+
+ // SAFETY: We just checked that the list is not empty.
+ let last = 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<ListArc<T, ID>> {
+ if self.first.is_null() {
+ return None;
+ }
+
+ // SAFETY: The first item of this list is in this list.
+ Some(unsafe { self.remove_internal(self.first) })
+ }
+
+ /// Removes the provided item from this list and returns it.
+ ///
+ /// This returns `None` if the item is not in the list.
+ ///
+ /// # Safety
+ ///
+ /// The provided item must not be in a different linked list.
+ pub unsafe fn remove(&mut self, item: &T) -> Option<ListArc<T, ID>> {
+ let mut item = 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-only 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 } = 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 raw pointer that was
+ // obtained without going through a pointer->reference->pointer conversion rountrip.
+ // This ensures that the list is valid under the more restrictive strict provenance
+ // ruleset.
+ //
+ // SAFETY: We just checked that `next` is not null, and it's not dangling by the
+ // list invariants.
+ unsafe {
+ debug_assert_eq!(item, (*next).prev);
+ item = (*next).prev;
+ }
+
+ // SAFETY: We just checked that `item` is in a list, so the caller guarantees that it
+ // is in this list. The pointers are in the right order.
+ Some(unsafe { self.remove_internal_inner(item, next, prev) })
+ } else {
+ None
+ }
+ }
+
+ /// Removes the provided item from the list.
+ ///
+ /// # Safety
+ ///
+ /// The pointer must point at an item in this list.
+ unsafe fn remove_internal(&mut self, item: *mut ListLinksFields) -> ListArc<T, ID> {
+ // 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 } = 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 ==
+ /// next` and `(*item).prev == prev`.
+ unsafe fn remove_internal_inner(
+ &mut self,
+ item: *mut ListLinksFields,
+ next: *mut ListLinksFields,
+ prev: *mut ListLinksFields,
+ ) -> ListArc<T, ID> {
+ // SAFETY: We have exclusive access to items in the list, and prev/next pointers are
+ // never null for items in a list.
+ //
+ // INVARIANT: There are three cases:
+ // * If the list has at least three items, then after removing the item, `prev` and `next`
+ // will be next to each other.
+ // * If the list has two items, then the remaining item will point at itself.
+ // * If the list has one item, then `next == prev == item`, so these writes have no effect
+ // due to the writes to `item` below.
+ unsafe {
+ (*next).prev = prev;
+ (*prev).next = next;
+ }
+ // SAFETY: We have exclusive access to items in the list.
+ // INVARIANT: The item is no longer in a list, so the pointers should be null.
+ unsafe {
+ (*item).prev = ptr::null_mut();
+ (*item).next = ptr::null_mut();
+ }
+ // INVARIANT: There are three cases:
+ // * If `item` was not the first item, then `self.first` should remain 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 setting `item->next` to null
+ // did not modify `prev->next`.
+ // * If `item` was the only item in the list, then `prev == item`, and we just set
+ // `item->next` to null, so this correctly sets `first` to null now that the list is
+ // empty.
+ if self.first == item {
+ // SAFETY: The `prev` field of an item in a list is never dangling.
+ self.first = unsafe { (*prev).next };
+ }
+
+ // SAFETY: We just removed a `ListArc` from the list, so we can turn it back into a
+ // `ListArc`.
+ unsafe { ListArc::from_raw(T::post_remove(ListLinks::from_fields(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<T, ID>) {
+ // 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 of `self`.
+ self.first = other.first;
+ } else if !other.is_empty() {
+ let other_first = other.first;
+ // SAFETY: The other list is not empty, so this pointer is valid.
+ let other_last = unsafe { (*other_first).prev };
+ let self_first = self.first;
+ // SAFETY: The self list is not empty, so this pointer is valid.
+ let self_last = unsafe { (*self_first).prev };
+
+ // SAFETY: We have exclusive access to both lists, so we can update the pointers.
+ // INVARIANT: This correctly sets the pointers to merge both lists. We do not need to
+ // update `self.first` because the first element of `self` does not change.
+ unsafe {
+ (*self_first).prev = other_last;
+ (*other_last).next = self_first;
+ (*self_last).next = other_first;
+ (*other_first).prev = self_last;
+ }
+ }
+
+ // INVARIANT: The other list is now empty, so update its pointer.
+ other.first = ptr::null_mut();
+ }
+}
+
+impl<T: ?Sized + ListItem<ID>, const ID: u64> Drop for List<T, ID> {
+ fn drop(&mut self) {
+ while let Some(item) = self.pop_front() {
+ drop(item);
+ }
+ }
}
diff --git a/rust/kernel/list/arc.rs b/rust/kernel/list/arc.rs
index 5c27491a5889..fb433a2cd253 100644
--- a/rust/kernel/list/arc.rs
+++ b/rust/kernel/list/arc.rs
@@ -101,8 +101,8 @@ fn try_new_list_arc(&self) -> bool {
/// The `ListArc` type can be thought of as a special reference to a 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.
+/// 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 to ensuring that a value has only one `ListArc` reference. The
/// simplest is to convert a [`UniqueArc`] into a `ListArc`. However, the refcounted object could
@@ -121,6 +121,8 @@ fn try_new_list_arc(&self) -> bool {
///
/// * Each reference counted object has at most one `ListArc` for each value of `ID`.
/// * The tracking inside `T` is aware that a `ListArc` reference exists.
+///
+/// [`List`]: crate::list::List
#[repr(transparent)]
pub struct ListArc<T, const ID: u64 = 0>
where
--
2.44.0.478.gd926399ef9-goog
On 02.04.24 14:17, Alice Ryhl wrote:
> +/// Declares that this type has a `ListLinks<ID>` field at a fixed offset.
> +///
> +/// This trait is only used to help implement `ListItem` safely. If `ListItem` is implemented
> +/// manually, then this trait is not needed.
> +///
> +/// # Safety
> +///
> +/// All values of this type must have a `ListLinks<ID>` field at the given offset.
> +pub unsafe trait HasListLinks<const ID: u64 = 0> {
> + /// The offset of the `ListLinks` field.
> + const OFFSET: usize;
> +
> + /// Returns a pointer to the [`ListLinks<T, ID>`] field.
> + ///
> + /// # Safety
> + ///
> + /// The provided pointer must point at a valid struct of type `Self`.
> + ///
> + /// [`ListLinks<T, ID>`]: ListLinks
> + // We don't really need this method, but it's necessary for the implementation of
> + // `impl_has_work!` to be correct.
> + #[inline]
> + unsafe fn raw_get_list_links(ptr: *mut Self) -> *mut ListLinks<ID> {
> + // SAFETY: The caller promises that the pointer is valid.
The caller only provides a valid pointer, this also needs the
requirement from the trait that `OFFSET` is correct.
--
Cheers,
Benno
> + unsafe { (ptr as *mut u8).add(Self::OFFSET) as *mut ListLinks<ID> }
> + }
> +}
On 02.04.24 14:17, Alice Ryhl wrote:
> diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs
> index 892705dd0571..47e52818c7bd 100644
> --- a/rust/kernel/list.rs
> +++ b/rust/kernel/list.rs
> @@ -408,6 +408,20 @@ pub fn push_all_back(&mut self, other: &mut List<T, ID>) {
> other.first = ptr::null_mut();
> }
>
> + /// 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<Cursor<'_, T, ID>> {
> + if self.first.is_null() {
> + None
> + } else {
> + Some(Cursor {
Missing INVARIANT comment.
> + 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. Otherwise, both pointers point
> @@ -476,6 +490,69 @@ fn next(&mut self) -> Option<ArcBorrow<'a, T>> {
> }
> }
>
> +/// A cursor into a [`List`].
> +///
> +/// # Invariants
> +///
> +/// The `current` pointer points a value in `list`.
> +pub struct Cursor<'a, T: ?Sized + ListItem<ID>, const ID: u64 = 0> {
> + current: *mut ListLinksFields,
> + list: &'a mut List<T, ID>,
> +}
> +
> +impl<'a, T: ?Sized + ListItem<ID>, 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 = unsafe { T::view_value(ListLinks::from_fields(self.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 cursor or the list. However, the `ArcBorrow` holds an immutable borrow
> + // on the cursor, which in turn holds an immutable borrow on the list, so any such
The cursor has a mutable borrow on the list.
> + // mutable access requires first releasing the immutable borrow on the cursor.
> + // * Values in a list never have a `UniqueArc` reference.
Is there some type invariant guaranteeing this?
--
Cheers,
Benno
> + unsafe { ArcBorrow::from_raw(me) }
> + }
> +
> + /// Move the cursor to the next element.
> + pub fn next(self) -> Option<Cursor<'a, T, ID>> {
> + // SAFETY: The `current` field is always in a list.
> + let next = unsafe { (*self.current).next };
> +
> + if next == self.list.first {
> + None
> + } else {
> + Some(Cursor {
> + current: next,
> + list: self.list,
> + })
> + }
> + }
On Wed, Apr 3, 2024 at 2:19 PM Benno Lossin <[email protected]> wrote:
>
> On 02.04.24 14:17, Alice Ryhl wrote:
> > diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs
> > index 892705dd0571..47e52818c7bd 100644
> > --- a/rust/kernel/list.rs
> > +++ b/rust/kernel/list.rs
> > @@ -408,6 +408,20 @@ pub fn push_all_back(&mut self, other: &mut List<T, ID>) {
> > other.first = ptr::null_mut();
> > }
> >
> > + /// 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<Cursor<'_, T, ID>> {
> > + if self.first.is_null() {
> > + None
> > + } else {
> > + Some(Cursor {
>
> Missing INVARIANT comment.
>
> > + 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. Otherwise, both pointers point
> > @@ -476,6 +490,69 @@ fn next(&mut self) -> Option<ArcBorrow<'a, T>> {
> > }
> > }
> >
> > +/// A cursor into a [`List`].
> > +///
> > +/// # Invariants
> > +///
> > +/// The `current` pointer points a value in `list`.
> > +pub struct Cursor<'a, T: ?Sized + ListItem<ID>, const ID: u64 = 0> {
> > + current: *mut ListLinksFields,
> > + list: &'a mut List<T, ID>,
> > +}
> > +
> > +impl<'a, T: ?Sized + ListItem<ID>, 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 = unsafe { T::view_value(ListLinks::from_fields(self.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 cursor or the list. However, the `ArcBorrow` holds an immutable borrow
> > + // on the cursor, which in turn holds an immutable borrow on the list, so any such
>
> The cursor has a mutable borrow on the list.
>
>
> > + // mutable access requires first releasing the immutable borrow on the cursor.
> > + // * Values in a list never have a `UniqueArc` reference.
>
> Is there some type invariant guaranteeing this?
The List owns a ListArc reference to the value. It would be unsound
for there to also be a UniqueArc reference to it.
Alice
On 02.04.24 14:16, Alice Ryhl wrote:
> +impl<T: ListArcSafe<ID>, const ID: u64> ListArc<T, ID> {
> + /// Constructs a new reference counted instance of `T`.
> + pub fn try_new(contents: T) -> Result<Self, AllocError> {
> + Ok(Self::from_unique(UniqueArc::try_new(contents)?))
> + }
> +
> + /// Use the given initializer to in-place initialize a `T`.
> + ///
> + /// If `T: !Unpin` it will not be able to move afterwards.
> + pub fn pin_init<E>(init: impl PinInit<T, E>) -> error::Result<Self>
> + where
> + Error: From<E>,
> + {
> + Ok(Self::from_pin_unique(UniqueArc::pin_init(init)?))
> + }
pin-init has a general trait for this: InPlaceInit. I don't know if the
other functions that it provides would help you.
> +}
> +
> +impl<T, const ID: u64> ListArc<T, ID>
> +where
> + T: ListArcSafe<ID> + ?Sized,
> +{
> + /// Convert a [`UniqueArc`] into a [`ListArc`].
> + pub fn from_unique(mut unique: UniqueArc<T>) -> Self {
> + // SAFETY: We have a `UniqueArc`, so there is no `ListArc`.
> + unsafe { T::on_create_list_arc_from_unique(&mut unique) };
> + let arc = Arc::from(unique);
> + // SAFETY: We just called `on_create_list_arc_from_unique` on an arc without a `ListArc`,
> + // so we can create a `ListArc`.
> + unsafe { Self::transmute_from_arc(arc) }
> + }
> +
> + /// Convert a pinned [`UniqueArc`] into a [`ListArc`].
> + pub fn from_pin_unique(unique: Pin<UniqueArc<T>>) -> Self {
> + // SAFETY: We continue to treat this pointer as pinned after this call, since `ListArc`
> + // implicitly pins its value.
This is not sufficient, since you also rely on `Self::from_unique` to
handle the parameter as if it were pinned, which it does not. Since it
calls `T::on_create_list_arc_from_unique` which just gets a `&mut self`
as a parameter and it could move stuff out.
> + Self::from_unique(unsafe { Pin::into_inner_unchecked(unique) })
> + }
> +
> + /// Like [`from_unique`], but creates two `ListArcs`.
> + ///
> + /// The two ids must be different.
> + ///
> + /// [`from_unique`]: ListArc::from_unique
> + pub fn pair_from_unique<const ID2: u64>(mut unique: UniqueArc<T>) -> (Self, ListArc<T, ID2>)
> + where
> + T: ListArcSafe<ID2>,
> + {
> + assert_ne!(ID, ID2);
Can this be a `build_assert!`?
> +
> + // SAFETY: We have a `UniqueArc`, so we can call this method.
I liked the comment from above better:
// SAFETY: We have a `UniqueArc`, so there is no `ListArc`.
Maybe use the variation "so there are no `ListArc`s for any ID.".
> + unsafe { <T as ListArcSafe<ID>>::on_create_list_arc_from_unique(&mut unique) };
> + // SAFETY: We have a `UniqueArc`, so we can call this method. The two ids are not equal.
> + unsafe { <T as ListArcSafe<ID2>>::on_create_list_arc_from_unique(&mut unique) };
> +
> + let arc1 = Arc::from(unique);
> + let arc2 = Arc::clone(&arc1);
> +
> + // SAFETY: We just called `on_create_list_arc_from_unique` on an arc without a `ListArc`,
> + // so we can create a `ListArc`.
I would mention the two different IDs again.
> + unsafe {
> + (
> + Self::transmute_from_arc(arc1),
> + ListArc::transmute_from_arc(arc2),
> + )
> + }
> + }
> +
> + /// Like [`pair_from_unique`], but uses a pinned arc.
> + ///
> + /// The two ids must be different.
> + ///
> + /// [`pair_from_unique`]: ListArc::pair_from_unique
> + pub fn pair_from_pin_unique<const ID2: u64>(
> + unique: Pin<UniqueArc<T>>,
> + ) -> (Self, ListArc<T, ID2>)
> + where
> + T: ListArcSafe<ID2>,
> + {
> + // SAFETY: We continue to treat this pointer as pinned after this call, since `ListArc`
> + // implicitly pins its value.
> + Self::pair_from_unique(unsafe { Pin::into_inner_unchecked(unique) })
> + }
> +
> + /// Transmutes an [`Arc`] into a `ListArc` without updating the tracking inside `T`.
> + ///
> + /// # Safety
> + ///
> + /// * The value must not already have a `ListArc` reference.
> + /// * The tracking inside `T` must think that there is a `ListArc` reference.
> + #[inline]
> + unsafe fn transmute_from_arc(me: Arc<T>) -> Self {
> + // INVARIANT: By the safety requirements, the invariants on `ListArc` are satisfied.
> + // SAFETY: ListArc is repr(transparent).
> + unsafe { core::mem::transmute(me) }
Why do you need a transmute here? Can't you just construct the struct?
Self { arc: me }
--
Cheers,
Benno
> + }
> +
On 02.04.24 14:17, Alice Ryhl wrote:
> +/// Implemented by types where a [`ListArc<Self>`] can be inserted into a `List`.
> +///
> +/// # Safety
> +///
> +/// Implementers must ensure that they provide the guarantees documented on the three methods
> +/// below.
> +///
> +/// [`ListArc<Self>`]: ListArc
> +pub unsafe trait ListItem<const ID: u64 = 0>: ListArcSafe<ID> {
> + /// Views the [`ListLinks`] for this value.
> + ///
> + /// # Guarantees
> + ///
> + /// * If there is a currently active call to `prepare_to_insert`, then this returns the same
> + /// pointer as the one returned by the currently active call to `prepare_to_insert`.
I was a bit confused by the term "active call to `prepare_to_insert`",
since I thought that the function would need to be executed at this
moment. I inferred from below that you mean by this that there has been
a `prepare_to_insert` call, but not yet a corresponding `post_remove`
call.
I did not yet find a better way to phrase this.
I like putting the guarantees on the functions very much.
--
Cheers,
Benno
I think the commit one-line description sounds a bit strange, how about
"rust: list: add ListArc tracking strategies"?
On 02.04.24 14:16, Alice Ryhl wrote:
> @@ -33,19 +34,64 @@ pub trait ListArcSafe<const ID: u64 = 0> {
> unsafe fn on_drop_list_arc(&self);
> }
>
> +/// Declares that this type is able to safely attempt to create `ListArc`s at any time.
> +///
> +/// # Safety
> +///
> +/// Implementers must ensure that `try_new_list_arc` does not return `true` if a `ListArc` already
> +/// exists.
> +pub unsafe trait TryNewListArc<const ID: u64 = 0>: ListArcSafe<ID> {
> + /// Attempts to convert an `Arc<Self>` into an `ListArc<Self>`. Returns `true` if the
> + /// conversion was successful.
> + fn try_new_list_arc(&self) -> bool;
> +}
> +
> /// Declares that this type supports [`ListArc`].
> ///
> -/// When using this macro, it will only be possible to create a [`ListArc`] from a [`UniqueArc`].
> +/// When using this macro, you may choose between the `untracked` strategy where it is not tracked
> +/// whether a [`ListArc`] exists, and the `tracked_by` strategy where the tracking is deferred to a
> +/// field of the struct. The `tracked_by` strategy can be combined with a field of type
> +/// [`AtomicListArcTracker`] to track whether a [`ListArc`] exists.
> #[macro_export]
> macro_rules! impl_list_arc_safe {
> (impl$({$($generics:tt)*})? ListArcSafe<$num:tt> for $t:ty { untracked; } $($rest:tt)*) => {
> - impl$(<$($generics)*>)? $crate::list::ListArcSafe<$num> for $t {
> + impl$(<$($generics)*>)? ListArcSafe<$num> for $t {
This change seems unintentional.
> unsafe fn on_create_list_arc_from_unique(&mut self) {}
> unsafe fn on_drop_list_arc(&self) {}
> }
> $crate::list::impl_list_arc_safe! { $($rest)* }
> };
>
> + (impl$({$($generics:tt)*})? ListArcSafe<$num:tt> for $t:ty {
> + tracked_by $field:ident : $fty:ty;
> + } $($rest:tt)*) => {
> + impl$(<$($generics)*>)? ListArcSafe<$num> for $t {
Here you also want to access `ListArcSafe` via
`$crate::list::ListArcSafe`.
> + unsafe fn on_create_list_arc_from_unique(&mut self) {
> + let me = self as *mut Self;
> + let field: *mut $fty = unsafe { ::core::ptr::addr_of_mut!((*me).$field) };
I think we should also have `SAFETY` comments in macros.
Also why can't this be done using safe code?:
let field: &mut $fty = &mut self.$field;
> + unsafe { <$fty as $crate::list::ListArcSafe<$num>>::on_create_list_arc_from_unique(
> + &mut *field
> + ) };
Formatting? rustfmt gives me this:
unsafe {
<$fty as $crate::list::ListArcSafe<$num>>::on_create_list_arc_from_unique(
&mut *field
)
};
(maybe the `;` should be inside the `unsafe` block in this case?)
--
Cheers,
Benno
> + }
> + unsafe fn on_drop_list_arc(&self) {
> + let me = self as *const Self;
> + let field: *const $fty = unsafe { ::core::ptr::addr_of!((*me).$field) };
> + unsafe { <$fty as $crate::list::ListArcSafe<$num>>::on_drop_list_arc(&*field) };
> + }
> + }
> + unsafe impl$(<$($generics)*>)? TryNewListArc<$num> for $t
> + where
> + $fty: TryNewListArc<$num>,
> + {
> + fn try_new_list_arc(&self) -> bool {
> + let me = self as *const Self;
> + let field: *const $fty = unsafe { ::core::ptr::addr_of!((*me).$field) };
> + unsafe { <$fty as $crate::list::TryNewListArc<$num>>::try_new_list_arc(&*field) }
> + }
> + }
> + $crate::list::impl_list_arc_safe! { $($rest)* }
> + };
> +
> () => {};
> }
> pub use impl_list_arc_safe;
> +impl<T: ListArcSafe<ID>, const ID: u64> ListArc<T, ID> {
> + /// Constructs a new reference counted instance of `T`.
> + pub fn try_new(contents: T) -> Result<Self, AllocError> {
> + Ok(Self::from_unique(UniqueArc::try_new(contents)?))
> + }
This needs to be updated for the `alloc` changes to accept allocator flags.
On 03.04.24 14:49, Alice Ryhl wrote:
> On Wed, Apr 3, 2024 at 2:19 PM Benno Lossin <[email protected]> wrote:
>> On 02.04.24 14:17, Alice Ryhl wrote:
>>> +impl<'a, T: ?Sized + ListItem<ID>, 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 = unsafe { T::view_value(ListLinks::from_fields(self.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 cursor or the list. However, the `ArcBorrow` holds an immutable borrow
>>> + // on the cursor, which in turn holds an immutable borrow on the list, so any such
>>
>> The cursor has a mutable borrow on the list.
>>
>>
>>> + // mutable access requires first releasing the immutable borrow on the cursor.
>>> + // * Values in a list never have a `UniqueArc` reference.
>>
>> Is there some type invariant guaranteeing this?
>
> The List owns a ListArc reference to the value. It would be unsound
> for there to also be a UniqueArc reference to it.
I think it would be good to add the existence of the `ListArc` as an
explanation.
--
Cheers,
Benno
On Thu, Apr 4, 2024 at 3:28 PM Benno Lossin <[email protected]> wrote:
>
> On 03.04.24 14:49, Alice Ryhl wrote:
> > On Wed, Apr 3, 2024 at 2:19 PM Benno Lossin <[email protected]> wrote:
> >> On 02.04.24 14:17, Alice Ryhl wrote:
> >>> +impl<'a, T: ?Sized + ListItem<ID>, 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 = unsafe { T::view_value(ListLinks::from_fields(self.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 cursor or the list. However, the `ArcBorrow` holds an immutable borrow
> >>> + // on the cursor, which in turn holds an immutable borrow on the list, so any such
> >>
> >> The cursor has a mutable borrow on the list.
> >>
> >>
> >>> + // mutable access requires first releasing the immutable borrow on the cursor.
> >>> + // * Values in a list never have a `UniqueArc` reference.
> >>
> >> Is there some type invariant guaranteeing this?
> >
> > The List owns a ListArc reference to the value. It would be unsound
> > for there to also be a UniqueArc reference to it.
>
> I think it would be good to add the existence of the `ListArc` as an
> explanation.
Will do. I'll do the other suggestions as well.
Alice
On Wed, Apr 3, 2024 at 5:51 PM Benno Lossin <[email protected]> wrote:
>
> On 02.04.24 14:16, Alice Ryhl wrote:
> > +impl<T: ListArcSafe<ID>, const ID: u64> ListArc<T, ID> {
> > + /// Constructs a new reference counted instance of `T`.
> > + pub fn try_new(contents: T) -> Result<Self, AllocError> {
> > + Ok(Self::from_unique(UniqueArc::try_new(contents)?))
> > + }
> > +
> > + /// Use the given initializer to in-place initialize a `T`.
> > + ///
> > + /// If `T: !Unpin` it will not be able to move afterwards.
> > + pub fn pin_init<E>(init: impl PinInit<T, E>) -> error::Result<Self>
> > + where
> > + Error: From<E>,
> > + {
> > + Ok(Self::from_pin_unique(UniqueArc::pin_init(init)?))
> > + }
>
> pin-init has a general trait for this: InPlaceInit. I don't know if the
> other functions that it provides would help you.
I will use that.
> > +}
> > +
> > +impl<T, const ID: u64> ListArc<T, ID>
> > +where
> > + T: ListArcSafe<ID> + ?Sized,
> > +{
> > + /// Convert a [`UniqueArc`] into a [`ListArc`].
> > + pub fn from_unique(mut unique: UniqueArc<T>) -> Self {
> > + // SAFETY: We have a `UniqueArc`, so there is no `ListArc`.
> > + unsafe { T::on_create_list_arc_from_unique(&mut unique) };
> > + let arc = Arc::from(unique);
> > + // SAFETY: We just called `on_create_list_arc_from_unique` on an arc without a `ListArc`,
> > + // so we can create a `ListArc`.
> > + unsafe { Self::transmute_from_arc(arc) }
> > + }
> > +
> > + /// Convert a pinned [`UniqueArc`] into a [`ListArc`].
> > + pub fn from_pin_unique(unique: Pin<UniqueArc<T>>) -> Self {
> > + // SAFETY: We continue to treat this pointer as pinned after this call, since `ListArc`
> > + // implicitly pins its value.
>
> This is not sufficient, since you also rely on `Self::from_unique` to
> handle the parameter as if it were pinned, which it does not. Since it
> calls `T::on_create_list_arc_from_unique` which just gets a `&mut self`
> as a parameter and it could move stuff out.
I'll swap these so that from_unique calls from_pin_unique instead.
I'll also change on_create_list_arc_from_unique to take a Pin<&mut
Self>.
> > + Self::from_unique(unsafe { Pin::into_inner_unchecked(unique) })
> > + }
> > +
> > + /// Like [`from_unique`], but creates two `ListArcs`.
> > + ///
> > + /// The two ids must be different.
> > + ///
> > + /// [`from_unique`]: ListArc::from_unique
> > + pub fn pair_from_unique<const ID2: u64>(mut unique: UniqueArc<T>) -> (Self, ListArc<T, ID2>)
> > + where
> > + T: ListArcSafe<ID2>,
> > + {
> > + assert_ne!(ID, ID2);
>
> Can this be a `build_assert!`?
Most likely.
> > +
> > + // SAFETY: We have a `UniqueArc`, so we can call this method.
>
> I liked the comment from above better:
>
> // SAFETY: We have a `UniqueArc`, so there is no `ListArc`.
>
> Maybe use the variation "so there are no `ListArc`s for any ID.".
Will do.
> > + unsafe { <T as ListArcSafe<ID>>::on_create_list_arc_from_unique(&mut unique) };
> > + // SAFETY: We have a `UniqueArc`, so we can call this method. The two ids are not equal.
> > + unsafe { <T as ListArcSafe<ID2>>::on_create_list_arc_from_unique(&mut unique) };
> > +
> > + let arc1 = Arc::from(unique);
> > + let arc2 = Arc::clone(&arc1);
> > +
> > + // SAFETY: We just called `on_create_list_arc_from_unique` on an arc without a `ListArc`,
> > + // so we can create a `ListArc`.
>
> I would mention the two different IDs again.
Sure.
> > + unsafe {
> > + (
> > + Self::transmute_from_arc(arc1),
> > + ListArc::transmute_from_arc(arc2),
> > + )
> > + }
> > + }
> > +
> > + /// Like [`pair_from_unique`], but uses a pinned arc.
> > + ///
> > + /// The two ids must be different.
> > + ///
> > + /// [`pair_from_unique`]: ListArc::pair_from_unique
> > + pub fn pair_from_pin_unique<const ID2: u64>(
> > + unique: Pin<UniqueArc<T>>,
> > + ) -> (Self, ListArc<T, ID2>)
> > + where
> > + T: ListArcSafe<ID2>,
> > + {
> > + // SAFETY: We continue to treat this pointer as pinned after this call, since `ListArc`
> > + // implicitly pins its value.
> > + Self::pair_from_unique(unsafe { Pin::into_inner_unchecked(unique) })
> > + }
> > +
> > + /// Transmutes an [`Arc`] into a `ListArc` without updating the tracking inside `T`.
> > + ///
> > + /// # Safety
> > + ///
> > + /// * The value must not already have a `ListArc` reference.
> > + /// * The tracking inside `T` must think that there is a `ListArc` reference.
> > + #[inline]
> > + unsafe fn transmute_from_arc(me: Arc<T>) -> Self {
> > + // INVARIANT: By the safety requirements, the invariants on `ListArc` are satisfied.
> > + // SAFETY: ListArc is repr(transparent).
> > + unsafe { core::mem::transmute(me) }
>
> Why do you need a transmute here? Can't you just construct the struct?
>
> Self { arc: me }
Yeah, I guess that works.
Alice
On Wed, Apr 3, 2024 at 5:57 PM Benno Lossin <[email protected]> wrote:
>
> On 02.04.24 14:17, Alice Ryhl wrote:
> > +/// Implemented by types where a [`ListArc<Self>`] can be inserted into a `List`.
> > +///
> > +/// # Safety
> > +///
> > +/// Implementers must ensure that they provide the guarantees documented on the three methods
> > +/// below.
> > +///
> > +/// [`ListArc<Self>`]: ListArc
> > +pub unsafe trait ListItem<const ID: u64 = 0>: ListArcSafe<ID> {
> > + /// Views the [`ListLinks`] for this value.
> > + ///
> > + /// # Guarantees
> > + ///
> > + /// * If there is a currently active call to `prepare_to_insert`, then this returns the same
> > + /// pointer as the one returned by the currently active call to `prepare_to_insert`.
>
> I was a bit confused by the term "active call to `prepare_to_insert`",
> since I thought that the function would need to be executed at this
> moment. I inferred from below that you mean by this that there has been
> a `prepare_to_insert` call, but not yet a corresponding `post_remove`
> call.
> I did not yet find a better way to phrase this.
>
> I like putting the guarantees on the functions very much.
How about this?
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 pointer 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.
Alice
On 02.04.24 14:17, Alice Ryhl wrote:
> Add the actual linked list itself.
>
> The linked list uses the following design: The List type itself just has
> a single pointer to the first element of the list. And the actual list
> items then form a cycle. So the last item is `first->prev`.
>
> This is slightly different from the usual kernel linked list. Matching
> that exactly would amount to giving List two pointers, and having it be
> part of the cycle of items. This alternate design has the advantage that
> the cycle is never completely empty, which can reduce the number of
> branches in some cases. However, it also has the disadvantage that List
> must be pinned, which this design is trying to avoid.
>
> Having the list items form a cycle rather than having null pointers at
> the beginning/end is convenient for several reasons. For one, it lets us
> store only one pointer in List, and it simplifies the implementation of
> several functions.
>
> Unfortunately, the `remove` function that removes an arbitrary element
> from the list has to be unsafe. This is needed because there is no way
> to handle the case where you pass an element from the wrong list. For
> example, if it is the first element of some other list, then that other
> list's `first` pointer would not be updated. Similarly, it could be a
> data race if you try to remove it from two different lists in parallel.
> (There's no problem with passing `remove` an item that's not in any
> list. Additionally, other removal methods such as `pop_front` need not
> be unsafe, as they can't be used to remove items from another list.)
>
> Signed-off-by: Alice Ryhl <[email protected]>
> ---
> rust/kernel/list.rs | 294 +++++++++++++++++++++++++++++++++++++++++++++++-
> rust/kernel/list/arc.rs | 6 +-
> 2 files changed, 295 insertions(+), 5 deletions(-)
>
> diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs
> index 7af5109500f2..7e9ed802b26b 100644
> --- a/rust/kernel/list.rs
> +++ b/rust/kernel/list.rs
> @@ -6,6 +6,7 @@
>
> use crate::init::PinInit;
> use crate::types::Opaque;
> +use core::marker::PhantomData;
> use core::ptr;
>
> mod impl_list_item_mod;
> @@ -16,7 +17,41 @@
> impl_list_arc_safe, AtomicListArcTracker, ListArc, ListArcSafe, TryNewListArc,
> };
>
> -/// Implemented by types where a [`ListArc<Self>`] 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 ensures that the same
> +/// prev/next pointers are not used for several linked lists.
> +///
> +/// # Invariants
> +///
> +/// If the list is empty, then `first` is null. Otherwise, it points at the links field of the
> +/// first element of this list. The prev/next pointers of items in the list will always form a
> +/// cycle. This means that prev/next pointers for an item in a list are never null and never
> +/// dangling.
I think this is missing that all elements of the list are in `ListArc`s.
About "This means that prev/next pointers for an item in a list are
never null and never dangling.", I think it would be simpler to say that
"All prev/next pointers of items in the list are valid and form a cycle."
> +pub struct List<T: ?Sized + ListItem<ID>, const ID: u64 = 0> {
> + first: *mut ListLinksFields,
> + _ty: PhantomData<ListArc<T, ID>>,
> +}
> +
> +// SAFETY: This is a container of `ListArc<T, ID>`, and access to the container allows the same
> +// type of access to the `ListArc<T, ID>` elements.
> +unsafe impl<T, const ID: u64> Send for List<T, ID>
> +where
> + ListArc<T, ID>: Send,
> + T: ?Sized + ListItem<ID>,
> +{
> +}
> +// SAFETY: This is a container of `ListArc<T, ID>`, and access to the container allows the same
> +// type of access to the `ListArc<T, ID>` elements.
> +unsafe impl<T, const ID: u64> Sync for List<T, ID>
> +where
> + ListArc<T, ID>: Sync,
> + T: ?Sized + ListItem<ID>,
> +{
> +}
> +
> +/// Implemented by types where a [`ListArc<Self>`] can be inserted into a [`List`].
> ///
> /// # Safety
> ///
> @@ -56,7 +91,7 @@ pub unsafe trait ListItem<const ID: u64 = 0>: ListArcSafe<ID> {
> /// been called.
> unsafe fn view_value(me: *mut ListLinks<ID>) -> *const Self;
>
> - /// This is called when an item is inserted into a `List`.
> + /// This is called when an item is inserted into a [`List`].
> ///
> /// # Guarantees
> ///
> @@ -103,7 +138,6 @@ struct ListLinksFields {
> /// The fields are null if and only if this item is not in a list.
> #[repr(transparent)]
> pub struct ListLinks<const ID: u64 = 0> {
> - #[allow(dead_code)]
> inner: Opaque<ListLinksFields>,
> }
>
> @@ -125,4 +159,258 @@ pub fn new() -> impl PinInit<Self> {
> }),
> }
> }
> +
> + /// # Safety
> + ///
> + /// The pointer must be dereferencable.
I would use "`me` is valid.".
> + #[inline]
> + unsafe fn fields(me: *mut Self) -> *mut ListLinksFields {
> + // SAFETY: The caller promises that the pointer is valid.
> + unsafe { Opaque::raw_get(ptr::addr_of!((*me).inner)) }
> + }
> +
> + /// # Safety
> + ///
> + /// The pointer must be dereferencable.
Ditto.
> + #[inline]
> + unsafe fn from_fields(me: *mut ListLinksFields) -> *mut Self {
> + me.cast()
> + }
> +}
> +
> +impl<T: ?Sized + ListItem<ID>, const ID: u64> List<T, ID> {
> + /// 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<T, ID>) {
> + let item = unsafe { ListLinks::fields(T::prepare_to_insert(ListArc::into_raw(item))) };
Missing SAFETY comment.
> +
> + if self.first.is_null() {
> + self.first = item;
> + // SAFETY: The caller just gave us ownership of these fields.
> + // INVARIANT: A linked list with one item should be cyclic.
> + unsafe {
> + (*item).next = item;
> + (*item).prev = item;
> + }
> + } else {
> + let next = self.first;
> + // SAFETY: We just checked that `next` is non-null.
Missing mention of the type invariant.
> + let prev = unsafe { (*next).prev };
> + // SAFETY: Pointers in a linked list are never dangling, and the caller just gave us
> + // ownership of the fields on `item`.
> + // INVARIANT: This correctly inserts `item` between `prev` and `next`.
> + unsafe {
> + (*item).next = next;
> + (*item).prev = prev;
> + (*prev).next = item;
> + (*next).prev = item;
> + }
> + }
> + }
> +
> + /// Add the provided item to the front of the list.
> + pub fn push_front(&mut self, item: ListArc<T, ID>) {
> + let item = unsafe { ListLinks::fields(T::prepare_to_insert(ListArc::into_raw(item))) };
> +
> + if self.first.is_null() {
> + // SAFETY: The caller just gave us ownership of these fields.
> + // INVARIANT: A linked list with one item should be cyclic.
> + unsafe {
> + (*item).next = item;
> + (*item).prev = item;
> + }
> + } else {
> + let next = self.first;
> + // SAFETY: We just checked that `next` is non-null.
> + let prev = unsafe { (*next).prev };
> + // SAFETY: Pointers in a linked list are never dangling, and the caller just gave us
> + // ownership of the fields on `item`.
> + // INVARIANT: This correctly inserts `item` between `prev` and `next`.
> + unsafe {
> + (*item).next = next;
> + (*item).prev = prev;
> + (*prev).next = item;
> + (*next).prev = item;
> + }
> + }
> + self.first = item;
> + }
> +
> + /// Removes the last item from this list.
> + pub fn pop_back(&mut self) -> Option<ListArc<T, ID>> {
> + if self.first.is_null() {
> + return None;
> + }
> +
> + // SAFETY: We just checked that the list is not empty.
> + let last = 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<ListArc<T, ID>> {
> + 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.
I think this should say "Returns `None` if the item is not in a list.".
(Technically it should be "is not in a `List<T, ID>`", since it *can* be
in another list with a different ID.)
> + ///
> + /// # Safety
> + ///
> + /// The provided item must not be in a different linked list.
> + pub unsafe fn remove(&mut self, item: &T) -> Option<ListArc<T, ID>> {
> + let mut item = 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-only 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 } = 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 raw pointer that was
> + // obtained without going through a pointer->reference->pointer conversion rountrip.
> + // This ensures that the list is valid under the more restrictive strict provenance
> + // ruleset.
> + //
> + // SAFETY: We just checked that `next` is not null, and it's not dangling by the
> + // list invariants.
> + unsafe {
> + debug_assert_eq!(item, (*next).prev);
> + item = (*next).prev;
> + }
> +
> + // SAFETY: We just checked that `item` is in a list, so the caller guarantees that it
> + // is in this list. The pointers are in the right order.
> + Some(unsafe { self.remove_internal_inner(item, next, prev) })
> + } else {
> + None
> + }
> + }
> +
> + /// Removes the provided item from the list.
> + ///
> + /// # Safety
> + ///
> + /// The pointer must point at an item in this list.
> + unsafe fn remove_internal(&mut self, item: *mut ListLinksFields) -> ListArc<T, ID> {
> + // 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 } = 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 ==
> + /// next` and `(*item).prev == prev`.
> + unsafe fn remove_internal_inner(
> + &mut self,
> + item: *mut ListLinksFields,
> + next: *mut ListLinksFields,
> + prev: *mut ListLinksFields,
> + ) -> ListArc<T, ID> {
> + // SAFETY: We have exclusive access to items in the list, and prev/next pointers are
I think you mean that you have exclusive access to the prev/next fields
of the `ListLinks` associated with `ID`... But that is rather long.
Does anyone have any idea to shorten this?
> + // never null for items in a list.
> + //
> + // INVARIANT: There are three cases:
> + // * If the list has at least three items, then after removing the item, `prev` and `next`
> + // will be next to each other.
> + // * If the list has two items, then the remaining item will point at itself.
> + // * If the list has one item, then `next == prev == item`, so these writes have no effect
> + // due to the writes to `item` below.
I think the writes do not have an effect. (no need to reference the
writes to `item` below)
> + unsafe {
> + (*next).prev = prev;
> + (*prev).next = next;
> + }
> + // SAFETY: We have exclusive access to items in the list.
> + // INVARIANT: The item is no longer in a list, so the pointers should be null.
> + unsafe {
> + (*item).prev = ptr::null_mut();
> + (*item).next = ptr::null_mut();
> + }
> + // INVARIANT: There are three cases:
> + // * If `item` was not the first item, then `self.first` should remain 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 setting `item->next` to null
> + // did not modify `prev->next`.
> + // * If `item` was the only item in the list, then `prev == item`, and we just set
> + // `item->next` to null, so this correctly sets `first` to null now that the list is
> + // empty.
> + if self.first == item {
> + // SAFETY: The `prev` field of an item in a list is never dangling.
I don't think this SAFETY comment makes sense.
--
Cheers,
Benno
> + self.first = unsafe { (*prev).next };
> + }
> +
> + // SAFETY: We just removed a `ListArc` from the list, so we can turn it back into a
> + // `ListArc`.
> + unsafe { ListArc::from_raw(T::post_remove(ListLinks::from_fields(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<T, ID>) {
> + // 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 of `self`.
> + self.first = other.first;
> + } else if !other.is_empty() {
> + let other_first = other.first;
> + // SAFETY: The other list is not empty, so this pointer is valid.
> + let other_last = unsafe { (*other_first).prev };
> + let self_first = self.first;
> + // SAFETY: The self list is not empty, so this pointer is valid.
> + let self_last = unsafe { (*self_first).prev };
> +
> + // SAFETY: We have exclusive access to both lists, so we can update the pointers.
> + // INVARIANT: This correctly sets the pointers to merge both lists. We do not need to
> + // update `self.first` because the first element of `self` does not change.
> + unsafe {
> + (*self_first).prev = other_last;
> + (*other_last).next = self_first;
> + (*self_last).next = other_first;
> + (*other_first).prev = self_last;
> + }
> + }
> +
> + // INVARIANT: The other list is now empty, so update its pointer.
> + other.first = ptr::null_mut();
> + }
> +}
> +
> +impl<T: ?Sized + ListItem<ID>, const ID: u64> Drop for List<T, ID> {
> + fn drop(&mut self) {
> + while let Some(item) = self.pop_front() {
> + drop(item);
> + }
> + }
> }
On 04.04.24 16:03, Alice Ryhl wrote:
> On Wed, Apr 3, 2024 at 5:57 PM Benno Lossin <[email protected]> wrote:
>>
>> On 02.04.24 14:17, Alice Ryhl wrote:
>>> +/// Implemented by types where a [`ListArc<Self>`] can be inserted into a `List`.
>>> +///
>>> +/// # Safety
>>> +///
>>> +/// Implementers must ensure that they provide the guarantees documented on the three methods
>>> +/// below.
>>> +///
>>> +/// [`ListArc<Self>`]: ListArc
>>> +pub unsafe trait ListItem<const ID: u64 = 0>: ListArcSafe<ID> {
>>> + /// Views the [`ListLinks`] for this value.
>>> + ///
>>> + /// # Guarantees
>>> + ///
>>> + /// * If there is a currently active call to `prepare_to_insert`, then this returns the same
>>> + /// pointer as the one returned by the currently active call to `prepare_to_insert`.
>>
>> I was a bit confused by the term "active call to `prepare_to_insert`",
>> since I thought that the function would need to be executed at this
>> moment. I inferred from below that you mean by this that there has been
>> a `prepare_to_insert` call, but not yet a corresponding `post_remove`
>> call.
>> I did not yet find a better way to phrase this.
>>
>> I like putting the guarantees on the functions very much.
>
> How about this?
>
> 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 pointer 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.
Sounds good.
--
Cheers,
Benno
On Thu, Apr 4, 2024 at 4:03 PM Benno Lossin <[email protected]> wrote:
>
> On 02.04.24 14:17, Alice Ryhl wrote:
> > Add the actual linked list itself.
> >
> > The linked list uses the following design: The List type itself just has
> > a single pointer to the first element of the list. And the actual list
> > items then form a cycle. So the last item is `first->prev`.
> >
> > This is slightly different from the usual kernel linked list. Matching
> > that exactly would amount to giving List two pointers, and having it be
> > part of the cycle of items. This alternate design has the advantage that
> > the cycle is never completely empty, which can reduce the number of
> > branches in some cases. However, it also has the disadvantage that List
> > must be pinned, which this design is trying to avoid.
> >
> > Having the list items form a cycle rather than having null pointers at
> > the beginning/end is convenient for several reasons. For one, it lets us
> > store only one pointer in List, and it simplifies the implementation of
> > several functions.
> >
> > Unfortunately, the `remove` function that removes an arbitrary element
> > from the list has to be unsafe. This is needed because there is no way
> > to handle the case where you pass an element from the wrong list. For
> > example, if it is the first element of some other list, then that other
> > list's `first` pointer would not be updated. Similarly, it could be a
> > data race if you try to remove it from two different lists in parallel.
> > (There's no problem with passing `remove` an item that's not in any
> > list. Additionally, other removal methods such as `pop_front` need not
> > be unsafe, as they can't be used to remove items from another list.)
> >
> > Signed-off-by: Alice Ryhl <[email protected]>
> > ---
> > rust/kernel/list.rs | 294 +++++++++++++++++++++++++++++++++++++++++++++++-
> > rust/kernel/list/arc.rs | 6 +-
> > 2 files changed, 295 insertions(+), 5 deletions(-)
> >
> > diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs
> > index 7af5109500f2..7e9ed802b26b 100644
> > --- a/rust/kernel/list.rs
> > +++ b/rust/kernel/list.rs
> > @@ -6,6 +6,7 @@
> >
> > use crate::init::PinInit;
> > use crate::types::Opaque;
> > +use core::marker::PhantomData;
> > use core::ptr;
> >
> > mod impl_list_item_mod;
> > @@ -16,7 +17,41 @@
> > impl_list_arc_safe, AtomicListArcTracker, ListArc, ListArcSafe, TryNewListArc,
> > };
> >
> > -/// Implemented by types where a [`ListArc<Self>`] 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 ensures that the same
> > +/// prev/next pointers are not used for several linked lists.
> > +///
> > +/// # Invariants
> > +///
> > +/// If the list is empty, then `first` is null. Otherwise, it points at the links field of the
> > +/// first element of this list. The prev/next pointers of items in the list will always form a
> > +/// cycle. This means that prev/next pointers for an item in a list are never null and never
> > +/// dangling.
>
> I think this is missing that all elements of the list are in `ListArc`s.
>
> About "This means that prev/next pointers for an item in a list are
> never null and never dangling.", I think it would be simpler to say that
> "All prev/next pointers of items in the list are valid and form a cycle."
Sure.
> > +pub struct List<T: ?Sized + ListItem<ID>, const ID: u64 = 0> {
> > + first: *mut ListLinksFields,
> > + _ty: PhantomData<ListArc<T, ID>>,
> > +}
> > +
> > +// SAFETY: This is a container of `ListArc<T, ID>`, and access to the container allows the same
> > +// type of access to the `ListArc<T, ID>` elements.
> > +unsafe impl<T, const ID: u64> Send for List<T, ID>
> > +where
> > + ListArc<T, ID>: Send,
> > + T: ?Sized + ListItem<ID>,
> > +{
> > +}
> > +// SAFETY: This is a container of `ListArc<T, ID>`, and access to the container allows the same
> > +// type of access to the `ListArc<T, ID>` elements.
> > +unsafe impl<T, const ID: u64> Sync for List<T, ID>
> > +where
> > + ListArc<T, ID>: Sync,
> > + T: ?Sized + ListItem<ID>,
> > +{
> > +}
> > +
> > +/// Implemented by types where a [`ListArc<Self>`] can be inserted into a [`List`].
> > ///
> > /// # Safety
> > ///
> > @@ -56,7 +91,7 @@ pub unsafe trait ListItem<const ID: u64 = 0>: ListArcSafe<ID> {
> > /// been called.
> > unsafe fn view_value(me: *mut ListLinks<ID>) -> *const Self;
> >
> > - /// This is called when an item is inserted into a `List`.
> > + /// This is called when an item is inserted into a [`List`].
> > ///
> > /// # Guarantees
> > ///
> > @@ -103,7 +138,6 @@ struct ListLinksFields {
> > /// The fields are null if and only if this item is not in a list.
> > #[repr(transparent)]
> > pub struct ListLinks<const ID: u64 = 0> {
> > - #[allow(dead_code)]
> > inner: Opaque<ListLinksFields>,
> > }
> >
> > @@ -125,4 +159,258 @@ pub fn new() -> impl PinInit<Self> {
> > }),
> > }
> > }
> > +
> > + /// # Safety
> > + ///
> > + /// The pointer must be dereferencable.
>
> I would use "`me` is valid.".
Ok.
> > + #[inline]
> > + unsafe fn fields(me: *mut Self) -> *mut ListLinksFields {
> > + // SAFETY: The caller promises that the pointer is valid.
> > + unsafe { Opaque::raw_get(ptr::addr_of!((*me).inner)) }
> > + }
> > +
> > + /// # Safety
> > + ///
> > + /// The pointer must be dereferencable.
>
> Ditto.
Ok.
> > + #[inline]
> > + unsafe fn from_fields(me: *mut ListLinksFields) -> *mut Self {
> > + me.cast()
> > + }
> > +}
> > +
> > +impl<T: ?Sized + ListItem<ID>, const ID: u64> List<T, ID> {
> > + /// 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<T, ID>) {
> > + let item = unsafe { ListLinks::fields(T::prepare_to_insert(ListArc::into_raw(item))) };
>
> Missing SAFETY comment.
Will add one here and in push_front.
> > +
> > + if self.first.is_null() {
> > + self.first = item;
> > + // SAFETY: The caller just gave us ownership of these fields.
> > + // INVARIANT: A linked list with one item should be cyclic.
> > + unsafe {
> > + (*item).next = item;
> > + (*item).prev = item;
> > + }
> > + } else {
> > + let next = self.first;
> > + // SAFETY: We just checked that `next` is non-null.
>
> Missing mention of the type invariant.
SAFETY: By the type invariant, this pointer is valid or null. We just
checked that it's not null, so it must be valid.
> > + let prev = unsafe { (*next).prev };
> > + // SAFETY: Pointers in a linked list are never dangling, and the caller just gave us
> > + // ownership of the fields on `item`.
> > + // INVARIANT: This correctly inserts `item` between `prev` and `next`.
> > + unsafe {
> > + (*item).next = next;
> > + (*item).prev = prev;
> > + (*prev).next = item;
> > + (*next).prev = item;
> > + }
> > + }
> > + }
> > +
> > + /// Add the provided item to the front of the list.
> > + pub fn push_front(&mut self, item: ListArc<T, ID>) {
> > + let item = unsafe { ListLinks::fields(T::prepare_to_insert(ListArc::into_raw(item))) };
> > +
> > + if self.first.is_null() {
> > + // SAFETY: The caller just gave us ownership of these fields.
> > + // INVARIANT: A linked list with one item should be cyclic.
> > + unsafe {
> > + (*item).next = item;
> > + (*item).prev = item;
> > + }
> > + } else {
> > + let next = self.first;
> > + // SAFETY: We just checked that `next` is non-null.
> > + let prev = unsafe { (*next).prev };
> > + // SAFETY: Pointers in a linked list are never dangling, and the caller just gave us
> > + // ownership of the fields on `item`.
> > + // INVARIANT: This correctly inserts `item` between `prev` and `next`.
> > + unsafe {
> > + (*item).next = next;
> > + (*item).prev = prev;
> > + (*prev).next = item;
> > + (*next).prev = item;
> > + }
> > + }
> > + self.first = item;
> > + }
> > +
> > + /// Removes the last item from this list.
> > + pub fn pop_back(&mut self) -> Option<ListArc<T, ID>> {
> > + if self.first.is_null() {
> > + return None;
> > + }
> > +
> > + // SAFETY: We just checked that the list is not empty.
> > + let last = 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<ListArc<T, ID>> {
> > + 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.
>
> I think this should say "Returns `None` if the item is not in a list.".
> (Technically it should be "is not in a `List<T, ID>`", since it *can* be
> in another list with a different ID.)
I'm not really convinced. The phrases "the list" and "a list" are
equivalent given the safety requirement for this method, but "the
list" seems more natural to me. The `remove` method of any other
collection would say "the list" too.
> > + ///
> > + /// # Safety
> > + ///
> > + /// The provided item must not be in a different linked list.
> > + pub unsafe fn remove(&mut self, item: &T) -> Option<ListArc<T, ID>> {
> > + let mut item = 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-only 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 } = 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 raw pointer that was
> > + // obtained without going through a pointer->reference->pointer conversion rountrip.
> > + // This ensures that the list is valid under the more restrictive strict provenance
> > + // ruleset.
> > + //
> > + // SAFETY: We just checked that `next` is not null, and it's not dangling by the
> > + // list invariants.
> > + unsafe {
> > + debug_assert_eq!(item, (*next).prev);
> > + item = (*next).prev;
> > + }
> > +
> > + // SAFETY: We just checked that `item` is in a list, so the caller guarantees that it
> > + // is in this list. The pointers are in the right order.
> > + Some(unsafe { self.remove_internal_inner(item, next, prev) })
> > + } else {
> > + None
> > + }
> > + }
> > +
> > + /// Removes the provided item from the list.
> > + ///
> > + /// # Safety
> > + ///
> > + /// The pointer must point at an item in this list.
> > + unsafe fn remove_internal(&mut self, item: *mut ListLinksFields) -> ListArc<T, ID> {
> > + // 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 } = 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 ==
> > + /// next` and `(*item).prev == prev`.
> > + unsafe fn remove_internal_inner(
> > + &mut self,
> > + item: *mut ListLinksFields,
> > + next: *mut ListLinksFields,
> > + prev: *mut ListLinksFields,
> > + ) -> ListArc<T, ID> {
> > + // SAFETY: We have exclusive access to items in the list, and prev/next pointers are
>
> I think you mean that you have exclusive access to the prev/next fields
> of the `ListLinks` associated with `ID`... But that is rather long.
> Does anyone have any idea to shorten this?
SAFETY: We have exclusive access to the pointers of items in the list,
and the prev/next pointers are never null for items in a list.
> > + // never null for items in a list.
> > + //
> > + // INVARIANT: There are three cases:
> > + // * If the list has at least three items, then after removing the item, `prev` and `next`
> > + // will be next to each other.
> > + // * If the list has two items, then the remaining item will point at itself.
> > + // * If the list has one item, then `next == prev == item`, so these writes have no effect
> > + // due to the writes to `item` below.
>
> I think the writes do not have an effect. (no need to reference the
> writes to `item` below)
?
> > + unsafe {
> > + (*next).prev = prev;
> > + (*prev).next = next;
> > + }
> > + // SAFETY: We have exclusive access to items in the list.
> > + // INVARIANT: The item is no longer in a list, so the pointers should be null.
> > + unsafe {
> > + (*item).prev = ptr::null_mut();
> > + (*item).next = ptr::null_mut();
> > + }
> > + // INVARIANT: There are three cases:
> > + // * If `item` was not the first item, then `self.first` should remain 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 setting `item->next` to null
> > + // did not modify `prev->next`.
> > + // * If `item` was the only item in the list, then `prev == item`, and we just set
> > + // `item->next` to null, so this correctly sets `first` to null now that the list is
> > + // empty.
> > + if self.first == item {
> > + // SAFETY: The `prev` field of an item in a list is never dangling.
>
> I don't think this SAFETY comment makes sense.
>
> > + self.first = unsafe { (*prev).next };
SAFETY: `prev` is the `prev` pointer from a `ListLinks` in a `List`,
so the pointer is valid. There's no race, since we have exclusive
access to the list.
Alice
On Wed, Apr 3, 2024 at 5:52 PM Benno Lossin <[email protected]> wrote:
>
> I think the commit one-line description sounds a bit strange, how about
> "rust: list: add ListArc tracking strategies"?
>
> On 02.04.24 14:16, Alice Ryhl wrote:
> > @@ -33,19 +34,64 @@ pub trait ListArcSafe<const ID: u64 = 0> {
> > unsafe fn on_drop_list_arc(&self);
> > }
> >
> > +/// Declares that this type is able to safely attempt to create `ListArc`s at any time.
> > +///
> > +/// # Safety
> > +///
> > +/// Implementers must ensure that `try_new_list_arc` does not return `true` if a `ListArc` already
> > +/// exists.
> > +pub unsafe trait TryNewListArc<const ID: u64 = 0>: ListArcSafe<ID> {
> > + /// Attempts to convert an `Arc<Self>` into an `ListArc<Self>`. Returns `true` if the
> > + /// conversion was successful.
> > + fn try_new_list_arc(&self) -> bool;
> > +}
> > +
> > /// Declares that this type supports [`ListArc`].
> > ///
> > -/// When using this macro, it will only be possible to create a [`ListArc`] from a [`UniqueArc`].
> > +/// When using this macro, you may choose between the `untracked` strategy where it is not tracked
> > +/// whether a [`ListArc`] exists, and the `tracked_by` strategy where the tracking is deferred to a
> > +/// field of the struct. The `tracked_by` strategy can be combined with a field of type
> > +/// [`AtomicListArcTracker`] to track whether a [`ListArc`] exists.
> > #[macro_export]
> > macro_rules! impl_list_arc_safe {
> > (impl$({$($generics:tt)*})? ListArcSafe<$num:tt> for $t:ty { untracked; } $($rest:tt)*) => {
> > - impl$(<$($generics)*>)? $crate::list::ListArcSafe<$num> for $t {
> > + impl$(<$($generics)*>)? ListArcSafe<$num> for $t {
>
> This change seems unintentional.
Will fix.
> > unsafe fn on_create_list_arc_from_unique(&mut self) {}
> > unsafe fn on_drop_list_arc(&self) {}
> > }
> > $crate::list::impl_list_arc_safe! { $($rest)* }
> > };
> >
> > + (impl$({$($generics:tt)*})? ListArcSafe<$num:tt> for $t:ty {
> > + tracked_by $field:ident : $fty:ty;
> > + } $($rest:tt)*) => {
> > + impl$(<$($generics)*>)? ListArcSafe<$num> for $t {
>
> Here you also want to access `ListArcSafe` via
> `$crate::list::ListArcSafe`.
Will fix.
> > + unsafe fn on_create_list_arc_from_unique(&mut self) {
> > + let me = self as *mut Self;
> > + let field: *mut $fty = unsafe { ::core::ptr::addr_of_mut!((*me).$field) };
>
> I think we should also have `SAFETY` comments in macros.
>
> Also why can't this be done using safe code?:
>
> let field: &mut $fty = &mut self.$field;
Not sure why. Probably a historical accident. Will change it to be safe.
> > + unsafe { <$fty as $crate::list::ListArcSafe<$num>>::on_create_list_arc_from_unique(
> > + &mut *field
> > + ) };
>
> Formatting? rustfmt gives me this:
>
> unsafe {
> <$fty as $crate::list::ListArcSafe<$num>>::on_create_list_arc_from_unique(
> &mut *field
> )
> };
>
> (maybe the `;` should be inside the `unsafe` block in this case?)
I can make the change, but rustfmt does not affect macros.
Alice
On 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 04.04.24 16:14, Alice Ryhl wrote:
> On Wed, Apr 3, 2024 at 5:52 PM Benno Lossin <[email protected]> wrote:
>> On 02.04.24 14:16, Alice Ryhl wrote:
>>> + unsafe { <$fty as $crate::list::ListArcSafe<$num>>::on_create_list_arc_from_unique(
>>> + &mut *field
>>> + ) };
>>
>> Formatting? rustfmt gives me this:
>>
>> unsafe {
>> <$fty as $crate::list::ListArcSafe<$num>>::on_create_list_arc_from_unique(
>> &mut *field
>> )
>> };
>>
>> (maybe the `;` should be inside the `unsafe` block in this case?)
>
> I can make the change, but rustfmt does not affect macros.
I think we still should try to format macros correctly, it increases
readability. I take the in-macro code, remove all `$` and other
macro-only symbols, then use rustfmt and then manually format the code
accordingly. I also find it tedious, but the unformatted code also
doesn't look good :)
--
Cheers,
Benno
On Thu, Apr 4, 2024 at 4:36 PM Benno Lossin <[email protected]> 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:12, Alice Ryhl wrote:
> On Thu, Apr 4, 2024 at 4:03 PM Benno Lossin <[email protected]> wrote:
>> On 02.04.24 14:17, Alice Ryhl wrote:
>>> +
>>> + if self.first.is_null() {
>>> + self.first = item;
>>> + // SAFETY: The caller just gave us ownership of these fields.
>>> + // INVARIANT: A linked list with one item should be cyclic.
>>> + unsafe {
>>> + (*item).next = item;
>>> + (*item).prev = item;
>>> + }
>>> + } else {
>>> + let next = self.first;
>>> + // SAFETY: We just checked that `next` is non-null.
>>
>> Missing mention of the type invariant.
>
> SAFETY: By the type invariant, this pointer is valid or null. We just
> checked that it's not null, so it must be valid.
Sounds good.
[...]
>>> + /// Removes the first item from this list.
>>> + pub fn pop_front(&mut self) -> Option<ListArc<T, ID>> {
>>> + 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.
>>
>> I think this should say "Returns `None` if the item is not in a list.".
>> (Technically it should be "is not in a `List<T, ID>`", since it *can* be
>> in another list with a different ID.)
>
> I'm not really convinced. The phrases "the list" and "a list" are
> equivalent given the safety requirement for this method, but "the
> list" seems more natural to me. The `remove` method of any other
> collection would say "the list" too.
They are equivalent, but saying "the list" has the potential for this
confusion: "If the function returns `None` if the item is not in the
list, then why do I need to ensure that it is not in a different list?".
>
>>> + ///
>>> + /// # Safety
>>> + ///
>>> + /// The provided item must not be in a different linked list.
>>> + pub unsafe fn remove(&mut self, item: &T) -> Option<ListArc<T, ID>> {
>>> + let mut item = 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-only 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 } = 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 raw pointer that was
>>> + // obtained without going through a pointer->reference->pointer conversion rountrip.
>>> + // This ensures that the list is valid under the more restrictive strict provenance
>>> + // ruleset.
>>> + //
>>> + // SAFETY: We just checked that `next` is not null, and it's not dangling by the
>>> + // list invariants.
>>> + unsafe {
>>> + debug_assert_eq!(item, (*next).prev);
>>> + item = (*next).prev;
>>> + }
>>> +
>>> + // SAFETY: We just checked that `item` is in a list, so the caller guarantees that it
>>> + // is in this list. The pointers are in the right order.
>>> + Some(unsafe { self.remove_internal_inner(item, next, prev) })
>>> + } else {
>>> + None
>>> + }
>>> + }
>>> +
>>> + /// Removes the provided item from the list.
>>> + ///
>>> + /// # Safety
>>> + ///
>>> + /// The pointer must point at an item in this list.
>>> + unsafe fn remove_internal(&mut self, item: *mut ListLinksFields) -> ListArc<T, ID> {
>>> + // 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 } = 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 ==
>>> + /// next` and `(*item).prev == prev`.
>>> + unsafe fn remove_internal_inner(
>>> + &mut self,
>>> + item: *mut ListLinksFields,
>>> + next: *mut ListLinksFields,
>>> + prev: *mut ListLinksFields,
>>> + ) -> ListArc<T, ID> {
>>> + // SAFETY: We have exclusive access to items in the list, and prev/next pointers are
>>
>> I think you mean that you have exclusive access to the prev/next fields
>> of the `ListLinks` associated with `ID`... But that is rather long.
>> Does anyone have any idea to shorten this?
>
> SAFETY: We have exclusive access to the pointers of items in the list,
> and the prev/next pointers are never null for items in a list.
I would say that they are valid instead of never null, since you
dereference them below. Otherwise sounds good.
>
>>> + // never null for items in a list.
>>> + //
>>> + // INVARIANT: There are three cases:
>>> + // * If the list has at least three items, then after removing the item, `prev` and `next`
>>> + // will be next to each other.
>>> + // * If the list has two items, then the remaining item will point at itself.
>>> + // * If the list has one item, then `next == prev == item`, so these writes have no effect
>>> + // due to the writes to `item` below.
>>
>> I think the writes do not have an effect. (no need to reference the
>> writes to `item` below)
>
> ?
The first write is
(*next).prev = prev;
Using the fact that `next == prev == item` we have
(*item).prev = prev;
But that is already true, since the function requirement is that
`(*item).prev == prev`. So the write has no effect.
The same should hold for `(*prev).next = next`.
>
>>> + unsafe {
>>> + (*next).prev = prev;
>>> + (*prev).next = next;
>>> + }
>>> + // SAFETY: We have exclusive access to items in the list.
>>> + // INVARIANT: The item is no longer in a list, so the pointers should be null.
>>> + unsafe {
>>> + (*item).prev = ptr::null_mut();
>>> + (*item).next = ptr::null_mut();
>>> + }
>>> + // INVARIANT: There are three cases:
>>> + // * If `item` was not the first item, then `self.first` should remain 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 setting `item->next` to null
>>> + // did not modify `prev->next`.
>>> + // * If `item` was the only item in the list, then `prev == item`, and we just set
>>> + // `item->next` to null, so this correctly sets `first` to null now that the list is
>>> + // empty.
>>> + if self.first == item {
>>> + // SAFETY: The `prev` field of an item in a list is never dangling.
>>
>> I don't think this SAFETY comment makes sense.
>>
>>> + self.first = unsafe { (*prev).next };
>
> SAFETY: `prev` is the `prev` pointer from a `ListLinks` in a `List`,
> so the pointer is valid. There's no race, since we have exclusive
> access to the list.
Sounds good.
--
Cheers,
Benno
On 04.04.24 16:41, Alice Ryhl wrote:
> On Thu, Apr 4, 2024 at 4:36 PM Benno Lossin <[email protected]> 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 02.04.24 14:17, Alice Ryhl wrote:
> 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.
This pattern screams "field projection" :)
>
> Signed-off-by: Alice Ryhl <[email protected]>
> ---
> rust/kernel/list.rs | 3 ++
> rust/kernel/list/arc_field.rs | 94 +++++++++++++++++++++++++++++++++++++++++++
> 2 files changed, 97 insertions(+)
>
> diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs
> index 68d03b100863..a59b35b67e9b 100644
> --- a/rust/kernel/list.rs
> +++ b/rust/kernel/list.rs
> @@ -23,6 +23,9 @@
> impl_list_arc_safe, AtomicListArcTracker, ListArc, ListArcSafe, TryNewListArc,
> };
>
> +mod arc_field;
> +pub use self::arc_field::{define_list_arc_field_getter, ListArcField};
> +
> /// A linked list.
> ///
> /// All elements in this linked list will be [`ListArc`] references to the value. Since a value can
> diff --git a/rust/kernel/list/arc_field.rs b/rust/kernel/list/arc_field.rs
> new file mode 100644
> index 000000000000..936fd97bc5ac
> --- /dev/null
> +++ b/rust/kernel/list/arc_field.rs
> @@ -0,0 +1,94 @@
> +// SPDX-License-Identifier: GPL-2.0
> +
> +// Copyright (C) 2024 Google LLC.
> +
> +//! A field that is exclusively owned by a [`ListArc`].
> +//!
> +//! This can be used to have reference counted struct where one of the reference 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`.
Missing doc link.
> +pub struct ListArcField<T, const ID: u64 = 0> {
> + value: UnsafeCell<T>,
> +}
> +
> +// SAFETY: If the inner type is thread-safe, then it's also okay for `ListArc` to be thread-safe.
> +unsafe impl<T: Send + Sync, const ID: u64> Send for ListArcField<T, ID> {}
> +// SAFETY: If the inner type is thread-safe, then it's also okay for `ListArc` to be thread-safe.
> +unsafe impl<T: Send + Sync, const ID: u64> Sync for ListArcField<T, ID> {}
> +
> +impl<T, const ID: u64> ListArcField<T, ID> {
> + /// 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 `ListArcField`.
> + ///
> + /// 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 this field.
> + ///
> + /// # Safety
> + ///
> + /// The caller must have shared access to the `ListArc<ID>` 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<ID>` containing 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 they also have exclusive
> + // access to this field.
> + unsafe { &mut *self.value.get() }
> + }
> +}
> +
> +/// Defines.
Missing docs.
--
Cheers,
Benno
> +#[macro_export]
> +macro_rules! define_list_arc_field_getter {
> + ($pub:vis fn $name:ident(&self $(<$id:tt>)?) -> &$typ:ty { $field:ident }
> + $($rest:tt)*
> + ) => {
> + $pub fn $name<'a>(self: &'a $crate::list::ListArc<Self $(, $id)?>) -> &'a $typ {
> + let field = &(&**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 { $field:ident }
> + $($rest:tt)*
> + ) => {
> + $pub fn $name<'a>(self: &'a mut $crate::list::ListArc<Self $(, $id)?>) -> &'a mut $typ {
> + let field = &(&**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)*);
> + };
> +
> + () => {};
> +}
> +pub use define_list_arc_field_getter;
>
> --
> 2.44.0.478.gd926399ef9-goog
>
On 02.04.24 14:17, Alice Ryhl wrote:
> @@ -180,6 +184,41 @@ unsafe fn from_fields(me: *mut ListLinksFields) -> *mut Self {
> }
> }
>
> +/// Similar to [`ListLinks`], but also contains a pointer to the full value.
> +///
> +/// This type can be used instead of [`ListLinks`] to support lists with trait objects.
> +#[repr(C)]
> +pub struct ListLinksSelfPtr<T: ?Sized, const ID: u64 = 0> {
> + /// The `ListLinks` field inside this value.
> + ///
> + /// This is public so that it can be used with `impl_has_list_links!`.
> + pub inner: ListLinks<ID>,
> + self_ptr: UnsafeCell<MaybeUninit<*const T>>,
> +}
> +
> +unsafe impl<T: ?Sized + Send, const ID: u64> Send for ListLinksSelfPtr<T, ID> {}
> +unsafe impl<T: ?Sized + Sync, const ID: u64> Sync for ListLinksSelfPtr<T, ID> {}
Missing SAFETY comments.
> +
> +impl<T: ?Sized, const ID: u64> ListLinksSelfPtr<T, ID> {
> + /// The offset from the [`ListLinks`] to the self pointer field.
> + pub const LIST_LINKS_SELF_PTR_OFFSET: usize = core::mem::offset_of!(Self, self_ptr);
> +
> + /// Creates a new initializer for this type.
> + pub fn new() -> impl PinInit<Self> {
> + // 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(),
> + }),
> + },
Why don't you use `inner <- ListLinks::new(),`?
> + self_ptr: UnsafeCell::new(MaybeUninit::zeroed()),
> + }
> + }
> +}
> +
> impl<T: ?Sized + ListItem<ID>, const ID: u64> List<T, ID> {
> /// Creates a new empty list.
> pub const fn new() -> Self {
[...]
> @@ -94,5 +137,45 @@ unsafe fn post_remove(me: *mut ListLinks<$num>) -> *const Self {
> }
> }
> };
> +
> + (
> + impl$({$($generics:tt)*})? ListItem<$num:tt> for $t:ty {
> + using ListLinksSelfPtr;
> + } $($rest:tt)*
> + ) => {
> + unsafe impl$(<$($generics)*>)? ListItem<$num> for $t {
> + unsafe fn prepare_to_insert(me: *const Self) -> *mut ListLinks<$num> {
> + let links_field = unsafe { Self::view_links(me) };
> +
> + let spoff = ListLinksSelfPtr::<Self, $num>::LIST_LINKS_SELF_PTR_OFFSET;
> + let self_ptr = unsafe { (links_field as *const u8).add(spoff)
> + as *const ::core::cell::UnsafeCell<*const Self> };
> + let cell_inner = ::core::cell::UnsafeCell::raw_get(self_ptr);
> +
> + unsafe { ::core::ptr::write(cell_inner, me) };
> + links_field
> + }
> +
> + unsafe fn view_links(me: *const Self) -> *mut ListLinks<$num> {
> + unsafe {
> + <Self as HasListLinks<$num>>::raw_get_list_links(me.cast_mut())
> + }
> + }
> +
> + unsafe fn view_value(links_field: *mut ListLinks<$num>) -> *const Self {
> + let spoff = ListLinksSelfPtr::<Self, $num>::LIST_LINKS_SELF_PTR_OFFSET;
> + let self_ptr = unsafe { (links_field as *const u8).add(spoff)
> + as *const ::core::cell::UnsafeCell<*const Self> };
> + let cell_inner = ::core::cell::UnsafeCell::raw_get(self_ptr);
> + unsafe {
> + ::core::ptr::read(cell_inner)
> + }
> + }
> +
> + unsafe fn post_remove(me: *mut ListLinks<$num>) -> *const Self {
> + unsafe { Self::view_value(me) }
> + }
> + }
> + };
The paths in this macro should use `$crate::...` to prevent import
errors.
--
Cheers,
Benno
On 02.04.24 14:17, Alice Ryhl wrote:
> +impl<const ID: u64> ListLinks<ID> {
> + /// Creates a new initializer for this type.
> + pub fn new() -> impl PinInit<Self> {
> + // 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(),
> + }),
You might want to implement `Zeroable` (using the derive macro) for this
struct, since then you could just return `init::zeroed()`.
You can also use that for the `ListLinksSelfPtr` in the other patch.
--
Cheers,
Benno
> + }
> + }
> +}
>
> --
> 2.44.0.478.gd926399ef9-goog
>
On Fri, Apr 5, 2024 at 11:47 AM Benno Lossin <[email protected]> wrote:
>
> On 02.04.24 14:17, Alice Ryhl wrote:
> > +impl<const ID: u64> ListLinks<ID> {
> > + /// Creates a new initializer for this type.
> > + pub fn new() -> impl PinInit<Self> {
> > + // 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(),
> > + }),
>
> You might want to implement `Zeroable` (using the derive macro) for this
> struct, since then you could just return `init::zeroed()`.
> You can also use that for the `ListLinksSelfPtr` in the other patch.
Sure, that makes sense to me. I'll go for that.
Alice
On Thu, Apr 4, 2024 at 5:35 PM Benno Lossin <[email protected]> wrote:
>
> On 02.04.24 14:17, Alice Ryhl wrote:
> > @@ -180,6 +184,41 @@ unsafe fn from_fields(me: *mut ListLinksFields) -> *mut Self {
> > }
> > }
> >
> > +/// Similar to [`ListLinks`], but also contains a pointer to the full value.
> > +///
> > +/// This type can be used instead of [`ListLinks`] to support lists with trait objects.
> > +#[repr(C)]
> > +pub struct ListLinksSelfPtr<T: ?Sized, const ID: u64 = 0> {
> > + /// The `ListLinks` field inside this value.
> > + ///
> > + /// This is public so that it can be used with `impl_has_list_links!`.
> > + pub inner: ListLinks<ID>,
> > + self_ptr: UnsafeCell<MaybeUninit<*const T>>,
> > +}
> > +
> > +unsafe impl<T: ?Sized + Send, const ID: u64> Send for ListLinksSelfPtr<T, ID> {}
> > +unsafe impl<T: ?Sized + Sync, const ID: u64> Sync for ListLinksSelfPtr<T, ID> {}
>
> Missing SAFETY comments.
Will do.
> > +
> > +impl<T: ?Sized, const ID: u64> ListLinksSelfPtr<T, ID> {
> > + /// The offset from the [`ListLinks`] to the self pointer field.
> > + pub const LIST_LINKS_SELF_PTR_OFFSET: usize = core::mem::offset_of!(Self, self_ptr);
> > +
> > + /// Creates a new initializer for this type.
> > + pub fn new() -> impl PinInit<Self> {
> > + // 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(),
> > + }),
> > + },
>
> Why don't you use `inner <- ListLinks::new(),`?
Because I wasn't using the macro at all. I was just using the fact
that T implements PinInit<T>. But as discussed on another patch, I'll
replace this entire method with init::zeroed().
> > + self_ptr: UnsafeCell::new(MaybeUninit::zeroed()),
> > + }
> > + }
> > +}
> > +
> > impl<T: ?Sized + ListItem<ID>, const ID: u64> List<T, ID> {
> > /// Creates a new empty list.
> > pub const fn new() -> Self {
>
> [...]
>
> > @@ -94,5 +137,45 @@ unsafe fn post_remove(me: *mut ListLinks<$num>) -> *const Self {
> > }
> > }
> > };
> > +
> > + (
> > + impl$({$($generics:tt)*})? ListItem<$num:tt> for $t:ty {
> > + using ListLinksSelfPtr;
> > + } $($rest:tt)*
> > + ) => {
> > + unsafe impl$(<$($generics)*>)? ListItem<$num> for $t {
> > + unsafe fn prepare_to_insert(me: *const Self) -> *mut ListLinks<$num> {
> > + let links_field = unsafe { Self::view_links(me) };
> > +
> > + let spoff = ListLinksSelfPtr::<Self, $num>::LIST_LINKS_SELF_PTR_OFFSET;
> > + let self_ptr = unsafe { (links_field as *const u8).add(spoff)
> > + as *const ::core::cell::UnsafeCell<*const Self> };
> > + let cell_inner = ::core::cell::UnsafeCell::raw_get(self_ptr);
> > +
> > + unsafe { ::core::ptr::write(cell_inner, me) };
> > + links_field
> > + }
> > +
> > + unsafe fn view_links(me: *const Self) -> *mut ListLinks<$num> {
> > + unsafe {
> > + <Self as HasListLinks<$num>>::raw_get_list_links(me.cast_mut())
> > + }
> > + }
> > +
> > + unsafe fn view_value(links_field: *mut ListLinks<$num>) -> *const Self {
> > + let spoff = ListLinksSelfPtr::<Self, $num>::LIST_LINKS_SELF_PTR_OFFSET;
> > + let self_ptr = unsafe { (links_field as *const u8).add(spoff)
> > + as *const ::core::cell::UnsafeCell<*const Self> };
> > + let cell_inner = ::core::cell::UnsafeCell::raw_get(self_ptr);
> > + unsafe {
> > + ::core::ptr::read(cell_inner)
> > + }
> > + }
> > +
> > + unsafe fn post_remove(me: *mut ListLinks<$num>) -> *const Self {
> > + unsafe { Self::view_value(me) }
> > + }
> > + }
> > + };
>
> The paths in this macro should use `$crate::...` to prevent import
> errors.
Will do.
Alice
On Thu, Apr 4, 2024 at 4:52 PM Benno Lossin <[email protected]> wrote:
>
> On 04.04.24 16:41, Alice Ryhl wrote:
> > On Thu, Apr 4, 2024 at 4:36 PM Benno Lossin <[email protected]> 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.
On Thu, Apr 4, 2024 at 4:51 PM Benno Lossin <[email protected]> wrote:
>
> On 04.04.24 16:12, Alice Ryhl wrote:
> > On Thu, Apr 4, 2024 at 4:03 PM Benno Lossin <[email protected]> wrote:
> >> On 02.04.24 14:17, Alice Ryhl wrote:
> >>> + // never null for items in a list.
> >>> + //
> >>> + // INVARIANT: There are three cases:
> >>> + // * If the list has at least three items, then after removing the item, `prev` and `next`
> >>> + // will be next to each other.
> >>> + // * If the list has two items, then the remaining item will point at itself.
> >>> + // * If the list has one item, then `next == prev == item`, so these writes have no effect
> >>> + // due to the writes to `item` below.
> >>
> >> I think the writes do not have an effect. (no need to reference the
> >> writes to `item` below)
> >
> > ?
>
> The first write is
>
> (*next).prev = prev;
>
> Using the fact that `next == prev == item` we have
>
> (*item).prev = prev;
>
> But that is already true, since the function requirement is that
> `(*item).prev == prev`. So the write has no effect.
> The same should hold for `(*prev).next = next`.
Oh, you are arguing that we aren't changing the value? I hadn't
actually realized that this was the case. But the reason that they end
up with the correct values according to the invariants is the writes
below that set them to null - not the fact that we don't change them
here. After all, setting them to a non-null value is wrong according
to the invariants.
Alice
> >>> + unsafe {
> >>> + (*next).prev = prev;
> >>> + (*prev).next = next;
> >>> + }
> >>> + // SAFETY: We have exclusive access to items in the list.
> >>> + // INVARIANT: The item is no longer in a list, so the pointers should be null.
> >>> + unsafe {
> >>> + (*item).prev = ptr::null_mut();
> >>> + (*item).next = ptr::null_mut();
> >>> + }
On 08.04.24 10:04, Alice Ryhl wrote:
> On Thu, Apr 4, 2024 at 4:51 PM Benno Lossin <[email protected]> wrote:
>>
>> On 04.04.24 16:12, Alice Ryhl wrote:
>>> On Thu, Apr 4, 2024 at 4:03 PM Benno Lossin <[email protected]> wrote:
>>>> On 02.04.24 14:17, Alice Ryhl wrote:
>>>>> + // never null for items in a list.
>>>>> + //
>>>>> + // INVARIANT: There are three cases:
>>>>> + // * If the list has at least three items, then after removing the item, `prev` and `next`
>>>>> + // will be next to each other.
>>>>> + // * If the list has two items, then the remaining item will point at itself.
>>>>> + // * If the list has one item, then `next == prev == item`, so these writes have no effect
>>>>> + // due to the writes to `item` below.
>>>>
>>>> I think the writes do not have an effect. (no need to reference the
>>>> writes to `item` below)
>>>
>>> ?
>>
>> The first write is
>>
>> (*next).prev = prev;
>>
>> Using the fact that `next == prev == item` we have
>>
>> (*item).prev = prev;
>>
>> But that is already true, since the function requirement is that
>> `(*item).prev == prev`. So the write has no effect.
>> The same should hold for `(*prev).next = next`.
>
> Oh, you are arguing that we aren't changing the value? I hadn't
> actually realized that this was the case. But the reason that they end
> up with the correct values according to the invariants is the writes
> below that set them to null - not the fact that we don't change them
> here. After all, setting them to a non-null value is wrong according
> to the invariants.
I just was confused by the "due to the writes to `item` below".
In the single element case, I also think that the INVARIANT comment of
the next `unsafe` block (still visible in this mail) is a bit weird,
since the element still is in the list.
For a single item, removing it is setting the prev, next and first
pointers to null. So I think you might be able to use this for the last
bullet point:
* If the list has one item, then `next == prev == item`, so these
writes have no effect, since also `(*item).prev == prev` and
`(*item).next == next` by function requirement.
For the INVARIANT comment below, I think you also need the case
distinction:
* If the list had more than one item, `item` is no longer in the
list, so the pointers should be null.
* If the list had one item, then `item` points to itself, to remove
it, we set `prev` and `next` to null and later also `self.first`.
What do you think?
--
Cheers,
Benno
>
> Alice
>
>>>>> + unsafe {
>>>>> + (*next).prev = prev;
>>>>> + (*prev).next = next;
>>>>> + }
>>>>> + // SAFETY: We have exclusive access to items in the list.
>>>>> + // INVARIANT: The item is no longer in a list, so the pointers should be null.
>>>>> + unsafe {
>>>>> + (*item).prev = ptr::null_mut();
>>>>> + (*item).next = ptr::null_mut();
>>>>> + }
On Thu, Apr 4, 2024 at 4:00 PM Alice Ryhl <[email protected]> wrote:
>
> On Wed, Apr 3, 2024 at 5:51 PM Benno Lossin <[email protected]> wrote:
> >
> > On 02.04.24 14:16, Alice Ryhl wrote:
> > > +impl<T: ListArcSafe<ID>, const ID: u64> ListArc<T, ID> {
> > > + /// Constructs a new reference counted instance of `T`.
> > > + pub fn try_new(contents: T) -> Result<Self, AllocError> {
> > > + Ok(Self::from_unique(UniqueArc::try_new(contents)?))
> > > + }
> > > +
> > > + /// Use the given initializer to in-place initialize a `T`.
> > > + ///
> > > + /// If `T: !Unpin` it will not be able to move afterwards.
> > > + pub fn pin_init<E>(init: impl PinInit<T, E>) -> error::Result<Self>
> > > + where
> > > + Error: From<E>,
> > > + {
> > > + Ok(Self::from_pin_unique(UniqueArc::pin_init(init)?))
> > > + }
> >
> > pin-init has a general trait for this: InPlaceInit. I don't know if the
> > other functions that it provides would help you.
>
> I will use that.
Turns out it's not possible to use the trait in this case, for the
same reasons as why Arc isn't using them either.
Alice