src/neighbor_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: neighbor_table.c,v 1.19 2004/11/21 13:45:50 kattemat Exp $
  40  */
  41
  42
  43
  44 #include "defs.h"
  45 #include "two_hop_neighbor_table.h"
  46 #include "mid_set.h"
  47 #include "mpr.h"
  48 #include "olsr.h"
  49 #include "scheduler.h"
  50 #include "link_set.h"
  51 #include "mpr_selector_set.h"
  52
  53 void
  54 olsr_init_neighbor_table()
  55 {
  56   int i;
  57
  58   olsr_register_timeout_function(&olsr_time_out_neighborhood_tables);
  59
  60   for(i = 0; i < HASHSIZE; i++)
  61     {
  62       neighbortable[i].next = &neighbortable[i];
  63       neighbortable[i].prev = &neighbortable[i];
  64     }
  65 }
  66
  67
  68 /**
  69  *Delete a two hop neighbor from a neighbors two
  70  *hop neighbor list.
  71  *
  72  *@param neighbor the neighbor to delete the two hop
  73  *neighbor from.
  74  *@param address the IP address of the two hop neighbor
  75  *to delete.
  76  *
  77  *@return positive if entry deleted
  78  */
  79 int
  80 olsr_delete_neighbor_2_pointer(struct neighbor_entry *neighbor, union olsr_ip_addr *address)
  81 {
  82
  83   struct neighbor_2_list_entry *entry;
  84
  85   entry = neighbor->neighbor_2_list.next;
  86
  87   while(entry != &neighbor->neighbor_2_list)
  88     {
  89
  90       if(COMP_IP(&entry->neighbor_2->neighbor_2_addr, address))
  91         {
  92           /* Dequeue */
  93           DEQUEUE_ELEM(entry);
  94           /* Delete */
  95           free(entry);
  96           return 1;
  97         }
  98       entry = entry->next;
  99     }
 100   return 0;
 101 }
 102
 103
 104 /**
 105  *Check if a two hop neighbor is reachable via a given
 106  *neighbor.
 107  *
 108  *@param neighbor neighbor-entry to check via
 109  *@param neighbor_main_address the addres of the two hop neighbor
 110  *to find.
 111  *
 112  *@return a pointer to the neighbor_2_list_entry struct
 113  *representing the two hop neighbor if found. NULL if not found.
 114  */
 115 struct neighbor_2_list_entry *
 116 olsr_lookup_my_neighbors(struct neighbor_entry *neighbor, union olsr_ip_addr *neighbor_main_address)
 117 {
 118
 119   struct neighbor_2_list_entry *entry;
 120
 121   for(entry = neighbor->neighbor_2_list.next;
 122       entry != &neighbor->neighbor_2_list;
 123       entry = entry->next)
 124     {
 125
 126       if(COMP_IP(&entry->neighbor_2->neighbor_2_addr, neighbor_main_address))
 127         return entry;
 128
 129     }
 130   return NULL;
 131 }
 132
 133
 134
 135 /**
 136  *Delete a neighbr table entry.
 137  *
 138  *Remember: Deleting a neighbor entry results
 139  *the deletion of its 2 hop neighbors list!!!
 140  *@param neighbor the neighbor entry to delete
 141  *
 142  *@return nada
 143  */
 144
 145 int
 146 olsr_delete_neighbor_table(union olsr_ip_addr *neighbor_addr)
 147 {
 148   struct  neighbor_2_list_entry *two_hop_list, *two_hop_to_delete;
 149   struct  neighbor_2_entry      *two_hop_entry;
 150   olsr_u32_t                    hash;
 151   struct neighbor_entry         *entry;
 152
 153   //printf("inserting neighbor\n");
 154
 155   hash = olsr_hashing(neighbor_addr);
 156
 157   entry = neighbortable[hash].next;
 158
 159   /*
 160    * Find neighbor entry
 161    */
 162   while(entry != &neighbortable[hash])
 163     {
 164       if(COMP_IP(&entry->neighbor_main_addr, neighbor_addr))
 165         break;
 166
 167       entry = entry->next;
 168     }
 169
 170   if(entry == &neighbortable[hash])
 171     return 0;
 172
 173
 174   two_hop_list = entry->neighbor_2_list.next;
 175
 176   while(two_hop_list != &entry->neighbor_2_list)
 177     {
 178       two_hop_entry = two_hop_list->neighbor_2;
 179
 180       two_hop_entry->neighbor_2_pointer--;
 181
 182       olsr_delete_neighbor_pointer(two_hop_entry, &entry->neighbor_main_addr);
 183
 184       /* Delete entry if it has no more one hop neighbors pointing to it */
 185       if(two_hop_entry->neighbor_2_pointer < 1)
 186         {
 187           DEQUEUE_ELEM(two_hop_entry);
 188
 189           free(two_hop_entry);
 190         }
 191
 192
 193       two_hop_to_delete = two_hop_list;
 194       two_hop_list = two_hop_list->next;
 195       /* Delete entry */
 196       free(two_hop_to_delete);
 197
 198     }
 199
 200
 201   /* Dequeue */
 202   DEQUEUE_ELEM(entry);
 203
 204   free(entry);
 205
 206   changes_neighborhood = OLSR_TRUE;
 207   return 1;
 208
 209 }
 210
 211
 212
 213 /**
 214  *Insert a neighbor entry in the neighbor table
 215  *
 216  *@param main_addr the main address of the new node
 217  *
 218  *@return 0 if neighbor already exists 1 if inserted
 219  */
 220 struct neighbor_entry *
 221 olsr_insert_neighbor_table(union olsr_ip_addr *main_addr)
 222 {
 223   olsr_u32_t             hash;
 224   struct neighbor_entry  *new_neigh;
 225
 226   hash = olsr_hashing(main_addr);
 227
 228   /* Check if entry exists */
 229
 230   for(new_neigh = neighbortable[hash].next;
 231       new_neigh != &neighbortable[hash];
 232       new_neigh = new_neigh->next)
 233     {
 234       if(COMP_IP(&new_neigh->neighbor_main_addr, main_addr))
 235         return new_neigh;
 236     }
 237
 238   //printf("inserting neighbor\n");
 239
 240   new_neigh = olsr_malloc(sizeof(struct neighbor_entry), "New neighbor entry");
 241
 242   /* Set address, willingness and status */
 243   COPY_IP(&new_neigh->neighbor_main_addr, main_addr);
 244   new_neigh->willingness = WILL_NEVER;
 245   new_neigh->status = NOT_SYM;
 246
 247   new_neigh->neighbor_2_list.next = &new_neigh->neighbor_2_list;
 248   new_neigh->neighbor_2_list.prev = &new_neigh->neighbor_2_list;
 249
 250   new_neigh->linkcount = 0;
 251   new_neigh->is_mpr = OLSR_FALSE;
 252   new_neigh->was_mpr = OLSR_FALSE;
 253
 254   /* Queue */
 255   QUEUE_ELEM(neighbortable[hash], new_neigh);
 256
 257   return new_neigh;
 258 }
 259
 260
 261
 262 /**
 263  *Lookup a neighbor entry in the neighbortable based on an address.
 264  *
 265  *@param dst the IP address of the neighbor to look up
 266  *
 267  *@return a pointer to the neighbor struct registered on the given
 268  *address. NULL if not found.
 269  */
 270 struct neighbor_entry *
 271 olsr_lookup_neighbor_table(union olsr_ip_addr *dst)
 272 {
 273   struct neighbor_entry  *entry;
 274   olsr_u32_t             hash;
 275   //struct addresses       *adr;
 276   union olsr_ip_addr     *tmp_ip;
 277
 278   /*
 279    *Find main address of node
 280    */
 281   if((tmp_ip = mid_lookup_main_addr(dst)) != NULL)
 282     dst = tmp_ip;
 283
 284   hash = olsr_hashing(dst);
 285
 286
 287   //printf("\nLookup %s\n", olsr_ip_to_string(dst));
 288   for(entry = neighbortable[hash].next;
 289       entry != &neighbortable[hash];
 290       entry = entry->next)
 291     {
 292       //printf("Checking %s\n", olsr_ip_to_string(&neighbor_table_tmp->neighbor_main_addr));
 293       if(COMP_IP(&entry->neighbor_main_addr, dst))
 294         return entry;
 295
 296     }
 297   //printf("NOPE\n\n");
 298
 299   return NULL;
 300
 301 }
 302
 303
 304 /**
 305  *Lookup a neighbor entry in the neighbortable based on an address.
 306  *
 307  *@param dst the IP address of the neighbor to look up
 308  *
 309  *@return a pointer to the neighbor struct registered on the given
 310  *address. NULL if not found.
 311  */
 312 struct neighbor_entry *
 313 olsr_lookup_neighbor_table_alias(union olsr_ip_addr *dst)
 314 {
 315   struct neighbor_entry  *entry;
 316   olsr_u32_t             hash;
 317   //struct addresses       *adr;
 318
 319   hash = olsr_hashing(dst);
 320
 321
 322   //printf("\nLookup %s\n", olsr_ip_to_string(dst));
 323   for(entry = neighbortable[hash].next;
 324       entry != &neighbortable[hash];
 325       entry = entry->next)
 326     {
 327       //printf("Checking %s\n", olsr_ip_to_string(&neighbor_table_tmp->neighbor_main_addr));
 328       if(COMP_IP(&entry->neighbor_main_addr, dst))
 329         return entry;
 330
 331     }
 332   //printf("NOPE\n\n");
 333
 334   return NULL;
 335
 336 }
 337
 338
 339
 340 int
 341 update_neighbor_status(struct neighbor_entry *entry, int link)
 342 {
 343   struct neighbor_2_entry *two_hop_neighbor;
 344
 345   /*
 346    * Update neighbor entry
 347    */
 348
 349   if(link == SYM_LINK)
 350     {
 351       /* N_status is set to SYM */
 352       if(entry->status == NOT_SYM)
 353         {
 354
 355           /* Delete posible 2 hop entry on this neighbor */
 356           if((two_hop_neighbor = olsr_lookup_two_hop_neighbor_table(&entry->neighbor_main_addr))!=NULL)
 357             {
 358               olsr_delete_two_hop_neighbor_table(two_hop_neighbor);
 359             }
 360
 361           changes_neighborhood = OLSR_TRUE;
 362           changes_topology = OLSR_TRUE;
 363           if(olsr_cnf->tc_redundancy > 1)
 364             changes = OLSR_TRUE;
 365         }
 366       entry->status = SYM;
 367     }
 368   else
 369     {
 370       if(entry->status == SYM)
 371         {
 372           changes_neighborhood = OLSR_TRUE;
 373           changes_topology = OLSR_TRUE;
 374           if(olsr_cnf->tc_redundancy > 1)
 375             changes = OLSR_TRUE;
 376         }
 377       /* else N_status is set to NOT_SYM */
 378       entry->status = NOT_SYM;
 379       /* remove neighbor from routing list */
 380     }
 381
 382   return entry->status;
 383 }
 384
 385
 386
 387 /**
 388  *Times out the entries in the two hop neighbor table and
 389  *deletes those who have exceeded their time to live since
 390  *last update.
 391  *
 392  *@return nada
 393  */
 394
 395 void
 396 olsr_time_out_two_hop_neighbors(struct neighbor_entry  *neighbor)
 397 {
 398   struct  neighbor_2_list_entry *two_hop_list, *two_hop_to_delete;
 399   struct  neighbor_2_entry      *two_hop_entry;
 400
 401
 402   two_hop_list = neighbor->neighbor_2_list.next;
 403
 404   //neighbor->neighbor_2_list = NULL;
 405
 406   while(two_hop_list != &neighbor->neighbor_2_list)
 407     {
 408       if(TIMED_OUT(&two_hop_list->neighbor_2_timer))
 409         {
 410           two_hop_entry = two_hop_list->neighbor_2;
 411           two_hop_entry->neighbor_2_pointer--;
 412           olsr_delete_neighbor_pointer(two_hop_entry, &neighbor->neighbor_main_addr);
 413
 414           if(two_hop_entry->neighbor_2_pointer < 1)
 415             {
 416               /* FIX THIS (fix what?)*/
 417               DEQUEUE_ELEM(two_hop_entry);
 418
 419               free((void *)two_hop_entry);
 420             }
 421
 422           two_hop_to_delete = two_hop_list;
 423           two_hop_list = two_hop_list->next;
 424
 425           /* Dequeue */
 426           DEQUEUE_ELEM(two_hop_to_delete);
 427
 428           free(two_hop_to_delete);
 429
 430           /* This flag is set to OLSR_TRUE to recalculate the MPR set and the routing table*/
 431           changes_neighborhood = OLSR_TRUE;
 432           changes_topology = OLSR_TRUE;
 433
 434         }
 435       else
 436         two_hop_list = two_hop_list->next;
 437
 438     }
 439 }
 440
 441
 442
 443
 444
 445 void
 446 olsr_time_out_neighborhood_tables()
 447 {
 448   olsr_u8_t              index;
 449   struct neighbor_entry  *entry;
 450
 451   for(index=0;index<HASHSIZE;index++)
 452     {
 453       entry = neighbortable[index].next;
 454
 455       while(entry != &neighbortable[index])
 456         {
 457           olsr_time_out_two_hop_neighbors(entry);
 458
 459           entry = entry->next;
 460         }
 461     }
 462 }
 463
 464
 465
 466
 467
 468 /**
 469  *Prints the registered neighbors and two hop neighbors
 470  *to STDOUT.
 471  *
 472  *@return nada
 473  */
 474 void
 475 olsr_print_neighbor_table()
 476 {
 477   int i;
 478   struct neighbor_entry *neigh;
 479 #if defined USE_LINK_QUALITY
 480   struct link_entry *link;
 481 #endif
 482   double best_lq, inv_best_lq;
 483   char *fstr;
 484
 485   olsr_printf(1, "\n--- %02d:%02d:%02d.%02d ------------------------------------------------ NEIGHBORS\n\n",
 486               nowtm->tm_hour,
 487               nowtm->tm_min,
 488               nowtm->tm_sec,
 489               now.tv_usec/10000);
 490
 491   if (olsr_cnf->ip_version == AF_INET)
 492   {
 493     olsr_printf(1, "IP address       LQ     NLQ    SYM   MPR   MPRS  will\n");
 494     fstr = "%-15s  %5.3f  %5.3f  %s  %s  %s  %d\n";
 495   }
 496
 497   else
 498   {
 499     olsr_printf(1, "IP address                               LQ     NLQ    SYM   MPR   MPRS  will\n");
 500     fstr = "%-39s  %5.3f  %5.3f  %s  %s  %s  %d\n";
 501   }
 502
 503   for (i = 0; i < HASHSIZE; i++)
 504     {
 505       for(neigh = neighbortable[i].next; neigh != &neighbortable[i];
 506           neigh = neigh->next)
 507         {
 508 #if defined USE_LINK_QUALITY
 509           link = olsr_neighbor_best_link(&neigh->neighbor_main_addr);
 510           best_lq = link->neigh_link_quality;
 511
 512           link = olsr_neighbor_best_inverse_link(&neigh->neighbor_main_addr);
 513           inv_best_lq = link->loss_link_quality;
 514 #else
 515           best_lq = 0.0;
 516           inv_best_lq = 0.0;
 517 #endif
 518
 519           olsr_printf(1, fstr, olsr_ip_to_string(&neigh->neighbor_main_addr),
 520                       inv_best_lq, best_lq,
 521                       (neigh->status == SYM) ? "YES " : "NO  ",
 522                       neigh->is_mpr ? "YES " : "NO  ",
 523                       olsr_lookup_mprs_set(&neigh->neighbor_main_addr) == NULL ? "NO  " : "YES ",
 524                       neigh->willingness);
 525         }
 526     }
 527 }
 528
 529
 530
 531
 532
 533
 534
 535
 536
 537