folly/experimental/hazptr/hazptr.h

   1 /*
   2  * Copyright 2017 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 #pragma once
  17 #define HAZPTR_H
  18
  19 #include <atomic>
  20
  21 /* Stand-in for C++17 std::pmr::memory_resource */
  22 #include <folly/experimental/hazptr/memory_resource.h>
  23
  24 namespace folly {
  25 namespace hazptr {
  26
  27 /** hazptr_rec: Private class that contains hazard pointers. */
  28 class hazptr_rec;
  29
  30 /** hazptr_obj: Private class for objects protected by hazard pointers. */
  31 class hazptr_obj;
  32
  33 /** hazptr_obj_base: Base template for objects protected by hazard pointers. */
  34 template <typename T, typename Deleter>
  35 class hazptr_obj_base;
  36
  37 /** hazptr_local: Optimized template for bulk construction and destruction of
  38  *  hazard pointers */
  39 template <size_t M>
  40 class hazptr_array;
  41
  42 /** hazptr_local: Optimized template for locally-used hazard pointers */
  43 template <size_t M>
  44 class hazptr_local;
  45
  46 /** hazptr_domain: Class of hazard pointer domains. Each domain manages a set
  47  *  of hazard pointers and a set of retired objects. */
  48 class hazptr_domain {
  49  public:
  50   constexpr explicit hazptr_domain(
  51       memory_resource* = get_default_resource()) noexcept;
  52   ~hazptr_domain();
  53
  54   hazptr_domain(const hazptr_domain&) = delete;
  55   hazptr_domain(hazptr_domain&&) = delete;
  56   hazptr_domain& operator=(const hazptr_domain&) = delete;
  57   hazptr_domain& operator=(hazptr_domain&&) = delete;
  58
  59  private:
  60   friend class hazptr_holder;
  61   template <typename, typename>
  62   friend class hazptr_obj_base;
  63   friend struct hazptr_priv;
  64
  65   memory_resource* mr_;
  66   std::atomic<hazptr_rec*> hazptrs_ = {nullptr};
  67   std::atomic<hazptr_obj*> retired_ = {nullptr};
  68   std::atomic<int> hcount_ = {0};
  69   std::atomic<int> rcount_ = {0};
  70
  71   void objRetire(hazptr_obj*);
  72   hazptr_rec* hazptrAcquire();
  73   void hazptrRelease(hazptr_rec*) noexcept;
  74   int pushRetired(hazptr_obj* head, hazptr_obj* tail, int count);
  75   bool reachedThreshold(int rcount);
  76   void tryBulkReclaim();
  77   void bulkReclaim();
  78 };
  79
  80 /** Get the default hazptr_domain */
  81 hazptr_domain& default_hazptr_domain();
  82
  83 extern hazptr_domain default_domain_;
  84
  85 /** Definition of hazptr_obj */
  86 class hazptr_obj {
  87   friend class hazptr_domain;
  88   template <typename, typename>
  89   friend class hazptr_obj_base;
  90   friend struct hazptr_priv;
  91
  92   void (*reclaim_)(hazptr_obj*);
  93   hazptr_obj* next_;
  94   const void* getObjPtr() const;
  95 };
  96
  97 /** Definition of hazptr_obj_base */
  98 template <typename T, typename D = std::default_delete<T>>
  99 class hazptr_obj_base : public hazptr_obj {
 100  public:
 101   /* Retire a removed object and pass the responsibility for
 102    * reclaiming it to the hazptr library */
 103   void retire(hazptr_domain& domain = default_hazptr_domain(), D reclaim = {});
 104
 105  private:
 106   D deleter_;
 107 };
 108
 109 /** hazptr_holder: Class for automatic acquisition and release of
 110  *  hazard pointers, and interface for hazard pointer operations. */
 111 class hazptr_holder {
 112   template <size_t M>
 113   friend class hazptr_array;
 114   template <size_t M>
 115   friend class hazptr_local;
 116
 117  public:
 118   /* Constructor automatically acquires a hazard pointer. */
 119   explicit hazptr_holder(hazptr_domain& domain = default_hazptr_domain());
 120   /* Construct an empty hazptr_holder. */
 121   // Note: This diverges from the proposal in P0233R4
 122   explicit hazptr_holder(std::nullptr_t) noexcept;
 123
 124   /* Destructor automatically clears and releases the owned hazard pointer. */
 125   ~hazptr_holder();
 126
 127   hazptr_holder(const hazptr_holder&) = delete;
 128   hazptr_holder& operator=(const hazptr_holder&) = delete;
 129   // Note: This diverges from the proposal in P0233R4 which disallows
 130   // move constructor and assignment operator.
 131   hazptr_holder(hazptr_holder&&) noexcept;
 132   hazptr_holder& operator=(hazptr_holder&&) noexcept;
 133
 134   /** Hazard pointer operations */
 135   /* Returns a protected pointer from the source */
 136   template <typename T>
 137   T* get_protected(const std::atomic<T*>& src) noexcept;
 138   /* Returns a protected pointer from the source, filtering
 139      the protected pointer through function Func.  Useful for
 140      stealing bits of the pointer word */
 141   template <typename T, typename Func>
 142   T* get_protected(const std::atomic<T*>& src, Func f) noexcept;
 143   /* Return true if successful in protecting ptr if src == ptr after
 144    * setting the hazard pointer.  Otherwise sets ptr to src. */
 145   template <typename T>
 146   bool try_protect(T*& ptr, const std::atomic<T*>& src) noexcept;
 147   /* Return true if successful in protecting ptr if src == ptr after
 148    * setting the hazard pointer, filtering the pointer through Func.
 149    * Otherwise sets ptr to src. */
 150   template <typename T, typename Func>
 151   bool try_protect(T*& ptr, const std::atomic<T*>& src, Func f) noexcept;
 152   /* Set the hazard pointer to ptr */
 153   template <typename T>
 154   void reset(const T* ptr) noexcept;
 155   /* Set the hazard pointer to nullptr */
 156   void reset(std::nullptr_t = nullptr) noexcept;
 157
 158   /* Swap ownership of hazard pointers between hazptr_holder-s. */
 159   /* Note: The owned hazard pointers remain unmodified during the swap
 160    * and continue to protect the respective objects that they were
 161    * protecting before the swap, if any. */
 162   void swap(hazptr_holder&) noexcept;
 163
 164  private:
 165   hazptr_domain* domain_;
 166   hazptr_rec* hazptr_;
 167 };
 168
 169 void swap(hazptr_holder&, hazptr_holder&) noexcept;
 170
 171 using aligned_hazptr_holder = typename std::
 172     aligned_storage<sizeof(hazptr_holder), alignof(hazptr_holder)>::type;
 173
 174 /**
 175  *  hazptr_array: Optimized for bulk construction and destruction of
 176  *  hazptr_holder-s.
 177  *
 178  *  WARNING: Do not move from or to individual hazptr_holder-s.
 179  *  Only move the whole hazptr_array.
 180  */
 181 template <size_t M = 1>
 182 class hazptr_array {
 183   static_assert(M > 0, "M must be a positive integer.");
 184
 185  public:
 186   hazptr_array();
 187   explicit hazptr_array(std::nullptr_t) noexcept;
 188
 189   hazptr_array(const hazptr_array&) = delete;
 190   hazptr_array& operator=(const hazptr_array&) = delete;
 191   hazptr_array(hazptr_array&& other) noexcept;
 192   hazptr_array& operator=(hazptr_array&& other) noexcept;
 193
 194   ~hazptr_array();
 195
 196   hazptr_holder& operator[](size_t i) noexcept;
 197
 198  private:
 199   aligned_hazptr_holder raw_[M];
 200   bool empty_{false};
 201 };
 202
 203 /**
 204  *  hazptr_local: Optimized for construction and destruction of
 205  *  one or more hazptr_holder-s with local scope.
 206  *
 207  *  WARNING 1: Do not move from or to individual hazptr_holder-s.
 208  *
 209  *  WARNING 2: There can only be one hazptr_local active for the same
 210  *  thread at any time. This is not tracked and checked by the
 211  *  implementation because it would negate the performance gains of
 212  *  this class.
 213  */
 214 template <size_t M = 1>
 215 class hazptr_local {
 216   static_assert(M > 0, "M must be a positive integer.");
 217
 218  public:
 219   hazptr_local();
 220   hazptr_local(const hazptr_local&) = delete;
 221   hazptr_local& operator=(const hazptr_local&) = delete;
 222   hazptr_local(hazptr_local&&) = delete;
 223   hazptr_local& operator=(hazptr_local&&) = delete;
 224
 225   ~hazptr_local();
 226
 227   hazptr_holder& operator[](size_t i) noexcept;
 228
 229  private:
 230   aligned_hazptr_holder raw_[M];
 231   bool need_destruct_{false};
 232 };
 233
 234 } // namespace hazptr
 235 } // namespace folly
 236
 237 #include "hazptr-impl.h"