#include <arena.h>

Inheritance diagram for tbb::internal::arena:

Collaboration diagram for tbb::internal::arena:

Public Types
enum	new_work_type { work_spawned, wakeup, work_enqueued }
	Types of work advertised by advertise_new_work() More...

typedef padded< arena_base >	base_type

typedef uintptr_t	pool_state_t

Public Member Functions
	arena (market &, unsigned max_num_workers, unsigned num_reserved_slots)
	Constructor. More...

mail_outbox &	mailbox (affinity_id id)
	Get reference to mailbox corresponding to given affinity_id. More...

void	free_arena ()
	Completes arena shutdown, destructs and deallocates it. More...

unsigned	num_workers_active ()
	The number of workers active in the arena. More...

template<arena::new_work_type work_type>
void	advertise_new_work ()
	If necessary, raise a flag that there is new job in arena. More...

bool	is_out_of_work ()
	Check if there is job anywhere in arena. More...

void	enqueue_task (task &, intptr_t, FastRandom &)
	enqueue a task into starvation-resistance queue More...

void	process (generic_scheduler &)
	Registers the worker with the arena and enters TBB scheduler dispatch loop. More...

template<unsigned ref_param>
void	on_thread_leaving ()
	Notification that worker or master leaves its arena. More...

bool	has_enqueued_tasks ()
	Check for the presence of enqueued tasks at all priority levels. More...

template<bool as_worker>
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, returns out_of_arena. More...

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. More...

Static Public Member Functions
static arena &	allocate_arena (market &, unsigned num_slots, unsigned num_reserved_slots)
	Allocate an instance of arena. More...

static int unsigned	num_arena_slots (unsigned num_slots)

static int	allocation_size (unsigned num_slots)

static bool	is_busy_or_empty (pool_state_t s)
	No tasks to steal or snapshot is being taken. More...

Public Attributes
arena_slot	my_slots [1]

Public Attributes inherited from tbb::internal::padded_base< arena_base, NFS_MaxLineSize, sizeof(arena_base) % NFS_MaxLineSize >
char	pad [S - R]

Public Attributes inherited from tbb::internal::arena_base
unsigned	my_num_workers_allotted
	The number of workers that have been marked out by the resource manager to service the arena. More...

atomic< unsigned >	my_references
	Reference counter for the arena. More...

atomic< unsigned >	my_limit
	The maximal number of currently busy slots. More...

task_stream< num_priority_levels >	my_task_stream
	Task pool for the tasks scheduled via task::enqueue() method. More...

unsigned	my_max_num_workers
	The number of workers requested by the master thread owning the arena. More...

int	my_num_workers_requested
	The number of workers that are currently requested from the resource manager. More...

tbb::atomic< uintptr_t >	my_pool_state
	Current task pool state and estimate of available tasks amount. More...

market *	my_market
	The market that owns this arena. More...

uintptr_t	my_aba_epoch
	ABA prevention marker. More...

cpu_ctl_env	my_cpu_ctl_env
	FPU control settings of arena's master thread captured at the moment of arena instantiation. More...

unsigned	my_num_slots
	The number of slots in the arena. More...

unsigned	my_num_reserved_slots
	The number of reserved slots (can be occupied only by masters). More...

concurrent_monitor	my_exit_monitors
	Waiting object for master threads that cannot join the arena. More...

Public Attributes inherited from tbb::internal::padded_base< intrusive_list_node, NFS_MaxLineSize, sizeof(intrusive_list_node) % NFS_MaxLineSize >
char	pad [S - R]

Public Attributes inherited from tbb::internal::intrusive_list_node
intrusive_list_node *	my_prev_node

intrusive_list_node *	my_next_node

Static Public Attributes
static const pool_state_t	SNAPSHOT_EMPTY = 0
	No tasks to steal since last snapshot was taken. More...

static const pool_state_t	SNAPSHOT_FULL = pool_state_t(-1)
	At least one task has been offered for stealing since the last snapshot started. More...

static const unsigned	ref_external_bits = 12
	The number of least significant bits for external references. More...

static const unsigned	ref_external = 1
	Reference increment values for externals and workers. More...

static const unsigned	ref_worker = 1<<ref_external_bits

static const size_t	out_of_arena = ~size_t(0)

Private Member Functions
void	restore_priority_if_need ()
	If enqueued tasks found, restore arena priority and task presence status. More...

Detailed Description

Definition at line 162 of file arena.h.

Member Typedef Documentation

◆ base_type

typedef padded<arena_base> tbb::internal::arena::base_type

Definition at line 167 of file arena.h.

◆ pool_state_t

typedef uintptr_t tbb::internal::arena::pool_state_t

Definition at line 201 of file arena.h.

Member Enumeration Documentation

◆ new_work_type

enum tbb::internal::arena::new_work_type

Types of work advertised by advertise_new_work()

Enumerator
work_spawned
wakeup
work_enqueued

Definition at line 170 of file arena.h.

                        {
         work_spawned,
         wakeup,
         work_enqueued
     };

Constructor & Destructor Documentation

◆ arena()

tbb::internal::arena::arena	(	market &	m,
		unsigned	max_num_workers,
		unsigned	num_reserved_slots
	)

Constructor.

