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