1 // This file is part of Eigen, a lightweight C++ template library
2 // for linear algebra.
3 //
4 // Copyright (C) 2016 Dmitry Vyukov <dvyukov@google.com>
5 // Copyright (C) 2016 Benoit Steiner <benoit.steiner.goog@gmail.com>
6 //
7 // This Source Code Form is subject to the terms of the Mozilla
8 // Public License v. 2.0. If a copy of the MPL was not distributed
9 // with this file, You can obtain one at http://mozilla.org/MPL/2.0/.
10
11 #define EIGEN_USE_THREADS
12 #include <cstdlib>
13 #include "main.h"
14 #include <Eigen/CXX11/ThreadPool>
15
16
17 // Visual studio doesn't implement a rand_r() function since its
18 // implementation of rand() is already thread safe
rand_reentrant(unsigned int * s)19 int rand_reentrant(unsigned int* s) {
20 #ifdef EIGEN_COMP_MSVC_STRICT
21 EIGEN_UNUSED_VARIABLE(s);
22 return rand();
23 #else
24 return rand_r(s);
25 #endif
26 }
27
test_basic_runqueue()28 void test_basic_runqueue()
29 {
30 RunQueue<int, 4> q;
31 // Check empty state.
32 VERIFY(q.Empty());
33 VERIFY_IS_EQUAL(0u, q.Size());
34 VERIFY_IS_EQUAL(0, q.PopFront());
35 std::vector<int> stolen;
36 VERIFY_IS_EQUAL(0u, q.PopBackHalf(&stolen));
37 VERIFY_IS_EQUAL(0u, stolen.size());
38 // Push one front, pop one front.
39 VERIFY_IS_EQUAL(0, q.PushFront(1));
40 VERIFY_IS_EQUAL(1u, q.Size());
41 VERIFY_IS_EQUAL(1, q.PopFront());
42 VERIFY_IS_EQUAL(0u, q.Size());
43 // Push front to overflow.
44 VERIFY_IS_EQUAL(0, q.PushFront(2));
45 VERIFY_IS_EQUAL(1u, q.Size());
46 VERIFY_IS_EQUAL(0, q.PushFront(3));
47 VERIFY_IS_EQUAL(2u, q.Size());
48 VERIFY_IS_EQUAL(0, q.PushFront(4));
49 VERIFY_IS_EQUAL(3u, q.Size());
50 VERIFY_IS_EQUAL(0, q.PushFront(5));
51 VERIFY_IS_EQUAL(4u, q.Size());
52 VERIFY_IS_EQUAL(6, q.PushFront(6));
53 VERIFY_IS_EQUAL(4u, q.Size());
54 VERIFY_IS_EQUAL(5, q.PopFront());
55 VERIFY_IS_EQUAL(3u, q.Size());
56 VERIFY_IS_EQUAL(4, q.PopFront());
57 VERIFY_IS_EQUAL(2u, q.Size());
58 VERIFY_IS_EQUAL(3, q.PopFront());
59 VERIFY_IS_EQUAL(1u, q.Size());
60 VERIFY_IS_EQUAL(2, q.PopFront());
61 VERIFY_IS_EQUAL(0u, q.Size());
62 VERIFY_IS_EQUAL(0, q.PopFront());
63 // Push one back, pop one back.
64 VERIFY_IS_EQUAL(0, q.PushBack(7));
65 VERIFY_IS_EQUAL(1u, q.Size());
66 VERIFY_IS_EQUAL(1u, q.PopBackHalf(&stolen));
67 VERIFY_IS_EQUAL(1u, stolen.size());
68 VERIFY_IS_EQUAL(7, stolen[0]);
69 VERIFY_IS_EQUAL(0u, q.Size());
70 stolen.clear();
71 // Push back to overflow.
72 VERIFY_IS_EQUAL(0, q.PushBack(8));
73 VERIFY_IS_EQUAL(1u, q.Size());
74 VERIFY_IS_EQUAL(0, q.PushBack(9));
75 VERIFY_IS_EQUAL(2u, q.Size());
76 VERIFY_IS_EQUAL(0, q.PushBack(10));
77 VERIFY_IS_EQUAL(3u, q.Size());
78 VERIFY_IS_EQUAL(0, q.PushBack(11));
79 VERIFY_IS_EQUAL(4u, q.Size());
80 VERIFY_IS_EQUAL(12, q.PushBack(12));
81 VERIFY_IS_EQUAL(4u, q.Size());
82 // Pop back in halves.
83 VERIFY_IS_EQUAL(2u, q.PopBackHalf(&stolen));
84 VERIFY_IS_EQUAL(2u, stolen.size());
85 VERIFY_IS_EQUAL(10, stolen[0]);
86 VERIFY_IS_EQUAL(11, stolen[1]);
87 VERIFY_IS_EQUAL(2u, q.Size());
88 stolen.clear();
89 VERIFY_IS_EQUAL(1u, q.PopBackHalf(&stolen));
90 VERIFY_IS_EQUAL(1u, stolen.size());
91 VERIFY_IS_EQUAL(9, stolen[0]);
92 VERIFY_IS_EQUAL(1u, q.Size());
93 stolen.clear();
94 VERIFY_IS_EQUAL(1u, q.PopBackHalf(&stolen));
95 VERIFY_IS_EQUAL(1u, stolen.size());
96 VERIFY_IS_EQUAL(8, stolen[0]);
97 stolen.clear();
98 VERIFY_IS_EQUAL(0u, q.PopBackHalf(&stolen));
99 VERIFY_IS_EQUAL(0u, stolen.size());
100 // Empty again.
101 VERIFY(q.Empty());
102 VERIFY_IS_EQUAL(0u, q.Size());
103 VERIFY_IS_EQUAL(0, q.PushFront(1));
104 VERIFY_IS_EQUAL(0, q.PushFront(2));
105 VERIFY_IS_EQUAL(0, q.PushFront(3));
106 VERIFY_IS_EQUAL(1, q.PopBack());
107 VERIFY_IS_EQUAL(2, q.PopBack());
108 VERIFY_IS_EQUAL(3, q.PopBack());
109 VERIFY(q.Empty());
110 VERIFY_IS_EQUAL(0u, q.Size());
111 }
112
113 // Empty tests that the queue is not claimed to be empty when is is in fact not.
114 // Emptiness property is crucial part of thread pool blocking scheme,
115 // so we go to great effort to ensure this property. We create a queue with
116 // 1 element and then push 1 element (either front or back at random) and pop
117 // 1 element (either front or back at random). So queue always contains at least
118 // 1 element, but otherwise changes chaotically. Another thread constantly tests
119 // that the queue is not claimed to be empty.
test_empty_runqueue()120 void test_empty_runqueue()
121 {
122 RunQueue<int, 4> q;
123 q.PushFront(1);
124 std::atomic<bool> done(false);
125 std::thread mutator([&q, &done]() {
126 unsigned rnd = 0;
127 std::vector<int> stolen;
128 for (int i = 0; i < 1 << 18; i++) {
129 if (rand_reentrant(&rnd) % 2)
130 VERIFY_IS_EQUAL(0, q.PushFront(1));
131 else
132 VERIFY_IS_EQUAL(0, q.PushBack(1));
133 if (rand_reentrant(&rnd) % 2)
134 VERIFY_IS_EQUAL(1, q.PopFront());
135 else {
136 for (;;) {
137 if (q.PopBackHalf(&stolen) == 1) {
138 stolen.clear();
139 break;
140 }
141 VERIFY_IS_EQUAL(0u, stolen.size());
142 }
143 }
144 }
145 done = true;
146 });
147 while (!done) {
148 VERIFY(!q.Empty());
149 int size = q.Size();
150 VERIFY_GE(size, 1);
151 VERIFY_LE(size, 2);
152 }
153 VERIFY_IS_EQUAL(1, q.PopFront());
154 mutator.join();
155 }
156
157 // Stress is a chaotic random test.
158 // One thread (owner) calls PushFront/PopFront, other threads call PushBack/
159 // PopBack. Ensure that we don't crash, deadlock, and all sanity checks pass.
test_stress_runqueue()160 void test_stress_runqueue()
161 {
162 static const int kEvents = 1 << 18;
163 RunQueue<int, 8> q;
164 std::atomic<int> total(0);
165 std::vector<std::unique_ptr<std::thread>> threads;
166 threads.emplace_back(new std::thread([&q, &total]() {
167 int sum = 0;
168 int pushed = 1;
169 int popped = 1;
170 while (pushed < kEvents || popped < kEvents) {
171 if (pushed < kEvents) {
172 if (q.PushFront(pushed) == 0) {
173 sum += pushed;
174 pushed++;
175 }
176 }
177 if (popped < kEvents) {
178 int v = q.PopFront();
179 if (v != 0) {
180 sum -= v;
181 popped++;
182 }
183 }
184 }
185 total += sum;
186 }));
187 for (int i = 0; i < 2; i++) {
188 threads.emplace_back(new std::thread([&q, &total]() {
189 int sum = 0;
190 for (int j = 1; j < kEvents; j++) {
191 if (q.PushBack(j) == 0) {
192 sum += j;
193 continue;
194 }
195 EIGEN_THREAD_YIELD();
196 j--;
197 }
198 total += sum;
199 }));
200 threads.emplace_back(new std::thread([&q, &total]() {
201 int sum = 0;
202 std::vector<int> stolen;
203 for (int j = 1; j < kEvents;) {
204 if (q.PopBackHalf(&stolen) == 0) {
205 EIGEN_THREAD_YIELD();
206 continue;
207 }
208 while (stolen.size() && j < kEvents) {
209 int v = stolen.back();
210 stolen.pop_back();
211 VERIFY_IS_NOT_EQUAL(v, 0);
212 sum += v;
213 j++;
214 }
215 }
216 while (stolen.size()) {
217 int v = stolen.back();
218 stolen.pop_back();
219 VERIFY_IS_NOT_EQUAL(v, 0);
220 while ((v = q.PushBack(v)) != 0) EIGEN_THREAD_YIELD();
221 }
222 total -= sum;
223 }));
224 }
225 for (size_t i = 0; i < threads.size(); i++) threads[i]->join();
226 VERIFY(q.Empty());
227 VERIFY(total.load() == 0);
228 }
229
EIGEN_DECLARE_TEST(cxx11_runqueue)230 EIGEN_DECLARE_TEST(cxx11_runqueue)
231 {
232 CALL_SUBTEST_1(test_basic_runqueue());
233 CALL_SUBTEST_2(test_empty_runqueue());
234 CALL_SUBTEST_3(test_stress_runqueue());
235 }
236