folly/experimental/hazptr/hazptr.h

   1 /*
   2  * Copyright 2016-present 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_obj_base_refcounted:
  38  *  Base template for reference counted objects protected by hazard pointers.
  39  */
  40 template <typename T, typename Deleter>
  41 class hazptr_obj_base_refcounted;
  42
  43 /** hazptr_local: Optimized template for bulk construction and destruction of
  44  *  hazard pointers */
  45 template <size_t M>
  46 class hazptr_array;
  47
  48 /** hazptr_local: Optimized template for locally-used hazard pointers */
  49 template <size_t M>
  50 class hazptr_local;
  51
  52 /** hazptr_domain: Class of hazard pointer domains. Each domain manages a set
  53  *  of hazard pointers and a set of retired objects. */
  54 class hazptr_domain {
  55  public:
  56   constexpr explicit hazptr_domain(
  57       memory_resource* = get_default_resource()) noexcept;
  58   ~hazptr_domain();
  59
  60   hazptr_domain(const hazptr_domain&) = delete;
  61   hazptr_domain(hazptr_domain&&) = delete;
  62   hazptr_domain& operator=(const hazptr_domain&) = delete;
  63   hazptr_domain& operator=(hazptr_domain&&) = delete;
  64
  65   /** Free-function retire.  May allocate memory */
  66   template <typename T, typename D = std::default_delete<T>>
  67   void retire(T* obj, D reclaim = {});
  68
  69  private:
  70   friend class hazptr_obj_batch;
  71   friend class hazptr_holder;
  72   template <typename, typename>
  73   friend class hazptr_obj_base;
  74   template <typename, typename>
  75   friend class hazptr_obj_base_refcounted;
  76   friend struct hazptr_priv;
  77
  78   memory_resource* mr_;
  79   std::atomic<hazptr_rec*> hazptrs_ = {nullptr};
  80   std::atomic<hazptr_obj*> retired_ = {nullptr};
  81   std::atomic<int> hcount_ = {0};
  82   std::atomic<int> rcount_ = {0};
  83   /* Using signed int for rcount_ because it may transiently be
  84    * negative.  Using signed int for all integer variables that may be
  85    * involved in calculations related to the value of rcount_. */
  86
  87   void objRetire(hazptr_obj*);
  88   hazptr_rec* hazptrAcquire();
  89   void hazptrRelease(hazptr_rec*) noexcept;
  90   int pushRetired(hazptr_obj* head, hazptr_obj* tail, int count);
  91   bool reachedThreshold(int rcount);
  92   void tryBulkReclaim();
  93   void bulkReclaim();
  94 };
  95
  96 /** Get the default hazptr_domain */
  97 hazptr_domain& default_hazptr_domain();
  98
  99 extern hazptr_domain default_domain_;
 100
 101 /** Free-function retire, that operates on the default domain */
 102 template <typename T, typename D = std::default_delete<T>>
 103 void hazptr_retire(T* obj, D reclaim = {});
 104
 105 /** Definition of hazptr_obj */
 106 class hazptr_obj {
 107   friend class hazptr_obj_batch;
 108   friend class hazptr_domain;
 109   template <typename, typename>
 110   friend class hazptr_obj_base;
 111   template <typename, typename>
 112   friend class hazptr_obj_base_refcounted;
 113   friend struct hazptr_priv;
 114
 115   void (*reclaim_)(hazptr_obj*);
 116   hazptr_obj* next_{nullptr}; // nullptr for debugging
 117
 118   const void* getObjPtr() const;
 119 };
 120
 121 /** Definition of hazptr_obj_base */
 122 template <typename T, typename D = std::default_delete<T>>
 123 class hazptr_obj_base : public hazptr_obj {
 124  public:
 125   /* Retire a removed object and pass the responsibility for
 126    * reclaiming it to the hazptr library */
 127   void retire(hazptr_domain& domain = default_hazptr_domain(), D reclaim = {});
 128
 129  private:
 130   D deleter_;
 131 };
 132
 133 /** Definition of hazptr_recounted_obj_base */
 134 template <typename T, typename D = std::default_delete<T>>
 135 class hazptr_obj_base_refcounted : public hazptr_obj {
 136   friend class hazptr_obj_batch;
 137
 138  public:
 139   /* Retire a removed object and pass the responsibility for
 140    * reclaiming it to the hazptr library */
 141   void retire(hazptr_domain& domain = default_hazptr_domain(), D reclaim = {});
 142
 143   /* aquire_ref() increments the reference count
 144    *
 145    * acquire_ref_safe() is the same as acquire_ref() except that in
 146    * addition the caller guarantees that the call is made in a
 147    * thread-safe context, e.g., the object is not yet shared. This is
 148    * just an optimization to save an atomic operation.
 149    *
 150    * release_ref() decrements the reference count and returns true if
 151    * the object is safe to reclaim.
 152    */
 153   void acquire_ref();
 154   void acquire_ref_safe();
 155   bool release_ref();
 156
 157  private:
 158   void preRetire(D deleter);
 159
 160   std::atomic<uint32_t> refcount_{0};
 161   D deleter_;
 162 };
 163
 164 /** hazptr_holder: Class for automatic acquisition and release of
 165  *  hazard pointers, and interface for hazard pointer operations. */
 166 class hazptr_holder {
 167   template <size_t M>
 168   friend class hazptr_array;
 169   template <size_t M>
 170   friend class hazptr_local;
 171
 172  public:
 173   /* Constructor automatically acquires a hazard pointer. */
 174   explicit hazptr_holder(hazptr_domain& domain = default_hazptr_domain());
 175   /* Construct an empty hazptr_holder. */
 176   // Note: This diverges from the proposal in P0233R4
 177   explicit hazptr_holder(std::nullptr_t) noexcept;
 178
 179   /* Destructor automatically clears and releases the owned hazard pointer. */
 180   ~hazptr_holder();
 181
 182   hazptr_holder(const hazptr_holder&) = delete;
 183   hazptr_holder& operator=(const hazptr_holder&) = delete;
 184   // Note: This diverges from the proposal in P0233R4 which disallows
 185   // move constructor and assignment operator.
 186   hazptr_holder(hazptr_holder&&) noexcept;
 187   hazptr_holder& operator=(hazptr_holder&&) noexcept;
 188
 189   /** Hazard pointer operations */
 190   /* Returns a protected pointer from the source */
 191   template <typename T>
 192   T* get_protected(const std::atomic<T*>& src) noexcept;
 193   /* Returns a protected pointer from the source, filtering
 194      the protected pointer through function Func.  Useful for
 195      stealing bits of the pointer word */
 196   template <typename T, typename Func>
 197   T* get_protected(const std::atomic<T*>& src, Func f) noexcept;
 198   /* Return true if successful in protecting ptr if src == ptr after
 199    * setting the hazard pointer.  Otherwise sets ptr to src. */
 200   template <typename T>
 201   bool try_protect(T*& ptr, const std::atomic<T*>& src) noexcept;
 202   /* Return true if successful in protecting ptr if src == ptr after
 203    * setting the hazard pointer, filtering the pointer through Func.
 204    * Otherwise sets ptr to src. */
 205   template <typename T, typename Func>
 206   bool try_protect(T*& ptr, const std::atomic<T*>& src, Func f) noexcept;
 207   /* Set the hazard pointer to ptr */
 208   template <typename T>
 209   void reset(const T* ptr) noexcept;
 210   /* Set the hazard pointer to nullptr */
 211   void reset(std::nullptr_t = nullptr) noexcept;
 212
 213   /* Swap ownership of hazard pointers between hazptr_holder-s. */
 214   /* Note: The owned hazard pointers remain unmodified during the swap
 215    * and continue to protect the respective objects that they were
 216    * protecting before the swap, if any. */
 217   void swap(hazptr_holder&) noexcept;
 218
 219  private:
 220   hazptr_domain* domain_;
 221   hazptr_rec* hazptr_;
 222 };
 223
 224 void swap(hazptr_holder&, hazptr_holder&) noexcept;
 225
 226 using aligned_hazptr_holder = typename std::
 227     aligned_storage<sizeof(hazptr_holder), alignof(hazptr_holder)>::type;
 228
 229 /**
 230  *  hazptr_array: Optimized for bulk construction and destruction of
 231  *  hazptr_holder-s.
 232  *
 233  *  WARNING: Do not move from or to individual hazptr_holder-s.
 234  *  Only move the whole hazptr_array.
 235  */
 236 template <size_t M = 1>
 237 class hazptr_array {
 238   static_assert(M > 0, "M must be a positive integer.");
 239
 240  public:
 241   hazptr_array();
 242   explicit hazptr_array(std::nullptr_t) noexcept;
 243
 244   hazptr_array(const hazptr_array&) = delete;
 245   hazptr_array& operator=(const hazptr_array&) = delete;
 246   hazptr_array(hazptr_array&& other) noexcept;
 247   hazptr_array& operator=(hazptr_array&& other) noexcept;
 248
 249   ~hazptr_array();
 250
 251   hazptr_holder& operator[](size_t i) noexcept;
 252
 253  private:
 254   aligned_hazptr_holder raw_[M];
 255   bool empty_{false};
 256 };
 257
 258 /**
 259  *  hazptr_local: Optimized for construction and destruction of
 260  *  one or more hazptr_holder-s with local scope.
 261  *
 262  *  WARNING 1: Do not move from or to individual hazptr_holder-s.
 263  *
 264  *  WARNING 2: There can only be one hazptr_local active for the same
 265  *  thread at any time. This is not tracked and checked by the
 266  *  implementation because it would negate the performance gains of
 267  *  this class.
 268  */
 269 template <size_t M = 1>
 270 class hazptr_local {
 271   static_assert(M > 0, "M must be a positive integer.");
 272
 273  public:
 274   hazptr_local();
 275   hazptr_local(const hazptr_local&) = delete;
 276   hazptr_local& operator=(const hazptr_local&) = delete;
 277   hazptr_local(hazptr_local&&) = delete;
 278   hazptr_local& operator=(hazptr_local&&) = delete;
 279
 280   ~hazptr_local();
 281
 282   hazptr_holder& operator[](size_t i) noexcept;
 283
 284  private:
 285   aligned_hazptr_holder raw_[M];
 286   bool need_destruct_{false};
 287 };
 288
 289 } // namespace hazptr
 290 } // namespace folly
 291
 292 #include "hazptr-impl.h"