?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Merge branch 'maint-0.4.8'
[tor.git] / src / ext / timeouts / test-timeout.c
blob52d2e31e0c5b71eb536e11aa91d643b7cb4da569
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
273 struct intervals_cfg {
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 */
The Onion Router