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