Merge branch 'integration' into dev
[libcds.git] / cds / sync / spinlock.h
1 //$$CDS-header$$
2
3 #ifndef CDSLIB_SYNC_SPINLOCK_H
4 #define CDSLIB_SYNC_SPINLOCK_H
5
6 #include <cds/algo/atomic.h>
7 #include <cds/os/thread.h>
8 #include <cds/algo/backoff_strategy.h>
9
10 namespace cds {
11     /// Synchronization primitives
12     namespace sync {
13         /// Spin lock
14         /**
15             Simple and light-weight spin-lock critical section
16             It is useful to gain access to small (short-timed) code
17
18             Algorithm:
19
20                 TATAS (test-and-test-and-lock)
21                 [1984] L. Rudolph, Z. Segall. Dynamic Decentralized Cache Schemes for MIMD Parallel Processors.
22
23             No serialization performed - any of waiting threads may owns the spin-lock.
24             This spin-lock is NOT recursive: the thread owned the lock cannot call lock() method withod deadlock.
25             The method unlock() can call any thread
26
27             DEBUG version: The spinlock stores owner thead id. Assertion is raised when:
28                 - double lock attempt encountered by same thread (deadlock)
29                 - unlock by another thread
30
31             If spin-lock is locked the Backoff algorithm is called. Predefined backoff::LockDefault class yields current
32             thread and repeats lock attempts later
33
34             Template parameters:
35                 - @p Backoff    backoff strategy. Used when spin lock is locked
36         */
37         template <typename Backoff >
38         class spin_lock
39         {
40         public:
41             typedef Backoff backoff_strategy;   ///< back-off strategy type
42         private:
43             atomics::atomic<bool>    m_spin;    ///< Spin
44 #    ifdef CDS_DEBUG
45             typename OS::ThreadId    m_dbgOwnerId; ///< Owner thread id (only for debug mode)
46 #    endif
47
48         public:
49             /// Construct free (unlocked) spin-lock
50             spin_lock() CDS_NOEXCEPT
51 #    ifdef CDS_DEBUG
52                 :m_dbgOwnerId( OS::c_NullThreadId )
53 #    endif
54             {
55                 m_spin.store( false, atomics::memory_order_relaxed );
56             }
57
58             /// Construct spin-lock in specified state
59             /**
60                 In debug mode: if \p bLocked = true then spin-lock is made owned by current thread
61             */
62             spin_lock( bool bLocked ) CDS_NOEXCEPT
63 #    ifdef CDS_DEBUG
64                 : m_dbgOwnerId( bLocked ? cds::OS::get_current_thread_id() : cds::OS::c_NullThreadId )
65 #    endif
66             {
67                 m_spin.store( bLocked, atomics::memory_order_relaxed );
68             }
69
70             /// Dummy copy constructor
71             /**
72                 In theory, spin-lock cannot be copied. However, it is not practical.
73                 Therefore, we provide dummy copy constructor that do no copy in fact. The ctor
74                 initializes the spin to free (unlocked) state like default ctor.
75             */
76             spin_lock(const spin_lock<Backoff>& ) CDS_NOEXCEPT
77                 : m_spin( false )
78 #   ifdef CDS_DEBUG
79                 , m_dbgOwnerId( cds::OS::c_NullThreadId )
80 #   endif
81             {}
82
83             /// Destructor. On debug time it checks whether spin-lock is free
84             ~spin_lock()
85             {
86                 assert( !m_spin.load( atomics::memory_order_relaxed ) );
87             }
88
89             /// Check if the spin is locked
90             bool is_locked() const CDS_NOEXCEPT
91             {
92                 return m_spin.load( atomics::memory_order_relaxed );
93             }
94
95             /// Try to lock the object
96             /**
97                 Returns \p true if locking is succeeded
98                 otherwise (if the spin is already locked) returns \p false
99
100                 Debug version: deadlock can be detected
101             */
102             bool try_lock() CDS_NOEXCEPT
103             {
104                 bool bCurrent = false;
105                 m_spin.compare_exchange_strong( bCurrent, true, atomics::memory_order_acquire, atomics::memory_order_relaxed );
106
107                 CDS_DEBUG_ONLY(
108                     if ( !bCurrent ) {
109                         m_dbgOwnerId = OS::get_current_thread_id();
110                     }
111                 )
112                 return !bCurrent;
113             }
114
115             /// Try to lock the object, repeat @p nTryCount times if failed
116             /**
117                 Returns \p true if locking is succeeded
118                 otherwise (if the spin is already locked) returns \p false
119             */
120             bool try_lock( unsigned int nTryCount ) CDS_NOEXCEPT_( noexcept( backoff_strategy()() ) )
121             {
122                 backoff_strategy backoff;
123                 while ( nTryCount-- ) {
124                     if ( try_lock() )
125                         return true;
126                     backoff();
127                 }
128                 return false;
129             }
130
131             /// Lock the spin-lock. Waits infinitely while spin-lock is locked. Debug version: deadlock may be detected
132             void lock() CDS_NOEXCEPT_(noexcept( backoff_strategy()() ))
133             {
134                 backoff_strategy backoff;
135
136                 // Deadlock detected
137                 assert( m_dbgOwnerId != OS::get_current_thread_id() );
138
139                 // TATAS algorithm
140                 while ( !try_lock() ) {
141                     while ( m_spin.load( atomics::memory_order_relaxed ) ) {
142                         backoff();
143                     }
144                 }
145                 assert( m_dbgOwnerId == OS::get_current_thread_id() );
146             }
147
148             /// Unlock the spin-lock. Debug version: deadlock may be detected
149             void unlock() CDS_NOEXCEPT
150             {
151                 assert( m_spin.load( atomics::memory_order_relaxed ) );
152
153                 assert( m_dbgOwnerId == OS::get_current_thread_id() );
154                 CDS_DEBUG_ONLY( m_dbgOwnerId = OS::c_NullThreadId; )
155
156                 m_spin.store( false, atomics::memory_order_release );
157             }
158         };
159
160         /// Spin-lock implementation default for the current platform
161         typedef spin_lock<backoff::LockDefault > spin;
162
163         /// Recursive spin lock.
164         /**
165             Allows recursive calls: the owner thread may recursive enter to critical section guarded by the spin-lock.
166
167             Template parameters:
168                 - @p Integral       one of integral atomic type: <tt>unsigned int</tt>, <tt>int</tt>, and others
169                 - @p Backoff        backoff strategy. Used when spin lock is locked
170         */
171         template <typename Integral, class Backoff>
172         class reentrant_spin_lock
173         {
174             typedef OS::ThreadId    thread_id    ;        ///< The type of thread id
175
176         public:
177             typedef Integral        integral_type       ; ///< The integral type
178             typedef Backoff         backoff_strategy    ; ///< The backoff type
179
180         private:
181             atomics::atomic<integral_type>   m_spin      ; ///< spin-lock atomic
182             thread_id                        m_OwnerId   ; ///< Owner thread id. If spin-lock is not locked it usually equals to OS::c_NullThreadId
183
184         private:
185             //@cond
186             void take( thread_id tid ) CDS_NOEXCEPT
187             {
188                 m_OwnerId = tid;
189             }
190
191             void free() CDS_NOEXCEPT
192             {
193                 m_OwnerId = OS::c_NullThreadId;
194             }
195
196             bool is_taken( thread_id tid ) const CDS_NOEXCEPT
197             {
198                 return m_OwnerId == tid;
199             }
200
201             bool try_taken_lock( thread_id tid ) CDS_NOEXCEPT
202             {
203                 if ( is_taken( tid )) {
204                     m_spin.fetch_add( 1, atomics::memory_order_relaxed );
205                     return true;
206                 }
207                 return false;
208             }
209
210             bool try_acquire() CDS_NOEXCEPT
211             {
212                 integral_type nCurrent = 0;
213                 return m_spin.compare_exchange_weak( nCurrent, 1, atomics::memory_order_acquire, atomics::memory_order_relaxed );
214             }
215
216             bool try_acquire( unsigned int nTryCount ) CDS_NOEXCEPT_( noexcept( backoff_strategy()() ))
217             {
218                 backoff_strategy bkoff;
219
220                 while ( nTryCount-- ) {
221                     if ( try_acquire() )
222                         return true;
223                     bkoff();
224                 }
225                 return false;
226             }
227
228             void acquire() CDS_NOEXCEPT_( noexcept( backoff_strategy()() ))
229             {
230                 // TATAS algorithm
231                 backoff_strategy bkoff;
232                 while ( !try_acquire() ) {
233                     while ( m_spin.load( atomics::memory_order_relaxed ) )
234                         bkoff();
235                 }
236             }
237             //@endcond
238
239         public:
240             /// Default constructor initializes spin to free (unlocked) state
241             reentrant_spin_lock() CDS_NOEXCEPT
242                 : m_spin(0)
243                 , m_OwnerId( OS::c_NullThreadId )
244             {}
245
246             /// Dummy copy constructor
247             /**
248                 In theory, spin-lock cannot be copied. However, it is not practical.
249                 Therefore, we provide dummy copy constructor that do no copy in fact. The ctor
250                 initializes the spin to free (unlocked) state like default ctor.
251             */
252             reentrant_spin_lock( const reentrant_spin_lock<Integral, Backoff>& ) CDS_NOEXCEPT
253                 : m_spin(0)
254                 , m_OwnerId( OS::c_NullThreadId )
255             {}
256
257             /// Construct object for specified state
258             reentrant_spin_lock( bool bLocked ) CDS_NOEXCEPT
259                 : m_spin(0)
260                 , m_OwnerId( OS::c_NullThreadId )
261             {
262                 if ( bLocked )
263                     lock();
264             }
265
266             /// Checks if the spin is locked
267             /**
268                 The spin is locked if lock count > 0 and the current thread is not an owner of the lock.
269                 Otherwise (i.e. lock count == 0 or the curren thread owns the spin) the spin is unlocked.
270             */
271             bool is_locked() const CDS_NOEXCEPT
272             {
273                 return !( m_spin.load( atomics::memory_order_relaxed ) == 0 || is_taken( cds::OS::get_current_thread_id() ));
274             }
275
276             /// Try to lock the spin-lock (synonym for \ref try_lock)
277             bool try_lock() CDS_NOEXCEPT
278             {
279                 thread_id tid = OS::get_current_thread_id();
280                 if ( try_taken_lock( tid ) )
281                     return true;
282                 if ( try_acquire()) {
283                     take( tid );
284                     return true;
285                 }
286                 return false;
287             }
288
289             /// Try to lock the object
290             bool try_lock( unsigned int nTryCount ) CDS_NOEXCEPT_( noexcept( try_acquire( nTryCount ) ) )
291             {
292                 thread_id tid = OS::get_current_thread_id();
293                 if ( try_taken_lock( tid ) )
294                     return true;
295                 if ( try_acquire( nTryCount )) {
296                     take( tid );
297                     return true;
298                 }
299                 return false;
300             }
301
302             /// Lock the object waits if it is busy
303             void lock() CDS_NOEXCEPT
304             {
305                 thread_id tid = OS::get_current_thread_id();
306                 if ( !try_taken_lock( tid ) ) {
307                     acquire();
308                     take( tid );
309                 }
310             }
311
312             /// Unlock the spin-lock. Return @p true if the current thread is owner of spin-lock @p false otherwise
313             bool unlock() CDS_NOEXCEPT
314             {
315                 if ( is_taken( OS::get_current_thread_id() ) ) {
316                     integral_type n = m_spin.load( atomics::memory_order_relaxed );
317                     if ( n > 1 )
318                         m_spin.store( n - 1, atomics::memory_order_relaxed );
319                     else {
320                         free();
321                         m_spin.store( 0, atomics::memory_order_release );
322                     }
323                     return true;
324                 }
325                 return false;
326             }
327
328             /// Change the owner of locked spin-lock. May be called by thread that is owner of the spin-lock
329             bool change_owner( OS::ThreadId newOwnerId ) CDS_NOEXCEPT
330             {
331                 if ( is_taken( OS::get_current_thread_id() ) ) {
332                     assert( newOwnerId != OS::c_NullThreadId );
333                     m_OwnerId = newOwnerId;
334                     return true;
335                 }
336                 return false;
337             }
338         };
339
340         /// Recursive 32bit spin-lock
341         typedef reentrant_spin_lock<uint32_t, backoff::LockDefault> reentrant_spin32;
342
343         /// Default recursive spin-lock
344         typedef reentrant_spin32 reentrant_spin;
345
346         /// Recursive 64bit spin-lock
347         typedef reentrant_spin_lock<uint64_t, backoff::LockDefault> reentrant_spin64;
348     }    // namespace sync
349 } // namespace cds
350
351 #endif  // #ifndef CDSLIB_SYNC_SPINLOCK_H