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