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
32namespace libkern {
33namespace isp_detail {
34// TODO: Consolidate these utilities with the ones used in other similar places.
35using nullptr_t = decltype(nullptr);
36
37template <typename T> T && declval() noexcept;
38
39template <typename ...> using void_t = void;
40
41template <typename T> struct is_lvalue_reference { static constexpr bool value = false; };
42template <typename T> struct is_lvalue_reference<T&> { static constexpr bool value = true; };
43template <typename T> constexpr bool is_lvalue_reference_v = is_lvalue_reference<T>::value;
44
45template <typename T> constexpr bool is_empty_v = __is_empty(T);
46
47template <typename T> struct remove_reference { using type = T; };
48template <typename T> struct remove_reference<T&> { using type = T; };
49template <typename T> struct remove_reference<T &&> { using type = T; };
50template <typename T> using remove_reference_t = typename remove_reference<T>::type;
51
52template <bool Cond, typename T = void> struct enable_if;
53template <typename T> struct enable_if<true, T> { using type = T; };
54template <bool Cond, typename T = void> using enable_if_t = typename enable_if<Cond, T>::type;
55
56template <typename From, typename To> constexpr bool is_convertible_v = __is_convertible_to(From, To);
57
58template <typename T>
59constexpr T && forward(remove_reference_t<T>&t) noexcept {
60 return static_cast<T &&>(t);
61}
62
63template <typename T>
64constexpr 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
70template <typename T>
71constexpr remove_reference_t<T>&& move(T && t) noexcept {
72 using RvalueRef = remove_reference_t<T>&&;
73 return static_cast<RvalueRef>(t);
74}
75
76template <typename T, typename U>
77using WhenComparable = void_t<
78 decltype(declval<T>() == declval<U>()),
79 decltype(declval<T>() != declval<U>())
80 >;
81} // end namespace isp_detail
82
83struct no_retain_t {
84 explicit constexpr no_retain_t()
85 {
86 }
87};
88struct retain_t {
89 explicit constexpr retain_t()
90 {
91 }
92};
93inline constexpr no_retain_t no_retain{};
94inline 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.
123template <typename T, typename RefcountPolicy>
124struct __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
446private:
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).
474template <typename To, typename From, typename R>
475intrusive_shared_ptr<To, R>
476static_pointer_cast(intrusive_shared_ptr<From, R> const& ptr)
477{
478 return intrusive_shared_ptr<To, R>(static_cast<To*>(ptr.get()), retain);
479}
480template <typename To, typename From, typename R>
481intrusive_shared_ptr<To, R>
482static_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).
500template <typename To, typename From, typename R>
501intrusive_shared_ptr<To, R>
502const_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}
506template <typename To, typename From, typename R>
507intrusive_shared_ptr<To, R>
508const_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.
531template<typename To, typename From, typename R>
532intrusive_shared_ptr<To, R>
533reinterpret_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}
537template<typename To, typename From, typename R>
538intrusive_shared_ptr<To, R>
539reinterpret_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
548template <typename T, typename U, typename R, typename = isp_detail::WhenComparable<T*, U*> >
549bool
550operator==(intrusive_shared_ptr<T, R> const& x, intrusive_shared_ptr<U, R> const& y)
551{
552 return x.get() == y.get();
553}
554
555template <typename T, typename U, typename R, typename = isp_detail::WhenComparable<T*, U*> >
556bool
557operator!=(intrusive_shared_ptr<T, R> const& x, intrusive_shared_ptr<U, R> const& y)
558{
559 return x.get() != y.get();
560}
561
562template <typename T, typename U, typename R, typename = isp_detail::WhenComparable<T*, U*> >
563bool
564operator==(intrusive_shared_ptr<T, R> const& x, U* y)
565{
566 return x.get() == y;
567}
568
569template <typename T, typename U, typename R, typename = isp_detail::WhenComparable<T*, U*> >
570bool
571operator!=(intrusive_shared_ptr<T, R> const& x, U* y)
572{
573 return x.get() != y;
574}
575
576template <typename T, typename U, typename R, typename = isp_detail::WhenComparable<T*, U*> >
577bool
578operator==(T* x, intrusive_shared_ptr<U, R> const& y)
579{
580 return x == y.get();
581}
582
583template <typename T, typename U, typename R, typename = isp_detail::WhenComparable<T*, U*> >
584bool
585operator!=(T* x, intrusive_shared_ptr<U, R> const& y)
586{
587 return x != y.get();
588}
589
590template <typename T, typename R>
591bool
592operator==(intrusive_shared_ptr<T, R> const& x, isp_detail::nullptr_t) noexcept
593{
594 return x.get() == nullptr;
595}
596
597template <typename T, typename R>
598bool
599operator==(isp_detail::nullptr_t, intrusive_shared_ptr<T, R> const& x) noexcept
600{
601 return nullptr == x.get();
602}
603
604template <typename T, typename R>
605bool
606operator!=(intrusive_shared_ptr<T, R> const& x, isp_detail::nullptr_t) noexcept
607{
608 return x.get() != nullptr;
609}
610
611template <typename T, typename R>
612bool
613operator!=(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