e5bdcfd951109732292f9bfc0962ae469103f4da
[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       struct timeval time_used;
120       struct event_entry *entry;
121       struct timeout_entry *time_out_entry;
122       struct interface *ifn;
123
124       /* Global buffer for times(2) calls. Do not remove - at least OpenBSD needs it. */
125       struct tms tms_buf;
126  
127       /* Update now_times */
128       now_times = times(&tms_buf);
129
130       /* Update the global timestamp - kept for plugin compat */
131       gettimeofday(&now, NULL);
132       do {
133           nowtm = localtime(&now.tv_sec);
134       } while (nowtm == NULL);
135
136       /* Run timeout functions (before packet generation) */      
137       for (time_out_entry = timeout_functions; time_out_entry != NULL; time_out_entry = time_out_entry->next) {
138           time_out_entry->function();
139       }
140
141       /* Update */      
142       olsr_process_changes();
143
144       /* Check for changes in topology */
145       if(link_changes)
146         {
147           OLSR_PRINTF(3, "ANSN UPDATED %d\n\n", get_local_ansn());
148           increase_local_ansn();
149           link_changes = OLSR_FALSE;
150         }
151
152
153       /* Check scheduled events */
154       
155       /* UPDATED - resets timer upon triggered execution */
156       for (entry = event_functions; entry != NULL; entry = entry->next)
157         {
158           entry->since_last += olsr_cnf->pollrate;
159
160           /* Timed out */
161           if ((entry->since_last > entry->interval) ||
162               /* Triggered */
163               ((entry->trigger != NULL) && (*entry->trigger == 1))
164               ) {
165               /* Run scheduled function */
166               entry->function(entry->param);
167
168               /* Set jitter */
169               entry->since_last = (float)(random() / RAND_MAX) * olsr_cnf->max_jitter;
170               
171               /* Reset trigger */
172               if(entry->trigger != NULL) {
173                 *entry->trigger = 0;
174               }
175
176               //OLSR_PRINTF(3, "Since_last jitter: %0.2f\n", entry->since_last);
177             }
178         }
179
180       /* looping trough interfaces and emmittin pending data */
181       for (ifn = ifnet; ifn ; ifn = ifn->int_next) 
182         { 
183           if(net_output_pending(ifn) && TIMED_OUT(ifn->fwdtimer)) 
184             net_output(ifn);
185         }
186
187
188       end_of_loop = times(&tms_buf);
189
190       //printf("Tick diff: %d\n", end_of_loop - now_times);
191       time_used.tv_sec = ((end_of_loop - now_times) * olsr_cnf->system_tick_divider) / 1000;
192       time_used.tv_usec = ((end_of_loop - now_times) * olsr_cnf->system_tick_divider) % 1000;
193
194       //printf("Time used: %d.%04d\n", time_used.tv_sec, time_used.tv_usec);
195
196       if(timercmp(&time_used, &interval, <))
197         {
198           struct timespec remainder_spec;
199           struct timespec sleeptime_spec;
200           struct timeval sleeptime_val;
201           timersub(&interval, &time_used, &sleeptime_val);
202           
203           // printf("sleeptime_val = %u.%06u\n",
204           //        sleeptime_val.tv_sec, sleeptime_val.tv_usec);
205           
206           sleeptime_spec.tv_sec = sleeptime_val.tv_sec;
207           sleeptime_spec.tv_nsec = sleeptime_val.tv_usec * 1000;
208           
209           while(nanosleep(&sleeptime_spec, &remainder_spec) < 0)
210             sleeptime_spec = remainder_spec;
211         }
212
213 #if defined WIN32
214       // the Ctrl-C signal handler thread asks us to exit
215
216       if (olsr_win32_end_request)
217         break;
218 #endif
219       
220     }//end for
221
222 #if defined WIN32
223   // tell the Ctrl-C signal handler thread that we have exited
224
225   olsr_win32_end_flag = TRUE;
226
227   // the Ctrl-C signal handler thread will exit the process and
228   // hence also kill us
229   
230   while (1)
231     Sleep(1000);
232 #endif
233 }
234
235
236 /*
237  *
238  *@param initial how long utnil the first generation
239  *@param trigger pointer to a boolean indicating that
240  *this function should be triggered immediatley
241  */
242 int
243 olsr_register_scheduler_event(void (*event_function)(void *), 
244                               void *par,
245                               float interval, 
246                               float initial, 
247                               olsr_u8_t *trigger)
248 {
249   struct event_entry *new_entry;
250
251   OLSR_PRINTF(3, "Scheduler event registered int: %0.2f\n", interval);
252
253   /* check that this entry is not added already */
254   new_entry = event_functions;
255   while(new_entry)
256     {
257       if((new_entry->function == event_function) &&
258          (new_entry->param == par) &&
259          (new_entry->trigger == trigger) &&
260          (new_entry->interval == interval))
261         {
262           fprintf(stderr, "Register scheduler event: Event alread registered!\n");
263           olsr_syslog(OLSR_LOG_ERR, "Register scheduler event: Event alread registered!\n");
264           return 0;
265         }
266       new_entry = new_entry->next;
267     }
268
269   new_entry = olsr_malloc(sizeof(struct event_entry), "add scheduler event");
270
271   new_entry->function = event_function;
272   new_entry->param = par;
273   new_entry->interval = interval;
274   new_entry->since_last = interval - initial;
275   new_entry->next = event_functions;
276   new_entry->trigger = trigger;
277
278   event_functions = new_entry;
279
280   return 1;
281 }
282
283
284
285 /*
286  *
287  *@param initial how long until the first generation
288  *@param trigger pointer to a boolean indicating that
289  *this function should be triggered immediatley
290  */
291 int
292 olsr_remove_scheduler_event(void (*event_function)(void *), 
293                             void *par,
294                             float interval, 
295                             float initial __attribute__((unused)), 
296                             olsr_u8_t *trigger)
297 {
298   struct event_entry *entry, *prev;
299
300   prev = NULL;
301   entry = event_functions;
302
303   while(entry)
304     {
305       if((entry->function == event_function) &&
306          (entry->param == par) &&
307          (entry->trigger == trigger) &&
308          (0.0 > interval || entry->interval == interval))
309         {
310           if(entry == event_functions)
311             {
312               event_functions = entry->next;
313             }
314           else
315             {
316               prev->next = entry->next;
317             }
318           free(entry);
319           return 1;
320         }
321
322       prev = entry;
323       entry = entry->next;
324     }
325
326   return 0;
327 }
328
329 /*
330  * Sven-Ola, 2007: Since the original timing and flagging is changed (which
331  * saves lots of CPU time - see LinkQualityDijkstraLimit) the original timeout
332  * functions called every olsr_cnf->polltime uses too much CPU now. Because the
333  * changes_xxx handling is switched off with LQDL, it should be OK to call
334  * all timeout handlers at a much lower rate. To overcome UDP packet loss,
335  * a very low pollrate is used.
336  */
337
338 static float dijkstra_initial = 0.0;
339
340 int
341 olsr_register_scheduler_event_dijkstra(void (*event_function)(void *), 
342                               void *par,
343                               float interval, 
344                               float initial, 
345                               olsr_u8_t *trigger)
346 {
347   if (1 < olsr_cnf->lq_level && 0.0 < olsr_cnf->lq_dinter)
348   {
349     dijkstra_initial += olsr_cnf->lq_dinter / 10.0;
350     return olsr_register_scheduler_event(event_function, par, olsr_cnf->lq_dinter, dijkstra_initial, trigger);
351   }
352   return olsr_register_scheduler_event(event_function, par, interval, initial, trigger);
353 }
354
355 int
356 olsr_register_timeout_function(void (*time_out_function)(void), olsr_bool dijkstra_limit_ok)
357 {
358   struct timeout_entry *new_entry;
359
360   if (dijkstra_limit_ok && 1 < olsr_cnf->lq_level && 0.0 < olsr_cnf->lq_dinter)
361   {
362     dijkstra_initial += olsr_cnf->lq_dinter / 10.0;
363     return olsr_register_scheduler_event(
364       (void *)time_out_function,
365       NULL,
366       olsr_cnf->lq_dinter,
367       dijkstra_initial,
368       NULL);
369   }
370   
371   /* check that this entry is not added already */
372   new_entry = timeout_functions;
373   while(new_entry)
374     {
375       if(new_entry->function == time_out_function)
376         {
377           fprintf(stderr, "Register scheduler timeout: Event alread registered!\n");
378           olsr_syslog(OLSR_LOG_ERR, "Register scheduler timeout: Event alread registered!\n");
379           return 0;
380         }
381       new_entry = new_entry->next;
382     }
383
384   new_entry = olsr_malloc(sizeof(struct timeout_entry), "scheduler add timeout");
385
386   new_entry->function = time_out_function;
387   new_entry->next = timeout_functions;
388
389   timeout_functions = new_entry;
390
391   return 1;
392 }
393
394
395
396 int
397 olsr_remove_timeout_function(void (*time_out_function)(void), olsr_bool dijkstra_limit_ok)
398 {
399   struct timeout_entry *entry, *prev;
400
401   if (dijkstra_limit_ok && 1 < olsr_cnf->lq_level && 0.0 < olsr_cnf->lq_dinter)
402   {
403     return olsr_remove_scheduler_event(
404       (void *)time_out_function,
405       NULL,
406       -1.0,
407       -1.0,
408       NULL);
409   }
410   
411   /* check that this entry is not added already */
412   entry = timeout_functions;
413   prev = NULL;
414
415   while(entry)
416     {
417       if(entry->function == time_out_function)
418         {
419           if(entry == timeout_functions)
420             {
421               timeout_functions = entry->next;
422             }
423           else
424             {
425               prev->next = entry->next;
426             }
427           free(entry);
428           return 1;
429         }
430       prev = entry;
431       entry = entry->next;
432     }
433
434   return 0;
435 }
436