2 * Copyright 2016 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 <folly/test/DeterministicSchedule.h>
25 #include <unordered_map>
28 #include <folly/Random.h>
33 FOLLY_TLS sem_t* DeterministicSchedule::tls_sem;
34 FOLLY_TLS DeterministicSchedule* DeterministicSchedule::tls_sched;
35 FOLLY_TLS unsigned DeterministicSchedule::tls_threadId;
36 thread_local AuxAct DeterministicSchedule::tls_aux_act;
37 AuxChk DeterministicSchedule::aux_chk;
39 // access is protected by futexLock
40 static std::unordered_map<detail::Futex<DeterministicAtomic>*,
41 std::list<std::pair<uint32_t, bool*>>> futexQueues;
43 static std::mutex futexLock;
45 DeterministicSchedule::DeterministicSchedule(
46 const std::function<int(int)>& scheduler)
47 : scheduler_(scheduler), nextThreadId_(1), step_(0) {
48 assert(tls_sem == nullptr);
49 assert(tls_sched == nullptr);
50 assert(tls_aux_act == nullptr);
53 sem_init(tls_sem, 0, 1);
54 sems_.push_back(tls_sem);
59 DeterministicSchedule::~DeterministicSchedule() {
60 assert(tls_sched == this);
61 assert(sems_.size() == 1);
62 assert(sems_[0] == tls_sem);
66 std::function<int(int)> DeterministicSchedule::uniform(long seed) {
67 auto rand = std::make_shared<std::ranlux48>(seed);
68 return [rand](size_t numActive) {
69 auto dist = std::uniform_int_distribution<int>(0, numActive - 1);
74 struct UniformSubset {
75 UniformSubset(long seed, int subsetSize, int stepsBetweenSelect)
76 : uniform_(DeterministicSchedule::uniform(seed)),
77 subsetSize_(subsetSize),
78 stepsBetweenSelect_(stepsBetweenSelect),
81 size_t operator()(size_t numActive) {
82 adjustPermSize(numActive);
83 if (stepsLeft_-- == 0) {
84 stepsLeft_ = stepsBetweenSelect_ - 1;
87 return perm_[uniform_(std::min(numActive, subsetSize_))];
91 std::function<int(int)> uniform_;
92 const size_t subsetSize_;
93 const int stepsBetweenSelect_;
96 // only the first subsetSize_ is properly randomized
97 std::vector<int> perm_;
99 void adjustPermSize(size_t numActive) {
100 if (perm_.size() > numActive) {
101 perm_.erase(std::remove_if(perm_.begin(),
103 [=](size_t x) { return x >= numActive; }),
106 while (perm_.size() < numActive) {
107 perm_.push_back(perm_.size());
110 assert(perm_.size() == numActive);
113 void shufflePrefix() {
114 for (size_t i = 0; i < std::min(perm_.size() - 1, subsetSize_); ++i) {
115 int j = uniform_(perm_.size() - i) + i;
116 std::swap(perm_[i], perm_[j]);
121 std::function<int(int)> DeterministicSchedule::uniformSubset(long seed,
124 auto gen = std::make_shared<UniformSubset>(seed, n, m);
125 return [=](size_t numActive) { return (*gen)(numActive); };
128 void DeterministicSchedule::beforeSharedAccess() {
134 void DeterministicSchedule::afterSharedAccess() {
135 auto sched = tls_sched;
139 sem_post(sched->sems_[sched->scheduler_(sched->sems_.size())]);
142 void DeterministicSchedule::afterSharedAccess(bool success) {
143 auto sched = tls_sched;
147 sched->callAux(success);
148 sem_post(sched->sems_[sched->scheduler_(sched->sems_.size())]);
151 int DeterministicSchedule::getRandNumber(int n) {
153 return tls_sched->scheduler_(n);
155 return Random::rand32() % n;
158 int DeterministicSchedule::getcpu(unsigned* cpu,
160 void* /* unused */) {
161 if (!tls_threadId && tls_sched) {
162 beforeSharedAccess();
163 tls_threadId = tls_sched->nextThreadId_++;
170 *node = tls_threadId;
175 void DeterministicSchedule::setAuxAct(AuxAct& aux) {
179 void DeterministicSchedule::setAuxChk(AuxChk& aux) {
183 void DeterministicSchedule::clearAuxChk() {
187 sem_t* DeterministicSchedule::beforeThreadCreate() {
188 sem_t* s = new sem_t;
190 beforeSharedAccess();
196 void DeterministicSchedule::afterThreadCreate(sem_t* sem) {
197 assert(tls_sem == nullptr);
198 assert(tls_sched == nullptr);
201 bool started = false;
203 beforeSharedAccess();
204 if (active_.count(std::this_thread::get_id()) == 1) {
211 void DeterministicSchedule::beforeThreadExit() {
212 assert(tls_sched == this);
213 beforeSharedAccess();
214 sems_.erase(std::find(sems_.begin(), sems_.end(), tls_sem));
215 active_.erase(std::this_thread::get_id());
216 if (sems_.size() > 0) {
217 FOLLY_TEST_DSCHED_VLOG("exiting");
220 sem_destroy(tls_sem);
224 tls_aux_act = nullptr;
227 void DeterministicSchedule::join(std::thread& child) {
228 auto sched = tls_sched;
232 beforeSharedAccess();
233 done = !sched->active_.count(child.get_id());
235 FOLLY_TEST_DSCHED_VLOG("joined " << std::hex << child.get_id());
243 void DeterministicSchedule::callAux(bool success) {
246 tls_aux_act(success);
247 tls_aux_act = nullptr;
254 void DeterministicSchedule::post(sem_t* sem) {
255 beforeSharedAccess();
257 FOLLY_TEST_DSCHED_VLOG("sem_post(" << sem << ")");
261 bool DeterministicSchedule::tryWait(sem_t* sem) {
262 beforeSharedAccess();
263 int rv = sem_trywait(sem);
264 int e = rv == 0 ? 0 : errno;
265 FOLLY_TEST_DSCHED_VLOG("sem_trywait(" << sem << ") = " << rv
276 void DeterministicSchedule::wait(sem_t* sem) {
277 while (!tryWait(sem)) {
278 // we're not busy waiting because this is a deterministic schedule
287 using namespace test;
288 using namespace std::chrono;
291 FutexResult Futex<DeterministicAtomic>::futexWaitImpl(
293 time_point<system_clock>* absSystemTimeout,
294 time_point<steady_clock>* absSteadyTimeout,
296 bool hasTimeout = absSystemTimeout != nullptr || absSteadyTimeout != nullptr;
298 FutexResult result = FutexResult::AWOKEN;
300 DeterministicSchedule::beforeSharedAccess();
301 FOLLY_TEST_DSCHED_VLOG(this << ".futexWait(" << std::hex << expected
302 << ", .., " << std::hex << waitMask
305 if (data == expected) {
306 auto& queue = futexQueues[this];
307 queue.emplace_back(waitMask, &awoken);
308 auto ours = queue.end();
312 DeterministicSchedule::afterSharedAccess();
313 DeterministicSchedule::beforeSharedAccess();
316 // Simulate spurious wake-ups, timeouts each time with
317 // a 10% probability if we haven't been woken up already
318 if (!awoken && hasTimeout &&
319 DeterministicSchedule::getRandNumber(100) < 10) {
320 assert(futexQueues.count(this) != 0 && &futexQueues[this] == &queue);
323 futexQueues.erase(this);
325 // Simulate ETIMEDOUT 90% of the time and other failures
327 result = DeterministicSchedule::getRandNumber(100) >= 10
328 ? FutexResult::TIMEDOUT
329 : FutexResult::INTERRUPTED;
334 result = FutexResult::VALUE_CHANGED;
338 char const* resultStr = "?";
340 case FutexResult::AWOKEN:
341 resultStr = "AWOKEN";
343 case FutexResult::TIMEDOUT:
344 resultStr = "TIMEDOUT";
346 case FutexResult::INTERRUPTED:
347 resultStr = "INTERRUPTED";
349 case FutexResult::VALUE_CHANGED:
350 resultStr = "VALUE_CHANGED";
353 FOLLY_TEST_DSCHED_VLOG(this << ".futexWait(" << std::hex << expected
354 << ", .., " << std::hex << waitMask << ") -> "
356 DeterministicSchedule::afterSharedAccess();
361 int Futex<DeterministicAtomic>::futexWake(int count, uint32_t wakeMask) {
363 DeterministicSchedule::beforeSharedAccess();
365 if (futexQueues.count(this) > 0) {
366 auto& queue = futexQueues[this];
367 auto iter = queue.begin();
368 while (iter != queue.end() && rv < count) {
370 if ((cur->first & wakeMask) != 0) {
371 *(cur->second) = true;
377 futexQueues.erase(this);
381 FOLLY_TEST_DSCHED_VLOG(this << ".futexWake(" << count << ", " << std::hex
382 << wakeMask << ") -> " << rv);
383 DeterministicSchedule::afterSharedAccess();
388 CacheLocality const& CacheLocality::system<test::DeterministicAtomic>() {
389 static CacheLocality cache(CacheLocality::uniform(16));
394 Getcpu::Func AccessSpreader<test::DeterministicAtomic>::pickGetcpuFunc() {
395 return &DeterministicSchedule::getcpu;