2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
6 Source code repo: http://github.com/khizmax/libcds/
7 Download: http://sourceforge.net/projects/libcds/files/
9 Redistribution and use in source and binary forms, with or without
10 modification, are permitted provided that the following conditions are met:
12 * Redistributions of source code must retain the above copyright notice, this
13 list of conditions and the following disclaimer.
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
32 #include <cds_test/city.h>
36 // Test for set's thread-safe iterator:
37 // Several thread inserts/erases elemets from the set.
38 // Dedicated Iterator thread iterates over the set, calculates CityHash for each element
39 // and stores it in the element.
40 // Test goal: no crash
42 #define TEST_CASE(TAG, X) void X();
44 class Set_Iteration: public cds_test::stress_fixture
47 static size_t s_nSetSize; // set size
48 static size_t s_nInsertThreadCount; // count of insertion thread
49 static size_t s_nDeleteThreadCount; // count of deletion thread
50 static size_t s_nThreadPassCount; // pass count for each thread
51 static size_t s_nMaxLoadFactor; // maximum load factor
53 static size_t s_nCuckooInitialSize; // initial size for CuckooSet
54 static size_t s_nCuckooProbesetSize; // CuckooSet probeset size (only for list-based probeset)
55 static size_t s_nCuckooProbesetThreshold; // CUckooSet probeset threshold (0 - use default)
57 static size_t s_nFeldmanSet_HeadBits;
58 static size_t s_nFeldmanSet_ArrayBits;
60 static size_t s_nLoadFactor;
61 static std::vector<std::string> m_arrString;
63 static void SetUpTestCase();
64 static void TearDownTestCase();
66 void on_modifier_done()
68 m_nModifierCount.fetch_sub( 1, atomics::memory_order_relaxed );
71 bool all_modifiers_done() const
73 return m_nModifierCount.load( atomics::memory_order_relaxed ) == 0;
76 typedef std::string key_type;
83 explicit value_type( size_t v )
97 atomics::atomic<size_t> m_nModifierCount;
100 class Inserter: public cds_test::thread
102 typedef cds_test::thread base_class;
105 typedef typename Set::value_type keyval_type;
108 size_t m_nInsertSuccess = 0;
109 size_t m_nInsertFailed = 0;
112 Inserter( cds_test::thread_pool& pool, Set& set )
113 : base_class( pool, insert_thread )
117 Inserter( Inserter& src )
122 virtual thread * clone()
124 return new Inserter( *this );
131 Set_Iteration& fixture = pool().template fixture<Set_Iteration>();
132 size_t nArrSize = m_arrString.size();
133 size_t const nSetSize = fixture.s_nSetSize;
134 size_t const nPassCount = fixture.s_nThreadPassCount;
137 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
138 for ( size_t nItem = 0; nItem < nSetSize; ++nItem ) {
139 if ( rSet.insert( keyval_type( m_arrString[nItem % nArrSize], nItem * 8 )))
147 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
148 for ( size_t nItem = nSetSize; nItem > 0; --nItem ) {
149 if ( rSet.insert( keyval_type( m_arrString[nItem % nArrSize], nItem * 8 )))
157 fixture.on_modifier_done();
162 class Deleter: public cds_test::thread
164 typedef cds_test::thread base_class;
168 size_t m_nDeleteSuccess = 0;
169 size_t m_nDeleteFailed = 0;
172 Deleter( cds_test::thread_pool& pool, Set& set )
173 : base_class( pool, delete_thread )
177 Deleter( Deleter& src )
182 virtual thread * clone()
184 return new Deleter( *this );
191 Set_Iteration& fixture = pool().template fixture<Set_Iteration>();
192 size_t nArrSize = m_arrString.size();
193 size_t const nSetSize = fixture.s_nSetSize;
194 size_t const nPassCount = fixture.s_nThreadPassCount;
197 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
198 for ( size_t nItem = 0; nItem < nSetSize; ++nItem ) {
199 if ( rSet.erase( m_arrString[nItem % nArrSize] ))
207 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
208 for ( size_t nItem = nSetSize; nItem > 0; --nItem ) {
209 if ( rSet.erase( m_arrString[nItem % nArrSize] ))
217 fixture.on_modifier_done();
221 template <typename GC, class Set>
222 class Extractor: public cds_test::thread
224 typedef cds_test::thread base_class;
228 size_t m_nDeleteSuccess = 0;
229 size_t m_nDeleteFailed = 0;
232 Extractor( cds_test::thread_pool& pool, Set& set )
233 : base_class( pool, extract_thread )
237 Extractor( Extractor& src )
242 virtual thread * clone()
244 return new Extractor( *this );
251 typename Set::guarded_ptr gp;
253 Set_Iteration& fixture = pool().template fixture<Set_Iteration>();
254 size_t nArrSize = m_arrString.size();
255 size_t const nSetSize = fixture.s_nSetSize;
256 size_t const nPassCount = fixture.s_nThreadPassCount;
259 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
260 for ( size_t nItem = 0; nItem < nSetSize; ++nItem ) {
261 gp = rSet.extract( m_arrString[nItem % nArrSize] );
271 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
272 for ( size_t nItem = nSetSize; nItem > 0; --nItem ) {
273 gp = rSet.extract( m_arrString[nItem % nArrSize] );
283 fixture.on_modifier_done();
287 template <typename RCU, class Set>
288 class Extractor<cds::urcu::gc<RCU>, Set >: public cds_test::thread
290 typedef cds_test::thread base_class;
294 size_t m_nDeleteSuccess = 0;
295 size_t m_nDeleteFailed = 0;
298 Extractor( cds_test::thread_pool& pool, Set& set )
299 : base_class( pool, extract_thread )
303 Extractor( Extractor& src )
308 virtual thread * clone()
310 return new Extractor( *this );
317 typename Set::exempt_ptr xp;
319 Set_Iteration& fixture = pool().template fixture<Set_Iteration>();
320 size_t nArrSize = m_arrString.size();
321 size_t const nSetSize = fixture.s_nSetSize;
322 size_t const nPassCount = fixture.s_nThreadPassCount;
325 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
326 for ( size_t nItem = 0; nItem < nSetSize; ++nItem ) {
327 if ( Set::c_bExtractLockExternal ) {
328 typename Set::rcu_lock l;
329 xp = rSet.extract( m_arrString[nItem % nArrSize] );
336 xp = rSet.extract( m_arrString[nItem % nArrSize] );
347 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
348 for ( size_t nItem = nSetSize; nItem > 0; --nItem ) {
349 if ( Set::c_bExtractLockExternal ) {
350 typename Set::rcu_lock l;
351 xp = rSet.extract( m_arrString[nItem % nArrSize] );
358 xp = rSet.extract( m_arrString[nItem % nArrSize] );
369 fixture.on_modifier_done();
374 class Iterator: public cds_test::thread
376 typedef cds_test::thread base_class;
379 typedef typename Set::value_type keyval_type;
382 size_t m_nPassCount = 0;
383 size_t m_nVisitCount = 0; // how many items the iterator visited
386 Iterator( cds_test::thread_pool& pool, Set& set )
387 : base_class( pool, iterator_thread )
391 Iterator( Iterator& src )
396 virtual thread * clone()
398 return new Iterator( *this );
405 Set_Iteration& fixture = pool().template fixture<Set_Iteration>();
406 while ( !fixture.all_modifiers_done() ) {
408 for ( auto it = rSet.begin(); it != rSet.end(); ++it ) {
409 it->val.hash = CityHash64( it->key.c_str(), it->key.length());
418 void do_test( Set& testSet )
420 typedef Inserter<Set> InserterThread;
421 typedef Deleter<Set> DeleterThread;
422 typedef Iterator<Set> IteratorThread;
424 cds_test::thread_pool& pool = get_pool();
425 pool.add( new InserterThread( pool, testSet ), s_nInsertThreadCount );
426 pool.add( new DeleterThread( pool, testSet ), s_nDeleteThreadCount );
428 m_nModifierCount.store( pool.size(), atomics::memory_order_relaxed );
429 pool.add( new IteratorThread( pool, testSet ), 1 );
431 propout() << std::make_pair( "insert_thread_count", s_nInsertThreadCount )
432 << std::make_pair( "delete_thread_count", s_nDeleteThreadCount )
433 << std::make_pair( "thread_pass_count", s_nThreadPassCount )
434 << std::make_pair( "set_size", s_nSetSize );
436 std::chrono::milliseconds duration = pool.run();
438 propout() << std::make_pair( "duration", duration );
440 size_t nInsertSuccess = 0;
441 size_t nInsertFailed = 0;
442 size_t nDeleteSuccess = 0;
443 size_t nDeleteFailed = 0;
444 size_t nIteratorPassCount = 0;
445 size_t nIteratorVisitCount = 0;
446 for ( size_t i = 0; i < pool.size(); ++i ) {
447 cds_test::thread& thr = pool.get( i );
448 switch ( thr.type() ) {
451 InserterThread& inserter = static_cast<InserterThread&>( thr );
452 nInsertSuccess += inserter.m_nInsertSuccess;
453 nInsertFailed += inserter.m_nInsertFailed;
458 DeleterThread& deleter = static_cast<DeleterThread&>(thr);
459 nDeleteSuccess += deleter.m_nDeleteSuccess;
460 nDeleteFailed += deleter.m_nDeleteFailed;
463 case iterator_thread:
465 IteratorThread& iter = static_cast<IteratorThread&>(thr);
466 nIteratorPassCount += iter.m_nPassCount;
467 nIteratorVisitCount += iter.m_nVisitCount;
471 assert( false ); // Forgot anything?..
476 << std::make_pair( "insert_success", nInsertSuccess )
477 << std::make_pair( "delete_success", nDeleteSuccess )
478 << std::make_pair( "insert_failed", nInsertFailed )
479 << std::make_pair( "delete_failed", nDeleteFailed )
480 << std::make_pair( "iterator_pass_count", nIteratorPassCount )
481 << std::make_pair( "iterator_visit_count", nIteratorVisitCount )
482 << std::make_pair( "final_set_size", testSet.size() );
485 EXPECT_TRUE( testSet.empty() );
487 additional_check( testSet );
488 print_stat( propout(), testSet );
489 additional_cleanup( testSet );
493 void do_test_extract( Set& testSet )
495 typedef Inserter<Set> InserterThread;
496 typedef Deleter<Set> DeleterThread;
497 typedef Extractor<typename Set::gc, Set> ExtractThread;
498 typedef Iterator<Set> IteratorThread;
500 size_t const nDelThreadCount = s_nDeleteThreadCount / 2;
501 size_t const nExtractThreadCount = s_nDeleteThreadCount - nDelThreadCount;
503 cds_test::thread_pool& pool = get_pool();
504 pool.add( new InserterThread( pool, testSet ), s_nInsertThreadCount );
505 pool.add( new DeleterThread( pool, testSet ), nDelThreadCount );
506 pool.add( new ExtractThread( pool, testSet ), nExtractThreadCount );
508 m_nModifierCount.store( pool.size(), atomics::memory_order_relaxed );
509 pool.add( new IteratorThread( pool, testSet ), 1 );
511 propout() << std::make_pair( "insert_thread_count", s_nInsertThreadCount )
512 << std::make_pair( "delete_thread_count", nDelThreadCount )
513 << std::make_pair( "extract_thread_count", nExtractThreadCount )
514 << std::make_pair( "thread_pass_count", s_nThreadPassCount )
515 << std::make_pair( "set_size", s_nSetSize );
517 std::chrono::milliseconds duration = pool.run();
519 propout() << std::make_pair( "duration", duration );
521 size_t nInsertSuccess = 0;
522 size_t nInsertFailed = 0;
523 size_t nDeleteSuccess = 0;
524 size_t nDeleteFailed = 0;
525 size_t nExtractSuccess = 0;
526 size_t nExtractFailed = 0;
527 size_t nIteratorPassCount = 0;
528 size_t nIteratorVisitCount = 0;
529 for ( size_t i = 0; i < pool.size(); ++i ) {
530 cds_test::thread& thr = pool.get( i );
531 switch ( thr.type() ) {
534 InserterThread& inserter = static_cast<InserterThread&>(thr);
535 nInsertSuccess += inserter.m_nInsertSuccess;
536 nInsertFailed += inserter.m_nInsertFailed;
541 DeleterThread& deleter = static_cast<DeleterThread&>(thr);
542 nDeleteSuccess += deleter.m_nDeleteSuccess;
543 nDeleteFailed += deleter.m_nDeleteFailed;
548 ExtractThread& extractor = static_cast<ExtractThread&>(thr);
549 nExtractSuccess += extractor.m_nDeleteSuccess;
550 nExtractFailed += extractor.m_nDeleteFailed;
553 case iterator_thread:
555 IteratorThread& iter = static_cast<IteratorThread&>(thr);
556 nIteratorPassCount += iter.m_nPassCount;
557 nIteratorVisitCount += iter.m_nVisitCount;
561 assert( false ); // Forgot anything?..
566 << std::make_pair( "insert_success", nInsertSuccess )
567 << std::make_pair( "delete_success", nDeleteSuccess )
568 << std::make_pair( "extract_success", nExtractSuccess )
569 << std::make_pair( "insert_failed", nInsertFailed )
570 << std::make_pair( "delete_failed", nDeleteFailed )
571 << std::make_pair( "extract_failed", nExtractFailed )
572 << std::make_pair( "iterator_pass_count", nIteratorPassCount )
573 << std::make_pair( "iterator_visit_count", nIteratorVisitCount )
574 << std::make_pair( "final_set_size", testSet.size() );
577 EXPECT_TRUE( testSet.empty() );
579 additional_check( testSet );
580 print_stat( propout(), testSet );
581 additional_cleanup( testSet );
587 ASSERT_TRUE( m_arrString.size() > 0 );
594 void run_test_extract()
596 ASSERT_TRUE( m_arrString.size() > 0 );
599 do_test_extract( s );
603 class Set_Iteration_LF: public Set_Iteration
604 , public ::testing::WithParamInterface<size_t>
610 s_nLoadFactor = GetParam();
611 propout() << std::make_pair( "load_factor", s_nLoadFactor );
612 Set_Iteration::run_test<Set>();
616 void run_test_extract()
618 s_nLoadFactor = GetParam();
619 propout() << std::make_pair( "load_factor", s_nLoadFactor );
620 Set_Iteration::run_test_extract<Set>();
623 static std::vector<size_t> get_load_factors();