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

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.