Add Rust linked list for reference counted values
Subsystems (2)
Alice Ryhl
reviewerv3 cover Add Rust linked list for reference counted values
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.
---
Changes in v3:
- Add assert_pinned! macro and use it to ensure that the field is structurally pinned when using the tracked_by strategy.
- Improve ListArcSafe docs.
- Use From trait for UniqueArc->ListArc conversions.
- Implement AsRef<Arc> for ListArc.
- Improve safety documentation related to ListItem.
- Improve invariants of List.
- Other minor docs improvements.
- Add Reviewed-by tags
- Link to v2: https://lore.kernel.org/r/[email protected]
Changes in v2:
- Rebase on top of the new allocation APIs.
- Implement Default for List.
- on_create_list_arc_from_unique now takes Pin<&mut Self>
- from_unique now calls from_pin_unique instead of the other way around
- Add #[inline] markers.
- Use build_assert in pair_from_unique.
- Simplify transmute_from_arc
- Make macros consistently use full paths.
- Many improvements to safety comments.
- Link to v1: https://lore.kernel.org/r/[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
Benno Lossin (1):
rust: init: add assert_pinned macro
rust/kernel/init.rs | 67 ++++ rust/kernel/init/__internal.rs | 29 ++ rust/kernel/lib.rs | 1 + rust/kernel/list.rs | 685 +++++++++++++++++++++++++++++++++ rust/kernel/list/arc.rs | 508 ++++++++++++++++++++++++ rust/kernel/list/arc_field.rs | 96 +++++ rust/kernel/list/impl_list_item_mod.rs | 268 +++++++++++++ 7 files changed, 1654 insertions(+)
---
base-commit: b1263411112305acf2af728728591465becb45b0
change-id: 20240221-linked-list-25169a90a4de
Best regards,
Signature · 1 line
Alice Ryhl <[email protected]>
Alice Ryhl
reviewerPATCH v3 1/10 rust: init: add `assert_pinned` macro
From: Benno Lossin <[email protected]>
Add a macro to statically check if a field of a struct is marked with #[pin] ie that it is structurally pinned. This can be used when unsafe code needs to rely on fields being structurally pinned.
The macro has a special "inline" mode for the case where the type depends on generic parameters from the surrounding scope.
--- rust/kernel/init.rs | 67 ++++++++++++++++++++++++++++++++++++++++++ rust/kernel/init/__internal.rs | 29 ++++++++++++++++++ 2 files changed, 96 insertions(+)
rust/kernel/init.rs +67 -0
@@ -742,6 +742,73 @@ macro_rules! try_init { }; } +/// Asserts that a field on a struct using `#[pin_data]` is marked with `#[pin]` ie. that it is +/// structurally pinned. +/// +/// # Example +/// +/// This will succeed: +/// ``` +/// use kernel::assert_pinned; +/// #[pin_data] +/// struct MyStruct { +/// #[pin] +/// some_field: u64, +/// } +/// +/// assert_pinned!(MyStruct, some_field, u64); +/// ``` +/// +/// This will fail: +/// ```compile_fail +/// use kernel::assert_pinned; +/// #[pin_data] +/// struct MyStruct { +/// some_field: u64, +/// } +/// +/// assert_pinned!(MyStruct, some_field, u64); +/// ``` +/// +/// Some uses of the macro may trigger the `can't use generic parameters from outer item` error. To +/// work around this, you may pass the `inline` parameter to the macro. The `inline` parameter can +/// only be used when the macro is invoked from a function body. +/// ``` +/// use kernel::assert_pinned; +/// #[pin_data] +/// struct Foo<T> { +/// #[pin] +/// elem: T, +/// } +/// +/// impl<T> Foo<T> { +/// pub fn project(self: Pin<&mut Self>) -> Pin<&mut T> { +/// assert_pinned!(Foo<T>, elem, T, inline); +/// +/// // SAFETY: The field is structurally pinned. +/// unsafe { self.map_unchecked_mut(|me| &mut me.elem) } +/// } +/// } +/// ``` +#[macro_export] +macro_rules! assert_pinned { + ($ty:ty, $field:ident, $field_ty:ty, inline) => { +let _ =move |ptr: *mut $field_ty| { +// SAFETY: This code is unreachable. +let data =unsafe { <$tyas $crate::init::__internal::HasPinData >::__pin_data () }; +let init = $crate::init::__internal::AlwaysFail ::<$field_ty>::new (); +// SAFETY: This code is unreachable. +unsafe { data.$field(ptr, init) }.ok (); + }; + }; + + ($ty:ty, $field:ident, $field_ty:ty) => { +const _: () = { + $crate::assert_pinned!($ty, $field, $field_ty, inline); + }; + }; +} +/// A pin-initializer for the type `T`. /// /// To use this initializer, you will need a suitable memory location that can hold a `T`. This can
rust/kernel/init/__internal.rs +29 -0
@@ -228,3 +228,32 @@ pub unsafe fn new() -> Self {Self (()) } } + +/// Initializer that always fails. +/// +/// Used by [`assert_pinned!`]. +/// +/// [`assert_pinned!`]: crate::assert_pinned +pub struct AlwaysFail <T : ?Sized > { + _t:PhantomData <T >, +} + +impl <T : ?Sized >AlwaysFail <T > { +/// Creates a new initializer that always fails. +pub fn new () ->Self { +Self { _t:PhantomData } + } +} + +impl <T : ?Sized >Default for AlwaysFail <T > { +fn default () ->Self { +Self ::new () + } +} + +// SAFETY: `__pinned_init` always fails, which is always okay. +unsafe impl <T : ?Sized >PinInit <T , ()>for AlwaysFail <T > { +unsafe fn __pinned_init (self, _slot: *mut T ) ->Result <(), ()> { +Err (()) + } +}
Signature · 1 line
2.45.2.1089.g2a221341d9-goog
Alice Ryhl
reviewerPATCH v3 2/10 rust: list: add ListArc
In reply to Alice RyhlThe 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.
--- rust/kernel/lib.rs | 1 + rust/kernel/list.rs | 8 ++ rust/kernel/list/arc.rs | 348 ++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 357 insertions(+)
rust/kernel/lib.rs +1 -0
@@ -33,6 +33,7 @@pub mod ioctl;#[cfg( CONFIG_KUNIT )] pub mod kunit; +pub mod list;#[cfg( CONFIG_NET )] pub mod net;pub mod page;
rust/kernel/list.rs new file +8 -0
@@ -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 };
rust/kernel/list/arc.rs new file +348 -0
348 lines not on this page · raw message
Signature · 1 line
2.45.2.1089.g2a221341d9-goog
Re: [PATCH v3 02/10] rust: list: add ListArc
Quoted 17 lines · Alice Ryhl
The
ListArctype can be thought of as a special reference to a refcounted object that owns the permission to manipulate thenext/prevpointers stored in the refcounted object. By ensuring that each object has only oneListArcreference, the owner of that reference is assured exclusive access to thenext/prevpointers. When aListArcis inserted into aList, theListtakes ownership of theListArcreference.There are various strategies for ensuring that a value has only one
ListArcreference. The simplest is to convert aUniqueArcinto aListArc. However, the refcounted object could also keep track of whether aListArcexists using a boolean, which could allow for the creation of newListArcreferences from anArcreference. Whatever strategy is used, the relevant tracking is referred to as "the tracking insideT", and theListArcSafetrait (and its subtraits) are used to update the tracking when aListArcis created or destroyed.
Quoted 7 lines
Note that we allow the case where the tracking inside
Tthinks that aListArcexists, but actually, there isn't aListArc. However, we do not allow the opposite situation where aListArcexists, but the tracking thinks it doesn't. This is because the former can at most result in us failing to create aListArcwhen the operation could succeed, whereas the latter can result in the creation of twoListArcreferences.
You could add at the end of this paragraph that the latter is a soundness issue and could lead to memory bugs, but the former cannot.
Quoted 4 lines
This patch introduces the
impl_list_arc_safe!macro that allows you to implementListArcSafefor types using the strategy where aListArccan only be created from aUniqueArc. Other strategies are introduced in later patches.
[...]
Quoted 20 lines
rust/kernel/list/arc.rs new file +14
-0@@ -0,0 +1,348 @@ +// SPDX-License-Identifier: GPL-2.0 + +// Copyright (C) 2024 Google LLC. + +//! A wrapper around `Arc` for linked lists. + +use crate ::alloc::{AllocError ,Flags }; +use crate ::prelude::*; +use crate ::sync::{Arc ,ArcBorrow ,UniqueArc }; +use core::marker::Unsize ; +use core::ops::Deref ; +use core::pin::Pin ; + +/// Declares that this type has some way to ensure that there is exactly one `ListArc` instance for
rust/kernel/list/arc.rs line 24
Quoted 10 lines
rust/kernel/list/arc.rs new file +10
-0+/// this id. +/// +/// Types that implement this trait should include some kind of logic for keeping track of whether +/// a [`ListArc`] exists or not. We refer to this logic as "the tracking inside `T`". +/// +/// 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.
Would be good to also add it here.
Quoted 57 lines
rust/kernel/list/arc.rs new file +57
-0+/// +/// A consequence of the above is that you may implement the tracking inside `T` by not actually +/// keeping track of anything. To do this, you always claim that a [`ListArc`] exists, even if +/// there isn't one. This implementation is allowed by the above rule, but it means that +/// [`ListArc`] references can only be created if you have ownership of *all* references to the +/// refcounted object, as you otherwise have no way of knowing whether a [`ListArc`] exists. +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 (self:Pin <&mut Self >); + +/// Informs the tracking inside this type that there is no [`ListArc`] reference anymore. +/// +/// # Safety +/// +/// Must only be called if there is no [`ListArc`] reference, but the tracking thinks there is. +unsafe fn on_drop_list_arc (&self); +} + +/// Declares that this type supports [`ListArc`]. +/// +/// When using this macro, it will only be possible to create a [`ListArc`] from a [`UniqueArc`]. +#[macro_export] +macro_rules! impl_list_arc_safe { + (impl $({$($generics:tt)*})?ListArcSafe <$num:tt>for $t:ty { untracked; } $($rest:tt)*) => { +impl $(<$($generics)*>)? $crate::list::ListArcSafe <$num>for $t { +unsafe fn on_create_list_arc_from_unique (self: ::core::pin::Pin <&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. +///
rust/kernel/list/arc.rs line 91
Quoted 10 lines
rust/kernel/list/arc.rs new file +10
-0+/// 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.
I am not entirely sure where to put this, but I think it might be good as the first paragraph or directly after the first:
While this ListArc is unique for the given id, there still might exist normal Arc references to the object.
Feel free to modify it (I am not really happy with "object").
Quoted 7 lines
rust/kernel/list/arc.rs new file +7
-0+#[repr(transparent)] +pub struct ListArc <T ,const ID :u64 =0 > +where +T :ListArcSafe <ID > + ?Sized , +{ + arc:Arc <T >, +}
[...]
rust/kernel/list/arc.rs line 211
Quoted 8 lines
rust/kernel/list/arc.rs new file +8
-0+/// 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 (arc:Arc <T >) ->Self {
I think the name is inaccurate now, since it is no longer a transmute, so maybe from_arc_unchecked?
rust/kernel/list/arc.rs line 221
Quoted 10 lines
rust/kernel/list/arc.rs new file +10
-0+// INVARIANT: By the safety requirements, the invariants on `ListArc` are satisfied. +Self { arc } + } + +/// 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 > {
Maybe also change this then to be consistent, since the name transmute carries a "dangerous" feel to it, but this is actually totally safe.
Quoted 5 lines
rust/kernel/list/arc.rs new file +5
-0+// Use a transmute to skip destructor. +// +// SAFETY: ListArc is repr(transparent). +unsafe { core::mem::transmute (self) } + }
[...]
Quoted 10 lines
rust/kernel/list/arc.rs new file +10
-0+// 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 , +{
rust/kernel/list/arc.rs line 348
Quoted 10 lines
rust/kernel/list/arc.rs new file +10
-0+} + +// 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 , +{ +}
Can we start using feature(derive_smart_pointer) on new enough compiler versions? (I guess you probably want it as a separate patch series to avoid delaying this in case it needs anything [eg the new build system])
Do we need any Makefile modifications for that or could we just do #[cfg_attr(compiler-is-new-enough, derive(SmartPointer)) on the struct and then cfg these impls away? (and what would "compiler-is-new-enough" be?)
Aside from my docs nits, this looks good:
(feel free to discuss any changes, I am not set on the exact phrasing)
---
Cheers,
Benno
Alice Ryhl
reviewerRe: [PATCH v3 02/10] rust: list: add ListArc
Quoted 27 lines · Benno Lossin
Quoted 17 lines · Alice Ryhl
The
ListArctype can be thought of as a special reference to a refcounted object that owns the permission to manipulate thenext/prevpointers stored in the refcounted object. By ensuring that each object has only oneListArcreference, the owner of that reference is assured exclusive access to thenext/prevpointers. When aListArcis inserted into aList, theListtakes ownership of theListArcreference.There are various strategies for ensuring that a value has only one
ListArcreference. The simplest is to convert aUniqueArcinto aListArc. However, the refcounted object could also keep track of whether aListArcexists using a boolean, which could allow for the creation of newListArcreferences from anArcreference. Whatever strategy is used, the relevant tracking is referred to as "the tracking insideT", and theListArcSafetrait (and its subtraits) are used to update the tracking when aListArcis created or destroyed.Quoted 7 lines
Note that we allow the case where the tracking inside
Tthinks that aListArcexists, but actually, there isn't aListArc. However, we do not allow the opposite situation where aListArcexists, but the tracking thinks it doesn't. This is because the former can at most result in us failing to create aListArcwhen the operation could succeed, whereas the latter can result in the creation of twoListArcreferences.
Quoted 2 lines
You could add at the end of this paragraph that the latter is a soundness issue and could lead to memory bugs, but the former cannot.
Will do.
Quoted 31 lines
Quoted 4 lines
This patch introduces the
impl_list_arc_safe!macro that allows you to implementListArcSafefor types using the strategy where aListArccan only be created from aUniqueArc. Other strategies are introduced in later patches.[...]
Quoted 24 lines
rust/kernel/list/arc.rs new file +18
-0@@ -0,0 +1,348 @@ +// SPDX-License-Identifier: GPL-2.0 + +// Copyright (C) 2024 Google LLC. + +//! A wrapper around `Arc` for linked lists. + +use crate ::alloc::{AllocError ,Flags }; +use crate ::prelude::*; +use crate ::sync::{Arc ,ArcBorrow ,UniqueArc }; +use core::marker::Unsize ; +use core::ops::Deref ; +use core::pin::Pin ; + +/// Declares that this type has some way to ensure that there is exactly one `ListArc` instance for +/// this id. +/// +/// Types that implement this trait should include some kind of logic for keeping track of whether +/// a [`ListArc`] exists or not. We refer to this logic as "the tracking inside `T`".
Quoted 8 lines
rust/kernel/list/arc.rs line 24
Quoted 6 lines
rust/kernel/list/arc.rs new file +6
-0+/// +/// 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. Would be good to also add it here.
Will do.
Quoted 71 lines
Quoted 57 lines
rust/kernel/list/arc.rs new file +57
-0+/// +/// A consequence of the above is that you may implement the tracking inside `T` by not actually +/// keeping track of anything. To do this, you always claim that a [`ListArc`] exists, even if +/// there isn't one. This implementation is allowed by the above rule, but it means that +/// [`ListArc`] references can only be created if you have ownership of *all* references to the +/// refcounted object, as you otherwise have no way of knowing whether a [`ListArc`] exists. +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 (self:Pin <&mut Self >); + +/// Informs the tracking inside this type that there is no [`ListArc`] reference anymore. +/// +/// # Safety +/// +/// Must only be called if there is no [`ListArc`] reference, but the tracking thinks there is. +unsafe fn on_drop_list_arc (&self); +} + +/// Declares that this type supports [`ListArc`]. +/// +/// When using this macro, it will only be possible to create a [`ListArc`] from a [`UniqueArc`]. +#[macro_export] +macro_rules! impl_list_arc_safe { + (impl $({$($generics:tt)*})?ListArcSafe <$num:tt>for $t:ty { untracked; } $($rest:tt)*) => { +impl $(<$($generics)*>)? $crate::list::ListArcSafe <$num>for $t { +unsafe fn on_create_list_arc_from_unique (self: ::core::pin::Pin <&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. +/// rust/kernel/list/arc.rs line 91
Quoted 10 lines
rust/kernel/list/arc.rs new file +10
-0+/// 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. I am not entirely sure where to put this, but I think it might be good as the first paragraph or directly after the first:
Quoted 4 lines
While this
ListArcis unique for the given id, there still might exist normalArcreferences to the object.Feel free to modify it (I am not really happy with "object").
I added something about that above the heading.
Quoted 19 lines
Quoted 7 lines
rust/kernel/list/arc.rs new file +7
-0+#[repr(transparent)] +pub struct ListArc <T ,const ID :u64 =0 > +where +T :ListArcSafe <ID > + ?Sized , +{ + arc:Arc <T >, +}[...]
rust/kernel/list/arc.rs line 211
Quoted 8 lines
rust/kernel/list/arc.rs new file +8
-0+/// 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 (arc:Arc <T >) ->Self {
Quoted 2 lines
I think the name is inaccurate now, since it is no longer a transmute, so maybe
from_arc_unchecked?
I think it's fine to keep the transmute name. It gives the right connotations.
Quoted 11 lines
rust/kernel/list/arc.rs line 221
Quoted 10 lines
rust/kernel/list/arc.rs new file +10
-0+// INVARIANT: By the safety requirements, the invariants on `ListArc` are satisfied. +Self { arc } + } + +/// 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 > {
Quoted 2 lines
Maybe also change this then to be consistent, since the name
transmutecarries a "dangerous" feel to it, but this is actually totally safe.
I want it to carry a dangerous feel! Yes, it's safe to leak the ListArc, but you don't want people to think it's a generic ListArc -> Arc conversion function.
Quoted 29 lines
Quoted 5 lines
rust/kernel/list/arc.rs new file +5
-0+// Use a transmute to skip destructor. +// +// SAFETY: ListArc is repr(transparent). +unsafe { core::mem::transmute (self) } + }[...]
Quoted 10 lines
rust/kernel/list/arc.rs new file +10
-0+// 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 , +{rust/kernel/list/arc.rs line 348
Quoted 10 lines
rust/kernel/list/arc.rs new file +10
-0+} + +// 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 , +{ +}
Quoted 8 lines
Can we start using
feature(derive_smart_pointer)on new enough compiler versions? (I guess you probably want it as a separate patch series to avoid delaying this in case it needs anything [eg the new build system])
Do we need anyMakefilemodifications for that or could we just do#[cfg_attr(compiler-is-new-enough, derive(SmartPointer))on the struct and then cfg these impls away? (and what would "compiler-is-new-enough" be?)
That probably won't be until 1.83 or something like that. It will have to be a follow-up.
Quoted 3 lines
Aside from my docs nits, this looks good:
Reviewed-by Benno Lossin <[email protected]>
Thanks!
Alice
Re: [PATCH v3 02/10] rust: list: add ListArc
Quoted 13 lines · Alice Ryhl
Quoted 12 lines · Benno Lossin
Quoted 10 lines · Alice Ryhl
rust/kernel/list/arc.rs new file +10
-0+// INVARIANT: By the safety requirements, the invariants on `ListArc` are satisfied. +Self { arc } + } + +/// 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 > {
Quoted 6 lines
Quoted 2 lines
Maybe also change this then to be consistent, since the name
transmutecarries a "dangerous" feel to it, but this is actually totally safe.I want it to carry a dangerous feel! Yes, it's safe to leak the ListArc, but you don't want people to think it's a generic ListArc -> Arc conversion function.
For me to_arc_unchecked would also "feel" dangerous, transmute is just more dangerous :)
Since this is not public I don't mind keeping transmute, I just find it a bit strange.
---
Cheers,
Benno
Re: [PATCH v3 02/10] rust: list: add ListArc
In reply to Benno LossinQuoted 9 lines · Benno Lossin
Can we start using
feature(derive_smart_pointer)on new enough compiler versions? (I guess you probably want it as a separate patch series to avoid delaying this in case it needs anything [eg the new build system])
Do we need anyMakefilemodifications for that or could we just do#[cfg_attr(compiler-is-new-enough, derive(SmartPointer))on the struct and then cfg these impls away? (and what would "compiler-is-new-enough" be?)
That is possible with the upcoming RUSTC_VERSION: you can have Kconfig symbol for a particular version/feature/etc. Please see the upcoming lints series for an example in the docs for that.
Cheers,
Miguel
Alice Ryhl
reviewerPATCH v3 3/10 rust: list: add tracking for ListArc
In reply to Alice RyhlAdd 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.
--- rust/kernel/list.rs | 4 +- rust/kernel/list/arc.rs | 162 +++++++++++++++++++++++++++++++++++++++++++++++- 2 files changed, 163 insertions(+), 3 deletions(-)
rust/kernel/list.rs +3 -1
@@ -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 , +};
rust/kernel/list/arc.rs +160 -2
193 lines not on this page · raw message
Signature · 1 line
2.45.2.1089.g2a221341d9-goog
Re: [PATCH v3 03/10] rust: list: add tracking for ListArc
rust/kernel/list/arc.rs pub trait ListArcSafe<const ID: u64 = 0> { · line 59
Quoted 13 lines · Alice Ryhl
rust/kernel/list/arc.rs +9
-0@@ -47,9 +48,30 @@ 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.
I think this could use some more explanation. It has been a couple weeks since I last reviewed this, so I forgot what exactly this does and at first I thought that the tracking is not updated. But it actually is. Additionally, the safety documentation does not ensure that this function updates the tracking. So maybe use this?:
Attempts to convert an Arc<Self> into a ListArc<Self>.
# Guarantees
* If the return value is true, then there exists no ListArc<Self, ID> pointing to this value. Additionally, the tracking inside of self now thinks there is a ListArc<Self, ID>.
And then add in the Safety section of the trait that the guarantees of try_new_list_arc need to be ensured.
Just to make sure: this method must handle concurrent access, but that should be guaranteed if Self: Sync, right?
Quoted 6 lines
rust/kernel/list/arc.rs +3
-1+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`].
rust/kernel/list/arc.rs pub trait ListArcSafe<const ID: u64 = 0> { · line 74
Quoted 10 lines
rust/kernel/list/arc.rs +10
-0+/// This macro supports a few different strategies for implementing the tracking inside the type: +/// +/// * The `untracked` strategy does not actually keep track of whether a [`ListArc`] exists. When +/// using this strategy, the only way to create a [`ListArc`] is using a [`UniqueArc`]. +/// * The `tracked_by` strategy defers the tracking to a field of the struct. The user much specify +/// which field to defer the tracking to. The field must implement [`ListArcSafe`]. +/// +/// The `tracked_by` strategy is usually used by deferring to a field of type +/// [`AtomicListArcTracker`]. However, it is also possible to defer the tracking to another struct +/// using also using this macro.
Can you add that if the field selected by the tracked_by strategy implements TryNewListArc, so will $t?
Quoted 6 lines
rust/kernel/list/arc.rs +0
-0#[macro_export] macro_rules! impl_list_arc_safe { (impl $({$($generics:tt)*})?ListArcSafe <$num:tt>for $t:ty { untracked; } $($rest:tt)*) => {@@ -60,6 +82,39 @@ unsafe fn on_drop_list_arc(&self) {} $crate::list::impl_list_arc_safe! { $($rest)* } };
[...]
rust/kernel/list/arc.rs impl<T, U, const ID: u64> core::ops::DispatchFromDyn<ListArc<U, ID>> for ListArc · line 457
Quoted 12 lines
rust/kernel/list/arc.rs +8
-0@@ -346,3 +447,60 @@ 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 > {
I am not a fan of this long name, what about AtomicTracker? I could see this type also being used by other things that need tracking.
Review impl<T, U, const ID: u64> core::ops::DispatchFromDyn<ListArc<U, ID>> for ListArc · line 459
Quoted 2 lines
(quoted diff) +2
-0+ inner: AtomicBool, + _pin: PhantomPinned,
Would be nice to have a comment explaining why this is needed. IIUC then it is needed because of the INVARIANT comment in new().
---
Cheers,
Benno
Quoted 12 lines
rust/kernel/list/arc.rs +12
-0+} + +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 , + } + }
Alice Ryhl
reviewerPATCH v3 4/10 rust: list: add struct with prev/next pointers
In reply to Alice RyhlDefine 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.
--- rust/kernel/list.rs | 115 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 115 insertions(+)
rust/kernel/list.rs +115 -0
@@ -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 methods provided by +/// this trait. +/// +/// [`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 most recent 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 most recent call to `prepare_to_insert`, or +/// from a call to `view_links` that happened after the most recent call to +/// `prepare_to_insert`. +/// * Since the most recent call to `prepare_to_insert`, the `post_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`. +/// +/// # Safety +/// +/// The provided pointer must be the pointer returned by the most recent 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 (), + }), + } + } +}
Signature · 1 line
2.45.2.1089.g2a221341d9-goog
Re: [PATCH v3 04/10] rust: list: add struct with prev/next pointers
rust/kernel/list.rs line 104
Quoted 9 lines · Alice Ryhl
rust/kernel/list.rs +9
-0+/// 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 >,
Do you really need Opaque? Or would UnsafeCell be enough? (If it is enough and you change this, be aware that Opaque is !Unpin, so if you intend for ListLinks to also be !Unpin, then you need a PhantomPinned)
rust/kernel/list.rs line 107
Quoted 3 lines
rust/kernel/list.rs +3
-0+} + +// SAFETY: The next/prev fields of a ListLinks can be moved across thread boundaries.
Why? This is not a justification.
rust/kernel/list.rs line 110
Quoted 3 lines
rust/kernel/list.rs +3
-0+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.
You don't need to argue via Opaque, the type doesn't expose any &self functions, so there are no functions to consider.
---
Cheers,
Benno
Quoted 19 lines
rust/kernel/list.rs +15
-1+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.2.1089.g2a221341d9-goog
Alice Ryhl
reviewerRe: [PATCH v3 04/10] rust: list: add struct with prev/next pointers
Quoted 16 lines · Benno Lossin
rust/kernel/list.rs line 104
Quoted 9 lines · Alice Ryhl
rust/kernel/list.rs +9
-0+/// 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 >,Do you really need
Opaque? Or wouldUnsafeCellbe enough? (If it is enough and you change this, be aware thatOpaqueis!Unpin, so if you intend forListLinksto also be!Unpin, then you need aPhantomPinned)
I need the !Unpin part for aliasing.
Quoted 5 lines
rust/kernel/list.rs line 107
Quoted 3 lines
rust/kernel/list.rs +3
-0+} + +// SAFETY: The next/prev fields of a ListLinks can be moved across thread boundaries. Why? This is not a justification.
What would you say?
Quoted 6 lines
rust/kernel/list.rs line 110
Quoted 3 lines
rust/kernel/list.rs +3
-0+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. You don't need to argue via
Opaque, the type doesn't expose any&selffunctions, so there are no functions to consider.
I'm not arguing via the Opaque type. I'm just using "opaque" as a normal english word with its normal meaning.
Alice
Re: [PATCH v3 04/10] rust: list: add struct with prev/next pointers
Quoted 18 lines · Alice Ryhl
Quoted 16 lines · Benno Lossin
rust/kernel/list.rs line 104
Quoted 9 lines · Alice Ryhl
rust/kernel/list.rs +9
-0+/// 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 >,Do you really need
Opaque? Or wouldUnsafeCellbe enough? (If it is enough and you change this, be aware thatOpaqueis!Unpin, so if you intend forListLinksto also be!Unpin, then you need aPhantomPinned)
Quoted 1 line
I need the
!Unpinpart for aliasing.
Oh good point, do you mind adding a comment for that?
Quoted 7 lines
Quoted 5 lines
rust/kernel/list.rs line 107
Quoted 3 lines
rust/kernel/list.rs +3
-0+} + +// SAFETY: The next/prev fields of a ListLinks can be moved across thread boundaries. Why? This is not a justification.
What would you say?
While trying to come up with a safety comment I thought about the
following: this impl does not depend on the type that is behind the pointer (ie the type containing the ListLinks). Thus this ListLinks will always implement Send even if the pointed-to value does not. What we could do (and what definitely would be correct) is this:List can only be used with Send types, then we could implement Send for ListLinks. But I haven't actually come up with a problem, so there might a more permissive solution.
Do you have a use-case where you need !Send types in a list?
Here is a part of my reasoning: If the pointed-to value is !Send, then the List item type must also be !Send. Thus all list operations take place on the same thread (since the List will be !Send). Therefore nobody can access the prev/next pointers from another thread.
But this does not justify that ListLinks can be made Send. (although there isn't actually a problem)
Quoted 9 lines
Quoted 6 lines
rust/kernel/list.rs line 110
Quoted 3 lines
rust/kernel/list.rs +3
-0+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. You don't need to argue via
Opaque, the type doesn't expose any&selffunctions, so there are no functions to consider.I'm not arguing via the
Opaquetype. I'm just using "opaque" as a normal english word with its normal meaning.
Oh I see, then it's fine.
---
Cheers,
Benno
Alice Ryhl
reviewerRe: [PATCH v3 04/10] rust: list: add struct with prev/next pointers
Quoted 42 lines · Benno Lossin
Quoted 18 lines · Alice Ryhl
Quoted 16 lines · Benno Lossin
rust/kernel/list.rs line 104
Quoted 9 lines · Alice Ryhl
rust/kernel/list.rs +9
-0+/// 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 >,Do you really need
Opaque? Or wouldUnsafeCellbe enough? (If it is enough and you change this, be aware thatOpaqueis!Unpin, so if you intend forListLinksto also be!Unpin, then you need aPhantomPinned)Quoted 1 line
I need the
!Unpinpart for aliasing.Oh good point, do you mind adding a comment for that?
Quoted 7 lines
Quoted 5 lines
rust/kernel/list.rs line 107
Quoted 3 lines
rust/kernel/list.rs +3
-0+} + +// SAFETY: The next/prev fields of a ListLinks can be moved across thread boundaries. Why? This is not a justification.
What would you say?
While trying to come up with a safety comment I thought about the
following: this impl does not depend on the type that is behind the pointer (ie the type containing theListLinks). Thus thisListLinkswill always implementSendeven if the pointed-to value does not. What we could do (and what definitely would be correct) is this:Listcan only be used withSendtypes, then we could implementSendforListLinks. But I haven't actually come up with a problem, so there might a more permissive solution.
Do you have a use-case where you need!Sendtypes in a list?
Quoted 7 lines
Here is a part of my reasoning: If the pointed-to value is
!Send, then theListitem type must also be!Send. Thus all list operations take place on the same thread (since theListwill be!Send). Therefore nobody can access theprev/nextpointers from another thread.But this does not justify that
ListLinkscan be madeSend. (although there isn't actually a problem)
I don't think there's any reason to forbid lists with !Send types. The List just becomes !Send too.
Alice
Re: [PATCH v3 04/10] rust: list: add struct with prev/next pointers
Quoted 43 lines · Alice Ryhl
Quoted 42 lines · Benno Lossin
Quoted 18 lines · Alice Ryhl
Quoted 16 lines · Benno Lossin
rust/kernel/list.rs line 104
Quoted 9 lines · Alice Ryhl
rust/kernel/list.rs +9
-0+/// 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 >,Do you really need
Opaque? Or wouldUnsafeCellbe enough? (If it is enough and you change this, be aware thatOpaqueis!Unpin, so if you intend forListLinksto also be!Unpin, then you need aPhantomPinned)Quoted 1 line
I need the
!Unpinpart for aliasing.Oh good point, do you mind adding a comment for that?
Quoted 7 lines
Quoted 5 lines
rust/kernel/list.rs line 107
Quoted 3 lines
rust/kernel/list.rs +3
-0+} + +// SAFETY: The next/prev fields of a ListLinks can be moved across thread boundaries. Why? This is not a justification.
What would you say?
While trying to come up with a safety comment I thought about the
following: this impl does not depend on the type that is behind the pointer (ie the type containing theListLinks). Thus thisListLinkswill always implementSendeven if the pointed-to value does not. What we could do (and what definitely would be correct) is this:Listcan only be used withSendtypes, then we could implementSendforListLinks. But I haven't actually come up with a problem, so there might a more permissive solution.
Do you have a use-case where you need!Sendtypes in a list?
Quoted 7 lines
Quoted 7 lines
Here is a part of my reasoning: If the pointed-to value is
!Send, then theListitem type must also be!Send. Thus all list operations take place on the same thread (since theListwill be!Send). Therefore nobody can access theprev/nextpointers from another thread.But this does not justify that
ListLinkscan be madeSend. (although there isn't actually a problem)
I think I confused myself. The paragraph above actually explains why we are allowed to make ListLinks: Send. What do you think of the following comment:
// SAFETY: The only way to access/modify the pointers inside of ListLinks<ID> is via holding the // associated ListArc<T, ID>. Since that type correctly implements Send, it is impossible to // move this an instance of this type to a different thread if the pointees are !Send.
Quoted 2 lines
I don't think there's any reason to forbid lists with !Send types. The List just becomes !Send too.
Yes, but that doesn't explain why ListLinks is allowed to be Send.
---
Cheers,
Benno
Alice Ryhl
reviewerRe: [PATCH v3 04/10] rust: list: add struct with prev/next pointers
Quoted 53 lines · Benno Lossin
Quoted 43 lines · Alice Ryhl
Quoted 42 lines · Benno Lossin
Quoted 18 lines · Alice Ryhl
Quoted 16 lines · Benno Lossin
rust/kernel/list.rs line 104
Quoted 9 lines · Alice Ryhl
rust/kernel/list.rs +9
-0+/// 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 >,Do you really need
Opaque? Or wouldUnsafeCellbe enough? (If it is enough and you change this, be aware thatOpaqueis!Unpin, so if you intend forListLinksto also be!Unpin, then you need aPhantomPinned)Quoted 1 line
I need the
!Unpinpart for aliasing.Oh good point, do you mind adding a comment for that?
Quoted 7 lines
Quoted 5 lines
rust/kernel/list.rs line 107
Quoted 3 lines
rust/kernel/list.rs +3
-0+} + +// SAFETY: The next/prev fields of a ListLinks can be moved across thread boundaries. Why? This is not a justification.
What would you say?
While trying to come up with a safety comment I thought about the
following: this impl does not depend on the type that is behind the pointer (ie the type containing theListLinks). Thus thisListLinkswill always implementSendeven if the pointed-to value does not. What we could do (and what definitely would be correct) is this:Listcan only be used withSendtypes, then we could implementSendforListLinks. But I haven't actually come up with a problem, so there might a more permissive solution.
Do you have a use-case where you need!Sendtypes in a list?Quoted 7 lines
Quoted 7 lines
Here is a part of my reasoning: If the pointed-to value is
!Send, then theListitem type must also be!Send. Thus all list operations take place on the same thread (since theListwill be!Send). Therefore nobody can access theprev/nextpointers from another thread.But this does not justify that
ListLinkscan be madeSend. (although there isn't actually a problem)
Quoted 7 lines
I think I confused myself. The paragraph above actually explains why we are allowed to make
ListLinks: Send. What do you think of the following comment:// SAFETY: The only way to access/modify the pointers inside of
ListLinks<ID>is via holding the // associatedListArc<T, ID>. Since that type correctly implementsSend, it is impossible to // move this an instance of this type to a different thread if the pointees are!Send.
I will use that, thanks.
Alice
Alice Ryhl
reviewerPATCH v3 5/10 rust: list: add macro for implementing ListItem
In reply to Alice RyhlAdds 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.
--- rust/kernel/list.rs | 3 + rust/kernel/list/impl_list_item_mod.rs | 139 +++++++++++++++++++++++++++++++++ 2 files changed, 142 insertions(+)
rust/kernel/list.rs +3 -0
@@ -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 ,
rust/kernel/list/impl_list_item_mod.rs new file +139 -0
139 lines not on this page · raw message
Signature · 1 line
2.45.2.1089.g2a221341d9-goog
Alice Ryhl
reviewerRe: [PATCH v3 05/10] rust: list: add macro for implementing ListItem
rust/kernel/list/impl_list_item_mod.rs line 80
Quoted 6 lines · Alice Ryhl
rust/kernel/list/impl_list_item_mod.rs new file +6
-0+#[macro_export] +macro_rules! impl_list_item { + ( + impl$({$($generics:tt)*})? ListItem<$num:tt> for $t:ty { + using ListLinks; + } $($rest:tt)*
This uses $($rest:tt)* but does not call itself at the end. This means that trying to use this macro with several impl blocks results in additional impl blocks being silently swallowed. The macro should use repetition properly here.
Alice
Re: [PATCH v3 05/10] rust: list: add macro for implementing ListItem
In reply to Alice RyhlQuoted 8 lines · Alice Ryhl
rust/kernel/list/impl_list_item_mod.rs new file +2
-0@@ -0,0 +1,139 @@ +// SPDX-License-Identifier: GPL-2.0 +
rust/kernel/list/impl_list_item_mod.rs line 12
Quoted 10 lines
rust/kernel/list/impl_list_item_mod.rs new file +10
-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.
Can you reference the impl_has_list_links! macro here to guide the user to the safe version?
Quoted 9 lines
rust/kernel/list/impl_list_item_mod.rs new file +9
-0+/// +/// # Safety +/// +/// All values of this type must have a `ListLinks<ID>` field at the given offset. +/// +/// The implementation of `raw_get_list_links` must not be changed. +pub unsafe trait HasListLinks <const ID :u64 =0 > { +/// The offset of the `ListLinks` field. +const OFFSET :usize ;
rust/kernel/list/impl_list_item_mod.rs line 31
Quoted 10 lines
rust/kernel/list/impl_list_item_mod.rs new file +10
-0+ +/// 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.
Stale comment (this has nothing to do with impl_has_work!).
Quoted 31 lines
rust/kernel/list/impl_list_item_mod.rs new file +31
-0+#[inline] +unsafe fn raw_get_list_links (ptr: *mut Self ) -> *mut ListLinks <ID > { +// SAFETY: The caller promises that the pointer is valid. The implementer promises that the +// `OFFSET` constant is correct. +unsafe { (ptras *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. + // + // The implementation of `raw_get_list_links` is not changed since the `addr_of_mut!` macro + // is equivalent to the pointer offset operation in the trait definition. + 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. We know that this + // expression doesn't follow any pointers, as the `offset_of!` invocation above + // would otherwise not compile.
rust/kernel/list/impl_list_item_mod.rs line 72
Quoted 10 lines
rust/kernel/list/impl_list_item_mod.rs new file +10
-0+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`].
I would write "Requires", since "Assumes" sounds as if it isn't checked.
Can you also reference the impl_has_list_links! macro here to guide the user to the safe version?
Quoted 51 lines
rust/kernel/list/impl_list_item_mod.rs new file +51
-0+/// +/// [`ListItem`]: crate::list::ListItem +#[macro_export] +macro_rules! impl_list_item { + ( +impl $({$($generics:tt)*})?ListItem <$num:tt>for $t:ty { + usingListLinks ; + } $($rest:tt)* + ) => { +// SAFETY: See GUARANTEES comment on each method. +unsafe impl $(<$($generics)*>)? $crate::list::ListItem <$num>for $t { +// GUARANTEES: +// * This returns the same pointer as `prepare_to_insert` because `prepare_to_insert` +// is implemented in terms of `view_links`. +// * By the type invariants of `ListLinks`, the `ListLinks` has two null pointers when +// this value is not in a list. +unsafe fn view_links(me: *const Self ) -> *mut $crate::list::ListLinks <$num> { +// SAFETY: The caller guarantees that `me` points at a valid value of type `Self`. +unsafe { + <Self as $crate::list::HasListLinks <$num>>::raw_get_list_links(me.cast_mut()) + } + } + +// GUARANTEES: +// * `me` originates from the most recent call to `prepare_to_insert`, which just added +// `offset` to the pointer passed to `prepare_to_insert`. This method subtracts +// `offset` from `me` so it returns the pointer originally passed to +// `prepare_to_insert`. +// * The pointer remains valid until the next call to `post_remove` because the caller +// of the most recent call to `prepare_to_insert` promised to retain ownership of the +// `ListArc` containing `Self` until the next call to `post_remove`. The value cannot +// be destroyed while a `ListArc` reference exists. +unsafe fn view_value (me: *mut $crate::list::ListLinks <$num>) -> *const Self { +let offset = <Self as $crate::list::HasListLinks <$num>>::OFFSET ; +// SAFETY: `me` originates from the most recent call to `prepare_to_insert`, so it +// points at the field at offset `offset` in a value of type `Self`. Thus, +// subtracting `offset` from `me` is still in-bounds of the allocation. +unsafe { (meas *const u8 ).sub (offset)as *const Self } + } + +// GUARANTEES: +// This implementation of `ListItem` will not give out exclusive access to the same +// `ListLinks` several times because calls to `prepare_to_insert` and `post_remove` +// must alternate and exclusive access is given up when `post_remove` is called. +// +// Other invocations of `impl_list_item!` also cannot give out exclusive access to the +// same `ListLinks` because you can only implement `ListItem` once for each value of +// `ID`, and the `ListLinks` fields only work with the specified `ID`. +unsafe fn prepare_to_insert (me: *const Self ) -> *mut $crate::list::ListLinks <$num> { +// SAFETY: The caller promises that `me` points at a valid value. +unsafe { <Self as $crate::list::ListItem <$num>>::view_links (me) }
rust/kernel/list/impl_list_item_mod.rs line 133
Quoted 10 lines
rust/kernel/list/impl_list_item_mod.rs new file +10
-0+ } + +// GUARANTEES: +// The first guarantee of `view_value` is exactly what `post_remove` guarantees. +unsafe fn post_remove (me: *mut $crate::list::ListLinks <$num>) -> *const Self { +// SAFETY: This violates the safety requirement that `post_remove` has not been +// called since the most recent call to `prepare_to_insert`, but that is okay +// because the concrete implementation of `view_value` above does not rely on that +// requirement anywhere except for its second guarantee, and we don't need its +// second guarantee.
I don't like the "this isn't correct, but if you look closely at the implementations, it's fine". Do you think it would be better if you just copy paste the impl of view_value?
---
Cheers,
Benno
Quoted 10 lines
rust/kernel/list/impl_list_item_mod.rs new file +6
-1+unsafe { <Self as $crate::list::ListItem <$num>>::view_value (me) } + } + } + }; +} +pub use impl_list_item; --2.45.2.1089.g2a221341d9-goog
Alice Ryhl
reviewerPATCH v3 6/10 rust: list: add List
In reply to Alice RyhlAdd the actual linked list itself.
The linked list uses the following design: The List type itself just has a single pointer to the first element of the list. And the actual list items then form a cycle. So the last item is first->prev.
This is slightly different from the usual kernel linked list. Matching that exactly would amount to giving List two pointers, and having it be part of the cycle of items. This alternate design has the advantage that the cycle is never completely empty, which can reduce the number of branches in some cases. However, it also has the disadvantage that List must be pinned, which this design is trying to avoid.
Having the list items form a cycle rather than having null pointers at the beginning/end is convenient for several reasons. For one, it lets us store only one pointer in List, and it simplifies the implementation of several functions.
Unfortunately, the remove function that removes an arbitrary element from the list has to be unsafe. This is needed because there is no way to handle the case where you pass an element from the wrong list. For example, if it is the first element of some other list, then that other list's first pointer would not be updated. Similarly, it could be a data race if you try to remove it from two different lists in parallel. (There's no problem with passing remove an item that's not in any list. Additionally, other removal methods such as pop_front need not be unsafe, as they can't be used to remove items from another list.)
A future patch in this series will introduce support for cursors that can be used to remove arbitrary items without unsafe code.
--- rust/kernel/list.rs | 331 +++++++++++++++++++++++++++++++++++++++++++++++- rust/kernel/list/arc.rs | 6 +- 2 files changed, 332 insertions(+), 5 deletions(-)
rust/kernel/list.rs +328 -3
@@ -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,42 @@ 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, `first` points at the `ListLinks` +/// field of the first element in the list. +/// * All prev/next pointers in `ListLinks` fields of items in the list are valid and form a cycle. +/// * For every item in the list, the list owns the associated [`ListArc`] reference and has +/// exclusive access to the `ListLinks` field. +pub struct List <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 ///
@@ -58,7 +94,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 +139,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 +160,294 @@ pub fn new() -> impl PinInit<Self> { }), } } + +/// # Safety +/// +/// `me` must be dereferencable. +#[inline] +unsafe fn fields (me: *mut Self ) -> *mut ListLinksFields { +// SAFETY: The caller promises that the pointer is valid. +unsafe {Opaque ::raw_get (ptr::addr_of!((*me).inner)) } + } + +/// # Safety +/// +/// `me` must be dereferencable. +#[inline] +unsafe fn from_fields (me: *mut ListLinksFields ) -> *mut Self { + me.cast () + } +} + +impl <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 raw_item =ListArc ::into_raw (item); +// SAFETY: +// * We just got `raw_item` from a `ListArc`, so it's in an `Arc`. +// * If this requirement is violated, then the previous caller of `prepare_to_insert` +// violated the safety requirement that they can't give up ownership of the `ListArc` +// until they call `post_remove`. +// * We own the `ListArc`. +// * Removing items from this list is always done using `remove_internal_inner`, which +// calls `post_remove` before giving up ownership. +let list_links =unsafe {T ::prepare_to_insert (raw_item) }; +// SAFETY: We have not yet called `post_remove`, so `list_links` is still valid. +let item =unsafe {ListLinks ::fields (list_links) }; + +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: 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 raw_item =ListArc ::into_raw (item); +// SAFETY: +// * We just got `raw_item` from a `ListArc`, so it's in an `Arc`. +// * If this requirement is violated, then the previous caller of `prepare_to_insert` +// violated the safety requirement that they can't give up ownership of the `ListArc` +// until they call `post_remove`. +// * We own the `ListArc`. +// * Removing items] from this list is always done using `remove_internal_inner`, which +// calls `post_remove` before giving up ownership. +let list_links =unsafe {T ::prepare_to_insert (raw_item) }; +// SAFETY: We have not yet called `post_remove`, so `list_links` is still valid. +let item =unsafe {ListLinks ::fields (list_links) }; + +if self.first.is_null () { +// SAFETY: The caller just gave us ownership of these fields. +// INVARIANT: A linked list with one item should be cyclic. +unsafe { + (*item).next = 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. (Note that by the safety requirements, +/// this means that the item is not in any list.) +/// +/// # Safety +/// +/// `item` must not be in a different linked list (with the same id). +pub unsafe fn remove (&mut self, item: &T ) ->Option <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 +/// +/// `item` 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 the pointers of items in the list, and the prev/next +// pointers are always valid for items in a list. +// +// INVARIANT: There are three cases: +// * If the list has at least three items, then after removing 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. The list remains unchanged and `item` is still in the list for now. +unsafe { + (*next).prev = prev; + (*prev).next = next; + } +// SAFETY: We have exclusive access to items in the list. +// INVARIANT: `item` is being removed, 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` pointer is the value that `item->prev` had when it was in this +// list, so it must be valid. There is no race since `prev` is still in the list and we +// still have exclusive access to the list. + self.first =unsafe { (*prev).next }; + } + +// SAFETY: `item` used to be in the list, so it is dereferencable by the type invariants +// of `List`. +let list_links =unsafe {ListLinks ::from_fields (item) }; +// SAFETY: Any pointer in the list originates from a `prepare_to_insert` call. +let raw_item =unsafe {T ::post_remove (list_links) }; +// SAFETY: The above call to `post_remove` guarantees that we can recreate the `ListArc`. +unsafe {ListArc ::from_raw (raw_item) } + } + +/// Moves all items from `other` into `self`. +/// +/// The items of `other` are added to the back of `self`, so the last item of `other` becomes +/// the last item of `self`. +pub fn push_all_back (&mut self, other: &mut List <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 >Default for List <T ,ID > { +fn default () ->Self { +List ::new () + } +} + +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); + } + } }
rust/kernel/list/arc.rs +4 -2
@@ -124,8 +124,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
@@ -144,6 +144,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
Signature · 1 line
2.45.2.1089.g2a221341d9-goog
Re: [PATCH v3 06/10] rust: list: add List
rust/kernel/list.rs pub fn new() -> impl PinInit<Self> { · line 203
Quoted 8 lines · Alice Ryhl
rust/kernel/list.rs +8
-0+/// Add the provided item to the back of the list. +pub fn push_back (&mut self, item:ListArc <T ,ID >) { +let raw_item =ListArc ::into_raw (item); +// SAFETY: +// * We just got `raw_item` from a `ListArc`, so it's in an `Arc`. +// * If this requirement is violated, then the previous caller of `prepare_to_insert` +// violated the safety requirement that they can't give up ownership of the `ListArc` +// until they call `post_remove`.
I don't like this negative phrasing, what about "Since we have ownership of the ListArc, post_remove must have been called after each previous call to prepare_to_insert."?
Quoted 19 lines
rust/kernel/list.rs +19
-0+// * We own the `ListArc`. +// * Removing items from this list is always done using `remove_internal_inner`, which +// calls `post_remove` before giving up ownership. +let list_links =unsafe {T ::prepare_to_insert (raw_item) }; +// SAFETY: We have not yet called `post_remove`, so `list_links` is still valid. +let item =unsafe {ListLinks ::fields (list_links) }; + +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: By the type invariant, this pointer is valid or null. We just checked that +// it's not null, so it must be valid.
rust/kernel/list.rs pub fn new() -> impl PinInit<Self> { · line 232
Quoted 10 lines
rust/kernel/list.rs +10
-0+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; + }
You have this pattern several times, maybe make a function for this?
rust/kernel/list.rs pub fn new() -> impl PinInit<Self> { · line 245
Quoted 13 lines
rust/kernel/list.rs +13
-0+ } + } + +/// Add the provided item to the front of the list. +pub fn push_front (&mut self, item:ListArc <T ,ID >) { +let raw_item =ListArc ::into_raw (item); +// SAFETY: +// * We just got `raw_item` from a `ListArc`, so it's in an `Arc`. +// * If this requirement is violated, then the previous caller of `prepare_to_insert` +// violated the safety requirement that they can't give up ownership of the `ListArc` +// until they call `post_remove`. +// * We own the `ListArc`. +// * Removing items] from this list is always done using `remove_internal_inner`, which
Typo: "]".
Quoted 26 lines
rust/kernel/list.rs +26
-0+// calls `post_remove` before giving up ownership. +let list_links =unsafe {T ::prepare_to_insert (raw_item) }; +// SAFETY: We have not yet called `post_remove`, so `list_links` is still valid. +let item =unsafe {ListLinks ::fields (list_links) }; + +if self.first.is_null () { +// SAFETY: The caller just gave us ownership of these fields. +// INVARIANT: A linked list with one item should be cyclic. +unsafe { + (*item).next = 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; + } + }
rust/kernel/list.rs pub fn new() -> impl PinInit<Self> { · line 281
Quoted 10 lines
rust/kernel/list.rs +10
-0+ 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.
Additionally you need the type invariant that pointers in linked lists are valid... This is a bit annoying, maybe in the future, we can have a ValidPtr type that we could use here instead to avoid these comments...
Quoted 39 lines
rust/kernel/list.rs +39
-0+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. (Note that by the safety requirements, +/// this means that the item is not in any list.) +/// +/// # Safety +/// +/// `item` must not be in a different linked list (with the same id). +pub unsafe fn remove (&mut self, item: &T ) ->Option <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
rust/kernel/list.rs pub fn new() -> impl PinInit<Self> { · line 330
Quoted 10 lines
rust/kernel/list.rs +10
-0+// 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; + }
How bad do you reckon is this for performance?
---
Cheers,
Benno
Quoted 8 lines
rust/kernel/list.rs +8
-0+ +// 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 + } + }
Alice Ryhl
reviewerRe: [PATCH v3 06/10] rust: list: add List
Quoted 11 lines · Benno Lossin
rust/kernel/list.rs pub fn new() -> impl PinInit<Self> { · line 203
Quoted 8 lines · Alice Ryhl
rust/kernel/list.rs +8
-0+/// Add the provided item to the back of the list. +pub fn push_back (&mut self, item:ListArc <T ,ID >) { +let raw_item =ListArc ::into_raw (item); +// SAFETY: +// * We just got `raw_item` from a `ListArc`, so it's in an `Arc`. +// * If this requirement is violated, then the previous caller of `prepare_to_insert` +// violated the safety requirement that they can't give up ownership of the `ListArc` +// until they call `post_remove`.
Quoted 3 lines
I don't like this negative phrasing, what about "Since we have ownership of the
ListArc,post_removemust have been called after each previous call toprepare_to_insert."?
I think we just need to argue about the most recent call to prepare_to_insert but ok.
Quoted 30 lines
Quoted 19 lines
rust/kernel/list.rs +19
-0+// * We own the `ListArc`. +// * Removing items from this list is always done using `remove_internal_inner`, which +// calls `post_remove` before giving up ownership. +let list_links =unsafe {T ::prepare_to_insert (raw_item) }; +// SAFETY: We have not yet called `post_remove`, so `list_links` is still valid. +let item =unsafe {ListLinks ::fields (list_links) }; + +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: By the type invariant, this pointer is valid or null. We just checked that +// it's not null, so it must be valid. rust/kernel/list.rs pub fn new() -> impl PinInit<Self> { · line 232
Quoted 10 lines
rust/kernel/list.rs +10
-0+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; + }
Quoted 1 line
You have this pattern several times, maybe make a function for this?
It's just two times. I think it's fine.
Quoted 13 lines
rust/kernel/list.rs pub fn new() -> impl PinInit<Self> { · line 330
Quoted 12 lines
rust/kernel/list.rs +12
-0+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; + }
Quoted 1 line
How bad do you reckon is this for performance?
I don't think it's a problem at all.
Alice
Re: [PATCH v3 06/10] rust: list: add List
Quoted 12 lines · Alice Ryhl
Quoted 11 lines · Benno Lossin
Quoted 8 lines · Alice Ryhl
rust/kernel/list.rs +8
-0+/// Add the provided item to the back of the list. +pub fn push_back (&mut self, item:ListArc <T ,ID >) { +let raw_item =ListArc ::into_raw (item); +// SAFETY: +// * We just got `raw_item` from a `ListArc`, so it's in an `Arc`. +// * If this requirement is violated, then the previous caller of `prepare_to_insert` +// violated the safety requirement that they can't give up ownership of the `ListArc` +// until they call `post_remove`.
Quoted 6 lines
Quoted 3 lines
I don't like this negative phrasing, what about "Since we have ownership of the
ListArc,post_removemust have been called after each previous call toprepare_to_insert."?I think we just need to argue about the most recent call to
prepare_to_insertbut ok.
I would argue that's exactly what my version does. Maybe "Since we have ownership of the ListArc, the most recent call to prepare_to_insert must have had a matching post_remove call afterwards."
But I liked the above version more.
Quoted 30 lines
Quoted 30 lines
Quoted 29 lines
rust/kernel/list.rs +29
-0+// * We own the `ListArc`. +// * Removing items from this list is always done using `remove_internal_inner`, which +// calls `post_remove` before giving up ownership. +let list_links =unsafe {T ::prepare_to_insert (raw_item) }; +// SAFETY: We have not yet called `post_remove`, so `list_links` is still valid. +let item =unsafe {ListLinks ::fields (list_links) }; + +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: 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; + }
Quoted 3 lines
Quoted 1 line
You have this pattern several times, maybe make a function for this?
It's just two times. I think it's fine.
Sure, it seemed more in my mind.
Quoted 13 lines
Quoted 13 lines
Quoted 12 lines
rust/kernel/list.rs +12
-0+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; + }
Quoted 3 lines
Quoted 1 line
How bad do you reckon is this for performance?
I don't think it's a problem at all.
Sounds good.
---
Cheers,
Benno
Alice Ryhl
reviewerPATCH v3 7/10 rust: list: add iterators
In reply to Alice RyhlRust Binder has lists containing stuff such as all contexts or all processes, and sometimes needs to iterate over them. This patch enables Rust Binder to do that using a normal for loop.
The iterator returns the ArcBorrow type, so it is possible to grab a refcount to values while iterating.
--- rust/kernel/list.rs | 102 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 102 insertions(+)
rust/kernel/list.rs +102 -0
@@ -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;
@@ -436,6 +438,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 >Default for List <T ,ID > {
@@ -451,3 +464,92 @@ fn drop(&mut self) { } } } + +/// An iterator over a [`List`]. +/// +/// # Invariants +/// +/// * There must be a [`List`] that is immutably borrowed for the duration of `'a`. +/// * The `current` pointer is null or points at a value in that [`List`]. +/// * The `stop` pointer is equal to the `first` field of that [`List`]. +#[derive( Clone )] +pub struct Iter <'a,T : ?Sized +ListItem <ID >,const ID :u64 =0 > { + current: *mut ListLinksFields , + stop: *mut ListLinksFields , + _ty:PhantomData <&'aListArc <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 at a value in the list. +let item =unsafe {T ::view_value (ListLinks ::from_fields (current)) }; +// SAFETY: +// * All values in a list are stored in an `Arc`. +// * The value cannot be removed from the list for the duration of the lifetime annotated +// on the returned `ArcBorrow`, because removing it from the list would require mutable +// access to the list. However, the `ArcBorrow` is annotated with the iterator's +// lifetime, and the list is immutably borrowed for that lifetime. +// * Values in a list never have a `UniqueArc` reference. +Some (unsafe {ArcBorrow ::from_raw (item) }) + } +} + +impl <'a,T : ?Sized +ListItem <ID >,const ID :u64 >FusedIterator for Iter <'a,T ,ID > {} + +impl <'a,T : ?Sized +ListItem <ID >,const ID :u64 >IntoIterator for &'aList <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 } + } +}
Signature · 1 line
2.45.2.1089.g2a221341d9-goog
Alice Ryhl
reviewerPATCH v3 8/10 rust: list: add cursor
In reply to Alice RyhlThe 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.
--- rust/kernel/list.rs | 82 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 82 insertions(+)
rust/kernel/list.rs +82 -0
@@ -439,6 +439,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
@@ -513,6 +527,74 @@ 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: &'amut 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 a mutable 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, because the list has a `ListArc` +// reference, and `UniqueArc` references must be unique. +unsafe {ArcBorrow ::from_raw (me) } + } + +/// Move the cursor to the next element. +pub fn next (self) ->Option <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 { +// INVARIANT: Since `self.current` is in the `list`, its `next` pointer is also in the +// `list`. +Some (Cursor { + current: next, + list: self.list, + }) + } + } + +/// Move the cursor to the previous element. +pub fn prev (self) ->Option <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 { +// INVARIANT: Since `self.current` is in the `list`, its `prev` pointer is also in the +// `list`. +Some (Cursor { + current: prev, + list: self.list, + }) + } + } + +/// Remove the current element from the list. +pub fn remove (self) ->ListArc <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 &'aList <T ,ID > {
Signature · 1 line
2.45.2.1089.g2a221341d9-goog
Alice Ryhl
reviewerPATCH v3 9/10 rust: list: support heterogeneous lists
In reply to Alice RyhlSupport linked lists that can hold many different structs at once. This is generally done using trait objects. The main challenge is figuring what the struct is given only a pointer to the ListLinks.
We do this by storing a pointer to the struct next to the ListLinks field. The container_of operation will then just read that pointer. When the type is a trait object, that pointer will be a fat pointer whose metadata is a vtable that tells you what kind of struct it is.
Heterogeneous lists are heavily used by Rust Binder. There are a lot of so-called todo lists containing various events that need to be delivered to userspace next time userspace calls into the driver. And there are quite a few different todo item types: incoming transaction, changes to refcounts, death notifications, and more.
--- rust/kernel/list.rs | 47 +++++++++++- rust/kernel/list/impl_list_item_mod.rs | 129 +++++++++++++++++++++++++++++++++ 2 files changed, 175 insertions(+), 1 deletion(-)
rust/kernel/list.rs +46 -1
@@ -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::{
@@ -181,6 +185,47 @@ 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 >>, +} + +// SAFETY: The fields of a ListLinksSelfPtr can be moved across thread boundaries. +unsafe impl <T : ?Sized +Send ,const ID :u64 >Send for ListLinksSelfPtr <T ,ID > {} +// SAFETY: The type is opaque so immutable references to a ListLinksSelfPtr are useless. Therefore, +// it's okay to have immutable access to a ListLinks from several threads at once. +// +// Note that `inner` being a public field does not prevent this type from being opaque, since +// `inner` is a opaque type. +unsafe impl <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 {
rust/kernel/list/impl_list_item_mod.rs +129 -0
140 lines not on this page · raw message
Signature · 1 line
2.45.2.1089.g2a221341d9-goog
Re: [PATCH v3 09/10] rust: list: support heterogeneous lists
Quoted 4 lines · Alice Ryhl
rust/kernel/list.rs +0
-0@@ -181,6 +185,47 @@ unsafe fn from_fields(me: *mut ListLinksFields) -> *mut Self { } }
rust/kernel/list.rs unsafe fn from_fields(me: *mut ListLinksFields) -> *mut Self { · line 197
Quoted 10 lines
rust/kernel/list.rs +10
-0+/// 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 >>,
Why do you need MaybeUninit?
Quoted 10 lines
rust/kernel/list.rs +10
-0+} + +// SAFETY: The fields of a ListLinksSelfPtr can be moved across thread boundaries. +unsafe impl <T : ?Sized +Send ,const ID :u64 >Send for ListLinksSelfPtr <T ,ID > {} +// SAFETY: The type is opaque so immutable references to a ListLinksSelfPtr are useless. Therefore, +// it's okay to have immutable access to a ListLinks from several threads at once. +// +// Note that `inner` being a public field does not prevent this type from being opaque, since +// `inner` is a opaque type. +unsafe impl <T : ?Sized +Sync ,const ID :u64 >Sync for ListLinksSelfPtr <T ,ID > {}
[...]
Quoted 19 lines
rust/kernel/list/impl_list_item_mod.rs +15
-0@@ -135,5 +178,91 @@ unsafe fn post_remove(me: *mut $crate::list::ListLinks<$num>) -> *const Self { } } }; + + ( + impl$({$($generics:tt)*})? ListItem<$num:tt> for $t:ty { + using ListLinksSelfPtr; + } $($rest:tt)* + ) => { + // SAFETY: See GUARANTEES comment on each method. + unsafe impl$(<$($generics)*>)? $crate::list::ListItem<$num> for $t { + // GUARANTEES: + // This implementation of `ListItem` will not give out exclusive access to the same + // `ListLinks` several times because calls to `prepare_to_insert` and `post_remove` + // must alternate and exclusive access is given up when `post_remove` is called. + // + // Other invocations of `impl_list_item!` also cannot give out exclusive access to the + // same `ListLinks` because you can only implement `ListItem` once for each value of
rust/kernel/list/impl_list_item_mod.rs unsafe fn post_remove(me: *mut $crate::list::ListLinks<$num>) -> *const Self { · line 205
Quoted 10 lines
rust/kernel/list/impl_list_item_mod.rs +10
-0+// `ID`, and the `ListLinks` fields only work with the specified `ID`. +unsafe fn prepare_to_insert (me: *const Self ) -> *mut $crate::list::ListLinks <$num> { +// SAFETY: The caller promises that `me` points at a valid value of type `Self`. +let links_field =unsafe { <Self as $crate::list::ListItem <$num>>::view_links (me) }; + +let spoff = $crate::list::ListLinksSelfPtr ::<Self , $num>::LIST_LINKS_SELF_PTR_OFFSET ; +// SAFETY: The constant is equal to `offset_of!(ListLinksSelfPtr, self_ptr)`, so +// the pointer stays in bounds of the allocation. +let self_ptr =unsafe { (links_fieldas *const u8 ).add (spoff) } +as *const ::core::cell::UnsafeCell <*const Self >;
A bit confused why you need to do it this way, can't you just do this?:
let links_self_field = links_field.cast::<$crate::list::ListLinksSelfPtr>();
// SAFETY: ...
let self_ptr = unsafe { ::core::ptr::addr_of_mut!((*links_self_field).self_ptr) };Quoted 15 lines
rust/kernel/list/impl_list_item_mod.rs +15
-0+let cell_inner = ::core::cell::UnsafeCell ::raw_get (self_ptr); + +// SAFETY: This value is not accessed in any other places than `prepare_to_insert`, +// `post_remove`, or `view_value`. By the safety requirements of those methods, +// none of these three methods may be called in parallel with this call to +// `prepare_to_insert`, so this write will not race with any other access to the +// value. +unsafe { ::core::ptr::write (cell_inner, me) }; + + links_field + } + +// GUARANTEES: +// * This returns the same pointer as `prepare_to_insert` because `prepare_to_insert` +// returns the return value of `view_links`.
rust/kernel/list/impl_list_item_mod.rs unsafe fn post_remove(me: *mut $crate::list::ListLinks<$num>) -> *const Self { · line 230
Quoted 10 lines
rust/kernel/list/impl_list_item_mod.rs +10
-0+// * By the type invariants of `ListLinks`, the `ListLinks` has two null pointers when +// this value is not in a list. +unsafe fn view_links (me: *const Self ) -> *mut $crate::list::ListLinks <$num> { +// SAFETY: The caller promises that `me` points at a valid value of type `Self`. +unsafe { <Self as HasListLinks <$num>>::raw_get_list_links (me.cast_mut ()) } + } + +// This function is also used as the implementation of `post_remove`, so the caller +// may choose to satisfy the safety requirements of `post_remove` instead of the safety +// requirements for `view_value`.
This almost sounds like a magic card :)
Review unsafe fn post_remove(me: *mut $crate::list::ListLinks<$num>) -> *const Self { · line 232
Quoted 2 lines
(quoted diff) +2
-0+ // + // GUARANTEES:
Can you also put in "()" here that this satisfies the guarantees of post_remove?
Quoted 20 lines
rust/kernel/list/impl_list_item_mod.rs +20
-0+// * This returns the same pointer as the one passed to the most recent call to +// `prepare_to_insert` since that call wrote that pointer to this location. The value +// is only modified in `prepare_to_insert`, so it has not been modified since the +// most recent call. +// +// GUARANTEES: (when using the `view_value` safety requirements) +// * The pointer remains valid until the next call to `post_remove` because the caller +// of the most recent call to `prepare_to_insert` promised to retain ownership of the +// `ListArc` containing `Self` until the next call to `post_remove`. The value cannot +// be destroyed while a `ListArc` reference exists. +unsafe fn view_value (links_field: *mut $crate::list::ListLinks <$num>) -> *const Self { +let spoff = $crate::list::ListLinksSelfPtr ::<Self , $num>::LIST_LINKS_SELF_PTR_OFFSET ; +// SAFETY: The constant is equal to `offset_of!(ListLinksSelfPtr, self_ptr)`, so +// the pointer stays in bounds of the allocation. +let self_ptr =unsafe { (links_fieldas *const u8 ).add (spoff) } +as *const ::core::cell::UnsafeCell <*const Self >; +let cell_inner = ::core::cell::UnsafeCell ::raw_get (self_ptr); +// SAFETY: This is not a data race, because the only function that writes to this +// value is `prepare_to_insert`, but by the safety requirements the +// `prepare_to_insert` method may not be called in parallel with `view_value` or
rust/kernel/list/impl_list_item_mod.rs unsafe fn post_remove(me: *mut $crate::list::ListLinks<$num>) -> *const Self { · line 262
Quoted 10 lines
rust/kernel/list/impl_list_item_mod.rs +10
-0+// `post_remove`. +unsafe { ::core::ptr::read (cell_inner) } + } + +// GUARANTEES: +// The first guarantee of `view_value` is exactly what `post_remove` guarantees. +unsafe fn post_remove (me: *mut $crate::list::ListLinks <$num>) -> *const Self { +// SAFETY: This specific implementation of `view_value` allows the caller to +// promise the safety requirements of `post_remove` instead of the safety +// requirements for `view_value`.
I like this solution better than what you have for impl_list_item "using ListLinks;"
---
Cheers,
Benno
Quoted 10 lines
rust/kernel/list/impl_list_item_mod.rs +4
-1+unsafe { <Self as $crate::list::ListItem <$num>>::view_value (me) } + } + } + }; }pub use impl_list_item; --2.45.2.1089.g2a221341d9-goog
Alice Ryhl
reviewerRe: [PATCH v3 09/10] rust: list: support heterogeneous lists
Quoted 6 lines · Benno Lossin
Quoted 4 lines · Alice Ryhl
(quoted diff) +0
-0@@ -181,6 +185,47 @@ unsafe fn from_fields(me: *mut ListLinksFields) -> *mut Self { } }
Quoted 12 lines
rust/kernel/list.rs unsafe fn from_fields(me: *mut ListLinksFields) -> *mut Self { · line 197
Quoted 10 lines
rust/kernel/list.rs +10
-0+/// 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 >>,Why do you need
MaybeUninit?
Right now the constructor initializes it to MaybeUninit::zeroed(). What would you initialize it to without MaybeUninit? Remember that the vtable pointer in a fat pointer has strict validity requirements.
Quoted 45 lines
Quoted 10 lines
rust/kernel/list.rs +10
-0+} + +// SAFETY: The fields of a ListLinksSelfPtr can be moved across thread boundaries. +unsafe impl <T : ?Sized +Send ,const ID :u64 >Send for ListLinksSelfPtr <T ,ID > {} +// SAFETY: The type is opaque so immutable references to a ListLinksSelfPtr are useless. Therefore, +// it's okay to have immutable access to a ListLinks from several threads at once. +// +// Note that `inner` being a public field does not prevent this type from being opaque, since +// `inner` is a opaque type. +unsafe impl <T : ?Sized +Sync ,const ID :u64 >Sync for ListLinksSelfPtr <T ,ID > {}[...]
Quoted 19 lines
rust/kernel/list/impl_list_item_mod.rs +15
-0@@ -135,5 +178,91 @@ unsafe fn post_remove(me: *mut $crate::list::ListLinks<$num>) -> *const Self { } } }; + + ( + impl$({$($generics:tt)*})? ListItem<$num:tt> for $t:ty { + using ListLinksSelfPtr; + } $($rest:tt)* + ) => { + // SAFETY: See GUARANTEES comment on each method. + unsafe impl$(<$($generics)*>)? $crate::list::ListItem<$num> for $t { + // GUARANTEES: + // This implementation of `ListItem` will not give out exclusive access to the same + // `ListLinks` several times because calls to `prepare_to_insert` and `post_remove` + // must alternate and exclusive access is given up when `post_remove` is called. + // + // Other invocations of `impl_list_item!` also cannot give out exclusive access to the + // same `ListLinks` because you can only implement `ListItem` once for each value ofrust/kernel/list/impl_list_item_mod.rs unsafe fn post_remove(me: *mut $crate::list::ListLinks<$num>) -> *const Self { · line 205
Quoted 10 lines
rust/kernel/list/impl_list_item_mod.rs +10
-0+// `ID`, and the `ListLinks` fields only work with the specified `ID`. +unsafe fn prepare_to_insert (me: *const Self ) -> *mut $crate::list::ListLinks <$num> { +// SAFETY: The caller promises that `me` points at a valid value of type `Self`. +let links_field =unsafe { <Self as $crate::list::ListItem <$num>>::view_links (me) }; + +let spoff = $crate::list::ListLinksSelfPtr ::<Self , $num>::LIST_LINKS_SELF_PTR_OFFSET ; +// SAFETY: The constant is equal to `offset_of!(ListLinksSelfPtr, self_ptr)`, so +// the pointer stays in bounds of the allocation. +let self_ptr =unsafe { (links_fieldas *const u8 ).add (spoff) } +as *const ::core::cell::UnsafeCell <*const Self >;A bit confused why you need to do it this way, can't you just do this?:
Quoted 3 lines
let links_self_field = links_field.cast::<$crate::list::ListLinksSelfPtr>();
// SAFETY: ...
let self_ptr = unsafe { ::core::ptr::addr_of_mut!((*links_self_field).self_ptr) };If nothing else, the field is not public. I can't remember if there was another reason.
Alice
Re: [PATCH v3 09/10] rust: list: support heterogeneous lists
Quoted 20 lines · Alice Ryhl
Quoted 6 lines · Benno Lossin
Quoted 4 lines · Alice Ryhl
(quoted diff) +0
-0@@ -181,6 +185,47 @@ unsafe fn from_fields(me: *mut ListLinksFields) -> *mut Self { } }Quoted 12 lines
rust/kernel/list.rs unsafe fn from_fields(me: *mut ListLinksFields) -> *mut Self { · line 197
Quoted 10 lines
rust/kernel/list.rs +10
-0+/// 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 >>,Why do you need
MaybeUninit?
Quoted 3 lines
Right now the constructor initializes it to
MaybeUninit::zeroed(). What would you initialize it to without MaybeUninit? Remember that the vtable pointer in a fat pointer has strict validity requirements.
Oh... I forgot about that, can you add a comment about that? Also why not use Opaque in that case then?
Quoted 45 lines
Quoted 45 lines
Quoted 10 lines
rust/kernel/list.rs +10
-0+} + +// SAFETY: The fields of a ListLinksSelfPtr can be moved across thread boundaries. +unsafe impl <T : ?Sized +Send ,const ID :u64 >Send for ListLinksSelfPtr <T ,ID > {} +// SAFETY: The type is opaque so immutable references to a ListLinksSelfPtr are useless. Therefore, +// it's okay to have immutable access to a ListLinks from several threads at once. +// +// Note that `inner` being a public field does not prevent this type from being opaque, since +// `inner` is a opaque type. +unsafe impl <T : ?Sized +Sync ,const ID :u64 >Sync for ListLinksSelfPtr <T ,ID > {}[...]
Quoted 19 lines
rust/kernel/list/impl_list_item_mod.rs +15
-0@@ -135,5 +178,91 @@ unsafe fn post_remove(me: *mut $crate::list::ListLinks<$num>) -> *const Self { } } }; + + ( + impl$({$($generics:tt)*})? ListItem<$num:tt> for $t:ty { + using ListLinksSelfPtr; + } $($rest:tt)* + ) => { + // SAFETY: See GUARANTEES comment on each method. + unsafe impl$(<$($generics)*>)? $crate::list::ListItem<$num> for $t { + // GUARANTEES: + // This implementation of `ListItem` will not give out exclusive access to the same + // `ListLinks` several times because calls to `prepare_to_insert` and `post_remove` + // must alternate and exclusive access is given up when `post_remove` is called. + // + // Other invocations of `impl_list_item!` also cannot give out exclusive access to the + // same `ListLinks` because you can only implement `ListItem` once for each value ofrust/kernel/list/impl_list_item_mod.rs unsafe fn post_remove(me: *mut $crate::list::ListLinks<$num>) -> *const Self { · line 205
Quoted 10 lines
rust/kernel/list/impl_list_item_mod.rs +10
-0+// `ID`, and the `ListLinks` fields only work with the specified `ID`. +unsafe fn prepare_to_insert (me: *const Self ) -> *mut $crate::list::ListLinks <$num> { +// SAFETY: The caller promises that `me` points at a valid value of type `Self`. +let links_field =unsafe { <Self as $crate::list::ListItem <$num>>::view_links (me) }; + +let spoff = $crate::list::ListLinksSelfPtr ::<Self , $num>::LIST_LINKS_SELF_PTR_OFFSET ; +// SAFETY: The constant is equal to `offset_of!(ListLinksSelfPtr, self_ptr)`, so +// the pointer stays in bounds of the allocation. +let self_ptr =unsafe { (links_fieldas *const u8 ).add (spoff) } +as *const ::core::cell::UnsafeCell <*const Self >;A bit confused why you need to do it this way, can't you just do this?:
Quoted 6 lines
Quoted 3 lines
let links_self_field = links_field.cast::<$crate::list::ListLinksSelfPtr>(); // SAFETY: ... let self_ptr = unsafe { ::core::ptr::addr_of_mut!((*links_self_field).self_ptr) };If nothing else, the field is not public. I can't remember if there was another reason.
Oh yeah that's true, then you have to go via the offset.
---
Cheers,
Benno
Alice Ryhl
reviewerRe: [PATCH v3 09/10] rust: list: support heterogeneous lists
Quoted 22 lines · Benno Lossin
Quoted 20 lines · Alice Ryhl
Quoted 18 lines · Benno Lossin
Quoted 4 lines · Alice Ryhl
rust/kernel/list.rs +0
-0@@ -181,6 +185,47 @@ unsafe fn from_fields(me: *mut ListLinksFields) -> *mut Self { } }rust/kernel/list.rs unsafe fn from_fields(me: *mut ListLinksFields) -> *mut Self { · line 197
Quoted 10 lines
rust/kernel/list.rs +10
-0+/// 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 >>,Why do you need
MaybeUninit?
Quoted 6 lines
Quoted 3 lines
Right now the constructor initializes it to
MaybeUninit::zeroed(). What would you initialize it to without MaybeUninit? Remember that the vtable pointer in a fat pointer has strict validity requirements.Oh... I forgot about that, can you add a comment about that? Also why not use
Opaquein that case then?
It used to just be UnsafeCell, but then I tried it in miri and found out about the issue and added MaybeUninit. But I can make it use Opaque instead.
Alice
Alice Ryhl
reviewerPATCH v3 10/10 rust: list: add ListArcField
In reply to Alice RyhlOne 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.
--- rust/kernel/list.rs | 3 ++ rust/kernel/list/arc_field.rs | 96 +++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 99 insertions(+)
rust/kernel/list.rs +3 -0
@@ -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
rust/kernel/list/arc_field.rs new file +96 -0
96 lines not on this page · raw message
Signature · 1 line
2.45.2.1089.g2a221341d9-goog