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