IterableList: fixed a complex bug that can be called "ABA problem of null pointer"

diff --git a/cds/container/details/make_split_list_set_iterable_list.h b/cds/container/details/make_split_list_set_iterable_list.h
index f38edb5e3c7f40bbaa8d9bba5af1e92d776800e5..87e511e4a02823624192ee90ae29f47d2efac28a 100644 (file)
--- a/cds/container/details/make_split_list_set_iterable_list.h
+++ b/cds/container/details/make_split_list_set_iterable_list.h
@@ -51,9 +51,10 @@ namespace cds { namespace container { namespace details {
             value_type  m_Value;
 
             template <typename Q>
             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)... )
             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 ));
                 }
                 {
                     return base_class::operator()( key_accessor()( v.m_Value ));
                 }

+

                 template <typename Q>
                 size_t operator()( Q const& k ) const
                 {
                 template <typename Q>
                 size_t operator()( Q const& k ) const
                 {

diff --git a/cds/container/details/make_split_list_set_lazy_list.h b/cds/container/details/make_split_list_set_lazy_list.h
index f2fe26a4eee3dafb5478a9e8435657a1ceb43775..2d82a0039d4d5ed16962a46e44d98d98a3b95bc7 100644 (file)
--- a/cds/container/details/make_split_list_set_lazy_list.h
+++ b/cds/container/details/make_split_list_set_lazy_list.h
@@ -57,8 +57,8 @@ namespace cds { namespace container { namespace details {
             value_type  m_Value;
 
             template <typename Q>
             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>
             {}
 
             template <typename Q, typename... Args>

diff --git a/cds/container/details/make_split_list_set_michael_list.h b/cds/container/details/make_split_list_set_michael_list.h
index 73ff261431eb834989fdf0e676fc36488427f8e7..a16679e2dc510c1ca12c6493eeab951716fd8524 100644 (file)
--- a/cds/container/details/make_split_list_set_michael_list.h
+++ b/cds/container/details/make_split_list_set_michael_list.h
@@ -52,8 +52,8 @@ namespace cds { namespace container { namespace details {
             value_type  m_Value;
 
             template <typename Q>
             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 )
             {}
             template <typename Q, typename... Args>
             explicit node_type( Q&& q, Args&&... args )

diff --git a/cds/container/split_list_map_nogc.h b/cds/container/split_list_map_nogc.h
index 82f9237542fbbb1b7058bd1a4cfa4388d849e8aa..b005cd9d5895373621c2ebedefba750e9e79f9c7 100644 (file)
--- a/cds/container/split_list_map_nogc.h
+++ b/cds/container/split_list_map_nogc.h
@@ -376,6 +376,12 @@ namespace cds { namespace container {
         {
             return base_class::statistics();
         }
         {
             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
 
     };
 }}  // namespace cds::container
 

diff --git a/cds/container/split_list_map_rcu.h b/cds/container/split_list_map_rcu.h
index 9dc68aa8820fe668d3e8a8a8b8c269c160daae1a..800f2edbac094cd13b11183f2f801fd39aac0e06 100644 (file)
--- a/cds/container/split_list_map_rcu.h
+++ b/cds/container/split_list_map_rcu.h
@@ -707,6 +707,12 @@ namespace cds { namespace container {
         {
             return base_class::statistics();
         }
         {
             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
     };
 
 }} // namespace cds::container

diff --git a/cds/container/split_list_set.h b/cds/container/split_list_set.h
index acb24adb779d94e9b98952d6ef4589342b0411c3..cf1ed65c858b1194a43a6c6940c37d16bbbb7f92 100644 (file)
--- a/cds/container/split_list_set.h
+++ b/cds/container/split_list_set.h
@@ -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>
             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
         }
 
         /// Inserts new node


@@ -414,9 +414,9 @@ namespace cds { namespace container {
             synchronization.
         */
         template <typename Q, typename Func>
             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();
 
             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 )
         {
 #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 );
 
 
             auto bRet = base_class::upsert( *pNode, bAllowInsert );
 


@@ -514,9 +514,9 @@ namespace cds { namespace container {
             std::pair<bool, bool>
         >::type
 #endif
             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*/ ) {
 
             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
             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 ) {
 
             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_;
 
         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 )
         {
         template <typename... Args>
         static node_type * alloc_node( Args&&... args )
         {

diff --git a/cds/container/split_list_set_nogc.h b/cds/container/split_list_set_nogc.h
index 33b85e7104c40664a9db313f14ed158eac9181fa..ffc98b8415f27dba9ec42ce16aa06d90fedd180d 100644 (file)
--- a/cds/container/split_list_set_nogc.h
+++ b/cds/container/split_list_set_nogc.h
@@ -445,6 +445,12 @@ namespace cds { namespace container {
         {
             return base_class::statistics();
         }
         {
             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
     };
 
 }}  // namespace cds::container

diff --git a/cds/container/split_list_set_rcu.h b/cds/container/split_list_set_rcu.h
index 49d11e2d545ebcb988e3773d6827857dcc0acc4b..a4a9bc6fc9af950bd7876a08280cb81d44058f4a 100644 (file)
--- a/cds/container/split_list_set_rcu.h
+++ b/cds/container/split_list_set_rcu.h
@@ -993,6 +993,12 @@ namespace cds { namespace container {
         {
             return base_class::statistics();
         }
         {
             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
 
     };
 }}  // namespace cds::container
 

diff --git a/cds/intrusive/details/iterable_list_base.h b/cds/intrusive/details/iterable_list_base.h
index 5fdce3ae95d41a206585116136fa22628a8ec5a0..83ca5d3eb8bbcfea7eb2bce2a925fdb70c910074 100644 (file)
--- a/cds/intrusive/details/iterable_list_base.h
+++ b/cds/intrusive/details/iterable_list_base.h
@@ -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_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
             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 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;  }
             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 onReuseNode()                  const {}
             void onNodeMarkFailed()             const {}
             void onNodeSeqBreak()               const {}

+            void onNullPrevABA()                const {}

             void onNewNodeCreated()             const {}
             void onUpdateNew()                  const {}
             void onUpdateExisting()             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 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();}
             void onNewNodeCreated()  { m_stat.onNewNodeCreated();}
             void onUpdateNew()       { m_stat.onUpdateNew();     }
             void onUpdateExisting()  { m_stat.onUpdateExisting();}

diff --git a/cds/intrusive/details/split_list_base.h b/cds/intrusive/details/split_list_base.h
index d24ddb3fce52e8379326d5f2c2fc06466508df33..5e68bc8369329f012ff0ff1d2eb2bd3d616758df 100644 (file)
--- a/cds/intrusive/details/split_list_base.h
+++ b/cds/intrusive/details/split_list_base.h
@@ -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.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 );
                         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 );
             }
 
                 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);
                     }
 
                         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 )
                     {
                 {
                     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;
                     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
                         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);
                     }
 
                         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 );

                     }
                 };
 
                     }
                 };
 

