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                         p->nConsumer = m_nThreadNo;
 153                         ++m_nPopCount;
 154                         if ( p->nNo < sizeof(m_arrPop)/sizeof(m_arrPop[0]) )
 155                             ++m_arrPop[p->nNo];
 156                         else
 157                             ++m_nDirtyPop;
 158                     }
 159                     else
 160                         ++m_nPopEmpty;
 161                 }
 162             }
 163         };
 164
 165         template <typename T>
 166         class value_array
 167         {
 168             T * m_pArr;
 169         public:
 170             value_array( size_t nSize )
 171                 : m_pArr( new T[nSize] )
 172             {}
 173
 174             ~value_array()
 175             {
 176                 delete [] m_pArr;
 177             }
 178
 179             T * get() const { return m_pArr; }
 180         };
 181
 182     protected:
 183         void setUpParams( const CppUnitMini::TestCfg& cfg ) {
 184             s_nPushThreadCount = cfg.getULong("PushThreadCount", 4 );
 185             s_nPopThreadCount = cfg.getULong("PopThreadCount", 4 );
 186             s_nStackSize = cfg.getULong("StackSize", 1000000 );
 187             s_nEliminationSize = cfg.getULong("EliminationSize", 4 );
 188             s_bFCIterative = cfg.getBool( "FCIterate", false );
 189             s_nFCCombinePassCount = cfg.getUInt( "FCCombinePassCount", 64 );
 190             s_nFCCompactFactor = cfg.getUInt( "FCCompactFactor", 1024 );
 191         }
 192
 193         template <class Stack>
 194         void analyze( CppUnitMini::ThreadPool& pool, Stack& /*testStack*/  )
 195         {
 196             size_t nPushError = 0;
 197             size_t nPopEmpty = 0;
 198             size_t nPopCount = 0;
 199             size_t arrVal[c_nValArraySize];
 200             memset( arrVal, 0, sizeof(arrVal));
 201             size_t nDirtyPop = 0;
 202
 203             for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
 204                 CppUnitMini::TestThread * pThread = *it;
 205                 Producer<Stack> * pPusher = dynamic_cast< Producer<Stack> *>( pThread );
 206                 if ( pPusher ) {
 207                     nPushError += pPusher->m_nPushError;
 208                     for ( size_t i = 0; i < sizeof(arrVal)/sizeof(arrVal[0]); ++i )
 209                         arrVal[i] += pPusher->m_arrPush[i];
 210                 }
 211                 else {
 212                     Consumer<Stack> * pPopper = dynamic_cast<Consumer<Stack> *>( pThread );
 213                     assert( pPopper );
 214                     nPopEmpty += pPopper->m_nPopEmpty;
 215                     nPopCount += pPopper->m_nPopCount;
 216                     nDirtyPop += pPopper->m_nDirtyPop;
 217                     for ( size_t i = 0; i < sizeof(arrVal)/sizeof(arrVal[0]); ++i )
 218                         arrVal[i] -= pPopper->m_arrPop[i];
 219                 }
 220             }
 221
 222             CPPUNIT_MSG( "Push count=" << s_nStackSize
 223                 << " push error=" << nPushError
 224                 << " pop count=" << nPopCount
 225                 << " pop empty=" << nPopEmpty
 226                 << " dirty pop=" << nDirtyPop
 227                 );
 228             CPPUNIT_CHECK( nPopCount == s_nStackSize );
 229             CPPUNIT_CHECK( nDirtyPop == 0 );
 230             for ( size_t i = 0; i < sizeof(arrVal)/sizeof(arrVal[0]); ++i ) {
 231                 CPPUNIT_CHECK_EX( arrVal[i] == 0, "arrVal[" << i << "]=" << long(arrVal[i]) );
 232             }
 233         }
 234
 235         template <class Stack>
 236         void test( Stack& testStack, value_array<typename Stack::value_type>& arrValue )
 237         {
 238             m_nWorkingProducers.store( s_nPushThreadCount, atomics::memory_order_release );
 239             size_t const nPushCount = s_nStackSize / s_nPushThreadCount;
 240
 241             typename Stack::value_type * pValStart = arrValue.get();
 242             typename Stack::value_type * pValEnd = pValStart + s_nStackSize;
 243
 244             CppUnitMini::ThreadPool pool( *this );
 245             pool.add( new Producer<Stack>( pool, testStack ), s_nPushThreadCount );
 246             {
 247                 for ( typename Stack::value_type * it = pValStart; it != pValEnd; ++it )
 248                     it->nConsumer = c_nBadConsumer;
 249
 250                 typename Stack::value_type * pStart = pValStart;
 251                 for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
 252                     static_cast<Producer<Stack>* >( *it )->m_pStart = pStart;
 253                     pStart += nPushCount;
 254                     static_cast<Producer<Stack>* >( *it )->m_pEnd = pStart;
 255                 }
 256             }
 257             pool.add( new Consumer<Stack>( pool, testStack ), s_nPopThreadCount );
 258
 259             CPPUNIT_MSG( "   Push/Pop test, push thread count=" << s_nPushThreadCount
 260                 << " pop thread count=" << s_nPopThreadCount
 261                 << " items=" << (nPushCount * s_nPushThreadCount)
 262                 << "...");
 263             pool.run();
 264             CPPUNIT_MSG( "   Duration=" << pool.avgDuration() );
 265
 266             s_nStackSize = nPushCount * s_nPushThreadCount;
 267
 268             {
 269                 typename Stack::value_type * pEnd = pValStart + s_nStackSize;
 270                 for ( typename Stack::value_type * it = pValStart; it != pEnd; ++it  )
 271                     CPPUNIT_CHECK( it->nConsumer != c_nBadConsumer );
 272             }
 273
 274             analyze( pool, testStack );
 275             CPPUNIT_MSG( testStack.statistics() );
 276         }
 277
 278     public:
 279         // Unbounded stack test
 280         template <class Stack>
 281         void test_unbounded()
 282         {
 283             value_array<typename Stack::value_type> arrValue( s_nStackSize );
 284             {
 285                 Stack testStack;
 286                 test( testStack, arrValue );
 287             }
 288             Stack::gc::force_dispose();
 289         }
 290
 291         template <class Stack>
 292         void test_fcstack()
 293         {
 294             if ( s_bFCIterative ) {
 295                 for (unsigned int nCompactFactor = 1; nCompactFactor <= s_nFCCompactFactor; nCompactFactor *= 2 ) {
 296                     for ( unsigned int nPass = 1; nPass <= s_nFCCombinePassCount; nPass *= 2 ) {
 297                         CPPUNIT_MSG( "Compact factor=" << nCompactFactor << ", combine pass count=" << nPass );
 298                         value_array<typename Stack::value_type> arrValue( s_nStackSize );
 299                         Stack testStack( nCompactFactor, nPass );
 300                         test( testStack, arrValue );
 301                     }
 302                 }
 303             }
 304             else {
 305                 if ( s_nFCCompactFactor && s_nFCCombinePassCount ) {
 306                     CPPUNIT_MSG( "Compact factor=" << s_nFCCompactFactor << ", combine pass count=" << s_nFCCombinePassCount );
 307                     value_array<typename Stack::value_type> arrValue( s_nStackSize );
 308                     Stack testStack( s_nFCCompactFactor, s_nFCCombinePassCount );
 309                     test( testStack, arrValue );
 310                 }
 311                 else {
 312                     value_array<typename Stack::value_type> arrValue( s_nStackSize );
 313                     Stack testStack;
 314                     test( testStack, arrValue );
 315                 }
 316             }
 317         }
 318
 319         // Unbounded elimination stack test
 320         template <class Stack>
 321         void test_elimination()
 322         {
 323             value_array<typename Stack::value_type> arrValue( s_nStackSize );
 324             {
 325                 Stack testStack( s_nEliminationSize );
 326                 test( testStack, arrValue );
 327                 check_elimination_stat( testStack.statistics() );
 328             }
 329             Stack::gc::force_dispose();
 330         }
 331         void check_elimination_stat( cds::intrusive::treiber_stack::empty_stat const& )
 332         {}
 333         void check_elimination_stat( cds::intrusive::treiber_stack::stat<> const& s )
 334         {
 335             CPPUNIT_CHECK( s.m_PushCount.get() + s.m_ActivePushCollision.get() + s.m_PassivePushCollision.get() == s_nStackSize );
 336             CPPUNIT_CHECK( s.m_PopCount.get() + s.m_ActivePopCollision.get() + s.m_PassivePopCollision.get() == s_nStackSize );
 337             CPPUNIT_CHECK( s.m_PushCount.get() == s.m_PopCount.get() );
 338             CPPUNIT_CHECK( s.m_ActivePopCollision.get() == s.m_PassivePushCollision.get() );
 339             CPPUNIT_CHECK( s.m_ActivePushCollision.get() == s.m_PassivePopCollision.get() );
 340         }
 341
 342         // Bounded stack test
 343         template <class Stack>
 344         void test_bounded()
 345         {
 346             value_array<typename Stack::value_type> arrValue( s_nStackSize );
 347             Stack testStack( s_nStackSize );
 348             test( testStack, arrValue );
 349         }
 350
 351         template <class Stack>
 352         void test_stdstack()
 353         {
 354             value_array<typename Stack::value_type> arrValue( s_nStackSize );
 355             Stack testStack;
 356             test( testStack, arrValue );
 357         }
 358
 359     protected:
 360 #   include "stack/intrusive_stack_defs.h"
 361         CDSUNIT_DECLARE_TreiberStack
 362         CDSUNIT_DECLARE_EliminationStack
 363         CDSUNIT_DECLARE_FCStack
 364         CDSUNIT_DECLARE_StdStack
 365
 366         CPPUNIT_TEST_SUITE(IntrusiveStack_PushPop)
 367             CDSUNIT_TEST_TreiberStack
 368             CDSUNIT_TEST_EliminationStack
 369             CDSUNIT_TEST_FCStack
 370             CDSUNIT_TEST_StdStack
 371         CPPUNIT_TEST_SUITE_END();
 372     };
 373 } // namespace istack
 374
 375 CPPUNIT_TEST_SUITE_REGISTRATION(istack::IntrusiveStack_PushPop);