IterableList: fixed case of sequence breaking when reusing node

diff --git a/cds/intrusive/details/iterable_list_base.h b/cds/intrusive/details/iterable_list_base.h
index 83fa58d9fa543096fcdf70f877f5ad5722e61a57..4bb37e48b460ad9787c5c49cf1fa9c8a49d60f71 100644 (file)
--- a/cds/intrusive/details/iterable_list_base.h
+++ b/cds/intrusive/details/iterable_list_base.h
@@ -77,7 +77,8 @@ namespace cds { namespace intrusive {
             event_counter   m_nInsertFailed;    ///< Number of failed \p insert() operations
             event_counter   m_nInsertRetry;     ///< Number of attempts to insert new item
             event_counter   m_nReuseNode;       ///< Number of reusing empty node when inserting/updating
-            event_counter   m_nReuseNodeFailed; ///< Number of failed attempsof reusing free node when inserting/updating
+            event_counter   m_nReuseNodeMarkFailed; ///< Number of unsuccessful marking attempts when we try to reuse node
+            event_counter   m_nReuseNodeSeqBreak;   ///< Number of breaking sequence of \p prev -> \p next node when we try to reuse \p prev node
             event_counter   m_nUpdateNew;       ///< Number of new item inserted for \p update()
             event_counter   m_nUpdateExisting;  ///< Number of existing item updates
             event_counter   m_nUpdateFailed;    ///< Number of failed \p update() call
@@ -96,7 +97,8 @@ namespace cds { namespace intrusive {
             void onInsertFailed()       { ++m_nInsertFailed;    }
             void onInsertRetry()        { ++m_nInsertRetry;     }
             void onReuseNode()          { ++m_nReuseNode;       }
-            void onReuseNodeFailed()    { ++m_nReuseNodeFailed; }
+            void onReuseNodeMarkFailed(){ ++m_nReuseNodeMarkFailed; }
+            void onReuseNodeSeqBreak()  { ++m_nReuseNodeSeqBreak;   }
             void onUpdateNew()          { ++m_nUpdateNew;       }
             void onUpdateExisting()     { ++m_nUpdateExisting;  }
             void onUpdateFailed()       { ++m_nUpdateFailed;    }
@@ -119,7 +121,8 @@ namespace cds { namespace intrusive {
             void onInsertFailed()               const {}
             void onInsertRetry()                const {}
             void onReuseNode()                  const {}
-            void onReuseNodeFailed()            const {}
+            void onReuseNodeMarkFailed()        const {}
+            void onReuseNodeSeqBreak()          const {}
             void onUpdateNew()                  const {}
             void onUpdateExisting()             const {}
             void onUpdateFailed()               const {}
@@ -148,7 +151,8 @@ namespace cds { namespace intrusive {
             void onInsertFailed()    { m_stat.onInsertFailed();  }
             void onInsertRetry()     { m_stat.onInsertRetry();   }
             void onReuseNode()       { m_stat.onReuseNode();     }
-            void onReuseNodeFailed() { m_stat.onReuseNodeFailed(); }
+            void onReuseNodeMarkFailed() { m_stat.onReuseNodeMarkFailed(); }
+            void onReuseNodeSeqBreak()   { m_stat.onReuseNodeSeqBreak();   }
             void onUpdateNew()       { m_stat.onUpdateNew();     }
             void onUpdateExisting()  { m_stat.onUpdateExisting();}
             void onUpdateFailed()    { m_stat.onUpdateFailed();  }

diff --git a/cds/intrusive/impl/iterable_list.h b/cds/intrusive/impl/iterable_list.h
index a733b2d21ef3a4fb687eb3c4931c72e2066c1132..d16cf1c06991b64860ed000e4abc0f40123561b1 100644 (file)
--- a/cds/intrusive/impl/iterable_list.h
+++ b/cds/intrusive/impl/iterable_list.h
@@ -1153,7 +1153,15 @@ namespace cds { namespace intrusive {
                     marked_data_ptr val( pos.pFound );
                     if ( pos.pCur && !pos.pCur->data.compare_exchange_strong( val, val | 1, memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
                         // oops, pos.pCur data has been changed or another thread is setting pos.pPrev data
-                        m_Stat.onReuseNodeFailed();
+                        m_Stat.onReuseNodeMarkFailed();
+                        return false;
+                    }
+
+                    if ( pos.pPrev->next.load( memory_model::memory_order_acquire ) != pos.pCur ) {
+                        // sequence pPrev - pCur is broken
+                        if ( pos.pCur )
+                            pos.pCur->data.store( val, memory_model::memory_order_relaxed );
+                        m_Stat.onReuseNodeSeqBreak();
                         return false;
                     }
 

diff --git a/test/include/cds_test/stat_iterable_list_out.h b/test/include/cds_test/stat_iterable_list_out.h
index 94db6436be53b79b60ef2dfd42d728e44ee891f2..c2aceeefb7f35ec03473ba2a0919d5ae3d53e351 100644 (file)
--- a/test/include/cds_test/stat_iterable_list_out.h
+++ b/test/include/cds_test/stat_iterable_list_out.h
@@ -47,7 +47,8 @@ namespace cds_test {
             << CDSSTRESS_STAT_OUT( s, m_nInsertFailed )
             << CDSSTRESS_STAT_OUT( s, m_nInsertRetry )
             << CDSSTRESS_STAT_OUT( s, m_nReuseNode )
-            << CDSSTRESS_STAT_OUT( s, m_nReuseNodeFailed )
+            << CDSSTRESS_STAT_OUT( s, m_nReuseNodeMarkFailed )
+            << CDSSTRESS_STAT_OUT( s, m_nReuseNodeSeqBreak )
             << CDSSTRESS_STAT_OUT( s, m_nUpdateNew )
             << CDSSTRESS_STAT_OUT( s, m_nUpdateExisting )
             << CDSSTRESS_STAT_OUT( s, m_nUpdateFailed )