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