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