X-Git-Url: http://plrg.eecs.uci.edu/git/?p=libcds.git;a=blobdiff_plain;f=cds%2Fintrusive%2Fdetails%2Fsplit_list_base.h;h=ce7c299ef57b9cbba1777676a9ee03cc1ee9f8fe;hp=6b748e6d61145ea160f56622e10f5b5fc1d5e61c;hb=fb39f01da6fceb1d350bc0cae8ff2ed22b3c128b;hpb=393b80e12e2067c23471b8a323651aa044f6d975 diff --git a/cds/intrusive/details/split_list_base.h b/cds/intrusive/details/split_list_base.h index 6b748e6d..ce7c299e 100644 --- a/cds/intrusive/details/split_list_base.h +++ b/cds/intrusive/details/split_list_base.h @@ -1,14 +1,45 @@ -//$$CDS-header$$ +/* + This file is a part of libcds - Concurrent Data Structures library + + (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017 + + Source code repo: http://github.com/khizmax/libcds/ + Download: http://sourceforge.net/projects/libcds/files/ + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions are met: + + * Redistributions of source code must retain the above copyright notice, this + list of conditions and the following disclaimer. + + * Redistributions in binary form must reproduce the above copyright notice, + this list of conditions and the following disclaimer in the documentation + and/or other materials provided with the distribution. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" + AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE + FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER + CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, + OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +*/ #ifndef CDSLIB_INTRUSIVE_DETAILS_SPLIT_LIST_BASE_H #define CDSLIB_INTRUSIVE_DETAILS_SPLIT_LIST_BASE_H #include #include +#include #include #include #include #include +#include +#include namespace cds { namespace intrusive { @@ -17,51 +48,95 @@ namespace cds { namespace intrusive { */ namespace split_list { //@cond - struct implementation_tag; + struct hash_node + { + size_t m_nHash; ///< Hash value for node + + /// Default constructor + hash_node() + : m_nHash( 0 ) + { + assert( is_dummy()); + } + + /// Initializes dummy node with \p nHash value + explicit hash_node( size_t nHash ) + : m_nHash( nHash ) + { + assert( is_dummy()); + } + + /// Checks if the node is dummy node + bool is_dummy() const + { + return (m_nHash & 1) == 0; + } + }; //@endcond /// Split-ordered list node /** Template parameter: - - OrderedListNode - node type for underlying ordered list + - \p OrderedListNode - node type for underlying ordered list */ template - struct node: public OrderedListNode + struct node: public OrderedListNode, public hash_node { //@cond typedef OrderedListNode base_class; //@endcond - size_t m_nHash ; ///< Hash value for node - /// Default constructor node() - : m_nHash(0) + : hash_node(0) { - assert( is_dummy() ); + assert( is_dummy()); } /// Initializes dummy node with \p nHash value - node( size_t nHash ) - : m_nHash( nHash ) + explicit node( size_t nHash ) + : hash_node( nHash ) { - assert( is_dummy() ); + assert( is_dummy()); } /// Checks if the node is dummy node bool is_dummy() const { - return (m_nHash & 1) == 0; + return hash_node::is_dummy(); + } + }; + + //@cond + // for IterableList + template <> + struct node: public hash_node + { + // Default ctor + node() + : hash_node( 0 ) + { + assert( is_dummy()); + } + + /// Initializes dummy node with \p nHash value + explicit node( size_t nHash ) + : hash_node( nHash ) + { + assert( is_dummy()); + } + + /// Checks if the node is dummy node + bool is_dummy() const + { + return hash_node::is_dummy(); } }; + //@endcond - /// SplitListSet internal statistics. May be used for debugging or profiling + /// \p SplitListSet internal statistics. May be used for debugging or profiling /** - Template argument \p Counter defines type of counter. - Default is \p cds::atomicity::event_counter, that is weak, i.e. it is not guaranteed - strict event counting. - You may use stronger type of counter like as \p cds::atomicity::item_counter, - or even integral type, for example, \p int. + Template argument \p Counter defines type of counter, default is \p cds::atomicity::event_counter. */ template struct stat @@ -70,8 +145,8 @@ namespace cds { namespace intrusive { counter_type m_nInsertSuccess; ///< Count of success inserting counter_type m_nInsertFailed; ///< Count of failed inserting - counter_type m_nEnsureNew; ///< Count of new item created by \p ensure() member function - counter_type m_nEnsureExist; ///< Count of \p ensure() call for existing item + counter_type m_nUpdateNew; ///< Count of new item created by \p ensure() member function + counter_type m_nUpdateExist; ///< Count of \p ensure() call for existing item counter_type m_nEraseSuccess; ///< Count of success erasing of items counter_type m_nEraseFailed; ///< Count of attempts to erase unknown item counter_type m_nExtractSuccess; ///< Count of success extracting of items @@ -84,12 +159,13 @@ namespace cds { namespace intrusive { counter_type m_nInitBucketRecursive; ///< Count of recursive bucket initialization counter_type m_nInitBucketContention; ///< Count of bucket init contention encountered counter_type m_nBusyWaitBucketInit; ///< Count of busy wait cycle while a bucket is initialized + counter_type m_nBucketsExhausted; ///< Count of failed bucket allocation //@cond void onInsertSuccess() { ++m_nInsertSuccess; } void onInsertFailed() { ++m_nInsertFailed; } - void onEnsureNew() { ++m_nEnsureNew; } - void onEnsureExist() { ++m_nEnsureExist; } + void onUpdateNew() { ++m_nUpdateNew; } + void onUpdateExist() { ++m_nUpdateExist; } void onEraseSuccess() { ++m_nEraseSuccess; } void onEraseFailed() { ++m_nEraseFailed; } void onExtractSuccess() { ++m_nExtractSuccess; } @@ -110,6 +186,7 @@ namespace cds { namespace intrusive { void onRecursiveInitBucket() { ++m_nInitBucketRecursive; } void onBucketInitContenton() { ++m_nInitBucketContention; } void onBusyWaitBucketInit() { ++m_nBusyWaitBucketInit; } + void onBucketsExhausted() { ++m_nBucketsExhausted; } //@endcond }; @@ -118,8 +195,8 @@ namespace cds { namespace intrusive { //@cond void onInsertSuccess() const {} void onInsertFailed() const {} - void onEnsureNew() const {} - void onEnsureExist() const {} + void onUpdateNew() const {} + void onUpdateExist() const {} void onEraseSuccess() const {} void onEraseFailed() const {} void onExtractSuccess() const {} @@ -133,6 +210,23 @@ namespace cds { namespace intrusive { void onRecursiveInitBucket() const {} void onBucketInitContenton() const {} void onBusyWaitBucketInit() const {} + void onBucketsExhausted() const {} + //@endcond + }; + + /// Option to control bit reversal algorithm + /** + Bit reversal is a significant part of split-list. + \p Type can be one of predefined algorithm in \p cds::algo::bit_reversal namespace. + */ + template + struct bit_reversal { + //@cond + template + struct pack: public Base + { + typedef Type bit_reversal; + }; //@endcond }; @@ -147,13 +241,24 @@ namespace cds { namespace intrusive { */ typedef opt::none hash; + /// Bit reversal algorithm + /** + Bit reversal is a significant part of split-list. + There are several predefined algorithm in \p cds::algo::bit_reversal namespace, + \p cds::algo::bit_reversal::lookup is the best general purpose one. + + There are more efficient bit reversal algoritm for particular processor architecture, + for example, based on x86 SIMD/AVX instruction set, see here + */ + typedef cds::algo::bit_reversal::lookup bit_reversal; + /// Item counter /** The item counting is an important part of \p SplitListSet algorithm: the empty() member function depends on correct item counting. Therefore, \p cds::atomicity::empty_item_counter is not allowed as a type of the option. - Default is \p cds::atomicity::item_counter. + Default is \p cds::atomicity::item_counter; to avoid false sharing you may use \p atomicity::cache_friendly_item_counter */ typedef cds::atomicity::item_counter item_counter; @@ -192,6 +297,23 @@ namespace cds { namespace intrusive { /// Back-off strategy typedef cds::backoff::Default back_off; + + /// Padding; default is cache-line padding + enum { + padding = cds::opt::cache_line_padding + }; + + /// Free-list of auxiliary nodes + /** + The split-list contains auxiliary nodes marked the start of buckets. + To increase performance, there is a pool of preallocated aux nodes. The part of the pool is a free-list + of aux nodes. + + Default is: + - \p cds::intrusive::FreeList - if architecture and/or compiler does not support double-width CAS primitive + - \p cds::intrusive::TaggedFreeList - if architecture and/or compiler supports double-width CAS primitive + */ + typedef FreeListImpl free_list; }; /// [value-option] Split-list dynamic bucket table option @@ -216,17 +338,21 @@ namespace cds { namespace intrusive { /** Available \p Options: - \p opt::hash - mandatory option, specifies hash functor. + - \p split_list::bit_reversal - bit reversal algorithm, see \p traits::bit_reversal for explanation + default is \p cds::algo::bit_reversal::lookup - \p opt::item_counter - optional, specifies item counting policy. See \p traits::item_counter for default type. - \p opt::memory_model - C++ memory model for atomic operations. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default) - or \p opt::v::sequential_consistent (sequentially consisnent memory model). + or \p opt::v::sequential_consistent (sequentially consistent memory model). - \p opt::allocator - optional, bucket table allocator. Default is \ref CDS_DEFAULT_ALLOCATOR. - \p split_list::dynamic_bucket_table - use dynamic or static bucket table implementation. Dynamic bucket table expands its size up to maximum bucket count when necessary - - \p opt::back_off - back-off strategy used for spinning, defult is \p cds::backoff::Default. + - \p opt::back_off - back-off strategy used for spinning, default is \p cds::backoff::Default. - \p opt::stat - internal statistics, default is \p split_list::empty_stat (disabled). To enable internal statistics use \p split_list::stat. + - \p opt::padding - a padding to solve false-sharing issues; default is cache-line padding + - \p opt::free_list - a free-list implementation, see \p traits::free_list */ template struct make_traits { @@ -246,6 +372,8 @@ namespace cds { namespace intrusive { \p Options are: - \p opt::allocator - allocator used to allocate bucket table. Default is \ref CDS_DEFAULT_ALLOCATOR - \p opt::memory_model - memory model used. Possible types are \p opt::v::sequential_consistent, \p opt::v::relaxed_ordering + - \p opt::free_list - free-list implementation; default is \p TaggedFreeList if the processor supports double-with CAS + otherwise \p FreeList. */ template class static_bucket_table @@ -255,35 +383,59 @@ namespace cds { namespace intrusive { { typedef CDS_DEFAULT_ALLOCATOR allocator; typedef opt::v::relaxed_ordering memory_model; + typedef FreeListImpl free_list; }; typedef typename opt::make_options< default_options, Options... >::type options; //@endcond public: - typedef GC gc; ///< Garbage collector - typedef Node node_type; ///< Bucket node type - typedef atomics::atomic table_entry; ///< Table entry type + typedef GC gc; ///< Garbage collector + typedef Node node_type; ///< Bucket node type + typedef typename options::allocator allocator; ///< allocator + typedef typename options::memory_model memory_model; ///< Memory model for atomic operations + typedef typename options::free_list free_list; ///< Free-list + + /// Auxiliary node type + struct aux_node_type: public node_type, public free_list::node + { +# ifdef CDS_DEBUG + atomics::atomic m_busy; - /// Bucket table allocator - typedef cds::details::Allocator< table_entry, typename options::allocator > bucket_table_allocator; + aux_node_type() + { + m_busy.store( false, atomics::memory_order_release ); + } +# endif + }; - /// Memory model for atomic operations - typedef typename options::memory_model memory_model; + typedef atomics::atomic table_entry; ///< Table entry type + typedef cds::details::Allocator< table_entry, allocator > bucket_table_allocator; ///< Bucket table allocator protected: + //@cond const size_t m_nLoadFactor; ///< load factor (average count of items per bucket) const size_t m_nCapacity; ///< Bucket table capacity table_entry * m_Table; ///< Bucket table + typedef typename allocator::template rebind< aux_node_type >::other aux_node_allocator; + + aux_node_type* m_auxNode; ///< Array of pre-allocated auxiliary nodes + atomics::atomic m_nAuxNodeAllocated; ///< how many auxiliary node allocated + free_list m_freeList; ///< Free list + //@endcond + protected: //@cond void allocate_table() { m_Table = bucket_table_allocator().NewArray( m_nCapacity, nullptr ); + m_auxNode = aux_node_allocator().allocate( m_nCapacity ); } void destroy_table() { + m_freeList.clear( []( typename free_list::node* ) {} ); + aux_node_allocator().deallocate( m_auxNode, m_nCapacity ); bucket_table_allocator().Delete( m_Table, m_nCapacity ); } //@endcond @@ -293,6 +445,7 @@ namespace cds { namespace intrusive { static_bucket_table() : m_nLoadFactor(1) , m_nCapacity( 512 * 1024 ) + , m_nAuxNodeAllocated( 0 ) { allocate_table(); } @@ -302,11 +455,12 @@ namespace cds { namespace intrusive { size_t nItemCount, ///< Max expected item count in split-ordered list size_t nLoadFactor ///< Load factor ) - : m_nLoadFactor( nLoadFactor > 0 ? nLoadFactor : (size_t) 1 ), - m_nCapacity( cds::beans::ceil2( nItemCount / m_nLoadFactor ) ) + : m_nLoadFactor( nLoadFactor > 0 ? nLoadFactor : (size_t) 1 ) + , m_nCapacity( cds::beans::ceil2( nItemCount / m_nLoadFactor )) + , m_nAuxNodeAllocated( 0 ) { // m_nCapacity must be power of 2 - assert( cds::beans::is_power2( m_nCapacity ) ); + assert( cds::beans::is_power2( m_nCapacity )); allocate_table(); } @@ -317,21 +471,48 @@ namespace cds { namespace intrusive { } /// Returns head node of bucket \p nBucket - node_type * bucket( size_t nBucket ) const + aux_node_type * bucket( size_t nBucket ) const { - assert( nBucket < capacity() ); + assert( nBucket < capacity()); return m_Table[ nBucket ].load(memory_model::memory_order_acquire); } /// Set \p pNode as a head of bucket \p nBucket - void bucket( size_t nBucket, node_type * pNode ) + void bucket( size_t nBucket, aux_node_type * pNode ) { - assert( nBucket < capacity() ); + assert( nBucket < capacity()); assert( bucket( nBucket ) == nullptr ); m_Table[ nBucket ].store( pNode, memory_model::memory_order_release ); } + /// Allocates auxiliary node; can return \p nullptr if the table exhausted + aux_node_type* alloc_aux_node() + { + if ( m_nAuxNodeAllocated.load( memory_model::memory_order_relaxed ) < capacity()) { + // alloc next free node from m_auxNode + size_t const idx = m_nAuxNodeAllocated.fetch_add( 1, memory_model::memory_order_relaxed ); + if ( idx < capacity() ) { + CDS_TSAN_ANNOTATE_NEW_MEMORY( &m_auxNode[idx], sizeof( aux_node_type ) ); + return new( &m_auxNode[idx] ) aux_node_type(); + } + } + + // get from free-list + auto pFree = m_freeList.get(); + if ( pFree ) + return static_cast( pFree ); + + // table exhausted + return nullptr; + } + + /// Places node type to free-list + void free_aux_node( aux_node_type* p ) + { + m_freeList.put( static_cast( p )); + } + /// Returns the capacity of the bucket table size_t capacity() const { @@ -358,7 +539,9 @@ namespace cds { namespace intrusive { \p Options are: - \p opt::allocator - allocator used to allocate bucket table. Default is \ref CDS_DEFAULT_ALLOCATOR - \p opt::memory_model - memory model used. Possible types are \p opt::v::sequential_consistent, \p opt::v::relaxed_ordering - */ + - \p opt::free_list - free-list implementation; default is \p TaggedFreeList if the processor supports double-with CAS + otherwise \p FreeList. + */ template class expandable_bucket_table { @@ -367,28 +550,57 @@ namespace cds { namespace intrusive { { typedef CDS_DEFAULT_ALLOCATOR allocator; typedef opt::v::relaxed_ordering memory_model; + typedef FreeListImpl free_list; }; typedef typename opt::make_options< default_options, Options... >::type options; //@endcond + public: - typedef GC gc; ///< Garbage collector - typedef Node node_type; ///< Bucket node type - typedef atomics::atomic table_entry; ///< Table entry type + typedef GC gc; ///< Garbage collector + typedef Node node_type; ///< Bucket node type + typedef typename options::allocator allocator; ///< allocator /// Memory model for atomic operations typedef typename options::memory_model memory_model; - protected: - typedef atomics::atomic segment_type; ///< Bucket table segment type + /// Free-list + typedef typename options::free_list free_list; - public: - /// Bucket table allocator - typedef cds::details::Allocator< segment_type, typename options::allocator > bucket_table_allocator; + /// Auxiliary node type + struct aux_node_type: public node_type, public free_list::node + { +# ifdef CDS_DEBUG + atomics::atomic m_busy; - /// Bucket table segment allocator - typedef cds::details::Allocator< table_entry, typename options::allocator > segment_allocator; + aux_node_type() + { + m_busy.store( false, atomics::memory_order_release ); + } +# endif + }; protected: + //@cond + typedef atomics::atomic table_entry; ///< Table entry type + typedef atomics::atomic segment_type; ///< Bucket table segment type + + struct aux_node_segment { + atomics::atomic< size_t > aux_node_count; // how many aux nodes allocated from the segment + aux_node_segment* next_segment; + // aux_node_type nodes[]; + + aux_node_segment() + : next_segment( nullptr ) + { + aux_node_count.store( 0, atomics::memory_order_release ); + } + + aux_node_type* segment() + { + return reinterpret_cast( this + 1 ); + } + }; + /// Bucket table metrics struct metrics { size_t nSegmentCount; ///< max count of segments in bucket table @@ -397,85 +609,23 @@ namespace cds { namespace intrusive { size_t nLoadFactor; ///< load factor size_t nCapacity; ///< max capacity of bucket table - //@cond metrics() - : nSegmentCount(1024) - , nSegmentSize(512) - , nSegmentSizeLog2( cds::beans::log2( nSegmentSize ) ) - , nLoadFactor(1) + : nSegmentCount( 1024 ) + , nSegmentSize( 512 ) + , nSegmentSizeLog2( cds::beans::log2( nSegmentSize )) + , nLoadFactor( 1 ) , nCapacity( nSegmentCount * nSegmentSize ) {} - //@endcond }; - const metrics m_metrics; ///< Dynamic bucket table metrics - - protected: - segment_type * m_Segments; ///< bucket table - array of segments - - protected: - //@cond - metrics calc_metrics( size_t nItemCount, size_t nLoadFactor ) - { - metrics m; - - // Calculate m_nSegmentSize and m_nSegmentCount by nItemCount - m.nLoadFactor = nLoadFactor > 0 ? nLoadFactor : 1; - - size_t nBucketCount = (size_t)( ((float) nItemCount) / m.nLoadFactor ); - if ( nBucketCount <= 2 ) { - m.nSegmentCount = 1; - m.nSegmentSize = 2; - } - else if ( nBucketCount <= 1024 ) { - m.nSegmentCount = 1; - m.nSegmentSize = ((size_t) 1) << beans::log2ceil( nBucketCount ); - } - else { - nBucketCount = beans::log2ceil( nBucketCount ); - m.nSegmentCount = - m.nSegmentSize = ((size_t) 1) << ( nBucketCount / 2 ); - if ( nBucketCount & 1 ) - m.nSegmentSize *= 2; - if ( m.nSegmentCount * m.nSegmentSize * m.nLoadFactor < nItemCount ) - m.nSegmentSize *= 2; - } - m.nCapacity = m.nSegmentCount * m.nSegmentSize; - m.nSegmentSizeLog2 = cds::beans::log2( m.nSegmentSize ); - assert( m.nSegmentSizeLog2 != 0 ) ; // - return m; - } - - segment_type * allocate_table() - { - return bucket_table_allocator().NewArray( m_metrics.nSegmentCount, nullptr ); - } - - void destroy_table( segment_type * pTable ) - { - bucket_table_allocator().Delete( pTable, m_metrics.nSegmentCount ); - } - - table_entry * allocate_segment() - { - return segment_allocator().NewArray( m_metrics.nSegmentSize, nullptr ); - } - void destroy_segment( table_entry * pSegment ) - { - segment_allocator().Delete( pSegment, m_metrics.nSegmentSize ); - } - - void init_segments() - { - // m_nSegmentSize must be 2**N - assert( cds::beans::is_power2( m_metrics.nSegmentSize )); - assert( ( ((size_t) 1) << m_metrics.nSegmentSizeLog2) == m_metrics.nSegmentSize ); + /// Bucket table allocator + typedef cds::details::Allocator< segment_type, allocator > bucket_table_allocator; - // m_nSegmentCount must be 2**K - assert( cds::beans::is_power2( m_metrics.nSegmentCount )); + /// Bucket table segment allocator + typedef cds::details::Allocator< table_entry, allocator > segment_allocator; - m_Segments = allocate_table(); - } + // Aux node segment allocator + typedef typename allocator::template rebind::other raw_allocator; //@endcond @@ -484,7 +634,7 @@ namespace cds { namespace intrusive { expandable_bucket_table() : m_metrics( calc_metrics( 512 * 1024, 1 )) { - init_segments(); + init(); } /// Creates the table with specified capacity rounded up to nearest power-of-two @@ -494,50 +644,104 @@ namespace cds { namespace intrusive { ) : m_metrics( calc_metrics( nItemCount, nLoadFactor )) { - init_segments(); + init(); } /// Destroys bucket table ~expandable_bucket_table() { + m_freeList.clear( []( typename free_list::node* ) {} ); + + for ( auto aux_segment = m_auxNodeList.load( atomics::memory_order_relaxed ); aux_segment; ) { + auto next_segment = aux_segment->next_segment; + free_aux_segment( aux_segment ); + aux_segment = next_segment; + } + segment_type * pSegments = m_Segments; for ( size_t i = 0; i < m_metrics.nSegmentCount; ++i ) { - table_entry * pEntry = pSegments[i].load(memory_model::memory_order_relaxed); + table_entry* pEntry = pSegments[i].load(memory_model::memory_order_relaxed); if ( pEntry != nullptr ) destroy_segment( pEntry ); } + destroy_table( pSegments ); } /// Returns head node of the bucket \p nBucket - node_type * bucket( size_t nBucket ) const + aux_node_type * bucket( size_t nBucket ) const { size_t nSegment = nBucket >> m_metrics.nSegmentSizeLog2; assert( nSegment < m_metrics.nSegmentCount ); - table_entry * pSegment = m_Segments[ nSegment ].load(memory_model::memory_order_acquire); + table_entry* pSegment = m_Segments[ nSegment ].load(memory_model::memory_order_acquire); if ( pSegment == nullptr ) return nullptr; // uninitialized bucket return pSegment[ nBucket & (m_metrics.nSegmentSize - 1) ].load(memory_model::memory_order_acquire); } /// Set \p pNode as a head of bucket \p nBucket - void bucket( size_t nBucket, node_type * pNode ) + void bucket( size_t nBucket, aux_node_type * pNode ) { size_t nSegment = nBucket >> m_metrics.nSegmentSizeLog2; assert( nSegment < m_metrics.nSegmentCount ); segment_type& segment = m_Segments[nSegment]; if ( segment.load( memory_model::memory_order_relaxed ) == nullptr ) { - table_entry * pNewSegment = allocate_segment(); + table_entry* pNewSegment = allocate_segment(); table_entry * pNull = nullptr; - if ( !segment.compare_exchange_strong( pNull, pNewSegment, memory_model::memory_order_release, atomics::memory_order_relaxed )) { + if ( !segment.compare_exchange_strong( pNull, pNewSegment, memory_model::memory_order_release, atomics::memory_order_relaxed )) destroy_segment( pNewSegment ); - } } + + assert( segment.load( atomics::memory_order_relaxed )[nBucket & (m_metrics.nSegmentSize - 1)].load( atomics::memory_order_relaxed ) == nullptr ); segment.load(memory_model::memory_order_acquire)[ nBucket & (m_metrics.nSegmentSize - 1) ].store( pNode, memory_model::memory_order_release ); } + /// Allocates auxiliary node; can return \p nullptr if the table exhausted + aux_node_type* alloc_aux_node() + { + aux_node_segment* aux_segment = m_auxNodeList.load( memory_model::memory_order_acquire ); + + for ( ;; ) { + assert( aux_segment != nullptr ); + + // try to allocate from current aux segment + if ( aux_segment->aux_node_count.load( memory_model::memory_order_acquire ) < m_metrics.nSegmentSize ) { + size_t idx = aux_segment->aux_node_count.fetch_add( 1, memory_model::memory_order_relaxed ); + if ( idx < m_metrics.nSegmentSize ) { + CDS_TSAN_ANNOTATE_NEW_MEMORY( aux_segment->segment() + idx, sizeof( aux_node_type ) ); + return new( aux_segment->segment() + idx ) aux_node_type(); + } + } + + // try allocate from free-list + auto pFree = m_freeList.get(); + if ( pFree ) + return static_cast( pFree ); + + // free-list is empty, current segment is full + // try to allocate new aux segment + // We can allocate more aux segments than we need but it is not a problem in this context + aux_node_segment* new_aux_segment = allocate_aux_segment(); + new_aux_segment->next_segment = aux_segment; + new_aux_segment->aux_node_count.fetch_add( 1, memory_model::memory_order_relaxed ); + + if ( m_auxNodeList.compare_exchange_strong( aux_segment, new_aux_segment, memory_model::memory_order_release, atomics::memory_order_acquire ) ) { + CDS_TSAN_ANNOTATE_NEW_MEMORY( new_aux_segment->segment(), sizeof( aux_node_type ) ); + return new( new_aux_segment->segment() ) aux_node_type(); + } + + free_aux_segment( new_aux_segment ); + } + } + + /// Places auxiliary node type to free-list + void free_aux_node( aux_node_type* p ) + { + m_freeList.put( static_cast( p )); + } + /// Returns the capacity of the bucket table size_t capacity() const { @@ -549,73 +753,96 @@ namespace cds { namespace intrusive { { return m_metrics.nLoadFactor; } - }; - /// Split-list node traits - /** - This traits is intended for converting between underlying ordered list node type - and split-list node type + protected: + //@cond + metrics calc_metrics( size_t nItemCount, size_t nLoadFactor ) + { + metrics m; - Template parameter: - - \p BaseNodeTraits - node traits of base ordered list type - */ - template - struct node_traits: private BaseNodeTraits - { - typedef BaseNodeTraits base_class; ///< Base ordered list node type - typedef typename base_class::value_type value_type; ///< Value type - typedef typename base_class::node_type base_node_type; ///< Ordered list node type - typedef node node_type; ///< Spit-list node type + // Calculate m_nSegmentSize and m_nSegmentCount by nItemCount + m.nLoadFactor = nLoadFactor > 0 ? nLoadFactor : 1; - /// Convert value reference to node pointer - static node_type * to_node_ptr( value_type& v ) - { - return static_cast( base_class::to_node_ptr( v ) ); + size_t nBucketCount = ( nItemCount + m.nLoadFactor - 1 ) / m.nLoadFactor; + if ( nBucketCount <= 2 ) { + m.nSegmentCount = 1; + m.nSegmentSize = 2; + } + else if ( nBucketCount <= 1024 ) { + m.nSegmentCount = 1; + m.nSegmentSize = ((size_t)1) << beans::log2ceil( nBucketCount ); + } + else { + nBucketCount = beans::log2ceil( nBucketCount ); + m.nSegmentCount = + m.nSegmentSize = ((size_t)1) << (nBucketCount / 2); + if ( nBucketCount & 1 ) + m.nSegmentSize *= 2; + if ( m.nSegmentCount * m.nSegmentSize * m.nLoadFactor < nItemCount ) + m.nSegmentSize *= 2; + } + m.nCapacity = m.nSegmentCount * m.nSegmentSize; + m.nSegmentSizeLog2 = cds::beans::log2( m.nSegmentSize ); + assert( m.nSegmentSizeLog2 != 0 ); // + return m; } - /// Convert value pointer to node pointer - static node_type * to_node_ptr( value_type * v ) + segment_type * allocate_table() { - return static_cast( base_class::to_node_ptr( v ) ); + return bucket_table_allocator().NewArray( m_metrics.nSegmentCount, nullptr ); } - /// Convert value reference to node pointer (const version) - static node_type const * to_node_ptr( value_type const& v ) + void destroy_table( segment_type * pTable ) { - return static_cast( base_class::to_node_ptr( v ) ); + bucket_table_allocator().Delete( pTable, m_metrics.nSegmentCount ); } - /// Convert value pointer to node pointer (const version) - static node_type const * to_node_ptr( value_type const * v ) + table_entry* allocate_segment() { - return static_cast( base_class::to_node_ptr( v ) ); + return segment_allocator().NewArray( m_metrics.nSegmentSize, nullptr ); } - /// Convert node refernce to value pointer - static value_type * to_value_ptr( node_type& n ) + void destroy_segment( table_entry* pSegment ) { - return base_class::to_value_ptr( static_cast( n ) ); + segment_allocator().Delete( pSegment, m_metrics.nSegmentSize ); } - /// Convert node pointer to value pointer - static value_type * to_value_ptr( node_type * n ) + aux_node_segment* allocate_aux_segment() { - return base_class::to_value_ptr( static_cast( n ) ); + char* p = raw_allocator().allocate( sizeof( aux_node_segment ) + sizeof( aux_node_type ) * m_metrics.nSegmentSize ); + CDS_TSAN_ANNOTATE_NEW_MEMORY( p, sizeof( aux_node_segment ) ); + return new(p) aux_node_segment(); } - /// Convert node reference to value pointer (const version) - static const value_type * to_value_ptr( node_type const & n ) + void free_aux_segment( aux_node_segment* p ) { - return base_class::to_value_ptr( static_cast( n ) ); + raw_allocator().deallocate( reinterpret_cast( p ), sizeof( aux_node_segment ) + sizeof( aux_node_type ) * m_metrics.nSegmentSize ); } - /// Convert node pointer to value pointer (const version) - static const value_type * to_value_ptr( node_type const * n ) + void init() { - return base_class::to_value_ptr( static_cast( n ) ); + // m_nSegmentSize must be 2**N + assert( cds::beans::is_power2( m_metrics.nSegmentSize )); + assert( (((size_t)1) << m_metrics.nSegmentSizeLog2) == m_metrics.nSegmentSize ); + + // m_nSegmentCount must be 2**K + assert( cds::beans::is_power2( m_metrics.nSegmentCount )); + + m_Segments = allocate_table(); + m_auxNodeList = allocate_aux_segment(); } + //@endcond + + protected: + //@cond + metrics const m_metrics; ///< Dynamic bucket table metrics + segment_type* m_Segments; ///< bucket table - array of segments + atomics::atomic m_auxNodeList; ///< segment list of aux nodes + free_list m_freeList; ///< List of free aux nodes + //@endcond }; + //@cond namespace details { template @@ -633,16 +860,6 @@ namespace cds { namespace intrusive { typedef static_bucket_table type; }; - template - struct dummy_node_disposer { - template - void operator()( Node * p ) - { - typedef cds::details::Allocator< Node, Alloc > node_deallocator; - node_deallocator().Delete( p ); - } - }; - template struct search_value_type { @@ -655,8 +872,11 @@ namespace cds { namespace intrusive { {} }; + template + class ordered_list_adapter; + template - class rebind_list_traits + class ordered_list_adapter< OrderedList, Traits, false > { typedef OrderedList native_ordered_list; typedef Traits traits; @@ -665,7 +885,7 @@ namespace cds { namespace intrusive { typedef typename native_ordered_list::key_comparator native_key_comparator; typedef typename native_ordered_list::node_type node_type; typedef typename native_ordered_list::value_type value_type; - typedef typename native_ordered_list::node_traits node_traits; + typedef typename native_ordered_list::node_traits native_node_traits; typedef typename native_ordered_list::disposer native_disposer; typedef split_list::node splitlist_node_type; @@ -673,30 +893,30 @@ namespace cds { namespace intrusive { struct key_compare { int operator()( value_type const& v1, value_type const& v2 ) const { - splitlist_node_type const * n1 = static_cast( node_traits::to_node_ptr( v1 )); - splitlist_node_type const * n2 = static_cast( node_traits::to_node_ptr( v2 )); + splitlist_node_type const * n1 = static_cast(native_node_traits::to_node_ptr( v1 )); + splitlist_node_type const * n2 = static_cast(native_node_traits::to_node_ptr( v2 )); if ( n1->m_nHash != n2->m_nHash ) return n1->m_nHash < n2->m_nHash ? -1 : 1; - if ( n1->is_dummy() ) { - assert( n2->is_dummy() ); + if ( n1->is_dummy()) { + assert( n2->is_dummy()); return 0; } - assert( !n1->is_dummy() && !n2->is_dummy() ); + assert( !n1->is_dummy() && !n2->is_dummy()); - return native_key_comparator()( v1, v2 ); + return native_key_comparator()(v1, v2); } template int operator()( value_type const& v, search_value_type const& q ) const { - splitlist_node_type const * n = static_cast( node_traits::to_node_ptr( v )); + splitlist_node_type const * n = static_cast(native_node_traits::to_node_ptr( v )); if ( n->m_nHash != q.nHash ) return n->m_nHash < q.nHash ? -1 : 1; - assert( !n->is_dummy() ); - return native_key_comparator()( v, q.val ); + assert( !n->is_dummy()); + return native_key_comparator()(v, q.val); } template @@ -710,17 +930,72 @@ namespace cds { namespace intrusive { { void operator()( value_type * v ) { - splitlist_node_type * p = static_cast( node_traits::to_node_ptr( v )); - if ( p->is_dummy() ) { - dummy_node_disposer()( p ); - } - else { - native_disposer()( v ); - } + splitlist_node_type * p = static_cast(native_node_traits::to_node_ptr( v )); + if ( !p->is_dummy()) + native_disposer()(v); } }; public: + typedef node_type ordered_list_node_type; + typedef splitlist_node_type aux_node; + + struct node_traits: private native_node_traits + { + typedef native_node_traits base_class; ///< Base ordered list node type + typedef typename base_class::value_type value_type; ///< Value type + typedef typename base_class::node_type base_node_type; ///< Ordered list node type + typedef node node_type; ///< Split-list node type + + /// Convert value reference to node pointer + static node_type * to_node_ptr( value_type& v ) + { + return static_cast(base_class::to_node_ptr( v )); + } + + /// Convert value pointer to node pointer + static node_type * to_node_ptr( value_type * v ) + { + return static_cast(base_class::to_node_ptr( v )); + } + + /// Convert value reference to node pointer (const version) + static node_type const * to_node_ptr( value_type const& v ) + { + return static_cast(base_class::to_node_ptr( v )); + } + + /// Convert value pointer to node pointer (const version) + static node_type const * to_node_ptr( value_type const * v ) + { + return static_cast(base_class::to_node_ptr( v )); + } + + /// Convert node reference to value pointer + static value_type * to_value_ptr( node_type& n ) + { + return base_class::to_value_ptr( static_cast(n)); + } + + /// Convert node pointer to value pointer + static value_type * to_value_ptr( node_type * n ) + { + return base_class::to_value_ptr( static_cast(n)); + } + + /// Convert node reference to value pointer (const version) + static const value_type * to_value_ptr( node_type const & n ) + { + return base_class::to_value_ptr( static_cast(n)); + } + + /// Convert node pointer to value pointer (const version) + static const value_type * to_value_ptr( node_type const * n ) + { + return base_class::to_value_ptr( static_cast(n)); + } + }; + template struct make_compare_from_less: public cds::opt::details::make_comparator_from_less { @@ -729,39 +1004,200 @@ namespace cds { namespace intrusive { template int operator()( value_type const& v, search_value_type const& q ) const { - splitlist_node_type const * n = static_cast( node_traits::to_node_ptr( v )); + splitlist_node_type const * n = static_cast(native_node_traits::to_node_ptr( v )); if ( n->m_nHash != q.nHash ) return n->m_nHash < q.nHash ? -1 : 1; - assert( !n->is_dummy() ); - return base_class()( v, q.val ); + assert( !n->is_dummy()); + return base_class()(v, q.val); } template int operator()( search_value_type const& q, value_type const& v ) const { - splitlist_node_type const * n = static_cast( node_traits::to_node_ptr( v )); + splitlist_node_type const * n = static_cast(native_node_traits::to_node_ptr( v )); if ( n->m_nHash != q.nHash ) return q.nHash < n->m_nHash ? -1 : 1; - assert( !n->is_dummy() ); - return base_class()( q.val, v ); + assert( !n->is_dummy()); + return base_class()(q.val, v); } - template - int operator()( Q1 const& v1, Q2 const& v2 ) const + int operator()( value_type const& lhs, value_type const& rhs ) const { - return base_class()( v1, v2 ); + splitlist_node_type const * n1 = static_cast(native_node_traits::to_node_ptr( lhs )); + splitlist_node_type const * n2 = static_cast(native_node_traits::to_node_ptr( rhs )); + if ( n1->m_nHash != n2->m_nHash ) + return n1->m_nHash < n2->m_nHash ? -1 : 1; + + if ( n1->is_dummy()) { + assert( n2->is_dummy()); + return 0; + } + + assert( !n1->is_dummy() && !n2->is_dummy()); + + return native_key_comparator()( lhs, rhs ); } }; typedef typename native_ordered_list::template rebind_traits< opt::compare< key_compare > - ,opt::disposer< wrapped_disposer > - ,opt::boundary_node_type< splitlist_node_type > - >::type result; + , opt::disposer< wrapped_disposer > + , opt::boundary_node_type< splitlist_node_type > + >::type result; }; + template + class ordered_list_adapter< OrderedList, Traits, true > + { + typedef OrderedList native_ordered_list; + typedef Traits traits; + + typedef typename native_ordered_list::gc gc; + typedef typename native_ordered_list::key_comparator native_key_comparator; + typedef typename native_ordered_list::value_type value_type; + typedef typename native_ordered_list::disposer native_disposer; + + struct key_compare { + int operator()( value_type const& v1, value_type const& v2 ) const + { + hash_node const& n1 = static_cast( v1 ); + hash_node const& n2 = static_cast( v2 ); + if ( n1.m_nHash != n2.m_nHash ) + return n1.m_nHash < n2.m_nHash ? -1 : 1; + + if ( n1.is_dummy()) { + assert( n2.is_dummy()); + return 0; + } + + assert( !n1.is_dummy() && !n2.is_dummy()); + + return native_key_comparator()(v1, v2); + } + + template + int operator()( value_type const& v, search_value_type const& q ) const + { + hash_node const& n = static_cast( v ); + if ( n.m_nHash != q.nHash ) + return n.m_nHash < q.nHash ? -1 : 1; + + assert( !n.is_dummy()); + return native_key_comparator()(v, q.val); + } + + template + int operator()( search_value_type const& q, value_type const& v ) const + { + return -operator()( v, q ); + } + }; + + struct wrapped_disposer + { + void operator()( value_type * v ) + { + if ( !static_cast( v )->is_dummy()) + native_disposer()( v ); + } + }; + + public: + typedef void ordered_list_node_type; + + struct aux_node: public native_ordered_list::node_type, public hash_node + { + aux_node() + { + typedef typename native_ordered_list::node_type list_node_type; + + list_node_type::data.store( typename list_node_type::marked_data_ptr( + static_cast( static_cast( this ))), + atomics::memory_order_release + ); + } + }; + + struct node_traits + { + static hash_node * to_node_ptr( value_type& v ) + { + return static_cast( &v ); + } + + static hash_node * to_node_ptr( value_type * v ) + { + return static_cast( v ); + } + + static hash_node const * to_node_ptr( value_type const& v ) + { + return static_cast( &v ); + } + + static hash_node const * to_node_ptr( value_type const * v ) + { + return static_cast( v ); + } + }; + + template + struct make_compare_from_less: public cds::opt::details::make_comparator_from_less + { + typedef cds::opt::details::make_comparator_from_less base_class; + + template + int operator()( value_type const& v, search_value_type const& q ) const + { + hash_node const& n = static_cast( v ); + if ( n.m_nHash != q.nHash ) + return n.m_nHash < q.nHash ? -1 : 1; + + assert( !n.is_dummy()); + return base_class()(v, q.val); + } + + template + int operator()( search_value_type const& q, value_type const& v ) const + { + hash_node const& n = static_cast( v ); + if ( n.m_nHash != q.nHash ) + return q.nHash < n.m_nHash ? -1 : 1; + + assert( !n.is_dummy()); + return base_class()(q.val, v); + } + + int operator()( value_type const& lhs, value_type const& rhs ) const + { + hash_node const& n1 = static_cast( lhs ); + hash_node const& n2 = static_cast( rhs ); + if ( n1.m_nHash != n2.m_nHash ) + return n1.m_nHash < n2.m_nHash ? -1 : 1; + + if ( n1.is_dummy()) { + assert( n2.is_dummy()); + return 0; + } + + assert( !n1.is_dummy() && !n2.is_dummy()); + + return base_class()( lhs, rhs ); + } + }; + + typedef typename native_ordered_list::template rebind_traits< + opt::compare< key_compare > + , opt::disposer< wrapped_disposer > + , opt::boundary_node_type< aux_node > + >::type result; + }; + + template + using rebind_list_traits = ordered_list_adapter< OrderedList, Traits, is_iterable_list::value >; + template struct select_list_iterator; @@ -810,11 +1246,10 @@ namespace cds { namespace intrusive { , m_itEnd( itEnd ) { // skip dummy nodes - while ( m_itCur != m_itEnd && node_traits::to_node_ptr( *m_itCur )->is_dummy() ) + while ( m_itCur != m_itEnd && node_traits::to_node_ptr( *m_itCur )->is_dummy()) ++m_itCur; } - value_ptr operator ->() const { return m_itCur.operator->(); @@ -831,7 +1266,7 @@ namespace cds { namespace intrusive { if ( m_itCur != m_itEnd ) { do { ++m_itCur; - } while ( m_itCur != m_itEnd && node_traits::to_node_ptr( *m_itCur )->is_dummy() ); + } while ( m_itCur != m_itEnd && node_traits::to_node_ptr( *m_itCur )->is_dummy()); } return *this; } @@ -853,27 +1288,28 @@ namespace cds { namespace intrusive { { return m_itCur != i.m_itCur; } + + protected: + list_iterator const& underlying_iterator() const + { + return m_itCur; + } }; } // namespace details //@endcond //@cond // Helper functions - - /// Reverses bit order in \p nHash - static inline size_t reverse_bits( size_t nHash ) - { - return bitop::RBO( nHash ); - } - + template static inline size_t regular_hash( size_t nHash ) { - return reverse_bits( nHash ) | size_t(1); + return static_cast( BitReversalAlgo()( cds::details::size_t_cast( nHash ))) | size_t(1); } + template static inline size_t dummy_hash( size_t nHash ) { - return reverse_bits( nHash ) & ~size_t(1); + return static_cast( BitReversalAlgo()( cds::details::size_t_cast( nHash ))) & ~size_t(1); } //@endcond