tbb::internal::concurrent_vector_base_v3::helper Class Reference

Inheritance diagram for tbb::internal::concurrent_vector_base_v3::helper:

Collaboration diagram for tbb::internal::concurrent_vector_base_v3::helper:

Classes
struct	destroy_body
struct	init_body
	TODO: turn into lambda functions when available. More...
struct	safe_init_body
struct	segment_not_used_predicate

Public Member Functions
	helper (segment_t *segments, size_type fb, size_type esize, size_type index, size_type s, size_type f) throw ()
void	first_segment () throw ()
void	next_segment () throw ()
template<typename F >
size_type	apply (const F &func)
segment_value_t	get_segment_value (size_type index, bool wait)
	~helper ()
void	cleanup ()
	Out of line code to assists destructor in infrequent cases. More...

Static Public Member Functions
static bool	incompact_predicate (size_type size)
static size_type	find_segment_end (const concurrent_vector_base_v3 &v)
static void	assign_first_segment_if_necessary (concurrent_vector_base_v3 &v, segment_index_t k)
	assign first segment size. k - is index of last segment to be allocated, not a count of segments More...
static void *	allocate_segment (concurrent_vector_base_v3 &v, size_type n)
template<typename argument_type >
static void	publish_segment (segment_t &s, argument_type rhs)
	Publish segment so other threads can see it. More...
static size_type	enable_segment (concurrent_vector_base_v3 &v, size_type k, size_type element_size, bool mark_as_not_used_on_failure=false)
static void	extend_table_if_necessary (concurrent_vector_base_v3 &v, size_type k, size_type start)
static void	extend_segment_table (concurrent_vector_base_v3 &v, size_type start)
static segment_t &	acquire_segment (concurrent_vector_base_v3 &v, size_type index, size_type element_size, bool owner)

Public Attributes
segment_t *	table
size_type	first_block
size_type	k
size_type	sz
size_type	start
size_type	finish
size_type	element_size

Static Public Attributes
static const size_type	page_size = 4096
	memory page size More...

Additional Inherited Members
Private Member Functions inherited from tbb::internal::no_assign
void	operator= (const no_assign &)=delete
	no_assign (const no_assign &)=default
	no_assign ()=default

Detailed Description

Definition at line 40 of file concurrent_vector.cpp.

Constructor & Destructor Documentation

helper()

tbb::internal::concurrent_vector_base_v3::helper::helper ( segment_t *  segments, size_type  fb, size_type  esize, size_type  index, size_type  s, size_type  f  ) throw ( )

inline

Definition at line 124 of file concurrent_vector.cpp.

        : table(segments), first_block(fb), k(index), sz(0), start(s), finish(f), element_size(esize) {}

~helper()

tbb::internal::concurrent_vector_base_v3::helper::~helper ( )

inline

Definition at line 160 of file concurrent_vector.cpp.

              {
        if( sz >= finish ) return; // the work is done correctly
        cleanup();
    }

References cleanup(), finish, and sz.

Here is the call graph for this function:

Member Function Documentation

acquire_segment()

static segment_t& tbb::internal::concurrent_vector_base_v3::helper::acquire_segment ( concurrent_vector_base_v3 &  v, size_type  index, size_type  element_size, bool  owner  )

inlinestatic

Definition at line 104 of file concurrent_vector.cpp.

                                                                                                                                {
        segment_t &s = v.my_segment[index]; // TODO: pass v.my_segment as argument
        if( s.load<acquire>() == segment_not_used() ) { // do not check for segment_allocation_failed state
            if( owner ) {
                enable_segment( v, index, element_size );
            } else {
                ITT_NOTIFY(sync_prepare, &s);
                spin_wait_while(segment_not_used_predicate(s));
                ITT_NOTIFY(sync_acquired, &s);
            }
        } else {
            ITT_NOTIFY(sync_acquired, &s);
        }
        enforce_segment_allocated(s.load<relaxed>()); //it's hard to recover correctly after segment_allocation_failed state
        return s;
    }

