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.
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/AtomicUtils.h>
39 #include <folly/detail/CacheLocality.h>
40 #include <folly/detail/Futex.h>
45 // This is ugly, but better perf for DeterministicAtomic translates
46 // directly to more states explored and tested
47 #define FOLLY_TEST_DSCHED_VLOG(...) \
50 VLOG(2) << std::hex << std::this_thread::get_id() << ": " \
55 /* signatures of user-defined auxiliary functions */
56 using AuxAct = std::function<void(bool)>;
57 using AuxChk = std::function<void(uint64_t)>;
60 * DeterministicSchedule coordinates the inter-thread communication of a
61 * set of threads under test, so that despite concurrency the execution is
62 * the same every time. It works by stashing a reference to the schedule
63 * in a thread-local variable, then blocking all but one thread at a time.
65 * In order for DeterministicSchedule to work, it needs to intercept
66 * all inter-thread communication. To do this you should use
67 * DeterministicAtomic<T> instead of std::atomic<T>, create threads
68 * using DeterministicSchedule::thread() instead of the std::thread
69 * constructor, DeterministicSchedule::join(thr) instead of thr.join(),
70 * and access semaphores via the helper functions in DeterministicSchedule.
71 * Locks are not yet supported, although they would be easy to add with
72 * the same strategy as the mapping of sem_wait.
74 * The actual schedule is defined by a function from n -> [0,n). At
75 * each step, the function will be given the number of active threads
76 * (n), and it returns the index of the thread that should be run next.
77 * Invocations of the scheduler function will be serialized, but will
78 * occur from multiple threads. A good starting schedule is uniform(0).
80 class DeterministicSchedule : boost::noncopyable {
83 * Arranges for the current thread (and all threads created by
84 * DeterministicSchedule::thread on a thread participating in this
85 * schedule) to participate in a deterministic schedule.
87 explicit DeterministicSchedule(
88 const std::function<size_t(size_t)>& scheduler);
90 /** Completes the schedule. */
91 ~DeterministicSchedule();
94 * Returns a scheduling function that randomly chooses one of the
95 * runnable threads at each step, with no history. This implements
96 * a schedule that is equivalent to one in which the steps between
97 * inter-thread communication are random variables following a poisson
100 static std::function<size_t(size_t)> uniform(uint64_t seed);
103 * Returns a scheduling function that chooses a subset of the active
104 * threads and randomly chooses a member of the subset as the next
105 * runnable thread. The subset is chosen with size n, and the choice
106 * is made every m steps.
108 static std::function<size_t(size_t)>
109 uniformSubset(uint64_t seed, size_t n = 2, size_t m = 64);
111 /** Obtains permission for the current thread to perform inter-thread
113 static void beforeSharedAccess();
115 /** Releases permission for the current thread to perform inter-thread
117 static void afterSharedAccess();
119 /** Calls a user-defined auxiliary function if any, and releases
120 * permission for the current thread to perform inter-thread
121 * communication. The bool parameter indicates the success of the
122 * shared access (if conditional, true otherwise). */
123 static void afterSharedAccess(bool success);
125 /** Launches a thread that will participate in the same deterministic
126 * schedule as the current thread. */
127 template <typename Func, typename... Args>
128 static inline std::thread thread(Func&& func, Args&&... args) {
129 // TODO: maybe future versions of gcc will allow forwarding to thread
130 auto sched = tls_sched;
131 auto sem = sched ? sched->beforeThreadCreate() : nullptr;
132 auto child = std::thread([=](Args... a) {
134 sched->afterThreadCreate(sem);
135 beforeSharedAccess();
136 FOLLY_TEST_DSCHED_VLOG("running");
141 sched->beforeThreadExit();
147 beforeSharedAccess();
148 sched->active_.insert(child.get_id());
149 FOLLY_TEST_DSCHED_VLOG("forked " << std::hex << child.get_id());
155 /** Calls child.join() as part of a deterministic schedule. */
156 static void join(std::thread& child);
158 /** Calls sem_post(sem) as part of a deterministic schedule. */
159 static void post(sem_t* sem);
161 /** Calls sem_trywait(sem) as part of a deterministic schedule, returning
162 * true on success and false on transient failure. */
163 static bool tryWait(sem_t* sem);
165 /** Calls sem_wait(sem) as part of a deterministic schedule. */
166 static void wait(sem_t* sem);
168 /** Used scheduler_ to get a random number b/w [0, n). If tls_sched is
169 * not set-up it falls back to std::rand() */
170 static size_t getRandNumber(size_t n);
172 /** Deterministic implemencation of getcpu */
173 static int getcpu(unsigned* cpu, unsigned* node, void* unused);
175 /** Sets up a thread-specific function for call immediately after
176 * the next shared access by the thread for managing auxiliary
177 * data. The function takes a bool parameter that indicates the
178 * success of the shared access (if it is conditional, true
179 * otherwise). The function is cleared after one use. */
180 static void setAuxAct(AuxAct& aux);
182 /** Sets up a function to be called after every subsequent shared
183 * access (until clearAuxChk() is called) for checking global
184 * invariants and logging. The function takes a uint64_t parameter
185 * that indicates the number of shared accesses so far. */
186 static void setAuxChk(AuxChk& aux);
188 /** Clears the function set by setAuxChk */
189 static void clearAuxChk();
192 static FOLLY_TLS sem_t* tls_sem;
193 static FOLLY_TLS DeterministicSchedule* tls_sched;
194 static FOLLY_TLS unsigned tls_threadId;
195 static thread_local AuxAct tls_aux_act;
196 static AuxChk aux_chk;
198 std::function<size_t(size_t)> scheduler_;
199 std::vector<sem_t*> sems_;
200 std::unordered_set<std::thread::id> active_;
201 unsigned nextThreadId_;
202 /* step_ keeps count of shared accesses that correspond to user
203 * synchronization steps (atomic accesses for now).
204 * The reason for keeping track of this here and not just with
205 * auxiliary data is to provide users with warning signs (e.g.,
206 * skipped steps) if they inadvertently forget to set up aux
207 * functions for some shared accesses. */
210 sem_t* beforeThreadCreate();
211 void afterThreadCreate(sem_t*);
212 void beforeThreadExit();
213 /** Calls user-defined auxiliary function (if any) */
218 * DeterministicAtomic<T> is a drop-in replacement std::atomic<T> that
219 * cooperates with DeterministicSchedule.
221 template <typename T>
222 struct DeterministicAtomic {
225 DeterministicAtomic() = default;
226 ~DeterministicAtomic() = default;
227 DeterministicAtomic(DeterministicAtomic<T> const&) = delete;
228 DeterministicAtomic<T>& operator=(DeterministicAtomic<T> const&) = delete;
230 constexpr /* implicit */ DeterministicAtomic(T v) noexcept : data(v) {}
232 bool is_lock_free() const noexcept { return data.is_lock_free(); }
234 bool compare_exchange_strong(
237 std::memory_order mo = std::memory_order_seq_cst) noexcept {
238 return compare_exchange_strong(
239 v0, v1, mo, detail::default_failure_memory_order(mo));
241 bool compare_exchange_strong(
244 std::memory_order success,
245 std::memory_order failure) noexcept {
246 DeterministicSchedule::beforeSharedAccess();
248 bool rv = data.compare_exchange_strong(v0, v1, success, failure);
249 FOLLY_TEST_DSCHED_VLOG(this << ".compare_exchange_strong(" << std::hex
250 << orig << ", " << std::hex << v1 << ") -> "
251 << rv << "," << std::hex << v0);
252 DeterministicSchedule::afterSharedAccess(rv);
256 bool compare_exchange_weak(
259 std::memory_order mo = std::memory_order_seq_cst) noexcept {
260 return compare_exchange_weak(
261 v0, v1, mo, detail::default_failure_memory_order(mo));
263 bool compare_exchange_weak(
266 std::memory_order success,
267 std::memory_order failure) noexcept {
268 DeterministicSchedule::beforeSharedAccess();
270 bool rv = data.compare_exchange_weak(v0, v1, success, failure);
271 FOLLY_TEST_DSCHED_VLOG(this << ".compare_exchange_weak(" << std::hex << orig
272 << ", " << std::hex << v1 << ") -> " << rv
273 << "," << std::hex << v0);
274 DeterministicSchedule::afterSharedAccess(rv);
278 T exchange(T v, std::memory_order mo = std::memory_order_seq_cst) noexcept {
279 DeterministicSchedule::beforeSharedAccess();
280 T rv = data.exchange(v, mo);
281 FOLLY_TEST_DSCHED_VLOG(this << ".exchange(" << std::hex << v << ") -> "
283 DeterministicSchedule::afterSharedAccess(true);
287 /* implicit */ operator T() const noexcept {
288 DeterministicSchedule::beforeSharedAccess();
290 FOLLY_TEST_DSCHED_VLOG(this << "() -> " << std::hex << rv);
291 DeterministicSchedule::afterSharedAccess(true);
295 T load(std::memory_order mo = std::memory_order_seq_cst) const noexcept {
296 DeterministicSchedule::beforeSharedAccess();
297 T rv = data.load(mo);
298 FOLLY_TEST_DSCHED_VLOG(this << ".load() -> " << std::hex << rv);
299 DeterministicSchedule::afterSharedAccess(true);
303 T operator=(T v) noexcept {
304 DeterministicSchedule::beforeSharedAccess();
306 FOLLY_TEST_DSCHED_VLOG(this << " = " << std::hex << v);
307 DeterministicSchedule::afterSharedAccess(true);
311 void store(T v, std::memory_order mo = std::memory_order_seq_cst) noexcept {
312 DeterministicSchedule::beforeSharedAccess();
314 FOLLY_TEST_DSCHED_VLOG(this << ".store(" << std::hex << v << ")");
315 DeterministicSchedule::afterSharedAccess(true);
318 T operator++() noexcept {
319 DeterministicSchedule::beforeSharedAccess();
321 FOLLY_TEST_DSCHED_VLOG(this << " pre++ -> " << std::hex << rv);
322 DeterministicSchedule::afterSharedAccess(true);
326 T operator++(int /* postDummy */) noexcept {
327 DeterministicSchedule::beforeSharedAccess();
329 FOLLY_TEST_DSCHED_VLOG(this << " post++ -> " << std::hex << rv);
330 DeterministicSchedule::afterSharedAccess(true);
334 T operator--() noexcept {
335 DeterministicSchedule::beforeSharedAccess();
337 FOLLY_TEST_DSCHED_VLOG(this << " pre-- -> " << std::hex << rv);
338 DeterministicSchedule::afterSharedAccess(true);
342 T operator--(int /* postDummy */) noexcept {
343 DeterministicSchedule::beforeSharedAccess();
345 FOLLY_TEST_DSCHED_VLOG(this << " post-- -> " << std::hex << rv);
346 DeterministicSchedule::afterSharedAccess(true);
350 T operator+=(T v) noexcept {
351 DeterministicSchedule::beforeSharedAccess();
353 FOLLY_TEST_DSCHED_VLOG(this << " += " << std::hex << v << " -> " << std::hex
355 DeterministicSchedule::afterSharedAccess(true);
360 std::memory_order /* mo */ = std::memory_order_seq_cst) noexcept {
361 DeterministicSchedule::beforeSharedAccess();
364 FOLLY_TEST_DSCHED_VLOG(this << ".fetch_add(" << std::hex << v << ") -> "
366 DeterministicSchedule::afterSharedAccess(true);
370 T operator-=(T v) noexcept {
371 DeterministicSchedule::beforeSharedAccess();
373 FOLLY_TEST_DSCHED_VLOG(this << " -= " << std::hex << v << " -> " << std::hex
375 DeterministicSchedule::afterSharedAccess(true);
380 std::memory_order /* mo */ = std::memory_order_seq_cst) noexcept {
381 DeterministicSchedule::beforeSharedAccess();
384 FOLLY_TEST_DSCHED_VLOG(this << ".fetch_sub(" << std::hex << v << ") -> "
386 DeterministicSchedule::afterSharedAccess(true);
390 T operator&=(T v) noexcept {
391 DeterministicSchedule::beforeSharedAccess();
393 FOLLY_TEST_DSCHED_VLOG(this << " &= " << std::hex << v << " -> " << std::hex
395 DeterministicSchedule::afterSharedAccess(true);
400 std::memory_order /* mo */ = std::memory_order_seq_cst) noexcept {
401 DeterministicSchedule::beforeSharedAccess();
404 FOLLY_TEST_DSCHED_VLOG(this << ".fetch_and(" << std::hex << v << ") -> "
406 DeterministicSchedule::afterSharedAccess(true);
410 T operator|=(T v) noexcept {
411 DeterministicSchedule::beforeSharedAccess();
413 FOLLY_TEST_DSCHED_VLOG(this << " |= " << std::hex << v << " -> " << std::hex
415 DeterministicSchedule::afterSharedAccess(true);
420 std::memory_order /* mo */ = std::memory_order_seq_cst) noexcept {
421 DeterministicSchedule::beforeSharedAccess();
424 FOLLY_TEST_DSCHED_VLOG(this << ".fetch_or(" << std::hex << v << ") -> "
426 DeterministicSchedule::afterSharedAccess(true);
430 T operator^=(T v) noexcept {
431 DeterministicSchedule::beforeSharedAccess();
433 FOLLY_TEST_DSCHED_VLOG(this << " ^= " << std::hex << v << " -> " << std::hex
435 DeterministicSchedule::afterSharedAccess(true);
440 std::memory_order /* mo */ = std::memory_order_seq_cst) noexcept {
441 DeterministicSchedule::beforeSharedAccess();
444 FOLLY_TEST_DSCHED_VLOG(this << ".fetch_xor(" << std::hex << v << ") -> "
446 DeterministicSchedule::afterSharedAccess(true);
450 /** Read the value of the atomic variable without context switching */
451 T load_direct() const noexcept {
452 return data.load(std::memory_order_relaxed);
457 * DeterministicMutex is a drop-in replacement of std::mutex that
458 * cooperates with DeterministicSchedule.
460 struct DeterministicMutex {
463 DeterministicMutex() = default;
464 ~DeterministicMutex() = default;
465 DeterministicMutex(DeterministicMutex const&) = delete;
466 DeterministicMutex& operator=(DeterministicMutex const&) = delete;
469 FOLLY_TEST_DSCHED_VLOG(this << ".lock()");
470 while (!try_lock()) {
471 // Not calling m.lock() in order to avoid deadlock when the
472 // mutex m is held by another thread. The deadlock would be
473 // between the call to m.lock() and the lock holder's wait on
474 // its own tls_sem scheduling semaphore.
479 DeterministicSchedule::beforeSharedAccess();
480 bool rv = m.try_lock();
481 FOLLY_TEST_DSCHED_VLOG(this << ".try_lock() -> " << rv);
482 DeterministicSchedule::afterSharedAccess();
487 FOLLY_TEST_DSCHED_VLOG(this << ".unlock()");
492 } // namespace folly::test
494 /* Specialization declarations */
500 int Futex<test::DeterministicAtomic>::futexWake(int count, uint32_t wakeMask);
503 FutexResult Futex<test::DeterministicAtomic>::futexWaitImpl(
505 std::chrono::time_point<std::chrono::system_clock>* absSystemTime,
506 std::chrono::time_point<std::chrono::steady_clock>* absSteadyTime,
510 Getcpu::Func AccessSpreader<test::DeterministicAtomic>::pickGetcpuFunc();
512 } // namespace folly::detail