Definition at line 190 of file arena.cpp.

                                                                           {
     __TBB_ASSERT( !my_guard, "improperly allocated arena?" );
     __TBB_ASSERT( sizeof(my_slots[0]) % NFS_GetLineSize()==0, "arena::slot size not multiple of cache line size" );
     __TBB_ASSERT( (uintptr_t)this % NFS_GetLineSize()==0, "arena misaligned" );
 #if __TBB_TASK_PRIORITY
     __TBB_ASSERT( !my_reload_epoch && !my_orphaned_tasks && !my_skipped_fifo_priority, "New arena object is not zeroed" );
 #endif /* __TBB_TASK_PRIORITY */
     my_market = &m;
     my_limit = 1;
     // Two slots are mandatory: for the master, and for 1 worker (required to support starvation resistant tasks).
     my_num_slots = num_arena_slots(num_slots);
     my_num_reserved_slots = num_reserved_slots;
     my_max_num_workers = num_slots-num_reserved_slots;
     my_references = ref_external; // accounts for the master
 #if __TBB_TASK_PRIORITY
     my_bottom_priority = my_top_priority = normalized_normal_priority;
 #endif /* __TBB_TASK_PRIORITY */
     my_aba_epoch = m.my_arenas_aba_epoch;
 #if __TBB_ARENA_OBSERVER
     my_observers.my_arena = this;
 #endif
     __TBB_ASSERT ( my_max_num_workers <= my_num_slots, NULL );
     // Construct slots. Mark internal synchronization elements for the tools.
     for( unsigned i = 0; i < my_num_slots; ++i ) {
         __TBB_ASSERT( !my_slots[i].my_scheduler && !my_slots[i].task_pool, NULL );
         __TBB_ASSERT( !my_slots[i].task_pool_ptr, NULL );
         __TBB_ASSERT( !my_slots[i].my_task_pool_size, NULL );
         ITT_SYNC_CREATE(my_slots + i, SyncType_Scheduler, SyncObj_WorkerTaskPool);
         mailbox(i+1).construct();
         ITT_SYNC_CREATE(&mailbox(i+1), SyncType_Scheduler, SyncObj_Mailbox);
         my_slots[i].hint_for_pop = i;
 #if __TBB_STATISTICS
         my_slots[i].my_counters = new ( NFS_Allocate(1, sizeof(statistics_counters), NULL) ) statistics_counters;
 #endif /* __TBB_STATISTICS */
     }
     my_task_stream.initialize(my_num_slots);
     ITT_SYNC_CREATE(&my_task_stream, SyncType_Scheduler, SyncObj_TaskStream);
 #if __TBB_ENQUEUE_ENFORCED_CONCURRENCY
     my_concurrency_mode = cm_normal;
 #endif
 #if !__TBB_FP_CONTEXT
     my_cpu_ctl_env.get_env();
 #endif
 }

Referenced by allocate_arena().

Here is the call graph for this function:

Here is the caller graph for this function:

Member Function Documentation

◆ advertise_new_work()

template<arena::new_work_type work_type>

void tbb::internal::arena::advertise_new_work ( )

If necessary, raise a flag that there is new job in arena.

Definition at line 376 of file arena.h.

                                                                       {
     if( work_type == work_enqueued ) {
 #if __TBB_ENQUEUE_ENFORCED_CONCURRENCY
         if( my_market->my_num_workers_soft_limit == 0 ) {
             if( my_concurrency_mode!=cm_enforced_global ) {
                 if( my_market->mandatory_concurrency_enable( this ) ) {
                     my_pool_state = SNAPSHOT_FULL;
                     return;
                 }
             }
         } else if( my_max_num_workers==0 && my_num_reserved_slots==1 ) {
             my_max_num_workers = 1;
             __TBB_ASSERT(my_concurrency_mode==cm_normal, NULL);
             my_concurrency_mode = cm_enforced_local;
             my_pool_state = SNAPSHOT_FULL;
             my_market->adjust_demand( *this, 1 );
             return;
         }
 #endif /* __TBB_ENQUEUE_ENFORCED_CONCURRENCY */
         // Local memory fence here and below is required to avoid missed wakeups; see the comment below.
         // Starvation resistant tasks require concurrency, so missed wakeups are unacceptable.
         atomic_fence();
     }
     else if( work_type == wakeup ) {
         __TBB_ASSERT(my_max_num_workers!=0, "Unexpected worker wakeup request");
         atomic_fence();
     }
     // Double-check idiom that, in case of spawning, is deliberately sloppy about memory fences.
     // Technically, to avoid missed wakeups, there should be a full memory fence between the point we
     // released the task pool (i.e. spawned task) and read the arena's state.  However, adding such a
     // fence might hurt overall performance more than it helps, because the fence would be executed
     // on every task pool release, even when stealing does not occur.  Since TBB allows parallelism,
     // but never promises parallelism, the missed wakeup is not a correctness problem.
     pool_state_t snapshot = my_pool_state;
     if( is_busy_or_empty(snapshot) ) {
         // Attempt to mark as full.  The compare_and_swap below is a little unusual because the
         // result is compared to a value that can be different than the comparand argument.
         if( my_pool_state.compare_and_swap( SNAPSHOT_FULL, snapshot )==SNAPSHOT_EMPTY ) {
             if( snapshot!=SNAPSHOT_EMPTY ) {
                 // This thread read "busy" into snapshot, and then another thread transitioned
                 // my_pool_state to "empty" in the meantime, which caused the compare_and_swap above
                 // to fail.  Attempt to transition my_pool_state from "empty" to "full".
                 if( my_pool_state.compare_and_swap( SNAPSHOT_FULL, SNAPSHOT_EMPTY )!=SNAPSHOT_EMPTY ) {
                     // Some other thread transitioned my_pool_state from "empty", and hence became
                     // responsible for waking up workers.
                     return;
                 }
             }
             // This thread transitioned pool from empty to full state, and thus is responsible for
             // telling the market that there is work to do.
 #if __TBB_ENQUEUE_ENFORCED_CONCURRENCY
             if( work_type == work_spawned ) {
                 if( my_concurrency_mode!=cm_normal ) {
                     switch( my_concurrency_mode ) {
                     case cm_enforced_local:
                         __TBB_ASSERT(my_max_num_workers==1, "");
                         __TBB_ASSERT(!governor::local_scheduler()->is_worker(), "");
                         // There was deliberate oversubscription on 1 core for sake of starvation-resistant tasks.
                         // Now a single active thread (must be the master) supposedly starts a new parallel region
                         // with relaxed sequential semantics, and oversubscription should be avoided.
                         // Demand for workers has been decreased to 0 during SNAPSHOT_EMPTY, so just keep it.
                         my_max_num_workers = 0;
                         my_concurrency_mode = cm_normal;
                         break;
                     case cm_enforced_global:
                         my_market->mandatory_concurrency_disable( this );
                         restore_priority_if_need();
                         break;
                     default:
                         break;
                     }
                     return;
                 }
             }
 #endif /* __TBB_ENQUEUE_ENFORCED_CONCURRENCY */
             my_market->adjust_demand( *this, my_max_num_workers );
         }
     }
 }

