1 /* 2 * Copyright (c) 2017 Richard Palethorpe <rpalethorpe (at) suse.com> 3 * 4 * This program is free software: you can redistribute it and/or modify 5 * it under the terms of the GNU General Public License as published by 6 * the Free Software Foundation, either version 2 of the License, or 7 * (at your option) any later version. 8 * 9 * This program is distributed in the hope that it will be useful, 10 * but WITHOUT ANY WARRANTY; without even the implied warranty of 11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12 * GNU General Public License for more details. 13 * 14 * You should have received a copy of the GNU General Public License 15 * along with this program. If not, see <http://www.gnu.org/licenses/>. 16 */ 17 /* 18 * Fuzzy Synchronisation - abreviated to fzsync 19 * 20 * This library is intended to help reproduce race conditions by providing two 21 * thread synchronisation mechanisms. The first is a 'checkpoint' system where 22 * each thread will wait indefinitely for the other to enter a checkpoint 23 * before continuing. This is acheived by calling tst_fzsync_wait() and/or 24 * tst_fzsync_wait_update() at the points you want to synchronise in each 25 * thread. This is functionally very similar to using pthread_barrier_wait() 26 * with two threads. However tst_fzsync_wait() can be inlined and is 27 * guaranteed not to call sleep or futex. 28 * 29 * The second takes the form a of a delay which is calculated by measuring the 30 * time difference between two points in each thread and comparing it to the 31 * desired difference (default is zero). Using a delay allows you to 32 * synchronise the threads at a point outside of your direct control 33 * (e.g. inside the kernel) or just increase the accuracy for the first 34 * mechanism. It is acheived using tst_fzsync_delay_{a,b}(), 35 * tst_fzsync_time_{a,b}() and tst_fzsync[_wait_]update(). 36 * 37 * For a usage example see testcases/cve/cve-2016-7117.c or just run 38 * 'git grep tst_fuzzy_sync.h' 39 */ 40 41 #include <sys/time.h> 42 #include <time.h> 43 #include <math.h> 44 #include "tst_atomic.h" 45 46 #ifndef CLOCK_MONOTONIC_RAW 47 # define CLOCK_MONOTONIC_RAW CLOCK_MONOTONIC 48 #endif 49 50 /** 51 * struct tst_fzsync_pair - the state of a two way synchronisation 52 * @avg_diff: Internal; the average time difference over multiple iterations. 53 * @avg_diff_trgt: The desired average time difference, defaults to 0. 54 * @avg_alpha: The rate at which old diff samples are forgotten, 55 * defaults to 0.25. 56 * @avg_dev: Internal; Absolute average deviation. 57 * @a: Internal; The time at which call site A was last passed. 58 * @b: Internal; The time at which call site B was last passed. 59 * @delay: Internal; The size of the delay, positive to delay A, 60 * negative to delay B. 61 * @delay_inc: The step size of a delay increment, defaults to 1. 62 * @update_gap: The number of iterations between recalculating the delay. 63 * Defaults to 0xF and must be of the form $2^n - 1$ 64 * @info_gap: The number of iterations between printing some statistics. 65 * Defaults to 0x7FFFF and must also be one less than a power of 2. 66 * @a_cntr: Internal; Atomic counter used by fzsync_pair_wait() 67 * @b_cntr: Internal; Atomic counter used by fzsync_pair_wait() 68 * @exit: Internal; Used by tst_fzsync_pair_exit() and fzsync_pair_wait() 69 * 70 * This contains all the necessary state for synchronising two points A and 71 * B. Where A is the time of an event in one process and B is the time of an 72 * event in another process. 73 * 74 * Internal fields should only be accessed by library functions. 75 */ 76 struct tst_fzsync_pair { 77 float avg_diff; 78 float avg_diff_trgt; 79 float avg_alpha; 80 float avg_dev; 81 struct timespec a; 82 struct timespec b; 83 long delay; 84 long delay_inc; 85 int update_gap; 86 int info_gap; 87 int a_cntr; 88 int b_cntr; 89 int exit; 90 }; 91 92 /** 93 * TST_FZSYNC_PAIR_INIT - Default values for struct tst_fzysnc_pair 94 */ 95 #define TST_FZSYNC_PAIR_INIT { \ 96 .avg_alpha = 0.25, \ 97 .delay_inc = 1, \ 98 .update_gap = 0xF, \ 99 .info_gap = 0x7FFFF \ 100 } 101 102 /** 103 * tst_fzsync_pair_info - Print some synchronisation statistics 104 */ 105 static void tst_fzsync_pair_info(struct tst_fzsync_pair *pair) 106 { 107 tst_res(TINFO, 108 "avg_diff = %.0fns, avg_dev = %.0fns, delay = %05ld loops", 109 pair->avg_diff, pair->avg_dev, pair->delay); 110 } 111 112 /** 113 * tst_fzsync_delay_a - Perform spin delay for A, if needed 114 * 115 * Usually called just before the point you want to synchronise. 116 */ 117 static inline void tst_fzsync_delay_a(struct tst_fzsync_pair *pair) 118 { 119 volatile long spin_delay = pair->delay; 120 121 while (spin_delay > 0) 122 spin_delay--; 123 } 124 125 /** 126 * tst_fzsync_delay_b - Perform spin delay for B, if needed 127 * 128 * Usually called just before the point you want to synchronise. 129 */ 130 static inline void tst_fzsync_delay_b(struct tst_fzsync_pair *pair) 131 { 132 volatile long spin_delay = pair->delay; 133 134 while (spin_delay < 0) 135 spin_delay++; 136 } 137 138 static inline void tst_fzsync_time(struct timespec *t) 139 { 140 clock_gettime(CLOCK_MONOTONIC_RAW, t); 141 } 142 143 /** 144 * tst_fzsync_time_a - Set A's time to now. 145 * 146 * Called at the point you want to synchronise. 147 */ 148 static inline void tst_fzsync_time_a(struct tst_fzsync_pair *pair) 149 { 150 tst_fzsync_time(&pair->a); 151 } 152 153 /** 154 * tst_fzsync_time_b - Set B's call time to now. 155 * 156 * Called at the point you want to synchronise. 157 */ 158 static inline void tst_fzsync_time_b(struct tst_fzsync_pair *pair) 159 { 160 tst_fzsync_time(&pair->b); 161 } 162 163 /** 164 * tst_exp_moving_avg - Exponential moving average 165 * @alpha: The preference for recent samples over old ones. 166 * @sample: The current sample 167 * @prev_avg: The average of the all the previous samples 168 * 169 * Returns average including the current sample. 170 */ 171 static inline float tst_exp_moving_avg(float alpha, 172 float sample, 173 float prev_avg) 174 { 175 return alpha * sample + (1.0 - alpha) * prev_avg; 176 } 177 178 /** 179 * tst_fzsync_pair_update - Recalculate the delay 180 * @loop_index: The i in "for(i = 0;..." or zero to ignore update_gap 181 * @pair: The state necessary for calculating the delay 182 * 183 * This should be called at the end of each loop to update the average 184 * measured time difference (between A and B) and update the delay. It is 185 * assumed that A and B are less than a second apart. 186 * 187 * The values of update_gap, avg_alpha and delay_inc decide the speed at which 188 * the algorithm approaches the optimum delay value and whether it is 189 * stable. If your test is behaving strangely, it could be because this 190 * algorithm is behaving chaotically and flip-flopping between large positve 191 * and negative delay values. You can call tst_fzysync_pair_info every few 192 * loops to check whether the average difference and delay values are stable. 193 */ 194 static void tst_fzsync_pair_update(int loop_index, struct tst_fzsync_pair *pair) 195 { 196 long diff; 197 long inc = pair->delay_inc; 198 float target = pair->avg_diff_trgt; 199 float avg = pair->avg_diff; 200 201 diff = pair->a.tv_nsec - pair->b.tv_nsec 202 + 1000000000 * (pair->a.tv_sec - pair->b.tv_sec); 203 avg = tst_exp_moving_avg(pair->avg_alpha, diff, avg); 204 pair->avg_dev = tst_exp_moving_avg(pair->avg_alpha, 205 fabs(diff - avg), 206 pair->avg_dev); 207 208 if (!(loop_index & pair->update_gap)) { 209 if (avg > target) 210 pair->delay -= inc; 211 else if (avg < target) 212 pair->delay += inc; 213 } 214 215 if (!(loop_index & pair->info_gap)) 216 tst_fzsync_pair_info(pair); 217 218 pair->avg_diff = avg; 219 } 220 221 /** 222 * tst_fzsync_pair_wait - Wait for the other thread 223 * @our_cntr: The counter for the thread we are on 224 * @other_cntr: The counter for the thread we are synchronising with 225 * 226 * Use this (through tst_fzsync_pair_wait_a() and tst_fzsync_pair_wait_b()) if 227 * you need an additional synchronisation point in a thread or you do not want 228 * to use the delay facility (not recommended). See 229 * tst_fzsync_pair_wait_update(). 230 * 231 * Returns a non-zero value if the thread should continue otherwise the 232 * calling thread should exit. 233 */ 234 static inline int tst_fzsync_pair_wait(struct tst_fzsync_pair *pair, 235 int *our_cntr, int *other_cntr) 236 { 237 if (tst_atomic_inc(other_cntr) == INT_MAX) { 238 /* 239 * We are about to break the invariant that the thread with 240 * the lowest count is in front of the other. So we must wait 241 * here to ensure the other thread has atleast reached the 242 * line above before doing that. If we are in rear position 243 * then our counter may already have been set to zero. 244 */ 245 while (tst_atomic_load(our_cntr) > 0 246 && tst_atomic_load(our_cntr) < INT_MAX 247 && !tst_atomic_load(&pair->exit)) 248 ; 249 250 tst_atomic_store(0, other_cntr); 251 /* 252 * Once both counters have been set to zero the invariant 253 * is restored and we can continue. 254 */ 255 while (tst_atomic_load(our_cntr) > 1 256 && !tst_atomic_load(&pair->exit)) 257 ; 258 } else { 259 /* 260 * If our counter is less than the other thread's we are ahead 261 * of it and need to wait. 262 */ 263 while (tst_atomic_load(our_cntr) < tst_atomic_load(other_cntr) 264 && !tst_atomic_load(&pair->exit)) 265 ; 266 } 267 268 /* Only exit if we have done the same amount of work as the other thread */ 269 return !tst_atomic_load(&pair->exit) || 270 tst_atomic_load(other_cntr) <= tst_atomic_load(our_cntr); 271 } 272 273 static inline int tst_fzsync_wait_a(struct tst_fzsync_pair *pair) 274 { 275 return tst_fzsync_pair_wait(pair, &pair->a_cntr, &pair->b_cntr); 276 } 277 278 static inline int tst_fzsync_wait_b(struct tst_fzsync_pair *pair) 279 { 280 return tst_fzsync_pair_wait(pair, &pair->b_cntr, &pair->a_cntr); 281 } 282 283 /** 284 * tst_fzsync_pair_wait_update_{a,b} - Wait and then recalculate 285 * 286 * This allows you to have two long running threads which wait for each other 287 * every iteration. So each thread will exit this function at approximately 288 * the same time. It also updates the delay values in a thread safe manner. 289 * 290 * You must call this function in both threads the same number of times each 291 * iteration. So a call in one thread must match with a call in the 292 * other. Make sure that calls to tst_fzsync_pair_wait() and 293 * tst_fzsync_pair_wait_update() happen in the same order in each thread. That 294 * is, make sure that a call to tst_fzsync_pair_wait_update_a() in one thread 295 * corresponds to a call to tst_fzsync_pair_wait_update_b() in the other. 296 * 297 * Returns a non-zero value if the calling thread should continue to loop. If 298 * it returns zero then tst_fzsync_exit() has been called and you must exit 299 * the thread. 300 */ 301 static inline int tst_fzsync_wait_update_a(struct tst_fzsync_pair *pair) 302 { 303 static int loop_index; 304 305 tst_fzsync_pair_wait(pair, &pair->a_cntr, &pair->b_cntr); 306 loop_index++; 307 tst_fzsync_pair_update(loop_index, pair); 308 return tst_fzsync_pair_wait(pair, &pair->a_cntr, &pair->b_cntr); 309 } 310 311 static inline int tst_fzsync_wait_update_b(struct tst_fzsync_pair *pair) 312 { 313 tst_fzsync_pair_wait(pair, &pair->b_cntr, &pair->a_cntr); 314 return tst_fzsync_pair_wait(pair, &pair->b_cntr, &pair->a_cntr); 315 } 316 317 /** 318 * tst_fzsync_pair_exit - Signal that the other thread should exit 319 * 320 * Causes tst_fzsync_pair_wait() and tst_fzsync_pair_wait_update() to return 321 * 0. 322 */ 323 static inline void tst_fzsync_pair_exit(struct tst_fzsync_pair *pair) 324 { 325 tst_atomic_store(1, &pair->exit); 326 } 327
