Remove memory allocation in olsr_timer_add()
[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
63 /* remember if initialized or not */
64 OLSR_SUBSYSTEM_STATE(_timer_state);
65
66 /* Prototypes */
67 static uint32_t calc_jitter(unsigned int rel_time, uint8_t jitter_pct, unsigned int random_val);
68
69 /**
70  * Initialize timer scheduler subsystem
71  * @return -1 if an error happened, 0 otherwise
72  */
73 int
74 olsr_timer_init(void)
75 {
76   int idx;
77
78   if (olsr_subsystem_is_initialized(&_timer_state))
79     return 0;
80
81   OLSR_INFO(LOG_SOCKET, "Initializing scheduler.\n");
82
83   /* init lists */
84   for (idx = 0; idx < TIMER_WHEEL_SLOTS; idx++) {
85     list_init_head(&timer_wheel[idx]);
86   }
87
88   /*
89    * Reset the last timer run.
90    */
91   timer_last_run = olsr_clock_getNow();
92
93   /* Allocate a cookie for the block based memory manager. */
94   timer_mem_cookie = olsr_memcookie_add("timer_entry", sizeof(struct olsr_timer_entry));
95   if (timer_mem_cookie == NULL) {
96     OLSR_WARN_OOM(LOG_SOCKET);
97     return -1;
98   }
99
100   list_init_head(&timerinfo_list);
101
102   olsr_subsystem_init(&_timer_state);
103   return 0;
104 }
105
106 /**
107  * Cleanup timer scheduler, this stops and deletes all timers
108  */
109 void
110 olsr_timer_cleanup(void)
111 {
112   struct olsr_timer_info *ti, *iterator;
113   struct list_entity *timer_head_node;
114   unsigned int wheel_slot = 0;
115
116   if (olsr_subsystem_cleanup(&_timer_state))
117     return;
118
119   for (wheel_slot = 0; wheel_slot < TIMER_WHEEL_SLOTS; wheel_slot++) {
120     timer_head_node = &timer_wheel[wheel_slot & TIMER_WHEEL_MASK];
121
122     /* Kill all entries hanging off this hash bucket. */
123     while (!list_is_empty(timer_head_node)) {
124       struct olsr_timer_entry *timer;
125
126       timer = list_first_element(timer_head_node, timer, timer_list);
127       olsr_timer_stop(timer);
128     }
129   }
130
131   /* free all timerinfos */
132   OLSR_FOR_ALL_TIMERS(ti, iterator) {
133     olsr_timer_remove(ti);
134   }
135
136   /* release memory cookie for timers */
137   olsr_memcookie_remove(timer_mem_cookie);
138 }
139
140 /**
141  * Add a new group of timers to the scheduler
142  * @param ti pointer to uninitialized timer info
143  */
144 void
145 olsr_timer_add(struct olsr_timer_info *ti) {
146   list_add_tail(&timerinfo_list, &ti->node);
147 }
148
149 /**
150  * Removes a group of timers from the scheduler
151  * All pointers to timers of this timer_info will be invalid after this.
152  * @param info pointer to timer info
153  */
154 void
155 olsr_timer_remove(struct olsr_timer_info *info) {
156   struct olsr_timer_entry *timer, *iterator;
157   int slot;
158
159   for (slot=0; slot < TIMER_WHEEL_SLOTS; slot++) {
160     list_for_each_element_safe(&timer_wheel[slot], timer, timer_list, iterator) {
161       /* remove all timers of this timer_info */
162       if (timer->timer_info == info) {
163         olsr_timer_stop(timer);
164       }
165     }
166   }
167
168   list_remove(&info->node);
169 }
170
171 /**
172  * Start a new timer.
173  * @param rel_time time expressed in milliseconds
174  * @param jitter_pct expressed in percent
175  * @param context for the callback function
176  * @param ti pointer to timer_info object
177  * @return a pointer to the created entry
178  */
179 struct olsr_timer_entry *
180 olsr_timer_start(unsigned int rel_time,
181     uint8_t jitter_pct, void *context, struct olsr_timer_info *ti)
182 {
183   struct olsr_timer_entry *timer;
184 #if !defined(REMOVE_LOG_DEBUG)
185   struct timeval_buf timebuf;
186 #endif
187
188   assert(ti != 0);          /* we want timer cookies everywhere */
189   assert(rel_time);
190   assert(jitter_pct <= 100);
191
192   timer = olsr_memcookie_malloc(timer_mem_cookie);
193
194   /*
195    * Compute random numbers only once.
196    */
197   if (!timer->timer_random) {
198     timer->timer_random = random();
199   }
200
201   /* Fill entry */
202   timer->timer_clock = calc_jitter(rel_time, jitter_pct, timer->timer_random);
203   timer->timer_cb_context = context;
204   timer->timer_jitter_pct = jitter_pct;
205   timer->timer_running = true;
206
207   /* The cookie is used for debugging to traceback the originator */
208   timer->timer_info = ti;
209   ti->usage++;
210   ti->changes++;
211
212   /* Singleshot or periodical timer ? */
213   timer->timer_period = ti->periodic ? rel_time : 0;
214
215   /*
216    * Now insert in the respective timer_wheel slot.
217    */
218   list_add_before(&timer_wheel[timer->timer_clock & TIMER_WHEEL_MASK], &timer->timer_list);
219
220   OLSR_DEBUG(LOG_TIMER, "TIMER: start %s timer %p firing in %s, ctx %p\n",
221              ti->name, timer, olsr_clock_toClockString(&timebuf, timer->timer_clock), context);
222
223   return timer;
224 }
225
226 /**
227  * Delete a timer.
228  * @param timer the olsr_timer_entry that shall be removed
229  */
230 void
231 olsr_timer_stop(struct olsr_timer_entry *timer)
232 {
233   /* It's okay to get a NULL here */
234   if (timer == NULL) {
235     return;
236   }
237
238   assert(timer->timer_info);     /* we want timer cookies everywhere */
239   assert(timer->timer_list.next != NULL && timer->timer_list.prev != NULL);
240
241   OLSR_DEBUG(LOG_TIMER, "TIMER: stop %s timer %p, ctx %p\n",
242              timer->timer_info->name, timer, timer->timer_cb_context);
243
244
245   /*
246    * Carve out of the existing wheel_slot and free.
247    */
248   list_remove(&timer->timer_list);
249   timer->timer_running = false;
250   timer->timer_info->usage--;
251   timer->timer_info->changes++;
252
253   if (!timer->timer_in_callback) {
254     olsr_memcookie_free(timer_mem_cookie, timer);
255   }
256 }
257
258 /**
259  * Change time when a timer should fire.
260  * @param timer olsr_timer_entry to be changed.
261  * @param rel_time new relative time expressed in units of milliseconds.
262  * @param jitter_pct new jitter expressed in percent.
263  */
264 void
265 olsr_timer_change(struct olsr_timer_entry *timer, unsigned int rel_time, uint8_t jitter_pct)
266 {
267 #if !defined(REMOVE_LOG_DEBUG)
268   struct timeval_buf timebuf;
269 #endif
270
271   /* Sanity check. */
272   if (!timer) {
273     return;
274   }
275
276   assert(timer->timer_info);     /* we want timer cookies everywhere */
277
278   /* Singleshot or periodical timer ? */
279   timer->timer_period = timer->timer_info->periodic ? rel_time : 0;
280
281   timer->timer_clock = calc_jitter(rel_time, jitter_pct, timer->timer_random);
282   timer->timer_jitter_pct = jitter_pct;
283
284   /*
285    * Changes are easy: Remove timer from the exisiting timer_wheel slot
286    * and reinsert into the new slot.
287    */
288   list_remove(&timer->timer_list);
289   list_add_before(&timer_wheel[timer->timer_clock & TIMER_WHEEL_MASK], &timer->timer_list);
290
291   OLSR_DEBUG(LOG_TIMER, "TIMER: change %s timer %p, firing to %s, ctx %p\n",
292              timer->timer_info->name, timer,
293              olsr_clock_toClockString(&timebuf, timer->timer_clock), timer->timer_cb_context);
294 }
295
296 /**
297  * This is the one stop shop for all sort of timer manipulation.
298  * Depending on the passed in parameters a new timer is started,
299  * or an existing timer is started or an existing timer is
300  * terminated.
301  * @param timer_ptr pointer to timer_entry pointer
302  * @param rel_time time until the new timer should fire, 0 to stop timer
303  * @param jitter_pct jitter of timer in percent
304  * @param context context pointer of timer
305  * @param ti timer_info of timer
306  */
307 void
308 olsr_timer_set(struct olsr_timer_entry **timer_ptr,
309                unsigned int rel_time,
310                uint8_t jitter_pct, void *context, struct olsr_timer_info *ti)
311 {
312   assert(ti);          /* we want timer cookies everywhere */
313   if (rel_time == 0) {
314     /* No good future time provided, kill it. */
315     olsr_timer_stop(*timer_ptr);
316     *timer_ptr = NULL;
317   }
318   else if ((*timer_ptr) == NULL) {
319     /* No timer running, kick it. */
320     *timer_ptr = olsr_timer_start(rel_time, jitter_pct, context, ti);
321   }
322   else {
323     olsr_timer_change(*timer_ptr, rel_time, jitter_pct);
324   }
325 }
326
327 /**
328  * Walk through the timer list and check if any timer is ready to fire.
329  * Call the provided function with the context pointer.
330  */
331 void
332 olsr_timer_walk(void)
333 {
334   unsigned int total_timers_walked = 0, total_timers_fired = 0;
335   unsigned int wheel_slot_walks = 0;
336
337   /*
338    * Check the required wheel slots since the last time a timer walk was invoked,
339    * or check *all* the wheel slots, whatever is less work.
340    * The latter is meant as a safety belt if the scheduler falls behind.
341    */
342   while ((timer_last_run <= olsr_clock_getNow()) && (wheel_slot_walks < TIMER_WHEEL_SLOTS)) {
343     struct list_entity tmp_head_node;
344     /* keep some statistics */
345     unsigned int timers_walked = 0, timers_fired = 0;
346
347     /* Get the hash slot for this clocktick */
348     struct list_entity *timer_head_node;
349
350     timer_head_node = &timer_wheel[timer_last_run & TIMER_WHEEL_MASK];
351
352     /* Walk all entries hanging off this hash bucket. We treat this basically as a stack
353      * so that we always know if and where the next element is.
354      */
355     list_init_head(&tmp_head_node);
356     while (!list_is_empty(timer_head_node)) {
357       /* the top element */
358       struct olsr_timer_entry *timer;
359
360       timer = list_first_element(timer_head_node, timer, timer_list);
361
362       /*
363        * Dequeue and insert to a temporary list.
364        * We do this to avoid loosing our walking context when
365        * multiple timers fire.
366        */
367       list_remove(&timer->timer_list);
368       list_add_after(&tmp_head_node, &timer->timer_list);
369       timers_walked++;
370
371       /* Ready to fire ? */
372       if (olsr_clock_isPast(timer->timer_clock)) {
373 #if !defined(REMOVE_LOG_DEBUG)
374   struct timeval_buf timebuf;
375 #endif
376         OLSR_DEBUG(LOG_TIMER, "TIMER: fire %s timer %p, ctx %p, "
377                    "at clocktick %u (%s)\n",
378                    timer->timer_info->name,
379                    timer, timer->timer_cb_context, timer_last_run,
380                    olsr_clock_getWallclockString(&timebuf));
381
382         /* This timer is expired, call into the provided callback function */
383         timer->timer_in_callback = true;
384         timer->timer_info->callback(timer->timer_cb_context);
385         timer->timer_in_callback = false;
386         timer->timer_info->changes++;
387
388         /* Only act on actually running timers */
389         if (timer->timer_running) {
390           /*
391            * Don't restart the periodic timer if the callback function has
392            * stopped the timer.
393            */
394           if (timer->timer_period) {
395             /* For periodical timers, rehash the random number and restart */
396             timer->timer_random = random();
397             olsr_timer_change(timer, timer->timer_period, timer->timer_jitter_pct);
398           } else {
399             /* Singleshot timers are stopped */
400             olsr_timer_stop(timer);
401           }
402         }
403         else {
404           /* free memory */
405           olsr_memcookie_free(timer_mem_cookie, timer);
406         }
407
408         timers_fired++;
409       }
410     }
411
412     /*
413      * Now merge the temporary list back to the old bucket.
414      */
415     list_merge(timer_head_node, &tmp_head_node);
416
417     /* keep some statistics */
418     total_timers_walked += timers_walked;
419     total_timers_fired += timers_fired;
420
421     /* Increment the time slot and wheel slot walk iteration */
422     timer_last_run++;
423     wheel_slot_walks++;
424   }
425
426   OLSR_DEBUG(LOG_TIMER, "TIMER: processed %4u/%d clockwheel slots, "
427              "timers walked %4u/%u, timers fired %u\n",
428              wheel_slot_walks, TIMER_WHEEL_SLOTS, total_timers_walked, timer_mem_cookie->ci_usage, total_timers_fired);
429
430   /*
431    * If the scheduler has slipped and we have walked all wheel slots,
432    * reset the last timer run.
433    */
434   timer_last_run = olsr_clock_getNow();
435 }
436
437 /**
438  * Decrement a relative timer by a random number range.
439  * @param the relative timer expressed in units of milliseconds.
440  * @param the jitter in percent
441  * @param random_val cached random variable to calculate jitter
442  * @return the absolute time when timer will fire
443  */
444 static uint32_t
445 calc_jitter(unsigned int rel_time, uint8_t jitter_pct, unsigned int random_val)
446 {
447   unsigned int jitter_time;
448
449   /*
450    * No jitter or, jitter larger than 99% does not make sense.
451    * Also protect against overflows resulting from > 25 bit timers.
452    */
453   if (jitter_pct == 0 || jitter_pct > 99 || rel_time > (1 << 24)) {
454     return olsr_clock_get_absolute(rel_time);
455   }
456
457   /*
458    * Play some tricks to avoid overflows with integer arithmetic.
459    */
460   jitter_time = (jitter_pct * rel_time) / 100;
461   jitter_time = random_val / (1 + RAND_MAX / (jitter_time + 1));
462
463   OLSR_DEBUG(LOG_TIMER, "TIMER: jitter %u%% rel_time %ums to %ums\n", jitter_pct, rel_time, rel_time - jitter_time);
464
465   return olsr_clock_get_absolute(rel_time - jitter_time);
466 }