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 <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     protected:
 417         template <class Set>
 418         void do_test( Set& testSet )
 419         {
 420             typedef Inserter<Set> InserterThread;
 421             typedef Deleter<Set>  DeleterThread;
 422             typedef Iterator<Set> IteratorThread;
 423
 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 );
 427
 428             m_nModifierCount.store( pool.size(), atomics::memory_order_relaxed );
 429             pool.add( new IteratorThread( pool, testSet ), 1 );
 430
 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 );
 435
 436             std::chrono::milliseconds duration = pool.run();
 437
 438             propout() << std::make_pair( "duration", duration );
 439
 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() ) {
 449                 case insert_thread:
 450                     {
 451                         InserterThread& inserter = static_cast<InserterThread&>( thr );
 452                         nInsertSuccess += inserter.m_nInsertSuccess;
 453                         nInsertFailed += inserter.m_nInsertFailed;
 454                     }
 455                     break;
 456                 case delete_thread:
 457                     {
 458                         DeleterThread& deleter = static_cast<DeleterThread&>(thr);
 459                         nDeleteSuccess += deleter.m_nDeleteSuccess;
 460                         nDeleteFailed += deleter.m_nDeleteFailed;
 461                     }
 462                     break;
 463                 case iterator_thread:
 464                     {
 465                         IteratorThread& iter = static_cast<IteratorThread&>(thr);
 466                         nIteratorPassCount += iter.m_nPassCount;
 467                         nIteratorVisitCount += iter.m_nVisitCount;
 468                     }
 469                     break;
 470                 default:
 471                     assert( false ); // Forgot anything?..
 472                 }
 473             }
 474
 475             propout()
 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() );
 483
 484             testSet.clear();
 485             EXPECT_TRUE( testSet.empty() );
 486
 487             additional_check( testSet );
 488             print_stat( propout(), testSet );
 489             additional_cleanup( testSet );
 490         }
 491
 492         template <class Set>
 493         void do_test_extract( Set& testSet )
 494         {
 495             typedef Inserter<Set> InserterThread;
 496             typedef Deleter<Set>  DeleterThread;
 497             typedef Extractor<typename Set::gc, Set> ExtractThread;
 498             typedef Iterator<Set> IteratorThread;
 499
 500             size_t const nDelThreadCount = s_nDeleteThreadCount / 2;
 501             size_t const nExtractThreadCount = s_nDeleteThreadCount - nDelThreadCount;
 502
 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 );
 507
 508             m_nModifierCount.store( pool.size(), atomics::memory_order_relaxed );
 509             pool.add( new IteratorThread( pool, testSet ), 1 );
 510
 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 );
 516
 517             std::chrono::milliseconds duration = pool.run();
 518
 519             propout() << std::make_pair( "duration", duration );
 520
 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() ) {
 532                 case insert_thread:
 533                     {
 534                         InserterThread& inserter = static_cast<InserterThread&>(thr);
 535                         nInsertSuccess += inserter.m_nInsertSuccess;
 536                         nInsertFailed += inserter.m_nInsertFailed;
 537                     }
 538                     break;
 539                 case delete_thread:
 540                     {
 541                         DeleterThread& deleter = static_cast<DeleterThread&>(thr);
 542                         nDeleteSuccess += deleter.m_nDeleteSuccess;
 543                         nDeleteFailed += deleter.m_nDeleteFailed;
 544                     }
 545                     break;
 546                 case extract_thread:
 547                     {
 548                         ExtractThread& extractor = static_cast<ExtractThread&>(thr);
 549                         nExtractSuccess += extractor.m_nDeleteSuccess;
 550                         nExtractFailed += extractor.m_nDeleteFailed;
 551                     }
 552                     break;
 553                 case iterator_thread:
 554                     {
 555                         IteratorThread& iter = static_cast<IteratorThread&>(thr);
 556                         nIteratorPassCount += iter.m_nPassCount;
 557                         nIteratorVisitCount += iter.m_nVisitCount;
 558                     }
 559                     break;
 560                 default:
 561                     assert( false ); // Forgot anything?..
 562                 }
 563             }
 564
 565             propout()
 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() );
 575
 576             testSet.clear();
 577             EXPECT_TRUE( testSet.empty() );
 578
 579             additional_check( testSet );
 580             print_stat( propout(), testSet );
 581             additional_cleanup( testSet );
 582         }
 583
 584         template <class Set>
 585         void run_test()
 586         {
 587             ASSERT_TRUE( m_arrString.size() > 0 );
 588
 589             Set s( *this );
 590             do_test( s );
 591         }
 592
 593         template <class Set>
 594         void run_test_extract()
 595         {
 596             ASSERT_TRUE( m_arrString.size() > 0 );
 597
 598             Set s( *this );
 599             do_test_extract( s );
 600         }
 601     };
 602
 603     class Set_Iteration_LF: public Set_Iteration
 604         , public ::testing::WithParamInterface<size_t>
 605     {
 606     public:
 607         template <class Set>
 608         void run_test()
 609         {
 610             s_nLoadFactor = GetParam();
 611             propout() << std::make_pair( "load_factor", s_nLoadFactor );
 612             Set_Iteration::run_test<Set>();
 613         }
 614
 615         template <class Set>
 616         void run_test_extract()
 617         {
 618             s_nLoadFactor = GetParam();
 619             propout() << std::make_pair( "load_factor", s_nLoadFactor );
 620             Set_Iteration::run_test_extract<Set>();
 621         }
 622
 623         static std::vector<size_t> get_load_factors();
 624     };
 625
 626 } // namespace set