diff --git a/cds/intrusive/impl/iterable_list.h b/cds/intrusive/impl/iterable_list.h
index 3cb3fd84e0a4feaa458582a99343eb992dbb48de..5ef08b1a573df41837c0f0b16273089e2db587ef 100644 (file)
--- a/cds/intrusive/impl/iterable_list.h
+++ b/cds/intrusive/impl/iterable_list.h
@@ -147,7 +147,7 @@ namespace cds { namespace intrusive {
 
         typedef typename gc::template guarded_ptr< value_type > guarded_ptr; ///< Guarded pointer
 
 
         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)
 
         //@cond
         // Rebind traits (split-list support)


@@ -852,7 +852,7 @@ namespace cds { namespace intrusive {
                     return false;
                 }
 
                     return false;
                 }
 

-                if ( link_aux_node( pNode, pos )) {
+                if ( link_aux_node( pNode, pos, pHead )) {

                     ++m_ItemCounter;
                     m_Stat.onInsertSuccess();
                     return true;
                     ++m_ItemCounter;
                     m_Stat.onInsertSuccess();
                     return true;


@@ -872,7 +872,7 @@ namespace cds { namespace intrusive {
                     return false;
                 }
 
                     return false;
                 }
 

-                if ( link_data( &val, pos )) {
+                if ( link_data( &val, pos, pHead )) {

                     ++m_ItemCounter;
                     m_Stat.onInsertSuccess();
                     return true;
                     ++m_ItemCounter;
                     m_Stat.onInsertSuccess();
                     return true;


@@ -896,7 +896,7 @@ namespace cds { namespace intrusive {
                     return false;
                 }
 
                     return false;
                 }
 

-                if ( link_data( &val, pos )) {
+                if ( link_data( &val, pos, pHead )) {

                     f( val );
                     ++m_ItemCounter;
                     m_Stat.onInsertSuccess();
                     f( val );
                     ++m_ItemCounter;
                     m_Stat.onInsertSuccess();


@@ -939,7 +939,7 @@ namespace cds { namespace intrusive {
                         return std::make_pair( false, false );
                     }
 
                         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();
                         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 );
         {
             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 );
             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;
             }
                 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 );
                 // 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;
             }
 
                 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
                 // reuse pPrev
 
                 // Set pos.pPrev data if it is null


@@ -1319,7 +1334,7 @@ namespace cds { namespace intrusive {
         }
 
         // split-list support
         }
 
         // 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 );
         {
             assert( pos.pPrev != nullptr );
             assert( pos.pCur != nullptr );


@@ -1351,6 +1366,20 @@ namespace cds { namespace intrusive {
                 return false;
             }
 
                 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 );
 
             // 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;
         }
             }
             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
         //@endcond
     };
 }} // namespace cds::intrusive

