test/stress/misc/deque_driver.cpp

   1 #include "common.h"
   2 #include <cds/misc/chase-lev-deque.h>
   3 #include <cds_test/stress_test.h>
   4 #include <cstdlib>
   5 #include <ctime>
   6 #include <iostream>
   7 #include <memory>
   8 #include <thread>
   9
  10 using namespace std;
  11
  12 namespace {
  13
  14 typedef cds_others::ChaseLevDeque Deque;
  15 static size_t s_nDequePushPercentage = 70;
  16 static size_t s_nDequeStealerThreadCount = 3;
  17 static size_t s_nDequeMainPassCount = 100000000;
  18 static size_t s_nInitialDequePushPassCount = 10000;
  19
  20 class ChaseLevDequeTest : public cds_test::stress_fixture {
  21 protected:
  22   static Deque *deque;
  23   static atomic_bool pusher_done;
  24   static ullong *sums;
  25   static ullong *succ_counts;
  26   static ullong push_sum;
  27   static ullong push_count;
  28
  29   static void SetUpTestCase() {
  30     cds_test::config const &cfg = get_config("Misc");
  31     GetConfig(DequePushPercentage);
  32     GetConfig(DequeStealerThreadCount);
  33     GetConfig(DequeMainPassCount);
  34     GetConfig(InitialDequePushPassCount);
  35   }
  36
  37   static void StealerThread(int index) {
  38     while (!pusher_done.load(memory_order_acquire)) {
  39       while (true) {
  40         int res = deque->steal();
  41         if (res != EMPTY && res != ABORT) {
  42           sums[index] += res;
  43           succ_counts[index]++;
  44         } else {
  45           break;
  46         }
  47       }
  48     }
  49   }
  50
  51   static void MainThread(int index, int push_percentage) {
  52     for (size_t i = 0; i < s_nInitialDequePushPassCount; i++) {
  53       deque->push(i + 1);
  54       push_sum += i + 1;
  55       push_count++;
  56     }
  57     for (size_t i = 0; i < s_nDequeMainPassCount; i++) {
  58       if (rand(100) < push_percentage) {
  59         int item = rand(s_nDequeMainPassCount);
  60         if (item == EMPTY || item == ABORT) {
  61           item = 1;
  62         }
  63         deque->push(item);
  64         push_sum += item;
  65         push_count++;
  66       } else {
  67         int res = deque->take();
  68         if (res != EMPTY) {
  69           sums[index] += res;
  70           succ_counts[index]++;
  71         }
  72       }
  73     }
  74     // Try take() until we don't can't take any more.
  75     while (true) {
  76       int res = deque->take();
  77       if (res != EMPTY) {
  78         sums[index] += res;
  79         succ_counts[index]++;
  80       } else {
  81         break;
  82       }
  83     }
  84   }
  85 };
  86
  87 atomic_bool ChaseLevDequeTest::pusher_done;
  88 ullong *ChaseLevDequeTest::sums;
  89 ullong *ChaseLevDequeTest::succ_counts;
  90 ullong ChaseLevDequeTest::push_count;
  91 ullong ChaseLevDequeTest::push_sum;
  92 Deque *ChaseLevDequeTest::deque;
  93
  94 TEST_F(ChaseLevDequeTest, DequePushPopTake) {
  95   deque = new Deque();
  96   push_sum = 0;
  97   sums = (ullong *)calloc(1, sizeof(ullong) * (s_nDequeStealerThreadCount + 1));
  98   succ_counts =
  99       (ullong *)calloc(1, sizeof(ullong) * (s_nDequeStealerThreadCount + 1));
 100
 101   // Stealer threads
 102   std::unique_ptr<std::thread[]> threads(
 103       new std::thread[s_nDequeStealerThreadCount]);
 104   for (ullong i = 0; i < s_nDequeStealerThreadCount; i++) {
 105     threads[i] = std::thread(StealerThread, i);
 106   }
 107
 108   MainThread(s_nDequeStealerThreadCount, s_nDequePushPercentage);
 109   pusher_done.store(true, memory_order_release);
 110
 111   for (ullong i = 0; i < s_nDequeStealerThreadCount; i++) {
 112     threads[i].join();
 113   }
 114
 115   // Result analysis
 116   ullong received_sum = 0;
 117   ullong overall_count = 0;
 118   for (ullong i = 0; i <= s_nDequeStealerThreadCount; i++) {
 119     received_sum += sums[i];
 120     overall_count += succ_counts[i];
 121   }
 122   if (overall_count != push_count || received_sum != push_sum) {
 123     cout << "Incorrect deque\n";
 124     cout << "Push sum: " << push_sum << "\n";
 125     cout << "Received sum:" << received_sum << "\n";
 126     cout << "Push count=" << push_count << "\n";
 127     cout << "Received count:" << overall_count << "\n";
 128   }
 129
 130   free(sums);
 131   free(succ_counts);
 132   delete deque;
 133 }
 134
 135 } // namespace