src/neighbor_table.c

   1 /*
   2  * OLSR ad-hoc routing table management protocol
   3  * Copyright (C) 2003 Andreas Tønnesen (andreto@ifi.uio.no)
   4  *
   5  * This file is part of the olsr.org OLSR daemon.
   6  *
   7  * olsr.org is free software; you can redistribute it and/or modify
   8  * it under the terms of the GNU General Public License as published by
   9  * the Free Software Foundation; either version 2 of the License, or
  10  * (at your option) any later version.
  11  *
  12  * olsr.org is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  * GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with olsr.org; if not, write to the Free Software
  19  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  20  *
  21  *
  22  * $Id: neighbor_table.c,v 1.10 2004/11/05 11:52:55 kattemat Exp $
  23  *
  24  */
  25
  26
  27
  28
  29 #include "defs.h"
  30 #include "two_hop_neighbor_table.h"
  31 #include "mid_set.h"
  32 #include "mpr.h"
  33 #include "olsr.h"
  34 #include "scheduler.h"
  35
  36 void
  37 olsr_init_neighbor_table()
  38 {
  39   int i;
  40
  41   olsr_register_timeout_function(&olsr_time_out_neighborhood_tables);
  42
  43   for(i = 0; i < HASHSIZE; i++)
  44     {
  45       neighbortable[i].next = &neighbortable[i];
  46       neighbortable[i].prev = &neighbortable[i];
  47     }
  48 }
  49
  50
  51 /**
  52  *Delete a two hop neighbor from a neighbors two
  53  *hop neighbor list.
  54  *
  55  *@param neighbor the neighbor to delete the two hop
  56  *neighbor from.
  57  *@param address the IP address of the two hop neighbor
  58  *to delete.
  59  *
  60  *@return positive if entry deleted
  61  */
  62 int
  63 olsr_delete_neighbor_2_pointer(struct neighbor_entry *neighbor, union olsr_ip_addr *address)
  64 {
  65
  66   struct neighbor_2_list_entry *entry;
  67
  68   entry = neighbor->neighbor_2_list.next;
  69
  70   while(entry != &neighbor->neighbor_2_list)
  71     {
  72
  73       if(COMP_IP(&entry->neighbor_2->neighbor_2_addr, address))
  74         {
  75           /* Dequeue */
  76           DEQUEUE_ELEM(entry);
  77           /* Delete */
  78           free(entry);
  79           return 1;
  80         }
  81       entry = entry->next;
  82     }
  83   return 0;
  84 }
  85
  86
  87 /**
  88  *Check if a two hop neighbor is reachable via a given
  89  *neighbor.
  90  *
  91  *@param neighbor neighbor-entry to check via
  92  *@param neighbor_main_address the addres of the two hop neighbor
  93  *to find.
  94  *
  95  *@return a pointer to the neighbor_2_list_entry struct
  96  *representing the two hop neighbor if found. NULL if not found.
  97  */
  98 struct neighbor_2_list_entry *
  99 olsr_lookup_my_neighbors(struct neighbor_entry *neighbor, union olsr_ip_addr *neighbor_main_address)
 100 {
 101
 102   struct neighbor_2_list_entry *entry;
 103
 104   for(entry = neighbor->neighbor_2_list.next;
 105       entry != &neighbor->neighbor_2_list;
 106       entry = entry->next)
 107     {
 108
 109       if(COMP_IP(&entry->neighbor_2->neighbor_2_addr, neighbor_main_address))
 110         return entry;
 111
 112     }
 113   return NULL;
 114 }
 115
 116
 117
 118 /**
 119  *Delete a neighbr table entry.
 120  *
 121  *Remember: Deleting a neighbor entry results
 122  *the deletion of its 2 hop neighbors list!!!
 123  *@param neighbor the neighbor entry to delete
 124  *
 125  *@return nada
 126  */
 127
 128 int
 129 olsr_delete_neighbor_table(union olsr_ip_addr *neighbor_addr)
 130 {
 131   struct  neighbor_2_list_entry *two_hop_list, *two_hop_to_delete;
 132   struct  neighbor_2_entry      *two_hop_entry;
 133   olsr_u32_t                    hash;
 134   struct neighbor_entry         *entry;
 135
 136   //printf("inserting neighbor\n");
 137
 138   hash = olsr_hashing(neighbor_addr);
 139
 140   entry = neighbortable[hash].next;
 141
 142   /*
 143    * Find neighbor entry
 144    */
 145   while(entry != &neighbortable[hash])
 146     {
 147       if(COMP_IP(&entry->neighbor_main_addr, neighbor_addr))
 148         break;
 149
 150       entry = entry->next;
 151     }
 152
 153   if(entry == &neighbortable[hash])
 154     return 0;
 155
 156
 157   two_hop_list = entry->neighbor_2_list.next;
 158
 159   while(two_hop_list != &entry->neighbor_2_list)
 160     {
 161       two_hop_entry = two_hop_list->neighbor_2;
 162
 163       two_hop_entry->neighbor_2_pointer--;
 164
 165       olsr_delete_neighbor_pointer(two_hop_entry, &entry->neighbor_main_addr);
 166
 167       /* Delete entry if it has no more one hop neighbors pointing to it */
 168       if(two_hop_entry->neighbor_2_pointer < 1)
 169         {
 170           DEQUEUE_ELEM(two_hop_entry);
 171
 172           free(two_hop_entry);
 173         }
 174
 175
 176       two_hop_to_delete = two_hop_list;
 177       two_hop_list = two_hop_list->next;
 178       /* Delete entry */
 179       free(two_hop_to_delete);
 180
 181     }
 182
 183
 184   /* Dequeue */
 185   DEQUEUE_ELEM(entry);
 186
 187   free(entry);
 188
 189   changes_neighborhood = OLSR_TRUE;
 190   return 1;
 191
 192 }
 193
 194
 195
 196 /**
 197  *Insert a neighbor entry in the neighbor table
 198  *
 199  *@param main_addr the main address of the new node
 200  *
 201  *@return 0 if neighbor already exists 1 if inserted
 202  */
 203 struct neighbor_entry *
 204 olsr_insert_neighbor_table(union olsr_ip_addr *main_addr)
 205 {
 206   olsr_u32_t             hash;
 207   struct neighbor_entry  *new_neigh;
 208
 209   hash = olsr_hashing(main_addr);
 210
 211   /* Check if entry exists */
 212
 213   for(new_neigh = neighbortable[hash].next;
 214       new_neigh != &neighbortable[hash];
 215       new_neigh = new_neigh->next)
 216     {
 217       if(COMP_IP(&new_neigh->neighbor_main_addr, main_addr))
 218         return new_neigh;
 219     }
 220
 221   //printf("inserting neighbor\n");
 222
 223   new_neigh = olsr_malloc(sizeof(struct neighbor_entry), "New neighbor entry");
 224
 225   /* Set address, willingness and status */
 226   COPY_IP(&new_neigh->neighbor_main_addr, main_addr);
 227   new_neigh->willingness = WILL_NEVER;
 228   new_neigh->status = NOT_SYM;
 229
 230   new_neigh->neighbor_2_list.next = &new_neigh->neighbor_2_list;
 231   new_neigh->neighbor_2_list.prev = &new_neigh->neighbor_2_list;
 232
 233   new_neigh->linkcount = 0;
 234   new_neigh->is_mpr = OLSR_FALSE;
 235   new_neigh->was_mpr = OLSR_FALSE;
 236
 237   /* Queue */
 238   QUEUE_ELEM(neighbortable[hash], new_neigh);
 239
 240   return new_neigh;
 241 }
 242
 243
 244
 245 /**
 246  *Lookup a neighbor entry in the neighbortable based on an address.
 247  *
 248  *@param dst the IP address of the neighbor to look up
 249  *
 250  *@return a pointer to the neighbor struct registered on the given
 251  *address. NULL if not found.
 252  */
 253 struct neighbor_entry *
 254 olsr_lookup_neighbor_table(union olsr_ip_addr *dst)
 255 {
 256   struct neighbor_entry  *entry;
 257   olsr_u32_t             hash;
 258   //struct addresses       *adr;
 259   union olsr_ip_addr     *tmp_ip;
 260
 261   /*
 262    *Find main address of node
 263    */
 264   if((tmp_ip = mid_lookup_main_addr(dst)) != NULL)
 265     dst = tmp_ip;
 266
 267   hash = olsr_hashing(dst);
 268
 269
 270   //printf("\nLookup %s\n", olsr_ip_to_string(dst));
 271   for(entry = neighbortable[hash].next;
 272       entry != &neighbortable[hash];
 273       entry = entry->next)
 274     {
 275       //printf("Checking %s\n", olsr_ip_to_string(&neighbor_table_tmp->neighbor_main_addr));
 276       if(COMP_IP(&entry->neighbor_main_addr, dst))
 277         return entry;
 278
 279     }
 280   //printf("NOPE\n\n");
 281
 282   return NULL;
 283
 284 }
 285
 286
 287 /**
 288  *Lookup a neighbor entry in the neighbortable based on an address.
 289  *
 290  *@param dst the IP address of the neighbor to look up
 291  *
 292  *@return a pointer to the neighbor struct registered on the given
 293  *address. NULL if not found.
 294  */
 295 struct neighbor_entry *
 296 olsr_lookup_neighbor_table_alias(union olsr_ip_addr *dst)
 297 {
 298   struct neighbor_entry  *entry;
 299   olsr_u32_t             hash;
 300   //struct addresses       *adr;
 301
 302   hash = olsr_hashing(dst);
 303
 304
 305   //printf("\nLookup %s\n", olsr_ip_to_string(dst));
 306   for(entry = neighbortable[hash].next;
 307       entry != &neighbortable[hash];
 308       entry = entry->next)
 309     {
 310       //printf("Checking %s\n", olsr_ip_to_string(&neighbor_table_tmp->neighbor_main_addr));
 311       if(COMP_IP(&entry->neighbor_main_addr, dst))
 312         return entry;
 313
 314     }
 315   //printf("NOPE\n\n");
 316
 317   return NULL;
 318
 319 }
 320
 321
 322
 323 int
 324 update_neighbor_status(struct neighbor_entry *entry, int link)
 325 {
 326   struct neighbor_2_entry *two_hop_neighbor;
 327
 328   /*
 329    * Update neighbor entry
 330    */
 331
 332   if(link == SYM_LINK)
 333     {
 334       /* N_status is set to SYM */
 335       if(entry->status == NOT_SYM)
 336         {
 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             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             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 /**
 371  *Times out the entries in the two hop neighbor table and
 372  *deletes those who have exceeded their time to live since
 373  *last update.
 374  *
 375  *@return nada
 376  */
 377
 378 void
 379 olsr_time_out_two_hop_neighbors(struct neighbor_entry  *neighbor)
 380 {
 381   struct  neighbor_2_list_entry *two_hop_list, *two_hop_to_delete;
 382   struct  neighbor_2_entry      *two_hop_entry;
 383
 384
 385   two_hop_list = neighbor->neighbor_2_list.next;
 386
 387   //neighbor->neighbor_2_list = NULL;
 388
 389   while(two_hop_list != &neighbor->neighbor_2_list)
 390     {
 391       if(TIMED_OUT(&two_hop_list->neighbor_2_timer))
 392         {
 393           two_hop_entry = two_hop_list->neighbor_2;
 394           two_hop_entry->neighbor_2_pointer--;
 395           olsr_delete_neighbor_pointer(two_hop_entry, &neighbor->neighbor_main_addr);
 396
 397           if(two_hop_entry->neighbor_2_pointer < 1)
 398             {
 399               /* FIX THIS (fix what?)*/
 400               DEQUEUE_ELEM(two_hop_entry);
 401
 402               free((void *)two_hop_entry);
 403             }
 404
 405           two_hop_to_delete = two_hop_list;
 406           two_hop_list = two_hop_list->next;
 407
 408           /* Dequeue */
 409           DEQUEUE_ELEM(two_hop_to_delete);
 410
 411           free(two_hop_to_delete);
 412
 413           /* This flag is set to OLSR_TRUE to recalculate the MPR set and the routing table*/
 414           changes_neighborhood = OLSR_TRUE;
 415           changes_topology = OLSR_TRUE;
 416
 417         }
 418       else
 419         two_hop_list = two_hop_list->next;
 420
 421     }
 422 }
 423
 424
 425
 426
 427
 428 void
 429 olsr_time_out_neighborhood_tables()
 430 {
 431   olsr_u8_t              index;
 432   struct neighbor_entry  *entry;
 433
 434   for(index=0;index<HASHSIZE;index++)
 435     {
 436       entry = neighbortable[index].next;
 437
 438       while(entry != &neighbortable[index])
 439         {
 440           olsr_time_out_two_hop_neighbors(entry);
 441
 442           entry = entry->next;
 443         }
 444     }
 445 }
 446
 447
 448
 449
 450
 451 /**
 452  *Prints the registered neighbors and two hop neighbors
 453  *to STDOUT.
 454  *
 455  *@return nada
 456  */
 457 void
 458 olsr_print_neighbor_table()
 459 {
 460   olsr_u8_t                    index;
 461   struct neighbor_entry        *neighbor_table_tmp;
 462   struct neighbor_2_list_entry *list_2;
 463
 464
 465
 466   olsr_printf(1, "Neighbor list(%02d:%02d:%02d.%06lu):\n",
 467               nowtm->tm_hour,
 468               nowtm->tm_min,
 469               nowtm->tm_sec,
 470               now.tv_usec);
 471
 472   for(index=0;index<HASHSIZE;index++)
 473     {
 474
 475       for(neighbor_table_tmp = neighbortable[index].next;
 476           neighbor_table_tmp != &neighbortable[index];
 477           neighbor_table_tmp = neighbor_table_tmp->next)
 478         {
 479           olsr_printf(1, "%s:l=%d:m=%d:w=%d[2hlist:",
 480                       olsr_ip_to_string(&neighbor_table_tmp->neighbor_main_addr),
 481                       neighbor_table_tmp->status, neighbor_table_tmp->is_mpr, neighbor_table_tmp->willingness);
 482
 483           for(list_2 = neighbor_table_tmp->neighbor_2_list.next;
 484               list_2 != &neighbor_table_tmp->neighbor_2_list;
 485               list_2 = list_2->next)
 486             {
 487               olsr_printf(1, "%s:", olsr_ip_to_string(&list_2->neighbor_2->neighbor_2_addr));
 488             }
 489           olsr_printf(1, "]\n");
 490
 491         }
 492     }
 493 }
 494
 495
 496
 497
 498
 499
 500
 501
 502
 503