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