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