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