Merge branch 'pud' into stable
[olsrd.git] / src / routing_table.c
index d50e945..749b479 100644 (file)
@@ -1,34 +1,35 @@
+
 /*
  * The olsr.org Optimized Link-State Routing daemon(olsrd)
- * Copyright (c) 2004, Andreas TΓΈnnesen(andreto@olsr.org)
+ * Copyright (c) 2004, Andreas Tonnesen(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 
- * modification, are permitted provided that the following conditions 
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
  * are met:
  *
- * * Redistributions of source code must retain the above copyright 
+ * * Redistributions of source code must retain the above copyright
  *   notice, this list of conditions and the following disclaimer.
- * * Redistributions in binary form must reproduce the above copyright 
- *   notice, this list of conditions and the following disclaimer in 
- *   the documentation and/or other materials provided with the 
+ * * Redistributions in binary form must reproduce the above copyright
+ *   notice, this list of conditions and the following disclaimer in
+ *   the documentation and/or other materials provided with the
  *   distribution.
- * * Neither the name of olsr.org, olsrd nor the names of its 
- *   contributors may be used to endorse or promote products derived 
+ * * Neither the name of olsr.org, olsrd nor the names of its
+ *   contributors may be used to endorse or promote products derived
  *   from this software without specific prior written permission.
  *
- * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 
- * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 
- * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 
- * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 
- * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 
- * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 
- * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 
- * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 
- * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 
- * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 
- * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
+ * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
+ * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
+ * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
+ * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
+ * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
+ * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  * POSSIBILITY OF SUCH DAMAGE.
  *
  * Visit http://www.olsr.org for more information.
@@ -37,7 +38,6 @@
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: routing_table.c,v 1.36 2007/11/29 00:49:39 bernd67 Exp $
  */
 
 #include "routing_table.h"
 #include "neighbor_table.h"
 #include "olsr.h"
 #include "link_set.h"
-#include "lq_avl.h"
-#include "lq_route.h"
+#include "common/avl.h"
+#include "olsr_spf.h"
 #include "net_olsr.h"
 
 #include <assert.h>
 
+/* Cookies */
+struct olsr_cookie_info *rt_mem_cookie = NULL;
+struct olsr_cookie_info *rtp_mem_cookie = NULL;
+
+/*
+ * Sven-Ola: if the current internet gateway is switched, the
+ * NAT connection info is lost for any active TCP/UDP session.
+ * For this reason, we do not want to switch if the advantage
+ * is only minimal (cost of loosing all NATs is too high).
+ * The following rt_path keeps track of the current inet gw.
+ */
+static struct rt_path *current_inetgw = NULL;
+
+/* 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;
 
 /**
@@ -83,12 +102,12 @@ olsr_bump_routingtree_version(void)
  * -1 / +1 depending on being smaller or bigger.
  */
 int
