2 * The olsr.org Optimized Link-State Routing daemon(olsrd)
3 * Copyright (c) 2004, Andreas Tønnesen(andreto@olsr.org)
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
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
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.
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.
33 * Visit http://www.olsr.org for more information.
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.
39 * $Id: routing_table.c,v 1.12 2005/01/17 20:18:22 kattemat Exp $
45 #include "two_hop_neighbor_table.h"
54 * Prototypes for internal functions
58 olsr_fill_routing_table_with_neighbors(void);
60 static struct destination_n *
61 olsr_fill_routing_table_with_two_hop_neighbors(void);
63 static struct rt_entry *
64 olsr_check_for_higher_hopcount(struct rt_entry *, struct hna_net *, olsr_u16_t);
66 static struct rt_entry *
67 olsr_lookup_routing_table(union olsr_ip_addr *);
70 olsr_check_for_lower_hopcount(struct rt_entry *, struct hna_net *, olsr_u16_t);
73 * Prototypes for internal functions
78 *Initialize the routing table
81 olsr_init_routing_table()
86 *The hna routes hash will almost always
88 *But it is kept as a hash to be compatible
89 *with the functions used on the regular
92 for(index=0;index<HASHSIZE;index++)
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];
103 *Look up an entry in the routing table.
105 *@param dst the address of the entry
107 *@return a pointer to a rt_entry struct
108 *representing the route entry.
110 static struct rt_entry *
111 olsr_lookup_routing_table(union olsr_ip_addr *dst)
114 struct rt_entry *rt_table;
117 hash = olsr_hashing(dst);
119 for(rt_table = routingtable[hash].next;
120 rt_table != &routingtable[hash];
121 rt_table = rt_table->next)
123 if (COMP_IP(&rt_table->rt_dst, dst))
136 *Delete all the entries in the routing table hash
138 *@param table the routing hash table
143 olsr_free_routing_table(struct rt_entry *table)
147 for(index=0;index<HASHSIZE;index++)
149 struct rt_entry *destination = table[index].next;
151 while(destination != &table[index])
153 struct rt_entry *dst_to_delete = destination;
154 destination = destination->next;
156 DEQUEUE_ELEM(dst_to_delete);
165 *Insert an 1 or 2 neighbor-entry into the routing table.
167 *@param dst the destination
169 *@return the new rt_entry struct
172 olsr_insert_routing_table(union olsr_ip_addr *dst, union olsr_ip_addr *router, int metric)
174 struct rt_entry *new_route_entry, *rt_list;
177 hash = olsr_hashing(dst);
178 rt_list = &routingtable[hash];
180 new_route_entry = olsr_malloc(sizeof(struct rt_entry), "Insert routing table");
182 COPY_IP(&new_route_entry->rt_dst, dst);
183 COPY_IP(&new_route_entry->rt_router, router);
185 new_route_entry->rt_metric = metric;
186 if(COMP_IP(dst, router))
188 new_route_entry->rt_flags = (RTF_UP|RTF_HOST);
190 new_route_entry->rt_flags = (RTF_UP|RTF_HOST|RTF_GATEWAY);
192 if(olsr_cnf->ip_version == AF_INET)
194 new_route_entry->rt_mask.v4 = NETMASK_HOST;
197 new_route_entry->rt_mask.v6 = 128;
200 if((new_route_entry->rt_if = get_interface_link_set(router)) == NULL)
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);
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;
217 return(new_route_entry);
223 *Insert all the one hop neighbors in the routing table.
228 olsr_fill_routing_table_with_neighbors()
231 struct rt_entry *new_route_entry=NULL;
234 olsr_printf(7, "FILL ROUTING TABLE WITH NEIGHBORS\n");
237 for(index=0;index<HASHSIZE;index++)
239 struct neighbor_entry *neighbor;
241 for(neighbor = neighbortable[index].next;
242 neighbor != &neighbortable[index];
243 neighbor=neighbor->next)
246 if(neighbor->status == SYM)
248 static struct addresses addrs;
249 struct addresses *addrs2;
252 *Insert all the neighbors addresses
255 COPY_IP(&addrs.address, &neighbor->neighbor_main_addr);
256 addrs.next = mid_lookup_aliases(&neighbor->neighbor_main_addr);
262 olsr_printf(7, "(ROUTE)Adding neighbor %s\n", olsr_ip_to_string(&addrs->address));
265 new_route_entry = olsr_insert_routing_table(&addrs2->address, get_neighbor_nexthop(&addrs2->address), 1);
267 addrs2 = addrs2->next;
279 *Insert all the two hop neighbors that is not already added
280 *in the routing table.
282 *@return a pointer to a destination_n linked-list of the neighbors.
285 static struct destination_n *
286 olsr_fill_routing_table_with_two_hop_neighbors()
288 struct destination_n *list_destination_n=NULL;
291 //printf("FILL ROUTING TABLE WITH TWO HOP NEIGHBORS\n");
293 for(index=0;index<HASHSIZE;index++)
295 struct neighbor_entry *neighbor;
297 for(neighbor = neighbortable[index].next;
298 neighbor != &neighbortable[index];
299 neighbor=neighbor->next)
301 struct neighbor_2_list_entry *neigh_2_list;
303 if(neighbor->status != SYM)
307 *Insert all the two hop neighbors
309 for(neigh_2_list = neighbor->neighbor_2_list.next;
310 neigh_2_list != &neighbor->neighbor_2_list;
311 neigh_2_list = neigh_2_list->next)
313 olsr_bool neighbor_ok;
314 union olsr_ip_addr *n2_addr;
315 static struct addresses addrs;
316 struct addresses *addrsp;
317 struct neighbor_list_entry *neighbors;
319 n2_addr = &neigh_2_list->neighbor_2->neighbor_2_addr;
321 if(olsr_lookup_routing_table(n2_addr))
324 olsr_printf(7, "2hop: %s already added\n", olsr_ip_to_string(n2_addr));
330 * Neighbor is only added if avalible trough
331 * a 1 hop neighbor with willingness != WILL_NEVER
333 neighbor_ok = OLSR_FALSE;
335 for(neighbors = neigh_2_list->neighbor_2->neighbor_2_nblist.next;
336 neighbors != &neigh_2_list->neighbor_2->neighbor_2_nblist;
337 neighbors = neighbors->next)
339 if((neighbors->neighbor->status != NOT_NEIGH) &&
340 (neighbors->neighbor->willingness != WILL_NEVER))
341 neighbor_ok = OLSR_TRUE;
346 olsr_printf(1, "Two hop neighbor %s not added - no one hop neighbors.\n",
347 olsr_ip_to_string(n2_addr));
351 COPY_IP(&addrs.address, n2_addr);
352 addrs.next = mid_lookup_aliases(n2_addr);
357 struct rt_entry *new_route_entry = NULL;
359 olsr_printf(7, "(ROUTE)Adding neighbor %s\n", olsr_ip_to_string(&addrsp->address));
363 olsr_insert_routing_table(&addrsp->address,
364 get_neighbor_nexthop(&neighbor->neighbor_main_addr),
367 if(new_route_entry != NULL)
369 struct destination_n *list_destination_tmp;
370 list_destination_tmp = olsr_malloc(sizeof(struct destination_n),
371 "Fill rt table 2 hop tmp");
373 list_destination_tmp->destination = new_route_entry;
374 list_destination_tmp->next = list_destination_n;
375 list_destination_n = list_destination_tmp;
377 addrsp = addrsp->next;
384 return(list_destination_n);
391 *Recalculate the routing table
396 olsr_calculate_routing_table()
398 struct destination_n *list_destination_n_1 = NULL;
400 olsr_move_route_table(routingtable, old_routes);
403 olsr_fill_routing_table_with_neighbors();
404 /* Add two hop enighbors - now they are the "outer rim" */
405 list_destination_n_1 = olsr_fill_routing_table_with_two_hop_neighbors();
407 while(list_destination_n_1!=NULL)
409 /* List_destination_n_1 holds the "outer rim" */
410 struct destination_n *list_destination_n = list_destination_n_1;
412 list_destination_n_1=NULL;
414 /* Next "outer rim" */
415 while(list_destination_n!=NULL)
417 struct destination_n *destination_n_1=NULL;
418 struct tc_entry *topo_entry;
420 if((topo_entry = olsr_lookup_tc_entry(&list_destination_n->destination->rt_dst)) != NULL)
422 struct topo_dst *topo_dest = topo_entry->destinations.next;
424 /* Loop trough this nodes MPR selectors */
425 while(topo_dest != &topo_entry->destinations)
427 static struct addresses tmp_addrs;
428 struct addresses *tmp_addrsp;
430 /* Do not add ourselves */
431 if(if_ifwithaddr(&topo_dest->T_dest_addr))
433 topo_dest=topo_dest->next;
438 COPY_IP(&tmp_addrs.address, &topo_dest->T_dest_addr);
439 tmp_addrs.next = mid_lookup_aliases(&topo_dest->T_dest_addr);
440 tmp_addrsp = &tmp_addrs;
442 while(tmp_addrsp!=NULL)
444 if(NULL==olsr_lookup_routing_table(&tmp_addrsp->address))
446 /* PRINT OUT: Last Hop to Final Destination */
447 /* The function ip_to_string has to be seperately */
448 olsr_printf(3, "%s -> ", olsr_ip_to_string(&list_destination_n->destination->rt_dst));
449 olsr_printf(3, "%s\n", olsr_ip_to_string(&tmp_addrsp->address) );
451 destination_n_1 = olsr_malloc(sizeof(struct destination_n),
452 "Calculate routing table 2");
454 /* Add this entry to the "outer rim" */
455 destination_n_1->destination =
456 olsr_insert_routing_table(&tmp_addrsp->address,
457 &list_destination_n->destination->rt_router,
458 list_destination_n->destination->rt_metric+1);
459 if(destination_n_1->destination != NULL)
461 destination_n_1->next=list_destination_n_1;
462 list_destination_n_1=destination_n_1;
465 tmp_addrsp = tmp_addrsp->next;
468 /* Next MPR selector */
469 topo_dest=topo_dest->next;
471 } /* End loop trought MPR selectors */
473 } /* End check if already added */
475 /* Delete this entry - do next */
476 destination_n_1 = list_destination_n;
477 list_destination_n = list_destination_n->next;
478 free(destination_n_1);
485 if(olsr_cnf->debug_level > 5)
487 printf("************** TABLES ****************\n");
488 printf("Routing table:\n");
489 olsr_print_routing_table(routingtable);
490 printf("Old table:\n");
491 olsr_print_routing_table(old_routes);
492 printf("**************************************\n");
497 olsr_update_kernel_routes();
499 olsr_free_routing_table(old_routes);
506 *Check for a entry with a higher hopcount than
507 *a given value in a routing table
509 *@param routes the routingtable to look in
510 *@param net the network entry to look for
511 *@param metric the metric to check for
513 *@return the localted entry if found. NULL if not
515 static struct rt_entry *
516 olsr_check_for_higher_hopcount(struct rt_entry *routes, struct hna_net *net, olsr_u16_t metric)
520 for(index=0;index<HASHSIZE;index++)
522 struct rt_entry *tmp_routes;
524 for(tmp_routes = routes[index].next;
525 tmp_routes != &routes[index];
526 tmp_routes = tmp_routes->next)
528 if(COMP_IP(&tmp_routes->rt_dst, &net->A_network_addr) &&
529 (memcmp(&tmp_routes->rt_mask, &net->A_netmask, netmask_size) == 0))
532 if(tmp_routes->rt_metric > metric)
546 *Check for a entry with a lower or equal hopcount than
547 *a given value in a routing table
549 *@param routes the routingtable to look in
550 *@param net the network entry to look for
551 *@param metric the metric to check for
553 *@return the localted entry if found. NULL if not
556 olsr_check_for_lower_hopcount(struct rt_entry *routes, struct hna_net *net, olsr_u16_t metric)
560 for(index=0;index<HASHSIZE;index++)
562 struct rt_entry *tmp_routes;
564 for(tmp_routes = routes[index].next;
565 tmp_routes != &routes[index];
566 tmp_routes = tmp_routes->next)
568 if(COMP_IP(&tmp_routes->rt_dst, &net->A_network_addr) &&
569 (memcmp(&tmp_routes->rt_mask, &net->A_netmask, netmask_size) == 0))
572 if(tmp_routes->rt_metric <= metric)
589 *Calculate the HNA routes
593 olsr_calculate_hna_routes()
598 olsr_printf(3, "Calculating HNA routes\n");
601 olsr_move_route_table(hna_routes, old_hna);
604 for(index=0;index<HASHSIZE;index++)
606 struct hna_entry *tmp_hna;
608 for(tmp_hna = hna_set[index].next;
609 tmp_hna != &hna_set[index];
610 tmp_hna = tmp_hna->next)
612 struct hna_net *tmp_net;
614 for(tmp_net = tmp_hna->networks.next;
615 tmp_net != &tmp_hna->networks;
616 tmp_net = tmp_net->next)
618 struct rt_entry *tmp_rt, *new_rt;
619 //printf("HNA: checking %s -> ", olsr_ip_to_string(&tmp_hna->A_gateway_addr));
620 //printf("%s", olsr_ip_to_string(&tmp_net->A_network_addr));
622 /* If no route to gateway - skip */
623 if((tmp_rt = olsr_lookup_routing_table(&tmp_hna->A_gateway_addr)) == NULL)
628 /* If there exists a better or equal entry - skip */
629 if(olsr_check_for_lower_hopcount(hna_routes, tmp_net, tmp_rt->rt_metric) != NULL)
634 /* If we find an entry with higher hopcount we just edit it */
635 if((new_rt = olsr_check_for_higher_hopcount(hna_routes, tmp_net, tmp_rt->rt_metric)) != NULL)
639 COPY_IP(&new_rt->rt_dst, &tmp_net->A_network_addr);
640 new_rt->rt_mask = tmp_net->A_netmask;
642 COPY_IP(&new_rt->rt_router, &tmp_rt->rt_router);
644 new_rt->rt_metric = tmp_rt->rt_metric;
646 new_rt->rt_flags = RTF_UP | RTF_GATEWAY;
649 /* If not - create a new one */
652 new_rt = olsr_malloc(sizeof(struct rt_entry), "New rt entry");
656 COPY_IP(&new_rt->rt_dst, &tmp_net->A_network_addr);
657 new_rt->rt_mask = tmp_net->A_netmask;
659 COPY_IP(&new_rt->rt_router, &tmp_rt->rt_router);
661 new_rt->rt_metric = tmp_rt->rt_metric;
663 new_rt->rt_flags = RTF_UP | RTF_GATEWAY;
666 if((new_rt->rt_if = get_interface_link_set(&new_rt->rt_router)) == NULL)
668 fprintf(stderr, "ADD ROUTE 2: %s Could not find neighbor interface!!!\n",
669 olsr_ip_to_string(&new_rt->rt_dst));
670 /* This hopefullt never happens */
677 /* Queue HASH will almost always be 0 */
678 hna_hash = olsr_hashing(&tmp_net->A_network_addr);
679 hna_routes[hna_hash].next->prev = new_rt;
680 new_rt->next = hna_routes[hna_hash].next;
681 hna_routes[hna_hash].next = new_rt;
682 new_rt->prev = &hna_routes[hna_hash];
690 olsr_update_kernel_hna_routes();
692 if(olsr_cnf->debug_level > 2)
694 olsr_printf(3, "HNA table:\n");
695 olsr_print_routing_table(hna_routes);
698 olsr_free_routing_table(old_hna);
707 *Print the routingtable to STDOUT
712 olsr_print_routing_table(struct rt_entry *table)
717 printf("ROUTING TABLE\n");
718 printf("DESTINATION\tNEXT HOP\n");
719 for(index=0;index<HASHSIZE;index++)
721 struct rt_entry *destination;
722 for(destination = table[index].next;
723 destination != &table[index];
724 destination = destination->next)
726 printf("%s\t", olsr_ip_to_string(&destination->rt_dst));
727 printf("%s\n", olsr_ip_to_string(&destination->rt_router));