Merge branch 'pud' into stable
[olsrd.git] / src / routing_table.c
index 302756c..749b479 100644 (file)
+
 /*
- * OLSR ad-hoc routing table management protocol
- * Copyright (C) 2004 Andreas T√łnnesen (andreto@ifi.uio.no)
+ * The olsr.org Optimized Link-State Routing daemon(olsrd)
+ * 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
+ * are met:
  *
- * This file is part of the olsr.org OLSR daemon.
+ * * 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
+ *   distribution.
+ * * 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.
  *
- * olsr.org is free software; you can redistribute it and/or modify
- * it under the terms of the GNU General Public License as published by
- * the Free Software Foundation; either version 2 of the License, or
- * (at your option) any later version.
+ * 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.
  *
- * olsr.org is distributed in the hope that it will be useful,
- * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
- * GNU General Public License for more details.
+ * Visit http://www.olsr.org for more information.
  *
- * You should have received a copy of the GNU General Public License
- * along with olsr.org; if not, write to the Free Software
- * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ * If you find this software useful feel free to make a donation
+ * to the project. For more information see the website or contact
+ * the copyright holders.
  *
  */
 
-
-
+#include "routing_table.h"
+#include "ipcalc.h"
 #include "defs.h"
 #include "two_hop_neighbor_table.h"
 #include "tc_set.h"
 #include "mid_set.h"
-#include "mpr.h"
+#include "neighbor_table.h"
 #include "olsr.h"
 #include "link_set.h"
+#include "common/avl.h"
+#include "olsr_spf.h"
+#include "net_olsr.h"
 
+#include <assert.h>
 
-/* Begin:
- * Prototypes for internal functions 
- */
-
-static void
-olsr_free_routing_table(struct rt_entry *);
-
-static int
-olsr_fill_routing_table_with_neighbors();
+/* Cookies */
+struct olsr_cookie_info *rt_mem_cookie = NULL;
+struct olsr_cookie_info *rtp_mem_cookie = NULL;
 
-static struct destination_n *
-olsr_fill_routing_table_with_two_hop_neighbors();
+/*
+ * 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;
 
-static struct rt_entry *
-olsr_check_for_higher_hopcount(struct rt_entry *, struct hna_net *, olsr_u16_t);
+/* Root of our RIB */
+struct avl_tree routingtree;
 
-static struct rt_entry *
-olsr_lookup_routing_table(union olsr_ip_addr *);
+/*
+ * Keep a version number for detecting outdated elements
+ * in the per rt_entry rt_path subtree.
+ */
+unsigned int routingtree_version;
 
-/* End:
- * 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++;
+}
 
+/**
+ * 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(const void *prefix1, const void *prefix2)
+{
+  const struct olsr_ip_prefix *pfx1 = prefix1;
+  const struct olsr_ip_prefix *pfx2 = prefix2;
+  const uint32_t addr1 = ntohl(pfx1->prefix.v4.s_addr);
+  const uint32_t addr2 = ntohl(pfx2->prefix.v4.s_addr);
+
+  /* prefix */
+  if (addr1 < addr2) {
+    return -1;
+  }
+  if (addr1 > addr2) {
+    return +1;
+  }
+
+  /* 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
+ * 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
-olsr_init_routing_table()
+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 */
+  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 routingtree and kernel change queues.
+ */
+void
+olsr_init_routing_table(void)
 {
-  int index;
+  OLSR_PRINTF(5, "RIB: init routing tree\n");
+
+  /* the routing tree */
+  avl_init(&routingtree, avl_comp_prefix_default);
+  routingtree_version = 0;
 
   /*
-   *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
+   * Get some cookies for memory stats and memory recycling.
    */
-  for(index=0;index<HASHSIZE;index++)
-    {
-      routingtable[index].next = &routingtable[index];
-      routingtable[index].prev = &routingtable[index];
-      hna_routes[index].next = &hna_routes[index];
-      hna_routes[index].prev = &hna_routes[index];
-    }
-  return 1;
+  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));
 }
 
 /**
- *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.
  */
-static struct rt_entry *
-olsr_lookup_routing_table(union olsr_ip_addr *dst)
+struct rt_entry *
+olsr_lookup_routing_table(const 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;
+  prefix.prefix = *dst;
+  prefix.prefix_len = olsr_cnf->maxplen;
 
-  hash = olsr_hashing(dst);
+  rt_tree_node = avl_find(&routingtree, &prefix);
 
-  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);
-  
+  return rt_tree_node ? rt_tree2rt(rt_tree_node) : NULL;
 }
 
