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.
19 // This needs to be above semaphore.h due to the windows
20 // libevent implementation needing mode_t to be defined,
21 // but defining it differently than our portability
23 #include <folly/portability/SysTypes.h>
26 #include <boost/noncopyable.hpp>
28 #include <glog/logging.h>
29 #include <semaphore.h>
34 #include <unordered_set>
37 #include <folly/ScopeGuard.h>
38 #include <folly/detail/CacheLocality.h>
39 #include <folly/detail/Futex.h>
44 // This is ugly, but better perf for DeterministicAtomic translates
45 // directly to more states explored and tested
46 #define FOLLY_TEST_DSCHED_VLOG(...) \
49 VLOG(2) << std::hex << std::this_thread::get_id() << ": " \
54 /* signatures of user-defined auxiliary functions */
55 using AuxAct = std::function<void(bool)>;
56 using AuxChk = std::function<void(uint64_t)>;
59 * DeterministicSchedule coordinates the inter-thread communication of a
60 * set of threads under test, so that despite concurrency the execution is
61 * the same every time. It works by stashing a reference to the schedule
62 * in a thread-local variable, then blocking all but one thread at a time.
64 * In order for DeterministicSchedule to work, it needs to intercept
65 * all inter-thread communication. To do this you should use
66 * DeterministicAtomic<T> instead of std::atomic<T>, create threads
67 * using DeterministicSchedule::thread() instead of the std::thread
68 * constructor, DeterministicSchedule::join(thr) instead of thr.join(),
69 * and access semaphores via the helper functions in DeterministicSchedule.
70 * Locks are not yet supported, although they would be easy to add with
71 * the same strategy as the mapping of sem_wait.
73 * The actual schedule is defined by a function from n -> [0,n). At
74 * each step, the function will be given the number of active threads
75 * (n), and it returns the index of the thread that should be run next.
76 * Invocations of the scheduler function will be serialized, but will
77 * occur from multiple threads. A good starting schedule is uniform(0).
79 class DeterministicSchedule : boost::noncopyable {
82 * Arranges for the current thread (and all threads created by
83 * DeterministicSchedule::thread on a thread participating in this
84 * schedule) to participate in a deterministic schedule.
86 explicit DeterministicSchedule(const std::function<int(int)>& scheduler);
88 /** Completes the schedule. */
89 ~DeterministicSchedule();
92 * Returns a scheduling function that randomly chooses one of the
93 * runnable threads at each step, with no history. This implements
94 * a schedule that is equivalent to one in which the steps between
95 * inter-thread communication are random variables following a poisson
98 static std::function<int(int)> uniform(long seed);
101 * Returns a scheduling function that chooses a subset of the active
102 * threads and randomly chooses a member of the subset as the next
103 * runnable thread. The subset is chosen with size n, and the choice
104 * is made every m steps.
106 static std::function<int(int)> uniformSubset(long seed,
110 /** Obtains permission for the current thread to perform inter-thread
112 static void beforeSharedAccess();
114 /** Releases permission for the current thread to perform inter-thread
116 static void afterSharedAccess();
118 /** Calls a user-defined auxiliary function if any, and releases
119 * permission for the current thread to perform inter-thread
120 * communication. The bool parameter indicates the success of the
121 * shared access (if conditional, true otherwise). */
122 static void afterSharedAccess(bool success);
124 /** Launches a thread that will participate in the same deterministic
125 * schedule as the current thread. */
126 template <typename Func, typename... Args>
127 static inline std::thread thread(Func&& func, Args&&... args) {
128 // TODO: maybe future versions of gcc will allow forwarding to thread
129 auto sched = tls_sched;
130 auto sem = sched ? sched->beforeThreadCreate() : nullptr;
131 auto child = std::thread([=](Args... a) {
133 sched->afterThreadCreate(sem);
134 beforeSharedAccess();
135 FOLLY_TEST_DSCHED_VLOG("running");
140 sched->beforeThreadExit();
146 beforeSharedAccess();
147 sched->active_.insert(child.get_id());
148 FOLLY_TEST_DSCHED_VLOG("forked " << std::hex << child.get_id());
154 /** Calls child.join() as part of a deterministic schedule. */
155 static void join(std::thread& child);
157 /** Calls sem_post(sem) as part of a deterministic schedule. */
158 static void post(sem_t* sem);
160 /** Calls sem_trywait(sem) as part of a deterministic schedule, returning
161 * true on success and false on transient failure. */
162 static bool tryWait(sem_t* sem);
164 /** Calls sem_wait(sem) as part of a deterministic schedule. */
165 static void wait(sem_t* sem);
167 /** Used scheduler_ to get a random number b/w [0, n). If tls_sched is
168 * not set-up it falls back to std::rand() */
169 static int getRandNumber(int n);
171 /** Deterministic implemencation of getcpu */
172 static int getcpu(unsigned* cpu, unsigned* node, void* unused);
174 /** Sets up a thread-specific function for call immediately after
175 * the next shared access by the thread for managing auxiliary
176 * data. The function takes a bool parameter that indicates the
177 * success of the shared access (if it is conditional, true
178 * otherwise). The function is cleared after one use. */
179 static void setAuxAct(AuxAct& aux);
181 /** Sets up a function to be called after every subsequent shared
182 * access (until clearAuxChk() is called) for checking global
183 * invariants and logging. The function takes a uint64_t parameter
184 * that indicates the number of shared accesses so far. */
185 static void setAuxChk(AuxChk& aux);
187 /** Clears the function set by setAuxChk */
188 static void clearAuxChk();
191 static FOLLY_TLS sem_t* tls_sem;
192 static FOLLY_TLS DeterministicSchedule* tls_sched;
193 static FOLLY_TLS unsigned tls_threadId;
194 static thread_local AuxAct tls_aux_act;
195 static AuxChk aux_chk;
197 std::function<int(int)> scheduler_;
198 std::vector<sem_t*> sems_;
199 std::unordered_set<std::thread::id> active_;
200 unsigned nextThreadId_;
201 /* step_ keeps count of shared accesses that correspond to user
202 * synchronization steps (atomic accesses for now).
203 * The reason for keeping track of this here and not just with
204 * auxiliary data is to provide users with warning signs (e.g.,
205 * skipped steps) if they inadvertently forget to set up aux
206 * functions for some shared accesses. */
209 sem_t* beforeThreadCreate();
210 void afterThreadCreate(sem_t*);
211 void beforeThreadExit();
212 /** Calls user-defined auxiliary function (if any) */
217 * DeterministicAtomic<T> is a drop-in replacement std::atomic<T> that
218 * cooperates with DeterministicSchedule.
220 template <typename T>
221 struct DeterministicAtomic {
224 DeterministicAtomic() = default;
225 ~DeterministicAtomic() = default;
226 DeterministicAtomic(DeterministicAtomic<T> const&) = delete;
227 DeterministicAtomic<T>& operator=(DeterministicAtomic<T> const&) = delete;
229 constexpr /* implicit */ DeterministicAtomic(T v) noexcept : data(v) {}
231 bool is_lock_free() const noexcept { return data.is_lock_free(); }
233 bool compare_exchange_strong(
234 T& v0, T v1, std::memory_order mo = std::memory_order_seq_cst) noexcept {
235 DeterministicSchedule::beforeSharedAccess();
237 bool rv = data.compare_exchange_strong(v0, v1, mo);
238 FOLLY_TEST_DSCHED_VLOG(this << ".compare_exchange_strong(" << std::hex
239 << orig << ", " << std::hex << v1 << ") -> "
240 << rv << "," << std::hex << v0);
241 DeterministicSchedule::afterSharedAccess(rv);
245 bool compare_exchange_weak(
246 T& v0, T v1, std::memory_order mo = std::memory_order_seq_cst) noexcept {
247 DeterministicSchedule::beforeSharedAccess();
249 bool rv = data.compare_exchange_weak(v0, v1, mo);
250 FOLLY_TEST_DSCHED_VLOG(this << ".compare_exchange_weak(" << std::hex << orig
251 << ", " << std::hex << v1 << ") -> " << rv
252 << "," << std::hex << v0);
253 DeterministicSchedule::afterSharedAccess(rv);
257 T exchange(T v, std::memory_order mo = std::memory_order_seq_cst) noexcept {
258 DeterministicSchedule::beforeSharedAccess();
259 T rv = data.exchange(v, mo);
260 FOLLY_TEST_DSCHED_VLOG(this << ".exchange(" << std::hex << v << ") -> "
262 DeterministicSchedule::afterSharedAccess(true);
266 /* implicit */ operator T() const noexcept {
267 DeterministicSchedule::beforeSharedAccess();
269 FOLLY_TEST_DSCHED_VLOG(this << "() -> " << std::hex << rv);
270 DeterministicSchedule::afterSharedAccess(true);
274 T load(std::memory_order mo = std::memory_order_seq_cst) const noexcept {
275 DeterministicSchedule::beforeSharedAccess();
276 T rv = data.load(mo);
277 FOLLY_TEST_DSCHED_VLOG(this << ".load() -> " << std::hex << rv);
278 DeterministicSchedule::afterSharedAccess(true);
282 T operator=(T v) noexcept {
283 DeterministicSchedule::beforeSharedAccess();
285 FOLLY_TEST_DSCHED_VLOG(this << " = " << std::hex << v);
286 DeterministicSchedule::afterSharedAccess(true);
290 void store(T v, std::memory_order mo = std::memory_order_seq_cst) noexcept {
291 DeterministicSchedule::beforeSharedAccess();
293 FOLLY_TEST_DSCHED_VLOG(this << ".store(" << std::hex << v << ")");
294 DeterministicSchedule::afterSharedAccess(true);
297 T operator++() noexcept {
298 DeterministicSchedule::beforeSharedAccess();
300 FOLLY_TEST_DSCHED_VLOG(this << " pre++ -> " << std::hex << rv);
301 DeterministicSchedule::afterSharedAccess(true);
305 T operator++(int /* postDummy */) noexcept {
306 DeterministicSchedule::beforeSharedAccess();
308 FOLLY_TEST_DSCHED_VLOG(this << " post++ -> " << std::hex << rv);
309 DeterministicSchedule::afterSharedAccess(true);
313 T operator--() noexcept {
314 DeterministicSchedule::beforeSharedAccess();
316 FOLLY_TEST_DSCHED_VLOG(this << " pre-- -> " << std::hex << rv);
317 DeterministicSchedule::afterSharedAccess(true);
321 T operator--(int /* postDummy */) noexcept {
322 DeterministicSchedule::beforeSharedAccess();
324 FOLLY_TEST_DSCHED_VLOG(this << " post-- -> " << std::hex << rv);
325 DeterministicSchedule::afterSharedAccess(true);
329 T operator+=(T v) noexcept {
330 DeterministicSchedule::beforeSharedAccess();
332 FOLLY_TEST_DSCHED_VLOG(this << " += " << std::hex << v << " -> " << std::hex
334 DeterministicSchedule::afterSharedAccess(true);
339 std::memory_order /* mo */ = std::memory_order_seq_cst) noexcept {
340 DeterministicSchedule::beforeSharedAccess();
343 FOLLY_TEST_DSCHED_VLOG(this << ".fetch_add(" << std::hex << v << ") -> "
345 DeterministicSchedule::afterSharedAccess(true);
349 T operator-=(T v) noexcept {
350 DeterministicSchedule::beforeSharedAccess();
352 FOLLY_TEST_DSCHED_VLOG(this << " -= " << std::hex << v << " -> " << std::hex
354 DeterministicSchedule::afterSharedAccess(true);
359 std::memory_order /* mo */ = std::memory_order_seq_cst) noexcept {
360 DeterministicSchedule::beforeSharedAccess();
363 FOLLY_TEST_DSCHED_VLOG(this << ".fetch_sub(" << std::hex << v << ") -> "
365 DeterministicSchedule::afterSharedAccess(true);
369 T operator&=(T v) noexcept {
370 DeterministicSchedule::beforeSharedAccess();
372 FOLLY_TEST_DSCHED_VLOG(this << " &= " << std::hex << v << " -> " << std::hex
374 DeterministicSchedule::afterSharedAccess(true);
379 std::memory_order /* mo */ = std::memory_order_seq_cst) noexcept {
380 DeterministicSchedule::beforeSharedAccess();
383 FOLLY_TEST_DSCHED_VLOG(this << ".fetch_and(" << std::hex << v << ") -> "
385 DeterministicSchedule::afterSharedAccess(true);
389 T operator|=(T v) noexcept {
390 DeterministicSchedule::beforeSharedAccess();
392 FOLLY_TEST_DSCHED_VLOG(this << " |= " << std::hex << v << " -> " << std::hex
394 DeterministicSchedule::afterSharedAccess(true);
399 std::memory_order /* mo */ = std::memory_order_seq_cst) noexcept {
400 DeterministicSchedule::beforeSharedAccess();
403 FOLLY_TEST_DSCHED_VLOG(this << ".fetch_or(" << std::hex << v << ") -> "
405 DeterministicSchedule::afterSharedAccess(true);
409 T operator^=(T v) noexcept {
410 DeterministicSchedule::beforeSharedAccess();
412 FOLLY_TEST_DSCHED_VLOG(this << " ^= " << std::hex << v << " -> " << std::hex
414 DeterministicSchedule::afterSharedAccess(true);
419 std::memory_order /* mo */ = std::memory_order_seq_cst) noexcept {
420 DeterministicSchedule::beforeSharedAccess();
423 FOLLY_TEST_DSCHED_VLOG(this << ".fetch_xor(" << std::hex << v << ") -> "
425 DeterministicSchedule::afterSharedAccess(true);
429 /** Read the value of the atomic variable without context switching */
430 T load_direct() const noexcept {
431 return data.load(std::memory_order_relaxed);
436 * DeterministicMutex is a drop-in replacement of std::mutex that
437 * cooperates with DeterministicSchedule.
439 struct DeterministicMutex {
442 DeterministicMutex() = default;
443 ~DeterministicMutex() = default;
444 DeterministicMutex(DeterministicMutex const&) = delete;
445 DeterministicMutex& operator=(DeterministicMutex const&) = delete;
448 FOLLY_TEST_DSCHED_VLOG(this << ".lock()");
449 while (!try_lock()) {
450 // Not calling m.lock() in order to avoid deadlock when the
451 // mutex m is held by another thread. The deadlock would be
452 // between the call to m.lock() and the lock holder's wait on
453 // its own tls_sem scheduling semaphore.
458 DeterministicSchedule::beforeSharedAccess();
459 bool rv = m.try_lock();
460 FOLLY_TEST_DSCHED_VLOG(this << ".try_lock() -> " << rv);
461 DeterministicSchedule::afterSharedAccess();
466 FOLLY_TEST_DSCHED_VLOG(this << ".unlock()");
471 } // namespace folly::test
473 /* Specialization declarations */
479 int Futex<test::DeterministicAtomic>::futexWake(int count, uint32_t wakeMask);
482 FutexResult Futex<test::DeterministicAtomic>::futexWaitImpl(
484 std::chrono::time_point<std::chrono::system_clock>* absSystemTime,
485 std::chrono::time_point<std::chrono::steady_clock>* absSteadyTime,
489 Getcpu::Func AccessSpreader<test::DeterministicAtomic>::pickGetcpuFunc();
491 } // namespace folly::detail