Removed superfluous maxplen config var
[olsrd.git] / src / process_routes.c
1 /*
2  * The olsr.org Optimized Link-State Routing daemon(olsrd)
3  * Copyright (c) 2004, Andreas Tonnesen(andreto@olsr.org)
4  * RIB implementation (c) 2007, Hannes Gredler (hannes@gredler.at)
5  * All rights reserved.
6  *
7  * export_route_entry interface added by Immo 'FaUl Wehrenberg
8  * <immo@chaostreff-dortmund.de> and reworked by sven-ola 2007
9  *
10  * Redistribution and use in source and binary forms, with or without
11  * modification, are permitted provided that the following conditions
12  * are met:
13  *
14  * * Redistributions of source code must retain the above copyright
15  *   notice, this list of conditions and the following disclaimer.
16  * * Redistributions in binary form must reproduce the above copyright
17  *   notice, this list of conditions and the following disclaimer in
18  *   the documentation and/or other materials provided with the
19  *   distribution.
20  * * Neither the name of olsr.org, olsrd nor the names of its
21  *   contributors may be used to endorse or promote products derived
22  *   from this software without specific prior written permission.
23  *
24  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
25  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
26  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
27  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
28  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
29  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
30  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
31  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
32  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
33  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
34  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
35  * POSSIBILITY OF SUCH DAMAGE.
36  *
37  * Visit http://www.olsr.org for more information.
38  *
39  * If you find this software useful feel free to make a donation
40  * to the project. For more information see the website or contact
41  * the copyright holders.
42  *
43  */
44
45 #include "process_routes.h"
46 #include "log.h"
47 #include "kernel_routes.h"
48
49 #include <errno.h>
50
51 #ifdef WIN32
52 #undef strerror
53 #define strerror(x) StrError(x)
54 extern char *StrError(unsigned int ErrNo);
55 #endif
56
57 static struct list_node add_kernel_list;
58 static struct list_node chg_kernel_list;
59 static struct list_node del_kernel_list;
60
61
62 /**
63  *
64  * Calculate the kernel route flags.
65  * Called before enqueuing a change/delete operation
66  *
67  */
68 uint8_t
69 olsr_rt_flags(const struct rt_entry *rt)
70 {
71   const struct rt_nexthop *nh;
72   uint8_t flags = RTF_UP;
73
74   /* destination is host */
75   if (rt->rt_dst.prefix_len == 8 * olsr_cnf->ipsize) {
76     flags |= RTF_HOST;
77   }
78
79   nh = olsr_get_nh(rt);
80
81   if(!ipequal(&rt->rt_dst.prefix, &nh->gateway)) {
82     flags |= RTF_GATEWAY;
83   }
84
85   return flags;
86 }
87
88 export_route_function olsr_addroute_function;
89 export_route_function olsr_addroute6_function;
90 export_route_function olsr_delroute_function;
91 export_route_function olsr_delroute6_function;
92
93
94 void
95 olsr_init_export_route(void)
96 {
97   /* the add/chg/del kernel queues */
98   list_head_init(&add_kernel_list);
99   list_head_init(&chg_kernel_list);
100   list_head_init(&del_kernel_list);
101
102   olsr_addroute_function = olsr_ioctl_add_route;
103   olsr_addroute6_function = olsr_ioctl_add_route6;
104   olsr_delroute_function = olsr_ioctl_del_route;
105   olsr_delroute6_function = olsr_ioctl_del_route6;
106 }
107
108 /**
109  * Delete all OLSR routes.
110  *
111  * This is extremely simple - Just increment the version of the
112  * tree and then olsr_update_rib_routes() will see all routes in the tree
113  * as outdated and olsr_update_kernel_routes() will finally flush it.
114  *
115  */
116 void
117 olsr_delete_all_kernel_routes(void)
118 {
119   OLSR_PRINTF(1, "Deleting all routes...\n");
120
121   olsr_bump_routingtree_version();
122   olsr_update_rib_routes();
123   olsr_update_kernel_routes();
124 }
125
126 /**
127  * Enqueue a route on a kernel add/chg/del queue.
128  */
129 static void
130 olsr_enqueue_rt(struct list_node *head_node, struct rt_entry *rt)
131 {
132   const struct rt_nexthop *nh;
133
134   /* if this node is already on some changelist we are done */
135   if (list_node_on_list(&rt->rt_change_node)) {
136     return;
137   }
138
139   /*
140    * For easier route dependency tracking we enqueue nexthop routes
141    * at the head of the queue and non-nexthop routes at the tail of the queue.
142    */
143   nh = olsr_get_nh(rt);
144
145   if (ipequal(&rt->rt_dst.prefix, &nh->gateway)) {
146     list_add_after(head_node, &rt->rt_change_node);
147   } else {
148     list_add_before(head_node, &rt->rt_change_node);
149   }
150 }
151
152 /**
153  * Process a route from the kernel deletion list.
154  *
155  *@return nada
156  */
157 static void
158 olsr_delete_kernel_route(struct rt_entry *rt)
159 {
160   int16_t error = olsr_cnf->ip_version == AF_INET ?
161     olsr_delroute_function(rt) : olsr_delroute6_function(rt);
162
163   if(error < 0) {
164     const char * const err_msg = strerror(errno);
165     const char * const routestr = olsr_rt_to_string(rt);
166     OLSR_PRINTF(1, "KERN: ERROR deleting %s: %s\n", routestr, err_msg);
167
168     olsr_syslog(OLSR_LOG_ERR, "Delete route %s: %s", routestr, err_msg);
169   } else {
170
171     /* release the interface. */
172     unlock_interface(rt->rt_nexthop.interface);
173   }
174 }
175
176 /**
177  * Process a route from the kernel addition list.
178  *
179  *@return nada
180  */
181 static void
182 olsr_add_kernel_route(struct rt_entry *rt)
183 {
184
185   int16_t error = (olsr_cnf->ip_version == AF_INET) ?
186     olsr_addroute_function(rt) : olsr_addroute6_function(rt);
187
188   if(error < 0) {
189     const char * const err_msg = strerror(errno);
190     const char * const routestr = olsr_rtp_to_string(rt->rt_best);
191     OLSR_PRINTF(1, "KERN: ERROR adding %s: %s\n", routestr, err_msg);
192
193     olsr_syslog(OLSR_LOG_ERR, "Add route %s: %s", routestr, err_msg);
194   } else {
195
196     /* route addition has suceeded */
197
198     /* save the nexthop and metric in the route entry */
199     rt->rt_nexthop = rt->rt_best->rtp_nexthop;
200     rt->rt_metric = rt->rt_best->rtp_metric;
201
202     /* lock the interface such that it does not vanish underneath us */
203     lock_interface(rt->rt_nexthop.interface);
204   }
205 }
206
207 /**
208  * process the kernel add list.
209  * the routes are already ordered such that nexthop routes
210  * are on the head of the queue.
211  * nexthop routes need to be added first and therefore
212  * the queue needs to be traversed from head to tail.
213  */
214 static void
215 olsr_add_kernel_routes(struct list_node *head_node)
216 {
217   struct rt_entry *rt;
218
219   while (!list_is_empty(head_node)) {
220     rt = changelist2rt(head_node->next);
221     olsr_add_kernel_route(rt);
222
223     list_remove(&rt->rt_change_node);
224   }
225 }
226
227 /**
228  * process the kernel change list.
229  * the routes are already ordered such that nexthop routes
230  * are on the head of the queue.
231  * non-nexthop routes need to be changed first and therefore
232  * the queue needs to be traversed from tail to head.
233  */
234 static void
235 olsr_chg_kernel_routes(struct list_node *head_node)
236 {
237   struct rt_entry *rt;
238   struct list_node *node;
239
240   if (list_is_empty(head_node)) {
241     return;
242   }
243
244   /*
245    * First pass.
246    * traverse from the end to the beginning of the list,
247    * such that nexthop routes are deleted last.
248    */
249   for (node = head_node->prev; head_node != node; node = node->prev) {
250     rt = changelist2rt(node);
251     olsr_delete_kernel_route(rt);
252   }
253
254   /*
255    * Second pass.
256    * Traverse from the beginning to the end of the list,
257    * such that nexthop routes are added first.
258    */
259   while (!list_is_empty(head_node)) {
260     rt = changelist2rt(head_node->next);
261     olsr_add_kernel_route(rt);
262
263     list_remove(&rt->rt_change_node);
264   }
265 }
266
267 /**
268  * process the kernel delete list.
269  * the routes are already ordered such that nexthop routes
270  * are on the head of the queue.
271  * non-nexthop routes need to be deleted first and therefore
272  * the queue needs to be traversed from tail to head.
273  */
274 static void
275 olsr_del_kernel_routes(struct list_node *head_node)
276 {
277   struct rt_entry *rt;
278
279   while (!list_is_empty(head_node)) {
280     rt = changelist2rt(head_node->prev);
281
282     /*
283      * Only attempt to delete the route from kernel if it was
284      * installed previously. A reference to the interface gets
285      * set only when a route installation suceeds.
286      */
287     if (rt->rt_nexthop.interface) {
288       olsr_delete_kernel_route(rt);
289     }
290
291     list_remove(&rt->rt_change_node);
292     olsr_cookie_free(rt_mem_cookie, rt);
293   }
294 }
295
296 /**
297  * Check the version number of all route paths hanging off a route entry.
298  * If a route does not match the current routing tree number, remove it
299  * from the global originator tree for that rt_entry.
300  * Reset the best route pointer.
301  */
302 static void
303 olsr_delete_outdated_routes(struct rt_entry *rt)
304 {
305   struct rt_path *rtp;
306   struct avl_node *rtp_tree_node, *next_rtp_tree_node;
307
308   for (rtp_tree_node = avl_walk_first(&rt->rt_path_tree);
309        rtp_tree_node != NULL;
310        rtp_tree_node = next_rtp_tree_node) {
311
312     /*
313      * pre-fetch the next node before loosing context.
314      */
315     next_rtp_tree_node = avl_walk_next(rtp_tree_node);
316
317     rtp = rtp_tree2rtp(rtp_tree_node);
318
319     /*
320      * check the version number which gets incremented on every SPF run.
321      * comparing for unequalness avoids handling version number wraps.
322      */
323     if (routingtree_version != rtp->rtp_version) {
324
325       /* remove from the originator tree */
326       avl_delete(&rt->rt_path_tree, rtp_tree_node);
327       rtp->rtp_rt = NULL;
328     }
329   }
330
331   /* safety measure against dangling pointers */
332   rt->rt_best = NULL;
333 }
334
335 /**
336  * Walk all the routes, remove outdated routes and run
337  * best path selection on the remaining set.
338  * Finally compare the nexthop of the route head and the best
339  * path and enqueue an add/chg operation.
340  */
341 void
342 olsr_update_rib_routes(void)
343 {
344   struct rt_entry *rt;
345
346   OLSR_PRINTF(3, "Updating kernel routes...\n");
347
348   /* walk all routes in the RIB. */
349
350   OLSR_FOR_ALL_RT_ENTRIES(rt) {
351
352     /* eliminate first unused routes */
353     olsr_delete_outdated_routes(rt);
354
355     if (!rt->rt_path_tree.count) {
356
357       /* oops, all routes are gone - flush the route head */
358       avl_delete(&routingtree, rt_tree_node);
359
360       olsr_enqueue_rt(&del_kernel_list, rt);
361       continue;
362     }
363
364     /* run best route election */
365     olsr_rt_best(rt);
366
367     /* nexthop or hopcount change ? */
368     if (olsr_nh_change(&rt->rt_best->rtp_nexthop, &rt->rt_nexthop) ||
369         (FIBM_CORRECT == olsr_cnf->fib_metric &&
370          olsr_hopcount_change(&rt->rt_best->rtp_metric, &rt->rt_metric))) {
371
372       if (!rt->rt_nexthop.interface) {
373
374         /* fresh routes do not have an interface pointer */
375         olsr_enqueue_rt(&add_kernel_list, rt);
376       } else {
377
378         /* this is a route change. */
379         olsr_enqueue_rt(&chg_kernel_list, rt);
380       }
381     }
382   } OLSR_FOR_ALL_RT_ENTRIES_END(rt);
383 }
384
385 /**
386  * Propagate the accumulated changes from the last rib update to the kernel.
387  */
388 void
389 olsr_update_kernel_routes(void)
390 {
391
392   /* delete unreachable routes */
393   olsr_del_kernel_routes(&del_kernel_list);
394
395   /* route changes */
396   olsr_chg_kernel_routes(&chg_kernel_list);
397
398   /* route additions */
399   olsr_add_kernel_routes(&add_kernel_list);
400
401 #if DEBUG
402   olsr_print_routing_table(&routingtree);
403 #endif
404 }
405
406 /*
407  * Local Variables:
408  * c-basic-offset: 2
409  * indent-tabs-mode: nil
410  * End:
411  */