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