Code:
/ DotNET / DotNET / 8.0 / untmp / whidbey / REDBITS / ndp / fx / src / xsp / System / Web / Util / ReadWriteSpinLock.cs / 1 / ReadWriteSpinLock.cs
//------------------------------------------------------------------------------ //// Copyright (c) Microsoft Corporation. All rights reserved. // //----------------------------------------------------------------------------- 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; } ///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.
Link Menu
This book is available now!
Buy at Amazon US or
Buy at Amazon UK
- EnvironmentPermission.cs
- KeyedHashAlgorithm.cs
- SrgsItemList.cs
- EntityDataSourceWrapperPropertyDescriptor.cs
- LogManagementAsyncResult.cs
- XmlReaderDelegator.cs
- NoResizeHandleGlyph.cs
- XmlC14NWriter.cs
- SqlUdtInfo.cs
- WebPartsPersonalizationAuthorization.cs
- KnownAssemblyEntry.cs
- PropertyChangeTracker.cs
- MetadataHelper.cs
- IgnoreSection.cs
- ClientOptions.cs
- HostProtectionException.cs
- URLMembershipCondition.cs
- MsmqMessageProperty.cs
- Point3D.cs
- Substitution.cs
- XmlSchemaCollection.cs
- BuiltInExpr.cs
- ListView.cs
- CornerRadius.cs
- RelationshipNavigation.cs
- SwitchElementsCollection.cs
- DeobfuscatingStream.cs
- UnsignedPublishLicense.cs
- GridViewSelectEventArgs.cs
- InternalTransaction.cs
- PeerContact.cs
- HttpStreamMessage.cs
- NetworkAddressChange.cs
- XmlSchemaAll.cs
- PackagePartCollection.cs
- HtmlInputText.cs
- AuthorizationContext.cs
- DigitShape.cs
- PageRouteHandler.cs
- StaticResourceExtension.cs
- DataPagerField.cs
- NativeCompoundFileAPIs.cs
- Convert.cs
- DbQueryCommandTree.cs
- ZoneMembershipCondition.cs
- TokenizerHelper.cs
- ConfigXmlDocument.cs
- DocumentReferenceCollection.cs
- ModelServiceImpl.cs
- MinimizableAttributeTypeConverter.cs
- ValidateNames.cs
- DecimalAnimation.cs
- PageContentCollection.cs
- OLEDB_Enum.cs
- ResourcePart.cs
- MailMessage.cs
- Model3DCollection.cs
- FilteredAttributeCollection.cs
- X509AsymmetricSecurityKey.cs
- HtmlString.cs
- Stackframe.cs
- DependencyPropertyKind.cs
- TimerElapsedEvenArgs.cs
- InvalidDataException.cs
- SecurityListenerSettingsLifetimeManager.cs
- safelink.cs
- ToolbarAUtomationPeer.cs
- ColumnResult.cs
- InternalDispatchObject.cs
- MsmqIntegrationInputMessage.cs
- InputProcessorProfiles.cs
- hwndwrapper.cs
- Attributes.cs
- FrameworkTemplate.cs
- TakeQueryOptionExpression.cs
- BinaryHeap.cs
- EntityDesignerBuildProvider.cs
- Window.cs
- ServiceBuildProvider.cs
- Maps.cs
- PanelDesigner.cs
- ToolStripComboBox.cs
- TextTreeRootTextBlock.cs
- X509CertificateChain.cs
- SqlUtils.cs
- ModelUtilities.cs
- XmlSchemaSequence.cs
- TcpChannelFactory.cs
- ContravarianceAdapter.cs
- PopupRoot.cs
- NumberAction.cs
- DynamicActivityProperty.cs
- ZoneMembershipCondition.cs
- CategoriesDocument.cs
- SqlClientWrapperSmiStream.cs
- BuilderElements.cs
- Pair.cs
- SaveFileDialogDesigner.cs
- RuntimeCompatibilityAttribute.cs
- RichTextBox.cs