folly/test/ProducerConsumerQueueTest.cpp

   1 /*
   2  * Copyright 2015 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/ProducerConsumerQueue.h>
  18
  19 #include <gtest/gtest.h>
  20 #include <vector>
  21 #include <atomic>
  22 #include <chrono>
  23 #include <memory>
  24 #include <thread>
  25 #include <glog/logging.h>
  26
  27 //////////////////////////////////////////////////////////////////////
  28
  29 namespace {
  30
  31 template<class T> struct TestTraits {
  32   T limit() const { return 1 << 24; }
  33   T generate() const { return rand() % 26; }
  34 };
  35
  36 template<> struct TestTraits<std::string> {
  37   unsigned int limit() const { return 1 << 22; }
  38   std::string generate() const { return std::string(12, ' '); }
  39 };
  40
  41 template<class QueueType, size_t Size, bool Pop = false>
  42 struct PerfTest {
  43   typedef typename QueueType::value_type T;
  44
  45   explicit PerfTest() : queue_(Size), done_(false) {}
  46
  47   void operator()() {
  48     using namespace std::chrono;
  49     auto const startTime = system_clock::now();
  50
  51     std::thread producer([this] { this->producer(); });
  52     std::thread consumer([this] { this->consumer(); });
  53
  54     producer.join();
  55     done_ = true;
  56     consumer.join();
  57
  58     auto duration = duration_cast<milliseconds>(
  59       system_clock::now() - startTime);
  60     LOG(INFO) << "     done: " << duration.count() << "ms";
  61   }
  62
  63   void producer() {
  64     // This is written differently than you might expect so that
  65     // it does not run afoul of -Wsign-compare, regardless of the
  66     // signedness of this loop's upper bound.
  67     for (auto i = traits_.limit(); i > 0; --i) {
  68       while (!queue_.write(traits_.generate())) {
  69       }
  70     }
  71   }
  72
  73   void consumer() {
  74     /*static*/ if (Pop) {
  75       while (!done_) {
  76         if (queue_.frontPtr()) {
  77           queue_.popFront();
  78         }
  79       }
  80     } else {
  81       while (!done_) {
  82         T data;
  83         queue_.read(data);
  84       }
  85     }
  86   }
  87
  88   QueueType queue_;
  89   std::atomic<bool> done_;
  90   TestTraits<T> traits_;
  91 };
  92
  93 template<class TestType> void doTest(const char* name) {
  94   LOG(INFO) << "  testing: " << name;
  95   std::unique_ptr<TestType> const t(new TestType());
  96   (*t)();
  97 }
  98
  99 template<class T, bool Pop = false>
 100 void perfTestType(const char* type) {
 101   const size_t size = 0xfffe;
 102
 103   LOG(INFO) << "Type: " << type;
 104   doTest<PerfTest<folly::ProducerConsumerQueue<T>,size,Pop> >(
 105     "ProducerConsumerQueue");
 106 }
 107
 108 template<class QueueType, size_t Size, bool Pop>
 109 struct CorrectnessTest {
 110   typedef typename QueueType::value_type T;
 111
 112   explicit CorrectnessTest()
 113     : queue_(Size)
 114     , done_(false)
 115   {
 116     const size_t testSize = traits_.limit();
 117     testData_.reserve(testSize);
 118     for (size_t i = 0; i < testSize; ++i) {
 119       testData_.push_back(traits_.generate());
 120     }
 121   }
 122
 123   void operator()() {
 124     std::thread producer([this] { this->producer(); });
 125     std::thread consumer([this] { this->consumer(); });
 126
 127     producer.join();
 128     done_ = true;
 129     consumer.join();
 130   }
 131
 132   void producer() {
 133     for (auto& data : testData_) {
 134       while (!queue_.write(data)) {
 135       }
 136     }
 137   }
 138
 139   void consumer() {
 140     if (Pop) {
 141       consumerPop();
 142     } else {
 143       consumerRead();
 144     }
 145   }
 146
 147   void consumerPop() {
 148     for (auto expect : testData_) {
 149     again:
 150       T* data;
 151       if (!(data = queue_.frontPtr())) {
 152         if (done_) {
 153           // Try one more read; unless there's a bug in the queue class
 154           // there should still be more data sitting in the queue even
 155           // though the producer thread exited.
 156           if (!(data = queue_.frontPtr())) {
 157             EXPECT_TRUE(0 && "Finished too early ...");
 158             return;
 159           }
 160         } else {
 161           goto again;
 162         }
 163       } else {
 164         queue_.popFront();
 165       }
 166
 167       EXPECT_EQ(*data, expect);
 168     }
 169   }
 170
 171   void consumerRead() {
 172     for (auto expect : testData_) {
 173     again:
 174       T data;
 175       if (!queue_.read(data)) {
 176         if (done_) {
 177           // Try one more read; unless there's a bug in the queue class
 178           // there should still be more data sitting in the queue even
 179           // though the producer thread exited.
 180           if (!queue_.read(data)) {
 181             EXPECT_TRUE(0 && "Finished too early ...");
 182             return;
 183           }
 184         } else {
 185           goto again;
 186         }
 187       }
 188       EXPECT_EQ(data, expect);
 189     }
 190   }
 191
 192   std::vector<T> testData_;
 193   QueueType queue_;
 194   TestTraits<T> traits_;
 195   std::atomic<bool> done_;
 196 };
 197
 198 template<class T, bool Pop = false>
 199 void correctnessTestType(const std::string& type) {
 200   LOG(INFO) << "Type: " << type;
 201   doTest<CorrectnessTest<folly::ProducerConsumerQueue<T>,0xfffe,Pop> >(
 202     "ProducerConsumerQueue");
 203 }
 204
 205 struct DtorChecker {
 206   static unsigned int numInstances;
 207   DtorChecker() { ++numInstances; }
 208   DtorChecker(const DtorChecker& o) { ++numInstances; }
 209   ~DtorChecker() { --numInstances; }
 210 };
 211
 212 unsigned int DtorChecker::numInstances = 0;
 213
 214 }
 215
 216 //////////////////////////////////////////////////////////////////////
 217
 218 TEST(PCQ, QueueCorrectness) {
 219   correctnessTestType<std::string,true>("string (front+pop)");
 220   correctnessTestType<std::string>("string");
 221   correctnessTestType<int>("int");
 222   correctnessTestType<unsigned long long>("unsigned long long");
 223 }
 224
 225 TEST(PCQ, PerfTest) {
 226   perfTestType<std::string,true>("string (front+pop)");
 227   perfTestType<std::string>("string");
 228   perfTestType<int>("int");
 229   perfTestType<unsigned long long>("unsigned long long");
 230 }
 231
 232 TEST(PCQ, Destructor) {
 233   // Test that orphaned elements in a ProducerConsumerQueue are
 234   // destroyed.
 235   {
 236     folly::ProducerConsumerQueue<DtorChecker> queue(1024);
 237     for (int i = 0; i < 10; ++i) {
 238       EXPECT_TRUE(queue.write(DtorChecker()));
 239     }
 240
 241     EXPECT_EQ(DtorChecker::numInstances, 10);
 242
 243     {
 244       DtorChecker ignore;
 245       EXPECT_TRUE(queue.read(ignore));
 246       EXPECT_TRUE(queue.read(ignore));
 247     }
 248
 249     EXPECT_EQ(DtorChecker::numInstances, 8);
 250   }
 251
 252   EXPECT_EQ(DtorChecker::numInstances, 0);
 253
 254   // Test the same thing in the case that the queue write pointer has
 255   // wrapped, but the read one hasn't.
 256   {
 257     folly::ProducerConsumerQueue<DtorChecker> queue(4);
 258     for (int i = 0; i < 3; ++i) {
 259       EXPECT_TRUE(queue.write(DtorChecker()));
 260     }
 261     EXPECT_EQ(DtorChecker::numInstances, 3);
 262     {
 263       DtorChecker ignore;
 264       EXPECT_TRUE(queue.read(ignore));
 265     }
 266     EXPECT_EQ(DtorChecker::numInstances, 2);
 267     EXPECT_TRUE(queue.write(DtorChecker()));
 268     EXPECT_EQ(DtorChecker::numInstances, 3);
 269   }
 270   EXPECT_EQ(DtorChecker::numInstances, 0);
 271 }
 272
 273 TEST(PCQ, EmptyFull) {
 274   folly::ProducerConsumerQueue<int> queue(3);
 275   EXPECT_TRUE(queue.isEmpty());
 276   EXPECT_FALSE(queue.isFull());
 277
 278   EXPECT_TRUE(queue.write(1));
 279   EXPECT_FALSE(queue.isEmpty());
 280   EXPECT_FALSE(queue.isFull());
 281
 282   EXPECT_TRUE(queue.write(2));
 283   EXPECT_FALSE(queue.isEmpty());
 284   EXPECT_TRUE(queue.isFull());  // Tricky: full after 2 writes, not 3.
 285
 286   EXPECT_FALSE(queue.write(3));
 287   EXPECT_EQ(queue.sizeGuess(), 2);
 288 }