From Andreas Jacobs <andjac@kawo1.rwth-aachen.de>: bugfix for scheduler
[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  * All rights reserved.
5  *
6  * Redistribution and use in source and binary forms, with or without 
7  * modification, are permitted provided that the following conditions 
8  * are met:
9  *
10  * * Redistributions of source code must retain the above copyright 
11  *   notice, this list of conditions and the following disclaimer.
12  * * Redistributions in binary form must reproduce the above copyright 
13  *   notice, this list of conditions and the following disclaimer in 
14  *   the documentation and/or other materials provided with the 
15  *   distribution.
16  * * Neither the name of olsr.org, olsrd nor the names of its 
17  *   contributors may be used to endorse or promote products derived 
18  *   from this software without specific prior written permission.
19  *
20  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 
21  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 
22  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 
23  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 
24  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 
25  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 
26  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 
27  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 
28  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 
29  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 
30  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 
31  * POSSIBILITY OF SUCH DAMAGE.
32  *
33  * Visit http://www.olsr.org for more information.
34  *
35  * If you find this software useful feel free to make a donation
36  * to the project. For more information see the website or contact
37  * the copyright holders.
38  *
39  */
40
41
42 #include "defs.h"
43 #include "scheduler.h"
44 #include "log.h"
45 #include "tc_set.h"
46 #include "link_set.h"
47 #include "duplicate_set.h"
48 #include "mpr_selector_set.h"
49 #include "mid_set.h"
50 #include "mpr.h"
51 #include "olsr.h"
52 #include "build_msg.h"
53 #include "net_olsr.h"
54
55 /* Timer data, global. Externed in defs.h */
56 clock_t now_times;              /* current idea of times(2) reported uptime */
57 struct timeval now;             /* current idea of time */
58 struct tm *nowtm;               /* current idea of time (in tm) */
59
60 /* Lists */
61 static struct timeout_entry *timeout_functions;
62 static struct event_entry *event_functions;
63
64 static olsr_bool link_changes; /* is set if changes occur in MPRS set */ 
65
66 void
67 signal_link_changes(olsr_bool val)
68 {
69   link_changes = val;
70 }
71
72 static void 
73 trigger_dijkstra(void *foo __attribute__((unused)))
74 {
75   OLSR_PRINTF(3, "Triggering Dijkstra\n");
76
77   changes_neighborhood = OLSR_TRUE;
78   changes_topology = OLSR_TRUE;
79   changes_force = OLSR_TRUE;
80 }
81
82 /**
83  *Main scheduler event loop. Polls at every
84  *sched_poll_interval and calls all functions
85  *that are timed out or that are triggered.
86  *Also calls the olsr_process_changes()
87  *function at every poll.
88  *
89  *
90  *@return nada
91  */
92
93 void
94 scheduler(void)
95 {
96   struct timeval interval;
97   olsr_u32_t interval_usec;
98
99   link_changes = OLSR_FALSE;
100
101   if(olsr_cnf->lq_level > 1 && olsr_cnf->lq_dinter > 0.0)
102     olsr_register_scheduler_event(trigger_dijkstra, NULL, olsr_cnf->lq_dinter, 0, NULL);
103
104   interval_usec = olsr_cnf->pollrate * 1000000;
105
106   interval.tv_sec = interval_usec / 1000000;
107   interval.tv_usec = interval_usec % 1000000;
108
109   OLSR_PRINTF(1, "Scheduler started - polling every %0.2f seconds\n", olsr_cnf->pollrate);
110   OLSR_PRINTF(3, "Max jitter is %f\n\n", olsr_cnf->max_jitter);
111
112   /* Main scheduler event loop */
113   for(;;)
114     {
115       /*
116        * Used to calculate sleep time
117        */
118       clock_t end_of_loop;
119       clock_t milliseconds_used;
120       struct timeval time_used;
121       struct event_entry *entry;
122       struct timeout_entry *time_out_entry;
123       struct interface *ifn;
124
125       /* Global buffer for times(2) calls. Do not remove - at least OpenBSD needs it. */
126       struct tms tms_buf;
127  
128       /* Update now_times */
129       now_times = times(&tms_buf);
130
131       /* Update the global timestamp - kept for plugin compat */
132       gettimeofday(&now, NULL);
133       do {
134           nowtm = localtime(&now.tv_sec);
135       } while (nowtm == NULL);
136
137       /* Run timeout functions (before packet generation) */      
138       for (time_out_entry = timeout_functions; time_out_entry != NULL; time_out_entry = time_out_entry->next) {
139           time_out_entry->function();
140       }
141
142       /* Update */      
143       olsr_process_changes();
144
145       /* Check for changes in topology */
146       if(link_changes)
147         {
148           OLSR_PRINTF(3, "ANSN UPDATED %d\n\n", get_local_ansn());
149           increase_local_ansn();
150           link_changes = OLSR_FALSE;
151         }
152
153
154       /* Check scheduled events */
155       
156       /* UPDATED - resets timer upon triggered execution */
157       for (entry = event_functions; entry != NULL; entry = entry->next)
158         {
159           entry->since_last += olsr_cnf->pollrate;
160
161           /* Timed out */
162           if ((entry->since_last > entry->interval) ||
163               /* Triggered */
164               ((entry->trigger != NULL) && (*entry->trigger == 1))
165               ) {
166               /* Run scheduled function */
167               entry->function(entry->param);
168
169               /* Set jitter */
170               entry->since_last = (float)(random() / RAND_MAX) * olsr_cnf->max_jitter;
171               
172               /* Reset trigger */
173               if(entry->trigger != NULL) {
174                 *entry->trigger = 0;
175               }
176
177               //OLSR_PRINTF(3, "Since_last jitter: %0.2f\n", entry->since_last);
178             }
179         }
180
181       /* looping trough interfaces and emmittin pending data */
182       for (ifn = ifnet; ifn ; ifn = ifn->int_next) 
183         { 
184           if(net_output_pending(ifn) && TIMED_OUT(ifn->fwdtimer)) 
185             net_output(ifn);
186         }
187
188
189       end_of_loop = times(&tms_buf);
190
191       //printf("Tick diff: %d\n", end_of_loop - now_times);
192       milliseconds_used = (end_of_loop - now_times) * olsr_cnf->system_tick_divider;
193       time_used.tv_sec = milliseconds_used / 1000;
194       time_used.tv_usec = (milliseconds_used % 1000) * 1000;
195
196       //printf("Time used: %d.%04d\n", time_used.tv_sec, time_used.tv_usec);
197
198       if(timercmp(&time_used, &interval, <))
199         {
200           struct timespec remainder_spec;
201           struct timespec sleeptime_spec;
202           struct timeval sleeptime_val;
203           timersub(&interval, &time_used, &sleeptime_val);
204           
205           // printf("sleeptime_val = %u.%06u\n",
206           //        sleeptime_val.tv_sec, sleeptime_val.tv_usec);
207           
208           sleeptime_spec.tv_sec = sleeptime_val.tv_sec;
209           sleeptime_spec.tv_nsec = sleeptime_val.tv_usec * 1000;
210           
211           while(nanosleep(&sleeptime_spec, &remainder_spec) < 0)
212             sleeptime_spec = remainder_spec;
213         }
214
215 #if defined WIN32
216       // the Ctrl-C signal handler thread asks us to exit
217
218       if (olsr_win32_end_request)
219         break;
220 #endif
221       
222     }//end for
223
224 #if defined WIN32
225   // tell the Ctrl-C signal handler thread that we have exited
226
227   olsr_win32_end_flag = TRUE;
228
229   // the Ctrl-C signal handler thread will exit the process and
230   // hence also kill us
231   
232   while (1)
233     Sleep(1000);
234 #endif
235 }
236
237
238 /*
239  *
240  *@param initial how long utnil the first generation
241  *@param trigger pointer to a boolean indicating that
242  *this function should be triggered immediatley
243  */
244 int
245 olsr_register_scheduler_event(void (*event_function)(void *), 
246                               void *par,
247                               float interval, 
248                               float initial, 
249                               olsr_u8_t *trigger)
250 {
251   struct event_entry *new_entry;
252
253   OLSR_PRINTF(3, "Scheduler event registered int: %0.2f\n", interval);
254
255   /* check that this entry is not added already */
256   new_entry = event_functions;
257   while(new_entry)
258     {
259       if((new_entry->function == event_function) &&
260          (new_entry->param == par) &&
261          (new_entry->trigger == trigger) &&
262          (new_entry->interval == interval))
263         {
264           fprintf(stderr, "Register scheduler event: Event alread registered!\n");
265           olsr_syslog(OLSR_LOG_ERR, "Register scheduler event: Event alread registered!\n");
266           return 0;
267         }
268       new_entry = new_entry->next;
269     }
270
271   new_entry = olsr_malloc(sizeof(struct event_entry), "add scheduler event");
272
273   new_entry->function = event_function;
274   new_entry->param = par;
275   new_entry->interval = interval;
276   new_entry->since_last = interval - initial;
277   new_entry->next = event_functions;
278   new_entry->trigger = trigger;
279
280   event_functions = new_entry;
281
282   return 1;
283 }
284
285
286
287 /*
288  *
289  *@param initial how long until the first generation
290  *@param trigger pointer to a boolean indicating that
291  *this function should be triggered immediatley
292  */
293 int
294 olsr_remove_scheduler_event(void (*event_function)(void *), 
295                             void *par,
296                             float interval, 
297                             float initial __attribute__((unused)), 
298                             olsr_u8_t *trigger)
299 {
300   struct event_entry *entry, *prev;
301
302   prev = NULL;
303   entry = event_functions;
304
305   while(entry)
306     {
307       if((entry->function == event_function) &&
308          (entry->param == par) &&
309          (entry->trigger == trigger) &&
310          (0.0 > interval || entry->interval == interval))
311         {
312           if(entry == event_functions)
313             {
314               event_functions = entry->next;
315             }
316           else
317             {
318               prev->next = entry->next;
319             }
320           free(entry);
321           return 1;
322         }
323
324       prev = entry;
325       entry = entry->next;
326     }
327
328   return 0;
329 }
330
331 /*
332  * Sven-Ola, 2007: Since the original timing and flagging is changed (which
333  * saves lots of CPU time - see LinkQualityDijkstraLimit) the original timeout
334  * functions called every olsr_cnf->polltime uses too much CPU now. Because the
335  * changes_xxx handling is switched off with LQDL, it should be OK to call
336  * all timeout handlers at a much lower rate. To overcome UDP packet loss,
337  * a very low pollrate is used.
338  */
339
340 static float dijkstra_initial = 0.0;
341
342 int
343 olsr_register_scheduler_event_dijkstra(void (*event_function)(void *), 
344                               void *par,
345                               float interval, 
346                               float initial, 
347                               olsr_u8_t *trigger)
348 {
349   if (1 < olsr_cnf->lq_level && 0.0 < olsr_cnf->lq_dinter)
350   {
351     dijkstra_initial += olsr_cnf->lq_dinter / 10.0;
352     return olsr_register_scheduler_event(event_function, par, olsr_cnf->lq_dinter, dijkstra_initial, trigger);
353   }
354   return olsr_register_scheduler_event(event_function, par, interval, initial, trigger);
355 }
356
357 int
358 olsr_register_timeout_function(void (*time_out_function)(void), olsr_bool dijkstra_limit_ok)
359 {
360   struct timeout_entry *new_entry;
361
362   if (dijkstra_limit_ok && 1 < olsr_cnf->lq_level && 0.0 < olsr_cnf->lq_dinter)
363   {
364     dijkstra_initial += olsr_cnf->lq_dinter / 10.0;
365     return olsr_register_scheduler_event(
366       (void *)time_out_function,
367       NULL,
368       olsr_cnf->lq_dinter,
369       dijkstra_initial,
370       NULL);
371   }
372   
373   /* check that this entry is not added already */
374   new_entry = timeout_functions;
375   while(new_entry)
376     {
377       if(new_entry->function == time_out_function)
378         {
379           fprintf(stderr, "Register scheduler timeout: Event alread registered!\n");
380           olsr_syslog(OLSR_LOG_ERR, "Register scheduler timeout: Event alread registered!\n");
381           return 0;
382         }
383       new_entry = new_entry->next;
384     }
385
386   new_entry = olsr_malloc(sizeof(struct timeout_entry), "scheduler add timeout");
387
388   new_entry->function = time_out_function;
389   new_entry->next = timeout_functions;
390
391   timeout_functions = new_entry;
392
393   return 1;
394 }
395
396
397
398 int
399 olsr_remove_timeout_function(void (*time_out_function)(void), olsr_bool dijkstra_limit_ok)
400 {
401   struct timeout_entry *entry, *prev;
402
403   if (dijkstra_limit_ok && 1 < olsr_cnf->lq_level && 0.0 < olsr_cnf->lq_dinter)
404   {
405     return olsr_remove_scheduler_event(
406       (void *)time_out_function,
407       NULL,
408       -1.0,
409       -1.0,
410       NULL);
411   }
412   
413   /* check that this entry is not added already */
414   entry = timeout_functions;
415   prev = NULL;
416
417   while(entry)
418     {
419       if(entry->function == time_out_function)
420         {
421           if(entry == timeout_functions)
422             {
423               timeout_functions = entry->next;
424             }
425           else
426             {
427               prev->next = entry->next;
428             }
429           free(entry);
430           return 1;
431         }
432       prev = entry;
433       entry = entry->next;
434     }
435
436   return 0;
437 }
438