Fixed rare priority inversion bug in MSPriorityQueue
authorkhizmax <libcds.dev@gmail.com>
Mon, 1 Aug 2016 06:14:50 +0000 (09:14 +0300)
committerkhizmax <libcds.dev@gmail.com>
Mon, 1 Aug 2016 06:14:50 +0000 (09:14 +0300)
Revert "fixed potential buffer overflow"
This reverts commit df51f37347c12f42f142dc23858d6bd3cb60c84c.

cds/details/bit_reverse_counter.h
cds/intrusive/mspriority_queue.h
test/stress/pqueue/pop.cpp
test/stress/pqueue/pqueue_type.h
test/stress/pqueue/push.cpp
test/stress/pqueue/push_pop.cpp
test/unit/misc/bitop.cpp

index 6bcadd6..90c9d0a 100644 (file)
@@ -71,6 +71,7 @@ namespace cds { namespace bitop {
 
         counter_type dec()
         {
+            counter_type ret = m_nReversed;
             --m_nCounter;
             int nBit;
             for ( nBit = m_nHighBit - 1; nBit >= 0; --nBit ) {
@@ -81,7 +82,7 @@ namespace cds { namespace bitop {
                 m_nReversed = m_nCounter;
                 --m_nHighBit;
             }
-            return m_nReversed;
+            return ret;
         }
 
         counter_type    value() const
@@ -93,6 +94,11 @@ namespace cds { namespace bitop {
         {
             return m_nReversed;
         }
+
+        int high_bit() const
+        {
+            return m_nHighBit;
+        }
     };
 
 }}   // namespace cds::bitop
index 5d3d080..9128fca 100644 (file)
@@ -93,6 +93,34 @@ namespace cds { namespace intrusive {
             //@endcond
         };
 
+        class monotonic_counter
+        {
+        public:
+            typedef size_t counter_type;
+
+            monotonic_counter()
+                : m_nCounter(0)
+            {}
+
+            size_t inc()
+            {
+                return ++m_nCounter;
+            }
+
+            size_t dec()
+            {
+                return m_nCounter--;
+            }
+
+            size_t value() const
+            {
+                return m_nCounter;
+            }
+
+        private:
+            size_t m_nCounter;
+        };
+
         /// MSPriorityQueue traits
         struct traits {
             /// Storage type
@@ -103,7 +131,7 @@ namespace cds { namespace intrusive {
                 the \p buffer::rebind member metafunction is called to change type
                 of values stored in the buffer.
             */
-            typedef opt::v::initialized_dynamic_buffer<void *, CDS_DEFAULT_ALLOCATOR, false>  buffer;
+            typedef opt::v::initialized_dynamic_buffer<void *>  buffer;
 
             /// Priority compare functor
             /**
@@ -117,7 +145,7 @@ namespace cds { namespace intrusive {
             */
             typedef opt::none       less;
 
-            /// Type of mutual-exclusion lock
+            /// Type of mutual-exclusion lock. The lock is not need to be recursive.
             typedef cds::sync::spin lock_type;
 
             /// Back-off strategy
@@ -129,6 +157,12 @@ namespace cds { namespace intrusive {
                 or any other with interface like \p %mspriority_queue::stat
             */
             typedef empty_stat      stat;
+
+            /// Item counter type
+            typedef cds::bitop::bit_reverse_counter<> item_counter;
+
+            /// Fairness
+            static bool const fairness = true;
         };
 
         /// Metafunction converting option list to traits
@@ -243,10 +277,12 @@ namespace cds { namespace intrusive {
         typedef typename traits::buffer::template rebind<node>::other   buffer_type ;   ///< Heap array buffer type
 
         //@cond
-        typedef cds::bitop::bit_reverse_counter<>           item_counter_type;
+        typedef typename traits::item_counter  item_counter_type;
         typedef typename item_counter_type::counter_type    counter_type;
         //@endcond
 
+        static const bool c_bFairQueue = traits::fairness;
+
     protected:
         item_counter_type   m_ItemCounter   ;   ///< Item counter
         mutable lock_type   m_Lock          ;   ///< Heap's size lock
@@ -291,12 +327,7 @@ namespace cds { namespace intrusive {
             }
 
             counter_type i = m_ItemCounter.inc();
-            if ( i >= m_Heap.capacity() ) {
-                // the heap is full
-                m_Lock.unlock();
-                m_Stat.onPushFailed();
-                return false;
-            }
+            assert( i < m_Heap.capacity() );
 
             node& refNode = m_Heap[i];
             refNode.lock();
@@ -321,6 +352,8 @@ namespace cds { namespace intrusive {
         */
         value_type * pop()
         {
+            node& refTop = m_Heap[1];
+
             m_Lock.lock();
             if ( m_ItemCounter.value() == 0 ) {
                 // the heap is empty
@@ -328,12 +361,23 @@ namespace cds { namespace intrusive {
                 m_Stat.onPopFailed();
                 return nullptr;
             }
-            counter_type nBottom = m_ItemCounter.reversed_value();
-            m_ItemCounter.dec();
+            counter_type nBottom = m_ItemCounter.dec();
             assert( nBottom < m_Heap.capacity() );
             assert( nBottom > 0 );
 
-            node& refBottom = m_Heap[ nBottom ];
+            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;
+                }
+            }
+            node& refBottom = m_Heap[nBottom];
             refBottom.lock();
             m_Lock.unlock();
             refBottom.m_nTag = tag_type(Empty);
@@ -341,8 +385,10 @@ namespace cds { namespace intrusive {
             refBottom.m_pVal = nullptr;
             refBottom.unlock();
 
-            node& refTop = m_Heap[ 1 ];
-            refTop.lock();
+            //node& refTop = m_Heap[ 1 ];
+            if ( !c_bFairQueue )
+                refTop.lock();
+
             if ( refTop.m_nTag == tag_type(Empty) ) {
                 // nBottom == nTop
                 refTop.unlock();
index b6f2f93..65f055d 100644 (file)
@@ -87,7 +87,8 @@ namespace {
                                 m_arrFailedPops.back().next_key = val.key;
                             prevPopFailed = false;
                         }
-                        nPrevKey = val.key;
+                        if ( nPrevKey > val.key )
+                            nPrevKey = val.key;
                     }
 
                 }
@@ -117,9 +118,6 @@ namespace {
         {
             cds_test::thread_pool& pool = get_pool();
 
-            propout() << std::make_pair( "thread_count", s_nThreadCount )
-                << std::make_pair( "push_count", s_nQueueSize );
-
             // push
             {
                 std::vector< size_t > arr;
@@ -137,6 +135,9 @@ namespace {
                 s_nQueueSize -= nPushError;
             }
 
+            propout() << std::make_pair( "thread_count", s_nThreadCount )
+                << std::make_pair( "push_count", s_nQueueSize );
+
             // pop
             {
                 pool.add( new Consumer<PQueue>( pool, q ), s_nThreadCount );
@@ -207,8 +208,14 @@ namespace {
         pqueue_type pq( s_nQueueSize + 1 ); \
         test( pq ); \
     }
-    CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_dyn_less )
-    CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_dyn_less_stat )
+    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_cmp )
     //CDSSTRESS_MSPriorityQueue( pqueue_pop, MSPriorityQueue_dyn_mutex ) // too slow
 
index 8e20517..5e0752d 100644 (file)
@@ -25,7 +25,7 @@
     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.     
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
 #ifndef CDSSTRESS_PQUEUE_TYPES_H
@@ -392,20 +392,68 @@ namespace pqueue {
         {};
         typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_static_mutex > MSPriorityQueue_static_mutex;
 
-        struct traits_MSPriorityQueue_dyn_less : public
-            cc::mspriority_queue::make_traits<
-                co::buffer< co::v::initialized_dynamic_buffer< char > >
-            >::type
-        {};
-        typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_less > MSPriorityQueue_dyn_less;
+        struct traits_MSPriorityQueue_dyn: public cc::mspriority_queue::traits
+        {
+            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
+        {
+            typedef cds::bitop::bit_reverse_counter<> item_counter;
+        };
+        typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_unfair_bitreverse_less > MSPriorityQueue_dyn_unfair_bitreverse_less;
+
+        struct traits_MSPriorityQueue_dyn_unfair_bitreverse_less_stat: public traits_MSPriorityQueue_dyn_unfair_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;
+
+        struct traits_MSPriorityQueue_dyn_unfair_monotonic_less: public traits_MSPriorityQueue_dyn_unfair
+        {
+            typedef cds::intrusive::mspriority_queue::monotonic_counter item_counter;
+        };
+        typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_unfair_monotonic_less > MSPriorityQueue_dyn_unfair_monotonic_less;
+
+        struct traits_MSPriorityQueue_dyn_unfair_monotonic_less_stat: public traits_MSPriorityQueue_dyn_unfair_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;
 
-        struct traits_MSPriorityQueue_dyn_less_stat : public
-            cc::mspriority_queue::make_traits <
-                co::buffer< co::v::initialized_dynamic_buffer< char > >
-                , co::stat < cc::mspriority_queue::stat<> >
-            > ::type
-        {};
-        typedef cc::MSPriorityQueue< Value, traits_MSPriorityQueue_dyn_less_stat > MSPriorityQueue_dyn_less_stat;
 
         struct traits_MSPriorityQueue_dyn_cmp : public
             cc::mspriority_queue::make_traits <
index 990820a..cebbab9 100644 (file)
@@ -25,7 +25,7 @@
     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.     
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
 #include "pqueue_type.h"
@@ -169,8 +169,14 @@ namespace pqueue {
         pqueue_type pq( s_nQueueSize ); \
         test( pq ); \
     }
-    CDSSTRESS_MSPriorityQueue( pqueue_push, MSPriorityQueue_dyn_less )
-    CDSSTRESS_MSPriorityQueue( pqueue_push, MSPriorityQueue_dyn_less_stat )
+    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_cmp )
     //CDSSTRESS_MSPriorityQueue( pqueue_push, MSPriorityQueue_dyn_mutex ) // too slow
 
index a682835..8526574 100644 (file)
@@ -25,7 +25,7 @@
     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.     
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
 #include "pqueue_type.h"
@@ -223,10 +223,16 @@ namespace {
         pqueue_type pq( s_nQueueSize ); \
         test( pq ); \
     }
-    CDSSTRESS_MSPriorityQueue( pqueue_push_pop, MSPriorityQueue_dyn_less )
-    CDSSTRESS_MSPriorityQueue( pqueue_push_pop, MSPriorityQueue_dyn_less_stat )
+    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_cmp )
-    //CDSSTRESS_MSPriorityQueue( pqueue_push_pop, MSPriorityQueue_dyn_mutex ) too slow
+    //CDSSTRESS_MSPriorityQueue( pqueue_push_pop, MSPriorityQueue_dyn_mutex ) // too slow
 
 #define CDSSTRESS_MSPriorityQueue_static( fixture_t, pqueue_t ) \
     TEST_F( fixture_t, pqueue_t ) \
index 97a7589..54670dc 100644 (file)
     SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
     CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
     OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
-    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.     
+    OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */
 
 #include <gtest/gtest.h>
 
 #include <cds/algo/int_algo.h>
-#include <cds/os/timer.h>
+//#include <cds/details/bit_reverse_counter.h>
 
 namespace {
     class bitop : public ::testing::Test
@@ -134,4 +134,27 @@ namespace {
         }
     }
 
+    /*
+    TEST_F( bitop, bit_reverse_counter )
+    {
+        cds::bitop::bit_reverse_counter<> c;
+
+        while ( c.value() < 8 ) {
+            size_t res = c.inc();
+            std::cout << "inc result: " << res
+                      << " value: " << c.value()
+                      << " reversed: " << c.reversed_value()
+                      << " high_bit: " << c.high_bit() << "\n";
+        }
+
+        while ( c.value() > 0 ) {
+            size_t res = c.dec();
+            std::cout << "dec result: " << res
+                << " value: " << c.value()
+                << " reversed: " << c.reversed_value()
+                << " high_bit: " << c.high_bit() << "\n";
+        }
+    }
+    */
+
 } // namespace