References __TBB_ASSERT, tbb::internal::market::adjust_demand(), tbb::atomic_fence(), tbb::internal::atomic_impl< T >::compare_and_swap(), is_busy_or_empty(), tbb::internal::governor::local_scheduler(), tbb::internal::arena_base::my_market, tbb::internal::arena_base::my_max_num_workers, tbb::internal::arena_base::my_num_reserved_slots, tbb::internal::market::my_num_workers_soft_limit, tbb::internal::arena_base::my_pool_state, restore_priority_if_need(), SNAPSHOT_EMPTY, SNAPSHOT_FULL, wakeup, work_enqueued, and work_spawned.

Referenced by tbb::internal::generic_scheduler::get_task(), tbb::internal::generic_scheduler::local_spawn(), and tbb::internal::generic_scheduler::steal_task().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ allocate_arena()

arena & tbb::internal::arena::allocate_arena	(	market &	m,
		unsigned	num_slots,
		unsigned	num_reserved_slots
	)

static

Allocate an instance of arena.

Definition at line 235 of file arena.cpp.

                                                                                          {
     __TBB_ASSERT( sizeof(base_type) + sizeof(arena_slot) == sizeof(arena), "All arena data fields must go to arena_base" );
     __TBB_ASSERT( sizeof(base_type) % NFS_GetLineSize() == 0, "arena slots area misaligned: wrong padding" );
     __TBB_ASSERT( sizeof(mail_outbox) == NFS_MaxLineSize, "Mailbox padding is wrong" );
     size_t n = allocation_size(num_arena_slots(num_slots));
     unsigned char* storage = (unsigned char*)NFS_Allocate( 1, n, NULL );
     // Zero all slots to indicate that they are empty
     memset( storage, 0, n );
     return *new( storage + num_arena_slots(num_slots) * sizeof(mail_outbox) ) arena(m, num_slots, num_reserved_slots);
 }

References __TBB_ASSERT, allocation_size(), arena(), tbb::internal::NFS_Allocate(), tbb::internal::NFS_GetLineSize(), tbb::internal::NFS_MaxLineSize, and num_arena_slots().

Referenced by tbb::internal::market::create_arena().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ allocation_size()

static int tbb::internal::arena::allocation_size ( unsigned num_slots )

inlinestatic

Definition at line 186 of file arena.h.

                                                       {
         return sizeof(base_type) + num_slots * (sizeof(mail_outbox) + sizeof(arena_slot));
     }

Referenced by allocate_arena(), and free_arena().

Here is the caller graph for this function:

◆ enqueue_task()

void tbb::internal::arena::enqueue_task	(	task &	t,
		intptr_t	prio,
		FastRandom &	random
	)

enqueue a task into starvation-resistance queue

Definition at line 544 of file arena.cpp.

 {
 #if __TBB_RECYCLE_TO_ENQUEUE
     __TBB_ASSERT( t.state()==task::allocated || t.state()==task::to_enqueue, "attempt to enqueue task with inappropriate state" );
 #else
     __TBB_ASSERT( t.state()==task::allocated, "attempt to enqueue task that is not in 'allocated' state" );
 #endif
     t.prefix().state = task::ready;
     t.prefix().extra_state |= es_task_enqueued; // enqueued task marker
 
 #if TBB_USE_ASSERT
     if( task* parent = t.parent() ) {
         internal::reference_count ref_count = parent->prefix().ref_count;
         __TBB_ASSERT( ref_count!=0, "attempt to enqueue task whose parent has a ref_count==0 (forgot to set_ref_count?)" );
         __TBB_ASSERT( ref_count>0, "attempt to enqueue task whose parent has a ref_count<0" );
         parent->prefix().extra_state |= es_ref_count_active;
     }
     __TBB_ASSERT(t.prefix().affinity==affinity_id(0), "affinity is ignored for enqueued tasks");
 #endif /* TBB_USE_ASSERT */
 
     ITT_NOTIFY(sync_releasing, &my_task_stream);
 #if __TBB_TASK_PRIORITY
     intptr_t p = prio ? normalize_priority(priority_t(prio)) : normalized_normal_priority;
     assert_priority_valid(p);
     my_task_stream.push( &t, p, random );
     if ( p != my_top_priority )
         my_market->update_arena_priority( *this, p );
 #else /* !__TBB_TASK_PRIORITY */
     __TBB_ASSERT_EX(prio == 0, "the library is not configured to respect the task priority");
     my_task_stream.push( &t, 0, random );
 #endif /* !__TBB_TASK_PRIORITY */
     advertise_new_work<work_enqueued>();
 #if __TBB_TASK_PRIORITY
     if ( p != my_top_priority )
         my_market->update_arena_priority( *this, p );
 #endif /* __TBB_TASK_PRIORITY */
 }

References __TBB_ASSERT, __TBB_ASSERT_EX, tbb::task::allocated, tbb::internal::es_ref_count_active, tbb::internal::es_task_enqueued, ITT_NOTIFY, tbb::internal::arena_base::my_market, tbb::internal::arena_base::my_task_stream, p, parent, tbb::task::parent(), tbb::task::prefix(), tbb::internal::task_stream< Levels >::push(), tbb::task::ready, tbb::task::state(), and sync_releasing.

Referenced by tbb::internal::custom_scheduler< SchedulerTraits >::tally_completion_of_predecessor().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ free_arena()

void tbb::internal::arena::free_arena ( )

Completes arena shutdown, destructs and deallocates it.

