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   for (size_t i = 0; i < M; ++i) {
 456     new (&h[i]) hazptr_holder(std::move(other.h_[i]));
 457     DEBUG_PRINT(i << " " << &h[i] << " " << &other.h_[i]);
 458   }
 459   empty_ = other.empty_;
 460   other.empty_ = true;
 461 }
 462
 463 template <size_t M>
 464 FOLLY_ALWAYS_INLINE hazptr_array<M>::hazptr_array(std::nullptr_t) noexcept {
 465   DEBUG_PRINT(this << " " << M);
 466   auto h = reinterpret_cast<hazptr_holder*>(&raw_);
 467   for (size_t i = 0; i < M; ++i) {
 468     new (&h[i]) hazptr_holder(nullptr);
 469     DEBUG_PRINT(i << " " << &h[i]);
 470   }
 471   empty_ = true;
 472 }
 473
 474 template <size_t M>
 475 FOLLY_ALWAYS_INLINE hazptr_array<M>::~hazptr_array() {
 476   if (empty_) {
 477     return;
 478   }
 479   auto h = reinterpret_cast<hazptr_holder*>(&raw_);
 480   if (HAZPTR_TC) {
 481     auto ptc = hazptr_tc_tls();
 482     if (LIKELY(ptc != nullptr)) {
 483       auto& tc = *ptc;
 484       auto count = tc.count();
 485       if ((M <= HAZPTR_TC_SIZE) && (count + M <= HAZPTR_TC_SIZE)) {
 486         for (size_t i = 0; i < M; ++i) {
 487           tc[count + i].hprec_ = h[i].hazptr_;
 488           DEBUG_PRINT(i << " " << &h[i]);
 489           new (&h[i]) hazptr_holder(nullptr);
 490           DEBUG_PRINT(
 491               i << " " << &h[i] << " " << h[i].domain_ << " " << h[i].hazptr_);
 492         }
 493         tc.count_ = count + M;
 494         return;
 495       }
 496     }
 497   }
 498   // slow path
 499   for (size_t i = 0; i < M; ++i) {
 500     h[i].~hazptr_holder();
 501   }
 502 }
 503
 504 template <size_t M>
 505 FOLLY_ALWAYS_INLINE hazptr_array<M>& hazptr_array<M>::operator=(
 506     hazptr_array&& other) noexcept {
 507   DEBUG_PRINT(this << " " << M << " " << &other);
 508   auto h = reinterpret_cast<hazptr_holder*>(&raw_);
 509   for (size_t i = 0; i < M; ++i) {
 510     h[i] = std::move(other[i]);
 511     DEBUG_PRINT(i << " " << &h[i] << " " << &other[i]);
 512   }
 513   empty_ = other.empty_;
 514   other.empty_ = true;
 515   return *this;
 516 }
 517
 518 template <size_t M>
 519 FOLLY_ALWAYS_INLINE hazptr_holder& hazptr_array<M>::operator[](
 520     size_t i) noexcept {
 521   auto h = reinterpret_cast<hazptr_holder*>(&raw_);
 522   DCHECK(i < M);
 523   return h[i];
 524 }
 525
 526 /**
 527  *  hazptr_local
 528  */
 529
 530 template <size_t M>
 531 FOLLY_ALWAYS_INLINE hazptr_local<M>::hazptr_local() {
 532   auto h = reinterpret_cast<hazptr_holder*>(&raw_);
 533   if (HAZPTR_TC) {
 534     auto ptc = hazptr_tc_tls();
 535     if (LIKELY(ptc != nullptr)) {
 536       auto& tc = *ptc;
 537       auto count = tc.count();
 538       if (M <= count) {
 539         if (kIsDebug) {
 540           DCHECK(!tc.local_);
 541           tc.local_ = true;
 542         }
 543         // Fast path
 544         for (size_t i = 0; i < M; ++i) {
 545           auto hprec = tc[i].hprec_;
 546           DCHECK(hprec != nullptr);
 547           DEBUG_PRINT(i << " " << &h[i]);
 548           new (&h[i]) hazptr_holder(nullptr);
 549           h[i].hazptr_ = hprec;
 550           DEBUG_PRINT(
 551               i << " " << &h[i] << " " << h[i].domain_ << " " << h[i].hazptr_);
 552         }
 553         return;
 554       }
 555     }
 556   }
 557   // Slow path
 558   need_destruct_ = true;
 559   for (size_t i = 0; i < M; ++i) {
 560     new (&h[i]) hazptr_holder;
 561     DEBUG_PRINT(
 562         i << " " << &h[i] << " " << h[i].domain_ << " " << h[i].hazptr_);
 563   }
 564 }
 565
 566 template <size_t M>
 567 FOLLY_ALWAYS_INLINE hazptr_local<M>::~hazptr_local() {
 568   if (LIKELY(!need_destruct_)) {
 569     if (kIsDebug) {
 570       auto ptc = hazptr_tc_tls();
 571       DCHECK(ptc != nullptr);
 572       auto& tc = *ptc;
 573       DCHECK(tc.local_);
 574       tc.local_ = false;
 575     }
 576     return;
 577   }
 578   // Slow path
 579   auto h = reinterpret_cast<hazptr_holder*>(&raw_);
 580   for (size_t i = 0; i < M; ++i) {
 581     h[i].~hazptr_holder();
 582   }
 583 }
 584
 585 template <size_t M>
 586 FOLLY_ALWAYS_INLINE hazptr_holder& hazptr_local<M>::operator[](
 587     size_t i) noexcept {
 588   auto h = reinterpret_cast<hazptr_holder*>(&raw_);
 589   DCHECK(i < M);
 590   return h[i];
 591 }
 592
 593 ////////////////////////////////////////////////////////////////////////////////
 594 // [TODO]:
 595 // - Control of reclamation (when and by whom)
 596 // - End-to-end lock-free implementation
 597
 598 /** Definition of default_hazptr_domain() */
 599
 600 FOLLY_ALWAYS_INLINE hazptr_domain& default_hazptr_domain() {
 601   DEBUG_PRINT(&default_domain_);
 602   return default_domain_;
 603 }
 604
 605 template <typename T, typename D>
 606 FOLLY_ALWAYS_INLINE void hazptr_retire(T* obj, D reclaim) {
 607   default_hazptr_domain().retire(obj, std::move(reclaim));
 608 }
 609
 610 /** hazptr_rec */
 611
 612 FOLLY_ALWAYS_INLINE void hazptr_rec::set(const void* p) noexcept {
 613   DEBUG_PRINT(this << " " << p);
 614   hazptr_.store(p, std::memory_order_release);
 615 }
 616
 617 inline const void* hazptr_rec::get() const noexcept {
 618   auto p = hazptr_.load(std::memory_order_acquire);
 619   DEBUG_PRINT(this << " " << p);
 620   return p;
 621 }
 622
 623 FOLLY_ALWAYS_INLINE void hazptr_rec::clear() noexcept {
 624   DEBUG_PRINT(this);
 625   hazptr_.store(nullptr, std::memory_order_release);
 626 }
 627
 628 inline bool hazptr_rec::isActive() noexcept {
 629   return active_.load(std::memory_order_acquire);
 630 }
 631
 632 inline bool hazptr_rec::tryAcquire() noexcept {
 633   bool active = isActive();
 634   if (!active &&
 635       active_.compare_exchange_strong(
 636           active, true, std::memory_order_release, std::memory_order_relaxed)) {
 637     DEBUG_PRINT(this);
 638     return true;
 639   }
 640   return false;
 641 }
 642
 643 inline void hazptr_rec::release() noexcept {
 644   DEBUG_PRINT(this);
 645   active_.store(false, std::memory_order_release);
 646 }
 647
 648 /** hazptr_obj */
 649
 650 inline const void* hazptr_obj::getObjPtr() const {
 651   DEBUG_PRINT(this);
 652   return this;
 653 }
 654
 655 /** hazptr_domain */
 656
 657 template <typename T, typename D>
 658 void hazptr_domain::retire(T* obj, D reclaim) {
 659   struct hazptr_retire_node : hazptr_obj {
 660     std::unique_ptr<T, D> obj_;
 661
 662     hazptr_retire_node(T* obj, D reclaim) : obj_{obj, std::move(reclaim)} {}
 663   };
 664
 665   auto node = new hazptr_retire_node(obj, std::move(reclaim));
 666   node->reclaim_ = [](hazptr_obj* p) {
 667     delete static_cast<hazptr_retire_node*>(p);
 668   };
 669   objRetire(node);
 670 }
 671
 672 inline hazptr_domain::~hazptr_domain() {
 673   DEBUG_PRINT(this);
 674   { /* reclaim all remaining retired objects */
 675     hazptr_obj* next;
 676     auto retired = retired_.exchange(nullptr);
 677     while (retired) {
 678       for (auto p = retired; p; p = next) {
 679         next = p->next_;
 680         DEBUG_PRINT(this << " " << p << " " << p->reclaim_);
 681         (*(p->reclaim_))(p);
 682       }
 683       retired = retired_.exchange(nullptr);
 684     }
 685   }
 686   /* Leak the data for the default domain to avoid destruction order
 687    * issues with thread caches.
 688    */
 689   if (this != &default_hazptr_domain()) {
 690     /* free all hazptr_rec-s */
 691     hazptr_rec* next;
 692     for (auto p = hazptrs_.load(std::memory_order_acquire); p; p = next) {
 693       next = p->next_;
 694       DCHECK(!p->isActive());
 695       mr_->deallocate(static_cast<void*>(p), sizeof(hazptr_rec));
 696     }
 697   }
 698 }
 699
 700 inline hazptr_rec* hazptr_domain::hazptrAcquire() {
 701   hazptr_rec* p;
 702   hazptr_rec* next;
 703   for (p = hazptrs_.load(std::memory_order_acquire); p; p = next) {
 704     next = p->next_;
 705     if (p->tryAcquire()) {
 706       return p;
 707     }
 708   }
 709   p = static_cast<hazptr_rec*>(mr_->allocate(sizeof(hazptr_rec)));
 710   DEBUG_PRINT(this << " " << p << " " << sizeof(hazptr_rec));
 711   if (p == nullptr) {
 712     return nullptr;
 713   }
 714   p->active_.store(true, std::memory_order_relaxed);
 715   p->next_ = hazptrs_.load(std::memory_order_acquire);
 716   while (!hazptrs_.compare_exchange_weak(
 717       p->next_, p, std::memory_order_release, std::memory_order_acquire)) {
 718     /* keep trying */;
 719   }
 720   auto hcount = hcount_.fetch_add(1);
 721   DEBUG_PRINT(this << " " << p << " " << sizeof(hazptr_rec) << " " << hcount);
 722   return p;
 723 }
 724
 725 inline void hazptr_domain::hazptrRelease(hazptr_rec* p) noexcept {
 726   DEBUG_PRINT(this << " " << p);
 727   p->release();
 728 }
 729
 730 inline int
 731 hazptr_domain::pushRetired(hazptr_obj* head, hazptr_obj* tail, int count) {
 732   /*** Full fence ***/ hazptr_mb::light();
 733   tail->next_ = retired_.load(std::memory_order_acquire);
 734   while (!retired_.compare_exchange_weak(
 735       tail->next_,
 736       head,
 737       std::memory_order_release,
 738       std::memory_order_acquire)) {
 739   }
 740   return rcount_.fetch_add(count) + count;
 741 }
 742
 743 inline bool hazptr_domain::reachedThreshold(int rcount) {
 744   return (
 745       rcount >= HAZPTR_SCAN_THRESHOLD &&
 746       rcount >= HAZPTR_SCAN_MULT * hcount_.load(std::memory_order_acquire));
 747 }
 748
 749 inline void hazptr_domain::objRetire(hazptr_obj* p) {
 750   auto rcount = pushRetired(p, p, 1);
 751   if (reachedThreshold(rcount)) {
 752     tryBulkReclaim();
 753   }
 754 }
 755
 756 inline void hazptr_domain::tryBulkReclaim() {
 757   DEBUG_PRINT(this);
 758   do {
 759     auto hcount = hcount_.load(std::memory_order_acquire);
 760     auto rcount = rcount_.load(std::memory_order_acquire);
 761     if (rcount < HAZPTR_SCAN_THRESHOLD || rcount < HAZPTR_SCAN_MULT * hcount) {
 762       return;
 763     }
 764     if (rcount_.compare_exchange_weak(
 765             rcount, 0, std::memory_order_release, std::memory_order_relaxed)) {
 766       break;
 767     }
 768   } while (true);
 769   bulkReclaim();
 770 }
 771
 772 inline void hazptr_domain::bulkReclaim() {
 773   DEBUG_PRINT(this);
 774   /*** Full fence ***/ hazptr_mb::heavy();
 775   auto p = retired_.exchange(nullptr, std::memory_order_acquire);
 776   auto h = hazptrs_.load(std::memory_order_acquire);
 777   std::unordered_set<const void*> hs; // TODO lock-free alternative
 778   for (; h; h = h->next_) {
 779     hs.insert(h->get());
 780   }
 781   int rcount = 0;
 782   hazptr_obj* retired = nullptr;
 783   hazptr_obj* tail = nullptr;
 784   hazptr_obj* next;
 785   for (; p; p = next) {
 786     next = p->next_;
 787     if (hs.count(p->getObjPtr()) == 0) {
 788       DEBUG_PRINT(this << " " << p << " " << p->reclaim_);
 789       (*(p->reclaim_))(p);
 790     } else {
 791       p->next_ = retired;
 792       retired = p;
 793       if (tail == nullptr) {
 794         tail = p;
 795       }
 796       ++rcount;
 797     }
 798   }
 799   if (tail) {
 800     pushRetired(retired, tail, rcount);
 801   }
 802 }
 803
 804 /** hazptr_stats */
 805
 806 class hazptr_stats {
 807  public:
 808   ~hazptr_stats();
 809   void light();
 810   void heavy();
 811   void seq_cst();
 812
 813  private:
 814   std::atomic<uint64_t> light_{0};
 815   std::atomic<uint64_t> heavy_{0};
 816   std::atomic<uint64_t> seq_cst_{0};
 817 };
 818
 819 extern hazptr_stats hazptr_stats_;
 820
 821 inline hazptr_stats::~hazptr_stats() {
 822   DEBUG_PRINT(this << " light " << light_.load());
 823   DEBUG_PRINT(this << " heavy " << heavy_.load());
 824   DEBUG_PRINT(this << " seq_cst " << seq_cst_.load());
 825 }
 826
 827 FOLLY_ALWAYS_INLINE void hazptr_stats::light() {
 828   if (HAZPTR_STATS) {
 829     /* atomic */ ++light_;
 830   }
 831 }
 832
 833 inline void hazptr_stats::heavy() {
 834   if (HAZPTR_STATS) {
 835     /* atomic */ ++heavy_;
 836   }
 837 }
 838
 839 inline void hazptr_stats::seq_cst() {
 840   if (HAZPTR_STATS) {
 841     /* atomic */ ++seq_cst_;
 842   }
 843 }
 844
 845 /** hazptr_mb */
 846
 847 FOLLY_ALWAYS_INLINE void hazptr_mb::light() {
 848   DEBUG_PRINT("");
 849   if (HAZPTR_AMB) {
 850     folly::asymmetricLightBarrier();
 851     INC_HAZPTR_STATS(light);
 852   } else {
 853     atomic_thread_fence(std::memory_order_seq_cst);
 854     INC_HAZPTR_STATS(seq_cst);
 855   }
 856 }
 857
 858 inline void hazptr_mb::heavy() {
 859   DEBUG_PRINT("");
 860   if (HAZPTR_AMB) {
 861     folly::asymmetricHeavyBarrier(AMBFlags::EXPEDITED);
 862     INC_HAZPTR_STATS(heavy);
 863   } else {
 864     atomic_thread_fence(std::memory_order_seq_cst);
 865     INC_HAZPTR_STATS(seq_cst);
 866   }
 867 }
 868
 869 /**
 870  *  TLS structures
 871  */
 872
 873 /**
 874  *  hazptr_tc structures
 875  */
 876
 877 /** hazptr_tc_entry */
 878
 879 FOLLY_ALWAYS_INLINE void hazptr_tc_entry::fill(hazptr_rec* hprec) {
 880   hprec_ = hprec;
 881   DEBUG_PRINT(this << " " << hprec);
 882 }
 883
 884 FOLLY_ALWAYS_INLINE hazptr_rec* hazptr_tc_entry::get() {
 885   auto hprec = hprec_;
 886   DEBUG_PRINT(this << " " << hprec);
 887   return hprec;
 888 }
 889
 890 inline void hazptr_tc_entry::evict() {
 891   auto hprec = hprec_;
 892   hprec->release();
 893   DEBUG_PRINT(this << " " << hprec);
 894 }
 895
 896 /** hazptr_tc */
 897
 898 FOLLY_ALWAYS_INLINE hazptr_tc_entry& hazptr_tc::operator[](size_t i) {
 899   DCHECK(i <= HAZPTR_TC_SIZE);
 900   return entry_[i];
 901 }
 902
 903 FOLLY_ALWAYS_INLINE hazptr_rec* hazptr_tc::get() {
 904   if (LIKELY(count_ != 0)) {
 905     auto hprec = entry_[--count_].get();
 906     DEBUG_PRINT(this << " " << hprec);
 907     return hprec;
 908   }
 909   DEBUG_PRINT(this << " nullptr");
 910   return nullptr;
 911 }
 912
 913 FOLLY_ALWAYS_INLINE bool hazptr_tc::put(hazptr_rec* hprec) {
 914   if (LIKELY(count_ < HAZPTR_TC_SIZE)) {
 915     entry_[count_++].fill(hprec);
 916     DEBUG_PRINT(this << " " << count_ - 1);
 917     return true;
 918   }
 919   return false;
 920 }
 921
 922 FOLLY_ALWAYS_INLINE size_t hazptr_tc::count() {
 923   return count_;
 924 }
 925
 926 /** hazptr_tc free functions */
 927
 928 FOLLY_ALWAYS_INLINE hazptr_tc* hazptr_tc_tls() {
 929   DEBUG_PRINT(tls_state_);
 930   if (LIKELY(tls_state_ == TLS_ALIVE)) {
 931     DEBUG_PRINT(tls_state_);
 932     return &tls_tc_data_;
 933   } else if (tls_state_ == TLS_UNINITIALIZED) {
 934     tls_life_odr_use();
 935     return &tls_tc_data_;
 936   }
 937   return nullptr;
 938 }
 939
 940 inline void hazptr_tc_init() {
 941   DEBUG_PRINT("");
 942   auto& tc = tls_tc_data_;
 943   DEBUG_PRINT(&tc);
 944   tc.count_ = 0;
 945   if (kIsDebug) {
 946     tc.local_ = false;
 947   }
 948 }
 949
 950 inline void hazptr_tc_shutdown() {
 951   auto& tc = tls_tc_data_;
 952   DEBUG_PRINT(&tc);
 953   for (size_t i = 0; i < tc.count_; ++i) {
 954     tc.entry_[i].evict();
 955   }
 956 }
 957
 958 FOLLY_ALWAYS_INLINE hazptr_rec* hazptr_tc_try_get() {
 959   DEBUG_PRINT(TLS_UNINITIALIZED << TLS_ALIVE << TLS_DESTROYED);
 960   DEBUG_PRINT(tls_state_);
 961   if (LIKELY(tls_state_ == TLS_ALIVE)) {
 962     DEBUG_PRINT(tls_state_);
 963     return tls_tc_data_.get();
 964   } else if (tls_state_ == TLS_UNINITIALIZED) {
 965     tls_life_odr_use();
 966     return tls_tc_data_.get();
 967   }
 968   return nullptr;
 969 }
 970
 971 FOLLY_ALWAYS_INLINE bool hazptr_tc_try_put(hazptr_rec* hprec) {
 972   DEBUG_PRINT(tls_state_);
 973   if (LIKELY(tls_state_ == TLS_ALIVE)) {
 974     DEBUG_PRINT(tls_state_);
 975     return tls_tc_data_.put(hprec);
 976   }
 977   return false;
 978 }
 979
 980 /**
 981  *  hazptr_priv
 982  */
 983
 984 inline void hazptr_priv::push(hazptr_obj* obj) {
 985   auto& domain = default_hazptr_domain();
 986   obj->next_ = nullptr;
 987   if (tail_) {
 988     tail_->next_ = obj;
 989   } else {
 990     if (!active_) {
 991       domain.objRetire(obj);
 992       return;
 993     }
 994     head_ = obj;
 995   }
 996   tail_ = obj;
 997   ++rcount_;
 998   if (domain.reachedThreshold(rcount_)) {
 999     pushAllToDomain();
1000   }
1001 }
1002
1003 inline void hazptr_priv::pushAllToDomain() {
1004   auto& domain = default_hazptr_domain();
1005   domain.pushRetired(head_, tail_, rcount_);
1006   head_ = nullptr;
1007   tail_ = nullptr;
1008   rcount_ = 0;
1009   domain.tryBulkReclaim();
1010 }
1011
1012 inline void hazptr_priv_init() {
1013   auto& priv = tls_priv_data_;
1014   DEBUG_PRINT(&priv);
1015   priv.head_ = nullptr;
1016   priv.tail_ = nullptr;
1017   priv.rcount_ = 0;
1018   priv.active_ = true;
1019 }
1020
1021 inline void hazptr_priv_shutdown() {
1022   auto& priv = tls_priv_data_;
1023   DEBUG_PRINT(&priv);
1024   DCHECK(priv.active_);
1025   priv.active_ = false;
1026   if (priv.tail_) {
1027     priv.pushAllToDomain();
1028   }
1029 }
1030
1031 inline bool hazptr_priv_try_retire(hazptr_obj* obj) {
1032   DEBUG_PRINT(tls_state_);
1033   if (tls_state_ == TLS_ALIVE) {
1034     DEBUG_PRINT(tls_state_);
1035     tls_priv_data_.push(obj);
1036     return true;
1037   } else if (tls_state_ == TLS_UNINITIALIZED) {
1038     DEBUG_PRINT(tls_state_);
1039     tls_life_odr_use();
1040     tls_priv_data_.push(obj);
1041     return true;
1042   }
1043   return false;
1044 }
1045
1046 /** hazptr_tls_life */
1047
1048 inline void tls_life_odr_use() {
1049   DEBUG_PRINT(tls_state_);
1050   CHECK(tls_state_ == TLS_UNINITIALIZED);
1051   auto volatile tlsOdrUse = &tls_life_;
1052   CHECK(tlsOdrUse != nullptr);
1053   DEBUG_PRINT(tlsOdrUse);
1054 }
1055
1056 inline hazptr_tls_life::hazptr_tls_life() {
1057   DEBUG_PRINT(this);
1058   CHECK(tls_state_ == TLS_UNINITIALIZED);
1059   hazptr_tc_init();
1060   hazptr_priv_init();
1061   tls_state_ = TLS_ALIVE;
1062 }
1063
1064 inline hazptr_tls_life::~hazptr_tls_life() {
1065   DEBUG_PRINT(this);
1066   CHECK(tls_state_ == TLS_ALIVE);
1067   hazptr_tc_shutdown();
1068   hazptr_priv_shutdown();
1069   tls_state_ = TLS_DESTROYED;
1070 }
1071
1072 } // namespace hazptr
1073 } // namespace folly