test/stress/sequential/sequential-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-2017
   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                 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],
 139                                                 nItem * 8)))
 140                       ++m_nInsertSuccess;
 141                     else
 142                       ++m_nInsertFailed;
 143                   }
 144                 }
 145             }
 146         };
 147
 148         template <class Set>
 149         class Deleter: public cds_test::thread
 150         {
 151             typedef cds_test::thread base_class;
 152
 153             Set&     m_Set;
 154         public:
 155             size_t  m_nDeleteSuccess = 0;
 156             size_t  m_nDeleteFailed = 0;
 157
 158         public:
 159             Deleter( cds_test::thread_pool& pool, Set& set )
 160                 : base_class( pool, delete_thread )
 161                 , m_Set( set )
 162             {}
 163
 164             Deleter( Deleter& src )
 165                 : base_class( src )
 166                 , m_Set( src.m_Set )
 167             {}
 168
 169             virtual thread * clone()
 170             {
 171                 return new Deleter( *this );
 172             }
 173
 174             virtual void test()
 175             {
 176                 Set& rSet = m_Set;
 177
 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;
 182
 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]))
 186                       ++m_nDeleteSuccess;
 187                     else
 188                       ++m_nDeleteFailed;
 189                   }
 190                 }
 191             }
 192         };
 193
 194         template <typename GC, class Set>
 195         class Extractor: public cds_test::thread
 196         {
 197             typedef cds_test::thread base_class;
 198             Set&     m_Set;
 199
 200         public:
 201             size_t  m_nDeleteSuccess = 0;
 202             size_t  m_nDeleteFailed = 0;
 203
 204         public:
 205             Extractor( cds_test::thread_pool& pool, Set& set )
 206                 : base_class( pool, extract_thread )
 207                 , m_Set( set )
 208             {}
 209
 210             Extractor( Extractor& src )
 211                 : base_class( src )
 212                 , m_Set( src.m_Set )
 213             {}
 214
 215             virtual thread * clone()
 216             {
 217                 return new Extractor( *this );
 218             }
 219
 220             virtual void test()
 221             {
 222                 Set& rSet = m_Set;
 223
 224                 typename Set::guarded_ptr gp;
 225
 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;
 230
 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]);
 234                     if (gp)
 235                       ++m_nDeleteSuccess;
 236                     else
 237                       ++m_nDeleteFailed;
 238                     gp.release();
 239                   }
 240                 }
 241             }
 242         };
 243
 244         template <typename RCU, class Set>
 245         class Extractor<cds::urcu::gc<RCU>, Set >: public cds_test::thread
 246         {
 247             typedef cds_test::thread base_class;
 248             Set&     m_Set;
 249
 250         public:
 251             size_t  m_nDeleteSuccess = 0;
 252             size_t  m_nDeleteFailed = 0;
 253
 254         public:
 255             Extractor( cds_test::thread_pool& pool, Set& set )
 256                 : base_class( pool, extract_thread )
 257                 , m_Set( set )
 258             {}
 259
 260             Extractor( Extractor& src )
 261                 : base_class( src )
 262                 , m_Set( src.m_Set )
 263             {}
 264
 265             virtual thread * clone()
 266             {
 267                 return new Extractor( *this );
 268             }
 269
 270             virtual void test()
 271             {
 272                 Set& rSet = m_Set;
 273
 274                 typename Set::exempt_ptr xp;
 275
 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;
 280
 281                 if ( id() & 1 ) {
 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] );
 287                                 if ( xp )
 288                                     ++m_nDeleteSuccess;
 289                                 else
 290                                     ++m_nDeleteFailed;
 291                             }
 292                             else {
 293                                 xp = rSet.extract( m_arrString[nItem % nArrSize] );
 294                                 if ( xp )
 295                                     ++m_nDeleteSuccess;
 296                                 else
 297                                     ++m_nDeleteFailed;
 298                             }
 299                             xp.release();
 300                         }
 301                     }
 302                 }
 303                 else {
 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] );
 309                                 if ( xp )
 310                                     ++m_nDeleteSuccess;
 311                                 else
 312                                     ++m_nDeleteFailed;
 313                             }
 314                             else {
 315                                 xp = rSet.extract( m_arrString[nItem % nArrSize] );
 316                                 if ( xp )
 317                                     ++m_nDeleteSuccess;
 318                                 else
 319                                     ++m_nDeleteFailed;
 320                             }
 321                             xp.release();
 322                         }
 323                     }
 324                 }
 325
 326                 fixture.on_modifier_done();
 327             }
 328         };
 329
 330         template <typename GC, class Set>
 331         class Iterator: public cds_test::thread
 332         {
 333             typedef cds_test::thread base_class;
 334
 335             Set&     m_Set;
 336             typedef typename Set::value_type keyval_type;
 337
 338         public:
 339             size_t  m_nPassCount = 0;
 340             size_t  m_nVisitCount = 0; // how many items the iterator visited
 341
 342         public:
 343             Iterator( cds_test::thread_pool& pool, Set& set )
 344                 : base_class( pool, iterator_thread )
 345                 , m_Set( set )
 346             {}
 347
 348             Iterator( Iterator& src )
 349                 : base_class( src )
 350                 , m_Set( src.m_Set )
 351             {}
 352
 353             virtual thread * clone()
 354             {
 355                 return new Iterator( *this );
 356             }
 357
 358             virtual void test()
 359             {
 360                 Set& rSet = m_Set;
 361
 362                 Set_Iteration& fixture = pool().template fixture<Set_Iteration>();
 363                 typename Set::iterator it;
 364                 typename Set::iterator itEnd;
 365                 itEnd = rSet.end();
 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());
 369 #else
 370                   it->val.hash = std::hash<std::string>()(it->key);
 371 #endif
 372                   ++m_nVisitCount;
 373                 }
 374             }
 375         };
 376
 377         template <typename RCU, class Set>
 378         class Iterator<cds::urcu::gc<RCU>, Set>: public cds_test::thread
 379         {
 380             typedef cds_test::thread base_class;
 381
 382             Set&     m_Set;
 383             typedef typename Set::value_type keyval_type;
 384
 385         public:
 386             size_t  m_nPassCount = 0;
 387             size_t  m_nVisitCount = 0; // how many items the iterator visited
 388
 389         public:
 390             Iterator( cds_test::thread_pool& pool, Set& set )
 391                 : base_class( pool, iterator_thread )
 392                 , m_Set( set )
 393             {}
 394
 395             Iterator( Iterator& src )
 396                 : base_class( src )
 397                 , m_Set( src.m_Set )
 398             {}
 399
 400             virtual thread * clone()
 401             {
 402                 return new Iterator( *this );
 403             }
 404
 405             virtual void test()
 406             {
 407                 Set& rSet = m_Set;
 408
 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());
 414 #else
 415                   it->val.hash = std::hash<std::string>()(it->key);
 416 #endif
 417                   ++m_nVisitCount;
 418                 }
 419         }
 420         };
 421
 422     protected:
 423         template <class Set>
 424         void do_test( Set& testSet )
 425         {
 426             typedef Inserter<Set> InserterThread;
 427             typedef Deleter<Set>  DeleterThread;
 428             typedef Iterator<typename Set::gc, Set> IteratorThread;
 429
 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 );
 433
 434             m_nModifierCount.store( pool.size(), atomics::memory_order_relaxed );
 435             pool.add( new IteratorThread( pool, testSet ), 1 );
 436
 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 );
 441
 442             std::chrono::milliseconds duration = pool.run();
 443
 444             propout() << std::make_pair( "duration", duration );
 445
 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()) {
 455                 case insert_thread:
 456                     {
 457                         InserterThread& inserter = static_cast<InserterThread&>( thr );
 458                         nInsertSuccess += inserter.m_nInsertSuccess;
 459                         nInsertFailed += inserter.m_nInsertFailed;
 460                     }
 461                     break;
 462                 case delete_thread:
 463                     {
 464                         DeleterThread& deleter = static_cast<DeleterThread&>(thr);
 465                         nDeleteSuccess += deleter.m_nDeleteSuccess;
 466                         nDeleteFailed += deleter.m_nDeleteFailed;
 467                     }
 468                     break;
 469                 case iterator_thread:
 470                     {
 471                         IteratorThread& iter = static_cast<IteratorThread&>(thr);
 472                         nIteratorPassCount += iter.m_nPassCount;
 473                         nIteratorVisitCount += iter.m_nVisitCount;
 474                     }
 475                     break;
 476                 default:
 477                     assert( false ); // Forgot anything?..
 478                 }
 479             }
 480
 481             propout()
 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());
 489
 490             testSet.clear();
 491             EXPECT_TRUE( testSet.empty());
 492
 493             additional_check( testSet );
 494             print_stat( propout(), testSet );
 495             additional_cleanup( testSet );
 496         }
 497
 498         template <class Set>
 499         void do_test_extract( Set& testSet )
 500         {
 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;
 505
 506             cds_test::thread_pool& pool = get_pool();
 507
 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));
 516
 517             inserter->test();
 518             iterator->test();
 519             deleter->test();
 520             iterator->test();
 521             extractor->test();
 522             iterator->test();
 523
 524             testSet.clear();
 525             additional_cleanup( testSet );
 526         }
 527
 528         template <class Set>
 529         void run_test()
 530         {
 531             ASSERT_TRUE( m_arrString.size() > 0 );
 532
 533             Set s( *this );
 534             do_test( s );
 535         }
 536
 537         template <class Set>
 538         void run_test_extract()
 539         {
 540             ASSERT_TRUE( m_arrString.size() > 0 );
 541
 542             Set s( *this );
 543             do_test_extract( s );
 544         }
 545     };
 546
 547     class Set_Iteration_LF: public Set_Iteration
 548         , public ::testing::WithParamInterface<size_t>
 549     {
 550     public:
 551         template <class Set>
 552         void run_test()
 553         {
 554             s_nLoadFactor = GetParam();
 555             propout() << std::make_pair( "load_factor", s_nLoadFactor );
 556             Set_Iteration::run_test<Set>();
 557         }
 558
 559         template <class Set>
 560         void run_test_extract()
 561         {
 562             s_nLoadFactor = GetParam();
 563             propout() << std::make_pair( "load_factor", s_nLoadFactor );
 564             Set_Iteration::run_test_extract<Set>();
 565         }
 566
 567         static std::vector<size_t> get_load_factors();
 568     };
 569
 570 } // namespace set