all: ensure unsigned numbers are used in shifts
[olsrd.git] / src / scheduler.c
1 /*
2  * The olsr.org Optimized Link-State Routing daemon (olsrd)
3  *
4  * (c) by the OLSR project
5  *
6  * See our Git repository to find out who worked on this file
7  * and thus is a copyright holder on it.
8  *
9  * All rights reserved.
10  *
11  * Redistribution and use in source and binary forms, with or without
12  * modification, are permitted provided that the following conditions
13  * are met:
14  *
15  * * Redistributions of source code must retain the above copyright
16  *   notice, this list of conditions and the following disclaimer.
17  * * Redistributions in binary form must reproduce the above copyright
18  *   notice, this list of conditions and the following disclaimer in
19  *   the documentation and/or other materials provided with the
20  *   distribution.
21  * * Neither the name of olsr.org, olsrd nor the names of its
22  *   contributors may be used to endorse or promote products derived
23  *   from this software without specific prior written permission.
24  *
25  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
26  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
27  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
28  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
29  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
30  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
31  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
32  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
33  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
34  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
35  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
36  * POSSIBILITY OF SUCH DAMAGE.
37  *
38  * Visit http://www.olsr.org for more information.
39  *
40  * If you find this software useful feel free to make a donation
41  * to the project. For more information see the website or contact
42  * the copyright holders.
43  *
44  */
45
46 #include "scheduler.h"
47 #include "log.h"
48 #include "link_set.h"
49 #include "olsr.h"
50 #include "olsr_cookie.h"
51 #include "net_os.h"
52 #include "mpr_selector_set.h"
53 #include "olsr_random.h"
54 #include "common/avl.h"
55
56 #include <sys/times.h>
57
58 #include <unistd.h>
59 #include <assert.h>
60 #include <time.h>
61
62 #ifdef _WIN32
63 #define close(x) closesocket(x)
64 #endif /* _WIN32 */
65
66 /* Timer data, global. Externed in scheduler.h */
67 uint32_t now_times;                    /* relative time compared to startup (in milliseconds) */
68 struct timespec first_tv;              /* timevalue during startup */
69 struct timespec last_tv;               /* timevalue used for last olsr_times() calculation */
70
71 /* Hashed root of all timers */
72 static struct list_node timer_wheel[TIMER_WHEEL_SLOTS];
73 static uint32_t timer_last_run;        /* remember the last timeslot walk */
74
75 /* Memory cookie for the block based memory manager */
76 static struct olsr_cookie_info *timer_mem_cookie = NULL;
77
78 /* Head of all OLSR used sockets */
79 static struct list_node socket_head = { &socket_head, &socket_head };
80
81 /* Prototypes */
82 static void walk_timers(uint32_t *);
83 static void walk_timers_cleanup(void);
84 static void poll_sockets(void);
85 static uint32_t calc_jitter(unsigned int rel_time, uint8_t jitter_pct, unsigned int random_val);
86 static void olsr_cleanup_timer(struct timer_entry *timer);
87
88 struct avl_tree timer_cleanup_tree;
89
90 struct timer_cleanup_entry {
91   struct avl_node avl;
92   struct timer_entry * timer;
93 };
94
95 /* static inline struct timer_cleanup_entry * node2timercleanup(struct avl_node *ptr) */
96 AVLNODE2STRUCT(node2timercleanup, struct timer_cleanup_entry, avl);
97
98 /**
99  * Loop over all timer cleanup entries and put the iterated entry in timer
100  */
101 #define OLSR_FOR_ALL_TIMERS_CLEANUP(timer) \
102 { \
103   struct avl_node *timer_avl_node, *timer_avl_node_next; \
104   for (timer_avl_node = avl_walk_first(&timer_cleanup_tree); \
105   timer_avl_node; timer_avl_node = timer_avl_node_next) { \
106           timer_avl_node_next = avl_walk_next(timer_avl_node); \
107     timer = node2timercleanup(timer_avl_node);
108 #define OLSR_FOR_ALL_TIMER_CLEANUP_END(timer) }}
109
110 static int avl_comp_timer(const void *entry1, const void *entry2) {
111   if (entry1 < entry2) {
112     return -1;
113   }
114
115   if (entry1 > entry2) {
116     return 1;
117   }
118
119   return 0;
120 }
121
122 /*
123  * A wrapper around times(2). Note, that this function has some
124  * portability problems, so do not rely on absolute values returned.
125  * Under Linux, uclibc and libc directly call the sys_times() located
126  * in kernel/sys.c and will only return an error if the tms_buf is
127  * not writeable.
128  */
129 uint32_t
130 olsr_times(void)
131 {
132   struct timespec tv;
133
134   if (clock_gettime(CLOCK_MONOTONIC, &tv) != 0) {
135     olsr_exit("OS clock is not working, have to shut down OLSR", EXIT_FAILURE);
136   }
137
138   /* test if time jumped backward or more than 60 seconds forward */
139   if ((tv.tv_sec < last_tv.tv_sec) //
140       || ((tv.tv_sec == last_tv.tv_sec) //
141           && tv.tv_nsec < last_tv.tv_nsec) //
142       || ((tv.tv_sec - last_tv.tv_sec) > 60)) {
143     uint64_t nsec;
144
145     OLSR_PRINTF(1, "Time jump (%ld.%09ld to %ld.%09ld)\n", //
146         (long int) last_tv.tv_sec,//
147         (long int) last_tv.tv_nsec,//
148         (long int) tv.tv_sec,//
149         (long int) tv.tv_nsec);
150
151     nsec = (last_tv.tv_sec - first_tv.tv_sec) * 1000000000 + (last_tv.tv_nsec - first_tv.tv_nsec);
152     nsec += 1000000; /* advance time by one millisecond */
153
154     first_tv = tv;
155     first_tv.tv_sec -= (nsec / 1000000000);
156     first_tv.tv_nsec -= (nsec % 1000000000);
157
158     if (first_tv.tv_nsec < 0) {
159       first_tv.tv_sec--;
160       first_tv.tv_nsec += 1000000000;
161     }
162     last_tv = tv;
163     return (nsec / 1000000);
164   }
165
166   last_tv = tv;
167   return (uint32_t)((tv.tv_sec - first_tv.tv_sec) * 1000 + (tv.tv_nsec - first_tv.tv_nsec) / 1000000);
168 }
169
170 /**
171  * Returns a timestamp s seconds in the future
172  */
173 uint32_t
174 olsr_getTimestamp(uint32_t s)
175 {
176   return now_times + s;
177 }
178
179 /**
180  * Returns the number of milliseconds until the timestamp will happen
181  */
182
183 int32_t
184 olsr_getTimeDue(uint32_t s)
185 {
186   uint32_t diff;
187   if (s > now_times) {
188     diff = s - now_times;
189
190     /* overflow ? */
191     if (diff > (1u << 31)) {
192       return -(int32_t) (0xffffffff - diff);
193     }
194     return (int32_t) (diff);
195   }
196
197   diff = now_times - s;
198   /* overflow ? */
199   if (diff > (1u << 31)) {
200     return (int32_t) (0xffffffff - diff);
201   }
202   return -(int32_t) (diff);
203 }
204
205 bool
206 olsr_isTimedOut(uint32_t s)
207 {
208   if (s > now_times) {
209     return s - now_times > (1u << 31);
210   }
211
212   return now_times - s <= (1u << 31);
213 }
214
215 /**
216  * Add a socket and handler to the socketset
217  * beeing used in the main select(2) loop
218  * in listen_loop
219  *
220  *@param fd the socket
221  *@param pf_pr the processing function
222  *@param pf_imm the (immediate) processing function
223  *@param data the data pointer for the processing function
224  *@param flags the flags for the processing function
225  */
226 void
227 add_olsr_socket(int fd, socket_handler_func pf_pr, socket_handler_func pf_imm, void *data, unsigned int flags)
228 {
229   struct olsr_socket_entry *new_entry;
230
231   if (fd < 0 || (pf_pr == NULL && pf_imm == NULL)) {
232     OLSR_PRINTF(1, "Bogus socket entry - not registering...");
233     return;
234   }
235   OLSR_PRINTF(3, "Adding OLSR socket entry %d\n", fd);
236
237   new_entry = olsr_malloc(sizeof(*new_entry), "Socket entry");
238
239   new_entry->fd = fd;
240   new_entry->process_immediate = pf_imm;
241   new_entry->process_pollrate = pf_pr;
242   new_entry->data = data;
243   new_entry->flags = flags;
244
245   /* Queue */
246   list_node_init(&new_entry->socket_node);
247   list_add_before(&socket_head, &new_entry->socket_node);
248 }
249
250 /**
251  * Remove a socket and handler to the socketset
252  * beeing used in the main select(2) loop
253  * in listen_loop
254  *
255  *@param fd the socket
256  *@param pf_pr the processing function
257  *@param pf_imm the (immediate) processing function
258  */
259 int
260 remove_olsr_socket(int fd, socket_handler_func pf_pr, socket_handler_func pf_imm)
261 {
262   struct olsr_socket_entry *entry;
263
264   if (fd < 0 || (pf_pr == NULL && pf_imm == NULL)) {
265     OLSR_PRINTF(1, "Bogus socket entry - not processing...");
266     return 0;
267   }
268   OLSR_PRINTF(3, "Removing OLSR socket entry %d\n", fd);
269
270   OLSR_FOR_ALL_SOCKETS(entry) {
271     if (entry->fd == fd && entry->process_immediate == pf_imm && entry->process_pollrate == pf_pr) {
272       /* just mark this node as "deleted", it will be cleared later at the end of handle_fds() */
273       entry->process_immediate = NULL;
274       entry->process_pollrate = NULL;
275       entry->flags = 0;
276       return 1;
277     }
278   }
279   OLSR_FOR_ALL_SOCKETS_END(entry);
280   return 0;
281 }
282
283 void
284 enable_olsr_socket(int fd, socket_handler_func pf_pr, socket_handler_func pf_imm, unsigned int flags)
285 {
286   struct olsr_socket_entry *entry;
287
288   OLSR_FOR_ALL_SOCKETS(entry) {
289     if (entry->fd == fd && entry->process_immediate == pf_imm && entry->process_pollrate == pf_pr) {
290       entry->flags |= flags;
291     }
292   }
293   OLSR_FOR_ALL_SOCKETS_END(entry);
294 }
295
296 void
297 disable_olsr_socket(int fd, socket_handler_func pf_pr, socket_handler_func pf_imm, unsigned int flags)
298 {
299   struct olsr_socket_entry *entry;
300
301   OLSR_FOR_ALL_SOCKETS(entry) {
302     if (entry->fd == fd && entry->process_immediate == pf_imm && entry->process_pollrate == pf_pr) {
303       entry->flags &= ~flags;
304     }
305   }
306   OLSR_FOR_ALL_SOCKETS_END(entry);
307 }
308
309 /**
310  * Close and free all sockets.
311  */
312 void
313 olsr_flush_sockets(void)
314 {
315   struct olsr_socket_entry *entry;
316
317   OLSR_FOR_ALL_SOCKETS(entry) {
318     close(entry->fd);
319     list_remove(&entry->socket_node);
320     free(entry);
321   } OLSR_FOR_ALL_SOCKETS_END(entry);
322 }
323
324 static void
325 poll_sockets(void)
326 {
327   int n;
328   struct olsr_socket_entry *entry;
329   fd_set ibits, obits;
330   struct timeval tvp = { 0, 0 };
331   int hfd = 0, fdsets = 0;
332
333   /* If there are no registered sockets we
334    * do not call select(2)
335    */
336   if (list_is_empty(&socket_head)) {
337     return;
338   }
339
340   FD_ZERO(&ibits);
341   FD_ZERO(&obits);
342
343   /* Adding file-descriptors to FD set */
344   OLSR_FOR_ALL_SOCKETS(entry) {
345     if (entry->process_pollrate == NULL) {
346       continue;
347     }
348     if ((entry->flags & SP_PR_READ) != 0) {
349       fdsets |= SP_PR_READ;
350       FD_SET((unsigned int)entry->fd, &ibits);  /* And we cast here since we get a warning on Win32 */
351     }
352     if ((entry->flags & SP_PR_WRITE) != 0) {
353       fdsets |= SP_PR_WRITE;
354       FD_SET((unsigned int)entry->fd, &obits);  /* And we cast here since we get a warning on Win32 */
355     }
356     if ((entry->flags & (SP_PR_READ | SP_PR_WRITE)) != 0 && entry->fd >= hfd) {
357       hfd = entry->fd + 1;
358     }
359   }
360   OLSR_FOR_ALL_SOCKETS_END(entry);
361
362   /* Running select on the FD set */
363   do {
364     n = olsr_select(hfd, fdsets & SP_PR_READ ? &ibits : NULL, fdsets & SP_PR_WRITE ? &obits : NULL, NULL, &tvp);
365   } while (n == -1 && errno == EINTR);
366
367   if (n == 0) {
368     return;
369   }
370   if (n == -1) {                /* Did something go wrong? */
371     OLSR_PRINTF(1, "select error: %s", strerror(errno));
372     return;
373   }
374
375   /* Update time since this is much used by the parsing functions */
376   now_times = olsr_times();
377   OLSR_FOR_ALL_SOCKETS(entry) {
378     int flags;
379     if (entry->process_pollrate == NULL) {
380       continue;
381     }
382     flags = 0;
383     if (FD_ISSET(entry->fd, &ibits)) {
384       flags |= SP_PR_READ;
385     }
386     if (FD_ISSET(entry->fd, &obits)) {
387       flags |= SP_PR_WRITE;
388     }
389     if (flags != 0) {
390       entry->process_pollrate(entry->fd, entry->data, flags);
391     }
392   }
393   OLSR_FOR_ALL_SOCKETS_END(entry);
394 }
395
396 static void
397 handle_fds(uint32_t next_interval)
398 {
399   struct olsr_socket_entry *entry;
400   struct timeval tvp;
401   int32_t remaining;
402
403   /* calculate the first timeout */
404   now_times = olsr_times();
405
406   remaining = TIME_DUE(next_interval);
407   if (remaining <= 0) {
408     /* we are already over the interval */
409     if (list_is_empty(&socket_head)) {
410       /* If there are no registered sockets we do not call select(2) */
411       return;
412     }
413     tvp.tv_sec = 0;
414     tvp.tv_usec = 0;
415   } else {
416     /* we need an absolute time - milliseconds */
417     tvp.tv_sec = remaining / MSEC_PER_SEC;
418     tvp.tv_usec = (remaining % MSEC_PER_SEC) * USEC_PER_MSEC;
419   }
420
421   /* do at least one select */
422   for (;;) {
423     fd_set ibits, obits;
424     int n, hfd = 0, fdsets = 0;
425     FD_ZERO(&ibits);
426     FD_ZERO(&obits);
427
428     /* Adding file-descriptors to FD set */
429     OLSR_FOR_ALL_SOCKETS(entry) {
430       if (entry->process_immediate == NULL) {
431         continue;
432       }
433       if ((entry->flags & SP_IMM_READ) != 0) {
434         fdsets |= SP_IMM_READ;
435         FD_SET((unsigned int)entry->fd, &ibits);        /* And we cast here since we get a warning on Win32 */
436       }
437       if ((entry->flags & SP_IMM_WRITE) != 0) {
438         fdsets |= SP_IMM_WRITE;
439         FD_SET((unsigned int)entry->fd, &obits);        /* And we cast here since we get a warning on Win32 */
440       }
441       if ((entry->flags & (SP_IMM_READ | SP_IMM_WRITE)) != 0 && entry->fd >= hfd) {
442         hfd = entry->fd + 1;
443       }
444     }
445     OLSR_FOR_ALL_SOCKETS_END(entry);
446
447     if (hfd == 0 && (long)remaining <= 0) {
448       /* we are over the interval and we have no fd's. Skip the select() etc. */
449       break;
450     }
451
452     do {
453       n = olsr_select(hfd, fdsets & SP_IMM_READ ? &ibits : NULL, fdsets & SP_IMM_WRITE ? &obits : NULL, NULL, &tvp);
454     } while (n == -1 && errno == EINTR);
455
456     if (n == 0) {               /* timeout! */
457       break;
458     }
459     if (n == -1) {              /* Did something go wrong? */
460       OLSR_PRINTF(1, "select error: %s", strerror(errno));
461       break;
462     }
463
464     /* Update time since this is much used by the parsing functions */
465     now_times = olsr_times();
466     OLSR_FOR_ALL_SOCKETS(entry) {
467       int flags;
468       if (entry->process_immediate == NULL) {
469         continue;
470       }
471       flags = 0;
472       if (FD_ISSET(entry->fd, &ibits)) {
473         flags |= SP_IMM_READ;
474       }
475       if (FD_ISSET(entry->fd, &obits)) {
476         flags |= SP_IMM_WRITE;
477       }
478       if (flags != 0) {
479         entry->process_immediate(entry->fd, entry->data, flags);
480       }
481     }
482     OLSR_FOR_ALL_SOCKETS_END(entry);
483
484     /* calculate the next timeout */
485     remaining = TIME_DUE(next_interval);
486     if (remaining <= 0) {
487       /* we are already over the interval */
488       break;
489     }
490     /* we need an absolute time - milliseconds */
491     tvp.tv_sec = remaining / MSEC_PER_SEC;
492     tvp.tv_usec = (remaining % MSEC_PER_SEC) * USEC_PER_MSEC;
493   }
494
495   OLSR_FOR_ALL_SOCKETS(entry) {
496     if (entry->process_immediate == NULL && entry->process_pollrate == NULL) {
497       /* clean up socket handler */
498       list_remove(&entry->socket_node);
499       free(entry);
500     }
501   } OLSR_FOR_ALL_SOCKETS_END(entry);
502 }
503
504 typedef enum {
505   INIT, RUNNING, STOPPING, ENDED
506 } state_t;
507
508 static volatile state_t state = INIT;
509
510 static bool olsr_scheduler_is_stopped(void) {
511   return ((state == INIT) || (state == ENDED));
512 }
513
514 void olsr_scheduler_stop(void) {
515   if (olsr_scheduler_is_stopped()) {
516     return;
517   }
518
519   state = STOPPING;
520 }
521
522 /**
523  * Main scheduler event loop. Polls at every
524  * sched_poll_interval and calls all functions
525  * that are timed out or that are triggered.
526  * Also calls the olsr_process_changes()
527  * function at every poll.
528  *
529  * @return nada
530  */
531 void olsr_scheduler(void)
532 {
533   state = RUNNING;
534   OLSR_PRINTF(1, "Scheduler started - polling every %d ms\n", (int)(olsr_cnf->pollrate*1000));
535
536   /* Main scheduler loop */
537   while (state == RUNNING) {
538     uint32_t next_interval;
539
540     /*
541      * Update the global timestamp. We are using a non-wallclock timer here
542      * to avoid any undesired side effects if the system clock changes.
543      */
544     now_times = olsr_times();
545     next_interval = GET_TIMESTAMP(olsr_cnf->pollrate * 1000);
546
547     /* Read incoming data */
548     poll_sockets();
549
550     if (state != RUNNING) {
551       break;
552     }
553
554     /* Process timers */
555     walk_timers(&timer_last_run);
556     walk_timers_cleanup();
557
558     if (state != RUNNING) {
559       break;
560     }
561
562     /* Update */
563     olsr_process_changes();
564
565     if (state != RUNNING) {
566       break;
567     }
568
569     /* Check for changes in topology */
570     if (link_changes) {
571       increase_local_ansn();
572       OLSR_PRINTF(3, "ANSN UPDATED %d\n\n", get_local_ansn());
573       link_changes = false;
574     }
575
576     if (state != RUNNING) {
577       break;
578     }
579
580     /* Read incoming data and handle it immediiately */
581     handle_fds(next_interval);
582   }
583   walk_timers_cleanup();
584
585   state = ENDED;
586 }
587
588 /**
589  * Decrement a relative timer by a random number range.
590  *
591  * @param rel_time the relative timer expressed in units of milliseconds.
592  * @param jitter_pct the jitter in percent
593  * @param random_val cached result of random() at system init.
594  * @return the absolute timer in system clock tick units
595  */
596 static uint32_t
597 calc_jitter(unsigned int rel_time, uint8_t jitter_pct, unsigned int random_val)
598 {
599   unsigned int jitter_time;
600
601   /*
602    * No jitter or, jitter larger than 99% does not make sense.
603    * Also protect against overflows resulting from > 25 bit timers.
604    */
605   if (jitter_pct == 0 || jitter_pct > 99 || rel_time > (1u << 24)) {
606     return GET_TIMESTAMP(rel_time);
607   }
608
609   /*
610    * Play some tricks to avoid overflows with integer arithmetic.
611    */
612   jitter_time = (jitter_pct * rel_time) / 100;
613   jitter_time = random_val / (1 + RAND_MAX / (jitter_time + 1));
614
615   OLSR_PRINTF(3, "TIMER: jitter %u%% rel_time %ums to %ums\n", jitter_pct, rel_time, rel_time - jitter_time);
616
617   return GET_TIMESTAMP(rel_time - jitter_time);
618 }
619
620 /**
621  * Init datastructures for maintaining timers.
622  */
623 void
624 olsr_init_timers(void)
625 {
626   int idx;
627
628   OLSR_PRINTF(3, "Initializing scheduler.\n");
629
630   /* Grab initial timestamp */
631   if (clock_gettime(CLOCK_MONOTONIC, &first_tv)) {
632     olsr_exit("OS clock is not working, have to shut down OLSR", EXIT_FAILURE);
633   }
634   last_tv = first_tv;
635   now_times = olsr_times();
636
637   avl_init(&timer_cleanup_tree, avl_comp_timer);
638
639   for (idx = 0; idx < TIMER_WHEEL_SLOTS; idx++) {
640     list_head_init(&timer_wheel[idx]);
641   }
642
643   /*
644    * Reset the last timer run.
645    */
646   timer_last_run = now_times;
647
648   /* Allocate a cookie for the block based memory manager. */
649   timer_mem_cookie = olsr_alloc_cookie("timer_entry", OLSR_COOKIE_TYPE_MEMORY);
650   olsr_cookie_set_memory_size(timer_mem_cookie, sizeof(struct timer_entry));
651 }
652
653 /**
654  * Walk through the timer list and check if any timer is ready to fire.
655  * Callback the provided function with the context pointer.
656  */
657 static void
658 walk_timers(uint32_t * last_run)
659 {
660   unsigned int total_timers_walked = 0, total_timers_fired = 0;
661   unsigned int wheel_slot_walks = 0;
662
663   /*
664    * Check the required wheel slots since the last time a timer walk was invoked,
665    * or check *all* the wheel slots, whatever is less work.
666    * The latter is meant as a safety belt if the scheduler falls behind.
667    */
668   while ((*last_run <= now_times) && (wheel_slot_walks < TIMER_WHEEL_SLOTS)) {
669     struct list_node tmp_head_node;
670     /* keep some statistics */
671     unsigned int timers_walked = 0, timers_fired = 0;
672
673     /* Get the hash slot for this clocktick */
674     struct list_node *const timer_head_node = &timer_wheel[*last_run & TIMER_WHEEL_MASK];
675
676     /* Walk all entries hanging off this hash bucket. We treat this basically as a stack
677      * so that we always know if and where the next element is.
678      */
679     list_head_init(&tmp_head_node);
680     while (!list_is_empty(timer_head_node)) {
681       /* the top element */
682       struct list_node *const timer_node = timer_head_node->next;
683       struct timer_entry *const timer = list2timer(timer_node);
684
685       /*
686        * Dequeue and insert to a temporary list.
687        * We do this to avoid losing our walking context when
688        * multiple timers fire.
689        */
690       list_remove(timer_node);
691       list_add_after(&tmp_head_node, timer_node);
692       timers_walked++;
693
694       if (timer->timer_flags & OLSR_TIMER_REMOVED) {
695         continue;
696       }
697
698       /* Ready to fire ? */
699       if (TIMED_OUT(timer->timer_clock)) {
700
701         OLSR_PRINTF(7, "TIMER: fire %s timer %p, ctx %p, "
702                    "at clocktick %u (%s)\n",
703                    timer->timer_cookie->ci_name,
704                    timer, timer->timer_cb_context, (unsigned int)*last_run, olsr_wallclock_string());
705
706         /* This timer is expired, call into the provided callback function */
707         timer->timer_cb(timer->timer_cb_context);
708
709         /* Only act on actually running timers */
710         if (timer->timer_flags & OLSR_TIMER_RUNNING) {
711           /*
712            * Don't restart the periodic timer if the callback function has
713            * stopped the timer.
714            */
715           if (timer->timer_period) {
716             /* For periodical timers, rehash the random number and restart */
717             timer->timer_random = olsr_random();
718             olsr_change_timer(timer, timer->timer_period, timer->timer_jitter_pct, OLSR_TIMER_PERIODIC);
719           } else {
720             /* Singleshot timers are stopped */
721             olsr_stop_timer(timer);
722           }
723         }
724
725         timers_fired++;
726       }
727     }
728
729     /*
730      * Now merge the temporary list back to the old bucket.
731      */
732     list_merge(timer_head_node, &tmp_head_node);
733
734     /* keep some statistics */
735     total_timers_walked += timers_walked;
736     total_timers_fired += timers_fired;
737
738     /* Increment the time slot and wheel slot walk iteration */
739     (*last_run)++;
740     wheel_slot_walks++;
741   }
742
743   OLSR_PRINTF(7, "TIMER: processed %4u/%d clockwheel slots, "
744              "timers walked %4u/%u, timers fired %u\n",
745              wheel_slot_walks, TIMER_WHEEL_SLOTS, total_timers_walked, timer_mem_cookie->ci_usage, total_timers_fired);
746
747   /*
748    * If the scheduler has slipped and we have walked all wheel slots,
749    * reset the last timer run.
750    */
751   *last_run = now_times;
752 }
753
754 static void walk_timers_cleanup(void) {
755   struct timer_cleanup_entry * timer;
756
757   OLSR_FOR_ALL_TIMERS_CLEANUP(timer) {
758     olsr_cleanup_timer(timer->timer);
759     avl_delete(&timer_cleanup_tree, &timer->avl);
760     free(timer);
761   } OLSR_FOR_ALL_TIMER_CLEANUP_END(slot)
762 }
763
764 /**
765  * Stop and delete all timers.
766  */
767 void
768 olsr_flush_timers(void)
769 {
770   struct list_node *timer_head_node;
771   struct list_node tmp_head_node;
772   unsigned int wheel_slot = 0;
773
774   list_head_init(&tmp_head_node);
775
776   walk_timers_cleanup();
777
778   for (wheel_slot = 0; wheel_slot < TIMER_WHEEL_SLOTS; wheel_slot++) {
779     timer_head_node = &timer_wheel[wheel_slot & TIMER_WHEEL_MASK];
780
781     /* stop all entries hanging off this hash bucket. */
782     while (!list_is_empty(timer_head_node)) {
783       /* the top element */
784       struct list_node *const timer_node = timer_head_node->next;
785       struct timer_entry *const timer = list2timer(timer_node);
786
787       /*
788        * Dequeue and insert to a temporary list.
789        * We do this to avoid losing our walking context when
790        * multiple timers fire.
791        */
792       list_remove(timer_node);
793       list_add_after(&tmp_head_node, timer_node);
794
795       olsr_stop_timer(timer);
796     }
797   }
798
799   /*
800    * Now merge the temporary list back to the old bucket.
801    */
802   list_merge(timer_head_node, &tmp_head_node);
803
804   walk_timers_cleanup();
805 }
806
807 /**
808  * Returns the difference between gmt and local time in seconds.
809  * Use gmtime() and localtime() to keep things simple.
810  *
811  * taken and slightly modified from www.tcpdump.org.
812  */
813 static int
814 olsr_get_timezone(void)
815 {
816 #define OLSR_TIMEZONE_UNINITIALIZED -1
817   static int time_diff = OLSR_TIMEZONE_UNINITIALIZED;
818   if (time_diff == OLSR_TIMEZONE_UNINITIALIZED) {
819     int dir;
820     const time_t t = time(NULL);
821     const struct tm gmt = *gmtime(&t);
822     const struct tm *loc = localtime(&t);
823
824     time_diff = (loc->tm_hour - gmt.tm_hour) * 60 * 60 + (loc->tm_min - gmt.tm_min) * 60;
825
826     /*
827      * If the year or julian day is different, we span 00:00 GMT
828      * and must add or subtract a day. Check the year first to
829      * avoid problems when the julian day wraps.
830      */
831     dir = loc->tm_year - gmt.tm_year;
832     if (!dir) {
833       dir = loc->tm_yday - gmt.tm_yday;
834     }
835
836     time_diff += dir * 24 * 60 * 60;
837   }
838   return time_diff;
839 }
840
841 /**
842  * Format an absolute wallclock system time string.
843  * May be called upto 4 times in a single printf() statement.
844  * Displays microsecond resolution.
845  *
846  * @return buffer to a formatted system time string.
847  */
848 const char *
849 olsr_wallclock_string(void)
850 {
851   static char buf[sizeof("00:00:00.000000")];
852   struct timeval now;
853   int sec, usec;
854
855   gettimeofday(&now, NULL);
856
857   sec = (int)now.tv_sec + olsr_get_timezone();
858   usec = (int)now.tv_usec;
859
860   snprintf(buf, sizeof(buf), "%02d:%02d:%02d.%06d", (sec % 86400) / 3600, (sec % 3600) / 60, sec % 60, usec);
861
862   return buf;
863 }
864
865 /**
866  * Format an relative non-wallclock system time string.
867  * May be called upto 4 times in a single printf() statement.
868  * Displays millisecond resolution.
869  *
870  * @param clk absolute time expressed in clockticks
871  * @return buffer to a formatted system time string.
872  */
873 const char *
874 olsr_clock_string(uint32_t clk)
875 {
876   static char buf[sizeof("00:00:00.000")];
877
878   /* On most systems a clocktick is a 10ms quantity. */
879   unsigned int msec = clk % 1000;
880   unsigned int sec = clk / 1000;
881
882   snprintf(buf, sizeof(buf), "%02u:%02u:%02u.%03u", sec / 3600, (sec % 3600) / 60, (sec % 60), (msec % MSEC_PER_SEC));
883
884   return buf;
885 }
886
887 /**
888  * Start a new timer.
889  *
890  * @param rel_time relative time expressed in milliseconds
891  * @param jitter_pct jitter expressed in percent
892  * @param periodical true for a repeating timer, false for a one-shot timer
893  * @param cb_func timer callback function
894  * @param context context for the callback function
895  * @param ci timer cookie
896  * @return a pointer to the created entry
897  */
898 struct timer_entry *
899 olsr_start_timer(unsigned int rel_time,
900                  uint8_t jitter_pct, bool periodical, timer_cb_func cb_func, void *context, struct olsr_cookie_info *ci)
901 {
902   struct timer_entry *timer;
903
904   if (ci == NULL) {
905     ci = def_timer_ci;
906   }
907   assert(cb_func);
908
909   timer = olsr_cookie_malloc(timer_mem_cookie);
910
911   /*
912    * Compute random numbers only once.
913    */
914   if (!timer->timer_random) {
915     timer->timer_random = olsr_random();
916   }
917
918   /* Fill entry */
919   timer->timer_clock = calc_jitter(rel_time, jitter_pct, timer->timer_random);
920   timer->timer_cb = cb_func;
921   timer->timer_cb_context = context;
922   timer->timer_jitter_pct = jitter_pct;
923   timer->timer_flags = OLSR_TIMER_RUNNING;
924
925   /* The cookie is used for debugging to traceback the originator */
926   timer->timer_cookie = ci;
927   olsr_cookie_usage_incr(ci->ci_id);
928
929   /* Singleshot or periodical timer ? */
930   timer->timer_period = periodical ? rel_time : 0;
931
932   /*
933    * Now insert in the respective timer_wheel slot.
934    */
935   list_add_before(&timer_wheel[timer->timer_clock & TIMER_WHEEL_MASK], &timer->timer_list);
936
937   OLSR_PRINTF(7, "TIMER: start %s timer %p firing in %s, ctx %p\n",
938              ci->ci_name, timer, olsr_clock_string(timer->timer_clock), context);
939
940   return timer;
941 }
942
943 /**
944  * Delete a timer.
945  *
946  * @param timer the timer_entry that shall be removed
947  */
948 void
949 olsr_stop_timer(struct timer_entry *timer)
950 {
951   /* It's okay to get a NULL here */
952   if (!timer //
953       || !(timer->timer_flags & OLSR_TIMER_RUNNING)) {
954     return;
955   }
956
957   assert(timer->timer_cookie);     /* we want timer cookies everywhere */
958
959   OLSR_PRINTF(7, "TIMER: stop %s timer %p, ctx %p\n",
960              timer->timer_cookie->ci_name, timer, timer->timer_cb_context);
961
962
963   timer->timer_flags &= ~OLSR_TIMER_RUNNING;
964   timer->timer_flags |= OLSR_TIMER_REMOVED;
965
966   {
967     struct timer_cleanup_entry * node = olsr_malloc(sizeof(struct timer_cleanup_entry), "timer cleanup entry");
968     node->avl.key = timer;
969     node->timer = timer;
970     if (avl_insert(&timer_cleanup_tree, &node->avl, AVL_DUP_NO) == -1) {
971       /* duplicate */
972       free(node);
973     }
974   }
975 }
976
977 /**
978  * Clean up a timer.
979  *
980  * @param timer the timer_entry that shall be cleaned up
981  */
982 static void
983 olsr_cleanup_timer(struct timer_entry *timer)
984 {
985   /* It's okay to get a NULL here */
986   if (!timer //
987       || !(timer->timer_flags & OLSR_TIMER_REMOVED)) {
988     return;
989   }
990
991   assert(timer->timer_cookie);     /* we want timer cookies everywhere */
992
993   OLSR_PRINTF(7, "TIMER: cleanup %s timer %p, ctx %p\n",
994              timer->timer_cookie->ci_name, timer, timer->timer_cb_context);
995
996
997   /*
998    * Carve out of the existing wheel_slot and free.
999    */
1000   list_remove(&timer->timer_list);
1001   timer->timer_flags &= ~OLSR_TIMER_REMOVED;
1002   olsr_cookie_usage_decr(timer->timer_cookie->ci_id);
1003
1004   olsr_cookie_free(timer_mem_cookie, timer);
1005 }
1006
1007 /**
1008  * Change a timer_entry.
1009  *
1010  * @param timer timer_entry to be changed.
1011  * @param rel_time new relative time expressed in units of milliseconds.
1012  * @param jitter_pct new jitter expressed in percent.
1013  * @param periodical true for a repeating timer, false for a one-shot timer
1014  */
1015 void
1016 olsr_change_timer(struct timer_entry *timer, unsigned int rel_time, uint8_t jitter_pct, bool periodical)
1017 {
1018   /* Sanity check. */
1019   if (!timer) {
1020     return;
1021   }
1022
1023   assert(timer->timer_cookie);     /* we want timer cookies everywhere */
1024
1025   /* Singleshot or periodical timer ? */
1026   timer->timer_period = periodical ? rel_time : 0;
1027
1028   timer->timer_clock = calc_jitter(rel_time, jitter_pct, timer->timer_random);
1029   timer->timer_jitter_pct = jitter_pct;
1030
1031   /*
1032    * Changes are easy: Remove timer from the exisiting timer_wheel slot
1033    * and reinsert into the new slot.
1034    */
1035   list_remove(&timer->timer_list);
1036   list_add_before(&timer_wheel[timer->timer_clock & TIMER_WHEEL_MASK], &timer->timer_list);
1037
1038   OLSR_PRINTF(7, "TIMER: change %s timer %p, firing to %s, ctx %p\n",
1039              timer->timer_cookie->ci_name, timer, olsr_clock_string(timer->timer_clock), timer->timer_cb_context);
1040 }
1041
1042 /*
1043  * This is the one stop shop for all sort of timer manipulation.
1044  * Depending on the paseed in parameters a new timer is started,
1045  * or an existing timer is started or an existing timer is
1046  * terminated.
1047  */
1048 void
1049 olsr_set_timer(struct timer_entry **timer_ptr,
1050                unsigned int rel_time,
1051                uint8_t jitter_pct, bool periodical, timer_cb_func cb_func, void *context, struct olsr_cookie_info *cookie)
1052 {
1053   if (cookie) {
1054     cookie = def_timer_ci;
1055   }
1056
1057   if (rel_time == 0) {
1058     /* No good future time provided, kill it. */
1059     olsr_stop_timer(*timer_ptr);
1060     *timer_ptr = NULL;
1061   }
1062   else if ((*timer_ptr) == NULL) {
1063     /* No timer running, kick it. */
1064     *timer_ptr = olsr_start_timer(rel_time, jitter_pct, periodical, cb_func, context, cookie);
1065   }
1066   else {
1067     olsr_change_timer(*timer_ptr, rel_time, jitter_pct, periodical);
1068   }
1069 }
1070
1071 /*
1072  * Local Variables:
1073  * c-basic-offset: 2
1074  * indent-tabs-mode: nil
1075  * End:
1076  */