test/stress/sequential/sequential-set/insdel_func/set_insdel_func.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
  33 namespace set {
  34
  35     class Set_InsDel_func: public cds_test::stress_fixture
  36     {
  37     public:
  38         static size_t s_nSetSize;               // set size
  39         static size_t s_nInsertThreadCount;     // count of insertion thread
  40         static size_t s_nDeleteThreadCount;     // count of deletion thread
  41         static size_t s_nUpdateThreadCount;     // count of updating thread
  42         static size_t s_nThreadPassCount;       // pass count for each thread
  43         static size_t s_nFeldmanThreadPassCount;       // pass count for Feldman
  44         static size_t s_nMaxLoadFactor;         // maximum load factor
  45
  46         static size_t s_nCuckooInitialSize;     // initial size for CuckooSet
  47         static size_t s_nCuckooProbesetSize;    // CuckooSet probeset size (only for list-based probeset)
  48         static size_t s_nCuckooProbesetThreshold; // CUckooSet probeset threshold (0 - use default)
  49
  50         static size_t s_nFeldmanSet_HeadBits;
  51         static size_t s_nFeldmanSet_ArrayBits;
  52
  53         static size_t s_nLoadFactor;
  54
  55         static void SetUpTestCase();
  56         //static void TearDownTestCase();
  57
  58     public:
  59         typedef size_t  key_type;
  60
  61         struct value {
  62             size_t      nKey;
  63             size_t      nData;
  64             atomics::atomic<size_t> nUpdateCall;
  65             bool volatile           bInitialized;
  66             cds::OS::ThreadId       threadId;   // insert thread id
  67
  68             typedef cds::sync::spin_lock< cds::backoff::pause > lock_type;
  69             mutable lock_type   m_access;
  70
  71             value()
  72                 : nKey(0)
  73                 , nData(0)
  74                 , nUpdateCall(0)
  75                 , bInitialized( false )
  76                 , threadId( cds::OS::get_current_thread_id())
  77             {}
  78
  79             value( value const& s )
  80                 : nKey(s.nKey)
  81                 , nData(s.nData)
  82                 , nUpdateCall(s.nUpdateCall.load(atomics::memory_order_relaxed))
  83                 , bInitialized( s.bInitialized )
  84                 , threadId( cds::OS::get_current_thread_id())
  85                 , m_access()
  86             {}
  87
  88             // boost::container::flat_map requires operator =
  89             // cppcheck-suppress operatorEqVarError
  90             value& operator=( value const& v )
  91             {
  92                 nKey = v.nKey;
  93                 nData = v.nData;
  94                 threadId = v.threadId;
  95                 nUpdateCall.store( v.nUpdateCall.load(atomics::memory_order_relaxed), atomics::memory_order_relaxed );
  96                 bInitialized = v.bInitialized;
  97
  98                 return *this;
  99             }
 100         };
 101
 102         size_t *    m_pKeyFirst;
 103         size_t *    m_pKeyLast;
 104         std::unique_ptr< size_t[] > m_pKeyArr;
 105
 106         enum {
 107             insert_thread,
 108             update_thread,
 109             delete_thread
 110         };
 111
 112         template <class Set>
 113         class Inserter: public cds_test::thread
 114         {
 115             typedef cds_test::thread base_class;
 116
 117             Set&     m_Set;
 118             typedef typename Set::value_type keyval_type;
 119
 120             struct insert_functor {
 121                 size_t nTestFunctorRef;
 122
 123                 insert_functor()
 124                     : nTestFunctorRef(0)
 125                 {}
 126                 insert_functor( insert_functor const& ) = delete;
 127
 128                 void operator()( keyval_type& val )
 129                 {
 130                     std::unique_lock< typename value::lock_type> ac( val.val.m_access );
 131
 132                     val.val.nKey  = val.key;
 133                     val.val.nData = val.key * 8;
 134
 135                     ++nTestFunctorRef;
 136                     val.val.bInitialized = true;
 137                 }
 138             };
 139
 140         public:
 141             size_t  m_nInsertSuccess = 0;
 142             size_t  m_nInsertFailed = 0;
 143             size_t  m_nTestFunctorRef = 0;
 144
 145         public:
 146             Inserter( cds_test::thread_pool& pool, Set& set )
 147                 : base_class( pool, insert_thread )
 148                 , m_Set( set )
 149             {}
 150
 151             Inserter( Inserter& src )
 152                 : base_class( src )
 153                 , m_Set( src.m_Set )
 154             {}
 155
 156             virtual thread * clone()
 157             {
 158                 return new Inserter( *this );
 159             }
 160
 161             virtual void test()
 162             {
 163                 Set& rSet = m_Set;
 164                 Set_InsDel_func& fixture = pool().template fixture<Set_InsDel_func>();
 165
 166                 size_t * pKeyFirst      = fixture.m_pKeyFirst;
 167                 size_t * pKeyLast       = fixture.m_pKeyLast;
 168                 size_t const nPassCount = fixture.s_nThreadPassCount;
 169
 170                 // func is passed by reference
 171                 insert_functor  func;
 172                 for (size_t *p = pKeyFirst; p < pKeyLast; ++p) {
 173                   if (rSet.insert(*p, std::ref(func)))
 174                     ++m_nInsertSuccess;
 175                   else
 176                     ++m_nInsertFailed;
 177                 }
 178             }
 179         };
 180
 181         template <class Set>
 182         class Updater: public cds_test::thread
 183         {
 184             typedef cds_test::thread base_class;
 185
 186             Set&     m_Set;
 187             typedef typename Set::value_type keyval_type;
 188
 189             struct update_functor {
 190                 size_t  nCreated = 0;
 191                 size_t  nModified = 0;
 192
 193                 update_functor() {}
 194                 update_functor( const update_functor& ) = delete;
 195
 196                 void operator()( bool bNew, keyval_type& val, size_t /*nKey*/ )
 197                 {
 198                     std::unique_lock<typename value::lock_type> ac( val.val.m_access );
 199                     if ( !val.val.bInitialized )
 200                     {
 201                         val.val.nKey = val.key;
 202                         val.val.nData = val.key * 8;
 203                         val.val.bInitialized = true;
 204                     }
 205
 206                     if ( bNew ) {
 207                         ++nCreated;
 208                     }
 209                     else {
 210                         val.val.nUpdateCall.fetch_add( 1, atomics::memory_order_relaxed );
 211                         ++nModified;
 212                     }
 213                 }
 214
 215                 void operator()( keyval_type& cur, keyval_type * old )
 216                 {
 217                     operator()( old == nullptr, cur, 0 );
 218                 }
 219             };
 220
 221         public:
 222             size_t  m_nUpdateFailed = 0;
 223             size_t  m_nUpdateCreated = 0;
 224             size_t  m_nUpdateExisted = 0;
 225             size_t  m_nFunctorCreated = 0;
 226             size_t  m_nFunctorModified = 0;
 227
 228         public:
 229             Updater( cds_test::thread_pool& pool, Set& set )
 230                 : base_class( pool, update_thread )
 231                 , m_Set( set )
 232             {}
 233
 234             Updater( Updater& src )
 235                 : base_class( src )
 236                 , m_Set( src.m_Set )
 237             {}
 238
 239             virtual thread * clone()
 240             {
 241                 return new Updater( *this );
 242             }
 243
 244             virtual void test()
 245             {
 246                 Set& rSet = m_Set;
 247
 248                 Set_InsDel_func& fixture = pool().template fixture<Set_InsDel_func>();
 249                 size_t * pKeyFirst = fixture.m_pKeyFirst;
 250                 size_t * pKeyLast = fixture.m_pKeyLast;
 251                 size_t const nPassCount = fixture.s_nThreadPassCount;
 252
 253                 update_functor func;
 254
 255                 for (size_t *p = pKeyFirst; p < pKeyLast; ++p) {
 256                   std::pair<bool, bool> ret =
 257                       rSet.update(*p, std::ref(func), true);
 258                   if (ret.first) {
 259                     if (ret.second)
 260                       ++m_nUpdateCreated;
 261                     else
 262                       ++m_nUpdateExisted;
 263                   } else
 264                     ++m_nUpdateFailed;
 265                 }
 266             }
 267         };
 268
 269         template <class Set>
 270         class Deleter: public cds_test::thread
 271         {
 272             typedef cds_test::thread base_class;
 273
 274             Set&     m_Set;
 275             typedef typename Set::value_type keyval_type;
 276
 277             struct value_container
 278             {
 279                 size_t      nKeyExpected;
 280
 281                 size_t      nSuccessItem = 0;
 282                 size_t      nFailedItem = 0;
 283             };
 284
 285             struct erase_functor {
 286                 value_container     m_cnt;
 287
 288                 void operator ()( keyval_type const& itm )
 289                 {
 290                     keyval_type& item = const_cast<keyval_type&>(itm);
 291                     while ( true ) {
 292                         bool bBkoff = false;
 293                         {
 294                             std::unique_lock< typename value::lock_type> ac( item.val.m_access );
 295                             if ( item.val.bInitialized ) {
 296                                 if ( m_cnt.nKeyExpected == item.val.nKey && m_cnt.nKeyExpected * 8 == item.val.nData )
 297                                     ++m_cnt.nSuccessItem;
 298                                 else
 299                                     ++m_cnt.nFailedItem;
 300                                 item.val.nData++;
 301                                 item.val.nKey = 0;
 302                                 break;
 303                             }
 304                             else
 305                                 bBkoff = true;
 306                         }
 307                         if ( bBkoff )
 308                             cds::backoff::yield()();
 309                     }
 310                 }
 311             };
 312
 313         public:
 314             size_t  m_nDeleteSuccess = 0;
 315             size_t  m_nDeleteFailed = 0;
 316             size_t  m_nValueSuccess = 0;
 317             size_t  m_nValueFailed = 0;
 318
 319         public:
 320             Deleter( cds_test::thread_pool& pool, Set& set )
 321                 : base_class( pool, delete_thread )
 322                 , m_Set( set )
 323             {}
 324
 325             Deleter( Deleter& src )
 326                 : base_class( src )
 327                 , m_Set( src.m_Set )
 328             {}
 329
 330             virtual thread * clone()
 331             {
 332                 return new Deleter( *this );
 333             }
 334
 335             virtual void test()
 336             {
 337                 Set& rSet = m_Set;
 338
 339                 Set_InsDel_func& fixture = pool().template fixture<Set_InsDel_func>();
 340                 size_t * pKeyFirst      = fixture.m_pKeyFirst;
 341                 size_t * pKeyLast       = fixture.m_pKeyLast;
 342                 size_t const nPassCount = fixture.s_nThreadPassCount;
 343
 344                 erase_functor   func;
 345
 346                 for (size_t *p = pKeyFirst; p < pKeyLast; ++p) {
 347                   func.m_cnt.nKeyExpected = *p;
 348                   if (rSet.erase(*p, std::ref(func)))
 349                     ++m_nDeleteSuccess;
 350                   else
 351                     ++m_nDeleteFailed;
 352                 }
 353             }
 354         };
 355
 356     protected:
 357
 358         template <class Set>
 359         void run_test( Set& testSet, size_t pass_count)
 360         {
 361             typedef Inserter<Set>       InserterThread;
 362             typedef Deleter<Set>        DeleterThread;
 363             typedef Updater<Set>        UpdaterThread;
 364
 365             m_pKeyArr.reset( new size_t[ s_nSetSize ] );
 366             m_pKeyFirst = m_pKeyArr.get();
 367             m_pKeyLast = m_pKeyFirst + s_nSetSize;
 368             for ( size_t i = 0; i < s_nSetSize; ++i )
 369                 m_pKeyArr[i] = i;
 370             shuffle( m_pKeyFirst, m_pKeyLast );
 371
 372             cds_test::thread_pool &pool = get_pool();
 373             std::unique_ptr<InserterThread> inserter(
 374                 new InserterThread(pool, testSet));
 375             std::unique_ptr<DeleterThread> deleter(
 376                 new DeleterThread(pool, testSet));
 377             std::unique_ptr<UpdaterThread> updater(
 378                 new UpdaterThread(pool, testSet));
 379
 380             for (size_t i = 0; i < pass_count; i++) {
 381               inserter->test();
 382               updater->test();
 383               deleter->test();
 384               updater->test();
 385             }
 386
 387             for (size_t *p = m_pKeyFirst; p != m_pKeyLast; ++p)
 388               testSet.erase(*p);
 389             EXPECT_TRUE( testSet.empty());
 390             EXPECT_EQ( testSet.size(), 0u );
 391         }
 392
 393         template <class Set>
 394         void run_test()
 395         {
 396             Set s( *this );
 397             run_test(s, s_nThreadPassCount);
 398         }
 399
 400         template <class Set>
 401         void run_feldman()
 402         {
 403             Set s( *this );
 404             run_test(s, s_nFeldmanThreadPassCount);
 405         }
 406
 407         template <class Set>
 408         void run_test2()
 409         {
 410             Set s( *this );
 411             run_test( s, s_nThreadPassCount);
 412         }
 413     };
 414
 415     class Set_InsDel_func_LF: public Set_InsDel_func
 416         , public ::testing::WithParamInterface<size_t>
 417     {
 418     public:
 419         template <class Set>
 420         void run_test()
 421         {
 422             s_nLoadFactor = GetParam();
 423             propout() << std::make_pair( "load_factor", s_nLoadFactor );
 424             Set_InsDel_func::run_test<Set>();
 425         }
 426
 427         template <class Set>
 428         void run_test2()
 429         {
 430             s_nLoadFactor = GetParam();
 431             propout() << std::make_pair( "load_factor", s_nLoadFactor );
 432             Set_InsDel_func::run_test2<Set>();
 433         }
 434
 435         static std::vector<size_t> get_load_factors();
 436     };
 437
 438 } // namespace set