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