Merge branch 'integration' into dev
authorkhizmax <libcds.dev@gmail.com>
Mon, 27 Apr 2015 20:32:36 +0000 (23:32 +0300)
committerkhizmax <libcds.dev@gmail.com>
Mon, 27 Apr 2015 20:32:36 +0000 (23:32 +0300)
29 files changed:
cds/compiler/clang/defs.h
cds/compiler/defs.h
cds/compiler/feature_tsan.h [new file with mode: 0644]
cds/compiler/gcc/defs.h
cds/container/details/bronson_avltree_base.h
cds/container/impl/bronson_avltree_map_rcu.h
cds/container/lazy_kvlist_rcu.h
cds/container/striped_map/std_list.h
cds/container/striped_set/std_list.h
cds/gc/details/dhp.h
cds/intrusive/impl/michael_list.h
cds/intrusive/lazy_list_rcu.h
cds/intrusive/michael_list_rcu.h
cds/intrusive/split_list.h
cds/intrusive/split_list_nogc.h
cds/intrusive/split_list_rcu.h
cds/urcu/details/gpb.h
cds/urcu/details/gpi.h
cds/urcu/details/gpt.h
cds/urcu/details/sig_buffered.h
cds/urcu/details/sig_threaded.h
cds/urcu/dispose_thread.h
change.log
projects/Win/vc12/cds.vcxproj
projects/Win/vc12/cds.vcxproj.filters
src/dhp_gc.cpp
tests/cppunit/thread.cpp
thanks
tools/make_distrib.pl

index 182a5b8..ff6fb79 100644 (file)
 // Inheriting constructors
 #define CDS_CXX11_INHERITING_CTOR
 
+
+// *************************************************
+// Features
+#if defined(__has_feature) && __has_feature(thread_sanitizer)
+#   define CDS_THREAD_SANITIZER_ENABLED
+#endif
+
 // *************************************************
 // Alignment macro
 
index 1b4739b..a87195b 100644 (file)
@@ -1,7 +1,7 @@
 //$$CDS-header$$
 
