Intel(R) Threading Building Blocks Doxygen Documentation  version 4.2.3
arena.cpp
Go to the documentation of this file.
1 /*
2  Copyright (c) 2005-2019 Intel Corporation
3 
4  Licensed under the Apache License, Version 2.0 (the "License");
5  you may not use this file except in compliance with the License.
6  You may obtain a copy of the License at
7 
8  http://www.apache.org/licenses/LICENSE-2.0
9 
10  Unless required by applicable law or agreed to in writing, software
11  distributed under the License is distributed on an "AS IS" BASIS,
12  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  See the License for the specific language governing permissions and
14  limitations under the License.
15 
16 
17 
18 
19 */
20 
21 #include "tbb/global_control.h" // thread_stack_size
22 
23 #include "scheduler.h"
24 #include "governor.h"
25 #include "arena.h"
26 #include "itt_notify.h"
27 #include "semaphore.h"
29 
30 #include <functional>
31 
32 #if __TBB_STATISTICS_STDOUT
33 #include <cstdio>
34 #endif
35 
36 namespace tbb {
37 namespace internal {
38 
39 // put it here in order to enable compiler to inline it into arena::process and nested_arena_entry
40 void generic_scheduler::attach_arena( arena* a, size_t index, bool is_master ) {
41  __TBB_ASSERT( a->my_market == my_market, NULL );
42  my_arena = a;
43  my_arena_index = index;
44  my_arena_slot = a->my_slots + index;
45  attach_mailbox( affinity_id(index+1) );
46  if ( is_master && my_inbox.is_idle_state( true ) ) {
47  // Master enters an arena with its own task to be executed. It means that master is not
48  // going to enter stealing loop and take affinity tasks.
49  my_inbox.set_is_idle( false );
50  }
51 #if __TBB_TASK_GROUP_CONTEXT
52  // Context to be used by root tasks by default (if the user has not specified one).
53  if( !is_master )
54  my_dummy_task->prefix().context = a->my_default_ctx;
55 #endif /* __TBB_TASK_GROUP_CONTEXT */
56 #if __TBB_TASK_PRIORITY
57  // In the current implementation master threads continue processing even when
58  // there are other masters with higher priority. Only TBB worker threads are
59  // redistributed between arenas based on the latters' priority. Thus master
60  // threads use arena's top priority as a reference point (in contrast to workers
61  // that use my_market->my_global_top_priority).
62  if( is_master ) {
63  my_ref_top_priority = &a->my_top_priority;
64  my_ref_reload_epoch = &a->my_reload_epoch;
65  }
66  my_local_reload_epoch = *my_ref_reload_epoch;
67  __TBB_ASSERT( !my_offloaded_tasks, NULL );
68 #endif /* __TBB_TASK_PRIORITY */
69 }
70 
71 inline static bool occupy_slot( generic_scheduler*& slot, generic_scheduler& s ) {
72  return !slot && as_atomic( slot ).compare_and_swap( &s, NULL ) == NULL;
73 }
74 
75 size_t arena::occupy_free_slot_in_range( generic_scheduler& s, size_t lower, size_t upper ) {
76  if ( lower >= upper ) return out_of_arena;
77  // Start search for an empty slot from the one we occupied the last time
78  size_t index = s.my_arena_index;
79  if ( index < lower || index >= upper ) index = s.my_random.get() % (upper - lower) + lower;
80  __TBB_ASSERT( index >= lower && index < upper, NULL );
81  // Find a free slot
82  for ( size_t i = index; i < upper; ++i )
83  if ( occupy_slot(my_slots[i].my_scheduler, s) ) return i;
84  for ( size_t i = lower; i < index; ++i )
85  if ( occupy_slot(my_slots[i].my_scheduler, s) ) return i;
86  return out_of_arena;
87 }
88 
89 template <bool as_worker>
91  // Firstly, masters try to occupy reserved slots
92  size_t index = as_worker ? out_of_arena : occupy_free_slot_in_range( s, 0, my_num_reserved_slots );
93  if ( index == out_of_arena ) {
94  // Secondly, all threads try to occupy all non-reserved slots
96  // Likely this arena is already saturated
97  if ( index == out_of_arena )
98  return out_of_arena;
99  }
100 
101  ITT_NOTIFY(sync_acquired, my_slots + index);
102  atomic_update( my_limit, (unsigned)(index + 1), std::less<unsigned>() );
103  return index;
104 }
105 
107  __TBB_ASSERT( is_alive(my_guard), NULL );
108  __TBB_ASSERT( governor::is_set(&s), NULL );
109  __TBB_ASSERT( s.my_innermost_running_task == s.my_dummy_task, NULL );
110  __TBB_ASSERT( s.worker_outermost_level(), NULL );
111 
112  __TBB_ASSERT( my_num_slots > 1, NULL );
113 
114  size_t index = occupy_free_slot</*as_worker*/true>( s );
115  if ( index == out_of_arena )
116  goto quit;
117 
118  __TBB_ASSERT( index >= my_num_reserved_slots, "Workers cannot occupy reserved slots" );
119  s.attach_arena( this, index, /*is_master*/false );
120 
121 #if !__TBB_FP_CONTEXT
123 #endif
124 
125 #if __TBB_ARENA_OBSERVER
126  __TBB_ASSERT( !s.my_last_local_observer, "There cannot be notified local observers when entering arena" );
127  my_observers.notify_entry_observers( s.my_last_local_observer, /*worker=*/true );
128 #endif /* __TBB_ARENA_OBSERVER */
129 
130  // Task pool can be marked as non-empty if the worker occupies the slot left by a master.
131  if ( s.my_arena_slot->task_pool != EmptyTaskPool ) {
132  __TBB_ASSERT( s.my_inbox.is_idle_state(false), NULL );
133  s.local_wait_for_all( *s.my_dummy_task, NULL );
134  __TBB_ASSERT( s.my_inbox.is_idle_state(true), NULL );
135  }
136 
137  for ( ;; ) {
138  __TBB_ASSERT( s.my_innermost_running_task == s.my_dummy_task, NULL );
139  __TBB_ASSERT( s.worker_outermost_level(), NULL );
140  __TBB_ASSERT( is_alive(my_guard), NULL );
141  __TBB_ASSERT( s.is_quiescent_local_task_pool_reset(),
142  "Worker cannot leave arena while its task pool is not reset" );
143  __TBB_ASSERT( s.my_arena_slot->task_pool == EmptyTaskPool, "Empty task pool is not marked appropriately" );
144  // This check prevents relinquishing more than necessary workers because
145  // of the non-atomicity of the decision making procedure
148  || recall_by_mandatory_request()
149 #endif
150  )
151  break;
152  // Try to steal a task.
153  // Passing reference count is technically unnecessary in this context,
154  // but omitting it here would add checks inside the function.
155  task* t = s.receive_or_steal_task( __TBB_ISOLATION_ARG( s.my_dummy_task->prefix().ref_count, no_isolation ) );
156  if (t) {
157  // A side effect of receive_or_steal_task is that my_innermost_running_task can be set.
158  // But for the outermost dispatch loop it has to be a dummy task.
159  s.my_innermost_running_task = s.my_dummy_task;
160  s.local_wait_for_all(*s.my_dummy_task,t);
161  }
162  }
163 #if __TBB_ARENA_OBSERVER
164  my_observers.notify_exit_observers( s.my_last_local_observer, /*worker=*/true );
165  s.my_last_local_observer = NULL;
166 #endif /* __TBB_ARENA_OBSERVER */
167 #if __TBB_TASK_PRIORITY
168  if ( s.my_offloaded_tasks )
169  orphan_offloaded_tasks( s );
170 #endif /* __TBB_TASK_PRIORITY */
171 #if __TBB_STATISTICS
172  ++s.my_counters.arena_roundtrips;
173  *my_slots[index].my_counters += s.my_counters;
174  s.my_counters.reset();
175 #endif /* __TBB_STATISTICS */
176  __TBB_store_with_release( my_slots[index].my_scheduler, (generic_scheduler*)NULL );
177  s.my_arena_slot = 0; // detached from slot
178  s.my_inbox.detach();
179  __TBB_ASSERT( s.my_inbox.is_idle_state(true), NULL );
180  __TBB_ASSERT( s.my_innermost_running_task == s.my_dummy_task, NULL );
181  __TBB_ASSERT( s.worker_outermost_level(), NULL );
182  __TBB_ASSERT( is_alive(my_guard), NULL );
183 quit:
184  // In contrast to earlier versions of TBB (before 3.0 U5) now it is possible
185  // that arena may be temporarily left unpopulated by threads. See comments in
186  // arena::on_thread_leaving() for more details.
187  on_thread_leaving<ref_worker>();
188 }
189 
190 arena::arena ( market& m, unsigned num_slots, unsigned num_reserved_slots ) {
191  __TBB_ASSERT( !my_guard, "improperly allocated arena?" );
192  __TBB_ASSERT( sizeof(my_slots[0]) % NFS_GetLineSize()==0, "arena::slot size not multiple of cache line size" );
193  __TBB_ASSERT( (uintptr_t)this % NFS_GetLineSize()==0, "arena misaligned" );
194 #if __TBB_TASK_PRIORITY
195  __TBB_ASSERT( !my_reload_epoch && !my_orphaned_tasks && !my_skipped_fifo_priority, "New arena object is not zeroed" );
196 #endif /* __TBB_TASK_PRIORITY */
197  my_market = &m;
198  my_limit = 1;
199  // Two slots are mandatory: for the master, and for 1 worker (required to support starvation resistant tasks).
200  my_num_slots = num_arena_slots(num_slots);
201  my_num_reserved_slots = num_reserved_slots;
202  my_max_num_workers = num_slots-num_reserved_slots;
203  my_references = ref_external; // accounts for the master
204 #if __TBB_TASK_PRIORITY
205  my_bottom_priority = my_top_priority = normalized_normal_priority;
206 #endif /* __TBB_TASK_PRIORITY */
208 #if __TBB_ARENA_OBSERVER
209  my_observers.my_arena = this;
210 #endif
212  // Construct slots. Mark internal synchronization elements for the tools.
213  for( unsigned i = 0; i < my_num_slots; ++i ) {
214  __TBB_ASSERT( !my_slots[i].my_scheduler && !my_slots[i].task_pool, NULL );
215  __TBB_ASSERT( !my_slots[i].task_pool_ptr, NULL );
216  __TBB_ASSERT( !my_slots[i].my_task_pool_size, NULL );
217  ITT_SYNC_CREATE(my_slots + i, SyncType_Scheduler, SyncObj_WorkerTaskPool);
218  mailbox(i+1).construct();
219  ITT_SYNC_CREATE(&mailbox(i+1), SyncType_Scheduler, SyncObj_Mailbox);
220  my_slots[i].hint_for_pop = i;
221 #if __TBB_PREVIEW_CRITICAL_TASKS
222  my_slots[i].hint_for_critical = i;
223 #endif
224 #if __TBB_STATISTICS
225  my_slots[i].my_counters = new ( NFS_Allocate(1, sizeof(statistics_counters), NULL) ) statistics_counters;
226 #endif /* __TBB_STATISTICS */
227  }
229  ITT_SYNC_CREATE(&my_task_stream, SyncType_Scheduler, SyncObj_TaskStream);
230 #if __TBB_PREVIEW_CRITICAL_TASKS
231  my_critical_task_stream.initialize(my_num_slots);
232  ITT_SYNC_CREATE(&my_critical_task_stream, SyncType_Scheduler, SyncObj_CriticalTaskStream);
233 #endif
234 #if __TBB_ENQUEUE_ENFORCED_CONCURRENCY
235  my_concurrency_mode = cm_normal;
236 #endif
237 #if !__TBB_FP_CONTEXT
239 #endif
240 }
241 
242 arena& arena::allocate_arena( market& m, unsigned num_slots, unsigned num_reserved_slots ) {
243  __TBB_ASSERT( sizeof(base_type) + sizeof(arena_slot) == sizeof(arena), "All arena data fields must go to arena_base" );
244  __TBB_ASSERT( sizeof(base_type) % NFS_GetLineSize() == 0, "arena slots area misaligned: wrong padding" );
245  __TBB_ASSERT( sizeof(mail_outbox) == NFS_MaxLineSize, "Mailbox padding is wrong" );
246  size_t n = allocation_size(num_arena_slots(num_slots));
247  unsigned char* storage = (unsigned char*)NFS_Allocate( 1, n, NULL );
248  // Zero all slots to indicate that they are empty
249  memset( storage, 0, n );
250  return *new( storage + num_arena_slots(num_slots) * sizeof(mail_outbox) ) arena(m, num_slots, num_reserved_slots);
251 }
252 
254  __TBB_ASSERT( is_alive(my_guard), NULL );
255  __TBB_ASSERT( !my_references, "There are threads in the dying arena" );
256  __TBB_ASSERT( !my_num_workers_requested && !my_num_workers_allotted, "Dying arena requests workers" );
257  __TBB_ASSERT( my_pool_state == SNAPSHOT_EMPTY || !my_max_num_workers, "Inconsistent state of a dying arena" );
258 #if __TBB_ENQUEUE_ENFORCED_CONCURRENCY
259  __TBB_ASSERT( my_concurrency_mode != cm_enforced_global, NULL );
260 #endif
261 #if !__TBB_STATISTICS_EARLY_DUMP
262  GATHER_STATISTIC( dump_arena_statistics() );
263 #endif
264  poison_value( my_guard );
265  intptr_t drained = 0;
266  for ( unsigned i = 0; i < my_num_slots; ++i ) {
267  __TBB_ASSERT( !my_slots[i].my_scheduler, "arena slot is not empty" );
268  // TODO: understand the assertion and modify
269  // __TBB_ASSERT( my_slots[i].task_pool == EmptyTaskPool, NULL );
270  __TBB_ASSERT( my_slots[i].head == my_slots[i].tail, NULL ); // TODO: replace by is_quiescent_local_task_pool_empty
272 #if __TBB_STATISTICS
273  NFS_Free( my_slots[i].my_counters );
274 #endif /* __TBB_STATISTICS */
275  drained += mailbox(i+1).drain();
276  }
277  __TBB_ASSERT( my_task_stream.drain()==0, "Not all enqueued tasks were executed");
278 #if __TBB_PREVIEW_CRITICAL_TASKS
279  __TBB_ASSERT( my_critical_task_stream.drain()==0, "Not all critical tasks were executed");
280 #endif
281 #if __TBB_COUNT_TASK_NODES
282  my_market->update_task_node_count( -drained );
283 #endif /* __TBB_COUNT_TASK_NODES */
284  // remove an internal reference
285  my_market->release( /*is_public=*/false, /*blocking_terminate=*/false );
286 #if __TBB_TASK_GROUP_CONTEXT
287  __TBB_ASSERT( my_default_ctx, "Master thread never entered the arena?" );
288  my_default_ctx->~task_group_context();
289  NFS_Free(my_default_ctx);
290 #endif /* __TBB_TASK_GROUP_CONTEXT */
291 #if __TBB_ARENA_OBSERVER
292  if ( !my_observers.empty() )
293  my_observers.clear();
294 #endif /* __TBB_ARENA_OBSERVER */
295  void* storage = &mailbox(my_num_slots);
296  __TBB_ASSERT( my_references == 0, NULL );
298  this->~arena();
299 #if TBB_USE_ASSERT > 1
300  memset( storage, 0, allocation_size(my_num_slots) );
301 #endif /* TBB_USE_ASSERT */
302  NFS_Free( storage );
303 }
304 
305 #if __TBB_STATISTICS
306 void arena::dump_arena_statistics () {
307  statistics_counters total;
308  for( unsigned i = 0; i < my_num_slots; ++i ) {
309 #if __TBB_STATISTICS_EARLY_DUMP
311  if ( s )
312  *my_slots[i].my_counters += s->my_counters;
313 #else
314  __TBB_ASSERT( !my_slots[i].my_scheduler, NULL );
315 #endif
316  if ( i != 0 ) {
317  total += *my_slots[i].my_counters;
318  dump_statistics( *my_slots[i].my_counters, i );
319  }
320  }
321  dump_statistics( *my_slots[0].my_counters, 0 );
322 #if __TBB_STATISTICS_STDOUT
323 #if !__TBB_STATISTICS_TOTALS_ONLY
324  printf( "----------------------------------------------\n" );
325 #endif
326  dump_statistics( total, workers_counters_total );
327  total += *my_slots[0].my_counters;
328  dump_statistics( total, arena_counters_total );
329 #if !__TBB_STATISTICS_TOTALS_ONLY
330  printf( "==============================================\n" );
331 #endif
332 #endif /* __TBB_STATISTICS_STDOUT */
333 }
334 #endif /* __TBB_STATISTICS */
335 
336 #if __TBB_TASK_PRIORITY
337 // The method inspects a scheduler to determine:
338 // 1. if it has tasks that can be retrieved and executed (via the return value);
339 // 2. if it has any tasks at all, including those of lower priority (via tasks_present);
340 // 3. if it is able to work with enqueued tasks (via dequeuing_possible).
341 inline bool arena::may_have_tasks ( generic_scheduler* s, bool& tasks_present, bool& dequeuing_possible ) {
342  if ( !s || s->my_arena != this )
343  return false;
344  dequeuing_possible |= s->worker_outermost_level();
345  if ( s->my_pool_reshuffling_pending ) {
346  // This primary task pool is nonempty and may contain tasks at the current
347  // priority level. Its owner is winnowing lower priority tasks at the moment.
348  tasks_present = true;
349  return true;
350  }
351  if ( s->my_offloaded_tasks ) {
352  tasks_present = true;
353  if ( s->my_local_reload_epoch < *s->my_ref_reload_epoch ) {
354  // This scheduler's offload area is nonempty and may contain tasks at the
355  // current priority level.
356  return true;
357  }
358  }
359  return false;
360 }
361 
362 void arena::orphan_offloaded_tasks(generic_scheduler& s) {
363  __TBB_ASSERT( s.my_offloaded_tasks, NULL );
364  GATHER_STATISTIC( ++s.my_counters.prio_orphanings );
365  ++my_abandonment_epoch;
366  __TBB_ASSERT( s.my_offloaded_task_list_tail_link && !*s.my_offloaded_task_list_tail_link, NULL );
367  task* orphans;
368  do {
369  orphans = const_cast<task*>(my_orphaned_tasks);
370  *s.my_offloaded_task_list_tail_link = orphans;
371  } while ( as_atomic(my_orphaned_tasks).compare_and_swap(s.my_offloaded_tasks, orphans) != orphans );
372  s.my_offloaded_tasks = NULL;
373 #if TBB_USE_ASSERT
374  s.my_offloaded_task_list_tail_link = NULL;
375 #endif /* TBB_USE_ASSERT */
376 }
377 #endif /* __TBB_TASK_PRIORITY */
378 
380  // Look for enqueued tasks at all priority levels
381  for ( int p = 0; p < num_priority_levels; ++p )
382  if ( !my_task_stream.empty(p) )
383  return true;
384  return false;
385 }
386 
388  // Check for the presence of enqueued tasks "lost" on some of
389  // priority levels because updating arena priority and switching
390  // arena into "populated" (FULL) state happen non-atomically.
391  // Imposing atomicity would require task::enqueue() to use a lock,
392  // which is unacceptable.
393  if ( has_enqueued_tasks() ) {
394  advertise_new_work<work_enqueued>();
395 #if __TBB_TASK_PRIORITY
396  // update_arena_priority() expects non-zero arena::my_num_workers_requested,
397  // so must be called after advertise_new_work<work_enqueued>()
398  for ( int p = 0; p < num_priority_levels; ++p )
399  if ( !my_task_stream.empty(p) ) {
400  if ( p < my_bottom_priority || p > my_top_priority )
401  my_market->update_arena_priority(*this, p);
402  }
403 #endif
404  }
405 }
406 
408  // TODO: rework it to return at least a hint about where a task was found; better if the task itself.
409  for(;;) {
410  pool_state_t snapshot = my_pool_state;
411  switch( snapshot ) {
412  case SNAPSHOT_EMPTY:
413  return true;
414  case SNAPSHOT_FULL: {
415  // Use unique id for "busy" in order to avoid ABA problems.
416  const pool_state_t busy = pool_state_t(&busy);
417  // Request permission to take snapshot
419  // Got permission. Take the snapshot.
420  // NOTE: This is not a lock, as the state can be set to FULL at
421  // any moment by a thread that spawns/enqueues new task.
422  size_t n = my_limit;
423  // Make local copies of volatile parameters. Their change during
424  // snapshot taking procedure invalidates the attempt, and returns
425  // this thread into the dispatch loop.
426 #if __TBB_TASK_PRIORITY
427  uintptr_t reload_epoch = __TBB_load_with_acquire( my_reload_epoch );
428  intptr_t top_priority = my_top_priority;
429  // Inspect primary task pools first
430 #endif /* __TBB_TASK_PRIORITY */
431  size_t k;
432  for( k=0; k<n; ++k ) {
433  if( my_slots[k].task_pool != EmptyTaskPool &&
435  {
436  // k-th primary task pool is nonempty and does contain tasks.
437  break;
438  }
439  if( my_pool_state!=busy )
440  return false; // the work was published
441  }
442  __TBB_ASSERT( k <= n, NULL );
443  bool work_absent = k == n;
444 #if __TBB_PREVIEW_CRITICAL_TASKS
445  bool no_critical_tasks = my_critical_task_stream.empty(0);
446  work_absent &= no_critical_tasks;
447 #endif
448 #if __TBB_TASK_PRIORITY
449  // Variable tasks_present indicates presence of tasks at any priority
450  // level, while work_absent refers only to the current priority.
451  bool tasks_present = !work_absent || my_orphaned_tasks;
452  bool dequeuing_possible = false;
453  if ( work_absent ) {
454  // Check for the possibility that recent priority changes
455  // brought some tasks to the current priority level
456 
457  uintptr_t abandonment_epoch = my_abandonment_epoch;
458  // Master thread's scheduler needs special handling as it
459  // may be destroyed at any moment (workers' schedulers are
460  // guaranteed to be alive while at least one thread is in arena).
461  // The lock below excludes concurrency with task group state change
462  // propagation and guarantees lifetime of the master thread.
463  the_context_state_propagation_mutex.lock();
464  work_absent = !may_have_tasks( my_slots[0].my_scheduler, tasks_present, dequeuing_possible );
465  the_context_state_propagation_mutex.unlock();
466  // The following loop is subject to data races. While k-th slot's
467  // scheduler is being examined, corresponding worker can either
468  // leave to RML or migrate to another arena.
469  // But the races are not prevented because all of them are benign.
470  // First, the code relies on the fact that worker thread's scheduler
471  // object persists until the whole library is deinitialized.
472  // Second, in the worst case the races can only cause another
473  // round of stealing attempts to be undertaken. Introducing complex
474  // synchronization into this coldest part of the scheduler's control
475  // flow does not seem to make sense because it both is unlikely to
476  // ever have any observable performance effect, and will require
477  // additional synchronization code on the hotter paths.
478  for( k = 1; work_absent && k < n; ++k ) {
479  if( my_pool_state!=busy )
480  return false; // the work was published
481  work_absent = !may_have_tasks( my_slots[k].my_scheduler, tasks_present, dequeuing_possible );
482  }
483  // Preclude premature switching arena off because of a race in the previous loop.
484  work_absent = work_absent
485  && !__TBB_load_with_acquire(my_orphaned_tasks)
486  && abandonment_epoch == my_abandonment_epoch;
487  }
488 #endif /* __TBB_TASK_PRIORITY */
489  // Test and test-and-set.
490  if( my_pool_state==busy ) {
491 #if __TBB_TASK_PRIORITY
492  bool no_fifo_tasks = my_task_stream.empty(top_priority);
493  work_absent = work_absent && (!dequeuing_possible || no_fifo_tasks)
494  && top_priority == my_top_priority && reload_epoch == my_reload_epoch;
495 #else
496  bool no_fifo_tasks = my_task_stream.empty(0);
497  work_absent = work_absent && no_fifo_tasks;
498 #endif /* __TBB_TASK_PRIORITY */
499  if( work_absent ) {
500 #if __TBB_TASK_PRIORITY
501  if ( top_priority > my_bottom_priority ) {
502  if ( my_market->lower_arena_priority(*this, top_priority - 1, reload_epoch)
503  && !my_task_stream.empty(top_priority) )
504  {
505  atomic_update( my_skipped_fifo_priority, top_priority, std::less<intptr_t>());
506  }
507  }
508  else if ( !tasks_present && !my_orphaned_tasks && no_fifo_tasks ) {
509 #endif /* __TBB_TASK_PRIORITY */
510  // save current demand value before setting SNAPSHOT_EMPTY,
511  // to avoid race with advertise_new_work.
512  int current_demand = (int)my_max_num_workers;
513  if( my_pool_state.compare_and_swap( SNAPSHOT_EMPTY, busy )==busy ) {
514 #if __TBB_ENQUEUE_ENFORCED_CONCURRENCY
515  if( my_concurrency_mode==cm_enforced_global ) {
516  // adjust_demand() called inside, if needed
517  my_market->mandatory_concurrency_disable( this );
518  } else
519 #endif /* __TBB_ENQUEUE_ENFORCED_CONCURRENCY */
520  {
521  // This thread transitioned pool to empty state, and thus is
522  // responsible for telling the market that there is no work to do.
523  my_market->adjust_demand( *this, -current_demand );
524  }
526  return true;
527  }
528  return false;
529 #if __TBB_TASK_PRIORITY
530  }
531 #endif /* __TBB_TASK_PRIORITY */
532  }
533  // Undo previous transition SNAPSHOT_FULL-->busy, unless another thread undid it.
535  }
536  }
537  return false;
538  }
539  default:
540  // Another thread is taking a snapshot.
541  return false;
542  }
543  }
544 }
545 
546 #if __TBB_COUNT_TASK_NODES
547 intptr_t arena::workers_task_node_count() {
548  intptr_t result = 0;
549  for( unsigned i = 1; i < my_num_slots; ++i ) {
551  if( s )
552  result += s->my_task_node_count;
553  }
554  return result;
555 }
556 #endif /* __TBB_COUNT_TASK_NODES */
557 
558 void arena::enqueue_task( task& t, intptr_t prio, FastRandom &random )
559 {
560 #if __TBB_RECYCLE_TO_ENQUEUE
561  __TBB_ASSERT( t.state()==task::allocated || t.state()==task::to_enqueue, "attempt to enqueue task with inappropriate state" );
562 #else
563  __TBB_ASSERT( t.state()==task::allocated, "attempt to enqueue task that is not in 'allocated' state" );
564 #endif
565  t.prefix().state = task::ready;
566  t.prefix().extra_state |= es_task_enqueued; // enqueued task marker
567 
568 #if TBB_USE_ASSERT
569  if( task* parent = t.parent() ) {
570  internal::reference_count ref_count = parent->prefix().ref_count;
571  __TBB_ASSERT( ref_count!=0, "attempt to enqueue task whose parent has a ref_count==0 (forgot to set_ref_count?)" );
572  __TBB_ASSERT( ref_count>0, "attempt to enqueue task whose parent has a ref_count<0" );
573  parent->prefix().extra_state |= es_ref_count_active;
574  }
575  __TBB_ASSERT(t.prefix().affinity==affinity_id(0), "affinity is ignored for enqueued tasks");
576 #endif /* TBB_USE_ASSERT */
577 #if __TBB_PREVIEW_CRITICAL_TASKS
578  if( prio == internal::priority_critical || internal::is_critical( t ) ) {
579  // TODO: consider using of 'scheduler::handled_as_critical'
581 #if __TBB_TASK_ISOLATION
583  __TBB_ASSERT( s, "Scheduler must be initialized at this moment" );
584  // propagate isolation level to critical task
585  t.prefix().isolation = s->my_innermost_running_task->prefix().isolation;
586 #endif
587  ITT_NOTIFY(sync_releasing, &my_critical_task_stream);
588  if( !s || !s->my_arena_slot ) {
589  // Either scheduler is not initialized or it is not attached to the arena, use random
590  // lane for the task.
591  my_critical_task_stream.push( &t, 0, internal::random_lane_selector(random) );
592  } else {
593  unsigned& lane = s->my_arena_slot->hint_for_critical;
594  my_critical_task_stream.push( &t, 0, tbb::internal::subsequent_lane_selector(lane) );
595  }
596  advertise_new_work<work_spawned>();
597  return;
598  }
599 #endif /* __TBB_PREVIEW_CRITICAL_TASKS */
600 
602 #if __TBB_TASK_PRIORITY
603  intptr_t p = prio ? normalize_priority(priority_t(prio)) : normalized_normal_priority;
604  assert_priority_valid(p);
605 #if __TBB_PREVIEW_CRITICAL_TASKS && __TBB_CPF_BUILD
606  my_task_stream.push( &t, p, internal::random_lane_selector(random) );
607 #else
608  my_task_stream.push( &t, p, random );
609 #endif
610  if ( p != my_top_priority )
611  my_market->update_arena_priority( *this, p );
612 #else /* !__TBB_TASK_PRIORITY */
613  __TBB_ASSERT_EX(prio == 0, "the library is not configured to respect the task priority");
614 #if __TBB_PREVIEW_CRITICAL_TASKS && __TBB_CPF_BUILD
615  my_task_stream.push( &t, 0, internal::random_lane_selector(random) );
616 #else
617  my_task_stream.push( &t, 0, random );
618 #endif
619 #endif /* !__TBB_TASK_PRIORITY */
620  advertise_new_work<work_enqueued>();
621 #if __TBB_TASK_PRIORITY
622  if ( p != my_top_priority )
623  my_market->update_arena_priority( *this, p );
624 #endif /* __TBB_TASK_PRIORITY */
625 }
626 
628 public:
629  nested_arena_context(generic_scheduler *s, arena* a, size_t slot_index, bool type, bool same)
630  : my_scheduler(*s), my_orig_ctx(NULL), same_arena(same) {
631  if (same_arena) {
635  } else {
636  my_orig_state = *s;
638  s->nested_arena_entry(a, slot_index);
639  }
640  }
642 #if __TBB_TASK_GROUP_CONTEXT
643  my_scheduler.my_dummy_task->prefix().context = my_orig_ctx; // restore context of dummy task
644 #endif
645  if (same_arena) {
648  } else {
650  static_cast<scheduler_state&>(my_scheduler) = my_orig_state; // restore arena settings
651 #if __TBB_TASK_PRIORITY
652  my_scheduler.my_local_reload_epoch = *my_orig_state.my_ref_reload_epoch;
653 #endif
655  }
656  }
657 
658 private:
662  const bool same_arena;
663 
668 #if __TBB_PREVIEW_CRITICAL_TASKS
669  my_scheduler.my_properties.has_taken_critical_task = false;
670 #endif
671 #if __TBB_TASK_GROUP_CONTEXT
672  // Save dummy's context and replace it by arena's context
674  my_scheduler.my_dummy_task->prefix().context = a->my_default_ctx;
675 #endif
676  }
677 };
678 
679 void generic_scheduler::nested_arena_entry(arena* a, size_t slot_index) {
680  __TBB_ASSERT( is_alive(a->my_guard), NULL );
681  __TBB_ASSERT( a!=my_arena, NULL);
682 
683  // overwrite arena settings
684 #if __TBB_TASK_PRIORITY
685  if ( my_offloaded_tasks )
686  my_arena->orphan_offloaded_tasks( *this );
687  my_offloaded_tasks = NULL;
688 #endif /* __TBB_TASK_PRIORITY */
689  attach_arena( a, slot_index, /*is_master*/true );
690  __TBB_ASSERT( my_arena == a, NULL );
692  // TODO? ITT_NOTIFY(sync_acquired, a->my_slots + index);
693  // TODO: it requires market to have P workers (not P-1)
694  // TODO: a preempted worker should be excluded from assignment to other arenas e.g. my_slack--
695  if( !is_worker() && slot_index >= my_arena->my_num_reserved_slots )
697 #if __TBB_ARENA_OBSERVER
698  my_last_local_observer = 0; // TODO: try optimize number of calls
699  my_arena->my_observers.notify_entry_observers( my_last_local_observer, /*worker=*/false );
700 #endif
701 }
702 
704 #if __TBB_ARENA_OBSERVER
705  my_arena->my_observers.notify_exit_observers( my_last_local_observer, /*worker=*/false );
706 #endif /* __TBB_ARENA_OBSERVER */
707 #if __TBB_TASK_PRIORITY
708  if ( my_offloaded_tasks )
709  my_arena->orphan_offloaded_tasks( *this );
710 #endif
713  // Free the master slot.
714  __TBB_ASSERT(my_arena->my_slots[my_arena_index].my_scheduler, "A slot is already empty");
716  my_arena->my_exit_monitors.notify_one(); // do not relax!
717 }
718 
720  my_dummy_task->prefix().ref_count++; // prevents exit from local_wait_for_all when local work is done enforcing the stealing
723  my_dummy_task->prefix().ref_count--;
724 }
725 
726 } // namespace internal
727 } // namespace tbb
728 
729 #include "scheduler_utility.h"
730 #include "tbb/task_arena.h" // task_arena_base
731 
732 namespace tbb {
733 namespace interface7 {
734 namespace internal {
735 
738  if( my_max_concurrency < 1 )
740  __TBB_ASSERT( my_master_slots <= (unsigned)my_max_concurrency, "Number of slots reserved for master should not exceed arena concurrency");
742  // add an internal market reference; a public reference was added in create_arena
743  market &m = market::global_market( /*is_public=*/false );
744  // allocate default context for task_arena
745 #if __TBB_TASK_GROUP_CONTEXT
746  new_arena->my_default_ctx = new ( NFS_Allocate(1, sizeof(task_group_context), NULL) )
748 #if __TBB_FP_CONTEXT
749  new_arena->my_default_ctx->capture_fp_settings();
750 #endif
751 #endif /* __TBB_TASK_GROUP_CONTEXT */
752  // threads might race to initialize the arena
753  if(as_atomic(my_arena).compare_and_swap(new_arena, NULL) != NULL) {
754  __TBB_ASSERT(my_arena, NULL); // another thread won the race
755  // release public market reference
756  m.release( /*is_public=*/true, /*blocking_terminate=*/false );
757  new_arena->on_thread_leaving<arena::ref_external>(); // destroy unneeded arena
758 #if __TBB_TASK_GROUP_CONTEXT
760  } else {
761  new_arena->my_default_ctx->my_version_and_traits |= my_version_and_traits & exact_exception_flag;
762  as_atomic(my_context) = new_arena->my_default_ctx;
763 #endif
764  }
765  // TODO: should it trigger automatic initialization of this thread?
767 }
768 
770  if( my_arena ) {// task_arena was initialized
771  my_arena->my_market->release( /*is_public=*/true, /*blocking_terminate=*/false );
772  my_arena->on_thread_leaving<arena::ref_external>();
773  my_arena = 0;
774 #if __TBB_TASK_GROUP_CONTEXT
775  my_context = 0;
776 #endif
777  }
778 }
779 
781  __TBB_ASSERT(!my_arena, NULL);
783  if( s && s->my_arena ) {
784  // There is an active arena to attach to.
785  // It's still used by s, so won't be destroyed right away.
786  my_arena = s->my_arena;
787  __TBB_ASSERT( my_arena->my_references > 0, NULL );
788  my_arena->my_references += arena::ref_external;
789 #if __TBB_TASK_GROUP_CONTEXT
790  my_context = my_arena->my_default_ctx;
792 #endif
793  my_master_slots = my_arena->my_num_reserved_slots;
794  my_max_concurrency = my_master_slots + my_arena->my_max_num_workers;
796  // increases market's ref count for task_arena
797  market::global_market( /*is_public=*/true );
798  }
799 }
800 
801 void task_arena_base::internal_enqueue( task& t, intptr_t prio ) const {
802  __TBB_ASSERT(my_arena, NULL);
804  __TBB_ASSERT(s, "Scheduler is not initialized"); // we allocated a task so can expect the scheduler
805 #if __TBB_TASK_GROUP_CONTEXT
806  __TBB_ASSERT(my_arena->my_default_ctx == t.prefix().context, NULL);
807  __TBB_ASSERT(!my_arena->my_default_ctx->is_group_execution_cancelled(), // TODO: any better idea?
808  "The task will not be executed because default task_group_context of task_arena is cancelled. Has previously enqueued task thrown an exception?");
809 #endif
810  my_arena->enqueue_task( t, prio, s->my_random );
811 }
812 
813 class delegated_task : public task {
814  internal::delegate_base & my_delegate;
819  __TBB_ASSERT(s.outermost_level(), "expected to be enqueued and received on the outermost level");
820  struct outermost_context : internal::no_copy {
821  delegated_task * t;
823  task * orig_dummy;
824  task_group_context * orig_ctx;
825  scheduler_properties orig_props;
826  outermost_context(delegated_task *_t, generic_scheduler &_s)
827  : t(_t), s(_s), orig_dummy(s.my_dummy_task), orig_props(s.my_properties) {
828  __TBB_ASSERT(s.my_innermost_running_task == t, NULL);
829 #if __TBB_TASK_GROUP_CONTEXT
830  orig_ctx = t->prefix().context;
831  t->prefix().context = s.my_arena->my_default_ctx;
832 #endif
833  // Mimics outermost master
834  s.my_dummy_task = t;
835  s.my_properties.type = scheduler_properties::master;
836  }
837  ~outermost_context() {
838 #if __TBB_TASK_GROUP_CONTEXT
839  // Restore context for sake of registering potential exception
840  t->prefix().context = orig_ctx;
841 #endif
842  s.my_properties = orig_props;
843  s.my_dummy_task = orig_dummy;
844  }
845  } scope(this, s);
846  my_delegate();
847  return NULL;
848  }
850  // potential exception was already registered. It must happen before the notification
851  __TBB_ASSERT(my_root->ref_count()==2, NULL);
852  __TBB_store_with_release(my_root->prefix().ref_count, 1); // must precede the wakeup
853  my_monitor.notify(*this); // do not relax, it needs a fence!
854  }
855 public:
856  delegated_task( internal::delegate_base & d, concurrent_monitor & s, task * t )
857  : my_delegate(d), my_monitor(s), my_root(t) {}
858  // predicate for concurrent_monitor notification
859  bool operator()(uintptr_t ctx) const { return (void*)ctx == (void*)&my_delegate; }
860 };
861 
862 void task_arena_base::internal_execute(internal::delegate_base& d) const {
863  __TBB_ASSERT(my_arena, NULL);
865  __TBB_ASSERT(s, "Scheduler is not initialized");
866 
867  bool same_arena = s->my_arena == my_arena;
868  size_t index1 = s->my_arena_index;
869  if (!same_arena) {
870  index1 = my_arena->occupy_free_slot</* as_worker*/false>(*s);
871  if (index1 == arena::out_of_arena) {
872 
873 #if __TBB_USE_OPTIONAL_RTTI
874  // Workaround for the bug inside graph. If the thread can not occupy arena slot during task_arena::execute()
875  // and all aggregator operations depend on this task completion (all other threads are inside arena already)
876  // deadlock appears, because enqueued task will never enter arena.
877  // Workaround: check if the task came from graph via RTTI (casting to graph::spawn_functor)
878  // and enqueue this task with non-blocking internal_enqueue method.
879  // TODO: have to change behaviour later in next GOLD release (maybe to add new library entry point - try_execute)
881  internal::delegated_function< graph_funct, void >* deleg_funct =
882  dynamic_cast< internal::delegated_function< graph_funct, void>* >(&d);
883 
884  if (deleg_funct) {
886  internal::function_task< internal::strip< graph_funct >::type >
887  (internal::forward< graph_funct >(deleg_funct->my_func)), 0);
888  return;
889  } else {
890 #endif /* __TBB_USE_OPTIONAL_RTTI */
892 #if __TBB_TASK_GROUP_CONTEXT
894 #if __TBB_FP_CONTEXT
895  exec_context.copy_fp_settings(*my_context);
896 #endif
897 #endif
898  auto_empty_task root(__TBB_CONTEXT_ARG(s, &exec_context));
899  root.prefix().ref_count = 2;
900  my_arena->enqueue_task(*new(task::allocate_root(__TBB_CONTEXT_ARG1(exec_context)))
901  delegated_task(d, my_arena->my_exit_monitors, &root),
902  0, s->my_random); // TODO: priority?
903  size_t index2 = arena::out_of_arena;
904  do {
905  my_arena->my_exit_monitors.prepare_wait(waiter, (uintptr_t)&d);
906  if (__TBB_load_with_acquire(root.prefix().ref_count) < 2) {
907  my_arena->my_exit_monitors.cancel_wait(waiter);
908  break;
909  }
910  index2 = my_arena->occupy_free_slot</*as_worker*/false>(*s);
911  if (index2 != arena::out_of_arena) {
912  my_arena->my_exit_monitors.cancel_wait(waiter);
914  s->local_wait_for_all(root, NULL);
915 #if TBB_USE_EXCEPTIONS
916  __TBB_ASSERT(!exec_context.my_exception, NULL); // exception can be thrown above, not deferred
917 #endif
918  __TBB_ASSERT(root.prefix().ref_count == 0, NULL);
919  break;
920  }
921  my_arena->my_exit_monitors.commit_wait(waiter);
922  } while (__TBB_load_with_acquire(root.prefix().ref_count) == 2);
923  if (index2 == arena::out_of_arena) {
924  // notify a waiting thread even if this thread did not enter arena,
925  // in case it was woken by a leaving thread but did not need to enter
926  my_arena->my_exit_monitors.notify_one(); // do not relax!
927  }
928 #if TBB_USE_EXCEPTIONS
929  // process possible exception
931  TbbRethrowException(pe);
932 #endif
933  return;
934 #if __TBB_USE_OPTIONAL_RTTI
935  } // if task came from graph
936 #endif
937  } // if (index1 == arena::out_of_arena)
938  } // if (!same_arena)
939 
940  context_guard_helper</*report_tasks=*/false> context_guard;
941  context_guard.set_ctx(__TBB_CONTEXT_ARG1(my_context));
942 #if TBB_USE_EXCEPTIONS
943  try {
944 #endif
945  //TODO: replace dummy tasks for workers as well to avoid using of the_dummy_context
947  d();
948 #if TBB_USE_EXCEPTIONS
949  }
950  catch (...) {
951  context_guard.restore_default(); // TODO: is it needed on Windows?
953  else {
956  exception_container.register_pending_exception();
957  __TBB_ASSERT(exception_container.my_exception, NULL);
958  TbbRethrowException(exception_container.my_exception);
959  }
960  }
961 #endif
962 }
963 
964 // this wait task is a temporary approach to wait for arena emptiness for masters without slots
965 // TODO: it will be rather reworked for one source of notification from is_out_of_work
966 class wait_task : public task {
970  __TBB_ASSERT( s, NULL );
971  __TBB_ASSERT( s->outermost_level(), "The enqueued task can be processed only on outermost level" );
972  if ( s->is_worker() ) {
973  __TBB_ASSERT( s->my_innermost_running_task == this, NULL );
974  // Mimic worker on outermost level to run remaining tasks
975  s->my_innermost_running_task = s->my_dummy_task;
976  s->local_wait_for_all( *s->my_dummy_task, NULL );
977  s->my_innermost_running_task = this;
978  } else s->my_arena->is_out_of_work(); // avoids starvation of internal_wait: issuing this task makes arena full
979  my_signal.V();
980  return NULL;
981  }
982 public:
983  wait_task ( binary_semaphore & sema ) : my_signal(sema) {}
984 };
985 
987  __TBB_ASSERT(my_arena, NULL);
989  __TBB_ASSERT(s, "Scheduler is not initialized");
990  __TBB_ASSERT(s->my_arena != my_arena || s->my_arena_index == 0, "task_arena::wait_until_empty() is not supported within a worker context" );
991  if( s->my_arena == my_arena ) {
992  //unsupported, but try do something for outermost master
993  __TBB_ASSERT(s->master_outermost_level(), "unsupported");
994  if( !s->my_arena_index )
995  while( my_arena->num_workers_active() )
996  s->wait_until_empty();
997  } else for(;;) {
998  while( my_arena->my_pool_state != arena::SNAPSHOT_EMPTY ) {
999  if( !__TBB_load_with_acquire(my_arena->my_slots[0].my_scheduler) // TODO TEMP: one master, make more masters
1000  && as_atomic(my_arena->my_slots[0].my_scheduler).compare_and_swap(s, NULL) == NULL ) {
1002  s->wait_until_empty();
1003  } else {
1004  binary_semaphore waiter; // TODO: replace by a single event notification from is_out_of_work
1005  internal_enqueue( *new( task::allocate_root(__TBB_CONTEXT_ARG1(*my_context)) ) wait_task(waiter), 0 ); // TODO: priority?
1006  waiter.P(); // TODO: concurrent_monitor
1007  }
1008  }
1009  if( !my_arena->num_workers_active() && !my_arena->my_slots[0].my_scheduler) // no activity
1010  break; // spin until workers active but avoid spinning in a worker
1011  __TBB_Yield(); // wait until workers and master leave
1012  }
1013 }
1014 
1017  return s? int(s->my_arena_index) : -1;
1018 }
1019 
1020 #if __TBB_TASK_ISOLATION
1021 class isolation_guard : tbb::internal::no_copy {
1022  isolation_tag &guarded;
1023  isolation_tag previous_value;
1024 public:
1025  isolation_guard( isolation_tag &isolation ) : guarded( isolation ), previous_value( isolation ) {}
1026  ~isolation_guard() {
1027  guarded = previous_value;
1028  }
1029 };
1030 
1031 void isolate_within_arena( delegate_base& d, intptr_t reserved ) {
1032  __TBB_ASSERT_EX( reserved == 0, NULL );
1033  // TODO: Decide what to do if the scheduler is not initialized. Is there a use case for it?
1034  generic_scheduler* s = governor::local_scheduler_weak();
1035  __TBB_ASSERT( s, "this_task_arena::isolate() needs an initialized scheduler" );
1036  // Theoretically, we can keep the current isolation in the scheduler; however, it makes sense to store it in innermost
1037  // running task because it can in principle be queried via task::self().
1038  isolation_tag& current_isolation = s->my_innermost_running_task->prefix().isolation;
1039  // We temporarily change the isolation tag of the currently running task. It will be restored in the destructor of the guard.
1040  isolation_guard guard( current_isolation );
1041  current_isolation = reinterpret_cast<isolation_tag>(&d);
1042  d();
1043 }
1044 #endif /* __TBB_TASK_ISOLATION */
1045 
1047  arena* a = NULL;
1048  if( ta ) // for special cases of ta->max_concurrency()
1049  a = ta->my_arena;
1051  a = s->my_arena; // the current arena if any
1052 
1053  if( a ) { // Get parameters from the arena
1054  __TBB_ASSERT( !ta || ta->my_max_concurrency==1, NULL );
1056  } else {
1057  __TBB_ASSERT( !ta || ta->my_max_concurrency==automatic, NULL );
1059  }
1060 }
1061 } // tbb::interfaceX::internal
1062 } // tbb::interfaceX
1063 } // tbb
task * execute() __TBB_override
Should be overridden by derived classes.
Definition: arena.cpp:817
intptr_t drain()
Destroys all remaining tasks in every lane. Returns the number of destroyed tasks.
Definition: task_stream.h:149
void *__TBB_EXPORTED_FUNC NFS_Allocate(size_t n_element, size_t element_size, void *hint)
Allocate memory on cache/sector line boundary.
void free_arena()
Completes arena shutdown, destructs and deallocates it.
Definition: arena.cpp:253
#define __TBB_override
Definition: tbb_stddef.h:244
uintptr_t my_arenas_aba_epoch
ABA prevention marker to assign to newly created arenas.
Definition: market.h:147
void __TBB_EXPORTED_METHOD register_pending_exception()
Records the pending exception, and cancels the task group.
static int unsigned num_arena_slots(unsigned num_slots)
Definition: arena.h:199
static int allocation_size(unsigned num_slots)
Definition: arena.h:203
__TBB_atomic reference_count ref_count
Reference count used for synchronization.
Definition: task.h:252
#define __TBB_CONTEXT_ARG(arg1, context)
intptr_t drain()
Drain the mailbox.
Definition: mailbox.h:172
bool operator()(uintptr_t ctx) const
Definition: arena.cpp:859
unsigned my_num_workers_allotted
The number of workers that have been marked out by the resource manager to service the arena.
Definition: arena.h:55
nested_arena_context(generic_scheduler *s, arena *a, size_t slot_index, bool type, bool same)
Definition: arena.cpp:629
void __TBB_EXPORTED_METHOD internal_initialize()
Definition: arena.cpp:736
void set_ctx(__TBB_CONTEXT_ARG1(task_group_context *))
Definition: scheduler.h:811
task_group_context * my_context
default context of the arena
Definition: task_arena.h:110
void initialize(unsigned n_lanes)
Definition: task_stream.h:87
#define EmptyTaskPool
Definition: scheduler.h:46
unsigned short affinity_id
An id as used for specifying affinity.
Definition: task.h:124
#define __TBB_ENQUEUE_ENFORCED_CONCURRENCY
Definition: tbb_config.h:588
size_t __TBB_EXPORTED_FUNC NFS_GetLineSize()
Cache/sector line size.
T __TBB_load_with_acquire(const volatile T &location)
Definition: tbb_machine.h:713
void attach_arena(arena *, size_t index, bool is_master)
Definition: arena.cpp:40
market * my_market
The market that owns this arena.
Definition: arena.h:135
unsigned my_num_reserved_slots
The number of reserved slots (can be occupied only by masters).
Definition: arena.h:156
Set if ref_count might be changed by another thread. Used for debugging.
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 ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain ITT_FORMAT p const __itt_domain __itt_string_handle unsigned long long ITT_FORMAT lu const __itt_domain __itt_id __itt_string_handle __itt_metadata_type size_t void ITT_FORMAT p const __itt_domain __itt_id __itt_string_handle const wchar_t size_t ITT_FORMAT lu const __itt_domain __itt_id head
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:169
const isolation_tag no_isolation
Definition: task.h:129
void adjust_demand(arena &, int delta)
Request that arena's need in workers should be adjusted.
Definition: market.cpp:590
size_t occupy_free_slot(generic_scheduler &s)
Tries to occupy a slot in the arena. On success, returns the slot index; if no slot is available,...
Definition: arena.cpp:90
static const size_t out_of_arena
Definition: arena.h:292
task object is freshly allocated or recycled.
Definition: task.h:620
cpu_ctl_env my_cpu_ctl_env
FPU control settings of arena's master thread captured at the moment of arena instantiation.
Definition: arena.h:142
#define ITT_SYNC_CREATE(obj, type, name)
Definition: itt_notify.h:123
static market & global_market(bool is_public, unsigned max_num_workers=0, size_t stack_size=0)
Factory method creating new market object.
Definition: market.cpp:100
static const pool_state_t SNAPSHOT_FULL
At least one task has been offered for stealing since the last snapshot started.
Definition: arena.h:224
void on_thread_leaving()
Notification that worker or master leaves its arena.
Definition: arena.h:304
Used to form groups of tasks.
Definition: task.h:335
A fast random number generator.
Definition: tbb_misc.h:132
Bit-field representing properties of a sheduler.
Definition: scheduler.h:50
wait_task(binary_semaphore &sema)
Definition: arena.cpp:983
static unsigned default_num_threads()
Definition: governor.h:85
internal::delegate_base & my_delegate
Definition: arena.cpp:814
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
exception_container_type * my_exception
Pointer to the container storing exception being propagated across this task group.
Definition: task.h:426
task * execute() __TBB_override
Should be overridden by derived classes.
Definition: arena.cpp:968
void mimic_outermost_level(arena *a, bool type)
Definition: arena.cpp:664
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 ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain ITT_FORMAT p const __itt_domain __itt_string_handle unsigned long long ITT_FORMAT lu const __itt_domain __itt_id __itt_string_handle __itt_metadata_type type
bool is_worker() const
True if running on a worker thread, false otherwise.
Definition: scheduler.h:595
Base class for types that should not be copied or assigned.
Definition: tbb_stddef.h:335
intptr_t my_version_and_traits
Special settings.
Definition: task_arena.h:120
static generic_scheduler * local_scheduler_if_initialized()
Definition: governor.h:136
delegated_task(internal::delegate_base &d, concurrent_monitor &s, task *t)
Definition: arena.cpp:856
int my_max_concurrency
Concurrency level for deferred initialization.
Definition: task_arena.h:114
#define __TBB_Yield()
Definition: ibm_aix51.h:48
static arena * create_arena(int num_slots, int num_reserved_slots, size_t stack_size)
Creates an arena object.
Definition: market.cpp:300
void __TBB_EXPORTED_METHOD internal_terminate()
Definition: arena.cpp:769
void enqueue_task(task &, intptr_t, FastRandom &)
enqueue a task into starvation-resistance queue
Definition: arena.cpp:558
void notify_one()
Notify one thread about the event.
Base class for user-defined tasks.
Definition: task.h:592
static bool occupy_slot(generic_scheduler *&slot, generic_scheduler &s)
Definition: arena.cpp:71
Work stealing task scheduler.
Definition: scheduler.h:124
task * my_innermost_running_task
Innermost task whose task::execute() is running. A dummy task on the outermost level.
Definition: scheduler.h:81
static void assume_scheduler(generic_scheduler *s)
Temporarily set TLS slot to the given scheduler.
Definition: governor.cpp:120
#define __TBB_ASSERT_EX(predicate, comment)
"Extended" version is useful to suppress warnings if a variable is only used with an assert
Definition: tbb_stddef.h:171
static const unsigned ref_external
Reference increment values for externals and workers.
Definition: arena.h:230
intptr_t isolation_tag
A tag for task isolation.
Definition: task.h:128
unsigned my_num_slots
The number of slots in the arena.
Definition: arena.h:153
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 ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain ITT_FORMAT p const __itt_domain __itt_string_handle unsigned long long ITT_FORMAT lu const __itt_domain __itt_id __itt_string_handle __itt_metadata_type size_t void ITT_FORMAT p const __itt_domain __itt_id __itt_string_handle const wchar_t size_t ITT_FORMAT lu const __itt_domain __itt_id __itt_relation __itt_id ITT_FORMAT p const wchar_t int ITT_FORMAT __itt_group_mark d __itt_event ITT_FORMAT __itt_group_mark d void const wchar_t const wchar_t int ITT_FORMAT __itt_group_sync __itt_group_fsync x void const wchar_t int const wchar_t int int ITT_FORMAT __itt_group_sync __itt_group_fsync x void ITT_FORMAT __itt_group_sync __itt_group_fsync p void ITT_FORMAT __itt_group_sync __itt_group_fsync p void size_t ITT_FORMAT lu no args __itt_obj_prop_t __itt_obj_state_t ITT_FORMAT d const char ITT_FORMAT s __itt_frame ITT_FORMAT p const char const char ITT_FORMAT s __itt_counter ITT_FORMAT p __itt_counter unsigned long long ITT_FORMAT lu const wchar_t ITT_FORMAT S __itt_mark_type const wchar_t ITT_FORMAT S __itt_mark_type const char ITT_FORMAT s __itt_mark_type ITT_FORMAT d __itt_caller ITT_FORMAT p __itt_caller ITT_FORMAT p no args const __itt_domain __itt_clock_domain unsigned long long __itt_id ITT_FORMAT lu const __itt_domain __itt_clock_domain unsigned long long __itt_id __itt_id void ITT_FORMAT p const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain __itt_id ITT_FORMAT lu const __itt_domain __itt_clock_domain unsigned long long __itt_id __itt_string_handle __itt_scope scope
arena(market &, unsigned max_num_workers, unsigned num_reserved_slots)
Constructor.
Definition: arena.cpp:190
generic_scheduler * my_scheduler
Scheduler of the thread attached to the slot.
market * my_market
The market I am in.
Definition: scheduler.h:159
void const char const char int ITT_FORMAT __itt_group_sync p
arena_slot my_slots[1]
Definition: arena.h:300
binary_semaphore for concurrent monitor
Definition: semaphore.h:226
size_t my_arena_index
Index of the arena slot the scheduler occupies now, or occupied last time.
Definition: scheduler.h:72
bool is_critical(task &t)
Definition: task.h:953
void __TBB_EXPORTED_METHOD internal_wait() const
Definition: arena.cpp:986
static const int automatic
Typedef for number of threads that is automatic.
Definition: task_arena.h:150
#define poison_value(g)
Smart holder for the empty task class with automatic destruction.
arena_slot * my_arena_slot
Pointer to the slot in the arena we own at the moment.
Definition: scheduler.h:75
#define __TBB_ISOLATION_ARG(arg1, isolation)
task * parent() const
task on whose behalf this task is working, or NULL if this is a root.
Definition: task.h:830
size_t occupy_free_slot_in_range(generic_scheduler &s, size_t lower, size_t upper)
Tries to occupy a slot in the specified range.
Definition: arena.cpp:75
priority_t
Definition: task.h:295
T1 atomic_update(tbb::atomic< T1 > &dst, T2 newValue, Pred compare)
Atomically replaces value of dst with newValue if they satisfy condition of compare predicate.
Definition: tbb_misc.h:183
tbb::atomic< uintptr_t > my_pool_state
Current task pool state and estimate of available tasks amount.
Definition: arena.h:103
bool empty(int level)
Checks existence of a task.
Definition: task_stream.h:142
atomic< unsigned > my_references
Reference counter for the arena.
Definition: arena.h:61
bool is_out_of_work()
Check if there is job anywhere in arena.
Definition: arena.cpp:407
unsigned my_max_num_workers
The number of workers requested by the master thread owning the arena.
Definition: arena.h:93
static const pool_state_t SNAPSHOT_EMPTY
No tasks to steal since last snapshot was taken.
Definition: arena.h:221
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
static const intptr_t num_priority_levels
void construct()
Construct *this as a mailbox from zeroed memory.
Definition: mailbox.h:162
The graph class.
int my_num_workers_requested
The number of workers that are currently requested from the resource manager.
Definition: arena.h:96
void __TBB_EXPORTED_FUNC isolate_within_arena(delegate_base &d, intptr_t reserved=0)
void spin_wait_while_eq(const volatile T &location, U value)
Spin WHILE the value of the variable is equal to a given value.
Definition: tbb_machine.h:395
#define GATHER_STATISTIC(x)
static void one_time_init()
Definition: governor.cpp:160
bool release(bool is_public, bool blocking_terminate)
Decrements market's refcount and destroys it in the end.
Definition: market.cpp:179
static arena & allocate_arena(market &, unsigned num_slots, unsigned num_reserved_slots)
Allocate an instance of arena.
Definition: arena.cpp:242
bool type
Indicates that a scheduler acts as a master or a worker.
Definition: scheduler.h:54
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 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 ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain ITT_FORMAT p const __itt_domain __itt_string_handle unsigned long long ITT_FORMAT lu const __itt_domain __itt_id __itt_string_handle __itt_metadata_type size_t void ITT_FORMAT p const __itt_domain __itt_id __itt_string_handle const wchar_t size_t ITT_FORMAT lu const __itt_domain __itt_id __itt_relation __itt_id tail
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 push(task *source, int level, FastRandom &random)
Push a task into a lane.
Definition: task_stream.h:105
bool has_enqueued_tasks()
Check for the presence of enqueued tasks at all priority levels.
Definition: arena.cpp:379
internal::tbb_exception_ptr exception_container_type
Definition: task.h:344
task is in ready pool, or is going to be put there, or was just taken off.
Definition: task.h:618
void restore_priority_if_need()
If enqueued tasks found, restore arena priority and task presence status.
Definition: arena.cpp:387
bool outermost
Indicates that a scheduler is on outermost level.
Definition: scheduler.h:57
scheduler_properties my_properties
Definition: scheduler.h:95
atomic< unsigned > my_limit
The maximal number of currently busy slots.
Definition: arena.h:69
uintptr_t my_version_and_traits
Version for run-time checks and behavioral traits of the context.
Definition: task.h:423
unsigned my_master_slots
Reserved master slots.
Definition: task_arena.h:117
#define ITT_NOTIFY(name, obj)
Definition: itt_notify.h:120
void attach_mailbox(affinity_id id)
Definition: scheduler.h:589
uintptr_t my_aba_epoch
ABA prevention marker.
Definition: arena.h:138
const size_t NFS_MaxLineSize
Compile-time constant that is upper bound on cache line/sector size.
Definition: tbb_stddef.h:220
void const char const char int ITT_FORMAT __itt_group_sync s
#define __TBB_CONTEXT_ARG1(context)
task * my_dummy_task
Fake root task created by slave threads.
Definition: scheduler.h:173
static generic_scheduler * local_scheduler_weak()
Definition: governor.h:131
void notify(const P &predicate)
Notify waiting threads of the event that satisfies the given predicate.
T __TBB_load_relaxed(const volatile T &location)
Definition: tbb_machine.h:739
generic_scheduler & my_scheduler
Definition: arena.cpp:659
mail_outbox & mailbox(affinity_id id)
Get reference to mailbox corresponding to given affinity_id.
Definition: arena.h:208
static bool is_set(generic_scheduler *s)
Used to check validity of the local scheduler TLS contents.
Definition: governor.cpp:124
concurrent_monitor my_exit_monitors
Waiting object for master threads that cannot join the arena.
Definition: arena.h:171
void __TBB_EXPORTED_FUNC NFS_Free(void *)
Free memory allocated by NFS_Allocate.
static int __TBB_EXPORTED_FUNC internal_current_slot()
Definition: arena.cpp:1015
void copy_fp_settings(const task_group_context &src)
Copies FPU control setting from another context.
void free_task_pool()
Deallocate task pool that was allocated by means of allocate_task_pool.
virtual void local_wait_for_all(task &parent, task *child)=0
value_type compare_and_swap(value_type value, value_type comparand)
Definition: atomic.h:289
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 ITT_FORMAT lu const __itt_domain __itt_id __itt_id __itt_string_handle ITT_FORMAT p const __itt_domain ITT_FORMAT p const __itt_domain __itt_string_handle unsigned long long ITT_FORMAT lu const __itt_domain __itt_id __itt_string_handle __itt_metadata_type size_t void ITT_FORMAT p const __itt_domain __itt_id __itt_string_handle const wchar_t size_t ITT_FORMAT lu const __itt_domain __itt_id __itt_relation __itt_id ITT_FORMAT p const wchar_t int ITT_FORMAT __itt_group_mark d int
task_stream< num_priority_levels > my_task_stream
Task pool for the tasks scheduled via task::enqueue() method.
Definition: arena.h:80
void set_is_idle(bool value)
Indicate whether thread that reads this mailbox is idle.
Definition: mailbox.h:215
internal::arena * my_arena
NULL if not currently initialized.
Definition: task_arena.h:106
state_type state() const
Current execution state.
Definition: task.h:859
static internal::allocate_root_proxy allocate_root()
Returns proxy for overloaded new that allocates a root task.
Definition: task.h:636
void make_critical(task &t)
Definition: task.h:952
intptr_t reference_count
A reference count.
Definition: task.h:121
static int __TBB_EXPORTED_FUNC internal_max_concurrency(const task_arena *)
Definition: arena.cpp:1046
static const int priority_critical
Definition: task.h:291
internal::task_prefix & prefix(internal::version_tag *=NULL) const
Get reference to corresponding task_prefix.
Definition: task.h:941
bool is_idle_state(bool value) const
Indicate whether thread that reads this mailbox is idle.
Definition: mailbox.h:222
Class representing where mail is put.
Definition: mailbox.h:100
task_group_context * my_orig_ctx
Definition: arena.cpp:661
void __TBB_EXPORTED_METHOD internal_execute(delegate_base &) const
Definition: arena.cpp:862
binary_semaphore & my_signal
Definition: arena.cpp:967
unsigned num_workers_active()
The number of workers active in the arena.
Definition: arena.h:237
void __TBB_store_with_release(volatile T &location, V value)
Definition: tbb_machine.h:717
atomic< T > & as_atomic(T &t)
Definition: atomic.h:547
void __TBB_EXPORTED_METHOD internal_attach()
Definition: arena.cpp:780
void process(generic_scheduler &)
Registers the worker with the arena and enters TBB scheduler dispatch loop.
Definition: arena.cpp:106
void __TBB_EXPORTED_METHOD internal_enqueue(task &, intptr_t) const
Definition: arena.cpp:801
unsigned hint_for_pop
Hint provided for operations with the container of starvation-resistant tasks.
uintptr_t pool_state_t
Definition: arena.h:218
void nested_arena_entry(arena *, size_t)
Definition: arena.cpp:679
int ref_count() const
The internal reference count.
Definition: task.h:862
arena * my_arena
The arena that I own (if master) or am servicing at the moment (if worker)
Definition: scheduler.h:78

Copyright © 2005-2019 Intel Corporation. All Rights Reserved.

Intel, Pentium, Intel Xeon, Itanium, Intel XScale and VTune are registered trademarks or trademarks of Intel Corporation or its subsidiaries in the United States and other countries.

* Other names and brands may be claimed as the property of others.