1 // SPDX-License-Identifier: GPL-2.0 2 3 // Copyright (C) 2024 Google LLC. 4 5 //! Helpers for implementing list traits safely. 6 7 use 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 implemented 12 /// manually, then this trait is not needed. Use the [`impl_has_list_links!`] macro to implement 13 /// this trait. 14 /// 15 /// # Safety 16 /// 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. 20 pub 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 /// # Safety 27 /// 28 /// The provided pointer must point at a valid struct of type `Self`. 29 /// 30 /// [`ListLinks<T, ID>`]: ListLinks 31 // We don't really need this method, but it's necessary for the implementation of 32 // `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 the 36 // `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] 43 macro_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 the 50 // right type. 51 // 52 // The behavior of `raw_get_list_links` is not changed since the `addr_of_mut!` macro is 53 // equivalent to the pointer offset operation in the trait definition. 54 unsafe impl$(<$($implarg),*>)? $crate::list::HasListLinks$(<$id>)? for 55 $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 this 62 // expression doesn't follow any pointers, as the `offset_of!` invocation above 63 // would otherwise not compile. 64 unsafe { ::core::ptr::addr_of_mut!((*ptr)$(.$field)*) } 65 } 66 } 67 )*}; 68 } 69 pub use impl_has_list_links; 70 71 /// Declares that the `ListLinks<ID>` field in this struct is inside a `ListLinksSelfPtr<T, ID>`. 72 /// 73 /// # Safety 74 /// 75 /// The `ListLinks<ID>` field of this struct at the offset `HasListLinks<ID>::OFFSET` must be 76 /// inside a `ListLinksSelfPtr<T, ID>`. 77 pub unsafe trait HasSelfPtr<T: ?Sized, const ID: u64 = 0> 78 where 79 Self: HasListLinks<ID>, 80 { 81 } 82 83 /// Implements the [`HasListLinks`] and [`HasSelfPtr`] traits for the given type. 84 #[macro_export] 85 macro_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 the 92 // right type. 93 unsafe impl$(<$($implarg)*>)? $crate::list::HasSelfPtr<$item_type $(, $id)?> for 94 $self $(<$($selfarg),*>)? 95 {} 96 97 unsafe impl$(<$($implarg)*>)? $crate::list::HasListLinks$(<$id>)? for 98 $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 } 112 pub 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 to 117 /// implement that trait. 118 /// 119 /// [`ListItem`]: crate::list::ListItem 120 #[macro_export] 121 macro_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 when 133 // 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 added 143 // `offset` to the pointer passed to `prepare_to_insert`. This method subtracts 144 // `offset` from `me` so it returns the pointer originally passed to 145 // `prepare_to_insert`. 146 // * The pointer remains valid until the next call to `post_remove` because the caller 147 // of the most recent call to `prepare_to_insert` promised to retain ownership of the 148 // `ListArc` containing `Self` until the next call to `post_remove`. The value cannot 149 // 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 it 153 // 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 same 160 // `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 the 164 // same `ListLinks` because you can only implement `ListItem` once for each value of 165 // `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 added 173 // `offset` to the pointer passed to `prepare_to_insert`. This method subtracts 174 // `offset` from `me` so it returns the pointer originally passed to 175 // `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 it 179 // 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 same 195 // `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 the 199 // same `ListLinks` because you can only implement `ListItem` once for each value of 200 // `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)`, so 209 // 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 to 217 // `prepare_to_insert`, so this write will not race with any other access to the 218 // value. 219 unsafe { ::core::ptr::write(cell_inner, me) }; 220 221 links_field 222 } 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 when 228 // 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 caller 235 // may choose to satisfy the safety requirements of `post_remove` instead of the safety 236 // requirements for `view_value`. 237 // 238 // GUARANTEES: (always) 239 // * This returns the same pointer as the one passed to the most recent call to 240 // `prepare_to_insert` since that call wrote that pointer to this location. The value 241 // is only modified in `prepare_to_insert`, so it has not been modified since the 242 // 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 caller 246 // of the most recent call to `prepare_to_insert` promised to retain ownership of the 247 // `ListArc` containing `Self` until the next call to `post_remove`. The value cannot 248 // 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)`, so 252 // 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 this 257 // value is `prepare_to_insert`, but by the safety requirements the 258 // `prepare_to_insert` method may not be called in parallel with `view_value` or 259 // `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 to 267 // promise the safety requirements of `post_remove` instead of the safety 268 // requirements for `view_value`. 269 unsafe { <Self as $crate::list::ListItem<$num>>::view_value(me) } 270 } 271 } 272 )*}; 273 } 274 pub use impl_list_item; 275