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 
test_cxx11_runqueue()230 void 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