1 // Licensed to the .NET Foundation under one or more agreements.
2 // The .NET Foundation licenses this file to you under the MIT license.
3 // See the LICENSE file in the project root for more information.
5 using System
.Diagnostics
; // for TraceInformation
6 using System
.Diagnostics
.CodeAnalysis
;
7 using System
.Runtime
.CompilerServices
;
9 namespace System
.Threading
11 public enum LockRecursionPolicy
14 SupportsRecursion
= 1,
18 // ReaderWriterCount tracks how many of each kind of lock is held by each thread.
19 // We keep a linked list for each thread, attached to a ThreadStatic field.
20 // These are reused wherever possible, so that a given thread will only
21 // allocate N of these, where N is the maximum number of locks held simultaneously
24 internal class ReaderWriterCount
26 // Which lock does this object belong to? This is a numeric ID for two reasons:
27 // 1) We don't want this field to keep the lock object alive, and a WeakReference would
29 // 2) Setting the value of a long is faster than setting the value of a reference.
30 // The "hot" paths in ReaderWriterLockSlim are short enough that this actually
34 // How many reader locks does this thread hold on this ReaderWriterLockSlim instance?
35 public int readercount
;
37 // Ditto for writer/upgrader counts. These are only used if the lock allows recursion.
38 // But we have to have the fields on every ReaderWriterCount instance, because
39 // we reuse it for different locks.
40 public int writercount
;
41 public int upgradecount
;
43 // Next RWC in this thread's list.
44 public ReaderWriterCount
? next
;
48 /// A reader-writer lock implementation that is intended to be simple, yet very
49 /// efficient. In particular only 1 interlocked operation is taken for any lock
50 /// operation (we use spin locks to achieve this). The spin lock is never held
51 /// for more than a few instructions (in particular, we never call event APIs
52 /// or in fact any non-trivial API while holding the spin lock).
54 public class ReaderWriterLockSlim
: IDisposable
56 private static readonly int ProcessorCount
= Environment
.ProcessorCount
;
58 //Specifying if the lock can be reacquired recursively.
59 private readonly bool _fIsReentrant
;
61 // Lock specification for _spinLock: This lock protects exactly the local fields associated with this
62 // instance of ReaderWriterLockSlim. It does NOT protect the memory associated with
63 // the events that hang off this lock (eg writeEvent, readEvent upgradeEvent).
64 private SpinLock _spinLock
;
66 // These variables allow use to avoid Setting events (which is expensive) if we don't have to.
67 private uint _numWriteWaiters
; // maximum number of threads that can be doing a WaitOne on the writeEvent
68 private uint _numReadWaiters
; // maximum number of threads that can be doing a WaitOne on the readEvent
69 private uint _numWriteUpgradeWaiters
; // maximum number of threads that can be doing a WaitOne on the upgradeEvent (at most 1).
70 private uint _numUpgradeWaiters
;
72 private WaiterStates _waiterStates
;
74 private int _upgradeLockOwnerId
;
75 private int _writeLockOwnerId
;
77 // conditions we wait on.
78 private EventWaitHandle
? _writeEvent
; // threads waiting to acquire a write lock go here.
79 private EventWaitHandle
? _readEvent
; // threads waiting to acquire a read lock go here (will be released in bulk)
80 private EventWaitHandle
? _upgradeEvent
; // thread waiting to acquire the upgrade lock
81 private EventWaitHandle
? _waitUpgradeEvent
; // thread waiting to upgrade from the upgrade lock to a write lock go here (at most one)
83 // Every lock instance has a unique ID, which is used by ReaderWriterCount to associate itself with the lock
84 // without holding a reference to it.
85 private static long s_nextLockID
;
86 private readonly long _lockID
;
88 // See comments on ReaderWriterCount.
90 private static ReaderWriterCount
? t_rwc
;
92 private bool _fUpgradeThreadHoldingRead
;
94 private const int MaxSpinCount
= 20;
96 //The uint, that contains info like if the writer lock is held, num of
102 //The Uint is divided as follows:
104 //Writer-Owned Waiting-Writers Waiting Upgraders Num-Readers
105 // 31 30 29 28.......0
107 //Dividing the uint, allows to vastly simplify logic for checking if a
108 //reader should go in etc. Setting the writer bit will automatically
109 //make the value of the uint much larger than the max num of readers
110 //allowed, thus causing the check for max_readers to fail.
112 private const uint WRITER_HELD
= 0x80000000;
113 private const uint WAITING_WRITERS
= 0x40000000;
114 private const uint WAITING_UPGRADER
= 0x20000000;
116 //The max readers is actually one less then its theoretical max.
117 //This is done in order to prevent reader count overflows. If the reader
118 //count reaches max, other readers will wait.
119 private const uint MAX_READER
= 0x10000000 - 2;
121 private const uint READER_MASK
= 0x10000000 - 1;
123 private bool _fDisposed
;
125 private void InitializeThreadCounts()
127 _upgradeLockOwnerId
= -1;
128 _writeLockOwnerId
= -1;
131 public ReaderWriterLockSlim()
132 : this(LockRecursionPolicy
.NoRecursion
)
136 public ReaderWriterLockSlim(LockRecursionPolicy recursionPolicy
)
138 if (recursionPolicy
== LockRecursionPolicy
.SupportsRecursion
)
140 _fIsReentrant
= true;
142 InitializeThreadCounts();
143 _waiterStates
= WaiterStates
.NoWaiters
;
144 _lockID
= Interlocked
.Increment(ref s_nextLockID
);
147 private bool HasNoWaiters
152 Debug
.Assert(_spinLock
.IsHeld
);
155 return (_waiterStates
& WaiterStates
.NoWaiters
) != WaiterStates
.None
;
160 Debug
.Assert(_spinLock
.IsHeld
);
165 _waiterStates
|= WaiterStates
.NoWaiters
;
169 _waiterStates
&= ~WaiterStates
.NoWaiters
;
174 [MethodImpl(MethodImplOptions
.AggressiveInlining
)]
175 private static bool IsRWEntryEmpty(ReaderWriterCount rwc
)
179 else if (rwc
.readercount
== 0 && rwc
.writercount
== 0 && rwc
.upgradecount
== 0)
185 private bool IsRwHashEntryChanged(ReaderWriterCount lrwc
)
187 return lrwc
.lockID
!= _lockID
;
191 /// This routine retrieves/sets the per-thread counts needed to enforce the
192 /// various rules related to acquiring the lock.
194 /// DontAllocate is set to true if the caller just wants to get an existing
195 /// entry for this thread, but doesn't want to add one if an existing one
196 /// could not be found.
198 [MethodImpl(MethodImplOptions
.AggressiveInlining
)]
199 private ReaderWriterCount
? GetThreadRWCount(bool dontAllocate
)
201 ReaderWriterCount
? rwc
= t_rwc
;
202 ReaderWriterCount
? empty
= null;
205 if (rwc
.lockID
== _lockID
)
208 if (!dontAllocate
&& empty
== null && IsRWEntryEmpty(rwc
))
219 empty
= new ReaderWriterCount();
224 empty
.lockID
= _lockID
;
228 public void EnterReadLock()
230 TryEnterReadLock(-1);
234 // Common timeout support
236 private struct TimeoutTracker
238 private readonly int _total
;
239 private readonly int _start
;
241 public TimeoutTracker(TimeSpan timeout
)
243 long ltm
= (long)timeout
.TotalMilliseconds
;
244 if (ltm
< -1 || ltm
> (long)int.MaxValue
)
245 throw new ArgumentOutOfRangeException(nameof(timeout
));
247 if (_total
!= -1 && _total
!= 0)
248 _start
= Environment
.TickCount
;
253 public TimeoutTracker(int millisecondsTimeout
)
255 if (millisecondsTimeout
< -1)
256 throw new ArgumentOutOfRangeException(nameof(millisecondsTimeout
));
257 _total
= millisecondsTimeout
;
258 if (_total
!= -1 && _total
!= 0)
259 _start
= Environment
.TickCount
;
264 public int RemainingMilliseconds
268 if (_total
== -1 || _total
== 0)
271 int elapsed
= Environment
.TickCount
- _start
;
272 // elapsed may be negative if TickCount has overflowed by 2^31 milliseconds.
273 if (elapsed
< 0 || elapsed
>= _total
)
276 return _total
- elapsed
;
280 public bool IsExpired
284 return RemainingMilliseconds
== 0;
289 public bool TryEnterReadLock(TimeSpan timeout
)
291 return TryEnterReadLock(new TimeoutTracker(timeout
));
294 public bool TryEnterReadLock(int millisecondsTimeout
)
296 return TryEnterReadLock(new TimeoutTracker(millisecondsTimeout
));
299 private bool TryEnterReadLock(TimeoutTracker timeout
)
301 return TryEnterReadLockCore(timeout
);
304 private bool TryEnterReadLockCore(TimeoutTracker timeout
)
307 throw new ObjectDisposedException(null);
309 ReaderWriterCount lrwc
;
310 int id
= Environment
.CurrentManagedThreadId
;
314 if (id
== _writeLockOwnerId
)
317 throw new LockRecursionException(SR
.LockRecursionException_ReadAfterWriteNotAllowed
);
320 _spinLock
.Enter(EnterSpinLockReason
.EnterAnyRead
);
322 lrwc
= GetThreadRWCount(dontAllocate
: false)!;
324 //Check if the reader lock is already acquired. Note, we could
325 //check the presence of a reader by not allocating rwc (But that
326 //would lead to two lookups in the common case. It's better to keep
327 //a count in the structure).
328 if (lrwc
.readercount
> 0)
331 throw new LockRecursionException(SR
.LockRecursionException_RecursiveReadNotAllowed
);
333 else if (id
== _upgradeLockOwnerId
)
335 //The upgrade lock is already held.
336 //Update the global read counts and exit.
346 _spinLock
.Enter(EnterSpinLockReason
.EnterAnyRead
);
347 lrwc
= GetThreadRWCount(dontAllocate
: false)!;
348 if (lrwc
.readercount
> 0)
354 else if (id
== _upgradeLockOwnerId
)
356 //The upgrade lock is already held.
357 //Update the global read counts and exit.
361 _fUpgradeThreadHoldingRead
= true;
364 else if (id
== _writeLockOwnerId
)
366 //The write lock is already held.
367 //Update global read counts here,
380 // We can enter a read lock if there are only read-locks have been given out
381 // and a writer is not trying to get in.
383 if (_owners
< MAX_READER
)
385 // Good case, there is no contention, we are basically done
386 _owners
++; // Indicate we have another reader
391 if (timeout
.IsExpired
)
397 if (spinCount
< MaxSpinCount
&& ShouldSpinForEnterAnyRead())
402 _spinLock
.Enter(EnterSpinLockReason
.EnterAnyRead
);
403 //The per-thread structure may have been recycled as the lock is acquired (due to message pumping), load again.
404 if (IsRwHashEntryChanged(lrwc
))
405 lrwc
= GetThreadRWCount(dontAllocate
: false)!;
409 // Drat, we need to wait. Mark that we have waiters and wait.
410 if (_readEvent
== null) // Create the needed event
412 LazyCreateEvent(ref _readEvent
, EnterLockType
.Read
);
413 if (IsRwHashEntryChanged(lrwc
))
414 lrwc
= GetThreadRWCount(dontAllocate
: false)!;
415 continue; // since we left the lock, start over.
418 retVal
= WaitOnEvent(_readEvent
, ref _numReadWaiters
, timeout
, EnterLockType
.Read
);
423 if (IsRwHashEntryChanged(lrwc
))
424 lrwc
= GetThreadRWCount(dontAllocate
: false)!;
431 public void EnterWriteLock()
433 TryEnterWriteLock(-1);
436 public bool TryEnterWriteLock(TimeSpan timeout
)
438 return TryEnterWriteLock(new TimeoutTracker(timeout
));
441 public bool TryEnterWriteLock(int millisecondsTimeout
)
443 return TryEnterWriteLock(new TimeoutTracker(millisecondsTimeout
));
446 private bool TryEnterWriteLock(TimeoutTracker timeout
)
448 return TryEnterWriteLockCore(timeout
);
451 private bool TryEnterWriteLockCore(TimeoutTracker timeout
)
454 throw new ObjectDisposedException(null);
456 int id
= Environment
.CurrentManagedThreadId
;
457 ReaderWriterCount
? lrwc
;
458 bool upgradingToWrite
= false;
462 EnterSpinLockReason enterMyLockReason
;
463 if (id
== _writeLockOwnerId
)
466 throw new LockRecursionException(SR
.LockRecursionException_RecursiveWriteNotAllowed
);
468 else if (id
== _upgradeLockOwnerId
)
470 //AU->AW case is allowed once.
471 upgradingToWrite
= true;
472 enterMyLockReason
= EnterSpinLockReason
.UpgradeToWrite
;
476 enterMyLockReason
= EnterSpinLockReason
.EnterWrite
;
478 _spinLock
.Enter(enterMyLockReason
);
480 lrwc
= GetThreadRWCount(dontAllocate
: true);
482 //Can't acquire write lock with reader lock held.
483 if (lrwc
!= null && lrwc
.readercount
> 0)
486 throw new LockRecursionException(SR
.LockRecursionException_WriteAfterReadNotAllowed
);
491 EnterSpinLockReason enterMyLockReason
;
492 if (id
== _writeLockOwnerId
)
494 enterMyLockReason
= EnterSpinLockReason
.EnterRecursiveWrite
;
496 else if (id
== _upgradeLockOwnerId
)
498 enterMyLockReason
= EnterSpinLockReason
.UpgradeToWrite
;
502 enterMyLockReason
= EnterSpinLockReason
.EnterWrite
;
504 _spinLock
.Enter(enterMyLockReason
);
506 lrwc
= GetThreadRWCount(dontAllocate
: false)!;
508 if (id
== _writeLockOwnerId
)
514 else if (id
== _upgradeLockOwnerId
)
516 upgradingToWrite
= true;
518 else if (lrwc
.readercount
> 0)
520 //Write locks may not be acquired if only read locks have been
523 throw new LockRecursionException(SR
.LockRecursionException_WriteAfterReadNotAllowed
);
532 if (IsWriterAcquired())
534 // Good case, there is no contention, we are basically done
539 //Check if there is just one upgrader, and no readers.
540 //Assumption: Only one thread can have the upgrade lock, so the
541 //following check will fail for all other threads that may sneak in
542 //when the upgrading thread is waiting.
544 if (upgradingToWrite
)
546 uint readercount
= GetNumReaders();
548 if (readercount
== 1)
550 //Good case again, there is just one upgrader, and no readers.
551 SetWriterAcquired(); // indicate we have a writer.
554 else if (readercount
== 2)
558 if (IsRwHashEntryChanged(lrwc
))
559 lrwc
= GetThreadRWCount(dontAllocate
: false)!;
561 if (lrwc
.readercount
> 0)
563 //This check is needed for EU->ER->EW case, as the owner count will be two.
564 Debug
.Assert(_fIsReentrant
);
565 Debug
.Assert(_fUpgradeThreadHoldingRead
);
567 //Good case again, there is just one upgrader, and no readers.
568 SetWriterAcquired(); // indicate we have a writer.
575 if (timeout
.IsExpired
)
581 if (spinCount
< MaxSpinCount
&& ShouldSpinForEnterAnyWrite(upgradingToWrite
))
586 _spinLock
.Enter(upgradingToWrite
? EnterSpinLockReason
.UpgradeToWrite
: EnterSpinLockReason
.EnterWrite
);
590 if (upgradingToWrite
)
592 if (_waitUpgradeEvent
== null) // Create the needed event
594 LazyCreateEvent(ref _waitUpgradeEvent
, EnterLockType
.UpgradeToWrite
);
595 continue; // since we left the lock, start over.
598 Debug
.Assert(_numWriteUpgradeWaiters
== 0, "There can be at most one thread with the upgrade lock held.");
600 retVal
= WaitOnEvent(_waitUpgradeEvent
, ref _numWriteUpgradeWaiters
, timeout
, EnterLockType
.UpgradeToWrite
);
602 //The lock is not held in case of failure.
608 // Drat, we need to wait. Mark that we have waiters and wait.
609 if (_writeEvent
== null) // create the needed event.
611 LazyCreateEvent(ref _writeEvent
, EnterLockType
.Write
);
612 continue; // since we left the lock, start over.
615 retVal
= WaitOnEvent(_writeEvent
, ref _numWriteWaiters
, timeout
, EnterLockType
.Write
);
616 //The lock is not held in case of failure.
622 Debug
.Assert((_owners
& WRITER_HELD
) > 0);
626 Debug
.Assert(lrwc
!= null, "Initialized based on _fIsReentrant earlier in the method");
627 if (IsRwHashEntryChanged(lrwc
))
628 lrwc
= GetThreadRWCount(dontAllocate
: false)!;
634 _writeLockOwnerId
= id
;
639 public void EnterUpgradeableReadLock()
641 TryEnterUpgradeableReadLock(-1);
644 public bool TryEnterUpgradeableReadLock(TimeSpan timeout
)
646 return TryEnterUpgradeableReadLock(new TimeoutTracker(timeout
));
649 public bool TryEnterUpgradeableReadLock(int millisecondsTimeout
)
651 return TryEnterUpgradeableReadLock(new TimeoutTracker(millisecondsTimeout
));
654 private bool TryEnterUpgradeableReadLock(TimeoutTracker timeout
)
656 return TryEnterUpgradeableReadLockCore(timeout
);
659 private bool TryEnterUpgradeableReadLockCore(TimeoutTracker timeout
)
662 throw new ObjectDisposedException(null);
664 int id
= Environment
.CurrentManagedThreadId
;
665 ReaderWriterCount
? lrwc
;
669 if (id
== _upgradeLockOwnerId
)
672 throw new LockRecursionException(SR
.LockRecursionException_RecursiveUpgradeNotAllowed
);
674 else if (id
== _writeLockOwnerId
)
677 throw new LockRecursionException(SR
.LockRecursionException_UpgradeAfterWriteNotAllowed
);
680 _spinLock
.Enter(EnterSpinLockReason
.EnterAnyRead
);
681 lrwc
= GetThreadRWCount(dontAllocate
: true);
682 //Can't acquire upgrade lock with reader lock held.
683 if (lrwc
!= null && lrwc
.readercount
> 0)
686 throw new LockRecursionException(SR
.LockRecursionException_UpgradeAfterReadNotAllowed
);
691 _spinLock
.Enter(EnterSpinLockReason
.EnterAnyRead
);
692 lrwc
= GetThreadRWCount(dontAllocate
: false)!;
694 if (id
== _upgradeLockOwnerId
)
700 else if (id
== _writeLockOwnerId
)
702 //Write lock is already held, Just update the global state
703 //to show presence of upgrader.
704 Debug
.Assert((_owners
& WRITER_HELD
) > 0);
706 _upgradeLockOwnerId
= id
;
708 if (lrwc
.readercount
> 0)
709 _fUpgradeThreadHoldingRead
= true;
713 else if (lrwc
.readercount
> 0)
715 //Upgrade locks may not be acquired if only read locks have been
718 throw new LockRecursionException(SR
.LockRecursionException_UpgradeAfterReadNotAllowed
);
727 //Once an upgrade lock is taken, it's like having a reader lock held
728 //until upgrade or downgrade operations are performed.
730 if ((_upgradeLockOwnerId
== -1) && (_owners
< MAX_READER
))
733 _upgradeLockOwnerId
= id
;
737 if (timeout
.IsExpired
)
743 if (spinCount
< MaxSpinCount
&& ShouldSpinForEnterAnyRead())
748 _spinLock
.Enter(EnterSpinLockReason
.EnterAnyRead
);
752 // Drat, we need to wait. Mark that we have waiters and wait.
753 if (_upgradeEvent
== null) // Create the needed event
755 LazyCreateEvent(ref _upgradeEvent
, EnterLockType
.UpgradeableRead
);
756 continue; // since we left the lock, start over.
759 //Only one thread with the upgrade lock held can proceed.
760 retVal
= WaitOnEvent(_upgradeEvent
, ref _numUpgradeWaiters
, timeout
, EnterLockType
.UpgradeableRead
);
767 //The lock may have been dropped getting here, so make a quick check to see whether some other
768 //thread did not grab the entry.
769 Debug
.Assert(lrwc
!= null, "Initialized based on _fIsReentrant earlier in the method");
770 if (IsRwHashEntryChanged(lrwc
))
771 lrwc
= GetThreadRWCount(dontAllocate
: false)!;
780 public void ExitReadLock()
782 _spinLock
.Enter(EnterSpinLockReason
.ExitAnyRead
);
784 ReaderWriterCount
? lrwc
= GetThreadRWCount(dontAllocate
: true);
786 if (lrwc
== null || lrwc
.readercount
< 1)
788 //You have to be holding the read lock to make this call.
790 throw new SynchronizationLockException(SR
.SynchronizationLockException_MisMatchedRead
);
795 if (lrwc
.readercount
> 1)
802 if (Environment
.CurrentManagedThreadId
== _upgradeLockOwnerId
)
804 _fUpgradeThreadHoldingRead
= false;
808 Debug
.Assert(_owners
> 0, "ReleasingReaderLock: releasing lock and no read lock taken");
812 Debug
.Assert(lrwc
.readercount
== 1);
815 ExitAndWakeUpAppropriateWaiters();
818 public void ExitWriteLock()
820 ReaderWriterCount lrwc
;
823 if (Environment
.CurrentManagedThreadId
!= _writeLockOwnerId
)
825 //You have to be holding the write lock to make this call.
826 throw new SynchronizationLockException(SR
.SynchronizationLockException_MisMatchedWrite
);
828 _spinLock
.Enter(EnterSpinLockReason
.ExitAnyWrite
);
832 _spinLock
.Enter(EnterSpinLockReason
.ExitAnyWrite
);
833 lrwc
= GetThreadRWCount(dontAllocate
: false)!;
838 throw new SynchronizationLockException(SR
.SynchronizationLockException_MisMatchedWrite
);
841 if (lrwc
.writercount
< 1)
844 throw new SynchronizationLockException(SR
.SynchronizationLockException_MisMatchedWrite
);
849 if (lrwc
.writercount
> 0)
856 Debug
.Assert((_owners
& WRITER_HELD
) > 0, "Calling ReleaseWriterLock when no write lock is held");
858 ClearWriterAcquired();
860 _writeLockOwnerId
= -1;
862 ExitAndWakeUpAppropriateWaiters();
865 public void ExitUpgradeableReadLock()
867 ReaderWriterCount
? lrwc
;
870 if (Environment
.CurrentManagedThreadId
!= _upgradeLockOwnerId
)
872 //You have to be holding the upgrade lock to make this call.
873 throw new SynchronizationLockException(SR
.SynchronizationLockException_MisMatchedUpgrade
);
875 _spinLock
.Enter(EnterSpinLockReason
.ExitAnyRead
);
879 _spinLock
.Enter(EnterSpinLockReason
.ExitAnyRead
);
880 lrwc
= GetThreadRWCount(dontAllocate
: true);
885 throw new SynchronizationLockException(SR
.SynchronizationLockException_MisMatchedUpgrade
);
888 if (lrwc
.upgradecount
< 1)
891 throw new SynchronizationLockException(SR
.SynchronizationLockException_MisMatchedUpgrade
);
896 if (lrwc
.upgradecount
> 0)
902 _fUpgradeThreadHoldingRead
= false;
906 _upgradeLockOwnerId
= -1;
908 ExitAndWakeUpAppropriateWaiters();
912 /// A routine for lazily creating a event outside the lock (so if errors
913 /// happen they are outside the lock and that we don't do much work
914 /// while holding a spin lock). If all goes well, reenter the lock and
917 private void LazyCreateEvent([NotNull
] ref EventWaitHandle
? waitEvent
, EnterLockType enterLockType
)
920 Debug
.Assert(_spinLock
.IsHeld
);
921 Debug
.Assert(waitEvent
== null);
929 enterLockType
== EnterLockType
.Read
? EventResetMode
.ManualReset
: EventResetMode
.AutoReset
);
931 EnterSpinLockReason enterMyLockReason
;
932 switch (enterLockType
)
934 case EnterLockType
.Read
:
935 case EnterLockType
.UpgradeableRead
:
936 enterMyLockReason
= EnterSpinLockReason
.EnterAnyRead
| EnterSpinLockReason
.Wait
;
939 case EnterLockType
.Write
:
940 enterMyLockReason
= EnterSpinLockReason
.EnterWrite
| EnterSpinLockReason
.Wait
;
944 Debug
.Assert(enterLockType
== EnterLockType
.UpgradeToWrite
);
945 enterMyLockReason
= EnterSpinLockReason
.UpgradeToWrite
| EnterSpinLockReason
.Wait
;
948 _spinLock
.Enter(enterMyLockReason
);
950 if (waitEvent
== null) // maybe someone snuck in.
951 waitEvent
= newEvent
;
957 /// Waits on 'waitEvent' with a timeout
958 /// Before the wait 'numWaiters' is incremented and is restored before leaving this routine.
960 private bool WaitOnEvent(
961 EventWaitHandle waitEvent
,
963 TimeoutTracker timeout
,
964 EnterLockType enterLockType
)
967 Debug
.Assert(_spinLock
.IsHeld
);
970 WaiterStates waiterSignaledState
= WaiterStates
.None
;
971 EnterSpinLockReason enterMyLockReason
;
972 switch (enterLockType
)
974 case EnterLockType
.UpgradeableRead
:
975 waiterSignaledState
= WaiterStates
.UpgradeableReadWaiterSignaled
;
976 goto case EnterLockType
.Read
;
978 case EnterLockType
.Read
:
979 enterMyLockReason
= EnterSpinLockReason
.EnterAnyRead
;
982 case EnterLockType
.Write
:
983 waiterSignaledState
= WaiterStates
.WriteWaiterSignaled
;
984 enterMyLockReason
= EnterSpinLockReason
.EnterWrite
;
988 Debug
.Assert(enterLockType
== EnterLockType
.UpgradeToWrite
);
989 enterMyLockReason
= EnterSpinLockReason
.UpgradeToWrite
;
993 // It was not possible to acquire the RW lock because some other thread was holding some type of lock. The other
994 // thread, when it releases its lock, will wake appropriate waiters. Along with resetting the wait event, clear the
995 // waiter signaled bit for this type of waiter if applicable, to indicate that a waiter of this type is no longer
998 // If the waiter signaled bit is not updated upon event reset, the following scenario would lead to deadlock:
999 // - Thread T0 signals the write waiter event or the upgradeable read waiter event to wake a waiter
1000 // - There are no threads waiting on the event, but T1 is in WaitOnEvent() after exiting the spin lock and before
1001 // actually waiting on the event (that is, it's recorded that there is one waiter for the event). It remains in
1002 // this region for a while, in the repro case it typically gets context-switched out.
1003 // - T2 acquires the RW lock in some fashion that blocks T0 or T3 from acquiring the RW lock
1004 // - T0 or T3 fails to acquire the RW lock enough times for it to enter WaitOnEvent for the same event as T1
1005 // - T0 or T3 resets the event
1006 // - T2 releases the RW lock and does not wake a waiter because the reset at the previous step lost a signal but
1007 // _waiterStates was not updated to reflect that
1008 // - T1 and other threads begin waiting on the event, but there's no longer any thread that would wake them
1009 if (waiterSignaledState
!= WaiterStates
.None
&& (_waiterStates
& waiterSignaledState
) != WaiterStates
.None
)
1011 _waiterStates
&= ~waiterSignaledState
;
1016 HasNoWaiters
= false;
1018 //Setting these bits will prevent new readers from getting in.
1019 if (_numWriteWaiters
== 1)
1020 SetWritersWaiting();
1021 if (_numWriteUpgradeWaiters
== 1)
1022 SetUpgraderWaiting();
1024 bool waitSuccessful
= false;
1025 _spinLock
.Exit(); // Do the wait outside of any lock
1029 waitSuccessful
= waitEvent
.WaitOne(timeout
.RemainingMilliseconds
);
1033 _spinLock
.Enter(enterMyLockReason
);
1037 if (waitSuccessful
&&
1038 waiterSignaledState
!= WaiterStates
.None
&&
1039 (_waiterStates
& waiterSignaledState
) != WaiterStates
.None
)
1041 // Indicate that a signaled waiter of this type has woken. Since non-read waiters are signaled to wake one
1042 // at a time, we avoid waking up more than one waiter of that type upon successive enter/exit loops until
1043 // the signaled thread actually wakes up. For example, if there are multiple write waiters and one thread is
1044 // repeatedly entering and exiting a write lock, every exit would otherwise signal a different write waiter
1045 // to wake up unnecessarily when only one woken waiter may actually succeed in entering the write lock.
1046 _waiterStates
&= ~waiterSignaledState
;
1049 if (_numWriteWaiters
== 0 && _numWriteUpgradeWaiters
== 0 && _numUpgradeWaiters
== 0 && _numReadWaiters
== 0)
1050 HasNoWaiters
= true;
1052 if (_numWriteWaiters
== 0)
1053 ClearWritersWaiting();
1054 if (_numWriteUpgradeWaiters
== 0)
1055 ClearUpgraderWaiting();
1057 if (!waitSuccessful
) // We may also be about to throw for some reason. Exit myLock.
1059 if (enterLockType
>= EnterLockType
.Write
)
1061 // Write waiters block read waiters from acquiring the lock. Since this was the last write waiter, try
1062 // to wake up the appropriate read waiters.
1063 ExitAndWakeUpAppropriateReadWaiters();
1071 return waitSuccessful
;
1075 /// Determines the appropriate events to set, leaves the locks, and sets the events.
1077 private void ExitAndWakeUpAppropriateWaiters()
1080 Debug
.Assert(_spinLock
.IsHeld
);
1088 ExitAndWakeUpAppropriateWaitersPreferringWriters();
1091 private void ExitAndWakeUpAppropriateWaitersPreferringWriters()
1093 uint readercount
= GetNumReaders();
1095 //We need this case for EU->ER->EW case, as the read count will be 2 in
1099 if (_numWriteUpgradeWaiters
> 0 && _fUpgradeThreadHoldingRead
&& readercount
== 2)
1101 _spinLock
.Exit(); // Exit before signaling to improve efficiency (wakee will need the lock)
1102 _waitUpgradeEvent
!.Set(); // release all upgraders (however there can be at most one). Known non-null because _numWriteUpgradeWaiters > 0.
1107 if (readercount
== 1 && _numWriteUpgradeWaiters
> 0)
1109 //We have to be careful now, as we are dropping the lock.
1110 //No new writes should be allowed to sneak in if an upgrade
1113 _spinLock
.Exit(); // Exit before signaling to improve efficiency (wakee will need the lock)
1114 _waitUpgradeEvent
!.Set(); // release all upgraders (however there can be at most one). Known non-null because _numWriteUpgradeWaiters > 0.
1116 else if (readercount
== 0 && _numWriteWaiters
> 0)
1118 // Check if a waiter of the same type has already been signaled but hasn't woken yet. If so, avoid signaling
1119 // and waking another waiter unnecessarily.
1120 WaiterStates signaled
= _waiterStates
& WaiterStates
.WriteWaiterSignaled
;
1121 if (signaled
== WaiterStates
.None
)
1123 _waiterStates
|= WaiterStates
.WriteWaiterSignaled
;
1126 _spinLock
.Exit(); // Exit before signaling to improve efficiency (wakee will need the lock)
1128 if (signaled
== WaiterStates
.None
)
1130 _writeEvent
!.Set(); // release one writer. Known non-null because _numWriteWaiters > 0.
1135 ExitAndWakeUpAppropriateReadWaiters();
1139 private void ExitAndWakeUpAppropriateReadWaiters()
1142 Debug
.Assert(_spinLock
.IsHeld
);
1145 if (_numWriteWaiters
!= 0 || _numWriteUpgradeWaiters
!= 0 || HasNoWaiters
)
1151 Debug
.Assert(_numReadWaiters
!= 0 || _numUpgradeWaiters
!= 0);
1153 bool setReadEvent
= _numReadWaiters
!= 0;
1154 bool setUpgradeEvent
= _numUpgradeWaiters
!= 0 && _upgradeLockOwnerId
== -1;
1155 if (setUpgradeEvent
)
1157 // Check if a waiter of the same type has already been signaled but hasn't woken yet. If so, avoid signaling
1158 // and waking another waiter unnecessarily.
1159 if ((_waiterStates
& WaiterStates
.UpgradeableReadWaiterSignaled
) == WaiterStates
.None
)
1161 _waiterStates
|= WaiterStates
.UpgradeableReadWaiterSignaled
;
1165 setUpgradeEvent
= false;
1169 _spinLock
.Exit(); // Exit before signaling to improve efficiency (wakee will need the lock)
1172 _readEvent
!.Set(); // release all readers. Known non-null because _numUpgradeWaiters != 0.
1174 if (setUpgradeEvent
)
1175 _upgradeEvent
!.Set(); //release one upgrader.
1178 private bool IsWriterAcquired()
1180 return (_owners
& ~WAITING_WRITERS
) == 0;
1183 private void SetWriterAcquired()
1185 _owners
|= WRITER_HELD
; // indicate we have a writer.
1188 private void ClearWriterAcquired()
1190 _owners
&= ~WRITER_HELD
;
1193 private void SetWritersWaiting()
1195 _owners
|= WAITING_WRITERS
;
1198 private void ClearWritersWaiting()
1200 _owners
&= ~WAITING_WRITERS
;
1203 private void SetUpgraderWaiting()
1205 _owners
|= WAITING_UPGRADER
;
1208 private void ClearUpgraderWaiting()
1210 _owners
&= ~WAITING_UPGRADER
;
1213 private uint GetNumReaders()
1215 return _owners
& READER_MASK
;
1218 private bool ShouldSpinForEnterAnyRead()
1220 // If there is a write waiter or write upgrade waiter, the waiter would block a reader from acquiring the RW lock
1221 // because the waiter takes precedence. In that case, the reader is not likely to make progress by spinning.
1222 // Although another thread holding a write lock would prevent this thread from acquiring a read lock, it is by
1223 // itself not a good enough reason to skip spinning.
1224 return HasNoWaiters
|| (_numWriteWaiters
== 0 && _numWriteUpgradeWaiters
== 0);
1227 private bool ShouldSpinForEnterAnyWrite(bool isUpgradeToWrite
)
1229 // If there is a write upgrade waiter, the waiter would block a writer from acquiring the RW lock because the waiter
1230 // holds a read lock. In that case, the writer is not likely to make progress by spinning. Regarding upgrading to a
1231 // write lock, there is no type of waiter that would block the upgrade from happening. Although another thread
1232 // holding a read or write lock would prevent this thread from acquiring the write lock, it is by itself not a good
1233 // enough reason to skip spinning.
1234 return isUpgradeToWrite
|| _numWriteUpgradeWaiters
== 0;
1237 private static void SpinWait(int spinCount
)
1239 const int LockSpinCycles
= 20;
1241 //Exponential back-off
1242 if ((spinCount
< 5) && (ProcessorCount
> 1))
1244 Thread
.SpinWait(LockSpinCycles
* spinCount
);
1251 // Don't want to Sleep(1) in this spin wait:
1252 // - Don't want to spin for that long, since a proper wait will follow when the spin wait fails. The artificial
1253 // delay introduced by Sleep(1) will in some cases be much longer than desired.
1254 // - Sleep(1) would put the thread into a wait state, and a proper wait will follow when the spin wait fails
1255 // anyway, so it's preferable to put the thread into the proper wait state
1258 public void Dispose()
1263 private void Dispose(bool disposing
)
1265 if (disposing
&& !_fDisposed
)
1267 if (WaitingReadCount
> 0 || WaitingUpgradeCount
> 0 || WaitingWriteCount
> 0)
1268 throw new SynchronizationLockException(SR
.SynchronizationLockException_IncorrectDispose
);
1270 if (IsReadLockHeld
|| IsUpgradeableReadLockHeld
|| IsWriteLockHeld
)
1271 throw new SynchronizationLockException(SR
.SynchronizationLockException_IncorrectDispose
);
1273 if (_writeEvent
!= null)
1275 _writeEvent
.Dispose();
1279 if (_readEvent
!= null)
1281 _readEvent
.Dispose();
1285 if (_upgradeEvent
!= null)
1287 _upgradeEvent
.Dispose();
1288 _upgradeEvent
= null;
1291 if (_waitUpgradeEvent
!= null)
1293 _waitUpgradeEvent
.Dispose();
1294 _waitUpgradeEvent
= null;
1301 public bool IsReadLockHeld
1305 if (RecursiveReadCount
> 0)
1312 public bool IsUpgradeableReadLockHeld
1316 if (RecursiveUpgradeCount
> 0)
1323 public bool IsWriteLockHeld
1327 if (RecursiveWriteCount
> 0)
1334 public LockRecursionPolicy RecursionPolicy
1340 return LockRecursionPolicy
.SupportsRecursion
;
1344 return LockRecursionPolicy
.NoRecursion
;
1349 public int CurrentReadCount
1353 int numreaders
= (int)GetNumReaders();
1355 if (_upgradeLockOwnerId
!= -1)
1356 return numreaders
- 1;
1363 public int RecursiveReadCount
1368 ReaderWriterCount
? lrwc
= GetThreadRWCount(dontAllocate
: true);
1370 count
= lrwc
.readercount
;
1376 public int RecursiveUpgradeCount
1384 ReaderWriterCount
? lrwc
= GetThreadRWCount(dontAllocate
: true);
1386 count
= lrwc
.upgradecount
;
1392 if (Environment
.CurrentManagedThreadId
== _upgradeLockOwnerId
)
1400 public int RecursiveWriteCount
1408 ReaderWriterCount
? lrwc
= GetThreadRWCount(dontAllocate
: true);
1410 count
= lrwc
.writercount
;
1416 if (Environment
.CurrentManagedThreadId
== _writeLockOwnerId
)
1424 public int WaitingReadCount
1428 return (int)_numReadWaiters
;
1432 public int WaitingUpgradeCount
1436 return (int)_numUpgradeWaiters
;
1440 public int WaitingWriteCount
1444 return (int)_numWriteWaiters
;
1448 private struct SpinLock
1450 private int _isLocked
;
1453 /// Used to deprioritize threads attempting to enter the lock when they would not make progress after doing so.
1454 /// <see cref="EnterSpin(EnterSpinLockReason)"/> avoids acquiring the lock as long as the operation for which it
1455 /// was called is deprioritized.
1458 /// - Low 16 bits: Number of threads that have deprioritized an enter-any-write operation
1459 /// - High 16 bits: Number of threads that have deprioritized an enter-any-read operation
1461 private int _enterDeprioritizationState
;
1463 // Layout-specific constants for _enterDeprioritizationState
1464 private const int DeprioritizeEnterAnyReadIncrement
= 1 << 16;
1465 private const int DeprioritizeEnterAnyWriteIncrement
= 1;
1467 // The variables controlling spinning behavior of this spin lock
1468 private const int LockSpinCycles
= 20;
1469 private const int LockSpinCount
= 10;
1470 private const int LockSleep0Count
= 5;
1471 private const int DeprioritizedLockSleep1Count
= 5;
1473 private static int GetEnterDeprioritizationStateChange(EnterSpinLockReason reason
)
1475 EnterSpinLockReason operation
= reason
& EnterSpinLockReason
.OperationMask
;
1478 case EnterSpinLockReason
.EnterAnyRead
:
1481 case EnterSpinLockReason
.ExitAnyRead
:
1482 // A read lock is held until this thread is able to exit it, so deprioritize enter-write threads as they
1483 // will not be able to make progress
1484 return DeprioritizeEnterAnyWriteIncrement
;
1486 case EnterSpinLockReason
.EnterWrite
:
1487 // Writers are typically much less frequent and much less in number than readers. Waiting writers take
1488 // precedence over new read attempts in order to let current readers release their lock and allow a
1489 // writer to obtain the lock. Before a writer can register as a waiter though, the presence of just
1490 // relatively few enter-read spins can easily starve the enter-write from even entering this lock,
1491 // delaying its spin loop for an unreasonable duration.
1493 // Deprioritize enter-read to preference enter-write. This makes it easier for enter-write threads to
1494 // starve enter-read threads. However, writers can already by design starve readers. A waiting writer
1495 // blocks enter-read threads and a new enter-write that needs to wait will be given precedence over
1496 // previously waiting enter-read threads. So this is not a new problem, and the RW lock is designed for
1497 // scenarios where writers are rare compared to readers.
1498 return DeprioritizeEnterAnyReadIncrement
;
1502 operation
== EnterSpinLockReason
.UpgradeToWrite
||
1503 operation
== EnterSpinLockReason
.EnterRecursiveWrite
||
1504 operation
== EnterSpinLockReason
.ExitAnyWrite
);
1507 // - A read lock is held and an exit-read is not nearby, so deprioritize enter-write threads as they
1508 // will not be able to make progress. This thread also intends to enter a write lock, so deprioritize
1509 // enter -read threads as well, see case EnterSpinLockReason.EnterWrite for the rationale.
1510 // EnterRecursiveWrite, ExitAnyWrite:
1511 // - In both cases, a write lock is held until this thread is able to exit it, so deprioritize
1512 // enter -read and enter-write threads as they will not be able to make progress
1513 return DeprioritizeEnterAnyReadIncrement
+ DeprioritizeEnterAnyWriteIncrement
;
1517 private ushort EnterForEnterAnyReadDeprioritizedCount
1521 Debug
.Assert(DeprioritizeEnterAnyReadIncrement
== (1 << 16));
1522 return (ushort)((uint)_enterDeprioritizationState
>> 16);
1526 private ushort EnterForEnterAnyWriteDeprioritizedCount
1530 Debug
.Assert(DeprioritizeEnterAnyWriteIncrement
== 1);
1531 return (ushort)_enterDeprioritizationState
;
1535 private bool IsEnterDeprioritized(EnterSpinLockReason reason
)
1537 Debug
.Assert((reason
& EnterSpinLockReason
.Wait
) != 0 || reason
== (reason
& EnterSpinLockReason
.OperationMask
));
1539 (reason
& EnterSpinLockReason
.Wait
) == 0 ||
1540 (reason
& EnterSpinLockReason
.OperationMask
) == EnterSpinLockReason
.EnterAnyRead
||
1541 (reason
& EnterSpinLockReason
.OperationMask
) == EnterSpinLockReason
.EnterWrite
||
1542 (reason
& EnterSpinLockReason
.OperationMask
) == EnterSpinLockReason
.UpgradeToWrite
);
1548 (reason
& EnterSpinLockReason
.Wait
) != 0 ||
1549 reason
== EnterSpinLockReason
.ExitAnyRead
||
1550 reason
== EnterSpinLockReason
.EnterRecursiveWrite
||
1551 reason
== EnterSpinLockReason
.ExitAnyWrite
);
1554 case EnterSpinLockReason
.EnterAnyRead
:
1555 return EnterForEnterAnyReadDeprioritizedCount
!= 0;
1557 case EnterSpinLockReason
.EnterWrite
:
1558 Debug
.Assert((GetEnterDeprioritizationStateChange(reason
) & DeprioritizeEnterAnyWriteIncrement
) == 0);
1559 return EnterForEnterAnyWriteDeprioritizedCount
!= 0;
1561 case EnterSpinLockReason
.UpgradeToWrite
:
1562 Debug
.Assert((GetEnterDeprioritizationStateChange(reason
) & DeprioritizeEnterAnyWriteIncrement
) != 0);
1563 return EnterForEnterAnyWriteDeprioritizedCount
> 1;
1567 [MethodImpl(MethodImplOptions
.AggressiveInlining
)]
1568 private bool TryEnter()
1570 return Interlocked
.CompareExchange(ref _isLocked
, 1, 0) == 0;
1573 [MethodImpl(MethodImplOptions
.AggressiveInlining
)]
1574 public void Enter(EnterSpinLockReason reason
)
1582 private void EnterSpin(EnterSpinLockReason reason
)
1584 int deprioritizationStateChange
= GetEnterDeprioritizationStateChange(reason
);
1585 if (deprioritizationStateChange
!= 0)
1587 Interlocked
.Add(ref _enterDeprioritizationState
, deprioritizationStateChange
);
1590 int processorCount
= ProcessorCount
;
1591 for (int spinIndex
= 0; ; spinIndex
++)
1593 if (spinIndex
< LockSpinCount
&& processorCount
> 1)
1595 Thread
.SpinWait(LockSpinCycles
* (spinIndex
+ 1)); // Wait a few dozen instructions to let another processor release lock.
1597 else if (spinIndex
< (LockSpinCount
+ LockSleep0Count
))
1599 Thread
.Sleep(0); // Give up my quantum.
1603 Thread
.Sleep(1); // Give up my quantum.
1606 if (!IsEnterDeprioritized(reason
))
1608 if (_isLocked
== 0 && TryEnter())
1610 if (deprioritizationStateChange
!= 0)
1612 Interlocked
.Add(ref _enterDeprioritizationState
, -deprioritizationStateChange
);
1619 // It's possible for an Enter thread to be deprioritized for an extended duration. It's undesirable for a
1620 // deprioritized thread to keep waking up to spin despite a Sleep(1) when a large number of such threads are
1621 // involved. After a threshold of Sleep(1)s, ignore the deprioritization and enter this lock to allow this
1622 // thread to stop spinning and hopefully enter a proper wait state.
1624 reason
== EnterSpinLockReason
.EnterAnyRead
||
1625 reason
== EnterSpinLockReason
.EnterWrite
||
1626 reason
== EnterSpinLockReason
.UpgradeToWrite
);
1627 if (spinIndex
>= (LockSpinCount
+ LockSleep0Count
+ DeprioritizedLockSleep1Count
))
1629 reason
|= EnterSpinLockReason
.Wait
;
1637 Debug
.Assert(_isLocked
!= 0, "Exiting spin lock that is not held");
1638 Volatile
.Write(ref _isLocked
, 0);
1642 public bool IsHeld
=> _isLocked
!= 0;
1647 private enum WaiterStates
: byte
1651 // Used for quick check when there are no waiters
1654 // Used to avoid signaling more than one waiter to wake up when only one can make progress, see WaitOnEvent
1655 WriteWaiterSignaled
= 0x2,
1656 UpgradeableReadWaiterSignaled
= 0x4
1657 // Write upgrade waiters are excluded because there can only be one at any given time
1660 private enum EnterSpinLockReason
1666 EnterRecursiveWrite
= 4,
1669 OperationMask
= 0x7,
1674 private enum EnterLockType