References tbb::acquire, element_size, enable_segment(), tbb::internal::concurrent_vector_base_v3::enforce_segment_allocated, ITT_NOTIFY, tbb::internal::concurrent_vector_base_v3::my_segment, tbb::relaxed, s, and tbb::internal::spin_wait_while().

Referenced by tbb::internal::concurrent_vector_base_v3::internal_grow(), and tbb::internal::concurrent_vector_base_v3::internal_push_back().

Here is the call graph for this function:

Here is the caller graph for this function:

allocate_segment()

static void* tbb::internal::concurrent_vector_base_v3::helper::allocate_segment ( concurrent_vector_base_v3 &  v, size_type  n  )

inlinestatic

Definition at line 75 of file concurrent_vector.cpp.

                                                                                    {
        void *ptr = v.vector_allocator_ptr(v, n);
        if(!ptr) throw_exception(eid_bad_alloc); // check for bad allocation, throw exception
        return ptr;
    }

References tbb::internal::eid_bad_alloc, tbb::internal::throw_exception(), and tbb::internal::concurrent_vector_base_v3::vector_allocator_ptr.

Referenced by tbb::internal::concurrent_vector_base_v3::internal_compact().

Here is the call graph for this function:

Here is the caller graph for this function:

apply()

template<typename F >

size_type tbb::internal::concurrent_vector_base_v3::helper::apply ( const F &  func )

inline

Definition at line 141 of file concurrent_vector.cpp.

                                          {
        first_segment();
        while( sz < finish ) { // work for more than one segment
            //TODO: remove extra load() of table[k] inside func
            func( table[k], table[k].load<relaxed>().pointer<char>() + element_size*start, sz - start );
            next_segment();
        }
        func( table[k], table[k].load<relaxed>().pointer<char>() + element_size*start, finish - start );
        return k;
    }

References element_size, finish, first_segment(), k, next_segment(), start, sz, and table.

Referenced by tbb::internal::concurrent_vector_base_v3::internal_clear(), tbb::internal::concurrent_vector_base_v3::internal_compact(), tbb::internal::concurrent_vector_base_v3::internal_grow(), and tbb::internal::concurrent_vector_base_v3::internal_resize().

Here is the call graph for this function:

Here is the caller graph for this function:

assign_first_segment_if_necessary()

static void tbb::internal::concurrent_vector_base_v3::helper::assign_first_segment_if_necessary ( concurrent_vector_base_v3 &  v, segment_index_t  k  )

inlinestatic

assign first segment size. k - is index of last segment to be allocated, not a count of segments

Definition at line 60 of file concurrent_vector.cpp.

                                                                                                          {
        if( !v.my_first_block ) {
            /* There was a suggestion to set first segment according to incompact_predicate:
            while( k && !helper::incompact_predicate(segment_size( k ) * element_size) )
                --k; // while previous vector size is compact, decrement
            // reasons to not do it:
            // * constructor(n) is not ready to accept fragmented segments
            // * backward compatibility due to that constructor
            // * current version gives additional guarantee and faster init.
            // * two calls to reserve() will give the same effect.
            */
            v.my_first_block.compare_and_swap(k+1, 0); // store number of segments
        }
    }

References k, and tbb::internal::concurrent_vector_base_v3::my_first_block.

Referenced by tbb::internal::concurrent_vector_base_v3::internal_assign(), tbb::internal::concurrent_vector_base_v3::internal_copy(), tbb::internal::concurrent_vector_base_v3::internal_grow(), and tbb::internal::concurrent_vector_base_v3::internal_reserve().

Here is the caller graph for this function:

cleanup()

void tbb::internal::concurrent_vector_base_v3::helper::cleanup

(

)

Out of line code to assists destructor in infrequent cases.

