folly/experimental/hazptr/hazptr.h

   1 /*
   2  * Copyright 2016 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 #include <functional>
  21 #include <memory>
  22
  23 /* Stand-in for std::pmr::memory_resource */
  24 #include <folly/experimental/hazptr/memory_resource.h>
  25
  26 namespace folly {
  27 namespace hazptr {
  28
  29 /** hazptr_rec: Private class that contains hazard pointers. */
  30 class hazptr_rec;
  31
  32 /** hazptr_obj_base: Base template for objects protected by hazard pointers. */
  33 template <typename T> class hazptr_obj_base;
  34
  35 /** Alias for object reclamation function template */
  36 template <typename T> using hazptr_obj_reclaim = std::function<void(T*)>;
  37
  38 /** hazptr_domain: Class of hazard pointer domains. Each domain manages a set
  39  *  of hazard pointers and a set of retired objects. */
  40 class hazptr_domain {
  41  public:
  42   constexpr explicit hazptr_domain(
  43       memory_resource* = get_default_resource()) noexcept;
  44   ~hazptr_domain();
  45
  46   hazptr_domain(const hazptr_domain&) = delete;
  47   hazptr_domain(hazptr_domain&&) = delete;
  48   hazptr_domain& operator=(const hazptr_domain&) = delete;
  49   hazptr_domain& operator=(hazptr_domain&&) = delete;
  50
  51   /* Reclaim all retired objects with a specific reclamation
  52    * function currently stored by this domain */
  53   template <typename T> void flush(const hazptr_obj_reclaim<T>* reclaim);
  54   /* Reclaim all retired objects currently stored by this domain  */
  55   void flush();
  56
  57  private:
  58   template <typename> friend class hazptr_obj_base;
  59   template <typename> friend class hazptr_owner;
  60
  61   using hazptr_obj = hazptr_obj_base<void>;
  62
  63   /** Constant -- May be changed to parameter in the future */
  64   enum { kScanThreshold = 3 };
  65
  66   memory_resource* mr_;
  67   std::atomic<hazptr_rec*> hazptrs_ = {nullptr};
  68   std::atomic<hazptr_obj*> retired_ = {nullptr};
  69   std::atomic<int> hcount_ = {0};
  70   std::atomic<int> rcount_ = {0};
  71
  72   template <typename T> void objRetire(hazptr_obj_base<T>*);
  73   hazptr_rec* hazptrAcquire();
  74   void hazptrRelease(hazptr_rec*) const noexcept;
  75   void objRetire(hazptr_obj*);
  76   int pushRetired(hazptr_obj* head, hazptr_obj* tail, int count);
  77   void bulkReclaim();
  78   void flush(const hazptr_obj_reclaim<void>* reclaim);
  79 };
  80
  81 /** Get the default hazptr_domain */
  82 hazptr_domain* default_hazptr_domain();
  83
  84 /** Declaration of default reclamation function template */
  85 template <typename T> hazptr_obj_reclaim<T>* default_hazptr_obj_reclaim();
  86
  87 /** Definition of hazptr_obj_base */
  88 template <typename T> class hazptr_obj_base {
  89  public:
  90   /* Policy for storing retired objects */
  91   enum class storage_policy { priv, shared };
  92
  93   /* Retire a removed object and pass the responsibility for
  94    * reclaiming it to the hazptr library */
  95   void retire(
  96       hazptr_domain* domain = default_hazptr_domain(),
  97       const hazptr_obj_reclaim<T>* reclaim = default_hazptr_obj_reclaim<T>(),
  98       const storage_policy policy = storage_policy::shared);
  99
 100  private:
 101   friend class hazptr_domain;
 102   template <typename> friend class hazptr_owner;
 103
 104   const hazptr_obj_reclaim<T>* reclaim_;
 105   hazptr_obj_base* next_;
 106 };
 107
 108 /** hazptr_owner: Template for automatic acquisition and release of
 109  *  hazard pointers, and interface for hazard pointer operations. */
 110 template <typename T> class hazptr_owner;
 111
 112 /* Swap ownership of hazard ponters between hazptr_owner-s. */
 113 /* Note: The owned hazard pointers remain unmodified during the swap
 114  * and continue to protect the respective objects that they were
 115  * protecting before the swap, if any. */
 116 template <typename T>
 117 void swap(hazptr_owner<T>&, hazptr_owner<T>&) noexcept;
 118
 119 template <typename T> class hazptr_owner {
 120  public:
 121   /* Policy for caching hazard pointers */
 122   enum class cache_policy { cache, nocache };
 123
 124   /* Constructor automatically acquires a hazard pointer. */
 125   explicit hazptr_owner(
 126       hazptr_domain* domain = default_hazptr_domain(),
 127       const cache_policy policy = cache_policy::nocache);
 128
 129   /* Destructor automatically clears and releases the owned hazard pointer. */
 130   ~hazptr_owner() noexcept;
 131
 132   /* Copy and move constructors and assignment operators are
 133    * disallowed because:
 134    * - Each hazptr_owner owns exactly one hazard pointer at any time.
 135    * - Each hazard pointer may have up to one owner at any time. */
 136   hazptr_owner(const hazptr_owner&) = delete;
 137   hazptr_owner(hazptr_owner&&) = delete;
 138   hazptr_owner& operator=(const hazptr_owner&) = delete;
 139   hazptr_owner& operator=(hazptr_owner&&) = delete;
 140
 141   /** Hazard pointer operations */
 142   /* Return true if successful in protecting the object */
 143   bool protect(const T* ptr, const std::atomic<T*>& src) const noexcept;
 144   /* Set the hazard pointer to ptr */
 145   void set(const T* ptr) const noexcept;
 146   /* Clear the hazard pointer */
 147   void clear() const noexcept;
 148
 149  private:
 150   friend void swap<T>(hazptr_owner&, hazptr_owner&) noexcept;
 151
 152   hazptr_domain* domain_;
 153   hazptr_rec* hazptr_;
 154 };
 155
 156 /** hazptr_user: Thread-specific interface for users of hazard
 157  *  pointers (i.e., threads that own hazard pointers by using
 158  *  hazptr_owner. */
 159 class hazptr_user {
 160  public:
 161   /* Release all hazptr_rec-s cached by this thread */
 162   static void flush();
 163 };
 164
 165 /** hazptr_remover: Thread-specific interface for removers of objects
 166  *  protected by hazard pointersd, i.e., threads that call the retire
 167  *  member function of hazptr_obj_base. */
 168 class hazptr_remover {
 169  public:
 170   /* Pass responsibility of reclaiming any retired objects stored
 171    * privately by this thread to the hazptr_domain to which they
 172    * belong. */
 173   static void flush();
 174 };
 175
 176 } // namespace hazptr
 177 } // namespace folly
 178
 179 ////////////////////////////////////////////////////////////////////////////////
 180 /// Notes
 181 ////////////////////////////////////////////////////////////////////////////////
 182
 183 /* The hazptr_obj_base template uses a reclamation function as a
 184  * parameter for the retire() member function instead of taking an
 185  * allocator template as an extra template parameter because objects
 186  * of the same type may need different reclamation functions. */
 187
 188 /* The hazptr interface supports reclamation by one domain at a
 189  * time. If an abject belongs to multiple domains simultaneously, a
 190  * workaround may be to design reclamation functions to form a series
 191  * of retirements from one domain to the next until it reaches the
 192  * final domain in the series that finally reclaims the object. */
 193
 194 ////////////////////////////////////////////////////////////////////////////////
 195
 196 #include "hazptr-impl.h"