1 /* 2 * The olsr.org Optimized Link-State Routing daemon (olsrd) 3 * 4 * (c) by the OLSR project 5 * 6 * See our Git repository to find out who worked on this file 7 * and thus is a copyright holder on it. 8 * 9 * All rights reserved. 10 * 11 * Redistribution and use in source and binary forms, with or without 12 * modification, are permitted provided that the following conditions 13 * are met: 14 * 15 * * Redistributions of source code must retain the above copyright 16 * notice, this list of conditions and the following disclaimer. 17 * * Redistributions in binary form must reproduce the above copyright 18 * notice, this list of conditions and the following disclaimer in 19 * the documentation and/or other materials provided with the 20 * distribution. 21 * * Neither the name of olsr.org, olsrd nor the names of its 22 * contributors may be used to endorse or promote products derived 23 * from this software without specific prior written permission. 24 * 25 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 26 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 27 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 28 * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 29 * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 30 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 31 * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 32 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 33 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 34 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 35 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 36 * POSSIBILITY OF SUCH DAMAGE. 37 * 38 * Visit http://www.olsr.org for more information. 39 * 40 * If you find this software useful feel free to make a donation 41 * to the project. For more information see the website or contact 42 * the copyright holders. 43 * 44 */ 45 46 #ifndef _OLSR_ROUTING_TABLE 47 #define _OLSR_ROUTING_TABLE 48 49 #include <sys/types.h> 50 #include <sys/time.h> 51 #include <sys/socket.h> 52 #include <net/if.h> 53 #include <net/route.h> 54 #include "hna_set.h" 55 #include "link_set.h" 56 #include "olsr_cookie.h" 57 #include "common/avl.h" 58 #include "common/list.h" 59 60 #define NETMASK_HOST 0xffffffff 61 #define NETMASK_DEFAULT 0x0 62 63 /* a composite metric is used for path selection */ 64 struct rt_metric { 65 olsr_linkcost cost; 66 uint32_t hops; 67 }; 68 69 /* a nexthop is a pointer to a gateway router plus an interface */ 70 struct rt_nexthop { 71 union olsr_ip_addr gateway; /* gateway router */ 72 int iif_index; /* outgoing interface index */ 73 }; 74 75 /* 76 * Every prefix in our RIB needs a route entry that contains 77 * the nexthop of the best path as installed in the kernel FIB. 78 * The route entry is the root of a rt_path tree of equal prefixes 79 * originated by different routers. It also contains a shortcut 80 * for accessing the best route among all contributing routes. 81 */ 82 struct rt_entry { 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 rt_metric rt_metric; /* metric of FIB route */ 88 struct avl_tree rt_path_tree; 89 struct list_node rt_change_node; /* queue for kernel FIB add/chg/del */ 90 }; 91 92 AVLNODE2STRUCT(rt_tree2rt, struct rt_entry, rt_tree_node); 93 LISTNODE2STRUCT(changelist2rt, struct rt_entry, rt_change_node); 94 95 /* 96 * For every received route a rt_path is added to the RIB. 97 * Depending on the results of the SPF calculation we perform a 98 * best_path calculation and pick the one with the lowest etx/metric. 99 * The rt_path gets first inserted into the per tc_entry prefix tree. 100 * If during the SPF calculation the tc_entry becomes reachable via 101 * a local nexthop it is inserted into the global RIB tree. 102 */ 103 struct rt_path { 104 struct rt_entry *rtp_rt; /* backpointer to owning route head */ 105 struct tc_entry *rtp_tc; /* backpointer to owning tc entry */ 106 struct rt_nexthop rtp_nexthop; 107 struct rt_metric rtp_metric; 108 struct avl_node rtp_tree_node; /* global rtp node */ 109 union olsr_ip_addr rtp_originator; /* originator of the route */ 110 struct avl_node rtp_prefix_tree_node; /* tc entry rtp node */ 111 struct olsr_ip_prefix rtp_dst; /* the prefix */ 112 uint32_t rtp_version; /* for detection of outdated rt_paths */ 113 uint8_t rtp_origin; /* internal, MID or HNA */ 114 }; 115 116 AVLNODE2STRUCT(rtp_tree2rtp, struct rt_path, rtp_tree_node); 117 AVLNODE2STRUCT(rtp_prefix_tree2rtp, struct rt_path, rtp_prefix_tree_node); 118 119 /* 120 * In olsrd we have three different route types. 121 * Internal routes are generated by simple reachability 122 * of a node (by means of a tc message reception). 123 * MID routes result from MID messages and HNA routes 124 * from a gw routers HNA anncouncements. 125 */ 126 enum olsr_rt_origin { 127 OLSR_RT_ORIGIN_MIN, 128 OLSR_RT_ORIGIN_INT, 129 OLSR_RT_ORIGIN_MID, 130 OLSR_RT_ORIGIN_HNA, 131 OLSR_RT_ORIGIN_MAX 132 }; 133 134 /* 135 * OLSR_FOR_ALL_RT_ENTRIES 136 * 137 * macro for traversing the entire routing table. 138 * it is recommended to use this because it hides all the internal 139 * datastructure from the callers. 140 * 141 * the loop prefetches the next node in order to not loose context if 142 * for example the caller wants to delete the current rt_entry. 143 */ 144 #define OLSR_FOR_ALL_RT_ENTRIES(rt) \ 145 { \ 146 struct avl_node *rt_tree_node, *next_rt_tree_node; \ 147 for (rt_tree_node = avl_walk_first(&routingtree); \ 148 rt_tree_node; rt_tree_node = next_rt_tree_node) { \ 149 next_rt_tree_node = avl_walk_next(rt_tree_node); \ 150 rt = rt_tree2rt(rt_tree_node); 151 #define OLSR_FOR_ALL_RT_ENTRIES_END(rt) }} 152 153 /* 154 * OLSR_FOR_ALL_HNA_RT_ENTRIES 155 * 156 * macro for traversing the entire routing table and pick only 157 * HNA routes. This is not optimal - however, If the RIBs become 158 * too big one day then we keep an additional per origin tree 159 * in order to speed up traversal. 160 * In the meantime it is recommended to use this macro because 161 * it hides all the internal datastructure from the callers 162 * and the core maintainers do not have to update all the plugins 163 * once we decide to change the datastructures. 164 */ 165 #define OLSR_FOR_ALL_HNA_RT_ENTRIES(rt) \ 166 { \ 167 struct avl_node *rt_tree_node, *next_rt_tree_node; \ 168 for (rt_tree_node = avl_walk_first(&routingtree); \ 169 rt_tree_node; rt_tree_node = next_rt_tree_node) { \ 170 next_rt_tree_node = avl_walk_next(rt_tree_node); \ 171 rt = rt_tree2rt(rt_tree_node); \ 172 if (rt->rt_best->rtp_origin != OLSR_RT_ORIGIN_HNA) \ 173 continue; 174 #define OLSR_FOR_ALL_HNA_RT_ENTRIES_END(rt) }} 175 176 /** 177 * IPv4 <-> IPv6 wrapper 178 */ 179 union olsr_kernel_route { 180 struct { 181 struct sockaddr rt_dst; 182 struct sockaddr rt_gateway; 183 uint32_t metric; 184 } v4; 185 186 struct { 187 struct in6_addr rtmsg_dst; 188 struct in6_addr rtmsg_gateway; 189 uint32_t rtmsg_metric; 190 } v6; 191 }; 192 193 extern struct avl_tree routingtree; 194 extern unsigned int routingtree_version; 195 extern struct olsr_cookie_info *rt_mem_cookie; 196 197 void olsr_init_routing_table(void); 198 199 unsigned int olsr_bump_routingtree_version(void); 200 201 int avl_comp_ipv4_prefix(const void *, const void *); 202 int avl_comp_ipv6_prefix(const void *, const void *); 203 204 void olsr_rt_best(struct rt_entry *); 205 bool olsr_nh_change(const struct rt_nexthop *, const struct rt_nexthop *); 206 bool olsr_hopcount_change(const struct rt_metric *, const struct rt_metric *); 207 bool olsr_cmp_rt(const struct rt_entry *, const struct rt_entry *); 208 uint8_t olsr_fib_metric(const struct rt_metric *); 209 210 char *olsr_rt_to_string(const struct rt_entry *); 211 char *olsr_rtp_to_string(const struct rt_path *); 212 #ifndef NODEBUG 213 void olsr_print_routing_table(struct avl_tree *); 214 #else 215 #define olsr_print_routing_table(x) do { } while(0) 216 #endif 217 218 const struct rt_nexthop *olsr_get_nh(const struct rt_entry *); 219 220 /* rt_path manipulation */ 221 struct rt_path *olsr_insert_routing_table(union olsr_ip_addr *, int, union olsr_ip_addr *, int); 222 void olsr_delete_routing_table(union olsr_ip_addr *, int, union olsr_ip_addr *); 223 void olsr_insert_rt_path(struct rt_path *, struct tc_entry *, struct link_entry *); 224 void olsr_update_rt_path(struct rt_path *, struct tc_entry *, struct link_entry *); 225 void olsr_delete_rt_path(struct rt_path *); 226 227 struct rt_entry *olsr_lookup_routing_table(const union olsr_ip_addr *); 228 229 #endif /* _OLSR_ROUTING_TABLE */ 230 231 /* 232 * Local Variables: 233 * c-basic-offset: 2 234 * indent-tabs-mode: nil 235 * End: 236 */ 237