2 * OLSR ad-hoc routing table management protocol
3 * Copyright (C) 2004 Andreas Tønnesen (andreto@ifi.uio.no)
5 * This file is part of the olsr.org OLSR daemon.
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.
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.
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
22 * $Id: routing_table.c,v 1.9 2004/11/07 17:51:20 tlopatic Exp $
29 #include "two_hop_neighbor_table.h"
38 * Prototypes for internal functions
42 olsr_fill_routing_table_with_neighbors(void);
44 static struct destination_n *
45 olsr_fill_routing_table_with_two_hop_neighbors(void);
47 static struct rt_entry *
48 olsr_check_for_higher_hopcount(struct rt_entry *, struct hna_net *, olsr_u16_t);
50 static struct rt_entry *
51 olsr_lookup_routing_table(union olsr_ip_addr *);
54 olsr_check_for_lower_hopcount(struct rt_entry *, struct hna_net *, olsr_u16_t);
57 * Prototypes for internal functions
62 *Initialize the routing table
65 olsr_init_routing_table()
70 *The hna routes hash will almost always
72 *But it is kept as a hash to be compatible
73 *with the functions used on the regular
76 for(index=0;index<HASHSIZE;index++)
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];
87 *Look up an entry in the routing table.
89 *@param dst the address of the entry
91 *@return a pointer to a rt_entry struct
92 *representing the route entry.
94 static struct rt_entry *
95 olsr_lookup_routing_table(union olsr_ip_addr *dst)
98 struct rt_entry *rt_table;
101 hash = olsr_hashing(dst);
103 for(rt_table = routingtable[hash].next;
104 rt_table != &routingtable[hash];
105 rt_table = rt_table->next)
107 if (COMP_IP(&rt_table->rt_dst, dst))
120 *Delete all the entries in the routing table hash
122 *@param table the routing hash table
127 olsr_free_routing_table(struct rt_entry *table)
129 struct rt_entry *destination;
130 struct rt_entry *dst_to_delete;
134 for(index=0;index<HASHSIZE;index++)
136 destination = table[index].next;
138 while(destination != &table[index])
140 dst_to_delete = destination;
141 destination = destination->next;
143 dst_to_delete->next->prev = dst_to_delete->prev;
144 dst_to_delete->prev->next = dst_to_delete->next;
154 *Insert an 1 or 2 neighbor-entry into the routing table.
156 *@param dst the destination
158 *@return the new rt_entry struct
161 olsr_insert_routing_table(union olsr_ip_addr *dst, union olsr_ip_addr *router, int metric)
163 struct rt_entry *new_route_entry, *rt_list;
166 hash = olsr_hashing(dst);
167 rt_list = &routingtable[hash];
169 new_route_entry = olsr_malloc(sizeof(struct rt_entry), "Insert routing table");
171 COPY_IP(&new_route_entry->rt_dst, dst);
172 COPY_IP(&new_route_entry->rt_router, router);
174 new_route_entry->rt_metric = metric;
175 if(COMP_IP(dst, router))
177 new_route_entry->rt_flags = (RTF_UP|RTF_HOST);
179 new_route_entry->rt_flags = (RTF_UP|RTF_HOST|RTF_GATEWAY);
181 if(olsr_cnf->ip_version == AF_INET)
183 new_route_entry->rt_mask.v4 = NETMASK_HOST;
186 new_route_entry->rt_mask.v6 = 128;
189 if((new_route_entry->rt_if = get_interface_link_set(router)) == NULL)
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);
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;
206 return(new_route_entry);
212 *Insert all the one hop neighbors in the routing table.
214 *@return a pointer to a destination_n linked-list of the neighbors.
217 olsr_fill_routing_table_with_neighbors()
220 struct neighbor_entry *neighbor;
221 struct rt_entry *new_route_entry=NULL;
223 struct addresses *addrs=NULL, *addrs2;
226 olsr_printf(7, "FILL ROUTING TABLE WITH NEIGHBORS\n");
229 for(index=0;index<HASHSIZE;index++)
231 for(neighbor = neighbortable[index].next;
232 neighbor != &neighbortable[index];
233 neighbor=neighbor->next)
236 if(neighbor->status == SYM)
239 *Insert all the neighbors addresses
241 addrs = olsr_malloc(sizeof(struct addresses), "Fill routing table with neighbors");
243 COPY_IP(&addrs->address, &neighbor->neighbor_main_addr);
244 addrs->next = mid_lookup_aliases(&neighbor->neighbor_main_addr);
250 olsr_printf(7, "(ROUTE)Adding neighbor %s\n", olsr_ip_to_string(&addrs->address));
253 new_route_entry = olsr_insert_routing_table(&addrs->address, get_neighbor_nexthop(&addrs->address), 1);
268 *Insert all the two hop neighbors that is not already added
269 *in the routing table.
271 *@return a pointer to a destination_n linked-list of the neighbors.
274 static struct destination_n *
275 olsr_fill_routing_table_with_two_hop_neighbors()
277 struct destination_n *list_destination_n=NULL;
278 struct destination_n *list_destination_tmp=NULL;
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;
288 //printf("FILL ROUTING TABLE WITH TWO HOP NEIGHBORS\n");
290 for(index=0;index<HASHSIZE;index++)
292 for(neighbor = neighbortable[index].next;
293 neighbor != &neighbortable[index];
294 neighbor=neighbor->next)
297 if(neighbor->status != SYM)
301 *Insert all the two hop neighbors
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)
308 n2_addr = &neigh_2_list->neighbor_2->neighbor_2_addr;
310 if(olsr_lookup_routing_table(n2_addr))
313 olsr_printf(7, "2hop: %s already added\n", olsr_ip_to_string(n2_addr));
319 * Neighbor is only added if avalible trough
320 * a 1 hop neighbor with willingness != WILL_NEVER
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)
328 if((neighbors->neighbor->status != NOT_NEIGH) &&
329 (neighbors->neighbor->willingness != WILL_NEVER))
335 olsr_printf(1, "Two hop neighbor %s not added - no one hop neighbors.\n",
336 olsr_ip_to_string(n2_addr));
340 addrs = olsr_malloc(sizeof(struct addresses), "Fill rt table 2 hop neighbors");
342 COPY_IP(&addrs->address, n2_addr);
343 addrs->next = mid_lookup_aliases(n2_addr);
349 olsr_printf(7, "(ROUTE)Adding neighbor %s\n", olsr_ip_to_string(&addrs->address));
352 new_route_entry = olsr_insert_routing_table(&addrs->address, get_neighbor_nexthop(&neighbor->neighbor_main_addr), 2);
354 if(new_route_entry != NULL)
356 list_destination_tmp = olsr_malloc(sizeof(struct destination_n), "Fill rt table 2 hop tmp");
358 list_destination_tmp->destination = new_route_entry;
359 list_destination_tmp->next = list_destination_n;
360 list_destination_n = list_destination_tmp;
370 return(list_destination_n);
377 *Recalculate the routing table
382 olsr_calculate_routing_table()
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;
394 olsr_move_route_table(routingtable, old_routes);
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();
402 /* List_destination_n_1 holds the "outer rim" */
403 list_destination_n = list_destination_n_1;
405 while(list_destination_n_1!=NULL)
407 list_destination_n_1=NULL;
409 /* Next "outer rim" */
410 while(list_destination_n!=NULL)
412 if((topo_entry = olsr_lookup_tc_entry(&list_destination_n->destination->rt_dst)) != NULL)
414 topo_dest = topo_entry->destinations.next;
416 /* Loop trough this nodes MPR selectors */
417 while(topo_dest != &topo_entry->destinations)
419 /* Check if dest is ourselves!! */
422 /* Do not add ourselves */
423 if(if_ifwithaddr(&topo_dest->T_dest_addr))
425 topo_dest=topo_dest->next;
430 tmp_addrs = olsr_malloc(sizeof(struct addresses), "Calculate routing table MID");
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;
436 while(tmp_addrs!=NULL)
438 if(NULL==olsr_lookup_routing_table(&tmp_addrs->address))
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) );
445 destination_n_1 = olsr_malloc(sizeof(struct destination_n), "Calculate routing table 2");
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)
454 destination_n_1->next=list_destination_n_1;
455 list_destination_n_1=destination_n_1;
458 tmp_addrs = tmp_addrs->next;
462 /* Next MPR selector */
463 topo_dest=topo_dest->next;
465 } /* End loop trought MPR selectors */
467 } /* End check if already added */
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);
476 /* New "outer rim" */
477 list_destination_n=list_destination_n_1;
481 if(olsr_cnf->debug_level > 5)
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");
493 olsr_update_kernel_routes();
495 olsr_free_routing_table(old_routes);
502 *Check for a entry with a higher hopcount than
503 *a given value in a routing table
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
509 *@return the localted entry if found. NULL if not
511 static struct rt_entry *
512 olsr_check_for_higher_hopcount(struct rt_entry *routes, struct hna_net *net, olsr_u16_t metric)
515 struct rt_entry *tmp_routes;
517 for(index=0;index<HASHSIZE;index++)
520 for(tmp_routes = routes[index].next;
521 tmp_routes != &routes[index];
522 tmp_routes = tmp_routes->next)
524 if(COMP_IP(&tmp_routes->rt_dst, &net->A_network_addr) &&
525 (memcmp(&tmp_routes->rt_mask, &net->A_netmask, netmask_size) == 0))
528 if(tmp_routes->rt_metric > metric)
542 *Check for a entry with a lower or equal hopcount than
543 *a given value in a routing table
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
549 *@return the localted entry if found. NULL if not
552 olsr_check_for_lower_hopcount(struct rt_entry *routes, struct hna_net *net, olsr_u16_t metric)
555 struct rt_entry *tmp_routes;
557 for(index=0;index<HASHSIZE;index++)
560 for(tmp_routes = routes[index].next;
561 tmp_routes != &routes[index];
562 tmp_routes = tmp_routes->next)
564 if(COMP_IP(&tmp_routes->rt_dst, &net->A_network_addr) &&
565 (memcmp(&tmp_routes->rt_mask, &net->A_netmask, netmask_size) == 0))
568 if(tmp_routes->rt_metric <= metric)
585 *Calculate the HNA routes
589 olsr_calculate_hna_routes()
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;
597 olsr_printf(3, "Calculating HNA routes\n");
600 olsr_move_route_table(hna_routes, old_hna);
603 for(index=0;index<HASHSIZE;index++)
606 for(tmp_hna = hna_set[index].next;
607 tmp_hna != &hna_set[index];
608 tmp_hna = tmp_hna->next)
612 for(tmp_net = tmp_hna->networks.next;
613 tmp_net != &tmp_hna->networks;
614 tmp_net = tmp_net->next)
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));
619 /* If no route to gateway - skip */
620 if((tmp_rt = olsr_lookup_routing_table(&tmp_hna->A_gateway_addr)) == NULL)
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)
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)
636 COPY_IP(&new_rt->rt_dst, &tmp_net->A_network_addr);
637 memcpy(&new_rt->rt_mask, &tmp_net->A_netmask, netmask_size);
639 COPY_IP(&new_rt->rt_router, &tmp_rt->rt_router);
641 new_rt->rt_metric = tmp_rt->rt_metric;
643 new_rt->rt_flags = RTF_UP | RTF_GATEWAY;
646 /* If not - create a new one */
649 new_rt = olsr_malloc(sizeof(struct rt_entry), "New rt entry");
653 COPY_IP(&new_rt->rt_dst, &tmp_net->A_network_addr);
654 memcpy(&new_rt->rt_mask, &tmp_net->A_netmask, netmask_size);
656 COPY_IP(&new_rt->rt_router, &tmp_rt->rt_router);
658 new_rt->rt_metric = tmp_rt->rt_metric;
660 new_rt->rt_flags = RTF_UP | RTF_GATEWAY;
663 if((new_rt->rt_if = get_interface_link_set(&new_rt->rt_router)) == NULL)
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 */
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];
685 olsr_update_kernel_hna_routes();
687 if(olsr_cnf->debug_level > 2)
689 olsr_printf(3, "HNA table:\n");
690 olsr_print_routing_table(hna_routes);
693 olsr_free_routing_table(old_hna);
702 *Print the routingtable to STDOUT
707 olsr_print_routing_table(struct rt_entry *table)
710 struct rt_entry *destination;
713 printf("ROUTING TABLE\n");
714 printf("DESTINATION\tNEXT HOP\n");
715 for(index=0;index<HASHSIZE;index++)
717 for(destination = table[index].next;
718 destination != &table[index];
719 destination = destination->next)
721 printf("%s\t", olsr_ip_to_string(&destination->rt_dst));
722 printf("%s\n", olsr_ip_to_string(&destination->rt_router));