-avl_comp_ipv4_prefix (const void *prefix1, const void *prefix2)
-{       
+avl_comp_ipv4_prefix(const void *prefix1, const void *prefix2)
+{
   const struct olsr_ip_prefix *pfx1 = prefix1;
   const struct olsr_ip_prefix *pfx2 = prefix2;
-  const olsr_u32_t addr1 = ntohl(pfx1->prefix.v4.s_addr);
-  const olsr_u32_t addr2 = ntohl(pfx2->prefix.v4.s_addr);
+  const uint32_t addr1 = ntohl(pfx1->prefix.v4.s_addr);
+  const uint32_t addr2 = ntohl(pfx2->prefix.v4.s_addr);
 
   /* prefix */
   if (addr1 < addr2) {
@@ -120,8 +139,8 @@ avl_comp_ipv4_prefix (const void *prefix1, const void *prefix2)
  * -1 / +1 depending on being smaller or bigger.
  */
 int
-avl_comp_ipv6_prefix (const void *prefix1, const void *prefix2)
-{       
+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;
@@ -130,7 +149,7 @@ avl_comp_ipv6_prefix (const void *prefix1, const void *prefix2)
   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;
@@ -148,9 +167,20 @@ avl_comp_ipv6_prefix (const void *prefix1, const void *prefix2)
 void
 olsr_init_routing_table(void)
 {
+  OLSR_PRINTF(5, "RIB: init routing tree\n");
+
   /* the routing tree */
   avl_init(&routingtree, avl_comp_prefix_default);
   routingtree_version = 0;
+
+  /*
+   * Get some cookies for memory stats and memory recycling.
+   */
+  rt_mem_cookie = olsr_alloc_cookie("rt_entry", OLSR_COOKIE_TYPE_MEMORY);
+  olsr_cookie_set_memory_size(rt_mem_cookie, sizeof(struct rt_entry));
+
+  rtp_mem_cookie = olsr_alloc_cookie("rt_path", OLSR_COOKIE_TYPE_MEMORY);
+  olsr_cookie_set_memory_size(rtp_mem_cookie, sizeof(struct rt_path));
 }
 
 /**
@@ -158,7 +188,7 @@ olsr_init_routing_table(void)
  *
  * @param dst the address of the entry
  *
- * @return a pointer to a rt_entry struct 
+ * @return a pointer to a rt_entry struct
  * representing the route entry.
  */
 struct rt_entry *
@@ -172,36 +202,27 @@ olsr_lookup_routing_table(const union olsr_ip_addr *dst)
 
   rt_tree_node = avl_find(&routingtree, &prefix);
 
-  return rt_tree_node ? rt_tree_node->data : NULL;
+  return rt_tree_node ? rt_tree2rt(rt_tree_node) : NULL;
 }
 
 /**
- * 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.cost = tc->path_cost;
 }
 
 /**
@@ -210,13 +231,13 @@ olsr_update_routing_entry(struct rt_path *rtp, union olsr_ip_addr *gateway,
 static struct rt_entry *
 olsr_alloc_rt_entry(struct olsr_ip_prefix *prefix)
 {
-  struct rt_entry *rt = olsr_malloc(sizeof(struct rt_entry), __FUNCTION__);
+  struct rt_entry *rt = olsr_cookie_malloc(rt_mem_cookie);
   if (!rt) {
     return NULL;
   }
 
   memset(rt, 0, sizeof(*rt));
-  
+
   /* Mark this entry as fresh (see process_routes.c:512) */
   rt->rt_nexthop.iif_index = -1;
 
@@ -224,7 +245,6 @@ olsr_alloc_rt_entry(struct olsr_ip_prefix *prefix)
   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 */
@@ -233,15 +253,13 @@ 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, uint8_t origin)
 {
-  struct rt_path *rtp = olsr_malloc(sizeof(struct rt_path), __FUNCTION__);
+  struct rt_path *rtp = olsr_cookie_malloc(rtp_mem_cookie);
 
   if (!rtp) {
     return NULL;
@@ -249,12 +267,71 @@ olsr_alloc_rt_path(struct rt_entry *rt,
 
   memset(rtp, 0, sizeof(*rtp));
 
-  //COPY_IP(&rtp->rtp_originator, originator);
-  rtp->rtp_originator = *originator;
+  rtp->rtp_dst = *prefix;
+
+  /* set key and backpointer prior to tree insertion */
+  rtp->rtp_prefix_tree_node.key = &rtp->rtp_dst;
+
+  /* insert to the tc prefix tree */
+  avl_insert(&tc->prefix_tree, &rtp->rtp_prefix_tree_node, AVL_DUP_NO);
+  olsr_lock_tc_entry(tc);
+
+  /* backlink to the owning tc entry */
+  rtp->rtp_tc = tc;
+
+  /* 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_cost == ROUTE_COST_BROKEN) {
+    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;
+    }
+
+  } else {
+    rt = rt_tree2rt(node);
+  }
+
+  /* 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);
@@ -262,20 +339,73 @@ olsr_alloc_rt_path(struct rt_entry *rt,
   /* backlink to the owning route entry */
   rtp->rtp_rt = rt;
 
-  return rtp;
+  /* update the version field and relevant parameters */
+  olsr_update_rt_path(rtp, tc, link);
+}
+
+/**
+ * Unlink and free a rt_path.
+ */
+void
+olsr_delete_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);
+    olsr_unlock_tc_entry(rtp->rtp_tc);
+    rtp->rtp_tc = NULL;
+  }
+
+  /* no current inet gw if the rt_path is removed */
+  if (current_inetgw == rtp) {
+    current_inetgw = NULL;
+  }
+
+  olsr_cookie_free(rtp_mem_cookie, rtp);
 }
 
 /**
  * Check if there is an interface or gateway change.
  */
-olsr_bool
+bool
 olsr_nh_change(const struct rt_nexthop *nh1, const struct rt_nexthop *nh2)
 {
-  if (!ipequal(&nh1->gateway, &nh2->gateway) ||
-      (nh1->iif_index != nh2->iif_index)) {
-    return OLSR_TRUE;
+  if (!ipequal(&nh1->gateway, &nh2->gateway) || (nh1->iif_index != nh2->iif_index)) {
+    return true;
   }
-  return OLSR_FALSE;
+  return false;
+}
+
+/**
+ * Check if there is a hopcount change.
+ */
+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.
+ */
+uint8_t
+olsr_fib_metric(const struct rt_metric * met)
+{
+  if (FIBM_CORRECT == olsr_cnf->fib_metric) {
+    return met->hops;
+  }
+  return RT_METRIC_DEFAULT;
 }
 
 /**
@@ -286,12 +416,12 @@ const struct rt_nexthop *
 olsr_get_nh(const struct rt_entry *rt)
 {
 
-  if(rt->rt_best) {
+  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;
 }
@@ -302,28 +432,38 @@ olsr_get_nh(const struct rt_entry *rt)
  * returns TRUE if the first path is better
  * than the second one, FALSE otherwise.
  */
-static olsr_bool
-olsr_cmp_rtp(const struct rt_path *rtp1, const struct rt_path *rtp2)
+static bool
+olsr_cmp_rtp(const struct rt_path *rtp1, const struct rt_path *rtp2, const struct rt_path *inetgw)
 {
-   /* etx comes first */
-    if (rtp1->rtp_metric.etx < rtp2->rtp_metric.etx) {
-      return OLSR_TRUE;
-    }
+  olsr_linkcost etx1 = rtp1->rtp_metric.cost;
+  olsr_linkcost etx2 = rtp2->rtp_metric.cost;
+  if (inetgw == rtp1)
+    etx1 *= olsr_cnf->lq_nat_thresh;
+  if (inetgw == rtp2)
+    etx2 *= olsr_cnf->lq_nat_thresh;
+
+  /* etx comes first */
+  if (etx1 < etx2) {
+    return true;
+  }
+  if (etx1 > etx2) {
+    return false;
+  }
 
-    /* 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;
-    }
+  /* hopcount is next tie breaker */
+  if (rtp1->rtp_metric.hops < rtp2->rtp_metric.hops) {
+    return true;
+  }
+  if (rtp1->rtp_metric.hops > rtp2->rtp_metric.hops) {
+    return 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;
-    }
+  /* originator (which is guaranteed to be unique) is final tie breaker */
+  if (memcmp(&rtp1->rtp_originator, &rtp2->rtp_originator, olsr_cnf->ipsize) < 0) {
+    return true;
+  }
 
-    return OLSR_FALSE;
+  return false;
 }
 
 /**
@@ -332,10 +472,10 @@ olsr_cmp_rtp(const struct rt_path *rtp1, const struct rt_path *rtp2)
  * returns TRUE if the first entry is better
  * than the second one, FALSE otherwise.
  */
-olsr_bool
-olsr_cmp_rt(const struct rt_entry *rt1, const struct rt_entry *rt2)
+bool
+olsr_cmp_rt(const struct rt_entry * rt1, const struct rt_entry * rt2)
 {
-  return olsr_cmp_rtp(rt1->rt_best, rt2->rt_best);
+  return olsr_cmp_rtp(rt1->rt_best, rt2->rt_best, NULL);
 }
 
 /**
@@ -348,111 +488,141 @@ olsr_rt_best(struct rt_entry *rt)
   /* grab the first entry */
   struct avl_node *node = avl_walk_first(&rt->rt_path_tree);
 
-  assert(node != 0); /* should not happen */
+  assert(node != 0);            /* should not happen */
 
-  rt->rt_best = node->data;
+  rt->rt_best = rtp_tree2rtp(node);
 
   /* walk all remaining originator entries */
   while ((node = avl_walk_next(node))) {
-    struct rt_path *rtp = node->data;
+    struct rt_path *rtp = rtp_tree2rtp(node);
 
-    if (olsr_cmp_rtp(rtp, rt->rt_best)) {
+    if (olsr_cmp_rtp(rtp, rt->rt_best, current_inetgw)) {
       rt->rt_best = rtp;
     }
   }
+
+  if (0 == rt->rt_dst.prefix_len) {
+    current_inetgw = rt->rt_best;
+  }
 }
 
 /**
- * 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;
+#ifdef DEBUG
+  struct ipaddr_str dstbuf, origbuf;
+#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;
   }
 
   /*
-   * No bogus prefix lengths.
+   * For all routes we use the tc_entry as an hookup point.
+   * If the tc_entry is disconnected, i.e. 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;
     }
+#ifdef DEBUG
+    OLSR_PRINTF(1, "RIB: add prefix %s/%u from %s\n", olsr_ip_to_string(&dstbuf, dst), plen,
+                olsr_ip_to_string(&origbuf, originator));
+#endif
+
+    /* overload the hna change bit for flagging a prefix change */
+    changes_hna = true;
 
   } else {
-    rt = node->data;
+    rtp = rtp_prefix_tree2rtp(node);
   }
 
+  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)
+{
+#ifdef DEBUG
+  struct ipaddr_str dstbuf, origbuf;
+#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) {
+  tc = olsr_lookup_tc_entry(originator);
+  if (!tc) {
+    return;
+  }
 
-    /* no route path from this originator yet */
-    rtp = olsr_alloc_rt_path(rt, originator);
+  /*
+   * Grab the rt_path for the prefix.
+   */
+  prefix.prefix = *dst;
+  prefix.prefix_len = plen;
 
-    if (!rtp) {
-      return NULL;
-    }
+  node = avl_find(&tc->prefix_tree, &prefix);
 
-  } else {
-    rtp = node->data;
-  }
+  if (node) {
+    rtp = rtp_prefix_tree2rtp(node);
+    olsr_delete_rt_path(rtp);
 
-  /* update the version field and relevant parameters */
-  olsr_update_routing_entry(rtp, gateway, iif_index, metric, etx);
+#ifdef DEBUG
+    OLSR_PRINTF(1, "RIB: del prefix %s/%u from %s\n", olsr_ip_to_string(&dstbuf, dst), plen,
+                olsr_ip_to_string(&origbuf, originator));
+#endif
 
-  return rtp;
+    /* overload the hna change bit for flagging a prefix change */
+    changes_hna = true;
+  }
 }
 
 /**
@@ -464,10 +634,7 @@ olsr_rt_to_string(const struct rt_entry *rt)
   static char buff[128];
   struct ipaddr_str prefixstr, gwstr;
 
-  snprintf(buff, sizeof(buff),
-           "%s/%u via %s",
-           olsr_ip_to_string(&prefixstr, &rt->rt_dst.prefix),
-           rt->rt_dst.prefix_len,
+  snprintf(buff, sizeof(buff), "%s/%u via %s", olsr_ip_to_string(&prefixstr, &rt->rt_dst.prefix), rt->rt_dst.prefix_len,
            olsr_ip_to_string(&gwstr, &rt->rt_nexthop.gateway));
 
   return buff;
@@ -482,106 +649,58 @@ olsr_rtp_to_string(const struct rt_path *rtp)
   static char buff[128];
   struct ipaddr_str prefixstr, origstr, gwstr;
   struct rt_entry *rt = rtp->rtp_rt;
+  struct lqtextbuffer lqbuffer;
 
-  snprintf(buff, sizeof(buff),
-           "%s/%u from %s via %s, "
-           "etx %.3f, metric %u, v %u",
-           olsr_ip_to_string(&prefixstr, &rt->rt_dst.prefix),
-           rt->rt_dst.prefix_len,
-           olsr_ip_to_string(&origstr, &rtp->rtp_originator),
-           olsr_ip_to_string(&gwstr, &rtp->rtp_nexthop.gateway),
-           rtp->rtp_metric.etx,
-           rtp->rtp_metric.hops,
-           rtp->rtp_version);
+  snprintf(buff, sizeof(buff), "%s/%u from %s via %s, " "cost %s, metric %u, v %u",
+           olsr_ip_to_string(&prefixstr, &rt->rt_dst.prefix), rt->rt_dst.prefix_len, olsr_ip_to_string(&origstr,
+                                                                                                       &rtp->rtp_originator),
+           olsr_ip_to_string(&gwstr, &rtp->rtp_nexthop.gateway), get_linkcost_text(rtp->rtp_metric.cost, true, &lqbuffer),
+           rtp->rtp_metric.hops, rtp->rtp_version);
 
   return buff;
 }
 
-/**
- *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
  *
  */
 void