diff --git a/cds/intrusive/split_list_nogc.h b/cds/intrusive/split_list_nogc.h
index 7e96194b785ac2cf1e77741fc09ce931d78af369..e49e3b3acdf79c1d62079404ff1d59e6b7cc9119 100644 (file)
--- a/cds/intrusive/split_list_nogc.h
+++ b/cds/intrusive/split_list_nogc.h
@@ -411,6 +411,12 @@ namespace cds { namespace intrusive {
             return m_Stat;
         }
 
             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>
     protected:
         //@cond
         template <bool IsConst>

diff --git a/cds/intrusive/split_list_rcu.h b/cds/intrusive/split_list_rcu.h
index e3d459cef6f8453695233f004173eeb5c3f5b42d..b6f60d449d7407d820c0f1d61e3fd0b8a4e9f1e4 100644 (file)
--- a/cds/intrusive/split_list_rcu.h
+++ b/cds/intrusive/split_list_rcu.h
@@ -779,6 +779,12 @@ namespace cds { namespace intrusive {
             return m_Stat;
         }
 
             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>
     protected:
         //@cond
         template <bool IsConst>

diff --git a/test/include/cds_test/stat_iterable_list_out.h b/test/include/cds_test/stat_iterable_list_out.h
index 04b1193aaf4b4a681dc04fda976af2ce0f511242..692b7e55fa829e99d7008c364ff26dbabcce3b56 100644 (file)
--- a/test/include/cds_test/stat_iterable_list_out.h
+++ b/test/include/cds_test/stat_iterable_list_out.h
@@ -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_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 )
             << CDSSTRESS_STAT_OUT( s, m_nNewNodeCreated )
             << CDSSTRESS_STAT_OUT( s, m_nUpdateNew )
             << CDSSTRESS_STAT_OUT( s, m_nUpdateExisting )

diff --git a/test/stress/map/map_type_split_list.h b/test/stress/map/map_type_split_list.h
index a11a4d77c063d18d832f3827feb6317e1a388fdb..93ff510339ba238da737dcf0b3fe19070ed4ea96 100644 (file)
--- a/test/stress/map/map_type_split_list.h
+++ b/test/stress/map/map_type_split_list.h
@@ -51,6 +51,9 @@
 #include <cds/container/split_list_map_nogc.h>
 
 #include <cds_test/stat_splitlist_out.h>
 #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 {
 
 
 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 )
     {
     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
     }
 
 }   // namespace map

diff --git a/test/stress/set/set_type_split_list.h b/test/stress/set/set_type_split_list.h
index 38cfab2d61b9a8bd8bb3360c286c5481939a6408..13501ad856c4faf80537b4f210143ce11c7f3d71 100644 (file)
--- a/test/stress/set/set_type_split_list.h
+++ b/test/stress/set/set_type_split_list.h
@@ -46,6 +46,9 @@
 #include <cds/container/split_list_set_rcu.h>
 
 #include <cds_test/stat_splitlist_out.h>
 #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 {
 
 
 namespace set {
 


@@ -108,6 +111,7 @@ namespace set {
                 ,cc::split_list::ordered_list_traits<
                     typename cc::michael_list::make_traits<
                         co::compare< compare >
                 ,cc::split_list::ordered_list_traits<
                     typename cc::michael_list::make_traits<
                         co::compare< compare >

+                        ,co::stat< cc::michael_list::stat<>>

                     >::type
                 >
             >::type
                     >::type
                 >
             >::type


@@ -220,6 +224,7 @@ namespace set {
                 ,cc::split_list::ordered_list_traits<
                     typename cc::michael_list::make_traits<
                         co::less< less >
                 ,cc::split_list::ordered_list_traits<
                     typename cc::michael_list::make_traits<
                         co::less< less >

+                        ,co::stat< cc::michael_list::stat<>>

                     >::type
                 >
             >::type
                     >::type
                 >
             >::type


@@ -408,6 +413,7 @@ namespace set {
                 ,cc::split_list::ordered_list_traits<
                     typename cc::iterable_list::make_traits<
                         co::compare< compare >
                 ,cc::split_list::ordered_list_traits<
                     typename cc::iterable_list::make_traits<
                         co::compare< compare >

+                        ,co::stat< cc::iterable_list::stat<>>

                     >::type
                 >
             >::type
                     >::type
                 >
             >::type


@@ -530,6 +536,7 @@ namespace set {
                 ,cc::split_list::ordered_list_traits<
                     typename cc::iterable_list::make_traits<
                         co::less< less >
                 ,cc::split_list::ordered_list_traits<
                     typename cc::iterable_list::make_traits<
                         co::less< less >

+                        ,co::stat< cc::iterable_list::stat<>>

                     >::type
                 >
             >::type
                     >::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 )
     {
     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
     }
 
 } // namespace set