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                 public 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
 265                                 do {
 266                                         int state = rwlock;
 267
 268                                         if (state <= stateCheck) {
 269                                                 try {}
 270                                                 finally {
 271                                                         if (Interlocked.CompareExchange (ref rwlock, RwWrite, state) == state) {
 272                                                                 writerDoneEvent.Reset ();
 273                                                                 ctstate.LockState ^= LockState.Write;
 274                                                                 ++ctstate.WriterRecursiveCount;
 275                                                                 --numWriteWaiters;
 276                                                                 registered = false;
 277                                                                 success = true;
 278                                                         }
 279                                                 }
 280                                                 if (success)
 281                                                         return true;
 282                                         }
 283
 284                                         state = rwlock;
 285
 286                                         // We register our interest in taking the Write lock (if upgradeable it's already done)
 287                                         if (!isUpgradable) {
 288                                                 while ((state & RwWait) == 0) {
 289                                                         try {}
 290                                                         finally {
 291                                                                 if (Interlocked.CompareExchange (ref rwlock, state | RwWait, state) == state)
 292                                                                         registered = true;
 293                                                         }
 294                                                         if (registered)
 295                                                                 break;
 296                                                         state = rwlock;
 297                                                 }
 298                                         }
 299
 300                                         // Before falling to sleep
 301                                         do {
 302                                                 if (rwlock <= stateCheck)
 303                                                         break;
 304                                                 if ((rwlock & RwWrite) != 0)
 305                                                         writerDoneEvent.Wait (ComputeTimeout (millisecondsTimeout, start));
 306                                                 else if ((rwlock >> RwReadBit) > 0)
 307                                                         readerDoneEvent.Wait (ComputeTimeout (millisecondsTimeout, start));
 308                                         } while (millisecondsTimeout < 0 || (sw.ElapsedMilliseconds - start) < millisecondsTimeout);
 309                                 } while (millisecondsTimeout < 0 || (sw.ElapsedMilliseconds - start) < millisecondsTimeout);
 310
 311                                 --numWriteWaiters;
 312                         } finally {
 313                                 if (registered)
 314                                         Interlocked.Add (ref rwlock, isUpgradable ? -RwWaitUpgrade : -RwWait);
 315                         }
 316
 317                         return false;
 318                 }
 319
 320                 public bool TryEnterWriteLock (TimeSpan timeout)
 321                 {
 322                         return TryEnterWriteLock (CheckTimeout (timeout));
 323                 }
 324
 325                 public void ExitWriteLock ()
 326                 {
 327                         RuntimeHelpers.PrepareConstrainedRegions ();
 328                         try {}
 329                         finally {
 330                                 ThreadLockState ctstate = CurrentThreadState;
 331
 332                                 if (!ctstate.LockState.Has (LockState.Write))
 333                                         throw new SynchronizationLockException ("The current thread has not entered the lock in write mode");
 334
 335                                 if (--ctstate.WriterRecursiveCount == 0) {
 336                                         bool isUpgradable = ctstate.LockState.Has (LockState.Upgradable);
 337                                         ctstate.LockState ^= LockState.Write;
 338
 339                                         int value = Interlocked.Add (ref rwlock, isUpgradable ? RwRead - RwWrite : -RwWrite);
 340                                         writerDoneEvent.Set ();
 341                                         if (isUpgradable && value >> RwReadBit == 1)
 342                                                 readerDoneEvent.Reset ();
 343                                 }
 344                         }
 345                 }
 346
 347                 public void EnterUpgradeableReadLock ()
 348                 {
 349                         TryEnterUpgradeableReadLock (-1);
 350                 }
 351
 352                 //
 353                 // Taking the Upgradable read lock is like taking a read lock
 354                 // but we limit it to a single upgradable at a time.
 355                 //
 356                 public bool TryEnterUpgradeableReadLock (int millisecondsTimeout)
 357                 {
 358                         ThreadLockState ctstate = CurrentThreadState;
 359
 360                         if (CheckState (ctstate, millisecondsTimeout, LockState.Upgradable)) {
 361                                 ++ctstate.UpgradeableRecursiveCount;
 362                                 return true;
 363                         }
 364
 365                         if (ctstate.LockState.Has (LockState.Read))
 366                                 throw new LockRecursionException ("The current thread has already entered read mode");
 367
 368                         ++numUpgradeWaiters;
 369                         long start = millisecondsTimeout == -1 ? 0 : sw.ElapsedMilliseconds;
 370                         bool taken = false;
 371                         bool success = false;
 372
 373                         // We first try to obtain the upgradeable right
 374                         try {
 375                                 while (!upgradableEvent.IsSet () || !taken) {
 376                                         try {}
 377                                         finally {
 378                                                 taken = upgradableTaken.TryRelaxedSet ();
 379                                         }
 380                                         if (taken)
 381                                                 break;
 382                                         if (millisecondsTimeout != -1 && (sw.ElapsedMilliseconds - start) > millisecondsTimeout) {
 383                                                 --numUpgradeWaiters;
 384                                                 return false;
 385                                         }
 386
 387                                         upgradableEvent.Wait (ComputeTimeout (millisecondsTimeout, start));
 388                                 }
 389
 390                                 upgradableEvent.Reset ();
 391
 392                                 RuntimeHelpers.PrepareConstrainedRegions ();
 393                                 try {
 394                                         // Then it's a simple reader lock acquiring
 395                                         TryEnterReadLock (ComputeTimeout (millisecondsTimeout, start), ref success);
 396                                 } finally {
 397                                         if (success) {
 398                                                 ctstate.LockState |= LockState.Upgradable;
 399                                                 ctstate.LockState &= ~LockState.Read;
 400                                                 --ctstate.ReaderRecursiveCount;
 401                                                 ++ctstate.UpgradeableRecursiveCount;
 402                                         } else {
 403                                                 upgradableTaken.Value = false;
 404                                                 upgradableEvent.Set ();
 405                                         }
 406                                 }
 407
 408                                 --numUpgradeWaiters;
 409                         } catch {
 410                                 // An async exception occured, if we had taken the upgradable mode, release it
 411                                 if (taken && !success)
 412                                         upgradableTaken.Value = false;
 413                         }
 414
 415                         return success;
 416                 }
 417
 418                 public bool TryEnterUpgradeableReadLock (TimeSpan timeout)
 419                 {
 420                         return TryEnterUpgradeableReadLock (CheckTimeout (timeout));
 421                 }
 422
 423                 public void ExitUpgradeableReadLock ()
 424                 {
 425                         RuntimeHelpers.PrepareConstrainedRegions ();
 426                         try {}
 427                         finally {
 428                                 ThreadLockState ctstate = CurrentThreadState;
 429
 430                                 if (!ctstate.LockState.Has (LockState.Upgradable | LockState.Read))
 431                                         throw new SynchronizationLockException ("The current thread has not entered the lock in upgradable mode");
 432
 433                                 if (--ctstate.UpgradeableRecursiveCount == 0) {
 434                                         upgradableTaken.Value = false;
 435                                         upgradableEvent.Set ();
 436
 437                                         ctstate.LockState &= ~LockState.Upgradable;
 438                                         if (Interlocked.Add (ref rwlock, -RwRead) >> RwReadBit == 0)
 439                                                 readerDoneEvent.Set ();
 440                                 }
 441                         }
 442
 443                 }
 444
 445                 public void Dispose ()
 446                 {
 447                         disposed = true;
 448                 }
 449
 450                 public bool IsReadLockHeld {
 451                         get {
 452                                 return rwlock >= RwRead && CurrentThreadState.LockState.Has (LockState.Read);
 453                         }
 454                 }
 455
 456                 public bool IsWriteLockHeld {
 457                         get {
 458                                 return (rwlock & RwWrite) > 0 && CurrentThreadState.LockState.Has (LockState.Write);
 459                         }
 460                 }
 461
 462                 public bool IsUpgradeableReadLockHeld {
 463                         get {
 464                                 return upgradableTaken.Value && CurrentThreadState.LockState.Has (LockState.Upgradable);
 465                         }
 466                 }
 467
 468                 public int CurrentReadCount {
 469                         get {
 470                                 return (rwlock >> RwReadBit) - (upgradableTaken.Value ? 1 : 0);
 471                         }
 472                 }
 473
 474                 public int RecursiveReadCount {
 475                         get {
 476                                 return CurrentThreadState.ReaderRecursiveCount;
 477                         }
 478                 }
 479
 480                 public int RecursiveUpgradeCount {
 481                         get {
 482                                 return CurrentThreadState.UpgradeableRecursiveCount;
 483                         }
 484                 }
 485
 486                 public int RecursiveWriteCount {
 487                         get {
 488                                 return CurrentThreadState.WriterRecursiveCount;
 489                         }
 490                 }
 491
 492                 public int WaitingReadCount {
 493                         get {
 494                                 return numReadWaiters;
 495                         }
 496                 }
 497
 498                 public int WaitingUpgradeCount {
 499                         get {
 500                                 return numUpgradeWaiters;
 501                         }
 502                 }
 503
 504                 public int WaitingWriteCount {
 505                         get {
 506                                 return numWriteWaiters;
 507                         }
 508                 }
 509
 510                 public LockRecursionPolicy RecursionPolicy {
 511                         get {
 512                                 return recursionPolicy;
 513                         }
 514                 }
 515
 516                 ThreadLockState CurrentThreadState {
 517                         get {
 518                                 int tid = Thread.CurrentThread.ManagedThreadId;
 519
 520                                 if (tid < fastStateCache.Length)
 521                                         return fastStateCache[tid] == null ? (fastStateCache[tid] = new ThreadLockState ()) : fastStateCache[tid];
 522
 523                                 if (currentThreadState == null)
 524                                         currentThreadState = new Dictionary<int, ThreadLockState> ();
 525
 526                                 ThreadLockState state;
 527                                 if (!currentThreadState.TryGetValue (id, out state))
 528                                         currentThreadState[id] = state = new ThreadLockState ();
 529
 530                                 return state;
 531                         }
 532                 }
 533
 534                 bool CheckState (ThreadLockState state, int millisecondsTimeout, LockState validState)
 535                 {
 536                         if (disposed)
 537                                 throw new ObjectDisposedException ("ReaderWriterLockSlim");
 538
 539                         if (millisecondsTimeout < -1)
 540                                 throw new ArgumentOutOfRangeException ("millisecondsTimeout");
 541
 542                         // Detect and prevent recursion
 543                         LockState ctstate = state.LockState;
 544
 545                         if (ctstate != LockState.None && noRecursion && (!ctstate.Has (LockState.Upgradable) || validState == LockState.Upgradable))
 546                                 throw new LockRecursionException ("The current thread has already a lock and recursion isn't supported");
 547
 548                         if (noRecursion)
 549                                 return false;
 550
 551                         // If we already had right lock state, just return
 552                         if (ctstate.Has (validState))
 553                                 return true;
 554
 555                         CheckRecursionAuthorization (ctstate, validState);
 556
 557                         return false;
 558                 }
 559
 560                 static void CheckRecursionAuthorization (LockState ctstate, LockState desiredState)
 561                 {
 562                         // In read mode you can just enter Read recursively
 563                         if (ctstate == LockState.Read)
 564                                 throw new LockRecursionException ();
 565                 }
 566
 567                 static int CheckTimeout (TimeSpan timeout)
 568                 {
 569                         try {
 570                                 return checked ((int)timeout.TotalMilliseconds);
 571                         } catch (System.OverflowException) {
 572                                 throw new ArgumentOutOfRangeException ("timeout");
 573                         }
 574                 }
 575
 576                 static int ComputeTimeout (int millisecondsTimeout, long start)
 577                 {
 578                         return millisecondsTimeout == -1 ? -1 : (int)Math.Max (sw.ElapsedMilliseconds - start - millisecondsTimeout, 1);
 579                 }
 580         }
 581 }