1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 /*
3 * Copyright (c) 2017-2018 Richard Palethorpe <rpalethorpe@suse.com>
4 */
5 /**
6 * @file tst_fuzzy_sync.h
7 * Fuzzy Synchronisation - abbreviated to fzsync
8 *
9 * This library is intended to help reproduce race conditions by synchronising
10 * two threads at a given place by marking the range a race may occur
11 * in. Because the exact place where any race occurs is within the kernel,
12 * and therefore impossible to mark accurately, the library may add randomised
13 * delays to either thread in order to help find the exact race timing.
14 *
15 * Currently only two way races are explicitly supported, that is races
16 * involving two threads or processes. We refer to the main test thread as
17 * thread A and the child thread as thread B.
18 *
19 * In each thread you need a simple while- or for-loop which the tst_fzsync_*
20 * functions are called in. In the simplest case thread A will look something
21 * like:
22 *
23 * tst_fzsync_pair_reset(&pair, run_thread_b);
24 * while (tst_fzsync_run_a(&pair)) {
25 * // Perform some setup which must happen before the race
26 * tst_fzsync_start_race_a(&pair);
27 * // Do some dodgy syscall
28 * tst_fzsync_end_race_a(&pair);
29 * }
30 *
31 * Then in thread B (run_thread_b):
32 *
33 * while (tst_fzsync_run_b(&pair)) {
34 * tst_fzsync_start_race_b(&pair);
35 * // Do something which can race with the dodgy syscall in A
36 * tst_fzsync_end_race_b(&pair)
37 * }
38 *
39 * The calls to tst_fzsync_start/end_race and tst_fzsync_run_a/b block (at
40 * least) until both threads have enter them. These functions can only be
41 * called once for each iteration, but further synchronisation points can be
42 * added by calling tst_fzsync_wait_a() and tst_fzsync_wait_b() in each
43 * thread.
44 *
45 * The execution of the loops in threads A and B are bounded by both iteration
46 * count and time. A slow machine is likely to be limited by time and a fast
47 * one by iteration count. The user can use the -i parameter to run the test
48 * multiple times or LTP_TIMEOUT_MUL to give the test more time.
49 *
50 * It is possible to use the library just for tst_fzsync_pair_wait() to get a
51 * basic spin wait. However if you are actually testing a race condition then
52 * it is recommended to use tst_fzsync_start_race_a/b even if the
53 * randomisation is not needed. It provides some semantic information which
54 * may be useful in the future.
55 *
56 * For a usage example see testcases/cve/cve-2016-7117.c or just run
57 * 'git grep tst_fuzzy_sync.h'
58 *
59 * @sa tst_fzsync_pair
60 */
61
62 #include <math.h>
63 #include <stdbool.h>
64 #include <stdlib.h>
65 #include <sys/time.h>
66 #include <time.h>
67 #include "tst_atomic.h"
68 #include "tst_cpu.h"
69 #include "tst_timer.h"
70 #include "tst_safe_pthread.h"
71
72 #ifndef TST_FUZZY_SYNC_H__
73 #define TST_FUZZY_SYNC_H__
74
75 /* how much of exec time is sampling allowed to take */
76 #define SAMPLING_SLICE 0.5f
77
78 /** Some statistics for a variable */
79 struct tst_fzsync_stat {
80 float avg;
81 float avg_dev;
82 float dev_ratio;
83 };
84
85 /**
86 * The state of a two way synchronisation or race.
87 *
88 * This contains all the necessary state for approximately synchronising two
89 * sections of code in different threads.
90 *
91 * Some of the fields can be configured before calling
92 * tst_fzsync_pair_reset(), however this is mainly for debugging purposes. If
93 * a test requires one of the parameters to be modified, we should consider
94 * finding a way of automatically selecting an appropriate value at runtime.
95 *
96 * Internal fields should only be accessed by library functions.
97 */
98 struct tst_fzsync_pair {
99 /**
100 * The rate at which old diff samples are forgotten
101 *
102 * Defaults to 0.25.
103 */
104 float avg_alpha;
105 /** Internal; Thread A start time */
106 struct timespec a_start;
107 /** Internal; Thread B start time */
108 struct timespec b_start;
109 /** Internal; Thread A end time */
110 struct timespec a_end;
111 /** Internal; Thread B end time */
112 struct timespec b_end;
113 /** Internal; Avg. difference between a_start and b_start */
114 struct tst_fzsync_stat diff_ss;
115 /** Internal; Avg. difference between a_start and a_end */
116 struct tst_fzsync_stat diff_sa;
117 /** Internal; Avg. difference between b_start and b_end */
118 struct tst_fzsync_stat diff_sb;
119 /** Internal; Avg. difference between a_end and b_end */
120 struct tst_fzsync_stat diff_ab;
121 /** Internal; Number of spins while waiting for the slower thread */
122 int spins;
123 struct tst_fzsync_stat spins_avg;
124 /**
125 * Internal; Number of spins to use in the delay.
126 *
127 * A negative value delays thread A and a positive delays thread B.
128 */
129 int delay;
130 int delay_bias;
131 /**
132 * Internal; The number of samples left or the sampling state.
133 *
134 * A positive value is the number of remaining mandatory
135 * samples. Zero or a negative indicate some other state.
136 */
137 int sampling;
138 /**
139 * The Minimum number of statistical samples which must be collected.
140 *
141 * The minimum number of iterations which must be performed before a
142 * random delay can be calculated. Defaults to 1024.
143 */
144 int min_samples;
145 /**
146 * The maximum allowed proportional average deviation.
147 *
148 * A value in the range (0, 1) which gives the maximum average
149 * deviation which must be attained before random delays can be
150 * calculated.
151 *
152 * It is a ratio of (average_deviation / total_time). The default is
153 * 0.1, so this allows an average deviation of at most 10%.
154 */
155 float max_dev_ratio;
156
157 /** Internal; Atomic counter used by fzsync_pair_wait() */
158 int a_cntr;
159 /** Internal; Atomic counter used by fzsync_pair_wait() */
160 int b_cntr;
161 /** Internal; Used by tst_fzsync_pair_exit() and fzsync_pair_wait() */
162 int exit;
163 /**
164 * The maximum desired execution time as a proportion of the timeout
165 *
166 * A value x so that 0 < x < 1 which decides how long the test should
167 * be run for (assuming the loop limit is not exceeded first).
168 *
169 * Defaults to 0.5 (~150 seconds with default timeout).
170 */
171 float exec_time_p;
172 /** Internal; The test time remaining on tst_fzsync_pair_reset() */
173 float exec_time_start;
174 /**
175 * The maximum number of iterations to execute during the test
176 *
177 * Defaults to a large number, but not too large.
178 */
179 int exec_loops;
180 /** Internal; The current loop index */
181 int exec_loop;
182 /** Internal; The second thread or 0 */
183 pthread_t thread_b;
184 /**
185 * The flag indicates single core machines or not
186 *
187 * If running on single core machines, it would take considerable
188 * amount of time to run fuzzy sync library.
189 * Thus call sched_yield to give up cpu to decrease the test time.
190 */
191 bool yield_in_wait;
192
193 };
194
195 #define CHK(param, low, hi, def) do { \
196 pair->param = (pair->param ? pair->param : def); \
197 if (pair->param < low) \
198 tst_brk(TBROK, #param " is less than the lower bound " #low); \
199 if (pair->param > hi) \
200 tst_brk(TBROK, #param " is more than the upper bound " #hi); \
201 } while (0)
202 /**
203 * Ensures that any Fuzzy Sync parameters are properly set
204 *
205 * @relates tst_fzsync_pair
206 *
207 * Usually called from the setup function, it sets default parameter values or
208 * validates any existing non-defaults.
209 *
210 * @sa tst_fzsync_pair_reset()
211 */
tst_fzsync_pair_init(struct tst_fzsync_pair * pair)212 static void tst_fzsync_pair_init(struct tst_fzsync_pair *pair)
213 {
214 CHK(avg_alpha, 0, 1, 0.25);
215 CHK(min_samples, 20, INT_MAX, 1024);
216 CHK(max_dev_ratio, 0, 1, 0.1);
217 CHK(exec_time_p, 0, 1, 0.5);
218 CHK(exec_loops, 20, INT_MAX, 3000000);
219
220 if (tst_ncpus_available() <= 1)
221 pair->yield_in_wait = 1;
222 }
223 #undef CHK
224
225 /**
226 * Exit and join thread B if necessary.
227 *
228 * @relates tst_fzsync_pair
229 *
230 * Call this from your cleanup function.
231 */
tst_fzsync_pair_cleanup(struct tst_fzsync_pair * pair)232 static void tst_fzsync_pair_cleanup(struct tst_fzsync_pair *pair)
233 {
234 if (pair->thread_b) {
235 /* Revoke thread B if parent hits accidental break */
236 if (!pair->exit)
237 tst_atomic_store(1, &pair->exit);
238 SAFE_PTHREAD_JOIN(pair->thread_b, NULL);
239 pair->thread_b = 0;
240 }
241 }
242
243 /**
244 * Zero some stat fields
245 *
246 * @relates tst_fzsync_stat
247 */
tst_init_stat(struct tst_fzsync_stat * s)248 static void tst_init_stat(struct tst_fzsync_stat *s)
249 {
250 s->avg = 0;
251 s->avg_dev = 0;
252 }
253
254 /**
255 * Reset or initialise fzsync.
256 *
257 * @relates tst_fzsync_pair
258 * @param pair The state structure initialised with TST_FZSYNC_PAIR_INIT.
259 * @param run_b The function defining thread B or NULL.
260 *
261 * Call this from your main test function (thread A), just before entering the
262 * main loop. It will (re)set any variables needed by fzsync and (re)start
263 * thread B using the function provided.
264 *
265 * If you need to use fork or clone to start the second thread/process then
266 * you can pass NULL to run_b and handle starting and stopping thread B
267 * yourself. You may need to place tst_fzsync_pair in some shared memory as
268 * well.
269 *
270 * @sa tst_fzsync_pair_init()
271 */
tst_fzsync_pair_reset(struct tst_fzsync_pair * pair,void * (* run_b)(void *))272 static void tst_fzsync_pair_reset(struct tst_fzsync_pair *pair,
273 void *(*run_b)(void *))
274 {
275 tst_fzsync_pair_cleanup(pair);
276
277 tst_init_stat(&pair->diff_ss);
278 tst_init_stat(&pair->diff_sa);
279 tst_init_stat(&pair->diff_sb);
280 tst_init_stat(&pair->diff_ab);
281 tst_init_stat(&pair->spins_avg);
282 pair->delay = 0;
283 pair->delay_bias = 0;
284 pair->sampling = pair->min_samples;
285
286 pair->exec_loop = 0;
287
288 pair->a_cntr = 0;
289 pair->b_cntr = 0;
290 pair->exit = 0;
291 if (run_b)
292 SAFE_PTHREAD_CREATE(&pair->thread_b, 0, run_b, 0);
293
294 pair->exec_time_start = (float)tst_timeout_remaining();
295 }
296
297 /**
298 * Print stat
299 *
300 * @relates tst_fzsync_stat
301 */
tst_fzsync_stat_info(struct tst_fzsync_stat stat,char * unit,char * name)302 static inline void tst_fzsync_stat_info(struct tst_fzsync_stat stat,
303 char *unit, char *name)
304 {
305 tst_res(TINFO,
306 "%1$-17s: { avg = %3$5.0f%2$s, avg_dev = %4$5.0f%2$s, dev_ratio = %5$.2f }",
307 name, unit, stat.avg, stat.avg_dev, stat.dev_ratio);
308 }
309
310 /**
311 * Print some synchronisation statistics
312 *
313 * @relates tst_fzsync_pair
314 */
tst_fzsync_pair_info(struct tst_fzsync_pair * pair)315 static void tst_fzsync_pair_info(struct tst_fzsync_pair *pair)
316 {
317 tst_res(TINFO, "loop = %d, delay_bias = %d",
318 pair->exec_loop, pair->delay_bias);
319 tst_fzsync_stat_info(pair->diff_ss, "ns", "start_a - start_b");
320 tst_fzsync_stat_info(pair->diff_sa, "ns", "end_a - start_a");
321 tst_fzsync_stat_info(pair->diff_sb, "ns", "end_b - start_b");
322 tst_fzsync_stat_info(pair->diff_ab, "ns", "end_a - end_b");
323 tst_fzsync_stat_info(pair->spins_avg, " ", "spins");
324 }
325
326 /** Wraps clock_gettime */
tst_fzsync_time(struct timespec * t)327 static inline void tst_fzsync_time(struct timespec *t)
328 {
329 #ifdef CLOCK_MONOTONIC_RAW
330 clock_gettime(CLOCK_MONOTONIC_RAW, t);
331 #else
332 clock_gettime(CLOCK_MONOTONIC, t);
333 #endif
334 }
335
336 /**
337 * Exponential moving average
338 *
339 * @param alpha The preference for recent samples over old ones.
340 * @param sample The current sample
341 * @param prev_avg The average of the all the previous samples
342 *
343 * @return The average including the current sample.
344 */
tst_exp_moving_avg(float alpha,float sample,float prev_avg)345 static inline float tst_exp_moving_avg(float alpha,
346 float sample,
347 float prev_avg)
348 {
349 return alpha * sample + (1.0 - alpha) * prev_avg;
350 }
351
352 /**
353 * Update a stat with a new sample
354 *
355 * @relates tst_fzsync_stat
356 */
tst_upd_stat(struct tst_fzsync_stat * s,float alpha,float sample)357 static inline void tst_upd_stat(struct tst_fzsync_stat *s,
358 float alpha,
359 float sample)
360 {
361 s->avg = tst_exp_moving_avg(alpha, sample, s->avg);
362 s->avg_dev = tst_exp_moving_avg(alpha,
363 fabs(s->avg - sample), s->avg_dev);
364 s->dev_ratio = fabs(s->avg ? s->avg_dev / s->avg : 0);
365 }
366
367 /**
368 * Update a stat with a new diff sample
369 *
370 * @relates tst_fzsync_stat
371 */
tst_upd_diff_stat(struct tst_fzsync_stat * s,float alpha,struct timespec t1,struct timespec t2)372 static inline void tst_upd_diff_stat(struct tst_fzsync_stat *s,
373 float alpha,
374 struct timespec t1,
375 struct timespec t2)
376 {
377 tst_upd_stat(s, alpha, tst_timespec_diff_ns(t1, t2));
378 }
379
380 /**
381 * Calculate various statistics and the delay
382 *
383 * This function helps create the fuzz in fuzzy sync. Imagine we have the
384 * following timelines in threads A and B:
385 *
386 * start_race_a
387 * ^ end_race_a (a)
388 * | ^
389 * | |
390 * - --+------------------------+-- - -
391 * | Syscall A | Thread A
392 * - --+------------------------+-- - -
393 * - --+----------------+-------+-- - -
394 * | Syscall B | spin | Thread B
395 * - --+----------------+-------+-- - -
396 * | |
397 * ^ ^
398 * start_race_b end_race_b
399 *
400 * Here we have synchronised the calls to syscall A and B with start_race_{a,
401 * b} so that they happen at approximately the same time in threads A and
402 * B. If the race condition occurs during the entry code for these two
403 * functions then we will quickly hit it. If it occurs during the exit code of
404 * B and mid way through A, then we will quickly hit it.
405 *
406 * However if the exit paths of A and B need to be aligned and (end_race_a -
407 * end_race_b) is large relative to the variation in call times, the
408 * probability of hitting the race condition is close to zero. To solve this
409 * scenario (and others) a randomised delay is introduced before the syscalls
410 * in A and B. Given enough time the following should happen where the exit
411 * paths are now synchronised:
412 *
413 * start_race_a
414 * ^ end_race_a (a)
415 * | ^
416 * | |
417 * - --+------------------------+-- - -
418 * | Syscall A | Thread A
419 * - --+------------------------+-- - -
420 * - --+-------+----------------+-- - -
421 * | delay | Syscall B | Thread B
422 * - --+-------+----------------+-- - -
423 * | |
424 * ^ ^
425 * start_race_b end_race_b
426 *
427 * The delay is not introduced immediately and the delay range is only
428 * calculated once the average relative deviation has dropped below some
429 * percentage of the total time.
430 *
431 * The delay range is chosen so that any point in Syscall A could be
432 * synchronised with any point in Syscall B using a value from the
433 * range. Because the delay range may be too large for a linear search, we use
434 * an evenly distributed random function to pick a value from it.
435 *
436 * The delay range goes from positive to negative. A negative delay will delay
437 * thread A and a positive one will delay thread B. The range is bounded by
438 * the point where the entry code to Syscall A is synchronised with the exit
439 * to Syscall B and the entry code to Syscall B is synchronised with the exit
440 * of A.
441 *
442 * In order to calculate the lower bound (the max delay of A) we can simply
443 * negate the execution time of Syscall B and convert it to a spin count. For
444 * the upper bound (the max delay of B), we just take the execution time of A
445 * and convert it to a spin count.
446 *
447 * In order to calculate spin count we need to know approximately how long a
448 * spin takes and divide the delay time with it. We find this by first
449 * counting how many spins one thread spends waiting for the other during
450 * end_race[1]. We also know when each syscall exits so we can take the
451 * difference between the exit times and divide it with the number of spins
452 * spent waiting.
453 *
454 * All the times and counts we use in the calculation are averaged over a
455 * variable number of iterations. There is an initial sampling period where we
456 * simply collect time and count samples then calculate their averages. When a
457 * minimum number of samples have been collected, and if the average deviation
458 * is below some proportion of the average sample magnitude, then the sampling
459 * period is ended. On all further iterations a random delay is calculated and
460 * applied, but the averages are not updated.
461 *
462 * [1] This assumes there is always a significant difference. The algorithm
463 * may fail to introduce a delay (when one is needed) in situations where
464 * Syscall A and B finish at approximately the same time.
465 *
466 * @relates tst_fzsync_pair
467 */
tst_fzsync_pair_update(struct tst_fzsync_pair * pair)468 static void tst_fzsync_pair_update(struct tst_fzsync_pair *pair)
469 {
470 float alpha = pair->avg_alpha;
471 float per_spin_time, time_delay;
472 float max_dev = pair->max_dev_ratio;
473 int over_max_dev;
474
475 pair->delay = pair->delay_bias;
476
477 over_max_dev = pair->diff_ss.dev_ratio > max_dev
478 || pair->diff_sa.dev_ratio > max_dev
479 || pair->diff_sb.dev_ratio > max_dev
480 || pair->diff_ab.dev_ratio > max_dev
481 || pair->spins_avg.dev_ratio > max_dev;
482
483 if (pair->sampling > 0 || over_max_dev) {
484 tst_upd_diff_stat(&pair->diff_ss, alpha,
485 pair->a_start, pair->b_start);
486 tst_upd_diff_stat(&pair->diff_sa, alpha,
487 pair->a_end, pair->a_start);
488 tst_upd_diff_stat(&pair->diff_sb, alpha,
489 pair->b_end, pair->b_start);
490 tst_upd_diff_stat(&pair->diff_ab, alpha,
491 pair->a_end, pair->b_end);
492 tst_upd_stat(&pair->spins_avg, alpha, pair->spins);
493 if (pair->sampling > 0 && --pair->sampling == 0) {
494 tst_res(TINFO, "Minimum sampling period ended");
495 tst_fzsync_pair_info(pair);
496 }
497 } else if (fabsf(pair->diff_ab.avg) >= 1) {
498 per_spin_time = fabsf(pair->diff_ab.avg) / MAX(pair->spins_avg.avg, 1.0f);
499 time_delay = drand48() * (pair->diff_sa.avg + pair->diff_sb.avg)
500 - pair->diff_sb.avg;
501 pair->delay += (int)(1.1 * time_delay / per_spin_time);
502
503 if (!pair->sampling) {
504 tst_res(TINFO,
505 "Reached deviation ratios < %.2f, introducing randomness",
506 pair->max_dev_ratio);
507 tst_res(TINFO, "Delay range is [%d, %d]",
508 -(int)(pair->diff_sb.avg / per_spin_time) + pair->delay_bias,
509 (int)(pair->diff_sa.avg / per_spin_time) + pair->delay_bias);
510 tst_fzsync_pair_info(pair);
511 pair->sampling = -1;
512 }
513 } else if (!pair->sampling) {
514 tst_res(TWARN, "Can't calculate random delay");
515 tst_fzsync_pair_info(pair);
516 pair->sampling = -1;
517 }
518
519 pair->spins = 0;
520 }
521
522 /**
523 * Wait for the other thread
524 *
525 * @relates tst_fzsync_pair
526 * @param our_cntr The counter for the thread we are on
527 * @param other_cntr The counter for the thread we are synchronising with
528 * @param spins A pointer to the spin counter or NULL
529 * @param exit Exit flag when we need to break out of the wait loop
530 *
531 * Used by tst_fzsync_pair_wait_a(), tst_fzsync_pair_wait_b(),
532 * tst_fzsync_start_race_a(), etc. If the calling thread is ahead of the other
533 * thread, then it will spin wait. Unlike pthread_barrier_wait it will never
534 * use futex and can count the number of spins spent waiting.
535 *
536 * @return A non-zero value if the thread should continue otherwise the
537 * calling thread should exit.
538 */
tst_fzsync_pair_wait(int * our_cntr,int * other_cntr,int * spins,int * exit,bool yield_in_wait)539 static inline void tst_fzsync_pair_wait(int *our_cntr,
540 int *other_cntr,
541 int *spins,
542 int *exit,
543 bool yield_in_wait)
544 {
545 if (tst_atomic_inc(other_cntr) == INT_MAX) {
546 /*
547 * We are about to break the invariant that the thread with
548 * the lowest count is in front of the other. So we must wait
549 * here to ensure the other thread has at least reached the
550 * line above before doing that. If we are in rear position
551 * then our counter may already have been set to zero.
552 */
553 if (yield_in_wait) {
554 while (tst_atomic_load(our_cntr) > 0
555 && tst_atomic_load(our_cntr) < INT_MAX
556 && !tst_atomic_load(exit)) {
557 if (spins)
558 (*spins)++;
559
560 sched_yield();
561 }
562 } else {
563 while (tst_atomic_load(our_cntr) > 0
564 && tst_atomic_load(our_cntr) < INT_MAX
565 && !tst_atomic_load(exit)) {
566 if (spins)
567 (*spins)++;
568 }
569 }
570
571
572 tst_atomic_store(0, other_cntr);
573 /*
574 * Once both counters have been set to zero the invariant
575 * is restored and we can continue.
576 */
577 if (yield_in_wait) {
578 while (tst_atomic_load(our_cntr) > 1
579 && !tst_atomic_load(exit))
580 sched_yield();
581 } else {
582 while (tst_atomic_load(our_cntr) > 1
583 && !tst_atomic_load(exit))
584 ;
585 }
586 } else {
587 /*
588 * If our counter is less than the other thread's we are ahead
589 * of it and need to wait.
590 */
591 if (yield_in_wait) {
592 while (tst_atomic_load(our_cntr) <
593 tst_atomic_load(other_cntr)
594 && !tst_atomic_load(exit)) {
595 if (spins)
596 (*spins)++;
597 sched_yield();
598 }
599 } else {
600 while (tst_atomic_load(our_cntr) <
601 tst_atomic_load(other_cntr)
602 && !tst_atomic_load(exit)) {
603 if (spins)
604 (*spins)++;
605 }
606 }
607 }
608 }
609
610 /**
611 * Wait in thread A
612 *
613 * @relates tst_fzsync_pair
614 * @sa tst_fzsync_pair_wait
615 */
tst_fzsync_wait_a(struct tst_fzsync_pair * pair)616 static inline void tst_fzsync_wait_a(struct tst_fzsync_pair *pair)
617 {
618 tst_fzsync_pair_wait(&pair->a_cntr, &pair->b_cntr,
619 NULL, &pair->exit, pair->yield_in_wait);
620 }
621
622 /**
623 * Wait in thread B
624 *
625 * @relates tst_fzsync_pair
626 * @sa tst_fzsync_pair_wait
627 */
tst_fzsync_wait_b(struct tst_fzsync_pair * pair)628 static inline void tst_fzsync_wait_b(struct tst_fzsync_pair *pair)
629 {
630 tst_fzsync_pair_wait(&pair->b_cntr, &pair->a_cntr,
631 NULL, &pair->exit, pair->yield_in_wait);
632 }
633
634 /**
635 * Decide whether to continue running thread A
636 *
637 * @relates tst_fzsync_pair
638 *
639 * Checks some values and decides whether it is time to break the loop of
640 * thread A.
641 *
642 * @return True to continue and false to break.
643 * @sa tst_fzsync_run_a
644 */
tst_fzsync_run_a(struct tst_fzsync_pair * pair)645 static inline int tst_fzsync_run_a(struct tst_fzsync_pair *pair)
646 {
647 float rem_p = 1 - tst_timeout_remaining() / pair->exec_time_start;
648
649 if ((pair->exec_time_p * SAMPLING_SLICE < rem_p)
650 && (pair->sampling > 0)) {
651 tst_res(TINFO, "Stopped sampling at %d (out of %d) samples, "
652 "sampling time reached 50%% of the total time limit",
653 pair->exec_loop, pair->min_samples);
654 pair->sampling = 0;
655 tst_fzsync_pair_info(pair);
656 }
657
658 if (pair->exec_time_p < rem_p) {
659 tst_res(TINFO,
660 "Exceeded execution time, requesting exit");
661 tst_atomic_store(1, &pair->exit);
662 }
663
664 if (++pair->exec_loop > pair->exec_loops) {
665 tst_res(TINFO,
666 "Exceeded execution loops, requesting exit");
667 tst_atomic_store(1, &pair->exit);
668 }
669
670 tst_fzsync_wait_a(pair);
671
672 if (pair->exit) {
673 tst_fzsync_pair_cleanup(pair);
674 return 0;
675 }
676
677 return 1;
678 }
679
680 /**
681 * Decide whether to continue running thread B
682 *
683 * @relates tst_fzsync_pair
684 * @sa tst_fzsync_run_a
685 */
tst_fzsync_run_b(struct tst_fzsync_pair * pair)686 static inline int tst_fzsync_run_b(struct tst_fzsync_pair *pair)
687 {
688 tst_fzsync_wait_b(pair);
689 return !tst_atomic_load(&pair->exit);
690 }
691
692 /**
693 * Marks the start of a race region in thread A
694 *
695 * @relates tst_fzsync_pair
696 *
697 * This should be placed just before performing whatever action can cause a
698 * race condition. Usually it is placed just before a syscall and
699 * tst_fzsync_end_race_a() is placed just afterwards.
700 *
701 * A corresponding call to tst_fzsync_start_race_b() should be made in thread
702 * B.
703 *
704 * @return A non-zero value if the calling thread should continue to loop. If
705 * it returns zero then tst_fzsync_exit() has been called and you must exit
706 * the thread.
707 *
708 * @sa tst_fzsync_pair_update
709 */
tst_fzsync_start_race_a(struct tst_fzsync_pair * pair)710 static inline void tst_fzsync_start_race_a(struct tst_fzsync_pair *pair)
711 {
712 volatile int delay;
713
714 tst_fzsync_pair_update(pair);
715
716 tst_fzsync_wait_a(pair);
717
718 delay = pair->delay;
719 if (pair->yield_in_wait) {
720 while (delay < 0) {
721 sched_yield();
722 delay++;
723 }
724 } else {
725 while (delay < 0)
726 delay++;
727 }
728
729 tst_fzsync_time(&pair->a_start);
730 }
731
732 /**
733 * Marks the end of a race region in thread A
734 *
735 * @relates tst_fzsync_pair
736 * @sa tst_fzsync_start_race_a
737 */
tst_fzsync_end_race_a(struct tst_fzsync_pair * pair)738 static inline void tst_fzsync_end_race_a(struct tst_fzsync_pair *pair)
739 {
740 tst_fzsync_time(&pair->a_end);
741 tst_fzsync_pair_wait(&pair->a_cntr, &pair->b_cntr,
742 &pair->spins, &pair->exit, pair->yield_in_wait);
743 }
744
745 /**
746 * Marks the start of a race region in thread B
747 *
748 * @relates tst_fzsync_pair
749 * @sa tst_fzsync_start_race_a
750 */
tst_fzsync_start_race_b(struct tst_fzsync_pair * pair)751 static inline void tst_fzsync_start_race_b(struct tst_fzsync_pair *pair)
752 {
753 volatile int delay;
754
755 tst_fzsync_wait_b(pair);
756
757 delay = pair->delay;
758 if (pair->yield_in_wait) {
759 while (delay > 0) {
760 sched_yield();
761 delay--;
762 }
763 } else {
764 while (delay > 0)
765 delay--;
766 }
767
768 tst_fzsync_time(&pair->b_start);
769 }
770
771 /**
772 * Marks the end of a race region in thread B
773 *
774 * @relates tst_fzsync_pair
775 * @sa tst_fzsync_start_race_a
776 */
tst_fzsync_end_race_b(struct tst_fzsync_pair * pair)777 static inline void tst_fzsync_end_race_b(struct tst_fzsync_pair *pair)
778 {
779 tst_fzsync_time(&pair->b_end);
780 tst_fzsync_pair_wait(&pair->b_cntr, &pair->a_cntr,
781 &pair->spins, &pair->exit, pair->yield_in_wait);
782 }
783
784 /**
785 * Add some amount to the delay bias
786 *
787 * @relates tst_fzsync_pair
788 * @param change The amount to add, can be negative
789 *
790 * A positive change delays thread B and a negative one delays thread
791 * A.
792 *
793 * It is intended to be used in tests where the time taken by syscall A and/or
794 * B are significantly affected by their chronological order. To the extent
795 * that the delay range will not include the correct values if too many of the
796 * initial samples are taken when the syscalls (or operations within the
797 * syscalls) happen in the wrong order.
798 *
799 * An example of this is cve/cve-2016-7117.c where a call to close() is racing
800 * with a call to recvmmsg(). If close() happens before recvmmsg() has chance
801 * to check if the file descriptor is open then recvmmsg() completes very
802 * quickly. If the call to close() happens once recvmmsg() has already checked
803 * the descriptor it takes much longer. The sample where recvmmsg() completes
804 * quickly is essentially invalid for our purposes. The test uses the simple
805 * heuristic of whether recvmmsg() returns EBADF, to decide if it should call
806 * tst_fzsync_pair_add_bias() to further delay syscall B.
807 */
tst_fzsync_pair_add_bias(struct tst_fzsync_pair * pair,int change)808 static inline void tst_fzsync_pair_add_bias(struct tst_fzsync_pair *pair, int change)
809 {
810 if (pair->sampling > 0)
811 pair->delay_bias += change;
812 }
813
814 #endif /* TST_FUZZY_SYNC_H__ */
815