* applied rt-refactoring-6.diff from Hannes Gredler <hannes@gredler.at>
authorBernd Petrovitsch <bernd@firmix.at>
Wed, 5 Sep 2007 16:11:11 +0000 (16:11 +0000)
committerBernd Petrovitsch <bernd@firmix.at>
Wed, 5 Sep 2007 16:11:11 +0000 (16:11 +0000)
28 files changed:
lib/httpinfo/src/olsrd_httpinfo.c
lib/nameservice/src/nameservice.c
lib/nameservice/src/nameservice.h
lib/quagga/src/quagga.c
lib/tas/src/plugin.c
lib/txtinfo/src/olsrd_txtinfo.c
src/bsd/kernel_routes.c
src/hna_set.c
src/hna_set.h
src/ipc_frontend.c
src/kernel_routes.h
src/linux/kernel_routes.c
src/lq_avl.c
src/lq_avl.h
src/lq_list.c
src/lq_list.h
src/lq_route.c
src/lq_route.h
src/main.c
src/net_olsr.c
src/net_olsr.h
src/olsr.c
src/olsr_types.h
src/process_routes.c
src/process_routes.h
src/routing_table.c
src/routing_table.h
src/win32/kernel_routes.c

index ea5c25f..73af0a8 100644 (file)
@@ -36,7 +36,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: olsrd_httpinfo.c,v 1.71 2007/07/15 21:09:37 bernd67 Exp $
+ * $Id: olsrd_httpinfo.c,v 1.72 2007/09/05 16:11:10 bernd67 Exp $
  */
 
 /*
@@ -150,8 +150,6 @@ static int build_neigh_body(char *, olsr_u32_t);
 
 static int build_topo_body(char *, olsr_u32_t);
 
-static int build_hna_body(char *, olsr_u32_t);
-
 static int build_mid_body(char *, olsr_u32_t);
 
 static int build_nodes_body(char *, olsr_u32_t);
@@ -164,11 +162,12 @@ static int build_cfgfile_body(char *, olsr_u32_t);
 
 static int check_allowed_ip(const struct allowed_net * const allowed_nets, const union olsr_ip_addr * const addr);
 
-static int build_ip_txt(char *buf, const olsr_u32_t bufsize, const olsr_bool want_link, const char * const ipstr, const char  * const maskstr);
-
-static int build_ipaddr_link(char *buf, const olsr_u32_t bufsize, const olsr_bool want_link, const union olsr_ip_addr * const ipaddr, const union hna_netmask * const mask);
+static int build_ip_txt(char *buf, const olsr_u32_t bufsize, const olsr_bool want_link,
+                        const union olsr_ip_addr * const ipaddr, const int prefix_len);
 
-static char *olsr_netmask_to_string(union hna_netmask *);
+static int build_ipaddr_link(char *buf, const olsr_u32_t bufsize, const olsr_bool want_link,
+                             const union olsr_ip_addr * const ipaddr,
+                             const int prefix_len);
 
 static ssize_t writen(int fd, const void *buf, size_t count);
 
@@ -679,60 +678,52 @@ static int build_frame(char *title __attribute__((unused)),
   return size;
 }
 
-static int build_ip_txt(char *buf, const olsr_u32_t bufsize, const olsr_bool want_link, const char * const ipstr, const char  * const maskstr)
+static int build_ip_txt(char *buf, const olsr_u32_t bufsize, const olsr_bool want_link,
+                        const union olsr_ip_addr * const ipaddr, const int prefix_len)
 {
   int size = 0;
-  if (want_link && maskstr == NULL) { /* Print the link only if there is not netmask */
+  if (want_link && prefix_len == -1) { /* Print the link only if there is no prefix_len */
     size += snprintf(&buf[size],
                      bufsize-size,
                      "<a href=\"http://%s:%d/all\">",
-                     ipstr,
+                     olsr_ip_to_string(ipaddr),
                      http_port);
   }
