folly/experimental/test/LockFreeRingBufferTest.cpp

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