Definition at line 281 of file concurrent_vector.cpp.

                                              {
    if( !sz ) { // allocation failed, restore the table
        segment_index_t k_start = k, k_end = segment_index_of(finish-1);
        if( segment_base( k_start ) < start )
            get_segment_value(k_start++, true); // wait
        if( k_start < first_block ) {
            segment_value_t segment0 = get_segment_value(0, start>0); // wait if necessary
            if((segment0 != segment_not_used()) && !k_start ) ++k_start;
            if(segment0 != segment_allocated())
                for(; k_start < first_block && k_start <= k_end; ++k_start )
                    publish_segment(table[k_start], segment_allocation_failed());
            else for(; k_start < first_block && k_start <= k_end; ++k_start )
                    publish_segment(table[k_start], static_cast<void*>(
                        (segment0.pointer<char>()) + segment_base(k_start)*element_size) );
        }
        for(; k_start <= k_end; ++k_start ) // not in first block
            if(table[k_start].load<acquire>() == segment_not_used())
                publish_segment(table[k_start], segment_allocation_failed());
        // fill allocated items
        first_segment();
        goto recover;
    }
    while( sz <= finish ) { // there is still work for at least one segment
        next_segment();
recover:
        segment_value_t array = table[k].load<relaxed>();
        if(array == segment_allocated())
            std::memset( (array.pointer<char>()) + element_size*start, 0, ((sz<finish?sz:finish) - start)*element_size );
        else __TBB_ASSERT( array == segment_allocation_failed(), NULL );
    }
}

References __TBB_ASSERT, tbb::internal::concurrent_vector_base_v3::segment_t::load(), tbb::internal::concurrent_vector_base_v3::segment_value_t::pointer(), tbb::relaxed, tbb::internal::concurrent_vector_base_v3::segment_base(), and tbb::internal::concurrent_vector_base_v3::segment_index_of().

Referenced by ~helper().

Here is the call graph for this function:

Here is the caller graph for this function:

enable_segment()

concurrent_vector_base_v3::size_type tbb::internal::concurrent_vector_base_v3::helper::enable_segment ( concurrent_vector_base_v3 &  v, concurrent_vector_base_v3::size_type  k, concurrent_vector_base_v3::size_type  element_size, bool  mark_as_not_used_on_failure = false  )

static

Definition at line 222 of file concurrent_vector.cpp.

                                           {

    struct segment_scope_guard : no_copy{
        segment_t* my_segment_ptr;
        bool my_mark_as_not_used;
        segment_scope_guard(segment_t& segment, bool mark_as_not_used) : my_segment_ptr(&segment), my_mark_as_not_used(mark_as_not_used){}
        void dismiss(){ my_segment_ptr = 0;}
        ~segment_scope_guard(){
            if (my_segment_ptr){
                if (!my_mark_as_not_used){
                    publish_segment(*my_segment_ptr, segment_allocation_failed());
                }else{
                    publish_segment(*my_segment_ptr, segment_not_used());
                }
            }
        }
    };

    segment_t* s = v.my_segment; // TODO: optimize out as argument? Optimize accesses to my_first_block
    __TBB_ASSERT(s[k].load<relaxed>() != segment_allocated(), "concurrent operation during growth?");

    size_type size_of_enabled_segment =  segment_size(k);
    size_type size_to_allocate = size_of_enabled_segment;
    if( !k ) {
        assign_first_segment_if_necessary(v, default_initial_segments-1);
        size_of_enabled_segment =  2 ;
        size_to_allocate = segment_size(v.my_first_block);

    } else  {
        spin_wait_while_eq( v.my_first_block, segment_index_t(0) );
    }

    if( k && (k < v.my_first_block)){ //no need to allocate anything
        // s[0].array is changed only once ( 0 -> !0 ) and points to uninitialized memory
        segment_value_t array0 = s[0].load<acquire>();
        if(array0 == segment_not_used()){
            // sync_prepare called only if there is a wait
            ITT_NOTIFY(sync_prepare, &s[0]);
            spin_wait_while( segment_not_used_predicate(s[0]));
            array0 = s[0].load<acquire>();
        }
        ITT_NOTIFY(sync_acquired, &s[0]);

        segment_scope_guard k_segment_guard(s[k], false);
        enforce_segment_allocated(array0); // initial segment should be allocated
        k_segment_guard.dismiss();

        publish_segment( s[k],
            static_cast<void*>(array0.pointer<char>() + segment_base(k)*element_size )
        );
    } else {
        segment_scope_guard k_segment_guard(s[k], mark_as_not_used_on_failure);
        publish_segment(s[k], allocate_segment(v, size_to_allocate));
        k_segment_guard.dismiss();
    }
    return size_of_enabled_segment;
}

