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