src/mid_set.c

   1
   2 /*
   3  * The olsr.org Optimized Link-State Routing daemon(olsrd)
   4  * Copyright (c) 2004, Andreas Tonnesen(andreto@olsr.org)
   5  * All rights reserved.
   6  *
   7  * Redistribution and use in source and binary forms, with or without
   8  * modification, are permitted provided that the following conditions
   9  * are met:
  10  *
  11  * * Redistributions of source code must retain the above copyright
  12  *   notice, this list of conditions and the following disclaimer.
  13  * * Redistributions in binary form must reproduce the above copyright
  14  *   notice, this list of conditions and the following disclaimer in
  15  *   the documentation and/or other materials provided with the
  16  *   distribution.
  17  * * Neither the name of olsr.org, olsrd nor the names of its
  18  *   contributors may be used to endorse or promote products derived
  19  *   from this software without specific prior written permission.
  20  *
  21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  22  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  25  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  26  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
  27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  28  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  29  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  31  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  32  * POSSIBILITY OF SUCH DAMAGE.
  33  *
  34  * Visit http://www.olsr.org for more information.
  35  *
  36  * If you find this software useful feel free to make a donation
  37  * to the project. For more information see the website or contact
  38  * the copyright holders.
  39  *
  40  */
  41 #include <assert.h>
  42
  43 #include "ipcalc.h"
  44 #include "defs.h"
  45 #include "two_hop_neighbor_table.h"
  46 #include "mid_set.h"
  47 #include "olsr.h"
  48 #include "rebuild_packet.h"
  49 #include "scheduler.h"
  50 #include "neighbor_table.h"
  51 #include "link_set.h"
  52 #include "tc_set.h"
  53 #include "packet.h"             /* struct mid_alias */
  54 #include "net_olsr.h"
  55
  56 struct mid_entry mid_set[HASHSIZE];
  57 struct mid_address reverse_mid_set[HASHSIZE];
  58
  59 struct mid_entry *mid_lookup_entry_bymain(const union olsr_ip_addr *adr);
  60
  61 /**
  62  * Initialize the MID set
  63  *
  64  */
  65 int
  66 olsr_init_mid_set(void)
  67 {
  68   int idx;
  69
  70   OLSR_PRINTF(5, "MID: init\n");
  71
  72   for (idx = 0; idx < HASHSIZE; idx++) {
  73     mid_set[idx].next = &mid_set[idx];
  74     mid_set[idx].prev = &mid_set[idx];
  75
  76     reverse_mid_set[idx].next = &reverse_mid_set[idx];
  77     reverse_mid_set[idx].prev = &reverse_mid_set[idx];
  78   }
  79
  80   return 1;
  81 }
  82
  83 void olsr_delete_all_mid_entries(void) {
  84   int hash;
  85
  86   for (hash = 0; hash < HASHSIZE; hash++) {
  87     while (mid_set[hash].next != &mid_set[hash]) {
  88       olsr_delete_mid_entry(mid_set[hash].next);
  89     }
  90   }
  91 }
  92 /**
  93  * Wrapper for the timer callback.
  94  */
  95 static void
  96 olsr_expire_mid_entry(void *context)
  97 {
  98 #ifdef DEBUG
  99   struct ipaddr_str buf;
 100 #endif
 101   struct mid_entry *mid;
 102
 103   mid = (struct mid_entry *)context;
 104   mid->mid_timer = NULL;
 105
 106 #ifdef DEBUG
 107   OLSR_PRINTF(1, "MID info for %s timed out.. deleting it\n", olsr_ip_to_string(&buf, &mid->main_addr));
 108 #endif
 109
 110   olsr_delete_mid_entry(mid);
 111 }
 112
 113 /**
 114  * Set the mid set expiration timer.
 115  *
 116  * all timer setting shall be done using this function.
 117  * The timer param is a relative timer expressed in milliseconds.
 118  */
 119 static void
 120 olsr_set_mid_timer(struct mid_entry *mid, olsr_reltime rel_timer)
 121 {
 122   int32_t willFireIn = -1;
 123   if (mid->mid_timer != NULL) willFireIn = olsr_getTimeDue(mid->mid_timer->timer_clock);
 124
 125   if (willFireIn < 0 || (olsr_reltime)willFireIn < rel_timer) {
 126     olsr_set_timer(&mid->mid_timer, rel_timer, OLSR_MID_JITTER, OLSR_TIMER_ONESHOT, &olsr_expire_mid_entry, mid, 0);
 127   }
 128 }
 129
 130 /**
 131  * Insert a new interface alias to the interface association set.
 132  * If the main interface of the association is not yet registered
 133  * in the set a new entry is created.
 134  *
 135  * @param m_addr the main address of the node
 136  * @param alias the alias address to insert
 137  * @return false if mid_address is unnecessary, true otherwise
 138  */
 139
 140 static bool
 141 insert_mid_tuple(union olsr_ip_addr *m_addr, struct mid_address *alias, olsr_reltime vtime)
 142 {
 143   struct mid_entry *tmp;
 144   struct mid_address *tmp_adr;
 145   uint32_t hash, alias_hash;
 146   union olsr_ip_addr *registered_m_addr;
 147
 148   hash = olsr_ip_hashing(m_addr);
 149   alias_hash = olsr_ip_hashing(&alias->alias);
 150
 151   /* Check for registered entry */
 152   for (tmp = mid_set[hash].next; tmp != &mid_set[hash]; tmp = tmp->next) {
 153     if (ipequal(&tmp->main_addr, m_addr))
 154       break;
 155   }
 156
 157   /* Check if alias is already registered with m_addr */
 158   registered_m_addr = mid_lookup_main_addr(&alias->alias);
 159   if (registered_m_addr != NULL && ipequal(registered_m_addr, m_addr)) {
 160     /* Alias is already registered with main address. Nothing to do here. */
 161     return false;
 162   }
 163
 164   /*
 165    * Add a rt_path for the alias.
 166    */
 167   olsr_insert_routing_table(&alias->alias, olsr_cnf->maxplen, m_addr, OLSR_RT_ORIGIN_MID);
 168
 169   /*If the address was registered */
 170   if (tmp != &mid_set[hash]) {
 171     tmp_adr = tmp->aliases;
 172     tmp->aliases = alias;
 173     alias->main_entry = tmp;
 174     QUEUE_ELEM(reverse_mid_set[alias_hash], alias);
 175     alias->next_alias = tmp_adr;
 176     olsr_set_mid_timer(tmp, vtime);
 177   } else {
 178
 179     /*Create new node */
 180     tmp = olsr_malloc(sizeof(struct mid_entry), "MID new alias");
 181
 182     tmp->aliases = alias;
 183     alias->main_entry = tmp;
 184     QUEUE_ELEM(reverse_mid_set[alias_hash], alias);
 185     tmp->main_addr = *m_addr;
 186     olsr_set_mid_timer(tmp, vtime);
 187
 188     /* Queue */
 189     QUEUE_ELEM(mid_set[hash], tmp);
 190   }
 191
 192   /*
 193    * Delete possible duplicate entries in 2 hop set
 194    * and delete duplicate neighbor entries. Redirect
 195    * link entries to the correct neighbor entry.
 196    *
 197    *THIS OPTIMIZATION IS NOT SPECIFIED IN RFC3626
 198    */
 199
 200   tmp_adr = alias;
 201
 202   while (tmp_adr) {
 203     struct neighbor_2_entry *tmp_2_neighbor;
 204     struct neighbor_entry *tmp_neigh, *real_neigh;
 205
 206     /* Delete possible 2 hop neighbor */
 207     if ((tmp_2_neighbor = olsr_lookup_two_hop_neighbor_table_mid(&tmp_adr->alias)) != NULL) {
 208       struct ipaddr_str buf;
 209       OLSR_PRINTF(1, "Deleting 2 hop node from MID: %s to ", olsr_ip_to_string(&buf, &tmp_adr->alias));
 210       OLSR_PRINTF(1, "%s\n", olsr_ip_to_string(&buf, m_addr));
 211
 212       olsr_delete_two_hop_neighbor_table(tmp_2_neighbor);
 213
 214       changes_neighborhood = true;
 215     }
 216
 217     /* Delete a possible neighbor entry */
 218     if (((tmp_neigh = olsr_lookup_neighbor_table_alias(&tmp_adr->alias)) != NULL)
 219         && ((real_neigh = olsr_lookup_neighbor_table_alias(m_addr)) != NULL)) {
 220       struct ipaddr_str buf;
 221       OLSR_PRINTF(1, "[MID]Deleting bogus neighbor entry %s real ", olsr_ip_to_string(&buf, &tmp_adr->alias));
 222       OLSR_PRINTF(1, "%s\n", olsr_ip_to_string(&buf, m_addr));
 223
 224       replace_neighbor_link_set(tmp_neigh, real_neigh);
 225
 226       /* Dequeue */
 227       DEQUEUE_ELEM(tmp_neigh);
 228       /* Delete */
 229       free(tmp_neigh);
 230
 231       changes_neighborhood = true;
 232     }
 233     tmp_adr = tmp_adr->next_alias;
 234   }
 235   return true;
 236 }
 237
 238 /**
 239  * Insert an alias address for a node.
 240  * If the main address is not registered
 241  * then a new entry is created.
 242  *
 243  * @param main_add the main address of the node
 244  * @param alias the alias address to insert
 245  * @param seq the sequence number to register a new node with
 246  * @return nada
 247  */
 248 void
 249 insert_mid_alias(union olsr_ip_addr *main_add, const union olsr_ip_addr *alias, olsr_reltime vtime)
 250 {
 251   struct neighbor_entry *ne_old, *ne_new;
 252   struct mid_entry *me_old;
 253   int ne_ref_rp_count;
 254   struct ipaddr_str buf1, buf2;
 255   struct mid_address *adr;
 256   if (!olsr_validate_address(alias))
 257     return;
 258
 259   OLSR_PRINTF(1, "Inserting alias %s for ", olsr_ip_to_string(&buf1, alias));
 260   OLSR_PRINTF(1, "%s\n", olsr_ip_to_string(&buf1, main_add));
 261
 262   adr = olsr_malloc(sizeof(struct mid_address), "Insert MID alias");
 263
 264   adr->alias = *alias;
 265   adr->next_alias = NULL;
 266
 267   /*
 268    * If we have an entry for this alias in neighbortable, we better adjust it's
 269    * main address, because otherwise a fatal inconsistency between
 270    * neighbortable and link_set will be created by way of this mid entry.
 271    */
 272   ne_old = olsr_lookup_neighbor_table_alias(alias);
 273   if (ne_old != NULL) {
 274     OLSR_PRINTF(2, "Remote main address change detected. Mangling neighbortable to replace %s with %s.\n",
 275                 olsr_ip_to_string(&buf1, alias), olsr_ip_to_string(&buf2, main_add));
 276     olsr_delete_neighbor_table(alias);
 277     ne_new = olsr_insert_neighbor_table(main_add);
 278     /* adjust pointers to neighbortable-entry in link_set */
 279     ne_ref_rp_count = replace_neighbor_link_set(ne_old, ne_new);
 280     if (ne_ref_rp_count > 0)
 281       OLSR_PRINTF(2, "Performed %d neighbortable-pointer replacements (%p -> %p) in link_set.\n", ne_ref_rp_count, ne_old, ne_new);
 282
 283     me_old = mid_lookup_entry_bymain(alias);
 284     if (me_old) {
 285
 286       /*
 287        * we knew aliases to the previous main address;
 288        * better forget about them now.
 289        */
 290       OLSR_PRINTF(2,
 291                   "I already have an mid entry mapping addresses to this "
 292                   "alias address. Removing existing mid entry to preserve consistency of mid_set.\n");
 293       olsr_delete_mid_entry(me_old);
 294     }
 295   }
 296
 297   if (!insert_mid_tuple(main_add, adr, vtime)) {
 298     free(adr);
 299   }
 300
 301   /*
 302    *Recalculate topology
 303    */
 304   changes_neighborhood = true;
 305   changes_topology = true;
 306 }
 307
 308 /**
 309  * Lookup the main address for a alias address
 310  *
 311  * @param adr the alias address to check
 312  * @return the main address registered on the alias
 313  * or NULL if not found
 314  */
 315 union olsr_ip_addr *
 316 mid_lookup_main_addr(const union olsr_ip_addr *adr)
 317 {
 318   uint32_t hash;
 319   struct mid_address *tmp_list;
 320
 321   hash = olsr_ip_hashing(adr);
 322
 323   /*Traverse MID list */
 324   for (tmp_list = reverse_mid_set[hash].next; tmp_list != &reverse_mid_set[hash]; tmp_list = tmp_list->next) {
 325     if (ipequal(&tmp_list->alias, adr))
 326       return &tmp_list->main_entry->main_addr;
 327   }
 328   return NULL;
 329
 330 }
 331
 332 /*
 333  * Find mid entry to an address.
 334  *
 335  * @param adr the main address to search for
 336  * @return a linked list of address structs
 337  */
 338 struct mid_entry *
 339 mid_lookup_entry_bymain(const union olsr_ip_addr *adr)
 340 {
 341   struct mid_entry *tmp_list;
 342   uint32_t hash;
 343
 344   hash = olsr_ip_hashing(adr);
 345
 346   /* Check all registered nodes... */
 347   for (tmp_list = mid_set[hash].next; tmp_list != &mid_set[hash]; tmp_list = tmp_list->next) {
 348     if (ipequal(&tmp_list->main_addr, adr))
 349       return tmp_list;
 350   }
 351   return NULL;
 352 }
 353
 354 /*
 355  * Find all aliases for an address.
 356  *
 357  * @param adr the main address to search for
 358  * @return a linked list of addresses structs
 359  */
 360 struct mid_address *
 361 mid_lookup_aliases(const union olsr_ip_addr *adr)
 362 {
 363   struct mid_entry *tmp = mid_lookup_entry_bymain(adr);
 364   return tmp ? tmp->aliases : NULL;
 365 }
 366
 367 /**
 368  * Update the timer for an MID entry
 369  *
 370  * @param adr the main address of the entry
 371  * @return 1 if the node was updated, 0 if not
 372  */
 373 int
 374 olsr_update_mid_table(const union olsr_ip_addr *adr, olsr_reltime vtime)
 375 {
 376   uint32_t hash;
 377   struct ipaddr_str buf;
 378   struct mid_entry *tmp_list = mid_set;
 379
 380   OLSR_PRINTF(3, "MID: update %s\n", olsr_ip_to_string(&buf, adr));
 381   hash = olsr_ip_hashing(adr);
 382
 383   /* Check all registered nodes... */
 384   for (tmp_list = mid_set[hash].next; tmp_list != &mid_set[hash]; tmp_list = tmp_list->next) {
 385     /*find match */
 386     if (ipequal(&tmp_list->main_addr, adr)) {
 387       olsr_set_mid_timer(tmp_list, vtime);
 388
 389       return 1;
 390     }
 391   }
 392   return 0;
 393 }
 394
 395 /**
 396  * Remove aliases from 'entry' which are not listed in 'declared_aliases'.
 397  *
 398  * @param entry the MID entry
 399  * @param declared_aliases the list of declared aliases for the MID entry
 400  * @return nada
 401  */
 402 void
 403 olsr_prune_aliases(const union olsr_ip_addr *m_addr, struct mid_alias *declared_aliases)
 404 {
 405   struct mid_entry *entry;
 406   uint32_t hash;
 407   struct mid_address *registered_aliases;
 408   struct mid_address *previous_alias;
 409   struct mid_alias *save_declared_aliases = declared_aliases;
 410
 411   hash = olsr_ip_hashing(m_addr);
 412
 413   /* Check for registered entry */
 414   for (entry = mid_set[hash].next; entry != &mid_set[hash]; entry = entry->next) {
 415     if (ipequal(&entry->main_addr, m_addr))
 416       break;
 417   }
 418   if (entry == &mid_set[hash]) {
 419     /* MID entry not found, nothing to prune here */
 420     return;
 421   }
 422
 423   registered_aliases = entry->aliases;
 424   previous_alias = NULL;
 425
 426   while (registered_aliases != NULL) {
 427     struct mid_address *current_alias = registered_aliases;
 428     registered_aliases = registered_aliases->next_alias;
 429
 430     declared_aliases = save_declared_aliases;
 431
 432     /* Go through the list of declared aliases to find the matching current alias */
 433     while (declared_aliases != 0 && !ipequal(&current_alias->alias, &declared_aliases->alias_addr)) {
 434       declared_aliases = declared_aliases->next;
 435     }
 436
 437     if (declared_aliases == NULL) {
 438       struct ipaddr_str buf;
 439       /* Current alias not found in list of declared aliases: free current alias */
 440       OLSR_PRINTF(1, "MID remove: (%s, ", olsr_ip_to_string(&buf, &entry->main_addr));
 441       OLSR_PRINTF(1, "%s)\n", olsr_ip_to_string(&buf, &current_alias->alias));
 442
 443       /* Update linked list as seen by 'entry' */
 444       if (previous_alias != NULL) {
 445         previous_alias->next_alias = current_alias->next_alias;
 446       } else {
 447         entry->aliases = current_alias->next_alias;
 448       }
 449
 450       /* Remove from hash table */
 451       DEQUEUE_ELEM(current_alias);
 452
 453       /*
 454        * Delete the rt_path for the alias.
 455        */
 456       olsr_delete_routing_table(&current_alias->alias, olsr_cnf->maxplen, &entry->main_addr);
 457
 458       free(current_alias);
 459
 460       /*
 461        *Recalculate topology
 462        */
 463       changes_neighborhood = true;
 464       changes_topology = true;
 465     } else {
 466       previous_alias = current_alias;
 467     }
 468   }
 469 }
 470
 471 /**
 472  * Delete a MID entry
 473  *
 474  * @param entry the entry to delete
 475  */
 476 void
 477 olsr_delete_mid_entry(struct mid_entry *mid)
 478 {
 479   struct mid_address *aliases;
 480
 481   /* Free aliases */
 482   aliases = mid->aliases;
 483   while (aliases) {
 484     struct mid_address *tmp_aliases = aliases;
 485     aliases = aliases->next_alias;
 486     DEQUEUE_ELEM(tmp_aliases);
 487
 488     /*
 489      * Delete the rt_path for the alias.
 490      */
 491     olsr_delete_routing_table(&tmp_aliases->alias, olsr_cnf->maxplen, &mid->main_addr);
 492
 493     free(tmp_aliases);
 494   }
 495
 496   /*
 497    * Kill any pending timers.
 498    */
 499   if (mid->mid_timer) {
 500     olsr_stop_timer(mid->mid_timer);
 501     mid->mid_timer = NULL;
 502   }
 503
 504   /* Dequeue */
 505   DEQUEUE_ELEM(mid);
 506   free(mid);
 507 }
 508
 509 /**
 510  * Print all MID entries
 511  * For debuging purposes
 512  */
 513 void
 514 olsr_print_mid_set(void)
 515 {
 516   int idx;
 517
 518   OLSR_PRINTF(1, "\n--- %s ------------------------------------------------- MID\n\n", olsr_wallclock_string());
 519
 520   for (idx = 0; idx < HASHSIZE; idx++) {
 521     struct mid_entry *tmp_list = mid_set[idx].next;
 522     /*Traverse MID list */
 523     for (tmp_list = mid_set[idx].next; tmp_list != &mid_set[idx]; tmp_list = tmp_list->next) {
 524       struct mid_address *tmp_addr;
 525       struct ipaddr_str buf;
 526       OLSR_PRINTF(1, "%s: ", olsr_ip_to_string(&buf, &tmp_list->main_addr));
 527       for (tmp_addr = tmp_list->aliases; tmp_addr; tmp_addr = tmp_addr->next_alias) {
 528         OLSR_PRINTF(1, " %s ", olsr_ip_to_string(&buf, &tmp_addr->alias));
 529       }
 530       OLSR_PRINTF(1, "\n");
 531     }
 532   }
 533 }
 534
 535 /**
 536  *Process a received(and parsed) MID message
 537  *For every address check if there is a topology node
 538  *registered with it and update its addresses.
 539  *
 540  *@param m the OLSR message received.
 541  *@return 1 on success
 542  */
 543
 544 bool
 545 olsr_input_mid(union olsr_message *m, struct interface *in_if __attribute__ ((unused)), union olsr_ip_addr *from_addr)
 546 {
 547   struct ipaddr_str buf;
 548   struct mid_alias *tmp_adr;
 549   struct mid_message message;
 550
 551   mid_chgestruct(&message, m);
 552
 553   if (!olsr_validate_address(&message.mid_origaddr)) {
 554     olsr_free_mid_packet(&message);
 555     return false;
 556   }
 557 #ifdef DEBUG
 558   OLSR_PRINTF(5, "Processing MID from %s...\n", olsr_ip_to_string(&buf, &message.mid_origaddr));
 559 #endif
 560   tmp_adr = message.mid_addr;
 561
 562   /*
 563    *      If the sender interface (NB: not originator) of this message
 564    *      is not in the symmetric 1-hop neighborhood of this node, the
 565    *      message MUST be discarded.
 566    */
 567
 568   if (check_neighbor_link(from_addr) != SYM_LINK) {
 569     OLSR_PRINTF(2, "Received MID from NON SYM neighbor %s\n", olsr_ip_to_string(&buf, from_addr));
 570     olsr_free_mid_packet(&message);
 571     return false;
 572   }
 573
 574   /* Update the timeout of the MID */
 575   olsr_update_mid_table(&message.mid_origaddr, message.vtime);
 576
 577   while (tmp_adr) {
 578     if (!mid_lookup_main_addr(&tmp_adr->alias_addr)) {
 579       OLSR_PRINTF(1, "MID new: (%s, ", olsr_ip_to_string(&buf, &message.mid_origaddr));
 580       OLSR_PRINTF(1, "%s)\n", olsr_ip_to_string(&buf, &tmp_adr->alias_addr));
 581       insert_mid_alias(&message.mid_origaddr, &tmp_adr->alias_addr, message.vtime);
 582     } else {
 583       olsr_insert_routing_table(&tmp_adr->alias_addr, olsr_cnf->maxplen, &message.mid_origaddr, OLSR_RT_ORIGIN_MID);
 584     }
 585     tmp_adr = tmp_adr->next;
 586   }
 587
 588   olsr_prune_aliases(&message.mid_origaddr, message.mid_addr);
 589   olsr_free_mid_packet(&message);
 590
 591   /* Forward the message */
 592   return true;
 593 }
 594
 595 /*
 596  * Local Variables:
 597  * c-basic-offset: 2
 598  * indent-tabs-mode: nil
 599  * End:
 600  */