Merge branch 'master' into scheduler_cleanup
[olsrd.git] / src / olsr_timer.c
1 /*
2  * olsr_timer.c
3  *
4  *  Created on: Feb 14, 2011
5  *      Author: rogge
6  */
7
8 #include <unistd.h>
9 #include <assert.h>
10 #include <stdlib.h>
11
12 #include "common/avl.h"
13 #include "common/avl_olsr_comp.h"
14 #include "olsr.h"
15 #include "olsr_logging.h"
16 #include "olsr_memcookie.h"
17 #include "olsr_socket.h"
18 #include "os_time.h"
19 #include "olsr_timer.h"
20
21 /* Timer data */
22 static uint32_t now_times;             /* relative time compared to startup (in milliseconds */
23 static struct timeval first_tv;        /* timevalue during startup */
24 static struct timeval last_tv;         /* timevalue used for last olsr_times() calculation */
25
26 /* Hashed root of all timers */
27 static struct list_entity timer_wheel[TIMER_WHEEL_SLOTS];
28 static uint32_t timer_last_run;        /* remember the last timeslot walk */
29
30 /* Memory cookie for the timer manager */
31 struct list_entity timerinfo_list;
32 static struct olsr_memcookie_info *timer_mem_cookie = NULL;
33 static struct olsr_memcookie_info *timerinfo_cookie = NULL;
34
35 /* Prototypes */
36 static void walk_timers(uint32_t *);
37 static uint32_t calc_jitter(unsigned int rel_time, uint8_t jitter_pct, unsigned int random_val);
38 static int olsr_get_timezone(void);
39
40 /**
41  * Init datastructures for maintaining timers.
42  */
43 void
44 olsr_timer_init(void)
45 {
46   int idx;
47
48   OLSR_INFO(LOG_SCHEDULER, "Initializing scheduler.\n");
49
50   /* Grab initial timestamp */
51   if (os_gettimeofday(&first_tv, NULL)) {
52     OLSR_ERROR(LOG_TIMER, "OS clock is not working, have to shut down OLSR (%s)\n", strerror(errno));
53     olsr_exit(1);
54   }
55   last_tv = first_tv;
56   olsr_timer_updateClock();
57
58   /* init lists */
59   for (idx = 0; idx < TIMER_WHEEL_SLOTS; idx++) {
60     list_init_head(&timer_wheel[idx]);
61   }
62
63   /*
64    * Reset the last timer run.
65    */
66   timer_last_run = now_times;
67
68   /* Allocate a cookie for the block based memory manager. */
69   timer_mem_cookie = olsr_memcookie_add("timer_entry", sizeof(struct olsr_timer_entry));
70
71   list_init_head(&timerinfo_list);
72   timerinfo_cookie = olsr_memcookie_add("timerinfo", sizeof(struct olsr_timer_info));
73 }
74
75 /**
76  * Cleanup timer scheduler, this stops and deletes all timers
77  */
78 void
79 olsr_timer_cleanup(void)
80 {
81   struct olsr_timer_info *ti, *iterator;
82
83   struct list_entity *timer_head_node;
84   unsigned int wheel_slot = 0;
85
86   for (wheel_slot = 0; wheel_slot < TIMER_WHEEL_SLOTS; wheel_slot++) {
87     timer_head_node = &timer_wheel[wheel_slot & TIMER_WHEEL_MASK];
88
89     /* Kill all entries hanging off this hash bucket. */
90     while (!list_is_empty(timer_head_node)) {
91       struct olsr_timer_entry *timer;
92
93       timer = list_first_element(timer_head_node, timer, timer_list);
94       olsr_timer_stop(timer);
95     }
96   }
97
98   /* free all timerinfos */
99   OLSR_FOR_ALL_TIMERS(ti, iterator) {
100     list_remove(&ti->node);
101     free(ti->name);
102     olsr_memcookie_free(timerinfo_cookie, ti);
103   }
104
105   /* release memory cookie for timers */
106   olsr_memcookie_remove(timerinfo_cookie);
107 }
108
109 /**
110  * Update the internal clock to current system time
111  */
112 void
113 olsr_timer_updateClock(void)
114 {
115   struct timeval tv;
116   uint32_t t;
117
118   if (os_gettimeofday(&tv, NULL) != 0) {
119     OLSR_ERROR(LOG_SCHEDULER, "OS clock is not working, have to shut down OLSR (%s)\n", strerror(errno));
120     olsr_exit(1);
121   }
122
123   /* test if time jumped backward or more than 60 seconds forward */
124   if (tv.tv_sec < last_tv.tv_sec || (tv.tv_sec == last_tv.tv_sec && tv.tv_usec < last_tv.tv_usec)
125       || tv.tv_sec - last_tv.tv_sec > 60) {
126     OLSR_WARN(LOG_SCHEDULER, "Time jump (%d.%06d to %d.%06d)\n",
127               (int32_t) (last_tv.tv_sec), (int32_t) (last_tv.tv_usec), (int32_t) (tv.tv_sec), (int32_t) (tv.tv_usec));
128
129     t = (last_tv.tv_sec - first_tv.tv_sec) * 1000 + (last_tv.tv_usec - first_tv.tv_usec) / 1000;
130     t++;                        /* advance time by one millisecond */
131
132     first_tv = tv;
133     first_tv.tv_sec -= (t / 1000);
134     first_tv.tv_usec -= ((t % 1000) * 1000);
135
136     if (first_tv.tv_usec < 0) {
137       first_tv.tv_sec--;
138       first_tv.tv_usec += 1000000;
139     }
140     last_tv = tv;
141     now_times =  t;
142   }
143   last_tv = tv;
144   now_times = (tv.tv_sec - first_tv.tv_sec) * 1000 + (tv.tv_usec - first_tv.tv_usec) / 1000;
145 }
146
147 /**
148  * Returns a timestamp s seconds in the future
149  * @param s milliseconds until timestamp
150  * @return absolute time when event will happen
151  */
152 uint32_t
153 olsr_timer_getAbsolute(uint32_t relative)
154 {
155   return now_times + relative;
156 }
157
158 /**
159  * Returns the number of milliseconds until the timestamp will happen
160  * @param absolute timestamp
161  * @return milliseconds until event will happen, negative if it already
162  *   happened.
163  */
164 int32_t
165 olsr_timer_getRelative(uint32_t absolute)
166 {
167   uint32_t diff;
168   if (absolute > now_times) {
169     diff = absolute - now_times;
170
171     /* overflow ? */
172     if (diff > (1u << 31)) {
173       return -(int32_t) (0xffffffff - diff);
174     }
175     return (int32_t) (diff);
176   }
177
178   diff = now_times - absolute;
179   /* overflow ? */
180   if (diff > (1u << 31)) {
181     return (int32_t) (0xffffffff - diff);
182   }
183   return -(int32_t) (diff);
184 }
185
186 /**
187  * Checks if a timestamp has already happened
188  * @param absolute timestamp
189  * @return true if the event already happened, false otherwise
190  */
191 bool
192 olsr_timer_isTimedOut(uint32_t absolute)
193 {
194   if (absolute > now_times) {
195     return absolute - now_times > (1u << 31);
196   }
197
198   return now_times - absolute <= (1u << 31);
199 }
200
201 /**
202  * Add a new group of timers to the scheduler
203  * @param name
204  * @param callback timer event function
205  * @param periodic true if the timer is periodic, false otherwise
206  * @return new timer info
207  */
208 struct olsr_timer_info *
209 olsr_timer_add(const char *name, timer_cb_func callback, bool periodic) {
210   struct olsr_timer_info *ti;
211
212   ti = olsr_memcookie_malloc(timerinfo_cookie);
213   ti->name = strdup(name);
214   ti->callback = callback;
215   ti->periodic = periodic;
216
217   list_add_tail(&timerinfo_list, &ti->node);
218   return ti;
219 }
220
221 /**
222  * Main timer scheduler event loop.
223  * Will call socket scheduler and olsr_process_changes()
224  */
225 void
226 olsr_timer_scheduler(void)
227 {
228   OLSR_INFO(LOG_SCHEDULER, "Scheduler started - polling every %u ms\n", olsr_cnf->pollrate);
229
230   /* Main scheduler loop */
231   while (app_state == STATE_RUNNING) {
232     uint32_t next_interval;
233
234     /*
235      * Update the global timestamp. We are using a non-wallclock timer here
236      * to avoid any undesired side effects if the system clock changes.
237      */
238     olsr_timer_updateClock();
239     next_interval = olsr_timer_getAbsolute(olsr_cnf->pollrate);
240
241     /* Process timers */
242     walk_timers(&timer_last_run);
243
244     /* Update */
245     olsr_process_changes();
246
247     /* Read incoming data and handle it immediately */
248     handle_sockets(next_interval);
249   }
250 }
251
252 /**
253  * Format an absolute wallclock system time string.
254  * May be called upto 4 times in a single printf() statement.
255  * Displays microsecond resolution.
256  *
257  * @return buffer to a formatted system time string.
258  */
259 const char *
260 olsr_timer_getWallclockString(struct timeval_buf *buf)
261 {
262   struct timeval now;
263   int sec, usec;
264
265   os_gettimeofday(&now, NULL);
266
267   sec = (int)now.tv_sec + olsr_get_timezone();
268   usec = (int)now.tv_usec;
269
270   snprintf(buf->buf, sizeof(buf), "%02d:%02d:%02d.%06d",
271       (sec % 86400) / 3600, (sec % 3600) / 60, sec % 60, usec);
272
273   return buf->buf;
274 }
275
276 /**
277  * Format an relative non-wallclock system time string.
278  * Displays millisecond resolution.
279  *
280  * @param absolute timestamp
281  * @return buffer to a formatted system time string.
282  */
283 const char *
284 olsr_timer_getClockString(struct timeval_buf *buf, uint32_t clk)
285 {
286   unsigned int msec = clk % 1000;
287   unsigned int sec = clk / 1000;
288
289   snprintf(buf->buf, sizeof(buf),
290       "%02u:%02u:%02u.%03u", sec / 3600, (sec % 3600) / 60, (sec % 60), (msec % MSEC_PER_SEC));
291
292   return buf->buf;
293 }
294
295 /**
296  * Start a new timer.
297  *
298  * @param relative time expressed in milliseconds
299  * @param jitter expressed in percent
300  * @param timer callback function
301  * @param context for the callback function
302  * @return a pointer to the created entry
303  */
304 struct olsr_timer_entry *
305 olsr_timer_start(unsigned int rel_time,
306                  uint8_t jitter_pct, void *context, struct olsr_timer_info *ti)
307 {
308   struct olsr_timer_entry *timer;
309 #if !defined(REMOVE_LOG_DEBUG)
310   struct timeval_buf timebuf;
311 #endif
312
313   assert(ti != 0);          /* we want timer cookies everywhere */
314   assert(rel_time);
315   assert(jitter_pct <= 100);
316
317   timer = olsr_memcookie_malloc(timer_mem_cookie);
318
319   /*
320    * Compute random numbers only once.
321    */
322   if (!timer->timer_random) {
323     timer->timer_random = random();
324   }
325
326   /* Fill entry */
327   timer->timer_clock = calc_jitter(rel_time, jitter_pct, timer->timer_random);
328   timer->timer_cb_context = context;
329   timer->timer_jitter_pct = jitter_pct;
330   timer->timer_running = true;
331
332   /* The cookie is used for debugging to traceback the originator */
333   timer->timer_info = ti;
334   ti->usage++;
335   ti->changes++;
336
337   /* Singleshot or periodical timer ? */
338   timer->timer_period = ti->periodic ? rel_time : 0;
339
340   /*
341    * Now insert in the respective timer_wheel slot.
342    */
343   list_add_before(&timer_wheel[timer->timer_clock & TIMER_WHEEL_MASK], &timer->timer_list);
344
345   OLSR_DEBUG(LOG_TIMER, "TIMER: start %s timer %p firing in %s, ctx %p\n",
346              ti->name, timer, olsr_timer_getClockString(&timebuf, timer->timer_clock), context);
347
348   return timer;
349 }
350
351 /**
352  * Delete a timer.
353  *
354  * @param the olsr_timer_entry that shall be removed
355  * @return nada
356  */
357 void
358 olsr_timer_stop(struct olsr_timer_entry *timer)
359 {
360   /* It's okay to get a NULL here */
361   if (timer == NULL) {
362     return;
363   }
364
365   assert(timer->timer_info);     /* we want timer cookies everywhere */
366   assert(timer->timer_list.next != NULL && timer->timer_list.prev != NULL);
367
368   OLSR_DEBUG(LOG_TIMER, "TIMER: stop %s timer %p, ctx %p\n",
369              timer->timer_info->name, timer, timer->timer_cb_context);
370
371
372   /*
373    * Carve out of the existing wheel_slot and free.
374    */
375   list_remove(&timer->timer_list);
376   timer->timer_running = false;
377   timer->timer_info->usage--;
378   timer->timer_info->changes++;
379
380   if (!timer->timer_in_callback) {
381     olsr_memcookie_free(timer_mem_cookie, timer);
382   }
383 }
384
385 /**
386  * Change a olsr_timer_entry.
387  *
388  * @param olsr_timer_entry to be changed.
389  * @param new relative time expressed in units of milliseconds.
390  * @param new jitter expressed in percent.
391  * @return nada
392  */
393 void
394 olsr_timer_change(struct olsr_timer_entry *timer, unsigned int rel_time, uint8_t jitter_pct)
395 {
396 #if !defined(REMOVE_LOG_DEBUG)
397   struct timeval_buf timebuf;
398 #endif
399
400   /* Sanity check. */
401   if (!timer) {
402     return;
403   }
404
405   assert(timer->timer_info);     /* we want timer cookies everywhere */
406
407   /* Singleshot or periodical timer ? */
408   timer->timer_period = timer->timer_info->periodic ? rel_time : 0;
409
410   timer->timer_clock = calc_jitter(rel_time, jitter_pct, timer->timer_random);
411   timer->timer_jitter_pct = jitter_pct;
412
413   /*
414    * Changes are easy: Remove timer from the exisiting timer_wheel slot
415    * and reinsert into the new slot.
416    */
417   list_remove(&timer->timer_list);
418   list_add_before(&timer_wheel[timer->timer_clock & TIMER_WHEEL_MASK], &timer->timer_list);
419
420   OLSR_DEBUG(LOG_TIMER, "TIMER: change %s timer %p, firing to %s, ctx %p\n",
421              timer->timer_info->name, timer,
422              olsr_timer_getClockString(&timebuf, timer->timer_clock), timer->timer_cb_context);
423 }
424
425 /*
426  * This is the one stop shop for all sort of timer manipulation.
427  * Depending on the paseed in parameters a new timer is started,
428  * or an existing timer is started or an existing timer is
429  * terminated.
430  */
431 void
432 olsr_timer_set(struct olsr_timer_entry **timer_ptr,
433                unsigned int rel_time,
434                uint8_t jitter_pct, void *context, struct olsr_timer_info *ti)
435 {
436   assert(ti);          /* we want timer cookies everywhere */
437   if (rel_time == 0) {
438     /* No good future time provided, kill it. */
439     olsr_timer_stop(*timer_ptr);
440     *timer_ptr = NULL;
441   }
442   else if ((*timer_ptr) == NULL) {
443     /* No timer running, kick it. */
444     *timer_ptr = olsr_timer_start(rel_time, jitter_pct, context, ti);
445   }
446   else {
447     olsr_timer_change(*timer_ptr, rel_time, jitter_pct);
448   }
449 }
450
451 /**
452  * Decrement a relative timer by a random number range.
453  *
454  * @param the relative timer expressed in units of milliseconds.
455  * @param the jitter in percent
456  * @param cached result of random() at system init.
457  * @return the absolute timer
458  */
459 static uint32_t
460 calc_jitter(unsigned int rel_time, uint8_t jitter_pct, unsigned int random_val)
461 {
462   unsigned int jitter_time;
463
464   /*
465    * No jitter or, jitter larger than 99% does not make sense.
466    * Also protect against overflows resulting from > 25 bit timers.
467    */
468   if (jitter_pct == 0 || jitter_pct > 99 || rel_time > (1 << 24)) {
469     return olsr_timer_getAbsolute(rel_time);
470   }
471
472   /*
473    * Play some tricks to avoid overflows with integer arithmetic.
474    */
475   jitter_time = (jitter_pct * rel_time) / 100;
476   jitter_time = random_val / (1 + RAND_MAX / (jitter_time + 1));
477
478   OLSR_DEBUG(LOG_TIMER, "TIMER: jitter %u%% rel_time %ums to %ums\n", jitter_pct, rel_time, rel_time - jitter_time);
479
480   return olsr_timer_getAbsolute(rel_time - jitter_time);
481 }
482
483 /**
484  * Walk through the timer list and check if any timer is ready to fire.
485  * Callback the provided function with the context pointer.
486  */
487 static void
488 walk_timers(uint32_t * last_run)
489 {
490   unsigned int total_timers_walked = 0, total_timers_fired = 0;
491   unsigned int wheel_slot_walks = 0;
492
493   /*
494    * Check the required wheel slots since the last time a timer walk was invoked,
495    * or check *all* the wheel slots, whatever is less work.
496    * The latter is meant as a safety belt if the scheduler falls behind.
497    */
498   while ((*last_run <= now_times) && (wheel_slot_walks < TIMER_WHEEL_SLOTS)) {
499     struct list_entity tmp_head_node;
500     /* keep some statistics */
501     unsigned int timers_walked = 0, timers_fired = 0;
502
503     /* Get the hash slot for this clocktick */
504     struct list_entity *timer_head_node;
505
506     timer_head_node = &timer_wheel[*last_run & TIMER_WHEEL_MASK];
507
508     /* Walk all entries hanging off this hash bucket. We treat this basically as a stack
509      * so that we always know if and where the next element is.
510      */
511     list_init_head(&tmp_head_node);
512     while (!list_is_empty(timer_head_node)) {
513       /* the top element */
514       struct olsr_timer_entry *timer;
515
516       timer = list_first_element(timer_head_node, timer, timer_list);
517
518       /*
519        * Dequeue and insert to a temporary list.
520        * We do this to avoid loosing our walking context when
521        * multiple timers fire.
522        */
523       list_remove(&timer->timer_list);
524       list_add_after(&tmp_head_node, &timer->timer_list);
525       timers_walked++;
526
527       /* Ready to fire ? */
528       if (olsr_timer_isTimedOut(timer->timer_clock)) {
529 #if !defined(REMOVE_LOG_DEBUG)
530   struct timeval_buf timebuf;
531 #endif
532         OLSR_DEBUG(LOG_TIMER, "TIMER: fire %s timer %p, ctx %p, "
533                    "at clocktick %u (%s)\n",
534                    timer->timer_info->name,
535                    timer, timer->timer_cb_context, (unsigned int)*last_run,
536                    olsr_timer_getWallclockString(&timebuf));
537
538         /* This timer is expired, call into the provided callback function */
539         timer->timer_in_callback = true;
540         timer->timer_info->callback(timer->timer_cb_context);
541         timer->timer_in_callback = false;
542         timer->timer_info->changes++;
543
544         /* Only act on actually running timers */
545         if (timer->timer_running) {
546           /*
547            * Don't restart the periodic timer if the callback function has
548            * stopped the timer.
549            */
550           if (timer->timer_period) {
551             /* For periodical timers, rehash the random number and restart */
552             timer->timer_random = random();
553             olsr_timer_change(timer, timer->timer_period, timer->timer_jitter_pct);
554           } else {
555             /* Singleshot timers are stopped */
556             olsr_timer_stop(timer);
557           }
558         }
559         else {
560           /* free memory */
561           olsr_memcookie_free(timer_mem_cookie, timer);
562         }
563
564         timers_fired++;
565       }
566     }
567
568     /*
569      * Now merge the temporary list back to the old bucket.
570      */
571     list_merge(timer_head_node, &tmp_head_node);
572
573     /* keep some statistics */
574     total_timers_walked += timers_walked;
575     total_timers_fired += timers_fired;
576
577     /* Increment the time slot and wheel slot walk iteration */
578     (*last_run)++;
579     wheel_slot_walks++;
580   }
581
582   OLSR_DEBUG(LOG_TIMER, "TIMER: processed %4u/%d clockwheel slots, "
583              "timers walked %4u/%u, timers fired %u\n",
584              wheel_slot_walks, TIMER_WHEEL_SLOTS, total_timers_walked, timer_mem_cookie->ci_usage, total_timers_fired);
585
586   /*
587    * If the scheduler has slipped and we have walked all wheel slots,
588    * reset the last timer run.
589    */
590   *last_run = now_times;
591 }
592
593 /**
594  * Returns the difference between gmt and local time in seconds.
595  * Use gmtime() and localtime() to keep things simple.
596  *
597  * taken and slightly modified from www.tcpdump.org.
598  */
599 static int
600 olsr_get_timezone(void)
601 {
602 #define OLSR_TIMEZONE_UNINITIALIZED -1
603   static int time_diff = OLSR_TIMEZONE_UNINITIALIZED;
604   if (time_diff == OLSR_TIMEZONE_UNINITIALIZED) {
605     int dir;
606     const time_t t = time(NULL);
607     const struct tm gmt = *gmtime(&t);
608     const struct tm *loc = localtime(&t);
609
610     time_diff = (loc->tm_hour - gmt.tm_hour) * 60 * 60 + (loc->tm_min - gmt.tm_min) * 60;
611
612     /*
613      * If the year or julian day is different, we span 00:00 GMT
614      * and must add or subtract a day. Check the year first to
615      * avoid problems when the julian day wraps.
616      */
617     dir = loc->tm_year - gmt.tm_year;
618     if (!dir) {
619       dir = loc->tm_yday - gmt.tm_yday;
620     }
621
622     time_diff += dir * 24 * 60 * 60;
623   }
624   return time_diff;
625 }
626