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;
136 for (size_t nPass = 0; nPass < nPassCount; ++nPass) {
137 for (size_t nItem = 0; nItem < nSetSize; ++nItem) {
138 if (rSet.insert(keyval_type(m_arrString[nItem % nArrSize],
149 class Deleter: public cds_test::thread
151 typedef cds_test::thread base_class;
155 size_t m_nDeleteSuccess = 0;
156 size_t m_nDeleteFailed = 0;
159 Deleter( cds_test::thread_pool& pool, Set& set )
160 : base_class( pool, delete_thread )
164 Deleter( Deleter& src )
169 virtual thread * clone()
171 return new Deleter( *this );
178 Set_Iteration& fixture = pool().template fixture<Set_Iteration>();
179 size_t nArrSize = m_arrString.size();
180 size_t const nSetSize = fixture.s_nSetSize;
181 size_t const nPassCount = fixture.s_nThreadPassCount;
183 for (size_t nPass = 0; nPass < nPassCount; ++nPass) {
184 for (size_t nItem = 0; nItem < nSetSize; ++nItem) {
185 if (rSet.erase(m_arrString[nItem % nArrSize]))
194 template <typename GC, class Set>
195 class Extractor: public cds_test::thread
197 typedef cds_test::thread base_class;
201 size_t m_nDeleteSuccess = 0;
202 size_t m_nDeleteFailed = 0;
205 Extractor( cds_test::thread_pool& pool, Set& set )
206 : base_class( pool, extract_thread )
210 Extractor( Extractor& src )
215 virtual thread * clone()
217 return new Extractor( *this );
224 typename Set::guarded_ptr gp;
226 Set_Iteration& fixture = pool().template fixture<Set_Iteration>();
227 size_t nArrSize = m_arrString.size();
228 size_t const nSetSize = fixture.s_nSetSize;
229 size_t const nPassCount = fixture.s_nThreadPassCount;
231 for (size_t nPass = 0; nPass < nPassCount; ++nPass) {
232 for (size_t nItem = 0; nItem < nSetSize; ++nItem) {
233 gp = rSet.extract(m_arrString[nItem % nArrSize]);
244 template <typename RCU, class Set>
245 class Extractor<cds::urcu::gc<RCU>, Set >: public cds_test::thread
247 typedef cds_test::thread base_class;
251 size_t m_nDeleteSuccess = 0;
252 size_t m_nDeleteFailed = 0;
255 Extractor( cds_test::thread_pool& pool, Set& set )
256 : base_class( pool, extract_thread )
260 Extractor( Extractor& src )
265 virtual thread * clone()
267 return new Extractor( *this );
274 typename Set::exempt_ptr xp;
276 Set_Iteration& fixture = pool().template fixture<Set_Iteration>();
277 size_t nArrSize = m_arrString.size();
278 size_t const nSetSize = fixture.s_nSetSize;
279 size_t const nPassCount = fixture.s_nThreadPassCount;
282 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
283 for ( size_t nItem = 0; nItem < nSetSize; ++nItem ) {
284 if ( Set::c_bExtractLockExternal ) {
285 typename Set::rcu_lock l;
286 xp = rSet.extract( m_arrString[nItem % nArrSize] );
293 xp = rSet.extract( m_arrString[nItem % nArrSize] );
304 for ( size_t nPass = 0; nPass < nPassCount; ++nPass ) {
305 for ( size_t nItem = nSetSize; nItem > 0; --nItem ) {
306 if ( Set::c_bExtractLockExternal ) {
307 typename Set::rcu_lock l;
308 xp = rSet.extract( m_arrString[nItem % nArrSize] );
315 xp = rSet.extract( m_arrString[nItem % nArrSize] );
326 fixture.on_modifier_done();
330 template <typename GC, class Set>
331 class Iterator: public cds_test::thread
333 typedef cds_test::thread base_class;
336 typedef typename Set::value_type keyval_type;
339 size_t m_nPassCount = 0;
340 size_t m_nVisitCount = 0; // how many items the iterator visited
343 Iterator( cds_test::thread_pool& pool, Set& set )
344 : base_class( pool, iterator_thread )
348 Iterator( Iterator& src )
353 virtual thread * clone()
355 return new Iterator( *this );
362 Set_Iteration& fixture = pool().template fixture<Set_Iteration>();
363 typename Set::iterator it;
364 typename Set::iterator itEnd;
366 for (it = rSet.begin(); it != itEnd; ++it) {
367 #if CDS_BUILD_BITS == 64
368 it->val.hash = CityHash64(it->key.c_str(), it->key.length());
370 it->val.hash = std::hash<std::string>()(it->key);
377 template <typename RCU, class Set>
378 class Iterator<cds::urcu::gc<RCU>, Set>: public cds_test::thread
380 typedef cds_test::thread base_class;
383 typedef typename Set::value_type keyval_type;
386 size_t m_nPassCount = 0;
387 size_t m_nVisitCount = 0; // how many items the iterator visited
390 Iterator( cds_test::thread_pool& pool, Set& set )
391 : base_class( pool, iterator_thread )
395 Iterator( Iterator& src )
400 virtual thread * clone()
402 return new Iterator( *this );
409 Set_Iteration& fixture = pool().template fixture<Set_Iteration>();
410 typename Set::rcu_lock l;
411 for (auto it = rSet.begin(); it != rSet.end(); ++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);
424 void do_test( Set& testSet )
426 typedef Inserter<Set> InserterThread;
427 typedef Deleter<Set> DeleterThread;
428 typedef Iterator<typename Set::gc, Set> IteratorThread;
430 cds_test::thread_pool& pool = get_pool();
431 pool.add( new InserterThread( pool, testSet ), s_nInsertThreadCount );
432 pool.add( new DeleterThread( pool, testSet ), s_nDeleteThreadCount );
434 m_nModifierCount.store( pool.size(), atomics::memory_order_relaxed );
435 pool.add( new IteratorThread( pool, testSet ), 1 );
437 propout() << std::make_pair( "insert_thread_count", s_nInsertThreadCount )
438 << std::make_pair( "delete_thread_count", s_nDeleteThreadCount )
439 << std::make_pair( "thread_pass_count", s_nThreadPassCount )
440 << std::make_pair( "set_size", s_nSetSize );
442 std::chrono::milliseconds duration = pool.run();
444 propout() << std::make_pair( "duration", duration );
446 size_t nInsertSuccess = 0;
447 size_t nInsertFailed = 0;
448 size_t nDeleteSuccess = 0;
449 size_t nDeleteFailed = 0;
450 size_t nIteratorPassCount = 0;
451 size_t nIteratorVisitCount = 0;
452 for ( size_t i = 0; i < pool.size(); ++i ) {
453 cds_test::thread& thr = pool.get( i );
454 switch ( thr.type()) {
457 InserterThread& inserter = static_cast<InserterThread&>( thr );
458 nInsertSuccess += inserter.m_nInsertSuccess;
459 nInsertFailed += inserter.m_nInsertFailed;
464 DeleterThread& deleter = static_cast<DeleterThread&>(thr);
465 nDeleteSuccess += deleter.m_nDeleteSuccess;
466 nDeleteFailed += deleter.m_nDeleteFailed;
469 case iterator_thread:
471 IteratorThread& iter = static_cast<IteratorThread&>(thr);
472 nIteratorPassCount += iter.m_nPassCount;
473 nIteratorVisitCount += iter.m_nVisitCount;
477 assert( false ); // Forgot anything?..
482 << std::make_pair( "insert_success", nInsertSuccess )
483 << std::make_pair( "delete_success", nDeleteSuccess )
484 << std::make_pair( "insert_failed", nInsertFailed )
485 << std::make_pair( "delete_failed", nDeleteFailed )
486 << std::make_pair( "iterator_pass_count", nIteratorPassCount )
487 << std::make_pair( "iterator_visit_count", nIteratorVisitCount )
488 << std::make_pair( "final_set_size", testSet.size());
491 EXPECT_TRUE( testSet.empty());
493 additional_check( testSet );
494 print_stat( propout(), testSet );
495 additional_cleanup( testSet );
499 void do_test_extract( Set& testSet )
501 typedef Inserter<Set> InserterThread;
502 typedef Deleter<Set> DeleterThread;
503 typedef Extractor<typename Set::gc, Set> ExtractThread;
504 typedef Iterator<typename Set::gc, Set> IteratorThread;
506 cds_test::thread_pool& pool = get_pool();
508 std::unique_ptr<InserterThread> inserter(
509 new InserterThread(pool, testSet));
510 std::unique_ptr<DeleterThread> deleter(
511 new DeleterThread(pool, testSet));
512 std::unique_ptr<ExtractThread> extractor(
513 new ExtractThread(pool, testSet));
514 std::unique_ptr<IteratorThread> iterator(
515 new IteratorThread(pool, testSet));
525 additional_cleanup( testSet );
531 ASSERT_TRUE( m_arrString.size() > 0 );
538 void run_test_extract()
540 ASSERT_TRUE( m_arrString.size() > 0 );
543 do_test_extract( s );
547 class Set_Iteration_LF: public Set_Iteration
548 , public ::testing::WithParamInterface<size_t>
554 s_nLoadFactor = GetParam();
555 propout() << std::make_pair( "load_factor", s_nLoadFactor );
556 Set_Iteration::run_test<Set>();
560 void run_test_extract()
562 s_nLoadFactor = GetParam();
563 propout() << std::make_pair( "load_factor", s_nLoadFactor );
564 Set_Iteration::run_test_extract<Set>();
567 static std::vector<size_t> get_load_factors();