cds/lock/spinlock.h

   1 //$$CDS-header$$
   2
   3 #ifndef __CDS_LOCK_SPINLOCK_H
   4 #define __CDS_LOCK_SPINLOCK_H
   5
   6 /*
   7     Defines spin-lock primitives
   8     Editions:
   9         2012.01.23  1.1.0 khizmax     Refactoring: use C++11 atomics
  10         2010.01.22  0.6.0 khizmax     Refactoring: use cds::atomic namespace
  11                                       Explicit memory ordering specification (atomic::memory_order_xxx)
  12         2006              khizmax     Created
  13 */
  14
  15 #include <cds/cxx11_atomic.h>
  16 #include <cds/os/thread.h>
  17 #include <cds/algo/backoff_strategy.h>
  18 #include <cds/lock/scoped_lock.h>
  19
  20 #include <cds/details/noncopyable.h>
  21
  22 namespace cds {
  23     /// Synchronization primitives
  24     namespace lock {
  25         /// Spin lock.
  26         /**
  27             Simple and light-weight spin-lock critical section
  28             It is useful to gain access to small (short-timed) code
  29
  30             Algorithm:
  31
  32                 TATAS (test-and-test-and-lock)
  33                 [1984] L. Rudolph, Z. Segall. Dynamic Decentralized Cache Schemes for MIMD Parallel Processors.
  34
  35             No serialization performed - any of waiting threads may owns the spin-lock.
  36             This spin-lock is NOT recursive: the thread owned the lock cannot call lock() method withod deadlock.
  37             The method unlock() can call any thread
  38
  39             DEBUG version: The spinlock stores owner thead id. Assertion is raised when:
  40                 - double lock attempt encountered by same thread (deadlock)
  41                 - unlock by another thread
  42
  43             If spin-lock is locked the Backoff algorithm is called. Predefined backoff::LockDefault class yields current
  44             thread and repeats lock attempts later
  45
  46             Template parameters:
  47                 - @p Backoff    backoff strategy. Used when spin lock is locked
  48         */
  49         template <class Backoff >
  50         class Spinlock
  51         {
  52         public:
  53             typedef        Backoff      backoff_strategy    ;        ///< back-off strategy type
  54         private:
  55             atomics::atomic<bool>    m_spin  ;       ///< Spin
  56 #    ifdef CDS_DEBUG
  57             typename OS::ThreadId       m_dbgOwnerId        ;       ///< Owner thread id (only for debug mode)
  58 #    endif
  59
  60         public:
  61             /// Construct free (unlocked) spin-lock
  62             Spinlock() CDS_NOEXCEPT
  63 #    ifdef CDS_DEBUG
  64                 :m_dbgOwnerId( OS::c_NullThreadId )
  65 #    endif
  66             {
  67                 m_spin.store( false, atomics::memory_order_relaxed );
  68             }
  69
  70             /// Construct spin-lock in specified state
  71             /**
  72                 In debug mode: if \p bLocked = true then spin-lock is made owned by current thread
  73             */
  74             Spinlock( bool bLocked ) CDS_NOEXCEPT
  75 #    ifdef CDS_DEBUG
  76                 :m_dbgOwnerId( bLocked ? OS::getCurrentThreadId() : OS::c_NullThreadId )
  77 #    endif
  78             {
  79                 m_spin.store( bLocked, atomics::memory_order_relaxed );
  80             }
  81
  82             /// Dummy copy constructor
  83             /**
  84                 In theory, spin-lock cannot be copied. However, it is not practical.
  85                 Therefore, we provide dummy copy constructor that do no copy in fact. The ctor
  86                 initializes the spin to free (unlocked) state like default ctor.
  87             */
  88             Spinlock(const Spinlock<Backoff>& ) CDS_NOEXCEPT
  89                 : m_spin( false )
  90 #   ifdef CDS_DEBUG
  91                 , m_dbgOwnerId( OS::c_NullThreadId )
  92 #   endif
  93             {}
  94
  95             /// Destructor. On debug time it checks whether spin-lock is free
  96             ~Spinlock()
  97             {
  98                 assert( !m_spin.load( atomics::memory_order_relaxed ) );
  99             }
 100
 101             /// Check if the spin is locked
 102             bool is_locked() const CDS_NOEXCEPT
 103             {
 104                 return m_spin.load( atomics::memory_order_relaxed );
 105             }
 106
 107             /// Try to lock the object
 108             /**
 109                 Returns \p true if locking is succeeded
 110                 otherwise (if the spin is already locked) returns \p false
 111
 112                 Debug version: deadlock can be detected
 113             */
 114             bool try_lock() CDS_NOEXCEPT
 115             {
 116                 return tryLock();
 117             }
 118
 119             /// Try to lock the object (synonym for \ref try_lock)
 120             bool tryLock() CDS_NOEXCEPT
 121             {
 122                 bool bCurrent = false;
 123                 m_spin.compare_exchange_strong( bCurrent, true, atomics::memory_order_acquire, atomics::memory_order_relaxed );
 124
 125                 CDS_DEBUG_ONLY(
 126                     if ( !bCurrent ) {
 127                         m_dbgOwnerId = OS::getCurrentThreadId();
 128                     }
 129                 )
 130                 return !bCurrent;
 131             }
 132
 133             /// Try to lock the object, repeat @p nTryCount times if failed
 134             /**
 135                 Returns \p true if locking is succeeded
 136                 otherwise (if the spin is already locked) returns \p false
 137             */
 138             bool try_lock( unsigned int nTryCount ) CDS_NOEXCEPT
 139             {
 140                 return tryLock( nTryCount );
 141             }
 142
 143             /// Try to lock the object (synonym for \ref try_lock)
 144             bool tryLock( unsigned int nTryCount ) CDS_NOEXCEPT
 145             {
 146                 Backoff backoff;
 147                 while ( nTryCount-- ) {
 148                     if ( tryLock() )
 149                         return true;
 150                     backoff();
 151                 }
 152                 return false;
 153             }
 154
 155             /// Lock the spin-lock. Waits infinitely while spin-lock is locked. Debug version: deadlock may be detected
 156             void lock() CDS_NOEXCEPT
 157             {
 158                 Backoff backoff;
 159
 160                 // Deadlock detected
 161                 assert( m_dbgOwnerId != OS::getCurrentThreadId() );
 162
 163                 // TATAS algorithm
 164                 while ( !tryLock() ) {
 165                     while ( m_spin.load( atomics::memory_order_relaxed ) ) {
 166                         backoff();
 167                     }
 168                 }
 169                 assert( m_dbgOwnerId == OS::getCurrentThreadId() );
 170             }
 171
 172             /// Unlock the spin-lock. Debug version: deadlock may be detected
 173             void unlock() CDS_NOEXCEPT
 174             {
 175                 assert( m_spin.load( atomics::memory_order_relaxed ) );
 176
 177                 assert( m_dbgOwnerId == OS::getCurrentThreadId() );
 178                 CDS_DEBUG_ONLY( m_dbgOwnerId = OS::c_NullThreadId; )
 179
 180                 m_spin.store( false, atomics::memory_order_release );
 181             }
 182         };
 183
 184         /// Spin-lock implementation default for the current platform
 185         typedef Spinlock<backoff::LockDefault >                 Spin;
 186
 187         /// Recursive spin lock.
 188         /**
 189             Allows recursive calls: the owner thread may recursive enter to critical section guarded by the spin-lock.
 190
 191             Template parameters:
 192                 - @p Integral       one of integral atomic type: <tt>unsigned int</tt>, <tt>int</tt>, and others
 193                 - @p Backoff        backoff strategy. Used when spin lock is locked
 194         */
 195         template <typename Integral, class Backoff>
 196         class ReentrantSpinT
 197         {
 198             typedef OS::ThreadId    thread_id    ;        ///< The type of thread id
 199
 200         public:
 201             typedef Integral        integral_type       ; ///< The integral type
 202             typedef Backoff         backoff_strategy    ; ///< The backoff type
 203
 204         private:
 205             atomics::atomic<integral_type>   m_spin      ; ///< spin-lock atomic
 206             thread_id                           m_OwnerId   ; ///< Owner thread id. If spin-lock is not locked it usually equals to OS::c_NullThreadId
 207
 208         private:
 209             //@cond
 210             void beOwner( thread_id tid ) CDS_NOEXCEPT
 211             {
 212                 m_OwnerId = tid;
 213             }
 214
 215             void free() CDS_NOEXCEPT
 216             {
 217                 m_OwnerId = OS::c_NullThreadId;
 218             }
 219
 220             bool isOwned( thread_id tid ) const CDS_NOEXCEPT
 221             {
 222                 return m_OwnerId == tid;
 223             }
 224
 225             bool    tryLockOwned( thread_id tid ) CDS_NOEXCEPT
 226             {
 227                 if ( isOwned( tid )) {
 228                     m_spin.fetch_add( 1, atomics::memory_order_relaxed );
 229                     return true;
 230                 }
 231                 return false;
 232             }
 233
 234             bool tryAcquireLock() CDS_NOEXCEPT
 235             {
 236                 integral_type nCurrent = 0;
 237                 return m_spin.compare_exchange_weak( nCurrent, 1, atomics::memory_order_acquire, atomics::memory_order_relaxed );
 238             }
 239
 240             bool tryAcquireLock( unsigned int nTryCount ) CDS_NOEXCEPT_( noexcept( backoff_strategy()() ))
 241             {
 242                 backoff_strategy bkoff;
 243
 244                 while ( nTryCount-- ) {
 245                     if ( tryAcquireLock() )
 246                         return true;
 247                     bkoff();
 248                 }
 249                 return false;
 250             }
 251
 252             void acquireLock() CDS_NOEXCEPT_( noexcept( backoff_strategy()() ))
 253             {
 254                 // TATAS algorithm
 255                 backoff_strategy bkoff;
 256                 while ( !tryAcquireLock() ) {
 257                     while ( m_spin.load( atomics::memory_order_relaxed ) )
 258                         bkoff();
 259                 }
 260             }
 261             //@endcond
 262
 263         public:
 264             /// Default constructor initializes spin to free (unlocked) state
 265             ReentrantSpinT() CDS_NOEXCEPT
 266                 : m_spin(0)
 267                 , m_OwnerId( OS::c_NullThreadId )
 268             {}
 269
 270             /// Dummy copy constructor
 271             /**
 272                 In theory, spin-lock cannot be copied. However, it is not practical.
 273                 Therefore, we provide dummy copy constructor that do no copy in fact. The ctor
 274                 initializes the spin to free (unlocked) state like default ctor.
 275             */
 276             ReentrantSpinT(const ReentrantSpinT<Integral, Backoff>& ) CDS_NOEXCEPT
 277                 : m_spin(0)
 278                 , m_OwnerId( OS::c_NullThreadId )
 279             {}
 280
 281             /// Construct object for specified state
 282             ReentrantSpinT(bool bLocked) CDS_NOEXCEPT
 283                 : m_spin(0)
 284                 , m_OwnerId( OS::c_NullThreadId )
 285             {
 286                 if ( bLocked )
 287                     lock();
 288             }
 289
 290             /// Checks if the spin is locked
 291             /**
 292                 The spin is locked if lock count > 0 and the current thread is not an owner of the lock.
 293                 Otherwise (i.e. lock count == 0 or the curren thread owns the spin) the spin is unlocked.
 294             */
 295             bool is_locked() const CDS_NOEXCEPT
 296             {
 297                 return !( m_spin.load( atomics::memory_order_relaxed ) == 0 || isOwned( cds::OS::getCurrentThreadId() ));
 298             }
 299
 300             /// Try to lock the spin-lock (synonym for \ref try_lock)
 301             bool tryLock() CDS_NOEXCEPT
 302             {
 303                 thread_id tid = OS::getCurrentThreadId();
 304                 if ( tryLockOwned( tid ) )
 305                     return true;
 306                 if ( tryAcquireLock()) {
 307                     beOwner( tid );
 308                     return true;
 309                 }
 310                 return false;
 311             }
 312
 313             /// Try to lock the spin-lock. If spin-lock is free the current thread owns it. Return @p true if locking is success
 314             bool try_lock() CDS_NOEXCEPT
 315             {
 316                 return tryLock();
 317             }
 318
 319             /// Try to lock the object (synonym for \ref try_lock)
 320             bool tryLock( unsigned int nTryCount )
 321 #       if !( (CDS_COMPILER == CDS_COMPILER_GCC && CDS_COMPILER_VERSION >= 40600 && CDS_COMPILER_VERSION < 40700) || (CDS_COMPILER == CDS_COMPILER_CLANG && CDS_COMPILER_VERSION < 30100) )
 322                 // GCC 4.6, clang 3.0 error in noexcept expression:
 323                 // cannot call member function \91bool cds::lock::ReentrantSpinT<Integral, Backoff>::tryAcquireLock(unsigned int) without object
 324                 CDS_NOEXCEPT_( noexcept( tryAcquireLock(nTryCount) ))
 325 #       endif
 326             {
 327                 thread_id tid = OS::getCurrentThreadId();
 328                 if ( tryLockOwned( tid ) )
 329                     return true;
 330                 if ( tryAcquireLock( nTryCount )) {
 331                     beOwner( tid );
 332                     return true;
 333                 }
 334                 return false;
 335             }
 336
 337             /// Try to lock the object.
 338             /**
 339                 If the spin-lock is locked the method repeats attempts to own spin-lock up to @p nTryCount times.
 340                 Between attempts @p backoff() is called.
 341                 Return @p true if current thread owns the lock @p false otherwise
 342             */
 343             bool try_lock( unsigned int nTryCount )
 344 #       if !( (CDS_COMPILER == CDS_COMPILER_GCC && CDS_COMPILER_VERSION >= 40600 && CDS_COMPILER_VERSION < 40700) || (CDS_COMPILER == CDS_COMPILER_CLANG && CDS_COMPILER_VERSION < 30100) )
 345                 // GCC 4.6, clang 3.0 error in noexcept expression:
 346                 // cannot call member function \91bool cds::lock::ReentrantSpinT<Integral, Backoff>::tryLock(unsigned int) without object
 347                 CDS_NOEXCEPT_( noexcept( tryLock(nTryCount) ))
 348 #       endif
 349             {
 350                 return tryLock( nTryCount );
 351             }
 352
 353             /// Lock the object waits if it is busy
 354             void lock() CDS_NOEXCEPT
 355             {
 356                 thread_id tid = OS::getCurrentThreadId();
 357                 if ( !tryLockOwned( tid ) ) {
 358                     acquireLock();
 359                     beOwner( tid );
 360                 }
 361             }
 362
 363             /// Unlock the spin-lock. Return @p true if the current thread is owner of spin-lock @p false otherwise
 364             bool unlock() CDS_NOEXCEPT
 365             {
 366                 if ( isOwned( OS::getCurrentThreadId() ) ) {
 367                     integral_type n = m_spin.load( atomics::memory_order_relaxed );
 368                     if ( n > 1 )
 369                         m_spin.store( n - 1, atomics::memory_order_relaxed );
 370                     else {
 371                         free();
 372                         m_spin.store( 0, atomics::memory_order_release );
 373                     }
 374                     return true;
 375                 }
 376                 return false;
 377             }
 378
 379             /// Change the owner of locked spin-lock. May be called by thread that is owner of the spin-lock
 380             bool changeOwner( OS::ThreadId newOwnerId ) CDS_NOEXCEPT
 381             {
 382                 if ( isOwned( OS::getCurrentThreadId() ) ) {
 383                     assert( newOwnerId != OS::c_NullThreadId );
 384                     m_OwnerId = newOwnerId;
 385                     return true;
 386                 }
 387                 return false;
 388             }
 389         };
 390
 391         /// Recursive spin-lock based on atomic32u_t
 392         typedef ReentrantSpinT<atomic32u_t, backoff::LockDefault>   ReentrantSpin32;
 393
 394         /// Recursive spin-lock based on atomic64u_t type
 395         typedef ReentrantSpinT<atomic64u_t, backoff::LockDefault>   ReentrantSpin64;
 396
 397         /// Recursive spin-lock based on atomic32_t type
 398         typedef ReentrantSpin32                                     ReentrantSpin;
 399
 400         /// The best (for the current platform) auto spin-lock
 401         typedef scoped_lock<Spin>   AutoSpin;
 402
 403     }    // namespace lock
 404
 405     /// Standard (best for the current platform) spin-lock implementation
 406     typedef lock::Spin              SpinLock;
 407
 408     /// Standard (best for the current platform) recursive spin-lock implementation
 409     typedef lock::ReentrantSpin     RecursiveSpinLock;
 410
 411     /// 32bit recursive spin-lock shortcut
 412     typedef lock::ReentrantSpin32   RecursiveSpinLock32;
 413
 414     /// 64bit recursive spin-lock shortcut
 415     typedef lock::ReentrantSpin64   RecursiveSpinLock64;
 416
 417     /// Auto spin-lock shortcut
 418     typedef lock::AutoSpin          AutoSpinLock;
 419
 420 } // namespace cds
 421
 422 #endif  // #ifndef __CDS_LOCK_SPINLOCK_H