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 friend class hazptr_holder;
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 inline hazptr_holder::hazptr_holder(hazptr_domain& domain) {
156 hazptr_ = domain_->hazptrAcquire();
157 DEBUG_PRINT(this << " " << domain_ << " " << hazptr_);
158 if (hazptr_ == nullptr) { std::bad_alloc e; throw e; }
161 hazptr_holder::~hazptr_holder() {
163 domain_->hazptrRelease(hazptr_);
166 template <typename T>
167 inline bool hazptr_holder::try_protect(
169 const std::atomic<T*>& src) noexcept {
170 DEBUG_PRINT(this << " " << ptr << " " << &src);
172 /*** Full fence ***/ hazptr_mb::light();
173 T* p = src.load(std::memory_order_acquire);
182 template <typename T>
183 inline T* hazptr_holder::get_protected(const std::atomic<T*>& src) noexcept {
184 T* p = src.load(std::memory_order_relaxed);
185 while (!try_protect(p, src)) {}
186 DEBUG_PRINT(this << " " << p << " " << &src);
190 template <typename T>
191 inline void hazptr_holder::reset(const T* ptr) noexcept {
192 auto p = static_cast<hazptr_obj*>(const_cast<T*>(ptr));
193 DEBUG_PRINT(this << " " << ptr << " p:" << p);
197 inline void hazptr_holder::reset(std::nullptr_t) noexcept {
202 inline void hazptr_holder::swap(hazptr_holder& rhs) noexcept {
204 this << " " << this->hazptr_ << " " << this->domain_ << " -- "
205 << &rhs << " " << rhs.hazptr_ << " " << rhs.domain_);
206 std::swap(this->domain_, rhs.domain_);
207 std::swap(this->hazptr_, rhs.hazptr_);
210 inline void swap(hazptr_holder& lhs, hazptr_holder& rhs) noexcept {
214 ////////////////////////////////////////////////////////////////////////////////
216 // - Private storage of retired objects
217 // - Control of reclamation (when and by whom)
218 // - End-to-end lock-free implementation
220 /** Definition of default_hazptr_domain() */
221 inline hazptr_domain& default_hazptr_domain() {
222 static hazptr_domain d;
229 inline void hazptr_rec::set(const void* p) noexcept {
230 DEBUG_PRINT(this << " " << p);
231 hazptr_.store(p, std::memory_order_release);
234 inline const void* hazptr_rec::get() const noexcept {
235 auto p = hazptr_.load(std::memory_order_acquire);
236 DEBUG_PRINT(this << " " << p);
240 inline void hazptr_rec::clear() noexcept {
242 hazptr_.store(nullptr, std::memory_order_release);
245 inline bool hazptr_rec::isActive() noexcept {
246 return active_.load(std::memory_order_acquire);
249 inline bool hazptr_rec::tryAcquire() noexcept {
250 bool active = isActive();
252 active_.compare_exchange_strong(
253 active, true, std::memory_order_release, std::memory_order_relaxed)) {
260 inline void hazptr_rec::release() noexcept {
263 active_.store(false, std::memory_order_release);
268 inline const void* hazptr_obj::getObjPtr() const {
275 inline hazptr_domain::~hazptr_domain() {
277 { /* reclaim all remaining retired objects */
279 auto retired = retired_.exchange(nullptr);
281 for (auto p = retired; p; p = next) {
285 retired = retired_.exchange(nullptr);
288 { /* free all hazptr_rec-s */
290 for (auto p = hazptrs_.load(std::memory_order_acquire); p; p = next) {
294 hazptr_tc_guard g(hazptr_tc_lock());
296 auto tc = p->tc_.load(std::memory_order_acquire);
297 DCHECK(tc != nullptr);
302 CHECK(!p->isActive());
304 mr_->deallocate(static_cast<void*>(p), sizeof(hazptr_rec));
309 inline hazptr_rec* hazptr_domain::hazptrAcquire() {
311 hazptr_rec* hprec = hazptr_tc().get(this);
318 for (p = hazptrs_.load(std::memory_order_acquire); p; p = next) {
320 if (p->tryAcquire()) {
324 p = static_cast<hazptr_rec*>(mr_->allocate(sizeof(hazptr_rec)));
328 p->active_.store(true, std::memory_order_relaxed);
329 p->next_ = hazptrs_.load(std::memory_order_acquire);
330 while (!hazptrs_.compare_exchange_weak(
331 p->next_, p, std::memory_order_release, std::memory_order_acquire))
333 auto hcount = hcount_.fetch_add(1);
334 DEBUG_PRINT(this << " " << p << " " << sizeof(hazptr_rec) << " " << hcount);
338 inline void hazptr_domain::hazptrRelease(hazptr_rec* p) noexcept {
339 if (HAZPTR_TC && hazptr_tc().put(p, this)) {
342 DEBUG_PRINT(this << " " << p);
347 hazptr_domain::pushRetired(hazptr_obj* head, hazptr_obj* tail, int count) {
348 /*** Full fence ***/ hazptr_mb::light();
349 tail->next_ = retired_.load(std::memory_order_acquire);
350 while (!retired_.compare_exchange_weak(
353 std::memory_order_release,
354 std::memory_order_acquire)) {
356 return rcount_.fetch_add(count);
359 inline void hazptr_domain::objRetire(hazptr_obj* p) {
360 auto rcount = pushRetired(p, p, 1) + 1;
361 if (rcount >= HAZPTR_SCAN_THRESHOLD &&
362 rcount >= HAZPTR_SCAN_MULT * hcount_.load(std::memory_order_acquire)) {
367 inline void hazptr_domain::tryBulkReclaim() {
370 auto hcount = hcount_.load(std::memory_order_acquire);
371 auto rcount = rcount_.load(std::memory_order_acquire);
372 if (rcount < HAZPTR_SCAN_THRESHOLD || rcount < HAZPTR_SCAN_MULT * hcount) {
375 if (rcount_.compare_exchange_weak(
376 rcount, 0, std::memory_order_release, std::memory_order_relaxed)) {
383 inline void hazptr_domain::bulkReclaim() {
385 /*** Full fence ***/ hazptr_mb::heavy();
386 auto p = retired_.exchange(nullptr, std::memory_order_acquire);
387 auto h = hazptrs_.load(std::memory_order_acquire);
388 std::unordered_set<const void*> hs; // TODO lock-free alternative
389 for (; h; h = h->next_) {
393 hazptr_obj* retired = nullptr;
394 hazptr_obj* tail = nullptr;
396 for (; p; p = next) {
398 if (hs.count(p->getObjPtr()) == 0) {
399 DEBUG_PRINT(this << " " << p << " " << p->reclaim_);
404 if (tail == nullptr) {
411 pushRetired(retired, tail, rcount);
425 std::atomic<uint64_t> light_{0};
426 std::atomic<uint64_t> heavy_{0};
427 std::atomic<uint64_t> seq_cst_{0};
430 inline hazptr_stats::~hazptr_stats() {
431 DEBUG_PRINT(this << " light " << light_.load());
432 DEBUG_PRINT(this << " heavy " << heavy_.load());
433 DEBUG_PRINT(this << " seq_cst " << seq_cst_.load());
436 inline void hazptr_stats::light() {
438 /* atomic */ ++light_;
442 inline void hazptr_stats::heavy() {
444 /* atomic */ ++heavy_;
448 inline void hazptr_stats::seq_cst() {
450 /* atomic */ ++seq_cst_;
454 inline class hazptr_stats& hazptr_stats() {
455 static class hazptr_stats stats_;
456 DEBUG_PRINT(&stats_);
462 inline void hazptr_mb::light() {
465 folly::asymmetricLightBarrier();
466 hazptr_stats().light();
468 atomic_thread_fence(std::memory_order_seq_cst);
469 hazptr_stats().seq_cst();
473 inline void hazptr_mb::heavy() {
476 folly::asymmetricHeavyBarrier();
477 hazptr_stats().heavy();
479 atomic_thread_fence(std::memory_order_seq_cst);
480 hazptr_stats().seq_cst();
484 /** hazptr_tc - functions */
486 inline void hazptr_tc_entry::fill(hazptr_rec* hprec, hazptr_domain* domain) {
487 hprec_.store(hprec, std::memory_order_release);
488 domain_.store(domain, std::memory_order_release);
489 hprec->tc_.store(this, std::memory_order_release);
490 DEBUG_PRINT(this << " " << domain << " " << hprec);
493 inline hazptr_rec* hazptr_tc_entry::get(hazptr_domain* domain) {
494 if (domain == domain_.load(std::memory_order_acquire)) {
495 auto hprec = hprec_.load(std::memory_order_acquire);
497 hprec_.store(nullptr, std::memory_order_release);
498 DEBUG_PRINT(this << " " << domain << " " << hprec);
505 inline void hazptr_tc_entry::invalidate(hazptr_rec* hprec) {
506 DCHECK_EQ(hprec, hprec_);
507 hprec_.store(nullptr, std::memory_order_release);
508 domain_.store(nullptr, std::memory_order_release);
509 hprec->tc_.store(nullptr, std::memory_order_relaxed);
511 DEBUG_PRINT(this << " " << hprec);
514 inline void hazptr_tc_entry::evict() {
515 auto hprec = hprec_.load(std::memory_order_relaxed);
517 hazptr_tc_guard g(hazptr_tc_lock());
518 hprec = hprec_.load(std::memory_order_relaxed);
526 inline hazptr_tc::hazptr_tc() {
530 inline hazptr_tc::~hazptr_tc() {
532 for (int i = 0; i < HAZPTR_TC_SIZE; ++i) {
537 inline hazptr_rec* hazptr_tc::get(hazptr_domain* domain) {
538 for (int i = 0; i < HAZPTR_TC_SIZE; ++i) {
539 auto hprec = tc_[i].get(domain);
541 DEBUG_PRINT(this << " " << domain << " " << hprec);
545 DEBUG_PRINT(this << " " << domain << " nullptr");
549 inline bool hazptr_tc::put(hazptr_rec* hprec, hazptr_domain* domain) {
550 int other = HAZPTR_TC_SIZE;
551 for (int i = 0; i < HAZPTR_TC_SIZE; ++i) {
552 if (tc_[i].hprec_.load(std::memory_order_acquire) == nullptr) {
553 tc_[i].fill(hprec, domain);
554 DEBUG_PRINT(this << " " << i);
557 if (tc_[i].domain_.load(std::memory_order_relaxed) != domain) {
561 if (other < HAZPTR_TC_SIZE) {
563 tc_[other].fill(hprec, domain);
564 DEBUG_PRINT(this << " " << other);
570 inline class hazptr_tc& hazptr_tc() {
571 static thread_local class hazptr_tc tc;
576 inline std::mutex& hazptr_tc_lock() {
583 } // namespace hazptr