a68a65015dafd08f0e81a1846322a12bebcb233d
[olsrd.git] / src / process_routes.c
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 #include "process_routes.h"
43 #include "log.h"
44 #include "kernel_routes.h"
45 #include "olsr_logging.h"
46
47 #include <errno.h>
48
49 static struct list_entity chg_kernel_list;
50 static struct list_entity del_kernel_list;
51
52 /*
53  * Function hooks for plugins to intercept
54  * adding / deleting routes from the kernel
55  */
56 export_route_function olsr_add_route_function;
57 export_route_function olsr_del_route_function;
58
59
60 void
61 olsr_init_export_route(void)
62 {
63   OLSR_INFO(LOG_ROUTING, "Initialize route processing...\n");
64
65   /* the add/chg and del kernel queues */
66   list_init_head(&chg_kernel_list);
67   list_init_head(&del_kernel_list);
68
69   olsr_add_route_function = olsr_kernel_add_route;
70   olsr_del_route_function = olsr_kernel_del_route;
71 }
72
73 /**
74  * Delete all OLSR routes.
75  *
76  * This is extremely simple - Just increment the version of the
77  * tree and then olsr_update_rib_routes() will see all routes in the tree
78  * as outdated and olsr_update_kernel_routes() will finally flush it.
79  *
80  */
81 void
82 olsr_delete_all_kernel_routes(void)
83 {
84   OLSR_DEBUG(LOG_ROUTING, "Deleting all routes...\n");
85
86   olsr_bump_routingtree_version();
87   olsr_update_rib_routes();
88   olsr_update_kernel_routes();
89 }
90
91 /**
92  * Enqueue a route on a kernel chg/del queue.
93  */
94 static void
95 olsr_enqueue_rt(struct list_entity *head_node, struct rt_entry *rt)
96 {
97   const struct rt_nexthop *nh;
98
99   /* if this node is already on some changelist we are done */
100   if (list_node_added(&rt->rt_change_node)) {
101     return;
102   }
103
104   /*
105    * For easier route dependency tracking we enqueue nexthop routes
106    * at the head of the queue and non-nexthop routes at the tail of the queue.
107    */
108   nh = olsr_get_nh(rt);
109
110   if (olsr_ipcmp(&rt->rt_dst.prefix, &nh->gateway) == 0) {
111     list_add_after(head_node, &rt->rt_change_node);
112   } else {
113     list_add_before(head_node, &rt->rt_change_node);
114   }
115 }
116
117 /**
118  * Process a route from the kernel deletion list.
119  *
120  *@return nada
121  */
122 static void
123 olsr_del_route(struct rt_entry *rt)
124 {
125   int16_t error = olsr_del_route_function(rt, olsr_cnf->ip_version);
126
127   if (error < 0) {
128     OLSR_WARN(LOG_ROUTING, "KERN: ERROR deleting %s: %s\n", olsr_rt_to_string(rt), strerror(errno));
129   } else {
130
131     /* release the interface. */
132     unlock_interface(rt->rt_nexthop.interface);
133   }
134 }
135
136 /**
137  * Process a route from the kernel addition list.
138  *
139  *@return nada
140  */
141 static void
142 olsr_add_route(struct rt_entry *rt)
143 {
144   if (olsr_cnf->del_gws && 0 == rt->rt_dst.prefix_len) {
145     struct rt_entry defrt;
146     memset(&defrt, 0, sizeof(defrt));
147     /*
148      * Note: defrt.nexthop.interface == NULL means "remove unspecified default route"
149      */
150     while (0 <= olsr_del_route_function(&defrt, olsr_cnf->ip_version)) {
151     }
152     olsr_cnf->del_gws = false;
153     olsr_exit(9);
154   }
155
156   if (0 > olsr_add_route_function(rt, olsr_cnf->ip_version)) {
157     OLSR_WARN(LOG_ROUTING, "KERN: ERROR adding %s: %s\n", olsr_rtp_to_string(rt->rt_best), strerror(errno));
158   } else {
159     /* route addition has suceeded */
160
161     /* save the nexthop and metric in the route entry */
162     rt->rt_nexthop = rt->rt_best->rtp_nexthop;
163     rt->rt_metric = rt->rt_best->rtp_metric;
164
165     /* lock the interface such that it does not vanish underneath us */
166     lock_interface(rt->rt_nexthop.interface);
167   }
168 }
169
170 /**
171  * process the kernel change list.
172  * the routes are already ordered such that nexthop routes
173  * are on the head of the queue.
174  * non-nexthop routes need to be changed first and therefore
175  * the queue needs to be traversed from tail to head.
176  */
177 static void
178 olsr_chg_kernel_routes(struct list_entity *head_node)
179 {
180   struct rt_entry *rt;
181   struct list_iterator iterator;
182
183   if (list_is_empty(head_node)) {
184     return;
185   }
186
187   /*
188    * Traverse from the beginning to the end of the list,
189    * such that nexthop routes are added first.
190    */
191   OLSR_FOR_ALL_RTLIST_ENTRIES(head_node, rt, iterator) {
192
193     /*if netlink and NLFM_REPLACE is available (ipv4 only?) and used in linux/kernel_*.c no delete would be necesarry here */
194     if (rt->rt_nexthop.interface) olsr_del_route(rt); // fresh routes do not have an interface pointer
195
196     olsr_add_route(rt);
197
198     list_remove(&rt->rt_change_node);
199   }
200 }
201
202 /**
203  * process the kernel delete list.
204  * the routes are already ordered such that nexthop routes
205  * are on the head of the queue.
206  * non-nexthop routes need to be deleted first and therefore
207  * the queue needs to be traversed from tail to head.
208  */
209 static void
210 olsr_del_kernel_routes(struct list_entity *head_node)
211 {
212   struct rt_entry *rt;
213   struct list_iterator iterator;
214
215   OLSR_FOR_ALL_RTLIST_ENTRIES(head_node, rt, iterator) {
216     /*
217      * Only attempt to delete the route from kernel if it was
218      * installed previously. A reference to the interface gets
219      * set only when a route installation suceeds.
220      */
221     if (rt->rt_nexthop.interface) {
222       olsr_del_route(rt);
223     }
224
225     list_remove(&rt->rt_change_node);
226     olsr_cookie_free(rt_mem_cookie, rt);
227   }
228 }
229
230 /**
231  * Check the version number of all route paths hanging off a route entry.
232  * If a route does not match the current routing tree number, remove it
233  * from the global originator tree for that rt_entry.
234  * Reset the best route pointer.
235  */
236 static void
237 olsr_delete_outdated_routes(struct rt_entry *rt)
238 {
239   struct rt_path *rtp;
240   struct list_iterator iterator;
241
242   OLSR_FOR_ALL_RT_PATH_ENTRIES(rt, rtp, iterator) {
243     /*
244      * check the version number which gets incremented on every SPF run.
245      * comparing for unequalness avoids handling version number wraps.
246      */
247     if (routingtree_version != rtp->rtp_version) {
248
249       /* remove from the originator tree */
250       avl_delete(&rt->rt_path_tree, &rtp->rtp_tree_node);
251       rtp->rtp_rt = NULL;
252     }
253   }
254
255   /* safety measure against dangling pointers */
256   rt->rt_best = NULL;
257 }
258
259 /**
260  * Walk all the routes, remove outdated routes and run
261  * best path selection on the remaining set.
262  * Finally compare the nexthop of the route head and the best
263  * path and enqueue an add/chg operation.
264  */
265 void
266 olsr_update_rib_routes(void)
267 {
268   struct rt_entry *rt;
269   struct list_iterator iterator;
270
271   OLSR_DEBUG(LOG_ROUTING, "Updating kernel routes...\n");
272
273   /* walk all routes in the RIB. */
274
275   OLSR_FOR_ALL_RT_ENTRIES(rt, iterator) {
276
277     /* eliminate first unused routes */
278     olsr_delete_outdated_routes(rt);
279
280     if (!rt->rt_path_tree.count) {
281
282       /* oops, all routes are gone - flush the route head */
283       avl_delete(&routingtree, &rt->rt_tree_node);
284
285       olsr_enqueue_rt(&del_kernel_list, rt);
286       continue;
287     }
288
289     /* run best route election */
290     olsr_rt_best(rt);
291
292     /* nexthop or hopcount change ? */
293     if (olsr_nh_change(&rt->rt_best->rtp_nexthop, &rt->rt_nexthop) ||
294         (FIBM_CORRECT == olsr_cnf->fib_metric && olsr_hopcount_change(&rt->rt_best->rtp_metric, &rt->rt_metric))) {
295
296       olsr_enqueue_rt(&chg_kernel_list, rt);
297      
298     }
299   }
300 }
301
302 /**
303  * Propagate the accumulated changes from the last rib update to the kernel.
304  */
305 void
306 olsr_update_kernel_routes(void)
307 {
308
309   /* delete unreachable routes */
310   olsr_del_kernel_routes(&del_kernel_list);
311
312   /* route changes and additions */
313   olsr_chg_kernel_routes(&chg_kernel_list);
314
315 #ifdef DEBUG
316   olsr_print_routing_table();
317 #endif
318 }
319
320 /*
321  * Local Variables:
322  * c-basic-offset: 2
323  * indent-tabs-mode: nil
324  * End:
325  */