3 #include "cppunit/thread.h"
4 #include "stack/stack_type.h"
5 #include "print_deque_stat.h"
7 // Multi-threaded stack test for push/pop operation
10 #define TEST_CASE( Q ) void Q() { test_unbounded< Types<SimpleValue>::Q >(); }
11 #define TEST_ELIMINATION( Q ) void Q() { test_elimination< Types<SimpleValue>::Q >(); }
12 #define TEST_BOUNDED( Q ) void Q() { test_bounded< Types<SimpleValue>::Q >(); }
15 static size_t s_nPushThreadCount = 4;
16 static size_t s_nPopThreadCount = 4;
17 static size_t s_nStackSize = 1000000;
18 static size_t s_nEliminationSize = 4;
24 SimpleValue(): nNo(0), nThread(0) {}
25 SimpleValue( size_t n ): nNo(n), nThread(0) {}
26 size_t getNo() const { return nNo; }
30 class Stack_PushPop: public CppUnitMini::TestCase
32 atomics::atomic<size_t> m_nWorkingProducers;
33 static size_t const c_nValArraySize = 1024;
35 template <class Stack>
36 class Pusher: public CppUnitMini::TestThread
38 virtual TestThread * clone()
40 return new Pusher( *this );
46 size_t m_arrPush[c_nValArraySize];
49 Pusher( CppUnitMini::ThreadPool& pool, Stack& s )
50 : CppUnitMini::TestThread( pool )
54 : CppUnitMini::TestThread( src )
55 , m_Stack( src.m_Stack )
58 Stack_PushPop& getTest()
60 return reinterpret_cast<Stack_PushPop&>( m_Pool.m_Test );
65 cds::threading::Manager::attachThread();
69 cds::threading::Manager::detachThread();
75 memset( m_arrPush, 0, sizeof(m_arrPush));
78 v.nThread = m_nThreadNo;
79 for ( size_t i = 0; i < m_nItemCount; ++i ) {
80 v.nNo = i % c_nValArraySize;
81 if ( m_Stack.push( v ))
88 getTest().m_nWorkingProducers.fetch_sub(1, atomics::memory_order_release);
92 template <class Stack>
93 class Popper: public CppUnitMini::TestThread
95 virtual TestThread * clone()
97 return new Popper( *this );
103 size_t m_arrPop[c_nValArraySize];
106 Popper( CppUnitMini::ThreadPool& pool, Stack& s )
107 : CppUnitMini::TestThread( pool )
110 Popper( Popper& src )
111 : CppUnitMini::TestThread( src )
112 , m_Stack( src.m_Stack )
115 Stack_PushPop& getTest()
117 return reinterpret_cast<Stack_PushPop&>( m_Pool.m_Test );
122 cds::threading::Manager::attachThread();
126 cds::threading::Manager::detachThread();
134 memset( m_arrPop, 0, sizeof(m_arrPop));
137 while ( !(getTest().m_nWorkingProducers.load(atomics::memory_order_acquire) == 0 && m_Stack.empty()) ) {
138 if ( m_Stack.pop( v )) {
140 if ( v.nNo < sizeof(m_arrPop)/sizeof(m_arrPop[0]) )
152 void setUpParams( const CppUnitMini::TestCfg& cfg ) {
153 s_nPushThreadCount = cfg.getULong("PushThreadCount", 4 );
154 s_nPopThreadCount = cfg.getULong("PopThreadCount", 4 );
155 s_nStackSize = cfg.getULong("StackSize", 1000000 );
156 s_nEliminationSize = cfg.getULong("EliminationSize", 4 );
159 template <class Stack>
160 void analyze( CppUnitMini::ThreadPool& pool, Stack& testStack )
162 size_t nPushError = 0;
163 size_t nPopEmpty = 0;
164 size_t nPopCount = 0;
165 size_t arrVal[c_nValArraySize];
166 memset( arrVal, 0, sizeof(arrVal));
167 size_t nDirtyPop = 0;
169 for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
170 CppUnitMini::TestThread * pThread = *it;
171 Pusher<Stack> * pPusher = dynamic_cast< Pusher<Stack> *>( pThread );
173 nPushError += pPusher->m_nPushError;
174 for ( size_t i = 0; i < sizeof(arrVal)/sizeof(arrVal[0]); ++i )
175 arrVal[i] += pPusher->m_arrPush[i];
178 Popper<Stack> * pPopper = dynamic_cast<Popper<Stack> *>( pThread );
180 nPopEmpty += pPopper->m_nPopEmpty;
181 nPopCount += pPopper->m_nPopCount;
182 nDirtyPop += pPopper->m_nDirtyPop;
183 for ( size_t i = 0; i < sizeof(arrVal)/sizeof(arrVal[0]); ++i )
184 arrVal[i] -= pPopper->m_arrPop[i];
188 CPPUNIT_MSG( "Push count=" << s_nStackSize
189 << " push error=" << nPushError
190 << " pop count=" << nPopCount
191 << " pop empty=" << nPopEmpty
192 << " dirty pop=" << nDirtyPop
194 CPPUNIT_CHECK( nPopCount == s_nStackSize );
195 CPPUNIT_CHECK( nDirtyPop == 0 );
196 for ( size_t i = 0; i < sizeof(arrVal)/sizeof(arrVal[0]); ++i ) {
197 CPPUNIT_CHECK_EX( arrVal[i] == 0, "arrVal[" << i << "]=" << long(arrVal[i]) );
201 // Unbounded stack test
202 template <class Stack>
203 void test_unbounded()
209 // Unbounded elimination stack test
210 template <class Stack>
211 void test_elimination()
213 Stack testStack( s_nEliminationSize );
215 check_elimination_stat( testStack.statistics() );
217 void check_elimination_stat( cds::container::treiber_stack::empty_stat const& )
219 void check_elimination_stat( cds::container::treiber_stack::stat<> const& s )
221 CPPUNIT_CHECK( s.m_PushCount.get() + s.m_ActivePushCollision.get() + s.m_PassivePushCollision.get() == s_nStackSize );
222 CPPUNIT_CHECK( s.m_PopCount.get() + s.m_ActivePopCollision.get() + s.m_PassivePopCollision.get() == s_nStackSize );
223 CPPUNIT_CHECK( s.m_PushCount.get() == s.m_PopCount.get() );
224 CPPUNIT_CHECK( s.m_ActivePopCollision.get() == s.m_PassivePushCollision.get() );
225 CPPUNIT_CHECK( s.m_ActivePushCollision.get() == s.m_PassivePopCollision.get() );
228 // Bounded stack test
229 template <class Stack>
232 Stack testStack( s_nStackSize );
236 template <class Stack>
237 void test( Stack& testStack )
239 m_nWorkingProducers.store(s_nPushThreadCount, atomics::memory_order_release);
240 size_t const nPushCount = s_nStackSize / s_nPushThreadCount;
242 CppUnitMini::ThreadPool pool( *this );
243 pool.add( new Pusher<Stack>( pool, testStack ), s_nPushThreadCount );
244 for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it )
245 static_cast<Pusher<Stack>* >( *it )->m_nItemCount = nPushCount;
246 pool.add( new Popper<Stack>( pool, testStack ), s_nPopThreadCount );
248 CPPUNIT_MSG( " Push/Pop test, push thread count=" << s_nPushThreadCount
249 << " pop thread count=" << s_nPopThreadCount
250 << " items=" << (nPushCount * s_nPushThreadCount)
253 CPPUNIT_MSG( " Duration=" << pool.avgDuration() );
255 s_nStackSize = nPushCount * s_nPushThreadCount;
256 analyze( pool, testStack );
257 CPPUNIT_MSG( testStack.statistics() );
261 # include "stack/stack_defs.h"
262 CDSUNIT_DECLARE_TreiberStack
263 CDSUNIT_DECLARE_EliminationStack
264 CDSUNIT_DECLARE_FCStack
265 CDSUNIT_DECLARE_FCDeque
266 CDSUNIT_DECLARE_MichaelDeque
267 CDSUNIT_DECLARE_StdStack
269 CPPUNIT_TEST_SUITE(Stack_PushPop)
270 CDSUNIT_TEST_TreiberStack
271 CDSUNIT_TEST_EliminationStack
274 CDSUNIT_TEST_MichaelDeque
275 CDSUNIT_TEST_StdStack
276 CPPUNIT_TEST_SUITE_END();
280 CPPUNIT_TEST_SUITE_REGISTRATION(stack::Stack_PushPop);