2 This file is a part of libcds - Concurrent Data Structures library
4 (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2017
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();
373 template <typename GC, class Set>
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 typename Set::iterator it;
409 typename Set::iterator itEnd;
411 for ( it = rSet.begin(); it != itEnd; ++it ) {
412 #if CDS_BUILD_BITS == 64
413 it->val.hash = CityHash64( it->key.c_str(), it->key.length());
415 it->val.hash = std::hash<std::string>()( it->key );
423 template <typename RCU, class Set>
424 class Iterator<cds::urcu::gc<RCU>, Set>: public cds_test::thread
426 typedef cds_test::thread base_class;
429 typedef typename Set::value_type keyval_type;
432 size_t m_nPassCount = 0;
433 size_t m_nVisitCount = 0; // how many items the iterator visited
436 Iterator( cds_test::thread_pool& pool, Set& set )
437 : base_class( pool, iterator_thread )
441 Iterator( Iterator& src )
446 virtual thread * clone()
448 return new Iterator( *this );
455 Set_Iteration& fixture = pool().template fixture<Set_Iteration>();
456 while ( !fixture.all_modifiers_done()) {
458 typename Set::rcu_lock l;
459 for ( auto it = rSet.begin(); it != rSet.end(); ++it ) {
460 #if CDS_BUILD_BITS == 64
461 it->val.hash = CityHash64( it->key.c_str(), it->key.length());
463 it->val.hash = std::hash<std::string>()(it->key);
473 void do_test( Set& testSet )
475 typedef Inserter<Set> InserterThread;
476 typedef Deleter<Set> DeleterThread;
477 typedef Iterator<typename Set::gc, Set> IteratorThread;
479 cds_test::thread_pool& pool = get_pool();
480 pool.add( new InserterThread( pool, testSet ), s_nInsertThreadCount );
481 pool.add( new DeleterThread( pool, testSet ), s_nDeleteThreadCount );
483 m_nModifierCount.store( pool.size(), atomics::memory_order_relaxed );
484 pool.add( new IteratorThread( pool, testSet ), 1 );
486 propout() << std::make_pair( "insert_thread_count", s_nInsertThreadCount )
487 << std::make_pair( "delete_thread_count", s_nDeleteThreadCount )
488 << std::make_pair( "thread_pass_count", s_nThreadPassCount )
489 << std::make_pair( "set_size", s_nSetSize );
491 std::chrono::milliseconds duration = pool.run();
493 propout() << std::make_pair( "duration", duration );
495 size_t nInsertSuccess = 0;
496 size_t nInsertFailed = 0;
497 size_t nDeleteSuccess = 0;
498 size_t nDeleteFailed = 0;
499 size_t nIteratorPassCount = 0;
500 size_t nIteratorVisitCount = 0;
501 for ( size_t i = 0; i < pool.size(); ++i ) {
502 cds_test::thread& thr = pool.get( i );
503 switch ( thr.type()) {
506 InserterThread& inserter = static_cast<InserterThread&>( thr );
507 nInsertSuccess += inserter.m_nInsertSuccess;
508 nInsertFailed += inserter.m_nInsertFailed;
513 DeleterThread& deleter = static_cast<DeleterThread&>(thr);
514 nDeleteSuccess += deleter.m_nDeleteSuccess;
515 nDeleteFailed += deleter.m_nDeleteFailed;
518 case iterator_thread:
520 IteratorThread& iter = static_cast<IteratorThread&>(thr);
521 nIteratorPassCount += iter.m_nPassCount;
522 nIteratorVisitCount += iter.m_nVisitCount;
526 assert( false ); // Forgot anything?..
531 << std::make_pair( "insert_success", nInsertSuccess )
532 << std::make_pair( "delete_success", nDeleteSuccess )
533 << std::make_pair( "insert_failed", nInsertFailed )
534 << std::make_pair( "delete_failed", nDeleteFailed )
535 << std::make_pair( "iterator_pass_count", nIteratorPassCount )
536 << std::make_pair( "iterator_visit_count", nIteratorVisitCount )
537 << std::make_pair( "final_set_size", testSet.size());
540 EXPECT_TRUE( testSet.empty());
542 additional_check( testSet );
543 print_stat( propout(), testSet );
544 additional_cleanup( testSet );
548 void do_test_extract( Set& testSet )
550 typedef Inserter<Set> InserterThread;
551 typedef Deleter<Set> DeleterThread;
552 typedef Extractor<typename Set::gc, Set> ExtractThread;
553 typedef Iterator<typename Set::gc, Set> IteratorThread;
555 size_t const nDelThreadCount = s_nDeleteThreadCount / 2;
556 size_t const nExtractThreadCount = s_nDeleteThreadCount - nDelThreadCount;
558 cds_test::thread_pool& pool = get_pool();
559 pool.add( new InserterThread( pool, testSet ), s_nInsertThreadCount );
560 pool.add( new DeleterThread( pool, testSet ), nDelThreadCount );
561 pool.add( new ExtractThread( pool, testSet ), nExtractThreadCount );
563 m_nModifierCount.store( pool.size(), atomics::memory_order_relaxed );
564 pool.add( new IteratorThread( pool, testSet ), 1 );
566 propout() << std::make_pair( "insert_thread_count", s_nInsertThreadCount )
567 << std::make_pair( "delete_thread_count", nDelThreadCount )
568 << std::make_pair( "extract_thread_count", nExtractThreadCount )
569 << std::make_pair( "thread_pass_count", s_nThreadPassCount )
570 << std::make_pair( "set_size", s_nSetSize );
572 std::chrono::milliseconds duration = pool.run();
574 propout() << std::make_pair( "duration", duration );
576 size_t nInsertSuccess = 0;
577 size_t nInsertFailed = 0;
578 size_t nDeleteSuccess = 0;
579 size_t nDeleteFailed = 0;
580 size_t nExtractSuccess = 0;
581 size_t nExtractFailed = 0;
582 size_t nIteratorPassCount = 0;
583 size_t nIteratorVisitCount = 0;
584 for ( size_t i = 0; i < pool.size(); ++i ) {
585 cds_test::thread& thr = pool.get( i );
586 switch ( thr.type()) {
589 InserterThread& inserter = static_cast<InserterThread&>(thr);
590 nInsertSuccess += inserter.m_nInsertSuccess;
591 nInsertFailed += inserter.m_nInsertFailed;
596 DeleterThread& deleter = static_cast<DeleterThread&>(thr);
597 nDeleteSuccess += deleter.m_nDeleteSuccess;
598 nDeleteFailed += deleter.m_nDeleteFailed;
603 ExtractThread& extractor = static_cast<ExtractThread&>(thr);
604 nExtractSuccess += extractor.m_nDeleteSuccess;
605 nExtractFailed += extractor.m_nDeleteFailed;
608 case iterator_thread:
610 IteratorThread& iter = static_cast<IteratorThread&>(thr);
611 nIteratorPassCount += iter.m_nPassCount;
612 nIteratorVisitCount += iter.m_nVisitCount;
616 assert( false ); // Forgot anything?..
621 << std::make_pair( "insert_success", nInsertSuccess )
622 << std::make_pair( "delete_success", nDeleteSuccess )
623 << std::make_pair( "extract_success", nExtractSuccess )
624 << std::make_pair( "insert_failed", nInsertFailed )
625 << std::make_pair( "delete_failed", nDeleteFailed )
626 << std::make_pair( "extract_failed", nExtractFailed )
627 << std::make_pair( "iterator_pass_count", nIteratorPassCount )
628 << std::make_pair( "iterator_visit_count", nIteratorVisitCount )
629 << std::make_pair( "final_set_size", testSet.size());
632 EXPECT_TRUE( testSet.empty());
634 additional_check( testSet );
635 print_stat( propout(), testSet );
636 additional_cleanup( testSet );
642 ASSERT_TRUE( m_arrString.size() > 0 );
649 void run_test_extract()
651 ASSERT_TRUE( m_arrString.size() > 0 );
654 do_test_extract( s );
658 class Set_Iteration_LF: public Set_Iteration
659 , public ::testing::WithParamInterface<size_t>
665 s_nLoadFactor = GetParam();
666 propout() << std::make_pair( "load_factor", s_nLoadFactor );
667 Set_Iteration::run_test<Set>();
671 void run_test_extract()
673 s_nLoadFactor = GetParam();
674 propout() << std::make_pair( "load_factor", s_nLoadFactor );
675 Set_Iteration::run_test_extract<Set>();
678 static std::vector<size_t> get_load_factors();