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