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 #include <string.h> // memset
  38
  39 //@cond
  40 namespace cds {
  41     namespace gc { namespace hp {
  42         // forwards
  43         class GarbageCollector;
  44         class ThreadGC;
  45
  46     /// Hazard Pointer schema implementation details
  47     namespace details {
  48
  49         /// Hazard pointer guard
  50         /**
  51             It is unsafe to use this class directly.
  52             Instead, the \p hp::guard class should be used.
  53         */
  54         class hp_guard : protected atomics::atomic < hazard_pointer >
  55         {
  56             template <class Allocator> friend class hp_allocator;
  57
  58         public:
  59             typedef hazard_pointer hazard_ptr;///< Hazard pointer type
  60
  61         private:
  62             typedef atomics::atomic<hazard_ptr> atomic_hazard_ptr;
  63
  64             atomic_hazard_ptr m_hp;
  65             hp_guard*         m_next; // next free guard
  66
  67         public:
  68             hp_guard() CDS_NOEXCEPT
  69                 : m_hp( nullptr )
  70                 , m_next( nullptr )
  71             {}
  72
  73             ~hp_guard() CDS_NOEXCEPT
  74             {}
  75
  76             /// Sets HP value. Guards pointer \p p from reclamation.
  77             /**
  78                 Storing has release semantics.
  79                 */
  80                 template <typename T>
  81             T * operator =(T * p) CDS_NOEXCEPT
  82             {
  83                 // We use atomic store with explicit memory order because other threads may read this hazard pointer concurrently
  84                 set( p );
  85                 return p;
  86             }
  87
  88             std::nullptr_t operator=(std::nullptr_t) CDS_NOEXCEPT
  89             {
  90                 clear();
  91                 return nullptr;
  92             }
  93
  94             /// Returns current value of hazard pointer
  95             /**
  96                 Loading has acquire semantics
  97             */
  98             hazard_ptr get( atomics::memory_order order = atomics::memory_order_acquire ) const CDS_NOEXCEPT
  99             {
 100                 return m_hp.load( order );
 101             }
 102
 103             template <typename T>
 104             void set( T * p, atomics::memory_order order = atomics::memory_order_release ) CDS_NOEXCEPT
 105             {
 106                 m_hp.store( reinterpret_cast<hazard_ptr>(p), order );
 107             }
 108
 109             /// Clears HP
 110             /**
 111                 Clearing has relaxed semantics.
 112             */
 113             void clear( atomics::memory_order order = atomics::memory_order_release ) CDS_NOEXCEPT
 114             {
 115                 // memory order is not necessary here
 116                 m_hp.store( nullptr, order );
 117             }
 118         };
 119
 120         /// Array of hazard pointers.
 121         /**
 122             Array of hazard-pointer. Placing a pointer into this array guards the pointer against reclamation.
 123             Template parameter \p Count defines the size of hazard pointer array. \p Count parameter should not exceed
 124             GarbageCollector::getHazardPointerCount().
 125
 126             It is unsafe to use this class directly. Instead, the \p hp::array should be used.
 127
 128             While creating the object of \p hp_array class an array of size \p Count of hazard pointers is reserved by
 129             the HP Manager of current thread. The object's destructor cleans all of reserved hazard pointer and
 130             returns reserved HP to the HP pool of ThreadGC.
 131
 132             Usually, it is not necessary to create an object of this class. The object of class ThreadGC contains
 133             the \p hp_array object and implements interface for HP setting and freeing.
 134
 135             Template parameter:
 136                 \li Count - capacity of array
 137         */
 138         template <size_t Count>
 139         class hp_array
 140         {
 141             template <class Allocator> friend class hp_allocator;
 142
 143         public:
 144             typedef hazard_pointer  hazard_ptr;   ///< Hazard pointer type
 145             static CDS_CONSTEXPR const size_t c_nCapacity = Count ;   ///< Capacity of the array
 146
 147         public:
 148             /// Constructs uninitialized array.
 149             hp_array() CDS_NOEXCEPT
 150             {
 151                 memset( m_arr, 0, sizeof( m_arr ));
 152             }
 153
 154             /// Destructs object
 155             ~hp_array() CDS_NOEXCEPT
 156             {}
 157
 158             /// Returns max count of hazard pointer for this array
 159             CDS_CONSTEXPR size_t capacity() const
 160             {
 161                 return c_nCapacity;
 162             }
 163
 164             /// Set hazard pointer \p nIndex. 0 <= \p nIndex < \p Count
 165             void set( size_t nIndex, hazard_ptr hptr ) CDS_NOEXCEPT
 166             {
 167                 assert( nIndex < capacity());
 168                 assert( m_arr[nIndex] != nullptr );
 169
 170                 *m_arr[nIndex] = hptr;
 171             }
 172
 173             /// Returns pointer to hazard pointer of index \p nIndex (0 <= \p nIndex < \p Count)
 174             hp_guard* operator []( size_t nIndex ) CDS_NOEXCEPT
 175             {
 176                 assert( nIndex < capacity());
 177                 return m_arr[nIndex];
 178             }
 179
 180             /// Returns pointer to hazard pointer of index \p nIndex (0 <= \p nIndex < \p Count) [const version]
 181             hp_guard* operator []( size_t nIndex ) const CDS_NOEXCEPT
 182             {
 183                 assert( nIndex < capacity());
 184                 return m_arr[nIndex];
 185             }
 186
 187             /// Clears (sets to \p nullptr) hazard pointer \p nIndex
 188             void clear( size_t nIndex ) CDS_NOEXCEPT
 189             {
 190                 assert( nIndex < capacity());
 191                 assert( m_arr[nIndex] != nullptr );
 192
 193                 m_arr[ nIndex ]->clear();
 194             }
 195
 196             hp_guard* release( size_t nIndex ) CDS_NOEXCEPT
 197             {
 198                 assert( nIndex < capacity());
 199
 200                 hp_guard* p = m_arr[ nIndex ];
 201                 m_arr[ nIndex ] = nullptr;
 202                 return p;
 203             }
 204
 205
 206         private:
 207             hp_guard* m_arr[c_nCapacity]; ///< Hazard pointer array of size = \p Count
 208         };
 209
 210         /// Allocator of hazard pointers for the thread
 211         /**
 212             The hazard pointer array is the free-list of unused hazard pointer for the thread.
 213             The array is managed as a stack.
 214             The max size (capacity) of array is defined at ctor time and cannot be changed during object's lifetime
 215
 216             Each allocator object is thread-private.
 217
 218             Template parameters:
 219                 \li Allocator - memory allocator class, default is \ref CDS_DEFAULT_ALLOCATOR
 220
 221             This helper class should not be used directly.
 222         */
 223         template <class Allocator = CDS_DEFAULT_ALLOCATOR >
 224         class hp_allocator
 225         {
 226         public:
 227             typedef hazard_pointer  hazard_ptr;     ///< type of hazard pointer
 228             typedef Allocator       allocator_type; ///< allocator type
 229
 230         private:
 231             typedef cds::details::Allocator< hp_guard, allocator_type > allocator_impl;
 232
 233             hp_guard*    m_arrHazardPtr; ///< Array of hazard pointers
 234             hp_guard*    m_FreeListHead; ///< List of free hp guards
 235             size_t const m_nCapacity;    ///< Array capacity
 236
 237         public:
 238             /// Default ctor
 239             explicit hp_allocator(
 240                 size_t  nCapacity ///< max count of hazard pointer per thread
 241             )
 242             : m_arrHazardPtr( alloc_array( nCapacity ))
 243             , m_FreeListHead( m_arrHazardPtr )
 244             , m_nCapacity( nCapacity )
 245             {
 246                 build_free_list();
 247             }
 248
 249             /// Dtor
 250             ~hp_allocator()
 251             {
 252                 allocator_impl().Delete( m_arrHazardPtr, capacity());
 253             }
 254
 255             /// Get capacity of array
 256             size_t capacity() const CDS_NOEXCEPT
 257             {
 258                 return m_nCapacity;
 259             }
 260
 261             /// Get size of array. The size is equal to the capacity of array
 262             size_t size() const CDS_NOEXCEPT
 263             {
 264                 return capacity();
 265             }
 266
 267             /// Checks if all items are allocated
 268             bool full() const CDS_NOEXCEPT
 269             {
 270                 return m_FreeListHead == nullptr;
 271             }
 272
 273             /// Allocates hazard pointer
 274             hp_guard* alloc()
 275             {
 276                 assert( !full());
 277
 278                 hp_guard* p = m_FreeListHead;
 279                 m_FreeListHead = m_FreeListHead->m_next;
 280                 return p;
 281             }
 282
 283             /// Frees previously allocated hazard pointer
 284             void free( hp_guard* hp ) CDS_NOEXCEPT
 285             {
 286                 if ( hp ) {
 287                     hp->clear();
 288                     hp->m_next = m_FreeListHead;
 289                     m_FreeListHead = hp;
 290                 }
 291             }
 292
 293             /// Allocates hazard pointers array
 294             /**
 295                 Allocates \p Count hazard pointers from array \p m_arrHazardPtr
 296                 Initializes \p arr with hazard pointers.
 297
 298                 @return actual size of allocated array.
 299             */
 300             template <size_t Count>
 301             size_t alloc( hp_array<Count>& arr )
 302             {
 303                 size_t i;
 304                 hp_guard* p = m_FreeListHead;
 305                 for ( i = 0; i < Count && p; ++i ) {
 306                     arr.m_arr[i] = p;
 307                     p = p->m_next;
 308                 }
 309                 size_t ret = i;
 310                 for ( ; i < Count; ++i )
 311                     arr.m_arr[i] = nullptr;
 312                 m_FreeListHead = p;
 313                 return ret;
 314             }
 315
 316             /// Frees hazard pointer array
 317             /**
 318                 Frees the array of hazard pointers allocated by previous call \p this->alloc.
 319             */
 320             template <size_t Count>
 321             void free( hp_array<Count> const& arr ) CDS_NOEXCEPT
 322             {
 323                 hp_guard* pList = m_FreeListHead;
 324                 for ( size_t i = 0; i < Count; ++i ) {
 325                     hp_guard* p = arr[i];
 326                     if ( p ) {
 327                         p->clear();
 328                         p->m_next = pList;
 329                         pList = p;
 330                     }
 331                 }
 332                 m_FreeListHead = pList;
 333             }
 334
 335             /// Makes all HP free
 336             void clear() CDS_NOEXCEPT
 337             {
 338                 for ( size_t i = 0; i < capacity(); ++i )
 339                     m_arrHazardPtr[i].clear();
 340             }
 341
 342             /// Returns i-th hazard pointer
 343             hp_guard& operator []( size_t i ) CDS_NOEXCEPT
 344             {
 345                 assert( i < capacity());
 346                 return m_arrHazardPtr[i];
 347             }
 348
 349         private:
 350             hp_guard* alloc_array( size_t nCapacity )
 351             {
 352                 return allocator_impl().NewArray( nCapacity );
 353             }
 354
 355             void build_free_list()
 356             {
 357                 hp_guard* first = m_arrHazardPtr;
 358                 hp_guard* last = m_arrHazardPtr + capacity();
 359                 hp_guard* prev = first;
 360                 for ( ++first; first < last; ++first ) {
 361                     prev->m_next = first;
 362                     prev = first;
 363                 }
 364                 prev->m_next = nullptr;
 365                 m_FreeListHead = m_arrHazardPtr;
 366             }
 367         };
 368
 369     }}} // namespace gc::hp::details
 370 }   // namespace cds
 371 //@endcond
 372
 373 #endif // #ifndef CDSLIB_GC_DETAILS_HP_ALLOC_H