folly/experimental/test/EventCountTest.cpp

   1 /*
   2  * Copyright 2017 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #include <folly/experimental/EventCount.h>
  18
  19 #include <algorithm>
  20 #include <atomic>
  21 #include <random>
  22 #include <thread>
  23 #include <vector>
  24 #include <glog/logging.h>
  25
  26 #include <folly/Random.h>
  27 #include <folly/portability/GTest.h>
  28
  29 using namespace folly;
  30
  31 namespace {
  32
  33 class Semaphore {
  34  public:
  35   explicit Semaphore(int v=0) : value_(v) { }
  36
  37   void down() {
  38     ec_.await([this] { return tryDown(); });
  39   }
  40
  41   void up() {
  42     ++value_;
  43     ec_.notifyAll();
  44   }
  45
  46   int value() const {
  47     return value_;
  48   }
  49
  50  private:
  51   bool tryDown() {
  52     for (int v = value_; v != 0;) {
  53       if (value_.compare_exchange_weak(v, v-1)) {
  54         return true;
  55       }
  56     }
  57     return false;
  58   }
  59
  60   std::atomic<int> value_;
  61   EventCount ec_;
  62 };
  63
  64 template <class T, class Random>
  65 void randomPartition(Random& random, T key, int n,
  66                      std::vector<std::pair<T, int>>& out) {
  67   while (n != 0) {
  68     int m = std::min(n, 1000);
  69     std::uniform_int_distribution<uint32_t> u(1, m);
  70     int cut = u(random);
  71     out.emplace_back(key, cut);
  72     n -= cut;
  73   }
  74 }
  75
  76 }  // namespace
  77
  78 TEST(EventCount, Simple) {
  79   // We're basically testing for no deadlock.
  80   static const size_t count = 300000;
  81
  82   enum class Op {
  83     UP,
  84     DOWN
  85   };
  86   std::vector<std::pair<Op, int>> ops;
  87   std::mt19937 rnd(randomNumberSeed());
  88   randomPartition(rnd, Op::UP, count, ops);
  89   size_t uppers = ops.size();
  90   randomPartition(rnd, Op::DOWN, count, ops);
  91   size_t downers = ops.size() - uppers;
  92   VLOG(1) << "Using " << ops.size() << " threads: uppers=" << uppers
  93           << " downers=" << downers << " sem_count=" << count;
  94
  95   std::random_shuffle(ops.begin(), ops.end());
  96
  97   std::vector<std::thread> threads;
  98   threads.reserve(ops.size());
  99
 100   Semaphore sem;
 101   for (auto& op : ops) {
 102     int n = op.second;
 103     if (op.first == Op::UP) {
 104       auto fn = [&sem, n] () mutable {
 105         while (n--) {
 106           sem.up();
 107         }
 108       };
 109       threads.push_back(std::thread(fn));
 110     } else {
 111       auto fn = [&sem, n] () mutable {
 112         while (n--) {
 113           sem.down();
 114         }
 115       };
 116       threads.push_back(std::thread(fn));
 117     }
 118   }
 119
 120   for (auto& thread : threads) {
 121     thread.join();
 122   }
 123
 124   EXPECT_EQ(0, sem.value());
 125 }