Reworking layer2 subsystem
[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 first relative time when the timer should fire the first time
144  * @param interval time between two timer events for periodic timers
145  */
146 void
147 oonf_timer_start_ext(struct oonf_timer_entry *timer, uint64_t first, uint64_t interval)
148 {
149 #ifdef OONF_LOG_DEBUG_INFO
150   struct human_readable_str timebuf1;
151 #endif
152
153   assert(timer->info);
154   assert(timer->jitter_pct <= 100);
155
156   if (timer->_clock) {
157     avl_remove(&_timer_tree, &timer->_node);
158   }
159   else {
160     timer->_node.key = timer;
161     timer->info->usage++;
162   }
163   timer->info->changes++;
164
165   /*
166    * Compute random numbers only once.
167    */
168   if (!timer->_random) {
169     timer->_random = os_core_random();
170   }
171
172   /* Fill entry */
173   _calc_clock(timer, first);
174
175   /* Singleshot or periodical timer ? */
176   timer->_period = timer->info->periodic ? interval : 0;
177
178   /* insert into tree */
179   avl_insert(&_timer_tree, &timer->_node);
180
181   OONF_DEBUG(LOG_TIMER, "TIMER: start timer '%s' firing in %s (%"PRIu64")\n",
182       timer->info->name,
183       oonf_clock_toClockString(&timebuf1, first), timer->_clock);
184
185   /* fix 'next event' pointers if necessary */
186   if (_scheduling_now) {
187     /* will be fixed at the end of the timer scheduling loop */
188     return;
189   }
190 }
191
192 /**
193  * Delete a timer.
194  * @param timer the oonf_timer_entry that shall be removed
195  */
196 void
197 oonf_timer_stop(struct oonf_timer_entry *timer)
198 {
199   if (timer->_clock == 0) {
200     return;
201   }
202
203   OONF_DEBUG(LOG_TIMER, "TIMER: stop %s\n", timer->info->name);
204
205   /* remove timer from tree */
206   avl_remove(&_timer_tree, &timer->_node);
207   timer->_clock = 0;
208   timer->_random = 0;
209   timer->info->usage--;
210   timer->info->changes++;
211
212   if (timer->info->_timer_in_callback == timer) {
213     timer->info->_timer_stopped = true;
214   }
215 }
216
217 /**
218  * This is the one stop shop for all sort of timer manipulation.
219  * Depending on the passed in parameters a new timer is started,
220  * or an existing timer is started or an existing timer is
221  * terminated.
222  * @param timer timer_entry pointer
223  * @param first relative time when the timer should fire the first time
224  * @param interval time between two timer events for periodic timers
225  */
226 void
227 oonf_timer_set_ext(struct oonf_timer_entry *timer, uint64_t first, uint64_t interval)
228 {
229   if (first == 0) {
230     /* No good future time provided, kill it. */
231     oonf_timer_stop(timer);
232   }
233   else {
234     /* Start or restart the timer */
235     oonf_timer_start_ext(timer, first, interval);
236   }
237 }
238
239 /**
240  * Walk through the timer list and check if any timer is ready to fire.
241  * Call the provided function with the context pointer.
242  */
243 void
244 oonf_timer_walk(void)
245 {
246   struct oonf_timer_entry *timer;
247   struct oonf_timer_info *info;
248
249   _scheduling_now = true;
250
251   while (true) {
252     timer = avl_first_element(&_timer_tree, timer, _node);
253
254     if (timer->_clock > oonf_clock_getNow()) {
255       break;
256     }
257
258     OONF_DEBUG(LOG_TIMER, "TIMER: fire '%s' at clocktick %" PRIu64 "\n",
259                   timer->info->name, timer->_clock);
260
261     /*
262      * The timer->info pointer is invalidated by oonf_timer_stop()
263      */
264     info = timer->info;
265     info->_timer_in_callback = timer;
266     info->_timer_stopped = false;
267
268     /* update statistics */
269     info->changes++;
270
271     if (timer->_period == 0) {
272       /* stop now, the data structure might not be available anymore later */
273       oonf_timer_stop(timer);
274     }
275
276     /* This timer is expired, call into the provided callback function */
277     timer->info->callback(timer->cb_context);
278
279     /*
280      * Only act on actually running timers, the callback might have
281      * called oonf_timer_stop() !
282      */
283     if (!info->_timer_stopped) {
284       /*
285        * Timer has been not been stopped, so its periodic.
286        * rehash the random number and restart.
287        */
288       timer->_random = os_core_random();
289       oonf_timer_start(timer, timer->_period);
290     }
291   }
292
293   _scheduling_now = false;
294 }
295
296 /**
297  * @return timestamp when next timer will fire
298  */
299 uint64_t
300 oonf_timer_getNextEvent(void) {
301   struct oonf_timer_entry *first;
302
303   if (avl_is_empty(&_timer_tree)) {
304     return UINT64_MAX;
305   }
306
307   first = avl_first_element(&_timer_tree, first, _node);
308   return first->_clock;
309 }
310
311 /**
312  * Decrement a relative timer by a random number range.
313  * @param the relative timer expressed in units of milliseconds.
314  * @param the jitter in percent
315  * @param random_val cached random variable to calculate jitter
316  * @return the absolute time when timer will fire
317  */
318 static void
319 _calc_clock(struct oonf_timer_entry *timer, uint64_t rel_time)
320 {
321   uint64_t t = 0;
322   unsigned random_jitter;
323
324   if (timer->jitter_pct) {
325     /*
326      * Play some tricks to avoid overflows with integer arithmetic.
327      */
328     random_jitter = timer->_random / (RAND_MAX / timer->jitter_pct);
329     t = (uint64_t)random_jitter * rel_time / 100;
330
331     OONF_DEBUG(LOG_TIMER, "TIMER: jitter %u%% rel_time %" PRIu64 "ms to %" PRIu64 "ms\n",
332         timer->jitter_pct, rel_time, rel_time - t);
333
334     rel_time -= t;
335   }
336
337   timer->_clock = oonf_clock_get_absolute(rel_time - t);
338
339   /* round up to next timeslice */
340   timer->_clock += TIMESLICE;
341   timer->_clock -= (timer->_clock % TIMESLICE);
342 }
343
344 /**
345  * Custom AVL comparator for two timer entries.
346  * @param p1
347  * @param p2
348  * @return
349  */
350 static int
351 _avlcomp_timer(const void *p1, const void *p2) {
352   const struct oonf_timer_entry *t1, *t2;
353
354   t1 = p1;
355   t2 = p2;
356
357   if (t1->_clock > t2->_clock) {
358     return 1;
359   }
360   if (t1->_clock < t2->_clock) {
361     return -1;
362   }
363   return 0;
364 }