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