2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31 #ifndef CDSLIB_URCU_DETAILS_GPT_H
32 #define CDSLIB_URCU_DETAILS_GPT_H
34 #include <mutex> //unique_lock
36 #include <cds/urcu/details/gp.h>
37 #include <cds/urcu/dispose_thread.h>
38 #include <cds/algo/backoff_strategy.h>
39 #include <cds/container/vyukov_mpmc_cycle_queue.h>
41 namespace cds { namespace urcu {
43 /// User-space general-purpose RCU with deferred threaded reclamation
45 @headerfile cds/urcu/general_threaded.h
47 This implementation is similar to \ref general_buffered but separate thread is created
48 for deleting the retired objects. Like \p %general_buffered, the class contains an internal buffer
49 where retired objects are accumulated. When the buffer becomes full,
50 the RCU \p synchronize() function is called that waits until all reader/updater threads end up their read-side critical sections,
51 i.e. until the RCU quiescent state will come. After that the "work ready" message is sent to reclamation thread.
52 The reclamation thread frees the buffer.
53 This synchronization cycle may be called in any thread that calls \p retire_ptr() function.
55 There is a wrapper \ref cds_urcu_general_threaded_gc "gc<general_threaded>" for \p %general_threaded class
56 that provides unified RCU interface. You should use this wrapper class instead \p %general_threaded
58 The \p Buffer contains items of \ref cds_urcu_retired_ptr "epoch_retired_ptr" type
60 and it should support a multiple producer/single consumer queue with the following interface:
61 - <tt> bool push( epoch_retired_ptr& p ) </tt> - places the retired pointer \p p into queue. If the function
62 returns \p false it means that the buffer is full and RCU synchronization cycle must be processed.
63 - <tt>epoch_retired_ptr * front() </tt> - returns a pointer to the top element or \p nullptr if the buffer is empty.
64 - <tt>bool pop_front() </tt> - pops the top element; returns \p false if the buffer is empty.
65 - <tt>size_t size()</tt> - returns queue's item count.
67 The buffer is considered as full if \p push() returns \p false or the buffer size reaches the RCU threshold.
70 - \p Buffer - MPSC (muliple producer/single consumer) buffer type with FIFO semantics.
72 Default is \p cds::container::VyukovMPSCCycleQueue. The buffer contains the objects of \ref epoch_retired_ptr
73 type that contains additional \p m_nEpoch field. This field specifies an epoch when the object
74 has been placed into the buffer. The \p %general_threaded object has a global epoch counter
75 that is incremented on each \p synchronize() call. The epoch is used internally to prevent early deletion.
76 - \p Lock - mutex type, default is \p std::mutex
77 - \p DisposerThread - the reclamation thread class. Default is \ref cds::urcu::dispose_thread,
78 see the description of this class for required interface.
79 - \p Backoff - back-off schema, default is cds::backoff::Default
82 class Buffer = cds::container::VyukovMPSCCycleQueue< epoch_retired_ptr >
83 ,class Lock = std::mutex
84 ,class DisposerThread = dispose_thread<Buffer>
85 ,class Backoff = cds::backoff::Default
87 class general_threaded: public details::gp_singleton< general_threaded_tag >
90 typedef details::gp_singleton< general_threaded_tag > base_class;
93 typedef Buffer buffer_type ; ///< Buffer type
94 typedef Lock lock_type ; ///< Lock type
95 typedef Backoff back_off ; ///< Back-off scheme
96 typedef DisposerThread disposer_thread ; ///< Disposer thread type
98 typedef general_threaded_tag rcu_tag ; ///< Thread-side RCU part
99 typedef base_class::thread_gc thread_gc ; ///< Access lock class
100 typedef typename thread_gc::scoped_lock scoped_lock ; ///< Access lock class
103 static bool const c_bBuffered = true ; ///< Bufferized RCU
108 typedef details::gp_singleton_instance< rcu_tag > singleton_ptr;
110 struct scoped_disposer {
111 void operator ()( general_threaded * p )
120 buffer_type m_Buffer;
121 atomics::atomic<uint64_t> m_nCurEpoch;
123 size_t const m_nCapacity;
124 disposer_thread m_DisposerThread;
128 /// Returns singleton instance
129 static general_threaded * instance()
131 return static_cast<general_threaded *>( base_class::instance());
133 /// Checks if the singleton is created and ready to use
136 return singleton_ptr::s_pRCU != nullptr;
141 general_threaded( size_t nBufferCapacity )
142 : m_Buffer( nBufferCapacity )
144 , m_nCapacity( nBufferCapacity )
150 base_class::flip_and_wait( bkoff );
153 // Return: true - synchronize has been called, false - otherwise
154 bool push_buffer( epoch_retired_ptr&& p )
156 bool bPushed = m_Buffer.push( p );
157 if ( !bPushed || m_Buffer.size() >= capacity()) {
174 /// Creates singleton object and starts reclamation thread
176 The \p nBufferCapacity parameter defines RCU threshold.
178 static void Construct( size_t nBufferCapacity = 256 )
180 if ( !singleton_ptr::s_pRCU ) {
181 std::unique_ptr< general_threaded, scoped_disposer > pRCU( new general_threaded( nBufferCapacity ));
182 pRCU->m_DisposerThread.start();
184 singleton_ptr::s_pRCU = pRCU.release();
188 /// Destroys singleton object and terminates internal reclamation thread
189 static void Destruct( bool bDetachAll = false )
192 general_threaded * pThis = instance();
194 pThis->m_ThreadList.detach_all();
196 pThis->m_DisposerThread.stop( pThis->m_Buffer, std::numeric_limits< uint64_t >::max());
199 singleton_ptr::s_pRCU = nullptr;
204 /// Retires \p p pointer
206 The method pushes \p p pointer to internal buffer.
207 When the buffer becomes full \ref synchronize function is called
208 to wait for the end of grace period and then
209 a message is sent to the reclamation thread.
211 virtual void retire_ptr( retired_ptr& p ) override
214 push_buffer( epoch_retired_ptr( p, m_nCurEpoch.load( atomics::memory_order_acquire )));
217 /// Retires the pointer chain [\p itFirst, \p itLast)
218 template <typename ForwardIterator>
219 void batch_retire( ForwardIterator itFirst, ForwardIterator itLast )
221 uint64_t nEpoch = m_nCurEpoch.load( atomics::memory_order_acquire );
222 while ( itFirst != itLast ) {
223 epoch_retired_ptr ep( *itFirst, nEpoch );
225 push_buffer( std::move(ep));
229 /// Retires the pointer chain until \p Func returns \p nullptr retired pointer
230 template <typename Func>
231 void batch_retire( Func e )
233 uint64_t nEpoch = m_nCurEpoch.load( atomics::memory_order_acquire );
234 for ( retired_ptr p{ e() }; p.m_p; ) {
235 epoch_retired_ptr ep( p, nEpoch );
237 push_buffer( std::move(ep));
241 /// Waits to finish a grace period and calls disposing thread
244 synchronize( false );
248 void synchronize( bool bSync )
250 uint64_t nPrevEpoch = m_nCurEpoch.fetch_add( 1, atomics::memory_order_release );
252 std::unique_lock<lock_type> sl( m_Lock );
256 m_DisposerThread.dispose( m_Buffer, nPrevEpoch, bSync );
264 /// Returns the threshold of internal buffer
265 size_t capacity() const
271 /// User-space general-purpose RCU with deferred threaded reclamation (stripped version)
273 @headerfile cds/urcu/general_threaded.h
275 This short version of \p general_threaded is intended for stripping debug info.
276 If you use \p %general_threaded with default template arguments you may use
277 this stripped version. All functionality of both classes are identical.
279 class general_threaded_stripped: public general_threaded<>
282 }} // namespace cds::urcu
284 #endif // #ifndef CDSLIB_URCU_DETAILS_GPT_H