cds::gc::DHP details bugfix
[libcds.git] / cds / gc / impl / dhp_decl.h
1 //$$CDS-header$$
2
3 #ifndef __CDS_GC_IMPL_DHP_DECL_H
4 #define __CDS_GC_IMPL_DHP_DECL_H
5
6 #include <cds/gc/details/dhp.h>
7 #include <cds/details/marked_ptr.h>
8 #include <cds/details/static_functor.h>
9
10 namespace cds { namespace gc {
11
12     /// Dynamic Hazard Pointer garbage collector
13     /**  @ingroup cds_garbage_collector
14         @headerfile cds/gc/dhp.h
15
16         Implementation of Dynamic Hazard Pointer garbage collector.
17
18         Sources:
19             - [2002] Maged M.Michael "Safe memory reclamation for dynamic lock-freeobjects using atomic reads and writes"
20             - [2003] Maged M.Michael "Hazard Pointers: Safe memory reclamation for lock-free objects"
21             - [2004] Andrei Alexandrescy, Maged Michael "Lock-free Data Structures with Hazard Pointers"
22
23         Dynamic Hazard Pointers SMR (safe memory reclamation) provides an unbounded number of hazard pointer per thread
24         despite of classic Hazard Pointer SMR in which the count of the hazard pointef per thread is limited.
25
26         See \ref cds_how_to_use "How to use" section for details how to apply garbage collector.
27     */
28     class DHP
29     {
30     public:
31         /// Native guarded pointer type
32         /**
33             @headerfile cds/gc/dhp.h
34         */
35         typedef void * guarded_pointer;
36
37         /// Atomic reference
38         /**
39             @headerfile cds/gc/dhp.h
40         */
41         template <typename T> using atomic_ref = atomics::atomic<T *>;
42
43         /// Atomic type
44         /**
45             @headerfile cds/gc/dhp.h
46         */
47         template <typename T> using atomic_type = atomics::atomic<T>;
48
49         /// Atomic marked pointer
50         /**
51             @headerfile cds/gc/dhp.h
52         */
53         template <typename MarkedPtr> using atomic_marked_ptr = atomics::atomic<MarkedPtr>;
54
55         /// Thread GC implementation for internal usage
56         /**
57             @headerfile cds/gc/dhp.h
58         */
59         typedef dhp::ThreadGC   thread_gc_impl;
60
61         /// Thread-level garbage collector
62         /**
63             @headerfile cds/gc/dhp.h
64             This class performs automatically attaching/detaching Dynamic Hazard Pointer GC
65             for the current thread.
66         */
67         class thread_gc: public thread_gc_impl
68         {
69             //@cond
70             bool    m_bPersistent;
71             //@endcond
72         public:
73             /// Constructor
74             /**
75                 The constructor attaches the current thread to the Dynamic Hazard Pointer GC
76                 if it is not yet attached.
77                 The \p bPersistent parameter specifies attachment persistence:
78                 - \p true - the class destructor will not detach the thread from Dynamic Hazard Pointer GC.
79                 - \p false (default) - the class destructor will detach the thread from Dynamic Hazard Pointer GC.
80             */
81             thread_gc(
82                 bool    bPersistent = false
83             )   ;   // inline in dhp_impl.h
84
85             /// Destructor
86             /**
87                 If the object has been created in persistent mode, the destructor does nothing.
88                 Otherwise it detaches the current thread from Dynamic Hazard Pointer GC.
89             */
90             ~thread_gc()    ;   // inline in dhp_impl.h
91
92         public: // for internal use only!!!
93             //@cond
94             static void alloc_guard( cds::gc::dhp::details::guard& g ); // inline in dhp_impl.h
95             static void free_guard( cds::gc::dhp::details::guard& g ); // inline in dhp_impl.h
96             //@endcond
97         };
98
99
100         /// Dynamic Hazard Pointer guard
101         /**
102             @headerfile cds/gc/dhp.h
103
104             A guard is the hazard pointer.
105             Additionally, the \p %Guard class manages allocation and deallocation of the hazard pointer
106
107             A \p %Guard object is not copy- and move-constructible
108             and not copy- and move-assignable.
109         */
110         class Guard: public dhp::Guard
111         {
112             //@cond
113             typedef dhp::Guard base_class;
114             //@endcond
115
116         public: // for internal use only
117             //@cond
118             typedef cds::gc::dhp::details::guard native_guard;
119             //@endcond
120
121         public:
122             // Default ctor
123             Guard();   // inline in dhp_impl.h
124
125             //@cond
126             Guard( Guard const& ) = delete;
127             Guard( Guard&& s ) = delete;
128             Guard& operator=(Guard const&) = delete;
129             Guard& operator=(Guard&&) = delete;
130             //@endcond
131
132             /// Protects a pointer of type <tt> atomic<T*> </tt>
133             /**
134                 Return the value of \p toGuard
135
136                 The function tries to load \p toGuard and to store it
137                 to the HP slot repeatedly until the guard's value equals \p toGuard
138             */
139             template <typename T>
140             T protect( atomics::atomic<T> const& toGuard )
141             {
142                 T pCur = toGuard.load(atomics::memory_order_relaxed);
143                 T pRet;
144                 do {
145                     pRet = assign( pCur );
146                     pCur = toGuard.load(atomics::memory_order_acquire);
147                 } while ( pRet != pCur );
148                 return pCur;
149             }
150
151             /// Protects a converted pointer of type <tt> atomic<T*> </tt>
152             /**
153                 Return the value of \p toGuard
154
155                 The function tries to load \p toGuard and to store result of \p f functor
156                 to the HP slot repeatedly until the guard's value equals \p toGuard.
157
158                 The function is useful for intrusive containers when \p toGuard is a node pointer
159                 that should be converted to a pointer to the value type before guarding.
160                 The parameter \p f of type Func is a functor that makes this conversion:
161                 \code
162                     struct functor {
163                         value_type * operator()( T * p );
164                     };
165                 \endcode
166                 Really, the result of <tt> f( toGuard.load() ) </tt> is assigned to the hazard pointer.
167             */
168             template <typename T, class Func>
169             T protect( atomics::atomic<T> const& toGuard, Func f )
170             {
171                 T pCur = toGuard.load(atomics::memory_order_relaxed);
172                 T pRet;
173                 do {
174                     pRet = pCur;
175                     assign( f( pCur ) );
176                     pCur = toGuard.load(atomics::memory_order_acquire);
177                 } while ( pRet != pCur );
178                 return pCur;
179             }
180
181             /// Store \p p to the guard
182             /**
183                 The function is just an assignment, no loop is performed.
184                 Can be used for a pointer that cannot be changed concurrently
185                 or for already guarded pointer.
186             */
187             template <typename T>
188             T * assign( T * p )
189             {
190                 return base_class::operator =(p);
191             }
192
193             //@cond
194             std::nullptr_t assign( std::nullptr_t )
195             {
196                 return base_class::operator =(nullptr);
197             }
198             //@endcond
199
200             /// Store marked pointer \p p to the guard
201             /**
202                 The function is just an assignment of <tt>p.ptr()</tt>, no loop is performed.
203                 Can be used for a marked pointer that cannot be changed concurrently
204                 or for already guarded pointer.
205             */
206             template <typename T, int BITMASK>
207             T * assign( cds::details::marked_ptr<T, BITMASK> p )
208             {
209                 return base_class::operator =( p.ptr() );
210             }
211
212             /// Copy from \p src guard to \p this guard
213             void copy( Guard const& src )
214             {
215                 assign( src.get_native() );
216             }
217
218             /// Clears value of the guard
219             void clear()
220             {
221                 base_class::clear();
222             }
223
224             /// Gets the value currently protected (relaxed read)
225             template <typename T>
226             T * get() const
227             {
228                 return reinterpret_cast<T *>( get_native() );
229             }
230
231             /// Gets native guarded pointer stored
232             guarded_pointer get_native() const
233             {
234                 return base_class::get_guard()->pPost.load(atomics::memory_order_relaxed);
235             }
236         };
237
238         /// Array of Dynamic Hazard Pointer guards
239         /**
240             @headerfile cds/gc/dhp.h
241             The class is intended for allocating an array of hazard pointer guards.
242             Template parameter \p Count defines the size of the array.
243
244             A \p %GuardArray object is not copy- and move-constructible
245             and not copy- and move-assignable.
246         */
247         template <size_t Count>
248         class GuardArray: public dhp::GuardArray<Count>
249         {
250             //@cond
251             typedef dhp::GuardArray<Count> base_class;
252             //@endcond
253         public:
254             /// Rebind array for other size \p OtherCount
255             template <size_t OtherCount>
256             struct rebind {
257                 typedef GuardArray<OtherCount>  other   ;   ///< rebinding result
258             };
259
260         public:
261             // Default ctor
262             GuardArray();   // inline in dhp_impl.h
263
264             //@cond
265             GuardArray( GuardArray const& ) = delete;
266             GuardArray( GuardArray&& ) = delete;
267             GuardArray& operator=(GuardArray const&) = delete;
268             GuardArray& operator-(GuardArray&&) = delete;
269             //@endcond
270
271             /// Protects a pointer of type \p atomic<T*>
272             /**
273                 Return the value of \p toGuard
274
275                 The function tries to load \p toGuard and to store it
276                 to the slot \p nIndex repeatedly until the guard's value equals \p toGuard
277             */
278             template <typename T>
279             T protect( size_t nIndex, atomics::atomic<T> const& toGuard )
280             {
281                 T pRet;
282                 do {
283                     pRet = assign( nIndex, toGuard.load(atomics::memory_order_relaxed) );
284                 } while ( pRet != toGuard.load(atomics::memory_order_acquire));
285
286                 return pRet;
287             }
288
289             /// Protects a pointer of type \p atomic<T*>
290             /**
291                 Return the value of \p toGuard
292
293                 The function tries to load \p toGuard and to store it
294                 to the slot \p nIndex repeatedly until the guard's value equals \p toGuard
295
296                 The function is useful for intrusive containers when \p toGuard is a node pointer
297                 that should be converted to a pointer to the value type before guarding.
298                 The parameter \p f of type Func is a functor to make that conversion:
299                 \code
300                     struct functor {
301                         value_type * operator()( T * p );
302                     };
303                 \endcode
304                 Actually, the result of <tt> f( toGuard.load() ) </tt> is assigned to the hazard pointer.
305             */
306             template <typename T, class Func>
307             T protect( size_t nIndex, atomics::atomic<T> const& toGuard, Func f )
308             {
309                 T pRet;
310                 do {
311                     assign( nIndex, f( pRet = toGuard.load(atomics::memory_order_relaxed) ));
312                 } while ( pRet != toGuard.load(atomics::memory_order_acquire));
313
314                 return pRet;
315             }
316
317             /// Store \p p to the slot \p nIndex
318             /**
319                 The function is just an assignment, no loop is performed.
320             */
321             template <typename T>
322             T * assign( size_t nIndex, T * p )
323             {
324                 base_class::set(nIndex, p);
325                 return p;
326             }
327
328             /// Store marked pointer \p p to the guard
329             /**
330                 The function is just an assignment of <tt>p.ptr()</tt>, no loop is performed.
331                 Can be used for a marked pointer that cannot be changed concurrently
332                 or for already guarded pointer.
333             */
334             template <typename T, int Bitmask>
335             T * assign( size_t nIndex, cds::details::marked_ptr<T, Bitmask> p )
336             {
337                 return assign( nIndex, p.ptr() );
338             }
339
340             /// Copy guarded value from \p src guard to slot at index \p nIndex
341             void copy( size_t nIndex, Guard const& src )
342             {
343                 assign( nIndex, src.get_native() );
344             }
345
346             /// Copy guarded value from slot \p nSrcIndex to slot at index \p nDestIndex
347             void copy( size_t nDestIndex, size_t nSrcIndex )
348             {
349                 assign( nDestIndex, get_native( nSrcIndex ));
350             }
351
352             /// Clear value of the slot \p nIndex
353             void clear( size_t nIndex )
354             {
355                 base_class::clear( nIndex );
356             }
357
358             /// Get current value of slot \p nIndex
359             template <typename T>
360             T * get( size_t nIndex ) const
361             {
362                 return reinterpret_cast<T *>( get_native( nIndex ) );
363             }
364
365             /// Get native guarded pointer stored
366             guarded_pointer get_native( size_t nIndex ) const
367             {
368                 return base_class::operator[](nIndex).get_guard()->pPost.load(atomics::memory_order_relaxed);
369             }
370
371             /// Capacity of the guard array
372             static CDS_CONSTEXPR size_t capacity()
373             {
374                 return Count;
375             }
376         };
377
378         /// Guarded pointer
379         /**
380             A guarded pointer is a pair of a pointer and GC's guard.
381             Usually, it is used for returning a pointer to the item from an lock-free container.
382             The guard prevents the pointer to be early disposed (freed) by GC.
383             After destructing \p %guarded_ptr object the pointer can be disposed (freed) automatically at any time.
384
385             Template arguments:
386             - \p GuardedType - a type which the guard stores
387             - \p ValueType - a value type
388             - \p Cast - a functor for converting <tt>GuardedType*</tt> to <tt>ValueType*</tt>. Default is \p void (no casting).
389
390             For intrusive containers, \p GuardedType is the same as \p ValueType and no casting is needed.
391             In such case the \p %guarded_ptr is:
392             @code
393             typedef cds::gc::DHP::guarded_ptr< foo > intrusive_guarded_ptr;
394             @endcode
395
396             For standard (non-intrusive) containers \p GuardedType is not the same as \p ValueType and casting is needed.
397             For example:
398             @code
399             struct foo {
400                 int const   key;
401                 std::string value;
402             };
403
404             struct value_accessor {
405                 std::string* operator()( foo* pFoo ) const
406                 {
407                     return &(pFoo->value);
408                 }
409             };
410
411             // Guarded ptr
412             typedef cds::gc::DHP::guarded_ptr< Foo, std::string, value_accessor > nonintrusive_guarded_ptr;
413             @endcode
414
415             You don't need use this class directly.
416             All set/map container classes from \p libcds declare the typedef for \p %guarded_ptr with appropriate casting functor.
417         */
418         template <typename GuardedType, typename ValueType=GuardedType, typename Cast=void >
419         class guarded_ptr
420         {
421             //@cond
422             struct trivial_cast {
423                 ValueType * operator()( GuardedType * p ) const
424                 {
425                     return p;
426                 }
427             };
428             //@endcond
429
430         public:
431             typedef GuardedType guarded_type; ///< Guarded type
432             typedef ValueType   value_type;   ///< Value type
433
434             /// Functor for casting \p guarded_type to \p value_type
435             typedef typename std::conditional< std::is_same<Cast, void>::value, trivial_cast, Cast >::type value_cast;
436
437             //@cond
438             typedef cds::gc::dhp::details::guard native_guard;
439             //@endcond
440
441         private:
442             //@cond
443             native_guard    m_guard;
444             //@endcond
445
446         public:
447             /// Creates empty guarded pointer
448             guarded_ptr() CDS_NOEXCEPT
449             {}
450
451             //@cond
452             /// Initializes guarded pointer with \p p
453             explicit guarded_ptr( guarded_type * p ) CDS_NOEXCEPT
454             {
455                 alloc_guard();
456                 assert( m_guard.is_initialized() );
457                 m_guard.set( p );
458             }
459             explicit guarded_ptr( std::nullptr_t ) CDS_NOEXCEPT
460             {}
461             //@endcond
462
463             /// Move ctor
464             guarded_ptr( guarded_ptr&& gp ) CDS_NOEXCEPT
465             {
466                 m_guard.set_guard( gp.m_guard.release_guard() );
467             }
468
469             /// The guarded pointer is not copy-constructible
470             guarded_ptr( guarded_ptr const& gp ) = delete;
471
472             /// Clears the guarded pointer
473             /**
474                 \ref release is called if guarded pointer is not \ref empty
475             */
476             ~guarded_ptr() CDS_NOEXCEPT
477             {
478                 free_guard();
479             }
480
481             /// Move-assignment operator
482             guarded_ptr& operator=( guarded_ptr&& gp ) CDS_NOEXCEPT
483             {
484                 free_guard();
485                 m_guard.set_guard( gp.m_guard.release_guard() );
486                 return *this;
487             }
488
489             /// The guarded pointer is not copy-assignable
490             guarded_ptr& operator=(guarded_ptr const& gp) = delete;
491
492             /// Returns a pointer to guarded value
493             value_type * operator ->() const CDS_NOEXCEPT
494             {
495                 assert( !empty() );
496                 return value_cast()( reinterpret_cast<guarded_type *>(m_guard.get()));
497             }
498
499             /// Returns a reference to guarded value
500             value_type& operator *() CDS_NOEXCEPT
501             {
502                 assert( !empty());
503                 return *value_cast()(reinterpret_cast<guarded_type *>(m_guard.get()));
504             }
505
506             /// Returns const reference to guarded value
507             value_type const& operator *() const CDS_NOEXCEPT
508             {
509                 assert( !empty() );
510                 return *value_cast()(reinterpret_cast<guarded_type *>(m_guard.get()));
511             }
512
513             /// Checks if the guarded pointer is \p nullptr
514             bool empty() const CDS_NOEXCEPT
515             {
516                 return !m_guard.is_initialized() || m_guard.get() == nullptr;
517             }
518
519             /// \p bool operator returns <tt>!empty()</tt>
520             explicit operator bool() const CDS_NOEXCEPT
521             {
522                 return !empty();
523             }
524
525             /// Clears guarded pointer
526             /**
527                 If the guarded pointer has been released, the pointer can be disposed (freed) at any time.
528                 Dereferncing the guarded pointer after \p release() is dangerous.
529             */
530             void release() CDS_NOEXCEPT
531             {
532                 if ( m_guard.is_initialized() )
533                     m_guard.clear();
534             }
535
536             //@cond
537             // For internal use only!!!
538             native_guard& guard() CDS_NOEXCEPT
539             {
540                 alloc_guard();
541                 assert( m_guard.is_initialized() );
542                 return m_guard;
543             }
544             //@endcond
545
546         private:
547             //@cond
548             void alloc_guard()
549             {
550                 if ( !m_guard.is_initialized() )
551                     thread_gc::alloc_guard( m_guard );
552             }
553
554             void free_guard()
555             {
556                 if ( m_guard.is_initialized() )
557                     thread_gc::free_guard( m_guard );
558             }
559             //@endcond
560         };
561
562     public:
563         /// Initializes dhp::GarbageCollector singleton
564         /**
565             The constructor calls GarbageCollector::Construct with passed parameters.
566             See dhp::GarbageCollector::Construct for explanation of parameters meaning.
567         */
568         DHP(
569             size_t nLiberateThreshold = 1024
570             , size_t nInitialThreadGuardCount = 8
571         )
572         {
573             dhp::GarbageCollector::Construct(
574                 nLiberateThreshold,
575                 nInitialThreadGuardCount
576             );
577         }
578
579         /// Terminates dhp::GarbageCollector singleton
580         /**
581             The destructor calls \code dhp::GarbageCollector::Destruct() \endcode
582         */
583         ~DHP()
584         {
585             dhp::GarbageCollector::Destruct();
586         }
587
588         /// Checks if count of hazard pointer is no less than \p nCountNeeded
589         /**
590             The function always returns \p true since the guard count is unlimited for
591             \p gc::DHP garbage collector.
592         */
593         static CDS_CONSTEXPR bool check_available_guards( 
594 #ifdef CDS_DOXYGEN_INVOKED
595             size_t nCountNeeded, 
596 #else
597             size_t,
598 #endif
599             bool /*bRaiseException*/ = true )
600         {
601             return true;
602         }
603
604         /// Retire pointer \p p with function \p pFunc
605         /**
606             The function places pointer \p p to array of pointers ready for removing.
607             (so called retired pointer array). The pointer can be safely removed when no guarded pointer points to it.
608             Deleting the pointer is the function \p pFunc call.
609         */
610         template <typename T>
611         static void retire( T * p, void (* pFunc)(T *) )
612         {
613             dhp::GarbageCollector::instance().retirePtr( p, pFunc );
614         }
615
616         /// Retire pointer \p p with functor of type \p Disposer
617         /**
618             The function places pointer \p p to array of pointers ready for removing.
619             (so called retired pointer array). The pointer can be safely removed when no guarded pointer points to it.
620
621             See gc::HP::retire for \p Disposer requirements.
622         */
623         template <class Disposer, typename T>
624         static void retire( T * p )
625         {
626             retire( p, cds::details::static_functor<Disposer, T>::call );
627         }
628
629         /// Checks if Dynamic Hazard Pointer GC is constructed and may be used
630         static bool isUsed()
631         {
632             return dhp::GarbageCollector::isUsed();
633         }
634
635         /// Forced GC cycle call for current thread
636         /**
637             Usually, this function should not be called directly.
638         */
639         static void scan()  ;   // inline in dhp_impl.h
640
641         /// Synonym for \ref scan()
642         static void force_dispose()
643         {
644             scan();
645         }
646     };
647
648 }} // namespace cds::gc
649
650 #endif // #ifndef __CDS_GC_IMPL_DHP_DECL_H