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 2
  38 #endif
  39
  40 #ifndef HAZPTR_SCAN_MULT
  41 #define HAZPTR_SCAN_MULT 2
  42 #endif
  43
  44 #ifndef HAZPTR_SCAN_THRESHOLD
  45 #define HAZPTR_SCAN_THRESHOLD 1000
  46 #endif
  47
  48 /* stats switch */
  49 #ifndef HAZPTR_STATS
  50 #define HAZPTR_STATS false
  51 #endif
  52
  53 #include <folly/experimental/AsymmetricMemoryBarrier.h>
  54 #include <folly/experimental/hazptr/debug.h>
  55
  56 #include <mutex> // for thread caching
  57 #include <unordered_set> // for hash set in bulk reclamation
  58
  59 namespace folly {
  60 namespace hazptr {
  61
  62 /**
  63  * helper classes and functions
  64  */
  65
  66 /** hazptr_stats */
  67
  68 class hazptr_stats;
  69 hazptr_stats& hazptr_stats();
  70
  71 /** hazptr_mb */
  72
  73 class hazptr_mb {
  74  public:
  75   static void light();
  76   static void heavy();
  77 };
  78
  79 /** hazptr_tc */
  80
  81 class hazptr_tc_entry {
  82   friend class hazptr_tc;
  83   std::atomic<hazptr_rec*> hprec_{nullptr};
  84   std::atomic<hazptr_domain*> domain_{nullptr};
  85
  86  public:
  87   void fill(hazptr_rec* hprec, hazptr_domain* domain);
  88   hazptr_rec* get(hazptr_domain* domain);
  89   void invalidate(hazptr_rec* hprec);
  90   void evict();
  91 };
  92
  93 class hazptr_tc {
  94   hazptr_tc_entry tc_[HAZPTR_TC_SIZE];
  95
  96  public:
  97   hazptr_tc();
  98   ~hazptr_tc();
  99   hazptr_rec* get(hazptr_domain* domain);
 100   bool put(hazptr_rec* hprec, hazptr_domain* domain);
 101 };
 102
 103 hazptr_tc& hazptr_tc();
 104
 105 std::mutex& hazptr_tc_lock();
 106
 107 using hazptr_tc_guard = std::lock_guard<std::mutex>;
 108
 109 /**
 110  * public functions
 111  */
 112
 113 /** hazptr_domain */
 114
 115 constexpr hazptr_domain::hazptr_domain(memory_resource* mr) noexcept
 116     : mr_(mr) {}
 117
 118 /** hazptr_obj_base */
 119
 120 template <typename T, typename D>
 121 inline void hazptr_obj_base<T, D>::retire(hazptr_domain& domain, D deleter) {
 122   DEBUG_PRINT(this << " " << &domain);
 123   deleter_ = std::move(deleter);
 124   reclaim_ = [](hazptr_obj* p) {
 125     auto hobp = static_cast<hazptr_obj_base*>(p);
 126     auto obj = static_cast<T*>(hobp);
 127     hobp->deleter_(obj);
 128   };
 129   domain.objRetire(this);
 130 }
 131
 132 /** hazptr_rec */
 133
 134 class hazptr_rec {
 135   friend class hazptr_domain;
 136   friend class hazptr_tc_entry;
 137   friend class hazptr_holder;
 138
 139   std::atomic<const void*> hazptr_{nullptr};
 140   hazptr_rec* next_{nullptr};
 141   std::atomic<hazptr_tc_entry*> tc_{nullptr};
 142   std::atomic<bool> active_{false};
 143
 144   void set(const void* p) noexcept;
 145   const void* get() const noexcept;
 146   void clear() noexcept;
 147   bool isActive() noexcept;
 148   bool tryAcquire() noexcept;
 149   void release() noexcept;
 150 };
 151
 152 /** hazptr_holder */
 153
 154 inline hazptr_holder::hazptr_holder(hazptr_domain& domain) {
 155   domain_ = &domain;
 156   hazptr_ = domain_->hazptrAcquire();
 157   DEBUG_PRINT(this << " " << domain_ << " " << hazptr_);
 158   if (hazptr_ == nullptr) { std::bad_alloc e; throw e; }
 159 }
 160
 161 hazptr_holder::~hazptr_holder() {
 162   DEBUG_PRINT(this);
 163   domain_->hazptrRelease(hazptr_);
 164 }
 165
 166 template <typename T>
 167 inline bool hazptr_holder::try_protect(
 168     T*& ptr,
 169     const std::atomic<T*>& src) noexcept {
 170   DEBUG_PRINT(this << " " << ptr << " " << &src);
 171   reset(ptr);
 172   /*** Full fence ***/ hazptr_mb::light();
 173   T* p = src.load(std::memory_order_acquire);
 174   if (p != ptr) {
 175     ptr = p;
 176     reset();
 177     return false;
 178   }
 179   return true;
 180 }
 181
 182 template <typename T>
 183 inline T* hazptr_holder::get_protected(const std::atomic<T*>& src) noexcept {
 184   T* p = src.load(std::memory_order_relaxed);
 185   while (!try_protect(p, src)) {}
 186   DEBUG_PRINT(this << " " << p << " " << &src);
 187   return p;
 188 }
 189
 190 template <typename T>
 191 inline void hazptr_holder::reset(const T* ptr) noexcept {
 192   auto p = static_cast<hazptr_obj*>(const_cast<T*>(ptr));
 193   DEBUG_PRINT(this << " " << ptr << " p:" << p);
 194   hazptr_->set(p);
 195 }
 196
 197 inline void hazptr_holder::reset(std::nullptr_t) noexcept {
 198   DEBUG_PRINT(this);
 199   hazptr_->clear();
 200 }
 201
 202 inline void hazptr_holder::swap(hazptr_holder& rhs) noexcept {
 203   DEBUG_PRINT(
 204     this << " " <<  this->hazptr_ << " " << this->domain_ << " -- "
 205     << &rhs << " " << rhs.hazptr_ << " " << rhs.domain_);
 206   std::swap(this->domain_, rhs.domain_);
 207   std::swap(this->hazptr_, rhs.hazptr_);
 208 }
 209
 210 inline void swap(hazptr_holder& lhs, hazptr_holder& rhs) noexcept {
 211   lhs.swap(rhs);
 212 }
 213
 214 ////////////////////////////////////////////////////////////////////////////////
 215 // [TODO]:
 216 // - Private storage of retired objects
 217 // - Control of reclamation (when and by whom)
 218 // - End-to-end lock-free implementation
 219
 220 /** Definition of default_hazptr_domain() */
 221 inline hazptr_domain& default_hazptr_domain() {
 222   static hazptr_domain d;
 223   DEBUG_PRINT(&d);
 224   return d;
 225 }
 226
 227 /** hazptr_rec */
 228
 229 inline void hazptr_rec::set(const void* p) noexcept {
 230   DEBUG_PRINT(this << " " << p);
 231   hazptr_.store(p, std::memory_order_release);
 232 }
 233
 234 inline const void* hazptr_rec::get() const noexcept {
 235   auto p = hazptr_.load(std::memory_order_acquire);
 236   DEBUG_PRINT(this << " " << p);
 237   return p;
 238 }
 239
 240 inline void hazptr_rec::clear() noexcept {
 241   DEBUG_PRINT(this);
 242   hazptr_.store(nullptr, std::memory_order_release);
 243 }
 244
 245 inline bool hazptr_rec::isActive() noexcept {
 246   return active_.load(std::memory_order_acquire);
 247 }
 248
 249 inline bool hazptr_rec::tryAcquire() noexcept {
 250   bool active = isActive();
 251   if (!active &&
 252       active_.compare_exchange_strong(
 253           active, true, std::memory_order_release, std::memory_order_relaxed)) {
 254     DEBUG_PRINT(this);
 255     return true;
 256   }
 257   return false;
 258 }
 259
 260 inline void hazptr_rec::release() noexcept {
 261   DEBUG_PRINT(this);
 262   clear();
 263   active_.store(false, std::memory_order_release);
 264 }
 265
 266 /** hazptr_obj */
 267
 268 inline const void* hazptr_obj::getObjPtr() const {
 269   DEBUG_PRINT(this);
 270   return this;
 271 }
 272
 273 /** hazptr_domain */
 274
 275 inline hazptr_domain::~hazptr_domain() {
 276   DEBUG_PRINT(this);
 277   { /* reclaim all remaining retired objects */
 278     hazptr_obj* next;
 279     auto retired = retired_.exchange(nullptr);
 280     while (retired) {
 281       for (auto p = retired; p; p = next) {
 282         next = p->next_;
 283         (*(p->reclaim_))(p);
 284       }
 285       retired = retired_.exchange(nullptr);
 286     }
 287   }
 288   { /* free all hazptr_rec-s */
 289     hazptr_rec* next;
 290     for (auto p = hazptrs_.load(std::memory_order_acquire); p; p = next) {
 291       next = p->next_;
 292       if (HAZPTR_TC) {
 293         if (p->isActive()) {
 294           hazptr_tc_guard g(hazptr_tc_lock());
 295           if (p->isActive()) {
 296             auto tc = p->tc_.load(std::memory_order_acquire);
 297             DCHECK(tc != nullptr);
 298             tc->invalidate(p);
 299           }
 300         }
 301       } else {
 302         CHECK(!p->isActive());
 303       }
 304       mr_->deallocate(static_cast<void*>(p), sizeof(hazptr_rec));
 305     }
 306   }
 307 }
 308
 309 inline hazptr_rec* hazptr_domain::hazptrAcquire() {
 310   if (HAZPTR_TC) {
 311     hazptr_rec* hprec = hazptr_tc().get(this);
 312     if (hprec) {
 313       return hprec;
 314     }
 315   }
 316   hazptr_rec* p;
 317   hazptr_rec* next;
 318   for (p = hazptrs_.load(std::memory_order_acquire); p; p = next) {
 319     next = p->next_;
 320     if (p->tryAcquire()) {
 321       return p;
 322     }
 323   }
 324   p = static_cast<hazptr_rec*>(mr_->allocate(sizeof(hazptr_rec)));
 325   if (p == nullptr) {
 326     return nullptr;
 327   }
 328   p->active_.store(true, std::memory_order_relaxed);
 329   p->next_ = hazptrs_.load(std::memory_order_acquire);
 330   while (!hazptrs_.compare_exchange_weak(
 331       p->next_, p, std::memory_order_release, std::memory_order_acquire))
 332     /* keep trying */;
 333   auto hcount = hcount_.fetch_add(1);
 334   DEBUG_PRINT(this << " " << p << " " << sizeof(hazptr_rec) << " " << hcount);
 335   return p;
 336 }
 337
 338 inline void hazptr_domain::hazptrRelease(hazptr_rec* p) noexcept {
 339   if (HAZPTR_TC && hazptr_tc().put(p, this)) {
 340     return;
 341   }
 342   DEBUG_PRINT(this << " " << p);
 343   p->release();
 344 }
 345
 346 inline int
 347 hazptr_domain::pushRetired(hazptr_obj* head, hazptr_obj* tail, int count) {
 348   /*** Full fence ***/ hazptr_mb::light();
 349   tail->next_ = retired_.load(std::memory_order_acquire);
 350   while (!retired_.compare_exchange_weak(
 351       tail->next_,
 352       head,
 353       std::memory_order_release,
 354       std::memory_order_acquire)) {
 355   }
 356   return rcount_.fetch_add(count);
 357 }
 358
 359 inline void hazptr_domain::objRetire(hazptr_obj* p) {
 360   auto rcount = pushRetired(p, p, 1) + 1;
 361   if (rcount >= HAZPTR_SCAN_THRESHOLD &&
 362       rcount >= HAZPTR_SCAN_MULT * hcount_.load(std::memory_order_acquire)) {
 363     tryBulkReclaim();
 364   }
 365 }
 366
 367 inline void hazptr_domain::tryBulkReclaim() {
 368   DEBUG_PRINT(this);
 369   do {
 370     auto hcount = hcount_.load(std::memory_order_acquire);
 371     auto rcount = rcount_.load(std::memory_order_acquire);
 372     if (rcount < HAZPTR_SCAN_THRESHOLD || rcount < HAZPTR_SCAN_MULT * hcount) {
 373       return;
 374     }
 375     if (rcount_.compare_exchange_weak(
 376             rcount, 0, std::memory_order_release, std::memory_order_relaxed)) {
 377       break;
 378     }
 379   } while (true);
 380   bulkReclaim();
 381 }
 382
 383 inline void hazptr_domain::bulkReclaim() {
 384   DEBUG_PRINT(this);
 385   /*** Full fence ***/ hazptr_mb::heavy();
 386   auto p = retired_.exchange(nullptr, std::memory_order_acquire);
 387   auto h = hazptrs_.load(std::memory_order_acquire);
 388   std::unordered_set<const void*> hs; // TODO lock-free alternative
 389   for (; h; h = h->next_) {
 390     hs.insert(h->get());
 391   }
 392   int rcount = 0;
 393   hazptr_obj* retired = nullptr;
 394   hazptr_obj* tail = nullptr;
 395   hazptr_obj* next;
 396   for (; p; p = next) {
 397     next = p->next_;
 398     if (hs.count(p->getObjPtr()) == 0) {
 399       DEBUG_PRINT(this << " " << p << " " << p->reclaim_);
 400       (*(p->reclaim_))(p);
 401     } else {
 402       p->next_ = retired;
 403       retired = p;
 404       if (tail == nullptr) {
 405         tail = p;
 406       }
 407       ++rcount;
 408     }
 409   }
 410   if (tail) {
 411     pushRetired(retired, tail, rcount);
 412   }
 413 }
 414
 415 /** hazptr_stats */
 416
 417 class hazptr_stats {
 418  public:
 419   ~hazptr_stats();
 420   void light();
 421   void heavy();
 422   void seq_cst();
 423
 424  private:
 425   std::atomic<uint64_t> light_{0};
 426   std::atomic<uint64_t> heavy_{0};
 427   std::atomic<uint64_t> seq_cst_{0};
 428 };
 429
 430 inline hazptr_stats::~hazptr_stats() {
 431   DEBUG_PRINT(this << " light " << light_.load());
 432   DEBUG_PRINT(this << " heavy " << heavy_.load());
 433   DEBUG_PRINT(this << " seq_cst " << seq_cst_.load());
 434 }
 435
 436 inline void hazptr_stats::light() {
 437   if (HAZPTR_STATS) {
 438     /* atomic */ ++light_;
 439   }
 440 }
 441
 442 inline void hazptr_stats::heavy() {
 443   if (HAZPTR_STATS) {
 444     /* atomic */ ++heavy_;
 445   }
 446 }
 447
 448 inline void hazptr_stats::seq_cst() {
 449   if (HAZPTR_STATS) {
 450     /* atomic */ ++seq_cst_;
 451   }
 452 }
 453
 454 inline class hazptr_stats& hazptr_stats() {
 455   static class hazptr_stats stats_;
 456   DEBUG_PRINT(&stats_);
 457   return stats_;
 458 }
 459
 460 /** hazptr_mb */
 461
 462 inline void hazptr_mb::light() {
 463   DEBUG_PRINT("");
 464   if (HAZPTR_AMB) {
 465     folly::asymmetricLightBarrier();
 466     hazptr_stats().light();
 467   } else {
 468     atomic_thread_fence(std::memory_order_seq_cst);
 469     hazptr_stats().seq_cst();
 470   }
 471 }
 472
 473 inline void hazptr_mb::heavy() {
 474   DEBUG_PRINT("");
 475   if (HAZPTR_AMB) {
 476     folly::asymmetricHeavyBarrier();
 477     hazptr_stats().heavy();
 478   } else {
 479     atomic_thread_fence(std::memory_order_seq_cst);
 480     hazptr_stats().seq_cst();
 481   }
 482 }
 483
 484 /** hazptr_tc - functions */
 485
 486 inline void hazptr_tc_entry::fill(hazptr_rec* hprec, hazptr_domain* domain) {
 487   hprec_.store(hprec, std::memory_order_release);
 488   domain_.store(domain, std::memory_order_release);
 489   hprec->tc_.store(this, std::memory_order_release);
 490   DEBUG_PRINT(this << " " << domain << " " << hprec);
 491 }
 492
 493 inline hazptr_rec* hazptr_tc_entry::get(hazptr_domain* domain) {
 494   if (domain == domain_.load(std::memory_order_acquire)) {
 495     auto hprec = hprec_.load(std::memory_order_acquire);
 496     if (hprec) {
 497       hprec_.store(nullptr, std::memory_order_release);
 498       DEBUG_PRINT(this << " " << domain << " " << hprec);
 499       return hprec;
 500     }
 501   }
 502   return nullptr;
 503 }
 504
 505 inline void hazptr_tc_entry::invalidate(hazptr_rec* hprec) {
 506   DCHECK_EQ(hprec, hprec_);
 507   hprec_.store(nullptr, std::memory_order_release);
 508   domain_.store(nullptr, std::memory_order_release);
 509   hprec->tc_.store(nullptr, std::memory_order_relaxed);
 510   hprec->release();
 511   DEBUG_PRINT(this << " " << hprec);
 512 }
 513
 514 inline void hazptr_tc_entry::evict() {
 515   auto hprec = hprec_.load(std::memory_order_relaxed);
 516   if (hprec) {
 517     hazptr_tc_guard g(hazptr_tc_lock());
 518     hprec = hprec_.load(std::memory_order_relaxed);
 519     if (hprec) {
 520       invalidate(hprec);
 521     }
 522   }
 523   DEBUG_PRINT(hprec);
 524 }
 525
 526 inline hazptr_tc::hazptr_tc() {
 527   DEBUG_PRINT(this);
 528 }
 529
 530 inline hazptr_tc::~hazptr_tc() {
 531   DEBUG_PRINT(this);
 532   for (int i = 0; i < HAZPTR_TC_SIZE; ++i) {
 533     tc_[i].evict();
 534   }
 535 }
 536
 537 inline hazptr_rec* hazptr_tc::get(hazptr_domain* domain) {
 538   for (int i = 0; i < HAZPTR_TC_SIZE; ++i) {
 539     auto hprec = tc_[i].get(domain);
 540     if (hprec) {
 541       DEBUG_PRINT(this << " " << domain << " " << hprec);
 542       return hprec;
 543     }
 544   }
 545   DEBUG_PRINT(this << " " << domain << " nullptr");
 546   return nullptr;
 547 }
 548
 549 inline bool hazptr_tc::put(hazptr_rec* hprec, hazptr_domain* domain) {
 550   int other = HAZPTR_TC_SIZE;
 551   for (int i = 0; i < HAZPTR_TC_SIZE; ++i) {
 552     if (tc_[i].hprec_.load(std::memory_order_acquire) == nullptr) {
 553       tc_[i].fill(hprec, domain);
 554       DEBUG_PRINT(this << " " << i);
 555       return true;
 556     }
 557     if (tc_[i].domain_.load(std::memory_order_relaxed) != domain) {
 558       other = i;
 559     }
 560   }
 561   if (other < HAZPTR_TC_SIZE) {
 562     tc_[other].evict();
 563     tc_[other].fill(hprec, domain);
 564     DEBUG_PRINT(this << " " << other);
 565     return true;
 566   }
 567   return false;
 568 }
 569
 570 inline class hazptr_tc& hazptr_tc() {
 571   static thread_local class hazptr_tc tc;
 572   DEBUG_PRINT(&tc);
 573   return tc;
 574 }
 575
 576 inline std::mutex& hazptr_tc_lock() {
 577   static std::mutex m;
 578   DEBUG_PRINT(&m);
 579   return m;
 580 }
 581
 582 } // namespace folly
 583 } // namespace hazptr