X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=cds%2Fgc%2Fimpl%2Fhp_decl.h;h=354ac6a80d7dfbb9bfdaa1340331dfd54bcf67f4;hb=7a70599883226459c97174848a1f53b307631eb7;hp=b42c44c1ae72df1655e8839233cf95142b0b6f7d;hpb=65ed182a3ae919d4e05fa4f6c353b91c60bfd15b;p=libcds.git diff --git a/cds/gc/impl/hp_decl.h b/cds/gc/impl/hp_decl.h index b42c44c1..354ac6a8 100644 --- a/cds/gc/impl/hp_decl.h +++ b/cds/gc/impl/hp_decl.h @@ -1,7 +1,35 @@ -//$$CDS-header$$ - -#ifndef __CDS_GC_IMPL_HP_DECL_H -#define __CDS_GC_IMPL_HP_DECL_H +/* + This file is a part of libcds - Concurrent Data Structures library + + (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016 + + Source code repo: http://github.com/khizmax/libcds/ + Download: http://sourceforge.net/projects/libcds/files/ + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright notice, this + list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE + FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ + +#ifndef CDSLIB_GC_IMPL_HP_DECL_H +#define CDSLIB_GC_IMPL_HP_DECL_H #include // overflow_error #include @@ -59,6 +87,9 @@ namespace cds { namespace gc { */ typedef hp::ThreadGC thread_gc_impl; + /// Exception "Too many Hazard Pointer" + typedef hp::GarbageCollector::too_many_hazard_ptr too_many_hazard_ptr_exception; + /// Wrapper for hp::ThreadGC class /** @headerfile cds/gc/hp.h @@ -90,34 +121,89 @@ 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 /** @headerfile cds/gc/hp.h - A guard is the hazard pointer. - Additionally, the \p %Guard class manages allocation and deallocation of the hazard pointer + A guard is a hazard pointer. + Additionally, the \p %Guard class manages allocation and deallocation of the hazard pointer. - A \p %Guard object is not copy- and move-constructible - and not copy- and move-assignable. + \p %Guard object is movable but not copyable. + + The guard object can be in two states: + - unlinked - the guard is not linked with any internal hazard pointer. + In this state no operation except \p link() and move assignment is supported. + - linked (default) - the guard allocates an internal hazard pointer and fully operable. + + Due to performance reason the implementation does not check state of the guard in runtime. + + @warning Move assignment can transfer the guard in unlinked state, use with care. */ - class Guard : public hp::guard + class Guard { - //@cond - typedef hp::guard base_class; - //@endcond - public: - /// Default ctor - Guard(); // inline in hp_impl.h + /// Default ctor allocates a guard (hazard pointer) from thread-private storage + /** + @warning Can throw \p too_many_hazard_ptr_exception if internal hazard pointer objects are exhausted. + */ + Guard(); // inline in hp_impl.h - //@cond + /// Initilalizes an unlinked guard i.e. the guard contains no hazard pointer. Used for move semantics support + explicit Guard( std::nullptr_t ) CDS_NOEXCEPT + : m_guard( nullptr ) + {} + + /// Move ctor - \p src guard becomes unlinked (transfer internal guard ownership) + Guard( Guard&& src ) CDS_NOEXCEPT + : m_guard( src.m_guard ) + { + src.m_guard = nullptr; + } + + /// Move assignment: the internal guards are swapped between \p src and \p this + /** + @warning \p src will become in unlinked state if \p this was unlinked on entry. + */ + Guard& operator=( Guard&& src ) CDS_NOEXCEPT + { + std::swap( m_guard, src.m_guard ); + return *this; + } + + /// Copy ctor is prohibited - the guard is not copyable Guard( Guard const& ) = delete; - Guard( Guard&& s ) = delete; - Guard& operator=(Guard const&) = delete; - Guard& operator=(Guard&&) = delete; - //@endcond + + /// Copy assignment is prohibited + Guard& operator=( Guard const& ) = delete; + + /// Frees the internal hazard pointer if the guard is in linked state + ~Guard() + { + unlink(); + } + + /// Checks if the guard object linked with any internal hazard pointer + bool is_linked() const + { + return m_guard != nullptr; + } + + /// Links the guard with internal hazard pointer if the guard is in unlinked state + /** + @warning Can throw \p too_many_hazard_ptr_exception if internal hazard pointer objects are exhausted. + */ + void link(); // inline in hp_impl.h + + /// Unlinks the guard from internal hazard pointer; the guard becomes in unlinked state + void unlink(); // inline in hp_impl.h /// Protects a pointer of type \p atomic /** @@ -125,11 +211,15 @@ namespace cds { namespace gc { The function tries to load \p toGuard and to store it to the HP slot repeatedly until the guard's value equals \p toGuard + + @warning The guad object should be in linked state, otherwise the result is undefined */ template T protect( atomics::atomic const& toGuard ) { - T pCur = toGuard.load(atomics::memory_order_relaxed); + assert( m_guard != nullptr ); + + T pCur = toGuard.load(atomics::memory_order_acquire); T pRet; do { pRet = assign( pCur ); @@ -146,19 +236,23 @@ 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 { value_type * operator()( T * p ); }; \endcode - Really, the result of f( toGuard.load() ) is assigned to the hazard pointer. + Actually, the result of f( toGuard.load() ) is assigned to the hazard pointer. + + @warning The guad object should be in linked state, otherwise the result is undefined */ template T protect( atomics::atomic const& toGuard, Func f ) { - T pCur = toGuard.load(atomics::memory_order_relaxed); + assert( m_guard != nullptr ); + + T pCur = toGuard.load(atomics::memory_order_acquire); T pRet; do { pRet = pCur; @@ -172,21 +266,21 @@ namespace cds { namespace gc { /** The function equals to a simple assignment the value \p p to guard, no loop is performed. Can be used for a pointer that cannot be changed concurrently + + @warning The guad object should be in linked state, otherwise the result is undefined */ template - T * assign( T * p ) - { - return base_class::operator =(p); - } + T * assign( T* p ); // inline in hp_impl.h //@cond std::nullptr_t assign( std::nullptr_t ) { - return base_class::operator =(nullptr); + assert(m_guard != nullptr ); + return *m_guard = nullptr; } //@endcond - /// Copy from \p src guard to \p this guard + /// Copy a value guarded from \p src guard to \p this guard (valid only in linked state) void copy( Guard const& src ) { assign( src.get_native() ); @@ -196,31 +290,48 @@ namespace cds { namespace gc { /** The function equals to a simple assignment of p.ptr(), no loop is performed. Can be used for a marked pointer that cannot be changed concurrently. + + @warning The guad object should be in linked state, otherwise the result is undefined */ template T * assign( cds::details::marked_ptr p ) { - return base_class::operator =( p.ptr() ); + return assign( p.ptr()); } - /// Clear value of the guard + /// Clear value of the guard (valid only in linked state) void clear() { assign( nullptr ); } - /// Get the value currently protected + /// Get the value currently protected (valid only in linked state) template T * get() const { return reinterpret_cast( get_native() ); } - /// Get native hazard pointer stored + /// Get native hazard pointer stored (valid only in linked state) guarded_pointer get_native() const { - return base_class::get(); + assert( m_guard != nullptr ); + return m_guard->get(); } + + //@cond + hp::details::hp_guard* release() + { + hp::details::hp_guard* g = m_guard; + m_guard = nullptr; + return g; + } + //@endcond + + private: + //@cond + hp::details::hp_guard* m_guard; + //@endcond }; /// Array of Hazard Pointer guards @@ -229,32 +340,38 @@ namespace cds { namespace gc { The class is intended for allocating an array of hazard pointer guards. Template parameter \p Count defines the size of the array. - A \p %GuardArray object is not copy- and move-constructible - and not copy- and move-assignable. */ template - class GuardArray : public hp::array + class GuardArray { - //@cond - typedef hp::array base_class; - //@endcond public: /// Rebind array for other size \p Count2 template struct rebind { - typedef GuardArray other ; ///< rebinding result + typedef GuardArray other; ///< rebinding result }; + /// Array capacity + static CDS_CONSTEXPR const size_t c_nCapacity = Count; + public: - /// Default ctor - GuardArray(); // inline in hp_impl.h + /// Default ctor allocates \p Count hazard pointers + GuardArray(); // inline in hp_impl.h - //@cond - GuardArray( GuardArray const& ) = delete; + /// Move ctor is prohibited GuardArray( GuardArray&& ) = delete; - GuardArray& operator=(GuardArray const&) = delete; - GuardArray& operator-(GuardArray&&) = delete; - //@endcond + + /// Move assignment is prohibited + GuardArray& operator=( GuardArray&& ) = delete; + + /// Copy ctor is prohibited + GuardArray( GuardArray const& ) = delete; + + /// Copy assignment is prohibited + GuardArray& operator=( GuardArray const& ) = delete; + + /// Frees allocated hazard pointers + ~GuardArray(); // inline in hp_impl.h /// Protects a pointer of type \p atomic /** @@ -266,9 +383,11 @@ namespace cds { namespace gc { template T protect( size_t nIndex, atomics::atomic const& toGuard ) { + assert( nIndex < capacity()); + T pRet; do { - pRet = assign( nIndex, toGuard.load(atomics::memory_order_relaxed) ); + pRet = assign( nIndex, toGuard.load(atomics::memory_order_acquire) ); } while ( pRet != toGuard.load(atomics::memory_order_acquire)); return pRet; @@ -294,9 +413,11 @@ namespace cds { namespace gc { template T protect( size_t nIndex, atomics::atomic const& toGuard, Func f ) { + assert( nIndex < capacity() ); + T pRet; do { - assign( nIndex, f( pRet = toGuard.load(atomics::memory_order_relaxed) )); + assign( nIndex, f( pRet = toGuard.load(atomics::memory_order_acquire) )); } while ( pRet != toGuard.load(atomics::memory_order_acquire)); return pRet; @@ -307,11 +428,7 @@ namespace cds { namespace gc { The function equals to a simple assignment, no loop is performed. */ template - T * assign( size_t nIndex, T * p ) - { - base_class::set(nIndex, p); - return p; - } + T * assign( size_t nIndex, T * p ); // inline in hp_impl.h /// Store marked pointer \p p to the guard /** @@ -339,7 +456,7 @@ namespace cds { namespace gc { /// Clear value of the slot \p nIndex void clear( size_t nIndex ) { - base_class::clear( nIndex ); + m_arr.clear( nIndex ); } /// Get current value of slot \p nIndex @@ -352,14 +469,235 @@ namespace cds { namespace gc { /// Get native hazard pointer stored guarded_pointer get_native( size_t nIndex ) const { - return base_class::operator[](nIndex).get(); + assert( nIndex < capacity() ); + return m_arr[nIndex]->get(); + } + + //@cond + hp::details::hp_guard* release( size_t nIndex ) CDS_NOEXCEPT + { + return m_arr.release( nIndex ); } + //@endcond /// Capacity of the guard array static CDS_CONSTEXPR size_t capacity() { - return Count; + return c_nCapacity; + } + + private: + //@cond + hp::details::hp_array m_arr; + //@endcond + }; + + /// 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; + } + }; + + template friend class guarded_ptr; + //@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; + + public: + /// Creates empty guarded pointer + guarded_ptr() CDS_NOEXCEPT + : m_pGuard(nullptr) + {} + + //@cond + explicit guarded_ptr( hp::details::hp_guard* g ) CDS_NOEXCEPT + : m_pGuard( g ) + {} + + /// Initializes guarded pointer with \p p + explicit guarded_ptr( guarded_type* p ) CDS_NOEXCEPT + : m_pGuard( nullptr ) + { + reset(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; + } + + /// Move ctor + template + guarded_ptr( guarded_ptr&& gp ) CDS_NOEXCEPT + : m_pGuard( gp.m_pGuard ) + { + gp.m_pGuard = nullptr; + } + + /// Ctor from \p Guard + explicit guarded_ptr( Guard&& g ) CDS_NOEXCEPT + : m_pGuard( g.release() ) + {} + + /// 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 + { + release(); + } + + /// Move-assignment operator + guarded_ptr& operator=( guarded_ptr&& gp ) CDS_NOEXCEPT + { + std::swap( m_pGuard, gp.m_pGuard ); + return *this; + } + + /// Move-assignment from \p Guard + guarded_ptr& operator=( Guard&& g ) CDS_NOEXCEPT + { + std::swap( m_pGuard, g.m_guard ); + 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 + { + free_guard(); + } + + //@cond + // For internal use only!!! + void reset(guarded_type * p) CDS_NOEXCEPT + { + alloc_guard(); + assert( m_pGuard ); + m_pGuard->set(p); + } + //@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 + + private: + //@cond + hp::details::hp_guard* m_pGuard; + //@endcond }; public: @@ -368,13 +706,13 @@ namespace cds { namespace gc { classic = hp::classic, ///< classic scan as described in Michael's papers inplace = hp::inplace ///< inplace scan without allocation }; - /// Initializes hp::GarbageCollector singleton + /// Initializes %HP singleton /** The constructor initializes GC singleton with passed parameters. If GC instance is not exist then the function creates the instance. Otherwise it does nothing. - The Michael's HP reclamation schema depends of three parameters: + The Michael's %HP reclamation schema depends of three parameters: - \p nHazardPtrCount - hazard pointer count per thread. Usually it is small number (up to 10) depending from the data structure algorithms. By default, if \p nHazardPtrCount = 0, the function uses maximum of the hazard pointer count for CDS library. @@ -399,7 +737,9 @@ namespace cds { namespace gc { /// Terminates GC singleton /** - The destructor calls \code hp::GarbageCollector::Destruct( true ) \endcode + The destructor destroys %HP global object. After calling of this function you may \b NOT + use CDS data structures based on \p %cds::gc::HP. + Usually, %HP object is destroyed at the end of your \p main(). */ ~HP() { @@ -408,7 +748,7 @@ namespace cds { namespace gc { /// Checks if count of hazard pointer is no less than \p nCountNeeded /** - If \p bRaiseException is \p true (that is the default), the function raises + If \p bRaiseException is \p true (that is the default), the function raises an \p std::overflow_error exception "Too few hazard pointers" if \p nCountNeeded is more than the count of hazard pointer per thread. */ @@ -535,4 +875,4 @@ namespace cds { namespace gc { }; }} // namespace cds::gc -#endif // #ifndef __CDS_GC_IMPL_HP_DECL_H +#endif // #ifndef CDSLIB_GC_IMPL_HP_DECL_H