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