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 C++17 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: Private class for objects protected by hazard pointers. */
  33 class hazptr_obj;
  34
  35 /** hazptr_obj_base: Base template for objects protected by hazard pointers. */
  36 template <typename T, typename Deleter>
  37 class hazptr_obj_base;
  38
  39 /** hazptr_domain: Class of hazard pointer domains. Each domain manages a set
  40  *  of hazard pointers and a set of retired objects. */
  41 class hazptr_domain {
  42  public:
  43   constexpr explicit hazptr_domain(
  44       memory_resource* = get_default_resource()) noexcept;
  45   ~hazptr_domain();
  46
  47   hazptr_domain(const hazptr_domain&) = delete;
  48   hazptr_domain(hazptr_domain&&) = delete;
  49   hazptr_domain& operator=(const hazptr_domain&) = delete;
  50   hazptr_domain& operator=(hazptr_domain&&) = delete;
  51
  52  private:
  53   template <typename, typename>
  54   friend class hazptr_obj_base;
  55   template <typename> friend class hazptr_owner;
  56
  57   /** Constant -- May be changed to parameter in the future */
  58   enum { kScanThreshold = 3 };
  59
  60   memory_resource* mr_;
  61   std::atomic<hazptr_rec*> hazptrs_ = {nullptr};
  62   std::atomic<hazptr_obj*> retired_ = {nullptr};
  63   std::atomic<int> hcount_ = {0};
  64   std::atomic<int> rcount_ = {0};
  65
  66   void objRetire(hazptr_obj*);
  67   hazptr_rec* hazptrAcquire();
  68   void hazptrRelease(hazptr_rec*) noexcept;
  69   int pushRetired(hazptr_obj* head, hazptr_obj* tail, int count);
  70   void tryBulkReclaim();
  71   void bulkReclaim();
  72   void try_reclaim();
  73 };
  74
  75 /** Get the default hazptr_domain */
  76 hazptr_domain& default_hazptr_domain();
  77
  78 /** Definition of hazptr_obj */
  79 class hazptr_obj {
  80   friend class hazptr_domain;
  81   template <typename, typename>
  82   friend class hazptr_obj_base;
  83
  84   void (*reclaim_)(hazptr_obj*);
  85   hazptr_obj* next_;
  86   const void* getObjPtr() const;
  87 };
  88
  89 /** Definition of hazptr_obj_base */
  90 template <typename T, typename Deleter = std::default_delete<T>>
  91 class hazptr_obj_base : private hazptr_obj {
  92  public:
  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       Deleter reclaim = {});
  98
  99  private:
 100   Deleter deleter_;
 101 };
 102
 103 /** hazptr_owner: Template for automatic acquisition and release of
 104  *  hazard pointers, and interface for hazard pointer operations. */
 105 template <typename T> class hazptr_owner {
 106  public:
 107   /* Constructor automatically acquires a hazard pointer. */
 108   explicit hazptr_owner(hazptr_domain& domain = default_hazptr_domain());
 109   /* Destructor automatically clears and releases the owned hazard pointer. */
 110   ~hazptr_owner();
 111
 112   /* Copy and move constructors and assignment operators are
 113    * disallowed because:
 114    * - Each hazptr_owner owns exactly one hazard pointer at any time.
 115    * - Each hazard pointer may have up to one owner at any time. */
 116   hazptr_owner(const hazptr_owner&) = delete;
 117   hazptr_owner(hazptr_owner&&) = delete;
 118   hazptr_owner& operator=(const hazptr_owner&) = delete;
 119   hazptr_owner& operator=(hazptr_owner&&) = delete;
 120
 121   /** Hazard pointer operations */
 122   /* Returns a protected pointer from the source */
 123   T* get_protected(const std::atomic<T*>& src) noexcept;
 124   /* Return true if successful in protecting ptr if src == ptr after
 125    * setting the hazard pointer.  Otherwise sets ptr to src. */
 126   bool try_protect(T*& ptr, const std::atomic<T*>& src) noexcept;
 127   /* Set the hazard pointer to ptr */
 128   void set(const T* ptr) noexcept;
 129   /* Clear the hazard pointer */
 130   void clear() noexcept;
 131
 132   /* Swap ownership of hazard pointers between hazptr_owner-s. */
 133   /* Note: The owned hazard pointers remain unmodified during the swap
 134    * and continue to protect the respective objects that they were
 135    * protecting before the swap, if any. */
 136   void swap(hazptr_owner&) noexcept;
 137
 138  private:
 139   hazptr_domain* domain_;
 140   hazptr_rec* hazptr_;
 141 };
 142
 143 template <typename T>
 144 void swap(hazptr_owner<T>&, hazptr_owner<T>&) noexcept;
 145
 146 } // namespace hazptr
 147 } // namespace folly
 148
 149 ////////////////////////////////////////////////////////////////////////////////
 150 /// Notes
 151 ////////////////////////////////////////////////////////////////////////////////
 152
 153 /* The hazptr_obj_base template uses a reclamation function as a
 154  * parameter for the retire() member function instead of taking an
 155  * allocator template as an extra template parameter because objects
 156  * of the same type may need different reclamation functions. */
 157
 158 /* The hazptr interface supports reclamation by one domain at a
 159  * time. If an abject belongs to multiple domains simultaneously, a
 160  * workaround may be to design reclamation functions to form a series
 161  * of retirements from one domain to the next until it reaches the
 162  * final domain in the series that finally reclaims the object. */
 163
 164 ////////////////////////////////////////////////////////////////////////////////
 165
 166 #include "hazptr-impl.h"