From 5e103696543a070027dc37bd05cbac6324ca7e93 Mon Sep 17 00:00:00 2001 From: khizmax Date: Thu, 5 Feb 2015 23:13:39 +0300 Subject: [PATCH] Changed sync monitor internal interface from base hook to member hook --- .gitignore | 2 + cds/container/details/bronson_avltree_base.h | 11 +-- cds/container/impl/bronson_avltree_map_rcu.h | 6 +- cds/sync/injecting_monitor.h | 21 ++---- cds/sync/monitor.h | 15 +++- cds/sync/pool_monitor.h | 78 +++++++------------- projects/Win/vc12/cds.vcxproj | 1 - projects/Win/vc12/cds.vcxproj.filters | 3 - 8 files changed, 57 insertions(+), 80 deletions(-) diff --git a/.gitignore b/.gitignore index 8a8cb0eb..069a979e 100644 --- a/.gitignore +++ b/.gitignore @@ -16,3 +16,5 @@ obj /projects/Win/vc14/cds.vcxproj.user /projects/Win/vc14/*.opensdf /projects/Win/vc14/.vs/cds/v14 +/build/build-mingw-amd64.bat +/build/build-mingw-amd64.log diff --git a/cds/container/details/bronson_avltree_base.h b/cds/container/details/bronson_avltree_base.h index faa127ea..5c3baafe 100644 --- a/cds/container/details/bronson_avltree_base.h +++ b/cds/container/details/bronson_avltree_base.h @@ -14,11 +14,11 @@ namespace cds { namespace container { /// BronsonAVLTree related declarations namespace bronson_avltree { - template + template struct node; //@cond - template + template struct link_node { typedef Node node_type; @@ -37,6 +37,7 @@ namespace cds { namespace container { atomics::atomic m_pParent; ///< Parent node atomics::atomic m_pLeft; ///< Left child atomics::atomic m_pRight; ///< Right child + typename SyncMonitor::node_injection m_SyncMonitorInjection; ///< @ref cds_sync_monitor "synchronization monitor" injected data public: //@cond @@ -113,10 +114,10 @@ namespace cds { namespace container { //@endcond // BronsonAVLTree internal node - template - struct node: public link_node< node> + template + struct node: public link_node< node, SyncMonitor > { - typedef link_node< node> base_class; + typedef link_node< node, SyncMonitor > base_class; typedef Key key_type; ///< key type typedef T mapped_type; ///< value type diff --git a/cds/container/impl/bronson_avltree_map_rcu.h b/cds/container/impl/bronson_avltree_map_rcu.h index 143152b1..3ebf228c 100644 --- a/cds/container/impl/bronson_avltree_map_rcu.h +++ b/cds/container/impl/bronson_avltree_map_rcu.h @@ -75,7 +75,7 @@ namespace cds { namespace container { protected: //@cond - typedef typename sync_monitor::template node_injection< bronson_avltree::node< key_type, mapped_type >> node_type; + typedef bronson_avltree::node< key_type, mapped_type, sync_monitor > node_type; typedef typename node_type::version_type version_type; typedef cds::details::Allocator< node_type, node_allocator_type > cxx_allocator; @@ -130,12 +130,12 @@ namespace cds { namespace container { static node_type * child( node_type * pNode, int nDir, atomics::memory_order order ) { - return static_cast(pNode->child( nDir ).load( order )); + return pNode->child( nDir ).load( order ); } static node_type * parent( node_type * pNode, atomics::memory_order order ) { - return static_cast(pNode->m_pParent.load( order )); + return pNode->m_pParent.load( order ); } // RCU safe disposer diff --git a/cds/sync/injecting_monitor.h b/cds/sync/injecting_monitor.h index a2610e59..e1cf5637 100644 --- a/cds/sync/injecting_monitor.h +++ b/cds/sync/injecting_monitor.h @@ -24,34 +24,23 @@ namespace cds { namespace sync { public: typedef Lock lock_type; ///< Lock type - /// Monitor injection into \p Node - template - struct node_injection: public Node - { -# ifdef CDS_CXX11_INHERITING_CTOR - using Node::Node; -# else - // Inheriting ctor emulation - template - node_injection( Args&&... args ) - : Node( std::forward( args )... ) - {} -# endif - mutable lock_type m_Lock; ///< Node-level lock + /// Node injection + struct node_injection { + mutable lock_type m_Lock; ///< Node spin-lock }; /// Makes exclusive access to node \p p template void lock( Node const& p ) const { - p.m_Lock.lock(); + p.m_SyncMonitorInjection.m_Lock.lock(); } /// Unlocks the node \p p template void unlock( Node const& p ) const { - p.m_Lock.unlock(); + p.m_SyncMonitorInjection.m_Lock.unlock(); } /// Scoped lock diff --git a/cds/sync/monitor.h b/cds/sync/monitor.h index 896e5a9b..c3ea5252 100644 --- a/cds/sync/monitor.h +++ b/cds/sync/monitor.h @@ -17,10 +17,9 @@ namespace cds { namespace sync { For huge trees containing millions of nodes it can be very inefficient to inject the lock object into each node. Moreover, some operating systems may not support the millions of system objects like mutexes per user process. - The monitor strategy is intended to solve that problem. When the node should be locked, the monitor is called to allocate appropriate - lock object for the node if it's needed, and to lock the node. + lock object for the node if needed, and to lock the node. The monitor strategy can significantly reduce the number of system objects required for data structure. @@ -68,16 +67,28 @@ namespace cds { namespace sync { using scoped_lock = monitor_scoped_lock< pool_monitor, Node >; }; \endcode + + Monitor's data should be inject into container's node as \p m_SyncMonitorInjection data member: + \code + template + struct my_node + { + typename SyncMonitor::node_injection m_SyncMonitorInjection; + }; + \endcode + The monitor should be a member of your container: \code template class my_container { // ... typedef typename Traits::sync_monitor sync_monitor; + typedef my_node node_type; sync_monitor m_Monitor; //... }; \endcode + */ /// Monitor scoped lock (RAII) diff --git a/cds/sync/pool_monitor.h b/cds/sync/pool_monitor.h index 6e5fea63..4d0fad90 100644 --- a/cds/sync/pool_monitor.h +++ b/cds/sync/pool_monitor.h @@ -45,45 +45,23 @@ namespace cds { namespace sync { //@endcond public: - /// Monitor injection into \p Node - template - class node_injection : public Node + + /// Node injection + struct node_injection { - //@cond - typedef unsigned int refspin_type; - static CDS_CONSTEXPR refspin_type const c_nSpinBit = 1; - static CDS_CONSTEXPR refspin_type const c_nRefIncrement = 2; + mutable atomics::atomic m_RefSpin; ///< Spin-lock for \p m_pLock (bit 0) + reference counter + mutable lock_type * m_pLock; ///< Node-level lock - struct injection - { - atomics::atomic m_RefSpin; ///< Spin-lock for \p m_pLock (bit 0) + reference counter - lock_type * m_pLock; ///< Node-level lock - - injection() - : m_Access( 0 ) - , m_pLock( nullptr ) - {} - - ~injection() - { - assert( m_pLock == nullptr ); - assert( m_RefSpin.load( atomics::memory_order_relaxed ) == 0 ); - } - }; - //@endcond - - public: - mutable injection m_Access; ///< injected data - -# ifdef CDS_CXX11_INHERITING_CTOR - using Node::Node; -# else - // Inheriting ctor emulation - template - node_injection( Args&&... args ) - : Node( std::forward( args )... ) + node_injection() + : m_Access( 0 ) + , m_pLock( nullptr ) {} -# endif + + ~node_injection() + { + assert( m_pLock == nullptr ); + assert( m_RefSpin.load( atomics::memory_order_relaxed ) == 0 ); + } }; /// Initializes the pool of 256 preallocated mutexes @@ -103,26 +81,26 @@ namespace cds { namespace sync { lock_type * pLock; // try lock spin and increment reference counter - refspin_type cur = p.m_Access.m_RefSpin.load( atomics::memory_order_relaxed ) & ~c_nSpinBit; - if ( !p.m_Access.m_RefSpin.compare_exchange_weak( cur, cur + c_nRefIncrement + c_nSpinBit, + refspin_type cur = p.m_SyncMonitorInjection.m_RefSpin.load( atomics::memory_order_relaxed ) & ~c_nSpinBit; + if ( !p.m_SyncMonitorInjection.m_RefSpin.compare_exchange_weak( cur, cur + c_nRefIncrement + c_nSpinBit, atomics::memory_order_acquire, atomics::memory_order_relaxed ) ) { back_off bkoff; do { bkoff(); cur &= ~c_nSpinBit; - } while ( !p.m_Access.m_RefSpin.compare_exchange_weak( cur, cur + c_nRefIncrement + c_nSpinBit, + } while ( !p.m_SyncMonitorInjection.m_RefSpin.compare_exchange_weak( cur, cur + c_nRefIncrement + c_nSpinBit, atomics::memory_order_acquire, atomics::memory_order_relaxed ); } // spin locked // If the node has no lock, allocate it from pool - pLock = p.m_Access.m_pLock; + pLock = p.m_SyncMonitorInjection.m_pLock; if ( !pLock ) - pLock = p.m_Access.m_pLock = m_Pool.allocate( 1 ); + pLock = p.m_SyncMonitorInjection.m_pLock = m_Pool.allocate( 1 ); // unlock spin - p.m_Access.m_RefSpin.store( cur + c_nRefIncrement, atomics::memory_order_release ); + p.m_SyncMonitorInjection.m_RefSpin.store( cur + c_nRefIncrement, atomics::memory_order_release ); // lock the node pLock->lock(); @@ -134,19 +112,19 @@ namespace cds { namespace sync { { lock_type * pLock = nullptr; - assert( p.m_Access.m_pLock != nullptr ); - p.m_Access.m_pLock->unlock(); + assert( p.m_SyncMonitorInjection.m_pLock != nullptr ); + p.m_SyncMonitorInjection.m_pLock->unlock(); // try lock spin - refspin_type cur = p.m_Access.m_RefSpin.load( atomics::memory_order_relaxed ) & ~c_nSpinBit; - if ( !p.m_Access.m_RefSpin.compare_exchange_weak( cur, cur + c_nSpinBit, + refspin_type cur = p.m_SyncMonitorInjection.m_RefSpin.load( atomics::memory_order_relaxed ) & ~c_nSpinBit; + if ( !p.m_SyncMonitorInjection.m_RefSpin.compare_exchange_weak( cur, cur + c_nSpinBit, atomics::memory_order_acquire, atomics::memory_order_relaxed ) ) { back_off bkoff; do { bkoff(); cur &= ~c_nSpinBit; - } while ( !p.m_Access.m_RefSpin.compare_exchange_weak( cur, cur + c_nSpinBit, + } while ( !p.m_SyncMonitorInjection.m_RefSpin.compare_exchange_weak( cur, cur + c_nSpinBit, atomics::memory_order_acquire, atomics::memory_order_relaxed ); } @@ -154,12 +132,12 @@ namespace cds { namespace sync { // If we are the unique owner - deallocate lock if ( cur == c_nRefIncrement ) { - pLock = p.m_Access.m_pLock; - p.m_Access.m_pLock = nullptr; + pLock = p.m_SyncMonitorInjection.m_pLock; + p.m_SyncMonitorInjection.m_pLock = nullptr; } // unlock spin - p.m_Access.m_RefSpin.store( cur - c_nRefIncrement, atomics::memory_order_release ); + p.m_SyncMonitorInjection.m_RefSpin.store( cur - c_nRefIncrement, atomics::memory_order_release ); // free pLock if ( pLock ) diff --git a/projects/Win/vc12/cds.vcxproj b/projects/Win/vc12/cds.vcxproj index 9f3752a4..159bf047 100644 --- a/projects/Win/vc12/cds.vcxproj +++ b/projects/Win/vc12/cds.vcxproj @@ -787,7 +787,6 @@ - diff --git a/projects/Win/vc12/cds.vcxproj.filters b/projects/Win/vc12/cds.vcxproj.filters index c3667980..63066563 100644 --- a/projects/Win/vc12/cds.vcxproj.filters +++ b/projects/Win/vc12/cds.vcxproj.filters @@ -644,9 +644,6 @@ Header Files\cds\compiler\clang - - Header Files\cds\memory - Header Files\cds\intrusive -- 2.34.1