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   preRetire(deleter);
 220   if (HAZPTR_PRIV &&
 221       (HAZPTR_ONE_DOMAIN || (&domain == &default_hazptr_domain()))) {
 222     if (hazptr_priv_try_retire(this)) {
 223       return;
 224     }
 225   }
 226   domain.objRetire(this);
 227 }
 228
 229 template <typename T, typename D>
 230 inline void hazptr_obj_base_refcounted<T, D>::acquire_ref() {
 231   DEBUG_PRINT(this);
 232   auto oldval = refcount_.fetch_add(1);
 233   DCHECK(oldval >= 0);
 234 }
 235
 236 template <typename T, typename D>
 237 inline void hazptr_obj_base_refcounted<T, D>::acquire_ref_safe() {
 238   DEBUG_PRINT(this);
 239   auto oldval = refcount_.load(std::memory_order_acquire);
 240   DCHECK(oldval >= 0);
 241   refcount_.store(oldval + 1, std::memory_order_release);
 242 }
 243
 244 template <typename T, typename D>
 245 inline bool hazptr_obj_base_refcounted<T, D>::release_ref() {
 246   DEBUG_PRINT(this);
 247   auto oldval = refcount_.load(std::memory_order_acquire);
 248   if (oldval > 0) {
 249     oldval = refcount_.fetch_sub(1);
 250   } else {
 251     if (kIsDebug) {
 252       refcount_.store(-1);
 253     }
 254   }
 255   DEBUG_PRINT(this << " " << oldval);
 256   DCHECK(oldval >= 0);
 257   return oldval == 0;
 258 }
 259
 260 template <typename T, typename D>
 261 inline void hazptr_obj_base_refcounted<T, D>::preRetire(D deleter) {
 262   DCHECK(next_ == nullptr);
 263   deleter_ = std::move(deleter);
 264   reclaim_ = [](hazptr_obj* p) {
 265     auto hrobp = static_cast<hazptr_obj_base_refcounted*>(p);
 266     if (hrobp->release_ref()) {
 267       auto obj = static_cast<T*>(hrobp);
 268       hrobp->deleter_(obj);
 269     }
 270   };
 271 }
 272
 273 /**
 274  *  hazptr_rec
 275  */
 276
 277 class alignas(hardware_destructive_interference_size) hazptr_rec {
 278   friend class hazptr_domain;
 279   friend class hazptr_holder;
 280   friend struct hazptr_tc_entry;
 281
 282   std::atomic<const void*> hazptr_{nullptr};
 283   hazptr_rec* next_{nullptr};
 284   std::atomic<bool> active_{false};
 285
 286   void set(const void* p) noexcept;
 287   const void* get() const noexcept;
 288   void clear() noexcept;
 289   bool isActive() noexcept;
 290   bool tryAcquire() noexcept;
 291   void release() noexcept;
 292 };
 293
 294 /**
 295  *  hazptr_holder
 296  */
 297
 298 FOLLY_ALWAYS_INLINE hazptr_holder::hazptr_holder(hazptr_domain& domain) {
 299   domain_ = &domain;
 300   if (LIKELY(
 301           HAZPTR_TC &&
 302           (HAZPTR_ONE_DOMAIN || &domain == &default_hazptr_domain()))) {
 303     auto hprec = hazptr_tc_try_get();
 304     if (LIKELY(hprec != nullptr)) {
 305       hazptr_ = hprec;
 306       DEBUG_PRINT(this << " " << domain_ << " " << hazptr_);
 307       return;
 308     }
 309   }
 310   hazptr_ = domain_->hazptrAcquire();
 311   DEBUG_PRINT(this << " " << domain_ << " " << hazptr_);
 312   if (hazptr_ == nullptr) { std::bad_alloc e; throw e; }
 313 }
 314
 315 FOLLY_ALWAYS_INLINE hazptr_holder::hazptr_holder(std::nullptr_t) noexcept {
 316   domain_ = nullptr;
 317   hazptr_ = nullptr;
 318   DEBUG_PRINT(this << " " << domain_ << " " << hazptr_);
 319 }
 320
 321 FOLLY_ALWAYS_INLINE hazptr_holder::~hazptr_holder() {
 322   DEBUG_PRINT(this);
 323   if (LIKELY(hazptr_ != nullptr)) {
 324     hazptr_->clear();
 325     if (LIKELY(
 326             HAZPTR_TC &&
 327             (HAZPTR_ONE_DOMAIN || domain_ == &default_hazptr_domain()))) {
 328       if (LIKELY(hazptr_tc_try_put(hazptr_))) {
 329         return;
 330       }
 331     }
 332     domain_->hazptrRelease(hazptr_);
 333   }
 334 }
 335
 336 FOLLY_ALWAYS_INLINE hazptr_holder::hazptr_holder(hazptr_holder&& rhs) noexcept {
 337   domain_ = rhs.domain_;
 338   hazptr_ = rhs.hazptr_;
 339   rhs.domain_ = nullptr;
 340   rhs.hazptr_ = nullptr;
 341 }
 342
 343 FOLLY_ALWAYS_INLINE
 344 hazptr_holder& hazptr_holder::operator=(hazptr_holder&& rhs) noexcept {
 345   /* Self-move is a no-op.  */
 346   if (LIKELY(this != &rhs)) {
 347     this->~hazptr_holder();
 348     new (this) hazptr_holder(std::move(rhs));
 349   }
 350   return *this;
 351 }
 352
 353 template <typename T>
 354 FOLLY_ALWAYS_INLINE bool hazptr_holder::try_protect(
 355     T*& ptr,
 356     const std::atomic<T*>& src) noexcept {
 357   return try_protect(ptr, src, [](T* t) { return t; });
 358 }
 359
 360 template <typename T, typename Func>
 361 FOLLY_ALWAYS_INLINE bool hazptr_holder::try_protect(
 362     T*& ptr,
 363     const std::atomic<T*>& src,
 364     Func f) noexcept {
 365   DEBUG_PRINT(this << " " << ptr << " " << &src);
 366   reset(f(ptr));
 367   /*** Full fence ***/ hazptr_mb::light();
 368   T* p = src.load(std::memory_order_acquire);
 369   if (UNLIKELY(p != ptr)) {
 370     ptr = p;
 371     reset();
 372     return false;
 373   }
 374   return true;
 375 }
 376
 377 template <typename T>
 378 FOLLY_ALWAYS_INLINE T* hazptr_holder::get_protected(
 379     const std::atomic<T*>& src) noexcept {
 380   return get_protected(src, [](T* t) { return t; });
 381 }
 382
 383 template <typename T, typename Func>
 384 FOLLY_ALWAYS_INLINE T* hazptr_holder::get_protected(
 385     const std::atomic<T*>& src,
 386     Func f) noexcept {
 387   T* p = src.load(std::memory_order_relaxed);
 388   while (!try_protect(p, src, f)) {
 389   }
 390   DEBUG_PRINT(this << " " << p << " " << &src);
 391   return p;
 392 }
 393
 394 template <typename T>
 395 FOLLY_ALWAYS_INLINE void hazptr_holder::reset(const T* ptr) noexcept {
 396   auto p = static_cast<hazptr_obj*>(const_cast<T*>(ptr));
 397   DEBUG_PRINT(this << " " << ptr << " p:" << p);
 398   DCHECK(hazptr_); // UB if *this is empty
 399   hazptr_->set(p);
 400 }
 401
 402 FOLLY_ALWAYS_INLINE void hazptr_holder::reset(std::nullptr_t) noexcept {
 403   DEBUG_PRINT(this);
 404   DCHECK(hazptr_); // UB if *this is empty
 405   hazptr_->clear();
 406 }
 407
 408 FOLLY_ALWAYS_INLINE void hazptr_holder::swap(hazptr_holder& rhs) noexcept {
 409   DEBUG_PRINT(
 410     this << " " <<  this->hazptr_ << " " << this->domain_ << " -- "
 411     << &rhs << " " << rhs.hazptr_ << " " << rhs.domain_);
 412   if (!HAZPTR_ONE_DOMAIN) {
 413     std::swap(this->domain_, rhs.domain_);
 414   }
 415   std::swap(this->hazptr_, rhs.hazptr_);
 416 }
 417
 418 FOLLY_ALWAYS_INLINE void swap(hazptr_holder& lhs, hazptr_holder& rhs) noexcept {
 419   lhs.swap(rhs);
 420 }
 421
 422 /**
 423  *  hazptr_array
 424  */
 425
 426 template <size_t M>
 427 FOLLY_ALWAYS_INLINE hazptr_array<M>::hazptr_array() {
 428   auto h = reinterpret_cast<hazptr_holder*>(&raw_);
 429   if (HAZPTR_TC) {
 430     auto ptc = hazptr_tc_tls();
 431     if (LIKELY(ptc != nullptr)) {
 432       auto& tc = *ptc;
 433       auto count = tc.count();
 434       if (M <= count) {
 435         size_t offset = count - M;
 436         for (size_t i = 0; i < M; ++i) {
 437           auto hprec = tc[offset + i].hprec_;
 438           DCHECK(hprec != nullptr);
 439           DEBUG_PRINT(i << " " << &h[i]);
 440           new (&h[i]) hazptr_holder(nullptr);
 441           h[i].hazptr_ = hprec;
 442           DEBUG_PRINT(
 443               i << " " << &h[i] << " " << h[i].domain_ << " " << h[i].hazptr_);
 444         }
 445         tc.count_ = offset;
 446         return;
 447       }
 448     }
 449   }
 450   // slow path
 451   for (size_t i = 0; i < M; ++i) {
 452     new (&h[i]) hazptr_holder;
 453     DEBUG_PRINT(
 454         i << " " << &h[i] << " " << h[i].domain_ << " " << h[i].hazptr_);
 455   }
 456 }
 457
 458 template <size_t M>
 459 FOLLY_ALWAYS_INLINE hazptr_array<M>::hazptr_array(
 460     hazptr_array&& other) noexcept {
 461   DEBUG_PRINT(this << " " << M << " " << &other);
 462   auto h = reinterpret_cast<hazptr_holder*>(&raw_);
 463   auto hother = reinterpret_cast<hazptr_holder*>(&other.raw_);
 464   for (size_t i = 0; i < M; ++i) {
 465     new (&h[i]) hazptr_holder(std::move(hother[i]));
 466     DEBUG_PRINT(i << " " << &h[i] << " " << &hother[i]);
 467   }
 468   empty_ = other.empty_;
 469   other.empty_ = true;
 470 }
 471
 472 template <size_t M>
 473 FOLLY_ALWAYS_INLINE hazptr_array<M>::hazptr_array(std::nullptr_t) noexcept {
 474   DEBUG_PRINT(this << " " << M);
 475   auto h = reinterpret_cast<hazptr_holder*>(&raw_);
 476   for (size_t i = 0; i < M; ++i) {
 477     new (&h[i]) hazptr_holder(nullptr);
 478     DEBUG_PRINT(i << " " << &h[i]);
 479   }
 480   empty_ = true;
 481 }
 482
 483 template <size_t M>
 484 FOLLY_ALWAYS_INLINE hazptr_array<M>::~hazptr_array() {
 485   if (empty_) {
 486     return;
 487   }
 488   auto h = reinterpret_cast<hazptr_holder*>(&raw_);
 489   if (HAZPTR_TC) {
 490     auto ptc = hazptr_tc_tls();
 491     if (LIKELY(ptc != nullptr)) {
 492       auto& tc = *ptc;
 493       auto count = tc.count();
 494       if ((M <= HAZPTR_TC_SIZE) && (count + M <= HAZPTR_TC_SIZE)) {
 495         for (size_t i = 0; i < M; ++i) {
 496           tc[count + i].hprec_ = h[i].hazptr_;
 497           DEBUG_PRINT(i << " " << &h[i]);
 498           new (&h[i]) hazptr_holder(nullptr);
 499           DEBUG_PRINT(
 500               i << " " << &h[i] << " " << h[i].domain_ << " " << h[i].hazptr_);
 501         }
 502         tc.count_ = count + M;
 503         return;
 504       }
 505     }
 506   }
 507   // slow path
 508   for (size_t i = 0; i < M; ++i) {
 509     h[i].~hazptr_holder();
 510   }
 511 }
 512
 513 template <size_t M>
 514 FOLLY_ALWAYS_INLINE hazptr_array<M>& hazptr_array<M>::operator=(
 515     hazptr_array&& other) noexcept {
 516   DEBUG_PRINT(this << " " << M << " " << &other);
 517   auto h = reinterpret_cast<hazptr_holder*>(&raw_);
 518   for (size_t i = 0; i < M; ++i) {
 519     h[i] = std::move(other[i]);
 520     DEBUG_PRINT(i << " " << &h[i] << " " << &other[i]);
 521   }
 522   empty_ = other.empty_;
 523   other.empty_ = true;
 524   return *this;
 525 }
 526
 527 template <size_t M>
 528 FOLLY_ALWAYS_INLINE hazptr_holder& hazptr_array<M>::operator[](
 529     size_t i) noexcept {
 530   auto h = reinterpret_cast<hazptr_holder*>(&raw_);
 531   DCHECK(i < M);
 532   return h[i];
 533 }
 534
 535 /**
 536  *  hazptr_local
 537  */
 538
 539 template <size_t M>
 540 FOLLY_ALWAYS_INLINE hazptr_local<M>::hazptr_local() {
 541   auto h = reinterpret_cast<hazptr_holder*>(&raw_);
 542   if (HAZPTR_TC) {
 543     auto ptc = hazptr_tc_tls();
 544     if (LIKELY(ptc != nullptr)) {
 545       auto& tc = *ptc;
 546       auto count = tc.count();
 547       if (M <= count) {
 548         if (kIsDebug) {
 549           DCHECK(!tc.local_);
 550           tc.local_ = true;
 551         }
 552         // Fast path
 553         for (size_t i = 0; i < M; ++i) {
 554           auto hprec = tc[i].hprec_;
 555           DCHECK(hprec != nullptr);
 556           DEBUG_PRINT(i << " " << &h[i]);
 557           new (&h[i]) hazptr_holder(nullptr);
 558           h[i].hazptr_ = hprec;
 559           DEBUG_PRINT(
 560               i << " " << &h[i] << " " << h[i].domain_ << " " << h[i].hazptr_);
 561         }
 562         return;
 563       }
 564     }
 565   }
 566   // Slow path
 567   need_destruct_ = true;
 568   for (size_t i = 0; i < M; ++i) {
 569     new (&h[i]) hazptr_holder;
 570     DEBUG_PRINT(
 571         i << " " << &h[i] << " " << h[i].domain_ << " " << h[i].hazptr_);
 572   }
 573 }
 574
 575 template <size_t M>
 576 FOLLY_ALWAYS_INLINE hazptr_local<M>::~hazptr_local() {
 577   if (LIKELY(!need_destruct_)) {
 578     if (kIsDebug) {
 579       auto ptc = hazptr_tc_tls();
 580       DCHECK(ptc != nullptr);
 581       auto& tc = *ptc;
 582       DCHECK(tc.local_);
 583       tc.local_ = false;
 584     }
 585     return;
 586   }
 587   // Slow path
 588   auto h = reinterpret_cast<hazptr_holder*>(&raw_);
 589   for (size_t i = 0; i < M; ++i) {
 590     h[i].~hazptr_holder();
 591   }
 592 }
 593
 594 template <size_t M>
 595 FOLLY_ALWAYS_INLINE hazptr_holder& hazptr_local<M>::operator[](
 596     size_t i) noexcept {
 597   auto h = reinterpret_cast<hazptr_holder*>(&raw_);
 598   DCHECK(i < M);
 599   return h[i];
 600 }
 601
 602 ////////////////////////////////////////////////////////////////////////////////
 603 // [TODO]:
 604 // - Control of reclamation (when and by whom)
 605 // - End-to-end lock-free implementation
 606
 607 /** Definition of default_hazptr_domain() */
 608
 609 FOLLY_ALWAYS_INLINE hazptr_domain& default_hazptr_domain() {
 610   DEBUG_PRINT(&default_domain_);
 611   return default_domain_;
 612 }
 613
 614 template <typename T, typename D>
 615 FOLLY_ALWAYS_INLINE void hazptr_retire(T* obj, D reclaim) {
 616   default_hazptr_domain().retire(obj, std::move(reclaim));
 617 }
 618
 619 /** hazptr_rec */
 620
 621 FOLLY_ALWAYS_INLINE void hazptr_rec::set(const void* p) noexcept {
 622   DEBUG_PRINT(this << " " << p);
 623   hazptr_.store(p, std::memory_order_release);
 624 }
 625
 626 inline const void* hazptr_rec::get() const noexcept {
 627   auto p = hazptr_.load(std::memory_order_acquire);
 628   DEBUG_PRINT(this << " " << p);
 629   return p;
 630 }
 631
 632 FOLLY_ALWAYS_INLINE void hazptr_rec::clear() noexcept {
 633   DEBUG_PRINT(this);
 634   hazptr_.store(nullptr, std::memory_order_release);
 635 }
 636
 637 inline bool hazptr_rec::isActive() noexcept {
 638   return active_.load(std::memory_order_acquire);
 639 }
 640
 641 inline bool hazptr_rec::tryAcquire() noexcept {
 642   bool active = isActive();
 643   if (!active &&
 644       active_.compare_exchange_strong(
 645           active, true, std::memory_order_release, std::memory_order_relaxed)) {
 646     DEBUG_PRINT(this);
 647     return true;
 648   }
 649   return false;
 650 }
 651
 652 inline void hazptr_rec::release() noexcept {
 653   DEBUG_PRINT(this);
 654   active_.store(false, std::memory_order_release);
 655 }
 656
 657 /** hazptr_obj */
 658
 659 inline const void* hazptr_obj::getObjPtr() const {
 660   DEBUG_PRINT(this);
 661   return this;
 662 }
 663
 664 /** hazptr_domain */
 665
 666 template <typename T, typename D>
 667 void hazptr_domain::retire(T* obj, D reclaim) {
 668   struct hazptr_retire_node : hazptr_obj {
 669     std::unique_ptr<T, D> obj_;
 670
 671     hazptr_retire_node(T* obj, D reclaim) : obj_{obj, std::move(reclaim)} {}
 672   };
 673
 674   auto node = new hazptr_retire_node(obj, std::move(reclaim));
 675   node->reclaim_ = [](hazptr_obj* p) {
 676     delete static_cast<hazptr_retire_node*>(p);
 677   };
 678   objRetire(node);
 679 }
 680
 681 inline hazptr_domain::~hazptr_domain() {
 682   DEBUG_PRINT(this);
 683   { /* reclaim all remaining retired objects */
 684     hazptr_obj* next;
 685     auto retired = retired_.exchange(nullptr);
 686     while (retired) {
 687       for (auto p = retired; p; p = next) {
 688         next = p->next_;
 689         DCHECK(p != next);
 690         DEBUG_PRINT(this << " " << p << " " << p->reclaim_);
 691         (*(p->reclaim_))(p);
 692       }
 693       retired = retired_.exchange(nullptr);
 694     }
 695   }
 696   /* Leak the data for the default domain to avoid destruction order
 697    * issues with thread caches.
 698    */
 699   if (this != &default_hazptr_domain()) {
 700     /* free all hazptr_rec-s */
 701     hazptr_rec* next;
 702     for (auto p = hazptrs_.load(std::memory_order_acquire); p; p = next) {
 703       next = p->next_;
 704       DCHECK(!p->isActive());
 705       mr_->deallocate(static_cast<void*>(p), sizeof(hazptr_rec));
 706     }
 707   }
 708 }
 709
 710 inline hazptr_rec* hazptr_domain::hazptrAcquire() {
 711   hazptr_rec* p;
 712   hazptr_rec* next;
 713   for (p = hazptrs_.load(std::memory_order_acquire); p; p = next) {
 714     next = p->next_;
 715     if (p->tryAcquire()) {
 716       return p;
 717     }
 718   }
 719   p = static_cast<hazptr_rec*>(mr_->allocate(sizeof(hazptr_rec)));
 720   DEBUG_PRINT(this << " " << p << " " << sizeof(hazptr_rec));
 721   if (p == nullptr) {
 722     return nullptr;
 723   }
 724   p->active_.store(true, std::memory_order_relaxed);
 725   p->next_ = hazptrs_.load(std::memory_order_acquire);
 726   while (!hazptrs_.compare_exchange_weak(
 727       p->next_, p, std::memory_order_release, std::memory_order_acquire)) {
 728     /* keep trying */;
 729   }
 730   auto hcount = hcount_.fetch_add(1);
 731   DEBUG_PRINT(this << " " << p << " " << sizeof(hazptr_rec) << " " << hcount);
 732   return p;
 733 }
 734
 735 inline void hazptr_domain::hazptrRelease(hazptr_rec* p) noexcept {
 736   DEBUG_PRINT(this << " " << p);
 737   p->release();
 738 }
 739
 740 inline int
 741 hazptr_domain::pushRetired(hazptr_obj* head, hazptr_obj* tail, int count) {
 742   /*** Full fence ***/ hazptr_mb::light();
 743   tail->next_ = retired_.load(std::memory_order_acquire);
 744   while (!retired_.compare_exchange_weak(
 745       tail->next_,
 746       head,
 747       std::memory_order_release,
 748       std::memory_order_acquire)) {
 749   }
 750   return rcount_.fetch_add(count) + count;
 751 }
 752
 753 inline bool hazptr_domain::reachedThreshold(int rcount) {
 754   return (
 755       rcount >= HAZPTR_SCAN_THRESHOLD &&
 756       rcount >= HAZPTR_SCAN_MULT * hcount_.load(std::memory_order_acquire));
 757 }
 758
 759 inline void hazptr_domain::objRetire(hazptr_obj* p) {
 760   auto rcount = pushRetired(p, p, 1);
 761   if (reachedThreshold(rcount)) {
 762     tryBulkReclaim();
 763   }
 764 }
 765
 766 inline void hazptr_domain::tryBulkReclaim() {
 767   DEBUG_PRINT(this);
 768   do {
 769     auto hcount = hcount_.load(std::memory_order_acquire);
 770     auto rcount = rcount_.load(std::memory_order_acquire);
 771     if (rcount < HAZPTR_SCAN_THRESHOLD || rcount < HAZPTR_SCAN_MULT * hcount) {
 772       return;
 773     }
 774     if (rcount_.compare_exchange_weak(
 775             rcount, 0, std::memory_order_release, std::memory_order_relaxed)) {
 776       break;
 777     }
 778   } while (true);
 779   bulkReclaim();
 780 }
 781
 782 inline void hazptr_domain::bulkReclaim() {
 783   DEBUG_PRINT(this);
 784   /*** Full fence ***/ hazptr_mb::heavy();
 785   auto p = retired_.exchange(nullptr, std::memory_order_acquire);
 786   auto h = hazptrs_.load(std::memory_order_acquire);
 787   std::unordered_set<const void*> hs; // TODO lock-free alternative
 788   for (; h; h = h->next_) {
 789     hs.insert(h->get());
 790   }
 791   int rcount = 0;
 792   hazptr_obj* retired = nullptr;
 793   hazptr_obj* tail = nullptr;
 794   hazptr_obj* next;
 795   for (; p; p = next) {
 796     next = p->next_;
 797     DCHECK(p != next);
 798     if (hs.count(p->getObjPtr()) == 0) {
 799       DEBUG_PRINT(this << " " << p << " " << p->reclaim_);
 800       (*(p->reclaim_))(p);
 801     } else {
 802       p->next_ = retired;
 803       retired = p;
 804       if (tail == nullptr) {
 805         tail = p;
 806       }
 807       ++rcount;
 808     }
 809   }
 810   if (tail) {
 811     pushRetired(retired, tail, rcount);
 812   }
 813 }
 814
 815 /** hazptr_stats */
 816
 817 class hazptr_stats {
 818  public:
 819   ~hazptr_stats();
 820   void light();
 821   void heavy();
 822   void seq_cst();
 823
 824  private:
 825   std::atomic<uint64_t> light_{0};
 826   std::atomic<uint64_t> heavy_{0};
 827   std::atomic<uint64_t> seq_cst_{0};
 828 };
 829
 830 extern hazptr_stats hazptr_stats_;
 831
 832 inline hazptr_stats::~hazptr_stats() {
 833   DEBUG_PRINT(this << " light " << light_.load());
 834   DEBUG_PRINT(this << " heavy " << heavy_.load());
 835   DEBUG_PRINT(this << " seq_cst " << seq_cst_.load());
 836 }
 837
 838 FOLLY_ALWAYS_INLINE void hazptr_stats::light() {
 839   if (HAZPTR_STATS) {
 840     /* atomic */ ++light_;
 841   }
 842 }
 843
 844 inline void hazptr_stats::heavy() {
 845   if (HAZPTR_STATS) {
 846     /* atomic */ ++heavy_;
 847   }
 848 }
 849
 850 inline void hazptr_stats::seq_cst() {
 851   if (HAZPTR_STATS) {
 852     /* atomic */ ++seq_cst_;
 853   }
 854 }
 855
 856 /** hazptr_mb */
 857
 858 FOLLY_ALWAYS_INLINE void hazptr_mb::light() {
 859   DEBUG_PRINT("");
 860   if (HAZPTR_AMB) {
 861     folly::asymmetricLightBarrier();
 862     INC_HAZPTR_STATS(light);
 863   } else {
 864     atomic_thread_fence(std::memory_order_seq_cst);
 865     INC_HAZPTR_STATS(seq_cst);
 866   }
 867 }
 868
 869 inline void hazptr_mb::heavy() {
 870   DEBUG_PRINT("");
 871   if (HAZPTR_AMB) {
 872     folly::asymmetricHeavyBarrier(AMBFlags::EXPEDITED);
 873     INC_HAZPTR_STATS(heavy);
 874   } else {
 875     atomic_thread_fence(std::memory_order_seq_cst);
 876     INC_HAZPTR_STATS(seq_cst);
 877   }
 878 }
 879
 880 /**
 881  *  TLS structures
 882  */
 883
 884 /**
 885  *  hazptr_tc structures
 886  */
 887
 888 /** hazptr_tc_entry */
 889
 890 FOLLY_ALWAYS_INLINE void hazptr_tc_entry::fill(hazptr_rec* hprec) {
 891   hprec_ = hprec;
 892   DEBUG_PRINT(this << " " << hprec);
 893 }
 894
 895 FOLLY_ALWAYS_INLINE hazptr_rec* hazptr_tc_entry::get() {
 896   auto hprec = hprec_;
 897   DEBUG_PRINT(this << " " << hprec);
 898   return hprec;
 899 }
 900
 901 inline void hazptr_tc_entry::evict() {
 902   auto hprec = hprec_;
 903   hprec->release();
 904   DEBUG_PRINT(this << " " << hprec);
 905 }
 906
 907 /** hazptr_tc */
 908
 909 FOLLY_ALWAYS_INLINE hazptr_tc_entry& hazptr_tc::operator[](size_t i) {
 910   DCHECK(i <= HAZPTR_TC_SIZE);
 911   return entry_[i];
 912 }
 913
 914 FOLLY_ALWAYS_INLINE hazptr_rec* hazptr_tc::get() {
 915   if (LIKELY(count_ != 0)) {
 916     auto hprec = entry_[--count_].get();
 917     DEBUG_PRINT(this << " " << hprec);
 918     return hprec;
 919   }
 920   DEBUG_PRINT(this << " nullptr");
 921   return nullptr;
 922 }
 923
 924 FOLLY_ALWAYS_INLINE bool hazptr_tc::put(hazptr_rec* hprec) {
 925   if (LIKELY(count_ < HAZPTR_TC_SIZE)) {
 926     entry_[count_++].fill(hprec);
 927     DEBUG_PRINT(this << " " << count_ - 1);
 928     return true;
 929   }
 930   return false;
 931 }
 932
 933 FOLLY_ALWAYS_INLINE size_t hazptr_tc::count() {
 934   return count_;
 935 }
 936
 937 /** hazptr_tc free functions */
 938
 939 FOLLY_ALWAYS_INLINE hazptr_tc* hazptr_tc_tls() {
 940   DEBUG_PRINT(tls_state_);
 941   if (LIKELY(tls_state_ == TLS_ALIVE)) {
 942     DEBUG_PRINT(tls_state_);
 943     return &tls_tc_data_;
 944   } else if (tls_state_ == TLS_UNINITIALIZED) {
 945     tls_life_odr_use();
 946     return &tls_tc_data_;
 947   }
 948   return nullptr;
 949 }
 950
 951 inline void hazptr_tc_init() {
 952   DEBUG_PRINT("");
 953   auto& tc = tls_tc_data_;
 954   DEBUG_PRINT(&tc);
 955   tc.count_ = 0;
 956   if (kIsDebug) {
 957     tc.local_ = false;
 958   }
 959 }
 960
 961 inline void hazptr_tc_shutdown() {
 962   auto& tc = tls_tc_data_;
 963   DEBUG_PRINT(&tc);
 964   for (size_t i = 0; i < tc.count_; ++i) {
 965     tc.entry_[i].evict();
 966   }
 967 }
 968
 969 FOLLY_ALWAYS_INLINE hazptr_rec* hazptr_tc_try_get() {
 970   DEBUG_PRINT(TLS_UNINITIALIZED << TLS_ALIVE << TLS_DESTROYED);
 971   DEBUG_PRINT(tls_state_);
 972   if (LIKELY(tls_state_ == TLS_ALIVE)) {
 973     DEBUG_PRINT(tls_state_);
 974     return tls_tc_data_.get();
 975   } else if (tls_state_ == TLS_UNINITIALIZED) {
 976     tls_life_odr_use();
 977     return tls_tc_data_.get();
 978   }
 979   return nullptr;
 980 }
 981
 982 FOLLY_ALWAYS_INLINE bool hazptr_tc_try_put(hazptr_rec* hprec) {
 983   DEBUG_PRINT(tls_state_);
 984   if (LIKELY(tls_state_ == TLS_ALIVE)) {
 985     DEBUG_PRINT(tls_state_);
 986     return tls_tc_data_.put(hprec);
 987   }
 988   return false;
 989 }
 990
 991 /**
 992  *  hazptr_priv
 993  */
 994
 995 inline void hazptr_priv::push(hazptr_obj* obj) {
 996   auto& domain = default_hazptr_domain();
 997   obj->next_ = nullptr;
 998   if (tail_) {
 999     tail_->next_ = obj;
1000   } else {
1001     if (!active_) {
1002       domain.objRetire(obj);
1003       return;
1004     }
1005     head_ = obj;
1006   }
1007   tail_ = obj;
1008   if (++rcount_ >= HAZPTR_PRIV_THRESHOLD) {
1009     pushAllToDomain();
1010   }
1011 }
1012
1013 inline void hazptr_priv::pushAllToDomain() {
1014   auto& domain = default_hazptr_domain();
1015   domain.pushRetired(head_, tail_, rcount_);
1016   head_ = nullptr;
1017   tail_ = nullptr;
1018   rcount_ = 0;
1019   domain.tryBulkReclaim();
1020 }
1021
1022 inline void hazptr_priv_init() {
1023   auto& priv = tls_priv_data_;
1024   DEBUG_PRINT(&priv);
1025   priv.head_ = nullptr;
1026   priv.tail_ = nullptr;
1027   priv.rcount_ = 0;
1028   priv.active_ = true;
1029 }
1030
1031 inline void hazptr_priv_shutdown() {
1032   auto& priv = tls_priv_data_;
1033   DEBUG_PRINT(&priv);
1034   DCHECK(priv.active_);
1035   priv.active_ = false;
1036   if (priv.tail_) {
1037     priv.pushAllToDomain();
1038   }
1039 }
1040
1041 inline bool hazptr_priv_try_retire(hazptr_obj* obj) {
1042   DEBUG_PRINT(tls_state_);
1043   if (tls_state_ == TLS_ALIVE) {
1044     DEBUG_PRINT(tls_state_);
1045     tls_priv_data_.push(obj);
1046     return true;
1047   } else if (tls_state_ == TLS_UNINITIALIZED) {
1048     DEBUG_PRINT(tls_state_);
1049     tls_life_odr_use();
1050     tls_priv_data_.push(obj);
1051     return true;
1052   }
1053   return false;
1054 }
1055
1056 /** hazptr_tls_life */
1057
1058 inline void tls_life_odr_use() {
1059   DEBUG_PRINT(tls_state_);
1060   CHECK(tls_state_ == TLS_UNINITIALIZED);
1061   auto volatile tlsOdrUse = &tls_life_;
1062   CHECK(tlsOdrUse != nullptr);
1063   DEBUG_PRINT(tlsOdrUse);
1064 }
1065
1066 inline hazptr_tls_life::hazptr_tls_life() {
1067   DEBUG_PRINT(this);
1068   CHECK(tls_state_ == TLS_UNINITIALIZED);
1069   hazptr_tc_init();
1070   hazptr_priv_init();
1071   tls_state_ = TLS_ALIVE;
1072 }
1073
1074 inline hazptr_tls_life::~hazptr_tls_life() {
1075   DEBUG_PRINT(this);
1076   CHECK(tls_state_ == TLS_ALIVE);
1077   hazptr_tc_shutdown();
1078   hazptr_priv_shutdown();
1079   tls_state_ = TLS_DESTROYED;
1080 }
1081
1082 /** hazptr_obj_batch */
1083 /*  Only for default domain. Supports only hazptr_obj_base_refcounted
1084  *  and a thread-safe access only, for now. */
1085
1086 class hazptr_obj_batch {
1087   static constexpr size_t DefaultThreshold = 20;
1088   hazptr_obj* head_{nullptr};
1089   hazptr_obj* tail_{nullptr};
1090   size_t rcount_{0};
1091   size_t threshold_{DefaultThreshold};
1092
1093  public:
1094   hazptr_obj_batch() {}
1095   hazptr_obj_batch(hazptr_obj* head, hazptr_obj* tail, size_t rcount)
1096       : head_(head), tail_(tail), rcount_(rcount) {}
1097
1098   ~hazptr_obj_batch() {
1099     retire_all();
1100   }
1101
1102   /* Prepare a hazptr_obj_base_refcounted for retirement but don't
1103        push it the domain yet. Return true if the batch is ready. */
1104   template <typename T, typename D = std::default_delete<T>>
1105   hazptr_obj_batch prep_retire_refcounted(
1106       hazptr_obj_base_refcounted<T, D>* obj,
1107       D deleter = {}) {
1108     obj->preRetire(deleter);
1109     obj->next_ = head_;
1110     head_ = obj;
1111     if (tail_ == nullptr) {
1112       tail_ = obj;
1113     }
1114     if (++rcount_ < threshold_) {
1115       return hazptr_obj_batch();
1116     } else {
1117       auto head = head_;
1118       auto tail = tail_;
1119       auto rcount = rcount_;
1120       clear();
1121       return hazptr_obj_batch(head, tail, rcount);
1122     }
1123   }
1124
1125   bool empty() {
1126     return rcount_ == 0;
1127   }
1128
1129   void retire_all() {
1130     if (!empty()) {
1131       auto& domain = default_hazptr_domain();
1132       domain.pushRetired(head_, tail_, rcount_);
1133       domain.tryBulkReclaim();
1134       clear();
1135     }
1136   }
1137
1138   void set_threshold(size_t thresh) {
1139     threshold_ = thresh;
1140   }
1141
1142  private:
1143   void clear() {
1144     head_ = nullptr;
1145     tail_ = nullptr;
1146     rcount_ = 0;
1147   }
1148 };
1149
1150 } // namespace hazptr
1151 } // namespace folly