Definition at line 246 of file arena.cpp.

                         {
     __TBB_ASSERT( is_alive(my_guard), NULL );
     __TBB_ASSERT( !my_references, "There are threads in the dying arena" );
     __TBB_ASSERT( !my_num_workers_requested && !my_num_workers_allotted, "Dying arena requests workers" );
     __TBB_ASSERT( my_pool_state == SNAPSHOT_EMPTY || !my_max_num_workers, "Inconsistent state of a dying arena" );
 #if __TBB_ENQUEUE_ENFORCED_CONCURRENCY
     __TBB_ASSERT( my_concurrency_mode != cm_enforced_global, NULL );
 #endif
 #if !__TBB_STATISTICS_EARLY_DUMP
     GATHER_STATISTIC( dump_arena_statistics() );
 #endif
     poison_value( my_guard );
     intptr_t drained = 0;
     for ( unsigned i = 0; i < my_num_slots; ++i ) {
         __TBB_ASSERT( !my_slots[i].my_scheduler, "arena slot is not empty" );
         // TODO: understand the assertion and modify
         // __TBB_ASSERT( my_slots[i].task_pool == EmptyTaskPool, NULL );
         __TBB_ASSERT( my_slots[i].head == my_slots[i].tail, NULL ); // TODO: replace by is_quiescent_local_task_pool_empty
         my_slots[i].free_task_pool();
 #if __TBB_STATISTICS
         NFS_Free( my_slots[i].my_counters );
 #endif /* __TBB_STATISTICS */
         drained += mailbox(i+1).drain();
     }
     __TBB_ASSERT( my_task_stream.drain()==0, "Not all enqueued tasks were executed");
 #if __TBB_COUNT_TASK_NODES
     my_market->update_task_node_count( -drained );
 #endif /* __TBB_COUNT_TASK_NODES */
     // remove an internal reference
     my_market->release( /*is_public=*/false, /*blocking_terminate=*/false );
 #if __TBB_TASK_GROUP_CONTEXT
     __TBB_ASSERT( my_default_ctx, "Master thread never entered the arena?" );
     my_default_ctx->~task_group_context();
     NFS_Free(my_default_ctx);
 #endif /* __TBB_TASK_GROUP_CONTEXT */
 #if __TBB_ARENA_OBSERVER
     if ( !my_observers.empty() )
         my_observers.clear();
 #endif /* __TBB_ARENA_OBSERVER */
     void* storage  = &mailbox(my_num_slots);
     __TBB_ASSERT( my_references == 0, NULL );
     __TBB_ASSERT( my_pool_state == SNAPSHOT_EMPTY || !my_max_num_workers, NULL );
     this->~arena();
 #if TBB_USE_ASSERT > 1
     memset( storage, 0, allocation_size(my_num_slots) );
 #endif /* TBB_USE_ASSERT */
     NFS_Free( storage );
 }

Referenced by tbb::internal::market::try_destroy_arena().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ has_enqueued_tasks()

bool tbb::internal::arena::has_enqueued_tasks ( )

Check for the presence of enqueued tasks at all priority levels.

Definition at line 369 of file arena.cpp.

                                {
     // Look for enqueued tasks at all priority levels
     for ( int p = 0; p < num_priority_levels; ++p )
         if ( !my_task_stream.empty(p) )
             return true;
     return false;
 }

References tbb::internal::task_stream< Levels >::empty(), tbb::internal::arena_base::my_task_stream, tbb::internal::num_priority_levels, and p.

Referenced by restore_priority_if_need().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ is_busy_or_empty()

static bool tbb::internal::arena::is_busy_or_empty ( pool_state_t s )

inlinestatic

No tasks to steal or snapshot is being taken.

Definition at line 217 of file arena.h.

217 { return s < SNAPSHOT_FULL; }

s

void const char const char int ITT_FORMAT __itt_group_sync s

Definition: ittnotify_static.h:80

tbb::internal::arena::SNAPSHOT_FULL

static const pool_state_t SNAPSHOT_FULL

At least one task has been offered for stealing since the last snapshot started.

Definition: arena.h:207

References s, and SNAPSHOT_FULL.

Referenced by advertise_new_work().

Here is the caller graph for this function:

◆ is_out_of_work()

bool tbb::internal::arena::is_out_of_work ( )

Check if there is job anywhere in arena.

Return true if no job or if arena is being cleaned up.

