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