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