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