cds/gc/details/hp_alloc.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_GC_DETAILS_HP_ALLOC_H
   4 #define __CDS_GC_DETAILS_HP_ALLOC_H
   5
   6 #include <cds/algo/atomic.h>
   7 #include <cds/details/allocator.h>
   8 #include <cds/gc/details/hp_type.h>
   9
  10 //@cond
  11 namespace cds {
  12     namespace gc { namespace hp {
  13         // forwards
  14         class GarbageCollector;
  15         class ThreadGC;
  16
  17     /// Hazard Pointer schema implementation details
  18     namespace details {
  19
  20         /// Hazard pointer guard
  21         /**
  22             It is unsafe to use this class directly.
  23             Instead, the \p hp::guard class should be used.
  24         */
  25         class hp_guard : protected atomics::atomic < hazard_pointer >
  26         {
  27         public:
  28             typedef hazard_pointer   hazard_ptr;    ///< Hazard pointer type
  29         private:
  30             typedef atomics::atomic<hazard_ptr>  base_class;
  31
  32         protected:
  33             template <class Allocator> friend class hp_allocator;
  34
  35         public:
  36             hp_guard() CDS_NOEXCEPT
  37                 : base_class( nullptr )
  38             {}
  39             ~hp_guard() CDS_NOEXCEPT
  40             {}
  41
  42             /// Sets HP value. Guards pointer \p p from reclamation.
  43             /**
  44                 Storing has release semantics.
  45                 */
  46                 template <typename T>
  47             T * operator =(T * p) CDS_NOEXCEPT
  48             {
  49                 // We use atomic store with explicit memory order because other threads may read this hazard pointer concurrently
  50                 set( p );
  51                 return p;
  52             }
  53
  54             std::nullptr_t operator=(std::nullptr_t) CDS_NOEXCEPT
  55             {
  56                 clear();
  57                 return nullptr;
  58             }
  59
  60             /// Returns current value of hazard pointer
  61             /**
  62                 Loading has acquire semantics
  63             */
  64             operator hazard_ptr() const CDS_NOEXCEPT
  65             {
  66                 return get();
  67             }
  68
  69             /// Returns current value of hazard pointer
  70             /**
  71                 Loading has acquire semantics
  72             */
  73             hazard_ptr get( atomics::memory_order order = atomics::memory_order_acquire ) const CDS_NOEXCEPT
  74             {
  75                 return base_class::load( order );
  76             }
  77
  78             template <typename T>
  79             void set( T * p, atomics::memory_order order = atomics::memory_order_release ) CDS_NOEXCEPT
  80             {
  81                 base_class::store( reinterpret_cast<hazard_ptr>(p), order );
  82             }
  83
  84             /// Clears HP
  85             /**
  86                 Clearing has relaxed semantics.
  87             */
  88             void clear( atomics::memory_order order = atomics::memory_order_relaxed ) CDS_NOEXCEPT
  89             {
  90                 // memory order is not necessary here
  91                 base_class::store( nullptr, order );
  92             }
  93         };
  94
  95         /// Array of hazard pointers.
  96         /**
  97             Array of hazard-pointer. Placing a pointer into this array guards the pointer against reclamation.
  98             Template parameter \p Count defines the size of hazard pointer array. \p Count parameter should not exceed
  99             GarbageCollector::getHazardPointerCount().
 100
 101             It is unsafe to use this class directly. Instead, the \p hp::array should be used.
 102
 103             While creating the object of \p hp_array class an array of size \p Count of hazard pointers is reserved by
 104             the HP Manager of current thread. The object's destructor cleans all of reserved hazard pointer and
 105             returns reserved HP to the HP pool of ThreadGC.
 106
 107             Usually, it is not necessary to create an object of this class. The object of class ThreadGC contains
 108             the \p hp_array object and implements interface for HP setting and freeing.
 109
 110             Template parameter:
 111                 \li Count - capacity of array
 112
 113         */
 114         template <size_t Count>
 115         class hp_array
 116         {
 117         public:
 118             typedef hazard_pointer  hazard_ptr_type;   ///< Hazard pointer type
 119             typedef hp_guard        atomic_hazard_ptr; ///< Element type of the array
 120             static CDS_CONSTEXPR const size_t c_nCapacity = Count ;   ///< Capacity of the array
 121
 122         private:
 123             atomic_hazard_ptr *     m_arr               ;   ///< Hazard pointer array of size = \p Count
 124             template <class Allocator> friend class hp_allocator;
 125
 126         public:
 127             /// Constructs uninitialized array.
 128             hp_array() CDS_NOEXCEPT
 129             {}
 130
 131             /// Destructs object
 132             ~hp_array() CDS_NOEXCEPT
 133             {}
 134
 135             /// Returns max count of hazard pointer for this array
 136             CDS_CONSTEXPR size_t capacity() const
 137             {
 138                 return c_nCapacity;
 139             }
 140
 141             /// Set hazard pointer \p nIndex. 0 <= \p nIndex < \p Count
 142             void set( size_t nIndex, hazard_ptr_type hzPtr ) CDS_NOEXCEPT
 143             {
 144                 assert( nIndex < capacity() );
 145                 m_arr[nIndex] = hzPtr;
 146             }
 147
 148             /// Returns reference to hazard pointer of index \p nIndex (0 <= \p nIndex < \p Count)
 149             atomic_hazard_ptr& operator []( size_t nIndex ) CDS_NOEXCEPT
 150             {
 151                 assert( nIndex < capacity() );
 152                 return m_arr[nIndex];
 153             }
 154
 155             /// Returns reference to hazard pointer of index \p nIndex (0 <= \p nIndex < \p Count) [const version]
 156             atomic_hazard_ptr& operator []( size_t nIndex ) const CDS_NOEXCEPT
 157             {
 158                 assert( nIndex < capacity() );
 159                 return m_arr[nIndex];
 160             }
 161
 162             /// Clears (sets to \p nullptr) hazard pointer \p nIndex
 163             void clear( size_t nIndex ) CDS_NOEXCEPT
 164             {
 165                 assert( nIndex < capacity() );
 166                 m_arr[ nIndex ].clear();
 167             }
 168         };
 169
 170         /// Allocator of hazard pointers for the thread
 171         /**
 172             The hazard pointer array is the free-list of unused hazard pointer for the thread.
 173             The array is managed as a stack.
 174             The max size (capacity) of array is defined at ctor time and cannot be changed during object's lifetime
 175
 176             Each allocator object is thread-private.
 177
 178             Template parameters:
 179                 \li Allocator - memory allocator class, default is \ref CDS_DEFAULT_ALLOCATOR
 180
 181             This helper class should not be used directly.
 182         */
 183         template <class Allocator = CDS_DEFAULT_ALLOCATOR >
 184         class hp_allocator
 185         {
 186         public:
 187             typedef hazard_pointer  hazard_ptr_type;    ///< type of hazard pointer
 188             typedef hp_guard        atomic_hazard_ptr;  ///< Atomic hazard pointer type
 189             typedef Allocator       allocator_type;     ///< allocator type
 190
 191         private:
 192             typedef cds::details::Allocator< atomic_hazard_ptr, allocator_type > allocator_impl;
 193
 194             atomic_hazard_ptr * m_arrHazardPtr  ;   ///< Array of hazard pointers
 195             size_t              m_nTop          ;   ///< The top of stack
 196             const size_t        m_nCapacity     ;   ///< Array capacity
 197
 198         public:
 199             /// Default ctor
 200             explicit hp_allocator(
 201                 size_t  nCapacity            ///< max count of hazard pointer per thread
 202                 )
 203                 : m_arrHazardPtr( alloc_array( nCapacity ) )
 204                 , m_nCapacity( nCapacity )
 205             {
 206                 make_free();
 207             }
 208
 209             /// Dtor
 210             ~hp_allocator()
 211             {
 212                 allocator_impl().Delete( m_arrHazardPtr, capacity() );
 213             }
 214
 215             /// Get capacity of array
 216             size_t capacity() const CDS_NOEXCEPT
 217             {
 218                 return m_nCapacity;
 219             }
 220
 221             /// Get size of array. The size is equal to the capacity of array
 222             size_t size() const CDS_NOEXCEPT
 223             {
 224                 return capacity();
 225             }
 226
 227             /// Checks if all items are allocated
 228             bool isFull() const CDS_NOEXCEPT
 229             {
 230                 return m_nTop == 0;
 231             }
 232
 233             /// Allocates hazard pointer
 234             atomic_hazard_ptr& alloc()
 235             {
 236                 assert( m_nTop > 0 );
 237                 --m_nTop;
 238                 return m_arrHazardPtr[m_nTop];
 239             }
 240
 241             /// Frees previously allocated hazard pointer
 242             void free( atomic_hazard_ptr& hp ) CDS_NOEXCEPT
 243             {
 244                 assert( m_nTop < capacity() );
 245                 hp.clear();
 246                 ++m_nTop;
 247             }
 248
 249             /// Allocates hazard pointers array
 250             /**
 251                 Allocates \p Count hazard pointers from array \p m_arrHazardPtr
 252                 Returns initialized object \p arr
 253             */
 254             template <size_t Count>
 255             void alloc( hp_array<Count>& arr )
 256             {
 257                 assert( m_nTop >= Count );
 258                 m_nTop -= Count;
 259                 arr.m_arr = m_arrHazardPtr + m_nTop;
 260             }
 261
 262             /// Frees hazard pointer array
 263             /**
 264                 Frees the array of hazard pointers allocated by previous call \p this->alloc.
 265             */
 266             template <size_t Count>
 267             void free( hp_array<Count> const& arr ) CDS_NOEXCEPT
 268             {
 269                 CDS_UNUSED( arr );
 270
 271                 assert( m_nTop + Count <= capacity());
 272                 for ( size_t i = m_nTop; i < m_nTop + Count; ++i )
 273                     m_arrHazardPtr[i].clear();
 274                 m_nTop += Count;
 275             }
 276
 277             /// Makes all HP free
 278             void clear() CDS_NOEXCEPT
 279             {
 280                 make_free();
 281             }
 282
 283             /// Returns to i-th hazard pointer
 284             atomic_hazard_ptr& operator []( size_t i ) CDS_NOEXCEPT
 285             {
 286                 assert( i < capacity() );
 287                 return m_arrHazardPtr[i];
 288             }
 289
 290         private:
 291             void make_free() CDS_NOEXCEPT
 292             {
 293                 for ( size_t i = 0; i < capacity(); ++i )
 294                     m_arrHazardPtr[i].clear();
 295                 m_nTop = capacity();
 296             }
 297
 298             atomic_hazard_ptr * alloc_array( size_t nCapacity )
 299             {
 300                 return allocator_impl().NewArray( nCapacity );
 301             }
 302         };
 303
 304     }}} // namespace gc::hp::details
 305 }   // namespace cds
 306 //@endcond
 307
 308 #endif // #ifndef __CDS_GC_DETAILS_HP_ALLOC_H