src/routing_table.h

   1 /*
   2  * The olsr.org Optimized Link-State Routing daemon(olsrd)
   3  * Copyright (c) 2004, Andreas Tønnesen(andreto@olsr.org)
   4  * RIB implementation (c) 2007, Hannes Gredler (hannes@gredler.at)
   5  * All rights reserved.
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  *
  11  * * Redistributions of source code must retain the above copyright
  12  *   notice, this list of conditions and the following disclaimer.
  13  * * Redistributions in binary form must reproduce the above copyright
  14  *   notice, this list of conditions and the following disclaimer in
  15  *   the documentation and/or other materials provided with the
  16  *   distribution.
  17  * * Neither the name of olsr.org, olsrd nor the names of its
  18  *   contributors may be used to endorse or promote products derived
  19  *   from this software without specific prior written permission.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  22  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  25  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  26  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
  27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  28  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  29  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  31  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  32  * POSSIBILITY OF SUCH DAMAGE.
  33  *
  34  * Visit http://www.olsr.org for more information.
  35  *
  36  * If you find this software useful feel free to make a donation
  37  * to the project. For more information see the website or contact
  38  * the copyright holders.
  39  *
  40  * $Id: routing_table.h,v 1.25 2007/11/11 23:10:24 bernd67 Exp $
  41  */
  42
  43 #ifndef _OLSR_ROUTING_TABLE
  44 #define _OLSR_ROUTING_TABLE
  45
  46 #include <net/route.h>
  47 #include "hna_set.h"
  48 #include "lq_avl.h"
  49 #include "lq_list.h"
  50
  51 #define NETMASK_HOST 0xffffffff
  52 #define NETMASK_DEFAULT 0x0
  53
  54 /*
  55  * the kernel FIB does not need to know the metric of a route.
  56  * this saves us from enqueuing/dequeueing hopcount only changes.
  57  */
  58 #define RT_METRIC_DEFAULT 2
  59
  60 /* a composite metric is used for path selection */
  61 struct rt_metric
  62 {
  63   float                 etx;
  64   olsr_u32_t            hops;
  65 };
  66
  67 /* a nexthop is a pointer to a gateway router plus an interface */
  68 struct rt_nexthop
  69 {
  70   union olsr_ip_addr    gateway; /* gateway router */
  71   int                   iif_index; /* outgoing interface index */
  72 };
  73
  74 /*
  75  * Every prefix in our RIB needs a route entry that contains
  76  * the nexthop of the best path as installed in the kernel FIB.
  77  * The route entry is the root of a rt_path tree of equal prefixes
  78  * originated by different routers. It also contains a shortcut
  79  * for accessing the best route among all contributing routes.
  80  */
  81 struct rt_entry
  82 {
  83   struct olsr_ip_prefix rt_dst;
  84   struct avl_node       rt_tree_node;
  85   struct rt_path        *rt_best; /* shortcut to the best path */
  86   struct rt_nexthop     rt_nexthop; /* nexthop of FIB route */
  87   struct avl_tree       rt_path_tree;
  88   struct list_node      rt_change_node; /* queue for kernel FIB add/chg/del */
  89 };
  90
  91 /*
  92  * For every received route a rt_path is added to the RIB.
  93  * Depending on the results of the SPF calculation we perform a
  94  * best_path calculation and pick the one with the lowest etx/metric.
  95  */
  96 struct rt_path
  97 {
  98   struct rt_entry       *rtp_rt; /* backpointer to owning route head */
  99   struct rt_nexthop     rtp_nexthop;
 100   struct rt_metric      rtp_metric;
 101   union olsr_ip_addr    rtp_originator; /* originator of the route */
 102   struct avl_node       rtp_tree_node;
 103   olsr_u32_t            rtp_version;
 104 };
 105
 106 /*
 107  * macro for traversing the entire routing table.
 108  * it is recommended to use this because it hides all the internal
 109  * datastructure from the callers.
 110  *
 111  * the loop prefetches the next node in order to not loose context if
 112  * for example the caller wants to delete the current rt_entry.
 113  */
 114 #define OLSR_FOR_ALL_RT_ENTRIES(rt) \
 115 { \
 116   struct avl_node *rt_tree_node, *next_rt_tree_node; \
 117   for (rt_tree_node = avl_walk_first(&routingtree); \
 118     rt_tree_node; rt_tree_node = next_rt_tree_node) { \
 119     next_rt_tree_node = avl_walk_next(rt_tree_node); \
 120     rt = rt_tree_node->data;
 121 #define OLSR_FOR_ALL_RT_ENTRIES_END(rt) }}
 122
 123 /**
 124  * IPv4 <-> IPv6 wrapper
 125  */
 126 union olsr_kernel_route
 127 {
 128   struct
 129   {
 130     struct sockaddr rt_dst;
 131     struct sockaddr rt_gateway;
 132     olsr_u32_t metric;
 133   } v4;
 134
 135   struct
 136   {
 137     struct in6_addr rtmsg_dst;
 138     struct in6_addr rtmsg_gateway;
 139     olsr_u32_t rtmsg_metric;
 140   } v6;
 141 };
 142
 143
 144 extern struct avl_tree routingtree;
 145 extern unsigned int routingtree_version;
 146
 147 void
 148 olsr_init_routing_table(void);
 149
 150 unsigned int olsr_bump_routingtree_version(void);
 151
 152 int avl_comp_ipv4_prefix (const void *, const void *);
 153 int avl_comp_ipv6_prefix (const void *, const void *);
 154
 155 void olsr_rt_best(struct rt_entry *);
 156 olsr_bool olsr_nh_change(const struct rt_nexthop *, const struct rt_nexthop *);
 157 olsr_bool olsr_cmp_rt(const struct rt_entry *, const struct rt_entry *);
 158
 159 void olsr_calculate_hna_routes(void);
 160 char *olsr_rt_to_string(const struct rt_entry *);
 161 char *olsr_rtp_to_string(const struct rt_path *);
 162 void olsr_print_routing_table(const struct avl_tree *);
 163
 164 const struct rt_nexthop * olsr_get_nh(const struct rt_entry *);
 165
 166 struct rt_path *
 167 olsr_insert_routing_table(union olsr_ip_addr *, int,
 168                           union olsr_ip_addr *,
 169                           union olsr_ip_addr *,
 170                           int, int, float);
 171
 172 struct rt_entry *
 173 olsr_lookup_routing_table(const union olsr_ip_addr *);
 174
 175
 176 #endif
 177
 178 /*
 179  * Local Variables:
 180  * c-basic-offset: 2
 181  * End:
 182  */