Fixed priority inversion bug in MSPriorityQueue
authorkhizmax <khizmax@gmail.com>
Mon, 1 Aug 2016 08:30:51 +0000 (11:30 +0300)
committerkhizmax <khizmax@gmail.com>
Mon, 1 Aug 2016 08:30:51 +0000 (11:30 +0300)
cds/container/mspriority_queue.h
cds/intrusive/mspriority_queue.h
change.log
test/stress/pqueue/pop.cpp
test/stress/pqueue/pqueue_type.h
test/stress/pqueue/push.cpp
test/stress/pqueue/push_pop.cpp
test/unit/pqueue/intrusive_mspqueue.cpp
test/unit/pqueue/mspqueue.cpp

index a846de6..77e7ea0 100644 (file)
@@ -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 <typename... Options>
         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<value_type>::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
index 9128fca..fb920a8 100644 (file)
@@ -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 <a href="http://www.research.ibm.com/people/m/michael/ipl-1996.pdf">original paper</a>,
+                  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 2<sup>K</sup>
+                  where \p K - the nearest power of two such that <tt>2<sup>K</sup> >= N</tt>.
+                - \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 <typename... Options>
         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<node>::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();
index fbfb992..9eb20b9 100644 (file)
@@ -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
index 65f055d..e939d69 100644 (file)
@@ -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
 
index 5e0752d..83dee9d 100644 (file)
@@ -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
index cebbab9..d66fe76 100644 (file)
@@ -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
 
index 8526574..b529c69 100644 (file)
@@ -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
 
index c5e29c0..ee95693 100644 (file)
@@ -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
index 88ce037..cf278ef 100644 (file)
@@ -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