mcs/class/referencesource/System.Web/Util/ReadWriteSpinLock.cs

   1 //------------------------------------------------------------------------------
   2 // <copyright file="ReadWriteSpinLock.cs" company="Microsoft">
   3 //     Copyright (c) Microsoft Corporation.  All rights reserved.
   4 // </copyright>
   5 //------------------------------------------------------------------------------
   6
   7
   8 namespace System.Web.Util {
   9
  10 using System.Threading;
  11 using System.Collections;
  12 using System.Globalization;
  13 using Microsoft.Win32;
  14
  15 struct ReadWriteSpinLock {
  16     //
  17     // Fields
  18     //
  19
  20     //  _bits is layed out as follows:
  21     //
  22     //   3 3 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1
  23     //   1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0
  24     //  +-+-+---------------------------+--------------------------------+
  25     //  |S|W|          WriteLockCount   |           ReadLockCount        |
  26     //  +-+-+---------------------------+--------------------------------+
  27     //  where
  28     //
  29     //      S - sign bit (always zero) - By having a sign bit, operations
  30     //      on the ReadLockCount can use InterlockedIncrement/Decrement
  31     //
  32     //      W - writer waiting bit - set by threads attempting write lock, preventing
  33     //          any further threads from acquiring read locks.  This attempts to hint
  34     //          that updates have priority, but doesn't guarantee priority.
  35     //
  36     //      WriteLockCount - Write lock recursion count
  37     //
  38     //      ReadLockCount - Read lock recursion count
  39     //
  40     int     _bits;
  41     int     _id;
  42
  43     //
  44     // Statics
  45     //
  46
  47     static bool s_disableBusyWaiting = (SystemInfo.GetNumProcessCPUs() == 1);
  48
  49     //
  50     // Constants
  51     //
  52
  53     const int BACK_OFF_FACTORS_LENGTH = 13;
  54     static readonly double [] s_backOffFactors = new double [BACK_OFF_FACTORS_LENGTH] {
  55         1.020, 0.965,  0.890, 1.065,
  56         1.025, 1.115,  0.940, 0.995,
  57         1.050, 1.080,  0.915, 0.980,
  58         1.010
  59     };
  60
  61     const int WRITER_WAITING_MASK   = (int) 0x40000000;
  62     const int WRITE_COUNT_MASK      = (int) 0x3FFF0000;
  63     const int READ_COUNT_MASK       = (int) 0x0000FFFF;
  64     const int WRITER_WAITING_SHIFT  = 30;
  65     const int WRITE_COUNT_SHIFT     = 16;
  66
  67     static bool WriterWaiting(int bits)             {return ((bits & WRITER_WAITING_MASK) != 0);}
  68     static int  WriteLockCount(int bits)            {return ((bits & WRITE_COUNT_MASK) >> WRITE_COUNT_SHIFT);}
  69     static int  ReadLockCount(int bits)             {return (bits & READ_COUNT_MASK);}
  70     static bool NoWriters(int bits)                 {return ((bits & WRITE_COUNT_MASK) == 0);}
  71     static bool NoWritersOrWaitingWriters(int bits) {return ((bits & (WRITE_COUNT_MASK | WRITER_WAITING_MASK)) == 0);}
  72     static bool NoLocks(int bits)                   {return ((bits & ~WRITER_WAITING_MASK) == 0);}
  73
  74     bool        WriterWaiting()                     {return WriterWaiting(_bits);}
  75     int         WriteLockCount()                    {return WriteLockCount(_bits);}
  76     int         ReadLockCount()                     {return ReadLockCount(_bits);}
  77     bool        NoWriters()                         {return NoWriters(_bits);}
  78     bool        NoWritersOrWaitingWriters()         {return NoWritersOrWaitingWriters(_bits);}
  79     bool        NoLocks()                           {return NoLocks(_bits);}
  80
  81     int CreateNewBits(bool writerWaiting, int writeCount, int readCount) {
  82         int bits = ((writeCount << WRITE_COUNT_SHIFT) | readCount);
  83         if (writerWaiting) {
  84             bits |= WRITER_WAITING_MASK;
  85         }
  86
  87         return bits;
  88     }
  89
  90
  91     internal /*public*/ void AcquireReaderLock() {
  92
  93         // This lock supports Writelock then Readlock
  94         // from the same thread (possibly from different functions).
  95         int threadId = Thread.CurrentThread.GetHashCode();
  96
  97         // Optimize for the common case by
  98         if (_TryAcquireReaderLock(threadId))
  99             return;
 100
 101         _Spin(true, threadId);
 102         Debug.Trace("Spinlock", "AcquireReaderLock: _bits=" + _bits.ToString("x8", CultureInfo.InvariantCulture)
 103                     + " _id= " + _id.ToString("x8", CultureInfo.InvariantCulture));
 104     }
 105
 106
 107     internal /*public*/ void AcquireWriterLock() {
 108
 109         int threadId = Thread.CurrentThread.GetHashCode();
 110
 111         // Optimize for the common case by
 112         if (_TryAcquireWriterLock(threadId))
 113             return;
 114
 115         _Spin(false, threadId);
 116
 117         Debug.Trace("Spinlock", "AcquireWriterLock: _bits=" + _bits.ToString("x8", CultureInfo.InvariantCulture)
 118                     + " _id= " + _id.ToString("x8", CultureInfo.InvariantCulture));
 119     }
 120
 121
 122     internal /*public*/ void ReleaseReaderLock() {
 123 #if DBG
 124         int id = _id;
 125         Debug.Assert(id == 0 || id == Thread.CurrentThread.GetHashCode(), "id == 0 || id == Thread.CurrentThread.GetHashCode()");
 126 #endif
 127
 128         int n = Interlocked.Decrement(ref _bits);
 129
 130         Debug.Assert(n >= 0, "n >= 0");
 131         Debug.Trace("Spinlock", "ReleaseReaderLock: _bits=" + _bits.ToString("x8", CultureInfo.InvariantCulture)
 132                     + " _id= " + _id.ToString("x8", CultureInfo.InvariantCulture));
 133     }
 134
 135
 136     void AlterWriteCountHoldingWriterLock(int oldBits, int delta) {
 137         int readLockCount = ReadLockCount(oldBits);
 138         int oldWriteLockCount = WriteLockCount(oldBits);
 139         int newWriteLockCount = oldWriteLockCount + delta;
 140         Debug.Assert(newWriteLockCount >= 0, "newWriteLockCount >= 0");
 141         int newBits;
 142         int test;
 143
 144         for (;;) {
 145             //
 146             // Since we own the lock, the only change that can be
 147             // made by another thread to _bits is to add the writer-waiting bit.
 148             //
 149             Debug.Assert(WriteLockCount(oldBits) == oldWriteLockCount, "WriteLockCount(oldBits) == oldWriteLockCount");
 150             Debug.Assert(ReadLockCount(oldBits) == readLockCount, "ReadLockCount(oldBits) == readLockCount");
 151             newBits = CreateNewBits(WriterWaiting(oldBits), newWriteLockCount, readLockCount);
 152             test = Interlocked.CompareExchange(ref _bits, newBits, oldBits);
 153             if (test == oldBits) {
 154                 break;
 155             }
 156
 157             oldBits = test;
 158         }
 159     }
 160
 161     internal /*public*/ void ReleaseWriterLock() {
 162 #if DBG
 163         int id = _id;
 164         Debug.Assert(id == Thread.CurrentThread.GetHashCode(), "id == Thread.CurrentThread.GetHashCode()");
 165 #endif
 166
 167         int oldBits = _bits;
 168         int writeLockCount = WriteLockCount(oldBits);
 169         Debug.Assert(writeLockCount > 0, "writeLockCount > 0");
 170         if (writeLockCount == 1) {
 171             // Reset the id before releasing count so that
 172             // AcquireRead works correctly.
 173             _id = 0;
 174         }
 175
 176         AlterWriteCountHoldingWriterLock(oldBits, -1);
 177         Debug.Trace("Spinlock", "ReleaseWriterLock: _bits=" + _bits.ToString("x8", CultureInfo.InvariantCulture)
 178                     + " _id= " + _id.ToString("x8", CultureInfo.InvariantCulture));
 179     }
 180
 181
 182     bool _TryAcquireWriterLock(int threadId) {
 183         int id = _id;
 184         int oldBits = _bits;
 185         int newBits;
 186         int test;
 187
 188         if (id == threadId) {
 189             // we can just pound in the correct value
 190             AlterWriteCountHoldingWriterLock(oldBits, +1);
 191             return true;
 192         }
 193
 194         if (id == 0 && NoLocks(oldBits)) {
 195             newBits = CreateNewBits(false, 1, 0);
 196             test = Interlocked.CompareExchange(ref _bits, newBits, oldBits);
 197             if (test == oldBits) {
 198                 id = _id;
 199                 Debug.Assert(id == 0);
 200                 _id = threadId;
 201
 202                 return true;
 203             }
 204
 205             oldBits = test;
 206         }
 207
 208         // If there is contention, make sure the WRITER_WAITING bit is set.
 209         // Note: this blocks readers from using a value that is about to be changed
 210         if (!WriterWaiting(oldBits)) {
 211             // hammer on _bits until the bit is set
 212             for (;;) {
 213                 newBits = (oldBits | WRITER_WAITING_MASK);
 214                 test = Interlocked.CompareExchange(ref _bits, newBits, oldBits);
 215                 if (test == oldBits)
 216                     break;
 217
 218                 oldBits = test;
 219             }
 220         }
 221
 222         return false;
 223     }
 224
 225     bool _TryAcquireReaderLock(int threadId) {
 226         int oldBits = _bits;
 227         int id = _id;
 228
 229         if (id == 0) {
 230             if (!NoWriters(oldBits)) {
 231                 return false;
 232             }
 233         }
 234         else if (id != threadId) {
 235             return false;
 236         }
 237
 238         if (Interlocked.CompareExchange(ref _bits, oldBits + 1, oldBits) == oldBits) {
 239             return true;
 240         }
 241
 242         return false;
 243     }
 244
 245
 246
 247     /// <internalonly/>
 248     void _Spin(bool isReaderLock, int threadId) {
 249
 250         const int LOCK_MAXIMUM_SPINS =      10000;    // maximum allowable spin count
 251         const int LOCK_DEFAULT_SPINS =       4000;    // default spin count
 252         const int LOCK_MINIMUM_SPINS =        100;    // minimum allowable spin count
 253
 254         int sleepTime = 0;
 255         int baseSpins;
 256
 257         {   // limit scope of temp. stack vars to calculation of baseSpin2
 258
 259             // Alternatives for threadId include a static counter
 260             // or the low DWORD of QueryPerformanceCounter().
 261             double randomBackoffFactor = s_backOffFactors[Math.Abs(threadId) % BACK_OFF_FACTORS_LENGTH];
 262             baseSpins = (int)(LOCK_DEFAULT_SPINS * randomBackoffFactor);
 263             baseSpins = Math.Min(LOCK_MAXIMUM_SPINS, baseSpins);
 264             baseSpins = Math.Max(baseSpins, LOCK_MINIMUM_SPINS);
 265         }
 266
 267         DateTime utcSpinStartTime = DateTime.UtcNow; // error if struct not initialized
 268
 269         // hand-optimize loop: Increase locality by copying static variables
 270         // onto the stack (this will reduce cache misses after a contact
 271         // switch induced by Sleep()).
 272         bool disableBusyWaiting = s_disableBusyWaiting;
 273
 274         for (;;) {
 275             if (isReaderLock) {
 276                 if (_TryAcquireReaderLock(threadId)) {
 277                     break;
 278                 }
 279             }
 280             else {
 281                 if (_TryAcquireWriterLock(threadId)) {
 282                     break;
 283                 }
 284             }
 285
 286             // if 1 cpu, or cpu affinity is set to 1, spinning is a waste of time
 287             if (disableBusyWaiting) {
 288
 289                 Thread.Sleep(sleepTime);
 290
 291                 // Avoid priority inversion: 0, 1, 0, 1,...
 292                 sleepTime ^= 1;
 293             }
 294             else {
 295                 int spinCount = baseSpins;
 296
 297                 // Check no more than baseSpins times then yield.
 298                 // It is important not to use the InterlockedExchange in the
 299                 // inner loop in order to minimize system memory bus traffic.
 300                 for(;;) {
 301                     //
 302                     // If the lock is available break spinning and
 303                     // try to obtain it.
 304                     //
 305                     if (isReaderLock) {
 306                         if (NoWritersOrWaitingWriters()) {
 307                             break;
 308                         }
 309                     }
 310                     else {
 311                         if (NoLocks()) {
 312                             break;
 313                         }
 314                     }
 315
 316                     if (--spinCount < 0) {
 317
 318                         Thread.Sleep(sleepTime);
 319
 320                         // Backoff algorithm: reduce (or increase) busy wait time
 321                         baseSpins /= 2;
 322                         // LOCK_MINIMUM_SPINS <= baseSpins <= LOCK_MAXIMUM_SPINS
 323                         //baseSpins = Math.Min(LOCK_MAXIMUM_SPINS, baseSpins); //= min(LOCK_MAXIMUM_SPINS, baseSpins)
 324                         baseSpins = Math.Max(baseSpins, LOCK_MINIMUM_SPINS); //= max(baseSpins, LOCK_MINIMUM_SPINS);
 325                         spinCount = baseSpins;
 326
 327                         // Using Sleep(0) leads to the possibility of priority
 328                         // inversion.  Sleep(0) only yields the processor if
 329                         // there's another thread of the same priority that's
 330                         // ready to run.  If a high-priority thread is trying to
 331                         // acquire the lock, which is held by a low-priority
 332                         // thread, then the low-priority thread may never get
 333                         // scheduled and hence never free the lock.  NT attempts
 334                         // to avoid priority inversions by temporarily boosting
 335                         // the priority of low-priority runnable threads, but the
 336                         // problem can still occur if there's a medium-priority
 337                         // thread that's always runnable.  If Sleep(1) is used,
 338                         // then the thread unconditionally yields the CPU.  We
 339                         // only do this for the second and subsequent even
 340                         // iterations, since a millisecond is a long time to wait
 341                         // if the thread can be scheduled in again sooner
 342                         // (~100,000 instructions).
 343                         // Avoid priority inversion: 0, 1, 0, 1,...
 344                         sleepTime ^= 1;
 345                     }
 346                     else {
 347                         // kill about 20 clock cycles on this proc
 348                         Thread.SpinWait(10);
 349                     }
 350                 }
 351
 352             }
 353         }// while
 354
 355     }// _Spin
 356
 357 } // ReadWriteSpinLock
 358
 359 } // namespace System.Web.Util
 360
 361 // NOTES:
 362 //
 363 // This ReaderWriterSpinlock is a combination of the
 364 // original lightweight (4 byte) System.Web.Util.ReadWriteSpinLock
 365 // and the lightweight (4 byte) exclusive lock (SmallSpinLock) used
 366 // in the George Reilly's LKRHash (see http://georgere/work/lkrhash).
 367 //
 368 // In an effort to support reentrancy during writes we are squirreling
 369 // away the thread id of the thread holding the write lock into the upper
 370 // 16 bits of the lock count.  This is possible as long as thread ids stay
 371 // smaller than 7FFF.  Anything higher than that would flip the sign bit
 372 // and we'd no longer be able to do signed comparisons to check
 373 // for read vs. write.
 374 //
 375 //          read            write
 376 // lower    #read locks     #write locks (from same thread)
 377 // higher   0x0000          thread id of thread holding lock
 378 //
 379 // Adapted from LKRHash's lock.cpp, from GeorgeRe
 380 // The original implementation is due to PALarson.
 381