1 // SPDX-License-Identifier: GPL-2.0 2 3 // Copyright (C) 2024 Google LLC. 4 5 //! A wrapper around `Arc` for linked lists. 6 7 use crate::alloc::{AllocError, Flags}; 8 use crate::prelude::*; 9 use crate::sync::{Arc, ArcBorrow, UniqueArc}; 10 use core::marker::{PhantomPinned, Unsize}; 11 use core::ops::Deref; 12 use core::pin::Pin; 13 use core::sync::atomic::{AtomicBool, Ordering}; 14 15 /// Declares that this type has some way to ensure that there is exactly one `ListArc` instance for 16 /// this id. 17 /// 18 /// Types that implement this trait should include some kind of logic for keeping track of whether 19 /// a [`ListArc`] exists or not. We refer to this logic as "the tracking inside `T`". 20 /// 21 /// We allow the case where the tracking inside `T` thinks that a [`ListArc`] exists, but actually, 22 /// there isn't a [`ListArc`]. However, we do not allow the opposite situation where a [`ListArc`] 23 /// exists, but the tracking thinks it doesn't. This is because the former can at most result in us 24 /// failing to create a [`ListArc`] when the operation could succeed, whereas the latter can result 25 /// in the creation of two [`ListArc`] references. Only the latter situation can lead to memory 26 /// safety issues. 27 /// 28 /// A consequence of the above is that you may implement the tracking inside `T` by not actually 29 /// keeping track of anything. To do this, you always claim that a [`ListArc`] exists, even if 30 /// there isn't one. This implementation is allowed by the above rule, but it means that 31 /// [`ListArc`] references can only be created if you have ownership of *all* references to the 32 /// refcounted object, as you otherwise have no way of knowing whether a [`ListArc`] exists. 33 pub trait ListArcSafe<const ID: u64 = 0> { 34 /// Informs the tracking inside this type that it now has a [`ListArc`] reference. 35 /// 36 /// This method may be called even if the tracking inside this type thinks that a `ListArc` 37 /// reference exists. (But only if that's not actually the case.) 38 /// 39 /// # Safety 40 /// 41 /// Must not be called if a [`ListArc`] already exist for this value. 42 unsafe fn on_create_list_arc_from_unique(self: Pin<&mut Self>); 43 44 /// Informs the tracking inside this type that there is no [`ListArc`] reference anymore. 45 /// 46 /// # Safety 47 /// 48 /// Must only be called if there is no [`ListArc`] reference, but the tracking thinks there is. 49 unsafe fn on_drop_list_arc(&self); 50 } 51 52 /// Declares that this type is able to safely attempt to create `ListArc`s at any time. 53 /// 54 /// # Safety 55 /// 56 /// The guarantees of `try_new_list_arc` must be upheld. 57 pub unsafe trait TryNewListArc<const ID: u64 = 0>: ListArcSafe<ID> { 58 /// Attempts to convert an `Arc<Self>` into an `ListArc<Self>`. Returns `true` if the 59 /// conversion was successful. 60 /// 61 /// This method should not be called directly. Use [`ListArc::try_from_arc`] instead. 62 /// 63 /// # Guarantees 64 /// 65 /// If this call returns `true`, then there is no [`ListArc`] pointing to this value. 66 /// Additionally, this call will have transitioned the tracking inside `Self` from not thinking 67 /// that a [`ListArc`] exists, to thinking that a [`ListArc`] exists. 68 fn try_new_list_arc(&self) -> bool; 69 } 70 71 /// Declares that this type supports [`ListArc`]. 72 /// 73 /// This macro supports a few different strategies for implementing the tracking inside the type: 74 /// 75 /// * The `untracked` strategy does not actually keep track of whether a [`ListArc`] exists. When 76 /// using this strategy, the only way to create a [`ListArc`] is using a [`UniqueArc`]. 77 /// * The `tracked_by` strategy defers the tracking to a field of the struct. The user much specify 78 /// which field to defer the tracking to. The field must implement [`ListArcSafe`]. If the field 79 /// implements [`TryNewListArc`], then the type will also implement [`TryNewListArc`]. 80 /// 81 /// The `tracked_by` strategy is usually used by deferring to a field of type 82 /// [`AtomicTracker`]. However, it is also possible to defer the tracking to another struct 83 /// using also using this macro. 84 #[macro_export] 85 macro_rules! impl_list_arc_safe { 86 (impl$({$($generics:tt)*})? ListArcSafe<$num:tt> for $t:ty { untracked; } $($rest:tt)*) => { 87 impl$(<$($generics)*>)? $crate::list::ListArcSafe<$num> for $t { 88 unsafe fn on_create_list_arc_from_unique(self: ::core::pin::Pin<&mut Self>) {} 89 unsafe fn on_drop_list_arc(&self) {} 90 } 91 $crate::list::impl_list_arc_safe! { $($rest)* } 92 }; 93 94 (impl$({$($generics:tt)*})? ListArcSafe<$num:tt> for $t:ty { 95 tracked_by $field:ident : $fty:ty; 96 } $($rest:tt)*) => { 97 impl$(<$($generics)*>)? $crate::list::ListArcSafe<$num> for $t { 98 unsafe fn on_create_list_arc_from_unique(self: ::core::pin::Pin<&mut Self>) { 99 $crate::assert_pinned!($t, $field, $fty, inline); 100 101 // SAFETY: This field is structurally pinned as per the above assertion. 102 let field = unsafe { 103 ::core::pin::Pin::map_unchecked_mut(self, |me| &mut me.$field) 104 }; 105 // SAFETY: The caller promises that there is no `ListArc`. 106 unsafe { 107 <$fty as $crate::list::ListArcSafe<$num>>::on_create_list_arc_from_unique(field) 108 }; 109 } 110 unsafe fn on_drop_list_arc(&self) { 111 // SAFETY: The caller promises that there is no `ListArc` reference, and also 112 // promises that the tracking thinks there is a `ListArc` reference. 113 unsafe { <$fty as $crate::list::ListArcSafe<$num>>::on_drop_list_arc(&self.$field) }; 114 } 115 } 116 unsafe impl$(<$($generics)*>)? $crate::list::TryNewListArc<$num> for $t 117 where 118 $fty: TryNewListArc<$num>, 119 { 120 fn try_new_list_arc(&self) -> bool { 121 <$fty as $crate::list::TryNewListArc<$num>>::try_new_list_arc(&self.$field) 122 } 123 } 124 $crate::list::impl_list_arc_safe! { $($rest)* } 125 }; 126 127 () => {}; 128 } 129 pub use impl_list_arc_safe; 130 131 /// A wrapper around [`Arc`] that's guaranteed unique for the given id. 132 /// 133 /// The `ListArc` type can be thought of as a special reference to a refcounted object that owns the 134 /// permission to manipulate the `next`/`prev` pointers stored in the refcounted object. By ensuring 135 /// that each object has only one `ListArc` reference, the owner of that reference is assured 136 /// exclusive access to the `next`/`prev` pointers. When a `ListArc` is inserted into a [`List`], 137 /// the [`List`] takes ownership of the `ListArc` reference. 138 /// 139 /// There are various strategies to ensuring that a value has only one `ListArc` reference. The 140 /// simplest is to convert a [`UniqueArc`] into a `ListArc`. However, the refcounted object could 141 /// also keep track of whether a `ListArc` exists using a boolean, which could allow for the 142 /// creation of new `ListArc` references from an [`Arc`] reference. Whatever strategy is used, the 143 /// relevant tracking is referred to as "the tracking inside `T`", and the [`ListArcSafe`] trait 144 /// (and its subtraits) are used to update the tracking when a `ListArc` is created or destroyed. 145 /// 146 /// Note that we allow the case where the tracking inside `T` thinks that a `ListArc` exists, but 147 /// actually, there isn't a `ListArc`. However, we do not allow the opposite situation where a 148 /// `ListArc` exists, but the tracking thinks it doesn't. This is because the former can at most 149 /// result in us failing to create a `ListArc` when the operation could succeed, whereas the latter 150 /// can result in the creation of two `ListArc` references. 151 /// 152 /// While this `ListArc` is unique for the given id, there still might exist normal `Arc` 153 /// references to the object. 154 /// 155 /// # Invariants 156 /// 157 /// * Each reference counted object has at most one `ListArc` for each value of `ID`. 158 /// * The tracking inside `T` is aware that a `ListArc` reference exists. 159 /// 160 /// [`List`]: crate::list::List 161 #[repr(transparent)] 162 pub struct ListArc<T, const ID: u64 = 0> 163 where 164 T: ListArcSafe<ID> + ?Sized, 165 { 166 arc: Arc<T>, 167 } 168 169 impl<T: ListArcSafe<ID>, const ID: u64> ListArc<T, ID> { 170 /// Constructs a new reference counted instance of `T`. 171 #[inline] 172 pub fn new(contents: T, flags: Flags) -> Result<Self, AllocError> { 173 Ok(Self::from(UniqueArc::new(contents, flags)?)) 174 } 175 176 /// Use the given initializer to in-place initialize a `T`. 177 /// 178 /// If `T: !Unpin` it will not be able to move afterwards. 179 // We don't implement `InPlaceInit` because `ListArc` is implicitly pinned. This is similar to 180 // what we do for `Arc`. 181 #[inline] 182 pub fn pin_init<E>(init: impl PinInit<T, E>, flags: Flags) -> Result<Self, E> 183 where 184 E: From<AllocError>, 185 { 186 Ok(Self::from(UniqueArc::try_pin_init(init, flags)?)) 187 } 188 189 /// Use the given initializer to in-place initialize a `T`. 190 /// 191 /// This is equivalent to [`ListArc<T>::pin_init`], since a [`ListArc`] is always pinned. 192 #[inline] 193 pub fn init<E>(init: impl Init<T, E>, flags: Flags) -> Result<Self, E> 194 where 195 E: From<AllocError>, 196 { 197 Ok(Self::from(UniqueArc::try_init(init, flags)?)) 198 } 199 } 200 201 impl<T, const ID: u64> From<UniqueArc<T>> for ListArc<T, ID> 202 where 203 T: ListArcSafe<ID> + ?Sized, 204 { 205 /// Convert a [`UniqueArc`] into a [`ListArc`]. 206 #[inline] 207 fn from(unique: UniqueArc<T>) -> Self { 208 Self::from(Pin::from(unique)) 209 } 210 } 211 212 impl<T, const ID: u64> From<Pin<UniqueArc<T>>> for ListArc<T, ID> 213 where 214 T: ListArcSafe<ID> + ?Sized, 215 { 216 /// Convert a pinned [`UniqueArc`] into a [`ListArc`]. 217 #[inline] 218 fn from(mut unique: Pin<UniqueArc<T>>) -> Self { 219 // SAFETY: We have a `UniqueArc`, so there is no `ListArc`. 220 unsafe { T::on_create_list_arc_from_unique(unique.as_mut()) }; 221 let arc = Arc::from(unique); 222 // SAFETY: We just called `on_create_list_arc_from_unique` on an arc without a `ListArc`, 223 // so we can create a `ListArc`. 224 unsafe { Self::transmute_from_arc(arc) } 225 } 226 } 227 228 impl<T, const ID: u64> ListArc<T, ID> 229 where 230 T: ListArcSafe<ID> + ?Sized, 231 { 232 /// Creates two `ListArc`s from a [`UniqueArc`]. 233 /// 234 /// The two ids must be different. 235 #[inline] 236 pub fn pair_from_unique<const ID2: u64>(unique: UniqueArc<T>) -> (Self, ListArc<T, ID2>) 237 where 238 T: ListArcSafe<ID2>, 239 { 240 Self::pair_from_pin_unique(Pin::from(unique)) 241 } 242 243 /// Creates two `ListArc`s from a pinned [`UniqueArc`]. 244 /// 245 /// The two ids must be different. 246 #[inline] 247 pub fn pair_from_pin_unique<const ID2: u64>( 248 mut unique: Pin<UniqueArc<T>>, 249 ) -> (Self, ListArc<T, ID2>) 250 where 251 T: ListArcSafe<ID2>, 252 { 253 build_assert!(ID != ID2); 254 255 // SAFETY: We have a `UniqueArc`, so there is no `ListArc`. 256 unsafe { <T as ListArcSafe<ID>>::on_create_list_arc_from_unique(unique.as_mut()) }; 257 // SAFETY: We have a `UniqueArc`, so there is no `ListArc`. 258 unsafe { <T as ListArcSafe<ID2>>::on_create_list_arc_from_unique(unique.as_mut()) }; 259 260 let arc1 = Arc::from(unique); 261 let arc2 = Arc::clone(&arc1); 262 263 // SAFETY: We just called `on_create_list_arc_from_unique` on an arc without a `ListArc` 264 // for both IDs (which are different), so we can create two `ListArc`s. 265 unsafe { 266 ( 267 Self::transmute_from_arc(arc1), 268 ListArc::transmute_from_arc(arc2), 269 ) 270 } 271 } 272 273 /// Try to create a new `ListArc`. 274 /// 275 /// This fails if this value already has a `ListArc`. 276 pub fn try_from_arc(arc: Arc<T>) -> Result<Self, Arc<T>> 277 where 278 T: TryNewListArc<ID>, 279 { 280 if arc.try_new_list_arc() { 281 // SAFETY: The `try_new_list_arc` method returned true, so we made the tracking think 282 // that a `ListArc` exists. This lets us create a `ListArc`. 283 Ok(unsafe { Self::transmute_from_arc(arc) }) 284 } else { 285 Err(arc) 286 } 287 } 288 289 /// Try to create a new `ListArc`. 290 /// 291 /// This fails if this value already has a `ListArc`. 292 pub fn try_from_arc_borrow(arc: ArcBorrow<'_, T>) -> Option<Self> 293 where 294 T: TryNewListArc<ID>, 295 { 296 if arc.try_new_list_arc() { 297 // SAFETY: The `try_new_list_arc` method returned true, so we made the tracking think 298 // that a `ListArc` exists. This lets us create a `ListArc`. 299 Some(unsafe { Self::transmute_from_arc(Arc::from(arc)) }) 300 } else { 301 None 302 } 303 } 304 305 /// Try to create a new `ListArc`. 306 /// 307 /// If it's not possible to create a new `ListArc`, then the `Arc` is dropped. This will never 308 /// run the destructor of the value. 309 pub fn try_from_arc_or_drop(arc: Arc<T>) -> Option<Self> 310 where 311 T: TryNewListArc<ID>, 312 { 313 match Self::try_from_arc(arc) { 314 Ok(list_arc) => Some(list_arc), 315 Err(arc) => Arc::into_unique_or_drop(arc).map(Self::from), 316 } 317 } 318 319 /// Transmutes an [`Arc`] into a `ListArc` without updating the tracking inside `T`. 320 /// 321 /// # Safety 322 /// 323 /// * The value must not already have a `ListArc` reference. 324 /// * The tracking inside `T` must think that there is a `ListArc` reference. 325 #[inline] 326 unsafe fn transmute_from_arc(arc: Arc<T>) -> Self { 327 // INVARIANT: By the safety requirements, the invariants on `ListArc` are satisfied. 328 Self { arc } 329 } 330 331 /// Transmutes a `ListArc` into an [`Arc`] without updating the tracking inside `T`. 332 /// 333 /// After this call, the tracking inside `T` will still think that there is a `ListArc` 334 /// reference. 335 #[inline] 336 fn transmute_to_arc(self) -> Arc<T> { 337 // Use a transmute to skip destructor. 338 // 339 // SAFETY: ListArc is repr(transparent). 340 unsafe { core::mem::transmute(self) } 341 } 342 343 /// Convert ownership of this `ListArc` into a raw pointer. 344 /// 345 /// The returned pointer is indistinguishable from pointers returned by [`Arc::into_raw`]. The 346 /// tracking inside `T` will still think that a `ListArc` exists after this call. 347 #[inline] 348 pub fn into_raw(self) -> *const T { 349 Arc::into_raw(Self::transmute_to_arc(self)) 350 } 351 352 /// Take ownership of the `ListArc` from a raw pointer. 353 /// 354 /// # Safety 355 /// 356 /// * `ptr` must satisfy the safety requirements of [`Arc::from_raw`]. 357 /// * The value must not already have a `ListArc` reference. 358 /// * The tracking inside `T` must think that there is a `ListArc` reference. 359 #[inline] 360 pub unsafe fn from_raw(ptr: *const T) -> Self { 361 // SAFETY: The pointer satisfies the safety requirements for `Arc::from_raw`. 362 let arc = unsafe { Arc::from_raw(ptr) }; 363 // SAFETY: The value doesn't already have a `ListArc` reference, but the tracking thinks it 364 // does. 365 unsafe { Self::transmute_from_arc(arc) } 366 } 367 368 /// Converts the `ListArc` into an [`Arc`]. 369 #[inline] 370 pub fn into_arc(self) -> Arc<T> { 371 let arc = Self::transmute_to_arc(self); 372 // SAFETY: There is no longer a `ListArc`, but the tracking thinks there is. 373 unsafe { T::on_drop_list_arc(&arc) }; 374 arc 375 } 376 377 /// Clone a `ListArc` into an [`Arc`]. 378 #[inline] 379 pub fn clone_arc(&self) -> Arc<T> { 380 self.arc.clone() 381 } 382 383 /// Returns a reference to an [`Arc`] from the given [`ListArc`]. 384 /// 385 /// This is useful when the argument of a function call is an [`&Arc`] (e.g., in a method 386 /// receiver), but we have a [`ListArc`] instead. 387 /// 388 /// [`&Arc`]: Arc 389 #[inline] 390 pub fn as_arc(&self) -> &Arc<T> { 391 &self.arc 392 } 393 394 /// Returns an [`ArcBorrow`] from the given [`ListArc`]. 395 /// 396 /// This is useful when the argument of a function call is an [`ArcBorrow`] (e.g., in a method 397 /// receiver), but we have an [`Arc`] instead. Getting an [`ArcBorrow`] is free when optimised. 398 #[inline] 399 pub fn as_arc_borrow(&self) -> ArcBorrow<'_, T> { 400 self.arc.as_arc_borrow() 401 } 402 403 /// Compare whether two [`ListArc`] pointers reference the same underlying object. 404 #[inline] 405 pub fn ptr_eq(this: &Self, other: &Self) -> bool { 406 Arc::ptr_eq(&this.arc, &other.arc) 407 } 408 } 409 410 impl<T, const ID: u64> Deref for ListArc<T, ID> 411 where 412 T: ListArcSafe<ID> + ?Sized, 413 { 414 type Target = T; 415 416 #[inline] 417 fn deref(&self) -> &Self::Target { 418 self.arc.deref() 419 } 420 } 421 422 impl<T, const ID: u64> Drop for ListArc<T, ID> 423 where 424 T: ListArcSafe<ID> + ?Sized, 425 { 426 #[inline] 427 fn drop(&mut self) { 428 // SAFETY: There is no longer a `ListArc`, but the tracking thinks there is by the type 429 // invariants on `Self`. 430 unsafe { T::on_drop_list_arc(&self.arc) }; 431 } 432 } 433 434 impl<T, const ID: u64> AsRef<Arc<T>> for ListArc<T, ID> 435 where 436 T: ListArcSafe<ID> + ?Sized, 437 { 438 #[inline] 439 fn as_ref(&self) -> &Arc<T> { 440 self.as_arc() 441 } 442 } 443 444 // This is to allow coercion from `ListArc<T>` to `ListArc<U>` if `T` can be converted to the 445 // dynamically-sized type (DST) `U`. 446 impl<T, U, const ID: u64> core::ops::CoerceUnsized<ListArc<U, ID>> for ListArc<T, ID> 447 where 448 T: ListArcSafe<ID> + Unsize<U> + ?Sized, 449 U: ListArcSafe<ID> + ?Sized, 450 { 451 } 452 453 // This is to allow `ListArc<U>` to be dispatched on when `ListArc<T>` can be coerced into 454 // `ListArc<U>`. 455 impl<T, U, const ID: u64> core::ops::DispatchFromDyn<ListArc<U, ID>> for ListArc<T, ID> 456 where 457 T: ListArcSafe<ID> + Unsize<U> + ?Sized, 458 U: ListArcSafe<ID> + ?Sized, 459 { 460 } 461 462 /// A utility for tracking whether a [`ListArc`] exists using an atomic. 463 /// 464 /// # Invariant 465 /// 466 /// If the boolean is `false`, then there is no [`ListArc`] for this value. 467 #[repr(transparent)] 468 pub struct AtomicTracker<const ID: u64 = 0> { 469 inner: AtomicBool, 470 // This value needs to be pinned to justify the INVARIANT: comment in `AtomicTracker::new`. 471 _pin: PhantomPinned, 472 } 473 474 impl<const ID: u64> AtomicTracker<ID> { 475 /// Creates a new initializer for this type. 476 pub fn new() -> impl PinInit<Self> { 477 // INVARIANT: Pin-init initializers can't be used on an existing `Arc`, so this value will 478 // not be constructed in an `Arc` that already has a `ListArc`. 479 Self { 480 inner: AtomicBool::new(false), 481 _pin: PhantomPinned, 482 } 483 } 484 485 fn project_inner(self: Pin<&mut Self>) -> &mut AtomicBool { 486 // SAFETY: The `inner` field is not structurally pinned, so we may obtain a mutable 487 // reference to it even if we only have a pinned reference to `self`. 488 unsafe { &mut Pin::into_inner_unchecked(self).inner } 489 } 490 } 491 492 impl<const ID: u64> ListArcSafe<ID> for AtomicTracker<ID> { 493 unsafe fn on_create_list_arc_from_unique(self: Pin<&mut Self>) { 494 // INVARIANT: We just created a ListArc, so the boolean should be true. 495 *self.project_inner().get_mut() = true; 496 } 497 498 unsafe fn on_drop_list_arc(&self) { 499 // INVARIANT: We just dropped a ListArc, so the boolean should be false. 500 self.inner.store(false, Ordering::Release); 501 } 502 } 503 504 // SAFETY: If this method returns `true`, then by the type invariant there is no `ListArc` before 505 // this call, so it is okay to create a new `ListArc`. 506 // 507 // The acquire ordering will synchronize with the release store from the destruction of any 508 // previous `ListArc`, so if there was a previous `ListArc`, then the destruction of the previous 509 // `ListArc` happens-before the creation of the new `ListArc`. 510 unsafe impl<const ID: u64> TryNewListArc<ID> for AtomicTracker<ID> { 511 fn try_new_list_arc(&self) -> bool { 512 // INVARIANT: If this method returns true, then the boolean used to be false, and is no 513 // longer false, so it is okay for the caller to create a new [`ListArc`]. 514 self.inner 515 .compare_exchange(false, true, Ordering::Acquire, Ordering::Relaxed) 516 .is_ok() 517 } 518 } 519