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