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