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_domain: Class of hazard pointer domains. Each domain manages a set
  38  *  of hazard pointers and a set of retired objects. */
  39 class hazptr_domain {
  40  public:
  41   constexpr explicit hazptr_domain(
  42       memory_resource* = get_default_resource()) noexcept;
  43   ~hazptr_domain();
  44
  45   hazptr_domain(const hazptr_domain&) = delete;
  46   hazptr_domain(hazptr_domain&&) = delete;
  47   hazptr_domain& operator=(const hazptr_domain&) = delete;
  48   hazptr_domain& operator=(hazptr_domain&&) = delete;
  49
  50  private:
  51   friend class hazptr_holder;
  52   template <typename, typename>
  53   friend class hazptr_obj_base;
  54   friend struct hazptr_priv;
  55
  56   memory_resource* mr_;
  57   std::atomic<hazptr_rec*> hazptrs_ = {nullptr};
  58   std::atomic<hazptr_obj*> retired_ = {nullptr};
  59   std::atomic<int> hcount_ = {0};
  60   std::atomic<int> rcount_ = {0};
  61
  62   void objRetire(hazptr_obj*);
  63   hazptr_rec* hazptrAcquire();
  64   void hazptrRelease(hazptr_rec*) noexcept;
  65   int pushRetired(hazptr_obj* head, hazptr_obj* tail, int count);
  66   bool reachedThreshold(int rcount);
  67   void tryBulkReclaim();
  68   void bulkReclaim();
  69 };
  70
  71 /** Get the default hazptr_domain */
  72 hazptr_domain& default_hazptr_domain();
  73
  74 extern hazptr_domain default_domain_;
  75
  76 /** Definition of hazptr_obj */
  77 class hazptr_obj {
  78   friend class hazptr_domain;
  79   template <typename, typename>
  80   friend class hazptr_obj_base;
  81   friend struct hazptr_priv;
  82
  83   void (*reclaim_)(hazptr_obj*);
  84   hazptr_obj* next_;
  85   const void* getObjPtr() const;
  86 };
  87
  88 /** Definition of hazptr_obj_base */
  89 template <typename T, typename D = std::default_delete<T>>
  90 class hazptr_obj_base : public hazptr_obj {
  91  public:
  92   /* Retire a removed object and pass the responsibility for
  93    * reclaiming it to the hazptr library */
  94   void retire(hazptr_domain& domain = default_hazptr_domain(), D reclaim = {});
  95
  96  private:
  97   D deleter_;
  98 };
  99
 100 /** hazptr_holder: Class for automatic acquisition and release of
 101  *  hazard pointers, and interface for hazard pointer operations. */
 102 class hazptr_holder {
 103  public:
 104   /* Constructor automatically acquires a hazard pointer. */
 105   explicit hazptr_holder(hazptr_domain& domain = default_hazptr_domain());
 106   /* Construct an empty hazptr_holder. */
 107   // Note: This diverges from the proposal in P0233R4
 108   explicit hazptr_holder(std::nullptr_t);
 109
 110   /* Destructor automatically clears and releases the owned hazard pointer. */
 111   ~hazptr_holder();
 112
 113   hazptr_holder(const hazptr_holder&) = delete;
 114   hazptr_holder& operator=(const hazptr_holder&) = delete;
 115   // Note: This diverges from the proposal in P0233R4 which disallows
 116   // move constructor and assignment operator.
 117   hazptr_holder(hazptr_holder&&) noexcept;
 118   hazptr_holder& operator=(hazptr_holder&&) noexcept;
 119
 120   /** Hazard pointer operations */
 121   /* Returns a protected pointer from the source */
 122   template <typename T>
 123   T* get_protected(const std::atomic<T*>& src) noexcept;
 124   /* Returns a protected pointer from the source, filtering
 125      the protected pointer through function Func.  Useful for
 126      stealing bits of the pointer word */
 127   template <typename T, typename Func>
 128   T* get_protected(const std::atomic<T*>& src, Func f) noexcept;
 129   /* Return true if successful in protecting ptr if src == ptr after
 130    * setting the hazard pointer.  Otherwise sets ptr to src. */
 131   template <typename T>
 132   bool try_protect(T*& ptr, const std::atomic<T*>& src) noexcept;
 133   /* Return true if successful in protecting ptr if src == ptr after
 134    * setting the hazard pointer, filtering the pointer through Func.
 135    * Otherwise sets ptr to src. */
 136   template <typename T, typename Func>
 137   bool try_protect(T*& ptr, const std::atomic<T*>& src, Func f) noexcept;
 138   /* Set the hazard pointer to ptr */
 139   template <typename T>
 140   void reset(const T* ptr) noexcept;
 141   /* Set the hazard pointer to nullptr */
 142   void reset(std::nullptr_t = nullptr) noexcept;
 143
 144   /* Swap ownership of hazard pointers between hazptr_holder-s. */
 145   /* Note: The owned hazard pointers remain unmodified during the swap
 146    * and continue to protect the respective objects that they were
 147    * protecting before the swap, if any. */
 148   void swap(hazptr_holder&) noexcept;
 149
 150  private:
 151   hazptr_domain* domain_;
 152   hazptr_rec* hazptr_;
 153 };
 154
 155 void swap(hazptr_holder&, hazptr_holder&) noexcept;
 156
 157 } // namespace hazptr
 158 } // namespace folly
 159
 160 #include "hazptr-impl.h"