0317c3a3a22dc2aa034dbc026606b9ebcdf71f0b
[oonf.git] / src / subsystems / oonf_timer.c
1
2 /*
3  * The olsr.org Optimized Link-State Routing daemon version 2 (olsrd2)
4  * Copyright (c) 2004-2015, 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 /**
43  * @file
44  */
45
46 #include <stdlib.h>
47 #include <string.h>
48 #include <unistd.h>
49
50 #include <oonf/libcommon/avl.h>
51 #include <oonf/oonf.h>
52 #include <oonf/libcore/oonf_logging.h>
53 #include <oonf/libcore/oonf_subsystem.h>
54 #include <oonf/libcore/os_core.h>
55 #include <oonf/subsystems/oonf_clock.h>
56 #include <oonf/subsystems/os_clock.h>
57
58 #include <oonf/subsystems/oonf_timer.h>
59
60 /* Definitions */
61 #define LOG_TIMER _oonf_timer_subsystem.logging
62
63 /* prototypes */
64 static int _init(void);
65 static void _cleanup(void);
66
67 static void _calc_clock(struct oonf_timer_instance *timer, uint64_t rel_time);
68 static int _avlcomp_timer(const void *p1, const void *p2);
69
70 /* tree of all timers */
71 static struct avl_tree _timer_tree;
72
73 /* true if scheduler is active */
74 static bool _scheduling_now;
75
76 /* List of timer classes */
77 static struct list_entity _timer_info_list;
78
79 /* subsystem definition */
80 static const char *_dependencies[] = {
81   OONF_CLOCK_SUBSYSTEM,
82 };
83
84 static struct oonf_subsystem _oonf_timer_subsystem = {
85   .name = OONF_TIMER_SUBSYSTEM,
86   .dependencies = _dependencies,
87   .dependencies_count = ARRAYSIZE(_dependencies),
88   .init = _init,
89   .cleanup = _cleanup,
90 };
91 DECLARE_OONF_PLUGIN(_oonf_timer_subsystem);
92
93 /**
94  * Initialize timer scheduler subsystem
95  * @return always returns 0
96  */
97 int
98 _init(void) {
99   OONF_INFO(LOG_TIMER, "Initializing timer scheduler.\n");
100
101   avl_init(&_timer_tree, _avlcomp_timer, true);
102   _scheduling_now = false;
103
104   list_init_head(&_timer_info_list);
105   return 0;
106 }
107
108 /**
109  * Cleanup timer scheduler, this stops and deletes all timers
110  */
111 static void
112 _cleanup(void) {
113   struct oonf_timer_class *ti, *iterator;
114
115   /* free all timerinfos */
116   list_for_each_element_safe(&_timer_info_list, ti, _node, iterator) {
117     oonf_timer_remove(ti);
118   }
119 }
120
121 /**
122  * Add a new group of timers to the scheduler
123  * @param ti pointer to uninitialized timer info
124  */
125 void
126 oonf_timer_add(struct oonf_timer_class *ti) {
127   list_add_tail(&_timer_info_list, &ti->_node);
128 }
129
130 /**
131  * Removes a group of timers from the scheduler
132  * All pointers to timers of this info will be invalid after this.
133  * @param info pointer to timer info
134  */
135 void
136 oonf_timer_remove(struct oonf_timer_class *info) {
137   struct oonf_timer_instance *timer, *iterator;
138
139   if (!list_is_node_added(&info->_node)) {
140     /* only free node if its hooked to the timer core */
141     return;
142   }
143
144   avl_for_each_element_safe(&_timer_tree, timer, _node, iterator) {
145     if (timer->class == info) {
146       oonf_timer_stop(timer);
147     }
148   }
149
150   list_remove(&info->_node);
151 }
152
153 /**
154  * Start or restart a new timer.
155  * @param timer initialized timer entry
156  * @param first relative time when the timer should fire the first time
157  * @param interval time between two timer events for periodic timers
158  */
159 void
160 oonf_timer_start_ext(struct oonf_timer_instance *timer, uint64_t first, uint64_t interval) {
161 #ifdef OONF_LOG_DEBUG_INFO
162   struct isonumber_str timebuf1;
163 #endif
164
165   if (timer->_clock) {
166     avl_remove(&_timer_tree, &timer->_node);
167     timer->class->_stat_changes++;
168   }
169   else {
170     timer->_node.key = timer;
171     timer->class->_stat_usage++;
172   }
173
174   /*
175    * Compute random numbers only once.
176    */
177   if (!timer->_random) {
178     if (os_core_get_random(&timer->_random, sizeof(timer->_random))) {
179       OONF_WARN(LOG_TIMER, "Could not get random data");
180       timer->_random = 0;
181     }
182   }
183
184   /* Fill entry */
185   _calc_clock(timer, first);
186
187   /* Singleshot or periodical timer ? */
188   timer->_period = timer->class->periodic ? interval : 0;
189
190   /* insert into tree */
191   avl_insert(&_timer_tree, &timer->_node);
192
193   OONF_DEBUG(LOG_TIMER, "TIMER: start timer '%s' firing in %s (%" PRIu64 ")\n", timer->class->name,
194     oonf_clock_toClockString(&timebuf1, first), timer->_clock);
195 }
196
197 /**
198  * Delete a timer.
199  * @param timer the oonf_timer_entry that shall be removed
200  */
201 void
202 oonf_timer_stop(struct oonf_timer_instance *timer) {
203   if (timer->_clock == 0) {
204     return;
205   }
206
207   OONF_DEBUG(LOG_TIMER, "TIMER: stop %s\n", timer->class->name);
208
209   /* remove timer from tree */
210   avl_remove(&_timer_tree, &timer->_node);
211   timer->_clock = 0;
212   timer->_random = 0;
213   timer->class->_stat_usage--;
214
215   if (timer->class->_timer_in_callback == timer) {
216     timer->class->_timer_stopped = true;
217   }
218 }
219
220 /**
221  * This is the one stop shop for all sort of timer manipulation.
222  * Depending on the passed in parameters a new timer is started,
223  * or an existing timer is started or an existing timer is
224  * terminated.
225  * @param timer timer_entry pointer
226  * @param first relative time when the timer should fire the first time
227  * @param interval time between two timer events for periodic timers
228  */
229 void
230 oonf_timer_set_ext(struct oonf_timer_instance *timer, uint64_t first, uint64_t interval) {
231   if (first == 0) {
232     /* No good future time provided, kill it. */
233     oonf_timer_stop(timer);
234   }
235   else {
236     /* Start or restart the timer */
237     oonf_timer_start_ext(timer, first, interval);
238   }
239 }
240
241 /**
242  * Walk through the timer list and check if any timer is ready to fire.
243  * Call the provided function with the context pointer.
244  */
245 void
246 oonf_timer_walk(void) {
247   struct oonf_timer_instance *timer;
248   struct oonf_timer_class *info;
249   uint64_t start_time, end_time;
250
251   _scheduling_now = true;
252
253   while (!avl_is_empty(&_timer_tree)) {
254     timer = avl_first_element(&_timer_tree, timer, _node);
255
256     if (timer->_clock > oonf_clock_getNow()) {
257       break;
258     }
259
260     OONF_DEBUG(LOG_TIMER, "TIMER: fire '%s' at clocktick %" PRIu64 "\n", timer->class->name, timer->_clock);
261
262     /*
263      * The timer->info pointer is invalidated by oonf_timer_stop()
264      */
265     info = timer->class;
266     info->_timer_in_callback = timer;
267     info->_timer_stopped = false;
268
269     /* update statistics */
270     info->_stat_fired++;
271
272     if (timer->_period == 0) {
273       /* stop now, the data structure might not be available anymore later */
274       oonf_timer_stop(timer);
275     }
276
277     /* This timer is expired, call into the provided callback function */
278     os_clock_gettime64(&start_time);
279     timer->class->callback(timer);
280     os_clock_gettime64(&end_time);
281
282     if (end_time - start_time > OONF_TIMER_SLICE) {
283       OONF_WARN(LOG_TIMER, "Timer %s scheduling took %" PRIu64 " ms", timer->class->name, end_time - start_time);
284       info->_stat_long++;
285     }
286
287     /*
288      * Only act on actually running timers, the callback might have
289      * called oonf_timer_stop() !
290      */
291     if (!info->_timer_stopped) {
292       /*
293        * Timer has been not been stopped, so its periodic.
294        * rehash the random number and restart.
295        */
296       if (os_core_get_random(&timer->_random, sizeof(timer->_random))) {
297         OONF_WARN(LOG_TIMER, "Could not get random data");
298         timer->_random = 0;
299       }
300       oonf_timer_start(timer, timer->_period);
301     }
302   }
303
304   _scheduling_now = false;
305 }
306
307 /**
308  * @return timestamp when next timer will fire
309  */
310 uint64_t
311 oonf_timer_getNextEvent(void) {
312   struct oonf_timer_instance *first;
313
314   if (avl_is_empty(&_timer_tree)) {
315     return UINT64_MAX;
316   }
317
318   first = avl_first_element(&_timer_tree, first, _node);
319   return first->_clock;
320 }
321
322 /**
323  * get list of active timer classes
324  * @return timer class list
325  */
326 struct list_entity *
327 oonf_timer_get_list(void) {
328   return &_timer_info_list;
329 }
330
331 /**
332  * calculate the absolute time when a timer should fire, incuding jitter
333  * @param timer timer instance that will be initialized
334  * @param rel_time relative time until timer should fire
335  */
336 static void
337 _calc_clock(struct oonf_timer_instance *timer, uint64_t rel_time) {
338   uint64_t t = 0;
339   unsigned random_jitter;
340
341   if (timer->jitter_pct) {
342     /*
343      * Play some tricks to avoid overflows with integer arithmetic.
344      */
345     random_jitter = timer->_random / (UINT32_MAX / timer->jitter_pct);
346     t = (uint64_t)random_jitter * rel_time / 100;
347
348     OONF_DEBUG(LOG_TIMER, "TIMER: jitter %u%% (%u) rel_time %" PRIu64 "ms to %" PRIu64 "ms\n", timer->jitter_pct,
349       random_jitter, rel_time, rel_time - t);
350
351     rel_time -= t;
352   }
353
354   timer->_clock = oonf_clock_get_absolute(rel_time);
355
356   /* round up to next timeslice */
357   timer->_clock += OONF_TIMER_SLICE;
358   timer->_clock -= (timer->_clock % OONF_TIMER_SLICE);
359 }
360
361 /**
362  * Custom AVL comparator for two timer entries.
363  * @param p1 first timer entry
364  * @param p2 second timer entry
365  * @return -1/0/1 depending on comparision of time when timer fires
366  */
367 static int
368 _avlcomp_timer(const void *p1, const void *p2) {
369   const struct oonf_timer_instance *t1, *t2;
370
371   t1 = p1;
372   t2 = p2;
373
374   if (t1->_clock > t2->_clock) {
375     return 1;
376   }
377   if (t1->_clock < t2->_clock) {
378     return -1;
379   }
380   return 0;
381 }