2 * Copyright 2017 Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 /* override-include-guard */
19 #error "This should only be included by hazptr.h"
22 /* quality of implementation switches */
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.
29 #define HAZPTR_AMB true
32 #ifndef HAZPTR_SCAN_MULT
33 #define HAZPTR_SCAN_MULT 2
36 #ifndef HAZPTR_SCAN_THRESHOLD
37 #define HAZPTR_SCAN_THRESHOLD 1000
42 #define HAZPTR_STATS false
45 #include <folly/experimental/AsymmetricMemoryBarrier.h>
46 #include <folly/experimental/hazptr/debug.h>
48 #include <unordered_set>
54 * helper classes and functions
60 hazptr_stats& hazptr_stats();
76 constexpr hazptr_domain::hazptr_domain(memory_resource* mr) noexcept : mr_(mr) {
80 /** hazptr_obj_base */
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);
91 domain.objRetire(this);
97 friend class hazptr_domain;
98 template <typename> friend class hazptr_owner;
100 std::atomic<const void*> hazptr_ = {nullptr};
101 hazptr_rec* next_ = {nullptr};
102 std::atomic<bool> active_ = {false};
104 void set(const void* p) noexcept;
105 const void* get() const noexcept;
106 void clear() noexcept;
107 void release() noexcept;
112 template <typename T>
113 inline hazptr_owner<T>::hazptr_owner(hazptr_domain& domain) {
115 hazptr_ = domain_->hazptrAcquire();
116 DEBUG_PRINT(this << " " << domain_ << " " << hazptr_);
117 if (hazptr_ == nullptr) { std::bad_alloc e; throw e; }
120 template <typename T>
121 hazptr_owner<T>::~hazptr_owner() {
123 domain_->hazptrRelease(hazptr_);
126 template <typename T>
127 template <typename A>
128 inline bool hazptr_owner<T>::try_protect(T*& ptr, const A& src) noexcept {
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);
134 /*** Full fence ***/ hazptr_mb::light();
135 T* p = src.load(std::memory_order_acquire);
144 template <typename T>
145 template <typename A>
146 inline T* hazptr_owner<T>::get_protected(const A& src) noexcept {
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);
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);
163 template <typename T>
164 inline void hazptr_owner<T>::clear() noexcept {
169 template <typename T>
170 inline void hazptr_owner<T>::swap(hazptr_owner<T>& rhs) noexcept {
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_);
178 template <typename T>
179 inline void swap(hazptr_owner<T>& lhs, hazptr_owner<T>& rhs) noexcept {
183 ////////////////////////////////////////////////////////////////////////////////
185 // - Thread caching of hazptr_rec-s
186 // - Private storage of retired objects
187 // - Control of reclamation (when and by whom)
189 /** Definition of default_hazptr_domain() */
190 inline hazptr_domain& default_hazptr_domain() {
191 static hazptr_domain d;
198 inline void hazptr_rec::set(const void* p) noexcept {
199 DEBUG_PRINT(this << " " << p);
200 hazptr_.store(p, std::memory_order_release);
203 inline const void* hazptr_rec::get() const noexcept {
204 auto p = hazptr_.load(std::memory_order_acquire);
205 DEBUG_PRINT(this << " " << p);
209 inline void hazptr_rec::clear() noexcept {
211 hazptr_.store(nullptr, std::memory_order_release);
214 inline void hazptr_rec::release() noexcept {
217 active_.store(false, std::memory_order_release);
222 inline const void* hazptr_obj::getObjPtr() const {
229 inline hazptr_domain::~hazptr_domain() {
231 { /* reclaim all remaining retired objects */
233 auto retired = retired_.exchange(nullptr);
235 for (auto p = retired; p; p = next) {
239 retired = retired_.exchange(nullptr);
242 { /* free all hazptr_rec-s */
244 for (auto p = hazptrs_.load(std::memory_order_acquire); p; p = next) {
246 mr_->deallocate(static_cast<void*>(p), sizeof(hazptr_rec));
251 inline hazptr_rec* hazptr_domain::hazptrAcquire() {
254 for (p = hazptrs_.load(std::memory_order_acquire); p; p = next) {
256 bool active = p->active_.load(std::memory_order_acquire);
258 if (p->active_.compare_exchange_weak(
261 std::memory_order_release,
262 std::memory_order_relaxed)) {
263 DEBUG_PRINT(this << " " << p);
268 p = static_cast<hazptr_rec*>(mr_->allocate(sizeof(hazptr_rec)));
272 p->active_.store(true, std::memory_order_relaxed);
273 p->next_ = hazptrs_.load(std::memory_order_acquire);
275 if (hazptrs_.compare_exchange_weak(
278 std::memory_order_release,
279 std::memory_order_acquire)) {
283 auto hcount = hcount_.fetch_add(1);
284 DEBUG_PRINT(this << " " << p << " " << sizeof(hazptr_rec) << " " << hcount);
288 inline void hazptr_domain::hazptrRelease(hazptr_rec* p) noexcept {
289 DEBUG_PRINT(this << " " << p);
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(
300 std::memory_order_release,
301 std::memory_order_acquire)) {
303 return rcount_.fetch_add(count);
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)) {
314 inline void hazptr_domain::tryBulkReclaim() {
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) {
322 if (rcount_.compare_exchange_weak(
323 rcount, 0, std::memory_order_release, std::memory_order_relaxed)) {
330 inline void hazptr_domain::bulkReclaim() {
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));
340 hazptr_obj* retired = nullptr;
341 hazptr_obj* tail = nullptr;
343 for (; p; p = next) {
345 if (hs.count(p->getObjPtr()) == 0) {
346 DEBUG_PRINT(this << " " << p << " " << p->reclaim_);
351 if (tail == nullptr) {
358 pushRetired(retired, tail, rcount);
372 std::atomic<uint64_t> light_{0};
373 std::atomic<uint64_t> heavy_{0};
374 std::atomic<uint64_t> seq_cst_{0};
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());
383 inline void hazptr_stats::light() {
385 /* atomic */ ++light_;
389 inline void hazptr_stats::heavy() {
391 /* atomic */ ++heavy_;
395 inline void hazptr_stats::seq_cst() {
397 /* atomic */ ++seq_cst_;
401 inline class hazptr_stats& hazptr_stats() {
402 static class hazptr_stats stats_;
403 DEBUG_PRINT(&stats_);
409 inline void hazptr_mb::light() {
412 folly::asymmetricLightBarrier();
413 hazptr_stats().light();
415 atomic_thread_fence(std::memory_order_seq_cst);
416 hazptr_stats().seq_cst();
420 inline void hazptr_mb::heavy() {
423 folly::asymmetricHeavyBarrier();
424 hazptr_stats().heavy();
426 atomic_thread_fence(std::memory_order_seq_cst);
427 hazptr_stats().seq_cst();
432 } // namespace hazptr