src/tc_set.c

   1 /*
   2  * The olsr.org Optimized Link-State Routing daemon(olsrd)
   3  * Copyright (c) 2004, Andreas Tønnesen(andreto@olsr.org)
   4  * LSDB rewrite (c) 2007, Hannes Gredler (hannes@gredler.at)
   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
  42 #include "tc_set.h"
  43 #include "ipcalc.h"
  44 #include "mid_set.h"
  45 #include "link_set.h"
  46 #include "olsr.h"
  47 #include "scheduler.h"
  48 #include "lq_route.h"
  49 #include "common/avl.h"
  50 #include "lq_packet.h"
  51 #include "net_olsr.h"
  52 #include "lq_plugin.h"
  53 #include "olsr_cookie.h"
  54
  55 #include <assert.h>
  56
  57 /* Root of the link state database */
  58 struct avl_tree tc_tree;
  59 struct tc_entry *tc_myself; /* Shortcut to ourselves */
  60
  61 /* Some cookies for stats keeping */
  62 struct olsr_cookie_info *tc_edge_gc_timer_cookie = NULL;
  63 struct olsr_cookie_info *tc_validity_timer_cookie = NULL;
  64 struct olsr_cookie_info *tc_edge_mem_cookie = NULL;
  65 struct olsr_cookie_info *tc_mem_cookie = NULL;
  66
  67 /*
  68  * Sven-Ola 2007-Dec: These four constants include an assumption
  69  * on how long a typical olsrd mesh memorizes (TC) messages in the
  70  * RAM of all nodes and how many neighbour changes between TC msgs.
  71  * In Berlin, we encounter hop values up to 70 which means that
  72  * messages may live up to ~15 minutes cycling between nodes and
  73  * obviously breaking out of the timeout_dup() jail. It may be more
  74  * correct to dynamically adapt those constants, e.g. by using the
  75  * max hop number (denotes size-of-mesh) in some form or maybe
  76  * a factor indicating how many (old) versions of olsrd are on.
  77  */
  78
  79 /* Value window for ansn, identifies old messages to be ignored */
  80 #define TC_ANSN_WINDOW 256
  81 /* Value window for seqno, identifies old messages to be ignored */
  82 #define TC_SEQNO_WINDOW 1024
  83
  84 /* Enlarges the value window for upcoming ansn/seqno to be accepted */
  85 #define TC_ANSN_WINDOW_MULT 4
  86 /* Enlarges the value window for upcoming ansn/seqno to be accepted */
  87 #define TC_SEQNO_WINDOW_MULT 8
  88
  89 static olsr_bool
  90 olsr_seq_inrange_low(int beg, int end, olsr_u16_t seq)
  91 {
  92   if (beg < 0) {
  93     if (seq >= (olsr_u16_t)beg || seq < end) {
  94       return OLSR_TRUE;
  95     }
  96   } else if (end >= 0x10000) {
  97     if (seq >= beg || seq < (olsr_u16_t)end) {
  98       return OLSR_TRUE;
  99     }
 100   } else if (seq >= beg && seq < end) {
 101     return OLSR_TRUE;
 102   }
 103   return OLSR_FALSE;
 104 }
 105
 106 static olsr_bool
 107 olsr_seq_inrange_high(int beg, int end, olsr_u16_t seq)
 108 {
 109   if (beg < 0) {
 110     if (seq > (olsr_u16_t)beg || seq <= end) {
 111       return OLSR_TRUE;
 112     }
 113   } else if (end >= 0x10000) {
 114     if (seq > beg || seq <= (olsr_u16_t)end) {
 115       return OLSR_TRUE;
 116     }
 117   } else if (seq > beg && seq <= end) {
 118     return OLSR_TRUE;
 119   }
 120   return OLSR_FALSE;
 121 }
 122
 123 /**
 124  * Add a new tc_entry to the tc tree
 125  *
 126  * @param (last)adr address of the entry
 127  * @return a pointer to the created entry
 128  */
 129 static struct tc_entry *
 130 olsr_add_tc_entry(union olsr_ip_addr *adr)
 131 {
 132 #if !defined(NODEBUG) && defined(DEBUG)
 133   struct ipaddr_str buf;
 134 #endif
 135   struct tc_entry *tc;
 136
 137 #ifdef DEBUG
 138   OLSR_PRINTF(1, "TC: add entry %s\n", olsr_ip_to_string(&buf, adr));
 139 #endif
 140
 141   tc = olsr_cookie_malloc(tc_mem_cookie);
 142   if (!tc) {
 143     return NULL;
 144   }
 145
 146   /* Fill entry */
 147   tc->addr = *adr;
 148   tc->vertex_node.key = &tc->addr;
 149
 150   /*
 151    * Insert into the global tc tree.
 152    */
 153   avl_insert(&tc_tree, &tc->vertex_node, AVL_DUP_NO);
 154   olsr_lock_tc_entry(tc);
 155
 156   /*
 157    * Initialize subtrees for edges and prefixes.
 158    */
 159   avl_init(&tc->edge_tree, avl_comp_default);
 160   avl_init(&tc->prefix_tree, avl_comp_prefix_default);
 161
 162   /*
 163    * Add a rt_path for ourselves.
 164    */
 165   olsr_insert_routing_table(adr, olsr_cnf->maxplen, adr,
 166                             OLSR_RT_ORIGIN_INT);
 167
 168   return tc;
 169 }
 170
 171 /**
 172  * Initialize the topology set
 173  *
 174  */
 175 void
 176 olsr_init_tc(void)
 177 {
 178   OLSR_PRINTF(5, "TC: init topo\n");
 179
 180   avl_init(&tc_tree, avl_comp_default);
 181
 182   /*
 183    * Get some cookies for getting stats to ease troubleshooting.
 184    */
 185   tc_edge_gc_timer_cookie = olsr_alloc_cookie("TC edge GC", OLSR_COOKIE_TYPE_TIMER);
 186   tc_validity_timer_cookie = olsr_alloc_cookie("TC validity", OLSR_COOKIE_TYPE_TIMER);
 187
 188   tc_edge_mem_cookie = olsr_alloc_cookie("TC edge", OLSR_COOKIE_TYPE_MEMORY);
 189   olsr_cookie_set_memory_size(tc_edge_mem_cookie, sizeof(struct tc_edge_entry));
 190
 191   tc_mem_cookie = olsr_alloc_cookie("TC", OLSR_COOKIE_TYPE_MEMORY);
 192   olsr_cookie_set_memory_size(tc_mem_cookie, sizeof(struct tc_entry));
 193
 194   /*
 195    * Add a TC entry for ourselves.
 196    */
 197   tc_myself = olsr_add_tc_entry(&olsr_cnf->main_addr);
 198 }
 199
 200 /**
 201  * The main ip address has changed.
 202  * Do the needful.
 203  */
 204 void
 205 olsr_change_myself_tc(void)
 206 {
 207   if (tc_myself) {
 208
 209     /*
 210      * Check if there was a change.
 211      */
 212     if (ipequal(&tc_myself->addr, &olsr_cnf->main_addr)) {
 213       return;
 214     }
 215
 216     /*
 217      * Flush our own tc_entry.
 218      */
 219     olsr_delete_tc_entry(tc_myself);
 220   }
 221
 222   /*
 223    * The old entry for ourselves is gone, generate a new one and trigger SPF.
 224    */
 225   tc_myself = olsr_add_tc_entry(&olsr_cnf->main_addr);
 226   changes_topology = OLSR_TRUE;
 227 }
 228
 229 /*
 230  * Increment the reference counter.
 231  */
 232 void
 233 olsr_lock_tc_entry(struct tc_entry *tc)
 234 {
 235   tc->refcount++;
 236 }
 237
 238 /*
 239  * Unlock and free a tc_entry once all references are gone.
 240  */
 241 void
 242 olsr_unlock_tc_entry(struct tc_entry *tc)
 243 {
 244   if (--tc->refcount) {
 245     return;
 246   }
 247
 248   /*
 249    * All references are gone.
 250    */
 251   olsr_cookie_free(tc_mem_cookie, tc);
 252 }
 253
 254 /**
 255  * Delete a TC entry.
 256  *
 257  * @param entry the TC entry to delete
 258  *
 259  */
 260 void
 261 olsr_delete_tc_entry(struct tc_entry *tc)
 262 {
 263   struct tc_edge_entry *tc_edge;
 264   struct rt_path *rtp;
 265 #if 0
 266   struct ipaddr_str buf;
 267   OLSR_PRINTF(1, "TC: del entry %s\n", olsr_ip_to_string(&buf, &tc->addr));
 268 #endif
 269
 270   /*
 271    * Delete the rt_path for ourselves.
 272    */
 273   olsr_delete_routing_table(&tc->addr, olsr_cnf->maxplen, &tc->addr);
 274
 275   /* The edgetree and prefix tree must be empty before */
 276   OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
 277     olsr_delete_tc_edge_entry(tc_edge);
 278   } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge);
 279
 280   OLSR_FOR_ALL_PREFIX_ENTRIES(tc, rtp) {
 281     olsr_delete_rt_path(rtp);
 282   } OLSR_FOR_ALL_PREFIX_ENTRIES_END(tc, rtp);
 283
 284   /* Stop running timers */
 285   olsr_stop_timer(tc->edge_gc_timer);
 286   tc->edge_gc_timer = NULL;
 287   olsr_stop_timer(tc->validity_timer);
 288   tc->validity_timer = NULL;
 289
 290   avl_delete(&tc_tree, &tc->vertex_node);
 291   olsr_unlock_tc_entry(tc);
 292 }
 293
 294 /**
 295  * Look up a entry from the TC tree based on address
 296  *
 297  * @param adr the address to look for
 298  * @return the entry found or NULL
 299  */
 300 struct tc_entry *
 301 olsr_lookup_tc_entry(union olsr_ip_addr *adr)
 302 {
 303   struct avl_node *node;
 304
 305 #if 0
 306   OLSR_PRINTF(1, "TC: lookup entry\n");
 307 #endif
 308
 309   node = avl_find(&tc_tree, adr);
 310
 311   return (node ? vertex_tree2tc(node) : NULL);
 312 }
 313
 314 /*
 315  * Lookup a tc entry. Creates one if it does not exist yet.
 316  */
 317 struct tc_entry *
 318 olsr_locate_tc_entry(union olsr_ip_addr *adr)
 319 {
 320   struct tc_entry *tc;
 321
 322   if (!(tc = olsr_lookup_tc_entry(adr))) {
 323     return olsr_add_tc_entry(adr);
 324   }
 325   return tc;
 326 }
 327
 328 /**
 329  * Format tc_edge contents into a buffer.
 330  */
 331 char *
 332 olsr_tc_edge_to_string(struct tc_edge_entry *tc_edge)
 333 {
 334   static char buf[128];
 335   struct ipaddr_str addrbuf, dstbuf;
 336   struct tc_entry *tc = tc_edge->tc;
 337   struct lqtextbuffer lqbuffer1, lqbuffer2;
 338
 339   snprintf(buf, sizeof(buf),
 340            "%s > %s, cost (%6s) %s",
 341            olsr_ip_to_string(&addrbuf, &tc->addr),
 342            olsr_ip_to_string(&dstbuf, &tc_edge->T_dest_addr),
 343            get_tc_edge_entry_text(tc_edge, &lqbuffer1),
 344            get_linkcost_text(tc_edge->cost, OLSR_FALSE, &lqbuffer2));
 345
 346   return buf;
 347 }
 348
 349 /**
 350  * Wrapper for the timer callback.
 351  * A TC entry has not been refreshed in time.
 352  * Remove it from the link-state database.
 353  */
 354 static void
 355 olsr_expire_tc_entry(void *context)
 356 {
 357   struct tc_entry *tc;
 358
 359   tc = (struct tc_entry *)context;
 360   tc->validity_timer = NULL;
 361
 362   olsr_delete_tc_entry(tc);
 363   changes_topology = OLSR_TRUE;
 364 }
 365
 366 /**
 367  * Wrapper for the timer callback.
 368  * Does the garbage collection of older ansn entries after no edge addition to
 369  * the TC entry has happened for OLSR_TC_EDGE_GC_TIME.
 370  */
 371 static void
 372 olsr_expire_tc_edge_gc(void *context)
 373 {
 374   struct tc_entry *tc;
 375
 376   tc = (struct tc_entry *)context;
 377   tc->edge_gc_timer = NULL;
 378
 379   if (olsr_delete_outdated_tc_edges(tc)) {
 380     changes_topology = OLSR_TRUE;
 381   }
 382 }
 383
 384 /*
 385  * If the edge does not have a minimum acceptable link quality
 386  * set the etx cost to infinity such that it gets ignored during
 387  * SPF calculation.
 388  *
 389  * @return 1 if the change of the etx value was relevant
 390  */
 391 olsr_bool
 392 olsr_calc_tc_edge_entry_etx(struct tc_edge_entry *tc_edge)
 393 {
 394   olsr_linkcost old;
 395
 396   /*
 397    * Some sanity check before recalculating the etx.
 398    */
 399   if (olsr_cnf->lq_level < 1) {
 400     return 0;
 401   }
 402
 403   old = tc_edge->cost;
 404   tc_edge->cost = olsr_calc_tc_cost(tc_edge);
 405
 406   return olsr_is_relevant_costchange(old, tc_edge->cost);
 407 }
 408
 409 /**
 410  * Add a new tc_edge_entry to the tc_edge_tree
 411  *
 412  * @param (last)adr address of the entry
 413  * @return a pointer to the created entry
 414  */
 415 struct tc_edge_entry *
 416 olsr_add_tc_edge_entry(struct tc_entry *tc, union olsr_ip_addr *addr,
 417                        olsr_u16_t ansn)
 418 {
 419 #if !defined(NODEBUG) && defined(DEBUG)
 420   struct ipaddr_str buf;
 421 #endif
 422   struct tc_entry *tc_neighbor;
 423   struct tc_edge_entry *tc_edge, *tc_edge_inv;
 424
 425   tc_edge = olsr_malloc_tc_edge_entry("add TC edge");
 426   if (!tc_edge) {
 427     return NULL;
 428   }
 429
 430   /* Fill entry */
 431   tc_edge->T_dest_addr = *addr;
 432   tc_edge->ansn = ansn;
 433   tc_edge->edge_node.key = &tc_edge->T_dest_addr;
 434
 435   /*
 436    * Insert into the edge tree.
 437    */
 438   avl_insert(&tc->edge_tree, &tc_edge->edge_node, AVL_DUP_NO);
 439   olsr_lock_tc_entry(tc);
 440
 441   /*
 442    * Connect backpointer.
 443    */
 444   tc_edge->tc = tc;
 445
 446   /*
 447    * Check if the neighboring router and the inverse edge is in the lsdb.
 448    * Create short cuts to the inverse edge for faster SPF execution.
 449    */
 450   tc_neighbor = olsr_lookup_tc_entry(&tc_edge->T_dest_addr);
 451   if (tc_neighbor) {
 452 #ifdef DEBUG
 453     OLSR_PRINTF(1, "TC:   found neighbor tc_entry %s\n",
 454                 olsr_ip_to_string(&buf, &tc_neighbor->addr));
 455 #endif
 456
 457     tc_edge_inv = olsr_lookup_tc_edge(tc_neighbor, &tc->addr);
 458     if (tc_edge_inv) {
 459 #ifdef DEBUG
 460       OLSR_PRINTF(1, "TC:   found inverse edge for %s\n",
 461                   olsr_ip_to_string(&buf, &tc_edge_inv->T_dest_addr));
 462 #endif
 463
 464       /*
 465        * Connect the edges mutually.
 466        */
 467       tc_edge_inv->edge_inv = tc_edge;
 468       tc_edge->edge_inv = tc_edge_inv;
 469
 470     }
 471   }
 472
 473   /*
 474    * Update the etx.
 475    */
 476   olsr_calc_tc_edge_entry_etx(tc_edge);
 477
 478 #ifdef DEBUG
 479   OLSR_PRINTF(1, "TC: add edge entry %s\n", olsr_tc_edge_to_string(tc_edge));
 480 #endif
 481
 482   return tc_edge;
 483 }
 484
 485
 486 /**
 487  * Delete a TC edge entry.
 488  *
 489  * @param tc the TC entry
 490  * @param tc_edge the TC edge entry
 491  */
 492 void
 493 olsr_delete_tc_edge_entry(struct tc_edge_entry *tc_edge)
 494 {
 495   struct tc_entry *tc;
 496   struct tc_edge_entry *tc_edge_inv;
 497
 498 #ifdef DEBUG
 499   OLSR_PRINTF(1, "TC: del edge entry %s\n", olsr_tc_edge_to_string(tc_edge));
 500 #endif
 501
 502   tc = tc_edge->tc;
 503   avl_delete(&tc->edge_tree, &tc_edge->edge_node);
 504   olsr_unlock_tc_entry(tc);
 505
 506   /*
 507    * Clear the backpointer of our inverse edge.
 508    */
 509   tc_edge_inv = tc_edge->edge_inv;
 510   if (tc_edge_inv) {
 511     tc_edge_inv->edge_inv = NULL;
 512   }
 513
 514   free(tc_edge);
 515 }
 516
 517
 518 /**
 519  * Delete all destinations that have a lower ANSN.
 520  *
 521  * @param tc the entry to delete edges from
 522  * @param ansn the advertised neighbor set sequence number
 523  * @return 1 if any destinations were deleted 0 if not
 524  */
 525 olsr_bool
 526 olsr_delete_outdated_tc_edges(struct tc_entry *tc)
 527 {
 528   struct tc_edge_entry *tc_edge;
 529   olsr_bool retval = OLSR_FALSE;
 530
 531 #if 0
 532   OLSR_PRINTF(5, "TC: deleting outdated TC-edge entries\n");
 533 #endif
 534
 535   OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
 536     if (SEQNO_GREATER_THAN(tc->ansn, tc_edge->ansn)) {
 537       olsr_delete_tc_edge_entry(tc_edge);
 538       retval = OLSR_TRUE;
 539     }
 540   } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge);
 541
 542   return retval;
 543 }
 544
 545 /**
 546  * Update an edge registered on an entry.
 547  * Creates new edge-entries if not registered.
 548  * Bases update on a received TC message
 549  *
 550  * @param entry the TC entry to check
 551  * @pkt the TC edge entry in the packet
 552  * @return 1 if entries are added 0 if not
 553  */
 554 static int
 555 olsr_tc_update_edge(struct tc_entry *tc, olsr_u16_t ansn,
 556                     const unsigned char **curr)
 557 {
 558   struct tc_edge_entry *tc_edge;
 559   union olsr_ip_addr neighbor;
 560   int edge_change;
 561
 562   edge_change = 0;
 563
 564   /*
 565    * Fetch the per-edge data
 566    */
 567   pkt_get_ipaddress(curr, &neighbor);
 568
 569   /* First check if we know this edge */
 570   tc_edge = olsr_lookup_tc_edge(tc, &neighbor);
 571
 572   if(!tc_edge) {
 573
 574     /*
 575      * Yet unknown - create it.
 576      * Check if the address is allowed.
 577      */
 578     if (!olsr_validate_address(&neighbor)) {
 579       return 0;
 580     }
 581
 582     tc_edge = olsr_add_tc_edge_entry(tc, &neighbor, ansn);
 583
 584     olsr_deserialize_tc_lq_pair(curr, tc_edge);
 585     edge_change = 1;
 586
 587   } else {
 588
 589     /*
 590      * We know this edge - Update entry.
 591      */
 592     tc_edge->ansn = ansn;
 593
 594     /*
 595      * Update link quality if configured.
 596      */
 597     if (olsr_cnf->lq_level > 0) {
 598       olsr_deserialize_tc_lq_pair(curr, tc_edge);
 599     }
 600
 601     /*
 602      * Update the etx.
 603      */
 604     if (olsr_calc_tc_edge_entry_etx(tc_edge)) {
 605         if (tc->msg_hops <= olsr_cnf->lq_dlimit) {
 606                 edge_change = 1;
 607         }
 608     }
 609
 610 #if DEBUG
 611     if (edge_change) {
 612       OLSR_PRINTF(1, "TC:   chg edge entry %s\n",
 613                   olsr_tc_edge_to_string(tc_edge));
 614     }
 615 #endif
 616
 617   }
 618
 619   return edge_change;
 620 }
 621
 622 /**
 623  * Lookup an edge hanging off a TC entry.
 624  *
 625  * @param entry the entry to check
 626  * @param dst_addr the destination address to check for
 627  * @return a pointer to the tc_edge found - or NULL
 628  */
 629 struct tc_edge_entry *
 630 olsr_lookup_tc_edge(struct tc_entry *tc, union olsr_ip_addr *edge_addr)
 631 {
 632   struct avl_node *edge_node;
 633
 634 #if 0
 635   OLSR_PRINTF(1, "TC: lookup dst\n");
 636 #endif
 637
 638   edge_node = avl_find(&tc->edge_tree, edge_addr);
 639
 640   return (edge_node ? edge_tree2tc_edge(edge_node) : NULL);
 641 }
 642
 643 /**
 644  * Print the topology table to stdout
 645  */
 646 void
 647 olsr_print_tc_table(void)
 648 {
 649 #ifndef NODEBUG
 650   /* The whole function makes no sense without it. */
 651   struct tc_entry *tc;
 652   const int ipwidth = olsr_cnf->ip_version == AF_INET ? 15 : 30;
 653
 654   OLSR_PRINTF(1, "\n--- %s ------------------------------------------------- TOPOLOGY\n\n"
 655               "%-*s %-*s %-5s  %-5s  %s %s\n",
 656               olsr_wallclock_string(),
 657               ipwidth, "Source IP addr", ipwidth, "Dest IP addr", "LQ", "ILQ", "ETX", "UP");
 658
 659   OLSR_FOR_ALL_TC_ENTRIES(tc) {
 660     struct tc_edge_entry *tc_edge;
 661     OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
 662       struct ipaddr_str addrbuf, dstaddrbuf;
 663       struct lqtextbuffer lqbuffer1, lqbuffer2;
 664
 665       OLSR_PRINTF(1, "%-*s %-*s  (%-10s) %s\n",
 666                   ipwidth, olsr_ip_to_string(&addrbuf, &tc->addr),
 667                   ipwidth, olsr_ip_to_string(&dstaddrbuf, &tc_edge->T_dest_addr),
 668                   get_tc_edge_entry_text(tc_edge, &lqbuffer1),
 669                   get_linkcost_text(tc_edge->cost, OLSR_FALSE, &lqbuffer2));
 670
 671     } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge);
 672   } OLSR_FOR_ALL_TC_ENTRIES_END(tc);
 673 #endif
 674 }
 675
 676 /*
 677  * Process an incoming TC or TC_LQ message.
 678  *
 679  * If the message is interesting enough, update our edges for it,
 680  * trigger SPF and finally flood it to all our 2way neighbors.
 681  *
 682  * The order for extracting data off the message does matter,
 683  * as every call to pkt_get increases the packet offset and
 684  * hence the spot we are looking at.
 685  */
 686 void
 687 olsr_input_tc(union olsr_message *msg,
 688               struct interface *input_if __attribute__((unused)),
 689               union olsr_ip_addr *from_addr)
 690 {
 691 #ifndef NODEBUG
 692   struct ipaddr_str buf;
 693 #endif
 694   olsr_u16_t size, msg_seq, ansn;
 695   olsr_u8_t type, ttl, msg_hops;
 696   double vtime;
 697   unsigned int vtime_s;
 698   union olsr_ip_addr originator;
 699   const unsigned char *limit, *curr;
 700   struct tc_entry *tc;
 701
 702   curr = (void *)msg;
 703   if (!msg) {
 704     return;
 705   }
 706
 707   /* We are only interested in TC message types. */
 708   pkt_get_u8(&curr, &type);
 709   if ((type != LQ_TC_MESSAGE) && (type != TC_MESSAGE)) {
 710     return;
 711   }
 712
 713   pkt_get_double(&curr, &vtime);
 714   vtime_s = (unsigned int)vtime;
 715   pkt_get_u16(&curr, &size);
 716
 717   pkt_get_ipaddress(&curr, &originator);
 718
 719   /* Copy header values */
 720   pkt_get_u8(&curr, &ttl);
 721   pkt_get_u8(&curr, &msg_hops);
 722   pkt_get_u16(&curr, &msg_seq);
 723   pkt_get_u16(&curr, &ansn);
 724   pkt_ignore_u16(&curr);
 725
 726   tc = olsr_lookup_tc_entry(&originator);
 727
 728   if (tc && 0 != tc->edge_tree.count) {
 729     if (olsr_seq_inrange_high(
 730           (int)tc->msg_seq - TC_SEQNO_WINDOW,
 731           tc->msg_seq,
 732           msg_seq) &&
 733         olsr_seq_inrange_high(
 734           (int)tc->ansn - TC_ANSN_WINDOW,
 735           tc->ansn, ansn)) {
 736
 737       /*
 738        * Ignore already seen seq/ansn values (small window for mesh memory)
 739        */
 740       if ((tc->msg_seq == msg_seq) || (tc->ignored++ < 32)) {
 741         return;
 742       }
 743
 744       OLSR_PRINTF(1, "Ignored to much LQTC's for %s, restarting\n",
 745                   olsr_ip_to_string(&buf, &originator));
 746
 747     } else if (!olsr_seq_inrange_high(
 748                  tc->msg_seq,
 749                  (int)tc->msg_seq + TC_SEQNO_WINDOW * TC_SEQNO_WINDOW_MULT,
 750                  msg_seq) ||
 751                !olsr_seq_inrange_low(
 752                  tc->ansn,
 753                  (int)tc->ansn + TC_ANSN_WINDOW * TC_ANSN_WINDOW_MULT,
 754                  ansn)) {
 755
 756       /*
 757        * Only accept future seq/ansn values (large window for node reconnects).
 758        * Restart in all other cases. Ignore a single stray message.
 759        */
 760       if (!tc->err_seq_valid) {
 761         tc->err_seq = msg_seq;
 762         tc->err_seq_valid = OLSR_TRUE;
 763       }
 764       if (tc->err_seq == msg_seq) {
 765         return;
 766       }
 767
 768       OLSR_PRINTF(2, "Detected node restart for %s\n",
 769                   olsr_ip_to_string(&buf, &originator));
 770     }
 771   }
 772
 773   /*
 774    * Generate a new tc_entry in the lsdb and store the sequence number.
 775    */
 776   if (!tc) {
 777     tc = olsr_add_tc_entry(&originator);
 778   }
 779
 780   /*
 781    * Update the tc entry.
 782    */
 783   tc->msg_hops = msg_hops;
 784   tc->msg_seq = msg_seq;
 785   tc->ansn = ansn;
 786   tc->ignored = 0;
 787   tc->err_seq_valid = OLSR_FALSE;
 788
 789   /*
 790    * If the sender interface (NB: not originator) of this message
 791    * is not in the symmetric 1-hop neighborhood of this node, the
 792    * message MUST be discarded.
 793    */
 794   if (check_neighbor_link(from_addr) != SYM_LINK) {
 795     OLSR_PRINTF(2, "Received TC from NON SYM neighbor %s\n",
 796                 olsr_ip_to_string(&buf, from_addr));
 797     return;
 798   }
 799
 800   OLSR_PRINTF(1, "Processing TC from %s, seq 0x%04x\n",
 801               olsr_ip_to_string(&buf, &originator), ansn);
 802
 803   /*
 804    * Now walk the edge advertisements contained in the packet.
 805    */
 806   limit = (unsigned char *)msg + size;
 807   while (curr < limit) {
 808     if (olsr_tc_update_edge(tc, ansn, &curr)) {
 809       changes_topology = OLSR_TRUE;
 810     }
 811   }
 812
 813   /*
 814    * Set or change the expiration timer accordingly.
 815    */
 816   olsr_set_timer(&tc->validity_timer, vtime_s * MSEC_PER_SEC,
 817                  OLSR_TC_VTIME_JITTER, OLSR_TIMER_ONESHOT,
 818                  &olsr_expire_tc_entry, tc, tc_validity_timer_cookie->ci_id);
 819
 820   /*
 821    * Kick the the edge garbage collection timer. In the meantime hopefully
 822    * all edges belonging to a multipart neighbor set will arrive.
 823    */
 824   olsr_set_timer(&tc->edge_gc_timer, OLSR_TC_EDGE_GC_TIME,
 825                  OLSR_TC_EDGE_GC_JITTER, OLSR_TIMER_ONESHOT,
 826                  &olsr_expire_tc_edge_gc, tc, tc_edge_gc_timer_cookie->ci_id);
 827
 828   /*
 829    * Last, flood the message to our other neighbors.
 830    */
 831   olsr_forward_message(msg, from_addr);
 832   return;
 833 }
 834
 835 /*
 836  * Local Variables:
 837  * c-basic-offset: 2
 838  * End:
 839  */