1 // SPDX-License-Identifier: GPL-2.0 2 3 // Copyright (C) 2024 Google LLC. 4 5 //! Helpers for implementing list traits safely. 6 7 /// Declares that this type has a [`ListLinks<ID>`] field. 8 /// 9 /// This trait is only used to help implement [`ListItem`] safely. If [`ListItem`] is implemented 10 /// manually, then this trait is not needed. Use the [`impl_has_list_links!`] macro to implement 11 /// this trait. 12 /// 13 /// # Safety 14 /// 15 /// The methods on this trait must have exactly the behavior that the definitions given below have. 16 /// 17 /// [`ListLinks<ID>`]: crate::list::ListLinks 18 /// [`ListItem`]: crate::list::ListItem 19 pub unsafe trait HasListLinks<const ID: u64 = 0> { 20 /// Returns a pointer to the [`ListLinks<ID>`] field. 21 /// 22 /// # Safety 23 /// 24 /// The provided pointer must point at a valid struct of type `Self`. 25 /// 26 /// [`ListLinks<ID>`]: crate::list::ListLinks raw_get_list_links(ptr: *mut Self) -> *mut crate::list::ListLinks<ID>27 unsafe fn raw_get_list_links(ptr: *mut Self) -> *mut crate::list::ListLinks<ID>; 28 } 29 30 /// Implements the [`HasListLinks`] trait for the given type. 31 #[macro_export] 32 #[doc(hidden)] 33 macro_rules! impl_has_list_links { 34 ($(impl$({$($generics:tt)*})? 35 HasListLinks$(<$id:tt>)? 36 for $self:ty 37 { self$(.$field:ident)* } 38 )*) => {$( 39 // SAFETY: The implementation of `raw_get_list_links` only compiles if the field has the 40 // right type. 41 unsafe impl$(<$($generics)*>)? $crate::list::HasListLinks$(<$id>)? for $self { 42 #[inline] 43 unsafe fn raw_get_list_links(ptr: *mut Self) -> *mut $crate::list::ListLinks$(<$id>)? { 44 // Statically ensure that `$(.field)*` doesn't follow any pointers. 45 // 46 // Cannot be `const` because `$self` may contain generics and E0401 says constants 47 // "can't use {`Self`,generic parameters} from outer item". 48 if false { let _: usize = ::core::mem::offset_of!(Self, $($field).*); } 49 50 // SAFETY: The caller promises that the pointer is not dangling. We know that this 51 // expression doesn't follow any pointers, as the `offset_of!` invocation above 52 // would otherwise not compile. 53 unsafe { ::core::ptr::addr_of_mut!((*ptr)$(.$field)*) } 54 } 55 } 56 )*}; 57 } 58 pub use impl_has_list_links; 59 60 /// Declares that the [`ListLinks<ID>`] field in this struct is inside a 61 /// [`ListLinksSelfPtr<T, ID>`]. 62 /// 63 /// # Safety 64 /// 65 /// The [`ListLinks<ID>`] field of this struct at [`HasListLinks<ID>::raw_get_list_links`] must be 66 /// inside a [`ListLinksSelfPtr<T, ID>`]. 67 /// 68 /// [`ListLinks<ID>`]: crate::list::ListLinks 69 /// [`ListLinksSelfPtr<T, ID>`]: crate::list::ListLinksSelfPtr 70 pub unsafe trait HasSelfPtr<T: ?Sized, const ID: u64 = 0> 71 where 72 Self: HasListLinks<ID>, 73 { 74 } 75 76 /// Implements the [`HasListLinks`] and [`HasSelfPtr`] traits for the given type. 77 #[macro_export] 78 #[doc(hidden)] 79 macro_rules! impl_has_list_links_self_ptr { 80 ($(impl$({$($generics:tt)*})? 81 HasSelfPtr<$item_type:ty $(, $id:tt)?> 82 for $self:ty 83 { self$(.$field:ident)* } 84 )*) => {$( 85 // SAFETY: The implementation of `raw_get_list_links` only compiles if the field has the 86 // right type. 87 unsafe impl$(<$($generics)*>)? $crate::list::HasSelfPtr<$item_type $(, $id)?> for $self {} 88 89 // SAFETY: TODO. 90 unsafe impl$(<$($generics)*>)? $crate::list::HasListLinks$(<$id>)? for $self { 91 #[inline] 92 unsafe fn raw_get_list_links(ptr: *mut Self) -> *mut $crate::list::ListLinks$(<$id>)? { 93 let ptr: *mut $crate::list::ListLinksSelfPtr<$item_type $(, $id)?> = 94 // SAFETY: The caller promises that the pointer is not dangling. 95 unsafe { ::core::ptr::addr_of_mut!((*ptr)$(.$field)*) }; 96 ptr.cast() 97 } 98 } 99 )*}; 100 } 101 pub use impl_has_list_links_self_ptr; 102 103 /// Implements the [`ListItem`] trait for the given type. 104 /// 105 /// Requires that the type implements [`HasListLinks`]. Use the [`impl_has_list_links!`] macro to 106 /// implement that trait. 107 /// 108 /// [`ListItem`]: crate::list::ListItem 109 /// 110 /// # Examples 111 /// 112 /// ``` 113 /// #[pin_data] 114 /// struct SimpleListItem { 115 /// value: u32, 116 /// #[pin] 117 /// links: kernel::list::ListLinks, 118 /// } 119 /// 120 /// kernel::list::impl_list_arc_safe! { 121 /// impl ListArcSafe<0> for SimpleListItem { untracked; } 122 /// } 123 /// 124 /// kernel::list::impl_list_item! { 125 /// impl ListItem<0> for SimpleListItem { using ListLinks { self.links }; } 126 /// } 127 /// 128 /// struct ListLinksHolder { 129 /// inner: kernel::list::ListLinks, 130 /// } 131 /// 132 /// #[pin_data] 133 /// struct ComplexListItem<T, U> { 134 /// value: Result<T, U>, 135 /// #[pin] 136 /// links: ListLinksHolder, 137 /// } 138 /// 139 /// kernel::list::impl_list_arc_safe! { 140 /// impl{T, U} ListArcSafe<0> for ComplexListItem<T, U> { untracked; } 141 /// } 142 /// 143 /// kernel::list::impl_list_item! { 144 /// impl{T, U} ListItem<0> for ComplexListItem<T, U> { using ListLinks { self.links.inner }; } 145 /// } 146 /// ``` 147 /// 148 /// ``` 149 /// #[pin_data] 150 /// struct SimpleListItem { 151 /// value: u32, 152 /// #[pin] 153 /// links: kernel::list::ListLinksSelfPtr<SimpleListItem>, 154 /// } 155 /// 156 /// kernel::list::impl_list_arc_safe! { 157 /// impl ListArcSafe<0> for SimpleListItem { untracked; } 158 /// } 159 /// 160 /// kernel::list::impl_list_item! { 161 /// impl ListItem<0> for SimpleListItem { using ListLinksSelfPtr { self.links }; } 162 /// } 163 /// 164 /// struct ListLinksSelfPtrHolder<T, U> { 165 /// inner: kernel::list::ListLinksSelfPtr<ComplexListItem<T, U>>, 166 /// } 167 /// 168 /// #[pin_data] 169 /// struct ComplexListItem<T, U> { 170 /// value: Result<T, U>, 171 /// #[pin] 172 /// links: ListLinksSelfPtrHolder<T, U>, 173 /// } 174 /// 175 /// kernel::list::impl_list_arc_safe! { 176 /// impl{T, U} ListArcSafe<0> for ComplexListItem<T, U> { untracked; } 177 /// } 178 /// 179 /// kernel::list::impl_list_item! { 180 /// impl{T, U} ListItem<0> for ComplexListItem<T, U> { 181 /// using ListLinksSelfPtr { self.links.inner }; 182 /// } 183 /// } 184 /// ``` 185 #[macro_export] 186 #[doc(hidden)] 187 macro_rules! impl_list_item { 188 ( 189 $(impl$({$($generics:tt)*})? ListItem<$num:tt> for $self:ty { 190 using ListLinks { self$(.$field:ident)* }; 191 })* 192 ) => {$( 193 $crate::list::impl_has_list_links! { 194 impl$({$($generics)*})? HasListLinks<$num> for $self { self$(.$field)* } 195 } 196 197 // SAFETY: See GUARANTEES comment on each method. 198 unsafe impl$(<$($generics)*>)? $crate::list::ListItem<$num> for $self { 199 // GUARANTEES: 200 // * This returns the same pointer as `prepare_to_insert` because `prepare_to_insert` 201 // is implemented in terms of `view_links`. 202 // * By the type invariants of `ListLinks`, the `ListLinks` has two null pointers when 203 // this value is not in a list. 204 unsafe fn view_links(me: *const Self) -> *mut $crate::list::ListLinks<$num> { 205 // SAFETY: The caller guarantees that `me` points at a valid value of type `Self`. 206 unsafe { 207 <Self as $crate::list::HasListLinks<$num>>::raw_get_list_links(me.cast_mut()) 208 } 209 } 210 211 // GUARANTEES: 212 // * `me` originates from the most recent call to `prepare_to_insert`, which calls 213 // `raw_get_list_link`, which is implemented using `addr_of_mut!((*self)$(.$field)*)`. 214 // This method uses `container_of` to perform the inverse operation, so it returns the 215 // pointer originally passed to `prepare_to_insert`. 216 // * The pointer remains valid until the next call to `post_remove` because the caller 217 // of the most recent call to `prepare_to_insert` promised to retain ownership of the 218 // `ListArc` containing `Self` until the next call to `post_remove`. The value cannot 219 // be destroyed while a `ListArc` reference exists. 220 unsafe fn view_value(me: *mut $crate::list::ListLinks<$num>) -> *const Self { 221 // SAFETY: `me` originates from the most recent call to `prepare_to_insert`, so it 222 // points at the field `$field` in a value of type `Self`. Thus, reversing that 223 // operation is still in-bounds of the allocation. 224 unsafe { $crate::container_of!(me, Self, $($field).*) } 225 } 226 227 // GUARANTEES: 228 // This implementation of `ListItem` will not give out exclusive access to the same 229 // `ListLinks` several times because calls to `prepare_to_insert` and `post_remove` 230 // must alternate and exclusive access is given up when `post_remove` is called. 231 // 232 // Other invocations of `impl_list_item!` also cannot give out exclusive access to the 233 // same `ListLinks` because you can only implement `ListItem` once for each value of 234 // `ID`, and the `ListLinks` fields only work with the specified `ID`. 235 unsafe fn prepare_to_insert(me: *const Self) -> *mut $crate::list::ListLinks<$num> { 236 // SAFETY: The caller promises that `me` points at a valid value. 237 unsafe { <Self as $crate::list::ListItem<$num>>::view_links(me) } 238 } 239 240 // GUARANTEES: 241 // * `me` originates from the most recent call to `prepare_to_insert`, which calls 242 // `raw_get_list_link`, which is implemented using `addr_of_mut!((*self)$(.$field)*)`. 243 // This method uses `container_of` to perform the inverse operation, so it returns the 244 // pointer originally passed to `prepare_to_insert`. 245 unsafe fn post_remove(me: *mut $crate::list::ListLinks<$num>) -> *const Self { 246 // SAFETY: `me` originates from the most recent call to `prepare_to_insert`, so it 247 // points at the field `$field` in a value of type `Self`. Thus, reversing that 248 // operation is still in-bounds of the allocation. 249 unsafe { $crate::container_of!(me, Self, $($field).*) } 250 } 251 } 252 )*}; 253 254 ( 255 $(impl$({$($generics:tt)*})? ListItem<$num:tt> for $self:ty { 256 using ListLinksSelfPtr { self$(.$field:ident)* }; 257 })* 258 ) => {$( 259 $crate::list::impl_has_list_links_self_ptr! { 260 impl$({$($generics)*})? HasSelfPtr<$self> for $self { self$(.$field)* } 261 } 262 263 // SAFETY: See GUARANTEES comment on each method. 264 unsafe impl$(<$($generics)*>)? $crate::list::ListItem<$num> for $self { 265 // GUARANTEES: 266 // This implementation of `ListItem` will not give out exclusive access to the same 267 // `ListLinks` several times because calls to `prepare_to_insert` and `post_remove` 268 // must alternate and exclusive access is given up when `post_remove` is called. 269 // 270 // Other invocations of `impl_list_item!` also cannot give out exclusive access to the 271 // same `ListLinks` because you can only implement `ListItem` once for each value of 272 // `ID`, and the `ListLinks` fields only work with the specified `ID`. 273 unsafe fn prepare_to_insert(me: *const Self) -> *mut $crate::list::ListLinks<$num> { 274 // SAFETY: The caller promises that `me` points at a valid value of type `Self`. 275 let links_field = unsafe { <Self as $crate::list::ListItem<$num>>::view_links(me) }; 276 277 // SAFETY: TODO. 278 let container = unsafe { 279 $crate::container_of!( 280 links_field, $crate::list::ListLinksSelfPtr<Self, $num>, inner 281 ) 282 }; 283 284 // SAFETY: By the same reasoning above, `links_field` is a valid pointer. 285 let self_ptr = unsafe { 286 $crate::list::ListLinksSelfPtr::raw_get_self_ptr(container) 287 }; 288 289 let cell_inner = $crate::types::Opaque::cast_into(self_ptr); 290 291 // SAFETY: This value is not accessed in any other places than `prepare_to_insert`, 292 // `post_remove`, or `view_value`. By the safety requirements of those methods, 293 // none of these three methods may be called in parallel with this call to 294 // `prepare_to_insert`, so this write will not race with any other access to the 295 // value. 296 unsafe { ::core::ptr::write(cell_inner, me) }; 297 298 links_field 299 } 300 301 // GUARANTEES: 302 // * This returns the same pointer as `prepare_to_insert` because `prepare_to_insert` 303 // returns the return value of `view_links`. 304 // * By the type invariants of `ListLinks`, the `ListLinks` has two null pointers when 305 // this value is not in a list. 306 unsafe fn view_links(me: *const Self) -> *mut $crate::list::ListLinks<$num> { 307 // SAFETY: The caller promises that `me` points at a valid value of type `Self`. 308 unsafe { 309 <Self as $crate::list::HasListLinks<$num>>::raw_get_list_links(me.cast_mut()) 310 } 311 } 312 313 // This function is also used as the implementation of `post_remove`, so the caller 314 // may choose to satisfy the safety requirements of `post_remove` instead of the safety 315 // requirements for `view_value`. 316 // 317 // GUARANTEES: (always) 318 // * This returns the same pointer as the one passed to the most recent call to 319 // `prepare_to_insert` since that call wrote that pointer to this location. The value 320 // is only modified in `prepare_to_insert`, so it has not been modified since the 321 // most recent call. 322 // 323 // GUARANTEES: (only when using the `view_value` safety requirements) 324 // * The pointer remains valid until the next call to `post_remove` because the caller 325 // of the most recent call to `prepare_to_insert` promised to retain ownership of the 326 // `ListArc` containing `Self` until the next call to `post_remove`. The value cannot 327 // be destroyed while a `ListArc` reference exists. 328 unsafe fn view_value(links_field: *mut $crate::list::ListLinks<$num>) -> *const Self { 329 // SAFETY: TODO. 330 let container = unsafe { 331 $crate::container_of!( 332 links_field, $crate::list::ListLinksSelfPtr<Self, $num>, inner 333 ) 334 }; 335 336 // SAFETY: By the same reasoning above, `links_field` is a valid pointer. 337 let self_ptr = unsafe { 338 $crate::list::ListLinksSelfPtr::raw_get_self_ptr(container) 339 }; 340 341 let cell_inner = $crate::types::Opaque::cast_into(self_ptr); 342 343 // SAFETY: This is not a data race, because the only function that writes to this 344 // value is `prepare_to_insert`, but by the safety requirements the 345 // `prepare_to_insert` method may not be called in parallel with `view_value` or 346 // `post_remove`. 347 unsafe { ::core::ptr::read(cell_inner) } 348 } 349 350 // GUARANTEES: 351 // The first guarantee of `view_value` is exactly what `post_remove` guarantees. 352 unsafe fn post_remove(me: *mut $crate::list::ListLinks<$num>) -> *const Self { 353 // SAFETY: This specific implementation of `view_value` allows the caller to 354 // promise the safety requirements of `post_remove` instead of the safety 355 // requirements for `view_value`. 356 unsafe { <Self as $crate::list::ListItem<$num>>::view_value(me) } 357 } 358 } 359 )*}; 360 } 361 pub use impl_list_item; 362