2 * Copyright 2014 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>
29 #include <folly/ScopeGuard.h>
30 #include <folly/detail/CacheLocality.h>
31 #include <folly/detail/Futex.h>
33 namespace folly { namespace test {
36 * DeterministicSchedule coordinates the inter-thread communication of a
37 * set of threads under test, so that despite concurrency the execution is
38 * the same every time. It works by stashing a reference to the schedule
39 * in a thread-local variable, then blocking all but one thread at a time.
41 * In order for DeterministicSchedule to work, it needs to intercept
42 * all inter-thread communication. To do this you should use
43 * DeterministicAtomic<T> instead of std::atomic<T>, create threads
44 * using DeterministicSchedule::thread() instead of the std::thread
45 * constructor, DeterministicSchedule::join(thr) instead of thr.join(),
46 * and access semaphores via the helper functions in DeterministicSchedule.
47 * Locks are not yet supported, although they would be easy to add with
48 * the same strategy as the mapping of sem_wait.
50 * The actual schedule is defined by a function from n -> [0,n). At
51 * each step, the function will be given the number of active threads
52 * (n), and it returns the index of the thread that should be run next.
53 * Invocations of the scheduler function will be serialized, but will
54 * occur from multiple threads. A good starting schedule is uniform(0).
56 class DeterministicSchedule : boost::noncopyable {
59 * Arranges for the current thread (and all threads created by
60 * DeterministicSchedule::thread on a thread participating in this
61 * schedule) to participate in a deterministic schedule.
63 explicit DeterministicSchedule(const std::function<int(int)>& scheduler);
65 /** Completes the schedule. */
66 ~DeterministicSchedule();
69 * Returns a scheduling function that randomly chooses one of the
70 * runnable threads at each step, with no history. This implements
71 * a schedule that is equivalent to one in which the steps between
72 * inter-thread communication are random variables following a poisson
75 static std::function<int(int)> uniform(long seed);
78 * Returns a scheduling function that chooses a subset of the active
79 * threads and randomly chooses a member of the subset as the next
80 * runnable thread. The subset is chosen with size n, and the choice
81 * is made every m steps.
83 static std::function<int(int)> uniformSubset(long seed, int n = 2,
86 /** Obtains permission for the current thread to perform inter-thread
88 static void beforeSharedAccess();
90 /** Releases permission for the current thread to perform inter-thread
92 static void afterSharedAccess();
94 /** Launches a thread that will participate in the same deterministic
95 * schedule as the current thread. */
96 template <typename Func, typename... Args>
97 static inline std::thread thread(Func&& func, Args&&... args) {
98 // TODO: maybe future versions of gcc will allow forwarding to thread
99 auto sched = tls_sched;
100 auto sem = sched ? sched->beforeThreadCreate() : nullptr;
101 auto child = std::thread([=](Args... a) {
102 if (sched) sched->afterThreadCreate(sem);
103 SCOPE_EXIT { if (sched) sched->beforeThreadExit(); };
107 beforeSharedAccess();
108 sched->active_.insert(child.get_id());
114 /** Calls child.join() as part of a deterministic schedule. */
115 static void join(std::thread& child);
117 /** Calls sem_post(sem) as part of a deterministic schedule. */
118 static void post(sem_t* sem);
120 /** Calls sem_trywait(sem) as part of a deterministic schedule, returning
121 * true on success and false on transient failure. */
122 static bool tryWait(sem_t* sem);
124 /** Calls sem_wait(sem) as part of a deterministic schedule. */
125 static void wait(sem_t* sem);
127 /** Used scheduler_ to get a random number b/w [0, n). If tls_sched is
128 * not set-up it falls back to std::rand() */
129 static int getRandNumber(int n);
132 static FOLLY_TLS sem_t* tls_sem;
133 static FOLLY_TLS DeterministicSchedule* tls_sched;
135 std::function<int(int)> scheduler_;
136 std::vector<sem_t*> sems_;
137 std::unordered_set<std::thread::id> active_;
139 sem_t* beforeThreadCreate();
140 void afterThreadCreate(sem_t*);
141 void beforeThreadExit();
146 * DeterministicAtomic<T> is a drop-in replacement std::atomic<T> that
147 * cooperates with DeterministicSchedule.
149 template <typename T>
150 struct DeterministicAtomic {
153 DeterministicAtomic() = default;
154 ~DeterministicAtomic() = default;
155 DeterministicAtomic(DeterministicAtomic<T> const &) = delete;
156 DeterministicAtomic<T>& operator= (DeterministicAtomic<T> const &) = delete;
158 constexpr /* implicit */ DeterministicAtomic(T v) noexcept : data(v) {}
160 bool is_lock_free() const noexcept {
161 return data.is_lock_free();
164 bool compare_exchange_strong(
166 std::memory_order mo = std::memory_order_seq_cst) noexcept {
167 DeterministicSchedule::beforeSharedAccess();
168 bool rv = data.compare_exchange_strong(v0, v1, mo);
169 DeterministicSchedule::afterSharedAccess();
173 bool compare_exchange_weak(
175 std::memory_order mo = std::memory_order_seq_cst) noexcept {
176 DeterministicSchedule::beforeSharedAccess();
177 bool rv = data.compare_exchange_weak(v0, v1, mo);
178 DeterministicSchedule::afterSharedAccess();
182 T exchange(T v, std::memory_order mo = std::memory_order_seq_cst) noexcept {
183 DeterministicSchedule::beforeSharedAccess();
184 T rv = data.exchange(v, mo);
185 DeterministicSchedule::afterSharedAccess();
189 /* implicit */ operator T () const noexcept {
190 DeterministicSchedule::beforeSharedAccess();
192 DeterministicSchedule::afterSharedAccess();
196 T load(std::memory_order mo = std::memory_order_seq_cst) const noexcept {
197 DeterministicSchedule::beforeSharedAccess();
198 T rv = data.load(mo);
199 DeterministicSchedule::afterSharedAccess();
203 T operator= (T v) noexcept {
204 DeterministicSchedule::beforeSharedAccess();
206 DeterministicSchedule::afterSharedAccess();
210 void store(T v, std::memory_order mo = std::memory_order_seq_cst) noexcept {
211 DeterministicSchedule::beforeSharedAccess();
213 DeterministicSchedule::afterSharedAccess();
216 T operator++ () noexcept {
217 DeterministicSchedule::beforeSharedAccess();
219 DeterministicSchedule::afterSharedAccess();
223 T operator++ (int postDummy) noexcept {
224 DeterministicSchedule::beforeSharedAccess();
226 DeterministicSchedule::afterSharedAccess();
230 T operator-- () noexcept {
231 DeterministicSchedule::beforeSharedAccess();
233 DeterministicSchedule::afterSharedAccess();
237 T operator-- (int postDummy) noexcept {
238 DeterministicSchedule::beforeSharedAccess();
240 DeterministicSchedule::afterSharedAccess();
244 T operator+= (T v) noexcept {
245 DeterministicSchedule::beforeSharedAccess();
247 DeterministicSchedule::afterSharedAccess();
251 T operator-= (T v) noexcept {
252 DeterministicSchedule::beforeSharedAccess();
254 DeterministicSchedule::afterSharedAccess();
258 T operator&= (T v) noexcept {
259 DeterministicSchedule::beforeSharedAccess();
261 DeterministicSchedule::afterSharedAccess();
265 T operator|= (T v) noexcept {
266 DeterministicSchedule::beforeSharedAccess();
268 DeterministicSchedule::afterSharedAccess();
275 namespace folly { namespace detail {
278 bool Futex<test::DeterministicAtomic>::futexWait(uint32_t expected,
281 /// This function ignores the time bound, and instead pseudo-randomly chooses
282 /// whether the timeout was reached. To do otherwise would not be deterministic.
283 FutexResult futexWaitUntilImpl(Futex<test::DeterministicAtomic> *futex,
284 uint32_t expected, uint32_t waitMask);
286 template<> template<class Clock, class Duration>
288 Futex<test::DeterministicAtomic>::futexWaitUntil(
290 const time_point<Clock, Duration>& absTimeUnused,
292 return futexWaitUntilImpl(this, expected, waitMask);
296 int Futex<test::DeterministicAtomic>::futexWake(int count, uint32_t wakeMask);