X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=gdax-orderbook-hpp%2Fdemo%2Fdependencies%2Flibcds-2.3.2%2Fcds%2Furcu%2Fdetails%2Fbase.h;fp=gdax-orderbook-hpp%2Fdemo%2Fdependencies%2Flibcds-2.3.2%2Fcds%2Furcu%2Fdetails%2Fbase.h;h=599bb2b13a96037eec944cae142c21c5cea54a5f;hb=4223430d9168223029c7639149025c79e69b4f37;hp=0000000000000000000000000000000000000000;hpb=7ea7751a31c0388bf888052517be181a2989b113;p=c11concurrency-benchmarks.git diff --git a/gdax-orderbook-hpp/demo/dependencies/libcds-2.3.2/cds/urcu/details/base.h b/gdax-orderbook-hpp/demo/dependencies/libcds-2.3.2/cds/urcu/details/base.h new file mode 100644 index 0000000..599bb2b --- /dev/null +++ b/gdax-orderbook-hpp/demo/dependencies/libcds-2.3.2/cds/urcu/details/base.h @@ -0,0 +1,472 @@ +/* + 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_URCU_DETAILS_BASE_H +#define CDSLIB_URCU_DETAILS_BASE_H + +#include +#include +#include +#include +#include + +namespace cds { + /// User-space Read-Copy Update (URCU) namespace + /** @ingroup cds_garbage_collector + @anchor cds_urcu_desc + + This namespace contains declarations for different types of Read-Copy Update (%RCU) + synchronization primitive and data structures developed for RCU. + In libcds %RCU is used as garbage collector. + + Source papers: + - [2009] M.Desnoyers "Low-Impact Operating System Tracing" PhD Thesis, + 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" + + Informal introduction to user-space %RCU + + [From Desnoyer's papers] %RCU is a synchronization mechanism that was added to the + Linux kernel in October of 2002. %RCU achieves scalability improvements by allowing + reads to occur concurrently with updates. In contrast to conventional locking + primitives that ensure mutual exclusion among concurrent threads regardless of whether + they be readers or updaters, or with reader-writer locks that allow concurrent reads + but not in the presence of updates, %RCU supports concurrency between multiple updaters + and multiple readers. %RCU ensures that data are not freed up until all pre-existing + critical sections complete. %RCU defines and uses efficient and scalable mechanisms + for deferring reclamation of old data. These mechanisms distribute the work among read and update + paths in such a way as to make read paths extremely fast. + + %RCU readers execute within %RCU read-side critical sections. Each such critical section begins with + \p rcu_read_lock(), ends with \p rcu_read_unlock() (in \p libcds these primitives are the methods of + GC class and are usually called \p access_lock and \p access_unlock respectively). Read-side + critical sections can be nested. + The performance benefits of %RCU are due to the fact that \p rcu_read_lock() + and \p rcu_read_unlock() are exceedingly fast. + + When a thread is not in an %RCU read-side critical section, it is in a quiescent state. + A quiescent state that persists for a significant time period is an extended quiescent state. + Any time period during which every thread has been in at least one quiescent state + is a grace period; this implies that every %RCU read-side critical section + that starts before a grace period must end before that grace period does. + Distinct grace periods may overlap, either partially or completely. Any time period + that includes a grace period is by definition itself a grace period. + Each grace period is guaranteed to complete as long as all read-side critical sections + are finite in duration; thus even a constant flow of such critical sections is unable to + extend an %RCU grace period indefinitely. + + Suppose that readers enclose each of their data-structure traversals in + an %RCU read-side critical section. If an updater first removes an element + from such a data structure and then waits for a grace period, there can be + no more readers accessing that element. The updater can then carry out destructive + operations, for example freeing the element, without disturbing any readers. + + The %RCU update is split into two phases, a removal phase and a reclamation phase. + These two phases must be separated by a grace period, for example via the \p synchronize_rcu() + primitive, which initiates a grace period and waits for it to finish. + During the removal phase, the %RCU update removes elements from a shared data structure. + The removed data elements will only be accessible to read-side critical sections + that ran concurrently with the removal phase, which are guaranteed to complete before the + grace period ends. Therefore the reclamation phase can safely free the data elements + removed by the removal phase. + + Desnoyers describes several classes of user-space %RCU implementations: + - The Quiescent-State-Based Reclamation (QSBR) %RCU implementation offers + 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'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. + - \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. + + @note The signal-handled %RCU is defined only for UNIX-like systems, not for Windows. + + @anchor cds_urcu_type + RCU implementation type + + 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 + + You cannot create an object of any of those classes directly. + Instead, you should use wrapper classes. + The wrapper simplifies creation and usage of RCU singleton objects + 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) + - \ref cds_urcu_general_instant_gc "gc" - general purpose RCU with immediate reclamation, + include file + - \ref cds_urcu_general_buffered_gc "gc" - general purpose RCU with deferred (buffered) reclamation, + include file + - \ref cds_urcu_general_threaded_gc "gc" - general purpose RCU with special reclamation thread + include file + - \ref cds_urcu_signal_buffered_gc "gc" - signal-handling RCU with deferred (buffered) reclamation + include file + + Any RCU-related container in \p libcds expects that its \p RCU template parameter is one of those wrapper. + + @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 + + @anchor cds_urcu_performance + Performance + + As a result of our experiments we can range above %RCU implementation in such order, + from high to low performance: + - gc - high + - gc + - gc + - gc - 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 + How to use + + 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. + The only limitation is that only one object of each RCU type can be instantiated. + Since each RCU type is a template class the creation of two object of one RCU type class + with different template arguments is an error and is not supported. + However, it is correct when your RCU objects relates to different RCU types. + + In \p libcds, many GC-based ordered list, set and map template classes have %RCU-related specializations + that hide the %RCU specific details. + + RCU GC is initialized in usual way: you should declare an object of type \p cds::urcu::gc< RCU_type >, + for example: + \code + #include + + typedef cds::urcu::gc< cds::urcu::general_buffered<> > rcu_gpb; + + int main() { + // Initialize libcds + cds::Initialize(); + { + // Initialize general_buffered RCU + rcu_gpb gpbRCU; + + // If main thread uses lock-free containers + // the main thread should be attached to libcds infrastructure + cds::threading::Manager::attachThread(); + + // Now you can use RCU-based containers in the main thread + //... + } + // Terminate libcds + cds::Terminate(); + } + \endcode + + Each thread that deals with RCU-based container should be initialized first: + \code + #include + int myThreadEntryPoint(void *) + { + // Attach the thread to libcds infrastructure + cds::threading::Manager::attachThread(); + + // Now you can use RCU-based containers in the thread + //... + + // Detach thread when terminating + cds::threading::Manager::detachThread(); + } + \endcode + */ + namespace urcu { + +# if (CDS_OS_INTERFACE == CDS_OSI_UNIX || defined(CDS_DOXYGEN_INVOKED)) && !defined(CDS_THREAD_SANITIZER_ENABLED) +# define CDS_URCU_SIGNAL_HANDLING_ENABLED 1 +# endif + + /// General-purpose URCU type + struct general_purpose_rcu { + //@cond + static uint32_t const c_nControlBit = 0x80000000; + static uint32_t const c_nNestMask = c_nControlBit - 1; + //@endcond + }; + +# ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED + /// Signal-handling URCU type + struct signal_handling_rcu { + //@cond + static uint32_t const c_nControlBit = 0x80000000; + static uint32_t const c_nNestMask = c_nControlBit - 1; + //@endcond + }; +# endif + + /// Tag for general_instant URCU + struct general_instant_tag: public general_purpose_rcu { + typedef general_purpose_rcu rcu_class ; ///< The URCU type + }; + + /// Tag for general_buffered URCU + struct general_buffered_tag: public general_purpose_rcu + { + typedef general_purpose_rcu rcu_class ; ///< The URCU type + }; + + /// Tag for general_threaded URCU + struct general_threaded_tag: public general_purpose_rcu { + typedef general_purpose_rcu rcu_class ; ///< The URCU type + }; + +# ifdef CDS_URCU_SIGNAL_HANDLING_ENABLED + /// Tag for signal_buffered URCU + struct signal_buffered_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; + + //@cond + /// Implementation-specific URCU details + namespace details { + /// forward declarations + template + struct thread_data; + + template + class thread_gc; + + template + class singleton; + + //@cond + class singleton_vtbl { + protected: + virtual ~singleton_vtbl() + {} + public: + virtual void retire_ptr( retired_ptr& p ) = 0; + }; + + class gc_common + { + public: + template using atomic_marked_ptr = atomics::atomic; + }; + //@endcond + + //@cond + template + struct thread_list_record { + atomics::atomic m_pNext; ///< Next item in thread list + atomics::atomic 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() + {} + }; + //@endcond + + //@cond + template + class thread_list { + public: + typedef thread_data thread_record; + typedef cds::details::Allocator< thread_record, Alloc > allocator_type; + + private: + atomics::atomic m_pHead; + + public: + thread_list() + : m_pHead( nullptr ) + {} + + ~thread_list() + { + destroy(); + } + + thread_record * alloc() + { + thread_record * pRec; + 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.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 )) + continue; + return pRec; + } + + // No records available for reuse + // Allocate and push a new record + pRec = allocator_type().New( curThreadId ); + + thread_record * pOldHead = m_pHead.load( atomics::memory_order_acquire ); + do { + // 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; + } + + void retire( thread_record * pRec ) + { + assert( pRec != nullptr ); + pRec->m_list.m_idOwner.store( cds::OS::c_NullThreadId, atomics::memory_order_release ); + } + + void detach_all() + { + 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.load( atomics::memory_order_relaxed ); + if ( pRec->m_list.m_idOwner.load( atomics::memory_order_relaxed ) != nullThreadId ) { + retire( pRec ); + } + } + } + + thread_record * head( atomics::memory_order mo ) const + { + return m_pHead.load( mo ); + } + + private: + void destroy() + { + allocator_type al; + 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_acquire ); + while ( p ) { + 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 + ); + + al.Delete( p ); + p = pNext; + } + } + }; + //@endcond + + //@cond + template + class scoped_lock { + public: + typedef ThreadGC thread_gc; + typedef typename thread_gc::rcu_tag rcu_tag; + + public: + scoped_lock() + { + thread_gc::access_lock(); + } + + ~scoped_lock() + { + thread_gc::access_unlock(); + } + }; + //@endcond + } // namespace details + //@endcond + + // forwards + //@cond + template class gc; + //@endcond + + /// Epoch-based retired ptr + /** + Retired pointer with additional epoch field that prevents early reclamation. + This type of retired pointer is used in buffered RCU implementations. + */ + struct epoch_retired_ptr: public retired_ptr + { + uint64_t m_nEpoch; ///< The epoch when the object has been retired + + //@cond + epoch_retired_ptr() + {} + //@endcond + + /// Constructor creates a copy of \p rp retired pointer and saves \p nEpoch reclamation epoch. + epoch_retired_ptr( retired_ptr const& rp, uint64_t nEpoch ) + : retired_ptr( rp ) + , m_nEpoch( nEpoch ) + {} + }; + + } // namespace urcu +} // namespace cds + +#endif // #ifndef CDSLIB_URCU_DETAILS_BASE_H