* applied rt-refactoring-6.diff from Hannes Gredler <hannes@gredler.at>
[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>
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  * $Id: process_routes.c,v 1.35 2007/09/05 16:11:11 bernd67 Exp $
44  */
45
46 #include "defs.h"
47 #include "olsr.h"
48 #include "log.h"
49 #include "kernel_routes.h"
50 #include <assert.h>
51 #include "lq_avl.h"
52
53 #ifdef WIN32
54 #undef strerror
55 #define strerror(x) StrError(x)
56 #endif
57
58 struct export_route_entry
59 {
60   olsr_u8_t type;       /* AF_INET/AF_INET6 */
61   int (*function)(struct rt_entry*);
62   struct export_route_entry *next;
63 };
64
65
66 static struct export_route_entry *add_routes;
67 static struct export_route_entry *del_routes;
68
69 struct list_node add_kernel_list;
70 struct list_node chg_kernel_list;
71 struct list_node del_kernel_list;
72
73 /**
74  *
75  * Calculate the kernel route flags.
76  * Called before enqueuing a change/delete operation
77  *
78  */
79 olsr_u8_t
80 olsr_rt_flags(struct rt_entry *rt)
81 {
82   struct rt_nexthop *nh;
83   olsr_u8_t flags;
84
85   flags = (RTF_UP);
86
87   if (rt->rt_dst.prefix_len == olsr_host_rt_maxplen()) {
88     flags |= RTF_HOST;
89   }
90
91   nh = olsr_get_nh(rt);
92
93   if(!COMP_IP(&rt->rt_dst.prefix, &nh->gateway)) {
94     flags |= RTF_GATEWAY;
95   }
96
97   return flags;
98 }
99
100 void 
101 olsr_addroute_add_function(int (*function)(struct rt_entry*), olsr_u8_t type) 
102 {
103   struct export_route_entry *tmp;
104   tmp = olsr_malloc(sizeof *tmp, "olsr_addroute_add_function");
105   tmp->type = type;
106   tmp->function = function;
107   tmp->next = add_routes;
108   add_routes = tmp;
109 }
110
111 void 
112 olsr_delroute_add_function(int (*function) (struct rt_entry*), olsr_u8_t type)
113 {
114   struct export_route_entry *tmp;
115   tmp = olsr_malloc(sizeof *tmp, "olsr_delroute_add_function");
116   tmp->type = type;
117   tmp->function = function;
118   tmp->next = del_routes;
119   del_routes = tmp;
120 }
121
122
123 int 
124 olsr_addroute_remove_function(int (*function) (struct rt_entry*), olsr_u8_t type)
125 {
126   struct export_route_entry *tmp, *prev = NULL /* Make compiler happy */; 
127   tmp = add_routes;
128   while (tmp) 
129     {
130       if (function == tmp->function && type == tmp->type) 
131         {
132           if (tmp == add_routes) 
133             {
134               add_routes = add_routes->next;
135               free (tmp);
136               return 1;
137             }
138           else 
139             {
140               prev->next = tmp->next;
141               free (tmp);
142               return 1;
143             }
144         }
145       prev = tmp;
146       tmp = tmp->next;
147     }
148   return 0;
149 }
150
151 int
152 olsr_delroute_remove_function(int (*function) (struct rt_entry*), olsr_u8_t type)
153 {
154   struct export_route_entry *tmp, *prev = NULL /* Make compiler happy */;
155   tmp = del_routes;
156   while (tmp) 
157     {
158       if (function == tmp->function && type == tmp->type) 
159         {
160           if (tmp == del_routes) 
161             {
162               del_routes = del_routes->next;
163               free (tmp);
164               return 1;
165             }
166           else 
167             {
168               prev->next = tmp->next;
169               free (tmp);
170               return 1; 
171             }
172         }
173       prev = tmp;
174       tmp = tmp->next;
175     }
176   return 0;
177 }
178
179 void 
180 olsr_init_export_route(void)
181 {
182   olsr_addroute_add_function(&olsr_ioctl_add_route, AF_INET);
183   olsr_addroute_add_function(&olsr_ioctl_add_route6, AF_INET6);
184   olsr_delroute_add_function(&olsr_ioctl_del_route, AF_INET);
185   olsr_delroute_add_function(&olsr_ioctl_del_route6, AF_INET6);
186 }
187
188 int
189 olsr_export_add_route (struct rt_entry *rt) 
190 {
191   int retval = 0;
192   struct export_route_entry *tmp;
193   for (tmp = add_routes; tmp; tmp = tmp->next)
194     {
195       if (tmp->type == AF_INET)
196         retval = tmp->function(rt);
197     }
198   return retval;
199 }
200
201 int
202 olsr_export_add_route6 (struct rt_entry *rt) 
203 {
204   int retval = 0;
205   struct export_route_entry *tmp;
206   for (tmp = add_routes; tmp; tmp = tmp->next)
207     {
208       if (tmp->type == AF_INET6)
209         retval = tmp->function(rt);
210     }
211   return retval;
212 }
213
214 int
215 olsr_export_del_route (struct rt_entry *rt) 
216 {
217   int retval = 0;
218   struct export_route_entry *tmp;
219   for (tmp = del_routes; tmp; tmp = tmp->next)
220     {
221       if (tmp->type == AF_INET)
222         retval = tmp->function(rt);
223     }
224   return retval;
225 }
226
227 int
228 olsr_export_del_route6 (struct rt_entry *rt) 
229 {
230   int retval = 0;
231   struct export_route_entry *tmp;
232   for (tmp = del_routes; tmp; tmp = tmp->next)
233     {
234       if (tmp->type == AF_INET6)
235         retval = tmp->function(rt);
236     }
237   return retval;
238 }
239
240 /**
241  *Deletes all OLSR routes
242  *
243  * This is extremely simple - Just increment the version of the
244  * tree and then olsr_update_kernel_routes() will see
245  * all routes in the tree as outdated and flush it.
246  *
247  *@return 1
248  */
249 int
250 olsr_delete_all_kernel_routes(void)
251
252   OLSR_PRINTF(1, "Deleting all routes...\n");
253
254   olsr_bump_routingtree_version();
255   olsr_update_kernel_routes();
256
257   return 1;
258 }
259
260 /**
261  * Enqueue a route on a kernel add/chg/del queue.
262  */
263 static void
264 olsr_enqueue_rt(struct list_node *head_node, struct rt_entry *rt)
265 {
266   struct rt_nexthop *nh;
267
268   /* if this node is already on some changelist we are done */
269   if (list_node_on_list(&rt->rt_change_node)) {
270     return;
271   }
272
273   rt->rt_change_node.data = rt;
274
275   /*
276    * For easier route dependency tracking we enqueue nexthop routes
277    * at the head of the queue and non-nexthop routes at the tail of the queue.
278    */
279   nh = olsr_get_nh(rt);
280
281   if (COMP_IP(&rt->rt_dst.prefix, &nh->gateway)) {
282     list_add_after(head_node, &rt->rt_change_node);
283   } else {
284     list_add_before(head_node, &rt->rt_change_node);
285   }
286 }
287
288 /**
289  * Process a route from the kernel deletion list.
290  *
291  *@return nada
292  */
293 static void
294 olsr_delete_kernel_route(struct rt_entry *rt)
295 {
296   olsr_16_t error;                
297
298   if(!olsr_cnf->host_emul) {
299
300     if(olsr_cnf->ip_version == AF_INET) {
301       error = olsr_export_del_route(rt);
302     } else {
303       error = olsr_export_del_route6(rt);
304     }
305
306     if(error < 0) {
307       const char * const err_msg = strerror(errno);
308
309       OLSR_PRINTF(1, "KERN: ERROR deleting %s: %s\n",
310                   olsr_rt_to_string(rt), err_msg);
311
312       olsr_syslog(OLSR_LOG_ERR, "Delete route: %s", err_msg);
313
314     }
315   }
316 }
317
318 /**
319  * Process a route from the kernel addition list.
320  *
321  *@return nada
322  */
323 static void
324 olsr_add_kernel_route(struct rt_entry *rt)
325 {
326   olsr_16_t error;                
327
328   if(!olsr_cnf->host_emul) {
329
330     if(olsr_cnf->ip_version == AF_INET) {
331       error = olsr_export_add_route(rt);
332     } else {
333       error = olsr_export_add_route6(rt);
334     }
335     
336     if(error < 0) {
337       const char * const err_msg = strerror(errno);
338       OLSR_PRINTF(1, "KERN: ERROR adding %s: %s\n",
339                   olsr_rtp_to_string(rt->rt_best), err_msg);
340
341       olsr_syslog(OLSR_LOG_ERR, "Add route: %s", err_msg);
342     } else {
343
344       /* route addition has suceeded */
345
346       /* save the nexthop in the route entry */
347       rt->rt_nexthop = rt->rt_best->rtp_nexthop;
348     }
349   }
350 }
351
352 /**
353  * process the kernel add list.
354  * the routes are already ordered such that nexthop routes
355  * are on the head of the queue.
356  * nexthop routes need to be added first and therefore
357  * the queue needs to be traversed from head to tail.
358  */
359 static void
360 olsr_add_kernel_routes(struct list_node *head_node)
361 {
362   struct rt_entry *rt;
363
364   while (!list_is_empty(head_node)) {
365
366     rt = head_node->next->data;
367     olsr_add_kernel_route(rt);
368
369     list_remove(&rt->rt_change_node);
370   }
371 }
372
373 /**
374  * process the kernel change list.
375  * the routes are already ordered such that nexthop routes
376  * are on the head of the queue.
377  * non-nexthop routes need to be changed first and therefore
378  * the queue needs to be traversed from tail to head.
379  */
380 static void
381 olsr_chg_kernel_routes(struct list_node *head_node)
382 {
383   struct rt_entry *rt;
384   struct list_node *node;
385
386   if (list_is_empty(head_node)) {
387     return;
388   }
389
390   /*
391    * First pass.
392    * traverse from the end to the beginning of the list,
393    * such that nexthop routes are deleted last.
394    */
395   for (node = head_node->prev; head_node != node; node = node->prev) {
396
397     rt = node->data;
398     olsr_delete_kernel_route(rt);
399   }
400
401   /*
402    * Second pass.
403    * Traverse from the beginning to the end of the list,
404    * such that nexthop routes are added first.
405    */
406   while (!list_is_empty(head_node)) {
407
408     rt = head_node->next->data;
409     olsr_add_kernel_route(rt);
410
411     list_remove(&rt->rt_change_node);
412   }
413 }
414
415 /**
416  * process the kernel delete list.
417  * the routes are already ordered such that nexthop routes
418  * are on the head of the queue.
419  * non-nexthop routes need to be deleted first and therefore
420  * the queue needs to be traversed from tail to head.
421  */
422 static void
423 olsr_del_kernel_routes(struct list_node *head_node)
424 {
425   struct rt_entry *rt;
426
427   while (!list_is_empty(head_node)) {
428
429     rt = head_node->prev->data;
430     olsr_delete_kernel_route(rt);
431
432     list_remove(&rt->rt_change_node);
433     free(rt);
434   }
435 }
436
437 /**
438  * Check the version number of all route paths hanging off a route entry.
439  * If a route does not match the current routing tree number, delete it.
440  * Reset the best route pointer.
441  */
442 static void
443 olsr_delete_outdated_routes(struct rt_entry *rt)
444 {
445   struct rt_path *rtp;
446   struct avl_node *rtp_tree_node, *next_rtp_tree_node;
447
448   for (rtp_tree_node = avl_walk_first(&rt->rt_path_tree);
449        rtp_tree_node;
450        rtp_tree_node = next_rtp_tree_node) {
451
452     /*
453      * pre-fetch the next node before loosing context.
454      */
455     next_rtp_tree_node = avl_walk_next(rtp_tree_node);
456
457     rtp = rtp_tree_node->data;
458
459     /*
460      * check the version number which gets incremented on every SPF run.
461      * comparing for unequalness avoids handling version number wraps.
462      */
463     if (routingtree_version != rtp->rtp_version) {
464
465       /* remove from the originator tree */
466       avl_delete(&rt->rt_path_tree, rtp_tree_node);
467       free(rtp);
468     }
469   }
470
471   /* safety measure against dangling pointers */
472   rt->rt_best = NULL;
473 }
474
475 /**
476  * Walk all the routes, remove outdated routes and run
477  * best path selection on the remaining set.
478  * Finally compare the nexthop of the route head and the best
479  * path and enqueue a add/chg operation.
480  */
481 void
482 olsr_update_kernel_routes(void)
483 {
484   struct rt_entry *rt;
485
486   OLSR_PRINTF(3, "Updating kernel routes...\n");
487
488   /* walk all routes in the RIB. */
489
490   OLSR_FOR_ALL_RT_ENTRIES(rt) {
491
492     /* eliminate first unused routes */
493     olsr_delete_outdated_routes(rt);
494
495     if (!rt->rt_path_tree.count) {
496
497       /* oops, all routes are gone - flush the route head */
498       avl_delete(&routingtree, rt_tree_node);
499
500       olsr_enqueue_rt(&del_kernel_list, rt);
501       continue;
502     }
503
504     /* run best route election */
505     olsr_rt_best(rt);
506
507     /* nexthop change ? */
508     if (olsr_nh_change(&rt->rt_best->rtp_nexthop, &rt->rt_nexthop)) {
509
510       if (!rt->rt_nexthop.iface) {
511
512         /* fresh routes do have NULL pointers in the nexthop fields. */
513         olsr_enqueue_rt(&add_kernel_list, rt);
514       } else { 
515
516         /* this is a route change. */
517         olsr_enqueue_rt(&chg_kernel_list, rt);
518       }
519     }
520   } OLSR_FOR_ALL_RT_ENTRIES_END(rt);
521
522   /* delete unreachable routes */
523   olsr_del_kernel_routes(&del_kernel_list);
524
525   /* route changes */
526   olsr_chg_kernel_routes(&chg_kernel_list);
527
528   /* route additions */
529   olsr_add_kernel_routes(&add_kernel_list);
530
531 #if DEBUG
532   olsr_print_routing_table(&routingtree);
533 #endif
534 }
535
536 /*
537  * Local Variables:
538  * c-basic-offset: 2
539  * End:
540  */