Code:
/ 4.0 / 4.0 / untmp / DEVDIV_TFS / Dev10 / Releases / RTMRel / ndp / fx / src / tx / System / Transactions / TransactionTable.cs / 1305376 / TransactionTable.cs
//------------------------------------------------------------------------------ //// Copyright (c) Microsoft Corporation. All rights reserved. // //----------------------------------------------------------------------------- namespace System.Transactions { using System; using System.Diagnostics; using System.Threading; class CheapUnfairReaderWriterLock { object writerFinishedEvent; int readersIn; int readersOut; bool writerPresent; object syncRoot; // Spin lock params const int MAX_SPIN_COUNT = 100; const int SLEEP_TIME = 500; public CheapUnfairReaderWriterLock() { } object SyncRoot { get { if( this.syncRoot == null ) { Interlocked.CompareExchange( ref this.syncRoot, new object(), null ); } return this.syncRoot; } } bool ReadersPresent { get { return this.readersIn != this.readersOut; } } ManualResetEvent WriterFinishedEvent { get { if( this.writerFinishedEvent == null ) { Interlocked.CompareExchange( ref this.writerFinishedEvent, new ManualResetEvent( true ), null ); } return (ManualResetEvent)this.writerFinishedEvent; } } public int AcquireReaderLock() { int readerIndex = 0; do { if( this.writerPresent ) { WriterFinishedEvent.WaitOne(); } readerIndex = Interlocked.Increment( ref this.readersIn ); if( !this.writerPresent ) { break; } Interlocked.Decrement( ref this.readersIn ); } while( true ); return readerIndex; } public void AcquireWriterLock() { #pragma warning disable 0618 //@ Monitor.Enter(this.SyncRoot); #pragma warning restore 0618 this.writerPresent = true; this.WriterFinishedEvent.Reset(); do { int i = 0; while( ReadersPresent && i < MAX_SPIN_COUNT ) { Thread.Sleep( 0 ); i++; } if( ReadersPresent ) { Thread.Sleep( SLEEP_TIME ); } } while( ReadersPresent ); } public void ReleaseReaderLock() { Interlocked.Increment( ref this.readersOut ); } public void ReleaseWriterLock() { try { this.writerPresent = false; this.WriterFinishedEvent.Set(); } finally { Monitor.Exit( this.SyncRoot ); } } } // This transaction table implementation uses an array of lists to avoid contention. The list for a // transaction is decided by its hashcode. class TransactionTable { // Use a timer to initiate looking for transactions that have timed out. System.Threading.Timer timer; // Private storage noting if the timer is enabled. bool timerEnabled; // Store the timer interval const int timerInternalExponent = 9; int timerInterval; // Store the number of ticks. A tick is a mark of 1 timer interval. By counting ticks // we can avoid expensive calls to get the current time for every transaction creation. const long TicksPerMillisecond = 10000; long ticks; Int64 lastTimerTime; // Sets of arrays of transactions. BucketSet headBucketSet; // Synchronize adding transactions with shutting off the timer and started events. CheapUnfairReaderWriterLock rwLock; internal TransactionTable() { // Create a timer that is initially disabled by specifing an Infinite time to the first interval this.timer = new Timer( new TimerCallback(ThreadTimer), null, Timeout.Infinite, this.timerInterval ); // Note that the timer is disabled this.timerEnabled = false; // Store the timer interval this.timerInterval = 1 << TransactionTable.timerInternalExponent; // Ticks start off at zero. this.ticks = 0; // The head of the list is long.MaxValue. It contains all of the transactions that for // some reason or other don't have a timeout. this.headBucketSet = new BucketSet( this, long.MaxValue ); // Allocate the lock rwLock = new CheapUnfairReaderWriterLock(); } // Calculate the maximum number of ticks for which this transaction should live internal long TimeoutTicks( TimeSpan timeout ) { if( timeout != TimeSpan.Zero ) { // Note: At the current setting of approximately 2 ticks per second this timer will // wrap in approximately 2^64/2/60/60/24/365=292,471,208,677.5360162195585996 // (nearly 300 billion) years. long timeoutTicks = ((timeout.Ticks / TimeSpan.TicksPerMillisecond) >> TransactionTable.timerInternalExponent) + this.ticks; return timeoutTicks; } else { return long.MaxValue; } } // Absolute timeout internal TimeSpan RecalcTimeout( InternalTransaction tx ) { return TimeSpan.FromMilliseconds( (tx.AbsoluteTimeout - this.ticks) * this.timerInterval ); } // Creation time private Int64 CurrentTime { get { if( this.timerEnabled ) { return this.lastTimerTime; } else { return DateTime.UtcNow.Ticks; } } } // Add a transaction to the table. Transactions are added to the end of the list in sorted order based on their // absolute timeout. internal int Add( InternalTransaction txNew ) { // Tell the runtime that we are modifying global state. Thread.BeginCriticalRegion(); int readerIndex = 0; try { readerIndex = rwLock.AcquireReaderLock(); try { // Start the timer if needed before checking the current time since the current // time can be more efficient with a running timer. if( txNew.AbsoluteTimeout != long.MaxValue ) { if( !this.timerEnabled ) { if( !this.timer.Change( this.timerInterval, this.timerInterval )) { throw TransactionException.CreateInvalidOperationException( SR.GetString( SR.TraceSourceLtm ), SR.GetString(SR.UnexpectedTimerFailure), null ); } this.lastTimerTime = DateTime.UtcNow.Ticks; this.timerEnabled = true; } } txNew.CreationTime = CurrentTime; AddIter( txNew ); } finally { rwLock.ReleaseReaderLock(); } } finally { Thread.EndCriticalRegion(); } return readerIndex; } void AddIter( InternalTransaction txNew ) { // // Theory of operation. // // Note that the head bucket contains any transaction with essentially infinite // timeout (long.MaxValue). The list is sorted in decending order. To add // a node the code must walk down the list looking for a set of bucket that matches // the absolute timeout value for the transaction. When it is found it passes // the insert down to that set. // // An importent thing to note about the list is that forward links are all weak // references and reverse links are all strong references. This allows the GC // to clean up old links in the list so that they don't need to be removed manually. // However if there is still a rooted strong reference to an old link in the // chain that link wont fall off the list because there is a strong reference held // forward. // BucketSet currentBucketSet = this.headBucketSet; while( currentBucketSet.AbsoluteTimeout != txNew.AbsoluteTimeout ) { BucketSet lastBucketSet = null; do { WeakReference nextSetWeak = (WeakReference)currentBucketSet.nextSetWeak; BucketSet nextBucketSet = null; if( nextSetWeak != null ) { nextBucketSet = (BucketSet)nextSetWeak.Target; } if( nextBucketSet == null ) { // // We've reached the end of the list either because nextSetWeak was null or // because its reference was collected. This code doesn't care. Make a new // set, attempt to attach it and move on. // BucketSet newBucketSet = new BucketSet( this, txNew.AbsoluteTimeout ); WeakReference newSetWeak = new WeakReference( newBucketSet ); WeakReference oldNextSetWeak = (WeakReference)Interlocked.CompareExchange( ref currentBucketSet.nextSetWeak, newSetWeak, nextSetWeak ); if( oldNextSetWeak == nextSetWeak ) { // Ladies and Gentlemen we have a winner. newBucketSet.prevSet = currentBucketSet; } // Note that at this point we don't update currentBucketSet. On the next loop // iteration we should be able to pick up where we left off. } else { lastBucketSet = currentBucketSet; currentBucketSet = nextBucketSet; } }while( currentBucketSet.AbsoluteTimeout > txNew.AbsoluteTimeout ); if( currentBucketSet.AbsoluteTimeout != txNew.AbsoluteTimeout ) { // // Getting to here means that we've found a slot in the list where this bucket set should go. // BucketSet newBucketSet = new BucketSet( this, txNew.AbsoluteTimeout ); WeakReference newSetWeak = new WeakReference( newBucketSet ); newBucketSet.nextSetWeak = lastBucketSet.nextSetWeak; WeakReference oldNextSetWeak = (WeakReference)Interlocked.CompareExchange( ref lastBucketSet.nextSetWeak, newSetWeak, newBucketSet.nextSetWeak ); if( oldNextSetWeak == newBucketSet.nextSetWeak ) { // Ladies and Gentlemen we have a winner. if( oldNextSetWeak != null ) { BucketSet oldSet = (BucketSet)oldNextSetWeak.Target; if( oldSet != null ) { // prev references are just there to root things for the GC. If this object is // gone we don't really care. oldSet.prevSet = newBucketSet; } } newBucketSet.prevSet = currentBucketSet; } currentBucketSet = lastBucketSet; lastBucketSet = null; // The outer loop will iterate and pick up where we left off. } } // // Great we found a spot. // currentBucketSet.Add( txNew ); } // Remove a transaction from the table. internal void Remove( InternalTransaction tx ) { tx.tableBucket.Remove( tx ); tx.tableBucket = null; } // Process a timer event private void ThreadTimer( Object state ) { // // Theory of operation. // // To timeout transactions we must walk down the list starting from the head // until we find a link with an absolute timeout that is greater than our own. // At that point everything further down in the list is elegable to be timed // out. So simply remove that link in the list and walk down from that point // timing out any transaction that is found. // // There could be a ---- between this callback being queued and the timer // being disabled. If we get here when the timer is disabled, just return. if ( !this.timerEnabled ) { return; } // Increment the number of ticks this.ticks++; this.lastTimerTime = DateTime.UtcNow.Ticks; // // First find the starting point of transactions that should time out. Every transaction after // that point will timeout so once we've found it then it is just a matter of traversing the // structure. // BucketSet lastBucketSet = null; BucketSet currentBucketSet = this.headBucketSet; // The list always has a head. WeakReference nextWeakSet = (WeakReference)currentBucketSet.nextSetWeak; BucketSet nextBucketSet = null; if( nextWeakSet != null ) { nextBucketSet = (BucketSet)nextWeakSet.Target; } if( nextBucketSet == null ) { // // Special case to allow for disabling the timer. // this.rwLock.AcquireWriterLock(); try { // If there are no transactions on the timeout list we can disable the // timer. if( !this.timer.Change( Timeout.Infinite, Timeout.Infinite )) { throw TransactionException.CreateInvalidOperationException( SR.GetString( SR.TraceSourceLtm ), SR.GetString(SR.UnexpectedTimerFailure), null ); } this.timerEnabled = false; return; } finally { this.rwLock.ReleaseWriterLock(); } } // Note it is slightly subtle that we always skip the head node. This is done // on purpose because the head node contains transactions with essentially // an infinite timeout. do { do { nextWeakSet = (WeakReference)currentBucketSet.nextSetWeak; if( nextWeakSet == null ) { // Nothing more to do. return; } nextBucketSet = (BucketSet)nextWeakSet.Target; if( nextBucketSet == null ) { // Again nothing more to do. return; } lastBucketSet = currentBucketSet; currentBucketSet = nextBucketSet; } while( currentBucketSet.AbsoluteTimeout > this.ticks ); // Tell the runtime that we are modifying global state. Thread.BeginCriticalRegion(); try { // // Pinch off the list at this point making sure it is still the correct set. // WeakReference abortingSetsWeak = (WeakReference)Interlocked.CompareExchange( ref lastBucketSet.nextSetWeak, null, nextWeakSet ); if( abortingSetsWeak == nextWeakSet ) { // Yea - now proceed to abort the transactions. BucketSet abortingBucketSets = null; do { if( abortingSetsWeak != null ) { abortingBucketSets = (BucketSet)abortingSetsWeak.Target; } else { abortingBucketSets = null; } if( abortingBucketSets != null ) { abortingBucketSets.TimeoutTransactions(); abortingSetsWeak = (WeakReference)abortingBucketSets.nextSetWeak; } } while( abortingBucketSets != null ); // That's all we needed to do. break; } } finally { Thread.EndCriticalRegion(); } // We missed pulling the right transactions off. Loop back up and try again. currentBucketSet = lastBucketSet; }while( true ); } } class BucketSet { // Buckets are kept in sets. Each element of a set will have the same absoluteTimeout. internal object nextSetWeak; internal BucketSet prevSet; TransactionTable table; long absoluteTimeout; internal Bucket headBucket; internal BucketSet( TransactionTable table, long absoluteTimeout ) { this.headBucket = new Bucket( this ); this.table = table; this.absoluteTimeout = absoluteTimeout; } internal long AbsoluteTimeout { get { return this.absoluteTimeout; } } internal void Add( InternalTransaction newTx ) { while( !this.headBucket.Add( newTx )) ; } internal void TimeoutTransactions() { Bucket currentBucket = this.headBucket; // It will always have a head. do { currentBucket.TimeoutTransactions(); WeakReference nextWeakBucket = (WeakReference)currentBucket.nextBucketWeak; if( nextWeakBucket != null ) { currentBucket = (Bucket)nextWeakBucket.Target; } else { currentBucket = null; } } while( currentBucket != null ); } } class Bucket { bool timedOut; int index; int size; InternalTransaction [] transactions; internal WeakReference nextBucketWeak; Bucket previous; BucketSet owningSet; internal Bucket( BucketSet owningSet ) { this.timedOut = false; this.index = -1; this.size = 1024; // A possible design change here is to have this scale dynamically based on load. transactions = new InternalTransaction [this.size]; this.owningSet = owningSet; } internal bool Add( InternalTransaction tx ) { int currentIndex = Interlocked.Increment( ref this.index ); if( currentIndex < this.size ) { tx.tableBucket = this; tx.bucketIndex = currentIndex; Thread.MemoryBarrier(); // This data must be written before the transaction // could be timed out. this.transactions [currentIndex] = tx; if( this.timedOut ) { lock( tx ) { tx.State.Timeout( tx ); } } } else { Bucket newBucket = new Bucket( this.owningSet ); newBucket.nextBucketWeak = new WeakReference( this ); Bucket oldBucket = Interlocked.CompareExchange( ref this.owningSet.headBucket, newBucket, this ); if( oldBucket == this ) { // ladies and gentlemen we have a winner. this.previous = newBucket; } return false; } return true; } internal void Remove( InternalTransaction tx ) { this.transactions [tx.bucketIndex] = null; } internal void TimeoutTransactions() { int i; int transactionCount = this.index; this.timedOut = true; Thread.MemoryBarrier(); for( i = 0; i <= transactionCount && i < this.size; i++ ) { Debug.Assert( transactionCount == this.index, "Index changed timing out transactions" ); InternalTransaction tx = this.transactions [i]; if( tx != null ) { lock( tx ) { tx.State.Timeout( tx ); } } } } } } // File provided for Reference Use Only by Microsoft Corporation (c) 2007.
Link Menu
This book is available now!
Buy at Amazon US or
Buy at Amazon UK
- PtsContext.cs
- WindowsAuthenticationModule.cs
- sapiproxy.cs
- ImageSource.cs
- RoutedUICommand.cs
- XomlDesignerLoader.cs
- SchemaSetCompiler.cs
- smtpconnection.cs
- PropertyItem.cs
- KnownBoxes.cs
- DataError.cs
- UInt32.cs
- BStrWrapper.cs
- InstanceLockedException.cs
- ComAdminWrapper.cs
- TableStyle.cs
- DbParameterCollectionHelper.cs
- DiscoveryRequestHandler.cs
- JsonDataContract.cs
- LocalBuilder.cs
- ClientOptions.cs
- ApplicationInterop.cs
- XmlSchemaGroup.cs
- WorkflowQueue.cs
- Metafile.cs
- RoleServiceManager.cs
- Pair.cs
- XmlName.cs
- OleDbError.cs
- WebPartAddingEventArgs.cs
- __Error.cs
- RecordsAffectedEventArgs.cs
- XmlWrappingWriter.cs
- MemberRelationshipService.cs
- IDataContractSurrogate.cs
- ECDiffieHellmanPublicKey.cs
- OdbcInfoMessageEvent.cs
- CommonDialog.cs
- ADMembershipProvider.cs
- SqlLiftWhereClauses.cs
- DiscreteKeyFrames.cs
- DispatcherObject.cs
- AuthenticationSection.cs
- SystemDiagnosticsSection.cs
- _CacheStreams.cs
- IxmlLineInfo.cs
- ListSourceHelper.cs
- CodeGotoStatement.cs
- TextDpi.cs
- TextRangeEditLists.cs
- DecimalConverter.cs
- FunctionDescription.cs
- WebBrowserUriTypeConverter.cs
- RightsManagementPermission.cs
- ExtendedPropertyCollection.cs
- CacheEntry.cs
- SortFieldComparer.cs
- ScriptDescriptor.cs
- MetaModel.cs
- EntityProxyTypeInfo.cs
- TabRenderer.cs
- WebHttpElement.cs
- GeneralTransform2DTo3DTo2D.cs
- _SecureChannel.cs
- GatewayIPAddressInformationCollection.cs
- PersonalizationProviderCollection.cs
- ValidationUtility.cs
- DbProviderManifest.cs
- BmpBitmapEncoder.cs
- SmtpCommands.cs
- Win32SafeHandles.cs
- StylusButton.cs
- SqlSupersetValidator.cs
- FormViewModeEventArgs.cs
- WindowsListViewItem.cs
- Control.cs
- ZoneLinkButton.cs
- RuleSetCollection.cs
- CompilationSection.cs
- ReflectionPermission.cs
- ChildrenQuery.cs
- TextDecorationLocationValidation.cs
- InternalConfigHost.cs
- InteropAutomationProvider.cs
- COM2PropertyDescriptor.cs
- FullTextState.cs
- AlternateView.cs
- LineVisual.cs
- cookie.cs
- __FastResourceComparer.cs
- NullableIntAverageAggregationOperator.cs
- LazyInitializer.cs
- MatrixValueSerializer.cs
- SplineKeyFrames.cs
- WmlListAdapter.cs
- ParserContext.cs
- OleAutBinder.cs
- ListViewDeletedEventArgs.cs
- CrossSiteScriptingValidation.cs
- SystemUnicastIPAddressInformation.cs