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