folly/experimental/hazptr/hazptr-impl.h

   1 /*
   2  * Copyright 2017 Facebook, Inc.
   3  *
   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
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  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.
  15  */
  16
  17 /* override-include-guard */
  18 #ifndef HAZPTR_H
  19 #error "This should only be included by hazptr.h"
  20 #endif
  21
  22 /* quality of implementation switches */
  23
  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.
  27
  28 #ifndef HAZPTR_AMB
  29 #define HAZPTR_AMB true
  30 #endif
  31
  32 #ifndef HAZPTR_TC
  33 #define HAZPTR_TC true
  34 #endif
  35
  36 #ifndef HAZPTR_TC_SIZE
  37 #define HAZPTR_TC_SIZE 10
  38 #endif
  39
  40 #ifndef HAZPTR_PRIV
  41 #define HAZPTR_PRIV true
  42 #endif
  43
  44 #ifndef HAZPTR_ONE_DOMAIN
  45 #define HAZPTR_ONE_DOMAIN false
  46 #endif
  47
  48 #ifndef HAZPTR_SCAN_MULT
  49 #define HAZPTR_SCAN_MULT 2
  50 #endif
  51
  52 #ifndef HAZPTR_SCAN_THRESHOLD
  53 #define HAZPTR_SCAN_THRESHOLD 1000
  54 #endif
  55
  56 /* stats switch */
  57 #ifndef HAZPTR_STATS
  58 #define HAZPTR_STATS false
  59 #endif
  60
  61 #include <folly/concurrency/CacheLocality.h>
  62 #include <folly/experimental/hazptr/debug.h>
  63 #include <folly/synchronization/AsymmetricMemoryBarrier.h>
  64
  65 #include <mutex> // for thread caching
  66 #include <unordered_set> // for hash set in bulk reclamation
  67
  68 namespace folly {
  69 namespace hazptr {
  70
  71 /**
  72  *  Helper classes and functions
  73  */
  74
  75 /** hazptr_stats */
  76
  77 class hazptr_stats;
  78
  79 #if HAZPTR_STATS
  80 #define INC_HAZPTR_STATS(x) hazptr_stats_.x()
  81 #else
  82 #define INC_HAZPTR_STATS(x)
  83 #endif
  84
  85 /** hazptr_mb */
  86
  87 class hazptr_mb {
  88  public:
  89   static void light();
  90   static void heavy();
  91 };
  92
  93 /**
  94  *  TLS structures
  95  */
  96
  97 /** TLS life state */
  98
  99 enum hazptr_tls_state { TLS_ALIVE, TLS_UNINITIALIZED, TLS_DESTROYED };
 100
 101 /** hazptr_tc structures
 102  *  Thread caching of hazptr_rec-s that belong to the default domain.
 103  */
 104
 105 struct hazptr_tc_entry {
 106   hazptr_rec* hprec_;
 107
 108   void fill(hazptr_rec* hprec);
 109   hazptr_rec* get();
 110   void evict();
 111 };
 112
 113 static_assert(
 114     std::is_trivial<hazptr_tc_entry>::value,
 115     "hazptr_tc_entry must be trivial"
 116     " to avoid a branch to check initialization");
 117
 118 struct hazptr_tc {
 119   hazptr_tc_entry entry_[HAZPTR_TC_SIZE];
 120   size_t count_;
 121   bool local_; // for debug mode only
 122
 123  public:
 124   hazptr_tc_entry& operator[](size_t i);
 125   hazptr_rec* get();
 126   bool put(hazptr_rec* hprec);
 127   size_t count();
 128 };
 129
 130 static_assert(
 131     std::is_trivial<hazptr_tc>::value,
 132     "hazptr_tc must be trivial to avoid a branch to check initialization");
 133
 134 hazptr_tc* hazptr_tc_tls();
 135 void hazptr_tc_init();
 136 void hazptr_tc_shutdown();
 137 hazptr_rec* hazptr_tc_try_get();
 138 bool hazptr_tc_try_put(hazptr_rec* hprec);
 139
 140 /** hazptr_priv structures
 141  *  Thread private lists of retired objects that belong to the default domain.
 142  */
 143
 144 struct hazptr_priv {
 145   hazptr_obj* head_;
 146   hazptr_obj* tail_;
 147   int rcount_;
 148   bool active_;
 149
 150   void push(hazptr_obj* obj);
 151   void pushAllToDomain();
 152 };
 153
 154 static_assert(
 155     std::is_trivial<hazptr_priv>::value,
 156     "hazptr_priv must be trivial to avoid a branch to check initialization");
 157
 158 void hazptr_priv_init();
 159 void hazptr_priv_shutdown();
 160 bool hazptr_priv_try_retire(hazptr_obj* obj);
 161
 162 /** hazptr_tls_life */
 163
 164 struct hazptr_tls_life {
 165   hazptr_tls_life();
 166   ~hazptr_tls_life();
 167 };
 168
 169 void tls_life_odr_use();
 170
 171 /** tls globals */
 172
 173 extern thread_local hazptr_tls_state tls_state_;
 174 extern thread_local hazptr_tc tls_tc_data_;
 175 extern thread_local hazptr_priv tls_priv_data_;
 176 extern thread_local hazptr_tls_life tls_life_; // last
 177
 178 /**
 179  *  hazptr_domain
 180  */
 181
 182 inline constexpr hazptr_domain::hazptr_domain(memory_resource* mr) noexcept
 183     : mr_(mr) {}
 184
 185 /**
 186  *  hazptr_obj_base
 187  */
 188
 189 template <typename T, typename D>
 190 inline void hazptr_obj_base<T, D>::retire(hazptr_domain& domain, D deleter) {
 191   DEBUG_PRINT(this << " " << &domain);
 192   deleter_ = std::move(deleter);
 193   reclaim_ = [](hazptr_obj* p) {
 194     auto hobp = static_cast<hazptr_obj_base*>(p);
 195     auto obj = static_cast<T*>(hobp);
 196     hobp->deleter_(obj);
 197   };
 198   if (HAZPTR_PRIV &&
 199       (HAZPTR_ONE_DOMAIN || (&domain == &default_hazptr_domain()))) {
 200     if (hazptr_priv_try_retire(this)) {
 201       return;
 202     }
 203   }
 204   domain.objRetire(this);
 205 }
 206
 207 /**
 208  *  hazptr_obj_base_refcounted
 209  */
 210
 211 template <typename T, typename D>
 212 inline void hazptr_obj_base_refcounted<T, D>::retire(
 213     hazptr_domain& domain,
 214     D deleter) {
 215   DEBUG_PRINT(this << " " << &domain);
 216   deleter_ = std::move(deleter);
 217   reclaim_ = [](hazptr_obj* p) {
 218     auto hrobp = static_cast<hazptr_obj_base_refcounted*>(p);
 219     if (hrobp->release_ref()) {
 220       auto obj = static_cast<T*>(hrobp);
 221       hrobp->deleter_(obj);
 222     }
 223   };
 224   if (HAZPTR_PRIV &&
 225       (HAZPTR_ONE_DOMAIN || (&domain == &default_hazptr_domain()))) {
 226     if (hazptr_priv_try_retire(this)) {
 227       return;
 228     }
 229   }
 230   domain.objRetire(this);
 231 }
 232
 233 template <typename T, typename D>
 234 inline void hazptr_obj_base_refcounted<T, D>::acquire_ref() {
 235   DEBUG_PRINT(this);
 236   auto oldval = refcount_.fetch_add(1);
 237   DCHECK(oldval >= 0);
 238 }
 239
 240 template <typename T, typename D>
 241 inline void hazptr_obj_base_refcounted<T, D>::acquire_ref_safe() {
 242   DEBUG_PRINT(this);
 243   auto oldval = refcount_.load(std::memory_order_acquire);
 244   DCHECK(oldval >= 0);
 245   refcount_.store(oldval + 1, std::memory_order_release);
 246 }
 247
 248 template <typename T, typename D>
 249 inline bool hazptr_obj_base_refcounted<T, D>::release_ref() {
 250   DEBUG_PRINT(this);
 251   auto oldval = refcount_.load(std::memory_order_acquire);
 252   if (oldval > 0) {
 253     oldval = refcount_.fetch_sub(1);
 254   } else {
 255     if (kIsDebug) {
 256       refcount_.store(-1);
 257     }
 258   }
 259   DEBUG_PRINT(this << " " << oldval);
 260   DCHECK(oldval >= 0);
 261   return oldval == 0;
 262 }
 263
 264 /**
 265  *  hazptr_rec
 266  */
 267
 268 class hazptr_rec {
 269   friend class hazptr_domain;
 270   friend class hazptr_holder;
 271   friend struct hazptr_tc_entry;
 272
 273   FOLLY_ALIGN_TO_AVOID_FALSE_SHARING
 274   std::atomic<const void*> hazptr_{nullptr};
 275   hazptr_rec* next_{nullptr};
 276   std::atomic<bool> active_{false};
 277
 278   void set(const void* p) noexcept;
 279   const void* get() const noexcept;
 280   void clear() noexcept;
 281   bool isActive() noexcept;
 282   bool tryAcquire() noexcept;
 283   void release() noexcept;
 284 };
 285
 286 /**
 287  *  hazptr_holder
 288  */
 289
 290 FOLLY_ALWAYS_INLINE hazptr_holder::hazptr_holder(hazptr_domain& domain) {
 291   domain_ = &domain;
 292   if (LIKELY(
 293           HAZPTR_TC &&
 294           (HAZPTR_ONE_DOMAIN || &domain == &default_hazptr_domain()))) {
 295     auto hprec = hazptr_tc_try_get();
 296     if (LIKELY(hprec != nullptr)) {
 297       hazptr_ = hprec;
 298       DEBUG_PRINT(this << " " << domain_ << " " << hazptr_);
 299       return;
 300     }
 301   }
 302   hazptr_ = domain_->hazptrAcquire();
 303   DEBUG_PRINT(this << " " << domain_ << " " << hazptr_);
 304   if (hazptr_ == nullptr) { std::bad_alloc e; throw e; }
 305 }
 306
 307 FOLLY_ALWAYS_INLINE hazptr_holder::hazptr_holder(std::nullptr_t) noexcept {
 308   domain_ = nullptr;
 309   hazptr_ = nullptr;
 310   DEBUG_PRINT(this << " " << domain_ << " " << hazptr_);
 311 }
 312
 313 FOLLY_ALWAYS_INLINE hazptr_holder::~hazptr_holder() {
 314   DEBUG_PRINT(this);
 315   if (LIKELY(hazptr_ != nullptr)) {
 316     hazptr_->clear();
 317     if (LIKELY(
 318             HAZPTR_TC &&
 319             (HAZPTR_ONE_DOMAIN || domain_ == &default_hazptr_domain()))) {
 320       if (LIKELY(hazptr_tc_try_put(hazptr_))) {
 321         return;
 322       }
 323     }
 324     domain_->hazptrRelease(hazptr_);
 325   }
 326 }
 327
 328 FOLLY_ALWAYS_INLINE hazptr_holder::hazptr_holder(hazptr_holder&& rhs) noexcept {
 329   domain_ = rhs.domain_;
 330   hazptr_ = rhs.hazptr_;
 331   rhs.domain_ = nullptr;
 332   rhs.hazptr_ = nullptr;
 333 }
 334
 335 FOLLY_ALWAYS_INLINE
 336 hazptr_holder& hazptr_holder::operator=(hazptr_holder&& rhs) noexcept {
 337   /* Self-move is a no-op.  */
 338   if (LIKELY(this != &rhs)) {
 339     this->~hazptr_holder();
 340     new (this) hazptr_holder(std::move(rhs));
 341   }
 342   return *this;
 343 }
 344
 345 template <typename T>
 346 FOLLY_ALWAYS_INLINE bool hazptr_holder::try_protect(
 347     T*& ptr,
 348     const std::atomic<T*>& src) noexcept {
 349   return try_protect(ptr, src, [](T* t) { return t; });
 350 }
 351
 352 template <typename T, typename Func>
 353 FOLLY_ALWAYS_INLINE bool hazptr_holder::try_protect(
 354     T*& ptr,
 355     const std::atomic<T*>& src,
 356     Func f) noexcept {
 357   DEBUG_PRINT(this << " " << ptr << " " << &src);
 358   reset(f(ptr));
 359   /*** Full fence ***/ hazptr_mb::light();
 360   T* p = src.load(std::memory_order_acquire);
 361   if (UNLIKELY(p != ptr)) {
 362     ptr = p;
 363     reset();
 364     return false;
 365   }
 366   return true;
 367 }
 368
 369 template <typename T>
 370 FOLLY_ALWAYS_INLINE T* hazptr_holder::get_protected(
 371     const std::atomic<T*>& src) noexcept {
 372   return get_protected(src, [](T* t) { return t; });
 373 }
 374
 375 template <typename T, typename Func>
 376 FOLLY_ALWAYS_INLINE T* hazptr_holder::get_protected(
 377     const std::atomic<T*>& src,
 378     Func f) noexcept {
 379   T* p = src.load(std::memory_order_relaxed);
 380   while (!try_protect(p, src, f)) {
 381   }
 382   DEBUG_PRINT(this << " " << p << " " << &src);
 383   return p;
 384 }
 385
 386 template <typename T>
 387 FOLLY_ALWAYS_INLINE void hazptr_holder::reset(const T* ptr) noexcept {
 388   auto p = static_cast<hazptr_obj*>(const_cast<T*>(ptr));
 389   DEBUG_PRINT(this << " " << ptr << " p:" << p);
 390   DCHECK(hazptr_); // UB if *this is empty
 391   hazptr_->set(p);
 392 }
 393
 394 FOLLY_ALWAYS_INLINE void hazptr_holder::reset(std::nullptr_t) noexcept {
 395   DEBUG_PRINT(this);
 396   DCHECK(hazptr_); // UB if *this is empty
 397   hazptr_->clear();
 398 }
 399
 400 FOLLY_ALWAYS_INLINE void hazptr_holder::swap(hazptr_holder& rhs) noexcept {
 401   DEBUG_PRINT(
 402     this << " " <<  this->hazptr_ << " " << this->domain_ << " -- "
 403     << &rhs << " " << rhs.hazptr_ << " " << rhs.domain_);
 404   if (!HAZPTR_ONE_DOMAIN) {
 405     std::swap(this->domain_, rhs.domain_);
 406   }
 407   std::swap(this->hazptr_, rhs.hazptr_);
 408 }
 409
 410 FOLLY_ALWAYS_INLINE void swap(hazptr_holder& lhs, hazptr_holder& rhs) noexcept {
 411   lhs.swap(rhs);
 412 }
 413
 414 /**
 415  *  hazptr_array
 416  */
 417
 418 template <size_t M>
 419 FOLLY_ALWAYS_INLINE hazptr_array<M>::hazptr_array() {
 420   auto h = reinterpret_cast<hazptr_holder*>(&raw_);
 421   if (HAZPTR_TC) {
 422     auto ptc = hazptr_tc_tls();
 423     if (LIKELY(ptc != nullptr)) {
 424       auto& tc = *ptc;
 425       auto count = tc.count();
 426       if (M <= count) {
 427         size_t offset = count - M;
 428         for (size_t i = 0; i < M; ++i) {
 429           auto hprec = tc[offset + i].hprec_;
 430           DCHECK(hprec != nullptr);
 431           DEBUG_PRINT(i << " " << &h[i]);
 432           new (&h[i]) hazptr_holder(nullptr);
 433           h[i].hazptr_ = hprec;
 434           DEBUG_PRINT(
 435               i << " " << &h[i] << " " << h[i].domain_ << " " << h[i].hazptr_);
 436         }
 437         tc.count_ = offset;
 438         return;
 439       }
 440     }
 441   }
 442   // slow path
 443   for (size_t i = 0; i < M; ++i) {
 444     new (&h[i]) hazptr_holder;
 445     DEBUG_PRINT(
 446         i << " " << &h[i] << " " << h[i].domain_ << " " << h[i].hazptr_);
 447   }
 448 }
 449
 450 template <size_t M>
 451 FOLLY_ALWAYS_INLINE hazptr_array<M>::hazptr_array(
 452     hazptr_array&& other) noexcept {
 453   DEBUG_PRINT(this << " " << M << " " << &other);
 454   auto h = reinterpret_cast<hazptr_holder*>(&raw_);
 455   auto hother = reinterpret_cast<hazptr_holder*>(&other.raw_);
 456   for (size_t i = 0; i < M; ++i) {
 457     new (&h[i]) hazptr_holder(std::move(hother[i]));
 458     DEBUG_PRINT(i << " " << &h[i] << " " << &hother[i]);
 459   }
 460   empty_ = other.empty_;
 461   other.empty_ = true;
 462 }
 463
 464 template <size_t M>
 465 FOLLY_ALWAYS_INLINE hazptr_array<M>::hazptr_array(std::nullptr_t) noexcept {
 466   DEBUG_PRINT(this << " " << M);
 467   auto h = reinterpret_cast<hazptr_holder*>(&raw_);
 468   for (size_t i = 0; i < M; ++i) {
 469     new (&h[i]) hazptr_holder(nullptr);
 470     DEBUG_PRINT(i << " " << &h[i]);
 471   }
 472   empty_ = true;
 473 }
 474
 475 template <size_t M>
 476 FOLLY_ALWAYS_INLINE hazptr_array<M>::~hazptr_array() {
 477   if (empty_) {
 478     return;
 479   }
 480   auto h = reinterpret_cast<hazptr_holder*>(&raw_);
 481   if (HAZPTR_TC) {
 482     auto ptc = hazptr_tc_tls();
 483     if (LIKELY(ptc != nullptr)) {
 484       auto& tc = *ptc;
 485       auto count = tc.count();
 486       if ((M <= HAZPTR_TC_SIZE) && (count + M <= HAZPTR_TC_SIZE)) {
 487         for (size_t i = 0; i < M; ++i) {
 488           tc[count + i].hprec_ = h[i].hazptr_;
 489           DEBUG_PRINT(i << " " << &h[i]);
 490           new (&h[i]) hazptr_holder(nullptr);
 491           DEBUG_PRINT(
 492               i << " " << &h[i] << " " << h[i].domain_ << " " << h[i].hazptr_);
 493         }
 494         tc.count_ = count + M;
 495         return;
 496       }
 497     }
 498   }
 499   // slow path
 500   for (size_t i = 0; i < M; ++i) {
 501     h[i].~hazptr_holder();
 502   }
 503 }
 504
 505 template <size_t M>
 506 FOLLY_ALWAYS_INLINE hazptr_array<M>& hazptr_array<M>::operator=(
 507     hazptr_array&& other) noexcept {
 508   DEBUG_PRINT(this << " " << M << " " << &other);
 509   auto h = reinterpret_cast<hazptr_holder*>(&raw_);
 510   for (size_t i = 0; i < M; ++i) {
 511     h[i] = std::move(other[i]);
 512     DEBUG_PRINT(i << " " << &h[i] << " " << &other[i]);
 513   }
 514   empty_ = other.empty_;
 515   other.empty_ = true;
 516   return *this;
 517 }
 518
 519 template <size_t M>
 520 FOLLY_ALWAYS_INLINE hazptr_holder& hazptr_array<M>::operator[](
 521     size_t i) noexcept {
 522   auto h = reinterpret_cast<hazptr_holder*>(&raw_);
 523   DCHECK(i < M);
 524   return h[i];
 525 }
 526
 527 /**
 528  *  hazptr_local
 529  */
 530
 531 template <size_t M>
 532 FOLLY_ALWAYS_INLINE hazptr_local<M>::hazptr_local() {
 533   auto h = reinterpret_cast<hazptr_holder*>(&raw_);
 534   if (HAZPTR_TC) {
 535     auto ptc = hazptr_tc_tls();
 536     if (LIKELY(ptc != nullptr)) {
 537       auto& tc = *ptc;
 538       auto count = tc.count();
 539       if (M <= count) {
 540         if (kIsDebug) {
 541           DCHECK(!tc.local_);
 542           tc.local_ = true;
 543         }
 544         // Fast path
 545         for (size_t i = 0; i < M; ++i) {
 546           auto hprec = tc[i].hprec_;
 547           DCHECK(hprec != nullptr);
 548           DEBUG_PRINT(i << " " << &h[i]);
 549           new (&h[i]) hazptr_holder(nullptr);
 550           h[i].hazptr_ = hprec;
 551           DEBUG_PRINT(
 552               i << " " << &h[i] << " " << h[i].domain_ << " " << h[i].hazptr_);
 553         }
 554         return;
 555       }
 556     }
 557   }
 558   // Slow path
 559   need_destruct_ = true;
 560   for (size_t i = 0; i < M; ++i) {
 561     new (&h[i]) hazptr_holder;
 562     DEBUG_PRINT(
 563         i << " " << &h[i] << " " << h[i].domain_ << " " << h[i].hazptr_);
 564   }
 565 }
 566
 567 template <size_t M>
 568 FOLLY_ALWAYS_INLINE hazptr_local<M>::~hazptr_local() {
 569   if (LIKELY(!need_destruct_)) {
 570     if (kIsDebug) {
 571       auto ptc = hazptr_tc_tls();
 572       DCHECK(ptc != nullptr);
 573       auto& tc = *ptc;
 574       DCHECK(tc.local_);
 575       tc.local_ = false;
 576     }
 577     return;
 578   }
 579   // Slow path
 580   auto h = reinterpret_cast<hazptr_holder*>(&raw_);
 581   for (size_t i = 0; i < M; ++i) {
 582     h[i].~hazptr_holder();
 583   }
 584 }
 585
 586 template <size_t M>
 587 FOLLY_ALWAYS_INLINE hazptr_holder& hazptr_local<M>::operator[](
 588     size_t i) noexcept {
 589   auto h = reinterpret_cast<hazptr_holder*>(&raw_);
 590   DCHECK(i < M);
 591   return h[i];
 592 }
 593
 594 ////////////////////////////////////////////////////////////////////////////////
 595 // [TODO]:
 596 // - Control of reclamation (when and by whom)
 597 // - End-to-end lock-free implementation
 598
 599 /** Definition of default_hazptr_domain() */
 600
 601 FOLLY_ALWAYS_INLINE hazptr_domain& default_hazptr_domain() {
 602   DEBUG_PRINT(&default_domain_);
 603   return default_domain_;
 604 }
 605
 606 template <typename T, typename D>
 607 FOLLY_ALWAYS_INLINE void hazptr_retire(T* obj, D reclaim) {
 608   default_hazptr_domain().retire(obj, std::move(reclaim));
 609 }
 610
 611 /** hazptr_rec */
 612
 613 FOLLY_ALWAYS_INLINE void hazptr_rec::set(const void* p) noexcept {
 614   DEBUG_PRINT(this << " " << p);
 615   hazptr_.store(p, std::memory_order_release);
 616 }
 617
 618 inline const void* hazptr_rec::get() const noexcept {
 619   auto p = hazptr_.load(std::memory_order_acquire);
 620   DEBUG_PRINT(this << " " << p);
 621   return p;
 622 }
 623
 624 FOLLY_ALWAYS_INLINE void hazptr_rec::clear() noexcept {
 625   DEBUG_PRINT(this);
 626   hazptr_.store(nullptr, std::memory_order_release);
 627 }
 628
 629 inline bool hazptr_rec::isActive() noexcept {
 630   return active_.load(std::memory_order_acquire);
 631 }
 632
 633 inline bool hazptr_rec::tryAcquire() noexcept {
 634   bool active = isActive();
 635   if (!active &&
 636       active_.compare_exchange_strong(
 637           active, true, std::memory_order_release, std::memory_order_relaxed)) {
 638     DEBUG_PRINT(this);
 639     return true;
 640   }
 641   return false;
 642 }
 643
 644 inline void hazptr_rec::release() noexcept {
 645   DEBUG_PRINT(this);
 646   active_.store(false, std::memory_order_release);
 647 }
 648
 649 /** hazptr_obj */
 650
 651 inline const void* hazptr_obj::getObjPtr() const {
 652   DEBUG_PRINT(this);
 653   return this;
 654 }
 655
 656 /** hazptr_domain */
 657
 658 template <typename T, typename D>
 659 void hazptr_domain::retire(T* obj, D reclaim) {
 660   struct hazptr_retire_node : hazptr_obj {
 661     std::unique_ptr<T, D> obj_;
 662
 663     hazptr_retire_node(T* obj, D reclaim) : obj_{obj, std::move(reclaim)} {}
 664   };
 665
 666   auto node = new hazptr_retire_node(obj, std::move(reclaim));
 667   node->reclaim_ = [](hazptr_obj* p) {
 668     delete static_cast<hazptr_retire_node*>(p);
 669   };
 670   objRetire(node);
 671 }
 672
 673 inline hazptr_domain::~hazptr_domain() {
 674   DEBUG_PRINT(this);
 675   { /* reclaim all remaining retired objects */
 676     hazptr_obj* next;
 677     auto retired = retired_.exchange(nullptr);
 678     while (retired) {
 679       for (auto p = retired; p; p = next) {
 680         next = p->next_;
 681         DEBUG_PRINT(this << " " << p << " " << p->reclaim_);
 682         (*(p->reclaim_))(p);
 683       }
 684       retired = retired_.exchange(nullptr);
 685     }
 686   }
 687   /* Leak the data for the default domain to avoid destruction order
 688    * issues with thread caches.
 689    */
 690   if (this != &default_hazptr_domain()) {
 691     /* free all hazptr_rec-s */
 692     hazptr_rec* next;
 693     for (auto p = hazptrs_.load(std::memory_order_acquire); p; p = next) {
 694       next = p->next_;
 695       DCHECK(!p->isActive());
 696       mr_->deallocate(static_cast<void*>(p), sizeof(hazptr_rec));
 697     }
 698   }
 699 }
 700
 701 inline hazptr_rec* hazptr_domain::hazptrAcquire() {
 702   hazptr_rec* p;
 703   hazptr_rec* next;
 704   for (p = hazptrs_.load(std::memory_order_acquire); p; p = next) {
 705     next = p->next_;
 706     if (p->tryAcquire()) {
 707       return p;
 708     }
 709   }
 710   p = static_cast<hazptr_rec*>(mr_->allocate(sizeof(hazptr_rec)));
 711   DEBUG_PRINT(this << " " << p << " " << sizeof(hazptr_rec));
 712   if (p == nullptr) {
 713     return nullptr;
 714   }
 715   p->active_.store(true, std::memory_order_relaxed);
 716   p->next_ = hazptrs_.load(std::memory_order_acquire);
 717   while (!hazptrs_.compare_exchange_weak(
 718       p->next_, p, std::memory_order_release, std::memory_order_acquire)) {
 719     /* keep trying */;
 720   }
 721   auto hcount = hcount_.fetch_add(1);
 722   DEBUG_PRINT(this << " " << p << " " << sizeof(hazptr_rec) << " " << hcount);
 723   return p;
 724 }
 725
 726 inline void hazptr_domain::hazptrRelease(hazptr_rec* p) noexcept {
 727   DEBUG_PRINT(this << " " << p);
 728   p->release();
 729 }
 730
 731 inline int
 732 hazptr_domain::pushRetired(hazptr_obj* head, hazptr_obj* tail, int count) {
 733   /*** Full fence ***/ hazptr_mb::light();
 734   tail->next_ = retired_.load(std::memory_order_acquire);
 735   while (!retired_.compare_exchange_weak(
 736       tail->next_,
 737       head,
 738       std::memory_order_release,
 739       std::memory_order_acquire)) {
 740   }
 741   return rcount_.fetch_add(count) + count;
 742 }
 743
 744 inline bool hazptr_domain::reachedThreshold(int rcount) {
 745   return (
 746       rcount >= HAZPTR_SCAN_THRESHOLD &&
 747       rcount >= HAZPTR_SCAN_MULT * hcount_.load(std::memory_order_acquire));
 748 }
 749
 750 inline void hazptr_domain::objRetire(hazptr_obj* p) {
 751   auto rcount = pushRetired(p, p, 1);
 752   if (reachedThreshold(rcount)) {
 753     tryBulkReclaim();
 754   }
 755 }
 756
 757 inline void hazptr_domain::tryBulkReclaim() {
 758   DEBUG_PRINT(this);
 759   do {
 760     auto hcount = hcount_.load(std::memory_order_acquire);
 761     auto rcount = rcount_.load(std::memory_order_acquire);
 762     if (rcount < HAZPTR_SCAN_THRESHOLD || rcount < HAZPTR_SCAN_MULT * hcount) {
 763       return;
 764     }
 765     if (rcount_.compare_exchange_weak(
 766             rcount, 0, std::memory_order_release, std::memory_order_relaxed)) {
 767       break;
 768     }
 769   } while (true);
 770   bulkReclaim();
 771 }
 772
 773 inline void hazptr_domain::bulkReclaim() {
 774   DEBUG_PRINT(this);
 775   /*** Full fence ***/ hazptr_mb::heavy();
 776   auto p = retired_.exchange(nullptr, std::memory_order_acquire);
 777   auto h = hazptrs_.load(std::memory_order_acquire);
 778   std::unordered_set<const void*> hs; // TODO lock-free alternative
 779   for (; h; h = h->next_) {
 780     hs.insert(h->get());
 781   }
 782   int rcount = 0;
 783   hazptr_obj* retired = nullptr;
 784   hazptr_obj* tail = nullptr;
 785   hazptr_obj* next;
 786   for (; p; p = next) {
 787     next = p->next_;
 788     if (hs.count(p->getObjPtr()) == 0) {
 789       DEBUG_PRINT(this << " " << p << " " << p->reclaim_);
 790       (*(p->reclaim_))(p);
 791     } else {
 792       p->next_ = retired;
 793       retired = p;
 794       if (tail == nullptr) {
 795         tail = p;
 796       }
 797       ++rcount;
 798     }
 799   }
 800   if (tail) {
 801     pushRetired(retired, tail, rcount);
 802   }
 803 }
 804
 805 /** hazptr_stats */
 806
 807 class hazptr_stats {
 808  public:
 809   ~hazptr_stats();
 810   void light();
 811   void heavy();
 812   void seq_cst();
 813
 814  private:
 815   std::atomic<uint64_t> light_{0};
 816   std::atomic<uint64_t> heavy_{0};
 817   std::atomic<uint64_t> seq_cst_{0};
 818 };
 819
 820 extern hazptr_stats hazptr_stats_;
 821
 822 inline hazptr_stats::~hazptr_stats() {
 823   DEBUG_PRINT(this << " light " << light_.load());
 824   DEBUG_PRINT(this << " heavy " << heavy_.load());
 825   DEBUG_PRINT(this << " seq_cst " << seq_cst_.load());
 826 }
 827
 828 FOLLY_ALWAYS_INLINE void hazptr_stats::light() {
 829   if (HAZPTR_STATS) {
 830     /* atomic */ ++light_;
 831   }
 832 }
 833
 834 inline void hazptr_stats::heavy() {
 835   if (HAZPTR_STATS) {
 836     /* atomic */ ++heavy_;
 837   }
 838 }
 839
 840 inline void hazptr_stats::seq_cst() {
 841   if (HAZPTR_STATS) {
 842     /* atomic */ ++seq_cst_;
 843   }
 844 }
 845
 846 /** hazptr_mb */
 847
 848 FOLLY_ALWAYS_INLINE void hazptr_mb::light() {
 849   DEBUG_PRINT("");
 850   if (HAZPTR_AMB) {
 851     folly::asymmetricLightBarrier();
 852     INC_HAZPTR_STATS(light);
 853   } else {
 854     atomic_thread_fence(std::memory_order_seq_cst);
 855     INC_HAZPTR_STATS(seq_cst);
 856   }
 857 }
 858
 859 inline void hazptr_mb::heavy() {
 860   DEBUG_PRINT("");
 861   if (HAZPTR_AMB) {
 862     folly::asymmetricHeavyBarrier(AMBFlags::EXPEDITED);
 863     INC_HAZPTR_STATS(heavy);
 864   } else {
 865     atomic_thread_fence(std::memory_order_seq_cst);
 866     INC_HAZPTR_STATS(seq_cst);
 867   }
 868 }
 869
 870 /**
 871  *  TLS structures
 872  */
 873
 874 /**
 875  *  hazptr_tc structures
 876  */
 877
 878 /** hazptr_tc_entry */
 879
 880 FOLLY_ALWAYS_INLINE void hazptr_tc_entry::fill(hazptr_rec* hprec) {
 881   hprec_ = hprec;
 882   DEBUG_PRINT(this << " " << hprec);
 883 }
 884
 885 FOLLY_ALWAYS_INLINE hazptr_rec* hazptr_tc_entry::get() {
 886   auto hprec = hprec_;
 887   DEBUG_PRINT(this << " " << hprec);
 888   return hprec;
 889 }
 890
 891 inline void hazptr_tc_entry::evict() {
 892   auto hprec = hprec_;
 893   hprec->release();
 894   DEBUG_PRINT(this << " " << hprec);
 895 }
 896
 897 /** hazptr_tc */
 898
 899 FOLLY_ALWAYS_INLINE hazptr_tc_entry& hazptr_tc::operator[](size_t i) {
 900   DCHECK(i <= HAZPTR_TC_SIZE);
 901   return entry_[i];
 902 }
 903
 904 FOLLY_ALWAYS_INLINE hazptr_rec* hazptr_tc::get() {
 905   if (LIKELY(count_ != 0)) {
 906     auto hprec = entry_[--count_].get();
 907     DEBUG_PRINT(this << " " << hprec);
 908     return hprec;
 909   }
 910   DEBUG_PRINT(this << " nullptr");
 911   return nullptr;
 912 }
 913
 914 FOLLY_ALWAYS_INLINE bool hazptr_tc::put(hazptr_rec* hprec) {
 915   if (LIKELY(count_ < HAZPTR_TC_SIZE)) {
 916     entry_[count_++].fill(hprec);
 917     DEBUG_PRINT(this << " " << count_ - 1);
 918     return true;
 919   }
 920   return false;
 921 }
 922
 923 FOLLY_ALWAYS_INLINE size_t hazptr_tc::count() {
 924   return count_;
 925 }
 926
 927 /** hazptr_tc free functions */
 928
 929 FOLLY_ALWAYS_INLINE hazptr_tc* hazptr_tc_tls() {
 930   DEBUG_PRINT(tls_state_);
 931   if (LIKELY(tls_state_ == TLS_ALIVE)) {
 932     DEBUG_PRINT(tls_state_);
 933     return &tls_tc_data_;
 934   } else if (tls_state_ == TLS_UNINITIALIZED) {
 935     tls_life_odr_use();
 936     return &tls_tc_data_;
 937   }
 938   return nullptr;
 939 }
 940
 941 inline void hazptr_tc_init() {
 942   DEBUG_PRINT("");
 943   auto& tc = tls_tc_data_;
 944   DEBUG_PRINT(&tc);
 945   tc.count_ = 0;
 946   if (kIsDebug) {
 947     tc.local_ = false;
 948   }
 949 }
 950
 951 inline void hazptr_tc_shutdown() {
 952   auto& tc = tls_tc_data_;
 953   DEBUG_PRINT(&tc);
 954   for (size_t i = 0; i < tc.count_; ++i) {
 955     tc.entry_[i].evict();
 956   }
 957 }
 958
 959 FOLLY_ALWAYS_INLINE hazptr_rec* hazptr_tc_try_get() {
 960   DEBUG_PRINT(TLS_UNINITIALIZED << TLS_ALIVE << TLS_DESTROYED);
 961   DEBUG_PRINT(tls_state_);
 962   if (LIKELY(tls_state_ == TLS_ALIVE)) {
 963     DEBUG_PRINT(tls_state_);
 964     return tls_tc_data_.get();
 965   } else if (tls_state_ == TLS_UNINITIALIZED) {
 966     tls_life_odr_use();
 967     return tls_tc_data_.get();
 968   }
 969   return nullptr;
 970 }
 971
 972 FOLLY_ALWAYS_INLINE bool hazptr_tc_try_put(hazptr_rec* hprec) {
 973   DEBUG_PRINT(tls_state_);
 974   if (LIKELY(tls_state_ == TLS_ALIVE)) {
 975     DEBUG_PRINT(tls_state_);
 976     return tls_tc_data_.put(hprec);
 977   }
 978   return false;
 979 }
 980
 981 /**
 982  *  hazptr_priv
 983  */
 984
 985 inline void hazptr_priv::push(hazptr_obj* obj) {
 986   auto& domain = default_hazptr_domain();
 987   obj->next_ = nullptr;
 988   if (tail_) {
 989     tail_->next_ = obj;
 990   } else {
 991     if (!active_) {
 992       domain.objRetire(obj);
 993       return;
 994     }
 995     head_ = obj;
 996   }
 997   tail_ = obj;
 998   ++rcount_;
 999   if (domain.reachedThreshold(rcount_)) {
1000     pushAllToDomain();
1001   }
1002 }
1003
1004 inline void hazptr_priv::pushAllToDomain() {
1005   auto& domain = default_hazptr_domain();
1006   domain.pushRetired(head_, tail_, rcount_);
1007   head_ = nullptr;
1008   tail_ = nullptr;
1009   rcount_ = 0;
1010   domain.tryBulkReclaim();
1011 }
1012
1013 inline void hazptr_priv_init() {
1014   auto& priv = tls_priv_data_;
1015   DEBUG_PRINT(&priv);
1016   priv.head_ = nullptr;
1017   priv.tail_ = nullptr;
1018   priv.rcount_ = 0;
1019   priv.active_ = true;
1020 }
1021
1022 inline void hazptr_priv_shutdown() {
1023   auto& priv = tls_priv_data_;
1024   DEBUG_PRINT(&priv);
1025   DCHECK(priv.active_);
1026   priv.active_ = false;
1027   if (priv.tail_) {
1028     priv.pushAllToDomain();
1029   }
1030 }
1031
1032 inline bool hazptr_priv_try_retire(hazptr_obj* obj) {
1033   DEBUG_PRINT(tls_state_);
1034   if (tls_state_ == TLS_ALIVE) {
1035     DEBUG_PRINT(tls_state_);
1036     tls_priv_data_.push(obj);
1037     return true;
1038   } else if (tls_state_ == TLS_UNINITIALIZED) {
1039     DEBUG_PRINT(tls_state_);
1040     tls_life_odr_use();
1041     tls_priv_data_.push(obj);
1042     return true;
1043   }
1044   return false;
1045 }
1046
1047 /** hazptr_tls_life */
1048
1049 inline void tls_life_odr_use() {
1050   DEBUG_PRINT(tls_state_);
1051   CHECK(tls_state_ == TLS_UNINITIALIZED);
1052   auto volatile tlsOdrUse = &tls_life_;
1053   CHECK(tlsOdrUse != nullptr);
1054   DEBUG_PRINT(tlsOdrUse);
1055 }
1056
1057 inline hazptr_tls_life::hazptr_tls_life() {
1058   DEBUG_PRINT(this);
1059   CHECK(tls_state_ == TLS_UNINITIALIZED);
1060   hazptr_tc_init();
1061   hazptr_priv_init();
1062   tls_state_ = TLS_ALIVE;
1063 }
1064
1065 inline hazptr_tls_life::~hazptr_tls_life() {
1066   DEBUG_PRINT(this);
1067   CHECK(tls_state_ == TLS_ALIVE);
1068   hazptr_tc_shutdown();
1069   hazptr_priv_shutdown();
1070   tls_state_ = TLS_DESTROYED;
1071 }
1072
1073 } // namespace hazptr
1074 } // namespace folly