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