-//$$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_TREIBER_STACK_H
#define CDSLIB_INTRUSIVE_TREIBER_STACK_H
operation()
: pVal( nullptr )
- , nStatus(0)
+ , nStatus( 0 /*op_free*/ )
{}
};
//@endcond
/// Enable elimination back-off; by default, it is disabled
static CDS_CONSTEXPR const bool enable_elimination = false;
- /// Back-off strategy to wait for elimination, default is cds::backoff::delay<>
+ /// Back-off strategy to wait for elimination, default is \p cds::backoff::delay<>
typedef cds::backoff::delay<> elimination_backoff;
/// Buffer type for elimination array
/**
- Possible types are \p opt::v::static_buffer, \p opt::v::dynamic_buffer.
+ Possible types are \p opt::v::initialized_static_buffer, \p opt::v::initialized_dynamic_buffer.
The buffer can be any size: \p Exp2 template parameter of those classes can be \p false.
The size should be selected empirically for your application and hardware, there are no common rules for that.
- Default is <tt> %opt::v::static_buffer< any_type, 4 > </tt>.
+ Default is <tt> %opt::v::initialized_static_buffer< any_type, 4 > </tt>.
*/
- typedef opt::v::static_buffer< int, 4 > buffer;
+ typedef opt::v::initialized_static_buffer< int, 4 > buffer;
/// Random engine to generate a random position in elimination array
typedef opt::v::c_rand random_engine;
/// Metafunction converting option list to \p treiber_stack::traits
/**
Supported \p Options are:
- - opt::hook - hook used. Possible hooks are: \p treiber_stack::base_hook, \p treiber_stack::member_hook, \p treiber_stack::traits_hook.
+ - \p opt::hook - hook used. Possible hooks are: \p treiber_stack::base_hook, \p treiber_stack::member_hook, \p treiber_stack::traits_hook.
If the option is not specified, \p %treiber_stack::base_hook<> is used.
- - opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
- - opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer. This option is used only
+ - \p opt::back_off - back-off strategy used. If the option is not specified, the \p cds::backoff::Default is used.
+ - \p opt::disposer - the functor used for dispose removed items. Default is \p opt::v::empty_disposer. This option is used only
in \p TreiberStack::clear function.
- - opt::link_checker - the type of node's link fields checking. Default is \ref opt::debug_check_link.
- - opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
+ - \p opt::link_checker - the type of node's link fields checking. Default is \ref opt::debug_check_link.
+ - \p opt::memory_model - C++ memory ordering model. Can be \p opt::v::relaxed_ordering (relaxed memory model, the default)
or \p opt::v::sequential_consistent (sequentially consisnent memory model).
- - opt::item_counter - the type of item counting feature. Default is \p cds::atomicity::empty_item_counter, i.e.
+ - \p opt::item_counter - the type of item counting feature. Default is \p cds::atomicity::empty_item_counter, i.e.
no item counting. Use \p cds::atomicity::item_counter to enable item counting.
- - opt::stat - the type to gather internal statistics.
+ - \p opt::stat - the type to gather internal statistics.
Possible option value are: \p treiber_stack::stat, \p treiber_stack::empty_stat (the default),
user-provided class that supports \p treiber_stack::stat interface.
- - opt::enable_elimination - enable elimination back-off for the stack. Default value is \p false.
+ - \p opt::enable_elimination - enable elimination back-off for the stack. Default value is \p false.
If elimination back-off is enabled, additional options can be specified:
- - opt::buffer - a buffer type for elimination array, see \p opt::v::static_buffer, \p opt::v::dynamic_buffer.
+ - \p opt::buffer - a buffer type for elimination array, see \p opt::v::initialized_static_buffer, \p opt::v::initialized_dynamic_buffer.
The buffer can be any size: \p Exp2 template parameter of those classes can be \p false.
The size should be selected empirically for your application and hardware, there are no common rules for that.
- Default is <tt> %opt::v::static_buffer< any_type, 4 > </tt>.
- - opt::random_engine - a random engine to generate a random position in elimination array.
+ Default is <tt> %opt::v::initialized_static_buffer< any_type, 4 > </tt>.
+ - \p opt::random_engine - a random engine to generate a random position in elimination array.
Default is \p opt::v::c_rand.
- - opt::elimination_backoff - back-off strategy to wait for elimination, default is \p cds::backoff::delay<>
- - opt::lock_type - a lock type used in elimination back-off, default is \p cds::sync::spin
+ - \p opt::elimination_backoff - back-off strategy to wait for elimination, default is \p cds::backoff::delay<>
+ - \p opt::lock_type - a lock type used in elimination back-off, default is \p cds::sync::spin
Example: declare \p %TreiberStack with elimination enabled and internal statistics
\code
/// Elimination back-off data
struct elimination_data {
- elimination_random_engine randEngine; ///< random engine
- collision_array collisions; ///< collision array
+ mutable elimination_random_engine randEngine; ///< random engine
+ collision_array collisions; ///< collision array
elimination_data()
{
enum operation_status {
op_free = 0,
- op_busy = 1,
+ op_waiting = 1,
op_collided = 2
};
typedef std::unique_lock< elimination_lock_type > slot_scoped_lock;
+ template <bool Exp2 = collision_array::c_bExp2>
+ typename std::enable_if< Exp2, size_t >::type slot_index() const
+ {
+ return m_Elimination.randEngine() & (m_Elimination.collisions.capacity() - 1);
+ }
+
+ template <bool Exp2 = collision_array::c_bExp2>
+ typename std::enable_if< !Exp2, size_t >::type slot_index() const
+ {
+ return m_Elimination.randEngine() % m_Elimination.collisions.capacity();
+ }
+
public:
elimination_backoff()
{
bool backoff( operation_desc& op, Stat& stat )
{
elimination_backoff_type bkoff;
- op.nStatus.store( op_busy, atomics::memory_order_relaxed );
+ op.nStatus.store( op_waiting, atomics::memory_order_relaxed );
elimination_rec * myRec = cds::algo::elimination::init_record( op );
- collision_array_record& slot = m_Elimination.collisions[m_Elimination.randEngine() % m_Elimination.collisions.capacity()];
+ collision_array_record& slot = m_Elimination.collisions[ slot_index() ];
{
slot.lock.lock();
elimination_rec * himRec = slot.pRec;
operation_desc * himOp = static_cast<operation_desc *>( himRec->pOp );
assert( himOp );
if ( himOp->idOp != op.idOp ) {
+
if ( op.idOp == treiber_stack::op_push )
himOp->pVal = op.pVal;
else
op.pVal = himOp->pVal;
+
slot.pRec = nullptr;
+ himOp->nStatus.store( op_collided, atomics::memory_order_release );
slot.lock.unlock();
- himOp->nStatus.store( op_collided, atomics::memory_order_release );
cds::algo::elimination::clear_record();
stat.onActiveCollision( op.idOp );
return true;
}
- himOp->nStatus.store( op_free, atomics::memory_order_release );
+ //himOp->nStatus.store( op_free, atomics::memory_order_release );
}
slot.pRec = myRec;
slot.lock.unlock();
}
// Wait for colliding operation
- bkoff( [&op]() CDS_NOEXCEPT -> bool { return op.nStatus.load( atomics::memory_order_acquire ) != op_busy; } );
+ bkoff( [&op]() CDS_NOEXCEPT -> bool { return op.nStatus.load( atomics::memory_order_acquire ) != op_waiting; } );
+
{
slot_scoped_lock l( slot.lock );
if ( slot.pRec == myRec )
slot.pRec = nullptr;
}
- bool bCollided = op.nStatus.load( atomics::memory_order_acquire ) == op_collided;
+ bool bCollided = op.nStatus.load( atomics::memory_order_relaxed ) == op_collided;
if ( !bCollided )
stat.onEliminationFailed();
@note Hendler's et al paper describes a lock-free implementation of elimination back-off which is quite complex.
The main difficulty is the managing life-time of elimination record.
- Our implementation uses simplified lock-based (spin-based) approach which allows
+ This implementation uses simplified lock-based (spin-based) approach which allows
the elimination record allocation on thread's stack.
This approach demonstrates sufficient performance under high load.
typedef typename traits::stat stat; ///< Internal statistics
typedef typename traits::back_off back_off; ///< back-off strategy
+ /// How many Hazard pointers is required for Treiber's stack implementation
+ static CDS_CONSTEXPR size_t const c_nHazardPtrCount = 1;
+
public: // related to elimination back-off
/// Elimination back-off is enabled or not
typedef treiber_stack::details::elimination_backoff<enable_elimination, value_type, traits> elimination_backoff;
elimination_backoff m_Backoff;
- typedef intrusive::node_to_value<TreiberStack> node_to_value;
typedef treiber_stack::operation< value_type > operation_desc;
// GC and node_type::gc must be the same
/// Constructs empty stack and initializes elimination back-off data
/**
This form should be used if you use elimination back-off with dynamically allocated collision array, i.e
- \p Options... contains cds::opt::buffer< cds::opt::v::dynamic_buffer >.
+ \p Traits contains <tt>typedef cds::opt::v::initialized_dynamic_buffer buffer</tt>.
\p nCollisionCapacity parameter specifies the capacity of collision array.
*/
TreiberStack( size_t nCollisionCapacity )
op.pVal = &val;
}
- node_type * t = m_Top.load(memory_model::memory_order_relaxed);
+ node_type * t = m_Top.load( memory_model::memory_order_relaxed );
while ( true ) {
pNew->m_pNext.store( t, memory_model::memory_order_relaxed );
- if ( m_Top.compare_exchange_weak( t, pNew, memory_model::memory_order_release, atomics::memory_order_relaxed )) {
+ if ( m_Top.compare_exchange_weak( t, pNew, memory_model::memory_order_release, atomics::memory_order_acquire )) {
++m_ItemCounter;
m_stat.onPush();
return true;
}
while ( true ) {
- node_type * t = guard.protect( m_Top, node_to_value() );
+ node_type * t = guard.protect( m_Top,
+ []( node_type * p ) -> value_type * {
+ return node_traits::to_value_ptr( p );
+ });
if ( t == nullptr )
return nullptr; // stack is empty
pTop = m_Top.load( memory_model::memory_order_relaxed );
if ( pTop == nullptr )
return;
- if ( m_Top.compare_exchange_weak( pTop, nullptr, memory_model::memory_order_acquire, atomics::memory_order_relaxed ) ) {
+ if ( m_Top.compare_exchange_weak( pTop, nullptr, memory_model::memory_order_acquire, atomics::memory_order_relaxed )) {
m_ItemCounter.reset();
break;
}
node_type * p = pTop;
pTop = p->m_pNext.load(memory_model::memory_order_relaxed);
clear_links( p );
- gc::template retire<disposer>( node_traits::to_value_ptr( *p ) );
+ gc::template retire<disposer>( node_traits::to_value_ptr( *p ));
}
}
projects / libcds.git / blobdiff