1 // This file is part of Eigen, a lightweight C++ template library 2 // for linear algebra. 3 // 4 // Copyright (C) 2016 Dmitry Vyukov <dvyukov (at) google.com> 5 // Copyright (C) 2016 Benoit Steiner <benoit.steiner.goog (at) 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 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 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. 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. 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 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
