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