changed travis script
[libcds.git] / cds / urcu / details / base.h
index 8aa281072d38ca38015d9ee0d030f21f5d7cf518..599bb2b13a96037eec944cae142c21c5cea54a5f 100644 (file)
@@ -1,7 +1,35 @@
-//$$CDS-header$$
+/*
+    This file is a part of libcds - Concurrent Data Structures library
 
-#ifndef _CDS_URCU_DETAILS_BASE_H
-#define _CDS_URCU_DETAILS_BASE_H
+    (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_URCU_DETAILS_BASE_H
+#define CDSLIB_URCU_DETAILS_BASE_H
 
 #include <cds/algo/atomic.h>
 #include <cds/gc/details/retired_ptr.h>
@@ -23,6 +51,8 @@ namespace cds {
           Chapter 6 "User-Level Implementations of Read-Copy Update"
         - [2011] M.Desnoyers, P.McKenney, A.Stern, M.Dagenias, J.Walpole "User-Level
           Implementations of Read-Copy Update"
+        - [2012] M.Desnoyers, P.McKenney, A.Stern, M.Dagenias, J.Walpole "Supplementary
+          Material for User-Level Implementations of Read-Copy Update"
 
         <b>Informal introduction to user-space %RCU</b>
 
@@ -75,26 +105,23 @@ namespace cds {
           the best possible read-side performance, but requires that each thread periodically
           calls a function to announce that it is in a quiescent state, thus strongly
           constraining the application design. This type of %RCU is not implemented in \p libcds.
-        - The general-purpose %RCU implementation places almost no constraints on the application\92s
+        - The general-purpose %RCU implementation places almost no constraints on the application's
           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
+        - \p 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.
@@ -102,8 +129,8 @@ namespace cds {
         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,
@@ -112,37 +139,33 @@ namespace cds {
             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.
@@ -151,11 +174,6 @@ namespace cds {
         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.
 
@@ -203,7 +221,7 @@ namespace cds {
     */
     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
 
@@ -246,15 +264,11 @@ namespace cds {
         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
         typedef cds::gc::details::retired_ptr   retired_ptr;
+        using cds::gc::make_retired_ptr;
 
         /// Pointer to function to free (destruct and deallocate) retired pointer of specific type
         typedef cds::gc::details::free_retired_ptr_func free_retired_ptr_func;
@@ -291,14 +305,19 @@ namespace cds {
             //@cond
             template <typename ThreadData>
             struct thread_list_record {
-                ThreadData *    m_pNext ;  ///< Next item in thread list
-                atomics::atomic<OS::ThreadId>    m_idOwner   ; ///< Owner thread id; 0 - the record is free (not owned)
+                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_pNext( nullptr )
                     , m_idOwner( cds::OS::c_NullThreadId )
                 {}
 
+                explicit thread_list_record( OS::ThreadId owner )
+                    : m_pNext( nullptr )
+                    , m_idOwner( owner )
+                {}
+
                 ~thread_list_record()
                 {}
             };
@@ -308,11 +327,11 @@ namespace cds {
             template <typename RCUtag, class Alloc = CDS_DEFAULT_ALLOCATOR >
             class thread_list {
             public:
-                typedef thread_data<RCUtag>         thread_record;
-                typedef cds::details::Allocator< thread_record, Alloc >   allocator_type;
+                typedef thread_data<RCUtag>                             thread_record;
+                typedef cds::details::Allocator< thread_record, Alloc > allocator_type;
 
             private:
-                atomics::atomic<thread_record *>   m_pHead;
+                atomics::atomic<thread_record *> m_pHead;
 
             public:
                 thread_list()
@@ -330,25 +349,25 @@ namespace cds {
                     cds::OS::ThreadId const nullThreadId = cds::OS::c_NullThreadId;
                     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 ) {
+                    // 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.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 );
-
-                    atomics::atomic_thread_fence( atomics::memory_order_release );
+                    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;
                 }
@@ -364,9 +383,9 @@ namespace cds {
                     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 );
                         }
                     }
@@ -384,13 +403,12 @@ namespace cds {
                     CDS_DEBUG_ONLY( cds::OS::ThreadId const nullThreadId = cds::OS::c_NullThreadId; )
                     CDS_DEBUG_ONLY( cds::OS::ThreadId const mainThreadId = cds::OS::get_current_thread_id() ;)
 
-                    thread_record * p = m_pHead.exchange( nullptr, atomics::memory_order_seq_cst );
+                    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 );
@@ -407,19 +425,15 @@ namespace cds {
                 typedef ThreadGC                    thread_gc;
                 typedef typename thread_gc::rcu_tag rcu_tag;
 
-                bool m_bLocked;
             public:
-                scoped_lock(bool bLock = true)
-                    : m_bLocked( bLock )
+                scoped_lock()
                 {
-                    if ( bLock )
-                        thread_gc::access_lock();
+                    thread_gc::access_lock();
                 }
 
                 ~scoped_lock()
                 {
-                    if ( m_bLocked )
-                        thread_gc::access_unlock();
+                    thread_gc::access_unlock();
                 }
             };
             //@endcond
@@ -438,7 +452,7 @@ namespace cds {
         */
         struct epoch_retired_ptr: public retired_ptr
         {
-            uint64_t    m_nEpoch ;  ///< The epoch when the object has been retired
+            uint64_t    m_nEpoch;  ///< The epoch when the object has been retired
 
             //@cond
             epoch_retired_ptr()
@@ -455,4 +469,4 @@ namespace cds {
     } // namespace urcu
 } // namespace cds
 
-#endif // #ifndef _CDS_URCU_DETAILS_BASE_H
+#endif // #ifndef CDSLIB_URCU_DETAILS_BASE_H