References __TBB_ASSERT, tbb::acquire, tbb::internal::concurrent_vector_base_v3::default_initial_segments, tbb::internal::concurrent_vector_base_v3::enforce_segment_allocated, ITT_NOTIFY, tbb::internal::concurrent_vector_base_v3::my_first_block, tbb::internal::concurrent_vector_base_v3::my_segment, tbb::internal::concurrent_vector_base_v3::segment_value_t::pointer(), s, tbb::internal::concurrent_vector_base_v3::segment_base(), tbb::internal::concurrent_vector_base_v3::segment_size(), tbb::internal::spin_wait_while(), and tbb::internal::spin_wait_while_eq().

Referenced by acquire_segment(), tbb::internal::concurrent_vector_base_v3::internal_assign(), tbb::internal::concurrent_vector_base_v3::internal_copy(), and tbb::internal::concurrent_vector_base_v3::internal_reserve().

Here is the call graph for this function:

Here is the caller graph for this function:

extend_segment_table()

void tbb::internal::concurrent_vector_base_v3::helper::extend_segment_table ( concurrent_vector_base_v3 &  v, concurrent_vector_base_v3::size_type  start  )

static

Definition at line 196 of file concurrent_vector.cpp.

                                                                                                                                 {
    if( start > segment_size(pointers_per_short_table) ) start = segment_size(pointers_per_short_table);
    // If other threads are trying to set pointers in the short segment, wait for them to finish their
    // assignments before we copy the short segment to the long segment. Note: grow_to_at_least depends on it
    for( segment_index_t i = 0; segment_base(i) < start && v.my_segment == v.my_storage; i++ ){
        if(v.my_storage[i].load<relaxed>() == segment_not_used()) {
            ITT_NOTIFY(sync_prepare, &v.my_storage[i]);
            atomic_backoff backoff(true);
            while( v.my_segment == v.my_storage && (v.my_storage[i].load<relaxed>() == segment_not_used()) )
                backoff.pause();
            ITT_NOTIFY(sync_acquired, &v.my_storage[i]);
        }
    }
    if( v.my_segment != v.my_storage ) return;

    segment_t* new_segment_table = (segment_t*)NFS_Allocate( pointers_per_long_table, sizeof(segment_t), NULL );
    __TBB_ASSERT(new_segment_table, "NFS_Allocate should throws exception if it cannot allocate the requested storage, and not returns zero pointer" );
    std::uninitialized_fill_n(new_segment_table,size_t(pointers_per_long_table),segment_t()); //init newly allocated table
   //TODO: replace with static assert
    __TBB_STATIC_ASSERT(pointers_per_long_table >= pointers_per_short_table, "size of the big table should be not lesser than of the small one, as we copy values to it" );
    std::copy(v.my_storage, v.my_storage+pointers_per_short_table, new_segment_table);//copy values from old table, here operator= of segment_t is used
    if( v.my_segment.compare_and_swap( new_segment_table, v.my_storage ) != v.my_storage )
        NFS_Free( new_segment_table );
    // else TODO: add ITT_NOTIFY signals for v.my_segment?
}

