2 * Copyright 2015 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.
17 #include <gflags/gflags.h>
18 #include <gtest/gtest.h>
22 #include <folly/detail/Futex.h>
23 #include <folly/experimental/LockFreeRingBuffer.h>
24 #include <folly/test/DeterministicSchedule.h>
28 TEST(LockFreeRingBuffer, writeReadSequentially) {
29 const int capacity = 256;
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;
40 for (unsigned int write = 0; write < capacity; write++) {
42 ASSERT_TRUE(rb.tryRead(dest, cur));
43 ASSERT_EQ(turn*capacity + write, dest);
49 TEST(LockFreeRingBuffer, writeReadSequentiallyBackward) {
50 const int capacity = 256;
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;
60 LockFreeRingBuffer<int>::Cursor cur = rb.currentHead();
61 cur.moveBackward(1); /// last write
62 for (int write = capacity - 1; write >= 0; write--) {
64 ASSERT_TRUE(rb.tryRead(foo, cur));
65 ASSERT_EQ(turn*capacity + write, foo);
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
78 const int sentinel = 0xfaceb00c;
80 auto reader = std::thread([&]() {
82 EXPECT_TRUE(rb.waitAndTryRead(val, cursor));
84 EXPECT_EQ(sentinel, val);
87 for (int i = 0; i < 4; i++) {
88 EXPECT_FALSE(readerHasRun);
93 EXPECT_TRUE(readerHasRun);
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;
101 RBCursor cursor = std::move(rbcursor);
103 struct ExposedCursor : RBCursor {
104 ExposedCursor(const RBCursor& cursor): RBCursor(cursor) {}
109 return ExposedCursor(cursor).value();
112 template<template<typename> class Atom>
114 LockFreeRingBuffer<int, Atom>& rb, std::atomic<int32_t>& writes
117 while ((idx = writes--) > 0) {
122 template<template<typename> class Atom>
123 void runWritesNeverFail(
124 int capacity, int writes, int writers
126 using folly::test::DeterministicSchedule;
128 DeterministicSchedule sched(DeterministicSchedule::uniform(0));
129 LockFreeRingBuffer<int, Atom> rb(capacity);
131 std::atomic<int32_t> writes_remaining(writes);
132 std::vector<std::thread> threads(writers);
134 for (int i = 0; i < writers; i++) {
135 threads[i] = DeterministicSchedule::thread(
136 std::bind(runReader<Atom>, std::ref(rb), std::ref(writes_remaining))
140 for (auto& thread : threads) {
141 DeterministicSchedule::join(thread);
144 EXPECT_EQ(writes, (value<int, Atom>)(rb.currentHead()));
147 TEST(LockFreeRingBuffer, writesNeverFail) {
148 using folly::test::DeterministicAtomic;
149 using folly::detail::EmulatedFutexAtomic;
151 runWritesNeverFail<DeterministicAtomic>(1, 100, 4);
152 runWritesNeverFail<DeterministicAtomic>(10, 100, 4);
153 runWritesNeverFail<DeterministicAtomic>(100, 1000, 8);
154 runWritesNeverFail<DeterministicAtomic>(1000, 10000, 16);
156 runWritesNeverFail<std::atomic>(1, 100, 4);
157 runWritesNeverFail<std::atomic>(10, 100, 4);
158 runWritesNeverFail<std::atomic>(100, 1000, 8);
159 runWritesNeverFail<std::atomic>(1000, 10000, 16);
161 runWritesNeverFail<EmulatedFutexAtomic>(1, 100, 4);
162 runWritesNeverFail<EmulatedFutexAtomic>(10, 100, 4);
163 runWritesNeverFail<EmulatedFutexAtomic>(100, 1000, 8);
164 runWritesNeverFail<EmulatedFutexAtomic>(1000, 10000, 16);
167 TEST(LockFreeRingBuffer, readerCanDetectSkips) {
168 const int capacity = 4;
169 const int rounds = 4;
171 LockFreeRingBuffer<int> rb(capacity);
172 auto cursor = rb.currentHead();
173 cursor.moveForward(1);
175 for (int round = 0; round < rounds; round++) {
176 for (int i = 0; i < capacity; i++) {
177 int val = round * capacity + i;
183 EXPECT_FALSE(rb.tryRead(result, cursor));
184 EXPECT_FALSE(rb.waitAndTryRead(result, cursor));
185 EXPECT_EQ(-1, result);
187 cursor = rb.currentTail();
188 EXPECT_TRUE(rb.tryRead(result, cursor));
189 EXPECT_EQ(capacity * (rounds - 1), result);
191 cursor = rb.currentTail(1.0);
192 EXPECT_TRUE(rb.tryRead(result, cursor));
193 EXPECT_EQ((capacity * rounds) - 1, result);
197 TEST(LockFreeRingBuffer, currentTailRange) {
198 const int capacity = 4;
199 LockFreeRingBuffer<int> rb(capacity);
201 // Workaround for template deduction failure
202 auto (&cursorValue)(value<int, std::atomic>);
204 // Empty buffer - everything points to 0
205 EXPECT_EQ(0, cursorValue(rb.currentTail(0)));
206 EXPECT_EQ(0, cursorValue(rb.currentTail(0.5)));
207 EXPECT_EQ(0, cursorValue(rb.currentTail(1)));
214 EXPECT_EQ(0, cursorValue(rb.currentTail(0)));
215 EXPECT_EQ(1, cursorValue(rb.currentTail(1)));
221 EXPECT_EQ(0, cursorValue(rb.currentTail(0)));
222 EXPECT_EQ(3, cursorValue(rb.currentTail(1)));
224 auto midvalue = cursorValue(rb.currentTail(0.5));
225 // both rounding behaviours are acceptable
226 EXPECT_TRUE(midvalue == 1 || midvalue == 2);