folly/experimental/hazptr/hazptr-impl.h

   1 /*
   2  * Copyright 2016 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 #include <folly/experimental/hazptr/debug.h>
  23
  24 #include <unordered_set>
  25
  26 namespace folly {
  27 namespace hazptr {
  28
  29 /** hazptr_domain */
  30
  31 constexpr hazptr_domain::hazptr_domain(memory_resource* mr) noexcept
  32     : mr_(mr) {}
  33
  34 template <typename T>
  35 void hazptr_domain::flush(const hazptr_obj_reclaim<T>* reclaim) {
  36   DEBUG_PRINT(this << " " << reclaim);
  37   flush(reinterpret_cast<const hazptr_obj_reclaim<void>*>(reclaim));
  38 }
  39
  40 template <typename T>
  41 inline void hazptr_domain::objRetire(hazptr_obj_base<T>* p) {
  42   DEBUG_PRINT(this << " " << p);
  43   objRetire(reinterpret_cast<hazptr_obj_base<void>*>(p));
  44 }
  45
  46 /** hazptr_obj_base */
  47
  48 template <typename T>
  49 inline void hazptr_obj_base<T>::retire(
  50     hazptr_domain* domain,
  51     const hazptr_obj_reclaim<T>* reclaim,
  52     const storage_policy /* policy */) {
  53   DEBUG_PRINT(this << " " << reclaim << " " << &domain);
  54   reclaim_ = reclaim;
  55   domain->objRetire<T>(this);
  56 }
  57
  58 /* Definition of default_hazptr_obj_reclaim */
  59
  60 template <typename T>
  61 inline hazptr_obj_reclaim<T>* default_hazptr_obj_reclaim() {
  62   static hazptr_obj_reclaim<T> fn = [](T* p) {
  63     DEBUG_PRINT("default_hazptr_obj_reclaim " << p << " " << sizeof(T));
  64     delete p;
  65   };
  66   DEBUG_PRINT(&fn);
  67   return &fn;
  68 }
  69
  70 /** hazptr_rec */
  71
  72 class hazptr_rec {
  73   friend class hazptr_domain;
  74   template <typename> friend class hazptr_owner;
  75
  76   std::atomic<const void*> hazptr_ = {nullptr};
  77   hazptr_rec* next_ = {nullptr};
  78   std::atomic<bool> active_ = {false};
  79
  80   void set(const void* p) noexcept;
  81   const void* get() const noexcept;
  82   void clear() noexcept;
  83   void release() noexcept;
  84 };
  85
  86 /** hazptr_owner */
  87
  88 template <typename T>
  89 inline hazptr_owner<T>::hazptr_owner(
  90     hazptr_domain* domain,
  91     const cache_policy /* policy */) {
  92   domain_ = domain;
  93   hazptr_ = domain_->hazptrAcquire();
  94   DEBUG_PRINT(this << " " << domain_ << " " << hazptr_);
  95   if (hazptr_ == nullptr) { std::bad_alloc e; throw e; }
  96 }
  97
  98 template <typename T>
  99 hazptr_owner<T>::~hazptr_owner() noexcept {
 100   DEBUG_PRINT(this);
 101   domain_->hazptrRelease(hazptr_);
 102 }
 103
 104 template <typename T>
 105 inline bool hazptr_owner<T>::protect(const T* ptr, const std::atomic<T*>& src)
 106     const noexcept {
 107   DEBUG_PRINT(this << " " << ptr << " " << &src);
 108   hazptr_->set(ptr);
 109   // ORDER: store-load
 110   return (src.load() == ptr);
 111 }
 112
 113 template <typename T>
 114 inline void hazptr_owner<T>::set(const T* ptr) const noexcept {
 115   DEBUG_PRINT(this << " " << ptr);
 116   hazptr_->set(ptr);
 117 }
 118
 119 template <typename T>
 120 inline void hazptr_owner<T>::clear() const noexcept {
 121   DEBUG_PRINT(this);
 122   hazptr_->clear();
 123 }
 124
 125 template <typename T>
 126 inline void hazptr_owner<T>::swap(hazptr_owner<T>& rhs) noexcept {
 127   DEBUG_PRINT(
 128     this << " " <<  this->hazptr_ << " " << this->domain_ << " -- "
 129     << &rhs << " " << rhs.hazptr_ << " " << rhs.domain_);
 130   std::swap(this->domain_, rhs.domain_);
 131   std::swap(this->hazptr_, rhs.hazptr_);
 132 }
 133
 134 template <typename T>
 135 inline void swap(hazptr_owner<T>& lhs, hazptr_owner<T>& rhs) noexcept {
 136   lhs.swap(rhs);
 137 }
 138
 139 ////////////////////////////////////////////////////////////////////////////////
 140 // Non-template part of implementation
 141 ////////////////////////////////////////////////////////////////////////////////
 142 // [TODO]:
 143 // - Thread caching of hazptr_rec-s
 144 // - Private storage of retired objects
 145 // - Optimized memory order
 146
 147 /** Definition of default_hazptr_domain() */
 148 inline hazptr_domain* default_hazptr_domain() {
 149   static hazptr_domain d;
 150   return &d;
 151 }
 152
 153 /** hazptr_rec */
 154
 155 inline void hazptr_rec::set(const void* p) noexcept {
 156   DEBUG_PRINT(this << " " << p);
 157   hazptr_.store(p);
 158 }
 159
 160 inline const void* hazptr_rec::get() const noexcept {
 161   DEBUG_PRINT(this << " " << hazptr_.load());
 162   return hazptr_.load();
 163 }
 164
 165 inline void hazptr_rec::clear() noexcept {
 166   DEBUG_PRINT(this);
 167   // ORDER: release
 168   hazptr_.store(nullptr);
 169 }
 170
 171 inline void hazptr_rec::release() noexcept {
 172   DEBUG_PRINT(this);
 173   clear();
 174   // ORDER: release
 175   active_.store(false);
 176 }
 177
 178 /** hazptr_domain */
 179
 180 inline hazptr_domain::~hazptr_domain() {
 181   DEBUG_PRINT(this);
 182   { /* free all hazptr_rec-s */
 183     hazptr_rec* next;
 184     for (auto p = hazptrs_.load(); p; p = next) {
 185       next = p->next_;
 186       mr_->deallocate(static_cast<void*>(p), sizeof(hazptr_rec));
 187     }
 188   }
 189   { /* reclaim all remaining retired objects */
 190     hazptr_obj* next;
 191     for (auto p = retired_.load(); p; p = next) {
 192       next = p->next_;
 193       (*(p->reclaim_))(p);
 194     }
 195   }
 196 }
 197
 198 inline void hazptr_domain::flush() {
 199   DEBUG_PRINT(this);
 200   auto rcount = rcount_.exchange(0);
 201   auto p = retired_.exchange(nullptr);
 202   hazptr_obj* next;
 203   for (; p; p = next) {
 204     next = p->next_;
 205     (*(p->reclaim_))(p);
 206     --rcount;
 207   }
 208   rcount_.fetch_add(rcount);
 209 }
 210
 211 inline hazptr_rec* hazptr_domain::hazptrAcquire() {
 212   hazptr_rec* p;
 213   hazptr_rec* next;
 214   for (p = hazptrs_.load(); p; p = next) {
 215     next = p->next_;
 216     bool active = p->active_.load();
 217     if (!active) {
 218       if (p->active_.compare_exchange_weak(active, true)) {
 219         DEBUG_PRINT(this << " " << p);
 220         return p;
 221       }
 222     }
 223   }
 224   p = static_cast<hazptr_rec*>(mr_->allocate(sizeof(hazptr_rec)));
 225   if (p == nullptr) {
 226     return nullptr;
 227   }
 228   p->active_.store(true);
 229   do {
 230     p->next_ = hazptrs_.load();
 231     if (hazptrs_.compare_exchange_weak(p->next_, p)) {
 232       break;
 233     }
 234   } while (true);
 235   auto hcount = hcount_.fetch_add(1);
 236   DEBUG_PRINT(this << " " << p << " " << sizeof(hazptr_rec) << " " << hcount);
 237   return p;
 238 }
 239
 240 inline void hazptr_domain::hazptrRelease(hazptr_rec* p) const noexcept {
 241   DEBUG_PRINT(this << " " << p);
 242   p->release();
 243 }
 244
 245 inline int
 246 hazptr_domain::pushRetired(hazptr_obj* head, hazptr_obj* tail, int count) {
 247   tail->next_ = retired_.load();
 248   // ORDER: store-store order
 249   while (!retired_.compare_exchange_weak(tail->next_, head)) {}
 250   return rcount_.fetch_add(count);
 251 }
 252
 253 inline void hazptr_domain::objRetire(hazptr_obj* p) {
 254   auto rcount = pushRetired(p, p, 1) + 1;
 255   if (rcount >= kScanThreshold * hcount_.load()) {
 256     bulkReclaim();
 257   }
 258 }
 259
 260 inline void hazptr_domain::bulkReclaim() {
 261   DEBUG_PRINT(this);
 262   auto h = hazptrs_.load();
 263   auto hcount = hcount_.load();
 264   auto rcount = rcount_.load();
 265   do {
 266     if (rcount < kScanThreshold * hcount) {
 267       return;
 268     }
 269     if (rcount_.compare_exchange_weak(rcount, 0)) {
 270       break;
 271     }
 272   } while (true);
 273   /* ORDER: store-load order between removing each object and scanning
 274    * the hazard pointers -- can be combined in one fence */
 275   std::unordered_set<const void*> hs;
 276   for (; h; h = h->next_) {
 277     hs.insert(h->hazptr_.load());
 278   }
 279   rcount = 0;
 280   hazptr_obj* retired = nullptr;
 281   hazptr_obj* tail = nullptr;
 282   auto p = retired_.exchange(nullptr);
 283   hazptr_obj* next;
 284   for (; p; p = next) {
 285     next = p->next_;
 286     if (hs.count(p) == 0) {
 287       (*(p->reclaim_))(p);
 288     } else {
 289       p->next_ = retired;
 290       retired = p;
 291       if (tail == nullptr) {
 292         tail = p;
 293       }
 294       ++rcount;
 295     }
 296   }
 297   if (tail) {
 298     pushRetired(retired, tail, rcount);
 299   }
 300 }
 301
 302 inline void hazptr_domain::flush(const hazptr_obj_reclaim<void>* reclaim) {
 303   DEBUG_PRINT(this << " " << reclaim);
 304   auto rcount = rcount_.exchange(0);
 305   auto p = retired_.exchange(nullptr);
 306   hazptr_obj* retired = nullptr;
 307   hazptr_obj* tail = nullptr;
 308   hazptr_obj* next;
 309   for (; p; p = next) {
 310     next = p->next_;
 311     if (p->reclaim_ == reclaim) {
 312       (*reclaim)(p);
 313     } else {
 314       p->next_ = retired;
 315       retired = p;
 316       if (tail == nullptr) {
 317         tail = p;
 318       }
 319       ++rcount;
 320     }
 321   }
 322   if (tail) {
 323     pushRetired(retired, tail, rcount);
 324   }
 325 }
 326
 327 /** hazptr_user */
 328
 329 inline void hazptr_user::flush() {
 330   DEBUG_PRINT("");
 331 }
 332
 333 /** hazptr_remover */
 334
 335 inline void hazptr_remover::flush() {
 336   DEBUG_PRINT("");
 337 }
 338
 339 } // namespace folly
 340 } // namespace hazptr