From 1ed1fd2e3b72891e0be0c819fb6f8fa6f3036173 Mon Sep 17 00:00:00 2001 From: khizmax Date: Sat, 22 Apr 2017 11:01:39 +0300 Subject: [PATCH] [TSan] Fixed memory order --- cds/compiler/feature_tsan.h | 11 +++++++++++ cds/container/details/make_skip_list_map.h | 3 --- cds/container/details/make_skip_list_set.h | 3 --- cds/container/details/skip_list_base.h | 11 +++++++++-- cds/intrusive/details/skip_list_base.h | 19 +++++++++++++++---- cds/intrusive/impl/skip_list.h | 4 ++-- cds/intrusive/skip_list_rcu.h | 21 +++------------------ 7 files changed, 40 insertions(+), 32 deletions(-) diff --git a/cds/compiler/feature_tsan.h b/cds/compiler/feature_tsan.h index a6c8695c..7599ee35 100644 --- a/cds/compiler/feature_tsan.h +++ b/cds/compiler/feature_tsan.h @@ -51,7 +51,12 @@ CDS_TSAN_ANNOTATE_IGNORE_WRITES_END;\ CDS_TSAN_ANNOTATE_IGNORE_READS_END # define CDS_TSAN_ANNOTATE_NEW_MEMORY( addr, sz ) AnnotateNewMemory( __FILE__, __LINE__, reinterpret_cast(addr), sz ) + +// Publish/unpublish - DEPRECATED +#if 0 # define CDS_TSAN_ANNOTATE_PUBLISH_MEMORY_RANGE( addr, sz ) AnnotatePublishMemoryRange( __FILE__, __LINE__, reinterpret_cast(addr), sz ) +# define CDS_TSAN_ANNOTATE_UNPUBLISH_MEMORY_RANGE( addr, sz ) AnnotateUnpublishMemoryRange( __FILE__, __LINE__, reinterpret_cast(addr), sz ) +#endif # define CDS_TSAN_ANNOTATE_MUTEX_CREATE( addr ) AnnotateRWLockCreate( __FILE__, __LINE__, reinterpret_cast(addr)) # define CDS_TSAN_ANNOTATE_MUTEX_DESTROY( addr ) AnnotateRWLockDestroy( __FILE__, __LINE__, reinterpret_cast(addr)) @@ -70,7 +75,10 @@ void AnnotateIgnoreWritesBegin(const char *f, int l); void AnnotateIgnoreWritesEnd(const char *f, int l); +#if 0 void AnnotatePublishMemoryRange( const char *f, int l, void * mem, size_t size ); + void AnnotateUnpublishMemoryRange( const char *f, int l, void * addr, size_t size ); +#endif void AnnotateNewMemory( const char *f, int l, void * mem, size_t size ); void AnnotateRWLockCreate( const char *f, int l, void* m ); @@ -91,7 +99,10 @@ # define CDS_TSAN_ANNOTATE_IGNORE_RW_BEGIN # define CDS_TSAN_ANNOTATE_IGNORE_RW_END +#if 0 # define CDS_TSAN_ANNOTATE_PUBLISH_MEMORY_RANGE( addr, sz ) +# define CDS_TSAN_ANNOTATE_UNPUBLISH_MEMORY_RANGE( addr, sz ) +#endif # define CDS_TSAN_ANNOTATE_NEW_MEMORY( addr, sz ) # define CDS_TSAN_ANNOTATE_MUTEX_CREATE( addr ) diff --git a/cds/container/details/make_skip_list_map.h b/cds/container/details/make_skip_list_map.h index 895b9586..8cb6fab9 100644 --- a/cds/container/details/make_skip_list_map.h +++ b/cds/container/details/make_skip_list_map.h @@ -76,11 +76,8 @@ namespace cds { namespace container { namespace details { void init_tower( unsigned int nHeight, atomic_marked_ptr * pTower ) { if ( nHeight > 1 ) { - // TSan: make_tower() issues atomic_thread_fence( release ) - CDS_TSAN_ANNOTATE_IGNORE_WRITES_BEGIN; new (pTower) atomic_marked_ptr[ nHeight - 1 ]; base_class::make_tower( nHeight, pTower ); - CDS_TSAN_ANNOTATE_IGNORE_WRITES_END; } } }; diff --git a/cds/container/details/make_skip_list_set.h b/cds/container/details/make_skip_list_set.h index ae629060..c88dd81e 100644 --- a/cds/container/details/make_skip_list_set.h +++ b/cds/container/details/make_skip_list_set.h @@ -74,11 +74,8 @@ namespace cds { namespace container { namespace details { void init_tower( unsigned nHeight, atomic_marked_ptr* pTower ) { if ( nHeight > 1 ) { - // TSan: make_tower() issues atomic_thread_fence( release ) - CDS_TSAN_ANNOTATE_IGNORE_WRITES_BEGIN; new ( pTower ) atomic_marked_ptr[nHeight - 1]; base_class::make_tower( nHeight, pTower ); - CDS_TSAN_ANNOTATE_IGNORE_WRITES_END; } } }; diff --git a/cds/container/details/skip_list_base.h b/cds/container/details/skip_list_base.h index 1b744b9d..5a343afe 100644 --- a/cds/container/details/skip_list_base.h +++ b/cds/container/details/skip_list_base.h @@ -170,23 +170,30 @@ namespace cds { namespace container { { return c_nNodeSize + (nHeight - 1) * c_nTowerItemSize; } + static unsigned char * alloc_space( unsigned int nHeight ) { + unsigned char * pMem; + size_t const sz = node_size( nHeight ); + if ( nHeight > 1 ) { - unsigned char * pMem = tower_allocator_type().allocate( node_size(nHeight)); + pMem = tower_allocator_type().allocate( sz ); // check proper alignments assert( (((uintptr_t) pMem) & (alignof(node_type) - 1)) == 0 ); assert( (((uintptr_t) (pMem + c_nNodeSize)) & (alignof(node_tower_item) - 1)) == 0 ); return pMem; } + else + pMem = reinterpret_cast( node_allocator_type().allocate( 1 ) ); - return reinterpret_cast( node_allocator_type().allocate(1)); + return pMem; } static void free_space( unsigned char * p, unsigned int nHeight ) { assert( p != nullptr ); + if ( nHeight == 1 ) node_allocator_type().deallocate( reinterpret_cast(p), 1 ); else diff --git a/cds/intrusive/details/skip_list_base.h b/cds/intrusive/details/skip_list_base.h index 00c5676f..252ea7b9 100644 --- a/cds/intrusive/details/skip_list_base.h +++ b/cds/intrusive/details/skip_list_base.h @@ -78,8 +78,9 @@ namespace cds { namespace intrusive { : m_pNext( nullptr ) , m_nHeight( 1 ) , m_arrNext( nullptr ) - , m_nUnlink( 1 ) - {} + { + m_nUnlink.store( 1, atomics::memory_order_release ); + } /// Constructs a node's tower of height \p nHeight @@ -121,7 +122,13 @@ namespace cds { namespace intrusive { assert( nLevel < height()); assert( nLevel == 0 || (nLevel > 0 && m_arrNext != nullptr)); - return nLevel ? m_arrNext[ nLevel - 1] : m_pNext; + if ( nLevel ) { + // TSan: data race between m_arrNext[ nLevel - 1 ] and make_tower() + // In fact, m_arrNext is a const array that is never changed + CDS_TSAN_ANNOTATE_HAPPENS_BEFORE( &m_arrNext[ nLevel - 1 ] ); + return m_arrNext[nLevel - 1]; + } + return m_pNext; } /// Access to element of next pointer array (const version) @@ -130,7 +137,11 @@ namespace cds { namespace intrusive { assert( nLevel < height()); assert( nLevel == 0 || nLevel > 0 && m_arrNext != nullptr ); - return nLevel ? m_arrNext[ nLevel - 1] : m_pNext; + if ( nLevel ) { + CDS_TSAN_ANNOTATE_HAPPENS_BEFORE( &m_arrNext[nLevel - 1] ); + return m_arrNext[nLevel - 1]; + } + return m_pNext; } /// Access to element of next pointer array (synonym for \p next() function) diff --git a/cds/intrusive/impl/skip_list.h b/cds/intrusive/impl/skip_list.h index 89f80bfc..8ee2d69e 100644 --- a/cds/intrusive/impl/skip_list.h +++ b/cds/intrusive/impl/skip_list.h @@ -1411,7 +1411,7 @@ namespace cds { namespace intrusive { // Insert at level 0 { marked_node_ptr p( pos.pSucc[0] ); - pNode->next( 0 ).store( p, memory_model::memory_order_relaxed ); + pNode->next( 0 ).store( p, memory_model::memory_order_release ); if ( !pos.pPrev[0]->next( 0 ).compare_exchange_strong( p, marked_node_ptr( pNode ), memory_model::memory_order_release, atomics::memory_order_relaxed )) return false; @@ -1427,7 +1427,7 @@ namespace cds { namespace intrusive { // Set pNode->next // pNode->next can have "logical deleted" flag if another thread is removing pNode right now if ( !pNode->next( nLevel ).compare_exchange_strong( p, pSucc, - memory_model::memory_order_acq_rel, atomics::memory_order_acquire )) + memory_model::memory_order_release, atomics::memory_order_acquire )) { // pNode has been marked as removed while we are inserting it // Stop inserting diff --git a/cds/intrusive/skip_list_rcu.h b/cds/intrusive/skip_list_rcu.h index 1d3a9774..e5b87111 100644 --- a/cds/intrusive/skip_list_rcu.h +++ b/cds/intrusive/skip_list_rcu.h @@ -76,8 +76,9 @@ namespace cds { namespace intrusive { , m_pDelChain( nullptr ) , m_nHeight(1) , m_arrNext( nullptr ) - , m_nUnlink(1) - {} + { + m_nUnlink.store( 1, atomics::memory_order_release ); + } /// Constructs a node of height \p nHeight void make_tower( unsigned int nHeight, atomic_marked_ptr * nextTower ) @@ -117,15 +118,7 @@ namespace cds { namespace intrusive { assert( nLevel < height()); assert( nLevel == 0 || (nLevel > 0 && m_arrNext != nullptr)); -# ifdef CDS_THREAD_SANITIZER_ENABLED - // TSan false positive: m_arrNext is read-only array - CDS_TSAN_ANNOTATE_IGNORE_READS_BEGIN; - atomic_marked_ptr& r = nLevel ? m_arrNext[ nLevel - 1] : m_pNext; - CDS_TSAN_ANNOTATE_IGNORE_READS_END; - return r; -# else return nLevel ? m_arrNext[ nLevel - 1] : m_pNext; -# endif } /// Access to element of next pointer array (const version) @@ -134,15 +127,7 @@ namespace cds { namespace intrusive { assert( nLevel < height()); assert( nLevel == 0 || nLevel > 0 && m_arrNext != nullptr ); -# ifdef CDS_THREAD_SANITIZER_ENABLED - // TSan false positive: m_arrNext is read-only array - CDS_TSAN_ANNOTATE_IGNORE_READS_BEGIN; - atomic_marked_ptr& r = nLevel ? m_arrNext[ nLevel - 1] : m_pNext; - CDS_TSAN_ANNOTATE_IGNORE_READS_END; - return r; -# else return nLevel ? m_arrNext[ nLevel - 1] : m_pNext; -# endif } /// Access to element of next pointer array (same as \ref next function) -- 2.34.1