tests/unit/stack/stack_intrusive_pushpop.cpp

   1 //$$CDS-header$$
   2
   3 #include "cppunit/thread.h"
   4 #include "stack/intrusive_stack_type.h"
   5
   6 // Multi-threaded stack test for push/pop operation
   7 namespace istack {
   8
   9 #define TEST_CASE( Q, HOOK ) void Q()          { test_unbounded< Types<SimpleValue<HOOK> >::Q >();   }
  10 #define TEST_ELIMINATION( Q, HOOK ) void Q()   { test_elimination< Types<SimpleValue<HOOK> >::Q >(); }
  11 #define TEST_BOUNDED( Q, HOOK ) void Q()       { test_bounded< Types<SimpleValue<HOOK> >::Q >();     }
  12 #define TEST_FCSTACK( Q, HOOK ) void Q()       { test_fcstack< Types<SimpleValue<HOOK> >::Q >();     }
  13 #define TEST_STDSTACK( Q ) void Q()            { test_stdstack< Types<SimpleValue<> >::Q >();       }
  14
  15     namespace {
  16         static size_t s_nPushThreadCount = 4;
  17         static size_t s_nPopThreadCount = 4;
  18         static size_t s_nStackSize = 10000000;
  19         static size_t s_nEliminationSize = 4;
  20         static bool s_bFCIterative = false;
  21         static unsigned int s_nFCCombinePassCount = 64;
  22         static unsigned int s_nFCCompactFactor = 1024;
  23
  24         struct empty {};
  25
  26         template <typename Base = empty >
  27         struct SimpleValue: public Base
  28         {
  29             size_t      nNo;
  30             size_t      nProducer;
  31             size_t      nConsumer;
  32
  33             SimpleValue() {}
  34             SimpleValue( size_t n ): nNo(n) {}
  35             size_t getNo() const { return  nNo; }
  36         };
  37
  38     } // namespace
  39
  40     class IntrusiveStack_PushPop: public CppUnitMini::TestCase
  41     {
  42         atomics::atomic<size_t>  m_nWorkingProducers;
  43         static CDS_CONSTEXPR const size_t c_nValArraySize = 1024;
  44         static CDS_CONSTEXPR const size_t c_nBadConsumer = 0xbadc0ffe;
  45
  46         template <class Stack>
  47         class Producer: public CppUnitMini::TestThread
  48         {
  49             virtual TestThread *    clone()
  50             {
  51                 return new Producer( *this );
  52             }
  53         public:
  54             Stack&              m_Stack;
  55             size_t              m_nPushError;
  56             size_t              m_arrPush[c_nValArraySize];
  57
  58             // Interval in m_arrValue
  59             typename Stack::value_type *       m_pStart;
  60             typename Stack::value_type *       m_pEnd;
  61
  62         public:
  63             Producer( CppUnitMini::ThreadPool& pool, Stack& s )
  64                 : CppUnitMini::TestThread( pool )
  65                 , m_Stack( s )
  66             {}
  67             Producer( Producer& src )
  68                 : CppUnitMini::TestThread( src )
  69                 , m_Stack( src.m_Stack )
  70             {}
  71
  72             IntrusiveStack_PushPop&  getTest()
  73             {
  74                 return static_cast<IntrusiveStack_PushPop&>( m_Pool.m_Test );
  75             }
  76
  77             virtual void init()
  78             {
  79                 cds::threading::Manager::attachThread();
  80             }
  81             virtual void fini()
  82             {
  83                 cds::threading::Manager::detachThread();
  84             }
  85
  86             virtual void test()
  87             {
  88                 m_nPushError = 0;
  89                 memset( m_arrPush, 0, sizeof(m_arrPush));
  90
  91                 size_t i = 0;
  92                 for ( typename Stack::value_type * p = m_pStart; p < m_pEnd; ++p, ++i ) {
  93                     p->nProducer = m_nThreadNo;
  94                     p->nNo = i % c_nValArraySize;
  95                     if ( m_Stack.push( *p ))
  96                         ++m_arrPush[ p->nNo ];
  97                     else
  98                         ++m_nPushError;
  99                 }
 100
 101                 getTest().m_nWorkingProducers.fetch_sub( 1, atomics::memory_order_release );
 102             }
 103         };
 104
 105         template <class Stack>
 106         class Consumer: public CppUnitMini::TestThread
 107         {
 108             virtual TestThread *    clone()
 109             {
 110                 return new Consumer( *this );
 111             }
 112         public:
 113             Stack&              m_Stack;
 114             size_t              m_nPopCount;
 115             size_t              m_nPopEmpty;
 116             size_t              m_arrPop[c_nValArraySize];
 117             size_t              m_nDirtyPop;
 118         public:
 119             Consumer( CppUnitMini::ThreadPool& pool, Stack& s )
 120                 : CppUnitMini::TestThread( pool )
 121                 , m_Stack( s )
 122             {}
 123             Consumer( Consumer& src )
 124                 : CppUnitMini::TestThread( src )
 125                 , m_Stack( src.m_Stack )
 126             {}
 127
 128             IntrusiveStack_PushPop&  getTest()
 129             {
 130                 return static_cast<IntrusiveStack_PushPop&>( m_Pool.m_Test );
 131             }
 132
 133             virtual void init()
 134             {
 135                 cds::threading::Manager::attachThread();
 136             }
 137             virtual void fini()
 138             {
 139                 cds::threading::Manager::detachThread();
 140             }
 141
 142             virtual void test()
 143             {
 144                 m_nPopEmpty = 0;
 145                 m_nPopCount = 0;
 146                 m_nDirtyPop = 0;
 147                 memset( m_arrPop, 0, sizeof(m_arrPop));
 148
 149                 while ( !(getTest().m_nWorkingProducers.load(atomics::memory_order_acquire) == 0 && m_Stack.empty()) ) {
 150                     typename Stack::value_type * p = m_Stack.pop();
 151                     if ( p ) {
 152                         CDS_TSAN_ANNOTATE_IGNORE_WRITES_BEGIN;
 153                         p->nConsumer = m_nThreadNo;
 154                         ++m_nPopCount;
 155                         if ( p->nNo < sizeof(m_arrPop)/sizeof(m_arrPop[0]) )
 156                             ++m_arrPop[p->nNo];
 157                         else
 158                             ++m_nDirtyPop;
 159                         CDS_TSAN_ANNOTATE_IGNORE_WRITES_END;
 160                     }
 161                     else
 162                         ++m_nPopEmpty;
 163                 }
 164             }
 165         };
 166
 167         template <typename T>
 168         class value_array
 169         {
 170             T * m_pArr;
 171         public:
 172             value_array( size_t nSize )
 173                 : m_pArr( new T[nSize] )
 174             {}
 175
 176             ~value_array()
 177             {
 178                 delete [] m_pArr;
 179             }
 180
 181             T * get() const { return m_pArr; }
 182         };
 183
 184     protected:
 185         void setUpParams( const CppUnitMini::TestCfg& cfg ) {
 186             s_nPushThreadCount = cfg.getULong("PushThreadCount", 4 );
 187             s_nPopThreadCount = cfg.getULong("PopThreadCount", 4 );
 188             s_nStackSize = cfg.getULong("StackSize", 1000000 );
 189             s_nEliminationSize = cfg.getULong("EliminationSize", 4 );
 190             s_bFCIterative = cfg.getBool( "FCIterate", false );
 191             s_nFCCombinePassCount = cfg.getUInt( "FCCombinePassCount", 64 );
 192             s_nFCCompactFactor = cfg.getUInt( "FCCompactFactor", 1024 );
 193         }
 194
 195         template <class Stack>
 196         void analyze( CppUnitMini::ThreadPool& pool, Stack& /*testStack*/  )
 197         {
 198             size_t nPushError = 0;
 199             size_t nPopEmpty = 0;
 200             size_t nPopCount = 0;
 201             size_t arrVal[c_nValArraySize];
 202             memset( arrVal, 0, sizeof(arrVal));
 203             size_t nDirtyPop = 0;
 204
 205             for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
 206                 CppUnitMini::TestThread * pThread = *it;
 207                 Producer<Stack> * pPusher = dynamic_cast< Producer<Stack> *>( pThread );
 208                 if ( pPusher ) {
 209                     nPushError += pPusher->m_nPushError;
 210                     for ( size_t i = 0; i < sizeof(arrVal)/sizeof(arrVal[0]); ++i )
 211                         arrVal[i] += pPusher->m_arrPush[i];
 212                 }
 213                 else {
 214                     Consumer<Stack> * pPopper = dynamic_cast<Consumer<Stack> *>( pThread );
 215                     assert( pPopper );
 216                     nPopEmpty += pPopper->m_nPopEmpty;
 217                     nPopCount += pPopper->m_nPopCount;
 218                     nDirtyPop += pPopper->m_nDirtyPop;
 219                     for ( size_t i = 0; i < sizeof(arrVal)/sizeof(arrVal[0]); ++i )
 220                         arrVal[i] -= pPopper->m_arrPop[i];
 221                 }
 222             }
 223
 224             CPPUNIT_MSG( "Push count=" << s_nStackSize
 225                 << " push error=" << nPushError
 226                 << " pop count=" << nPopCount
 227                 << " pop empty=" << nPopEmpty
 228                 << " dirty pop=" << nDirtyPop
 229                 );
 230             CPPUNIT_CHECK( nPopCount == s_nStackSize );
 231             CPPUNIT_CHECK( nDirtyPop == 0 );
 232             for ( size_t i = 0; i < sizeof(arrVal)/sizeof(arrVal[0]); ++i ) {
 233                 CPPUNIT_CHECK_EX( arrVal[i] == 0, "arrVal[" << i << "]=" << long(arrVal[i]) );
 234             }
 235         }
 236
 237         template <class Stack>
 238         void test( Stack& testStack, value_array<typename Stack::value_type>& arrValue )
 239         {
 240             m_nWorkingProducers.store( s_nPushThreadCount, atomics::memory_order_release );
 241             size_t const nPushCount = s_nStackSize / s_nPushThreadCount;
 242
 243             typename Stack::value_type * pValStart = arrValue.get();
 244             typename Stack::value_type * pValEnd = pValStart + s_nStackSize;
 245
 246             CppUnitMini::ThreadPool pool( *this );
 247             pool.add( new Producer<Stack>( pool, testStack ), s_nPushThreadCount );
 248             {
 249                 for ( typename Stack::value_type * it = pValStart; it != pValEnd; ++it )
 250                     it->nConsumer = c_nBadConsumer;
 251
 252                 typename Stack::value_type * pStart = pValStart;
 253                 for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
 254                     static_cast<Producer<Stack>* >( *it )->m_pStart = pStart;
 255                     pStart += nPushCount;
 256                     static_cast<Producer<Stack>* >( *it )->m_pEnd = pStart;
 257                 }
 258             }
 259             pool.add( new Consumer<Stack>( pool, testStack ), s_nPopThreadCount );
 260
 261             CPPUNIT_MSG( "   Push/Pop test, push thread count=" << s_nPushThreadCount
 262                 << " pop thread count=" << s_nPopThreadCount
 263                 << " items=" << (nPushCount * s_nPushThreadCount)
 264                 << "...");
 265             pool.run();
 266             CPPUNIT_MSG( "   Duration=" << pool.avgDuration() );
 267
 268             s_nStackSize = nPushCount * s_nPushThreadCount;
 269
 270             {
 271                 typename Stack::value_type * pEnd = pValStart + s_nStackSize;
 272                 for ( typename Stack::value_type * it = pValStart; it != pEnd; ++it  )
 273                     CPPUNIT_CHECK( it->nConsumer != c_nBadConsumer );
 274             }
 275
 276             analyze( pool, testStack );
 277             CPPUNIT_MSG( testStack.statistics() );
 278         }
 279
 280     public:
 281         // Unbounded stack test
 282         template <class Stack>
 283         void test_unbounded()
 284         {
 285             value_array<typename Stack::value_type> arrValue( s_nStackSize );
 286             {
 287                 Stack testStack;
 288                 test( testStack, arrValue );
 289             }
 290             Stack::gc::force_dispose();
 291         }
 292
 293         template <class Stack>
 294         void test_fcstack()
 295         {
 296             if ( s_bFCIterative ) {
 297                 for (unsigned int nCompactFactor = 1; nCompactFactor <= s_nFCCompactFactor; nCompactFactor *= 2 ) {
 298                     for ( unsigned int nPass = 1; nPass <= s_nFCCombinePassCount; nPass *= 2 ) {
 299                         CPPUNIT_MSG( "Compact factor=" << nCompactFactor << ", combine pass count=" << nPass );
 300                         value_array<typename Stack::value_type> arrValue( s_nStackSize );
 301                         Stack testStack( nCompactFactor, nPass );
 302                         test( testStack, arrValue );
 303                     }
 304                 }
 305             }
 306             else {
 307                 if ( s_nFCCompactFactor && s_nFCCombinePassCount ) {
 308                     CPPUNIT_MSG( "Compact factor=" << s_nFCCompactFactor << ", combine pass count=" << s_nFCCombinePassCount );
 309                     value_array<typename Stack::value_type> arrValue( s_nStackSize );
 310                     Stack testStack( s_nFCCompactFactor, s_nFCCombinePassCount );
 311                     test( testStack, arrValue );
 312                 }
 313                 else {
 314                     value_array<typename Stack::value_type> arrValue( s_nStackSize );
 315                     Stack testStack;
 316                     test( testStack, arrValue );
 317                 }
 318             }
 319         }
 320
 321         // Unbounded elimination stack test
 322         template <class Stack>
 323         void test_elimination()
 324         {
 325             value_array<typename Stack::value_type> arrValue( s_nStackSize );
 326             {
 327                 Stack testStack( s_nEliminationSize );
 328                 test( testStack, arrValue );
 329                 check_elimination_stat( testStack.statistics() );
 330             }
 331             Stack::gc::force_dispose();
 332         }
 333         void check_elimination_stat( cds::intrusive::treiber_stack::empty_stat const& )
 334         {}
 335         void check_elimination_stat( cds::intrusive::treiber_stack::stat<> const& s )
 336         {
 337             CPPUNIT_CHECK( s.m_PushCount.get() + s.m_ActivePushCollision.get() + s.m_PassivePushCollision.get() == s_nStackSize );
 338             CPPUNIT_CHECK( s.m_PopCount.get() + s.m_ActivePopCollision.get() + s.m_PassivePopCollision.get() == s_nStackSize );
 339             CPPUNIT_CHECK( s.m_PushCount.get() == s.m_PopCount.get() );
 340             CPPUNIT_CHECK( s.m_ActivePopCollision.get() == s.m_PassivePushCollision.get() );
 341             CPPUNIT_CHECK( s.m_ActivePushCollision.get() == s.m_PassivePopCollision.get() );
 342         }
 343
 344         // Bounded stack test
 345         template <class Stack>
 346         void test_bounded()
 347         {
 348             value_array<typename Stack::value_type> arrValue( s_nStackSize );
 349             Stack testStack( s_nStackSize );
 350             test( testStack, arrValue );
 351         }
 352
 353         template <class Stack>
 354         void test_stdstack()
 355         {
 356             value_array<typename Stack::value_type> arrValue( s_nStackSize );
 357             Stack testStack;
 358             test( testStack, arrValue );
 359         }
 360
 361     protected:
 362 #   include "stack/intrusive_stack_defs.h"
 363         CDSUNIT_DECLARE_TreiberStack
 364         CDSUNIT_DECLARE_EliminationStack
 365         CDSUNIT_DECLARE_FCStack
 366         CDSUNIT_DECLARE_StdStack
 367
 368         CPPUNIT_TEST_SUITE(IntrusiveStack_PushPop)
 369             CDSUNIT_TEST_TreiberStack
 370             CDSUNIT_TEST_EliminationStack
 371             CDSUNIT_TEST_FCStack
 372             CDSUNIT_TEST_StdStack
 373         CPPUNIT_TEST_SUITE_END();
 374     };
 375 } // namespace istack
 376
 377 CPPUNIT_TEST_SUITE_REGISTRATION(istack::IntrusiveStack_PushPop);