Messages in this thread Patch in this message | | | Date | Tue, 02 Apr 2024 12:17:05 +0000 | Subject | [PATCH 8/9] rust: list: support heterogeneous lists | From | Alice Ryhl <> |
| |
Support linked lists that can have many different structs at once. This is generally done using trait objects. The main challenge is figuring what the struct is given only a pointer to the ListLinks.
We do this by storing a pointer to the struct next to the ListLinks field. The container_of operation will then just read that pointer. When the type is a trait object, that pointer will be a fat pointer whose metadata is a vtable that tells you what kind of struct it is.
Heterogeneous lists are heavily used by Rust Binder. There are a lot of so-called todo lists containing various events that need to be delivered to userspace next time userspace calls into the driver. And there are quite a few different todo item types: incoming transaction, changes to refcounts, death notifications, and more.
Signed-off-by: Alice Ryhl <aliceryhl@google.com> --- rust/kernel/list.rs | 41 ++++++++++++++++- rust/kernel/list/impl_list_item_mod.rs | 83 ++++++++++++++++++++++++++++++++++ 2 files changed, 123 insertions(+), 1 deletion(-)
diff --git a/rust/kernel/list.rs b/rust/kernel/list.rs index 47e52818c7bd..68d03b100863 100644 --- a/rust/kernel/list.rs +++ b/rust/kernel/list.rs @@ -7,12 +7,16 @@ use crate::init::PinInit; use crate::sync::ArcBorrow; use crate::types::Opaque; +use core::cell::UnsafeCell; use core::iter::{DoubleEndedIterator, FusedIterator}; use core::marker::PhantomData; +use core::mem::MaybeUninit; use core::ptr; mod impl_list_item_mod; -pub use self::impl_list_item_mod::{impl_has_list_links, impl_list_item, HasListLinks}; +pub use self::impl_list_item_mod::{ + impl_has_list_links, impl_has_list_links_self_ptr, impl_list_item, HasListLinks, HasSelfPtr, +}; mod arc; pub use self::arc::{ @@ -180,6 +184,41 @@ unsafe fn from_fields(me: *mut ListLinksFields) -> *mut Self { } } +/// Similar to [`ListLinks`], but also contains a pointer to the full value. +/// +/// This type can be used instead of [`ListLinks`] to support lists with trait objects. +#[repr(C)] +pub struct ListLinksSelfPtr<T: ?Sized, const ID: u64 = 0> { + /// The `ListLinks` field inside this value. + /// + /// This is public so that it can be used with `impl_has_list_links!`. + pub inner: ListLinks<ID>, + self_ptr: UnsafeCell<MaybeUninit<*const T>>, +} + +unsafe impl<T: ?Sized + Send, const ID: u64> Send for ListLinksSelfPtr<T, ID> {} +unsafe impl<T: ?Sized + Sync, const ID: u64> Sync for ListLinksSelfPtr<T, ID> {} + +impl<T: ?Sized, const ID: u64> ListLinksSelfPtr<T, ID> { + /// The offset from the [`ListLinks`] to the self pointer field. + pub const LIST_LINKS_SELF_PTR_OFFSET: usize = core::mem::offset_of!(Self, self_ptr); + + /// Creates a new initializer for this type. + pub fn new() -> impl PinInit<Self> { + // INVARIANT: Pin-init initializers can't be used on an existing `Arc`, so this value will + // not be constructed in an `Arc` that already has a `ListArc`. + Self { + inner: ListLinks { + inner: Opaque::new(ListLinksFields { + prev: ptr::null_mut(), + next: ptr::null_mut(), + }), + }, + self_ptr: UnsafeCell::new(MaybeUninit::zeroed()), + } + } +} + impl<T: ?Sized + ListItem<ID>, const ID: u64> List<T, ID> { /// Creates a new empty list. pub const fn new() -> Self { diff --git a/rust/kernel/list/impl_list_item_mod.rs b/rust/kernel/list/impl_list_item_mod.rs index 9e2f6d6d4786..6884d8a3e710 100644 --- a/rust/kernel/list/impl_list_item_mod.rs +++ b/rust/kernel/list/impl_list_item_mod.rs @@ -61,6 +61,49 @@ unsafe fn raw_get_list_links(ptr: *mut Self) -> *mut $crate::list::ListLinks$(<$ } pub use impl_has_list_links; +/// Declares that the `ListLinks<ID>` field in this struct is inside a `ListLinksSelfPtr<T, ID>`. +/// +/// # Safety +/// +/// The `ListLinks<ID>` field of this struct at the offset `HasListLinks<ID>::OFFSET` must be +/// inside a `ListLinksSelfPtr<T, ID>`. +pub unsafe trait HasSelfPtr<T: ?Sized, const ID: u64 = 0> +where + Self: HasListLinks<ID>, +{ +} + +/// Implements the [`HasListLinks`] and [`HasSelfPtr`] traits for the given type. +#[macro_export] +macro_rules! impl_has_list_links_self_ptr { + ($(impl$({$($implarg:tt)*})? + HasSelfPtr<$item_type:ty $(, $id:tt)?> + for $self:ident $(<$($selfarg:ty),*>)? + { self.$field:ident } + )*) => {$( + // SAFETY: The implementation of `raw_get_list_links` only compiles if the field has the + // right type. + unsafe impl$(<$($implarg)*>)? $crate::list::HasSelfPtr<$item_type $(, $id)?> for + $self $(<$($selfarg),*>)? + {} + + unsafe impl$(<$($implarg)*>)? $crate::list::HasListLinks$(<$id>)? for + $self $(<$($selfarg),*>)? + { + const OFFSET: usize = ::core::mem::offset_of!(Self, $field) as usize; + + #[inline] + unsafe fn raw_get_list_links(ptr: *mut Self) -> *mut $crate::list::ListLinks$(<$id>)? { + // SAFETY: The caller promises that the pointer is not dangling. + let ptr: *mut $crate::list::ListLinksSelfPtr<$item_type $(, $id)?> = + unsafe { ::core::ptr::addr_of_mut!((*ptr).$field) }; + ptr.cast() + } + } + )*}; +} +pub use impl_has_list_links_self_ptr; + /// Implements the [`ListItem`] trait for the given type. /// /// Assumes that the type implements [`HasListLinks`]. @@ -94,5 +137,45 @@ unsafe fn post_remove(me: *mut ListLinks<$num>) -> *const Self { } } }; + + ( + impl$({$($generics:tt)*})? ListItem<$num:tt> for $t:ty { + using ListLinksSelfPtr; + } $($rest:tt)* + ) => { + unsafe impl$(<$($generics)*>)? ListItem<$num> for $t { + unsafe fn prepare_to_insert(me: *const Self) -> *mut ListLinks<$num> { + let links_field = unsafe { Self::view_links(me) }; + + let spoff = ListLinksSelfPtr::<Self, $num>::LIST_LINKS_SELF_PTR_OFFSET; + let self_ptr = unsafe { (links_field as *const u8).add(spoff) + as *const ::core::cell::UnsafeCell<*const Self> }; + let cell_inner = ::core::cell::UnsafeCell::raw_get(self_ptr); + + unsafe { ::core::ptr::write(cell_inner, me) }; + links_field + } + + unsafe fn view_links(me: *const Self) -> *mut ListLinks<$num> { + unsafe { + <Self as HasListLinks<$num>>::raw_get_list_links(me.cast_mut()) + } + } + + unsafe fn view_value(links_field: *mut ListLinks<$num>) -> *const Self { + let spoff = ListLinksSelfPtr::<Self, $num>::LIST_LINKS_SELF_PTR_OFFSET; + let self_ptr = unsafe { (links_field as *const u8).add(spoff) + as *const ::core::cell::UnsafeCell<*const Self> }; + let cell_inner = ::core::cell::UnsafeCell::raw_get(self_ptr); + unsafe { + ::core::ptr::read(cell_inner) + } + } + + unsafe fn post_remove(me: *mut ListLinks<$num>) -> *const Self { + unsafe { Self::view_value(me) } + } + } + }; } pub use impl_list_item; -- 2.44.0.478.gd926399ef9-goog
| |