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