+/**
+ * Update gateway/interface/etx/hopcount and the version for a route path.
+ */
+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 = link->neighbor_iface_addr;
 
+  /* interface */
+  rtp->rtp_nexthop.iif_index = link->inter->if_index;
+
+  /* metric/etx */
+  rtp->rtp_metric.hops = tc->hops;
+  rtp->rtp_metric.cost = tc->path_cost;
+}
 
 /**
- *Delete all the entries in the routing table hash
- *
- *@param table the routing hash table
- *
- *@return nada
+ * Alloc and key a new rt_entry.
  */
-static void
-olsr_free_routing_table(struct rt_entry *table)
+static struct rt_entry *
+olsr_alloc_rt_entry(struct olsr_ip_prefix *prefix)
 {
-  struct rt_entry *destination;
-  struct rt_entry *dst_to_delete;
-  olsr_u8_t       index;
-  
+  struct rt_entry *rt = olsr_cookie_malloc(rt_mem_cookie);
+  if (!rt) {
+    return NULL;
+  }
 
-  for(index=0;index<HASHSIZE;index++)
-    {
-      destination = table[index].next;
+  memset(rt, 0, sizeof(*rt));
 
-      while(destination != &table[index])
-       {
-         dst_to_delete = destination;
-         destination = destination->next;
+  /* Mark this entry as fresh (see process_routes.c:512) */
+  rt->rt_nexthop.iif_index = -1;
 
-         dst_to_delete->next->prev = dst_to_delete->prev;
-         dst_to_delete->prev->next = dst_to_delete->next;
+  /* set key and backpointer prior to tree insertion */
+  rt->rt_dst = *prefix;
 
-         free(dst_to_delete);
-       }
-    }
+  rt->rt_tree_node.key = &rt->rt_dst;
+  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, union olsr_ip_addr *router, int metric)
+static struct rt_path *
+olsr_alloc_rt_path(struct tc_entry *tc, struct olsr_ip_prefix *prefix, uint8_t origin)
 {
-  struct rt_entry *new_route_entry, *rt_list;
-  olsr_u32_t       hash;
-
-  hash = olsr_hashing(dst);
-  rt_list = &routingtable[hash];
-
-  new_route_entry = olsr_malloc(sizeof(struct rt_entry), "Insert routing table");
-
-  COPY_IP(&new_route_entry->rt_dst, dst);
-  COPY_IP(&new_route_entry->rt_router, router);
-
-  new_route_entry->rt_metric = metric;
-  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(ipversion == AF_INET)
-    /* IPv4 */
-    new_route_entry->rt_mask.v4 = NETMASK_HOST;
-  else
-    /* IPv6 */
-    new_route_entry->rt_mask.v6 = 128;
-
-  /* Find interface */
-  if((new_route_entry->rt_if = get_interface_link_set(router)) == NULL)
-    {
-      fprintf(stderr, "ADD ROUTE 1: %s Could not find neighbor interface ", 
-             olsr_ip_to_string(dst));
-      fprintf(stderr, "for %s!!\n", 
-             olsr_ip_to_string(router));
-      free(new_route_entry);
-      return NULL;
-    }
-  
-
-  /* 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);
-}
+  struct rt_path *rtp = olsr_cookie_malloc(rtp_mem_cookie);
 
+  if (!rtp) {
+    return NULL;
+  }
 
+  memset(rtp, 0, sizeof(*rtp));
 
-/**
- *Insert all the one hop neighbors in the routing table.
- *
- *@return a pointer to a destination_n linked-list of the neighbors.
- */
-static int
-olsr_fill_routing_table_with_neighbors()
-{
-  olsr_u8_t              index;
-  struct neighbor_entry  *neighbor;
-  struct rt_entry        *new_route_entry=NULL;
+  rtp->rtp_dst = *prefix;
 
-  struct addresses *addrs=NULL, *addrs2;
+  /* set key and backpointer prior to tree insertion */
+  rtp->rtp_prefix_tree_node.key = &rtp->rtp_dst;
 
-#ifdef DEBUG
-  olsr_printf(7, "FILL ROUTING TABLE WITH NEIGHBORS\n");
-#endif
+  /* insert to the tc prefix tree */
+  avl_insert(&tc->prefix_tree, &rtp->rtp_prefix_tree_node, AVL_DUP_NO);
+  olsr_lock_tc_entry(tc);
 
-  for(index=0;index<HASHSIZE;index++)
-    {
-      for(neighbor = neighbortable[index].next;
-         neighbor != &neighbortable[index];
-         neighbor=neighbor->next)     
-       {
-
-         if(neighbor->status == SYM)
-           {
-             /*
-              *Insert all the neighbors addresses
-              */
-             addrs = olsr_malloc(sizeof(struct addresses), "Fill routing table with neighbors");
-
-             COPY_IP(&addrs->address, &neighbor->neighbor_main_addr);
-             addrs->next = mid_lookup_aliases(&neighbor->neighbor_main_addr);
-             addrs2 = addrs;
-
-             while(addrs!=NULL)
-               {
-#ifdef DEBUG
-                 olsr_printf(7, "(ROUTE)Adding neighbor %s\n", olsr_ip_to_string(&addrs->address));
-#endif
-                 /* New in 0.4.6 */
-                 new_route_entry = olsr_insert_routing_table(&addrs->address, get_neighbor_nexthop(&addrs->address), 1);
-             
-                 addrs = addrs->next;
-               }
-             free(addrs2);
-           }
-       }
-    }
+  /* backlink to the owning tc entry */
+  rtp->rtp_tc = tc;
 
+  /* store the origin of the route */
+  rtp->rtp_origin = origin;
 
-  return 1;
+  return rtp;
 }
 
-
 /**
- *Insert all the two hop neighbors that is not already added
- *in the routing table.
- *
- *@return a pointer to a destination_n linked-list of the neighbors.
+ * Create a route entry for a given rt_path and
+ * insert it into the global RIB tree.
  */
-
-static struct destination_n *
-olsr_fill_routing_table_with_two_hop_neighbors()
+void
+olsr_insert_rt_path(struct rt_path *rtp, struct tc_entry *tc, struct link_entry *link)
 {
-  struct destination_n         *list_destination_n=NULL;
-  struct destination_n         *list_destination_tmp=NULL;
-  olsr_u8_t                    index;
-  struct neighbor_entry        *neighbor;
-  struct rt_entry              *new_route_entry=NULL;
-  struct neighbor_2_list_entry *neigh_2_list; 
-  union olsr_ip_addr           *n2_addr;
-  struct addresses *addrs=NULL, *addrs2;
-  struct neighbor_list_entry   *neighbors;
-  int                          neighbor_ok;
-
-  //printf("FILL ROUTING TABLE WITH TWO HOP NEIGHBORS\n");
-
-  for(index=0;index<HASHSIZE;index++)
-    {
-      for(neighbor = neighbortable[index].next;
-         neighbor != &neighbortable[index];
-         neighbor=neighbor->next)     
-       {
-         
-         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)
-           {
-             
-             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;
-               }           
-
-             /*
-              * Neighbor is only added if avalible trough
-              * a 1 hop neighbor with willingness != WILL_NEVER
-              */
-             neighbor_ok = 0;
-
-             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))
-                   neighbor_ok = 1;
-               }
-
-             if(!neighbor_ok)
-               {
-                 olsr_printf(1, "Two hop neighbor %s not added - no one hop neighbors.\n",
-                             olsr_ip_to_string(n2_addr));
-                 continue;
-               }
-
-             addrs = olsr_malloc(sizeof(struct addresses), "Fill rt table 2 hop neighbors");
-             
-             COPY_IP(&addrs->address, n2_addr);
-             addrs->next = mid_lookup_aliases(n2_addr);
-             addrs2 = addrs;
-
-             while(addrs!=NULL)
-               {
-#ifdef DEBUG
-                 olsr_printf(7, "(ROUTE)Adding neighbor %s\n", olsr_ip_to_string(&addrs->address));
-#endif
-                 /* New in 0.4.6 */
-                 new_route_entry = olsr_insert_routing_table(&addrs->address, get_neighbor_nexthop(&neighbor->neighbor_main_addr), 2);
-
-                 if(new_route_entry != NULL)
-                   {
-                     list_destination_tmp = olsr_malloc(sizeof(struct destination_n), "Fill rt table 2 hop tmp");
-                     
-                     list_destination_tmp->destination = new_route_entry;
-                     list_destination_tmp->next = list_destination_n;
-                     list_destination_n = list_destination_tmp;
-                   }
-                 addrs = addrs->next; 
-               }
-             free(addrs2);
-           }
-       }
+  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;
     }
 
