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
  36 namespace System.Threading {
  37
  38         [HostProtectionAttribute(SecurityAction.LinkDemand, MayLeakOnAbort = true)]
  39         [HostProtectionAttribute(SecurityAction.LinkDemand, Synchronization = true, ExternalThreading = true)]
  40         public class ReaderWriterLockSlim : IDisposable
  41         {
  42                 /* Position of each bit isn't really important
  43                  * but their relative order is
  44                  */
  45                 const int RwReadBit = 3;
  46
  47                 /* These values are used to manipulate the corresponding flags in rwlock field
  48                  */
  49                 const int RwWait = 1;
  50                 const int RwWaitUpgrade = 2;
  51                 const int RwWrite = 4;
  52                 const int RwRead = 8;
  53
  54                 /* Some explanations: this field is the central point of the lock and keep track of all the requests
  55                  * that are being made. The 3 lowest bits are used as flag to track "destructive" lock entries
  56                  * (i.e attempting to take the write lock with or without having acquired an upgradeable lock beforehand).
  57                  * All the remaining bits are intepreted as the actual number of reader currently using the lock
  58                  * (which mean the lock is limited to 4294967288 concurrent readers but since it's a high number there
  59                  * is no overflow safe guard to remain simple).
  60                  */
  61                 int rwlock;
  62
  63                 readonly LockRecursionPolicy recursionPolicy;
  64
  65                 AtomicBoolean upgradableTaken = new AtomicBoolean ();
  66
  67                 /* These events are just here for the sake of having a CPU-efficient sleep
  68                  * when the wait for acquiring the lock is too long
  69                  */
  70 #if NET_4_0
  71                 ManualResetEventSlim upgradableEvent = new ManualResetEventSlim (true);
  72                 ManualResetEventSlim writerDoneEvent = new ManualResetEventSlim (true);
  73                 ManualResetEventSlim readerDoneEvent = new ManualResetEventSlim (true);
  74 #else
  75                 ManualResetEvent upgradableEvent = new ManualResetEvent (true);
  76                 ManualResetEvent writerDoneEvent = new ManualResetEvent (true);
  77                 ManualResetEvent readerDoneEvent = new ManualResetEvent (true);
  78 #endif
  79
  80                 int numReadWaiters, numUpgradeWaiters, numWriteWaiters;
  81                 bool disposed;
  82
  83                 static int idPool = int.MinValue;
  84                 readonly int id = Interlocked.Increment (ref idPool);
  85
  86                 [ThreadStatic]
  87                 static IDictionary<int, ThreadLockState> currentThreadState;
  88
  89                 public ReaderWriterLockSlim () : this (LockRecursionPolicy.NoRecursion)
  90                 {
  91                 }
  92
  93                 public ReaderWriterLockSlim (LockRecursionPolicy recursionPolicy)
  94                 {
  95                         this.recursionPolicy = recursionPolicy;
  96                 }
  97
  98                 public void EnterReadLock ()
  99                 {
 100                         TryEnterReadLock (-1);
 101                 }
 102
 103                 public bool TryEnterReadLock (int millisecondsTimeout)
 104                 {
 105                         ThreadLockState ctstate = CurrentThreadState;
 106
 107                         if (CheckState (millisecondsTimeout, LockState.Read)) {
 108                                 ctstate.ReaderRecursiveCount++;
 109                                 return true;
 110                         }
 111
 112                         // This is downgrading from upgradable, no need for check since
 113                         // we already have a sort-of read lock that's going to disappear
 114                         // after user calls ExitUpgradeableReadLock.
 115                         // Same idea when recursion is allowed and a write thread wants to
 116                         // go for a Read too.
 117                         if (CurrentLockState.Has (LockState.Upgradable)
 118                             || recursionPolicy == LockRecursionPolicy.SupportsRecursion) {
 119                                 Interlocked.Add (ref rwlock, RwRead);
 120                                 ctstate.LockState ^= LockState.Read;
 121                                 ctstate.ReaderRecursiveCount++;
 122
 123                                 return true;
 124                         }
 125
 126                         Stopwatch sw = Stopwatch.StartNew ();
 127                         Interlocked.Increment (ref numReadWaiters);
 128                         int val = 0;
 129
 130                         while (millisecondsTimeout == -1 || sw.ElapsedMilliseconds < millisecondsTimeout) {
 131                                 /* Check if a writer is present (RwWrite) or if there is someone waiting to
 132                                  * acquire a writer lock in the queue (RwWait | RwWaitUpgrade).
 133                                  */
 134                                 if ((rwlock & 0x7) > 0) {
 135                                         writerDoneEvent.Wait (ComputeTimeout (millisecondsTimeout, sw));
 136                                         continue;
 137                                 }
 138
 139                                 /* Optimistically try to add ourselves to the reader value
 140                                  * if the adding was too late and another writer came in between
 141                                  * we revert the operation.
 142                                  */
 143                                 if (((val = Interlocked.Add (ref rwlock, RwRead)) & 0x7) == 0) {
 144                                         /* If we are the first reader, reset the event to let other threads
 145                                          * sleep correctly if they try to acquire write lock
 146                                          */
 147                                         if (val >> RwReadBit == 1)
 148                                                 readerDoneEvent.Reset ();
 149
 150                                         ctstate.LockState ^= LockState.Read;
 151                                         ctstate.ReaderRecursiveCount++;
 152                                         Interlocked.Decrement (ref numReadWaiters);
 153                                         return true;
 154                                 }
 155
 156                                 Interlocked.Add (ref rwlock, -RwRead);
 157
 158                                 writerDoneEvent.Wait (ComputeTimeout (millisecondsTimeout, sw));
 159                         }
 160
 161                         Interlocked.Decrement (ref numReadWaiters);
 162                         return false;
 163                 }
 164
 165                 public bool TryEnterReadLock (TimeSpan timeout)
 166                 {
 167                         return TryEnterReadLock (CheckTimeout (timeout));
 168                 }
 169
 170                 public void ExitReadLock ()
 171                 {
 172                         ThreadLockState ctstate = CurrentThreadState;
 173
 174                         if (!ctstate.LockState.Has (LockState.Read))
 175                                 throw new SynchronizationLockException ("The current thread has not entered the lock in read mode");
 176
 177                         ctstate.LockState ^= LockState.Read;
 178                         ctstate.ReaderRecursiveCount--;
 179                         if (Interlocked.Add (ref rwlock, -RwRead) >> RwReadBit == 0)
 180                                 readerDoneEvent.Set ();
 181                 }
 182
 183                 public void EnterWriteLock ()
 184                 {
 185                         TryEnterWriteLock (-1);
 186                 }
 187
 188                 public bool TryEnterWriteLock (int millisecondsTimeout)
 189                 {
 190                         ThreadLockState ctstate = CurrentThreadState;
 191
 192                         if (CheckState (millisecondsTimeout, LockState.Write)) {
 193                                 ctstate.WriterRecursiveCount++;
 194                                 return true;
 195                         }
 196
 197                         Stopwatch sw = Stopwatch.StartNew ();
 198                         Interlocked.Increment (ref numWriteWaiters);
 199                         bool isUpgradable = ctstate.LockState.Has (LockState.Upgradable);
 200
 201                         /* If the code goes there that means we had a read lock beforehand
 202                          * that need to be suppressed, we also take the opportunity to register
 203                          * our interest in the write lock to avoid other write wannabe process
 204                          * coming in the middle
 205                          */
 206                         if (isUpgradable && rwlock >= RwRead)
 207                                 if (Interlocked.Add (ref rwlock, RwWaitUpgrade - RwRead) >> RwReadBit == 0)
 208                                         readerDoneEvent.Set ();
 209
 210                         int stateCheck = isUpgradable ? RwWaitUpgrade : RwWait;
 211
 212                         while (millisecondsTimeout < 0 || sw.ElapsedMilliseconds < millisecondsTimeout) {
 213                                 int state = rwlock;
 214
 215                                 if (state <= stateCheck) {
 216                                         if (Interlocked.CompareExchange (ref rwlock, RwWrite, state) == state) {
 217                                                 writerDoneEvent.Reset ();
 218                                                 ctstate.LockState ^= LockState.Write;
 219                                                 ctstate.WriterRecursiveCount++;
 220                                                 Interlocked.Decrement (ref numWriteWaiters);
 221                                                 return true;
 222                                         }
 223                                         state = rwlock;
 224                                 }
 225
 226                                 // We register our interest in taking the Write lock (if upgradeable it's already done)
 227                                 if (!isUpgradable)
 228                                         while ((state & RwWait) == 0 && Interlocked.CompareExchange (ref rwlock, state | RwWait, state) == state)
 229                                                 state = rwlock;
 230
 231                                 // Before falling to sleep
 232                                 while (rwlock > stateCheck && (millisecondsTimeout < 0 || sw.ElapsedMilliseconds < millisecondsTimeout)) {
 233                                         if ((rwlock & RwWrite) != 0)
 234                                                 writerDoneEvent.Wait (ComputeTimeout (millisecondsTimeout, sw));
 235                                         else if ((rwlock >> RwReadBit) > 0)
 236                                                 readerDoneEvent.Wait (ComputeTimeout (millisecondsTimeout, sw));
 237                                 }
 238                         }
 239
 240                         Interlocked.Decrement (ref numWriteWaiters);
 241                         return false;
 242                 }
 243
 244                 public bool TryEnterWriteLock (TimeSpan timeout)
 245                 {
 246                         return TryEnterWriteLock (CheckTimeout (timeout));
 247                 }
 248
 249                 public void ExitWriteLock ()
 250                 {
 251                         ThreadLockState ctstate = CurrentThreadState;
 252
 253                         if (!ctstate.LockState.Has (LockState.Write))
 254                                 throw new SynchronizationLockException ("The current thread has not entered the lock in write mode");
 255
 256                         bool isUpgradable = ctstate.LockState.Has (LockState.Upgradable);
 257                         ctstate.LockState ^= LockState.Write;
 258                         ctstate.WriterRecursiveCount--;
 259
 260                         int value = Interlocked.Add (ref rwlock, isUpgradable ? RwRead - RwWrite : -RwWrite);
 261                         writerDoneEvent.Set ();
 262                         if (isUpgradable && value >> RwReadBit == 1)
 263                                 readerDoneEvent.Reset ();
 264                 }
 265
 266                 public void EnterUpgradeableReadLock ()
 267                 {
 268                         TryEnterUpgradeableReadLock (-1);
 269                 }
 270
 271                 //
 272                 // Taking the Upgradable read lock is like taking a read lock
 273                 // but we limit it to a single upgradable at a time.
 274                 //
 275                 public bool TryEnterUpgradeableReadLock (int millisecondsTimeout)
 276                 {
 277                         ThreadLockState ctstate = CurrentThreadState;
 278
 279                         if (CheckState (millisecondsTimeout, LockState.Upgradable)) {
 280                                 ctstate.UpgradeableRecursiveCount++;
 281                                 return true;
 282                         }
 283
 284                         if (ctstate.LockState.Has (LockState.Read))
 285                                 throw new LockRecursionException ("The current thread has already entered read mode");
 286
 287                         Stopwatch sw = Stopwatch.StartNew ();
 288                         Interlocked.Increment (ref numUpgradeWaiters);
 289
 290                         // We first try to obtain the upgradeable right
 291                         while (!upgradableEvent.IsSet () || !upgradableTaken.TryRelaxedSet ()) {
 292                                 if (millisecondsTimeout != -1 && sw.ElapsedMilliseconds > millisecondsTimeout) {
 293                                         Interlocked.Decrement (ref numUpgradeWaiters);
 294                                         return false;
 295                                 }
 296
 297                                 upgradableEvent.Wait (ComputeTimeout (millisecondsTimeout, sw));
 298                         }
 299
 300                         upgradableEvent.Reset ();
 301
 302                         // Then it's a simple reader lock acquiring
 303                         if (TryEnterReadLock (ComputeTimeout (millisecondsTimeout, sw))) {
 304                                 ctstate.LockState = LockState.Upgradable;
 305                                 Interlocked.Decrement (ref numUpgradeWaiters);
 306                                 ctstate.ReaderRecursiveCount--;
 307                                 ctstate.UpgradeableRecursiveCount++;
 308                                 return true;
 309                         }
 310
 311                         upgradableTaken.Value = false;
 312                         upgradableEvent.Set ();
 313
 314                         Interlocked.Decrement (ref numUpgradeWaiters);
 315
 316                         return false;
 317                 }
 318
 319                 public bool TryEnterUpgradeableReadLock (TimeSpan timeout)
 320                 {
 321                         return TryEnterUpgradeableReadLock (CheckTimeout (timeout));
 322                 }
 323
 324                 public void ExitUpgradeableReadLock ()
 325                 {
 326                         ThreadLockState ctstate = CurrentThreadState;
 327
 328                         if (!ctstate.LockState.Has (LockState.Upgradable | LockState.Read))
 329                                 throw new SynchronizationLockException ("The current thread has not entered the lock in upgradable mode");
 330
 331                         upgradableTaken.Value = false;
 332                         upgradableEvent.Set ();
 333
 334                         ctstate.LockState ^= LockState.Upgradable;
 335                         ctstate.UpgradeableRecursiveCount--;
 336                         if (Interlocked.Add (ref rwlock, -RwRead) >> RwReadBit == 0)
 337                                 readerDoneEvent.Set ();
 338                 }
 339
 340                 public void Dispose ()
 341                 {
 342                         disposed = true;
 343                 }
 344
 345                 public bool IsReadLockHeld {
 346                         get {
 347                                 return rwlock >= RwRead && CurrentThreadState.LockState.Has (LockState.Read);
 348                         }
 349                 }
 350
 351                 public bool IsWriteLockHeld {
 352                         get {
 353                                 return (rwlock & RwWrite) > 0 && CurrentThreadState.LockState.Has (LockState.Write);
 354                         }
 355                 }
 356
 357                 public bool IsUpgradeableReadLockHeld {
 358                         get {
 359                                 return upgradableTaken.Value && CurrentThreadState.LockState.Has (LockState.Upgradable);
 360                         }
 361                 }
 362
 363                 public int CurrentReadCount {
 364                         get {
 365                                 return (rwlock >> RwReadBit) - (upgradableTaken.Value ? 1 : 0);
 366                         }
 367                 }
 368
 369                 public int RecursiveReadCount {
 370                         get {
 371                                 return CurrentThreadState.ReaderRecursiveCount;
 372                         }
 373                 }
 374
 375                 public int RecursiveUpgradeCount {
 376                         get {
 377                                 return CurrentThreadState.UpgradeableRecursiveCount;
 378                         }
 379                 }
 380
 381                 public int RecursiveWriteCount {
 382                         get {
 383                                 return CurrentThreadState.WriterRecursiveCount;
 384                         }
 385                 }
 386
 387                 public int WaitingReadCount {
 388                         get {
 389                                 return numReadWaiters;
 390                         }
 391                 }
 392
 393                 public int WaitingUpgradeCount {
 394                         get {
 395                                 return numUpgradeWaiters;
 396                         }
 397                 }
 398
 399                 public int WaitingWriteCount {
 400                         get {
 401                                 return numWriteWaiters;
 402                         }
 403                 }
 404
 405                 public LockRecursionPolicy RecursionPolicy {
 406                         get {
 407                                 return recursionPolicy;
 408                         }
 409                 }
 410
 411                 LockState CurrentLockState {
 412                         get {
 413                                 return CurrentThreadState.LockState;
 414                         }
 415                         set {
 416                                 CurrentThreadState.LockState = value;
 417                         }
 418                 }
 419
 420                 ThreadLockState CurrentThreadState {
 421                         get {
 422                                 if (currentThreadState == null)
 423                                         currentThreadState = new Dictionary<int, ThreadLockState> ();
 424
 425                                 ThreadLockState state;
 426                                 if (!currentThreadState.TryGetValue (id, out state))
 427                                         currentThreadState[id] = state = new ThreadLockState ();
 428
 429                                 return state;
 430                         }
 431                 }
 432
 433                 bool CheckState (int millisecondsTimeout, LockState validState)
 434                 {
 435                         if (disposed)
 436                                 throw new ObjectDisposedException ("ReaderWriterLockSlim");
 437
 438                         if (millisecondsTimeout < Timeout.Infinite)
 439                                 throw new ArgumentOutOfRangeException ("millisecondsTimeout");
 440
 441                         // Detect and prevent recursion
 442                         LockState ctstate = CurrentLockState;
 443
 444                         if (recursionPolicy == LockRecursionPolicy.NoRecursion)
 445                                 if ((ctstate != LockState.None && ctstate != LockState.Upgradable)
 446                                     || (ctstate == LockState.Upgradable && validState == LockState.Upgradable))
 447                                         throw new LockRecursionException ("The current thread has already a lock and recursion isn't supported");
 448
 449                         // If we already had right lock state, just return
 450                         if (ctstate.Has (validState))
 451                                 return true;
 452
 453                         CheckRecursionAuthorization (ctstate, validState);
 454
 455                         return false;
 456                 }
 457
 458                 static void CheckRecursionAuthorization (LockState ctstate, LockState desiredState)
 459                 {
 460                         // In read mode you can just enter Read recursively
 461                         if (ctstate == LockState.Read)
 462                                 throw new LockRecursionException ();
 463                 }
 464
 465                 static int CheckTimeout (TimeSpan timeout)
 466                 {
 467                         try {
 468                                 return checked ((int)timeout.TotalMilliseconds);
 469                         } catch (System.OverflowException) {
 470                                 throw new ArgumentOutOfRangeException ("timeout");
 471                         }
 472                 }
 473
 474                 static int ComputeTimeout (int millisecondsTimeout, Stopwatch sw)
 475                 {
 476                         return millisecondsTimeout == -1 ? -1 : (int)Math.Max (sw.ElapsedMilliseconds - millisecondsTimeout, 1);
 477                 }
 478         }
 479 }