X-Git-Url: http://plrg.eecs.uci.edu/git/?p=libcds.git;a=blobdiff_plain;f=cds%2Fgc%2Fimpl%2Fhp_decl.h;h=bffc52687ad8139178050d7d72aee4dc9b13dbff;hp=4a0593a6cddc547e9edb65afdd572fed0112da22;hb=e9fda6acf3c6a28fb822cfe85d784682eb8dbbe0;hpb=7029b34e759d463d1b27962f9ccbd0769402a386 diff --git a/cds/gc/impl/hp_decl.h b/cds/gc/impl/hp_decl.h index 4a0593a6..bffc5268 100644 --- a/cds/gc/impl/hp_decl.h +++ b/cds/gc/impl/hp_decl.h @@ -21,6 +21,9 @@ namespace cds { namespace gc { - [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 + GC class \p %cds::gc::HP and its nested classes. Before use any HP-related class you must initialize HP garbage collector + 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 garbage collector. */ class HP @@ -87,6 +90,12 @@ namespace cds { namespace gc { Otherwise it detaches the current thread from Hazard Pointer GC. */ ~thread_gc() ; // inline in hp_impl.h + + public: // for internal use only!!! + //@cond + static cds::gc::hp::details::hp_guard& alloc_guard(); // inline in hp_impl.h + static void free_guard( cds::gc::hp::details::hp_guard& g ); // inline in hp_impl.h + //@endcond }; /// Hazard Pointer guard @@ -107,7 +116,7 @@ namespace cds { namespace gc { public: /// Default ctor - Guard() CDS_NOEXCEPT; // inline in hp_impl.h + Guard(); // inline in hp_impl.h //@cond Guard( Guard const& ) = delete; @@ -124,7 +133,7 @@ namespace cds { namespace gc { to the HP slot repeatedly until the guard's value equals \p toGuard */ template - T protect( atomics::atomic const& toGuard ) CDS_NOEXCEPT + T protect( atomics::atomic const& toGuard ) { T pCur = toGuard.load(atomics::memory_order_relaxed); T pRet; @@ -143,7 +152,7 @@ namespace cds { namespace gc { to the HP slot repeatedly until the guard's value equals \p toGuard. The function is useful for intrusive containers when \p toGuard is a node pointer - that should be converted to a pointer to the value type before protecting. + that should be converted to a pointer to the value before protecting. The parameter \p f of type Func is a functor that makes this conversion: \code struct functor { @@ -171,20 +180,20 @@ namespace cds { namespace gc { Can be used for a pointer that cannot be changed concurrently */ template - T * assign( T * p ) CDS_NOEXCEPT + T * assign( T * p ) { return base_class::operator =(p); } //@cond - std::nullptr_t assign( std::nullptr_t ) CDS_NOEXCEPT + std::nullptr_t assign( std::nullptr_t ) { return base_class::operator =(nullptr); } //@endcond /// Copy from \p src guard to \p this guard - void copy( Guard const& src ) CDS_NOEXCEPT + void copy( Guard const& src ) { assign( src.get_native() ); } @@ -195,26 +204,26 @@ namespace cds { namespace gc { Can be used for a marked pointer that cannot be changed concurrently. */ template - T * assign( cds::details::marked_ptr p ) CDS_NOEXCEPT + T * assign( cds::details::marked_ptr p ) { return base_class::operator =( p.ptr() ); } /// Clear value of the guard - void clear() CDS_NOEXCEPT + void clear() { assign( nullptr ); } /// Get the value currently protected template - T * get() const CDS_NOEXCEPT + T * get() const { return reinterpret_cast( get_native() ); } /// Get native hazard pointer stored - guarded_pointer get_native() const CDS_NOEXCEPT + guarded_pointer get_native() const { return base_class::get(); } @@ -244,7 +253,7 @@ namespace cds { namespace gc { public: /// Default ctor - GuardArray() CDS_NOEXCEPT; // inline in hp_impl.h + GuardArray(); // inline in hp_impl.h //@cond GuardArray( GuardArray const& ) = delete; @@ -261,7 +270,7 @@ namespace cds { namespace gc { to the slot \p nIndex repeatedly until the guard's value equals \p toGuard */ template - T protect( size_t nIndex, atomics::atomic const& toGuard ) CDS_NOEXCEPT + T protect( size_t nIndex, atomics::atomic const& toGuard ) { T pRet; do { @@ -304,7 +313,7 @@ namespace cds { namespace gc { The function equals to a simple assignment, no loop is performed. */ template - T * assign( size_t nIndex, T * p ) CDS_NOEXCEPT + T * assign( size_t nIndex, T * p ) { base_class::set(nIndex, p); return p; @@ -316,49 +325,246 @@ namespace cds { namespace gc { Can be used for a marked pointer that cannot be changed concurrently. */ template - T * assign( size_t nIndex, cds::details::marked_ptr p ) CDS_NOEXCEPT + T * assign( size_t nIndex, cds::details::marked_ptr p ) { return assign( nIndex, p.ptr() ); } /// Copy guarded value from \p src guard to slot at index \p nIndex - void copy( size_t nIndex, Guard const& src ) CDS_NOEXCEPT + void copy( size_t nIndex, Guard const& src ) { assign( nIndex, src.get_native() ); } /// Copy guarded value from slot \p nSrcIndex to slot at index \p nDestIndex - void copy( size_t nDestIndex, size_t nSrcIndex ) CDS_NOEXCEPT + void copy( size_t nDestIndex, size_t nSrcIndex ) { assign( nDestIndex, get_native( nSrcIndex )); } /// Clear value of the slot \p nIndex - void clear( size_t nIndex ) CDS_NOEXCEPT + void clear( size_t nIndex ) { base_class::clear( nIndex ); } /// Get current value of slot \p nIndex template - T * get( size_t nIndex ) const CDS_NOEXCEPT + T * get( size_t nIndex ) const { return reinterpret_cast( get_native( nIndex ) ); } /// Get native hazard pointer stored - guarded_pointer get_native( size_t nIndex ) const CDS_NOEXCEPT + guarded_pointer get_native( size_t nIndex ) const { return base_class::operator[](nIndex).get(); } /// Capacity of the guard array - static CDS_CONSTEXPR size_t capacity() CDS_NOEXCEPT + static CDS_CONSTEXPR size_t capacity() { return Count; } }; + /// Guarded pointer + /** + A guarded pointer is a pair of a pointer and GC's guard. + Usually, it is used for returning a pointer to the item from an lock-free container. + The guard prevents the pointer to be early disposed (freed) by GC. + After destructing \p %guarded_ptr object the pointer can be disposed (freed) automatically at any time. + + Template arguments: + - \p GuardedType - a type which the guard stores + - \p ValueType - a value type + - \p Cast - a functor for converting GuardedType* to ValueType*. Default is \p void (no casting). + + For intrusive containers, \p GuardedType is the same as \p ValueType and no casting is needed. + In such case the \p %guarded_ptr is: + @code + typedef cds::gc::HP::guarded_ptr< foo > intrusive_guarded_ptr; + @endcode + + For standard (non-intrusive) containers \p GuardedType is not the same as \p ValueType and casting is needed. + For example: + @code + struct foo { + int const key; + std::string value; + }; + + struct value_accessor { + std::string* operator()( foo* pFoo ) const + { + return &(pFoo->value); + } + }; + + // Guarded ptr + typedef cds::gc::HP::guarded_ptr< Foo, std::string, value_accessor > nonintrusive_guarded_ptr; + @endcode + + You don't need use this class directly. + All set/map container classes from \p libcds declare the typedef for \p %guarded_ptr with appropriate casting functor. + */ + template + class guarded_ptr + { + //@cond + struct trivial_cast { + ValueType * operator()( GuardedType * p ) const + { + return p; + } + }; + //@endcond + + public: + typedef GuardedType guarded_type; ///< Guarded type + typedef ValueType value_type; ///< Value type + + /// Functor for casting \p guarded_type to \p value_type + typedef typename std::conditional< std::is_same::value, trivial_cast, Cast >::type value_cast; + + //@cond + typedef cds::gc::hp::details::hp_guard native_guard; + //@endcond + + private: + //@cond + native_guard * m_pGuard; + //@endcond + + public: + /// Creates empty guarded pointer + guarded_ptr() CDS_NOEXCEPT + : m_pGuard(nullptr) + {} + + //@cond + /// Initializes guarded pointer with \p p + explicit guarded_ptr( guarded_type * p ) CDS_NOEXCEPT + { + alloc_guard(); + assert( m_pGuard ); + m_pGuard->set(p); + } + explicit guarded_ptr( std::nullptr_t ) CDS_NOEXCEPT + : m_pGuard( nullptr ) + {} + //@endcond + + /// Move ctor + guarded_ptr( guarded_ptr&& gp ) CDS_NOEXCEPT + : m_pGuard( gp.m_pGuard ) + { + gp.m_pGuard = nullptr; + } + + /// The guarded pointer is not copy-constructible + guarded_ptr( guarded_ptr const& gp ) = delete; + + /// Clears the guarded pointer + /** + \ref release is called if guarded pointer is not \ref empty + */ + ~guarded_ptr() CDS_NOEXCEPT + { + free_guard(); + } + + /// Move-assignment operator + guarded_ptr& operator=( guarded_ptr&& gp ) CDS_NOEXCEPT + { + // Hazard Pointer array is organized as a stack + if ( m_pGuard && m_pGuard > gp.m_pGuard ) { + m_pGuard->set( gp.m_pGuard->get(atomics::memory_order_relaxed) ); + gp.free_guard(); + } + else { + free_guard(); + m_pGuard = gp.m_pGuard; + gp.m_pGuard = nullptr; + } + return *this; + } + + /// The guarded pointer is not copy-assignable + guarded_ptr& operator=(guarded_ptr const& gp) = delete; + + /// Returns a pointer to guarded value + value_type * operator ->() const CDS_NOEXCEPT + { + assert( !empty() ); + return value_cast()( reinterpret_cast(m_pGuard->get())); + } + + /// Returns a reference to guarded value + value_type& operator *() CDS_NOEXCEPT + { + assert( !empty()); + return *value_cast()(reinterpret_cast(m_pGuard->get())); + } + + /// Returns const reference to guarded value + value_type const& operator *() const CDS_NOEXCEPT + { + assert( !empty() ); + return *value_cast()(reinterpret_cast(m_pGuard->get())); + } + + /// Checks if the guarded pointer is \p nullptr + bool empty() const CDS_NOEXCEPT + { + return !m_pGuard || m_pGuard->get( atomics::memory_order_relaxed ) == nullptr; + } + + /// \p bool operator returns !empty() + explicit operator bool() const CDS_NOEXCEPT + { + return !empty(); + } + + /// Clears guarded pointer + /** + If the guarded pointer has been released, the pointer can be disposed (freed) at any time. + Dereferncing the guarded pointer after \p release() is dangerous. + */ + void release() CDS_NOEXCEPT + { + if ( m_pGuard ) + m_pGuard->clear(); + } + + //@cond + // For internal use only!!! + native_guard& guard() CDS_NOEXCEPT + { + alloc_guard(); + assert( m_pGuard ); + return *m_pGuard; + } + //@endcond + + private: + //@cond + void alloc_guard() + { + if ( !m_pGuard ) + m_pGuard = &thread_gc::alloc_guard(); + } + + void free_guard() + { + if ( m_pGuard ) { + thread_gc::free_guard( *m_pGuard ); + m_pGuard = nullptr; + } + } + //@endcond + }; + public: /// \p scan() type enum class scan_type { @@ -444,7 +650,7 @@ namespace cds { namespace gc { Deleting the pointer is the function \p pFunc call. */ template - static void retire( T * p, void (* pFunc)(T *) ) ; // inline in hp_impl.h + static void retire( T * p, void (* pFunc)(T *) ); // inline in hp_impl.h /// Retire pointer \p p with functor of type \p Disposer /** @@ -496,7 +702,7 @@ namespace cds { namespace gc { \endcode */ template - static void retire( T * p ) ; // inline in hp_impl.h + static void retire( T * p ); // inline in hp_impl.h /// Get current scan strategy static scan_type getScanType()