Intel(R) Threading Building Blocks Doxygen Documentation  version 4.2.3
scheduler.cpp
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 #include "custom_scheduler.h"
18 #include "scheduler_utility.h"
19 #include "governor.h"
20 #include "market.h"
21 #include "arena.h"
22 #include "mailbox.h"
23 #include "observer_proxy.h"
24 #include "tbb/tbb_machine.h"
25 #include "tbb/atomic.h"
26 
27 namespace tbb {
28 namespace internal {
29 
30 //------------------------------------------------------------------------
31 // Library initialization
32 //------------------------------------------------------------------------
33 
35 extern generic_scheduler* (*AllocateSchedulerPtr)( market& );
36 
38  return AllocateSchedulerPtr( m );
39 }
40 
41 #if __TBB_TASK_GROUP_CONTEXT
42 context_state_propagation_mutex_type the_context_state_propagation_mutex;
43 
44 uintptr_t the_context_state_propagation_epoch = 0;
45 
47 
49 static task_group_context the_dummy_context(task_group_context::isolated);
50 #endif /* __TBB_TASK_GROUP_CONTEXT */
51 
52 void Scheduler_OneTimeInitialization ( bool itt_present ) {
55 #if __TBB_TASK_GROUP_CONTEXT
56  // There must be no tasks belonging to this fake task group. Mark invalid for the assert
59 #if __TBB_TASK_PRIORITY
60  // It should never prevent tasks from being passed to execution.
61  the_dummy_context.my_priority = num_priority_levels - 1;
62 #endif /* __TBB_TASK_PRIORITY */
63 #endif /* __TBB_TASK_GROUP_CONTEXT */
64 }
65 
66 //------------------------------------------------------------------------
67 // scheduler interface
68 //------------------------------------------------------------------------
69 
70 // A pure virtual destructor should still have a body
71 // so the one for tbb::internal::scheduler::~scheduler() is provided here
73 
74 //------------------------------------------------------------------------
75 // generic_scheduler
76 //------------------------------------------------------------------------
77 
78 #if _MSC_VER && !defined(__INTEL_COMPILER)
79  // Suppress overzealous compiler warning about using 'this' in base initializer list.
80  #pragma warning(push)
81  #pragma warning(disable:4355)
82 #endif
83 
85  : my_market(&m)
86  , my_random(this)
87  , my_ref_count(1)
88  , my_small_task_count(1) // Extra 1 is a guard reference
89 #if __TBB_SURVIVE_THREAD_SWITCH && TBB_USE_ASSERT
90  , my_cilk_state(cs_none)
91 #endif /* __TBB_SURVIVE_THREAD_SWITCH && TBB_USE_ASSERT */
92 {
93  __TBB_ASSERT( !my_arena_index, "constructor expects the memory being zero-initialized" );
94  __TBB_ASSERT( governor::is_set(NULL), "scheduler is already initialized for this thread" );
95 
96  my_innermost_running_task = my_dummy_task = &allocate_task( sizeof(task), __TBB_CONTEXT_ARG(NULL, &the_dummy_context) );
97 #if __TBB_PREVIEW_CRITICAL_TASKS
98  my_properties.has_taken_critical_task = false;
99 #endif
100  my_properties.outermost = true;
101 #if __TBB_TASK_PRIORITY
102  my_ref_top_priority = &m.my_global_top_priority;
103  my_ref_reload_epoch = &m.my_global_reload_epoch;
104 #endif /* __TBB_TASK_PRIORITY */
105 #if __TBB_TASK_GROUP_CONTEXT
106  // Sync up the local cancellation state with the global one. No need for fence here.
107  my_context_state_propagation_epoch = the_context_state_propagation_epoch;
108  my_context_list_head.my_prev = &my_context_list_head;
109  my_context_list_head.my_next = &my_context_list_head;
110  ITT_SYNC_CREATE(&my_context_list_mutex, SyncType_Scheduler, SyncObj_ContextsList);
111 #endif /* __TBB_TASK_GROUP_CONTEXT */
112  ITT_SYNC_CREATE(&my_dummy_task->prefix().ref_count, SyncType_Scheduler, SyncObj_WorkerLifeCycleMgmt);
113  ITT_SYNC_CREATE(&my_return_list, SyncType_Scheduler, SyncObj_TaskReturnList);
114 }
115 
116 #if _MSC_VER && !defined(__INTEL_COMPILER)
117  #pragma warning(pop)
118 #endif // warning 4355 is back
119 
120 #if TBB_USE_ASSERT > 1
122  if ( !my_arena_slot )
123  return;
128  const size_t H = __TBB_load_relaxed(my_arena_slot->head); // mirror
129  const size_t T = __TBB_load_relaxed(my_arena_slot->tail); // mirror
130  __TBB_ASSERT( H <= T, NULL );
131  for ( size_t i = 0; i < H; ++i )
132  __TBB_ASSERT( tp[i] == poisoned_ptr, "Task pool corrupted" );
133  for ( size_t i = H; i < T; ++i ) {
134  if ( tp[i] ) {
135  assert_task_valid( tp[i] );
136  __TBB_ASSERT( tp[i]->prefix().state == task::ready ||
137  tp[i]->prefix().extra_state == es_task_proxy, "task in the deque has invalid state" );
138  }
139  }
140  for ( size_t i = T; i < my_arena_slot->my_task_pool_size; ++i )
141  __TBB_ASSERT( tp[i] == poisoned_ptr, "Task pool corrupted" );
143 }
144 #endif /* TBB_USE_ASSERT > 1 */
145 
147  // Stacks are growing top-down. Highest address is called "stack base",
148  // and the lowest is "stack limit".
149  __TBB_ASSERT( !my_stealing_threshold, "Stealing threshold has already been calculated" );
150  size_t stack_size = my_market->worker_stack_size();
151 #if USE_WINTHREAD
152 #if defined(_MSC_VER)&&_MSC_VER<1400 && !_WIN64
153  NT_TIB *pteb;
154  __asm mov eax, fs:[0x18]
155  __asm mov pteb, eax
156 #else
157  NT_TIB *pteb = (NT_TIB*)NtCurrentTeb();
158 #endif
159  __TBB_ASSERT( &pteb < pteb->StackBase && &pteb > pteb->StackLimit, "invalid stack info in TEB" );
160  __TBB_ASSERT( stack_size >0, "stack_size not initialized?" );
161  // When a thread is created with the attribute STACK_SIZE_PARAM_IS_A_RESERVATION, stack limit
162  // in the TIB points to the committed part of the stack only. This renders the expression
163  // "(uintptr_t)pteb->StackBase / 2 + (uintptr_t)pteb->StackLimit / 2" virtually useless.
164  // Thus for worker threads we use the explicit stack size we used while creating them.
165  // And for master threads we rely on the following fact and assumption:
166  // - the default stack size of a master thread on Windows is 1M;
167  // - if it was explicitly set by the application it is at least as large as the size of a worker stack.
168  if ( is_worker() || stack_size < MByte )
169  my_stealing_threshold = (uintptr_t)pteb->StackBase - stack_size / 2;
170  else
171  my_stealing_threshold = (uintptr_t)pteb->StackBase - MByte / 2;
172 #else /* USE_PTHREAD */
173  // There is no portable way to get stack base address in Posix, so we use
174  // non-portable method (on all modern Linux) or the simplified approach
175  // based on the common sense assumptions. The most important assumption
176  // is that the main thread's stack size is not less than that of other threads.
177  // See also comment 3 at the end of this file
178  void *stack_base = &stack_size;
179 #if __linux__ && !__bg__
180 #if __TBB_ipf
181  void *rsb_base = __TBB_get_bsp();
182 #endif
183  size_t np_stack_size = 0;
184  void *stack_limit = NULL;
185  pthread_attr_t np_attr_stack;
186  if( 0 == pthread_getattr_np(pthread_self(), &np_attr_stack) ) {
187  if ( 0 == pthread_attr_getstack(&np_attr_stack, &stack_limit, &np_stack_size) ) {
188 #if __TBB_ipf
189  pthread_attr_t attr_stack;
190  if ( 0 == pthread_attr_init(&attr_stack) ) {
191  if ( 0 == pthread_attr_getstacksize(&attr_stack, &stack_size) ) {
192  if ( np_stack_size < stack_size ) {
193  // We are in a secondary thread. Use reliable data.
194  // IA-64 architecture stack is split into RSE backup and memory parts
195  rsb_base = stack_limit;
196  stack_size = np_stack_size/2;
197  // Limit of the memory part of the stack
198  stack_limit = (char*)stack_limit + stack_size;
199  }
200  // We are either in the main thread or this thread stack
201  // is bigger that that of the main one. As we cannot discern
202  // these cases we fall back to the default (heuristic) values.
203  }
204  pthread_attr_destroy(&attr_stack);
205  }
206  // IA-64 architecture stack is split into RSE backup and memory parts
207  my_rsb_stealing_threshold = (uintptr_t)((char*)rsb_base + stack_size/2);
208 #endif /* __TBB_ipf */
209  // Size of the stack free part
210  stack_size = size_t((char*)stack_base - (char*)stack_limit);
211  }
212  pthread_attr_destroy(&np_attr_stack);
213  }
214 #endif /* __linux__ */
215  __TBB_ASSERT( stack_size>0, "stack size must be positive" );
216  my_stealing_threshold = (uintptr_t)((char*)stack_base - stack_size/2);
217 #endif /* USE_PTHREAD */
218 }
219 
220 #if __TBB_TASK_GROUP_CONTEXT
221 
226 void generic_scheduler::cleanup_local_context_list () {
227  // Detach contexts remaining in the local list
228  bool wait_for_concurrent_destroyers_to_leave = false;
229  uintptr_t local_count_snapshot = my_context_state_propagation_epoch;
230  my_local_ctx_list_update.store<relaxed>(1);
231  {
232  // This is just a definition. Actual lock is acquired only in case of conflict.
234  // Full fence prevents reordering of store to my_local_ctx_list_update with
235  // load from my_nonlocal_ctx_list_update.
236  atomic_fence();
237  // Check for the conflict with concurrent destroyer or cancellation propagator
238  if ( my_nonlocal_ctx_list_update.load<relaxed>() || local_count_snapshot != the_context_state_propagation_epoch )
239  lock.acquire(my_context_list_mutex);
240  // No acquire fence is necessary for loading my_context_list_head.my_next,
241  // as the list can be updated by this thread only.
242  context_list_node_t *node = my_context_list_head.my_next;
243  while ( node != &my_context_list_head ) {
245  __TBB_ASSERT( __TBB_load_relaxed(ctx.my_kind) != task_group_context::binding_required, "Only a context bound to a root task can be detached" );
246  node = node->my_next;
247  __TBB_ASSERT( is_alive(ctx.my_version_and_traits), "Walked into a destroyed context while detaching contexts from the local list" );
248  // Synchronizes with ~task_group_context(). TODO: evaluate and perhaps relax
250  wait_for_concurrent_destroyers_to_leave = true;
251  }
252  }
253  my_local_ctx_list_update.store<release>(0);
254  // Wait until other threads referencing this scheduler object finish with it
255  if ( wait_for_concurrent_destroyers_to_leave )
256  spin_wait_until_eq( my_nonlocal_ctx_list_update, 0u );
257 }
258 #endif /* __TBB_TASK_GROUP_CONTEXT */
259 
261  __TBB_ASSERT( !my_arena_slot, NULL );
262 #if __TBB_PREVIEW_CRITICAL_TASKS
263  __TBB_ASSERT( !my_properties.has_taken_critical_task, "Critical tasks miscount." );
264 #endif
265 #if __TBB_TASK_GROUP_CONTEXT
266  cleanup_local_context_list();
267 #endif /* __TBB_TASK_GROUP_CONTEXT */
268  free_task<small_local_task>( *my_dummy_task );
269 
270 #if __TBB_HOARD_NONLOCAL_TASKS
271  while( task* t = my_nonlocal_free_list ) {
272  task_prefix& p = t->prefix();
273  my_nonlocal_free_list = p.next;
274  __TBB_ASSERT( p.origin && p.origin!=this, NULL );
276  }
277 #endif
278  // k accounts for a guard reference and each task that we deallocate.
279  intptr_t k = 1;
280  for(;;) {
281  while( task* t = my_free_list ) {
282  my_free_list = t->prefix().next;
283  deallocate_task(*t);
284  ++k;
285  }
287  break;
288  my_free_list = (task*)__TBB_FetchAndStoreW( &my_return_list, (intptr_t)plugged_return_list() );
289  }
290 #if __TBB_COUNT_TASK_NODES
291  my_market->update_task_node_count( my_task_node_count );
292 #endif /* __TBB_COUNT_TASK_NODES */
293  // Update my_small_task_count last. Doing so sooner might cause another thread to free *this.
294  __TBB_ASSERT( my_small_task_count>=k, "my_small_task_count corrupted" );
295  governor::sign_off(this);
296  if( __TBB_FetchAndAddW( &my_small_task_count, -k )==k )
297  NFS_Free( this );
298 }
299 
300 task& generic_scheduler::allocate_task( size_t number_of_bytes,
302  GATHER_STATISTIC(++my_counters.active_tasks);
303  task *t;
304  if( number_of_bytes<=quick_task_size ) {
305 #if __TBB_HOARD_NONLOCAL_TASKS
306  if( (t = my_nonlocal_free_list) ) {
307  GATHER_STATISTIC(--my_counters.free_list_length);
308  __TBB_ASSERT( t->state()==task::freed, "free list of tasks is corrupted" );
309  my_nonlocal_free_list = t->prefix().next;
310  } else
311 #endif
312  if( (t = my_free_list) ) {
313  GATHER_STATISTIC(--my_counters.free_list_length);
314  __TBB_ASSERT( t->state()==task::freed, "free list of tasks is corrupted" );
315  my_free_list = t->prefix().next;
316  } else if( my_return_list ) {
317  // No fence required for read of my_return_list above, because __TBB_FetchAndStoreW has a fence.
318  t = (task*)__TBB_FetchAndStoreW( &my_return_list, 0 ); // with acquire
319  __TBB_ASSERT( t, "another thread emptied the my_return_list" );
320  __TBB_ASSERT( t->prefix().origin==this, "task returned to wrong my_return_list" );
321  ITT_NOTIFY( sync_acquired, &my_return_list );
322  my_free_list = t->prefix().next;
323  } else {
325 #if __TBB_COUNT_TASK_NODES
326  ++my_task_node_count;
327 #endif /* __TBB_COUNT_TASK_NODES */
328  t->prefix().origin = this;
329  t->prefix().next = 0;
331  }
332 #if __TBB_PREFETCHING
333  task *t_next = t->prefix().next;
334  if( !t_next ) { // the task was last in the list
335 #if __TBB_HOARD_NONLOCAL_TASKS
336  if( my_free_list )
337  t_next = my_free_list;
338  else
339 #endif
340  if( my_return_list ) // enable prefetching, gives speedup
341  t_next = my_free_list = (task*)__TBB_FetchAndStoreW( &my_return_list, 0 );
342  }
343  if( t_next ) { // gives speedup for both cache lines
344  __TBB_cl_prefetch(t_next);
345  __TBB_cl_prefetch(&t_next->prefix());
346  }
347 #endif /* __TBB_PREFETCHING */
348  } else {
349  GATHER_STATISTIC(++my_counters.big_tasks);
350  t = (task*)((char*)NFS_Allocate( 1, task_prefix_reservation_size+number_of_bytes, NULL ) + task_prefix_reservation_size );
351 #if __TBB_COUNT_TASK_NODES
352  ++my_task_node_count;
353 #endif /* __TBB_COUNT_TASK_NODES */
354  t->prefix().origin = NULL;
355  }
356  task_prefix& p = t->prefix();
357 #if __TBB_TASK_GROUP_CONTEXT
358  p.context = context;
359 #endif /* __TBB_TASK_GROUP_CONTEXT */
360  // Obsolete. But still in use, so has to be assigned correct value here.
361  p.owner = this;
362  p.ref_count = 0;
363  // Obsolete. Assign some not outrageously out-of-place value for a while.
364  p.depth = 0;
365  p.parent = parent;
366  // In TBB 2.1 and later, the constructor for task sets extra_state to indicate the version of the tbb/task.h header.
367  // In TBB 2.0 and earlier, the constructor leaves extra_state as zero.
368  p.extra_state = 0;
369  p.affinity = 0;
372  return *t;
373 }
374 
376  __TBB_ASSERT( t.state()==task::freed, NULL );
377  generic_scheduler& s = *static_cast<generic_scheduler*>(t.prefix().origin);
378  __TBB_ASSERT( &s!=this, NULL );
379  for(;;) {
380  task* old = s.my_return_list;
381  if( old==plugged_return_list() )
382  break;
383  // Atomically insert t at head of s.my_return_list
384  t.prefix().next = old;
385  ITT_NOTIFY( sync_releasing, &s.my_return_list );
386  if( as_atomic(s.my_return_list).compare_and_swap(&t, old )==old ) {
387 #if __TBB_PREFETCHING
388  __TBB_cl_evict(&t.prefix());
389  __TBB_cl_evict(&t);
390 #endif
391  return;
392  }
393  }
394  deallocate_task(t);
395  if( __TBB_FetchAndDecrementWrelease( &s.my_small_task_count )==1 ) {
396  // We freed the last task allocated by scheduler s, so it's our responsibility
397  // to free the scheduler.
398  NFS_Free( &s );
399  }
400 }
401 
402 inline size_t generic_scheduler::prepare_task_pool ( size_t num_tasks ) {
403  size_t T = __TBB_load_relaxed(my_arena_slot->tail); // mirror
404  if ( T + num_tasks <= my_arena_slot->my_task_pool_size )
405  return T;
406 
407  size_t new_size = num_tasks;
408 
412  if ( num_tasks < min_task_pool_size ) new_size = min_task_pool_size;
413  my_arena_slot->allocate_task_pool( new_size );
414  return 0;
415  }
416 
418  size_t H = __TBB_load_relaxed( my_arena_slot->head ); // mirror
419  task** task_pool = my_arena_slot->task_pool_ptr;;
421  // Count not skipped tasks. Consider using std::count_if.
422  for ( size_t i = H; i < T; ++i )
423  if ( task_pool[i] ) ++new_size;
424  // If the free space at the beginning of the task pool is too short, we
425  // are likely facing a pathological single-producer-multiple-consumers
426  // scenario, and thus it's better to expand the task pool
427  bool allocate = new_size > my_arena_slot->my_task_pool_size - min_task_pool_size/4;
428  if ( allocate ) {
429  // Grow task pool. As this operation is rare, and its cost is asymptotically
430  // amortizable, we can tolerate new task pool allocation done under the lock.
431  if ( new_size < 2 * my_arena_slot->my_task_pool_size )
432  new_size = 2 * my_arena_slot->my_task_pool_size;
433  my_arena_slot->allocate_task_pool( new_size ); // updates my_task_pool_size
434  }
435  // Filter out skipped tasks. Consider using std::copy_if.
436  size_t T1 = 0;
437  for ( size_t i = H; i < T; ++i )
438  if ( task_pool[i] )
439  my_arena_slot->task_pool_ptr[T1++] = task_pool[i];
440  // Deallocate the previous task pool if a new one has been allocated.
441  if ( allocate )
442  NFS_Free( task_pool );
443  else
445  // Publish the new state.
448  return T1;
449 }
450 
457  if ( !is_task_pool_published() )
458  return; // we are not in arena - nothing to lock
459  bool sync_prepare_done = false;
460  for( atomic_backoff b;;b.pause() ) {
461 #if TBB_USE_ASSERT
462  __TBB_ASSERT( my_arena_slot == my_arena->my_slots + my_arena_index, "invalid arena slot index" );
463  // Local copy of the arena slot task pool pointer is necessary for the next
464  // assertion to work correctly to exclude asynchronous state transition effect.
465  task** tp = my_arena_slot->task_pool;
466  __TBB_ASSERT( tp == LockedTaskPool || tp == my_arena_slot->task_pool_ptr, "slot ownership corrupt?" );
467 #endif
470  {
471  // We acquired our own slot
472  ITT_NOTIFY(sync_acquired, my_arena_slot);
473  break;
474  }
475  else if( !sync_prepare_done ) {
476  // Start waiting
477  ITT_NOTIFY(sync_prepare, my_arena_slot);
478  sync_prepare_done = true;
479  }
480  // Someone else acquired a lock, so pause and do exponential backoff.
481  }
482  __TBB_ASSERT( my_arena_slot->task_pool == LockedTaskPool, "not really acquired task pool" );
483 } // generic_scheduler::acquire_task_pool
484 
486  if ( !is_task_pool_published() )
487  return; // we are not in arena - nothing to unlock
488  __TBB_ASSERT( my_arena_slot, "we are not in arena" );
489  __TBB_ASSERT( my_arena_slot->task_pool == LockedTaskPool, "arena slot is not locked" );
492 }
493 
500 inline task** generic_scheduler::lock_task_pool( arena_slot* victim_arena_slot ) const {
501  task** victim_task_pool;
502  bool sync_prepare_done = false;
503  for( atomic_backoff backoff;; /*backoff pause embedded in the loop*/) {
504  victim_task_pool = victim_arena_slot->task_pool;
505  // NOTE: Do not use comparison of head and tail indices to check for
506  // the presence of work in the victim's task pool, as they may give
507  // incorrect indication because of task pool relocations and resizes.
508  if ( victim_task_pool == EmptyTaskPool ) {
509  // The victim thread emptied its task pool - nothing to lock
510  if( sync_prepare_done )
511  ITT_NOTIFY(sync_cancel, victim_arena_slot);
512  break;
513  }
514  if( victim_task_pool != LockedTaskPool &&
515  as_atomic(victim_arena_slot->task_pool).compare_and_swap(LockedTaskPool, victim_task_pool ) == victim_task_pool )
516  {
517  // We've locked victim's task pool
518  ITT_NOTIFY(sync_acquired, victim_arena_slot);
519  break;
520  }
521  else if( !sync_prepare_done ) {
522  // Start waiting
523  ITT_NOTIFY(sync_prepare, victim_arena_slot);
524  sync_prepare_done = true;
525  }
526  GATHER_STATISTIC( ++my_counters.thieves_conflicts );
527  // Someone else acquired a lock, so pause and do exponential backoff.
528 #if __TBB_STEALING_ABORT_ON_CONTENTION
529  if(!backoff.bounded_pause()) {
530  // the 16 was acquired empirically and a theory behind it supposes
531  // that number of threads becomes much bigger than number of
532  // tasks which can be spawned by one thread causing excessive contention.
533  // TODO: However even small arenas can benefit from the abort on contention
534  // if preemption of a thief is a problem
535  if(my_arena->my_limit >= 16)
536  return EmptyTaskPool;
537  __TBB_Yield();
538  }
539 #else
540  backoff.pause();
541 #endif
542  }
543  __TBB_ASSERT( victim_task_pool == EmptyTaskPool ||
544  (victim_arena_slot->task_pool == LockedTaskPool && victim_task_pool != LockedTaskPool),
545  "not really locked victim's task pool?" );
546  return victim_task_pool;
547 } // generic_scheduler::lock_task_pool
548 
549 inline void generic_scheduler::unlock_task_pool( arena_slot* victim_arena_slot,
550  task** victim_task_pool ) const {
551  __TBB_ASSERT( victim_arena_slot, "empty victim arena slot pointer" );
552  __TBB_ASSERT( victim_arena_slot->task_pool == LockedTaskPool, "victim arena slot is not locked" );
553  ITT_NOTIFY(sync_releasing, victim_arena_slot);
554  __TBB_store_with_release( victim_arena_slot->task_pool, victim_task_pool );
555 }
556 
557 
559  __TBB_ASSERT( t->state()==task::allocated, "attempt to spawn task that is not in 'allocated' state" );
560  t->prefix().state = task::ready;
561 #if TBB_USE_ASSERT
562  if( task* parent = t->parent() ) {
563  internal::reference_count ref_count = parent->prefix().ref_count;
564  __TBB_ASSERT( ref_count>=0, "attempt to spawn task whose parent has a ref_count<0" );
565  __TBB_ASSERT( ref_count!=0, "attempt to spawn task whose parent has a ref_count==0 (forgot to set_ref_count?)" );
566  parent->prefix().extra_state |= es_ref_count_active;
567  }
568 #endif /* TBB_USE_ASSERT */
569  affinity_id dst_thread = t->prefix().affinity;
570  __TBB_ASSERT( dst_thread == 0 || is_version_3_task(*t),
571  "backwards compatibility to TBB 2.0 tasks is broken" );
572 #if __TBB_TASK_ISOLATION
573  isolation_tag isolation = my_innermost_running_task->prefix().isolation;
574  t->prefix().isolation = isolation;
575 #endif /* __TBB_TASK_ISOLATION */
576  if( dst_thread != 0 && dst_thread != my_affinity_id ) {
577  task_proxy& proxy = (task_proxy&)allocate_task( sizeof(task_proxy),
578  __TBB_CONTEXT_ARG(NULL, NULL) );
579  // Mark as a proxy
580  proxy.prefix().extra_state = es_task_proxy;
581  proxy.outbox = &my_arena->mailbox(dst_thread);
582  // Mark proxy as present in both locations (sender's task pool and destination mailbox)
583  proxy.task_and_tag = intptr_t(t) | task_proxy::location_mask;
584 #if __TBB_TASK_PRIORITY
585  poison_pointer( proxy.prefix().context );
586 #endif /* __TBB_TASK_PRIORITY */
587  __TBB_ISOLATION_EXPR( proxy.prefix().isolation = isolation );
588  ITT_NOTIFY( sync_releasing, proxy.outbox );
589  // Mail the proxy - after this point t may be destroyed by another thread at any moment.
590  proxy.outbox->push(&proxy);
591  return &proxy;
592  }
593  return t;
594 }
595 
596 #if __TBB_PREVIEW_CRITICAL_TASKS
597 bool generic_scheduler::handled_as_critical( task& t ) {
598  if( !internal::is_critical( t ) )
599  return false;
600 #if __TBB_TASK_ISOLATION
601  t.prefix().isolation = my_innermost_running_task->prefix().isolation;
602 #endif
603  ITT_NOTIFY(sync_releasing, &my_arena->my_critical_task_stream);
604  __TBB_ASSERT( my_arena, "Must be attached to the arena." );
605  __TBB_ASSERT( my_arena_slot, "Must occupy a slot in the attached arena" );
606  my_arena->my_critical_task_stream.push(
607  &t, 0, tbb::internal::subsequent_lane_selector(my_arena_slot->hint_for_critical) );
608  return true;
609 }
610 #endif /* __TBB_PREVIEW_CRITICAL_TASKS */
611 
615  __TBB_ASSERT( first, NULL );
616  __TBB_ASSERT( governor::is_set(this), NULL );
617 #if __TBB_TODO
618  // We need to consider capping the max task pool size and switching
619  // to in-place task execution whenever it is reached.
620 #endif
621  if ( &first->prefix().next == &next ) {
622  // Single task is being spawned
623 #if __TBB_TODO
624  // TODO:
625  // In the future we need to add overloaded spawn method for a single task,
626  // and a method accepting an array of task pointers (we may also want to
627  // change the implementation of the task_list class). But since such changes
628  // may affect the binary compatibility, we postpone them for a while.
629 #endif
630 #if __TBB_PREVIEW_CRITICAL_TASKS
631  if( !handled_as_critical( *first ) )
632 #endif
633  {
634  size_t T = prepare_task_pool( 1 );
636  commit_spawned_tasks( T + 1 );
637  if ( !is_task_pool_published() )
639  }
640  }
641  else {
642  // Task list is being spawned
643 #if __TBB_TODO
644  // TODO: add task_list::front() and implement&document the local execution ordering which is
645  // opposite to the current implementation. The idea is to remove hackish fast_reverse_vector
646  // and use push_back/push_front when accordingly LIFO and FIFO order of local execution is
647  // desired. It also requires refactoring of the reload_tasks method and my_offloaded_tasks list.
648  // Additional benefit may come from adding counter to the task_list so that it can reserve enough
649  // space in the task pool in advance and move all the tasks directly without any intermediate
650  // storages. But it requires dealing with backward compatibility issues and still supporting
651  // counter-less variant (though not necessarily fast implementation).
652 #endif
653  task *arr[min_task_pool_size];
655  task *t_next = NULL;
656  for( task* t = first; ; t = t_next ) {
657  // If t is affinitized to another thread, it may already be executed
658  // and destroyed by the time prepare_for_spawning returns.
659  // So milk it while it is alive.
660  bool end = &t->prefix().next == &next;
661  t_next = t->prefix().next;
662 #if __TBB_PREVIEW_CRITICAL_TASKS
663  if( !handled_as_critical( *t ) )
664 #endif
665  tasks.push_back( prepare_for_spawning(t) );
666  if( end )
667  break;
668  }
669  if( size_t num_tasks = tasks.size() ) {
670  size_t T = prepare_task_pool( num_tasks );
672  commit_spawned_tasks( T + num_tasks );
673  if ( !is_task_pool_published() )
675  }
676  }
679 }
680 
682  __TBB_ASSERT( governor::is_set(this), NULL );
683  __TBB_ASSERT( first, NULL );
684  auto_empty_task dummy( __TBB_CONTEXT_ARG(this, first->prefix().context) );
686  for( task* t=first; ; t=t->prefix().next ) {
687  ++n;
688  __TBB_ASSERT( !t->prefix().parent, "not a root task, or already running" );
689  t->prefix().parent = &dummy;
690  if( &t->prefix().next==&next ) break;
691 #if __TBB_TASK_GROUP_CONTEXT
692  __TBB_ASSERT( t->prefix().context == t->prefix().next->prefix().context,
693  "all the root tasks in list must share the same context");
694 #endif /* __TBB_TASK_GROUP_CONTEXT */
695  }
696  dummy.prefix().ref_count = n+1;
697  if( n>1 )
698  local_spawn( first->prefix().next, next );
699  local_wait_for_all( dummy, first );
700 }
701 
703  governor::local_scheduler()->local_spawn( &first, next );
704 }
705 
708 }
709 
712  // these redirections are due to bw-compatibility, consider reworking some day
713  __TBB_ASSERT( s->my_arena, "thread is not in any arena" );
714  s->my_arena->enqueue_task(t, (intptr_t)prio, s->my_random );
715 }
716 
717 #if __TBB_TASK_PRIORITY
718 class auto_indicator : no_copy {
719  volatile bool& my_indicator;
720 public:
721  auto_indicator ( volatile bool& indicator ) : my_indicator(indicator) { my_indicator = true ;}
722  ~auto_indicator () { my_indicator = false; }
723 };
724 
725 task *generic_scheduler::get_task_and_activate_task_pool( size_t H0, __TBB_ISOLATION_ARG( size_t T0, isolation_tag isolation ) ) {
727 
728  // Go through the task pool to find an available task for execution.
729  task *t = NULL;
730 #if __TBB_TASK_ISOLATION
731  size_t T = T0;
732  bool tasks_omitted = false;
733  while ( !t && T>H0 ) {
734  t = get_task( --T, isolation, tasks_omitted );
735  if ( !tasks_omitted ) {
737  --T0;
738  }
739  }
740  // Make a hole if some tasks have been skipped.
741  if ( t && tasks_omitted ) {
742  my_arena_slot->task_pool_ptr[T] = NULL;
743  if ( T == H0 ) {
744  // The obtained task is on the head. So we can move the head instead of making a hole.
745  ++H0;
747  }
748  }
749 #else
750  while ( !t && T0 ) {
751  t = get_task( --T0 );
753  }
754 #endif /* __TBB_TASK_ISOLATION */
755 
756  if ( H0 < T0 ) {
757  // There are some tasks in the task pool. Publish them.
760  if ( is_task_pool_published() )
762  else
764  } else {
767  if ( is_task_pool_published() )
768  leave_task_pool();
769  }
770 
771 #if __TBB_TASK_ISOLATION
772  // Now it is safe to call note_affinity because the task pool is restored.
773  if ( tasks_omitted && my_innermost_running_task == t ) {
774  assert_task_valid( t );
776  }
777 #endif /* __TBB_TASK_ISOLATION */
778 
780  return t;
781 }
782 
783 task* generic_scheduler::winnow_task_pool( __TBB_ISOLATION_EXPR( isolation_tag isolation ) ) {
784  GATHER_STATISTIC( ++my_counters.prio_winnowings );
786  __TBB_ASSERT( my_offloaded_tasks, "At least one task is expected to be already offloaded" );
787  // To eliminate possible sinking of the store to the indicator below the subsequent
788  // store to my_arena_slot->tail, the stores should have either been separated
789  // by full fence or both use release fences. And resetting indicator should have
790  // been done with release fence. But since this is just an optimization, and
791  // the corresponding checking sequence in arena::is_out_of_work() is not atomic
792  // anyway, fences aren't used, so that not to penalize warmer path.
793  auto_indicator indicator( my_pool_reshuffling_pending );
794 
795  // Locking the task pool unconditionally produces simpler code,
796  // scalability of which should not suffer unless priority jitter takes place.
797  // TODO: consider the synchronization algorithm here is for the owner thread
798  // to avoid locking task pool most of the time.
800  size_t T0 = __TBB_load_relaxed( my_arena_slot->tail );
801  size_t H0 = __TBB_load_relaxed( my_arena_slot->head );
802  size_t T1 = 0;
803  for ( size_t src = H0; src<T0; ++src ) {
804  if ( task *t = my_arena_slot->task_pool_ptr[src] ) {
805  // We cannot offload a proxy task (check the priority of it) because it can be already consumed.
806  if ( !is_proxy( *t ) ) {
807  intptr_t p = priority( *t );
808  if ( p<*my_ref_top_priority ) {
809  offload_task( *t, p );
810  continue;
811  }
812  }
813  my_arena_slot->task_pool_ptr[T1++] = t;
814  }
815  }
816  __TBB_ASSERT( T1<=T0, NULL );
817 
818  // Choose max(T1, H0) because ranges [0, T1) and [H0, T0) can overlap.
819  my_arena_slot->fill_with_canary_pattern( max( T1, H0 ), T0 );
820  return get_task_and_activate_task_pool( 0, __TBB_ISOLATION_ARG( T1, isolation ) );
821 }
822 
823 task* generic_scheduler::reload_tasks ( task*& offloaded_tasks, task**& offloaded_task_list_link, __TBB_ISOLATION_ARG( intptr_t top_priority, isolation_tag isolation ) ) {
824  GATHER_STATISTIC( ++my_counters.prio_reloads );
825 #if __TBB_TASK_ISOLATION
826  // In many cases, locking the task pool is no-op here because the task pool is in the empty
827  // state. However, isolation allows entering stealing loop with non-empty task pool.
828  // In principle, it is possible to process reloaded tasks without locking but it will
829  // complicate the logic of get_task_and_activate_task_pool (TODO: evaluate).
831 #else
833 #endif
834  task *arr[min_task_pool_size];
836  task **link = &offloaded_tasks;
837  while ( task *t = *link ) {
838  task** next_ptr = &t->prefix().next_offloaded;
839  __TBB_ASSERT( !is_proxy(*t), "The proxy tasks cannot be offloaded" );
840  if ( priority(*t) >= top_priority ) {
841  tasks.push_back( t );
842  // Note that owner is an alias of next_offloaded. Thus the following
843  // assignment overwrites *next_ptr
844  task* next = *next_ptr;
845  t->prefix().owner = this;
846  __TBB_ASSERT( t->prefix().state == task::ready, NULL );
847  *link = next;
848  }
849  else {
850  link = next_ptr;
851  }
852  }
853  if ( link == &offloaded_tasks ) {
854  offloaded_tasks = NULL;
855 #if TBB_USE_ASSERT
856  offloaded_task_list_link = NULL;
857 #endif /* TBB_USE_ASSERT */
858  }
859  else {
860  __TBB_ASSERT( link, NULL );
861  // Mark end of list
862  *link = NULL;
863  offloaded_task_list_link = link;
864  }
865  __TBB_ASSERT( link, NULL );
866  size_t num_tasks = tasks.size();
867  if ( !num_tasks ) {
869  return NULL;
870  }
871 
872  // Copy found tasks into the task pool.
873  GATHER_STATISTIC( ++my_counters.prio_tasks_reloaded );
874  size_t T = prepare_task_pool( num_tasks );
876 
877  // Find a task available for execution.
878  task *t = get_task_and_activate_task_pool( __TBB_load_relaxed( my_arena_slot->head ), __TBB_ISOLATION_ARG( T + num_tasks, isolation ) );
879  if ( t ) --num_tasks;
880  if ( num_tasks )
882 
883  return t;
884 }
885 
886 task* generic_scheduler::reload_tasks( __TBB_ISOLATION_EXPR( isolation_tag isolation ) ) {
887  uintptr_t reload_epoch = *my_ref_reload_epoch;
888  __TBB_ASSERT( my_offloaded_tasks, NULL );
889  __TBB_ASSERT( my_local_reload_epoch <= reload_epoch
890  || my_local_reload_epoch - reload_epoch > uintptr_t(-1)/2,
891  "Reload epoch counter overflow?" );
892  if ( my_local_reload_epoch == reload_epoch )
893  return NULL;
894  __TBB_ASSERT( my_offloaded_tasks, NULL );
895  intptr_t top_priority = effective_reference_priority();
896  __TBB_ASSERT( (uintptr_t)top_priority < (uintptr_t)num_priority_levels, NULL );
897  task *t = reload_tasks( my_offloaded_tasks, my_offloaded_task_list_tail_link, __TBB_ISOLATION_ARG( top_priority, isolation ) );
898  if ( my_offloaded_tasks && (my_arena->my_bottom_priority >= top_priority || !my_arena->my_num_workers_requested) ) {
899  // Safeguard against deliberately relaxed synchronization while checking
900  // for the presence of work in arena (so that not to impact hot paths).
901  // Arena may be reset to empty state when offloaded low priority tasks
902  // are still present. This results in both bottom and top priority bounds
903  // becoming 'normal', which makes offloaded low priority tasks unreachable.
904  // Update arena's bottom priority to accommodate them.
905  // NOTE: If the number of priority levels is increased, we may want
906  // to calculate minimum of priorities in my_offloaded_tasks.
907 
908  // First indicate the presence of lower-priority tasks
909  my_market->update_arena_priority( *my_arena, priority(*my_offloaded_tasks) );
910  // Then mark arena as full to unlock arena priority level adjustment
911  // by arena::is_out_of_work(), and ensure worker's presence
913  }
914  my_local_reload_epoch = reload_epoch;
915  return t;
916 }
917 #endif /* __TBB_TASK_PRIORITY */
918 
919 #if __TBB_TASK_ISOLATION
920 inline task* generic_scheduler::get_task( size_t T, isolation_tag isolation, bool& tasks_omitted )
921 #else
923 #endif /* __TBB_TASK_ISOLATION */
924 {
926  || is_local_task_pool_quiescent(), "Is it safe to get a task at position T?" );
927 
928  task* result = my_arena_slot->task_pool_ptr[T];
929  __TBB_ASSERT( !is_poisoned( result ), "The poisoned task is going to be processed" );
930 #if __TBB_TASK_ISOLATION
931  if ( !result )
932  return NULL;
933 
934  bool omit = isolation != no_isolation && isolation != result->prefix().isolation;
935  if ( !omit && !is_proxy( *result ) )
936  return result;
937  else if ( omit ) {
938  tasks_omitted = true;
939  return NULL;
940  }
941 #else
943  if ( !result || !is_proxy( *result ) )
944  return result;
945 #endif /* __TBB_TASK_ISOLATION */
946 
947  task_proxy& tp = static_cast<task_proxy&>(*result);
948  if ( task *t = tp.extract_task<task_proxy::pool_bit>() ) {
949  GATHER_STATISTIC( ++my_counters.proxies_executed );
950  // Following assertion should be true because TBB 2.0 tasks never specify affinity, and hence are not proxied.
951  __TBB_ASSERT( is_version_3_task( *t ), "backwards compatibility with TBB 2.0 broken" );
953  my_innermost_running_task = t; // prepare for calling note_affinity()
954 #if __TBB_TASK_ISOLATION
955  // Task affinity has changed. Postpone calling note_affinity because the task pool is in invalid state.
956  if ( !tasks_omitted )
957 #endif /* __TBB_TASK_ISOLATION */
958  {
961  }
962  return t;
963  }
964 
965  // Proxy was empty, so it's our responsibility to free it
966  free_task<small_task>( tp );
967 #if __TBB_TASK_ISOLATION
968  if ( tasks_omitted )
969  my_arena_slot->task_pool_ptr[T] = NULL;
970 #endif /* __TBB_TASK_ISOLATION */
971  return NULL;
972 }
973 
976  // The current task position in the task pool.
977  size_t T0 = __TBB_load_relaxed( my_arena_slot->tail );
978  // The bounds of available tasks in the task pool. H0 is only used when the head bound is reached.
979  size_t H0 = (size_t)-1, T = T0;
980  task* result = NULL;
981  bool task_pool_empty = false;
982  __TBB_ISOLATION_EXPR( bool tasks_omitted = false );
983  do {
984  __TBB_ASSERT( !result, NULL );
986  atomic_fence();
987  if ( (intptr_t)__TBB_load_relaxed( my_arena_slot->head ) > (intptr_t)T ) {
990  if ( (intptr_t)H0 > (intptr_t)T ) {
991  // The thief has not backed off - nothing to grab.
994  && H0 == T + 1, "victim/thief arbitration algorithm failure" );
996  // No tasks in the task pool.
997  task_pool_empty = true;
998  break;
999  } else if ( H0 == T ) {
1000  // There is only one task in the task pool.
1002  task_pool_empty = true;
1003  } else {
1004  // Release task pool if there are still some tasks.
1005  // After the release, the tail will be less than T, thus a thief
1006  // will not attempt to get a task at position T.
1008  }
1009  }
1010  __TBB_control_consistency_helper(); // on my_arena_slot->head
1011 #if __TBB_TASK_ISOLATION
1012  result = get_task( T, isolation, tasks_omitted );
1013  if ( result ) {
1015  break;
1016  } else if ( !tasks_omitted ) {
1018  __TBB_ASSERT( T0 == T+1, NULL );
1019  T0 = T;
1020  }
1021 #else
1022  result = get_task( T );
1023 #endif /* __TBB_TASK_ISOLATION */
1024  } while ( !result && !task_pool_empty );
1025 
1026 #if __TBB_TASK_ISOLATION
1027  if ( tasks_omitted ) {
1028  if ( task_pool_empty ) {
1029  // All tasks have been checked. The task pool should be in reset state.
1030  // We just restore the bounds for the available tasks.
1031  // TODO: Does it have sense to move them to the beginning of the task pool?
1033  if ( result ) {
1034  // If we have a task, it should be at H0 position.
1035  __TBB_ASSERT( H0 == T, NULL );
1036  ++H0;
1037  }
1038  __TBB_ASSERT( H0 <= T0, NULL );
1039  if ( H0 < T0 ) {
1040  // Restore the task pool if there are some tasks.
1043  // The release fence is used in publish_task_pool.
1045  // Synchronize with snapshot as we published some tasks.
1047  }
1048  } else {
1049  // A task has been obtained. We need to make a hole in position T.
1051  __TBB_ASSERT( result, NULL );
1052  my_arena_slot->task_pool_ptr[T] = NULL;
1054  // Synchronize with snapshot as we published some tasks.
1055  // TODO: consider some approach not to call wakeup for each time. E.g. check if the tail reached the head.
1057  }
1058 
1059  // Now it is safe to call note_affinity because the task pool is restored.
1060  if ( my_innermost_running_task == result ) {
1061  assert_task_valid( result );
1062  result->note_affinity( my_affinity_id );
1063  }
1064  }
1065 #endif /* __TBB_TASK_ISOLATION */
1066  __TBB_ASSERT( (intptr_t)__TBB_load_relaxed( my_arena_slot->tail ) >= 0, NULL );
1067  __TBB_ASSERT( result || __TBB_ISOLATION_EXPR( tasks_omitted || ) is_quiescent_local_task_pool_reset(), NULL );
1068  return result;
1069 } // generic_scheduler::get_task
1070 
1072  // Try to steal a task from a random victim.
1073  size_t k = my_random.get() % (my_arena->my_limit-1);
1074  arena_slot* victim = &my_arena->my_slots[k];
1075  // The following condition excludes the master that might have
1076  // already taken our previous place in the arena from the list .
1077  // of potential victims. But since such a situation can take
1078  // place only in case of significant oversubscription, keeping
1079  // the checks simple seems to be preferable to complicating the code.
1080  if( k >= my_arena_index )
1081  ++victim; // Adjusts random distribution to exclude self
1082  task **pool = victim->task_pool;
1083  task *t = NULL;
1084  if( pool == EmptyTaskPool || !(t = steal_task_from( __TBB_ISOLATION_ARG(*victim, isolation) )) )
1085  return NULL;
1086  if( is_proxy(*t) ) {
1087  task_proxy &tp = *(task_proxy*)t;
1089  if ( !t ) {
1090  // Proxy was empty, so it's our responsibility to free it
1091  free_task<no_cache_small_task>(tp);
1092  return NULL;
1093  }
1094  GATHER_STATISTIC( ++my_counters.proxies_stolen );
1095  }
1096  t->prefix().extra_state |= es_task_is_stolen;
1097  if( is_version_3_task(*t) ) {
1099  t->prefix().owner = this;
1101  }
1102  GATHER_STATISTIC( ++my_counters.steals_committed );
1103  return t;
1104 }
1105 
1107  task** victim_pool = lock_task_pool( &victim_slot );
1108  if ( !victim_pool )
1109  return NULL;
1110  task* result = NULL;
1111  size_t H = __TBB_load_relaxed(victim_slot.head); // mirror
1112  size_t H0 = H;
1113  bool tasks_omitted = false;
1114  do {
1115  __TBB_store_relaxed( victim_slot.head, ++H );
1116  atomic_fence();
1117  if ( (intptr_t)H > (intptr_t)__TBB_load_relaxed( victim_slot.tail ) ) {
1118  // Stealing attempt failed, deque contents has not been changed by us
1119  GATHER_STATISTIC( ++my_counters.thief_backoffs );
1120  __TBB_store_relaxed( victim_slot.head, /*dead: H = */ H0 );
1121  __TBB_ASSERT( !result, NULL );
1122  goto unlock;
1123  }
1124  __TBB_control_consistency_helper(); // on victim_slot.tail
1125  result = victim_pool[H-1];
1126  __TBB_ASSERT( !is_poisoned( result ), NULL );
1127 
1128  if ( result ) {
1129  __TBB_ISOLATION_EXPR( if ( isolation == no_isolation || isolation == result->prefix().isolation ) )
1130  {
1131  if ( !is_proxy( *result ) )
1132  break;
1133  task_proxy& tp = *static_cast<task_proxy*>(result);
1134  // If mailed task is likely to be grabbed by its destination thread, skip it.
1136  break;
1137  GATHER_STATISTIC( ++my_counters.proxies_bypassed );
1138  }
1139  // The task cannot be executed either due to isolation or proxy constraints.
1140  result = NULL;
1141  tasks_omitted = true;
1142  } else if ( !tasks_omitted ) {
1143  // Cleanup the task pool from holes until a task is skipped.
1144  __TBB_ASSERT( H0 == H-1, NULL );
1145  poison_pointer( victim_pool[H0] );
1146  H0 = H;
1147  }
1148  } while ( !result );
1149  __TBB_ASSERT( result, NULL );
1150 
1151  // emit "task was consumed" signal
1152  ITT_NOTIFY( sync_acquired, (void*)((uintptr_t)&victim_slot+sizeof( uintptr_t )) );
1153  poison_pointer( victim_pool[H-1] );
1154  if ( tasks_omitted ) {
1155  // Some proxies in the task pool have been omitted. Set the stolen task to NULL.
1156  victim_pool[H-1] = NULL;
1157  __TBB_store_relaxed( victim_slot.head, /*dead: H = */ H0 );
1158  }
1159 unlock:
1160  unlock_task_pool( &victim_slot, victim_pool );
1161 #if __TBB_PREFETCHING
1162  __TBB_cl_evict(&victim_slot.head);
1163  __TBB_cl_evict(&victim_slot.tail);
1164 #endif
1165  if ( tasks_omitted )
1166  // Synchronize with snapshot as the head and tail can be bumped which can falsely trigger EMPTY state
1168  return result;
1169 }
1170 
1171 #if __TBB_PREVIEW_CRITICAL_TASKS
1172 // Retrieves critical task respecting isolation level, if provided. The rule is:
1173 // 1) If no outer critical task and no isolation => take any critical task
1174 // 2) If working on an outer critical task and no isolation => cannot take any critical task
1175 // 3) If no outer critical task but isolated => respect isolation
1176 // 4) If working on an outer critical task and isolated => respect isolation
1177 task* generic_scheduler::get_critical_task( __TBB_ISOLATION_EXPR(isolation_tag isolation) ) {
1178  __TBB_ASSERT( my_arena && my_arena_slot, "Must be attached to arena" );
1179  if( my_arena->my_critical_task_stream.empty(0) )
1180  return NULL;
1181  task* critical_task = NULL;
1182  // To keep some LIFO-ness, start search with the lane that was used during push operation.
1183  unsigned& start_lane = my_arena_slot->hint_for_critical;
1184 #if __TBB_TASK_ISOLATION
1185  if( isolation != no_isolation ) {
1186  critical_task = my_arena->my_critical_task_stream.pop_specific( 0, start_lane, isolation );
1187  } else
1188 #endif
1189  if( !my_properties.has_taken_critical_task ) {
1190  critical_task = my_arena->my_critical_task_stream.pop( 0, preceding_lane_selector(start_lane) );
1191  }
1192  return critical_task;
1193 }
1194 #endif
1195 
1197  __TBB_ASSERT( my_affinity_id>0, "not in arena" );
1198  while ( task_proxy* const tp = my_inbox.pop( __TBB_ISOLATION_EXPR( isolation ) ) ) {
1199  if ( task* result = tp->extract_task<task_proxy::mailbox_bit>() ) {
1200  ITT_NOTIFY( sync_acquired, my_inbox.outbox() );
1201  result->prefix().extra_state |= es_task_is_stolen;
1202  return result;
1203  }
1204  // We have exclusive access to the proxy, and can destroy it.
1205  free_task<no_cache_small_task>(*tp);
1206  }
1207  return NULL;
1208 }
1209 
1211  __TBB_ASSERT ( my_arena, "no arena: initialization not completed?" );
1212  __TBB_ASSERT ( my_arena_index < my_arena->my_num_slots, "arena slot index is out-of-bound" );
1214  __TBB_ASSERT ( my_arena_slot->task_pool == EmptyTaskPool, "someone else grabbed my arena slot?" );
1216  "entering arena without tasks to share" );
1217  // Release signal on behalf of previously spawned tasks (when this thread was not in arena yet)
1220 }
1221 
1223  __TBB_ASSERT( is_task_pool_published(), "Not in arena" );
1224  // Do not reset my_arena_index. It will be used to (attempt to) re-acquire the slot next time
1225  __TBB_ASSERT( &my_arena->my_slots[my_arena_index] == my_arena_slot, "arena slot and slot index mismatch" );
1226  __TBB_ASSERT ( my_arena_slot->task_pool == LockedTaskPool, "Task pool must be locked when leaving arena" );
1227  __TBB_ASSERT ( is_quiescent_local_task_pool_empty(), "Cannot leave arena when the task pool is not empty" );
1229  // No release fence is necessary here as this assignment precludes external
1230  // accesses to the local task pool when becomes visible. Thus it is harmless
1231  // if it gets hoisted above preceding local bookkeeping manipulations.
1233 }
1234 
1237  __TBB_ASSERT(index, "workers should have index > 0");
1238  s->my_arena_index = index; // index is not a real slot in arena yet
1239  s->my_dummy_task->prefix().ref_count = 2;
1241  // Do not call init_stack_info before the scheduler is set as master or worker.
1242  s->init_stack_info();
1243  governor::sign_on(s);
1244  return s;
1245 }
1246 
1247 // TODO: make it a member method
1249  // add an internal market reference; the public reference is possibly added in create_arena
1250  generic_scheduler* s = allocate_scheduler( market::global_market(/*is_public=*/false) );
1251  __TBB_ASSERT( !s->my_arena, NULL );
1252  __TBB_ASSERT( s->my_market, NULL );
1253  task& t = *s->my_dummy_task;
1255  t.prefix().ref_count = 1;
1256 #if __TBB_TASK_GROUP_CONTEXT
1257  t.prefix().context = new ( NFS_Allocate(1, sizeof(task_group_context), NULL) )
1259 #if __TBB_FP_CONTEXT
1260  s->default_context()->capture_fp_settings();
1261 #endif
1262  // Do not call init_stack_info before the scheduler is set as master or worker.
1263  s->init_stack_info();
1264  context_state_propagation_mutex_type::scoped_lock lock(the_context_state_propagation_mutex);
1265  s->my_market->my_masters.push_front( *s );
1266  lock.release();
1267 #endif /* __TBB_TASK_GROUP_CONTEXT */
1268  if( a ) {
1269  // Master thread always occupies the first slot
1270  s->attach_arena( a, /*index*/0, /*is_master*/true );
1272  a->my_default_ctx = s->default_context(); // also transfers implied ownership
1273  }
1274  __TBB_ASSERT( s->my_arena_index == 0, "Master thread must occupy the first slot in its arena" );
1275  governor::sign_on(s);
1276 
1277 #if _WIN32||_WIN64
1278  s->my_market->register_master( s->master_exec_resource );
1279 #endif /* _WIN32||_WIN64 */
1280  // Process any existing observers.
1281 #if __TBB_ARENA_OBSERVER
1282  __TBB_ASSERT( !a || a->my_observers.empty(), "Just created arena cannot have any observers associated with it" );
1283 #endif
1284 #if __TBB_SCHEDULER_OBSERVER
1285  the_global_observer_list.notify_entry_observers( s->my_last_global_observer, /*worker=*/false );
1286 #endif /* __TBB_SCHEDULER_OBSERVER */
1287  return s;
1288 }
1289 
1290 void generic_scheduler::cleanup_worker( void* arg, bool worker ) {
1292  __TBB_ASSERT( !s.my_arena_slot, "cleaning up attached worker" );
1293 #if __TBB_SCHEDULER_OBSERVER
1294  if ( worker ) // can be called by master for worker, do not notify master twice
1295  the_global_observer_list.notify_exit_observers( s.my_last_global_observer, /*worker=*/true );
1296 #endif /* __TBB_SCHEDULER_OBSERVER */
1297  s.free_scheduler();
1298 }
1299 
1300 bool generic_scheduler::cleanup_master( bool blocking_terminate ) {
1301  arena* const a = my_arena;
1302  market * const m = my_market;
1303  __TBB_ASSERT( my_market, NULL );
1304  if( a && is_task_pool_published() ) {
1308  {
1309  // Local task pool is empty
1310  leave_task_pool();
1311  }
1312  else {
1313  // Master's local task pool may e.g. contain proxies of affinitized tasks.
1315  __TBB_ASSERT ( governor::is_set(this), "TLS slot is cleared before the task pool cleanup" );
1318  __TBB_ASSERT ( governor::is_set(this), "Other thread reused our TLS key during the task pool cleanup" );
1319  }
1320  }
1321 #if __TBB_ARENA_OBSERVER
1322  if( a )
1323  a->my_observers.notify_exit_observers( my_last_local_observer, /*worker=*/false );
1324 #endif
1325 #if __TBB_SCHEDULER_OBSERVER
1326  the_global_observer_list.notify_exit_observers( my_last_global_observer, /*worker=*/false );
1327 #endif /* __TBB_SCHEDULER_OBSERVER */
1328 #if _WIN32||_WIN64
1329  m->unregister_master( master_exec_resource );
1330 #endif /* _WIN32||_WIN64 */
1331  if( a ) {
1332  __TBB_ASSERT(a->my_slots+0 == my_arena_slot, NULL);
1333 #if __TBB_STATISTICS
1334  *my_arena_slot->my_counters += my_counters;
1335 #endif /* __TBB_STATISTICS */
1337  }
1338 #if __TBB_TASK_GROUP_CONTEXT
1339  else { // task_group_context ownership was not transferred to arena
1340  default_context()->~task_group_context();
1341  NFS_Free(default_context());
1342  }
1343  context_state_propagation_mutex_type::scoped_lock lock(the_context_state_propagation_mutex);
1344  my_market->my_masters.remove( *this );
1345  lock.release();
1346 #endif /* __TBB_TASK_GROUP_CONTEXT */
1347  my_arena_slot = NULL; // detached from slot
1348  free_scheduler(); // do not use scheduler state after this point
1349 
1350  if( a )
1352  // If there was an associated arena, it added a public market reference
1353  return m->release( /*is_public*/ a != NULL, blocking_terminate );
1354 }
1355 
1356 } // namespace internal
1357 } // namespace tbb
1358 
1359 /*
1360  Comments:
1361 
1362 1. The premise of the cancellation support implementation is that cancellations are
1363  not part of the hot path of the program execution. Therefore all changes in its
1364  implementation in order to reduce the overhead of the cancellation control flow
1365  should be done only in ways that do not increase overhead of the normal execution.
1366 
1367  In general contexts are used by all threads and their descendants are created in
1368  different threads as well. In order to minimize impact of the cross-thread tree
1369  maintenance (first of all because of the synchronization), the tree of contexts
1370  is split into pieces, each of which is handled by the only thread. Such pieces
1371  are represented as lists of contexts, members of which are contexts that were
1372  bound to their parents in the given thread.
1373 
1374  The context tree maintenance and cancellation propagation algorithms is designed
1375  in such a manner that cross-thread access to a context list will take place only
1376  when cancellation signal is sent (by user or when an exception happens), and
1377  synchronization is necessary only then. Thus the normal execution flow (without
1378  exceptions and cancellation) remains free from any synchronization done on
1379  behalf of exception handling and cancellation support.
1380 
1381 2. Consider parallel cancellations at the different levels of the context tree:
1382 
1383  Ctx1 <- Cancelled by Thread1 |- Thread2 started processing
1384  | |
1385  Ctx2 |- Thread1 started processing
1386  | T1 |- Thread2 finishes and syncs up local counters
1387  Ctx3 <- Cancelled by Thread2 |
1388  | |- Ctx5 is bound to Ctx2
1389  Ctx4 |
1390  T2 |- Thread1 reaches Ctx2
1391 
1392  Thread-propagator of each cancellation increments global counter. However the thread
1393  propagating the cancellation from the outermost context (Thread1) may be the last
1394  to finish. Which means that the local counters may be synchronized earlier (by Thread2,
1395  at Time1) than it propagated cancellation into Ctx2 (at time Time2). If a new context
1396  (Ctx5) is created and bound to Ctx2 between Time1 and Time2, checking its parent only
1397  (Ctx2) may result in cancellation request being lost.
1398 
1399  This issue is solved by doing the whole propagation under the lock.
1400 
1401  If we need more concurrency while processing parallel cancellations, we could try
1402  the following modification of the propagation algorithm:
1403 
1404  advance global counter and remember it
1405  for each thread:
1406  scan thread's list of contexts
1407  for each thread:
1408  sync up its local counter only if the global counter has not been changed
1409 
1410  However this version of the algorithm requires more analysis and verification.
1411 
1412 3. There is no portable way to get stack base address in Posix, however the modern
1413  Linux versions provide pthread_attr_np API that can be used to obtain thread's
1414  stack size and base address. Unfortunately even this function does not provide
1415  enough information for the main thread on IA-64 architecture (RSE spill area
1416  and memory stack are allocated as two separate discontinuous chunks of memory),
1417  and there is no portable way to discern the main and the secondary threads.
1418  Thus for macOS* and IA-64 architecture for Linux* OS we use the TBB worker stack size for
1419  all threads and use the current stack top as the stack base. This simplified
1420  approach is based on the following assumptions:
1421  1) If the default stack size is insufficient for the user app needs, the
1422  required amount will be explicitly specified by the user at the point of the
1423  TBB scheduler initialization (as an argument to tbb::task_scheduler_init
1424  constructor).
1425  2) When a master thread initializes the scheduler, it has enough space on its
1426  stack. Here "enough" means "at least as much as worker threads have".
1427  3) If the user app strives to conserve the memory by cutting stack size, it
1428  should do this for TBB workers too (as in the #1).
1429 */
task * get_task(__TBB_ISOLATION_EXPR(isolation_tag isolation))
Get a task from the local pool.
Definition: scheduler.cpp:974
static const intptr_t mailbox_bit
Definition: mailbox.h:31
market * my_market
The market I am in.
Definition: scheduler.h:155
generic_scheduler * allocate_scheduler(market &m)
Definition: scheduler.cpp:37
void free_scheduler()
Destroy and deallocate this scheduler object.
Definition: scheduler.cpp:260
arena_slot my_slots[1]
Definition: arena.h:296
bool outermost
Indicates that a scheduler is on outermost level.
Definition: scheduler.h:53
scheduler_properties my_properties
Definition: scheduler.h:91
atomic< unsigned > my_limit
The maximal number of currently busy slots.
Definition: arena.h:65
static const intptr_t num_priority_levels
static void cleanup_worker(void *arg, bool worker)
Perform necessary cleanup when a worker thread finishes.
Definition: scheduler.cpp:1290
int depth
Obsolete. Used to be scheduling depth before TBB 2.2.
Definition: task.h:253
void release_task_pool() const
Unlocks the local task pool.
Definition: scheduler.cpp:485
affinity_id affinity
Definition: task.h:268
virtual void local_wait_for_all(task &parent, task *child)=0
T __TBB_load_relaxed(const volatile T &location)
Definition: tbb_machine.h:738
size_t prepare_task_pool(size_t n)
Makes sure that the task pool can accommodate at least n more elements.
Definition: scheduler.cpp:402
static const intptr_t location_mask
Definition: mailbox.h:32
static const unsigned ref_external
Reference increment values for externals and workers.
Definition: arena.h:226
void unlock_task_pool(arena_slot *victim_arena_slot, task **victim_task_pool) const
Unlocks victim&#39;s task pool.
Definition: scheduler.cpp:549
void local_spawn_root_and_wait(task *first, task *&next)
Definition: scheduler.cpp:681
void init_stack_info()
Sets up the data necessary for the stealing limiting heuristics.
Definition: scheduler.cpp:146
task_group_context * context()
This method is deprecated and will be removed in the future.
Definition: task.h:848
tbb::task * next
"next" field for list of task
Definition: task.h:271
task * my_dummy_task
Fake root task created by slave threads.
Definition: scheduler.h:169
generic_scheduler * my_scheduler
Scheduler of the thread attached to the slot.
internal::task_prefix & prefix(internal::version_tag *=NULL) const
Get reference to corresponding task_prefix.
Definition: task.h:946
bool is_quiescent_local_task_pool_empty() const
Definition: scheduler.h:557
task * extract_task()
Returns a pointer to the encapsulated task or NULL, and frees proxy if necessary. ...
Definition: mailbox.h:57
void __TBB_store_relaxed(volatile T &location, V value)
Definition: tbb_machine.h:742
void Scheduler_OneTimeInitialization(bool itt_present)
Defined in scheduler.cpp.
Definition: scheduler.cpp:52
Class that implements exponential backoff.
Definition: tbb_machine.h:348
#define TBB_USE_ASSERT
Definition: tbb_config.h:442
void spin_wait_until_eq(const volatile T &location, const U value)
Spin UNTIL the value of the variable is equal to a given value.
Definition: tbb_machine.h:402
#define __TBB_ISOLATION_EXPR(isolation)
void commit_spawned_tasks(size_t new_tail)
Makes newly spawned tasks visible to thieves.
Definition: scheduler.h:628
intptr_t reference_count
A reference count.
Definition: task.h:117
static bool is_shared(intptr_t tat)
True if the proxy is stored both in its sender&#39;s pool and in the destination mailbox.
Definition: mailbox.h:46
task object is freshly allocated or recycled.
Definition: task.h:617
static void sign_on(generic_scheduler *s)
Register TBB scheduler instance in thread-local storage.
Definition: governor.cpp:124
void deallocate_task(task &t)
Return task object to the memory allocator.
Definition: scheduler.h:601
#define ITT_SYNC_CREATE(obj, type, name)
Definition: itt_notify.h:119
void copy_memory(T *dst) const
Copies the contents of the vector into the dst array.
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 new_size
void const char const char int ITT_FORMAT __itt_group_sync s
mail_outbox & mailbox(affinity_id id)
Get reference to mailbox corresponding to given affinity_id.
Definition: arena.h:204
#define EmptyTaskPool
Definition: scheduler.h:42
#define __TBB_get_object_ref(class_name, member_name, member_addr)
Returns address of the object containing a member with the given name and address.
Definition: tbb_stddef.h:270
void reset_task_pool_and_leave()
Resets head and tail indices to 0, and leaves task pool.
Definition: scheduler.h:620
void fill_with_canary_pattern(size_t, size_t)
#define __TBB_FetchAndDecrementWrelease(P)
Definition: tbb_machine.h:314
#define __TBB_cl_prefetch(p)
Definition: mic_common.h:33
#define GATHER_STATISTIC(x)
static bool is_proxy(const task &t)
True if t is a task_proxy.
Definition: scheduler.h:269
void spawn(task &first, task *&next) __TBB_override
For internal use only.
Definition: scheduler.cpp:702
void poison_pointer(T *__TBB_atomic &)
Definition: tbb_stddef.h:305
__TBB_atomic size_t tail
Index of the element following the last ready task in the deque.
const size_t task_prefix_reservation_size
Number of bytes reserved for a task prefix.
task * prepare_for_spawning(task *t)
Checks if t is affinitized to another thread, and if so, bundles it as proxy.
Definition: scheduler.cpp:558
static task * plugged_return_list()
Special value used to mark my_return_list as not taking any more entries.
Definition: scheduler.h:376
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
auto first(Container &c) -> decltype(begin(c))
static bool is_version_3_task(task &t)
Definition: scheduler.h:129
The graph class.
void pause()
Pause for a while.
Definition: tbb_machine.h:363
void acquire_task_pool() const
Locks the local task pool.
Definition: scheduler.cpp:456
static bool is_set(generic_scheduler *s)
Used to check validity of the local scheduler TLS contents.
Definition: governor.cpp:120
int my_num_workers_requested
The number of workers that are currently requested from the resource manager.
Definition: arena.h:92
void enqueue(task &, void *reserved) __TBB_override
For internal use only.
Definition: scheduler.cpp:710
void free_nonlocal_small_task(task &t)
Free a small task t that that was allocated by a different scheduler.
Definition: scheduler.cpp:375
static const size_t min_task_pool_size
Definition: scheduler.h:290
void attach_arena(arena *, size_t index, bool is_master)
Definition: arena.cpp:36
A scheduler with a customized evaluation loop.
Release.
Definition: atomic.h:45
void * __TBB_get_bsp()
Retrieves the current RSE backing store pointer. IA64 specific.
size_t worker_stack_size() const
Returns the requested stack size of worker threads.
Definition: market.h:294
bool type
Indicates that a scheduler acts as a master or a worker.
Definition: scheduler.h:50
void advertise_new_work()
If necessary, raise a flag that there is new job in arena.
Definition: arena.h:389
void __TBB_EXPORTED_FUNC NFS_Free(void *)
Free memory allocated by NFS_Allocate.
static generic_scheduler * create_master(arena *a)
Initialize a scheduler for a master thread.
Definition: scheduler.cpp:1248
unsigned short affinity_id
An id as used for specifying affinity.
Definition: task.h:120
static market & global_market(bool is_public, unsigned max_num_workers=0, size_t stack_size=0)
Factory method creating new market object.
Definition: market.cpp:96
task ** lock_task_pool(arena_slot *victim_arena_slot) const
Locks victim&#39;s task pool, and returns pointer to it. The pointer can be NULL.
Definition: scheduler.cpp:500
atomic< T > & as_atomic(T &t)
Definition: atomic.h:543
static generic_scheduler * create_worker(market &m, size_t index)
Initialize a scheduler for a worker thread.
Definition: scheduler.cpp:1235
task * steal_task(__TBB_ISOLATION_EXPR(isolation_tag isolation))
Attempts to steal a task from a randomly chosen thread/scheduler.
Definition: scheduler.cpp:1071
task & allocate_task(size_t number_of_bytes, __TBB_CONTEXT_ARG(task *parent, task_group_context *context))
Allocate task object, either from the heap or a free list.
Definition: scheduler.cpp:300
scheduler * owner
Obsolete. The scheduler that owns the task.
Definition: task.h:228
static generic_scheduler * local_scheduler()
Obtain the thread-local instance of the TBB scheduler.
Definition: governor.h:122
void acquire(spin_mutex &m)
Acquire lock.
Definition: spin_mutex.h:89
static const kind_type binding_required
Definition: task.h:563
affinity_id my_affinity_id
The mailbox id assigned to this scheduler.
Definition: scheduler.h:89
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
task_proxy * pop(__TBB_ISOLATION_EXPR(isolation_tag isolation))
Get next piece of mail, or NULL if mailbox is empty.
Definition: mailbox.h:202
__TBB_atomic kind_type my_kind
Flavor of this context: bound or isolated.
Definition: task.h:379
task * my_return_list
List of small tasks that have been returned to this scheduler by other schedulers.
Definition: scheduler.h:383
bool is_worker() const
True if running on a worker thread, false otherwise.
Definition: scheduler.h:591
task * steal_task_from(__TBB_ISOLATION_ARG(arena_slot &victim_arena_slot, isolation_tag isolation))
Steal task from another scheduler&#39;s ready pool.
Definition: scheduler.cpp:1106
Memory prefix to a task object.
Definition: task.h:184
static const size_t quick_task_size
If sizeof(task) is <=quick_task_size, it is handled on a free list instead of malloc&#39;d.
Definition: scheduler.h:127
Represents acquisition of a mutex.
Definition: spin_mutex.h:50
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:165
FastRandom my_random
Random number generator used for picking a random victim from which to steal.
Definition: scheduler.h:158
void assert_task_valid(const task *)
size_t my_task_pool_size
Capacity of the primary task pool (number of elements - pointers to task).
void allocate_task_pool(size_t n)
virtual ~scheduler()=0
Pure virtual destructor;.
Definition: scheduler.cpp:72
#define __TBB_control_consistency_helper()
Definition: gcc_generic.h:60
state_type state() const
Current execution state.
Definition: task.h:864
uintptr_t my_stealing_threshold
Position in the call stack specifying its maximal filling when stealing is still allowed.
Definition: scheduler.h:138
#define __TBB_CONTEXT_ARG(arg1, context)
__TBB_atomic reference_count ref_count
Reference count used for synchronization.
Definition: task.h:248
void leave_task_pool()
Leave the task pool.
Definition: scheduler.cpp:1222
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
unsigned char extra_state
Miscellaneous state that is not directly visible to users, stored as a byte for compactness.
Definition: task.h:266
void push(task_proxy *t)
Push task_proxy onto the mailbox queue of another thread.
Definition: mailbox.h:140
void __TBB_store_with_release(volatile T &location, V value)
Definition: tbb_machine.h:716
arena * my_arena
The arena that I own (if master) or am servicing at the moment (if worker)
Definition: scheduler.h:74
task * get_mailbox_task(__TBB_ISOLATION_EXPR(isolation_tag isolation))
Attempt to get a task from the mailbox.
Definition: scheduler.cpp:1196
unsigned char state
A task::state_type, stored as a byte for compactness.
Definition: task.h:257
Used to form groups of tasks.
Definition: task.h:332
uintptr_t my_version_and_traits
Version for run-time checks and behavioral traits of the context.
Definition: task.h:420
#define __TBB_cl_evict(p)
Definition: mic_common.h:34
void enqueue_task(task &, intptr_t, FastRandom &)
enqueue a task into starvation-resistance queue
Definition: arena.cpp:554
task is in ready pool, or is going to be put there, or was just taken off.
Definition: task.h:615
void spawn_root_and_wait(task &first, task *&next) __TBB_override
For internal use only.
Definition: scheduler.cpp:706
virtual void __TBB_EXPORTED_METHOD note_affinity(affinity_id id)
Invoked by scheduler to notify task that it ran on unexpected thread.
Definition: task.cpp:245
static void sign_off(generic_scheduler *s)
Unregister TBB scheduler instance from thread-local storage.
Definition: governor.cpp:145
task object is on free list, or is going to be put there, or was just taken off.
Definition: task.h:619
#define ITT_NOTIFY(name, obj)
Definition: itt_notify.h:116
intptr_t my_priority
Priority level of the task group (in normalized representation)
Definition: task.h:433
tbb::task * parent
The task whose reference count includes me.
Definition: task.h:241
static const kind_type detached
Definition: task.h:565
bool is_critical(task &t)
Definition: task.h:958
static const kind_type dying
Definition: task.h:566
Base class for types that should not be copied or assigned.
Definition: tbb_stddef.h:331
Vector that grows without reallocations, and stores items in the reverse order.
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 * lock
const size_t MByte
Definition: tbb_misc.h:40
static const intptr_t pool_bit
Definition: mailbox.h:30
No ordering.
Definition: atomic.h:47
#define LockedTaskPool
Definition: scheduler.h:43
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
Base class for user-defined tasks.
Definition: task.h:589
Work stealing task scheduler.
Definition: scheduler.h:120
arena_slot * my_arena_slot
Pointer to the slot in the arena we own at the moment.
Definition: scheduler.h:71
task * parent() const
task on whose behalf this task is working, or NULL if this is a root.
Definition: task.h:835
isolation_tag isolation
The tag used for task isolation.
Definition: task.h:201
task * my_free_list
Free list of small tasks that can be reused.
Definition: scheduler.h:161
void publish_task_pool()
Used by workers to enter the task pool.
Definition: scheduler.cpp:1210
#define __TBB_ISOLATION_ARG(arg1, isolation)
const isolation_tag no_isolation
Definition: task.h:125
context_list_node_t * my_next
Definition: task.h:132
generic_scheduler *(* AllocateSchedulerPtr)(market &)
Pointer to the scheduler factory function.
Definition: tbb_main.cpp:74
size_t my_arena_index
Index of the arena slot the scheduler occupies now, or occupied last time.
Definition: scheduler.h:68
bool is_local_task_pool_quiescent() const
Definition: scheduler.h:551
void commit_relocated_tasks(size_t new_tail)
Makes relocated tasks visible to thieves and releases the local task pool.
Definition: scheduler.h:637
bool cleanup_master(bool blocking_terminate)
Perform necessary cleanup when a master thread stops using TBB.
Definition: scheduler.cpp:1300
void atomic_fence()
Sequentially consistent full memory fence.
Definition: tbb_machine.h:342
__TBB_atomic intptr_t my_small_task_count
Number of small tasks that have been allocated by this scheduler.
Definition: scheduler.h:379
T max(const T &val1, const T &val2)
Utility template function returning greater of the two values.
Definition: tbb_misc.h:112
void const char const char int ITT_FORMAT __itt_group_sync p
Smart holder for the empty task class with automatic destruction.
task * my_innermost_running_task
Innermost task whose task::execute() is running. A dummy task on the outermost level.
Definition: scheduler.h:77
mail_outbox * outbox
Mailbox to which this was mailed.
Definition: mailbox.h:43
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 end
void local_spawn(task *first, task *&next)
Definition: scheduler.cpp:614
bool is_quiescent_local_task_pool_reset() const
Definition: scheduler.h:562
unsigned short get()
Get a random number.
Definition: tbb_misc.h:139
void on_thread_leaving()
Notification that worker or master leaves its arena.
Definition: arena.h:300
__TBB_atomic size_t head
Index of the first ready task in the deque.
scheduler * origin
The scheduler that allocated the task, or NULL if the task is big.
Definition: task.h:220
task_group_context * context
Shared context that is used to communicate asynchronous state changes.
Definition: task.h:211
bool release(bool is_public, bool blocking_terminate)
Decrements market&#39;s refcount and destroys it in the end.
Definition: market.cpp:175
uintptr_t my_state
Internal state (combination of state flags, currently only may_have_children).
Definition: task.h:429
Tag for v3 task_proxy.
Set if the task has been stolen.
bool recipient_is_idle()
True if thread that owns this mailbox is looking for work.
Definition: mailbox.h:179
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.