91f46393958acef5b6e9dc10968f14344b35ab5d
[ccan] / ccan / timer / timer.c
1 /* LGPL (v2.1 or any later version) - see LICENSE file for details */
2 #include <ccan/timer/timer.h>
3 #include <ccan/array_size/array_size.h>
4 #include <ccan/ilog/ilog.h>
5 #include <ccan/likely/likely.h>
6 #include <stdlib.h>
7 #include <stdio.h>
8
9 #define PER_LEVEL (1ULL << TIMER_LEVEL_BITS)
10
11 struct timer_level {
12         struct list_head list[PER_LEVEL];
13 };
14
15 static uint64_t time_to_grains(struct timemono t)
16 {
17         return t.ts.tv_sec * ((uint64_t)1000000000 / TIMER_GRANULARITY)
18                 + (t.ts.tv_nsec / TIMER_GRANULARITY);
19 }
20
21 static struct timemono grains_to_time(uint64_t grains)
22 {
23         struct timemono t;
24
25         t.ts.tv_sec = grains / (1000000000 / TIMER_GRANULARITY);
26         t.ts.tv_nsec = (grains % (1000000000 / TIMER_GRANULARITY))
27                 * TIMER_GRANULARITY;
28         return t;
29 }
30
31 void timers_init(struct timers *timers, struct timemono start)
32 {
33         unsigned int i;
34
35         list_head_init(&timers->far);
36         timers->base = time_to_grains(start);
37         timers->first = -1ULL;
38         memset(timers->firsts, 0xFF, sizeof(timers->firsts));
39         for (i = 0; i < ARRAY_SIZE(timers->level); i++)
40                 timers->level[i] = NULL;
41 }
42
43 static unsigned int level_of(const struct timers *timers, uint64_t time)
44 {
45         uint64_t diff;
46
47         /* Level depends how far away it is. */
48         diff = time - timers->base;
49         return ilog64(diff / 2) / TIMER_LEVEL_BITS;
50 }
51
52 static void timer_add_raw(struct timers *timers, struct timer *t)
53 {
54         struct list_head *l;
55         unsigned int level = level_of(timers, t->time);
56         uint64_t *first;
57
58         if (!timers->level[level]) {
59                 l = &timers->far;
60                 first = &timers->firsts[ARRAY_SIZE(timers->level)];
61         } else {
62                 int off = (t->time >> (level*TIMER_LEVEL_BITS)) & (PER_LEVEL-1);
63                 l = &timers->level[level]->list[off];
64                 first = &timers->firsts[level];
65         }
66
67         list_add_tail(l, &t->list);
68         if (t->time < *first)
69                 *first = t->time;
70 }
71
72 void timer_init(struct timer *t)
73 {
74         list_node_init(&t->list);
75 }
76
77 static bool list_node_initted(const struct list_node *n)
78 {
79         return n->prev == n;
80 }
81
82 void timer_addrel(struct timers *timers, struct timer *t, struct timerel rel)
83 {
84         assert(list_node_initted(&t->list));
85
86         t->time = time_to_grains(timemono_add(time_mono(), rel));
87
88 #if TIME_HAVE_MONOTONIC
89         assert(t->time >= timers->base);
90 #else
91         /* Added in the past?  Treat it as imminent. */
92         if (t->time < timers->base)
93                 t->time = timers->base;
94 #endif
95         if (t->time < timers->first)
96                 timers->first = t->time;
97
98         timer_add_raw(timers, t);
99 }
100
101 void timer_addmono(struct timers *timers, struct timer *t, struct timemono when)
102 {
103         assert(list_node_initted(&t->list));
104
105         t->time = time_to_grains(when);
106
107         /* Added in the past?  Treat it as imminent. */
108         if (t->time < timers->base)
109                 t->time = timers->base;
110         if (t->time < timers->first)
111                 timers->first = t->time;
112
113         timer_add_raw(timers, t);
114 }
115
116 /* FIXME: inline */
117 void timer_del(struct timers *timers UNNEEDED, struct timer *t)
118 {
119         list_del_init(&t->list);
120 }
121
122 static void timers_far_get(struct timers *timers,
123                            struct list_head *list,
124                            uint64_t when)
125 {
126         struct timer *i, *next;
127
128         list_for_each_safe(&timers->far, i, next, list) {
129                 if (i->time <= when) {
130                         list_del_from(&timers->far, &i->list);
131                         list_add_tail(list, &i->list);
132                 }
133         }
134 }
135
136 static void add_level(struct timers *timers, unsigned int level)
137 {
138         struct timer_level *l;
139         struct timer *t;
140         unsigned int i;
141         struct list_head from_far;
142
143         l = malloc(sizeof(*l));
144         if (!l)
145                 return;
146
147         for (i = 0; i < ARRAY_SIZE(l->list); i++)
148                 list_head_init(&l->list[i]);
149         timers->level[level] = l;
150
151         list_head_init(&from_far);
152         timers_far_get(timers, &from_far,
153                        timers->base + (1ULL << ((level+1)*TIMER_LEVEL_BITS)) - 1);
154
155         while ((t = list_pop(&from_far, struct timer, list)) != NULL)
156                 timer_add_raw(timers, t);
157 }
158
159 /* We don't need to search past the first at level 0, since the
160  * bucket range is 1; they're all the same. */
161 static const struct timer *find_first(const struct list_head *list,
162                                       unsigned int level,
163                                       const struct timer *prev)
164 {
165         struct timer *t;
166
167         list_for_each(list, t, list) {
168                 if (!prev || t->time < prev->time)
169                         prev = t;
170                 if (level == 0)
171                         break;
172         }
173         return prev;
174 }
175
176 /* Update level's first watermark, and return overall first. */
177 static const struct timer *first_for_level(struct timers *timers,
178                                            size_t level,
179                                            const struct timer *level_first,
180                                            const struct timer *first)
181 {
182         if (level_first) {
183                 timers->firsts[level] = level_first->time;
184                 if (!first || level_first->time < first->time)
185                         first = level_first;
186         } else {
187                 timers->firsts[level] = -1ULL;
188         }
189         return first;
190 }
191
192 static bool level_may_beat(const struct timers *timers, size_t level,
193                            const struct timer *first)
194 {
195         return !first || timers->firsts[level] < first->time;
196 }
197
198 /* FIXME: Suboptimal */
199 static const struct timer *brute_force_first(struct timers *timers)
200 {
201         unsigned int l, i;
202         const struct timer *found = NULL;
203
204         for (l = 0; l < ARRAY_SIZE(timers->level) && timers->level[l]; l++) {
205                 const struct timer *t = NULL;
206
207                 /* Do we know they don't have a better one? */
208                 if (!level_may_beat(timers, l, found))
209                         continue;
210
211                 /* Find first timer on this level. */
212                 for (i = 0; i < PER_LEVEL; i++)
213                         t = find_first(&timers->level[l]->list[i], l, t);
214
215                 found = first_for_level(timers, l, t, found);
216         }
217
218         /* Check (and update) far list if there's a chance. */
219         l = ARRAY_SIZE(timers->level);
220         if (level_may_beat(timers, l, found)) {
221                 const struct timer *t = find_first(&timers->far, l, NULL);
222                 found = first_for_level(timers, l, t, found);
223         }
224
225         return found;
226 }
227
228 static const struct timer *get_first(struct timers *timers)
229 {
230         /* We can have just far timers, for example. */
231         if (timers->level[0]) {
232                 /* First search rest of lower buckets; we've already spilled
233                  * so if we find one there we don't need to search further. */
234                 unsigned int i, off = timers->base % PER_LEVEL;
235
236                 for (i = off; i < PER_LEVEL; i++) {
237                         struct list_head *h = &timers->level[0]->list[i];
238                         if (!list_empty(h))
239                                 return find_first(h, 0, NULL);
240                 }
241         }
242
243         /* From here on, we're searching non-normalized parts of the
244          * data structure, which is much subtler.
245          *
246          * So we brute force. */
247         return brute_force_first(timers);
248 }
249
250 static bool update_first(struct timers *timers)
251 {
252         const struct timer *found = get_first(timers);
253
254         if (!found) {
255                 timers->first = -1ULL;
256                 return false;
257         }
258
259         timers->first = found->time;
260         return true;
261 }
262
263 bool timer_earliest(struct timers *timers, struct timemono *first)
264 {
265         if (!update_first(timers))
266                 return false;
267
268         *first = grains_to_time(timers->first);
269         return true;
270 }
271
272 /* Assume no timers before 'time', cascade down and update base time. */
273 static void timer_fast_forward(struct timers *timers, uint64_t time)
274 {
275         unsigned int level, changed;
276         int need_level = -1;
277         struct list_head list;
278         struct timer *i;
279
280         /* How many bits changed between base and time?
281          * Each time we wrap, we need to empty buckets from above. */
282         if (time == timers->base)
283                 return;
284
285         changed = ilog64_nz(time ^ timers->base);
286         level = (changed - 1) / TIMER_LEVEL_BITS;
287
288         /* Buckets always empty downwards, so we could cascade manually,
289          * but it's rarely very many so we just remove and re-add */
290         list_head_init(&list);
291
292         do {
293                 if (!timers->level[level]) {
294                         /* We need any which belong on this level. */
295                         timers_far_get(timers, &list,
296                                        timers->base
297                                        + (1ULL << ((level+1)*TIMER_LEVEL_BITS))-1);
298                         need_level = level;
299                 } else {
300                         unsigned src;
301
302                         /* Get all timers from this bucket. */
303                         src = (time >> (level * TIMER_LEVEL_BITS)) % PER_LEVEL;
304                         list_append_list(&list,
305                                          &timers->level[level]->list[src]);
306                 }
307         } while (level--);
308
309         /* Did we hit the last level?  If so, add. */
310         if (need_level != -1)
311                 add_level(timers, need_level);
312
313         /* Fast-forward the time, and re-add everyone. */
314         timers->base = time;
315         while ((i = list_pop(&list, struct timer, list)) != NULL)
316                 timer_add_raw(timers, i);
317 }
318
319 /* Returns an expired timer. */
320 struct timer *timers_expire(struct timers *timers, struct timemono expire)
321 {
322         uint64_t now = time_to_grains(expire);
323         unsigned int off;
324         struct timer *t;
325
326         assert(now >= timers->base);
327
328         if (!timers->level[0]) {
329                 if (list_empty(&timers->far))
330                         return NULL;
331                 add_level(timers, 0);
332         }
333
334         do {
335                 if (timers->first > now) {
336                         timer_fast_forward(timers, now);
337                         return NULL;
338                 }
339
340                 timer_fast_forward(timers, timers->first);
341                 off = timers->base % PER_LEVEL;
342
343                 /* This *may* be NULL, if we deleted the first timer */
344                 t = list_pop(&timers->level[0]->list[off], struct timer, list);
345                 if (t)
346                         list_node_init(&t->list);
347         } while (!t && update_first(timers));
348
349         return t;
350 }
351
352 static bool timer_list_check(const struct list_head *l,
353                              uint64_t min, uint64_t max, uint64_t first,
354                              const char *abortstr)
355 {
356         const struct timer *t;
357
358         if (!list_check(l, abortstr))
359                 return false;
360
361         list_for_each(l, t, list) {
362                 if (t->time < min || t->time > max) {
363                         if (abortstr) {
364                                 fprintf(stderr,
365                                         "%s: timer %p %llu not %llu-%llu\n",
366                                         abortstr, t, (long long)t->time,
367                                         (long long)min, (long long)max);
368                                 abort();
369                         }
370                         return false;
371                 }
372                 if (t->time < first) {
373                         if (abortstr) {
374                                 fprintf(stderr,
375                                         "%s: timer %p %llu < minimum %llu\n",
376                                         abortstr, t, (long long)t->time,
377                                         (long long)first);
378                                 abort();
379                         }
380                         return false;
381                 }
382         }
383         return true;
384 }
385
386 struct timers *timers_check(const struct timers *timers, const char *abortstr)
387 {
388         unsigned int l, i, off;
389         uint64_t base;
390
391         l = 0;
392         if (!timers->level[0])
393                 goto past_levels;
394
395         /* First level is simple. */
396         off = timers->base % PER_LEVEL;
397         for (i = 0; i < PER_LEVEL; i++) {
398                 struct list_head *h;
399
400                 h = &timers->level[l]->list[(i+off) % PER_LEVEL];
401                 if (!timer_list_check(h, timers->base + i, timers->base + i,
402                                       timers->firsts[l], abortstr))
403                         return NULL;
404         }
405
406         /* For other levels, "current" bucket has been emptied, and may contain
407          * entries for the current + level_size bucket. */
408         for (l = 1; l < ARRAY_SIZE(timers->level) && timers->level[l]; l++) {
409                 uint64_t per_bucket = 1ULL << (TIMER_LEVEL_BITS * l);
410
411                 off = ((timers->base >> (l*TIMER_LEVEL_BITS)) % PER_LEVEL);
412                 /* We start at *next* bucket. */
413                 base = (timers->base & ~(per_bucket - 1)) + per_bucket;
414
415                 for (i = 1; i <= PER_LEVEL; i++) {
416                         struct list_head *h;
417
418                         h = &timers->level[l]->list[(i+off) % PER_LEVEL];
419                         if (!timer_list_check(h, base, base + per_bucket - 1,
420                                               timers->firsts[l], abortstr))
421                                 return NULL;
422                         base += per_bucket;
423                 }
424         }
425
426 past_levels:
427         base = (timers->base & ~((1ULL << (TIMER_LEVEL_BITS * l)) - 1))
428                 + (1ULL << (TIMER_LEVEL_BITS * l)) - 1;
429         if (!timer_list_check(&timers->far, base, -1ULL,
430                               timers->firsts[ARRAY_SIZE(timers->level)],
431                               abortstr))
432                 return NULL;
433
434         return (struct timers *)timers;
435 }
436
437 #ifdef CCAN_TIMER_DEBUG
438 static void dump_bucket_stats(FILE *fp, const struct list_head *h)
439 {
440         unsigned long long min, max, num;
441         struct timer *t;
442
443         if (list_empty(h)) {
444                 printf("\n");
445                 return;
446         }
447
448         min = -1ULL;
449         max = 0;
450         num = 0;
451         list_for_each(h, t, list) {
452                 if (t->time < min)
453                         min = t->time;
454                 if (t->time > max)
455                         max = t->time;
456                 num++;
457         }
458         fprintf(fp, " %llu (%llu-%llu)\n",
459                 num, min, max);
460 }
461
462 void timers_dump(const struct timers *timers, FILE *fp)
463 {
464         unsigned int l, i, off;
465         unsigned long long base;
466
467         if (!fp)
468                 fp = stderr;
469
470         fprintf(fp, "Base: %llu\n", (unsigned long long)timers->base);
471
472         if (!timers->level[0])
473                 goto past_levels;
474
475         fprintf(fp, "Level 0:\n");
476
477         /* First level is simple. */
478         off = timers->base % PER_LEVEL;
479         for (i = 0; i < PER_LEVEL; i++) {
480                 const struct list_head *h;
481
482                 fprintf(fp, "  Bucket %llu (%lu):",
483                         (i+off) % PER_LEVEL, timers->base + i);
484                 h = &timers->level[0]->list[(i+off) % PER_LEVEL];
485                 dump_bucket_stats(fp, h);
486         }
487
488         /* For other levels, "current" bucket has been emptied, and may contain
489          * entries for the current + level_size bucket. */
490         for (l = 1; l < ARRAY_SIZE(timers->level) && timers->level[l]; l++) {
491                 uint64_t per_bucket = 1ULL << (TIMER_LEVEL_BITS * l);
492
493                 off = ((timers->base >> (l*TIMER_LEVEL_BITS)) % PER_LEVEL);
494                 /* We start at *next* bucket. */
495                 base = (timers->base & ~(per_bucket - 1)) + per_bucket;
496
497                 fprintf(fp, "Level %u:\n", l);
498                 for (i = 1; i <= PER_LEVEL; i++) {
499                         const struct list_head *h;
500
501                         fprintf(fp, "  Bucket %llu (%llu - %llu):",
502                                 (i+off) % PER_LEVEL,
503                                 base, base + per_bucket - 1);
504
505                         h = &timers->level[l]->list[(i+off) % PER_LEVEL];
506                         dump_bucket_stats(fp, h);
507                         base += per_bucket;
508                 }
509         }
510
511 past_levels:
512         if (!list_empty(&timers->far)) {
513                 fprintf(fp, "Far timers:");
514                 dump_bucket_stats(fp, &timers->far);
515         }
516 }
517 #endif
518
519 void timers_cleanup(struct timers *timers)
520 {
521         unsigned int l;
522
523         for (l = 0; l < ARRAY_SIZE(timers->level); l++)
524                 free(timers->level[l]);
525 }