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.37 2007/11/29 18:10:14 bernd67 Exp $
  40  */
  41
  42 #include "ipcalc.h"
  43 #include "defs.h"
  44 #include "two_hop_neighbor_table.h"
  45 #include "mid_set.h"
  46 #include "mpr.h"
  47 #include "neighbor_table.h"
  48 #include "olsr.h"
  49 #include "scheduler.h"
  50 #include "link_set.h"
  51 #include "mpr_selector_set.h"
  52 #include "net_olsr.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, OLSR_TRUE);
  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       if(ipequal(&entry->neighbor_2->neighbor_2_addr, address))
  94         {
  95           /* Dequeue */
  96           DEQUEUE_ELEM(entry);
  97           /* Delete */
  98           free(entry);
  99           return 1;
 100         }
 101       entry = entry->next;
 102     }
 103   return 0;
 104 }
 105
 106
 107 /**
 108  *Check if a two hop neighbor is reachable via a given
 109  *neighbor.
 110  *
 111  *@param neighbor neighbor-entry to check via
 112  *@param neighbor_main_address the addres of the two hop neighbor
 113  *to find.
 114  *
 115  *@return a pointer to the neighbor_2_list_entry struct
 116  *representing the two hop neighbor if found. NULL if not found.
 117  */
 118 struct neighbor_2_list_entry *
 119 olsr_lookup_my_neighbors(const struct neighbor_entry *neighbor, const union olsr_ip_addr *neighbor_main_address)
 120 {
 121   struct neighbor_2_list_entry *entry;
 122
 123   for(entry = neighbor->neighbor_2_list.next;
 124       entry != &neighbor->neighbor_2_list;
 125       entry = entry->next)
 126     {
 127
 128       if(ipequal(&entry->neighbor_2->neighbor_2_addr, neighbor_main_address))
 129         return entry;
 130
 131     }
 132   return NULL;
 133 }
 134
 135
 136
 137 /**
 138  *Delete a neighbr table entry.
 139  *
 140  *Remember: Deleting a neighbor entry results
 141  *the deletion of its 2 hop neighbors list!!!
 142  *@param neighbor the neighbor entry to delete
 143  *
 144  *@return nada
 145  */
 146
 147 int
 148 olsr_delete_neighbor_table(const union olsr_ip_addr *neighbor_addr)
 149 {
 150   struct  neighbor_2_list_entry *two_hop_list, *two_hop_to_delete;
 151   olsr_u32_t                    hash;
 152   struct neighbor_entry         *entry;
 153
 154   //printf("inserting neighbor\n");
 155
 156   hash = olsr_hashing(neighbor_addr);
 157
 158   entry = neighbortable[hash].next;
 159
 160   /*
 161    * Find neighbor entry
 162    */
 163   while(entry != &neighbortable[hash])
 164     {
 165       if(ipequal(&entry->neighbor_main_addr, neighbor_addr))
 166         break;
 167
 168       entry = entry->next;
 169     }
 170
 171   if(entry == &neighbortable[hash])
 172     return 0;
 173
 174
 175   two_hop_list = entry->neighbor_2_list.next;
 176
 177   while(two_hop_list != &entry->neighbor_2_list)
 178     {
 179       struct neighbor_2_entry *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(const 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(ipequal(&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   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(const union olsr_ip_addr *dst)
 273 {
 274   /*
 275    *Find main address of node
 276    */
 277   union olsr_ip_addr *tmp_ip = mid_lookup_main_addr(dst);
 278   if(tmp_ip != NULL)
 279     dst = tmp_ip;
 280   return olsr_lookup_neighbor_table_alias(dst);
 281 }
 282
 283
 284 /**
 285  *Lookup a neighbor entry in the neighbortable based on an address.
 286  *
 287  *@param dst the IP address of the neighbor to look up
 288  *
 289  *@return a pointer to the neighbor struct registered on the given
 290  *address. NULL if not found.
 291  */
 292 struct neighbor_entry *
 293 olsr_lookup_neighbor_table_alias(const union olsr_ip_addr *dst)
 294 {
 295   struct neighbor_entry  *entry;
 296   olsr_u32_t             hash = olsr_hashing(dst);
 297
 298   //printf("\nLookup %s\n", olsr_ip_to_string(&buf, dst));
 299   for(entry = neighbortable[hash].next;
 300       entry != &neighbortable[hash];
 301       entry = entry->next)
 302     {
 303       //printf("Checking %s\n", olsr_ip_to_string(&buf, &entry->neighbor_main_addr));
 304       if(ipequal(&entry->neighbor_main_addr, dst))
 305         return entry;
 306
 307     }
 308   //printf("NOPE\n\n");
 309
 310   return NULL;
 311
 312 }
 313
 314
 315
 316 int
 317 update_neighbor_status(struct neighbor_entry *entry, int lnk)
 318 {
 319   /*
 320    * Update neighbor entry
 321    */
 322
 323   if(lnk == SYM_LINK)
 324     {
 325       /* N_status is set to SYM */
 326       if(entry->status == NOT_SYM)
 327         {
 328           struct neighbor_2_entry *two_hop_neighbor;
 329
 330           /* Delete posible 2 hop entry on this neighbor */
 331           if((two_hop_neighbor = olsr_lookup_two_hop_neighbor_table(&entry->neighbor_main_addr))!=NULL)
 332             {
 333               olsr_delete_two_hop_neighbor_table(two_hop_neighbor);
 334             }
 335
 336           changes_neighborhood = OLSR_TRUE;
 337           changes_topology = OLSR_TRUE;
 338           if(olsr_cnf->tc_redundancy > 1)
 339             signal_link_changes(OLSR_TRUE);
 340         }
 341       entry->status = SYM;
 342     }
 343   else
 344     {
 345       if(entry->status == SYM)
 346         {
 347           changes_neighborhood = OLSR_TRUE;
 348           changes_topology = OLSR_TRUE;
 349           if(olsr_cnf->tc_redundancy > 1)
 350             signal_link_changes(OLSR_TRUE);
 351         }
 352       /* else N_status is set to NOT_SYM */
 353       entry->status = NOT_SYM;
 354       /* remove neighbor from routing list */
 355     }
 356
 357   return entry->status;
 358 }
 359
 360
 361
 362 /**
 363  *Times out the entries in the two hop neighbor table and
 364  *deletes those who have exceeded their time to live since
 365  *last update.
 366  *
 367  *@return nada
 368  */
 369
 370 void
 371 olsr_time_out_two_hop_neighbors(struct neighbor_entry  *neighbor)
 372 {
 373   struct neighbor_2_list_entry *two_hop_list = neighbor->neighbor_2_list.next;
 374
 375   while(two_hop_list != &neighbor->neighbor_2_list)
 376     {
 377       if(TIMED_OUT(two_hop_list->neighbor_2_timer))
 378         {
 379           struct neighbor_2_list_entry *two_hop_to_delete;
 380           struct neighbor_2_entry      *two_hop_entry = two_hop_list->neighbor_2;
 381
 382           two_hop_entry->neighbor_2_pointer--;
 383           olsr_delete_neighbor_pointer(two_hop_entry, &neighbor->neighbor_main_addr);
 384
 385           if(two_hop_entry->neighbor_2_pointer < 1)
 386             {
 387               DEQUEUE_ELEM(two_hop_entry);
 388               free(two_hop_entry);
 389             }
 390
 391           two_hop_to_delete = two_hop_list;
 392           two_hop_list = two_hop_list->next;
 393
 394           /* Dequeue */
 395           DEQUEUE_ELEM(two_hop_to_delete);
 396
 397           free(two_hop_to_delete);
 398
 399           /* This flag is set to OLSR_TRUE to recalculate the MPR set and the routing table*/
 400           changes_neighborhood = OLSR_TRUE;
 401           changes_topology = OLSR_TRUE;
 402
 403         }
 404       else
 405         two_hop_list = two_hop_list->next;
 406
 407     }
 408 }
 409
 410 void
 411 olsr_time_out_neighborhood_tables(void)
 412 {
 413   int idx;
 414
 415   for(idx=0;idx<HASHSIZE;idx++)
 416     {
 417       struct neighbor_entry *entry;
 418       for(entry = neighbortable[idx].next; entry != &neighbortable[idx]; entry = entry->next)
 419         {
 420           olsr_time_out_two_hop_neighbors(entry);
 421         }
 422     }
 423 }
 424
 425 /**
 426  *Prints the registered neighbors and two hop neighbors
 427  *to STDOUT.
 428  *
 429  *@return nada
 430  */
 431 void
 432 olsr_print_neighbor_table(void)
 433 {
 434 #ifdef NODEBUG
 435   /* The whole function doesn't do anything else. */
 436 #ifndef NODEBUG
 437   const int iplen = olsr_cnf->ip_version == AF_INET ?  15 : 39;
 438 #endif
 439   int idx;
 440   OLSR_PRINTF(1, "\n--- %02d:%02d:%02d.%02d ------------------------------------------------ NEIGHBORS\n\n"
 441               "%*s  LQ     NLQ    SYM   MPR   MPRS  will\n",
 442               nowtm->tm_hour,
 443               nowtm->tm_min,
 444               nowtm->tm_sec,
 445               (int)now.tv_usec/10000,
 446               iplen,
 447               "IP address");
 448
 449   for (idx = 0; idx < HASHSIZE; idx++) {
 450     struct neighbor_entry *neigh;
 451     for(neigh = neighbortable[idx].next; neigh != &neighbortable[idx]; neigh = neigh->next) {
 452       struct link_entry *lnk = get_best_link_to_neighbor(&neigh->neighbor_main_addr);
 453       if(lnk) {
 454 #ifndef NODEBUG
 455         struct ipaddr_str buf;
 456 #endif
 457         OLSR_PRINTF(1, "%-*s  %5.3f  %5.3f  %s  %s  %s  %d\n",
 458                     iplen,
 459                     olsr_ip_to_string(&buf, &neigh->neighbor_main_addr),
 460                     lnk->loss_link_quality,
 461                     lnk->neigh_link_quality,
 462                     neigh->status == SYM ? "YES " : "NO  ",
 463                     neigh->is_mpr ? "YES " : "NO  ",
 464                     olsr_lookup_mprs_set(&neigh->neighbor_main_addr) == NULL ? "NO  " : "YES ",
 465                     neigh->willingness);
 466       }
 467     }
 468   }
 469 #endif
 470 }