275 lines · rust
1// SPDX-License-Identifier: GPL-2.02 3// Copyright (C) 2024 Google LLC.4 5//! Helpers for implementing list traits safely.6 7use crate::list::ListLinks;8 9/// Declares that this type has a `ListLinks<ID>` field at a fixed offset.10///11/// This trait is only used to help implement `ListItem` safely. If `ListItem` is implemented12/// manually, then this trait is not needed. Use the [`impl_has_list_links!`] macro to implement13/// this trait.14///15/// # Safety16///17/// All values of this type must have a `ListLinks<ID>` field at the given offset.18///19/// The behavior of `raw_get_list_links` must not be changed.20pub unsafe trait HasListLinks<const ID: u64 = 0> {21 /// The offset of the `ListLinks` field.22 const OFFSET: usize;23 24 /// Returns a pointer to the [`ListLinks<T, ID>`] field.25 ///26 /// # Safety27 ///28 /// The provided pointer must point at a valid struct of type `Self`.29 ///30 /// [`ListLinks<T, ID>`]: ListLinks31 // We don't really need this method, but it's necessary for the implementation of32 // `impl_has_list_links!` to be correct.33 #[inline]34 unsafe fn raw_get_list_links(ptr: *mut Self) -> *mut ListLinks<ID> {35 // SAFETY: The caller promises that the pointer is valid. The implementer promises that the36 // `OFFSET` constant is correct.37 unsafe { (ptr as *mut u8).add(Self::OFFSET) as *mut ListLinks<ID> }38 }39}40 41/// Implements the [`HasListLinks`] trait for the given type.42#[macro_export]43macro_rules! impl_has_list_links {44 ($(impl$(<$($implarg:ident),*>)?45 HasListLinks$(<$id:tt>)?46 for $self:ident $(<$($selfarg:ty),*>)?47 { self$(.$field:ident)* }48 )*) => {$(49 // SAFETY: The implementation of `raw_get_list_links` only compiles if the field has the50 // right type.51 //52 // The behavior of `raw_get_list_links` is not changed since the `addr_of_mut!` macro is53 // equivalent to the pointer offset operation in the trait definition.54 unsafe impl$(<$($implarg),*>)? $crate::list::HasListLinks$(<$id>)? for55 $self $(<$($selfarg),*>)?56 {57 const OFFSET: usize = ::core::mem::offset_of!(Self, $($field).*) as usize;58 59 #[inline]60 unsafe fn raw_get_list_links(ptr: *mut Self) -> *mut $crate::list::ListLinks$(<$id>)? {61 // SAFETY: The caller promises that the pointer is not dangling. We know that this62 // expression doesn't follow any pointers, as the `offset_of!` invocation above63 // would otherwise not compile.64 unsafe { ::core::ptr::addr_of_mut!((*ptr)$(.$field)*) }65 }66 }67 )*};68}69pub use impl_has_list_links;70 71/// Declares that the `ListLinks<ID>` field in this struct is inside a `ListLinksSelfPtr<T, ID>`.72///73/// # Safety74///75/// The `ListLinks<ID>` field of this struct at the offset `HasListLinks<ID>::OFFSET` must be76/// inside a `ListLinksSelfPtr<T, ID>`.77pub unsafe trait HasSelfPtr<T: ?Sized, const ID: u64 = 0>78where79 Self: HasListLinks<ID>,80{81}82 83/// Implements the [`HasListLinks`] and [`HasSelfPtr`] traits for the given type.84#[macro_export]85macro_rules! impl_has_list_links_self_ptr {86 ($(impl$({$($implarg:tt)*})?87 HasSelfPtr<$item_type:ty $(, $id:tt)?>88 for $self:ident $(<$($selfarg:ty),*>)?89 { self.$field:ident }90 )*) => {$(91 // SAFETY: The implementation of `raw_get_list_links` only compiles if the field has the92 // right type.93 unsafe impl$(<$($implarg)*>)? $crate::list::HasSelfPtr<$item_type $(, $id)?> for94 $self $(<$($selfarg),*>)?95 {}96 97 unsafe impl$(<$($implarg)*>)? $crate::list::HasListLinks$(<$id>)? for98 $self $(<$($selfarg),*>)?99 {100 const OFFSET: usize = ::core::mem::offset_of!(Self, $field) as usize;101 102 #[inline]103 unsafe fn raw_get_list_links(ptr: *mut Self) -> *mut $crate::list::ListLinks$(<$id>)? {104 // SAFETY: The caller promises that the pointer is not dangling.105 let ptr: *mut $crate::list::ListLinksSelfPtr<$item_type $(, $id)?> =106 unsafe { ::core::ptr::addr_of_mut!((*ptr).$field) };107 ptr.cast()108 }109 }110 )*};111}112pub use impl_has_list_links_self_ptr;113 114/// Implements the [`ListItem`] trait for the given type.115///116/// Requires that the type implements [`HasListLinks`]. Use the [`impl_has_list_links!`] macro to117/// implement that trait.118///119/// [`ListItem`]: crate::list::ListItem120#[macro_export]121macro_rules! impl_list_item {122 (123 $(impl$({$($generics:tt)*})? ListItem<$num:tt> for $t:ty {124 using ListLinks;125 })*126 ) => {$(127 // SAFETY: See GUARANTEES comment on each method.128 unsafe impl$(<$($generics)*>)? $crate::list::ListItem<$num> for $t {129 // GUARANTEES:130 // * This returns the same pointer as `prepare_to_insert` because `prepare_to_insert`131 // is implemented in terms of `view_links`.132 // * By the type invariants of `ListLinks`, the `ListLinks` has two null pointers when133 // this value is not in a list.134 unsafe fn view_links(me: *const Self) -> *mut $crate::list::ListLinks<$num> {135 // SAFETY: The caller guarantees that `me` points at a valid value of type `Self`.136 unsafe {137 <Self as $crate::list::HasListLinks<$num>>::raw_get_list_links(me.cast_mut())138 }139 }140 141 // GUARANTEES:142 // * `me` originates from the most recent call to `prepare_to_insert`, which just added143 // `offset` to the pointer passed to `prepare_to_insert`. This method subtracts144 // `offset` from `me` so it returns the pointer originally passed to145 // `prepare_to_insert`.146 // * The pointer remains valid until the next call to `post_remove` because the caller147 // of the most recent call to `prepare_to_insert` promised to retain ownership of the148 // `ListArc` containing `Self` until the next call to `post_remove`. The value cannot149 // be destroyed while a `ListArc` reference exists.150 unsafe fn view_value(me: *mut $crate::list::ListLinks<$num>) -> *const Self {151 let offset = <Self as $crate::list::HasListLinks<$num>>::OFFSET;152 // SAFETY: `me` originates from the most recent call to `prepare_to_insert`, so it153 // points at the field at offset `offset` in a value of type `Self`. Thus,154 // subtracting `offset` from `me` is still in-bounds of the allocation.155 unsafe { (me as *const u8).sub(offset) as *const Self }156 }157 158 // GUARANTEES:159 // This implementation of `ListItem` will not give out exclusive access to the same160 // `ListLinks` several times because calls to `prepare_to_insert` and `post_remove`161 // must alternate and exclusive access is given up when `post_remove` is called.162 //163 // Other invocations of `impl_list_item!` also cannot give out exclusive access to the164 // same `ListLinks` because you can only implement `ListItem` once for each value of165 // `ID`, and the `ListLinks` fields only work with the specified `ID`.166 unsafe fn prepare_to_insert(me: *const Self) -> *mut $crate::list::ListLinks<$num> {167 // SAFETY: The caller promises that `me` points at a valid value.168 unsafe { <Self as $crate::list::ListItem<$num>>::view_links(me) }169 }170 171 // GUARANTEES:172 // * `me` originates from the most recent call to `prepare_to_insert`, which just added173 // `offset` to the pointer passed to `prepare_to_insert`. This method subtracts174 // `offset` from `me` so it returns the pointer originally passed to175 // `prepare_to_insert`.176 unsafe fn post_remove(me: *mut $crate::list::ListLinks<$num>) -> *const Self {177 let offset = <Self as $crate::list::HasListLinks<$num>>::OFFSET;178 // SAFETY: `me` originates from the most recent call to `prepare_to_insert`, so it179 // points at the field at offset `offset` in a value of type `Self`. Thus,180 // subtracting `offset` from `me` is still in-bounds of the allocation.181 unsafe { (me as *const u8).sub(offset) as *const Self }182 }183 }184 )*};185 186 (187 $(impl$({$($generics:tt)*})? ListItem<$num:tt> for $t:ty {188 using ListLinksSelfPtr;189 })*190 ) => {$(191 // SAFETY: See GUARANTEES comment on each method.192 unsafe impl$(<$($generics)*>)? $crate::list::ListItem<$num> for $t {193 // GUARANTEES:194 // This implementation of `ListItem` will not give out exclusive access to the same195 // `ListLinks` several times because calls to `prepare_to_insert` and `post_remove`196 // must alternate and exclusive access is given up when `post_remove` is called.197 //198 // Other invocations of `impl_list_item!` also cannot give out exclusive access to the199 // same `ListLinks` because you can only implement `ListItem` once for each value of200 // `ID`, and the `ListLinks` fields only work with the specified `ID`.201 unsafe fn prepare_to_insert(me: *const Self) -> *mut $crate::list::ListLinks<$num> {202 // SAFETY: The caller promises that `me` points at a valid value of type `Self`.203 let links_field = unsafe { <Self as $crate::list::ListItem<$num>>::view_links(me) };204 205 let spoff = $crate::list::ListLinksSelfPtr::<Self, $num>::LIST_LINKS_SELF_PTR_OFFSET;206 // Goes via the offset as the field is private.207 //208 // SAFETY: The constant is equal to `offset_of!(ListLinksSelfPtr, self_ptr)`, so209 // the pointer stays in bounds of the allocation.210 let self_ptr = unsafe { (links_field as *const u8).add(spoff) }211 as *const $crate::types::Opaque<*const Self>;212 let cell_inner = $crate::types::Opaque::raw_get(self_ptr);213 214 // SAFETY: This value is not accessed in any other places than `prepare_to_insert`,215 // `post_remove`, or `view_value`. By the safety requirements of those methods,216 // none of these three methods may be called in parallel with this call to217 // `prepare_to_insert`, so this write will not race with any other access to the218 // value.219 unsafe { ::core::ptr::write(cell_inner, me) };220 221 links_field222 }223 224 // GUARANTEES:225 // * This returns the same pointer as `prepare_to_insert` because `prepare_to_insert`226 // returns the return value of `view_links`.227 // * By the type invariants of `ListLinks`, the `ListLinks` has two null pointers when228 // this value is not in a list.229 unsafe fn view_links(me: *const Self) -> *mut $crate::list::ListLinks<$num> {230 // SAFETY: The caller promises that `me` points at a valid value of type `Self`.231 unsafe { <Self as HasListLinks<$num>>::raw_get_list_links(me.cast_mut()) }232 }233 234 // This function is also used as the implementation of `post_remove`, so the caller235 // may choose to satisfy the safety requirements of `post_remove` instead of the safety236 // requirements for `view_value`.237 //238 // GUARANTEES: (always)239 // * This returns the same pointer as the one passed to the most recent call to240 // `prepare_to_insert` since that call wrote that pointer to this location. The value241 // is only modified in `prepare_to_insert`, so it has not been modified since the242 // most recent call.243 //244 // GUARANTEES: (only when using the `view_value` safety requirements)245 // * The pointer remains valid until the next call to `post_remove` because the caller246 // of the most recent call to `prepare_to_insert` promised to retain ownership of the247 // `ListArc` containing `Self` until the next call to `post_remove`. The value cannot248 // be destroyed while a `ListArc` reference exists.249 unsafe fn view_value(links_field: *mut $crate::list::ListLinks<$num>) -> *const Self {250 let spoff = $crate::list::ListLinksSelfPtr::<Self, $num>::LIST_LINKS_SELF_PTR_OFFSET;251 // SAFETY: The constant is equal to `offset_of!(ListLinksSelfPtr, self_ptr)`, so252 // the pointer stays in bounds of the allocation.253 let self_ptr = unsafe { (links_field as *const u8).add(spoff) }254 as *const ::core::cell::UnsafeCell<*const Self>;255 let cell_inner = ::core::cell::UnsafeCell::raw_get(self_ptr);256 // SAFETY: This is not a data race, because the only function that writes to this257 // value is `prepare_to_insert`, but by the safety requirements the258 // `prepare_to_insert` method may not be called in parallel with `view_value` or259 // `post_remove`.260 unsafe { ::core::ptr::read(cell_inner) }261 }262 263 // GUARANTEES:264 // The first guarantee of `view_value` is exactly what `post_remove` guarantees.265 unsafe fn post_remove(me: *mut $crate::list::ListLinks<$num>) -> *const Self {266 // SAFETY: This specific implementation of `view_value` allows the caller to267 // promise the safety requirements of `post_remove` instead of the safety268 // requirements for `view_value`.269 unsafe { <Self as $crate::list::ListItem<$num>>::view_value(me) }270 }271 }272 )*};273}274pub use impl_list_item;275