| /* |
| Copyright 2005-2010 Intel Corporation. All Rights Reserved. |
| |
| This file is part of Threading Building Blocks. |
| |
| Threading Building Blocks is free software; you can redistribute it |
| and/or modify it under the terms of the GNU General Public License |
| version 2 as published by the Free Software Foundation. |
| |
| Threading Building Blocks is distributed in the hope that it will be |
| useful, but WITHOUT ANY WARRANTY; without even the implied warranty |
| of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| GNU General Public License for more details. |
| |
| You should have received a copy of the GNU General Public License |
| along with Threading Building Blocks; if not, write to the Free Software |
| Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA |
| |
| As a special exception, you may use this file as part of a free software |
| library without restriction. Specifically, if other files instantiate |
| templates or use macros or inline functions from this file, or you compile |
| this file and link it with other files to produce an executable, this |
| file does not by itself cause the resulting executable to be covered by |
| the GNU General Public License. This exception does not however |
| invalidate any other reasons why the executable file might be covered by |
| the GNU General Public License. |
| */ |
| |
| // Put tbb/atomic.h first, so if it is missing a prerequisite header, we find out about it. |
| // The tests here do *not* test for atomicity, just serial correctness. */ |
| |
| #include "tbb/atomic.h" |
| #include "harness_assert.h" |
| #include <string.h> // memcmp |
| |
| #if _MSC_VER && !defined(__INTEL_COMPILER) |
| // unary minus operator applied to unsigned type, result still unsigned |
| #pragma warning( push ) |
| #pragma warning( disable: 4310 ) |
| #endif |
| |
| //! Structure that holds an atomic<T> and some guard bytes around it. |
| template<typename T> |
| struct TestStruct { |
| T prefix; |
| tbb::atomic<T> counter; |
| T suffix; |
| TestStruct( T i ) : prefix(T(0x1234)), suffix(T(0x5678)) { |
| counter = i; |
| ASSERT( sizeof(*this)==3*sizeof(T), NULL ); |
| } |
| ~TestStruct() { |
| // Check for writes outside the counter. |
| ASSERT( prefix==T(0x1234), NULL ); |
| ASSERT( suffix==T(0x5678), NULL ); |
| } |
| }; |
| |
| #if _MSC_VER && !defined(__INTEL_COMPILER) |
| #pragma warning( pop ) |
| #endif |
| |
| #if defined(__INTEL_COMPILER) |
| // reference to EBX in a function requiring stack alignment |
| #pragma warning( disable: 998 ) |
| #endif |
| |
| //! Test compare_and_swap template members of class atomic<T> for memory_semantics=M |
| template<typename T,tbb::memory_semantics M> |
| void TestCompareAndSwapAcquireRelease( T i, T j, T k ) { |
| ASSERT( i!=k, "values must be distinct" ); |
| // Test compare_and_swap that should fail |
| TestStruct<T> x(i); |
| T old = x.counter.template compare_and_swap<M>( j, k ); |
| ASSERT( old==i, NULL ); |
| ASSERT( x.counter==i, "old value not retained" ); |
| // Test compare and swap that should suceed |
| old = x.counter.template compare_and_swap<M>( j, i ); |
| ASSERT( old==i, NULL ); |
| ASSERT( x.counter==j, "value not updated?" ); |
| } |
| |
| //! i, j, k must be different values |
| template<typename T> |
| void TestCompareAndSwap( T i, T j, T k ) { |
| ASSERT( i!=k, "values must be distinct" ); |
| // Test compare_and_swap that should fail |
| TestStruct<T> x(i); |
| T old = x.counter.compare_and_swap( j, k ); |
| ASSERT( old==i, NULL ); |
| ASSERT( x.counter==i, "old value not retained" ); |
| // Test compare and swap that should suceed |
| old = x.counter.compare_and_swap( j, i ); |
| ASSERT( old==i, NULL ); |
| if( x.counter==i ) { |
| ASSERT( x.counter==j, "value not updated?" ); |
| } else { |
| ASSERT( x.counter==j, "value trashed" ); |
| } |
| TestCompareAndSwapAcquireRelease<T,tbb::acquire>(i,j,k); |
| TestCompareAndSwapAcquireRelease<T,tbb::release>(i,j,k); |
| } |
| |
| //! memory_semantics variation on TestFetchAndStore |
| template<typename T, tbb::memory_semantics M> |
| void TestFetchAndStoreAcquireRelease( T i, T j ) { |
| ASSERT( i!=j, "values must be distinct" ); |
| TestStruct<T> x(i); |
| T old = x.counter.template fetch_and_store<M>( j ); |
| ASSERT( old==i, NULL ); |
| ASSERT( x.counter==j, NULL ); |
| } |
| |
| //! i and j must be different values |
| template<typename T> |
| void TestFetchAndStore( T i, T j ) { |
| ASSERT( i!=j, "values must be distinct" ); |
| TestStruct<T> x(i); |
| T old = x.counter.fetch_and_store( j ); |
| ASSERT( old==i, NULL ); |
| ASSERT( x.counter==j, NULL ); |
| TestFetchAndStoreAcquireRelease<T,tbb::acquire>(i,j); |
| TestFetchAndStoreAcquireRelease<T,tbb::release>(i,j); |
| } |
| |
| #if _MSC_VER && !defined(__INTEL_COMPILER) |
| // conversion from <bigger integer> to <smaller integer>, possible loss of data |
| // the warning seems a complete nonsense when issued for e.g. short+=short |
| #pragma warning( push ) |
| #pragma warning( disable: 4244 ) |
| #endif |
| |
| //! Test fetch_and_add members of class atomic<T> for memory_semantics=M |
| template<typename T,tbb::memory_semantics M> |
| void TestFetchAndAddAcquireRelease( T i ) { |
| TestStruct<T> x(i); |
| T actual; |
| T expected = i; |
| |
| // Test fetch_and_add member template |
| for( int j=0; j<10; ++j ) { |
| actual = x.counter.fetch_and_add(j); |
| ASSERT( actual==expected, NULL ); |
| expected += j; |
| } |
| for( int j=0; j<10; ++j ) { |
| actual = x.counter.fetch_and_add(-j); |
| ASSERT( actual==expected, NULL ); |
| expected -= j; |
| } |
| |
| // Test fetch_and_increment member template |
| ASSERT( x.counter==i, NULL ); |
| actual = x.counter.template fetch_and_increment<M>(); |
| ASSERT( actual==i, NULL ); |
| ASSERT( x.counter==T(i+1), NULL ); |
| |
| // Test fetch_and_decrement member template |
| actual = x.counter.template fetch_and_decrement<M>(); |
| ASSERT( actual==T(i+1), NULL ); |
| ASSERT( x.counter==i, NULL ); |
| } |
| |
| //! Test fetch_and_add and related operators |
| template<typename T> |
| void TestFetchAndAdd( T i ) { |
| TestStruct<T> x(i); |
| T value; |
| value = ++x.counter; |
| ASSERT( value==T(i+1), NULL ); |
| value = x.counter++; |
| ASSERT( value==T(i+1), NULL ); |
| value = x.counter--; |
| ASSERT( value==T(i+2), NULL ); |
| value = --x.counter; |
| ASSERT( value==i, NULL ); |
| T actual; |
| T expected = i; |
| for( int j=-100; j<=100; ++j ) { |
| expected += j; |
| actual = x.counter += j; |
| ASSERT( actual==expected, NULL ); |
| } |
| for( int j=-100; j<=100; ++j ) { |
| expected -= j; |
| actual = x.counter -= j; |
| ASSERT( actual==expected, NULL ); |
| } |
| // Test fetch_and_increment |
| ASSERT( x.counter==i, NULL ); |
| actual = x.counter.fetch_and_increment(); |
| ASSERT( actual==i, NULL ); |
| ASSERT( x.counter==T(i+1), NULL ); |
| |
| // Test fetch_and_decrement |
| actual = x.counter.fetch_and_decrement(); |
| ASSERT( actual==T(i+1), NULL ); |
| ASSERT( x.counter==i, NULL ); |
| x.counter = i; |
| ASSERT( x.counter==i, NULL ); |
| |
| TestFetchAndAddAcquireRelease<T,tbb::acquire>(i); |
| TestFetchAndAddAcquireRelease<T,tbb::release>(i); |
| } |
| |
| #if _MSC_VER && !defined(__INTEL_COMPILER) |
| #pragma warning( pop ) |
| #endif // warning 4244 is back |
| |
| //! A type with unknown size. |
| class IncompleteType; |
| |
| void TestFetchAndAdd( IncompleteType* ) { |
| // There are no fetch-and-add operations on a IncompleteType*. |
| } |
| void TestFetchAndAdd( void* ) { |
| // There are no fetch-and-add operations on a void*. |
| } |
| |
| void TestFetchAndAdd( bool ) { |
| // There are no fetch-and-add operations on a bool. |
| } |
| |
| template<typename T> |
| void TestConst( T i ) { |
| // Try const |
| const TestStruct<T> x(i); |
| ASSERT( memcmp( &i, &x.counter, sizeof(T) )==0, "write to atomic<T> broken?" );; |
| ASSERT( x.counter==i, "read of atomic<T> broken?" ); |
| } |
| |
| template<typename T> |
| void TestOperations( T i, T j, T k ) { |
| TestConst(i); |
| TestCompareAndSwap(i,j,k); |
| TestFetchAndStore(i,k); // Pass i,k instead of i,j, because callee requires two distinct values. |
| } |
| |
| template<typename T> |
| void TestParallel( const char* name ); |
| |
| bool ParallelError; |
| |
| template<typename T> |
| struct AlignmentChecker { |
| char c; |
| tbb::atomic<T> i; |
| }; |
| |
| #include "harness.h" |
| |
| #if _MSC_VER && !defined(__INTEL_COMPILER) |
| // unary minus operator applied to unsigned type, result still unsigned |
| #pragma warning( push ) |
| #pragma warning( disable: 4146 ) |
| #endif |
| |
| /** T is an integral type. */ |
| template<typename T> |
| void TestAtomicInteger( const char* name ) { |
| REMARK("testing atomic<%s>\n",name); |
| #if ( __linux__ && __TBB_x86_32 && __GNUC__==3 && __GNUC_MINOR__==3 ) || defined(__SUNPRO_CC) |
| // gcc 3.3 has known problem for 32-bit Linux, so only warn if there is a problem. |
| // SUNPRO_CC does have this problem as well |
| if( sizeof(T)==8 ) { |
| if( sizeof(AlignmentChecker<T>)!=2*sizeof(tbb::atomic<T>) ) { |
| REPORT("Known issue: alignment for atomic<%s> is wrong with gcc 3.3 and sunCC 5.9 2008/01/28 for IA32\n",name); |
| } |
| } else |
| #endif /* ( __linux__ && __TBB_x86_32 && __GNUC__==3 && __GNUC_MINOR__==3 ) || defined(__SUNPRO_CC) */ |
| ASSERT( sizeof(AlignmentChecker<T>)==2*sizeof(tbb::atomic<T>), NULL ); |
| TestOperations<T>(0L,T(-T(1)),T(1)); |
| for( int k=0; k<int(sizeof(long))*8-1; ++k ) { |
| TestOperations<T>(T(1L<<k),T(~(1L<<k)),T(1-(1L<<k))); |
| TestOperations<T>(T(-1L<<k),T(~(-1L<<k)),T(1-(-1L<<k))); |
| TestFetchAndAdd<T>(T(-1L<<k)); |
| } |
| TestParallel<T>( name ); |
| } |
| |
| #if _MSC_VER && !defined(__INTEL_COMPILER) |
| #pragma warning( pop ) |
| #endif |
| |
| |
| template<typename T> |
| struct Foo { |
| T x, y, z; |
| }; |
| |
| |
| template<typename T> |
| void TestIndirection() { |
| Foo<T> item; |
| tbb::atomic<Foo<T>*> pointer; |
| pointer = &item; |
| for( int k=-10; k<=10; ++k ) { |
| // Test various syntaxes for indirection to fields with non-zero offset. |
| T value1=T(), value2=T(); |
| for( size_t j=0; j<sizeof(T); ++j ) { |
| *(char*)&value1 = char(k^j); |
| *(char*)&value2 = char(k^j*j); |
| } |
| pointer->y = value1; |
| (*pointer).z = value2; |
| T result1 = (*pointer).y; |
| T result2 = pointer->z; |
| ASSERT( memcmp(&value1,&result1,sizeof(T))==0, NULL ); |
| ASSERT( memcmp(&value2,&result2,sizeof(T))==0, NULL ); |
| } |
| } |
| |
| //! Test atomic<T*> |
| template<typename T> |
| void TestAtomicPointer() { |
| REMARK("testing atomic pointer (%d)\n",int(sizeof(T))); |
| T array[1000]; |
| TestOperations<T*>(&array[500],&array[250],&array[750]); |
| TestFetchAndAdd<T*>(&array[500]); |
| TestIndirection<T>(); |
| TestParallel<T*>( "pointer" ); |
| } |
| |
| //! Test atomic<Ptr> where Ptr is a pointer to a type of unknown size |
| template<typename Ptr> |
| void TestAtomicPointerToTypeOfUnknownSize( const char* name ) { |
| REMARK("testing atomic<%s>\n",name); |
| char array[1000]; |
| TestOperations<Ptr>((Ptr)(void*)&array[500],(Ptr)(void*)&array[250],(Ptr)(void*)&array[750]); |
| TestParallel<Ptr>( name ); |
| } |
| |
| void TestAtomicBool() { |
| REMARK("testing atomic<bool>\n"); |
| TestOperations<bool>(true,true,false); |
| TestOperations<bool>(false,false,true); |
| TestParallel<bool>( "bool" ); |
| } |
| |
| enum Color {Red=0,Green=1,Blue=-1}; |
| |
| void TestAtomicEnum() { |
| REMARK("testing atomic<Color>\n"); |
| TestOperations<Color>(Red,Green,Blue); |
| TestParallel<Color>( "Color" ); |
| } |
| |
| #if !__TBB_FLOATING_POINT_BROKEN |
| template<typename T> |
| void TestAtomicFloat( const char* name ) { |
| REMARK("testing atomic<%s>\n", name ); |
| TestOperations<T>(0.5,3.25,10.75); |
| TestParallel<T>( name ); |
| } |
| #endif /* !__TBB_FLOATING_POINT_BROKEN */ |
| |
| const int numMaskedOperations = 100000; |
| const int testSpaceSize = 8; |
| int prime[testSpaceSize] = {3,5,7,11,13,17,19,23}; |
| |
| #if _MSC_VER && !defined(__INTEL_COMPILER) |
| // "possible loss of data" warning suppressed again |
| #pragma warning( push ) |
| #pragma warning( disable: 4244 ) |
| #endif |
| |
| template<typename T> |
| class TestMaskedCAS_Body: NoAssign { |
| T* test_space_uncontended; |
| T* test_space_contended; |
| public: |
| TestMaskedCAS_Body( T* _space1, T* _space2 ) : test_space_uncontended(_space1), test_space_contended(_space2) {} |
| void operator()( int my_idx ) const { |
| using tbb::internal::__TBB_MaskedCompareAndSwap; |
| const T my_prime = T(prime[my_idx]); |
| T* const my_ptr = test_space_uncontended+my_idx; |
| T old_value=0; |
| for( int i=0; i<numMaskedOperations; ++i, old_value+=my_prime ){ |
| T result; |
| // Test uncontended case |
| T new_value = old_value + my_prime; |
| // The following CAS should always fail |
| result = __TBB_MaskedCompareAndSwap<sizeof(T),T>(my_ptr,new_value,old_value-1); |
| ASSERT(result!=old_value-1, "masked CAS succeeded while it should fail"); |
| ASSERT(result==*my_ptr, "masked CAS result mismatch with real value"); |
| // The following one should succeed |
| result = __TBB_MaskedCompareAndSwap<sizeof(T),T>(my_ptr,new_value,old_value); |
| ASSERT(result==old_value && *my_ptr==new_value, "masked CAS failed while it should succeed"); |
| // The following one should fail again |
| result = __TBB_MaskedCompareAndSwap<sizeof(T),T>(my_ptr,new_value,old_value); |
| ASSERT(result!=old_value, "masked CAS succeeded while it should fail"); |
| ASSERT(result==*my_ptr, "masked CAS result mismatch with real value"); |
| // Test contended case |
| for( int j=0; j<testSpaceSize; ++j ){ |
| // try adding my_prime until success |
| T value; |
| do { |
| value = test_space_contended[j]; |
| result = __TBB_MaskedCompareAndSwap<sizeof(T),T>(test_space_contended+j,value+my_prime,value); |
| } while( result!=value ); |
| } |
| } |
| } |
| }; |
| |
| template<typename T> |
| struct intptr_as_array_of |
| { |
| static const int how_many_Ts = sizeof(intptr_t)/sizeof(T); |
| union { |
| intptr_t result; |
| T space[ how_many_Ts ]; |
| }; |
| }; |
| |
| template<typename T> |
| intptr_t getCorrectUncontendedValue(int slot_idx) { |
| intptr_as_array_of<T> slot; |
| slot.result = 0; |
| for( int i=0; i<slot.how_many_Ts; ++i ) { |
| const T my_prime = T(prime[slot_idx*slot.how_many_Ts + i]); |
| for( int j=0; j<numMaskedOperations; ++j ) |
| slot.space[i] += my_prime; |
| } |
| return slot.result; |
| } |
| |
| template<typename T> |
| intptr_t getCorrectContendedValue() { |
| intptr_as_array_of<T> slot; |
| slot.result = 0; |
| for( int i=0; i<slot.how_many_Ts; ++i ) |
| for( int primes=0; primes<testSpaceSize; ++primes ) |
| for( int j=0; j<numMaskedOperations; ++j ) |
| slot.space[i] += prime[primes]; |
| return slot.result; |
| } |
| |
| #if _MSC_VER && !defined(__INTEL_COMPILER) |
| #pragma warning( pop ) |
| #endif // warning 4244 is back again |
| |
| template<typename T> |
| void TestMaskedCAS() { |
| REMARK("testing masked CAS<%d>\n",int(sizeof(T))); |
| |
| const int num_slots = sizeof(T)*testSpaceSize/sizeof(intptr_t); |
| intptr_t arr1[num_slots+2]; // two more "canary" slots at boundaries |
| intptr_t arr2[num_slots+2]; |
| for(int i=0; i<num_slots+2; ++i) |
| arr2[i] = arr1[i] = 0; |
| T* test_space_uncontended = (T*)(arr1+1); |
| T* test_space_contended = (T*)(arr2+1); |
| |
| NativeParallelFor( testSpaceSize, TestMaskedCAS_Body<T>(test_space_uncontended, test_space_contended) ); |
| |
| ASSERT( arr1[0]==0 && arr1[num_slots+1]==0 && arr2[0]==0 && arr2[num_slots+1]==0 , "adjacent memory was overwritten" ); |
| const intptr_t correctContendedValue = getCorrectContendedValue<T>(); |
| for(int i=0; i<num_slots; ++i) { |
| ASSERT( arr1[i+1]==getCorrectUncontendedValue<T>(i), "unexpected value in an uncontended slot" ); |
| ASSERT( arr2[i+1]==correctContendedValue, "unexpected value in a contended slot" ); |
| } |
| } |
| |
| template<unsigned N> |
| class ArrayElement { |
| char item[N]; |
| }; |
| |
| int TestMain () { |
| #if defined(__INTEL_COMPILER)||!defined(_MSC_VER)||_MSC_VER>=1400 |
| TestAtomicInteger<unsigned long long>("unsigned long long"); |
| TestAtomicInteger<long long>("long long"); |
| #else |
| REPORT("Known issue: atomic<64-bits> does not compile with VC 7.1\n"); |
| #endif /*defined(__INTEL_COMPILER)||!defined(_MSC_VER)||_MSC_VER>=1400 */ |
| TestAtomicInteger<unsigned long>("unsigned long"); |
| TestAtomicInteger<long>("long"); |
| TestAtomicInteger<unsigned int>("unsigned int"); |
| TestAtomicInteger<int>("int"); |
| TestAtomicInteger<unsigned short>("unsigned short"); |
| TestAtomicInteger<short>("short"); |
| TestAtomicInteger<signed char>("signed char"); |
| TestAtomicInteger<unsigned char>("unsigned char"); |
| TestAtomicInteger<char>("char"); |
| TestAtomicInteger<wchar_t>("wchar_t"); |
| TestAtomicInteger<size_t>("size_t"); |
| TestAtomicInteger<ptrdiff_t>("ptrdiff_t"); |
| TestAtomicPointer<ArrayElement<1> >(); |
| TestAtomicPointer<ArrayElement<2> >(); |
| TestAtomicPointer<ArrayElement<3> >(); |
| TestAtomicPointer<ArrayElement<4> >(); |
| TestAtomicPointer<ArrayElement<5> >(); |
| TestAtomicPointer<ArrayElement<6> >(); |
| TestAtomicPointer<ArrayElement<7> >(); |
| TestAtomicPointer<ArrayElement<8> >(); |
| TestAtomicPointerToTypeOfUnknownSize<IncompleteType*>( "IncompleteType*" ); |
| TestAtomicPointerToTypeOfUnknownSize<void*>( "void*" ); |
| TestAtomicBool(); |
| TestAtomicEnum(); |
| #if !__TBB_FLOATING_POINT_BROKEN |
| TestAtomicFloat<float>("float"); |
| TestAtomicFloat<double>("double"); |
| #endif /* !__TBB_FLOATING_POINT_BROKEN */ |
| ASSERT( !ParallelError, NULL ); |
| TestMaskedCAS<unsigned char>(); |
| TestMaskedCAS<unsigned short>(); |
| return Harness::Done; |
| } |
| |
| template<typename T> |
| struct FlagAndMessage { |
| //! 0 if message not set yet, 1 if message is set. |
| tbb::atomic<T> flag; |
| /** Force flag and message to be on distinct cache lines for machines with cache line size <= 4096 bytes */ |
| char pad[4096/sizeof(T)]; |
| //! Non-zero if message is ready |
| T message; |
| }; |
| |
| // A special template function used for summation. |
| // Actually it is only necessary because of its specialization for void* |
| template<typename T> |
| T special_sum(intptr_t arg1, intptr_t arg2) { |
| return (T)((T)arg1 + arg2); |
| } |
| |
| // The specialization for IncompleteType* is required |
| // because pointer arithmetic (+) is impossible with IncompleteType* |
| template<> |
| IncompleteType* special_sum<IncompleteType*>(intptr_t arg1, intptr_t arg2) { |
| return (IncompleteType*)(arg1 + arg2); |
| } |
| |
| // The specialization for void* is required |
| // because pointer arithmetic (+) is impossible with void* |
| template<> |
| void* special_sum<void*>(intptr_t arg1, intptr_t arg2) { |
| return (void*)(arg1 + arg2); |
| } |
| |
| // The specialization for bool is required to shut up gratuitous compiler warnings, |
| // because some compilers warn about casting int to bool. |
| template<> |
| bool special_sum<bool>(intptr_t arg1, intptr_t arg2) { |
| return ((arg1!=0) + arg2)!=0; |
| } |
| |
| volatile int One = 1; |
| |
| template<typename T> |
| class HammerLoadAndStoreFence: NoAssign { |
| FlagAndMessage<T>* fam; |
| const int n; |
| const int p; |
| const int trial; |
| const char* name; |
| mutable T accum; |
| public: |
| HammerLoadAndStoreFence( FlagAndMessage<T>* fam_, int n_, int p_, const char* name_, int trial_ ) : fam(fam_), n(n_), p(p_), trial(trial_), name(name_) {} |
| void operator()( int k ) const { |
| int one = One; |
| FlagAndMessage<T>* s = fam+k; |
| FlagAndMessage<T>* s_next = fam + (k+1)%p; |
| for( int i=0; i<n; ++i ) { |
| // The inner for loop is a spin-wait loop, which is normally considered very bad style. |
| // But we must use it here because we are interested in examining subtle hardware effects. |
| for(unsigned short cnt=1; ; ++cnt) { |
| if( !cnt ) // to help 1-core systems complete the test, yield every 2^16 iterations |
| __TBB_Yield(); |
| // Compilers typically generate non-trivial sequence for division by a constant. |
| // The expression here is dependent on the loop index i, so it cannot be hoisted. |
| #define COMPLICATED_ZERO (i*(one-1)/100) |
| // Read flag and then the message |
| T flag, message; |
| if( trial&1 ) { |
| // COMPLICATED_ZERO here tempts compiler to hoist load of message above reading of flag. |
| flag = (s+COMPLICATED_ZERO)->flag; |
| message = s->message; |
| } else { |
| flag = s->flag; |
| message = s->message; |
| } |
| if( flag ) { |
| if( flag!=(T)-1 ) { |
| REPORT("ERROR: flag!=(T)-1 k=%d i=%d trial=%x type=%s (atomicity problem?)\n", k, i, trial, name ); |
| ParallelError = true; |
| } |
| if( message!=(T)-1 ) { |
| REPORT("ERROR: message!=(T)-1 k=%d i=%d trial=%x type=%s (memory fence problem?)\n", k, i, trial, name ); |
| ParallelError = true; |
| } |
| s->message = T(0); |
| s->flag = T(0); |
| // Set message and then the flag |
| if( trial&2 ) { |
| // COMPLICATED_ZERO here tempts compiler to sink store below setting of flag |
| s_next->message = special_sum<T>(-1, COMPLICATED_ZERO); |
| s_next->flag = (T)-1; |
| } else { |
| s_next->message = (T)-1; |
| s_next->flag = (T)-1; |
| } |
| break; |
| } else { |
| // Force compiler to use message anyway, so it cannot sink read of s->message below the if. |
| accum = message; |
| } |
| } |
| } |
| } |
| }; |
| |
| //! Test that atomic<T> has acquire semantics for loads and release semantics for stores. |
| /** Test performs round-robin passing of message among p processors, |
| where p goes from MinThread to MaxThread. */ |
| template<typename T> |
| void TestLoadAndStoreFences( const char* name ) { |
| for( int p=MinThread<2 ? 2 : MinThread; p<=MaxThread; ++p ) { |
| FlagAndMessage<T>* fam = new FlagAndMessage<T>[p]; |
| // Each of four trials excercise slightly different expresion pattern within the test. |
| // See occurrences of COMPLICATED_ZERO for details. |
| for( int trial=0; trial<4; ++trial ) { |
| memset( fam, 0, p*sizeof(FlagAndMessage<T>) ); |
| fam->message = (T)-1; |
| fam->flag = (T)-1; |
| NativeParallelFor( p, HammerLoadAndStoreFence<T>( fam, 100, p, name, trial ) ); |
| for( int k=0; k<p; ++k ) { |
| ASSERT( fam[k].message==(k==0 ? (T)-1 : 0), "incomplete round-robin?" ); |
| ASSERT( fam[k].flag==(k==0 ? (T)-1 : 0), "incomplete round-robin?" ); |
| } |
| } |
| delete[] fam; |
| } |
| } |
| |
| //! Sparse set of values of integral type T. |
| /** Set is designed so that if a value is read or written non-atomically, |
| the resulting intermediate value is likely to not be a member of the set. */ |
| template<typename T> |
| class SparseValueSet { |
| T factor; |
| public: |
| SparseValueSet() { |
| // Compute factor such that: |
| // 1. It has at least one 1 in most of its bytes. |
| // 2. The bytes are typically different. |
| // 3. When multiplied by any value <=127, the product does not overflow. |
| factor = T(0); |
| for( unsigned i=0; i<sizeof(T)*8-7; i+=7 ) |
| factor = T(factor | T(1)<<i); |
| } |
| //! Get ith member of set |
| T get( int i ) const { |
| // Create multiple of factor. The & prevents overflow of the product. |
| return T((i&0x7F)*factor); |
| } |
| //! True if set contains x |
| bool contains( T x ) const { |
| // True if |
| return (x%factor)==0; |
| } |
| }; |
| |
| //! Specialization for pointer types. The pointers are random and should not be dereferenced. |
| template<typename T> |
| class SparseValueSet<T*> { |
| SparseValueSet<ptrdiff_t> my_set; |
| public: |
| T* get( int i ) const {return reinterpret_cast<T*>(my_set.get(i));} |
| bool contains( T* x ) const {return my_set.contains(reinterpret_cast<ptrdiff_t>(x));} |
| }; |
| |
| //! Specialization for bool. |
| /** Checking bool for atomic read/write is pointless in practice, because |
| there is no way to *not* atomically read or write a bool value. */ |
| template<> |
| class SparseValueSet<bool> { |
| public: |
| bool get( int i ) const {return i&1;} |
| bool contains( bool ) const {return true;} |
| }; |
| |
| #if !__TBB_FLOATING_POINT_BROKEN |
| |
| #if _MSC_VER==1500 && !defined(__INTEL_COMPILER) |
| // VS2008/VC9 seems to have an issue; limits pull in math.h |
| #pragma warning( push ) |
| #pragma warning( disable: 4985 ) |
| #endif |
| #include <limits> /* Need std::numeric_limits */ |
| #if _MSC_VER==1500 && !defined(__INTEL_COMPILER) |
| #pragma warning( pop ) |
| #endif |
| |
| //! Commonality inherited by specializations for floating-point types. |
| template<typename T> |
| class SparseFloatSet: NoAssign { |
| const T epsilon; |
| public: |
| SparseFloatSet() : epsilon(std::numeric_limits<T>::epsilon()) {} |
| T get( int i ) const { |
| return i==0 ? T(0) : 1/T((i&0x7F)+1); |
| } |
| bool contains( T x ) const { |
| if( x==T(0) ) { |
| return true; |
| } else { |
| int j = int(1/x+T(0.5)); |
| if( 0<j && j<=128 ) { |
| T error = x*T(j)-T(1); |
| // In the calculation above, if x was indeed generated by method get, the error should be |
| // at most epsilon, because x is off by at most 1/2 ulp from its infinitely precise value, |
| // j is exact, and the multiplication incurs at most another 1/2 ulp of round-off error. |
| if( -epsilon<=error && error<=epsilon ) { |
| return true; |
| } else { |
| REPORT("Warning: excessive floating-point error encountered j=%d x=%.15g error=%.15g\n",j,x,error); |
| } |
| } |
| return false; |
| } |
| }; |
| }; |
| |
| template<> |
| class SparseValueSet<float>: public SparseFloatSet<float> {}; |
| |
| template<> |
| class SparseValueSet<double>: public SparseFloatSet<double> {}; |
| |
| #endif /* !__TBB_FLOATING_POINT_BROKEN */ |
| |
| template<typename T> |
| class HammerAssignment: NoAssign { |
| tbb::atomic<T>& x; |
| const char* name; |
| SparseValueSet<T> set; |
| public: |
| HammerAssignment( tbb::atomic<T>& x_, const char* name_ ) : x(x_), name(name_) {} |
| void operator()( int k ) const { |
| const int n = 1000000; |
| if( k ) { |
| tbb::atomic<T> z; |
| AssertSameType( z=x, z ); // Check that return type from assignment is correct |
| for( int i=0; i<n; ++i ) { |
| // Read x atomically into z. |
| z = x; |
| if( !set.contains(z) ) { |
| REPORT("ERROR: assignment of atomic<%s> is not atomic\n", name); |
| ParallelError = true; |
| return; |
| } |
| } |
| } else { |
| tbb::atomic<T> y; |
| for( int i=0; i<n; ++i ) { |
| // Get pseudo-random value. |
| y = set.get(i); |
| // Write y atomically into x. |
| x = y; |
| } |
| } |
| } |
| }; |
| |
| // Compile-time check that a class method has the required signature. |
| // Intended to check the assignment operator of tbb::atomic. |
| template<typename T> void TestAssignmentSignature( T& (T::*)(const T&) ) {} |
| |
| #if _MSC_VER && !defined(__INTEL_COMPILER) |
| // Suppress "conditional expression is constant" warning. |
| #pragma warning( push ) |
| #pragma warning( disable: 4127 ) |
| #endif |
| |
| template<typename T> |
| void TestAssignment( const char* name ) { |
| TestAssignmentSignature( &tbb::atomic<T>::operator= ); |
| tbb::atomic<T> x; |
| x = T(0); |
| NativeParallelFor( 2, HammerAssignment<T>( x, name ) ); |
| #if __TBB_x86_32 && (__linux__ || __FreeBSD__ || _WIN32) |
| if( sizeof(T)==8 ) { |
| // Some compilers for IA-32 fail to provide 8-byte alignment of objects on the stack, |
| // even if the object specifies 8-byte alignment. On such platforms, the IA-32 implementation |
| // of atomic<long long> and atomic<unsigned long long> use different tactics depending upon |
| // whether the object is properly aligned or not. The following abusive test ensures that we |
| // cover both the proper and improper alignment cases, one with the x above and the other with |
| // the y below, perhaps not respectively. |
| |
| // Allocate space big enough to always contain 8-byte locations that are aligned and misaligned. |
| char raw_space[15]; |
| // Set delta to 0 if x is aligned, 4 otherwise. |
| uintptr_t delta = ((reinterpret_cast<uintptr_t>(&x)&7) ? 0 : 4); |
| // y crosses 8-byte boundary if and only if x does not cross. |
| tbb::atomic<T>& y = *reinterpret_cast<tbb::atomic<T>*>((reinterpret_cast<uintptr_t>(&raw_space[7+delta])&~7u) - delta); |
| // Assertion checks that y really did end up somewhere inside "raw_space". |
| ASSERT( raw_space<=reinterpret_cast<char*>(&y), "y starts before raw_space" ); |
| ASSERT( reinterpret_cast<char*>(&y+1) <= raw_space+sizeof(raw_space), "y starts after raw_space" ); |
| y = T(0); |
| NativeParallelFor( 2, HammerAssignment<T>( y, name ) ); |
| } |
| #endif /* __TBB_x86_32 && (__linux__ || __FreeBSD__ || _WIN32) */ |
| } |
| |
| #if _MSC_VER && !defined(__INTEL_COMPILER) |
| #pragma warning( pop ) |
| #endif |
| |
| template<typename T> |
| void TestParallel( const char* name ) { |
| TestLoadAndStoreFences<T>(name); |
| TestAssignment<T>(name); |
| } |
