Re: [PATCH v3 09/10] rust: list: support heterogeneous lists

Benno Lossin
2024-08-01T09:24:49Z

On 23.07.24 10:22, Alice Ryhl wrote:
> @@ -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>>,

Why do you need `MaybeUninit`?

> +}
> +
> +// 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> {}

[...]

> @@ -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
> + // `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_field as *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) };

> + 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`.
> + // * 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 :)

> + //
> + // GUARANTEES:

Can you also put in "()" here that this satisfies the guarantees of
`post_remove`?

> + // * 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_field as *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
> + // `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

> + unsafe { <Self as $crate::list::ListItem<$num>>::view_value(me) }
> + }
> + }
> + };
> }
> pub use impl_list_item;
>
> --
> 2.45.2.1089.g2a221341d9-goog
>