0f77cbb1b2306e51e420406b120c9d307e8a03db
[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.21 2005/02/26 23:01:41 kattemat Exp $
40  */
41
42
43 #include "defs.h"
44 #include "olsr.h"
45 #include "kernel_routes.h"
46
47 #ifdef WIN32
48 #undef strerror
49 #define strerror(x) StrError(x)
50 #endif
51
52
53
54 int
55 olsr_init_old_table()
56 {
57   int index;
58
59   for(index=0;index<HASHSIZE;index++)
60     {
61       old_routes[index].next = &old_routes[index];
62       old_routes[index].prev = &old_routes[index];
63       old_hna[index].next = &old_hna[index];
64       old_hna[index].prev = &old_hna[index];
65     }
66
67   return 1;
68 }
69
70 /**
71  *Checks if there exists a route to a given host
72  *in a given hash table.
73  *
74  *@param dst the host to check for
75  *@param table the table to check
76  *
77  *@return 1 if the host exists in the table, 0 if not
78  */
79 int
80 olsr_find_up_route(struct rt_entry *dst, struct rt_entry *table)
81
82   struct rt_entry *destination;
83   olsr_u32_t      hash;
84  
85   hash = olsr_hashing(&dst->rt_dst);
86
87   for(destination = table[hash].next;
88       destination != &table[hash];
89       destination = destination->next)
90     {
91       //printf("Checking %s hc: %d ", olsr_ip_to_string(&dst->rt_dst), dst->rt_metric);
92       //printf("vs %s hc: %d ... ", olsr_ip_to_string(&destination->rt_dst), destination->rt_metric);      
93       if (COMP_IP(&destination->rt_dst, &dst->rt_dst) &&
94           COMP_IP(&destination->rt_router, &dst->rt_router) &&
95           (destination->rt_if->if_nr == dst->rt_if->if_nr))
96         {
97           if(destination->rt_metric == dst->rt_metric)
98             {
99               return 1;
100             }
101           else
102             {
103               return 0;
104             }
105         }
106     }
107
108   return 0;
109
110 }
111
112
113 /**
114  *Create a list containing the entries in in_table
115  *that does not exist in from_table
116  *
117  *@param from_table the table to use
118  *@param in_table the routes already added
119  *
120  *@return a poiter to a linked list of routes to add
121  */
122 struct destination_n *
123 olsr_build_update_list(struct rt_entry *from_table,struct rt_entry *in_table)
124 {
125   struct destination_n *kernel_route_list = NULL;
126   struct rt_entry      *destination;
127   olsr_u8_t            index;
128   
129   for(index=0;index<HASHSIZE;index++)
130     {
131       for(destination = from_table[index].next;
132           destination != &from_table[index];
133           destination = destination->next)
134         {
135           if (!olsr_find_up_route(destination, in_table))
136             {
137               struct destination_n *route_list;
138               route_list = olsr_malloc(sizeof(struct destination_n), "create route tmp list");
139               
140               route_list->destination = destination;
141               
142               route_list->next = kernel_route_list;
143               kernel_route_list = route_list;
144             }
145         }   
146     }
147   
148   return (kernel_route_list);
149 }
150
151
152
153
154
155 /**
156  *Deletes all OLSR routes
157  *
158  *
159  *@return 1
160  */
161 int
162 olsr_delete_all_kernel_routes()
163
164   struct destination_n *delete_kernel_list = NULL;
165   struct destination_n *tmp = NULL;
166   union olsr_ip_addr *tmp_addr;
167
168   OLSR_PRINTF(1, "Deleting all routes...\n")
169
170   delete_kernel_list = olsr_build_update_list(hna_routes, old_hna);
171
172   tmp = delete_kernel_list;
173
174   OLSR_PRINTF(1, "HNA list:\n")
175   while(tmp)
176     {
177       tmp_addr = &tmp->destination->rt_dst;
178       OLSR_PRINTF(1, "Dest: %s\n", olsr_ip_to_string(tmp_addr))
179       tmp = tmp->next;
180     }
181
182   olsr_delete_routes_from_kernel(delete_kernel_list);
183
184   delete_kernel_list = olsr_build_update_list(routingtable,old_routes);
185
186   tmp = delete_kernel_list;
187
188   OLSR_PRINTF(1, "Route list:\n")
189   while(tmp)
190     {
191       tmp_addr = &tmp->destination->rt_dst;
192       OLSR_PRINTF(1, "Dest: %s\n", olsr_ip_to_string(tmp_addr))
193       tmp = tmp->next;
194     }
195
196   olsr_delete_routes_from_kernel(delete_kernel_list);
197
198   return 1;
199 }
200
201
202 /**
203  *Perform all neccessary actions for an update of the 
204  *routes in the kernel.
205  *
206  *@return nada
207  */
208 void
209 olsr_update_kernel_routes()
210 {
211   struct destination_n *delete_kernel_list = NULL;
212   struct destination_n *add_kernel_list = NULL;
213   
214   OLSR_PRINTF(3, "Updating kernel routes...\n")
215   delete_kernel_list = olsr_build_update_list(old_routes, routingtable);
216   add_kernel_list = olsr_build_update_list(routingtable, old_routes);
217
218   olsr_delete_routes_from_kernel(delete_kernel_list);
219   olsr_add_routes_in_kernel(add_kernel_list);
220 }
221
222
223
224 /**
225  *Perform all neccessary actions for an update of the 
226  *HNA routes in the kernel.
227  *
228  *@return nada
229  */
230 void
231 olsr_update_kernel_hna_routes()
232 {
233   struct destination_n *delete_kernel_list = NULL;
234   //struct destination_n *delete_kernel_list2;
235   struct destination_n *add_kernel_list = NULL;
236
237   OLSR_PRINTF(3, "Updating kernel HNA routes...\n")
238
239
240   delete_kernel_list = olsr_build_update_list(old_hna, hna_routes);
241   add_kernel_list = olsr_build_update_list(hna_routes, old_hna);
242
243   olsr_delete_routes_from_kernel(delete_kernel_list);
244   olsr_add_routes_in_kernel(add_kernel_list);
245 }
246
247
248 /**
249  *Create a copy of the routing table and
250  *clear the current table
251  *
252  *@param original the table to move from
253  *@param the table to move to
254  *
255  *@return nada
256  */
257 void
258 olsr_move_route_table(struct rt_entry *original, struct rt_entry *new)
259 {
260   olsr_16_t index;
261
262   for(index=0;index<HASHSIZE;index++)
263     {
264       if(original[index].next == &original[index])
265         {
266           new[index].next = &new[index];
267           new[index].prev = &new[index];
268         }
269       else
270         {
271           /* Copy to old */
272           new[index].next = original[index].next;
273           new[index].next->prev = &new[index];
274           new[index].prev = original[index].prev;
275           new[index].prev->next = &new[index];
276
277           /* Clear original */
278           original[index].next = &original[index];
279           original[index].prev = &original[index];
280         }
281     }
282 }
283
284
285 /**
286  *Delete a linked list of routes from the kernel.
287  *
288  *@param delete_kernel_list the list to delete
289  *
290  *@return nada
291  */
292 void 
293 olsr_delete_routes_from_kernel(struct destination_n *delete_kernel_list)
294 {
295   struct destination_n *destination_ptr;
296   int metric_counter = 1;
297   olsr_bool last_run = OLSR_FALSE;
298
299   /* Find highest metric */
300   for(destination_ptr = delete_kernel_list;
301       destination_ptr != NULL;
302       destination_ptr = destination_ptr->next)
303     {
304       if(destination_ptr->destination->rt_metric > metric_counter)
305         metric_counter = destination_ptr->destination->rt_metric;
306     }
307 #ifdef DEBUG
308   OLSR_PRINTF(3, "%s highest metric %d\n",
309               __func__, metric_counter)
310 #endif
311  
312   while(delete_kernel_list!=NULL)
313     {
314       struct destination_n *previous_node = delete_kernel_list;
315
316       /* searching for all the items with metric equal to n */
317       for(destination_ptr = delete_kernel_list; destination_ptr != NULL; )
318         {
319
320           if((destination_ptr->destination->rt_metric == metric_counter) &&
321              ((last_run || 
322                !COMP_IP(&destination_ptr->destination->rt_dst, 
323                         &destination_ptr->destination->rt_router))))
324             {
325               olsr_16_t error;
326 #ifdef DEBUG
327               OLSR_PRINTF(3, "Deleting route to %s hopcount %d\n",
328                           olsr_ip_to_string(&destination_ptr->destination->rt_dst),
329                           destination_ptr->destination->rt_metric)
330 #endif
331               
332               if(olsr_cnf->ip_version == AF_INET)
333                 error = olsr_ioctl_del_route(destination_ptr->destination);
334               else
335                 error = olsr_ioctl_del_route6(destination_ptr->destination);
336               
337               if(error < 0)
338                 {
339                   OLSR_PRINTF(1, "Delete route(%s):%s\n", olsr_ip_to_string(&destination_ptr->destination->rt_dst), strerror(errno))
340                   olsr_syslog(OLSR_LOG_ERR, "Delete route:%m");
341                 }
342               
343               /* Getting rid of this node and hooking up the broken point */
344               if(destination_ptr == delete_kernel_list) 
345                 {
346                   destination_ptr = delete_kernel_list->next;
347                   free(delete_kernel_list);
348                   delete_kernel_list = destination_ptr;
349                   previous_node = delete_kernel_list;
350                 }
351               else 
352                 {
353                   previous_node->next = destination_ptr->next;
354                   free(destination_ptr);
355                   destination_ptr = previous_node->next;
356                 }
357             }
358           else 
359             {
360               previous_node = destination_ptr;
361               destination_ptr = destination_ptr->next;
362             }
363                 
364         }
365       if((metric_counter == 1) && !last_run)
366         last_run = OLSR_TRUE;
367       else
368         metric_counter--;
369       
370     }
371  
372 }
373
374 /**
375  *Add a list of routes to the kernel. Adding
376  *is done by hopcount to be sure a route
377  *to the nexthop is added.
378  *
379  *@param add_kernel_list the linked list of routes to add
380  *
381  *@return nada
382  */
383 void 
384 olsr_add_routes_in_kernel(struct destination_n *add_kernel_list)
385 {
386   int metric_counter = 1;
387   olsr_bool first_run = OLSR_TRUE;
388   
389   while(add_kernel_list != NULL)
390     {
391       struct destination_n *destination_kernel = NULL;
392       struct destination_n *previous_node = add_kernel_list;
393
394       /* searching for all the items with metric equal to n */
395       for(destination_kernel = add_kernel_list; destination_kernel != NULL; )
396         {
397           if((destination_kernel->destination->rt_metric == metric_counter) &&
398              (!first_run || 
399               COMP_IP(&destination_kernel->destination->rt_dst,
400                       &destination_kernel->destination->rt_router)))
401             {
402               olsr_16_t error;
403               /* First add all 1-hop routes that has themselves as GW */
404
405 #ifdef DEBUG
406               OLSR_PRINTF(3, "Adding route to %s hopcount %d\n",
407                           olsr_ip_to_string(&destination_kernel->destination->rt_dst),
408                           destination_kernel->destination->rt_metric)
409 #endif
410                           
411               if(olsr_cnf->ip_version == AF_INET)
412                 error=olsr_ioctl_add_route(destination_kernel->destination);
413               else
414                 error=olsr_ioctl_add_route6(destination_kernel->destination);
415               
416               if(error < 0)
417                 {
418                   OLSR_PRINTF(1, "Add route(%s): %s\n", olsr_ip_to_string(&destination_kernel->destination->rt_dst), strerror(errno))
419                   olsr_syslog(OLSR_LOG_ERR, "Add route:%m");
420                 }
421               
422               /* Getting rid of this node and hooking up the broken point */
423               if(destination_kernel == add_kernel_list) 
424                 {
425                   destination_kernel = add_kernel_list->next;
426                   free(add_kernel_list);
427                   add_kernel_list = destination_kernel;
428                   previous_node=add_kernel_list;
429                 }
430               else 
431                 {
432                   previous_node->next = destination_kernel->next;
433                   free(destination_kernel);
434                   destination_kernel = previous_node->next;
435                 }
436             }
437           else 
438             {
439               previous_node = destination_kernel;
440               destination_kernel = destination_kernel->next;
441             }
442                 
443         }
444       if(first_run)
445         first_run = OLSR_FALSE;
446       else
447         metric_counter++;
448     }
449         
450 }
451
452
453