-#ifndef CDSLIB_ARH_COMPILER_DEFS_H
-#define CDSLIB_ARH_COMPILER_DEFS_H
+#ifndef CDSLIB_COMPILER_DEFS_H
+#define CDSLIB_COMPILER_DEFS_H
 
 /*
     Required C++11 features:
@@ -37,4 +37,7 @@
 #   define CDS_EXPORT_API
 #endif
 
-#endif  // #ifndef CDSLIB_ARH_COMPILER_DEFS_H
+// Features
+#include <cds/compiler/feature_tsan.h>
+
+#endif  // #ifndef CDSLIB_COMPILER_DEFS_H
diff --git a/cds/compiler/feature_tsan.h b/cds/compiler/feature_tsan.h
new file mode 100644 (file)
index 0000000..926876a
--- /dev/null
@@ -0,0 +1,46 @@
+//$$CDS-header$$
+
+#ifndef CDSLIB_COMPILER_FEATURE_TSAN_H
+#define CDSLIB_COMPILER_FEATURE_TSAN_H
+
+// Thread Sanitizer annotations.
+// From https://groups.google.com/d/msg/thread-sanitizer/SsrHB7FTnTk/mNTGNLQj-9cJ
+
+#ifdef CDS_THREAD_SANITIZER_ENABLED
+#   define CDS_TSAN_ANNOTATE_HAPPENS_BEFORE(addr)   AnnotateHappensBefore(__FILE__, __LINE__, (void*)(addr))\r
+#   define CDS_TSAN_ANNOTATE_HAPPENS_AFTER(addr)    AnnotateHappensAfter(__FILE__, __LINE__, (void*)(addr))\r
+\r
+#   define CDS_TSAN_ANNOTATE_IGNORE_READS_BEGIN     AnnotateIgnoreReadsBegin(__FILE__, __LINE__)\r
+#   define CDS_TSAN_ANNOTATE_IGNORE_READS_END       AnnotateIgnoreReadsEnd(__FILE__, __LINE__)\r
+#   define CDS_TSAN_ANNOTATE_IGNORE_WRITES_BEGIN    AnnotateIgnoreWritesBegin(__FILE__, __LINE__)\r
+#   define CDS_TSAN_ANNOTATE_IGNORE_WRITES_END      AnnotateIgnoreWritesEnd(__FILE__, __LINE__)\r
+#   define CDS_TSAN_ANNOTATE_IGNORE_RW_BEGIN        \\r
+                                                    CDS_TSAN_ANNOTATE_IGNORE_READS_BEGIN; \\r
+                                                    CDS_TSAN_ANNOTATE_IGNORE_WRITES_BEGIN\r
+#   define CDS_TSAN_ANNOTATE_IGNORE_RW_END          \\r
+                                                    CDS_TSAN_ANNOTATE_IGNORE_WRITES_END;\\r
+                                                    CDS_TSAN_ANNOTATE_IGNORE_READS_END\r
+\r
+    // provided by TSan\r
+    extern "C" {\r
+        void AnnotateHappensBefore(const char *f, int l, void *addr);\r
+        void AnnotateHappensAfter(const char *f, int l, void *addr);\r
+\r
+        void AnnotateIgnoreReadsBegin(const char *f, int l);\r
+        void AnnotateIgnoreReadsEnd(const char *f, int l);\r
+        void AnnotateIgnoreWritesBegin(const char *f, int l);\r
+        void AnnotateIgnoreWritesEnd(const char *f, int l);\r
+    }\r
+#else\r
+#   define CDS_TSAN_ANNOTATE_HAPPENS_BEFORE(addr)\r
+#   define CDS_TSAN_ANNOTATE_HAPPENS_AFTER(addr)
+
+#   define CDS_TSAN_ANNOTATE_IGNORE_READS_BEGIN\r
+#   define CDS_TSAN_ANNOTATE_IGNORE_READS_END\r
+#   define CDS_TSAN_ANNOTATE_IGNORE_WRITES_BEGIN\r
+#   define CDS_TSAN_ANNOTATE_IGNORE_WRITES_END\r
+#   define CDS_TSAN_ANNOTATE_IGNORE_RW_BEGIN\r
+#   define CDS_TSAN_ANNOTATE_IGNORE_RW_END\r
+#endif
+
+#endif  // #ifndef CDSLIB_COMPILER_FEATURE_TSAN_H
index 2dadc6e..386c623 100644 (file)
 // Inheriting constructors
 #define CDS_CXX11_INHERITING_CTOR
 
+// *************************************************
+// Features
+// If you run under Thread Sanitizer, pass -DCDS_THREAD_SANITIZER_ENABLED in compiler command line
+//#define CDS_THREAD_SANITIZER_ENABLED
+
 // *************************************************
 // Alignment macro
 
index 85e220d..178e0bd 100644 (file)
@@ -73,10 +73,10 @@ namespace cds { namespace container {
                 m_pParent.store( p, order );
             }
 
-            atomics::atomic<node_type *> const& child( int nDirection ) const
+            node_type * child( int nDirection, atomics::memory_order order ) const
             {
                 assert( nDirection != 0 );
-                return nDirection < 0 ? m_pLeft : m_pRight;
+                return nDirection < 0 ? m_pLeft.load( order ) : m_pRight.load( order );
             }
 
             void child( node_type * pChild, int nDirection, atomics::memory_order order )
index 3dd1d93..515f289 100644 (file)
@@ -152,12 +152,12 @@ namespace cds { namespace container {
             disposer()(pVal);
         }
 
-        static node_type * child( node_type * pNode, int nDir, atomics::memory_order order = memory_model::memory_order_relaxed )
+        static node_type * child( node_type * pNode, int nDir, atomics::memory_order order )
         {
-            return pNode->child( nDir ).load( order );
+            return pNode->child( nDir, order );
         }
 
-        static node_type * parent( node_type * pNode, atomics::memory_order order = memory_model::memory_order_relaxed )
+        static node_type * parent( node_type * pNode, atomics::memory_order order )
         {
             return pNode->parent( order );
         }
@@ -747,7 +747,7 @@ namespace cds { namespace container {
         template <typename Func>
         bool check_consistency( Func f ) const
         {
-            node_type * pChild = child( m_pRoot, right_child );
+            node_type * pChild = child( m_pRoot, right_child, memory_model::memory_order_acquire );
             if ( pChild ) {
                 size_t nErrors = 0;
                 do_check_consistency( pChild, 1, f, nErrors );
@@ -763,8 +763,8 @@ namespace cds { namespace container {
         {
             if ( pNode ) {
                 key_comparator cmp;
-                node_type * pLeft = child( pNode, left_child );
-                node_type * pRight = child( pNode, right_child );
+                node_type * pLeft = child( pNode, left_child, memory_model::memory_order_acquire );
+                node_type * pRight = child( pNode, right_child, memory_model::memory_order_acquire );
                 if ( pLeft && cmp( pLeft->m_key, pNode->m_key ) > 0 )
                     ++nErrors;
                 if (  pRight && cmp( pNode->m_key, pRight->m_key ) > 0 )
@@ -870,7 +870,7 @@ namespace cds { namespace container {
                         version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
                         if ( nChildVersion & node_type::shrinking ) {
                             m_stat.onRemoveRootWaitShrinking();
-                            pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
+                            pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_acquire );
                             result = update_flags::retry;
                         }
                         else if ( pChild == child( m_pRoot, right_child, memory_model::memory_order_acquire )) {
@@ -922,17 +922,17 @@ namespace cds { namespace container {
 
     private:
         //@cond
-        static int height( node_type * pNode, atomics::memory_order order = memory_model::memory_order_relaxed )
+        static int height( node_type * pNode, atomics::memory_order order )
         {
             assert( pNode );
             return pNode->m_nHeight.load( order );
         }
-        static void set_height( node_type * pNode, int h, atomics::memory_order order = memory_model::memory_order_relaxed )
+        static void set_height( node_type * pNode, int h, atomics::memory_order order )
         {
             assert( pNode );
             pNode->m_nHeight.store( h, order );
         }
-        static int height_null( node_type * pNode, atomics::memory_order order = memory_model::memory_order_relaxed )
+        static int height_null( node_type * pNode, atomics::memory_order order )
         {
             return pNode ? height( pNode, order ) : 0;
         }
@@ -964,7 +964,7 @@ namespace cds { namespace container {
                 nDir = stack[pos].nDir;
 
                 while ( true ) {
-                    node_type * pChild = child( pNode, nDir );
+                    node_type * pChild = child( pNode, nDir, memory_model::memory_order_acquire );
                     if ( !pChild ) {
                         if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
                             --pos;
@@ -977,10 +977,10 @@ namespace cds { namespace container {
 
                     int nCmp = cmp( key, pChild->m_key );
                     if ( nCmp == 0 ) {
-                        if ( pChild->is_valued( memory_model::memory_order_relaxed ) ) {
+                        if ( pChild->is_valued( memory_model::memory_order_acquire ) ) {
                             // key found
                             node_scoped_lock l( m_Monitor, *pChild );
-                            if ( child(pNode, nDir) == pChild ) {
+                            if ( child(pNode, nDir, memory_model::memory_order_acquire) == pChild ) {
                                 if ( pChild->is_valued( memory_model::memory_order_relaxed )) {
                                     if ( f( pChild ) ) {
                                         m_stat.onFindSuccess();
@@ -1000,7 +1000,7 @@ namespace cds { namespace container {
                         version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
                         if ( nChildVersion & node_type::shrinking ) {
                             m_stat.onFindWaitShrinking();
-                            pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
+                            pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_acquire );
 
                             if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
                                 --pos;
@@ -1008,7 +1008,7 @@ namespace cds { namespace container {
                                 break; // retry
                             }
                         }
-                        else if ( nChildVersion != node_type::unlinked && child( pNode, nDir ) == pChild )
+                        else if ( nChildVersion != node_type::unlinked && child( pNode, nDir, memory_model::memory_order_acquire ) == pChild )
                         {
                             if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
                                 --pos;
@@ -1050,7 +1050,7 @@ namespace cds { namespace container {
                     version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
                     if ( nChildVersion & node_type::shrinking ) {
                         m_stat.onUpdateRootWaitShrinking();
-                        pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
+                        pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_acquire );
                         result = update_flags::retry;
                     }
                     else if ( pChild == child( m_pRoot, right_child, memory_model::memory_order_acquire ))
@@ -1074,8 +1074,8 @@ namespace cds { namespace container {
                             assert( pVal != nullptr );
                             pNew->m_pValue.store( pVal, memory_model::memory_order_release );
 
-                            m_pRoot->child( pNew, right_child, memory_model::memory_order_relaxed );
-                            set_height( m_pRoot, 2 );
+                            m_pRoot->child( pNew, right_child, memory_model::memory_order_release);
+                            set_height( m_pRoot, 2, memory_model::memory_order_release );
                         }
 
                         ++m_ItemCounter;
@@ -1105,7 +1105,7 @@ namespace cds { namespace container {
                     version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
                     if ( nChildVersion & node_type::shrinking ) {
                         m_stat.onRemoveRootWaitShrinking();
-                        pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
+                        pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_acquire );
                         result = update_flags::retry;
                     }
                     else if ( pChild == child( m_pRoot, right_child, memory_model::memory_order_acquire )) {
@@ -1158,7 +1158,7 @@ namespace cds { namespace container {
                 }
 
                 while ( true ) {
-                    node_type * pChild = child( pNode, nCmp );
+                    node_type * pChild = child( pNode, nCmp, memory_model::memory_order_acquire );
                     if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
                         --pos;
                         m_stat.onUpdateRetry();
@@ -1183,10 +1183,10 @@ namespace cds { namespace container {
                         version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
                         if ( nChildVersion & node_type::shrinking ) {
                             m_stat.onUpdateWaitShrinking();
-                            pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
+                            pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_acquire );
                             // retry
                         }
-                        else if ( pChild == child( pNode, nCmp )) {
+                        else if ( pChild == child( pNode, nCmp, memory_model::memory_order_acquire )) {
                             // this second read is important, because it is protected by nChildVersion
 
                             // validate the read that our caller took to get to node
@@ -1249,7 +1249,7 @@ namespace cds { namespace container {
                 }
 
                 while ( true ) {
-                    node_type * pChild = child( pNode, nCmp );
+                    node_type * pChild = child( pNode, nCmp, memory_model::memory_order_acquire );
                     if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
                         --pos;
                         m_stat.onRemoveRetry();
@@ -1263,10 +1263,10 @@ namespace cds { namespace container {
                     version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
                     if ( nChildVersion & node_type::shrinking ) {
                         m_stat.onRemoveWaitShrinking();
-                        pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
+                        pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_acquire );
                         // retry
                     }
-                    else if ( pChild == child( pNode, nCmp )) {
+                    else if ( pChild == child( pNode, nCmp, memory_model::memory_order_acquire )) {
                         // this second read is important, because it is protected by nChildVersion
 
                         // validate the read that our caller took to get to node
@@ -1319,7 +1319,7 @@ namespace cds { namespace container {
                 nVersion = stack[pos].nVersion;
 
                 while ( true ) {
-                    node_type * pChild = child( pNode, nDir );
+                    node_type * pChild = child( pNode, nDir, memory_model::memory_order_acquire );
                     if ( pNode->version(memory_model::memory_order_acquire) != nVersion ) {
                         --pos;
                         m_stat.onRemoveRetry();
@@ -1328,7 +1328,7 @@ namespace cds { namespace container {
 
                     if ( pChild == nullptr ) {
                         // Found min/max
-                        assert(pNode->is_valued( memory_model::memory_order_relaxed ));
+                        assert(pNode->is_valued( memory_model::memory_order_acquire ));
                         int result = try_remove_node( pParent, pNode, nVersion, func, disp );
                         if ( result != update_flags::retry )
                             return result;
@@ -1340,10 +1340,10 @@ namespace cds { namespace container {
                     version_type nChildVersion = pChild->version( memory_model::memory_order_acquire );
                     if ( nChildVersion & node_type::shrinking ) {
                         m_stat.onRemoveWaitShrinking();
-                        pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_relaxed );
+                        pChild->template wait_until_shrink_completed<back_off>( memory_model::memory_order_acquire );
                         // retry
                     }
-                    else if ( pChild == child( pNode, nDir )) {
+                    else if ( pChild == child( pNode, nDir, memory_model::memory_order_acquire )) {
                         // this second read is important, because it is protected by nChildVersion
 
                         // validate the read that our caller took to get to node
@@ -1379,12 +1379,12 @@ namespace cds { namespace container {
             auto fnCreateNode = [&funcUpdate]( node_type * pNew ) {
                 mapped_type pVal = funcUpdate( pNew );
                 assert( pVal != nullptr );
-                pNew->m_pValue.store( pVal, memory_model::memory_order_relaxed );
+                pNew->m_pValue.store( pVal, memory_model::memory_order_release );
             };
 
             if ( c_bRelaxedInsert ) {
                 if ( pNode->version( memory_model::memory_order_acquire ) != nVersion
-                     || child( pNode, nDir ) != nullptr )
+                     || child( pNode, nDir, memory_model::memory_order_acquire ) != nullptr )
                 {
                     m_stat.onInsertRetry();
                     return update_flags::retry;
@@ -1399,7 +1399,7 @@ namespace cds { namespace container {
                 node_scoped_lock l( m_Monitor, *pNode );
 
                 if ( pNode->version( memory_model::memory_order_acquire ) != nVersion
-                     || child( pNode, nDir ) != nullptr )
+                     || child( pNode, nDir, memory_model::memory_order_acquire ) != nullptr )
                 {
                     if ( c_bRelaxedInsert ) {
                         mapped_type pVal = pNew->m_pValue.load( memory_model::memory_order_relaxed );
@@ -1416,7 +1416,7 @@ namespace cds { namespace container {
                 if ( !c_bRelaxedInsert )
                     fnCreateNode( pNew = alloc_node( key, 1, 0, pNode, nullptr, nullptr ));
 
-                pNode->child( pNew, nDir, memory_model::memory_order_relaxed );
+                pNode->child( pNew, nDir, memory_model::memory_order_release );
                 pDamaged = fix_height_locked( pNode );
             }
 
@@ -1443,7 +1443,7 @@ namespace cds { namespace container {
                 if ( pNode->version(memory_model::memory_order_acquire) != nVersion )
                     return update_flags::retry;
 
-                if ( pNode->is_unlinked( memory_model::memory_order_relaxed )) {
+                if ( pNode->is_unlinked( memory_model::memory_order_acquire )) {
                     m_stat.onUpdateUnlinked();
                     return update_flags::retry;
                 }
@@ -1460,7 +1460,7 @@ namespace cds { namespace container {
                     pOld = nullptr;
                 else {
                     assert( pVal != nullptr );
-                    pNode->m_pValue.store( pVal, memory_model::memory_order_relaxed );
+                    pNode->m_pValue.store( pVal, memory_model::memory_order_release );
                 }
             }
 
@@ -1484,17 +1484,19 @@ namespace cds { namespace container {
             assert( pParent != nullptr );
             assert( pNode != nullptr );
 
-            if ( !pNode->is_valued( memory_model::memory_order_relaxed ) )
+            if ( !pNode->is_valued( memory_model::memory_order_acquire ) )
                 return update_flags::failed;
 
-            if ( child( pNode, left_child ) == nullptr || child( pNode, right_child ) == nullptr ) {
+            if ( child( pNode, left_child, memory_model::memory_order_acquire ) == nullptr 
+              || child( pNode, right_child, memory_model::memory_order_acquire ) == nullptr ) 
+            {
                 // pNode can be replaced with its child
 
                 node_type * pDamaged;
                 mapped_type pOld;
                 {
                     node_scoped_lock lp( m_Monitor, *pParent );
-                    if ( pParent->is_unlinked( memory_model::memory_order_relaxed ) || parent( pNode ) != pParent )
+                    if ( pParent->is_unlinked( memory_model::memory_order_acquire ) || parent( pNode, memory_model::memory_order_acquire ) != pParent )
                         return update_flags::retry;
 
                     {
@@ -1530,12 +1532,12 @@ namespace cds { namespace container {
                 {
                     node_scoped_lock ln( m_Monitor, *pNode );
                     pOld = pNode->value( memory_model::memory_order_relaxed );
-                    if ( pNode->version( memory_model::memory_order_acquire ) != nVersion )
+                    if ( pNode->version( memory_model::memory_order_relaxed ) != nVersion )
                         return update_flags::retry;
                     if ( !pOld )
                         return update_flags::failed;
 
-                    pNode->m_pValue.store( nullptr, memory_model::memory_order_relaxed );
+                    pNode->m_pValue.store( nullptr, memory_model::memory_order_release );
                     m_stat.onMakeRoutingNode();
                 }
 
@@ -1553,18 +1555,18 @@ namespace cds { namespace container {
             // pParent and pNode must be locked
             assert( !pParent->is_unlinked(memory_model::memory_order_relaxed) );
 
-            node_type * pParentLeft = child( pParent, left_child );
-            node_type * pParentRight = child( pParent, right_child );
+            node_type * pParentLeft = child( pParent, left_child, memory_model::memory_order_relaxed );
+            node_type * pParentRight = child( pParent, right_child, memory_model::memory_order_relaxed );
             if ( pNode != pParentLeft && pNode != pParentRight ) {
                 // node is no longer a child of parent
                 return false;
             }
 
             assert( !pNode->is_unlinked( memory_model::memory_order_relaxed ));
-            assert( pParent == parent( pNode ));
+            assert( pParent == parent( pNode, memory_model::memory_order_relaxed ));
 
-            node_type * pLeft = child( pNode, left_child );
-            node_type * pRight = child( pNode, right_child );
+            node_type * pLeft = child( pNode, left_child, memory_model::memory_order_relaxed );
+            node_type * pRight = child( pNode, right_child, memory_model::memory_order_relaxed );
             if ( pLeft != nullptr && pRight != nullptr ) {
                 // splicing is no longer possible
                 return false;
@@ -1572,18 +1574,18 @@ namespace cds { namespace container {
             node_type * pSplice = pLeft ? pLeft : pRight;
 
             if ( pParentLeft == pNode )
-                pParent->m_pLeft.store( pSplice, memory_model::memory_order_relaxed );
+                pParent->m_pLeft.store( pSplice, memory_model::memory_order_release );
             else
-                pParent->m_pRight.store( pSplice, memory_model::memory_order_relaxed );
+                pParent->m_pRight.store( pSplice, memory_model::memory_order_release );
 
             if ( pSplice )
-                pSplice->parent( pParent, memory_model::memory_order_relaxed );
+                pSplice->parent( pParent, memory_model::memory_order_release );
 
             // Mark the node as unlinked
             pNode->version( node_type::unlinked, memory_model::memory_order_release );
 
             // The value will be disposed by calling function
-            pNode->m_pValue.store( nullptr, memory_model::memory_order_relaxed );
+            pNode->m_pValue.store( nullptr, memory_model::memory_order_release );
 
             disp.dispose( pNode );
             m_stat.onDisposeNode();
@@ -1597,15 +1599,15 @@ namespace cds { namespace container {
         //@cond
         int estimate_node_condition( node_type * pNode )
         {
-            node_type * pLeft = child( pNode, left_child );
-            node_type * pRight = child( pNode, right_child );
+            node_type * pLeft = child( pNode, left_child, memory_model::memory_order_acquire );
+            node_type * pRight = child( pNode, right_child, memory_model::memory_order_acquire );
 
-            if ( (pLeft == nullptr || pRight == nullptr) && !pNode->is_valued( memory_model::memory_order_relaxed ))
+            if ( (pLeft == nullptr || pRight == nullptr) && !pNode->is_valued( memory_model::memory_order_acquire ))
                 return unlink_required;
 
-            int h = height( pNode );
-            int hL = height_null( pLeft );
-            int hR = height_null( pRight );
+            int h = height( pNode, memory_model::memory_order_acquire );
+            int hL = height_null( pLeft, memory_model::memory_order_acquire );
+            int hR = height_null( pRight, memory_model::memory_order_acquire );
 
             int hNew = 1 + std::max( hL, hR );
             int nBalance = hL - hR;
@@ -1634,26 +1636,26 @@ namespace cds { namespace container {
                 case nothing_required:
                     return nullptr;
                 default:
-                    set_height( pNode, h );
-                    return parent( pNode );
+                    set_height( pNode, h, memory_model::memory_order_release );
+                    return parent( pNode, memory_model::memory_order_relaxed );
             }
         }
 
         void fix_height_and_rebalance( node_type * pNode, rcu_disposer& disp )
         {
-            while ( pNode && parent( pNode )) {
+            while ( pNode && parent( pNode, memory_model::memory_order_acquire )) {
                 int nCond = estimate_node_condition( pNode );
-                if ( nCond == nothing_required || pNode->is_unlinked( memory_model::memory_order_relaxed ) )
+                if ( nCond == nothing_required || pNode->is_unlinked( memory_model::memory_order_acquire ) )
                     return;
 
                 if ( nCond != unlink_required && nCond != rebalance_required )
                     pNode = fix_height( pNode );
                 else {
-                    node_type * pParent = parent( pNode );
+                    node_type * pParent = parent( pNode, memory_model::memory_order_acquire );
                     assert( pParent != nullptr );
                     {
                         node_scoped_lock lp( m_Monitor, *pParent );
-                        if ( !pParent->is_unlinked( memory_model::memory_order_relaxed ) && parent( pNode ) == pParent ) {
+                        if ( !pParent->is_unlinked( memory_model::memory_order_relaxed ) && parent( pNode, memory_model::memory_order_acquire ) == pParent ) {
                             node_scoped_lock ln( m_Monitor, *pNode );
                             pNode = rebalance_locked( pParent, pNode, disp );
                         }
@@ -1666,10 +1668,10 @@ namespace cds { namespace container {
         {
             // pParent and pNode should be locked.
             // Returns a damaged node, or nullptr if no more rebalancing is necessary
-            assert( parent( pNode ) == pParent );
+            assert( parent( pNode, memory_model::memory_order_relaxed ) == pParent );
 
-            node_type * pLeft = child( pNode, left_child );
-            node_type * pRight = child( pNode, right_child );
+            node_type * pLeft = child( pNode, left_child, memory_model::memory_order_relaxed );
+            node_type * pRight = child( pNode, right_child, memory_model::memory_order_relaxed );
 
             if ( (pLeft == nullptr || pRight == nullptr) && !pNode->is_valued( memory_model::memory_order_relaxed )) {
                 if ( try_unlink_locked( pParent, pNode, disp ))
@@ -1680,11 +1682,12 @@ namespace cds { namespace container {
                 }
             }
 
-            assert( child( pParent, left_child ) == pNode || child( pParent, right_child ) == pNode );
+            assert( child( pParent, left_child, memory_model::memory_order_relaxed ) == pNode 
+                 || child( pParent, right_child, memory_model::memory_order_relaxed ) == pNode );
 
-            int h = height( pNode );
-            int hL = height_null( pLeft );
-            int hR = height_null( pRight );
+            int h = height( pNode, memory_model::memory_order_acquire );
+            int hL = height_null( pLeft, memory_model::memory_order_acquire );
+            int hR = height_null( pRight, memory_model::memory_order_acquire );
             int hNew = 1 + std::max( hL, hR );
             int balance = hL - hR;
 
@@ -1693,7 +1696,7 @@ namespace cds { namespace container {
             else if ( balance < -1 )
                 return rebalance_to_left_locked( pParent, pNode, pRight, hL );
             else if ( hNew != h ) {
-                set_height( pNode, hNew );
+                set_height( pNode, hNew, memory_model::memory_order_release );
 
                 // pParent is already locked
                 return fix_height_locked( pParent );
@@ -1704,8 +1707,9 @@ namespace cds { namespace container {
 
         node_type * rebalance_to_right_locked( node_type * pParent, node_type * pNode, node_type * pLeft, int hR )
         {
-            assert( parent( pNode ) == pParent );
-            assert( child( pParent, left_child ) == pNode || child( pParent, right_child ) == pNode );
+            assert( parent( pNode, memory_model::memory_order_relaxed ) == pParent );
+            assert( child( pParent, left_child, memory_model::memory_order_relaxed ) == pNode 
+                 || child( pParent, right_child, memory_model::memory_order_relaxed ) == pNode );
 
             // pParent and pNode is locked yet
             // pNode->pLeft is too large, we will rotate-right.
@@ -1717,14 +1721,14 @@ namespace cds { namespace container {
                 if ( pNode->m_pLeft.load( memory_model::memory_order_relaxed ) != pLeft )
                     return pNode; // retry for pNode
 
-                int hL = height( pLeft );
+                int hL = height( pLeft, memory_model::memory_order_acquire );
                 if ( hL - hR <= 1 )
                     return pNode; // retry
 
-                node_type * pLRight = child( pLeft, right_child );
-                int hLR = height_null( pLRight );
-                node_type * pLLeft = child( pLeft, left_child );
-                int hLL = height_null( pLLeft );
+                node_type * pLRight = child( pLeft, right_child, memory_model::memory_order_relaxed );
+                int hLR = height_null( pLRight, memory_model::memory_order_acquire );
+                node_type * pLLeft = child( pLeft, left_child, memory_model::memory_order_relaxed );
+                int hLL = height_null( pLLeft, memory_model::memory_order_acquire );
 
                 if ( hLL > hLR ) {
                     // rotate right
@@ -1734,14 +1738,14 @@ namespace cds { namespace container {
                     assert( pLRight != nullptr );
                     {
                         node_scoped_lock lr( m_Monitor, *pLRight );
-                        if ( pLeft->m_pRight.load( memory_model::memory_order_relaxed ) != pLRight )
+                        if ( pLeft->m_pRight.load( memory_model::memory_order_acquire ) != pLRight )
                             return pNode; // retry
 
-                        hLR = height( pLRight );
+                        hLR = height( pLRight, memory_model::memory_order_acquire );
                         if ( hLL > hLR )
                             return rotate_right_locked( pParent, pNode, pLeft, hR, hLL, pLRight, hLR );
 
-                        int hLRL = height_null( child( pLRight, left_child ));
+                        int hLRL = height_null( child( pLRight, left_child, memory_model::memory_order_relaxed ), memory_model::memory_order_acquire);
                         int balance = hLL - hLRL;
                         if ( balance >= -1 && balance <= 1 && !((hLL == 0 || hLRL == 0) && !pLeft->is_valued(memory_model::memory_order_relaxed))) {
                             // nParent.child.left won't be damaged after a double rotation
@@ -1757,8 +1761,9 @@ namespace cds { namespace container {
 
         node_type * rebalance_to_left_locked( node_type * pParent, node_type * pNode, node_type * pRight, int hL )
         {
-            assert( parent( pNode ) == pParent );
-            assert( child( pParent, left_child ) == pNode || child( pParent, right_child ) == pNode );
+            assert( parent( pNode, memory_model::memory_order_relaxed ) == pParent );
+            assert( child( pParent, left_child, memory_model::memory_order_relaxed ) == pNode 
+                 || child( pParent, right_child, memory_model::memory_order_relaxed ) == pNode );
 
             // pParent and pNode is locked yet
             {
@@ -1767,29 +1772,29 @@ namespace cds { namespace container {
                 if ( pNode->m_pRight.load( memory_model::memory_order_relaxed ) != pRight )
                     return pNode; // retry for pNode
 
-                int hR = height( pRight );
+                int hR = height( pRight, memory_model::memory_order_acquire );
                 if ( hL - hR >= -1 )
                     return pNode; // retry
 
-                node_type * pRLeft = child( pRight, left_child );
-                int hRL = height_null( pRLeft );
-                node_type * pRRight = child( pRight, right_child );
-                int hRR = height_null( pRRight );
+                node_type * pRLeft = child( pRight, left_child, memory_model::memory_order_relaxed );
+                int hRL = height_null( pRLeft, memory_model::memory_order_acquire );
+                node_type * pRRight = child( pRight, right_child, memory_model::memory_order_relaxed );
+                int hRR = height_null( pRRight, memory_model::memory_order_acquire );
                 if ( hRR > hRL )
                     return rotate_left_locked( pParent, pNode, hL, pRight, pRLeft, hRL, hRR );
 
                 {
                     assert( pRLeft != nullptr );
                     node_scoped_lock lrl( m_Monitor, *pRLeft );
-                    if ( pRight->m_pLeft.load( memory_model::memory_order_relaxed ) != pRLeft )
+                    if ( pRight->m_pLeft.load( memory_model::memory_order_acquire ) != pRLeft )
                         return pNode; // retry
 
-                    hRL = height( pRLeft );
+                    hRL = height( pRLeft, memory_model::memory_order_acquire );
                     if ( hRR >= hRL )
                         return rotate_left_locked( pParent, pNode, hL, pRight, pRLeft, hRL, hRR );
 
-                    node_type * pRLRight = child( pRLeft, right_child );
-                    int hRLR = height_null( pRLRight );
+                    node_type * pRLRight = child( pRLeft, right_child, memory_model::memory_order_relaxed );
+                    int hRLR = height_null( pRLRight, memory_model::memory_order_acquire );
                     int balance = hRR - hRLR;
                     if ( balance >= -1 && balance <= 1 && !((hRR == 0 || hRLR == 0) && !pRight->is_valued( memory_model::memory_order_relaxed )))
                          return rotate_left_over_right_locked( pParent, pNode, hL, pRight, pRLeft, hRR, hRLR );
@@ -1812,36 +1817,36 @@ namespace cds { namespace container {
 
         node_type * rotate_right_locked( node_type * pParent, node_type * pNode, node_type * pLeft, int hR, int hLL, node_type * pLRight, int hLR )
         {
-            version_type nodeVersion = pNode->version( memory_model::memory_order_acquire );
-            node_type * pParentLeft = child( pParent, left_child );
+            version_type nodeVersion = pNode->version( memory_model::memory_order_relaxed );
+            node_type * pParentLeft = child( pParent, left_child, memory_model::memory_order_relaxed );
 
             begin_change( pNode, nodeVersion );
 
-            pNode->m_pLeft.store( pLRight, memory_model::memory_order_relaxed );
+            pNode->m_pLeft.store( pLRight, memory_model::memory_order_release );
             if ( pLRight != nullptr )
-                pLRight->parent( pNode, memory_model::memory_order_relaxed  );
+                pLRight->parent( pNode, memory_model::memory_order_release  );
 
             atomics::atomic_thread_fence( memory_model::memory_order_release );
 
-            pLeft->m_pRight.store( pNode, memory_model::memory_order_relaxed );
-            pNode->parent( pLeft, memory_model::memory_order_relaxed );
+            pLeft->m_pRight.store( pNode, memory_model::memory_order_release );
+            pNode->parent( pLeft, memory_model::memory_order_release );
 
             atomics::atomic_thread_fence( memory_model::memory_order_release );
 
             if ( pParentLeft == pNode )
-                pParent->m_pLeft.store( pLeft, memory_model::memory_order_relaxed );
+                pParent->m_pLeft.store( pLeft, memory_model::memory_order_release );
             else {
                 assert( pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode );
-                pParent->m_pRight.store( pLeft, memory_model::memory_order_relaxed );
+                pParent->m_pRight.store( pLeft, memory_model::memory_order_release );
             }
-            pLeft->parent( pParent, memory_model::memory_order_relaxed );
+            pLeft->parent( pParent, memory_model::memory_order_release );
 
             atomics::atomic_thread_fence( memory_model::memory_order_release );
 
             // fix up heights links
             int hNode = 1 + std::max( hLR, hR );
-            set_height( pNode, hNode );
-            set_height( pLeft, 1 + std::max( hLL, hNode ));
+            set_height( pNode, hNode, memory_model::memory_order_release );
+            set_height( pLeft, 1 + std::max( hLL, hNode ), memory_model::memory_order_release);
 
             end_change( pNode, nodeVersion );
             m_stat.onRotateRight();
@@ -1876,7 +1881,7 @@ namespace cds { namespace container {
             }
 
             // pLeft might also have routing node damage (if pLeft.left was null)
-            if ( hLL == 0 && !pLeft->is_valued(memory_model::memory_order_relaxed) ) {
+            if ( hLL == 0 && !pLeft->is_valued(memory_model::memory_order_acquire) ) {
                 m_stat.onDamageAfterRightRotation();
                 return pLeft;
             }
@@ -1887,37 +1892,37 @@ namespace cds { namespace container {
 
         node_type * rotate_left_locked( node_type * pParent, node_type * pNode, int hL, node_type * pRight, node_type * pRLeft, int hRL, int hRR )
         {
-            version_type nodeVersion = pNode->version( memory_model::memory_order_acquire );
-            node_type * pParentLeft = child( pParent, left_child );
+            version_type nodeVersion = pNode->version( memory_model::memory_order_relaxed );
+            node_type * pParentLeft = child( pParent, left_child, memory_model::memory_order_relaxed );
 
             begin_change( pNode, nodeVersion );
 
             // fix up pNode links, careful to be compatible with concurrent traversal for all but pNode
-            pNode->m_pRight.store( pRLeft, memory_model::memory_order_relaxed );
+            pNode->m_pRight.store( pRLeft, memory_model::memory_order_release );
             if ( pRLeft != nullptr )
-                pRLeft->parent( pNode, memory_model::memory_order_relaxed );
+                pRLeft->parent( pNode, memory_model::memory_order_release );
 
             atomics::atomic_thread_fence( memory_model::memory_order_release );
 
-            pRight->m_pLeft.store( pNode, memory_model::memory_order_relaxed );
-            pNode->parent( pRight, memory_model::memory_order_relaxed );
+            pRight->m_pLeft.store( pNode, memory_model::memory_order_release );
+            pNode->parent( pRight, memory_model::memory_order_release );
 
             atomics::atomic_thread_fence( memory_model::memory_order_release );
 
             if ( pParentLeft == pNode )
-                pParent->m_pLeft.store( pRight, memory_model::memory_order_relaxed );
+                pParent->m_pLeft.store( pRight, memory_model::memory_order_release );
             else {
                 assert( pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode );
-                pParent->m_pRight.store( pRight, memory_model::memory_order_relaxed );
+                pParent->m_pRight.store( pRight, memory_model::memory_order_release );
             }
-            pRight->parent( pParent, memory_model::memory_order_relaxed );
+            pRight->parent( pParent, memory_model::memory_order_release );
 
             atomics::atomic_thread_fence( memory_model::memory_order_release );
 
             // fix up heights
             int hNode = 1 + std::max( hL, hRL );
-            set_height( pNode, hNode );
-            set_height( pRight, 1 + std::max( hNode, hRR ));
+            set_height( pNode, hNode, memory_model::memory_order_release );
+            set_height( pRight, 1 + std::max( hNode, hRR ), memory_model::memory_order_release);
 
             end_change( pNode, nodeVersion );
             m_stat.onRotateLeft();
@@ -1939,7 +1944,7 @@ namespace cds { namespace container {
                 return pRight;
             }
 
-            if ( hRR == 0 && !pRight->is_valued(memory_model::memory_order_relaxed) ) {
+            if ( hRR == 0 && !pRight->is_valued(memory_model::memory_order_acquire) ) {
                 m_stat.onDamageAfterLeftRotation();
                 return pRight;
             }
@@ -1949,51 +1954,46 @@ namespace cds { namespace container {
 
         node_type * rotate_right_over_left_locked( node_type * pParent, node_type * pNode, node_type * pLeft, int hR, int hLL, node_type * pLRight, int hLRL )
         {
-            version_type nodeVersion = pNode->version( memory_model::memory_order_acquire );
+            version_type nodeVersion = pNode->version( memory_model::memory_order_relaxed );
             version_type leftVersion = pLeft->version( memory_model::memory_order_acquire );
 
-            node_type * pPL = child( pParent, left_child );
-            node_type * pLRL = child( pLRight, left_child );
-            node_type * pLRR = child( pLRight, right_child );
-            int hLRR = height_null( pLRR );
+            node_type * pPL = child( pParent, left_child, memory_model::memory_order_relaxed );
+            node_type * pLRL = child( pLRight, left_child, memory_model::memory_order_acquire );
+            node_type * pLRR = child( pLRight, right_child, memory_model::memory_order_acquire );
+            int hLRR = height_null( pLRR, memory_model::memory_order_acquire );
 
             begin_change( pNode, nodeVersion );
             begin_change( pLeft, leftVersion );
 
             // fix up pNode links, careful about the order!
-            pNode->m_pLeft.store( pLRR, memory_model::memory_order_relaxed );
+            pNode->m_pLeft.store( pLRR, memory_model::memory_order_release );
             if ( pLRR != nullptr )
-                pLRR->parent( pNode, memory_model::memory_order_relaxed );
-            atomics::atomic_thread_fence( memory_model::memory_order_release );
+                pLRR->parent( pNode, memory_model::memory_order_release );
 
-            pLeft->m_pRight.store( pLRL, memory_model::memory_order_relaxed );
+            pLeft->m_pRight.store( pLRL, memory_model::memory_order_release );
             if ( pLRL != nullptr )
-                pLRL->parent( pLeft, memory_model::memory_order_relaxed );
-            atomics::atomic_thread_fence( memory_model::memory_order_release );
+                pLRL->parent( pLeft, memory_model::memory_order_release );
 
-            pLRight->m_pLeft.store( pLeft, memory_model::memory_order_relaxed );
-            pLeft->parent( pLRight, memory_model::memory_order_relaxed );
-            atomics::atomic_thread_fence( memory_model::memory_order_release );
+            pLRight->m_pLeft.store( pLeft, memory_model::memory_order_release );
+            pLeft->parent( pLRight, memory_model::memory_order_release );
 
-            pLRight->m_pRight.store( pNode, memory_model::memory_order_relaxed );
-            pNode->parent( pLRight, memory_model::memory_order_relaxed );
-            atomics::atomic_thread_fence( memory_model::memory_order_release );
+            pLRight->m_pRight.store( pNode, memory_model::memory_order_release );
+            pNode->parent( pLRight, memory_model::memory_order_release );
 
             if ( pPL == pNode )
-                pParent->m_pLeft.store( pLRight, memory_model::memory_order_relaxed );
+                pParent->m_pLeft.store( pLRight, memory_model::memory_order_release );
             else {
-                assert( child( pParent, right_child ) == pNode );
-                pParent->m_pRight.store( pLRight, memory_model::memory_order_relaxed );
+                assert( child( pParent, right_child, memory_model::memory_order_relaxed ) == pNode );
+                pParent->m_pRight.store( pLRight, memory_model::memory_order_release );
             }
-            pLRight->parent( pParent, memory_model::memory_order_relaxed );
-            atomics::atomic_thread_fence( memory_model::memory_order_release );
+            pLRight->parent( pParent, memory_model::memory_order_release );
 
             // fix up heights
             int hNode = 1 + std::max( hLRR, hR );
-            set_height( pNode, hNode );
+            set_height( pNode, hNode, memory_model::memory_order_release );
             int hLeft = 1 + std::max( hLL, hLRL );
-            set_height( pLeft, hLeft );
-            set_height( pLRight, 1 + std::max( hLeft, hNode ));
+            set_height( pLeft, hLeft, memory_model::memory_order_release );
+            set_height( pLRight, 1 + std::max( hLeft, hNode ), memory_model::memory_order_release);
 
             end_change( pNode, nodeVersion );
             end_change( pLeft, leftVersion );
@@ -2002,7 +2002,7 @@ namespace cds { namespace container {
             // caller should have performed only a single rotation if pLeft was going
             // to end up damaged
             assert( hLL - hLRL <= 1 && hLRL - hLL <= 1 );
-            assert( !((hLL == 0 || pLRL == nullptr) && !pLeft->is_valued( memory_model::memory_order_relaxed )));
+            assert( !((hLL == 0 || pLRL == nullptr) && !pLeft->is_valued( memory_model::memory_order_acquire )));
 
             // We have damaged pParent, pLR (now parent.child), and pNode (now
             // parent.child.right).  pNode is the deepest.  Perform as many fixes as we
@@ -2038,51 +2038,46 @@ namespace cds { namespace container {
 
         node_type * rotate_left_over_right_locked( node_type * pParent, node_type * pNode, int hL, node_type * pRight, node_type * pRLeft, int hRR, int hRLR )
         {
-            version_type nodeVersion = pNode->version( memory_model::memory_order_acquire );
+            version_type nodeVersion = pNode->version( memory_model::memory_order_relaxed );
             version_type rightVersion = pRight->version( memory_model::memory_order_acquire );
 
-            node_type * pPL = child( pParent, left_child );
-            node_type * pRLL = child( pRLeft, left_child );
-            node_type * pRLR = child( pRLeft, right_child );
-            int hRLL = height_null( pRLL );
+            node_type * pPL = child( pParent, left_child, memory_model::memory_order_relaxed );
+            node_type * pRLL = child( pRLeft, left_child, memory_model::memory_order_acquire );
+            node_type * pRLR = child( pRLeft, right_child, memory_model::memory_order_acquire );
+            int hRLL = height_null( pRLL, memory_model::memory_order_acquire );
 
             begin_change( pNode, nodeVersion );
             begin_change( pRight, rightVersion );
 
             // fix up pNode links, careful about the order!
-            pNode->m_pRight.store( pRLL, memory_model::memory_order_relaxed );
+            pNode->m_pRight.store( pRLL, memory_model::memory_order_release );
             if ( pRLL != nullptr )
-                pRLL->parent( pNode, memory_model::memory_order_relaxed );
-            atomics::atomic_thread_fence( memory_model::memory_order_release );
+                pRLL->parent( pNode, memory_model::memory_order_release );
 
-            pRight->m_pLeft.store( pRLR, memory_model::memory_order_relaxed );
+            pRight->m_pLeft.store( pRLR, memory_model::memory_order_release );
             if ( pRLR != nullptr )
-                pRLR->parent( pRight, memory_model::memory_order_relaxed );
-            atomics::atomic_thread_fence( memory_model::memory_order_release );
+                pRLR->parent( pRight, memory_model::memory_order_release );
 
-            pRLeft->m_pRight.store( pRight, memory_model::memory_order_relaxed );
-            pRight->parent( pRLeft, memory_model::memory_order_relaxed );
-            atomics::atomic_thread_fence( memory_model::memory_order_release );
+            pRLeft->m_pRight.store( pRight, memory_model::memory_order_release );
+            pRight->parent( pRLeft, memory_model::memory_order_release );
 
-            pRLeft->m_pLeft.store( pNode, memory_model::memory_order_relaxed );
-            pNode->parent( pRLeft, memory_model::memory_order_relaxed );
-            atomics::atomic_thread_fence( memory_model::memory_order_release );
+            pRLeft->m_pLeft.store( pNode, memory_model::memory_order_release );
+            pNode->parent( pRLeft, memory_model::memory_order_release );
 
             if ( pPL == pNode )
-                pParent->m_pLeft.store( pRLeft, memory_model::memory_order_relaxed );
+                pParent->m_pLeft.store( pRLeft, memory_model::memory_order_release );
             else {
                 assert( pParent->m_pRight.load( memory_model::memory_order_relaxed ) == pNode );
-                pParent->m_pRight.store( pRLeft, memory_model::memory_order_relaxed );
+                pParent->m_pRight.store( pRLeft, memory_model::memory_order_release );
             }
-            pRLeft->parent( pParent, memory_model::memory_order_relaxed );
-            atomics::atomic_thread_fence( memory_model::memory_order_release );
+            pRLeft->parent( pParent, memory_model::memory_order_release );
 
             // fix up heights
             int hNode = 1 + std::max( hL, hRLL );
-            set_height( pNode, hNode );
+            set_height( pNode, hNode, memory_model::memory_order_release );
             int hRight = 1 + std::max( hRLR, hRR );
-            set_height( pRight, hRight );
-            set_height( pRLeft, 1 + std::max( hNode, hRight ));
+            set_height( pRight, hRight, memory_model::memory_order_release );
+            set_height( pRLeft, 1 + std::max( hNode, hRight ), memory_model::memory_order_release);
 
             end_change( pNode, nodeVersion );
             end_change( pRight, rightVersion );
index de24d13..1ead8cc 100644 (file)
@@ -130,19 +130,28 @@ namespace cds { namespace container {
         template <typename K>
         static node_type * alloc_node(const K& key)
         {
-            return cxx_allocator().New( key );
+            CDS_TSAN_ANNOTATE_IGNORE_WRITES_BEGIN;
+            node_type * p = cxx_allocator().New( key );
+            CDS_TSAN_ANNOTATE_IGNORE_WRITES_END;
+            return p;
         }
 
         template <typename K, typename V>
         static node_type * alloc_node( const K& key, const V& val )
         {
-            return cxx_allocator().New( key, val );
+            CDS_TSAN_ANNOTATE_IGNORE_WRITES_BEGIN;
+            node_type * p = cxx_allocator().New( key, val );
+            CDS_TSAN_ANNOTATE_IGNORE_WRITES_END;
+            return p;
         }
 
         template <typename... Args>
         static node_type * alloc_node( Args&&... args )
         {
-            return cxx_allocator().MoveNew( std::forward<Args>(args)... );
+            CDS_TSAN_ANNOTATE_IGNORE_WRITES_BEGIN;
+            node_type * p = cxx_allocator().MoveNew( std::forward<Args>(args)... );
+            CDS_TSAN_ANNOTATE_IGNORE_WRITES_END;
+            return p;
         }
 
         static void free_node( node_type * pNode )
index eba4c9f..4e7bdc1 100644 (file)
@@ -9,6 +9,11 @@
 #include <utility>      // std::pair
 #include <cds/container/striped_set/adapter.h>
 
+#undef CDS_STD_LIST_SIZE_CXX11_CONFORM
+#if !( defined(__GLIBCXX__ ) && (!defined(_GLIBCXX_USE_CXX11_ABI) || _GLIBCXX_USE_CXX11_ABI == 0 ))
+#   define CDS_STD_LIST_SIZE_CXX11_CONFORM
+#endif
+
 //@cond
 namespace cds { namespace container {
     namespace striped_set {
@@ -123,7 +128,7 @@ namespace cds { namespace intrusive { namespace striped_set {
         private:
             //@cond
             container_type  m_List;
-#       if defined(__GLIBCXX__ ) && !( CDS_COMPILER == CDS_COMPILER_GCC && CDS_COMPILER_VERSION >= 50000 )
+#       if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
             // GCC C++ lib bug:
             // In GCC (at least up to 4.7.x), the complexity of std::list::size() is O(N)
             // (see http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49561)
@@ -134,7 +139,7 @@ namespace cds { namespace intrusive { namespace striped_set {
 
         public:
             adapted_container()
-#       if defined(__GLIBCXX__ ) && !( CDS_COMPILER == CDS_COMPILER_GCC && CDS_COMPILER_VERSION >= 50000 )
+#       if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
                 : m_nSize(0)
 #       endif
             {}
@@ -148,7 +153,7 @@ namespace cds { namespace intrusive { namespace striped_set {
                     it = m_List.insert( it, value_type( key, mapped_type()) );
                     f( *it );
 
-#           if defined(__GLIBCXX__ ) && !( CDS_COMPILER == CDS_COMPILER_GCC && CDS_COMPILER_VERSION >= 50000 )
+#           if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
                     ++m_nSize;
 #           endif
                     return true;
@@ -166,7 +171,7 @@ namespace cds { namespace intrusive { namespace striped_set {
                     //value_type newItem( key );
                     it = m_List.emplace( it, value_type( std::forward<K>(key), std::move( mapped_type( std::forward<Args>(args)...) )) );
 
-#           if defined(__GLIBCXX__ ) && !( CDS_COMPILER == CDS_COMPILER_GCC && CDS_COMPILER_VERSION >= 50000 )
+#           if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
                     ++m_nSize;
 #           endif
                     return true;
@@ -183,7 +188,7 @@ namespace cds { namespace intrusive { namespace striped_set {
                     value_type newItem( key, mapped_type() );
                     it = m_List.insert( it, newItem );
                     func( true, *it );
-#           if defined(__GLIBCXX__ ) && !( CDS_COMPILER == CDS_COMPILER_GCC && CDS_COMPILER_VERSION >= 50000 )
+#           if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
                     ++m_nSize;
 #           endif
                     return std::make_pair( true, true );
@@ -205,7 +210,7 @@ namespace cds { namespace intrusive { namespace striped_set {
                 // key exists
                 f( *it );
                 m_List.erase( it );
-#           if defined(__GLIBCXX__ ) && !( CDS_COMPILER == CDS_COMPILER_GCC && CDS_COMPILER_VERSION >= 50000 )
+#           if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
                 --m_nSize;
 #           endif
 
@@ -222,7 +227,7 @@ namespace cds { namespace intrusive { namespace striped_set {
                 // key exists
                 f( *it );
                 m_List.erase( it );
-#           if defined(__GLIBCXX__ ) && !( CDS_COMPILER == CDS_COMPILER_GCC && CDS_COMPILER_VERSION >= 50000 )
+#           if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
                 --m_nSize;
 #           endif
 
@@ -269,14 +274,14 @@ namespace cds { namespace intrusive { namespace striped_set {
                 assert( it == m_List.end() || key_comparator()( itWhat->first, it->first ) != 0 );
 
                 copy_item()( m_List, it, itWhat );
-#           if defined(__GLIBCXX__ ) && !( CDS_COMPILER == CDS_COMPILER_GCC && CDS_COMPILER_VERSION >= 50000 )
+#           if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
                 ++m_nSize;
 #           endif
             }
 
             size_t size() const
             {
-#           if defined(__GLIBCXX__ ) && !( CDS_COMPILER == CDS_COMPILER_GCC && CDS_COMPILER_VERSION >= 50000 )
+#           if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
                 return m_nSize;
 #           else
                 return m_List.size();
index 05a239f..b0788c3 100644 (file)
@@ -8,6 +8,11 @@
 #include <algorithm>    // std::lower_bound
 #include <cds/container/striped_set/adapter.h>
 
+#undef CDS_STD_LIST_SIZE_CXX11_CONFORM
+#if !( defined(__GLIBCXX__ ) && (!defined(_GLIBCXX_USE_CXX11_ABI) || _GLIBCXX_USE_CXX11_ABI == 0 ))
+#   define CDS_STD_LIST_SIZE_CXX11_CONFORM
+#endif
+
 //@cond
 namespace cds { namespace container {
     namespace striped_set {
@@ -117,7 +122,7 @@ namespace cds { namespace intrusive { namespace striped_set {
         private:
             //@cond
             container_type  m_List;
-#       if defined(__GLIBCXX__ ) && !( CDS_COMPILER == CDS_COMPILER_GCC && CDS_COMPILER_VERSION >= 50000 )
+#       if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
             // GCC C++ lib bug:
             // In GCC, the complexity of std::list::size() is O(N)
             // (see http://gcc.gnu.org/bugzilla/show_bug.cgi?id=49561)
@@ -128,7 +133,7 @@ namespace cds { namespace intrusive { namespace striped_set {
 
         public:
             adapted_container()
-#       if defined(__GLIBCXX__ ) && !( CDS_COMPILER == CDS_COMPILER_GCC && CDS_COMPILER_VERSION >= 50000 )
+#       if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
                 : m_nSize(0)
 #       endif
             {}
@@ -142,7 +147,7 @@ namespace cds { namespace intrusive { namespace striped_set {
                     it = m_List.insert( it, newItem );
                     f( *it );
 
-#           if defined(__GLIBCXX__ ) && !( CDS_COMPILER == CDS_COMPILER_GCC && CDS_COMPILER_VERSION >= 50000 )
+#           if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
                     ++m_nSize;
 #           endif
                     return true;
@@ -159,7 +164,7 @@ namespace cds { namespace intrusive { namespace striped_set {
                 iterator it = std::lower_bound( m_List.begin(), m_List.end(), val, find_predicate() );
                 if ( it == m_List.end() || key_comparator()( val, *it ) != 0 ) {
                     it = m_List.emplace( it, std::move( val ) );
-#           if defined(__GLIBCXX__ ) && !( CDS_COMPILER == CDS_COMPILER_GCC && CDS_COMPILER_VERSION >= 50000 )
+#           if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
                     ++m_nSize;
 #           endif
                     return true;
@@ -176,7 +181,7 @@ namespace cds { namespace intrusive { namespace striped_set {
                     value_type newItem( val );
                     it = m_List.insert( it, newItem );
                     func( true, *it, val );
-#           if defined(__GLIBCXX__ ) && !( CDS_COMPILER == CDS_COMPILER_GCC && CDS_COMPILER_VERSION >= 50000 )
+#           if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
                     ++m_nSize;
 #           endif
                     return std::make_pair( true, true );
@@ -198,7 +203,7 @@ namespace cds { namespace intrusive { namespace striped_set {
                 // key exists
                 f( *it );
                 m_List.erase( it );
-#           if defined(__GLIBCXX__ ) && !( CDS_COMPILER == CDS_COMPILER_GCC && CDS_COMPILER_VERSION >= 50000 )
+#           if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
                 --m_nSize;
 #           endif
 
@@ -215,7 +220,7 @@ namespace cds { namespace intrusive { namespace striped_set {
                 // key exists
                 f( *it );
                 m_List.erase( it );
-#           if defined(__GLIBCXX__ ) && !( CDS_COMPILER == CDS_COMPILER_GCC && CDS_COMPILER_VERSION >= 50000 )
+#           if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
                 --m_nSize;
 #           endif
 
@@ -263,14 +268,14 @@ namespace cds { namespace intrusive { namespace striped_set {
                 assert( it == m_List.end() || key_comparator()( *itWhat, *it ) != 0 );
 
                 copy_item()( m_List, it, itWhat );
-#           if defined(__GLIBCXX__ ) && !( CDS_COMPILER == CDS_COMPILER_GCC && CDS_COMPILER_VERSION >= 50000 )
+#           if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
                 ++m_nSize;
 #           endif
             }
 
             size_t size() const
             {
-#           if defined(__GLIBCXX__ ) && !( CDS_COMPILER == CDS_COMPILER_GCC && CDS_COMPILER_VERSION >= 50000 )
+#           if !defined(CDS_STD_LIST_SIZE_CXX11_CONFORM)
                 return m_nSize;
 #           else
                 return m_List.size();
index 4491bd4..3a882e9 100644 (file)
@@ -57,8 +57,8 @@ namespace cds { namespace gc {
             /// Retired pointer buffer node
             struct retired_ptr_node {
                 retired_ptr         m_ptr   ;   ///< retired pointer
-                retired_ptr_node *  m_pNext     ;   ///< next retired pointer in buffer
-                retired_ptr_node *  m_pNextFree ;   ///< next item in free list of retired_ptr_node
+                atomics::atomic<retired_ptr_node *>  m_pNext     ;   ///< next retired pointer in buffer
+                atomics::atomic<retired_ptr_node *>  m_pNextFree ;   ///< next item in free list of \p retired_ptr_node
             };
 
             /// Internal guard representation
@@ -262,7 +262,7 @@ namespace cds { namespace gc {
                 {
                     retired_ptr_node * pHead = m_pHead.load(atomics::memory_order_acquire);
                     do {
-                        node.m_pNext = pHead;
+                        node.m_pNext.store( pHead, atomics::memory_order_relaxed );
                         // pHead is changed by compare_exchange_weak
                     } while ( !m_pHead.compare_exchange_weak( pHead, &node, atomics::memory_order_release, atomics::memory_order_relaxed ));
 
@@ -277,7 +277,7 @@ namespace cds { namespace gc {
 
                     retired_ptr_node * pHead = m_pHead.load( atomics::memory_order_acquire );
                     do {
-                        pLast->m_pNext = pHead;
+                        pLast->m_pNext.store( pHead, atomics::memory_order_relaxed );
                         // pHead is changed by compare_exchange_weak
                     } while ( !m_pHead.compare_exchange_weak( pHead, pFirst, atomics::memory_order_release, atomics::memory_order_relaxed ) );
 
@@ -326,8 +326,8 @@ namespace cds { namespace gc {
 
                 /// Pool block
                 struct block {
-                    block *     pNext;  ///< next block
-                    item        items[m_nItemPerBlock];   ///< item array
+                    atomics::atomic<block *> pNext;     ///< next block
+                    item        items[m_nItemPerBlock]; ///< item array
                 };
 
                 atomics::atomic<block *> m_pBlockListHead;   ///< head of of allocated block list
@@ -349,24 +349,24 @@ namespace cds { namespace gc {
                     // link items within the block
                     item * pLastItem = pNew->items + m_nItemPerBlock - 1;
                     for ( item * pItem = pNew->items; pItem != pLastItem; ++pItem ) {
-                        pItem->m_pNextFree = pItem + 1;
-                        CDS_STRICT_DO( pItem->m_pNext = nullptr );
+                        pItem->m_pNextFree.store( pItem + 1, atomics::memory_order_release );
+                        CDS_STRICT_DO( pItem->m_pNext.store( nullptr, atomics::memory_order_relaxed ));
                     }
 
                     // links new block to the block list
                     {
-                        block * pHead = m_pBlockListHead.load(atomics::memory_order_acquire);
+                        block * pHead = m_pBlockListHead.load(atomics::memory_order_relaxed);
                         do {
-                            pNew->pNext = pHead;
+                            pNew->pNext.store( pHead, atomics::memory_order_relaxed );
                             // pHead is changed by compare_exchange_weak
-                        } while ( !m_pBlockListHead.compare_exchange_weak( pHead, pNew, atomics::memory_order_release, atomics::memory_order_relaxed ));
+                        } while ( !m_pBlockListHead.compare_exchange_weak( pHead, pNew, atomics::memory_order_relaxed, atomics::memory_order_relaxed ));
                     }
 
                     // links block's items to the free list
                     {
-                        item * pHead = m_pGlobalFreeHead.load(atomics::memory_order_acquire);
+                        item * pHead = m_pGlobalFreeHead.load(atomics::memory_order_relaxed);
                         do {
-                            pLastItem->m_pNextFree = pHead;
+                            pLastItem->m_pNextFree.store( pHead, atomics::memory_order_release );
                             // pHead is changed by compare_exchange_weak
                         } while ( !m_pGlobalFreeHead.compare_exchange_weak( pHead, pNew->items, atomics::memory_order_release, atomics::memory_order_relaxed ));
                     }
@@ -398,7 +398,7 @@ namespace cds { namespace gc {
                 {
                     block * p;
                     for ( block * pBlock = m_pBlockListHead.load(atomics::memory_order_relaxed); pBlock; pBlock = p ) {
-                        p = pBlock->pNext;
+                        p = pBlock->pNext.load( atomics::memory_order_relaxed );
                         m_BlockAllocator.Delete( pBlock );
                     }
                 }
@@ -418,24 +418,30 @@ namespace cds { namespace gc {
                         pItem = m_pEpochFree[ nEpoch = current_epoch() ].load(atomics::memory_order_acquire);
                         if ( !pItem )
                             goto retry;
-                        if ( m_pEpochFree[nEpoch].compare_exchange_weak( pItem, pItem->m_pNextFree, atomics::memory_order_release, atomics::memory_order_relaxed ))
+                        if ( m_pEpochFree[nEpoch].compare_exchange_weak( pItem, 
+                                                                         pItem->m_pNextFree.load(atomics::memory_order_acquire), 
+                                                                         atomics::memory_order_acquire, atomics::memory_order_relaxed ))
+                        { 
                             goto success;
+                        }
                     }
 
                     // Epoch free list is empty
                     // Alloc from global free list
                 retry:
-                    pItem = m_pGlobalFreeHead.load( atomics::memory_order_acquire );
+                    pItem = m_pGlobalFreeHead.load( atomics::memory_order_relaxed );
                     do {
                         if ( !pItem ) {
                             allocNewBlock();
                             goto retry;
                         }
                         // pItem is changed by compare_exchange_weak
-                    } while ( !m_pGlobalFreeHead.compare_exchange_weak( pItem, pItem->m_pNextFree, atomics::memory_order_release, atomics::memory_order_relaxed ));
+                    } while ( !m_pGlobalFreeHead.compare_exchange_weak( pItem, 
+                                                                        pItem->m_pNextFree.load(atomics::memory_order_acquire), 
+                                                                        atomics::memory_order_acquire, atomics::memory_order_relaxed ));
 
                 success:
-                    CDS_STRICT_DO( pItem->m_pNextFree = nullptr );
+                    CDS_STRICT_DO( pItem->m_pNextFree.store( nullptr, atomics::memory_order_relaxed ));
                     return *pItem;
                 }
 
@@ -460,7 +466,7 @@ namespace cds { namespace gc {
                     item * pCurHead;
                     do {
                         pCurHead = m_pEpochFree[nEpoch = next_epoch()].load(atomics::memory_order_acquire);
-                        pTail->m_pNextFree = pCurHead;
+                        pTail->m_pNextFree.store( pCurHead, atomics::memory_order_release );
                     } while ( !m_pEpochFree[nEpoch].compare_exchange_weak( pCurHead, pHead, atomics::memory_order_release, atomics::memory_order_relaxed ));
                 }
             };
index 3f1548a..bbe9b13 100644 (file)
@@ -243,7 +243,7 @@ namespace cds { namespace intrusive {
             link_checker::is_empty( pNode );
 
             marked_node_ptr cur(pos.pCur);
-            pNode->m_pNext.store( cur, memory_model::memory_order_relaxed );
+            pNode->m_pNext.store( cur, memory_model::memory_order_release );
             return pos.pPrev->compare_exchange_strong( cur, marked_node_ptr(pNode), memory_model::memory_order_release, atomics::memory_order_relaxed );
         }
 
@@ -258,7 +258,7 @@ namespace cds { namespace intrusive {
                 // physical deletion may be performed by search function if it detects that a node is logically deleted (marked)
                 // CAS may be successful here or in other thread that searching something
                 marked_node_ptr cur(pos.pCur);
-                if ( pos.pPrev->compare_exchange_strong( cur, marked_node_ptr( pos.pNext ), memory_model::memory_order_release, atomics::memory_order_relaxed ))
+                if ( pos.pPrev->compare_exchange_strong( cur, marked_node_ptr( pos.pNext ), memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
                     retire_node( pos.pCur );
                 return true;
             }
@@ -1077,19 +1077,19 @@ try_again:
             while ( true ) {
                 if ( pCur.ptr() == nullptr ) {
                     pos.pPrev = pPrev;
-                    pos.pCur = pCur.ptr();
-                    pos.pNext = pNext.ptr();
+                    pos.pCur = nullptr;
+                    pos.pNext = nullptr;
                     return false;
                 }
 
-                pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed);
+                pNext = pCur->m_pNext.load(memory_model::memory_order_acquire);
                 pos.guards.assign( position::guard_next_item, node_traits::to_value_ptr( pNext.ptr() ));
                 if ( pCur->m_pNext.load(memory_model::memory_order_relaxed).all() != pNext.all() ) {
                     bkoff();
                     goto try_again;
                 }
 
-                if ( pPrev->load(memory_model::memory_order_relaxed).all() != pCur.ptr() ) {
+                if ( pPrev->load(memory_model::memory_order_acquire).all() != pCur.ptr() ) {
                     bkoff();
                     goto try_again;
                 }
@@ -1098,7 +1098,7 @@ try_again:
                 if ( pNext.bits() == 1 ) {
                     // pCur marked i.e. logically deleted. Help the erase/unlink function to unlink pCur node
                     marked_node_ptr cur( pCur.ptr());
-                    if ( pPrev->compare_exchange_strong( cur, marked_node_ptr( pNext.ptr() ), memory_model::memory_order_release, atomics::memory_order_relaxed )) {
+                    if ( pPrev->compare_exchange_strong( cur, marked_node_ptr( pNext.ptr() ), memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
                         retire_node( pCur.ptr() );
                     }
                     else {
index ceabfa0..a62cf15 100644 (file)
@@ -1142,7 +1142,7 @@ namespace cds { namespace intrusive {
 
             while ( pCur.ptr() != pTail && ( pCur.ptr() == pHead || cmp( *node_traits::to_value_ptr( *pCur.ptr() ), key ) < 0 )) {
                 pPrev = pCur;
-                pCur = pCur->m_pNext.load(memory_model::memory_order_relaxed);
+                pCur = pCur->m_pNext.load(memory_model::memory_order_acquire);
             }
 
             pos.pCur = pCur.ptr();
index 2114e83..25f9ce5 100644 (file)
@@ -138,7 +138,7 @@ namespace cds { namespace intrusive {
             link_checker::is_empty( pNode );
 
             marked_node_ptr p( pos.pCur );
-            pNode->m_pNext.store( p, memory_model::memory_order_relaxed );
+            pNode->m_pNext.store( p, memory_model::memory_order_release );
             return pos.pPrev->compare_exchange_strong( p, marked_node_ptr(pNode), memory_model::memory_order_release, atomics::memory_order_relaxed );
         }
 
@@ -146,12 +146,12 @@ namespace cds { namespace intrusive {
         {
             // Mark the node (logical deleting)
             marked_node_ptr next(pos.pNext, 0);
-            if ( pos.pCur->m_pNext.compare_exchange_strong( next, marked_node_ptr(pos.pNext, 1), memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
+            if ( pos.pCur->m_pNext.compare_exchange_strong( next, marked_node_ptr(pos.pNext, 1), memory_model::memory_order_release, atomics::memory_order_relaxed )) {
                 marked_node_ptr cur(pos.pCur);
-                if ( pos.pPrev->compare_exchange_strong( cur, marked_node_ptr( pos.pNext ), memory_model::memory_order_release, atomics::memory_order_relaxed ))
+                if ( pos.pPrev->compare_exchange_strong( cur, marked_node_ptr( pos.pNext ), memory_model::memory_order_acquire, atomics::memory_order_relaxed ))
                     return true;
                 next |= 1;
-                CDS_VERIFY( pos.pCur->m_pNext.compare_exchange_strong( next, next ^ 1, memory_model::memory_order_release, atomics::memory_order_relaxed ));
+                CDS_VERIFY( pos.pCur->m_pNext.compare_exchange_strong( next, next ^ 1, memory_model::memory_order_relaxed, atomics::memory_order_relaxed ));
             }
             return false;
         }
@@ -980,15 +980,15 @@ namespace cds { namespace intrusive {
             while ( true ) {
                 if ( !pCur.ptr() ) {
                     pos.pPrev = pPrev;
-                    pos.pCur = pCur.ptr();
-                    pos.pNext = pNext.ptr();
+                    pos.pCur = nullptr;
+                    pos.pNext = nullptr;
                     return false;
                 }
 
-                pNext = pCur->m_pNext.load(memory_model::memory_order_relaxed);
+                pNext = pCur->m_pNext.load(memory_model::memory_order_acquire);
 
-                if ( pPrev->load(memory_model::memory_order_acquire) != pCur
-                    || pNext != pCur->m_pNext.load(memory_model::memory_order_acquire)
+                if ( pPrev->load(memory_model::memory_order_relaxed) != pCur
+                    || pNext != pCur->m_pNext.load(memory_model::memory_order_relaxed)
                     || pNext.bits() != 0 )  // pNext contains deletion mark for pCur
                 {
                     // if pCur is marked as deleted (pNext.bits() != 0)
index 3f15411..0be790d 100644 (file)
@@ -478,11 +478,12 @@ namespace cds { namespace intrusive {
                 if ( nMaxCount < max_item_count( nBucketCount, nLoadFactor ))
                     return; // someone already have updated m_nBucketCountLog2, so stop here
 
-                const size_t nNewMaxCount = (nBucketCount < m_Buckets.capacity()) ? max_item_count( nBucketCount << 1, nLoadFactor )
-                                                                                  : std::numeric_limits<size_t>::max();
-                m_nMaxItemCount.compare_exchange_strong( nMaxCount, nNewMaxCount, memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
+                m_nMaxItemCount.compare_exchange_strong( nMaxCount, max_item_count( nBucketCount << 1, nLoadFactor ), 
+                                                         memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
                 m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
             }
+            else
+                m_nMaxItemCount.store( std::numeric_limits<size_t>::max(), memory_model::memory_order_relaxed );
         }
 
         template <typename Q, typename Compare, typename Func>
index 5eeb991..71d258c 100644 (file)
@@ -275,12 +275,12 @@ namespace cds { namespace intrusive {
                 if ( nMaxCount < max_item_count( nBucketCount, nLoadFactor ))
                     return; // someone already have updated m_nBucketCountLog2, so stop here
 
-                const size_t nNewMaxCount = (nBucketCount < m_Buckets.capacity()) ? max_item_count( nBucketCount << 1, nLoadFactor )
-                                                                                  : std::numeric_limits<size_t>::max();
-                m_nMaxItemCount.compare_exchange_strong( nMaxCount, nNewMaxCount, memory_model::memory_order_relaxed,
-                    atomics::memory_order_relaxed );
+                m_nMaxItemCount.compare_exchange_strong( nMaxCount, max_item_count( nBucketCount << 1, nLoadFactor ), 
+                                                         memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
                 m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
             }
+            else
+                m_nMaxItemCount.store( std::numeric_limits<size_t>::max(), memory_model::memory_order_relaxed );
         }
 
         //@endcond
index 293489f..3ba4049 100644 (file)
@@ -372,12 +372,12 @@ namespace cds { namespace intrusive {
                 if ( nMaxCount < max_item_count( nBucketCount, nLoadFactor ))
                     return; // someone already have updated m_nBucketCountLog2, so stop here
 
-                const size_t nNewMaxCount = (nBucketCount < m_Buckets.capacity()) ? max_item_count( nBucketCount << 1, nLoadFactor )
-                                                                                  : std::numeric_limits<size_t>::max();
-                m_nMaxItemCount.compare_exchange_strong( nMaxCount, nNewMaxCount, memory_model::memory_order_relaxed,
-                    atomics::memory_order_relaxed );
+                m_nMaxItemCount.compare_exchange_strong( nMaxCount, max_item_count( nBucketCount << 1, nLoadFactor ), 
+                                                         memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
                 m_nBucketCountLog2.compare_exchange_strong( sz, sz + 1, memory_model::memory_order_relaxed, atomics::memory_order_relaxed );
             }
+            else
+                m_nMaxItemCount.store( std::numeric_limits<size_t>::max(), memory_model::memory_order_relaxed );
         }
 
         template <typename Q, typename Compare, typename Func>
index f79b6e2..023c263 100644 (file)
@@ -107,8 +107,11 @@ namespace cds { namespace urcu {
         {
             epoch_retired_ptr p;
             while ( m_Buffer.pop( p )) {
-                if ( p.m_nEpoch <= nEpoch )
+                if ( p.m_nEpoch <= nEpoch ) {
+                    CDS_TSAN_ANNOTATE_IGNORE_RW_BEGIN;
                     p.free();
+                    CDS_TSAN_ANNOTATE_IGNORE_RW_END;
+                }
                 else {
                     push_buffer( p );
                     break;
@@ -122,8 +125,11 @@ namespace cds { namespace urcu {
             bool bPushed = m_Buffer.push( ep );
             if ( !bPushed || m_Buffer.size() >= capacity() ) {
                 synchronize();
-                if ( !bPushed )
+                if ( !bPushed ) {
+                    CDS_TSAN_ANNOTATE_IGNORE_RW_BEGIN;
                     ep.free();
+                    CDS_TSAN_ANNOTATE_IGNORE_RW_END;
+                }
                 return true;
             }
             return false;
index b72ffec..783a306 100644 (file)
@@ -111,8 +111,11 @@ namespace cds { namespace urcu {
         virtual void retire_ptr( retired_ptr& p )
         {
             synchronize();
-            if ( p.m_p )
+            if ( p.m_p ) {
+                CDS_TSAN_ANNOTATE_IGNORE_RW_BEGIN;
                 p.free();
+                CDS_TSAN_ANNOTATE_IGNORE_RW_END;
+            }
         }
 
         /// Retires the pointer chain [\p itFirst, \p itLast)
index 9bc0d87..84d2c1a 100644 (file)
@@ -113,8 +113,11 @@ namespace cds { namespace urcu {
             bool bPushed = m_Buffer.push( p );
             if ( !bPushed || m_Buffer.size() >= capacity() ) {
                 synchronize();
-                if ( !bPushed )
+                if ( !bPushed ) {
+                    CDS_TSAN_ANNOTATE_IGNORE_RW_BEGIN;
                     p.free();
+                    CDS_TSAN_ANNOTATE_IGNORE_RW_END;
+                }
                 return true;
             }
             return false;
index db4d88c..bb0e0c5 100644 (file)
@@ -68,10 +68,10 @@ namespace cds { namespace urcu {
 
     protected:
         //@cond
-        buffer_type                     m_Buffer;
-        atomics::atomic<uint64_t>    m_nCurEpoch;
-        lock_type                       m_Lock;
-        size_t const                    m_nCapacity;
+        buffer_type               m_Buffer;
+        atomics::atomic<uint64_t> m_nCurEpoch;
+        lock_type                 m_Lock;
+        size_t const              m_nCapacity;
         //@endcond
 
     public:
@@ -104,8 +104,11 @@ namespace cds { namespace urcu {
         {
             epoch_retired_ptr p;
             while ( m_Buffer.pop( p )) {
-                if ( p.m_nEpoch <= nEpoch )
+                if ( p.m_nEpoch <= nEpoch ) {
+                    CDS_TSAN_ANNOTATE_IGNORE_RW_BEGIN;
                     p.free();
+                    CDS_TSAN_ANNOTATE_IGNORE_RW_END;
+                }
                 else {
                     push_buffer( p );
                     break;
@@ -118,8 +121,11 @@ namespace cds { namespace urcu {
             bool bPushed = m_Buffer.push( ep );
             if ( !bPushed || m_Buffer.size() >= capacity() ) {
                 synchronize();
-                if ( !bPushed )
+                if ( !bPushed ) {
+                    CDS_TSAN_ANNOTATE_IGNORE_RW_BEGIN;
                     ep.free();
+                    CDS_TSAN_ANNOTATE_IGNORE_RW_END;
+                }
                 return true;
             }
             return false;
index cf99c54..17d0152 100644 (file)
@@ -110,8 +110,11 @@ namespace cds { namespace urcu {
             bool bPushed = m_Buffer.push( p );
             if ( !bPushed || m_Buffer.size() >= capacity() ) {
                 synchronize();
-                if ( !bPushed )
+                if ( !bPushed ) {
+                    CDS_TSAN_ANNOTATE_IGNORE_RW_BEGIN;
                     p.free();
+                    CDS_TSAN_ANNOTATE_IGNORE_RW_END;
+                }
                 return true;
             }
             return false;
index ca95603..46baa8f 100644 (file)
@@ -102,8 +102,11 @@ namespace cds { namespace urcu {
         {
             epoch_retired_ptr p;
             while ( pBuf->pop( p ) ) {
-                if ( p.m_nEpoch <= nCurEpoch )
+                if ( p.m_nEpoch <= nCurEpoch ) {
+                    CDS_TSAN_ANNOTATE_IGNORE_RW_BEGIN;
                     p.free();
+                    CDS_TSAN_ANNOTATE_IGNORE_RW_END;
+                }
                 else {
                     pBuf->push( p );
                     break;
index a986993..9940c6f 100644 (file)
@@ -1,7 +1,10 @@
 2.1.0
+    - Added: BronsonAVLTreeMap - Bronson's et al AVL tree implementation
+    - Added: CMake build script, thanks to Eugeny Kalishenko
+    - Changed: SplitList performance improving, thanks to Mike Krinkin
     - cds::lock namespace is renamed to cds::sync. All classes defined in cds::lock namespace 
       are moved to cds::sync with new names (for example, cds::lock::SpinLock is renamed to
-      cds::sync::spin_lock). cds::lock namespace and its contents is deprecated and it is kept 
+      cds::sync::spin_lock). cds::lock namespace and its contents is deprecated, it is kept 
       for backward compatibility.
 
 2.0.0 30.12.2014
index 0950449..6b981b4 100644 (file)
     <ClInclude Include="..\..\..\cds\algo\int_algo.h" />\r
     <ClInclude Include="..\..\..\cds\compiler\clang\defs.h" />\r
     <ClInclude Include="..\..\..\cds\compiler\cxx11_atomic.h" />\r
+    <ClInclude Include="..\..\..\cds\compiler\feature_tsan.h" />\r
     <ClInclude Include="..\..\..\cds\compiler\gcc\amd64\cxx11_atomic.h" />\r
     <ClInclude Include="..\..\..\cds\compiler\gcc\compiler_macro.h" />\r
     <ClInclude Include="..\..\..\cds\compiler\gcc\ia64\cxx11_atomic.h" />\r
index 54bc40c..e2042f8 100644 (file)
     <ClInclude Include="..\..\..\cds\sync\pool_monitor.h">\r
       <Filter>Header Files\cds\sync</Filter>\r
     </ClInclude>\r
+    <ClInclude Include="..\..\..\cds\compiler\feature_tsan.h">\r
+      <Filter>Header Files\cds\compiler</Filter>\r
+    </ClInclude>\r
   </ItemGroup>\r
 </Project>
\ No newline at end of file
index ea41aa1..cd96598 100644 (file)
@@ -46,23 +46,23 @@ namespace cds { namespace gc { namespace dhp {
 
             void insert( retired_ptr_node& node )
             {
-                node.m_pNext = nullptr;
+                node.m_pNext.store( nullptr, atomics::memory_order_relaxed );
 
                 item_type& refBucket = bucket( node );
                 if ( refBucket ) {
                     item_type p = refBucket;
                     do {
                         if ( p->m_ptr.m_p == node.m_ptr.m_p ) {
-                            assert( node.m_pNextFree == nullptr );
+                            assert( node.m_pNextFree.load( atomics::memory_order_relaxed ) == nullptr );
 
-                            node.m_pNextFree = p->m_pNextFree;
-                            p->m_pNextFree = &node;
+                            node.m_pNextFree.store( p->m_pNextFree.load( atomics::memory_order_relaxed ), atomics::memory_order_relaxed );
+                            p->m_pNextFree.store( &node, atomics::memory_order_relaxed );
                             return;
                         }
-                        p = p->m_pNext;
+                        p = p->m_pNext.load(atomics::memory_order_relaxed);
                     } while ( p );
 
-                    node.m_pNext = refBucket;
+                    node.m_pNext.store( refBucket, atomics::memory_order_relaxed );
                 }
                 refBucket = &node;
             }
@@ -76,14 +76,14 @@ namespace cds { namespace gc { namespace dhp {
                 while ( p ) {
                     if ( p->m_ptr.m_p == ptr ) {
                         if ( pPrev )
-                            pPrev->m_pNext = p->m_pNext;
+                            pPrev->m_pNext.store( p->m_pNext.load(atomics::memory_order_relaxed ), atomics::memory_order_relaxed );
                         else
-                            refBucket = p->m_pNext;
-                        p->m_pNext = nullptr;
+                            refBucket = p->m_pNext.load(atomics::memory_order_relaxed);
+                        p->m_pNext.store( nullptr, atomics::memory_order_relaxed );
                         return p;
                     }
                     pPrev = p;
-                    p = p->m_pNext;
+                    p = p->m_pNext.load( atomics::memory_order_relaxed );
                 }
 
                 return nullptr;
@@ -103,22 +103,24 @@ namespace cds { namespace gc { namespace dhp {
                         if ( !ret.first )
                             ret.first = pBucket;
                         else
-                            pTail->m_pNextFree = pBucket;
+                            pTail->m_pNextFree.store( pBucket, atomics::memory_order_relaxed );
 
                         pTail = pBucket;
                         for (;;) {
-                            item_type pNext = pTail->m_pNext;
+                            item_type pNext = pTail->m_pNext.load( atomics::memory_order_relaxed );
                             pTail->m_ptr.free();
-                            pTail->m_pNext = nullptr;
+                            pTail->m_pNext.store( nullptr, atomics::memory_order_relaxed );
 
-                            while ( pTail->m_pNextFree ) {
-                                pTail = pTail->m_pNextFree;
+                            while ( pTail->m_pNextFree.load( atomics::memory_order_relaxed )) {
+                                pTail = pTail->m_pNextFree.load( atomics::memory_order_relaxed );
                                 pTail->m_ptr.free();
-                                pTail->m_pNext = nullptr;
+                                pTail->m_pNext.store( nullptr, atomics::memory_order_relaxed );
                             }
 
-                            if ( pNext )
-                                pTail = pTail->m_pNextFree = pNext;
+                            if ( pNext ) {
+                                pTail->m_pNextFree.store( pNext, atomics::memory_order_relaxed );
+                                pTail = pNext;
+                            }
                             else
                                 break;
                         }
@@ -126,7 +128,7 @@ namespace cds { namespace gc { namespace dhp {
                 }
 
                 if ( pTail )
-                    pTail->m_pNextFree = nullptr;
+                    pTail->m_pNextFree.store( nullptr, atomics::memory_order_relaxed );
                 ret.second = pTail;
                 return ret;
             }
@@ -174,8 +176,8 @@ namespace cds { namespace gc { namespace dhp {
             // Get list of retired pointers
             details::retired_ptr_node * pHead = retiredList.first;
             while ( pHead ) {
-                details::retired_ptr_node * pNext = pHead->m_pNext;
-                pHead->m_pNextFree = nullptr;
+                details::retired_ptr_node * pNext = pHead->m_pNext.load( atomics::memory_order_relaxed );
+                pHead->m_pNextFree.store( nullptr, atomics::memory_order_relaxed );
                 set.insert( *pHead );
                 pHead = pNext;
             }
@@ -189,7 +191,7 @@ namespace cds { namespace gc { namespace dhp {
             for ( details::guard_data * pGuard = m_GuardPool.begin(); pGuard; pGuard = pGuard->pGlobalNext.load(atomics::memory_order_acquire) )
             {
                 // get guarded pointer
-                details::guard_data::guarded_ptr  valGuarded = pGuard->pPost.load(atomics::memory_order_acquire);
+                details::guard_data::guarded_ptr valGuarded = pGuard->pPost.load(atomics::memory_order_acquire);
 
                 if ( valGuarded ) {
                     details::retired_ptr_node * pRetired = set.erase( valGuarded );
@@ -199,13 +201,15 @@ namespace cds { namespace gc { namespace dhp {
                         // List is linked on m_pNextFree field
 
                         if ( pBusyLast )
-                            pBusyLast->m_pNext = pRetired;
+                            pBusyLast->m_pNext.store( pRetired, atomics::memory_order_relaxed );
                         else
                             pBusyFirst = pRetired;
                         pBusyLast = pRetired;
                         ++nBusyCount;
-                        while ( pBusyLast->m_pNextFree ) {
-                            pBusyLast = pBusyLast->m_pNext = pBusyLast->m_pNextFree;
+                        details::retired_ptr_node * p = pBusyLast->m_pNextFree.load(atomics::memory_order_relaxed);
+                        while ( p != nullptr ) {
+                            pBusyLast->m_pNext.store( p, atomics::memory_order_relaxed );
+                            pBusyLast = p;
                             ++nBusyCount;
                         }
                     }
index a50aa37..bac9801 100644 (file)
@@ -1,7 +1,8 @@
 //$$CDS-header$$
 
+#include <chrono>
+#include <cds/details/defs.h> // TSan annotations
 #include "cppunit/thread.h"
-#include <boost/date_time/posix_time/posix_time_types.hpp>
 
 namespace CppUnitMini {
 
@@ -42,12 +43,16 @@ namespace CppUnitMini {
 
     ThreadPool::~ThreadPool()
     {
+        CDS_TSAN_ANNOTATE_IGNORE_RW_BEGIN;
+
         delete m_pBarrierStart;
         delete m_pBarrierDone;
 
         for ( size_t i = 0; i < m_arrThreads.size(); ++i )
             delete m_arrThreads[i];
         m_arrThreads.resize( 0 );
+
+        CDS_TSAN_ANNOTATE_IGNORE_RW_END;
     }
 
     void    ThreadPool::add( TestThread * pThread, size_t nCount )
@@ -75,7 +80,7 @@ namespace CppUnitMini {
 
         // Wait while all threads is done
         m_pBarrierDone->wait();
-        boost::this_thread::sleep(boost::posix_time::milliseconds(500));
+        std::this_thread::sleep_for(std::chrono::milliseconds(500));
     }
 
     void ThreadPool::run( unsigned int nDuration )
@@ -87,17 +92,17 @@ namespace CppUnitMini {
         for ( size_t i = 0; i < nThreadCount; ++i )
             m_arrThreads[i]->create();
 
-        boost::system_time stEnd( boost::get_system_time() + boost::posix_time::seconds( nDuration ) );
+        auto stEnd(std::chrono::steady_clock::now() + std::chrono::seconds( nDuration ));
         do {
-            boost::this_thread::sleep( stEnd );
-        } while ( boost::get_system_time() < stEnd );
+            std::this_thread::sleep_until( stEnd );
+        } while ( std::chrono::steady_clock::now() < stEnd );
 
         for ( size_t i = 0; i < nThreadCount; ++i )
             m_arrThreads[i]->stop();
 
         // Wait while all threads is done
         m_pBarrierDone->wait();
-        boost::this_thread::sleep(boost::posix_time::milliseconds(500));
+        std::this_thread::sleep_for(std::chrono::milliseconds(500));
     }
 
     void    ThreadPool::onThreadInitDone( TestThread * pThread )
diff --git a/thanks b/thanks
index 6b40ec9..f28bb88 100644 (file)
--- a/thanks
+++ b/thanks
@@ -2,7 +2,9 @@ Many thanks to the contributors who feedbacks the errors and propositions for li
 In alphabetical order:\r
 \r
 blinkenlichten (https://github.com/blinkenlichten)\r
+Eugeny Kalishenko (https://github.com/eugenyk)\r
 Jelle van den Hooff\r
 Lucas Larsch\r
 Markus Elfring\r
+Mike Krinkin (https://github.com/krinkinmu)\r
 Tamas Lengyel\r
index 0c8cd10..1e9d948 100644 (file)
@@ -26,7 +26,8 @@ print "make copyright...\n" ;
 makeCopyright($DistrDir);\r
 \r
 print "patch files...\n";\r
-patch_file("$DistrDir/build/Makefile", 'VERSION=\d+\.\d+\.\d+', "VERSION=$Version" ) ;\r
+patch_file("$DistrDir/build/Makefile", 'VERSION=\d+\.\d+\.\d+', "VERSION=$Version" );\r
+patch_file("$DistrDir/CMakeList.txt", 'PROJECT_VERSION \d+\.\d+\.\d+', "PROJECT_VERSION $Version" );\r
 patch_file("$DistrDir/doxygen/cds.doxy", 'PROJECT_NUMBER\s*=\s*\d+\.\d+\.\d+', "PROJECT_NUMBER = $Version" ) ;\r
 patch_file("$DistrDir/projects/android/jni/Android.mk", 'CDS_LIBRARY_VERSION\s*:=\s*\d+\.\d+\.\d+', \r
    "CDS_LIBRARY_VERSION := $Version" );\r