mirror of
https://github.com/BepInEx/mono.git
synced 2026-11-19 01:31:17 -10:00
Adding reference source for System.Data System.Data.DataSetExtensions System.Data.Entity System.Data.Entity.Design System.Data.Linq System.Data.SqlXml System.ServiceModel System.ServiceModel.Activation System.ServiceModel.Activities System.ServiceModel.Channels System.ServiceModel.Discovery System.ServiceModel.Internals System.ServiceModel.Routing System.ServiceModel.WasHosting System.ServiceModel.Web System.Web System.Web.ApplicationServices System.Web.DynamicData System.Web.Entity System.Web.Entity.Design System.Web.Extensions System.Web.Mobile System.Web.Routing System.Web.Services System.Xml System.Xml.Linq
382 lines
14 KiB
C#
382 lines
14 KiB
C#
//------------------------------------------------------------------------------
|
|
// <copyright file="ReadWriteSpinLock.cs" company="Microsoft">
|
|
// Copyright (c) Microsoft Corporation. All rights reserved.
|
|
// </copyright>
|
|
//------------------------------------------------------------------------------
|
|
|
|
|
|
namespace System.Web.Util {
|
|
|
|
using System.Threading;
|
|
using System.Collections;
|
|
using System.Globalization;
|
|
using Microsoft.Win32;
|
|
|
|
struct ReadWriteSpinLock {
|
|
//
|
|
// Fields
|
|
//
|
|
|
|
// _bits is layed out as follows:
|
|
//
|
|
// 3 3 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1
|
|
// 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0
|
|
// +-+-+---------------------------+--------------------------------+
|
|
// |S|W| WriteLockCount | ReadLockCount |
|
|
// +-+-+---------------------------+--------------------------------+
|
|
// where
|
|
//
|
|
// S - sign bit (always zero) - By having a sign bit, operations
|
|
// on the ReadLockCount can use InterlockedIncrement/Decrement
|
|
//
|
|
// W - writer waiting bit - set by threads attempting write lock, preventing
|
|
// any further threads from acquiring read locks. This attempts to hint
|
|
// that updates have priority, but doesn't guarantee priority.
|
|
//
|
|
// WriteLockCount - Write lock recursion count
|
|
//
|
|
// ReadLockCount - Read lock recursion count
|
|
//
|
|
int _bits;
|
|
int _id;
|
|
|
|
//
|
|
// Statics
|
|
//
|
|
|
|
static bool s_disableBusyWaiting = (SystemInfo.GetNumProcessCPUs() == 1);
|
|
|
|
//
|
|
// Constants
|
|
//
|
|
|
|
const int BACK_OFF_FACTORS_LENGTH = 13;
|
|
static readonly double [] s_backOffFactors = new double [BACK_OFF_FACTORS_LENGTH] {
|
|
1.020, 0.965, 0.890, 1.065,
|
|
1.025, 1.115, 0.940, 0.995,
|
|
1.050, 1.080, 0.915, 0.980,
|
|
1.010
|
|
};
|
|
|
|
const int WRITER_WAITING_MASK = (int) 0x40000000;
|
|
const int WRITE_COUNT_MASK = (int) 0x3FFF0000;
|
|
const int READ_COUNT_MASK = (int) 0x0000FFFF;
|
|
const int WRITER_WAITING_SHIFT = 30;
|
|
const int WRITE_COUNT_SHIFT = 16;
|
|
|
|
static bool WriterWaiting(int bits) {return ((bits & WRITER_WAITING_MASK) != 0);}
|
|
static int WriteLockCount(int bits) {return ((bits & WRITE_COUNT_MASK) >> WRITE_COUNT_SHIFT);}
|
|
static int ReadLockCount(int bits) {return (bits & READ_COUNT_MASK);}
|
|
static bool NoWriters(int bits) {return ((bits & WRITE_COUNT_MASK) == 0);}
|
|
static bool NoWritersOrWaitingWriters(int bits) {return ((bits & (WRITE_COUNT_MASK | WRITER_WAITING_MASK)) == 0);}
|
|
static bool NoLocks(int bits) {return ((bits & ~WRITER_WAITING_MASK) == 0);}
|
|
|
|
bool WriterWaiting() {return WriterWaiting(_bits);}
|
|
int WriteLockCount() {return WriteLockCount(_bits);}
|
|
int ReadLockCount() {return ReadLockCount(_bits);}
|
|
bool NoWriters() {return NoWriters(_bits);}
|
|
bool NoWritersOrWaitingWriters() {return NoWritersOrWaitingWriters(_bits);}
|
|
bool NoLocks() {return NoLocks(_bits);}
|
|
|
|
int CreateNewBits(bool writerWaiting, int writeCount, int readCount) {
|
|
int bits = ((writeCount << WRITE_COUNT_SHIFT) | readCount);
|
|
if (writerWaiting) {
|
|
bits |= WRITER_WAITING_MASK;
|
|
}
|
|
|
|
return bits;
|
|
}
|
|
|
|
|
|
internal /*public*/ void AcquireReaderLock() {
|
|
|
|
// This lock supports Writelock then Readlock
|
|
// from the same thread (possibly from different functions).
|
|
int threadId = Thread.CurrentThread.GetHashCode();
|
|
|
|
// Optimize for the common case by
|
|
if (_TryAcquireReaderLock(threadId))
|
|
return;
|
|
|
|
_Spin(true, threadId);
|
|
Debug.Trace("Spinlock", "AcquireReaderLock: _bits=" + _bits.ToString("x8", CultureInfo.InvariantCulture)
|
|
+ " _id= " + _id.ToString("x8", CultureInfo.InvariantCulture));
|
|
}
|
|
|
|
|
|
internal /*public*/ void AcquireWriterLock() {
|
|
|
|
int threadId = Thread.CurrentThread.GetHashCode();
|
|
|
|
// Optimize for the common case by
|
|
if (_TryAcquireWriterLock(threadId))
|
|
return;
|
|
|
|
_Spin(false, threadId);
|
|
|
|
Debug.Trace("Spinlock", "AcquireWriterLock: _bits=" + _bits.ToString("x8", CultureInfo.InvariantCulture)
|
|
+ " _id= " + _id.ToString("x8", CultureInfo.InvariantCulture));
|
|
}
|
|
|
|
|
|
internal /*public*/ void ReleaseReaderLock() {
|
|
#if DBG
|
|
int id = _id;
|
|
Debug.Assert(id == 0 || id == Thread.CurrentThread.GetHashCode(), "id == 0 || id == Thread.CurrentThread.GetHashCode()");
|
|
#endif
|
|
|
|
int n = Interlocked.Decrement(ref _bits);
|
|
|
|
Debug.Assert(n >= 0, "n >= 0");
|
|
Debug.Trace("Spinlock", "ReleaseReaderLock: _bits=" + _bits.ToString("x8", CultureInfo.InvariantCulture)
|
|
+ " _id= " + _id.ToString("x8", CultureInfo.InvariantCulture));
|
|
}
|
|
|
|
|
|
void AlterWriteCountHoldingWriterLock(int oldBits, int delta) {
|
|
int readLockCount = ReadLockCount(oldBits);
|
|
int oldWriteLockCount = WriteLockCount(oldBits);
|
|
int newWriteLockCount = oldWriteLockCount + delta;
|
|
Debug.Assert(newWriteLockCount >= 0, "newWriteLockCount >= 0");
|
|
int newBits;
|
|
int test;
|
|
|
|
for (;;) {
|
|
//
|
|
// Since we own the lock, the only change that can be
|
|
// made by another thread to _bits is to add the writer-waiting bit.
|
|
//
|
|
Debug.Assert(WriteLockCount(oldBits) == oldWriteLockCount, "WriteLockCount(oldBits) == oldWriteLockCount");
|
|
Debug.Assert(ReadLockCount(oldBits) == readLockCount, "ReadLockCount(oldBits) == readLockCount");
|
|
newBits = CreateNewBits(WriterWaiting(oldBits), newWriteLockCount, readLockCount);
|
|
test = Interlocked.CompareExchange(ref _bits, newBits, oldBits);
|
|
if (test == oldBits) {
|
|
break;
|
|
}
|
|
|
|
oldBits = test;
|
|
}
|
|
}
|
|
|
|
internal /*public*/ void ReleaseWriterLock() {
|
|
#if DBG
|
|
int id = _id;
|
|
Debug.Assert(id == Thread.CurrentThread.GetHashCode(), "id == Thread.CurrentThread.GetHashCode()");
|
|
#endif
|
|
|
|
int oldBits = _bits;
|
|
int writeLockCount = WriteLockCount(oldBits);
|
|
Debug.Assert(writeLockCount > 0, "writeLockCount > 0");
|
|
if (writeLockCount == 1) {
|
|
// Reset the id before releasing count so that
|
|
// AcquireRead works correctly.
|
|
_id = 0;
|
|
}
|
|
|
|
AlterWriteCountHoldingWriterLock(oldBits, -1);
|
|
Debug.Trace("Spinlock", "ReleaseWriterLock: _bits=" + _bits.ToString("x8", CultureInfo.InvariantCulture)
|
|
+ " _id= " + _id.ToString("x8", CultureInfo.InvariantCulture));
|
|
}
|
|
|
|
|
|
bool _TryAcquireWriterLock(int threadId) {
|
|
int id = _id;
|
|
int oldBits = _bits;
|
|
int newBits;
|
|
int test;
|
|
|
|
if (id == threadId) {
|
|
// we can just pound in the correct value
|
|
AlterWriteCountHoldingWriterLock(oldBits, +1);
|
|
return true;
|
|
}
|
|
|
|
if (id == 0 && NoLocks(oldBits)) {
|
|
newBits = CreateNewBits(false, 1, 0);
|
|
test = Interlocked.CompareExchange(ref _bits, newBits, oldBits);
|
|
if (test == oldBits) {
|
|
id = _id;
|
|
Debug.Assert(id == 0);
|
|
_id = threadId;
|
|
|
|
return true;
|
|
}
|
|
|
|
oldBits = test;
|
|
}
|
|
|
|
// If there is contention, make sure the WRITER_WAITING bit is set.
|
|
// Note: this blocks readers from using a value that is about to be changed
|
|
if (!WriterWaiting(oldBits)) {
|
|
// hammer on _bits until the bit is set
|
|
for (;;) {
|
|
newBits = (oldBits | WRITER_WAITING_MASK);
|
|
test = Interlocked.CompareExchange(ref _bits, newBits, oldBits);
|
|
if (test == oldBits)
|
|
break;
|
|
|
|
oldBits = test;
|
|
}
|
|
}
|
|
|
|
return false;
|
|
}
|
|
|
|
bool _TryAcquireReaderLock(int threadId) {
|
|
int oldBits = _bits;
|
|
int id = _id;
|
|
|
|
if (id == 0) {
|
|
if (!NoWriters(oldBits)) {
|
|
return false;
|
|
}
|
|
}
|
|
else if (id != threadId) {
|
|
return false;
|
|
}
|
|
|
|
if (Interlocked.CompareExchange(ref _bits, oldBits + 1, oldBits) == oldBits) {
|
|
return true;
|
|
}
|
|
|
|
return false;
|
|
}
|
|
|
|
|
|
|
|
/// <internalonly/>
|
|
void _Spin(bool isReaderLock, int threadId) {
|
|
|
|
const int LOCK_MAXIMUM_SPINS = 10000; // maximum allowable spin count
|
|
const int LOCK_DEFAULT_SPINS = 4000; // default spin count
|
|
const int LOCK_MINIMUM_SPINS = 100; // minimum allowable spin count
|
|
|
|
int sleepTime = 0;
|
|
int baseSpins;
|
|
|
|
{ // limit scope of temp. stack vars to calculation of baseSpin2
|
|
|
|
// Alternatives for threadId include a static counter
|
|
// or the low DWORD of QueryPerformanceCounter().
|
|
double randomBackoffFactor = s_backOffFactors[Math.Abs(threadId) % BACK_OFF_FACTORS_LENGTH];
|
|
baseSpins = (int)(LOCK_DEFAULT_SPINS * randomBackoffFactor);
|
|
baseSpins = Math.Min(LOCK_MAXIMUM_SPINS, baseSpins);
|
|
baseSpins = Math.Max(baseSpins, LOCK_MINIMUM_SPINS);
|
|
}
|
|
|
|
DateTime utcSpinStartTime = DateTime.UtcNow; // error if struct not initialized
|
|
|
|
// hand-optimize loop: Increase locality by copying static variables
|
|
// onto the stack (this will reduce cache misses after a contact
|
|
// switch induced by Sleep()).
|
|
bool disableBusyWaiting = s_disableBusyWaiting;
|
|
|
|
for (;;) {
|
|
if (isReaderLock) {
|
|
if (_TryAcquireReaderLock(threadId)) {
|
|
break;
|
|
}
|
|
}
|
|
else {
|
|
if (_TryAcquireWriterLock(threadId)) {
|
|
break;
|
|
}
|
|
}
|
|
|
|
// if 1 cpu, or cpu affinity is set to 1, spinning is a waste of time
|
|
if (disableBusyWaiting) {
|
|
|
|
Thread.Sleep(sleepTime);
|
|
|
|
// Avoid priority inversion: 0, 1, 0, 1,...
|
|
sleepTime ^= 1;
|
|
}
|
|
else {
|
|
int spinCount = baseSpins;
|
|
|
|
// Check no more than baseSpins times then yield.
|
|
// It is important not to use the InterlockedExchange in the
|
|
// inner loop in order to minimize system memory bus traffic.
|
|
for(;;) {
|
|
//
|
|
// If the lock is available break spinning and
|
|
// try to obtain it.
|
|
//
|
|
if (isReaderLock) {
|
|
if (NoWritersOrWaitingWriters()) {
|
|
break;
|
|
}
|
|
}
|
|
else {
|
|
if (NoLocks()) {
|
|
break;
|
|
}
|
|
}
|
|
|
|
if (--spinCount < 0) {
|
|
|
|
Thread.Sleep(sleepTime);
|
|
|
|
// Backoff algorithm: reduce (or increase) busy wait time
|
|
baseSpins /= 2;
|
|
// LOCK_MINIMUM_SPINS <= baseSpins <= LOCK_MAXIMUM_SPINS
|
|
//baseSpins = Math.Min(LOCK_MAXIMUM_SPINS, baseSpins); //= min(LOCK_MAXIMUM_SPINS, baseSpins)
|
|
baseSpins = Math.Max(baseSpins, LOCK_MINIMUM_SPINS); //= max(baseSpins, LOCK_MINIMUM_SPINS);
|
|
spinCount = baseSpins;
|
|
|
|
// Using Sleep(0) leads to the possibility of priority
|
|
// inversion. Sleep(0) only yields the processor if
|
|
// there's another thread of the same priority that's
|
|
// ready to run. If a high-priority thread is trying to
|
|
// acquire the lock, which is held by a low-priority
|
|
// thread, then the low-priority thread may never get
|
|
// scheduled and hence never free the lock. NT attempts
|
|
// to avoid priority inversions by temporarily boosting
|
|
// the priority of low-priority runnable threads, but the
|
|
// problem can still occur if there's a medium-priority
|
|
// thread that's always runnable. If Sleep(1) is used,
|
|
// then the thread unconditionally yields the CPU. We
|
|
// only do this for the second and subsequent even
|
|
// iterations, since a millisecond is a long time to wait
|
|
// if the thread can be scheduled in again sooner
|
|
// (~100,000 instructions).
|
|
// Avoid priority inversion: 0, 1, 0, 1,...
|
|
sleepTime ^= 1;
|
|
}
|
|
else {
|
|
// kill about 20 clock cycles on this proc
|
|
Thread.SpinWait(10);
|
|
}
|
|
}
|
|
|
|
}
|
|
}// while
|
|
|
|
}// _Spin
|
|
|
|
} // ReadWriteSpinLock
|
|
|
|
} // namespace System.Web.Util
|
|
|
|
// NOTES:
|
|
//
|
|
// This ReaderWriterSpinlock is a combination of the
|
|
// original lightweight (4 byte) System.Web.Util.ReadWriteSpinLock
|
|
// and the lightweight (4 byte) exclusive lock (SmallSpinLock) used
|
|
// in the George Reilly's LKRHash (see http://georgere/work/lkrhash).
|
|
//
|
|
// In an effort to support reentrancy during writes we are squirreling
|
|
// away the thread id of the thread holding the write lock into the upper
|
|
// 16 bits of the lock count. This is possible as long as thread ids stay
|
|
// smaller than 7FFF. Anything higher than that would flip the sign bit
|
|
// and we'd no longer be able to do signed comparisons to check
|
|
// for read vs. write.
|
|
//
|
|
// read write
|
|
// lower #read locks #write locks (from same thread)
|
|
// higher 0x0000 thread id of thread holding lock
|
|
//
|
|
// Adapted from LKRHash's lock.cpp, from GeorgeRe
|
|
// The original implementation is due to PALarson.
|
|
|