Intel(R) Threading Building Blocks Doxygen Documentation  version 4.2.3
custom_scheduler.h
Go to the documentation of this file.
1 /*
2  Copyright (c) 2005-2019 Intel Corporation
3 
4  Licensed under the Apache License, Version 2.0 (the "License");
5  you may not use this file except in compliance with the License.
6  You may obtain a copy of the License at
7 
8  http://www.apache.org/licenses/LICENSE-2.0
9 
10  Unless required by applicable law or agreed to in writing, software
11  distributed under the License is distributed on an "AS IS" BASIS,
12  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  See the License for the specific language governing permissions and
14  limitations under the License.
15 */
16 
17 #ifndef _TBB_custom_scheduler_H
18 #define _TBB_custom_scheduler_H
19 
20 #include "scheduler.h"
21 #include "observer_proxy.h"
22 #include "itt_notify.h"
23 
24 namespace tbb {
25 namespace internal {
26 
27 //------------------------------------------------------------------------
29 //------------------------------------------------------------------------
30 
32  static const bool itt_possible = true;
33  static const bool has_slow_atomic = false;
34 };
35 
37  static const bool itt_possible = false;
38 #if __TBB_x86_32||__TBB_x86_64
39  static const bool has_slow_atomic = true;
40 #else
41  static const bool has_slow_atomic = false;
42 #endif /* __TBB_x86_32||__TBB_x86_64 */
43 };
44 
45 //------------------------------------------------------------------------
46 // custom_scheduler
47 //------------------------------------------------------------------------
48 
50 
51 template<typename SchedulerTraits>
54 
56 
58 
61 
63 
66  static_cast<custom_scheduler*>(governor::local_scheduler())->scheduler_type::local_wait_for_all( parent, child );
67  }
68 
70 
73  task_prefix& p = s.prefix();
74  if( SchedulerTraits::itt_possible )
75  ITT_NOTIFY(sync_releasing, &p.ref_count);
76  if( SchedulerTraits::has_slow_atomic && p.ref_count==1 )
77  p.ref_count=0;
78  else if( __TBB_FetchAndDecrementWrelease(&p.ref_count) > 1 ) {// more references exist
79  // '__TBB_cl_evict(&p)' degraded performance of parallel_preorder example
80  return;
81  }
82 
83  // Ordering on p.ref_count (superfluous if SchedulerTraits::has_slow_atomic)
85  __TBB_ASSERT(p.ref_count==0, "completion of task caused predecessor's reference count to underflow");
86  if( SchedulerTraits::itt_possible )
87  ITT_NOTIFY(sync_acquired, &p.ref_count);
88 #if TBB_USE_ASSERT
89  p.extra_state &= ~es_ref_count_active;
90 #endif /* TBB_USE_ASSERT */
91 #if __TBB_TASK_ISOLATION
92  if ( isolation != no_isolation ) {
93  // The parent is allowed not to have isolation (even if a child has isolation) because it has never spawned.
94  __TBB_ASSERT(p.isolation == no_isolation || p.isolation == isolation, NULL);
95  p.isolation = isolation;
96  }
97 #endif /* __TBB_TASK_ISOLATION */
98 
99 #if __TBB_RECYCLE_TO_ENQUEUE
100  if (p.state==task::to_enqueue) {
101  // related to __TBB_TASK_ARENA TODO: try keep priority of the task
102  // e.g. rework task_prefix to remember priority of received task and use here
104  } else
105 #endif /*__TBB_RECYCLE_TO_ENQUEUE*/
106  if( bypass_slot==NULL )
107  bypass_slot = &s;
108 #if __TBB_PREVIEW_CRITICAL_TASKS
109  else if( internal::is_critical( s ) ) {
110  local_spawn( bypass_slot, bypass_slot->prefix().next );
111  bypass_slot = &s;
112  }
113 #endif /* __TBB_PREVIEW_CRITICAL_TASKS */
114  else
115  local_spawn( &s, s.prefix().next );
116  }
117 
118 public:
120  void* p = NFS_Allocate(1, sizeof(scheduler_type), NULL);
121  std::memset(p, 0, sizeof(scheduler_type));
122  scheduler_type* s = new( p ) scheduler_type( m );
123  s->assert_task_pool_valid();
124  ITT_SYNC_CREATE(s, SyncType_Scheduler, SyncObj_TaskPoolSpinning);
125  return s;
126  }
127 
129 
131 
132 }; // class custom_scheduler<>
133 
134 //------------------------------------------------------------------------
135 // custom_scheduler methods
136 //------------------------------------------------------------------------
137 template<typename SchedulerTraits>
139  task* t = NULL;
140  bool outermost_worker_level = worker_outermost_level();
141  bool outermost_dispatch_level = outermost_worker_level || master_outermost_level();
142  bool can_steal_here = can_steal();
143  my_inbox.set_is_idle( true );
144 #if __TBB_HOARD_NONLOCAL_TASKS
145  __TBB_ASSERT(!my_nonlocal_free_list, NULL);
146 #endif
147 #if __TBB_TASK_PRIORITY
148  if ( outermost_dispatch_level ) {
149  if ( intptr_t skipped_priority = my_arena->my_skipped_fifo_priority ) {
150  // This thread can dequeue FIFO tasks, and some priority levels of
151  // FIFO tasks have been bypassed (to prevent deadlock caused by
152  // dynamic priority changes in nested task group hierarchy).
153  if ( my_arena->my_skipped_fifo_priority.compare_and_swap(0, skipped_priority) == skipped_priority
154  && skipped_priority > my_arena->my_top_priority )
155  {
156  my_market->update_arena_priority( *my_arena, skipped_priority );
157  }
158  }
159  }
160 #endif /* !__TBB_TASK_PRIORITY */
161  // TODO: Try to find a place to reset my_limit (under market's lock)
162  // The number of slots potentially used in the arena. Updated once in a while, as my_limit changes rarely.
163  size_t n = my_arena->my_limit-1;
164  int yield_count = 0;
165  // The state "failure_count==-1" is used only when itt_possible is true,
166  // and denotes that a sync_prepare has not yet been issued.
167  for( int failure_count = -static_cast<int>(SchedulerTraits::itt_possible);; ++failure_count) {
168  __TBB_ASSERT( my_arena->my_limit > 0, NULL );
169  __TBB_ASSERT( my_arena_index <= n, NULL );
170  if( completion_ref_count==1 ) {
171  if( SchedulerTraits::itt_possible ) {
172  if( failure_count!=-1 ) {
173  ITT_NOTIFY(sync_prepare, &completion_ref_count);
174  // Notify Intel(R) Thread Profiler that thread has stopped spinning.
175  ITT_NOTIFY(sync_acquired, this);
176  }
177  ITT_NOTIFY(sync_acquired, &completion_ref_count);
178  }
179  __TBB_ASSERT( !t, NULL );
180  // A worker thread in its outermost dispatch loop (i.e. its execution stack is empty) should
181  // exit it either when there is no more work in the current arena, or when revoked by the market.
182  __TBB_ASSERT( !outermost_worker_level, NULL );
183  __TBB_control_consistency_helper(); // on ref_count
184  break; // exit stealing loop and return;
185  }
186  // Check if the resource manager requires our arena to relinquish some threads
187  if ( outermost_worker_level && (my_arena->my_num_workers_allotted < my_arena->num_workers_active()
188 #if __TBB_ENQUEUE_ENFORCED_CONCURRENCY
189  || my_arena->recall_by_mandatory_request()
190 #endif
191  ) ) {
192  if( SchedulerTraits::itt_possible && failure_count != -1 )
193  ITT_NOTIFY(sync_cancel, this);
194  return NULL;
195  }
196 #if __TBB_TASK_PRIORITY
197  const int p = int(my_arena->my_top_priority);
198 #else /* !__TBB_TASK_PRIORITY */
199  static const int p = 0;
200 #endif
201  // Check if there are tasks mailed to this thread via task-to-thread affinity mechanism.
202  __TBB_ASSERT(my_affinity_id, NULL);
203  if ( n && !my_inbox.empty() ) {
204  t = get_mailbox_task( __TBB_ISOLATION_EXPR( isolation ) );
205 #if __TBB_TASK_ISOLATION
206  // There is a race with a thread adding a new task (possibly with suitable isolation)
207  // to our mailbox, so the below conditions might result in a false positive.
208  // Then set_is_idle(false) allows that task to be stolen; it's OK.
209  if ( isolation != no_isolation && !t && !my_inbox.empty()
210  && my_inbox.is_idle_state( true ) ) {
211  // We have proxy tasks in our mailbox but the isolation blocks their execution.
212  // So publish the proxy tasks in mailbox to be available for stealing from owner's task pool.
213  my_inbox.set_is_idle( false );
214  }
215 #endif /* __TBB_TASK_ISOLATION */
216  }
217  if ( t ) {
218  GATHER_STATISTIC( ++my_counters.mails_received );
219  }
220  // Check if there are tasks in starvation-resistant stream.
221  // Only allowed at the outermost dispatch level without isolation.
222  else if (__TBB_ISOLATION_EXPR(isolation == no_isolation &&) outermost_dispatch_level &&
223  !my_arena->my_task_stream.empty(p) && (
224 #if __TBB_PREVIEW_CRITICAL_TASKS && __TBB_CPF_BUILD
225  t = my_arena->my_task_stream.pop( p, subsequent_lane_selector(my_arena_slot->hint_for_pop) )
226 #else
227  t = my_arena->my_task_stream.pop( p, my_arena_slot->hint_for_pop )
228 #endif
229  ) ) {
230  ITT_NOTIFY(sync_acquired, &my_arena->my_task_stream);
231  // just proceed with the obtained task
232  }
233 #if __TBB_TASK_PRIORITY
234  // Check if any earlier offloaded non-top priority tasks become returned to the top level
235  else if ( my_offloaded_tasks && (t = reload_tasks( __TBB_ISOLATION_EXPR( isolation ) )) ) {
236  __TBB_ASSERT( !is_proxy(*t), "The proxy task cannot be offloaded" );
237  // just proceed with the obtained task
238  }
239 #endif /* __TBB_TASK_PRIORITY */
240  else if ( can_steal_here && n && (t = steal_task( __TBB_ISOLATION_EXPR(isolation) )) ) {
241  // just proceed with the obtained task
242  }
243 #if __TBB_PREVIEW_CRITICAL_TASKS
244  else if( (t = get_critical_task( __TBB_ISOLATION_EXPR(isolation) )) ) {
245  __TBB_ASSERT( internal::is_critical(*t), "Received task must be critical one" );
246  ITT_NOTIFY(sync_acquired, &my_arena->my_critical_task_stream);
247  // just proceed with the obtained task
248  }
249 #endif // __TBB_PREVIEW_CRITICAL_TASKS
250  else
251  goto fail;
252  // A task was successfully obtained somewhere
253  __TBB_ASSERT(t,NULL);
254 #if __TBB_ARENA_OBSERVER
255  my_arena->my_observers.notify_entry_observers( my_last_local_observer, is_worker() );
256 #endif
257 #if __TBB_SCHEDULER_OBSERVER
258  the_global_observer_list.notify_entry_observers( my_last_global_observer, is_worker() );
259 #endif /* __TBB_SCHEDULER_OBSERVER */
260  if ( SchedulerTraits::itt_possible && failure_count != -1 ) {
261  // FIXME - might be victim, or might be selected from a mailbox
262  // Notify Intel(R) Thread Profiler that thread has stopped spinning.
263  ITT_NOTIFY(sync_acquired, this);
264  }
265  break; // exit stealing loop and return
266 fail:
267  GATHER_STATISTIC( ++my_counters.steals_failed );
268  if( SchedulerTraits::itt_possible && failure_count==-1 ) {
269  // The first attempt to steal work failed, so notify Intel(R) Thread Profiler that
270  // the thread has started spinning. Ideally, we would do this notification
271  // *before* the first failed attempt to steal, but at that point we do not
272  // know that the steal will fail.
273  ITT_NOTIFY(sync_prepare, this);
274  failure_count = 0;
275  }
276  // Pause, even if we are going to yield, because the yield might return immediately.
277  prolonged_pause();
278  const int failure_threshold = 2*int(n+1);
279  if( failure_count>=failure_threshold ) {
280 #if __TBB_YIELD2P
281  failure_count = 0;
282 #else
283  failure_count = failure_threshold;
284 #endif
285  __TBB_Yield();
286 #if __TBB_TASK_PRIORITY
287  // Check if there are tasks abandoned by other workers
288  if ( my_arena->my_orphaned_tasks ) {
289  // Epoch must be advanced before seizing the list pointer
290  ++my_arena->my_abandonment_epoch;
291  task* orphans = (task*)__TBB_FetchAndStoreW( &my_arena->my_orphaned_tasks, 0 );
292  if ( orphans ) {
293  task** link = NULL;
294  // Get local counter out of the way (we've just brought in external tasks)
295  my_local_reload_epoch--;
296  t = reload_tasks( orphans, link, __TBB_ISOLATION_ARG( effective_reference_priority(), isolation ) );
297  if ( orphans ) {
298  *link = my_offloaded_tasks;
299  if ( !my_offloaded_tasks )
300  my_offloaded_task_list_tail_link = link;
301  my_offloaded_tasks = orphans;
302  }
303  __TBB_ASSERT( !my_offloaded_tasks == !my_offloaded_task_list_tail_link, NULL );
304  if ( t ) {
305  if( SchedulerTraits::itt_possible )
306  ITT_NOTIFY(sync_cancel, this);
307  __TBB_ASSERT( !is_proxy(*t), "The proxy task cannot be offloaded" );
308  break; // exit stealing loop and return
309  }
310  }
311  }
312 #endif /* __TBB_TASK_PRIORITY */
313  const int yield_threshold = 100;
314  if( yield_count++ >= yield_threshold ) {
315  // When a worker thread has nothing to do, return it to RML.
316  // For purposes of affinity support, the thread is considered idle while in RML.
317 #if __TBB_TASK_PRIORITY
318  if( outermost_worker_level || my_arena->my_top_priority > my_arena->my_bottom_priority ) {
319  if ( my_arena->is_out_of_work() && outermost_worker_level ) {
320 #else /* !__TBB_TASK_PRIORITY */
321  if ( outermost_worker_level && my_arena->is_out_of_work() ) {
322 #endif /* !__TBB_TASK_PRIORITY */
323  if( SchedulerTraits::itt_possible )
324  ITT_NOTIFY(sync_cancel, this);
325  return NULL;
326  }
327 #if __TBB_TASK_PRIORITY
328  }
329  if ( my_offloaded_tasks ) {
330  // Safeguard against any sloppiness in managing reload epoch
331  // counter (e.g. on the hot path because of performance reasons).
332  my_local_reload_epoch--;
333  // Break the deadlock caused by a higher priority dispatch loop
334  // stealing and offloading a lower priority task. Priority check
335  // at the stealing moment cannot completely preclude such cases
336  // because priorities can changes dynamically.
337  if ( !outermost_worker_level && *my_ref_top_priority > my_arena->my_top_priority ) {
338  GATHER_STATISTIC( ++my_counters.prio_ref_fixups );
339  my_ref_top_priority = &my_arena->my_top_priority;
340  // it's expected that only outermost workers can use global reload epoch
341  __TBB_ASSERT(my_ref_reload_epoch == &my_arena->my_reload_epoch, NULL);
342  }
343  }
344 #endif /* __TBB_TASK_PRIORITY */
345  } // end of arena snapshot branch
346  // If several attempts did not find work, re-read the arena limit.
347  n = my_arena->my_limit-1;
348  } // end of yielding branch
349  } // end of nonlocal task retrieval loop
350  if ( my_inbox.is_idle_state( true ) )
351  my_inbox.set_is_idle( false );
352  return t;
353 }
354 
355 template<typename SchedulerTraits>
357  __TBB_ASSERT( governor::is_set(this), NULL );
358  __TBB_ASSERT( parent.ref_count() >= (child && child->parent() == &parent ? 2 : 1), "ref_count is too small" );
359  __TBB_ASSERT( my_innermost_running_task, NULL );
360  assert_task_pool_valid();
361  // Using parent's refcount in sync_prepare (in the stealing loop below) is
362  // a workaround for TP. We need to name it here to display correctly in Ampl.
363  if( SchedulerTraits::itt_possible )
364  ITT_SYNC_CREATE(&parent.prefix().ref_count, SyncType_Scheduler, SyncObj_TaskStealingLoop);
365 #if __TBB_TASK_GROUP_CONTEXT
366  __TBB_ASSERT( parent.prefix().context, "parent task does not have context" );
367 #endif /* __TBB_TASK_GROUP_CONTEXT */
368  task* t = child;
369  // Constant all_local_work_done is an unreachable refcount value that prevents
370  // early quitting the dispatch loop. It is defined to be in the middle of the range
371  // of negative values representable by the reference_count type.
372  static const reference_count
373  // For normal dispatch loops
374  parents_work_done = 1,
375  // For termination dispatch loops in masters
376  all_local_work_done = (reference_count)3 << (sizeof(reference_count) * 8 - 2);
377  reference_count quit_point;
378 #if __TBB_TASK_PRIORITY
379  __TBB_ASSERT( (uintptr_t)*my_ref_top_priority < (uintptr_t)num_priority_levels, NULL );
380  volatile intptr_t *old_ref_top_priority = my_ref_top_priority;
381  // When entering nested parallelism level market level counter
382  // must be replaced with the one local to this arena.
383  volatile uintptr_t *old_ref_reload_epoch = my_ref_reload_epoch;
384 #endif /* __TBB_TASK_PRIORITY */
385  task* old_innermost_running_task = my_innermost_running_task;
386  scheduler_properties old_properties = my_properties;
387  // Remove outermost property to indicate nested level.
388  __TBB_ASSERT( my_properties.outermost || my_innermost_running_task!=my_dummy_task, "The outermost property should be set out of a dispatch loop" );
389  my_properties.outermost &= my_innermost_running_task==my_dummy_task;
390 #if __TBB_TASK_ISOLATION
391  isolation_tag isolation = my_innermost_running_task->prefix().isolation;
392 #endif /* __TBB_TASK_ISOLATION */
393  if( master_outermost_level() ) {
394  // We are in the outermost task dispatch loop of a master thread or a worker which mimics master
395  quit_point = &parent == my_dummy_task ? all_local_work_done : parents_work_done;
396  } else {
397  quit_point = parents_work_done;
398 #if __TBB_TASK_PRIORITY
399  if ( &parent != my_dummy_task ) {
400  // We are in a nested dispatch loop.
401  // Market or arena priority must not prevent child tasks from being
402  // executed so that dynamic priority changes did not cause deadlock.
403  my_ref_top_priority = &parent.prefix().context->my_priority;
404  my_ref_reload_epoch = &my_arena->my_reload_epoch;
405  if(my_ref_reload_epoch != old_ref_reload_epoch)
406  my_local_reload_epoch = *my_ref_reload_epoch-1;
407  }
408 #endif /* __TBB_TASK_PRIORITY */
409  }
410 
411  context_guard_helper</*report_tasks=*/SchedulerTraits::itt_possible> context_guard;
412  if ( t ) {
413  context_guard.set_ctx( __TBB_CONTEXT_ARG1(t->prefix().context) );
414 #if __TBB_TASK_ISOLATION
415  if ( isolation != no_isolation ) {
416  __TBB_ASSERT( t->prefix().isolation == no_isolation, NULL );
417  // Propagate the isolation to the task executed without spawn.
418  t->prefix().isolation = isolation;
419  }
420 #endif /* __TBB_TASK_ISOLATION */
421  }
422 #if TBB_USE_EXCEPTIONS
423  // Infinite safeguard EH loop
424  for (;;) {
425  try {
426 #endif /* TBB_USE_EXCEPTIONS */
427  // Outer loop receives tasks from global environment (via mailbox, FIFO queue(s),
428  // and by stealing from other threads' task pools).
429  // All exit points from the dispatch loop are located in its immediate scope.
430  for(;;) {
431  // Middle loop retrieves tasks from the local task pool.
432  for(;;) {
433  // Inner loop evaluates tasks coming from nesting loops and those returned
434  // by just executed tasks (bypassing spawn or enqueue calls).
435  while(t) {
436  __TBB_ASSERT( my_inbox.is_idle_state(false), NULL );
437  __TBB_ASSERT(!is_proxy(*t),"unexpected proxy");
438  __TBB_ASSERT( t->prefix().owner, NULL );
439 #if __TBB_TASK_ISOLATION
440  __TBB_ASSERT( isolation == no_isolation || isolation == t->prefix().isolation,
441  "A task from another isolated region is going to be executed" );
442 #endif /* __TBB_TASK_ISOLATION */
444 #if __TBB_TASK_GROUP_CONTEXT && TBB_USE_ASSERT
445  assert_context_valid(t->prefix().context);
446  if ( !t->prefix().context->my_cancellation_requested )
447 #endif
448  // TODO: make the assert stronger by prohibiting allocated state.
449  __TBB_ASSERT( 1L<<t->state() & (1L<<task::allocated|1L<<task::ready|1L<<task::reexecute), NULL );
450  assert_task_pool_valid();
451 #if __TBB_PREVIEW_CRITICAL_TASKS
452  // TODO: check performance and optimize if needed for added conditions on the
453  // hot-path.
454  if( !internal::is_critical(*t) ) {
455  if( task* critical_task = get_critical_task( __TBB_ISOLATION_EXPR(isolation) ) ) {
456  __TBB_ASSERT( internal::is_critical(*critical_task),
457  "Received task must be critical one" );
458  ITT_NOTIFY(sync_acquired, &my_arena->my_critical_task_stream);
459  t->prefix().state = task::allocated;
460  my_innermost_running_task = t; // required during spawn to propagate isolation
461  local_spawn(t, t->prefix().next);
462  t = critical_task;
463  } else {
464 #endif /* __TBB_PREVIEW_CRITICAL_TASKS */
465 #if __TBB_TASK_PRIORITY
466  intptr_t p = priority(*t);
467  if ( p != *my_ref_top_priority
468  && (t->prefix().extra_state & es_task_enqueued) == 0 ) {
469  assert_priority_valid(p);
470  if ( p != my_arena->my_top_priority ) {
471  my_market->update_arena_priority( *my_arena, p );
472  }
473  if ( p < effective_reference_priority() ) {
474  if ( !my_offloaded_tasks ) {
475  my_offloaded_task_list_tail_link = &t->prefix().next_offloaded;
476  // Erase possible reference to the owner scheduler
477  // (next_offloaded is a union member)
478  *my_offloaded_task_list_tail_link = NULL;
479  }
480  offload_task( *t, p );
481  if ( is_task_pool_published() ) {
482  t = winnow_task_pool( __TBB_ISOLATION_EXPR( isolation ) );
483  if ( t )
484  continue;
485  } else {
486  // Mark arena as full to unlock arena priority level adjustment
487  // by arena::is_out_of_work(), and ensure worker's presence.
488  my_arena->advertise_new_work<arena::wakeup>();
489  }
490  goto stealing_ground;
491  }
492  }
493 #endif /* __TBB_TASK_PRIORITY */
494 #if __TBB_PREVIEW_CRITICAL_TASKS
495  }
496  } // if is not critical
497 #endif
498  task* t_next = NULL;
499  my_innermost_running_task = t;
500  t->prefix().owner = this;
501  t->prefix().state = task::executing;
502 #if __TBB_TASK_GROUP_CONTEXT
503  if ( !t->prefix().context->my_cancellation_requested )
504 #endif
505  {
506  GATHER_STATISTIC( ++my_counters.tasks_executed );
507  GATHER_STATISTIC( my_counters.avg_arena_concurrency += my_arena->num_workers_active() );
508  GATHER_STATISTIC( my_counters.avg_assigned_workers += my_arena->my_num_workers_allotted );
509 #if __TBB_TASK_PRIORITY
510  GATHER_STATISTIC( my_counters.avg_arena_prio += p );
511  GATHER_STATISTIC( my_counters.avg_market_prio += my_market->my_global_top_priority );
512 #endif /* __TBB_TASK_PRIORITY */
513  ITT_STACK(SchedulerTraits::itt_possible, callee_enter, t->prefix().context->itt_caller);
514 #if __TBB_PREVIEW_CRITICAL_TASKS
515  internal::critical_task_count_guard tc_guard(my_properties, *t);
516 #endif
517  t_next = t->execute();
518  ITT_STACK(SchedulerTraits::itt_possible, callee_leave, t->prefix().context->itt_caller);
519  if (t_next) {
520  __TBB_ASSERT( t_next->state()==task::allocated,
521  "if task::execute() returns task, it must be marked as allocated" );
522  reset_extra_state(t_next);
523  __TBB_ISOLATION_EXPR( t_next->prefix().isolation = t->prefix().isolation );
524 #if TBB_USE_ASSERT
525  affinity_id next_affinity=t_next->prefix().affinity;
526  if (next_affinity != 0 && next_affinity != my_affinity_id)
527  GATHER_STATISTIC( ++my_counters.affinity_ignored );
528 #endif
529  } // if there is bypassed task
530  }
531  assert_task_pool_valid();
532  switch( t->state() ) {
533  case task::executing: {
534  task* s = t->parent();
535  __TBB_ASSERT( my_innermost_running_task==t, NULL );
536  __TBB_ASSERT( t->prefix().ref_count==0, "Task still has children after it has been executed" );
537  t->~task();
538  if( s )
539  tally_completion_of_predecessor( *s, __TBB_ISOLATION_ARG( t_next, t->prefix().isolation ) );
540  free_task<no_hint>( *t );
541  poison_pointer( my_innermost_running_task );
542  assert_task_pool_valid();
543  break;
544  }
545 
546  case task::recycle: // set by recycle_as_safe_continuation()
547  t->prefix().state = task::allocated;
548 #if __TBB_RECYCLE_TO_ENQUEUE
550  case task::to_enqueue: // set by recycle_to_enqueue()
551 #endif
552  __TBB_ASSERT( t_next != t, "a task returned from method execute() can not be recycled in another way" );
554  // for safe continuation, need atomically decrement ref_count;
555  tally_completion_of_predecessor(*t, __TBB_ISOLATION_ARG( t_next, t->prefix().isolation ) );
556  assert_task_pool_valid();
557  break;
558 
559  case task::reexecute: // set by recycle_to_reexecute()
560  __TBB_ASSERT( t_next, "reexecution requires that method execute() return another task" );
561  __TBB_ASSERT( t_next != t, "a task returned from method execute() can not be recycled in another way" );
562  t->prefix().state = task::allocated;
564  local_spawn( t, t->prefix().next );
565  assert_task_pool_valid();
566  break;
567  case task::allocated:
569  break;
570 #if TBB_USE_ASSERT
571  case task::ready:
572  __TBB_ASSERT( false, "task is in READY state upon return from method execute()" );
573  break;
574  default:
575  __TBB_ASSERT( false, "illegal state" );
576 #else
577  default: // just to shut up some compilation warnings
578  break;
579 #endif /* TBB_USE_ASSERT */
580  }
581  GATHER_STATISTIC( t_next ? ++my_counters.spawns_bypassed : 0 );
582  t = t_next;
583  } // end of scheduler bypass loop
584 
585  assert_task_pool_valid();
586  if ( parent.prefix().ref_count == quit_point ) {
587  __TBB_ASSERT( quit_point != all_local_work_done, NULL );
588  __TBB_control_consistency_helper(); // on ref_count
589  ITT_NOTIFY(sync_acquired, &parent.prefix().ref_count);
590  goto done;
591  }
592  if ( is_task_pool_published() ) {
593  t = get_task( __TBB_ISOLATION_EXPR( isolation ) );
594  } else {
595  __TBB_ASSERT( is_quiescent_local_task_pool_reset(), NULL );
596  break;
597  }
598  assert_task_pool_valid();
599 
600  if ( !t ) break;
601 
602  context_guard.set_ctx( __TBB_CONTEXT_ARG1(t->prefix().context) );
603  }; // end of local task pool retrieval loop
604 
605 #if __TBB_TASK_PRIORITY
606 stealing_ground:
607 #endif /* __TBB_TASK_PRIORITY */
608 #if __TBB_HOARD_NONLOCAL_TASKS
609  // before stealing, previously stolen task objects are returned
610  for (; my_nonlocal_free_list; my_nonlocal_free_list = t ) {
611  t = my_nonlocal_free_list->prefix().next;
612  free_nonlocal_small_task( *my_nonlocal_free_list );
613  }
614 #endif
615  if ( quit_point == all_local_work_done ) {
616  __TBB_ASSERT( !is_task_pool_published() && is_quiescent_local_task_pool_reset(), NULL );
617  __TBB_ASSERT( !worker_outermost_level(), NULL );
618  my_innermost_running_task = old_innermost_running_task;
619  my_properties = old_properties;
620 #if __TBB_TASK_PRIORITY
621  my_ref_top_priority = old_ref_top_priority;
622  if(my_ref_reload_epoch != old_ref_reload_epoch)
623  my_local_reload_epoch = *old_ref_reload_epoch-1;
624  my_ref_reload_epoch = old_ref_reload_epoch;
625 #endif /* __TBB_TASK_PRIORITY */
626  return;
627  }
628 
629  t = receive_or_steal_task( __TBB_ISOLATION_ARG( parent.prefix().ref_count, isolation ) );
630  if ( !t )
631  goto done;
632  // The user can capture another the FPU settings to the context so the
633  // cached data in the helper can be out-of-date and we cannot do fast
634  // check.
635  context_guard.set_ctx( __TBB_CONTEXT_ARG1(t->prefix().context) );
636  } // end of infinite stealing loop
637 #if TBB_USE_EXCEPTIONS
638  __TBB_ASSERT( false, "Must never get here" );
639  } // end of try-block
640  TbbCatchAll( t->prefix().context );
641  // Complete post-processing ...
642  if( t->state() == task::recycle
643 #if __TBB_RECYCLE_TO_ENQUEUE
644  // TODO: the enqueue semantics gets lost below, consider reimplementing
645  || t->state() == task::to_enqueue
646 #endif
647  ) {
648  // ... for recycled tasks to atomically decrement ref_count
649  t->prefix().state = task::allocated;
650  if( SchedulerTraits::itt_possible )
651  ITT_NOTIFY(sync_releasing, &t->prefix().ref_count);
652  if( __TBB_FetchAndDecrementWrelease(&t->prefix().ref_count)==1 ) {
653  if( SchedulerTraits::itt_possible )
654  ITT_NOTIFY(sync_acquired, &t->prefix().ref_count);
655  }else{
656  t = NULL;
657  }
658  }
659  } // end of infinite EH loop
660  __TBB_ASSERT( false, "Must never get here too" );
661 #endif /* TBB_USE_EXCEPTIONS */
662 done:
663  my_innermost_running_task = old_innermost_running_task;
664  my_properties = old_properties;
665 #if __TBB_TASK_PRIORITY
666  my_ref_top_priority = old_ref_top_priority;
667  if(my_ref_reload_epoch != old_ref_reload_epoch)
668  my_local_reload_epoch = *old_ref_reload_epoch-1;
669  my_ref_reload_epoch = old_ref_reload_epoch;
670 #endif /* __TBB_TASK_PRIORITY */
671  if ( !ConcurrentWaitsEnabled(parent) ) {
672  if ( parent.prefix().ref_count != parents_work_done ) {
673  // This is a worker that was revoked by the market.
674  __TBB_ASSERT( worker_outermost_level(),
675  "Worker thread exits nested dispatch loop prematurely" );
676  return;
677  }
678  parent.prefix().ref_count = 0;
679  }
680 #if TBB_USE_ASSERT
681  parent.prefix().extra_state &= ~es_ref_count_active;
682 #endif /* TBB_USE_ASSERT */
683 #if __TBB_TASK_GROUP_CONTEXT
684  __TBB_ASSERT(parent.prefix().context && default_context(), NULL);
685  task_group_context* parent_ctx = parent.prefix().context;
686  if ( parent_ctx->my_cancellation_requested ) {
687  task_group_context::exception_container_type *pe = parent_ctx->my_exception;
688  if ( master_outermost_level() && parent_ctx == default_context() ) {
689  // We are in the outermost task dispatch loop of a master thread, and
690  // the whole task tree has been collapsed. So we may clear cancellation data.
691  parent_ctx->my_cancellation_requested = 0;
692  // TODO: Add assertion that master's dummy task context does not have children
693  parent_ctx->my_state &= ~(uintptr_t)task_group_context::may_have_children;
694  }
695  if ( pe ) {
696  // On Windows, FPU control settings changed in the helper destructor are not visible
697  // outside a catch block. So restore the default settings manually before rethrowing
698  // the exception.
699  context_guard.restore_default();
700  TbbRethrowException( pe );
701  }
702  }
703  __TBB_ASSERT(!is_worker() || !CancellationInfoPresent(*my_dummy_task),
704  "Worker's dummy task context modified");
705  __TBB_ASSERT(!master_outermost_level() || !CancellationInfoPresent(*my_dummy_task),
706  "Unexpected exception or cancellation data in the master's dummy task");
707 #endif /* __TBB_TASK_GROUP_CONTEXT */
708  assert_task_pool_valid();
709 }
710 
711 } // namespace internal
712 } // namespace tbb
713 
714 #endif /* _TBB_custom_scheduler_H */
static generic_scheduler * local_scheduler()
Obtain the thread-local instance of the TBB scheduler.
Definition: governor.h:122
static const intptr_t num_priority_levels
#define __TBB_override
Definition: tbb_stddef.h:240
internal::tbb_exception_ptr exception_container_type
Definition: task.h:341
void local_wait_for_all(task &parent, task *child) __TBB_override
Scheduler loop that dispatches tasks.
#define __TBB_ISOLATION_EXPR(isolation)
intptr_t reference_count
A reference count.
Definition: task.h:117
void set_ctx(__TBB_CONTEXT_ARG1(task_group_context *))
Definition: scheduler.h:807
void local_spawn(task *first, task *&next)
Definition: scheduler.cpp:614
#define ITT_SYNC_CREATE(obj, type, name)
Definition: itt_notify.h:119
void const char const char int ITT_FORMAT __itt_group_sync s
Memory prefix to a task object.
Definition: task.h:184
#define __TBB_FetchAndDecrementWrelease(P)
Definition: tbb_machine.h:311
#define GATHER_STATISTIC(x)
void poison_pointer(T *__TBB_atomic &)
Definition: tbb_stddef.h:305
custom_scheduler< SchedulerTraits > scheduler_type
state_type state() const
Current execution state.
Definition: task.h:864
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p sync_cancel
The graph class.
void wait_for_all(task &parent, task *child) __TBB_override
Entry point from client code to the scheduler loop that dispatches tasks.
Used to form groups of tasks.
Definition: task.h:332
arena * my_arena
The arena that I own (if master) or am servicing at the moment (if worker)
Definition: scheduler.h:74
task object is freshly allocated or recycled.
Definition: task.h:617
Bit-field representing properties of a sheduler.
Definition: scheduler.h:46
void tally_completion_of_predecessor(task &s, __TBB_ISOLATION_ARG(task *&bypass_slot, isolation_tag isolation))
Decrements ref_count of a predecessor.
internal::task_prefix & prefix(internal::version_tag *=NULL) const
Get reference to corresponding task_prefix.
Definition: task.h:946
unsigned short affinity_id
An id as used for specifying affinity.
Definition: task.h:120
#define ITT_STACK(precond, name, obj)
Definition: itt_notify.h:122
FastRandom my_random
Random number generator used for picking a random victim from which to steal.
Definition: scheduler.h:158
task to be rescheduled.
Definition: task.h:613
static bool is_set(generic_scheduler *s)
Used to check validity of the local scheduler TLS contents.
Definition: governor.cpp:120
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id parent
#define __TBB_fallthrough
Definition: tbb_stddef.h:250
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:165
void assert_task_valid(const task *)
bool ConcurrentWaitsEnabled(task &t)
#define __TBB_control_consistency_helper()
Definition: gcc_generic.h:60
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p sync_releasing
#define __TBB_Yield()
Definition: ibm_aix51.h:44
Base class for user-defined tasks.
Definition: task.h:589
Work stealing task scheduler.
Definition: scheduler.h:120
task * receive_or_steal_task(__TBB_ISOLATION_ARG(__TBB_atomic reference_count &completion_ref_count, isolation_tag isolation)) __TBB_override
Try getting a task from the mailbox or stealing from another scheduler.
static generic_scheduler * allocate_scheduler(market &m)
Traits classes for scheduler.
virtual task * execute()=0
Should be overridden by derived classes.
#define __TBB_CONTEXT_ARG1(context)
#define ITT_NOTIFY(name, obj)
Definition: itt_notify.h:116
bool is_critical(task &t)
Definition: task.h:958
Set if ref_count might be changed by another thread. Used for debugging.
intptr_t isolation_tag
A tag for task isolation.
Definition: task.h:124
task * parent() const
task on whose behalf this task is working, or NULL if this is a root.
Definition: task.h:835
A scheduler with a customized evaluation loop.
#define __TBB_ISOLATION_ARG(arg1, isolation)
const isolation_tag no_isolation
Definition: task.h:125
task to be recycled as continuation
Definition: task.h:621
#define __TBB_atomic
Definition: tbb_stddef.h:237
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT p const __itt_domain __itt_id __itt_timestamp __itt_timestamp ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain ITT_FORMAT p const __itt_domain __itt_string_handle unsigned long long ITT_FORMAT lu const __itt_domain __itt_id __itt_string_handle __itt_metadata_type size_t void ITT_FORMAT p const __itt_domain __itt_id __itt_string_handle const wchar_t size_t ITT_FORMAT lu const __itt_domain __itt_id __itt_relation __itt_id ITT_FORMAT p const wchar_t int ITT_FORMAT __itt_group_mark d int
task is in ready pool, or is going to be put there, or was just taken off.
Definition: task.h:615
void const char const char int ITT_FORMAT __itt_group_sync p
void reset_extra_state(task *t)
task is running, and will be destroyed after method execute() completes.
Definition: task.h:611
void enqueue_task(task &, intptr_t, FastRandom &)
enqueue a task into starvation-resistance queue
Definition: arena.cpp:554
void *__TBB_EXPORTED_FUNC NFS_Allocate(size_t n_element, size_t element_size, void *hint)
Allocate memory on cache/sector line boundary.

Copyright © 2005-2019 Intel Corporation. All Rights Reserved.

Intel, Pentium, Intel Xeon, Itanium, Intel XScale and VTune are registered trademarks or trademarks of Intel Corporation or its subsidiaries in the United States and other countries.

* Other names and brands may be claimed as the property of others.