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;
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.