remove the per tc_edge timer
[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 #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  */