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                         bool dummy = false;
 128                         return TryEnterReadLock (millisecondsTimeout, ref dummy);
 129                 }
 130
 131                 bool TryEnterReadLock (int millisecondsTimeout, ref bool success)
 132                 {
 133                         ThreadLockState ctstate = CurrentThreadState;
 134
 135                         if (CheckState (ctstate, millisecondsTimeout, LockState.Read)) {
 136                                 ++ctstate.ReaderRecursiveCount;
 137                                 return true;
 138                         }
 139
 140                         // This is downgrading from upgradable, no need for check since
 141                         // we already have a sort-of read lock that's going to disappear
 142                         // after user calls ExitUpgradeableReadLock.
 143                         // Same idea when recursion is allowed and a write thread wants to
 144                         // go for a Read too.
 145                         if (ctstate.LockState.Has (LockState.Upgradable)
 146                             || (!noRecursion && ctstate.LockState.Has (LockState.Write))) {
 147                                 RuntimeHelpers.PrepareConstrainedRegions ();
 148                                 try {}
 149                                 finally {
 150                                         Interlocked.Add (ref rwlock, RwRead);
 151                                         ctstate.LockState |= LockState.Read;
 152                                         ++ctstate.ReaderRecursiveCount;
 153                                         success = true;
 154                                 }
 155
 156                                 return true;
 157                         }
 158
 159                         ++numReadWaiters;
 160                         int val = 0;
 161                         long start = millisecondsTimeout == -1 ? 0 : sw.ElapsedMilliseconds;
 162
 163                         do {
 164                                 /* Check if a writer is present (RwWrite) or if there is someone waiting to
 165                                  * acquire a writer lock in the queue (RwWait | RwWaitUpgrade).
 166                                  */
 167                                 if ((rwlock & (RwWrite | RwWait | RwWaitUpgrade)) > 0) {
 168                                         writerDoneEvent.Wait (ComputeTimeout (millisecondsTimeout, start));
 169                                         continue;
 170                                 }
 171
 172                                 /* Optimistically try to add ourselves to the reader value
 173                                  * if the adding was too late and another writer came in between
 174                                  * we revert the operation.
 175                                  */
 176                                 RuntimeHelpers.PrepareConstrainedRegions ();
 177                                 try {}
 178                                 finally {
 179                                         if (((val = Interlocked.Add (ref rwlock, RwRead)) & (RwWrite | RwWait | RwWaitUpgrade)) == 0) {
 180                                                 /* If we are the first reader, reset the event to let other threads
 181                                                  * sleep correctly if they try to acquire write lock
 182                                                  */
 183                                                 if (val >> RwReadBit == 1)
 184                                                         readerDoneEvent.Reset ();
 185
 186                                                 ctstate.LockState ^= LockState.Read;
 187                                                 ++ctstate.ReaderRecursiveCount;
 188                                                 --numReadWaiters;
 189                                                 success = true;
 190                                         } else {
 191                                                 Interlocked.Add (ref rwlock, -RwRead);
 192                                         }
 193                                 }
 194                                 if (success)
 195                                         return true;
 196
 197                                 writerDoneEvent.Wait (ComputeTimeout (millisecondsTimeout, start));
 198                         } while (millisecondsTimeout == -1 || (sw.ElapsedMilliseconds - start) < millisecondsTimeout);
 199
 200                         --numReadWaiters;
 201                         return false;
 202                 }
 203
 204                 public bool TryEnterReadLock (TimeSpan timeout)
 205                 {
 206                         return TryEnterReadLock (CheckTimeout (timeout));
 207                 }
 208
 209                 public void ExitReadLock ()
 210                 {
 211                         RuntimeHelpers.PrepareConstrainedRegions ();
 212                         try {}
 213                         finally {
 214                                 ThreadLockState ctstate = CurrentThreadState;
 215
 216                                 if (!ctstate.LockState.Has (LockState.Read))
 217                                         throw new SynchronizationLockException ("The current thread has not entered the lock in read mode");
 218
 219                                 if (--ctstate.ReaderRecursiveCount == 0) {
 220                                         ctstate.LockState ^= LockState.Read;
 221                                         if (Interlocked.Add (ref rwlock, -RwRead) >> RwReadBit == 0)
 222                                                 readerDoneEvent.Set ();
 223                                 }
 224                         }
 225                 }
 226
 227                 public void EnterWriteLock ()
 228                 {
 229                         TryEnterWriteLock (-1);
 230                 }
 231
 232                 public bool TryEnterWriteLock (int millisecondsTimeout)
 233                 {
 234                         ThreadLockState ctstate = CurrentThreadState;
 235
 236                         if (CheckState (ctstate, millisecondsTimeout, LockState.Write)) {
 237                                 ++ctstate.WriterRecursiveCount;
 238                                 return true;
 239                         }
 240
 241                         ++numWriteWaiters;
 242                         bool isUpgradable = ctstate.LockState.Has (LockState.Upgradable);
 243                         bool registered = false;
 244                         bool success = false;
 245
 246                         RuntimeHelpers.PrepareConstrainedRegions ();
 247                         try {
 248                                 /* If the code goes there that means we had a read lock beforehand
 249                                  * that need to be suppressed, we also take the opportunity to register
 250                                  * our interest in the write lock to avoid other write wannabe process
 251                                  * coming in the middle
 252                                  */
 253                                 if (isUpgradable && rwlock >= RwRead) {
 254                                         try {}
 255                                         finally {
 256                                                 if (Interlocked.Add (ref rwlock, RwWaitUpgrade - RwRead) >> RwReadBit == 0)
 257                                                         readerDoneEvent.Set ();
 258                                                 registered = true;
 259                                         }
 260                                 }
 261
 262                                 int stateCheck = isUpgradable ? RwWaitUpgrade + RwWait : RwWait;
 263                                 long start = millisecondsTimeout == -1 ? 0 : sw.ElapsedMilliseconds;
 264                                 int registration = isUpgradable ? RwWaitUpgrade : RwWait;
 265
 266                                 do {
 267                                         int state = rwlock;
 268
 269                                         if (state <= stateCheck) {
 270                                                 try {}
 271                                                 finally {
 272                                                         var toWrite = state + RwWrite - (registered ? registration : 0);
 273                                                         if (Interlocked.CompareExchange (ref rwlock, toWrite, state) == state) {
 274                                                                 writerDoneEvent.Reset ();
 275                                                                 ctstate.LockState ^= LockState.Write;
 276                                                                 ++ctstate.WriterRecursiveCount;
 277                                                                 --numWriteWaiters;
 278                                                                 registered = false;
 279                                                                 success = true;
 280                                                         }
 281                                                 }
 282                                                 if (success)
 283                                                         return true;
 284                                         }
 285
 286                                         state = rwlock;
 287
 288                                         // We register our interest in taking the Write lock (if upgradeable it's already done)
 289                                         if (!isUpgradable) {
 290                                                 while ((state & RwWait) == 0) {
 291                                                         try {}
 292                                                         finally {
 293                                                                 if (Interlocked.CompareExchange (ref rwlock, state | RwWait, state) == state)
 294                                                                         registered = true;
 295                                                         }
 296                                                         if (registered)
 297                                                                 break;
 298                                                         state = rwlock;
 299                                                 }
 300                                         }
 301
 302                                         // Before falling to sleep
 303                                         do {
 304                                                 if (rwlock <= stateCheck)
 305                                                         break;
 306                                                 if ((rwlock & RwWrite) != 0)
 307                                                         writerDoneEvent.Wait (ComputeTimeout (millisecondsTimeout, start));
 308                                                 else if ((rwlock >> RwReadBit) > 0)
 309                                                         readerDoneEvent.Wait (ComputeTimeout (millisecondsTimeout, start));
 310                                         } while (millisecondsTimeout < 0 || (sw.ElapsedMilliseconds - start) < millisecondsTimeout);
 311                                 } while (millisecondsTimeout < 0 || (sw.ElapsedMilliseconds - start) < millisecondsTimeout);
 312
 313                                 --numWriteWaiters;
 314                         } finally {
 315                                 if (registered)
 316                                         Interlocked.Add (ref rwlock, isUpgradable ? -RwWaitUpgrade : -RwWait);
 317                         }
 318
 319                         return false;
 320                 }
 321
 322                 public bool TryEnterWriteLock (TimeSpan timeout)
 323                 {
 324                         return TryEnterWriteLock (CheckTimeout (timeout));
 325                 }
 326
 327                 public void ExitWriteLock ()
 328                 {
 329                         RuntimeHelpers.PrepareConstrainedRegions ();
 330                         try {}
 331                         finally {
 332                                 ThreadLockState ctstate = CurrentThreadState;
 333
 334                                 if (!ctstate.LockState.Has (LockState.Write))
 335                                         throw new SynchronizationLockException ("The current thread has not entered the lock in write mode");
 336
 337                                 if (--ctstate.WriterRecursiveCount == 0) {
 338                                         bool isUpgradable = ctstate.LockState.Has (LockState.Upgradable);
 339                                         ctstate.LockState ^= LockState.Write;
 340
 341                                         int value = Interlocked.Add (ref rwlock, isUpgradable ? RwRead - RwWrite : -RwWrite);
 342                                         writerDoneEvent.Set ();
 343                                         if (isUpgradable && value >> RwReadBit == 1)
 344                                                 readerDoneEvent.Reset ();
 345                                 }
 346                         }
 347                 }
 348
 349                 public void EnterUpgradeableReadLock ()
 350                 {
 351                         TryEnterUpgradeableReadLock (-1);
 352                 }
 353
 354                 //
 355                 // Taking the Upgradable read lock is like taking a read lock
 356                 // but we limit it to a single upgradable at a time.
 357                 //
 358                 public bool TryEnterUpgradeableReadLock (int millisecondsTimeout)
 359                 {
 360                         ThreadLockState ctstate = CurrentThreadState;
 361
 362                         if (CheckState (ctstate, millisecondsTimeout, LockState.Upgradable)) {
 363                                 ++ctstate.UpgradeableRecursiveCount;
 364                                 return true;
 365                         }
 366
 367                         if (ctstate.LockState.Has (LockState.Read))
 368                                 throw new LockRecursionException ("The current thread has already entered read mode");
 369
 370                         ++numUpgradeWaiters;
 371                         long start = millisecondsTimeout == -1 ? 0 : sw.ElapsedMilliseconds;
 372                         bool taken = false;
 373                         bool success = false;
 374
 375                         // We first try to obtain the upgradeable right
 376                         try {
 377                                 while (!upgradableEvent.IsSet () || !taken) {
 378                                         try {}
 379                                         finally {
 380                                                 taken = upgradableTaken.TryRelaxedSet ();
 381                                         }
 382                                         if (taken)
 383                                                 break;
 384                                         if (millisecondsTimeout != -1 && (sw.ElapsedMilliseconds - start) > millisecondsTimeout) {
 385                                                 --numUpgradeWaiters;
 386                                                 return false;
 387                                         }
 388
 389                                         upgradableEvent.Wait (ComputeTimeout (millisecondsTimeout, start));
 390                                 }
 391
 392                                 upgradableEvent.Reset ();
 393
 394                                 RuntimeHelpers.PrepareConstrainedRegions ();
 395                                 try {
 396                                         // Then it's a simple reader lock acquiring
 397                                         TryEnterReadLock (ComputeTimeout (millisecondsTimeout, start), ref success);
 398                                 } finally {
 399                                         if (success) {
 400                                                 ctstate.LockState |= LockState.Upgradable;
 401                                                 ctstate.LockState &= ~LockState.Read;
 402                                                 --ctstate.ReaderRecursiveCount;
 403                                                 ++ctstate.UpgradeableRecursiveCount;
 404                                         } else {
 405                                                 upgradableTaken.Value = false;
 406                                                 upgradableEvent.Set ();
 407                                         }
 408                                 }
 409
 410                                 --numUpgradeWaiters;
 411                         } catch {
 412                                 // An async exception occured, if we had taken the upgradable mode, release it
 413                                 if (taken && !success)
 414                                         upgradableTaken.Value = false;
 415                         }
 416
 417                         return success;
 418                 }
 419
 420                 public bool TryEnterUpgradeableReadLock (TimeSpan timeout)
 421                 {
 422                         return TryEnterUpgradeableReadLock (CheckTimeout (timeout));
 423                 }
 424
 425                 public void ExitUpgradeableReadLock ()
 426                 {
 427                         RuntimeHelpers.PrepareConstrainedRegions ();
 428                         try {}
 429                         finally {
 430                                 ThreadLockState ctstate = CurrentThreadState;
 431
 432                                 if (!ctstate.LockState.Has (LockState.Upgradable | LockState.Read))
 433                                         throw new SynchronizationLockException ("The current thread has not entered the lock in upgradable mode");
 434
 435                                 if (--ctstate.UpgradeableRecursiveCount == 0) {
 436                                         upgradableTaken.Value = false;
 437                                         upgradableEvent.Set ();
 438
 439                                         ctstate.LockState &= ~LockState.Upgradable;
 440                                         if (Interlocked.Add (ref rwlock, -RwRead) >> RwReadBit == 0)
 441                                                 readerDoneEvent.Set ();
 442                                 }
 443                         }
 444
 445                 }
 446
 447                 public void Dispose ()
 448                 {
 449                         disposed = true;
 450                 }
 451
 452                 public bool IsReadLockHeld {
 453                         get {
 454                                 return rwlock >= RwRead && CurrentThreadState.LockState.Has (LockState.Read);
 455                         }
 456                 }
 457
 458                 public bool IsWriteLockHeld {
 459                         get {
 460                                 return (rwlock & RwWrite) > 0 && CurrentThreadState.LockState.Has (LockState.Write);
 461                         }
 462                 }
 463
 464                 public bool IsUpgradeableReadLockHeld {
 465                         get {
 466                                 return upgradableTaken.Value && CurrentThreadState.LockState.Has (LockState.Upgradable);
 467                         }
 468                 }
 469
 470                 public int CurrentReadCount {
 471                         get {
 472                                 return (rwlock >> RwReadBit) - (upgradableTaken.Value ? 1 : 0);
 473                         }
 474                 }
 475
 476                 public int RecursiveReadCount {
 477                         get {
 478                                 return CurrentThreadState.ReaderRecursiveCount;
 479                         }
 480                 }
 481
 482                 public int RecursiveUpgradeCount {
 483                         get {
 484                                 return CurrentThreadState.UpgradeableRecursiveCount;
 485                         }
 486                 }
 487
 488                 public int RecursiveWriteCount {
 489                         get {
 490                                 return CurrentThreadState.WriterRecursiveCount;
 491                         }
 492                 }
 493
 494                 public int WaitingReadCount {
 495                         get {
 496                                 return numReadWaiters;
 497                         }
 498                 }
 499
 500                 public int WaitingUpgradeCount {
 501                         get {
 502                                 return numUpgradeWaiters;
 503                         }
 504                 }
 505
 506                 public int WaitingWriteCount {
 507                         get {
 508                                 return numWriteWaiters;
 509                         }
 510                 }
 511
 512                 public LockRecursionPolicy RecursionPolicy {
 513                         get {
 514                                 return recursionPolicy;
 515                         }
 516                 }
 517
 518                 ThreadLockState CurrentThreadState {
 519                         get {
 520                                 int tid = Thread.CurrentThread.ManagedThreadId;
 521
 522                                 if (tid < fastStateCache.Length)
 523                                         return fastStateCache[tid] == null ? (fastStateCache[tid] = new ThreadLockState ()) : fastStateCache[tid];
 524
 525                                 if (currentThreadState == null)
 526                                         currentThreadState = new Dictionary<int, ThreadLockState> ();
 527
 528                                 ThreadLockState state;
 529                                 if (!currentThreadState.TryGetValue (id, out state))
 530                                         currentThreadState[id] = state = new ThreadLockState ();
 531
 532                                 return state;
 533                         }
 534                 }
 535
 536                 bool CheckState (ThreadLockState state, int millisecondsTimeout, LockState validState)
 537                 {
 538                         if (disposed)
 539                                 throw new ObjectDisposedException ("ReaderWriterLockSlim");
 540
 541                         if (millisecondsTimeout < -1)
 542                                 throw new ArgumentOutOfRangeException ("millisecondsTimeout");
 543
 544                         // Detect and prevent recursion
 545                         LockState ctstate = state.LockState;
 546
 547                         if (ctstate != LockState.None && noRecursion && (!ctstate.Has (LockState.Upgradable) || validState == LockState.Upgradable))
 548                                 throw new LockRecursionException ("The current thread has already a lock and recursion isn't supported");
 549
 550                         if (noRecursion)
 551                                 return false;
 552
 553                         // If we already had right lock state, just return
 554                         if (ctstate.Has (validState))
 555                                 return true;
 556
 557                         CheckRecursionAuthorization (ctstate, validState);
 558
 559                         return false;
 560                 }
 561
 562                 static void CheckRecursionAuthorization (LockState ctstate, LockState desiredState)
 563                 {
 564                         // In read mode you can just enter Read recursively
 565                         if (ctstate == LockState.Read)
 566                                 throw new LockRecursionException ();
 567                 }
 568
 569                 static int CheckTimeout (TimeSpan timeout)
 570                 {
 571                         try {
 572                                 return checked ((int)timeout.TotalMilliseconds);
 573                         } catch (System.OverflowException) {
 574                                 throw new ArgumentOutOfRangeException ("timeout");
 575                         }
 576                 }
 577
 578                 static int ComputeTimeout (int millisecondsTimeout, long start)
 579                 {
 580                         return millisecondsTimeout == -1 ? -1 : (int)Math.Max (sw.ElapsedMilliseconds - start - millisecondsTimeout, 1);
 581                 }
 582         }
 583 }