Definition at line 397 of file arena.cpp.

                            {
     // TODO: rework it to return at least a hint about where a task was found; better if the task itself.
     for(;;) {
         pool_state_t snapshot = my_pool_state;
         switch( snapshot ) {
             case SNAPSHOT_EMPTY:
                 return true;
             case SNAPSHOT_FULL: {
                 // Use unique id for "busy" in order to avoid ABA problems.
                 const pool_state_t busy = pool_state_t(&busy);
                 // Request permission to take snapshot
                 if( my_pool_state.compare_and_swap( busy, SNAPSHOT_FULL )==SNAPSHOT_FULL ) {
                     // Got permission. Take the snapshot.
                     // NOTE: This is not a lock, as the state can be set to FULL at
                     //       any moment by a thread that spawns/enqueues new task.
                     size_t n = my_limit;
                     // Make local copies of volatile parameters. Their change during
                     // snapshot taking procedure invalidates the attempt, and returns
                     // this thread into the dispatch loop.
 #if __TBB_TASK_PRIORITY
                     uintptr_t reload_epoch = __TBB_load_with_acquire( my_reload_epoch );
                     intptr_t top_priority = my_top_priority;
                     // Inspect primary task pools first
 #endif /* __TBB_TASK_PRIORITY */
                     size_t k;
                     for( k=0; k<n; ++k ) {
                         if( my_slots[k].task_pool != EmptyTaskPool &&
                             __TBB_load_relaxed(my_slots[k].head) < __TBB_load_relaxed(my_slots[k].tail) )
                         {
                             // k-th primary task pool is nonempty and does contain tasks.
                             break;
                         }
                         if( my_pool_state!=busy )
                             return false; // the work was published
                     }
                     __TBB_ASSERT( k <= n, NULL );
                     bool work_absent = k == n;
 #if __TBB_TASK_PRIORITY
                     // Variable tasks_present indicates presence of tasks at any priority
                     // level, while work_absent refers only to the current priority.
                     bool tasks_present = !work_absent || my_orphaned_tasks;
                     bool dequeuing_possible = false;
                     if ( work_absent ) {
                         // Check for the possibility that recent priority changes
                         // brought some tasks to the current priority level
 
                         uintptr_t abandonment_epoch = my_abandonment_epoch;
                         // Master thread's scheduler needs special handling as it
                         // may be destroyed at any moment (workers' schedulers are
                         // guaranteed to be alive while at least one thread is in arena).
                         // The lock below excludes concurrency with task group state change
                         // propagation and guarantees lifetime of the master thread.
                         the_context_state_propagation_mutex.lock();
                         work_absent = !may_have_tasks( my_slots[0].my_scheduler, tasks_present, dequeuing_possible );
                         the_context_state_propagation_mutex.unlock();
                         // The following loop is subject to data races. While k-th slot's
                         // scheduler is being examined, corresponding worker can either
                         // leave to RML or migrate to another arena.
                         // But the races are not prevented because all of them are benign.
                         // First, the code relies on the fact that worker thread's scheduler
                         // object persists until the whole library is deinitialized.
                         // Second, in the worst case the races can only cause another
                         // round of stealing attempts to be undertaken. Introducing complex
                         // synchronization into this coldest part of the scheduler's control
                         // flow does not seem to make sense because it both is unlikely to
                         // ever have any observable performance effect, and will require
                         // additional synchronization code on the hotter paths.
                         for( k = 1; work_absent && k < n; ++k ) {
                             if( my_pool_state!=busy )
                                 return false; // the work was published
                             work_absent = !may_have_tasks( my_slots[k].my_scheduler, tasks_present, dequeuing_possible );
                         }
                         // Preclude premature switching arena off because of a race in the previous loop.
                         work_absent = work_absent
                                       && !__TBB_load_with_acquire(my_orphaned_tasks)
                                       && abandonment_epoch == my_abandonment_epoch;
                     }
 #endif /* __TBB_TASK_PRIORITY */
                     // Test and test-and-set.
                     if( my_pool_state==busy ) {
 #if __TBB_TASK_PRIORITY
                         bool no_fifo_tasks = my_task_stream.empty(top_priority);
                         work_absent = work_absent && (!dequeuing_possible || no_fifo_tasks)
                                       && top_priority == my_top_priority && reload_epoch == my_reload_epoch;
 #else
                         bool no_fifo_tasks = my_task_stream.empty(0);
                         work_absent = work_absent && no_fifo_tasks;
 #endif /* __TBB_TASK_PRIORITY */
                         if( work_absent ) {
 #if __TBB_TASK_PRIORITY
                             if ( top_priority > my_bottom_priority ) {
                                 if ( my_market->lower_arena_priority(*this, top_priority - 1, reload_epoch)
                                      && !my_task_stream.empty(top_priority) )
                                 {
                                     atomic_update( my_skipped_fifo_priority, top_priority, std::less<intptr_t>());
                                 }
                             }
                             else if ( !tasks_present && !my_orphaned_tasks && no_fifo_tasks ) {
 #endif /* __TBB_TASK_PRIORITY */
                                 // save current demand value before setting SNAPSHOT_EMPTY,
                                 // to avoid race with advertise_new_work.
                                 int current_demand = (int)my_max_num_workers;
                                 if( my_pool_state.compare_and_swap( SNAPSHOT_EMPTY, busy )==busy ) {
 #if __TBB_ENQUEUE_ENFORCED_CONCURRENCY
                                     if( my_concurrency_mode==cm_enforced_global  ) {
                                         // adjust_demand() called inside, if needed
                                         my_market->mandatory_concurrency_disable( this );
                                     } else
 #endif /* __TBB_ENQUEUE_ENFORCED_CONCURRENCY */
                                     {
                                         // This thread transitioned pool to empty state, and thus is
                                         // responsible for telling the market that there is no work to do.
                                         my_market->adjust_demand( *this, -current_demand );
                                     }
                                     restore_priority_if_need();
                                     return true;
                                 }
                                 return false;
 #if __TBB_TASK_PRIORITY
                             }
 #endif /* __TBB_TASK_PRIORITY */
                         }
                         // Undo previous transition SNAPSHOT_FULL-->busy, unless another thread undid it.
                         my_pool_state.compare_and_swap( SNAPSHOT_FULL, busy );
                     }
                 }
                 return false;
             }
             default:
                 // Another thread is taking a snapshot.
                 return false;
         }
     }
 }

References __TBB_ASSERT, tbb::internal::__TBB_load_relaxed(), tbb::internal::__TBB_load_with_acquire(), tbb::internal::market::adjust_demand(), tbb::internal::atomic_update(), tbb::internal::atomic_impl< T >::compare_and_swap(), tbb::internal::task_stream< Levels >::empty(), EmptyTaskPool, head, int, tbb::internal::arena_base::my_limit, tbb::internal::arena_base::my_market, tbb::internal::arena_base::my_max_num_workers, tbb::internal::arena_base::my_pool_state, my_slots, tbb::internal::arena_base::my_task_stream, restore_priority_if_need(), SNAPSHOT_EMPTY, SNAPSHOT_FULL, and tail.

Referenced by on_thread_leaving().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ mailbox()

mail_outbox& tbb::internal::arena::mailbox ( affinity_id id )

inline

Get reference to mailbox corresponding to given affinity_id.

Definition at line 191 of file arena.h.

                                            {
         __TBB_ASSERT( 0<id, "affinity id must be positive integer" );
         __TBB_ASSERT( id <= my_num_slots, "affinity id out of bounds" );
 
         return ((mail_outbox*)this)[-(int)id];
     }

References __TBB_ASSERT, int, and tbb::internal::arena_base::my_num_slots.

Referenced by arena(), tbb::internal::generic_scheduler::attach_mailbox(), free_arena(), and tbb::internal::generic_scheduler::prepare_for_spawning().

Here is the caller graph for this function:

◆ num_arena_slots()

static int unsigned tbb::internal::arena::num_arena_slots ( unsigned num_slots )

inlinestatic

Definition at line 182 of file arena.h.

                                                                {
         return max(2u, num_slots);
     }

References tbb::internal::max().