-olsr_print_routing_table(const struct avl_tree *tree)
+olsr_print_routing_table(struct avl_tree *tree)
 {
-  const struct avl_node *rt_tree_node;
+#ifndef NODEBUG
+  /* The whole function makes no sense without it. */
+  struct avl_node *rt_tree_node;
+  struct lqtextbuffer lqbuffer;
 
-#ifdef DEBUG
-  printf("ROUTING TABLE\n");
-#endif
+  OLSR_PRINTF(6, "ROUTING TABLE\n");
 
-  for (rt_tree_node = avl_walk_first_c(tree);
-       rt_tree_node != NULL;
-       rt_tree_node = avl_walk_next_c(rt_tree_node)) {
-    const struct avl_node *rtp_tree_node;
+  for (rt_tree_node = avl_walk_first(tree); rt_tree_node != NULL; rt_tree_node = avl_walk_next(rt_tree_node)) {
+    struct avl_node *rtp_tree_node;
     struct ipaddr_str prefixstr, origstr, gwstr;
-    const struct rt_entry * const rt = rt_tree_node->data;
+    struct rt_entry *rt = rt_tree2rt(rt_tree_node);
 
     /* first the route entry */
-    printf("%s/%u, via %s, best-originator %s\n",
-           olsr_ip_to_string(&prefixstr, &rt->rt_dst.prefix),
-           rt->rt_dst.prefix_len,
-           olsr_ip_to_string(&origstr, &rt->rt_nexthop.gateway),
-           olsr_ip_to_string(&gwstr, &rt->rt_best->rtp_originator));
+    OLSR_PRINTF(6, "%s/%u, via %s, best-originator %s\n", olsr_ip_to_string(&prefixstr, &rt->rt_dst.prefix), rt->rt_dst.prefix_len,
+                olsr_ip_to_string(&origstr, &rt->rt_nexthop.gateway), olsr_ip_to_string(&gwstr, &rt->rt_best->rtp_originator));
 
     /* walk the per-originator path tree of routes */
-    for (rtp_tree_node = avl_walk_first_c(&rt->rt_path_tree);
-         rtp_tree_node != NULL;
-         rtp_tree_node = avl_walk_next_c(rtp_tree_node)) {
-      const struct rt_path * const rtp = rtp_tree_node->data;
-      printf("\tfrom %s, etx %.3f, metric %u, via %s, %s, v %u\n",
-             olsr_ip_to_string(&origstr, &rtp->rtp_originator),
-             rtp->rtp_metric.etx,
-             rtp->rtp_metric.hops,
-             olsr_ip_to_string(&gwstr, &rtp->rtp_nexthop.gateway),
-             if_ifwithindex_name(rt->rt_nexthop.iif_index),
-             rtp->rtp_version);    
+    for (rtp_tree_node = avl_walk_first(&rt->rt_path_tree); rtp_tree_node != NULL; rtp_tree_node = avl_walk_next(rtp_tree_node)) {
+      struct rt_path *rtp = rtp_tree2rtp(rtp_tree_node);
+      OLSR_PRINTF(6, "\tfrom %s, cost %s, metric %u, via %s, %s, v %u\n", olsr_ip_to_string(&origstr, &rtp->rtp_originator),
+                  get_linkcost_text(rtp->rtp_metric.cost, true, &lqbuffer), rtp->rtp_metric.hops, olsr_ip_to_string(&gwstr,
+                                                                                                                    &rtp->
+                                                                                                                    rtp_nexthop.
+                                                                                                                    gateway),
+                  if_ifwithindex_name(rt->rt_nexthop.iif_index), rtp->rtp_version);
     }
   }
+#endif
+  tree = NULL;                  /* squelch compiler warnings */
 }
 
 /*
  * Local Variables:
  * c-basic-offset: 2
+ * indent-tabs-mode: nil
  * End:
  */