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