src/tc_set.c

   1
   2 /*
   3  * The olsr.org Optimized Link-State Routing daemon(olsrd)
   4  * Copyright (c) 2004-2009, the olsr.org team - see HISTORY file
   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 "tc_set.h"
  44 #include "olsr.h"
  45 #include "lq_packet.h"
  46 #include "net_olsr.h"
  47 #include "link_set.h"
  48 #include "mid_set.h"
  49 #include "neighbor_table.h"
  50 #include "olsr_logging.h"
  51
  52 static bool delete_outdated_tc_edges(struct tc_entry *);
  53
  54 /* Root of the link state database */
  55 struct avl_tree tc_tree;
  56 struct tc_entry *tc_myself = NULL;     /* Shortcut to ourselves */
  57
  58 /* Some cookies for stats keeping */
  59 static struct olsr_cookie_info *tc_edge_gc_timer_cookie = NULL;
  60 static struct olsr_cookie_info *tc_validity_timer_cookie = NULL;
  61 struct olsr_cookie_info *spf_backoff_timer_cookie = NULL;
  62 struct olsr_cookie_info *tc_mem_cookie = NULL;
  63
  64 static uint32_t relevantTcCount = 0;
  65
  66 /* the first 32 TCs are without Fisheye */
  67 static int ttl_index = -32;
  68
  69 static uint16_t local_ansn_number = 0;
  70
  71 static void olsr_cleanup_tc_entry(struct tc_entry *tc);
  72
  73 /**
  74  * Add a new tc_entry to the tc tree
  75  *
  76  * @param (last)adr address of the entry
  77  * @return a pointer to the created entry
  78  */
  79 static struct tc_entry *
  80 olsr_add_tc_entry(const union olsr_ip_addr *adr)
  81 {
  82 #if !defined REMOVE_LOG_DEBUG
  83   struct ipaddr_str buf;
  84 #endif
  85   struct tc_entry *tc;
  86
  87   /*
  88    * Safety net against loss of the last main IP address.
  89    */
  90   if (olsr_ipcmp(&olsr_cnf->router_id, &all_zero) == 0) {
  91     return NULL;
  92   }
  93
  94   OLSR_DEBUG(LOG_TC, "TC: add entry %s\n", olsr_ip_to_string(&buf, adr));
  95
  96   tc = olsr_cookie_malloc(tc_mem_cookie);
  97   if (!tc) {
  98     return NULL;
  99   }
 100
 101   /* Fill entry */
 102   tc->addr = *adr;
 103   tc->vertex_node.key = &tc->addr;
 104
 105   tc->mid_seq = -1;
 106   tc->hna_seq = -1;
 107   tc->tc_seq = -1;
 108   /*
 109    * Insert into the global tc tree.
 110    */
 111   avl_insert(&tc_tree, &tc->vertex_node, false);
 112   olsr_lock_tc_entry(tc);
 113
 114   /*
 115    * Initialize subtrees for edges, prefixes, HNAs and MIDs.
 116    */
 117   avl_init(&tc->edge_tree, avl_comp_default);
 118   avl_init(&tc->prefix_tree, avl_comp_prefix_origin_default);
 119   avl_init(&tc->mid_tree, avl_comp_default);
 120   avl_init(&tc->hna_tree, avl_comp_prefix_default);
 121
 122   /*
 123    * Add a rt_path for ourselves.
 124    */
 125   olsr_insert_routing_table(adr, 8 * olsr_cnf->ipsize, adr, OLSR_RT_ORIGIN_TC);
 126
 127   return tc;
 128 }
 129
 130 /**
 131  * Initialize the topology set
 132  *
 133  */
 134 void
 135 olsr_init_tc(void)
 136 {
 137   OLSR_INFO(LOG_TC, "Initialize topology set...\n");
 138
 139   avl_init(&tc_tree, avl_comp_default);
 140
 141   /*
 142    * Get some cookies for getting stats to ease troubleshooting.
 143    */
 144   tc_edge_gc_timer_cookie = olsr_alloc_cookie("TC edge GC", OLSR_COOKIE_TYPE_TIMER);
 145   tc_validity_timer_cookie = olsr_alloc_cookie("TC validity", OLSR_COOKIE_TYPE_TIMER);
 146   spf_backoff_timer_cookie = olsr_alloc_cookie("SPF backoff", OLSR_COOKIE_TYPE_TIMER);
 147
 148   tc_mem_cookie = olsr_alloc_cookie("tc_entry", OLSR_COOKIE_TYPE_MEMORY);
 149   olsr_cookie_set_memory_size(tc_mem_cookie, sizeof(struct tc_entry));
 150 }
 151
 152 /**
 153  * The main ip address has changed.
 154  * Do the needful.
 155  */
 156 void
 157 olsr_change_myself_tc(void)
 158 {
 159   struct link_entry *entry;
 160   bool main_ip_change = false;
 161
 162   if (tc_myself) {
 163
 164     /*
 165      * Check if there was a change.
 166      */
 167     if (olsr_ipcmp(&tc_myself->addr, &olsr_cnf->router_id) == 0) {
 168       return;
 169     }
 170
 171     /*
 172      * Flush our own tc_entry.
 173      */
 174     olsr_delete_tc_entry(tc_myself);
 175
 176     /*
 177      * Clear the reference.
 178      */
 179     olsr_unlock_tc_entry(tc_myself);
 180     tc_myself = NULL;
 181
 182     main_ip_change = true;
 183   }
 184
 185   /*
 186    * The old entry for ourselves is gone, generate a new one and trigger SPF.
 187    */
 188   tc_myself = olsr_add_tc_entry(&olsr_cnf->router_id);
 189   olsr_lock_tc_entry(tc_myself);
 190
 191   OLSR_FOR_ALL_LINK_ENTRIES(entry) {
 192
 193     /**
 194      * check if a main ip change destroyed our TC entries
 195      */
 196     if (main_ip_change || entry->link_tc_edge == NULL) {
 197       struct nbr_entry *ne = entry->neighbor;
 198       entry->link_tc_edge = olsr_add_tc_edge_entry(tc_myself, &ne->nbr_addr, 0);
 199     }
 200   } OLSR_FOR_ALL_LINK_ENTRIES_END(link);
 201   changes_topology = true;
 202 }
 203
 204 /**
 205  * Attempts to delete a tc entry. This will work unless there are virtual edges left
 206  * that cannot be removed
 207  *
 208  * @param entry the TC entry to delete
 209  *
 210  */
 211 void
 212 olsr_delete_tc_entry(struct tc_entry *tc)
 213 {
 214   struct tc_edge_entry *tc_edge;
 215
 216 #if !defined REMOVE_LOG_DEBUG
 217   struct ipaddr_str buf;
 218 #endif
 219   OLSR_DEBUG(LOG_TC, "TC: del entry %s %u %s\n", olsr_ip_to_string(&buf, &tc->addr),
 220       tc->edge_tree.count, tc->is_virtual ? "true" : "false");
 221
 222   /* we don't want to keep this node */
 223   tc->is_virtual = true;
 224
 225   if (tc->edge_tree.count == 0) {
 226     olsr_cleanup_tc_entry(tc);
 227     return;
 228   }
 229   /* The delete all non-virtual edges, the last one will clean up the tc if possible */
 230   OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
 231     /* we don't need this edge for the tc, so let's try to remove it */
 232     olsr_delete_tc_edge_entry(tc_edge);
 233   } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END();
 234 }
 235
 236 /**
 237  * Delete a tc entry after all edges have been cleared.
 238  *
 239  * @param entry the TC entry to delete
 240  */
 241 static void
 242 olsr_cleanup_tc_entry(struct tc_entry *tc) {
 243   struct rt_path *rtp;
 244 #if !defined(REMOVE_LOG_DEBUG)
 245   struct ipaddr_str buf;
 246 #endif
 247   OLSR_DEBUG(LOG_TC, "TC: del entry %s %u\n", olsr_ip_to_string(&buf, &tc->addr), tc->refcount);
 248   assert (tc->edge_tree.count == 0);
 249
 250   OLSR_FOR_ALL_PREFIX_ENTRIES(tc, rtp) {
 251     olsr_delete_rt_path(rtp);
 252   } OLSR_FOR_ALL_PREFIX_ENTRIES_END();
 253
 254   /* Flush all MID aliases and kill the MID timer */
 255   olsr_flush_mid_entries(tc);
 256
 257   /* Flush all HNA Networks and kill its timers */
 258   olsr_flush_hna_nets(tc);
 259
 260   /* Stop running timers */
 261   olsr_stop_timer(tc->edge_gc_timer);
 262   tc->edge_gc_timer = NULL;
 263   olsr_stop_timer(tc->validity_timer);
 264   tc->validity_timer = NULL;
 265
 266   avl_delete(&tc_tree, &tc->vertex_node);
 267   olsr_unlock_tc_entry(tc);
 268 }
 269
 270 /**
 271  * Look up a entry from the TC tree based on address
 272  *
 273  * @param adr the address to look for
 274  * @return the entry found or NULL
 275  */
 276 struct tc_entry *
 277 olsr_lookup_tc_entry(const union olsr_ip_addr *adr)
 278 {
 279   struct avl_node *node;
 280
 281   node = avl_find(&tc_tree, adr);
 282   return node ? vertex_tree2tc(node) : NULL;
 283 }
 284
 285 /*
 286  * Lookup a tc entry. Creates one if it does not exist yet.
 287  */
 288 struct tc_entry *
 289 olsr_locate_tc_entry(const union olsr_ip_addr *adr)
 290 {
 291   struct tc_entry *tc = olsr_lookup_tc_entry(adr);
 292
 293   return tc == NULL ? olsr_add_tc_entry(adr) : tc;
 294 }
 295
 296 /**
 297  * Format tc_edge contents into a buffer.
 298  */
 299 #if !defined REMOVE_LOG_DEBUG
 300 static char *
 301 olsr_tc_edge_to_string(struct tc_edge_entry *tc_edge)
 302 {
 303   static char buf[128];
 304   struct ipaddr_str addrbuf, dstbuf;
 305   char lqbuffer[LQTEXT_MAXLENGTH];
 306
 307   snprintf(buf, sizeof(buf),
 308            "%s > %s, cost %s",
 309            olsr_ip_to_string(&addrbuf, &tc_edge->tc->addr),
 310            olsr_ip_to_string(&dstbuf, &tc_edge->T_dest_addr),
 311            olsr_get_linkcost_text(tc_edge->cost, false, lqbuffer, sizeof(lqbuffer)));
 312   return buf;
 313 }
 314 #endif
 315
 316 /**
 317  * Wrapper for the timer callback.
 318  * A TC entry has not been refreshed in time.
 319  * Remove it from the link-state database.
 320  */
 321 static void
 322 olsr_expire_tc_entry(void *context)
 323 {
 324 #if !defined REMOVE_LOG_DEBUG
 325   struct ipaddr_str buf;
 326 #endif
 327   struct tc_entry *tc = context;
 328   tc->validity_timer = NULL;
 329
 330   OLSR_DEBUG(LOG_TC, "TC: expire node entry %s\n",
 331              olsr_ip_to_string(&buf, &tc->addr));
 332
 333   olsr_delete_tc_entry(tc);
 334   changes_topology = true;
 335 }
 336
 337 /**
 338  * Wrapper for the timer callback.
 339  * Does the garbage collection of older ansn entries after no edge addition to
 340  * the TC entry has happened for OLSR_TC_EDGE_GC_TIME.
 341  */
 342 static void
 343 olsr_expire_tc_edge_gc(void *context)
 344 {
 345 #if !defined REMOVE_LOG_DEBUG
 346   struct ipaddr_str buf;
 347 #endif
 348   struct tc_entry *tc = context;
 349
 350   OLSR_DEBUG(LOG_TC, "TC: expire edge GC for %s\n",
 351              olsr_ip_to_string(&buf, &tc->addr));
 352
 353   tc->edge_gc_timer = NULL;
 354
 355   if (delete_outdated_tc_edges(tc)) {
 356     changes_topology = true;
 357   }
 358 }
 359
 360 /*
 361  * If the edge does not have a minimum acceptable link quality
 362  * set the etx cost to infinity such that it gets ignored during
 363  * SPF calculation.
 364  *
 365  * @return 1 if the change of the etx value was relevant
 366  */
 367 bool
 368 olsr_calc_tc_edge_entry_etx(struct tc_edge_entry *tc_edge)
 369 {
 370   olsr_linkcost old = tc_edge->cost;
 371   tc_edge->cost = olsr_calc_tc_cost(tc_edge);
 372   tc_edge->common_cost = tc_edge->cost;
 373   if (tc_edge->edge_inv) {
 374     tc_edge->edge_inv->common_cost = tc_edge->cost;
 375   }
 376   return olsr_is_relevant_costchange(old, tc_edge->cost);
 377 }
 378
 379 /**
 380  * Add a new tc_edge_entry to the tc_edge_tree
 381  *
 382  * @param (last)adr address of the entry
 383  * @return a pointer to the created entry
 384  */
 385 struct tc_edge_entry *
 386 olsr_add_tc_edge_entry(struct tc_entry *tc, union olsr_ip_addr *addr, uint16_t ansn)
 387 {
 388   struct tc_entry *tc_neighbor;
 389   struct tc_edge_entry *tc_edge;
 390   struct tc_edge_entry *tc_edge_inv;
 391 #if !defined REMOVE_LOG_DEBUG
 392   struct ipaddr_str buf;
 393 #endif
 394   tc_edge = olsr_malloc_tc_edge_entry();
 395   if (!tc_edge) {
 396     return NULL;
 397   }
 398
 399   /* Fill entry */
 400   tc_edge->T_dest_addr = *addr;
 401   tc_edge->ansn = ansn;
 402   tc_edge->edge_node.key = &tc_edge->T_dest_addr;
 403
 404   /*
 405    * Insert into the edge tree.
 406    * Expectation is to have only one tc_edge per tc pair.
 407    * However we need duplicate key support for the case of local
 408    * parallel links where we add one tc_edge per link_entry.
 409    */
 410   avl_insert(&tc->edge_tree, &tc_edge->edge_node, true);
 411   olsr_lock_tc_entry(tc);
 412
 413   /*
 414    * Connect backpointer.
 415    */
 416   tc_edge->tc = tc;
 417
 418   /*
 419    * Check if the neighboring router and the inverse edge is in the lsdb.
 420    * Create short cuts to the inverse edge for faster SPF execution.
 421    */
 422   tc_neighbor = olsr_lookup_tc_entry(&tc_edge->T_dest_addr);
 423   if (tc_neighbor == NULL) {
 424     OLSR_DEBUG(LOG_TC, "TC:   creating neighbor tc_entry %s\n", olsr_ip_to_string(&buf, &tc_edge->T_dest_addr));
 425     tc_neighbor = olsr_add_tc_entry(&tc_edge->T_dest_addr);
 426     tc_neighbor->is_virtual = true;
 427   }
 428
 429   /* don't create an inverse edge for a tc pointing to us ! */
 430   if (1 && tc_neighbor != tc_myself) {
 431     tc_edge_inv = olsr_lookup_tc_edge(tc_neighbor, &tc->addr);
 432     if (!tc_edge_inv ) {
 433       OLSR_DEBUG(LOG_TC, "TC:   creating inverse edge for %s\n", olsr_ip_to_string(&buf, &tc->addr));
 434       tc_edge_inv = olsr_add_tc_edge_entry(tc_neighbor, &tc->addr, 0);
 435
 436       tc_edge_inv->is_virtual = 1;
 437     }
 438
 439     /*
 440      * Connect the edges mutually.
 441      */
 442     tc_edge_inv->edge_inv = tc_edge;
 443     tc_edge->edge_inv = tc_edge_inv;
 444   }
 445
 446   /*
 447    * Update the etx.
 448    */
 449   olsr_calc_tc_edge_entry_etx(tc_edge);
 450
 451   OLSR_DEBUG(LOG_TC, "TC: add edge entry %s\n", olsr_tc_edge_to_string(tc_edge));
 452
 453   return tc_edge;
 454 }
 455
 456 /**
 457  * Delete a TC edge entry.
 458  *
 459  * @param tc the TC entry
 460  * @param tc_edge the TC edge entry
 461  * @return true if the tc entry was deleted, false otherwise
 462  */
 463 void
 464 olsr_delete_tc_edge_entry(struct tc_edge_entry *tc_edge)
 465 {
 466   struct tc_entry *tc;
 467   struct tc_edge_entry *tc_edge_inv;
 468 #if !defined REMOVE_LOG_DEBUG
 469   struct ipaddr_str buf;
 470 #endif
 471
 472   tc_edge->is_virtual = 1;
 473
 474   tc_edge_inv = tc_edge->edge_inv;
 475   if (tc_edge_inv != NULL && tc_edge_inv->is_virtual == 0) {
 476     OLSR_DEBUG(LOG_TC, "TC: mark edge entry %s\n", olsr_tc_edge_to_string(tc_edge));
 477     return;
 478   }
 479
 480   OLSR_DEBUG(LOG_TC, "TC: del edge entry %s\n", olsr_tc_edge_to_string(tc_edge));
 481
 482   /*
 483    * Clear the backpointer of our inverse edge.
 484    */
 485   if (tc_edge_inv) {
 486     /* split the two edges */
 487     tc_edge_inv->edge_inv = NULL;
 488     tc_edge->edge_inv = NULL;
 489
 490     if (tc_edge_inv->is_virtual) {
 491       /* remove the other side too because it's a virtual link */
 492       olsr_delete_tc_edge_entry(tc_edge_inv);
 493     }
 494   }
 495
 496   tc = tc_edge->tc;
 497
 498   /* remove edge from tc FIRST */
 499   avl_delete(&tc->edge_tree, &tc_edge->edge_node);
 500   OLSR_DEBUG(LOG_TC, "TC: %s down to %d edges\n", olsr_ip_to_string(&buf, &tc->addr), tc->edge_tree.count);
 501
 502   /* now check if TC is virtual and has no edges left */
 503   if (tc->is_virtual && tc->edge_tree.count == 0) {
 504     /* cleanup virtual tc node */
 505     olsr_cleanup_tc_entry(tc);
 506   }
 507   olsr_unlock_tc_entry(tc);
 508   olsr_free_tc_edge_entry(tc_edge);
 509 }
 510
 511 /**
 512  * Delete all destinations that have a lower ANSN.
 513  *
 514  * @param tc the entry to delete edges from
 515  * @return TRUE if any destinations were deleted, FALSE if not
 516  */
 517 static bool
 518 delete_outdated_tc_edges(struct tc_entry *tc)
 519 {
 520   struct tc_edge_entry *tc_edge;
 521   bool retval = false;
 522
 523   OLSR_DEBUG(LOG_TC, "TC: deleting outdated TC-edge entries\n");
 524
 525   OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
 526     if (SEQNO_GREATER_THAN(tc->ansn, tc_edge->ansn)) {
 527       olsr_delete_tc_edge_entry(tc_edge);
 528       retval = true;
 529     }
 530   }
 531   OLSR_FOR_ALL_TC_EDGE_ENTRIES_END();
 532
 533   if (retval)
 534     changes_topology = true;
 535   return retval;
 536 }
 537
 538 /**
 539  * Delete all destinations that are inside the borders but
 540  * not updated in the last tc.
 541  *
 542  * @param tc the entry to delete edges from
 543  * @param ansn the advertised neighbor set sequence number
 544  * @return 1 if any destinations were deleted 0 if not
 545  */
 546 static int
 547 olsr_delete_revoked_tc_edges(struct tc_entry *tc, uint16_t ansn, union olsr_ip_addr *lower_border, union olsr_ip_addr *upper_border)
 548 {
 549   struct tc_edge_entry *tc_edge;
 550   int retval = 0;
 551   bool passedLowerBorder = false;
 552
 553   OLSR_DEBUG(LOG_TC, "TC: deleting revoked TCs\n");
 554
 555   OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
 556     if (!passedLowerBorder) {
 557       if (avl_comp_default(lower_border, &tc_edge->T_dest_addr) <= 0) {
 558         passedLowerBorder = true;
 559       } else {
 560         continue;
 561       }
 562     }
 563
 564     if (passedLowerBorder) {
 565       if (avl_comp_default(upper_border, &tc_edge->T_dest_addr) <= 0) {
 566         break;
 567       }
 568     }
 569
 570     if (SEQNO_GREATER_THAN(ansn, tc_edge->ansn)) {
 571       olsr_delete_tc_edge_entry(tc_edge);
 572       retval = 1;
 573     }
 574   }
 575   OLSR_FOR_ALL_TC_EDGE_ENTRIES_END();
 576
 577   if (retval)
 578     changes_topology = true;
 579   return retval;
 580 }
 581
 582
 583 /**
 584  * Update an edge registered on an entry.
 585  * Creates new edge-entries if not registered.
 586  * Bases update on a received TC message
 587  *
 588  * @param entry the TC entry to check
 589  * @pkt the TC edge entry in the packet
 590  * @return 1 if entries are added 0 if not
 591  */
 592 static int
 593 olsr_tc_update_edge(struct tc_entry *tc, uint16_t ansn, const unsigned char **curr, union olsr_ip_addr *neighbor)
 594 {
 595   struct tc_edge_entry *tc_edge;
 596   int edge_change = 0;
 597
 598   /*
 599    * Fetch the per-edge data
 600    */
 601   pkt_get_ipaddress(curr, neighbor);
 602
 603   /* First check if we know this edge */
 604   tc_edge = olsr_lookup_tc_edge(tc, neighbor);
 605   if (!tc_edge) {
 606     /*
 607      * Yet unknown - create it.
 608      * Check if the address is allowed.
 609      */
 610     if (!olsr_validate_address(neighbor)) {
 611       return 0;
 612     }
 613
 614     tc_edge = olsr_add_tc_edge_entry(tc, neighbor, ansn);
 615
 616     olsr_deserialize_tc_lq_pair(curr, tc_edge);
 617     edge_change = 1;
 618   } else {
 619     /*
 620      * We know this edge - Update entry.
 621      */
 622     tc_edge->ansn = ansn;
 623
 624     /*
 625      * Update link quality if configured.
 626      */
 627     olsr_deserialize_tc_lq_pair(curr, tc_edge);
 628
 629     /*
 630      * Update the etx.
 631      */
 632     if (olsr_calc_tc_edge_entry_etx(tc_edge)) {
 633       if (tc->msg_hops <= olsr_cnf->lq_dlimit) {
 634         edge_change = 1;
 635       }
 636     }
 637     if (edge_change) {
 638       OLSR_DEBUG(LOG_TC, "TC:   chg edge entry %s\n", olsr_tc_edge_to_string(tc_edge));
 639     }
 640   }
 641   tc_edge->is_virtual = 0;
 642   tc->is_virtual = false;
 643
 644   return edge_change;
 645 }
 646
 647 /**
 648  * Lookup an edge hanging off a TC entry.
 649  *
 650  * @param entry the entry to check
 651  * @param dst_addr the destination address to check for
 652  * @return a pointer to the tc_edge found - or NULL
 653  */
 654 struct tc_edge_entry *
 655 olsr_lookup_tc_edge(struct tc_entry *tc, union olsr_ip_addr *edge_addr)
 656 {
 657   struct avl_node *edge_node;
 658
 659   edge_node = avl_find(&tc->edge_tree, edge_addr);
 660
 661   return edge_node ? edge_tree2tc_edge(edge_node) : NULL;
 662 }
 663
 664 /**
 665  * Print the topology table to stdout
 666  */
 667 void
 668 olsr_print_tc_table(void)
 669 {
 670 #if !defined REMOVE_LOG_INFO
 671   /* The whole function makes no sense without it. */
 672   struct tc_entry *tc;
 673   const int ipwidth = olsr_cnf->ip_version == AF_INET ? 15 : 30;
 674
 675   OLSR_INFO(LOG_TC, "\n--- %s ------------------------------------------------- TOPOLOGY\n\n", olsr_wallclock_string());
 676   OLSR_INFO_NH(LOG_TC, "%-*s %-*s             %8s %8s\n", ipwidth,
 677                "Source IP addr", ipwidth, "Dest IP addr", olsr_get_linklabel(0), "(common)");
 678
 679   OLSR_FOR_ALL_TC_ENTRIES(tc) {
 680     struct tc_edge_entry *tc_edge;
 681     OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
 682       struct ipaddr_str addrbuf, dstaddrbuf;
 683       char lqbuffer1[LQTEXT_MAXLENGTH], lqbuffer2[LQTEXT_MAXLENGTH];
 684
 685       OLSR_INFO_NH(LOG_TC, "%-*s %-*s %-7s      %8s %8s\n",
 686                    ipwidth, olsr_ip_to_string(&addrbuf, &tc->addr),
 687                    ipwidth, olsr_ip_to_string(&dstaddrbuf,
 688                                               &tc_edge->T_dest_addr),
 689                    tc_edge->is_virtual ? "virtual" : "",
 690                    olsr_get_linkcost_text(tc_edge->cost, false, lqbuffer1, sizeof(lqbuffer1)),
 691                    olsr_get_linkcost_text(tc_edge->common_cost, false, lqbuffer2, sizeof(lqbuffer2)));
 692
 693     } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END();
 694   } OLSR_FOR_ALL_TC_ENTRIES_END();
 695 #endif
 696 }
 697
 698 /*
 699  * calculate the border IPs of a tc edge set according to the border flags
 700  *
 701  * @param lower border flag
 702  * @param pointer to lower border ip
 703  * @param upper border flag
 704  * @param pointer to upper border ip
 705  * @result 1 if lower/upper border ip have been set
 706  */
 707 static int
 708 olsr_calculate_tc_border(uint8_t lower_border,
 709                          union olsr_ip_addr *lower_border_ip, uint8_t upper_border, union olsr_ip_addr *upper_border_ip)
 710 {
 711   if (lower_border == 0 && upper_border == 0) {
 712     return 0;
 713   }
 714   if (lower_border == 0xff) {
 715     memset(lower_border_ip, 0, sizeof(lower_border_ip));
 716   } else {
 717     int i;
 718
 719     lower_border--;
 720     for (i = 0; i < lower_border / 8; i++) {
 721       lower_border_ip->v6.s6_addr[olsr_cnf->ipsize - i - 1] = 0;
 722     }
 723     lower_border_ip->v6.s6_addr[olsr_cnf->ipsize - lower_border / 8 - 1] &= (0xff << (lower_border & 7));
 724     lower_border_ip->v6.s6_addr[olsr_cnf->ipsize - lower_border / 8 - 1] |= (1 << (lower_border & 7));
 725   }
 726
 727   if (upper_border == 0xff) {
 728     memset(upper_border_ip, 0xff, sizeof(upper_border_ip));
 729   } else {
 730     int i;
 731
 732     upper_border--;
 733
 734     for (i = 0; i < upper_border / 8; i++) {
 735       upper_border_ip->v6.s6_addr[olsr_cnf->ipsize - i - 1] = 0;
 736     }
 737     upper_border_ip->v6.s6_addr[olsr_cnf->ipsize - upper_border / 8 - 1] &= (0xff << (upper_border & 7));
 738     upper_border_ip->v6.s6_addr[olsr_cnf->ipsize - upper_border / 8 - 1] |= (1 << (upper_border & 7));
 739   }
 740   return 1;
 741 }
 742
 743 /*
 744  * Process an incoming TC or TC_LQ message.
 745  *
 746  * If the message is interesting enough, update our edges for it,
 747  * trigger SPF and finally flood it to all our 2way neighbors.
 748  *
 749  * The order for extracting data off the message does matter,
 750  * as every call to pkt_get increases the packet offset and
 751  * hence the spot we are looking at.
 752  */
 753 void
 754 olsr_input_tc(union olsr_message * msg, struct interface * input_if __attribute__ ((unused)),
 755     union olsr_ip_addr * from_addr, enum duplicate_status status)
 756 {
 757   uint16_t size, msg_seq, ansn;
 758   uint8_t type, ttl, msg_hops, lower_border, upper_border;
 759   uint32_t vtime;
 760   union olsr_ip_addr originator;
 761   const unsigned char *limit, *curr;
 762   struct tc_entry *tc;
 763   bool relevantTc;
 764 #if !defined REMOVE_LOG_DEBUG
 765   struct ipaddr_str buf;
 766 #endif
 767   union olsr_ip_addr lower_border_ip, upper_border_ip;
 768   int borderSet = 0;
 769
 770   curr = (void *)msg;
 771
 772   /* We are only interested in TC message types. */
 773   pkt_get_u8(&curr, &type);
 774   if (type != olsr_get_TC_MessageId()) {
 775     return;
 776   }
 777
 778   /*
 779    * If the sender interface (NB: not originator) of this message
 780    * is not in the symmetric 1-hop neighborhood of this node, the
 781    * message MUST be discarded.
 782    */
 783   if (check_neighbor_link(from_addr) != SYM_LINK) {
 784     OLSR_DEBUG(LOG_TC, "Received TC from NON SYM neighbor %s\n", olsr_ip_to_string(&buf, from_addr));
 785     return;
 786   }
 787
 788   pkt_get_reltime(&curr, &vtime);
 789   pkt_get_u16(&curr, &size);
 790
 791   pkt_get_ipaddress(&curr, &originator);
 792
 793   /* Copy header values */
 794   pkt_get_u8(&curr, &ttl);
 795   pkt_get_u8(&curr, &msg_hops);
 796   pkt_get_u16(&curr, &msg_seq);
 797   pkt_get_u16(&curr, &ansn);
 798
 799   /* Get borders */
 800   pkt_get_u8(&curr, &lower_border);
 801   pkt_get_u8(&curr, &upper_border);
 802
 803   tc = olsr_lookup_tc_entry(&originator);
 804
 805   /* TCs can be splitted, so we are looking for ANSNs equal or higher */
 806   if (tc && status != RESET_SEQNO_OLSR_MESSAGE && tc->tc_seq != -1 && olsr_seqno_diff(ansn, tc->ansn) < 0) {
 807     /* this TC is too old, discard it */
 808     return;
 809   }
 810
 811   /*
 812    * Generate a new tc_entry in the lsdb and store the sequence number.
 813    */
 814   if (!tc) {
 815     tc = olsr_add_tc_entry(&originator);
 816   }
 817
 818   /*
 819    * Update the tc entry.
 820    */
 821   tc->msg_hops = msg_hops;
 822   tc->tc_seq = msg_seq;
 823   tc->ansn = ansn;
 824   tc->ignored = 0;
 825   tc->err_seq_valid = false;
 826   tc->is_virtual = false;
 827
 828   OLSR_DEBUG(LOG_TC, "Processing TC from %s, seq 0x%04x\n", olsr_ip_to_string(&buf, &originator), tc->tc_seq);
 829
 830   /*
 831    * Now walk the edge advertisements contained in the packet.
 832    */
 833
 834   limit = (unsigned char *)msg + size;
 835   borderSet = 0;
 836   relevantTc = false;
 837   while (curr + olsr_cnf->ipsize + olsr_sizeof_TCLQ() <= limit) {
 838     if (olsr_tc_update_edge(tc, ansn, &curr, &upper_border_ip)) {
 839       relevantTc = true;
 840     }
 841
 842     if (!borderSet) {
 843       borderSet = 1;
 844       memcpy(&lower_border_ip, &upper_border_ip, sizeof(lower_border_ip));
 845     }
 846   }
 847
 848   if (relevantTc) {
 849     relevantTcCount++;
 850     changes_topology = true;
 851   }
 852
 853   /*
 854    * Calculate real border IPs.
 855    */
 856   if (borderSet) {
 857     borderSet = olsr_calculate_tc_border(lower_border, &lower_border_ip, upper_border, &upper_border_ip);
 858   }
 859
 860   /*
 861    * Set or change the expiration timer accordingly.
 862    */
 863   olsr_set_timer(&tc->validity_timer, vtime,
 864                  OLSR_TC_VTIME_JITTER, OLSR_TIMER_ONESHOT, &olsr_expire_tc_entry, tc, tc_validity_timer_cookie);
 865
 866   if (borderSet) {
 867
 868     /*
 869      * Delete all old tc edges within borders.
 870      */
 871     olsr_delete_revoked_tc_edges(tc, ansn, &lower_border_ip, &upper_border_ip);
 872   } else {
 873
 874     /*
 875      * Kick the the edge garbage collection timer. In the meantime hopefully
 876      * all edges belonging to a multipart neighbor set will arrive.
 877      */
 878     olsr_set_timer(&tc->edge_gc_timer, OLSR_TC_EDGE_GC_TIME,
 879                    OLSR_TC_EDGE_GC_JITTER, OLSR_TIMER_ONESHOT, &olsr_expire_tc_edge_gc, tc, tc_edge_gc_timer_cookie);
 880   }
 881 }
 882
 883 uint32_t
 884 getRelevantTcCount(void)
 885 {
 886   return relevantTcCount;
 887 }
 888
 889 void
 890 olsr_delete_all_tc_entries(void) {
 891   struct tc_entry *tc;
 892   struct link_entry *link;
 893
 894   /* then remove all tc entries */
 895   OLSR_FOR_ALL_TC_ENTRIES(tc) {
 896     tc->is_virtual = 0;
 897   } OLSR_FOR_ALL_TC_ENTRIES_END(tc)
 898
 899   OLSR_FOR_ALL_TC_ENTRIES(tc) {
 900     if (tc != tc_myself) {
 901       olsr_delete_tc_entry(tc);
 902     }
 903   } OLSR_FOR_ALL_TC_ENTRIES_END(tc)
 904
 905   /* kill all references in link_set */
 906   OLSR_FOR_ALL_LINK_ENTRIES(link) {
 907     link->link_tc_edge = NULL;
 908   } OLSR_FOR_ALL_LINK_ENTRIES_END(link)
 909
 910
 911   /* kill tc_myself */
 912   if (tc_myself) {
 913     olsr_delete_tc_entry(tc_myself);
 914     olsr_unlock_tc_entry(tc_myself);
 915     tc_myself = NULL;
 916   }
 917 }
 918
 919 static uint8_t
 920 calculate_border_flag(void *lower_border, void *higher_border)
 921 {
 922   uint8_t *lower = lower_border;
 923   uint8_t *higher = higher_border;
 924   uint8_t bitmask;
 925   uint8_t part, bitpos;
 926
 927   for (part = 0; part < olsr_cnf->ipsize; part++) {
 928     if (lower[part] != higher[part]) {
 929       break;
 930     }
 931   }
 932
 933   if (part == olsr_cnf->ipsize) {       // same IPs ?
 934     return 0;
 935   }
 936   // look for first bit of difference
 937   bitmask = 0xfe;
 938   for (bitpos = 0; bitpos < 8; bitpos++, bitmask <<= 1) {
 939     if ((lower[part] & bitmask) == (higher[part] & bitmask)) {
 940       break;
 941     }
 942   }
 943
 944   bitpos += 8 * (olsr_cnf->ipsize - part - 1);
 945   return bitpos + 1;
 946 }
 947
 948 uint16_t
 949 get_local_ansn_number(void) {
 950   return local_ansn_number;
 951 }
 952
 953 void
 954 increase_local_ansn_number(void) {
 955   local_ansn_number++;
 956 }
 957
 958 static bool
 959 olsr_output_lq_tc_internal(void *ctx  __attribute__ ((unused)), union olsr_ip_addr *nextIp, bool skip)
 960 {
 961   static int ttl_list[] = { 2, 8, 2, 16, 2, 8, 2, MAX_TTL };
 962   struct interface *ifp;
 963   struct nbr_entry *nbr;
 964   struct link_entry *link;
 965   uint8_t msg_buffer[MAXMESSAGESIZE - OLSR_HEADERSIZE] __attribute__ ((aligned));
 966   uint8_t *curr = msg_buffer;
 967   uint8_t *length_field, *border_flags, *seqno, *last;
 968   bool sendTC = false, nextFragment = false;
 969   uint8_t ttl = 255;
 970
 971   OLSR_INFO(LOG_PACKET_CREATION, "Building TC\n-------------------\n");
 972
 973   pkt_put_u8(&curr, olsr_get_TC_MessageId());
 974   pkt_put_reltime(&curr, olsr_cnf->tc_params.validity_time);
 975
 976   length_field = curr;
 977   pkt_put_u16(&curr, 0); /* put in real messagesize later */
 978
 979   pkt_put_ipaddress(&curr, &olsr_cnf->router_id);
 980
 981   if (olsr_cnf->lq_fish > 0) {
 982     /* handle fisheye */
 983     ttl_index++;
 984     if (ttl_index >= (int)ARRAYSIZE(ttl_list)) {
 985       ttl_index = 0;
 986     }
 987     if (ttl_index >= 0) {
 988       ttl = ttl_list[ttl_index];
 989     }
 990   }
 991   pkt_put_u8(&curr, ttl);
 992
 993   /* hopcount */
 994   pkt_put_u8(&curr, 0);
 995
 996   /* reserve sequence number lazy */
 997   seqno = curr;
 998   pkt_put_u16(&curr, 0);
 999   pkt_put_u16(&curr, get_local_ansn_number());
1000
1001   /* border flags */
1002   border_flags = curr;
1003   pkt_put_u16(&curr, 0xffff);
1004
1005   last = msg_buffer + sizeof(msg_buffer) - olsr_cnf->ipsize - olsr_sizeof_TCLQ();
1006
1007   OLSR_FOR_ALL_NBR_ENTRIES(nbr) {
1008     /* allow fragmentation */
1009     if (skip) {
1010       struct nbr_entry *prevNbr;
1011       if (olsr_ipcmp(&nbr->nbr_addr, nextIp) != 0) {
1012         continue;
1013       }
1014       skip = false;
1015
1016       /* rewrite lower border flag */
1017       prevNbr = nbr_node_to_nbr(nbr->nbr_node.prev);
1018       *border_flags = calculate_border_flag(&prevNbr->nbr_addr, &nbr->nbr_addr);
1019     }
1020
1021     /* too long ? */
1022     if (curr > last) {
1023       /* rewrite upper border flag */
1024       struct nbr_entry *prevNbr = nbr_node_to_nbr(nbr->nbr_node.prev);
1025
1026       *(border_flags+1) = calculate_border_flag(&prevNbr->nbr_addr, &nbr->nbr_addr);
1027       *nextIp = nbr->nbr_addr;
1028       nextFragment = true;
1029       break;
1030     }
1031
1032     /*
1033      * TC redundancy 2
1034      *
1035      * Only consider symmetric neighbours.
1036      */
1037     if (!nbr->is_sym) {
1038       continue;
1039     }
1040
1041     /*
1042      * TC redundancy 1
1043      *
1044      * Only consider MPRs and MPR selectors
1045      */
1046     if (olsr_cnf->tc_redundancy == 1 && !nbr->is_mpr && nbr->mprs_count == 0) {
1047       continue;
1048     }
1049
1050     /*
1051      * TC redundancy 0
1052      *
1053      * Only consider MPR selectors
1054      */
1055     if (olsr_cnf->tc_redundancy == 0 && nbr->mprs_count == 0) {
1056       continue;
1057     }
1058
1059     /* Set the entry's link quality */
1060     link = get_best_link_to_neighbor(&nbr->nbr_addr);
1061     if (!link) {
1062       /* no link ? */
1063       continue;
1064     }
1065
1066     if (link->linkcost >= LINK_COST_BROKEN) {
1067       /* don't advertisebroken links */
1068       continue;
1069     }
1070
1071     pkt_put_ipaddress(&curr, &nbr->nbr_addr);
1072     olsr_serialize_tc_lq(&curr, link);
1073
1074     sendTC = true;
1075   } OLSR_FOR_ALL_NBR_ENTRIES_END()
1076
1077   if (!sendTC && skip) {
1078     OLSR_DEBUG(LOG_TC, "Nothing to send for this TC...\n");
1079     return false;
1080   }
1081
1082   /* late initialization of length and sequence number */
1083   pkt_put_u16(&seqno, get_msg_seqno());
1084   pkt_put_u16(&length_field, curr - msg_buffer);
1085
1086   /* send to all interfaces */
1087   OLSR_FOR_ALL_INTERFACES(ifp) {
1088     if (net_outbuffer_bytes_left(ifp) < curr - msg_buffer) {
1089       net_output(ifp);
1090       set_buffer_timer(ifp);
1091     }
1092     net_outbuffer_push(ifp, msg_buffer, curr - msg_buffer);
1093   } OLSR_FOR_ALL_INTERFACES_END(ifp)
1094   return nextFragment;
1095 }
1096
1097 void
1098 olsr_output_lq_tc(void *ctx) {
1099   union olsr_ip_addr next;
1100   bool skip = false;
1101
1102   memset(&next, 0, sizeof(next));
1103
1104   while ((skip = olsr_output_lq_tc_internal(ctx, &next, skip)));
1105 }
1106
1107 /*
1108  * Local Variables:
1109  * c-basic-offset: 2
1110  * indent-tabs-mode: nil
1111  * End:
1112  */