* applied patches from the most recent FreiFunkFirmware (and fixed compile errors...
[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.30 2007/01/31 12:36:50 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() 
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()
215 {
216   int index;
217
218   for(index=0;index<HASHSIZE;index++)
219     {
220       old_routes[index].next = &old_routes[index];
221       old_routes[index].prev = &old_routes[index];
222       old_hna[index].next = &old_hna[index];
223       old_hna[index].prev = &old_hna[index];
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   olsr_u32_t      hash;
243  
244   hash = olsr_hashing(&dst->rt_dst);
245
246   for(destination = table[hash].next;
247       destination != &table[hash];
248       destination = destination->next)
249     {
250       //printf("Checking %s hc: %d ", olsr_ip_to_string(&dst->rt_dst), dst->rt_metric);
251       //printf("vs %s hc: %d ... ", olsr_ip_to_string(&destination->rt_dst), destination->rt_metric);      
252       if (COMP_IP(&destination->rt_dst, &dst->rt_dst) &&
253           COMP_IP(&destination->rt_router, &dst->rt_router) &&
254           (destination->rt_if->if_nr == dst->rt_if->if_nr))
255         {
256           if(destination->rt_metric == dst->rt_metric)
257             {
258               return 1;
259             }
260           else
261             {
262               return 0;
263             }
264         }
265     }
266
267   return 0;
268
269 }
270
271
272 /**
273  *Create a list containing the entries in from_table
274  *that do not exist in in_table
275  *
276  *@param from_table the table to use
277  *@param in_table the routes already added
278  *
279  *@return a poiter to a linked list of routes to add
280  */
281 struct destination_n *
282 olsr_build_update_list(struct rt_entry *from_table,struct rt_entry *in_table)
283 {
284   struct destination_n *kernel_route_list = NULL;
285   struct rt_entry      *destination;
286   olsr_u8_t            index;
287   
288   for(index=0;index<HASHSIZE;index++)
289     {
290       for(destination = from_table[index].next;
291           destination != &from_table[index];
292           destination = destination->next)
293         {
294           if (!olsr_find_up_route(destination, in_table))
295             {
296               struct destination_n *route_list;
297               route_list = olsr_malloc(sizeof(struct destination_n), "create route tmp list");
298               
299               route_list->destination = destination;
300               
301               route_list->next = kernel_route_list;
302               kernel_route_list = route_list;
303             }
304         }   
305     }
306   
307   return (kernel_route_list);
308 }
309
310
311
312
313
314 /**
315  *Deletes all OLSR routes
316  *
317  *
318  *@return 1
319  */
320 int
321 olsr_delete_all_kernel_routes()
322
323   struct destination_n *delete_kernel_list = NULL;
324   struct destination_n *tmp = NULL;
325   union olsr_ip_addr *tmp_addr;
326
327   OLSR_PRINTF(1, "Deleting all routes...\n")
328
329   delete_kernel_list = olsr_build_update_list(hna_routes, old_hna);
330
331   tmp = delete_kernel_list;
332
333   OLSR_PRINTF(1, "HNA list:\n")
334   while(tmp)
335     {
336       tmp_addr = &tmp->destination->rt_dst;
337       OLSR_PRINTF(1, "Dest: %s\n", olsr_ip_to_string(tmp_addr))
338       tmp = tmp->next;
339     }
340
341   olsr_delete_routes_from_kernel(delete_kernel_list);
342
343   delete_kernel_list = olsr_build_update_list(routingtable,old_routes);
344
345   tmp = delete_kernel_list;
346
347   OLSR_PRINTF(1, "Route list:\n")
348   while(tmp)
349     {
350       tmp_addr = &tmp->destination->rt_dst;
351       OLSR_PRINTF(1, "Dest: %s\n", olsr_ip_to_string(tmp_addr))
352       tmp = tmp->next;
353     }
354
355   olsr_delete_routes_from_kernel(delete_kernel_list);
356
357   return 1;
358 }
359
360
361 /**
362  *Perform all neccessary actions for an update of the 
363  *routes in the kernel.
364  *
365  *@return nada
366  */
367 void
368 olsr_update_kernel_routes()
369 {
370   struct destination_n *delete_kernel_list = NULL;
371   struct destination_n *add_kernel_list = NULL;
372
373   OLSR_PRINTF(3, "Updating kernel routes...\n")
374   delete_kernel_list = olsr_build_update_list(old_routes, routingtable);
375   add_kernel_list = olsr_build_update_list(routingtable, old_routes);
376
377   olsr_delete_routes_from_kernel(delete_kernel_list);
378   olsr_add_routes_in_kernel(add_kernel_list);
379 }
380
381
382
383 /**
384  *Perform all neccessary actions for an update of the 
385  *HNA routes in the kernel.
386  *
387  *@return nada
388  */
389 void
390 olsr_update_kernel_hna_routes()
391 {
392   struct destination_n *delete_kernel_list = NULL;
393   //struct destination_n *delete_kernel_list2;
394   struct destination_n *add_kernel_list = NULL;
395
396   OLSR_PRINTF(3, "Updating kernel HNA routes...\n")
397
398
399   delete_kernel_list = olsr_build_update_list(old_hna, hna_routes);
400   add_kernel_list = olsr_build_update_list(hna_routes, old_hna);
401
402   olsr_delete_routes_from_kernel(delete_kernel_list);
403   olsr_add_routes_in_kernel(add_kernel_list);
404 }
405
406
407 /**
408  *Create a copy of the routing table and
409  *clear the current table
410  *
411  *@param original the table to move from
412  *@param the table to move to
413  *
414  *@return nada
415  */
416 void
417 olsr_move_route_table(struct rt_entry *original, struct rt_entry *new)
418 {
419   olsr_16_t index;
420
421   for(index=0;index<HASHSIZE;index++)
422     {
423       if(original[index].next == &original[index])
424         {
425           new[index].next = &new[index];
426           new[index].prev = &new[index];
427         }
428       else
429         {
430           /* Copy to old */
431           new[index].next = original[index].next;
432           new[index].next->prev = &new[index];
433           new[index].prev = original[index].prev;
434           new[index].prev->next = &new[index];
435
436           /* Clear original */
437           original[index].next = &original[index];
438           original[index].prev = &original[index];
439         }
440     }
441 }
442
443
444 /**
445  *Delete a linked list of routes from the kernel.
446  *
447  *@param delete_kernel_list the list to delete
448  *
449  *@return nada
450  */
451 void 
452 olsr_delete_routes_from_kernel(struct destination_n *delete_kernel_list)
453 {
454   struct destination_n *destination_ptr;
455   int metric_counter = 1;
456   olsr_bool last_run = OLSR_FALSE;
457
458
459   /* Find highest metric */
460   for(destination_ptr = delete_kernel_list;
461       destination_ptr != NULL;
462       destination_ptr = destination_ptr->next)
463     {
464       if(destination_ptr->destination->rt_metric > metric_counter)
465         metric_counter = destination_ptr->destination->rt_metric;
466     }
467
468 #ifdef DEBUG
469   OLSR_PRINTF(3, "%s highest metric %d\n",
470               __func__, metric_counter)
471 #endif
472  
473   while(delete_kernel_list!=NULL)
474     {
475       struct destination_n *previous_node = delete_kernel_list;
476
477       assert(metric_counter);
478
479       /* searching for all the items with metric equal to n */
480       for(destination_ptr = delete_kernel_list; destination_ptr != NULL; )
481         {
482
483           if(destination_ptr->destination->rt_metric == metric_counter)
484             {
485               /* Make sure one-hop direct neighbors are deleted last */
486               if(metric_counter == 1 &&
487                  (!last_run && 
488                   COMP_IP(&destination_ptr->destination->rt_dst, 
489                           &destination_ptr->destination->rt_router)))
490                 {
491                   previous_node = destination_ptr;
492                   destination_ptr = destination_ptr->next;
493                 }
494               else
495                 {
496                   olsr_16_t error;                
497 #ifdef DEBUG
498                   OLSR_PRINTF(3, "Deleting route to %s hopcount %d\n",
499                               olsr_ip_to_string(&destination_ptr->destination->rt_dst),
500                               destination_ptr->destination->rt_metric)
501 #endif
502                     if(!olsr_cnf->host_emul)
503                       {
504                         if(olsr_cnf->ip_version == AF_INET)
505                           error = olsr_export_del_route(destination_ptr->destination);
506                         else
507                           error = olsr_export_del_route6(destination_ptr->destination);
508                         
509                         if(error < 0)
510                           {
511                             OLSR_PRINTF(1, "Delete route(%s):%s\n", olsr_ip_to_string(&destination_ptr->destination->rt_dst), strerror(errno))
512                               olsr_syslog(OLSR_LOG_ERR, "Delete route:%m");
513                           }
514                     }
515                   
516                   /* Getting rid of this node and hooking up the broken point */
517                   if(destination_ptr == delete_kernel_list) 
518                     {
519                       destination_ptr = delete_kernel_list->next;
520                       free(delete_kernel_list);
521                       delete_kernel_list = destination_ptr;
522                       previous_node = delete_kernel_list;
523                     }
524                   else 
525                     {
526                       previous_node->next = destination_ptr->next;
527                       free(destination_ptr);
528                       destination_ptr = previous_node->next;
529                     }
530                 }
531             }
532           else 
533             {
534               previous_node = destination_ptr;
535               destination_ptr = destination_ptr->next;
536             }
537                 
538         }
539       if((metric_counter == 1) && !last_run)
540         {
541           last_run = OLSR_TRUE;
542         }
543       else
544         {
545           metric_counter--;
546         }
547     }
548  
549 }
550
551 /**
552  *Add a list of routes to the kernel. Adding
553  *is done by hopcount to be sure a route
554  *to the nexthop is added.
555  *
556  *@param add_kernel_list the linked list of routes to add
557  *
558  *@return nada
559  */
560 void 
561 olsr_add_routes_in_kernel(struct destination_n *add_kernel_list)
562 {
563   int metric_counter = 1;
564   olsr_bool first_run = OLSR_TRUE;
565   
566   while(add_kernel_list != NULL)
567     {
568       struct destination_n *destination_kernel = NULL;
569       struct destination_n *previous_node = add_kernel_list;
570
571       /* searching for all the items with metric equal to n */
572       for(destination_kernel = add_kernel_list; destination_kernel != NULL; )
573         {
574           if((destination_kernel->destination->rt_metric == metric_counter) &&
575              (!first_run || 
576               COMP_IP(&destination_kernel->destination->rt_dst,
577                       &destination_kernel->destination->rt_router)))
578             {
579               olsr_16_t error;
580               /* First add all 1-hop routes that has themselves as GW */
581
582 #ifdef DEBUG
583               OLSR_PRINTF(3, "Adding route to %s hopcount %d\n",
584                           olsr_ip_to_string(&destination_kernel->destination->rt_dst),
585                           destination_kernel->destination->rt_metric)
586 #endif
587                           
588                 if(!olsr_cnf->host_emul)
589                   {
590                     if(olsr_cnf->ip_version == AF_INET)
591                       error=olsr_export_add_route(destination_kernel->destination);
592                     else
593                       error=olsr_export_add_route6(destination_kernel->destination);
594                     
595                     if(error < 0)
596                       {
597                         OLSR_PRINTF(1, "Add route(%s): %s\n", olsr_ip_to_string(&destination_kernel->destination->rt_dst), strerror(errno))
598                           olsr_syslog(OLSR_LOG_ERR, "Add route:%m");
599                       }
600                   }
601
602               
603               /* Getting rid of this node and hooking up the broken point */
604               if(destination_kernel == add_kernel_list) 
605                 {
606                   destination_kernel = add_kernel_list->next;
607                   free(add_kernel_list);
608                   add_kernel_list = destination_kernel;
609                   previous_node=add_kernel_list;
610                 }
611               else 
612                 {
613                   previous_node->next = destination_kernel->next;
614                   free(destination_kernel);
615                   destination_kernel = previous_node->next;
616                 }
617             }
618           else 
619             {
620               previous_node = destination_kernel;
621               destination_kernel = destination_kernel->next;
622             }
623                 
624         }
625       if(first_run)
626         {
627           first_run = OLSR_FALSE;
628         }
629       else
630         {
631           metric_counter++;
632         }
633     }
634         
635 }
636
637
638