cds/sync/spinlock.h

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