Referenced by allocate_arena(), arena(), and tbb::interface7::internal::task_arena_base::internal_attach().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ num_workers_active()

unsigned tbb::internal::arena::num_workers_active ( )

inline

The number of workers active in the arena.

Definition at line 220 of file arena.h.

                                    {
         return my_references >> ref_external_bits;
     }

References tbb::internal::arena_base::my_references, and ref_external_bits.

Referenced by tbb::internal::market::arena_in_need(), and process().

Here is the caller graph for this function:

◆ occupy_free_slot()

template<bool as_worker>

size_t tbb::internal::arena::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, returns out_of_arena.

Definition at line 90 of file arena.cpp.

                                                      {
     // Firstly, masters try to occupy reserved slots
     size_t index = as_worker ? out_of_arena : occupy_free_slot_in_range( s, 0, my_num_reserved_slots );
     if ( index == out_of_arena ) {
         // Secondly, all threads try to occupy all non-reserved slots
         index = occupy_free_slot_in_range( s, my_num_reserved_slots, my_num_slots );
         // Likely this arena is already saturated
         if ( index == out_of_arena )
             return out_of_arena;
     }
 
     ITT_NOTIFY(sync_acquired, my_slots + index);
     atomic_update( my_limit, (unsigned)(index + 1), std::less<unsigned>() );
     return index;
 }

References tbb::internal::atomic_update(), ITT_NOTIFY, tbb::internal::arena_base::my_limit, tbb::internal::arena_base::my_num_reserved_slots, tbb::internal::arena_base::my_num_slots, my_slots, occupy_free_slot_in_range(), out_of_arena, and s.

Referenced by process().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ occupy_free_slot_in_range()

size_t tbb::internal::arena::occupy_free_slot_in_range	(	generic_scheduler &	s,
		size_t	lower,
		size_t	upper
	)

Tries to occupy a slot in the specified range.

Definition at line 75 of file arena.cpp.

                                                                                           {
     if ( lower >= upper ) return out_of_arena;
     // Start search for an empty slot from the one we occupied the last time
     size_t index = s.my_arena_index;
     if ( index < lower || index >= upper ) index = s.my_random.get() % (upper - lower) + lower;
     __TBB_ASSERT( index >= lower && index < upper, NULL );
     // Find a free slot
     for ( size_t i = index; i < upper; ++i )
         if ( occupy_slot(my_slots[i].my_scheduler, s) ) return i;
     for ( size_t i = lower; i < index; ++i )
         if ( occupy_slot(my_slots[i].my_scheduler, s) ) return i;
     return out_of_arena;
 }

References __TBB_ASSERT, my_slots, tbb::internal::occupy_slot(), out_of_arena, and s.

Referenced by occupy_free_slot().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ on_thread_leaving()

template<unsigned ref_param>

void tbb::internal::arena::on_thread_leaving ( )

inline

Notification that worker or master leaves its arena.

Definition at line 287 of file arena.h.

                                        {
     //
     // Implementation of arena destruction synchronization logic contained various
     // bugs/flaws at the different stages of its evolution, so below is a detailed
     // description of the issues taken into consideration in the framework of the
     // current design.
     //
     // In case of using fire-and-forget tasks (scheduled via task::enqueue())
     // master thread is allowed to leave its arena before all its work is executed,
     // and market may temporarily revoke all workers from this arena. Since revoked
     // workers never attempt to reset arena state to EMPTY and cancel its request
     // to RML for threads, the arena object is destroyed only when both the last
     // thread is leaving it and arena's state is EMPTY (that is its master thread
     // left and it does not contain any work).
     // Thus resetting arena to EMPTY state (as earlier TBB versions did) should not
     // be done here (or anywhere else in the master thread to that matter); doing so
     // can result either in arena's premature destruction (at least without
     // additional costly checks in workers) or in unnecessary arena state changes
     // (and ensuing workers migration).
     //
     // A worker that checks for work presence and transitions arena to the EMPTY
     // state (in snapshot taking procedure arena::is_out_of_work()) updates
     // arena::my_pool_state first and only then arena::my_num_workers_requested.
     // So the check for work absence must be done against the latter field.
     //
     // In a time window between decrementing the active threads count and checking
     // if there is an outstanding request for workers. New worker thread may arrive,
     // finish remaining work, set arena state to empty, and leave decrementing its
     // refcount and destroying. Then the current thread will destroy the arena
     // the second time. To preclude it a local copy of the outstanding request
     // value can be stored before decrementing active threads count.
     //
     // But this technique may cause two other problem. When the stored request is
     // zero, it is possible that arena still has threads and they can generate new
     // tasks and thus re-establish non-zero requests. Then all the threads can be
     // revoked (as described above) leaving this thread the last one, and causing
     // it to destroy non-empty arena.
     //
     // The other problem takes place when the stored request is non-zero. Another
     // thread may complete the work, set arena state to empty, and leave without
     // arena destruction before this thread decrements the refcount. This thread
     // cannot destroy the arena either. Thus the arena may be "orphaned".
     //
     // In both cases we cannot dereference arena pointer after the refcount is
     // decremented, as our arena may already be destroyed.
     //
     // If this is the master thread, the market is protected by refcount to it.
     // In case of workers market's liveness is ensured by the RML connection
     // rundown protocol, according to which the client (i.e. the market) lives
     // until RML server notifies it about connection termination, and this
     // notification is fired only after all workers return into RML.
     //
     // Thus if we decremented refcount to zero we ask the market to check arena
     // state (including the fact if it is alive) under the lock.
     //
     uintptr_t aba_epoch = my_aba_epoch;
     market* m = my_market;
     __TBB_ASSERT(my_references >= ref_param, "broken arena reference counter");
 #if __TBB_STATISTICS_EARLY_DUMP
     // While still holding a reference to the arena, compute how many external references are left.
     // If just one, dump statistics.
     if ( modulo_power_of_two(my_references,ref_worker)==ref_param ) // may only be true with ref_external
         GATHER_STATISTIC( dump_arena_statistics() );
 #endif
 #if __TBB_ENQUEUE_ENFORCED_CONCURRENCY
     // When there is no workers someone must free arena, as
     // without workers, no one calls is_out_of_work().
     // Skip workerless arenas because they have no demand for workers.
     // TODO: consider more strict conditions for the cleanup,
     // because it can create the demand of workers,
     // but the arena can be already empty (and so ready for destroying)
     if( ref_param==ref_external && my_num_slots != my_num_reserved_slots
         && 0 == m->my_num_workers_soft_limit && my_concurrency_mode==cm_normal ) {
         bool is_out = false;
         for (int i=0; i<num_priority_levels; i++) {
             is_out = is_out_of_work();
             if (is_out)
                 break;
         }
         // We expect, that in worst case it's enough to have num_priority_levels-1
         // calls to restore priorities and and yet another is_out_of_work() to conform
         // that no work was found. But as market::set_active_num_workers() can be called
         // concurrently, can't guarantee last is_out_of_work() return true.
     }
 #endif
     if ( (my_references -= ref_param ) == 0 )
         m->try_destroy_arena( this, aba_epoch );
 }

