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  */
  40
  41 #include "ipcalc.h"
  42 #include "defs.h"
  43 #include "two_hop_neighbor_table.h"
  44 #include "mid_set.h"
  45 #include "mpr.h"
  46 #include "neighbor_table.h"
  47 #include "olsr.h"
  48 #include "scheduler.h"
  49 #include "link_set.h"
  50 #include "mpr_selector_set.h"
  51 #include "net_olsr.h"
  52
  53
  54 struct neighbor_entry neighbortable[HASHSIZE];
  55
  56
  57 void
  58 olsr_init_neighbor_table(void)
  59 {
  60   int i;
  61
  62   for(i = 0; i < HASHSIZE; i++)
  63     {
  64       neighbortable[i].next = &neighbortable[i];
  65       neighbortable[i].prev = &neighbortable[i];
  66     }
  67 }
  68
  69 /**
  70  * Unlink, delete and free a nbr2_list entry.
  71  */
  72 static void
  73 olsr_del_nbr2_list(struct neighbor_2_list_entry *nbr2_list)
  74 {
  75   struct neighbor_entry *nbr;
  76   struct neighbor_2_entry *nbr2;
  77
  78   nbr = nbr2_list->nbr2_nbr;
  79   nbr2 = nbr2_list->neighbor_2;
  80
  81   if (nbr2->neighbor_2_pointer < 1) {
  82       DEQUEUE_ELEM(nbr2);
  83       free(nbr2);
  84   }
  85
  86   /*
  87    * Kill running timers.
  88    */
  89   olsr_stop_timer(nbr2_list->nbr2_list_timer);
  90   nbr2_list->nbr2_list_timer = NULL;
  91
  92   /* Dequeue */
  93   DEQUEUE_ELEM(nbr2_list);
  94
  95   free(nbr2_list);
  96
  97   /* Set flags to recalculate the MPR set and the routing table */
  98   changes_neighborhood = OLSR_TRUE;
  99   changes_topology = OLSR_TRUE;
 100 }
 101
 102 /**
 103  * Delete a two hop neighbor from a neighbors two hop neighbor list.
 104  *
 105  * @param neighbor the neighbor to delete the two hop neighbor from.
 106  * @param address the IP address of the two hop neighbor to delete.
 107  *
 108  * @return positive if entry deleted
 109  */
 110 int
 111 olsr_delete_neighbor_2_pointer(struct neighbor_entry *neighbor, union olsr_ip_addr *address)
 112 {
 113   struct neighbor_2_list_entry *nbr2_list;
 114
 115   nbr2_list = neighbor->neighbor_2_list.next;
 116
 117   while (nbr2_list != &neighbor->neighbor_2_list) {
 118     if (ipequal(&nbr2_list->neighbor_2->neighbor_2_addr, address)) {
 119       olsr_del_nbr2_list(nbr2_list);
 120       return 1;
 121     }
 122     nbr2_list = nbr2_list->next;
 123   }
 124   return 0;
 125 }
 126
 127
 128 /**
 129  *Check if a two hop neighbor is reachable via a given
 130  *neighbor.
 131  *
 132  *@param neighbor neighbor-entry to check via
 133  *@param neighbor_main_address the addres of the two hop neighbor
 134  *to find.
 135  *
 136  *@return a pointer to the neighbor_2_list_entry struct
 137  *representing the two hop neighbor if found. NULL if not found.
 138  */
 139 struct neighbor_2_list_entry *
 140 olsr_lookup_my_neighbors(const struct neighbor_entry *neighbor, const union olsr_ip_addr *neighbor_main_address)
 141 {
 142   struct neighbor_2_list_entry *entry;
 143
 144   for(entry = neighbor->neighbor_2_list.next;
 145       entry != &neighbor->neighbor_2_list;
 146       entry = entry->next)
 147     {
 148
 149       if(ipequal(&entry->neighbor_2->neighbor_2_addr, neighbor_main_address))
 150         return entry;
 151
 152     }
 153   return NULL;
 154 }
 155
 156
 157
 158 /**
 159  *Delete a neighbr table entry.
 160  *
 161  *Remember: Deleting a neighbor entry results
 162  *the deletion of its 2 hop neighbors list!!!
 163  *@param neighbor the neighbor entry to delete
 164  *
 165  *@return nada
 166  */
 167
 168 int
 169 olsr_delete_neighbor_table(const union olsr_ip_addr *neighbor_addr)
 170 {
 171   struct  neighbor_2_list_entry *two_hop_list, *two_hop_to_delete;
 172   olsr_u32_t                    hash;
 173   struct neighbor_entry         *entry;
 174
 175   //printf("inserting neighbor\n");
 176
 177   hash = olsr_ip_hashing(neighbor_addr);
 178
 179   entry = neighbortable[hash].next;
 180
 181   /*
 182    * Find neighbor entry
 183    */
 184   while(entry != &neighbortable[hash])
 185     {
 186       if(ipequal(&entry->neighbor_main_addr, neighbor_addr))
 187         break;
 188
 189       entry = entry->next;
 190     }
 191
 192   if(entry == &neighbortable[hash])
 193     return 0;
 194
 195
 196   two_hop_list = entry->neighbor_2_list.next;
 197
 198   while (two_hop_list != &entry->neighbor_2_list) {
 199       two_hop_to_delete = two_hop_list;
 200       two_hop_list = two_hop_list->next;
 201
 202       two_hop_to_delete->neighbor_2->neighbor_2_pointer--;
 203       olsr_delete_neighbor_pointer(two_hop_to_delete->neighbor_2,
 204                                    &entry->neighbor_main_addr);
 205
 206       olsr_del_nbr2_list(two_hop_to_delete);
 207     }
 208
 209
 210   /* Dequeue */
 211   DEQUEUE_ELEM(entry);
 212
 213   free(entry);
 214
 215   changes_neighborhood = OLSR_TRUE;
 216   return 1;
 217
 218 }
 219
 220
 221
 222 /**
 223  *Insert a neighbor entry in the neighbor table
 224  *
 225  *@param main_addr the main address of the new node
 226  *
 227  *@return 0 if neighbor already exists 1 if inserted
 228  */
 229 struct neighbor_entry *
 230 olsr_insert_neighbor_table(const union olsr_ip_addr *main_addr)
 231 {
 232   olsr_u32_t             hash;
 233   struct neighbor_entry  *new_neigh;
 234
 235   hash = olsr_ip_hashing(main_addr);
 236
 237   /* Check if entry exists */
 238
 239   for(new_neigh = neighbortable[hash].next;
 240       new_neigh != &neighbortable[hash];
 241       new_neigh = new_neigh->next)
 242     {
 243       if(ipequal(&new_neigh->neighbor_main_addr, main_addr))
 244         return new_neigh;
 245     }
 246
 247   //printf("inserting neighbor\n");
 248
 249   new_neigh = olsr_malloc(sizeof(struct neighbor_entry), "New neighbor entry");
 250
 251   /* Set address, willingness and status */
 252   new_neigh->neighbor_main_addr = *main_addr;
 253   new_neigh->willingness = WILL_NEVER;
 254   new_neigh->status = NOT_SYM;
 255
 256   new_neigh->neighbor_2_list.next = &new_neigh->neighbor_2_list;
 257   new_neigh->neighbor_2_list.prev = &new_neigh->neighbor_2_list;
 258
 259   new_neigh->linkcount = 0;
 260   new_neigh->is_mpr = OLSR_FALSE;
 261   new_neigh->was_mpr = OLSR_FALSE;
 262
 263   /* Queue */
 264   QUEUE_ELEM(neighbortable[hash], new_neigh);
 265
 266   return new_neigh;
 267 }
 268
 269
 270
 271 /**
 272  *Lookup a neighbor entry in the neighbortable based on an address.
 273  *
 274  *@param dst the IP address of the neighbor to look up
 275  *
 276  *@return a pointer to the neighbor struct registered on the given
 277  *address. NULL if not found.
 278  */
 279 struct neighbor_entry *
 280 olsr_lookup_neighbor_table(const union olsr_ip_addr *dst)
 281 {
 282   /*
 283    *Find main address of node
 284    */
 285   union olsr_ip_addr *tmp_ip = mid_lookup_main_addr(dst);
 286   if(tmp_ip != NULL)
 287     dst = tmp_ip;
 288   return olsr_lookup_neighbor_table_alias(dst);
 289 }
 290
 291
 292 /**
 293  *Lookup a neighbor entry in the neighbortable based on an address.
 294  *
 295  *@param dst the IP address of the neighbor to look up
 296  *
 297  *@return a pointer to the neighbor struct registered on the given
 298  *address. NULL if not found.
 299  */
 300 struct neighbor_entry *
 301 olsr_lookup_neighbor_table_alias(const union olsr_ip_addr *dst)
 302 {
 303   struct neighbor_entry  *entry;
 304   olsr_u32_t             hash = olsr_ip_hashing(dst);
 305
 306   //printf("\nLookup %s\n", olsr_ip_to_string(&buf, dst));
 307   for(entry = neighbortable[hash].next;
 308       entry != &neighbortable[hash];
 309       entry = entry->next)
 310     {
 311       //printf("Checking %s\n", olsr_ip_to_string(&buf, &entry->neighbor_main_addr));
 312       if(ipequal(&entry->neighbor_main_addr, dst))
 313         return entry;
 314
 315     }
 316   //printf("NOPE\n\n");
 317
 318   return NULL;
 319
 320 }
 321
 322
 323
 324 int
 325 update_neighbor_status(struct neighbor_entry *entry, int lnk)
 326 {
 327   /*
 328    * Update neighbor entry
 329    */
 330
 331   if(lnk == SYM_LINK)
 332     {
 333       /* N_status is set to SYM */
 334       if(entry->status == NOT_SYM)
 335         {
 336           struct neighbor_2_entry *two_hop_neighbor;
 337
 338           /* Delete posible 2 hop entry on this neighbor */
 339           if((two_hop_neighbor = olsr_lookup_two_hop_neighbor_table(&entry->neighbor_main_addr))!=NULL)
 340             {
 341               olsr_delete_two_hop_neighbor_table(two_hop_neighbor);
 342             }
 343
 344           changes_neighborhood = OLSR_TRUE;
 345           changes_topology = OLSR_TRUE;
 346           if(olsr_cnf->tc_redundancy > 1)
 347             signal_link_changes(OLSR_TRUE);
 348         }
 349       entry->status = SYM;
 350     }
 351   else
 352     {
 353       if(entry->status == SYM)
 354         {
 355           changes_neighborhood = OLSR_TRUE;
 356           changes_topology = OLSR_TRUE;
 357           if(olsr_cnf->tc_redundancy > 1)
 358             signal_link_changes(OLSR_TRUE);
 359         }
 360       /* else N_status is set to NOT_SYM */
 361       entry->status = NOT_SYM;
 362       /* remove neighbor from routing list */
 363     }
 364
 365   return entry->status;
 366 }
 367
 368
 369 /**
 370  * Callback for the nbr2_list timer.
 371  */
 372 void
 373 olsr_expire_nbr2_list(void *context)
 374 {
 375   struct neighbor_2_list_entry *nbr2_list;
 376   struct neighbor_entry *nbr;
 377   struct neighbor_2_entry *nbr2;
 378
 379   nbr2_list = (struct neighbor_2_list_entry *)context;
 380   nbr2_list->nbr2_list_timer = NULL;
 381
 382   nbr = nbr2_list->nbr2_nbr;
 383   nbr2 = nbr2_list->neighbor_2;
 384
 385   nbr2->neighbor_2_pointer--;
 386   olsr_delete_neighbor_pointer(nbr2, &nbr->neighbor_main_addr);
 387
 388   olsr_del_nbr2_list(nbr2_list);
 389 }
 390
 391
 392 /**
 393  *Prints the registered neighbors and two hop neighbors
 394  *to STDOUT.
 395  *
 396  *@return nada
 397  */
 398 void
 399 olsr_print_neighbor_table(void)
 400 {
 401 #ifdef NODEBUG
 402   /* The whole function doesn't do anything else. */
 403 #ifndef NODEBUG
 404   const int iplen = olsr_cnf->ip_version == AF_INET ?  15 : 39;
 405 #endif
 406   int idx;
 407   OLSR_PRINTF(1, "\n--- %02d:%02d:%02d.%02d ------------------------------------------------ NEIGHBORS\n\n"
 408               "%*s  LQ     NLQ    SYM   MPR   MPRS  will\n",
 409               nowtm->tm_hour,
 410               nowtm->tm_min,
 411               nowtm->tm_sec,
 412               (int)now.tv_usec/10000,
 413               iplen,
 414               "IP address");
 415
 416   for (idx = 0; idx < HASHSIZE; idx++) {
 417     struct neighbor_entry *neigh;
 418     for(neigh = neighbortable[idx].next; neigh != &neighbortable[idx]; neigh = neigh->next) {
 419       struct link_entry *lnk = get_best_link_to_neighbor(&neigh->neighbor_main_addr);
 420       if(lnk) {
 421 #ifndef NODEBUG
 422         struct ipaddr_str buf;
 423 #endif
 424         OLSR_PRINTF(1, "%-*s  %5.3f  %5.3f  %s  %s  %s  %d\n",
 425                     iplen,
 426                     olsr_ip_to_string(&buf, &neigh->neighbor_main_addr),
 427                     lnk->loss_link_quality,
 428                     lnk->neigh_link_quality,
 429                     neigh->status == SYM ? "YES " : "NO  ",
 430                     neigh->is_mpr ? "YES " : "NO  ",
 431                     olsr_lookup_mprs_set(&neigh->neighbor_main_addr) == NULL ? "NO  " : "YES ",
 432                     neigh->willingness);
 433       }
 434     }
 435   }
 436 #endif
 437 }
 438
 439 /*
 440  * Local Variables:
 441  * c-basic-offset: 2
 442  * End:
 443  */