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