src/mid_set.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: mid_set.c,v 1.12 2005/01/22 00:09:18 kattemat Exp $
  40  */
  41
  42 #include "defs.h"
  43 #include "two_hop_neighbor_table.h"
  44 #include "mid_set.h"
  45 #include "olsr.h"
  46 #include "scheduler.h"
  47 #include "neighbor_table.h"
  48 #include "link_set.h"
  49
  50 /**
  51  * Initialize the MID set
  52  *
  53  */
  54
  55 int
  56 olsr_init_mid_set()
  57 {
  58   int index;
  59
  60   olsr_printf(5, "MID: init\n");
  61
  62   /* Since the holdingtime is assumed to be rather large for
  63    * MID entries, the timeoutfunction is only ran once every second
  64    */
  65   olsr_register_scheduler_event(&olsr_time_out_mid_set, NULL, 1, 0, NULL);
  66
  67   for(index=0;index<HASHSIZE;index++)
  68     {
  69       mid_set[index].next = &mid_set[index];
  70       mid_set[index].prev = &mid_set[index];
  71
  72       reverse_mid_set[index].next = &reverse_mid_set[index];
  73       reverse_mid_set[index].prev = &reverse_mid_set[index];
  74     }
  75
  76   return 1;
  77 }
  78
  79
  80 /**
  81  *Insert a new interface alias to the interface association set.
  82  *If the main interface of the association is not yet registered
  83  *in the set a new entry is created.
  84  *
  85  *@param m_addr the main address of the node
  86  *@param alias the alias address to insert
  87  *
  88  *@return nada
  89  */
  90
  91 void
  92 insert_mid_tuple(union olsr_ip_addr *m_addr, struct mid_address *alias, float vtime)
  93 {
  94   struct mid_entry *tmp;
  95   struct mid_address *tmp_adr;
  96   olsr_u32_t hash, alias_hash;
  97
  98   hash = olsr_hashing(m_addr);
  99   alias_hash = olsr_hashing(&alias->alias);
 100
 101   /* Check for registered entry */
 102   for(tmp = mid_set[hash].next;
 103       tmp != &mid_set[hash];
 104       tmp = tmp->next)
 105     {
 106       if(COMP_IP(&tmp->main_addr, m_addr))
 107         break;
 108     }
 109
 110   /*If the address was registered*/
 111   if(tmp != &mid_set[hash])
 112     {
 113       tmp_adr = tmp->aliases;
 114       tmp->aliases = alias;
 115       alias->main_entry = tmp;
 116       QUEUE_ELEM(reverse_mid_set[alias_hash], alias);
 117       alias->next_alias = tmp_adr;
 118       tmp->ass_timer = GET_TIMESTAMP(vtime*1000);
 119     }
 120       /*Create new node*/
 121   else
 122     {
 123       tmp = olsr_malloc(sizeof(struct mid_entry), "MID new alias");
 124
 125       tmp->aliases = alias;
 126       alias->main_entry = tmp;
 127       QUEUE_ELEM(reverse_mid_set[alias_hash], alias);
 128       COPY_IP(&tmp->main_addr, m_addr);
 129       tmp->ass_timer = GET_TIMESTAMP(vtime*1000);
 130       /* Queue */
 131       QUEUE_ELEM(mid_set[hash], tmp);
 132     }
 133
 134
 135
 136   /*
 137    * Delete possible duplicate entries in 2 hop set
 138    * and delete duplicate neighbor entries. Redirect
 139    * link entries to the correct neighbor entry.
 140    *
 141    *THIS OPTIMIZATION IS NOT SPECIFIED IN RFC3626
 142    */
 143
 144   tmp_adr = alias;
 145
 146   while(tmp_adr)
 147     {
 148       struct neighbor_2_entry *tmp_2_neighbor;
 149       struct neighbor_entry *tmp_neigh, *real_neigh;
 150
 151       /* Delete possible 2 hop neighbor */
 152       if((tmp_2_neighbor = olsr_lookup_two_hop_neighbor_table_mid(&tmp_adr->alias)) != NULL)
 153         {
 154           olsr_printf(1, "Deleting 2 hop node from MID: %s to ", olsr_ip_to_string(&tmp_adr->alias));
 155           olsr_printf(1, "%s\n", olsr_ip_to_string(m_addr));
 156
 157           olsr_delete_two_hop_neighbor_table(tmp_2_neighbor);
 158
 159           changes_neighborhood = OLSR_TRUE;
 160         }
 161
 162       /* Delete a possible neighbor entry */
 163       if(((tmp_neigh = olsr_lookup_neighbor_table_alias(&tmp_adr->alias)) != NULL)
 164          && ((real_neigh = olsr_lookup_neighbor_table_alias(m_addr)) != NULL))
 165
 166         {
 167           olsr_printf(1, "[MID]Deleting bogus neighbor entry %s real ", olsr_ip_to_string(&tmp_adr->alias));
 168           olsr_printf(1, "%s\n", olsr_ip_to_string(m_addr));
 169
 170           replace_neighbor_link_set(tmp_neigh, real_neigh);
 171
 172           /* Dequeue */
 173           DEQUEUE_ELEM(tmp_neigh);
 174           /* Delete */
 175           free(tmp_neigh);
 176
 177           changes_neighborhood = OLSR_TRUE;
 178         }
 179
 180       tmp_adr = tmp_adr->next_alias;
 181     }
 182
 183
 184 }
 185
 186
 187 /**
 188  *Insert an alias address for a node.
 189  *If the main address is not registered
 190  *then a new entry is created.
 191  *
 192  *@param main_add the main address of the node
 193  *@param alias the alias address to insert
 194  *@param seq the sequence number to register a new node with
 195  *
 196  *@return nada
 197  */
 198 void
 199 insert_mid_alias(union olsr_ip_addr *main_add, union olsr_ip_addr *alias, float vtime)
 200 {
 201   struct mid_address *adr;
 202
 203   adr = olsr_malloc(sizeof(struct mid_address), "Insert MID alias");
 204
 205   olsr_printf(1, "Inserting alias %s for ", olsr_ip_to_string(alias));
 206   olsr_printf(1, "%s\n", olsr_ip_to_string(main_add));
 207
 208   COPY_IP(&adr->alias, alias);
 209   adr->next_alias = NULL;
 210
 211   insert_mid_tuple(main_add, adr, vtime);
 212
 213   /*
 214    *Recalculate topology
 215    */
 216   changes_neighborhood = OLSR_TRUE;
 217   changes_topology = OLSR_TRUE;
 218
 219   //print_mid_list();
 220 }
 221
 222
 223
 224
 225 /**
 226  *Lookup the main address for a alias address
 227  *
 228  *@param adr the alias address to check
 229  *
 230  *@return the main address registered on the alias
 231  *or NULL if not found
 232  */
 233 union olsr_ip_addr *
 234 mid_lookup_main_addr(union olsr_ip_addr *adr)
 235 {
 236   olsr_u32_t hash;
 237   struct mid_address *tmp_list;
 238
 239 #warning MID SET NOW HAS REVERSE INDEXING!
 240   hash = olsr_hashing(adr);
 241   /*Traverse MID list*/
 242   for(tmp_list = reverse_mid_set[hash].next;
 243       tmp_list != &reverse_mid_set[hash];
 244       tmp_list = tmp_list->next)
 245         {
 246           if(COMP_IP(&tmp_list->alias, adr))
 247             return &tmp_list->main_entry->main_addr;
 248         }
 249   return NULL;
 250
 251 }
 252
 253
 254
 255
 256 /*
 257  *Find all aliases for an address.
 258  *
 259  *@param adr the main address to search for
 260  *
 261  *@return a linked list of addresses structs
 262  */
 263 struct mid_address *
 264 mid_lookup_aliases(union olsr_ip_addr *adr)
 265 {
 266   struct mid_entry *tmp_list;
 267   olsr_u32_t hash;
 268
 269   //olsr_printf(1, "MID: lookup entry...");
 270
 271   hash = olsr_hashing(adr);
 272
 273   /* Check all registered nodes...*/
 274   for(tmp_list = mid_set[hash].next;
 275       tmp_list != &mid_set[hash];
 276       tmp_list = tmp_list->next)
 277     {
 278       if(COMP_IP(&tmp_list->main_addr, adr))
 279         return tmp_list->aliases;
 280     }
 281
 282
 283   return NULL;
 284 }
 285
 286
 287 /**
 288  *Update the timer for an entry
 289  *
 290  *@param adr the main address of the entry
 291  *
 292  *@return 1 if the node was updated, 0 if not
 293  */
 294 int
 295 olsr_update_mid_table(union olsr_ip_addr *adr, float vtime)
 296 {
 297   struct mid_entry *tmp_list = mid_set;
 298   olsr_u32_t hash;
 299
 300   olsr_printf(3, "MID: update %s\n", olsr_ip_to_string(adr));
 301   hash = olsr_hashing(adr);
 302
 303   /* Check all registered nodes...*/
 304   for(tmp_list = mid_set[hash].next;
 305       tmp_list != &mid_set[hash];
 306       tmp_list = tmp_list->next)
 307     {
 308       /*find match*/
 309       if(COMP_IP(&tmp_list->main_addr, adr))
 310         {
 311           //printf("Updating timer for node %s\n",ip_to_string(&tmp_list->main_addr));
 312           tmp_list->ass_timer = GET_TIMESTAMP(vtime*1000);
 313
 314           return 1;
 315         }
 316     }
 317   return 0;
 318 }
 319
 320
 321
 322 /**
 323  *Find timed out entries and delete them
 324  *
 325  *@return nada
 326  */
 327 void
 328 olsr_time_out_mid_set(void *foo)
 329 {
 330   int index;
 331
 332
 333   for(index=0;index<HASHSIZE;index++)
 334     {
 335       struct mid_entry *tmp_list = mid_set[index].next;
 336       /*Traverse MID list*/
 337       while(tmp_list != &mid_set[index])
 338         {
 339           /*Check if the entry is timed out*/
 340           if(TIMED_OUT(tmp_list->ass_timer))
 341             {
 342               struct mid_entry *entry_to_delete = tmp_list;
 343               tmp_list = tmp_list->next;
 344 #ifdef DEBUG
 345               olsr_printf(1, "MID info for %s timed out.. deleting it\n",
 346                           olsr_ip_to_string(&entry_to_delete->main_addr));
 347 #endif
 348               /*Delete it*/
 349               mid_delete_node(entry_to_delete);
 350             }
 351           else
 352               tmp_list = tmp_list->next;
 353         }
 354     }
 355
 356   return;
 357 }
 358
 359
 360 /*
 361  *Delete an entry
 362  *
 363  *@param entry the entry to delete
 364  *
 365  *@return 1
 366  */
 367 int
 368 mid_delete_node(struct mid_entry *entry)
 369 {
 370   struct mid_address *aliases;
 371
 372   /* Free aliases */
 373   aliases = entry->aliases;
 374   while(aliases)
 375     {
 376       struct mid_address *tmp_aliases = aliases;
 377       aliases = aliases->next_alias;
 378       DEQUEUE_ELEM(tmp_aliases);
 379       free(tmp_aliases);
 380     }
 381   /* Dequeue */
 382   DEQUEUE_ELEM(entry);
 383   free(entry);
 384
 385   return 0;
 386 }
 387
 388
 389 /**
 390  *Print all multiple interface info
 391  *For debuging purposes
 392  */
 393 void
 394 olsr_print_mid_set()
 395 {
 396
 397   int index;
 398
 399   olsr_printf(1, "mid set: %02d:%02d:%02d.%06lu\n",nowtm->tm_hour, nowtm->tm_min, nowtm->tm_sec, now.tv_usec);
 400
 401   for(index=0;index<HASHSIZE;index++)
 402     {
 403       struct mid_entry *tmp_list = mid_set[index].next;
 404       /*Traverse MID list*/
 405       for(tmp_list = mid_set[index].next;
 406           tmp_list != &mid_set[index];
 407           tmp_list = tmp_list->next)
 408         {
 409           struct mid_address *tmp_addr = tmp_list->aliases;
 410
 411           olsr_printf(1, "%s: ", olsr_ip_to_string(&tmp_list->main_addr));
 412           while(tmp_addr)
 413             {
 414               olsr_printf(1, " %s ", olsr_ip_to_string(&tmp_addr->alias));
 415               tmp_addr = tmp_addr->next_alias;
 416             }
 417           olsr_printf(1, "\n");
 418
 419         }
 420     }
 421
 422 }
 423
 424
 425
 426
 427