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