3 #include "cppunit/thread.h"
4 #include "stack/intrusive_stack_type.h"
6 // Multi-threaded stack test for push/pop operation
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 >(); }
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;
26 template <typename Base = empty >
27 struct SimpleValue: public Base
34 SimpleValue( size_t n ): nNo(n) {}
35 size_t getNo() const { return nNo; }
40 class IntrusiveStack_PushPop: public CppUnitMini::TestCase
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;
46 template <class Stack>
47 class Producer: public CppUnitMini::TestThread
49 virtual TestThread * clone()
51 return new Producer( *this );
56 size_t m_arrPush[c_nValArraySize];
58 // Interval in m_arrValue
59 typename Stack::value_type * m_pStart;
60 typename Stack::value_type * m_pEnd;
63 Producer( CppUnitMini::ThreadPool& pool, Stack& s )
64 : CppUnitMini::TestThread( pool )
67 Producer( Producer& src )
68 : CppUnitMini::TestThread( src )
69 , m_Stack( src.m_Stack )
72 IntrusiveStack_PushPop& getTest()
74 return static_cast<IntrusiveStack_PushPop&>( m_Pool.m_Test );
79 cds::threading::Manager::attachThread();
83 cds::threading::Manager::detachThread();
89 memset( m_arrPush, 0, sizeof(m_arrPush));
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 ];
101 getTest().m_nWorkingProducers.fetch_sub( 1, atomics::memory_order_release );
105 template <class Stack>
106 class Consumer: public CppUnitMini::TestThread
108 virtual TestThread * clone()
110 return new Consumer( *this );
116 size_t m_arrPop[c_nValArraySize];
119 Consumer( CppUnitMini::ThreadPool& pool, Stack& s )
120 : CppUnitMini::TestThread( pool )
123 Consumer( Consumer& src )
124 : CppUnitMini::TestThread( src )
125 , m_Stack( src.m_Stack )
128 IntrusiveStack_PushPop& getTest()
130 return static_cast<IntrusiveStack_PushPop&>( m_Pool.m_Test );
135 cds::threading::Manager::attachThread();
139 cds::threading::Manager::detachThread();
147 memset( m_arrPop, 0, sizeof(m_arrPop));
149 while ( !(getTest().m_nWorkingProducers.load(atomics::memory_order_acquire) == 0 && m_Stack.empty()) ) {
150 typename Stack::value_type * p = m_Stack.pop();
152 p->nConsumer = m_nThreadNo;
154 if ( p->nNo < sizeof(m_arrPop)/sizeof(m_arrPop[0]) )
165 template <typename T>
170 value_array( size_t nSize )
171 : m_pArr( new T[nSize] )
179 T * get() const { return m_pArr; }
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 );
193 template <class Stack>
194 void analyze( CppUnitMini::ThreadPool& pool, Stack& testStack )
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;
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 );
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];
212 Consumer<Stack> * pPopper = dynamic_cast<Consumer<Stack> *>( pThread );
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];
222 CPPUNIT_MSG( "Push count=" << s_nStackSize
223 << " push error=" << nPushError
224 << " pop count=" << nPopCount
225 << " pop empty=" << nPopEmpty
226 << " dirty pop=" << nDirtyPop
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]) );
235 template <class Stack>
236 void test( Stack& testStack, value_array<typename Stack::value_type>& arrValue )
238 m_nWorkingProducers.store( s_nPushThreadCount, atomics::memory_order_release );
239 size_t const nPushCount = s_nStackSize / s_nPushThreadCount;
241 typename Stack::value_type * pValStart = arrValue.get();
242 typename Stack::value_type * pValEnd = pValStart + s_nStackSize;
244 CppUnitMini::ThreadPool pool( *this );
245 pool.add( new Producer<Stack>( pool, testStack ), s_nPushThreadCount );
247 for ( typename Stack::value_type * it = pValStart; it != pValEnd; ++it )
248 it->nConsumer = c_nBadConsumer;
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;
257 pool.add( new Consumer<Stack>( pool, testStack ), s_nPopThreadCount );
259 CPPUNIT_MSG( " Push/Pop test, push thread count=" << s_nPushThreadCount
260 << " pop thread count=" << s_nPopThreadCount
261 << " items=" << (nPushCount * s_nPushThreadCount)
264 CPPUNIT_MSG( " Duration=" << pool.avgDuration() );
266 s_nStackSize = nPushCount * s_nPushThreadCount;
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 );
274 analyze( pool, testStack );
275 CPPUNIT_MSG( testStack.statistics() );
279 // Unbounded stack test
280 template <class Stack>
281 void test_unbounded()
283 value_array<typename Stack::value_type> arrValue( s_nStackSize );
286 test( testStack, arrValue );
288 Stack::gc::force_dispose();
291 template <class Stack>
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 );
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 );
312 value_array<typename Stack::value_type> arrValue( s_nStackSize );
314 test( testStack, arrValue );
319 // Unbounded elimination stack test
320 template <class Stack>
321 void test_elimination()
323 value_array<typename Stack::value_type> arrValue( s_nStackSize );
325 Stack testStack( s_nEliminationSize );
326 test( testStack, arrValue );
327 check_elimination_stat( testStack.statistics() );
329 Stack::gc::force_dispose();
331 void check_elimination_stat( cds::intrusive::treiber_stack::empty_stat const& )
333 void check_elimination_stat( cds::intrusive::treiber_stack::stat<> const& s )
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() );
342 // Bounded stack test
343 template <class Stack>
346 value_array<typename Stack::value_type> arrValue( s_nStackSize );
347 Stack testStack( s_nStackSize );
348 test( testStack, arrValue );
351 template <class Stack>
354 value_array<typename Stack::value_type> arrValue( s_nStackSize );
356 test( testStack, arrValue );
360 # include "stack/intrusive_stack_defs.h"
361 CDSUNIT_DECLARE_TreiberStack
362 CDSUNIT_DECLARE_EliminationStack
363 CDSUNIT_DECLARE_FCStack
364 CDSUNIT_DECLARE_StdStack
366 CPPUNIT_TEST_SUITE(IntrusiveStack_PushPop)
367 CDSUNIT_TEST_TreiberStack
368 CDSUNIT_TEST_EliminationStack
370 CDSUNIT_TEST_StdStack
371 CPPUNIT_TEST_SUITE_END();
373 } // namespace istack
375 CPPUNIT_TEST_SUITE_REGISTRATION(istack::IntrusiveStack_PushPop);