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.
20 #include <boost/noncopyable.hpp>
22 #include <glog/logging.h>
27 #include <unordered_set>
30 #include <folly/ScopeGuard.h>
31 #include <folly/concurrency/CacheLocality.h>
32 #include <folly/detail/AtomicUtils.h>
33 #include <folly/detail/Futex.h>
34 #include <folly/portability/Semaphore.h>
39 // This is ugly, but better perf for DeterministicAtomic translates
40 // directly to more states explored and tested
41 #define FOLLY_TEST_DSCHED_VLOG(...) \
44 VLOG(2) << std::hex << std::this_thread::get_id() << ": " \
49 /* signatures of user-defined auxiliary functions */
50 using AuxAct = std::function<void(bool)>;
51 using AuxChk = std::function<void(uint64_t)>;
54 * DeterministicSchedule coordinates the inter-thread communication of a
55 * set of threads under test, so that despite concurrency the execution is
56 * the same every time. It works by stashing a reference to the schedule
57 * in a thread-local variable, then blocking all but one thread at a time.
59 * In order for DeterministicSchedule to work, it needs to intercept
60 * all inter-thread communication. To do this you should use
61 * DeterministicAtomic<T> instead of std::atomic<T>, create threads
62 * using DeterministicSchedule::thread() instead of the std::thread
63 * constructor, DeterministicSchedule::join(thr) instead of thr.join(),
64 * and access semaphores via the helper functions in DeterministicSchedule.
65 * Locks are not yet supported, although they would be easy to add with
66 * the same strategy as the mapping of sem_wait.
68 * The actual schedule is defined by a function from n -> [0,n). At
69 * each step, the function will be given the number of active threads
70 * (n), and it returns the index of the thread that should be run next.
71 * Invocations of the scheduler function will be serialized, but will
72 * occur from multiple threads. A good starting schedule is uniform(0).
74 class DeterministicSchedule : boost::noncopyable {
77 * Arranges for the current thread (and all threads created by
78 * DeterministicSchedule::thread on a thread participating in this
79 * schedule) to participate in a deterministic schedule.
81 explicit DeterministicSchedule(
82 const std::function<size_t(size_t)>& scheduler);
84 /** Completes the schedule. */
85 ~DeterministicSchedule();
88 * Returns a scheduling function that randomly chooses one of the
89 * runnable threads at each step, with no history. This implements
90 * a schedule that is equivalent to one in which the steps between
91 * inter-thread communication are random variables following a poisson
94 static std::function<size_t(size_t)> uniform(uint64_t seed);
97 * Returns a scheduling function that chooses a subset of the active
98 * threads and randomly chooses a member of the subset as the next
99 * runnable thread. The subset is chosen with size n, and the choice
100 * is made every m steps.
102 static std::function<size_t(size_t)>
103 uniformSubset(uint64_t seed, size_t n = 2, size_t m = 64);
105 /** Obtains permission for the current thread to perform inter-thread
107 static void beforeSharedAccess();
109 /** Releases permission for the current thread to perform inter-thread
111 static void afterSharedAccess();
113 /** Calls a user-defined auxiliary function if any, and releases
114 * permission for the current thread to perform inter-thread
115 * communication. The bool parameter indicates the success of the
116 * shared access (if conditional, true otherwise). */
117 static void afterSharedAccess(bool success);
119 /** Launches a thread that will participate in the same deterministic
120 * schedule as the current thread. */
121 template <typename Func, typename... Args>
122 static inline std::thread thread(Func&& func, Args&&... args) {
123 // TODO: maybe future versions of gcc will allow forwarding to thread
124 auto sched = tls_sched;
125 auto sem = sched ? sched->beforeThreadCreate() : nullptr;
126 auto child = std::thread([=](Args... a) {
128 sched->afterThreadCreate(sem);
129 beforeSharedAccess();
130 FOLLY_TEST_DSCHED_VLOG("running");
135 sched->beforeThreadExit();
141 beforeSharedAccess();
142 sched->active_.insert(child.get_id());
143 FOLLY_TEST_DSCHED_VLOG("forked " << std::hex << child.get_id());
149 /** Calls child.join() as part of a deterministic schedule. */
150 static void join(std::thread& child);
152 /** Calls sem_post(sem) as part of a deterministic schedule. */
153 static void post(sem_t* sem);
155 /** Calls sem_trywait(sem) as part of a deterministic schedule, returning
156 * true on success and false on transient failure. */
157 static bool tryWait(sem_t* sem);
159 /** Calls sem_wait(sem) as part of a deterministic schedule. */
160 static void wait(sem_t* sem);
162 /** Used scheduler_ to get a random number b/w [0, n). If tls_sched is
163 * not set-up it falls back to std::rand() */
164 static size_t getRandNumber(size_t n);
166 /** Deterministic implemencation of getcpu */
167 static int getcpu(unsigned* cpu, unsigned* node, void* unused);
169 /** Sets up a thread-specific function for call immediately after
170 * the next shared access by the thread for managing auxiliary
171 * data. The function takes a bool parameter that indicates the
172 * success of the shared access (if it is conditional, true
173 * otherwise). The function is cleared after one use. */
174 static void setAuxAct(AuxAct& aux);
176 /** Sets up a function to be called after every subsequent shared
177 * access (until clearAuxChk() is called) for checking global
178 * invariants and logging. The function takes a uint64_t parameter
179 * that indicates the number of shared accesses so far. */
180 static void setAuxChk(AuxChk& aux);
182 /** Clears the function set by setAuxChk */
183 static void clearAuxChk();
186 static FOLLY_TLS sem_t* tls_sem;
187 static FOLLY_TLS DeterministicSchedule* tls_sched;
188 static FOLLY_TLS unsigned tls_threadId;
189 static thread_local AuxAct tls_aux_act;
190 static AuxChk aux_chk;
192 std::function<size_t(size_t)> scheduler_;
193 std::vector<sem_t*> sems_;
194 std::unordered_set<std::thread::id> active_;
195 unsigned nextThreadId_;
196 /* step_ keeps count of shared accesses that correspond to user
197 * synchronization steps (atomic accesses for now).
198 * The reason for keeping track of this here and not just with
199 * auxiliary data is to provide users with warning signs (e.g.,
200 * skipped steps) if they inadvertently forget to set up aux
201 * functions for some shared accesses. */
204 sem_t* beforeThreadCreate();
205 void afterThreadCreate(sem_t*);
206 void beforeThreadExit();
207 /** Calls user-defined auxiliary function (if any) */
212 * DeterministicAtomic<T> is a drop-in replacement std::atomic<T> that
213 * cooperates with DeterministicSchedule.
215 template <typename T>
216 struct DeterministicAtomic {
219 DeterministicAtomic() = default;
220 ~DeterministicAtomic() = default;
221 DeterministicAtomic(DeterministicAtomic<T> const&) = delete;
222 DeterministicAtomic<T>& operator=(DeterministicAtomic<T> const&) = delete;
224 constexpr /* implicit */ DeterministicAtomic(T v) noexcept : data(v) {}
226 bool is_lock_free() const noexcept { return data.is_lock_free(); }
228 bool compare_exchange_strong(
231 std::memory_order mo = std::memory_order_seq_cst) noexcept {
232 return compare_exchange_strong(
233 v0, v1, mo, detail::default_failure_memory_order(mo));
235 bool compare_exchange_strong(
238 std::memory_order success,
239 std::memory_order failure) noexcept {
240 DeterministicSchedule::beforeSharedAccess();
242 bool rv = data.compare_exchange_strong(v0, v1, success, failure);
243 FOLLY_TEST_DSCHED_VLOG(this << ".compare_exchange_strong(" << std::hex
244 << orig << ", " << std::hex << v1 << ") -> "
245 << rv << "," << std::hex << v0);
246 DeterministicSchedule::afterSharedAccess(rv);
250 bool compare_exchange_weak(
253 std::memory_order mo = std::memory_order_seq_cst) noexcept {
254 return compare_exchange_weak(
255 v0, v1, mo, detail::default_failure_memory_order(mo));
257 bool compare_exchange_weak(
260 std::memory_order success,
261 std::memory_order failure) noexcept {
262 DeterministicSchedule::beforeSharedAccess();
264 bool rv = data.compare_exchange_weak(v0, v1, success, failure);
265 FOLLY_TEST_DSCHED_VLOG(this << ".compare_exchange_weak(" << std::hex << orig
266 << ", " << std::hex << v1 << ") -> " << rv
267 << "," << std::hex << v0);
268 DeterministicSchedule::afterSharedAccess(rv);
272 T exchange(T v, std::memory_order mo = std::memory_order_seq_cst) noexcept {
273 DeterministicSchedule::beforeSharedAccess();
274 T rv = data.exchange(v, mo);
275 FOLLY_TEST_DSCHED_VLOG(this << ".exchange(" << std::hex << v << ") -> "
277 DeterministicSchedule::afterSharedAccess(true);
281 /* implicit */ operator T() const noexcept {
282 DeterministicSchedule::beforeSharedAccess();
284 FOLLY_TEST_DSCHED_VLOG(this << "() -> " << std::hex << rv);
285 DeterministicSchedule::afterSharedAccess(true);
289 T load(std::memory_order mo = std::memory_order_seq_cst) const noexcept {
290 DeterministicSchedule::beforeSharedAccess();
291 T rv = data.load(mo);
292 FOLLY_TEST_DSCHED_VLOG(this << ".load() -> " << std::hex << rv);
293 DeterministicSchedule::afterSharedAccess(true);
297 T operator=(T v) noexcept {
298 DeterministicSchedule::beforeSharedAccess();
300 FOLLY_TEST_DSCHED_VLOG(this << " = " << std::hex << v);
301 DeterministicSchedule::afterSharedAccess(true);
305 void store(T v, std::memory_order mo = std::memory_order_seq_cst) noexcept {
306 DeterministicSchedule::beforeSharedAccess();
308 FOLLY_TEST_DSCHED_VLOG(this << ".store(" << std::hex << v << ")");
309 DeterministicSchedule::afterSharedAccess(true);
312 T operator++() noexcept {
313 DeterministicSchedule::beforeSharedAccess();
315 FOLLY_TEST_DSCHED_VLOG(this << " pre++ -> " << std::hex << rv);
316 DeterministicSchedule::afterSharedAccess(true);
320 T operator++(int /* postDummy */) noexcept {
321 DeterministicSchedule::beforeSharedAccess();
323 FOLLY_TEST_DSCHED_VLOG(this << " post++ -> " << std::hex << rv);
324 DeterministicSchedule::afterSharedAccess(true);
328 T operator--() noexcept {
329 DeterministicSchedule::beforeSharedAccess();
331 FOLLY_TEST_DSCHED_VLOG(this << " pre-- -> " << std::hex << rv);
332 DeterministicSchedule::afterSharedAccess(true);
336 T operator--(int /* postDummy */) noexcept {
337 DeterministicSchedule::beforeSharedAccess();
339 FOLLY_TEST_DSCHED_VLOG(this << " post-- -> " << std::hex << rv);
340 DeterministicSchedule::afterSharedAccess(true);
344 T operator+=(T v) noexcept {
345 DeterministicSchedule::beforeSharedAccess();
347 FOLLY_TEST_DSCHED_VLOG(this << " += " << std::hex << v << " -> " << std::hex
349 DeterministicSchedule::afterSharedAccess(true);
354 std::memory_order /* mo */ = std::memory_order_seq_cst) noexcept {
355 DeterministicSchedule::beforeSharedAccess();
358 FOLLY_TEST_DSCHED_VLOG(this << ".fetch_add(" << std::hex << v << ") -> "
360 DeterministicSchedule::afterSharedAccess(true);
364 T operator-=(T v) noexcept {
365 DeterministicSchedule::beforeSharedAccess();
367 FOLLY_TEST_DSCHED_VLOG(this << " -= " << std::hex << v << " -> " << std::hex
369 DeterministicSchedule::afterSharedAccess(true);
374 std::memory_order /* mo */ = std::memory_order_seq_cst) noexcept {
375 DeterministicSchedule::beforeSharedAccess();
378 FOLLY_TEST_DSCHED_VLOG(this << ".fetch_sub(" << std::hex << v << ") -> "
380 DeterministicSchedule::afterSharedAccess(true);
384 T operator&=(T v) noexcept {
385 DeterministicSchedule::beforeSharedAccess();
387 FOLLY_TEST_DSCHED_VLOG(this << " &= " << std::hex << v << " -> " << std::hex
389 DeterministicSchedule::afterSharedAccess(true);
394 std::memory_order /* mo */ = std::memory_order_seq_cst) noexcept {
395 DeterministicSchedule::beforeSharedAccess();
398 FOLLY_TEST_DSCHED_VLOG(this << ".fetch_and(" << std::hex << v << ") -> "
400 DeterministicSchedule::afterSharedAccess(true);
404 T operator|=(T v) noexcept {
405 DeterministicSchedule::beforeSharedAccess();
407 FOLLY_TEST_DSCHED_VLOG(this << " |= " << std::hex << v << " -> " << std::hex
409 DeterministicSchedule::afterSharedAccess(true);
414 std::memory_order /* mo */ = std::memory_order_seq_cst) noexcept {
415 DeterministicSchedule::beforeSharedAccess();
418 FOLLY_TEST_DSCHED_VLOG(this << ".fetch_or(" << std::hex << v << ") -> "
420 DeterministicSchedule::afterSharedAccess(true);
424 T operator^=(T v) noexcept {
425 DeterministicSchedule::beforeSharedAccess();
427 FOLLY_TEST_DSCHED_VLOG(this << " ^= " << std::hex << v << " -> " << std::hex
429 DeterministicSchedule::afterSharedAccess(true);
434 std::memory_order /* mo */ = std::memory_order_seq_cst) noexcept {
435 DeterministicSchedule::beforeSharedAccess();
438 FOLLY_TEST_DSCHED_VLOG(this << ".fetch_xor(" << std::hex << v << ") -> "
440 DeterministicSchedule::afterSharedAccess(true);
444 /** Read the value of the atomic variable without context switching */
445 T load_direct() const noexcept {
446 return data.load(std::memory_order_relaxed);
451 * DeterministicMutex is a drop-in replacement of std::mutex that
452 * cooperates with DeterministicSchedule.
454 struct DeterministicMutex {
457 DeterministicMutex() = default;
458 ~DeterministicMutex() = default;
459 DeterministicMutex(DeterministicMutex const&) = delete;
460 DeterministicMutex& operator=(DeterministicMutex const&) = delete;
463 FOLLY_TEST_DSCHED_VLOG(this << ".lock()");
464 while (!try_lock()) {
465 // Not calling m.lock() in order to avoid deadlock when the
466 // mutex m is held by another thread. The deadlock would be
467 // between the call to m.lock() and the lock holder's wait on
468 // its own tls_sem scheduling semaphore.
473 DeterministicSchedule::beforeSharedAccess();
474 bool rv = m.try_lock();
475 FOLLY_TEST_DSCHED_VLOG(this << ".try_lock() -> " << rv);
476 DeterministicSchedule::afterSharedAccess();
481 FOLLY_TEST_DSCHED_VLOG(this << ".unlock()");
486 } // namespace folly::test
488 /* Specialization declarations */
494 int Futex<test::DeterministicAtomic>::futexWake(int count, uint32_t wakeMask);
497 FutexResult Futex<test::DeterministicAtomic>::futexWaitImpl(
499 std::chrono::time_point<std::chrono::system_clock>* absSystemTime,
500 std::chrono::time_point<std::chrono::steady_clock>* absSteadyTime,
505 Getcpu::Func AccessSpreader<test::DeterministicAtomic>::pickGetcpuFunc();
507 } // namespace folly::detail