2 * Copyright 2017 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<size_t(size_t)>& 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<size_t(size_t)> DeterministicSchedule::uniform(uint64_t seed) {
67 auto rand = std::make_shared<std::ranlux48>(seed);
68 return [rand](size_t numActive) {
69 auto dist = std::uniform_int_distribution<size_t>(0, numActive - 1);
74 struct UniformSubset {
75 UniformSubset(uint64_t seed, size_t subsetSize, size_t 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<size_t(size_t)> uniform_;
92 const size_t subsetSize_;
93 const size_t stepsBetweenSelect_;
96 // only the first subsetSize_ is properly randomized
97 std::vector<size_t> 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 size_t j = uniform_(perm_.size() - i) + i;
116 std::swap(perm_[i], perm_[j]);
121 std::function<size_t(size_t)>
122 DeterministicSchedule::uniformSubset(uint64_t seed, size_t n, size_t m) {
123 auto gen = std::make_shared<UniformSubset>(seed, n, m);
124 return [=](size_t numActive) { return (*gen)(numActive); };
127 void DeterministicSchedule::beforeSharedAccess() {
133 void DeterministicSchedule::afterSharedAccess() {
134 auto sched = tls_sched;
138 sem_post(sched->sems_[sched->scheduler_(sched->sems_.size())]);
141 void DeterministicSchedule::afterSharedAccess(bool success) {
142 auto sched = tls_sched;
146 sched->callAux(success);
147 sem_post(sched->sems_[sched->scheduler_(sched->sems_.size())]);
150 size_t DeterministicSchedule::getRandNumber(size_t n) {
152 return tls_sched->scheduler_(n);
154 return Random::rand32() % n;
157 int DeterministicSchedule::getcpu(unsigned* cpu,
159 void* /* unused */) {
160 if (!tls_threadId && tls_sched) {
161 beforeSharedAccess();
162 tls_threadId = tls_sched->nextThreadId_++;
169 *node = tls_threadId;
174 void DeterministicSchedule::setAuxAct(AuxAct& aux) {
178 void DeterministicSchedule::setAuxChk(AuxChk& aux) {
182 void DeterministicSchedule::clearAuxChk() {
186 sem_t* DeterministicSchedule::beforeThreadCreate() {
187 sem_t* s = new sem_t;
189 beforeSharedAccess();
195 void DeterministicSchedule::afterThreadCreate(sem_t* sem) {
196 assert(tls_sem == nullptr);
197 assert(tls_sched == nullptr);
200 bool started = false;
202 beforeSharedAccess();
203 if (active_.count(std::this_thread::get_id()) == 1) {
210 void DeterministicSchedule::beforeThreadExit() {
211 assert(tls_sched == this);
212 beforeSharedAccess();
213 sems_.erase(std::find(sems_.begin(), sems_.end(), tls_sem));
214 active_.erase(std::this_thread::get_id());
215 if (sems_.size() > 0) {
216 FOLLY_TEST_DSCHED_VLOG("exiting");
219 sem_destroy(tls_sem);
223 tls_aux_act = nullptr;
226 void DeterministicSchedule::join(std::thread& child) {
227 auto sched = tls_sched;
231 beforeSharedAccess();
232 done = !sched->active_.count(child.get_id());
234 FOLLY_TEST_DSCHED_VLOG("joined " << std::hex << child.get_id());
242 void DeterministicSchedule::callAux(bool success) {
245 tls_aux_act(success);
246 tls_aux_act = nullptr;
253 void DeterministicSchedule::post(sem_t* sem) {
254 beforeSharedAccess();
256 FOLLY_TEST_DSCHED_VLOG("sem_post(" << sem << ")");
260 bool DeterministicSchedule::tryWait(sem_t* sem) {
261 beforeSharedAccess();
262 int rv = sem_trywait(sem);
263 int e = rv == 0 ? 0 : errno;
264 FOLLY_TEST_DSCHED_VLOG("sem_trywait(" << sem << ") = " << rv
275 void DeterministicSchedule::wait(sem_t* sem) {
276 while (!tryWait(sem)) {
277 // we're not busy waiting because this is a deterministic schedule
286 using namespace test;
287 using namespace std::chrono;
290 FutexResult Futex<DeterministicAtomic>::futexWaitImpl(
292 time_point<system_clock>* absSystemTimeout,
293 time_point<steady_clock>* absSteadyTimeout,
295 bool hasTimeout = absSystemTimeout != nullptr || absSteadyTimeout != nullptr;
297 FutexResult result = FutexResult::AWOKEN;
299 DeterministicSchedule::beforeSharedAccess();
300 FOLLY_TEST_DSCHED_VLOG(this << ".futexWait(" << std::hex << expected
301 << ", .., " << std::hex << waitMask
304 if (this->data == expected) {
305 auto& queue = futexQueues[this];
306 queue.emplace_back(waitMask, &awoken);
307 auto ours = queue.end();
311 DeterministicSchedule::afterSharedAccess();
312 DeterministicSchedule::beforeSharedAccess();
315 // Simulate spurious wake-ups, timeouts each time with
316 // a 10% probability if we haven't been woken up already
317 if (!awoken && hasTimeout &&
318 DeterministicSchedule::getRandNumber(100) < 10) {
319 assert(futexQueues.count(this) != 0 && &futexQueues[this] == &queue);
322 futexQueues.erase(this);
324 // Simulate ETIMEDOUT 90% of the time and other failures
326 result = DeterministicSchedule::getRandNumber(100) >= 10
327 ? FutexResult::TIMEDOUT
328 : FutexResult::INTERRUPTED;
333 result = FutexResult::VALUE_CHANGED;
337 char const* resultStr = "?";
339 case FutexResult::AWOKEN:
340 resultStr = "AWOKEN";
342 case FutexResult::TIMEDOUT:
343 resultStr = "TIMEDOUT";
345 case FutexResult::INTERRUPTED:
346 resultStr = "INTERRUPTED";
348 case FutexResult::VALUE_CHANGED:
349 resultStr = "VALUE_CHANGED";
352 FOLLY_TEST_DSCHED_VLOG(this << ".futexWait(" << std::hex << expected
353 << ", .., " << std::hex << waitMask << ") -> "
355 DeterministicSchedule::afterSharedAccess();
360 int Futex<DeterministicAtomic>::futexWake(int count, uint32_t wakeMask) {
362 DeterministicSchedule::beforeSharedAccess();
364 if (futexQueues.count(this) > 0) {
365 auto& queue = futexQueues[this];
366 auto iter = queue.begin();
367 while (iter != queue.end() && rv < count) {
369 if ((cur->first & wakeMask) != 0) {
370 *(cur->second) = true;
376 futexQueues.erase(this);
380 FOLLY_TEST_DSCHED_VLOG(this << ".futexWake(" << count << ", " << std::hex
381 << wakeMask << ") -> " << rv);
382 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 &detail::DeterministicSchedule::getcpu;