From Hannes Gredler <hannes@gredler.at>: refactor the timer implementation
authorHannes Gredler <hannes@gredler.at>
Tue, 19 Feb 2008 22:49:52 +0000 (23:49 +0100)
committerHannes Gredler <hannes@gredler.at>
Tue, 19 Feb 2008 22:49:52 +0000 (23:49 +0100)
-slash all timeout functions and the corresponding infrastructure
-slash all event functions and the corresponding infrastructure

  that means all polling based timer comparisions have been removed.
  the scheduler rate can be now brought down to 10ms without much
  additional overhead.

-introduce a new wheel based timer similar to the BSD kernel implementation
 described in http://www.olsr.org/docs/wucs-95-23.pdf

 there are three major calls

  olsr_start_timer()
  olsr_stop_timer()
  olsr_change_timer()

alternatively there is a one-stop shop that figures out on its own what
to do.

  olsr_set_timer()

this comes handy for avoiding a lot of copy and paste code updating
all the client code.

the new timer API supports periodical and singleshot timers.
once the timer expires a provided function along with a context pointer
is called back. After the singleshot timer fires the used memeory for
the timer is not freed but rather returned to a free memory pool for
avoiding malloc() churn.

the implementation is very efficient as all timer start/stop/change operations
are done in O(1) complexity. walking the timer slot in the main scheduler loop
has a complexity of O(N/K) where K is 256 which should give reasonable defaults
for thousands of timers in the system.

as a sideeffect all wallclock timer references have been removed. now only
one non-wallclock timer obtained by the times() call is maintained.

note that the olsr_secure plugin does keep its wallclock based timer.
it is left to the olsrd_secure plugin authors to convert this to a
non-wallclock based timers to avoid disaster events like when the system
clock changes.

60 files changed:
.hgignore
lib/arprefresh/src/olsrd_arprefresh.c
lib/bmf/src/Bmf.c
lib/bmf/src/NetworkInterfaces.c
lib/bmf/src/olsrd_plugin.c
lib/dyn_gw/src/olsrd_dyn_gw.c
lib/dyn_gw_plain/src/olsrd_dyn_gw_plain.c
lib/httpinfo/src/olsrd_httpinfo.c
lib/nameservice/src/mapwrite.c
lib/nameservice/src/nameservice.c
lib/nameservice/src/nameservice.h
lib/nameservice/src/olsrd_plugin.c
lib/quagga/src/olsrd_plugin.c
lib/secure/src/olsrd_plugin.c
lib/secure/src/olsrd_secure.c
lib/tas/src/plugin.c
lib/tas/src/plugin.h
lib/txtinfo/src/olsrd_txtinfo.c
src/defs.h
src/duplicate_set.c
src/duplicate_set.h
src/generate_msg.h
src/hashing.c
src/hashing.h
src/hna_set.c
src/hna_set.h
src/hysteresis.c
src/interfaces.c
src/interfaces.h
src/link_set.c
src/link_set.h
src/linux/apm.c
src/linux/link_layer.c
src/lq_list.h
src/lq_packet.c
src/lq_route.c
src/lq_route.h
src/main.c
src/mid_set.c
src/mid_set.h
src/mpr_selector_set.c
src/mpr_selector_set.h
src/neighbor_table.c
src/neighbor_table.h
src/olsr.c
src/olsr_protocol.h
src/olsr_types.h
src/packet.c
src/parser.c
src/process_package.c
src/routing_table.c
src/scheduler.c
src/scheduler.h
src/socket_parser.c
src/socket_parser.h
src/tc_set.c
src/tc_set.h
src/two_hop_neighbor_table.c
src/unix/ifnet.c
src/win32/ifnet.c

index ec70ee4..40fb0d5 100644 (file)
--- a/.hgignore
+++ b/.hgignore
@@ -5,7 +5,9 @@ syntax: glob
 *.diff
 *.rej
 *.orig
+*.swp
 *~
+*.out.*
 TAGS
 olsrd
 src/builddata.c
index 9210ff6..d45107d 100644 (file)
@@ -188,7 +188,8 @@ int olsrd_plugin_init(void)
                    0 <= setsockopt(arprefresh_sockfd, SOL_SOCKET, SO_ATTACH_FILTER, &filter, sizeof(filter)))
                {
                        /* Register the ARP refresh event */
-                       olsr_register_scheduler_event(&olsr_arp_event, NULL, 2, 0, NULL);
+                        olsr_start_timer(2 * MSEC_PER_SEC, 0, OLSR_TIMER_PERIODIC,
+                                         &olsr_arp_event, NULL, 0);
                        ret = 1;
                }
                else
index a93f524..3b116fe 100644 (file)
@@ -60,7 +60,7 @@
 #include "defs.h" /* olsr_cnf, OLSR_PRINTF */
 #include "ipcalc.h"
 #include "olsr.h" /* olsr_printf */
-#include "scheduler.h" /* olsr_register_scheduler_event */
+#include "scheduler.h" /* olsr_start_timer() */
 #include "mid_set.h" /* mid_lookup_main_addr() */
 #include "mpr_selector_set.h" /* olsr_lookup_mprs_set() */
 #include "link_set.h" /* get_best_link_to_neighbor() */
index 0969cbf..f1ffb75 100644 (file)
@@ -461,9 +461,7 @@ void FindNeighbors(
   {
     struct link_entry* walker;
 
-    /* TODO: get_link_set() is not thread-safe! */
-    for (walker = get_link_set(); walker != NULL; walker = walker->next) 
-    {
+    OLSR_FOR_ALL_LINK_ENTRIES(walker) {
 #ifndef NODEBUG
       struct ipaddr_str buf;
 #endif
@@ -550,7 +548,7 @@ void FindNeighbors(
       }
 
       *nPossibleNeighbors += 1;
-    } /* for */
+    } OLSR_FOR_ALL_LINK_ENTRIES_END(walker);
 
   }
   /* handle the LQ case */
@@ -775,9 +773,7 @@ void FindNeighbors(
       }
     }
 
-    /* TODO: get_link_set() is not thread-safe! */
-    for (walker = get_link_set(); walker != NULL; walker = walker->next) 
-    {
+    OLSR_FOR_ALL_LINK_ENTRIES(walker) {
 #ifndef NODEBUG
       struct ipaddr_str buf;
 #endif
@@ -994,7 +990,7 @@ void FindNeighbors(
       }
 
       *nPossibleNeighbors += 1;
-    } /* for */
+    } OLSR_FOR_ALL_LINK_ENTRIES_END(walker);
 
 #endif /* USING_THALES_LINK_COST_ROUTING */
 
index 3625965..bc08401 100644 (file)
@@ -45,7 +45,7 @@
 #include "olsrd_plugin.h"
 #include "plugin_util.h"
 #include "defs.h" /* olsr_u8_t, olsr_cnf */
-#include "scheduler.h" /* olsr_register_scheduler_event */
+#include "scheduler.h" /* olsr_start_timer() */
 
 /* BMF includes */
 #include "Bmf.h" /* InitBmf(), CloseBmf() */
@@ -98,7 +98,9 @@ int olsrd_plugin_init(void)
   add_ifchgf(&InterfaceChange);
 
   /* Register the duplicate registration pruning process */
-  olsr_register_scheduler_event(&PrunePacketHistory, NULL, 3.0, 2.0, NULL);
+  olsr_start_timer(3 * MSEC_PER_SEC, 0, OLSR_TIMER_PERIODIC,
+                   &PrunePacketHistory, NULL, 0);
+
 
   return InitBmf(NULL);
 }
index 621ce48..3c2e53f 100644 (file)
@@ -1,4 +1,3 @@
-
 /*
  * The olsr.org Optimized Link-State Routing daemon(olsrd)
  * Copyright (c) 2004, Andreas Tønnesen(andreto@olsr.org)
 
 #include "olsr_types.h"
 #include "olsrd_dyn_gw.h"
-#include "scheduler.h"
 #include "olsr.h"
 #include "defs.h"
 #include "ipcalc.h"
+#include "scheduler.h"
 
 #include <stdio.h>
 #include <string.h>
@@ -251,7 +250,8 @@ olsrd_plugin_init(void)
   pthread_create(&ping_thread, NULL, (void *(*)(void *))looped_checks, NULL);
   
   /* Register the GW check */
-  olsr_register_scheduler_event(&olsr_event_doing_hna, NULL, 3, 4, NULL);
+  olsr_start_timer(3 * MSEC_PER_SEC, 0, OLSR_TIMER_PERIODIC,
+                   &olsr_event_doing_hna, NULL, 0);
 
   return 1;
 }
index 8ea7989..fd1149c 100644 (file)
@@ -95,7 +95,8 @@ olsrd_plugin_init(void)
   }
 
   /* Register the GW check */
-  olsr_register_scheduler_event(&olsr_event, NULL, 3, 4, NULL);
+  olsr_start_timer(3 * MSEC_PER_SEC, 0, OLSR_TIMER_PERIODIC,
+                   &olsr_event, NULL, 0);
 
   return 1;
 }
index ba9001a..72ede97 100644 (file)
@@ -980,7 +980,7 @@ static int build_neigh_body(char *buf, olsr_u32_t bufsize)
   size += snprintf(&buf[size], bufsize-size, "</tr>\n");
 
   /* Link set */
-  for (link = link_set; link != NULL; link = link->next) {
+  OLSR_FOR_ALL_LINK_ENTRIES(link) {
     size += snprintf(&buf[size], bufsize-size, "<tr>");
     size += build_ipaddr_with_link(&buf[size], bufsize, &link->local_iface_addr, -1);
     size += build_ipaddr_with_link(&buf[size], bufsize, &link->neighbor_iface_addr, -1);
@@ -999,7 +999,7 @@ static int build_neigh_body(char *buf, olsr_u32_t bufsize)
                        olsr_etx_to_string(olsr_calc_link_etx(link)));
     }
     size += snprintf(&buf[size], bufsize-size, "</tr>\n");
-  }
+  } OLSR_FOR_ALL_LINK_ENTRIES_END(link);
 
   size += snprintf(&buf[size], bufsize-size, "</table>\n");
 
