Let interface monitor take interface down and up
[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
56 #ifdef WIN32
57 char *StrError(unsigned int ErrNo);
58 #undef strerror
59 #define strerror(x) StrError(x)
60 #endif
61
62 static struct list_node chg_kernel_list;
63 static struct list_node del_kernel_list;
64
65 /**
66  *
67  * Calculate the kernel route flags.
68  * Called before enqueuing a change/delete operation
69  *
70  */
71 uint8_t
72 olsr_rt_flags(const struct rt_entry *rt)
73 {
74   const struct rt_nexthop *nh;
75   uint8_t flags = RTF_UP;
76
77   /* destination is host */
78   if (rt->rt_dst.prefix_len == olsr_cnf->maxplen) {
79     flags |= RTF_HOST;
80   }
81
82   nh = olsr_get_nh(rt);
83
84   if (!ipequal(&rt->rt_dst.prefix, &nh->gateway)) {
85     flags |= RTF_GATEWAY;
86   }
87
88   return flags;
89 }
90
91 export_route_function olsr_addroute_function;
92 export_route_function olsr_addroute6_function;
93 export_route_function olsr_delroute_function;
94 export_route_function olsr_delroute6_function;
95
96 void
97 olsr_init_export_route(void)
98 {
99   /* the add/chg/del kernel queues */
100   //list_head_init(&add_kernel_list);
101   list_head_init(&chg_kernel_list);
102   list_head_init(&del_kernel_list);
103
104   olsr_addroute_function = olsr_ioctl_add_route;
105   olsr_addroute6_function = olsr_ioctl_add_route6;
106   olsr_delroute_function = olsr_ioctl_del_route;
107   olsr_delroute6_function = olsr_ioctl_del_route6;
108 }
109
110 /**
111  * Delete all OLSR routes.
112  *
113  * This is extremely simple - Just increment the version of the
114  * tree and then olsr_update_rib_routes() will see all routes in the tree
115  * as outdated and olsr_update_kernel_routes() will finally flush it.
116  *
117  */
118 void
119 olsr_delete_all_kernel_routes(void)
120 {
121   OLSR_PRINTF(1, "Deleting all routes...\n");
122
123   olsr_bump_routingtree_version();
124   olsr_update_rib_routes();
125   olsr_update_kernel_routes();
126 }
127
128 /**
129  * Enqueue a route on a kernel add/chg/del queue.
130  */
131 static void
132 olsr_enqueue_rt(struct list_node *head_node, struct rt_entry *rt)
133 {
134   const struct rt_nexthop *nh;
135
136   /* if this node is already on some changelist we are done */
137   if (list_node_on_list(&rt->rt_change_node)) {
138     return;
139   }
140
141   /*
142    * For easier route dependency tracking we enqueue nexthop routes
143    * at the head of the queue and non-nexthop routes at the tail of the queue.
144    */
145   nh = olsr_get_nh(rt);
146
147   if (ipequal(&rt->rt_dst.prefix, &nh->gateway)) {
148     list_add_after(head_node, &rt->rt_change_node);
149   } else {
150     list_add_before(head_node, &rt->rt_change_node);
151   }
152 }
153
154 /**
155  * Process a route from the kernel deletion list.
156  *
157  *@return nada
158  */
159 static void
160 olsr_delete_kernel_route(struct rt_entry *rt)
161 {
162   if (!olsr_cnf->host_emul) {
163     int16_t error = olsr_cnf->ip_version == AF_INET ? 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     int16_t error = (olsr_cnf->ip_version == AF_INET) ? olsr_addroute_function(rt) : olsr_addroute6_function(rt);
186
187     if (error < 0) {
188       const char *const err_msg = strerror(errno);
189       const char *const routestr = olsr_rtp_to_string(rt->rt_best);
190       OLSR_PRINTF(1, "KERN: ERROR adding %s: %s\n", routestr, err_msg);
191
192       olsr_syslog(OLSR_LOG_ERR, "Add route %s: %s", routestr, err_msg);
193     } else {
194
195       /* route addition has suceeded */
196
197       /* save the nexthop and metric in the route entry */
198       rt->rt_nexthop = rt->rt_best->rtp_nexthop;
199       rt->rt_metric = rt->rt_best->rtp_metric;
200     }
201   }
202 }
203
204 /**
205  * process the kernel change list.
206  * the routes are already ordered such that nexthop routes
207  * are on the head of the queue.
208  * non-nexthop routes need to be changed first and therefore
209  * the queue needs to be traversed from tail to head.
210  */
211 static void
212 olsr_chg_kernel_routes(struct list_node *head_node)
213 {
214   struct rt_entry *rt;
215
216   if (list_is_empty(head_node)) {
217     return;
218   }
219
220   /*
221    * Traverse from the beginning to the end of the list,
222    * such that nexthop routes are added first.
223    */
224   while (!list_is_empty(head_node)) {
225     rt = changelist2rt(head_node->next);
226
227     if (rt->rt_nexthop.iif_index > -1) olsr_delete_kernel_route(rt);
228
229     olsr_add_kernel_route(rt);
230
231     list_remove(&rt->rt_change_node);
232   }
233 }
234
235 /**
236  * process the kernel delete list.
237  * the routes are already ordered such that nexthop routes
238  * are on the head of the queue.
239  * non-nexthop routes need to be deleted first and therefore
240  * the queue needs to be traversed from tail to head.
241  */
242 static void
243 olsr_del_kernel_routes(struct list_node *head_node)
244 {
245   struct rt_entry *rt;
246
247   while (!list_is_empty(head_node)) {
248     rt = changelist2rt(head_node->prev);
249 #if LINUX_POLICY_ROUTING
250     if (rt->rt_nexthop.iif_index >= 0)
251 #endif /*LINUX_POLICY_ROUTING*/
252       olsr_delete_kernel_route(rt);
253
254     list_remove(&rt->rt_change_node);
255     olsr_cookie_free(rt_mem_cookie, rt);
256   }
257 }
258
259 /**
260  * Check the version number of all route paths hanging off a route entry.
261  * If a route does not match the current routing tree number, remove it
262  * from the global originator tree for that rt_entry.
263  * Reset the best route pointer.
264  */
265 static void
266 olsr_delete_outdated_routes(struct rt_entry *rt)
267 {
268   struct rt_path *rtp;
269   struct avl_node *rtp_tree_node, *next_rtp_tree_node;
270
271   for (rtp_tree_node = avl_walk_first(&rt->rt_path_tree); rtp_tree_node != NULL; rtp_tree_node = next_rtp_tree_node) {
272     /*
273      * pre-fetch the next node before loosing context.
274      */
275     next_rtp_tree_node = avl_walk_next(rtp_tree_node);
276
277     rtp = rtp_tree2rtp(rtp_tree_node);
278
279     /*
280      * check the version number which gets incremented on every SPF run.
281      * comparing for unequalness avoids handling version number wraps.
282      */
283     if (routingtree_version != rtp->rtp_version) {
284       /* remove from the originator tree */
285       avl_delete(&rt->rt_path_tree, rtp_tree_node);
286       rtp->rtp_rt = NULL;
287
288       if (rt->rt_best == rtp) {
289         rt->rt_best = NULL;
290       }
291     }
292   }
293 }
294
295 /**
296  * Walk all the routes, remove outdated routes and run
297  * best path selection on the remaining set.
298  * Finally compare the nexthop of the route head and the best
299  * path and enqueue an add/chg operation.
300  */
301 void
302 olsr_update_rib_routes(void)
303 {
304   struct rt_entry *rt;
305
306   OLSR_PRINTF(3, "Updating kernel routes...\n");
307
308   /* walk all routes in the RIB. */
309
310   OLSR_FOR_ALL_RT_ENTRIES(rt) {
311
312     /* eliminate first unused routes */
313     olsr_delete_outdated_routes(rt);
314
315     if (!rt->rt_path_tree.count) {
316
317       /* oops, all routes are gone - flush the route head */
318       avl_delete(&routingtree, rt_tree_node);
319
320       olsr_enqueue_rt(&del_kernel_list, rt);
321       continue;
322     }
323
324     /* run best route election */
325     olsr_rt_best(rt);
326
327     /* nexthop or hopcount change ? */
328     if (olsr_nh_change(&rt->rt_best->rtp_nexthop, &rt->rt_nexthop)
329         || (FIBM_CORRECT == olsr_cnf->fib_metric && olsr_hopcount_change(&rt->rt_best->rtp_metric, &rt->rt_metric))) {
330
331         /* this is a route add or change. */
332         olsr_enqueue_rt(&chg_kernel_list, rt);
333     }
334   }
335   OLSR_FOR_ALL_RT_ENTRIES_END(rt);
336 }
337
338 void
339 olsr_delete_interface_routes(int if_index) {
340   struct rt_entry *rt;
341   bool triggerUpdate = false;
342
343   OLSR_FOR_ALL_RT_ENTRIES(rt) {
344     bool mightTrigger = false;
345     struct rt_path *rtp;
346     struct avl_node *rtp_tree_node, *next_rtp_tree_node;
347
348     /* run through all routing paths of route */
349     for (rtp_tree_node = avl_walk_first(&rt->rt_path_tree); rtp_tree_node != NULL; rtp_tree_node = next_rtp_tree_node) {
350       /*
351        * pre-fetch the next node before loosing context.
352        */
353       next_rtp_tree_node = avl_walk_next(rtp_tree_node);
354
355       rtp = rtp_tree2rtp(rtp_tree_node);
356
357       /* nexthop use lost interface ? */
358       if (rtp->rtp_nexthop.iif_index == if_index) {
359         /* remove from the originator tree */
360         avl_delete(&rt->rt_path_tree, rtp_tree_node);
361         rtp->rtp_rt = NULL;
362
363         if (rt->rt_best == rtp) {
364           rt->rt_best = NULL;
365           mightTrigger = true;
366         }
367       }
368     }
369
370     if (mightTrigger) {
371       if (!rt->rt_path_tree.count) {
372         /* oops, all routes are gone - flush the route head */
373         avl_delete(&routingtree, rt_tree_node);
374
375         /* do not dequeue route because they are already gone */
376       }
377       triggerUpdate = true;
378     }
379   } OLSR_FOR_ALL_RT_ENTRIES_END(rt)
380
381   /* trigger route update if necessary */
382   if (triggerUpdate) {
383     olsr_update_rib_routes();
384     olsr_update_kernel_routes();
385   }
386 }
387
388 /**
389  * Propagate the accumulated changes from the last rib update to the kernel.
390  */
391 void
392 olsr_update_kernel_routes(void)
393 {
394
395   /* delete unreachable routes */
396   olsr_del_kernel_routes(&del_kernel_list);
397
398   /* route changes */
399   olsr_chg_kernel_routes(&chg_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  */