References __TBB_ASSERT, GATHER_STATISTIC, is_out_of_work(), tbb::internal::modulo_power_of_two(), tbb::internal::arena_base::my_aba_epoch, tbb::internal::arena_base::my_market, tbb::internal::arena_base::my_num_reserved_slots, tbb::internal::arena_base::my_num_slots, tbb::internal::market::my_num_workers_soft_limit, tbb::internal::arena_base::my_references, tbb::internal::num_priority_levels, ref_external, ref_worker, and tbb::internal::market::try_destroy_arena().

Referenced by tbb::internal::generic_scheduler::cleanup_master(), and tbb::interface7::internal::task_arena_base::internal_initialize().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ process()

void tbb::internal::arena::process ( generic_scheduler & s )

Registers the worker with the arena and enters TBB scheduler dispatch loop.

Definition at line 106 of file arena.cpp.

                                           {
     __TBB_ASSERT( is_alive(my_guard), NULL );
     __TBB_ASSERT( governor::is_set(&s), NULL );
     __TBB_ASSERT( s.my_innermost_running_task == s.my_dummy_task, NULL );
     __TBB_ASSERT( s.worker_outermost_level(), NULL );
 
     __TBB_ASSERT( my_num_slots > 1, NULL );
 
     size_t index = occupy_free_slot</*as_worker*/true>( s );
     if ( index == out_of_arena )
         goto quit;
 
     __TBB_ASSERT( index >= my_num_reserved_slots, "Workers cannot occupy reserved slots" );
     s.attach_arena( this, index, /*is_master*/false );
 
 #if !__TBB_FP_CONTEXT
     my_cpu_ctl_env.set_env();
 #endif
 
 #if __TBB_ARENA_OBSERVER
     __TBB_ASSERT( !s.my_last_local_observer, "There cannot be notified local observers when entering arena" );
     my_observers.notify_entry_observers( s.my_last_local_observer, /*worker=*/true );
 #endif /* __TBB_ARENA_OBSERVER */
 
     // Task pool can be marked as non-empty if the worker occupies the slot left by a master.
     if ( s.my_arena_slot->task_pool != EmptyTaskPool ) {
         __TBB_ASSERT( s.my_inbox.is_idle_state(false), NULL );
         s.local_wait_for_all( *s.my_dummy_task, NULL );
         __TBB_ASSERT( s.my_inbox.is_idle_state(true), NULL );
     }
 
     for ( ;; ) {
         __TBB_ASSERT( s.my_innermost_running_task == s.my_dummy_task, NULL );
         __TBB_ASSERT( s.worker_outermost_level(), NULL );
         __TBB_ASSERT( is_alive(my_guard), NULL );
         __TBB_ASSERT( s.is_quiescent_local_task_pool_reset(),
                       "Worker cannot leave arena while its task pool is not reset" );
         __TBB_ASSERT( s.my_arena_slot->task_pool == EmptyTaskPool, "Empty task pool is not marked appropriately" );
         // This check prevents relinquishing more than necessary workers because
         // of the non-atomicity of the decision making procedure
         if ( num_workers_active() > my_num_workers_allotted
 #if __TBB_ENQUEUE_ENFORCED_CONCURRENCY
              || recall_by_mandatory_request()
 #endif
             )
             break;
         // Try to steal a task.
         // Passing reference count is technically unnecessary in this context,
         // but omitting it here would add checks inside the function.
         task* t = s.receive_or_steal_task( __TBB_ISOLATION_ARG( s.my_dummy_task->prefix().ref_count, no_isolation ) );
         if (t) {
             // A side effect of receive_or_steal_task is that my_innermost_running_task can be set.
             // But for the outermost dispatch loop it has to be a dummy task.
             s.my_innermost_running_task = s.my_dummy_task;
             s.local_wait_for_all(*s.my_dummy_task,t);
         }
     }
 #if __TBB_ARENA_OBSERVER
     my_observers.notify_exit_observers( s.my_last_local_observer, /*worker=*/true );
     s.my_last_local_observer = NULL;
 #endif /* __TBB_ARENA_OBSERVER */
 #if __TBB_TASK_PRIORITY
     if ( s.my_offloaded_tasks )
         orphan_offloaded_tasks( s );
 #endif /* __TBB_TASK_PRIORITY */
 #if __TBB_STATISTICS
     ++s.my_counters.arena_roundtrips;
     *my_slots[index].my_counters += s.my_counters;
     s.my_counters.reset();
 #endif /* __TBB_STATISTICS */
     __TBB_store_with_release( my_slots[index].my_scheduler, (generic_scheduler*)NULL );
     s.my_arena_slot = 0; // detached from slot
     s.my_inbox.detach();
     __TBB_ASSERT( s.my_inbox.is_idle_state(true), NULL );
     __TBB_ASSERT( s.my_innermost_running_task == s.my_dummy_task, NULL );
     __TBB_ASSERT( s.worker_outermost_level(), NULL );
     __TBB_ASSERT( is_alive(my_guard), NULL );
 quit:
     // In contrast to earlier versions of TBB (before 3.0 U5) now it is possible
     // that arena may be temporarily left unpopulated by threads. See comments in
     // arena::on_thread_leaving() for more details.
     on_thread_leaving<ref_worker>();
 }

