cds/gc/hp/details/hp_alloc.h

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