mcs/class/System.Core/System.Threading/ReaderWriterLockSlim.cs

   1 //
   2 // System.Threading.ReaderWriterLockSlim.cs
   3 //
   4 // Author:
   5 //       Jérémie "Garuma" Laval <jeremie.laval@gmail.com>
   6 //
   7 // Copyright (c) 2010 Jérémie "Garuma" Laval
   8 //
   9 // Permission is hereby granted, free of charge, to any person obtaining
  10 // a copy of this software and associated documentation files (the
  11 // "Software"), to deal in the Software without restriction, including
  12 // without limitation the rights to use, copy, modify, merge, publish,
  13 // distribute, sublicense, and/or sell copies of the Software, and to
  14 // permit persons to whom the Software is furnished to do so, subject to
  15 // the following conditions:
  16 //
  17 // The above copyright notice and this permission notice shall be
  18 // included in all copies or substantial portions of the Software.
  19 //
  20 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  21 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  22 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  23 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  24 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  25 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  26 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  27 //
  28
  29 using System;
  30 using System.Collections;
  31 using System.Collections.Generic;
  32 using System.Security.Permissions;
  33 using System.Diagnostics;
  34 using System.Threading;
  35 using System.Runtime.CompilerServices;
  36
  37 namespace System.Threading {
  38
  39         [HostProtectionAttribute(SecurityAction.LinkDemand, MayLeakOnAbort = true)]
  40         [HostProtectionAttribute(SecurityAction.LinkDemand, Synchronization = true, ExternalThreading = true)]
  41         public class ReaderWriterLockSlim : IDisposable
  42         {
  43                 /* Position of each bit isn't really important
  44                  * but their relative order is
  45                  */
  46                 const int RwReadBit = 3;
  47
  48                 /* These values are used to manipulate the corresponding flags in rwlock field
  49                  */
  50                 const int RwWait = 1;
  51                 const int RwWaitUpgrade = 2;
  52                 const int RwWrite = 4;
  53                 const int RwRead = 8;
  54
  55                 /* Some explanations: this field is the central point of the lock and keep track of all the requests
  56                  * that are being made. The 3 lowest bits are used as flag to track "destructive" lock entries
  57                  * (i.e attempting to take the write lock with or without having acquired an upgradeable lock beforehand).
  58                  * All the remaining bits are intepreted as the actual number of reader currently using the lock
  59                  * (which mean the lock is limited to 4294967288 concurrent readers but since it's a high number there
  60                  * is no overflow safe guard to remain simple).
  61                  */
  62                 int rwlock;
  63
  64                 readonly LockRecursionPolicy recursionPolicy;
  65                 readonly bool noRecursion;
  66
  67                 AtomicBoolean upgradableTaken = new AtomicBoolean ();
  68
  69                 /* These events are just here for the sake of having a CPU-efficient sleep
  70                  * when the wait for acquiring the lock is too long
  71                  */
  72 #if NET_4_0
  73                 ManualResetEventSlim upgradableEvent = new ManualResetEventSlim (true);
  74                 ManualResetEventSlim writerDoneEvent = new ManualResetEventSlim (true);
  75                 ManualResetEventSlim readerDoneEvent = new ManualResetEventSlim (true);
  76 #else
  77                 ManualResetEvent upgradableEvent = new ManualResetEvent (true);
  78                 ManualResetEvent writerDoneEvent = new ManualResetEvent (true);
  79                 ManualResetEvent readerDoneEvent = new ManualResetEvent (true);
  80 #endif
  81
  82                 // This Stopwatch instance is used for all threads since .Elapsed is thread-safe
  83                 readonly static Stopwatch sw = Stopwatch.StartNew ();
  84
  85                 /* For performance sake, these numbers are manipulated via classic increment and
  86                  * decrement operations and thus are (as hinted by MSDN) not meant to be precise
  87                  */
  88                 int numReadWaiters, numUpgradeWaiters, numWriteWaiters;
  89                 bool disposed;
  90
  91                 static int idPool = int.MinValue;
  92                 readonly int id = Interlocked.Increment (ref idPool);
  93
  94                 /* This dictionary is instanciated per thread for all existing ReaderWriterLockSlim instance.
  95                  * Each instance is defined by an internal integer id value used as a key in the dictionary.
  96                  * to avoid keeping unneeded reference to the instance and getting in the way of the GC.
  97                  * Since there is no LockCookie type here, all the useful per-thread infos concerning each
  98                  * instance are kept here.
  99                  */
 100                 [ThreadStatic]
 101                 static IDictionary<int, ThreadLockState> currentThreadState;
 102
 103                 /* Rwls tries to use this array as much as possible to quickly retrieve the thread-local
 104                  * informations so that it ends up being only an array lookup. When the number of thread
 105                  * using the instance goes past the length of the array, the code fallback to the normal
 106                  * dictionary
 107                  */
 108                 ThreadLockState[] fastStateCache = new ThreadLockState[64];
 109
 110                 public ReaderWriterLockSlim () : this (LockRecursionPolicy.NoRecursion)
 111                 {
 112                 }
 113
 114                 public ReaderWriterLockSlim (LockRecursionPolicy recursionPolicy)
 115                 {
 116                         this.recursionPolicy = recursionPolicy;
 117                         this.noRecursion = recursionPolicy == LockRecursionPolicy.NoRecursion;
 118                 }
 119
 120                 public void EnterReadLock ()
 121                 {
 122                         TryEnterReadLock (-1);
 123                 }
 124
 125                 public bool TryEnterReadLock (int millisecondsTimeout)
 126                 {
 127                         ThreadLockState ctstate = CurrentThreadState;
 128
 129                         if (CheckState (ctstate, millisecondsTimeout, LockState.Read)) {
 130                                 ++ctstate.ReaderRecursiveCount;
 131                                 return true;
 132                         }
 133
 134                         // This is downgrading from upgradable, no need for check since
 135                         // we already have a sort-of read lock that's going to disappear
 136                         // after user calls ExitUpgradeableReadLock.
 137                         // Same idea when recursion is allowed and a write thread wants to
 138                         // go for a Read too.
 139                         if (ctstate.LockState.Has (LockState.Upgradable)
 140                             || (!noRecursion && ctstate.LockState.Has (LockState.Write))) {
 141                                 RuntimeHelpers.PrepareConstrainedRegions ();
 142                                 try {}
 143                                 finally {
 144                                         Interlocked.Add (ref rwlock, RwRead);
 145                                         ctstate.LockState ^= LockState.Read;
 146                                         ++ctstate.ReaderRecursiveCount;
 147                                 }
 148
 149                                 return true;
 150                         }
 151
 152                         ++numReadWaiters;
 153                         int val = 0;
 154                         long start = millisecondsTimeout == -1 ? 0 : sw.ElapsedMilliseconds;
 155                         bool success = false;
 156
 157                         do {
 158                                 /* Check if a writer is present (RwWrite) or if there is someone waiting to
 159                                  * acquire a writer lock in the queue (RwWait | RwWaitUpgrade).
 160                                  */
 161                                 if ((rwlock & (RwWrite | RwWait | RwWaitUpgrade)) > 0) {
 162                                         writerDoneEvent.Wait (ComputeTimeout (millisecondsTimeout, start));
 163                                         continue;
 164                                 }
 165
 166                                 /* Optimistically try to add ourselves to the reader value
 167                                  * if the adding was too late and another writer came in between
 168                                  * we revert the operation.
 169                                  */
 170                                 RuntimeHelpers.PrepareConstrainedRegions ();
 171                                 try {}
 172                                 finally {
 173                                         if (((val = Interlocked.Add (ref rwlock, RwRead)) & (RwWrite | RwWait | RwWaitUpgrade)) == 0) {
 174                                                 /* If we are the first reader, reset the event to let other threads
 175                                                  * sleep correctly if they try to acquire write lock
 176                                                  */
 177                                                 if (val >> RwReadBit == 1)
 178                                                         readerDoneEvent.Reset ();
 179
 180                                                 ctstate.LockState ^= LockState.Read;
 181                                                 ++ctstate.ReaderRecursiveCount;
 182                                                 --numReadWaiters;
 183                                                 success = true;
 184                                         } else {
 185                                                 Interlocked.Add (ref rwlock, -RwRead);
 186                                         }
 187                                 }
 188                                 if (success)
 189                                         return true;
 190
 191                                 writerDoneEvent.Wait (ComputeTimeout (millisecondsTimeout, start));
 192                         } while (millisecondsTimeout == -1 || (sw.ElapsedMilliseconds - start) < millisecondsTimeout);
 193
 194                         --numReadWaiters;
 195                         return false;
 196                 }
 197
 198                 public bool TryEnterReadLock (TimeSpan timeout)
 199                 {
 200                         return TryEnterReadLock (CheckTimeout (timeout));
 201                 }
 202
 203                 public void ExitReadLock ()
 204                 {
 205                         RuntimeHelpers.PrepareConstrainedRegions ();
 206                         try {}
 207                         finally {
 208                                 ThreadLockState ctstate = CurrentThreadState;
 209
 210                                 if (!ctstate.LockState.Has (LockState.Read))
 211                                         throw new SynchronizationLockException ("The current thread has not entered the lock in read mode");
 212
 213                                 if (--ctstate.ReaderRecursiveCount == 0) {
 214                                         ctstate.LockState ^= LockState.Read;
 215                                         if (Interlocked.Add (ref rwlock, -RwRead) >> RwReadBit == 0)
 216                                                 readerDoneEvent.Set ();
 217                                 }
 218                         }
 219                 }
 220
 221                 public void EnterWriteLock ()
 222                 {
 223                         TryEnterWriteLock (-1);
 224                 }
 225
 226                 public bool TryEnterWriteLock (int millisecondsTimeout)
 227                 {
 228                         ThreadLockState ctstate = CurrentThreadState;
 229
 230                         if (CheckState (ctstate, millisecondsTimeout, LockState.Write)) {
 231                                 ++ctstate.WriterRecursiveCount;
 232                                 return true;
 233                         }
 234
 235                         ++numWriteWaiters;
 236                         bool isUpgradable = ctstate.LockState.Has (LockState.Upgradable);
 237                         bool registered = false;
 238                         bool success = false;
 239
 240                         RuntimeHelpers.PrepareConstrainedRegions ();
 241                         try {
 242                                 /* If the code goes there that means we had a read lock beforehand
 243                                  * that need to be suppressed, we also take the opportunity to register
 244                                  * our interest in the write lock to avoid other write wannabe process
 245                                  * coming in the middle
 246                                  */
 247                                 if (isUpgradable && rwlock >= RwRead) {
 248                                         try {}
 249                                         finally {
 250                                                 if (Interlocked.Add (ref rwlock, RwWaitUpgrade - RwRead) >> RwReadBit == 0)
 251                                                         readerDoneEvent.Set ();
 252                                                 registered = true;
 253                                         }
 254                                 }
 255
 256                                 int stateCheck = isUpgradable ? RwWaitUpgrade : RwWait;
 257                                 long start = millisecondsTimeout == -1 ? 0 : sw.ElapsedMilliseconds;
 258
 259                                 do {
 260                                         int state = rwlock;
 261
 262                                         if (state <= stateCheck) {
 263                                                 try {}
 264                                                 finally {
 265                                                         if (Interlocked.CompareExchange (ref rwlock, RwWrite, state) == state) {
 266                                                                 writerDoneEvent.Reset ();
 267                                                                 ctstate.LockState ^= LockState.Write;
 268                                                                 ++ctstate.WriterRecursiveCount;
 269                                                                 --numWriteWaiters;
 270                                                                 registered = false;
 271                                                                 success = true;
 272                                                         }
 273                                                 }
 274                                                 if (success)
 275                                                         return true;
 276                                         }
 277
 278                                         state = rwlock;
 279
 280                                         // We register our interest in taking the Write lock (if upgradeable it's already done)
 281                                         if (!isUpgradable) {
 282                                                 while ((state & RwWait) == 0) {
 283                                                         try {}
 284                                                         finally {
 285                                                                 if (Interlocked.CompareExchange (ref rwlock, state | RwWait, state) == state)
 286                                                                         registered = true;
 287                                                         }
 288                                                         if (registered)
 289                                                                 break;
 290                                                         state = rwlock;
 291                                                 }
 292                                         }
 293
 294                                         // Before falling to sleep
 295                                         do {
 296                                                 if (rwlock <= stateCheck)
 297                                                         break;
 298                                                 if ((rwlock & RwWrite) != 0)
 299                                                         writerDoneEvent.Wait (ComputeTimeout (millisecondsTimeout, start));
 300                                                 else if ((rwlock >> RwReadBit) > 0)
 301                                                         readerDoneEvent.Wait (ComputeTimeout (millisecondsTimeout, start));
 302                                         } while (millisecondsTimeout < 0 || (sw.ElapsedMilliseconds - start) < millisecondsTimeout);
 303                                 } while (millisecondsTimeout < 0 || (sw.ElapsedMilliseconds - start) < millisecondsTimeout);
 304
 305                                 --numWriteWaiters;
 306                         } finally {
 307                                 if (registered)
 308                                         Interlocked.Add (ref rwlock, isUpgradable ? -RwWaitUpgrade : -RwWait);
 309                         }
 310
 311                         return false;
 312                 }
 313
 314                 public bool TryEnterWriteLock (TimeSpan timeout)
 315                 {
 316                         return TryEnterWriteLock (CheckTimeout (timeout));
 317                 }
 318
 319                 public void ExitWriteLock ()
 320                 {
 321                         RuntimeHelpers.PrepareConstrainedRegions ();
 322                         try {}
 323                         finally {
 324                                 ThreadLockState ctstate = CurrentThreadState;
 325
 326                                 if (!ctstate.LockState.Has (LockState.Write))
 327                                         throw new SynchronizationLockException ("The current thread has not entered the lock in write mode");
 328
 329                                 if (--ctstate.WriterRecursiveCount == 0) {
 330                                         bool isUpgradable = ctstate.LockState.Has (LockState.Upgradable);
 331                                         ctstate.LockState ^= LockState.Write;
 332
 333                                         int value = Interlocked.Add (ref rwlock, isUpgradable ? RwRead - RwWrite : -RwWrite);
 334                                         writerDoneEvent.Set ();
 335                                         if (isUpgradable && value >> RwReadBit == 1)
 336                                                 readerDoneEvent.Reset ();
 337                                 }
 338                         }
 339                 }
 340
 341                 public void EnterUpgradeableReadLock ()
 342                 {
 343                         TryEnterUpgradeableReadLock (-1);
 344                 }
 345
 346                 //
 347                 // Taking the Upgradable read lock is like taking a read lock
 348                 // but we limit it to a single upgradable at a time.
 349                 //
 350                 public bool TryEnterUpgradeableReadLock (int millisecondsTimeout)
 351                 {
 352                         ThreadLockState ctstate = CurrentThreadState;
 353
 354                         if (CheckState (ctstate, millisecondsTimeout, LockState.Upgradable)) {
 355                                 ++ctstate.UpgradeableRecursiveCount;
 356                                 return true;
 357                         }
 358
 359                         if (ctstate.LockState.Has (LockState.Read))
 360                                 throw new LockRecursionException ("The current thread has already entered read mode");
 361
 362                         ++numUpgradeWaiters;
 363                         long start = millisecondsTimeout == -1 ? 0 : sw.ElapsedMilliseconds;
 364
 365                         // We first try to obtain the upgradeable right
 366                         while (!upgradableEvent.IsSet () || !upgradableTaken.TryRelaxedSet ()) {
 367                                 if (millisecondsTimeout != -1 && (sw.ElapsedMilliseconds - start) > millisecondsTimeout) {
 368                                         --numUpgradeWaiters;
 369                                         return false;
 370                                 }
 371
 372                                 upgradableEvent.Wait (ComputeTimeout (millisecondsTimeout, start));
 373                         }
 374
 375                         upgradableEvent.Reset ();
 376
 377                         // Then it's a simple reader lock acquiring
 378                         if (TryEnterReadLock (ComputeTimeout (millisecondsTimeout, start))) {
 379                                 ctstate.LockState = LockState.Upgradable;
 380                                 --numUpgradeWaiters;
 381                                 --ctstate.ReaderRecursiveCount;
 382                                 ++ctstate.UpgradeableRecursiveCount;
 383                                 return true;
 384                         }
 385
 386                         upgradableTaken.Value = false;
 387                         upgradableEvent.Set ();
 388
 389                         --numUpgradeWaiters;
 390
 391                         return false;
 392                 }
 393
 394                 public bool TryEnterUpgradeableReadLock (TimeSpan timeout)
 395                 {
 396                         return TryEnterUpgradeableReadLock (CheckTimeout (timeout));
 397                 }
 398
 399                 public void ExitUpgradeableReadLock ()
 400                 {
 401                         RuntimeHelpers.PrepareConstrainedRegions ();
 402                         try {}
 403                         finally {
 404                                 ThreadLockState ctstate = CurrentThreadState;
 405
 406                                 if (!ctstate.LockState.Has (LockState.Upgradable | LockState.Read))
 407                                         throw new SynchronizationLockException ("The current thread has not entered the lock in upgradable mode");
 408
 409                                 if (--ctstate.UpgradeableRecursiveCount == 0) {
 410                                         upgradableTaken.Value = false;
 411                                         upgradableEvent.Set ();
 412
 413                                         ctstate.LockState ^= LockState.Upgradable;
 414                                         if (Interlocked.Add (ref rwlock, -RwRead) >> RwReadBit == 0)
 415                                                 readerDoneEvent.Set ();
 416                                 }
 417                         }
 418                 }
 419
 420                 public void Dispose ()
 421                 {
 422                         disposed = true;
 423                 }
 424
 425                 public bool IsReadLockHeld {
 426                         get {
 427                                 return rwlock >= RwRead && CurrentThreadState.LockState.Has (LockState.Read);
 428                         }
 429                 }
 430
 431                 public bool IsWriteLockHeld {
 432                         get {
 433                                 return (rwlock & RwWrite) > 0 && CurrentThreadState.LockState.Has (LockState.Write);
 434                         }
 435                 }
 436
 437                 public bool IsUpgradeableReadLockHeld {
 438                         get {
 439                                 return upgradableTaken.Value && CurrentThreadState.LockState.Has (LockState.Upgradable);
 440                         }
 441                 }
 442
 443                 public int CurrentReadCount {
 444                         get {
 445                                 return (rwlock >> RwReadBit) - (upgradableTaken.Value ? 1 : 0);
 446                         }
 447                 }
 448
 449                 public int RecursiveReadCount {
 450                         get {
 451                                 return CurrentThreadState.ReaderRecursiveCount;
 452                         }
 453                 }
 454
 455                 public int RecursiveUpgradeCount {
 456                         get {
 457                                 return CurrentThreadState.UpgradeableRecursiveCount;
 458                         }
 459                 }
 460
 461                 public int RecursiveWriteCount {
 462                         get {
 463                                 return CurrentThreadState.WriterRecursiveCount;
 464                         }
 465                 }
 466
 467                 public int WaitingReadCount {
 468                         get {
 469                                 return numReadWaiters;
 470                         }
 471                 }
 472
 473                 public int WaitingUpgradeCount {
 474                         get {
 475                                 return numUpgradeWaiters;
 476                         }
 477                 }
 478
 479                 public int WaitingWriteCount {
 480                         get {
 481                                 return numWriteWaiters;
 482                         }
 483                 }
 484
 485                 public LockRecursionPolicy RecursionPolicy {
 486                         get {
 487                                 return recursionPolicy;
 488                         }
 489                 }
 490
 491                 ThreadLockState CurrentThreadState {
 492                         get {
 493                                 int tid = Thread.CurrentThread.ManagedThreadId;
 494
 495                                 if (tid < fastStateCache.Length)
 496                                         return fastStateCache[tid] == null ? (fastStateCache[tid] = new ThreadLockState ()) : fastStateCache[tid];
 497
 498                                 if (currentThreadState == null)
 499                                         currentThreadState = new Dictionary<int, ThreadLockState> ();
 500
 501                                 ThreadLockState state;
 502                                 if (!currentThreadState.TryGetValue (id, out state))
 503                                         currentThreadState[id] = state = new ThreadLockState ();
 504
 505                                 return state;
 506                         }
 507                 }
 508
 509                 bool CheckState (ThreadLockState state, int millisecondsTimeout, LockState validState)
 510                 {
 511                         if (disposed)
 512                                 throw new ObjectDisposedException ("ReaderWriterLockSlim");
 513
 514                         if (millisecondsTimeout < -1)
 515                                 throw new ArgumentOutOfRangeException ("millisecondsTimeout");
 516
 517                         // Detect and prevent recursion
 518                         LockState ctstate = state.LockState;
 519
 520                         if (ctstate != LockState.None && noRecursion && (ctstate != LockState.Upgradable || validState == LockState.Upgradable))
 521                                 throw new LockRecursionException ("The current thread has already a lock and recursion isn't supported");
 522
 523                         if (noRecursion)
 524                                 return false;
 525
 526                         // If we already had right lock state, just return
 527                         if (ctstate.Has (validState))
 528                                 return true;
 529
 530                         CheckRecursionAuthorization (ctstate, validState);
 531
 532                         return false;
 533                 }
 534
 535                 static void CheckRecursionAuthorization (LockState ctstate, LockState desiredState)
 536                 {
 537                         // In read mode you can just enter Read recursively
 538                         if (ctstate == LockState.Read)
 539                                 throw new LockRecursionException ();
 540                 }
 541
 542                 static int CheckTimeout (TimeSpan timeout)
 543                 {
 544                         try {
 545                                 return checked ((int)timeout.TotalMilliseconds);
 546                         } catch (System.OverflowException) {
 547                                 throw new ArgumentOutOfRangeException ("timeout");
 548                         }
 549                 }
 550
 551                 static int ComputeTimeout (int millisecondsTimeout, long start)
 552                 {
 553                         return millisecondsTimeout == -1 ? -1 : (int)Math.Max (sw.ElapsedMilliseconds - start - millisecondsTimeout, 1);
 554                 }
 555         }
 556 }