/*
- * Copyright 2016 Facebook, Inc.
+ * Copyright 2016-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.
#define HAZPTR_H
#include <atomic>
-#include <functional>
-#include <memory>
-/* Stand-in for std::pmr::memory_resource */
+/* Stand-in for C++17 std::pmr::memory_resource */
#include <folly/experimental/hazptr/memory_resource.h>
namespace folly {
/** hazptr_rec: Private class that contains hazard pointers. */
class hazptr_rec;
+/** hazptr_obj: Private class for objects protected by hazard pointers. */
+class hazptr_obj;
+
/** hazptr_obj_base: Base template for objects protected by hazard pointers. */
-template <typename T> class hazptr_obj_base;
+template <typename T, typename Deleter>
+class hazptr_obj_base;
+
+/** hazptr_obj_base_refcounted:
+ * Base template for reference counted objects protected by hazard pointers.
+ */
+template <typename T, typename Deleter>
+class hazptr_obj_base_refcounted;
-/** Alias for object reclamation function template */
-template <typename T> using hazptr_obj_reclaim = std::function<void(T*)>;
+/** hazptr_local: Optimized template for bulk construction and destruction of
+ * hazard pointers */
+template <size_t M>
+class hazptr_array;
+
+/** hazptr_local: Optimized template for locally-used hazard pointers */
+template <size_t M>
+class hazptr_local;
/** hazptr_domain: Class of hazard pointer domains. Each domain manages a set
* of hazard pointers and a set of retired objects. */
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();
+ /** Free-function retire. May allocate memory */
+ template <typename T, typename D = std::default_delete<T>>
+ void retire(T* obj, D reclaim = {});
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 };
+ friend class hazptr_obj_batch;
+ friend class hazptr_holder;
+ template <typename, typename>
+ friend class hazptr_obj_base;
+ template <typename, typename>
+ friend class hazptr_obj_base_refcounted;
+ friend struct hazptr_priv;
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};
+ /* Using signed int for rcount_ because it may transiently be
+ * negative. Using signed int for all integer variables that may be
+ * involved in calculations related to the value of rcount_. */
- template <typename T> void objRetire(hazptr_obj_base<T>*);
- hazptr_rec* hazptrAcquire();
- void hazptrRelease(hazptr_rec*) const noexcept;
void objRetire(hazptr_obj*);
+ hazptr_rec* hazptrAcquire();
+ void hazptrRelease(hazptr_rec*) noexcept;
int pushRetired(hazptr_obj* head, hazptr_obj* tail, int count);
+ bool reachedThreshold(int rcount);
+ void tryBulkReclaim();
void bulkReclaim();
- void flush(const hazptr_obj_reclaim<void>* reclaim);
};
/** Get the default hazptr_domain */
-hazptr_domain* default_hazptr_domain();
+hazptr_domain& default_hazptr_domain();
+
+extern hazptr_domain default_domain_;
+
+/** Free-function retire, that operates on the default domain */
+template <typename T, typename D = std::default_delete<T>>
+void hazptr_retire(T* obj, D reclaim = {});
+
+/** Definition of hazptr_obj */
+class hazptr_obj {
+ friend class hazptr_obj_batch;
+ friend class hazptr_domain;
+ template <typename, typename>
+ friend class hazptr_obj_base;
+ template <typename, typename>
+ friend class hazptr_obj_base_refcounted;
+ friend struct hazptr_priv;
-/** Declaration of default reclamation function template */
-template <typename T> hazptr_obj_reclaim<T>* default_hazptr_obj_reclaim();
+ void (*reclaim_)(hazptr_obj*);
+ hazptr_obj* next_{nullptr}; // nullptr for debugging
+
+ const void* getObjPtr() const;
+};
/** Definition of hazptr_obj_base */
-template <typename T> class hazptr_obj_base {
+template <typename T, typename D = std::default_delete<T>>
+class hazptr_obj_base : public hazptr_obj {
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(), D reclaim = {});
+
+ private:
+ D deleter_;
+};
+
+/** Definition of hazptr_recounted_obj_base */
+template <typename T, typename D = std::default_delete<T>>
+class hazptr_obj_base_refcounted : public hazptr_obj {
+ friend class hazptr_obj_batch;
+ public:
/* 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);
+ void retire(hazptr_domain& domain = default_hazptr_domain(), D reclaim = {});
+
+ /* aquire_ref() increments the reference count
+ *
+ * acquire_ref_safe() is the same as acquire_ref() except that in
+ * addition the caller guarantees that the call is made in a
+ * thread-safe context, e.g., the object is not yet shared. This is
+ * just an optimization to save an atomic operation.
+ *
+ * release_ref() decrements the reference count and returns true if
+ * the object is safe to reclaim.
+ */
+ void acquire_ref();
+ void acquire_ref_safe();
+ bool release_ref();
private:
- friend class hazptr_domain;
- template <typename> friend class hazptr_owner;
+ void preRetire(D deleter);
- const hazptr_obj_reclaim<T>* reclaim_;
- hazptr_obj_base* next_;
+ std::atomic<uint32_t> refcount_{0};
+ D deleter_;
};
-/** hazptr_owner: Template for automatic acquisition and release of
+/** hazptr_holder: Class 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;
+class hazptr_holder {
+ template <size_t M>
+ friend class hazptr_array;
+ template <size_t M>
+ friend class hazptr_local;
-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);
+ explicit hazptr_holder(hazptr_domain& domain = default_hazptr_domain());
+ /* Construct an empty hazptr_holder. */
+ // Note: This diverges from the proposal in P0233R4
+ explicit hazptr_holder(std::nullptr_t) noexcept;
/* Destructor automatically clears and releases the owned hazard pointer. */
- ~hazptr_owner() noexcept;
+ ~hazptr_holder();
- /* 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;
+ hazptr_holder(const hazptr_holder&) = delete;
+ hazptr_holder& operator=(const hazptr_holder&) = delete;
+ // Note: This diverges from the proposal in P0233R4 which disallows
+ // move constructor and assignment operator.
+ hazptr_holder(hazptr_holder&&) noexcept;
+ hazptr_holder& operator=(hazptr_holder&&) noexcept;
/** Hazard pointer operations */
- /* Return true if successful in protecting the object */
- bool protect(const T* ptr, const std::atomic<T*>& src) const noexcept;
+ /* Returns a protected pointer from the source */
+ template <typename T>
+ T* get_protected(const std::atomic<T*>& src) noexcept;
+ /* Returns a protected pointer from the source, filtering
+ the protected pointer through function Func. Useful for
+ stealing bits of the pointer word */
+ template <typename T, typename Func>
+ T* get_protected(const std::atomic<T*>& src, Func f) noexcept;
+ /* Return true if successful in protecting ptr if src == ptr after
+ * setting the hazard pointer. Otherwise sets ptr to src. */
+ template <typename T>
+ bool try_protect(T*& ptr, const std::atomic<T*>& src) noexcept;
+ /* Return true if successful in protecting ptr if src == ptr after
+ * setting the hazard pointer, filtering the pointer through Func.
+ * Otherwise sets ptr to src. */
+ template <typename T, typename Func>
+ bool try_protect(T*& ptr, const std::atomic<T*>& src, Func f) noexcept;
/* Set the hazard pointer to ptr */
- void set(const T* ptr) const noexcept;
- /* Clear the hazard pointer */
- void clear() const noexcept;
+ template <typename T>
+ void reset(const T* ptr) noexcept;
+ /* Set the hazard pointer to nullptr */
+ void reset(std::nullptr_t = nullptr) noexcept;
- void swap(hazptr_owner&) noexcept;
+ /* Swap ownership of hazard pointers between hazptr_holder-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. */
+ void swap(hazptr_holder&) noexcept;
private:
-
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();
-};
+void swap(hazptr_holder&, hazptr_holder&) noexcept;
+
+using aligned_hazptr_holder = typename std::
+ aligned_storage<sizeof(hazptr_holder), alignof(hazptr_holder)>::type;
+
+/**
+ * hazptr_array: Optimized for bulk construction and destruction of
+ * hazptr_holder-s.
+ *
+ * WARNING: Do not move from or to individual hazptr_holder-s.
+ * Only move the whole hazptr_array.
+ */
+template <size_t M = 1>
+class hazptr_array {
+ static_assert(M > 0, "M must be a positive integer.");
-/** 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();
+ hazptr_array();
+ explicit hazptr_array(std::nullptr_t) noexcept;
+
+ hazptr_array(const hazptr_array&) = delete;
+ hazptr_array& operator=(const hazptr_array&) = delete;
+ hazptr_array(hazptr_array&& other) noexcept;
+ hazptr_array& operator=(hazptr_array&& other) noexcept;
+
+ ~hazptr_array();
+
+ hazptr_holder& operator[](size_t i) noexcept;
+
+ private:
+ aligned_hazptr_holder raw_[M];
+ bool empty_{false};
};
-} // namespace hazptr
-} // namespace folly
+/**
+ * hazptr_local: Optimized for construction and destruction of
+ * one or more hazptr_holder-s with local scope.
+ *
+ * WARNING 1: Do not move from or to individual hazptr_holder-s.
+ *
+ * WARNING 2: There can only be one hazptr_local active for the same
+ * thread at any time. This is not tracked and checked by the
+ * implementation because it would negate the performance gains of
+ * this class.
+ */
+template <size_t M = 1>
+class hazptr_local {
+ static_assert(M > 0, "M must be a positive integer.");
-////////////////////////////////////////////////////////////////////////////////
-/// Notes
-////////////////////////////////////////////////////////////////////////////////
+ public:
+ hazptr_local();
+ hazptr_local(const hazptr_local&) = delete;
+ hazptr_local& operator=(const hazptr_local&) = delete;
+ hazptr_local(hazptr_local&&) = delete;
+ hazptr_local& operator=(hazptr_local&&) = delete;
-/* 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. */
+ ~hazptr_local();
-/* 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. */
+ hazptr_holder& operator[](size_t i) noexcept;
-////////////////////////////////////////////////////////////////////////////////
+ private:
+ aligned_hazptr_holder raw_[M];
+ bool need_destruct_{false};
+};
+
+} // namespace hazptr
+} // namespace folly
#include "hazptr-impl.h"