References __TBB_ASSERT, __TBB_STATIC_ASSERT, ITT_NOTIFY, tbb::internal::concurrent_vector_base_v3::segment_t::load(), tbb::internal::concurrent_vector_base_v3::my_segment, tbb::internal::concurrent_vector_base_v3::my_storage, tbb::internal::NFS_Allocate(), tbb::internal::NFS_Free(), tbb::internal::atomic_backoff::pause(), tbb::internal::concurrent_vector_base_v3::pointers_per_long_table, tbb::internal::concurrent_vector_base_v3::pointers_per_short_table, tbb::relaxed, tbb::internal::concurrent_vector_base_v3::segment_base(), tbb::internal::concurrent_vector_base_v3::segment_size(), and start.

Referenced by extend_table_if_necessary().

Here is the call graph for this function:

Here is the caller graph for this function:

extend_table_if_necessary()

static void tbb::internal::concurrent_vector_base_v3::helper::extend_table_if_necessary ( concurrent_vector_base_v3 &  v, size_type  k, size_type  start  )

inlinestatic

Definition at line 92 of file concurrent_vector.cpp.

                                                                                                              {
        if(k >= pointers_per_short_table && v.my_segment == v.my_storage)
            extend_segment_table(v, start );
    }

References extend_segment_table(), k, tbb::internal::concurrent_vector_base_v3::my_segment, tbb::internal::concurrent_vector_base_v3::my_storage, tbb::internal::concurrent_vector_base_v3::pointers_per_short_table, and start.

Referenced by tbb::internal::concurrent_vector_base_v3::internal_assign(), tbb::internal::concurrent_vector_base_v3::internal_copy(), tbb::internal::concurrent_vector_base_v3::internal_grow(), tbb::internal::concurrent_vector_base_v3::internal_push_back(), and tbb::internal::concurrent_vector_base_v3::internal_reserve().

Here is the call graph for this function:

Here is the caller graph for this function:

find_segment_end()

static size_type tbb::internal::concurrent_vector_base_v3::helper::find_segment_end ( const concurrent_vector_base_v3 &  v )

inlinestatic

Definition at line 49 of file concurrent_vector.cpp.

                                                                                 {
        segment_t *s = v.my_segment;
        segment_index_t u = s==v.my_storage? pointers_per_short_table : pointers_per_long_table;
        segment_index_t k = 0;
        while( k < u && (s[k].load<relaxed>()==segment_allocated() ))
            ++k;
        return k;
    }

References k, tbb::internal::concurrent_vector_base_v3::my_segment, tbb::internal::concurrent_vector_base_v3::my_storage, tbb::internal::concurrent_vector_base_v3::pointers_per_long_table, tbb::internal::concurrent_vector_base_v3::pointers_per_short_table, and s.

Referenced by tbb::internal::concurrent_vector_base_v3::internal_capacity(), tbb::internal::concurrent_vector_base_v3::internal_clear(), tbb::internal::concurrent_vector_base_v3::internal_compact(), and tbb::internal::concurrent_vector_base_v3::internal_reserve().

Here is the caller graph for this function:

first_segment()

void tbb::internal::concurrent_vector_base_v3::helper::first_segment ( ) throw ( )

inline

Definition at line 126 of file concurrent_vector.cpp.

                                        {
        __TBB_ASSERT( start <= finish, NULL );
        __TBB_ASSERT( first_block || !finish, NULL );
        if( k < first_block ) k = 0; // process solid segment at a time
        size_type base = segment_base( k );
        __TBB_ASSERT( base <= start, NULL );
        finish -= base; start -= base; // rebase as offsets from segment k
        sz = k ? base : segment_size( first_block ); // sz==base for k>0
    }

References __TBB_ASSERT, finish, first_block, k, tbb::internal::concurrent_vector_base_v3::segment_base(), tbb::internal::concurrent_vector_base_v3::segment_size(), start, and sz.

Referenced by apply().

Here is the call graph for this function:

Here is the caller graph for this function:

get_segment_value()

segment_value_t tbb::internal::concurrent_vector_base_v3::helper::get_segment_value ( size_type  index, bool  wait  )

inline

