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