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 CDS_TSAN_ANNOTATE_IGNORE_WRITES_BEGIN;
153 p->nConsumer = m_nThreadNo;
155 if ( p->nNo < sizeof(m_arrPop)/sizeof(m_arrPop[0]) )
159 CDS_TSAN_ANNOTATE_IGNORE_WRITES_END;
167 template <typename T>
172 value_array( size_t nSize )
173 : m_pArr( new T[nSize] )
181 T * get() const { return m_pArr; }
185 void setUpParams( const CppUnitMini::TestCfg& cfg ) {
186 s_nPushThreadCount = cfg.getULong("PushThreadCount", 4 );
187 s_nPopThreadCount = cfg.getULong("PopThreadCount", 4 );
188 s_nStackSize = cfg.getULong("StackSize", 1000000 );
189 s_nEliminationSize = cfg.getULong("EliminationSize", 4 );
190 s_bFCIterative = cfg.getBool( "FCIterate", false );
191 s_nFCCombinePassCount = cfg.getUInt( "FCCombinePassCount", 64 );
192 s_nFCCompactFactor = cfg.getUInt( "FCCompactFactor", 1024 );
195 template <class Stack>
196 void analyze( CppUnitMini::ThreadPool& pool, Stack& /*testStack*/ )
198 size_t nPushError = 0;
199 size_t nPopEmpty = 0;
200 size_t nPopCount = 0;
201 size_t arrVal[c_nValArraySize];
202 memset( arrVal, 0, sizeof(arrVal));
203 size_t nDirtyPop = 0;
205 for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
206 CppUnitMini::TestThread * pThread = *it;
207 Producer<Stack> * pPusher = dynamic_cast< Producer<Stack> *>( pThread );
209 nPushError += pPusher->m_nPushError;
210 for ( size_t i = 0; i < sizeof(arrVal)/sizeof(arrVal[0]); ++i )
211 arrVal[i] += pPusher->m_arrPush[i];
214 Consumer<Stack> * pPopper = dynamic_cast<Consumer<Stack> *>( pThread );
216 nPopEmpty += pPopper->m_nPopEmpty;
217 nPopCount += pPopper->m_nPopCount;
218 nDirtyPop += pPopper->m_nDirtyPop;
219 for ( size_t i = 0; i < sizeof(arrVal)/sizeof(arrVal[0]); ++i )
220 arrVal[i] -= pPopper->m_arrPop[i];
224 CPPUNIT_MSG( "Push count=" << s_nStackSize
225 << " push error=" << nPushError
226 << " pop count=" << nPopCount
227 << " pop empty=" << nPopEmpty
228 << " dirty pop=" << nDirtyPop
230 CPPUNIT_CHECK( nPopCount == s_nStackSize );
231 CPPUNIT_CHECK( nDirtyPop == 0 );
232 for ( size_t i = 0; i < sizeof(arrVal)/sizeof(arrVal[0]); ++i ) {
233 CPPUNIT_CHECK_EX( arrVal[i] == 0, "arrVal[" << i << "]=" << long(arrVal[i]) );
237 template <class Stack>
238 void test( Stack& testStack, value_array<typename Stack::value_type>& arrValue )
240 m_nWorkingProducers.store( s_nPushThreadCount, atomics::memory_order_release );
241 size_t const nPushCount = s_nStackSize / s_nPushThreadCount;
243 typename Stack::value_type * pValStart = arrValue.get();
244 typename Stack::value_type * pValEnd = pValStart + s_nStackSize;
246 CppUnitMini::ThreadPool pool( *this );
247 pool.add( new Producer<Stack>( pool, testStack ), s_nPushThreadCount );
249 for ( typename Stack::value_type * it = pValStart; it != pValEnd; ++it )
250 it->nConsumer = c_nBadConsumer;
252 typename Stack::value_type * pStart = pValStart;
253 for ( CppUnitMini::ThreadPool::iterator it = pool.begin(); it != pool.end(); ++it ) {
254 static_cast<Producer<Stack>* >( *it )->m_pStart = pStart;
255 pStart += nPushCount;
256 static_cast<Producer<Stack>* >( *it )->m_pEnd = pStart;
259 pool.add( new Consumer<Stack>( pool, testStack ), s_nPopThreadCount );
261 CPPUNIT_MSG( " Push/Pop test, push thread count=" << s_nPushThreadCount
262 << " pop thread count=" << s_nPopThreadCount
263 << " items=" << (nPushCount * s_nPushThreadCount)
266 CPPUNIT_MSG( " Duration=" << pool.avgDuration() );
268 s_nStackSize = nPushCount * s_nPushThreadCount;
271 typename Stack::value_type * pEnd = pValStart + s_nStackSize;
272 for ( typename Stack::value_type * it = pValStart; it != pEnd; ++it )
273 CPPUNIT_CHECK( it->nConsumer != c_nBadConsumer );
276 analyze( pool, testStack );
277 CPPUNIT_MSG( testStack.statistics() );
281 // Unbounded stack test
282 template <class Stack>
283 void test_unbounded()
285 value_array<typename Stack::value_type> arrValue( s_nStackSize );
288 test( testStack, arrValue );
290 Stack::gc::force_dispose();
293 template <class Stack>
296 if ( s_bFCIterative ) {
297 for (unsigned int nCompactFactor = 1; nCompactFactor <= s_nFCCompactFactor; nCompactFactor *= 2 ) {
298 for ( unsigned int nPass = 1; nPass <= s_nFCCombinePassCount; nPass *= 2 ) {
299 CPPUNIT_MSG( "Compact factor=" << nCompactFactor << ", combine pass count=" << nPass );
300 value_array<typename Stack::value_type> arrValue( s_nStackSize );
301 Stack testStack( nCompactFactor, nPass );
302 test( testStack, arrValue );
307 if ( s_nFCCompactFactor && s_nFCCombinePassCount ) {
308 CPPUNIT_MSG( "Compact factor=" << s_nFCCompactFactor << ", combine pass count=" << s_nFCCombinePassCount );
309 value_array<typename Stack::value_type> arrValue( s_nStackSize );
310 Stack testStack( s_nFCCompactFactor, s_nFCCombinePassCount );
311 test( testStack, arrValue );
314 value_array<typename Stack::value_type> arrValue( s_nStackSize );
316 test( testStack, arrValue );
321 // Unbounded elimination stack test
322 template <class Stack>
323 void test_elimination()
325 value_array<typename Stack::value_type> arrValue( s_nStackSize );
327 Stack testStack( s_nEliminationSize );
328 test( testStack, arrValue );
329 check_elimination_stat( testStack.statistics() );
331 Stack::gc::force_dispose();
333 void check_elimination_stat( cds::intrusive::treiber_stack::empty_stat const& )
335 void check_elimination_stat( cds::intrusive::treiber_stack::stat<> const& s )
337 CPPUNIT_CHECK( s.m_PushCount.get() + s.m_ActivePushCollision.get() + s.m_PassivePushCollision.get() == s_nStackSize );
338 CPPUNIT_CHECK( s.m_PopCount.get() + s.m_ActivePopCollision.get() + s.m_PassivePopCollision.get() == s_nStackSize );
339 CPPUNIT_CHECK( s.m_PushCount.get() == s.m_PopCount.get() );
340 CPPUNIT_CHECK( s.m_ActivePopCollision.get() == s.m_PassivePushCollision.get() );
341 CPPUNIT_CHECK( s.m_ActivePushCollision.get() == s.m_PassivePopCollision.get() );
344 // Bounded stack test
345 template <class Stack>
348 value_array<typename Stack::value_type> arrValue( s_nStackSize );
349 Stack testStack( s_nStackSize );
350 test( testStack, arrValue );
353 template <class Stack>
356 value_array<typename Stack::value_type> arrValue( s_nStackSize );
358 test( testStack, arrValue );
362 # include "stack/intrusive_stack_defs.h"
363 CDSUNIT_DECLARE_TreiberStack
364 CDSUNIT_DECLARE_EliminationStack
365 CDSUNIT_DECLARE_FCStack
366 CDSUNIT_DECLARE_StdStack
368 CPPUNIT_TEST_SUITE(IntrusiveStack_PushPop)
369 CDSUNIT_TEST_TreiberStack
370 CDSUNIT_TEST_EliminationStack
372 CDSUNIT_TEST_StdStack
373 CPPUNIT_TEST_SUITE_END();
375 } // namespace istack
377 CPPUNIT_TEST_SUITE_REGISTRATION(istack::IntrusiveStack_PushPop);