gdax-orderbook-hpp/demo/dependencies/libcds-2.3.2/test/stress/stack/intrusive_stack_push_pop.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 "intrusive_stack_type.h"
  32
  33 namespace cds_test {
  34
  35     class intrusive_stack_push_pop : public cds_test::stress_fixture
  36     {
  37     protected:
  38         static size_t s_nPushThreadCount;
  39         static size_t s_nPopThreadCount;
  40         static size_t s_nStackSize;
  41         static size_t s_nEliminationSize;
  42         static bool s_bFCIterative;
  43         static unsigned int s_nFCCombinePassCount;
  44         static unsigned int s_nFCCompactFactor;
  45
  46         static atomics::atomic<size_t>  s_nWorkingProducers;
  47
  48         static constexpr const size_t c_nValArraySize = 1024;
  49         static constexpr const size_t c_nBadConsumer = 0xbadc0ffe;
  50
  51         enum thread_type
  52         {
  53             producer_thread,
  54             consumer_thread
  55         };
  56
  57         struct empty
  58         {};
  59
  60         template <typename Base = empty >
  61         struct value_type : public Base
  62         {
  63             atomics::atomic<size_t> nNo;
  64             size_t      nProducer;
  65             size_t      nConsumer;
  66
  67             value_type() {}
  68             value_type( size_t n ) : nNo( n ) {}
  69         };
  70
  71
  72         template <class Stack>
  73         class Producer : public cds_test::thread
  74         {
  75             typedef cds_test::thread base_class;
  76         public:
  77             Stack&              m_Stack;
  78             size_t              m_nPushError;
  79             size_t              m_arrPush[c_nValArraySize];
  80
  81             // Interval in m_arrValue
  82             typename Stack::value_type *       m_pStart;
  83             typename Stack::value_type *       m_pEnd;
  84
  85         public:
  86             Producer( cds_test::thread_pool& pool, Stack& s )
  87                 : base_class( pool, producer_thread )
  88                 , m_Stack( s )
  89                 , m_nPushError( 0 )
  90                 , m_pStart( nullptr )
  91                 , m_pEnd( nullptr )
  92             {}
  93
  94             Producer( Producer& src )
  95                 : base_class( src )
  96                 , m_Stack( src.m_Stack )
  97                 , m_nPushError( 0 )
  98                 , m_pStart( nullptr )
  99                 , m_pEnd( nullptr )
 100             {}
 101
 102             virtual thread * clone()
 103             {
 104                 return new Producer( *this );
 105             }
 106
 107             virtual void test()
 108             {
 109                 m_nPushError = 0;
 110                 memset( m_arrPush, 0, sizeof( m_arrPush ));
 111
 112                 size_t i = 0;
 113                 for ( typename Stack::value_type * p = m_pStart; p < m_pEnd; ++p, ++i ) {
 114                     p->nProducer = id();
 115                     size_t no;
 116                     p->nNo.store( no = i % c_nValArraySize, atomics::memory_order_release );
 117                     if ( m_Stack.push( *p ))
 118                         ++m_arrPush[no];
 119                     else
 120                         ++m_nPushError;
 121                 }
 122
 123                 s_nWorkingProducers.fetch_sub( 1, atomics::memory_order_release );
 124             }
 125         };
 126
 127         template <class Stack>
 128         class Consumer : public cds_test::thread
 129         {
 130             typedef cds_test::thread base_class;
 131         public:
 132             Stack&              m_Stack;
 133             size_t              m_nPopCount;
 134             size_t              m_nPopEmpty;
 135             size_t              m_arrPop[c_nValArraySize];
 136             size_t              m_nDirtyPop;
 137         public:
 138             Consumer( cds_test::thread_pool& pool, Stack& s )
 139                 : base_class( pool, consumer_thread )
 140                 , m_Stack( s )
 141                 , m_nPopCount( 0 )
 142                 , m_nPopEmpty( 0 )
 143                 , m_nDirtyPop( 0 )
 144             {}
 145
 146             Consumer( Consumer& src )
 147                 : base_class( src )
 148                 , m_Stack( src.m_Stack )
 149                 , m_nPopCount( 0 )
 150                 , m_nPopEmpty( 0 )
 151                 , m_nDirtyPop( 0 )
 152             {}
 153
 154             virtual thread * clone()
 155             {
 156                 return new Consumer( *this );
 157             }
 158
 159             virtual void test()
 160             {
 161                 m_nPopEmpty = 0;
 162                 m_nPopCount = 0;
 163                 m_nDirtyPop = 0;
 164                 memset( m_arrPop, 0, sizeof( m_arrPop ));
 165
 166                 while ( !(s_nWorkingProducers.load( atomics::memory_order_acquire ) == 0 && m_Stack.empty())) {
 167                     typename Stack::value_type * p = m_Stack.pop();
 168                     if ( p ) {
 169                         p->nConsumer = id();
 170                         ++m_nPopCount;
 171                         size_t no = p->nNo.load( atomics::memory_order_acquire );
 172                         if ( no < sizeof( m_arrPop ) / sizeof( m_arrPop[0] ))
 173                             ++m_arrPop[no];
 174                         else
 175                             ++m_nDirtyPop;
 176                     }
 177                     else
 178                         ++m_nPopEmpty;
 179                 }
 180             }
 181         };
 182
 183         template <typename T>
 184         class value_array
 185         {
 186             std::unique_ptr< T[] > m_pArr;
 187
 188         public:
 189             value_array( size_t nSize )
 190                 : m_pArr( new T[nSize] )
 191             {}
 192
 193             T * get() const { return m_pArr.get(); }
 194         };
 195
 196     public:
 197         static void SetUpTestCase();
 198         //static void TearDownTestCase();
 199
 200     protected:
 201         template <class Stack>
 202         void analyze( Stack& /*stack*/ )
 203         {
 204             cds_test::thread_pool& pool = get_pool();
 205
 206             size_t nPushError = 0;
 207             size_t nPopEmpty = 0;
 208             size_t nPopCount = 0;
 209             size_t arrVal[c_nValArraySize];
 210             memset( arrVal, 0, sizeof( arrVal ));
 211             size_t nDirtyPop = 0;
 212
 213             for ( size_t threadNo = 0; threadNo < pool.size(); ++threadNo ) {
 214                 cds_test::thread& thread = pool.get( threadNo );
 215                 if ( thread.type() == producer_thread ) {
 216                     Producer<Stack>& producer = static_cast<Producer<Stack>&>(thread);
 217                     nPushError += producer.m_nPushError;
 218                     for ( size_t i = 0; i < sizeof( arrVal ) / sizeof( arrVal[0] ); ++i )
 219                         arrVal[i] += producer.m_arrPush[i];
 220                 }
 221                 else {
 222                     ASSERT_TRUE( thread.type() == consumer_thread );
 223                     Consumer<Stack>& consumer = static_cast<Consumer<Stack>&>(thread);
 224                     nPopEmpty += consumer.m_nPopEmpty;
 225                     nPopCount += consumer.m_nPopCount;
 226                     nDirtyPop += consumer.m_nDirtyPop;
 227                     for ( size_t i = 0; i < sizeof( arrVal ) / sizeof( arrVal[0] ); ++i )
 228                         arrVal[i] -= consumer.m_arrPop[i];
 229                 }
 230             }
 231
 232             EXPECT_EQ( nPopCount, s_nStackSize );
 233             EXPECT_EQ( nDirtyPop, 0u );
 234             EXPECT_EQ( nPushError, 0u );
 235
 236             for ( size_t i = 0; i < sizeof( arrVal ) / sizeof( arrVal[0] ); ++i ) {
 237                 EXPECT_EQ( arrVal[i], 0u ) << "i=" << i;
 238             }
 239
 240             propout() << std::make_pair( "push_count", s_nStackSize )
 241                 << std::make_pair( "push_error", nPushError )
 242                 << std::make_pair( "pop_count", nPopCount )
 243                 << std::make_pair( "pop_empty", nPopEmpty )
 244                 << std::make_pair( "dirty_pop", nDirtyPop )
 245 ;
 246
 247         }
 248
 249         template <typename Stack>
 250         void do_test( Stack& stack, value_array<typename Stack::value_type>& arrValue )
 251         {
 252             cds_test::thread_pool& pool = get_pool();
 253
 254             s_nWorkingProducers.store( s_nPushThreadCount, atomics::memory_order_release );
 255             size_t const nPushCount = s_nStackSize / s_nPushThreadCount;
 256
 257             typename Stack::value_type * pValStart = arrValue.get();
 258             typename Stack::value_type * pValEnd = pValStart + s_nStackSize;
 259
 260             pool.add( new Producer<Stack>( pool, stack ), s_nPushThreadCount );
 261             {
 262                 for ( typename Stack::value_type * it = pValStart; it != pValEnd; ++it )
 263                     it->nConsumer = c_nBadConsumer;
 264
 265                 typename Stack::value_type * pStart = pValStart;
 266                 for ( size_t thread_no = 0; thread_no < pool.size(); ++thread_no ) {
 267                     static_cast<Producer<Stack>&>(pool.get( thread_no )).m_pStart = pStart;
 268                     pStart += nPushCount;
 269                     static_cast<Producer<Stack>&>(pool.get( thread_no )).m_pEnd = pStart;
 270                 }
 271             }
 272             pool.add( new Consumer<Stack>( pool, stack ), s_nPopThreadCount );
 273
 274             propout() << std::make_pair( "producer_thread_count", s_nPushThreadCount )
 275                 << std::make_pair( "consumer_thread_count", s_nPopThreadCount )
 276                 << std::make_pair( "push_count", nPushCount * s_nPushThreadCount )
 277 ;
 278
 279             std::chrono::milliseconds duration = pool.run();
 280
 281             propout() << std::make_pair( "duration", duration );
 282
 283             s_nStackSize = nPushCount * s_nPushThreadCount;
 284
 285             {
 286                 typename Stack::value_type * pEnd = pValStart + s_nStackSize;
 287                 size_t const nBadConsumer = c_nBadConsumer;
 288                 for ( typename Stack::value_type * it = pValStart; it != pEnd; ++it )
 289                     EXPECT_NE( it->nConsumer, nBadConsumer );
 290             }
 291
 292             analyze( stack );
 293
 294             propout() << stack.statistics();
 295         }
 296     };
 297 } // namespace cds_test