folly/experimental/hazptr/hazptr-impl.h

   1 /*
   2  * Copyright 2017 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 /* override-include-guard */
  18 #ifndef HAZPTR_H
  19 #error "This should only be included by hazptr.h"
  20 #endif
  21
  22 /* quality of implementation switches */
  23
  24 // NOTE: The #ifndef pattern is prone to ODR violation. Its use for
  25 // quality of implementation options is temporary. Eventually these
  26 // options should be added to the API in future API extensions.
  27
  28 #ifndef HAZPTR_AMB
  29 #define HAZPTR_AMB true
  30 #endif
  31
  32 #ifndef HAZPTR_TC
  33 #define HAZPTR_TC true
  34 #endif
  35
  36 #ifndef HAZPTR_TC_SIZE
  37 #define HAZPTR_TC_SIZE 10
  38 #endif
  39
  40 #ifndef HAZPTR_PRIV
  41 #define HAZPTR_PRIV true
  42 #endif
  43
  44 #ifndef HAZPTR_ONE_DOMAIN
  45 #define HAZPTR_ONE_DOMAIN false
  46 #endif
  47
  48 #ifndef HAZPTR_SCAN_MULT
  49 #define HAZPTR_SCAN_MULT 2
  50 #endif
  51
  52 #ifndef HAZPTR_SCAN_THRESHOLD
  53 #define HAZPTR_SCAN_THRESHOLD 1000
  54 #endif
  55
  56 /* stats switch */
  57 #ifndef HAZPTR_STATS
  58 #define HAZPTR_STATS false
  59 #endif
  60
  61 #include <folly/concurrency/CacheLocality.h>
  62 #include <folly/experimental/hazptr/debug.h>
  63 #include <folly/synchronization/AsymmetricMemoryBarrier.h>
  64
  65 #include <mutex> // for thread caching
  66 #include <unordered_set> // for hash set in bulk reclamation
  67
  68 namespace folly {
  69 namespace hazptr {
  70
  71 /**
  72  *  Helper classes and functions
  73  */
  74
  75 /** hazptr_stats */
  76
  77 class hazptr_stats;
  78
  79 #if HAZPTR_STATS
  80 #define INC_HAZPTR_STATS(x) hazptr_stats_.x()
  81 #else
  82 #define INC_HAZPTR_STATS(x)
  83 #endif
  84
  85 /** hazptr_mb */
  86
  87 class hazptr_mb {
  88  public:
  89   static void light();
  90   static void heavy();
  91 };
  92
  93 /**
  94  *  TLS structures
  95  */
  96
  97 /** TLS life state */
  98
  99 enum hazptr_tls_state { TLS_ALIVE, TLS_UNINITIALIZED, TLS_DESTROYED };
 100
 101 /** hazptr_tc structures
 102  *  Thread caching of hazptr_rec-s that belong to the default domain.
 103  */
 104
 105 struct hazptr_tc_entry {
 106   hazptr_rec* hprec_;
 107
 108   void fill(hazptr_rec* hprec);
 109   hazptr_rec* get();
 110   void evict();
 111 };
 112
 113 static_assert(
 114     std::is_trivial<hazptr_tc_entry>::value,
 115     "hazptr_tc_entry must be trivial"
 116     " to avoid a branch to check initialization");
 117
 118 struct hazptr_tc {
 119   hazptr_tc_entry entry_[HAZPTR_TC_SIZE];
 120   size_t count_;
 121 #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   }
 644   auto hcount = hcount_.fetch_add(1);
 645   DEBUG_PRINT(this << " " << p << " " << sizeof(hazptr_rec) << " " << hcount);
 646   return p;
 647 }
 648
 649 inline void hazptr_domain::hazptrRelease(hazptr_rec* p) noexcept {
 650   DEBUG_PRINT(this << " " << p);
 651   p->release();
 652 }
 653
 654 inline int
 655 hazptr_domain::pushRetired(hazptr_obj* head, hazptr_obj* tail, int count) {
 656   /*** Full fence ***/ hazptr_mb::light();
 657   tail->next_ = retired_.load(std::memory_order_acquire);
 658   while (!retired_.compare_exchange_weak(
 659       tail->next_,
 660       head,
 661       std::memory_order_release,
 662       std::memory_order_acquire)) {
 663   }
 664   return rcount_.fetch_add(count) + count;
 665 }
 666
 667 inline bool hazptr_domain::reachedThreshold(int rcount) {
 668   return (
 669       rcount >= HAZPTR_SCAN_THRESHOLD &&
 670       rcount >= HAZPTR_SCAN_MULT * hcount_.load(std::memory_order_acquire));
 671 }
 672
 673 inline void hazptr_domain::objRetire(hazptr_obj* p) {
 674   auto rcount = pushRetired(p, p, 1);
 675   if (reachedThreshold(rcount)) {
 676     tryBulkReclaim();
 677   }
 678 }
 679
 680 inline void hazptr_domain::tryBulkReclaim() {
 681   DEBUG_PRINT(this);
 682   do {
 683     auto hcount = hcount_.load(std::memory_order_acquire);
 684     auto rcount = rcount_.load(std::memory_order_acquire);
 685     if (rcount < HAZPTR_SCAN_THRESHOLD || rcount < HAZPTR_SCAN_MULT * hcount) {
 686       return;
 687     }
 688     if (rcount_.compare_exchange_weak(
 689             rcount, 0, std::memory_order_release, std::memory_order_relaxed)) {
 690       break;
 691     }
 692   } while (true);
 693   bulkReclaim();
 694 }
 695
 696 inline void hazptr_domain::bulkReclaim() {
 697   DEBUG_PRINT(this);
 698   /*** Full fence ***/ hazptr_mb::heavy();
 699   auto p = retired_.exchange(nullptr, std::memory_order_acquire);
 700   auto h = hazptrs_.load(std::memory_order_acquire);
 701   std::unordered_set<const void*> hs; // TODO lock-free alternative
 702   for (; h; h = h->next_) {
 703     hs.insert(h->get());
 704   }
 705   int rcount = 0;
 706   hazptr_obj* retired = nullptr;
 707   hazptr_obj* tail = nullptr;
 708   hazptr_obj* next;
 709   for (; p; p = next) {
 710     next = p->next_;
 711     if (hs.count(p->getObjPtr()) == 0) {
 712       DEBUG_PRINT(this << " " << p << " " << p->reclaim_);
 713       (*(p->reclaim_))(p);
 714     } else {
 715       p->next_ = retired;
 716       retired = p;
 717       if (tail == nullptr) {
 718         tail = p;
 719       }
 720       ++rcount;
 721     }
 722   }
 723   if (tail) {
 724     pushRetired(retired, tail, rcount);
 725   }
 726 }
 727
 728 /** hazptr_stats */
 729
 730 class hazptr_stats {
 731  public:
 732   ~hazptr_stats();
 733   void light();
 734   void heavy();
 735   void seq_cst();
 736
 737  private:
 738   std::atomic<uint64_t> light_{0};
 739   std::atomic<uint64_t> heavy_{0};
 740   std::atomic<uint64_t> seq_cst_{0};
 741 };
 742
 743 extern hazptr_stats hazptr_stats_;
 744
 745 inline hazptr_stats::~hazptr_stats() {
 746   DEBUG_PRINT(this << " light " << light_.load());
 747   DEBUG_PRINT(this << " heavy " << heavy_.load());
 748   DEBUG_PRINT(this << " seq_cst " << seq_cst_.load());
 749 }
 750
 751 FOLLY_ALWAYS_INLINE void hazptr_stats::light() {
 752   if (HAZPTR_STATS) {
 753     /* atomic */ ++light_;
 754   }
 755 }
 756
 757 inline void hazptr_stats::heavy() {
 758   if (HAZPTR_STATS) {
 759     /* atomic */ ++heavy_;
 760   }
 761 }
 762
 763 inline void hazptr_stats::seq_cst() {
 764   if (HAZPTR_STATS) {
 765     /* atomic */ ++seq_cst_;
 766   }
 767 }
 768
 769 /** hazptr_mb */
 770
 771 FOLLY_ALWAYS_INLINE void hazptr_mb::light() {
 772   DEBUG_PRINT("");
 773   if (HAZPTR_AMB) {
 774     folly::asymmetricLightBarrier();
 775     INC_HAZPTR_STATS(light);
 776   } else {
 777     atomic_thread_fence(std::memory_order_seq_cst);
 778     INC_HAZPTR_STATS(seq_cst);
 779   }
 780 }
 781
 782 inline void hazptr_mb::heavy() {
 783   DEBUG_PRINT("");
 784   if (HAZPTR_AMB) {
 785     folly::asymmetricHeavyBarrier(AMBFlags::EXPEDITED);
 786     INC_HAZPTR_STATS(heavy);
 787   } else {
 788     atomic_thread_fence(std::memory_order_seq_cst);
 789     INC_HAZPTR_STATS(seq_cst);
 790   }
 791 }
 792
 793 /**
 794  *  TLS structures
 795  */
 796
 797 /**
 798  *  hazptr_tc structures
 799  */
 800
 801 /** hazptr_tc_entry */
 802
 803 FOLLY_ALWAYS_INLINE void hazptr_tc_entry::fill(hazptr_rec* hprec) {
 804   hprec_ = hprec;
 805   DEBUG_PRINT(this << " " << hprec);
 806 }
 807
 808 FOLLY_ALWAYS_INLINE hazptr_rec* hazptr_tc_entry::get() {
 809   auto hprec = hprec_;
 810   DEBUG_PRINT(this << " " << hprec);
 811   return hprec;
 812 }
 813
 814 inline void hazptr_tc_entry::evict() {
 815   auto hprec = hprec_;
 816   hprec->release();
 817   DEBUG_PRINT(this << " " << hprec);
 818 }
 819
 820 /** hazptr_tc */
 821
 822 FOLLY_ALWAYS_INLINE hazptr_tc_entry& hazptr_tc::operator[](size_t i) {
 823   DCHECK(i <= HAZPTR_TC_SIZE);
 824   return entry_[i];
 825 }
 826
 827 FOLLY_ALWAYS_INLINE hazptr_rec* hazptr_tc::get() {
 828   if (LIKELY(count_ != 0)) {
 829     auto hprec = entry_[--count_].get();
 830     DEBUG_PRINT(this << " " << hprec);
 831     return hprec;
 832   }
 833   DEBUG_PRINT(this << " nullptr");
 834   return nullptr;
 835 }
 836
 837 FOLLY_ALWAYS_INLINE bool hazptr_tc::put(hazptr_rec* hprec) {
 838   if (LIKELY(count_ < HAZPTR_TC_SIZE)) {
 839     entry_[count_++].fill(hprec);
 840     DEBUG_PRINT(this << " " << count_ - 1);
 841     return true;
 842   }
 843   return false;
 844 }
 845
 846 FOLLY_ALWAYS_INLINE size_t hazptr_tc::count() {
 847   return count_;
 848 }
 849
 850 /** hazptr_tc free functions */
 851
 852 FOLLY_ALWAYS_INLINE hazptr_tc* hazptr_tc_tls() {
 853   DEBUG_PRINT(tls_state_);
 854   if (LIKELY(tls_state_ == TLS_ALIVE)) {
 855     DEBUG_PRINT(tls_state_);
 856     return &tls_tc_data_;
 857   } else if (tls_state_ == TLS_UNINITIALIZED) {
 858     tls_life_odr_use();
 859     return &tls_tc_data_;
 860   }
 861   return nullptr;
 862 }
 863
 864 inline void hazptr_tc_init() {
 865   DEBUG_PRINT("");
 866   auto& tc = tls_tc_data_;
 867   DEBUG_PRINT(&tc);
 868   tc.count_ = 0;
 869 #ifndef NDEBUG
 870   tc.local_ = false;
 871 #endif
 872 }
 873
 874 inline void hazptr_tc_shutdown() {
 875   auto& tc = tls_tc_data_;
 876   DEBUG_PRINT(&tc);
 877   for (size_t i = 0; i < tc.count_; ++i) {
 878     tc.entry_[i].evict();
 879   }
 880 }
 881
 882 FOLLY_ALWAYS_INLINE hazptr_rec* hazptr_tc_try_get() {
 883   DEBUG_PRINT(TLS_UNINITIALIZED << TLS_ALIVE << TLS_DESTROYED);
 884   DEBUG_PRINT(tls_state_);
 885   if (LIKELY(tls_state_ == TLS_ALIVE)) {
 886     DEBUG_PRINT(tls_state_);
 887     return tls_tc_data_.get();
 888   } else if (tls_state_ == TLS_UNINITIALIZED) {
 889     tls_life_odr_use();
 890     return tls_tc_data_.get();
 891   }
 892   return nullptr;
 893 }
 894
 895 FOLLY_ALWAYS_INLINE bool hazptr_tc_try_put(hazptr_rec* hprec) {
 896   DEBUG_PRINT(tls_state_);
 897   if (LIKELY(tls_state_ == TLS_ALIVE)) {
 898     DEBUG_PRINT(tls_state_);
 899     return tls_tc_data_.put(hprec);
 900   }
 901   return false;
 902 }
 903
 904 /**
 905  *  hazptr_priv
 906  */
 907
 908 inline void hazptr_priv::push(hazptr_obj* obj) {
 909   auto& domain = default_hazptr_domain();
 910   obj->next_ = nullptr;
 911   if (tail_) {
 912     tail_->next_ = obj;
 913   } else {
 914     if (!active_) {
 915       domain.objRetire(obj);
 916       return;
 917     }
 918     head_ = obj;
 919   }
 920   tail_ = obj;
 921   ++rcount_;
 922   if (domain.reachedThreshold(rcount_)) {
 923     pushAllToDomain();
 924   }
 925 }
 926
 927 inline void hazptr_priv::pushAllToDomain() {
 928   auto& domain = default_hazptr_domain();
 929   domain.pushRetired(head_, tail_, rcount_);
 930   head_ = nullptr;
 931   tail_ = nullptr;
 932   rcount_ = 0;
 933   domain.tryBulkReclaim();
 934 }
 935
 936 inline void hazptr_priv_init() {
 937   auto& priv = tls_priv_data_;
 938   DEBUG_PRINT(&priv);
 939   priv.head_ = nullptr;
 940   priv.tail_ = nullptr;
 941   priv.rcount_ = 0;
 942   priv.active_ = true;
 943 }
 944
 945 inline void hazptr_priv_shutdown() {
 946   auto& priv = tls_priv_data_;
 947   DEBUG_PRINT(&priv);
 948   DCHECK(priv.active_);
 949   priv.active_ = false;
 950   if (priv.tail_) {
 951     priv.pushAllToDomain();
 952   }
 953 }
 954
 955 inline bool hazptr_priv_try_retire(hazptr_obj* obj) {
 956   DEBUG_PRINT(tls_state_);
 957   if (tls_state_ == TLS_ALIVE) {
 958     DEBUG_PRINT(tls_state_);
 959     tls_priv_data_.push(obj);
 960     return true;
 961   } else if (tls_state_ == TLS_UNINITIALIZED) {
 962     DEBUG_PRINT(tls_state_);
 963     tls_life_odr_use();
 964     tls_priv_data_.push(obj);
 965     return true;
 966   }
 967   return false;
 968 }
 969
 970 /** hazptr_tls_life */
 971
 972 inline void tls_life_odr_use() {
 973   DEBUG_PRINT(tls_state_);
 974   CHECK(tls_state_ == TLS_UNINITIALIZED);
 975   auto volatile tlsOdrUse = &tls_life_;
 976   CHECK(tlsOdrUse != nullptr);
 977   DEBUG_PRINT(tlsOdrUse);
 978 }
 979
 980 inline hazptr_tls_life::hazptr_tls_life() {
 981   DEBUG_PRINT(this);
 982   CHECK(tls_state_ == TLS_UNINITIALIZED);
 983   hazptr_tc_init();
 984   hazptr_priv_init();
 985   tls_state_ = TLS_ALIVE;
 986 }
 987
 988 inline hazptr_tls_life::~hazptr_tls_life() {
 989   DEBUG_PRINT(this);
 990   CHECK(tls_state_ == TLS_ALIVE);
 991   hazptr_tc_shutdown();
 992   hazptr_priv_shutdown();
 993   tls_state_ = TLS_DESTROYED;
 994 }
 995
 996 } // namespace hazptr
 997 } // namespace folly