1a113f5ae68703cab4725d783a0aea41628d3cd3
[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  * All rights reserved.
5  *
6  * export_route_entry interface added by Immo 'FaUl Wehrenberg 
7  * <immo@chaostreff-dortmund.de>
8  *
9  * Redistribution and use in source and binary forms, with or without 
10  * modification, are permitted provided that the following conditions 
11  * are met:
12  *
13  * * Redistributions of source code must retain the above copyright 
14  *   notice, this list of conditions and the following disclaimer.
15  * * Redistributions in binary form must reproduce the above copyright 
16  *   notice, this list of conditions and the following disclaimer in 
17  *   the documentation and/or other materials provided with the 
18  *   distribution.
19  * * Neither the name of olsr.org, olsrd nor the names of its 
20  *   contributors may be used to endorse or promote products derived 
21  *   from this software without specific prior written permission.
22  *
23  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 
24  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 
25  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 
26  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 
27  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 
28  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 
29  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 
30  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 
31  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 
32  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 
33  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 
34  * POSSIBILITY OF SUCH DAMAGE.
35  *
36  * Visit http://www.olsr.org for more information.
37  *
38  * If you find this software useful feel free to make a donation
39  * to the project. For more information see the website or contact
40  * the copyright holders.
41  *
42  * $Id: process_routes.c,v 1.34 2007/08/02 22:07:19 bernd67 Exp $
43  */
44
45 #include "defs.h"
46 #include "olsr.h"
47 #include "log.h"
48 #include "kernel_routes.h"
49 #include <assert.h>
50
51 #ifdef WIN32
52 #undef strerror
53 #define strerror(x) StrError(x)
54 #endif
55
56 struct export_route_entry
57 {
58   olsr_u8_t type;       /* AF_INET/AF_INET6 */
59   int (*function)(struct rt_entry*);
60   struct export_route_entry *next;
61 };
62
63
64 static struct export_route_entry *add_routes;
65 static struct export_route_entry *del_routes;
66
67
68 struct rt_entry old_routes[HASHSIZE];
69 struct rt_entry old_hna[HASHSIZE];
70
71 void 
72 olsr_addroute_add_function(int (*function)(struct rt_entry*), olsr_u8_t type) 
73 {
74   struct export_route_entry *tmp;
75   tmp = olsr_malloc(sizeof *tmp, "olsr_addroute_add_function");
76   tmp->type = type;
77   tmp->function = function;
78   tmp->next = add_routes;
79   add_routes = tmp;
80 }
81
82 void 
83 olsr_delroute_add_function(int (*function) (struct rt_entry*), olsr_u8_t type)
84 {
85   struct export_route_entry *tmp;
86   tmp = olsr_malloc(sizeof *tmp, "olsr_delroute_add_function");
87   tmp->type = type;
88   tmp->function = function;
89   tmp->next = del_routes;
90   del_routes = tmp;
91 }
92
93
94 int 
95 olsr_addroute_remove_function(int (*function) (struct rt_entry*), olsr_u8_t type)
96 {
97   struct export_route_entry *tmp, *prev = NULL /* Make compiler happy */; 
98   tmp = add_routes;
99   while (tmp) 
100     {
101       if (function == tmp->function && type == tmp->type) 
102         {
103           if (tmp == add_routes) 
104             {
105               add_routes = add_routes->next;
106               free (tmp);
107               return 1;
108             }
109           else 
110             {
111               prev->next = tmp->next;
112               free (tmp);
113               return 1;
114             }
115         }
116       prev = tmp;
117       tmp = tmp->next;
118     }
119   return 0;
120 }
121
122 int
123 olsr_delroute_remove_function(int (*function) (struct rt_entry*), olsr_u8_t type)
124 {
125   struct export_route_entry *tmp, *prev = NULL /* Make compiler happy */;
126   tmp = del_routes;
127   while (tmp) 
128     {
129       if (function == tmp->function && type == tmp->type) 
130         {
131           if (tmp == del_routes) 
132             {
133               del_routes = del_routes->next;
134               free (tmp);
135               return 1;
136             }
137           else 
138             {
139               prev->next = tmp->next;
140               free (tmp);
141               return 1; 
142             }
143         }
144       prev = tmp;
145       tmp = tmp->next;
146     }
147   return 0;
148 }
149
150 void 
151 olsr_init_export_route(void)
152 {
153   olsr_addroute_add_function(&olsr_ioctl_add_route, AF_INET);
154   olsr_addroute_add_function(&olsr_ioctl_add_route6, AF_INET6);
155   olsr_delroute_add_function(&olsr_ioctl_del_route, AF_INET);
156   olsr_delroute_add_function(&olsr_ioctl_del_route6, AF_INET6);
157 }
158
159 int
160 olsr_export_add_route (struct rt_entry *e) 
161 {
162   int retval = 0;
163   struct export_route_entry *tmp;
164   for (tmp = add_routes; tmp; tmp = tmp->next)
165     {
166       if (tmp->type == AF_INET)
167         retval = tmp->function(e);
168     }
169   return retval;
170 }
171
172 int
173 olsr_export_add_route6 (struct rt_entry *e) 
174 {
175   int retval = 0;
176   struct export_route_entry *tmp;
177   for (tmp = add_routes; tmp; tmp = tmp->next)
178     {
179       if (tmp->type == AF_INET6)
180         retval = tmp->function(e);
181     }
182   return retval;
183 }
184
185 int
186 olsr_export_del_route (struct rt_entry *e) 
187 {
188   int retval = 0;
189   struct export_route_entry *tmp;
190   for (tmp = del_routes; tmp; tmp = tmp->next)
191     {
192       if (tmp->type == AF_INET)
193         retval = tmp->function(e);
194     }
195   return retval;
196 }
197
198 int
199 olsr_export_del_route6 (struct rt_entry *e) 
200 {
201   int retval = 0;
202   struct export_route_entry *tmp;
203   for (tmp = del_routes; tmp; tmp = tmp->next)
204     {
205       if (tmp->type == AF_INET6)
206         retval = tmp->function(e);
207     }
208   return retval;
209 }
210
211
212
213 int
214 olsr_init_old_table(void)
215 {
216   int idx;
217
218   for(idx=0;idx<HASHSIZE;idx++)
219     {
220       old_routes[idx].next = &old_routes[idx];
221       old_routes[idx].prev = &old_routes[idx];
222       old_hna[idx].next = &old_hna[idx];
223       old_hna[idx].prev = &old_hna[idx];
224     }
225
226   return 1;
227 }
228
229 /**
230  *Checks if there exists a route to a given host
231  *in a given hash table.
232  *
233  *@param dst the host to check for
234  *@param table the table to check
235  *
236  *@return 1 if the host exists in the table, 0 if not
237  */
238 int
239 olsr_find_up_route(struct rt_entry *dst, struct rt_entry *table)
240
241   struct rt_entry  *destination;
242   const olsr_u32_t  hash = olsr_hashing(&dst->rt_dst);
243
244   for(destination = table[hash].next; destination != &table[hash]; destination = destination->next)
245     {
246       //printf("Checking %s hc: %d ", olsr_ip_to_string(&dst->rt_dst), dst->rt_metric);
247       //printf("vs %s hc: %d ... ", olsr_ip_to_string(&destination->rt_dst), destination->rt_metric);      
248       if (COMP_IP(&destination->rt_dst, &dst->rt_dst) &&
249           COMP_IP(&destination->rt_router, &dst->rt_router) &&
250           (destination->rt_if->if_index == dst->rt_if->if_index))
251         {
252           if(destination->rt_metric == dst->rt_metric)
253             {
254               return 1;
255             }
256           else
257             {
258               return 0;
259             }
260         }
261     }
262   return 0;
263 }
264
265
266 /**
267  *Create a list containing the entries in from_table
268  *that do not exist in in_table
269  *
270  *@param from_table the table to use
271  *@param in_table the routes already added
272  *
273  *@return a poiter to a linked list of routes to add
274  */
275 struct destination_n *
276 olsr_build_update_list(struct rt_entry *from_table,struct rt_entry *in_table)
277 {
278   struct destination_n *kernel_route_list = NULL;
279   struct rt_entry      *destination;
280   int                   idx;
281   
282   for(idx=0;idx<HASHSIZE;idx++)
283     {
284       for(destination = from_table[idx].next;
285           destination != &from_table[idx];
286           destination = destination->next)
287         {
288           if (!olsr_find_up_route(destination, in_table))
289             {
290               struct destination_n *route_list;
291               route_list = olsr_malloc(sizeof(struct destination_n), "create route tmp list");
292               
293               route_list->destination = destination;
294               
295               route_list->next = kernel_route_list;
296               kernel_route_list = route_list;
297             }
298         }   
299     }
300   
301   return (kernel_route_list);
302 }
303
304
305
306
307
308 /**
309  *Deletes all OLSR routes
310  *
311  *
312  *@return 1
313  */
314 int
315 olsr_delete_all_kernel_routes(void)
316
317   struct destination_n *delete_kernel_list;
318   struct destination_n *tmp;
319
320   OLSR_PRINTF(1, "Deleting all routes...\n");
321
322   delete_kernel_list = olsr_build_update_list(hna_routes, old_hna);
323
324   OLSR_PRINTF(1, "HNA list:\n");
325   for(tmp = delete_kernel_list;tmp;tmp = tmp->next)
326     {
327       union olsr_ip_addr *tmp_addr = &tmp->destination->rt_dst;
328       OLSR_PRINTF(1, "Dest: %s\n", olsr_ip_to_string(tmp_addr));
329     }
330
331   olsr_delete_routes_from_kernel(delete_kernel_list);
332
333   delete_kernel_list = olsr_build_update_list(routingtable,old_routes);
334
335   OLSR_PRINTF(1, "Route list:\n");
336   for(tmp = delete_kernel_list;tmp;tmp = tmp->next)
337     {
338       union olsr_ip_addr *tmp_addr = &tmp->destination->rt_dst;
339       OLSR_PRINTF(1, "Dest: %s\n", olsr_ip_to_string(tmp_addr));
340     }
341   olsr_delete_routes_from_kernel(delete_kernel_list);
342   return 1;
343 }
344
345
346 /**
347  *Perform all neccessary actions for an update of the 
348  *routes in the kernel.
349  *
350  *@return nada
351  */
352 void
353 olsr_update_kernel_routes(void)
354 {
355   struct destination_n *delete_kernel_list;
356   struct destination_n *add_kernel_list;
357
358   OLSR_PRINTF(3, "Updating kernel routes...\n");
359   delete_kernel_list = olsr_build_update_list(old_routes, routingtable);
360   add_kernel_list = olsr_build_update_list(routingtable, old_routes);
361
362   olsr_delete_routes_from_kernel(delete_kernel_list);
363   olsr_add_routes_in_kernel(add_kernel_list);
364 }
365
366
367
368 /**
369  *Perform all neccessary actions for an update of the 
370  *HNA routes in the kernel.
371  *
372  *@return nada
373  */
374 void
375 olsr_update_kernel_hna_routes(void)
376 {
377   struct destination_n *delete_kernel_list;
378   struct destination_n *add_kernel_list;
379
380   OLSR_PRINTF(3, "Updating kernel HNA routes...\n");
381
382   delete_kernel_list = olsr_build_update_list(old_hna, hna_routes);
383   add_kernel_list = olsr_build_update_list(hna_routes, old_hna);
384
385   olsr_delete_routes_from_kernel(delete_kernel_list);
386   olsr_add_routes_in_kernel(add_kernel_list);
387 }
388
389
390 /**
391  *Create a copy of the routing table and
392  *clear the current table
393  *
394  *@param original the table to move from
395  *@param the table to move to
396  *
397  *@return nada
398  */
399 void
400 olsr_move_route_table(struct rt_entry *original, struct rt_entry *new)
401 {
402   int idx;
403
404   for(idx=0;idx<HASHSIZE;idx++)
405     {
406       if(original[idx].next == &original[idx])
407         {
408           new[idx].next = &new[idx];
409           new[idx].prev = &new[idx];
410         }
411       else
412         {
413           /* Copy to old */
414           new[idx].next = original[idx].next;
415           new[idx].next->prev = &new[idx];
416           new[idx].prev = original[idx].prev;
417           new[idx].prev->next = &new[idx];
418
419           /* Clear original */
420           original[idx].next = &original[idx];
421           original[idx].prev = &original[idx];
422         }
423     }
424 }
425
426
427 /**
428  *Delete a linked list of routes from the kernel.
429  *
430  *@param delete_kernel_list the list to delete
431  *
432  *@return nada
433  */
434 void 
435 olsr_delete_routes_from_kernel(struct destination_n *delete_kernel_list)
436 {
437   struct destination_n *destination_ptr;
438   int metric_counter = 1;
439   olsr_bool last_run = OLSR_FALSE;
440
441
442   /* Find highest metric */
443   for(destination_ptr = delete_kernel_list;
444       destination_ptr != NULL;
445       destination_ptr = destination_ptr->next)
446     {
447       if(destination_ptr->destination->rt_metric > metric_counter)
448         metric_counter = destination_ptr->destination->rt_metric;
449     }
450
451 #ifdef DEBUG
452   OLSR_PRINTF(3, "%s highest metric %d\n",
453               __func__, metric_counter);
454 #endif
455  
456   while(delete_kernel_list!=NULL)
457     {
458       struct destination_n *previous_node = delete_kernel_list;
459
460       assert(metric_counter);
461
462       /* searching for all the items with metric equal to n */
463       for(destination_ptr = delete_kernel_list; destination_ptr != NULL; )
464         {
465
466           if(destination_ptr->destination->rt_metric == metric_counter)
467             {
468               /* Make sure one-hop direct neighbors are deleted last */
469               if(metric_counter == 1 &&
470                  (!last_run && 
471                   COMP_IP(&destination_ptr->destination->rt_dst, 
472                           &destination_ptr->destination->rt_router)))
473                 {
474                   previous_node = destination_ptr;
475                   destination_ptr = destination_ptr->next;
476                 }
477               else
478                 {
479                   olsr_16_t error;                
480 #ifdef DEBUG
481                   OLSR_PRINTF(3, "Deleting route to %s hopcount %d\n",
482                               olsr_ip_to_string(&destination_ptr->destination->rt_dst),
483                               destination_ptr->destination->rt_metric);
484 #endif
485                     if(!olsr_cnf->host_emul)
486                       {
487                         if(olsr_cnf->ip_version == AF_INET)
488                           error = olsr_export_del_route(destination_ptr->destination);
489                         else
490                           error = olsr_export_del_route6(destination_ptr->destination);
491                         
492                         if(error < 0)
493                           {
494                             const char * const err_msg = strerror(errno);
495                             OLSR_PRINTF(1, "Delete route(%s):%s\n", olsr_ip_to_string(&destination_ptr->destination->rt_dst), err_msg);
496                             olsr_syslog(OLSR_LOG_ERR, "Delete route:%s", err_msg);
497                           }
498                     }
499                   
500                   /* Getting rid of this node and hooking up the broken point */
501                   if(destination_ptr == delete_kernel_list) 
502                     {
503                       destination_ptr = delete_kernel_list->next;
504                       free(delete_kernel_list);
505                       delete_kernel_list = destination_ptr;
506                       previous_node = delete_kernel_list;
507                     }
508                   else 
509                     {
510                       previous_node->next = destination_ptr->next;
511                       free(destination_ptr);
512                       destination_ptr = previous_node->next;
513                     }
514                 }
515             }
516           else 
517             {
518               previous_node = destination_ptr;
519               destination_ptr = destination_ptr->next;
520             }
521                 
522         }
523       if((metric_counter == 1) && !last_run)
524         {
525           last_run = OLSR_TRUE;
526         }
527       else
528         {
529           metric_counter--;
530         }
531     }
532  
533 }
534
535 /**
536  *Add a list of routes to the kernel. Adding
537  *is done by hopcount to be sure a route
538  *to the nexthop is added.
539  *
540  *@param add_kernel_list the linked list of routes to add
541  *
542  *@return nada
543  */
544 void 
545 olsr_add_routes_in_kernel(struct destination_n *add_kernel_list)
546 {
547   int metric_counter = 1;
548   olsr_bool first_run = OLSR_TRUE;
549   
550   while(add_kernel_list != NULL)
551     {
552       struct destination_n *destination_kernel = NULL;
553       struct destination_n *previous_node = add_kernel_list;
554
555       /* searching for all the items with metric equal to n */
556       for(destination_kernel = add_kernel_list; destination_kernel != NULL; )
557         {
558           if((destination_kernel->destination->rt_metric == metric_counter) &&
559              (!first_run || 
560               COMP_IP(&destination_kernel->destination->rt_dst,
561                       &destination_kernel->destination->rt_router)))
562             {
563               olsr_16_t error;
564               /* First add all 1-hop routes that has themselves as GW */
565
566 #ifdef DEBUG
567               OLSR_PRINTF(3, "Adding route to %s hopcount %d\n",
568                           olsr_ip_to_string(&destination_kernel->destination->rt_dst),
569                           destination_kernel->destination->rt_metric);
570 #endif
571                           
572                 if(!olsr_cnf->host_emul)
573                   {
574                     if(olsr_cnf->ip_version == AF_INET)
575                       error=olsr_export_add_route(destination_kernel->destination);
576                     else
577                       error=olsr_export_add_route6(destination_kernel->destination);
578                     
579                     if(error < 0)
580                       {
581                         const char * const err_msg = strerror(errno);
582                         OLSR_PRINTF(1, "Add route(%s): %s\n", olsr_ip_to_string(&destination_kernel->destination->rt_dst), err_msg);
583                         olsr_syslog(OLSR_LOG_ERR, "Add route:%s", err_msg);
584                       }
585                   }
586
587               
588               /* Getting rid of this node and hooking up the broken point */
589               if(destination_kernel == add_kernel_list) 
590                 {
591                   destination_kernel = add_kernel_list->next;
592                   free(add_kernel_list);
593                   add_kernel_list = destination_kernel;
594                   previous_node=add_kernel_list;
595                 }
596               else 
597                 {
598                   previous_node->next = destination_kernel->next;
599                   free(destination_kernel);
600                   destination_kernel = previous_node->next;
601                 }
602             }
603           else 
604             {
605               previous_node = destination_kernel;
606               destination_kernel = destination_kernel->next;
607             }
608                 
609         }
610       if(first_run)
611         {
612           first_run = OLSR_FALSE;
613         }
614       else
615         {
616           metric_counter++;
617         }
618     }
619         
620 }
621
622
623