Support for FIB metric configuration, other than 2
[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 /* a composite metric is used for path selection */
61 struct rt_metric {
62   olsr_linkcost cost;
63   uint32_t hops;
64 };
65
66 /* a nexthop is a pointer to a gateway router plus an interface */
67 struct rt_nexthop {
68   union olsr_ip_addr gateway;          /* gateway router */
69   int iif_index;                       /* outgoing interface index */
70 };
71
72 /*
73  * Every prefix in our RIB needs a route entry that contains
74  * the nexthop of the best path as installed in the kernel FIB.
75  * The route entry is the root of a rt_path tree of equal prefixes
76  * originated by different routers. It also contains a shortcut
77  * for accessing the best route among all contributing routes.
78  */
79 struct rt_entry {
80   struct olsr_ip_prefix rt_dst;
81   struct avl_node rt_tree_node;
82   struct rt_path *rt_best;             /* shortcut to the best path */
83   struct rt_nexthop rt_nexthop;        /* nexthop of FIB route */
84   struct rt_metric rt_metric;          /* metric of FIB route */
85   struct avl_tree rt_path_tree;
86   struct list_node rt_change_node;     /* queue for kernel FIB add/chg/del */
87 };
88
89 AVLNODE2STRUCT(rt_tree2rt, struct rt_entry, rt_tree_node);
90 LISTNODE2STRUCT(changelist2rt, struct rt_entry, rt_change_node);
91
92 /*
93  * For every received route a rt_path is added to the RIB.
94  * Depending on the results of the SPF calculation we perform a
95  * best_path calculation and pick the one with the lowest etx/metric.
96  * The rt_path gets first inserted into the per tc_entry prefix tree.
97  * If during the SPF calculation the tc_entry becomes reachable via
98  * a local nexthop it is inserted into the global RIB tree.
99  */
100 struct rt_path {
101   struct rt_entry *rtp_rt;             /* backpointer to owning route head */
102   struct tc_entry *rtp_tc;             /* backpointer to owning tc entry */
103   struct rt_nexthop rtp_nexthop;
104   struct rt_metric rtp_metric;
105   struct avl_node rtp_tree_node;       /* global rtp node */
106   union olsr_ip_addr rtp_originator;   /* originator of the route */
107   struct avl_node rtp_prefix_tree_node; /* tc entry rtp node */
108   struct olsr_ip_prefix rtp_dst;       /* the prefix */
109   uint32_t rtp_version;                /* for detection of outdated rt_paths */
110   uint8_t rtp_origin;                  /* internal, MID or HNA */
111 };
112
113 AVLNODE2STRUCT(rtp_tree2rtp, struct rt_path, rtp_tree_node);
114 AVLNODE2STRUCT(rtp_prefix_tree2rtp, struct rt_path, rtp_prefix_tree_node);
115
116 /*
117  * In olsrd we have three different route types.
118  * Internal routes are generated by simple reachability
119  * of a node (by means of a tc message reception).
120  * MID routes result from MID messages and HNA routes
121  * from a gw routers HNA anncouncements.
122  */
123 enum olsr_rt_origin {
124   OLSR_RT_ORIGIN_MIN,
125   OLSR_RT_ORIGIN_INT,
126   OLSR_RT_ORIGIN_MID,
127   OLSR_RT_ORIGIN_HNA,
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) \
142 { \
143   struct avl_node *rt_tree_node, *next_rt_tree_node; \
144   for (rt_tree_node = avl_walk_first(&routingtree); \
145     rt_tree_node; rt_tree_node = next_rt_tree_node) { \
146     next_rt_tree_node = avl_walk_next(rt_tree_node); \
147     rt = rt_tree2rt(rt_tree_node);
148 #define OLSR_FOR_ALL_RT_ENTRIES_END(rt) }}
149
150 /*
151  * OLSR_FOR_ALL_HNA_RT_ENTRIES
152  *
153  * macro for traversing the entire routing table and pick only
154  * HNA routes. This is not optimal - however, If the RIBs become
155  * too big one day then we keep an additional per origin tree
156  * in order to speed up traversal.
157  * In the meantime it is recommended to use this macro because
158  * it hides all the internal datastructure from the callers
159  * and the core maintainers do not have to update all the plugins
160  * once we decide to change the datastructures.
161  */
162 #define OLSR_FOR_ALL_HNA_RT_ENTRIES(rt) \
163 { \
164   struct avl_node *rt_tree_node, *next_rt_tree_node; \
165   for (rt_tree_node = avl_walk_first(&routingtree); \
166     rt_tree_node; rt_tree_node = next_rt_tree_node) { \
167     next_rt_tree_node = avl_walk_next(rt_tree_node); \
168     rt = rt_tree2rt(rt_tree_node); \
169     if (rt->rt_best->rtp_origin != OLSR_RT_ORIGIN_HNA) \
170       continue;
171 #define OLSR_FOR_ALL_HNA_RT_ENTRIES_END(rt) }}
172
173 /**
174  * IPv4 <-> IPv6 wrapper
175  */
176 union olsr_kernel_route {
177   struct {
178     struct sockaddr rt_dst;
179     struct sockaddr rt_gateway;
180     uint32_t metric;
181   } v4;
182
183   struct {
184     struct in6_addr rtmsg_dst;
185     struct in6_addr rtmsg_gateway;
186     uint32_t rtmsg_metric;
187   } v6;
188 };
189
190 extern struct avl_tree routingtree;
191 extern unsigned int routingtree_version;
192 extern struct olsr_cookie_info *rt_mem_cookie;
193
194 void olsr_init_routing_table(void);
195
196 unsigned int olsr_bump_routingtree_version(void);
197
198 int avl_comp_ipv4_prefix(const void *, const void *);
199 int avl_comp_ipv6_prefix(const void *, const void *);
200
201 void olsr_rt_best(struct rt_entry *);
202 bool olsr_nh_change(const struct rt_nexthop *, const struct rt_nexthop *);
203 bool olsr_hopcount_change(const struct rt_metric *, const struct rt_metric *);
204 bool olsr_cmp_rt(const struct rt_entry *, const struct rt_entry *);
205 uint8_t olsr_fib_metric(const struct rt_metric *);
206
207 char *olsr_rt_to_string(const struct rt_entry *);
208 char *olsr_rtp_to_string(const struct rt_path *);
209 #ifndef NODEBUG
210 void olsr_print_routing_table(struct avl_tree *);
211 #else
212 #define olsr_print_routing_table(x) do { } while(0)
213 #endif
214
215 const struct rt_nexthop *olsr_get_nh(const struct rt_entry *);
216
217 /* rt_path manipulation */
218 struct rt_path *olsr_insert_routing_table(union olsr_ip_addr *, int, union olsr_ip_addr *, int);
219 void olsr_delete_routing_table(union olsr_ip_addr *, int, union olsr_ip_addr *);
220 void olsr_insert_rt_path(struct rt_path *, struct tc_entry *, struct link_entry *);
221 void olsr_update_rt_path(struct rt_path *, struct tc_entry *, struct link_entry *);
222 void olsr_delete_rt_path(struct rt_path *);
223
224 struct rt_entry *olsr_lookup_routing_table(const union olsr_ip_addr *);
225
226 #endif /* _OLSR_ROUTING_TABLE */
227
228 /*
229  * Local Variables:
230  * c-basic-offset: 2
231  * indent-tabs-mode: nil
232  * End:
233  */