c14edfba74d2fa33d1d6b75cce878d4ee8c65479
[olsrd.git] / src / scheduler.c
1
2 /*
3  * The olsr.org Optimized Link-State Routing daemon(olsrd)
4  * Copyright (c) 2004, Andreas T√łnnesen(andreto@olsr.org)
5  * Timer rewrite (c) 2008, Hannes Gredler (hannes@gredler.at)
6  * All rights reserved.
7  *
8  * Redistribution and use in source and binary forms, with or without 
9  * modification, are permitted provided that the following conditions 
10  * are met:
11  *
12  * * Redistributions of source code must retain the above copyright 
13  *   notice, this list of conditions and the following disclaimer.
14  * * Redistributions in binary form must reproduce the above copyright 
15  *   notice, this list of conditions and the following disclaimer in 
16  *   the documentation and/or other materials provided with the 
17  *   distribution.
18  * * Neither the name of olsr.org, olsrd nor the names of its 
19  *   contributors may be used to endorse or promote products derived 
20  *   from this software without specific prior written permission.
21  *
22  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 
23  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 
24  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 
25  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 
26  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 
27  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 
28  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 
29  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 
30  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 
31  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 
32  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 
33  * POSSIBILITY OF SUCH DAMAGE.
34  *
35  * Visit http://www.olsr.org for more information.
36  *
37  * If you find this software useful feel free to make a donation
38  * to the project. For more information see the website or contact
39  * the copyright holders.
40  *
41  */
42
43 #include "defs.h"
44 #include "scheduler.h"
45 #include "log.h"
46 #include "tc_set.h"
47 #include "link_set.h"
48 #include "duplicate_set.h"
49 #include "mpr_selector_set.h"
50 #include "mid_set.h"
51 #include "mpr.h"
52 #include "olsr.h"
53 #include "build_msg.h"
54 #include "net_olsr.h"
55 #include "socket_parser.h"
56 #include "olsr_spf.h"
57 #include "link_set.h"
58 #include "olsr_cookie.h"
59
60 #include <stdlib.h>
61
62 #ifdef WIN32
63 #define random(x) rand(x)
64 #endif
65
66 /* Timer data, global. Externed in scheduler.h */
67 clock_t now_times;                     /* current idea of times(2) reported uptime */
68
69 /* Hashed root of all timers */
70 struct list_node timer_wheel[TIMER_WHEEL_SLOTS];
71 clock_t timer_last_run;                /* remember the last timeslot walk */
72
73 /* Pool of timers to avoid malloc() churn */
74 struct list_node free_timer_list;
75
76 /* Statistics */
77 unsigned int timers_running;
78
79
80 /**
81  * Sleep until the next scheduling interval.
82  *
83  * @param scheduler loop runtime in clock ticks.
84  * @return nada
85  */
86 static void
87 olsr_scheduler_sleep(unsigned long scheduler_runtime)
88 {
89   struct timespec remainder_spec, sleeptime_spec;
90   struct timeval sleeptime_val, time_used, next_interval;
91   olsr_u32_t next_interval_usec;
92   unsigned long milliseconds_used;
93
94   /* Calculate next planned scheduler invocation */
95   next_interval_usec = olsr_cnf->pollrate * USEC_PER_SEC;
96   next_interval.tv_sec = next_interval_usec / USEC_PER_SEC;
97   next_interval.tv_usec = next_interval_usec % USEC_PER_SEC;
98
99   /* Determine used runtime */
100   milliseconds_used = scheduler_runtime * olsr_cnf->system_tick_divider;
101   time_used.tv_sec = milliseconds_used / MSEC_PER_SEC;
102   time_used.tv_usec = (milliseconds_used % MSEC_PER_SEC) * USEC_PER_MSEC;
103
104   if (timercmp(&time_used, &next_interval, <)) {
105     timersub(&next_interval, &time_used, &sleeptime_val);
106
107     sleeptime_spec.tv_sec = sleeptime_val.tv_sec;
108     sleeptime_spec.tv_nsec = sleeptime_val.tv_usec * NSEC_PER_USEC;
109
110     while (nanosleep(&sleeptime_spec, &remainder_spec) < 0)
111       sleeptime_spec = remainder_spec;
112   }
113 }
114
115 /**
116  * Main scheduler event loop. Polls at every
117  * sched_poll_interval and calls all functions
118  * that are timed out or that are triggered.
119  * Also calls the olsr_process_changes()
120  * function at every poll.
121  *
122  * @return nada
123  */
124 void
125 olsr_scheduler(void)
126 {
127   struct interface *ifn;
128
129   OLSR_PRINTF(1, "Scheduler started - polling every %0.2f seconds\n",
130               olsr_cnf->pollrate);
131   OLSR_PRINTF(3, "Max jitter is %f\n\n", olsr_cnf->max_jitter);
132
133   /* Main scheduler loop */
134   for (;;) {
135
136     /*
137      * Update the global timestamp. We are using a non-wallclock timer here
138      * to avoid any undesired side effects if the system clock changes.
139      */
140     now_times = olsr_times();
141
142     /* Read incoming data */
143     olsr_poll_sockets();
144
145     /* Process timers (before packet generation) */
146     olsr_walk_timers(&timer_last_run);
147
148     /* Update */
149     olsr_process_changes();
150
151     /* Check for changes in topology */
152     if (link_changes) {
153       OLSR_PRINTF(3, "ANSN UPDATED %d\n\n", get_local_ansn());
154       increase_local_ansn();
155       link_changes = OLSR_FALSE;
156     }
157
158     /* looping trough interfaces and emmitting pending data */
159     for (ifn = ifnet; ifn; ifn = ifn->int_next) {
160       if (net_output_pending(ifn) && TIMED_OUT(ifn->fwdtimer)) {
161         net_output(ifn);
162       }
163     }
164
165     /* We are done, sleep until the next scheduling interval. */
166     olsr_scheduler_sleep(olsr_times() - now_times);
167
168 #if defined WIN32
169     /* The Ctrl-C signal handler thread asks us to exit */
170     if (olsr_win32_end_request) {
171       break;
172     }
173 #endif
174   }
175
176 #if defined WIN32
177   /* Tell the Ctrl-C signal handler thread that we have exited */
178   olsr_win32_end_flag = TRUE;
179
180   /*
181    * The Ctrl-C signal handler thread will exit the process
182    * and hence also kill us.
183    */
184   while (1) {
185     Sleep(1000);                /* milliseconds */
186   }
187 #endif
188 }
189
190
191 /**
192  * Decrement a relative timer by a random number range.
193  *
194  * @param the relative timer expressed in units of milliseconds.
195  * @param the jitter in percent
196  * @param cached result of random() at system init.
197  * @return the absolute timer in system clock tick units
198  */
199 static clock_t
200 olsr_jitter(unsigned int rel_time, olsr_u8_t jitter_pct, unsigned int random)
201 {
202   unsigned int jitter_time;
203
204   /*
205    * No jitter or, jitter larger than 99% does not make sense.
206    * Also protect against overflows resulting from > 25 bit timers.
207    */
208   if (jitter_pct == 0 || jitter_pct > 99 || rel_time > (1 << 24)) {
209     return GET_TIMESTAMP(rel_time);
210   }
211
212   /*
213    * Play some tricks to avoid overflows with integer arithmetic.
214    */
215   jitter_time = (jitter_pct * rel_time) / 100;
216   jitter_time = random / (1 + RAND_MAX / jitter_time);
217
218 #if 0
219   OLSR_PRINTF(3, "TIMER: jitter %u%% rel_time %ums to %ums\n",
220               jitter_pct, rel_time, rel_time - jitter_time);
221 #endif
222
223   return GET_TIMESTAMP(rel_time - jitter_time);
224 }
225
226
227 /**
228  * Allocate a timer_entry.
229  * Do this first by checking if something is available in the free_timer_pool
230  * If not then allocate a big chunk of memory and thread its elements up
231  * to the free_timer_list.
232  */
233 static struct timer_entry *
234 olsr_get_timer(void)
235 {
236   void *timer_block;
237   struct timer_entry *timer;
238   struct list_node *timer_list_node;
239   unsigned int timer_index;
240
241   /*
242    * If there is at least one timer in the pool then remove the first
243    * element from the pool and recycle it.
244    */
245   if (!list_is_empty(&free_timer_list)) {
246     timer_list_node = free_timer_list.next;
247
248     /* carve it out of the pool, do not memset overwrite timer->timer_random */
249     list_remove(timer_list_node);
250     timer = list2timer(timer_list_node);
251
252     return timer;
253   }
254
255   /*
256    * Nothing in the pool, allocate a new chunk.
257    */
258   timer_block =
259     olsr_malloc(sizeof(struct timer_entry) * OLSR_TIMER_MEMORY_CHUNK,
260                 "timer chunk");
261
262 #if 0
263   OLSR_PRINTF(3, "TIMER: alloc %u bytes chunk at %p\n",
264               sizeof(struct timer_entry) * OLSR_TIMER_MEMORY_CHUNK,
265               timer_block);
266 #endif
267
268   /*
269    * Slice the chunk up and put the future timer_entries in the free timer pool.
270    */
271   timer = timer_block;
272   for (timer_index = 0; timer_index < OLSR_TIMER_MEMORY_CHUNK; timer_index++) {
273
274     /* Insert new timers at the tail of the free_timer list */
275     list_add_before(&free_timer_list, &timer->timer_list);
276
277     /* 
278      * For performance reasons (read: frequent timer changes),
279      * precompute a random number once per timer and reuse later.
280      * The random number only gets recomputed if a periodical timer fires,
281      * such that a different jitter is applied for future firing.
282      */
283     timer->timer_random = random();
284
285     timer++;
286   }
287
288   /*
289    * There are now timers in the pool, recurse once.
290    */
291   return olsr_get_timer();
292 }
293
294
295 /**
296  * Init datastructures for maintaining timers.
297  */
298 void
299 olsr_init_timers(void)
300 {
301   struct list_node *timer_head_node;
302   int index;
303
304   OLSR_PRINTF(5, "TIMER: init timers\n");
305
306   memset(timer_wheel, 0, sizeof(timer_wheel));
307
308   timer_head_node = timer_wheel;
309   for (index = 0; index < TIMER_WHEEL_SLOTS; index++) {
310     list_head_init(timer_head_node);
311     timer_head_node++;
312   }
313
314   /*
315    * Reset the last timer run.
316    */
317   timer_last_run = now_times;
318
319   /* Timer memory pooling */
320   list_head_init(&free_timer_list);
321   timers_running = 0;
322 }
323
324 /*
325  * olsr_get_next_list_entry
326  *
327  * Get the next list node in a hash bucket.
328  * The listnode of the timer in may be subject to getting removed from
329  * this timer bucket in olsr_change_timer() and olsr_stop_timer(), which
330  * means that we can miss our walking context.
331  * By caching the previous node we can figure out if the current node
332  * has been removed from the hash bucket and compute the next node.
333  */
334 static struct list_node *
335 olsr_get_next_list_entry (struct list_node **prev_node,
336                           struct list_node *current_node)
337 {
338   if ((*prev_node)->next == current_node) {
339
340     /*
341      * No change in the list, normal traversal, update the previous node.
342      */
343     *prev_node = current_node;
344     return (current_node->next);
345   } else {
346
347     /*
348      * List change. Recompute the walking context.
349      */
350     return ((*prev_node)->next);
351   }
352 }
353
354 /**
355  * Walk through the timer list and check if any timer is ready to fire.
356  * Callback the provided function with the context pointer.
357  */
358 void
359 olsr_walk_timers(clock_t * last_run)
360 {
361   static struct timer_entry *timer;
362   struct list_node *timer_head_node, *timer_walk_node, *timer_walk_prev_node;
363   unsigned int timers_walked, timers_fired;
364   unsigned int total_timers_walked, total_timers_fired;
365   unsigned int wheel_slot_walks = 0;
366
367   /*
368    * Check the required wheel slots since the last time a timer walk was invoked,
369    * or check *all* the wheel slots, whatever is less work.
370    * The latter is meant as a safety belt if the scheduler falls behind.
371    */
372   total_timers_walked = total_timers_fired = timers_walked = timers_fired = 0;
373   while ((*last_run <= now_times) && (wheel_slot_walks < TIMER_WHEEL_SLOTS)) {
374
375     /* keep some statistics */
376     total_timers_walked += timers_walked;
377     total_timers_fired += timers_fired;
378     timers_walked = 0;
379     timers_fired = 0;
380
381     /* Get the hash slot for this clocktick */
382     timer_head_node = &timer_wheel[*last_run & TIMER_WHEEL_MASK];
383     timer_walk_prev_node = timer_head_node;
384
385     /* Walk all entries hanging off this hash bucket */
386     for (timer_walk_node = timer_head_node->next;
387          timer_walk_node != timer_head_node; /* circular list */
388          timer_walk_node = olsr_get_next_list_entry(&timer_walk_prev_node,
389                                                     timer_walk_node)) {
390
391       timer = list2timer(timer_walk_node);
392
393       timers_walked++;
394
395       /* Ready to fire ? */
396       if (TIMED_OUT(timer->timer_clock)) {
397
398         OLSR_PRINTF(3, "TIMER: fire %s timer %p, ctx %p, "
399                     "at clocktick %u (%s)\n",
400                     olsr_cookie_name(timer->timer_cookie),
401                     timer, timer->timer_cb_context,
402                     (unsigned int)*last_run,
403                     olsr_wallclock_string());
404
405         /* This timer is expired, call into the provided callback function */
406         timer->timer_cb(timer->timer_cb_context);
407
408         if (timer->timer_period) {
409
410           /*
411            * Don't restart the periodic timer if the callback function has
412            * stopped the timer.
413            */
414           if (timer->timer_flags & OLSR_TIMER_RUNNING) {
415
416             /* For periodical timers, rehash the random number and restart */
417             timer->timer_random = random();
418             olsr_change_timer(timer, timer->timer_period,
419                               timer->timer_jitter_pct, OLSR_TIMER_PERIODIC);
420           }
421
422         } else {
423
424           /*
425            * Don't stop the singleshot timer if the callback function has
426            * stopped the timer.
427            */
428           if (timer->timer_flags & OLSR_TIMER_RUNNING) {
429
430             /* Singleshot timers are stopped and returned to the pool */
431             olsr_stop_timer(timer);
432           }
433         }
434
435         timers_fired++;
436       }
437     }
438
439     /* Increment the time slot and wheel slot walk iteration */
440     (*last_run)++;
441     wheel_slot_walks++;
442   }
443
444 #ifdef DEBUG
445   OLSR_PRINTF(3, "TIMER: processed %4u/%u clockwheel slots, "
446               "timers walked %4u/%u, timers fired %u\n",
447               wheel_slot_walks, TIMER_WHEEL_SLOTS,
448               total_timers_walked, timers_running, total_timers_fired);
449 #endif
450
451   /*
452    * If the scheduler has slipped and we have walked all wheel slots,
453    * reset the last timer run.
454    */
455   *last_run = now_times;
456 }
457
458 /**
459  * Returns the difference between gmt and local time in seconds.
460  * Use gmtime() and localtime() to keep things simple.
461  * 
462  * taken and slightly modified from www.tcpdump.org.
463  */
464 static int
465 olsr_get_timezone(void)
466 {
467 #define OLSR_TIMEZONE_UNINITIALIZED -1
468
469   static int time_diff = OLSR_TIMEZONE_UNINITIALIZED;
470   int dir;
471   struct tm *gmt, *loc;
472   struct tm sgmt;
473   time_t t;
474
475   if (time_diff != OLSR_TIMEZONE_UNINITIALIZED) {
476     return time_diff;
477   }
478
479   t = time(NULL);
480   gmt = &sgmt;
481   *gmt = *gmtime(&t);
482   loc = localtime(&t);
483
484   time_diff = (loc->tm_hour - gmt->tm_hour) * 60 * 60
485     + (loc->tm_min - gmt->tm_min) * 60;
486
487   /*
488    * If the year or julian day is different, we span 00:00 GMT
489    * and must add or subtract a day. Check the year first to
490    * avoid problems when the julian day wraps.
491    */
492   dir = loc->tm_year - gmt->tm_year;
493   if (!dir) {
494     dir = loc->tm_yday - gmt->tm_yday;
495   }
496
497   time_diff += dir * 24 * 60 * 60;
498
499   return (time_diff);
500 }
501
502 /**
503  * Format an absolute wallclock system time string.
504  * May be called upto 4 times in a single printf() statement.
505  * Displays microsecond resolution.
506  *
507  * @return buffer to a formatted system time string.
508  */
509 const char *
510 olsr_wallclock_string(void)
511 {
512   static char buf[4][sizeof("00:00:00.000000")];
513   static int idx = 0;
514   char *ret;
515   struct timeval now;
516   int sec, usec;
517
518   ret = buf[idx];
519   idx = (idx + 1) & 3;
520
521   gettimeofday(&now, NULL);
522
523   sec = (int)now.tv_sec + olsr_get_timezone();
524   usec = (int)now.tv_usec;
525
526   snprintf(ret, sizeof(buf)/4, "%02u:%02u:%02u.%06u",
527            (sec % 86400) / 3600, (sec % 3600) / 60, sec % 60, usec);
528
529   return ret;
530 }
531
532
533 /**
534  * Format an relative non-wallclock system time string.
535  * May be called upto 4 times in a single printf() statement.
536  * Displays millisecond resolution.
537  *
538  * @param absolute time expressed in clockticks
539  * @return buffer to a formatted system time string.
540  */
541 const char *
542 olsr_clock_string(clock_t clock)
543 {
544   static char buf[4][sizeof("00:00:00.000")];
545   static int idx = 0;
546   char *ret;
547   unsigned int sec, msec;
548
549   ret = buf[idx];
550   idx = (idx + 1) & 3;
551
552   /* On most systems a clocktick is a 10ms quantity. */
553   msec = olsr_cnf->system_tick_divider * (unsigned int)(clock - now_times);
554   sec = msec / MSEC_PER_SEC;
555
556   snprintf(ret, sizeof(buf) / 4, "%02u:%02u:%02u.%03u",
557            sec / 3600, (sec % 3600) / 60, (sec % 60), (msec % MSEC_PER_SEC));
558
559   return ret;
560 }
561
562
563 /**
564  * Start a new timer.
565  *
566  * @param relative time expressed in milliseconds
567  * @param jitter expressed in percent
568  * @param timer callback function
569  * @param context for the callback function
570  * @return a pointer to the created entry
571  */
572 struct timer_entry *
573 olsr_start_timer(unsigned int rel_time, olsr_u8_t jitter_pct,
574                  olsr_bool periodical, void (*timer_cb_function) (void *),
575                  void *context, olsr_cookie_t cookie)
576 {
577   struct timer_entry *timer;
578
579   timer = olsr_get_timer();
580
581   /* Fill entry */
582   timer->timer_clock = olsr_jitter(rel_time, jitter_pct, timer->timer_random);
583   timer->timer_cb = timer_cb_function;
584   timer->timer_cb_context = context;
585   timer->timer_jitter_pct = jitter_pct;
586   timer->timer_flags = OLSR_TIMER_RUNNING;
587
588   /* The cookie is used for debugging to traceback the originator */
589   timer->timer_cookie = cookie;
590   olsr_cookie_usage_incr(cookie);
591
592   /* Singleshot or periodical timer ? */
593   if (periodical) {
594     timer->timer_period = rel_time;
595   } else {
596     timer->timer_period = 0;
597   }
598
599   /*
600    * Now insert in the respective timer_wheel slot.
601    */
602   list_add_before(&timer_wheel[timer->timer_clock & TIMER_WHEEL_MASK],
603                   &timer->timer_list);
604   timers_running++;
605
606 #ifdef DEBUG
607   OLSR_PRINTF(3, "TIMER: start %s timer %p firing in %s, ctx %p\n",
608               olsr_cookie_name(timer->timer_cookie),
609               timer, olsr_clock_string(timer->timer_clock), context);
610 #endif
611
612   return timer;
613 }
614
615 /**
616  * Delete a timer.
617  *
618  * @param the timer_entry that shall be removed
619  * @return nada
620  */
621 void
622 olsr_stop_timer(struct timer_entry *timer)
623 {
624
625   /* sanity check */
626   if (!timer) {
627     return;
628   }
629 #ifdef DEBUG
630   OLSR_PRINTF(3, "TIMER: stop %s timer %p, ctx %p\n",
631               olsr_cookie_name(timer->timer_cookie),
632               timer, timer->timer_cb_context);
633 #endif
634
635   /*
636    * Carve out of the existing wheel_slot and return to the pool
637    * rather than freeing for later reycling.
638    */
639   list_remove(&timer->timer_list);
640   list_add_before(&free_timer_list, &timer->timer_list);
641   timer->timer_flags &= ~OLSR_TIMER_RUNNING;
642   olsr_cookie_usage_decr(timer->timer_cookie);
643   timers_running--;
644 }
645
646
647 /**
648  * Change a timer_entry.
649  *
650  * @param timer_entry to be changed.
651  * @param new relative time expressed in units of milliseconds.
652  * @param new jitter expressed in percent.
653  * @return nada
654  */
655 void
656 olsr_change_timer(struct timer_entry *timer, unsigned int rel_time,
657                   olsr_u8_t jitter_pct, olsr_bool periodical)
658 {
659
660   /* Sanity check. */
661   if (!timer) {
662     return;
663   }
664
665   /* Singleshot or periodical timer ? */
666   if (periodical) {
667     timer->timer_period = rel_time;
668   } else {
669     timer->timer_period = 0;
670   }
671
672   timer->timer_clock = olsr_jitter(rel_time, jitter_pct, timer->timer_random);
673   timer->timer_jitter_pct = jitter_pct;
674
675   /*
676    * Changes are easy: Remove timer from the exisiting timer_wheel slot
677    * and reinsert into the new slot.
678    */
679   list_remove(&timer->timer_list);
680   list_add_before(&timer_wheel[timer->timer_clock & TIMER_WHEEL_MASK],
681                   &timer->timer_list);
682
683 #ifdef DEBUG
684   OLSR_PRINTF(3, "TIMER: change %s timer %p, firing to %s, ctx %p\n",
685               olsr_cookie_name(timer->timer_cookie), timer,
686               olsr_clock_string(timer->timer_clock), timer->timer_cb_context);
687 #endif
688 }
689
690
691 /*
692  * This is the one stop shop for all sort of timer manipulation.
693  * Depending on the paseed in parameters a new timer is started,
694  * or an existing timer is started or an existing timer is
695  * terminated.
696  */
697 void
698 olsr_set_timer(struct timer_entry **timer_ptr, unsigned int rel_time,
699                olsr_u8_t jitter_pct, olsr_bool periodical,
700                void (*timer_cb_function) (void *), void *context,
701                olsr_cookie_t cookie)
702 {
703
704   if (!*timer_ptr) {
705
706     /* No timer running, kick it. */
707     *timer_ptr = olsr_start_timer(rel_time, jitter_pct, periodical,
708                                   timer_cb_function, context, cookie);
709   } else {
710
711     if (!rel_time) {
712
713       /* No good future time provided, kill it. */
714       olsr_stop_timer(*timer_ptr);
715       *timer_ptr = NULL;
716     } else {
717
718       /* Time is ok and timer is running, change it ! */
719       olsr_change_timer(*timer_ptr, rel_time, jitter_pct, periodical);
720     }
721   }
722 }
723
724 /*
725  * Local Variables:
726  * c-basic-offset: 2
727  * End:
728  */