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-2016
   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_relaxed );
  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_relaxed );
  96             }
  97
  98             /// Dummy copy constructor
  99             /**
 100                 In theory, spin-lock cannot be copied. However, it is not practical.
 101                 Therefore, we provide dummy copy constructor that do no copy in fact. The ctor
 102                 initializes the spin to free (unlocked) state like default ctor.
 103             */
 104             spin_lock(const spin_lock<Backoff>& ) CDS_NOEXCEPT
 105                 : m_spin( false )
 106 #   ifdef CDS_DEBUG
 107                 , m_dbgOwnerId( cds::OS::c_NullThreadId )
 108 #   endif
 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             }
 116
 117             /// Check if the spin is locked
 118             bool is_locked() const CDS_NOEXCEPT
 119             {
 120                 return m_spin.load( atomics::memory_order_relaxed );
 121             }
 122
 123             /// Try to lock the object
 124             /**
 125                 Returns \p true if locking is succeeded
 126                 otherwise (if the spin is already locked) returns \p false
 127
 128                 Debug version: deadlock can be detected
 129             */
 130             bool try_lock() CDS_NOEXCEPT
 131             {
 132                 bool bCurrent = false;
 133                 m_spin.compare_exchange_strong( bCurrent, true, atomics::memory_order_acquire, atomics::memory_order_relaxed );
 134
 135                 CDS_DEBUG_ONLY(
 136                     if ( !bCurrent ) {
 137                         m_dbgOwnerId = OS::get_current_thread_id();
 138                     }
 139                 )
 140                 return !bCurrent;
 141             }
 142
 143             /// Try to lock the object, repeat \p nTryCount times if failed
 144             /**
 145                 Returns \p true if locking is succeeded
 146                 otherwise (if the spin is already locked) returns \p false
 147             */
 148             bool try_lock( unsigned int nTryCount ) CDS_NOEXCEPT_( noexcept( backoff_strategy()()))
 149             {
 150                 backoff_strategy backoff;
 151                 while ( nTryCount-- ) {
 152                     if ( try_lock() ) {
 153                         CDS_TSAN_ANNOTATE_MUTEX_ACQUIRED( &m_spin );
 154                         return true;
 155                     }
 156                     backoff();
 157                 }
 158                 return false;
 159             }
 160
 161             /// Lock the spin-lock. Waits infinitely while spin-lock is locked. Debug version: deadlock may be detected
 162             void lock() CDS_NOEXCEPT_(noexcept( backoff_strategy()()))
 163             {
 164                 backoff_strategy backoff;
 165
 166                 // Deadlock detected
 167                 assert( m_dbgOwnerId != OS::get_current_thread_id());
 168
 169                 // TATAS algorithm
 170                 while ( !try_lock()) {
 171                     while ( m_spin.load( atomics::memory_order_relaxed )) {
 172                         backoff();
 173                     }
 174                 }
 175                 assert( m_dbgOwnerId == OS::get_current_thread_id());
 176             }
 177
 178             /// Unlock the spin-lock. Debug version: deadlock may be detected
 179             void unlock() CDS_NOEXCEPT
 180             {
 181                 assert( m_spin.load( atomics::memory_order_relaxed ));
 182
 183                 assert( m_dbgOwnerId == OS::get_current_thread_id());
 184                 CDS_DEBUG_ONLY( m_dbgOwnerId = OS::c_NullThreadId; )
 185
 186                 m_spin.store( false, atomics::memory_order_release );
 187                 CDS_TSAN_ANNOTATE_MUTEX_RELEASED( &m_spin );
 188             }
 189         };
 190
 191         /// Spin-lock implementation default for the current platform
 192         typedef spin_lock<backoff::LockDefault > spin;
 193
 194         /// Recursive spin lock.
 195         /**
 196             Allows recursive calls: the owner thread may recursive enter to critical section guarded by the spin-lock.
 197
 198             Template parameters:
 199                 - \p Integral       one of integral atomic type: <tt>unsigned int</tt>, \p int, and others
 200                 - \p Backoff        backoff strategy. Used when spin lock is locked
 201         */
 202         template <typename Integral, class Backoff>
 203         class reentrant_spin_lock
 204         {
 205             typedef OS::ThreadId    thread_id    ;        ///< The type of thread id
 206
 207         public:
 208             typedef Integral        integral_type       ; ///< The integral type
 209             typedef Backoff         backoff_strategy    ; ///< The backoff type
 210
 211         private:
 212             atomics::atomic<integral_type>   m_spin      ; ///< spin-lock atomic
 213             thread_id                        m_OwnerId   ; ///< Owner thread id. If spin-lock is not locked it usually equals to \p OS::c_NullThreadId
 214
 215         private:
 216             //@cond
 217             void take( thread_id tid ) CDS_NOEXCEPT
 218             {
 219                 m_OwnerId = tid;
 220             }
 221
 222             void free() CDS_NOEXCEPT
 223             {
 224                 m_OwnerId = OS::c_NullThreadId;
 225             }
 226
 227             bool is_taken( thread_id tid ) const CDS_NOEXCEPT
 228             {
 229                 return m_OwnerId == tid;
 230             }
 231
 232             bool try_taken_lock( thread_id tid ) CDS_NOEXCEPT
 233             {
 234                 if ( is_taken( tid )) {
 235                     m_spin.fetch_add( 1, atomics::memory_order_relaxed );
 236                     return true;
 237                 }
 238                 return false;
 239             }
 240
 241             bool try_acquire() CDS_NOEXCEPT
 242             {
 243                 integral_type nCurrent = 0;
 244                 return m_spin.compare_exchange_weak( nCurrent, 1, atomics::memory_order_acquire, atomics::memory_order_relaxed );
 245             }
 246
 247             bool try_acquire( unsigned int nTryCount ) CDS_NOEXCEPT_( noexcept( backoff_strategy()()))
 248             {
 249                 backoff_strategy bkoff;
 250
 251                 while ( nTryCount-- ) {
 252                     if ( try_acquire() ) {
 253                         CDS_TSAN_ANNOTATE_MUTEX_ACQUIRED( &m_spin );
 254                         return true;
 255                     }
 256                     bkoff();
 257                 }
 258                 return false;
 259             }
 260
 261             void acquire() CDS_NOEXCEPT_( noexcept( backoff_strategy()()))
 262             {
 263                 // TATAS algorithm
 264                 backoff_strategy bkoff;
 265                 while ( !try_acquire()) {
 266                     while ( m_spin.load( atomics::memory_order_relaxed ))
 267                         bkoff();
 268                 }
 269             }
 270             //@endcond
 271
 272         public:
 273             /// Default constructor initializes spin to free (unlocked) state
 274             reentrant_spin_lock() CDS_NOEXCEPT
 275                 : m_spin(0)
 276                 , m_OwnerId( OS::c_NullThreadId )
 277             {}
 278
 279             /// Dummy copy constructor
 280             /**
 281                 In theory, spin-lock cannot be copied. However, it is not practical.
 282                 Therefore, we provide dummy copy constructor that do no copy in fact. The ctor
 283                 initializes the spin to free (unlocked) state like default ctor.
 284             */
 285             reentrant_spin_lock( const reentrant_spin_lock<Integral, Backoff>& ) CDS_NOEXCEPT
 286                 : m_spin(0)
 287                 , m_OwnerId( OS::c_NullThreadId )
 288             {}
 289
 290             /// Construct object for specified state
 291             explicit reentrant_spin_lock( bool bLocked )
 292                 : m_spin(0)
 293                 , m_OwnerId( OS::c_NullThreadId )
 294             {
 295                 if ( bLocked )
 296                     lock();
 297             }
 298
 299             /// Checks if the spin is locked
 300             /**
 301                 The spin is locked if lock count > 0 and the current thread is not an owner of the lock.
 302                 Otherwise (i.e. lock count == 0 or the curren thread owns the spin) the spin is unlocked.
 303             */
 304             bool is_locked() const CDS_NOEXCEPT
 305             {
 306                 return !( m_spin.load( atomics::memory_order_relaxed ) == 0 || is_taken( cds::OS::get_current_thread_id()));
 307             }
 308
 309             /// Try to lock the spin-lock (synonym for \p try_lock())
 310             bool try_lock() CDS_NOEXCEPT
 311             {
 312                 thread_id tid = OS::get_current_thread_id();
 313                 if ( try_taken_lock( tid ))
 314                     return true;
 315                 if ( try_acquire()) {
 316                     take( tid );
 317                     return true;
 318                 }
 319                 return false;
 320             }
 321
 322             /// Try to lock the object
 323             bool try_lock( unsigned int nTryCount ) CDS_NOEXCEPT_( noexcept( std::declval<reentrant_spin_lock>().try_acquire( nTryCount )))
 324             {
 325                 thread_id tid = OS::get_current_thread_id();
 326                 if ( try_taken_lock( tid ))
 327                     return true;
 328                 if ( try_acquire( nTryCount )) {
 329                     take( tid );
 330                     return true;
 331                 }
 332                 return false;
 333             }
 334
 335             /// Lock the object waits if it is busy
 336             void lock() CDS_NOEXCEPT_( noexcept( std::declval<reentrant_spin_lock>().acquire()))
 337             {
 338                 thread_id tid = OS::get_current_thread_id();
 339                 if ( !try_taken_lock( tid )) {
 340                     acquire();
 341                     take( tid );
 342                 }
 343             }
 344
 345             /// Unlock the spin-lock. Return \p true if the current thread is owner of spin-lock \p false otherwise
 346             bool unlock() CDS_NOEXCEPT
 347             {
 348                 if ( is_taken( OS::get_current_thread_id())) {
 349                     integral_type n = m_spin.load( atomics::memory_order_relaxed );
 350                     if ( n > 1 )
 351                         m_spin.store( n - 1, atomics::memory_order_relaxed );
 352                     else {
 353                         free();
 354                         m_spin.store( 0, atomics::memory_order_release );
 355                         CDS_TSAN_ANNOTATE_MUTEX_RELEASED( &m_spin );
 356                     }
 357                     return true;
 358                 }
 359                 return false;
 360             }
 361
 362             /// Change the owner of locked spin-lock. May be called by thread that is owner of the spin-lock
 363             bool change_owner( OS::ThreadId newOwnerId ) CDS_NOEXCEPT
 364             {
 365                 if ( is_taken( OS::get_current_thread_id())) {
 366                     assert( newOwnerId != OS::c_NullThreadId );
 367                     m_OwnerId = newOwnerId;
 368                     return true;
 369                 }
 370                 return false;
 371             }
 372         };
 373
 374         /// Recursive 32bit spin-lock
 375         typedef reentrant_spin_lock<uint32_t, backoff::LockDefault> reentrant_spin32;
 376
 377         /// Default recursive spin-lock
 378         typedef reentrant_spin32 reentrant_spin;
 379
 380         /// Recursive 64bit spin-lock
 381         typedef reentrant_spin_lock<uint64_t, backoff::LockDefault> reentrant_spin64;
 382     }    // namespace sync
 383 } // namespace cds
 384
 385 #endif  // #ifndef CDSLIB_SYNC_SPINLOCK_H