New configfile parser and configuration scheme integrated
[olsrd.git] / src / routing_table.c
1 /*
2  * OLSR ad-hoc routing table management protocol
3  * Copyright (C) 2004 Andreas T√łnnesen (andreto@ifi.uio.no)
4  *
5  * This file is part of the olsr.org OLSR daemon.
6  *
7  * olsr.org is free software; you can redistribute it and/or modify
8  * it under the terms of the GNU General Public License as published by
9  * the Free Software Foundation; either version 2 of the License, or
10  * (at your option) any later version.
11  *
12  * olsr.org is distributed in the hope that it will be useful,
13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with olsr.org; if not, write to the Free Software
19  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
20  * 
21  * 
22  * $Id: routing_table.c,v 1.8 2004/10/18 13:13:37 kattemat Exp $
23  *
24  */
25
26
27
28 #include "defs.h"
29 #include "two_hop_neighbor_table.h"
30 #include "tc_set.h"
31 #include "mid_set.h"
32 #include "mpr.h"
33 #include "olsr.h"
34 #include "link_set.h"
35
36
37 /* Begin:
38  * Prototypes for internal functions 
39  */
40
41 static void
42 olsr_free_routing_table(struct rt_entry *);
43
44 static int
45 olsr_fill_routing_table_with_neighbors(void);
46
47 static struct destination_n *
48 olsr_fill_routing_table_with_two_hop_neighbors(void);
49
50 static struct rt_entry *
51 olsr_check_for_higher_hopcount(struct rt_entry *, struct hna_net *, olsr_u16_t);
52
53 static struct rt_entry *
54 olsr_lookup_routing_table(union olsr_ip_addr *);
55
56 struct rt_entry *
57 olsr_insert_routing_table(union olsr_ip_addr *, union olsr_ip_addr *, int);
58
59 struct rt_entry *
60 olsr_check_for_lower_hopcount(struct rt_entry *, struct hna_net *, olsr_u16_t);
61
62 /* End:
63  * Prototypes for internal functions 
64  */
65
66
67 /**
68  *Initialize the routing table
69  */
70 int
71 olsr_init_routing_table()
72 {
73   int index;
74
75   /*
76    *The hna routes hash will almost always
77    *be indexed to 0
78    *But it is kept as a hash to be compatible
79    *with the functions used on the regular
80    *routing table
81    */
82   for(index=0;index<HASHSIZE;index++)
83     {
84       routingtable[index].next = &routingtable[index];
85       routingtable[index].prev = &routingtable[index];
86       hna_routes[index].next = &hna_routes[index];
87       hna_routes[index].prev = &hna_routes[index];
88     }
89   return 1;
90 }
91
92 /**
93  *Look up an entry in the routing table.
94  *
95  *@param dst the address of the entry
96  *
97  *@return a pointer to a rt_entry struct 
98  *representing the route entry.
99  */
100 static struct rt_entry *
101 olsr_lookup_routing_table(union olsr_ip_addr *dst)
102 {
103
104   struct rt_entry *rt_table;
105   olsr_u32_t      hash;
106
107   hash = olsr_hashing(dst);
108
109   for(rt_table = routingtable[hash].next;
110       rt_table != &routingtable[hash];
111       rt_table = rt_table->next)
112     {
113       if (COMP_IP(&rt_table->rt_dst, dst))
114         {
115           return(rt_table);
116         }
117     }
118   return(NULL);
119   
120 }
121
122
123
124
125 /**
126  *Delete all the entries in the routing table hash
127  *
128  *@param table the routing hash table
129  *
130  *@return nada
131  */
132 static void
133 olsr_free_routing_table(struct rt_entry *table)
134 {
135   struct rt_entry *destination;
136   struct rt_entry *dst_to_delete;
137   olsr_u8_t       index;
138   
139
140   for(index=0;index<HASHSIZE;index++)
141     {
142       destination = table[index].next;
143
144       while(destination != &table[index])
145         {
146           dst_to_delete = destination;
147           destination = destination->next;
148
149           dst_to_delete->next->prev = dst_to_delete->prev;
150           dst_to_delete->prev->next = dst_to_delete->next;
151
152           free(dst_to_delete);
153         }
154     }
155
156 }
157
158
159 /**
160  *Insert an 1 or 2 neighbor-entry into the routing table.
161  *
162  *@param dst the destination
163  *
164  *@return the new rt_entry struct
165  */
166 struct rt_entry *
167 olsr_insert_routing_table(union olsr_ip_addr *dst, union olsr_ip_addr *router, int metric)
168 {
169   struct rt_entry *new_route_entry, *rt_list;
170   olsr_u32_t       hash;
171
172   hash = olsr_hashing(dst);
173   rt_list = &routingtable[hash];
174
175   new_route_entry = olsr_malloc(sizeof(struct rt_entry), "Insert routing table");
176
177   COPY_IP(&new_route_entry->rt_dst, dst);
178   COPY_IP(&new_route_entry->rt_router, router);
179
180   new_route_entry->rt_metric = metric;
181   if(COMP_IP(dst, router))
182     /* Not GW */
183     new_route_entry->rt_flags = (RTF_UP|RTF_HOST);
184   else
185     new_route_entry->rt_flags = (RTF_UP|RTF_HOST|RTF_GATEWAY);
186
187   if(olsr_cnf->ip_version == AF_INET)
188     /* IPv4 */
189     new_route_entry->rt_mask.v4 = NETMASK_HOST;
190   else
191     /* IPv6 */
192     new_route_entry->rt_mask.v6 = 128;
193
194   /* Find interface */
195   if((new_route_entry->rt_if = get_interface_link_set(router)) == NULL)
196     {
197       fprintf(stderr, "ADD ROUTE 1: %s Could not find neighbor interface ", 
198               olsr_ip_to_string(dst));
199       fprintf(stderr, "for %s!!\n", 
200               olsr_ip_to_string(router));
201       free(new_route_entry);
202       return NULL;
203     }
204   
205
206   /* queue */
207   rt_list->next->prev = new_route_entry;
208   new_route_entry->next = rt_list->next;
209   rt_list->next = new_route_entry;
210   new_route_entry->prev = rt_list;
211   
212   return(new_route_entry);
213 }
214
215
216
217 /**
218  *Insert all the one hop neighbors in the routing table.
219  *
220  *@return a pointer to a destination_n linked-list of the neighbors.
221  */
222 static int
223 olsr_fill_routing_table_with_neighbors()
224 {
225   olsr_u8_t              index;
226   struct neighbor_entry  *neighbor;
227   struct rt_entry        *new_route_entry=NULL;
228
229   struct addresses *addrs=NULL, *addrs2;
230
231 #ifdef DEBUG
232   olsr_printf(7, "FILL ROUTING TABLE WITH NEIGHBORS\n");
233 #endif
234
235   for(index=0;index<HASHSIZE;index++)
236     {
237       for(neighbor = neighbortable[index].next;
238           neighbor != &neighbortable[index];
239           neighbor=neighbor->next)     
240         {
241
242           if(neighbor->status == SYM)
243             {
244               /*
245                *Insert all the neighbors addresses
246                */
247               addrs = olsr_malloc(sizeof(struct addresses), "Fill routing table with neighbors");
248
249               COPY_IP(&addrs->address, &neighbor->neighbor_main_addr);
250               addrs->next = mid_lookup_aliases(&neighbor->neighbor_main_addr);
251               addrs2 = addrs;
252
253               while(addrs!=NULL)
254                 {
255 #ifdef DEBUG
256                   olsr_printf(7, "(ROUTE)Adding neighbor %s\n", olsr_ip_to_string(&addrs->address));
257 #endif
258                   /* New in 0.4.6 */
259                   new_route_entry = olsr_insert_routing_table(&addrs->address, get_neighbor_nexthop(&addrs->address), 1);
260               
261                   addrs = addrs->next;
262                 }
263               free(addrs2);
264             }
265         }
266     }
267
268
269   return 1;
270 }
271
272
273 /**
274  *Insert all the two hop neighbors that is not already added
275  *in the routing table.
276  *
277  *@return a pointer to a destination_n linked-list of the neighbors.
278  */
279
280 static struct destination_n *
281 olsr_fill_routing_table_with_two_hop_neighbors()
282 {
283   struct destination_n         *list_destination_n=NULL;
284   struct destination_n         *list_destination_tmp=NULL;
285   olsr_u8_t                    index;
286   struct neighbor_entry        *neighbor;
287   struct rt_entry              *new_route_entry=NULL;
288   struct neighbor_2_list_entry *neigh_2_list; 
289   union olsr_ip_addr           *n2_addr;
290   struct addresses *addrs=NULL, *addrs2;
291   struct neighbor_list_entry   *neighbors;
292   int                          neighbor_ok;
293
294   //printf("FILL ROUTING TABLE WITH TWO HOP NEIGHBORS\n");
295
296   for(index=0;index<HASHSIZE;index++)
297     {
298       for(neighbor = neighbortable[index].next;
299           neighbor != &neighbortable[index];
300           neighbor=neighbor->next)     
301         {
302           
303           if(neighbor->status != SYM)
304             continue;
305           
306           /*
307            *Insert all the two hop neighbors
308            */
309           for(neigh_2_list = neighbor->neighbor_2_list.next;
310               neigh_2_list != &neighbor->neighbor_2_list;
311               neigh_2_list = neigh_2_list->next)
312             {
313               
314               n2_addr = &neigh_2_list->neighbor_2->neighbor_2_addr;
315               
316               if(olsr_lookup_routing_table(n2_addr))
317                 {
318 #ifdef DEBUG
319                   olsr_printf(7, "2hop: %s already added\n", olsr_ip_to_string(n2_addr));
320 #endif
321                   continue;
322                 }           
323
324               /*
325                * Neighbor is only added if avalible trough
326                * a 1 hop neighbor with willingness != WILL_NEVER
327                */
328               neighbor_ok = 0;
329
330               for(neighbors = neigh_2_list->neighbor_2->neighbor_2_nblist.next;
331                   neighbors != &neigh_2_list->neighbor_2->neighbor_2_nblist;
332                   neighbors = neighbors->next)
333                 {
334                   if((neighbors->neighbor->status != NOT_NEIGH) &&
335                      (neighbors->neighbor->willingness != WILL_NEVER))
336                     neighbor_ok = 1;
337                 }
338
339               if(!neighbor_ok)
340                 {
341                   olsr_printf(1, "Two hop neighbor %s not added - no one hop neighbors.\n",
342                               olsr_ip_to_string(n2_addr));
343                   continue;
344                 }
345
346               addrs = olsr_malloc(sizeof(struct addresses), "Fill rt table 2 hop neighbors");
347               
348               COPY_IP(&addrs->address, n2_addr);
349               addrs->next = mid_lookup_aliases(n2_addr);
350               addrs2 = addrs;
351
352               while(addrs!=NULL)
353                 {
354 #ifdef DEBUG
355                   olsr_printf(7, "(ROUTE)Adding neighbor %s\n", olsr_ip_to_string(&addrs->address));
356 #endif
357                   /* New in 0.4.6 */
358                   new_route_entry = olsr_insert_routing_table(&addrs->address, get_neighbor_nexthop(&neighbor->neighbor_main_addr), 2);
359
360                   if(new_route_entry != NULL)
361                     {
362                       list_destination_tmp = olsr_malloc(sizeof(struct destination_n), "Fill rt table 2 hop tmp");
363                       
364                       list_destination_tmp->destination = new_route_entry;
365                       list_destination_tmp->next = list_destination_n;
366                       list_destination_n = list_destination_tmp;
367                     }
368                   addrs = addrs->next; 
369                 }
370               free(addrs2);
371             }
372         }
373
374     }
375
376   return(list_destination_n);
377 }
378
379
380
381
382 /**
383  *Recalculate the routing table
384  *
385  *@return nada
386  */
387 void 
388 olsr_calculate_routing_table()
389
390 {
391   struct destination_n               *list_destination_n=NULL;
392   struct destination_n               *list_destination_n_1=NULL;
393   struct destination_n               *destination_n_1=NULL;
394   //struct topology_last_entry         *topo_last;
395   struct tc_entry                    *topo_entry;
396   struct topo_dst                    *topo_dest;
397   struct addresses                   *tmp_addrs, *tmp2_addrs;
398   int                                add_dest;
399
400   olsr_move_route_table(routingtable, old_routes);
401
402
403   /* Add neighbors */
404   olsr_fill_routing_table_with_neighbors();
405   /* Add two hop enighbors - now they are the "outer rim" */
406   list_destination_n_1 = olsr_fill_routing_table_with_two_hop_neighbors();
407
408   /* List_destination_n_1 holds the "outer rim" */
409   list_destination_n = list_destination_n_1;
410
411   while(list_destination_n_1!=NULL)
412     {
413       list_destination_n_1=NULL;
414
415       /* Next "outer rim" */
416       while(list_destination_n!=NULL)
417         {
418           if((topo_entry = olsr_lookup_tc_entry(&list_destination_n->destination->rt_dst)) != NULL)
419             {
420               topo_dest = topo_entry->destinations.next;
421
422               /* Loop trough this nodes MPR selectors */
423               while(topo_dest != &topo_entry->destinations)
424                 {
425                   /* Check if dest is ourselves!! */
426                   add_dest = 1;
427                   
428                   /* Do not add ourselves */
429                   if(if_ifwithaddr(&topo_dest->T_dest_addr))
430                     {
431                       topo_dest=topo_dest->next;
432                       continue;
433                     }
434                   
435                   /* Find mid nodes */
436                   tmp_addrs = olsr_malloc(sizeof(struct addresses), "Calculate routing table MID");
437                   
438                   COPY_IP(&tmp_addrs->address, &topo_dest->T_dest_addr);
439                   tmp_addrs->next = mid_lookup_aliases(&topo_dest->T_dest_addr);
440                   tmp2_addrs = tmp_addrs;
441                   
442                   while(tmp_addrs!=NULL)
443                     {
444                       if(NULL==olsr_lookup_routing_table(&tmp_addrs->address))
445                         {
446                           /* PRINT OUT: Last Hop to Final Destination */
447                           /* The function ip_to_string has to be seperately */
448                           olsr_printf(3, "%s -> ", olsr_ip_to_string(&list_destination_n->destination->rt_dst));
449                           olsr_printf(3, "%s\n", olsr_ip_to_string(&tmp_addrs->address) );
450                           
451                           destination_n_1 = olsr_malloc(sizeof(struct destination_n), "Calculate routing table 2");
452                           
453                           /* Add this entry to the "outer rim" */
454                           destination_n_1->destination = 
455                             olsr_insert_routing_table(&tmp_addrs->address, 
456                                                       &list_destination_n->destination->rt_router, 
457                                                       list_destination_n->destination->rt_metric+1);
458                           if(destination_n_1->destination != NULL)
459                             {
460                               destination_n_1->next=list_destination_n_1;
461                               list_destination_n_1=destination_n_1;
462                             }
463                         }
464                       tmp_addrs = tmp_addrs->next;
465                     }
466                   free(tmp2_addrs);
467                   
468                   /* Next MPR selector */
469                   topo_dest=topo_dest->next;
470                   
471                 } /* End loop trought MPR selectors */
472               
473             } /* End check if already added */
474           
475           /* Delete this entry - do next */ 
476           destination_n_1=list_destination_n;
477           list_destination_n=list_destination_n->next;
478           free(destination_n_1);
479           
480         }
481
482       /* New "outer rim" */
483       list_destination_n=list_destination_n_1;
484     }
485
486
487   if(olsr_cnf->debug_level > 5)
488     {
489       printf("************** TABLES ****************\n");
490       printf("Routing table:\n");
491       olsr_print_routing_table(routingtable);
492       printf("Old table:\n");
493       olsr_print_routing_table(old_routes);
494       printf("**************************************\n");
495     }
496
497   
498   /* Update routes */
499   olsr_update_kernel_routes();
500
501   olsr_free_routing_table(old_routes);
502 }
503
504
505
506
507 /**
508  *Check for a entry with a higher hopcount than
509  *a given value in a routing table
510  *
511  *@param routes the routingtable to look in
512  *@param net the network entry to look for
513  *@param metric the metric to check for
514  *
515  *@return the localted entry if found. NULL if not
516  */
517 static struct rt_entry *
518 olsr_check_for_higher_hopcount(struct rt_entry *routes, struct hna_net *net, olsr_u16_t metric)
519 {
520   int index;
521   struct rt_entry *tmp_routes;
522
523   for(index=0;index<HASHSIZE;index++)
524     {
525       /* All entries */
526       for(tmp_routes = routes[index].next;
527           tmp_routes != &routes[index];
528           tmp_routes = tmp_routes->next)
529         {
530           if(COMP_IP(&tmp_routes->rt_dst, &net->A_network_addr) &&
531              (memcmp(&tmp_routes->rt_mask, &net->A_netmask, netmask_size) == 0))
532             {
533               /* Found a entry */
534               if(tmp_routes->rt_metric > metric)
535                 return tmp_routes;
536               else
537                 return NULL;
538             }
539         }
540     }
541
542   return NULL;
543 }
544
545
546
547 /**
548  *Check for a entry with a lower or equal hopcount than
549  *a given value in a routing table
550  *
551  *@param routes the routingtable to look in
552  *@param net the network entry to look for
553  *@param metric the metric to check for
554  *
555  *@return the localted entry if found. NULL if not
556  */
557 struct rt_entry *
558 olsr_check_for_lower_hopcount(struct rt_entry *routes, struct hna_net *net, olsr_u16_t metric)
559 {
560   int index;
561   struct rt_entry *tmp_routes;
562
563   for(index=0;index<HASHSIZE;index++)
564     {
565       /* All entries */
566       for(tmp_routes = routes[index].next;
567           tmp_routes != &routes[index];
568           tmp_routes = tmp_routes->next)
569         {
570           if(COMP_IP(&tmp_routes->rt_dst, &net->A_network_addr) &&
571              (memcmp(&tmp_routes->rt_mask, &net->A_netmask, netmask_size) == 0))
572             {
573               /* Found a entry */
574               if(tmp_routes->rt_metric <= metric)
575                 return tmp_routes;
576               else
577                 return NULL;
578             }
579         }
580     }
581
582
583
584   return NULL;
585 }
586
587
588
589
590 /**
591  *Calculate the HNA routes
592  *
593  */
594 void
595 olsr_calculate_hna_routes()
596 {
597   olsr_u32_t index, hna_hash;
598   struct hna_entry *tmp_hna;
599   struct hna_net *tmp_net;
600   struct rt_entry *tmp_rt, *new_rt;
601
602 #ifdef DEBUG
603   olsr_printf(3, "Calculating HNA routes\n");
604 #endif
605
606   olsr_move_route_table(hna_routes, old_hna);
607
608   
609   for(index=0;index<HASHSIZE;index++)
610     {
611       /* All entries */
612       for(tmp_hna = hna_set[index].next;
613           tmp_hna != &hna_set[index];
614           tmp_hna = tmp_hna->next)
615         {
616
617           /* All networks */
618           for(tmp_net = tmp_hna->networks.next;
619               tmp_net != &tmp_hna->networks;
620               tmp_net = tmp_net->next)
621             {
622               //printf("HNA: checking %s -> ", olsr_ip_to_string(&tmp_hna->A_gateway_addr));
623               //printf("%s", olsr_ip_to_string(&tmp_net->A_network_addr));
624
625               /* If no route to gateway - skip */
626               if((tmp_rt = olsr_lookup_routing_table(&tmp_hna->A_gateway_addr)) == NULL)
627                 {
628                   continue;
629                 }
630
631               /* If there exists a better or equal entry - skip */
632               if(olsr_check_for_lower_hopcount(hna_routes, tmp_net, tmp_rt->rt_metric) != NULL)
633                 {
634                   continue;
635                 }
636
637               /* If we find an entry with higher hopcount we just edit it */
638               if((new_rt = olsr_check_for_higher_hopcount(hna_routes, tmp_net, tmp_rt->rt_metric)) != NULL)
639                 {
640                   /* Fill struct */
641                   /* Net */
642                   COPY_IP(&new_rt->rt_dst, &tmp_net->A_network_addr);
643                   memcpy(&new_rt->rt_mask, &tmp_net->A_netmask, netmask_size);
644                   /* Gateway */
645                   COPY_IP(&new_rt->rt_router, &tmp_rt->rt_router);
646                   /* Metric */
647                   new_rt->rt_metric = tmp_rt->rt_metric;
648                   /* Flags */
649                   new_rt->rt_flags = RTF_UP | RTF_GATEWAY;
650
651                 }
652               /* If not - create a new one */
653               else
654                 {
655                   new_rt = olsr_malloc(sizeof(struct rt_entry), "New rt entry");
656
657                   /* Fill struct */
658                   /* Net */
659                   COPY_IP(&new_rt->rt_dst, &tmp_net->A_network_addr);
660                   memcpy(&new_rt->rt_mask, &tmp_net->A_netmask, netmask_size);
661                   /* Gateway */
662                   COPY_IP(&new_rt->rt_router, &tmp_rt->rt_router);
663                   /* Metric */
664                   new_rt->rt_metric = tmp_rt->rt_metric;
665                   /* Flags */
666                   new_rt->rt_flags = RTF_UP | RTF_GATEWAY;
667               
668                   /* Find interface */
669                   if((new_rt->rt_if = get_interface_link_set(&new_rt->rt_router)) == NULL)
670                     {
671                       fprintf(stderr, "ADD ROUTE 2: %s Could not find neighbor interface!!!\n", 
672                               olsr_ip_to_string(&new_rt->rt_dst));
673                       /* This hopefullt never happens */
674                       free(new_rt);
675                     }
676                   else
677                     {
678                       /* Queue HASH will almost always be 0 */
679                       hna_hash = olsr_hashing(&tmp_net->A_network_addr);
680                       hna_routes[hna_hash].next->prev = new_rt;
681                       new_rt->next = hna_routes[hna_hash].next;
682                       hna_routes[hna_hash].next = new_rt;
683                       new_rt->prev = &hna_routes[hna_hash];
684                     }
685                 }
686             }
687         }
688     }
689
690   /* Update kernel */
691   olsr_update_kernel_hna_routes();
692
693   if(olsr_cnf->debug_level > 2)
694     {
695       olsr_printf(3, "HNA table:\n");
696       olsr_print_routing_table(hna_routes);
697     }
698
699   olsr_free_routing_table(old_hna);
700
701 }
702
703
704
705
706
707 /**
708  *Print the routingtable to STDOUT
709  *
710  */
711
712 void
713 olsr_print_routing_table(struct rt_entry *table)
714 {
715
716   struct rt_entry     *destination;
717   olsr_u8_t           index;
718
719   printf("ROUTING TABLE\n");
720   printf("DESTINATION\tNEXT HOP\n");
721   for(index=0;index<HASHSIZE;index++)
722     {
723       for(destination = table[index].next;
724           destination != &table[index];
725           destination = destination->next)
726         {
727           printf("%s\t", olsr_ip_to_string(&destination->rt_dst));
728           printf("%s\n", olsr_ip_to_string(&destination->rt_router));
729         }
730     }
731   fflush(stdout);
732 }
733
734
735
736
737