4946d616ce3abec26d32971a424f193ee02dc025
[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/common_types.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 /* BUCKET_COUNT and BUCKET_TIMESLICE must be powers of 2 */
56 #define BUCKET_DEPTH 3
57 #define BUCKET_COUNT 512ull
58 #define BUCKET_TIMESLICE 128ull /* ms */
59
60 /* root of all timers */
61 static struct list_entity _buckets[BUCKET_COUNT][BUCKET_DEPTH];
62 static int _bucket_ptr[BUCKET_DEPTH];
63
64 /* time when the next timer will fire */
65 static uint64_t _next_fire_event;
66
67 /* number of timer events still in queue */
68 static uint32_t _total_timer_events;
69
70 /* Memory cookie for the timer manager */
71 struct list_entity timerinfo_list;
72
73 /* remember if initialized or not */
74 OLSR_SUBSYSTEM_STATE(_timer_state);
75
76 /* Prototypes */
77 static uint64_t _calc_jitter(uint64_t rel_time, uint8_t jitter_pct, unsigned int random_val);
78 static void _insert_into_bucket(struct olsr_timer_entry *);
79 static void _calculate_next_event(void);
80
81 /**
82  * Initialize timer scheduler subsystem
83  * @return -1 if an error happened, 0 otherwise
84  */
85 void
86 olsr_timer_init(void)
87 {
88   uint64_t now, offset;
89   unsigned i,j;
90
91   if (olsr_subsystem_init(&_timer_state))
92     return;
93
94   OLSR_INFO(LOG_TIMER, "Initializing timer scheduler.\n");
95   /* mask "last run" to slot size */
96   now = olsr_clock_getNow();
97
98   offset = BUCKET_TIMESLICE * BUCKET_COUNT;
99   now /= BUCKET_TIMESLICE;
100
101   for (i = 0; i < BUCKET_DEPTH; i++) {
102     _bucket_ptr[i] = now & (BUCKET_COUNT - 1ull);
103
104     now /= BUCKET_COUNT;
105     offset *= BUCKET_COUNT;
106
107     for (j = 0; j < BUCKET_COUNT; j++) {
108       list_init_head(&_buckets[j][i]);
109     }
110   }
111
112   /* at the moment we have no timer */
113   _next_fire_event = ~0ull;
114   _total_timer_events = 0;
115
116   list_init_head(&timerinfo_list);
117 }
118
119 /**
120  * Cleanup timer scheduler, this stops and deletes all timers
121  */
122 void
123 olsr_timer_cleanup(void)
124 {
125   struct olsr_timer_info *ti, *iterator;
126   struct list_entity *timer_head_node;
127   unsigned i,j;
128
129   if (olsr_subsystem_cleanup(&_timer_state))
130     return;
131
132   for (i = 0; i < BUCKET_DEPTH; i++) {
133     for (j = 0; j < BUCKET_COUNT; j++) {
134       timer_head_node = &_buckets[j][i];
135
136       /* Kill all entries hanging off this hash bucket. */
137       while (!list_is_empty(timer_head_node)) {
138         struct olsr_timer_entry *timer;
139
140         timer = list_first_element(timer_head_node, timer, _node);
141         olsr_timer_stop(timer);
142       }
143     }
144   }
145
146   /* free all timerinfos */
147   OLSR_FOR_ALL_TIMERS(ti, iterator) {
148     olsr_timer_remove(ti);
149   }
150 }
151
152 /**
153  * Add a new group of timers to the scheduler
154  * @param ti pointer to uninitialized timer info
155  */
156 void
157 olsr_timer_add(struct olsr_timer_info *ti) {
158   list_add_tail(&timerinfo_list, &ti->node);
159 }
160
161 /**
162  * Removes a group of timers from the scheduler
163  * All pointers to timers of this timer_info will be invalid after this.
164  * @param info pointer to timer info
165  */
166 void
167 olsr_timer_remove(struct olsr_timer_info *info) {
168   struct olsr_timer_entry *timer, *iterator;
169   unsigned i,j;
170
171   for (i = 0; i < BUCKET_DEPTH; i++) {
172     for (j = 0; j < BUCKET_COUNT; j++) {
173       list_for_each_element_safe(&_buckets[j][i], timer, _node, iterator) {
174         /* remove all timers of this timer_info */
175         if (timer->timer_info == info) {
176           olsr_timer_stop(timer);
177         }
178       }
179     }
180   }
181
182   list_remove(&info->node);
183 }
184
185 /**
186  * Start a new timer.
187  * @param timer initialized timer entry
188  */
189 void
190 olsr_timer_start(struct olsr_timer_entry *timer, uint64_t rel_time)
191 {
192 #if !defined(REMOVE_LOG_DEBUG)
193   struct timeval_buf timebuf;
194 #endif
195
196   assert(timer->timer_info);
197   assert(timer->timer_jitter_pct <= 100);
198   assert(rel_time > 0 && rel_time < 1000ull * INT32_MAX);
199
200   /*
201    * Compute random numbers only once.
202    */
203   if (!timer->timer_random) {
204     timer->timer_random = random();
205   }
206
207   /* Fill entry */
208   timer->timer_clock = _calc_jitter(rel_time, timer->timer_jitter_pct, timer->timer_random);
209
210   /* The cookie is used for debugging to traceback the originator */
211   timer->timer_info->usage++;
212   timer->timer_info->changes++;
213
214   /* Singleshot or periodical timer ? */
215   timer->timer_period = timer->timer_info->periodic ? rel_time : 0;
216
217   /*
218    * Now insert in the respective _timer_wheel slot.
219    */
220   _insert_into_bucket(timer);
221
222   /* and update internal time data */
223   _total_timer_events++;
224   if (timer->timer_clock < _next_fire_event) {
225     _next_fire_event = timer->timer_clock;
226   }
227
228   OLSR_DEBUG(LOG_TIMER, "TIMER: start %s timer %p firing in %s\n",
229              timer->timer_info->name, timer,
230              olsr_clock_toClockString(&timebuf, timer->timer_clock));
231 }
232
233 /**
234  * Delete a timer.
235  * @param timer the olsr_timer_entry that shall be removed
236  */
237 void
238 olsr_timer_stop(struct olsr_timer_entry *timer)
239 {
240   if (timer->timer_clock == 0) {
241     return;
242   }
243
244   OLSR_DEBUG(LOG_TIMER, "TIMER: stop %s\n", timer->timer_info->name);
245
246   /* remove timer from buckets */
247   list_remove(&timer->_node);
248   timer->timer_clock = 0;
249   timer->timer_info->usage--;
250   timer->timer_info->changes++;
251
252   /* and update internal time data */
253   _total_timer_events--;
254   if (_next_fire_event == timer->timer_clock) {
255     _calculate_next_event();
256   }
257 }
258
259 /**
260  * Change time when a timer should fire.
261  * @param timer olsr_timer_entry to be changed.
262  * @param rel_time new relative time expressed in units of milliseconds.
263  * @param jitter_pct new jitter expressed in percent.
264  */
265 void
266 olsr_timer_change(struct olsr_timer_entry *timer, uint64_t rel_time)
267 {
268 #if !defined(REMOVE_LOG_DEBUG)
269   struct timeval_buf timebuf;
270 #endif
271   bool recalculate;
272
273   /* Sanity check. */
274   if (!timer) {
275     return;
276   }
277
278   assert (rel_time < 1000ull * INT32_MAX);
279
280   /* remember if we have to recalculate the _next_fire_event variable */
281   recalculate = _next_fire_event == timer->timer_clock;
282
283   /* Singleshot or periodical timer ? */
284   timer->timer_period = timer->timer_info->periodic ? rel_time : 0;
285
286   timer->timer_clock = _calc_jitter(rel_time, timer->timer_jitter_pct, timer->timer_random);
287
288   /*
289    * Changes are easy: Remove timer from the existing _timer_wheel slot
290    * and reinsert into the new slot.
291    */
292
293   list_remove(&timer->_node);
294   _insert_into_bucket(timer);
295
296   if (timer->timer_clock < _next_fire_event) {
297     _next_fire_event = timer->timer_clock;
298   }
299   else if (recalculate) {
300     _calculate_next_event();
301   }
302
303   OLSR_DEBUG(LOG_TIMER, "TIMER: change %s timer, firing to %s\n",
304              timer->timer_info->name,
305              olsr_clock_toClockString(&timebuf, timer->timer_clock));
306 }
307
308 /**
309  * This is the one stop shop for all sort of timer manipulation.
310  * Depending on the passed in parameters a new timer is started,
311  * or an existing timer is started or an existing timer is
312  * terminated.
313  * @param timer_ptr pointer to timer_entry pointer
314  * @param rel_time time until the new timer should fire, 0 to stop timer
315  */
316 void
317 olsr_timer_set(struct olsr_timer_entry *timer, uint64_t rel_time)
318 {
319   if (rel_time == 0) {
320     /* No good future time provided, kill it. */
321     olsr_timer_stop(timer);
322   }
323   else if (timer->timer_clock == 0) {
324     /* No timer running, kick it. */
325     olsr_timer_start(timer, rel_time);
326   }
327   else {
328     olsr_timer_change(timer, rel_time);
329   }
330 }
331
332 /**
333  * Walk through the timer list and check if any timer is ready to fire.
334  * Call the provided function with the context pointer.
335  */
336 void
337 olsr_timer_walk(void)
338 {
339   struct olsr_timer_entry *timer, *t_it;
340   int i;
341
342   while (_next_fire_event <= olsr_clock_getNow()) {
343     i = _bucket_ptr[0];
344     list_for_each_element_safe(&_buckets[i][0], timer, _node, t_it) {
345       OLSR_DEBUG(LOG_TIMER, "TIMER: fire %s timer %p, ctx %p, "
346                   "at clocktick %" PRIu64 "\n",
347                   timer->timer_info->name,
348                   timer, timer->timer_cb_context, _next_fire_event);
349
350        /* This timer is expired, call into the provided callback function */
351        timer->timer_info->callback(timer->timer_cb_context);
352        timer->timer_info->changes++;
353
354        /*
355         * Only act on actually running timers, the callback might have
356         * called olsr_timer_stop() !
357         */
358        if (timer->timer_clock) {
359          /*
360           * Don't restart the periodic timer if the callback function has
361           * stopped the timer.
362           */
363          if (timer->timer_period) {
364            /* For periodical timers, rehash the random number and restart */
365            timer->timer_random = random();
366            olsr_timer_change(timer, timer->timer_period);
367          } else {
368            /* Singleshot timers are stopped */
369            olsr_timer_stop(timer);
370          }
371        }
372     }
373
374     /* advance our 'next event' marker */
375     _calculate_next_event();
376   }
377 }
378
379 /**
380  * @return timestamp when next timer will fire
381  */
382 uint64_t
383 olsr_timer_getNextEvent(void) {
384   return _next_fire_event;
385 }
386
387 /**
388  *
389  * @param timestamp
390  * @param depth
391  * @return true if the
392  */
393 static void
394 _insert_into_bucket(struct olsr_timer_entry *timer) {
395   uint64_t slot;
396   int64_t relative;
397   int group;
398
399   slot = timer->timer_clock / BUCKET_TIMESLICE;
400   relative = olsr_clock_getRelative(timer->timer_clock) / BUCKET_TIMESLICE;
401   OLSR_DEBUG(LOG_TIMER, "Insert new timer: %" PRIu64, relative);
402
403   for (group = 0; group < BUCKET_DEPTH; group++, slot /= BUCKET_COUNT, relative /= BUCKET_COUNT) {
404     if (relative < (int64_t)BUCKET_COUNT) {
405       slot %= BUCKET_COUNT;
406       OLSR_DEBUG_NH(LOG_TIMER, "    Insert into bucket: %" PRId64"/%d", slot, group);
407       list_add_tail(&_buckets[slot][group], &timer->_node);
408       return;
409     }
410   }
411
412   OLSR_WARN(LOG_TIMER, "Error, timer event too far in the future: %" PRIu64,
413       olsr_clock_getRelative(timer->timer_clock));
414 }
415
416
417 /**
418  * Decrement a relative timer by a random number range.
419  * @param the relative timer expressed in units of milliseconds.
420  * @param the jitter in percent
421  * @param random_val cached random variable to calculate jitter
422  * @return the absolute time when timer will fire
423  */
424 static uint64_t
425 _calc_jitter(uint64_t rel_time, uint8_t jitter_pct, unsigned int random_val)
426 {
427   uint64_t jitter_time;
428
429   /*
430    * No jitter or, jitter larger than 99% does not make sense.
431    * Also protect against overflows resulting from > 25 bit timers.
432    */
433   if (jitter_pct == 0 || jitter_pct > 99 || rel_time > (1 << 24)) {
434     return olsr_clock_get_absolute(rel_time);
435   }
436
437   /*
438    * Play some tricks to avoid overflows with integer arithmetic.
439    */
440   jitter_time = ((uint64_t)jitter_pct * rel_time) / 100;
441   jitter_time = (uint64_t)random_val / (1ull + (uint64_t)RAND_MAX / (jitter_time + 1ull));
442
443   OLSR_DEBUG(LOG_TIMER, "TIMER: jitter %u%% rel_time %" PRIu64 "ms to %" PRIu64 "ms\n",
444       jitter_pct, rel_time, rel_time - jitter_time);
445
446   return olsr_clock_get_absolute(rel_time - jitter_time);
447 }
448
449 static void
450 _copy_bucket(unsigned depth, unsigned idx) {
451   struct olsr_timer_entry *timer, *timer_it;
452   uint64_t divide;
453   unsigned i;
454
455   assert (depth > 0 && depth < BUCKET_DEPTH && idx < BUCKET_COUNT);
456
457   divide = BUCKET_TIMESLICE;
458   for (i = 0; i < depth-1; i++) {
459     divide *= BUCKET_COUNT;
460   }
461
462   _bucket_ptr[depth] = idx+1;
463
464   list_for_each_element_safe(&_buckets[idx][depth], timer, _node, timer_it) {
465     list_remove(&timer->_node);
466
467     i = (timer->timer_clock / divide) & (BUCKET_COUNT - 1ull);
468     list_add_tail(&_buckets[i][depth-1], &timer->_node);
469   }
470 }
471
472 static int
473 _look_for_event(unsigned depth) {
474   unsigned i,j;
475   int idx;
476
477   /* first look in existing data */
478   for (i=_bucket_ptr[depth], j=0; j < BUCKET_COUNT; i=(i+1)&255, j++) {
479     if (!list_is_empty(&_buckets[i][depth])) {
480       return i;
481     }
482   }
483
484   /* copy bucket from level higher if possible */
485   if (depth < BUCKET_DEPTH - 1) {
486     idx = _look_for_event(depth+1);
487     if (idx != -1) {
488       _copy_bucket(depth+1, idx);
489     }
490   }
491
492   for (i=0; i < BUCKET_COUNT; i++) {
493     if (!list_is_empty(&_buckets[i][depth])) {
494       return i;
495     }
496   }
497
498   return -1;
499 }
500
501 static void
502 _calculate_next_event(void) {
503   struct olsr_timer_entry *timer;
504
505   /* no timer event in queue ? */
506   if (_total_timer_events == 0) {
507     _next_fire_event = ~0ull;
508     return;
509   }
510
511   _bucket_ptr[0] = _look_for_event(0);
512   assert (_bucket_ptr[0] != -1);
513
514   timer = list_first_element(&_buckets[_bucket_ptr[0]][0], timer, _node);
515   _next_fire_event = timer->timer_clock & (~((uint64_t)BUCKET_TIMESLICE - 1));
516 }