folly/test/ProducerConsumerQueueTest.cpp

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