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