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