-  size += snprintf(&buf[size], bufsize-size, "%s", ipstr);
-  if (maskstr) {
-    size += snprintf(&buf[size], bufsize-size, "/%s", maskstr);
+
+  /* print ip address or ip prefix ? */
+  if (prefix_len == -1) {
+      size += snprintf(&buf[size], bufsize-size, "%s", olsr_ip_to_string(ipaddr));
+  } else {
+      size += snprintf(&buf[size], bufsize-size, "%s/%d", olsr_ip_to_string(ipaddr),
+                       prefix_len);
   }
-  if (want_link && maskstr == NULL) { /* Print the link only if there is not netmask */
+  
+  if (want_link && prefix_len == -1) { /* Print the link only if there is no prefix_len */
     size += snprintf(&buf[size], bufsize-size, "</a>");
   }
   return size;
 }
 
-static int build_ipaddr_link(char *buf, const olsr_u32_t bufsize, const olsr_bool want_link, const union olsr_ip_addr * const ipaddr, const union hna_netmask * const mask)
+static int build_ipaddr_link(char *buf, const olsr_u32_t bufsize,
+                             const olsr_bool want_link,
+                             const union olsr_ip_addr * const ipaddr,
+                             const int prefix_len)
 {
   int size = 0;
-  char maskbuf[32];
-  char *maskstr;
   const struct hostent * const hp =
 #ifndef WIN32
-                                    resolve_ip_addresses ? gethostbyaddr(ipaddr, olsr_cnf->ipsize, olsr_cnf->ip_version) :
+      resolve_ip_addresses ? gethostbyaddr(ipaddr, olsr_cnf->ipsize, olsr_cnf->ip_version) :
 #endif
-                                        NULL;
-  if (mask != NULL) {
-    if (olsr_cnf->ip_version == AF_INET) {
-      if (mask->v4 == ~0U) {
-        maskstr = NULL;
-      } else {
-        struct in_addr in;
-        in.s_addr = mask->v4;
-        snprintf(maskbuf, sizeof(maskbuf), "%s", inet_ntoa(in));
-        maskstr = maskbuf;
-      }
-    } else {
-      snprintf(maskbuf, sizeof(maskbuf), "%d", mask->v6);
-      maskstr = maskbuf;
-    }
-  } else {
-    maskstr =  NULL;
-  }
+      NULL;
+
   size += snprintf(&buf[size], bufsize-size, "<td>");
-  size += build_ip_txt(&buf[size], bufsize-size, want_link, olsr_ip_to_string(ipaddr), maskstr);
+  size += build_ip_txt(&buf[size], bufsize-size, want_link, ipaddr, prefix_len);
   size += snprintf(&buf[size], bufsize-size, "</td>");
+
   if (resolve_ip_addresses) {
     if (hp) {
       size += snprintf(&buf[size], bufsize-size, "<td>(");
-      size += build_ip_txt(&buf[size], bufsize-size, want_link, hp->h_name, NULL);
+      size += snprintf(&buf[size], bufsize-size, "%s", hp->h_name);
       size += snprintf(&buf[size], bufsize-size, ")</td>");
     } else {
       size += snprintf(&buf[size], bufsize-size, "<td/>");
@@ -740,51 +731,48 @@ static int build_ipaddr_link(char *buf, const olsr_u32_t bufsize, const olsr_boo
   }
   return size;
 }
-#define build_ipaddr_with_link(buf, bufsize, ipaddr, mask) build_ipaddr_link((buf), (bufsize), OLSR_TRUE, (ipaddr), (mask))
-#define build_ipaddr_no_link(buf, bufsize, ipaddr, mask)   build_ipaddr_link((buf), (bufsize), OLSR_FALSE, (ipaddr), (mask))
 
+#define build_ipaddr_with_link(buf, bufsize, ipaddr, plen) \
+          build_ipaddr_link((buf), (bufsize), OLSR_TRUE, (ipaddr), (plen))
+#define build_ipaddr_no_link(buf, bufsize, ipaddr, plen) \
+          build_ipaddr_link((buf), (bufsize), OLSR_FALSE, (ipaddr), (plen))
 
-static int build_route(char *buf, olsr_u32_t bufsize, const struct rt_entry * const route, const char * const title, const int print_netmask)
+static int build_route(char *buf, olsr_u32_t bufsize, const struct rt_entry * rt)
 {
   int size = 0;
-  size += snprintf(&buf[size], bufsize-size, "<tr>");
-  size += build_ipaddr_with_link(&buf[size], bufsize-size, &route->rt_dst, print_netmask ? &route->rt_mask : NULL);
-  size += build_ipaddr_with_link(&buf[size], bufsize-size, &route->rt_router, NULL);
 
-  size += snprintf(&buf[size], bufsize-size, "<td align=\"center\">%d</td>", route->rt_metric);
-  if (olsr_cnf->lq_level > 0) {
-    size += snprintf(&buf[size], bufsize-size, "<td align=\"center\">%.2f</td>", route->rt_etx);
-  }
-  size += snprintf(&buf[size], bufsize-size, "<td align=\"center\">%s</td><td>%s</td></tr>\n", route->rt_if->int_name, title);
+  size += snprintf(&buf[size], bufsize-size, "<tr>");
+  size += build_ipaddr_with_link(&buf[size], bufsize-size, &rt->rt_dst.prefix,
+                                 rt->rt_dst.prefix_len);
+  size += build_ipaddr_with_link(&buf[size], bufsize-size,
+                                 &rt->rt_best->rtp_nexthop.gateway, -1);
+
+  size += snprintf(&buf[size], bufsize-size, "<td align=\"center\">%d</td>",
+                   rt->rt_best->rtp_metric.hops);
+  size += snprintf(&buf[size], bufsize-size, "<td align=\"center\">%.3f</td>",
+                     rt->rt_best->rtp_metric.etx);
+  size += snprintf(&buf[size], bufsize-size, "<td align=\"center\">%s</td></tr>\n",
+                   rt->rt_best->rtp_nexthop.iface->int_name);
   return size;
 }
 
 static int build_routes_body(char *buf, olsr_u32_t bufsize)
 {
-  int size = 0, index;
-  struct rt_entry *routes;
+  int size = 0;
+  struct rt_entry *rt;
 
   size += snprintf(&buf[size], bufsize-size, "<h2>OLSR routes in kernel</h2>\n");
 
   size += snprintf(&buf[size], bufsize-size, "<table width=\"100%%\" border=\"0\" cellspacing=\"0\" cellpadding=\"0\" align=\"center\"><tr><th%1$s>Destination</th><th%1$s>Gateway</th><th>Metric</th>",
                   resolve_ip_addresses ? " colspan=\"2\"" : "");
-  if (olsr_cnf->lq_level > 0)
-    size += snprintf(&buf[size], bufsize-size, "<th>ETX</th>");
-  size += snprintf(&buf[size], bufsize-size, "<th>Interface</th><th>Type</th></tr>\n");
 
-  /* Neighbors */
-  for(index = 0;index < HASHSIZE;index++) {
-    for(routes = routingtable[index].next; routes != &routingtable[index]; routes = routes->next) {
-      size += build_route(&buf[size], bufsize-size, routes, "HOST", OLSR_FALSE);
-    }
-  }
+  size += snprintf(&buf[size], bufsize-size, "<th>ETX</th>");
+  size += snprintf(&buf[size], bufsize-size, "<th>Interface</th></tr>\n");
 
-  /* HNA */
-  for(index = 0;index < HASHSIZE;index++) {
-    for(routes = hna_routes[index].next; routes != &hna_routes[index];routes = routes->next) {
-      size += build_route(&buf[size], bufsize-size, routes, "HNA", OLSR_TRUE);
-    }
-  }
+  /* Walk the route table */
+  OLSR_FOR_ALL_RT_ENTRIES(rt) {
+      size += build_route(&buf[size], bufsize-size, rt);
+  } OLSR_FOR_ALL_RT_ENTRIES_END(rt);
 
   size += snprintf(&buf[size], bufsize-size, "</table>\n");
 
@@ -1004,8 +992,8 @@ static int build_neigh_body(char *buf, olsr_u32_t bufsize)
     while(link)
       {
         size += snprintf(&buf[size], bufsize-size, "<tr>");
-        size += build_ipaddr_no_link(&buf[size], bufsize, &link->local_iface_addr, NULL);
-        size += build_ipaddr_with_link(&buf[size], bufsize, &link->neighbor_iface_addr, NULL);
+        size += build_ipaddr_no_link(&buf[size], bufsize, &link->local_iface_addr, -1);
+        size += build_ipaddr_with_link(&buf[size], bufsize, &link->neighbor_iface_addr, -1);
        size += snprintf(&buf[size], bufsize-size,
                        "<td align=\"right\">%0.2f</td>",
                        link->L_link_quality);
@@ -1040,7 +1028,7 @@ static int build_neigh_body(char *buf, olsr_u32_t bufsize)
          neigh = neigh->next)
        {
           size += snprintf(&buf[size], bufsize-size, "<tr>");
-          size += build_ipaddr_with_link(&buf[size], bufsize, &neigh->neighbor_main_addr, NULL);
+          size += build_ipaddr_with_link(&buf[size], bufsize, &neigh->neighbor_main_addr, -1);
          size += snprintf(&buf[size], bufsize-size, 
                          "<td>%s</td>"
                          "<td>%s</td>"
@@ -1099,8 +1087,8 @@ static int build_topo_body(char *buf, olsr_u32_t bufsize)
          while(dst_entry != &entry->destinations)
            {
               size += snprintf(&buf[size], bufsize-size, "<tr>");
-              size += build_ipaddr_with_link(&buf[size], bufsize, &dst_entry->T_dest_addr, NULL);
-              size += build_ipaddr_with_link(&buf[size], bufsize, &entry->T_last_addr, NULL);
+              size += build_ipaddr_with_link(&buf[size], bufsize, &dst_entry->T_dest_addr, -1);
+              size += build_ipaddr_with_link(&buf[size], bufsize, &entry->T_last_addr, -1);
               if (olsr_cnf->lq_level > 0)
                 {
                   const double d = dst_entry->link_quality * dst_entry->inverse_link_quality;
@@ -1125,47 +1113,6 @@ static int build_topo_body(char *buf, olsr_u32_t bufsize)
   return size;
 }
 
-static int build_hna_body(char *buf, olsr_u32_t bufsize)
-{
-  int size;
-  olsr_u8_t index;
-  struct hna_entry *tmp_hna;
-  struct hna_net *tmp_net;
-
-  size = 0;
-
-  size += snprintf(&buf[size], bufsize-size, "<h2>HNA entries</h2>\n<table width=\"100%%\" BORDER=0 CELLSPACING=0 CELLPADDING=0 ALIGN=center><tr><th>Network</th><th>Netmask</th><th>Gateway</th></tr>\n");
-
-  /* HNA entries */
-  for(index=0;index<HASHSIZE;index++)
-    {
-      tmp_hna = hna_set[index].next;
-      /* Check all entrys */
-      while(tmp_hna != &hna_set[index])
-       {
-         /* Check all networks */
-         tmp_net = tmp_hna->networks.next;
-             
-         while(tmp_net != &tmp_hna->networks)
-           {
-              size += snprintf(&buf[size], bufsize-size, "<tr>");
-              size += build_ipaddr_no_link(&buf[size], bufsize, &tmp_net->A_network_addr, NULL);
-             size += snprintf(&buf[size], bufsize-size, "<td>%s</td>",
-                             olsr_netmask_to_string(&tmp_net->A_netmask));
-              size += build_ipaddr_with_link(&buf[size], bufsize, &tmp_hna->A_gateway_addr, NULL);
-             tmp_net = tmp_net->next;
-           }
-             
-         tmp_hna = tmp_hna->next;
-       }
-    }
-
-  size += snprintf(&buf[size], bufsize-size, "</table>\n");
-
-  return size;
-}
-
-
 static int build_mid_body(char *buf, olsr_u32_t bufsize)
 {
   int size = 0;
@@ -1182,7 +1129,7 @@ static int build_mid_body(char *buf, olsr_u32_t bufsize)
           int mid_cnt;
           struct mid_address *alias;
           size += snprintf(&buf[size], bufsize-size, "<tr>");
-          size += build_ipaddr_with_link(&buf[size], bufsize, &entry->main_addr, NULL);
+          size += build_ipaddr_with_link(&buf[size], bufsize, &entry->main_addr, -1);
          size += snprintf(&buf[size], bufsize-size, "<td><select>\n<option>IP ADDRESS</option>\n");
 
          alias = entry->aliases;
@@ -1209,7 +1156,6 @@ static int build_nodes_body(char *buf, olsr_u32_t bufsize)
 
   size += build_neigh_body(&buf[size], bufsize-size);
   size += build_topo_body(&buf[size], bufsize-size);
-  size += build_hna_body(&buf[size], bufsize-size);
   size += build_mid_body(&buf[size], bufsize-size);
 
   return size;
@@ -1223,7 +1169,6 @@ static int build_all_body(char *buf, olsr_u32_t bufsize)
   size += build_routes_body(&buf[size], bufsize-size);
   size += build_neigh_body(&buf[size], bufsize-size);
   size += build_topo_body(&buf[size], bufsize-size);
-  size += build_hna_body(&buf[size], bufsize-size);
   size += build_mid_body(&buf[size], bufsize-size);
 
   return size;
@@ -1289,26 +1234,6 @@ static int check_allowed_ip(const struct allowed_net * const allowed_nets, const
 
 
 
-/**
- *This function is just as bad as the previous one :-(
- */
-static char *olsr_netmask_to_string(union hna_netmask *mask)
-{
-  char *ret;
-  if(olsr_cnf->ip_version == AF_INET) {
-      struct in_addr in;
-      in.s_addr = mask->v4;
-      ret = inet_ntoa(in);
-  } else {
-      static char netmask[5];
-      /* IPv6 */
-      snprintf(netmask, sizeof(netmask), "%d", mask->v6);
-      ret = netmask;
-  }
-  return ret;
-}
-
-
 #if 0
 /*
  * In a bigger mesh, there are probs with the fixed
index 7196588..47a93a5 100644 (file)
@@ -31,7 +31,7 @@
  *
  */
 
-/* $Id: nameservice.c,v 1.27 2007/08/28 20:45:17 bernd67 Exp $ */
+/* $Id: nameservice.c,v 1.28 2007/09/05 16:11:10 bernd67 Exp $ */
 
 /*
  * Dynamic linked library for UniK OLSRd
@@ -99,18 +99,15 @@ olsr_bool forwarder_table_changed = OLSR_TRUE;
 struct db_entry* latlon_list[HASHSIZE];
 olsr_bool latlon_table_changed = OLSR_TRUE;
 
-/* regualar expression to be matched by valid hostnames, compiled in name_init() */
+/* regular expression to be matched by valid hostnames, compiled in name_init() */
 regex_t regex_t_name;
 regmatch_t regmatch_t_name;
 
-/* regualar expression to be matched by valid service_lines, compiled in name_init() */
+/* regular expression to be matched by valid service_lines, compiled in name_init() */
 regex_t regex_t_service;
 int pmatch_service = 10;
 regmatch_t regmatch_t_service[10];
 
-static void free_routing_table_list(struct rt_entry **list) ;
-static struct rt_entry *host_lookup_routing_table(union olsr_ip_addr *);
-
 /**
  * do initialization
  */
@@ -836,7 +833,7 @@ decap_namemsg(struct name *from_packet, struct name_entry **to, olsr_bool *this_
 
 
 /**
- * unpack the received message and delegate to the decapsilation function for each
+ * unpack the received message and delegate to the decapsulation function for each
  * name/service/forwarder entry in the message
  */
 void
@@ -1076,6 +1073,44 @@ write_services_file(void)
 }
 
 /**
+ * Sort the nameserver pointer array.
+ *
+ * fresh entries are at the beginning of the array and
+ * the best entry is at the end of the array.
+ */
+static void
+select_best_nameserver(struct rt_entry **rt)
+{
+    int nameserver_idx;
+    struct rt_entry *rt1, *rt2;
+
+    for (nameserver_idx = 0;
+         nameserver_idx < NAMESERVER_COUNT;
+         nameserver_idx++) {
+
+        rt1 = rt[nameserver_idx];
+        rt2 = rt[nameserver_idx+1];
+
+        /*
+         * compare the next two pointers in the array.
+         * if the second pointer is NULL then percolate it up.
+         */
+        if (!rt2 || olsr_cmp_rt(rt1, rt2)) {
+
+            /*
+             * first is better, swap the pointers.
+             */
+            OLSR_PRINTF(6, "NAME PLUGIN: nameserver %s, etx %.3f\n",
+                        olsr_ip_to_string(&rt1->rt_dst.prefix),
+                        rt1->rt_best->rtp_metric.etx);
+
+            rt[nameserver_idx] = rt2;
+            rt[nameserver_idx+1] = rt1;
+        }
+    }
+}
+
+/**
  * write the 3 best upstream DNS servers to resolv.conf file
  * best means the 3 with the best etx value in routing table
  */
@@ -1083,88 +1118,50 @@ void
 write_resolv_file(void)
 {
        int hash;
-       struct name_entry *name, *tmp_dns, *last_dns, *dnslist = NULL;
+       struct name_entry *name;
        struct db_entry *entry;
-       struct rt_entry *best_routes = NULL;
-       struct rt_entry *route, *tmp = NULL, *last;
+       struct rt_entry *route;
+    static struct rt_entry *nameserver_routes[NAMESERVER_COUNT+1];
        FILE* resolv;
        int i=0;
        time_t currtime;
-       
+
        if (!forwarder_table_changed || my_forwarders != NULL || my_resolv_file[0] == '\0')
                return;
 
+    /* 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) 
                        {
-                               
-                               /* find the nearest one */
-                               route = host_lookup_routing_table(&name->ip);
+
+                               route = olsr_lookup_routing_table(&name->ip);
+
+                OLSR_PRINTF(6, "NAME PLUGIN: check route for nameserver %s %s",
+                                                       olsr_ip_to_string(&name->ip),
+                            route ? "suceeded" : "failed");
+
                                if (route==NULL) // it's possible that route is not present yet
                                        continue;
-                               
-                               if (best_routes == NULL || route->rt_etx < best_routes->rt_etx) {
-                                       OLSR_PRINTF(6, "NAME PLUGIN: best nameserver %s\n",
-                                               olsr_ip_to_string(&name->ip));
-                                       if (best_routes!=NULL)
-                                               OLSR_PRINTF(6, "NAME PLUGIN: better than %f (%s)\n",
-                                                       best_routes->rt_etx,
-                                                       olsr_ip_to_string(&best_routes->rt_dst));
-                                       
-                                       tmp = olsr_malloc(sizeof(struct rt_entry), "new rt_entry");
-                                       memcpy(&tmp->rt_dst, &route->rt_dst, olsr_cnf->ipsize);
-                                       tmp->rt_etx = route->rt_etx;
-                                       tmp->next = best_routes;
-                                       best_routes = tmp;
-                                       tmp_dns = olsr_malloc(sizeof(struct name_entry), "write_resolv name_entry");
-                                       COPY_IP(&tmp_dns->ip, &name->ip);
-                                       tmp_dns->type = name->type;
-                                       tmp_dns->len = 0;
-                                       tmp_dns->name = NULL;
-                                       tmp_dns->next = dnslist;
-                                       dnslist = tmp_dns;
-                               } else {
-                                       // queue in etx order
-                                       last = best_routes;
-                                       last_dns = dnslist;
-                                       while ( last->next!=NULL && i<3 ) {
-                                               if (last->next->rt_etx > route->rt_etx)
-                                                       break;
-                                               last = last->next;
-                                               last_dns = last_dns->next;
-                                               i++;
-                                       }
-                                       if (i<3) {
-                                               OLSR_PRINTF(6, "NAME PLUGIN: queue %f (%s)",
-                                                       route->rt_etx,
-                                                       olsr_ip_to_string(&name->ip));
-                                               OLSR_PRINTF(6, " after %f (%s)\n", 
-                                                       last->rt_etx, olsr_ip_to_string(&last_dns->ip));
-                                               
-                                               tmp = olsr_malloc(sizeof(struct rt_entry), "new rt_entry");
-                                               memcpy(&tmp->rt_dst, &route->rt_dst, olsr_cnf->ipsize);
-                                               tmp->rt_etx = route->rt_etx;
-                                               tmp->next = last->next;
-                                               last->next = tmp;
-
-                                               tmp_dns = olsr_malloc(sizeof(struct name_entry), "write_resolv name_entry");
-                                               COPY_IP(&tmp_dns->ip, &name->ip);
-                                               tmp_dns->type = name->type;
-                                               tmp_dns->len = 0;
-                                               tmp_dns->name = NULL;
-                                               tmp_dns->next = last_dns->next;
-                                               last_dns->next = tmp_dns;
-                                       } else {
-                                               OLSR_PRINTF(6, "NAME PLUGIN: don't need more than 3 nameservers\n");
-                                       }
-                               }
+
+                /* enqueue it on the head of list */
+                *nameserver_routes = route;
+                OLSR_PRINTF(6, "NAME PLUGIN: found nameserver %s, etx %.3f",
+                                                       olsr_ip_to_string(&name->ip),
+                            route->rt_best->rtp_metric.etx);
+
+                /* find the closet one */
+                select_best_nameserver(nameserver_routes);
                        }
                }
        }
-       if (best_routes==NULL)
+
+    /* if there is no best route we are done */
+       if (nameserver_routes[NAMESERVER_COUNT]==NULL)
                return;
                 
        /* write to file */
@@ -1176,15 +1173,21 @@ write_resolv_file(void)
        }
        fprintf(resolv, "### this file is overwritten regularly by olsrd\n");
        fprintf(resolv, "### do not edit\n\n");
-       i=0;
-       for (tmp_dns=dnslist; tmp_dns!=NULL && i<3; tmp_dns=tmp_dns->next) {
-               OLSR_PRINTF(6, "NAME PLUGIN: nameserver %s\n", olsr_ip_to_string(&tmp_dns->ip));
-               fprintf(resolv, "nameserver %s\n", olsr_ip_to_string(&tmp_dns->ip));
-               i++;
-       }
-       free_name_entry_list(&dnslist);
-       if(tmp != NULL) {
-               free_routing_table_list(&tmp);
+
+       for (i = NAMESERVER_COUNT; i >= 0; i--) {
+
+        route = nameserver_routes[i];
+
+        OLSR_PRINTF(2, "NAME PLUGIN: nameserver_routes #%d %p\n", i, route);
+
+        if (!route) {
+            continue;
+        }
+
+               OLSR_PRINTF(2, "NAME PLUGIN: nameserver %s\n",
+                    olsr_ip_to_string(&route->rt_dst.prefix));
+               fprintf(resolv, "nameserver %s\n",
+                olsr_ip_to_string(&route->rt_dst.prefix));
        }
        if (time(&currtime)) {
                fprintf(resolv, "\n### written by olsrd at %s", ctime(&currtime));
@@ -1214,23 +1217,6 @@ free_name_entry_list(struct name_entry **list)
 
 
 /**
- * completely free a list of rt_entries
- */
-static void 
-free_routing_table_list(struct rt_entry **list) 
-{
-       struct rt_entry **tmp = list;
-       struct rt_entry *to_delete;
-       while (*tmp != NULL) {
-               to_delete = *tmp;
-               *tmp = (*tmp)->next;
-               free( to_delete );
-               to_delete = NULL;
-       }
-}
-
-
-/**
  * we only allow names for IP addresses which we are
  * responsible for: 
  * so the IP must either be from one of the interfaces
@@ -1292,51 +1278,6 @@ allowed_ip(union olsr_ip_addr *addr)
        return OLSR_FALSE;
 }
 
-static struct rt_entry *
-host_lookup_routing_table(union olsr_ip_addr *dst)
-{
-       olsr_u32_t index;
-       union olsr_ip_addr tmp_ip, tmp_msk;
-       struct rt_entry *walker;
-
-       walker = olsr_lookup_routing_table(dst);
-       if (walker != NULL)
-               return walker;
-
-       for (index = 0; index < HASHSIZE; index++) {
-               for (walker = hna_routes[index].next;
-                  walker != &hna_routes[index]; walker = walker->next) {
-                       if (COMP_IP(&walker->rt_dst, dst))
-                               return walker;
-                       if (olsr_cnf->ip_version == AF_INET) {
-                               if ( walker->rt_mask.v4 != 0 &&
-                                   (dst->v4 & walker->rt_mask.v4) ==
-                                   walker->rt_dst.v4 ) {
-                                       OLSR_PRINTF(6, "MATCHED\n");
-                                       return walker;
-                               }
-                       } else {
-                               int i;
-                               
-                               if ( walker->rt_mask.v6 == 0 )
-                                       continue;
-                               olsr_prefix_to_netmask(&tmp_msk,
-                                       walker->rt_mask.v6);
-                               for (i = 0; i < 16; i++) {
-                                       tmp_ip.v6.s6_addr[i] =
-                                               dst->v6.s6_addr[i] &
-                                               tmp_msk.v6.s6_addr[i];
-                               }
-                               if (COMP_IP(&tmp_ip, &walker->rt_dst)) {
-                                       OLSR_PRINTF(6, "MATCHED\n");
-                                       return walker;
-                               }
-                       }
-               }
-       }
-       return NULL;
-}
-
 /** check if name has the right syntax, i.e. it must adhere to a special regex 
  * stored in regex_t_name
  * necessary to avaid names like "0.0.0.0 google.de\n etc"
@@ -1461,9 +1402,9 @@ void lookup_defhna_latlon(union olsr_ip_addr *ip)
        struct rt_entry* rt_hna;
        memset(ip, 0, sizeof(ip));
        memset(&dest, 0, sizeof(dest));
-       if (NULL != (rt_hna = olsr_lookup_hna_routing_table(&dest)))
+       if (NULL != (rt_hna = olsr_lookup_routing_table(&dest)))
        {
-               COPY_IP(ip, &rt_hna->rt_router);
+               COPY_IP(ip, &rt_hna->rt_best->rtp_nexthop.gateway);
        }
 }
 
index 696b899..c3cd4c3 100644 (file)
@@ -29,7 +29,7 @@
  *
  */
 
-/* $Id: nameservice.h,v 1.12 2007/07/02 10:59:12 bernd67 Exp $ */
+/* $Id: nameservice.h,v 1.13 2007/09/05 16:11:10 bernd67 Exp $ */
  
 /*
  * Dynamic linked library for UniK OLSRd
@@ -60,6 +60,7 @@
 #define PARSER_TYPE            MESSAGE_TYPE
 #define EMISSION_INTERVAL      120 /* two minutes */
 #define NAME_VALID_TIME                1800 /* half one hour */
+#define NAMESERVER_COUNT        3
 
 #define NAME_PROTOCOL_VERSION  1
 
index e6a10f9..c5b0f58 100644 (file)
@@ -163,13 +163,11 @@ void init_zebra (void) {
 
 void zebra_cleanup (void) {
   int i;
-  struct rt_entry *tmp;
   if (zebra.options & OPTION_EXPORT) {
-    for (i = 0; i < HASHSIZE; i++) {
-      for (tmp = routingtable[i].next; tmp != &routingtable[i]; tmp = tmp->next)
-       zebra_del_olsr_v4_route (tmp);     
-      for (tmp = hna_routes[i].next; tmp != &hna_routes[i]; tmp = tmp->next)
-       zebra_del_olsr_v4_route (tmp) ;   }
+    struct rt_entry *rt;
+    OLSR_FOR_ALL_RT_ENTRIES(rt) {
+        zebra_del_olsr_v4_route (rt);
+    } OLSR_FOR_ALL_RT_ENTRIES_END(rt);
   }  
 
   for (i = 0; ZEBRA_ROUTE_MAX - 1; i++)
@@ -178,19 +176,16 @@ void zebra_cleanup (void) {
 
 
 static void zebra_reconnect (void) {
-  struct rt_entry *tmp;
   int i;
 
   zebra_connect();
   if (!zebra.status & STATUS_CONNECTED) return; // try again next time
 
   if (zebra.options & OPTION_EXPORT) {
-    for (i = 0; i < HASHSIZE; i++) {
-      for (tmp = routingtable[i].next; tmp != &routingtable[i]; tmp = tmp->next)
-       zebra_add_olsr_v4_route (tmp);     
-      for (tmp = hna_routes[i].next; tmp != &hna_routes[i]; tmp = tmp->next)
-       zebra_add_olsr_v4_route (tmp);
-    }
+    struct rt_entry *rt;
+    OLSR_FOR_ALL_RT_ENTRIES(rt) {
+        zebra_add_olsr_v4_route (rt);
+    } OLSR_FOR_ALL_RT_ENTRIES_END(rt);
   }  
 
   for (i = 0; ZEBRA_ROUTE_MAX - 1; i++)
@@ -740,14 +735,15 @@ int zebra_add_olsr_v4_route (struct rt_entry *r) {
   route.type = ZEBRA_ROUTE_OLSR; // OLSR
   route.message = ZAPI_MESSAGE_METRIC;
   route.flags = zebra.flags;
-  route.prefixlen = masktoprefixlen (r->rt_mask.v4);
-  route.prefix = r->rt_dst.v4;
-  if ((r->rt_router.v4 == r->rt_dst.v4 && route.prefixlen == 32)){
+  route.prefixlen = r->rt_dst.prefix_len;
+  route.prefix = r->rt_dst.prefix.v4;
+  if ((r->rt_best->rtp_nexthop.gateway.v4 == r->rt_dst.prefix.v4 &&
+       route.prefixlen == 32)) {
     route.message |= ZAPI_MESSAGE_IFINDEX | ZAPI_MESSAGE_NEXTHOP;
     route.ind_num = 1;
     route.index = olsr_malloc (sizeof *route.index, 
                               "zebra_add_olsr_v4_route");
-    *route.index = htonl(r->rt_if->if_index);
+    *route.index = htonl(r->rt_best->rtp_nexthop.iface->if_index);
     route.nexthops = olsr_malloc (sizeof route.nexthops->type +
                                  sizeof route.nexthops->payload,
                                  "zebra_add_olsr_v4_route");
@@ -762,10 +758,10 @@ int zebra_add_olsr_v4_route (struct rt_entry *r) {
                                   sizeof route.nexthops->payload), 
                                   "zebra_add_olsr_v4_route");
     route.nexthops->type = ZEBRA_NEXTHOP_IPV4;
-    route.nexthops->payload.v4 = r->rt_router.v4;
+    route.nexthops->payload.v4 = r->rt_best->rtp_nexthop.gateway.v4;
   }
 
-  route.metric = r->rt_metric;
+  route.metric = r->rt_best->rtp_metric.hops;
   route.metric = htonl(route.metric);
 
   if (zebra.distance) {
@@ -785,14 +781,14 @@ int zebra_del_olsr_v4_route (struct rt_entry *r) {
   route.type = ZEBRA_ROUTE_OLSR; // OLSR
   route.message = ZAPI_MESSAGE_METRIC;
   route.flags = zebra.flags;
-  route.prefixlen = masktoprefixlen (r->rt_mask.v4);
-  route.prefix = r->rt_dst.v4;
-  if ((r->rt_router.v4 == r->rt_dst.v4 && route.prefixlen == 32)){
+  route.prefixlen = r->rt_dst.prefix_len;
+  route.prefix = r->rt_dst.prefix.v4;
+  if ((r->rt_best->rtp_nexthop.gateway.v4 == r->rt_dst.prefix.v4 && route.prefixlen == 32)){
     route.message |= ZAPI_MESSAGE_IFINDEX;
     route.ind_num = 1;
     route.index = olsr_malloc (sizeof *route.index, 
                               "zebra_add_olsr_v4_route");
-    *route.index = htonl (r->rt_if->if_index);
+    *route.index = htonl (r->rt_best->rtp_nexthop.iface->if_index);
     route.nexthops = olsr_malloc (sizeof route.nexthops->type +
                                  sizeof route.nexthops->payload,
                                  "zebra_add_olsr_v4_route");
@@ -807,9 +803,9 @@ int zebra_del_olsr_v4_route (struct rt_entry *r) {
                                   sizeof route.nexthops->payload), 
                                  "zebra_add_olsr_v4_route");
     route.nexthops->type = ZEBRA_NEXTHOP_IPV4;
-    route.nexthops->payload.v4 = r->rt_router.v4;
+    route.nexthops->payload.v4 = r->rt_best->rtp_nexthop.gateway.v4;
   }
-  route.metric = r->rt_metric;
+  route.metric = r->rt_best->rtp_metric.hops;
   route.metric = htonl (route.metric);
   
   if (zebra.distance) {
index 21f98f2..2c30a14 100644 (file)
@@ -37,7 +37,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: plugin.c,v 1.9 2007/09/02 22:17:00 bernd67 Exp $
+ * $Id: plugin.c,v 1.10 2007/09/05 16:11:10 bernd67 Exp $
  */
 
 #include <string.h>
@@ -84,7 +84,6 @@ static struct neighbor_entry *neighTab = NULL;
 static struct mid_entry *midTab = NULL;
 static struct tc_entry *tcTab = NULL;
 static struct hna_entry *hnaTab = NULL;
-static struct rt_entry *routeTab = NULL;
 static struct olsrd_config *config = NULL;
 
 static int iterIndex;
@@ -221,26 +220,22 @@ void iterNeighTabInit(void)
 
 int iterRouteTabNext(char *buff, int len)
 {
+  struct avl_node *rt_tree_node;
+
   if (iterRouteTab == NULL)
     return -1;
 
   snprintf(buff, len, "destination~%s~gateway~%s~interface~%s~metric~%d~",
-           rawIpAddrToString(&iterRouteTab->rt_dst, ipAddrLen),
-           rawIpAddrToString(&iterRouteTab->rt_router, ipAddrLen),
-           iterRouteTab->rt_if->int_name, iterRouteTab->rt_metric);
-
-  iterRouteTab = iterRouteTab->next;
-
-  if (iterRouteTab == &routeTab[iterIndex])
-  {
-    iterRouteTab = NULL;
-    
-    while (++iterIndex < HASHSIZE)
-      if (routeTab[iterIndex].next != &routeTab[iterIndex])
-      {
-        iterRouteTab = routeTab[iterIndex].next;
-        break;
-      }
+           rawIpAddrToString(&iterRouteTab->rt_dst.prefix, ipAddrLen),
+           rawIpAddrToString(&iterRouteTab->rt_best->rtp_nexthop.gateway, ipAddrLen),
+           iterRouteTab->rt_best->rtp_nexthop.iface->int_name,
+           iterRouteTab->rt_best->rtp_metric.hops);
+
+  rt_tree_node = avl_walk_next(&iterRouteTab->rt_tree_node);
+  if (rt_tree_node) {
+      iterRouteTab = rt_tree_node->data;
+  } else {
+      iterRouteTab = NULL;
   }
 
   return 0;
@@ -248,17 +243,10 @@ int iterRouteTabNext(char *buff, int len)
 
 void iterRouteTabInit(void)
 {
-  iterRouteTab = NULL;
-
-  if (routeTab == NULL)
-    return;
+    avl_init(&routingtree, avl_comp_prefix_default);
+    routingtree_version = 0;
 
-  for (iterIndex = 0; iterIndex < HASHSIZE; iterIndex++)
-    if (routeTab[iterIndex].next != &routeTab[iterIndex])
-    {
-      iterRouteTab = routeTab[iterIndex].next;
-      break;
-    }
+    iterRouteTab = (avl_walk_first(&routingtree)->data);
 }
 
 int iterTcTabNext(char *buff, int len)
@@ -478,7 +466,6 @@ int olsrd_plugin_init(void)
   midTab = mid_set;
   tcTab = tc_table;
   hnaTab = hna_set;
-  routeTab = routingtable;
   config = olsr_cnf;
 
   httpInit();
index a8582eb..6e6e667 100644 (file)
@@ -40,7 +40,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: olsrd_txtinfo.c,v 1.7 2007/07/15 19:29:37 bernd67 Exp $
+ * $Id: olsrd_txtinfo.c,v 1.8 2007/09/05 16:11:10 bernd67 Exp $
  */
 
 /*
@@ -309,37 +309,26 @@ static void ipc_print_neigh_link(void)
 
 static void ipc_print_routes(void)
 {
-    int size = 0, index;
-    struct rt_entry *routes;
+    struct rt_entry *rt;
+    struct avl_node *rt_tree_node;
 
-    ipc_sendf("Table: Routes\nDestination\tGateway\tMetric\tETX\tInterface\tType\n");
+    ipc_sendf("Table: Routes\nDestination\tGateway\tMetric\tETX\tInterface\n");
 
-    /* Neighbors */
-    for(index = 0;index < HASHSIZE; index++) {
-        for(routes = routingtable[index].next;
-            routes != &routingtable[index];
-            routes = routes->next) {
-            size = 0;
-            ipc_sendf( "%s\t%s\t%d\t%.2f\t%s\tHOST\n",
-                       olsr_ip_to_string(&routes->rt_dst),
-                       olsr_ip_to_string(&routes->rt_router),
-                       routes->rt_metric,
-                       routes->rt_etx,
-                       routes->rt_if->int_name);
-       }
-    }
+    /* Walk the route table */
+    for (rt_tree_node = avl_walk_first(&routingtree);
+         rt_tree_node;
+         rt_tree_node = avl_walk_next(rt_tree_node)) {
+
+        rt = rt_tree_node->data;
+
+        ipc_sendf( "%s/%d\t%s\t%d\t%.3f\t%s\t\n",
+                   olsr_ip_to_string(&rt->rt_dst.prefix),
+                   rt->rt_dst.prefix_len,
+                   olsr_ip_to_string(&rt->rt_best->rtp_nexthop.gateway),
+                   rt->rt_best->rtp_metric.hops,
+                   rt->rt_best->rtp_metric.etx,
+                   rt->rt_best->rtp_nexthop.iface->int_name);
 
-    /* HNA */
-    for(index = 0;index < HASHSIZE;index++) {
-        for(routes = hna_routes[index].next;
-            routes != &hna_routes[index];
-            routes = routes->next) {
-            ipc_sendf("%s\t%s\t%d\t%s\t\tHNA\n",
-                      olsr_ip_to_string(&routes->rt_dst),
-                      olsr_ip_to_string(&routes->rt_router),
-                      routes->rt_metric,
-                      routes->rt_if->int_name);
-       }
     }
     ipc_sendf("\n");
 
index 6918189..c5b9cc4 100644 (file)
@@ -36,7 +36,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: kernel_routes.c,v 1.11 2007/05/02 07:41:20 bernd67 Exp $
+ * $Id: kernel_routes.c,v 1.12 2007/09/05 16:11:11 bernd67 Exp $
  */
 
 
@@ -49,7 +49,7 @@
 
 static unsigned int seq = 0;
 
-static int add_del_route(struct rt_entry *dest, int add)
+static int add_del_route(struct rt_entry *rt, int add)
 {
   struct rt_msghdr *rtm;
   unsigned char buff[512];
@@ -58,17 +58,17 @@ static int add_del_route(struct rt_entry *dest, int add)
   struct sockaddr_dl *sdl;
   struct ifaddrs *addrs;
   struct ifaddrs *awalker;
+  struct rt_nexthop *nexthop;
+  union olsr_ip_addr mask;
   int step, step2;
   int len;
-  char Str1[16], Str2[16], Str3[16];
   int flags;
 
-  inet_ntop(AF_INET, &dest->rt_dst.v4, Str1, 16);
-  inet_ntop(AF_INET, &dest->rt_mask.v4, Str2, 16);
-  inet_ntop(AF_INET, &dest->rt_router.v4, Str3, 16);
-
-  OLSR_PRINTF(1, "%s IPv4 route to %s/%s via %s.\n",
-    (add != 0) ? "Adding" : "Removing", Str1, Str2, Str3);
+  if (add) {
+      OLSR_PRINTF(2, "KERN: Adding %s\n", olsr_rtp_to_string(rt->rt_best));
+  } else {
+      OLSR_PRINTF(2, "KERN: Deleting %s\n", olsr_rt_to_string(rt));
+  }
 
   memset(buff, 0, sizeof (buff));
   memset(&sin, 0, sizeof (sin));
@@ -81,7 +81,7 @@ static int add_del_route(struct rt_entry *dest, int add)
 
   rtm = (struct rt_msghdr *)buff;
 
-  flags = dest->rt_flags;
+  flags = olsr_rt_flags(rt);
 
   // the host is directly reachable, so use cloning and a /32 net
   // routing table entry
@@ -101,14 +101,15 @@ static int add_del_route(struct rt_entry *dest, int add)
 
   walker = buff + sizeof (struct rt_msghdr);
 
-  sin.sin_addr.s_addr = dest->rt_dst.v4;
+  sin.sin_addr.s_addr = rt->rt_dst.prefix.v4;
 
   memcpy(walker, &sin, sizeof (sin));
   walker += step;
 
+  nexthop = olsr_get_nh(rt);
   if ((flags & RTF_GATEWAY) != 0)
   {
-    sin.sin_addr.s_addr = dest->rt_router.v4;
+    sin.sin_addr.s_addr = nexthop->gateway.v4;
 
     memcpy(walker, &sin, sizeof (sin));
     walker += step;
@@ -127,12 +128,12 @@ static int add_del_route(struct rt_entry *dest, int add)
 
     for (awalker = addrs; awalker != NULL; awalker = awalker->ifa_next)
       if (awalker->ifa_addr->sa_family == AF_LINK &&
-          strcmp(awalker->ifa_name, dest->rt_if->int_name) == 0)
+          strcmp(awalker->ifa_name, nexthop->iface->int_name) == 0)
         break;
 
     if (awalker == NULL)
     {
-      fprintf(stderr, "interface %s not found\n", dest->rt_if->int_name);
+      fprintf(stderr, "interface %s not found\n", nexthop->iface->int_name);
       freeifaddrs(addrs);
       return -1;
     }
@@ -145,7 +146,10 @@ static int add_del_route(struct rt_entry *dest, int add)
     freeifaddrs(addrs);
   }
 
-  sin.sin_addr.s_addr = dest->rt_mask.v4;
+  if (!olsr_prefix_to_netmask(&mask, rt->rt_dst.prefix_len)) {
+    return -1;
+  }
+  sin.sin_addr.s_addr = mask.v4;
 
   memcpy(walker, &sin, sizeof (sin));
   walker += step;
@@ -160,32 +164,32 @@ static int add_del_route(struct rt_entry *dest, int add)
   return 0;
 }
 
-int olsr_ioctl_add_route(struct rt_entry *dest)
+int olsr_ioctl_add_route(struct rt_entry *rt)
 {
-  return add_del_route(dest, 1);
+  return add_del_route(rt, 1);
 }
 
-int olsr_ioctl_del_route(struct rt_entry *dest)
+int olsr_ioctl_del_route(struct rt_entry *rt)
 {
-  return add_del_route(dest, 0);
+  return add_del_route(rt, 0);
 }
 
-static int add_del_route6(struct rt_entry *dest, int add)
+static int add_del_route6(struct rt_entry *rt, int add)
 {
   struct rt_msghdr *rtm;
   unsigned char buff[512];
   unsigned char *walker;
   struct sockaddr_in6 sin6;
   struct sockaddr_dl sdl;
+  struct rt_nexthop *nexthop;
   int step, step_dl;
   int len;
-  char Str1[40], Str2[40];
-
-  inet_ntop(AF_INET6, &dest->rt_dst.v6, Str1, 40);
-  inet_ntop(AF_INET6, &dest->rt_router.v6, Str2, 40);
 
-  OLSR_PRINTF(1, "%s IPv6 route to %s/%d via %s.\n", 
-    (add != 0) ? "Adding" : "Removing", Str1, dest->rt_mask.v6, Str2);
+  if (add) {
+      OLSR_PRINTF(2, "KERN: Adding %s\n", olsr_rtp_to_string(rt->rt_best));
+  } else {
+      OLSR_PRINTF(2, "KERN: Deleting %s\n", olsr_rt_to_string(rt));
+  }
 
   memset(buff, 0, sizeof (buff));
   memset(&sin6, 0, sizeof (sin6));
@@ -203,20 +207,21 @@ static int add_del_route6(struct rt_entry *dest, int add)
   rtm->rtm_version = RTM_VERSION;
   rtm->rtm_type = (add != 0) ? RTM_ADD : RTM_DELETE;
   rtm->rtm_index = 0;
-  rtm->rtm_flags = dest->rt_flags;
+  rtm->rtm_flags = olsr_rt_flags(rt);
   rtm->rtm_addrs = RTA_DST | RTA_GATEWAY;
   rtm->rtm_seq = ++seq;
 
   walker = buff + sizeof (struct rt_msghdr);
 
-  memcpy(&sin6.sin6_addr.s6_addr, &dest->rt_dst.v6, sizeof(struct in6_addr));
+  memcpy(&sin6.sin6_addr.s6_addr, &rt->rt_dst.prefix.v6, sizeof(struct in6_addr));
 
   memcpy(walker, &sin6, sizeof (sin6));
   walker += step;
 
+  nexthop = olsr_get_nh(rt);
   if ((rtm->rtm_flags & RTF_GATEWAY) != 0)
   {
-    memcpy(&sin6.sin6_addr.s6_addr, &dest->rt_router.v6, sizeof(struct in6_addr));
+    memcpy(&sin6.sin6_addr.s6_addr, &nexthop->gateway.v6, sizeof(struct in6_addr));
 
     memcpy(walker, &sin6, sizeof (sin6));
     walker += step;
@@ -226,7 +231,7 @@ static int add_del_route6(struct rt_entry *dest, int add)
 
   else
   {
-    memcpy(&sin6.sin6_addr.s6_addr, &dest->rt_if->int6_addr.sin6_addr.s6_addr,
+    memcpy(&sin6.sin6_addr.s6_addr, &nexthop->iface->int6_addr.sin6_addr.s6_addr,
       sizeof(struct in6_addr));
 
     memcpy(walker, &sin6, sizeof (sin6));
@@ -236,7 +241,7 @@ static int add_del_route6(struct rt_entry *dest, int add)
 
   if ((rtm->rtm_flags & RTF_HOST) == 0)
   {
-    olsr_prefix_to_netmask((union olsr_ip_addr *)&sin6.sin6_addr, dest->rt_mask.v6);
+    olsr_prefix_to_netmask((union olsr_ip_addr *)&sin6.sin6_addr, rt->rt_dst.prefix_len);
     memcpy(walker, &sin6, sizeof (sin6));
     walker += step;
     rtm->rtm_addrs |= RTA_NETMASK;
@@ -244,8 +249,8 @@ static int add_del_route6(struct rt_entry *dest, int add)
 
   if ((rtm->rtm_flags & RTF_GATEWAY) != 0)
   {
-    strcpy(&sdl.sdl_data[0], dest->rt_if->int_name);
-    sdl.sdl_nlen = (u_char)strlen(dest->rt_if->int_name);
+    strcpy(&sdl.sdl_data[0], nexthop->iface->int_name);
+    sdl.sdl_nlen = (u_char)strlen(nexthop->iface->int_name);
     memcpy(walker, &sdl, sizeof (sdl));
     walker += step_dl;
     rtm->rtm_addrs |= RTA_IFP;
@@ -261,12 +266,18 @@ static int add_del_route6(struct rt_entry *dest, int add)
   return 0;
 }
 
-int olsr_ioctl_add_route6(struct rt_entry *dest)
+int olsr_ioctl_add_route6(struct rt_entry *rt)
 {
-  return add_del_route6(dest, 1);
+  return add_del_route6(rt, 1);
 }
 
-int olsr_ioctl_del_route6(struct rt_entry *dest)
+int olsr_ioctl_del_route6(struct rt_entry *rt)
 {
-  return add_del_route6(dest, 0);
+  return add_del_route6(rt, 0);
 }
+
+/*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */
index 2b1a093..8017bae 100644 (file)
@@ -36,7 +36,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: hna_set.c,v 1.20 2007/08/02 22:07:19 bernd67 Exp $
+ * $Id: hna_set.c,v 1.21 2007/09/05 16:11:10 bernd67 Exp $
  */
 
 #include "defs.h"
@@ -80,7 +80,15 @@ olsr_init_hna_set(void)
   return 1;
 }
 
-
+int
+olsr_get_hna_prefix_len(struct hna_net *hna)
+{
+  if (olsr_cnf->ip_version == AF_INET) {
+    return olsr_netmask_to_prefix((union olsr_ip_addr *)&hna->A_netmask.v4);
+  } else {
+    return hna->A_netmask.v6;
+  }
+}
 
 
 /**
@@ -365,4 +373,8 @@ olsr_print_hna_set(void)
 
 }
 
-
+/*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */
index c9ab23b..22ec926 100644 (file)
@@ -36,7 +36,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: hna_set.h,v 1.14 2005/05/29 12:47:45 br1 Exp $
+ * $Id: hna_set.h,v 1.15 2007/09/05 16:11:10 bernd67 Exp $
  */
 
 
@@ -73,6 +73,9 @@ extern size_t netmask_size;
 int
 olsr_init_hna_set(void);
 
+int
+olsr_get_hna_prefix_len(struct hna_net *);
+
 struct hna_net *
 olsr_lookup_hna_net(struct hna_net *, union olsr_ip_addr *, union hna_netmask *);
 
index c66dfad..1e57074 100644 (file)
@@ -36,7 +36,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: ipc_frontend.c,v 1.33 2007/08/02 22:07:19 bernd67 Exp $
+ * $Id: ipc_frontend.c,v 1.34 2007/09/05 16:11:10 bernd67 Exp $
  */
 
 /*
@@ -270,12 +270,16 @@ frontend_msgparser(union olsr_message *msg, struct interface *in_if __attribute_
  *@return negative on error
  */
 int
-ipc_route_send_rtentry(union olsr_ip_addr *dst, union olsr_ip_addr *gw, int met, int add, char *int_name)
+ipc_route_send_rtentry(union olsr_ip_addr *dst, union olsr_ip_addr *gw,
+                       int met, int add, char *int_name)
 {
   struct ipcmsg packet;
-  //int i, x;
   char *tmp;
 
+  if(!olsr_cnf->open_ipc) {
+    return -1;
+  }
+
   if(!ipc_active)
     return 0;
 
@@ -333,9 +337,8 @@ ipc_route_send_rtentry(union olsr_ip_addr *dst, union olsr_ip_addr *gw, int met,
 static int
 ipc_send_all_routes(int fd)
 {
-  struct rt_entry  *destination;
+  struct rt_entry  *rt;
   struct interface *ifn;
-  int               idx;
   struct ipcmsg packet;
   char *tmp;
   
@@ -343,99 +346,36 @@ ipc_send_all_routes(int fd)
   if(!ipc_active)
     return 0;
   
-  for(idx=0;idx<HASHSIZE;idx++)
-    {
-      for(destination = routingtable[idx].next;
-         destination != &routingtable[idx];
-         destination = destination->next)
-       {
-         ifn = destination->rt_if;
-         
+  OLSR_FOR_ALL_RT_ENTRIES(rt) {
 
-         memset(&packet, 0, sizeof(struct ipcmsg));
-         packet.size = htons(IPC_PACK_SIZE);
-         packet.msgtype = ROUTE_IPC;
+    ifn = rt->rt_nexthop.iface;
          
-         COPY_IP(&packet.target_addr, &destination->rt_dst);
+    memset(&packet, 0, sizeof(struct ipcmsg));
+    packet.size = htons(IPC_PACK_SIZE);
+    packet.msgtype = ROUTE_IPC;
          
-         packet.add = 1;
-
-         if(olsr_cnf->ip_version == AF_INET)
-           {
-             packet.metric = (olsr_u8_t)(destination->rt_metric - 1);
-           }
-         else
-           {
-             packet.metric = (olsr_u8_t)destination->rt_metric;
-           }
-         COPY_IP(&packet.gateway_addr, &destination->rt_router);
-
-         if(ifn)
-           memcpy(&packet.device[0], ifn->int_name, 4);
-         else
-           memset(&packet.device[0], 0, 4);
-
-
-         tmp = (char *) &packet;
-  
-         if (send(fd, tmp, IPC_PACK_SIZE, MSG_NOSIGNAL) < 0) // MSG_NOSIGNAL to avoid sigpipe
-           {
-             OLSR_PRINTF(1, "(RT_ENTRY)IPC connection lost!\n");
-             CLOSE(ipc_conn);
-             //olsr_cnf->open_ipc = 0;
-             ipc_active = OLSR_FALSE;
-             return -1;
-           }
-
-       }
-    }
-
-  for(idx=0;idx<HASHSIZE;idx++)
-    {
-      for(destination = hna_routes[idx].next;
-         destination != &hna_routes[idx];
-         destination = destination->next)
-       {
-         ifn = destination->rt_if;
-
-         packet.size = htons(IPC_PACK_SIZE);
-         packet.msgtype = ROUTE_IPC;
-         
-         COPY_IP(&packet.target_addr, &destination->rt_dst);
+    COPY_IP(&packet.target_addr, &rt->rt_dst.prefix);
          
-         packet.add = 1;
+    packet.add = 1;
+    packet.metric = (olsr_u8_t)(rt->rt_best->rtp_metric.hops);
 
-         if(olsr_cnf->ip_version == AF_INET)
-           {
-             packet.metric = (olsr_u8_t)(destination->rt_metric - 1);
-           }
-         else
-           {
-             packet.metric = (olsr_u8_t)destination->rt_metric;
-           }
-         COPY_IP(&packet.gateway_addr, &destination->rt_router);
+    COPY_IP(&packet.gateway_addr, &rt->rt_nexthop.gateway);
 
-         if(ifn)
-           memcpy(&packet.device[0], ifn->int_name, 4);
-         else
-           memset(&packet.device[0], 0, 4);
+    if(ifn)
+      memcpy(&packet.device[0], ifn->int_name, 4);
+    else
+      memset(&packet.device[0], 0, 4);
 
-
-         tmp = (char *) &packet;
+    tmp = (char *) &packet;
   
-         if (send(ipc_conn, tmp, IPC_PACK_SIZE, MSG_NOSIGNAL) < 0) // MSG_NOSIGNAL to avoid sigpipe
-           {
-             OLSR_PRINTF(1, "(RT_ENTRY)IPC connection lost!\n");
-             CLOSE(ipc_conn);
-             //olsr_cnf->open_ipc = 0;
-             ipc_active = OLSR_FALSE;
-             return -1;
-           }
-
-       }
+    /* MSG_NOSIGNAL to avoid sigpipe */
+    if (send(fd, tmp, IPC_PACK_SIZE, MSG_NOSIGNAL) < 0) {
+      OLSR_PRINTF(1, "(RT_ENTRY)IPC connection lost!\n");
+      CLOSE(ipc_conn);
+      ipc_active = OLSR_FALSE;
+      return -1;
     }
-
-
+  } OLSR_FOR_ALL_RT_ENTRIES_END(rt);
   return 1;
 }
 
@@ -549,3 +489,9 @@ shutdown_ipc(void)
   
   return 1;
 }
+
+/*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */
index 5d05b5f..c5884fd 100644 (file)
@@ -36,7 +36,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: kernel_routes.h,v 1.8 2004/11/21 11:28:56 kattemat Exp $
+ * $Id: kernel_routes.h,v 1.9 2007/09/05 16:11:10 bernd67 Exp $
  */
 
 
 
 
 int
-olsr_ioctl_add_route(struct rt_entry *destination);
+olsr_ioctl_add_route(struct rt_entry *);
 
 int
-olsr_ioctl_add_route6(struct rt_entry *destination);
+olsr_ioctl_add_route6(struct rt_entry *);
 
 int
-olsr_ioctl_del_route(struct rt_entry *destination);
+olsr_ioctl_del_route(struct rt_entry *);
 
 int
-olsr_ioctl_del_route6(struct rt_entry *destination);
+olsr_ioctl_del_route6(struct rt_entry *);
 
 
 int
index 996f31e..6191466 100644 (file)
@@ -36,7 +36,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: kernel_routes.c,v 1.23 2007/05/17 20:30:09 bernd67 Exp $
+ * $Id: kernel_routes.c,v 1.24 2007/09/05 16:11:11 bernd67 Exp $
  */
 
 
 #include <unistd.h>
 
 
-
-static struct sockaddr_in6 null_addr6; /* Address used as Originator Address IPv6 */
-
 /**
- *Insert a route in the kernel routing table
+ * Insert a route in the kernel routing table
  *
- *@param destination the route to add
+ * @param destination the route to add
  *
- *@return negative on error
+ * @return negative on error
  */
 int
-olsr_ioctl_add_route(struct rt_entry *destination)
+olsr_ioctl_add_route(struct rt_entry *rt)
 {
   struct rtentry kernel_route;
-  int tmp;
-  char dst_str[INET_ADDRSTRLEN], mask_str[INET_ADDRSTRLEN], router_str[INET_ADDRSTRLEN];
-
-  OLSR_PRINTF(1, "(ioctl)Adding route with metric %d to %s/%s via %s/%s.\n",
-              destination->rt_metric,
-              inet_ntop(AF_INET, &destination->rt_dst.v4, dst_str, sizeof(dst_str)),
-              inet_ntop(AF_INET, &destination->rt_mask.v4, mask_str, sizeof(mask_str)),
-              inet_ntop(AF_INET, &destination->rt_router.v4, router_str, sizeof(router_str)),
-              destination->rt_if->int_name);
-  
+  union olsr_ip_addr mask;
+  int rslt;
+
+  OLSR_PRINTF(2, "KERN: Adding %s\n", olsr_rtp_to_string(rt->rt_best));
+
   memset(&kernel_route, 0, sizeof(struct rtentry));
 
   ((struct sockaddr_in*)&kernel_route.rt_dst)->sin_family = AF_INET;
   ((struct sockaddr_in*)&kernel_route.rt_gateway)->sin_family = AF_INET;
   ((struct sockaddr_in*)&kernel_route.rt_genmask)->sin_family = AF_INET;
 
-  ((struct sockaddr_in *)&kernel_route.rt_dst)->sin_addr.s_addr = destination->rt_dst.v4;
-  ((struct sockaddr_in *)&kernel_route.rt_genmask)->sin_addr.s_addr = destination->rt_mask.v4;
+  ((struct sockaddr_in *)&kernel_route.rt_dst)->sin_addr.s_addr =
+    rt->rt_dst.prefix.v4;
 
-  if(destination->rt_dst.v4 != destination->rt_router.v4)
-    {
-      ((struct sockaddr_in *)&kernel_route.rt_gateway)->sin_addr.s_addr=destination->rt_router.v4;
-    }
+  if (!olsr_prefix_to_netmask(&mask, rt->rt_dst.prefix_len)) {
+    return -1;
+  }
+  ((struct sockaddr_in *)&kernel_route.rt_genmask)->sin_addr.s_addr = mask.v4;
 
-  kernel_route.rt_flags = destination->rt_flags;
-  
-  kernel_route.rt_metric = destination->rt_metric + 1;
+  if (rt->rt_dst.prefix.v4 != rt->rt_best->rtp_nexthop.gateway.v4) {
+    ((struct sockaddr_in *)&kernel_route.rt_gateway)->sin_addr.s_addr =
+      rt->rt_best->rtp_nexthop.gateway.v4;
+  }
 
-  if((olsr_cnf->del_gws) &&
-     (destination->rt_dst.v4 == INADDR_ANY) &&
-     (destination->rt_dst.v4 == INADDR_ANY))
-    {
-      delete_all_inet_gws();
-      olsr_cnf->del_gws = OLSR_FALSE;
-    }
+  kernel_route.rt_flags = olsr_rt_flags(rt);
+  kernel_route.rt_metric = RT_METRIC_DEFAULT;
 
   /*
    * Set interface
    */
-  kernel_route.rt_dev = destination->rt_if->int_name;
-  
-  //printf("Inserting route entry on device %s\n\n", kernel_route.rt_dev);
-  
-  /*
-  printf("Adding route:\n\tdest: %s\n", olsr_ip_to_string(&destination->rt_dst));    
-  printf("\trouter: %s\n", olsr_ip_to_string(&destination->rt_router));    
-  printf("\tmask: %s\n", olsr_ip_to_string((union olsr_ip_addr *)&destination->rt_mask));    
-  printf("\tmetric: %d\n", destination->rt_metric);    
-  */
+  kernel_route.rt_dev = rt->rt_best->rtp_nexthop.iface->int_name;
 
-  //printf("\tiface: %s\n", kernel_route.rt_dev);    
-  
-  tmp = ioctl(olsr_cnf->ioctl_s,SIOCADDRT,&kernel_route);
-  /*  kernel_route.rt_dev=*/
+  /* delete existing default route before ? */
+  if((olsr_cnf->del_gws) &&
+     (rt->rt_dst.prefix.v4 == INADDR_ANY) &&
+     (rt->rt_dst.prefix_len == INADDR_ANY)) {
+    delete_all_inet_gws();
+    olsr_cnf->del_gws = OLSR_FALSE;
+  }
 
-  /*
-   *Send IPC route update message
-   */
-  
-  if(olsr_cnf->open_ipc)
-      {
-       ipc_route_send_rtentry(&destination->rt_dst, 
-                              &destination->rt_router, 
-                              destination->rt_metric, 
-                              1,
-                              destination->rt_if->int_name); /* Send interface name */
-      }
-  
-  return tmp;
-}
+  if ((rslt = ioctl(olsr_cnf->ioctl_s, SIOCADDRT, &kernel_route)) >= 0) {
 
+    /*
+     * Send IPC route update message
+     */
+    ipc_route_send_rtentry(&rt->rt_dst.prefix, &rt->rt_best->rtp_nexthop.gateway,
+                           rt->rt_best->rtp_metric.hops, 1,
+                           rt->rt_best->rtp_nexthop.iface->int_name);
+  }
 
+  return rslt;
+}
 
 
 /**
@@ -146,65 +123,43 @@ olsr_ioctl_add_route(struct rt_entry *destination)
  *@return negative on error
  */
 int
-olsr_ioctl_add_route6(struct rt_entry *destination)
+olsr_ioctl_add_route6(struct rt_entry *rt)
 {
 
   struct in6_rtmsg kernel_route;
-  int tmp;
-  struct in6_addr zeroaddr;
-
-  OLSR_PRINTF(2, "(ioctl)Adding route: %s(hopc %d)\n", 
-             olsr_ip_to_string(&destination->rt_dst), 
-             destination->rt_metric + 1);
-  
-
-  memset(&zeroaddr, 0, olsr_cnf->ipsize); /* Use for comparision */
+  int rslt;
 
+  OLSR_PRINTF(2, "KERN: Adding %s\n", olsr_rtp_to_string(rt->rt_best));
 
   memset(&kernel_route, 0, sizeof(struct in6_rtmsg));
 
-  COPY_IP(&kernel_route.rtmsg_dst, &destination->rt_dst);
-
-  kernel_route.rtmsg_flags = destination->rt_flags;
-  kernel_route.rtmsg_metric = destination->rt_metric;
-  
-  kernel_route.rtmsg_dst_len = destination->rt_mask.v6;
-
-  if(memcmp(&destination->rt_dst, &destination->rt_router, olsr_cnf->ipsize) != 0)
-    {
-      COPY_IP(&kernel_route.rtmsg_gateway, &destination->rt_router);
-    }
-  else
-    {
-      COPY_IP(&kernel_route.rtmsg_gateway, &destination->rt_dst);
-    }
-
-      /*
-       * set interface
-       */
-  kernel_route.rtmsg_ifindex = destination->rt_if->if_index;
+  COPY_IP(&kernel_route.rtmsg_dst, &rt->rt_dst.prefix);
+  kernel_route.rtmsg_dst_len = rt->rt_dst.prefix_len;
 
+  COPY_IP(&kernel_route.rtmsg_gateway, &rt->rt_best->rtp_nexthop.gateway);
 
+  kernel_route.rtmsg_flags = olsr_rt_flags(rt);
+  kernel_route.rtmsg_metric = RT_METRIC_DEFAULT;
   
-  //OLSR_PRINTF(3, "Adding route to %s using gw ", olsr_ip_to_string((union olsr_ip_addr *)&kernel_route.rtmsg_dst));
-  //OLSR_PRINTF(3, "%s\n", olsr_ip_to_string((union olsr_ip_addr *)&kernel_route.rtmsg_gateway));
+  /*
+   * set interface
+   */
+  kernel_route.rtmsg_ifindex = rt->rt_best->rtp_nexthop.iface->if_index;
+  
+  /* XXX delete 0/0 route before ? */
 
-  if((tmp = ioctl(olsr_cnf->ioctl_s, SIOCADDRT, &kernel_route)) >= 0)
-    {
-      if(olsr_cnf->open_ipc)
-       {
-         if(memcmp(&destination->rt_router, &null_addr6, olsr_cnf->ipsize) != 0)
-           ipc_route_send_rtentry(&destination->rt_dst, 
-                                  &destination->rt_router, 
-                                  destination->rt_metric, 
-                                  1,
-                                  destination->rt_if->int_name); /* Send interface name */
+  if((rslt = ioctl(olsr_cnf->ioctl_s, SIOCADDRT, &kernel_route)) >= 0) {
 
-       }
-    }
-    return(tmp);
-}
+    /*
+     * Send IPC route update message
+     */
+    ipc_route_send_rtentry(&rt->rt_dst.prefix, &rt->rt_best->rtp_nexthop.gateway, 
+                           rt->rt_best->rtp_metric.hops, 1,
+                           rt->rt_best->rtp_nexthop.iface->int_name);
+  }
 
+  return rslt;
+}
 
 
 /**
@@ -215,66 +170,54 @@ olsr_ioctl_add_route6(struct rt_entry *destination)
  *@return negative on error
  */
 int
-olsr_ioctl_del_route(struct rt_entry *destination)
+olsr_ioctl_del_route(struct rt_entry *rt)
 {
   struct rtentry kernel_route;
-  int tmp;
-  char dst_str[INET_ADDRSTRLEN], mask_str[INET_ADDRSTRLEN], router_str[INET_ADDRSTRLEN];
-
-  OLSR_PRINTF(1, "(ioctl)Deleting route with metric %d to %s/%s via %s.\n",
-              destination->rt_metric,
-              inet_ntop(AF_INET, &destination->rt_dst.v4, dst_str, sizeof(dst_str)),
-              inet_ntop(AF_INET, &destination->rt_mask.v4, mask_str, sizeof(mask_str)),
-              inet_ntop(AF_INET, &destination->rt_router.v4, router_str, sizeof(router_str)));
-  
+  union olsr_ip_addr mask;
+  int rslt;
+
+  OLSR_PRINTF(2, "KERN: Deleting %s\n", olsr_rt_to_string(rt));
+
   memset(&kernel_route,0,sizeof(struct rtentry));
 
   ((struct sockaddr_in*)&kernel_route.rt_dst)->sin_family = AF_INET;
   ((struct sockaddr_in*)&kernel_route.rt_gateway)->sin_family = AF_INET;
   ((struct sockaddr_in*)&kernel_route.rt_genmask)->sin_family = AF_INET;
 
-  ((struct sockaddr_in *)&kernel_route.rt_dst)->sin_addr.s_addr = destination->rt_dst.v4;
-  if(destination->rt_dst.v4 != destination->rt_router.v4)
-    ((struct sockaddr_in *)&kernel_route.rt_gateway)->sin_addr.s_addr = destination->rt_router.v4;
-  ((struct sockaddr_in *)&kernel_route.rt_genmask)->sin_addr.s_addr = destination->rt_mask.v4;
+  ((struct sockaddr_in *)&kernel_route.rt_dst)->sin_addr.s_addr =
+    rt->rt_dst.prefix.v4;
 
+  if (rt->rt_dst.prefix.v4 != rt->rt_nexthop.gateway.v4) {
+    ((struct sockaddr_in *)&kernel_route.rt_gateway)->sin_addr.s_addr =
+      rt->rt_nexthop.gateway.v4;
+  }
 
-  kernel_route.rt_dev = NULL;
+  if (!olsr_prefix_to_netmask(&mask, rt->rt_dst.prefix_len)) {
+    return -1;
+  } else {
+    ((struct sockaddr_in *)&kernel_route.rt_genmask)->sin_addr.s_addr = mask.v4;
+  }
 
-  kernel_route.rt_flags = destination->rt_flags;
-  
-  kernel_route.rt_metric = destination->rt_metric + 1;
+  kernel_route.rt_flags = olsr_rt_flags(rt);
+  kernel_route.rt_metric = RT_METRIC_DEFAULT;
 
   /*
-  printf("Deleteing route:\n\tdest: %s\n", olsr_ip_to_string(&destination->rt_dst));    
-  printf("\trouter: %s\n", olsr_ip_to_string(&destination->rt_router));    
-  printf("\tmask: %s\n", olsr_ip_to_string((union olsr_ip_addr *)&destination->rt_mask));    
-  printf("\tmetric: %d\n", destination->rt_metric);    
-  //printf("\tiface: %s\n", kernel_route.rt_dev);    
-  */
-
-  tmp = ioctl(olsr_cnf->ioctl_s, SIOCDELRT, &kernel_route);
+   * Set interface
+   */
+  kernel_route.rt_dev = NULL;
 
+  if ((rslt = ioctl(olsr_cnf->ioctl_s, SIOCDELRT, &kernel_route)) >= 0) {
 
     /*
-     *Send IPC route update message
+     * Send IPC route update message
      */
+    ipc_route_send_rtentry(&rt->rt_dst.prefix, NULL, 0, 0, NULL);
+  }
 
-  if(olsr_cnf->open_ipc)
-    ipc_route_send_rtentry(&destination->rt_dst, 
-                          NULL, 
-                          destination->rt_metric, 
-                          0,
-                          NULL); /* Send interface name */
-
-  return tmp;
+  return rslt;
 }
 
 
-
-
-
-
 /**
  *Remove a route from the kernel
  *
@@ -283,48 +226,34 @@ olsr_ioctl_del_route(struct rt_entry *destination)
  *@return negative on error
  */
 int
-olsr_ioctl_del_route6(struct rt_entry *destination)
+olsr_ioctl_del_route6(struct rt_entry *rt)
 {
 
   struct in6_rtmsg kernel_route;
-  int tmp;
-
-  union olsr_ip_addr tmp_addr = destination->rt_dst;
-
-  OLSR_PRINTF(2, "(ioctl)Deleting route: %s(hopc %d)\n", 
-             olsr_ip_to_string(&destination->rt_dst), 
-             destination->rt_metric);
+  int rslt;
 
-
-  OLSR_PRINTF(1, "Deleting route: %s\n", olsr_ip_to_string(&tmp_addr));
+  OLSR_PRINTF(2, "KERN: Deleting %s\n", olsr_rt_to_string(rt));
 
   memset(&kernel_route,0,sizeof(struct in6_rtmsg));
 
-  kernel_route.rtmsg_dst_len = destination->rt_mask.v6;
-
-  memcpy(&kernel_route.rtmsg_dst, &destination->rt_dst, olsr_cnf->ipsize);
-
-  memcpy(&kernel_route.rtmsg_gateway, &destination->rt_router, olsr_cnf->ipsize);
 
-  kernel_route.rtmsg_flags = destination->rt_flags;
-  kernel_route.rtmsg_metric = destination->rt_metric;
+  COPY_IP(&kernel_route.rtmsg_dst, &rt->rt_dst.prefix);
+  kernel_route.rtmsg_dst_len = rt->rt_dst.prefix_len;
 
+  COPY_IP(&kernel_route.rtmsg_gateway, &rt->rt_best->rtp_nexthop.gateway);
 
-  tmp = ioctl(olsr_cnf->ioctl_s, SIOCDELRT,&kernel_route);
+  kernel_route.rtmsg_flags = olsr_rt_flags(rt);
+  kernel_route.rtmsg_metric = RT_METRIC_DEFAULT;
 
+  if ((rslt = ioctl(olsr_cnf->ioctl_s, SIOCDELRT, &kernel_route) >= 0)) {
 
     /*
-     *Send IPC route update message
+     * Send IPC route update message
      */
+    ipc_route_send_rtentry(&rt->rt_dst.prefix, NULL, 0, 0, NULL);
+  }
 
-  if(olsr_cnf->open_ipc)
-    ipc_route_send_rtentry(&destination->rt_dst, 
-                          NULL, 
-                          destination->rt_metric, 
-                          0,
-                          NULL); /* Send interface name */
-
-  return tmp;
+  return rslt;
 }
 
 
@@ -383,18 +312,11 @@ delete_all_inet_gws(void)
       ((struct sockaddr_in *)&kernel_route.rt_gateway)->sin_addr.s_addr = INADDR_ANY;
       ((struct sockaddr_in *)&kernel_route.rt_gateway)->sin_family=AF_INET;
       
-      //memcpy(&kernel_route.rt_gateway, gw, olsr_cnf->ipsize);
-      
-          
-          
+
       kernel_route.rt_flags = RTF_UP | RTF_GATEWAY;
           
-          
       kernel_route.rt_dev = ifr->ifr_ifrn.ifrn_name;
 
-  
-      //printf("Inserting route entry on device %s\n\n", kernel_route.rt_dev);
-      
       if((ioctl(s, SIOCDELRT, &kernel_route)) < 0)
          OLSR_PRINTF(1, "NO\n");
       else
@@ -404,3 +326,9 @@ delete_all_inet_gws(void)
   return 0;
        
 }
+
+/*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */
index d2717d1..d7c88cb 100755 (executable)
@@ -37,7 +37,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: lq_avl.c,v 1.11 2007/08/02 22:00:46 bernd67 Exp $
+ * $Id: lq_avl.c,v 1.12 2007/09/05 16:11:10 bernd67 Exp $
  */
 
 #include <stddef.h>
 #define AVLMIN(x, y) ((x < y) ? x : y)
 
 /*
- * dummy comparison pointer
- * set to zero for a fast inline ipv4 comparison
+ * default comparison pointers 
+ * set to the respective compare function.
+ * if avl_comp_default is set to zero, a fast
+ * inline ipv4 comparison will be executed.
  */
 int (*avl_comp_default)(void *, void *) = NULL;
+int (*avl_comp_prefix_default)(void *, void *);
 
 int avl_comp_ipv4(void *ip1, void *ip2)
 {
@@ -69,6 +72,9 @@ int avl_comp_ipv6(void *ip1, void *ip2)
 void avl_init(struct avl_tree *tree, int (*comp)(void *, void *))
 {
   tree->root = NULL;
+  tree->first = NULL;
+  tree->last = NULL;
+  tree->count = 0;
   tree->comp = comp;
 }
 
@@ -259,35 +265,51 @@ static void post_insert(struct avl_tree *tree, struct avl_node *node)
   return;
 }
 
-static void avl_insert_before(struct avl_node *pos_node, struct avl_node *node)
+static void avl_insert_before(struct avl_tree *tree, struct avl_node *pos_node,
+                              struct avl_node *node)
 {
   if (pos_node->prev != NULL)
     pos_node->prev->next = node;
+  else
+    tree->first = node;
 
   node->prev = pos_node->prev;
   node->next = pos_node;
 
   pos_node->prev = node;
+
+  tree->count++;
 }
 
-static void avl_insert_after(struct avl_node *pos_node, struct avl_node *node)
+static void avl_insert_after(struct avl_tree *tree, struct avl_node *pos_node,
+                             struct avl_node *node)
 {
   if (pos_node->next != NULL)
     pos_node->next->prev = node;
+  else
+    tree->last = node;
 
   node->prev = pos_node;
   node->next = pos_node->next;
 
   pos_node->next = node;
+
+  tree->count++;
 }
 
-static void avl_remove(struct avl_node *node)
+static void avl_remove(struct avl_tree *tree, struct avl_node *node)
 {
   if (node->prev != NULL)
     node->prev->next = node->next;
+  else
+    tree->first = node->next;
 
   if (node->next != NULL)
     node->next->prev = node->prev;
+  else
+    tree->last = node->prev;
+
+  tree->count--;
 }
 
 int avl_insert(struct avl_tree *tree, struct avl_node *new, int allow_duplicates)
@@ -310,6 +332,9 @@ int avl_insert(struct avl_tree *tree, struct avl_node *new, int allow_duplicates
   if (tree->root == NULL)
   {
     tree->root = new;
+    tree->first = new;
+    tree->last = new;
+    tree->count = 1;
     return 0;
   }
 
@@ -328,18 +353,18 @@ int avl_insert(struct avl_tree *tree, struct avl_node *new, int allow_duplicates
 
   if (diff == 0)
   {
-    if (allow_duplicates == 0)
+    if (allow_duplicates == AVL_DUP_NO)
       return -1;
 
     new->leader = 0;
 
-    avl_insert_after(last, new);
+    avl_insert_after(tree, last, new);
     return 0;
   }
 
   if (node->balance == 1)
   {
-    avl_insert_before(node, new);
+    avl_insert_before(tree, node, new);
 
     node->balance = 0;
     new->parent = node;
@@ -349,7 +374,7 @@ int avl_insert(struct avl_tree *tree, struct avl_node *new, int allow_duplicates
   
   if (node->balance == -1)
   {
-    avl_insert_after(last, new);
+    avl_insert_after(tree, last, new);
 
     node->balance = 0;
     new->parent = node;
@@ -359,7 +384,7 @@ int avl_insert(struct avl_tree *tree, struct avl_node *new, int allow_duplicates
 
   if (diff < 0)
   {
-    avl_insert_before(node, new);
+    avl_insert_before(tree, node, new);
 
     node->balance = -1;
     new->parent = node;
@@ -368,7 +393,7 @@ int avl_insert(struct avl_tree *tree, struct avl_node *new, int allow_duplicates
     return 0;
   }
 
-  avl_insert_after(last, new);
+  avl_insert_after(tree, last, new);
 
   node->balance = 1;
   new->parent = node;
@@ -661,27 +686,17 @@ void avl_delete(struct avl_tree *tree, struct avl_node *node)
       avl_delete_worker(tree, node);
   }
 
-  avl_remove(node);
+  avl_remove(tree, node);
 }
 
 struct avl_node *avl_walk_first(struct avl_tree *tree)
 {
-  struct avl_node *node = tree->root;
-
-  if (node == NULL)
-    return NULL;
-
-  return avl_local_min(node);
+  return tree->first;
 }
 
 struct avl_node *avl_walk_last(struct avl_tree *tree)
 {
-  struct avl_node *node = tree->root;
-
-  if (node == NULL)
-    return NULL;
-
-  return avl_local_max(node);
+  return tree->last;
 }
 
 struct avl_node *avl_walk_next(struct avl_node *node)
index 6f1264a..5aa9259 100755 (executable)
@@ -37,7 +37,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: lq_avl.h,v 1.9 2007/07/05 22:43:46 bernd67 Exp $
+ * $Id: lq_avl.h,v 1.10 2007/09/05 16:11:10 bernd67 Exp $
  */
 
 #ifndef _LQ_AVL_H
@@ -59,9 +59,15 @@ struct avl_node
 struct avl_tree
 {
   struct avl_node *root;
+  struct avl_node *first;
+  struct avl_node *last;
+  unsigned int count;
   int (*comp)(void *, void *);
 };
 
+#define AVL_DUP    1
+#define AVL_DUP_NO 0
+
 void avl_init(struct avl_tree *, int (*)(void *, void *));
 struct avl_node *avl_find(struct avl_tree *, void *);
 int avl_insert(struct avl_tree *, struct avl_node *, int);
@@ -72,6 +78,7 @@ struct avl_node *avl_walk_next(struct avl_node *);
 struct avl_node *avl_walk_prev(struct avl_node *);
 
 extern int (*avl_comp_default)(void *, void *);
+extern int (*avl_comp_prefix_default)(void *, void *);
 extern int avl_comp_ipv4(void *, void *);
 extern int avl_comp_ipv6(void *, void *);
 
index 37496f6..d11bf91 100644 (file)
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: lq_list.c,v 1.5 2007/02/10 17:36:51 bernd67 Exp $
+ * $Id: lq_list.c,v 1.6 2007/09/05 16:11:10 bernd67 Exp $
  */
 
 #include <stdlib.h>
 #include "lq_list.h"
 
-void list_init(struct list *list)
+/* init a circular list  */
+void list_head_init(struct list_node *node)
 {
-  list->head = NULL;
-  list->tail = NULL;
+  node->prev = node;
+  node->next = node;
 }
 
-void list_add_head(struct list *list, struct list_node *node)
+void list_node_init(struct list_node *node)
 {
-  if (list->head != NULL)
-    list->head->prev = node;
-
-  else
-    list->tail = node;
-
   node->prev = NULL;
-  node->next = list->head;
-
-  list->head = node;
+  node->next = NULL;
 }
 
-void list_add_tail(struct list *list, struct list_node *node)
+int list_node_on_list(struct list_node *node)
 {
-  if (list->tail != NULL)
-    list->tail->next = node;
+  if (node->prev || node->next) {
+    return 1;
+  }
 
-  else
-    list->head = node;
-
-  node->prev = list->tail;
-  node->next = NULL;
-
-  list->tail = node;
+  return 0;
 }
 
-void list_add_before(struct list *list, struct list_node *pos_node,
-                     struct list_node *node)
+int list_is_empty(struct list_node *node)
 {
-  if (pos_node->prev != NULL)
-    pos_node->prev->next = node;
-
-  else
-    list->head = node;
+  if (node->prev == node && node->next == node) {
+    return 1;
+  }
 
-  node->prev = pos_node->prev;
-  node->next = pos_node;
-
-  pos_node->prev = node;
+  return 0;
 }
 
-void list_add_after(struct list *list, struct list_node *pos_node,
-                    struct list_node *node)
+void list_add_after(struct list_node *pos_node, struct list_node *new_node)
 {
-  if (pos_node->next != NULL)
-    pos_node->next->prev = node;
-
-  else
-    list->tail = node;
+  new_node->next = pos_node->next;
+  new_node->prev = pos_node;
 
-  node->prev = pos_node;
-  node->next = pos_node->next;
-
-  pos_node->next = node;
+  pos_node->next->prev = new_node;
+  pos_node->next = new_node;
 }
 
-void list_remove(struct list *list, struct list_node *node)
+void list_add_before(struct list_node *pos_node, struct list_node *new_node)
 {
-  if (node == list->head)
-    list->head = node->next;
+  new_node->prev = pos_node->prev;
+  new_node->next = pos_node;
 
-  else
-    node->prev->next = node->next;
+  pos_node->prev->next = new_node;
+  pos_node->prev = new_node;
+}
 
-  if (node == list->tail)
-    list->tail = node->prev;
+void list_remove(struct list_node *del_node)
+{
+  del_node->next->prev = del_node->prev;
+  del_node->prev->next = del_node->next;
 
-  else
-    node->next->prev = node->prev;
+  list_node_init(del_node);
 }
+
+/*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */
index 383c8a8..f54693a 100644 (file)
@@ -37,7 +37,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: lq_list.h,v 1.5 2007/02/10 17:36:51 bernd67 Exp $
+ * $Id: lq_list.h,v 1.6 2007/09/05 16:11:10 bernd67 Exp $
  */
 
 #ifndef _LQ_LIST_H
@@ -47,32 +47,18 @@ struct list_node
 {
   struct list_node *next;
   struct list_node *prev;
-
   void *data;
 };
 
-struct list
-{
-  struct list_node *head;
-  struct list_node *tail;
-};
-
-void list_init(struct list *list);
-
-#define list_get_head(node) ((node)->head)
-#define list_get_tail(node) ((node)->tail)
-#define list_get_next(node) ((node)->next)
-#define list_get_prev(node) ((node)->prev)
-
-void list_add_head(struct list *list, struct list_node *node);
-void list_add_tail(struct list *list, struct list_node *node);
+void list_head_init(struct list_node *);
+void list_node_init(struct list_node *);
+int list_node_on_list(struct list_node *);
+int list_is_empty(struct list_node *);
 
-void list_add_before(struct list *list, struct list_node *pos_node,
-                     struct list_node *node);
-void list_add_after(struct list *list, struct list_node *pos_node,
-                    struct list_node *node);
+void list_add_before(struct list_node *, struct list_node *);
+void list_add_after(struct list_node *, struct list_node *);
 
-void list_remove(struct list *list, struct list_node *node);
+void list_remove(struct list_node *);
 
 #endif
 
index 7966933..8e5b656 100644 (file)
@@ -38,7 +38,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: lq_route.c,v 1.48 2007/08/02 22:07:19 bernd67 Exp $
+ * $Id: lq_route.c,v 1.49 2007/09/05 16:11:10 bernd67 Exp $
  */
 
 #include "defs.h"
@@ -65,10 +65,10 @@ struct olsr_spf_vertex
 {
   struct avl_node tree_node; /* node keyed by ip address */
   struct avl_node cand_tree_node; /* node keyed by etx */
-  struct avl_node path_tree_node; /* node keyed by etx */
+  struct list_node path_list_node; /* SPF result list */
   union olsr_ip_addr addr;
   struct avl_tree edge_tree;
-  union olsr_ip_addr *next_hop; /* the gateway router */
+  struct link_entry *next_hop; /* the link to the 1st hop neighbor */
   float path_etx;
   olsr_u8_t hops;
 };
@@ -137,25 +137,26 @@ olsr_spf_del_cand_tree (struct avl_tree *tree,
 }
 
 /*
- * olsr_spf_add_path_tree
+ * olsr_spf_add_path_list
  *
- * Key an existing vertex to a path tree.
+ * Insert an SPF result at the end of the path list.
  */
 static void
-olsr_spf_add_path_tree (struct avl_tree *tree,
+olsr_spf_add_path_list (struct list_node *head,
+                        int *path_count,
                         struct olsr_spf_vertex *vert)
 {
-  vert->path_tree_node.key = &vert->path_etx;
-  vert->path_tree_node.data = vert;
+  vert->path_list_node.data = vert;
 
 #ifdef DEBUG
-  OLSR_PRINTF(1, "SPF: insert path %s, cost %f, via %s\n",
+  OLSR_PRINTF(1, "SPF: append path %s, cost %f, via %s\n",
               olsr_ip_to_string(&(vert->addr)),
               vert->path_etx,
-              olsr_ip_to_string(vert->next_hop));
+              olsr_ip_to_string(vert->next_hop ? &vert->next_hop->neighbor_iface_addr : NULL));
 #endif
 
-  avl_insert(tree, &vert->path_tree_node, 1);
+  list_add_before(head, &vert->path_list_node);
+  *path_count = *path_count + 1;
 }
 
 /*
@@ -197,7 +198,7 @@ olsr_spf_add_vertex (struct avl_tree *vertex_tree,
   return vert;
 }
 
-static void
+static struct olsr_spf_vertex *
 olsr_spf_add_edge (struct avl_tree *vertex_tree,
                    union olsr_ip_addr *src, union olsr_ip_addr *dst,
                    float etx)
@@ -214,7 +215,7 @@ olsr_spf_add_edge (struct avl_tree *vertex_tree,
   // source vertex does not exist
 
   if (node == NULL)
-    return;
+    return NULL;
 
   svert = node->data;
 
@@ -225,7 +226,7 @@ olsr_spf_add_edge (struct avl_tree *vertex_tree,
   // destination vertex does not exist
 
   if (node == NULL)
-    return;
+    return NULL;
 
   dvert = node->data;
 
@@ -262,6 +263,8 @@ olsr_spf_add_edge (struct avl_tree *vertex_tree,
 
     avl_insert(&dvert->edge_tree, &edge->tree_node, 0);
   }
+
+  return svert;
 }
 
 static void olsr_free_everything(struct avl_tree *vertex_tree)
@@ -383,7 +386,8 @@ olsr_spf_relax (struct avl_tree *cand_tree, struct olsr_spf_vertex *vert)
                   olsr_ip_to_string(&(edge->dest->addr)),
                   olsr_etx_to_string(edge->dest->path_etx),
                   olsr_etx_to_string(new_etx),
-                  olsr_ip_to_string(vert->next_hop),
+                  olsr_ip_to_string(vert->next_hop ?
+                                    &vert->next_hop->neighbor_iface_addr : NULL),
                   edge->dest->hops);
 #endif
 
@@ -398,38 +402,40 @@ olsr_spf_relax (struct avl_tree *cand_tree, struct olsr_spf_vertex *vert)
  *
  * Run the Dijkstra algorithm.
  * 
- * We are using two trees: the candidate and the path tree.
  * A node gets added to the candidate tree when one of its edges has
  * an overall better root path cost than the node itself.
  * The node with the shortest metric gets moved from the candidate to
- * the path tree every pass.
+ * the path list every pass.
  * The SPF computation is completed when there are no more nodes
  * on the candidate tree. 
  */ 
 static void
-olsr_spf_run_full (struct avl_tree *cand_tree, struct avl_tree *path_tree)
+olsr_spf_run_full (struct avl_tree *cand_tree, struct list_node *path_list,
+                   int *path_count)
 {
   struct olsr_spf_vertex *vert;
 
+  *path_count = 0;
+
   while ((vert = olsr_spf_extract_best(cand_tree))) {
 
     olsr_spf_relax(cand_tree, vert);
 
     /*
      * move the best path from the candidate tree
-     * to the path tree.
+     * to the path list.
      */
     olsr_spf_del_cand_tree(cand_tree, vert);
-    olsr_spf_add_path_tree(path_tree, vert);
+    olsr_spf_add_path_list(path_list, path_count, vert);
   }
 }
 
 void
-olsr_calculate_lq_routing_table (void)
+olsr_calculate_routing_table (void)
 {
-  struct avl_tree vertex_tree, cand_tree, path_tree;
-  struct avl_node *tree_node;
-  int i;
+  struct avl_tree vertex_tree, cand_tree;
+  struct list_node path_list;
+  int i, plen, max_host_plen, path_count = 0;
   struct tc_entry *tcsrc;
   struct topo_dst *tcdst;
   struct olsr_spf_vertex *vert, *myself;
@@ -438,21 +444,25 @@ olsr_calculate_lq_routing_table (void)
   float etx;
   struct hna_entry *hna_gw;
   struct hna_net *hna;
-  struct rt_entry *gw_rt, *hna_rt, *head_rt;
   struct neighbor_2_entry *neigh2;
-#if 0
-  struct neighbor_list_entry *neigh_walker;
-#endif
   struct interface *inter;
+  struct link_entry *link;
 
-  if (olsr_cnf->ipsize != 4)
-    avl_comp_default = avl_comp_ipv6;
+#ifdef SPF_PROFILING
+  struct timeval t1, t2, t3, t4, t5, t6, spf_init, spf_run, route, kernel, cleanup, total;
+
+  gettimeofday(&t1, NULL);
+#endif
+
+  max_host_plen = olsr_host_rt_maxplen();
 
   // initialize the graph
 
   avl_init(&vertex_tree, avl_comp_default);
   avl_init(&cand_tree, avl_comp_etx);
-  avl_init(&path_tree, avl_comp_etx);
+  list_head_init(&path_list);
+
+  olsr_bump_routingtree_version();
 
   // add ourselves to the vertex and candidate tree
 
@@ -465,25 +475,11 @@ olsr_calculate_lq_routing_table (void)
   for (i = 0; i < HASHSIZE; i++)
     for (neigh = neighbortable[i].next; neigh != &neighbortable[i];
          neigh = neigh->next) {
-      if (neigh->status == SYM) {
 
-        vert = olsr_spf_add_vertex(&vertex_tree, &neigh->neighbor_main_addr,
-                                   INFINITE_ETX);
-
-        /*
-         * Set the next-hop pointer to ourselves.
-         * During olsr_spf_relax() the next_hop pointer will be
-         * pulled up to the new candidate node.
-         * At the End of the SPF computation every reachable node has
-         * a pointer to its corresponding first hop router.
-         */
-        vert->next_hop = &vert->addr;
-
-        /*
-         * one hop neighbors are just one hop away.
-         */
-        vert->hops = 1;
-      }
+      if (neigh->status != SYM)
+        continue;
+
+      olsr_spf_add_vertex(&vertex_tree, &neigh->neighbor_main_addr, INFINITE_ETX);
     }
 
   // add our two-hop neighbours
@@ -493,13 +489,7 @@ olsr_calculate_lq_routing_table (void)
          neigh2 != &two_hop_neighbortable[i];
          neigh2 = neigh2->next) {
 
-      vert = olsr_spf_add_vertex(&vertex_tree, &neigh2->neighbor_2_addr,
-                                 INFINITE_ETX);
-
-      /*
-       * two hop neighbors are two hops away.
-       */
-      vert->hops = 2;
+      olsr_spf_add_vertex(&vertex_tree, &neigh2->neighbor_2_addr, INFINITE_ETX);
     }
   // add remaining vertices
 
@@ -521,76 +511,64 @@ olsr_calculate_lq_routing_table (void)
 
   for (i = 0; i < HASHSIZE; i++)
     for (neigh = neighbortable[i].next; neigh != &neighbortable[i];
-         neigh = neigh->next)
-      if (neigh->status == SYM)
-      {
-        struct link_entry *lnk = get_best_link_to_neighbor(&neigh->neighbor_main_addr);
-
-       if(!lnk)
-         continue;
-
-        if (lnk->loss_link_quality2 >= MIN_LINK_QUALITY &&
-            lnk->neigh_link_quality2 >= MIN_LINK_QUALITY)
-          {
-            etx = 1.0 / (lnk->loss_link_quality2 * lnk->neigh_link_quality2);
+         neigh = neigh->next) {
 
-            olsr_spf_add_edge(&vertex_tree, &neigh->neighbor_main_addr, &olsr_cnf->main_addr, etx);
-          }
-      }
+      if (neigh->status == SYM) {
 
-// we now rely solely on TC messages for routes to our two-hop neighbours
+        link = get_best_link_to_neighbor(&neigh->neighbor_main_addr);
+       if (!link) {
+         continue;
+        }
 
-#if 0
+        if (olsr_cnf->lq_level < 2) {
+          /* for non-lq the etx is always 1.0 */
+          vert = olsr_spf_add_edge(&vertex_tree, &neigh->neighbor_main_addr,
+                                   &olsr_cnf->main_addr, 1.0 );
+          vert->next_hop = link;
 
-  // add edges between our neighbours and our two-hop neighbours
+        } else if (link->loss_link_quality2 >= MIN_LINK_QUALITY &&
+                   link->neigh_link_quality2 >= MIN_LINK_QUALITY) {
+            
+          etx = 1.0 / (link->loss_link_quality2 * link->neigh_link_quality2);
 
-  for (i = 0; i < HASHSIZE; i++)
-    for (neigh2 = two_hop_neighbortable[i].next;
-         neigh2 != &two_hop_neighbortable[i];
-         neigh2 = neigh2->next)
-      for (neigh_walker = neigh2->neighbor_2_nblist.next;
-           neigh_walker != &neigh2->neighbor_2_nblist;
-           neigh_walker = neigh_walker->next)
-      {
-        if (neigh_walker->second_hop_link_quality >=
-            MIN_LINK_QUALITY * MIN_LINK_QUALITY)
-        {
-          neigh = neigh_walker->neighbor;
-
-          etx = 1.0 / neigh_walker->second_hop_link_quality;
-
-          olsr_spf_add_edge(&vertex_tree, &neigh2->neighbor_2_addr,
-                   &neigh->neighbor_main_addr, etx);
+          vert = olsr_spf_add_edge(&vertex_tree, &neigh->neighbor_main_addr,
+                                     &olsr_cnf->main_addr, etx);
+          vert->next_hop = link;
         }
       }
+    }
 
-#endif
-
-  // add remaining edges
+  /* add remaining edges from TC messages */
 
   for (i = 0; i < HASHSIZE; i++)
     for (tcsrc = tc_table[i].next; tcsrc != &tc_table[i]; tcsrc = tcsrc->next)
       for (tcdst = tcsrc->destinations.next; tcdst != &tcsrc->destinations;
-           tcdst = tcdst->next)
-      {
-        if (tcdst->link_quality >= MIN_LINK_QUALITY &&
-            tcdst->inverse_link_quality >= MIN_LINK_QUALITY)
-          {
-            etx = 1.0 / (tcdst->link_quality * tcdst->inverse_link_quality);
-
-            olsr_spf_add_edge(&vertex_tree, &tcdst->T_dest_addr, &tcsrc->T_last_addr,
-                     etx);
-          }
+           tcdst = tcdst->next) {
+
+        if (olsr_cnf->lq_level < 2) {
+
+          /* for non-lq the etx is always 1.0 */
+          olsr_spf_add_edge(&vertex_tree, &tcdst->T_dest_addr,
+                            &tcsrc->T_last_addr, 1.0);
+
+        } else if (tcdst->link_quality >= MIN_LINK_QUALITY &&
+                   tcdst->inverse_link_quality >= MIN_LINK_QUALITY) {
+
+          etx = 1.0 / (tcdst->link_quality * tcdst->inverse_link_quality);
+
+          olsr_spf_add_edge(&vertex_tree, &tcdst->T_dest_addr,
+                            &tcsrc->T_last_addr, etx);
+        }
       }
 
+#ifdef SPF_PROFILING
+  gettimeofday(&t2, NULL);
+#endif
+
   /*
    * Run the SPF calculation.
    */
-  olsr_spf_run_full(&cand_tree, &path_tree);
-
-  // save the old routing table
-
-  olsr_move_route_table(routingtable, old_routes);
+  olsr_spf_run_full(&cand_tree, &path_list, &path_count);
 
   OLSR_PRINTF(2, "\n--- %02d:%02d:%02d.%02d ------------------------------------------------- DIJKSTRA\n\n",
               nowtm->tm_hour,
@@ -598,172 +576,99 @@ olsr_calculate_lq_routing_table (void)
               nowtm->tm_sec,
               (int)now.tv_usec/10000);
 
-  /*
-   * In the path tree we have all the reachable nodes
-   * in our topology sorted by etx metric.
-   */
-  for (tree_node = avl_walk_first(&path_tree);
-       tree_node != NULL;
-       tree_node = avl_walk_next(tree_node)) {
-    struct link_entry *lnk;
-    vert = tree_node->data;
-
-    if (!vert->next_hop) {
-      OLSR_PRINTF(2, "%s no next-hop\n", olsr_ip_to_string(&vert->addr));
-      continue;
-    }
-
-    // find the best link to the one-hop neighbour
-
-    lnk = get_best_link_to_neighbor(vert->next_hop);
-
-    // we may see NULL here, if the one-hop neighbour is not in the
-    // link and neighbour sets any longer, but we have derived an edge
-    // between us and the one-hop neighbour from the TC set
-
-    if (lnk != NULL)
-    {
-      // find the interface for the found link
-      inter = lnk->if_name ? if_ifwithname(lnk->if_name) : 
-              if_ifwithaddr(&lnk->local_iface_addr);
-
-      // we may see NULL here if the interface is down, but we have
-      // links that haven't timed out, yet
-
-      if (inter != NULL)
-      {
-        // XXX - fix me: structurally prevent duplicates, don't test via
-        //       olsr_lookup_routing_table()
-
-        // route addition, case A - add a route to the main address of the
-        // destination node
-
-        if (olsr_lookup_routing_table(&vert->addr) == NULL)
-          olsr_insert_routing_table(&vert->addr, &lnk->neighbor_iface_addr,
-                                    inter, vert->hops, vert->path_etx);
-
-        // route addition, case B - add routes to the remaining interfaces
-        // of the destination node
-
-        for (mid_walker = mid_lookup_aliases(&vert->addr); mid_walker != NULL;
-             mid_walker = mid_walker->next_alias)
-          if (olsr_lookup_routing_table(&mid_walker->alias) == NULL)
-            olsr_insert_routing_table(&mid_walker->alias,
-                                      &lnk->neighbor_iface_addr, inter, vert->hops, 
-                                      vert->path_etx);
-
-        // XXX - we used to use olsr_lookup_routing_table() only here, but
-        //       this assumed that case A or case B had already happened for
-        //       this destination; if case A or case B happened after case C
-        //       for the same destination, we had duplicates, as cases A and
-        //       B would not test whether case C had already happened
-
-        // route addition, case C - make sure that we have a route to the
-        // router - e.g. in case the router's not the main address and it's
-        // MID entry has timed out
-
-        if (olsr_lookup_routing_table(&lnk->neighbor_iface_addr) == NULL)
-          olsr_insert_routing_table(&lnk->neighbor_iface_addr,
-                                    &lnk->neighbor_iface_addr, inter, 1,
-                                    vert->path_etx);
-      }
-    }
-  }
-
-  // save the old HNA routing table
-
-  olsr_move_route_table(hna_routes, old_hna);
+#ifdef SPF_PROFILING
+  gettimeofday(&t3, NULL);
+#endif
 
-  // add HNA routes
+  olsr_fill_routing_table_with_neighbors();
 
   /*
-   * In the path tree we have all the reachable nodes
-   * in our topology sorted by etx metric.
+   * In the path tree we have all the reachable nodes in our topology.
    */
-  for (tree_node = avl_walk_first(&path_tree);
-       tree_node;
-       tree_node = avl_walk_next(tree_node)) {
-
-    if (!(vert = tree_node->data)) {
-      break;
-    }
-
-    // find the node's HNAs
-
-    hna_gw = olsr_lookup_hna_gw(&vert->addr);
+  for (; !list_is_empty(&path_list); list_remove(path_list.next)) {
 
-    // node doesn't announce any HNAs
+    vert = path_list.next->data;
+    link = vert->next_hop;
 
-    if (hna_gw == NULL)
+    if (!link) {
+      OLSR_PRINTF(2, "%s no next-hop\n", olsr_ip_to_string(&vert->addr));
       continue;
+    }
 
-    // find route to the node
+    /* find the interface for the found link */
+    inter = link->if_name ? if_ifwithname(link->if_name)
+      : if_ifwithaddr(&link->local_iface_addr);
 
-    gw_rt = olsr_lookup_routing_table(&hna_gw->A_gateway_addr);
+    /* interface is up ? */
+    if (inter) {
 
-    // maybe we haven't found a link or an interface for the gateway above
-    // and hence haven't added a route - skip the HNA in this case
+      /* add a route to the main address of the destination node */
+      olsr_insert_routing_table(&vert->addr, max_host_plen, &vert->addr,
+                                &link->neighbor_iface_addr, inter,
+                                vert->hops, vert->path_etx);
 
-    if (gw_rt == NULL)
-      continue;
+      /* add routes to the remaining interfaces of the destination node */
+      for (mid_walker = mid_lookup_aliases(&vert->addr);
+           mid_walker != NULL;
+           mid_walker = mid_walker->next_alias) {
 
-    // loop through the node's HNAs
+        olsr_insert_routing_table(&mid_walker->alias, max_host_plen, &vert->addr,
+                                  &link->neighbor_iface_addr, inter,
+                                  vert->hops, vert->path_etx);
+      }
 
-    for (hna = hna_gw->networks.next; hna != &hna_gw->networks;
-         hna = hna->next)
-    {
-      // we already have a route via a previous (better) node
+      /* find the node's HNAs */
+      hna_gw = olsr_lookup_hna_gw(&vert->addr);
 
-      if (olsr_lookup_hna_routing_table(&hna->A_network_addr) != NULL)
+      /* node doesn't announce any HNAs */
+      if (!hna_gw) {
         continue;
+      }
 
-      // create route for the HNA
-
-      hna_rt = olsr_malloc(sizeof(struct rt_entry), "LQ HNA route entry");
-
-      // set HNA IP address and netmask
-
-      COPY_IP(&hna_rt->rt_dst, &hna->A_network_addr);
-      hna_rt->rt_mask = hna->A_netmask;
-
-      // copy remaining fields from the node's route
-
-      COPY_IP(&hna_rt->rt_router, &gw_rt->rt_router);
-      hna_rt->rt_metric = gw_rt->rt_metric;
-      hna_rt->rt_etx = gw_rt->rt_etx;
-      hna_rt->rt_if = gw_rt->rt_if;
-
-      // we're not a host route
-
-      hna_rt->rt_flags = RTF_UP | RTF_GATEWAY;
-
-      // find the correct list
-
-      head_rt = &hna_routes[olsr_hashing(&hna->A_network_addr)];
-
-      // enqueue
-
-      head_rt->next->prev = hna_rt;
-      hna_rt->next = head_rt->next;
+      /* loop through the node's HNAs */
+      for (hna = hna_gw->networks.next;
+           hna != &hna_gw->networks;
+           hna = hna->next) {
 
-      head_rt->next = hna_rt;
-      hna_rt->prev = head_rt;
+        plen = olsr_get_hna_prefix_len(hna);
+        if (vert->path_etx != INFINITE_ETX)
+        olsr_insert_routing_table(&hna->A_network_addr, plen, &vert->addr,
+                                  &link->neighbor_iface_addr, inter,
+                                  vert->hops, vert->path_etx);
+      }
     }
   }
 
-  // free the graph
-
-  olsr_free_everything(&vertex_tree);
+#ifdef SPF_PROFILING
+  gettimeofday(&t4, NULL);
+#endif
 
-  // move the route changes into the kernel
+  /* move the route changes into the kernel */
 
   olsr_update_kernel_routes();
-  olsr_update_kernel_hna_routes();
 
-  // free the saved routing table
+#ifdef SPF_PROFILING
+  gettimeofday(&t5, NULL);
+#endif
+
+  /* free the SPF graph */
 
-  olsr_free_routing_table(old_routes);
-  olsr_free_routing_table(old_hna);
+  olsr_free_everything(&vertex_tree);
+
+#ifdef SPF_PROFILING
+  gettimeofday(&t6, NULL);
+
+  timersub(&t2, &t1, &spf_init);
+  timersub(&t3, &t2, &spf_run);
+  timersub(&t4, &t3, &route);
+  timersub(&t5, &t4, &kernel);
+  timersub(&t6, &t5, &cleanup);
+  timersub(&t6, &t1, &total);
+  olsr_printf(1, "\n--- SPF-stats for %d nodes, %d routes (total/init/run/route/kern/cleanup): %d, %d, %d, %d, %d, %d\n",
+              path_count, routingtree.count,
+              (int)total.tv_usec, (int)spf_init.tv_usec, (int)spf_run.tv_usec,
+              (int)route.tv_usec, (int)kernel.tv_usec,  (int)cleanup.tv_usec);
+#endif
 }
 
 /*
index 36d0b71..5cdf09c 100644 (file)
@@ -36,7 +36,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: lq_route.h,v 1.4 2007/07/05 22:43:47 bernd67 Exp $
+ * $Id: lq_route.h,v 1.5 2007/09/05 16:11:10 bernd67 Exp $
  */
 
 #ifndef _LQ_ROUTE_H
@@ -46,6 +46,6 @@
 #define ZERO_ETX 0.0
 #define MIN_LINK_QUALITY 0.01
 
-void olsr_calculate_lq_routing_table(void);
+void olsr_calculate_routing_table(void);
 
 #endif
index 1cb8446..345d3bb 100644 (file)
@@ -1,4 +1,3 @@
-
 /*
  * The olsr.org Optimized Link-State Routing daemon(olsrd)
  * Copyright (c) 2004, Andreas Tønnesen(andreto@olsr.org)
@@ -37,7 +36,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: main.c,v 1.96 2007/05/08 23:10:37 bernd67 Exp $
+ * $Id: main.c,v 1.97 2007/09/05 16:11:10 bernd67 Exp $
  */
 
 #include <unistd.h>
index 43d6bc0..7215fc2 100644 (file)
@@ -36,7 +36,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: net_olsr.c,v 1.28 2007/08/28 20:10:16 bernd67 Exp $
+ * $Id: net_olsr.c,v 1.29 2007/09/05 16:11:11 bernd67 Exp $
  */
 
 #include "net_olsr.h"
@@ -499,10 +499,12 @@ olsr_prefix_to_netmask(union olsr_ip_addr *adr, olsr_u16_t prefix)
 olsr_u16_t
 olsr_netmask_to_prefix(const union olsr_ip_addr *adr)
 {
-  int i;
   olsr_u16_t prefix = 0;
+  unsigned int i;
 
-  for (i = 0; i < 16; i++)
+  prefix = 0;
+
+  for(i = 0; i < olsr_cnf->ipsize; i++)
     {
       if(adr->v6.s6_addr[i] == 0xff)
        {
@@ -525,6 +527,22 @@ olsr_netmask_to_prefix(const union olsr_ip_addr *adr)
   return prefix;
 }
 
+/**
+ * olsr_host_rt_maxplen
+ *
+ * @return the maxium prefix length based wether v4 or v6 is configured 
+ */
+int
+olsr_host_rt_maxplen(void)
+{
+  if(olsr_cnf->ip_version == AF_INET) {
+    /* IPv4 */
+    return 32;
+  } else {
+    /* IPv6 */
+    return 128;
+  }
+}
 
 
 /**
@@ -658,3 +676,9 @@ olsr_validate_address(const union olsr_ip_addr *adr)
 
   return OLSR_TRUE;
 }
+
+/*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */
index 3b02bce..afef709 100644 (file)
@@ -36,7 +36,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: net_olsr.h,v 1.10 2007/08/20 18:46:03 bernd67 Exp $
+ * $Id: net_olsr.h,v 1.11 2007/09/05 16:11:11 bernd67 Exp $
  */
 
 
@@ -90,6 +90,9 @@ olsr_prefix_to_netmask(union olsr_ip_addr *, olsr_u16_t);
 olsr_u16_t
 olsr_netmask_to_prefix(const union olsr_ip_addr *);
 
+int
+olsr_host_rt_maxplen(void);
+
 char *
 sockaddr_to_string(const struct sockaddr *);
 
index 957566e..3dfd024 100644 (file)
@@ -36,7 +36,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: olsr.c,v 1.56 2007/08/01 16:22:57 bernd67 Exp $
+ * $Id: olsr.c,v 1.57 2007/09/05 16:11:11 bernd67 Exp $
  */
 
 /**
@@ -172,38 +172,18 @@ olsr_process_changes(void)
           olsr_calculate_lq_mpr();
         }
 
-      if (olsr_cnf->lq_level < 2)
-        {
-          olsr_calculate_routing_table();
-          olsr_calculate_hna_routes();
-        }
+      olsr_calculate_routing_table();
+      olsr_calculate_hna_routes();
     }
   
-  else if (changes_topology)
+  else if (changes_topology || changes_hna)
     {
       /* calculate the routing table and HNA */
 
-      if (olsr_cnf->lq_level < 2)
-        {
-          olsr_calculate_routing_table();
-          olsr_calculate_hna_routes();
-        }
+        olsr_calculate_routing_table();
+        olsr_calculate_hna_routes();
     }
 
-  else if (changes_hna)
-    {
-      /* update HNA routes */
-
-      if (olsr_cnf->lq_level < 2)
-        {
-          olsr_calculate_hna_routes();
-        }
-    }
-  
-  if (olsr_cnf->lq_level >= 2)
-    {
-      olsr_calculate_lq_routing_table();
-    }
   
   if (olsr_cnf->debug_level > 0)
     {      
@@ -264,8 +244,10 @@ olsr_init_tables(void)
   /* Set avl tree comparator */
   if (olsr_cnf->ipsize == 4) {
     avl_comp_default = NULL;
+    avl_comp_prefix_default = avl_comp_ipv4_prefix;
   } else {
     avl_comp_default = avl_comp_ipv6;
+    avl_comp_prefix_default = avl_comp_ipv6_prefix;
   }
 
   /* Initialize link set */
@@ -283,9 +265,6 @@ olsr_init_tables(void)
   /* Initialize two hop table */
   olsr_init_two_hop_table();
 
-  /* Initialize old route table */
-  olsr_init_old_table();
-
   /* Initialize topology */
   olsr_init_tc();
 
index 76f595a..f23f966 100644 (file)
@@ -36,7 +36,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: olsr_types.h,v 1.8 2007/06/28 22:34:52 bernd67 Exp $
+ * $Id: olsr_types.h,v 1.9 2007/09/05 16:11:11 bernd67 Exp $
  */
 
 /*
@@ -98,6 +98,12 @@ union olsr_ip_addr
   struct in6_addr v6;
 };
 
+struct olsr_ip_prefix
+{
+  union olsr_ip_addr prefix;
+  olsr_u8_t prefix_len;
+};
+
 union hna_netmask
 {
   olsr_u32_t v4;
index 1a113f5..3240d85 100644 (file)
@@ -1,6 +1,7 @@
 /*
  * The olsr.org Optimized Link-State Routing daemon(olsrd)
  * Copyright (c) 2004, Andreas Tønnesen(andreto@olsr.org)
+ * RIB implementation (c) 2007, Hannes Gredler (hannes@gredler.at)
  * All rights reserved.
  *
  * export_route_entry interface added by Immo 'FaUl Wehrenberg 
@@ -39,7 +40,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: process_routes.c,v 1.34 2007/08/02 22:07:19 bernd67 Exp $
+ * $Id: process_routes.c,v 1.35 2007/09/05 16:11:11 bernd67 Exp $
  */
 
 #include "defs.h"
@@ -47,6 +48,7 @@
 #include "log.h"
 #include "kernel_routes.h"
 #include <assert.h>
+#include "lq_avl.h"
 
 #ifdef WIN32
 #undef strerror
@@ -64,9 +66,36 @@ struct export_route_entry
 static struct export_route_entry *add_routes;
 static struct export_route_entry *del_routes;
 
+struct list_node add_kernel_list;
+struct list_node chg_kernel_list;
+struct list_node del_kernel_list;
 
-struct rt_entry old_routes[HASHSIZE];
-struct rt_entry old_hna[HASHSIZE];
+/**
+ *
+ * Calculate the kernel route flags.
+ * Called before enqueuing a change/delete operation
+ *
+ */
+olsr_u8_t
+olsr_rt_flags(struct rt_entry *rt)
+{
+  struct rt_nexthop *nh;
+  olsr_u8_t flags;
+
+  flags = (RTF_UP);
+
+  if (rt->rt_dst.prefix_len == olsr_host_rt_maxplen()) {
+    flags |= RTF_HOST;
+  }
+
+  nh = olsr_get_nh(rt);
+
+  if(!COMP_IP(&rt->rt_dst.prefix, &nh->gateway)) {
+    flags |= RTF_GATEWAY;
+  }
+
+  return flags;
+}
 
 void 
 olsr_addroute_add_function(int (*function)(struct rt_entry*), olsr_u8_t type) 
@@ -157,467 +186,355 @@ olsr_init_export_route(void)
 }
 
 int
-olsr_export_add_route (struct rt_entry *e
+olsr_export_add_route (struct rt_entry *rt
 {
   int retval = 0;
   struct export_route_entry *tmp;
   for (tmp = add_routes; tmp; tmp = tmp->next)
     {
       if (tmp->type == AF_INET)
-       retval = tmp->function(e);
+       retval = tmp->function(rt);
     }
   return retval;
 }
 
 int
-olsr_export_add_route6 (struct rt_entry *e
+olsr_export_add_route6 (struct rt_entry *rt
 {
   int retval = 0;
   struct export_route_entry *tmp;
   for (tmp = add_routes; tmp; tmp = tmp->next)
     {
       if (tmp->type == AF_INET6)
-       retval = tmp->function(e);
+       retval = tmp->function(rt);
     }
   return retval;
 }
 
 int
-olsr_export_del_route (struct rt_entry *e
+olsr_export_del_route (struct rt_entry *rt
 {
   int retval = 0;
   struct export_route_entry *tmp;
   for (tmp = del_routes; tmp; tmp = tmp->next)
     {
       if (tmp->type == AF_INET)
-       retval = tmp->function(e);
+       retval = tmp->function(rt);
     }
   return retval;
 }
 
 int
-olsr_export_del_route6 (struct rt_entry *e
+olsr_export_del_route6 (struct rt_entry *rt
 {
   int retval = 0;
   struct export_route_entry *tmp;
   for (tmp = del_routes; tmp; tmp = tmp->next)
     {
       if (tmp->type == AF_INET6)
-       retval = tmp->function(e);
+       retval = tmp->function(rt);
     }
   return retval;
 }
 
-
-
-int
-olsr_init_old_table(void)
-{
-  int idx;
-
-  for(idx=0;idx<HASHSIZE;idx++)
-    {
-      old_routes[idx].next = &old_routes[idx];
-      old_routes[idx].prev = &old_routes[idx];
-      old_hna[idx].next = &old_hna[idx];
-      old_hna[idx].prev = &old_hna[idx];
-    }
-
-  return 1;
-}
-
 /**
- *Checks if there exists a route to a given host
- *in a given hash table.
+ *Deletes all OLSR routes
  *
- *@param dst the host to check for
- *@param table the table to check
+ * This is extremely simple - Just increment the version of the
+ * tree and then olsr_update_kernel_routes() will see
+ * all routes in the tree as outdated and flush it.
  *
- *@return 1 if the host exists in the table, 0 if not
+ *@return 1
  */
 int
-olsr_find_up_route(struct rt_entry *dst, struct rt_entry *table)
+olsr_delete_all_kernel_routes(void)
 { 
-  struct rt_entry  *destination;
-  const olsr_u32_t  hash = olsr_hashing(&dst->rt_dst);
+  OLSR_PRINTF(1, "Deleting all routes...\n");
 
-  for(destination = table[hash].next; destination != &table[hash]; destination = destination->next)
-    {
-      //printf("Checking %s hc: %d ", olsr_ip_to_string(&dst->rt_dst), dst->rt_metric);
-      //printf("vs %s hc: %d ... ", olsr_ip_to_string(&destination->rt_dst), destination->rt_metric);      
-      if (COMP_IP(&destination->rt_dst, &dst->rt_dst) &&
-         COMP_IP(&destination->rt_router, &dst->rt_router) &&
-         (destination->rt_if->if_index == dst->rt_if->if_index))
-       {
-         if(destination->rt_metric == dst->rt_metric)
-           {
-             return 1;
-           }
-         else
-           {
-             return 0;
-           }
-       }
-    }
-  return 0;
+  olsr_bump_routingtree_version();
+  olsr_update_kernel_routes();
+
+  return 1;
 }
 
+/**
+ * Enqueue a route on a kernel add/chg/del queue.
+ */
+static void
+olsr_enqueue_rt(struct list_node *head_node, struct rt_entry *rt)
+{
+  struct rt_nexthop *nh;
+
+  /* if this node is already on some changelist we are done */
+  if (list_node_on_list(&rt->rt_change_node)) {
+    return;
+  }
+
+  rt->rt_change_node.data = rt;
+
+  /*
+   * For easier route dependency tracking we enqueue nexthop routes
+   * at the head of the queue and non-nexthop routes at the tail of the queue.
+   */
+  nh = olsr_get_nh(rt);
+
+  if (COMP_IP(&rt->rt_dst.prefix, &nh->gateway)) {
+    list_add_after(head_node, &rt->rt_change_node);
+  } else {
+    list_add_before(head_node, &rt->rt_change_node);
+  }
+}
 
 /**
- *Create a list containing the entries in from_table
- *that do not exist in in_table
- *
- *@param from_table the table to use
- *@param in_table the routes already added
+ * Process a route from the kernel deletion list.
  *
- *@return a poiter to a linked list of routes to add
+ *@return nada
  */
-struct destination_n *
-olsr_build_update_list(struct rt_entry *from_table,struct rt_entry *in_table)
+static void
+olsr_delete_kernel_route(struct rt_entry *rt)
 {
-  struct destination_n *kernel_route_list = NULL;
-  struct rt_entry      *destination;
-  int                   idx;
-  
-  for(idx=0;idx<HASHSIZE;idx++)
-    {
-      for(destination = from_table[idx].next;
-         destination != &from_table[idx];
-         destination = destination->next)
-       {
-         if (!olsr_find_up_route(destination, in_table))
-           {
-             struct destination_n *route_list;
-             route_list = olsr_malloc(sizeof(struct destination_n), "create route tmp list");
-             
-             route_list->destination = destination;
-             
-             route_list->next = kernel_route_list;
-             kernel_route_list = route_list;
-           }
-       }   
+  olsr_16_t error;               
+
+  if(!olsr_cnf->host_emul) {
+
+    if(olsr_cnf->ip_version == AF_INET) {
+      error = olsr_export_del_route(rt);
+    } else {
+      error = olsr_export_del_route6(rt);
     }
-  
-  return (kernel_route_list);
-}
 
+    if(error < 0) {
+      const char * const err_msg = strerror(errno);
 
+      OLSR_PRINTF(1, "KERN: ERROR deleting %s: %s\n",
+                  olsr_rt_to_string(rt), err_msg);
 
+      olsr_syslog(OLSR_LOG_ERR, "Delete route: %s", err_msg);
 
+    }
+  }
+}
 
 /**
- *Deletes all OLSR routes
+ * Process a route from the kernel addition list.
  *
- *
- *@return 1
+ *@return nada
  */
-int
-olsr_delete_all_kernel_routes(void)
-{ 
-  struct destination_n *delete_kernel_list;
-  struct destination_n *tmp;
-
-  OLSR_PRINTF(1, "Deleting all routes...\n");
+static void
+olsr_add_kernel_route(struct rt_entry *rt)
+{
+  olsr_16_t error;               
 
-  delete_kernel_list = olsr_build_update_list(hna_routes, old_hna);
+  if(!olsr_cnf->host_emul) {
 
-  OLSR_PRINTF(1, "HNA list:\n");
-  for(tmp = delete_kernel_list;tmp;tmp = tmp->next)
-    {
-      union olsr_ip_addr *tmp_addr = &tmp->destination->rt_dst;
-      OLSR_PRINTF(1, "Dest: %s\n", olsr_ip_to_string(tmp_addr));
+    if(olsr_cnf->ip_version == AF_INET) {
+      error = olsr_export_add_route(rt);
+    } else {
+      error = olsr_export_add_route6(rt);
     }
+    
+    if(error < 0) {
+      const char * const err_msg = strerror(errno);
+      OLSR_PRINTF(1, "KERN: ERROR adding %s: %s\n",
+                  olsr_rtp_to_string(rt->rt_best), err_msg);
 
-  olsr_delete_routes_from_kernel(delete_kernel_list);
+      olsr_syslog(OLSR_LOG_ERR, "Add route: %s", err_msg);
+    } else {
 
-  delete_kernel_list = olsr_build_update_list(routingtable,old_routes);
+      /* route addition has suceeded */
 
-  OLSR_PRINTF(1, "Route list:\n");
-  for(tmp = delete_kernel_list;tmp;tmp = tmp->next)
-    {
-      union olsr_ip_addr *tmp_addr = &tmp->destination->rt_dst;
-      OLSR_PRINTF(1, "Dest: %s\n", olsr_ip_to_string(tmp_addr));
+      /* save the nexthop in the route entry */
+      rt->rt_nexthop = rt->rt_best->rtp_nexthop;
     }
-  olsr_delete_routes_from_kernel(delete_kernel_list);
-  return 1;
+  }
 }
 
-
 /**
- *Perform all neccessary actions for an update of the 
- *routes in the kernel.
- *
- *@return nada
+ * process the kernel add list.
+ * the routes are already ordered such that nexthop routes
+ * are on the head of the queue.
+ * nexthop routes need to be added first and therefore
+ * the queue needs to be traversed from head to tail.
  */
-void
-olsr_update_kernel_routes(void)
+static void
+olsr_add_kernel_routes(struct list_node *head_node)
 {
-  struct destination_n *delete_kernel_list;
-  struct destination_n *add_kernel_list;
+  struct rt_entry *rt;
 
-  OLSR_PRINTF(3, "Updating kernel routes...\n");
-  delete_kernel_list = olsr_build_update_list(old_routes, routingtable);
-  add_kernel_list = olsr_build_update_list(routingtable, old_routes);
+  while (!list_is_empty(head_node)) {
 
-  olsr_delete_routes_from_kernel(delete_kernel_list);
-  olsr_add_routes_in_kernel(add_kernel_list);
-}
+    rt = head_node->next->data;
+    olsr_add_kernel_route(rt);
 
+    list_remove(&rt->rt_change_node);
+  }
+}
 
+/**
+ * process the kernel change list.
+ * the routes are already ordered such that nexthop routes
+ * are on the head of the queue.
+ * non-nexthop routes need to be changed first and therefore
+ * the queue needs to be traversed from tail to head.
+ */
+static void
+olsr_chg_kernel_routes(struct list_node *head_node)
+{
+  struct rt_entry *rt;
+  struct list_node *node;
+
+  if (list_is_empty(head_node)) {
+    return;
+  }
+
+  /*
+   * First pass.
+   * traverse from the end to the beginning of the list,
+   * such that nexthop routes are deleted last.
+   */
+  for (node = head_node->prev; head_node != node; node = node->prev) {
+
+    rt = node->data;
+    olsr_delete_kernel_route(rt);
+  }
+
+  /*
+   * Second pass.
+   * Traverse from the beginning to the end of the list,
+   * such that nexthop routes are added first.
+   */
+  while (!list_is_empty(head_node)) {
+
+    rt = head_node->next->data;
+    olsr_add_kernel_route(rt);
+
+    list_remove(&rt->rt_change_node);
+  }
+}
 
 /**
- *Perform all neccessary actions for an update of the 
- *HNA routes in the kernel.
- *
- *@return nada
+ * process the kernel delete list.
+ * the routes are already ordered such that nexthop routes
+ * are on the head of the queue.
+ * non-nexthop routes need to be deleted first and therefore
+ * the queue needs to be traversed from tail to head.
  */
-void
-olsr_update_kernel_hna_routes(void)
+static void
+olsr_del_kernel_routes(struct list_node *head_node)
 {
-  struct destination_n *delete_kernel_list;
-  struct destination_n *add_kernel_list;
+  struct rt_entry *rt;
 
-  OLSR_PRINTF(3, "Updating kernel HNA routes...\n");
+  while (!list_is_empty(head_node)) {
 
-  delete_kernel_list = olsr_build_update_list(old_hna, hna_routes);
-  add_kernel_list = olsr_build_update_list(hna_routes, old_hna);
+    rt = head_node->prev->data;
+    olsr_delete_kernel_route(rt);
 
-  olsr_delete_routes_from_kernel(delete_kernel_list);
-  olsr_add_routes_in_kernel(add_kernel_list);
+    list_remove(&rt->rt_change_node);
+    free(rt);
+  }
 }
 
-
 /**
- *Create a copy of the routing table and
- *clear the current table
- *
- *@param original the table to move from
- *@param the table to move to
- *
- *@return nada
+ * Check the version number of all route paths hanging off a route entry.
+ * If a route does not match the current routing tree number, delete it.
+ * Reset the best route pointer.
  */
-void
-olsr_move_route_table(struct rt_entry *original, struct rt_entry *new)
+static void
+olsr_delete_outdated_routes(struct rt_entry *rt)
 {
-  int idx;
+  struct rt_path *rtp;
+  struct avl_node *rtp_tree_node, *next_rtp_tree_node;
 
-  for(idx=0;idx<HASHSIZE;idx++)
-    {
-      if(original[idx].next == &original[idx])
-       {
-         new[idx].next = &new[idx];
-         new[idx].prev = &new[idx];
-       }
-      else
-       {
-         /* Copy to old */
-         new[idx].next = original[idx].next;
-         new[idx].next->prev = &new[idx];
-         new[idx].prev = original[idx].prev;
-         new[idx].prev->next = &new[idx];
-
-         /* Clear original */
-         original[idx].next = &original[idx];
-         original[idx].prev = &original[idx];
-       }
+  for (rtp_tree_node = avl_walk_first(&rt->rt_path_tree);
+       rtp_tree_node;
+       rtp_tree_node = next_rtp_tree_node) {
+
+    /*
+     * pre-fetch the next node before loosing context.
+     */
+    next_rtp_tree_node = avl_walk_next(rtp_tree_node);
+
+    rtp = rtp_tree_node->data;
+
+    /*
+     * check the version number which gets incremented on every SPF run.
+     * comparing for unequalness avoids handling version number wraps.
+     */
+    if (routingtree_version != rtp->rtp_version) {
+
+      /* remove from the originator tree */
+      avl_delete(&rt->rt_path_tree, rtp_tree_node);
+      free(rtp);
     }
-}
+  }
 
+  /* safety measure against dangling pointers */
+  rt->rt_best = NULL;
+}
 
 /**
- *Delete a linked list of routes from the kernel.
- *
- *@param delete_kernel_list the list to delete
- *
- *@return nada
+ * Walk all the routes, remove outdated routes and run
+ * best path selection on the remaining set.
+ * Finally compare the nexthop of the route head and the best
+ * path and enqueue a add/chg operation.
  */
-void 
-olsr_delete_routes_from_kernel(struct destination_n *delete_kernel_list)
+void
+olsr_update_kernel_routes(void)
 {
-  struct destination_n *destination_ptr;
-  int metric_counter = 1;
-  olsr_bool last_run = OLSR_FALSE;
+  struct rt_entry *rt;
 
+  OLSR_PRINTF(3, "Updating kernel routes...\n");
 
-  /* Find highest metric */
-  for(destination_ptr = delete_kernel_list;
-      destination_ptr != NULL;
-      destination_ptr = destination_ptr->next)
-    {
-      if(destination_ptr->destination->rt_metric > metric_counter)
-       metric_counter = destination_ptr->destination->rt_metric;
-    }
+  /* walk all routes in the RIB. */
 
-#ifdef DEBUG
-  OLSR_PRINTF(3, "%s highest metric %d\n",
-             __func__, metric_counter);
-#endif
-  while(delete_kernel_list!=NULL)
-    {
-      struct destination_n *previous_node = delete_kernel_list;
+  OLSR_FOR_ALL_RT_ENTRIES(rt) {
 
-      assert(metric_counter);
+    /* eliminate first unused routes */
+    olsr_delete_outdated_routes(rt);
 
-      /* searching for all the items with metric equal to n */
-      for(destination_ptr = delete_kernel_list; destination_ptr != NULL; )
-       {
+    if (!rt->rt_path_tree.count) {
 
-         if(destination_ptr->destination->rt_metric == metric_counter)
-           {
-             /* Make sure one-hop direct neighbors are deleted last */
-             if(metric_counter == 1 &&
-                (!last_run && 
-                 COMP_IP(&destination_ptr->destination->rt_dst, 
-                         &destination_ptr->destination->rt_router)))
-               {
-                 previous_node = destination_ptr;
-                 destination_ptr = destination_ptr->next;
-               }
-             else
-               {
-                 olsr_16_t error;                
-#ifdef DEBUG
-                 OLSR_PRINTF(3, "Deleting route to %s hopcount %d\n",
-                             olsr_ip_to_string(&destination_ptr->destination->rt_dst),
-                             destination_ptr->destination->rt_metric);
-#endif
-                   if(!olsr_cnf->host_emul)
-                     {
-                       if(olsr_cnf->ip_version == AF_INET)
-                         error = olsr_export_del_route(destination_ptr->destination);
-                       else
-                         error = olsr_export_del_route6(destination_ptr->destination);
-                       
-                       if(error < 0)
-                         {
-                            const char * const err_msg = strerror(errno);
-                           OLSR_PRINTF(1, "Delete route(%s):%s\n", olsr_ip_to_string(&destination_ptr->destination->rt_dst), err_msg);
-                            olsr_syslog(OLSR_LOG_ERR, "Delete route:%s", err_msg);
-                         }
-                   }
-                 
-                 /* Getting rid of this node and hooking up the broken point */
-                 if(destination_ptr == delete_kernel_list) 
-                   {
-                     destination_ptr = delete_kernel_list->next;
-                     free(delete_kernel_list);
-                     delete_kernel_list = destination_ptr;
-                     previous_node = delete_kernel_list;
-                   }
-                 else 
-                   {
-                     previous_node->next = destination_ptr->next;
-                     free(destination_ptr);
-                     destination_ptr = previous_node->next;
-                   }
-               }
-           }
-         else 
-           {
-             previous_node = destination_ptr;
-             destination_ptr = destination_ptr->next;
-           }
-               
-       }
-      if((metric_counter == 1) && !last_run)
-        {
-         last_run = OLSR_TRUE;
-        }
-      else
-        {
-         metric_counter--;
-        }
+      /* oops, all routes are gone - flush the route head */
+      avl_delete(&routingtree, rt_tree_node);
+
+      olsr_enqueue_rt(&del_kernel_list, rt);
+      continue;
     }
-}
 
-/**
- *Add a list of routes to the kernel. Adding
- *is done by hopcount to be sure a route
- *to the nexthop is added.
- *
- *@param add_kernel_list the linked list of routes to add
- *
- *@return nada
- */
-void 
-olsr_add_routes_in_kernel(struct destination_n *add_kernel_list)
-{
-  int metric_counter = 1;
-  olsr_bool first_run = OLSR_TRUE;
-  
-  while(add_kernel_list != NULL)
-    {
-      struct destination_n *destination_kernel = NULL;
-      struct destination_n *previous_node = add_kernel_list;
+    /* run best route election */
+    olsr_rt_best(rt);
 
-      /* searching for all the items with metric equal to n */
-      for(destination_kernel = add_kernel_list; destination_kernel != NULL; )
-       {
-         if((destination_kernel->destination->rt_metric == metric_counter) &&
-            (!first_run || 
-              COMP_IP(&destination_kernel->destination->rt_dst,
-                      &destination_kernel->destination->rt_router)))
-           {
-             olsr_16_t error;
-             /* First add all 1-hop routes that has themselves as GW */
+    /* nexthop change ? */
+    if (olsr_nh_change(&rt->rt_best->rtp_nexthop, &rt->rt_nexthop)) {
 
-#ifdef DEBUG
-             OLSR_PRINTF(3, "Adding route to %s hopcount %d\n",
-                         olsr_ip_to_string(&destination_kernel->destination->rt_dst),
-                         destination_kernel->destination->rt_metric);
-#endif
-                         
-               if(!olsr_cnf->host_emul)
-                 {
-                   if(olsr_cnf->ip_version == AF_INET)
-                     error=olsr_export_add_route(destination_kernel->destination);
-                   else
-                     error=olsr_export_add_route6(destination_kernel->destination);
-                   
-                   if(error < 0)
-                     {
-                        const char * const err_msg = strerror(errno);
-                       OLSR_PRINTF(1, "Add route(%s): %s\n", olsr_ip_to_string(&destination_kernel->destination->rt_dst), err_msg);
-                        olsr_syslog(OLSR_LOG_ERR, "Add route:%s", err_msg);
-                     }
-                 }
-
-             
-             /* Getting rid of this node and hooking up the broken point */
-             if(destination_kernel == add_kernel_list) 
-               {
-                 destination_kernel = add_kernel_list->next;
-                 free(add_kernel_list);
-                 add_kernel_list = destination_kernel;
-                 previous_node=add_kernel_list;
-               }
-             else 
-               {
-                 previous_node->next = destination_kernel->next;
-                 free(destination_kernel);
-                 destination_kernel = previous_node->next;
-               }
-           }
-         else 
-           {
-             previous_node = destination_kernel;
-             destination_kernel = destination_kernel->next;
-           }
-               
-       }
-      if(first_run)
-        {
-         first_run = OLSR_FALSE;
-        }
-      else
-        {
-         metric_counter++;
-        }
+      if (!rt->rt_nexthop.iface) {
+
+        /* fresh routes do have NULL pointers in the nexthop fields. */
+        olsr_enqueue_rt(&add_kernel_list, rt);
+      } else { 
+
+        /* this is a route change. */
+        olsr_enqueue_rt(&chg_kernel_list, rt);
+      }
     }
-       
-}
+  } OLSR_FOR_ALL_RT_ENTRIES_END(rt);
+
+  /* delete unreachable routes */
+  olsr_del_kernel_routes(&del_kernel_list);
+
+  /* route changes */
+  olsr_chg_kernel_routes(&chg_kernel_list);
 
+  /* route additions */
+  olsr_add_kernel_routes(&add_kernel_list);
 
+#if DEBUG
+  olsr_print_routing_table(&routingtree);
+#endif
+}
 
+/*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */
index 1032534..953c2e5 100644 (file)
@@ -36,7 +36,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: process_routes.h,v 1.10 2007/01/31 12:36:50 bernd67 Exp $
+ * $Id: process_routes.h,v 1.11 2007/09/05 16:11:11 bernd67 Exp $
  */
 
 #include "routing_table.h"
@@ -47,8 +47,9 @@
 
 #include <sys/ioctl.h>
 
-extern struct rt_entry old_routes[HASHSIZE];
-extern struct rt_entry old_hna[HASHSIZE];
+extern struct list_node add_kernel_list;
+extern struct list_node chg_kernel_list;
+extern struct list_node del_kernel_list;
 
 void
 olsr_init_export_route(void);
@@ -77,32 +78,13 @@ olsr_export_add_route6 (struct rt_entry*);
 int
 olsr_export_del_route6 (struct rt_entry*); 
 
-
-int
-olsr_init_old_table(void);
-
-int
-olsr_find_up_route(struct rt_entry *dst,struct rt_entry *table);
-
-struct destination_n *
-olsr_build_update_list(struct rt_entry *from_table, struct rt_entry *in_table);
-
 void
 olsr_update_kernel_routes(void);
 
-void
-olsr_update_kernel_hna_routes(void);
-
-void
-olsr_move_route_table(struct rt_entry *, struct rt_entry *);
-
-void
-olsr_delete_routes_from_kernel(struct destination_n *delete_kernel_list);
-
-void
-olsr_add_routes_in_kernel(struct destination_n *add_kernel_list);
-
 int
 olsr_delete_all_kernel_routes(void);
 
+olsr_u8_t
+olsr_rt_flags(struct rt_entry *);
+
 #endif
index 84d4316..01458ae 100644 (file)
@@ -1,6 +1,7 @@
 /*
  * The olsr.org Optimized Link-State Routing daemon(olsrd)
  * Copyright (c) 2004, Andreas Tønnesen(andreto@olsr.org)
+ * RIB implementation (c) 2007, Hannes Gredler (hannes@gredler.at)
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without 
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: routing_table.c,v 1.28 2007/08/02 21:54:54 bernd67 Exp $
+ * $Id: routing_table.c,v 1.29 2007/09/05 16:11:11 bernd67 Exp $
  */
 
-
-
 #include "defs.h"
 #include "two_hop_neighbor_table.h"
 #include "tc_set.h"
 #include "olsr.h"
 #include "link_set.h"
 #include "routing_table.h"
+#include "lq_avl.h"
+#include "lq_route.h"
+#include "assert.h"
 
+struct avl_tree routingtree;
+unsigned int routingtree_version;
 
-struct rt_entry routingtable[HASHSIZE];
-struct rt_entry hna_routes[HASHSIZE];
-
-
-/* Begin:
- * Prototypes for internal functions 
+/**
+ * Bump the version number of the routing tree.
+ *
+ * After route-insertion compare the version number of the routes
+ * against the version number of the table.
+ * This is a lightweight detection if a node or prefix went away,
+ * rather than brute force old vs. new rt_entry comparision.
  */
+unsigned int
+olsr_bump_routingtree_version(void)
+{
+  return(routingtree_version++);
+}
 
-static int
-olsr_fill_routing_table_with_neighbors(void);
-
-static struct destination_n *
-olsr_fill_routing_table_with_two_hop_neighbors(void);
-
-static struct rt_entry *
-olsr_check_for_higher_quality(struct rt_entry *, struct hna_net *, float);
-
-struct rt_entry *
-olsr_check_for_lower_quality(struct rt_entry *, struct hna_net *, float);
-
-static olsr_bool
-two_hop_neighbor_reachable(struct neighbor_2_list_entry *);
-
-/* End:
- * Prototypes for internal functions 
+/**
+ * avl_comp_ipv4_prefix
+ *
+ * compare two ipv4 prefixes.
+ * first compare the prefixes, then
+ *  then compare the prefix lengths.
+ *
+ * return 0 if there is an exact match and
+ * -1 / +1 depending on being smaller or bigger.
  */
+int
+avl_comp_ipv4_prefix (void *prefix1, void *prefix2)
+{       
+  struct olsr_ip_prefix *pfx1, *pfx2;
+
+  pfx1 = prefix1;
+  pfx2 = prefix2;
+
+  /* prefix */
+  if (pfx1->prefix.v4 < pfx2->prefix.v4) {
+    return -1;
+  }
+  if (pfx1->prefix.v4 > pfx2->prefix.v4) {
+    return +1;
+  }
+
+  /* prefix length */
+  if (pfx1->prefix_len < pfx2->prefix_len) {
+    return -1;
+  }
+  if (pfx1->prefix_len > pfx2->prefix_len) {
+    return +1;
+  }
+
+  return 0;
+}
 
+/**
+ * avl_comp_ipv6_prefix
+ *
+ * compare two ipv6 prefixes.
+ * first compare the prefixes, then
+ *  then compare the prefix lengths.
+ *
+ * return 0 if there is an exact match and
+ * -1 / +1 depending on being smaller or bigger.
+ */
+int
+avl_comp_ipv6_prefix (void *prefix1, void *prefix2)
+{       
+  struct olsr_ip_prefix *pfx1, *pfx2;
+  int res;
+
+  pfx1 = prefix1;
+  pfx2 = prefix2;
+
+  /* prefix */
+  res = memcmp(&pfx1->prefix.v6, &pfx2->prefix.v6, 16);
+  if (res != 0) {
+    return res;
+  } 
+  /* prefix length */
+  if (pfx1->prefix_len < pfx2->prefix_len) {
+    return -1;
+  }
+  if (pfx1->prefix_len > pfx2->prefix_len) {
+    return +1;
+  }
+
+  return 0;
+}
 
 /**
- *Initialize the routing table
+ * Initialize the routingtree and kernel change queues.
  */
 int
 olsr_init_routing_table(void)
 {
-  int idx;
-  /*
-   *The hna routes hash will almost always
-   *be indexed to 0
-   *But it is kept as a hash to be compatible
-   *with the functions used on the regular
-   *routing table
-   */
-  for(idx=0;idx<HASHSIZE;idx++)
-    {
-      routingtable[idx].next = &routingtable[idx];
-      routingtable[idx].prev = &routingtable[idx];
-      hna_routes[idx].next = &hna_routes[idx];
-      hna_routes[idx].prev = &hna_routes[idx];
-    }
+  /* the routing tree */
+  avl_init(&routingtree, avl_comp_prefix_default);
+  routingtree_version = 0;
+
+  /* the add/chg/del kernel queues */
+  list_head_init(&add_kernel_list);
+  list_head_init(&chg_kernel_list);
+  list_head_init(&del_kernel_list);
+
   return 1;
 }
 
 /**
- *Look up an entry in the routing table.
+ * Look up a maxplen entry (= /32 or /128) in the routing table.
  *
- *@param dst the address of the entry
+ * @param dst the address of the entry
  *
- *@return a pointer to a rt_entry struct 
- *representing the route entry.
+ * @return a pointer to a rt_entry struct 
+ * representing the route entry.
  */
 struct rt_entry *
 olsr_lookup_routing_table(union olsr_ip_addr *dst)
 {
+  struct avl_node *rt_tree_node;
+  struct olsr_ip_prefix prefix;
 
-  struct rt_entry *rt_table;
-  olsr_u32_t      hash = olsr_hashing(dst);
+  COPY_IP(&prefix, dst);
+  prefix.prefix_len = olsr_host_rt_maxplen();
 
-  for(rt_table = routingtable[hash].next;
-      rt_table != &routingtable[hash];
-      rt_table = rt_table->next)
-    {
-      if (COMP_IP(&rt_table->rt_dst, dst))
-       {
-         return rt_table;
-       }
-    }
-  return NULL;
-  
+  rt_tree_node = avl_find(&routingtree, &prefix);
+
+  return (rt_tree_node ? rt_tree_node->data : NULL);
 }
 
 /**
- * Look up an entry in the HNA routing table.
- *
- * @param dst the address of the entry
- *
- * @return a pointer to a rt_entry struct 
- * representing the route entry.
+ * Update the fields in an routing entry.
+ * Depending on the update mask update either the old,
+ * the new or both arrays for gateway/interface/etx/hopcount.
  */
-
-struct rt_entry *
-olsr_lookup_hna_routing_table(union olsr_ip_addr *dst)
+static void
+olsr_update_routing_entry(struct rt_path *rtp, union olsr_ip_addr *gateway,
+                          struct interface *iface, int metric, float etx)
 {
-  struct rt_entry *walker;
-  olsr_u32_t hash = olsr_hashing(dst);
 
-  for (walker = hna_routes[hash].next; walker != &hna_routes[hash];
-       walker = walker->next)
-    if (COMP_IP(&walker->rt_dst, dst))
-      return walker;
+  rtp->rtp_version = routingtree_version;
+
+  /* gateway */
+  rtp->rtp_nexthop.gateway = *gateway;
 
-  return NULL;
+  /* interface */
+  rtp->rtp_nexthop.iface = iface;
+
+  /* etx */
+  rtp->rtp_metric.hops = metric;
+  if (etx < 0.0) {
+    /* non-LQ case */
+    rtp->rtp_metric.etx = (float)metric;
+  } else {
+    /* LQ case */
+    rtp->rtp_metric.etx = etx;
+  }
 }
 
 /**
- *Delete all the entries in the routing table hash
- *
- *@param table the routing hash table
- *
- *@return nada
+ * Alloc and key a new rt_entry.
  */
-void
-olsr_free_routing_table(struct rt_entry *table)
+static struct rt_entry *
+olsr_alloc_rt_entry(struct olsr_ip_prefix *prefix)
 {
-  int idx;
-  
-  for(idx=0;idx<HASHSIZE;idx++)
-    {
-      struct rt_entry *destination = table[idx].next;
+  struct rt_entry *rt;
 
-      while(destination != &table[idx])
-       {
-         struct rt_entry *dst_to_delete = destination;
-         destination = destination->next;
+  rt = olsr_malloc(sizeof(struct rt_entry), __FUNCTION__);
 
-         DEQUEUE_ELEM(dst_to_delete);
-         free(dst_to_delete);
-       }
-    }
+  if (!rt) {
+    return NULL;
+  }
 
+  memset(rt, 0, sizeof(struct rt_entry));
+
+  /* set key and backpointer prior to tree insertion */
+  rt->rt_dst = *prefix;
+
+  rt->rt_tree_node.key = &rt->rt_dst;
+  rt->rt_tree_node.data = rt;
+  avl_insert(&routingtree, &rt->rt_tree_node, AVL_DUP_NO);
+
+  /* init the originator subtree */
+  avl_init(&rt->rt_path_tree, avl_comp_default);
+
+  return rt;
 }
 
 
 /**
- *Insert an 1 or 2 neighbor-entry into the routing table.
- *
- *@param dst the destination
- *
- *@return the new rt_entry struct
+ * Alloc and key a new rt_path.
  */
-struct rt_entry *
-olsr_insert_routing_table(union olsr_ip_addr *dst, 
-                         const union olsr_ip_addr *router, 
-                         struct interface *iface, 
-                         int metric,
-                         float etx)
+static struct rt_path *
+olsr_alloc_rt_path(struct rt_entry *rt,
+                   union olsr_ip_addr *originator)
 {
-  const olsr_u32_t hash = olsr_hashing(dst);
-  struct rt_entry *rt_list = &routingtable[hash];
-  struct rt_entry *new_route_entry = olsr_malloc(sizeof(struct rt_entry), "Insert routing table");
+  struct rt_path *rtp;
 
-  COPY_IP(&new_route_entry->rt_dst, dst);
-  COPY_IP(&new_route_entry->rt_router, router);
-  new_route_entry->rt_if = iface;
+  rtp = olsr_malloc(sizeof(struct rt_path), __FUNCTION__);
 
-  new_route_entry->rt_metric = metric;
-  if (etx< 0.0)
-    /* non-LQ case */
-    new_route_entry->rt_etx = (float)metric;
-  else
-    /* LQ case */
-    new_route_entry->rt_etx = etx;
-  
-  if(COMP_IP(dst, router))
-    /* Not GW */
-    new_route_entry->rt_flags = (RTF_UP|RTF_HOST);
-  else
-    new_route_entry->rt_flags = (RTF_UP|RTF_HOST|RTF_GATEWAY);
-
-  if(olsr_cnf->ip_version == AF_INET)
-    /* IPv4 */
-    new_route_entry->rt_mask.v4 = NETMASK_HOST;
-  else
-    /* IPv6 */
-    new_route_entry->rt_mask.v6 = 128;
-
-  /* queue */
-  rt_list->next->prev = new_route_entry;
-  new_route_entry->next = rt_list->next;
-  rt_list->next = new_route_entry;
-  new_route_entry->prev = rt_list;
-  
-  return(new_route_entry);
-}
+  if (!rtp) {
+    return NULL;
+  }
+
+  memset(rtp, 0, sizeof(struct rt_path));
 
+  COPY_IP(&rtp->rtp_originator, originator);
 
+  /* set key and backpointer prior to tree insertion */
+  rtp->rtp_tree_node.key = &rtp->rtp_originator;
+  rtp->rtp_tree_node.data = rtp;
+
+  /* insert to the route entry originator tree */
+  avl_insert(&rt->rt_path_tree, &rtp->rtp_tree_node, AVL_DUP_NO);
+
+  /* backlink to the owning route entry */
+  rtp->rtp_rt = rt;
+
+  return rtp;
+}
 
 /**
- *Insert all the one hop neighbors in the routing table.
- *
- *@return
+ * Check if there is an interface or gateway change.
  */
-static int
-olsr_fill_routing_table_with_neighbors(void)
+olsr_bool
+olsr_nh_change(struct rt_nexthop *nh1, struct rt_nexthop *nh2)
 {
-  int idx;
+  if ((!COMP_IP(&nh1->gateway, &nh2->gateway)) ||
+      (nh1->iface != nh2->iface)) {
+    return OLSR_TRUE;
+  }
+  return OLSR_FALSE;
+}
 
-#ifdef DEBUG
-  OLSR_PRINTF(7, "FILL ROUTING TABLE WITH NEIGHBORS\n");
-#endif
+/**
+ * depending on the operation (add/chg/del) the nexthop
+ * field from the route entry or best route path shall be used.
+ */
+struct rt_nexthop *
+olsr_get_nh(struct rt_entry *rt)
+{
 
-  for(idx=0;idx<HASHSIZE;idx++)
-    {
-      struct neighbor_entry *neighbor;
-      for(neighbor = neighbortable[idx].next;
-         neighbor != &neighbortable[idx];
-         neighbor=neighbor->next)     
-       {
-         if(neighbor->status == SYM)
-           {
-             static struct mid_address addrs;
-             struct mid_address *addrs2;
-
-             /*
-              *Insert all the neighbors addresses
-              */
-
-             COPY_IP(&addrs.alias, &neighbor->neighbor_main_addr);
-             addrs.next_alias = mid_lookup_aliases(&neighbor->neighbor_main_addr);
-
-             for(addrs2 = &addrs;addrs2!=NULL;addrs2 = addrs2->next_alias)
-               {
-                 const struct link_entry *lnk = get_best_link_to_neighbor(&addrs2->alias);
-#ifdef DEBUG
-                 OLSR_PRINTF(7, "(ROUTE)Adding neighbor %s\n", olsr_ip_to_string(&addrs.alias));
-#endif
-                 if(lnk)
-                   {
-                     struct interface *iface = lnk->if_name ? if_ifwithname(lnk->if_name) :
-                                               if_ifwithaddr(&lnk->local_iface_addr);
-                     if(iface)
-                       {
-                         olsr_insert_routing_table(&addrs2->alias, 
-                                                   &lnk->neighbor_iface_addr,
-                                                   iface,
-                                                   1,
-                                                   -1.0);
-                       }
-                   }
-               }
-           }
-       }
-    }
-  return 1;
-}
+  if(rt->rt_best) {
 
+    /* this is a route add/chg - grab nexthop from the best route. */
+    return &rt->rt_best->rtp_nexthop;
+  } 
+  
+  /* this is a route deletion - all routes are gone. */
+  return &rt->rt_nexthop;
+}
 
 /**
- * Check if a two hop neighbor is reachable trough
- * a one hop neighbor with willingness != WILL_NEVER
+ * compare two route paths.
  *
- * @return OLSR_TRUE if reachable OLSR_FALSE if not
+ * returns TRUE if the first path is better
+ * than the second one, FALSE otherwise.
  */
 static olsr_bool
-two_hop_neighbor_reachable(struct neighbor_2_list_entry *neigh_2_list)
+olsr_cmp_rtp(struct rt_path *rtp1, struct rt_path *rtp2)
 {
-  struct neighbor_list_entry *neighbors;
+   /* etx comes first */
+    if (rtp1->rtp_metric.etx < rtp2->rtp_metric.etx) {
+      return OLSR_TRUE;
+    }
 
-  for(neighbors = neigh_2_list->neighbor_2->neighbor_2_nblist.next;
-      neighbors != &neigh_2_list->neighbor_2->neighbor_2_nblist;
-      neighbors = neighbors->next)
-    {
-      if((neighbors->neighbor->status != NOT_NEIGH) &&
-        (neighbors->neighbor->willingness != WILL_NEVER))
-       return OLSR_TRUE;
+    /* hopcount is next tie breaker */
+    if ((rtp1->rtp_metric.etx == rtp2->rtp_metric.etx) &&
+        (rtp1->rtp_metric.hops < rtp2->rtp_metric.hops)) {
+      return OLSR_TRUE;
     }
 
-  return OLSR_FALSE;  
-}
+    /* originator (which is guaranteed to be unique) is final tie breaker */
+    if ((rtp1->rtp_metric.hops == rtp2->rtp_metric.hops) &&
+        (memcmp(&rtp1->rtp_originator, &rtp2->rtp_originator,
+                olsr_cnf->ipsize) == -1)) {
+      return OLSR_TRUE;
+    }
 
+    return OLSR_FALSE;
+}
 
 /**
- *Insert all the two hop neighbors that is not already added
- *in the routing table.
+ * compare the best path of two route entries.
  *
- *@return a pointer to a destination_n linked-list of the neighbors.
+ * returns TRUE if the first entry is better
+ * than the second one, FALSE otherwise.
  */
+olsr_bool
+olsr_cmp_rt(struct rt_entry *rt1, struct rt_entry *rt2)
+{
+  return(olsr_cmp_rtp(rt1->rt_best, rt2->rt_best));
+}
 
-static struct destination_n *
-olsr_fill_routing_table_with_two_hop_neighbors(void)
+/**
+ * run best route selection among a
+ * set of identical prefixes.
+ */
+void
+olsr_rt_best(struct rt_entry *rt)
 {
-  struct destination_n *list_destination_n=NULL;
-  int            idx;
+  struct rt_path *rtp;
+  struct avl_node *node;
 
-  //printf("FILL ROUTING TABLE WITH TWO HOP NEIGHBORS\n");
+  /* grab the first entry */
+  node = avl_walk_first(&rt->rt_path_tree);
 
-  for(idx=0;idx<HASHSIZE;idx++)
-    {
-      struct neighbor_entry *neighbor;
-
-      for(neighbor = neighbortable[idx].next;
-         neighbor != &neighbortable[idx];
-         neighbor=neighbor->next)     
-       {
-         struct neighbor_2_list_entry *neigh_2_list; 
-
-         if(neighbor->status != SYM)
-           continue;
-         
-         /*
-          *Insert all the two hop neighbors
-          */
-         for(neigh_2_list = neighbor->neighbor_2_list.next;
-             neigh_2_list != &neighbor->neighbor_2_list;
-             neigh_2_list = neigh_2_list->next)
-           {
-             union olsr_ip_addr *n2_addr;
-             static struct mid_address addrs;
-             struct mid_address *addrsp;
-             
-             n2_addr = &neigh_2_list->neighbor_2->neighbor_2_addr;
-             
-             if(olsr_lookup_routing_table(n2_addr))
-               {
-#ifdef DEBUG
-                 OLSR_PRINTF(7, "2hop: %s already added\n", olsr_ip_to_string(n2_addr));
-#endif
-                 continue;
-               }           
-
-             if(!two_hop_neighbor_reachable(neigh_2_list))
-               {
-                 OLSR_PRINTF(1, "Two hop neighbor %s not added - no one hop neighbors.\n",
-                             olsr_ip_to_string(n2_addr));
-                 continue;
-               }
-
-             COPY_IP(&addrs.alias, n2_addr);
-             addrs.next_alias = mid_lookup_aliases(n2_addr);
-
-             for(addrsp = &addrs; addrsp; addrsp = addrsp->next_alias)
-               {
-                 const struct link_entry * const lnk = get_best_link_to_neighbor(&neighbor->neighbor_main_addr);
-#ifdef DEBUG
-                 OLSR_PRINTF(7, "(ROUTE)Adding neighbor %s\n", olsr_ip_to_string(&addrsp->alias));
-#endif
-                 if(lnk)
-                   {
-                      struct interface *iface = lnk->if_name ? if_ifwithname(lnk->if_name) :
-                                               if_ifwithaddr(&lnk->local_iface_addr);
-                     if(iface)
-                       {
-                         struct rt_entry *new_route_entry = 
-                           olsr_insert_routing_table(&addrsp->alias, 
-                                                     &lnk->neighbor_iface_addr,
-                                                     iface,
-                                                     2,
-                                                     -1.0);
-                         
-                         if(new_route_entry != NULL)
-                           {
-                             struct destination_n *tmp = olsr_malloc(sizeof(struct destination_n), 
-                                                                      "Fill rt table 2 hop tmp");
-                             tmp->destination = new_route_entry;
-                             tmp->next = list_destination_n;
-                             list_destination_n = tmp;
-                           }
-                       }
-                   }
-               }
-           }
-       }      
+  if (!node) {
+    assert(0); /* should not happen */
+  }
+
+  rt->rt_best = node->data;
+
+  /* walk all remaining originator entries */
+  while ((node = avl_walk_next(node))) {
+
+    rtp = node->data;
+
+    if (olsr_cmp_rtp(rtp, rt->rt_best)) {
+      rt->rt_best = rtp;
     }
-  return list_destination_n;
+  }
 }
 
 /**
- *Recalculate the routing table
+ * Insert/Update a route entry into the routing table.
  *
- *@return nada
+ * Check is the route exisits and depending if this is a
+ * new version of the RIB do a full inplace update.
+ * If there is already a route from this table version then 
+ * check if the new route is better.
+ *
+ * For exisiting routes only interface or gateway router changes
+ * do trigger a kernel change.
+ *
+ *@param dst the destination
+ *@param plen the prefix length
+ *@param gateway the next-hop router
+ *@param iface the next-hop interface
+ *@param metric the hopcount
+ *@param etx the LQ extension metric
+ *
+ *@return the new rt_entry struct
  */
-void 
-olsr_calculate_routing_table(void)
+struct rt_path *
+olsr_insert_routing_table(union olsr_ip_addr *dst, 
+                          int plen,
+                          union olsr_ip_addr *originator,
+                         union olsr_ip_addr *gateway,
+                         struct interface *iface, 
+                         int metric,
+                         float etx)
 {
-  struct destination_n *list_destination_n_1;
+  struct rt_entry *rt;
+  struct rt_path *rtp;
+  struct avl_node *node;
+  struct olsr_ip_prefix prefix;
 
-  olsr_move_route_table(routingtable, old_routes);
+  /*
+   * no unreachable routes please.
+   */
+  if (etx >= INFINITE_ETX) {
+    return NULL;
+  }
 
-  /* Add neighbors */
-  olsr_fill_routing_table_with_neighbors();
-  /* Add two hop enighbors - now they are the "outer rim" */
-  
-  list_destination_n_1 = olsr_fill_routing_table_with_two_hop_neighbors();
-  while(list_destination_n_1)
-    {
-      /* List_destination_n_1 holds the "outer rim" */
-      struct destination_n *list_destination_n = list_destination_n_1;
-
-      list_destination_n_1=NULL;
-
-      /* Next "outer rim" */
-      while(list_destination_n!=NULL)
-       {
-         struct destination_n *destination_n_1=NULL;
-         struct tc_entry      *topo_entry;
-
-         if((topo_entry = olsr_lookup_tc_entry(&list_destination_n->destination->rt_dst)) != NULL)
-           {
-             struct topo_dst *topo_dest = topo_entry->destinations.next;
-
-             /* Loop trough this nodes MPR selectors */
-             while(topo_dest != &topo_entry->destinations)
-               {
-                 static struct mid_address tmp_addrs;
-                 struct mid_address *tmp_addrsp;
-                 
-                 /* Do not add ourselves */
-                 if(if_ifwithaddr(&topo_dest->T_dest_addr))
-                   {
-                     topo_dest=topo_dest->next;
-                     continue;
-                   }
-                 
-                 /* Find mid nodes */            
-                 COPY_IP(&tmp_addrs.alias, &topo_dest->T_dest_addr);
-                 tmp_addrs.next_alias = mid_lookup_aliases(&topo_dest->T_dest_addr);
-                 tmp_addrsp = &tmp_addrs;
-                 
-                 while(tmp_addrsp!=NULL)
-                   {
-                     if(NULL==olsr_lookup_routing_table(&tmp_addrsp->alias))
-                       {
-                         /* PRINT OUT: Last Hop to Final Destination */
-                         /* The function ip_to_string has to be seperately */
-                         OLSR_PRINTF(3, "%s -> ", olsr_ip_to_string(&list_destination_n->destination->rt_dst));
-                         OLSR_PRINTF(3, "%s\n", olsr_ip_to_string(&tmp_addrsp->alias));
-                         
-                         destination_n_1 = olsr_malloc(sizeof(struct destination_n), 
-                                                       "Calculate routing table 2");
-                         
-                         /* Add this entry to the "outer rim" */
-                         destination_n_1->destination = 
-                           olsr_insert_routing_table(&tmp_addrsp->alias, 
-                                                     &list_destination_n->destination->rt_router, 
-                                                     list_destination_n->destination->rt_if,
-                                                     list_destination_n->destination->rt_metric+1,
-                                                     -1.0);
-                         if(destination_n_1->destination != NULL)
-                           {
-                             destination_n_1->next=list_destination_n_1;
-                             list_destination_n_1=destination_n_1;
-                           }
-                       }
-                     tmp_addrsp = tmp_addrsp->next_alias;
-                   }
-                 
-                 /* Next MPR selector */
-                 topo_dest=topo_dest->next;
-                 
-               } /* End loop trought MPR selectors */
-             
-           } /* End check if already added */
-         
-         /* Delete this entry - do next */ 
-         destination_n_1 = list_destination_n;
-         list_destination_n = list_destination_n->next;
-         free(destination_n_1);
-         
-       }
+  /*
+   * first check if there is a route_entry for the prefix.
+   */
+  prefix.prefix = *dst;
+  prefix.prefix_len = plen;
 
-    }
+  node = avl_find(&routingtree, &prefix);
 
+  if (!node) {
 
-  if(olsr_cnf->debug_level > 5)
-    {
-      printf("************** TABLES ****************\n");
-      printf("Routing table:\n");
-      olsr_print_routing_table(routingtable);
-      printf("Old table:\n");
-      olsr_print_routing_table(old_routes);
-      printf("**************************************\n");
+    /* no route entry yet */
+    rt = olsr_alloc_rt_entry(&prefix);
+
+    if (!rt) {
+      return NULL;
     }
 
-  
-  /* Update routes */
-  olsr_update_kernel_routes();
+  } else {
+    rt = node->data;
+  }
 
-  olsr_free_routing_table(old_routes);
-}
+  /*
+   * next check if the route path from this originator is known
+   */
+  node = avl_find(&rt->rt_path_tree, originator);
+
+  if (!node) {
+
+    /* no route path from this originator yet */
+    rtp = olsr_alloc_rt_path(rt, originator);
 
+    if (!rtp) {
+      return NULL;
+    }
+
+  } else {
+    rtp = node->data;
+  }
 
+  /* update the version field and relevant parameters */
+  olsr_update_routing_entry(rtp, gateway, iface, metric, etx);
 
+  return rtp;
+}
 
 /**
- *Check for an entry with a higher quality (lower etx) than
- *a given value in a routing table
- *
- *@param routes the routingtable to look in
- *@param net the network entry to look for
- *@param etx the metric to check for
- *
- *@return the located entry if found. NULL if not
+ * format a route entry into a buffer
  */
-static struct rt_entry *
-olsr_check_for_higher_quality(struct rt_entry *routes, struct hna_net *net, float etx)
+char *
+olsr_rt_to_string(struct rt_entry *rt)
 {
-  int idx;
+  static char buff[128];
 
-  for(idx=0;idx<HASHSIZE;idx++)
-    {
-      struct rt_entry *tmp_routes;
-      /* All entries */
-      for(tmp_routes = routes[idx].next;
-         tmp_routes != &routes[idx];
-         tmp_routes = tmp_routes->next)
-       {
-         if(COMP_IP(&tmp_routes->rt_dst, &net->A_network_addr) &&
-            (memcmp(&tmp_routes->rt_mask, &net->A_netmask, netmask_size) == 0))
-           {
-             /* Found an entry */
-             if(tmp_routes->rt_etx < etx)
-               return tmp_routes;
-             else
-               return NULL;
-           }
-       }
-    }
+  snprintf(buff, sizeof(buff),
+           "%s/%u via %s",
+           olsr_ip_to_string(&rt->rt_dst.prefix),
+           rt->rt_dst.prefix_len,
+           olsr_ip_to_string(&rt->rt_nexthop.gateway));
 
-  return NULL;
+  return buff;
 }
 
-
+/**
+ * format a route path into a buffer
+ */
+char *
+olsr_rtp_to_string(struct rt_path *rtp)
+{
+  struct rt_entry *rt;
+  static char buff[128];
+
+  rt = rtp->rtp_rt;
+
+  snprintf(buff, sizeof(buff),
+           "%s/%u from %s via %s, "
+           "etx %.3f, metric %u, v %u",
+           olsr_ip_to_string(&rt->rt_dst.prefix),
+           rt->rt_dst.prefix_len,
+           olsr_ip_to_string(&rtp->rtp_originator),
+           olsr_ip_to_string(&rtp->rtp_nexthop.gateway),
+           rtp->rtp_metric.etx,
+           rtp->rtp_metric.hops,
+           rtp->rtp_version);
+
+  return buff;
+}
 
 /**
- *Check for an entry with a lower or equal quality (higher or equal etx) than
- *a given value in a routing table
- *
- *@param routes the routingtable to look in
- *@param net the network entry to look for
- *@param etx the metric to check for
+ *Insert all the one hop neighbors in the routing table.
  *
- *@return the located entry if found. NULL if not
+ *@return
  */
-struct rt_entry *
-olsr_check_for_lower_quality(struct rt_entry *routes, struct hna_net *net, float etx)
+int
+olsr_fill_routing_table_with_neighbors(void)
 {
-  int idx;
+  int index, max_host_plen;
+  float etx;
 
-  for(idx=0;idx<HASHSIZE;idx++)
-    {
-      struct rt_entry *tmp_routes;
-      /* All entries */
-      for(tmp_routes = routes[idx].next;
-         tmp_routes != &routes[idx];
-         tmp_routes = tmp_routes->next)
-       {
-         if(COMP_IP(&tmp_routes->rt_dst, &net->A_network_addr) &&
-            (memcmp(&tmp_routes->rt_mask, &net->A_netmask, netmask_size) == 0))
-           {
-             /* Found an entry */
-             if(tmp_routes->rt_etx >= etx)
-               return tmp_routes;
-             else
-               return NULL;
-           }
-       }
-    }
+#ifdef DEBUG
+  OLSR_PRINTF(7, "FILL ROUTING TABLE WITH NEIGHBORS\n");
+#endif
 
+  max_host_plen = olsr_host_rt_maxplen();
 
+  for (index=0;index<HASHSIZE;index++) {
 
-  return NULL;
-}
+    struct neighbor_entry *neighbor;
+
+    for(neighbor = neighbortable[index].next;
+        neighbor != &neighbortable[index];
+        neighbor=neighbor->next) {
+
+      if (neighbor->status == SYM) {
+
+        static struct mid_address addrs;
+        struct mid_address *addrs2;
+
+        /*
+         * Insert all the neighbors addresses
+         */
+        COPY_IP(&addrs.alias, &neighbor->neighbor_main_addr);
+        addrs.next_alias = mid_lookup_aliases(&neighbor->neighbor_main_addr);
+
+        for (addrs2 = &addrs; addrs2; addrs2 = addrs2->next_alias) {
+
+          struct link_entry *link;
+
+          link = get_best_link_to_neighbor(&addrs2->alias);
+
+#ifdef DEBUG
+          OLSR_PRINTF(7, "(ROUTE)Adding neighbor %s\n", olsr_ip_to_string(&addrs.alias));
+#endif
+          if (link) {
+
+            struct interface *iface;
+
+            iface = link->if_name ? if_ifwithname(link->if_name) :
+              if_ifwithaddr(&link->local_iface_addr);
+
+            etx = 1.0 / (link->loss_link_quality2 * link->neigh_link_quality2);
 
+            if (iface) {
 
+              /* neighbor main IP address */
+              olsr_insert_routing_table(&link->neighbor_iface_addr, max_host_plen,
+                                        &link->neighbor->neighbor_main_addr,
+                                        &link->neighbor_iface_addr,
+                                        iface, 1, etx);
+
+              /* this is the nexthop route that all routes will be tracking */
+              olsr_insert_routing_table(&addrs2->alias, max_host_plen,
+                                        &link->neighbor->neighbor_main_addr,
+                                        &link->neighbor_iface_addr,
+                                        iface, 1, etx);
+            }
+          }
+        }
+      }
+    }
+  }
+  return 1;
+}
 
 
 /**
@@ -623,130 +587,96 @@ olsr_check_for_lower_quality(struct rt_entry *routes, struct hna_net *net, float
 void
 olsr_calculate_hna_routes(void)
 {
-  int idx;
+  int index, plen;
+  struct rt_entry *rt;
 
 #ifdef DEBUG
   OLSR_PRINTF(3, "Calculating HNA routes\n");
 #endif
 
-  olsr_move_route_table(hna_routes, old_hna);
-
-  for(idx=0;idx<HASHSIZE;idx++)
+  for(index=0;index<HASHSIZE;index++)
+  {
+    struct hna_entry *tmp_hna;
+    /* All entries */
+    for(tmp_hna = hna_set[index].next;
+        tmp_hna != &hna_set[index];
+        tmp_hna = tmp_hna->next)
     {
-      struct hna_entry *tmp_hna;
-      /* All entries */
-      for(tmp_hna = hna_set[idx].next;
-         tmp_hna != &hna_set[idx];
-         tmp_hna = tmp_hna->next)
-       {
-         struct hna_net *tmp_net;
-         /* All networks */
-         for(tmp_net = tmp_hna->networks.next;
-             tmp_net != &tmp_hna->networks;
-             tmp_net = tmp_net->next)
-           {
-             struct rt_entry *tmp_rt, *new_rt;
-             //printf("HNA: checking %s -> ", olsr_ip_to_string(&tmp_hna->A_gateway_addr));
-             //printf("%s", olsr_ip_to_string(&tmp_net->A_network_addr));
-
-             /* If no route to gateway - skip */
-             if((tmp_rt = olsr_lookup_routing_table(&tmp_hna->A_gateway_addr)) == NULL)
-                 continue;
-
-             /* If there exists a better or equal entry - skip */
-             if(olsr_check_for_higher_quality(hna_routes, tmp_net, tmp_rt->rt_etx) != NULL)
-                 continue;
-
-             /* If we find an entry with lower quality we just edit it */
-             if((new_rt = olsr_check_for_lower_quality(hna_routes, tmp_net, tmp_rt->rt_etx)) != NULL)
-               {
-                 /* Fill struct */
-                 /* Net */
-                 COPY_IP(&new_rt->rt_dst, &tmp_net->A_network_addr);
-                 new_rt->rt_mask = tmp_net->A_netmask;
-                 /* Gateway */
-                 COPY_IP(&new_rt->rt_router, &tmp_rt->rt_router);
-                 /* Metric */
-                 new_rt->rt_etx = tmp_rt->rt_etx;
-                 new_rt->rt_metric = tmp_rt->rt_metric;
-                 /* Flags */
-                 new_rt->rt_flags = RTF_UP | RTF_GATEWAY;
-                 /* Interface */
-                 new_rt->rt_if = tmp_rt->rt_if;
-               }
-             /* If not - create a new one */
-             else
-               {
-                 olsr_u32_t  hna_hash;
-
-                 new_rt = olsr_malloc(sizeof(struct rt_entry), "New rt entry");
-
-                 /* Fill struct */
-                 /* Net */
-                 COPY_IP(&new_rt->rt_dst, &tmp_net->A_network_addr);
-                 new_rt->rt_mask = tmp_net->A_netmask;
-                 /* Gateway */
-                 COPY_IP(&new_rt->rt_router, &tmp_rt->rt_router);
-                 /* Metric */
-                 new_rt->rt_etx = tmp_rt->rt_etx;
-                 new_rt->rt_metric = tmp_rt->rt_metric;
-                 /* Flags */
-                 new_rt->rt_flags = RTF_UP | RTF_GATEWAY;
-
-                 /* Interface */
-                 new_rt->rt_if = tmp_rt->rt_if;
-                         
-                 /* Queue HASH will almost always be 0 */
-                 hna_hash = olsr_hashing(&tmp_net->A_network_addr);
-                 hna_routes[hna_hash].next->prev = new_rt;
-                 new_rt->next = hna_routes[hna_hash].next;
-                 hna_routes[hna_hash].next = new_rt;
-                 new_rt->prev = &hna_routes[hna_hash];
-               }
-           }
-       }
+      struct hna_net *tmp_net;
+      /* All networks */
+      for(tmp_net = tmp_hna->networks.next;
+          tmp_net != &tmp_hna->networks;
+          tmp_net = tmp_net->next) {
+
+        /* If no route to gateway - skip */
+        if((rt = olsr_lookup_routing_table(&tmp_hna->A_gateway_addr)) == NULL)
+          continue;
+
+        /* update if better */
+        plen = olsr_get_hna_prefix_len(tmp_net);
+        olsr_insert_routing_table(&tmp_net->A_network_addr, plen,
+                                  &tmp_hna->A_gateway_addr,
+                                  &rt->rt_best->rtp_nexthop.gateway,
+                                  rt->rt_best->rtp_nexthop.iface,
+                                  rt->rt_best->rtp_metric.hops,
+                                  rt->rt_best->rtp_metric.etx);
+
+      }
     }
+  }
 
   /* Update kernel */
-  olsr_update_kernel_hna_routes();
-
-  if(olsr_cnf->debug_level > 2)
-    {
-      OLSR_PRINTF(3, "HNA table:\n");
-      olsr_print_routing_table(hna_routes);
-    }
-
-  olsr_free_routing_table(old_hna);
+  olsr_update_kernel_routes();
 }
 
-
-
-
-
 /**
- *Print the routingtable to STDOUT
+ * Print the routingtree to STDOUT
  *
  */
-
 void
-olsr_print_routing_table(struct rt_entry *table)
+olsr_print_routing_table(struct avl_tree *tree)
 {
-  int idx;
+  struct rt_entry *rt;
+  struct rt_path *rtp;
+
+  struct avl_node *rt_tree_node, *rtp_tree_node;
 
   printf("ROUTING TABLE\n");
-  printf("DESTINATION\tNEXT HOP\tHOPCNT\tINTERFACE\n");
-  for(idx = 0; idx < HASHSIZE; idx++)
-    {
-      struct rt_entry *destination;
-      for(destination = table[idx].next;
-         destination != &table[idx];
-         destination = destination->next)
-       {
-         printf("%s\t", olsr_ip_to_string(&destination->rt_dst));
-         printf("%s\t%d\t%s\n", 
-                olsr_ip_to_string(&destination->rt_router),
-                destination->rt_metric,
-                destination->rt_if->int_name);
-       }
+
+  for (rt_tree_node = avl_walk_first(tree);
+       rt_tree_node;
+       rt_tree_node = avl_walk_next(rt_tree_node)) {
+
+    rt = rt_tree_node->data;
+
+    /* first the route entry */
+    printf("%s/%u, via %s, best-originator %s\n",
+           olsr_ip_to_string(&rt->rt_dst.prefix),
+           rt->rt_dst.prefix_len,
+           olsr_ip_to_string(&rt->rt_nexthop.gateway),
+           olsr_ip_to_string(&rt->rt_best->rtp_originator));
+
+    /* walk the per-originator path tree of routes */
+    for (rtp_tree_node = avl_walk_first(&rt->rt_path_tree);
+         rtp_tree_node;
+         rtp_tree_node = avl_walk_next(rtp_tree_node)) {
+
+      rtp = rtp_tree_node->data;
+
+      printf("\tfrom %s, etx %.3f, metric %u, via %s, %s, v %u\n",
+             olsr_ip_to_string(&rtp->rtp_originator),
+             rtp->rtp_metric.etx,
+             rtp->rtp_metric.hops,
+             olsr_ip_to_string(&rtp->rtp_nexthop.gateway),
+             rtp->rtp_nexthop.iface->int_name,
+             rtp->rtp_version);
+    
     }
+  }
 }
+
+/*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */
index 2a26569..397f7db 100644 (file)
@@ -1,6 +1,7 @@
 /*
  * The olsr.org Optimized Link-State Routing daemon(olsrd)
  * Copyright (c) 2004, Andreas Tønnesen(andreto@olsr.org)
+ * RIB implementation (c) 2007, Hannes Gredler (hannes@gredler.at)
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without 
@@ -36,7 +37,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: routing_table.h,v 1.18 2007/08/02 21:54:54 bernd67 Exp $
+ * $Id: routing_table.h,v 1.19 2007/09/05 16:11:11 bernd67 Exp $
  */
 
 #ifndef _OLSR_ROUTING_TABLE
 
 #include <net/route.h>
 #include "hna_set.h"
+#include "lq_avl.h"
+#include "lq_list.h"
 
 #define NETMASK_HOST 0xffffffff
 #define NETMASK_DEFAULT 0x0
 
-struct rt_entry
+/*
+ * the kernel FIB does not need to know the metric of a route.
+ * this saves us from enqueuing/dequeueing hopcount only changes.
+ */
+#define RT_METRIC_DEFAULT 2
+
+/* a composite metric is used for path selection */
+struct rt_metric
 {
-  union olsr_ip_addr    rt_dst;
-  union olsr_ip_addr    rt_router;
-  union hna_netmask     rt_mask;
-  olsr_u8_t            rt_flags; 
-  olsr_u16_t           rt_metric;
-  float                 rt_etx;
-  struct interface      *rt_if;
-  struct rt_entry       *prev;
-  struct rt_entry       *next;
+  float                 etx;
+  olsr_u32_t           hops;
 };
 
+/* a nexthop is a pointer to a gateway router plus an interface */
+struct rt_nexthop
+{
+  union olsr_ip_addr    gateway; /* gateway router */
+  struct interface      *iface; /* outgoing interface */
+};
 
-struct destination_n
+/*
+ * Every prefix in our RIB needs a route entry that contains
+ * the nexthop of the best path as installed in the kernel FIB.
+ * The route entry is the root of a rt_path tree of equal prefixes
+ * originated by different routers. It also contains a shortcut
+ * for accessing the best route among all contributing routes.
+ */
+struct rt_entry
+{
+  struct olsr_ip_prefix rt_dst;
+  struct avl_node       rt_tree_node; 
+  struct rt_path        *rt_best; /* shortcut to the best path */
+  struct rt_nexthop     rt_nexthop; /* nexthop of FIB route */
+  struct avl_tree       rt_path_tree;
+  struct list_node      rt_change_node; /* queue for kernel FIB add/chg/del */
+};
+
+/*
+ * For every received route a rt_path is added to the RIB.
+ * Depending on the results of the SPF calculation we perform a
+ * best_path calculation and pick the one with the lowest etx/metric.
+ */
+struct rt_path
 {
-  struct rt_entry      *destination;
-  struct destination_n *next;
+  struct rt_entry       *rtp_rt; /* backpointer to owning route head */
+  struct rt_nexthop     rtp_nexthop;
+  struct rt_metric      rtp_metric;
+  union olsr_ip_addr    rtp_originator; /* originator of the route */
+  struct avl_node       rtp_tree_node; 
+  olsr_u32_t            rtp_version;
 };
 
+/*
+ * macro for traversing the entire routing table.
+ * it is recommended to use this because it hides all the internal
+ * datastructure from the callers.
+ *
+ * the loop prefetches the next node in order to not loose context if
+ * for example the caller wants to delete the current rt_entry.
+ */
+#define OLSR_FOR_ALL_RT_ENTRIES(rt) \
+{ \
+  struct avl_node *rt_tree_node, *next_rt_tree_node; \
+  for (rt_tree_node = avl_walk_first(&routingtree); \
+    rt_tree_node; rt_tree_node = next_rt_tree_node) { \
+    next_rt_tree_node = avl_walk_next(rt_tree_node); \
+    rt = rt_tree_node->data;
+#define OLSR_FOR_ALL_RT_ENTRIES_END(rt) }}
 
 /**
  * IPv4 <-> IPv6 wrapper
@@ -78,7 +129,7 @@ union olsr_kernel_route
   {
     struct sockaddr rt_dst;
     struct sockaddr rt_gateway;
-    olsr_u32_t rt_metric;
+    olsr_u32_t metric;
   } v4;
 
   struct
@@ -90,32 +141,43 @@ union olsr_kernel_route
 };
 
 
-extern struct rt_entry routingtable[HASHSIZE];
-extern struct rt_entry hna_routes[HASHSIZE];
-
+extern struct avl_tree routingtree;
+extern unsigned int routingtree_version;
 
 int
 olsr_init_routing_table(void);
 
-void 
-olsr_calculate_routing_table(void);
+unsigned int olsr_bump_routingtree_version(void);
 
-void
-olsr_calculate_hna_routes(void);
+int avl_comp_ipv4_prefix (void *, void *);
+int avl_comp_ipv6_prefix (void *, void *);
 
-void
-olsr_print_routing_table(struct rt_entry *);
+void olsr_rt_best(struct rt_entry *);
+olsr_bool olsr_nh_change(struct rt_nexthop *, struct rt_nexthop *);
+olsr_bool olsr_cmp_rt(struct rt_entry *, struct rt_entry *);
 
-struct rt_entry *
-olsr_insert_routing_table(union olsr_ip_addr *, const union olsr_ip_addr *, struct interface *, int, float);
+void olsr_calculate_hna_routes(void);
+int olsr_fill_routing_table_with_neighbors(void);
+char *olsr_rt_to_string(struct rt_entry *);
+char *olsr_rtp_to_string(struct rt_path *);
+void olsr_print_routing_table(struct avl_tree *);
 
-struct rt_entry *
-olsr_lookup_routing_table(union olsr_ip_addr *);
+struct rt_nexthop * olsr_get_nh(struct rt_entry *);
+
+struct rt_path *
+olsr_insert_routing_table(union olsr_ip_addr *, int,
+                          union olsr_ip_addr *,
+                          union olsr_ip_addr *,
+                          struct interface *, int, float);
 
 struct rt_entry *
-olsr_lookup_hna_routing_table(union olsr_ip_addr *dst);
+olsr_lookup_routing_table(union olsr_ip_addr *);
 
-void
-olsr_free_routing_table(struct rt_entry *);
 
 #endif
+
+/*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */
index 048cbf2..159be0f 100644 (file)
@@ -36,7 +36,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: kernel_routes.c,v 1.20 2007/04/25 22:22:15 bernd67 Exp $
+ * $Id: kernel_routes.c,v 1.21 2007/09/05 16:11:11 bernd67 Exp $
  */
 
 #include <stdio.h>
 
 char *StrError(unsigned int ErrNo);
 
-int olsr_ioctl_add_route(struct rt_entry *Dest)
+/**
+ *Insert a route in the kernel routing table
+ *
+ *@param destination the route to add
+ *
+ *@return negative on error
+ */
+int olsr_ioctl_add_route(struct rt_entry *rt)
 {
   MIB_IPFORWARDROW Row;
+  union olsr_ip_addr mask;
   unsigned long Res;
-  char Str1[16], Str2[16], Str3[16];
 
-  inet_ntop(AF_INET, &Dest->rt_dst.v4, Str1, 16);
-  inet_ntop(AF_INET, &Dest->rt_mask.v4, Str2, 16);
-  inet_ntop(AF_INET, &Dest->rt_router.v4, Str3, 16);
-
-  OLSR_PRINTF(1, "Adding IPv4 route with metric %d to %s/%s via %s and I/F 0x%x.\n",
-              Dest->rt_metric + Dest->rt_if->int_metric, Str1, Str2, Str3, Dest->rt_if->if_index);
+  OLSR_PRINTF(2, "KERN: Adding %s\n", olsr_rt_to_string(rt));
 
   memset(&Row, 0, sizeof (MIB_IPFORWARDROW));
 
-  Row.dwForwardDest = Dest->rt_dst.v4;
-  Row.dwForwardMask = Dest->rt_mask.v4;
+  Row.dwForwardDest = rt->rt_dst.prefix.v4;
+
+  if (!olsr_prefix_to_netmask(&mask, rt->rt_dst.prefix_len)) {
+    return -1;
+  } else {
+      Row.dwForwardMask = mask.v4;
+  }
+
   Row.dwForwardPolicy = 0;
-  Row.dwForwardNextHop = Dest->rt_router.v4;
-  Row.dwForwardIfIndex = Dest->rt_if->if_index;
+  Row.dwForwardNextHop = rt->rt_best->rtp_nexthop.gateway.v4;
+  Row.dwForwardIfIndex = rt->rt_best->rtp_nexthop.iface->if_index;
   // MIB_IPROUTE_TYPE_DIRECT and MIB_IPROUTE_TYPE_INDIRECT
-  Row.dwForwardType = (Dest->rt_dst.v4 == Dest->rt_router.v4) ? 3 : 4;
+  Row.dwForwardType = (rt->rt_dst.prefix.v4 == rt->rt_best->rtp_nexthop.gateway.v4) ? 3 : 4;
   Row.dwForwardProto = 3; // MIB_IPPROTO_NETMGMT
   Row.dwForwardAge = INFINITE;
   Row.dwForwardNextHopAS = 0;
-  Row.dwForwardMetric1 = Dest->rt_metric + Dest->rt_if->int_metric;
+  Row.dwForwardMetric1 = RT_METRIC_DEFAULT;
   Row.dwForwardMetric2 = -1;
   Row.dwForwardMetric3 = -1;
   Row.dwForwardMetric4 = -1;
@@ -104,46 +112,59 @@ int olsr_ioctl_add_route(struct rt_entry *Dest)
     return -1;
   }
 
-  if(olsr_cnf->open_ipc)
-    ipc_route_send_rtentry(&Dest->rt_dst, &Dest->rt_router, Dest->rt_metric,
-                           1, Dest->rt_if->int_name);
+  /*
+   * Send IPC route update message
+   */
+  if(olsr_cnf->open_ipc) {
+    ipc_route_send_rtentry(&rt->rt_dst.prefix, &rt->rt_best->rtp_nexthop.gateway,
+        rt->rt_best->rtp_metric.hops, 1,
+        rt->rt_best->rtp_nexthop.iface->int_name);
+  }
 
   return 0;
 }
 
 // XXX - to be implemented
 
-int olsr_ioctl_add_route6(struct rt_entry *Dest __attribute__((unused)))
+int olsr_ioctl_add_route6(struct rt_entry *rt __attribute__((unused)))
 {
   return 0;
 }
 
-int olsr_ioctl_del_route(struct rt_entry *Dest)
+/**
+ *Remove a route from the kernel
+ *
+ *@param destination the route to remove
+ *
+ *@return negative on error
+ */
+int olsr_ioctl_del_route(struct rt_entry *rt)
 {
   MIB_IPFORWARDROW Row;
+  union olsr_ip_addr mask;
   unsigned long Res;
-  char Str1[16], Str2[16], Str3[16];
 
-  inet_ntop(AF_INET, &Dest->rt_dst.v4, Str1, 16);
-  inet_ntop(AF_INET, &Dest->rt_mask.v4, Str2, 16);
-  inet_ntop(AF_INET, &Dest->rt_router.v4, Str3, 16);
-
-  OLSR_PRINTF(1, "Deleting IPv4 route with metric %d to %s/%s via %s and I/F 0x%x.\n",
-              Dest->rt_metric + Dest->rt_if->int_metric, Str1, Str2, Str3, Dest->rt_if->if_index);
+  OLSR_PRINTF(2, "KERN: Deleting %s\n", olsr_rt_to_string(rt));
 
   memset(&Row, 0, sizeof (MIB_IPFORWARDROW));
 
-  Row.dwForwardDest = Dest->rt_dst.v4;
-  Row.dwForwardMask = Dest->rt_mask.v4;
+  Row.dwForwardDest = rt->rt_dst.prefix.v4;
+
+  if (!olsr_prefix_to_netmask(&mask, rt->rt_dst.prefix_len)) {
+    return -1;
+  } else {
+      Row.dwForwardMask = mask.v4;
+  }
+
   Row.dwForwardPolicy = 0;
-  Row.dwForwardNextHop = Dest->rt_router.v4;
-  Row.dwForwardIfIndex = Dest->rt_if->if_index;
+  Row.dwForwardNextHop = rt->rt_nexthop.gateway.v4;
+  Row.dwForwardIfIndex = rt->rt_nexthop.iface->if_index;
   // MIB_IPROUTE_TYPE_DIRECT and MIB_IPROUTE_TYPE_INDIRECT
-  Row.dwForwardType = (Dest->rt_dst.v4 == Dest->rt_router.v4) ? 3 : 4;
+  Row.dwForwardType = (rt->rt_dst.prefix.v4 == rt->rt_nexthop.gateway.v4) ? 3 : 4;
   Row.dwForwardProto = 3; // MIB_IPPROTO_NETMGMT
   Row.dwForwardAge = INFINITE;
   Row.dwForwardNextHopAS = 0;
-  Row.dwForwardMetric1 = Dest->rt_metric + Dest->rt_if->int_metric;
+  Row.dwForwardMetric1 = RT_METRIC_DEFAULT;
   Row.dwForwardMetric2 = -1;
   Row.dwForwardMetric3 = -1;
   Row.dwForwardMetric4 = -1;
@@ -162,15 +183,19 @@ int olsr_ioctl_del_route(struct rt_entry *Dest)
     return -1;
   }
 
-  if(olsr_cnf->open_ipc)
-    ipc_route_send_rtentry(&Dest->rt_dst, NULL, Dest->rt_metric, 0, NULL);
+  /*
+   * Send IPC route update message
+   */
+  if(olsr_cnf->open_ipc) {
+    ipc_route_send_rtentry(&rt->rt_dst.prefix, NULL, 0 , 0, NULL);
+  }
 
   return 0;
 }
 
 // XXX - to be implemented
 
-int olsr_ioctl_del_route6(struct rt_entry *Dest __attribute__((unused)))
+int olsr_ioctl_del_route6(struct rt_entry *rt __attribute__((unused)))
 {
   return 0;
 }