Intel(R) Threading Building Blocks Doxygen Documentation version 4.2.3
scheduler.h
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#ifndef _TBB_scheduler_H
18#define _TBB_scheduler_H
19
20#include "scheduler_common.h"
21#include "tbb/spin_mutex.h"
22#include "mailbox.h"
23#include "tbb_misc.h" // for FastRandom
24#include "itt_notify.h"
25#include "../rml/include/rml_tbb.h"
26
27#include "intrusive_list.h"
28
29#if __TBB_SURVIVE_THREAD_SWITCH
30#include "cilk-tbb-interop.h"
31#endif /* __TBB_SURVIVE_THREAD_SWITCH */
32
33#if __TBB_PREVIEW_RESUMABLE_TASKS
34#include "co_context.h"
35#endif
36
37namespace tbb {
38namespace internal {
39
40template<typename SchedulerTraits> class custom_scheduler;
41
42//------------------------------------------------------------------------
43// generic_scheduler
44//------------------------------------------------------------------------
45
46#define EmptyTaskPool ((task**)0)
47#define LockedTaskPool ((task**)~(intptr_t)0)
48
51 static const bool worker = false;
52 static const bool master = true;
54 bool type : 1;
56
57 bool outermost : 1;
58#if __TBB_PREVIEW_CRITICAL_TASKS
60 bool has_taken_critical_task : 1;
61#endif
62#if __TBB_PREVIEW_RESUMABLE_TASKS
64 bool genuine : 1;
65#endif
67 unsigned char :
68#if __TBB_PREVIEW_RESUMABLE_TASKS
69 4;
70#elif __TBB_PREVIEW_CRITICAL_TASKS
71 5;
72#else
73 6;
74#endif
75};
76
79 size_t my_arena_index; // TODO: make it unsigned and pair with my_affinity_id to fit into cache line
80
83
86
89
91
93
100
102
103#if __TBB_SCHEDULER_OBSERVER
105 observer_proxy* my_last_global_observer;
106#endif
107
108#if __TBB_ARENA_OBSERVER
110 observer_proxy* my_last_local_observer;
111#endif
112#if __TBB_TASK_PRIORITY
114
116 volatile intptr_t *my_ref_top_priority;
117
119 volatile uintptr_t *my_ref_reload_epoch;
120#endif /* __TBB_TASK_PRIORITY */
121#if __TBB_PREVIEW_RESUMABLE_TASKS
123 task* my_wait_task;
124
126 tbb::atomic<bool>* my_current_is_recalled;
127#endif
128};
129
131
138 , public ::rml::job
139 , public intrusive_list_node
140 , public scheduler_state {
141public: // almost every class in TBB uses generic_scheduler
142
145
146 static bool is_version_3_task( task& t ) {
147#if __TBB_PREVIEW_CRITICAL_TASKS
148 return (t.prefix().extra_state & 0x7)>=0x1;
149#else
150 return (t.prefix().extra_state & 0x0F)>=0x1;
151#endif
152 }
153
156#if __TBB_ipf
158 uintptr_t my_rsb_stealing_threshold;
159#endif
160
161 static const size_t null_arena_index = ~size_t(0);
162
163 inline bool is_task_pool_published () const;
164
165 inline bool is_local_task_pool_quiescent () const;
166
167 inline bool is_quiescent_local_task_pool_empty () const;
168
169 inline bool is_quiescent_local_task_pool_reset () const;
170
173
176
179
180#if __TBB_HOARD_NONLOCAL_TASKS
182 task* my_nonlocal_free_list;
183#endif
185
187
189
191
192 inline void attach_mailbox( affinity_id id );
193
194 /* A couple of bools can be located here because space is otherwise just padding after my_affinity_id. */
195
198
199#if __TBB_COUNT_TASK_NODES
201 intptr_t my_task_node_count;
202#endif /* __TBB_COUNT_TASK_NODES */
203
204#if __TBB_PREVIEW_RESUMABLE_TASKS
206 enum post_resume_action {
207 PRA_INVALID,
208 PRA_ABANDON,
209 PRA_CALLBACK,
210 PRA_CLEANUP,
211 PRA_NOTIFY,
212 PRA_NONE
213 };
214
216 typedef void(*suspend_callback_t)(void*, task::suspend_point);
217
219 struct callback_t {
220 suspend_callback_t suspend_callback;
221 void* user_callback;
222 task::suspend_point tag;
223
224 void operator()() {
225 if (suspend_callback) {
226 __TBB_ASSERT(suspend_callback && user_callback && tag, NULL);
227 suspend_callback(user_callback, tag);
228 }
229 }
230 };
231
233 co_context my_co_context;
234
236 post_resume_action my_post_resume_action;
237
239 void* my_post_resume_arg;
240
242 generic_scheduler* my_target_on_exit;
243
245 void set_post_resume_action(post_resume_action, void* arg);
246
248 void do_post_resume_action();
249
251
253 bool prepare_resume(generic_scheduler& target);
254
256
258 bool resume_original_scheduler();
259
261 void resume(generic_scheduler& target);
262
263 friend void recall_function(task::suspend_point tag);
264#endif /* __TBB_PREVIEW_RESUMABLE_TASKS */
265
267 void init_stack_info ();
268
270 bool can_steal () {
271 int anchor;
272 // TODO IDEA: Add performance warning?
273#if __TBB_ipf
274 return my_stealing_threshold < (uintptr_t)&anchor && (uintptr_t)__TBB_get_bsp() < my_rsb_stealing_threshold;
275#else
276 return my_stealing_threshold < (uintptr_t)&anchor;
277#endif
278 }
279
281
282 void publish_task_pool();
283
285
286 void leave_task_pool();
287
289
290 inline void reset_task_pool_and_leave ();
291
293
294 task** lock_task_pool( arena_slot* victim_arena_slot ) const;
295
297
298 void unlock_task_pool( arena_slot* victim_arena_slot, task** victim_task_pool ) const;
299
301
303 void acquire_task_pool() const;
304
306
308 void release_task_pool() const;
309
311
313
315 inline void commit_spawned_tasks( size_t new_tail );
316
318
319 inline void commit_relocated_tasks( size_t new_tail );
320
322
326
328
333#if __TBB_TASK_ISOLATION
334 task* get_task( size_t T, isolation_tag isolation, bool& tasks_omitted );
335#else
336 task* get_task( size_t T );
337#endif /* __TBB_TASK_ISOLATION */
339
346
348 static bool is_proxy( const task& t ) {
349 return t.prefix().extra_state==es_task_proxy;
350 }
351
354
356 task* steal_task_from( __TBB_ISOLATION_ARG( arena_slot& victim_arena_slot, isolation_tag isolation ) );
357
358#if __TBB_PREVIEW_CRITICAL_TASKS
360 task* get_critical_task( __TBB_ISOLATION_EXPR(isolation_tag isolation) );
361
364 bool handled_as_critical( task& t );
365#endif
366
369 static const size_t min_task_pool_size = 64;
370
372
374 size_t prepare_task_pool( size_t n );
375
378
380 bool cleanup_master( bool blocking_terminate );
381
383 static generic_scheduler* create_worker( market& m, size_t index, bool geniune );
384
386 static void cleanup_worker( void* arg, bool worker );
387
388protected:
389 template<typename SchedulerTraits> friend class custom_scheduler;
390 generic_scheduler( market &, bool );
391
392public:
393#if TBB_USE_ASSERT > 1
395
396 void assert_task_pool_valid() const;
397#else
399#endif /* TBB_USE_ASSERT <= 1 */
400
401 void attach_arena( arena*, size_t index, bool is_master );
402 void nested_arena_entry( arena*, size_t );
403 void nested_arena_exit();
404 void wait_until_empty();
405
406 void spawn( task& first, task*& next ) __TBB_override;
407
409
410 void enqueue( task&, void* reserved ) __TBB_override;
411
412 void local_spawn( task* first, task*& next );
413 void local_spawn_root_and_wait( task* first, task*& next );
414 virtual void local_wait_for_all( task& parent, task* child ) = 0;
415
417 void destroy();
418
420 void cleanup_scheduler();
421
423
424 task& allocate_task( size_t number_of_bytes,
426
428
429 template<free_task_hint h>
430 void free_task( task& t );
431
433 inline void deallocate_task( task& t );
434
436 inline bool is_worker() const;
437
439 inline bool outermost_level() const;
440
442
445 inline bool master_outermost_level () const;
446
448 inline bool worker_outermost_level () const;
449
451 unsigned max_threads_in_arena();
452
453#if __TBB_COUNT_TASK_NODES
454 intptr_t get_task_node_count( bool count_arena_workers = false );
455#endif /* __TBB_COUNT_TASK_NODES */
456
458 static task* plugged_return_list() {return (task*)(intptr_t)(-1);}
459
462
464 // TODO IDEA: see if putting my_return_list on separate cache line improves performance
466
468
469 virtual task* receive_or_steal_task( __TBB_ISOLATION_ARG( __TBB_atomic reference_count& completion_ref_count, isolation_tag isolation ) ) = 0;
470
473
474#if __TBB_TASK_GROUP_CONTEXT
476
481 inline task_group_context* default_context ();
482
484 char _padding1[NFS_MaxLineSize - sizeof(context_list_node_t)];
485
487 context_list_node_t my_context_list_head;
488
490 // TODO: check whether it can be deadly preempted and replace by spinning/sleeping mutex
491 spin_mutex my_context_list_mutex;
492
494
500 uintptr_t my_context_state_propagation_epoch;
501
503
506 tbb::atomic<uintptr_t> my_local_ctx_list_update;
507
508#if __TBB_TASK_PRIORITY
510 inline intptr_t effective_reference_priority () const;
511
512 // TODO: move into slots and fix is_out_of_work
514 task* my_offloaded_tasks;
515
517 task** my_offloaded_task_list_tail_link;
518
520 uintptr_t my_local_reload_epoch;
521
523 volatile bool my_pool_reshuffling_pending;
524
526
527 task* reload_tasks( __TBB_ISOLATION_EXPR( isolation_tag isolation ) );
528
529 task* reload_tasks( task*& offloaded_tasks, task**& offloaded_task_list_link, __TBB_ISOLATION_ARG( intptr_t top_priority, isolation_tag isolation ) );
530
532
533 task* winnow_task_pool ( __TBB_ISOLATION_EXPR( isolation_tag isolation ) );
534
536
537 task *get_task_and_activate_task_pool( size_t H0 , __TBB_ISOLATION_ARG( size_t T0, isolation_tag isolation ) );
538
540 inline void offload_task ( task& t, intptr_t task_priority );
541#endif /* __TBB_TASK_PRIORITY */
542
544
545 void cleanup_local_context_list ();
546
549 template <typename T>
550 void propagate_task_group_state ( T task_group_context::*mptr_state, task_group_context& src, T new_state );
551
552 // check consistency
553 static void assert_context_valid(const task_group_context *tgc) {
555#if TBB_USE_ASSERT
556 __TBB_ASSERT(tgc, NULL);
557 uintptr_t ctx = tgc->my_version_and_traits;
558 __TBB_ASSERT(is_alive(ctx), "referenced task_group_context was destroyed");
559 static const char *msg = "task_group_context is invalid";
560 __TBB_ASSERT(!(ctx&~(3|(7<<task_group_context::traits_offset))), msg); // the value fits known values of versions and traits
565 __TBB_ASSERT(tgc->my_owner, msg);
566 __TBB_ASSERT(tgc->my_node.my_next && tgc->my_node.my_prev, msg);
567 }
568#if __TBB_TASK_PRIORITY
569 assert_priority_valid(tgc->my_priority);
570#endif
571 if(tgc->my_parent)
572#if TBB_USE_ASSERT > 1
573 assert_context_valid(tgc->my_parent);
574#else
575 __TBB_ASSERT(is_alive(tgc->my_parent->my_version_and_traits), msg);
576#endif
577#endif
578 }
579#endif /* __TBB_TASK_GROUP_CONTEXT */
580
581#if _WIN32||_WIN64
582private:
584 ::rml::server::execution_resource_t master_exec_resource;
585public:
586#endif /* _WIN32||_WIN64 */
587
588#if __TBB_TASK_GROUP_CONTEXT
590
591 tbb::atomic<uintptr_t> my_nonlocal_ctx_list_update;
592#endif /* __TBB_TASK_GROUP_CONTEXT */
593
594#if __TBB_SURVIVE_THREAD_SWITCH
595 __cilk_tbb_unwatch_thunk my_cilk_unwatch_thunk;
596#if TBB_USE_ASSERT
598
599 enum cilk_state_t {
600 cs_none=0xF000, // Start at nonzero value so that we can detect use of zeroed memory.
601 cs_running,
602 cs_limbo,
603 cs_freed
604 };
605 cilk_state_t my_cilk_state;
606#endif /* TBB_USE_ASSERT */
607#endif /* __TBB_SURVIVE_THREAD_SWITCH */
608
609#if __TBB_STATISTICS
611
613 mutable statistics_counters my_counters;
614#endif /* __TBB_STATISTICS */
615
616}; // class generic_scheduler
617
618
619} // namespace internal
620} // namespace tbb
621
622#include "arena.h"
623#include "governor.h"
624
625namespace tbb {
626namespace internal {
627
630 return my_arena_slot->task_pool != EmptyTaskPool;
631}
632
635 task** tp = my_arena_slot->task_pool;
636 return tp == EmptyTaskPool || tp == LockedTaskPool;
637}
638
640 __TBB_ASSERT( is_local_task_pool_quiescent(), "Task pool is not quiescent" );
642}
643
645 __TBB_ASSERT( is_local_task_pool_quiescent(), "Task pool is not quiescent" );
646 return __TBB_load_relaxed(my_arena_slot->head) == 0 && __TBB_load_relaxed(my_arena_slot->tail) == 0;
647}
648
651}
652
654 return !is_worker() && outermost_level();
655}
656
658 return is_worker() && outermost_level();
659}
660
661#if __TBB_TASK_GROUP_CONTEXT
662inline task_group_context* generic_scheduler::default_context () {
663 return my_dummy_task->prefix().context;
664}
665#endif /* __TBB_TASK_GROUP_CONTEXT */
666
668 __TBB_ASSERT(id>0,NULL);
671}
672
673inline bool generic_scheduler::is_worker() const {
675}
676
678 __TBB_ASSERT(my_arena, NULL);
679 return my_arena->my_num_slots;
680}
681
684#if TBB_USE_ASSERT
685 task_prefix& p = t.prefix();
686 p.state = 0xFF;
687 p.extra_state = 0xFF;
688 poison_pointer(p.next);
689#endif /* TBB_USE_ASSERT */
691#if __TBB_COUNT_TASK_NODES
692 --my_task_node_count;
693#endif /* __TBB_COUNT_TASK_NODES */
694}
695
696#if __TBB_COUNT_TASK_NODES
697inline intptr_t generic_scheduler::get_task_node_count( bool count_arena_workers ) {
698 return my_task_node_count + (count_arena_workers? my_arena->workers_task_node_count(): 0);
699}
700#endif /* __TBB_COUNT_TASK_NODES */
701
703 __TBB_ASSERT( my_arena_slot->task_pool == LockedTaskPool, "Task pool must be locked when resetting task pool" );
707}
708
709//TODO: move to arena_slot
710inline void generic_scheduler::commit_spawned_tasks( size_t new_tail ) {
711 __TBB_ASSERT ( new_tail <= my_arena_slot->my_task_pool_size, "task deque end was overwritten" );
712 // emit "task was released" signal
713 ITT_NOTIFY(sync_releasing, (void*)((uintptr_t)my_arena_slot+sizeof(uintptr_t)));
714 // Release fence is necessary to make sure that previously stored task pointers
715 // are visible to thieves.
716 __TBB_store_with_release( my_arena_slot->tail, new_tail );
717}
718
721 "Task pool must be locked when calling commit_relocated_tasks()" );
723 // Tail is updated last to minimize probability of a thread making arena
724 // snapshot being misguided into thinking that this task pool is empty.
725 __TBB_store_release( my_arena_slot->tail, new_tail );
727}
728
729template<free_task_hint hint>
731#if __TBB_HOARD_NONLOCAL_TASKS
732 static const int h = hint&(~local_task);
733#else
734 static const free_task_hint h = hint;
735#endif
736 GATHER_STATISTIC(--my_counters.active_tasks);
737 task_prefix& p = t.prefix();
738 // Verify that optimization hints are correct.
739 __TBB_ASSERT( h!=small_local_task || p.origin==this, NULL );
740 __TBB_ASSERT( !(h&small_task) || p.origin, NULL );
741 __TBB_ASSERT( !(h&local_task) || (!p.origin || uintptr_t(p.origin) > uintptr_t(4096)), "local_task means allocated");
742 poison_value(p.depth);
743 poison_value(p.ref_count);
744 poison_pointer(p.owner);
745#if __TBB_PREVIEW_RESUMABLE_TASKS
746 __TBB_ASSERT(1L << t.state() & (1L << task::executing | 1L << task::allocated | 1 << task::to_resume), NULL);
747#else
748 __TBB_ASSERT(1L << t.state() & (1L << task::executing | 1L << task::allocated), NULL);
749#endif
750 p.state = task::freed;
751 if( h==small_local_task || p.origin==this ) {
752 GATHER_STATISTIC(++my_counters.free_list_length);
753 p.next = my_free_list;
754 my_free_list = &t;
755 } else if( !(h&local_task) && p.origin && uintptr_t(p.origin) < uintptr_t(4096) ) {
756 // a special value reserved for future use, do nothing since
757 // origin is not pointing to a scheduler instance
758 } else if( !(h&local_task) && p.origin ) {
759 GATHER_STATISTIC(++my_counters.free_list_length);
760#if __TBB_HOARD_NONLOCAL_TASKS
761 if( !(h&no_cache) ) {
762 p.next = my_nonlocal_free_list;
763 my_nonlocal_free_list = &t;
764 } else
765#endif
767 } else {
768 GATHER_STATISTIC(--my_counters.big_tasks);
770 }
771}
772
773#if __TBB_TASK_PRIORITY
774inline intptr_t generic_scheduler::effective_reference_priority () const {
775 // Workers on the outermost dispatch level (i.e. with empty stack) use market's
776 // priority as a reference point (to speedup discovering process level priority
777 // changes). But when there are enough workers to service (even if only partially)
778 // a lower priority arena, they should use arena's priority as a reference, lest
779 // be trapped in a futile spinning (because market's priority would prohibit
780 // executing ANY tasks in this arena).
781 return !worker_outermost_level() ||
782 my_arena->my_num_workers_allotted < my_arena->num_workers_active() ? *my_ref_top_priority : my_arena->my_top_priority;
783}
784
785inline void generic_scheduler::offload_task ( task& t, intptr_t /*priority*/ ) {
786 GATHER_STATISTIC( ++my_counters.prio_tasks_offloaded );
787 __TBB_ASSERT( !is_proxy(t), "The proxy task cannot be offloaded" );
788 __TBB_ASSERT( my_offloaded_task_list_tail_link && !*my_offloaded_task_list_tail_link, NULL );
789#if TBB_USE_ASSERT
791#endif /* TBB_USE_ASSERT */
792 t.prefix().next_offloaded = my_offloaded_tasks;
793 my_offloaded_tasks = &t;
794}
795#endif /* __TBB_TASK_PRIORITY */
796
797#if __TBB_PREVIEW_RESUMABLE_TASKS
798inline void generic_scheduler::set_post_resume_action(post_resume_action pra, void* arg) {
799 __TBB_ASSERT(my_post_resume_action == PRA_NONE, "Post resume action has already been set.");
800 __TBB_ASSERT(!my_post_resume_arg, NULL);
801
802 my_post_resume_action = pra;
803 my_post_resume_arg = arg;
804}
805
806inline bool generic_scheduler::prepare_resume(generic_scheduler& target) {
807 // The second condition is valid for worker or cleanup operation for master
808 if (my_properties.outermost && my_wait_task == my_dummy_task) {
809 if (my_properties.genuine) {
810 // We are in someone's original scheduler.
811 target.set_post_resume_action(PRA_NOTIFY, my_current_is_recalled);
812 return true;
813 }
814 // We are in a coroutine on outermost level.
815 target.set_post_resume_action(PRA_CLEANUP, this);
816 my_target_on_exit = &target;
817 // Request to finish coroutine instead of immediate resume.
818 return false;
819 }
820 __TBB_ASSERT(my_wait_task != my_dummy_task, NULL);
821 // We are in the coroutine on a nested level.
822 my_wait_task->prefix().abandoned_scheduler = this;
823 target.set_post_resume_action(PRA_ABANDON, my_wait_task);
824 return true;
825}
826
827inline bool generic_scheduler::resume_original_scheduler() {
828 generic_scheduler& target = *my_arena_slot->my_scheduler;
829 if (!prepare_resume(target)) {
830 // We should return and finish the current coroutine.
831 return false;
832 }
833 resume(target);
834 return true;
835}
836
837inline void generic_scheduler::resume(generic_scheduler& target) {
838 // Do not create non-trivial objects on the stack of this function. They might never be destroyed.
839 __TBB_ASSERT(governor::is_set(this), NULL);
840 __TBB_ASSERT(target.my_post_resume_action != PRA_NONE,
841 "The post resume action is not set. Has prepare_resume been called?");
842 __TBB_ASSERT(target.my_post_resume_arg, NULL);
843 __TBB_ASSERT(&target != this, NULL);
844 __TBB_ASSERT(target.my_arena == my_arena, "Cross-arena switch is forbidden.");
845
846 // Transfer thread related data.
847 target.my_arena_index = my_arena_index;
848 target.my_arena_slot = my_arena_slot;
849#if __TBB_SCHEDULER_OBSERVER
850 target.my_last_global_observer = my_last_global_observer;
851#endif
852#if __TBB_ARENA_OBSERVER
853 target.my_last_local_observer = my_last_local_observer;
854#endif
855 target.attach_mailbox(affinity_id(target.my_arena_index + 1));
856
857#if __TBB_TASK_PRIORITY
858 if (my_offloaded_tasks)
859 my_arena->orphan_offloaded_tasks(*this);
860#endif /* __TBB_TASK_PRIORITY */
861
863 my_co_context.resume(target.my_co_context);
864 __TBB_ASSERT(governor::is_set(this), NULL);
865
866 do_post_resume_action();
867 if (this == my_arena_slot->my_scheduler) {
868 my_arena_slot->my_scheduler_is_recalled->store<tbb::relaxed>(false);
869 }
870}
871
872inline void generic_scheduler::do_post_resume_action() {
873 __TBB_ASSERT(my_post_resume_action != PRA_NONE, "The post resume action is not set.");
874 __TBB_ASSERT(my_post_resume_arg, NULL);
875
876 switch (my_post_resume_action) {
877 case PRA_ABANDON:
878 {
879 task_prefix& wait_task_prefix = static_cast<task*>(my_post_resume_arg)->prefix();
880 reference_count old_ref_count = __TBB_FetchAndAddW(&wait_task_prefix.ref_count, internal::abandon_flag);
881 __TBB_ASSERT(old_ref_count > 0, NULL);
882 if (old_ref_count == 1) {
883 // Remove the abandon flag.
884 __TBB_store_with_release(wait_task_prefix.ref_count, 1);
885 // The wait has been completed. Spawn a resume task.
886 tbb::task::resume(wait_task_prefix.abandoned_scheduler);
887 }
888 break;
889 }
890 case PRA_CALLBACK:
891 {
892 callback_t callback = *static_cast<callback_t*>(my_post_resume_arg);
893 callback();
894 break;
895 }
896 case PRA_CLEANUP:
897 {
898 generic_scheduler* to_cleanup = static_cast<generic_scheduler*>(my_post_resume_arg);
899 __TBB_ASSERT(!to_cleanup->my_properties.genuine, NULL);
900 // Release coroutine's reference to my_arena.
901 to_cleanup->my_arena->on_thread_leaving<arena::ref_external>();
902 // Cache the coroutine for possible later re-usage
903 to_cleanup->my_arena->my_co_cache.push(to_cleanup);
904 break;
905 }
906 case PRA_NOTIFY:
907 {
908 tbb::atomic<bool>& scheduler_recall_flag = *static_cast<tbb::atomic<bool>*>(my_post_resume_arg);
909 scheduler_recall_flag = true;
910 // Do not access recall_flag because it can be destroyed after the notification.
911 break;
912 }
913 default:
914 __TBB_ASSERT(false, NULL);
915 }
916
917 my_post_resume_action = PRA_NONE;
918 my_post_resume_arg = NULL;
919}
920
921struct recall_functor {
922 tbb::atomic<bool>* scheduler_recall_flag;
923
924 recall_functor(tbb::atomic<bool>* recall_flag_) :
925 scheduler_recall_flag(recall_flag_) {}
926
927 void operator()(task::suspend_point /*tag*/) {
928 *scheduler_recall_flag = true;
929 }
930};
931
932#if _WIN32
933/* [[noreturn]] */ inline void __stdcall co_local_wait_for_all(void* arg) {
934#else
935/* [[noreturn]] */ inline void co_local_wait_for_all(void* arg) {
936#endif
937 // Do not create non-trivial objects on the stack of this function. They will never be destroyed.
938 generic_scheduler& s = *static_cast<generic_scheduler*>(arg);
940 // For correct task stealing threshold, calculate stack on a coroutine start
941 s.init_stack_info();
942 // Basically calls the user callback passed to the tbb::task::suspend function
943 s.do_post_resume_action();
944 // Endless loop here because coroutine could be reused
945 for( ;; ) {
946 __TBB_ASSERT(s.my_innermost_running_task == s.my_dummy_task, NULL);
947 __TBB_ASSERT(s.worker_outermost_level(), NULL);
948 s.local_wait_for_all(*s.my_dummy_task, NULL);
949 __TBB_ASSERT(s.my_target_on_exit, NULL);
950 __TBB_ASSERT(s.my_wait_task == NULL, NULL);
951 s.resume(*s.my_target_on_exit);
952 }
953 // This code is unreachable
954}
955#endif /* __TBB_PREVIEW_RESUMABLE_TASKS */
956
957#if __TBB_TASK_GROUP_CONTEXT
959
962template <bool report_tasks>
963class context_guard_helper {
964 const task_group_context *curr_ctx;
965#if __TBB_FP_CONTEXT
966 cpu_ctl_env guard_cpu_ctl_env;
967 cpu_ctl_env curr_cpu_ctl_env;
968#endif
969public:
970 context_guard_helper() : curr_ctx( NULL ) {
971#if __TBB_FP_CONTEXT
972 guard_cpu_ctl_env.get_env();
973 curr_cpu_ctl_env = guard_cpu_ctl_env;
974#endif
975 }
976 ~context_guard_helper() {
977#if __TBB_FP_CONTEXT
978 if ( curr_cpu_ctl_env != guard_cpu_ctl_env )
979 guard_cpu_ctl_env.set_env();
980#endif
981 if ( report_tasks && curr_ctx )
983 }
984 // The function is called from bypass dispatch loop on the hot path.
985 // Consider performance issues when refactoring.
986 void set_ctx( const task_group_context *ctx ) {
987 generic_scheduler::assert_context_valid( ctx );
988#if __TBB_FP_CONTEXT
989 const cpu_ctl_env &ctl = *punned_cast<cpu_ctl_env*>( &ctx->my_cpu_ctl_env );
990 // Compare the FPU settings directly because the context can be reused between parallel algorithms.
991 if ( ctl != curr_cpu_ctl_env ) {
992 curr_cpu_ctl_env = ctl;
993 curr_cpu_ctl_env.set_env();
994 }
995#endif
996 if ( report_tasks && ctx != curr_ctx ) {
997 // if task group context was active, report end of current execution frame.
998 if ( curr_ctx )
1000 // reporting begin of new task group context execution frame.
1001 // using address of task group context object to group tasks (parent).
1002 // id of task execution frame is NULL and reserved for future use.
1003 ITT_TASK_BEGIN( ctx,ctx->my_name, NULL );
1004 curr_ctx = ctx;
1005 }
1006 }
1007 void restore_default() {
1008#if __TBB_FP_CONTEXT
1009 if ( curr_cpu_ctl_env != guard_cpu_ctl_env ) {
1010 guard_cpu_ctl_env.set_env();
1011 curr_cpu_ctl_env = guard_cpu_ctl_env;
1012 }
1013#endif
1014 }
1015};
1016#else
1017template <bool T>
1019 void set_ctx() {}
1021};
1022#endif /* __TBB_TASK_GROUP_CONTEXT */
1023
1024} // namespace internal
1025} // namespace tbb
1026
1027#endif /* _TBB_scheduler_H */
#define __TBB_atomic
Definition: tbb_stddef.h:237
#define __TBB_ASSERT(predicate, comment)
No-op version of __TBB_ASSERT.
Definition: tbb_stddef.h:165
#define __TBB_override
Definition: tbb_stddef.h:240
#define __TBB_store_release
Definition: tbb_machine.h:857
void * __TBB_get_bsp()
Retrieves the current RSE backing store pointer. IA64 specific.
#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 * 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 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 id
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 h
#define __TBB_CONTEXT_ARG(arg1, context)
#define __TBB_ISOLATION_EXPR(isolation)
#define __TBB_ISOLATION_ARG(arg1, isolation)
#define poison_value(g)
#define ITT_TASK_BEGIN(type, name, id)
Definition: itt_notify.h:121
#define ITT_TASK_END
Definition: itt_notify.h:122
#define ITT_NOTIFY(name, obj)
Definition: itt_notify.h:112
#define LockedTaskPool
Definition: scheduler.h:47
#define EmptyTaskPool
Definition: scheduler.h:46
const size_t NFS_MaxLineSize
Compile-time constant that is upper bound on cache line/sector size.
Definition: tbb_stddef.h:216
void __TBB_EXPORTED_FUNC NFS_Free(void *)
Free memory allocated by NFS_Allocate.
The graph class.
@ 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
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.
T __TBB_load_relaxed(const volatile T &location)
Definition: tbb_machine.h:735
auto first(Container &c) -> decltype(begin(c))
free_task_hint
Optimization hint to free_task that enables it omit unnecessary tests and code.
@ no_cache
Disable caching for a small task.
@ small_task
Task is known to be a small task.
@ local_task
Task is known to have been allocated by this scheduler.
@ small_local_task
Bitwise-OR of local_task and small_task.
void __TBB_store_with_release(volatile T &location, V value)
Definition: tbb_machine.h:713
void co_local_wait_for_all(void *)
A lock that occupies a single byte.
Definition: spin_mutex.h:39
context_list_node_t * my_next
Definition: task.h:152
context_list_node_t * my_prev
Definition: task.h:151
Memory prefix to a task object.
Definition: task.h:203
unsigned char extra_state
Miscellaneous state that is not directly visible to users, stored as a byte for compactness.
Definition: task.h:292
unsigned char state
A task::state_type, stored as a byte for compactness.
Definition: task.h:283
task * next_offloaded
Pointer to the next offloaded lower priority task.
Definition: task.h:252
task_group_context * context
Shared context that is used to communicate asynchronous state changes.
Definition: task.h:230
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
task_group_context * my_parent
Pointer to the context of the parent cancellation group. NULL for isolated contexts.
Definition: task.h:410
intptr_t my_priority
Priority level of the task group (in normalized representation)
Definition: task.h:459
uintptr_t my_cancellation_requested
Specifies whether cancellation was requested for this task group.
Definition: task.h:440
uintptr_t my_state
Internal state (combination of state flags, currently only may_have_children).
Definition: task.h:455
internal::context_list_node_t my_node
Used to form the thread specific list of contexts without additional memory allocation.
Definition: task.h:415
static const kind_type dying
Definition: task.h:592
internal::generic_scheduler * my_owner
Scheduler instance that registered this context in its thread specific list.
Definition: task.h:452
uintptr_t my_version_and_traits
Version for run-time checks and behavioral traits of the context.
Definition: task.h:446
Base class for user-defined tasks.
Definition: task.h:615
@ 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
@ executing
task is running, and will be destroyed after method execute() completes.
Definition: task.h:637
state_type state() const
Current execution state.
Definition: task.h:912
internal::task_prefix & prefix(internal::version_tag *=NULL) const
Get reference to corresponding task_prefix.
Definition: task.h:1002
static const unsigned ref_external
Reference increment values for externals and workers.
Definition: arena.h:327
unsigned num_workers_active() const
The number of workers active in the arena.
Definition: arena.h:334
mail_outbox & mailbox(affinity_id id)
Get reference to mailbox corresponding to given affinity_id.
Definition: arena.h:305
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 void assume_scheduler(generic_scheduler *s)
Temporarily set TLS slot to the given scheduler.
Definition: governor.cpp:116
Data structure to be inherited by the types that can form intrusive lists.
Class representing source of mail.
Definition: mailbox.h:196
void attach(mail_outbox &putter)
Attach inbox to a corresponding outbox.
Definition: mailbox.h:204
Bit-field representing properties of a sheduler.
Definition: scheduler.h:50
bool type
Indicates that a scheduler acts as a master or a worker.
Definition: scheduler.h:54
unsigned char
Reserved bits.
Definition: scheduler.h:73
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
void free_task(task &t)
Put task on free list.
Definition: scheduler.h:730
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
bool can_steal()
Returns true if stealing is allowed.
Definition: scheduler.h:270
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 attach_mailbox(affinity_id id)
Definition: scheduler.h:667
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 master_outermost_level() const
True if the scheduler is on the outermost dispatch level in a master thread.
Definition: scheduler.h:653
bool is_local_task_pool_quiescent() const
Definition: scheduler.h:633
void nested_arena_entry(arena *, size_t)
Definition: arena.cpp:729
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
long my_ref_count
Reference count for scheduler.
Definition: scheduler.h:190
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 attach_arena(arena *, size_t index, bool is_master)
Definition: arena.cpp:80
void leave_task_pool()
Leave the task pool.
Definition: scheduler.cpp:1260
void destroy()
Destroy and deallocate this scheduler object.
Definition: scheduler.cpp:285
bool outermost_level() const
True if the scheduler is on the outermost dispatch level.
Definition: scheduler.h:649
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
virtual task * receive_or_steal_task(__TBB_ISOLATION_ARG(__TBB_atomic reference_count &completion_ref_count, isolation_tag isolation))=0
Try getting a task from other threads (via mailbox, stealing, FIFO queue, orphans adoption).
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
bool worker_outermost_level() const
True if the scheduler is on the outermost dispatch level in a worker thread.
Definition: scheduler.h:657
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
unsigned max_threads_in_arena()
Returns the concurrency limit of the current arena.
Definition: scheduler.h:677
static const size_t null_arena_index
Definition: scheduler.h:161
bool my_auto_initialized
True if *this was created by automatic TBB initialization.
Definition: scheduler.h:197
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
A fast random number generator.
Definition: tbb_misc.h:135

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.