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 hazptr_stats& hazptr_stats();
  79
  80 #if HAZPTR_STATS
  81 #define INC_HAZPTR_STATS(x) hazptr_stats().x()
  82 #else
  83 #define INC_HAZPTR_STATS(x)
  84 #endif
  85
  86 /** hazptr_mb */
  87
  88 class hazptr_mb {
  89  public:
  90   static void light();
  91   static void heavy();
  92 };
  93
  94 /** hazptr_tc
  95  *  Thread caching of hazptr_rec-s that belong to the default domain.
  96  */
  97
  98 class hazptr_tc_entry {
  99   friend class hazptr_tc;
 100   hazptr_rec* hprec_{nullptr};
 101
 102  public:
 103   void fill(hazptr_rec* hprec);
 104   hazptr_rec* get();
 105   void evict();
 106 };
 107
 108 class hazptr_tc {
 109   hazptr_tc_entry tc_[HAZPTR_TC_SIZE];
 110   int count_{0};
 111
 112  public:
 113   hazptr_tc();
 114   ~hazptr_tc();
 115   hazptr_rec* get();
 116   bool put(hazptr_rec* hprec);
 117 };
 118
 119 hazptr_tc& hazptr_tc();
 120
 121 /** hazptr_priv
 122  *  Thread private lists of retired objects that belong to the default domain.
 123  */
 124
 125 class hazptr_priv {
 126   hazptr_domain* domain_{&default_hazptr_domain()};
 127   hazptr_obj* head_{nullptr};
 128   hazptr_obj* tail_{nullptr};
 129   int rcount_{0};
 130   bool active_{true};
 131
 132  public:
 133   hazptr_priv();
 134   ~hazptr_priv();
 135   void push(hazptr_obj* obj);
 136
 137  private:
 138   void pushAllToDomain();
 139 };
 140
 141 hazptr_priv& hazptr_priv();
 142
 143 /**
 144  * public functions
 145  */
 146
 147 /** hazptr_domain */
 148
 149 constexpr hazptr_domain::hazptr_domain(memory_resource* mr) noexcept
 150     : mr_(mr) {}
 151
 152 /** hazptr_obj_base */
 153
 154 template <typename T, typename D>
 155 inline void hazptr_obj_base<T, D>::retire(hazptr_domain& domain, D deleter) {
 156   DEBUG_PRINT(this << " " << &domain);
 157   deleter_ = std::move(deleter);
 158   reclaim_ = [](hazptr_obj* p) {
 159     auto hobp = static_cast<hazptr_obj_base*>(p);
 160     auto obj = static_cast<T*>(hobp);
 161     hobp->deleter_(obj);
 162   };
 163   if (HAZPTR_PRIV &&
 164       (HAZPTR_ONE_DOMAIN || (&domain == &default_hazptr_domain()))) {
 165     hazptr_priv().push(this);
 166   } else {
 167     domain.objRetire(this);
 168   }
 169 }
 170
 171 /** hazptr_rec */
 172
 173 class hazptr_rec {
 174   friend class hazptr_domain;
 175   friend class hazptr_holder;
 176   friend class hazptr_tc_entry;
 177
 178   FOLLY_ALIGN_TO_AVOID_FALSE_SHARING
 179   std::atomic<const void*> hazptr_{nullptr};
 180   hazptr_rec* next_{nullptr};
 181   std::atomic<bool> active_{false};
 182
 183   void set(const void* p) noexcept;
 184   const void* get() const noexcept;
 185   void clear() noexcept;
 186   bool isActive() noexcept;
 187   bool tryAcquire() noexcept;
 188   void release() noexcept;
 189 };
 190
 191 /** hazptr_holder */
 192
 193 FOLLY_ALWAYS_INLINE hazptr_holder::hazptr_holder(hazptr_domain& domain) {
 194   domain_ = &domain;
 195   hazptr_ = domain_->hazptrAcquire();
 196   DEBUG_PRINT(this << " " << domain_ << " " << hazptr_);
 197   if (hazptr_ == nullptr) { std::bad_alloc e; throw e; }
 198 }
 199
 200 inline hazptr_holder::hazptr_holder(std::nullptr_t) {
 201   domain_ = nullptr;
 202   hazptr_ = nullptr;
 203   DEBUG_PRINT(this << " " << domain_ << " " << hazptr_);
 204 }
 205
 206 FOLLY_ALWAYS_INLINE hazptr_holder::~hazptr_holder() {
 207   DEBUG_PRINT(this);
 208   if (domain_) {
 209     hazptr_->clear();
 210     domain_->hazptrRelease(hazptr_);
 211   }
 212 }
 213
 214 inline hazptr_holder::hazptr_holder(hazptr_holder&& rhs) noexcept {
 215   domain_ = rhs.domain_;
 216   hazptr_ = rhs.hazptr_;
 217   rhs.domain_ = nullptr;
 218   rhs.hazptr_ = nullptr;
 219 }
 220
 221 inline hazptr_holder& hazptr_holder::operator=(hazptr_holder&& rhs) noexcept {
 222   /* Self-move is a no-op.  */
 223   if (this != &rhs) {
 224     this->~hazptr_holder();
 225     new (this) hazptr_holder(std::move(rhs));
 226   }
 227   return *this;
 228 }
 229
 230 template <typename T>
 231 FOLLY_ALWAYS_INLINE bool hazptr_holder::try_protect(
 232     T*& ptr,
 233     const std::atomic<T*>& src) noexcept {
 234   return try_protect(ptr, src, [](T* t) { return t; });
 235 }
 236
 237 template <typename T, typename Func>
 238 FOLLY_ALWAYS_INLINE bool hazptr_holder::try_protect(
 239     T*& ptr,
 240     const std::atomic<T*>& src,
 241     Func f) noexcept {
 242   DEBUG_PRINT(this << " " << ptr << " " << &src);
 243   reset(f(ptr));
 244   /*** Full fence ***/ hazptr_mb::light();
 245   T* p = src.load(std::memory_order_acquire);
 246   if (p != ptr) {
 247     ptr = p;
 248     reset();
 249     return false;
 250   }
 251   return true;
 252 }
 253
 254 template <typename T>
 255 FOLLY_ALWAYS_INLINE T* hazptr_holder::get_protected(
 256     const std::atomic<T*>& src) noexcept {
 257   return get_protected(src, [](T* t) { return t; });
 258 }
 259
 260 template <typename T, typename Func>
 261 FOLLY_ALWAYS_INLINE T* hazptr_holder::get_protected(
 262     const std::atomic<T*>& src,
 263     Func f) noexcept {
 264   T* p = src.load(std::memory_order_relaxed);
 265   while (!try_protect(p, src, f)) {
 266   }
 267   DEBUG_PRINT(this << " " << p << " " << &src);
 268   return p;
 269 }
 270
 271 template <typename T>
 272 FOLLY_ALWAYS_INLINE void hazptr_holder::reset(const T* ptr) noexcept {
 273   auto p = static_cast<hazptr_obj*>(const_cast<T*>(ptr));
 274   DEBUG_PRINT(this << " " << ptr << " p:" << p);
 275   DCHECK(hazptr_); // UB if *this is empty
 276   hazptr_->set(p);
 277 }
 278
 279 FOLLY_ALWAYS_INLINE void hazptr_holder::reset(std::nullptr_t) noexcept {
 280   DEBUG_PRINT(this);
 281   DCHECK(hazptr_); // UB if *this is empty
 282   hazptr_->clear();
 283 }
 284
 285 FOLLY_ALWAYS_INLINE void hazptr_holder::swap(hazptr_holder& rhs) noexcept {
 286   DEBUG_PRINT(
 287     this << " " <<  this->hazptr_ << " " << this->domain_ << " -- "
 288     << &rhs << " " << rhs.hazptr_ << " " << rhs.domain_);
 289   if (!HAZPTR_ONE_DOMAIN) {
 290     std::swap(this->domain_, rhs.domain_);
 291   }
 292   std::swap(this->hazptr_, rhs.hazptr_);
 293 }
 294
 295 FOLLY_ALWAYS_INLINE void swap(hazptr_holder& lhs, hazptr_holder& rhs) noexcept {
 296   lhs.swap(rhs);
 297 }
 298
 299 ////////////////////////////////////////////////////////////////////////////////
 300 // [TODO]:
 301 // - Control of reclamation (when and by whom)
 302 // - End-to-end lock-free implementation
 303
 304 /** Definition of default_hazptr_domain() */
 305
 306 inline hazptr_domain& default_hazptr_domain() {
 307   static hazptr_domain d;
 308   DEBUG_PRINT(&d);
 309   return d;
 310 }
 311
 312 /** hazptr_rec */
 313
 314 inline void hazptr_rec::set(const void* p) noexcept {
 315   DEBUG_PRINT(this << " " << p);
 316   hazptr_.store(p, std::memory_order_release);
 317 }
 318
 319 inline const void* hazptr_rec::get() const noexcept {
 320   auto p = hazptr_.load(std::memory_order_acquire);
 321   DEBUG_PRINT(this << " " << p);
 322   return p;
 323 }
 324
 325 inline void hazptr_rec::clear() noexcept {
 326   DEBUG_PRINT(this);
 327   hazptr_.store(nullptr, std::memory_order_release);
 328 }
 329
 330 inline bool hazptr_rec::isActive() noexcept {
 331   return active_.load(std::memory_order_acquire);
 332 }
 333
 334 inline bool hazptr_rec::tryAcquire() noexcept {
 335   bool active = isActive();
 336   if (!active &&
 337       active_.compare_exchange_strong(
 338           active, true, std::memory_order_release, std::memory_order_relaxed)) {
 339     DEBUG_PRINT(this);
 340     return true;
 341   }
 342   return false;
 343 }
 344
 345 inline void hazptr_rec::release() noexcept {
 346   DEBUG_PRINT(this);
 347   active_.store(false, std::memory_order_release);
 348 }
 349
 350 /** hazptr_obj */
 351
 352 inline const void* hazptr_obj::getObjPtr() const {
 353   DEBUG_PRINT(this);
 354   return this;
 355 }
 356
 357 /** hazptr_domain */
 358
 359 inline hazptr_domain::~hazptr_domain() {
 360   DEBUG_PRINT(this);
 361   { /* reclaim all remaining retired objects */
 362     hazptr_obj* next;
 363     auto retired = retired_.exchange(nullptr);
 364     while (retired) {
 365       for (auto p = retired; p; p = next) {
 366         next = p->next_;
 367         (*(p->reclaim_))(p);
 368       }
 369       retired = retired_.exchange(nullptr);
 370     }
 371   }
 372   { /* free all hazptr_rec-s */
 373     hazptr_rec* next;
 374     for (auto p = hazptrs_.load(std::memory_order_acquire); p; p = next) {
 375       next = p->next_;
 376       DCHECK(!p->isActive());
 377       mr_->deallocate(static_cast<void*>(p), sizeof(hazptr_rec));
 378     }
 379   }
 380 }
 381
 382 FOLLY_ALWAYS_INLINE hazptr_rec* hazptr_domain::hazptrAcquire() {
 383   if (HAZPTR_TC && (HAZPTR_ONE_DOMAIN || this == &default_hazptr_domain())) {
 384     auto hprec = hazptr_tc().get();
 385     if (hprec) {
 386       return hprec;
 387     }
 388   }
 389   hazptr_rec* p;
 390   hazptr_rec* next;
 391   for (p = hazptrs_.load(std::memory_order_acquire); p; p = next) {
 392     next = p->next_;
 393     if (p->tryAcquire()) {
 394       return p;
 395     }
 396   }
 397   p = static_cast<hazptr_rec*>(mr_->allocate(sizeof(hazptr_rec)));
 398   if (p == nullptr) {
 399     return nullptr;
 400   }
 401   p->active_.store(true, std::memory_order_relaxed);
 402   p->next_ = hazptrs_.load(std::memory_order_acquire);
 403   while (!hazptrs_.compare_exchange_weak(
 404       p->next_, p, std::memory_order_release, std::memory_order_acquire))
 405     /* keep trying */;
 406   auto hcount = hcount_.fetch_add(1);
 407   DEBUG_PRINT(this << " " << p << " " << sizeof(hazptr_rec) << " " << hcount);
 408   return p;
 409 }
 410
 411 FOLLY_ALWAYS_INLINE void hazptr_domain::hazptrRelease(hazptr_rec* p) noexcept {
 412   if (HAZPTR_TC && (HAZPTR_ONE_DOMAIN || this == &default_hazptr_domain()) &&
 413       hazptr_tc().put(p)) {
 414     return;
 415   }
 416   DEBUG_PRINT(this << " " << p);
 417   p->release();
 418 }
 419
 420 inline int
 421 hazptr_domain::pushRetired(hazptr_obj* head, hazptr_obj* tail, int count) {
 422   /*** Full fence ***/ hazptr_mb::light();
 423   tail->next_ = retired_.load(std::memory_order_acquire);
 424   while (!retired_.compare_exchange_weak(
 425       tail->next_,
 426       head,
 427       std::memory_order_release,
 428       std::memory_order_acquire)) {
 429   }
 430   return rcount_.fetch_add(count) + count;
 431 }
 432
 433 inline bool hazptr_domain::reachedThreshold(int rcount) {
 434   return (
 435       rcount >= HAZPTR_SCAN_THRESHOLD &&
 436       rcount >= HAZPTR_SCAN_MULT * hcount_.load(std::memory_order_acquire));
 437 }
 438
 439 inline void hazptr_domain::objRetire(hazptr_obj* p) {
 440   auto rcount = pushRetired(p, p, 1);
 441   if (reachedThreshold(rcount)) {
 442     tryBulkReclaim();
 443   }
 444 }
 445
 446 inline void hazptr_domain::tryBulkReclaim() {
 447   DEBUG_PRINT(this);
 448   do {
 449     auto hcount = hcount_.load(std::memory_order_acquire);
 450     auto rcount = rcount_.load(std::memory_order_acquire);
 451     if (rcount < HAZPTR_SCAN_THRESHOLD || rcount < HAZPTR_SCAN_MULT * hcount) {
 452       return;
 453     }
 454     if (rcount_.compare_exchange_weak(
 455             rcount, 0, std::memory_order_release, std::memory_order_relaxed)) {
 456       break;
 457     }
 458   } while (true);
 459   bulkReclaim();
 460 }
 461
 462 inline void hazptr_domain::bulkReclaim() {
 463   DEBUG_PRINT(this);
 464   /*** Full fence ***/ hazptr_mb::heavy();
 465   auto p = retired_.exchange(nullptr, std::memory_order_acquire);
 466   auto h = hazptrs_.load(std::memory_order_acquire);
 467   std::unordered_set<const void*> hs; // TODO lock-free alternative
 468   for (; h; h = h->next_) {
 469     hs.insert(h->get());
 470   }
 471   int rcount = 0;
 472   hazptr_obj* retired = nullptr;
 473   hazptr_obj* tail = nullptr;
 474   hazptr_obj* next;
 475   for (; p; p = next) {
 476     next = p->next_;
 477     if (hs.count(p->getObjPtr()) == 0) {
 478       DEBUG_PRINT(this << " " << p << " " << p->reclaim_);
 479       (*(p->reclaim_))(p);
 480     } else {
 481       p->next_ = retired;
 482       retired = p;
 483       if (tail == nullptr) {
 484         tail = p;
 485       }
 486       ++rcount;
 487     }
 488   }
 489   if (tail) {
 490     pushRetired(retired, tail, rcount);
 491   }
 492 }
 493
 494 /** hazptr_stats */
 495
 496 class hazptr_stats {
 497  public:
 498   ~hazptr_stats();
 499   void light();
 500   void heavy();
 501   void seq_cst();
 502
 503  private:
 504   std::atomic<uint64_t> light_{0};
 505   std::atomic<uint64_t> heavy_{0};
 506   std::atomic<uint64_t> seq_cst_{0};
 507 };
 508
 509 inline hazptr_stats::~hazptr_stats() {
 510   DEBUG_PRINT(this << " light " << light_.load());
 511   DEBUG_PRINT(this << " heavy " << heavy_.load());
 512   DEBUG_PRINT(this << " seq_cst " << seq_cst_.load());
 513 }
 514
 515 FOLLY_ALWAYS_INLINE void hazptr_stats::light() {
 516   if (HAZPTR_STATS) {
 517     /* atomic */ ++light_;
 518   }
 519 }
 520
 521 inline void hazptr_stats::heavy() {
 522   if (HAZPTR_STATS) {
 523     /* atomic */ ++heavy_;
 524   }
 525 }
 526
 527 inline void hazptr_stats::seq_cst() {
 528   if (HAZPTR_STATS) {
 529     /* atomic */ ++seq_cst_;
 530   }
 531 }
 532
 533 inline class hazptr_stats& hazptr_stats() {
 534   static class hazptr_stats stats_;
 535   DEBUG_PRINT(&stats_);
 536   return stats_;
 537 }
 538
 539 /** hazptr_mb */
 540
 541 inline void hazptr_mb::light() {
 542   DEBUG_PRINT("");
 543   if (HAZPTR_AMB) {
 544     folly::asymmetricLightBarrier();
 545     INC_HAZPTR_STATS(light);
 546   } else {
 547     atomic_thread_fence(std::memory_order_seq_cst);
 548     INC_HAZPTR_STATS(seq_cst);
 549   }
 550 }
 551
 552 inline void hazptr_mb::heavy() {
 553   DEBUG_PRINT("");
 554   if (HAZPTR_AMB) {
 555     folly::asymmetricHeavyBarrier(AMBFlags::EXPEDITED);
 556     INC_HAZPTR_STATS(heavy);
 557   } else {
 558     atomic_thread_fence(std::memory_order_seq_cst);
 559     INC_HAZPTR_STATS(seq_cst);
 560   }
 561 }
 562
 563 /** hazptr_tc - functions */
 564
 565 inline void hazptr_tc_entry::fill(hazptr_rec* hprec) {
 566   hprec_ = hprec;
 567   DEBUG_PRINT(this << " " << hprec);
 568 }
 569
 570 inline hazptr_rec* hazptr_tc_entry::get() {
 571   auto hprec = hprec_;
 572   hprec_ = nullptr;
 573   DEBUG_PRINT(this << " " << hprec);
 574   return hprec;
 575 }
 576
 577 inline void hazptr_tc_entry::evict() {
 578   auto hprec = hprec_;
 579   hprec_ = nullptr;
 580   hprec->release();
 581   DEBUG_PRINT(this << " " << hprec);
 582 }
 583
 584 inline hazptr_tc::hazptr_tc() {
 585   DEBUG_PRINT(this);
 586 }
 587
 588 inline hazptr_tc::~hazptr_tc() {
 589   DEBUG_PRINT(this);
 590   for (int i = 0; i < count_; ++i) {
 591     tc_[i].evict();
 592   }
 593 }
 594
 595 inline hazptr_rec* hazptr_tc::get() {
 596   if (count_ > 0) {
 597     auto hprec = tc_[--count_].get();
 598     DEBUG_PRINT(this << " " << hprec);
 599     return hprec;
 600   }
 601   DEBUG_PRINT(this << " nullptr");
 602   return nullptr;
 603 }
 604
 605 inline bool hazptr_tc::put(hazptr_rec* hprec) {
 606   if (count_ < HAZPTR_TC_SIZE) {
 607     tc_[count_++].fill(hprec);
 608     DEBUG_PRINT(this << " " << count_ - 1);
 609     return true;
 610   }
 611   return false;
 612 }
 613
 614 inline class hazptr_tc& hazptr_tc() {
 615   static thread_local class hazptr_tc tc;
 616   DEBUG_PRINT(&tc);
 617   return tc;
 618 }
 619
 620 /** hazptr_priv - functions */
 621
 622 inline hazptr_priv::hazptr_priv() {
 623   DEBUG_PRINT(this);
 624 }
 625
 626 inline hazptr_priv::~hazptr_priv() {
 627   DEBUG_PRINT(this);
 628   DCHECK(active_);
 629   active_ = false;
 630   if (tail_) {
 631     pushAllToDomain();
 632   }
 633 }
 634
 635 inline void hazptr_priv::push(hazptr_obj* obj) {
 636   obj->next_ = nullptr;
 637   if (tail_) {
 638     tail_->next_ = obj;
 639   } else {
 640     if (!active_) {
 641       default_hazptr_domain().objRetire(obj);
 642       return;
 643     }
 644     head_ = obj;
 645   }
 646   tail_ = obj;
 647   ++rcount_;
 648   if (domain_->reachedThreshold(rcount_)) {
 649     pushAllToDomain();
 650   }
 651 }
 652
 653 inline void hazptr_priv::pushAllToDomain() {
 654   domain_->pushRetired(head_, tail_, rcount_);
 655   head_ = nullptr;
 656   tail_ = nullptr;
 657   rcount_ = 0;
 658   domain_->tryBulkReclaim();
 659 }
 660
 661 inline class hazptr_priv& hazptr_priv() {
 662   static thread_local class hazptr_priv priv;
 663   DEBUG_PRINT(&priv);
 664   return priv;
 665 }
 666
 667 } // namespace folly
 668 } // namespace hazptr