1300f167bf7c8d80436be2b0af3fa6b902c94270
[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 olsr_u8_t
69 olsr_rt_flags(const struct rt_entry *rt)
70 {
71   const struct rt_nexthop *nh;
72   olsr_u8_t flags = RTF_UP;
73
74   /* destination is host */
75   if (rt->rt_dst.prefix_len == olsr_cnf->maxplen) {
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
89 export_route_function olsr_addroute_function;
90 export_route_function olsr_addroute6_function;
91 export_route_function olsr_delroute_function;
92 export_route_function olsr_delroute6_function;
93
94
95 void 
96 olsr_init_export_route(void)
97 {
98   /* the add/chg/del kernel queues */
99   list_head_init(&add_kernel_list);
100   list_head_init(&chg_kernel_list);
101   list_head_init(&del_kernel_list);
102
103   olsr_addroute_function = olsr_ioctl_add_route;
104   olsr_addroute6_function = olsr_ioctl_add_route6;
105   olsr_delroute_function = olsr_ioctl_del_route;
106   olsr_delroute6_function = olsr_ioctl_del_route6;
107 }
108
109 /**
110  * Delete all OLSR routes.
111  *
112  * This is extremely simple - Just increment the version of the
113  * tree and then olsr_update_rib_routes() will see all routes in the tree
114  * as outdated and olsr_update_kernel_routes() will finally flush it.
115  *
116  */
117 void
118 olsr_delete_all_kernel_routes(void)
119
120   OLSR_PRINTF(1, "Deleting all routes...\n");
121
122   olsr_bump_routingtree_version();
123   olsr_update_rib_routes();
124   olsr_update_kernel_routes();
125 }
126
127 /**
128  * Enqueue a route on a kernel add/chg/del queue.
129  */
130 static void
131 olsr_enqueue_rt(struct list_node *head_node, struct rt_entry *rt)
132 {
133   const struct rt_nexthop *nh;
134
135   /* if this node is already on some changelist we are done */
136   if (list_node_on_list(&rt->rt_change_node)) {
137     return;
138   }
139
140   /*
141    * For easier route dependency tracking we enqueue nexthop routes
142    * at the head of the queue and non-nexthop routes at the tail of the queue.
143    */
144   nh = olsr_get_nh(rt);
145
146   if (ipequal(&rt->rt_dst.prefix, &nh->gateway)) {
147     list_add_after(head_node, &rt->rt_change_node);
148   } else {
149     list_add_before(head_node, &rt->rt_change_node);
150   }
151 }
152
153 /**
154  * Process a route from the kernel deletion list.
155  *
156  *@return nada
157  */
158 static void
159 olsr_delete_kernel_route(struct rt_entry *rt)
160 {
161   if(!olsr_cnf->host_emul) {
162     olsr_16_t error = olsr_cnf->ip_version == AF_INET ?
163       olsr_delroute_function(rt) : olsr_delroute6_function(rt);
164
165     if(error < 0) {
166       const char * const err_msg = strerror(errno);
167       const char * const routestr = olsr_rt_to_string(rt);
168       OLSR_PRINTF(1, "KERN: ERROR deleting %s: %s\n", routestr, err_msg);
169
170       olsr_syslog(OLSR_LOG_ERR, "Delete route %s: %s", routestr, err_msg);
171     }
172   }
173 }
174
175 /**
176  * Process a route from the kernel addition list.
177  *
178  *@return nada
179  */
180 static void
181 olsr_add_kernel_route(struct rt_entry *rt)
182 {
183
184   if(!olsr_cnf->host_emul) {
185     olsr_16_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   }
203 }
204
205 /**
206  * process the kernel add list.
207  * the routes are already ordered such that nexthop routes
208  * are on the head of the queue.
209  * nexthop routes need to be added first and therefore
210  * the queue needs to be traversed from head to tail.
211  */
212 static void
213 olsr_add_kernel_routes(struct list_node *head_node)
214 {
215   struct rt_entry *rt;
216
217   while (!list_is_empty(head_node)) {
218     rt = changelist2rt(head_node->next);
219     olsr_add_kernel_route(rt);
220
221     list_remove(&rt->rt_change_node);
222   }
223 }
224
225 /**
226  * process the kernel change list.
227  * the routes are already ordered such that nexthop routes
228  * are on the head of the queue.
229  * non-nexthop routes need to be changed first and therefore
230  * the queue needs to be traversed from tail to head.
231  */
232 static void
233 olsr_chg_kernel_routes(struct list_node *head_node)
234 {
235   struct rt_entry *rt;
236   struct list_node *node;
237
238   if (list_is_empty(head_node)) {
239     return;
240   }
241
242   /*
243    * First pass.
244    * traverse from the end to the beginning of the list,
245    * such that nexthop routes are deleted last.
246    */
247   for (node = head_node->prev; head_node != node; node = node->prev) {
248     rt = changelist2rt(node);
249     olsr_delete_kernel_route(rt);
250   }
251
252   /*
253    * Second pass.
254    * Traverse from the beginning to the end of the list,
255    * such that nexthop routes are added first.
256    */
257   while (!list_is_empty(head_node)) {
258     rt = changelist2rt(head_node->next);
259     olsr_add_kernel_route(rt);
260
261     list_remove(&rt->rt_change_node);
262   }
263 }
264
265 /**
266  * process the kernel delete list.
267  * the routes are already ordered such that nexthop routes
268  * are on the head of the queue.
269  * non-nexthop routes need to be deleted first and therefore
270  * the queue needs to be traversed from tail to head.
271  */
272 static void
273 olsr_del_kernel_routes(struct list_node *head_node)
274 {
275   struct rt_entry *rt;
276
277   while (!list_is_empty(head_node)) {
278     rt = changelist2rt(head_node->prev);
279     olsr_delete_kernel_route(rt);
280
281     list_remove(&rt->rt_change_node);
282     olsr_cookie_free(rt_mem_cookie, rt);
283   }
284 }
285
286 /**
287  * Check the version number of all route paths hanging off a route entry.
288  * If a route does not match the current routing tree number, remove it
289  * from the global originator tree for that rt_entry.
290  * Reset the best route pointer.
291  */
292 static void
293 olsr_delete_outdated_routes(struct rt_entry *rt)
294 {
295   struct rt_path *rtp;
296   struct avl_node *rtp_tree_node, *next_rtp_tree_node;
297
298   for (rtp_tree_node = avl_walk_first(&rt->rt_path_tree);
299        rtp_tree_node != NULL;
300        rtp_tree_node = next_rtp_tree_node) {
301
302     /*
303      * pre-fetch the next node before loosing context.
304      */
305     next_rtp_tree_node = avl_walk_next(rtp_tree_node);
306
307     rtp = rtp_tree2rtp(rtp_tree_node);
308
309     /*
310      * check the version number which gets incremented on every SPF run.
311      * comparing for unequalness avoids handling version number wraps.
312      */
313     if (routingtree_version != rtp->rtp_version) {
314
315       /* remove from the originator tree */
316       avl_delete(&rt->rt_path_tree, rtp_tree_node);
317       rtp->rtp_rt = NULL;
318     }
319   }
320
321   /* safety measure against dangling pointers */
322   rt->rt_best = NULL;
323 }
324
325 /**
326  * Walk all the routes, remove outdated routes and run
327  * best path selection on the remaining set.
328  * Finally compare the nexthop of the route head and the best
329  * path and enqueue an add/chg operation.
330  */
331 void
332 olsr_update_rib_routes(void)
333 {
334   struct rt_entry *rt;
335
336   OLSR_PRINTF(3, "Updating kernel routes...\n");
337
338   /* walk all routes in the RIB. */
339
340   OLSR_FOR_ALL_RT_ENTRIES(rt) {
341
342     /* eliminate first unused routes */
343     olsr_delete_outdated_routes(rt);
344
345     if (!rt->rt_path_tree.count) {
346
347       /* oops, all routes are gone - flush the route head */
348       avl_delete(&routingtree, rt_tree_node);
349
350       olsr_enqueue_rt(&del_kernel_list, rt);
351       continue;
352     }
353
354     /* run best route election */
355     olsr_rt_best(rt);
356
357     /* nexthop or hopcount change ? */
358     if (olsr_nh_change(&rt->rt_best->rtp_nexthop, &rt->rt_nexthop) ||
359         (FIBM_CORRECT == olsr_cnf->fib_metric &&
360          olsr_hopcount_change(&rt->rt_best->rtp_metric, &rt->rt_metric))) {
361
362       if (0 > rt->rt_nexthop.iif_index) {
363
364         /* fresh routes do have an interface index of -1. */
365         olsr_enqueue_rt(&add_kernel_list, rt);
366       } else { 
367
368         /* this is a route change. */
369         olsr_enqueue_rt(&chg_kernel_list, rt);
370       }
371     }
372   } OLSR_FOR_ALL_RT_ENTRIES_END(rt);
373 }
374
375 /**
376  * Propagate the accumulated changes from the last rib update to the kernel.
377  */
378 void
379 olsr_update_kernel_routes(void)
380 {
381
382   /* delete unreachable routes */
383   olsr_del_kernel_routes(&del_kernel_list);
384
385   /* route changes */
386   olsr_chg_kernel_routes(&chg_kernel_list);
387
388   /* route additions */
389   olsr_add_kernel_routes(&add_kernel_list);
390
391 #if DEBUG
392   olsr_print_routing_table(&routingtree);
393 #endif
394 }
395
396 /*
397  * Local Variables:
398  * c-basic-offset: 2
399  * indent-tabs-mode: nil
400  * End:
401  */