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

[Benno Lossin <benno.lossin@proton.me>]

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
>