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_SCAN_MULT
  33 #define HAZPTR_SCAN_MULT 2
  34 #endif
  35
  36 #ifndef HAZPTR_SCAN_THRESHOLD
  37 #define HAZPTR_SCAN_THRESHOLD 1000
  38 #endif
  39
  40 /* stats switch */
  41 #ifndef HAZPTR_STATS
  42 #define HAZPTR_STATS false
  43 #endif
  44
  45 #include <folly/experimental/AsymmetricMemoryBarrier.h>
  46 #include <folly/experimental/hazptr/debug.h>
  47
  48 #include <unordered_set>
  49
  50 namespace folly {
  51 namespace hazptr {
  52
  53 /**
  54  * helper classes and functions
  55  */
  56
  57 /** hazptr_stats */
  58
  59 class hazptr_stats;
  60 hazptr_stats& hazptr_stats();
  61
  62 /** hazptr_mb */
  63
  64 class hazptr_mb {
  65  public:
  66   static void light();
  67   static void heavy();
  68 };
  69
  70 /**
  71  * public functions
  72  */
  73
  74 /** hazptr_domain */
  75
  76 constexpr hazptr_domain::hazptr_domain(memory_resource* mr) noexcept : mr_(mr) {
  77   hazptr_stats();
  78 }
  79
  80 /** hazptr_obj_base */
  81
  82 template <typename T, typename D>
  83 inline void hazptr_obj_base<T, D>::retire(hazptr_domain& domain, D deleter) {
  84   DEBUG_PRINT(this << " " << &domain);
  85   deleter_ = std::move(deleter);
  86   reclaim_ = [](hazptr_obj* p) {
  87     auto hobp = static_cast<hazptr_obj_base*>(p);
  88     auto obj = static_cast<T*>(hobp);
  89     hobp->deleter_(obj);
  90   };
  91   domain.objRetire(this);
  92 }
  93
  94 /** hazptr_rec */
  95
  96 class hazptr_rec {
  97   friend class hazptr_domain;
  98   template <typename> friend class hazptr_owner;
  99
 100   std::atomic<const void*> hazptr_ = {nullptr};
 101   hazptr_rec* next_ = {nullptr};
 102   std::atomic<bool> active_ = {false};
 103
 104   void set(const void* p) noexcept;
 105   const void* get() const noexcept;
 106   void clear() noexcept;
 107   void release() noexcept;
 108 };
 109
 110 /** hazptr_owner */
 111
 112 template <typename T>
 113 inline hazptr_owner<T>::hazptr_owner(hazptr_domain& domain) {
 114   domain_ = &domain;
 115   hazptr_ = domain_->hazptrAcquire();
 116   DEBUG_PRINT(this << " " << domain_ << " " << hazptr_);
 117   if (hazptr_ == nullptr) { std::bad_alloc e; throw e; }
 118 }
 119
 120 template <typename T>
 121 hazptr_owner<T>::~hazptr_owner() {
 122   DEBUG_PRINT(this);
 123   domain_->hazptrRelease(hazptr_);
 124 }
 125
 126 template <typename T>
 127 template <typename A>
 128 inline bool hazptr_owner<T>::try_protect(T*& ptr, const A& src) noexcept {
 129   static_assert(
 130       std::is_same<decltype(std::declval<A>().load()), T*>::value,
 131       "Return type of A::load() must be T*");
 132   DEBUG_PRINT(this << " " << ptr << " " << &src);
 133   set(ptr);
 134   /*** Full fence ***/ hazptr_mb::light();
 135   T* p = src.load(std::memory_order_acquire);
 136   if (p != ptr) {
 137     ptr = p;
 138     clear();
 139     return false;
 140   }
 141   return true;
 142 }
 143
 144 template <typename T>
 145 template <typename A>
 146 inline T* hazptr_owner<T>::get_protected(const A& src) noexcept {
 147   static_assert(
 148       std::is_same<decltype(std::declval<A>().load()), T*>::value,
 149       "Return type of A::load() must be T*");
 150   T* p = src.load(std::memory_order_relaxed);
 151   while (!try_protect(p, src)) {}
 152   DEBUG_PRINT(this << " " << p << " " << &src);
 153   return p;
 154 }
 155
 156 template <typename T>
 157 inline void hazptr_owner<T>::set(const T* ptr) noexcept {
 158   auto p = static_cast<hazptr_obj*>(const_cast<T*>(ptr));
 159   DEBUG_PRINT(this << " " << ptr << " p:" << p);
 160   hazptr_->set(p);
 161 }
 162
 163 template <typename T>
 164 inline void hazptr_owner<T>::clear() noexcept {
 165   DEBUG_PRINT(this);
 166   hazptr_->clear();
 167 }
 168
 169 template <typename T>
 170 inline void hazptr_owner<T>::swap(hazptr_owner<T>& rhs) noexcept {
 171   DEBUG_PRINT(
 172     this << " " <<  this->hazptr_ << " " << this->domain_ << " -- "
 173     << &rhs << " " << rhs.hazptr_ << " " << rhs.domain_);
 174   std::swap(this->domain_, rhs.domain_);
 175   std::swap(this->hazptr_, rhs.hazptr_);
 176 }
 177
 178 template <typename T>
 179 inline void swap(hazptr_owner<T>& lhs, hazptr_owner<T>& rhs) noexcept {
 180   lhs.swap(rhs);
 181 }
 182
 183 ////////////////////////////////////////////////////////////////////////////////
 184 // [TODO]:
 185 // - Thread caching of hazptr_rec-s
 186 // - Private storage of retired objects
 187 // - Control of reclamation (when and by whom)
 188
 189 /** Definition of default_hazptr_domain() */
 190 inline hazptr_domain& default_hazptr_domain() {
 191   static hazptr_domain d;
 192   DEBUG_PRINT(&d);
 193   return d;
 194 }
 195
 196 /** hazptr_rec */
 197
 198 inline void hazptr_rec::set(const void* p) noexcept {
 199   DEBUG_PRINT(this << " " << p);
 200   hazptr_.store(p, std::memory_order_release);
 201 }
 202
 203 inline const void* hazptr_rec::get() const noexcept {
 204   auto p = hazptr_.load(std::memory_order_acquire);
 205   DEBUG_PRINT(this << " " << p);
 206   return p;
 207 }
 208
 209 inline void hazptr_rec::clear() noexcept {
 210   DEBUG_PRINT(this);
 211   hazptr_.store(nullptr, std::memory_order_release);
 212 }
 213
 214 inline void hazptr_rec::release() noexcept {
 215   DEBUG_PRINT(this);
 216   clear();
 217   active_.store(false, std::memory_order_release);
 218 }
 219
 220 /** hazptr_obj */
 221
 222 inline const void* hazptr_obj::getObjPtr() const {
 223   DEBUG_PRINT(this);
 224   return this;
 225 }
 226
 227 /** hazptr_domain */
 228
 229 inline hazptr_domain::~hazptr_domain() {
 230   DEBUG_PRINT(this);
 231   { /* reclaim all remaining retired objects */
 232     hazptr_obj* next;
 233     auto retired = retired_.exchange(nullptr);
 234     while (retired) {
 235       for (auto p = retired; p; p = next) {
 236         next = p->next_;
 237         (*(p->reclaim_))(p);
 238       }
 239       retired = retired_.exchange(nullptr);
 240     }
 241   }
 242   { /* free all hazptr_rec-s */
 243     hazptr_rec* next;
 244     for (auto p = hazptrs_.load(std::memory_order_acquire); p; p = next) {
 245       next = p->next_;
 246       mr_->deallocate(static_cast<void*>(p), sizeof(hazptr_rec));
 247     }
 248   }
 249 }
 250
 251 inline hazptr_rec* hazptr_domain::hazptrAcquire() {
 252   hazptr_rec* p;
 253   hazptr_rec* next;
 254   for (p = hazptrs_.load(std::memory_order_acquire); p; p = next) {
 255     next = p->next_;
 256     bool active = p->active_.load(std::memory_order_acquire);
 257     if (!active) {
 258       if (p->active_.compare_exchange_weak(
 259               active,
 260               true,
 261               std::memory_order_release,
 262               std::memory_order_relaxed)) {
 263         DEBUG_PRINT(this << " " << p);
 264         return p;
 265       }
 266     }
 267   }
 268   p = static_cast<hazptr_rec*>(mr_->allocate(sizeof(hazptr_rec)));
 269   if (p == nullptr) {
 270     return nullptr;
 271   }
 272   p->active_.store(true, std::memory_order_relaxed);
 273   p->next_ = hazptrs_.load(std::memory_order_acquire);
 274   do {
 275     if (hazptrs_.compare_exchange_weak(
 276             p->next_,
 277             p,
 278             std::memory_order_release,
 279             std::memory_order_acquire)) {
 280       break;
 281     }
 282   } while (true);
 283   auto hcount = hcount_.fetch_add(1);
 284   DEBUG_PRINT(this << " " << p << " " << sizeof(hazptr_rec) << " " << hcount);
 285   return p;
 286 }
 287
 288 inline void hazptr_domain::hazptrRelease(hazptr_rec* p) noexcept {
 289   DEBUG_PRINT(this << " " << p);
 290   p->release();
 291 }
 292
 293 inline int
 294 hazptr_domain::pushRetired(hazptr_obj* head, hazptr_obj* tail, int count) {
 295   /*** Full fence ***/ hazptr_mb::light();
 296   tail->next_ = retired_.load(std::memory_order_acquire);
 297   while (!retired_.compare_exchange_weak(
 298       tail->next_,
 299       head,
 300       std::memory_order_release,
 301       std::memory_order_acquire)) {
 302   }
 303   return rcount_.fetch_add(count);
 304 }
 305
 306 inline void hazptr_domain::objRetire(hazptr_obj* p) {
 307   auto rcount = pushRetired(p, p, 1) + 1;
 308   if (rcount >= HAZPTR_SCAN_THRESHOLD &&
 309       rcount >= HAZPTR_SCAN_MULT * hcount_.load(std::memory_order_acquire)) {
 310     tryBulkReclaim();
 311   }
 312 }
 313
 314 inline void hazptr_domain::tryBulkReclaim() {
 315   DEBUG_PRINT(this);
 316   do {
 317     auto hcount = hcount_.load(std::memory_order_acquire);
 318     auto rcount = rcount_.load(std::memory_order_acquire);
 319     if (rcount < HAZPTR_SCAN_THRESHOLD || rcount < HAZPTR_SCAN_MULT * hcount) {
 320       return;
 321     }
 322     if (rcount_.compare_exchange_weak(
 323             rcount, 0, std::memory_order_release, std::memory_order_relaxed)) {
 324       break;
 325     }
 326   } while (true);
 327   bulkReclaim();
 328 }
 329
 330 inline void hazptr_domain::bulkReclaim() {
 331   DEBUG_PRINT(this);
 332   /*** Full fence ***/ hazptr_mb::heavy();
 333   auto p = retired_.exchange(nullptr, std::memory_order_acquire);
 334   auto h = hazptrs_.load(std::memory_order_acquire);
 335   std::unordered_set<const void*> hs; // TODO lock-free alternative
 336   for (; h; h = h->next_) {
 337     hs.insert(h->hazptr_.load(std::memory_order_relaxed));
 338   }
 339   int rcount = 0;
 340   hazptr_obj* retired = nullptr;
 341   hazptr_obj* tail = nullptr;
 342   hazptr_obj* next;
 343   for (; p; p = next) {
 344     next = p->next_;
 345     if (hs.count(p->getObjPtr()) == 0) {
 346       DEBUG_PRINT(this << " " << p << " " << p->reclaim_);
 347       (*(p->reclaim_))(p);
 348     } else {
 349       p->next_ = retired;
 350       retired = p;
 351       if (tail == nullptr) {
 352         tail = p;
 353       }
 354       ++rcount;
 355     }
 356   }
 357   if (tail) {
 358     pushRetired(retired, tail, rcount);
 359   }
 360 }
 361
 362 /** hazptr_stats */
 363
 364 class hazptr_stats {
 365  public:
 366   ~hazptr_stats();
 367   void light();
 368   void heavy();
 369   void seq_cst();
 370
 371  private:
 372   std::atomic<uint64_t> light_{0};
 373   std::atomic<uint64_t> heavy_{0};
 374   std::atomic<uint64_t> seq_cst_{0};
 375 };
 376
 377 inline hazptr_stats::~hazptr_stats() {
 378   DEBUG_PRINT(this << " light " << light_.load());
 379   DEBUG_PRINT(this << " heavy " << heavy_.load());
 380   DEBUG_PRINT(this << " seq_cst " << seq_cst_.load());
 381 }
 382
 383 inline void hazptr_stats::light() {
 384   if (HAZPTR_STATS) {
 385     /* atomic */ ++light_;
 386   }
 387 }
 388
 389 inline void hazptr_stats::heavy() {
 390   if (HAZPTR_STATS) {
 391     /* atomic */ ++heavy_;
 392   }
 393 }
 394
 395 inline void hazptr_stats::seq_cst() {
 396   if (HAZPTR_STATS) {
 397     /* atomic */ ++seq_cst_;
 398   }
 399 }
 400
 401 inline class hazptr_stats& hazptr_stats() {
 402   static class hazptr_stats stats_;
 403   DEBUG_PRINT(&stats_);
 404   return stats_;
 405 }
 406
 407 /** hazptr_mb */
 408
 409 inline void hazptr_mb::light() {
 410   DEBUG_PRINT("");
 411   if (HAZPTR_AMB) {
 412     folly::asymmetricLightBarrier();
 413     hazptr_stats().light();
 414   } else {
 415     atomic_thread_fence(std::memory_order_seq_cst);
 416     hazptr_stats().seq_cst();
 417   }
 418 }
 419
 420 inline void hazptr_mb::heavy() {
 421   DEBUG_PRINT("");
 422   if (HAZPTR_AMB) {
 423     folly::asymmetricHeavyBarrier();
 424     hazptr_stats().heavy();
 425   } else {
 426     atomic_thread_fence(std::memory_order_seq_cst);
 427     hazptr_stats().seq_cst();
 428   }
 429 }
 430
 431 } // namespace folly
 432 } // namespace hazptr