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 | 116 ++++++++++++++++++++++++++++++++++++++++++++++++++++
1 file changed, 116 insertions(+)
diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs
index c5caa0f6105c..b5cfbb96a392 100644
--- a/rust/kernel/list.rs
+++ b/rust/kernel/list.rs
@@ -4,7 +4,123 @@
//! 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 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.
+ ///
+ /// # 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.45.0.rc1.225.g2a3ae87e7f-goog
On 06.05.24 11:53, Alice Ryhl wrote:
> 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 | 116 ++++++++++++++++++++++++++++++++++++++++++++++++++++
> 1 file changed, 116 insertions(+)
>
> diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs
> index c5caa0f6105c..b5cfbb96a392 100644
> --- a/rust/kernel/list.rs
> +++ b/rust/kernel/list.rs
> @@ -4,7 +4,123 @@
>
> //! 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
I would not mention the number of methods, since it is difficult to
maintain and doesn't actually provide any value (it already is incorrect :)
> +/// 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 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.
> + ///
> + /// # 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.
Are there any synchronization requirements? Am I allowed to call
`prepare_to_insert` and `post_remove` on different threads without
synchronizing?
> + /// * 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.
As I read the requirements on `prepare_to_insert`, the caller is not
required to deconstruct the `ListArc`. For example the caller is allowed
to `clone_arc()` and then `into_raw()` and then pass that pointer to
`prepare_to_insert`.
So I would just remove this sentence.
> + ///
> + /// # Safety
> + ///
> + /// The provided pointer must be the pointer returned by the previous call to
Does "most recent call" make more sense? I find previous call a bit
weird. (also in the requirements above)
---
Cheers,
Benno
> + /// `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.45.0.rc1.225.g2a3ae87e7f-goog
>
On Mon, May 27, 2024 at 11:58 AM Benno Lossin <[email protected]> wrote:
>
> On 06.05.24 11:53, Alice Ryhl wrote:
> > 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 | 116 ++++++++++++++++++++++++++++++++++++++++++++++++++++
> > 1 file changed, 116 insertions(+)
> >
> > diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs
> > index c5caa0f6105c..b5cfbb96a392 100644
> > --- a/rust/kernel/list.rs
> > +++ b/rust/kernel/list.rs
> > @@ -4,7 +4,123 @@
> >
> > //! 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
>
> I would not mention the number of methods, since it is difficult to
> maintain and doesn't actually provide any value (it already is incorrect :)
I will remove the mention of a number.
> > + /// 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.
>
> Are there any synchronization requirements? Am I allowed to call
> `prepare_to_insert` and `post_remove` on different threads without
> synchronizing?
No, if you call them at the same time, then they aren't alternating.
> > + /// * 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.
>
> As I read the requirements on `prepare_to_insert`, the caller is not
> required to deconstruct the `ListArc`. For example the caller is allowed
> to `clone_arc()` and then `into_raw()` and then pass that pointer to
> `prepare_to_insert`.
> So I would just remove this sentence.
I will remove it.
> > + ///
> > + /// # Safety
> > + ///
> > + /// The provided pointer must be the pointer returned by the previous call to
>
> Does "most recent call" make more sense? I find previous call a bit
> weird. (also in the requirements above)
Sure, I can say "most recent".
Alice
> ---
> Cheers,
> Benno
>
> > + /// `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.45.0.rc1.225.g2a3ae87e7f-goog
> >
>
>