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

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.