Several small refactorings. Split log-group of network scheduler and timer scheduler
[olsrd.git] / src / scheduler.c
1
2 /*
3  * The olsr.org Optimized Link-State Routing daemon(olsrd)
4  * Copyright (c) 2004-2009, 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 <unistd.h>
43 #include <assert.h>
44 #include <stdlib.h>
45
46 #include "common/avl.h"
47 #include "common/avl_olsr_comp.h"
48 #include "scheduler.h"
49 #include "link_set.h"
50 #include "olsr.h"
51 #include "olsr_cookie.h"
52 #include "os_net.h"
53 #include "os_time.h"
54 #include "olsr_logging.h"
55
56 /* Timer data, global. Externed in scheduler.h */
57 uint32_t now_times;                    /* relative time compared to startup (in milliseconds */
58 struct timeval first_tv;               /* timevalue during startup */
59 struct timeval last_tv;                /* timevalue used for last olsr_times() calculation */
60
61 /* Hashed root of all timers */
62 static struct list_entity timer_wheel[TIMER_WHEEL_SLOTS];
63 static uint32_t timer_last_run;        /* remember the last timeslot walk */
64
65 /* Memory cookie for the timer manager */
66 struct avl_tree timerinfo_tree;
67 static struct olsr_cookie_info *timer_mem_cookie = NULL;
68 static struct olsr_cookie_info *timerinfo_cookie = NULL;
69
70 /* Head of all OLSR used sockets */
71 static struct list_entity socket_head;
72
73 /* Prototypes */
74 static void walk_timers(uint32_t *);
75 static void poll_sockets(void);
76 static uint32_t calc_jitter(unsigned int rel_time, uint8_t jitter_pct, unsigned int random_val);
77
78 /*
79  * A wrapper around times(2). Note, that this function has some
80  * portability problems, so do not rely on absolute values returned.
81  * Under Linux, uclibc and libc directly call the sys_times() located
82  * in kernel/sys.c and will only return an error if the tms_buf is
83  * not writeable.
84  */
85 static uint32_t
86 olsr_times(void)
87 {
88   struct timeval tv;
89   uint32_t t;
90
91   if (os_gettimeofday(&tv, NULL) != 0) {
92     OLSR_ERROR(LOG_SCHEDULER, "OS clock is not working, have to shut down OLSR (%s)\n", strerror(errno));
93     olsr_exit(1);
94   }
95
96   /* test if time jumped backward or more than 60 seconds forward */
97   if (tv.tv_sec < last_tv.tv_sec || (tv.tv_sec == last_tv.tv_sec && tv.tv_usec < last_tv.tv_usec)
98       || tv.tv_sec - last_tv.tv_sec > 60) {
99     OLSR_WARN(LOG_SCHEDULER, "Time jump (%d.%06d to %d.%06d)\n",
100               (int32_t) (last_tv.tv_sec), (int32_t) (last_tv.tv_usec), (int32_t) (tv.tv_sec), (int32_t) (tv.tv_usec));
101
102     t = (last_tv.tv_sec - first_tv.tv_sec) * 1000 + (last_tv.tv_usec - first_tv.tv_usec) / 1000;
103     t++;                        /* advance time by one millisecond */
104
105     first_tv = tv;
106     first_tv.tv_sec -= (t / 1000);
107     first_tv.tv_usec -= ((t % 1000) * 1000);
108
109     if (first_tv.tv_usec < 0) {
110       first_tv.tv_sec--;
111       first_tv.tv_usec += 1000000;
112     }
113     last_tv = tv;
114     return t;
115   }
116   last_tv = tv;
117   return (tv.tv_sec - first_tv.tv_sec) * 1000 + (tv.tv_usec - first_tv.tv_usec) / 1000;
118 }
119
120 /**
121  * Returns a timestamp s seconds in the future
122  */
123 uint32_t
124 olsr_getTimestamp(uint32_t s)
125 {
126   return now_times + s;
127 }
128
129 /**
130  * Returns the number of milliseconds until the timestamp will happen
131  */
132
133 int32_t
134 olsr_getTimeDue(uint32_t s)
135 {
136   uint32_t diff;
137   if (s > now_times) {
138     diff = s - now_times;
139
140     /* overflow ? */
141     if (diff > (1u << 31)) {
142       return -(int32_t) (0xffffffff - diff);
143     }
144     return (int32_t) (diff);
145   }
146
147   diff = now_times - s;
148   /* overflow ? */
149   if (diff > (1u << 31)) {
150     return (int32_t) (0xffffffff - diff);
151   }
152   return -(int32_t) (diff);
153 }
154
155 bool
156 olsr_isTimedOut(uint32_t s)
157 {
158   if (s > now_times) {
159     return s - now_times > (1u << 31);
160   }
161
162   return now_times - s <= (1u << 31);
163 }
164
165 struct olsr_timer_info *
166 olsr_alloc_timerinfo(const char *name, timer_cb_func callback, bool periodic) {
167   struct olsr_timer_info *ti;
168
169   ti = olsr_cookie_malloc(timerinfo_cookie);
170   ti->name = strdup(name);
171   ti->node.key = ti->name;
172   ti->callback = callback;
173   ti->periodic = periodic;
174
175   avl_insert(&timerinfo_tree, &ti->node);
176   return ti;
177 }
178
179 /**
180  * Add a socket and handler to the socketset
181  * beeing used in the main select(2) loop
182  * in listen_loop
183  *
184  *@param fd the socket
185  *@param pf the processing function
186  */
187 void
188 add_olsr_socket(int fd, socket_handler_func pf_pr, socket_handler_func pf_imm, void *data, unsigned int flags)
189 {
190   struct olsr_socket_entry *new_entry;
191
192   if (fd < 0 || (pf_pr == NULL && pf_imm == NULL)) {
193     OLSR_WARN(LOG_SCHEDULER, "Bogus socket entry - not registering...");
194     return;
195   }
196   OLSR_DEBUG(LOG_SCHEDULER, "Adding OLSR socket entry %d\n", fd);
197
198   new_entry = olsr_malloc(sizeof(*new_entry), "Socket entry");
199
200   new_entry->fd = fd;
201   new_entry->process_immediate = pf_imm;
202   new_entry->process_pollrate = pf_pr;
203   new_entry->data = data;
204   new_entry->flags = flags;
205
206   /* Queue */
207   list_add_before(&socket_head, &new_entry->socket_node);
208 }
209
210 /**
211  * Remove a socket and handler to the socketset
212  * beeing used in the main select(2) loop
213  * in listen_loop
214  *
215  *@param fd the socket
216  *@param pf the processing function
217  */
218 int
219 remove_olsr_socket(int fd, socket_handler_func pf_pr, socket_handler_func pf_imm)
220 {
221   struct olsr_socket_entry *entry;
222   struct list_iterator iterator;
223
224   if (fd < 0 || (pf_pr == NULL && pf_imm == NULL)) {
225     OLSR_WARN(LOG_SCHEDULER, "Bogus socket entry - not processing...");
226     return 0;
227   }
228   OLSR_DEBUG(LOG_SCHEDULER, "Removing OLSR socket entry %d\n", fd);
229
230   OLSR_FOR_ALL_SOCKETS(entry, iterator) {
231     if (entry->fd == fd && entry->process_immediate == pf_imm && entry->process_pollrate == pf_pr) {
232       /* just mark this node as "deleted", it will be cleared later at the end of handle_fds() */
233       entry->process_immediate = NULL;
234       entry->process_pollrate = NULL;
235       entry->flags = 0;      return 1;
236     }
237   }
238   return 0;
239 }
240
241 void
242 enable_olsr_socket(int fd, socket_handler_func pf_pr, socket_handler_func pf_imm, unsigned int flags)
243 {
244   struct olsr_socket_entry *entry;
245   struct list_iterator iterator;
246
247   OLSR_FOR_ALL_SOCKETS(entry, iterator) {
248     if (entry->fd == fd && entry->process_immediate == pf_imm && entry->process_pollrate == pf_pr) {
249       entry->flags |= flags;
250     }
251   }
252 }
253
254 void
255 disable_olsr_socket(int fd, socket_handler_func pf_pr, socket_handler_func pf_imm, unsigned int flags)
256 {
257   struct olsr_socket_entry *entry;
258   struct list_iterator iterator;
259
260   OLSR_FOR_ALL_SOCKETS(entry, iterator) {
261     if (entry->fd == fd && entry->process_immediate == pf_imm && entry->process_pollrate == pf_pr) {
262       entry->flags &= ~flags;
263     }
264   }
265 }
266
267 /**
268  * Close and free all sockets.
269  */
270 void
271 olsr_flush_sockets(void)
272 {
273   struct olsr_socket_entry *entry;
274   struct list_iterator iterator;
275
276   OLSR_FOR_ALL_SOCKETS(entry, iterator) {
277     os_close(entry->fd);
278     list_remove(&entry->socket_node);
279     free(entry);
280   }
281 }
282
283 static void
284 poll_sockets(void)
285 {
286   int n;
287   struct olsr_socket_entry *entry;
288   struct list_iterator iterator;
289   fd_set ibits, obits;
290   struct timeval tvp = { 0, 0 };
291   int hfd = 0, fdsets = 0;
292
293   /* If there are no registered sockets we
294    * do not call select(2)
295    */
296   if (list_is_empty(&socket_head)) {
297     return;
298   }
299
300   FD_ZERO(&ibits);
301   FD_ZERO(&obits);
302
303   /* Adding file-descriptors to FD set */
304   OLSR_FOR_ALL_SOCKETS(entry, iterator) {
305     if (entry->process_pollrate == NULL) {
306       continue;
307     }
308     if ((entry->flags & SP_PR_READ) != 0) {
309       fdsets |= SP_PR_READ;
310       FD_SET((unsigned int)entry->fd, &ibits);  /* And we cast here since we get a warning on Win32 */
311     }
312     if ((entry->flags & SP_PR_WRITE) != 0) {
313       fdsets |= SP_PR_WRITE;
314       FD_SET((unsigned int)entry->fd, &obits);  /* And we cast here since we get a warning on Win32 */
315     }
316     if ((entry->flags & (SP_PR_READ | SP_PR_WRITE)) != 0 && entry->fd >= hfd) {
317       hfd = entry->fd + 1;
318     }
319   }
320
321   /* Running select on the FD set */
322   do {
323     n = os_select(hfd, fdsets & SP_PR_READ ? &ibits : NULL, fdsets & SP_PR_WRITE ? &obits : NULL, NULL, &tvp);
324   } while (n == -1 && errno == EINTR);
325
326   if (n == 0) {
327     return;
328   }
329   if (n == -1) {                /* Did something go wrong? */
330     OLSR_WARN(LOG_SCHEDULER, "select error: %s", strerror(errno));
331     return;
332   }
333
334   /* Update time since this is much used by the parsing functions */
335   now_times = olsr_times();
336   OLSR_FOR_ALL_SOCKETS(entry, iterator) {
337     int flags;
338     if (entry->process_pollrate == NULL) {
339       continue;
340     }
341     flags = 0;
342     if (FD_ISSET(entry->fd, &ibits)) {
343       flags |= SP_PR_READ;
344     }
345     if (FD_ISSET(entry->fd, &obits)) {
346       flags |= SP_PR_WRITE;
347     }
348
349     if (flags) {
350       OLSR_DEBUG(LOG_SCHEDULER, "Event from socket %d (%d)", entry->fd, flags);
351     }
352
353     if (flags != 0) {
354       entry->process_pollrate(entry->fd, entry->data, flags);
355     }
356   }
357 }
358
359 static void
360 handle_fds(uint32_t next_interval)
361 {
362   struct olsr_socket_entry *entry;
363   struct list_iterator iterator;
364   struct timeval tvp;
365   int32_t remaining;
366
367   /* calculate the first timeout */
368   now_times = olsr_times();
369
370   remaining = TIME_DUE(next_interval);
371   if (remaining <= 0) {
372     /* we are already over the interval */
373     if (list_is_empty(&socket_head)) {
374       /* If there are no registered sockets we do not call select(2) */
375       return;
376     }
377     tvp.tv_sec = 0;
378     tvp.tv_usec = 0;
379   } else {
380     /* we need an absolute time - milliseconds */
381     tvp.tv_sec = remaining / MSEC_PER_SEC;
382     tvp.tv_usec = (remaining % MSEC_PER_SEC) * USEC_PER_MSEC;
383   }
384
385   /* do at least one select */
386   for (;;) {
387     fd_set ibits, obits;
388     int n, hfd = 0, fdsets = 0;
389     FD_ZERO(&ibits);
390     FD_ZERO(&obits);
391
392     /* Adding file-descriptors to FD set */
393     OLSR_FOR_ALL_SOCKETS(entry, iterator) {
394       if (entry->process_immediate == NULL) {
395         continue;
396       }
397       if ((entry->flags & SP_IMM_READ) != 0) {
398         fdsets |= SP_IMM_READ;
399         FD_SET((unsigned int)entry->fd, &ibits);        /* And we cast here since we get a warning on Win32 */
400       }
401       if ((entry->flags & SP_IMM_WRITE) != 0) {
402         fdsets |= SP_IMM_WRITE;
403         FD_SET((unsigned int)entry->fd, &obits);        /* And we cast here since we get a warning on Win32 */
404       }
405       if ((entry->flags & (SP_IMM_READ | SP_IMM_WRITE)) != 0 && entry->fd >= hfd) {
406         hfd = entry->fd + 1;
407       }
408     }
409
410     if (hfd == 0 && (long)remaining <= 0) {
411       /* we are over the interval and we have no fd's. Skip the select() etc. */
412       return;
413     }
414
415     do {
416       n = os_select(hfd, fdsets & SP_IMM_READ ? &ibits : NULL, fdsets & SP_IMM_WRITE ? &obits : NULL, NULL, &tvp);
417     } while (n == -1 && errno == EINTR);
418
419     if (n == 0) {               /* timeout! */
420       break;
421     }
422     if (n == -1) {              /* Did something go wrong? */
423       OLSR_WARN(LOG_SCHEDULER, "select error: %s", strerror(errno));
424       break;
425     }
426
427     /* Update time since this is much used by the parsing functions */
428     now_times = olsr_times();
429     OLSR_FOR_ALL_SOCKETS(entry, iterator) {
430       int flags;
431       if (entry->process_immediate == NULL) {
432         continue;
433       }
434       flags = 0;
435       if (FD_ISSET(entry->fd, &ibits)) {
436         flags |= SP_IMM_READ;
437       }
438       if (FD_ISSET(entry->fd, &obits)) {
439         flags |= SP_IMM_WRITE;
440       }
441       if (flags != 0) {
442         entry->process_immediate(entry->fd, entry->data, flags);
443       }
444     }
445
446     /* calculate the next timeout */
447     remaining = TIME_DUE(next_interval);
448     if (remaining <= 0) {
449       /* we are already over the interval */
450       break;
451     }
452     /* we need an absolute time - milliseconds */
453     tvp.tv_sec = remaining / MSEC_PER_SEC;
454     tvp.tv_usec = (remaining % MSEC_PER_SEC) * USEC_PER_MSEC;
455   }
456
457   OLSR_FOR_ALL_SOCKETS(entry, iterator) {
458     if (entry->process_immediate == NULL && entry->process_pollrate == NULL) {
459       /* clean up socket handler */
460       list_remove(&entry->socket_node);
461       free(entry);
462     }
463   }
464 }
465
466 /**
467  * Main scheduler event loop. Polls at every
468  * sched_poll_interval and calls all functions
469  * that are timed out or that are triggered.
470  * Also calls the olsr_process_changes()
471  * function at every poll.
472  *
473  * @return nada
474  */
475 void
476 olsr_scheduler(void)
477 {
478   OLSR_INFO(LOG_SCHEDULER, "Scheduler started - polling every %u ms\n", olsr_cnf->pollrate);
479
480   /* Main scheduler loop */
481   while (app_state == STATE_RUNNING) {
482     uint32_t next_interval;
483
484     /*
485      * Update the global timestamp. We are using a non-wallclock timer here
486      * to avoid any undesired side effects if the system clock changes.
487      */
488     now_times = olsr_times();
489     next_interval = GET_TIMESTAMP(olsr_cnf->pollrate);
490
491     /* Read incoming data */
492     poll_sockets();
493
494     /* Process timers */
495     walk_timers(&timer_last_run);
496
497     /* Update */
498     olsr_process_changes();
499
500     /* Check for changes in topology */
501     if (link_changes) {
502       increase_local_ansn_number();
503       OLSR_DEBUG(LOG_SCHEDULER, "ANSN UPDATED %d\n\n", get_local_ansn_number());
504       link_changes = false;
505     }
506
507     /* Read incoming data and handle it immediiately */
508     handle_fds(next_interval);
509   }
510 }
511
512 /**
513  * Decrement a relative timer by a random number range.
514  *
515  * @param the relative timer expressed in units of milliseconds.
516  * @param the jitter in percent
517  * @param cached result of random() at system init.
518  * @return the absolute timer in system clock tick units
519  */
520 static uint32_t
521 calc_jitter(unsigned int rel_time, uint8_t jitter_pct, unsigned int random_val)
522 {
523   unsigned int jitter_time;
524
525   /*
526    * No jitter or, jitter larger than 99% does not make sense.
527    * Also protect against overflows resulting from > 25 bit timers.
528    */
529   if (jitter_pct == 0 || jitter_pct > 99 || rel_time > (1 << 24)) {
530     return GET_TIMESTAMP(rel_time);
531   }
532
533   /*
534    * Play some tricks to avoid overflows with integer arithmetic.
535    */
536   jitter_time = (jitter_pct * rel_time) / 100;
537   jitter_time = random_val / (1 + RAND_MAX / (jitter_time + 1));
538
539   OLSR_DEBUG(LOG_TIMER, "TIMER: jitter %u%% rel_time %ums to %ums\n", jitter_pct, rel_time, rel_time - jitter_time);
540
541   return GET_TIMESTAMP(rel_time - jitter_time);
542 }
543
544 /**
545  * Init datastructures for maintaining timers.
546  */
547 void
548 olsr_init_timers(void)
549 {
550   int idx;
551
552   OLSR_INFO(LOG_SCHEDULER, "Initializing scheduler.\n");
553
554   /* Grab initial timestamp */
555   if (os_gettimeofday(&first_tv, NULL)) {
556     OLSR_ERROR(LOG_TIMER, "OS clock is not working, have to shut down OLSR (%s)\n", strerror(errno));
557     olsr_exit(1);
558   }
559   last_tv = first_tv;
560   now_times = olsr_times();
561
562   /* init lists */
563   list_init_head(&socket_head);
564   for (idx = 0; idx < TIMER_WHEEL_SLOTS; idx++) {
565     list_init_head(&timer_wheel[idx]);
566   }
567
568   /*
569    * Reset the last timer run.
570    */
571   timer_last_run = now_times;
572
573   /* Allocate a cookie for the block based memory manager. */
574   timer_mem_cookie = olsr_create_memcookie("timer_entry", sizeof(struct timer_entry));
575
576   avl_init(&timerinfo_tree, avl_comp_strcasecmp, false, NULL);
577   timerinfo_cookie = olsr_create_memcookie("timerinfo", sizeof(struct olsr_timer_info));
578 }
579
580 /**
581  * Walk through the timer list and check if any timer is ready to fire.
582  * Callback the provided function with the context pointer.
583  */
584 static void
585 walk_timers(uint32_t * last_run)
586 {
587   unsigned int total_timers_walked = 0, total_timers_fired = 0;
588   unsigned int wheel_slot_walks = 0;
589
590   /*
591    * Check the required wheel slots since the last time a timer walk was invoked,
592    * or check *all* the wheel slots, whatever is less work.
593    * The latter is meant as a safety belt if the scheduler falls behind.
594    */
595   while ((*last_run <= now_times) && (wheel_slot_walks < TIMER_WHEEL_SLOTS)) {
596     struct list_entity tmp_head_node;
597     /* keep some statistics */
598     unsigned int timers_walked = 0, timers_fired = 0;
599
600     /* Get the hash slot for this clocktick */
601     struct list_entity *timer_head_node;
602
603     timer_head_node = &timer_wheel[*last_run & TIMER_WHEEL_MASK];
604
605     /* Walk all entries hanging off this hash bucket. We treat this basically as a stack
606      * so that we always know if and where the next element is.
607      */
608     list_init_head(&tmp_head_node);
609     while (!list_is_empty(timer_head_node)) {
610       /* the top element */
611       struct timer_entry *timer;
612
613       timer = list_first_element(timer_head_node, timer, timer_list);
614
615       /*
616        * Dequeue and insert to a temporary list.
617        * We do this to avoid loosing our walking context when
618        * multiple timers fire.
619        */
620       list_remove(&timer->timer_list);
621       list_add_after(&tmp_head_node, &timer->timer_list);
622       timers_walked++;
623
624       /* Ready to fire ? */
625       if (TIMED_OUT(timer->timer_clock)) {
626         OLSR_DEBUG(LOG_TIMER, "TIMER: fire %s timer %p, ctx %p, "
627                    "at clocktick %u (%s)\n",
628                    timer->timer_info->name,
629                    timer, timer->timer_cb_context, (unsigned int)*last_run, olsr_wallclock_string());
630
631         /* This timer is expired, call into the provided callback function */
632         timer->timer_in_callback = true;
633         timer->timer_info->callback(timer->timer_cb_context);
634         timer->timer_in_callback = false;
635         timer->timer_info->changes++;
636
637         /* Only act on actually running timers */
638         if (timer->timer_running) {
639           /*
640            * Don't restart the periodic timer if the callback function has
641            * stopped the timer.
642            */
643           if (timer->timer_period) {
644             /* For periodical timers, rehash the random number and restart */
645             timer->timer_random = random();
646             olsr_change_timer(timer, timer->timer_period, timer->timer_jitter_pct);
647           } else {
648             /* Singleshot timers are stopped */
649             olsr_stop_timer(timer);
650           }
651         }
652         else {
653           /* free memory */
654           olsr_cookie_free(timer_mem_cookie, timer);
655         }
656
657         timers_fired++;
658       }
659     }
660
661     /*
662      * Now merge the temporary list back to the old bucket.
663      */
664     list_merge(timer_head_node, &tmp_head_node);
665
666     /* keep some statistics */
667     total_timers_walked += timers_walked;
668     total_timers_fired += timers_fired;
669
670     /* Increment the time slot and wheel slot walk iteration */
671     (*last_run)++;
672     wheel_slot_walks++;
673   }
674
675   OLSR_DEBUG(LOG_TIMER, "TIMER: processed %4u/%d clockwheel slots, "
676              "timers walked %4u/%u, timers fired %u\n",
677              wheel_slot_walks, TIMER_WHEEL_SLOTS, total_timers_walked, timer_mem_cookie->ci_usage, total_timers_fired);
678
679   /*
680    * If the scheduler has slipped and we have walked all wheel slots,
681    * reset the last timer run.
682    */
683   *last_run = now_times;
684 }
685
686 /**
687  * Stop and delete all timers.
688  */
689 void
690 olsr_flush_timers(void)
691 {
692   struct olsr_timer_info *ti;
693   struct list_iterator iterator;
694
695   struct list_entity *timer_head_node;
696   unsigned int wheel_slot = 0;
697
698   for (wheel_slot = 0; wheel_slot < TIMER_WHEEL_SLOTS; wheel_slot++) {
699     timer_head_node = &timer_wheel[wheel_slot & TIMER_WHEEL_MASK];
700
701     /* Kill all entries hanging off this hash bucket. */
702     while (!list_is_empty(timer_head_node)) {
703       struct timer_entry *timer;
704
705       timer = list_first_element(timer_head_node, timer, timer_list);
706       olsr_stop_timer(timer);
707     }
708   }
709
710   /* free all timerinfos */
711   OLSR_FOR_ALL_TIMERS(ti, iterator) {
712     avl_delete(&timerinfo_tree, &ti->node);
713     free(ti->name);
714     olsr_cookie_free(timerinfo_cookie, ti);
715   }
716
717   /* release memory cookie for timers */
718   olsr_cleanup_memcookie(timerinfo_cookie);
719 }
720
721 /**
722  * Returns the difference between gmt and local time in seconds.
723  * Use gmtime() and localtime() to keep things simple.
724  *
725  * taken and slightly modified from www.tcpdump.org.
726  */
727 static int
728 olsr_get_timezone(void)
729 {
730 #define OLSR_TIMEZONE_UNINITIALIZED -1
731   static int time_diff = OLSR_TIMEZONE_UNINITIALIZED;
732   if (time_diff == OLSR_TIMEZONE_UNINITIALIZED) {
733     int dir;
734     const time_t t = time(NULL);
735     const struct tm gmt = *gmtime(&t);
736     const struct tm *loc = localtime(&t);
737
738     time_diff = (loc->tm_hour - gmt.tm_hour) * 60 * 60 + (loc->tm_min - gmt.tm_min) * 60;
739
740     /*
741      * If the year or julian day is different, we span 00:00 GMT
742      * and must add or subtract a day. Check the year first to
743      * avoid problems when the julian day wraps.
744      */
745     dir = loc->tm_year - gmt.tm_year;
746     if (!dir) {
747       dir = loc->tm_yday - gmt.tm_yday;
748     }
749
750     time_diff += dir * 24 * 60 * 60;
751   }
752   return time_diff;
753 }
754
755 /**
756  * Format an absolute wallclock system time string.
757  * May be called upto 4 times in a single printf() statement.
758  * Displays microsecond resolution.
759  *
760  * @return buffer to a formatted system time string.
761  */
762 const char *
763 olsr_wallclock_string(void)
764 {
765   static char buf[sizeof("00:00:00.000000")];
766   struct timeval now;
767   int sec, usec;
768
769   os_gettimeofday(&now, NULL);
770
771   sec = (int)now.tv_sec + olsr_get_timezone();
772   usec = (int)now.tv_usec;
773
774   snprintf(buf, sizeof(buf), "%02d:%02d:%02d.%06d", (sec % 86400) / 3600, (sec % 3600) / 60, sec % 60, usec);
775
776   return buf;
777 }
778
779 /**
780  * Format an relative non-wallclock system time string.
781  * May be called upto 4 times in a single printf() statement.
782  * Displays millisecond resolution.
783  *
784  * @param absolute time expressed in clockticks
785  * @return buffer to a formatted system time string.
786  */
787 const char *
788 olsr_clock_string(uint32_t clk)
789 {
790   static char buf[sizeof("00:00:00.000")];
791
792   /* On most systems a clocktick is a 10ms quantity. */
793   unsigned int msec = clk % 1000;
794   unsigned int sec = clk / 1000;
795
796   snprintf(buf, sizeof(buf), "%02u:%02u:%02u.%03u", sec / 3600, (sec % 3600) / 60, (sec % 60), (msec % MSEC_PER_SEC));
797
798   return buf;
799 }
800
801 /**
802  * Start a new timer.
803  *
804  * @param relative time expressed in milliseconds
805  * @param jitter expressed in percent
806  * @param timer callback function
807  * @param context for the callback function
808  * @return a pointer to the created entry
809  */
810 struct timer_entry *
811 olsr_start_timer(unsigned int rel_time,
812                  uint8_t jitter_pct, void *context, struct olsr_timer_info *ti)
813 {
814   struct timer_entry *timer;
815
816   assert(ti != 0);          /* we want timer cookies everywhere */
817   assert(rel_time);
818   assert(jitter_pct <= 100);
819
820   timer = olsr_cookie_malloc(timer_mem_cookie);
821
822   /*
823    * Compute random numbers only once.
824    */
825   if (!timer->timer_random) {
826     timer->timer_random = random();
827   }
828
829   /* Fill entry */
830   timer->timer_clock = calc_jitter(rel_time, jitter_pct, timer->timer_random);
831   timer->timer_cb_context = context;
832   timer->timer_jitter_pct = jitter_pct;
833   timer->timer_running = true;
834
835   /* The cookie is used for debugging to traceback the originator */
836   timer->timer_info = ti;
837   ti->usage++;
838   ti->changes++;
839
840   /* Singleshot or periodical timer ? */
841   timer->timer_period = ti->periodic ? rel_time : 0;
842
843   /*
844    * Now insert in the respective timer_wheel slot.
845    */
846   list_add_before(&timer_wheel[timer->timer_clock & TIMER_WHEEL_MASK], &timer->timer_list);
847
848   OLSR_DEBUG(LOG_TIMER, "TIMER: start %s timer %p firing in %s, ctx %p\n",
849              ti->name, timer, olsr_clock_string(timer->timer_clock), context);
850
851   return timer;
852 }
853 #include "valgrind/valgrind.h"
854
855 /**
856  * Delete a timer.
857  *
858  * @param the timer_entry that shall be removed
859  * @return nada
860  */
861 void
862 olsr_stop_timer(struct timer_entry *timer)
863 {
864   /* It's okay to get a NULL here */
865   if (timer == NULL) {
866     return;
867   }
868
869   assert(timer->timer_info);     /* we want timer cookies everywhere */
870   assert(timer->timer_list.next != NULL && timer->timer_list.prev != NULL);
871
872   OLSR_DEBUG(LOG_TIMER, "TIMER: stop %s timer %p, ctx %p\n",
873              timer->timer_info->name, timer, timer->timer_cb_context);
874
875
876   /*
877    * Carve out of the existing wheel_slot and free.
878    */
879   list_remove(&timer->timer_list);
880   timer->timer_running = false;
881   timer->timer_info->usage--;
882   timer->timer_info->changes++;
883
884   if (!timer->timer_in_callback) {
885     olsr_cookie_free(timer_mem_cookie, timer);
886   }
887 }
888
889 /**
890  * Change a timer_entry.
891  *
892  * @param timer_entry to be changed.
893  * @param new relative time expressed in units of milliseconds.
894  * @param new jitter expressed in percent.
895  * @return nada
896  */
897 void
898 olsr_change_timer(struct timer_entry *timer, unsigned int rel_time, uint8_t jitter_pct)
899 {
900   /* Sanity check. */
901   if (!timer) {
902     return;
903   }
904
905   assert(timer->timer_info);     /* we want timer cookies everywhere */
906
907   /* Singleshot or periodical timer ? */
908   timer->timer_period = timer->timer_info->periodic ? rel_time : 0;
909
910   timer->timer_clock = calc_jitter(rel_time, jitter_pct, timer->timer_random);
911   timer->timer_jitter_pct = jitter_pct;
912
913   /*
914    * Changes are easy: Remove timer from the exisiting timer_wheel slot
915    * and reinsert into the new slot.
916    */
917   list_remove(&timer->timer_list);
918   list_add_before(&timer_wheel[timer->timer_clock & TIMER_WHEEL_MASK], &timer->timer_list);
919
920   OLSR_DEBUG(LOG_TIMER, "TIMER: change %s timer %p, firing to %s, ctx %p\n",
921              timer->timer_info->name, timer,
922              olsr_clock_string(timer->timer_clock), timer->timer_cb_context);
923 }
924
925 /*
926  * This is the one stop shop for all sort of timer manipulation.
927  * Depending on the paseed in parameters a new timer is started,
928  * or an existing timer is started or an existing timer is
929  * terminated.
930  */
931 void
932 olsr_set_timer(struct timer_entry **timer_ptr,
933                unsigned int rel_time,
934                uint8_t jitter_pct, void *context, struct olsr_timer_info *ti)
935 {
936   assert(ti);          /* we want timer cookies everywhere */
937   if (rel_time == 0) {
938     /* No good future time provided, kill it. */
939     olsr_stop_timer(*timer_ptr);
940     *timer_ptr = NULL;
941   }
942   else if ((*timer_ptr) == NULL) {
943     /* No timer running, kick it. */
944     *timer_ptr = olsr_start_timer(rel_time, jitter_pct, context, ti);
945   }
946   else {
947     olsr_change_timer(*timer_ptr, rel_time, jitter_pct);
948   }
949 }
950
951 /*
952  * Local Variables:
953  * c-basic-offset: 2
954  * indent-tabs-mode: nil
955  * End:
956  */