3 #include "cppunit/thread.h"
4 #include "stack/stack_type.h"
6 // Multi-threaded stack test for push/pop operation
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 >(); }
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;
23 SimpleValue(): nNo(0), nThread(0) {}
24 SimpleValue( size_t n ): nNo(n), nThread(0) {}
25 size_t getNo() const { return nNo; }
29 class Stack_PushPop: public CppUnitMini::TestCase
31 atomics::atomic<size_t> m_nWorkingProducers;
32 static size_t const c_nValArraySize = 1024;
34 template <class Stack>
35 class Pusher: public CppUnitMini::TestThread
37 virtual TestThread * clone()
39 return new Pusher( *this );
45 size_t m_arrPush[c_nValArraySize];
48 Pusher( CppUnitMini::ThreadPool& pool, Stack& s )
49 : CppUnitMini::TestThread( pool )
53 : CppUnitMini::TestThread( src )
54 , m_Stack( src.m_Stack )
57 Stack_PushPop& getTest()
59 return reinterpret_cast<Stack_PushPop&>( m_Pool.m_Test );
64 cds::threading::Manager::attachThread();
68 cds::threading::Manager::detachThread();
74 memset( m_arrPush, 0, sizeof(m_arrPush));
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 ))
87 getTest().m_nWorkingProducers.fetch_sub(1, atomics::memory_order_release);
91 template <class Stack>
92 class Popper: public CppUnitMini::TestThread
94 virtual TestThread * clone()
96 return new Popper( *this );
102 size_t m_arrPop[c_nValArraySize];
105 Popper( CppUnitMini::ThreadPool& pool, Stack& s )
106 : CppUnitMini::TestThread( pool )
109 Popper( Popper& src )
110 : CppUnitMini::TestThread( src )
111 , m_Stack( src.m_Stack )
114 Stack_PushPop& getTest()
116 return reinterpret_cast<Stack_PushPop&>( m_Pool.m_Test );
121 cds::threading::Manager::attachThread();
125 cds::threading::Manager::detachThread();
133 memset( m_arrPop, 0, sizeof(m_arrPop));
136 while ( !(getTest().m_nWorkingProducers.load(atomics::memory_order_acquire) == 0 && m_Stack.empty()) ) {
137 if ( m_Stack.pop( v )) {
139 if ( v.nNo < sizeof(m_arrPop)/sizeof(m_arrPop[0]) )
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 );
158 template <class Stack>
159 void analyze( CppUnitMini::ThreadPool& pool, Stack& testStack )
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;
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 );
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];
177 Popper<Stack> * pPopper = dynamic_cast<Popper<Stack> *>( pThread );
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];
187 CPPUNIT_MSG( "Push count=" << s_nStackSize
188 << " push error=" << nPushError
189 << " pop count=" << nPopCount
190 << " pop empty=" << nPopEmpty
191 << " dirty pop=" << nDirtyPop
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]) );
200 // Unbounded stack test
201 template <class Stack>
202 void test_unbounded()
208 // Unbounded elimination stack test
209 template <class Stack>
210 void test_elimination()
212 Stack testStack( s_nEliminationSize );
214 check_elimination_stat( testStack.statistics() );
216 void check_elimination_stat( cds::container::treiber_stack::empty_stat const& )
218 void check_elimination_stat( cds::container::treiber_stack::stat<> const& s )
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() );
227 // Bounded stack test
228 template <class Stack>
231 Stack testStack( s_nStackSize );
235 template <class Stack>
236 void test( Stack& testStack )
238 m_nWorkingProducers.store(s_nPushThreadCount, atomics::memory_order_release);
239 size_t const nPushCount = s_nStackSize / s_nPushThreadCount;
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 );
247 CPPUNIT_MSG( " Push/Pop test, push thread count=" << s_nPushThreadCount
248 << " pop thread count=" << s_nPopThreadCount
249 << " items=" << (nPushCount * s_nPushThreadCount)
252 CPPUNIT_MSG( " Duration=" << pool.avgDuration() );
254 s_nStackSize = nPushCount * s_nPushThreadCount;
255 analyze( pool, testStack );
256 CPPUNIT_MSG( testStack.statistics() );
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
267 CPPUNIT_TEST_SUITE(Stack_PushPop)
268 CDSUNIT_TEST_TreiberStack
269 CDSUNIT_TEST_EliminationStack
272 CDSUNIT_TEST_StdStack
273 CPPUNIT_TEST_SUITE_END();
277 CPPUNIT_TEST_SUITE_REGISTRATION(stack::Stack_PushPop);