index 1545616..7bf23f6 100644 (file)
@@ -54,16 +54,20 @@ static char* lookup_position_latlon(union olsr_ip_addr *ip)
 {
   int hash;
   struct db_entry *entry;
-  if (ipequal(ip, &olsr_cnf->main_addr))
-  {
+  struct list_node *list_head, *list_node;
+
+  if (ipequal(ip, &olsr_cnf->main_addr)) {
     return my_latlon_str;
   }
-  for (hash = 0; hash < HASHSIZE; hash++) 
-  {
-    for(entry = latlon_list[hash]; entry != NULL; entry = entry->next)
-    {
-      if (NULL != entry->names && ipequal(&entry->originator, ip))
-      {
+
+  for (hash = 0; hash < HASHSIZE; hash++) {
+      list_head = &latlon_list[hash];
+      for (list_node = list_head->next; list_node != list_head;
+           list_node = list_node->next) {
+
+          entry = list2db(list_node);
+
+      if (entry->names && ipequal(&entry->originator, ip)) {
         return entry->names->name;
       }
     }
@@ -143,8 +147,14 @@ void mapwrite_work(FILE* fmap)
   for (hash = 0; hash < HASHSIZE; hash++) 
   {
     struct db_entry *entry;
-    for(entry = latlon_list[hash]; entry != NULL; entry = entry->next)
-    {
+       struct list_node *list_head, *list_node;
+
+    list_head = &latlon_list[hash];
+    for (list_node = list_head->next; list_node != list_head;
+         list_node = list_node->next) {
+        
+      entry = list2db(list_node);
+
       if (NULL != entry->names)
       {
         if (0 > fprintf(fmap, "Node('%s',%s,'%s','%s');\n",
@@ -207,7 +217,7 @@ void mapwrite_work(FILE* fmap)
 static const char* the_fifoname = 0;
 static int fifopolltime = 0;
 
-static void mapwrite_poll(void)
+static void mapwrite_poll(void *context __attribute__((unused)))
 {
   fifopolltime++;
   if (0 == (fifopolltime & 7) && 0 != the_fifoname)
@@ -251,7 +261,7 @@ int mapwrite_init(const char* fifoname)
     else
     {
       the_fifoname = fifoname;
-      olsr_register_timeout_function(&mapwrite_poll, OLSR_FALSE);
+      olsr_start_timer(100, 5, OLSR_TIMER_PERIODIC, &mapwrite_poll, NULL, 0);
     }
   }
   return OLSR_TRUE;
index 329067d..d1b64db 100644 (file)
@@ -60,7 +60,6 @@
 #include "plugin_util.h"
 #include "nameservice.h"
 #include "mapwrite.h"
-#include "olsrd_copy.h"
 #include "compat.h"
 
 
@@ -82,21 +81,25 @@ float my_lat = 0.0, my_lon = 0.0;
  * my own hostnames, service_lines and dns-servers
  * are store in a linked list (without hashing)
  * */
-static struct db_entry* list[HASHSIZE];
+static struct list_node list[HASHSIZE];
 struct name_entry *my_names = NULL;
+struct timer_entry *name_table_write = NULL;
 static olsr_bool name_table_changed = OLSR_TRUE;
 
-static struct db_entry* service_list[HASHSIZE];
+static struct list_node service_list[HASHSIZE];
 static struct name_entry *my_services = NULL;
 static olsr_bool service_table_changed = OLSR_TRUE;
 
-static struct db_entry* forwarder_list[HASHSIZE];
+static struct list_node forwarder_list[HASHSIZE];
 static struct name_entry *my_forwarders = NULL;
 static olsr_bool forwarder_table_changed = OLSR_TRUE;
 
-struct db_entry* latlon_list[HASHSIZE];
+struct list_node latlon_list[HASHSIZE];
 static olsr_bool latlon_table_changed = OLSR_TRUE;
 
+/* backoff timer for writing changes into a file */
+struct timer_entry *write_file_timer = NULL;
+
 /* regular expression to be matched by valid hostnames, compiled in name_init() */
 static regex_t regex_t_name;
 static regmatch_t regmatch_t_name;
@@ -146,12 +149,12 @@ name_constructor(void)
        my_latlon_file[0] = '\0';
        latlon_in_file[0] = '\0';
        
-       /* init lists */
+       /* init the lists heads */
        for(i = 0; i < HASHSIZE; i++) {
-               list[i] = NULL;
-               forwarder_list[i] = NULL;
-               service_list[i] = NULL;
-               latlon_list[i] = NULL;
+               list_head_init(&list[i]);
+               list_head_init(&forwarder_list[i]);
+               list_head_init(&service_list[i]);
+               list_head_init(&latlon_list[i]);
        }
        
 
@@ -372,8 +375,11 @@ name_init(void)
 
        /* register functions with olsrd */
        olsr_parser_add_function(&olsr_parser, PARSER_TYPE, 1);
-       olsr_register_timeout_function(&olsr_timeout, OLSR_TRUE);
-       olsr_register_scheduler_event(&olsr_event, NULL, my_interval, 0, NULL);
+
+       /* periodic message generation */
+       olsr_start_timer(my_interval * MSEC_PER_SEC, EMISSION_JITTER,
+                                        OLSR_TIMER_PERIODIC, &olsr_namesvc_gen, NULL, 0);
+
        mapwrite_init(my_latlon_file);
 
        return 1;
@@ -453,108 +459,101 @@ name_destructor(void)
 
 /* free all list entries */
 void 
-free_all_list_entries(struct db_entry **this_db_list) 
+free_all_list_entries(struct list_node *this_db_list) 
 {
+       struct db_entry *db;
+       struct list_node *list_head, *list_node;
+
        int i;
        
-       for(i = 0; i < HASHSIZE; i++)
-       {
-               struct db_entry **tmp = &this_db_list[i];
-               while(*tmp != NULL)
-               {
-                       struct db_entry *to_delete = *tmp;
-                       *tmp = (*tmp)->next;
-                       free_name_entry_list(&to_delete->names);
-                       free(to_delete);
-                       to_delete = NULL;
+       for (i = 0; i < HASHSIZE; i++) {
+
+               list_head = &this_db_list[i];
+
+               for (list_node = list_head->next;
+                        list_node != list_head;
+                        list_node = list_node->next) {
+
+                       /* map list node to db_entry */
+                       db = NULL;
+                       free_name_entry_list(&db->names);
+                       free(db);
                }
        }
 }
 
 
 /**
- * A timeout function called every time
- *
- * XXX:the scheduler is polled (by default 10 times a sec,
- * which is far too often):
- *
- * time out old list entries
- * and write changes to file
+ * The write file timer has fired.
  */
-
-static int timeout_roundrobin = 0;
-
 void
-olsr_timeout(void)
+olsr_expire_write_file_timer(void *context __attribute__((unused)))
 {
-       switch(timeout_roundrobin++)
-       {
-               case 0:
-                       timeout_old_names(list, &name_table_changed);
-                       timeout_old_names(forwarder_list, &forwarder_table_changed);
-                       timeout_old_names(service_list, &service_table_changed);
-                       timeout_old_names(latlon_list, &latlon_table_changed);
-                       break;
-               case 1:
-                       write_resolv_file(); // if forwarder_table_changed
-                       break;
-               case 2:
-                       write_hosts_file(); // if name_table_changed
-                       break;
-               case 3:
-                       write_services_file(); // if service_table_changed
-                       break;
+       write_file_timer = NULL;
+
+       write_resolv_file();   /* if forwarder_table_changed */
+       write_hosts_file();    /* if name_table_changed */
+       write_services_file(); /* if service_table_changed */
 #ifdef WIN32
-               case 4:
-                       write_latlon_file(); // latlon_table_changed
-                       break;
+       write_latlon_file();   /* if latlon_table_changed */
 #endif
-               default:
-                       timeout_roundrobin = 0;
-       } // switch
 }
 
-void
-timeout_old_names(struct db_entry **this_list, olsr_bool *this_table_changed)
+
+/*
+ * Kick a timer to write everything into a file.
+ * This also paces things a bit.
+ */
+static void
+olsr_start_write_file_timer(void)
 {
-       struct db_entry **tmp;
-       struct db_entry *to_delete;
-       int index;
+       if (write_file_timer) {
+               return;
+       }
 
-       for(index=0;index<HASHSIZE;index++)
-       {
-               for (tmp = &this_list[index]; *tmp != NULL; )
-               {
-                       /* check if the entry for this ip is timed out */
-                       if (olsr_timed_out(&(*tmp)->timer))
-                       {
+       write_file_timer = olsr_start_timer(5 * MSEC_PER_SEC, 5, OLSR_TIMER_ONESHOT,
+                                                                               olsr_expire_write_file_timer, NULL, 0);
+}
+
+/*
+ * Delete and unlink db_entry.
+ */
+static void
+olsr_namesvc_delete_db_entry(struct db_entry *db)
+{
 #ifndef NODEBUG
-                               struct ipaddr_str strbuf;
+       struct ipaddr_str strbuf;
 #endif
-                               to_delete = *tmp;
-                               /* update the pointer in the linked list */
-                               *tmp = (*tmp)->next;
-                               
-                               OLSR_PRINTF(2, "NAME PLUGIN: %s timed out... deleting\n", 
-                                       olsr_ip_to_string(&strbuf, &to_delete->originator));
+       OLSR_PRINTF(2, "NAME PLUGIN: %s timed out... deleting\n", 
+                               olsr_ip_to_string(&strbuf, &to_delete->originator));
+
+       olsr_start_write_file_timer();
+       olsr_stop_timer(db->db_timer); /* stop timer if running */
        
-                               /* Delete */
-                               free_name_entry_list(&to_delete->names);
-                               free(to_delete);
-                               *this_table_changed = OLSR_TRUE;
-                       } else {
-                               tmp = &(*tmp)->next;
-                       }
-               }
-       }
+       /* Delete */
+       free_name_entry_list(&db->names);
+       free(db);
 }
 
+/**
+ * Callback for the db validity timer.
+ */
+static void
+olsr_nameservice_expire_db_timer(void *context)
+{
+  struct db_entry *db;
+
+  db = (struct db_entry *)context;
+  db->db_timer = NULL; /* be pedandic */
+
+  olsr_namesvc_delete_db_entry(db);
+}
 
 /**
  * Scheduled event: generate and send NAME packet
  */
 void
-olsr_event(void *foo __attribute__((unused)))
+olsr_namesvc_gen(void *foo __attribute__((unused)))
 {
        /* send buffer: huge */
        char buffer[10240];
@@ -824,7 +823,9 @@ decap_namemsg(struct name *from_packet, struct name_entry **to, olsr_bool *this_
                                free(already_saved_name_entries->name);
                                already_saved_name_entries->name = olsr_malloc(len_of_name + 1, "upd name_entry name");
                                strncpy(already_saved_name_entries->name, name, len_of_name);
+
                                *this_table_changed = OLSR_TRUE;
+                               olsr_start_write_file_timer();
                        }
                        if (!ipequal(&already_saved_name_entries->ip, &from_packet->ip))
                        {
@@ -836,7 +837,9 @@ decap_namemsg(struct name *from_packet, struct name_entry **to, olsr_bool *this_
                                        olsr_ip_to_string(&strbuf2, &from_packet->ip),
                                        olsr_ip_to_string(&strbuf3, &already_saved_name_entries->ip));
                                already_saved_name_entries->ip = from_packet->ip;
+
                                *this_table_changed = OLSR_TRUE;
+                               olsr_start_write_file_timer();
                        }
                        if (!*this_table_changed)
                        {
@@ -860,6 +863,7 @@ decap_namemsg(struct name *from_packet, struct name_entry **to, olsr_bool *this_
                tmp->name, olsr_ip_to_string(&strbuf, &tmp->ip), tmp->len, tmp->type);
 
        *this_table_changed = OLSR_TRUE;
+       olsr_start_write_file_timer();
 
        // queue to front
        tmp->next = *to;
@@ -899,19 +903,24 @@ update_name_entry(union olsr_ip_addr *originator, struct namemsg *msg, int msg_s
                
                switch (ntohs(from_packet->type)) {
                        case NAME_HOST: 
-                               insert_new_name_in_list(originator, list, from_packet, &name_table_changed, vtime); 
+                               insert_new_name_in_list(originator, list, from_packet,
+                                                                               &name_table_changed, vtime); 
                                break;
                        case NAME_FORWARDER:
-                               insert_new_name_in_list(originator, forwarder_list, from_packet, &forwarder_table_changed, vtime); 
+                               insert_new_name_in_list(originator, forwarder_list, from_packet,
+                                                                               &forwarder_table_changed, vtime); 
                                break;
                        case NAME_SERVICE:
-                               insert_new_name_in_list(originator, service_list, from_packet, &service_table_changed, vtime); 
+                               insert_new_name_in_list(originator, service_list, from_packet,
+                                                                               &service_table_changed, vtime); 
                                break;
                        case NAME_LATLON:
-                               insert_new_name_in_list(originator, latlon_list, from_packet, &latlon_table_changed, vtime);
+                               insert_new_name_in_list(originator, latlon_list, from_packet,
+                                                                               &latlon_table_changed, vtime);
                                break;
                        default:
-                               OLSR_PRINTF(3, "NAME PLUGIN: Received Message of unknown type [%d] from (%s)\n", from_packet->type, olsr_ip_to_string(&strbuf, originator));
+                               OLSR_PRINTF(3, "NAME PLUGIN: Received Message of unknown type [%d] from (%s)\n",
+                                                       from_packet->type, olsr_ip_to_string(&strbuf, originator));
                                break;
                }
 
@@ -928,51 +937,68 @@ update_name_entry(union olsr_ip_addr *originator, struct namemsg *msg, int msg_s
  * corresponding entry for this ip in the corresponding hash table
  */
 void
-insert_new_name_in_list(union olsr_ip_addr *originator, struct db_entry **this_list, struct name *from_packet, olsr_bool *this_table_changed, double vtime)
+insert_new_name_in_list(union olsr_ip_addr *originator,
+                                               struct list_node *this_list,
+                                               struct name *from_packet, olsr_bool *this_table_changed,
+                                               double vtime)
 {
        int hash;
        struct db_entry *entry;
+       struct list_node *list_head, *list_node;
 
        olsr_bool entry_found = OLSR_FALSE;
 
-       hash = olsr_hashing(originator);
+       hash = olsr_ip_hashing(originator);
 
        /* find the entry for originator, if there is already one */
-       for (entry = this_list[hash]; entry != NULL; entry = entry->next)
-       {
+       list_head = &this_list[hash];
+       for (list_node = list_head->next; list_node != list_head;
+                list_node = list_node->next) {
+
+               entry = list2db(list_node);
+
                if (ipequal(originator, &entry->originator)) {
 #ifndef NODEBUG
                        struct ipaddr_str strbuf;
 #endif
                        // found
-                       OLSR_PRINTF(4, "NAME PLUGIN: found entry for (%s) in its hash table\n", olsr_ip_to_string(&strbuf, originator));
+                       OLSR_PRINTF(4, "NAME PLUGIN: found entry for (%s) in its hash table\n",
+                                               olsr_ip_to_string(&strbuf, originator));
 
                        //delegate to function for parsing the packet and linking it to entry->names
                        decap_namemsg(from_packet, &entry->names, this_table_changed);
 
-                       olsr_get_timestamp(vtime * 1000, &entry->timer);
+                       olsr_set_timer(&entry->db_timer, vtime * MSEC_PER_SEC,
+                                                  OLSR_NAMESVC_DB_JITTER, OLSR_TIMER_ONESHOT,
+                                                  &olsr_nameservice_expire_db_timer, entry, 0);
 
                        entry_found = OLSR_TRUE;
                }
        }
+
        if (! entry_found)
        {
 #ifndef NODEBUG
                struct ipaddr_str strbuf;
 #endif
-               OLSR_PRINTF(3, "NAME PLUGIN: create new db entry for ip (%s) in hash table\n", olsr_ip_to_string(&strbuf, originator));
+               OLSR_PRINTF(3, "NAME PLUGIN: create new db entry for ip (%s) in hash table\n",
+                                       olsr_ip_to_string(&strbuf, originator));
 
                /* insert a new entry */
                entry = olsr_malloc(sizeof(struct db_entry), "new db_entry");
+               memset(entry, 0, sizeof(struct db_entry));
 
                entry->originator = *originator;
-               olsr_get_timestamp(vtime * 1000, &entry->timer);
-               entry->names = NULL;
 
-               // queue to front
-               entry->next = this_list[hash];
-               this_list[hash] = entry;
+               olsr_set_timer(&entry->db_timer, vtime * MSEC_PER_SEC,
+                                          OLSR_LINK_LOSS_JITTER, OLSR_TIMER_ONESHOT,
+                                          &olsr_nameservice_expire_db_timer, entry, 0);
+
+               entry->names = NULL;
 
+               /* insert to the list */
+               list_add_before(&this_list[hash], &entry->db_list);
+               
                //delegate to function for parsing the packet and linking it to entry->names
                decap_namemsg(from_packet, &entry->names, this_table_changed);
        }
@@ -987,6 +1013,7 @@ write_hosts_file(void)
        int hash;
        struct name_entry *name;
        struct db_entry *entry;
+       struct list_node *list_head, *list_node;
        FILE* hosts;
        FILE* add_hosts;
        int c=0;
@@ -1035,25 +1062,26 @@ write_hosts_file(void)
        }
        
        // write received names
-       for (hash = 0; hash < HASHSIZE; hash++) 
-       {
-               for(entry = list[hash]; entry != NULL; entry = entry->next)
-               {
-                       for (name = entry->names; name != NULL; name = name->next) 
-                       {
-                               struct ipaddr_str strbuf;
+       for (hash = 0; hash < HASHSIZE; hash++) {
+               list_head = &list[hash];
+               for (list_node = list_head->next; list_node != list_head;
+                        list_node = list_node->next) {
+
+                       entry = list2db(list_node);
 
+                       for (name = entry->names; name != NULL; name = name->next) {
+                               struct ipaddr_str strbuf;
                                OLSR_PRINTF(
                                        6, "%s\t%s%s\t#%s\n",
-                                               olsr_ip_to_string( &strbuf, &name->ip ), name->name, my_suffix,
-                                               olsr_ip_to_string( &strbuf, &entry->originator )
-                               );
+                                       olsr_ip_to_string( &strbuf, &name->ip ), name->name, my_suffix,
+                                       olsr_ip_to_string( &strbuf, &entry->originator )
+                                       );
 
                                fprintf(
                                        hosts, "%s\t%s%s\t# %s\n",
-                                               olsr_ip_to_string( &strbuf, &name->ip ), name->name, my_suffix,
-                                               olsr_ip_to_string( &strbuf, &entry->originator )
-                               );
+                                       olsr_ip_to_string( &strbuf, &name->ip ), name->name, my_suffix,
+                                       olsr_ip_to_string( &strbuf, &entry->originator )
+                                       );
 
 #ifdef MID_ENTRIES
                                // write mid entries
@@ -1071,19 +1099,19 @@ write_hosts_file(void)
 
                                                OLSR_PRINTF(
                                                        6, "%s\t%s%s%s\t# %s (mid #%i)\n",
-                                                               olsr_ip_to_string( &midbuf, &alias->alias ),
-                                                               mid_prefix, name->name, my_suffix,
-                                                               olsr_ip_to_string( &strbuf, &entry->originator ),
-                                                               mid_num
-                                               );
+                                                       olsr_ip_to_string( &midbuf, &alias->alias ),
+                                                       mid_prefix, name->name, my_suffix,
+                                                       olsr_ip_to_string( &strbuf, &entry->originator ),
+                                                       mid_num
+                                                       );
 
                                                fprintf(
                                                        hosts, "%s\t%s%s%s\t# %s (mid #%i)\n",
-                                                               olsr_ip_to_string( &midbuf, &alias->alias ),
-                                                               mid_prefix, name->name, my_suffix,
-                                                               olsr_ip_to_string( &strbuf, &entry->originator ),
-                                                               mid_num
-                                               );
+                                                       olsr_ip_to_string( &midbuf, &alias->alias ),
+                                                       mid_prefix, name->name, my_suffix,
+                                                       olsr_ip_to_string( &strbuf, &entry->originator ),
+                                                       mid_num
+                                                       );
 
                                                alias = alias->next_alias;
                                                mid_num++;
@@ -1117,6 +1145,7 @@ write_services_file(void)
        int hash;
        struct name_entry *name;
        struct db_entry *entry;
+       struct list_node *list_head, *list_node;
        FILE* services_file;
        time_t currtime;
 
@@ -1142,18 +1171,22 @@ write_services_file(void)
        }
        
        // write received services
-       for (hash = 0; hash < HASHSIZE; hash++) 
-       {
-               for(entry = service_list[hash]; entry != NULL; entry = entry->next)
-               {
-                       for (name = entry->names; name != NULL; name = name->next) 
-                       {
+       for (hash = 0; hash < HASHSIZE; hash++) {
+               list_head = &list[hash];
+               for (list_node = list_head->next; list_node != list_head;
+                        list_node = list_node->next) {
+
+                       entry = list2db(list_node);
+
+                       for (name = entry->names; name != NULL; name = name->next) {
                                struct ipaddr_str strbuf;
                                OLSR_PRINTF(6, "%s\t",  name->name);
-                               OLSR_PRINTF(6, "\t#%s\n", olsr_ip_to_string(&strbuf, &entry->originator));
+                               OLSR_PRINTF(6, "\t#%s\n",
+                                                       olsr_ip_to_string(&strbuf, &entry->originator));
 
                                fprintf(services_file, "%s\t", name->name );
-                               fprintf(services_file, "\t#%s\n", olsr_ip_to_string(&strbuf, &entry->originator));
+                               fprintf(services_file, "\t#%s\n",
+                                               olsr_ip_to_string(&strbuf, &entry->originator));
                        }
                }
        }
@@ -1216,6 +1249,7 @@ write_resolv_file(void)
        int hash;
        struct name_entry *name;
        struct db_entry *entry;
+       struct list_node *list_head, *list_node;
        struct rt_entry *route;
        static struct rt_entry *nameserver_routes[NAMESERVER_COUNT+1];
        FILE* resolv;
@@ -1228,12 +1262,14 @@ write_resolv_file(void)
        /* clear the array of 3+1 nameserver routes */
        memset(nameserver_routes, 0, sizeof(nameserver_routes));
 
-       for (hash = 0; hash < HASHSIZE; hash++) 
-       {
-               for(entry = forwarder_list[hash]; entry != NULL; entry = entry->next)
-               {
-                       for (name = entry->names; name != NULL; name = name->next) 
-                       {
+       for (hash = 0; hash < HASHSIZE; hash++) {
+               list_head = &list[hash];
+               for (list_node = list_head->next; list_node != list_head;
+                        list_node = list_node->next) {
+
+                       entry = list2db(list_node);
+
+                       for (name = entry->names; name != NULL; name = name->next) {
 #ifndef NODEBUG
                                struct ipaddr_str strbuf;
 #endif
@@ -1307,6 +1343,25 @@ free_name_entry_list(struct name_entry **list)
        while (*tmp != NULL) {
                to_delete = *tmp;
                *tmp = (*tmp)->next;
+
+               /* flag changes */
+               switch (to_delete->type) {
+               case NAME_HOST:
+                       name_table_changed = OLSR_TRUE;
+                       break;
+               case NAME_FORWARDER:
+                       forwarder_table_changed = OLSR_TRUE;
+                       break;
+               case NAME_SERVICE:
+                       service_table_changed = OLSR_TRUE;
+                       break;
+               case NAME_LATLON:
+                       latlon_table_changed = OLSR_TRUE;
+                       break;
+               default:
+                       break;
+               }
+
                free( to_delete->name );
                to_delete->name = NULL;
                free( to_delete );
@@ -1511,13 +1566,17 @@ lookup_name_latlon(union olsr_ip_addr *ip)
 {
        int hash;
        struct db_entry *entry;
+       struct list_node *list_head, *list_node;
        struct name_entry *name;
-       for (hash = 0; hash < HASHSIZE; hash++) 
-       {
-               for(entry = list[hash]; entry != NULL; entry = entry->next)
-               {
-                       for (name = entry->names; name != NULL; name = name->next) 
-                       {
+
+       for (hash = 0; hash < HASHSIZE; hash++) {
+               list_head = &list[hash];
+               for (list_node = list_head->next; list_node != list_head;
+                        list_node = list_node->next) {
+
+                       entry = list2db(list_node);
+
+                       for (name = entry->names; name != NULL; name = name->next) {
                                if (ipequal(&name->ip, ip)) return name->name;
                        }
                }
index 53679cd..05bb0cd 100644 (file)
@@ -43,6 +43,7 @@
 #include "olsr_types.h"
 #include "interfaces.h"
 #include "olsr_protocol.h"
+#include "lq_list.h"
 
 #include "olsrd_plugin.h"
 #include "nameservice_msg.h"
@@ -51,7 +52,7 @@
 
 #define PLUGIN_NAME    "OLSRD nameservice plugin"
 #define PLUGIN_VERSION "0.3"
-#define PLUGIN_AUTHOR   "Bruno Randolf, Jens Nachtigall, Sven-Ola"
+#define PLUGIN_AUTHOR   "Bruno Randolf, Jens Nachtigall, Sven-Ola Tuecke"
 
 // useful to set for the freifunkfirmware to remove all
 // calls to olsr_printf by the empty statement ";"
@@ -59,8 +60,9 @@
 
 #define MESSAGE_TYPE           130
 #define PARSER_TYPE            MESSAGE_TYPE
-#define EMISSION_INTERVAL      120 /* two minutes */
-#define NAME_VALID_TIME                1800 /* half one hour */
+#define EMISSION_INTERVAL      120 /* seconds */
+#define EMISSION_JITTER         25 /* percent */
+#define NAME_VALID_TIME                1800 /* seconds */
 #define NAMESERVER_COUNT        3
 
 #define NAME_PROTOCOL_VERSION  1
@@ -103,26 +105,28 @@ struct name_entry
 struct db_entry
 {
        union olsr_ip_addr      originator;     /* IP address of the node this entry describes */
-       struct timeval          timer;          /* Validity time */
+        struct timer_entry      *db_timer;      /* Validity time */
        struct name_entry       *names;         /* list of names this originator declares */
-       struct db_entry         *next;          /* linked list */
+        struct list_node        db_list;        /* linked list of db entries per hash container */
 };
 
+/* inline to recast from db_list back to db_entry */
+LISTNODE2STRUCT(list2db, struct db_entry, db_list);
+
+#define OLSR_NAMESVC_DB_JITTER 5 /* percent */
+
 extern struct name_entry *my_names;
-extern struct db_entry* latlon_list[HASHSIZE];
+extern struct list_node latlon_list[HASHSIZE];
 extern float my_lat, my_lon;
 
-/* Timeout function to register with the sceduler */
-void
-olsr_timeout(void);
+void olsr_expire_write_file_timer(void *);
 
 /* Parser function to register with the sceduler */
 void
 olsr_parser(union olsr_message *, struct interface *, union olsr_ip_addr *);
 
-/* Event function to register with the sceduler */
-void
-olsr_event(void *);
+/* callback for periodic timer */
+void olsr_namesvc_gen(void *);
 
 int
 encap_namemsg(struct namemsg *);
@@ -134,16 +138,14 @@ struct name_entry*
 remove_nonvalid_names_from_list(struct name_entry *my_list, int type);
 
 void 
-free_all_list_entries(struct db_entry **this_db_list) ;
-
-void
-timeout_old_names(struct db_entry **this_list, olsr_bool *this_table_changed);
+free_all_list_entries(struct list_node *) ;
 
 void
 decap_namemsg(struct name *from_packet, struct name_entry **to, olsr_bool *this_table_changed );
 
 void
-insert_new_name_in_list(union olsr_ip_addr *originator, struct db_entry **this_list, struct name *from_packet, olsr_bool *this_table_changed, double vtime);
+insert_new_name_in_list(union olsr_ip_addr *, struct list_node *,
+                        struct name *, olsr_bool *, double);
 
 olsr_bool
 allowed_hostname_or_ip_in_service(const char *service_line, const regmatch_t *hostname_or_ip);
@@ -209,3 +211,4 @@ int
 name_init(void);
 
 #endif
+
index 5535431..a63c318 100644 (file)
@@ -42,7 +42,7 @@
 
 #define PLUGIN_NAME    "OLSRD nameservice plugin"
 #define PLUGIN_VERSION "0.3"
-#define PLUGIN_AUTHOR   "Bruno Randolf, Jens Nachtigall, Sven-Ola"
+#define PLUGIN_AUTHOR   "Bruno Randolf, Jens Nachtigall, Sven-Ola Tuecke"
 #define MOD_DESC PLUGIN_NAME " " PLUGIN_VERSION
 #define PLUGIN_INTERFACE_VERSION 5
 
index 5b8a126..9360721 100644 (file)
@@ -125,7 +125,9 @@ int olsrd_plugin_init(void) {
     return 1;
   }
 
-  olsr_register_scheduler_event(&zebra_check, NULL, 1, 0, NULL);
+  olsr_start_timer(1 * MSEC_PER_SEC, 0, OLSR_TIMER_PERIODIC,
+                   &zebra_check, NULL, 0);
+
   return 0;
 }
 
index fc00422..342744f 100644 (file)
@@ -1,4 +1,3 @@
-
 /*
  * Secure OLSR plugin
  * http://www.olsr.org
index 126ccd8..ffa9643 100644 (file)
@@ -107,6 +107,7 @@ MD5_checksum(const olsr_u8_t *data, const olsr_u16_t data_len, olsr_u8_t *hashbu
 #define OS "Undefined"
 #endif
 
+static struct timeval now;
 
 /* Timestamp node */
 struct stamp
@@ -198,7 +199,9 @@ secure_plugin_init(void)
   olsr_preprocessor_add_function(&secure_preprocessor);
   
   /* Register timeout - poll every 2 seconds */
-  olsr_register_scheduler_event(&timeout_timestamps, NULL, 2, 0 , NULL);
+  olsr_start_timer(2 * MSEC_PER_SEC, 0, OLSR_TIMER_PERIODIC,
+                   &timeout_timestamps, NULL, 0);
+
 
   return 1;
 }
@@ -641,7 +644,7 @@ send_challenge(struct interface *olsr_if, const union olsr_ip_addr *new_host)
   /* update validtime - not validated */
   entry->conftime = GET_TIMESTAMP(EXCHANGE_HOLD_TIME * 1000);
 
-  hash = olsr_hashing(new_host);
+  hash = olsr_ip_hashing(new_host);
   
   /* Queue */
   timestamps[hash].next->prev = entry;
@@ -883,7 +886,7 @@ parse_challenge(struct interface *olsr_if, char *in_msg)
       entry = malloc(sizeof(struct stamp));
       memcpy(&entry->addr, &msg->originator, olsr_cnf->ipsize);
 
-      hash = olsr_hashing((union olsr_ip_addr *)&msg->originator);
+      hash = olsr_ip_hashing((union olsr_ip_addr *)&msg->originator);
   
       /* Queue */
       timestamps[hash].next->prev = entry;
@@ -1122,7 +1125,7 @@ lookup_timestamp_entry(const union olsr_ip_addr *adr)
   struct stamp *entry;
   struct ipaddr_str buf;
 
-  hash = olsr_hashing(adr);
+  hash = olsr_ip_hashing(adr);
 
   for(entry = timestamps[hash].next;
       entry != &timestamps[hash];
@@ -1154,6 +1157,8 @@ timeout_timestamps(void* foo __attribute__((unused)))
   struct stamp *entry_to_delete;
   int index;
 
+  /* Update our local timestamp */
+  gettimeofday(&now, NULL);
 
   for(index=0;index<HASHSIZE;index++)
     {
index a679773..d7804a7 100644 (file)
@@ -105,11 +105,12 @@ static void __attribute__((constructor)) banner(void)
 
 int iterLinkTabNext(char *buff, int len)
 {
+  struct list_node *link_node;
 #ifdef USE_FPM
   fpm etx;
 #else
   double etx;
-#endif
+ #endif
 
   if (iterLinkTab == NULL)
     return -1;
@@ -125,14 +126,27 @@ int iterLinkTabNext(char *buff, int len)
            olsr_etx_to_string(iterLinkTab->neigh_link_quality),
            olsr_etx_to_string(etx));
 
-  iterLinkTab = iterLinkTab->next;
+
+  link_node = iterLinkTab->link_list.next;
+  if (link_node != &link_entry_head) {
+    iterLinkTab = list2link(link_node);
+  } else {
+    iterLinkTab = NULL;
+  }
 
   return 0;
 }
 
 void iterLinkTabInit(void)
 {
-  iterLinkTab = get_link_set();
+  struct list_node *link_node;
+
+  link_node = link_entry_head.next;
+  if (link_node != &link_entry_head) {
+    iterLinkTab = list2link(link_node);
+  } else {
+    iterLinkTab = NULL;
+  }
 }
 
 int iterNeighTabNext(char *buff, int len)
@@ -433,7 +447,7 @@ void sendMessage(const char *service, const char *string)
   }
 }
 
-static void serviceFunc(void)
+static void serviceFunc(void *context __attribute__((unused)))
 {
   static int up = 0;
 
@@ -467,7 +481,9 @@ int olsrd_plugin_init(void)
 
   httpInit();
   
-  olsr_register_timeout_function(serviceFunc, OLSR_FALSE);
+  olsr_start_timer(OLSR_TAS_SERVICE_INT, 0, OLSR_TIMER_PERIODIC,
+                   &serviceFunc, NULL, 0);
+
   olsr_parser_add_function(parserFunc, MESSAGE_TYPE, 1);
 
   return 0;
index 6e24ec5..9eeb69b 100644 (file)
@@ -39,6 +39,8 @@
  *
  */
 
+#define OLSR_TAS_SERVICE_INT 100 /* msec */
+
 extern void sendMessage(const char *service, const char *string);
 extern void iterLinkTabInit(void);
 extern int iterLinkTabNext(char *buff, int len);
index 602c7e5..b68177b 100644 (file)
@@ -306,8 +306,7 @@ static void ipc_print_neigh_link(void)
     ipc_sendf("Table: Links\nLocal IP\tremote IP\tHysteresis\tLinkQuality\tlost\ttotal\tNLQ\tETX\n");
 
     /* Link set */
-    link = link_set;
-    while(link)        {
+    OLSR_FOR_ALL_LINK_ENTRIES(link) {
        ipc_sendf( "%s\t%s\t%s\t%s\t%d\t%d\t%s\t%s\t\n",
                    olsr_ip_to_string(&buf1, &link->local_iface_addr),
                    olsr_ip_to_string(&buf2, &link->neighbor_iface_addr),
@@ -317,8 +316,8 @@ static void ipc_print_neigh_link(void)
                    link->total_packets,
                    olsr_etx_to_string(link->neigh_link_quality), 
                    olsr_etx_to_string(olsr_calc_link_etx(link)));
-        link = link->next;
-    }
+    } OLSR_FOR_ALL_LINK_ENTRIES_END(link);
+
     ipc_sendf("\nTable: Neighbors\nIP address\tSYM\tMPR\tMPRS\tWillingness\t2 Hop Neighbors\n");
 
     /* Neighbors */
index efe7e90..9a4784a 100644 (file)
@@ -91,10 +91,16 @@ extern FILE *debug_handle;
   } while (0)
 #endif
 
-/* Provides a timestamp s1 milliseconds in the future
-   according to system ticks returned by times(2) */
+/*
+ * Provides a timestamp s1 milliseconds in the future according
+ * to system ticks returned by times(2)
+*/
 #define GET_TIMESTAMP(s1)      (now_times + ((s1) / olsr_cnf->system_tick_divider))
 
+/* Compute the time in milliseconds when a timestamp will expire. */
+#define TIME_DUE(s1)   ((int)((s1) * olsr_cnf->system_tick_divider) - now_times)
+
+/* Returns TRUE if a timestamp is expired */
 #define TIMED_OUT(s1)  ((int)((s1) - now_times) < 0)
 
 
@@ -132,13 +138,10 @@ extern FILE *debug_handle;
 /*
  * Global olsrd configuragtion
  */
-
 extern struct olsrd_config *olsr_cnf;
 
 /* Timer data */
-extern clock_t now_times;              /* current idea of times(2) reported uptime */
-extern struct timeval now;            /* current idea of time */
-extern struct tm *nowtm;              /* current idea of time (in tm) */
+extern clock_t now_times; /* current idea of times(2) reported uptime */
 
 #if defined WIN32
 extern olsr_bool olsr_win32_end_request;
index 6a9240c..fc0bf3c 100644 (file)
@@ -59,11 +59,6 @@ olsr_init_duplicate_table(void)
 
   OLSR_PRINTF(3, "Initializing duplicatetable - hashsize %d\n", HASHSIZE);
 
-  /* Since the holdingtime is rather large for duplicate
-   * entries the timeoutfunction is only ran every 2 seconds
-   */
-  olsr_register_scheduler_event_dijkstra(&olsr_time_out_duplicate_table, NULL, 2.0, 0.0, NULL);
-  
   for(i = 0; i < HASHSIZE; i++)
     {
       dup_set[i].next = &dup_set[i];
@@ -71,6 +66,29 @@ olsr_init_duplicate_table(void)
     }
 }
 
+/**
+ * Callback for the dup_entry timer.
+ */
+static void
+olsr_expire_dup_entry(void *context)
+{
+  struct dup_entry *dup;
+
+  dup = context;
+  dup->timer = NULL;
+
+#ifdef DEBUG
+#ifndef NODEBUG
+  struct ipaddr_str buf;
+#endif
+  OLSR_PRINTF(5, "DUP TIMEOUT[%s] s: %d\n", 
+              olsr_ip_to_string(&buf, &dup->addr),
+              dup->seqno);
+#endif
+
+  olsr_del_dup_entry(dup);
+}
+
 
 /**
  *Add an entry to the duplicate set. The set is not checked
@@ -98,7 +116,11 @@ olsr_add_dup_entry(const union olsr_ip_addr *originator, const olsr_u16_t seqno)
   /* Seqno */
   new_dup_entry->seqno = seqno;
   /* Set timer */
-  new_dup_entry->timer = GET_TIMESTAMP(DUP_HOLD_TIME*1000);
+  new_dup_entry->timer =
+    olsr_start_timer(DUP_HOLD_TIME * MSEC_PER_SEC, OLSR_DUP_ENTRY_JITTER,
+                     OLSR_TIMER_ONESHOT, &olsr_expire_dup_entry, new_dup_entry,
+                     0);
+
   /* Interfaces */
   new_dup_entry->ifaces = NULL;
   /* Forwarded */
@@ -106,12 +128,7 @@ olsr_add_dup_entry(const union olsr_ip_addr *originator, const olsr_u16_t seqno)
 
   /* Insert into set */
   QUEUE_ELEM(dup_set[hash], new_dup_entry);
-  /*
-  dup_set[hash].next->prev = new_dup_entry;
-  new_dup_entry->next = dup_set[hash].next;
-  dup_set[hash].next = new_dup_entry;
-  new_dup_entry->prev = &dup_set[hash];
-  */
+
   return new_dup_entry;
 }
 
@@ -212,46 +229,15 @@ olsr_del_dup_entry(struct dup_entry *entry)
 
   /* Dequeue */
   DEQUEUE_ELEM(entry);
-  free(entry);
-}
-
 
+  /* Stop timer */
+  if (entry->timer) {
+    olsr_stop_timer(entry->timer);
+  }
 
-void
-olsr_time_out_duplicate_table(void *foo __attribute__((unused)))
-{
-  int i;
-
-  for(i = 0; i < HASHSIZE; i++)
-    {      
-      struct dup_entry *tmp_dup_table;
-      tmp_dup_table = dup_set[i].next;
-
-      while(tmp_dup_table != &dup_set[i])
-       {
-         if(TIMED_OUT(tmp_dup_table->timer))
-           {
-             struct dup_entry *entry_to_delete = tmp_dup_table;
-#ifdef DEBUG
-#ifndef NODEBUG
-              struct ipaddr_str buf;
-#endif
-             OLSR_PRINTF(5, "DUP TIMEOUT[%s] s: %d\n", 
-                         olsr_ip_to_string(&buf, &tmp_dup_table->addr),
-                         tmp_dup_table->seqno);
-#endif
-             tmp_dup_table = tmp_dup_table->next;
-             olsr_del_dup_entry(entry_to_delete);
-           }
-         else
-           {
-             tmp_dup_table = tmp_dup_table->next;
-           }
-       }
-    }
+  free(entry);
 }
 
-
 int
 olsr_update_dup_entry(const union olsr_ip_addr *originator, 
                      const olsr_u16_t seqno, 
@@ -277,10 +263,16 @@ olsr_update_dup_entry(const union olsr_ip_addr *originator,
        }
     }
 
-  if(tmp_dup_table == &dup_set[hash])
+  if(tmp_dup_table == &dup_set[hash]) {
     /* Did not find entry - create it */
     tmp_dup_table = olsr_add_dup_entry(originator, seqno);
-  
+  } else {
+
+    /* Change timer */
+    olsr_change_timer(tmp_dup_table->timer, DUP_HOLD_TIME * MSEC_PER_SEC,
+                      OLSR_DUP_ENTRY_JITTER, OLSR_TIMER_ONESHOT);
+  }  
+
   /* 0 for now */
   tmp_dup_table->forwarded = 0;
   
@@ -290,9 +282,6 @@ olsr_update_dup_entry(const union olsr_ip_addr *originator,
   new_iface->next = tmp_dup_table->ifaces;
   tmp_dup_table->ifaces = new_iface;
   
-  /* Set timer */
-  tmp_dup_table->timer = GET_TIMESTAMP(DUP_HOLD_TIME*1000);
-  
   return 1;
 }
 
@@ -333,7 +322,8 @@ olsr_set_dup_forward(const union olsr_ip_addr *originator,
   tmp_dup_table->forwarded = 1;
   
   /* Set timer */
-  tmp_dup_table->timer = GET_TIMESTAMP(DUP_HOLD_TIME*1000);
+  olsr_change_timer(tmp_dup_table->timer, DUP_HOLD_TIME * MSEC_PER_SEC,
+                    OLSR_DUP_ENTRY_JITTER, OLSR_TIMER_ONESHOT);
   
   return 1;
 }
@@ -362,3 +352,9 @@ olsr_print_duplicate_table(void)
   printf("\n");
 
 }
+
+/*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */
index 60dca28..4c52879 100644 (file)
@@ -50,12 +50,14 @@ struct dup_entry
   union olsr_ip_addr     addr;      /* IP address of originator */
   olsr_u16_t             seqno;     /* Seqno of message */
   olsr_u8_t              forwarded; /* If this message was forwarded or not */
-  clock_t                timer;            /* Holding time */
+  struct timer_entry     *timer; /* Holding time */
   struct dup_iface       *ifaces;   /* Interfaces this message was recieved on */
   struct dup_entry       *next;     /* Next entry */
   struct dup_entry       *prev;     /* Prev entry */
 };
 
+#define OLSR_DUP_ENTRY_JITTER 5 /* percent */
+
 struct dup_iface
 {
   union olsr_ip_addr     addr;      /* Addess of the interface */
@@ -91,3 +93,9 @@ int
 olsr_check_dup_forward(union olsr_ip_addr *, olsr_u16_t);
 
 #endif
+
+/*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */
index 42dea71..bd175ca 100644 (file)
@@ -43,7 +43,7 @@
 
 #include "interfaces.h"
 
-#define STDOUT_PULSE_INT 0.6
+#define STDOUT_PULSE_INT 600 /* msec */
 
 /* Functions */
 
index 009dab0..d04e20e 100644 (file)
  * Hashing function. Creates a key based on
  * an 32-bit address.
  * @param address the address to hash
- * @return the hash(a value in the 0-31 range)
+ * @return the hash(a value in the (0 to HASHMASK-1) range)
  */
-olsr_u32_t olsr_hashing(const union olsr_ip_addr * address)
+olsr_u32_t olsr_ip_hashing(const union olsr_ip_addr * address)
 {
-    olsr_u32_t hash;
-    if(olsr_cnf->ip_version == AF_INET) {
-        /* IPv4 */  
-        const olsr_u8_t * const v4x = (const olsr_u8_t *)&address->v4;
-        hash = v4x[0] ^ v4x[1] ^ v4x[2] ^ v4x[3];
-    } else {
-        /* IPv6 */
-        const char * const tmp = (const char *)&address->v6;
-        hash = ntohl(*tmp);
-    }
-    return hash & HASHMASK;
+  olsr_u32_t hash;
+  if(olsr_cnf->ip_version == AF_INET) {
+    /* IPv4 */  
+    const olsr_u8_t * const v4x = (const olsr_u8_t *)&address->v4;
+    hash = v4x[0] ^ v4x[1] ^ v4x[2] ^ v4x[3];
+  } else {
+    /* IPv6 */
+    const char * const tmp = (const char *)&address->v6;
+    hash = ntohl(*tmp);
+  }
+  return hash & HASHMASK;
 }
 
 /*
  * Local Variables:
- * mode: c
- * style: linux
- * c-basic-offset: 4
- * indent-tabs-mode: nil
+ * c-basic-offset: 2
  * End:
  */
index 2f90d94..0e2b238 100644 (file)
@@ -47,8 +47,6 @@
 
 #include "olsr_types.h"
 
-olsr_u32_t
-olsr_hashing(const union olsr_ip_addr *);
-
+olsr_u32_t olsr_ip_hashing(const union olsr_ip_addr *);
 
 #endif
index f3e0e4a..fd0412b 100644 (file)
@@ -56,11 +56,6 @@ olsr_init_hna_set(void)
 {
   int idx;
 
-  /* Since the holdingtime is assumed to be rather large for 
-   * HNA entries, the timeoutfunction is only ran once every second
-   */
-  olsr_register_scheduler_event_dijkstra(&olsr_time_out_hna_set, NULL, 1, 0, NULL);
-
   for(idx=0;idx<HASHSIZE;idx++)
     {
       hna_set[idx].next = &hna_set[idx];
@@ -105,7 +100,7 @@ struct hna_entry *
 olsr_lookup_hna_gw(const union olsr_ip_addr *gw)
 {
   struct hna_entry *tmp_hna;
-  olsr_u32_t hash = olsr_hashing(gw);
+  olsr_u32_t hash = olsr_ip_hashing(gw);
 
 #if 0
   OLSR_PRINTF(5, "HNA: lookup entry\n");
@@ -149,7 +144,7 @@ olsr_add_hna_entry(const union olsr_ip_addr *addr)
   new_entry->networks.prev = &new_entry->networks;
 
   /* queue */
-  hash = olsr_hashing(addr);
+  hash = olsr_ip_hashing(addr);
   
   hna_set[hash].next->prev = new_entry;
   new_entry->next = hna_set[hash].next;
@@ -183,6 +178,9 @@ olsr_add_hna_net(struct hna_entry *hna_gw, const union olsr_ip_addr *net, olsr_u
   new_net->A_network_addr = *net;
   new_net->prefixlen = prefixlen;
 
+  /* Set backpointer */
+  new_net->hna_gw = hna_gw;
+
   /* Queue */
   hna_gw->networks.next->prev = new_net;
   new_net->next = hna_gw->networks.next;
@@ -200,8 +198,48 @@ olsr_add_hna_net(struct hna_entry *hna_gw, const union olsr_ip_addr *net, olsr_u
   return new_net;
 }
 
+/**
+ * Callback for the hna_net timer.
+ */
+static void
+olsr_expire_hna_net_entry(void *context)
+{
+  struct hna_net *net_to_delete;
+  struct hna_entry *hna_gw;
 
+  net_to_delete = (struct hna_net *)context;
+  net_to_delete->hna_net_timer = NULL; /* be pedandic */
+  hna_gw = net_to_delete->hna_gw;
 
+#ifdef DEBUG
+#ifndef NODEBUG
+  struct ipaddr_str buf;
+#endif
+  OLSR_PRINTF(5, "HNA: timeout %s/%u via hna-gw %s\n", 
+              olsr_ip_to_string(&buf, &net_to_delete->A_network_addr),
+              net_to_delete->prefixlen,
+              &hna_gw->A_gateway_addr);
+#endif
+
+  /*
+   * Delete the rt_path for the entry.
+   */
+  olsr_delete_routing_table(&net_to_delete->A_network_addr,
+                            net_to_delete->prefixlen,
+                            &hna_gw->A_gateway_addr);
+
+
+  /* Delete hna_gw if empty */
+  if (hna_gw->networks.next == &hna_gw->networks) {
+    DEQUEUE_ELEM(hna_gw);
+    free(hna_gw);
+  }
+
+  DEQUEUE_ELEM(net_to_delete);
+  free(net_to_delete);
+
+  changes_hna = OLSR_TRUE;
+}
 
 /**
  * Update a HNA entry. If it does not exist it
@@ -217,95 +255,33 @@ olsr_add_hna_net(struct hna_entry *hna_gw, const union olsr_ip_addr *net, olsr_u
  *@return nada
  */
 void
-olsr_update_hna_entry(const union olsr_ip_addr *gw, const union olsr_ip_addr *net, olsr_u8_t prefixlen, const float vtime)
+olsr_update_hna_entry(const union olsr_ip_addr *gw, const union olsr_ip_addr *net,
+                      olsr_u8_t prefixlen, const float vtime)
 {
   struct hna_entry *gw_entry = olsr_lookup_hna_gw(gw);
   struct hna_net *net_entry;
 
   if (gw_entry == NULL) {
+
     /* Need to add the entry */
     gw_entry = olsr_add_hna_entry(gw);
   }
   net_entry = olsr_lookup_hna_net(&gw_entry->networks, net, prefixlen);
   if (net_entry == NULL)  {
+
     /* Need to add the net */
     net_entry = olsr_add_hna_net(gw_entry, net, prefixlen);
     changes_hna = OLSR_TRUE;
   }
 
-  /* Update holdingtime */
-  net_entry->A_time = GET_TIMESTAMP(vtime*1000);
-}
-
-
-
-
-
-
-/**
- *Function that times out all entrys in the hna set and
- *deletes the timed out ones.
- *
- *@return nada
- */
-void
-olsr_time_out_hna_set(void *foo __attribute__((unused)))
-{
-  int idx;
-
-  for(idx=0;idx<HASHSIZE;idx++)
-    {
-      struct hna_entry *tmp_hna = hna_set[idx].next;
-      /* Check all entrys */
-      while(tmp_hna != &hna_set[idx])
-       {
-         /* Check all networks */
-         struct hna_net *tmp_net = tmp_hna->networks.next;
-
-         while(tmp_net != &tmp_hna->networks)
-           {
-             if(TIMED_OUT(tmp_net->A_time))
-               {
-                 struct hna_net *net_to_delete = tmp_net;
-                 tmp_net = tmp_net->next;
-                 DEQUEUE_ELEM(net_to_delete);
-
-                  /*
-                   * Delete the rt_path for the entry.
-                   */
-                  olsr_delete_routing_table(&net_to_delete->A_network_addr,
-                                            net_to_delete->prefixlen,
-                                            &tmp_hna->A_gateway_addr);
-                 free(net_to_delete);
-                 changes_hna = OLSR_TRUE;
-               }
-             else
-               tmp_net = tmp_net->next;
-           }
-
-         /* Delete gw entry if empty */
-         if(tmp_hna->networks.next == &tmp_hna->networks)
-           {
-             struct hna_entry *hna_to_delete = tmp_hna;
-             tmp_hna = tmp_hna->next;
-
-             /* Dequeue */
-             DEQUEUE_ELEM(hna_to_delete);
-             /* Delete */
-             free(hna_to_delete);
-           }
-         else
-           tmp_hna = tmp_hna->next;
-       }
-    }
-
+  olsr_set_timer(&net_entry->hna_net_timer, vtime * MSEC_PER_SEC,
+                 OLSR_HNA_NET_JITTER, OLSR_TIMER_ONESHOT,
+                 &olsr_expire_hna_net_entry, net_entry, 0);
 }
 
 
-
 /**
- *Function that times out all entrys in the hna set and
- *deletes the timed out ones.
+ * Print all HNA entries.
  *
  *@return nada
  */
index a03bf6b..704956a 100644 (file)
@@ -53,11 +53,14 @@ struct hna_net
 {
   union olsr_ip_addr A_network_addr;
   olsr_u8_t          prefixlen;
-  clock_t            A_time;
+  struct timer_entry *hna_net_timer;
+  struct hna_entry   *hna_gw; /* backpointer to the owning HNA entry */
   struct hna_net     *next;
   struct hna_net     *prev;
 };
 
+#define OLSR_HNA_NET_JITTER 5 /* percent */
+
 struct hna_entry
 {
   union olsr_ip_addr A_gateway_addr;
@@ -95,3 +98,9 @@ void
 olsr_print_hna_set(void);
 
 #endif
+
+/*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */
index 698a149..9f0159b 100644 (file)
@@ -47,6 +47,7 @@
 #include "olsr.h"
 #include "net_olsr.h"
 #include "ipcalc.h"
+#include "scheduler.h"
 
 #ifdef USE_FPM
 #define hscaling ftofpm(olsr_cnf->hysteresis_param.scaling)
@@ -93,8 +94,6 @@ olsr_hyst_calc_instability(float old_quality)
 int
 olsr_process_hysteresis(struct link_entry *entry)
 {
-  clock_t tmp_timer;
-
   //printf("PROCESSING QUALITY: %f\n", entry->L_link_quality);
   if(entry->L_link_quality > hhigh)
     {
@@ -139,12 +138,8 @@ olsr_process_hysteresis(struct link_entry *entry)
        changes_neighborhood = OLSR_TRUE;
 
       /* Timer = min (L_time, current time + NEIGHB_HOLD_TIME) */
-      //tmp_timer = now;
-      //tmp_timer.tv_sec += NEIGHB_HOLD_TIME; /* Takafumi fix */
-      tmp_timer = now_times + get_hold_time_neighbor();
-
-       entry->L_LOST_LINK_time = 
-         entry->time > tmp_timer ? tmp_timer : entry->time;
+      entry->L_LOST_LINK_time = MIN(GET_TIMESTAMP(NEIGHB_HOLD_TIME * MSEC_PER_SEC),
+                                    entry->link_timer->timer_clock);
 
       /* (the link is then considered as lost according to section
         8.5 and this may produce a neighbor loss).
@@ -179,12 +174,11 @@ olsr_update_hysteresis_hello(struct link_entry *entry, double htime)
 #ifndef NODEBUG
   struct ipaddr_str buf;
 #endif
-  OLSR_PRINTF(3, "HYST[%s]: HELLO update vtime %f\n", olsr_ip_to_string(&buf, &entry->neighbor_iface_addr), htime*1.5);
-  /* hello timeout = current time + hint time */
-  /* SET TIMER TO 1.5 TIMES THE INTERVAL */
-  /* Update timer */
+  OLSR_PRINTF(3, "HYST[%s]: HELLO update vtime %f\n",
+              olsr_ip_to_string(&buf, &entry->neighbor_iface_addr), htime*1.5);
 
-  entry->hello_timeout = GET_TIMESTAMP(htime*1500);
+  olsr_set_timer(&entry->link_hello_timer, htime * 1500, OLSR_LINK_HELLO_JITTER,
+                 OLSR_TIMER_PERIODIC, &olsr_expire_link_hello_timer, entry, 0);
 
   return;
 }
index 76e8fcb..606980d 100644 (file)
@@ -71,26 +71,23 @@ ifinit(void)
 {
   struct olsr_if *tmp_if;
 
-
   /* Initial values */
   ifnet = NULL;
 
   OLSR_PRINTF(1, "\n ---- Interface configuration ---- \n\n");
-    /* Run trough all interfaces immedeatly */
-    for(tmp_if = olsr_cnf->interfaces; tmp_if != NULL; tmp_if = tmp_if->next)
-      {
-       if(!tmp_if->host_emul)
-         {
-           if(!olsr_cnf->host_emul) /* XXX: TEMPORARY! */
-             chk_if_up(tmp_if, 1);     
-         }
-       else
-         add_hemu_if(tmp_if);
-      }
+  /* Run trough all interfaces immedeatly */
+  for (tmp_if = olsr_cnf->interfaces; tmp_if != NULL; tmp_if = tmp_if->next) {
+    if (!tmp_if->host_emul) {
+      if (!olsr_cnf->host_emul) /* XXX: TEMPORARY! */
+        chk_if_up(tmp_if, 1);  
+    } else {
+      add_hemu_if(tmp_if);
+    }
+  }
   
-  /* register network interface update function with scheduler */
-  olsr_register_scheduler_event(&check_interface_updates, NULL, 
-                                olsr_cnf->nic_chgs_pollrate, 0, NULL);
+  /* Kick a periodic timer for the network interface update function */
+  olsr_start_timer((unsigned int)olsr_cnf->nic_chgs_pollrate * MSEC_PER_SEC, 5,
+                   OLSR_TIMER_PERIODIC, &check_interface_updates, NULL, 0);
 
   return (ifnet == NULL) ? 0 : 1;
 }
@@ -338,3 +335,9 @@ del_ifchgf(int (*f)(struct interface *, int))
 
   return 0;
 }
+
+/*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */
index ac9fca0..8ed76f1 100644 (file)
@@ -143,6 +143,13 @@ struct interface
   int           is_wireless;                    /* wireless interface or not*/
   char         *int_name;                      /* from kernel if structure */
   olsr_u16_t    olsr_seqnum;                    /* Olsr message seqno */
+
+  /* Periodic message generation timers */
+  struct timer_entry *hello_gen_timer;
+  struct timer_entry *hna_gen_timer;
+  struct timer_entry *mid_gen_timer;
+  struct timer_entry *tc_gen_timer;
+
 #ifdef linux
 /* Struct used to store original redirect/ingress setting */
   struct nic_state
@@ -211,3 +218,9 @@ int
 del_ifchgf(int (*f)(struct interface *, int));
 
 #endif
+
+/*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */
index befb577..a6fb68d 100644 (file)
 #include "ipcalc.h"
 
 
-static clock_t hold_time_neighbor;
+/* head node for all link sets */
+struct list_node link_entry_head;
 
-struct link_entry *link_set;
+olsr_bool link_changes; /* is set if changes occur in MPRS set */ 
 
+void
+signal_link_changes(olsr_bool val) /* XXX ugly */
+{
+  link_changes = val;
+}
 
 static int
 check_link_status(const struct hello_message *message, const struct interface *in_if);
 
-static void
-olsr_time_out_hysteresis(void);
-
-static void olsr_time_out_packet_loss(void);
-
 static struct link_entry *
 add_link_entry(const union olsr_ip_addr *, const union olsr_ip_addr *, const union olsr_ip_addr *, double, double, const struct interface *);
 
-static void
-olsr_time_out_link_set(void);
-
 static int
 get_neighbor_status(const union olsr_ip_addr *);
 
-
-clock_t 
-get_hold_time_neighbor(void)
-{
-  return hold_time_neighbor;
-}
-
-struct link_entry *
-get_link_set(void)
-{
-  return link_set;
-}
-
 void
 olsr_init_link_set(void)
 {
 
-  /* Timers */
-  hold_time_neighbor = (NEIGHB_HOLD_TIME*1000) / olsr_cnf->system_tick_divider;
-
-  olsr_register_timeout_function(&olsr_time_out_link_set, OLSR_TRUE);
-  if(olsr_cnf->use_hysteresis)
-    {
-      olsr_register_timeout_function(&olsr_time_out_hysteresis, OLSR_TRUE);
-    }
-
-  if (olsr_cnf->lq_level > 0)
-    {
-      olsr_register_timeout_function(&olsr_time_out_packet_loss, OLSR_TRUE);
-    }
+  /* Init list head */
+  list_head_init(&link_entry_head);
 }
 
 
-
 /**
  * Get the status of a link. The status is based upon different
  * timeouts in the link entry.
@@ -124,8 +97,9 @@ int
 lookup_link_status(const struct link_entry *entry)
 {
 
-  if(entry == NULL || link_set == NULL)
+  if(entry == NULL || list_is_empty(&link_entry_head)) {
     return UNSPEC_LINK;
+  }
 
   /*
    * Hysteresis
@@ -158,8 +132,9 @@ lookup_link_status(const struct link_entry *entry)
       */
     }
 
-  if(!TIMED_OUT(entry->SYM_time))
+  if (entry->link_sym_timer) {
     return SYM_LINK;
+  }
 
   if(!TIMED_OUT(entry->ASYM_time))
     return ASYM_LINK;
@@ -170,10 +145,6 @@ lookup_link_status(const struct link_entry *entry)
 }
 
 
-
-
-
-
 /**
  *Find the "best" link status to a
  *neighbor
@@ -263,10 +234,9 @@ get_best_link_to_neighbor(const union olsr_ip_addr *remote)
 
   // loop through all links that we have
 
-  for (walker = link_set; walker != NULL; walker = walker->next)
-  {
-    // if this is not a link to the neighour in question, skip
+  OLSR_FOR_ALL_LINK_ENTRIES(walker) {
 
+    /* if this is not a link to the neighour in question, skip */
     if (!ipequal(&walker->neighbor->neighbor_main_addr, main_addr))
       continue;
 
@@ -343,7 +313,7 @@ get_best_link_to_neighbor(const union olsr_ip_addr *remote)
           backup_link = walker;
       }
     }
-  }
+  } OLSR_FOR_ALL_LINK_ENTRIES_END(walker);
 
   // if we haven't found any symmetric links, try to return an
   // asymmetric link
@@ -413,67 +383,155 @@ static void set_loss_link_multiplier(struct link_entry *entry)
   entry->loss_link_multiplier = val;
 }
 
-/**
- *Delete all interface link entries
- *
- *@param interface ip address
+/*
+ * Delete, unlink and free a link entry.
  */
+static void
+olsr_delete_link_entry(struct link_entry *link)
+{
+
+  /* Delete neighbor entry */
+  if (link->neighbor->linkcount == 1) {
+    olsr_delete_neighbor_table(&link->neighbor->neighbor_main_addr);
+  } else {
+    link->neighbor->linkcount--;
+  }
+
+  /* Kill running timers */
+  olsr_stop_timer(link->link_timer);
+  link->link_timer = NULL;
+  olsr_stop_timer(link->link_sym_timer);
+  link->link_sym_timer = NULL;
+  olsr_stop_timer(link->link_hello_timer);
+  link->link_hello_timer = NULL;
+  olsr_stop_timer(link->link_loss_timer);
+  link->link_loss_timer = NULL;
+
+  list_remove(&link->link_list);
+
+  free(link->if_name);
+  free(link);
+
+  changes_neighborhood = OLSR_TRUE;
+}
 
 void
-del_if_link_entries(const union olsr_ip_addr *int_addr)
+olsr_delete_link_entry_by_ip(const union olsr_ip_addr *int_addr)
 {
-  struct link_entry *tmp_link_set, *last_link_entry;
+  struct link_entry *link;
 
-  if(link_set == NULL)
+  if (list_is_empty(&link_entry_head)) {
     return;
+  }
 
-  tmp_link_set = link_set;
-  last_link_entry = NULL;
+  OLSR_FOR_ALL_LINK_ENTRIES(link) {
+    if (ipequal(int_addr, &link->local_iface_addr)) {
+      olsr_delete_link_entry(link);
+    }
+  } OLSR_FOR_ALL_LINK_ENTRIES_END(link);
+}
 
-  while(tmp_link_set)
-    {
+/**
+ * Callback for the link loss timer.
+ */
+static void
+olsr_expire_link_loss_timer(void *context)
+{
+  struct link_entry *link;
 
-      if(ipequal(int_addr, &tmp_link_set->local_iface_addr))
-        {
-          if(last_link_entry != NULL)
-            {
-              last_link_entry->next = tmp_link_set->next;
-
-              /* Delete neighbor entry */
-              if(tmp_link_set->neighbor->linkcount == 1)
-                olsr_delete_neighbor_table(&tmp_link_set->neighbor->neighbor_main_addr);
-              else
-                tmp_link_set->neighbor->linkcount--;
-
-              //olsr_delete_neighbor_if_no_link(&tmp_link_set->neighbor->neighbor_main_addr);
-              changes_neighborhood = OLSR_TRUE;
-
-              free(tmp_link_set);
-              tmp_link_set = last_link_entry;
-            }
-          else
-            {
-              link_set = tmp_link_set->next; /* CHANGED */
+  link = (struct link_entry *)context;
 
-              /* Delete neighbor entry */
-              if(tmp_link_set->neighbor->linkcount == 1)
-                olsr_delete_neighbor_table(&tmp_link_set->neighbor->neighbor_main_addr);
-              else
-                tmp_link_set->neighbor->linkcount--;
+  /* count the lost packet */
+  olsr_update_packet_loss_worker(link, OLSR_TRUE);
 
-              changes_neighborhood = OLSR_TRUE;
+  /*
+   * memorize that we've counted the packet, so that we do not
+   * count it a second time later.
+   */
+  link->loss_missed_hellos++;
 
-              free(tmp_link_set);
-              tmp_link_set = link_set;
-              continue;
-            }
-        }
+  /* next timeout in 1.0 x htime */
+  olsr_change_timer(link->link_loss_timer, link->loss_hello_int * MSEC_PER_SEC,
+                    OLSR_LINK_LOSS_JITTER, OLSR_TIMER_PERIODIC);
+}
 
-      last_link_entry = tmp_link_set;
-      tmp_link_set = tmp_link_set->next;
-    }
+/**
+ * Callback for the link SYM timer.
+ */
+static void
+olsr_expire_link_sym_timer(void *context)
+{
+  struct link_entry *link;
+
+  link = (struct link_entry *)context;
+  link->link_sym_timer = NULL; /* be pedandic */
 
-  return;
+  if (link->prev_status != SYM_LINK) {
+    return;
+  } 
+
+  link->prev_status = lookup_link_status(link);
+  update_neighbor_status(link->neighbor,
+                         get_neighbor_status(&link->neighbor_iface_addr));
+  changes_neighborhood = OLSR_TRUE;
+}
+
+/**
+ * Callback for the link_hello timer.
+ */
+void
+olsr_expire_link_hello_timer(void *context)
+{
+#ifndef NODEBUG
+  struct ipaddr_str buf;
+#endif
+  struct link_entry *link;
+
+  link = (struct link_entry *)context;
+
+  link->L_link_quality = olsr_hyst_calc_instability(link->L_link_quality);
+
+  OLSR_PRINTF(1, "HYST[%s] HELLO timeout %0.3f\n",
+              olsr_ip_to_string(&buf, &link->neighbor_iface_addr),
+              link->L_link_quality);
+
+  /* Update hello_timeout - NO SLACK THIS TIME */
+  olsr_change_timer(link->link_hello_timer, link->last_htime * MSEC_PER_SEC,
+                    OLSR_LINK_JITTER, OLSR_TIMER_PERIODIC);
+
+  /* Update hysteresis values */
+  olsr_process_hysteresis(link);
+         
+  /* update neighbor status */
+  update_neighbor_status(link->neighbor,
+                         get_neighbor_status(&link->neighbor_iface_addr));
+
+  /* Update seqno - not mentioned in the RFC... kind of a hack.. */
+  link->olsr_seqno++;
+}
+
+/**
+ * Callback for the link timer.
+ */
+static void
+olsr_expire_link_entry(void *context)
+{
+  struct link_entry *link;
+
+  link = (struct link_entry *)context;
+  link->link_timer = NULL; /* be pedandic */
+
+  olsr_delete_link_entry(link);
+}
+
+/**
+ * Set the link expiration timer.
+ */
+void
+olsr_set_link_timer(struct link_entry *link, unsigned int rel_timer)
+{
+  olsr_set_timer(&link->link_timer, rel_timer, OLSR_LINK_JITTER,
+                 OLSR_TIMER_ONESHOT, &olsr_expire_link_entry, link, 0);
 }
 
 /**
@@ -502,6 +560,7 @@ add_link_entry(const union olsr_ip_addr *local,
   if (tmp_link_set) {
     return tmp_link_set;
   }
+
   /*
    * if there exists no link tuple with
    * L_neighbor_iface_addr == Source Address
@@ -542,11 +601,8 @@ add_link_entry(const union olsr_ip_addr *local,
   /* L_neighbor_iface_addr = Source Address */
   new_link->neighbor_iface_addr = *remote;
 
-  /* L_SYM_time            = current time - 1 (expired) */
-  new_link->SYM_time = now_times - 1;
-
   /* L_time = current time + validity time */
-  new_link->time = GET_TIMESTAMP(vtime*1000);
+  olsr_set_link_timer(new_link, vtime * MSEC_PER_SEC);
 
   new_link->prev_status = ASYM_LINK;
 
@@ -555,7 +611,7 @@ add_link_entry(const union olsr_ip_addr *local,
     {
       new_link->L_link_pending = 1;
       new_link->L_LOST_LINK_time = GET_TIMESTAMP(vtime*1000);
-      new_link->hello_timeout = GET_TIMESTAMP(htime*1500);
+      olsr_update_hysteresis_hello(new_link, htime);
       new_link->last_htime = htime;
       new_link->olsr_seqno = 0;
       new_link->olsr_seqno_valid = OLSR_FALSE;
@@ -571,7 +627,9 @@ add_link_entry(const union olsr_ip_addr *local,
     {
       new_link->loss_hello_int = htime;
 
-      new_link->loss_timeout = GET_TIMESTAMP(htime * 1500.0);
+      olsr_set_timer(&new_link->link_loss_timer, htime * 1500,
+                     OLSR_LINK_LOSS_JITTER, OLSR_TIMER_PERIODIC,
+                     &olsr_expire_link_loss_timer, new_link, 0);
 
       new_link->loss_seqno = 0;
       new_link->loss_seqno_valid = 0;
@@ -608,9 +666,7 @@ add_link_entry(const union olsr_ip_addr *local,
 #endif
 
   /* Add to queue */
-  new_link->next = link_set;
-  link_set = new_link;
-
+  list_add_before(&link_entry_head, &new_link->link_list);
 
   /*
    * Create the neighbor entry
@@ -631,50 +687,27 @@ add_link_entry(const union olsr_ip_addr *local,
 
   neighbor->linkcount++;
   new_link->neighbor = neighbor;
-  if(!ipequal(remote, remote_main))
-    {
-      /* Add MID alias if not already registered */
-      /* This is kind of sketchy... and not specified
-       * in the RFC. We can only guess a vtime.
-       * We'll go for one that is hopefully long
-       * enough in most cases. 10 seconds
-       */
 
-    /* Erik Tromp - commented out. It is not RFC-compliant. Also, MID aliases
-     * that are not explicitly declared by a node will be removed as soon as
-     * the olsr_prune_aliases(...) function is called.
-     *
-     * OLSR_PRINTF(1, "Adding MID alias main %s ", olsr_ip_to_string(remote_main));
-     * OLSR_PRINTF(1, "-> %s based on HELLO\n\n", olsr_ip_to_string(remote));
-     * insert_mid_alias(remote_main, remote, MID_ALIAS_HACK_VTIME);
-     */
-    }
-
-  return link_set;
+  return new_link;
 }
 
 
 /**
- *Lookup the status of a link.
- *
- *@param int_addr address of the remote interface
+ * Lookup the status of a link.
  *
- *@return 1 of the link is symmertic 0 if not
+ * @param int_addr address of the remote interface
+ * @return 1 of the link is symmertic 0 if not
  */
-
 int
 check_neighbor_link(const union olsr_ip_addr *int_addr)
 {
-  struct link_entry *tmp_link_set;
+  struct link_entry *link;
 
-  tmp_link_set = link_set;
+  OLSR_FOR_ALL_LINK_ENTRIES(link) {
+    if (ipequal(int_addr, &link->neighbor_iface_addr))
+      return lookup_link_status(link);
+  } OLSR_FOR_ALL_LINK_ENTRIES_END(link);
 
-  while(tmp_link_set)
-    {
-      if(ipequal(int_addr, &tmp_link_set->neighbor_iface_addr))
-       return lookup_link_status(tmp_link_set);
-      tmp_link_set = tmp_link_set->next;
-    }
   return UNSPEC_LINK;
 }
 
@@ -689,27 +722,24 @@ check_neighbor_link(const union olsr_ip_addr *int_addr)
  *@return the link entry if found, NULL if not
  */
 struct link_entry *
-lookup_link_entry(const union olsr_ip_addr *remote, const union olsr_ip_addr *remote_main, const struct interface *local)
+lookup_link_entry(const union olsr_ip_addr *remote,
+                  const union olsr_ip_addr *remote_main,
+                  const struct interface *local)
 {
-  struct link_entry *tmp_link_set;
+  struct link_entry *link;
 
-  tmp_link_set = link_set;
+  OLSR_FOR_ALL_LINK_ENTRIES(link) {
+    if(ipequal(remote, &link->neighbor_iface_addr) &&
+       (link->if_name ? !strcmp(link->if_name, local->int_name)
+        : ipequal(&local->ip_addr, &link->local_iface_addr)) &&
 
-  while(tmp_link_set)
-    {
-      if(ipequal(remote, &tmp_link_set->neighbor_iface_addr) &&
-        (tmp_link_set->if_name
-          ? !strcmp(tmp_link_set->if_name, local->int_name)
-          : ipequal(&local->ip_addr, &tmp_link_set->local_iface_addr)
-          ) &&
-         /* check the remote-main address only if there is one given */
-         (remote_main == NULL || ipequal(remote_main, &tmp_link_set->neighbor->neighbor_main_addr))
-         )
-       return tmp_link_set;
-      tmp_link_set = tmp_link_set->next;
+       /* check the remote-main address only if there is one given */
+       (!remote_main || ipequal(remote_main, &link->neighbor->neighbor_main_addr))) {
+      return link;
     }
-  return NULL;
+  } OLSR_FOR_ALL_LINK_ENTRIES_END(link);
 
+  return NULL;
 }
 
 
@@ -755,26 +785,27 @@ update_link_entry(const union olsr_ip_addr *local,
   switch(entry->prev_status)
     {
     case(LOST_LINK):
-      /* L_SYM_time = current time - 1 (i.e., expired) */
-      entry->SYM_time = now_times - 1;
-
+      olsr_stop_timer(entry->link_sym_timer);
+      entry->link_sym_timer = NULL;
       break;
     case(SYM_LINK):
     case(ASYM_LINK):
       /* L_SYM_time = current time + validity time */
-      //printf("updating SYM time for %s\n", olsr_ip_to_string(remote));
-      entry->SYM_time = GET_TIMESTAMP(message->vtime*1000);
+      olsr_set_timer(&entry->link_sym_timer, message->vtime * MSEC_PER_SEC,
+                     OLSR_LINK_SYM_JITTER, OLSR_TIMER_ONESHOT,
+                     &olsr_expire_link_sym_timer, entry, 0);
 
       /* L_time = L_SYM_time + NEIGHB_HOLD_TIME */
-      entry->time = entry->SYM_time + hold_time_neighbor;
-
+      olsr_set_link_timer(entry, (message->vtime + NEIGHB_HOLD_TIME) *
+                          MSEC_PER_SEC);
       break;
     default:;
     }
 
   /* L_time = max(L_time, L_ASYM_time) */
-  if(entry->time < entry->ASYM_time)
-    entry->time = entry->ASYM_time;
+  if(entry->link_timer && (entry->link_timer->timer_clock < entry->ASYM_time)) {
+    olsr_set_link_timer(entry, TIME_DUE(entry->ASYM_time));
+  }
 
 
   /*
@@ -809,29 +840,22 @@ int
 replace_neighbor_link_set(const struct neighbor_entry *old,
                          struct neighbor_entry *new)
 {
-  struct link_entry *tmp_link_set;
-  int retval;
+  struct link_entry *link;
+  int retval = 0;
 
-  retval = 0;
-
-  if(link_set == NULL)
+  if (list_is_empty(&link_entry_head)) {
     return retval;
+  }
       
-  tmp_link_set = link_set;
-
-  while(tmp_link_set)
-    {
+  OLSR_FOR_ALL_LINK_ENTRIES(link) {
 
-      if(tmp_link_set->neighbor == old)
-       {
-         tmp_link_set->neighbor = new;
-         retval++;
-       }
-      tmp_link_set = tmp_link_set->next;
+    if (link->neighbor == old) {
+      link->neighbor = new;
+      retval++;
     }
+  } OLSR_FOR_ALL_LINK_ENTRIES_END(link);
 
   return retval;
-
 }
 
 
@@ -871,133 +895,6 @@ check_link_status(const struct hello_message *message, const struct interface *i
   return ret;
 }
 
-
-/**
- *Time out the link set. In other words, the link
- *set is traversed and all non-valid entries are
- *deleted.
- *
- */
-static void
-olsr_time_out_link_set(void)
-{
-
-  struct link_entry *tmp_link_set, *last_link_entry;
-
-  if(link_set == NULL)
-    return;
-      
-  tmp_link_set = link_set;
-  last_link_entry = NULL;
-
-  while(tmp_link_set)
-    {
-
-      if(TIMED_OUT(tmp_link_set->time))
-       {
-         if(last_link_entry != NULL)
-           {
-             last_link_entry->next = tmp_link_set->next;
-
-             /* Delete neighbor entry */
-             if(tmp_link_set->neighbor->linkcount == 1)
-               olsr_delete_neighbor_table(&tmp_link_set->neighbor->neighbor_main_addr);
-             else
-               tmp_link_set->neighbor->linkcount--;
-
-             //olsr_delete_neighbor_if_no_link(&tmp_link_set->neighbor->neighbor_main_addr);
-             changes_neighborhood = OLSR_TRUE;
-             free(tmp_link_set->if_name);
-             free(tmp_link_set);
-             tmp_link_set = last_link_entry;
-           }
-         else
-           {
-             link_set = tmp_link_set->next; /* CHANGED */
-
-             /* Delete neighbor entry */
-             if(tmp_link_set->neighbor->linkcount == 1)
-               olsr_delete_neighbor_table(&tmp_link_set->neighbor->neighbor_main_addr);
-             else
-               tmp_link_set->neighbor->linkcount--;
-
-             changes_neighborhood = OLSR_TRUE;
-
-             free(tmp_link_set->if_name);
-             free(tmp_link_set);
-             tmp_link_set = link_set;
-             continue;
-           }       
-       }
-      else if((tmp_link_set->prev_status == SYM_LINK) &&
-             TIMED_OUT(tmp_link_set->SYM_time))
-       {
-         tmp_link_set->prev_status = lookup_link_status(tmp_link_set);
-         update_neighbor_status(tmp_link_set->neighbor, 
-                                get_neighbor_status(&tmp_link_set->neighbor_iface_addr));
-         changes_neighborhood = OLSR_TRUE;
-       }
-      
-      last_link_entry = tmp_link_set;
-      tmp_link_set = tmp_link_set->next;
-    }
-
-  return;
-}
-
-
-
-
-/**
- *Updates links that we have not received
- *HELLO from in expected time according to 
- *hysteresis.
- *
- *@return nada
- */
-static void
-olsr_time_out_hysteresis(void)
-{
-  struct link_entry *tmp_link_set;
-
-  if(link_set == NULL)
-    return;
-
-  tmp_link_set = link_set;
-
-  while(tmp_link_set)
-    {
-      if(TIMED_OUT(tmp_link_set->hello_timeout))
-       {
-#ifndef NODEBUG
-          struct ipaddr_str buf;
-#endif
-         tmp_link_set->L_link_quality = olsr_hyst_calc_instability(tmp_link_set->L_link_quality);
-         OLSR_PRINTF(1, "HYST[%s] HELLO timeout %s\n",
-                      olsr_ip_to_string(&buf, &tmp_link_set->neighbor_iface_addr),
-                      olsr_etx_to_string(tmp_link_set->L_link_quality));
-         /* Update hello_timeout - NO SLACK THIS TIME */
-         tmp_link_set->hello_timeout = GET_TIMESTAMP(tmp_link_set->last_htime*1000);
-         /* Recalculate status */
-         /* Update hysteresis values */
-         olsr_process_hysteresis(tmp_link_set);
-         
-         /* update neighbor status */
-
-
-         /* Update neighbor */
-         update_neighbor_status(tmp_link_set->neighbor, 
-                                get_neighbor_status(&tmp_link_set->neighbor_iface_addr));
-
-         /* Update seqno - not mentioned in the RFC... kind of a hack.. */
-         tmp_link_set->olsr_seqno++;
-       }
-      tmp_link_set = tmp_link_set->next;
-    }
-
-  return;
-}
-
 void olsr_print_link_set(void)
 {
 #ifndef NODEBUG
@@ -1043,7 +940,7 @@ void olsr_print_link_set(void)
 #endif
 }
 
-static void update_packet_loss_worker(struct link_entry *entry, int lost)
+void olsr_update_packet_loss_worker(struct link_entry *entry, olsr_bool lost)
 {
   unsigned char mask = 1 << (entry->loss_index & 7);
   const int idx = entry->loss_index >> 3;
@@ -1053,7 +950,7 @@ static void update_packet_loss_worker(struct link_entry *entry, int lost)
   double rel_lq, saved_lq;
 #endif
 
-  if (lost == 0)
+  if (!lost)
     {
       // packet not lost
 
@@ -1174,7 +1071,8 @@ void olsr_update_packet_loss_hello_int(struct link_entry *entry,
   entry->loss_hello_int = loss_hello_int;
 }
 
-void olsr_update_packet_loss(const union olsr_ip_addr *rem, const struct interface *loc,
+void olsr_update_packet_loss(const union olsr_ip_addr *rem,
+                             const struct interface *loc,
                              olsr_u16_t seqno)
 {
   struct link_entry *entry;
@@ -1203,7 +1101,7 @@ void olsr_update_packet_loss(const union olsr_ip_addr *rem, const struct interfa
           // have we already considered all lost LQ HELLO messages?
 
           if (entry->loss_missed_hellos == 0)
-            update_packet_loss_worker(entry, 1);
+            olsr_update_packet_loss_worker(entry, OLSR_TRUE);
 
           // if not, then decrement the number of lost LQ HELLOs
 
@@ -1217,7 +1115,7 @@ void olsr_update_packet_loss(const union olsr_ip_addr *rem, const struct interfa
   // we have received a packet, otherwise this function would not
   // have been called
 
-  update_packet_loss_worker(entry, 0);
+  olsr_update_packet_loss_worker(entry, OLSR_FALSE);
 
   // (re-)initialize
 
@@ -1230,47 +1128,19 @@ void olsr_update_packet_loss(const union olsr_ip_addr *rem, const struct interfa
 
   // timeout for the first lost packet is 1.5 x htime
 
-  entry->loss_timeout = GET_TIMESTAMP(entry->loss_hello_int * 1500.0);
-}
-
-static void olsr_time_out_packet_loss(void)
-{
-  struct link_entry *walker;
-
-  // loop through all links
-
-  for (walker = link_set; walker != NULL; walker = walker->next)
-    {
-      // find a link that has not seen any packets for a very long
-      // time (first time: 1.5 x htime, subsequently: 1.0 x htime)
-
-      if (!TIMED_OUT(walker->loss_timeout))
-        continue;
-      
-      // count the lost packet
-
-      update_packet_loss_worker(walker, 1);
-
-      // memorize that we've counted the packet, so that we do not
-      // count it a second time later
-
-      walker->loss_missed_hellos++;
-
-      // next timeout in 1.0 x htime
-
-      walker->loss_timeout = GET_TIMESTAMP(walker->loss_hello_int * 1000.0);
-    }
+  olsr_set_timer(&entry->link_loss_timer, entry->loss_hello_int * 1500,
+                 OLSR_LINK_LOSS_JITTER, OLSR_TIMER_PERIODIC,
+                 &olsr_expire_link_loss_timer, entry, 0);
 }
 
 void olsr_update_dijkstra_link_qualities(void)
 {
   struct link_entry *walker;
 
-  for (walker = link_set; walker != NULL; walker = walker->next)
-  {
+  OLSR_FOR_ALL_LINK_ENTRIES(walker) {
     walker->loss_link_quality2 = walker->loss_link_quality;
     walker->neigh_link_quality2 = walker->neigh_link_quality;
-  }
+  } OLSR_FOR_ALL_LINK_ENTRIES_END(walker);
 }
 
 #ifdef USE_FPM
@@ -1290,3 +1160,9 @@ olsr_calc_link_etx(const struct link_entry *link)
              : 1.0 / (link->loss_link_quality * link->neigh_link_quality);
 #endif
 }
+
+/*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */
index d7034ac..708dd25 100644 (file)
@@ -47,6 +47,7 @@
 #define _LINK_SET_H
 
 #include "packet.h"
+#include "lq_list.h"
 
 #define MID_ALIAS_HACK_VTIME  10.0
 
@@ -56,9 +57,9 @@ struct link_entry
   union olsr_ip_addr neighbor_iface_addr;
   const struct interface *inter;
   char *if_name;
-  clock_t SYM_time;
+  struct timer_entry *link_timer;
+  struct timer_entry *link_sym_timer;
   clock_t ASYM_time;
-  clock_t time;
   unsigned int vtime;
   struct neighbor_entry *neighbor;
   olsr_u8_t prev_status;
@@ -73,7 +74,7 @@ struct link_entry
 #endif
   int L_link_pending;
   clock_t L_LOST_LINK_time;
-  clock_t hello_timeout; /* When we should receive a new HELLO */
+  struct timer_entry *link_hello_timer; /* When we should receive a new HELLO */
   double last_htime;
   olsr_bool olsr_seqno_valid;
   olsr_u16_t olsr_seqno;
@@ -86,7 +87,7 @@ struct link_entry
   int loss_missed_hellos;
 
   double loss_hello_int;
-  clock_t loss_timeout;
+  struct timer_entry *link_loss_timer;
 
   unsigned int lost_packets;
   unsigned int total_packets;
@@ -117,26 +118,41 @@ struct link_entry
   double saved_neigh_link_quality;
 #endif
 
-  struct link_entry *next;
+  struct list_node link_list; /* double linked list of all link entries */
 };
 
-
-extern struct link_entry *link_set;
-
+/* inline to recast from link_list back to link_entry */
+LISTNODE2STRUCT(list2link, struct link_entry, link_list);
+
+#define OLSR_LINK_JITTER       5 /* percent */
+#define OLSR_LINK_HELLO_JITTER 0 /* percent jitter */
+#define OLSR_LINK_SYM_JITTER   0 /* percent jitter */
+#define OLSR_LINK_LOSS_JITTER  0 /* percent jitter */
+
+/* deletion safe macro for link entry traversal */
+#define OLSR_FOR_ALL_LINK_ENTRIES(link) \
+{ \
+  struct list_node *link_head_node, *link_node, *next_link_node; \
+  link_head_node = &link_entry_head; \
+  for (link_node = link_head_node->next; \
+    link_node != link_head_node; link_node = next_link_node) { \
+    next_link_node = link_node->next; \
+    link = list2link(link_node);
+#define OLSR_FOR_ALL_LINK_ENTRIES_END(link) }}
+
+/* Externals */
+extern struct list_node link_entry_head;
+extern olsr_bool link_changes;
 
 /* Function prototypes */
 
-struct link_entry *
-get_link_set(void);
-
-clock_t 
-get_hold_time_neighbor(void);
+void olsr_set_link_timer(struct link_entry *, unsigned int );
+void olsr_init_link_set(void);
+void olsr_delete_link_entry_by_ip(const union olsr_ip_addr *);
+void olsr_expire_link_hello_timer(void *);
+void olsr_update_packet_loss_worker(struct link_entry *, olsr_bool);
+void signal_link_changes(olsr_bool); /* XXX ugly */
 
-void
-olsr_init_link_set(void);
-
-void
-del_if_link_entries(const union olsr_ip_addr *);
 
 struct link_entry *
 get_best_link_to_neighbor(const union olsr_ip_addr *);
index 75cf408..2035d2d 100644 (file)
@@ -149,6 +149,8 @@ apm_printinfo(struct olsr_apm_info *ainfo)
              ainfo->ac_line_status,
              ainfo->battery_percentage,
              ainfo->battery_time_left);
+
+  ainfo = NULL; /* squelch compiler warnings */
 }
 
 
index 8659bb2..ddc95b1 100644 (file)
@@ -71,7 +71,7 @@ add_spy_node(union olsr_ip_addr *, char *);
 #define        MAXIPLEN        60
 #define        MAXICMPLEN      76
 
-float poll_int = 0.2;
+float poll_int = 200; /* msec */
 
 int
 iw_get_range_info(char *, struct iw_range *);
@@ -100,7 +100,7 @@ init_link_layer_notification()
        clear_spy_list(ifd->int_name);
     }
 
-  olsr_register_scheduler_event(&poll_link_layer, NULL, poll_int, 0, NULL);
+  olsr_start_timer(poll_int, 0, OLSR_TIMER_PERIODIC, &poll_link_layer, NULL, 0);
 
   return;
 }
index ac0c921..fbcb129 100644 (file)
@@ -42,6 +42,8 @@
 #ifndef _LQ_LIST_H
 #define _LQ_LIST_H
 
+#include "stddef.h"
+
 struct list_node
 {
   struct list_node *next;
@@ -59,5 +61,18 @@ void list_add_after(struct list_node *, struct list_node *);
 
 void list_remove(struct list_node *);
 
+/*
+ * Macro to define an inline function to map from a list_node offset back to the
+ * base of the datastructure. This saves you from populating the data field.
+ */
+#define LISTNODE2STRUCT(funcname, structname, listnodename) \
+static inline structname * funcname (struct list_node *ptr)\
+{\
+  if (ptr) {\
+    return((structname *) (((olsr_u8_t *) ptr) - offsetof(structname, listnodename))); \
+  } \
+  return(NULL); \
+}
+
 #endif
 
index 3e39300..2e84917 100644 (file)
@@ -86,50 +86,51 @@ create_lq_hello(struct lq_hello_message *lq_hello, struct interface *outif)
   
   // loop through the link set
 
-  for (walker = get_link_set(); walker != NULL; walker = walker->next)
-    {
-      // allocate a neighbour entry
-      struct lq_hello_neighbor *neigh = olsr_malloc(sizeof (struct lq_hello_neighbor), "Build LQ_HELLO");
+  OLSR_FOR_ALL_LINK_ENTRIES(walker) {
+
+    // allocate a neighbour entry
+    struct lq_hello_neighbor *neigh = olsr_malloc(sizeof (struct lq_hello_neighbor), "Build LQ_HELLO");
 
-      // a) this neighbor interface IS NOT visible via the output interface
-      if(!ipequal(&walker->local_iface_addr, &outif->ip_addr))
-        neigh->link_type = UNSPEC_LINK;
+    // a) this neighbor interface IS NOT visible via the output interface
+    if(!ipequal(&walker->local_iface_addr, &outif->ip_addr))
+      neigh->link_type = UNSPEC_LINK;
       
-      // b) this neighbor interface IS visible via the output interface
+    // b) this neighbor interface IS visible via the output interface
 
-      else
-        neigh->link_type = lookup_link_status(walker);
+    else
+      neigh->link_type = lookup_link_status(walker);
 
-      // set the entry's link quality
+    // set the entry's link quality
 
-      neigh->link_quality = walker->loss_link_quality;
-      neigh->neigh_link_quality = walker->neigh_link_quality;
+    neigh->link_quality = walker->loss_link_quality;
+    neigh->neigh_link_quality = walker->neigh_link_quality;
 
-      // set the entry's neighbour type
+    // set the entry's neighbour type
 
-      if(walker->neighbor->is_mpr)
-        neigh->neigh_type = MPR_NEIGH;
+    if(walker->neighbor->is_mpr)
+      neigh->neigh_type = MPR_NEIGH;
 
-      else if (walker->neighbor->status == SYM)
-        neigh->neigh_type = SYM_NEIGH;
+    else if (walker->neighbor->status == SYM)
+      neigh->neigh_type = SYM_NEIGH;
 
-      else if (walker->neighbor->status == NOT_SYM)
-        neigh->neigh_type = NOT_NEIGH;
+    else if (walker->neighbor->status == NOT_SYM)
+      neigh->neigh_type = NOT_NEIGH;
         
-      else {
-        OLSR_PRINTF(0, "Error: neigh_type undefined");
-        neigh->neigh_type = NOT_NEIGH;
-      }
+    else {
+      OLSR_PRINTF(0, "Error: neigh_type undefined");
+      neigh->neigh_type = NOT_NEIGH;
+    }
   
-      // set the entry's neighbour interface address
+    // set the entry's neighbour interface address
 
-      neigh->addr = walker->neighbor_iface_addr;
+    neigh->addr = walker->neighbor_iface_addr;
       
-      // queue the neighbour entry
+    // queue the neighbour entry
 
-      neigh->next = lq_hello->neigh;
-      lq_hello->neigh = neigh;
-    }
+    neigh->next = lq_hello->neigh;
+    lq_hello->neigh = neigh;
+
+  } OLSR_FOR_ALL_LINK_ENTRIES_END(walker);
 }
 
 static void
@@ -661,3 +662,9 @@ olsr_output_lq_tc(void *para)
     set_buffer_timer(outif);
   }
 }
+
+/*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */
index 155778a..5417f0a 100644 (file)
@@ -65,6 +65,8 @@
 #include "lq_route.h"
 #include "net_olsr.h"
 
+struct timer_entry *spf_backoff_timer = NULL;
+
 /*
  * avl_comp_etx
  *
@@ -314,9 +316,21 @@ olsr_spf_run_full (struct avl_tree *cand_tree, struct list_node *path_list,
   }
 }
 
+/**
+ * Callback for the SPF backoff timer.
+ */
+static void
+olsr_expire_spf_backoff(void *context __attribute__((unused)))
+{
+  spf_backoff_timer = NULL;
+}
+
 void
-olsr_calculate_routing_table (void)
+olsr_calculate_routing_table (void *context __attribute__((unused)))
 {
+#ifdef SPF_PROFILING
+  struct timeval t1, t2, t3, t4, t5, spf_init, spf_run, route, kernel, total;
+#endif
   struct avl_tree cand_tree;
   struct avl_node *rtp_tree_node;
   struct list_node path_list; /* head of the path_list */
@@ -327,9 +341,16 @@ olsr_calculate_routing_table (void)
   struct neighbor_entry *neigh;
   struct link_entry *link;
 
-#ifdef SPF_PROFILING
-  struct timeval t1, t2, t3, t4, t5, spf_init, spf_run, route, kernel, total;
+  /* We are done if our backoff timer is running */
+  if (!spf_backoff_timer) {
+    spf_backoff_timer = 
+      olsr_start_timer(1000, 5, OLSR_TIMER_ONESHOT, &olsr_expire_spf_backoff,
+                       NULL, 0);
+  } else {
+    return;
+  }
 
+#ifdef SPF_PROFILING
   gettimeofday(&t1, NULL);
 #endif
 
index 1ce225b..8aaba2d 100644 (file)
@@ -41,6 +41,6 @@
 #ifndef _LQ_ROUTE_H
 #define _LQ_ROUTE_H
 
-void olsr_calculate_routing_table(void);
+void olsr_calculate_routing_table(void *);
 
 #endif
index b0019aa..cc3f56f 100644 (file)
@@ -154,10 +154,6 @@ main(int argc, char *argv[])
 
   /* Grab initial timestamp */
   now_times = times(&tms_buf);
-  do {
-    time_t t = now.tv_sec;
-    nowtm = localtime(&t);
-  } while (nowtm == NULL);
     
   printf("\n *** %s ***\n Build date: %s on %s\n http://www.olsr.org\n\n", 
         olsrd_version, 
@@ -233,6 +229,9 @@ main(int argc, char *argv[])
   olsr_cnf->system_tick_divider = 1;
 #endif
 
+  /* Initialize timers */
+  olsr_init_timers();
+
   /*
    * Process olsrd options.
    */
@@ -357,12 +356,11 @@ main(int argc, char *argv[])
   /* Print heartbeat to stdout */
 
 #if !defined WINCE
-  if(olsr_cnf->debug_level > 0 && isatty(STDOUT_FILENO))
-    olsr_register_scheduler_event(&generate_stdout_pulse, NULL, STDOUT_PULSE_INT, 0, NULL);
+  if (olsr_cnf->debug_level > 0 && isatty(STDOUT_FILENO)) {
+    olsr_start_timer(STDOUT_PULSE_INT, 0, OLSR_TIMER_PERIODIC,
+                     &generate_stdout_pulse, NULL, 0);
+  }
 #endif
-  
-  gettimeofday(&now, NULL);
-
 
   /* Initialize the IPC socket */
 
@@ -411,11 +409,10 @@ main(int argc, char *argv[])
   signal(SIGPIPE, SIG_IGN);
 #endif
 
-  /* Register socket poll event */
-  olsr_register_timeout_function(&poll_sockets, OLSR_FALSE);
+  link_changes = OLSR_FALSE;
 
   /* Starting scheduler */
-  scheduler();
+  olsr_scheduler();
 
   /* Like we're ever going to reach this ;-) */
   return 1;
@@ -885,3 +882,9 @@ olsr_process_arguments(int argc, char *argv[],
     }
   return 0;
 }
+
+/*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */
index 403d20f..de4adc3 100644 (file)
@@ -68,11 +68,6 @@ olsr_init_mid_set(void)
 
   OLSR_PRINTF(5, "MID: init\n");
 
-  /* Since the holdingtime is assumed to be rather large for 
-   * MID entries, the timeoutfunction is only ran once every second
-   */
-  olsr_register_scheduler_event_dijkstra(&olsr_time_out_mid_set, NULL, 1, 0, NULL);
-
   for(idx=0;idx<HASHSIZE;idx++)
     {
       mid_set[idx].next = &mid_set[idx];
@@ -85,6 +80,43 @@ olsr_init_mid_set(void)
   return 1;
 }
 
+/**
+ * Wrapper for the timer callback.
+ */
+static void
+olsr_expire_mid_entry(void *context)
+{
+#if !defined(NODEBUG) && defined(DEBUG)
+  struct ipaddr_str buf;
+#endif
+  struct mid_entry *mid;
+
+  mid = (struct mid_entry *)context;
+  mid->mid_timer = NULL;
+
+#ifdef DEBUG
+  OLSR_PRINTF(1, "MID info for %s timed out.. deleting it\n",
+              olsr_ip_to_string(&buf, &mid->main_addr));
+#endif
+
+  mid_delete_node(mid);
+}
+
+
+/**
+ * Set the mid set expiration timer.
+ *
+ * all timer setting shall be done using this function.
+ * The timer param is a relative timer expressed in milliseconds.
+ */
+static void
+olsr_set_mid_timer(struct mid_entry *mid, unsigned int rel_timer)
+{
+
+  olsr_set_timer(&mid->mid_timer, rel_timer, OLSR_MID_JITTER,
+                 OLSR_TIMER_ONESHOT, &olsr_expire_mid_entry, mid, 0);
+}
+
 
 /**
  *Insert a new interface alias to the interface association set.
@@ -105,8 +137,8 @@ insert_mid_tuple(union olsr_ip_addr *m_addr, struct mid_address *alias, float vt
   olsr_u32_t hash, alias_hash;
   union olsr_ip_addr *registered_m_addr;
 
-  hash = olsr_hashing(m_addr);
-  alias_hash = olsr_hashing(&alias->alias);
+  hash = olsr_ip_hashing(m_addr);
+  alias_hash = olsr_ip_hashing(&alias->alias);
 
   /* Check for registered entry */
   for(tmp = mid_set[hash].next;
@@ -139,7 +171,7 @@ insert_mid_tuple(union olsr_ip_addr *m_addr, struct mid_address *alias, float vt
       alias->main_entry = tmp;
       QUEUE_ELEM(reverse_mid_set[alias_hash], alias);
       alias->next_alias = tmp_adr;
-      tmp->ass_timer = GET_TIMESTAMP(vtime*1000);
+      olsr_set_mid_timer(tmp, vtime * MSEC_PER_SEC);
     }
   else
     {
@@ -151,7 +183,7 @@ insert_mid_tuple(union olsr_ip_addr *m_addr, struct mid_address *alias, float vt
       alias->main_entry = tmp;
       QUEUE_ELEM(reverse_mid_set[alias_hash], alias);
       tmp->main_addr = *m_addr;
-      tmp->ass_timer = GET_TIMESTAMP(vtime*1000);
+      olsr_set_mid_timer(tmp, vtime * MSEC_PER_SEC);
       /* Queue */
       QUEUE_ELEM(mid_set[hash], tmp);
     }
@@ -294,7 +326,7 @@ mid_lookup_main_addr(const union olsr_ip_addr *adr)
   olsr_u32_t hash;
   struct mid_address *tmp_list;
 
-  hash = olsr_hashing(adr);
+  hash = olsr_ip_hashing(adr);
   /*Traverse MID list*/
   for(tmp_list = reverse_mid_set[hash].next; 
       tmp_list != &reverse_mid_set[hash];
@@ -320,7 +352,7 @@ mid_lookup_entry_bymain(const union olsr_ip_addr *adr)
 
   //OLSR_PRINTF(1, "MID: lookup entry...");
 
-  hash = olsr_hashing(adr);
+  hash = olsr_ip_hashing(adr);
 
   /* Check all registered nodes...*/
   for(tmp_list = mid_set[hash].next;
@@ -365,7 +397,7 @@ olsr_update_mid_table(const union olsr_ip_addr *adr, float vtime)
   struct mid_entry *tmp_list = mid_set;
 
   OLSR_PRINTF(3, "MID: update %s\n", olsr_ip_to_string(&buf, adr));
-  hash = olsr_hashing(adr);
+  hash = olsr_ip_hashing(adr);
 
   /* Check all registered nodes...*/
   for(tmp_list = mid_set[hash].next;
@@ -376,7 +408,7 @@ olsr_update_mid_table(const union olsr_ip_addr *adr, float vtime)
       if(ipequal(&tmp_list->main_addr, adr))
        {
          // printf("MID: Updating timer for node %s\n", olsr_ip_to_string(&buf, &tmp_list->main_addr));
-         tmp_list->ass_timer = GET_TIMESTAMP(vtime*1000);
+          olsr_set_mid_timer(tmp_list, vtime * MSEC_PER_SEC);
 
          return 1;
        }
@@ -402,7 +434,7 @@ olsr_prune_aliases(const union olsr_ip_addr *m_addr, struct mid_alias *declared_
   struct mid_address *previous_alias;
   struct mid_alias *save_declared_aliases = declared_aliases;
 
-  hash = olsr_hashing(m_addr);
+  hash = olsr_ip_hashing(m_addr);
 
   /* Check for registered entry */
   for(entry = mid_set[hash].next;
@@ -479,47 +511,6 @@ olsr_prune_aliases(const union olsr_ip_addr *m_addr, struct mid_alias *declared_
 }
 
 
-
-/**
- *Find timed out entries and delete them
- *
- *@return nada
- */
-void
-olsr_time_out_mid_set(void *foo __attribute__((unused)))
-{
-  int idx;
-
-  for(idx=0;idx<HASHSIZE;idx++)
-    {
-      struct mid_entry *tmp_list = mid_set[idx].next;
-      /*Traverse MID list*/
-      while(tmp_list != &mid_set[idx])
-       {
-         /*Check if the entry is timed out*/
-         if(TIMED_OUT(tmp_list->ass_timer))
-           {
-#if !defined(NODEBUG) && defined(DEBUG)
-              struct ipaddr_str buf;
-#endif
-             struct mid_entry *entry_to_delete = tmp_list;
-             tmp_list = tmp_list->next;
-#ifdef DEBUG
-             OLSR_PRINTF(1, "MID info for %s timed out.. deleting it\n",
-                         olsr_ip_to_string(&buf, &entry_to_delete->main_addr));
-#endif
-             /*Delete it*/
-             mid_delete_node(entry_to_delete);
-           }
-         else
-             tmp_list = tmp_list->next;
-       }
-    }
-
-  return;
-}
-
-
 /*
  *Delete an entry
  *
@@ -549,6 +540,15 @@ mid_delete_node(struct mid_entry *mid)
 
       free(tmp_aliases);
     }
+
+  /*
+   * Kill any pending timers.
+   */
+  if (mid->mid_timer) {
+    olsr_stop_timer(mid->mid_timer);
+    mid->mid_timer = NULL;
+  }
+
   /* Dequeue */
   DEQUEUE_ELEM(mid);
   free(mid);
index db7ade5..2b778b7 100644 (file)
@@ -66,9 +66,10 @@ struct mid_entry
   struct mid_address *aliases;
   struct mid_entry   *prev;
   struct mid_entry   *next;
-  clock_t             ass_timer;  
+  struct timer_entry  *mid_timer;
 };
 
+#define OLSR_MID_JITTER 5 /* percent */
 
 extern struct mid_entry mid_set[HASHSIZE];
 extern struct mid_address reverse_mid_set[HASHSIZE];
index d209fbe..f62c0ee 100644 (file)
@@ -59,11 +59,10 @@ void
 olsr_init_mprs_set(void)
 {
   OLSR_PRINTF(5, "MPRS: Init\n");
+
   /* Initial values */
   ansn = 0;
 
-  olsr_register_timeout_function(&olsr_time_out_mprs_set, OLSR_TRUE);
-  
   mprs_list.next = &mprs_list;
   mprs_list.prev = &mprs_list;
 }
@@ -93,6 +92,49 @@ olsr_is_mpr(void)
 }
 #endif
 
+
+/**
+ * Wrapper for the timer callback.
+ */
+static void
+olsr_expire_mpr_sel_entry(void *context)
+{
+#if !defined(NODEBUG) && defined(DEBUG)
+  struct ipaddr_str buf;
+#endif
+  struct mpr_selector *mpr_sel;
+
+  mpr_sel = (struct mpr_selector *)context;
+  mpr_sel->MS_timer = NULL;
+
+#ifdef DEBUG
+  OLSR_PRINTF(1, "MPRS: Timing out %st\n",
+              olsr_ip_to_string(&buf, &mpr_sel->MS_main_addr));
+#endif
+
+  DEQUEUE_ELEM(mpr_sel);
+
+  /* Delete entry */
+  free(mpr_sel);
+  signal_link_changes(OLSR_TRUE);
+}
+
+
+/**
+ * Set the mpr selector expiration timer.
+ *
+ * all timer setting shall be done using this function.
+ * The timer param is a relative timer expressed in milliseconds.
+ */
+static void
+olsr_set_mpr_sel_timer(struct mpr_selector *mpr_sel, unsigned int rel_timer)
+{
+
+  olsr_set_timer(&mpr_sel->MS_timer, rel_timer, OLSR_MPR_SEL_JITTER,
+                 OLSR_TIMER_ONESHOT, &olsr_expire_mpr_sel_entry, mpr_sel, 0);
+}
+
+
 /**
  *Add a MPR selector to the MPR selector set
  *
@@ -115,7 +157,7 @@ olsr_add_mpr_selector(const union olsr_ip_addr *addr, float vtime)
 
   /* Fill struct */
   new_entry->MS_main_addr = *addr;
-  new_entry->MS_time = GET_TIMESTAMP(vtime*1000);
+  olsr_set_mpr_sel_timer(new_entry, vtime * MSEC_PER_SEC);
 
   /* Queue */
   QUEUE_ELEM(mprs_list, new_entry);
@@ -182,42 +224,10 @@ olsr_update_mprs_set(const union olsr_ip_addr *addr, float vtime)
     signal_link_changes(OLSR_TRUE);
     return 1;
   }
-  mprs->MS_time = GET_TIMESTAMP(vtime*1000);
+  olsr_set_mpr_sel_timer(mprs, vtime * MSEC_PER_SEC);
   return 0;
 }
 
-/**
- *Time out MPR selector entries
- *
- *@return nada
- */
-void
-olsr_time_out_mprs_set(void)
-{
-  struct mpr_selector *mprs = mprs_list.next;
-
-  while(mprs != &mprs_list) {
-      if(TIMED_OUT(mprs->MS_time))
-       {
-         /* Dequeue */
-         struct mpr_selector *mprs_to_delete = mprs;
-#ifndef NODEBUG
-          struct ipaddr_str buf;
-#endif
-         mprs = mprs->next;
-
-         OLSR_PRINTF(1, "MPRS: Timing out %s\n", olsr_ip_to_string(&buf, &mprs_to_delete->MS_main_addr));
-
-         DEQUEUE_ELEM(mprs_to_delete);
-
-         /* Delete entry */
-         free(mprs_to_delete);
-         signal_link_changes(OLSR_TRUE);
-       }
-      else
-       mprs = mprs->next;
-    }
-}
 
 #if 0
 /**
@@ -238,3 +248,8 @@ olsr_print_mprs_set(void)
 }
 #endif
 
+/*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */
index 4eb9ebc..e00ccdc 100644 (file)
 struct mpr_selector
 {
   union olsr_ip_addr  MS_main_addr;
-  clock_t             MS_time;
+  struct timer_entry  *MS_timer;
   struct mpr_selector *next;
   struct mpr_selector *prev;
 };
 
+#define OLSR_MPR_SEL_JITTER 5 /* percent */
 
 #if 0
 olsr_bool
@@ -88,3 +89,9 @@ olsr_print_mprs_set(void);
 #endif
 
 #endif
+
+/*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */
index 9f2eeef..8703134 100644 (file)
@@ -59,7 +59,6 @@ olsr_init_neighbor_table(void)
 {
   int i;
 
-  olsr_register_timeout_function(&olsr_time_out_neighborhood_tables, OLSR_TRUE);
   for(i = 0; i < HASHSIZE; i++)
     {
       neighbortable[i].next = &neighbortable[i];
@@ -69,36 +68,39 @@ olsr_init_neighbor_table(void)
 
 
 /**
- *Delete a two hop neighbor from a neighbors two 
- *hop neighbor list.
+ * Delete a two hop neighbor from a neighbors two hop neighbor list.
  *
- *@param neighbor the neighbor to delete the two hop 
- *neighbor from.
- *@param address the IP address of the two hop neighbor 
- *to delete.
+ * @param neighbor the neighbor to delete the two hop neighbor from.
+ * @param address the IP address of the two hop neighbor to delete.
  *
- *@return positive if entry deleted
+ * @return positive if entry deleted
  */
 int
 olsr_delete_neighbor_2_pointer(struct neighbor_entry *neighbor, union olsr_ip_addr *address)
 {
-
-  struct neighbor_2_list_entry *entry;
+  struct neighbor_2_list_entry *nbr2_list;
   
-  entry = neighbor->neighbor_2_list.next;
+  nbr2_list = neighbor->neighbor_2_list.next;
+
+  while (nbr2_list != &neighbor->neighbor_2_list) {
+      if (ipequal(&nbr2_list->neighbor_2->neighbor_2_addr, address)) {
+
+          /*
+           * Kill running timers.
+           */
+          olsr_stop_timer(nbr2_list->nbr2_list_timer);
+          nbr2_list->nbr2_list_timer = NULL;
 
-  while(entry != &neighbor->neighbor_2_list)
-    {      
-      if(ipequal(&entry->neighbor_2->neighbor_2_addr, address))
-       {
          /* Dequeue */
-         DEQUEUE_ELEM(entry);
+         DEQUEUE_ELEM(nbr2_list);
+
          /* Delete */
-         free(entry);
+         free(nbr2_list);
+
          return 1;       
-       }
-      entry = entry->next;      
-    }
+      }
+      nbr2_list = nbr2_list->next;      
+  }
   return 0;
 }
 
@@ -152,7 +154,7 @@ olsr_delete_neighbor_table(const union olsr_ip_addr *neighbor_addr)
 
   //printf("inserting neighbor\n");
 
-  hash = olsr_hashing(neighbor_addr);
+  hash = olsr_ip_hashing(neighbor_addr);
 
   entry = neighbortable[hash].next;
 
@@ -223,7 +225,7 @@ olsr_insert_neighbor_table(const union olsr_ip_addr *main_addr)
   olsr_u32_t             hash;
   struct neighbor_entry  *new_neigh;
   
-  hash = olsr_hashing(main_addr);
+  hash = olsr_ip_hashing(main_addr);
 
   /* Check if entry exists */
   
@@ -292,7 +294,7 @@ struct neighbor_entry *
 olsr_lookup_neighbor_table_alias(const union olsr_ip_addr *dst)
 {
   struct neighbor_entry  *entry;
-  olsr_u32_t             hash = olsr_hashing(dst);
+  olsr_u32_t             hash = olsr_ip_hashing(dst);
   
   //printf("\nLookup %s\n", olsr_ip_to_string(&buf, dst));
   for(entry = neighbortable[hash].next;
@@ -357,69 +359,40 @@ update_neighbor_status(struct neighbor_entry *entry, int lnk)
 }
 
 
-
 /**
- *Times out the entries in the two hop neighbor table and 
- *deletes those who have exceeded their time to live since 
- *last update.
- *
- *@return nada
+ * Callback for the nbr2_list timer.
  */
-
 void
-olsr_time_out_two_hop_neighbors(struct neighbor_entry  *neighbor)
+olsr_expire_nbr2_list(void *context)
 {
-  struct neighbor_2_list_entry *two_hop_list = neighbor->neighbor_2_list.next;
+  struct neighbor_2_list_entry *nbr2_list;
+  struct neighbor_entry *nbr;
+  struct neighbor_2_entry *nbr2;
 
-  while(two_hop_list != &neighbor->neighbor_2_list)
-    {
-      if(TIMED_OUT(two_hop_list->neighbor_2_timer))
-       {
-         struct neighbor_2_list_entry *two_hop_to_delete;
-         struct neighbor_2_entry      *two_hop_entry = two_hop_list->neighbor_2;
+  nbr2_list = (struct neighbor_2_list_entry *)context;
+  nbr2_list->nbr2_list_timer = NULL;
 
-         two_hop_entry->neighbor_2_pointer--;
-         olsr_delete_neighbor_pointer(two_hop_entry, &neighbor->neighbor_main_addr);
-         
-         if(two_hop_entry->neighbor_2_pointer < 1)
-           {
-             DEQUEUE_ELEM(two_hop_entry);
-             free(two_hop_entry);
-           }
-         
-         two_hop_to_delete = two_hop_list;
-         two_hop_list = two_hop_list->next;
+  nbr = nbr2_list->nbr2_nbr;
+  nbr2 = nbr2_list->neighbor_2;
+
+  nbr2->neighbor_2_pointer--;
+  olsr_delete_neighbor_pointer(nbr2, &nbr->neighbor_main_addr);
          
-         /* Dequeue */
-         DEQUEUE_ELEM(two_hop_to_delete);
+  if (nbr2->neighbor_2_pointer < 1) {
+      DEQUEUE_ELEM(nbr2); /* XXX replace with proper unlock function */
+      free(nbr2);
+  }
          
-         free(two_hop_to_delete);
-
-         /* This flag is set to OLSR_TRUE to recalculate the MPR set and the routing table*/
-         changes_neighborhood = OLSR_TRUE;
-         changes_topology = OLSR_TRUE;
+  /* Dequeue */
+  DEQUEUE_ELEM(nbr2_list);
          
-       }
-      else
-       two_hop_list = two_hop_list->next;
+  free(nbr2_list);
 
-    }
+  /* Set flags to recalculate the MPR set and the routing table */
+  changes_neighborhood = OLSR_TRUE;
+  changes_topology = OLSR_TRUE;
 }
 
-void
-olsr_time_out_neighborhood_tables(void)
-{
-  int idx;
-  
-  for(idx=0;idx<HASHSIZE;idx++)
-    {
-      struct neighbor_entry *entry;
-      for(entry = neighbortable[idx].next; entry != &neighbortable[idx]; entry = entry->next)
-       {         
-         olsr_time_out_two_hop_neighbors(entry);
-       }
-    }
-}
 
 /**
  *Prints the registered neighbors and two hop neighbors
index fb5cc4a..224f1be 100644 (file)
 
 struct neighbor_2_list_entry 
 {
+  struct neighbor_entry *nbr2_nbr; /* backpointer to owning nbr entry */
   struct neighbor_2_entry      *neighbor_2;
-  clock_t                     neighbor_2_timer;
+  struct timer_entry *nbr2_list_timer;
   struct neighbor_2_list_entry *next;
   struct neighbor_2_list_entry *prev;
 };
 
-
+#define OLSR_NBR2_LIST_JITTER 5 /* percent */
 
 struct neighbor_entry
 {
@@ -104,6 +105,7 @@ olsr_time_out_two_hop_neighbors(struct neighbor_entry  *);
 
 void
 olsr_time_out_neighborhood_tables(void);
+void olsr_expire_nbr2_list(void *);
 
 void
 olsr_print_neighbor_table(void);
@@ -113,3 +115,9 @@ int
 update_neighbor_status(struct neighbor_entry *, int);
 
 #endif
+
+/*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */
index 0af5d34..fb924d5 100644 (file)
@@ -169,7 +169,7 @@ olsr_process_changes(void)
 
   /* calculate the routing table */
   if (changes_neighborhood || changes_topology || changes_hna) {
-    olsr_calculate_routing_table();
+    olsr_calculate_routing_table(NULL);
   }
   
   if (olsr_cnf->debug_level > 0)
@@ -262,6 +262,12 @@ olsr_init_tables(void)
 
   /* Initialize HNA set */
   olsr_init_hna_set();  
+
+  /* Start periodic SPF and RIB recalculation */
+  if (olsr_cnf->lq_dinter > 0.0) {
+    olsr_start_timer((unsigned int)(olsr_cnf->lq_dinter * MSEC_PER_SEC), 5,
+                     OLSR_TIMER_PERIODIC, &olsr_calculate_routing_table, NULL, 0);
+  }
 }
 
 /**
@@ -404,9 +410,14 @@ set_buffer_timer(struct interface *ifn)
 void
 olsr_init_willingness(void)
 {
-  if(olsr_cnf->willingness_auto)
-    olsr_register_scheduler_event(&olsr_update_willingness, 
-                                 NULL, olsr_cnf->will_int, olsr_cnf->will_int, NULL);
+  if (olsr_cnf->willingness_auto) {
+
+    /* Run it first and then periodic. */
+    olsr_update_willingness(NULL);
+
+    olsr_start_timer((unsigned int)olsr_cnf->will_int * MSEC_PER_SEC, 5,
+                     OLSR_TIMER_PERIODIC, &olsr_update_willingness, NULL, 0);
+  }
 }
 
 void
index 56d45a1..9ebcfa1 100644 (file)
 #define MID_INTERVAL          TC_INTERVAL
 #define HNA_INTERVAL          TC_INTERVAL
 
+
+/* Emission Jitter */
+#define HELLO_JITTER         25 /* percent */
+#define HNA_JITTER           25 /* percent */
+#define MID_JITTER           25 /* percent */
+#define TC_JITTER            25 /* percent */
+
 /*
  *Holding Time
  */
@@ -434,3 +441,9 @@ union olsr_packet
 
 
 #endif
+
+/*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */
index e644974..f6894fc 100644 (file)
@@ -64,6 +64,9 @@ typedef enum {
     OLSR_TRUE
 } olsr_bool;
 
+/* user defined cookies */
+typedef uint16_t        olsr_cookie_t;
+
 #if defined linux || defined __MacOSX__ || defined WIN32 || defined __FreeBSD__ || defined __NetBSD__ || defined __OpenBSD__
 
 typedef uint8_t         olsr_u8_t;
index e85dce1..7385c30 100644 (file)
@@ -116,90 +116,84 @@ olsr_build_hello_packet(struct hello_message *message, struct interface *outif)
   OLSR_PRINTF(5, "On link:\n");
 #endif
 
-  /* Get the links of this interface */
-  links = get_link_set();
-
-  while(links != NULL)
-    {      
+  /* Walk all links of this interface */
+  OLSR_FOR_ALL_LINK_ENTRIES(links) {
 #if !defined(NODEBUG) && defined(DEBUG)
-      struct ipaddr_str buf;
+    struct ipaddr_str buf;
 #endif
-      int lnk = lookup_link_status(links);
-      /* Update the status */
+    int lnk = lookup_link_status(links);
+    /* Update the status */
       
-      /* Check if this link tuple is registered on the outgoing interface */
-      if(!ipequal(&links->local_iface_addr, &outif->ip_addr))
-       {
-         links = links->next;
-         continue;
-       }
+    /* Check if this link tuple is registered on the outgoing interface */
+    if(!ipequal(&links->local_iface_addr, &outif->ip_addr)) {
+      continue;
+    }
 
-      message_neighbor = olsr_malloc(sizeof(struct hello_neighbor), "Build HELLO");
+    message_neighbor = olsr_malloc(sizeof(struct hello_neighbor), "Build HELLO");
       
 
-      /* Find the link status */
-      message_neighbor->link = lnk;
-
+    /* Find the link status */
+    message_neighbor->link = lnk;
+
+    /*
+     * Calculate neighbor status
+     */
+    /* 
+     * 2.1  If the main address, corresponding to
+     *      L_neighbor_iface_addr, is included in the MPR set:
+     *
+     *            Neighbor Type = MPR_NEIGH
+     */
+    if(links->neighbor->is_mpr)
+    {
+      message_neighbor->status = MPR_NEIGH;
+    }
+    /*
+     *  2.2  Otherwise, if the main address, corresponding to
+     *       L_neighbor_iface_addr, is included in the neighbor set:
+     */
+      
+    /* NOTE:
+     * It is garanteed to be included when come this far
+     * due to the extentions made in the link sensing
+     * regarding main addresses.
+     */
+    else
+    {
       /*
-       * Calculate neighbor status
-       */
-      /* 
-       * 2.1  If the main address, corresponding to
-       *      L_neighbor_iface_addr, is included in the MPR set:
+       *   2.2.1
+       *        if N_status == SYM
        *
-       *            Neighbor Type = MPR_NEIGH
+       *             Neighbor Type = SYM_NEIGH
        */
-      if(links->neighbor->is_mpr)
-       {
-         message_neighbor->status = MPR_NEIGH;
-       }
+      if(links->neighbor->status == SYM)
+      {
+        message_neighbor->status = SYM_NEIGH;
+      }
       /*
-       *  2.2  Otherwise, if the main address, corresponding to
-       *       L_neighbor_iface_addr, is included in the neighbor set:
-       */
-      
-      /* NOTE:
-       * It is garanteed to be included when come this far
-       * due to the extentions made in the link sensing
-       * regarding main addresses.
+       *   2.2.2
+       *        Otherwise, if N_status == NOT_SYM
+       *             Neighbor Type = NOT_NEIGH
        */
       else
-       {
-         /*
-          *   2.2.1
-          *        if N_status == SYM
-          *
-          *             Neighbor Type = SYM_NEIGH
-          */
-         if(links->neighbor->status == SYM)
-           {
-             message_neighbor->status = SYM_NEIGH;
-           }
-         /*
-          *   2.2.2
-          *        Otherwise, if N_status == NOT_SYM
-          *             Neighbor Type = NOT_NEIGH
-          */
-         else
-           if(links->neighbor->status == NOT_SYM)
-             {
-               message_neighbor->status = NOT_NEIGH;
-             }
-       }
+        if(links->neighbor->status == NOT_SYM)
+        {
+          message_neighbor->status = NOT_NEIGH;
+        }
+    }
   
-      /* Set the remote interface address */
-      message_neighbor->address = links->neighbor_iface_addr;
+    /* Set the remote interface address */
+    message_neighbor->address = links->neighbor_iface_addr;
       
-      /* Set the main address */
-      message_neighbor->main_address = links->neighbor->neighbor_main_addr;
+    /* Set the main address */
+    message_neighbor->main_address = links->neighbor->neighbor_main_addr;
 #ifdef DEBUG
-      OLSR_PRINTF(5, "Added: %s -  status %d\n", olsr_ip_to_string(&buf, &message_neighbor->address), message_neighbor->status);
+    OLSR_PRINTF(5, "Added: %s -  status %d\n", olsr_ip_to_string(&buf, &message_neighbor->address), message_neighbor->status);
 #endif
-      message_neighbor->next=message->neighbors;
-      message->neighbors=message_neighbor;         
+    message_neighbor->next=message->neighbors;
+    message->neighbors=message_neighbor;           
       
-      links = links->next;
-    }
+  } OLSR_FOR_ALL_LINK_ENTRIES_END(links);
   
   /* Add the links */
 
@@ -299,7 +293,7 @@ olsr_build_hello_packet(struct hello_message *message, struct interface *outif)
            message->neighbors=message_neighbor;            
          }
       }
-  
+
 
   return 0;
 }
@@ -459,3 +453,9 @@ olsr_free_mid_packet(struct mid_message *message)
       free(tmp_adr2);
     }
 }
+
+/*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */
index 3094416..fdc69ba 100644 (file)
@@ -422,8 +422,6 @@ parse_packet(struct olsr *olsr, int size, struct interface *in_if, union olsr_ip
        }
 
     } /* for olsr_msg */ 
-
-
 }
 
 
index 2f922e9..c66818e 100644 (file)
@@ -114,7 +114,10 @@ process_message_neighbors(struct neighbor_entry *neighbor, const struct hello_me
           if (two_hop_neighbor_yet != NULL)
             {
               /* Updating the holding time for this neighbor */
-              two_hop_neighbor_yet->neighbor_2_timer = GET_TIMESTAMP(message->vtime*1000);
+              olsr_set_timer(&two_hop_neighbor_yet->nbr2_list_timer,
+                             message->vtime * MSEC_PER_SEC, OLSR_NBR2_LIST_JITTER,
+                             OLSR_TIMER_ONESHOT, &olsr_expire_nbr2_list,
+                             two_hop_neighbor_yet, 0);
               two_hop_neighbor = two_hop_neighbor_yet->neighbor_2;
 
               // For link quality OLSR, reset the path link quality here.
@@ -412,8 +415,10 @@ linking_this_2_entries(struct neighbor_entry *neighbor, struct neighbor_2_entry
   two_hop_neighbor->neighbor_2_nblist.next = list_of_1_neighbors;
   list_of_1_neighbors->prev = &two_hop_neighbor->neighbor_2_nblist;
   list_of_2_neighbors->neighbor_2 = two_hop_neighbor;
+  list_of_2_neighbors->nbr2_nbr = neighbor; /* XXX refcount */
   
-  list_of_2_neighbors->neighbor_2_timer = GET_TIMESTAMP(vtime*1000);
+  olsr_change_timer(list_of_2_neighbors->nbr2_list_timer, vtime * MSEC_PER_SEC,
+                    OLSR_NBR2_LIST_JITTER, OLSR_TIMER_ONESHOT);
 
   /* Queue */
   neighbor->neighbor_2_list.next->prev = list_of_2_neighbors;
index f897e42..0456c84 100644 (file)
@@ -673,11 +673,11 @@ olsr_rtp_to_string(const struct rt_path *rtp)
 void
 olsr_print_routing_table(const struct avl_tree *tree)
 {
+#ifndef NODEBUG
+  /* The whole function makes no sense without it. */
   const struct avl_node *rt_tree_node;
 
-#ifdef DEBUG
-  printf("ROUTING TABLE\n");
-#endif
+  OLSR_PRINTF(6, "ROUTING TABLE\n");
 
   for (rt_tree_node = avl_walk_first_c(tree);
        rt_tree_node != NULL;
@@ -687,7 +687,7 @@ olsr_print_routing_table(const struct avl_tree *tree)
     const struct rt_entry * const rt = rt_tree_node->data;
 
     /* first the route entry */
-    printf("%s/%u, via %s, best-originator %s\n",
+    OLSR_PRINTF(6, "%s/%u, via %s, best-originator %s\n",
            olsr_ip_to_string(&prefixstr, &rt->rt_dst.prefix),
            rt->rt_dst.prefix_len,
            olsr_ip_to_string(&origstr, &rt->rt_nexthop.gateway),
@@ -698,7 +698,7 @@ olsr_print_routing_table(const struct avl_tree *tree)
          rtp_tree_node != NULL;
          rtp_tree_node = avl_walk_next_c(rtp_tree_node)) {
       const struct rt_path * const rtp = rtp_tree_node->data;
-      printf("\tfrom %s, etx %s, metric %u, via %s, %s, v %u\n",
+      OLSR_PRINTF(6, "\tfrom %s, etx %s, metric %u, via %s, %s, v %u\n",
              olsr_ip_to_string(&origstr, &rtp->rtp_originator),
              olsr_etx_to_string(rtp->rtp_metric.etx),
              rtp->rtp_metric.hops,
@@ -707,6 +707,8 @@ olsr_print_routing_table(const struct avl_tree *tree)
              rtp->rtp_version);    
     }
   }
+#endif
+  tree = NULL; /* squelch compiler warnings */
 }
 
 /*
index 8f3d07a..9da0cf3 100644 (file)
@@ -1,6 +1,7 @@
 /*
  * The olsr.org Optimized Link-State Routing daemon(olsrd)
  * Copyright (c) 2004, Andreas Tønnesen(andreto@olsr.org)
+ * Timer rewrite (c) 2008, Hannes Gredler (hannes@gredler.at)
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without 
 #include "olsr.h"
 #include "build_msg.h"
 #include "net_olsr.h"
+#include "socket_parser.h"
+#include "lq_route.h"
+#include "link_set.h"
 
 /* Timer data, global. Externed in defs.h */
-clock_t now_times;              /* current idea of times(2) reported uptime */
-struct timeval now;            /* current idea of time */
-struct tm *nowtm;              /* current idea of time (in tm) */
+clock_t now_times;  /* current idea of times(2) reported uptime */
 
-/* Lists */
-static struct timeout_entry *timeout_functions;
-static struct event_entry *event_functions;
+/* Hashed root of all timers */
+struct list_node timer_wheel[TIMER_WHEEL_SLOTS];
+clock_t timer_last_run; /* remember the last timeslot walk */
 
-static olsr_bool link_changes; /* is set if changes occur in MPRS set */ 
+/* Pool of timers to avoid malloc() churn */
+struct list_node free_timer_list;
 
-void
-signal_link_changes(olsr_bool val)
-{
-  link_changes = val;
-}
+/* Statistics */
+unsigned int timers_running;
 
-static void 
-trigger_dijkstra(void *foo __attribute__((unused)))
-{
-  OLSR_PRINTF(3, "Triggering Dijkstra\n");
 
-  changes_neighborhood = OLSR_TRUE;
-  changes_topology = OLSR_TRUE;
-  changes_force = OLSR_TRUE;
+/**
+ * Sleep until the next scheduling interval.
+ *
+ * @param scheduler loop runtime in clock ticks.
+ * @return nada
+ */
+static void
+olsr_scheduler_sleep(clock_t scheduler_runtime)
+{
+  struct timespec remainder_spec, sleeptime_spec;
+  struct timeval sleeptime_val, time_used, next_interval;
+  olsr_u32_t next_interval_usec;
+  clock_t milliseconds_used;
+
+  /* Calculate next planned scheduler invocation */
+  next_interval_usec = olsr_cnf->pollrate * USEC_PER_SEC;
+  next_interval.tv_sec = next_interval_usec / USEC_PER_SEC;
+  next_interval.tv_usec = next_interval_usec % USEC_PER_SEC;
+
+  /* Determine used runtime */
+  milliseconds_used = scheduler_runtime * olsr_cnf->system_tick_divider;
+  time_used.tv_sec = milliseconds_used / MSEC_PER_SEC;
+  time_used.tv_usec = (milliseconds_used % MSEC_PER_SEC) * USEC_PER_MSEC;
+
+  if (timercmp(&time_used, &next_interval, <)) {
+    timersub(&next_interval, &time_used, &sleeptime_val);
+         
+    sleeptime_spec.tv_sec = sleeptime_val.tv_sec;
+    sleeptime_spec.tv_nsec = sleeptime_val.tv_usec * NSEC_PER_USEC;
+         
+    while (nanosleep(&sleeptime_spec, &remainder_spec) < 0)
+      sleeptime_spec = remainder_spec;
+  }
 }
 
 /**
- *Main scheduler event loop. Polls at every
- *sched_poll_interval and calls all functions
- *that are timed out or that are triggered.
- *Also calls the olsr_process_changes()
- *function at every poll.
+ * Main scheduler event loop. Polls at every
+ * sched_poll_interval and calls all functions
+ * that are timed out or that are triggered.
+ * Also calls the olsr_process_changes()
+ * function at every poll.
  *
- *
- *@return nada
+ * @return nada
  */
-
 void
-scheduler(void)
+olsr_scheduler(void)
 {
-  struct timeval interval;
-  olsr_u32_t interval_usec;
-
-  link_changes = OLSR_FALSE;
-
-  if(olsr_cnf->lq_level > 1 && olsr_cnf->lq_dinter > 0.0)
-    olsr_register_scheduler_event(trigger_dijkstra, NULL, olsr_cnf->lq_dinter, 0, NULL);
-
-  interval_usec = olsr_cnf->pollrate * 1000000;
-
-  interval.tv_sec = interval_usec / 1000000;
-  interval.tv_usec = interval_usec % 1000000;
+  struct tms tms_buf;   /* Buffer for times(2) calls. */
+  struct interface *ifn;
 
   OLSR_PRINTF(1, "Scheduler started - polling every %0.2f seconds\n", olsr_cnf->pollrate);
   OLSR_PRINTF(3, "Max jitter is %f\n\n", olsr_cnf->max_jitter);
 
-  /* Main scheduler event loop */
-  for(;;)
-    {
-      /*
-       * Used to calculate sleep time
-       */
-      clock_t end_of_loop;
-      clock_t milliseconds_used;
-      struct timeval time_used;
-      struct event_entry *entry;
-      struct timeout_entry *time_out_entry;
-      struct interface *ifn;
-
-      /* Global buffer for times(2) calls. Do not remove - at least OpenBSD needs it. */
-      struct tms tms_buf;
+  /* Main scheduler loop */
+  for (;;) {
  
-      /* Update now_times */
-      now_times = times(&tms_buf);
-
-      /* Update the global timestamp - kept for plugin compat */
-      gettimeofday(&now, NULL);
-      do {
-          nowtm = localtime(&now.tv_sec);
-      } while (nowtm == NULL);
-
-      /* Run timeout functions (before packet generation) */      
-      for (time_out_entry = timeout_functions; time_out_entry != NULL; time_out_entry = time_out_entry->next) {
-         time_out_entry->function();
+    /*
+     * Update the global timestamp. We are using a non-wallclock timer here
+     * to avoid any undesired side effects if the system clock changes.
+     */
+    now_times = times(&tms_buf);
+
+    /* Read incoming data */
+    olsr_poll_sockets();
+
+    /* Process timers (before packet generation) */      
+    olsr_walk_timers(&timer_last_run);
+
+    /* Update */      
+    olsr_process_changes();
+
+    /* Check for changes in topology */
+    if (link_changes) {
+      OLSR_PRINTF(3, "ANSN UPDATED %d\n\n", get_local_ansn());
+      increase_local_ansn();
+      link_changes = OLSR_FALSE;
+    }
+
+    /* looping trough interfaces and emmitting pending data */
+    for (ifn = ifnet; ifn ; ifn = ifn->int_next) { 
+      if (net_output_pending(ifn) && TIMED_OUT(ifn->fwdtimer)) {
+        net_output(ifn);
       }
+    }
 
-      /* Update */      
-      olsr_process_changes();
-
-      /* Check for changes in topology */
-      if(link_changes)
-        {
-         OLSR_PRINTF(3, "ANSN UPDATED %d\n\n", get_local_ansn());
-         increase_local_ansn();
-          link_changes = OLSR_FALSE;
-       }
-
-
-      /* Check scheduled events */
-      
-      /* UPDATED - resets timer upon triggered execution */
-      for (entry = event_functions; entry != NULL; entry = entry->next)
-       {
-         entry->since_last += olsr_cnf->pollrate;
-
-         /* Timed out */
-         if ((entry->since_last > entry->interval) ||
-              /* Triggered */
-              ((entry->trigger != NULL) && (*entry->trigger == 1))
-              ) {
-             /* Run scheduled function */
-             entry->function(entry->param);
-
-             /* Set jitter */
-             entry->since_last = (float)(random() / RAND_MAX) * olsr_cnf->max_jitter;
-             
-             /* Reset trigger */
-             if(entry->trigger != NULL) {
-               *entry->trigger = 0;
-              }
-
-             //OLSR_PRINTF(3, "Since_last jitter: %0.2f\n", entry->since_last);
-           }
-       }
-
-      /* looping trough interfaces and emmittin pending data */
-      for (ifn = ifnet; ifn ; ifn = ifn->int_next) 
-       { 
-         if(net_output_pending(ifn) && TIMED_OUT(ifn->fwdtimer)) 
-           net_output(ifn);
-       }
-
-
-      end_of_loop = times(&tms_buf);
-
-      //printf("Tick diff: %d\n", end_of_loop - now_times);
-      milliseconds_used = (end_of_loop - now_times) * olsr_cnf->system_tick_divider;
-      time_used.tv_sec = milliseconds_used / 1000;
-      time_used.tv_usec = (milliseconds_used % 1000) * 1000;
-
-      //printf("Time used: %d.%04d\n", time_used.tv_sec, time_used.tv_usec);
-
-      if(timercmp(&time_used, &interval, <))
-       {
-          struct timespec remainder_spec;
-          struct timespec sleeptime_spec;
-          struct timeval sleeptime_val;
-         timersub(&interval, &time_used, &sleeptime_val);
-         
-         // printf("sleeptime_val = %u.%06u\n",
-         //        sleeptime_val.tv_sec, sleeptime_val.tv_usec);
-         
-         sleeptime_spec.tv_sec = sleeptime_val.tv_sec;
-         sleeptime_spec.tv_nsec = sleeptime_val.tv_usec * 1000;
-         
-         while(nanosleep(&sleeptime_spec, &remainder_spec) < 0)
-           sleeptime_spec = remainder_spec;
-       }
+    /* We are done, sleep until the next scheduling interval. */
+    olsr_scheduler_sleep(times(&tms_buf) - now_times);
 
 #if defined WIN32
-      // the Ctrl-C signal handler thread asks us to exit
-
-      if (olsr_win32_end_request)
-        break;
-#endif
-      
-    }//end for
+    /* The Ctrl-C signal handler thread asks us to exit */
+    if (olsr_win32_end_request) {
+      break;
+    }
+#endif      
+  }
 
 #if defined WIN32
-  // tell the Ctrl-C signal handler thread that we have exited
-
+  /* Tell the Ctrl-C signal handler thread that we have exited */
   olsr_win32_end_flag = TRUE;
 
-  // the Ctrl-C signal handler thread will exit the process and
-  // hence also kill us
-  
-  while (1)
-    Sleep(1000);
+  /*
+   * The Ctrl-C signal handler thread will exit the process
+   * and hence also kill us.
+   */
+  while (1) {
+    Sleep(1000); /* milliseconds */
+  }
 #endif
 }
 
 
-/*
+/**
+ * Decrement a relative timer by a random number range.
  *
- *@param initial how long utnil the first generation
- *@param trigger pointer to a boolean indicating that
- *this function should be triggered immediatley
+ * @param the relative timer expressed in units of milliseconds.
+ * @param the jitter in percent
+ * @param cached result of random() at system init.
+ * @return the absolute timer in system clock tick units
  */
-int
-olsr_register_scheduler_event(void (*event_function)(void *), 
-                             void *par,
-                             float interval, 
-                             float initial, 
-                             olsr_u8_t *trigger)
+static clock_t 
+olsr_jitter(unsigned int rel_time, olsr_u8_t jitter_pct, unsigned int random)
 {
-  struct event_entry *new_entry;
-
-  OLSR_PRINTF(3, "Scheduler event registered int: %0.2f\n", interval);
-
-  /* check that this entry is not added already */
-  new_entry = event_functions;
-  while(new_entry)
-    {
-      if((new_entry->function == event_function) &&
-        (new_entry->param == par) &&
-        (new_entry->trigger == trigger) &&
-        (new_entry->interval == interval))
-       {
-         fprintf(stderr, "Register scheduler event: Event alread registered!\n");
-         olsr_syslog(OLSR_LOG_ERR, "Register scheduler event: Event alread registered!\n");
-         return 0;
-       }
-      new_entry = new_entry->next;
-    }
+  unsigned int jitter_time, factorial;
+
+  /*
+   * No jitter or, jitter larger than 99% does not make sense.
+   * Also protect against overflows resulting from > 25 bit timers.
+   */
+  if (jitter_pct == 0 || jitter_pct > 99 || rel_time > (1 << 24)) {
+    return GET_TIMESTAMP(rel_time);
+  }
+
+  /*
+   * Play some tricks to avoid overflows with integer arithmetic.
+   */
+  jitter_time = (jitter_pct * rel_time) / 100;
+  factorial = random / (RAND_MAX / jitter_time);
+  jitter_time = (jitter_time * factorial) / (RAND_MAX / jitter_time);
+
+#if 0
+  OLSR_PRINTF(1, "TIMER: jitter %u%% rel_time %u%% to %u\n",
+              rel_time, jitter_pct, rel_time - jitter_time);
+#endif
+
+  return GET_TIMESTAMP(rel_time - jitter_time);
+}
+
 
-  new_entry = olsr_malloc(sizeof(struct event_entry), "add scheduler event");
+/**
+ * Allocate a timer_entry.
+ * Do this first by checking if something is available in the free_timer_pool
+ * If not then allocate a big chunk of memory and thread its elements up
+ * to the free_timer_list.
+ */
+static struct timer_entry *
+olsr_get_timer(void)
+{
+  void *timer_block;
+  struct timer_entry *timer;
+  struct list_node *timer_list_node;
+  unsigned int timer_index;
+
+  /*
+   * If there is at least one timer in the pool then remove the first
+   * element from the pool and recycle it.
+   */
+  if (!list_is_empty(&free_timer_list)) {
+    timer_list_node = free_timer_list.next;
+    
+    /* carve it out of the pool, do not memset overwrite timer->timer_random */
+    list_remove(timer_list_node);
+    timer = list2timer(timer_list_node);
+
+    return timer;
+  }
 
-  new_entry->function = event_function;
-  new_entry->param = par;
-  new_entry->interval = interval;
-  new_entry->since_last = interval - initial;
-  new_entry->next = event_functions;
-  new_entry->trigger = trigger;
+  /*
+   * Nothing in the pool, allocate a new chunk.
+   */
+  timer_block = olsr_malloc(sizeof(struct timer_entry) * OLSR_TIMER_MEMORY_CHUNK,
+                            "timer chunk");
+  memset(timer_block, 0, sizeof(struct timer_entry) * OLSR_TIMER_MEMORY_CHUNK); 
+
+#if 0
+  OLSR_PRINTF(1, "TIMER: alloc %u bytes chunk at %p\n",
+              sizeof(struct timer_entry) * OLSR_TIMER_MEMORY_CHUNK,
+              timer_block);
+#endif
+
+  /*
+   * Slice the chunk up and put the future timer_entries in the free timer pool.
+   */
+  timer = timer_block;
+  for (timer_index = 0; timer_index < OLSR_TIMER_MEMORY_CHUNK; timer_index++) {
 
-  event_functions = new_entry;
+    /* Insert new timers at the tail of the free_timer list */
+    list_add_before(&free_timer_list, &timer->timer_list);
 
-  return 1;
+    /* 
+     * For performance reasons (read: frequent timer changes),
+     * precompute a random number once per timer and reuse later.
+     * The random number only gets recomputed if a periodical timer fires,
+     * such that a different jitter is applied for future firing.
+     */
+    timer->timer_random = random();
+
+    timer++;
+  }
+
+  /*
+   * There are now timers in the pool, recurse once.
+   */
+  return olsr_get_timer();
 }
 
 
+/**
+ * Init datastructures for maintaining timers.
+ */
+void
+olsr_init_timers(void)
+{
+  struct list_node *timer_head_node;
+  int index;
+
+  OLSR_PRINTF(5, "TIMER: init timers\n");
 
-/*
- *
- *@param initial how long until the first generation
- *@param trigger pointer to a boolean indicating that
- *this function should be triggered immediatley
+  memset(timer_wheel, 0 , sizeof(timer_wheel));
+
+  timer_head_node = timer_wheel;
+  for (index = 0; index < TIMER_WHEEL_SLOTS; index++) {
+    list_head_init(timer_head_node);
+    timer_head_node++;
+  }
+
+  /*
+   * Reset the last timer run.
+   */
+  timer_last_run = now_times;
+
+  /* Timer memory pooling */
+  list_head_init(&free_timer_list);
+  timers_running = 0;
+}
+
+
+/**
+ * Walk through the timer list and check if any timer is ready to fire.
+ * Callback the provided function with the context pointer.
  */
-int
-olsr_remove_scheduler_event(void (*event_function)(void *), 
-                           void *par,
-                           float interval, 
-                           float initial __attribute__((unused)), 
-                           olsr_u8_t *trigger)
+void
+olsr_walk_timers(clock_t *last_run)
 {
-  struct event_entry *entry, *prev;
-
-  prev = NULL;
-  entry = event_functions;
-
-  while(entry)
-    {
-      if((entry->function == event_function) &&
-        (entry->param == par) &&
-        (entry->trigger == trigger) &&
-        (0.0 > interval || entry->interval == interval))
-       {
-         if(entry == event_functions)
-           {
-             event_functions = entry->next;
-           }
-         else
-           {
-             prev->next = entry->next;
-           }
-          free(entry);
-         return 1;
-       }
-
-      prev = entry;
-      entry = entry->next;
+  static struct timer_entry *timer;
+  struct list_node *timer_list_node, *timer_list_node_next, *timer_head_node;
+  unsigned int timers_walked, timers_fired;
+  unsigned int total_timers_walked, total_timers_fired;
+  unsigned int wheel_slot_walks = 0;
+
+  /*
+   * Check the required wheel slots since the last time a timer walk was invoked,
+   * or check *all* the wheel slots, whatever is less work.
+   * The latter is meant as a safety belt if the scheduler falls behind.
+   */
+  total_timers_walked = total_timers_fired = timers_walked = timers_fired = 0;
+  while ((*last_run <= now_times) && (wheel_slot_walks < TIMER_WHEEL_SLOTS)) {
+
+    /* keep some statistics */
+    total_timers_walked += timers_walked;
+    total_timers_fired += timers_fired;
+    timers_walked = 0;
+    timers_fired = 0;
+
+    /* Get the hash slot for this clocktick */
+    timer_head_node = &timer_wheel[*last_run & TIMER_WHEEL_MASK];
+
+    /* Walk all entries hanging off this hash bucket */
+    for (timer_list_node = timer_head_node->next;
+         timer_list_node != timer_head_node; /* circular list */
+         timer_list_node = timer_list_node_next) {
+
+      /* prefetch next node in case this node fires and we have to delete. */
+      timer_list_node_next = timer_list_node->next;
+      timer = list2timer(timer_list_node);
+
+      timers_walked++;
+
+      /* Ready to fire ? */
+      if (TIMED_OUT(timer->timer_clock)) {
+
+        olsr_printf(3, "TIMER: fire timer %p, ctx %p, "
+                    "cookie %u at clocktick %u\n",
+                    timer, timer->timer_cb_context, timer->timer_cookie,
+                    (unsigned int)(*last_run));
+
+        /* This timer is expired, call into the provided callback function */
+        timer->timer_cb(timer->timer_cb_context);
+
+        if (timer->timer_period) {
+
+          /* For periodical timers, rehash the random number and restart */
+          timer->timer_random = random();
+          olsr_change_timer(timer, timer->timer_period, timer->timer_jitter_pct,
+                            OLSR_TIMER_PERIODIC);
+        } else {
+
+          /*
+           * Don't stop the timer if the callback function already has stopped
+           * the timer.
+           */
+          if (timer->timer_flags & OLSR_TIMER_RUNNING) {
+
+            /* Singleshot timers are stopped and returned to the pool */
+            olsr_stop_timer(timer);
+          }
+        }
+
+        timers_fired++;
+      }
     }
 
-  return 0;
+    /* Increment the time slot and wheel slot walk iteration */
+    (*last_run)++;
+    wheel_slot_walks++;
+  }
+
+#ifdef DEBUG
+  olsr_printf(3, "TIMER: processed %4u/%u clockwheel slots, "
+              "timers walked %4u/%u, timers fired %u\n",
+              wheel_slot_walks, TIMER_WHEEL_SLOTS,
+              total_timers_walked, timers_running, total_timers_fired);
+#endif
+
 }
 
-/*
- * Sven-Ola, 2007: Since the original timing and flagging is changed (which
- * saves lots of CPU time - see LinkQualityDijkstraLimit) the original timeout
- * functions called every olsr_cnf->polltime uses too much CPU now. Because the
- * changes_xxx handling is switched off with LQDL, it should be OK to call
- * all timeout handlers at a much lower rate. To overcome UDP packet loss,
- * a very low pollrate is used.
+
+/**
+ * Format an relative system time string.
+ * May be called upto 4 times in a single printf() statement.
+ *
+ * @param absolute time expressed in clockticks
+ * @return buffer to a formatted system time string.
  */
+const char*
+olsr_clock_string(clock_t clock)
+{
+  static char buf[4][32];
+  static int idx = 0;
+  char *ret;
+  unsigned int sec,msec;
 
-static float dijkstra_initial = 0.0;
+  ret = buf[idx];
+  idx = (idx+1) & 3;
+
+  /* On most systems a clocktick is a 10ms quantity. */
+  msec = olsr_cnf->system_tick_divider * (unsigned int)(clock - now_times);
+  sec = msec / MSEC_PER_SEC;
+
+  snprintf(ret, sizeof(buf)/4, "%02u:%02u:%02u.%03u",
+           sec / 3600, (sec % 3600) / 60, (sec % 60), (msec % MSEC_PER_SEC));
+
+  return ret;
+}
 
-int
-olsr_register_scheduler_event_dijkstra(void (*event_function)(void *), 
-                             void *par,
-                             float interval, 
-                             float initial, 
-                             olsr_u8_t *trigger)
+
+/**
+ * Start a new timer.
+ *
+ * @param relative time expressed in milliseconds
+ * @param jitter expressed in percent
+ * @param timer callback function
+ * @param context for the callback function
+ * @return a pointer to the created entry
+ */
+struct timer_entry *
+olsr_start_timer(unsigned int rel_time, olsr_u8_t jitter_pct,
+                 olsr_bool periodical, void (*timer_cb_function)(void *),
+                 void *context, olsr_cookie_t cookie)
 {
-  if (1 < olsr_cnf->lq_level && 0.0 < olsr_cnf->lq_dinter)
-  {
-    dijkstra_initial += olsr_cnf->lq_dinter / 10.0;
-    return olsr_register_scheduler_event(event_function, par, olsr_cnf->lq_dinter, dijkstra_initial, trigger);
+  struct timer_entry *timer;
+
+  timer = olsr_get_timer();
+
+  /* Fill entry */
+  timer->timer_clock = olsr_jitter(rel_time, jitter_pct, timer->timer_random);
+  timer->timer_cb = timer_cb_function;
+  timer->timer_cb_context = context;
+  timer->timer_jitter_pct = jitter_pct;
+  timer->timer_flags = OLSR_TIMER_RUNNING;
+
+  /* The cookie is used for debugging to traceback the originator */
+  timer->timer_cookie = cookie;
+
+  /* Singleshot or periodical timer ? */
+  if (periodical) {
+    timer->timer_period = rel_time;
+  } else {
+    timer->timer_period = 0;
   }
-  return olsr_register_scheduler_event(event_function, par, interval, initial, trigger);
+
+  /*
+   * Now insert in the respective timer_wheel slot.
+   */
+  list_add_before(&timer_wheel[timer->timer_clock & TIMER_WHEEL_MASK],
+                  &timer->timer_list);
+  timers_running++;
+
+#ifdef DEBUG
+  OLSR_PRINTF(3, "TIMER: start timer %p firing in %s, ctx %p\n",
+              timer, olsr_clock_string(timer->timer_clock), context);
+#endif
+
+  return timer;
 }
 
-int
-olsr_register_timeout_function(void (*time_out_function)(void), olsr_bool dijkstra_limit_ok)
+
+/**
+ * Delete a timer.
+ *
+ * @param the timer_entry that shall be removed
+ * @return nada
+ */
+void
+olsr_stop_timer(struct timer_entry *timer)
 {
-  struct timeout_entry *new_entry;
-
-  if (dijkstra_limit_ok && 1 < olsr_cnf->lq_level && 0.0 < olsr_cnf->lq_dinter)
-  {
-    dijkstra_initial += olsr_cnf->lq_dinter / 10.0;
-    return olsr_register_scheduler_event(
-      (void *)time_out_function,
-      NULL,
-      olsr_cnf->lq_dinter,
-      dijkstra_initial,
-      NULL);
+
+  /* sanity check */
+  if (!timer) {
+    return;
   }
-  
-  /* check that this entry is not added already */
-  new_entry = timeout_functions;
-  while(new_entry)
-    {
-      if(new_entry->function == time_out_function)
-       {
-         fprintf(stderr, "Register scheduler timeout: Event alread registered!\n");
-         olsr_syslog(OLSR_LOG_ERR, "Register scheduler timeout: Event alread registered!\n");
-         return 0;
-       }
-      new_entry = new_entry->next;
-    }
 
-  new_entry = olsr_malloc(sizeof(struct timeout_entry), "scheduler add timeout");
+#ifdef DEBUG
+  OLSR_PRINTF(3, "TIMER: stop timer %p firing in %s, ctx %p\n",
+              timer, olsr_clock_string(timer->timer_clock),
+              timer->timer_cb_context);
+#endif
 
-  new_entry->function = time_out_function;
-  new_entry->next = timeout_functions;
+  /*
+   * Carve out of the existing wheel_slot and return to the pool
+   * rather than freeing for later reycling.
+   */
+  list_remove(&timer->timer_list);
+  list_add_before(&free_timer_list, &timer->timer_list);
+  timer->timer_flags &= ~OLSR_TIMER_RUNNING;
+  timers_running--;
+}
 
-  timeout_functions = new_entry;
 
-  return 1;
-}
+/**
+ * Change a timer_entry.
+ *
+ * @param timer_entry to be changed.
+ * @param new relative time expressed in units of milliseconds.
+ * @param new jitter expressed in percent.
+ * @return nada
+ */
+void
+olsr_change_timer(struct timer_entry *timer, unsigned int rel_time,
+                  olsr_u8_t jitter_pct, olsr_bool periodical)
+{
 
+  /* Sanity check. */
+  if (!timer) {
+    return;
+  }
 
+  /* Singleshot or periodical timer ? */
+  if (periodical) {
+    timer->timer_period = rel_time;
+  } else {
+    timer->timer_period = 0;
+  }
 
-int
-olsr_remove_timeout_function(void (*time_out_function)(void), olsr_bool dijkstra_limit_ok)
+  timer->timer_clock = olsr_jitter(rel_time, jitter_pct, timer->timer_random);
+  timer->timer_jitter_pct = jitter_pct;
+
+  /*
+   * Changes are easy: Remove timer from the exisiting timer_wheel slot
+   * and reinsert into the new slot.
+   */
+  list_remove(&timer->timer_list);
+  list_add_before(&timer_wheel[timer->timer_clock & TIMER_WHEEL_MASK],
+                  &timer->timer_list);
+
+#ifdef DEBUG
+  OLSR_PRINTF(3, "TIMER: change timer %p, firing to %s, ctx %p\n",
+              timer,
+              olsr_clock_string(timer->timer_clock),
+              timer->timer_cb_context);
+#endif
+}
+
+
+/*
+ * This is the one stop shop for all sort of timer manipulation.
+ * Depending on the paseed in parameters a new timer is started,
+ * or an existing timer is started or an existing timer is
+ * terminated.
+ */
+void
+olsr_set_timer(struct timer_entry **timer_ptr, unsigned int rel_time,
+               olsr_u8_t jitter_pct, olsr_bool periodical,
+               void (*timer_cb_function)(void *), void *context,
+               olsr_cookie_t cookie)
 {
-  struct timeout_entry *entry, *prev;
-
-  if (dijkstra_limit_ok && 1 < olsr_cnf->lq_level && 0.0 < olsr_cnf->lq_dinter)
-  {
-    return olsr_remove_scheduler_event(
-      (void *)time_out_function,
-      NULL,
-      -1.0,
-      -1.0,
-      NULL);
-  }
-  
-  /* check that this entry is not added already */
-  entry = timeout_functions;
-  prev = NULL;
-
-  while(entry)
-    {
-      if(entry->function == time_out_function)
-       {
-         if(entry == timeout_functions)
-           {
-             timeout_functions = entry->next;
-           }
-         else
-           {
-             prev->next = entry->next;
-           }
-         free(entry);
-         return 1;
-       }
-      prev = entry;
-      entry = entry->next;
-    }
 
-  return 0;
+  if (!*timer_ptr) {
+
+    /* No timer running, kick it. */
+    *timer_ptr = olsr_start_timer(rel_time, jitter_pct, periodical,
+                                  timer_cb_function, context, cookie);
+  } else {
+
+    if (!rel_time) {
+
+      /* No good future time provided, kill it.*/
+      olsr_stop_timer(*timer_ptr);
+      *timer_ptr = NULL;
+    } else {
+
+      /* Time is ok and timer is running, change it !*/
+      olsr_change_timer(*timer_ptr, rel_time, jitter_pct, periodical);
+    }
+  }
 }
 
+/*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */
index a3831d1..033a025 100644 (file)
@@ -1,6 +1,7 @@
 /*
  * The olsr.org Optimized Link-State Routing daemon(olsrd)
  * Copyright (c) 2004, Andreas Tønnesen(andreto@olsr.org)
+ * Timer rewrite (c) 2008, Hannes Gredler (hannes@gredler.at)
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without 
  */
 
 
-
-
 #ifndef _OLSR_SCHEDULER
 #define _OLSR_SCHEDULER
 
+#include "lq_list.h"
 
-/* List entries */
-
-/* Timeout entry */
-
-struct timeout_entry
-{
-  void (*function)(void);
-  struct timeout_entry *next;
-};
+#define TIMER_WHEEL_SLOTS 256
+#define TIMER_WHEEL_MASK (TIMER_WHEEL_SLOTS - 1)
 
-/* Event entry */
+/* Some defs for juggling with timers */
+#define MSEC_PER_SEC 1000
+#define USEC_PER_SEC 1000000
+#define NSEC_PER_USEC 1000
+#define USEC_PER_MSEC 1000
 
-struct event_entry
+/*
+ * Our timer implementation is a based on individual timers arranged in
+ * a double linked list hanging of hash containers called a timer wheel slot.
+ * For every timer a timer_entry is created and attached to the timer wheel slot.
+ * When the timer fires, the timer_cb function is called with the
+ * context pointer.
+ * The implementation supports periodic and oneshot timers.
+ * For a periodic timer the timer_period field is set to non zero,
+ * which causes the timer to run forever until manually stopped.
+ */
+struct timer_entry
 {
-  void (*function)(void *);
-  void *param;
-  float interval;
-  float since_last;
-  olsr_u8_t *trigger;
-  struct event_entry *next;
+  struct list_node timer_list; /* memory pooling, or wheel membership */
+  clock_t timer_clock; /* when timer shall fire (absolute time)*/
+  unsigned int timer_period; /* set for periodical timers (relative time) */
+  olsr_cookie_t timer_cookie; /* used for diag stuff */
+  olsr_u8_t timer_jitter_pct; /* the jitter expressed in percent */
+  olsr_u8_t timer_flags; /* misc flags */
+  unsigned int timer_random; /* cache random() result for performance reasons */
+  void (*timer_cb)(void *); /* callback function */
+  void *timer_cb_context; /* context pointer */
 };
 
-void
-signal_link_changes(olsr_bool);
-
-int
-olsr_register_timeout_function(void (*)(void), olsr_bool);
+/* inline to recast from timer_list back to timer_entry */
+LISTNODE2STRUCT(list2timer, struct timer_entry, timer_list);
 
-int
-olsr_remove_timeout_function(void (*)(void), olsr_bool);
+#define OLSR_TIMER_ONESHOT    0 /* One shot timer */
+#define OLSR_TIMER_PERIODIC   1 /* Periodic timer */
 
-int
-olsr_register_scheduler_event_dijkstra(void (*)(void *), void *, float, float, olsr_u8_t *);
+/* Timer flags */
+#define OLSR_TIMER_RUNNING  ( 1 << 0) /* this timer is running */
 
-int
-olsr_register_scheduler_event(void (*)(void *), void *, float, float, olsr_u8_t *);
+/* Memory pooling */
+#define OLSR_TIMER_MEMORY_CHUNK 100 /* timers per chunk */
 
-int
-olsr_remove_scheduler_event(void (*)(void *), void *, float, float, olsr_u8_t *);
+/* Timers */
+void olsr_init_timers(void);
+void olsr_walk_timers(clock_t *);
+void olsr_set_timer(struct timer_entry **, unsigned int, olsr_u8_t, olsr_bool,
+                    void (*)(void *), void *, olsr_cookie_t);
+struct timer_entry *olsr_start_timer(unsigned int, olsr_u8_t, olsr_bool,
+                                     void (*)(void *), void *, olsr_cookie_t);
+void olsr_change_timer(struct timer_entry *, unsigned int, olsr_u8_t, olsr_bool);
+void olsr_stop_timer(struct timer_entry *);
+const char* olsr_clock_string(clock_t);
 
-void
-scheduler(void) __attribute__((noreturn));
+/* Main scheduler loop */
+void olsr_scheduler(void) __attribute__((noreturn));
 
 #endif
+
+/*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */
index 5e433ae..ec12b85 100644 (file)
@@ -153,7 +153,7 @@ remove_olsr_socket(int fd, void(*pf)(int))
 
 
 void
-poll_sockets(void)
+olsr_poll_sockets(void)
 {
   int n;
   struct olsr_socket_entry *olsr_sockets;
@@ -195,7 +195,6 @@ poll_sockets(void)
     }
 
   /* Update time since this is much used by the parsing functions */
-  gettimeofday(&now, NULL);
   now_times = times(&tms_buf);
 
   for(olsr_sockets = olsr_socket_entries;olsr_sockets;olsr_sockets = olsr_sockets->next)
index cb87cb8..6ea4b49 100644 (file)
@@ -50,20 +50,11 @@ struct olsr_socket_entry
   struct olsr_socket_entry *next;
 };
 
-
 extern struct olsr_socket_entry *olsr_socket_entries;
+void olsr_poll_sockets(void);
 
-
-void
-add_olsr_socket(int, void(*)(int));
-
-int
-remove_olsr_socket(int, void(*)(int));
-
-void
-listen_loop(void);
-
-void
-poll_sockets(void);
+void add_olsr_socket(int, void(*)(int));
+int remove_olsr_socket(int, void(*)(int));
+void listen_loop(void);
 
 #endif
index ac53584..8ec0177 100644 (file)
@@ -169,8 +169,6 @@ olsr_init_tc(void)
 {
   OLSR_PRINTF(5, "TC: init topo\n");
 
-  olsr_register_timeout_function(&olsr_time_out_tc_set, OLSR_TRUE);
-
   avl_init(&tc_tree, avl_comp_default);
 
   /*
@@ -189,6 +187,7 @@ olsr_change_myself_tc(void)
   struct tc_edge_entry *tc_edge;
 
   if (tc_myself) {
+
     /*
      * Check if there was a change.
      */
@@ -277,7 +276,7 @@ olsr_locate_tc_entry(union olsr_ip_addr *adr)
 }
 
 /**
- * format a tc_edge contents into a buffer
+ * Format tc_edge contents into a buffer.
  */
 char *
 olsr_tc_edge_to_string(struct tc_edge_entry *tc_edge)
@@ -298,16 +297,30 @@ olsr_tc_edge_to_string(struct tc_edge_entry *tc_edge)
 }
 
 /**
+ * Wrapper for the timer callback.
+ */
+static void
+olsr_expire_tc_edge_entry(void *context)
+{
+  struct tc_edge_entry *tc_edge;
+
+  tc_edge = (struct tc_edge_entry *)context;
+  tc_edge->edge_timer = NULL;
+
+  olsr_delete_tc_edge_entry(tc_edge);
+}
+
+/**
  * Set the TC edge expiration timer.
  *
- * all timer setting shall be done using this function since
- * it does also the correct insertion and sorting in the timer tree.
+ * all timer setting shall be done using this function.
  * The timer param is a relative timer expressed in milliseconds.
  */
 void
-olsr_set_tc_edge_timer(struct tc_edge_entry *tc_edge, unsigned int timer)
+olsr_set_tc_edge_timer(struct tc_edge_entry *tc_edge, unsigned int rel_timer)
 {
-  tc_edge->T_time = GET_TIMESTAMP(timer);
+  olsr_set_timer(&tc_edge->edge_timer, rel_timer, OLSR_TC_EDGE_JITTER,
+                 OLSR_TIMER_ONESHOT, &olsr_expire_tc_edge_entry, tc_edge, 0);
 }
 
 /*
@@ -461,6 +474,12 @@ olsr_delete_tc_edge_entry(struct tc_edge_entry *tc_edge)
   avl_delete(&tc->edge_tree, &tc_edge->edge_node);
 
   /*
+   * Kill running timers.
+   */
+  olsr_stop_timer(tc_edge->edge_timer);
+  tc_edge->edge_timer = NULL;
+
+  /*
    * Clear the backpointer of our inverse edge.
    */
   tc_edge_inv = tc_edge->edge_inv;
@@ -717,30 +736,6 @@ olsr_lookup_tc_edge(struct tc_entry *tc, union olsr_ip_addr *edge_addr)
 }
 
 /**
- * Walk the timers and time out entries.
- *
- * @return nada
- */
-void
-olsr_time_out_tc_set(void)
-{
-  struct tc_entry *tc;
-
-  OLSR_FOR_ALL_TC_ENTRIES(tc) {
-    struct tc_edge_entry *tc_edge;
-    OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
-      /*
-       * Delete outdated edges.
-       */
-      if(TIMED_OUT(tc_edge->T_time)) {
-        olsr_delete_tc_edge_entry(tc_edge);
-        changes_topology = OLSR_TRUE;
-      }
-    } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge);
-  } OLSR_FOR_ALL_TC_ENTRIES_END(tc)
-}
-
-/**
  * Print the topology table to stdout
  */
 void
index e604069..a97a137 100644 (file)
@@ -46,6 +46,7 @@
 #include "packet.h"
 #include "lq_avl.h"
 #include "lq_list.h"
+#include "scheduler.h"
 
 /*
  * This file holds the definitions for the link state database.
@@ -60,7 +61,7 @@ struct tc_edge_entry
   union olsr_ip_addr T_dest_addr; /* edge_node key */
   struct tc_edge_entry *edge_inv; /* shortcut, used during SPF calculation */
   struct tc_entry    *tc; /* backpointer to owning tc entry */
-  clock_t            T_time; /* expiration timer, timer_node key */
+  struct timer_entry *edge_timer; /* expiration timer */
   olsr_u16_t         T_seq; /* sequence number of the advertised neighbor set */
   olsr_u16_t         flags; /* misc flags */
 #ifdef USE_FPM
@@ -75,6 +76,7 @@ struct tc_edge_entry
 };
 
 #define OLSR_TC_EDGE_DOWN (1 << 0) /* this edge is down */
+#define OLSR_TC_EDGE_JITTER 5 /* percent */
 
 /*
  * Garbage collection time for downed edges
index 0a11545..051f098 100644 (file)
@@ -143,7 +143,7 @@ olsr_delete_two_hop_neighbor_table(struct neighbor_2_entry *two_hop_neighbor)
 void
 olsr_insert_two_hop_neighbor_table(struct neighbor_2_entry *two_hop_neighbor)
 {
-  olsr_u32_t hash = olsr_hashing(&two_hop_neighbor->neighbor_2_addr);
+  olsr_u32_t hash = olsr_ip_hashing(&two_hop_neighbor->neighbor_2_addr);
 
   //printf("Adding 2 hop neighbor %s\n", olsr_ip_to_string(&buf, &two_hop_neighbor->neighbor_2_addr));
 
@@ -165,7 +165,7 @@ olsr_lookup_two_hop_neighbor_table(const union olsr_ip_addr *dest)
 {
 
   struct neighbor_2_entry  *neighbor_2;
-  olsr_u32_t               hash = olsr_hashing(dest);
+  olsr_u32_t               hash = olsr_ip_hashing(dest);
 
   //printf("LOOKING FOR %s\n", olsr_ip_to_string(&buf, dest));
   for(neighbor_2 = two_hop_neighbortable[hash].next;
@@ -209,7 +209,7 @@ olsr_lookup_two_hop_neighbor_table_mid(const union olsr_ip_addr *dest)
   olsr_u32_t               hash;
 
   //printf("LOOKING FOR %s\n", olsr_ip_to_string(&buf, dest));
-  hash = olsr_hashing(dest);
+  hash = olsr_ip_hashing(dest);
   
   for(neighbor_2 = two_hop_neighbortable[hash].next;
       neighbor_2 != &two_hop_neighbortable[hash];
index 0ba63f4..4ac6a62 100644 (file)
@@ -70,7 +70,6 @@
 
 #define BUFSPACE  (127*1024)   /* max. input buffer size to request */
 
-
 int
 set_flag(char *ifname, short flag __attribute__((unused)))
 {
@@ -418,7 +417,7 @@ chk_if_changed(struct olsr_if *iface)
   OLSR_PRINTF(1, "Removing interface %s\n", iface->name);
   olsr_syslog(OLSR_LOG_INFO, "Removing interface %s\n", iface->name);
 
-  del_if_link_entries(&ifp->ip_addr);
+  olsr_delete_link_entry_by_ip(&ifp->ip_addr);
 
   /*
    *Call possible ifchange functions registered by plugins  
@@ -462,51 +461,13 @@ chk_if_changed(struct olsr_if *iface)
        }
     }
 
-
   /*
-   * Deregister scheduled functions 
+   * Deregister functions for periodic message generation 
    */
-
-  if (olsr_cnf->lq_level == 0)
-    {
-      olsr_remove_scheduler_event(&generate_hello, 
-                                  ifp, 
-                                  iface->cnf->hello_params.emission_interval, 
-                                  0, 
-                                  NULL);
-      olsr_remove_scheduler_event(&generate_tc, 
-                                  ifp, 
-                                  iface->cnf->tc_params.emission_interval,
-                                  0, 
-                                  NULL);
-    }
-
-  else
-    {
-      olsr_remove_scheduler_event(&olsr_output_lq_hello, 
-                                  ifp, 
-                                  iface->cnf->hello_params.emission_interval, 
-                                  0, 
-                                  NULL);
-      olsr_remove_scheduler_event(&olsr_output_lq_tc, 
-                                  ifp, 
-                                  iface->cnf->tc_params.emission_interval,
-                                  0, 
-                                  NULL);
-    }
-
-  olsr_remove_scheduler_event(&generate_mid, 
-                             ifp, 
-                             iface->cnf->mid_params.emission_interval,
-                             0, 
-                             NULL);
-  olsr_remove_scheduler_event(&generate_hna, 
-                             ifp, 
-                             iface->cnf->hna_params.emission_interval,
-                             0, 
-                             NULL);
-
-
+  olsr_stop_timer(ifp->hello_gen_timer);
+  olsr_stop_timer(ifp->tc_gen_timer);
+  olsr_stop_timer(ifp->mid_gen_timer);
+  olsr_stop_timer(ifp->hna_gen_timer);
 
   iface->configured = 0;
   iface->interf = NULL;
@@ -658,50 +619,25 @@ add_hemu_if(struct olsr_if *iface)
   add_olsr_socket(ifp->olsr_socket, &olsr_input_hostemu);
 
 
-  if (olsr_cnf->lq_level == 0)
-    {
-      olsr_register_scheduler_event(&generate_hello, 
-                                    ifp, 
-                                    iface->cnf->hello_params.emission_interval, 
-                                    0, 
-                                    NULL);
-      olsr_register_scheduler_event(&generate_tc, 
-                                    ifp, 
-                                    iface->cnf->tc_params.emission_interval,
-                                    0, 
-                                    NULL);
-    }
-
-  else
-    {
-      olsr_register_scheduler_event(&olsr_output_lq_hello, 
-                                    ifp, 
-                                    iface->cnf->hello_params.emission_interval, 
-                                    0, 
-                                    NULL);
-      olsr_register_scheduler_event(&olsr_output_lq_tc, 
-                                    ifp, 
-                                    iface->cnf->tc_params.emission_interval,
-                                    0, 
-                                    NULL);
-    }
-
-  olsr_register_scheduler_event(&generate_mid, 
-                               ifp, 
-                               iface->cnf->mid_params.emission_interval,
-                               0, 
-                               NULL);
-  olsr_register_scheduler_event(&generate_hna, 
-                               ifp, 
-                               iface->cnf->hna_params.emission_interval,
-                               0, 
-                               NULL);
-
-  /* Recalculate max jitter */
-
-  if((olsr_cnf->max_jitter == 0) || 
-     ((iface->cnf->hello_params.emission_interval / 4) < olsr_cnf->max_jitter))
-    olsr_cnf->max_jitter = iface->cnf->hello_params.emission_interval / 4;
+  /*
+   * Register functions for periodic message generation 
+   */
+  ifp->hello_gen_timer =
+    olsr_start_timer(iface->cnf->hello_params.emission_interval * MSEC_PER_SEC,
+                     HELLO_JITTER, OLSR_TIMER_PERIODIC,
+                     olsr_cnf->lq_level == 0 ? &generate_hello : &olsr_output_lq_hello,
+                     ifp, 0);
+  ifp->tc_gen_timer =
+    olsr_start_timer(iface->cnf->tc_params.emission_interval * MSEC_PER_SEC,
+                     TC_JITTER, OLSR_TIMER_PERIODIC,
+                     olsr_cnf->lq_level == 0 ? &generate_tc : &olsr_output_lq_tc,
+                     ifp, 0);
+  ifp->mid_gen_timer =
+    olsr_start_timer(iface->cnf->mid_params.emission_interval * MSEC_PER_SEC,
+                     MID_JITTER, OLSR_TIMER_PERIODIC, &generate_mid, ifp, 0);
+  ifp->hna_gen_timer =
+    olsr_start_timer(iface->cnf->hna_params.emission_interval * MSEC_PER_SEC,
+                     HNA_JITTER, OLSR_TIMER_PERIODIC, &generate_hna, ifp, 0);
 
   /* Recalculate max topology hold time */
   if(olsr_cnf->max_tc_vtime < iface->cnf->tc_params.emission_interval)
@@ -752,6 +688,7 @@ chk_if_up(struct olsr_if *iface, int debuglvl __attribute__((unused)))
     return -1;
 
   memset(&ifr, 0, sizeof(struct ifreq));
+  memset(&ifs, 0, sizeof(struct interface));
   strncpy(ifr.ifr_name, iface->name, IFNAMSIZ);
 
   OLSR_PRINTF(debuglvl, "Checking %s:\n", ifr.ifr_name);
@@ -763,7 +700,6 @@ chk_if_up(struct olsr_if *iface, int debuglvl __attribute__((unused)))
       return 0;
     }
 
-  memset(&ifs.netbuf, 0, sizeof(struct olsr_netbuf));
   ifs.int_flags = ifr.ifr_flags;      
 
 
@@ -861,7 +797,6 @@ chk_if_up(struct olsr_if *iface, int debuglvl __attribute__((unused)))
       if(iface->cnf->ipv4_broadcast.v4.s_addr)
        {
          /* Specified broadcast */
-         memset(&ifs.int_broadaddr, 0, sizeof(struct sockaddr));
          memcpy(&((struct sockaddr_in *)&ifs.int_broadaddr)->sin_addr.s_addr, 
                 &iface->cnf->ipv4_broadcast.v4, 
                 sizeof(olsr_u32_t));
@@ -940,7 +875,8 @@ chk_if_up(struct olsr_if *iface, int debuglvl __attribute__((unused)))
 
   iface->configured = 1;
   iface->interf = ifp;
-  
+
+  /* XXX bad code */
   memcpy(ifp, &ifs, sizeof(struct interface));
   
   ifp->gen_properties = NULL;
@@ -1035,36 +971,24 @@ chk_if_up(struct olsr_if *iface, int debuglvl __attribute__((unused)))
     }
   
   /*
-   * Register scheduled functions 
+   * Register functions for periodic message generation 
    */
-
-  olsr_register_scheduler_event(olsr_cnf->lq_level == 0 ? &generate_hello : &olsr_output_lq_hello,
-                                ifp, 
-                                iface->cnf->hello_params.emission_interval, 
-                                0, 
-                                NULL);
-  olsr_register_scheduler_event(olsr_cnf->lq_level == 0 ? &generate_tc : &olsr_output_lq_tc,
-                                ifp, 
-                                iface->cnf->tc_params.emission_interval,
-                                0, 
-                                NULL);
-  olsr_register_scheduler_event(&generate_mid, 
-                               ifp, 
-                               iface->cnf->mid_params.emission_interval,
-                               0, 
-                               NULL);
-  olsr_register_scheduler_event(&generate_hna, 
-                               ifp, 
-                               iface->cnf->hna_params.emission_interval,
-                               0, 
-                               NULL);
-
-  /* Recalculate max jitter */
-
-  if((olsr_cnf->max_jitter == 0) || 
-     ((iface->cnf->hello_params.emission_interval / 4) < olsr_cnf->max_jitter)) {
-    olsr_cnf->max_jitter = iface->cnf->hello_params.emission_interval / 4;
-  }
+  ifp->hello_gen_timer =
+    olsr_start_timer(iface->cnf->hello_params.emission_interval * MSEC_PER_SEC,
+                     HELLO_JITTER, OLSR_TIMER_PERIODIC,
+                     olsr_cnf->lq_level == 0 ? &generate_hello : &olsr_output_lq_hello,
+                     ifp, 0);
+  ifp->tc_gen_timer =
+    olsr_start_timer(iface->cnf->tc_params.emission_interval * MSEC_PER_SEC,
+                     TC_JITTER, OLSR_TIMER_PERIODIC,
+                     olsr_cnf->lq_level == 0 ? &generate_tc : &olsr_output_lq_tc,
+                     ifp, 0);
+  ifp->mid_gen_timer =
+    olsr_start_timer(iface->cnf->mid_params.emission_interval * MSEC_PER_SEC,
+                     MID_JITTER, OLSR_TIMER_PERIODIC, &generate_mid, ifp, 0);
+  ifp->hna_gen_timer =
+    olsr_start_timer(iface->cnf->hna_params.emission_interval * MSEC_PER_SEC,
+                     HNA_JITTER, OLSR_TIMER_PERIODIC, &generate_hna, ifp, 0);
 
   /* Recalculate max topology hold time */
   if(olsr_cnf->max_tc_vtime < iface->cnf->tc_params.emission_interval) {
@@ -1085,4 +1009,8 @@ chk_if_up(struct olsr_if *iface, int debuglvl __attribute__((unused)))
   return 1;
 }
 
-
+/*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */
index 93a76e6..57ea038 100644 (file)
@@ -556,35 +556,13 @@ void RemoveInterface(struct olsr_if *IntConf)
     }
   }
 
-  if (olsr_cnf->lq_level == 0)
-    {
-      olsr_remove_scheduler_event(&generate_hello, Int,
-                                  IntConf->cnf->hello_params.emission_interval,
-                                  0, NULL);
-
-      olsr_remove_scheduler_event(&generate_tc, Int,
-                                  IntConf->cnf->tc_params.emission_interval,
-                                  0, NULL);
-    }
-
-  else
-    {
-      olsr_remove_scheduler_event(&olsr_output_lq_hello, Int,
-                                  IntConf->cnf->hello_params.emission_interval,
-                                  0, NULL);
-
-      olsr_remove_scheduler_event(&olsr_output_lq_tc, Int,
-                                  IntConf->cnf->tc_params.emission_interval,
-                                  0, NULL);
-    }
-
-  olsr_remove_scheduler_event(&generate_mid, Int,
-                              IntConf->cnf->mid_params.emission_interval,
-                              0, NULL);
-
-  olsr_remove_scheduler_event(&generate_hna, Int,
-                              IntConf->cnf->hna_params.emission_interval,
-                              0, NULL);
+  /*
+   * Deregister functions for periodic message generation 
+   */
+  olsr_stop_timer(Int->hello_gen_timer);
+  olsr_stop_timer(Int->tc_gen_timer);
+  olsr_stop_timer(Int->mid_gen_timer);
+  olsr_stop_timer(Int->hna_gen_timer);
 
   net_remove_buffer(Int);
 
@@ -723,51 +701,25 @@ int add_hemu_if(struct olsr_if *iface)
   /* Register socket */
   add_olsr_socket(ifp->olsr_socket, &olsr_input_hostemu);
 
-
-  if (olsr_cnf->lq_level == 0)
-    {
-      olsr_register_scheduler_event(&generate_hello, 
-                                    ifp, 
-                                    iface->cnf->hello_params.emission_interval, 
-                                    0, 
-                                    NULL);
-      olsr_register_scheduler_event(&generate_tc, 
-                                    ifp, 
-                                    iface->cnf->tc_params.emission_interval,
-                                    0, 
-                                    NULL);
-    }
-
-  else
-    {
-      olsr_register_scheduler_event(&olsr_output_lq_hello, 
-                                    ifp, 
-                                    iface->cnf->hello_params.emission_interval, 
-                                    0, 
-                                    NULL);
-      olsr_register_scheduler_event(&olsr_output_lq_tc, 
-                                    ifp, 
-                                    iface->cnf->tc_params.emission_interval,
-                                    0, 
-                                    NULL);
-    }
-
-  olsr_register_scheduler_event(&generate_mid, 
-                               ifp, 
-                               iface->cnf->mid_params.emission_interval,
-                               0, 
-                               NULL);
-  olsr_register_scheduler_event(&generate_hna, 
-                               ifp, 
-                               iface->cnf->hna_params.emission_interval,
-                               0, 
-                               NULL);
-
-  /* Recalculate max jitter */
-
-  if((olsr_cnf->max_jitter == 0) || 
-     ((iface->cnf->hello_params.emission_interval / 4) < olsr_cnf->max_jitter))
-    olsr_cnf->max_jitter = iface->cnf->hello_params.emission_interval / 4;
+  /*
+   * Register functions for periodic message generation 
+   */
+  ifp->hello_gen_timer =
+    olsr_start_timer(iface->cnf->hello_params.emission_interval * MSEC_PER_SEC,
+                     HELLO_JITTER, OLSR_TIMER_PERIODIC,
+                     olsr_cnf->lq_level == 0 ? &generate_hello : &olsr_output_lq_hello,
+                     ifp, 0);
+  ifp->tc_gen_timer =
+    olsr_start_timer(iface->cnf->tc_params.emission_interval * MSEC_PER_SEC,
+                     TC_JITTER, OLSR_TIMER_PERIODIC,
+                     olsr_cnf->lq_level == 0 ? &generate_tc : &olsr_output_lq_tc,
+                     ifp, 0);
+  ifp->mid_gen_timer =
+    olsr_start_timer(iface->cnf->mid_params.emission_interval * MSEC_PER_SEC,
+                     MID_JITTER, OLSR_TIMER_PERIODIC, &generate_mid, ifp, 0);
+  ifp->hna_gen_timer =
+    olsr_start_timer(iface->cnf->hna_params.emission_interval * MSEC_PER_SEC,
+                     HNA_JITTER, OLSR_TIMER_PERIODIC, &generate_hna, ifp, 0);
 
   /* Recalculate max topology hold time */
   if(olsr_cnf->max_tc_vtime < iface->cnf->tc_params.emission_interval)
@@ -1046,39 +998,25 @@ int chk_if_up(struct olsr_if *IntConf, int DebugLevel __attribute__((unused)))
 
   net_add_buffer(New);
 
-  if (olsr_cnf->lq_level == 0)
-  {
-    olsr_register_scheduler_event(&generate_hello, New,
-                                  IntConf->cnf->hello_params.emission_interval,
-                                  0, NULL);
-
-    olsr_register_scheduler_event(&generate_tc, New,
-                                  IntConf->cnf->tc_params.emission_interval,
-                                  0, NULL);
-  }
-
-  else
-  {
-    olsr_register_scheduler_event(&olsr_output_lq_hello, New,
-                                  IntConf->cnf->hello_params.emission_interval,
-                                  0, NULL);
-
-    olsr_register_scheduler_event(&olsr_output_lq_tc, New,
-                                  IntConf->cnf->tc_params.emission_interval,
-                                  0, NULL);
-  }
-
-  olsr_register_scheduler_event(&generate_mid, New,
-                                IntConf->cnf->mid_params.emission_interval,
-                                0, NULL);
-
-  olsr_register_scheduler_event(&generate_hna, New,
-                                IntConf->cnf->hna_params.emission_interval,
-                                0, NULL);
-
-  if(olsr_cnf->max_jitter == 0 ||
-     IntConf->cnf->hello_params.emission_interval / 4 < olsr_cnf->max_jitter)
-    olsr_cnf->max_jitter = IntConf->cnf->hello_params.emission_interval / 4;
+  /*
+   * Register functions for periodic message generation 
+   */
+  New->hello_gen_timer =
+    olsr_start_timer(iface->cnf->hello_params.emission_interval * MSEC_PER_SEC,
+                     HELLO_JITTER, OLSR_TIMER_PERIODIC,
+                     olsr_cnf->lq_level == 0 ? &generate_hello : &olsr_output_lq_hello,
+                     New, 0);
+  New->tc_gen_timer =
+    olsr_start_timer(iface->cnf->tc_params.emission_interval * MSEC_PER_SEC,
+                     TC_JITTER, OLSR_TIMER_PERIODIC,
+                     olsr_cnf->lq_level == 0 ? &generate_tc : &olsr_output_lq_tc,
+                     New, 0);
+  New->mid_gen_timer =
+    olsr_start_timer(iface->cnf->mid_params.emission_interval * MSEC_PER_SEC,
+                     MID_JITTER, OLSR_TIMER_PERIODIC, &generate_mid, New, 0);
+  New->hna_gen_timer =
+    olsr_start_timer(iface->cnf->hna_params.emission_interval * MSEC_PER_SEC,
+                     HNA_JITTER, OLSR_TIMER_PERIODIC, &generate_hna, New, 0);
 
   if(olsr_cnf->max_tc_vtime < IntConf->cnf->tc_params.emission_interval)
     olsr_cnf->max_tc_vtime = IntConf->cnf->tc_params.emission_interval;