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