1 // SPDX-License-Identifier: GPL-2.0-or-later
2 /*
3 * Copyright (c) 2021 Richard Palethorpe <rpalethorpe@suse.com>
4 */
5 /*\
6 * [Description]
7 *
8 * This verifies Fuzzy Sync's ability to reproduce a particular
9 * outcome to a data race when multiple races are present.
10 *
11 * We make the simplifying assumptions that:
12 * - There is one data race we want to hit and one to avoid.
13 * - Each thread contains two contiguous critical sections. One for each race.
14 * - The threads only interact through two variables, one for each race.
15 * - If we hit the race we want to avoid then it causes thread A to exit early.
16 *
17 * We don't consider more complicated dynamic interactions between the
18 * two threads. Fuzzy Sync will eventually trigger a race so long as
19 * the delay range is large enough. Assuming the race is possible to
20 * reproduce without further tampering to increase the race window (a
21 * technique specific to each race). So I conject that beyond a lower
22 * threshold of complexity, increasing the complexity of the race is
23 * no different from adding random noise.
24 *
25 * Emperically this appears to be true. So far we have seen in
26 * reproducers that there are no more than two significant data
27 * races. One we wish to reproduce and one we wish to avoid. It is
28 * possible that the code contains multiple data races, but that they
29 * appear only as two to us.
30 *
31 * Indeed it is also only possible to add a delay to A or B. So
32 * regardless of the underlying complexity we really only have two
33 * options.
34 *
35 * Here we only test a bias to delay B. A delay of A would be
36 * identical except that the necessary delay bias would be negative.
37 *
38 \*/
39
40 #include "tst_test.h"
41 #include "tst_fuzzy_sync.h"
42
43 /* The time signature of a code path containing a critical section. */
44 struct window {
45 /* The delay until the start of the critical section */
46 const int critical_s;
47 /* The length of the critical section */
48 const int critical_t;
49 /* The remaining delay until the method returns */
50 const int return_t;
51 };
52
53 /* The time signatures of threads A and B. We interlace the two
54 * windows for each thread. bd.return_t is ignored, but ad.return_t is
55 * used instead of a.return_t if the ad and bd critical sections
56 * overlap. This may result in the critical section of a never being
57 * reached.
58 */
59 struct race {
60 const struct window ad;
61 const struct window a;
62 const struct window bd;
63 const struct window b;
64 };
65
66 static int c, d;
67 static struct tst_fzsync_pair pair;
68
69 static const struct race races[] = {
70 { .a = { 1, 1, 1 }, .b = { 1, 1, 1 },
71 .ad = { 0, 1, 0 }, .bd = { 0, 1, 0 } },
72 { .a = { 30, 1, 1 }, .b = { 1, 1, 1 },
73 .ad = { 0, 1, 0 }, .bd = { 0, 20, 0 } },
74 { .a = { 40, 1, 0 }, .b = { 1, 1, 20 },
75 .ad = { 1, 10, 0 }, .bd = { 1, 10, 0 } },
76 };
77
cleanup(void)78 static void cleanup(void)
79 {
80 tst_fzsync_pair_cleanup(&pair);
81 }
82
setup(void)83 static void setup(void)
84 {
85 pair.min_samples = 10000;
86
87 tst_fzsync_pair_init(&pair);
88 }
89
to_abs(const struct window w)90 static struct window to_abs(const struct window w)
91 {
92 const struct window wc = {
93 w.critical_s,
94 w.critical_s + w.critical_t,
95 w.critical_s + w.critical_t + w.return_t,
96 };
97
98 return wc;
99 }
100
worker(void * v)101 static void *worker(void *v)
102 {
103 unsigned int i = *(unsigned int *)v;
104 const struct window b = to_abs(races[i].b);
105 const struct window bd = to_abs(races[i].bd);
106 int now, fin = MAX(b.return_t, bd.return_t);
107
108 while (tst_fzsync_run_b(&pair)) {
109 tst_fzsync_start_race_b(&pair);
110 for (now = 0; now <= fin; now++) {
111 if (now == b.critical_s || now == b.critical_t)
112 tst_atomic_add_return(1, &c);
113 if (now == bd.critical_s || now == bd.critical_t)
114 tst_atomic_add_return(1, &d);
115
116 sched_yield();
117 }
118 tst_fzsync_end_race_b(&pair);
119 }
120
121 return NULL;
122 }
123
run(unsigned int i)124 static void run(unsigned int i)
125 {
126 const struct window a = to_abs(races[i].a);
127 const struct window ad = to_abs(races[i].ad);
128 struct tst_fzsync_run_thread wrap_run_b = {
129 .func = worker,
130 .arg = &i,
131 };
132 int critical = 0;
133 int now, fin;
134
135 tst_fzsync_pair_reset(&pair, NULL);
136 SAFE_PTHREAD_CREATE(&pair.thread_b, 0, tst_fzsync_thread_wrapper,
137 &wrap_run_b);
138
139 while (tst_fzsync_run_a(&pair)) {
140 c = 0;
141 d = 0;
142 fin = a.return_t;
143
144 tst_fzsync_start_race_a(&pair);
145 for (now = 0; now <= fin; now++) {
146 if (now >= ad.critical_s &&
147 now <= ad.critical_t && tst_atomic_load(&d) > 0)
148 fin = ad.return_t;
149
150 if (now >= a.critical_s &&
151 now <= a.critical_t && tst_atomic_load(&c) == 1) {
152 tst_atomic_add_return(1, &c);
153 critical++;
154 }
155
156 sched_yield();
157 }
158 tst_fzsync_end_race_a(&pair);
159
160 if (fin == ad.return_t)
161 tst_fzsync_pair_add_bias(&pair, 1);
162
163 if (critical > 100) {
164 tst_fzsync_pair_cleanup(&pair);
165 break;
166 }
167 }
168
169 tst_res(critical > 50 ? TPASS : TFAIL, "%d| =:%-4d", i, critical);
170 }
171
172 static struct tst_test test = {
173 .tcnt = ARRAY_SIZE(races),
174 .test = run,
175 .setup = setup,
176 .cleanup = cleanup,
177 };
178