Update to new avl/list iteration macros
[olsrd.git] / src / routing_table.h
1
2 /*
3  * The olsr.org Optimized Link-State Routing daemon(olsrd)
4  * Copyright (c) 2004-2009, the olsr.org team - see HISTORY file
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/socket.h>
47 #include <net/if.h>
48 #include <net/route.h>
49 #include "hna_set.h"
50 #include "link_set.h"
51 #include "olsr_cookie.h"
52 #include "common/avl.h"
53 #include "common/list.h"
54
55 #define NETMASK_HOST 0xffffffff
56 #define NETMASK_DEFAULT 0x0
57
58 /*
59  * the kernel FIB does not need to know the metric of a route.
60  * this saves us from enqueuing/dequeueing hopcount only changes.
61  */
62 #define RT_METRIC_DEFAULT 2
63
64 /* a composite metric is used for path selection */
65 struct rt_metric {
66   olsr_linkcost cost;
67   uint32_t hops;
68 };
69
70 /* a nexthop is a pointer to a gateway router plus an interface */
71 struct rt_nexthop {
72   union olsr_ip_addr gateway;          /* gateway router */
73   struct interface *interface;         /* outgoing interface */
74 };
75
76 /*
77  * Every prefix in our RIB needs a route entry that contains
78  * the nexthop of the best path as installed in the kernel FIB.
79  * The route entry is the root of a rt_path tree of equal prefixes
80  * originated by different routers. It also contains a shortcut
81  * for accessing the best route among all contributing routes.
82  */
83 struct rt_entry {
84   struct olsr_ip_prefix rt_dst;
85   struct avl_node rt_tree_node;
86   struct rt_path *rt_best;             /* shortcut to the best path */
87   struct rt_nexthop rt_nexthop;        /* nexthop of FIB route */
88   struct rt_metric rt_metric;          /* metric of FIB route */
89   struct avl_tree rt_path_tree;
90   struct list_entity rt_change_node;     /* queue for kernel FIB add/chg/del */
91   int failure_count;
92 };
93
94 #define OLSR_FOR_ALL_RTLIST_ENTRIES(head, rt_entry, iterator) list_for_each_element_safe(head, rt_entry, rt_change_node, iterator)
95
96 /*
97  * For every received route a rt_path is added to the RIB.
98  * Depending on the results of the SPF calculation we perform a
99  * best_path calculation and pick the one with the lowest etx/metric.
100  * The rt_path gets first inserted into the per tc_entry prefix tree.
101  * If during the SPF calculation the tc_entry becomes reachable via
102  * a local nexthop it is inserted into the global RIB tree.
103  */
104 struct rt_path {
105   struct rt_entry *rtp_rt;             /* backpointer to owning route head */
106   struct tc_entry *rtp_tc;             /* backpointer to owning tc entry */
107   struct rt_nexthop rtp_nexthop;
108   struct rt_metric rtp_metric;
109   struct avl_node rtp_tree_node;       /* global rtp node */
110   struct olsr_ip_prefix rtp_originator; /* originator of the route */
111   struct avl_node rtp_prefix_tree_node; /* tc entry rtp node */
112   struct olsr_ip_prefix rtp_dst;       /* the prefix */
113   uint32_t rtp_version;                /* for detection of outdated rt_paths */
114 };
115
116 #define OLSR_FOR_ALL_RT_PATH_ENTRIES(rt, rtp, iterator) avl_for_each_element_safe(&rt->rt_path_tree, rtp, rtp_tree_node, iterator)
117
118 /*
119  * Different routes types used in olsrd.
120  * Used to track which component did install a route.
121  */
122 enum olsr_rt_origin {
123   OLSR_RT_ORIGIN_MIN,
124   OLSR_RT_ORIGIN_TC,                   /* TC main-addr route */
125   OLSR_RT_ORIGIN_MID,                  /* MID alias route */
126   OLSR_RT_ORIGIN_HNA,                  /* HNA route */
127   OLSR_RT_ORIGIN_LINK,                 /* 1-hop LINK route */
128   OLSR_RT_ORIGIN_MAX
129 };
130
131 /*
132  * OLSR_FOR_ALL_RT_ENTRIES
133  *
134  * macro for traversing the entire routing table.
135  * it is recommended to use this because it hides all the internal
136  * datastructure from the callers.
137  *
138  * the loop prefetches the next node in order to not loose context if
139  * for example the caller wants to delete the current rt_entry.
140  */
141 #define OLSR_FOR_ALL_RT_ENTRIES(rt, iterator) avl_for_each_element_safe(&routingtree, rt, rt_tree_node, iterator)
142
143 /**
144  * IPv4 <-> IPv6 wrapper
145  */
146 union olsr_kernel_route {
147   struct {
148     struct sockaddr rt_dst;
149     struct sockaddr rt_gateway;
150     uint32_t metric;
151   } v4;
152
153   struct {
154     struct in6_addr rtmsg_dst;
155     struct in6_addr rtmsg_gateway;
156     uint32_t rtmsg_metric;
157   } v6;
158 };
159
160 extern struct avl_tree EXPORT(routingtree);
161 extern unsigned int routingtree_version;
162 extern struct olsr_cookie_info *rt_mem_cookie;
163
164 void olsr_init_routing_table(void);
165
166 /**
167  * Bump the version number of the routing tree.
168  *
169  * After route-insertion compare the version number of the routes
170  * against the version number of the table.
171  * This is a lightweight detection if a node or prefix went away,
172  * rather than brute force old vs. new rt_entry comparision.
173  */
174 static INLINE void
175 olsr_bump_routingtree_version(void)
176 {
177   routingtree_version++;
178 }
179
180
181 void olsr_rt_best(struct rt_entry *);
182
183 /**
184  * Check if there is an interface or gateway change.
185  */
186 static INLINE bool
187 olsr_nh_change(const struct rt_nexthop *nh1, const struct rt_nexthop *nh2)
188 {
189   return olsr_ipcmp(&nh1->gateway, &nh2->gateway) != 0 || nh1->interface != nh2->interface;
190 }
191
192 /**
193  * Check if there is a hopcount change.
194  */
195 static INLINE bool
196 olsr_hopcount_change(const struct rt_metric *met1, const struct rt_metric *met2)
197 {
198   return met1->hops != met2->hops;
199 }
200
201 bool EXPORT(olsr_cmp_rt) (const struct rt_entry *, const struct rt_entry *);
202
203 #if defined WIN32
204
205 /**
206  * Depending if flat_metric is configured and the kernel fib operation
207  * return the hopcount metric of a route.
208  * For adds this is the metric of best rour after olsr_rt_best() election,
209  * for deletes this is the metric of the route that got stored in the rt_entry,
210  * during route installation.
211  */
212 static INLINE uint8_t
213 olsr_fib_metric(const struct rt_metric *met)
214 {
215   return FIBM_CORRECT == olsr_cnf->fib_metric ? met->hops : RT_METRIC_DEFAULT;
216 }
217 #endif
218
219 char *olsr_rt_to_string(const struct rt_entry *);
220 char *olsr_rtp_to_string(const struct rt_path *);
221 void olsr_print_routing_table(void);
222
223 /**
224  * depending on the operation (add/chg/del) the nexthop
225  * field from the route entry or best route path shall be used.
226  */
227 static INLINE const struct rt_nexthop *
228 olsr_get_nh(const struct rt_entry *rt)
229 {
230   return rt->rt_best != NULL
231     /* this is a route add/chg - grab nexthop from the best route. */
232     ? &rt->rt_best->rtp_nexthop
233     /* this is a route deletion - all routes are gone. */
234     : &rt->rt_nexthop;
235 }
236
237
238 /* rt_path manipulation */
239 struct rt_path *olsr_insert_routing_table(const union olsr_ip_addr *, const int, const union olsr_ip_addr *, const int);
240 void olsr_delete_routing_table(union olsr_ip_addr *, int, union olsr_ip_addr *, int);
241 void olsr_insert_rt_path(struct rt_path *, struct tc_entry *, struct link_entry *);
242 void olsr_update_rt_path(struct rt_path *, struct tc_entry *, struct link_entry *);
243 void olsr_delete_rt_path(struct rt_path *);
244
245 struct rt_entry *EXPORT(olsr_lookup_routing_table) (const union olsr_ip_addr *);
246
247
248 #endif
249
250 /*
251  * Local Variables:
252  * c-basic-offset: 2
253  * indent-tabs-mode: nil
254  * End:
255  */