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

Copyright © 2005-2020 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.