applied patch by Hannes Gredler <hannes@gredler.at>::
authorBernd Petrovitsch <bernd@firmix.at>
Wed, 12 Dec 2007 21:57:56 +0000 (21:57 +0000)
committerBernd Petrovitsch <bernd@firmix.at>
Wed, 12 Dec 2007 21:57:56 +0000 (21:57 +0000)
pls find attached a pointer for further CPU savings in olsrd.
even in large networks (>250 nodes) the avg. CPU utilization
does not get beyond 0.5% CPU load on standard 200Mhz WRT hardware.

patch from http://gredler.at/download/olsrd/rib2-refactoring4.diff

change-list:

- avoid the periodical rib-tree insertion

- add a FOR_ALL_HNA_RT_ENTRIES() macro for the snmp folks
    (or any parties who want to walk HNA entries).

- add an olsr_cnf option 'flat_fib_metrics' which defaults to TRUE.

   this is as per sven-olas request who has expressed concerns
   that the current flap-metric style is a bit unpleasant for troubleshooting.

   note that i have not yet added the cfg file parser routine for that -
   just the required tweaks in the change-processing FIB code.

18 files changed:
CHANGELOG
src/cfgparser/olsrd_conf.c
src/hna_set.c
src/link_set.c
src/link_set.h
src/linux/kernel_routes.c
src/lq_route.c
src/mid_set.c
src/mid_set.h
src/olsr.c
src/olsr_cfg.h
src/process_routes.c
src/process_routes.h
src/routing_table.c
src/routing_table.h
src/tc_set.c
src/tc_set.h
src/win32/kernel_routes.c

index edd3b37..5c69f7a 100644 (file)
--- a/CHANGELOG
+++ b/CHANGELOG
@@ -1,5 +1,5 @@
 This file states changes as of version 0.2.4:
-$Id: CHANGELOG,v 1.122 2007/12/11 17:20:06 bernd67 Exp $
+$Id: CHANGELOG,v 1.123 2007/12/12 21:57:56 bernd67 Exp $
 
 0.5.5 ---------------------------------------------------------------------
 
@@ -8,6 +8,11 @@ BUGFIXES and PATCHES by Hannes Gredler <hannes@gredler.at>
 - avoid setting routes with an invalid/impossible netmask.
 - refactoring of TC parsing to kill another pile of malloc()/free()s
   saving (again) code and especially run.time performance.
+- RIB Refactoring, Part 2:
+  - avoid the periodical rib-tree insertion
+  - add a FOR_ALL_HNA_RT_ENTRIES() macro for the snmp folks
+    (or any parties who want to walk HNA entries).
+  - add an olsr_cnf option 'flat_fib_metrics' which defaults to TRUE.
 
 PATCH by John Hay <jhay@meraka.org.za>:
 - also printout our own HNAs in the dotdraw plugin.
index 27c97e7..269a7a7 100644 (file)
@@ -36,7 +36,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: olsrd_conf.c,v 1.65 2007/12/02 19:00:28 bernd67 Exp $
+ * $Id: olsrd_conf.c,v 1.66 2007/12/12 21:57:27 bernd67 Exp $
  */
 
 
@@ -436,6 +436,7 @@ set_default_cnf(struct olsrd_config *cnf)
     cnf->rttable = 254;
     cnf->willingness_auto = DEF_WILL_AUTO;
     cnf->ipc_connections = DEF_IPC_CONNECTIONS;
+    cnf->flat_fib_metric = DEF_FLAT_FIB_METRIC;
 
     cnf->use_hysteresis = DEF_USE_HYST;
     cnf->hysteresis_param.scaling = HYST_SCALING;
index 8a9d98e..8e3a060 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.29 2007/12/02 19:00:27 bernd67 Exp $
+ * $Id: hna_set.c,v 1.30 2007/12/12 21:57:27 bernd67 Exp $
  */
 
 #include "ipcalc.h"
@@ -44,6 +44,7 @@
 #include "olsr.h"
 #include "scheduler.h"
 #include "net_olsr.h"
+#include "tc_set.h"
 
 
 struct hna_entry hna_set[HASHSIZE];
