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