From 1b5087c99fb779e0b82efdfc9523a848fe593bb1 Mon Sep 17 00:00:00 2001 From: khizmax Date: Tue, 20 Sep 2016 19:33:43 +0300 Subject: [PATCH] Fixed spplit-list bucket allocation function --- CMakeLists.txt | 4 +- cds/intrusive/split_list.h | 48 +++++++++---------- cds/intrusive/split_list_nogc.h | 47 ++++++++++-------- cds/intrusive/split_list_rcu.h | 47 ++++++++++-------- .../vc14/gtest-intrusive-set.vcxproj.filters | 4 -- 5 files changed, 79 insertions(+), 71 deletions(-) diff --git a/CMakeLists.txt b/CMakeLists.txt index 9362edc6..139d5b8e 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -81,9 +81,7 @@ endif() if(CMAKE_COMPILER_IS_GNUCXX) set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -std=c++11 -Wall -Wextra -pedantic -fno-strict-aliasing") if(CMAKE_TARGET_ARCHITECTURE STREQUAL "x86_64") - set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -mcx16 -m64") - elseif(CMAKE_TARGET_ARCHITECTURE STREQUAL "i386") - set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -m32") + set(CMAKE_CXX_FLAGS "${CMAKE_CXX_FLAGS} -mcx16") endif() if(CMAKE_CXX_COMPILER_VERSION VERSION_LESS "4.9.0") # gcc 4.8: disable noise -Wunused-local-typedefs diff --git a/cds/intrusive/split_list.h b/cds/intrusive/split_list.h index f096b2d4..de983fae 100644 --- a/cds/intrusive/split_list.h +++ b/cds/intrusive/split_list.h @@ -992,7 +992,7 @@ namespace cds { namespace intrusive { return nBucket & ~(1 << bitop::MSBnz( nBucket )); } - aux_node_type * init_bucket( size_t nBucket ) + aux_node_type * init_bucket( size_t const nBucket ) { assert( nBucket > 0 ); size_t nParent = parent_bucket( nBucket ); @@ -1005,9 +1005,14 @@ namespace cds { namespace intrusive { assert( pParentBucket != nullptr ); - // Allocate a dummy node for new bucket - aux_node_type * pBucket; - if ( ( pBucket = m_Buckets.bucket( nBucket )) == nullptr ) { + // Allocate an aux node for new bucket + aux_node_type * pBucket = m_Buckets.bucket( nBucket ); + + back_off bkoff; + for ( ;; pBucket = m_Buckets.bucket( nBucket )) { + if ( pBucket ) + return pBucket; + pBucket = alloc_aux_node( split_list::dummy_hash( nBucket ) ); if ( pBucket ) { if ( m_List.insert_aux_node( pParentBucket, pBucket ) ) { @@ -1015,35 +1020,26 @@ namespace cds { namespace intrusive { m_Stat.onNewBucket(); return pBucket; } - else { - // Another thread set the bucket. Wait while it done - free_aux_node( pBucket ); - } - } - else { - // There are no free buckets. It means that the bucket table is full - // Wait while another thread set th bucket - m_Stat.onBucketsExhausted(); + + // Another thread set the bucket. Wait while it done + free_aux_node( pBucket ); + m_Stat.onBucketInitContenton(); + break; } + + // There are no free buckets. It means that the bucket table is full + // Wait while another thread set the bucket or a free bucket will be available + m_Stat.onBucketsExhausted(); + bkoff(); } - else - return pBucket; // Another thread set the bucket. Wait while it done - - // In this point, we must wait while nBucket is empty. - // The compiler can decide that waiting loop can be "optimized" (stripped) - // To prevent this situation, we use waiting on volatile bucket_head_ptr pointer. - - m_Stat.onBucketInitContenton(); - back_off bkoff; - while ( true ) { - aux_node_type volatile * p = m_Buckets.bucket( nBucket ); - if ( p != nullptr ) - return const_cast(p); + for ( pBucket = m_Buckets.bucket( nBucket ); pBucket == nullptr; pBucket = m_Buckets.bucket( nBucket )) { bkoff(); m_Stat.onBusyWaitBucketInit(); } + + return pBucket; } aux_node_type * get_bucket( size_t nHash ) diff --git a/cds/intrusive/split_list_nogc.h b/cds/intrusive/split_list_nogc.h index ef8acbe0..accccd6f 100644 --- a/cds/intrusive/split_list_nogc.h +++ b/cds/intrusive/split_list_nogc.h @@ -610,7 +610,7 @@ namespace cds { namespace intrusive { return nBucket & ~(1 << bitop::MSBnz( nBucket )); } - aux_node_type * init_bucket( size_t nBucket ) + aux_node_type * init_bucket( size_t const nBucket ) { assert( nBucket > 0 ); size_t nParent = parent_bucket( nBucket ); @@ -623,32 +623,41 @@ namespace cds { namespace intrusive { assert( pParentBucket != nullptr ); - // Allocate a dummy node for new bucket - { - aux_node_type * pBucket = alloc_aux_node( split_list::dummy_hash( nBucket ) ); - if ( m_List.insert_aux_node( pParentBucket, pBucket ) ) { - m_Buckets.bucket( nBucket, pBucket ); - m_Stat.onNewBucket(); + // Allocate an aux node for new bucket + aux_node_type * pBucket = m_Buckets.bucket( nBucket ); + + back_off bkoff; + for ( ;; pBucket = m_Buckets.bucket( nBucket ) ) { + if ( pBucket ) return pBucket; + + pBucket = alloc_aux_node( split_list::dummy_hash( nBucket ) ); + if ( pBucket ) { + if ( m_List.insert_aux_node( pParentBucket, pBucket ) ) { + m_Buckets.bucket( nBucket, pBucket ); + m_Stat.onNewBucket(); + return pBucket; + } + + // Another thread set the bucket. Wait while it done + free_aux_node( pBucket ); + m_Stat.onBucketInitContenton(); + break; } - free_aux_node( pBucket ); + + // There are no free buckets. It means that the bucket table is full + // Wait while another thread set the bucket or a free bucket will be available + m_Stat.onBucketsExhausted(); + bkoff(); } // Another thread set the bucket. Wait while it done - - // In this point, we must wait while nBucket is empty. - // The compiler can decide that waiting loop can be "optimized" (stripped) - // To prevent this situation, we use waiting on volatile bucket_head_ptr pointer. - // - m_Stat.onBucketInitContenton(); - back_off bkoff; - while ( true ) { - aux_node_type volatile * p = m_Buckets.bucket( nBucket ); - if ( p && p != nullptr ) - return const_cast(p); + for ( pBucket = m_Buckets.bucket( nBucket ); pBucket == nullptr; pBucket = m_Buckets.bucket( nBucket ) ) { bkoff(); m_Stat.onBusyWaitBucketInit(); } + + return pBucket; } aux_node_type * get_bucket( size_t nHash ) diff --git a/cds/intrusive/split_list_rcu.h b/cds/intrusive/split_list_rcu.h index 73f05a26..68949e60 100644 --- a/cds/intrusive/split_list_rcu.h +++ b/cds/intrusive/split_list_rcu.h @@ -901,7 +901,7 @@ namespace cds { namespace intrusive { return nBucket & ~( 1 << bitop::MSBnz( nBucket ) ); } - aux_node_type * init_bucket( size_t nBucket ) + aux_node_type * init_bucket( size_t const nBucket ) { assert( nBucket > 0 ); size_t nParent = parent_bucket( nBucket ); @@ -914,32 +914,41 @@ namespace cds { namespace intrusive { assert( pParentBucket != nullptr ); - // Allocate a dummy node for new bucket - { - aux_node_type * pBucket = alloc_aux_node( split_list::dummy_hash( nBucket ) ); - if ( m_List.insert_aux_node( pParentBucket, pBucket ) ) { - m_Buckets.bucket( nBucket, pBucket ); - m_Stat.onNewBucket(); + // Allocate an aux node for new bucket + aux_node_type * pBucket = m_Buckets.bucket( nBucket ); + + back_off bkoff; + for ( ;; pBucket = m_Buckets.bucket( nBucket ) ) { + if ( pBucket ) return pBucket; + + pBucket = alloc_aux_node( split_list::dummy_hash( nBucket ) ); + if ( pBucket ) { + if ( m_List.insert_aux_node( pParentBucket, pBucket ) ) { + m_Buckets.bucket( nBucket, pBucket ); + m_Stat.onNewBucket(); + return pBucket; + } + + // Another thread set the bucket. Wait while it done + free_aux_node( pBucket ); + m_Stat.onBucketInitContenton(); + break; } - free_aux_node( pBucket ); + + // There are no free buckets. It means that the bucket table is full + // Wait while another thread set the bucket or a free bucket will be available + m_Stat.onBucketsExhausted(); + bkoff(); } // Another thread set the bucket. Wait while it done - - // In this point, we must wait while nBucket is empty. - // The compiler can decide that waiting loop can be "optimized" (stripped) - // To prevent this situation, we use waiting on volatile bucket_head_ptr pointer. - // - m_Stat.onBucketInitContenton(); - back_off bkoff; - while ( true ) { - aux_node_type volatile * p = m_Buckets.bucket( nBucket ); - if ( p != nullptr ) - return const_cast( p ); + for ( pBucket = m_Buckets.bucket( nBucket ); pBucket == nullptr; pBucket = m_Buckets.bucket( nBucket ) ) { bkoff(); m_Stat.onBusyWaitBucketInit(); } + + return pBucket; } aux_node_type * get_bucket( size_t nHash ) diff --git a/projects/Win/vc14/gtest-intrusive-set.vcxproj.filters b/projects/Win/vc14/gtest-intrusive-set.vcxproj.filters index 027cb084..72708967 100644 --- a/projects/Win/vc14/gtest-intrusive-set.vcxproj.filters +++ b/projects/Win/vc14/gtest-intrusive-set.vcxproj.filters @@ -9,10 +9,6 @@ {93995380-89BD-4b04-88EB-625FBE52EBFB} h;hh;hpp;hxx;hm;inl;inc;xsd - - {67DA6AB6-F800-4c08-8B7A-83BB121AAD01} - rc;ico;cur;bmp;dlg;rc2;rct;bin;rgs;gif;jpg;jpeg;jpe;resx;tiff;tif;png;wav;mfcribbon-ms - {9f3cc5d8-7142-4a8e-a520-512911312b13} -- 2.34.1