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.23 2005/01/17 20:18:21 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   olsr_u32_t                    hash;
 150   struct neighbor_entry         *entry;
 151
 152   //printf("inserting neighbor\n");
 153
 154   hash = olsr_hashing(neighbor_addr);
 155
 156   entry = neighbortable[hash].next;
 157
 158   /*
 159    * Find neighbor entry
 160    */
 161   while(entry != &neighbortable[hash])
 162     {
 163       if(COMP_IP(&entry->neighbor_main_addr, neighbor_addr))
 164         break;
 165
 166       entry = entry->next;
 167     }
 168
 169   if(entry == &neighbortable[hash])
 170     return 0;
 171
 172
 173   two_hop_list = entry->neighbor_2_list.next;
 174
 175   while(two_hop_list != &entry->neighbor_2_list)
 176     {
 177       struct  neighbor_2_entry *two_hop_entry;
 178
 179       two_hop_entry = two_hop_list->neighbor_2;
 180
 181       two_hop_entry->neighbor_2_pointer--;
 182
 183       olsr_delete_neighbor_pointer(two_hop_entry, &entry->neighbor_main_addr);
 184
 185       /* Delete entry if it has no more one hop neighbors pointing to it */
 186       if(two_hop_entry->neighbor_2_pointer < 1)
 187         {
 188           DEQUEUE_ELEM(two_hop_entry);
 189
 190           free(two_hop_entry);
 191         }
 192
 193
 194       two_hop_to_delete = two_hop_list;
 195       two_hop_list = two_hop_list->next;
 196       /* Delete entry */
 197       free(two_hop_to_delete);
 198
 199     }
 200
 201
 202   /* Dequeue */
 203   DEQUEUE_ELEM(entry);
 204
 205   free(entry);
 206
 207   changes_neighborhood = OLSR_TRUE;
 208   return 1;
 209
 210 }
 211
 212
 213
 214 /**
 215  *Insert a neighbor entry in the neighbor table
 216  *
 217  *@param main_addr the main address of the new node
 218  *
 219  *@return 0 if neighbor already exists 1 if inserted
 220  */
 221 struct neighbor_entry *
 222 olsr_insert_neighbor_table(union olsr_ip_addr *main_addr)
 223 {
 224   olsr_u32_t             hash;
 225   struct neighbor_entry  *new_neigh;
 226
 227   hash = olsr_hashing(main_addr);
 228
 229   /* Check if entry exists */
 230
 231   for(new_neigh = neighbortable[hash].next;
 232       new_neigh != &neighbortable[hash];
 233       new_neigh = new_neigh->next)
 234     {
 235       if(COMP_IP(&new_neigh->neighbor_main_addr, main_addr))
 236         return new_neigh;
 237     }
 238
 239   //printf("inserting neighbor\n");
 240
 241   new_neigh = olsr_malloc(sizeof(struct neighbor_entry), "New neighbor entry");
 242
 243   /* Set address, willingness and status */
 244   COPY_IP(&new_neigh->neighbor_main_addr, main_addr);
 245   new_neigh->willingness = WILL_NEVER;
 246   new_neigh->status = NOT_SYM;
 247
 248   new_neigh->neighbor_2_list.next = &new_neigh->neighbor_2_list;
 249   new_neigh->neighbor_2_list.prev = &new_neigh->neighbor_2_list;
 250
 251   new_neigh->linkcount = 0;
 252   new_neigh->is_mpr = OLSR_FALSE;
 253   new_neigh->was_mpr = OLSR_FALSE;
 254
 255   /* Queue */
 256   QUEUE_ELEM(neighbortable[hash], new_neigh);
 257
 258   return new_neigh;
 259 }
 260
 261
 262
 263 /**
 264  *Lookup a neighbor entry in the neighbortable based on an address.
 265  *
 266  *@param dst the IP address of the neighbor to look up
 267  *
 268  *@return a pointer to the neighbor struct registered on the given
 269  *address. NULL if not found.
 270  */
 271 struct neighbor_entry *
 272 olsr_lookup_neighbor_table(union olsr_ip_addr *dst)
 273 {
 274   struct neighbor_entry  *entry;
 275   olsr_u32_t             hash;
 276   //struct addresses       *adr;
 277   union olsr_ip_addr     *tmp_ip;
 278
 279   /*
 280    *Find main address of node
 281    */
 282   if((tmp_ip = mid_lookup_main_addr(dst)) != NULL)
 283     dst = tmp_ip;
 284
 285   hash = olsr_hashing(dst);
 286
 287
 288   //printf("\nLookup %s\n", olsr_ip_to_string(dst));
 289   for(entry = neighbortable[hash].next;
 290       entry != &neighbortable[hash];
 291       entry = entry->next)
 292     {
 293       //printf("Checking %s\n", olsr_ip_to_string(&neighbor_table_tmp->neighbor_main_addr));
 294       if(COMP_IP(&entry->neighbor_main_addr, dst))
 295         return entry;
 296
 297     }
 298   //printf("NOPE\n\n");
 299
 300   return NULL;
 301
 302 }
 303
 304
 305 /**
 306  *Lookup a neighbor entry in the neighbortable based on an address.
 307  *
 308  *@param dst the IP address of the neighbor to look up
 309  *
 310  *@return a pointer to the neighbor struct registered on the given
 311  *address. NULL if not found.
 312  */
 313 struct neighbor_entry *
 314 olsr_lookup_neighbor_table_alias(union olsr_ip_addr *dst)
 315 {
 316   struct neighbor_entry  *entry;
 317   olsr_u32_t             hash;
 318   //struct addresses       *adr;
 319
 320   hash = olsr_hashing(dst);
 321
 322
 323   //printf("\nLookup %s\n", olsr_ip_to_string(dst));
 324   for(entry = neighbortable[hash].next;
 325       entry != &neighbortable[hash];
 326       entry = entry->next)
 327     {
 328       //printf("Checking %s\n", olsr_ip_to_string(&neighbor_table_tmp->neighbor_main_addr));
 329       if(COMP_IP(&entry->neighbor_main_addr, dst))
 330         return entry;
 331
 332     }
 333   //printf("NOPE\n\n");
 334
 335   return NULL;
 336
 337 }
 338
 339
 340
 341 int
 342 update_neighbor_status(struct neighbor_entry *entry, int link)
 343 {
 344   /*
 345    * Update neighbor entry
 346    */
 347
 348   if(link == SYM_LINK)
 349     {
 350       /* N_status is set to SYM */
 351       if(entry->status == NOT_SYM)
 352         {
 353           struct neighbor_2_entry *two_hop_neighbor;
 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;
 399
 400   two_hop_list = neighbor->neighbor_2_list.next;
 401
 402   while(two_hop_list != &neighbor->neighbor_2_list)
 403     {
 404       if(TIMED_OUT(two_hop_list->neighbor_2_timer))
 405         {
 406           struct neighbor_2_list_entry *two_hop_to_delete;
 407           struct neighbor_2_entry      *two_hop_entry = two_hop_list->neighbor_2;
 408
 409           two_hop_entry->neighbor_2_pointer--;
 410           olsr_delete_neighbor_pointer(two_hop_entry, &neighbor->neighbor_main_addr);
 411
 412           if(two_hop_entry->neighbor_2_pointer < 1)
 413             {
 414               DEQUEUE_ELEM(two_hop_entry);
 415               free((void *)two_hop_entry);
 416             }
 417
 418           two_hop_to_delete = two_hop_list;
 419           two_hop_list = two_hop_list->next;
 420
 421           /* Dequeue */
 422           DEQUEUE_ELEM(two_hop_to_delete);
 423
 424           free(two_hop_to_delete);
 425
 426           /* This flag is set to OLSR_TRUE to recalculate the MPR set and the routing table*/
 427           changes_neighborhood = OLSR_TRUE;
 428           changes_topology = OLSR_TRUE;
 429
 430         }
 431       else
 432         two_hop_list = two_hop_list->next;
 433
 434     }
 435 }
 436
 437
 438
 439
 440
 441 void
 442 olsr_time_out_neighborhood_tables()
 443 {
 444   olsr_u8_t              index;
 445
 446   for(index=0;index<HASHSIZE;index++)
 447     {
 448       struct neighbor_entry *entry = neighbortable[index].next;
 449
 450       while(entry != &neighbortable[index])
 451         {
 452           olsr_time_out_two_hop_neighbors(entry);
 453           entry = entry->next;
 454         }
 455     }
 456 }
 457
 458
 459
 460
 461
 462 /**
 463  *Prints the registered neighbors and two hop neighbors
 464  *to STDOUT.
 465  *
 466  *@return nada
 467  */
 468 void
 469 olsr_print_neighbor_table()
 470 {
 471   int i;
 472   char *fstr;
 473
 474   olsr_printf(1, "\n--- %02d:%02d:%02d.%02d ------------------------------------------------ NEIGHBORS\n\n",
 475               nowtm->tm_hour,
 476               nowtm->tm_min,
 477               nowtm->tm_sec,
 478               now.tv_usec/10000);
 479
 480   if (olsr_cnf->ip_version == AF_INET)
 481   {
 482     olsr_printf(1, "IP address       LQ     NLQ    SYM   MPR   MPRS  will\n");
 483     fstr = "%-15s  %5.3f  %5.3f  %s  %s  %s  %d\n";
 484   }
 485
 486   else
 487   {
 488     olsr_printf(1, "IP address                               LQ     NLQ    SYM   MPR   MPRS  will\n");
 489     fstr = "%-39s  %5.3f  %5.3f  %s  %s  %s  %d\n";
 490   }
 491
 492   for (i = 0; i < HASHSIZE; i++)
 493     {
 494       struct neighbor_entry *neigh;
 495       for(neigh = neighbortable[i].next; neigh != &neighbortable[i];
 496           neigh = neigh->next)
 497         {
 498           struct link_entry *link = olsr_neighbor_best_link(&neigh->neighbor_main_addr);
 499           double best_lq = link->neigh_link_quality;
 500           double inv_best_lq = link->loss_link_quality;
 501
 502           olsr_printf(1, fstr, olsr_ip_to_string(&neigh->neighbor_main_addr),
 503                       inv_best_lq, best_lq,
 504                       (neigh->status == SYM) ? "YES " : "NO  ",
 505                       neigh->is_mpr ? "YES " : "NO  ",
 506                       olsr_lookup_mprs_set(&neigh->neighbor_main_addr) == NULL ? "NO  " : "YES ",
 507                       neigh->willingness);
 508         }
 509     }
 510 }
 511
 512
 513
 514
 515
 516
 517
 518
 519
 520