@@ -106,9 +107,11 @@ olsr_lookup_hna_gw(const union olsr_ip_addr *gw)
 {
   struct hna_entry *tmp_hna;
   olsr_u32_t hash = olsr_hashing(gw);
-  
-  //OLSR_PRINTF(5, "TC: lookup entry\n");
 
+#if 0
+  OLSR_PRINTF(5, "HNA: lookup entry\n");
+#endif
+  
   /* Check for registered entry */
   for(tmp_hna = hna_set[hash].next;
       tmp_hna != &hna_set[hash];
@@ -177,8 +180,8 @@ olsr_add_hna_net(struct hna_entry *hna_gw, const union olsr_ip_addr *net, olsr_u
   struct hna_net *new_net = olsr_malloc(sizeof(struct hna_net), "Add HNA net");
   
   /* Fill struct */
+  memset(new_net, 0, sizeof(struct hna_net));
   new_net->A_network_addr = *net;
-  //memcpy(&new_net->A_netmask, mask, netmask_size);
   new_net->prefixlen = prefixlen;
 
   /* Queue */
@@ -187,6 +190,14 @@ olsr_add_hna_net(struct hna_entry *hna_gw, const union olsr_ip_addr *net, olsr_u
   hna_gw->networks.next = new_net;
   new_net->prev = &hna_gw->networks;
 
+  /*
+   * Add the rt_path for the entry.
+   */
+  olsr_insert_routing_table(&new_net->A_network_addr,
+                            new_net->prefixlen,
+                            &hna_gw->A_gateway_addr,
+                            OLSR_RT_ORIGIN_HNA);
+
   return new_net;
 }
 
@@ -259,6 +270,13 @@ olsr_time_out_hna_set(void *foo __attribute__((unused)))
                  struct hna_net *net_to_delete = tmp_net;
                  tmp_net = tmp_net->next;
                  DEQUEUE_ELEM(net_to_delete);
+
+                  /*
+                   * Delete the rt_path for the entry.
+                   */
+                  olsr_delete_routing_table(&net_to_delete->A_network_addr,
+                                            net_to_delete->prefixlen,
+                                            &tmp_hna->A_gateway_addr);
                  free(net_to_delete);
                  changes_hna = OLSR_TRUE;
                }
index bd5540e..ca3908a 100644 (file)
@@ -36,7 +36,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: link_set.c,v 1.80 2007/12/02 19:00:27 bernd67 Exp $
+ * $Id: link_set.c,v 1.81 2007/12/12 21:57:27 bernd67 Exp $
  */
 
 
@@ -502,6 +502,9 @@ add_link_entry(const union olsr_ip_addr *local,
     } else 
       new_link->if_name = NULL;
 
+  /* shortcut to interface. XXX refcount */
+  new_link->inter = local_if;
+
   /*
    * L_local_iface_addr = Address of the interface
    * which received the HELLO message
@@ -699,6 +702,7 @@ update_link_entry(const union olsr_ip_addr *local,
   /* Update ASYM_time */
   //printf("Vtime is %f\n", message->vtime);
   /* L_ASYM_time = current time + validity time */
+  entry->vtime = message->vtime;
   entry->ASYM_time = GET_TIMESTAMP(message->vtime*1000);
   
   entry->prev_status = check_link_status(message, in_if);
index 4e4ca88..f141a70 100644 (file)
@@ -36,7 +36,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: link_set.h,v 1.36 2007/11/25 22:08:57 bernd67 Exp $
+ * $Id: link_set.h,v 1.37 2007/12/12 21:57:27 bernd67 Exp $
  */
 
 
@@ -55,10 +55,12 @@ struct link_entry
 {
   union olsr_ip_addr local_iface_addr;
   union olsr_ip_addr neighbor_iface_addr;
+  const struct interface *inter;
   char *if_name;
   clock_t SYM_time;
   clock_t ASYM_time;
   clock_t time;
+  unsigned int vtime;
   struct neighbor_entry *neighbor;
   olsr_u8_t prev_status;
 
@@ -154,3 +156,9 @@ olsr_update_dijkstra_link_qualities(void);
 float olsr_calc_link_etx(const struct link_entry *);
 
 #endif
+
+/*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */
index 58b0975..eb348b1 100644 (file)
@@ -37,7 +37,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: kernel_routes.c,v 1.34 2007/12/02 19:00:28 bernd67 Exp $
+ * $Id: kernel_routes.c,v 1.35 2007/12/12 21:57:27 bernd67 Exp $
  */
 
 #include "kernel_routes.h"
@@ -87,9 +87,11 @@ static int olsr_netlink_route(const struct rt_entry *rt, olsr_u8_t family, olsr_
                0,
                0
        };
-       olsr_u32_t metric = 1;
+        olsr_u32_t metric = RT_METRIC_DEFAULT;
        const struct rt_nexthop* nexthop = (RTM_NEWROUTE == cmd) ?
                &rt->rt_best->rtp_nexthop : &rt->rt_nexthop;
+       const struct rt_metric* met = (RTM_NEWROUTE == cmd) ?
+               &rt->rt_best->rtp_metric : &rt->rt_metric;
 
        memset(&req, 0, sizeof(req));
        req.n.nlmsg_len = NLMSG_LENGTH(sizeof(struct rtmsg));
@@ -108,7 +110,7 @@ static int olsr_netlink_route(const struct rt_entry *rt, olsr_u8_t family, olsr_
                {
                        olsr_netlink_addreq(&req, RTA_GATEWAY, &nexthop->gateway.v4, sizeof(nexthop->gateway.v4));
                        req.r.rtm_scope = RT_SCOPE_UNIVERSE;
-                       metric = RT_METRIC_DEFAULT;
+                       metric = olsr_fib_metric(met);
                }
                olsr_netlink_addreq(&req, RTA_DST, &rt->rt_dst.prefix.v4, sizeof(rt->rt_dst.prefix.v4));
        }
@@ -118,7 +120,7 @@ static int olsr_netlink_route(const struct rt_entry *rt, olsr_u8_t family, olsr_
                {
                        olsr_netlink_addreq(&req, RTA_GATEWAY, &nexthop->gateway.v6, sizeof(nexthop->gateway.v6));
                        req.r.rtm_scope = RT_SCOPE_UNIVERSE;
-                       metric = RT_METRIC_DEFAULT;
+                       metric = olsr_fib_metric(met);
                }
                olsr_netlink_addreq(&req, RTA_DST, &rt->rt_dst.prefix.v6, sizeof(rt->rt_dst.prefix.v6));
        }
@@ -203,7 +205,7 @@ olsr_ioctl_add_route(const struct rt_entry *rt)
   }
 
   kernel_route.rt_flags = olsr_rt_flags(rt);
-  kernel_route.rt_metric = RT_METRIC_DEFAULT;
+  kernel_route.rt_metric = olsr_fib_metric(&rt->rt_best->rtp_metric.hops);
 
   /*
    * Set interface
@@ -268,7 +270,7 @@ olsr_ioctl_add_route6(const struct rt_entry *rt)
   kernel_route.rtmsg_gateway = rt->rt_best->rtp_nexthop.gateway.v6;
 
   kernel_route.rtmsg_flags = olsr_rt_flags(rt);
-  kernel_route.rtmsg_metric = RT_METRIC_DEFAULT;
+  kernel_route.rtmsg_metric = olsr_fib_metric(&rt->rt_best->rtp_metric.hops);
   
   /*
    * set interface
@@ -332,7 +334,7 @@ olsr_ioctl_del_route(const struct rt_entry *rt)
   }
 
   kernel_route.rt_flags = olsr_rt_flags(rt);
-  kernel_route.rt_metric = RT_METRIC_DEFAULT;
+  kernel_route.rt_metric = olsr_fib_metric(&rt->rt_metric.hops);
 
   /*
    * Set interface
@@ -388,7 +390,7 @@ olsr_ioctl_del_route6(const struct rt_entry *rt)
   kernel_route.rtmsg_gateway = rt->rt_best->rtp_nexthop.gateway.v6;
 
   kernel_route.rtmsg_flags = olsr_rt_flags(rt);
-  kernel_route.rtmsg_metric = RT_METRIC_DEFAULT;
+  kernel_route.rtmsg_metric = olsr_fib_metric(&rt->rt_best->rtp_metric.hops);
 
   if ((rslt = ioctl(olsr_cnf->ioctl_s, SIOCDELRT, &kernel_route) >= 0)) {
 
index 795745a..fc8bef8 100644 (file)
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: lq_route.c,v 1.61 2007/11/29 00:49:38 bernd67 Exp $
+ * $Id: lq_route.c,v 1.62 2007/12/12 21:57:27 bernd67 Exp $
  */
 
-#define SPF_PROFILING 1
+#define SPF_PROFILING 0
 
 #include "ipcalc.h"
 #include "defs.h"
@@ -88,21 +88,21 @@ avl_comp_etx (const void *etx1, const void *etx2)
  */
 static void
 olsr_spf_add_cand_tree (struct avl_tree *tree,
-                        struct tc_entry *vert)
+                        struct tc_entry *tc)
 {
 #if !defined(NODEBUG) && defined(DEBUG)
   struct ipaddr_str buf;
 #endif
-  vert->cand_tree_node.key = &vert->path_etx;
-  vert->cand_tree_node.data = vert;
+  tc->cand_tree_node.key = &tc->path_etx;
+  tc->cand_tree_node.data = tc;
 
 #ifdef DEBUG
   OLSR_PRINTF(1, "SPF: insert candidate %s, cost %f\n",
-              olsr_ip_to_string(&buf, &vert->addr),
-              vert->path_etx);
+              olsr_ip_to_string(&buf, &tc->addr),
+              tc->path_etx);
 #endif
 
-  avl_insert(tree, &vert->cand_tree_node, AVL_DUP);
+  avl_insert(tree, &tc->cand_tree_node, AVL_DUP);
 }
 
 /*
@@ -112,7 +112,7 @@ olsr_spf_add_cand_tree (struct avl_tree *tree,
  */
 static void
 olsr_spf_del_cand_tree (struct avl_tree *tree,
-                        struct tc_entry *vert)
+                        struct tc_entry *tc)
 {
 
 #ifdef DEBUG
@@ -120,11 +120,11 @@ olsr_spf_del_cand_tree (struct avl_tree *tree,
   struct ipaddr_str buf;
 #endif
   OLSR_PRINTF(1, "SPF: delete candidate %s, cost %f\n",
-              olsr_ip_to_string(&buf, &vert->addr),
-              vert->path_etx);
+              olsr_ip_to_string(&buf, &tc->addr),
+              tc->path_etx);
 #endif
 
-  avl_delete(tree, &vert->cand_tree_node);
+  avl_delete(tree, &tc->cand_tree_node);
 }
 
 /*
@@ -133,23 +133,22 @@ olsr_spf_del_cand_tree (struct avl_tree *tree,
  * Insert an SPF result at the end of the path list.
  */
 static void
-olsr_spf_add_path_list (struct list_node *head,
-                        int *path_count,
-                        struct tc_entry *vert)
+olsr_spf_add_path_list (struct list_node *head, int *path_count,
+                        struct tc_entry *tc)
 {
 #if !defined(NODEBUG) && defined(DEBUG)
   struct ipaddr_str pathbuf, nbuf;
 #endif
-  vert->path_list_node.data = vert;
+  tc->path_list_node.data = tc;
 
 #ifdef DEBUG
   OLSR_PRINTF(1, "SPF: append path %s, cost %f, via %s\n",
-              olsr_ip_to_string(&pathbuf, &vert->addr),
-              vert->path_etx,
-              vert->next_hop ? olsr_ip_to_string(&nbuf, &vert->next_hop->neighbor_iface_addr) : "-");
+              olsr_ip_to_string(&pathbuf, &tc->addr),
+              tc->path_etx,
+              tc->next_hop ? olsr_ip_to_string(&nbuf, &tc->next_hop->neighbor_iface_addr) : "-");
 #endif
 
-  list_add_before(head, &vert->path_list_node);
+  list_add_before(head, &tc->path_list_node);
   *path_count = *path_count + 1;
 }
 
@@ -187,7 +186,7 @@ const char *olsr_etx_to_string(float etx)
  * path cost is better.
  */
 static void
-olsr_spf_relax (struct avl_tree *cand_tree, struct tc_entry *vert)
+olsr_spf_relax (struct avl_tree *cand_tree, struct tc_entry *tc)
 {
   struct avl_node *edge_node;
   float new_etx;
@@ -197,17 +196,18 @@ olsr_spf_relax (struct avl_tree *cand_tree, struct tc_entry *vert)
   struct ipaddr_str buf, nbuf;
 #endif
   OLSR_PRINTF(1, "SPF: exploring node %s, cost %f\n",
-              olsr_ip_to_string(&buf, &vert->addr),
-              vert->path_etx);
+              olsr_ip_to_string(&buf, &tc->addr),
+              tc->path_etx);
 #endif
 
   /*
    * loop through all edges of this vertex.
    */