-  return(list_destination_n);
-}
+  } 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;
 
+  /* 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;
+
+  /* update the version field and relevant parameters */
+  olsr_update_rt_path(rtp, tc, link);
+}
 
 /**
- *Recalculate the routing table
- *
- *@return nada
+ * Unlink and free a rt_path.
  */
-void 
-olsr_calculate_routing_table()
-
+void
+olsr_delete_rt_path(struct rt_path *rtp)
 {
-  struct destination_n               *list_destination_n=NULL;
-  struct destination_n               *list_destination_n_1=NULL;
-  struct destination_n               *destination_n_1=NULL;
-  //struct topology_last_entry         *topo_last;
-  struct tc_entry                    *topo_entry;
-  struct topo_dst                    *topo_dest;
-  struct addresses                   *tmp_addrs, *tmp2_addrs;
-  int                                add_dest;
-
-  olsr_move_route_table(routingtable, old_routes);
-
-
-  /* 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();
-
-  /* List_destination_n_1 holds the "outer rim" */
-  list_destination_n = list_destination_n_1;
-
-  while(list_destination_n_1!=NULL)
-    {
-      list_destination_n_1=NULL;
-
-      /* Next "outer rim" */
-      while(list_destination_n!=NULL)
-       {
-         if((topo_entry = olsr_lookup_tc_entry(&list_destination_n->destination->rt_dst)) != NULL)
-           {
-             topo_dest = topo_entry->destinations.next;
-
-             /* Loop trough this nodes MPR selectors */
-             while(topo_dest != &topo_entry->destinations)
-               {
-                 /* Check if dest is ourselves!! */
-                 add_dest = 1;
-                 
-                 /* Do not add ourselves */
-                 if(if_ifwithaddr(&topo_dest->T_dest_addr))
-                   {
-                     topo_dest=topo_dest->next;
-                     continue;
-                   }
-                 
-                 /* Find mid nodes */
-                 tmp_addrs = olsr_malloc(sizeof(struct addresses), "Calculate routing table MID");
-                 
-                 COPY_IP(&tmp_addrs->address, &topo_dest->T_dest_addr);
-                 tmp_addrs->next = mid_lookup_aliases(&topo_dest->T_dest_addr);
-                 tmp2_addrs = tmp_addrs;
-                 
-                 while(tmp_addrs!=NULL)
-                   {
-                     if(NULL==olsr_lookup_routing_table(&tmp_addrs->address))
-                       {
-                         /* 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_addrs->address) );
-                         
-                         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_addrs->address, 
-                                                     &list_destination_n->destination->rt_router, 
-                                                     list_destination_n->destination->rt_metric+1);
-                         if(destination_n_1->destination != NULL)
-                           {
-                             destination_n_1->next=list_destination_n_1;
-                             list_destination_n_1=destination_n_1;
-                           }
-                       }
-                     tmp_addrs = tmp_addrs->next;
-                   }
-                 free(tmp2_addrs);
-                 
-                 /* 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);
-         
-       }
-
-      /* New "outer rim" */
-      list_destination_n=list_destination_n_1;
-    }
 
+  /* 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);
+}
 
-  if(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");
-    }
+/**
+ * Check if there is an interface or gateway change.
+ */
+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 true;
+  }
+  return false;
+}
 
-  
-  /* Update routes */
-  olsr_update_kernel_routes();
+/**
+ * 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);
+}
 
-  olsr_free_routing_table(old_routes);
+/**
+ * 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;
 }
 
+/**
+ * depending on the operation (add/chg/del) the nexthop
+ * field from the route entry or best route path shall be used.
+ */
+const struct rt_nexthop *
+olsr_get_nh(const struct rt_entry *rt)
+{
+
+  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 for a entry with a higher hopcount than
- *a given value in a routing table
+ * compare two route paths.
  *
- *@param routes the routingtable to look in
- *@param net the network entry to look for
- *@param metric the metric to check for
- *
- *@return the localted entry if found. NULL if not
+ * returns TRUE if the first path is better
+ * than the second one, FALSE otherwise.
  */
-static struct rt_entry *
-olsr_check_for_higher_hopcount(struct rt_entry *routes, struct hna_net *net, olsr_u16_t metric)
+static bool
+olsr_cmp_rtp(const struct rt_path *rtp1, const struct rt_path *rtp2, const struct rt_path *inetgw)
 {
-  int index;
-  struct rt_entry *tmp_routes;
-
-  for(index=0;index<HASHSIZE;index++)
-    {
-      /* All entries */
-      for(tmp_routes = routes[index].next;
-         tmp_routes != &routes[index];
-         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 a entry */
-             if(tmp_routes->rt_metric > metric)
-               return tmp_routes;
-             else
-               return NULL;
-           }
-       }
-    }
+  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.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 (memcmp(&rtp1->rtp_originator, &rtp2->rtp_originator, olsr_cnf->ipsize) < 0) {
+    return true;
+  }
+
+  return false;
+}
 
-  return NULL;
+/**
+ * compare the best path of two route entries.
+ *
+ * returns TRUE if the first entry is better
+ * than the second one, FALSE otherwise.
+ */
+bool
+olsr_cmp_rt(const struct rt_entry * rt1, const struct rt_entry * rt2)
+{
+  return olsr_cmp_rtp(rt1->rt_best, rt2->rt_best, NULL);
 }
 
+/**
+ * run best route selection among a
+ * set of identical prefixes.
+ */
+void
+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 */
+
+  rt->rt_best = rtp_tree2rtp(node);
 
+  /* walk all remaining originator entries */
+  while ((node = avl_walk_next(node))) {
+    struct rt_path *rtp = rtp_tree2rtp(node);
+
+    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;
+  }
+}
 
 /**
- *Check for a entry with a lower or equal hopcount than
- *a given value in a routing table
+ * Insert a prefix into the prefix tree hanging off a lsdb (tc) entry.
+ *
+ * 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 routes the routingtable to look in
- *@param net the network entry to look for
- *@param metric the metric to check for
+ *@param dst the destination
+ *@param plen the prefix length
+ *@param originator the originating router
  *
- *@return the localted entry if found. NULL if not
+ *@return the new rt_path struct
  */
-struct rt_entry *
-olsr_check_for_lower_hopcount(struct rt_entry *routes, struct hna_net *net, olsr_u16_t metric)
+struct rt_path *
+olsr_insert_routing_table(union olsr_ip_addr *dst, int plen, union olsr_ip_addr *originator, int origin)
 {
-  int index;
-  struct rt_entry *tmp_routes;
-
-  for(index=0;index<HASHSIZE;index++)
-    {
-      /* All entries */
-      for(tmp_routes = routes[index].next;
-         tmp_routes != &routes[index];
-         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 a entry */
-             if(tmp_routes->rt_metric <= metric)
-               return tmp_routes;
-             else
-               return NULL;
-           }
-       }
-    }
+#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 bogus prefix lengths.
+   */
+  if (plen > olsr_cnf->maxplen) {
+    return NULL;
+  }
 
+  /*
+   * 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.
+   */
+  tc = olsr_locate_tc_entry(originator);
 
-  return NULL;
-}
+  /*
+   * first check if there is a rt_path for the prefix.
+   */
+  prefix.prefix = *dst;
+  prefix.prefix_len = plen;
 
+  node = avl_find(&tc->prefix_tree, &prefix);
 
+  if (!node) {
+
+    /* no rt_path for this prefix yet */
+    rtp = olsr_alloc_rt_path(tc, &prefix, origin);
+
+    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 {
+    rtp = rtp_prefix_tree2rtp(node);
+  }
+
+  return rtp;
+}
 
 /**
- *Calculate the HNA routes
- *
+ * Delete a prefix from the prefix tree hanging off a lsdb (tc) entry.
  */
 void
-olsr_calculate_hna_routes()
+olsr_delete_routing_table(union olsr_ip_addr *dst, int plen, union olsr_ip_addr *originator)
 {
-  olsr_u32_t index, hna_hash;
-  struct hna_entry *tmp_hna;
-  struct hna_net *tmp_net;
-  struct rt_entry *tmp_rt, *new_rt;
-
 #ifdef DEBUG
-  olsr_printf(3, "Calculating HNA routes\n");
+  struct ipaddr_str dstbuf, origbuf;
 #endif
 
-  olsr_move_route_table(hna_routes, old_hna);
-
-  
-  for(index=0;index<HASHSIZE;index++)
-    {
-      /* All entries */
-      for(tmp_hna = hna_set[index].next;
-         tmp_hna != &hna_set[index];
-         tmp_hna = tmp_hna->next)
-       {
-
-         /* All networks */
-         for(tmp_net = tmp_hna->networks.next;
-             tmp_net != &tmp_hna->networks;
-             tmp_net = tmp_net->next)
-           {
-             //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_lower_hopcount(hna_routes, tmp_net, tmp_rt->rt_metric) != NULL)
-               {
-                 continue;
-               }
-
-             /* If we find an entry with higher hopcount we just edit it */
-             if((new_rt = olsr_check_for_higher_hopcount(hna_routes, tmp_net, tmp_rt->rt_metric)) != NULL)
-               {
-                 /* Fill struct */
-                 /* Net */
-                 COPY_IP(&new_rt->rt_dst, &tmp_net->A_network_addr);
-                 memcpy(&new_rt->rt_mask, &tmp_net->A_netmask, netmask_size);
-                 /* Gateway */
-                 COPY_IP(&new_rt->rt_router, &tmp_rt->rt_router);
-                 /* Metric */
-                 new_rt->rt_metric = tmp_rt->rt_metric;
-                 /* Flags */
-                 new_rt->rt_flags = RTF_UP | RTF_GATEWAY;
-
-               }
-             /* If not - create a new one */
-             else
-               {
-                 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);
-                 memcpy(&new_rt->rt_mask, &tmp_net->A_netmask, netmask_size);
-                 /* Gateway */
-                 COPY_IP(&new_rt->rt_router, &tmp_rt->rt_router);
-                 /* Metric */
-                 new_rt->rt_metric = tmp_rt->rt_metric;
-                 /* Flags */
-                 new_rt->rt_flags = RTF_UP | RTF_GATEWAY;
-             
-                 /* Find interface */
-                 if((new_rt->rt_if = get_interface_link_set(&new_rt->rt_router)) == NULL)
-                   {
-                     fprintf(stderr, "ADD ROUTE 2: %s Could not find neighbor interface!!!\n", 
-                             olsr_ip_to_string(&new_rt->rt_dst));
-                     /* This hopefullt never happens */
-                     free(new_rt);
-                   }
-                 else
-                   {
-                     /* 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 tc_entry *tc;
+  struct rt_path *rtp;
+  struct avl_node *node;
+  struct olsr_ip_prefix prefix;
 
-  /* Update kernel */
-  olsr_update_kernel_hna_routes();
+  /*
+   * No bogus prefix lengths.
+   */
+  if (plen > olsr_cnf->maxplen) {
+    return;
+  }
 
-  if(debug_level > 2)
-    {
-      olsr_printf(3, "HNA table:\n");
-      olsr_print_routing_table(hna_routes);
-    }
+  tc = olsr_lookup_tc_entry(originator);
+  if (!tc) {
+    return;
+  }
 
-  olsr_free_routing_table(old_hna);
+  /*
+   * Grab the rt_path for the prefix.
+   */
+  prefix.prefix = *dst;
+  prefix.prefix_len = plen;
 
+  node = avl_find(&tc->prefix_tree, &prefix);
+
+  if (node) {
+    rtp = rtp_prefix_tree2rtp(node);
+    olsr_delete_rt_path(rtp);
+
+#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
+
+    /* overload the hna change bit for flagging a prefix change */
+    changes_hna = true;
+  }
 }
 
+/**
+ * format a route entry into a buffer
+ */
+char *
+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,
+           olsr_ip_to_string(&gwstr, &rt->rt_nexthop.gateway));
 
+  return buff;
+}
 
+/**
+ * format a route path into a buffer
+ */
+char *
+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, " "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;
+}
 
 /**
- *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)
 {
-
-  struct rt_entry     *destination;
-  olsr_u8_t           index;
-
-  printf("ROUTING TABLE\n");
-  printf("DESTINATION\tNEXT HOP\n");
-  for(index=0;index<HASHSIZE;index++)
-    {
-      for(destination = table[index].next;
-         destination != &table[index];
-         destination = destination->next)
-       {
-         printf("%s\t", olsr_ip_to_string(&destination->rt_dst));
-         printf("%s\n", olsr_ip_to_string(&destination->rt_router));
-       }
+#ifndef NODEBUG
+  /* The whole function makes no sense without it. */
+  struct avl_node *rt_tree_node;
+  struct lqtextbuffer lqbuffer;
+
+  OLSR_PRINTF(6, "ROUTING TABLE\n");
+
+  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;
+    struct rt_entry *rt = rt_tree2rt(rt_tree_node);
+
+    /* first the route entry */
+    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(&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);
     }
-  fflush(stdout);
+  }
+#endif
+  tree = NULL;                  /* squelch compiler warnings */
 }
 
-
-
-
-
+/*
+ * Local Variables:
+ * c-basic-offset: 2
+ * indent-tabs-mode: nil
+ * End:
+ */