Intel(R) Threading Building Blocks Doxygen Documentation  version 4.2.3
scheduler_common.h
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 #ifndef _TBB_scheduler_common_H
18 #define _TBB_scheduler_common_H
19 
20 #include "tbb/tbb_machine.h"
22 
23 #include <string.h> // for memset, memcpy, memmove
24 
25 #include "tbb_statistics.h"
26 
27 #if TBB_USE_ASSERT > 1
28 #include <stdio.h>
29 #endif /* TBB_USE_ASSERT > 1 */
30 
31 /* Temporarily change "private" to "public" while including "tbb/task.h".
32  This hack allows us to avoid publishing internal types and methods
33  in the public header files just for sake of friend declarations. */
34 #ifndef private
35  #define private public
36  #define undef_private
37 #endif
38 
39 #include "tbb/task.h"
40 #include "tbb/tbb_exception.h"
41 
42 #ifdef undef_private
43  #undef private
44 #endif
45 
46 #ifndef __TBB_SCHEDULER_MUTEX_TYPE
47 #define __TBB_SCHEDULER_MUTEX_TYPE tbb::spin_mutex
48 #endif
49 // TODO: add conditional inclusion based on specified type
50 #include "tbb/spin_mutex.h"
51 
52 // This macro is an attempt to get rid of ugly ifdefs in the shared parts of the code.
53 // It drops the second argument depending on whether the controlling macro is defined.
54 // The first argument is just a convenience allowing to keep comma before the macro usage.
55 #if __TBB_TASK_GROUP_CONTEXT
56  #define __TBB_CONTEXT_ARG1(context) context
57  #define __TBB_CONTEXT_ARG(arg1, context) arg1, context
58 #else /* !__TBB_TASK_GROUP_CONTEXT */
59  #define __TBB_CONTEXT_ARG1(context)
60  #define __TBB_CONTEXT_ARG(arg1, context) arg1
61 #endif /* !__TBB_TASK_GROUP_CONTEXT */
62 
63 #if __TBB_TASK_ISOLATION
64  #define __TBB_ISOLATION_EXPR(isolation) isolation
65  #define __TBB_ISOLATION_ARG(arg1, isolation) arg1, isolation
66 #else
67  #define __TBB_ISOLATION_EXPR(isolation)
68  #define __TBB_ISOLATION_ARG(arg1, isolation) arg1
69 #endif /* __TBB_TASK_ISOLATION */
70 
71 
72 #if DO_TBB_TRACE
73 #include <cstdio>
74 #define TBB_TRACE(x) ((void)std::printf x)
75 #else
76 #define TBB_TRACE(x) ((void)(0))
77 #endif /* DO_TBB_TRACE */
78 
79 #if !__TBB_CPU_CTL_ENV_PRESENT
80 #include <fenv.h>
81 #endif
82 
83 #if _MSC_VER && !defined(__INTEL_COMPILER)
84  // Workaround for overzealous compiler warnings
85  // These particular warnings are so ubiquitous that no attempt is made to narrow
86  // the scope of the warnings.
87  #pragma warning (disable: 4100 4127 4312 4244 4267 4706)
88 #endif
89 
90 namespace tbb {
91 namespace interface7 {
92 namespace internal {
93 class task_arena_base;
94 class delegated_task;
95 class wait_task;
96 }}
97 namespace internal {
98 using namespace interface7::internal;
99 
100 class arena;
101 template<typename SchedulerTraits> class custom_scheduler;
102 class generic_scheduler;
103 class governor;
104 class mail_outbox;
105 class market;
106 class observer_proxy;
107 class task_scheduler_observer_v3;
108 
109 #if __TBB_TASK_PRIORITY
110 static const intptr_t num_priority_levels = 3;
111 static const intptr_t normalized_normal_priority = (num_priority_levels - 1) / 2;
112 
113 inline intptr_t normalize_priority ( priority_t p ) {
114  return intptr_t(p - priority_low) / priority_stride_v4;
115 }
116 
117 static const priority_t priority_from_normalized_rep[num_priority_levels] = {
119 };
120 
121 inline void assert_priority_valid ( intptr_t p ) {
122  __TBB_ASSERT_EX( p >= 0 && p < num_priority_levels, NULL );
123 }
124 
125 inline intptr_t& priority ( task& t ) {
126  return t.prefix().context->my_priority;
127 }
128 #else /* __TBB_TASK_PRIORITY */
129 static const intptr_t num_priority_levels = 1;
130 #endif /* __TBB_TASK_PRIORITY */
131 
134 
135 #if __TBB_TASK_GROUP_CONTEXT
136 
146 extern uintptr_t the_context_state_propagation_epoch;
147 
149 
150 typedef scheduler_mutex_type context_state_propagation_mutex_type;
151 extern context_state_propagation_mutex_type the_context_state_propagation_mutex;
152 #endif /* __TBB_TASK_GROUP_CONTEXT */
153 
155 const size_t task_alignment = 32;
156 
158 
159 const size_t task_prefix_reservation_size = ((sizeof(internal::task_prefix)-1)/task_alignment+1)*task_alignment;
160 
167 #if __TBB_PREVIEW_CRITICAL_TASKS
168  es_task_critical = 0x8,
170 #endif
171  es_task_enqueued = 0x10,
179 };
180 
181 inline void reset_extra_state ( task *t ) {
182  t->prefix().extra_state &= ~(es_task_is_stolen | es_task_enqueued);
183 }
184 
192 
195 
198  no_cache = 4,
201 };
202 
203 //------------------------------------------------------------------------
204 // Debugging support
205 //------------------------------------------------------------------------
206 
207 #if TBB_USE_ASSERT
208 
210 
211 template <typename T>
212 void poison_value ( T& val ) { val = * punned_cast<T*>(&venom); }
213 
215 inline bool is_alive( uintptr_t v ) { return v != venom; }
216 
219 inline void assert_task_valid( const task* task ) {
220  __TBB_ASSERT( task!=NULL, NULL );
221  __TBB_ASSERT( !is_poisoned(&task), NULL );
222  __TBB_ASSERT( (uintptr_t)task % task_alignment == 0, "misaligned task" );
223 #if __TBB_RECYCLE_TO_ENQUEUE
224  __TBB_ASSERT( (unsigned)task->state()<=(unsigned)task::to_enqueue, "corrupt task (invalid state)" );
225 #else
226  __TBB_ASSERT( (unsigned)task->state()<=(unsigned)task::recycle, "corrupt task (invalid state)" );
227 #endif
228 }
229 
230 #else /* !TBB_USE_ASSERT */
231 
234 #define poison_value(g) ((void)0)
235 
236 inline void assert_task_valid( const task* ) {}
237 
238 #endif /* !TBB_USE_ASSERT */
239 
240 //------------------------------------------------------------------------
241 // Helpers
242 //------------------------------------------------------------------------
243 
244 #if __TBB_TASK_GROUP_CONTEXT
245 inline bool ConcurrentWaitsEnabled ( task& t ) {
246  return (t.prefix().context->my_version_and_traits & task_group_context::concurrent_wait) != 0;
247 }
248 
249 inline bool CancellationInfoPresent ( task& t ) {
250  return t.prefix().context->my_cancellation_requested != 0;
251 }
252 
253 #if TBB_USE_CAPTURED_EXCEPTION
254  inline tbb_exception* TbbCurrentException( task_group_context*, tbb_exception* src) { return src->move(); }
255  inline tbb_exception* TbbCurrentException( task_group_context* c, captured_exception* src) {
256  if( c->my_version_and_traits & task_group_context::exact_exception )
257  runtime_warning( "Exact exception propagation is requested by application but the linked library is built without support for it");
258  return src;
259  }
260  #define TbbRethrowException(TbbCapturedException) (TbbCapturedException)->throw_self()
261 #else
262  // Using macro instead of an inline function here allows to avoid evaluation of the
263  // TbbCapturedException expression when exact propagation is enabled for the context.
264  #define TbbCurrentException(context, TbbCapturedException) \
265  context->my_version_and_traits & task_group_context::exact_exception \
266  ? tbb_exception_ptr::allocate() \
267  : tbb_exception_ptr::allocate( *(TbbCapturedException) );
268  #define TbbRethrowException(TbbCapturedException) \
269  { \
270  if( governor::rethrow_exception_broken() ) fix_broken_rethrow(); \
271  (TbbCapturedException)->throw_self(); \
272  }
273 #endif /* !TBB_USE_CAPTURED_EXCEPTION */
274 
275 #define TbbRegisterCurrentException(context, TbbCapturedException) \
276  if ( context->cancel_group_execution() ) { \
277  /* We are the first to signal cancellation, so store the exception that caused it. */ \
278  context->my_exception = TbbCurrentException( context, TbbCapturedException ); \
279  }
280 
281 #define TbbCatchAll(context) \
282  catch ( tbb_exception& exc ) { \
283  TbbRegisterCurrentException( context, &exc ); \
284  } catch ( std::exception& exc ) { \
285  TbbRegisterCurrentException( context, captured_exception::allocate(typeid(exc).name(), exc.what()) ); \
286  } catch ( ... ) { \
287  TbbRegisterCurrentException( context, captured_exception::allocate("...", "Unidentified exception") );\
288  }
289 
290 #else /* !__TBB_TASK_GROUP_CONTEXT */
291 
292 inline bool ConcurrentWaitsEnabled ( task& t ) { return false; }
293 
294 #endif /* __TBB_TASK_GROUP_CONTEXT */
295 
296 inline void prolonged_pause() {
297 #if defined(__TBB_time_stamp) && !__TBB_STEALING_PAUSE
298  // Assumption based on practice: 1000-2000 ticks seems to be a suitable invariant for the
299  // majority of platforms. Currently, skip platforms that define __TBB_STEALING_PAUSE
300  // because these platforms require very careful tuning.
302  const machine_tsc_t finish = prev + 1000;
303  atomic_backoff backoff;
304  do {
305  backoff.bounded_pause();
307  if ( curr <= prev )
308  // Possibly, the current logical thread is moved to another hardware thread or overflow is occurred.
309  break;
310  prev = curr;
311  } while ( prev < finish );
312 #else
313 #ifdef __TBB_STEALING_PAUSE
314  static const long PauseTime = __TBB_STEALING_PAUSE;
315 #elif __TBB_ipf
316  static const long PauseTime = 1500;
317 #else
318  static const long PauseTime = 80;
319 #endif
320  // TODO IDEA: Update PauseTime adaptively?
321  __TBB_Pause(PauseTime);
322 #endif
323 }
324 
325 //------------------------------------------------------------------------
326 // arena_slot
327 //------------------------------------------------------------------------
329  //TODO: make this tbb:atomic<>.
331 
333 
334  // Synchronization of access to Task pool
339 
341 
343 };
344 
347 
348  unsigned hint_for_pop;
349 
350 #if __TBB_PREVIEW_CRITICAL_TASKS
351  unsigned hint_for_critical;
353 #endif
354 
356 
358 
361 
362  // Task pool of the scheduler that owns this slot
364 
365 #if __TBB_STATISTICS
366  statistics_counters *my_counters;
368 #endif /* __TBB_STATISTICS */
369 };
370 
371 struct arena_slot : padded<arena_slot_line1>, padded<arena_slot_line2> {
372 #if TBB_USE_ASSERT
373  void fill_with_canary_pattern ( size_t first, size_t last ) {
374  for ( size_t i = first; i < last; ++i )
375  poison_pointer(task_pool_ptr[i]);
376  }
377 #else
378  void fill_with_canary_pattern ( size_t, size_t ) {}
379 #endif /* TBB_USE_ASSERT */
380 
381  void allocate_task_pool( size_t n ) {
382  size_t byte_size = ((n * sizeof(task*) + NFS_MaxLineSize - 1) / NFS_MaxLineSize) * NFS_MaxLineSize;
383  my_task_pool_size = byte_size / sizeof(task*);
384  task_pool_ptr = (task**)NFS_Allocate( 1, byte_size, NULL );
385  // No need to clear the fresh deque since valid items are designated by the head and tail members.
386  // But fill it with a canary pattern in the high vigilance debug mode.
387  fill_with_canary_pattern( 0, my_task_pool_size );
388  }
389 
391  void free_task_pool( ) {
392  // TODO: understand the assertion and modify
393  // __TBB_ASSERT( !task_pool /*TODO: == EmptyTaskPool*/, NULL);
394  if( task_pool_ptr ) {
395  __TBB_ASSERT( my_task_pool_size, NULL);
396  NFS_Free( task_pool_ptr );
397  task_pool_ptr = NULL;
398  my_task_pool_size = 0;
399  }
400  }
401 };
402 
403 #if !__TBB_CPU_CTL_ENV_PRESENT
404 class cpu_ctl_env {
405  fenv_t *my_fenv_ptr;
406 public:
407  cpu_ctl_env() : my_fenv_ptr(NULL) {}
409  if ( my_fenv_ptr )
410  tbb::internal::NFS_Free( (void*)my_fenv_ptr );
411  }
412  // It is possible not to copy memory but just to copy pointers but the following issues should be addressed:
413  // 1. The arena lifetime and the context lifetime are independent;
414  // 2. The user is allowed to recapture different FPU settings to context so 'current FPU settings' inside
415  // dispatch loop may become invalid.
416  // But do we really want to improve the fenv implementation? It seems to be better to replace the fenv implementation
417  // with a platform specific implementation.
418  cpu_ctl_env( const cpu_ctl_env &src ) : my_fenv_ptr(NULL) {
419  *this = src;
420  }
422  __TBB_ASSERT( src.my_fenv_ptr, NULL );
423  if ( !my_fenv_ptr )
424  my_fenv_ptr = (fenv_t*)tbb::internal::NFS_Allocate(1, sizeof(fenv_t), NULL);
425  *my_fenv_ptr = *src.my_fenv_ptr;
426  return *this;
427  }
428  bool operator!=( const cpu_ctl_env &ctl ) const {
429  __TBB_ASSERT( my_fenv_ptr, "cpu_ctl_env is not initialized." );
430  __TBB_ASSERT( ctl.my_fenv_ptr, "cpu_ctl_env is not initialized." );
431  return memcmp( (void*)my_fenv_ptr, (void*)ctl.my_fenv_ptr, sizeof(fenv_t) );
432  }
433  void get_env () {
434  if ( !my_fenv_ptr )
435  my_fenv_ptr = (fenv_t*)tbb::internal::NFS_Allocate(1, sizeof(fenv_t), NULL);
436  fegetenv( my_fenv_ptr );
437  }
438  const cpu_ctl_env& set_env () const {
439  __TBB_ASSERT( my_fenv_ptr, "cpu_ctl_env is not initialized." );
440  fesetenv( my_fenv_ptr );
441  return *this;
442  }
443 };
444 #endif /* !__TBB_CPU_CTL_ENV_PRESENT */
445 
446 } // namespace internal
447 } // namespace tbb
448 
449 #endif /* _TBB_scheduler_common_H */
void free_task_pool()
Deallocate task pool that was allocated by means of allocate_task_pool.
uint64_t machine_tsc_t
size_t my_task_pool_size
Capacity of the primary task pool (number of elements - pointers to task).
static const intptr_t num_priority_levels
#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:167
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 __TBB_EXPORTED_FUNC runtime_warning(const char *format,...)
Report a runtime warning.
bool ConcurrentWaitsEnabled(task &t)
const cpu_ctl_env & set_env() const
Task is known to be a small task and must not be cached.
Class that implements exponential backoff.
Definition: tbb_machine.h:345
task_extra_state
Definitions for bits in task_prefix::extra_state.
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:165
const size_t NFS_MaxLineSize
Compile-time constant that is upper bound on cache line/sector size.
Definition: tbb_stddef.h:216
Tag for v3 tasks (i.e. tasks in TBB 2.1-2.2)
Base class for user-defined tasks.
Definition: task.h:589
Work stealing task scheduler.
Definition: scheduler.h:120
bool operator!=(const cpu_ctl_env &ctl) const
__TBB_atomic size_t tail
Index of the element following the last ready task in the deque.
void __TBB_EXPORTED_FUNC NFS_Free(void *)
Free memory allocated by NFS_Allocate.
The graph class.
void assert_task_valid(const task *)
Tag for v3 task_proxy.
Set if the task has been stolen.
task to be recycled as continuation
Definition: task.h:621
Set if ref_count might be changed by another thread. Used for debugging.
void __TBB_Pause(int32_t)
Definition: tbb_machine.h:331
const size_t task_prefix_reservation_size
Number of bytes reserved for a task prefix.
void *__TBB_EXPORTED_FUNC NFS_Allocate(size_t n_element, size_t element_size, void *hint)
Allocate memory on cache/sector line boundary.
static const int priority_stride_v4
Definition: task.h:284
A template to select either 32-bit or 64-bit constant as compile time, depending on machine word size...
Definition: tbb_stddef.h:473
__TBB_SCHEDULER_MUTEX_TYPE scheduler_mutex_type
Mutex type for global locks in the scheduler.
Bitwise-OR of local_task and small_task.
auto first(Container &c) -> decltype(begin(c))
bool bounded_pause()
Pause for a few times and return false if saturated.
Definition: tbb_machine.h:372
Tag for v1 tasks (i.e. tasks in TBB 1.0 and 2.0)
generic_scheduler * my_scheduler
Scheduler of the thread attached to the slot.
cpu_ctl_env & operator=(const cpu_ctl_env &src)
const size_t task_alignment
Alignment for a task object.
void allocate_task_pool(size_t n)
#define __TBB_time_stamp()
void reset_extra_state(task *t)
cpu_ctl_env(const cpu_ctl_env &src)
__TBB_atomic size_t head
Index of the first ready task in the deque.
auto last(Container &c) -> decltype(begin(c))
#define __TBB_SCHEDULER_MUTEX_TYPE
void fill_with_canary_pattern(size_t, size_t)
unsigned hint_for_pop
Hint provided for operations with the container of starvation-resistant tasks.
void const char const char int ITT_FORMAT __itt_group_sync p
Disable caching for a small task.
Task is known to be a small task.
priority_t
Definition: task.h:291
#define __TBB_STEALING_PAUSE
Definition: mic_common.h:40
Task is known to have been allocated by this scheduler.
void poison_pointer(T *__TBB_atomic &)
Definition: tbb_stddef.h:305
internal::task_prefix & prefix(internal::version_tag *=NULL) const
Get reference to corresponding task_prefix.
Definition: task.h:946
#define __TBB_atomic
Definition: tbb_stddef.h:237
free_task_hint
Optimization hint to free_task that enables it omit unnecessary tests and code.
Pads type T to fill out to a multiple of cache line size.
Definition: tbb_stddef.h:261
#define poison_value(g)

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.