From 66bd4dba5cae2f5ced55e2a599006da8b443f610 Mon Sep 17 00:00:00 2001 From: khizmax Date: Sun, 31 May 2015 22:07:47 +0300 Subject: [PATCH] Changed SkipListSet/Map for new get() semantics (with raw_ptr) --- cds/container/skip_list_map_rcu.h | 67 ++-- cds/container/skip_list_set_rcu.h | 68 ++-- cds/intrusive/details/raw_ptr_disposer.h | 65 ++++ cds/intrusive/michael_list_rcu.h | 38 +-- cds/intrusive/skip_list_rcu.h | 298 +++++++----------- cds/urcu/raw_ptr.h | 10 +- change.log | 3 + projects/Win/vc12/cds.vcxproj | 1 + projects/Win/vc12/cds.vcxproj.filters | 3 + tests/test-hdr/map/hdr_skiplist_map_rcu.h | 23 +- .../set/hdr_intrusive_skiplist_set_rcu.h | 29 +- tests/test-hdr/set/hdr_skiplist_set_rcu.h | 24 +- 12 files changed, 315 insertions(+), 314 deletions(-) create mode 100644 cds/intrusive/details/raw_ptr_disposer.h diff --git a/cds/container/skip_list_map_rcu.h b/cds/container/skip_list_map_rcu.h index c5abe34a..8b78ba81 100644 --- a/cds/container/skip_list_map_rcu.h +++ b/cds/container/skip_list_map_rcu.h @@ -144,17 +144,37 @@ namespace cds { namespace container { /// pointer to extracted node using exempt_ptr = cds::urcu::exempt_ptr< gc, node_type, value_type, typename maker::intrusive_type_traits::disposer >; + private: + //@cond + struct raw_ptr_converter + { + value_type * operator()( node_type * p ) const + { + return p ? &p->m_Value : nullptr; + } + + value_type& operator()( node_type& n ) const + { + return n.m_Value; + } + + value_type const& operator()( node_type const& n ) const + { + return n.m_Value; + } + }; + //@endcond + + public: + /// Result of \p get(), \p get_with() functions - pointer to the node found + typedef cds::urcu::raw_ptr_adaptor< value_type, typename base_class::raw_ptr, raw_ptr_converter > raw_ptr; + protected: //@cond unsigned int random_level() { return base_class::random_level(); } - - value_type * to_value_ptr( node_type * pNode ) const CDS_NOEXCEPT - { - return pNode ? &pNode->m_Value : nullptr; - } //@endcond public: @@ -548,8 +568,8 @@ namespace cds { namespace container { /// Finds the key \p key and return the item found /** \anchor cds_nonintrusive_SkipListMap_rcu_get - The function searches the item with key equal to \p key and returns the pointer to item found. - If \p key is not found it returns \p nullptr. + The function searches the item with key equal to \p key and returns a \p raw_ptr object pointing to an item found. + If \p key is not found it returns empty \p raw_ptr. Note the compare functor in \p Traits class' template argument should accept a parameter of type \p K that can be not the same as \p key_type. @@ -560,26 +580,25 @@ namespace cds { namespace container { typedef cds::container::SkipListMap< cds::urcu::gc< cds::urcu::general_buffered<> >, int, foo, my_traits > skip_list; skip_list theList; // ... + typename skip_list::raw_ptr pVal; { // Lock RCU skip_list::rcu_lock lock; - skip_list::value_type * pVal = theList.get( 5 ); - // Deal with pVal - //... - - // Unlock RCU by rcu_lock destructor - // pVal can be freed at any time after RCU unlocking + pVal = theList.get( 5 ); + if ( pVal ) { + // Deal with pVal + //... + } } + // You can manually release pVal after RCU-locked section + pVal.release(); \endcode - - After RCU unlocking the \p %force_dispose member function can be called manually, - see \ref force_dispose for explanation. */ template - value_type * get( K const& key ) + raw_ptr get( K const& key ) { - return to_value_ptr( base_class::get( key )); + return raw_ptr( base_class::get( key )); } /// Finds the key \p key and return the item found @@ -592,10 +611,10 @@ namespace cds { namespace container { \p pred must imply the same element order as the comparator used for building the map. */ template - value_type * get_with( K const& key, Less pred ) + raw_ptr get_with( K const& key, Less pred ) { CDS_UNUSED( pred ); - return to_value_ptr( base_class::get_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >() )); + return raw_ptr( base_class::get_with( key, cds::details::predicate_wrapper< node_type, Less, typename maker::key_accessor >() )); } /// Clears the map (not atomic) @@ -624,14 +643,6 @@ namespace cds { namespace container { { return base_class::statistics(); } - - /// Clears internal list of ready-to-delete items passing them to RCU reclamation cycle - /** @copydetails cds_intrusive_SkipListSet_rcu_force_dispose - */ - void force_dispose() - { - return base_class::force_dispose(); - } }; }} // namespace cds::container diff --git a/cds/container/skip_list_set_rcu.h b/cds/container/skip_list_set_rcu.h index e57a8036..bb53d747 100644 --- a/cds/container/skip_list_set_rcu.h +++ b/cds/container/skip_list_set_rcu.h @@ -191,17 +191,37 @@ namespace cds { namespace container { /// pointer to extracted node using exempt_ptr = cds::urcu::exempt_ptr< gc, node_type, value_type, typename maker::intrusive_traits::disposer >; + private: + //@cond + struct raw_ptr_converter + { + value_type * operator()( node_type * p ) const + { + return p ? &p->m_Value : nullptr; + } + + value_type& operator()( node_type& n ) const + { + return n.m_Value; + } + + value_type const& operator()( node_type const& n ) const + { + return n.m_Value; + } + }; + //@endcond + + public: + /// Result of \p get(), \p get_with() functions - pointer to the node found + typedef cds::urcu::raw_ptr_adaptor< value_type, typename base_class::raw_ptr, raw_ptr_converter > raw_ptr; + protected: //@cond unsigned int random_level() { return base_class::random_level(); } - - value_type * to_value_ptr( node_type * pNode ) const CDS_NOEXCEPT - { - return pNode ? &pNode->m_Value : nullptr; - } //@endcond public: @@ -610,8 +630,8 @@ namespace cds { namespace container { /// Finds \p key and return the item found /** \anchor cds_nonintrusive_SkipListSet_rcu_get - The function searches the item with key equal to \p key and returns the pointer to item found. - If \p key is not found it returns \p nullptr. + The function searches the item with key equal to \p key and returns a \p raw_ptr object pointed to item found. + If \p key is not found it returns empty \p raw_ptr. Note the compare functor in \p Traits class' template argument should accept a parameter of type \p Q that can be not the same as \p value_type. @@ -622,26 +642,25 @@ namespace cds { namespace container { typedef cds::container::SkipListSet< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > skip_list; skip_list theList; // ... + typename skip_list::raw_ptr pVal; { // Lock RCU skip_list::rcu_lock lock; - foo * pVal = theList.get( 5 ); - // Deal with pVal - //... - - // Unlock RCU by rcu_lock destructor - // pVal can be freed at any time after RCU unlocking + pVal = theList.get( 5 ); + if ( pVal ) { + // Deal with pVal + //... + } } + // You can manually release pVal after RCU-locked section + pVal.release(); \endcode - - After RCU unlocking the \p %force_dispose member function can be called manually, - see \ref force_dispose for explanation. */ template - value_type * get( Q const& key ) + raw_ptr get( Q const& key ) { - return to_value_ptr( base_class::get( key )); + return raw_ptr( base_class::get( key )); } /// Finds the key \p val and return the item found @@ -654,10 +673,10 @@ namespace cds { namespace container { \p pred must imply the same element order as the comparator used for building the set. */ template - value_type * get_with( Q const& val, Less pred ) + raw_ptr get_with( Q const& val, Less pred ) { CDS_UNUSED( pred ); - return to_value_ptr( base_class::get_with( val, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >() )); + return raw_ptr( base_class::get_with( val, cds::details::predicate_wrapper< node_type, Less, typename maker::value_accessor >() )); } /// Clears the set (non-atomic). @@ -701,15 +720,6 @@ namespace cds { namespace container { { return base_class::statistics(); } - - /// Clears internal list of ready-to-delete items passing them to RCU reclamation cycle - /** - See \ref cds_intrusive_SkipListSet_rcu_force_dispose "intrusive SkipListSet" for explanation - */ - void force_dispose() - { - return base_class::force_dispose(); - } }; }} // namespace cds::container diff --git a/cds/intrusive/details/raw_ptr_disposer.h b/cds/intrusive/details/raw_ptr_disposer.h new file mode 100644 index 00000000..c76fbc43 --- /dev/null +++ b/cds/intrusive/details/raw_ptr_disposer.h @@ -0,0 +1,65 @@ +//$$CDS-header$$ + +#ifndef CDSLIB_INTRUSIVE_DETAILS_RAW_PTR_DISPOSER_H +#define CDSLIB_INTRUSIVE_DETAILS_RAW_PTR_DISPOSER_H + +#include + +//@cond +namespace cds { namespace intrusive { namespace details { + + template + struct raw_ptr_disposer + { + typedef RCU gc; + typedef NodeType node_type; + typedef Disposer disposer; + + node_type * pReclaimedChain; + + raw_ptr_disposer() + : pReclaimedChain( nullptr ) + {} + + template + explicit 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(); + } + + raw_ptr_disposer& operator=(raw_ptr_disposer&& d) + { + assert( pReclaimedChain == nullptr ); + pReclaimedChain = d.pReclaimedChain; + d.pReclaimedChain = nullptr; + retur *this; + } + + void apply() + { + if ( pReclaimedChain ) { + assert( !gc::is_locked()); + disposer()( pReclaimedChain ); + pReclaimedChain = nullptr; + } + } + }; + +}}} // namespace cds::intrusive::details +//@endcond + +#endif // #ifndef CDSLIB_INTRUSIVE_DETAILS_RAW_PTR_DISPOSER_H diff --git a/cds/intrusive/michael_list_rcu.h b/cds/intrusive/michael_list_rcu.h index 5843367d..f8b59f51 100644 --- a/cds/intrusive/michael_list_rcu.h +++ b/cds/intrusive/michael_list_rcu.h @@ -9,6 +9,7 @@ #include #include #include +#include namespace cds { namespace intrusive { @@ -195,42 +196,13 @@ namespace cds { namespace intrusive { private: //@cond - struct raw_ptr_disposer - { - node_type * pReclaimedChain; - - raw_ptr_disposer() - : pReclaimedChain( nullptr ) - {} - - raw_ptr_disposer( position& pos ) - : pReclaimedChain( pos.pDelChain ) + struct chain_disposer { + void operator()( node_type * pChain ) const { - 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 ) { - assert( !gc::is_locked()); - dispose_chain( pReclaimedChain ); - pReclaimedChain = nullptr; - } + dispose_chain( pChain ); } }; + typedef cds::intrusive::details::raw_ptr_disposer< gc, node_type, chain_disposer> raw_ptr_disposer; //@endcond public: diff --git a/cds/intrusive/skip_list_rcu.h b/cds/intrusive/skip_list_rcu.h index 9655545a..43692993 100644 --- a/cds/intrusive/skip_list_rcu.h +++ b/cds/intrusive/skip_list_rcu.h @@ -10,7 +10,8 @@ #include #include #include - +#include +#include namespace cds { namespace intrusive { @@ -551,6 +552,39 @@ namespace cds { namespace intrusive { typedef std::unique_ptr< node_type, typename node_builder::node_disposer > scoped_node_ptr; + static void dispose_node( value_type * pVal ) + { + assert( pVal ); + + typename node_builder::node_disposer()( node_traits::to_node_ptr(pVal) ); + disposer()( pVal ); + } + + struct node_disposer + { + void operator()( value_type * pVal ) + { + dispose_node( pVal ); + } + }; + + static void dispose_chain( node_type * pChain ) + { + if ( pChain ) { + assert( !gc::is_locked() ); + + auto f = [&pChain]() -> cds::urcu::retired_ptr { + node_type * p = pChain; + if ( p ) { + pChain = p->m_pDelChain; + return cds::urcu::make_retired_ptr( node_traits::to_value_ptr( p )); + } + return cds::urcu::make_retired_ptr( static_cast(nullptr)); + }; + gc::batch_retire(std::ref(f)); + } + } + struct position { node_type * pPrev[ c_nMaxHeight ]; node_type * pSucc[ c_nMaxHeight ]; @@ -562,12 +596,20 @@ namespace cds { namespace intrusive { position() : pDelChain( nullptr ) {} -# ifdef _DEBUG + ~position() { - assert( pDelChain == nullptr ); + dispose_chain( pDelChain ); + } + + void dispose( node_type * p ) + { + assert( p != nullptr ); + assert( p->m_pDelChain == nullptr ); + + p->m_pDelChain = pDelChain; + pDelChain = p; } -# endif }; typedef cds::urcu::details::check_deadlock_policy< gc, rcu_check_deadlock> check_deadlock_policy; @@ -596,26 +638,25 @@ namespace cds { namespace intrusive { { return node_builder::make_tower( v, m_RandomLevelGen ); } + //@endcond - static void dispose_node( value_type * pVal ) - { - assert( pVal ); - - typename node_builder::node_disposer()( node_traits::to_node_ptr(pVal) ); - disposer()( pVal ); - } + public: + using exempt_ptr = cds::urcu::exempt_ptr< gc, value_type, value_type, node_disposer, void >; ///< pointer to extracted node - struct node_disposer - { - void operator()( value_type * pVal ) + private: + //@cond + struct chain_disposer { + void operator()( node_type * pChain ) const { - dispose_node( pVal ); + dispose_chain( pChain ); } }; + typedef cds::intrusive::details::raw_ptr_disposer< gc, node_type, chain_disposer> raw_ptr_disposer; //@endcond public: - using exempt_ptr = cds::urcu::exempt_ptr< gc, value_type, value_type, node_disposer, void >; ///< pointer to extracted node + /// 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 @@ -672,7 +713,7 @@ namespace cds { namespace intrusive { if ( !is_extracted( pSucc )) { // We cannot free the node at this moment since RCU is locked // Link deleted nodes to a chain to free later - link_for_remove( pos, pCur.ptr() ); + pos.dispose( pCur.ptr() ); m_Stat.onEraseWhileFind(); } else { @@ -746,7 +787,7 @@ namespace cds { namespace intrusive { if ( !is_extracted( pSucc )) { // We cannot free the node at this moment since RCU is locked // Link deleted nodes to a chain to free later - link_for_remove( pos, pCur.ptr() ); + pos.dispose( pCur.ptr() ); m_Stat.onEraseWhileFind(); } else { @@ -773,7 +814,7 @@ namespace cds { namespace intrusive { marked_node_ptr pSucc; marked_node_ptr pCur; -retry: + retry: pPred = m_Head.head(); for ( int nLevel = static_cast(c_nMaxHeight - 1); nLevel >= 0; --nLevel ) { @@ -810,7 +851,7 @@ retry: if ( !is_extracted( pSucc )) { // We cannot free the node at this moment since RCU is locked // Link deleted nodes to a chain to free later - link_for_remove( pos, pCur.ptr() ); + pos.dispose( pCur.ptr() ); m_Stat.onEraseWhileFind(); } else { @@ -883,14 +924,6 @@ retry: return true; } - static void link_for_remove( position& pos, node_type * pDel ) - { - assert( pDel->m_pDelChain == nullptr ); - - pDel->m_pDelChain = pos.pDelChain; - pos.pDelChain = pDel; - } - template bool try_remove_at( node_type * pDel, position& pos, Func f, bool bExtract ) { @@ -948,7 +981,7 @@ retry: if ( !bExtract ) { // We cannot free the node at this moment since RCU is locked // Link deleted nodes to a chain to free later - link_for_remove( pos, pDel ); + pos.dispose( pDel ); m_Stat.onFastErase(); } else @@ -1034,32 +1067,37 @@ retry: bool do_find_with( Q& val, Compare cmp, Func f ) { position pos; + return do_find_with( val, cmp, f, pos ); + } + + template + bool do_find_with( Q& val, Compare cmp, Func f, position& pos ) + { bool bRet; - rcu_lock l; + { + rcu_lock l; - switch ( find_fastpath( val, cmp, f )) { - case find_fastpath_found: - m_Stat.onFindFastSuccess(); - return true; - case find_fastpath_not_found: - m_Stat.onFindFastFailed(); - return false; - default: - break; - } + switch ( find_fastpath( val, cmp, f )) { + case find_fastpath_found: + m_Stat.onFindFastSuccess(); + return true; + case find_fastpath_not_found: + m_Stat.onFindFastFailed(); + return false; + default: + break; + } - if ( find_slowpath( val, cmp, f, pos )) { - m_Stat.onFindSlowSuccess(); - bRet = true; - } - else { - m_Stat.onFindSlowFailed(); - bRet = false; + if ( find_slowpath( val, cmp, f, pos )) { + m_Stat.onFindSlowSuccess(); + bRet = true; + } + else { + m_Stat.onFindSlowFailed(); + bRet = false; + } } - - defer_chain( pos ); - return bRet; } @@ -1096,17 +1134,15 @@ retry: } } - dispose_chain( pos ); return bRet; } template - value_type * do_extract_key( Q const& key, Compare cmp ) + value_type * do_extract_key( Q const& key, Compare cmp, position& pos ) { // RCU should be locked!!! assert( gc::is_locked() ); - position pos; node_type * pDel; if ( !find_position( key, pos, cmp, false ) ) { @@ -1130,7 +1166,6 @@ retry: } } - defer_chain( pos ); return pDel ? node_traits::to_value_ptr( pDel ) : nullptr; } @@ -1139,12 +1174,12 @@ retry: { check_deadlock_policy::check(); value_type * pDel = nullptr; + position pos; { rcu_lock l; - pDel = do_extract_key( key, key_comparator() ); + pDel = do_extract_key( key, key_comparator(), pos ); } - dispose_deferred(); return pDel; } @@ -1154,13 +1189,12 @@ retry: CDS_UNUSED(pred); check_deadlock_policy::check(); value_type * pDel = nullptr; - + position pos; { rcu_lock l; - pDel = do_extract_key( key, cds::opt::details::make_comparator_from_less() ); + pDel = do_extract_key( key, cds::opt::details::make_comparator_from_less(), pos ); } - dispose_deferred(); return pDel; } @@ -1192,11 +1226,8 @@ retry: pDel = nullptr; } } - - defer_chain( pos ); } - dispose_deferred(); return pDel ? node_traits::to_value_ptr( pDel ) : nullptr; } @@ -1228,11 +1259,8 @@ retry: pDel = nullptr; } } - - defer_chain( pos ); } - dispose_deferred(); return pDel ? node_traits::to_value_ptr( pDel ) : nullptr; } @@ -1242,83 +1270,6 @@ retry: if ( nCur < nHeight ) m_nHeight.compare_exchange_strong( nCur, nHeight, memory_model::memory_order_release, atomics::memory_order_relaxed ); } - - class deferred_list_iterator - { - node_type * pCur; - public: - explicit deferred_list_iterator( node_type * p ) - : pCur(p) - {} - deferred_list_iterator() - : pCur( nullptr ) - {} - - cds::urcu::retired_ptr operator *() const - { - return cds::urcu::retired_ptr( node_traits::to_value_ptr(pCur), dispose_node ); - } - - void operator ++() - { - pCur = pCur->m_pDelChain; - } - - bool operator ==( deferred_list_iterator const& i ) const - { - return pCur == i.pCur; - } - bool operator !=( deferred_list_iterator const& i ) const - { - return !operator ==( i ); - } - }; - - void dispose_chain( node_type * pHead ) - { - // RCU should NOT be locked - check_deadlock_policy::check(); - - gc::batch_retire( deferred_list_iterator( pHead ), deferred_list_iterator() ); - } - - void dispose_chain( position& pos ) - { - // RCU should NOT be locked - check_deadlock_policy::check(); - - // Delete local chain - if ( pos.pDelChain ) { - dispose_chain( pos.pDelChain ); - pos.pDelChain = nullptr; - } - - // Delete deferred chain - dispose_deferred(); - } - - void dispose_deferred() - { - dispose_chain( m_pDeferredDelChain.exchange( nullptr, memory_model::memory_order_acq_rel ) ); - } - - void defer_chain( position& pos ) - { - if ( pos.pDelChain ) { - node_type * pHead = pos.pDelChain; - node_type * pTail = pHead; - while ( pTail->m_pDelChain ) - pTail = pTail->m_pDelChain; - - node_type * pDeferList = m_pDeferredDelChain.load( memory_model::memory_order_relaxed ); - do { - pTail->m_pDelChain = pDeferList; - } while ( !m_pDeferredDelChain.compare_exchange_weak( pDeferList, pHead, memory_model::memory_order_acq_rel, atomics::memory_order_relaxed )); - - pos.pDelChain = nullptr; - } - } - //@endcond public: @@ -1469,8 +1420,6 @@ retry: } } - dispose_chain( pos ); - return bRet; } @@ -1553,8 +1502,6 @@ retry: } } - dispose_chain( pos ); - return bRet; } @@ -1583,7 +1530,7 @@ retry: bool bRet; { - rcu_lock rcuLock; + rcu_lock l; if ( !find_position( val, pos, key_comparator(), false ) ) { m_Stat.onUnlinkFailed(); @@ -1608,8 +1555,6 @@ retry: } } - dispose_chain( pos ); - return bRet; } @@ -1884,8 +1829,8 @@ retry: /// Finds \p key and return the item found /** \anchor cds_intrusive_SkipListSet_rcu_get - The function searches the item with key equal to \p key and returns the pointer to item found. - If \p key is not found it returns \p nullptr. + The function searches the item with key equal to \p key and returns a \p raw_ptr object pointed to item found. + If \p key is not found it returns empty \p raw_ptr. Note the compare functor should accept a parameter of type \p Q that can be not the same as \p value_type. @@ -1895,31 +1840,31 @@ retry: typedef cds::intrusive::SkipListSet< cds::urcu::gc< cds::urcu::general_buffered<> >, foo, my_traits > skip_list; skip_list theList; // ... + typename skip_list::raw_ptr pVal; { // Lock RCU skip_list::rcu_lock lock; - foo * pVal = theList.get( 5 ); + pVal = theList.get( 5 ); if ( pVal ) { // Deal with pVal //... } } - // Unlock RCU by rcu_lock destructor - // pVal can be retired by disposer at any time after RCU has been unlocked + // You can manually release pVal after RCU-locked section + pVal.release(); \endcode - - After RCU unlocking the \p %force_dispose member function can be called manually, - see \ref force_dispose for explanation. */ template - value_type * get( Q const& key ) + raw_ptr get( Q const& key ) { assert( gc::is_locked()); + position pos; value_type * pFound; - return do_find_with( key, key_comparator(), [&pFound](value_type& found, Q const& ) { pFound = &found; } ) - ? pFound : nullptr; + if ( do_find_with( key, key_comparator(), [&pFound](value_type& found, Q const& ) { pFound = &found; }, pos )) + return raw_ptr( pFound, raw_ptr_disposer( pos )); + return raw_ptr( raw_ptr_disposer( pos )); } /// Finds \p key and return the item found @@ -1932,15 +1877,19 @@ retry: \p pred must imply the same element order as the comparator used for building the set. */ template - value_type * get_with( Q const& key, Less pred ) + raw_ptr get_with( Q const& key, Less pred ) { CDS_UNUSED( pred ); assert( gc::is_locked()); value_type * pFound; - return do_find_with( key, cds::opt::details::make_comparator_from_less(), - [&pFound](value_type& found, Q const& ) { pFound = &found; } ) - ? pFound : nullptr; + position pos; + if ( do_find_with( key, cds::opt::details::make_comparator_from_less(), + [&pFound](value_type& found, Q const& ) { pFound = &found; }, pos )) + { + return raw_ptr( pFound, raw_ptr_disposer( pos )); + } + return raw_ptr( raw_ptr_disposer( pos )); } /// Returns item count in the set @@ -1991,27 +1940,6 @@ retry: { return m_Stat; } - - /// Clears internal list of ready-to-remove items passing it to RCU reclamation cycle - /** @anchor cds_intrusive_SkipListSet_rcu_force_dispose - Skip list has complex multi-step algorithm for removing an item. In fact, when you - remove the item it is just marked as removed that is enough for the success of your operation. - Actual removing can take place in the future, in another call or even in another thread. - Inside RCU lock the removed item cannot be passed to RCU reclamation cycle - since it can lead to deadlock. To solve this problem, the current skip list implementation - has internal list of items which is ready to remove but is not yet passed to RCU reclamation. - Usually, this list will be passed to RCU reclamation in the next suitable call of skip list member function. - In some cases we want to pass it to RCU reclamation immediately after RCU unlocking. - This function provides such opportunity: it checks whether the RCU is not locked and if it is true - the function passes the internal ready-to-remove list to RCU reclamation cycle. - - The RCU \p synchronize can be called. - */ - void force_dispose() - { - if ( !gc::is_locked() ) - dispose_deferred(); - } }; }} // namespace cds::intrusive diff --git a/cds/urcu/raw_ptr.h b/cds/urcu/raw_ptr.h index 58c16646..81ef76f0 100644 --- a/cds/urcu/raw_ptr.h +++ b/cds/urcu/raw_ptr.h @@ -19,7 +19,7 @@ namespace cds { namespace urcu { 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 + and a chain of nodes that were 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. @@ -109,12 +109,12 @@ namespace cds { namespace urcu { /** 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() ); + if ( !rcu::is_locked() ) + release(); m_ptr = p.m_ptr; m_Enum = std::move( p.m_Enum ); @@ -159,8 +159,8 @@ namespace cds { namespace urcu { /// Releases the \p %raw_ptr object /** - This function may be called only outside RCU section. - After \p %release() the object can be reused. + This function may be called only outside RCU locked region. + After \p %release() the object becomes empty and can be reused. */ void release() { diff --git a/change.log b/change.log index 7960a2d2..a427e181 100644 --- a/change.log +++ b/change.log @@ -8,6 +8,9 @@ see doc. Thus, semantics of extract()/get() of all RCU-based set and maps based on MichaelList (MichaelSet/Map, SplitListSet/Map) has been changed too. + - Changed: SplitListSet/Map functions get() and get_with() return special wrapper + object of type raw_ptr, see doc. + - Removed: SplitListSet/Map force_dispose() function. - cds::lock namespace is renamed to cds::sync. All classes defined in cds::lock namespace are moved to cds::sync with new names (for example, cds::lock::SpinLock is renamed to cds::sync::spin_lock). cds::lock namespace and its contents is deprecated, it is kept diff --git a/projects/Win/vc12/cds.vcxproj b/projects/Win/vc12/cds.vcxproj index b4290f9f..514be40c 100644 --- a/projects/Win/vc12/cds.vcxproj +++ b/projects/Win/vc12/cds.vcxproj @@ -753,6 +753,7 @@ + diff --git a/projects/Win/vc12/cds.vcxproj.filters b/projects/Win/vc12/cds.vcxproj.filters index 55201468..b2487acc 100644 --- a/projects/Win/vc12/cds.vcxproj.filters +++ b/projects/Win/vc12/cds.vcxproj.filters @@ -1184,5 +1184,8 @@ Header Files\cds\urcu + + Header Files\cds\intrusive\details + \ No newline at end of file diff --git a/tests/test-hdr/map/hdr_skiplist_map_rcu.h b/tests/test-hdr/map/hdr_skiplist_map_rcu.h index 70a0dd65..b5b28e76 100644 --- a/tests/test-hdr/map/hdr_skiplist_map_rcu.h +++ b/tests/test-hdr/map/hdr_skiplist_map_rcu.h @@ -162,17 +162,19 @@ namespace map { typedef typename Map::value_type value_type; typename Map::exempt_ptr ep; + typename Map::raw_ptr rp; // extract/get for ( int i = 0; i < nLimit; ++i ) { int nKey = arrItem[i]; { rcu_lock l; - value_type * pVal = m.get( nKey ); - CPPUNIT_ASSERT( pVal != nullptr ); - CPPUNIT_CHECK( pVal->first == nKey ); - CPPUNIT_CHECK( pVal->second.m_val == nKey * 2 ); + rp = m.get( nKey ); + CPPUNIT_ASSERT( rp ); + CPPUNIT_CHECK( rp->first == nKey ); + CPPUNIT_CHECK( rp->second.m_val == nKey * 2 ); } + rp.release(); ep = m.extract( nKey ); CPPUNIT_ASSERT( ep ); @@ -183,7 +185,7 @@ namespace map { { rcu_lock l; - CPPUNIT_CHECK( m.get( nKey ) == nullptr ); + CPPUNIT_CHECK( !m.get( nKey )); } ep = m.extract( nKey ); CPPUNIT_CHECK( !ep ); @@ -198,11 +200,12 @@ namespace map { int nKey = arrItem[i]; { rcu_lock l; - value_type * pVal = m.get_with( wrapped_item(nKey), wrapped_less() ); - CPPUNIT_ASSERT( pVal != nullptr ); - CPPUNIT_CHECK( pVal->first == nKey ); - CPPUNIT_CHECK( pVal->second.m_val == nKey * 2 ); + rp = m.get_with( wrapped_item(nKey), wrapped_less() ); + CPPUNIT_ASSERT( rp ); + CPPUNIT_CHECK( rp->first == nKey ); + CPPUNIT_CHECK( rp->second.m_val == nKey * 2 ); } + rp.release(); ep = m.extract_with( wrapped_item( nKey ), wrapped_less() ); CPPUNIT_ASSERT( ep ); @@ -213,7 +216,7 @@ namespace map { { rcu_lock l; - CPPUNIT_CHECK( m.get_with( wrapped_item(nKey), wrapped_less() ) == nullptr ); + CPPUNIT_CHECK( !m.get_with( wrapped_item(nKey), wrapped_less() )); } ep = m.extract_with( wrapped_item( nKey ), wrapped_less() ); CPPUNIT_CHECK( !ep ); diff --git a/tests/test-hdr/set/hdr_intrusive_skiplist_set_rcu.h b/tests/test-hdr/set/hdr_intrusive_skiplist_set_rcu.h index d4898a04..be46d3fd 100644 --- a/tests/test-hdr/set/hdr_intrusive_skiplist_set_rcu.h +++ b/tests/test-hdr/set/hdr_intrusive_skiplist_set_rcu.h @@ -257,19 +257,21 @@ namespace set { // extract/get test { typename Set::exempt_ptr ep; + typename Set::raw_ptr rp; // extract { fill_skiplist( s, v ); - value_type * pVal; + for ( int i = c_nArrSize - 1; i >= 0; i -= 1 ) { { rcu_lock l; - pVal = s.get( i ); - CPPUNIT_ASSERT( pVal != nullptr ); - CPPUNIT_CHECK( pVal->nKey == i ); - CPPUNIT_CHECK( pVal->nVal == i * 2 ); - pVal->nVal *= 2; + rp = s.get( i ); + CPPUNIT_ASSERT( rp ); + CPPUNIT_CHECK( rp->nKey == i ); + CPPUNIT_CHECK( rp->nVal == i * 2 ); + rp->nVal *= 2; } + rp.release(); ep = s.extract( i ); CPPUNIT_ASSERT( ep ); @@ -280,7 +282,7 @@ namespace set { { rcu_lock l; - CPPUNIT_CHECK( s.get( i ) == nullptr ); + CPPUNIT_CHECK( !s.get( i )); } ep = s.extract( i ); CPPUNIT_CHECK( !ep ); @@ -296,12 +298,13 @@ namespace set { for ( int i = c_nArrSize - 1; i >= 0; i -= 1 ) { { rcu_lock l; - value_type * pVal = s.get_with( other_key(i), other_key_less() ); - CPPUNIT_ASSERT( pVal != nullptr ); - CPPUNIT_CHECK( pVal->nKey == i ); - CPPUNIT_CHECK( pVal->nVal == i * 2 ); - pVal->nVal *= 2; + rp = s.get_with( other_key(i), other_key_less() ); + CPPUNIT_ASSERT( rp ); + CPPUNIT_CHECK( rp->nKey == i ); + CPPUNIT_CHECK( rp->nVal == i * 2 ); + rp->nVal *= 2; } + rp.release(); ep = s.extract_with( other_key( i ), other_key_less() ); CPPUNIT_ASSERT( ep ); @@ -312,7 +315,7 @@ namespace set { { rcu_lock l; - CPPUNIT_CHECK( s.get_with( other_key( i ), other_key_less() ) == nullptr ); + CPPUNIT_CHECK( !s.get_with( other_key( i ), other_key_less() )); } ep = s.extract_with( other_key( i ), other_key_less() ); CPPUNIT_CHECK( !ep ); diff --git a/tests/test-hdr/set/hdr_skiplist_set_rcu.h b/tests/test-hdr/set/hdr_skiplist_set_rcu.h index c655ed18..f84b322b 100644 --- a/tests/test-hdr/set/hdr_skiplist_set_rcu.h +++ b/tests/test-hdr/set/hdr_skiplist_set_rcu.h @@ -157,19 +157,20 @@ namespace set { // extract/get tests { typedef typename base_class::less less_predicate; - typename Set::value_type * pVal; typename Set::exempt_ptr ep; + typename Set::raw_ptr rp; // extract/get for ( int i = 0; i < nLimit; ++i ) { int nKey = arrRandom[i]; { rcu_lock l; - pVal = s.get( nKey ); - CPPUNIT_ASSERT( pVal != nullptr ); - CPPUNIT_CHECK( pVal->nKey == nKey ); - CPPUNIT_CHECK( pVal->nVal == nKey * 2 ); + rp = s.get( nKey ); + CPPUNIT_ASSERT( rp ); + CPPUNIT_CHECK( rp->nKey == nKey ); + CPPUNIT_CHECK( rp->nVal == nKey * 2 ); } + rp.release(); ep = s.extract( nKey ); CPPUNIT_ASSERT( ep ); @@ -180,7 +181,7 @@ namespace set { { rcu_lock l; - CPPUNIT_CHECK( s.get( nKey ) == nullptr ); + CPPUNIT_CHECK( !s.get( nKey )); } ep = s.extract( nKey ); CPPUNIT_CHECK( !ep ); @@ -195,11 +196,12 @@ namespace set { int nKey = arrRandom[i]; { rcu_lock l; - pVal = s.get_with( wrapped_item(nKey), wrapped_less() ); - CPPUNIT_ASSERT( pVal != nullptr ); - CPPUNIT_CHECK( pVal->nKey == nKey ); - CPPUNIT_CHECK( pVal->nVal == nKey ); + rp = s.get_with( wrapped_item(nKey), wrapped_less() ); + CPPUNIT_ASSERT( rp ); + CPPUNIT_CHECK( rp->nKey == nKey ); + CPPUNIT_CHECK( rp->nVal == nKey ); } + rp.release(); ep = s.extract_with( wrapped_item( nKey ), wrapped_less() ); CPPUNIT_ASSERT( ep ); @@ -210,7 +212,7 @@ namespace set { { rcu_lock l; - CPPUNIT_CHECK( s.get_with( wrapped_item( nKey ), wrapped_less() ) == nullptr ); + CPPUNIT_CHECK( !s.get_with( wrapped_item( nKey ), wrapped_less() )); } ep = s.extract_with( wrapped_item( nKey ), wrapped_less() ); CPPUNIT_CHECK( !ep ); -- 2.34.1