cds/gc/hzp/details/hp_alloc.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_GC_HZP_DETAILS_HP_ALLOC_H
   4 #define __CDS_GC_HZP_DETAILS_HP_ALLOC_H
   5
   6 #include <cds/cxx11_atomic.h>
   7 #include <cds/details/allocator.h>
   8 #include <cds/gc/hzp/details/hp_fwd.h>
   9 #include <cds/gc/hzp/details/hp_type.h>
  10
  11 //@cond
  12 namespace cds {
  13     namespace gc { namespace hzp {
  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 CDS_ATOMIC::atomic<HazardPointer>
  27         {
  28         public:
  29             typedef HazardPointer   hazard_ptr ;    ///< Hazard pointer type
  30         private:
  31             //@cond
  32             typedef CDS_ATOMIC::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), CDS_ATOMIC::memory_order_release );
  56                 return p;
  57             }
  58
  59             /// Returns current value of hazard pointer
  60             /**
  61                 Loading has acquire semantics
  62             */
  63             operator hazard_ptr() const CDS_NOEXCEPT
  64             {
  65                 return get();
  66             }
  67
  68             /// Returns current value of hazard pointer
  69             /**
  70                 Loading has acquire semantics
  71             */
  72             hazard_ptr get() const CDS_NOEXCEPT
  73             {
  74                 return base_class::load( CDS_ATOMIC::memory_order_acquire );
  75             }
  76
  77             /// Clears HP
  78             /**
  79                 Clearing has relaxed semantics.
  80             */
  81             void clear() CDS_NOEXCEPT
  82             {
  83                 // memory order is not necessary here
  84                 base_class::store( nullptr, CDS_ATOMIC::memory_order_relaxed );
  85                 //CDS_COMPILER_RW_BARRIER;
  86             }
  87         };
  88
  89         /// Specialization of HPGuardT for hazard_pointer type
  90         typedef HPGuardT<hazard_pointer> HPGuard;
  91
  92         /// Array of hazard pointers.
  93         /**
  94             Array of hazard-pointer. Placing a pointer into this array guards the pointer against reclamation.
  95             Template parameter \p Count defines the size of hazard pointer array. \p Count parameter should not exceed
  96             GarbageCollector::getHazardPointerCount().
  97
  98             It is unsafe to use this class directly. Instead, the AutoHPArray should be used.
  99
 100             While creating the object of HPArray class an array of size \p Count of hazard pointers is reserved by
 101             the HP Manager of current thread. The object's destructor cleans all of reserved hazard pointer and
 102             returns reserved HP to the HP pool of ThreadGC.
 103
 104             Usually, it is not necessary to create an object of this class. The object of class ThreadGC contains
 105             the HPArray object and implements interface for HP setting and freeing.
 106
 107             Template parameter:
 108                 \li HazardPointer - type of hazard pointer. It is hazard_pointer usually
 109                 \li Count - capacity of array
 110
 111         */
 112         template <typename HazardPointer, size_t Count>
 113         class HPArrayT
 114         {
 115         public:
 116             typedef HazardPointer   hazard_ptr_type ;   ///< Hazard pointer type
 117             typedef HPGuardT<hazard_ptr_type>   atomic_hazard_ptr    ; ///< Element type of the array
 118             static const size_t c_nCapacity = Count ;   ///< Capacity of the array
 119
 120         private:
 121             //@cond
 122             atomic_hazard_ptr *     m_arr               ;   ///< Hazard pointer array of size = \p Count
 123             template <typename OtherHazardPointer, class Allocator> friend class HPAllocator;
 124             //@endcond
 125
 126         public:
 127             /// Constructs uninitialized array.
 128             HPArrayT() CDS_NOEXCEPT
 129             {}
 130
 131             /// Destructs object
 132             ~HPArrayT() 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 NULL) 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         /// Specialization of HPArrayT class for hazard_pointer type
 171 #ifdef CDS_CXX11_TEMPLATE_ALIAS_SUPPORT
 172         template <size_t Count> using HPArray = HPArrayT<hazard_pointer, Count >;
 173 #else
 174         template <size_t Count>
 175         class HPArray: public HPArrayT<hazard_pointer, Count>
 176         {};
 177 #endif
 178
 179         /// Allocator of hazard pointers for the thread
 180         /**
 181             The hazard pointer array is the free-list of unused hazard pointer for the thread.
 182             The array is managed as a stack.
 183             The max size (capacity) of array is defined at ctor time and cannot be changed during object's lifetime
 184
 185             Each allocator object is thread-private.
 186
 187             Template parameters:
 188                 \li HazardPointer - type of hazard pointer (hazard_pointer usually)
 189                 \li Allocator - memory allocator class, default is \ref CDS_DEFAULT_ALLOCATOR
 190
 191             This helper class should not be used directly.
 192         */
 193         template < typename HazardPointer, class Allocator = CDS_DEFAULT_ALLOCATOR >
 194         class HPAllocator
 195         {
 196         public:
 197             typedef HazardPointer               hazard_ptr_type     ;   ///< type of hazard pointer
 198             typedef HPGuardT<hazard_ptr_type>   atomic_hazard_ptr   ;   ///< Atomic hazard pointer type
 199             typedef Allocator                   allocator_type      ;   ///< allocator type
 200
 201         private:
 202             //@cond
 203             typedef cds::details::Allocator< atomic_hazard_ptr, allocator_type > allocator_impl;
 204
 205             atomic_hazard_ptr * m_arrHazardPtr  ;   ///< Array of hazard pointers
 206             size_t              m_nTop          ;   ///< The top of stack
 207             const size_t        m_nCapacity     ;   ///< Array capacity
 208
 209             //@endcond
 210
 211         public:
 212             /// Default ctor
 213             explicit HPAllocator(
 214                 size_t  nCapacity            ///< max count of hazard pointer per thread
 215                 )
 216                 : m_arrHazardPtr( alloc_array( nCapacity ) )
 217                 , m_nCapacity( nCapacity )
 218             {
 219                 make_free();
 220             }
 221
 222             /// Dtor
 223             ~HPAllocator()
 224             {
 225                 allocator_impl().Delete( m_arrHazardPtr, capacity() );
 226             }
 227
 228             /// Get capacity of array
 229             size_t capacity() const CDS_NOEXCEPT
 230             {
 231                 return m_nCapacity;
 232             }
 233
 234             /// Get size of array. The size is equal to the capacity of array
 235             size_t size() const CDS_NOEXCEPT
 236             {
 237                 return capacity();
 238             }
 239
 240             /// Checks if all items are allocated
 241             bool isFull() const CDS_NOEXCEPT
 242             {
 243                 return m_nTop == 0;
 244             }
 245
 246             /// Allocates hazard pointer
 247             atomic_hazard_ptr& alloc() CDS_NOEXCEPT
 248             {
 249                 assert( m_nTop > 0 );
 250                 --m_nTop;
 251                 return m_arrHazardPtr[m_nTop];
 252             }
 253
 254             /// Frees previously allocated hazard pointer
 255             void free( atomic_hazard_ptr& hp ) CDS_NOEXCEPT
 256             {
 257                 assert( m_nTop < capacity() );
 258                 hp.clear();
 259                 ++m_nTop;
 260                 CDS_COMPILER_RW_BARRIER ;   // ???
 261             }
 262
 263             /// Allocates hazard pointers array
 264             /**
 265                 Allocates \p Count hazard pointers from array \p m_arrHazardPtr
 266                 Returns initialized object \p arr
 267             */
 268             template <size_t Count>
 269             void alloc( HPArrayT<hazard_ptr_type, Count>& arr ) CDS_NOEXCEPT
 270             {
 271                 assert( m_nTop >= Count );
 272                 m_nTop -= Count;
 273                 arr.m_arr = m_arrHazardPtr + m_nTop;
 274             }
 275
 276             /// Frees hazard pointer array
 277             /**
 278                 Frees the array of hazard pointers allocated by previous call \p this->alloc.
 279             */
 280             template <size_t Count>
 281             void free( const HPArrayT<hazard_ptr_type, Count>& arr ) CDS_NOEXCEPT
 282             {
 283                 assert( m_nTop + Count <= capacity());
 284                 for ( size_t i = m_nTop; i < m_nTop + Count; ++i )
 285                     m_arrHazardPtr[ i ].clear();
 286                 m_nTop += Count;
 287             }
 288
 289             /// Makes all HP free
 290             void clear() CDS_NOEXCEPT
 291             {
 292                 make_free();
 293             }
 294
 295             /// Returns to i-th hazard pointer
 296             atomic_hazard_ptr& operator []( size_t i ) CDS_NOEXCEPT
 297             {
 298                 assert( i < capacity() );
 299                 return m_arrHazardPtr[i];
 300             }
 301
 302         private:
 303             //@cond
 304             void make_free() CDS_NOEXCEPT
 305             {
 306                 for ( size_t i = 0; i < capacity(); ++i )
 307                     m_arrHazardPtr[ i ].clear();
 308                 m_nTop = capacity();
 309             }
 310
 311             atomic_hazard_ptr * alloc_array( size_t nCapacity )
 312             {
 313                 return allocator_impl().NewArray( nCapacity );
 314             }
 315             //@endcond
 316         };
 317
 318     }}} // namespace gc::hzp::details
 319 }   // namespace cds
 320 //@endcond
 321
 322 #endif // #ifndef __CDS_GC_HZP_DETAILS_HP_ALLOC_H