/*
This file is a part of libcds - Concurrent Data Structures library
- (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
+ (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:
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.
+ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#ifndef CDSLIB_URCU_DETAILS_BASE_H
design, thus being appropriate for use within a general-purpose library, but it has
relatively higher read-side overhead. The \p libcds contains several implementations of general-purpose
%RCU: \ref general_instant, \ref general_buffered, \ref general_threaded.
- - The signal-handling %RCU presents an implementation having low read-side overhead and
+ - \ref signal_buffered: the signal-handling %RCU presents an implementation having low read-side overhead and
requiring only that the application give up one POSIX signal to %RCU update processing.
- The \p libcds contains several implementations if signal-handling %RCU: \ref signal_buffered,
- \ref signal_threaded.
- @note The signal-handled %RCU is defined only for UNIX-like systems, not for Windows.
+ @note The signal-handled %RCU is defined only for UNIX-like systems, not for Windows.
- @anchor cds_urcu_type
- <b>RCU implementation type</b>
+ @anchor cds_urcu_type
+ <b>RCU implementation type</b>
There are several internal implementation of RCU (all declared in \p %cds::urcu namespace):
- \ref general_instant - general purpose RCU with immediate reclamation
- \ref general_buffered - general purpose RCU with deferred (buffered) reclamation
- \ref general_threaded - general purpose RCU with special reclamation thread
- \ref signal_buffered - signal-handling RCU with deferred (buffered) reclamation
- - \ref signal_threaded - signal-handling RCU with special reclamation thread
You cannot create an object of any of those classes directly.
Instead, you should use wrapper classes.
and has the reacher interface that combines interfaces of wrapped class i.e. RCU global part like
\p synchronize, and corresponding RCU thread-specific interface like \p access_lock, \p access_unlock and \p retire_ptr.
- @anchor cds_urcu_gc
- There are several wrapper classes (all declared in \p %cds::urcu namespace)
+ @anchor cds_urcu_gc
+ There are several wrapper classes (all declared in \p %cds::urcu namespace)
- \ref cds_urcu_general_instant_gc "gc<general_instant>" - general purpose RCU with immediate reclamation,
include file <tt><cds/urcu/general_instant.h></tt>
- \ref cds_urcu_general_buffered_gc "gc<general_buffered>" - general purpose RCU with deferred (buffered) reclamation,
include file <tt><cds/urcu/general_threaded.h></tt>
- \ref cds_urcu_signal_buffered_gc "gc<signal_buffered>" - signal-handling RCU with deferred (buffered) reclamation
include file <tt><cds/urcu/signal_buffered.h></tt>
- - \ref cds_urcu_signal_threaded_gc "gc<signal_threaded>" - signal-handling RCU with special reclamation thread
- include file <tt><cds/urcu/signal_threaded.h></tt>
Any RCU-related container in \p libcds expects that its \p RCU template parameter is one of those wrapper.
- @anchor cds_urcu_tags
+ @anchor cds_urcu_tags
For simplicity, in some algorithms instead of using RCU implementation type
you should specify corresponding RCU tags (all declared in \p %cds::urcu namespace):
- \ref general_instant_tag - for \ref general_instant
- \ref general_buffered_tag - for \ref general_buffered
- \ref general_threaded_tag - for \ref general_threaded
- \ref signal_buffered_tag - for \ref signal_buffered
- - \ref signal_threaded_tag - for \ref signal_threaded
- @anchor cds_urcu_performance
- <b>Performance</b>
+ @anchor cds_urcu_performance
+ <b>Performance</b>
As a result of our experiments we can range above %RCU implementation in such order,
from high to low performance:
- <tt>gc<general_buffered></tt> - high
- <tt>gc<general_threaded></tt>
- <tt>gc<signal_buffered></tt>
- - <tt>gc<signal_threaded></tt>
- <tt>gc<general_instant></tt> - low
This estimation is very rough and depends on many factors:
type of payload - mostly read-only (seeking) or read-write (inserting and deleting), -
a hardware, your application, and so on.
- @anchor cds_urcu_howto
- <b>How to use</b>
+ @anchor cds_urcu_howto
+ <b>How to use</b>
Usually, in your application you use only one \ref cds_urcu_gc "type of RCU" that is the best for your needs.
However, the library allows to apply several RCU singleton in one application.
with different template arguments is an error and is not supported.
However, it is correct when your RCU objects relates to different RCU types.
- @note If you want to use \p %signal_buffered and \p %signal_threaded RCU in your application simultaneously,
- you should specify different signal number for each signal-handled RCU type on construction time,
- for example, \p SIGUSR1 and \p SIGUSR2 respectively. By default, both signal-handled RCU implementation
- share \p SIGUSR1 signal and cannot be applied together.
-
In \p libcds, many GC-based ordered list, set and map template classes have %RCU-related specializations
that hide the %RCU specific details.
*/
namespace urcu {
-# if CDS_OS_INTERFACE == CDS_OSI_UNIX || defined(CDS_DOXYGEN_INVOKED)
+# if (CDS_OS_INTERFACE == CDS_OSI_UNIX || defined(CDS_DOXYGEN_INVOKED)) && !defined(CDS_THREAD_SANITIZER_ENABLED)
# define CDS_URCU_SIGNAL_HANDLING_ENABLED 1
# endif
struct signal_buffered_tag: public signal_handling_rcu {
typedef signal_handling_rcu rcu_class ; ///< The URCU type
};
-
- /// Tag for signal_threaded URCU
- struct signal_threaded_tag: public signal_handling_rcu {
- typedef signal_handling_rcu rcu_class ; ///< The URCU type
- };
# endif
///@anchor cds_urcu_retired_ptr Retired pointer, i.e. pointer that ready for reclamation
//@cond
template <typename ThreadData>
struct thread_list_record {
- ThreadData * m_pNext; ///< Next item in thread list
+ atomics::atomic<ThreadData*> m_pNext; ///< Next item in thread list
atomics::atomic<OS::ThreadId> m_idOwner; ///< Owner thread id; 0 - the record is free (not owned)
thread_list_record()
, m_idOwner( cds::OS::c_NullThreadId )
{}
+ explicit thread_list_record( OS::ThreadId owner )
+ : m_pNext( nullptr )
+ , m_idOwner( owner )
+ {}
+
~thread_list_record()
{}
};
cds::OS::ThreadId const curThreadId = cds::OS::get_current_thread_id();
// First, try to reuse a retired (non-active) HP record
- for ( pRec = m_pHead.load( atomics::memory_order_acquire ); pRec; pRec = pRec->m_list.m_pNext ) {
+ for ( pRec = m_pHead.load( atomics::memory_order_acquire ); pRec; pRec = pRec->m_list.m_pNext.load( atomics::memory_order_relaxed )) {
cds::OS::ThreadId thId = nullThreadId;
- if ( !pRec->m_list.m_idOwner.compare_exchange_strong( thId, curThreadId, atomics::memory_order_seq_cst, atomics::memory_order_relaxed ) )
+ if ( !pRec->m_list.m_idOwner.compare_exchange_strong( thId, curThreadId, atomics::memory_order_seq_cst, atomics::memory_order_relaxed ))
continue;
return pRec;
}
// No records available for reuse
// Allocate and push a new record
- pRec = allocator_type().New();
- pRec->m_list.m_idOwner.store( curThreadId, atomics::memory_order_relaxed );
+ pRec = allocator_type().New( curThreadId );
thread_record * pOldHead = m_pHead.load( atomics::memory_order_acquire );
do {
- pRec->m_list.m_pNext = pOldHead;
- } while ( !m_pHead.compare_exchange_weak( pOldHead, pRec, atomics::memory_order_release, atomics::memory_order_relaxed ));
+ // Compiler barriers: assignment MUST BE inside the loop
+ CDS_COMPILER_RW_BARRIER;
+ pRec->m_list.m_pNext.store( pOldHead, atomics::memory_order_relaxed );
+ CDS_COMPILER_RW_BARRIER;
+ } while ( !m_pHead.compare_exchange_weak( pOldHead, pRec, atomics::memory_order_acq_rel, atomics::memory_order_acquire ));
return pRec;
}
thread_record * pNext = nullptr;
cds::OS::ThreadId const nullThreadId = cds::OS::c_NullThreadId;
- for ( thread_record * pRec = m_pHead.load(atomics::memory_order_acquire); pRec; pRec = pNext ) {
- pNext = pRec->m_list.m_pNext;
- if ( pRec->m_list.m_idOwner.load(atomics::memory_order_relaxed) != nullThreadId ) {
+ for ( thread_record * pRec = m_pHead.load( atomics::memory_order_acquire ); pRec; pRec = pNext ) {
+ pNext = pRec->m_list.m_pNext.load( atomics::memory_order_relaxed );
+ if ( pRec->m_list.m_idOwner.load( atomics::memory_order_relaxed ) != nullThreadId ) {
retire( pRec );
}
}
thread_record * p = m_pHead.exchange( nullptr, atomics::memory_order_acquire );
while ( p ) {
- thread_record * pNext = p->m_list.m_pNext;
+ thread_record * pNext = p->m_list.m_pNext.load( atomics::memory_order_relaxed );
assert( p->m_list.m_idOwner.load( atomics::memory_order_relaxed ) == nullThreadId
|| p->m_list.m_idOwner.load( atomics::memory_order_relaxed ) == mainThreadId
- || !cds::OS::is_thread_alive( p->m_list.m_idOwner.load( atomics::memory_order_relaxed ) )
);
al.Delete( p );
projects / libcds.git / blobdiff