cds/lock/spinlock.h

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