2 * Copyright 2017 Facebook, Inc.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
17 /* override-include-guard */
19 #error "This should only be included by hazptr.h"
22 /* quality of implementation switches */
24 // NOTE: The #ifndef pattern is prone to ODR violation. Its use for
25 // quality of implementation options is temporary. Eventually these
26 // options should be added to the API in future API extensions.
29 #define HAZPTR_AMB true
33 #define HAZPTR_TC true
36 #ifndef HAZPTR_TC_SIZE
37 #define HAZPTR_TC_SIZE 10
41 #define HAZPTR_PRIV true
44 #ifndef HAZPTR_ONE_DOMAIN
45 #define HAZPTR_ONE_DOMAIN false
48 #ifndef HAZPTR_SCAN_MULT
49 #define HAZPTR_SCAN_MULT 2
52 #ifndef HAZPTR_SCAN_THRESHOLD
53 #define HAZPTR_SCAN_THRESHOLD 1000
58 #define HAZPTR_STATS false
61 #include <folly/concurrency/CacheLocality.h>
62 #include <folly/experimental/AsymmetricMemoryBarrier.h>
63 #include <folly/experimental/hazptr/debug.h>
65 #include <mutex> // for thread caching
66 #include <unordered_set> // for hash set in bulk reclamation
72 * Helper classes and functions
80 #define INC_HAZPTR_STATS(x) hazptr_stats_.x()
82 #define INC_HAZPTR_STATS(x)
99 enum hazptr_tls_state { TLS_ALIVE, TLS_UNINITIALIZED, TLS_DESTROYED };
101 /** hazptr_tc structures
102 * Thread caching of hazptr_rec-s that belong to the default domain.
105 struct hazptr_tc_entry {
108 void fill(hazptr_rec* hprec);
114 std::is_trivial<hazptr_tc_entry>::value,
115 "hazptr_tc_entry must be trivial"
116 " to avoid a branch to check initialization");
119 hazptr_tc_entry entry_[HAZPTR_TC_SIZE];
124 bool put(hazptr_rec* hprec);
128 std::is_trivial<hazptr_tc>::value,
129 "hazptr_tc must be trivial to avoid a branch to check initialization");
131 void hazptr_tc_init();
132 void hazptr_tc_shutdown();
133 hazptr_rec* hazptr_tc_try_get();
134 bool hazptr_tc_try_put(hazptr_rec* hprec);
136 /** hazptr_priv structures
137 * Thread private lists of retired objects that belong to the default domain.
146 void push(hazptr_obj* obj);
147 void pushAllToDomain();
151 std::is_trivial<hazptr_priv>::value,
152 "hazptr_priv must be trivial to avoid a branch to check initialization");
154 void hazptr_priv_init();
155 void hazptr_priv_shutdown();
156 bool hazptr_priv_try_retire(hazptr_obj* obj);
158 /** hazptr_tls_life */
160 struct hazptr_tls_life {
165 void tls_life_odr_use();
169 extern thread_local hazptr_tls_state tls_state_;
170 extern thread_local hazptr_tc tls_tc_data_;
171 extern thread_local hazptr_priv tls_priv_data_;
172 extern thread_local hazptr_tls_life tls_life_; // last
178 inline constexpr hazptr_domain::hazptr_domain(memory_resource* mr) noexcept
185 template <typename T, typename D>
186 inline void hazptr_obj_base<T, D>::retire(hazptr_domain& domain, D deleter) {
187 DEBUG_PRINT(this << " " << &domain);
188 deleter_ = std::move(deleter);
189 reclaim_ = [](hazptr_obj* p) {
190 auto hobp = static_cast<hazptr_obj_base*>(p);
191 auto obj = static_cast<T*>(hobp);
195 (HAZPTR_ONE_DOMAIN || (&domain == &default_hazptr_domain()))) {
196 if (hazptr_priv_try_retire(this)) {
200 domain.objRetire(this);
208 friend class hazptr_domain;
209 friend class hazptr_holder;
210 friend struct hazptr_tc_entry;
212 FOLLY_ALIGN_TO_AVOID_FALSE_SHARING
213 std::atomic<const void*> hazptr_{nullptr};
214 hazptr_rec* next_{nullptr};
215 std::atomic<bool> active_{false};
217 void set(const void* p) noexcept;
218 const void* get() const noexcept;
219 void clear() noexcept;
220 bool isActive() noexcept;
221 bool tryAcquire() noexcept;
222 void release() noexcept;
229 FOLLY_ALWAYS_INLINE hazptr_holder::hazptr_holder(hazptr_domain& domain) {
233 (HAZPTR_ONE_DOMAIN || &domain == &default_hazptr_domain()))) {
234 auto hprec = hazptr_tc_try_get();
235 if (LIKELY(hprec != nullptr)) {
237 DEBUG_PRINT(this << " " << domain_ << " " << hazptr_);
241 hazptr_ = domain_->hazptrAcquire();
242 DEBUG_PRINT(this << " " << domain_ << " " << hazptr_);
243 if (hazptr_ == nullptr) { std::bad_alloc e; throw e; }
246 FOLLY_ALWAYS_INLINE hazptr_holder::hazptr_holder(std::nullptr_t) {
249 DEBUG_PRINT(this << " " << domain_ << " " << hazptr_);
252 FOLLY_ALWAYS_INLINE hazptr_holder::~hazptr_holder() {
254 if (LIKELY(hazptr_ != nullptr)) {
258 (HAZPTR_ONE_DOMAIN || domain_ == &default_hazptr_domain()))) {
259 if (LIKELY(hazptr_tc_try_put(hazptr_))) {
263 domain_->hazptrRelease(hazptr_);
267 FOLLY_ALWAYS_INLINE hazptr_holder::hazptr_holder(hazptr_holder&& rhs) noexcept {
268 domain_ = rhs.domain_;
269 hazptr_ = rhs.hazptr_;
270 rhs.domain_ = nullptr;
271 rhs.hazptr_ = nullptr;
275 hazptr_holder& hazptr_holder::operator=(hazptr_holder&& rhs) noexcept {
276 /* Self-move is a no-op. */
277 if (LIKELY(this != &rhs)) {
278 this->~hazptr_holder();
279 new (this) hazptr_holder(std::move(rhs));
284 template <typename T>
285 FOLLY_ALWAYS_INLINE bool hazptr_holder::try_protect(
287 const std::atomic<T*>& src) noexcept {
288 return try_protect(ptr, src, [](T* t) { return t; });
291 template <typename T, typename Func>
292 FOLLY_ALWAYS_INLINE bool hazptr_holder::try_protect(
294 const std::atomic<T*>& src,
296 DEBUG_PRINT(this << " " << ptr << " " << &src);
298 /*** Full fence ***/ hazptr_mb::light();
299 T* p = src.load(std::memory_order_acquire);
300 if (UNLIKELY(p != ptr)) {
308 template <typename T>
309 FOLLY_ALWAYS_INLINE T* hazptr_holder::get_protected(
310 const std::atomic<T*>& src) noexcept {
311 return get_protected(src, [](T* t) { return t; });
314 template <typename T, typename Func>
315 FOLLY_ALWAYS_INLINE T* hazptr_holder::get_protected(
316 const std::atomic<T*>& src,
318 T* p = src.load(std::memory_order_relaxed);
319 while (!try_protect(p, src, f)) {
321 DEBUG_PRINT(this << " " << p << " " << &src);
325 template <typename T>
326 FOLLY_ALWAYS_INLINE void hazptr_holder::reset(const T* ptr) noexcept {
327 auto p = static_cast<hazptr_obj*>(const_cast<T*>(ptr));
328 DEBUG_PRINT(this << " " << ptr << " p:" << p);
329 DCHECK(hazptr_); // UB if *this is empty
333 FOLLY_ALWAYS_INLINE void hazptr_holder::reset(std::nullptr_t) noexcept {
335 DCHECK(hazptr_); // UB if *this is empty
339 FOLLY_ALWAYS_INLINE void hazptr_holder::swap(hazptr_holder& rhs) noexcept {
341 this << " " << this->hazptr_ << " " << this->domain_ << " -- "
342 << &rhs << " " << rhs.hazptr_ << " " << rhs.domain_);
343 if (!HAZPTR_ONE_DOMAIN) {
344 std::swap(this->domain_, rhs.domain_);
346 std::swap(this->hazptr_, rhs.hazptr_);
349 FOLLY_ALWAYS_INLINE void swap(hazptr_holder& lhs, hazptr_holder& rhs) noexcept {
353 ////////////////////////////////////////////////////////////////////////////////
355 // - Control of reclamation (when and by whom)
356 // - End-to-end lock-free implementation
358 /** Definition of default_hazptr_domain() */
360 FOLLY_ALWAYS_INLINE hazptr_domain& default_hazptr_domain() {
361 DEBUG_PRINT(&default_domain_);
362 return default_domain_;
367 FOLLY_ALWAYS_INLINE void hazptr_rec::set(const void* p) noexcept {
368 DEBUG_PRINT(this << " " << p);
369 hazptr_.store(p, std::memory_order_release);
372 inline const void* hazptr_rec::get() const noexcept {
373 auto p = hazptr_.load(std::memory_order_acquire);
374 DEBUG_PRINT(this << " " << p);
378 FOLLY_ALWAYS_INLINE void hazptr_rec::clear() noexcept {
380 hazptr_.store(nullptr, std::memory_order_release);
383 inline bool hazptr_rec::isActive() noexcept {
384 return active_.load(std::memory_order_acquire);
387 inline bool hazptr_rec::tryAcquire() noexcept {
388 bool active = isActive();
390 active_.compare_exchange_strong(
391 active, true, std::memory_order_release, std::memory_order_relaxed)) {
398 inline void hazptr_rec::release() noexcept {
400 active_.store(false, std::memory_order_release);
405 inline const void* hazptr_obj::getObjPtr() const {
412 inline hazptr_domain::~hazptr_domain() {
414 { /* reclaim all remaining retired objects */
416 auto retired = retired_.exchange(nullptr);
418 for (auto p = retired; p; p = next) {
422 retired = retired_.exchange(nullptr);
425 /* Leak the data for the default domain to avoid destruction order
426 * issues with thread caches.
428 if (this != &default_hazptr_domain()) {
429 /* free all hazptr_rec-s */
431 for (auto p = hazptrs_.load(std::memory_order_acquire); p; p = next) {
433 DCHECK(!p->isActive());
434 mr_->deallocate(static_cast<void*>(p), sizeof(hazptr_rec));
439 inline hazptr_rec* hazptr_domain::hazptrAcquire() {
442 for (p = hazptrs_.load(std::memory_order_acquire); p; p = next) {
444 if (p->tryAcquire()) {
448 p = static_cast<hazptr_rec*>(mr_->allocate(sizeof(hazptr_rec)));
449 DEBUG_PRINT(this << " " << p << " " << sizeof(hazptr_rec));
453 p->active_.store(true, std::memory_order_relaxed);
454 p->next_ = hazptrs_.load(std::memory_order_acquire);
455 while (!hazptrs_.compare_exchange_weak(
456 p->next_, p, std::memory_order_release, std::memory_order_acquire))
458 auto hcount = hcount_.fetch_add(1);
459 DEBUG_PRINT(this << " " << p << " " << sizeof(hazptr_rec) << " " << hcount);
463 inline void hazptr_domain::hazptrRelease(hazptr_rec* p) noexcept {
464 DEBUG_PRINT(this << " " << p);
469 hazptr_domain::pushRetired(hazptr_obj* head, hazptr_obj* tail, int count) {
470 /*** Full fence ***/ hazptr_mb::light();
471 tail->next_ = retired_.load(std::memory_order_acquire);
472 while (!retired_.compare_exchange_weak(
475 std::memory_order_release,
476 std::memory_order_acquire)) {
478 return rcount_.fetch_add(count) + count;
481 inline bool hazptr_domain::reachedThreshold(int rcount) {
483 rcount >= HAZPTR_SCAN_THRESHOLD &&
484 rcount >= HAZPTR_SCAN_MULT * hcount_.load(std::memory_order_acquire));
487 inline void hazptr_domain::objRetire(hazptr_obj* p) {
488 auto rcount = pushRetired(p, p, 1);
489 if (reachedThreshold(rcount)) {
494 inline void hazptr_domain::tryBulkReclaim() {
497 auto hcount = hcount_.load(std::memory_order_acquire);
498 auto rcount = rcount_.load(std::memory_order_acquire);
499 if (rcount < HAZPTR_SCAN_THRESHOLD || rcount < HAZPTR_SCAN_MULT * hcount) {
502 if (rcount_.compare_exchange_weak(
503 rcount, 0, std::memory_order_release, std::memory_order_relaxed)) {
510 inline void hazptr_domain::bulkReclaim() {
512 /*** Full fence ***/ hazptr_mb::heavy();
513 auto p = retired_.exchange(nullptr, std::memory_order_acquire);
514 auto h = hazptrs_.load(std::memory_order_acquire);
515 std::unordered_set<const void*> hs; // TODO lock-free alternative
516 for (; h; h = h->next_) {
520 hazptr_obj* retired = nullptr;
521 hazptr_obj* tail = nullptr;
523 for (; p; p = next) {
525 if (hs.count(p->getObjPtr()) == 0) {
526 DEBUG_PRINT(this << " " << p << " " << p->reclaim_);
531 if (tail == nullptr) {
538 pushRetired(retired, tail, rcount);
552 std::atomic<uint64_t> light_{0};
553 std::atomic<uint64_t> heavy_{0};
554 std::atomic<uint64_t> seq_cst_{0};
557 extern hazptr_stats hazptr_stats_;
559 inline hazptr_stats::~hazptr_stats() {
560 DEBUG_PRINT(this << " light " << light_.load());
561 DEBUG_PRINT(this << " heavy " << heavy_.load());
562 DEBUG_PRINT(this << " seq_cst " << seq_cst_.load());
565 FOLLY_ALWAYS_INLINE void hazptr_stats::light() {
567 /* atomic */ ++light_;
571 inline void hazptr_stats::heavy() {
573 /* atomic */ ++heavy_;
577 inline void hazptr_stats::seq_cst() {
579 /* atomic */ ++seq_cst_;
585 FOLLY_ALWAYS_INLINE void hazptr_mb::light() {
588 folly::asymmetricLightBarrier();
589 INC_HAZPTR_STATS(light);
591 atomic_thread_fence(std::memory_order_seq_cst);
592 INC_HAZPTR_STATS(seq_cst);
596 inline void hazptr_mb::heavy() {
599 folly::asymmetricHeavyBarrier(AMBFlags::EXPEDITED);
600 INC_HAZPTR_STATS(heavy);
602 atomic_thread_fence(std::memory_order_seq_cst);
603 INC_HAZPTR_STATS(seq_cst);
612 * hazptr_tc structures
615 /** hazptr_tc_entry */
617 FOLLY_ALWAYS_INLINE void hazptr_tc_entry::fill(hazptr_rec* hprec) {
619 DEBUG_PRINT(this << " " << hprec);
622 FOLLY_ALWAYS_INLINE hazptr_rec* hazptr_tc_entry::get() {
624 DEBUG_PRINT(this << " " << hprec);
628 inline void hazptr_tc_entry::evict() {
631 DEBUG_PRINT(this << " " << hprec);
636 FOLLY_ALWAYS_INLINE hazptr_rec* hazptr_tc::get() {
637 if (LIKELY(count_ != 0)) {
638 auto hprec = entry_[--count_].get();
639 DEBUG_PRINT(this << " " << hprec);
642 DEBUG_PRINT(this << " nullptr");
646 FOLLY_ALWAYS_INLINE bool hazptr_tc::put(hazptr_rec* hprec) {
647 if (LIKELY(count_ < HAZPTR_TC_SIZE)) {
648 entry_[count_++].fill(hprec);
649 DEBUG_PRINT(this << " " << count_ - 1);
655 /** hazptr_tc free functions */
657 FOLLY_ALWAYS_INLINE hazptr_rec* hazptr_tc_try_get() {
658 DEBUG_PRINT(TLS_UNINITIALIZED << TLS_ALIVE << TLS_DESTROYED);
659 DEBUG_PRINT(tls_state_);
660 if (LIKELY(tls_state_ == TLS_ALIVE)) {
661 DEBUG_PRINT(tls_state_);
662 return tls_tc_data_.get();
663 } else if (tls_state_ == TLS_UNINITIALIZED) {
665 return tls_tc_data_.get();
670 FOLLY_ALWAYS_INLINE bool hazptr_tc_try_put(hazptr_rec* hprec) {
671 DEBUG_PRINT(tls_state_);
672 if (LIKELY(tls_state_ == TLS_ALIVE)) {
673 DEBUG_PRINT(tls_state_);
674 return tls_tc_data_.put(hprec);
679 inline void hazptr_tc_init() {
681 auto& tc = tls_tc_data_;
684 for (int i = 0; i < HAZPTR_TC_SIZE; ++i) {
685 tc.entry_[i].hprec_ = nullptr;
689 inline void hazptr_tc_shutdown() {
690 auto& tc = tls_tc_data_;
692 for (int i = 0; i < tc.count_; ++i) {
693 tc.entry_[i].evict();
701 inline void hazptr_priv::push(hazptr_obj* obj) {
702 auto& domain = default_hazptr_domain();
703 obj->next_ = nullptr;
708 domain.objRetire(obj);
715 if (domain.reachedThreshold(rcount_)) {
720 inline void hazptr_priv::pushAllToDomain() {
721 auto& domain = default_hazptr_domain();
722 domain.pushRetired(head_, tail_, rcount_);
726 domain.tryBulkReclaim();
729 inline void hazptr_priv_init() {
730 auto& priv = tls_priv_data_;
732 priv.head_ = nullptr;
733 priv.tail_ = nullptr;
738 inline void hazptr_priv_shutdown() {
739 auto& priv = tls_priv_data_;
741 DCHECK(priv.active_);
742 priv.active_ = false;
744 priv.pushAllToDomain();
748 inline bool hazptr_priv_try_retire(hazptr_obj* obj) {
749 DEBUG_PRINT(tls_state_);
750 if (tls_state_ == TLS_ALIVE) {
751 DEBUG_PRINT(tls_state_);
752 tls_priv_data_.push(obj);
754 } else if (tls_state_ == TLS_UNINITIALIZED) {
755 DEBUG_PRINT(tls_state_);
757 tls_priv_data_.push(obj);
763 /** hazptr_tls_life */
765 inline void tls_life_odr_use() {
766 DEBUG_PRINT(tls_state_);
767 CHECK(tls_state_ == TLS_UNINITIALIZED);
768 auto volatile tlsOdrUse = &tls_life_;
769 CHECK(tlsOdrUse != nullptr);
770 DEBUG_PRINT(tlsOdrUse);
773 inline hazptr_tls_life::hazptr_tls_life() {
775 CHECK(tls_state_ == TLS_UNINITIALIZED);
778 tls_state_ = TLS_ALIVE;
781 inline hazptr_tls_life::~hazptr_tls_life() {
783 CHECK(tls_state_ == TLS_ALIVE);
784 hazptr_tc_shutdown();
785 hazptr_priv_shutdown();
786 tls_state_ = TLS_DESTROYED;
790 } // namespace hazptr