From 478d6e9710642c4167f50ae1619c2a6f46b47ad7 Mon Sep 17 00:00:00 2001 From: khizmax Date: Sat, 23 May 2015 11:31:56 +0300 Subject: [PATCH] Added urcu::raw_ptr concept Applied urcu::raw_ptr to intrusive::MichaelList --- cds/intrusive/michael_list_rcu.h | 88 ++++++++-- cds/urcu/exempt_ptr.h | 1 + cds/urcu/raw_ptr.h | 176 ++++++++++++++++++++ projects/Win/vc12/cds.vcxproj | 1 + projects/Win/vc12/cds.vcxproj.filters | 3 + tests/test-hdr/list/hdr_intrusive_michael.h | 75 ++++----- 6 files changed, 288 insertions(+), 56 deletions(-) create mode 100644 cds/urcu/raw_ptr.h diff --git a/cds/intrusive/michael_list_rcu.h b/cds/intrusive/michael_list_rcu.h index e41d912c..e09ddafa 100644 --- a/cds/intrusive/michael_list_rcu.h +++ b/cds/intrusive/michael_list_rcu.h @@ -8,6 +8,7 @@ #include #include #include +#include namespace cds { namespace intrusive { @@ -150,6 +151,20 @@ namespace cds { namespace intrusive { gc::template retire_ptr( node_traits::to_value_ptr( *pNode ) ); } + static void dispose_chain( node_type * pChain ) + { + if ( pChain ) { + assert( !gc::is_locked() ); + + auto f = [&pChain]() -> cds::urcu::retired_ptr { + node_type * p = pChain; + pChain = p->m_pDelChain; + return cds::urcu::make_retired_ptr( node_traits::to_value_ptr( p )); + }; + gc::batch_retire(std::ref(f)); + } + } + /// Position pointer for item search struct position { atomic_node_ptr * pPrev ; ///< Previous node @@ -166,17 +181,7 @@ namespace cds { namespace intrusive { ~position() { - assert( !gc::is_locked() ); - - node_type * chain = pDelChain; - if ( chain ) { - auto f = [&chain]() -> cds::urcu::retired_ptr { - node_type * p = chain; - chain = p->m_pDelChain; - return cds::urcu::make_retired_ptr( node_traits::to_value_ptr( p )); - }; - gc::batch_retire(std::ref(f)); - } + dispose_chain( pDelChain ); } }; @@ -185,6 +190,49 @@ namespace cds { namespace intrusive { public: using exempt_ptr = cds::urcu::exempt_ptr< gc, value_type, value_type, clear_and_dispose, void >; ///< pointer to extracted node + private: + //@cond + struct raw_ptr_disposer + { + node_type * pReclaimedChain; + + raw_ptr_disposer() + : pReclaimedChain( nullptr ) + {} + + raw_ptr_disposer( position& pos ) + : pReclaimedChain( pos.pDelChain ) + { + pos.pDelChain = nullptr; + } + + raw_ptr_disposer( raw_ptr_disposer&& d ) + : pReclaimedChain( d.pReclaimedChain ) + { + d.pReclaimedChain = nullptr; + } + + raw_ptr_disposer( raw_ptr_disposer const& ) = delete; + + ~raw_ptr_disposer() + { + apply(); + } + + void apply() + { + if ( pReclaimedChain ) { + dispose_chain( pReclaimedChain ); + pReclaimedChain = nullptr; + } + } + }; + //@endcond + + public: + /// Result of \p get(), \p get_with() functions - pointer to the node found + typedef cds::urcu::raw_ptr< gc, value_type, raw_ptr_disposer > raw_ptr; + protected: //@cond @@ -720,7 +768,7 @@ namespace cds { namespace intrusive { \endcode */ template - value_type * get( Q const& key ) + raw_ptr get( Q const& key ) { return get_at( m_pHead, key, key_comparator()); } @@ -735,7 +783,7 @@ namespace cds { namespace intrusive { \p pred must imply the same element order as the comparator used for building the list. */ template - value_type * get_with( Q const& key, Less pred ) + raw_ptr get_with( Q const& key, Less pred ) { CDS_UNUSED( pred ); return get_at( m_pHead, key, cds::opt::details::make_comparator_from_less()); @@ -986,12 +1034,16 @@ namespace cds { namespace intrusive { } template - value_type * get_at( atomic_node_ptr& refHead, Q const& val, Compare cmp ) + raw_ptr get_at( atomic_node_ptr& refHead, Q const& val, Compare cmp ) { - value_type * pFound = nullptr; - return find_at( refHead, val, cmp, - [&pFound](value_type& found, Q const& ) { pFound = &found; } ) - ? pFound : nullptr; + // RCU should be locked! + assert(gc::is_locked() ); + + position pos( refHead ); + + if ( search( refHead, val, pos, cmp )) + return raw_ptr( node_traits::to_value_ptr( pos.pCur ), raw_ptr_disposer( pos )); + return raw_ptr( raw_ptr_disposer( pos )); } //@endcond diff --git a/cds/urcu/exempt_ptr.h b/cds/urcu/exempt_ptr.h index 05e96eca..6231da88 100644 --- a/cds/urcu/exempt_ptr.h +++ b/cds/urcu/exempt_ptr.h @@ -37,6 +37,7 @@ namespace cds { namespace urcu { For non-intrusive containers from \p cds::container namespace \p Disposer is usually an invocation of node deallocator. For intrusive containers the disposer can be empty or it can trigger an event "node can be reused safely". In any case, the exempt pointer concept keeps RCU semantics. + The destructor or \p release() should be called outside the RCU lock of current thread. You don't need use this helper class directly. Any RCU-based container typedefs a simplified version of this template. diff --git a/cds/urcu/raw_ptr.h b/cds/urcu/raw_ptr.h new file mode 100644 index 00000000..6455c9e7 --- /dev/null +++ b/cds/urcu/raw_ptr.h @@ -0,0 +1,176 @@ +//$$CDS-header$$ + +#ifndef CDSLIB_URCU_RAW_PTR_H +#define CDSLIB_URCU_RAW_PTR_H + +#include // std::move +#include +#include + +namespace cds { namespace urcu { + + /// Raw pointer to node of RCU-based container + /** + This class is intented for returning a pointer to node of RCU-based container. + The objects of \p %raw_ptr class is returned by functions like \p get() of that containers. + Those functions must be called only under RCU-lock, otherwise the node returned can be reclaimed. + On the other hand, traversing the container can remove a lot of nodes marked as deleted ones. + Since RCU is locked, such nodes cannot be reclaimed immediately and must be retired only + outside RCU lock. + + The object of \p %raw_ptr solves that problem: it contains the pointer to the node found + and a chain of nodes that be reclaimed during traversing. The \p %raw_ptr object destructor + frees the chain (but not the node found) passing it to RCU \p batch_retire(). + + The object of \p %raw_ptr class must be destructed only outside RCU-lock of current thread. + + Usually, you do not need to use \p %raw_ptr class directly. Each RCU container declares + a \p %raw_ptr typedef suitable for the container. + + Template arguments: + - \p RCU - one of \ref cds_urcu_gc "RCU type" + - \p ValueType - type of values stored in container + - \p ReclaimedEnumerator - implemntation-defined for each type of container + + Example: let \p Container is an RCU container + \code + Container c; + // ... + // Find a key + typename Container::raw_ptr pRaw; + + // RCU locked section + { + typename Container::rcu_lock l; + pRaw = c.get( key ); + if ( pRaw ) { + // Deal with pRaw + } + } + // Release outside RCU-lock + pRaw.release(); + \endcode + */ + template < + class RCU, + typename ValueType, + typename ReclaimedEnumerator + > + class raw_ptr + { + public: + typedef RCU rcu; ///< RCU type - one of cds::urcu::gc< ... > + typedef ValueType value_type; ///< Value type pointed by \p raw_ptr + typedef ReclaimedEnumerator reclaimed_enumerator; ///< implementation-defined, for internal use only + + private: + //@cond + value_type * m_ptr; ///< pointer to node + reclaimed_enumerator m_Enum; ///< reclaimed node enumerator + //@endcond + + public: + /// Constructs an empty raw pointer + raw_ptr() + : m_ptr( nullptr ) + {} + + /// Move ctor + raw_ptr( raw_ptr&& p ) + : m_ptr( p.m_ptr ) + , m_Enum(std::move( p.m_Enum )) + { + p.m_ptr = nullptr; + } + + /// Copy ctor is prohibited + raw_ptr( raw_ptr const& ) = delete; + + ///@cond + // Only for internal use + raw_ptr( value_type * p, reclaimed_enumerator&& e ) + : m_ptr( p ) + , m_Enum(std::move( e )) + {} + raw_ptr( reclaimed_enumerator&& e ) + : m_ptr( nullptr ) + , m_Enum(std::move( e )) + {} + //@endcond + + /// Releases the raw pointer + ~raw_ptr() + { + release(); + } + + public: + /// Move assignment operator + /** + This operator may be called only inside RCU-lock. + The \p this should be empty. + + In general, move assignment is intented for internal use. + */ + raw_ptr& operator=( raw_ptr&& p ) CDS_NOEXCEPT + { + assert( empty() ); + + m_ptr = p.m_ptr; + m_Enum = std::move( p.m_Enum ); + p.m_ptr = nullptr; + return *this; + } + + /// Copy assignment is prohibited + raw_ptr& operator=( raw_ptr const& ) = delete; + + /// Returns a pointer to stored value + value_type * operator ->() const CDS_NOEXCEPT + { + return m_ptr; + } + + /// Returns a reference to stored value + value_type& operator *() + { + assert( m_ptr != nullptr ); + return *m_ptr; + } + + /// Returns a reference to stored value + value_type const& operator *() const + { + assert( m_ptr != nullptr ); + return *m_ptr; + } + + /// Checks if the \p %raw_ptr is \p nullptr + bool empty() const CDS_NOEXCEPT + { + return m_ptr == nullptr; + } + + /// Checks if the \p %raw_ptr is not empty + explicit operator bool() const CDS_NOEXCEPT + { + return !empty(); + } + + /// Releases the \p %raw_ptr object + /** + This function may be called only outside RCU section. + After \p %release() the object can be reused. + */ + void release() + { + assert( !rcu::is_locked() ); + m_Enum.apply(); + m_ptr = nullptr; + } + }; + +}} // namespace cds::urcu + +#endif // #ifndef CDSLIB_URCU_RAW_PTR_H + diff --git a/projects/Win/vc12/cds.vcxproj b/projects/Win/vc12/cds.vcxproj index 6b981b47..b4290f9f 100644 --- a/projects/Win/vc12/cds.vcxproj +++ b/projects/Win/vc12/cds.vcxproj @@ -818,6 +818,7 @@ + diff --git a/projects/Win/vc12/cds.vcxproj.filters b/projects/Win/vc12/cds.vcxproj.filters index e2042f83..55201468 100644 --- a/projects/Win/vc12/cds.vcxproj.filters +++ b/projects/Win/vc12/cds.vcxproj.filters @@ -1181,5 +1181,8 @@ Header Files\cds\compiler + + Header Files\cds\urcu + \ No newline at end of file diff --git a/tests/test-hdr/list/hdr_intrusive_michael.h b/tests/test-hdr/list/hdr_intrusive_michael.h index c19f07bb..de018341 100644 --- a/tests/test-hdr/list/hdr_intrusive_michael.h +++ b/tests/test-hdr/list/hdr_intrusive_michael.h @@ -575,42 +575,42 @@ namespace ordlist { CPPUNIT_ASSERT( l.insert( arrItem[i] ) ); typename OrdList::exempt_ptr ep; + typename OrdList::raw_ptr rp; for ( int i = 0; i < nLimit; ++i ) { { rcu_lock lock; - value_type * pGet = l.get( a[i] ); - CPPUNIT_ASSERT( pGet != nullptr ); - CPPUNIT_CHECK( pGet->nKey == a[i] ); - CPPUNIT_CHECK( pGet->nVal == a[i] * 2 ); + rp = l.get( a[i] ); + CPPUNIT_ASSERT( rp ); + CPPUNIT_CHECK( rp->nKey == a[i] ); + CPPUNIT_CHECK( rp->nVal == a[i] * 2 ); } + rp.release(); - { - rcu_lock lock; - ep = l.extract( a[i] ); - CPPUNIT_ASSERT( ep ); - CPPUNIT_ASSERT( !ep.empty() ); - CPPUNIT_CHECK( ep->nKey == a[i] ); - CPPUNIT_CHECK( (*ep).nVal == a[i] * 2 ); - } + ep = l.extract( a[i] ); + CPPUNIT_ASSERT( ep ); + CPPUNIT_ASSERT( !ep.empty() ); + CPPUNIT_CHECK( ep->nKey == a[i] ); + CPPUNIT_CHECK( (*ep).nVal == a[i] * 2 ); ep.release(); { rcu_lock lock; - CPPUNIT_CHECK( l.get( a[i] ) == nullptr ); - CPPUNIT_CHECK( !l.extract( a[i] )); - CPPUNIT_CHECK( ep.empty() ); + CPPUNIT_CHECK( !l.get( a[i] )); } + CPPUNIT_CHECK( !l.extract( a[i] )); + CPPUNIT_CHECK( ep.empty() ); } CPPUNIT_ASSERT( l.empty() ); { rcu_lock lock; - CPPUNIT_CHECK( l.get( a[0] ) == nullptr ); - ep = l.extract( a[0] ); - CPPUNIT_CHECK( !ep ); - CPPUNIT_CHECK( ep.empty() ); + CPPUNIT_CHECK( !l.get( a[0] )); } + ep = l.extract( a[0] ); + CPPUNIT_CHECK( !ep ); + CPPUNIT_CHECK( ep.empty() ); + // Apply retired pointer OrdList::gc::force_dispose(); @@ -623,38 +623,37 @@ namespace ordlist { other_item itm( a[i] ); { rcu_lock lock; - value_type * pGet = l.get_with( itm, other_less() ); - CPPUNIT_ASSERT( pGet != nullptr ); - CPPUNIT_CHECK( pGet->nKey == a[i] ); - CPPUNIT_CHECK( pGet->nVal == a[i] * 2 ); + rp = l.get_with( itm, other_less() ); + CPPUNIT_ASSERT( rp ); + CPPUNIT_CHECK( rp->nKey == a[i] ); + CPPUNIT_CHECK( rp->nVal == a[i] * 2 ); } + rp.release(); - { - rcu_lock lock; - ep = l.extract_with( itm, other_less() ); - CPPUNIT_ASSERT( ep ); - CPPUNIT_ASSERT( !ep.empty() ); - CPPUNIT_CHECK( ep->nKey == a[i] ); - CPPUNIT_CHECK( ep->nVal == a[i] * 2 ); - } + ep = l.extract_with( itm, other_less() ); + CPPUNIT_ASSERT( ep ); + CPPUNIT_ASSERT( !ep.empty() ); + CPPUNIT_CHECK( ep->nKey == a[i] ); + CPPUNIT_CHECK( ep->nVal == a[i] * 2 ); ep.release(); { rcu_lock lock; - CPPUNIT_CHECK( l.get_with( itm, other_less() ) == nullptr ); - ep = l.extract_with( itm, other_less() ); - CPPUNIT_CHECK( !ep ); - CPPUNIT_CHECK( ep.empty() ); + CPPUNIT_CHECK( !l.get_with( itm, other_less() )); } + ep = l.extract_with( itm, other_less() ); + CPPUNIT_CHECK( !ep ); + CPPUNIT_CHECK( ep.empty() ); } CPPUNIT_ASSERT( l.empty() ); { rcu_lock lock; - CPPUNIT_CHECK( l.get_with( other_item( 0 ), other_less() ) == nullptr ); - CPPUNIT_CHECK( !l.extract_with( other_item(0), other_less() )); - CPPUNIT_CHECK( ep.empty() ); + CPPUNIT_CHECK( !l.get_with( other_item( 0 ), other_less() )); } + CPPUNIT_CHECK( !l.extract_with( other_item(0), other_less() )); + CPPUNIT_CHECK( ep.empty() ); + // Apply retired pointer OrdList::gc::force_dispose(); } -- 2.34.1