2 * Copyright 2015 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.
22 #include <unordered_set>
24 #include <boost/noncopyable.hpp>
25 #include <semaphore.h>
28 #include <glog/logging.h>
30 #include <folly/ScopeGuard.h>
31 #include <folly/detail/CacheLocality.h>
32 #include <folly/detail/Futex.h>
37 // This is ugly, but better perf for DeterministicAtomic translates
38 // directly to more states explored and tested
39 #define FOLLY_TEST_DSCHED_VLOG(msg...) \
42 VLOG(2) << std::hex << std::this_thread::get_id() << ": " << msg; \
47 * DeterministicSchedule coordinates the inter-thread communication of a
48 * set of threads under test, so that despite concurrency the execution is
49 * the same every time. It works by stashing a reference to the schedule
50 * in a thread-local variable, then blocking all but one thread at a time.
52 * In order for DeterministicSchedule to work, it needs to intercept
53 * all inter-thread communication. To do this you should use
54 * DeterministicAtomic<T> instead of std::atomic<T>, create threads
55 * using DeterministicSchedule::thread() instead of the std::thread
56 * constructor, DeterministicSchedule::join(thr) instead of thr.join(),
57 * and access semaphores via the helper functions in DeterministicSchedule.
58 * Locks are not yet supported, although they would be easy to add with
59 * the same strategy as the mapping of sem_wait.
61 * The actual schedule is defined by a function from n -> [0,n). At
62 * each step, the function will be given the number of active threads
63 * (n), and it returns the index of the thread that should be run next.
64 * Invocations of the scheduler function will be serialized, but will
65 * occur from multiple threads. A good starting schedule is uniform(0).
67 class DeterministicSchedule : boost::noncopyable {
70 * Arranges for the current thread (and all threads created by
71 * DeterministicSchedule::thread on a thread participating in this
72 * schedule) to participate in a deterministic schedule.
74 explicit DeterministicSchedule(const std::function<int(int)>& scheduler);
76 /** Completes the schedule. */
77 ~DeterministicSchedule();
80 * Returns a scheduling function that randomly chooses one of the
81 * runnable threads at each step, with no history. This implements
82 * a schedule that is equivalent to one in which the steps between
83 * inter-thread communication are random variables following a poisson
86 static std::function<int(int)> uniform(long seed);
89 * Returns a scheduling function that chooses a subset of the active
90 * threads and randomly chooses a member of the subset as the next
91 * runnable thread. The subset is chosen with size n, and the choice
92 * is made every m steps.
94 static std::function<int(int)> uniformSubset(long seed,
98 /** Obtains permission for the current thread to perform inter-thread
100 static void beforeSharedAccess();
102 /** Releases permission for the current thread to perform inter-thread
104 static void afterSharedAccess();
106 /** Launches a thread that will participate in the same deterministic
107 * schedule as the current thread. */
108 template <typename Func, typename... Args>
109 static inline std::thread thread(Func&& func, Args&&... args) {
110 // TODO: maybe future versions of gcc will allow forwarding to thread
111 auto sched = tls_sched;
112 auto sem = sched ? sched->beforeThreadCreate() : nullptr;
113 auto child = std::thread([=](Args... a) {
115 sched->afterThreadCreate(sem);
116 beforeSharedAccess();
117 FOLLY_TEST_DSCHED_VLOG("running");
122 sched->beforeThreadExit();
128 beforeSharedAccess();
129 sched->active_.insert(child.get_id());
130 FOLLY_TEST_DSCHED_VLOG("forked " << std::hex << child.get_id());
136 /** Calls child.join() as part of a deterministic schedule. */
137 static void join(std::thread& child);
139 /** Calls sem_post(sem) as part of a deterministic schedule. */
140 static void post(sem_t* sem);
142 /** Calls sem_trywait(sem) as part of a deterministic schedule, returning
143 * true on success and false on transient failure. */
144 static bool tryWait(sem_t* sem);
146 /** Calls sem_wait(sem) as part of a deterministic schedule. */
147 static void wait(sem_t* sem);
149 /** Used scheduler_ to get a random number b/w [0, n). If tls_sched is
150 * not set-up it falls back to std::rand() */
151 static int getRandNumber(int n);
153 /** Deterministic implemencation of getcpu */
154 static int getcpu(unsigned* cpu, unsigned* node, void* unused);
157 static FOLLY_TLS sem_t* tls_sem;
158 static FOLLY_TLS DeterministicSchedule* tls_sched;
159 static FOLLY_TLS unsigned tls_threadId;
161 std::function<int(int)> scheduler_;
162 std::vector<sem_t*> sems_;
163 std::unordered_set<std::thread::id> active_;
164 unsigned nextThreadId_;
166 sem_t* beforeThreadCreate();
167 void afterThreadCreate(sem_t*);
168 void beforeThreadExit();
172 * DeterministicAtomic<T> is a drop-in replacement std::atomic<T> that
173 * cooperates with DeterministicSchedule.
175 template <typename T>
176 struct DeterministicAtomic {
179 DeterministicAtomic() = default;
180 ~DeterministicAtomic() = default;
181 DeterministicAtomic(DeterministicAtomic<T> const&) = delete;
182 DeterministicAtomic<T>& operator=(DeterministicAtomic<T> const&) = delete;
184 constexpr /* implicit */ DeterministicAtomic(T v) noexcept : data(v) {}
186 bool is_lock_free() const noexcept { return data.is_lock_free(); }
188 bool compare_exchange_strong(
189 T& v0, T v1, std::memory_order mo = std::memory_order_seq_cst) noexcept {
190 DeterministicSchedule::beforeSharedAccess();
192 bool rv = data.compare_exchange_strong(v0, v1, mo);
193 FOLLY_TEST_DSCHED_VLOG(this << ".compare_exchange_strong(" << std::hex
194 << orig << ", " << std::hex << v1 << ") -> "
195 << rv << "," << std::hex << v0);
196 DeterministicSchedule::afterSharedAccess();
200 bool compare_exchange_weak(
201 T& v0, T v1, std::memory_order mo = std::memory_order_seq_cst) noexcept {
202 DeterministicSchedule::beforeSharedAccess();
204 bool rv = data.compare_exchange_weak(v0, v1, mo);
205 FOLLY_TEST_DSCHED_VLOG(this << ".compare_exchange_weak(" << std::hex << orig
206 << ", " << std::hex << v1 << ") -> " << rv
207 << "," << std::hex << v0);
208 DeterministicSchedule::afterSharedAccess();
212 T exchange(T v, std::memory_order mo = std::memory_order_seq_cst) noexcept {
213 DeterministicSchedule::beforeSharedAccess();
214 T rv = data.exchange(v, mo);
215 FOLLY_TEST_DSCHED_VLOG(this << ".exchange(" << std::hex << v << ") -> "
217 DeterministicSchedule::afterSharedAccess();
221 /* implicit */ operator T() const noexcept {
222 DeterministicSchedule::beforeSharedAccess();
224 FOLLY_TEST_DSCHED_VLOG(this << "() -> " << std::hex << rv);
225 DeterministicSchedule::afterSharedAccess();
229 T load(std::memory_order mo = std::memory_order_seq_cst) const noexcept {
230 DeterministicSchedule::beforeSharedAccess();
231 T rv = data.load(mo);
232 FOLLY_TEST_DSCHED_VLOG(this << ".load() -> " << std::hex << rv);
233 DeterministicSchedule::afterSharedAccess();
237 T operator=(T v) noexcept {
238 DeterministicSchedule::beforeSharedAccess();
240 FOLLY_TEST_DSCHED_VLOG(this << " = " << std::hex << v);
241 DeterministicSchedule::afterSharedAccess();
245 void store(T v, std::memory_order mo = std::memory_order_seq_cst) noexcept {
246 DeterministicSchedule::beforeSharedAccess();
248 FOLLY_TEST_DSCHED_VLOG(this << ".store(" << std::hex << v << ")");
249 DeterministicSchedule::afterSharedAccess();
252 T operator++() noexcept {
253 DeterministicSchedule::beforeSharedAccess();
255 FOLLY_TEST_DSCHED_VLOG(this << " pre++ -> " << std::hex << rv);
256 DeterministicSchedule::afterSharedAccess();
260 T operator++(int postDummy) noexcept {
261 DeterministicSchedule::beforeSharedAccess();
263 FOLLY_TEST_DSCHED_VLOG(this << " post++ -> " << std::hex << rv);
264 DeterministicSchedule::afterSharedAccess();
268 T operator--() noexcept {
269 DeterministicSchedule::beforeSharedAccess();
271 FOLLY_TEST_DSCHED_VLOG(this << " pre-- -> " << std::hex << rv);
272 DeterministicSchedule::afterSharedAccess();
276 T operator--(int postDummy) noexcept {
277 DeterministicSchedule::beforeSharedAccess();
279 FOLLY_TEST_DSCHED_VLOG(this << " post-- -> " << std::hex << rv);
280 DeterministicSchedule::afterSharedAccess();
284 T operator+=(T v) noexcept {
285 DeterministicSchedule::beforeSharedAccess();
287 FOLLY_TEST_DSCHED_VLOG(this << " += " << std::hex << v << " -> " << std::hex
289 DeterministicSchedule::afterSharedAccess();
293 T fetch_add(T v, std::memory_order mo = std::memory_order_seq_cst) noexcept {
294 DeterministicSchedule::beforeSharedAccess();
297 FOLLY_TEST_DSCHED_VLOG(this << ".fetch_add(" << std::hex << v << ") -> "
299 DeterministicSchedule::afterSharedAccess();
303 T operator-=(T v) noexcept {
304 DeterministicSchedule::beforeSharedAccess();
306 FOLLY_TEST_DSCHED_VLOG(this << " -= " << std::hex << v << " -> " << std::hex
308 DeterministicSchedule::afterSharedAccess();
312 T fetch_sub(T v, std::memory_order mo = std::memory_order_seq_cst) noexcept {
313 DeterministicSchedule::beforeSharedAccess();
316 FOLLY_TEST_DSCHED_VLOG(this << ".fetch_sub(" << std::hex << v << ") -> "
318 DeterministicSchedule::afterSharedAccess();
322 T operator&=(T v) noexcept {
323 DeterministicSchedule::beforeSharedAccess();
325 FOLLY_TEST_DSCHED_VLOG(this << " &= " << std::hex << v << " -> " << std::hex
327 DeterministicSchedule::afterSharedAccess();
331 T fetch_and(T v, std::memory_order mo = std::memory_order_seq_cst) noexcept {
332 DeterministicSchedule::beforeSharedAccess();
335 FOLLY_TEST_DSCHED_VLOG(this << ".fetch_and(" << std::hex << v << ") -> "
337 DeterministicSchedule::afterSharedAccess();
341 T operator|=(T v) noexcept {
342 DeterministicSchedule::beforeSharedAccess();
344 FOLLY_TEST_DSCHED_VLOG(this << " |= " << std::hex << v << " -> " << std::hex
346 DeterministicSchedule::afterSharedAccess();
350 T fetch_or(T v, std::memory_order mo = std::memory_order_seq_cst) noexcept {
351 DeterministicSchedule::beforeSharedAccess();
354 FOLLY_TEST_DSCHED_VLOG(this << ".fetch_or(" << std::hex << v << ") -> "
356 DeterministicSchedule::afterSharedAccess();
360 T operator^=(T v) noexcept {
361 DeterministicSchedule::beforeSharedAccess();
363 FOLLY_TEST_DSCHED_VLOG(this << " ^= " << std::hex << v << " -> " << std::hex
365 DeterministicSchedule::afterSharedAccess();
369 T fetch_xor(T v, std::memory_order mo = std::memory_order_seq_cst) noexcept {
370 DeterministicSchedule::beforeSharedAccess();
373 FOLLY_TEST_DSCHED_VLOG(this << ".fetch_xor(" << std::hex << v << ") -> "
375 DeterministicSchedule::afterSharedAccess();
380 } // namespace folly::test
382 /* Specialization declarations */
388 int Futex<test::DeterministicAtomic>::futexWake(int count, uint32_t wakeMask);
391 FutexResult Futex<test::DeterministicAtomic>::futexWaitImpl(
393 std::chrono::time_point<std::chrono::system_clock>* absSystemTime,
394 std::chrono::time_point<std::chrono::steady_clock>* absSteadyTime,
398 Getcpu::Func AccessSpreader<test::DeterministicAtomic>::pickGetcpuFunc(
401 } // namespace folly::detail