-  for (edge_node = avl_walk_first(&vert->edge_tree);
+  for (edge_node = avl_walk_first(&tc->edge_tree);
        edge_node;
        edge_node = avl_walk_next(edge_node)) {
-    struct tc_entry *new_vert;
+
+    struct tc_entry *new_tc;
     struct tc_edge_entry *tc_edge = edge_node->data;
 
     /*
@@ -231,7 +231,7 @@ olsr_spf_relax (struct avl_tree *cand_tree, struct tc_entry *vert)
      * total quality of the path through this vertex
      * to the destination of this edge
      */
-    new_etx = vert->path_etx + tc_edge->etx;
+    new_etx = tc->path_etx + tc_edge->etx;
 
 #ifdef DEBUG
       OLSR_PRINTF(1, "SPF:   exploring edge %s, cost %s\n",
@@ -243,32 +243,32 @@ olsr_spf_relax (struct avl_tree *cand_tree, struct tc_entry *vert)
        * if it's better than the current path quality of this edge's
        * destination node, then we've found a better path to this node.
        */
-    new_vert = tc_edge->edge_inv->tc;
+    new_tc = tc_edge->edge_inv->tc;
 
-    if (new_etx < new_vert->path_etx) {
+    if (new_etx < new_tc->path_etx) {
 
       /* if this node has been on the candidate tree delete it */
-      if (new_vert->path_etx != INFINITE_ETX) {
-        olsr_spf_del_cand_tree(cand_tree, new_vert);
+      if (new_tc->path_etx != INFINITE_ETX) {
+        olsr_spf_del_cand_tree(cand_tree, new_tc);
       }
 
       /* re-insert on candidate tree with the better metric */
-      new_vert->path_etx = new_etx;
-      olsr_spf_add_cand_tree(cand_tree, new_vert);
+      new_tc->path_etx = new_etx;
+      olsr_spf_add_cand_tree(cand_tree, new_tc);
 
       /* pull-up the next-hop and bump the hop count */
-      if (vert->next_hop) {
-        new_vert->next_hop = vert->next_hop;
+      if (tc->next_hop) {
+        new_tc->next_hop = tc->next_hop;
       }
-      new_vert->hops = vert->hops + 1;
+      new_tc->hops = tc->hops + 1;
 
 #ifdef DEBUG
       OLSR_PRINTF(1, "SPF:   better path to %s, cost %s -> %s, via %s, hops %u\n",
-                  olsr_ip_to_string(&buf, &new_vert->addr),
-                  olsr_etx_to_string(new_vert->path_etx),
+                  olsr_ip_to_string(&buf, &new_tc->addr),
+                  olsr_etx_to_string(new_tc->path_etx),
                   olsr_etx_to_string(new_etx),
-                  vert->next_hop ? olsr_ip_to_string(&nbuf, &vert->next_hop->neighbor_iface_addr) : "<none>",
-                  new_vert->hops);
+                  tc->next_hop ? olsr_ip_to_string(&nbuf, &tc->next_hop->neighbor_iface_addr) : "<none>",
+                  new_tc->hops);
 #endif
 
     }
@@ -291,37 +291,38 @@ static void
 olsr_spf_run_full (struct avl_tree *cand_tree, struct list_node *path_list,
                    int *path_count)
 {
-  struct tc_entry *vert;
+  struct tc_entry *tc;
 
   *path_count = 0;
 
-  while ((vert = olsr_spf_extract_best(cand_tree))) {
+  while ((tc = olsr_spf_extract_best(cand_tree))) {
 
-    olsr_spf_relax(cand_tree, vert);
+    olsr_spf_relax(cand_tree, tc);
 
     /*
      * move the best path from the candidate tree
      * to the path list.
      */
-    olsr_spf_del_cand_tree(cand_tree, vert);
-    olsr_spf_add_path_list(path_list, path_count, vert);
+    olsr_spf_del_cand_tree(cand_tree, tc);
+    olsr_spf_add_path_list(path_list, path_count, tc);
   }
 }
 
 void
 olsr_calculate_routing_table (void)
 {
+#if !defined(NODEBUG) && defined(DEBUG)
+  struct ipaddr_str buf;
+#endif
+
   struct avl_tree cand_tree;
-  struct list_node path_list;
+  struct avl_node *rtp_tree_node;
+  struct list_node path_list; /* head of the path_list */
   int i, path_count = 0;
   struct tc_entry *tc;
+  struct rt_path *rtp;
   struct tc_edge_entry *tc_edge;
-  struct tc_entry *vert;
   struct neighbor_entry *neigh;
-  struct mid_address *mid_walker;
-  struct hna_entry *hna_gw;
-  struct hna_net *hna;
-  struct interface *inter;
   struct link_entry *link;
 
 #ifdef SPF_PROFILING
@@ -376,17 +377,29 @@ olsr_calculate_routing_table (void)
          continue;
         }
 
+        /* find the interface for the link */
+        if (link->if_name) {
+          link->inter = if_ifwithname(link->if_name);
+        } else {
+          link->inter = if_ifwithaddr(&link->local_iface_addr);
+        }
+
         /*
          * Set the next-hops of our neighbors. 
          */
         if (!tc_edge) {
           tc_edge = olsr_add_tc_edge_entry(tc_myself, &neigh->neighbor_main_addr,
-                                           0, link->last_htime,
+                                           0, link->vtime,
                                            link->loss_link_quality2,
                                            link->neigh_link_quality2);
         } else {
+
+          /*
+           * Update LQ and timers, such that the edge does not get deleted.
+           */
           tc_edge->link_quality = link->loss_link_quality2;
           tc_edge->inverse_link_quality = link->neigh_link_quality2;
+          olsr_set_tc_edge_timer(tc_edge, link->vtime*1000);
           olsr_calc_tc_edge_entry_etx(tc_edge);
         }
         if (tc_edge->edge_inv) {
@@ -415,64 +428,59 @@ olsr_calculate_routing_table (void)
 #endif
 
   /*
-   * In the path tree we have all the reachable nodes in our topology.
+   * In the path list we have all the reachable nodes in our topology.
    */
   for (; !list_is_empty(&path_list); list_remove(path_list.next)) {
 
-    vert = path_list.next->data;
-    link = vert->next_hop;
+    tc = path_list.next->data;
+    link = tc->next_hop;
 
     if (!link) {
-#ifndef NODEBUG
-      struct ipaddr_str buf;
-#endif
-      OLSR_PRINTF(2, "%s no next-hop\n", olsr_ip_to_string(&buf, &vert->addr));
+
+      /*
+       * Supress the error msg when our own tc_entry
+       * does not contain a next-hop.
+       */
+      if (tc != tc_myself) {
+        OLSR_PRINTF(1, "SPF: %s no next-hop\n", olsr_ip_to_string(&buf, &tc->addr));
+      }
       continue;
     }
 
-    /* find the interface for the found link */
-    inter = link->if_name ? if_ifwithname(link->if_name)
-      : if_ifwithaddr(&link->local_iface_addr);
-
-    /* interface is up ? */
-    if (inter) {
-
-      /* add a route to the main address of the destination node */
-      olsr_insert_routing_table(&vert->addr, olsr_cnf->maxplen, &vert->addr,
-                                &link->neighbor_iface_addr, inter->if_index,
-                                vert->hops, vert->path_etx);
+    /*
+     * Now walk all prefixes advertised by that node.
+     * Since the node is reachable, insert the prefix into the global RIB.
+     * If the prefix is already in the RIB, refresh the entry such
+     * that olsr_delete_outdated_routes() does not purge it off.
+     */
+    for (rtp_tree_node = avl_walk_first(&tc->prefix_tree);
+         rtp_tree_node;
+         rtp_tree_node = avl_walk_next(rtp_tree_node)) {
 
-      /* 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) {
+      rtp = rtp_tree_node->data;
 
-        olsr_insert_routing_table(&mid_walker->alias, olsr_cnf->maxplen, &vert->addr,
-                                  &link->neighbor_iface_addr, inter->if_index,
-                                  vert->hops, vert->path_etx);
-      }
+      if (rtp->rtp_rt) {
 
-      /* find the node's HNAs */
-      hna_gw = olsr_lookup_hna_gw(&vert->addr);
+        /*
+         * If there is a route entry, the prefix is already in the global RIB.
+         */
+        olsr_update_rt_path(rtp, tc, link);
 
-      /* node doesn't announce any HNAs */
-      if (!hna_gw) {
-        continue;
-      }
+      } else {
 
-      /* loop through the node's HNAs */
-      for (hna = hna_gw->networks.next;
-           hna != &hna_gw->networks;
-           hna = hna->next) {
-        if (vert->path_etx != INFINITE_ETX) {
-          olsr_insert_routing_table(&hna->A_network_addr, hna->prefixlen, &vert->addr,
-                                    &link->neighbor_iface_addr, inter->if_index,
-                                    vert->hops, vert->path_etx);
-        }
+        /*
+         * The prefix is reachable and not yet in the global RIB.
+         * Build a rt_entry for it.
+         */
+        olsr_insert_rt_path(rtp, tc, link);
       }
     }
   }
 
+  /* Update the RIB based on the new SPF results */
+
+  olsr_update_rib_routes();
+
 #ifdef SPF_PROFILING
   gettimeofday(&t4, NULL);
 #endif
index b3a2875..4379970 100644 (file)
@@ -36,7 +36,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: mid_set.c,v 1.27 2007/12/02 19:00:27 bernd67 Exp $
+ * $Id: mid_set.c,v 1.28 2007/12/12 21:57:27 bernd67 Exp $
  */
 
 #include "ipcalc.h"
@@ -47,6 +47,7 @@
 #include "scheduler.h"
 #include "neighbor_table.h"
 #include "link_set.h"
+#include "tc_set.h"
 #include "packet.h" /* struct mid_alias */
 #include "net_olsr.h"
 
@@ -98,7 +99,7 @@ olsr_init_mid_set(void)
  */
 
 void 
-insert_mid_tuple(const union olsr_ip_addr *m_addr, struct mid_address *alias, float vtime)
+insert_mid_tuple(union olsr_ip_addr *m_addr, struct mid_address *alias, float vtime)
 {
   struct mid_entry *tmp;
   struct mid_address *tmp_adr;
@@ -125,6 +126,12 @@ insert_mid_tuple(const union olsr_ip_addr *m_addr, struct mid_address *alias, fl
       return;
     }
 
+  /*
+   * Add a rt_path for the alias.
+   */
+  olsr_insert_routing_table(&alias->alias, olsr_cnf->maxplen, m_addr,
+                            OLSR_RT_ORIGIN_MID);
+
   /*If the address was registered*/ 
   if(tmp != &mid_set[hash])
     {
@@ -139,6 +146,7 @@ insert_mid_tuple(const union olsr_ip_addr *m_addr, struct mid_address *alias, fl
     {
       /*Create new node*/
       tmp = olsr_malloc(sizeof(struct mid_entry), "MID new alias");
+      memset(tmp, 0, sizeof(struct mid_entry));
 
       tmp->aliases = alias;
       alias->main_entry = tmp;
@@ -220,7 +228,7 @@ insert_mid_tuple(const union olsr_ip_addr *m_addr, struct mid_address *alias, fl
  *@return nada
  */
 void
-insert_mid_alias(const union olsr_ip_addr *main_add, const union olsr_ip_addr *alias, float vtime)
+insert_mid_alias(union olsr_ip_addr *main_add, const union olsr_ip_addr *alias, float vtime)
 {
   struct neighbor_entry *ne_old, *ne_new;
   struct mid_entry *me_old;
@@ -228,11 +236,14 @@ insert_mid_alias(const union olsr_ip_addr *main_add, const union olsr_ip_addr *a
 #ifndef NODEBUG
   struct ipaddr_str buf1, buf2;
 #endif
-  struct mid_address *adr = olsr_malloc(sizeof(struct mid_address), "Insert MID alias");
+  struct mid_address *adr;
   
   OLSR_PRINTF(1, "Inserting alias %s for ", olsr_ip_to_string(&buf1, alias));
   OLSR_PRINTF(1, "%s\n", olsr_ip_to_string(&buf1, main_add));
 
+  adr = olsr_malloc(sizeof(struct mid_address), "Insert MID alias");
+  memset(adr, 0, sizeof(struct mid_address));
+
   adr->alias = *alias;
   adr->next_alias = NULL;
   
@@ -445,6 +456,12 @@ olsr_prune_aliases(const union olsr_ip_addr *m_addr, struct mid_alias *declared_
 
           /* Remove from hash table */
           DEQUEUE_ELEM(current_alias);
+
+          /*
+           * Delete the rt_path for the alias.
+           */
+          olsr_delete_routing_table(&current_alias->alias, olsr_cnf->maxplen,
+                                    &entry->main_addr);
  
           free(current_alias);
 
@@ -511,22 +528,30 @@ olsr_time_out_mid_set(void *foo __attribute__((unused)))
  *@return 1
  */
 int
-mid_delete_node(struct mid_entry *entry)
+mid_delete_node(struct mid_entry *mid)
 {
   struct mid_address *aliases;
 
   /* Free aliases */
-  aliases = entry->aliases;
+  aliases = mid->aliases;
   while(aliases)
     {
       struct mid_address *tmp_aliases = aliases;
       aliases = aliases->next_alias;
       DEQUEUE_ELEM(tmp_aliases);
+
+
+      /*
+       * Delete the rt_path for the alias.
+       */
+      olsr_delete_routing_table(&tmp_aliases->alias, olsr_cnf->maxplen,
+                                &mid->main_addr);
+
       free(tmp_aliases);
     }
   /* Dequeue */
-  DEQUEUE_ELEM(entry);
-  free(entry);
+  DEQUEUE_ELEM(mid);
+  free(mid);
   
   return 0;
 }
@@ -564,7 +589,8 @@ olsr_print_mid_set(void)
 
 }
 
-
-
-
-
+/*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */
index 7bcb2f5..16adb04 100644 (file)
@@ -36,7 +36,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: mid_set.h,v 1.16 2007/11/08 22:47:41 bernd67 Exp $
+ * $Id: mid_set.h,v 1.17 2007/12/12 21:57:27 bernd67 Exp $
  */
 
 
@@ -51,7 +51,6 @@ struct mid_address
 {
   union olsr_ip_addr  alias;
   struct mid_entry   *main_entry;
-
   struct mid_address *next_alias;
 
   /* These are for the reverse list */
@@ -81,10 +80,10 @@ int
 olsr_init_mid_set(void);
 
 void 
-insert_mid_tuple(const union olsr_ip_addr *, struct mid_address *, float);
+insert_mid_tuple(union olsr_ip_addr *, struct mid_address *, float);
 
 void
-insert_mid_alias(const union olsr_ip_addr *, const union olsr_ip_addr *, float);
+insert_mid_alias(union olsr_ip_addr *, const union olsr_ip_addr *, float);
 
 union olsr_ip_addr *
 mid_lookup_main_addr(const union olsr_ip_addr *);
@@ -92,6 +91,9 @@ mid_lookup_main_addr(const union olsr_ip_addr *);
 struct mid_address *
 mid_lookup_aliases(const union olsr_ip_addr *);
 
+struct mid_entry *
+mid_lookup_entry_bymain(const union olsr_ip_addr *);
+
 void
 olsr_print_mid_set(void);
 
@@ -108,3 +110,9 @@ int
 mid_delete_node(struct mid_entry *);
 
 #endif
+
+/*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */
index b6dc26e..1b22891 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.65 2007/12/02 19:00:27 bernd67 Exp $
+ * $Id: olsr.c,v 1.66 2007/12/12 21:57:27 bernd67 Exp $
  */
 
 /**
@@ -160,31 +160,18 @@ olsr_process_changes(void)
       printf("       *** %s (%s on %s) ***\n", olsrd_version, build_date, build_host);
   }
 
-  if (changes_neighborhood)
-    {
-      /* Calculate new mprs, HNA and routing table */
-      if (olsr_cnf->lq_level < 1)
-        {
-          olsr_calculate_mpr();
-        }
-
-      else
-        {
-          olsr_calculate_lq_mpr();
-        }
-
-      olsr_calculate_routing_table();
-      olsr_calculate_hna_routes();
-    }
-  
-  else if (changes_topology || changes_hna)
-    {
-      /* calculate the routing table and HNA */
-
-        olsr_calculate_routing_table();
-        olsr_calculate_hna_routes();
+  if (changes_neighborhood) {
+    if (olsr_cnf->lq_level < 1) {
+      olsr_calculate_mpr();
+    } else {
+      olsr_calculate_lq_mpr();
     }
+  }
 
+  /* calculate the routing table */
+  if (changes_neighborhood || changes_topology || changes_hna) {
+    olsr_calculate_routing_table();
+  }
   
   if (olsr_cnf->debug_level > 0)
     {      
@@ -201,11 +188,13 @@ olsr_process_changes(void)
               olsr_print_hna_set();
             }
         }
-      
+
+#if 1     
       olsr_print_link_set();
       olsr_print_neighbor_table();
       olsr_print_two_hop_neighbor_table();
       olsr_print_tc_table();
+#endif
     }
 
   for(tmp_pc_list = pcf_list; 
@@ -608,3 +597,9 @@ olsr_printf(int loglevel, const char *format, ...)
     }
   return 0;
 }
+
+/*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */
index 18ef500..72f99f9 100644 (file)
@@ -36,7 +36,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: olsr_cfg.h,v 1.42 2007/11/29 22:21:26 bernd67 Exp $
+ * $Id: olsr_cfg.h,v 1.43 2007/12/12 21:57:27 bernd67 Exp $
  */
 
 
@@ -62,6 +62,7 @@
 #define DEF_DEBUGLVL        1
 #define DEF_IPC_CONNECTIONS 0
 #define DEF_USE_HYST        OLSR_FALSE
+#define DEF_FLAT_FIB_METRIC OLSR_TRUE
 #define DEF_LQ_LEVEL        2
 #define DEF_LQ_FISH         0
 #define DEF_LQ_DIJK_LIMIT   255
@@ -193,6 +194,7 @@ struct olsrd_config
   olsr_bool                willingness_auto;
   int                      ipc_connections;
   olsr_bool                use_hysteresis;
+  olsr_bool                flat_fib_metric;
   struct hyst_param        hysteresis_param;
   struct plugin_entry      *plugins;
   struct ip_prefix_list    *hna_entries;
@@ -279,3 +281,9 @@ olsrd_get_default_cnf(void);
 #endif
 
 #endif
+
+/*
+ * Local Variables:
+ * c-basic-offset: 2
+ * End:
+ */
index 0631115..0ce6fde 100644 (file)
@@ -40,7 +40,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: process_routes.c,v 1.42 2007/12/02 19:00:28 bernd67 Exp $
+ * $Id: process_routes.c,v 1.43 2007/12/12 21:57:27 bernd67 Exp $
  */
 
 #include "ipcalc.h"
@@ -50,6 +50,7 @@
 #include "kernel_routes.h"
 #include "lq_avl.h"
 #include "net_olsr.h"
+#include "tc_set.h"
 
 #ifdef WIN32
 #undef strerror
@@ -111,8 +112,8 @@ olsr_init_export_route(void)
  *Deletes all OLSR routes
  *
  * 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.
+ * tree and then olsr_update_rib_routes() will see all routes in the tree
+ * as outdated and olsr_update_kernel_routes() will finally flush it.
  *
  *@return 1
  */
@@ -122,6 +123,7 @@ olsr_delete_all_kernel_routes(void)
   OLSR_PRINTF(1, "Deleting all routes...\n");
 
   olsr_bump_routingtree_version();
+  olsr_update_rib_routes();
   olsr_update_kernel_routes();
 }
 
@@ -198,8 +200,9 @@ olsr_add_kernel_route(struct rt_entry *rt)
 
       /* route addition has suceeded */
 
-      /* save the nexthop in the route entry */
+      /* save the nexthop and metric in the route entry */
       rt->rt_nexthop = rt->rt_best->rtp_nexthop;
+      rt->rt_metric = rt->rt_best->rtp_metric;
     }
   }
 }
@@ -282,7 +285,8 @@ olsr_del_kernel_routes(struct list_node *head_node)
 
 /**
  * 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.
+ * If a route does not match the current routing tree number, remove it
+ * from the global originator tree for that rt_entry.
  * Reset the best route pointer.
  */
 static void
@@ -310,7 +314,7 @@ olsr_delete_outdated_routes(struct rt_entry *rt)
 
       /* remove from the originator tree */
       avl_delete(&rt->rt_path_tree, rtp_tree_node);
-      free(rtp);
+      rtp->rtp_rt = NULL;
     }
   }
 
@@ -322,10 +326,10 @@ olsr_delete_outdated_routes(struct rt_entry *rt)
  * 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.
+ * path and enqueue an add/chg operation.
  */
 void
-olsr_update_kernel_routes(void)
+olsr_update_rib_routes(void)
 {
   struct rt_entry *rt;
 
@@ -350,8 +354,10 @@ olsr_update_kernel_routes(void)
     /* run best route election */
     olsr_rt_best(rt);
 
-    /* nexthop change ? */
-    if (olsr_nh_change(&rt->rt_best->rtp_nexthop, &rt->rt_nexthop)) {
+    /* nexthop or hopcount change ? */
+    if (olsr_nh_change(&rt->rt_best->rtp_nexthop, &rt->rt_nexthop) ||
+        (!olsr_cnf->flat_fib_metric &&
+         olsr_hopcount_change(&rt->rt_best->rtp_metric, &rt->rt_metric))) {
 
       if (0 > rt->rt_nexthop.iif_index) {
 
@@ -364,6 +370,14 @@ olsr_update_kernel_routes(void)
       }
     }
   } OLSR_FOR_ALL_RT_ENTRIES_END(rt);
+}
+
+/**
+ * Propagate the accumulated changes from the last rib update to the kernel.
+ */
+void
+olsr_update_kernel_routes(void)
+{
 
   /* delete unreachable routes */
   olsr_del_kernel_routes(&del_kernel_list);
index 381607c..7ba3e9f 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.15 2007/12/02 19:00:28 bernd67 Exp $
+ * $Id: process_routes.h,v 1.16 2007/12/12 21:57:27 bernd67 Exp $
  */
 
 #ifndef _OLSR_PROCESS_RT
@@ -52,16 +52,10 @@ extern export_route_function olsr_addroute6_function;
 extern export_route_function olsr_delroute_function;
 extern export_route_function olsr_delroute6_function;
 
-void
-olsr_init_export_route(void);
-
-void
-olsr_update_kernel_routes(void);
-
-void
-olsr_delete_all_kernel_routes(void);
-
-olsr_u8_t
-olsr_rt_flags(const struct rt_entry *);
+void olsr_init_export_route(void);
+void olsr_update_rib_routes(void);
+void olsr_update_kernel_routes(void);
+void olsr_delete_all_kernel_routes(void);
+olsr_u8_t olsr_rt_flags(const struct rt_entry *);
 
 #endif
index aa815de..671e381 100644 (file)
@@ -37,7 +37,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: routing_table.c,v 1.38 2007/11/29 22:59:51 bernd67 Exp $
+ * $Id: routing_table.c,v 1.39 2007/12/12 21:57:27 bernd67 Exp $
  */
 
 #include "routing_table.h"
 
 #include <assert.h>
 
+/* Root of our RIB */
 struct avl_tree routingtree;
+
+/*
+ * Keep a version number for detecting outdated elements
+ * in the per rt_entry rt_path subtree.
+ */
 unsigned int routingtree_version;
 
 /**
@@ -122,11 +128,12 @@ avl_comp_ipv4_prefix (const void *prefix1, const void *prefix2)
 int
 avl_comp_ipv6_prefix (const void *prefix1, const void *prefix2)
 {       
+  int res;
   const struct olsr_ip_prefix *pfx1 = prefix1;
   const struct olsr_ip_prefix *pfx2 = prefix2;
 
   /* prefix */
-  int res = ip6cmp(&pfx1->prefix.v6, &pfx2->prefix.v6);
+  res = memcmp(&pfx1->prefix.v6, &pfx2->prefix.v6, 16);
   if (res != 0) {
     return res;
   } 
@@ -175,32 +182,24 @@ olsr_lookup_routing_table(const union olsr_ip_addr *dst)
 }
 
 /**
- * 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.
+ * Update gateway/interface/etx/hopcount and the version for a route path.
  */
-static void
-olsr_update_routing_entry(struct rt_path *rtp, union olsr_ip_addr *gateway,
-                          int iif_index, int metric, float etx)
+void
+olsr_update_rt_path(struct rt_path *rtp, struct tc_entry *tc,
+                    struct link_entry *link)
 {
 
   rtp->rtp_version = routingtree_version;
 
   /* gateway */
-  rtp->rtp_nexthop.gateway = *gateway;
+  rtp->rtp_nexthop.gateway = link->neighbor_iface_addr;
 
   /* interface */
-  rtp->rtp_nexthop.iif_index = iif_index;
+  rtp->rtp_nexthop.iif_index = link->inter->if_index;
 
-  /* 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;
-  }
+  /* metric/etx */
+  rtp->rtp_metric.hops = tc->hops;
+  rtp->rtp_metric.etx = tc->path_etx;
 }
 
 /**
@@ -232,13 +231,12 @@ olsr_alloc_rt_entry(struct olsr_ip_prefix *prefix)
   return rt;
 }
 
-
 /**
  * Alloc and key a new rt_path.
  */
 static struct rt_path *
-olsr_alloc_rt_path(struct rt_entry *rt,
-                   union olsr_ip_addr *originator)
+olsr_alloc_rt_path(struct tc_entry *tc,
+                   struct olsr_ip_prefix *prefix, olsr_u8_t origin)
 {
   struct rt_path *rtp = olsr_malloc(sizeof(struct rt_path), __FUNCTION__);
 
@@ -248,22 +246,109 @@ olsr_alloc_rt_path(struct rt_entry *rt,
 
   memset(rtp, 0, sizeof(*rtp));
 
-  rtp->rtp_originator = *originator;
+  rtp->rtp_dst = *prefix;
 
   /* set key and backpointer prior to tree insertion */
-  rtp->rtp_tree_node.key = &rtp->rtp_originator;
-  rtp->rtp_tree_node.data = rtp;
+  rtp->rtp_prefix_tree_node.key = &rtp->rtp_dst;
+  rtp->rtp_prefix_tree_node.data = rtp;
+
+  /* insert to the tc prefix tree */
+  avl_insert(&tc->prefix_tree, &rtp->rtp_prefix_tree_node, AVL_DUP_NO);
 
-  /* insert to the route entry originator tree */
-  avl_insert(&rt->rt_path_tree, &rtp->rtp_tree_node, AVL_DUP_NO);
+  /* backlink to the owning tc entry */
+  rtp->rtp_tc = tc;
 
-  /* backlink to the owning route entry */
-  rtp->rtp_rt = rt;
+  /* store the origin of the route */
+  rtp->rtp_origin = origin;
 
   return rtp;
 }
 
 /**
+ * Create a route entry for a given rt_path and
+ * insert it into the global RIB tree.
+ */
+void
+olsr_insert_rt_path(struct rt_path *rtp, struct tc_entry *tc,
+                    struct link_entry *link)
+{
+  struct rt_entry *rt;
+  struct avl_node *node;
+
+  /*
+   * no unreachable routes please.
+   */
+  if (tc->path_etx >= INFINITE_ETX) {
+    return;
+  }
+
+  /*
+   * No bogus prefix lengths.
+   */
+  if (rtp->rtp_dst.prefix_len > olsr_cnf->maxplen) {
+    return;
+  }
+
+  /*
+   * first check if there is a route_entry for the prefix.
+   */
+  node = avl_find(&routingtree, &rtp->rtp_dst);
+
+  if (!node) {
+
+    /* no route entry yet */
+    rt = olsr_alloc_rt_entry(&rtp->rtp_dst);
+
+    if (!rt) {
+      return;
+    }
+
+    /* Now insert the rt_path to the owning rt_entry tree */
+
+    rtp->rtp_originator = tc->addr;
+
+    /* 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;
+
+  } else {
+    rt = node->data;
+  }
+
+  /* update the version field and relevant parameters */
+  olsr_update_rt_path(rtp, tc, link);
+}
+
+/**
+ * Unlink and free a rt_path.
+ */
+static void
+olsr_free_rt_path(struct rt_path *rtp)
+{
+
+  /* remove from the originator tree */
+  if (rtp->rtp_rt) {
+    avl_delete(&rtp->rtp_rt->rt_path_tree, &rtp->rtp_tree_node);
+    rtp->rtp_rt = NULL;
+  }
+
+  /* remove from the tc prefix tree */
+  if (rtp->rtp_tc) {
+    avl_delete(&rtp->rtp_tc->prefix_tree, &rtp->rtp_prefix_tree_node);
+    rtp->rtp_tc = NULL;
+  }
+
+  free(rtp);
+}
+
+
+/**
  * Check if there is an interface or gateway change.
  */
 olsr_bool
@@ -277,6 +362,31 @@ olsr_nh_change(const struct rt_nexthop *nh1, const struct rt_nexthop *nh2)
 }
 
 /**
+ * Check if there is a hopcount change.
+ */
+olsr_bool
+olsr_hopcount_change(const struct rt_metric *met1, const struct rt_metric *met2)
+{
+  return (met1->hops != met2->hops);
+}
+
+/**
+ * Depending if flat_metric is configured and the kernel fib operation
+ * return the hopcount metric of a route.
+ * For adds this is the metric of best rour after olsr_rt_best() election,
+ * for deletes this is the metric of the route that got stored in the rt_entry,
+ * during route installation.
+ */
+olsr_u8_t
+olsr_fib_metric(const struct rt_metric *met)
+{
+  if (!olsr_cnf->flat_fib_metric) {
+    return met->hops;
+  }
+  return RT_METRIC_DEFAULT;
+}
+
+/**
  * depending on the operation (add/chg/del) the nexthop
  * field from the route entry or best route path shall be used.
  */
@@ -351,7 +461,7 @@ olsr_rt_best(struct rt_entry *rt)
   rt->rt_best = node->data;
 
   /* walk all remaining originator entries */
-  while ((node = avl_walk_next(node)) != NULL) {
+  while ((node = avl_walk_next(node))) {
     struct rt_path *rtp = node->data;
 
     if (olsr_cmp_rtp(rtp, rt->rt_best)) {
@@ -361,96 +471,126 @@ olsr_rt_best(struct rt_entry *rt)
 }
 
 /**
- * Insert/Update a route entry into the routing table.
+ * Insert a prefix into the prefix tree hanging off a lsdb (tc) entry.
  *
- * 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.
+ * Check if the candidate route (we call this a rt_path) is known,
+ * if not create it.
+ * Upon post-SPF processing (if the node is reachable) the prefix
+ * will be finally inserted into the global RIB.
  *
  *@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
+ *@param originator the originating router
  *
- *@return the new rt_entry struct
+ *@return the new rt_path struct
  */
 struct rt_path *
-olsr_insert_routing_table(union olsr_ip_addr *dst, 
-                          int plen,
-                          union olsr_ip_addr *originator,
-                         union olsr_ip_addr *gateway,
-                         int iif_index,
-                         int metric,
-                         float etx)
+olsr_insert_routing_table(union olsr_ip_addr *dst, int plen,
+                          union olsr_ip_addr *originator, int origin)
 {
-  struct rt_entry *rt;
+#if !defined(NODEBUG) && defined(DEBUG)
+  struct ipaddr_str buf;
+#endif
+  struct tc_entry *tc;
   struct rt_path *rtp;
   struct avl_node *node;
   struct olsr_ip_prefix prefix;
 
   /*
-   * no unreachable routes please.
+   * No bogus prefix lengths.
    */
-  if (etx >= INFINITE_ETX) {
+  if (plen > olsr_cnf->maxplen) {
     return NULL;
   }
 
+  OLSR_PRINTF(1, "RIB: add prefix %s/%u from %s\n",
+              olsr_ip_to_string(&buf, dst), plen,
+              olsr_ip_to_string(&buf, originator));
+
   /*
-   * No bogus prefix lengths.
+   * For internal routes the tc_entry must already exist.
+   * For all other routes we may create it as an edgeless
+   * hookup point. If so he tc_entry has no edges it will not
+   * be explored during SPF run.
    */
-  if (plen > olsr_cnf->maxplen) {
-    return NULL;
-  }
+  tc = olsr_locate_tc_entry(originator);
   
   /*
-   * first check if there is a route_entry for the prefix.
+   * first check if there is a rt_path for the prefix.
    */
   prefix.prefix = *dst;
   prefix.prefix_len = plen;
 
-  node = avl_find(&routingtree, &prefix);
+  node = avl_find(&tc->prefix_tree, &prefix);
 
   if (!node) {
 
-    /* no route entry yet */
-    rt = olsr_alloc_rt_entry(&prefix);
+    /* no rt_path for this prefix yet */
+    rtp = olsr_alloc_rt_path(tc, &prefix, origin);
 
-    if (!rt) {
+    if (!rtp) {
       return NULL;
     }
 
+    /* overload the hna change bit for flagging a prefix change */
+    changes_hna = OLSR_TRUE;
+
   } else {
-    rt = node->data;
+    rtp = node->data;
   }
 
+  return rtp;
+}
+
+/**
+ * Delete a prefix from the prefix tree hanging off a lsdb (tc) entry.
+ */
+void
+olsr_delete_routing_table(union olsr_ip_addr *dst, int plen,
+                          union olsr_ip_addr *originator)
+{
+#if !defined(NODEBUG) && defined(DEBUG)
+  struct ipaddr_str buf;
+#endif
+
+  struct tc_entry *tc;
+  struct rt_path *rtp;
+  struct avl_node *node;
+  struct olsr_ip_prefix prefix;
+
   /*
-   * next check if the route path from this originator is known
+   * No bogus prefix lengths.
    */
-  node = avl_find(&rt->rt_path_tree, originator);
+  if (plen > olsr_cnf->maxplen) {
+    return;
+  }
 
-  if (!node) {
+#ifdef DEBUG
+  OLSR_PRINTF(1, "RIB: del prefix %s/%u from %s\n",
+              olsr_ip_to_string(&buf, dst), plen,
+              olsr_ip_to_string(&buf, originator));
+#endif
 
-    /* no route path from this originator yet */
-    rtp = olsr_alloc_rt_path(rt, originator);
+  tc = olsr_lookup_tc_entry(originator);
+  if (!tc) {
+    return;
+  }
 
-    if (!rtp) {
-      return NULL;
-    }
+  /*
+   * Grab the rt_path for the prefix.
+   */
+  prefix.prefix = *dst;
+  prefix.prefix_len = plen;
 
-  } else {
-    rtp = node->data;
-  }
+  node = avl_find(&tc->prefix_tree, &prefix);
 
-  /* update the version field and relevant parameters */
-  olsr_update_routing_entry(rtp, gateway, iif_index, metric, etx);
+  if (node) {
+    rtp = node->data;
+    olsr_free_rt_path(rtp);
 
-  return rtp;
+    /* overload the hna change bit for flagging a prefix change */
+    changes_hna = OLSR_TRUE;
+  }
 }
 
 /**
@@ -496,46 +636,6 @@ olsr_rtp_to_string(const struct rt_path *rtp)
 }
 
 /**
- *Calculate the HNA routes
- *
- */
-void
-olsr_calculate_hna_routes(void)
-{
-  int idx;
-
-#ifdef DEBUG
-  OLSR_PRINTF(3, "Calculating HNA routes\n");
-#endif
-
-  for (idx = 0; idx < HASHSIZE; idx++) {
-    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) {
-        /* If no route to gateway - skip */
-        struct rt_entry *rt = olsr_lookup_routing_table(&tmp_hna->A_gateway_addr);
-        if (rt != NULL) {
-          /* update if better */
-          olsr_insert_routing_table(&tmp_net->A_network_addr,
-                                    tmp_net->prefixlen,
-                                    &tmp_hna->A_gateway_addr,
-                                    &rt->rt_best->rtp_nexthop.gateway,
-                                    rt->rt_best->rtp_nexthop.iif_index,
-                                    rt->rt_best->rtp_metric.hops,
-                                    rt->rt_best->rtp_metric.etx);
-        }
-      }
-    }
-  }
-
-  /* Update kernel */
-  olsr_update_kernel_routes();
-}
-
-/**
  * Print the routingtree to STDOUT
  *
  */
index 8c84e71..c35e402 100644 (file)
@@ -37,7 +37,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: routing_table.h,v 1.25 2007/11/11 23:10:24 bernd67 Exp $
+ * $Id: routing_table.h,v 1.26 2007/12/12 21:57:27 bernd67 Exp $
  */
 
 #ifndef _OLSR_ROUTING_TABLE
@@ -45,6 +45,7 @@
 
 #include <net/route.h>
 #include "hna_set.h"
+#include "link_set.h"
 #include "lq_avl.h"
 #include "lq_list.h"
 
@@ -84,6 +85,7 @@ struct rt_entry
   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 rt_metric      rt_metric; /* metric of FIB route */
   struct avl_tree       rt_path_tree;
   struct list_node      rt_change_node; /* queue for kernel FIB add/chg/del */
 };
@@ -92,18 +94,42 @@ struct rt_entry
  * 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.
+ * The rt_path gets first inserted into the per tc_entry prefix tree.
+ * If during the SPF calculation the tc_entry becomes reachable via
+ * a local nexthop it is inserted into the global RIB tree.
  */
 struct rt_path
 {
   struct rt_entry       *rtp_rt; /* backpointer to owning route head */
+  struct tc_entry       *rtp_tc; /* backpointer to owning tc entry */
   struct rt_nexthop     rtp_nexthop;
   struct rt_metric      rtp_metric;
+  struct avl_node       rtp_tree_node; /* global rtp node */
   union olsr_ip_addr    rtp_originator; /* originator of the route */
-  struct avl_node       rtp_tree_node; 
-  olsr_u32_t            rtp_version;
+  struct avl_node       rtp_prefix_tree_node; /* tc entry rtp node */
+  struct olsr_ip_prefix rtp_dst; /* the prefix */
+  olsr_u32_t            rtp_version; /* for detection of outdated rt_paths */
+  olsr_u8_t             rtp_origin; /* internal, MID or HNA */
 };
 
 /*
+ * In olsrd we have three different route types.
+ * Internal routes are generated by simple reachability
+ * of a node (by means of a tc message reception).
+ * MID routes result from MID messages and HNA routes
+ * from a gw routers HNA anncouncements.
+ */
+enum olsr_rt_origin {
+  OLSR_RT_ORIGIN_MIN,
+  OLSR_RT_ORIGIN_INT,
+  OLSR_RT_ORIGIN_MID,
+  OLSR_RT_ORIGIN_HNA,
+  OLSR_RT_ORIGIN_MAX
+};
+
+/*
+ * OLSR_FOR_ALL_RT_ENTRIES
+ *
  * macro for traversing the entire routing table.
  * it is recommended to use this because it hides all the internal
  * datastructure from the callers.
@@ -120,6 +146,30 @@ struct rt_path
     rt = rt_tree_node->data;
 #define OLSR_FOR_ALL_RT_ENTRIES_END(rt) }}
 
+/*
+ * OLSR_FOR_ALL_HNA_RT_ENTRIES
+ *
+ * macro for traversing the entire routing table and pick only
+ * HNA routes. This is not optimal - however, If the RIBs become
+ * too big one day then we keep an additional per origin tree
+ * in order to speed up traversal.
+ * In the meantime it is recommended to use this macro because
+ * it hides all the internal datastructure from the callers
+ * and the core maintainers do not have to update all the plugins
+ * once we decide to change the datastructures.
+ */
+#define OLSR_FOR_ALL_HNA_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; \
+    if (rt->rt_best->rtp_origin != OLSR_RT_ORIGIN_HNA) \
+      continue; 
+#define OLSR_FOR_ALL_HNA_RT_ENTRIES_END(rt) }}
+
+
 /**
  * IPv4 <-> IPv6 wrapper
  */
@@ -154,20 +204,21 @@ int avl_comp_ipv6_prefix (const void *, const void *);
 
 void olsr_rt_best(struct rt_entry *);
 olsr_bool olsr_nh_change(const struct rt_nexthop *, const struct rt_nexthop *);
+olsr_bool olsr_hopcount_change(const struct rt_metric *, const struct rt_metric *);
 olsr_bool olsr_cmp_rt(const struct rt_entry *, const struct rt_entry *);
+olsr_u8_t olsr_fib_metric(const struct rt_metric *);
 
-void olsr_calculate_hna_routes(void);
 char *olsr_rt_to_string(const struct rt_entry *);
 char *olsr_rtp_to_string(const struct rt_path *);
 void olsr_print_routing_table(const struct avl_tree *);
 
 const struct rt_nexthop * olsr_get_nh(const struct rt_entry *);
 
-struct rt_path *
-olsr_insert_routing_table(union olsr_ip_addr *, int,
-                          union olsr_ip_addr *,
-                          union olsr_ip_addr *,
-                          int, int, float);
+/* rt_path manipulation */
+struct rt_path *olsr_insert_routing_table(union olsr_ip_addr *, int, union olsr_ip_addr *, int);
+void olsr_delete_routing_table(union olsr_ip_addr *, int, union olsr_ip_addr *);
+void olsr_insert_rt_path(struct rt_path *, struct tc_entry *, struct link_entry *);
+void olsr_update_rt_path(struct rt_path *, struct tc_entry *, struct link_entry *);
 
 struct rt_entry *
 olsr_lookup_routing_table(const union olsr_ip_addr *);
index 5b6e01d..b985748 100644 (file)
@@ -37,7 +37,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: tc_set.c,v 1.40 2007/11/29 22:59:51 bernd67 Exp $
+ * $Id: tc_set.c,v 1.41 2007/12/12 21:57:27 bernd67 Exp $
  */
 
 #include "tc_set.h"
@@ -123,8 +123,13 @@ olsr_delete_tc_entry(struct tc_entry *tc)
   OLSR_PRINTF(1, "TC: del entry %s\n", olsr_ip_to_string(%buf, &tc->addr));
 #endif
 
-  /* The edgetree must be empty before */
-  assert(!tc->edge_tree.count);
+  /*
+   * Delete the rt_path for ourselves.
+   */
+  olsr_delete_routing_table(&tc->addr, olsr_cnf->maxplen, &tc->addr);
+
+  /* The edgetree and prefix tree must be empty before */
+  assert(!tc->edge_tree.count && !tc->prefix_tree.count);
 
   avl_delete(&tc_tree, &tc->vertex_node);
   free(tc);
@@ -181,9 +186,12 @@ olsr_getnext_tc_entry(struct tc_entry *tc)
 struct tc_entry *
 olsr_add_tc_entry(union olsr_ip_addr *adr)
 {
-  struct tc_entry *tc;
-#if 0
+#if !defined(NODEBUG) && defined(DEBUG)
   struct ipaddr_str buf;
+#endif
+  struct tc_entry *tc;
+
+#ifdef DEBUG
   OLSR_PRINTF(1, "TC: add entry %s\n", olsr_ip_to_string(&buf, adr));
 #endif
 
@@ -204,13 +212,34 @@ olsr_add_tc_entry(union olsr_ip_addr *adr)
   avl_insert(&tc_tree, &tc->vertex_node, AVL_DUP_NO);
 
   /*
-   * Initialize subtree for further edges to come.
+   * Initialize subtrees for edges and prefixes.
    */
   avl_init(&tc->edge_tree, avl_comp_default);
+  avl_init(&tc->prefix_tree, avl_comp_prefix_default);
+
+  /*
+   * Add a rt_path for ourselves.
+   */
+  olsr_insert_routing_table(adr, olsr_cnf->maxplen, adr,
+                            OLSR_RT_ORIGIN_INT);
 
   return tc;
 }
 
+/*
+ * Lookup a tc entry. Creates one if it does not exist yet.
+ */
+struct tc_entry *
+olsr_locate_tc_entry(union olsr_ip_addr *adr)
+{
+  struct tc_entry *tc;
+
+  if (!(tc = olsr_lookup_tc_entry(adr))) {
+    return olsr_add_tc_entry(adr);
+  }
+  return tc;
+}
+
 /**
  * format a tc_edge contents into a buffer
  */
@@ -239,7 +268,7 @@ olsr_tc_edge_to_string(struct tc_edge_entry *tc_edge)
  * it does also the correct insertion and sorting in the timer tree.
  * The timer param is a relative timer expressed in milliseconds.
  */
-static void
+void
 olsr_set_tc_edge_timer(struct tc_edge_entry *tc_edge, unsigned int timer)
 {
   tc_edge->T_time = GET_TIMESTAMP(timer);
@@ -272,6 +301,9 @@ olsr_add_tc_edge_entry(struct tc_entry *tc, union olsr_ip_addr *addr,
                        olsr_u16_t ansn, unsigned int vtime,
                        float link_quality, float neigh_link_quality)
 {
+#if !defined(NODEBUG) && defined(DEBUG)
+  struct ipaddr_str buf;
+#endif
   struct tc_entry *tc_neighbor;
   struct tc_edge_entry *tc_edge, *tc_edge_inv;
 
@@ -311,7 +343,7 @@ olsr_add_tc_edge_entry(struct tc_entry *tc, union olsr_ip_addr *addr,
    */
   tc_edge->tc = tc;
 
-#if 0
+#ifdef DEBUG
   OLSR_PRINTF(1, "TC: add edge entry %s\n", olsr_tc_edge_to_string(tc_edge));
 #endif
 
@@ -321,16 +353,16 @@ olsr_add_tc_edge_entry(struct tc_entry *tc, union olsr_ip_addr *addr,
    */
   tc_neighbor = olsr_lookup_tc_entry(&tc_edge->T_dest_addr);
   if (tc_neighbor) {
-#if 0
+#ifdef DEBUG
     OLSR_PRINTF(1, "TC:   found neighbor tc_entry %s\n",
-                olsr_ip_to_string(&tc_neighbor->addr));
+                olsr_ip_to_string(&buf, &tc_neighbor->addr));
 #endif
 
     tc_edge_inv = olsr_lookup_tc_edge(tc_neighbor, &tc->addr);
     if (tc_edge_inv) {
-#if 0
+#ifdef DEBUG
       OLSR_PRINTF(1, "TC:   found inverse edge for %s\n",
-                  olsr_ip_to_string(&tc_edge_inv->T_dest_addr));
+                  olsr_ip_to_string(&buf, &tc_edge_inv->T_dest_addr));
 #endif
 
       /*
@@ -363,7 +395,7 @@ olsr_delete_tc_edge_entry(struct tc_edge_entry *tc_edge)
   struct tc_entry *tc;
   struct tc_edge_entry *tc_edge_inv;
 
-#if 0
+#ifdef DEBUG
   OLSR_PRINTF(1, "TC: del edge entry %s\n", olsr_tc_edge_to_string(tc_edge));
 #endif
 
@@ -379,9 +411,10 @@ olsr_delete_tc_edge_entry(struct tc_edge_entry *tc_edge)
   }
 
   /*
-   * Delete the tc_entry if the last edge is gone.
+   * Delete the tc_entry if the last edge and last prefix is gone.
    */
-  if (!tc_edge->tc->edge_tree.count) {
+  if (!tc_edge->tc->edge_tree.count &&
+      !tc_edge->tc->prefix_tree.count) {
 
     /*
      * Only remove remote tc entries.
@@ -545,7 +578,7 @@ olsr_tc_update_edge(struct tc_entry *tc, unsigned int vtime_s, olsr_u16_t ansn,
      */
     olsr_calc_tc_edge_entry_etx(tc_edge);
 
-#if 0
+#if DEBUG
     if (edge_change) {          
       OLSR_PRINTF(1, "TC:   chg edge entry %s\n",
                   olsr_tc_edge_to_string(tc_edge));
index 5f0a28d..04b6760 100644 (file)
@@ -37,7 +37,7 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: tc_set.h,v 1.23 2007/11/16 21:43:55 bernd67 Exp $
+ * $Id: tc_set.h,v 1.24 2007/12/12 21:57:27 bernd67 Exp $
  */
 
 #ifndef _OLSR_TOP_SET
@@ -83,7 +83,8 @@ struct tc_entry
   struct list_node   path_list_node; /* SPF result list */
   union olsr_ip_addr addr; /* vertex_node key */
   struct avl_tree    edge_tree; /* subtree for edges */
-  struct link_entry *next_hop; /* SPF calculated link to the 1st hop neighbor */
+  struct avl_tree    prefix_tree; /* subtree for prefixes */
+  struct link_entry  *next_hop; /* SPF calculated link to the 1st hop neighbor */
   float              path_etx; /* SPF calculated distance, cand_tree_node key */
   olsr_u16_t         msg_seq; /* sequence number of the tc message */
   olsr_u8_t          msg_hops; /* hopcount as per the tc message */
@@ -91,7 +92,7 @@ struct tc_entry
 };
 
 /*
- * macros for traversing the vertices and edges in the link state database.
+ * macros for traversing vertices, edges and prefixes in the link state database.
  * it is recommended to use this because it hides all the internal
  * datastructure from the callers.
  *
@@ -130,6 +131,7 @@ void olsr_input_tc(union olsr_message *, struct interface *,
 
 /* tc_entry manipulation */
 struct tc_entry *olsr_lookup_tc_entry(union olsr_ip_addr *);
+struct tc_entry *olsr_locate_tc_entry(union olsr_ip_addr *);
 struct tc_entry *olsr_add_tc_entry(union olsr_ip_addr *);
 struct tc_entry *olsr_getnext_tc_entry(struct tc_entry *);
 
@@ -144,6 +146,7 @@ void olsr_delete_tc_entry(struct tc_entry *);
 void olsr_delete_tc_edge_entry(struct tc_edge_entry *);
 void olsr_calc_tc_edge_entry_etx(struct tc_edge_entry *);
 float olsr_calc_tc_etx(const struct tc_edge_entry *);
+void olsr_set_tc_edge_timer(struct tc_edge_entry *, unsigned int);
 
 #endif
 
index 69f0e47..250b11f 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.26 2007/11/29 22:21:26 bernd67 Exp $
+ * $Id: kernel_routes.c,v 1.27 2007/12/12 21:57:27 bernd67 Exp $
  */
 
 #include <stdio.h>
@@ -86,7 +86,7 @@ int olsr_ioctl_add_route(const struct rt_entry *rt)
   Row.dwForwardProto = 3; // MIB_IPPROTO_NETMGMT
   Row.dwForwardAge = INFINITE;
   Row.dwForwardNextHopAS = 0;
-  Row.dwForwardMetric1 = RT_METRIC_DEFAULT;
+  Row.dwForwardMetric1 = olsr_fib_metric(&rt->rt_best->rtp_metric.hops);
   Row.dwForwardMetric2 = -1;
   Row.dwForwardMetric3 = -1;
   Row.dwForwardMetric4 = -1;
@@ -163,7 +163,7 @@ int olsr_ioctl_del_route(const struct rt_entry *rt)
   Row.dwForwardProto = 3; // MIB_IPPROTO_NETMGMT
   Row.dwForwardAge = INFINITE;
   Row.dwForwardNextHopAS = 0;
-  Row.dwForwardMetric1 = RT_METRIC_DEFAULT;
+  Row.dwForwardMetric1 = olsr_fib_metric(&rt->rt_metric.hops);
   Row.dwForwardMetric2 = -1;
   Row.dwForwardMetric3 = -1;
   Row.dwForwardMetric4 = -1;