move avl and list library into src/common
[olsrd.git] / src / process_routes.c
1 /*
2  * The olsr.org Optimized Link-State Routing daemon(olsrd)
3  * Copyright (c) 2004, Andreas T√łnnesen(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 "ipcalc.h"
46 #include "defs.h"
47 #include "olsr.h"
48 #include "log.h"
49 #include "kernel_routes.h"
50 #include "common/avl.h"
51 #include "net_olsr.h"
52 #include "tc_set.h"
53
54 #ifdef WIN32
55 #undef strerror
56 #define strerror(x) StrError(x)
57 #endif
58
59 static struct list_node add_kernel_list;
60 static struct list_node chg_kernel_list;
61 static struct list_node del_kernel_list;
62
63
64 /**
65  *
66  * Calculate the kernel route flags.
67  * Called before enqueuing a change/delete operation
68  *
69  */
70 olsr_u8_t
71 olsr_rt_flags(const struct rt_entry *rt)
72 {
73   const struct rt_nexthop *nh;
74   olsr_u8_t flags = RTF_UP;
75
76   if (rt->rt_dst.prefix_len == olsr_cnf->maxplen) {
77     flags |= RTF_HOST;
78   }
79
80   nh = olsr_get_nh(rt);
81
82   if(!ipequal(&rt->rt_dst.prefix, &nh->gateway)) {
83     flags |= RTF_GATEWAY;
84   }
85
86   return flags;
87 }
88
89
90 export_route_function olsr_addroute_function;
91 export_route_function olsr_addroute6_function;
92 export_route_function olsr_delroute_function;
93 export_route_function olsr_delroute6_function;
94
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  *Deletes 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  *@return 1
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   rt->rt_change_node.data = rt;
143
144   /*
145    * For easier route dependency tracking we enqueue nexthop routes
146    * at the head of the queue and non-nexthop routes at the tail of the queue.
147    */
148   nh = olsr_get_nh(rt);
149
150   if (ipequal(&rt->rt_dst.prefix, &nh->gateway)) {
151     list_add_after(head_node, &rt->rt_change_node);
152   } else {
153     list_add_before(head_node, &rt->rt_change_node);
154   }
155 }
156
157 /**
158  * Process a route from the kernel deletion list.
159  *
160  *@return nada
161  */
162 static void
163 olsr_delete_kernel_route(struct rt_entry *rt)
164 {
165   if(!olsr_cnf->host_emul) {
166     olsr_16_t error = olsr_cnf->ip_version == AF_INET ?
167       olsr_delroute_function(rt) : olsr_delroute6_function(rt);
168
169     if(error < 0) {
170       const char * const err_msg = strerror(errno);
171       const char * const routestr = olsr_rt_to_string(rt);
172       OLSR_PRINTF(1, "KERN: ERROR deleting %s: %s\n", routestr, err_msg);
173
174       olsr_syslog(OLSR_LOG_ERR, "Delete route %s: %s", routestr, err_msg);
175     }
176   }
177 }
178
179 /**
180  * Process a route from the kernel addition list.
181  *
182  *@return nada
183  */
184 static void
185 olsr_add_kernel_route(struct rt_entry *rt)
186 {
187
188   if(!olsr_cnf->host_emul) {
189     olsr_16_t error = olsr_cnf->ip_version == AF_INET ?
190       olsr_addroute_function(rt) : olsr_addroute6_function(rt);
191
192     if(error < 0) {
193       const char * const err_msg = strerror(errno);
194       const char * const routestr = olsr_rtp_to_string(rt->rt_best);
195       OLSR_PRINTF(1, "KERN: ERROR adding %s: %s\n", routestr, err_msg);
196
197       olsr_syslog(OLSR_LOG_ERR, "Add route %s: %s", routestr, err_msg);
198     } else {
199
200       /* route addition has suceeded */
201
202       /* save the nexthop and metric in the route entry */
203       rt->rt_nexthop = rt->rt_best->rtp_nexthop;
204       rt->rt_metric = rt->rt_best->rtp_metric;
205     }
206   }
207 }
208
209 /**
210  * process the kernel add list.
211  * the routes are already ordered such that nexthop routes
212  * are on the head of the queue.
213  * nexthop routes need to be added first and therefore
214  * the queue needs to be traversed from head to tail.
215  */
216 static void
217 olsr_add_kernel_routes(struct list_node *head_node)
218 {
219   while (!list_is_empty(head_node)) {
220     struct rt_entry *rt = head_node->next->data;
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 list_node *node;
238
239   if (list_is_empty(head_node)) {
240     return;
241   }
242
243   /*
244    * First pass.
245    * traverse from the end to the beginning of the list,
246    * such that nexthop routes are deleted last.
247    */
248   for (node = head_node->prev; head_node != node; node = node->prev) {
249     struct rt_entry *rt = node->data;
250     olsr_delete_kernel_route(rt);
251   }
252
253   /*
254    * Second pass.
255    * Traverse from the beginning to the end of the list,
256    * such that nexthop routes are added first.
257    */
258   while (!list_is_empty(head_node)) {
259     struct rt_entry *rt = head_node->next->data;
260     olsr_add_kernel_route(rt);
261
262     list_remove(&rt->rt_change_node);
263   }
264 }
265
266 /**
267  * process the kernel delete list.
268  * the routes are already ordered such that nexthop routes
269  * are on the head of the queue.
270  * non-nexthop routes need to be deleted first and therefore
271  * the queue needs to be traversed from tail to head.
272  */
273 static void
274 olsr_del_kernel_routes(struct list_node *head_node)
275 {
276   while (!list_is_empty(head_node)) {
277     struct rt_entry *rt = head_node->prev->data;
278     olsr_delete_kernel_route(rt);
279
280     list_remove(&rt->rt_change_node);
281     free(rt);
282   }
283 }
284
285 /**
286  * Check the version number of all route paths hanging off a route entry.
287  * If a route does not match the current routing tree number, remove it
288  * from the global originator tree for that rt_entry.
289  * Reset the best route pointer.
290  */
291 static void
292 olsr_delete_outdated_routes(struct rt_entry *rt)
293 {
294   struct rt_path *rtp;
295   struct avl_node *rtp_tree_node, *next_rtp_tree_node;
296
297   for (rtp_tree_node = avl_walk_first(&rt->rt_path_tree);
298        rtp_tree_node != NULL;
299        rtp_tree_node = next_rtp_tree_node) {
300
301     /*
302      * pre-fetch the next node before loosing context.
303      */
304     next_rtp_tree_node = avl_walk_next(rtp_tree_node);
305
306     rtp = rtp_tree_node->data;
307
308     /*
309      * check the version number which gets incremented on every SPF run.
310      * comparing for unequalness avoids handling version number wraps.
311      */
312     if (routingtree_version != rtp->rtp_version) {
313
314       /* remove from the originator tree */
315       avl_delete(&rt->rt_path_tree, rtp_tree_node);
316       rtp->rtp_rt = NULL;
317     }
318   }
319
320   /* safety measure against dangling pointers */
321   rt->rt_best = NULL;
322 }
323
324 /**
325  * Walk all the routes, remove outdated routes and run
326  * best path selection on the remaining set.
327  * Finally compare the nexthop of the route head and the best
328  * path and enqueue an add/chg operation.
329  */
330 void
331 olsr_update_rib_routes(void)
332 {
333   struct rt_entry *rt;
334
335   OLSR_PRINTF(3, "Updating kernel routes...\n");
336
337   /* walk all routes in the RIB. */
338
339   OLSR_FOR_ALL_RT_ENTRIES(rt) {
340
341     /* eliminate first unused routes */
342     olsr_delete_outdated_routes(rt);
343
344     if (!rt->rt_path_tree.count) {
345
346       /* oops, all routes are gone - flush the route head */
347       avl_delete(&routingtree, rt_tree_node);
348
349       olsr_enqueue_rt(&del_kernel_list, rt);
350       continue;
351     }
352
353     /* run best route election */
354     olsr_rt_best(rt);
355
356     /* nexthop or hopcount change ? */
357     if (olsr_nh_change(&rt->rt_best->rtp_nexthop, &rt->rt_nexthop) ||
358         (FIBM_CORRECT == olsr_cnf->fib_metric &&
359          olsr_hopcount_change(&rt->rt_best->rtp_metric, &rt->rt_metric))) {
360
361       if (0 > rt->rt_nexthop.iif_index) {
362
363         /* fresh routes do have an interface index of -1. */
364         olsr_enqueue_rt(&add_kernel_list, rt);
365       } else { 
366
367         /* this is a route change. */
368         olsr_enqueue_rt(&chg_kernel_list, rt);
369       }
370     }
371   } OLSR_FOR_ALL_RT_ENTRIES_END(rt);
372 }
373
374 /**
375  * Propagate the accumulated changes from the last rib update to the kernel.
376  */
377 void
378 olsr_update_kernel_routes(void)
379 {
380
381   /* delete unreachable routes */
382   olsr_del_kernel_routes(&del_kernel_list);
383
384   /* route changes */
385   olsr_chg_kernel_routes(&chg_kernel_list);
386
387   /* route additions */
388   olsr_add_kernel_routes(&add_kernel_list);
389
390 #if DEBUG
391   olsr_print_routing_table(&routingtree);
392 #endif
393 }
394
395 /*
396  * Local Variables:
397  * c-basic-offset: 2
398  * End:
399  */