rust/kernel/list/impl_list_item_mod.rs

   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;