From: khizmax Date: Mon, 1 Aug 2016 06:14:50 +0000 (+0300) Subject: Fixed rare priority inversion bug in MSPriorityQueue X-Git-Tag: v2.2.0~166 X-Git-Url: http://plrg.eecs.uci.edu/git/?p=libcds.git;a=commitdiff_plain;h=c12c4c5845f831ccbb3a3bc97e3e12cb53ce62de Fixed rare priority inversion bug in MSPriorityQueue Revert "fixed potential buffer overflow" This reverts commit df51f37347c12f42f142dc23858d6bd3cb60c84c. --- diff --git a/cds/details/bit_reverse_counter.h b/cds/details/bit_reverse_counter.h index 6bcadd66..90c9d0ad 100644 --- a/cds/details/bit_reverse_counter.h +++ b/cds/details/bit_reverse_counter.h @@ -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 diff --git a/cds/intrusive/mspriority_queue.h b/cds/intrusive/mspriority_queue.h index 5d3d0805..9128fca8 100644 --- a/cds/intrusive/mspriority_queue.h +++ b/cds/intrusive/mspriority_queue.h @@ -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 buffer; + typedef opt::v::initialized_dynamic_buffer 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::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(); diff --git a/test/stress/pqueue/pop.cpp b/test/stress/pqueue/pop.cpp index b6f2f935..65f055d2 100644 --- a/test/stress/pqueue/pop.cpp +++ b/test/stress/pqueue/pop.cpp @@ -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( 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 diff --git a/test/stress/pqueue/pqueue_type.h b/test/stress/pqueue/pqueue_type.h index 8e20517b..5e0752d1 100644 --- a/test/stress/pqueue/pqueue_type.h +++ b/test/stress/pqueue/pqueue_type.h @@ -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 < diff --git a/test/stress/pqueue/push.cpp b/test/stress/pqueue/push.cpp index 990820a1..cebbab93 100644 --- a/test/stress/pqueue/push.cpp +++ b/test/stress/pqueue/push.cpp @@ -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 diff --git a/test/stress/pqueue/push_pop.cpp b/test/stress/pqueue/push_pop.cpp index a6828351..85265748 100644 --- a/test/stress/pqueue/push_pop.cpp +++ b/test/stress/pqueue/push_pop.cpp @@ -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 ) \ diff --git a/test/unit/misc/bitop.cpp b/test/unit/misc/bitop.cpp index 97a75897..54670dc0 100644 --- a/test/unit/misc/bitop.cpp +++ b/test/unit/misc/bitop.cpp @@ -25,13 +25,13 @@ 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 #include -#include +//#include 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