folly/experimental/hazptr/hazptr-impl.h

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