69bdfb2032ced9e634c31f1c34c3e2f2e4e1705b
[oonf.git] / src / core / olsr_timer.c
1
2 /*
3  * The olsr.org Optimized Link-State Routing daemon(olsrd)
4  * Copyright (c) 2004-2011, the olsr.org team - see HISTORY file
5  * All rights reserved.
6  *
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions
9  * are met:
10  *
11  * * Redistributions of source code must retain the above copyright
12  *   notice, this list of conditions and the following disclaimer.
13  * * Redistributions in binary form must reproduce the above copyright
14  *   notice, this list of conditions and the following disclaimer in
15  *   the documentation and/or other materials provided with the
16  *   distribution.
17  * * Neither the name of olsr.org, olsrd nor the names of its
18  *   contributors may be used to endorse or promote products derived
19  *   from this software without specific prior written permission.
20  *
21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
29  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
31  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
32  * POSSIBILITY OF SUCH DAMAGE.
33  *
34  * Visit http://www.olsr.org for more information.
35  *
36  * If you find this software useful feel free to make a donation
37  * to the project. For more information see the website or contact
38  * the copyright holders.
39  *
40  */
41
42 #include <assert.h>
43 #include <stdlib.h>
44 #include <string.h>
45 #include <unistd.h>
46
47 #include "common/avl.h"
48 #include "common/avl_comp.h"
49 #include "olsr_clock.h"
50 #include "olsr_logging.h"
51 #include "olsr_memcookie.h"
52 #include "olsr_timer.h"
53 #include "olsr.h"
54
55 /* Hashed root of all timers */
56 static struct list_entity timer_wheel[TIMER_WHEEL_SLOTS];
57 static uint32_t timer_last_run;        /* remember the last timeslot walk */
58
59 /* Memory cookie for the timer manager */
60 struct list_entity timerinfo_list;
61 static struct olsr_memcookie_info *timer_mem_cookie = NULL;
62 static struct olsr_memcookie_info *timerinfo_cookie = NULL;
63
64 /* remember if initialized or not */
65 OLSR_SUBSYSTEM_STATE(_timer_state);
66
67 /* Prototypes */
68 static uint32_t calc_jitter(unsigned int rel_time, uint8_t jitter_pct, unsigned int random_val);
69
70 /**
71  * Initialize timer scheduler subsystem
72  * @return -1 if an error happened, 0 otherwise
73  */
74 int
75 olsr_timer_init(void)
76 {
77   int idx;
78
79   if (olsr_subsystem_is_initialized(&_timer_state))
80     return 0;
81
82   OLSR_INFO(LOG_SOCKET, "Initializing scheduler.\n");
83
84   /* init lists */
85   for (idx = 0; idx < TIMER_WHEEL_SLOTS; idx++) {
86     list_init_head(&timer_wheel[idx]);
87   }
88
89   /*
90    * Reset the last timer run.
91    */
92   timer_last_run = olsr_clock_getNow();
93
94   /* Allocate a cookie for the block based memory manager. */
95   timer_mem_cookie = olsr_memcookie_add("timer_entry", sizeof(struct olsr_timer_entry));
96   if (timer_mem_cookie == NULL) {
97     OLSR_WARN_OOM(LOG_SOCKET);
98     return -1;
99   }
100
101   list_init_head(&timerinfo_list);
102   timerinfo_cookie = olsr_memcookie_add("timerinfo", sizeof(struct olsr_timer_info));
103   if (timerinfo_cookie == NULL) {
104     olsr_memcookie_remove(timer_mem_cookie);
105     return -1;
106   }
107
108   olsr_subsystem_init(&_timer_state);
109   return 0;
110 }
111
112 /**
113  * Cleanup timer scheduler, this stops and deletes all timers
114  */
115 void
116 olsr_timer_cleanup(void)
117 {
118   struct olsr_timer_info *ti, *iterator;
119   struct list_entity *timer_head_node;
120   unsigned int wheel_slot = 0;
121
122   if (olsr_subsystem_cleanup(&_timer_state))
123     return;
124
125   for (wheel_slot = 0; wheel_slot < TIMER_WHEEL_SLOTS; wheel_slot++) {
126     timer_head_node = &timer_wheel[wheel_slot & TIMER_WHEEL_MASK];
127
128     /* Kill all entries hanging off this hash bucket. */
129     while (!list_is_empty(timer_head_node)) {
130       struct olsr_timer_entry *timer;
131
132       timer = list_first_element(timer_head_node, timer, timer_list);
133       olsr_timer_stop(timer);
134     }
135   }
136
137   /* free all timerinfos */
138   OLSR_FOR_ALL_TIMERS(ti, iterator) {
139     list_remove(&ti->node);
140     free(ti->name);
141     olsr_memcookie_free(timerinfo_cookie, ti);
142   }
143
144   /* release memory cookie for timers */
145   olsr_memcookie_remove(timerinfo_cookie);
146 }
147
148 // TODO: remove malloc by using pointer to initialized timer_info?
149 /**
150  * Add a new group of timers to the scheduler
151  * @param name name of timer
152  * @param callback timer event function
153  * @param periodic true if the timer is periodic, false otherwise
154  * @return new timer info
155  */
156 struct olsr_timer_info *
157 olsr_timer_add(const char *name, timer_cb_func callback, bool periodic) {
158   struct olsr_timer_info *ti;
159
160   ti = olsr_memcookie_malloc(timerinfo_cookie);
161   if (ti == NULL) {
162     OLSR_WARN_OOM(LOG_MEMCOOKIE);
163     return NULL;
164   }
165   ti->name = strdup(name);
166   ti->callback = callback;
167   ti->periodic = periodic;
168
169   list_add_tail(&timerinfo_list, &ti->node);
170   return ti;
171 }
172
173 /**
174  * Removes a group of timers from the scheduler
175  * All pointers to timers of this timer_info will be invalid after this.
176  * @param info pointer to timer info
177  */
178 void
179 olsr_timer_remove(struct olsr_timer_info *info) {
180   struct olsr_timer_entry *timer, *iterator;
181   int slot;
182
183   for (slot=0; slot < TIMER_WHEEL_SLOTS; slot++) {
184     list_for_each_element_safe(&timer_wheel[slot], timer, timer_list, iterator) {
185       /* remove all timers of this timer_info */
186       if (timer->timer_info == info) {
187         olsr_timer_stop(timer);
188       }
189     }
190   }
191
192   list_remove(&info->node);
193   free (info->name);
194
195   olsr_memcookie_free(timerinfo_cookie, info);
196 }
197
198 /**
199  * Start a new timer.
200  * @param rel_time time expressed in milliseconds
201  * @param jitter_pct expressed in percent
202  * @param context for the callback function
203  * @param ti pointer to timer_info object
204  * @return a pointer to the created entry
205  */
206 struct olsr_timer_entry *
207 olsr_timer_start(unsigned int rel_time,
208     uint8_t jitter_pct, void *context, struct olsr_timer_info *ti)
209 {
210   struct olsr_timer_entry *timer;
211 #if !defined(REMOVE_LOG_DEBUG)
212   struct timeval_buf timebuf;
213 #endif
214
215   assert(ti != 0);          /* we want timer cookies everywhere */
216   assert(rel_time);
217   assert(jitter_pct <= 100);
218
219   timer = olsr_memcookie_malloc(timer_mem_cookie);
220
221   /*
222    * Compute random numbers only once.
223    */
224   if (!timer->timer_random) {
225     timer->timer_random = random();
226   }
227
228   /* Fill entry */
229   timer->timer_clock = calc_jitter(rel_time, jitter_pct, timer->timer_random);
230   timer->timer_cb_context = context;
231   timer->timer_jitter_pct = jitter_pct;
232   timer->timer_running = true;
233
234   /* The cookie is used for debugging to traceback the originator */
235   timer->timer_info = ti;
236   ti->usage++;
237   ti->changes++;
238
239   /* Singleshot or periodical timer ? */
240   timer->timer_period = ti->periodic ? rel_time : 0;
241
242   /*
243    * Now insert in the respective timer_wheel slot.
244    */
245   list_add_before(&timer_wheel[timer->timer_clock & TIMER_WHEEL_MASK], &timer->timer_list);
246
247   OLSR_DEBUG(LOG_TIMER, "TIMER: start %s timer %p firing in %s, ctx %p\n",
248              ti->name, timer, olsr_clock_toClockString(&timebuf, timer->timer_clock), context);
249
250   return timer;
251 }
252
253 /**
254  * Delete a timer.
255  * @param timer the olsr_timer_entry that shall be removed
256  */
257 void
258 olsr_timer_stop(struct olsr_timer_entry *timer)
259 {
260   /* It's okay to get a NULL here */
261   if (timer == NULL) {
262     return;
263   }
264
265   assert(timer->timer_info);     /* we want timer cookies everywhere */
266   assert(timer->timer_list.next != NULL && timer->timer_list.prev != NULL);
267
268   OLSR_DEBUG(LOG_TIMER, "TIMER: stop %s timer %p, ctx %p\n",
269              timer->timer_info->name, timer, timer->timer_cb_context);
270
271
272   /*
273    * Carve out of the existing wheel_slot and free.
274    */
275   list_remove(&timer->timer_list);
276   timer->timer_running = false;
277   timer->timer_info->usage--;
278   timer->timer_info->changes++;
279
280   if (!timer->timer_in_callback) {
281     olsr_memcookie_free(timer_mem_cookie, timer);
282   }
283 }
284
285 /**
286  * Change time when a timer should fire.
287  * @param timer olsr_timer_entry to be changed.
288  * @param rel_time new relative time expressed in units of milliseconds.
289  * @param jitter_pct new jitter expressed in percent.
290  */
291 void
292 olsr_timer_change(struct olsr_timer_entry *timer, unsigned int rel_time, uint8_t jitter_pct)
293 {
294 #if !defined(REMOVE_LOG_DEBUG)
295   struct timeval_buf timebuf;
296 #endif
297
298   /* Sanity check. */
299   if (!timer) {
300     return;
301   }
302
303   assert(timer->timer_info);     /* we want timer cookies everywhere */
304
305   /* Singleshot or periodical timer ? */
306   timer->timer_period = timer->timer_info->periodic ? rel_time : 0;
307
308   timer->timer_clock = calc_jitter(rel_time, jitter_pct, timer->timer_random);
309   timer->timer_jitter_pct = jitter_pct;
310
311   /*
312    * Changes are easy: Remove timer from the exisiting timer_wheel slot
313    * and reinsert into the new slot.
314    */
315   list_remove(&timer->timer_list);
316   list_add_before(&timer_wheel[timer->timer_clock & TIMER_WHEEL_MASK], &timer->timer_list);
317
318   OLSR_DEBUG(LOG_TIMER, "TIMER: change %s timer %p, firing to %s, ctx %p\n",
319              timer->timer_info->name, timer,
320              olsr_clock_toClockString(&timebuf, timer->timer_clock), timer->timer_cb_context);
321 }
322
323 /**
324  * This is the one stop shop for all sort of timer manipulation.
325  * Depending on the passed in parameters a new timer is started,
326  * or an existing timer is started or an existing timer is
327  * terminated.
328  * @param timer_ptr pointer to timer_entry pointer
329  * @param rel_time time until the new timer should fire, 0 to stop timer
330  * @param jitter_pct jitter of timer in percent
331  * @param context context pointer of timer
332  * @param ti timer_info of timer
333  */
334 void
335 olsr_timer_set(struct olsr_timer_entry **timer_ptr,
336                unsigned int rel_time,
337                uint8_t jitter_pct, void *context, struct olsr_timer_info *ti)
338 {
339   assert(ti);          /* we want timer cookies everywhere */
340   if (rel_time == 0) {
341     /* No good future time provided, kill it. */
342     olsr_timer_stop(*timer_ptr);
343     *timer_ptr = NULL;
344   }
345   else if ((*timer_ptr) == NULL) {
346     /* No timer running, kick it. */
347     *timer_ptr = olsr_timer_start(rel_time, jitter_pct, context, ti);
348   }
349   else {
350     olsr_timer_change(*timer_ptr, rel_time, jitter_pct);
351   }
352 }
353
354 /**
355  * Walk through the timer list and check if any timer is ready to fire.
356  * Call the provided function with the context pointer.
357  */
358 void
359 olsr_timer_walk(void)
360 {
361   unsigned int total_timers_walked = 0, total_timers_fired = 0;
362   unsigned int wheel_slot_walks = 0;
363
364   /*
365    * Check the required wheel slots since the last time a timer walk was invoked,
366    * or check *all* the wheel slots, whatever is less work.
367    * The latter is meant as a safety belt if the scheduler falls behind.
368    */
369   while ((timer_last_run <= olsr_clock_getNow()) && (wheel_slot_walks < TIMER_WHEEL_SLOTS)) {
370     struct list_entity tmp_head_node;
371     /* keep some statistics */
372     unsigned int timers_walked = 0, timers_fired = 0;
373
374     /* Get the hash slot for this clocktick */
375     struct list_entity *timer_head_node;
376
377     timer_head_node = &timer_wheel[timer_last_run & TIMER_WHEEL_MASK];
378
379     /* Walk all entries hanging off this hash bucket. We treat this basically as a stack
380      * so that we always know if and where the next element is.
381      */
382     list_init_head(&tmp_head_node);
383     while (!list_is_empty(timer_head_node)) {
384       /* the top element */
385       struct olsr_timer_entry *timer;
386
387       timer = list_first_element(timer_head_node, timer, timer_list);
388
389       /*
390        * Dequeue and insert to a temporary list.
391        * We do this to avoid loosing our walking context when
392        * multiple timers fire.
393        */
394       list_remove(&timer->timer_list);
395       list_add_after(&tmp_head_node, &timer->timer_list);
396       timers_walked++;
397
398       /* Ready to fire ? */
399       if (olsr_clock_isPast(timer->timer_clock)) {
400 #if !defined(REMOVE_LOG_DEBUG)
401   struct timeval_buf timebuf;
402 #endif
403         OLSR_DEBUG(LOG_TIMER, "TIMER: fire %s timer %p, ctx %p, "
404                    "at clocktick %u (%s)\n",
405                    timer->timer_info->name,
406                    timer, timer->timer_cb_context, timer_last_run,
407                    olsr_clock_getWallclockString(&timebuf));
408
409         /* This timer is expired, call into the provided callback function */
410         timer->timer_in_callback = true;
411         timer->timer_info->callback(timer->timer_cb_context);
412         timer->timer_in_callback = false;
413         timer->timer_info->changes++;
414
415         /* Only act on actually running timers */
416         if (timer->timer_running) {
417           /*
418            * Don't restart the periodic timer if the callback function has
419            * stopped the timer.
420            */
421           if (timer->timer_period) {
422             /* For periodical timers, rehash the random number and restart */
423             timer->timer_random = random();
424             olsr_timer_change(timer, timer->timer_period, timer->timer_jitter_pct);
425           } else {
426             /* Singleshot timers are stopped */
427             olsr_timer_stop(timer);
428           }
429         }
430         else {
431           /* free memory */
432           olsr_memcookie_free(timer_mem_cookie, timer);
433         }
434
435         timers_fired++;
436       }
437     }
438
439     /*
440      * Now merge the temporary list back to the old bucket.
441      */
442     list_merge(timer_head_node, &tmp_head_node);
443
444     /* keep some statistics */
445     total_timers_walked += timers_walked;
446     total_timers_fired += timers_fired;
447
448     /* Increment the time slot and wheel slot walk iteration */
449     timer_last_run++;
450     wheel_slot_walks++;
451   }
452
453   OLSR_DEBUG(LOG_TIMER, "TIMER: processed %4u/%d clockwheel slots, "
454              "timers walked %4u/%u, timers fired %u\n",
455              wheel_slot_walks, TIMER_WHEEL_SLOTS, total_timers_walked, timer_mem_cookie->ci_usage, total_timers_fired);
456
457   /*
458    * If the scheduler has slipped and we have walked all wheel slots,
459    * reset the last timer run.
460    */
461   timer_last_run = olsr_clock_getNow();
462 }
463
464 /**
465  * Decrement a relative timer by a random number range.
466  * @param the relative timer expressed in units of milliseconds.
467  * @param the jitter in percent
468  * @param random_val cached random variable to calculate jitter
469  * @return the absolute time when timer will fire
470  */
471 static uint32_t
472 calc_jitter(unsigned int rel_time, uint8_t jitter_pct, unsigned int random_val)
473 {
474   unsigned int jitter_time;
475
476   /*
477    * No jitter or, jitter larger than 99% does not make sense.
478    * Also protect against overflows resulting from > 25 bit timers.
479    */
480   if (jitter_pct == 0 || jitter_pct > 99 || rel_time > (1 << 24)) {
481     return olsr_clock_get_absolute(rel_time);
482   }
483
484   /*
485    * Play some tricks to avoid overflows with integer arithmetic.
486    */
487   jitter_time = (jitter_pct * rel_time) / 100;
488   jitter_time = random_val / (1 + RAND_MAX / (jitter_time + 1));
489
490   OLSR_DEBUG(LOG_TIMER, "TIMER: jitter %u%% rel_time %ums to %ums\n", jitter_pct, rel_time, rel_time - jitter_time);
491
492   return olsr_clock_get_absolute(rel_time - jitter_time);
493 }