| lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
|
Open Source and information security mailing list archives
| ||
|
Message-ID: <20240402-linked-list-v1-8-b1c59ba7ae3b@google.com>
Date: Tue, 02 Apr 2024 12:17:05 +0000
From: Alice Ryhl <aliceryhl@...gle.com>
To: Miguel Ojeda <ojeda@...nel.org>, Andrew Morton <akpm@...ux-foundation.org>
Cc: Alex Gaynor <alex.gaynor@...il.com>, Wedson Almeida Filho <wedsonaf@...il.com>,
Boqun Feng <boqun.feng@...il.com>, Gary Guo <gary@...yguo.net>,
"Björn Roy Baron" <bjorn3_gh@...tonmail.com>, Benno Lossin <benno.lossin@...ton.me>,
Andreas Hindborg <a.hindborg@...sung.com>, Marco Elver <elver@...gle.com>,
Kees Cook <keescook@...omium.org>, Coly Li <colyli@...e.de>, Paolo Abeni <pabeni@...hat.com>,
Pierre Gondois <pierre.gondois@....com>, Ingo Molnar <mingo@...nel.org>,
Jakub Kicinski <kuba@...nel.org>, Wei Yang <richard.weiyang@...il.com>,
Matthew Wilcox <willy@...radead.org>, linux-kernel@...r.kernel.org,
rust-for-linux@...r.kernel.org, Alice Ryhl <aliceryhl@...gle.com>
Subject: [PATCH 8/9] rust: list: support heterogeneous lists
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@...gle.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
Powered by blists - more mailing lists