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;
37 // access is protected by futexLock
38 static std::unordered_map<detail::Futex<DeterministicAtomic>*,
39 std::list<std::pair<uint32_t, bool*>>> futexQueues;
41 static std::mutex futexLock;
43 DeterministicSchedule::DeterministicSchedule(
44 const std::function<int(int)>& scheduler)
45 : scheduler_(scheduler), nextThreadId_(1) {
46 assert(tls_sem == nullptr);
47 assert(tls_sched == nullptr);
50 sem_init(tls_sem, 0, 1);
51 sems_.push_back(tls_sem);
56 DeterministicSchedule::~DeterministicSchedule() {
57 assert(tls_sched == this);
58 assert(sems_.size() == 1);
59 assert(sems_[0] == tls_sem);
63 std::function<int(int)> DeterministicSchedule::uniform(long seed) {
64 auto rand = std::make_shared<std::ranlux48>(seed);
65 return [rand](size_t numActive) {
66 auto dist = std::uniform_int_distribution<int>(0, numActive - 1);
71 struct UniformSubset {
72 UniformSubset(long seed, int subsetSize, int stepsBetweenSelect)
73 : uniform_(DeterministicSchedule::uniform(seed)),
74 subsetSize_(subsetSize),
75 stepsBetweenSelect_(stepsBetweenSelect),
78 size_t operator()(size_t numActive) {
79 adjustPermSize(numActive);
80 if (stepsLeft_-- == 0) {
81 stepsLeft_ = stepsBetweenSelect_ - 1;
84 return perm_[uniform_(std::min(numActive, subsetSize_))];
88 std::function<int(int)> uniform_;
89 const size_t subsetSize_;
90 const int stepsBetweenSelect_;
93 // only the first subsetSize_ is properly randomized
94 std::vector<int> perm_;
96 void adjustPermSize(size_t numActive) {
97 if (perm_.size() > numActive) {
98 perm_.erase(std::remove_if(perm_.begin(),
100 [=](size_t x) { return x >= numActive; }),
103 while (perm_.size() < numActive) {
104 perm_.push_back(perm_.size());
107 assert(perm_.size() == numActive);
110 void shufflePrefix() {
111 for (size_t i = 0; i < std::min(perm_.size() - 1, subsetSize_); ++i) {
112 int j = uniform_(perm_.size() - i) + i;
113 std::swap(perm_[i], perm_[j]);
118 std::function<int(int)> DeterministicSchedule::uniformSubset(long seed,
121 auto gen = std::make_shared<UniformSubset>(seed, n, m);
122 return [=](size_t numActive) { return (*gen)(numActive); };
125 void DeterministicSchedule::beforeSharedAccess() {
131 void DeterministicSchedule::afterSharedAccess() {
132 auto sched = tls_sched;
137 sem_post(sched->sems_[sched->scheduler_(sched->sems_.size())]);
140 int DeterministicSchedule::getRandNumber(int n) {
142 return tls_sched->scheduler_(n);
144 return Random::rand32() % n;
147 int DeterministicSchedule::getcpu(unsigned* cpu,
149 void* /* unused */) {
150 if (!tls_threadId && tls_sched) {
151 beforeSharedAccess();
152 tls_threadId = tls_sched->nextThreadId_++;
159 *node = tls_threadId;
164 sem_t* DeterministicSchedule::beforeThreadCreate() {
165 sem_t* s = new sem_t;
167 beforeSharedAccess();
173 void DeterministicSchedule::afterThreadCreate(sem_t* sem) {
174 assert(tls_sem == nullptr);
175 assert(tls_sched == nullptr);
178 bool started = false;
180 beforeSharedAccess();
181 if (active_.count(std::this_thread::get_id()) == 1) {
188 void DeterministicSchedule::beforeThreadExit() {
189 assert(tls_sched == this);
190 beforeSharedAccess();
191 sems_.erase(std::find(sems_.begin(), sems_.end(), tls_sem));
192 active_.erase(std::this_thread::get_id());
193 if (sems_.size() > 0) {
194 FOLLY_TEST_DSCHED_VLOG("exiting");
197 sem_destroy(tls_sem);
203 void DeterministicSchedule::join(std::thread& child) {
204 auto sched = tls_sched;
208 beforeSharedAccess();
209 done = !sched->active_.count(child.get_id());
211 FOLLY_TEST_DSCHED_VLOG("joined " << std::hex << child.get_id());
219 void DeterministicSchedule::post(sem_t* sem) {
220 beforeSharedAccess();
222 FOLLY_TEST_DSCHED_VLOG("sem_post(" << sem << ")");
226 bool DeterministicSchedule::tryWait(sem_t* sem) {
227 beforeSharedAccess();
228 int rv = sem_trywait(sem);
229 int e = rv == 0 ? 0 : errno;
230 FOLLY_TEST_DSCHED_VLOG("sem_trywait(" << sem << ") = " << rv
241 void DeterministicSchedule::wait(sem_t* sem) {
242 while (!tryWait(sem)) {
243 // we're not busy waiting because this is a deterministic schedule
252 using namespace test;
253 using namespace std::chrono;
256 FutexResult Futex<DeterministicAtomic>::futexWaitImpl(
258 time_point<system_clock>* absSystemTimeout,
259 time_point<steady_clock>* absSteadyTimeout,
261 bool hasTimeout = absSystemTimeout != nullptr || absSteadyTimeout != nullptr;
263 FutexResult result = FutexResult::AWOKEN;
265 DeterministicSchedule::beforeSharedAccess();
266 FOLLY_TEST_DSCHED_VLOG(this << ".futexWait(" << std::hex << expected
267 << ", .., " << std::hex << waitMask
270 if (data == expected) {
271 auto& queue = futexQueues[this];
272 queue.emplace_back(waitMask, &awoken);
273 auto ours = queue.end();
277 DeterministicSchedule::afterSharedAccess();
278 DeterministicSchedule::beforeSharedAccess();
281 // Simulate spurious wake-ups, timeouts each time with
282 // a 10% probability if we haven't been woken up already
283 if (!awoken && hasTimeout &&
284 DeterministicSchedule::getRandNumber(100) < 10) {
285 assert(futexQueues.count(this) != 0 && &futexQueues[this] == &queue);
288 futexQueues.erase(this);
290 // Simulate ETIMEDOUT 90% of the time and other failures
292 result = DeterministicSchedule::getRandNumber(100) >= 10
293 ? FutexResult::TIMEDOUT
294 : FutexResult::INTERRUPTED;
299 result = FutexResult::VALUE_CHANGED;
303 char const* resultStr = "?";
305 case FutexResult::AWOKEN:
306 resultStr = "AWOKEN";
308 case FutexResult::TIMEDOUT:
309 resultStr = "TIMEDOUT";
311 case FutexResult::INTERRUPTED:
312 resultStr = "INTERRUPTED";
314 case FutexResult::VALUE_CHANGED:
315 resultStr = "VALUE_CHANGED";
318 FOLLY_TEST_DSCHED_VLOG(this << ".futexWait(" << std::hex << expected
319 << ", .., " << std::hex << waitMask << ") -> "
321 DeterministicSchedule::afterSharedAccess();
326 int Futex<DeterministicAtomic>::futexWake(int count, uint32_t wakeMask) {
328 DeterministicSchedule::beforeSharedAccess();
330 if (futexQueues.count(this) > 0) {
331 auto& queue = futexQueues[this];
332 auto iter = queue.begin();
333 while (iter != queue.end() && rv < count) {
335 if ((cur->first & wakeMask) != 0) {
336 *(cur->second) = true;
342 futexQueues.erase(this);
346 FOLLY_TEST_DSCHED_VLOG(this << ".futexWake(" << count << ", " << std::hex
347 << wakeMask << ") -> " << rv);
348 DeterministicSchedule::afterSharedAccess();
353 CacheLocality const& CacheLocality::system<test::DeterministicAtomic>() {
354 static CacheLocality cache(CacheLocality::uniform(16));
359 Getcpu::Func AccessSpreader<test::DeterministicAtomic>::pickGetcpuFunc() {
360 return &DeterministicSchedule::getcpu;