--- /dev/null
+/*
+ * Copyright 2016 Facebook, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+#pragma once
+
+#include <glog/logging.h>
+
+#define DO_DEBUG true
+
+#define DEBUG_PRINT(...) \
+ do { \
+ if (DO_DEBUG) { \
+ VLOG(2) << __func__ << " --- " << __VA_ARGS__; \
+ } \
+ } while (false)
--- /dev/null
+/*
+ * Copyright 2016 Facebook, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+#pragma once
+
+#include <folly/experimental/hazptr/debug.h>
+#include <folly/experimental/hazptr/hazptr.h>
+
+namespace folly {
+namespace hazptr {
+
+template <typename T>
+class LockFreeLIFO {
+ class Node : public hazptr_obj_base<Node> {
+ friend LockFreeLIFO;
+ public:
+ ~Node() {
+ DEBUG_PRINT(this);
+ }
+ private:
+ Node(T v, Node* n) : value_(v), next_(n) {
+ DEBUG_PRINT(this);
+ }
+ T value_;
+ Node* next_;
+ };
+
+ public:
+ LockFreeLIFO() {
+ DEBUG_PRINT(this);
+ }
+
+ ~LockFreeLIFO() {
+ DEBUG_PRINT(this);
+ }
+
+ void push(T val) {
+ DEBUG_PRINT(this);
+ auto pnode = new Node(val, head_.load());
+ while (!head_.compare_exchange_weak(pnode->next_, pnode));
+ }
+
+ bool pop(T& val) {
+ DEBUG_PRINT(this);
+ hazptr_owner<Node> hptr;
+ Node* pnode;
+ while (true) {
+ if ((pnode = head_.load()) == nullptr) return false;
+ if (!hptr.protect(pnode, head_)) continue;
+ auto next = pnode->next_;
+ if (head_.compare_exchange_weak(pnode, next)) break;
+ }
+ hptr.clear();
+ val = pnode->value_;
+ pnode->retire();
+ return true;
+ }
+
+ private:
+ std::atomic<Node*> head_ = {nullptr};
+};
+
+} // namespace folly {
+} // namespace hazptr {
--- /dev/null
+/*
+ * Copyright 2016 Facebook, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+#pragma once
+
+#include <folly/experimental/hazptr/debug.h>
+#include <folly/experimental/hazptr/hazptr.h>
+
+namespace folly {
+namespace hazptr {
+
+/** Set implemented as an ordered singly-linked list.
+ *
+ * A single writer thread may add or remove elements. Multiple reader
+ * threads may search the set concurrently with each other and with
+ * the writer's operations.
+ */
+template <typename T>
+class SWMRListSet {
+ class Node : public hazptr_obj_base<Node> {
+ friend SWMRListSet;
+ T elem_;
+ std::atomic<Node*> next_;
+
+ Node(T e, Node* n) : elem_(e), next_(n) {
+ DEBUG_PRINT(this << " " << e << " " << n);
+ }
+
+ public:
+ ~Node() {
+ DEBUG_PRINT(this);
+ }
+ };
+
+ std::atomic<Node*> head_ = {nullptr};
+ hazptr_domain* domain_;
+ hazptr_obj_reclaim<Node> reclaim_ = [](Node* p) { reclaim(p); };
+
+ static void reclaim(Node* p) {
+ DEBUG_PRINT(p << " " << sizeof(Node));
+ delete p;
+ };
+
+ /* Used by the single writer */
+ void locate_lower_bound(T v, std::atomic<Node*>*& prev) {
+ auto curr = prev->load();
+ while (curr) {
+ if (curr->elem_ >= v) break;
+ prev = &(curr->next_);
+ curr = curr->next_.load();
+ }
+ return;
+ }
+
+ public:
+ explicit SWMRListSet(hazptr_domain* domain = default_hazptr_domain())
+ : domain_(domain) {}
+
+ ~SWMRListSet() {
+ Node* next;
+ for (auto p = head_.load(); p; p = next) {
+ next = p->next_.load();
+ delete p;
+ }
+ domain_->flush(&reclaim_); /* avoid destruction order fiasco */
+ }
+
+ bool add(T v) {
+ auto prev = &head_;
+ locate_lower_bound(v, prev);
+ auto curr = prev->load();
+ if (curr && curr->elem_ == v) return false;
+ prev->store(new Node(v, curr));
+ return true;
+ }
+
+ bool remove(T v) {
+ auto prev = &head_;
+ locate_lower_bound(v, prev);
+ auto curr = prev->load();
+ if (!curr || curr->elem_ != v) return false;
+ prev->store(curr->next_.load());
+ curr->retire(domain_, &reclaim_);
+ return true;
+ }
+ /* Used by readers */
+ bool contains(T val) {
+ /* Acquire two hazard pointers for hand-over-hand traversal. */
+ hazptr_owner<Node> hptr_prev(domain_);
+ hazptr_owner<Node> hptr_curr(domain_);
+ T elem;
+ bool done = false;
+ while (!done) {
+ auto prev = &head_;
+ auto curr = prev->load();
+ while (true) {
+ if (!curr) { done = true; break; }
+ if (!hptr_curr.protect(curr, *prev)) break;
+ auto next = curr->next_.load();
+ elem = curr->elem_;
+ // Load-load order
+ std::atomic_thread_fence(std::memory_order_acquire);
+ if (prev->load() != curr) break;
+ if (elem >= val) { done = true; break; }
+ prev = &(curr->next_);
+ curr = next;
+ /* Swap does not change the values of the owned hazard
+ * pointers themselves. After the swap, The hazard pointer
+ * owned by hptr_prev continues to protect the node that
+ * contains the pointer *prev. The hazard pointer owned by
+ * hptr_curr will continue to protect the node that contains
+ * the old *prev (unless the old prev was &head), which no
+ * longer needs protection, so hptr_curr's hazard pointer is
+ * now free to protect *curr in the next iteration (if curr !=
+ * null).
+ */
+ swap(hptr_curr, hptr_prev);
+ }
+ }
+ return elem == val;
+ /* The hazard pointers are released automatically. */
+ }
+};
+
+} // namespace folly {
+} // namespace hazptr {
--- /dev/null
+/*
+ * Copyright 2016 Facebook, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+#pragma once
+
+#include <folly/experimental/hazptr/debug.h>
+#include <folly/experimental/hazptr/hazptr.h>
+
+#include <string>
+
+namespace folly {
+namespace hazptr {
+
+/** Wide CAS.
+ */
+class WideCAS {
+ using T = std::string;
+ class Node : public hazptr_obj_base<Node> {
+ friend WideCAS;
+ T val_;
+ Node() : val_(T()) { DEBUG_PRINT(this << " " << val_); }
+ explicit Node(T v) : val_(v) { DEBUG_PRINT(this << " " << v); }
+ public:
+ ~Node() { DEBUG_PRINT(this); }
+ };
+
+ std::atomic<Node*> p_ = {new Node()};
+
+ public:
+ WideCAS() = default;
+ ~WideCAS() {
+ DEBUG_PRINT(this << " " << p_.load());
+ delete p_.load();
+ }
+
+ bool cas(T& u, T& v) {
+ DEBUG_PRINT(this << " " << u << " " << v);
+ Node* n = new Node(v);
+ hazptr_owner<Node> hptr;
+ Node* p = p_.load();
+ do {
+ if (!hptr.protect(p, p_)) continue;
+ if (p->val_ != u) { delete n; return false; }
+ if (p_.compare_exchange_weak(p, n)) break;
+ } while (true);
+ hptr.clear();
+ p->retire();
+ DEBUG_PRINT(this << " " << p << " " << u << " " << n << " " << v);
+ return true;
+ }
+};
+
+} // namespace folly {
+} // namespace hazptr {
--- /dev/null
+/*
+ * Copyright 2016 Facebook, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * 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"
+#endif
+
+#include <folly/experimental/hazptr/debug.h>
+
+#include <unordered_set>
+
+namespace folly {
+namespace hazptr {
+
+/** hazptr_domain */
+
+constexpr hazptr_domain::hazptr_domain(memory_resource* mr) noexcept
+ : mr_(mr) {}
+
+template <typename T>
+void hazptr_domain::flush(const hazptr_obj_reclaim<T>* reclaim) {
+ DEBUG_PRINT(this << " " << reclaim);
+ flush(reinterpret_cast<const hazptr_obj_reclaim<void>*>(reclaim));
+}
+
+template <typename T>
+inline void hazptr_domain::objRetire(hazptr_obj_base<T>* p) {
+ DEBUG_PRINT(this << " " << p);
+ objRetire(reinterpret_cast<hazptr_obj_base<void>*>(p));
+}
+
+/** hazptr_obj_base */
+
+template <typename T>
+inline void hazptr_obj_base<T>::retire(
+ hazptr_domain* domain,
+ const hazptr_obj_reclaim<T>* reclaim,
+ const storage_policy /* policy */) {
+ DEBUG_PRINT(this << " " << reclaim << " " << &domain);
+ reclaim_ = reclaim;
+ domain->objRetire<T>(this);
+}
+
+/* Definition of default_hazptr_obj_reclaim */
+
+template <typename T>
+inline hazptr_obj_reclaim<T>* default_hazptr_obj_reclaim() {
+ static hazptr_obj_reclaim<T> fn = [](T* p) {
+ DEBUG_PRINT("default_hazptr_obj_reclaim " << p << " " << sizeof(T));
+ delete p;
+ };
+ DEBUG_PRINT(&fn);
+ return &fn;
+}
+
+/** hazptr_rec */
+
+class hazptr_rec {
+ friend class hazptr_domain;
+ template <typename> friend class hazptr_owner;
+
+ std::atomic<const void*> hazptr_ = {nullptr};
+ hazptr_rec* next_ = {nullptr};
+ std::atomic<bool> active_ = {false};
+
+ void set(const void* p) noexcept;
+ const void* get() const noexcept;
+ void clear() noexcept;
+ void release() noexcept;
+};
+
+/** hazptr_owner */
+
+template <typename T>
+inline hazptr_owner<T>::hazptr_owner(
+ hazptr_domain* domain,
+ const cache_policy /* policy */) {
+ domain_ = domain;
+ hazptr_ = domain_->hazptrAcquire();
+ DEBUG_PRINT(this << " " << domain_ << " " << hazptr_);
+ if (hazptr_ == nullptr) { std::bad_alloc e; throw e; }
+}
+
+template <typename T>
+hazptr_owner<T>::~hazptr_owner() noexcept {
+ DEBUG_PRINT(this);
+ domain_->hazptrRelease(hazptr_);
+}
+
+template <typename T>
+inline bool hazptr_owner<T>::protect(const T* ptr, const std::atomic<T*>& src)
+ const noexcept {
+ DEBUG_PRINT(this << " " << ptr << " " << &src);
+ hazptr_->set(ptr);
+ // ORDER: store-load
+ return (src.load() == ptr);
+}
+
+template <typename T>
+inline void hazptr_owner<T>::set(const T* ptr) const noexcept {
+ DEBUG_PRINT(this << " " << ptr);
+ hazptr_->set(ptr);
+}
+
+template <typename T>
+inline void hazptr_owner<T>::clear() const noexcept {
+ DEBUG_PRINT(this);
+ hazptr_->clear();
+}
+
+template <typename T>
+inline void swap(hazptr_owner<T>& lhs, hazptr_owner<T>& rhs) noexcept {
+ DEBUG_PRINT(
+ &lhs << " " << lhs.hazptr_ << " " << lhs.domain_ << " -- "
+ << &rhs << " " << rhs.hazptr_ << " " << rhs.domain_);
+ std::swap(lhs.domain_, rhs.domain_);
+ std::swap(lhs.hazptr_, rhs.hazptr_);
+}
+
+////////////////////////////////////////////////////////////////////////////////
+// Non-template part of implementation
+////////////////////////////////////////////////////////////////////////////////
+// [TODO]:
+// - Thread caching of hazptr_rec-s
+// - Private storage of retired objects
+// - Optimized memory order
+
+/** Definition of default_hazptr_domain() */
+inline hazptr_domain* default_hazptr_domain() {
+ static hazptr_domain d;
+ return &d;
+}
+
+/** hazptr_rec */
+
+inline void hazptr_rec::set(const void* p) noexcept {
+ DEBUG_PRINT(this << " " << p);
+ hazptr_.store(p);
+}
+
+inline const void* hazptr_rec::get() const noexcept {
+ DEBUG_PRINT(this << " " << hazptr_.load());
+ return hazptr_.load();
+}
+
+inline void hazptr_rec::clear() noexcept {
+ DEBUG_PRINT(this);
+ // ORDER: release
+ hazptr_.store(nullptr);
+}
+
+inline void hazptr_rec::release() noexcept {
+ DEBUG_PRINT(this);
+ clear();
+ // ORDER: release
+ active_.store(false);
+}
+
+/** hazptr_domain */
+
+inline hazptr_domain::~hazptr_domain() {
+ DEBUG_PRINT(this);
+ { /* free all hazptr_rec-s */
+ hazptr_rec* next;
+ for (auto p = hazptrs_.load(); p; p = next) {
+ next = p->next_;
+ mr_->deallocate(static_cast<void*>(p), sizeof(hazptr_rec));
+ }
+ }
+ { /* reclaim all remaining retired objects */
+ hazptr_obj* next;
+ for (auto p = retired_.load(); p; p = next) {
+ next = p->next_;
+ (*(p->reclaim_))(p);
+ }
+ }
+}
+
+inline void hazptr_domain::flush() {
+ DEBUG_PRINT(this);
+ auto rcount = rcount_.exchange(0);
+ auto p = retired_.exchange(nullptr);
+ hazptr_obj* next;
+ for (; p; p = next) {
+ next = p->next_;
+ (*(p->reclaim_))(p);
+ --rcount;
+ }
+ rcount_.fetch_add(rcount);
+}
+
+inline hazptr_rec* hazptr_domain::hazptrAcquire() {
+ hazptr_rec* p;
+ hazptr_rec* next;
+ for (p = hazptrs_.load(); p; p = next) {
+ next = p->next_;
+ bool active = p->active_.load();
+ if (!active) {
+ if (p->active_.compare_exchange_weak(active, true)) {
+ DEBUG_PRINT(this << " " << p);
+ return p;
+ }
+ }
+ }
+ p = static_cast<hazptr_rec*>(mr_->allocate(sizeof(hazptr_rec)));
+ if (p == nullptr) {
+ return nullptr;
+ }
+ p->active_.store(true);
+ do {
+ p->next_ = hazptrs_.load();
+ if (hazptrs_.compare_exchange_weak(p->next_, p)) {
+ break;
+ }
+ } while (true);
+ auto hcount = hcount_.fetch_add(1);
+ DEBUG_PRINT(this << " " << p << " " << sizeof(hazptr_rec) << " " << hcount);
+ return p;
+}
+
+inline void hazptr_domain::hazptrRelease(hazptr_rec* p) const noexcept {
+ DEBUG_PRINT(this << " " << p);
+ p->release();
+}
+
+inline int
+hazptr_domain::pushRetired(hazptr_obj* head, hazptr_obj* tail, int count) {
+ tail->next_ = retired_.load();
+ // ORDER: store-store order
+ while (!retired_.compare_exchange_weak(tail->next_, head)) {}
+ return rcount_.fetch_add(count);
+}
+
+inline void hazptr_domain::objRetire(hazptr_obj* p) {
+ auto rcount = pushRetired(p, p, 1) + 1;
+ if (rcount >= kScanThreshold * hcount_.load()) {
+ bulkReclaim();
+ }
+}
+
+inline void hazptr_domain::bulkReclaim() {
+ DEBUG_PRINT(this);
+ auto h = hazptrs_.load();
+ auto hcount = hcount_.load();
+ auto rcount = rcount_.load();
+ do {
+ if (rcount < kScanThreshold * hcount) {
+ return;
+ }
+ if (rcount_.compare_exchange_weak(rcount, 0)) {
+ break;
+ }
+ } while (true);
+ /* ORDER: store-load order between removing each object and scanning
+ * the hazard pointers -- can be combined in one fence */
+ std::unordered_set<const void*> hs;
+ for (; h; h = h->next_) {
+ hs.insert(h->hazptr_.load());
+ }
+ rcount = 0;
+ hazptr_obj* retired = nullptr;
+ hazptr_obj* tail = nullptr;
+ auto p = retired_.exchange(nullptr);
+ hazptr_obj* next;
+ for (; p; p = next) {
+ next = p->next_;
+ if (hs.count(p) == 0) {
+ (*(p->reclaim_))(p);
+ } else {
+ p->next_ = retired;
+ retired = p;
+ if (tail == nullptr) {
+ tail = p;
+ }
+ ++rcount;
+ }
+ }
+ if (tail) {
+ pushRetired(retired, tail, rcount);
+ }
+}
+
+inline void hazptr_domain::flush(const hazptr_obj_reclaim<void>* reclaim) {
+ DEBUG_PRINT(this << " " << reclaim);
+ auto rcount = rcount_.exchange(0);
+ auto p = retired_.exchange(nullptr);
+ hazptr_obj* retired = nullptr;
+ hazptr_obj* tail = nullptr;
+ hazptr_obj* next;
+ for (; p; p = next) {
+ next = p->next_;
+ if (p->reclaim_ == reclaim) {
+ (*reclaim)(p);
+ } else {
+ p->next_ = retired;
+ retired = p;
+ if (tail == nullptr) {
+ tail = p;
+ }
+ ++rcount;
+ }
+ }
+ if (tail) {
+ pushRetired(retired, tail, rcount);
+ }
+}
+
+/** hazptr_user */
+
+inline void hazptr_user::flush() {
+ DEBUG_PRINT("");
+}
+
+/** hazptr_remover */
+
+inline void hazptr_remover::flush() {
+ DEBUG_PRINT("");
+}
+
+} // namespace folly
+} // namespace hazptr
--- /dev/null
+/*
+ * Copyright 2016 Facebook, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+#pragma once
+#define HAZPTR_H
+
+#include <atomic>
+#include <functional>
+#include <memory>
+
+/* Stand-in for std::pmr::memory_resource */
+#include <folly/experimental/hazptr/memory_resource.h>
+
+namespace folly {
+namespace hazptr {
+
+/** hazptr_rec: Private class that contains hazard pointers. */
+class hazptr_rec;
+
+/** hazptr_obj_base: Base template for objects protected by hazard pointers. */
+template <typename T> class hazptr_obj_base;
+
+/** Alias for object reclamation function template */
+template <typename T> using hazptr_obj_reclaim = std::function<void(T*)>;
+
+/** hazptr_domain: Class of hazard pointer domains. Each domain manages a set
+ * of hazard pointers and a set of retired objects. */
+class hazptr_domain {
+ public:
+ constexpr explicit hazptr_domain(
+ memory_resource* = get_default_resource()) noexcept;
+ ~hazptr_domain();
+
+ hazptr_domain(const hazptr_domain&) = delete;
+ hazptr_domain(hazptr_domain&&) = delete;
+ hazptr_domain& operator=(const hazptr_domain&) = delete;
+ hazptr_domain& operator=(hazptr_domain&&) = delete;
+
+ /* Reclaim all retired objects with a specific reclamation
+ * function currently stored by this domain */
+ template <typename T> void flush(const hazptr_obj_reclaim<T>* reclaim);
+ /* Reclaim all retired objects currently stored by this domain */
+ void flush();
+
+ private:
+ template <typename> friend class hazptr_obj_base;
+ template <typename> friend class hazptr_owner;
+
+ using hazptr_obj = hazptr_obj_base<void>;
+
+ /** Constant -- May be changed to parameter in the future */
+ enum { kScanThreshold = 3 };
+
+ memory_resource* mr_;
+ std::atomic<hazptr_rec*> hazptrs_ = {nullptr};
+ std::atomic<hazptr_obj*> retired_ = {nullptr};
+ std::atomic<int> hcount_ = {0};
+ std::atomic<int> rcount_ = {0};
+
+ template <typename T> void objRetire(hazptr_obj_base<T>*);
+ hazptr_rec* hazptrAcquire();
+ void hazptrRelease(hazptr_rec*) const noexcept;
+ void objRetire(hazptr_obj*);
+ int pushRetired(hazptr_obj* head, hazptr_obj* tail, int count);
+ void bulkReclaim();
+ void flush(const hazptr_obj_reclaim<void>* reclaim);
+};
+
+/** Get the default hazptr_domain */
+hazptr_domain* default_hazptr_domain();
+
+/** Declaration of default reclamation function template */
+template <typename T> hazptr_obj_reclaim<T>* default_hazptr_obj_reclaim();
+
+/** Definition of hazptr_obj_base */
+template <typename T> class hazptr_obj_base {
+ public:
+ /* Policy for storing retired objects */
+ enum class storage_policy { priv, shared };
+
+ /* Retire a removed object and pass the responsibility for
+ * reclaiming it to the hazptr library */
+ void retire(
+ hazptr_domain* domain = default_hazptr_domain(),
+ const hazptr_obj_reclaim<T>* reclaim = default_hazptr_obj_reclaim<T>(),
+ const storage_policy policy = storage_policy::shared);
+
+ private:
+ friend class hazptr_domain;
+ template <typename> friend class hazptr_owner;
+
+ const hazptr_obj_reclaim<T>* reclaim_;
+ hazptr_obj_base* next_;
+};
+
+/** hazptr_owner: Template for automatic acquisition and release of
+ * hazard pointers, and interface for hazard pointer operations. */
+template <typename T> class hazptr_owner;
+
+/* Swap ownership of hazard ponters between hazptr_owner-s. */
+/* Note: The owned hazard pointers remain unmodified during the swap
+ * and continue to protect the respective objects that they were
+ * protecting before the swap, if any. */
+template <typename T>
+void swap(hazptr_owner<T>&, hazptr_owner<T>&) noexcept;
+
+template <typename T> class hazptr_owner {
+ public:
+ /* Policy for caching hazard pointers */
+ enum class cache_policy { cache, nocache };
+
+ /* Constructor automatically acquires a hazard pointer. */
+ explicit hazptr_owner(
+ hazptr_domain* domain = default_hazptr_domain(),
+ const cache_policy policy = cache_policy::nocache);
+
+ /* Destructor automatically clears and releases the owned hazard pointer. */
+ ~hazptr_owner() noexcept;
+
+ /* Copy and move constructors and assignment operators are
+ * disallowed because:
+ * - Each hazptr_owner owns exactly one hazard pointer at any time.
+ * - Each hazard pointer may have up to one owner at any time. */
+ hazptr_owner(const hazptr_owner&) = delete;
+ hazptr_owner(hazptr_owner&&) = delete;
+ hazptr_owner& operator=(const hazptr_owner&) = delete;
+ hazptr_owner& operator=(hazptr_owner&&) = delete;
+
+ /** Hazard pointer operations */
+ /* Return true if successful in protecting the object */
+ bool protect(const T* ptr, const std::atomic<T*>& src) const noexcept;
+ /* Set the hazard pointer to ptr */
+ void set(const T* ptr) const noexcept;
+ /* Clear the hazard pointer */
+ void clear() const noexcept;
+
+ private:
+ friend void swap<T>(hazptr_owner&, hazptr_owner&) noexcept;
+
+ hazptr_domain* domain_;
+ hazptr_rec* hazptr_;
+};
+
+/** hazptr_user: Thread-specific interface for users of hazard
+ * pointers (i.e., threads that own hazard pointers by using
+ * hazptr_owner. */
+class hazptr_user {
+ public:
+ /* Release all hazptr_rec-s cached by this thread */
+ static void flush();
+};
+
+/** hazptr_remover: Thread-specific interface for removers of objects
+ * protected by hazard pointersd, i.e., threads that call the retire
+ * member function of hazptr_obj_base. */
+class hazptr_remover {
+ public:
+ /* Pass responsibility of reclaiming any retired objects stored
+ * privately by this thread to the hazptr_domain to which they
+ * belong. */
+ static void flush();
+};
+
+} // namespace hazptr
+} // namespace folly
+
+////////////////////////////////////////////////////////////////////////////////
+/// Notes
+////////////////////////////////////////////////////////////////////////////////
+
+/* The hazptr_obj_base template uses a reclamation function as a
+ * parameter for the retire() member function instead of taking an
+ * allocator template as an extra template parameter because objects
+ * of the same type may need different reclamation functions. */
+
+/* The hazptr interface supports reclamation by one domain at a
+ * time. If an abject belongs to multiple domains simultaneously, a
+ * workaround may be to design reclamation functions to form a series
+ * of retirements from one domain to the next until it reaches the
+ * final domain in the series that finally reclaims the object. */
+
+////////////////////////////////////////////////////////////////////////////////
+
+#include "hazptr-impl.h"
--- /dev/null
+/*
+ * Copyright 2016 Facebook, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+#pragma once
+
+namespace folly {
+namespace hazptr {
+
+////////////////////////////////////////////////////////////////////////////////
+/// Disclaimer: This is intended only as a partial stand-in for
+/// std::pmr::memory_resource (C++17) as needed for developing a
+/// hazptr prototype.
+////////////////////////////////////////////////////////////////////////////////
+#include <memory>
+
+class memory_resource {
+ public:
+ virtual ~memory_resource() = default;
+ virtual void* allocate(
+ const size_t bytes,
+ const size_t alignment = alignof(std::max_align_t)) = 0;
+ virtual void deallocate(
+ void* p,
+ const size_t bytes,
+ const size_t alignment = alignof(std::max_align_t)) = 0;
+};
+
+memory_resource* get_default_resource();
+void set_default_resource(memory_resource*);
+memory_resource* new_delete_resource();
+
+////////////////////////////////////////////////////////////////////////////////
+/// Implementation
+////////////////////////////////////////////////////////////////////////////////
+#include <folly/experimental/hazptr/debug.h>
+
+inline memory_resource** default_mr_ptr() {
+ static memory_resource* default_mr = new_delete_resource();
+ DEBUG_PRINT(&default_mr << " " << default_mr);
+ return &default_mr;
+}
+
+inline memory_resource* get_default_resource() {
+ DEBUG_PRINT("");
+ return *default_mr_ptr();
+}
+
+inline void set_default_resource(memory_resource* mr) {
+ DEBUG_PRINT("");
+ *default_mr_ptr() = mr;
+}
+
+inline memory_resource* new_delete_resource() {
+ class new_delete : public memory_resource {
+ public:
+ void* allocate(
+ const size_t bytes,
+ const size_t alignment = alignof(std::max_align_t)) {
+ (void)alignment;
+ void* p = static_cast<void*>(new char[bytes]);
+ DEBUG_PRINT(this << " " << p << " " << bytes);
+ return p;
+ }
+ void deallocate(
+ void* p,
+ const size_t bytes,
+ const size_t alignment = alignof(std::max_align_t)) {
+ (void)alignment;
+ (void)bytes;
+ DEBUG_PRINT(p << " " << bytes);
+ delete[] static_cast<char*>(p);
+ }
+ };
+ static new_delete mr;
+ return &mr;
+}
+
+} // namespace folly {
+} // namespace hazptr {
--- /dev/null
+/*
+ * Copyright 2016 Facebook, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+#include <folly/experimental/hazptr/test/HazptrUse1.h>
+#include <folly/experimental/hazptr/test/HazptrUse2.h>
+#include <folly/experimental/hazptr/example/LockFreeLIFO.h>
+#include <folly/experimental/hazptr/example/SWMRList.h>
+#include <folly/experimental/hazptr/example/WideCAS.h>
+#include <folly/experimental/hazptr/debug.h>
+#include <folly/experimental/hazptr/hazptr.h>
+
+#include <gflags/gflags.h>
+#include <folly/portability/GTest.h>
+
+#include <thread>
+
+using namespace folly::hazptr;
+
+static hazptr_obj_reclaim<Node1> myReclaim_ = [](Node1* p) {
+ myReclaimFn(p);
+};
+
+static hazptr_obj_reclaim<Node2> mineReclaim_ = [](Node2* p) {
+ mineReclaimFn(p);
+};
+
+TEST(Hazptr, Test1) {
+ DEBUG_PRINT("========== start of scope");
+ DEBUG_PRINT("");
+ Node1* node0 = new Node1;
+ DEBUG_PRINT("=== new node0 " << node0 << " " << sizeof(*node0));
+ Node1* node1 = (Node1*)malloc(sizeof(Node1));
+ DEBUG_PRINT("=== malloc node1 " << node1 << " " << sizeof(*node1));
+ Node1* node2 = (Node1*)malloc(sizeof(Node1));
+ DEBUG_PRINT("=== malloc node2 " << node2 << " " << sizeof(*node2));
+ Node1* node3 = (Node1*)malloc(sizeof(Node1));
+ DEBUG_PRINT("=== malloc node3 " << node3 << " " << sizeof(*node3));
+
+ DEBUG_PRINT("");
+
+ std::atomic<Node1*> shared0 = {node0};
+ std::atomic<Node1*> shared1 = {node1};
+ std::atomic<Node1*> shared2 = {node2};
+ std::atomic<Node1*> shared3 = {node3};
+
+ MyMemoryResource myMr;
+ DEBUG_PRINT("=== myMr " << &myMr);
+ hazptr_domain myDomain0;
+ DEBUG_PRINT("=== myDomain0 " << &myDomain0);
+ hazptr_domain myDomain1(&myMr);
+ DEBUG_PRINT("=== myDomain1 " << &myDomain1);
+
+ DEBUG_PRINT("");
+
+ DEBUG_PRINT("=== hptr0");
+ hazptr_owner<Node1> hptr0;
+ DEBUG_PRINT("=== hptr1");
+ hazptr_owner<Node1> hptr1(&myDomain0);
+ DEBUG_PRINT("=== hptr2");
+ hazptr_owner<Node1> hptr2(&myDomain1);
+ DEBUG_PRINT("=== hptr3");
+ hazptr_owner<Node1> hptr3;
+
+ DEBUG_PRINT("");
+
+ Node1* n0 = shared0.load();
+ Node1* n1 = shared1.load();
+ Node1* n2 = shared2.load();
+ Node1* n3 = shared3.load();
+
+ if (hptr0.protect(n0, shared0)) {}
+ if (hptr1.protect(n1, shared1)) {}
+ hptr1.clear();
+ hptr1.set(n2);
+ if (hptr2.protect(n3, shared3)) {}
+ swap(hptr1, hptr2);
+ hptr3.clear();
+
+ DEBUG_PRINT("");
+
+ DEBUG_PRINT("=== retire n0 " << n0);
+ n0->retire();
+ DEBUG_PRINT("=== retire n1 " << n1);
+
+ n1->retire(default_hazptr_domain(), &myReclaim_);
+ DEBUG_PRINT("=== retire n2 " << n2);
+ n2->retire(&myDomain0, &myReclaim_);
+ DEBUG_PRINT("=== retire n3 " << n3);
+ n3->retire(&myDomain1, &myReclaim_);
+
+ DEBUG_PRINT("========== end of scope");
+}
+
+TEST(Hazptr, Test2) {
+ DEBUG_PRINT("========== start of scope");
+ Node2* node0 = new Node2;
+ DEBUG_PRINT("=== new node0 " << node0 << " " << sizeof(*node0));
+ Node2* node1 = (Node2*)malloc(sizeof(Node2));
+ DEBUG_PRINT("=== malloc node1 " << node1 << " " << sizeof(*node1));
+ Node2* node2 = (Node2*)malloc(sizeof(Node2));
+ DEBUG_PRINT("=== malloc node2 " << node2 << " " << sizeof(*node2));
+ Node2* node3 = (Node2*)malloc(sizeof(Node2));
+ DEBUG_PRINT("=== malloc node3 " << node3 << " " << sizeof(*node3));
+
+ DEBUG_PRINT("");
+
+ std::atomic<Node2*> shared0 = {node0};
+ std::atomic<Node2*> shared1 = {node1};
+ std::atomic<Node2*> shared2 = {node2};
+ std::atomic<Node2*> shared3 = {node3};
+
+ MineMemoryResource mineMr;
+ DEBUG_PRINT("=== mineMr " << &mineMr);
+ hazptr_domain mineDomain0;
+ DEBUG_PRINT("=== mineDomain0 " << &mineDomain0);
+ hazptr_domain mineDomain1(&mineMr);
+ DEBUG_PRINT("=== mineDomain1 " << &mineDomain1);
+
+ DEBUG_PRINT("");
+
+ DEBUG_PRINT("=== hptr0");
+ hazptr_owner<Node2> hptr0;
+ DEBUG_PRINT("=== hptr1");
+ hazptr_owner<Node2> hptr1(&mineDomain0);
+ DEBUG_PRINT("=== hptr2");
+ hazptr_owner<Node2> hptr2(&mineDomain1);
+ DEBUG_PRINT("=== hptr3");
+ hazptr_owner<Node2> hptr3;
+
+ DEBUG_PRINT("");
+
+ Node2* n0 = shared0.load();
+ Node2* n1 = shared1.load();
+ Node2* n2 = shared2.load();
+ Node2* n3 = shared3.load();
+
+ if (hptr0.protect(n0, shared0)) {}
+ if (hptr1.protect(n1, shared1)) {}
+ hptr1.clear();
+ hptr1.set(n2);
+ if (hptr2.protect(n3, shared3)) {}
+ swap(hptr1, hptr2);
+ hptr3.clear();
+
+ DEBUG_PRINT("");
+
+ DEBUG_PRINT("=== retire n0 " << n0);
+ n0->retire();
+ DEBUG_PRINT("=== retire n1 " << n1);
+
+ n1->retire(default_hazptr_domain(), &mineReclaim_);
+ DEBUG_PRINT("=== retire n2 " << n2);
+ n2->retire(&mineDomain0, &mineReclaim_);
+ DEBUG_PRINT("=== retire n3 " << n3);
+ n3->retire(&mineDomain1, &mineReclaim_);
+
+ DEBUG_PRINT("========== end of scope");
+}
+
+DEFINE_int32(num_threads, 1, "Number of threads");
+DEFINE_int64(num_reps, 1, "Number of test reps");
+DEFINE_int64(num_ops, 10, "Number of ops or pairs of ops per rep");
+
+TEST(Hazptr, LIFO) {
+ using T = uint32_t;
+ DEBUG_PRINT("========== start of test scope");
+ CHECK_GT(FLAGS_num_threads, 0);
+ for (int i = 0; i < FLAGS_num_reps; ++i) {
+ DEBUG_PRINT("========== start of rep scope");
+ LockFreeLIFO<T> s;
+ std::vector<std::thread> threads(FLAGS_num_threads);
+ for (int tid = 0; tid < FLAGS_num_threads; ++tid) {
+ threads[tid] = std::thread([&s, tid]() {
+ for (int j = tid; j < FLAGS_num_ops; j += FLAGS_num_threads) {
+ s.push(j);
+ T res;
+ while (!s.pop(res)) {}
+ }
+ });
+ }
+ for (auto& t : threads) {
+ t.join();
+ }
+ DEBUG_PRINT("========== end of rep scope");
+ }
+ DEBUG_PRINT("========== end of test scope");
+}
+
+TEST(Hazptr, SWMRLIST) {
+ using T = uint64_t;
+ DEBUG_PRINT("========== start of test scope");
+ hazptr_domain custom_domain;
+
+ CHECK_GT(FLAGS_num_threads, 0);
+ for (int i = 0; i < FLAGS_num_reps; ++i) {
+ DEBUG_PRINT("========== start of rep scope");
+ SWMRListSet<T> s(&custom_domain);
+ std::vector<std::thread> threads(FLAGS_num_threads);
+ for (int tid = 0; tid < FLAGS_num_threads; ++tid) {
+ threads[tid] = std::thread([&s, tid]() {
+ for (int j = tid; j < FLAGS_num_ops; j += FLAGS_num_threads) {
+ s.contains(j);
+ }
+ });
+ }
+ for (int j = 0; j < 10; ++j) {
+ s.add(j);
+ }
+ for (int j = 0; j < 10; ++j) {
+ s.remove(j);
+ }
+ for (auto& t : threads) {
+ t.join();
+ }
+ DEBUG_PRINT("========== end of rep scope");
+ }
+ DEBUG_PRINT("========== end of test scope");
+}
+
+TEST(Hazptr, WIDECAS) {
+ DEBUG_PRINT("========== start of test scope");
+
+ WideCAS s;
+ std::string u = "";
+ std::string v = "11112222";
+ auto ret = s.cas(u, v);
+ CHECK(ret);
+ u = "";
+ v = "11112222";
+ ret = s.cas(u, v);
+ CHECK(!ret);
+ u = "11112222";
+ v = "22223333";
+ ret = s.cas(u, v);
+ CHECK(ret);
+ u = "22223333";
+ v = "333344445555";
+ ret = s.cas(u, v);
+ CHECK(ret);
+
+ DEBUG_PRINT("========== end of test scope");
+}
+
+int main(int argc, char** argv) {
+ DEBUG_PRINT("=================================================== start main");
+ testing::InitGoogleTest(&argc, argv);
+ google::ParseCommandLineFlags(&argc, &argv, true);
+ auto ret = RUN_ALL_TESTS();
+ default_hazptr_domain()->flush();
+ DEBUG_PRINT("===================================================== end main");
+ return ret;
+}
--- /dev/null
+/*
+ * Copyright 2016 Facebook, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+#pragma once
+
+#include <folly/experimental/hazptr/debug.h>
+#include <folly/experimental/hazptr/hazptr.h>
+
+namespace folly {
+namespace hazptr {
+
+class MyMemoryResource : public memory_resource {
+ public:
+ void* allocate(const size_t sz, const size_t /* align */) {
+ void* p = malloc(sz);
+ DEBUG_PRINT(p << " " << sz);
+ return p;
+ }
+
+ void deallocate(void* p, const size_t sz, const size_t /* align */) {
+ DEBUG_PRINT(p << " " << sz);
+ free(p);
+ }
+};
+
+class Node1 : public hazptr_obj_base<Node1> {
+ char a[100];
+};
+
+inline void myReclaimFn(Node1* p) {
+ DEBUG_PRINT(p << " " << sizeof(Node1));
+ free(p);
+}
+
+} // namespace folly {
+} // namespace hazptr {
--- /dev/null
+/*
+ * Copyright 2016 Facebook, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+#pragma once
+
+#include <folly/experimental/hazptr/debug.h>
+#include <folly/experimental/hazptr/hazptr.h>
+
+namespace folly {
+namespace hazptr {
+
+class MineMemoryResource : public memory_resource {
+ public:
+ void* allocate(const size_t sz, const size_t /* align */) {
+ void* p = malloc(sz);
+ DEBUG_PRINT(p << " " << sz);
+ return p;
+ }
+
+ void deallocate(void* p, const size_t sz, const size_t /* align */) {
+ DEBUG_PRINT(p << " " << sz);
+ free(p);
+ }
+};
+
+class Node2 : public hazptr_obj_base<Node2> {
+ char a[200];
+};
+
+inline void mineReclaimFn(Node2* p) {
+ DEBUG_PRINT(p << " " << sizeof(Node2));
+ free(p);
+}
+
+} // namespace folly {
+} // namespace hazptr {
projects / folly.git / commitdiff