ea20b0b63ddf0d827c45d1d4cf5677d441a186f9
[olsrd.git] / src / routing_table.h
1 /*
2  * The olsr.org Optimized Link-State Routing daemon(olsrd)
3  * Copyright (c) 2004, Andreas Tonnesen(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  */
41
42 #ifndef _OLSR_ROUTING_TABLE
43 #define _OLSR_ROUTING_TABLE
44
45 #include <sys/types.h>
46 #include <sys/time.h>
47 #include <sys/socket.h>
48 #include <net/if.h>
49 #include <net/route.h>
50 #include "hna_set.h"
51 #include "link_set.h"
52 #include "olsr_cookie.h"
53 #include "common/avl.h"
54 #include "common/list.h"
55
56 #define NETMASK_HOST 0xffffffff
57 #define NETMASK_DEFAULT 0x0
58
59 /*
60  * the kernel FIB does not need to know the metric of a route.
61  * this saves us from enqueuing/dequeueing hopcount only changes.
62  */
63 #define RT_METRIC_DEFAULT 2
64
65 /* a composite metric is used for path selection */
66 struct rt_metric
67 {
68   olsr_linkcost       cost;
69   olsr_u32_t            hops;
70 };
71
72 /* a nexthop is a pointer to a gateway router plus an interface */
73 struct rt_nexthop
74 {
75   union olsr_ip_addr    gateway; /* gateway router */
76   int                   iif_index; /* outgoing interface index */
77 };
78
79 /*
80  * Every prefix in our RIB needs a route entry that contains
81  * the nexthop of the best path as installed in the kernel FIB.
82  * The route entry is the root of a rt_path tree of equal prefixes
83  * originated by different routers. It also contains a shortcut
84  * for accessing the best route among all contributing routes.
85  */
86 struct rt_entry
87 {
88   struct olsr_ip_prefix rt_dst;
89   struct avl_node       rt_tree_node; 
90   struct rt_path        *rt_best; /* shortcut to the best path */
91   struct rt_nexthop     rt_nexthop; /* nexthop of FIB route */
92   struct rt_metric      rt_metric; /* metric of FIB route */
93   struct avl_tree       rt_path_tree;
94   struct list_node      rt_change_node; /* queue for kernel FIB add/chg/del */
95 };
96
97 AVLNODE2STRUCT(rt_tree2rt, struct rt_entry, rt_tree_node);
98 LISTNODE2STRUCT(changelist2rt, struct rt_entry, rt_change_node);
99
100 /*
101  * For every received route a rt_path is added to the RIB.
102  * Depending on the results of the SPF calculation we perform a
103  * best_path calculation and pick the one with the lowest etx/metric.
104  * The rt_path gets first inserted into the per tc_entry prefix tree.
105  * If during the SPF calculation the tc_entry becomes reachable via
106  * a local nexthop it is inserted into the global RIB tree.
107  */
108 struct rt_path
109 {
110   struct rt_entry       *rtp_rt; /* backpointer to owning route head */
111   struct tc_entry       *rtp_tc; /* backpointer to owning tc entry */
112   struct rt_nexthop     rtp_nexthop;
113   struct rt_metric      rtp_metric;
114   struct avl_node       rtp_tree_node; /* global rtp node */
115   union olsr_ip_addr    rtp_originator; /* originator of the route */
116   struct avl_node       rtp_prefix_tree_node; /* tc entry rtp node */
117   struct olsr_ip_prefix rtp_dst; /* the prefix */
118   olsr_u32_t            rtp_version; /* for detection of outdated rt_paths */
119   olsr_u8_t             rtp_origin; /* internal, MID or HNA */
120 };
121
122 AVLNODE2STRUCT(rtp_tree2rtp, struct rt_path, rtp_tree_node);
123 AVLNODE2STRUCT(rtp_prefix_tree2rtp, struct rt_path, rtp_prefix_tree_node);
124
125 /*
126  * In olsrd we have three different route types.
127  * Internal routes are generated by simple reachability
128  * of a node (by means of a tc message reception).
129  * MID routes result from MID messages and HNA routes
130  * from a gw routers HNA anncouncements.
131  */
132 enum olsr_rt_origin {
133   OLSR_RT_ORIGIN_MIN,
134   OLSR_RT_ORIGIN_INT,
135   OLSR_RT_ORIGIN_MID,
136   OLSR_RT_ORIGIN_HNA,
137   OLSR_RT_ORIGIN_MAX
138 };
139
140 /*
141  * OLSR_FOR_ALL_RT_ENTRIES
142  *
143  * macro for traversing the entire routing table.
144  * it is recommended to use this because it hides all the internal
145  * datastructure from the callers.
146  *
147  * the loop prefetches the next node in order to not loose context if
148  * for example the caller wants to delete the current rt_entry.
149  */
150 #define OLSR_FOR_ALL_RT_ENTRIES(rt) \
151 { \
152   struct avl_node *rt_tree_node, *next_rt_tree_node; \
153   for (rt_tree_node = avl_walk_first(&routingtree); \
154     rt_tree_node; rt_tree_node = next_rt_tree_node) { \
155     next_rt_tree_node = avl_walk_next(rt_tree_node); \
156     rt = rt_tree2rt(rt_tree_node);
157 #define OLSR_FOR_ALL_RT_ENTRIES_END(rt) }}
158
159 /*
160  * OLSR_FOR_ALL_HNA_RT_ENTRIES
161  *
162  * macro for traversing the entire routing table and pick only
163  * HNA routes. This is not optimal - however, If the RIBs become
164  * too big one day then we keep an additional per origin tree
165  * in order to speed up traversal.
166  * In the meantime it is recommended to use this macro because
167  * it hides all the internal datastructure from the callers
168  * and the core maintainers do not have to update all the plugins
169  * once we decide to change the datastructures.
170  */
171 #define OLSR_FOR_ALL_HNA_RT_ENTRIES(rt) \
172 { \
173   struct avl_node *rt_tree_node, *next_rt_tree_node; \
174   for (rt_tree_node = avl_walk_first(&routingtree); \
175     rt_tree_node; rt_tree_node = next_rt_tree_node) { \
176     next_rt_tree_node = avl_walk_next(rt_tree_node); \
177     rt = rt_tree2rt(rt_tree_node); \
178     if (rt->rt_best->rtp_origin != OLSR_RT_ORIGIN_HNA) \
179       continue; 
180 #define OLSR_FOR_ALL_HNA_RT_ENTRIES_END(rt) }}
181
182
183 /**
184  * IPv4 <-> IPv6 wrapper
185  */
186 union olsr_kernel_route
187 {
188   struct
189   {
190     struct sockaddr rt_dst;
191     struct sockaddr rt_gateway;
192     olsr_u32_t metric;
193   } v4;
194
195   struct
196   {
197     struct in6_addr rtmsg_dst;
198     struct in6_addr rtmsg_gateway;
199     olsr_u32_t rtmsg_metric;
200   } v6;
201 };
202
203
204 extern struct avl_tree routingtree;
205 extern unsigned int routingtree_version;
206 extern struct olsr_cookie_info *rt_mem_cookie;
207
208 void
209 olsr_init_routing_table(void);
210
211 /**
212  * Bump the version number of the routing tree.
213  *
214  * After route-insertion compare the version number of the routes
215  * against the version number of the table.
216  * This is a lightweight detection if a node or prefix went away,
217  * rather than brute force old vs. new rt_entry comparision.
218  */
219 static INLINE void olsr_bump_routingtree_version(void) { routingtree_version++; }
220
221
222 int avl_comp_ipv4_prefix (const void *, const void *);
223 int avl_comp_ipv6_prefix (const void *, const void *);
224
225 void olsr_rt_best(struct rt_entry *);
226 /**
227  * Check if there is an interface or gateway change.
228  */
229 static INLINE olsr_bool olsr_nh_change(const struct rt_nexthop *nh1, const struct rt_nexthop *nh2) {
230     return !ipequal(&nh1->gateway, &nh2->gateway) || nh1->iif_index != nh2->iif_index;
231 }
232
233 /**
234  * Check if there is a hopcount change.
235  */
236 static INLINE olsr_bool olsr_hopcount_change(const struct rt_metric *met1, const struct rt_metric *met2) { return met1->hops != met2->hops; }
237
238 olsr_bool olsr_cmp_rt(const struct rt_entry *, const struct rt_entry *);
239
240 #if defined WIN32 || (defined linux && !LINUX_POLICY_ROUTING)
241 /**
242  * Depending if flat_metric is configured and the kernel fib operation
243  * return the hopcount metric of a route.
244  * For adds this is the metric of best rour after olsr_rt_best() election,
245  * for deletes this is the metric of the route that got stored in the rt_entry,
246  * during route installation.
247  */
248 static INLINE olsr_u8_t olsr_fib_metric(const struct rt_metric *met) {
249   return  FIBM_CORRECT == olsr_cnf->fib_metric ? met->hops : RT_METRIC_DEFAULT;
250 }
251 #endif
252
253 char *olsr_rt_to_string(const struct rt_entry *);
254 char *olsr_rtp_to_string(const struct rt_path *);
255 void olsr_print_routing_table(struct avl_tree *);
256
257 /**
258  * depending on the operation (add/chg/del) the nexthop
259  * field from the route entry or best route path shall be used.
260  */
261 static INLINE const struct rt_nexthop *olsr_get_nh(const struct rt_entry *rt) {
262   return rt->rt_best != NULL
263     /* this is a route add/chg - grab nexthop from the best route. */
264     ? &rt->rt_best->rtp_nexthop
265     /* this is a route deletion - all routes are gone. */
266     : &rt->rt_nexthop;
267 }
268
269
270 /* rt_path manipulation */
271 struct rt_path *olsr_insert_routing_table(const union olsr_ip_addr *, const int,
272                                           const union olsr_ip_addr *, const int);
273 void olsr_delete_routing_table(union olsr_ip_addr *, int, union olsr_ip_addr *);
274 void olsr_insert_rt_path(struct rt_path *, struct tc_entry *, struct link_entry *);
275 void olsr_update_rt_path(struct rt_path *, struct tc_entry *, struct link_entry *);
276 void olsr_delete_rt_path(struct rt_path *);
277
278 struct rt_entry *
279 olsr_lookup_routing_table(const union olsr_ip_addr *);
280
281
282 #endif
283
284 /*
285  * Local Variables:
286  * c-basic-offset: 2
287  * indent-tabs-mode: nil
288  * End:
289  */