2 * Copyright 2015-present Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
20 #include <folly/experimental/LockFreeRingBuffer.h>
21 #include <folly/portability/GTest.h>
22 #include <folly/test/DeterministicSchedule.h>
26 TEST(LockFreeRingBuffer, writeReadSequentially) {
27 const int capacity = 256;
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;
38 for (unsigned int write = 0; write < capacity; write++) {
40 ASSERT_TRUE(rb.tryRead(dest, cur));
41 ASSERT_EQ(turn*capacity + write, dest);
47 TEST(LockFreeRingBuffer, writeReadSequentiallyBackward) {
48 const int capacity = 256;
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;
58 LockFreeRingBuffer<int>::Cursor cur = rb.currentHead();
59 cur.moveBackward(1); /// last write
60 for (int write = capacity - 1; write >= 0; write--) {
62 ASSERT_TRUE(rb.tryRead(foo, cur));
63 ASSERT_EQ(turn*capacity + write, foo);
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
76 const int sentinel = 0xfaceb00c;
78 auto reader = std::thread([&]() {
80 EXPECT_TRUE(rb.waitAndTryRead(val, cursor));
82 EXPECT_EQ(sentinel, val);
85 for (int i = 0; i < 4; i++) {
86 EXPECT_FALSE(readerHasRun);
91 EXPECT_TRUE(readerHasRun);
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;
99 struct ExposedCursor : RBCursor {
100 ExposedCursor(const RBCursor& cursor): RBCursor(cursor) {}
105 return ExposedCursor(rbcursor).value();
108 template <template <typename> class Atom>
110 LockFreeRingBuffer<int, Atom>& rb, std::atomic<int32_t>& writes
113 while ((idx = writes--) > 0) {
118 template <template <typename> class Atom>
119 void runWritesNeverFail(
120 int capacity, int writes, int writers
122 using folly::test::DeterministicSchedule;
124 DeterministicSchedule sched(DeterministicSchedule::uniform(0));
125 LockFreeRingBuffer<int, Atom> rb(capacity);
127 std::atomic<int32_t> writes_remaining(writes);
128 std::vector<std::thread> threads(writers);
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))
136 for (auto& thread : threads) {
137 DeterministicSchedule::join(thread);
140 EXPECT_EQ(writes, (value<int, Atom>)(rb.currentHead()));
143 TEST(LockFreeRingBuffer, writesNeverFail) {
144 using folly::test::DeterministicAtomic;
145 using folly::detail::EmulatedFutexAtomic;
147 runWritesNeverFail<DeterministicAtomic>(1, 100, 4);
148 runWritesNeverFail<DeterministicAtomic>(10, 100, 4);
149 runWritesNeverFail<DeterministicAtomic>(100, 1000, 8);
150 runWritesNeverFail<DeterministicAtomic>(1000, 10000, 16);
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);
157 runWritesNeverFail<EmulatedFutexAtomic>(1, 100, 4);
158 runWritesNeverFail<EmulatedFutexAtomic>(10, 100, 4);
159 runWritesNeverFail<EmulatedFutexAtomic>(100, 1000, 8);
160 runWritesNeverFail<EmulatedFutexAtomic>(1000, 10000, 16);
163 TEST(LockFreeRingBuffer, readerCanDetectSkips) {
164 const int capacity = 4;
165 const int rounds = 4;
167 LockFreeRingBuffer<int> rb(capacity);
168 auto cursor = rb.currentHead();
169 cursor.moveForward(1);
171 for (int round = 0; round < rounds; round++) {
172 for (int i = 0; i < capacity; i++) {
173 int val = round * capacity + i;
179 EXPECT_FALSE(rb.tryRead(result, cursor));
180 EXPECT_FALSE(rb.waitAndTryRead(result, cursor));
181 EXPECT_EQ(-1, result);
183 cursor = rb.currentTail();
184 EXPECT_TRUE(rb.tryRead(result, cursor));
185 EXPECT_EQ(capacity * (rounds - 1), result);
187 cursor = rb.currentTail(1.0);
188 EXPECT_TRUE(rb.tryRead(result, cursor));
189 EXPECT_EQ((capacity * rounds) - 1, result);
193 TEST(LockFreeRingBuffer, currentTailRange) {
194 const int capacity = 4;
195 LockFreeRingBuffer<int> rb(capacity);
197 // Workaround for template deduction failure
198 auto (&cursorValue)(value<int, std::atomic>);
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)));
210 EXPECT_EQ(0, cursorValue(rb.currentTail(0)));
211 EXPECT_EQ(1, cursorValue(rb.currentTail(1)));
217 EXPECT_EQ(0, cursorValue(rb.currentTail(0)));
218 EXPECT_EQ(3, cursorValue(rb.currentTail(1)));
220 auto midvalue = cursorValue(rb.currentTail(0.5));
221 // both rounding behaviours are acceptable
222 EXPECT_TRUE(midvalue == 1 || midvalue == 2);
225 TEST(LockFreeRingBuffer, cursorFromWrites) {
226 const int capacity = 3;
227 LockFreeRingBuffer<int> rb(capacity);
229 // Workaround for template deduction failure
230 auto (&cursorValue)(value<int, std::atomic>);
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)));
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)));
242 TEST(LockFreeRingBuffer, moveBackwardsCanFail) {
243 const int capacity = 3;
244 LockFreeRingBuffer<int> rb(capacity);
246 // Workaround for template deduction failure
247 auto (&cursorValue)(value<int, std::atomic>);
249 int val = 0xfaceb00c;
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