From e61609109e075c98e21f5b555795f9090061e135 Mon Sep 17 00:00:00 2001 From: khizmax Date: Mon, 1 Aug 2016 11:30:51 +0300 Subject: [PATCH] Fixed priority inversion bug in MSPriorityQueue --- cds/container/mspriority_queue.h | 21 ++++++--- cds/intrusive/mspriority_queue.h | 58 ++++++++++++++----------- change.log | 1 + test/stress/pqueue/pop.cpp | 12 ++--- test/stress/pqueue/pqueue_type.h | 49 ++++----------------- test/stress/pqueue/push.cpp | 12 ++--- test/stress/pqueue/push_pop.cpp | 12 ++--- test/unit/pqueue/intrusive_mspqueue.cpp | 28 ++++++++++++ test/unit/pqueue/mspqueue.cpp | 28 ++++++++++++ 9 files changed, 123 insertions(+), 98 deletions(-) diff --git a/cds/container/mspriority_queue.h b/cds/container/mspriority_queue.h index a846de6a..77e7ea00 100644 --- a/cds/container/mspriority_queue.h +++ b/cds/container/mspriority_queue.h @@ -43,14 +43,18 @@ namespace cds { namespace container { namespace mspriority_queue { #ifdef CDS_DOXYGEN_INVOKED - /// Synonym for cds::intrusive::mspriority_queue::stat + /// Synonym for \p cds::intrusive::mspriority_queue::stat typedef cds::intrusive::mspriority_queue::stat<> stat; - /// Synonym for cds::intrusive::mspriority_queue::empty_stat + /// Synonym for \p cds::intrusive::mspriority_queue::empty_stat typedef cds::intrusive::mspriority_queue::empty_stat empty_stat; + + /// Synonym for \p cds::intrusive::mspriority_queue::monotonic_counter + typedef cds::intrusive::mspriority_queue::monotonic_counter monotonic_counter; #else using cds::intrusive::mspriority_queue::stat; using cds::intrusive::mspriority_queue::empty_stat; + using cds::intrusive::mspriority_queue::monotonic_counter; #endif /// MSPriorityQueue traits @@ -91,7 +95,9 @@ namespace cds { namespace container { If the compiler supports move semantics it would be better to specify the move policy based on the move semantics for type \p T. - \p opt::stat - internal statistics. Available types: \p mspriority_queue::stat, \p mspriority_queue::empty_stat (the default, no overhead) - */ + - \p opt::item_counter - an item counter type for \p MSPriorityQueue. + Available type: \p cds::bitop::bit_reverse_counter, \p mspriority_queue::monotonic_counter. See \p cds::intrusive::mspriority_queue::traits::item_counter for details. + */ template struct make_traits { # ifdef CDS_DOXYGEN_INVOKED @@ -142,11 +148,12 @@ namespace cds { namespace container { typedef Traits traits ; ///< Traits template parameter typedef typename base_class::key_comparator key_comparator; ///< priority comparing functor based on opt::compare and opt::less option setter. - typedef typename base_class::lock_type lock_type; ///< heap's size lock type - typedef typename base_class::back_off back_off ; ///< Back-off strategy - typedef typename base_class::stat stat ; ///< internal statistics type + typedef typename base_class::lock_type lock_type; ///< heap's size lock type + typedef typename base_class::back_off back_off ; ///< Back-off strategy + typedef typename traits::stat stat; ///< internal statistics type, see \p intrusive::mspriority_queue::traits::stat + typedef typename traits::item_counter item_counter;///< Item counter type, see \p intrusive::mspriority_queue::traits::item_counter typedef typename traits::allocator::template rebind::other allocator_type; ///< Value allocator - typedef typename traits::move_policy move_policy; ///< Move policy for type \p T + typedef typename traits::move_policy move_policy; ///< Move policy for type \p T protected: //@cond diff --git a/cds/intrusive/mspriority_queue.h b/cds/intrusive/mspriority_queue.h index 9128fca8..fb920a8c 100644 --- a/cds/intrusive/mspriority_queue.h +++ b/cds/intrusive/mspriority_queue.h @@ -93,8 +93,10 @@ namespace cds { namespace intrusive { //@endcond }; + /// Monotonic item counter, see \p traits::item_counter for explanation class monotonic_counter { + //@cond public: typedef size_t counter_type; @@ -119,6 +121,7 @@ namespace cds { namespace intrusive { private: size_t m_nCounter; + //@endcond }; /// MSPriorityQueue traits @@ -159,10 +162,18 @@ namespace cds { namespace intrusive { typedef empty_stat stat; /// Item counter type + /** + Two type are possible: + - \p cds::bitop::bit_reverse_counter - a counter described in original paper, + which was developed for reducing lock contention. However, bit-reversing technigue requires more memory than classic heapifying algorithm + because of sparsing of elements: for priority queue of max size \p N the bit-reversing technique requires array size up to 2K + where \p K - the nearest power of two such that 2K >= N. + - \p mspriority_queue::monotonic_counter - a classic monotonic item counter. This counter can lead to false sharing under high contention. + By the other hand, for priority queue of max size \p N it requires \p N array size. + + By default, \p MSPriorityQueue uses \p %cds::bitop::bit_reverse_counter as described in original paper. + */ typedef cds::bitop::bit_reverse_counter<> item_counter; - - /// Fairness - static bool const fairness = true; }; /// Metafunction converting option list to traits @@ -178,6 +189,8 @@ namespace cds { namespace intrusive { - \p opt::lock_type - lock type. Default is \p cds::sync::spin - \p opt::back_off - back-off strategy. Default is \p cds::backoff::yield - \p opt::stat - internal statistics. Available types: \p mspriority_queue::stat, \p mspriority_queue::empty_stat (the default, no overhead) + - \p opt::item_counter - an item counter type for \p MSPriorityQueue. + Available type: \p cds::bitop::bit_reverse_counter, \p mspriority_queue::monotonic_counter. See \p traits::item_counter for details. */ template struct make_traits { @@ -232,9 +245,10 @@ namespace cds { namespace intrusive { typedef typename opt::details::make_comparator< value_type, traits >::type key_comparator; # endif - typedef typename traits::lock_type lock_type; ///< heap's size lock type - typedef typename traits::back_off back_off; ///< Back-off strategy - typedef typename traits::stat stat; ///< internal statistics type + typedef typename traits::lock_type lock_type; ///< heap's size lock type + typedef typename traits::back_off back_off; ///< Back-off strategy + typedef typename traits::stat stat; ///< internal statistics type, see \p mspriority_queue::traits::stat + typedef typename traits::item_counter item_counter;///< Item counter type, see \p mspriority_queue::traits::item_counter protected: //@cond @@ -277,14 +291,11 @@ namespace cds { namespace intrusive { typedef typename traits::buffer::template rebind::other buffer_type ; ///< Heap array buffer type //@cond - typedef typename traits::item_counter item_counter_type; - typedef typename item_counter_type::counter_type counter_type; + typedef typename item_counter::counter_type counter_type; //@endcond - static const bool c_bFairQueue = traits::fairness; - protected: - item_counter_type m_ItemCounter ; ///< Item counter + item_counter m_ItemCounter ; ///< Item counter mutable lock_type m_Lock ; ///< Heap's size lock buffer_type m_Heap ; ///< Heap array stat m_Stat ; ///< internal statistics accumulator @@ -365,18 +376,17 @@ namespace cds { namespace intrusive { assert( nBottom < m_Heap.capacity() ); assert( nBottom > 0 ); - if ( c_bFairQueue ) { - refTop.lock(); - if ( nBottom == 1 ) { - refTop.m_nTag = tag_type( Empty ); - value_type * pVal = refTop.m_pVal; - refTop.m_pVal = nullptr; - refTop.unlock(); - m_Lock.unlock(); - m_Stat.onPopSuccess(); - return pVal; - } + refTop.lock(); + if ( nBottom == 1 ) { + refTop.m_nTag = tag_type( Empty ); + value_type * pVal = refTop.m_pVal; + refTop.m_pVal = nullptr; + refTop.unlock(); + m_Lock.unlock(); + m_Stat.onPopSuccess(); + return pVal; } + node& refBottom = m_Heap[nBottom]; refBottom.lock(); m_Lock.unlock(); @@ -385,10 +395,6 @@ namespace cds { namespace intrusive { refBottom.m_pVal = nullptr; refBottom.unlock(); - //node& refTop = m_Heap[ 1 ]; - if ( !c_bFairQueue ) - refTop.lock(); - if ( refTop.m_nTag == tag_type(Empty) ) { // nBottom == nTop refTop.unlock(); diff --git a/change.log b/change.log index fbfb9922..9eb20b9f 100644 --- a/change.log +++ b/change.log @@ -20,6 +20,7 @@ are removed. - Fixed: use-after-free bug in VyukovMPMCCycleQueue internal buffer. To prevent this bug the queue uses an uninitialized buffer now. + - Fixed: rare priority inversion bug in MSPriorityQueue - Added: for minimizing runtime of stress test the detail level for some test is added. Command line argument --detail-level=N specifies what test should be ran: each test with level not great than N will be ran. Instead of command line arg diff --git a/test/stress/pqueue/pop.cpp b/test/stress/pqueue/pop.cpp index 65f055d2..e939d691 100644 --- a/test/stress/pqueue/pop.cpp +++ b/test/stress/pqueue/pop.cpp @@ -208,14 +208,10 @@ namespace { pqueue_type pq( s_nQueueSize + 1 ); \ test( pq ); \ } - CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_dyn_fair_bitreverse_less ) - CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_dyn_fair_bitreverse_less_stat ) - CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_dyn_fair_monotonic_less ) - CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_dyn_fair_monotonic_less_stat ) - CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_dyn_unfair_bitreverse_less ) - CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_dyn_unfair_bitreverse_less_stat ) - CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_dyn_unfair_monotonic_less ) - CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_dyn_unfair_monotonic_less_stat ) + CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_dyn_bitreverse_less ) + CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_dyn_bitreverse_less_stat ) + CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_dyn_monotonic_less ) + CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_dyn_monotonic_less_stat ) CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_dyn_cmp ) //CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_dyn_mutex ) // too slow diff --git a/test/stress/pqueue/pqueue_type.h b/test/stress/pqueue/pqueue_type.h index 5e0752d1..83dee9da 100644 --- a/test/stress/pqueue/pqueue_type.h +++ b/test/stress/pqueue/pqueue_type.h @@ -396,63 +396,30 @@ namespace pqueue { { typedef co::v::initialized_dynamic_buffer< char > buffer; }; - struct traits_MSPriorityQueue_dyn_fair: public traits_MSPriorityQueue_dyn - { - enum { fairness = true }; - }; - struct traits_MSPriorityQueue_dyn_unfair: public traits_MSPriorityQueue_dyn - { - enum { fairness = false }; - }; - - - struct traits_MSPriorityQueue_dyn_fair_bitreverse_less : public traits_MSPriorityQueue_dyn_fair - { - typedef cds::bitop::bit_reverse_counter<> item_counter; - }; - typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_fair_bitreverse_less > MSPriorityQueue_dyn_fair_bitreverse_less; - - struct traits_MSPriorityQueue_dyn_fair_bitreverse_less_stat: public traits_MSPriorityQueue_dyn_fair_bitreverse_less - { - typedef cc::mspriority_queue::stat<> stat; - }; - typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_fair_bitreverse_less_stat > MSPriorityQueue_dyn_fair_bitreverse_less_stat; - - struct traits_MSPriorityQueue_dyn_fair_monotonic_less: public traits_MSPriorityQueue_dyn_fair - { - typedef cds::intrusive::mspriority_queue::monotonic_counter item_counter; - }; - typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_fair_monotonic_less > MSPriorityQueue_dyn_fair_monotonic_less; - - struct traits_MSPriorityQueue_dyn_fair_monotonic_less_stat: public traits_MSPriorityQueue_dyn_fair_monotonic_less - { - typedef cc::mspriority_queue::stat<> stat; - }; - typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_fair_monotonic_less_stat > MSPriorityQueue_dyn_fair_monotonic_less_stat; - struct traits_MSPriorityQueue_dyn_unfair_bitreverse_less: public traits_MSPriorityQueue_dyn_unfair + struct traits_MSPriorityQueue_dyn_bitreverse_less : public traits_MSPriorityQueue_dyn { typedef cds::bitop::bit_reverse_counter<> item_counter; }; - typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_unfair_bitreverse_less > MSPriorityQueue_dyn_unfair_bitreverse_less; + typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_bitreverse_less > MSPriorityQueue_dyn_bitreverse_less; - struct traits_MSPriorityQueue_dyn_unfair_bitreverse_less_stat: public traits_MSPriorityQueue_dyn_unfair_bitreverse_less + struct traits_MSPriorityQueue_dyn_bitreverse_less_stat: public traits_MSPriorityQueue_dyn_bitreverse_less { typedef cc::mspriority_queue::stat<> stat; }; - typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_unfair_bitreverse_less_stat > MSPriorityQueue_dyn_unfair_bitreverse_less_stat; + typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_bitreverse_less_stat > MSPriorityQueue_dyn_bitreverse_less_stat; - struct traits_MSPriorityQueue_dyn_unfair_monotonic_less: public traits_MSPriorityQueue_dyn_unfair + struct traits_MSPriorityQueue_dyn_monotonic_less: public traits_MSPriorityQueue_dyn { typedef cds::intrusive::mspriority_queue::monotonic_counter item_counter; }; - typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_unfair_monotonic_less > MSPriorityQueue_dyn_unfair_monotonic_less; + typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_monotonic_less > MSPriorityQueue_dyn_monotonic_less; - struct traits_MSPriorityQueue_dyn_unfair_monotonic_less_stat: public traits_MSPriorityQueue_dyn_unfair_monotonic_less + struct traits_MSPriorityQueue_dyn_monotonic_less_stat: public traits_MSPriorityQueue_dyn_monotonic_less { typedef cc::mspriority_queue::stat<> stat; }; - typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_unfair_monotonic_less_stat > MSPriorityQueue_dyn_unfair_monotonic_less_stat; + typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_monotonic_less_stat > MSPriorityQueue_dyn_monotonic_less_stat; struct traits_MSPriorityQueue_dyn_cmp : public diff --git a/test/stress/pqueue/push.cpp b/test/stress/pqueue/push.cpp index cebbab93..d66fe76e 100644 --- a/test/stress/pqueue/push.cpp +++ b/test/stress/pqueue/push.cpp @@ -169,14 +169,10 @@ namespace pqueue { pqueue_type pq( s_nQueueSize ); \ test( pq ); \ } - CDSSTRESS_MSPriorityQueue( pqueue_push, MSPriorityQueue_dyn_fair_bitreverse_less ) - CDSSTRESS_MSPriorityQueue( pqueue_push, MSPriorityQueue_dyn_fair_bitreverse_less_stat ) - CDSSTRESS_MSPriorityQueue( pqueue_push, MSPriorityQueue_dyn_fair_monotonic_less ) - CDSSTRESS_MSPriorityQueue( pqueue_push, MSPriorityQueue_dyn_fair_monotonic_less_stat ) - CDSSTRESS_MSPriorityQueue( pqueue_push, MSPriorityQueue_dyn_unfair_bitreverse_less ) - CDSSTRESS_MSPriorityQueue( pqueue_push, MSPriorityQueue_dyn_unfair_bitreverse_less_stat ) - CDSSTRESS_MSPriorityQueue( pqueue_push, MSPriorityQueue_dyn_unfair_monotonic_less ) - CDSSTRESS_MSPriorityQueue( pqueue_push, MSPriorityQueue_dyn_unfair_monotonic_less_stat ) + CDSSTRESS_MSPriorityQueue( pqueue_push, MSPriorityQueue_dyn_bitreverse_less ) + CDSSTRESS_MSPriorityQueue( pqueue_push, MSPriorityQueue_dyn_bitreverse_less_stat ) + CDSSTRESS_MSPriorityQueue( pqueue_push, MSPriorityQueue_dyn_monotonic_less ) + CDSSTRESS_MSPriorityQueue( pqueue_push, MSPriorityQueue_dyn_monotonic_less_stat ) CDSSTRESS_MSPriorityQueue( pqueue_push, MSPriorityQueue_dyn_cmp ) //CDSSTRESS_MSPriorityQueue( pqueue_push, MSPriorityQueue_dyn_mutex ) // too slow diff --git a/test/stress/pqueue/push_pop.cpp b/test/stress/pqueue/push_pop.cpp index 85265748..b529c69d 100644 --- a/test/stress/pqueue/push_pop.cpp +++ b/test/stress/pqueue/push_pop.cpp @@ -223,14 +223,10 @@ namespace { pqueue_type pq( s_nQueueSize ); \ test( pq ); \ } - CDSSTRESS_MSPriorityQueue( pqueue_push_pop, MSPriorityQueue_dyn_fair_bitreverse_less ) - CDSSTRESS_MSPriorityQueue( pqueue_push_pop, MSPriorityQueue_dyn_fair_bitreverse_less_stat ) - CDSSTRESS_MSPriorityQueue( pqueue_push_pop, MSPriorityQueue_dyn_fair_monotonic_less ) - CDSSTRESS_MSPriorityQueue( pqueue_push_pop, MSPriorityQueue_dyn_fair_monotonic_less_stat ) - CDSSTRESS_MSPriorityQueue( pqueue_push_pop, MSPriorityQueue_dyn_unfair_bitreverse_less ) - CDSSTRESS_MSPriorityQueue( pqueue_push_pop, MSPriorityQueue_dyn_unfair_bitreverse_less_stat ) - CDSSTRESS_MSPriorityQueue( pqueue_push_pop, MSPriorityQueue_dyn_unfair_monotonic_less ) - CDSSTRESS_MSPriorityQueue( pqueue_push_pop, MSPriorityQueue_dyn_unfair_monotonic_less_stat ) + CDSSTRESS_MSPriorityQueue( pqueue_push_pop, MSPriorityQueue_dyn_bitreverse_less ) + CDSSTRESS_MSPriorityQueue( pqueue_push_pop, MSPriorityQueue_dyn_bitreverse_less_stat ) + CDSSTRESS_MSPriorityQueue( pqueue_push_pop, MSPriorityQueue_dyn_monotonic_less ) + CDSSTRESS_MSPriorityQueue( pqueue_push_pop, MSPriorityQueue_dyn_monotonic_less_stat ) CDSSTRESS_MSPriorityQueue( pqueue_push_pop, MSPriorityQueue_dyn_cmp ) //CDSSTRESS_MSPriorityQueue( pqueue_push_pop, MSPriorityQueue_dyn_mutex ) // too slow diff --git a/test/unit/pqueue/intrusive_mspqueue.cpp b/test/unit/pqueue/intrusive_mspqueue.cpp index c5e29c07..ee95693c 100644 --- a/test/unit/pqueue/intrusive_mspqueue.cpp +++ b/test/unit/pqueue/intrusive_mspqueue.cpp @@ -267,4 +267,32 @@ namespace { test( *pq ); } + TEST_F( IntrusiveMSPQueue, bit_reverse_counter ) + { + typedef cds::intrusive::MSPriorityQueue< value_type, + cds::intrusive::mspriority_queue::make_traits< + cds::opt::buffer< dyn_buffer_type > + , cds::opt::less< less > + , cds::opt::item_counter< cds::bitop::bit_reverse_counter<>> + >::type + > pqueue; + + pqueue pq( c_nCapacity ); + test( pq ); + } + + TEST_F( IntrusiveMSPQueue, monotonic_counter ) + { + typedef cds::intrusive::MSPriorityQueue< value_type, + cds::intrusive::mspriority_queue::make_traits< + cds::opt::buffer< dyn_buffer_type > + , cds::opt::less< less > + , cds::opt::item_counter< cds::intrusive::mspriority_queue::monotonic_counter > + >::type + > pqueue; + + pqueue pq( c_nCapacity ); + test( pq ); + } + } // namespace diff --git a/test/unit/pqueue/mspqueue.cpp b/test/unit/pqueue/mspqueue.cpp index 88ce0373..cf278ef3 100644 --- a/test/unit/pqueue/mspqueue.cpp +++ b/test/unit/pqueue/mspqueue.cpp @@ -282,4 +282,32 @@ namespace { test( *pq ); } + TEST_F( MSPQueue, bit_reverse_counter ) + { + typedef cds::container::MSPriorityQueue< value_type, + cds::container::mspriority_queue::make_traits< + cds::opt::buffer< dyn_buffer_type > + ,cds::opt::less< less > + ,cds::opt::item_counter< cds::bitop::bit_reverse_counter<>> + >::type + > pqueue; + + pqueue pq( c_nCapacity ); + test( pq ); + } + + TEST_F( MSPQueue, monotonic_counter ) + { + typedef cds::container::MSPriorityQueue< value_type, + cds::container::mspriority_queue::make_traits< + cds::opt::buffer< dyn_buffer_type > + , cds::opt::less< less > + , cds::opt::item_counter< cds::container::mspriority_queue::monotonic_counter> + >::type + > pqueue; + + pqueue pq( c_nCapacity ); + test( pq ); + } + } // namespace -- 2.34.1