src/scheduler.c

   1
   2 /*
   3  * The olsr.org Optimized Link-State Routing daemon(olsrd)
   4  * Copyright (c) 2004-2009, the olsr.org team - see HISTORY file
   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 #include <unistd.h>
  43 #include <assert.h>
  44 #include <stdlib.h>
  45
  46 #include "common/avl.h"
  47 #include "common/avl_olsr_comp.h"
  48 #include "scheduler.h"
  49 #include "link_set.h"
  50 #include "olsr.h"
  51 #include "olsr_cookie.h"
  52 #include "os_net.h"
  53 #include "os_time.h"
  54 #include "olsr_logging.h"
  55
  56 /* Timer data, global. Externed in scheduler.h */
  57 uint32_t now_times;                    /* relative time compared to startup (in milliseconds */
  58 struct timeval first_tv;               /* timevalue during startup */
  59 struct timeval last_tv;                /* timevalue used for last olsr_times() calculation */
  60
  61 /* Hashed root of all timers */
  62 static struct list_entity timer_wheel[TIMER_WHEEL_SLOTS];
  63 static uint32_t timer_last_run;        /* remember the last timeslot walk */
  64
  65 /* Memory cookie for the timer manager */
  66 struct avl_tree timerinfo_tree;
  67 static struct olsr_cookie_info *timer_mem_cookie = NULL;
  68 static struct olsr_cookie_info *timerinfo_cookie = NULL;
  69
  70 /* Head of all OLSR used sockets */
  71 static struct list_entity socket_head;
  72
  73 /* Prototypes */
  74 static void walk_timers(uint32_t *);
  75 static void poll_sockets(void);
  76 static uint32_t calc_jitter(unsigned int rel_time, uint8_t jitter_pct, unsigned int random_val);
  77
  78 /*
  79  * A wrapper around times(2). Note, that this function has some
  80  * portability problems, so do not rely on absolute values returned.
  81  * Under Linux, uclibc and libc directly call the sys_times() located
  82  * in kernel/sys.c and will only return an error if the tms_buf is
  83  * not writeable.
  84  */
  85 static uint32_t
  86 olsr_times(void)
  87 {
  88   struct timeval tv;
  89   uint32_t t;
  90
  91   if (os_gettimeofday(&tv, NULL) != 0) {
  92     OLSR_ERROR(LOG_SCHEDULER, "OS clock is not working, have to shut down OLSR (%s)\n", strerror(errno));
  93     olsr_exit(1);
  94   }
  95
  96   /* test if time jumped backward or more than 60 seconds forward */
  97   if (tv.tv_sec < last_tv.tv_sec || (tv.tv_sec == last_tv.tv_sec && tv.tv_usec < last_tv.tv_usec)
  98       || tv.tv_sec - last_tv.tv_sec > 60) {
  99     OLSR_WARN(LOG_SCHEDULER, "Time jump (%d.%06d to %d.%06d)\n",
 100               (int32_t) (last_tv.tv_sec), (int32_t) (last_tv.tv_usec), (int32_t) (tv.tv_sec), (int32_t) (tv.tv_usec));
 101
 102     t = (last_tv.tv_sec - first_tv.tv_sec) * 1000 + (last_tv.tv_usec - first_tv.tv_usec) / 1000;
 103     t++;                        /* advance time by one millisecond */
 104
 105     first_tv = tv;
 106     first_tv.tv_sec -= (t / 1000);
 107     first_tv.tv_usec -= ((t % 1000) * 1000);
 108
 109     if (first_tv.tv_usec < 0) {
 110       first_tv.tv_sec--;
 111       first_tv.tv_usec += 1000000;
 112     }
 113     last_tv = tv;
 114     return t;
 115   }
 116   last_tv = tv;
 117   return (tv.tv_sec - first_tv.tv_sec) * 1000 + (tv.tv_usec - first_tv.tv_usec) / 1000;
 118 }
 119
 120 /**
 121  * Returns a timestamp s seconds in the future
 122  */
 123 uint32_t
 124 olsr_getTimestamp(uint32_t s)
 125 {
 126   return now_times + s;
 127 }
 128
 129 /**
 130  * Returns the number of milliseconds until the timestamp will happen
 131  */
 132
 133 int32_t
 134 olsr_getTimeDue(uint32_t s)
 135 {
 136   uint32_t diff;
 137   if (s > now_times) {
 138     diff = s - now_times;
 139
 140     /* overflow ? */
 141     if (diff > (1u << 31)) {
 142       return -(int32_t) (0xffffffff - diff);
 143     }
 144     return (int32_t) (diff);
 145   }
 146
 147   diff = now_times - s;
 148   /* overflow ? */
 149   if (diff > (1u << 31)) {
 150     return (int32_t) (0xffffffff - diff);
 151   }
 152   return -(int32_t) (diff);
 153 }
 154
 155 bool
 156 olsr_isTimedOut(uint32_t s)
 157 {
 158   if (s > now_times) {
 159     return s - now_times > (1u << 31);
 160   }
 161
 162   return now_times - s <= (1u << 31);
 163 }
 164
 165 struct olsr_timer_info *
 166 olsr_alloc_timerinfo(const char *name, timer_cb_func callback, bool periodic) {
 167   struct olsr_timer_info *ti;
 168
 169   ti = olsr_cookie_malloc(timerinfo_cookie);
 170   ti->name = strdup(name);
 171   ti->node.key = ti->name;
 172   ti->callback = callback;
 173   ti->periodic = periodic;
 174
 175   avl_insert(&timerinfo_tree, &ti->node);
 176   return ti;
 177 }
 178
 179 /**
 180  * Add a socket and handler to the socketset
 181  * beeing used in the main select(2) loop
 182  * in listen_loop
 183  *
 184  *@param fd the socket
 185  *@param pf the processing function
 186  */
 187 void
 188 add_olsr_socket(int fd, socket_handler_func pf_pr, socket_handler_func pf_imm, void *data, unsigned int flags)
 189 {
 190   struct olsr_socket_entry *new_entry;
 191
 192   if (fd < 0 || (pf_pr == NULL && pf_imm == NULL)) {
 193     OLSR_WARN(LOG_SCHEDULER, "Bogus socket entry - not registering...");
 194     return;
 195   }
 196   OLSR_DEBUG(LOG_SCHEDULER, "Adding OLSR socket entry %d\n", fd);
 197
 198   new_entry = olsr_malloc(sizeof(*new_entry), "Socket entry");
 199
 200   new_entry->fd = fd;
 201   new_entry->process_immediate = pf_imm;
 202   new_entry->process_pollrate = pf_pr;
 203   new_entry->data = data;
 204   new_entry->flags = flags;
 205
 206   /* Queue */
 207   list_add_before(&socket_head, &new_entry->socket_node);
 208 }
 209
 210 /**
 211  * Remove a socket and handler to the socketset
 212  * beeing used in the main select(2) loop
 213  * in listen_loop
 214  *
 215  *@param fd the socket
 216  *@param pf the processing function
 217  */
 218 int
 219 remove_olsr_socket(int fd, socket_handler_func pf_pr, socket_handler_func pf_imm)
 220 {
 221   struct olsr_socket_entry *entry;
 222   struct list_iterator iterator;
 223
 224   if (fd < 0 || (pf_pr == NULL && pf_imm == NULL)) {
 225     OLSR_WARN(LOG_SCHEDULER, "Bogus socket entry - not processing...");
 226     return 0;
 227   }
 228   OLSR_DEBUG(LOG_SCHEDULER, "Removing OLSR socket entry %d\n", fd);
 229
 230   OLSR_FOR_ALL_SOCKETS(entry, iterator) {
 231     if (entry->fd == fd && entry->process_immediate == pf_imm && entry->process_pollrate == pf_pr) {
 232       /* just mark this node as "deleted", it will be cleared later at the end of handle_fds() */
 233       entry->process_immediate = NULL;
 234       entry->process_pollrate = NULL;
 235       entry->flags = 0;      return 1;
 236     }
 237   }
 238   return 0;
 239 }
 240
 241 void
 242 enable_olsr_socket(int fd, socket_handler_func pf_pr, socket_handler_func pf_imm, unsigned int flags)
 243 {
 244   struct olsr_socket_entry *entry;
 245   struct list_iterator iterator;
 246
 247   OLSR_FOR_ALL_SOCKETS(entry, iterator) {
 248     if (entry->fd == fd && entry->process_immediate == pf_imm && entry->process_pollrate == pf_pr) {
 249       entry->flags |= flags;
 250     }
 251   }
 252 }
 253
 254 void
 255 disable_olsr_socket(int fd, socket_handler_func pf_pr, socket_handler_func pf_imm, unsigned int flags)
 256 {
 257   struct olsr_socket_entry *entry;
 258   struct list_iterator iterator;
 259
 260   OLSR_FOR_ALL_SOCKETS(entry, iterator) {
 261     if (entry->fd == fd && entry->process_immediate == pf_imm && entry->process_pollrate == pf_pr) {
 262       entry->flags &= ~flags;
 263     }
 264   }
 265 }
 266
 267 /**
 268  * Close and free all sockets.
 269  */
 270 void
 271 olsr_flush_sockets(void)
 272 {
 273   struct olsr_socket_entry *entry;
 274   struct list_iterator iterator;
 275
 276   OLSR_FOR_ALL_SOCKETS(entry, iterator) {
 277     os_close(entry->fd);
 278     list_remove(&entry->socket_node);
 279     free(entry);
 280   }
 281 }
 282
 283 static void
 284 poll_sockets(void)
 285 {
 286   int n;
 287   struct olsr_socket_entry *entry;
 288   struct list_iterator iterator;
 289   fd_set ibits, obits;
 290   struct timeval tvp = { 0, 0 };
 291   int hfd = 0, fdsets = 0;
 292
 293   /* If there are no registered sockets we
 294    * do not call select(2)
 295    */
 296   if (list_is_empty(&socket_head)) {
 297     return;
 298   }
 299
 300   FD_ZERO(&ibits);
 301   FD_ZERO(&obits);
 302
 303   /* Adding file-descriptors to FD set */
 304   OLSR_FOR_ALL_SOCKETS(entry, iterator) {
 305     if (entry->process_pollrate == NULL) {
 306       continue;
 307     }
 308     if ((entry->flags & SP_PR_READ) != 0) {
 309       fdsets |= SP_PR_READ;
 310       FD_SET((unsigned int)entry->fd, &ibits);  /* And we cast here since we get a warning on Win32 */
 311     }
 312     if ((entry->flags & SP_PR_WRITE) != 0) {
 313       fdsets |= SP_PR_WRITE;
 314       FD_SET((unsigned int)entry->fd, &obits);  /* And we cast here since we get a warning on Win32 */
 315     }
 316     if ((entry->flags & (SP_PR_READ | SP_PR_WRITE)) != 0 && entry->fd >= hfd) {
 317       hfd = entry->fd + 1;
 318     }
 319   }
 320
 321   /* Running select on the FD set */
 322   do {
 323     n = os_select(hfd, fdsets & SP_PR_READ ? &ibits : NULL, fdsets & SP_PR_WRITE ? &obits : NULL, NULL, &tvp);
 324   } while (n == -1 && errno == EINTR);
 325
 326   if (n == 0) {
 327     return;
 328   }
 329   if (n == -1) {                /* Did something go wrong? */
 330     OLSR_WARN(LOG_SCHEDULER, "select error: %s", strerror(errno));
 331     return;
 332   }
 333
 334   /* Update time since this is much used by the parsing functions */
 335   now_times = olsr_times();
 336   OLSR_FOR_ALL_SOCKETS(entry, iterator) {
 337     int flags;
 338     if (entry->process_pollrate == NULL) {
 339       continue;
 340     }
 341     flags = 0;
 342     if (FD_ISSET(entry->fd, &ibits)) {
 343       flags |= SP_PR_READ;
 344     }
 345     if (FD_ISSET(entry->fd, &obits)) {
 346       flags |= SP_PR_WRITE;
 347     }
 348
 349     if (flags) {
 350       OLSR_DEBUG(LOG_SCHEDULER, "Event from socket %d (%d)", entry->fd, flags);
 351     }
 352
 353     if (flags != 0) {
 354       entry->process_pollrate(entry->fd, entry->data, flags);
 355     }
 356   }
 357 }
 358
 359 static void
 360 handle_fds(uint32_t next_interval)
 361 {
 362   struct olsr_socket_entry *entry;
 363   struct list_iterator iterator;
 364   struct timeval tvp;
 365   int32_t remaining;
 366
 367   /* calculate the first timeout */
 368   now_times = olsr_times();
 369
 370   remaining = TIME_DUE(next_interval);
 371   if (remaining <= 0) {
 372     /* we are already over the interval */
 373     if (list_is_empty(&socket_head)) {
 374       /* If there are no registered sockets we do not call select(2) */
 375       return;
 376     }
 377     tvp.tv_sec = 0;
 378     tvp.tv_usec = 0;
 379   } else {
 380     /* we need an absolute time - milliseconds */
 381     tvp.tv_sec = remaining / MSEC_PER_SEC;
 382     tvp.tv_usec = (remaining % MSEC_PER_SEC) * USEC_PER_MSEC;
 383   }
 384
 385   /* do at least one select */
 386   for (;;) {
 387     fd_set ibits, obits;
 388     int n, hfd = 0, fdsets = 0;
 389     FD_ZERO(&ibits);
 390     FD_ZERO(&obits);
 391
 392     /* Adding file-descriptors to FD set */
 393     OLSR_FOR_ALL_SOCKETS(entry, iterator) {
 394       if (entry->process_immediate == NULL) {
 395         continue;
 396       }
 397       if ((entry->flags & SP_IMM_READ) != 0) {
 398         fdsets |= SP_IMM_READ;
 399         FD_SET((unsigned int)entry->fd, &ibits);        /* And we cast here since we get a warning on Win32 */
 400       }
 401       if ((entry->flags & SP_IMM_WRITE) != 0) {
 402         fdsets |= SP_IMM_WRITE;
 403         FD_SET((unsigned int)entry->fd, &obits);        /* And we cast here since we get a warning on Win32 */
 404       }
 405       if ((entry->flags & (SP_IMM_READ | SP_IMM_WRITE)) != 0 && entry->fd >= hfd) {
 406         hfd = entry->fd + 1;
 407       }
 408     }
 409
 410     if (hfd == 0 && (long)remaining <= 0) {
 411       /* we are over the interval and we have no fd's. Skip the select() etc. */
 412       return;
 413     }
 414
 415     do {
 416       n = os_select(hfd, fdsets & SP_IMM_READ ? &ibits : NULL, fdsets & SP_IMM_WRITE ? &obits : NULL, NULL, &tvp);
 417     } while (n == -1 && errno == EINTR);
 418
 419     if (n == 0) {               /* timeout! */
 420       break;
 421     }
 422     if (n == -1) {              /* Did something go wrong? */
 423       OLSR_WARN(LOG_SCHEDULER, "select error: %s", strerror(errno));
 424       break;
 425     }
 426
 427     /* Update time since this is much used by the parsing functions */
 428     now_times = olsr_times();
 429     OLSR_FOR_ALL_SOCKETS(entry, iterator) {
 430       int flags;
 431       if (entry->process_immediate == NULL) {
 432         continue;
 433       }
 434       flags = 0;
 435       if (FD_ISSET(entry->fd, &ibits)) {
 436         flags |= SP_IMM_READ;
 437       }
 438       if (FD_ISSET(entry->fd, &obits)) {
 439         flags |= SP_IMM_WRITE;
 440       }
 441       if (flags != 0) {
 442         entry->process_immediate(entry->fd, entry->data, flags);
 443       }
 444     }
 445
 446     /* calculate the next timeout */
 447     remaining = TIME_DUE(next_interval);
 448     if (remaining <= 0) {
 449       /* we are already over the interval */
 450       break;
 451     }
 452     /* we need an absolute time - milliseconds */
 453     tvp.tv_sec = remaining / MSEC_PER_SEC;
 454     tvp.tv_usec = (remaining % MSEC_PER_SEC) * USEC_PER_MSEC;
 455   }
 456
 457   OLSR_FOR_ALL_SOCKETS(entry, iterator) {
 458     if (entry->process_immediate == NULL && entry->process_pollrate == NULL) {
 459       /* clean up socket handler */
 460       list_remove(&entry->socket_node);
 461       free(entry);
 462     }
 463   }
 464 }
 465
 466 /**
 467  * Main scheduler event loop. Polls at every
 468  * sched_poll_interval and calls all functions
 469  * that are timed out or that are triggered.
 470  * Also calls the olsr_process_changes()
 471  * function at every poll.
 472  *
 473  * @return nada
 474  */
 475 void
 476 olsr_scheduler(void)
 477 {
 478   OLSR_INFO(LOG_SCHEDULER, "Scheduler started - polling every %u ms\n", olsr_cnf->pollrate);
 479
 480   /* Main scheduler loop */
 481   while (app_state == STATE_RUNNING) {
 482     uint32_t next_interval;
 483
 484     /*
 485      * Update the global timestamp. We are using a non-wallclock timer here
 486      * to avoid any undesired side effects if the system clock changes.
 487      */
 488     now_times = olsr_times();
 489     next_interval = GET_TIMESTAMP(olsr_cnf->pollrate);
 490
 491     /* Read incoming data */
 492     poll_sockets();
 493
 494     /* Process timers */
 495     walk_timers(&timer_last_run);
 496
 497     /* Update */
 498     olsr_process_changes();
 499
 500     /* Check for changes in topology */
 501     if (link_changes) {
 502       increase_local_ansn_number();
 503       OLSR_DEBUG(LOG_SCHEDULER, "ANSN UPDATED %d\n\n", get_local_ansn_number());
 504       link_changes = false;
 505     }
 506
 507     /* Read incoming data and handle it immediiately */
 508     handle_fds(next_interval);
 509   }
 510 }
 511
 512 /**
 513  * Decrement a relative timer by a random number range.
 514  *
 515  * @param the relative timer expressed in units of milliseconds.
 516  * @param the jitter in percent
 517  * @param cached result of random() at system init.
 518  * @return the absolute timer in system clock tick units
 519  */
 520 static uint32_t
 521 calc_jitter(unsigned int rel_time, uint8_t jitter_pct, unsigned int random_val)
 522 {
 523   unsigned int jitter_time;
 524
 525   /*
 526    * No jitter or, jitter larger than 99% does not make sense.
 527    * Also protect against overflows resulting from > 25 bit timers.
 528    */
 529   if (jitter_pct == 0 || jitter_pct > 99 || rel_time > (1 << 24)) {
 530     return GET_TIMESTAMP(rel_time);
 531   }
 532
 533   /*
 534    * Play some tricks to avoid overflows with integer arithmetic.
 535    */
 536   jitter_time = (jitter_pct * rel_time) / 100;
 537   jitter_time = random_val / (1 + RAND_MAX / (jitter_time + 1));
 538
 539   OLSR_DEBUG(LOG_TIMER, "TIMER: jitter %u%% rel_time %ums to %ums\n", jitter_pct, rel_time, rel_time - jitter_time);
 540
 541   return GET_TIMESTAMP(rel_time - jitter_time);
 542 }
 543
 544 /**
 545  * Init datastructures for maintaining timers.
 546  */
 547 void
 548 olsr_init_timers(void)
 549 {
 550   int idx;
 551
 552   OLSR_INFO(LOG_SCHEDULER, "Initializing scheduler.\n");
 553
 554   /* Grab initial timestamp */
 555   if (os_gettimeofday(&first_tv, NULL)) {
 556     OLSR_ERROR(LOG_TIMER, "OS clock is not working, have to shut down OLSR (%s)\n", strerror(errno));
 557     olsr_exit(1);
 558   }
 559   last_tv = first_tv;
 560   now_times = olsr_times();
 561
 562   /* init lists */
 563   list_init_head(&socket_head);
 564   for (idx = 0; idx < TIMER_WHEEL_SLOTS; idx++) {
 565     list_init_head(&timer_wheel[idx]);
 566   }
 567
 568   /*
 569    * Reset the last timer run.
 570    */
 571   timer_last_run = now_times;
 572
 573   /* Allocate a cookie for the block based memory manager. */
 574   timer_mem_cookie = olsr_create_memcookie("timer_entry", sizeof(struct timer_entry));
 575
 576   avl_init(&timerinfo_tree, avl_comp_strcasecmp, false, NULL);
 577   timerinfo_cookie = olsr_create_memcookie("timerinfo", sizeof(struct olsr_timer_info));
 578 }
 579
 580 /**
 581  * Walk through the timer list and check if any timer is ready to fire.
 582  * Callback the provided function with the context pointer.
 583  */
 584 static void
 585 walk_timers(uint32_t * last_run)
 586 {
 587   unsigned int total_timers_walked = 0, total_timers_fired = 0;
 588   unsigned int wheel_slot_walks = 0;
 589
 590   /*
 591    * Check the required wheel slots since the last time a timer walk was invoked,
 592    * or check *all* the wheel slots, whatever is less work.
 593    * The latter is meant as a safety belt if the scheduler falls behind.
 594    */
 595   while ((*last_run <= now_times) && (wheel_slot_walks < TIMER_WHEEL_SLOTS)) {
 596     struct list_entity tmp_head_node;
 597     /* keep some statistics */
 598     unsigned int timers_walked = 0, timers_fired = 0;
 599
 600     /* Get the hash slot for this clocktick */
 601     struct list_entity *timer_head_node;
 602
 603     timer_head_node = &timer_wheel[*last_run & TIMER_WHEEL_MASK];
 604
 605     /* Walk all entries hanging off this hash bucket. We treat this basically as a stack
 606      * so that we always know if and where the next element is.
 607      */
 608     list_init_head(&tmp_head_node);
 609     while (!list_is_empty(timer_head_node)) {
 610       /* the top element */
 611       struct timer_entry *timer;
 612
 613       timer = list_first_element(timer_head_node, timer, timer_list);
 614
 615       /*
 616        * Dequeue and insert to a temporary list.
 617        * We do this to avoid loosing our walking context when
 618        * multiple timers fire.
 619        */
 620       list_remove(&timer->timer_list);
 621       list_add_after(&tmp_head_node, &timer->timer_list);
 622       timers_walked++;
 623
 624       /* Ready to fire ? */
 625       if (TIMED_OUT(timer->timer_clock)) {
 626         OLSR_DEBUG(LOG_TIMER, "TIMER: fire %s timer %p, ctx %p, "
 627                    "at clocktick %u (%s)\n",
 628                    timer->timer_info->name,
 629                    timer, timer->timer_cb_context, (unsigned int)*last_run, olsr_wallclock_string());
 630
 631         /* This timer is expired, call into the provided callback function */
 632         timer->timer_in_callback = true;
 633         timer->timer_info->callback(timer->timer_cb_context);
 634         timer->timer_in_callback = false;
 635         timer->timer_info->changes++;
 636
 637         /* Only act on actually running timers */
 638         if (timer->timer_running) {
 639           /*
 640            * Don't restart the periodic timer if the callback function has
 641            * stopped the timer.
 642            */
 643           if (timer->timer_period) {
 644             /* For periodical timers, rehash the random number and restart */
 645             timer->timer_random = random();
 646             olsr_change_timer(timer, timer->timer_period, timer->timer_jitter_pct);
 647           } else {
 648             /* Singleshot timers are stopped */
 649             olsr_stop_timer(timer);
 650           }
 651         }
 652         else {
 653           /* free memory */
 654           olsr_cookie_free(timer_mem_cookie, timer);
 655         }
 656
 657         timers_fired++;
 658       }
 659     }
 660
 661     /*
 662      * Now merge the temporary list back to the old bucket.
 663      */
 664     list_merge(timer_head_node, &tmp_head_node);
 665
 666     /* keep some statistics */
 667     total_timers_walked += timers_walked;
 668     total_timers_fired += timers_fired;
 669
 670     /* Increment the time slot and wheel slot walk iteration */
 671     (*last_run)++;
 672     wheel_slot_walks++;
 673   }
 674
 675   OLSR_DEBUG(LOG_TIMER, "TIMER: processed %4u/%d clockwheel slots, "
 676              "timers walked %4u/%u, timers fired %u\n",
 677              wheel_slot_walks, TIMER_WHEEL_SLOTS, total_timers_walked, timer_mem_cookie->ci_usage, total_timers_fired);
 678
 679   /*
 680    * If the scheduler has slipped and we have walked all wheel slots,
 681    * reset the last timer run.
 682    */
 683   *last_run = now_times;
 684 }
 685
 686 /**
 687  * Stop and delete all timers.
 688  */
 689 void
 690 olsr_flush_timers(void)
 691 {
 692   struct olsr_timer_info *ti;
 693   struct list_iterator iterator;
 694
 695   struct list_entity *timer_head_node;
 696   unsigned int wheel_slot = 0;
 697
 698   for (wheel_slot = 0; wheel_slot < TIMER_WHEEL_SLOTS; wheel_slot++) {
 699     timer_head_node = &timer_wheel[wheel_slot & TIMER_WHEEL_MASK];
 700
 701     /* Kill all entries hanging off this hash bucket. */
 702     while (!list_is_empty(timer_head_node)) {
 703       struct timer_entry *timer;
 704
 705       timer = list_first_element(timer_head_node, timer, timer_list);
 706       olsr_stop_timer(timer);
 707     }
 708   }
 709
 710   /* free all timerinfos */
 711   OLSR_FOR_ALL_TIMERS(ti, iterator) {
 712     avl_delete(&timerinfo_tree, &ti->node);
 713     free(ti->name);
 714     olsr_cookie_free(timerinfo_cookie, ti);
 715   }
 716
 717   /* release memory cookie for timers */
 718   olsr_cleanup_memcookie(timerinfo_cookie);
 719 }
 720
 721 /**
 722  * Returns the difference between gmt and local time in seconds.
 723  * Use gmtime() and localtime() to keep things simple.
 724  *
 725  * taken and slightly modified from www.tcpdump.org.
 726  */
 727 static int
 728 olsr_get_timezone(void)
 729 {
 730 #define OLSR_TIMEZONE_UNINITIALIZED -1
 731   static int time_diff = OLSR_TIMEZONE_UNINITIALIZED;
 732   if (time_diff == OLSR_TIMEZONE_UNINITIALIZED) {
 733     int dir;
 734     const time_t t = time(NULL);
 735     const struct tm gmt = *gmtime(&t);
 736     const struct tm *loc = localtime(&t);
 737
 738     time_diff = (loc->tm_hour - gmt.tm_hour) * 60 * 60 + (loc->tm_min - gmt.tm_min) * 60;
 739
 740     /*
 741      * If the year or julian day is different, we span 00:00 GMT
 742      * and must add or subtract a day. Check the year first to
 743      * avoid problems when the julian day wraps.
 744      */
 745     dir = loc->tm_year - gmt.tm_year;
 746     if (!dir) {
 747       dir = loc->tm_yday - gmt.tm_yday;
 748     }
 749
 750     time_diff += dir * 24 * 60 * 60;
 751   }
 752   return time_diff;
 753 }
 754
 755 /**
 756  * Format an absolute wallclock system time string.
 757  * May be called upto 4 times in a single printf() statement.
 758  * Displays microsecond resolution.
 759  *
 760  * @return buffer to a formatted system time string.
 761  */
 762 const char *
 763 olsr_wallclock_string(void)
 764 {
 765   static char buf[sizeof("00:00:00.000000")];
 766   struct timeval now;
 767   int sec, usec;
 768
 769   os_gettimeofday(&now, NULL);
 770
 771   sec = (int)now.tv_sec + olsr_get_timezone();
 772   usec = (int)now.tv_usec;
 773
 774   snprintf(buf, sizeof(buf), "%02d:%02d:%02d.%06d", (sec % 86400) / 3600, (sec % 3600) / 60, sec % 60, usec);
 775
 776   return buf;
 777 }
 778
 779 /**
 780  * Format an relative non-wallclock system time string.
 781  * May be called upto 4 times in a single printf() statement.
 782  * Displays millisecond resolution.
 783  *
 784  * @param absolute time expressed in clockticks
 785  * @return buffer to a formatted system time string.
 786  */
 787 const char *
 788 olsr_clock_string(uint32_t clk)
 789 {
 790   static char buf[sizeof("00:00:00.000")];
 791
 792   /* On most systems a clocktick is a 10ms quantity. */
 793   unsigned int msec = clk % 1000;
 794   unsigned int sec = clk / 1000;
 795
 796   snprintf(buf, sizeof(buf), "%02u:%02u:%02u.%03u", sec / 3600, (sec % 3600) / 60, (sec % 60), (msec % MSEC_PER_SEC));
 797
 798   return buf;
 799 }
 800
 801 /**
 802  * Start a new timer.
 803  *
 804  * @param relative time expressed in milliseconds
 805  * @param jitter expressed in percent
 806  * @param timer callback function
 807  * @param context for the callback function
 808  * @return a pointer to the created entry
 809  */
 810 struct timer_entry *
 811 olsr_start_timer(unsigned int rel_time,
 812                  uint8_t jitter_pct, void *context, struct olsr_timer_info *ti)
 813 {
 814   struct timer_entry *timer;
 815
 816   assert(ti != 0);          /* we want timer cookies everywhere */
 817   assert(rel_time);
 818   assert(jitter_pct <= 100);
 819
 820   timer = olsr_cookie_malloc(timer_mem_cookie);
 821
 822   /*
 823    * Compute random numbers only once.
 824    */
 825   if (!timer->timer_random) {
 826     timer->timer_random = random();
 827   }
 828
 829   /* Fill entry */
 830   timer->timer_clock = calc_jitter(rel_time, jitter_pct, timer->timer_random);
 831   timer->timer_cb_context = context;
 832   timer->timer_jitter_pct = jitter_pct;
 833   timer->timer_running = true;
 834
 835   /* The cookie is used for debugging to traceback the originator */
 836   timer->timer_info = ti;
 837   ti->usage++;
 838   ti->changes++;
 839
 840   /* Singleshot or periodical timer ? */
 841   timer->timer_period = ti->periodic ? rel_time : 0;
 842
 843   /*
 844    * Now insert in the respective timer_wheel slot.
 845    */
 846   list_add_before(&timer_wheel[timer->timer_clock & TIMER_WHEEL_MASK], &timer->timer_list);
 847
 848   OLSR_DEBUG(LOG_TIMER, "TIMER: start %s timer %p firing in %s, ctx %p\n",
 849              ti->name, timer, olsr_clock_string(timer->timer_clock), context);
 850
 851   return timer;
 852 }
 853 #include "valgrind/valgrind.h"
 854
 855 /**
 856  * Delete a timer.
 857  *
 858  * @param the timer_entry that shall be removed
 859  * @return nada
 860  */
 861 void
 862 olsr_stop_timer(struct timer_entry *timer)
 863 {
 864   /* It's okay to get a NULL here */
 865   if (timer == NULL) {
 866     return;
 867   }
 868
 869   assert(timer->timer_info);     /* we want timer cookies everywhere */
 870   assert(timer->timer_list.next != NULL && timer->timer_list.prev != NULL);
 871
 872   OLSR_DEBUG(LOG_TIMER, "TIMER: stop %s timer %p, ctx %p\n",
 873              timer->timer_info->name, timer, timer->timer_cb_context);
 874
 875
 876   /*
 877    * Carve out of the existing wheel_slot and free.
 878    */
 879   list_remove(&timer->timer_list);
 880   timer->timer_running = false;
 881   timer->timer_info->usage--;
 882   timer->timer_info->changes++;
 883
 884   if (!timer->timer_in_callback) {
 885     olsr_cookie_free(timer_mem_cookie, timer);
 886   }
 887 }
 888
 889 /**
 890  * Change a timer_entry.
 891  *
 892  * @param timer_entry to be changed.
 893  * @param new relative time expressed in units of milliseconds.
 894  * @param new jitter expressed in percent.
 895  * @return nada
 896  */
 897 void
 898 olsr_change_timer(struct timer_entry *timer, unsigned int rel_time, uint8_t jitter_pct)
 899 {
 900   /* Sanity check. */
 901   if (!timer) {
 902     return;
 903   }
 904
 905   assert(timer->timer_info);     /* we want timer cookies everywhere */
 906
 907   /* Singleshot or periodical timer ? */
 908   timer->timer_period = timer->timer_info->periodic ? rel_time : 0;
 909
 910   timer->timer_clock = calc_jitter(rel_time, jitter_pct, timer->timer_random);
 911   timer->timer_jitter_pct = jitter_pct;
 912
 913   /*
 914    * Changes are easy: Remove timer from the exisiting timer_wheel slot
 915    * and reinsert into the new slot.
 916    */
 917   list_remove(&timer->timer_list);
 918   list_add_before(&timer_wheel[timer->timer_clock & TIMER_WHEEL_MASK], &timer->timer_list);
 919
 920   OLSR_DEBUG(LOG_TIMER, "TIMER: change %s timer %p, firing to %s, ctx %p\n",
 921              timer->timer_info->name, timer,
 922              olsr_clock_string(timer->timer_clock), timer->timer_cb_context);
 923 }
 924
 925 /*
 926  * This is the one stop shop for all sort of timer manipulation.
 927  * Depending on the paseed in parameters a new timer is started,
 928  * or an existing timer is started or an existing timer is
 929  * terminated.
 930  */
 931 void
 932 olsr_set_timer(struct timer_entry **timer_ptr,
 933                unsigned int rel_time,
 934                uint8_t jitter_pct, void *context, struct olsr_timer_info *ti)
 935 {
 936   assert(ti);          /* we want timer cookies everywhere */
 937   if (rel_time == 0) {
 938     /* No good future time provided, kill it. */
 939     olsr_stop_timer(*timer_ptr);
 940     *timer_ptr = NULL;
 941   }
 942   else if ((*timer_ptr) == NULL) {
 943     /* No timer running, kick it. */
 944     *timer_ptr = olsr_start_timer(rel_time, jitter_pct, context, ti);
 945   }
 946   else {
 947     olsr_change_timer(*timer_ptr, rel_time, jitter_pct);
 948   }
 949 }
 950
 951 /*
 952  * Local Variables:
 953  * c-basic-offset: 2
 954  * indent-tabs-mode: nil
 955  * End:
 956  */