1 // 2 // Copyright (c) 2019 Apple, Inc. All rights reserved. 3 // 4 // @APPLE_OSREFERENCE_LICENSE_HEADER_START@ 5 // 6 // This file contains Original Code and/or Modifications of Original Code 7 // as defined in and that are subject to the Apple Public Source License 8 // Version 2.0 (the 'License'). You may not use this file except in 9 // compliance with the License. The rights granted to you under the License 10 // may not be used to create, or enable the creation or redistribution of, 11 // unlawful or unlicensed copies of an Apple operating system, or to 12 // circumvent, violate, or enable the circumvention or violation of, any 13 // terms of an Apple operating system software license agreement. 14 // 15 // Please obtain a copy of the License at 16 // http://www.opensource.apple.com/apsl/ and read it before using this file. 17 // 18 // The Original Code and all software distributed under the License are 19 // distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER 20 // EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, 21 // INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, 22 // FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT. 23 // Please see the License for the specific language governing rights and 24 // limitations under the License. 25 // 26 // @APPLE_OSREFERENCE_LICENSE_HEADER_END@ 27 // 28 29 #ifndef XNU_LIBKERN_LIBKERN_CXX_INTRUSIVE_SHARED_PTR_H 30 #define XNU_LIBKERN_LIBKERN_CXX_INTRUSIVE_SHARED_PTR_H 31 32 namespace libkern { 33 namespace isp_detail { 34 // TODO: Consolidate these utilities with the ones used in other similar places. 35 using nullptr_t = decltype(nullptr); 36 37 template <typename T> T && declval() noexcept; 38 39 template <typename ...> using void_t = void; 40 41 template <typename T> struct is_lvalue_reference { static constexpr bool value = false; }; 42 template <typename T> struct is_lvalue_reference<T&> { static constexpr bool value = true; }; 43 template <typename T> constexpr bool is_lvalue_reference_v = is_lvalue_reference<T>::value; 44 45 template <typename T> constexpr bool is_empty_v = __is_empty(T); 46 47 template <typename T> struct remove_reference { using type = T; }; 48 template <typename T> struct remove_reference<T&> { using type = T; }; 49 template <typename T> struct remove_reference<T &&> { using type = T; }; 50 template <typename T> using remove_reference_t = typename remove_reference<T>::type; 51 52 template <bool Cond, typename T = void> struct enable_if; 53 template <typename T> struct enable_if<true, T> { using type = T; }; 54 template <bool Cond, typename T = void> using enable_if_t = typename enable_if<Cond, T>::type; 55 56 template <typename From, typename To> constexpr bool is_convertible_v = __is_convertible_to(From, To); 57 58 template <typename T> 59 constexpr T && forward(remove_reference_t<T>&t) noexcept { 60 return static_cast<T &&>(t); 61 } 62 63 template <typename T> 64 constexpr T && forward(remove_reference_t<T>&& t) noexcept { 65 static_assert(!is_lvalue_reference_v<T>, 66 "can not forward an rvalue as an lvalue"); 67 return static_cast<T &&>(t); 68 } 69 70 template <typename T> 71 constexpr remove_reference_t<T>&& move(T && t) noexcept { 72 using RvalueRef = remove_reference_t<T>&&; 73 return static_cast<RvalueRef>(t); 74 } 75 76 template <typename T, typename U> 77 using WhenComparable = void_t< 78 decltype(declval<T>() == declval<U>()), 79 decltype(declval<T>() != declval<U>()) 80 >; 81 } // end namespace isp_detail 82 83 struct no_retain_t { 84 explicit constexpr no_retain_t() 85 { 86 } 87 }; 88 struct retain_t { 89 explicit constexpr retain_t() 90 { 91 } 92 }; 93 inline constexpr no_retain_t no_retain{}; 94 inline constexpr retain_t retain{}; 95 96 // Smart pointer representing a shared resource. 97 // 98 // This shared pointer class implements a refcounted resource that uses 99 // a policy to manage the refcount. This allows various refcount 100 // implementations, notably ones where the refcount is contained 101 // in the pointed-to object. 102 // 103 // The refcounting policy must consist of the following two static functions: 104 // 105 // static void RefcountPolicy::retain(T&); 106 // static void RefcountPolicy::release(T&); 107 // 108 // The `retain` function is called whenever a new reference to the pointed-to 109 // object is created, and should increase the refcount. The `release` function 110 // is called whenever a reference to the pointed-to object is removed, and 111 // should decrease the refcount. These functions are always called with a 112 // reference to a valid object, i.e. there is no need to check whether the 113 // reference is null in `retain()` and `release()` (since this is already 114 // handled by the shared pointer). 115 // 116 // One notable difference between this shared pointer and most other shared 117 // pointer classes is that this shared pointer never destroys the pointed-to 118 // object. It relies on the `release()` function to do it whenever the refcount 119 // hits 0. 120 // 121 // Since this class represents a pointer to an object (as opposed to a range 122 // of objects), pointer arithmetic is not allowed on `intrusive_shared_ptr`s. 123 template <typename T, typename RefcountPolicy> 124 struct __attribute__((trivial_abi)) intrusive_shared_ptr { 125 static_assert(isp_detail::is_empty_v<RefcountPolicy>, 126 "intrusive_shared_ptr only allows a stateless RefcountPolicy " 127 "because it must be ABI compatible with raw pointers."); 128 129 // TODO: Add a check that `T` can be used with the `RefcountPolicy` 130 131 using pointer = T *; 132 using element_type = T; 133 134 // Constructs a null shared pointer. 135 // 136 // A null shared pointer can't be dereferenced, but it can be checked 137 // for nullness, assigned to, reset, etc. 138 constexpr intrusive_shared_ptr() noexcept : ptr_(nullptr) { 139 } 140 constexpr intrusive_shared_ptr(isp_detail::nullptr_t) noexcept : ptr_(nullptr) { 141 } 142 143 // Constructs a shared pointer to the given object, incrementing the 144 // refcount for that object. 145 // 146 // This constructor is adequate when transforming a raw pointer with 147 // shared ownership into a shared pointer, when the raw pointer is at 148 // +1. This can be done by replacing the raw pointer and the manual call 149 // to `retain()` by a shared pointer constructed with this constructor, 150 // which will retain the pointed-to object. 151 // 152 // If the original code did not contain a manual retain and you use this 153 // constructor, you will create a leak. 154 explicit 155 intrusive_shared_ptr(pointer p, retain_t) noexcept : ptr_(p) { 156 if (ptr_ != nullptr) { 157 RefcountPolicy::retain(*ptr_); 158 } 159 } 160 161 // Constructs a shared pointer to the given object, without incrementing 162 // the refcount for that object. 163 // 164 // This constructor is adequate when transforming a raw pointer with 165 // shared ownership into a shared pointer, when the raw pointer is at 166 // +0. This can be done by replacing the raw pointer by a shared 167 // pointer constructed with this constructor, which does not retain 168 // the pointed-to object. 169 // 170 // If the original code contained a manual retain that you removed and 171 // you use this constructor, you will cause a use-after-free bug. 172 explicit constexpr 173 intrusive_shared_ptr(__attribute__((os_consumed)) pointer p, no_retain_t) noexcept : ptr_(p) { 174 } 175 176 // Makes a copy of a shared pointer, incrementing the refcount. 177 // 178 // Since this creates a new reference to the pointed-to object, the 179 // refcount is increased. Unlike for move operations, the source 180 // pointer is left untouched. 181 intrusive_shared_ptr(intrusive_shared_ptr const & other) : ptr_(other.ptr_) { 182 if (ptr_ != nullptr) { 183 RefcountPolicy::retain(*ptr_); 184 } 185 } 186 187 // Makes a copy of a shared pointer from another compatible shared pointer, 188 // increasing the refcount. 189 // 190 // This converting constructor is enabled whenever `U*` is implicitly 191 // convertible to `T*`. This allows the usual implicit conversions 192 // between base-and-derived types. 193 // 194 // Since this creates a new reference to the pointed-to object, the 195 // refcount is increased. Unlike for move operations, the source 196 // pointer is left untouched. 197 template <typename U, typename = isp_detail::enable_if_t<isp_detail::is_convertible_v<U*, T*> > > 198 intrusive_shared_ptr(intrusive_shared_ptr<U, RefcountPolicy> const & other) : ptr_(other.ptr_) { 199 if (ptr_ != nullptr) { 200 RefcountPolicy::retain(*ptr_); 201 } 202 } 203 204 // Moves a shared pointer into another one, nulling the source. 205 // 206 // Since this moves the ownership from one pointer to another, no 207 // refcount increment or decrement is required. The moved-from pointer 208 // becomes a null pointer, as if it had been default-constructed. 209 constexpr intrusive_shared_ptr(intrusive_shared_ptr && other) noexcept : ptr_(other.ptr_) { 210 other.ptr_ = nullptr; 211 } 212 213 // Moves a shared pointer to a type `U` into a shared pointer 214 // to a type `T`. 215 // 216 // This converting constructor is enabled whenever `U*` is implicitly 217 // convertible to `T*`. This allows the usual implicit conversions 218 // between base-and-derived types. 219 // 220 // Since this moves the ownership from one pointer to another, no 221 // refcount increment or decrement is required. The moved-from pointer 222 // becomes a null pointer, as if it had been default-constructed. 223 template <typename U, typename = isp_detail::enable_if_t<isp_detail::is_convertible_v<U*, T*> > > 224 constexpr intrusive_shared_ptr(intrusive_shared_ptr<U, RefcountPolicy>&& other) noexcept : ptr_(other.ptr_) { 225 other.ptr_ = nullptr; 226 } 227 228 // Destroys a shared pointer. 229 // 230 // The destruction of the shared pointer implies that one fewer reference 231 // to the pointed-to object exist, which means that the refcount of the 232 // pointed-to object is decremented. 233 // 234 // If that decrement causes the refcount to reach 0, the refcounting 235 // policy must destroy the pointed-to object and perform any cleanup 236 // associated to it (such as freeing the allocated memory). 237 ~intrusive_shared_ptr() { 238 reset(); 239 } 240 241 // Copy-assigns a shared pointer. 242 // 243 // Since this creates a new reference to the pointed-to object, the 244 // refcount is increased. Unlike for move operations, the source 245 // pointer is left untouched. 246 // 247 // If the destination shared pointer is pointing to an object before 248 // the assignment, the refcount is decremented on that object after 249 // the assignment is performed. 250 intrusive_shared_ptr& 251 operator=(intrusive_shared_ptr const& other) 252 { 253 reset(other.get(), retain); 254 return *this; 255 } 256 257 // Copy-assigns a shared pointer, enabling implicit conversions. 258 // 259 // This converting copy-assignment is enabled whenever `U*` is implicitly 260 // convertible to `T*`. This allows the usual implicit conversions 261 // between base-and-derived types. 262 // 263 // Since this creates a new reference to the pointed-to object, the 264 // refcount is increased. Unlike for move operations, the source 265 // pointer is left untouched. 266 // 267 // If the destination shared pointer is pointing to an object before 268 // the assignment, the refcount is decremented on that object after 269 // the assignment is performed. 270 template <typename U, typename = isp_detail::enable_if_t<isp_detail::is_convertible_v<U*, T*> > > 271 intrusive_shared_ptr& 272 operator=(intrusive_shared_ptr<U, RefcountPolicy> const& other) 273 { 274 reset(other.get(), retain); 275 return *this; 276 } 277 278 // Move-assigns a shared pointer. 279 // 280 // Since this moves the ownership from one pointer to another, no 281 // refcount increment or decrement is required. The moved-from pointer 282 // becomes a null pointer, as if it had been default-constructed. 283 // 284 // If the destination shared pointer is pointing to an object before 285 // the assignment, the refcount is decremented on that object after 286 // the assignment is performed. 287 intrusive_shared_ptr& 288 operator=(intrusive_shared_ptr&& other) 289 { 290 reset(other.get(), no_retain); 291 other.ptr_ = nullptr; 292 return *this; 293 } 294 295 // Move-assigns a shared pointer, enabling implicit conversions. 296 // 297 // This converting move-assignment is enabled whenever `U*` is implicitly 298 // convertible to `T*`. This allows the usual implicit conversions 299 // between base-and-derived types. 300 // 301 // Since this moves the ownership from one pointer to another, no 302 // refcount increment or decrement is required. The moved-from pointer 303 // becomes a null pointer, as if it had been default-constructed. 304 // 305 // If the destination shared pointer is pointing to an object before 306 // the assignment, the refcount is decremented on that object after 307 // the assignment is performed. 308 template <typename U, typename = isp_detail::enable_if_t<isp_detail::is_convertible_v<U*, T*> > > 309 intrusive_shared_ptr& 310 operator=(intrusive_shared_ptr<U, RefcountPolicy>&& other) 311 { 312 reset(other.get(), no_retain); 313 other.ptr_ = nullptr; 314 return *this; 315 } 316 317 // Resets a shared pointer to a null pointer, as if calling `reset()`. 318 // 319 // If the destination shared pointer is pointing to an object before 320 // the assignment, the refcount is decremented on that object after 321 // the assignment is performed. 322 intrusive_shared_ptr& 323 operator=(isp_detail::nullptr_t) noexcept 324 { 325 reset(); 326 return *this; 327 } 328 329 // Returns a reference to the object pointed-to by the shared pointer. 330 constexpr T& 331 operator*() const noexcept 332 { 333 return *ptr_; 334 } 335 constexpr pointer 336 operator->() const noexcept 337 { 338 return ptr_; 339 } 340 341 // Implicit conversion to bool, returning whether the shared pointer is null. 342 explicit constexpr 343 operator bool() const noexcept 344 { 345 return ptr_ != nullptr; 346 } 347 348 // Sets a shared pointer to null. 349 // 350 // If the shared pointer is pointing to an object, the refcount is 351 // decremented on that object. 352 intrusive_shared_ptr& 353 reset() noexcept 354 { 355 if (ptr_ != nullptr) { 356 RefcountPolicy::release(*ptr_); 357 } 358 ptr_ = nullptr; 359 return *this; 360 } 361 362 // Sets the object pointed-to by the shared pointer to the given object. 363 // 364 // This variant of `reset()` does not increment the refcount on the object 365 // assigned to the shared pointer. 366 // 367 // If the shared pointer is pointing to an object before calling `reset`, 368 // the refcount is decremented on that object. 369 intrusive_shared_ptr& 370 reset(__attribute__((os_consumed)) pointer p, no_retain_t) noexcept 371 { 372 if (ptr_ != nullptr) { 373 RefcountPolicy::release(*ptr_); 374 } 375 ptr_ = p; 376 return *this; 377 } 378 379 // Sets the object pointed-to by the shared pointer to the given object. 380 // 381 // This variant of `reset()` increments the refcount on the object 382 // assigned to the shared pointer. 383 // 384 // If the shared pointer is pointing to an object before calling `reset`, 385 // the refcount is decremented on that object. 386 intrusive_shared_ptr& 387 reset(pointer p, retain_t) noexcept 388 { 389 // Make sure we don't release-before-we-retain in case of self-reset 390 pointer old = ptr_; 391 ptr_ = p; 392 if (ptr_ != nullptr) { 393 RefcountPolicy::retain(*ptr_); 394 } 395 if (old != nullptr) { 396 RefcountPolicy::release(*old); 397 } 398 return *this; 399 } 400 401 // Retrieves the raw pointer held by a shared pointer. 402 // 403 // The primary intended usage of this function is to aid bridging between 404 // code that uses shared pointers and code that does not, or simply to 405 // obtain a non-owning reference to the object managed by the shared pointer. 406 // 407 // After this operation, the shared pointer still manages the object it 408 // points to (unlike for `detach()`). 409 // 410 // One must not hold on to the pointer returned by `.get()` after the 411 // last shared pointer pointing to that object goes out of scope, since 412 // it will then be a dangling pointer. To try and catch frequent cases of 413 // misuse, calling `.get()` on a temporary shared pointer is not allowed. 414 constexpr pointer 415 get() const & noexcept 416 { 417 return ptr_; 418 } 419 420 constexpr pointer 421 get() const&& noexcept = delete; 422 423 // Returns the raw pointer contained in a shared pointer, detaching 424 // ownership management from the shared pointer. 425 // 426 // This operation returns a pointer to the object pointed-to by the 427 // shared pointer, and severes the link between the shared pointer and 428 // that object. After this operation, the shared pointer is no longer 429 // responsible for managing the object, and instead whoever called 430 // `detach()` has that responsibility. 431 // 432 // `detach()` does _not_ decrement the refcount of the pointee, since 433 // the caller of `detach()` is responsible for managing the lifetime of 434 // that object. 435 // 436 // After a call to `detach()`, the shared pointer is null since it has 437 // no more object to manage. 438 constexpr pointer 439 detach() noexcept 440 { 441 pointer tmp = ptr_; 442 ptr_ = nullptr; 443 return tmp; 444 } 445 446 private: 447 friend constexpr void 448 swap(intrusive_shared_ptr& a, intrusive_shared_ptr& b) noexcept 449 { 450 pointer tmp = a.ptr_; 451 a.ptr_ = b.ptr_; 452 b.ptr_ = tmp; 453 } 454 455 // For access to other.ptr_ in converting operations 456 template <typename U, typename Policy> 457 friend struct intrusive_shared_ptr; 458 459 pointer ptr_; 460 }; 461 462 // Casts a shared pointer to a type `T` to a shared pointer to a type `U` 463 // using `static_cast` on the underlying pointer type. 464 // 465 // The version of this function that takes a const reference to the source 466 // shared pointer makes a copy, and as such it increments the refcount of the 467 // pointed-to object (since a new reference is created). It leaves the source 468 // shared pointer untouched. 469 // 470 // The version of this function that takes a rvalue-reference moves the 471 // ownership from the source shared pointer to the destination shared pointer. 472 // It does not increment the refcount, and the source shared pointer is in a 473 // moved-from state (i.e. null). 474 template <typename To, typename From, typename R> 475 intrusive_shared_ptr<To, R> 476 static_pointer_cast(intrusive_shared_ptr<From, R> const& ptr) 477 { 478 return intrusive_shared_ptr<To, R>(static_cast<To*>(ptr.get()), retain); 479 } 480 template <typename To, typename From, typename R> 481 intrusive_shared_ptr<To, R> 482 static_pointer_cast(intrusive_shared_ptr<From, R>&& ptr) 483 { 484 return intrusive_shared_ptr<To, R>(static_cast<To*>(ptr.detach()), no_retain); 485 } 486 487 // Const-casts a shared pointer to a type `cv-T` to a shared pointer to a 488 // type `T` (without cv-qualifiers) using `const_cast` on the underlying 489 // pointer type. 490 // 491 // The version of this function that takes a const reference to the source 492 // shared pointer makes a copy, and as such it increments the refcount of the 493 // pointed-to object (since a new reference is created). It leaves the source 494 // shared pointer untouched. 495 // 496 // The version of this function that takes a rvalue-reference moves the 497 // ownership from the source shared pointer to the destination shared pointer. 498 // It does not increment the refcount, and the source shared pointer is in a 499 // moved-from state (i.e. null). 500 template <typename To, typename From, typename R> 501 intrusive_shared_ptr<To, R> 502 const_pointer_cast(intrusive_shared_ptr<From, R> const& ptr) noexcept 503 { 504 return intrusive_shared_ptr<To, R>(const_cast<To*>(ptr.get()), retain); 505 } 506 template <typename To, typename From, typename R> 507 intrusive_shared_ptr<To, R> 508 const_pointer_cast(intrusive_shared_ptr<From, R>&& ptr) noexcept 509 { 510 return intrusive_shared_ptr<To, R>(const_cast<To*>(ptr.detach()), no_retain); 511 } 512 513 // Casts a shared pointer to a type `T` to a shared pointer to a type `U` 514 // using `reinterpret_cast` on the underlying pointer type. 515 // 516 // The version of this function that takes a const reference to the source 517 // shared pointer makes a copy, and as such it increments the refcount of the 518 // pointed-to object (since a new reference is created). It leaves the source 519 // shared pointer untouched. 520 // 521 // The version of this function that takes a rvalue-reference moves the 522 // ownership from the source shared pointer to the destination shared pointer. 523 // It does not increment the refcount, and the source shared pointer is in a 524 // moved-from state (i.e. null). 525 // 526 // WARNING: 527 // This function makes it possible to cast pointers between unrelated types. 528 // This rarely makes sense, and when it does, it can often point to a design 529 // problem. You should have red lights turning on when you're about to use 530 // this function. 531 template<typename To, typename From, typename R> 532 intrusive_shared_ptr<To, R> 533 reinterpret_pointer_cast(intrusive_shared_ptr<From, R> const& ptr) noexcept 534 { 535 return intrusive_shared_ptr<To, R>(reinterpret_cast<To*>(ptr.get()), retain); 536 } 537 template<typename To, typename From, typename R> 538 intrusive_shared_ptr<To, R> 539 reinterpret_pointer_cast(intrusive_shared_ptr<From, R>&& ptr) noexcept 540 { 541 return intrusive_shared_ptr<To, R>(reinterpret_cast<To*>(ptr.detach()), no_retain); 542 } 543 544 // Comparison operations between: 545 // - two shared pointers 546 // - a shared pointer and nullptr_t 547 // - a shared pointer and a raw pointer 548 template <typename T, typename U, typename R, typename = isp_detail::WhenComparable<T*, U*> > 549 bool 550 operator==(intrusive_shared_ptr<T, R> const& x, intrusive_shared_ptr<U, R> const& y) 551 { 552 return x.get() == y.get(); 553 } 554 555 template <typename T, typename U, typename R, typename = isp_detail::WhenComparable<T*, U*> > 556 bool 557 operator!=(intrusive_shared_ptr<T, R> const& x, intrusive_shared_ptr<U, R> const& y) 558 { 559 return x.get() != y.get(); 560 } 561 562 template <typename T, typename U, typename R, typename = isp_detail::WhenComparable<T*, U*> > 563 bool 564 operator==(intrusive_shared_ptr<T, R> const& x, U* y) 565 { 566 return x.get() == y; 567 } 568 569 template <typename T, typename U, typename R, typename = isp_detail::WhenComparable<T*, U*> > 570 bool 571 operator!=(intrusive_shared_ptr<T, R> const& x, U* y) 572 { 573 return x.get() != y; 574 } 575 576 template <typename T, typename U, typename R, typename = isp_detail::WhenComparable<T*, U*> > 577 bool 578 operator==(T* x, intrusive_shared_ptr<U, R> const& y) 579 { 580 return x == y.get(); 581 } 582 583 template <typename T, typename U, typename R, typename = isp_detail::WhenComparable<T*, U*> > 584 bool 585 operator!=(T* x, intrusive_shared_ptr<U, R> const& y) 586 { 587 return x != y.get(); 588 } 589 590 template <typename T, typename R> 591 bool 592 operator==(intrusive_shared_ptr<T, R> const& x, isp_detail::nullptr_t) noexcept 593 { 594 return x.get() == nullptr; 595 } 596 597 template <typename T, typename R> 598 bool 599 operator==(isp_detail::nullptr_t, intrusive_shared_ptr<T, R> const& x) noexcept 600 { 601 return nullptr == x.get(); 602 } 603 604 template <typename T, typename R> 605 bool 606 operator!=(intrusive_shared_ptr<T, R> const& x, isp_detail::nullptr_t) noexcept 607 { 608 return x.get() != nullptr; 609 } 610 611 template <typename T, typename R> 612 bool 613 operator!=(isp_detail::nullptr_t, intrusive_shared_ptr<T, R> const& x) noexcept 614 { 615 return nullptr != x.get(); 616 } 617 } // end namespace libkern 618 619 #endif // !XNU_LIBKERN_LIBKERN_CXX_INTRUSIVE_SHARED_PTR_H 620