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