From 9f365e35c9da4fffae31bfc4c50164139e027385 Mon Sep 17 00:00:00 2001 From: khizmax Date: Tue, 4 Oct 2016 20:11:00 +0300 Subject: [PATCH] IterableList: fixed case of sequence breaking when reusing node --- cds/intrusive/details/iterable_list_base.h | 12 ++++++++---- cds/intrusive/impl/iterable_list.h | 10 +++++++++- test/include/cds_test/stat_iterable_list_out.h | 3 ++- 3 files changed, 19 insertions(+), 6 deletions(-) diff --git a/cds/intrusive/details/iterable_list_base.h b/cds/intrusive/details/iterable_list_base.h index 83fa58d9..4bb37e48 100644 --- 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 a733b2d2..d16cf1c0 100644 --- 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 94db6436..c2aceeef 100644 --- 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 ) -- 2.34.1