folly/experimental/test/LockFreeRingBufferTest.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 <gtest/gtest.h>
  18 #include <iostream>
  19 #include <thread>
  20
  21 #include <folly/detail/Futex.h>
  22 #include <folly/experimental/LockFreeRingBuffer.h>
  23 #include <folly/test/DeterministicSchedule.h>
  24
  25 namespace folly {
  26
  27 TEST(LockFreeRingBuffer, writeReadSequentially) {
  28   const int capacity = 256;
  29   const int turns = 4;
  30
  31   LockFreeRingBuffer<int> rb(capacity);
  32   LockFreeRingBuffer<int>::Cursor cur = rb.currentHead();
  33   for (unsigned int turn = 0; turn < turns; turn++) {
  34     for (unsigned int write = 0; write < capacity; write++) {
  35       int val = turn*capacity + write;
  36       rb.write(val);
  37     }
  38
  39     for (unsigned int write = 0; write < capacity; write++) {
  40       int dest = 0;
  41       ASSERT_TRUE(rb.tryRead(dest, cur));
  42       ASSERT_EQ(turn*capacity + write, dest);
  43       cur.moveForward();
  44     }
  45   }
  46 }
  47
  48 TEST(LockFreeRingBuffer, writeReadSequentiallyBackward) {
  49   const int capacity = 256;
  50   const int turns = 4;
  51
  52   LockFreeRingBuffer<int> rb(capacity);
  53   for (unsigned int turn = 0; turn < turns; turn++) {
  54     for (unsigned int write = 0; write < capacity; write++) {
  55       int val = turn*capacity + write;
  56       rb.write(val);
  57     }
  58
  59     LockFreeRingBuffer<int>::Cursor cur = rb.currentHead();
  60     cur.moveBackward(1); /// last write
  61     for (int write = capacity - 1; write >= 0; write--) {
  62       int foo = 0;
  63       ASSERT_TRUE(rb.tryRead(foo, cur));
  64       ASSERT_EQ(turn*capacity + write, foo);
  65       cur.moveBackward();
  66     }
  67   }
  68 }
  69
  70 TEST(LockFreeRingBuffer, readsCanBlock) {
  71   // Start a reader thread, confirm that reading can block
  72   std::atomic<bool> readerHasRun(false);
  73   LockFreeRingBuffer<int> rb(1);
  74   auto cursor = rb.currentHead();
  75   cursor.moveForward(3); // wait for the 4th write
  76
  77   const int sentinel = 0xfaceb00c;
  78
  79   auto reader = std::thread([&]() {
  80     int val = 0;
  81     EXPECT_TRUE(rb.waitAndTryRead(val, cursor));
  82     readerHasRun = true;
  83     EXPECT_EQ(sentinel, val);
  84   });
  85
  86   for (int i = 0; i < 4; i++) {
  87     EXPECT_FALSE(readerHasRun);
  88     int val = sentinel;
  89     rb.write(val);
  90   }
  91   reader.join();
  92   EXPECT_TRUE(readerHasRun);
  93 }
  94
  95 // expose the cursor raw value via a wrapper type
  96 template<typename T, template<typename> class Atom>
  97 uint64_t value(const typename LockFreeRingBuffer<T, Atom>::Cursor& rbcursor) {
  98   typedef typename LockFreeRingBuffer<T,Atom>::Cursor RBCursor;
  99
 100   struct ExposedCursor : RBCursor {
 101     ExposedCursor(const RBCursor& cursor): RBCursor(cursor) {}
 102     uint64_t value(){
 103       return this->ticket;
 104     }
 105   };
 106   return ExposedCursor(rbcursor).value();
 107 }
 108
 109 template<template<typename> class Atom>
 110 void runReader(
 111     LockFreeRingBuffer<int, Atom>& rb, std::atomic<int32_t>& writes
 112 ) {
 113   int32_t idx;
 114   while ((idx = writes--) > 0) {
 115     rb.write(idx);
 116   }
 117 }
 118
 119 template<template<typename> class Atom>
 120 void runWritesNeverFail(
 121     int capacity, int writes, int writers
 122 ) {
 123   using folly::test::DeterministicSchedule;
 124
 125   DeterministicSchedule sched(DeterministicSchedule::uniform(0));
 126   LockFreeRingBuffer<int, Atom> rb(capacity);
 127
 128   std::atomic<int32_t> writes_remaining(writes);
 129   std::vector<std::thread> threads(writers);
 130
 131   for (int i = 0; i < writers; i++) {
 132     threads[i] = DeterministicSchedule::thread(
 133         std::bind(runReader<Atom>, std::ref(rb), std::ref(writes_remaining))
 134     );
 135   }
 136
 137   for (auto& thread : threads) {
 138     DeterministicSchedule::join(thread);
 139   }
 140
 141   EXPECT_EQ(writes, (value<int, Atom>)(rb.currentHead()));
 142 }
 143
 144 TEST(LockFreeRingBuffer, writesNeverFail) {
 145   using folly::test::DeterministicAtomic;
 146   using folly::detail::EmulatedFutexAtomic;
 147
 148   runWritesNeverFail<DeterministicAtomic>(1, 100, 4);
 149   runWritesNeverFail<DeterministicAtomic>(10, 100, 4);
 150   runWritesNeverFail<DeterministicAtomic>(100, 1000, 8);
 151   runWritesNeverFail<DeterministicAtomic>(1000, 10000, 16);
 152
 153   runWritesNeverFail<std::atomic>(1, 100, 4);
 154   runWritesNeverFail<std::atomic>(10, 100, 4);
 155   runWritesNeverFail<std::atomic>(100, 1000, 8);
 156   runWritesNeverFail<std::atomic>(1000, 10000, 16);
 157
 158   runWritesNeverFail<EmulatedFutexAtomic>(1, 100, 4);
 159   runWritesNeverFail<EmulatedFutexAtomic>(10, 100, 4);
 160   runWritesNeverFail<EmulatedFutexAtomic>(100, 1000, 8);
 161   runWritesNeverFail<EmulatedFutexAtomic>(1000, 10000, 16);
 162 }
 163
 164 TEST(LockFreeRingBuffer, readerCanDetectSkips) {
 165   const int capacity = 4;
 166   const int rounds = 4;
 167
 168   LockFreeRingBuffer<int> rb(capacity);
 169   auto cursor = rb.currentHead();
 170   cursor.moveForward(1);
 171
 172   for (int round = 0; round < rounds; round++) {
 173     for (int i = 0; i < capacity; i++) {
 174       int val = round * capacity + i;
 175       rb.write(val);
 176     }
 177   }
 178
 179   int result = -1;
 180   EXPECT_FALSE(rb.tryRead(result, cursor));
 181   EXPECT_FALSE(rb.waitAndTryRead(result, cursor));
 182   EXPECT_EQ(-1, result);
 183
 184   cursor = rb.currentTail();
 185   EXPECT_TRUE(rb.tryRead(result, cursor));
 186   EXPECT_EQ(capacity * (rounds - 1), result);
 187
 188   cursor = rb.currentTail(1.0);
 189   EXPECT_TRUE(rb.tryRead(result, cursor));
 190   EXPECT_EQ((capacity * rounds) - 1, result);
 191 }
 192
 193
 194 TEST(LockFreeRingBuffer, currentTailRange) {
 195   const int capacity = 4;
 196   LockFreeRingBuffer<int> rb(capacity);
 197
 198   // Workaround for template deduction failure
 199   auto (&cursorValue)(value<int, std::atomic>);
 200
 201   // Empty buffer - everything points to 0
 202   EXPECT_EQ(0, cursorValue(rb.currentTail(0)));
 203   EXPECT_EQ(0, cursorValue(rb.currentTail(0.5)));
 204   EXPECT_EQ(0, cursorValue(rb.currentTail(1)));
 205
 206   // Half-full
 207   int val = 5;
 208   rb.write(val);
 209   rb.write(val);
 210
 211   EXPECT_EQ(0, cursorValue(rb.currentTail(0)));
 212   EXPECT_EQ(1, cursorValue(rb.currentTail(1)));
 213
 214   // Full
 215   rb.write(val);
 216   rb.write(val);
 217
 218   EXPECT_EQ(0, cursorValue(rb.currentTail(0)));
 219   EXPECT_EQ(3, cursorValue(rb.currentTail(1)));
 220
 221   auto midvalue = cursorValue(rb.currentTail(0.5));
 222   // both rounding behaviours are acceptable
 223   EXPECT_TRUE(midvalue == 1 || midvalue == 2);
 224 }
 225
 226 TEST(LockFreeRingBuffer, cursorFromWrites) {
 227   const int capacity = 3;
 228   LockFreeRingBuffer<int> rb(capacity);
 229
 230   // Workaround for template deduction failure
 231   auto (&cursorValue)(value<int, std::atomic>);
 232
 233   int val = 0xfaceb00c;
 234   EXPECT_EQ(0, cursorValue(rb.writeAndGetCursor(val)));
 235   EXPECT_EQ(1, cursorValue(rb.writeAndGetCursor(val)));
 236   EXPECT_EQ(2, cursorValue(rb.writeAndGetCursor(val)));
 237
 238   // Check that rb is giving out actual cursors and not just
 239   // pointing to the current slot.
 240   EXPECT_EQ(3, cursorValue(rb.writeAndGetCursor(val)));
 241 }
 242
 243 TEST(LockFreeRingBuffer, moveBackwardsCanFail) {
 244   const int capacity = 3;
 245   LockFreeRingBuffer<int> rb(capacity);
 246
 247   // Workaround for template deduction failure
 248   auto (&cursorValue)(value<int, std::atomic>);
 249
 250   int val = 0xfaceb00c;
 251   rb.write(val);
 252   rb.write(val);
 253
 254   auto cursor = rb.currentHead(); // points to 2
 255   EXPECT_EQ(2, cursorValue(cursor));
 256   EXPECT_TRUE(cursor.moveBackward());
 257   EXPECT_TRUE(cursor.moveBackward()); // now at 0
 258   EXPECT_FALSE(cursor.moveBackward()); // moving back does nothing
 259 }
 260
 261 } // namespace folly