/*
- * Copyright 2017 Facebook, Inc.
+ * Copyright 2017-present Facebook, Inc.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
-
/* override-include-guard */
#ifndef HAZPTR_H
#error "This should only be included by hazptr.h"
#define HAZPTR_PRIV true
#endif
+#ifndef HAZPTR_PRIV_THRESHOLD
+#define HAZPTR_PRIV_THRESHOLD 20
+#endif
+
#ifndef HAZPTR_ONE_DOMAIN
#define HAZPTR_ONE_DOMAIN false
#endif
#endif
#include <folly/concurrency/CacheLocality.h>
-#include <folly/experimental/AsymmetricMemoryBarrier.h>
#include <folly/experimental/hazptr/debug.h>
+#include <folly/synchronization/AsymmetricMemoryBarrier.h>
#include <mutex> // for thread caching
#include <unordered_set> // for hash set in bulk reclamation
struct hazptr_tc {
hazptr_tc_entry entry_[HAZPTR_TC_SIZE];
- int count_;
+ size_t count_;
+ bool local_; // for debug mode only
public:
+ hazptr_tc_entry& operator[](size_t i);
hazptr_rec* get();
bool put(hazptr_rec* hprec);
+ size_t count();
};
static_assert(
std::is_trivial<hazptr_tc>::value,
"hazptr_tc must be trivial to avoid a branch to check initialization");
+hazptr_tc* hazptr_tc_tls();
void hazptr_tc_init();
void hazptr_tc_shutdown();
hazptr_rec* hazptr_tc_try_get();
domain.objRetire(this);
}
+/**
+ * hazptr_obj_base_refcounted
+ */
+
+template <typename T, typename D>
+inline void hazptr_obj_base_refcounted<T, D>::retire(
+ hazptr_domain& domain,
+ D deleter) {
+ DEBUG_PRINT(this << " " << &domain);
+ preRetire(deleter);
+ if (HAZPTR_PRIV &&
+ (HAZPTR_ONE_DOMAIN || (&domain == &default_hazptr_domain()))) {
+ if (hazptr_priv_try_retire(this)) {
+ return;
+ }
+ }
+ domain.objRetire(this);
+}
+
+template <typename T, typename D>
+inline void hazptr_obj_base_refcounted<T, D>::acquire_ref() {
+ DEBUG_PRINT(this);
+ auto oldval = refcount_.fetch_add(1);
+ DCHECK(oldval >= 0);
+}
+
+template <typename T, typename D>
+inline void hazptr_obj_base_refcounted<T, D>::acquire_ref_safe() {
+ DEBUG_PRINT(this);
+ auto oldval = refcount_.load(std::memory_order_acquire);
+ DCHECK(oldval >= 0);
+ refcount_.store(oldval + 1, std::memory_order_release);
+}
+
+template <typename T, typename D>
+inline bool hazptr_obj_base_refcounted<T, D>::release_ref() {
+ DEBUG_PRINT(this);
+ auto oldval = refcount_.load(std::memory_order_acquire);
+ if (oldval > 0) {
+ oldval = refcount_.fetch_sub(1);
+ } else {
+ if (kIsDebug) {
+ refcount_.store(-1);
+ }
+ }
+ DEBUG_PRINT(this << " " << oldval);
+ DCHECK(oldval >= 0);
+ return oldval == 0;
+}
+
+template <typename T, typename D>
+inline void hazptr_obj_base_refcounted<T, D>::preRetire(D deleter) {
+ DCHECK(next_ == nullptr);
+ deleter_ = std::move(deleter);
+ reclaim_ = [](hazptr_obj* p) {
+ auto hrobp = static_cast<hazptr_obj_base_refcounted*>(p);
+ if (hrobp->release_ref()) {
+ auto obj = static_cast<T*>(hrobp);
+ hrobp->deleter_(obj);
+ }
+ };
+}
+
/**
* hazptr_rec
*/
-class hazptr_rec {
+class alignas(hardware_destructive_interference_size) hazptr_rec {
friend class hazptr_domain;
friend class hazptr_holder;
friend struct hazptr_tc_entry;
- FOLLY_ALIGN_TO_AVOID_FALSE_SHARING
std::atomic<const void*> hazptr_{nullptr};
hazptr_rec* next_{nullptr};
std::atomic<bool> active_{false};
if (hazptr_ == nullptr) { std::bad_alloc e; throw e; }
}
-FOLLY_ALWAYS_INLINE hazptr_holder::hazptr_holder(std::nullptr_t) {
+FOLLY_ALWAYS_INLINE hazptr_holder::hazptr_holder(std::nullptr_t) noexcept {
domain_ = nullptr;
hazptr_ = nullptr;
DEBUG_PRINT(this << " " << domain_ << " " << hazptr_);
lhs.swap(rhs);
}
+/**
+ * hazptr_array
+ */
+
+template <size_t M>
+FOLLY_ALWAYS_INLINE hazptr_array<M>::hazptr_array() {
+ auto h = reinterpret_cast<hazptr_holder*>(&raw_);
+ if (HAZPTR_TC) {
+ auto ptc = hazptr_tc_tls();
+ if (LIKELY(ptc != nullptr)) {
+ auto& tc = *ptc;
+ auto count = tc.count();
+ if (M <= count) {
+ size_t offset = count - M;
+ for (size_t i = 0; i < M; ++i) {
+ auto hprec = tc[offset + i].hprec_;
+ DCHECK(hprec != nullptr);
+ DEBUG_PRINT(i << " " << &h[i]);
+ new (&h[i]) hazptr_holder(nullptr);
+ h[i].hazptr_ = hprec;
+ DEBUG_PRINT(
+ i << " " << &h[i] << " " << h[i].domain_ << " " << h[i].hazptr_);
+ }
+ tc.count_ = offset;
+ return;
+ }
+ }
+ }
+ // slow path
+ for (size_t i = 0; i < M; ++i) {
+ new (&h[i]) hazptr_holder;
+ DEBUG_PRINT(
+ i << " " << &h[i] << " " << h[i].domain_ << " " << h[i].hazptr_);
+ }
+}
+
+template <size_t M>
+FOLLY_ALWAYS_INLINE hazptr_array<M>::hazptr_array(
+ hazptr_array&& other) noexcept {
+ DEBUG_PRINT(this << " " << M << " " << &other);
+ auto h = reinterpret_cast<hazptr_holder*>(&raw_);
+ auto hother = reinterpret_cast<hazptr_holder*>(&other.raw_);
+ for (size_t i = 0; i < M; ++i) {
+ new (&h[i]) hazptr_holder(std::move(hother[i]));
+ DEBUG_PRINT(i << " " << &h[i] << " " << &hother[i]);
+ }
+ empty_ = other.empty_;
+ other.empty_ = true;
+}
+
+template <size_t M>
+FOLLY_ALWAYS_INLINE hazptr_array<M>::hazptr_array(std::nullptr_t) noexcept {
+ DEBUG_PRINT(this << " " << M);
+ auto h = reinterpret_cast<hazptr_holder*>(&raw_);
+ for (size_t i = 0; i < M; ++i) {
+ new (&h[i]) hazptr_holder(nullptr);
+ DEBUG_PRINT(i << " " << &h[i]);
+ }
+ empty_ = true;
+}
+
+template <size_t M>
+FOLLY_ALWAYS_INLINE hazptr_array<M>::~hazptr_array() {
+ if (empty_) {
+ return;
+ }
+ auto h = reinterpret_cast<hazptr_holder*>(&raw_);
+ if (HAZPTR_TC) {
+ auto ptc = hazptr_tc_tls();
+ if (LIKELY(ptc != nullptr)) {
+ auto& tc = *ptc;
+ auto count = tc.count();
+ if ((M <= HAZPTR_TC_SIZE) && (count + M <= HAZPTR_TC_SIZE)) {
+ for (size_t i = 0; i < M; ++i) {
+ tc[count + i].hprec_ = h[i].hazptr_;
+ DEBUG_PRINT(i << " " << &h[i]);
+ new (&h[i]) hazptr_holder(nullptr);
+ DEBUG_PRINT(
+ i << " " << &h[i] << " " << h[i].domain_ << " " << h[i].hazptr_);
+ }
+ tc.count_ = count + M;
+ return;
+ }
+ }
+ }
+ // slow path
+ for (size_t i = 0; i < M; ++i) {
+ h[i].~hazptr_holder();
+ }
+}
+
+template <size_t M>
+FOLLY_ALWAYS_INLINE hazptr_array<M>& hazptr_array<M>::operator=(
+ hazptr_array&& other) noexcept {
+ DEBUG_PRINT(this << " " << M << " " << &other);
+ auto h = reinterpret_cast<hazptr_holder*>(&raw_);
+ for (size_t i = 0; i < M; ++i) {
+ h[i] = std::move(other[i]);
+ DEBUG_PRINT(i << " " << &h[i] << " " << &other[i]);
+ }
+ empty_ = other.empty_;
+ other.empty_ = true;
+ return *this;
+}
+
+template <size_t M>
+FOLLY_ALWAYS_INLINE hazptr_holder& hazptr_array<M>::operator[](
+ size_t i) noexcept {
+ auto h = reinterpret_cast<hazptr_holder*>(&raw_);
+ DCHECK(i < M);
+ return h[i];
+}
+
+/**
+ * hazptr_local
+ */
+
+template <size_t M>
+FOLLY_ALWAYS_INLINE hazptr_local<M>::hazptr_local() {
+ auto h = reinterpret_cast<hazptr_holder*>(&raw_);
+ if (HAZPTR_TC) {
+ auto ptc = hazptr_tc_tls();
+ if (LIKELY(ptc != nullptr)) {
+ auto& tc = *ptc;
+ auto count = tc.count();
+ if (M <= count) {
+ if (kIsDebug) {
+ DCHECK(!tc.local_);
+ tc.local_ = true;
+ }
+ // Fast path
+ for (size_t i = 0; i < M; ++i) {
+ auto hprec = tc[i].hprec_;
+ DCHECK(hprec != nullptr);
+ DEBUG_PRINT(i << " " << &h[i]);
+ new (&h[i]) hazptr_holder(nullptr);
+ h[i].hazptr_ = hprec;
+ DEBUG_PRINT(
+ i << " " << &h[i] << " " << h[i].domain_ << " " << h[i].hazptr_);
+ }
+ return;
+ }
+ }
+ }
+ // Slow path
+ need_destruct_ = true;
+ for (size_t i = 0; i < M; ++i) {
+ new (&h[i]) hazptr_holder;
+ DEBUG_PRINT(
+ i << " " << &h[i] << " " << h[i].domain_ << " " << h[i].hazptr_);
+ }
+}
+
+template <size_t M>
+FOLLY_ALWAYS_INLINE hazptr_local<M>::~hazptr_local() {
+ if (LIKELY(!need_destruct_)) {
+ if (kIsDebug) {
+ auto ptc = hazptr_tc_tls();
+ DCHECK(ptc != nullptr);
+ auto& tc = *ptc;
+ DCHECK(tc.local_);
+ tc.local_ = false;
+ }
+ return;
+ }
+ // Slow path
+ auto h = reinterpret_cast<hazptr_holder*>(&raw_);
+ for (size_t i = 0; i < M; ++i) {
+ h[i].~hazptr_holder();
+ }
+}
+
+template <size_t M>
+FOLLY_ALWAYS_INLINE hazptr_holder& hazptr_local<M>::operator[](
+ size_t i) noexcept {
+ auto h = reinterpret_cast<hazptr_holder*>(&raw_);
+ DCHECK(i < M);
+ return h[i];
+}
+
////////////////////////////////////////////////////////////////////////////////
// [TODO]:
// - Control of reclamation (when and by whom)
return default_domain_;
}
+template <typename T, typename D>
+FOLLY_ALWAYS_INLINE void hazptr_retire(T* obj, D reclaim) {
+ default_hazptr_domain().retire(obj, std::move(reclaim));
+}
+
/** hazptr_rec */
FOLLY_ALWAYS_INLINE void hazptr_rec::set(const void* p) noexcept {
/** hazptr_domain */
+template <typename T, typename D>
+void hazptr_domain::retire(T* obj, D reclaim) {
+ struct hazptr_retire_node : hazptr_obj {
+ std::unique_ptr<T, D> obj_;
+
+ hazptr_retire_node(T* obj, D reclaim) : obj_{obj, std::move(reclaim)} {}
+ };
+
+ auto node = new hazptr_retire_node(obj, std::move(reclaim));
+ node->reclaim_ = [](hazptr_obj* p) {
+ delete static_cast<hazptr_retire_node*>(p);
+ };
+ objRetire(node);
+}
+
inline hazptr_domain::~hazptr_domain() {
DEBUG_PRINT(this);
{ /* reclaim all remaining retired objects */
while (retired) {
for (auto p = retired; p; p = next) {
next = p->next_;
+ DCHECK(p != next);
+ DEBUG_PRINT(this << " " << p << " " << p->reclaim_);
(*(p->reclaim_))(p);
}
retired = retired_.exchange(nullptr);
p->active_.store(true, std::memory_order_relaxed);
p->next_ = hazptrs_.load(std::memory_order_acquire);
while (!hazptrs_.compare_exchange_weak(
- p->next_, p, std::memory_order_release, std::memory_order_acquire))
+ p->next_, p, std::memory_order_release, std::memory_order_acquire)) {
/* keep trying */;
+ }
auto hcount = hcount_.fetch_add(1);
DEBUG_PRINT(this << " " << p << " " << sizeof(hazptr_rec) << " " << hcount);
return p;
hazptr_obj* next;
for (; p; p = next) {
next = p->next_;
+ DCHECK(p != next);
if (hs.count(p->getObjPtr()) == 0) {
DEBUG_PRINT(this << " " << p << " " << p->reclaim_);
(*(p->reclaim_))(p);
/** hazptr_tc */
+FOLLY_ALWAYS_INLINE hazptr_tc_entry& hazptr_tc::operator[](size_t i) {
+ DCHECK(i <= HAZPTR_TC_SIZE);
+ return entry_[i];
+}
+
FOLLY_ALWAYS_INLINE hazptr_rec* hazptr_tc::get() {
if (LIKELY(count_ != 0)) {
auto hprec = entry_[--count_].get();
return false;
}
+FOLLY_ALWAYS_INLINE size_t hazptr_tc::count() {
+ return count_;
+}
+
/** hazptr_tc free functions */
-FOLLY_ALWAYS_INLINE hazptr_rec* hazptr_tc_try_get() {
- DEBUG_PRINT(TLS_UNINITIALIZED << TLS_ALIVE << TLS_DESTROYED);
+FOLLY_ALWAYS_INLINE hazptr_tc* hazptr_tc_tls() {
DEBUG_PRINT(tls_state_);
if (LIKELY(tls_state_ == TLS_ALIVE)) {
DEBUG_PRINT(tls_state_);
- return tls_tc_data_.get();
+ return &tls_tc_data_;
} else if (tls_state_ == TLS_UNINITIALIZED) {
tls_life_odr_use();
- return tls_tc_data_.get();
+ return &tls_tc_data_;
}
return nullptr;
}
-FOLLY_ALWAYS_INLINE bool hazptr_tc_try_put(hazptr_rec* hprec) {
- DEBUG_PRINT(tls_state_);
- if (LIKELY(tls_state_ == TLS_ALIVE)) {
- DEBUG_PRINT(tls_state_);
- return tls_tc_data_.put(hprec);
- }
- return false;
-}
-
inline void hazptr_tc_init() {
DEBUG_PRINT("");
auto& tc = tls_tc_data_;
DEBUG_PRINT(&tc);
tc.count_ = 0;
- for (int i = 0; i < HAZPTR_TC_SIZE; ++i) {
- tc.entry_[i].hprec_ = nullptr;
+ if (kIsDebug) {
+ tc.local_ = false;
}
}
inline void hazptr_tc_shutdown() {
auto& tc = tls_tc_data_;
DEBUG_PRINT(&tc);
- for (int i = 0; i < tc.count_; ++i) {
+ for (size_t i = 0; i < tc.count_; ++i) {
tc.entry_[i].evict();
}
}
+FOLLY_ALWAYS_INLINE hazptr_rec* hazptr_tc_try_get() {
+ DEBUG_PRINT(TLS_UNINITIALIZED << TLS_ALIVE << TLS_DESTROYED);
+ DEBUG_PRINT(tls_state_);
+ if (LIKELY(tls_state_ == TLS_ALIVE)) {
+ DEBUG_PRINT(tls_state_);
+ return tls_tc_data_.get();
+ } else if (tls_state_ == TLS_UNINITIALIZED) {
+ tls_life_odr_use();
+ return tls_tc_data_.get();
+ }
+ return nullptr;
+}
+
+FOLLY_ALWAYS_INLINE bool hazptr_tc_try_put(hazptr_rec* hprec) {
+ DEBUG_PRINT(tls_state_);
+ if (LIKELY(tls_state_ == TLS_ALIVE)) {
+ DEBUG_PRINT(tls_state_);
+ return tls_tc_data_.put(hprec);
+ }
+ return false;
+}
+
/**
* hazptr_priv
*/
head_ = obj;
}
tail_ = obj;
- ++rcount_;
- if (domain.reachedThreshold(rcount_)) {
+ if (++rcount_ >= HAZPTR_PRIV_THRESHOLD) {
pushAllToDomain();
}
}
tls_state_ = TLS_DESTROYED;
}
-} // namespace folly
+/** hazptr_obj_batch */
+/* Only for default domain. Supports only hazptr_obj_base_refcounted
+ * and a thread-safe access only, for now. */
+
+class hazptr_obj_batch {
+ static constexpr size_t DefaultThreshold = 20;
+ hazptr_obj* head_{nullptr};
+ hazptr_obj* tail_{nullptr};
+ size_t rcount_{0};
+ size_t threshold_{DefaultThreshold};
+
+ public:
+ hazptr_obj_batch() {}
+ hazptr_obj_batch(hazptr_obj* head, hazptr_obj* tail, size_t rcount)
+ : head_(head), tail_(tail), rcount_(rcount) {}
+
+ ~hazptr_obj_batch() {
+ retire_all();
+ }
+
+ /* Prepare a hazptr_obj_base_refcounted for retirement but don't
+ push it the domain yet. Return true if the batch is ready. */
+ template <typename T, typename D = std::default_delete<T>>
+ hazptr_obj_batch prep_retire_refcounted(
+ hazptr_obj_base_refcounted<T, D>* obj,
+ D deleter = {}) {
+ obj->preRetire(deleter);
+ obj->next_ = head_;
+ head_ = obj;
+ if (tail_ == nullptr) {
+ tail_ = obj;
+ }
+ if (++rcount_ < threshold_) {
+ return hazptr_obj_batch();
+ } else {
+ auto head = head_;
+ auto tail = tail_;
+ auto rcount = rcount_;
+ clear();
+ return hazptr_obj_batch(head, tail, rcount);
+ }
+ }
+
+ bool empty() {
+ return rcount_ == 0;
+ }
+
+ void retire_all() {
+ if (!empty()) {
+ auto& domain = default_hazptr_domain();
+ domain.pushRetired(head_, tail_, rcount_);
+ domain.tryBulkReclaim();
+ clear();
+ }
+ }
+
+ void set_threshold(size_t thresh) {
+ threshold_ = thresh;
+ }
+
+ private:
+ void clear() {
+ head_ = nullptr;
+ tail_ = nullptr;
+ rcount_ = 0;
+ }
+};
+
} // namespace hazptr
+} // namespace folly
projects / folly.git / blobdiff