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 basic ability to reproduce a particular
9 * outcome to a data race when the critical sections are not aligned.
10 *
11 * We make the simplifying assumptions that:
12 * - Each thread contains a single contiguous critical section.
13 * - The threads only interact through a single variable.
14 * - The various timings are constant except for variations introduced
15 * by the environment.
16 *
17 * If a single data race has N critical sections then we may remove
18 * N-1 sections to produce a more difficult race. We may then test
19 * only the more difficult race and induce from this the outcome of
20 * testing the easier races.
21 *
22 * In real code, the threads may interact through many side
23 * effects. While some of these side effects may not result in a bug,
24 * they may effect the total time it takes to execute either
25 * thread. This will be handled in tst_fuzzy_sync02.
26 *
27 * The number of variables which two threads interact through is
28 * irrelevant as the combined state of two variables can be
29 * represented with a single variable. We may also reduce the number
30 * of states to simply those required to show the thread is inside or
31 * outside of the critical section.
32 *
33 * There are two fundamental races which require alignment under these
34 * assumptions:
35 * 1 2
36 * A +-----+ +----+ The outer box is total execution time.
37 * | # | | # | The '#' is the critical section.
38 *
39 * | # | | # |
40 * B +----+ +-----+
41 *
42 * So we can either have the critical section of the shorter race
43 * before that of the longer one. Or the critical section of the
44 * longer one before the shorter.
45 *
46 * In reality both threads will never be the same length, but we can
47 * test that anyway. We also test with both A as the shorter and B as
48 * the shorter. We also vary the distance of the critical section from
49 * the start or end. The delay times are cubed to ensure that a delay
50 * range is required.
51 *
52 * When entering their critical sections, both threads increment the
53 * 'c' counter variable atomically. They both also increment it when
54 * leaving their critical sections. We record the value of 'c' when A
55 * increments it. From the recorded values of 'c' we can deduce if the
56 * critical sections overlap and their ordering.
57 *
58 * Start (cs) | End (ct) | Ordering
59 * --------------------------------------------
60 * 1 | 2 | A before B
61 * 3 | 4 | B before A
62 *
63 * Any other combination of 'cs' and 'ct' means the critical sections
64 * overlapped.
65 \*/
66
67 #include "tst_test.h"
68 #include "tst_fuzzy_sync.h"
69
70 /* Scale all the delay times by this function. The races become harder
71 * the faster this function grows. With cubic scaling the race windows
72 * will be 27 times smaller than the entry or return delays. Because
73 * TIME_SCALE(1) = 1*1*1, TIME_SCALE(3) = 3*3*3.
74 */
75 #define TIME_SCALE(x) ((x) * (x) * (x))
76
77 /* The time signature of a code path containing a critical section. */
78 struct window {
79 /* The delay until the start of the critical section */
80 const int critical_s;
81 /* The length of the critical section */
82 const int critical_t;
83 /* The remaining delay until the method returns */
84 const int return_t;
85 };
86
87 /* The time signatures of threads A and B */
88 struct race {
89 const struct window a;
90 const struct window b;
91 };
92
93 static int c;
94 static struct tst_fzsync_pair pair;
95
96 static const struct race races[] = {
97 /* Degnerate cases where the critical sections are already
98 * aligned. The first case will fail when ncpu < 2 as a yield
99 * inside the critical section is required for the other
100 * thread to run.
101 */
102 { .a = { 0, 0, 0 }, .b = { 0, 0, 0 } },
103 { .a = { 0, 1, 0 }, .b = { 0, 1, 0 } },
104 { .a = { 1, 1, 1 }, .b = { 1, 1, 1 } },
105 { .a = { 3, 1, 1 }, .b = { 3, 1, 1 } },
106
107 /* Both windows are the same length */
108 { .a = { 3, 1, 1 }, .b = { 1, 1, 3 } },
109 { .a = { 1, 1, 3 }, .b = { 3, 1, 1 } },
110
111 /* Different sized windows */
112 { .a = { 3, 1, 1 }, .b = { 1, 1, 2 } },
113 { .a = { 1, 1, 3 }, .b = { 2, 1, 1 } },
114 { .a = { 2, 1, 1 }, .b = { 1, 1, 3 } },
115 { .a = { 1, 1, 2 }, .b = { 3, 1, 1 } },
116
117 /* Same as above, but with critical section at entry or exit */
118 { .a = { 3, 1, 0 }, .b = { 0, 1, 3 } },
119 { .a = { 0, 1, 3 }, .b = { 3, 1, 0 } },
120
121 { .a = { 3, 1, 0 }, .b = { 0, 1, 2 } },
122 { .a = { 0, 1, 3 }, .b = { 2, 1, 0 } },
123 { .a = { 2, 1, 0 }, .b = { 0, 1, 3 } },
124 { .a = { 0, 1, 2 }, .b = { 3, 1, 0 } },
125
126 /* One side is very short */
127 { .a = { 3, 1, 1 }, .b = { 0, 1, 0 } },
128 { .a = { 1, 1, 3 }, .b = { 0, 1, 0 } },
129 { .a = { 0, 1, 0 }, .b = { 1, 1, 3 } },
130 { .a = { 0, 1, 0 }, .b = { 3, 1, 1 } },
131
132 { .a = { 3, 1, 1 }, .b = { 0, 0, 0 } },
133 { .a = { 1, 1, 3 }, .b = { 0, 0, 0 } },
134 { .a = { 0, 0, 0 }, .b = { 1, 1, 3 } },
135 { .a = { 0, 0, 0 }, .b = { 3, 1, 1 } },
136
137 };
138
cleanup(void)139 static void cleanup(void)
140 {
141 tst_fzsync_pair_cleanup(&pair);
142 }
143
setup(void)144 static void setup(void)
145 {
146 pair.min_samples = 10000;
147
148 tst_fzsync_pair_init(&pair);
149 }
150
delay(const int t)151 static void delay(const int t)
152 {
153 int k = TIME_SCALE(t);
154
155 while (k--)
156 sched_yield();
157 }
158
worker(void * v)159 static void *worker(void *v)
160 {
161 unsigned int i = *(unsigned int *)v;
162 const struct window b = races[i].b;
163
164 while (tst_fzsync_run_b(&pair)) {
165 if (tst_atomic_load(&c))
166 tst_brk(TBROK, "Counter should now be zero");
167
168 tst_fzsync_start_race_b(&pair);
169 delay(b.critical_s);
170
171 tst_atomic_add_return(1, &c);
172 delay(b.critical_t);
173 tst_atomic_add_return(1, &c);
174
175 delay(b.return_t);
176 tst_fzsync_end_race_b(&pair);
177 }
178
179 return NULL;
180 }
181
run(unsigned int i)182 static void run(unsigned int i)
183 {
184 const struct window a = races[i].a;
185 int cs, ct, r, too_early = 0, critical = 0, too_late = 0;
186
187 tst_fzsync_pair_reset(&pair, NULL);
188 SAFE_PTHREAD_CREATE(&pair.thread_b, 0, worker, &i);
189
190 while (tst_fzsync_run_a(&pair)) {
191
192 tst_fzsync_start_race_a(&pair);
193 delay(a.critical_s);
194
195 cs = tst_atomic_add_return(1, &c);
196 delay(a.critical_t);
197 ct = tst_atomic_add_return(1, &c);
198
199 delay(a.return_t);
200 tst_fzsync_end_race_a(&pair);
201
202 if (cs == 1 && ct == 2)
203 too_early++;
204 else if (cs == 3 && ct == 4)
205 too_late++;
206 else
207 critical++;
208
209 r = tst_atomic_add_return(-4, &c);
210 if (r)
211 tst_brk(TBROK, "cs = %d, ct = %d, r = %d", cs, ct, r);
212
213 if (critical > 100) {
214 tst_fzsync_pair_cleanup(&pair);
215 break;
216 }
217 }
218
219 tst_res(critical > 50 ? TPASS : TFAIL,
220 "acs:%-2d act:%-2d art:%-2d | =:%-4d -:%-4d +:%-4d",
221 a.critical_s, a.critical_t, a.return_t,
222 critical, too_early, too_late);
223 }
224
225 static struct tst_test test = {
226 .tcnt = ARRAY_SIZE(races),
227 .test = run,
228 .setup = setup,
229 .cleanup = cleanup,
230 .max_runtime = 150,
231 };
232