tests/unit/stack/stack_pushpop.cpp

   1 //$$CDS-header$$
   2
   3 #include "cppunit/thread.h"
   4 #include "stack/stack_type.h"
   5
   6 // Multi-threaded stack test for push/pop operation
   7 namespace stack {
   8
   9 #define TEST_CASE( Q ) void Q()          { test_unbounded< Types<SimpleValue>::Q >(); }
  10 #define TEST_ELIMINATION( Q ) void Q()   { test_elimination< Types<SimpleValue>::Q >(); }
  11 #define TEST_BOUNDED( Q ) void Q()       { test_bounded< Types<SimpleValue>::Q >(); }
  12
  13     namespace {
  14         static size_t s_nPushThreadCount = 4;
  15         static size_t s_nPopThreadCount = 4;
  16         static size_t s_nStackSize = 1000000;
  17         static size_t s_nEliminationSize = 4;
  18
  19         struct SimpleValue {
  20             size_t      nNo;
  21             size_t      nThread;
  22
  23             SimpleValue(): nNo(0), nThread(0) {}
  24             SimpleValue( size_t n ): nNo(n), nThread(0) {}
  25             size_t getNo() const { return  nNo; }
  26         };
  27     }
  28
  29     class Stack_PushPop: public CppUnitMini::TestCase
  30     {
  31         atomics::atomic<size_t>  m_nWorkingProducers;
  32         static size_t const c_nValArraySize = 1024;
  33
  34         template <class Stack>
  35         class Pusher: public CppUnitMini::TestThread
  36         {
  37             virtual TestThread *    clone()
  38             {
  39                 return new Pusher( *this );
  40             }
  41         public:
  42             Stack&              m_Stack;
  43             size_t              m_nItemCount;
  44             size_t              m_nPushError;
  45             size_t              m_arrPush[c_nValArraySize];
  46
  47         public:
  48             Pusher( CppUnitMini::ThreadPool& pool, Stack& s )
  49                 : CppUnitMini::TestThread( pool )
  50                 , m_Stack( s )
  51             {}
  52             Pusher( Pusher& src )
  53                 : CppUnitMini::TestThread( src )
  54                 , m_Stack( src.m_Stack )
  55             {}
  56
  57             Stack_PushPop&  getTest()
  58             {
  59                 return reinterpret_cast<Stack_PushPop&>( m_Pool.m_Test );
  60             }
  61
  62             virtual void init()
  63             {
  64                 cds::threading::Manager::attachThread();
  65             }
  66             virtual void fini()
  67             {
  68                 cds::threading::Manager::detachThread();
  69             }
  70
  71             virtual void test()
  72             {
  73                 m_nPushError = 0;
  74                 memset( m_arrPush, 0, sizeof(m_arrPush));
  75
  76                 SimpleValue v;
  77                 v.nThread = m_nThreadNo;
  78                 for ( size_t i = 0; i < m_nItemCount; ++i ) {
  79                     v.nNo = i % c_nValArraySize;
  80                     if ( m_Stack.push( v ))
  81                         ++m_arrPush[v.nNo];
  82                     else
  83                         ++m_nPushError;
  84                 }
  85
  86
  87                 getTest().m_nWorkingProducers.fetch_sub(1, atomics::memory_order_release);
  88             }
  89         };
  90
  91         template <class Stack>
  92         class Popper: public CppUnitMini::TestThread
  93         {
  94             virtual TestThread *    clone()
  95             {
  96                 return new Popper( *this );
  97             }
  98         public:
  99             Stack&              m_Stack;
 100             size_t              m_nPopCount;
 101             size_t              m_nPopEmpty;
 102             size_t              m_arrPop[c_nValArraySize];
 103             size_t              m_nDirtyPop;
 104         public:
 105             Popper( CppUnitMini::ThreadPool& pool, Stack& s )
 106                 : CppUnitMini::TestThread( pool )
 107                 , m_Stack( s )
 108             {}
 109             Popper( Popper& src )
 110                 : CppUnitMini::TestThread( src )
 111                 , m_Stack( src.m_Stack )
 112             {}
 113
 114             Stack_PushPop&  getTest()
 115             {
 116                 return reinterpret_cast<Stack_PushPop&>( m_Pool.m_Test );
 117             }
 118
 119             virtual void init()
 120             {
 121                 cds::threading::Manager::attachThread();
 122             }
 123             virtual void fini()
 124             {
 125                 cds::threading::Manager::detachThread();
 126             }
 127
 128             virtual void test()
 129             {
 130                 m_nPopEmpty = 0;
 131                 m_nPopCount = 0;
 132                 m_nDirtyPop = 0;
 133                 memset( m_arrPop, 0, sizeof(m_arrPop));
 134
 135                 SimpleValue v;
 136                 while ( !(getTest().m_nWorkingProducers.load(atomics::memory_order_acquire) == 0 && m_Stack.empty()) ) {
 137                     if ( m_Stack.pop( v )) {
 138                         ++m_nPopCount;
 139                         if ( v.nNo < sizeof(m_arrPop)/sizeof(m_arrPop[0]) )
 140                             ++m_arrPop[v.nNo];
 141                         else
 142                             ++m_nDirtyPop;
 143                     }
 144                     else
 145                         ++m_nPopEmpty;
 146                 }
 147             }
 148         };
 149
 150     protected:
 151         void setUpParams( const CppUnitMini::TestCfg& cfg ) {
 152             s_nPushThreadCount = cfg.getULong("PushThreadCount", 4 );
 153             s_nPopThreadCount = cfg.getULong("PopThreadCount", 4 );
 154             s_nStackSize = cfg.getULong("StackSize", 1000000 );
 155             s_nEliminationSize = cfg.getULong("EliminationSize", 4 );
 156         }
 157
 158         template <class Stack>
 159         void analyze( CppUnitMini::ThreadPool& pool, Stack& /*testStack*/  )
 160         {
 161             size_t nPushError = 0;
 162             size_t nPopEmpty = 0;
 163             size_t nPopCount = 0;
 164             size_t arrVal[c_nValArraySize];
 165             memset( arrVal, 0, sizeof(arrVal));
 166             size_t nDirtyPop = 0;
 167
 168             for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
 169                 CppUnitMini::TestThread * pThread = *it;
 170                 Pusher<Stack> * pPusher = dynamic_cast< Pusher<Stack> *>( pThread );
 171                 if ( pPusher ) {
 172                     nPushError += pPusher->m_nPushError;
 173                     for ( size_t i = 0; i < sizeof(arrVal)/sizeof(arrVal[0]); ++i )
 174                         arrVal[i] += pPusher->m_arrPush[i];
 175                 }
 176                 else {
 177                     Popper<Stack> * pPopper = dynamic_cast<Popper<Stack> *>( pThread );
 178                     assert( pPopper );
 179                     nPopEmpty += pPopper->m_nPopEmpty;
 180                     nPopCount += pPopper->m_nPopCount;
 181                     nDirtyPop += pPopper->m_nDirtyPop;
 182                     for ( size_t i = 0; i < sizeof(arrVal)/sizeof(arrVal[0]); ++i )
 183                         arrVal[i] -= pPopper->m_arrPop[i];
 184                 }
 185             }
 186
 187             CPPUNIT_MSG( "Push count=" << s_nStackSize
 188                 << " push error=" << nPushError
 189                 << " pop count=" << nPopCount
 190                 << " pop empty=" << nPopEmpty
 191                 << " dirty pop=" << nDirtyPop
 192                 );
 193             CPPUNIT_CHECK( nPopCount == s_nStackSize );
 194             CPPUNIT_CHECK( nDirtyPop == 0 );
 195             for ( size_t i = 0; i < sizeof(arrVal)/sizeof(arrVal[0]); ++i ) {
 196                 CPPUNIT_CHECK_EX( arrVal[i] == 0, "arrVal[" << i << "]=" << long(arrVal[i]) );
 197             }
 198         }
 199
 200         // Unbounded stack test
 201         template <class Stack>
 202         void test_unbounded()
 203         {
 204             Stack testStack;
 205             test( testStack );
 206         }
 207
 208         // Unbounded elimination stack test
 209         template <class Stack>
 210         void test_elimination()
 211         {
 212             Stack testStack( s_nEliminationSize );
 213             test( testStack );
 214             check_elimination_stat( testStack.statistics() );
 215         }
 216         void check_elimination_stat( cds::container::treiber_stack::empty_stat const& )
 217         {}
 218         void check_elimination_stat( cds::container::treiber_stack::stat<> const& s )
 219         {
 220             CPPUNIT_CHECK( s.m_PushCount.get() + s.m_ActivePushCollision.get() + s.m_PassivePushCollision.get() == s_nStackSize );
 221             CPPUNIT_CHECK( s.m_PopCount.get() + s.m_ActivePopCollision.get() + s.m_PassivePopCollision.get() == s_nStackSize );
 222             CPPUNIT_CHECK( s.m_PushCount.get() == s.m_PopCount.get() );
 223             CPPUNIT_CHECK( s.m_ActivePopCollision.get() == s.m_PassivePushCollision.get() );
 224             CPPUNIT_CHECK( s.m_ActivePushCollision.get() == s.m_PassivePopCollision.get() );
 225         }
 226
 227         // Bounded stack test
 228         template <class Stack>
 229         void test_bounded()
 230         {
 231             Stack testStack( s_nStackSize );
 232             test( testStack );
 233         }
 234
 235         template <class Stack>
 236         void test( Stack& testStack )
 237         {
 238             m_nWorkingProducers.store(s_nPushThreadCount, atomics::memory_order_release);
 239             size_t const nPushCount = s_nStackSize / s_nPushThreadCount;
 240
 241             CppUnitMini::ThreadPool pool( *this );
 242             pool.add( new Pusher<Stack>( pool, testStack ), s_nPushThreadCount );
 243             for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it )
 244                 static_cast<Pusher<Stack>* >( *it )->m_nItemCount = nPushCount;
 245             pool.add( new Popper<Stack>( pool, testStack ), s_nPopThreadCount );
 246
 247             CPPUNIT_MSG( "   Push/Pop test, push thread count=" << s_nPushThreadCount
 248                 << " pop thread count=" << s_nPopThreadCount
 249                 << " items=" << (nPushCount * s_nPushThreadCount)
 250                 << "...");
 251             pool.run();
 252             CPPUNIT_MSG( "   Duration=" << pool.avgDuration() );
 253
 254             s_nStackSize = nPushCount * s_nPushThreadCount;
 255             analyze( pool, testStack );
 256             CPPUNIT_MSG( testStack.statistics() );
 257         }
 258
 259     protected:
 260 #   include "stack/stack_defs.h"
 261         CDSUNIT_DECLARE_TreiberStack
 262         CDSUNIT_DECLARE_EliminationStack
 263         CDSUNIT_DECLARE_FCStack
 264         CDSUNIT_DECLARE_FCDeque
 265         CDSUNIT_DECLARE_StdStack
 266
 267         CPPUNIT_TEST_SUITE(Stack_PushPop)
 268             CDSUNIT_TEST_TreiberStack
 269             CDSUNIT_TEST_EliminationStack
 270             CDSUNIT_TEST_FCStack
 271             CDSUNIT_TEST_FCDeque
 272             CDSUNIT_TEST_StdStack
 273         CPPUNIT_TEST_SUITE_END();
 274     };
 275 } // namespace stack
 276
 277 CPPUNIT_TEST_SUITE_REGISTRATION(stack::Stack_PushPop);