decf002d7f9ae182776c7cbb8b3cae62cbf731c1
[libcds.git] / test / stress / set / iteration / set_iteration.h
1 /*
2     This file is a part of libcds - Concurrent Data Structures library
3
4     (C) Copyright Maxim Khizhinsky (libcds.dev@gmail.com) 2006-2016
5
6     Source code repo: http://github.com/khizmax/libcds/
7     Download: http://sourceforge.net/projects/libcds/files/
8     
9     Redistribution and use in source and binary forms, with or without
10     modification, are permitted provided that the following conditions are met:
11
12     * Redistributions of source code must retain the above copyright notice, this
13       list of conditions and the following disclaimer.
14
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.
18
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.
29 */
30
31 #include "set_type.h"
32 #include <cds_test/city.h>
33
34 namespace set {
35
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
41
42 #define TEST_CASE(TAG, X)  void X();
43
44     class Set_Iteration: public cds_test::stress_fixture
45     {
46     public:
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
52
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)
56
57         static size_t s_nFeldmanSet_HeadBits;
58         static size_t s_nFeldmanSet_ArrayBits;
59
60         static size_t s_nLoadFactor;
61         static std::vector<std::string>  m_arrString;
62
63         static void SetUpTestCase();
64         static void TearDownTestCase();
65
66         void on_modifier_done()
67         {
68             m_nModifierCount.fetch_sub( 1, atomics::memory_order_relaxed );
69         }
70
71         bool all_modifiers_done() const
72         {
73             return m_nModifierCount.load( atomics::memory_order_relaxed ) == 0;
74         }
75
76         typedef std::string key_type;
77
78         struct value_type
79         {
80             size_t   val;
81             uint64_t hash;
82
83             explicit value_type( size_t v )
84                 : val(v)
85                 , hash(0)
86             {}
87         };
88
89     private:
90         enum {
91             insert_thread,
92             delete_thread,
93             extract_thread,
94             iterator_thread
95         };
96
97         atomics::atomic<size_t> m_nModifierCount;
98
99         template <class Set>
100         class Inserter: public cds_test::thread
101         {
102             typedef cds_test::thread base_class;
103
104             Set&     m_Set;
105             typedef typename Set::value_type keyval_type;
106
107         public:
108             size_t  m_nInsertSuccess = 0;
109             size_t  m_nInsertFailed = 0;
110
111         public:
112             Inserter( cds_test::thread_pool& pool, Set& set )
113                 : base_class( pool, insert_thread )
114                 , m_Set( set )
115             {}
116
117             Inserter( Inserter& src )
118                 : base_class( src )
119                 , m_Set( src.m_Set )
120             {}
121
122             virtual thread * clone()
123             {
124                 return new Inserter( *this );
125             }
126
127             virtual void test()
128             {
129                 Set& rSet = m_Set;
130
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;
135
136                 if ( id() & 1 ) {
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 )))
140                                 ++m_nInsertSuccess;
141                             else
142                                 ++m_nInsertFailed;
143                         }
144                     }
145                 }
146                 else {
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 )))
150                                 ++m_nInsertSuccess;
151                             else
152                                 ++m_nInsertFailed;
153                         }
154                     }
155                 }
156
157                 fixture.on_modifier_done();
158             }
159         };
160
161         template <class Set>
162         class Deleter: public cds_test::thread
163         {
164             typedef cds_test::thread base_class;
165
166             Set&     m_Set;
167         public:
168             size_t  m_nDeleteSuccess = 0;
169             size_t  m_nDeleteFailed = 0;
170
171         public:
172             Deleter( cds_test::thread_pool& pool, Set& set )
173                 : base_class( pool, delete_thread )
174                 , m_Set( set )
175             {}
176
177             Deleter( Deleter& src )
178                 : base_class( src )
179                 , m_Set( src.m_Set )
180             {}
181
182             virtual thread * clone()
183             {
184                 return new Deleter( *this );
185             }
186
187             virtual void test()
188             {
189                 Set& rSet = m_Set;
190
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;
195
196                 if ( id() & 1 ) {
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] ))
200                                 ++m_nDeleteSuccess;
201                             else
202                                 ++m_nDeleteFailed;
203                         }
204                     }
205                 }
206                 else {
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] ))
210                                 ++m_nDeleteSuccess;
211                             else
212                                 ++m_nDeleteFailed;
213                         }
214                     }
215                 }
216
217                 fixture.on_modifier_done();
218             }
219         };
220
221         template <typename GC, class Set>
222         class Extractor: public cds_test::thread
223         {
224             typedef cds_test::thread base_class;
225             Set&     m_Set;
226
227         public:
228             size_t  m_nDeleteSuccess = 0;
229             size_t  m_nDeleteFailed = 0;
230
231         public:
232             Extractor( cds_test::thread_pool& pool, Set& set )
233                 : base_class( pool, extract_thread )
234                 , m_Set( set )
235             {}
236
237             Extractor( Extractor& src )
238                 : base_class( src )
239                 , m_Set( src.m_Set )
240             {}
241
242             virtual thread * clone()
243             {
244                 return new Extractor( *this );
245             }
246
247             virtual void test()
248             {
249                 Set& rSet = m_Set;
250
251                 typename Set::guarded_ptr gp;
252
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;
257
258                 if ( id() & 1 ) {
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] );
262                             if ( gp )
263                                 ++m_nDeleteSuccess;
264                             else
265                                 ++m_nDeleteFailed;
266                             gp.release();
267                         }
268                     }
269                 }
270                 else {
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] );
274                             if ( gp )
275                                 ++m_nDeleteSuccess;
276                             else
277                                 ++m_nDeleteFailed;
278                             gp.release();
279                         }
280                     }
281                 }
282
283                 fixture.on_modifier_done();
284             }
285         };
286
287         template <typename RCU, class Set>
288         class Extractor<cds::urcu::gc<RCU>, Set >: public cds_test::thread
289         {
290             typedef cds_test::thread base_class;
291             Set&     m_Set;
292
293         public:
294             size_t  m_nDeleteSuccess = 0;
295             size_t  m_nDeleteFailed = 0;
296
297         public:
298             Extractor( cds_test::thread_pool& pool, Set& set )
299                 : base_class( pool, extract_thread )
300                 , m_Set( set )
301             {}
302
303             Extractor( Extractor& src )
304                 : base_class( src )
305                 , m_Set( src.m_Set )
306             {}
307
308             virtual thread * clone()
309             {
310                 return new Extractor( *this );
311             }
312
313             virtual void test()
314             {
315                 Set& rSet = m_Set;
316
317                 typename Set::exempt_ptr xp;
318
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;
323
324                 if ( id() & 1 ) {
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] );
330                                 if ( xp )
331                                     ++m_nDeleteSuccess;
332                                 else
333                                     ++m_nDeleteFailed;
334                             }
335                             else {
336                                 xp = rSet.extract( m_arrString[nItem % nArrSize] );
337                                 if ( xp )
338                                     ++m_nDeleteSuccess;
339                                 else
340                                     ++m_nDeleteFailed;
341                             }
342                             xp.release();
343                         }
344                     }
345                 }
346                 else {
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] );
352                                 if ( xp )
353                                     ++m_nDeleteSuccess;
354                                 else
355                                     ++m_nDeleteFailed;
356                             }
357                             else {
358                                 xp = rSet.extract( m_arrString[nItem % nArrSize] );
359                                 if ( xp )
360                                     ++m_nDeleteSuccess;
361                                 else
362                                     ++m_nDeleteFailed;
363                             }
364                             xp.release();
365                         }
366                     }
367                 }
368
369                 fixture.on_modifier_done();
370             }
371         };
372
373         template <typename GC, class Set>
374         class Iterator: public cds_test::thread
375         {
376             typedef cds_test::thread base_class;
377
378             Set&     m_Set;
379             typedef typename Set::value_type keyval_type;
380
381         public:
382             size_t  m_nPassCount = 0;
383             size_t  m_nVisitCount = 0; // how many items the iterator visited
384
385         public:
386             Iterator( cds_test::thread_pool& pool, Set& set )
387                 : base_class( pool, iterator_thread )
388                 , m_Set( set )
389             {}
390
391             Iterator( Iterator& src )
392                 : base_class( src )
393                 , m_Set( src.m_Set )
394             {}
395
396             virtual thread * clone()
397             {
398                 return new Iterator( *this );
399             }
400
401             virtual void test()
402             {
403                 Set& rSet = m_Set;
404
405                 Set_Iteration& fixture = pool().template fixture<Set_Iteration>();
406                 while ( !fixture.all_modifiers_done() ) {
407                     ++m_nPassCount;
408                     for ( auto it = rSet.begin(); it != rSet.end(); ++it ) {
409                         it->val.hash = CityHash64( it->key.c_str(), it->key.length());
410                         ++m_nVisitCount;
411                     }
412                 }
413             }
414         };
415
416         template <typename RCU, class Set>
417         class Iterator<cds::urcu::gc<RCU>, Set>: public cds_test::thread
418         {
419             typedef cds_test::thread base_class;
420
421             Set&     m_Set;
422             typedef typename Set::value_type keyval_type;
423
424         public:
425             size_t  m_nPassCount = 0;
426             size_t  m_nVisitCount = 0; // how many items the iterator visited
427
428         public:
429             Iterator( cds_test::thread_pool& pool, Set& set )
430                 : base_class( pool, iterator_thread )
431                 , m_Set( set )
432             {}
433
434             Iterator( Iterator& src )
435                 : base_class( src )
436                 , m_Set( src.m_Set )
437             {}
438
439             virtual thread * clone()
440             {
441                 return new Iterator( *this );
442             }
443
444             virtual void test()
445             {
446                 Set& rSet = m_Set;
447
448                 Set_Iteration& fixture = pool().template fixture<Set_Iteration>();
449                 while ( !fixture.all_modifiers_done() ) {
450                     ++m_nPassCount;
451                     typename Set::rcu_lock l;
452                     for ( auto it = rSet.begin(); it != rSet.end(); ++it ) {
453                         it->val.hash = CityHash64( it->key.c_str(), it->key.length() );
454                         ++m_nVisitCount;
455                     }
456                 }
457             }
458         };
459
460     protected:
461         template <class Set>
462         void do_test( Set& testSet )
463         {
464             typedef Inserter<Set> InserterThread;
465             typedef Deleter<Set>  DeleterThread;
466             typedef Iterator<typename Set::gc, Set> IteratorThread;
467
468             cds_test::thread_pool& pool = get_pool();
469             pool.add( new InserterThread( pool, testSet ), s_nInsertThreadCount );
470             pool.add( new DeleterThread( pool, testSet ), s_nDeleteThreadCount );
471
472             m_nModifierCount.store( pool.size(), atomics::memory_order_relaxed );
473             pool.add( new IteratorThread( pool, testSet ), 1 );
474
475             propout() << std::make_pair( "insert_thread_count", s_nInsertThreadCount )
476                 << std::make_pair( "delete_thread_count", s_nDeleteThreadCount )
477                 << std::make_pair( "thread_pass_count", s_nThreadPassCount )
478                 << std::make_pair( "set_size", s_nSetSize );
479
480             std::chrono::milliseconds duration = pool.run();
481
482             propout() << std::make_pair( "duration", duration );
483
484             size_t nInsertSuccess = 0;
485             size_t nInsertFailed = 0;
486             size_t nDeleteSuccess = 0;
487             size_t nDeleteFailed = 0;
488             size_t nIteratorPassCount = 0;
489             size_t nIteratorVisitCount = 0;
490             for ( size_t i = 0; i < pool.size(); ++i ) {
491                 cds_test::thread& thr = pool.get( i );
492                 switch ( thr.type() ) {
493                 case insert_thread:
494                     {
495                         InserterThread& inserter = static_cast<InserterThread&>( thr );
496                         nInsertSuccess += inserter.m_nInsertSuccess;
497                         nInsertFailed += inserter.m_nInsertFailed;
498                     }
499                     break;
500                 case delete_thread:
501                     {
502                         DeleterThread& deleter = static_cast<DeleterThread&>(thr);
503                         nDeleteSuccess += deleter.m_nDeleteSuccess;
504                         nDeleteFailed += deleter.m_nDeleteFailed;
505                     }
506                     break;
507                 case iterator_thread:
508                     {
509                         IteratorThread& iter = static_cast<IteratorThread&>(thr);
510                         nIteratorPassCount += iter.m_nPassCount;
511                         nIteratorVisitCount += iter.m_nVisitCount;
512                     }
513                     break;
514                 default:
515                     assert( false ); // Forgot anything?..
516                 }
517             }
518
519             propout()
520                 << std::make_pair( "insert_success", nInsertSuccess )
521                 << std::make_pair( "delete_success", nDeleteSuccess )
522                 << std::make_pair( "insert_failed", nInsertFailed )
523                 << std::make_pair( "delete_failed", nDeleteFailed )
524                 << std::make_pair( "iterator_pass_count", nIteratorPassCount )
525                 << std::make_pair( "iterator_visit_count", nIteratorVisitCount )
526                 << std::make_pair( "final_set_size", testSet.size() );
527
528             testSet.clear();
529             EXPECT_TRUE( testSet.empty() );
530
531             additional_check( testSet );
532             print_stat( propout(), testSet );
533             additional_cleanup( testSet );
534         }
535
536         template <class Set>
537         void do_test_extract( Set& testSet )
538         {
539             typedef Inserter<Set> InserterThread;
540             typedef Deleter<Set>  DeleterThread;
541             typedef Extractor<typename Set::gc, Set> ExtractThread;
542             typedef Iterator<typename Set::gc, Set> IteratorThread;
543
544             size_t const nDelThreadCount = s_nDeleteThreadCount / 2;
545             size_t const nExtractThreadCount = s_nDeleteThreadCount - nDelThreadCount;
546
547             cds_test::thread_pool& pool = get_pool();
548             pool.add( new InserterThread( pool, testSet ), s_nInsertThreadCount );
549             pool.add( new DeleterThread( pool, testSet ), nDelThreadCount );
550             pool.add( new ExtractThread( pool, testSet ), nExtractThreadCount );
551
552             m_nModifierCount.store( pool.size(), atomics::memory_order_relaxed );
553             pool.add( new IteratorThread( pool, testSet ), 1 );
554
555             propout() << std::make_pair( "insert_thread_count", s_nInsertThreadCount )
556                 << std::make_pair( "delete_thread_count", nDelThreadCount )
557                 << std::make_pair( "extract_thread_count", nExtractThreadCount )
558                 << std::make_pair( "thread_pass_count", s_nThreadPassCount )
559                 << std::make_pair( "set_size", s_nSetSize );
560
561             std::chrono::milliseconds duration = pool.run();
562
563             propout() << std::make_pair( "duration", duration );
564
565             size_t nInsertSuccess = 0;
566             size_t nInsertFailed = 0;
567             size_t nDeleteSuccess = 0;
568             size_t nDeleteFailed = 0;
569             size_t nExtractSuccess = 0;
570             size_t nExtractFailed = 0;
571             size_t nIteratorPassCount = 0;
572             size_t nIteratorVisitCount = 0;
573             for ( size_t i = 0; i < pool.size(); ++i ) {
574                 cds_test::thread& thr = pool.get( i );
575                 switch ( thr.type() ) {
576                 case insert_thread:
577                     {
578                         InserterThread& inserter = static_cast<InserterThread&>(thr);
579                         nInsertSuccess += inserter.m_nInsertSuccess;
580                         nInsertFailed += inserter.m_nInsertFailed;
581                     }
582                     break;
583                 case delete_thread:
584                     {
585                         DeleterThread& deleter = static_cast<DeleterThread&>(thr);
586                         nDeleteSuccess += deleter.m_nDeleteSuccess;
587                         nDeleteFailed += deleter.m_nDeleteFailed;
588                     }
589                     break;
590                 case extract_thread:
591                     {
592                         ExtractThread& extractor = static_cast<ExtractThread&>(thr);
593                         nExtractSuccess += extractor.m_nDeleteSuccess;
594                         nExtractFailed += extractor.m_nDeleteFailed;
595                     }
596                     break;
597                 case iterator_thread:
598                     {
599                         IteratorThread& iter = static_cast<IteratorThread&>(thr);
600                         nIteratorPassCount += iter.m_nPassCount;
601                         nIteratorVisitCount += iter.m_nVisitCount;
602                     }
603                     break;
604                 default:
605                     assert( false ); // Forgot anything?..
606                 }
607             }
608
609             propout()
610                 << std::make_pair( "insert_success", nInsertSuccess )
611                 << std::make_pair( "delete_success", nDeleteSuccess )
612                 << std::make_pair( "extract_success", nExtractSuccess )
613                 << std::make_pair( "insert_failed",  nInsertFailed )
614                 << std::make_pair( "delete_failed",  nDeleteFailed )
615                 << std::make_pair( "extract_failed", nExtractFailed )
616                 << std::make_pair( "iterator_pass_count", nIteratorPassCount )
617                 << std::make_pair( "iterator_visit_count", nIteratorVisitCount )
618                 << std::make_pair( "final_set_size", testSet.size() );
619
620             testSet.clear();
621             EXPECT_TRUE( testSet.empty() );
622
623             additional_check( testSet );
624             print_stat( propout(), testSet );
625             additional_cleanup( testSet );
626         }
627
628         template <class Set>
629         void run_test()
630         {
631             ASSERT_TRUE( m_arrString.size() > 0 );
632
633             Set s( *this );
634             do_test( s );
635         }
636
637         template <class Set>
638         void run_test_extract()
639         {
640             ASSERT_TRUE( m_arrString.size() > 0 );
641
642             Set s( *this );
643             do_test_extract( s );
644         }
645     };
646
647     class Set_Iteration_LF: public Set_Iteration
648         , public ::testing::WithParamInterface<size_t>
649     {
650     public:
651         template <class Set>
652         void run_test()
653         {
654             s_nLoadFactor = GetParam();
655             propout() << std::make_pair( "load_factor", s_nLoadFactor );
656             Set_Iteration::run_test<Set>();
657         }
658
659         template <class Set>
660         void run_test_extract()
661         {
662             s_nLoadFactor = GetParam();
663             propout() << std::make_pair( "load_factor", s_nLoadFactor );
664             Set_Iteration::run_test_extract<Set>();
665         }
666
667         static std::vector<size_t> get_load_factors();
668     };
669
670 } // namespace set