Tor  0.4.6.0-alpha-dev
test-timeout.c
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include <string.h>
4 #include <assert.h>
5 #include <limits.h>
6 
7 #include "ext/timeouts/timeout.h"
8 
9 #define THE_END_OF_TIME ((timeout_t)-1)
10 
11 static int check_misc(void) {
12  if (TIMEOUT_VERSION != timeout_version())
13  return 1;
14  if (TIMEOUT_V_REL != timeout_v_rel())
15  return 1;
16  if (TIMEOUT_V_API != timeout_v_api())
17  return 1;
18  if (TIMEOUT_V_ABI != timeout_v_abi())
19  return 1;
20  if (strcmp(timeout_vendor(), TIMEOUT_VENDOR))
21  return 1;
22  return 0;
23 }
24 
25 static int check_open_close(timeout_t hz_set, timeout_t hz_expect) {
26  int err=0;
27  struct timeouts *tos = timeouts_open(hz_set, &err);
28  if (!tos)
29  return 1;
30  if (err)
31  return 1;
32  if (hz_expect != timeouts_hz(tos))
33  return 1;
34  timeouts_close(tos);
35  return 0;
36 }
37 
38 /* Not very random */
39 static timeout_t random_to(timeout_t min, timeout_t max)
40 {
41  if (max <= min)
42  return min;
43  /* Not actually all that random, but should exercise the code. */
44  timeout_t rand64 = random() * (timeout_t)INT_MAX + random();
45  return min + (rand64 % (max-min));
46 }
47 
48 /* configuration for check_randomized */
49 struct rand_cfg {
50  /* When creating timeouts, smallest possible delay */
51  timeout_t min_timeout;
52  /* When creating timeouts, largest possible delay */
53  timeout_t max_timeout;
54  /* First time to start the clock at. */
55  timeout_t start_at;
56  /* Do not advance the clock past this time. */
57  timeout_t end_at;
58  /* Number of timeouts to create and monitor. */
59  int n_timeouts;
60  /* Advance the clock by no more than this each step. */
61  timeout_t max_step;
62  /* Use relative timers and stepping */
63  int relative;
64  /* Every time the clock ticks, try removing this many timeouts at
65  * random. */
66  int try_removing;
67  /* When we're done, advance the clock to the end of time. */
68  int finalize;
69 };
70 
71 static int check_randomized(const struct rand_cfg *cfg)
72 {
73 #define FAIL() do { \
74  printf("Failure on line %d\n", __LINE__); \
75  goto done; \
76  } while (0)
77 
78  int i, err;
79  int rv = 1;
80  struct timeout *t = calloc(cfg->n_timeouts, sizeof(struct timeout));
81  timeout_t *timeouts = calloc(cfg->n_timeouts, sizeof(timeout_t));
82  uint8_t *fired = calloc(cfg->n_timeouts, sizeof(uint8_t));
83  uint8_t *found = calloc(cfg->n_timeouts, sizeof(uint8_t));
84  uint8_t *deleted = calloc(cfg->n_timeouts, sizeof(uint8_t));
85  struct timeouts *tos = timeouts_open(0, &err);
86  timeout_t now = cfg->start_at;
87  int n_added_pending = 0, cnt_added_pending = 0;
88  int n_added_expired = 0, cnt_added_expired = 0;
89  struct timeouts_it it_p, it_e, it_all;
90  int p_done = 0, e_done = 0, all_done = 0;
91  struct timeout *to = NULL;
92  const int rel = cfg->relative;
93 
94  if (!t || !timeouts || !tos || !fired || !found || !deleted)
95  FAIL();
96  timeouts_update(tos, cfg->start_at);
97 
98  for (i = 0; i < cfg->n_timeouts; ++i) {
99  if (&t[i] != timeout_init(&t[i], rel ? 0 : TIMEOUT_ABS))
100  FAIL();
101  if (timeout_pending(&t[i]))
102  FAIL();
103  if (timeout_expired(&t[i]))
104  FAIL();
105 
106  timeouts[i] = random_to(cfg->min_timeout, cfg->max_timeout);
107 
108  timeouts_add(tos, &t[i], timeouts[i] - (rel ? now : 0));
109  if (timeouts[i] <= cfg->start_at) {
110  if (timeout_pending(&t[i]))
111  FAIL();
112  if (! timeout_expired(&t[i]))
113  FAIL();
114  ++n_added_expired;
115  } else {
116  if (! timeout_pending(&t[i]))
117  FAIL();
118  if (timeout_expired(&t[i]))
119  FAIL();
120  ++n_added_pending;
121  }
122  }
123 
124  if (!!n_added_pending != timeouts_pending(tos))
125  FAIL();
126  if (!!n_added_expired != timeouts_expired(tos))
127  FAIL();
128 
129  /* Test foreach, interleaving a few iterators. */
130  TIMEOUTS_IT_INIT(&it_p, TIMEOUTS_PENDING);
131  TIMEOUTS_IT_INIT(&it_e, TIMEOUTS_EXPIRED);
132  TIMEOUTS_IT_INIT(&it_all, TIMEOUTS_ALL);
133  while (! (p_done && e_done && all_done)) {
134  if (!p_done) {
135  to = timeouts_next(tos, &it_p);
136  if (to) {
137  i = to - &t[0];
138  ++found[i];
139  ++cnt_added_pending;
140  } else {
141  p_done = 1;
142  }
143  }
144  if (!e_done) {
145  to = timeouts_next(tos, &it_e);
146  if (to) {
147  i = to - &t[0];
148  ++found[i];
149  ++cnt_added_expired;
150  } else {
151  e_done = 1;
152  }
153  }
154  if (!all_done) {
155  to = timeouts_next(tos, &it_all);
156  if (to) {
157  i = to - &t[0];
158  ++found[i];
159  } else {
160  all_done = 1;
161  }
162  }
163  }
164 
165  for (i = 0; i < cfg->n_timeouts; ++i) {
166  if (found[i] != 2)
167  FAIL();
168  }
169  if (cnt_added_expired != n_added_expired)
170  FAIL();
171  if (cnt_added_pending != n_added_pending)
172  FAIL();
173 
174  while (NULL != (to = timeouts_get(tos))) {
175  i = to - &t[0];
176  assert(&t[i] == to);
177  if (timeouts[i] > cfg->start_at)
178  FAIL(); /* shouldn't have happened yet */
179 
180  --n_added_expired; /* drop expired timeouts. */
181  ++fired[i];
182  }
183 
184  if (n_added_expired != 0)
185  FAIL();
186 
187  while (now < cfg->end_at) {
188  int n_fired_this_time = 0;
189  timeout_t first_at = timeouts_timeout(tos) + now;
190 
191  timeout_t oldtime = now;
192  timeout_t step = random_to(1, cfg->max_step);
193  int another;
194  now += step;
195  if (rel)
196  timeouts_step(tos, step);
197  else
198  timeouts_update(tos, now);
199 
200  for (i = 0; i < cfg->try_removing; ++i) {
201  int idx = random() % cfg->n_timeouts;
202  if (! fired[idx]) {
203  timeout_del(&t[idx]);
204  ++deleted[idx];
205  }
206  }
207 
208  another = (timeouts_timeout(tos) == 0);
209 
210  while (NULL != (to = timeouts_get(tos))) {
211  if (! another)
212  FAIL(); /* Thought we saw the last one! */
213  i = to - &t[0];
214  assert(&t[i] == to);
215  if (timeouts[i] > now)
216  FAIL(); /* shouldn't have happened yet */
217  if (timeouts[i] <= oldtime)
218  FAIL(); /* should have happened already */
219  if (timeouts[i] < first_at)
220  FAIL(); /* first_at should've been earlier */
221  fired[i]++;
222  n_fired_this_time++;
223  another = (timeouts_timeout(tos) == 0);
224  }
225  if (n_fired_this_time && first_at > now)
226  FAIL(); /* first_at should've been earlier */
227  if (another)
228  FAIL(); /* Huh? We think there are more? */
229  if (!timeouts_check(tos, stderr))
230  FAIL();
231  }
232 
233  for (i = 0; i < cfg->n_timeouts; ++i) {
234  if (fired[i] > 1)
235  FAIL(); /* Nothing fired twice. */
236  if (timeouts[i] <= now) {
237  if (!(fired[i] || deleted[i]))
238  FAIL();
239  } else {
240  if (fired[i])
241  FAIL();
242  }
243  if (fired[i] && deleted[i])
244  FAIL();
245  if (cfg->finalize > 1) {
246  if (!fired[i])
247  timeout_del(&t[i]);
248  }
249  }
250 
251  /* Now nothing more should fire between now and the end of time. */
252  if (cfg->finalize) {
253  timeouts_update(tos, THE_END_OF_TIME);
254  if (cfg->finalize > 1) {
255  if (timeouts_get(tos))
256  FAIL();
257  TIMEOUTS_FOREACH(to, tos, TIMEOUTS_ALL)
258  FAIL();
259  }
260  }
261  rv = 0;
262 
263  done:
264  if (tos) timeouts_close(tos);
265  if (t) free(t);
266  if (timeouts) free(timeouts);
267  if (fired) free(fired);
268  if (found) free(found);
269  if (deleted) free(deleted);
270  return rv;
271 }
272 
274  const timeout_t *timeouts;
275  int n_timeouts;
276  timeout_t start_at;
277  timeout_t end_at;
278  timeout_t skip;
279 };
280 
281 int
282 check_intervals(struct intervals_cfg *cfg)
283 {
284  int i, err;
285  int rv = 1;
286  struct timeout *to;
287  struct timeout *t = calloc(cfg->n_timeouts, sizeof(struct timeout));
288  unsigned *fired = calloc(cfg->n_timeouts, sizeof(unsigned));
289  struct timeouts *tos = timeouts_open(0, &err);
290 
291  timeout_t now = cfg->start_at;
292  if (!t || !tos || !fired)
293  FAIL();
294 
295  timeouts_update(tos, now);
296 
297  for (i = 0; i < cfg->n_timeouts; ++i) {
298  if (&t[i] != timeout_init(&t[i], TIMEOUT_INT))
299  FAIL();
300  if (timeout_pending(&t[i]))
301  FAIL();
302  if (timeout_expired(&t[i]))
303  FAIL();
304 
305  timeouts_add(tos, &t[i], cfg->timeouts[i]);
306  if (! timeout_pending(&t[i]))
307  FAIL();
308  if (timeout_expired(&t[i]))
309  FAIL();
310  }
311 
312  while (now < cfg->end_at) {
313  timeout_t delay = timeouts_timeout(tos);
314  if (cfg->skip && delay < cfg->skip)
315  delay = cfg->skip;
316  timeouts_step(tos, delay);
317  now += delay;
318 
319  while (NULL != (to = timeouts_get(tos))) {
320  i = to - &t[0];
321  assert(&t[i] == to);
322  fired[i]++;
323  if (0 != (to->expires - cfg->start_at) % cfg->timeouts[i])
324  FAIL();
325  if (to->expires <= now)
326  FAIL();
327  if (to->expires > now + cfg->timeouts[i])
328  FAIL();
329  }
330  if (!timeouts_check(tos, stderr))
331  FAIL();
332  }
333 
334  timeout_t duration = now - cfg->start_at;
335  for (i = 0; i < cfg->n_timeouts; ++i) {
336  if (cfg->skip) {
337  if (fired[i] > duration / cfg->timeouts[i])
338  FAIL();
339  } else {
340  if (fired[i] != duration / cfg->timeouts[i])
341  FAIL();
342  }
343  if (!timeout_pending(&t[i]))
344  FAIL();
345  }
346 
347  rv = 0;
348  done:
349  if (t) free(t);
350  if (fired) free(fired);
351  if (tos) free(tos);
352  return rv;
353 }
354 
355 int
356 main(int argc, char **argv)
357 {
358  int j;
359  int n_failed = 0;
360 #define DO(fn) do { \
361  printf("."); fflush(stdout); \
362  if (fn) { \
363  ++n_failed; \
364  printf("%s failed\n", #fn); \
365  } \
366  } while (0)
367 
368 #define DO_N(n, fn) do { \
369  for (j = 0; j < (n); ++j) { \
370  DO(fn); \
371  } \
372  } while (0)
373 
374  DO(check_misc());
375  DO(check_open_close(1000, 1000));
376  DO(check_open_close(0, TIMEOUT_mHZ));
377 
378  struct rand_cfg cfg1 = {
379  .min_timeout = 1,
380  .max_timeout = 100,
381  .start_at = 5,
382  .end_at = 1000,
383  .n_timeouts = 1000,
384  .max_step = 10,
385  .relative = 0,
386  .try_removing = 0,
387  .finalize = 2,
388  };
389  DO_N(300,check_randomized(&cfg1));
390 
391  struct rand_cfg cfg2 = {
392  .min_timeout = 20,
393  .max_timeout = 1000,
394  .start_at = 10,
395  .end_at = 100,
396  .n_timeouts = 1000,
397  .max_step = 5,
398  .relative = 1,
399  .try_removing = 0,
400  .finalize = 2,
401  };
402  DO_N(300,check_randomized(&cfg2));
403 
404  struct rand_cfg cfg2b = {
405  .min_timeout = 20,
406  .max_timeout = 1000,
407  .start_at = 10,
408  .end_at = 100,
409  .n_timeouts = 1000,
410  .max_step = 5,
411  .relative = 1,
412  .try_removing = 0,
413  .finalize = 1,
414  };
415  DO_N(300,check_randomized(&cfg2b));
416 
417  struct rand_cfg cfg2c = {
418  .min_timeout = 20,
419  .max_timeout = 1000,
420  .start_at = 10,
421  .end_at = 100,
422  .n_timeouts = 1000,
423  .max_step = 5,
424  .relative = 1,
425  .try_removing = 0,
426  .finalize = 0,
427  };
428  DO_N(300,check_randomized(&cfg2c));
429 
430  struct rand_cfg cfg3 = {
431  .min_timeout = 2000,
432  .max_timeout = ((uint64_t)1) << 50,
433  .start_at = 100,
434  .end_at = ((uint64_t)1) << 49,
435  .n_timeouts = 1000,
436  .max_step = 1<<31,
437  .relative = 0,
438  .try_removing = 0,
439  .finalize = 2,
440  };
441  DO_N(10,check_randomized(&cfg3));
442 
443  struct rand_cfg cfg3b = {
444  .min_timeout = ((uint64_t)1) << 50,
445  .max_timeout = ((uint64_t)1) << 52,
446  .start_at = 100,
447  .end_at = ((uint64_t)1) << 53,
448  .n_timeouts = 1000,
449  .max_step = ((uint64_t)1)<<48,
450  .relative = 0,
451  .try_removing = 0,
452  .finalize = 2,
453  };
454  DO_N(10,check_randomized(&cfg3b));
455 
456  struct rand_cfg cfg4 = {
457  .min_timeout = 2000,
458  .max_timeout = ((uint64_t)1) << 30,
459  .start_at = 100,
460  .end_at = ((uint64_t)1) << 26,
461  .n_timeouts = 10000,
462  .max_step = 1<<16,
463  .relative = 0,
464  .try_removing = 3,
465  .finalize = 2,
466  };
467  DO_N(10,check_randomized(&cfg4));
468 
469  const timeout_t primes[] = {
470  2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,
471  59,61,67,71,73,79,83,89,97
472  };
473  const timeout_t factors_of_1337[] = {
474  1, 7, 191, 1337
475  };
476  const timeout_t multiples_of_five[] = {
477  5, 10, 15, 20, 25, 30, 35, 40, 45, 50
478  };
479 
480  struct intervals_cfg icfg1 = {
481  .timeouts = primes,
482  .n_timeouts = sizeof(primes)/sizeof(timeout_t),
483  .start_at = 50,
484  .end_at = 5322,
485  .skip = 0,
486  };
487  DO(check_intervals(&icfg1));
488 
489  struct intervals_cfg icfg2 = {
490  .timeouts = factors_of_1337,
491  .n_timeouts = sizeof(factors_of_1337)/sizeof(timeout_t),
492  .start_at = 50,
493  .end_at = 50000,
494  .skip = 0,
495  };
496  DO(check_intervals(&icfg2));
497 
498  struct intervals_cfg icfg3 = {
499  .timeouts = multiples_of_five,
500  .n_timeouts = sizeof(multiples_of_five)/sizeof(timeout_t),
501  .start_at = 49,
502  .end_at = 5333,
503  .skip = 0,
504  };
505  DO(check_intervals(&icfg3));
506 
507  struct intervals_cfg icfg4 = {
508  .timeouts = primes,
509  .n_timeouts = sizeof(primes)/sizeof(timeout_t),
510  .start_at = 50,
511  .end_at = 5322,
512  .skip = 16,
513  };
514  DO(check_intervals(&icfg4));
515 
516  if (n_failed) {
517  puts("\nFAIL");
518  } else {
519  puts("\nOK");
520  }
521  return !!n_failed;
522 }
523 
524 /* TODO:
525 
526  * Solve PR#3.
527 
528  * Investigate whether any untaken branches are possible.
529 
530  */
timeouts
Definition: timeout.c:215
rand_cfg
Definition: test-timeout.c:49
timeouts_it
Definition: timeout.h:216
timeout
Definition: timeout.h:115
main
int main(int argc, char *argv[])
Definition: tor_main.c:25
intervals_cfg
Definition: test-timeout.c:273