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