IterableList: fixed a complex bug that can be called "ABA problem of null pointer"
authorkhizmax <libcds.dev@gmail.com>
Sun, 30 Oct 2016 19:06:57 +0000 (22:06 +0300)
committerkhizmax <libcds.dev@gmail.com>
Sun, 30 Oct 2016 19:06:57 +0000 (22:06 +0300)
16 files changed:
cds/container/details/make_split_list_set_iterable_list.h
cds/container/details/make_split_list_set_lazy_list.h
cds/container/details/make_split_list_set_michael_list.h
cds/container/split_list_map_nogc.h
cds/container/split_list_map_rcu.h
cds/container/split_list_set.h
cds/container/split_list_set_nogc.h
cds/container/split_list_set_rcu.h
cds/intrusive/details/iterable_list_base.h
cds/intrusive/details/split_list_base.h
cds/intrusive/impl/iterable_list.h
cds/intrusive/split_list_nogc.h
cds/intrusive/split_list_rcu.h
test/include/cds_test/stat_iterable_list_out.h
test/stress/map/map_type_split_list.h
test/stress/set/set_type_split_list.h

index f38edb5..87e511e 100644 (file)
@@ -51,9 +51,10 @@ namespace cds { namespace container { namespace details {
             value_type  m_Value;
 
             template <typename Q>
-            explicit node_type( Q const& v )
-                : m_Value(v)
+            explicit node_type( Q&& v )
+                : m_Value( std::forward<Q>( v ))
             {}
+
             template <typename Q, typename... Args>
             explicit node_type( Q&& q, Args&&... args )
                 : m_Value( std::forward<Q>(q), std::forward<Args>(args)... )
@@ -116,6 +117,7 @@ namespace cds { namespace container { namespace details {
                 {
                     return base_class::operator()( key_accessor()( v.m_Value ));
                 }
+
                 template <typename Q>
                 size_t operator()( Q const& k ) const
                 {
index f2fe26a..2d82a00 100644 (file)
@@ -57,8 +57,8 @@ namespace cds { namespace container { namespace details {
             value_type  m_Value;
 
             template <typename Q>
-            explicit node_type( const Q& v )
-                : m_Value(v)
+            explicit node_type( Q&& v )
+                : m_Value( std::forward<Q>( v ))
             {}
 
             template <typename Q, typename... Args>
index 73ff261..a16679e 100644 (file)
@@ -52,8 +52,8 @@ namespace cds { namespace container { namespace details {
             value_type  m_Value;
 
             template <typename Q>
-            explicit node_type( Q const& v )
-                : m_Value(v)
+            explicit node_type( Q&& v )
+                : m_Value( std::forward<Q>( v ))
             {}
             template <typename Q, typename... Args>
             explicit node_type( Q&& q, Args&&... args )
index 82f9237..b005cd9 100644 (file)
@@ -376,6 +376,12 @@ namespace cds { namespace container {
         {
             return base_class::statistics();
         }
+
+        /// Returns internal statistics for \p ordered_list
+        typename ordered_list::stat const& list_statistics() const
+        {
+            return base_class::list_statistics();
+        }
     };
 }}  // namespace cds::container
 
index 9dc68aa..800f2ed 100644 (file)
@@ -707,6 +707,12 @@ namespace cds { namespace container {
         {
             return base_class::statistics();
         }
+
+        /// Returns internal statistics for \p ordered_list
+        typename ordered_list::stat const& list_statistics() const
+        {
+            return base_class::list_statistics();
+        }
     };
 
 }} // namespace cds::container
index acb24ad..cf1ed65 100644 (file)
@@ -389,9 +389,9 @@ namespace cds { namespace container {
             Returns \p true if \p val is inserted into the set, \p false otherwise.
         */
         template <typename Q>
-        bool insert( Q const& val )
+        bool insert( Q&& val )
         {
-            return insert_node( alloc_node( val ));
+            return insert_node( alloc_node( std::forward<Q>( val )));
         }
 
         /// Inserts new node
@@ -414,9 +414,9 @@ namespace cds { namespace container {
             synchronization.
         */
         template <typename Q, typename Func>
-        bool insert( Q const& val, Func f )
+        bool insert( Q&& val, Func f )
         {
-            scoped_node_ptr pNode( alloc_node( val ));
+            scoped_node_ptr pNode( alloc_node( std::forward<Q>( val )));
 
             if ( base_class::insert( *pNode, [&f](node_type& node) { f( node.m_Value ) ; } )) {
                 pNode.release();
@@ -457,7 +457,7 @@ namespace cds { namespace container {
 #endif
         upsert( Q&& val, bool bAllowInsert = true )
         {
-            scoped_node_ptr pNode( alloc_node( val ));
+            scoped_node_ptr pNode( alloc_node( std::forward<Q>( val )));
 
             auto bRet = base_class::upsert( *pNode, bAllowInsert );
 
@@ -514,9 +514,9 @@ namespace cds { namespace container {
             std::pair<bool, bool>
         >::type
 #endif
-        update( Q const& val, Func func, bool bAllowInsert = true )
+        update( Q&& val, Func func, bool bAllowInsert = true )
         {
-            scoped_node_ptr pNode( alloc_node( val ));
+            scoped_node_ptr pNode( alloc_node( std::forward<Q>( val )));
 
             auto bRet = base_class::update( *pNode,
                 [&func, &val]( bool bNew, node_type& item,  node_type const& /*val*/ ) {
@@ -533,9 +533,9 @@ namespace cds { namespace container {
             std::is_same<Q, Q>::value && is_iterable_list<ordered_list>::value,
             std::pair<bool, bool>
         >::type
-        update( Q const& val, Func func, bool bAllowInsert = true )
+        update( Q&& val, Func func, bool bAllowInsert = true )
         {
-            scoped_node_ptr pNode( alloc_node( val ));
+            scoped_node_ptr pNode( alloc_node( std::forward<Q>( val )));
 
             auto bRet = base_class::update( *pNode,
                 [&func]( node_type& item, node_type* old ) {
@@ -900,12 +900,6 @@ namespace cds { namespace container {
         using base_class::extract_;
         using base_class::get_;
 
-        template <typename Q>
-        static node_type * alloc_node( Q const& v )
-        {
-            return cxx_node_allocator().New( v );
-        }
-
         template <typename... Args>
         static node_type * alloc_node( Args&&... args )
         {
index 33b85e7..ffc98b8 100644 (file)
@@ -445,6 +445,12 @@ namespace cds { namespace container {
         {
             return base_class::statistics();
         }
+
+        /// Returns internal statistics for \p ordered_list
+        typename ordered_list::stat const& list_statistics() const
+        {
+            return base_class::list_statistics();
+        }
     };
 
 }}  // namespace cds::container
index 49d11e2..a4a9bc6 100644 (file)
@@ -993,6 +993,12 @@ namespace cds { namespace container {
         {
             return base_class::statistics();
         }
+
+        /// Returns internal statistics for \p ordered_list
+        typename ordered_list::stat const& list_statistics() const
+        {
+            return base_class::list_statistics();
+        }
     };
 }}  // namespace cds::container
 
index 5fdce3a..83ca5d3 100644 (file)
@@ -81,6 +81,7 @@ namespace cds { namespace intrusive {
             event_counter   m_nReuseNode;       ///< Number of reusing empty node when inserting/updating
             event_counter   m_nNodeMarkFailed;  ///< Number of unsuccessful marking attempts when we try to insert new data
             event_counter   m_nNodeSeqBreak;    ///< Number of breaking sequence events of \p prev -> \p next node when we try to insert new data
+            event_counter   m_nNullPrevABA;     ///< Number of ABA-problem for \p nullptr prev node
             event_counter   m_nNewNodeCreated;  ///< Number of new node created when we try to insert new data
             event_counter   m_nUpdateNew;       ///< Number of new item inserted for \p update()
             event_counter   m_nUpdateExisting;  ///< Number of existing item updates
@@ -102,6 +103,7 @@ namespace cds { namespace intrusive {
             void onReuseNode()          { ++m_nReuseNode;       }
             void onNodeMarkFailed()     { ++m_nNodeMarkFailed;  }
             void onNodeSeqBreak()       { ++m_nNodeSeqBreak;    }
+            void onNullPrevABA()        { ++m_nNullPrevABA;     }
             void onNewNodeCreated()     { ++m_nNewNodeCreated;  }
             void onUpdateNew()          { ++m_nUpdateNew;       }
             void onUpdateExisting()     { ++m_nUpdateExisting;  }
@@ -127,6 +129,7 @@ namespace cds { namespace intrusive {
             void onReuseNode()                  const {}
             void onNodeMarkFailed()             const {}
             void onNodeSeqBreak()               const {}
+            void onNullPrevABA()                const {}
             void onNewNodeCreated()             const {}
             void onUpdateNew()                  const {}
             void onUpdateExisting()             const {}
@@ -158,6 +161,7 @@ namespace cds { namespace intrusive {
             void onReuseNode()       { m_stat.onReuseNode();     }
             void onNodeMarkFailed()  { m_stat.onNodeMarkFailed();}
             void onNodeSeqBreak()    { m_stat.onNodeSeqBreak();  }
+            void onNullPrevABA()     { m_stat.onNullPrevABA();   }
             void onNewNodeCreated()  { m_stat.onNewNodeCreated();}
             void onUpdateNew()       { m_stat.onUpdateNew();     }
             void onUpdateExisting()  { m_stat.onUpdateExisting();}
index d24ddb3..5e68bc8 100644 (file)
@@ -638,10 +638,11 @@ namespace cds { namespace intrusive {
                 if ( segment.load( memory_model::memory_order_relaxed ) == nullptr ) {
                     table_entry* pNewSegment = allocate_segment();
                     table_entry * pNull = nullptr;
-                    if ( !segment.compare_exchange_strong( pNull, pNewSegment, memory_model::memory_order_release, atomics::memory_order_relaxed )) {
+                    if ( !segment.compare_exchange_strong( pNull, pNewSegment, memory_model::memory_order_release, atomics::memory_order_relaxed ))
                         destroy_segment( pNewSegment );
-                    }
                 }
+
+                assert( segment.load( atomics::memory_order_relaxed )[nBucket & (m_metrics.nSegmentSize - 1)].load( atomics::memory_order_relaxed ) == nullptr );
                 segment.load(memory_model::memory_order_acquire)[ nBucket & (m_metrics.nSegmentSize - 1) ].store( pNode, memory_model::memory_order_release );
             }
 
@@ -962,10 +963,21 @@ namespace cds { namespace intrusive {
                         return base_class()(q.val, v);
                     }
 
-                    template <typename Q1, typename Q2>
-                    int operator()( Q1 const& v1, Q2 const& v2 ) const
+                    int operator()( value_type const& lhs, value_type const& rhs ) const
                     {
-                        return base_class()(v1, v2);
+                        splitlist_node_type const * n1 = static_cast<splitlist_node_type const *>(native_node_traits::to_node_ptr( lhs ));
+                        splitlist_node_type const * n2 = static_cast<splitlist_node_type const *>(native_node_traits::to_node_ptr( rhs ));
+                        if ( n1->m_nHash != n2->m_nHash )
+                            return n1->m_nHash < n2->m_nHash ? -1 : 1;
+
+                        if ( n1->is_dummy() ) {
+                            assert( n2->is_dummy() );
+                            return 0;
+                        }
+
+                        assert( !n1->is_dummy() && !n2->is_dummy() );
+
+                        return native_key_comparator()( lhs, rhs );
                     }
                 };
 
@@ -1027,9 +1039,8 @@ namespace cds { namespace intrusive {
                 {
                     void operator()( value_type * v )
                     {
-                        hash_node* p = static_cast<hash_node*>( v );
-                        if ( !p->is_dummy())
-                            native_disposer()(v);
+                        if ( !static_cast<hash_node*>( v )->is_dummy())
+                            native_disposer()( v );
                     }
                 };
 
@@ -1041,6 +1052,7 @@ namespace cds { namespace intrusive {
                     aux_node()
                     {
                         typedef typename native_ordered_list::node_type list_node_type;
+
                         list_node_type::data.store( typename list_node_type::marked_data_ptr(
                             static_cast<value_type*>( static_cast<hash_node *>( this ))),
                             atomics::memory_order_release
@@ -1098,10 +1110,21 @@ namespace cds { namespace intrusive {
                         return base_class()(q.val, v);
                     }
 
-                    template <typename Q1, typename Q2>
-                    int operator()( Q1 const& v1, Q2 const& v2 ) const
+                    int operator()( value_type const& lhs, value_type const& rhs ) const
                     {
-                        return base_class()(v1, v2);
+                        hash_node const& n1 = static_cast<hash_node const&>( lhs );
+                        hash_node const& n2 = static_cast<hash_node const&>( rhs );
+                        if ( n1.m_nHash != n2.m_nHash )
+                            return n1.m_nHash < n2.m_nHash ? -1 : 1;
+
+                        if ( n1.is_dummy() ) {
+                            assert( n2.is_dummy() );
+                            return 0;
+                        }
+
+                        assert( !n1.is_dummy() && !n2.is_dummy() );
+
+                        return base_class()( lhs, rhs );
                     }
                 };
 
index 3cb3fd8..5ef08b1 100644 (file)
@@ -147,7 +147,7 @@ namespace cds { namespace intrusive {
 
         typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer
 
-        static CDS_CONSTEXPR const size_t c_nHazardPtrCount = 3; ///< Count of hazard pointer required for the algorithm
+        static CDS_CONSTEXPR const size_t c_nHazardPtrCount = 4; ///< Count of hazard pointer required for the algorithm
 
         //@cond
         // Rebind traits (split-list support)
@@ -852,7 +852,7 @@ namespace cds { namespace intrusive {
                     return false;
                 }
 
-                if ( link_aux_node( pNode, pos )) {
+                if ( link_aux_node( pNode, pos, pHead )) {
                     ++m_ItemCounter;
                     m_Stat.onInsertSuccess();
                     return true;
@@ -872,7 +872,7 @@ namespace cds { namespace intrusive {
                     return false;
                 }
 
-                if ( link_data( &val, pos )) {
+                if ( link_data( &val, pos, pHead )) {
                     ++m_ItemCounter;
                     m_Stat.onInsertSuccess();
                     return true;
@@ -896,7 +896,7 @@ namespace cds { namespace intrusive {
                     return false;
                 }
 
-                if ( link_data( &val, pos )) {
+                if ( link_data( &val, pos, pHead )) {
                     f( val );
                     ++m_ItemCounter;
                     m_Stat.onInsertSuccess();
@@ -939,7 +939,7 @@ namespace cds { namespace intrusive {
                         return std::make_pair( false, false );
                     }
 
-                    if ( link_data( &val, pos )) {
+                    if ( link_data( &val, pos, pHead )) {
                         func( val, static_cast<value_type*>( nullptr ));
                         ++m_ItemCounter;
                         m_Stat.onUpdateNew();
@@ -1247,7 +1247,7 @@ namespace cds { namespace intrusive {
             }
         }
 
-        bool link_data( value_type * pVal, insert_position& pos )
+        bool link_data( value_type* pVal, insert_position& pos, node_type* pHead )
         {
             assert( pos.pPrev != nullptr );
             assert( pos.pCur != nullptr );
@@ -1266,6 +1266,7 @@ namespace cds { namespace intrusive {
             marked_data_ptr valPrev( pos.pPrevVal );
             if ( !pos.pPrev->data.compare_exchange_strong( valPrev, valPrev | 1, memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
                 pos.pCur->data.store( valCur, memory_model::memory_order_relaxed );
+
                 m_Stat.onNodeMarkFailed();
                 return false;
             }
@@ -1275,12 +1276,26 @@ namespace cds { namespace intrusive {
                 // sequence pPrev - pCur is broken
                 pos.pPrev->data.store( valPrev, memory_model::memory_order_relaxed );
                 pos.pCur->data.store( valCur, memory_model::memory_order_relaxed );
+
                 m_Stat.onNodeSeqBreak();
                 return false;
             }
 
-            if ( pos.pPrev != pos.pHead && pos.pPrevVal == nullptr )
-            {
+            if ( pos.pPrevVal == nullptr ) {
+                // Check ABA-problem for prev
+                // There is a possibility that the current thread was preempted
+                // on entry of this function. Other threads can link data to prev
+                // and then remove it. As a result, the order of items may be changed
+                if ( find_prev( pHead, *pVal ) != pos.pPrev ) {
+                    pos.pPrev->data.store( valPrev, memory_model::memory_order_relaxed );
+                    pos.pCur->data.store( valCur, memory_model::memory_order_relaxed );
+
+                    m_Stat.onNullPrevABA();
+                    return false;
+                }
+            }
+
+            if ( pos.pPrev != pos.pHead && pos.pPrevVal == nullptr ) {
                 // reuse pPrev
 
                 // Set pos.pPrev data if it is null
@@ -1319,7 +1334,7 @@ namespace cds { namespace intrusive {
         }
 
         // split-list support
-        bool link_aux_node( node_type * pNode, insert_position& pos )
+        bool link_aux_node( node_type * pNode, insert_position& pos, node_type* pHead )
         {
             assert( pos.pPrev != nullptr );
             assert( pos.pCur != nullptr );
@@ -1351,6 +1366,20 @@ namespace cds { namespace intrusive {
                 return false;
             }
 
+            if ( pos.pPrevVal == nullptr ) {
+                // Check ABA-problem for prev
+                // There is a possibility that the current thread was preempted
+                // on entry of this function. Other threads can insert (link) an item to prev
+                // and then remove it. As a result, the order of items may be changed
+                if ( find_prev( pHead, *pNode->data.load( memory_model::memory_order_relaxed ).ptr()) != pos.pPrev ) {
+                    pos.pPrev->data.store( valPrev, memory_model::memory_order_relaxed );
+                    pos.pCur->data.store( valCur, memory_model::memory_order_relaxed );
+
+                    m_Stat.onNullPrevABA();
+                    return false;
+                }
+            }
+
             // insert new node between pos.pPrev and pos.pCur
             pNode->next.store( pos.pCur, memory_model::memory_order_relaxed );
 
@@ -1375,6 +1404,34 @@ namespace cds { namespace intrusive {
             }
             return false;
         }
+
+        template <typename Q>
+        node_type* find_prev( node_type const* pHead, Q const& val ) const
+        {
+            node_type*  pPrev = const_cast<node_type*>(pHead);
+            typename gc::Guard guard;
+            key_comparator cmp;
+
+            while ( true ) {
+                node_type * pCur = pPrev->next.load( memory_model::memory_order_relaxed );
+
+                if ( pCur == pCur->next.load( memory_model::memory_order_acquire ) ) {
+                    // end-of-list
+                    return pPrev;
+                }
+
+                value_type * pVal = guard.protect( pCur->data,
+                    []( marked_data_ptr p ) -> value_type*
+                {
+                    return p.ptr();
+                } ).ptr();
+
+                if ( pVal && cmp( *pVal, val ) >= 0 )
+                    return pPrev;
+
+                pPrev = pCur;
+            }
+        }
         //@endcond
     };
 }} // namespace cds::intrusive
index 7e96194..e49e3b3 100644 (file)
@@ -411,6 +411,12 @@ namespace cds { namespace intrusive {
             return m_Stat;
         }
 
+        /// Returns internal statistics for \p OrderedList
+        typename OrderedList::stat const& list_statistics() const
+        {
+            return m_List.statistics();
+        }
+
     protected:
         //@cond
         template <bool IsConst>
index e3d459c..b6f60d4 100644 (file)
@@ -779,6 +779,12 @@ namespace cds { namespace intrusive {
             return m_Stat;
         }
 
+        /// Returns internal statistics for \p OrderedList
+        typename OrderedList::stat const& list_statistics() const
+        {
+            return m_List.statistics();
+        }
+
     protected:
         //@cond
         template <bool IsConst>
index 04b1193..692b7e5 100644 (file)
@@ -49,6 +49,7 @@ namespace cds_test {
             << CDSSTRESS_STAT_OUT( s, m_nReuseNode )
             << CDSSTRESS_STAT_OUT( s, m_nNodeMarkFailed )
             << CDSSTRESS_STAT_OUT( s, m_nNodeSeqBreak )
+            << CDSSTRESS_STAT_OUT( s, m_nNullPrevABA )
             << CDSSTRESS_STAT_OUT( s, m_nNewNodeCreated )
             << CDSSTRESS_STAT_OUT( s, m_nUpdateNew )
             << CDSSTRESS_STAT_OUT( s, m_nUpdateExisting )
index a11a4d7..93ff510 100644 (file)
@@ -51,6 +51,9 @@
 #include <cds/container/split_list_map_nogc.h>
 
 #include <cds_test/stat_splitlist_out.h>
+#include <cds_test/stat_michael_list_out.h>
+#include <cds_test/stat_lazy_list_out.h>
+#include <cds_test/stat_iterable_list_out.h>
 
 namespace map {
 
@@ -579,7 +582,8 @@ namespace map {
     template <typename GC, typename K, typename T, typename Traits >
     static inline void print_stat( cds_test::property_stream& o, SplitListMap< GC, K, T, Traits > const& m )
     {
-        o << m.statistics();
+        o << m.statistics()
+          << m.list_statistics();
     }
 
 }   // namespace map
index 38cfab2..13501ad 100644 (file)
@@ -46,6 +46,9 @@
 #include <cds/container/split_list_set_rcu.h>
 
 #include <cds_test/stat_splitlist_out.h>
+#include <cds_test/stat_michael_list_out.h>
+#include <cds_test/stat_lazy_list_out.h>
+#include <cds_test/stat_iterable_list_out.h>
 
 namespace set {
 
@@ -108,6 +111,7 @@ namespace set {
                 ,cc::split_list::ordered_list_traits<
                     typename cc::michael_list::make_traits<
                         co::compare< compare >
+                        ,co::stat< cc::michael_list::stat<>>
                     >::type
                 >
             >::type
@@ -220,6 +224,7 @@ namespace set {
                 ,cc::split_list::ordered_list_traits<
                     typename cc::michael_list::make_traits<
                         co::less< less >
+                        ,co::stat< cc::michael_list::stat<>>
                     >::type
                 >
             >::type
@@ -408,6 +413,7 @@ namespace set {
                 ,cc::split_list::ordered_list_traits<
                     typename cc::iterable_list::make_traits<
                         co::compare< compare >
+                        ,co::stat< cc::iterable_list::stat<>>
                     >::type
                 >
             >::type
@@ -530,6 +536,7 @@ namespace set {
                 ,cc::split_list::ordered_list_traits<
                     typename cc::iterable_list::make_traits<
                         co::less< less >
+                        ,co::stat< cc::iterable_list::stat<>>
                     >::type
                 >
             >::type
@@ -551,7 +558,8 @@ namespace set {
     template <typename GC, typename T, typename Traits>
     static inline void print_stat( cds_test::property_stream& o, SplitListSet<GC, T, Traits> const& s )
     {
-        o << s.statistics();
+        o << s.statistics()
+          << s.list_statistics();
     }
 
 } // namespace set