move avl and list library into src/common
[olsrd.git] / src / routing_table.h
index 1558d1c..f22d757 100644 (file)
  * to the project. For more information see the website or contact
  * the copyright holders.
  *
- * $Id: routing_table.h,v 1.23 2007/10/16 09:54:43 bernd67 Exp $
  */
 
 #ifndef _OLSR_ROUTING_TABLE
 #define _OLSR_ROUTING_TABLE
 
+#include <sys/types.h>
+#include <sys/time.h>
+#include <sys/socket.h>
+#include <net/if.h>
 #include <net/route.h>
 #include "hna_set.h"
-#include "lq_avl.h"
-#include "lq_list.h"
+#include "link_set.h"
+#include "common/avl.h"
+#include "common/list.h"
 
 #define NETMASK_HOST 0xffffffff
 #define NETMASK_DEFAULT 0x0
@@ -60,7 +64,7 @@
 /* a composite metric is used for path selection */
 struct rt_metric
 {
-  float                 etx;
+  olsr_linkcost       cost;
   olsr_u32_t           hops;
 };
 
@@ -84,6 +88,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 +97,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 +149,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
  */
@@ -144,30 +197,31 @@ union olsr_kernel_route
 extern struct avl_tree routingtree;
 extern unsigned int routingtree_version;
 
-int
+void
 olsr_init_routing_table(void);
 
 unsigned int olsr_bump_routingtree_version(void);
 
-int avl_comp_ipv4_prefix (void *, void *);
-int avl_comp_ipv6_prefix (void *, void *);
+int avl_comp_ipv4_prefix (const void *, const void *);
+int avl_comp_ipv6_prefix (const void *, const void *);
 
 void olsr_rt_best(struct rt_entry *);
-olsr_bool olsr_nh_change(struct rt_nexthop *, struct rt_nexthop *);
-olsr_bool olsr_cmp_rt(struct rt_entry *, struct rt_entry *);
+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(struct rt_entry *);
-char *olsr_rtp_to_string(struct rt_path *);
-void olsr_print_routing_table(struct avl_tree *);
+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 *);