From c83125f73b816802aa461bd6a59d5f69312e118e Mon Sep 17 00:00:00 2001 From: khizmax Date: Tue, 17 Jan 2017 22:59:07 +0300 Subject: [PATCH] Improved HP/DHP doc --- cds/gc/dhp_smr.h | 45 +++++++++++++++--------- cds/gc/hp.h | 43 ----------------------- cds/gc/hp_smr.h | 89 +++++++++++++++++++++++++++++++++++++----------- 3 files changed, 98 insertions(+), 79 deletions(-) diff --git a/cds/gc/dhp_smr.h b/cds/gc/dhp_smr.h index 7d0b5d7d..8e6f09d9 100644 --- a/cds/gc/dhp_smr.h +++ b/cds/gc/dhp_smr.h @@ -40,6 +40,8 @@ #include namespace cds { namespace gc { + + /// Dynamic (adaptive) Hazard Pointer implementation details namespace dhp { using namespace cds::gc::hp::common; @@ -47,11 +49,14 @@ namespace cds { namespace gc { class not_initialized: public std::runtime_error { public: + //@cond not_initialized() : std::runtime_error( "Global DHP SMR object is not initialized" ) {} + //@endcond }; + //@cond struct guard_block: public cds::intrusive::FreeListImpl::node { guard_block* next_; // next block in the thread list @@ -65,7 +70,9 @@ namespace cds { namespace gc { return reinterpret_cast( this + 1 ); } }; + //@endcond + //@cond /// \p guard_block allocator (global object) class hp_allocator { @@ -87,7 +94,9 @@ namespace cds { namespace gc { private: cds::intrusive::FreeListImpl free_list_; ///< list of free \p guard_block }; + //@endcond + //@cond /// Per-thread hazard pointer storage class thread_hp_storage { @@ -205,7 +214,9 @@ namespace cds { namespace gc { guard* const array_; ///< initial HP array size_t const initial_capacity_; ///< Capacity of \p array_ }; + //@endcond + //@cond struct retired_block: public cds::intrusive::FreeListImpl::node { retired_block* next_; ///< Next block in thread-private retired array @@ -226,7 +237,9 @@ namespace cds { namespace gc { return first() + c_capacity; } }; + //@endcond + //@cond class retired_allocator { friend class smr; @@ -248,7 +261,9 @@ namespace cds { namespace gc { private: cds::intrusive::FreeListImpl free_list_; ///< list of free \p guard_block }; + //@endcond + //@cond /// Per-thread retired array class retired_array { @@ -363,7 +378,9 @@ namespace cds { namespace gc { retired_block* list_tail_; size_t block_count_; }; + //@endcond + //@cond /// Per-thread data struct thread_data { thread_hp_storage hazards_; ///< Hazard pointers private to the thread @@ -389,8 +406,10 @@ namespace cds { namespace gc { sync_.fetch_add( 1, atomics::memory_order_acq_rel ); } }; + //@endcond - // Hazard Pointer SMR (Safe Memory Reclamation) + //@cond + // Dynmic (adaptive) Hazard Pointer SMR (Safe Memory Reclamation) class smr { struct thread_record; @@ -426,7 +445,6 @@ namespace cds { namespace gc { size_t nInitialHazardPtrCount = 16 ///< Initial number of hazard pointer per thread ); - //@cond // for back-copatibility static void Construct( size_t nInitialHazardPtrCount = 16 ///< Initial number of hazard pointer per thread @@ -434,7 +452,6 @@ namespace cds { namespace gc { { construct( nInitialHazardPtrCount ); } - //@endcond /// Destroys global instance of \ref smr /** @@ -447,15 +464,13 @@ namespace cds { namespace gc { bool bDetachAll = false ///< Detach all threads ); - //@cond - // for back-copatibility + // for back-compatibility static void Destruct( bool bDetachAll = false ///< Detach all threads ) { destruct( bDetachAll ); } - //@endcond /// Checks if global SMR object is constructed and may be used static bool isUsed() CDS_NOEXCEPT @@ -518,7 +533,6 @@ namespace cds { namespace gc { CDS_EXPORT_API void detach_all_thread(); private: - //@cond CDS_EXPORT_API thread_record* create_thread_data(); static CDS_EXPORT_API void destroy_thread_data( thread_record* pRec ); @@ -527,7 +541,6 @@ namespace cds { namespace gc { /// Free HP SMR thread-private data CDS_EXPORT_API void free_thread_data( thread_record* pRec ); - //@endcond private: static CDS_EXPORT_API smr* instance_; @@ -540,7 +553,9 @@ namespace cds { namespace gc { // temporaries std::atomic last_plist_size_; ///< HP array size in last scan() call }; + //@endcond + //@cond // for backward compatibility typedef smr GarbageCollector; @@ -555,25 +570,24 @@ namespace cds { namespace gc { { return smr::instance().get_retired_allocator(); } + //@endcond } // namespace dhp - /// Dynamic Hazard Pointer garbage collector + /// Dynamic (adaptie) Hazard Pointer SMR /** @ingroup cds_garbage_collector - @headerfile cds/gc/dhp.h - Implementation of Dynamic Hazard Pointer garbage collector. + Implementation of Dynamic (adaptive) Hazard Pointer SMR Sources: - [2002] Maged M.Michael "Safe memory reclamation for dynamic lock-freeobjects using atomic reads and writes" - [2003] Maged M.Michael "Hazard Pointers: Safe memory reclamation for lock-free objects" - [2004] Andrei Alexandrescy, Maged Michael "Lock-free Data Structures with Hazard Pointers" - Dynamic Hazard Pointers SMR (safe memory reclamation) provides an unbounded number of hazard pointer per thread - despite of classic Hazard Pointer SMR in which the count of the hazard pointef per thread is limited. + %DHP is an adaptive variant of classic \p cds::gc::HP, see @ref cds_garbage_collectors_comparison "Compare HP implementation" - See \ref cds_how_to_use "How to use" section for details how to apply garbage collector. + See \ref cds_how_to_use "How to use" section for details how to apply SMR. */ class DHP { @@ -1249,8 +1263,7 @@ namespace cds { namespace gc { @note This function may be called BEFORE creating an instance of Dynamic Hazard Pointer SMR - SMR object allocates some memory for thread-specific data and for - creating SMR object. + SMR object allocates some memory for thread-specific data and for creating SMR object. By default, a standard \p new and \p delete operators are used for this. */ static void set_memory_allocator( diff --git a/cds/gc/hp.h b/cds/gc/hp.h index e42fedb6..b1b3cb11 100644 --- a/cds/gc/hp.h +++ b/cds/gc/hp.h @@ -35,48 +35,5 @@ #include #include -/** - @page cds_garbage_collectors_comparison SMR (Safe Memory Reclamation schema) comparison - @ingroup cds_garbage_collector - - - - - - - - - - - - - - - - - - - - - - -
Feature%cds::gc::HP%cds::gc::DHP
Max number of guarded (hazard) pointers per threadlimited (specifies in SMR object ctor)unlimited (dynamically allocated when needed)
Max number of retired pointers1boundedbounded
Array of retired pointerspreallocated for each thread, size is limitedglobal for the entire process, unlimited (dynamically allocated when needed)
- - 1Unbounded count of retired pointer means a possibility of memory exhaustion. -*/ - -namespace cds { - - /// Different safe memory reclamation schemas (garbage collectors) - /** @ingroup cds_garbage_collector - - This namespace specifies different safe memory reclamation (SMR) algorithms. - See \ref cds_garbage_collector "Garbage collectors" - */ - namespace gc { - } // namespace gc - -} // namespace cds - #endif // #ifndef CDSLIB_GC_HP_H diff --git a/cds/gc/hp_smr.h b/cds/gc/hp_smr.h index 55111780..a9b28913 100644 --- a/cds/gc/hp_smr.h +++ b/cds/gc/hp_smr.h @@ -38,30 +38,80 @@ #include #include +/** + @page cds_garbage_collectors_comparison Hazard Pointer SMR implementations + @ingroup cds_garbage_collector + + + + + + + + + + + + + + + + + + + + + + +
Feature%cds::gc::HP%cds::gc::DHP
Max number of guarded (hazard) pointers per threadlimited (specified at construction time)unlimited (dynamically allocated when needed)
Max number of retired pointers1bounded, specified at construction timebounded, adaptive, depends on current thread count and number of hazard pointer for each thread
Thread countbounded, upper bound is specified at construction timeunbounded
+ + 1Unbounded count of retired pointers means a possibility of memory exhaustion. +*/ + +namespace cds { + /// @defgroup cds_garbage_collector Garbage collectors + + + /// Different safe memory reclamation schemas (garbage collectors) + /** @ingroup cds_garbage_collector + + This namespace specifies different safe memory reclamation (SMR) algorithms. + See \ref cds_garbage_collector "Garbage collectors" + */ + namespace gc { + } // namespace gc + +} // namespace cds + + namespace cds { namespace gc { + /// Hazard pointer implementation details namespace hp { using namespace cds::gc::hp::common; /// Exception "Not enough Hazard Pointer" class not_enought_hazard_ptr: public std::length_error { + //@cond public: - //@cond not_enought_hazard_ptr() : std::length_error( "Not enough Hazard Pointer" ) {} - //@endcond + //@endcond }; /// Exception "Hazard Pointer SMR is not initialized" class not_initialized: public std::runtime_error { + //@cond public: not_initialized() : std::runtime_error( "Global Hazard Pointer SMR object is not initialized" ) {} + //@endcond }; + //@cond /// Per-thread hazard pointer storage class thread_hp_storage { public: @@ -188,7 +238,9 @@ namespace cds { namespace gc { size_t free_guard_count_; # endif }; + //@endcond + //@cond /// Per-thread retired array class retired_array { @@ -256,8 +308,8 @@ namespace cds { namespace gc { public: size_t retire_call_count_; # endif - }; + //@endcond /// Internal statistics struct stat { @@ -270,11 +322,13 @@ namespace cds { namespace gc { size_t thread_rec_count; ///< Count of thread records + /// Default ctor stat() { clear(); } + /// Clears all counters void clear() { guard_allocated = @@ -287,6 +341,7 @@ namespace cds { namespace gc { } }; + //@cond /// Per-thread data struct thread_data { thread_hp_storage hazards_; ///< Hazard pointers private to the thread @@ -315,14 +370,16 @@ namespace cds { namespace gc { sync_.fetch_add( 1, atomics::memory_order_acq_rel ); } }; + //@endcond - /// smr::scan() strategy + /// \p smr::scan() strategy enum scan_type { classic, ///< classic scan as described in Michael's works (see smr::classic_scan() ) inplace ///< inplace scan without allocation (see smr::inplace_scan() ) }; - // Hazard Pointer SMR (Safe Memory Reclamation) + //@cond + /// Hazard Pointer SMR (Safe Memory Reclamation) class smr { struct thread_record; @@ -361,7 +418,6 @@ namespace cds { namespace gc { scan_type nScanType = inplace ///< Scan type (see \ref scan_type enum) ); - //@cond // for back-copatibility static void Construct( size_t nHazardPtrCount = 0, ///< Hazard pointer count per thread @@ -373,8 +429,6 @@ namespace cds { namespace gc { construct( nHazardPtrCount, nMaxThreadCount, nMaxRetiredPtrCount, nScanType ); } - //@endcond - /// Destroys global instance of \ref smr /** The parameter \p bDetachAll should be used carefully: if its value is \p true, @@ -386,15 +440,13 @@ namespace cds { namespace gc { bool bDetachAll = false ///< Detach all threads ); - //@cond - // for back-copatibility + // for back-compatibility static void Destruct( bool bDetachAll = false ///< Detach all threads ) { destruct( bDetachAll ); } - //@endcond /// Checks if global SMR object is constructed and may be used static bool isUsed() CDS_NOEXCEPT @@ -538,7 +590,6 @@ namespace cds { namespace gc { CDS_EXPORT_API void inplace_scan( thread_data* pRec ); private: - //@cond CDS_EXPORT_API thread_record* create_thread_data(); static CDS_EXPORT_API void destroy_thread_data( thread_record* pRec ); @@ -548,8 +599,6 @@ namespace cds { namespace gc { /// Free HP SMR thread-private data CDS_EXPORT_API void free_thread_data( thread_record* pRec ); - //@endcond - private: static CDS_EXPORT_API smr* instance_; @@ -561,27 +610,27 @@ namespace cds { namespace gc { scan_type const scan_type_; ///< scan type (see \ref scan_type enum) void ( smr::*scan_func_ )( thread_data* pRec ); }; + //@endcond + //@cond // for backward compatibility typedef smr GarbageCollector; + //@endcond } // namespace hp - - /// @defgroup cds_garbage_collector Garbage collectors - /// Hazard Pointer SMR (Safe Memory Reclamation) /** @ingroup cds_garbage_collector - Implementation of classic Hazard Pointer garbage collector. + Implementation of classic Hazard Pointer SMR Sources: - [2002] Maged M.Michael "Safe memory reclamation for dynamic lock-freeobjects using atomic reads and writes" - [2003] Maged M.Michael "Hazard Pointers: Safe memory reclamation for lock-free objects" - [2004] Andrei Alexandrescy, Maged Michael "Lock-free Data Structures with Hazard Pointers" - Hazard Pointer garbage collector is a singleton. The main user-level part of Hazard Pointer schema is - \p %cds::gc::HP class and its nested classes. Before use any HP-related class you must initialize HP + Hazard Pointer SMR is a singleton. The main user-level part of Hazard Pointer schema is + \p %cds::gc::HP class and its nested classes. Before use any HP-related class you must initialize \p %HP by contructing \p %cds::gc::HP object in beginning of your \p main(). See \ref cds_how_to_use "How to use" section for details how to apply SMR schema. */ -- 2.34.1