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