3 // Copyright (c) Microsoft Corporation. All rights reserved.
6 // =+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
10 // <OWNER>[....]</OWNER>
12 // A non-generic and generic parallel state class, used by the Parallel helper class
13 // for parallel loop management.
15 // =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
17 using System.Diagnostics;
18 using System.Security.Permissions;
19 using System.Diagnostics.Contracts;
21 // Prevents compiler warnings/errors regarding the use of ref params in Interlocked methods
22 #pragma warning disable 0420
24 namespace System.Threading.Tasks
28 /// Enables iterations of <see cref="T:System.Threading.Tasks.Parallel"/> loops to interact with
31 [HostProtection(Synchronization = true, ExternalThreading = true)]
32 [DebuggerDisplay("ShouldExitCurrentIteration = {ShouldExitCurrentIteration}")]
33 public class ParallelLoopState
35 // Derived classes will track a ParallelStateFlags32 or ParallelStateFlags64.
36 // So this is slightly redundant, but it enables us to implement some
37 // methods in this base class.
38 private ParallelLoopStateFlags m_flagsBase;
40 internal ParallelLoopState(ParallelLoopStateFlags fbase)
46 /// Internal/virtual support for ShouldExitCurrentIteration.
48 internal virtual bool InternalShouldExitCurrentIteration
52 Contract.Assert(false);
53 throw new NotSupportedException(
54 Environment.GetResourceString("ParallelState_NotSupportedException_UnsupportedMethod"));
59 /// Gets whether the current iteration of the loop should exit based
60 /// on requests made by this or other iterations.
63 /// When an iteration of a loop calls <see cref="Break()"/> or <see cref="Stop()"/>, or
64 /// when one throws an exception, or when the loop is canceled, the <see cref="Parallel"/> class will proactively
65 /// attempt to prohibit additional iterations of the loop from starting execution.
66 /// However, there may be cases where it is unable to prevent additional iterations from starting.
67 /// It may also be the case that a long-running iteration has already begun execution. In such
68 /// cases, iterations may explicitly check the <see cref="ShouldExitCurrentIteration"/> property and
69 /// cease execution if the property returns true.
71 public bool ShouldExitCurrentIteration
75 return InternalShouldExitCurrentIteration;
80 /// Gets whether any iteration of the loop has called <see cref="Stop()"/>.
86 return ((m_flagsBase.LoopStateFlags & ParallelLoopStateFlags.PLS_STOPPED) != 0);
91 /// Gets whether any iteration of the loop has thrown an exception that went unhandled by that
94 public bool IsExceptional
98 return ((m_flagsBase.LoopStateFlags & ParallelLoopStateFlags.PLS_EXCEPTIONAL) != 0);
103 /// Internal/virtual support for LowestBreakIteration.
105 internal virtual long? InternalLowestBreakIteration
109 Contract.Assert(false);
110 throw new NotSupportedException(
111 Environment.GetResourceString("ParallelState_NotSupportedException_UnsupportedMethod"));
116 /// Gets the lowest iteration of the loop from which <see cref="Break()"/> was called.
119 /// If no iteration of the loop called <see cref="Break()"/>, this property will return null.
121 public long? LowestBreakIteration
125 return InternalLowestBreakIteration;
130 /// Communicates that the <see cref="Parallel"/> loop should cease execution at the system's earliest
133 /// <exception cref="T:System.InvalidOperationException">
134 /// The <see cref="Break()"/> method was previously called. <see cref="Break()"/> and <see
135 /// cref="Stop()"/> may not be used in combination by iterations of the same loop.
139 /// <see cref="Stop()"/> may be used to communicate to the loop that no other iterations need be run.
140 /// For long-running iterations that may already be executing, <see cref="Stop()"/> causes <see cref="IsStopped"/>
141 /// to return true for all other iterations of the loop, such that another iteration may check <see
142 /// cref="IsStopped"/> and exit early if it's observed to be true.
145 /// <see cref="Stop()"/> is typically employed in search-based algorithms, where once a result is found,
146 /// no other iterations need be executed.
154 // Internal/virtual support for Break().
155 internal virtual void InternalBreak()
157 Contract.Assert(false);
158 throw new NotSupportedException(
159 Environment.GetResourceString("ParallelState_NotSupportedException_UnsupportedMethod"));
163 /// Communicates that the <see cref="Parallel"/> loop should cease execution at the system's earliest
164 /// convenience of iterations beyond the current iteration.
166 /// <exception cref="T:System.InvalidOperationException">
167 /// The <see cref="Stop()"/> method was previously called. <see cref="Break()"/> and <see cref="Stop()"/>
168 /// may not be used in combination by iterations of the same loop.
172 /// <see cref="Break()"/> may be used to communicate to the loop that no other iterations after the
173 /// current iteration need be run. For example, if <see cref="Break()"/> is called from the 100th
174 /// iteration of a for loop iterating in parallel from 0 to 1000, all iterations less than 100 should
175 /// still be run, but the iterations from 101 through to 1000 are not necessary.
178 /// For long-running iterations that may already be executing, <see cref="Break()"/> causes <see
179 /// cref="LowestBreakIteration"/>
180 /// to be set to the current iteration's index if the current index is less than the current value of
181 /// <see cref="LowestBreakIteration"/>.
184 /// <see cref="Break()"/> is typically employed in search-based algorithms where an ordering is
185 /// present in the data source.
193 // Helper method to avoid repeating Break() logic between ParallelState32 and ParallelState32<TLocal>
194 internal static void Break(int iteration, ParallelLoopStateFlags32 pflags)
196 int oldValue = ParallelLoopStateFlags.PLS_NONE;
198 // Attempt to change state from "not stopped or broken or canceled or exceptional" to "broken".
199 if (!pflags.AtomicLoopStateUpdate(ParallelLoopStateFlags.PLS_BROKEN,
200 ParallelLoopStateFlags.PLS_STOPPED | ParallelLoopStateFlags.PLS_EXCEPTIONAL | ParallelLoopStateFlags.PLS_CANCELED,
204 // If we were already stopped, we have a problem
205 if ((oldValue & ParallelLoopStateFlags.PLS_STOPPED) != 0)
207 throw new InvalidOperationException(
208 Environment.GetResourceString("ParallelState_Break_InvalidOperationException_BreakAfterStop"));
212 // Apparently we previously got cancelled or became exceptional. No action necessary
217 // replace shared LowestBreakIteration with CurrentIteration, but only if CurrentIteration
218 // is less than LowestBreakIteration.
219 int oldLBI = pflags.m_lowestBreakIteration;
220 if (iteration < oldLBI)
222 SpinWait wait = new SpinWait();
223 while (Interlocked.CompareExchange(
224 ref pflags.m_lowestBreakIteration,
229 oldLBI = pflags.m_lowestBreakIteration;
230 if (iteration > oldLBI) break;
236 // Helper method to avoid repeating Break() logic between ParallelState64 and ParallelState64<TLocal>
237 internal static void Break(long iteration, ParallelLoopStateFlags64 pflags)
239 int oldValue = ParallelLoopStateFlags.PLS_NONE;
241 // Attempt to change state from "not stopped or broken or canceled or exceptional" to "broken".
242 if (!pflags.AtomicLoopStateUpdate(ParallelLoopStateFlags.PLS_BROKEN,
243 ParallelLoopStateFlags.PLS_STOPPED | ParallelLoopStateFlags.PLS_EXCEPTIONAL | ParallelLoopStateFlags.PLS_CANCELED,
247 // If we were already stopped, we have a problem
248 if ((oldValue & ParallelLoopStateFlags.PLS_STOPPED) != 0)
250 throw new InvalidOperationException(
251 Environment.GetResourceString("ParallelState_Break_InvalidOperationException_BreakAfterStop"));
255 // Apparently we previously got cancelled or became exceptional. No action necessary
260 // replace shared LowestBreakIteration with CurrentIteration, but only if CurrentIteration
261 // is less than LowestBreakIteration.
262 long oldLBI = pflags.LowestBreakIteration;
263 if (iteration < oldLBI)
265 SpinWait wait = new SpinWait();
266 while (Interlocked.CompareExchange(
267 ref pflags.m_lowestBreakIteration,
272 oldLBI = pflags.LowestBreakIteration;
273 if (iteration > oldLBI) break;
280 internal class ParallelLoopState32 : ParallelLoopState
282 private ParallelLoopStateFlags32 m_sharedParallelStateFlags;
283 private int m_currentIteration = 0;
286 /// Internal constructor to ensure an instance isn't created by users.
288 /// <param name="sharedParallelStateFlags">A flag shared among all threads participating
289 /// in the execution of a certain loop.</param>
290 internal ParallelLoopState32(ParallelLoopStateFlags32 sharedParallelStateFlags)
291 : base(sharedParallelStateFlags)
293 m_sharedParallelStateFlags = sharedParallelStateFlags;
297 /// Tracks the current loop iteration for the owning task.
298 /// This is used to compute whether or not the task should
299 /// terminate early due to a Break() call.
301 internal int CurrentIteration {
302 get { return m_currentIteration; }
303 set { m_currentIteration = value; }
307 /// Returns true if we should be exiting from the current iteration
308 /// due to Stop(), Break() or exception.
310 internal override bool InternalShouldExitCurrentIteration
312 get { return m_sharedParallelStateFlags.ShouldExitLoop(CurrentIteration); }
316 /// Returns the lowest iteration at which Break() has been called, or
317 /// null if Break() has not yet been called.
319 internal override long? InternalLowestBreakIteration
321 get {return m_sharedParallelStateFlags.NullableLowestBreakIteration; }
325 /// Communicates that parallel tasks should stop when they reach a specified iteration element.
326 /// (which is CurrentIteration of the caller).
328 /// <exception cref="T:System.InvalidOperationException">Break() called after Stop().</exception>
330 /// This is shared with all other concurrent threads in the system which are participating in the
331 /// loop's execution. After calling Break(), no additional iterations will be executed on
332 /// the current thread, and other worker threads will execute once they get beyond the calling iteration.
334 internal override void InternalBreak()
336 ParallelLoopState.Break(CurrentIteration, m_sharedParallelStateFlags);
341 /// Allows independent iterations of a parallel loop to interact with other iterations.
343 internal class ParallelLoopState64 : ParallelLoopState
345 private ParallelLoopStateFlags64 m_sharedParallelStateFlags;
346 private long m_currentIteration = 0;
349 /// Internal constructor to ensure an instance isn't created by users.
351 /// <param name="sharedParallelStateFlags">A flag shared among all threads participating
352 /// in the execution of a certain loop.</param>
353 internal ParallelLoopState64(ParallelLoopStateFlags64 sharedParallelStateFlags)
354 : base(sharedParallelStateFlags)
356 m_sharedParallelStateFlags = sharedParallelStateFlags;
360 /// Tracks the current loop iteration for the owning task.
361 /// This is used to compute whether or not the task should
362 /// terminate early due to a Break() call.
364 internal long CurrentIteration
366 // No interlocks needed, because this value is only accessed in a single thread.
367 get {return m_currentIteration;}
368 set {m_currentIteration = value; }
372 /// Returns true if we should be exiting from the current iteration
373 /// due to Stop(), Break() or exception.
375 internal override bool InternalShouldExitCurrentIteration
377 get { return m_sharedParallelStateFlags.ShouldExitLoop(CurrentIteration); }
381 /// Returns the lowest iteration at which Break() has been called, or
382 /// null if Break() has not yet been called.
384 internal override long? InternalLowestBreakIteration
386 // We don't need to worry about torn read/write here because
387 // ParallelStateFlags64.LowestBreakIteration property is protected
388 // by an Interlocked.Read().
389 get { return m_sharedParallelStateFlags.NullableLowestBreakIteration; }
393 /// Communicates that parallel tasks should stop when they reach a specified iteration element.
394 /// (which is CurrentIteration of the caller).
396 /// <exception cref="T:System.InvalidOperationException">Break() called after Stop().</exception>
398 /// Atomically sets shared StoppedBroken flag to BROKEN, then atomically sets shared
399 /// LowestBreakIteration to CurrentIteration, but only if CurrentIteration is less than
400 /// LowestBreakIteration.
402 internal override void InternalBreak()
404 ParallelLoopState.Break(CurrentIteration, m_sharedParallelStateFlags);
410 /// State information that is common between ParallelStateFlags class
411 /// and ParallelStateFlags64 class.
413 internal class ParallelLoopStateFlags
415 #pragma warning disable 649
416 internal static int PLS_NONE;
417 #pragma warning restore
418 internal static int PLS_EXCEPTIONAL = 1;
419 internal static int PLS_BROKEN = 2;
420 internal static int PLS_STOPPED = 4;
421 internal static int PLS_CANCELED = 8;
423 private volatile int m_LoopStateFlags = PLS_NONE;
425 internal int LoopStateFlags
427 get { return m_LoopStateFlags; }
430 internal bool AtomicLoopStateUpdate(int newState, int illegalStates)
433 return AtomicLoopStateUpdate(newState, illegalStates, ref oldState);
436 internal bool AtomicLoopStateUpdate(int newState, int illegalStates, ref int oldState)
438 SpinWait sw = new SpinWait();
442 oldState = m_LoopStateFlags;
443 if ((oldState & illegalStates) != 0) return false;
444 #pragma warning disable 420
445 if (Interlocked.CompareExchange(ref m_LoopStateFlags, oldState | newState, oldState) == oldState)
446 #pragma warning restore
455 internal void SetExceptional()
457 // we can set the exceptional flag regardless of the state of other bits.
458 AtomicLoopStateUpdate(PLS_EXCEPTIONAL, PLS_NONE);
463 // disallow setting of PLS_STOPPED bit only if PLS_BROKEN was already set
464 if (!AtomicLoopStateUpdate(PLS_STOPPED, PLS_BROKEN))
466 throw new InvalidOperationException(
467 Environment.GetResourceString("ParallelState_Stop_InvalidOperationException_StopAfterBreak"));
471 // Returns true if StoppedBroken is updated to PLS_CANCELED.
472 internal bool Cancel()
474 // we can set the canceled flag regardless of the state of other bits.
475 return (AtomicLoopStateUpdate(PLS_CANCELED, PLS_NONE));
480 /// An internal class used to share accounting information in 32-bit versions
481 /// of For()/ForEach() loops.
483 internal class ParallelLoopStateFlags32 : ParallelLoopStateFlags
485 // Records the lowest iteration at which a Break() has been called,
486 // or Int32.MaxValue if no break has been called. Used directly
488 internal volatile int m_lowestBreakIteration = Int32.MaxValue;
490 // Not strictly necessary, but maintains consistency with ParallelStateFlags64
491 internal int LowestBreakIteration
493 get { return m_lowestBreakIteration; }
496 // Does some processing to convert m_lowestBreakIteration to a long?.
497 internal long? NullableLowestBreakIteration
501 if (m_lowestBreakIteration == Int32.MaxValue) return null;
504 // protect against torn read of 64-bit value
505 long rval = m_lowestBreakIteration;
506 if (IntPtr.Size >= 8) return rval;
507 else return Interlocked.Read(ref rval);
514 /// Lets the caller know whether or not to prematurely exit the For/ForEach loop.
515 /// If this returns true, then exit the loop. Otherwise, keep going.
517 /// <param name="CallerIteration">The caller's current iteration point
518 /// in the loop.</param>
520 /// The loop should exit on any one of the following conditions:
521 /// (1) Stop() has been called by one or more tasks.
522 /// (2) An exception has been raised by one or more tasks.
523 /// (3) Break() has been called by one or more tasks, and
524 /// CallerIteration exceeds the (lowest) iteration at which
525 /// Break() was called.
526 /// (4) The loop was canceled.
528 internal bool ShouldExitLoop(int CallerIteration)
530 int flags = LoopStateFlags;
531 return (flags != PLS_NONE && (
532 ((flags & (PLS_EXCEPTIONAL | PLS_STOPPED | PLS_CANCELED)) != 0) ||
533 (((flags & PLS_BROKEN) != 0) && (CallerIteration > LowestBreakIteration))));
536 // This lighter version of ShouldExitLoop will be used when the body type doesn't contain a state.
537 // Since simpler bodies cannot stop or break, we can safely skip checks for those flags here.
538 internal bool ShouldExitLoop()
540 int flags = LoopStateFlags;
541 return ((flags != PLS_NONE) && ((flags & (PLS_EXCEPTIONAL | PLS_CANCELED)) != 0));
546 /// An internal class used to share accounting information in 64-bit versions
547 /// of For()/ForEach() loops.
549 internal class ParallelLoopStateFlags64 : ParallelLoopStateFlags
551 // Records the lowest iteration at which a Break() has been called,
552 // or Int64.MaxValue if no break has been called. Used directly
554 internal long m_lowestBreakIteration = Int64.MaxValue;
556 // Performs a conditionally interlocked read of m_lowestBreakIteration.
557 internal long LowestBreakIteration
561 if (IntPtr.Size >= 8) return m_lowestBreakIteration;
562 else return Interlocked.Read(ref m_lowestBreakIteration);
566 // Does some processing to convert m_lowestBreakIteration to a long?.
567 internal long? NullableLowestBreakIteration
571 if (m_lowestBreakIteration == Int64.MaxValue) return null;
574 if (IntPtr.Size >= 8) return m_lowestBreakIteration;
575 else return Interlocked.Read(ref m_lowestBreakIteration);
581 /// Lets the caller know whether or not to prematurely exit the For/ForEach loop.
582 /// If this returns true, then exit the loop. Otherwise, keep going.
584 /// <param name="CallerIteration">The caller's current iteration point
585 /// in the loop.</param>
587 /// The loop should exit on any one of the following conditions:
588 /// (1) Stop() has been called by one or more tasks.
589 /// (2) An exception has been raised by one or more tasks.
590 /// (3) Break() has been called by one or more tasks, and
591 /// CallerIteration exceeds the (lowest) iteration at which
592 /// Break() was called.
593 /// (4) The loop has been canceled.
595 internal bool ShouldExitLoop(long CallerIteration)
597 int flags = LoopStateFlags;
598 return (flags != PLS_NONE && (
599 ((flags & (PLS_EXCEPTIONAL | PLS_STOPPED | PLS_CANCELED)) != 0) ||
600 (((flags & PLS_BROKEN) != 0) && (CallerIteration > LowestBreakIteration))));
603 // This lighter version of ShouldExitLoop will be used when the body type doesn't contain a state.
604 // Since simpler bodies cannot stop or break, we can safely skip checks for those flags here.
605 internal bool ShouldExitLoop()
607 int flags = LoopStateFlags;
608 return ((flags != PLS_NONE) && ((flags & (PLS_EXCEPTIONAL | PLS_CANCELED)) != 0));
613 /// Provides completion status on the execution of a <see cref="Parallel"/> loop.
616 /// If <see cref="IsCompleted"/> returns true, then the loop ran to completion, such that all iterations
617 /// of the loop were executed. If <see cref="IsCompleted"/> returns false and <see
618 /// cref="LowestBreakIteration"/> returns null, a call to <see
619 /// cref="System.Threading.Tasks.ParallelLoopState.Stop"/> was used to end the loop prematurely. If <see
620 /// cref="IsCompleted"/> returns false and <see cref="LowestBreakIteration"/> returns a non-null integral
621 /// value, <see cref="System.Threading.Tasks.ParallelLoopState.Break()"/> was used to end the loop prematurely.
623 public struct ParallelLoopResult
625 internal bool m_completed;
626 internal long? m_lowestBreakIteration;
629 /// Gets whether the loop ran to completion, such that all iterations of the loop were executed
630 /// and the loop didn't receive a request to end prematurely.
632 public bool IsCompleted { get { return m_completed; } }
635 /// Gets the index of the lowest iteration from which <see
636 /// cref="System.Threading.Tasks.ParallelLoopState.Break()"/>
640 /// If <see cref="System.Threading.Tasks.ParallelLoopState.Break()"/> was not employed, this property will
643 public long? LowestBreakIteration { get { return m_lowestBreakIteration; } }
648 #pragma warning restore 0420