* applied rt-refactoring-6.diff from Hannes Gredler <hannes@gredler.at>
[olsrd.git] / src / routing_table.h
1 /*
2  * The olsr.org Optimized Link-State Routing daemon(olsrd)
3  * Copyright (c) 2004, Andreas T√łnnesen(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  * $Id: routing_table.h,v 1.19 2007/09/05 16:11:11 bernd67 Exp $
41  */
42
43 #ifndef _OLSR_ROUTING_TABLE
44 #define _OLSR_ROUTING_TABLE
45
46 #include <net/route.h>
47 #include "hna_set.h"
48 #include "lq_avl.h"
49 #include "lq_list.h"
50
51 #define NETMASK_HOST 0xffffffff
52 #define NETMASK_DEFAULT 0x0
53
54 /*
55  * the kernel FIB does not need to know the metric of a route.
56  * this saves us from enqueuing/dequeueing hopcount only changes.
57  */
58 #define RT_METRIC_DEFAULT 2
59
60 /* a composite metric is used for path selection */
61 struct rt_metric
62 {
63   float                 etx;
64   olsr_u32_t            hops;
65 };
66
67 /* a nexthop is a pointer to a gateway router plus an interface */
68 struct rt_nexthop
69 {
70   union olsr_ip_addr    gateway; /* gateway router */
71   struct interface      *iface; /* outgoing interface */
72 };
73
74 /*
75  * Every prefix in our RIB needs a route entry that contains
76  * the nexthop of the best path as installed in the kernel FIB.
77  * The route entry is the root of a rt_path tree of equal prefixes
78  * originated by different routers. It also contains a shortcut
79  * for accessing the best route among all contributing routes.
80  */
81 struct rt_entry
82 {
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 avl_tree       rt_path_tree;
88   struct list_node      rt_change_node; /* queue for kernel FIB add/chg/del */
89 };
90
91 /*
92  * For every received route a rt_path is added to the RIB.
93  * Depending on the results of the SPF calculation we perform a
94  * best_path calculation and pick the one with the lowest etx/metric.
95  */
96 struct rt_path
97 {
98   struct rt_entry       *rtp_rt; /* backpointer to owning route head */
99   struct rt_nexthop     rtp_nexthop;
100   struct rt_metric      rtp_metric;
101   union olsr_ip_addr    rtp_originator; /* originator of the route */
102   struct avl_node       rtp_tree_node; 
103   olsr_u32_t            rtp_version;
104 };
105
106 /*
107  * macro for traversing the entire routing table.
108  * it is recommended to use this because it hides all the internal
109  * datastructure from the callers.
110  *
111  * the loop prefetches the next node in order to not loose context if
112  * for example the caller wants to delete the current rt_entry.
113  */
114 #define OLSR_FOR_ALL_RT_ENTRIES(rt) \
115 { \
116   struct avl_node *rt_tree_node, *next_rt_tree_node; \
117   for (rt_tree_node = avl_walk_first(&routingtree); \
118     rt_tree_node; rt_tree_node = next_rt_tree_node) { \
119     next_rt_tree_node = avl_walk_next(rt_tree_node); \
120     rt = rt_tree_node->data;
121 #define OLSR_FOR_ALL_RT_ENTRIES_END(rt) }}
122
123 /**
124  * IPv4 <-> IPv6 wrapper
125  */
126 union olsr_kernel_route
127 {
128   struct
129   {
130     struct sockaddr rt_dst;
131     struct sockaddr rt_gateway;
132     olsr_u32_t metric;
133   } v4;
134
135   struct
136   {
137     struct in6_addr rtmsg_dst;
138     struct in6_addr rtmsg_gateway;
139     olsr_u32_t rtmsg_metric;
140   } v6;
141 };
142
143
144 extern struct avl_tree routingtree;
145 extern unsigned int routingtree_version;
146
147 int
148 olsr_init_routing_table(void);
149
150 unsigned int olsr_bump_routingtree_version(void);
151
152 int avl_comp_ipv4_prefix (void *, void *);
153 int avl_comp_ipv6_prefix (void *, void *);
154
155 void olsr_rt_best(struct rt_entry *);
156 olsr_bool olsr_nh_change(struct rt_nexthop *, struct rt_nexthop *);
157 olsr_bool olsr_cmp_rt(struct rt_entry *, struct rt_entry *);
158
159 void olsr_calculate_hna_routes(void);
160 int olsr_fill_routing_table_with_neighbors(void);
161 char *olsr_rt_to_string(struct rt_entry *);
162 char *olsr_rtp_to_string(struct rt_path *);
163 void olsr_print_routing_table(struct avl_tree *);
164
165 struct rt_nexthop * olsr_get_nh(struct rt_entry *);
166
167 struct rt_path *
168 olsr_insert_routing_table(union olsr_ip_addr *, int,
169                           union olsr_ip_addr *,
170                           union olsr_ip_addr *,
171                           struct interface *, int, float);
172
173 struct rt_entry *
174 olsr_lookup_routing_table(union olsr_ip_addr *);
175
176
177 #endif
178
179 /*
180  * Local Variables:
181  * c-basic-offset: 2
182  * End:
183  */