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