2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
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.
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.
31 #ifndef CDSLIB_GC_DETAILS_HP_ALLOC_H
32 #define CDSLIB_GC_DETAILS_HP_ALLOC_H
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
41 namespace gc { namespace hp {
43 class GarbageCollector;
46 /// Hazard Pointer schema implementation details
49 /// Hazard pointer guard
51 It is unsafe to use this class directly.
52 Instead, the \p hp::guard class should be used.
54 class hp_guard : protected atomics::atomic < hazard_pointer >
56 template <class Allocator> friend class hp_allocator;
59 typedef hazard_pointer hazard_ptr;///< Hazard pointer type
62 typedef atomics::atomic<hazard_ptr> atomic_hazard_ptr;
64 atomic_hazard_ptr m_hp;
65 hp_guard* m_next; // next free guard
68 hp_guard() CDS_NOEXCEPT
73 ~hp_guard() CDS_NOEXCEPT
76 /// Sets HP value. Guards pointer \p p from reclamation.
78 Storing has release semantics.
81 T * operator =(T * p) CDS_NOEXCEPT
83 // We use atomic store with explicit memory order because other threads may read this hazard pointer concurrently
88 std::nullptr_t operator=(std::nullptr_t) CDS_NOEXCEPT
94 /// Returns current value of hazard pointer
96 Loading has acquire semantics
98 hazard_ptr get( atomics::memory_order order = atomics::memory_order_acquire ) const CDS_NOEXCEPT
100 return m_hp.load( order );
103 template <typename T>
104 void set( T * p, atomics::memory_order order = atomics::memory_order_release ) CDS_NOEXCEPT
106 m_hp.store( reinterpret_cast<hazard_ptr>(p), order );
111 Clearing has relaxed semantics.
113 void clear( atomics::memory_order order = atomics::memory_order_release ) CDS_NOEXCEPT
115 // memory order is not necessary here
116 m_hp.store( nullptr, order );
120 /// Array of hazard pointers.
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().
126 It is unsafe to use this class directly. Instead, the \p hp::array should be used.
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.
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.
136 \li Count - capacity of array
138 template <size_t Count>
141 template <class Allocator> friend class hp_allocator;
144 typedef hazard_pointer hazard_ptr; ///< Hazard pointer type
145 static CDS_CONSTEXPR const size_t c_nCapacity = Count ; ///< Capacity of the array
148 /// Constructs uninitialized array.
149 hp_array() CDS_NOEXCEPT
151 memset( m_arr, 0, sizeof( m_arr ));
155 ~hp_array() CDS_NOEXCEPT
158 /// Returns max count of hazard pointer for this array
159 CDS_CONSTEXPR size_t capacity() const
164 /// Set hazard pointer \p nIndex. 0 <= \p nIndex < \p Count
165 void set( size_t nIndex, hazard_ptr hptr ) CDS_NOEXCEPT
167 assert( nIndex < capacity());
168 assert( m_arr[nIndex] != nullptr );
170 *m_arr[nIndex] = hptr;
173 /// Returns pointer to hazard pointer of index \p nIndex (0 <= \p nIndex < \p Count)
174 hp_guard* operator []( size_t nIndex ) CDS_NOEXCEPT
176 assert( nIndex < capacity());
177 return m_arr[nIndex];
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
183 assert( nIndex < capacity());
184 return m_arr[nIndex];
187 /// Clears (sets to \p nullptr) hazard pointer \p nIndex
188 void clear( size_t nIndex ) CDS_NOEXCEPT
190 assert( nIndex < capacity());
191 assert( m_arr[nIndex] != nullptr );
193 m_arr[ nIndex ]->clear();
196 hp_guard* release( size_t nIndex ) CDS_NOEXCEPT
198 assert( nIndex < capacity() );
200 hp_guard* p = m_arr[ nIndex ];
201 m_arr[ nIndex ] = nullptr;
207 hp_guard* m_arr[c_nCapacity]; ///< Hazard pointer array of size = \p Count
210 /// Allocator of hazard pointers for the thread
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
216 Each allocator object is thread-private.
219 \li Allocator - memory allocator class, default is \ref CDS_DEFAULT_ALLOCATOR
221 This helper class should not be used directly.
223 template <class Allocator = CDS_DEFAULT_ALLOCATOR >
227 typedef hazard_pointer hazard_ptr; ///< type of hazard pointer
228 typedef Allocator allocator_type; ///< allocator type
231 typedef cds::details::Allocator< hp_guard, allocator_type > allocator_impl;
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
239 explicit hp_allocator(
240 size_t nCapacity ///< max count of hazard pointer per thread
242 : m_arrHazardPtr( alloc_array( nCapacity ))
243 , m_FreeListHead( m_arrHazardPtr )
244 , m_nCapacity( nCapacity )
252 allocator_impl().Delete( m_arrHazardPtr, capacity() );
255 /// Get capacity of array
256 size_t capacity() const CDS_NOEXCEPT
261 /// Get size of array. The size is equal to the capacity of array
262 size_t size() const CDS_NOEXCEPT
267 /// Checks if all items are allocated
268 bool full() const CDS_NOEXCEPT
270 return m_FreeListHead == nullptr;
273 /// Allocates hazard pointer
278 hp_guard* p = m_FreeListHead;
279 m_FreeListHead = m_FreeListHead->m_next;
283 /// Frees previously allocated hazard pointer
284 void free( hp_guard* hp ) CDS_NOEXCEPT
288 hp->m_next = m_FreeListHead;
293 /// Allocates hazard pointers array
295 Allocates \p Count hazard pointers from array \p m_arrHazardPtr
296 Initializes \p arr with hazard pointers.
298 @return actual size of allocated array.
300 template <size_t Count>
301 size_t alloc( hp_array<Count>& arr )
304 hp_guard* p = m_FreeListHead;
305 for ( i = 0; i < Count && p; ++i ) {
310 for ( ; i < Count; ++i )
311 arr.m_arr[i] = nullptr;
316 /// Frees hazard pointer array
318 Frees the array of hazard pointers allocated by previous call \p this->alloc.
320 template <size_t Count>
321 void free( hp_array<Count> const& arr ) CDS_NOEXCEPT
323 hp_guard* pList = m_FreeListHead;
324 for ( size_t i = 0; i < Count; ++i ) {
325 hp_guard* p = arr[i];
332 m_FreeListHead = pList;
335 /// Makes all HP free
336 void clear() CDS_NOEXCEPT
338 for ( size_t i = 0; i < capacity(); ++i )
339 m_arrHazardPtr[i].clear();
342 /// Returns i-th hazard pointer
343 hp_guard& operator []( size_t i ) CDS_NOEXCEPT
345 assert( i < capacity() );
346 return m_arrHazardPtr[i];
350 hp_guard* alloc_array( size_t nCapacity )
352 return allocator_impl().NewArray( nCapacity );
355 void build_free_list()
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;
364 prev->m_next = nullptr;
365 m_FreeListHead = m_arrHazardPtr;
369 }}} // namespace gc::hp::details
373 #endif // #ifndef CDSLIB_GC_DETAILS_HP_ALLOC_H