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