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