diff options
Diffstat (limited to 'src/mscorlib/src/System/Threading/Tasks/ParallelLoopState.cs')
| -rw-r--r-- | src/mscorlib/src/System/Threading/Tasks/ParallelLoopState.cs | 642 |
1 files changed, 642 insertions, 0 deletions
diff --git a/src/mscorlib/src/System/Threading/Tasks/ParallelLoopState.cs b/src/mscorlib/src/System/Threading/Tasks/ParallelLoopState.cs new file mode 100644 index 0000000000..4db3a9d105 --- /dev/null +++ b/src/mscorlib/src/System/Threading/Tasks/ParallelLoopState.cs @@ -0,0 +1,642 @@ +// Licensed to the .NET Foundation under one or more agreements. +// The .NET Foundation licenses this file to you under the MIT license. +// See the LICENSE file in the project root for more information. + +// =+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+ +// +// ParallelState.cs +// +// +// A non-generic and generic parallel state class, used by the Parallel helper class +// for parallel loop management. +// +// =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=- + +using System.Diagnostics; +using System.Security.Permissions; +using System.Diagnostics.Contracts; + +// Prevents compiler warnings/errors regarding the use of ref params in Interlocked methods +#pragma warning disable 0420 + +namespace System.Threading.Tasks +{ + + /// <summary> + /// Enables iterations of <see cref="T:System.Threading.Tasks.Parallel"/> loops to interact with + /// other iterations. + /// </summary> + [HostProtection(Synchronization = true, ExternalThreading = true)] + [DebuggerDisplay("ShouldExitCurrentIteration = {ShouldExitCurrentIteration}")] + public class ParallelLoopState + { + // Derived classes will track a ParallelStateFlags32 or ParallelStateFlags64. + // So this is slightly redundant, but it enables us to implement some + // methods in this base class. + private ParallelLoopStateFlags m_flagsBase; + + internal ParallelLoopState(ParallelLoopStateFlags fbase) + { + m_flagsBase = fbase; + } + + /// <summary> + /// Internal/virtual support for ShouldExitCurrentIteration. + /// </summary> + internal virtual bool InternalShouldExitCurrentIteration + { + get + { + Contract.Assert(false); + throw new NotSupportedException( + Environment.GetResourceString("ParallelState_NotSupportedException_UnsupportedMethod")); + } + } + + /// <summary> + /// Gets whether the current iteration of the loop should exit based + /// on requests made by this or other iterations. + /// </summary> + /// <remarks> + /// When an iteration of a loop calls <see cref="Break()"/> or <see cref="Stop()"/>, or + /// when one throws an exception, or when the loop is canceled, the <see cref="Parallel"/> class will proactively + /// attempt to prohibit additional iterations of the loop from starting execution. + /// However, there may be cases where it is unable to prevent additional iterations from starting. + /// It may also be the case that a long-running iteration has already begun execution. In such + /// cases, iterations may explicitly check the <see cref="ShouldExitCurrentIteration"/> property and + /// cease execution if the property returns true. + /// </remarks> + public bool ShouldExitCurrentIteration + { + get + { + return InternalShouldExitCurrentIteration; + } + } + + /// <summary> + /// Gets whether any iteration of the loop has called <see cref="Stop()"/>. + /// </summary> + public bool IsStopped + { + get + { + return ((m_flagsBase.LoopStateFlags & ParallelLoopStateFlags.PLS_STOPPED) != 0); + } + } + + /// <summary> + /// Gets whether any iteration of the loop has thrown an exception that went unhandled by that + /// iteration. + /// </summary> + public bool IsExceptional + { + get + { + return ((m_flagsBase.LoopStateFlags & ParallelLoopStateFlags.PLS_EXCEPTIONAL) != 0); + } + } + + /// <summary> + /// Internal/virtual support for LowestBreakIteration. + /// </summary> + internal virtual long? InternalLowestBreakIteration + { + get + { + Contract.Assert(false); + throw new NotSupportedException( + Environment.GetResourceString("ParallelState_NotSupportedException_UnsupportedMethod")); + } + } + + /// <summary> + /// Gets the lowest iteration of the loop from which <see cref="Break()"/> was called. + /// </summary> + /// <remarks> + /// If no iteration of the loop called <see cref="Break()"/>, this property will return null. + /// </remarks> + public long? LowestBreakIteration + { + get + { + return InternalLowestBreakIteration; + } + } + + /// <summary> + /// Communicates that the <see cref="Parallel"/> loop should cease execution at the system's earliest + /// convenience. + /// </summary> + /// <exception cref="T:System.InvalidOperationException"> + /// The <see cref="Break()"/> method was previously called. <see cref="Break()"/> and <see + /// cref="Stop()"/> may not be used in combination by iterations of the same loop. + /// </exception> + /// <remarks> + /// <para> + /// <see cref="Stop()"/> may be used to communicate to the loop that no other iterations need be run. + /// For long-running iterations that may already be executing, <see cref="Stop()"/> causes <see cref="IsStopped"/> + /// to return true for all other iterations of the loop, such that another iteration may check <see + /// cref="IsStopped"/> and exit early if it's observed to be true. + /// </para> + /// <para> + /// <see cref="Stop()"/> is typically employed in search-based algorithms, where once a result is found, + /// no other iterations need be executed. + /// </para> + /// </remarks> + public void Stop() + { + m_flagsBase.Stop(); + } + + // Internal/virtual support for Break(). + internal virtual void InternalBreak() + { + Contract.Assert(false); + throw new NotSupportedException( + Environment.GetResourceString("ParallelState_NotSupportedException_UnsupportedMethod")); + } + + /// <summary> + /// Communicates that the <see cref="Parallel"/> loop should cease execution at the system's earliest + /// convenience of iterations beyond the current iteration. + /// </summary> + /// <exception cref="T:System.InvalidOperationException"> + /// The <see cref="Stop()"/> method was previously called. <see cref="Break()"/> and <see cref="Stop()"/> + /// may not be used in combination by iterations of the same loop. + /// </exception> + /// <remarks> + /// <para> + /// <see cref="Break()"/> may be used to communicate to the loop that no other iterations after the + /// current iteration need be run. For example, if <see cref="Break()"/> is called from the 100th + /// iteration of a for loop iterating in parallel from 0 to 1000, all iterations less than 100 should + /// still be run, but the iterations from 101 through to 1000 are not necessary. + /// </para> + /// <para> + /// For long-running iterations that may already be executing, <see cref="Break()"/> causes <see + /// cref="LowestBreakIteration"/> + /// to be set to the current iteration's index if the current index is less than the current value of + /// <see cref="LowestBreakIteration"/>. + /// </para> + /// <para> + /// <see cref="Break()"/> is typically employed in search-based algorithms where an ordering is + /// present in the data source. + /// </para> + /// </remarks> + public void Break() + { + InternalBreak(); + } + + // Helper method to avoid repeating Break() logic between ParallelState32 and ParallelState32<TLocal> + internal static void Break(int iteration, ParallelLoopStateFlags32 pflags) + { + int oldValue = ParallelLoopStateFlags.PLS_NONE; + + // Attempt to change state from "not stopped or broken or canceled or exceptional" to "broken". + if (!pflags.AtomicLoopStateUpdate(ParallelLoopStateFlags.PLS_BROKEN, + ParallelLoopStateFlags.PLS_STOPPED | ParallelLoopStateFlags.PLS_EXCEPTIONAL | ParallelLoopStateFlags.PLS_CANCELED, + ref oldValue)) + { + + // If we were already stopped, we have a problem + if ((oldValue & ParallelLoopStateFlags.PLS_STOPPED) != 0) + { + throw new InvalidOperationException( + Environment.GetResourceString("ParallelState_Break_InvalidOperationException_BreakAfterStop")); + } + else + { + // Apparently we previously got cancelled or became exceptional. No action necessary + return; + } + } + + // replace shared LowestBreakIteration with CurrentIteration, but only if CurrentIteration + // is less than LowestBreakIteration. + int oldLBI = pflags.m_lowestBreakIteration; + if (iteration < oldLBI) + { + SpinWait wait = new SpinWait(); + while (Interlocked.CompareExchange( + ref pflags.m_lowestBreakIteration, + iteration, + oldLBI) != oldLBI) + { + wait.SpinOnce(); + oldLBI = pflags.m_lowestBreakIteration; + if (iteration > oldLBI) break; + } + } + + } + + // Helper method to avoid repeating Break() logic between ParallelState64 and ParallelState64<TLocal> + internal static void Break(long iteration, ParallelLoopStateFlags64 pflags) + { + int oldValue = ParallelLoopStateFlags.PLS_NONE; + + // Attempt to change state from "not stopped or broken or canceled or exceptional" to "broken". + if (!pflags.AtomicLoopStateUpdate(ParallelLoopStateFlags.PLS_BROKEN, + ParallelLoopStateFlags.PLS_STOPPED | ParallelLoopStateFlags.PLS_EXCEPTIONAL | ParallelLoopStateFlags.PLS_CANCELED, + ref oldValue)) + { + + // If we were already stopped, we have a problem + if ((oldValue & ParallelLoopStateFlags.PLS_STOPPED) != 0) + { + throw new InvalidOperationException( + Environment.GetResourceString("ParallelState_Break_InvalidOperationException_BreakAfterStop")); + } + else + { + // Apparently we previously got cancelled or became exceptional. No action necessary + return; + } + } + + // replace shared LowestBreakIteration with CurrentIteration, but only if CurrentIteration + // is less than LowestBreakIteration. + long oldLBI = pflags.LowestBreakIteration; + if (iteration < oldLBI) + { + SpinWait wait = new SpinWait(); + while (Interlocked.CompareExchange( + ref pflags.m_lowestBreakIteration, + iteration, + oldLBI) != oldLBI) + { + wait.SpinOnce(); + oldLBI = pflags.LowestBreakIteration; + if (iteration > oldLBI) break; + } + } + + } + } + + internal class ParallelLoopState32 : ParallelLoopState + { + private ParallelLoopStateFlags32 m_sharedParallelStateFlags; + private int m_currentIteration = 0; + + /// <summary> + /// Internal constructor to ensure an instance isn't created by users. + /// </summary> + /// <param name="sharedParallelStateFlags">A flag shared among all threads participating + /// in the execution of a certain loop.</param> + internal ParallelLoopState32(ParallelLoopStateFlags32 sharedParallelStateFlags) + : base(sharedParallelStateFlags) + { + m_sharedParallelStateFlags = sharedParallelStateFlags; + } + + /// <summary> + /// Tracks the current loop iteration for the owning task. + /// This is used to compute whether or not the task should + /// terminate early due to a Break() call. + /// </summary> + internal int CurrentIteration { + get { return m_currentIteration; } + set { m_currentIteration = value; } + } + + /// <summary> + /// Returns true if we should be exiting from the current iteration + /// due to Stop(), Break() or exception. + /// </summary> + internal override bool InternalShouldExitCurrentIteration + { + get { return m_sharedParallelStateFlags.ShouldExitLoop(CurrentIteration); } + } + + /// <summary> + /// Returns the lowest iteration at which Break() has been called, or + /// null if Break() has not yet been called. + /// </summary> + internal override long? InternalLowestBreakIteration + { + get {return m_sharedParallelStateFlags.NullableLowestBreakIteration; } + } + + /// <summary> + /// Communicates that parallel tasks should stop when they reach a specified iteration element. + /// (which is CurrentIteration of the caller). + /// </summary> + /// <exception cref="T:System.InvalidOperationException">Break() called after Stop().</exception> + /// <remarks> + /// This is shared with all other concurrent threads in the system which are participating in the + /// loop's execution. After calling Break(), no additional iterations will be executed on + /// the current thread, and other worker threads will execute once they get beyond the calling iteration. + /// </remarks> + internal override void InternalBreak() + { + ParallelLoopState.Break(CurrentIteration, m_sharedParallelStateFlags); + } + } + + /// <summary> + /// Allows independent iterations of a parallel loop to interact with other iterations. + /// </summary> + internal class ParallelLoopState64 : ParallelLoopState + { + private ParallelLoopStateFlags64 m_sharedParallelStateFlags; + private long m_currentIteration = 0; + + /// <summary> + /// Internal constructor to ensure an instance isn't created by users. + /// </summary> + /// <param name="sharedParallelStateFlags">A flag shared among all threads participating + /// in the execution of a certain loop.</param> + internal ParallelLoopState64(ParallelLoopStateFlags64 sharedParallelStateFlags) + : base(sharedParallelStateFlags) + { + m_sharedParallelStateFlags = sharedParallelStateFlags; + } + + /// <summary> + /// Tracks the current loop iteration for the owning task. + /// This is used to compute whether or not the task should + /// terminate early due to a Break() call. + /// </summary> + internal long CurrentIteration + { + // No interlocks needed, because this value is only accessed in a single thread. + get {return m_currentIteration;} + set {m_currentIteration = value; } + } + + /// <summary> + /// Returns true if we should be exiting from the current iteration + /// due to Stop(), Break() or exception. + /// </summary> + internal override bool InternalShouldExitCurrentIteration + { + get { return m_sharedParallelStateFlags.ShouldExitLoop(CurrentIteration); } + } + + /// <summary> + /// Returns the lowest iteration at which Break() has been called, or + /// null if Break() has not yet been called. + /// </summary> + internal override long? InternalLowestBreakIteration + { + // We don't need to worry about torn read/write here because + // ParallelStateFlags64.LowestBreakIteration property is protected + // by an Interlocked.Read(). + get { return m_sharedParallelStateFlags.NullableLowestBreakIteration; } + } + + /// <summary> + /// Communicates that parallel tasks should stop when they reach a specified iteration element. + /// (which is CurrentIteration of the caller). + /// </summary> + /// <exception cref="T:System.InvalidOperationException">Break() called after Stop().</exception> + /// <remarks> + /// Atomically sets shared StoppedBroken flag to BROKEN, then atomically sets shared + /// LowestBreakIteration to CurrentIteration, but only if CurrentIteration is less than + /// LowestBreakIteration. + /// </remarks> + internal override void InternalBreak() + { + ParallelLoopState.Break(CurrentIteration, m_sharedParallelStateFlags); + } + + } + + /// <summary> + /// State information that is common between ParallelStateFlags class + /// and ParallelStateFlags64 class. + /// </summary> + internal class ParallelLoopStateFlags + { + internal static int PLS_NONE; + internal static int PLS_EXCEPTIONAL = 1; + internal static int PLS_BROKEN = 2; + internal static int PLS_STOPPED = 4; + internal static int PLS_CANCELED = 8; + + private volatile int m_LoopStateFlags = PLS_NONE; + + internal int LoopStateFlags + { + get { return m_LoopStateFlags; } + } + + internal bool AtomicLoopStateUpdate(int newState, int illegalStates) + { + int oldState = 0; + return AtomicLoopStateUpdate(newState, illegalStates, ref oldState); + } + + internal bool AtomicLoopStateUpdate(int newState, int illegalStates, ref int oldState) + { + SpinWait sw = new SpinWait(); + + do + { + oldState = m_LoopStateFlags; + if ((oldState & illegalStates) != 0) return false; + if (Interlocked.CompareExchange(ref m_LoopStateFlags, oldState | newState, oldState) == oldState) + { + return true; + } + sw.SpinOnce(); + } while (true); + + } + + internal void SetExceptional() + { + // we can set the exceptional flag regardless of the state of other bits. + AtomicLoopStateUpdate(PLS_EXCEPTIONAL, PLS_NONE); + } + + internal void Stop() + { + // disallow setting of PLS_STOPPED bit only if PLS_BROKEN was already set + if (!AtomicLoopStateUpdate(PLS_STOPPED, PLS_BROKEN)) + { + throw new InvalidOperationException( + Environment.GetResourceString("ParallelState_Stop_InvalidOperationException_StopAfterBreak")); + } + } + + // Returns true if StoppedBroken is updated to PLS_CANCELED. + internal bool Cancel() + { + // we can set the canceled flag regardless of the state of other bits. + return (AtomicLoopStateUpdate(PLS_CANCELED, PLS_NONE)); + } + } + + /// <summary> + /// An internal class used to share accounting information in 32-bit versions + /// of For()/ForEach() loops. + /// </summary> + internal class ParallelLoopStateFlags32 : ParallelLoopStateFlags + { + // Records the lowest iteration at which a Break() has been called, + // or Int32.MaxValue if no break has been called. Used directly + // by Break(). + internal volatile int m_lowestBreakIteration = Int32.MaxValue; + + // Not strictly necessary, but maintains consistency with ParallelStateFlags64 + internal int LowestBreakIteration + { + get { return m_lowestBreakIteration; } + } + + // Does some processing to convert m_lowestBreakIteration to a long?. + internal long? NullableLowestBreakIteration + { + get + { + if (m_lowestBreakIteration == Int32.MaxValue) return null; + else + { + // protect against torn read of 64-bit value + long rval = m_lowestBreakIteration; + if (IntPtr.Size >= 8) return rval; + else return Interlocked.Read(ref rval); + } + } + } + + + /// <summary> + /// Lets the caller know whether or not to prematurely exit the For/ForEach loop. + /// If this returns true, then exit the loop. Otherwise, keep going. + /// </summary> + /// <param name="CallerIteration">The caller's current iteration point + /// in the loop.</param> + /// <remarks> + /// The loop should exit on any one of the following conditions: + /// (1) Stop() has been called by one or more tasks. + /// (2) An exception has been raised by one or more tasks. + /// (3) Break() has been called by one or more tasks, and + /// CallerIteration exceeds the (lowest) iteration at which + /// Break() was called. + /// (4) The loop was canceled. + /// </remarks> + internal bool ShouldExitLoop(int CallerIteration) + { + int flags = LoopStateFlags; + return (flags != PLS_NONE && ( + ((flags & (PLS_EXCEPTIONAL | PLS_STOPPED | PLS_CANCELED)) != 0) || + (((flags & PLS_BROKEN) != 0) && (CallerIteration > LowestBreakIteration)))); + } + + // This lighter version of ShouldExitLoop will be used when the body type doesn't contain a state. + // Since simpler bodies cannot stop or break, we can safely skip checks for those flags here. + internal bool ShouldExitLoop() + { + int flags = LoopStateFlags; + return ((flags != PLS_NONE) && ((flags & (PLS_EXCEPTIONAL | PLS_CANCELED)) != 0)); + } + } + + /// <summary> + /// An internal class used to share accounting information in 64-bit versions + /// of For()/ForEach() loops. + /// </summary> + internal class ParallelLoopStateFlags64 : ParallelLoopStateFlags + { + // Records the lowest iteration at which a Break() has been called, + // or Int64.MaxValue if no break has been called. Used directly + // by Break(). + internal long m_lowestBreakIteration = Int64.MaxValue; + + // Performs a conditionally interlocked read of m_lowestBreakIteration. + internal long LowestBreakIteration + { + get + { + if (IntPtr.Size >= 8) return m_lowestBreakIteration; + else return Interlocked.Read(ref m_lowestBreakIteration); + } + } + + // Does some processing to convert m_lowestBreakIteration to a long?. + internal long? NullableLowestBreakIteration + { + get + { + if (m_lowestBreakIteration == Int64.MaxValue) return null; + else + { + if (IntPtr.Size >= 8) return m_lowestBreakIteration; + else return Interlocked.Read(ref m_lowestBreakIteration); + } + } + } + + /// <summary> + /// Lets the caller know whether or not to prematurely exit the For/ForEach loop. + /// If this returns true, then exit the loop. Otherwise, keep going. + /// </summary> + /// <param name="CallerIteration">The caller's current iteration point + /// in the loop.</param> + /// <remarks> + /// The loop should exit on any one of the following conditions: + /// (1) Stop() has been called by one or more tasks. + /// (2) An exception has been raised by one or more tasks. + /// (3) Break() has been called by one or more tasks, and + /// CallerIteration exceeds the (lowest) iteration at which + /// Break() was called. + /// (4) The loop has been canceled. + /// </remarks> + internal bool ShouldExitLoop(long CallerIteration) + { + int flags = LoopStateFlags; + return (flags != PLS_NONE && ( + ((flags & (PLS_EXCEPTIONAL | PLS_STOPPED | PLS_CANCELED)) != 0) || + (((flags & PLS_BROKEN) != 0) && (CallerIteration > LowestBreakIteration)))); + } + + // This lighter version of ShouldExitLoop will be used when the body type doesn't contain a state. + // Since simpler bodies cannot stop or break, we can safely skip checks for those flags here. + internal bool ShouldExitLoop() + { + int flags = LoopStateFlags; + return ((flags != PLS_NONE) && ((flags & (PLS_EXCEPTIONAL | PLS_CANCELED)) != 0)); + } + } + + /// <summary> + /// Provides completion status on the execution of a <see cref="Parallel"/> loop. + /// </summary> + /// <remarks> + /// If <see cref="IsCompleted"/> returns true, then the loop ran to completion, such that all iterations + /// of the loop were executed. If <see cref="IsCompleted"/> returns false and <see + /// cref="LowestBreakIteration"/> returns null, a call to <see + /// cref="System.Threading.Tasks.ParallelLoopState.Stop"/> was used to end the loop prematurely. If <see + /// cref="IsCompleted"/> returns false and <see cref="LowestBreakIteration"/> returns a non-null integral + /// value, <see cref="System.Threading.Tasks.ParallelLoopState.Break()"/> was used to end the loop prematurely. + /// </remarks> + public struct ParallelLoopResult + { + internal bool m_completed; + internal long? m_lowestBreakIteration; + + /// <summary> + /// Gets whether the loop ran to completion, such that all iterations of the loop were executed + /// and the loop didn't receive a request to end prematurely. + /// </summary> + public bool IsCompleted { get { return m_completed; } } + + /// <summary> + /// Gets the index of the lowest iteration from which <see + /// cref="System.Threading.Tasks.ParallelLoopState.Break()"/> + /// was called. + /// </summary> + /// <remarks> + /// If <see cref="System.Threading.Tasks.ParallelLoopState.Break()"/> was not employed, this property will + /// return null. + /// </remarks> + public long? LowestBreakIteration { get { return m_lowestBreakIteration; } } + } + +} + +#pragma warning restore 0420 |