move avl and list library into src/common
[olsrd.git] / 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  */