Intel(R) Threading Building Blocks Doxygen Documentation version 4.2.3
Loading...
Searching...
No Matches
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
27namespace tbb {
28namespace internal {
29
30//------------------------------------------------------------------------
31// Library initialization
32//------------------------------------------------------------------------
33
35extern generic_scheduler* (*AllocateSchedulerPtr)( market&, bool );
36
37inline generic_scheduler* allocate_scheduler ( market& m, bool genuine ) {
38 return AllocateSchedulerPtr( m, genuine);
39}
40
41#if __TBB_TASK_GROUP_CONTEXT
42context_state_propagation_mutex_type the_context_state_propagation_mutex;
43
44uintptr_t the_context_state_propagation_epoch = 0;
45
47
49static task_group_context the_dummy_context(task_group_context::isolated);
50#endif /* __TBB_TASK_GROUP_CONTEXT */
51
52void 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
111#endif
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;
137 task** tp = my_arena_slot->task_pool_ptr;
138 if ( my_arena_slot->my_task_pool_size )
139 __TBB_ASSERT( my_arena_slot->my_task_pool_size >= min_task_pool_size, NULL );
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
251void 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
337task& 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
426 __TBB_cl_evict(&t);
427#endif
428 return;
429 }
430 }
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
439inline 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
446 if ( !my_arena_slot->my_task_pool_size ) {
448 __TBB_ASSERT( !my_arena_slot->task_pool_ptr, NULL );
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;;
457 __TBB_ASSERT( my_arena_slot->my_task_pool_size >= min_task_pool_size, NULL );
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
464 bool allocate = new_size > my_arena_slot->my_task_pool_size - min_task_pool_size/4;
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 )
469 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
505 if( my_arena_slot->task_pool != LockedTaskPool &&
506 as_atomic(my_arena_slot->task_pool).compare_and_swap(LockedTaskPool, my_arena_slot->task_pool_ptr ) == my_arena_slot->task_pool_ptr )
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" );
528 __TBB_store_with_release( my_arena_slot->task_pool, my_arena_slot->task_pool_ptr );
529}
530
537inline 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
586inline 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
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 );
626 // Mail the proxy, if success, it may be destroyed by another thread at any moment after this point.
627 if ( proxy.outbox->push(&proxy) )
628 return &proxy;
629 // The mailbox is overfilled, deallocate the proxy and return the initial task.
630 free_task<small_task>(proxy);
631 }
632 return t;
633}
634
635#if __TBB_PREVIEW_CRITICAL_TASKS
636bool generic_scheduler::handled_as_critical( task& t ) {
637 if( !internal::is_critical( t ) )
638 return false;
639#if __TBB_TASK_ISOLATION
641#endif
642 ITT_NOTIFY(sync_releasing, &my_arena->my_critical_task_stream);
643 __TBB_ASSERT( my_arena, "Must be attached to the arena." );
644 __TBB_ASSERT( my_arena_slot, "Must occupy a slot in the attached arena" );
645 my_arena->my_critical_task_stream.push(
646 &t, 0, tbb::internal::subsequent_lane_selector(my_arena_slot->hint_for_critical) );
647 return true;
648}
649#endif /* __TBB_PREVIEW_CRITICAL_TASKS */
650
654 __TBB_ASSERT( first, NULL );
655 __TBB_ASSERT( governor::is_set(this), NULL );
656#if __TBB_TODO
657 // We need to consider capping the max task pool size and switching
658 // to in-place task execution whenever it is reached.
659#endif
660 if ( &first->prefix().next == &next ) {
661 // Single task is being spawned
662#if __TBB_TODO
663 // TODO:
664 // In the future we need to add overloaded spawn method for a single task,
665 // and a method accepting an array of task pointers (we may also want to
666 // change the implementation of the task_list class). But since such changes
667 // may affect the binary compatibility, we postpone them for a while.
668#endif
669#if __TBB_PREVIEW_CRITICAL_TASKS
670 if( !handled_as_critical( *first ) )
671#endif
672 {
673 size_t T = prepare_task_pool( 1 );
674 my_arena_slot->task_pool_ptr[T] = prepare_for_spawning( first );
675 commit_spawned_tasks( T + 1 );
676 if ( !is_task_pool_published() )
678 }
679 }
680 else {
681 // Task list is being spawned
682#if __TBB_TODO
683 // TODO: add task_list::front() and implement&document the local execution ordering which is
684 // opposite to the current implementation. The idea is to remove hackish fast_reverse_vector
685 // and use push_back/push_front when accordingly LIFO and FIFO order of local execution is
686 // desired. It also requires refactoring of the reload_tasks method and my_offloaded_tasks list.
687 // Additional benefit may come from adding counter to the task_list so that it can reserve enough
688 // space in the task pool in advance and move all the tasks directly without any intermediate
689 // storages. But it requires dealing with backward compatibility issues and still supporting
690 // counter-less variant (though not necessarily fast implementation).
691#endif
694 task *t_next = NULL;
695 for( task* t = first; ; t = t_next ) {
696 // If t is affinitized to another thread, it may already be executed
697 // and destroyed by the time prepare_for_spawning returns.
698 // So milk it while it is alive.
699 bool end = &t->prefix().next == &next;
700 t_next = t->prefix().next;
701#if __TBB_PREVIEW_CRITICAL_TASKS
702 if( !handled_as_critical( *t ) )
703#endif
705 if( end )
706 break;
707 }
708 if( size_t num_tasks = tasks.size() ) {
709 size_t T = prepare_task_pool( num_tasks );
710 tasks.copy_memory( my_arena_slot->task_pool_ptr + T );
711 commit_spawned_tasks( T + num_tasks );
712 if ( !is_task_pool_published() )
714 }
715 }
718}
719
721 __TBB_ASSERT( governor::is_set(this), NULL );
722 __TBB_ASSERT( first, NULL );
723 auto_empty_task dummy( __TBB_CONTEXT_ARG(this, first->prefix().context) );
725 for( task* t=first; ; t=t->prefix().next ) {
726 ++n;
727 __TBB_ASSERT( !t->prefix().parent, "not a root task, or already running" );
728 t->prefix().parent = &dummy;
729 if( &t->prefix().next==&next ) break;
730#if __TBB_TASK_GROUP_CONTEXT
732 "all the root tasks in list must share the same context");
733#endif /* __TBB_TASK_GROUP_CONTEXT */
734 }
735 dummy.prefix().ref_count = n+1;
736 if( n>1 )
737 local_spawn( first->prefix().next, next );
738 local_wait_for_all( dummy, first );
739}
740
743}
744
747}
748
751 // these redirections are due to bw-compatibility, consider reworking some day
752 __TBB_ASSERT( s->my_arena, "thread is not in any arena" );
753 s->my_arena->enqueue_task(t, (intptr_t)prio, s->my_random );
754}
755
756#if __TBB_TASK_PRIORITY
757class auto_indicator : no_copy {
758 volatile bool& my_indicator;
759public:
760 auto_indicator ( volatile bool& indicator ) : my_indicator(indicator) { my_indicator = true ;}
761 ~auto_indicator () { my_indicator = false; }
762};
763
764task *generic_scheduler::get_task_and_activate_task_pool( size_t H0, __TBB_ISOLATION_ARG( size_t T0, isolation_tag isolation ) ) {
766
767 // Go through the task pool to find an available task for execution.
768 task *t = NULL;
769#if __TBB_TASK_ISOLATION
770 size_t T = T0;
771 bool tasks_omitted = false;
772 while ( !t && T>H0 ) {
773 t = get_task( --T, isolation, tasks_omitted );
774 if ( !tasks_omitted ) {
775 poison_pointer( my_arena_slot->task_pool_ptr[T] );
776 --T0;
777 }
778 }
779 // Make a hole if some tasks have been skipped.
780 if ( t && tasks_omitted ) {
781 my_arena_slot->task_pool_ptr[T] = NULL;
782 if ( T == H0 ) {
783 // The obtained task is on the head. So we can move the head instead of making a hole.
784 ++H0;
785 poison_pointer( my_arena_slot->task_pool_ptr[T] );
786 }
787 }
788#else
789 while ( !t && T0 ) {
790 t = get_task( --T0 );
791 poison_pointer( my_arena_slot->task_pool_ptr[T0] );
792 }
793#endif /* __TBB_TASK_ISOLATION */
794
795 if ( H0 < T0 ) {
796 // There are some tasks in the task pool. Publish them.
801 else
803 } else {
808 }
809
810#if __TBB_TASK_ISOLATION
811 // Now it is safe to call note_affinity because the task pool is restored.
812 if ( tasks_omitted && my_innermost_running_task == t ) {
814 t->note_affinity( my_affinity_id );
815 }
816#endif /* __TBB_TASK_ISOLATION */
817
819 return t;
820}
821
822task* generic_scheduler::winnow_task_pool( __TBB_ISOLATION_EXPR( isolation_tag isolation ) ) {
823 GATHER_STATISTIC( ++my_counters.prio_winnowings );
825 __TBB_ASSERT( my_offloaded_tasks, "At least one task is expected to be already offloaded" );
826 // To eliminate possible sinking of the store to the indicator below the subsequent
827 // store to my_arena_slot->tail, the stores should have either been separated
828 // by full fence or both use release fences. And resetting indicator should have
829 // been done with release fence. But since this is just an optimization, and
830 // the corresponding checking sequence in arena::is_out_of_work() is not atomic
831 // anyway, fences aren't used, so that not to penalize warmer path.
832 auto_indicator indicator( my_pool_reshuffling_pending );
833
834 // Locking the task pool unconditionally produces simpler code,
835 // scalability of which should not suffer unless priority jitter takes place.
836 // TODO: consider the synchronization algorithm here is for the owner thread
837 // to avoid locking task pool most of the time.
839 size_t T0 = __TBB_load_relaxed( my_arena_slot->tail );
840 size_t H0 = __TBB_load_relaxed( my_arena_slot->head );
841 size_t T1 = 0;
842 for ( size_t src = H0; src<T0; ++src ) {
843 if ( task *t = my_arena_slot->task_pool_ptr[src] ) {
844 // We cannot offload a proxy task (check the priority of it) because it can be already consumed.
845 if ( !is_proxy( *t ) ) {
846 intptr_t p = priority( *t );
847 if ( p<*my_ref_top_priority ) {
848 offload_task( *t, p );
849 continue;
850 }
851 }
852 my_arena_slot->task_pool_ptr[T1++] = t;
853 }
854 }
855 __TBB_ASSERT( T1<=T0, NULL );
856
857 // Choose max(T1, H0) because ranges [0, T1) and [H0, T0) can overlap.
859 return get_task_and_activate_task_pool( 0, __TBB_ISOLATION_ARG( T1, isolation ) );
860}
861
862task* generic_scheduler::reload_tasks ( task*& offloaded_tasks, task**& offloaded_task_list_link, __TBB_ISOLATION_ARG( intptr_t top_priority, isolation_tag isolation ) ) {
863 GATHER_STATISTIC( ++my_counters.prio_reloads );
864#if __TBB_TASK_ISOLATION
865 // In many cases, locking the task pool is no-op here because the task pool is in the empty
866 // state. However, isolation allows entering stealing loop with non-empty task pool.
867 // In principle, it is possible to process reloaded tasks without locking but it will
868 // complicate the logic of get_task_and_activate_task_pool (TODO: evaluate).
870#else
872#endif
874 fast_reverse_vector<task*> tasks(arr, min_task_pool_size);
875 task **link = &offloaded_tasks;
876 while ( task *t = *link ) {
877 task** next_ptr = &t->prefix().next_offloaded;
878 __TBB_ASSERT( !is_proxy(*t), "The proxy tasks cannot be offloaded" );
879 if ( priority(*t) >= top_priority ) {
880 tasks.push_back( t );
881 // Note that owner is an alias of next_offloaded. Thus the following
882 // assignment overwrites *next_ptr
883 task* next = *next_ptr;
884 t->prefix().owner = this;
885 __TBB_ASSERT( t->prefix().state == task::ready, NULL );
886 *link = next;
887 }
888 else {
889 link = next_ptr;
890 }
891 }
892 if ( link == &offloaded_tasks ) {
893 offloaded_tasks = NULL;
894#if TBB_USE_ASSERT
895 offloaded_task_list_link = NULL;
896#endif /* TBB_USE_ASSERT */
897 }
898 else {
899 __TBB_ASSERT( link, NULL );
900 // Mark end of list
901 *link = NULL;
902 offloaded_task_list_link = link;
903 }
904 __TBB_ASSERT( link, NULL );
905 size_t num_tasks = tasks.size();
906 if ( !num_tasks ) {
908 return NULL;
909 }
910
911 // Copy found tasks into the task pool.
912 GATHER_STATISTIC( ++my_counters.prio_tasks_reloaded );
913 size_t T = prepare_task_pool( num_tasks );
914 tasks.copy_memory( my_arena_slot->task_pool_ptr + T );
915
916 // Find a task available for execution.
917 task *t = get_task_and_activate_task_pool( __TBB_load_relaxed( my_arena_slot->head ), __TBB_ISOLATION_ARG( T + num_tasks, isolation ) );
918 if ( t ) --num_tasks;
919 if ( num_tasks )
921
922 return t;
923}
924
925task* generic_scheduler::reload_tasks( __TBB_ISOLATION_EXPR( isolation_tag isolation ) ) {
926 uintptr_t reload_epoch = *my_ref_reload_epoch;
927 __TBB_ASSERT( my_offloaded_tasks, NULL );
928 __TBB_ASSERT( my_local_reload_epoch <= reload_epoch
929 || my_local_reload_epoch - reload_epoch > uintptr_t(-1)/2,
930 "Reload epoch counter overflow?" );
931 if ( my_local_reload_epoch == reload_epoch )
932 return NULL;
933 __TBB_ASSERT( my_offloaded_tasks, NULL );
934 intptr_t top_priority = effective_reference_priority();
935 __TBB_ASSERT( (uintptr_t)top_priority < (uintptr_t)num_priority_levels, NULL );
936 task *t = reload_tasks( my_offloaded_tasks, my_offloaded_task_list_tail_link, __TBB_ISOLATION_ARG( top_priority, isolation ) );
937 if ( my_offloaded_tasks && (my_arena->my_bottom_priority >= top_priority || !my_arena->my_num_workers_requested) ) {
938 // Safeguard against deliberately relaxed synchronization while checking
939 // for the presence of work in arena (so that not to impact hot paths).
940 // Arena may be reset to empty state when offloaded low priority tasks
941 // are still present. This results in both bottom and top priority bounds
942 // becoming 'normal', which makes offloaded low priority tasks unreachable.
943 // Update arena's bottom priority to accommodate them.
944 // NOTE: If the number of priority levels is increased, we may want
945 // to calculate minimum of priorities in my_offloaded_tasks.
946
947 // First indicate the presence of lower-priority tasks
948 my_market->update_arena_priority( *my_arena, priority(*my_offloaded_tasks) );
949 // Then mark arena as full to unlock arena priority level adjustment
950 // by arena::is_out_of_work(), and ensure worker's presence
952 }
953 my_local_reload_epoch = reload_epoch;
954 return t;
955}
956#endif /* __TBB_TASK_PRIORITY */
957
958#if __TBB_TASK_ISOLATION
959inline task* generic_scheduler::get_task( size_t T, isolation_tag isolation, bool& tasks_omitted )
960#else
962#endif /* __TBB_TASK_ISOLATION */
963{
964 __TBB_ASSERT( __TBB_load_relaxed( my_arena_slot->tail ) <= T
965 || is_local_task_pool_quiescent(), "Is it safe to get a task at position T?" );
966
967 task* result = my_arena_slot->task_pool_ptr[T];
968 __TBB_ASSERT( !is_poisoned( result ), "The poisoned task is going to be processed" );
969#if __TBB_TASK_ISOLATION
970 if ( !result )
971 return NULL;
972
973 bool omit = isolation != no_isolation && isolation != result->prefix().isolation;
974 if ( !omit && !is_proxy( *result ) )
975 return result;
976 else if ( omit ) {
977 tasks_omitted = true;
978 return NULL;
979 }
980#else
981 poison_pointer( my_arena_slot->task_pool_ptr[T] );
982 if ( !result || !is_proxy( *result ) )
983 return result;
984#endif /* __TBB_TASK_ISOLATION */
985
986 task_proxy& tp = static_cast<task_proxy&>(*result);
987 if ( task *t = tp.extract_task<task_proxy::pool_bit>() ) {
988 GATHER_STATISTIC( ++my_counters.proxies_executed );
989 // Following assertion should be true because TBB 2.0 tasks never specify affinity, and hence are not proxied.
990 __TBB_ASSERT( is_version_3_task( *t ), "backwards compatibility with TBB 2.0 broken" );
991 my_innermost_running_task = t; // prepare for calling note_affinity()
992#if __TBB_TASK_ISOLATION
993 // Task affinity has changed. Postpone calling note_affinity because the task pool is in invalid state.
994 if ( !tasks_omitted )
995#endif /* __TBB_TASK_ISOLATION */
996 {
997 poison_pointer( my_arena_slot->task_pool_ptr[T] );
998 t->note_affinity( my_affinity_id );
999 }
1000 return t;
1001 }
1002
1003 // Proxy was empty, so it's our responsibility to free it
1004 free_task<small_task>( tp );
1005#if __TBB_TASK_ISOLATION
1006 if ( tasks_omitted )
1007 my_arena_slot->task_pool_ptr[T] = NULL;
1008#endif /* __TBB_TASK_ISOLATION */
1009 return NULL;
1010}
1011
1014 // The current task position in the task pool.
1015 size_t T0 = __TBB_load_relaxed( my_arena_slot->tail );
1016 // The bounds of available tasks in the task pool. H0 is only used when the head bound is reached.
1017 size_t H0 = (size_t)-1, T = T0;
1018 task* result = NULL;
1019 bool task_pool_empty = false;
1020 __TBB_ISOLATION_EXPR( bool tasks_omitted = false );
1021 do {
1022 __TBB_ASSERT( !result, NULL );
1023 __TBB_store_relaxed( my_arena_slot->tail, --T );
1024 atomic_fence();
1025 if ( (intptr_t)__TBB_load_relaxed( my_arena_slot->head ) > (intptr_t)T ) {
1027 H0 = __TBB_load_relaxed( my_arena_slot->head );
1028 if ( (intptr_t)H0 > (intptr_t)T ) {
1029 // The thief has not backed off - nothing to grab.
1031 && T == __TBB_load_relaxed( my_arena_slot->tail )
1032 && H0 == T + 1, "victim/thief arbitration algorithm failure" );
1034 // No tasks in the task pool.
1035 task_pool_empty = true;
1036 break;
1037 } else if ( H0 == T ) {
1038 // There is only one task in the task pool.
1040 task_pool_empty = true;
1041 } else {
1042 // Release task pool if there are still some tasks.
1043 // After the release, the tail will be less than T, thus a thief
1044 // will not attempt to get a task at position T.
1046 }
1047 }
1048 __TBB_control_consistency_helper(); // on my_arena_slot->head
1049#if __TBB_TASK_ISOLATION
1050 result = get_task( T, isolation, tasks_omitted );
1051 if ( result ) {
1052 poison_pointer( my_arena_slot->task_pool_ptr[T] );
1053 break;
1054 } else if ( !tasks_omitted ) {
1055 poison_pointer( my_arena_slot->task_pool_ptr[T] );
1056 __TBB_ASSERT( T0 == T+1, NULL );
1057 T0 = T;
1058 }
1059#else
1060 result = get_task( T );
1061#endif /* __TBB_TASK_ISOLATION */
1062 } while ( !result && !task_pool_empty );
1063
1064#if __TBB_TASK_ISOLATION
1065 if ( tasks_omitted ) {
1066 if ( task_pool_empty ) {
1067 // All tasks have been checked. The task pool should be in reset state.
1068 // We just restore the bounds for the available tasks.
1069 // TODO: Does it have sense to move them to the beginning of the task pool?
1071 if ( result ) {
1072 // If we have a task, it should be at H0 position.
1073 __TBB_ASSERT( H0 == T, NULL );
1074 ++H0;
1075 }
1076 __TBB_ASSERT( H0 <= T0, NULL );
1077 if ( H0 < T0 ) {
1078 // Restore the task pool if there are some tasks.
1081 // The release fence is used in publish_task_pool.
1083 // Synchronize with snapshot as we published some tasks.
1085 }
1086 } else {
1087 // A task has been obtained. We need to make a hole in position T.
1089 __TBB_ASSERT( result, NULL );
1090 my_arena_slot->task_pool_ptr[T] = NULL;
1092 // Synchronize with snapshot as we published some tasks.
1093 // TODO: consider some approach not to call wakeup for each time. E.g. check if the tail reached the head.
1095 }
1096
1097 // Now it is safe to call note_affinity because the task pool is restored.
1098 if ( my_innermost_running_task == result ) {
1099 assert_task_valid( result );
1100 result->note_affinity( my_affinity_id );
1101 }
1102 }
1103#endif /* __TBB_TASK_ISOLATION */
1104 __TBB_ASSERT( (intptr_t)__TBB_load_relaxed( my_arena_slot->tail ) >= 0, NULL );
1105 __TBB_ASSERT( result || __TBB_ISOLATION_EXPR( tasks_omitted || ) is_quiescent_local_task_pool_reset(), NULL );
1106 return result;
1107} // generic_scheduler::get_task
1108
1110 // Try to steal a task from a random victim.
1111 size_t k = my_random.get() % (my_arena->my_limit-1);
1112 arena_slot* victim = &my_arena->my_slots[k];
1113 // The following condition excludes the master that might have
1114 // already taken our previous place in the arena from the list .
1115 // of potential victims. But since such a situation can take
1116 // place only in case of significant oversubscription, keeping
1117 // the checks simple seems to be preferable to complicating the code.
1118 if( k >= my_arena_index )
1119 ++victim; // Adjusts random distribution to exclude self
1120 task **pool = victim->task_pool;
1121 task *t = NULL;
1122 if( pool == EmptyTaskPool || !(t = steal_task_from( __TBB_ISOLATION_ARG(*victim, isolation) )) )
1123 return NULL;
1124 if( is_proxy(*t) ) {
1125 task_proxy &tp = *(task_proxy*)t;
1127 if ( !t ) {
1128 // Proxy was empty, so it's our responsibility to free it
1129 free_task<no_cache_small_task>(tp);
1130 return NULL;
1131 }
1132 GATHER_STATISTIC( ++my_counters.proxies_stolen );
1133 }
1135 if( is_version_3_task(*t) ) {
1137 t->prefix().owner = this;
1139 }
1140 GATHER_STATISTIC( ++my_counters.steals_committed );
1141 return t;
1142}
1143
1145 task** victim_pool = lock_task_pool( &victim_slot );
1146 if ( !victim_pool )
1147 return NULL;
1148 task* result = NULL;
1149 size_t H = __TBB_load_relaxed(victim_slot.head); // mirror
1150 size_t H0 = H;
1151 bool tasks_omitted = false;
1152 do {
1153 __TBB_store_relaxed( victim_slot.head, ++H );
1154 atomic_fence();
1155 if ( (intptr_t)H > (intptr_t)__TBB_load_relaxed( victim_slot.tail ) ) {
1156 // Stealing attempt failed, deque contents has not been changed by us
1157 GATHER_STATISTIC( ++my_counters.thief_backoffs );
1158 __TBB_store_relaxed( victim_slot.head, /*dead: H = */ H0 );
1159 __TBB_ASSERT( !result, NULL );
1160 goto unlock;
1161 }
1162 __TBB_control_consistency_helper(); // on victim_slot.tail
1163 result = victim_pool[H-1];
1164 __TBB_ASSERT( !is_poisoned( result ), NULL );
1165
1166 if ( result ) {
1167 __TBB_ISOLATION_EXPR( if ( isolation == no_isolation || isolation == result->prefix().isolation ) )
1168 {
1169 if ( !is_proxy( *result ) )
1170 break;
1171 task_proxy& tp = *static_cast<task_proxy*>(result);
1172 // If mailed task is likely to be grabbed by its destination thread, skip it.
1174 break;
1175 GATHER_STATISTIC( ++my_counters.proxies_bypassed );
1176 }
1177 // The task cannot be executed either due to isolation or proxy constraints.
1178 result = NULL;
1179 tasks_omitted = true;
1180 } else if ( !tasks_omitted ) {
1181 // Cleanup the task pool from holes until a task is skipped.
1182 __TBB_ASSERT( H0 == H-1, NULL );
1183 poison_pointer( victim_pool[H0] );
1184 H0 = H;
1185 }
1186 } while ( !result );
1187 __TBB_ASSERT( result, NULL );
1188
1189 // emit "task was consumed" signal
1190 ITT_NOTIFY( sync_acquired, (void*)((uintptr_t)&victim_slot+sizeof( uintptr_t )) );
1191 poison_pointer( victim_pool[H-1] );
1192 if ( tasks_omitted ) {
1193 // Some proxies in the task pool have been omitted. Set the stolen task to NULL.
1194 victim_pool[H-1] = NULL;
1195 __TBB_store_relaxed( victim_slot.head, /*dead: H = */ H0 );
1196 }
1197unlock:
1198 unlock_task_pool( &victim_slot, victim_pool );
1199#if __TBB_PREFETCHING
1200 __TBB_cl_evict(&victim_slot.head);
1201 __TBB_cl_evict(&victim_slot.tail);
1202#endif
1203 if ( tasks_omitted )
1204 // Synchronize with snapshot as the head and tail can be bumped which can falsely trigger EMPTY state
1206 return result;
1207}
1208
1209#if __TBB_PREVIEW_CRITICAL_TASKS
1210// Retrieves critical task respecting isolation level, if provided. The rule is:
1211// 1) If no outer critical task and no isolation => take any critical task
1212// 2) If working on an outer critical task and no isolation => cannot take any critical task
1213// 3) If no outer critical task but isolated => respect isolation
1214// 4) If working on an outer critical task and isolated => respect isolation
1215task* generic_scheduler::get_critical_task( __TBB_ISOLATION_EXPR(isolation_tag isolation) ) {
1216 __TBB_ASSERT( my_arena && my_arena_slot, "Must be attached to arena" );
1217 if( my_arena->my_critical_task_stream.empty(0) )
1218 return NULL;
1219 task* critical_task = NULL;
1220 // To keep some LIFO-ness, start search with the lane that was used during push operation.
1221 unsigned& start_lane = my_arena_slot->hint_for_critical;
1222#if __TBB_TASK_ISOLATION
1223 if( isolation != no_isolation ) {
1224 critical_task = my_arena->my_critical_task_stream.pop_specific( 0, start_lane, isolation );
1225 } else
1226#endif
1227 if( !my_properties.has_taken_critical_task ) {
1228 critical_task = my_arena->my_critical_task_stream.pop( 0, preceding_lane_selector(start_lane) );
1229 }
1230 return critical_task;
1231}
1232#endif
1233
1235 __TBB_ASSERT( my_affinity_id>0, "not in arena" );
1236 while ( task_proxy* const tp = my_inbox.pop( __TBB_ISOLATION_EXPR( isolation ) ) ) {
1237 if ( task* result = tp->extract_task<task_proxy::mailbox_bit>() ) {
1238 ITT_NOTIFY( sync_acquired, my_inbox.outbox() );
1239 result->prefix().extra_state |= es_task_is_stolen;
1240 return result;
1241 }
1242 // We have exclusive access to the proxy, and can destroy it.
1243 free_task<no_cache_small_task>(*tp);
1244 }
1245 return NULL;
1246}
1247
1249 __TBB_ASSERT ( my_arena, "no arena: initialization not completed?" );
1250 __TBB_ASSERT ( my_arena_index < my_arena->my_num_slots, "arena slot index is out-of-bound" );
1252 __TBB_ASSERT ( my_arena_slot->task_pool == EmptyTaskPool, "someone else grabbed my arena slot?" );
1254 "entering arena without tasks to share" );
1255 // Release signal on behalf of previously spawned tasks (when this thread was not in arena yet)
1257 __TBB_store_with_release( my_arena_slot->task_pool, my_arena_slot->task_pool_ptr );
1258}
1259
1261 __TBB_ASSERT( is_task_pool_published(), "Not in arena" );
1262 // Do not reset my_arena_index. It will be used to (attempt to) re-acquire the slot next time
1263 __TBB_ASSERT( &my_arena->my_slots[my_arena_index] == my_arena_slot, "arena slot and slot index mismatch" );
1264 __TBB_ASSERT ( my_arena_slot->task_pool == LockedTaskPool, "Task pool must be locked when leaving arena" );
1265 __TBB_ASSERT ( is_quiescent_local_task_pool_empty(), "Cannot leave arena when the task pool is not empty" );
1267 // No release fence is necessary here as this assignment precludes external
1268 // accesses to the local task pool when becomes visible. Thus it is harmless
1269 // if it gets hoisted above preceding local bookkeeping manipulations.
1271}
1272
1274 generic_scheduler* s = allocate_scheduler( m, genuine );
1275 __TBB_ASSERT(!genuine || index, "workers should have index > 0");
1276 s->my_arena_index = index; // index is not a real slot in arena yet
1277 s->my_dummy_task->prefix().ref_count = 2;
1278 s->my_properties.type = scheduler_properties::worker;
1279 // Do not call init_stack_info before the scheduler is set as master or worker.
1280 if (genuine)
1281 s->init_stack_info();
1283 return s;
1284}
1285
1286// TODO: make it a member method
1288 // add an internal market reference; the public reference is possibly added in create_arena
1289 generic_scheduler* s = allocate_scheduler( market::global_market(/*is_public=*/false), /* genuine = */ true );
1290 __TBB_ASSERT( !s->my_arena, NULL );
1291 __TBB_ASSERT( s->my_market, NULL );
1292 task& t = *s->my_dummy_task;
1293 s->my_properties.type = scheduler_properties::master;
1294 t.prefix().ref_count = 1;
1295#if __TBB_TASK_GROUP_CONTEXT
1296 t.prefix().context = new ( NFS_Allocate(1, sizeof(task_group_context), NULL) )
1298#if __TBB_FP_CONTEXT
1299 s->default_context()->capture_fp_settings();
1300#endif
1301 // Do not call init_stack_info before the scheduler is set as master or worker.
1302 s->init_stack_info();
1303 context_state_propagation_mutex_type::scoped_lock lock(the_context_state_propagation_mutex);
1304 s->my_market->my_masters.push_front( *s );
1305 lock.release();
1306#endif /* __TBB_TASK_GROUP_CONTEXT */
1307 if( a ) {
1308 // Master thread always occupies the first slot
1309 s->attach_arena( a, /*index*/0, /*is_master*/true );
1310 s->my_arena_slot->my_scheduler = s;
1311#if __TBB_TASK_GROUP_CONTEXT
1312 a->my_default_ctx = s->default_context(); // also transfers implied ownership
1313#endif
1314 }
1315 __TBB_ASSERT( s->my_arena_index == 0, "Master thread must occupy the first slot in its arena" );
1317
1318#if _WIN32||_WIN64
1319 s->my_market->register_master( s->master_exec_resource );
1320#endif /* _WIN32||_WIN64 */
1321 // Process any existing observers.
1322#if __TBB_ARENA_OBSERVER
1323 __TBB_ASSERT( !a || a->my_observers.empty(), "Just created arena cannot have any observers associated with it" );
1324#endif
1325#if __TBB_SCHEDULER_OBSERVER
1326 the_global_observer_list.notify_entry_observers( s->my_last_global_observer, /*worker=*/false );
1327#endif /* __TBB_SCHEDULER_OBSERVER */
1328 return s;
1329}
1330
1331void generic_scheduler::cleanup_worker( void* arg, bool worker ) {
1333 __TBB_ASSERT( !s.my_arena_slot, "cleaning up attached worker" );
1334#if __TBB_SCHEDULER_OBSERVER
1335 if ( worker ) // can be called by master for worker, do not notify master twice
1336 the_global_observer_list.notify_exit_observers( s.my_last_global_observer, /*worker=*/true );
1337#endif /* __TBB_SCHEDULER_OBSERVER */
1338 s.cleanup_scheduler();
1339}
1340
1341bool generic_scheduler::cleanup_master( bool blocking_terminate ) {
1342 arena* const a = my_arena;
1343 market * const m = my_market;
1344 __TBB_ASSERT( my_market, NULL );
1345 if( a && is_task_pool_published() ) {
1347 if ( my_arena_slot->task_pool == EmptyTaskPool ||
1349 {
1350 // Local task pool is empty
1352 }
1353 else {
1354 // Master's local task pool may e.g. contain proxies of affinitized tasks.
1356 __TBB_ASSERT ( governor::is_set(this), "TLS slot is cleared before the task pool cleanup" );
1357 // Set refcount to make the following dispach loop infinite (it is interrupted by the cleanup logic).
1361 __TBB_ASSERT ( governor::is_set(this), "Other thread reused our TLS key during the task pool cleanup" );
1362 }
1363 }
1364#if __TBB_ARENA_OBSERVER
1365 if( a )
1366 a->my_observers.notify_exit_observers( my_last_local_observer, /*worker=*/false );
1367#endif
1368#if __TBB_SCHEDULER_OBSERVER
1369 the_global_observer_list.notify_exit_observers( my_last_global_observer, /*worker=*/false );
1370#endif /* __TBB_SCHEDULER_OBSERVER */
1371#if _WIN32||_WIN64
1372 m->unregister_master( master_exec_resource );
1373#endif /* _WIN32||_WIN64 */
1374 if( a ) {
1375 __TBB_ASSERT(a->my_slots+0 == my_arena_slot, NULL);
1376#if __TBB_STATISTICS
1377 *my_arena_slot->my_counters += my_counters;
1378#endif /* __TBB_STATISTICS */
1380 }
1381#if __TBB_TASK_GROUP_CONTEXT
1382 else { // task_group_context ownership was not transferred to arena
1383 default_context()->~task_group_context();
1384 NFS_Free(default_context());
1385 }
1386 context_state_propagation_mutex_type::scoped_lock lock(the_context_state_propagation_mutex);
1387 my_market->my_masters.remove( *this );
1388 lock.release();
1389#endif /* __TBB_TASK_GROUP_CONTEXT */
1390 my_arena_slot = NULL; // detached from slot
1391 cleanup_scheduler(); // do not use scheduler state after this point
1392
1393 if( a )
1395 // If there was an associated arena, it added a public market reference
1396 return m->release( /*is_public*/ a != NULL, blocking_terminate );
1397}
1398
1399} // namespace internal
1400} // namespace tbb
1401
1402/*
1403 Comments:
1404
14051. The premise of the cancellation support implementation is that cancellations are
1406 not part of the hot path of the program execution. Therefore all changes in its
1407 implementation in order to reduce the overhead of the cancellation control flow
1408 should be done only in ways that do not increase overhead of the normal execution.
1409
1410 In general contexts are used by all threads and their descendants are created in
1411 different threads as well. In order to minimize impact of the cross-thread tree
1412 maintenance (first of all because of the synchronization), the tree of contexts
1413 is split into pieces, each of which is handled by the only thread. Such pieces
1414 are represented as lists of contexts, members of which are contexts that were
1415 bound to their parents in the given thread.
1416
1417 The context tree maintenance and cancellation propagation algorithms is designed
1418 in such a manner that cross-thread access to a context list will take place only
1419 when cancellation signal is sent (by user or when an exception happens), and
1420 synchronization is necessary only then. Thus the normal execution flow (without
1421 exceptions and cancellation) remains free from any synchronization done on
1422 behalf of exception handling and cancellation support.
1423
14242. Consider parallel cancellations at the different levels of the context tree:
1425
1426 Ctx1 <- Cancelled by Thread1 |- Thread2 started processing
1427 | |
1428 Ctx2 |- Thread1 started processing
1429 | T1 |- Thread2 finishes and syncs up local counters
1430 Ctx3 <- Cancelled by Thread2 |
1431 | |- Ctx5 is bound to Ctx2
1432 Ctx4 |
1433 T2 |- Thread1 reaches Ctx2
1434
1435 Thread-propagator of each cancellation increments global counter. However the thread
1436 propagating the cancellation from the outermost context (Thread1) may be the last
1437 to finish. Which means that the local counters may be synchronized earlier (by Thread2,
1438 at Time1) than it propagated cancellation into Ctx2 (at time Time2). If a new context
1439 (Ctx5) is created and bound to Ctx2 between Time1 and Time2, checking its parent only
1440 (Ctx2) may result in cancellation request being lost.
1441
1442 This issue is solved by doing the whole propagation under the lock.
1443
1444 If we need more concurrency while processing parallel cancellations, we could try
1445 the following modification of the propagation algorithm:
1446
1447 advance global counter and remember it
1448 for each thread:
1449 scan thread's list of contexts
1450 for each thread:
1451 sync up its local counter only if the global counter has not been changed
1452
1453 However this version of the algorithm requires more analysis and verification.
1454
14553. There is no portable way to get stack base address in Posix, however the modern
1456 Linux versions provide pthread_attr_np API that can be used to obtain thread's
1457 stack size and base address. Unfortunately even this function does not provide
1458 enough information for the main thread on IA-64 architecture (RSE spill area
1459 and memory stack are allocated as two separate discontinuous chunks of memory),
1460 and there is no portable way to discern the main and the secondary threads.
1461 Thus for macOS* and IA-64 architecture for Linux* OS we use the TBB worker stack size for
1462 all threads and use the current stack top as the stack base. This simplified
1463 approach is based on the following assumptions:
1464 1) If the default stack size is insufficient for the user app needs, the
1465 required amount will be explicitly specified by the user at the point of the
1466 TBB scheduler initialization (as an argument to tbb::task_scheduler_init
1467 constructor).
1468 2) When a master thread initializes the scheduler, it has enough space on its
1469 stack. Here "enough" means "at least as much as worker threads have".
1470 3) If the user app strives to conserve the memory by cutting stack size, it
1471 should do this for TBB workers too (as in the #1).
1472*/
#define __TBB_control_consistency_helper()
Definition: gcc_generic.h:60
#define __TBB_Yield()
Definition: ibm_aix51.h:44
void * __TBB_get_bsp()
Retrieves the current RSE backing store pointer. IA64 specific.
#define __TBB_cl_prefetch(p)
Definition: mic_common.h:33
#define __TBB_cl_evict(p)
Definition: mic_common.h:34
#define __TBB_PREVIEW_RESUMABLE_TASKS
Definition: tbb_config.h:866
#define TBB_USE_ASSERT
Definition: tbb_config.h:438
#define __TBB_FetchAndDecrementWrelease(P)
Definition: tbb_machine.h:311
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:165
#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
#define ITT_SYNC_CREATE(obj, type, name)
Definition: itt_notify.h:115
#define ITT_NOTIFY(name, obj)
Definition: itt_notify.h:112
#define LockedTaskPool
Definition: scheduler.h:47
#define EmptyTaskPool
Definition: scheduler.h:46
#define __TBB_CONTEXT_ARG(arg1, context)
#define __TBB_ISOLATION_EXPR(isolation)
#define __TBB_ISOLATION_ARG(arg1, isolation)
#define GATHER_STATISTIC(x)
void const char const char int ITT_FORMAT __itt_group_sync s
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t new_size
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p 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 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 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
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
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p void ITT_FORMAT p no args __itt_suppress_mode_t unsigned int void size_t ITT_FORMAT d void ITT_FORMAT p void ITT_FORMAT p __itt_model_site __itt_model_site_instance ITT_FORMAT p __itt_model_task __itt_model_task_instance ITT_FORMAT p void ITT_FORMAT p void ITT_FORMAT p void size_t ITT_FORMAT d void ITT_FORMAT p const wchar_t ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s const char ITT_FORMAT s no args void ITT_FORMAT p size_t ITT_FORMAT d no args const wchar_t const wchar_t ITT_FORMAT s __itt_heap_function void size_t int ITT_FORMAT d __itt_heap_function void ITT_FORMAT p __itt_heap_function void void size_t int ITT_FORMAT d no args no args unsigned int ITT_FORMAT u const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_id __itt_id parent
void const char const char int ITT_FORMAT __itt_group_sync x void const char ITT_FORMAT __itt_group_sync s void ITT_FORMAT __itt_group_sync p void ITT_FORMAT p sync_releasing
void const char const char int ITT_FORMAT __itt_group_sync p
void *__TBB_EXPORTED_FUNC NFS_Allocate(size_t n_element, size_t element_size, void *hint)
Allocate memory on cache/sector line boundary.
void __TBB_EXPORTED_FUNC NFS_Free(void *)
Free memory allocated by NFS_Allocate.
The graph class.
void atomic_fence()
Sequentially consistent full memory fence.
Definition: tbb_machine.h:339
@ release
Release.
Definition: atomic.h:59
@ relaxed
No ordering.
Definition: atomic.h:61
const size_t task_prefix_reservation_size
Number of bytes reserved for a task prefix.
intptr_t isolation_tag
A tag for task isolation.
Definition: task.h:143
void __TBB_store_relaxed(volatile T &location, V value)
Definition: tbb_machine.h:739
intptr_t reference_count
A reference count.
Definition: task.h:131
bool is_critical(task &t)
Definition: task.h:1014
void assert_task_valid(const task *)
unsigned short affinity_id
An id as used for specifying affinity.
Definition: task.h:139
void suppress_unused_warning(const T1 &)
Utility template function to prevent "unused" warnings by various compilers.
Definition: tbb_stddef.h:398
void poison_pointer(T *__TBB_atomic &)
Definition: tbb_stddef.h:305
@ es_task_proxy
Tag for v3 task_proxy.
@ es_ref_count_active
Set if ref_count might be changed by another thread. Used for debugging.
@ es_task_is_stolen
Set if the task has been stolen.
const size_t MByte
Definition: tbb_misc.h:45
void Scheduler_OneTimeInitialization(bool itt_present)
Defined in scheduler.cpp.
Definition: scheduler.cpp:52
T max(const T &val1, const T &val2)
Utility template function returning greater of the two values.
Definition: tbb_misc.h:119
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:399
generic_scheduler * allocate_scheduler(market &m, bool genuine)
Definition: scheduler.cpp:37
atomic< T > & as_atomic(T &t)
Definition: atomic.h:572
T __TBB_load_relaxed(const volatile T &location)
Definition: tbb_machine.h:735
const isolation_tag no_isolation
Definition: task.h:144
auto first(Container &c) -> decltype(begin(c))
generic_scheduler *(* AllocateSchedulerPtr)(market &, bool)
Pointer to the scheduler factory function.
Definition: tbb_main.cpp:75
static const intptr_t num_priority_levels
void __TBB_store_with_release(volatile T &location, V value)
Definition: tbb_machine.h:713
Represents acquisition of a mutex.
Definition: spin_mutex.h:53
virtual ~scheduler()=0
Pure virtual destructor;.
Definition: scheduler.cpp:72
context_list_node_t * my_next
Definition: task.h:152
Memory prefix to a task object.
Definition: task.h:203
tbb::task * next
"next" field for list of task
Definition: task.h:297
scheduler * origin
The scheduler that allocated the task, or NULL if the task is big.
Definition: task.h:239
scheduler * owner
Obsolete. The scheduler that owns the task.
Definition: task.h:247
unsigned char extra_state
Miscellaneous state that is not directly visible to users, stored as a byte for compactness.
Definition: task.h:292
isolation_tag isolation
The tag used for task isolation.
Definition: task.h:220
__TBB_atomic reference_count ref_count
Reference count used for synchronization.
Definition: task.h:274
unsigned char state
A task::state_type, stored as a byte for compactness.
Definition: task.h:283
task_group_context * context
Shared context that is used to communicate asynchronous state changes.
Definition: task.h:230
tbb::task * parent
The task whose reference count includes me.
Definition: task.h:267
affinity_id affinity
Definition: task.h:294
Used to form groups of tasks.
Definition: task.h:358
__TBB_atomic kind_type my_kind
Flavor of this context: bound or isolated.
Definition: task.h:405
static const kind_type detached
Definition: task.h:591
static const kind_type dying
Definition: task.h:592
uintptr_t my_version_and_traits
Version for run-time checks and behavioral traits of the context.
Definition: task.h:446
static const kind_type binding_required
Definition: task.h:589
Base class for user-defined tasks.
Definition: task.h:615
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
task * parent() const
task on whose behalf this task is working, or NULL if this is a root.
Definition: task.h:865
@ allocated
task object is freshly allocated or recycled.
Definition: task.h:643
@ ready
task is in ready pool, or is going to be put there, or was just taken off.
Definition: task.h:641
@ freed
task object is on free list, or is going to be put there, or was just taken off.
Definition: task.h:645
state_type state() const
Current execution state.
Definition: task.h:912
void set_ref_count(int count)
Set reference count.
Definition: task.h:761
internal::task_prefix & prefix(internal::version_tag *=NULL) const
Get reference to corresponding task_prefix.
Definition: task.h:1002
Class that implements exponential backoff.
Definition: tbb_machine.h:345
void pause()
Pause for a while.
Definition: tbb_machine.h:360
Base class for types that should not be copied or assigned.
Definition: tbb_stddef.h:330
static const unsigned ref_external
Reference increment values for externals and workers.
Definition: arena.h:327
arena_slot my_slots[1]
Definition: arena.h:390
mail_outbox & mailbox(affinity_id id)
Get reference to mailbox corresponding to given affinity_id.
Definition: arena.h:305
void advertise_new_work()
If necessary, raise a flag that there is new job in arena.
Definition: arena.h:484
void on_thread_leaving()
Notification that worker or master leaves its arena.
Definition: arena.h:394
A scheduler with a customized evaluation loop.
static bool is_set(generic_scheduler *s)
Used to check validity of the local scheduler TLS contents.
Definition: governor.cpp:120
static generic_scheduler * local_scheduler()
Obtain the thread-local instance of the TBB scheduler.
Definition: governor.h:129
static void sign_off(generic_scheduler *s)
Unregister TBB scheduler instance from thread-local storage.
Definition: governor.cpp:145
static void sign_on(generic_scheduler *s)
Register TBB scheduler instance in thread-local storage.
Definition: governor.cpp:124
mail_outbox * outbox
Mailbox to which this was mailed.
Definition: mailbox.h:43
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
task * extract_task()
Returns a pointer to the encapsulated task or NULL, and frees proxy if necessary.
Definition: mailbox.h:57
static const intptr_t pool_bit
Definition: mailbox.h:30
static const intptr_t mailbox_bit
Definition: mailbox.h:31
static const intptr_t location_mask
Definition: mailbox.h:32
bool recipient_is_idle()
True if thread that owns this mailbox is looking for work.
Definition: mailbox.h:190
bool push(task_proxy *t)
Push task_proxy onto the mailbox queue of another thread.
Definition: mailbox.h:147
task_proxy * pop(__TBB_ISOLATION_EXPR(isolation_tag isolation))
Get next piece of mail, or NULL if mailbox is empty.
Definition: mailbox.h:213
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
bool release(bool is_public, bool blocking_terminate)
Decrements market's refcount and destroys it in the end.
Definition: market.cpp:175
size_t worker_stack_size() const
Returns the requested stack size of worker threads.
Definition: market.h:314
bool outermost
Indicates that a scheduler is on outermost level.
Definition: scheduler.h:57
size_t my_arena_index
Index of the arena slot the scheduler occupies now, or occupied last time.
Definition: scheduler.h:79
affinity_id my_affinity_id
The mailbox id assigned to this scheduler.
Definition: scheduler.h:99
arena * my_arena
The arena that I own (if master) or am servicing at the moment (if worker)
Definition: scheduler.h:85
arena_slot * my_arena_slot
Pointer to the slot in the arena we own at the moment.
Definition: scheduler.h:82
task * my_innermost_running_task
Innermost task whose task::execute() is running. A dummy task on the outermost level.
Definition: scheduler.h:88
scheduler_properties my_properties
Definition: scheduler.h:101
Work stealing task scheduler.
Definition: scheduler.h:140
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
bool is_quiescent_local_task_pool_reset() const
Definition: scheduler.h:644
task * get_task(__TBB_ISOLATION_EXPR(isolation_tag isolation))
Get a task from the local pool.
Definition: scheduler.cpp:1012
static const size_t min_task_pool_size
Definition: scheduler.h:369
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:1144
static task * plugged_return_list()
Special value used to mark my_return_list as not taking any more entries.
Definition: scheduler.h:458
void enqueue(task &, void *reserved) __TBB_override
For internal use only.
Definition: scheduler.cpp:749
bool is_worker() const
True if running on a worker thread, false otherwise.
Definition: scheduler.h:673
static bool is_version_3_task(task &t)
Definition: scheduler.h:146
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_atomic intptr_t my_small_task_count
Number of small tasks that have been allocated by this scheduler.
Definition: scheduler.h:461
void spawn(task &first, task *&next) __TBB_override
For internal use only.
Definition: scheduler.cpp:741
virtual void local_wait_for_all(task &parent, task *child)=0
task * my_free_list
Free list of small tasks that can be reused.
Definition: scheduler.h:178
bool is_quiescent_local_task_pool_empty() const
Definition: scheduler.h:639
static generic_scheduler * create_worker(market &m, size_t index, bool geniune)
Initialize a scheduler for a worker thread.
Definition: scheduler.cpp:1273
task * get_mailbox_task(__TBB_ISOLATION_EXPR(isolation_tag isolation))
Attempt to get a task from the mailbox.
Definition: scheduler.cpp:1234
void spawn_root_and_wait(task &first, task *&next) __TBB_override
For internal use only.
Definition: scheduler.cpp:745
void release_task_pool() const
Unlocks the local task pool.
Definition: scheduler.cpp:522
void free_nonlocal_small_task(task &t)
Free a small task t that that was allocated by a different scheduler.
Definition: scheduler.cpp:412
bool is_local_task_pool_quiescent() const
Definition: scheduler.h:633
void commit_spawned_tasks(size_t new_tail)
Makes newly spawned tasks visible to thieves.
Definition: scheduler.h:710
generic_scheduler(market &, bool)
Definition: scheduler.cpp:84
static bool is_proxy(const task &t)
True if t is a task_proxy.
Definition: scheduler.h:348
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
void cleanup_scheduler()
Cleans up this scheduler (the scheduler might be destroyed).
Definition: scheduler.cpp:294
void local_spawn_root_and_wait(task *first, task *&next)
Definition: scheduler.cpp:720
void unlock_task_pool(arena_slot *victim_arena_slot, task **victim_task_pool) const
Unlocks victim's task pool.
Definition: scheduler.cpp:586
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
void leave_task_pool()
Leave the task pool.
Definition: scheduler.cpp:1260
void destroy()
Destroy and deallocate this scheduler object.
Definition: scheduler.cpp:285
task * my_return_list
List of small tasks that have been returned to this scheduler by other schedulers.
Definition: scheduler.h:465
task * steal_task(__TBB_ISOLATION_EXPR(isolation_tag isolation))
Attempts to steal a task from a randomly chosen thread/scheduler.
Definition: scheduler.cpp:1109
task * my_dummy_task
Fake root task created by slave threads.
Definition: scheduler.h:186
bool cleanup_master(bool blocking_terminate)
Perform necessary cleanup when a master thread stops using TBB.
Definition: scheduler.cpp:1341
market * my_market
The market I am in.
Definition: scheduler.h:172
static generic_scheduler * create_master(arena *a)
Initialize a scheduler for a master thread.
Definition: scheduler.cpp:1287
void reset_task_pool_and_leave()
Resets head and tail indices to 0, and leaves task pool.
Definition: scheduler.h:702
void deallocate_task(task &t)
Return task object to the memory allocator.
Definition: scheduler.h:683
uintptr_t my_stealing_threshold
Position in the call stack specifying its maximal filling when stealing is still allowed.
Definition: scheduler.h:155
void acquire_task_pool() const
Locks the local task pool.
Definition: scheduler.cpp:493
void local_spawn(task *first, task *&next)
Definition: scheduler.cpp:653
static void cleanup_worker(void *arg, bool worker)
Perform necessary cleanup when a worker thread finishes.
Definition: scheduler.cpp:1331
void commit_relocated_tasks(size_t new_tail)
Makes relocated tasks visible to thieves and releases the local task pool.
Definition: scheduler.h:719
FastRandom my_random
Random number generator used for picking a random victim from which to steal.
Definition: scheduler.h:175
void publish_task_pool()
Used by workers to enter the task pool.
Definition: scheduler.cpp:1248
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
void init_stack_info()
Sets up the data necessary for the stealing limiting heuristics.
Definition: scheduler.cpp:158
void allocate_task_pool(size_t n)
void fill_with_canary_pattern(size_t, size_t)
Smart holder for the empty task class with automatic destruction.
Vector that grows without reallocations, and stores items in the reverse order.
void copy_memory(T *dst) const
Copies the contents of the vector into the dst array.
unsigned short get()
Get a random number.
Definition: tbb_misc.h:146

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.