Definition at line 151 of file concurrent_vector.cpp.

                                                                         {
        segment_t &s = table[index];
        if( wait && (s.load<acquire>() == segment_not_used()) ) {
            ITT_NOTIFY(sync_prepare, &s);
            spin_wait_while(segment_not_used_predicate(s));
            ITT_NOTIFY(sync_acquired, &s);
        }
        return s.load<relaxed>();
    }

References tbb::acquire, ITT_NOTIFY, tbb::relaxed, s, tbb::internal::spin_wait_while(), and table.

Here is the call graph for this function:

incompact_predicate()

static bool tbb::internal::concurrent_vector_base_v3::helper::incompact_predicate ( size_type  size )

inlinestatic

Definition at line 45 of file concurrent_vector.cpp.

                                                           { // assert size != 0, see source/test/test_vector_layout.cpp
        return size < page_size || ((size-1)%page_size < page_size/2 && size < page_size * 128); // for more details
    }

References page_size, and size.

Referenced by tbb::internal::concurrent_vector_base_v3::internal_compact().

Here is the caller graph for this function:

next_segment()

void tbb::internal::concurrent_vector_base_v3::helper::next_segment ( ) throw ( )

inline

Definition at line 135 of file concurrent_vector.cpp.

                                       {
        finish -= sz; start = 0; // offsets from next segment
        if( !k ) k = first_block;
        else { ++k; sz = segment_size( k ); }
    }

References finish, first_block, k, tbb::internal::concurrent_vector_base_v3::segment_size(), start, and sz.

Referenced by apply().

Here is the call graph for this function:

Here is the caller graph for this function:

publish_segment()

template<typename argument_type >

static void tbb::internal::concurrent_vector_base_v3::helper::publish_segment ( segment_t &  s, argument_type  rhs  )

inlinestatic

Publish segment so other threads can see it.

Definition at line 83 of file concurrent_vector.cpp.

                                                                          {
        // see also itt_store_pointer_with_release_v3()
        ITT_NOTIFY( sync_releasing, &s );
        s.store<release>(rhs);
    }

References ITT_NOTIFY, tbb::release, s, and sync_releasing.

Member Data Documentation

element_size

size_type tbb::internal::concurrent_vector_base_v3::helper::element_size

Definition at line 123 of file concurrent_vector.cpp.

Referenced by acquire_segment(), and apply().

finish

size_type tbb::internal::concurrent_vector_base_v3::helper::finish

Definition at line 123 of file concurrent_vector.cpp.

Referenced by apply(), first_segment(), next_segment(), and ~helper().

first_block

size_type tbb::internal::concurrent_vector_base_v3::helper::first_block

Definition at line 123 of file concurrent_vector.cpp.

Referenced by first_segment(), tbb::internal::concurrent_vector_base_v3::internal_grow(), and next_segment().

k

size_type tbb::internal::concurrent_vector_base_v3::helper::k

Definition at line 123 of file concurrent_vector.cpp.

Referenced by apply(), assign_first_segment_if_necessary(), extend_table_if_necessary(), find_segment_end(), first_segment(), and next_segment().

page_size

const size_type tbb::internal::concurrent_vector_base_v3::helper::page_size = 4096

static

memory page size

Definition at line 43 of file concurrent_vector.cpp.

Referenced by incompact_predicate().

start

size_type tbb::internal::concurrent_vector_base_v3::helper::start

Definition at line 123 of file concurrent_vector.cpp.

Referenced by apply(), extend_segment_table(), extend_table_if_necessary(), first_segment(), and next_segment().

sz

size_type tbb::internal::concurrent_vector_base_v3::helper::sz

Definition at line 123 of file concurrent_vector.cpp.

Referenced by apply(), first_segment(), next_segment(), and ~helper().

table

segment_t* tbb::internal::concurrent_vector_base_v3::helper::table

Definition at line 122 of file concurrent_vector.cpp.

Referenced by apply(), and get_segment_value().

---

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

• concurrent_vector.cpp