References __TBB_ASSERT, __TBB_ENQUEUE_ENFORCED_CONCURRENCY, __TBB_ISOLATION_ARG, tbb::internal::__TBB_store_with_release(), EmptyTaskPool, tbb::internal::governor::is_set(), tbb::internal::arena_base::my_cpu_ctl_env, tbb::internal::arena_base::my_num_reserved_slots, tbb::internal::arena_base::my_num_slots, tbb::internal::arena_base::my_num_workers_allotted, my_slots, tbb::internal::no_isolation, num_workers_active(), occupy_free_slot(), out_of_arena, s, and tbb::internal::cpu_ctl_env::set_env().

Referenced by tbb::internal::market::process().

Here is the call graph for this function:

Here is the caller graph for this function:

◆ restore_priority_if_need()

void tbb::internal::arena::restore_priority_if_need ( )

private

If enqueued tasks found, restore arena priority and task presence status.

Definition at line 377 of file arena.cpp.

                                      {
     // Check for the presence of enqueued tasks "lost" on some of
     // priority levels because updating arena priority and switching
     // arena into "populated" (FULL) state happen non-atomically.
     // Imposing atomicity would require task::enqueue() to use a lock,
     // which is unacceptable.
     if ( has_enqueued_tasks() ) {
         advertise_new_work<work_enqueued>();
 #if __TBB_TASK_PRIORITY
         // update_arena_priority() expects non-zero arena::my_num_workers_requested,
         // so must be called after advertise_new_work<work_enqueued>()
         for ( int p = 0; p < num_priority_levels; ++p )
             if ( !my_task_stream.empty(p) ) {
                 if ( p < my_bottom_priority || p > my_top_priority )
                     my_market->update_arena_priority(*this, p);
             }
 #endif
     }
 }

References tbb::internal::task_stream< Levels >::empty(), has_enqueued_tasks(), tbb::internal::arena_base::my_market, tbb::internal::arena_base::my_task_stream, tbb::internal::num_priority_levels, and p.

Referenced by advertise_new_work(), and is_out_of_work().

Here is the call graph for this function:

Here is the caller graph for this function:

Member Data Documentation

◆ my_slots

arena_slot tbb::internal::arena::my_slots[1]

Must be the last data field

Definition at line 283 of file arena.h.

Referenced by tbb::internal::generic_scheduler::acquire_task_pool(), arena(), tbb::internal::generic_scheduler::attach_arena(), tbb::internal::generic_scheduler::cleanup_master(), tbb::internal::market::detach_arena(), free_arena(), is_out_of_work(), tbb::internal::generic_scheduler::leave_task_pool(), tbb::internal::generic_scheduler::nested_arena_exit(), occupy_free_slot(), occupy_free_slot_in_range(), process(), and tbb::internal::generic_scheduler::publish_task_pool().

◆ out_of_arena

const size_t tbb::internal::arena::out_of_arena = ~size_t(0)

static

Definition at line 275 of file arena.h.

Referenced by tbb::interface7::internal::task_arena_base::internal_execute(), occupy_free_slot(), occupy_free_slot_in_range(), and process().

◆ ref_external

const unsigned tbb::internal::arena::ref_external = 1

static

Reference increment values for externals and workers.

Definition at line 213 of file arena.h.

Referenced by arena(), tbb::internal::generic_scheduler::cleanup_master(), tbb::interface7::internal::task_arena_base::internal_attach(), tbb::interface7::internal::task_arena_base::internal_initialize(), tbb::interface7::internal::task_arena_base::internal_terminate(), and on_thread_leaving().

◆ ref_external_bits

const unsigned tbb::internal::arena::ref_external_bits = 12

static

The number of least significant bits for external references.

Definition at line 210 of file arena.h.

Referenced by num_workers_active().

◆ ref_worker

const unsigned tbb::internal::arena::ref_worker = 1<<ref_external_bits

static

Definition at line 214 of file arena.h.

Referenced by tbb::internal::market::arena_in_need(), and on_thread_leaving().

◆ SNAPSHOT_EMPTY

const pool_state_t tbb::internal::arena::SNAPSHOT_EMPTY = 0

static

No tasks to steal since last snapshot was taken.

Definition at line 204 of file arena.h.

Referenced by advertise_new_work(), free_arena(), tbb::interface7::internal::task_arena_base::internal_wait(), is_out_of_work(), tbb::internal::market::try_destroy_arena(), and tbb::internal::generic_scheduler::wait_until_empty().

◆ SNAPSHOT_FULL

const pool_state_t tbb::internal::arena::SNAPSHOT_FULL = pool_state_t(-1)

static

At least one task has been offered for stealing since the last snapshot started.

Definition at line 207 of file arena.h.

Referenced by advertise_new_work(), is_busy_or_empty(), and is_out_of_work().

The documentation for this class was generated from the following files:

Public Types

Public Member Functions

Static Public Member Functions

Public Attributes

Static Public Attributes

Private Member Functions

Detailed Description

Member Typedef Documentation

◆ base_type

◆ pool_state_t

Member Enumeration Documentation

◆ new_work_type

Constructor & Destructor Documentation

◆ arena()

Member Function Documentation

◆ advertise_new_work()

◆ allocate_arena()

◆ allocation_size()

◆ enqueue_task()

◆ free_arena()

◆ has_enqueued_tasks()

◆ is_busy_or_empty()

◆ is_out_of_work()

◆ mailbox()

◆ num_arena_slots()

◆ num_workers_active()

◆ occupy_free_slot()

◆ occupy_free_slot_in_range()

◆ on_thread_leaving()

◆ process()

◆ restore_priority_if_need()

Member Data Documentation

◆ my_slots

◆ out_of_arena

◆ ref_external

◆ ref_external_bits

◆ ref_worker

◆ SNAPSHOT_EMPTY

◆ SNAPSHOT_FULL