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 2
40 #ifndef HAZPTR_SCAN_MULT
41 #define HAZPTR_SCAN_MULT 2
44 #ifndef HAZPTR_SCAN_THRESHOLD
45 #define HAZPTR_SCAN_THRESHOLD 1000
50 #define HAZPTR_STATS false
53 #include <folly/experimental/AsymmetricMemoryBarrier.h>
54 #include <folly/experimental/hazptr/debug.h>
56 #include <mutex> // for thread caching
57 #include <unordered_set> // for hash set in bulk reclamation
63 * helper classes and functions
69 hazptr_stats& hazptr_stats();
81 class hazptr_tc_entry {
82 friend class hazptr_tc;
83 std::atomic<hazptr_rec*> hprec_{nullptr};
84 std::atomic<hazptr_domain*> domain_{nullptr};
87 void fill(hazptr_rec* hprec, hazptr_domain* domain);
88 hazptr_rec* get(hazptr_domain* domain);
89 void invalidate(hazptr_rec* hprec);
94 hazptr_tc_entry tc_[HAZPTR_TC_SIZE];
99 hazptr_rec* get(hazptr_domain* domain);
100 bool put(hazptr_rec* hprec, hazptr_domain* domain);
103 hazptr_tc& hazptr_tc();
105 std::mutex& hazptr_tc_lock();
107 using hazptr_tc_guard = std::lock_guard<std::mutex>;
115 constexpr hazptr_domain::hazptr_domain(memory_resource* mr) noexcept
118 /** hazptr_obj_base */
120 template <typename T, typename D>
121 inline void hazptr_obj_base<T, D>::retire(hazptr_domain& domain, D deleter) {
122 DEBUG_PRINT(this << " " << &domain);
123 deleter_ = std::move(deleter);
124 reclaim_ = [](hazptr_obj* p) {
125 auto hobp = static_cast<hazptr_obj_base*>(p);
126 auto obj = static_cast<T*>(hobp);
129 domain.objRetire(this);
135 friend class hazptr_domain;
136 friend class hazptr_tc_entry;
137 template <typename> friend class hazptr_owner;
139 std::atomic<const void*> hazptr_{nullptr};
140 hazptr_rec* next_{nullptr};
141 std::atomic<hazptr_tc_entry*> tc_{nullptr};
142 std::atomic<bool> active_{false};
144 void set(const void* p) noexcept;
145 const void* get() const noexcept;
146 void clear() noexcept;
147 bool isActive() noexcept;
148 bool tryAcquire() noexcept;
149 void release() noexcept;
154 template <typename T>
155 inline hazptr_owner<T>::hazptr_owner(hazptr_domain& domain) {
157 hazptr_ = domain_->hazptrAcquire();
158 DEBUG_PRINT(this << " " << domain_ << " " << hazptr_);
159 if (hazptr_ == nullptr) { std::bad_alloc e; throw e; }
162 template <typename T>
163 hazptr_owner<T>::~hazptr_owner() {
165 domain_->hazptrRelease(hazptr_);
168 template <typename T>
169 template <typename A>
170 inline bool hazptr_owner<T>::try_protect(T*& ptr, const A& src) noexcept {
172 std::is_same<decltype(std::declval<A>().load()), T*>::value,
173 "Return type of A::load() must be T*");
174 DEBUG_PRINT(this << " " << ptr << " " << &src);
176 /*** Full fence ***/ hazptr_mb::light();
177 T* p = src.load(std::memory_order_acquire);
186 template <typename T>
187 template <typename A>
188 inline T* hazptr_owner<T>::get_protected(const A& src) noexcept {
190 std::is_same<decltype(std::declval<A>().load()), T*>::value,
191 "Return type of A::load() must be T*");
192 T* p = src.load(std::memory_order_relaxed);
193 while (!try_protect(p, src)) {}
194 DEBUG_PRINT(this << " " << p << " " << &src);
198 template <typename T>
199 inline void hazptr_owner<T>::set(const T* ptr) noexcept {
200 auto p = static_cast<hazptr_obj*>(const_cast<T*>(ptr));
201 DEBUG_PRINT(this << " " << ptr << " p:" << p);
205 template <typename T>
206 inline void hazptr_owner<T>::clear() noexcept {
211 template <typename T>
212 inline void hazptr_owner<T>::swap(hazptr_owner<T>& rhs) noexcept {
214 this << " " << this->hazptr_ << " " << this->domain_ << " -- "
215 << &rhs << " " << rhs.hazptr_ << " " << rhs.domain_);
216 std::swap(this->domain_, rhs.domain_);
217 std::swap(this->hazptr_, rhs.hazptr_);
220 template <typename T>
221 inline void swap(hazptr_owner<T>& lhs, hazptr_owner<T>& rhs) noexcept {
225 ////////////////////////////////////////////////////////////////////////////////
227 // - Private storage of retired objects
228 // - Control of reclamation (when and by whom)
229 // - End-to-end lock-free implementation
231 /** Definition of default_hazptr_domain() */
232 inline hazptr_domain& default_hazptr_domain() {
233 static hazptr_domain d;
240 inline void hazptr_rec::set(const void* p) noexcept {
241 DEBUG_PRINT(this << " " << p);
242 hazptr_.store(p, std::memory_order_release);
245 inline const void* hazptr_rec::get() const noexcept {
246 auto p = hazptr_.load(std::memory_order_acquire);
247 DEBUG_PRINT(this << " " << p);
251 inline void hazptr_rec::clear() noexcept {
253 hazptr_.store(nullptr, std::memory_order_release);
256 inline bool hazptr_rec::isActive() noexcept {
257 return active_.load(std::memory_order_acquire);
260 inline bool hazptr_rec::tryAcquire() noexcept {
261 bool active = isActive();
263 active_.compare_exchange_strong(
264 active, true, std::memory_order_release, std::memory_order_relaxed)) {
271 inline void hazptr_rec::release() noexcept {
274 active_.store(false, std::memory_order_release);
279 inline const void* hazptr_obj::getObjPtr() const {
286 inline hazptr_domain::~hazptr_domain() {
288 { /* reclaim all remaining retired objects */
290 auto retired = retired_.exchange(nullptr);
292 for (auto p = retired; p; p = next) {
296 retired = retired_.exchange(nullptr);
299 { /* free all hazptr_rec-s */
301 for (auto p = hazptrs_.load(std::memory_order_acquire); p; p = next) {
305 hazptr_tc_guard g(hazptr_tc_lock());
307 auto tc = p->tc_.load(std::memory_order_acquire);
308 DCHECK(tc != nullptr);
313 CHECK(!p->isActive());
315 mr_->deallocate(static_cast<void*>(p), sizeof(hazptr_rec));
320 inline hazptr_rec* hazptr_domain::hazptrAcquire() {
322 hazptr_rec* hprec = hazptr_tc().get(this);
329 for (p = hazptrs_.load(std::memory_order_acquire); p; p = next) {
331 if (p->tryAcquire()) {
335 p = static_cast<hazptr_rec*>(mr_->allocate(sizeof(hazptr_rec)));
339 p->active_.store(true, std::memory_order_relaxed);
340 p->next_ = hazptrs_.load(std::memory_order_acquire);
341 while (!hazptrs_.compare_exchange_weak(
342 p->next_, p, std::memory_order_release, std::memory_order_acquire))
344 auto hcount = hcount_.fetch_add(1);
345 DEBUG_PRINT(this << " " << p << " " << sizeof(hazptr_rec) << " " << hcount);
349 inline void hazptr_domain::hazptrRelease(hazptr_rec* p) noexcept {
350 if (HAZPTR_TC && hazptr_tc().put(p, this)) {
353 DEBUG_PRINT(this << " " << p);
358 hazptr_domain::pushRetired(hazptr_obj* head, hazptr_obj* tail, int count) {
359 /*** Full fence ***/ hazptr_mb::light();
360 tail->next_ = retired_.load(std::memory_order_acquire);
361 while (!retired_.compare_exchange_weak(
364 std::memory_order_release,
365 std::memory_order_acquire)) {
367 return rcount_.fetch_add(count);
370 inline void hazptr_domain::objRetire(hazptr_obj* p) {
371 auto rcount = pushRetired(p, p, 1) + 1;
372 if (rcount >= HAZPTR_SCAN_THRESHOLD &&
373 rcount >= HAZPTR_SCAN_MULT * hcount_.load(std::memory_order_acquire)) {
378 inline void hazptr_domain::tryBulkReclaim() {
381 auto hcount = hcount_.load(std::memory_order_acquire);
382 auto rcount = rcount_.load(std::memory_order_acquire);
383 if (rcount < HAZPTR_SCAN_THRESHOLD || rcount < HAZPTR_SCAN_MULT * hcount) {
386 if (rcount_.compare_exchange_weak(
387 rcount, 0, std::memory_order_release, std::memory_order_relaxed)) {
394 inline void hazptr_domain::bulkReclaim() {
396 /*** Full fence ***/ hazptr_mb::heavy();
397 auto p = retired_.exchange(nullptr, std::memory_order_acquire);
398 auto h = hazptrs_.load(std::memory_order_acquire);
399 std::unordered_set<const void*> hs; // TODO lock-free alternative
400 for (; h; h = h->next_) {
404 hazptr_obj* retired = nullptr;
405 hazptr_obj* tail = nullptr;
407 for (; p; p = next) {
409 if (hs.count(p->getObjPtr()) == 0) {
410 DEBUG_PRINT(this << " " << p << " " << p->reclaim_);
415 if (tail == nullptr) {
422 pushRetired(retired, tail, rcount);
436 std::atomic<uint64_t> light_{0};
437 std::atomic<uint64_t> heavy_{0};
438 std::atomic<uint64_t> seq_cst_{0};
441 inline hazptr_stats::~hazptr_stats() {
442 DEBUG_PRINT(this << " light " << light_.load());
443 DEBUG_PRINT(this << " heavy " << heavy_.load());
444 DEBUG_PRINT(this << " seq_cst " << seq_cst_.load());
447 inline void hazptr_stats::light() {
449 /* atomic */ ++light_;
453 inline void hazptr_stats::heavy() {
455 /* atomic */ ++heavy_;
459 inline void hazptr_stats::seq_cst() {
461 /* atomic */ ++seq_cst_;
465 inline class hazptr_stats& hazptr_stats() {
466 static class hazptr_stats stats_;
467 DEBUG_PRINT(&stats_);
473 inline void hazptr_mb::light() {
476 folly::asymmetricLightBarrier();
477 hazptr_stats().light();
479 atomic_thread_fence(std::memory_order_seq_cst);
480 hazptr_stats().seq_cst();
484 inline void hazptr_mb::heavy() {
487 folly::asymmetricHeavyBarrier();
488 hazptr_stats().heavy();
490 atomic_thread_fence(std::memory_order_seq_cst);
491 hazptr_stats().seq_cst();
495 /** hazptr_tc - functions */
497 inline void hazptr_tc_entry::fill(hazptr_rec* hprec, hazptr_domain* domain) {
498 hprec_.store(hprec, std::memory_order_release);
499 domain_.store(domain, std::memory_order_release);
500 hprec->tc_.store(this, std::memory_order_release);
501 DEBUG_PRINT(this << " " << domain << " " << hprec);
504 inline hazptr_rec* hazptr_tc_entry::get(hazptr_domain* domain) {
505 if (domain == domain_.load(std::memory_order_acquire)) {
506 auto hprec = hprec_.load(std::memory_order_acquire);
508 hprec_.store(nullptr, std::memory_order_release);
509 DEBUG_PRINT(this << " " << domain << " " << hprec);
516 inline void hazptr_tc_entry::invalidate(hazptr_rec* hprec) {
517 DCHECK_EQ(hprec, hprec_);
518 hprec_.store(nullptr, std::memory_order_release);
519 domain_.store(nullptr, std::memory_order_release);
520 hprec->tc_.store(nullptr, std::memory_order_relaxed);
522 DEBUG_PRINT(this << " " << hprec);
525 inline void hazptr_tc_entry::evict() {
526 auto hprec = hprec_.load(std::memory_order_relaxed);
528 hazptr_tc_guard g(hazptr_tc_lock());
529 hprec = hprec_.load(std::memory_order_relaxed);
537 inline hazptr_tc::hazptr_tc() {
541 inline hazptr_tc::~hazptr_tc() {
543 for (int i = 0; i < HAZPTR_TC_SIZE; ++i) {
548 inline hazptr_rec* hazptr_tc::get(hazptr_domain* domain) {
549 for (int i = 0; i < HAZPTR_TC_SIZE; ++i) {
550 auto hprec = tc_[i].get(domain);
552 DEBUG_PRINT(this << " " << domain << " " << hprec);
556 DEBUG_PRINT(this << " " << domain << " nullptr");
560 inline bool hazptr_tc::put(hazptr_rec* hprec, hazptr_domain* domain) {
561 int other = HAZPTR_TC_SIZE;
562 for (int i = 0; i < HAZPTR_TC_SIZE; ++i) {
563 if (tc_[i].hprec_.load(std::memory_order_acquire) == nullptr) {
564 tc_[i].fill(hprec, domain);
565 DEBUG_PRINT(this << " " << i);
568 if (tc_[i].domain_.load(std::memory_order_relaxed) != domain) {
572 if (other < HAZPTR_TC_SIZE) {
574 tc_[other].fill(hprec, domain);
575 DEBUG_PRINT(this << " " << other);
581 inline class hazptr_tc& hazptr_tc() {
582 static thread_local class hazptr_tc tc;
587 inline std::mutex& hazptr_tc_lock() {
594 } // namespace hazptr