cds/gc/details/hp_alloc.h

   1 /*
   2     This file is a part of libcds - Concurrent Data Structures library
   3
   4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
   5
   6     Source code repo: http://github.com/khizmax/libcds/
   7     Download: http://sourceforge.net/projects/libcds/files/
   8
   9     Redistribution and use in source and binary forms, with or without
  10     modification, are permitted provided that the following conditions are met:
  11
  12     * Redistributions of source code must retain the above copyright notice, this
  13       list of conditions and the following disclaimer.
  14
  15     * Redistributions in binary form must reproduce the above copyright notice,
  16       this list of conditions and the following disclaimer in the documentation
  17       and/or other materials provided with the distribution.
  18
  19     THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  20     AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  21     IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  22     DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  23     FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  24     DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  25     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  26     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  27     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28     OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29 */
  30
  31 #ifndef CDSLIB_GC_DETAILS_HP_ALLOC_H
  32 #define CDSLIB_GC_DETAILS_HP_ALLOC_H
  33
  34 #include <cds/algo/atomic.h>
  35 #include <cds/details/allocator.h>
  36 #include <cds/gc/details/hp_type.h>
  37
  38 //@cond
  39 namespace cds {
  40     namespace gc { namespace hp {
  41         // forwards
  42         class GarbageCollector;
  43         class ThreadGC;
  44
  45     /// Hazard Pointer schema implementation details
  46     namespace details {
  47
  48         /// Hazard pointer guard
  49         /**
  50             It is unsafe to use this class directly.
  51             Instead, the \p hp::guard class should be used.
  52         */
  53         class hp_guard : protected atomics::atomic < hazard_pointer >
  54         {
  55             template <class Allocator> friend class hp_allocator;
  56
  57         public:
  58             typedef hazard_pointer hazard_ptr;///< Hazard pointer type
  59
  60         private:
  61             typedef atomics::atomic<hazard_ptr> atomic_hazard_ptr;
  62
  63             atomic_hazard_ptr m_hp;
  64             hp_guard*         m_next; // next free guard
  65
  66         public:
  67             hp_guard() CDS_NOEXCEPT
  68                 : m_hp( nullptr )
  69                 , m_next( nullptr )
  70             {}
  71
  72             ~hp_guard() CDS_NOEXCEPT
  73             {}
  74
  75             /// Sets HP value. Guards pointer \p p from reclamation.
  76             /**
  77                 Storing has release semantics.
  78                 */
  79                 template <typename T>
  80             T * operator =(T * p) CDS_NOEXCEPT
  81             {
  82                 // We use atomic store with explicit memory order because other threads may read this hazard pointer concurrently
  83                 set( p );
  84                 return p;
  85             }
  86
  87             std::nullptr_t operator=(std::nullptr_t) CDS_NOEXCEPT
  88             {
  89                 clear();
  90                 return nullptr;
  91             }
  92
  93             /// Returns current value of hazard pointer
  94             /**
  95                 Loading has acquire semantics
  96             */
  97             hazard_ptr get( atomics::memory_order order = atomics::memory_order_acquire ) const CDS_NOEXCEPT
  98             {
  99                 return m_hp.load( order );
 100             }
 101
 102             template <typename T>
 103             void set( T * p, atomics::memory_order order = atomics::memory_order_release ) CDS_NOEXCEPT
 104             {
 105                 m_hp.store( reinterpret_cast<hazard_ptr>(p), order );
 106             }
 107
 108             /// Clears HP
 109             /**
 110                 Clearing has relaxed semantics.
 111             */
 112             void clear( atomics::memory_order order = atomics::memory_order_release ) CDS_NOEXCEPT
 113             {
 114                 // memory order is not necessary here
 115                 m_hp.store( nullptr, order );
 116             }
 117         };
 118
 119         /// Array of hazard pointers.
 120         /**
 121             Array of hazard-pointer. Placing a pointer into this array guards the pointer against reclamation.
 122             Template parameter \p Count defines the size of hazard pointer array. \p Count parameter should not exceed
 123             GarbageCollector::getHazardPointerCount().
 124
 125             It is unsafe to use this class directly. Instead, the \p hp::array should be used.
 126
 127             While creating the object of \p hp_array class an array of size \p Count of hazard pointers is reserved by
 128             the HP Manager of current thread. The object's destructor cleans all of reserved hazard pointer and
 129             returns reserved HP to the HP pool of ThreadGC.
 130
 131             Usually, it is not necessary to create an object of this class. The object of class ThreadGC contains
 132             the \p hp_array object and implements interface for HP setting and freeing.
 133
 134             Template parameter:
 135                 \li Count - capacity of array
 136         */
 137         template <size_t Count>
 138         class hp_array
 139         {
 140             template <class Allocator> friend class hp_allocator;
 141
 142         public:
 143             typedef hazard_pointer  hazard_ptr;   ///< Hazard pointer type
 144             static CDS_CONSTEXPR const size_t c_nCapacity = Count ;   ///< Capacity of the array
 145
 146         public:
 147             /// Constructs uninitialized array.
 148             hp_array() CDS_NOEXCEPT
 149             {
 150                 memset( m_arr, 0, sizeof( m_arr ));
 151             }
 152
 153             /// Destructs object
 154             ~hp_array() CDS_NOEXCEPT
 155             {}
 156
 157             /// Returns max count of hazard pointer for this array
 158             CDS_CONSTEXPR size_t capacity() const
 159             {
 160                 return c_nCapacity;
 161             }
 162
 163             /// Set hazard pointer \p nIndex. 0 <= \p nIndex < \p Count
 164             void set( size_t nIndex, hazard_ptr hptr ) CDS_NOEXCEPT
 165             {
 166                 assert( nIndex < capacity());
 167                 assert( m_arr[nIndex] != nullptr );
 168
 169                 *m_arr[nIndex] = hptr;
 170             }
 171
 172             /// Returns pointer to hazard pointer of index \p nIndex (0 <= \p nIndex < \p Count)
 173             hp_guard* operator []( size_t nIndex ) CDS_NOEXCEPT
 174             {
 175                 assert( nIndex < capacity());
 176                 return m_arr[nIndex];
 177             }
 178
 179             /// Returns pointer to hazard pointer of index \p nIndex (0 <= \p nIndex < \p Count) [const version]
 180             hp_guard* operator []( size_t nIndex ) const CDS_NOEXCEPT
 181             {
 182                 assert( nIndex < capacity());
 183                 return m_arr[nIndex];
 184             }
 185
 186             /// Clears (sets to \p nullptr) hazard pointer \p nIndex
 187             void clear( size_t nIndex ) CDS_NOEXCEPT
 188             {
 189                 assert( nIndex < capacity());
 190                 assert( m_arr[nIndex] != nullptr );
 191
 192                 m_arr[ nIndex ]->clear();
 193             }
 194
 195             hp_guard* release( size_t nIndex ) CDS_NOEXCEPT
 196             {
 197                 assert( nIndex < capacity() );
 198
 199                 hp_guard* p = m_arr[ nIndex ];
 200                 m_arr[ nIndex ] = nullptr;
 201                 return p;
 202             }
 203
 204
 205         private:
 206             hp_guard* m_arr[c_nCapacity]; ///< Hazard pointer array of size = \p Count
 207         };
 208
 209         /// Allocator of hazard pointers for the thread
 210         /**
 211             The hazard pointer array is the free-list of unused hazard pointer for the thread.
 212             The array is managed as a stack.
 213             The max size (capacity) of array is defined at ctor time and cannot be changed during object's lifetime
 214
 215             Each allocator object is thread-private.
 216
 217             Template parameters:
 218                 \li Allocator - memory allocator class, default is \ref CDS_DEFAULT_ALLOCATOR
 219
 220             This helper class should not be used directly.
 221         */
 222         template <class Allocator = CDS_DEFAULT_ALLOCATOR >
 223         class hp_allocator
 224         {
 225         public:
 226             typedef hazard_pointer  hazard_ptr;     ///< type of hazard pointer
 227             typedef Allocator       allocator_type; ///< allocator type
 228
 229         private:
 230             typedef cds::details::Allocator< hp_guard, allocator_type > allocator_impl;
 231
 232             hp_guard*    m_arrHazardPtr; ///< Array of hazard pointers
 233             hp_guard*    m_FreeListHead; ///< List of free hp guards
 234             size_t const m_nCapacity;    ///< Array capacity
 235
 236         public:
 237             /// Default ctor
 238             explicit hp_allocator(
 239                 size_t  nCapacity ///< max count of hazard pointer per thread
 240             )
 241             : m_arrHazardPtr( alloc_array( nCapacity ))
 242             , m_FreeListHead( m_arrHazardPtr )
 243             , m_nCapacity( nCapacity )
 244             {
 245                 build_free_list();
 246             }
 247
 248             /// Dtor
 249             ~hp_allocator()
 250             {
 251                 allocator_impl().Delete( m_arrHazardPtr, capacity() );
 252             }
 253
 254             /// Get capacity of array
 255             size_t capacity() const CDS_NOEXCEPT
 256             {
 257                 return m_nCapacity;
 258             }
 259
 260             /// Get size of array. The size is equal to the capacity of array
 261             size_t size() const CDS_NOEXCEPT
 262             {
 263                 return capacity();
 264             }
 265
 266             /// Checks if all items are allocated
 267             bool full() const CDS_NOEXCEPT
 268             {
 269                 return m_FreeListHead == nullptr;
 270             }
 271
 272             /// Allocates hazard pointer
 273             hp_guard* alloc()
 274             {
 275                 assert( !full());
 276
 277                 hp_guard* p = m_FreeListHead;
 278                 m_FreeListHead = m_FreeListHead->m_next;
 279                 return p;
 280             }
 281
 282             /// Frees previously allocated hazard pointer
 283             void free( hp_guard* hp ) CDS_NOEXCEPT
 284             {
 285                 if ( hp ) {
 286                     hp->clear();
 287                     hp->m_next = m_FreeListHead;
 288                     m_FreeListHead = hp;
 289                 }
 290             }
 291
 292             /// Allocates hazard pointers array
 293             /**
 294                 Allocates \p Count hazard pointers from array \p m_arrHazardPtr
 295                 Initializes \p arr with hazard pointers.
 296
 297                 @return actual size of allocated array.
 298             */
 299             template <size_t Count>
 300             size_t alloc( hp_array<Count>& arr )
 301             {
 302                 size_t i;
 303                 hp_guard* p = m_FreeListHead;
 304                 for ( i = 0; i < Count && p; ++i ) {
 305                     arr.m_arr[i] = p;
 306                     p = p->m_next;
 307                 }
 308                 size_t ret = i;
 309                 for ( ; i < Count; ++i )
 310                     arr.m_arr[i] = nullptr;
 311                 m_FreeListHead = p;
 312                 return ret;
 313             }
 314
 315             /// Frees hazard pointer array
 316             /**
 317                 Frees the array of hazard pointers allocated by previous call \p this->alloc.
 318             */
 319             template <size_t Count>
 320             void free( hp_array<Count> const& arr ) CDS_NOEXCEPT
 321             {
 322                 hp_guard* pList = m_FreeListHead;
 323                 for ( size_t i = 0; i < Count; ++i ) {
 324                     hp_guard* p = arr[i];
 325                     if ( p ) {
 326                         p->clear();
 327                         p->m_next = pList;
 328                         pList = p;
 329                     }
 330                 }
 331                 m_FreeListHead = pList;
 332             }
 333
 334             /// Makes all HP free
 335             void clear() CDS_NOEXCEPT
 336             {
 337                 for ( size_t i = 0; i < capacity(); ++i )
 338                     m_arrHazardPtr[i].clear();
 339             }
 340
 341             /// Returns i-th hazard pointer
 342             hp_guard& operator []( size_t i ) CDS_NOEXCEPT
 343             {
 344                 assert( i < capacity() );
 345                 return m_arrHazardPtr[i];
 346             }
 347
 348         private:
 349             hp_guard* alloc_array( size_t nCapacity )
 350             {
 351                 return allocator_impl().NewArray( nCapacity );
 352             }
 353
 354             void build_free_list()
 355             {
 356                 hp_guard* first = m_arrHazardPtr;
 357                 hp_guard* last = m_arrHazardPtr + capacity();
 358                 hp_guard* prev = first;
 359                 for ( ++first; first < last; ++first ) {
 360                     prev->m_next = first;
 361                     prev = first;
 362                 }
 363                 prev->m_next = nullptr;
 364                 m_FreeListHead = m_arrHazardPtr;
 365             }
 366         };
 367
 368     }}} // namespace gc::hp::details
 369 }   // namespace cds
 370 //@endcond
 371
 372 #endif // #ifndef CDSLIB_GC_DETAILS_HP_ALLOC_H