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