d069c2ce2528d35af046425c120a0f45a5ee4b69
[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 "lq_avl.h"
50 #include "lq_packet.h"
51 #include "net_olsr.h"
52
53 #include <assert.h>
54
55 /* Root of the link state database */
56 struct avl_tree tc_tree;
57 struct tc_entry *tc_myself; /* Shortcut to ourselves */
58
59 /* Sven-Ola 2007-Dec: These four constants include an assumption
60  * on how long a typical olsrd mesh memorizes (TC) messages in the
61  * RAM of all nodes and how many neighbour changes between TC msgs.
62  * In Berlin, we encounter hop values up to 70 which means that
63  * messages may live up to ~15 minutes cycling between nodes and
64  * obviously breaking out of the timeout_dup() jail. It may be more
65  * correct to dynamically adapt those constants, e.g. by using the
66  * max hop number (denotes size-of-mesh) in some form or maybe
67  * a factor indicating how many (old) versions of olsrd are on.
68  */
69
70 /* Value window for ansn, identifies old messages to be ignored */
71 #define TC_ANSN_WINDOW 256
72 /* Value window for seqno, identifies old messages to be ignored */
73 #define TC_SEQNO_WINDOW 1024
74
75 /* Enlarges the value window for upcoming ansn/seqno to be accepted */
76 #define TC_ANSN_WINDOW_MULT 4
77 /* Enlarges the value window for upcoming ansn/seqno to be accepted */
78 #define TC_SEQNO_WINDOW_MULT 8
79
80 static olsr_bool
81 olsr_seq_inrange_low(int beg, int end, olsr_u16_t seq)
82 {
83   if (beg < 0) {
84     if (seq >= (olsr_u16_t)beg || seq < end) {
85       return OLSR_TRUE;
86     }
87   } else if (end >= 0x10000) {
88     if (seq >= beg || seq < (olsr_u16_t)end) {
89       return OLSR_TRUE;
90     }
91   } else if (seq >= beg && seq < end) {
92     return OLSR_TRUE;
93   }
94   return OLSR_FALSE;
95 }
96
97 static olsr_bool
98 olsr_seq_inrange_high(int beg, int end, olsr_u16_t seq)
99 {
100   if (beg < 0) {
101     if (seq > (olsr_u16_t)beg || seq <= end) {
102       return OLSR_TRUE;
103     }
104   } else if (end >= 0x10000) {
105     if (seq > beg || seq <= (olsr_u16_t)end) {
106       return OLSR_TRUE;
107     }
108   } else if (seq > beg && seq <= end) {
109     return OLSR_TRUE;
110   }
111   return OLSR_FALSE;
112 }
113
114 /**
115  * Add a new tc_entry to the tc tree
116  *
117  * @param (last)adr address of the entry
118  * @return a pointer to the created entry
119  */
120 static struct tc_entry *
121 olsr_add_tc_entry(union olsr_ip_addr *adr)
122 {
123 #if !defined(NODEBUG) && defined(DEBUG)
124   struct ipaddr_str buf;
125 #endif
126   struct tc_entry *tc;
127
128 #ifdef DEBUG
129   OLSR_PRINTF(1, "TC: add entry %s\n", olsr_ip_to_string(&buf, adr));
130 #endif
131
132   tc = olsr_malloc(sizeof(struct tc_entry), "add TC entry");
133   if (!tc) {
134     return NULL;
135   }
136   memset(tc, 0, sizeof(struct tc_entry));
137
138   /* Fill entry */
139   tc->addr = *adr;
140   tc->vertex_node.data = tc;
141   tc->vertex_node.key = &tc->addr;
142
143   /*
144    * Insert into the global tc tree.
145    */
146   avl_insert(&tc_tree, &tc->vertex_node, AVL_DUP_NO);
147
148   /*
149    * Initialize subtrees for edges and prefixes.
150    */
151   avl_init(&tc->edge_tree, avl_comp_default);
152   avl_init(&tc->prefix_tree, avl_comp_prefix_default);
153
154   /*
155    * Add a rt_path for ourselves.
156    */
157   olsr_insert_routing_table(adr, olsr_cnf->maxplen, adr,
158                             OLSR_RT_ORIGIN_INT);
159
160   return tc;
161 }
162
163 /**
164  * Initialize the topology set
165  *
166  */
167 void
168 olsr_init_tc(void)
169 {
170   OLSR_PRINTF(5, "TC: init topo\n");
171
172   olsr_register_timeout_function(&olsr_time_out_tc_set, OLSR_TRUE);
173
174   avl_init(&tc_tree, avl_comp_default);
175
176   /*
177    * Add a TC entry for ourselves.
178    */
179   tc_myself = olsr_add_tc_entry(&olsr_cnf->main_addr);
180 }
181
182 /**
183  * The main ip address has changed.
184  * Do the needful.
185  */
186 void
187 olsr_change_myself_tc(void)
188 {
189   struct tc_edge_entry *tc_edge;
190
191   if (tc_myself) {
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 a 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
289   snprintf(buf, sizeof(buf),
290            "%s > %s, lq %.3f, inv-lq %.3f, etx %.3f",
291            olsr_ip_to_string(&addrbuf, &tc->addr),
292            olsr_ip_to_string(&dstbuf, &tc_edge->T_dest_addr),
293            tc_edge->link_quality,
294            tc_edge->inverse_link_quality,
295            tc_edge->etx);
296
297   return buf;
298 }
299
300 /**
301  * Set the TC edge expiration timer.
302  *
303  * all timer setting shall be done using this function since
304  * it does also the correct insertion and sorting in the timer tree.
305  * The timer param is a relative timer expressed in milliseconds.
306  */
307 void
308 olsr_set_tc_edge_timer(struct tc_edge_entry *tc_edge, unsigned int timer)
309 {
310   tc_edge->T_time = GET_TIMESTAMP(timer);
311 }
312
313 /*
314  * If the edge does not have a minimum acceptable link quality
315  * set the etx cost to infinity such that it gets ignored during
316  * SPF calculation.
317  */
318 void
319 olsr_calc_tc_edge_entry_etx(struct tc_edge_entry *tc_edge)
320 {
321
322   /*
323    * Some sanity check before recalculating the etx.
324    */
325   if (olsr_cnf->lq_level < 1) {
326     return;
327   }
328
329   if (tc_edge->link_quality < MIN_LINK_QUALITY &&
330       tc_edge->inverse_link_quality < MIN_LINK_QUALITY) {
331     tc_edge->etx = INFINITE_ETX;
332   } else {
333     tc_edge->etx = 1.0 / (tc_edge->link_quality * tc_edge->inverse_link_quality);
334   }
335 }
336
337 /**
338  * Add a new tc_edge_entry to the tc_edge_tree
339  *
340  * @param (last)adr address of the entry
341  * @return a pointer to the created entry
342  */
343 struct tc_edge_entry *
344 olsr_add_tc_edge_entry(struct tc_entry *tc, union olsr_ip_addr *addr,
345                        olsr_u16_t ansn, unsigned int vtime,
346                        float link_quality, float neigh_link_quality)
347 {
348 #if !defined(NODEBUG) && defined(DEBUG)
349   struct ipaddr_str buf;
350 #endif
351   struct tc_entry *tc_neighbor;
352   struct tc_edge_entry *tc_edge, *tc_edge_inv;
353
354   tc_edge = olsr_malloc(sizeof(struct tc_edge_entry), "add TC edge");
355   if (!tc_edge) {
356     return NULL;
357   }
358   memset(tc_edge, 0, sizeof(struct tc_edge_entry));
359
360   /* Fill entry */
361   tc_edge->T_dest_addr = *addr;
362   olsr_set_tc_edge_timer(tc_edge, vtime*1000);
363   tc_edge->T_seq = ansn;
364   tc_edge->edge_node.data = tc_edge;
365   tc_edge->edge_node.key = &tc_edge->T_dest_addr;
366
367   if (olsr_cnf->lq_level > 0) {
368     tc_edge->link_quality = neigh_link_quality;
369     tc_edge->inverse_link_quality = link_quality;
370   } else {
371
372     /*
373      * Set the link quality to 1.0 to mimikry a hopcount alike
374      * behaviour for nodes not supporting the LQ extensions.
375      */
376     tc_edge->link_quality = 1.0;
377     tc_edge->inverse_link_quality = 1.0;
378   }
379
380   /*
381    * Insert into the edge tree.
382    */
383   avl_insert(&tc->edge_tree, &tc_edge->edge_node, AVL_DUP_NO);
384
385   /*
386    * Connect backpointer.
387    */
388   tc_edge->tc = tc;
389
390 #ifdef DEBUG
391   OLSR_PRINTF(1, "TC: add edge entry %s\n", olsr_tc_edge_to_string(tc_edge));
392 #endif
393
394   /*
395    * Check if the neighboring router and the inverse edge is in the lsdb.
396    * Create short cuts to the inverse edge for faster SPF execution.
397    */
398   tc_neighbor = olsr_lookup_tc_entry(&tc_edge->T_dest_addr);
399   if (tc_neighbor) {
400 #ifdef DEBUG
401     OLSR_PRINTF(1, "TC:   found neighbor tc_entry %s\n",
402                 olsr_ip_to_string(&buf, &tc_neighbor->addr));
403 #endif
404
405     tc_edge_inv = olsr_lookup_tc_edge(tc_neighbor, &tc->addr);
406     if (tc_edge_inv) {
407 #ifdef DEBUG
408       OLSR_PRINTF(1, "TC:   found inverse edge for %s\n",
409                   olsr_ip_to_string(&buf, &tc_edge_inv->T_dest_addr));
410 #endif
411
412       /*
413        * Connect the edges mutually.
414        */
415       tc_edge_inv->edge_inv = tc_edge;
416       tc_edge->edge_inv = tc_edge_inv;
417
418     }
419   }
420
421   /*
422    * Update the etx.
423    */
424   olsr_calc_tc_edge_entry_etx(tc_edge);
425
426   return tc_edge;
427 }
428
429
430 /**
431  * Delete a TC edge entry.
432  *
433  * @param tc the TC entry
434  * @param tc_edge the TC edge entry
435  */
436 void
437 olsr_delete_tc_edge_entry(struct tc_edge_entry *tc_edge)
438 {
439   struct tc_entry *tc;
440   struct tc_edge_entry *tc_edge_inv;
441
442 #ifdef DEBUG
443   OLSR_PRINTF(1, "TC: del edge entry %s\n", olsr_tc_edge_to_string(tc_edge));
444 #endif
445
446   tc = tc_edge->tc;
447   avl_delete(&tc->edge_tree, &tc_edge->edge_node);
448
449   /*
450    * Clear the backpointer of our inverse edge.
451    */
452   tc_edge_inv = tc_edge->edge_inv;
453   if (tc_edge_inv) {
454     tc_edge_inv->edge_inv = NULL;
455   }
456
457   /*
458    * Delete the tc_entry if the last edge and last prefix is gone.
459    */
460   if (!tc_edge->tc->edge_tree.count &&
461       !tc_edge->tc->prefix_tree.count) {
462
463     /*
464      * Only remove remote tc entries.
465      */
466     if (tc_edge->tc != tc_myself) {
467       olsr_delete_tc_entry(tc_edge->tc);
468     }
469   }
470
471   free(tc_edge);
472 }
473
474
475 /**
476  * Delete all destinations that have a lower ANSN.
477  *
478  * @param tc the entry to delete edges from
479  * @param ansn the advertised neighbor set sequence number
480  * @return 1 if any destinations were deleted 0 if not
481  */
482 static int
483 olsr_delete_outdated_tc_edges(struct tc_entry *tc, olsr_u16_t ansn)
484 {
485   struct tc_edge_entry *tc_edge;
486   int retval = 0;
487
488 #if 0
489   OLSR_PRINTF(5, "TC: deleting MPRS\n");
490 #endif
491
492   OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
493     if (SEQNO_GREATER_THAN(ansn, tc_edge->T_seq)) {
494       /*
495        * Do not delete the edge now, just mark the edge as down.
496        * Downed edges will be ignored by the SPF computation.
497        * It could be that a TC message spans across multiple packets,
498        * which causes an edge delete followed by an edge add.
499        * If the edge gets refreshed in subsequent packets then we have
500        * avoided a two edge transistion.
501        * If the edge really went away then after the garbage collection
502        * timer has expired olsr_time_out_tc_set() will do the needful.
503        */
504       tc_edge->flags |= OLSR_TC_EDGE_DOWN;
505       olsr_set_tc_edge_timer(tc_edge, OLSR_TC_EDGE_GC_TIME);
506       retval = 1;
507     }
508   } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge);
509
510   return retval;
511 }
512
513 /*
514  * Determine if a etx change was more than 10%
515  * Need to know this for triggering a SPF calculation.
516  */
517 static olsr_bool
518 olsr_etx_significant_change(float etx1, float etx2)
519 {
520   float rel_lq;
521
522   if (etx1 == 0.0 || etx2 == 0.0) {
523     return OLSR_TRUE;
524   }
525
526   rel_lq = etx1 / etx2;
527
528   if (rel_lq > 1.1 || rel_lq < 0.9) {
529     return OLSR_TRUE;
530   }
531
532   return OLSR_FALSE;
533 }
534
535 /**
536  * Update an edge registered on an entry.
537  * Creates new edge-entries if not registered.
538  * Bases update on a received TC message
539  *
540  * @param entry the TC entry to check
541  * @pkt the TC edge entry in the packet
542  * @return 1 if entries are added 0 if not
543  */
544 static int
545 olsr_tc_update_edge(struct tc_entry *tc, unsigned int vtime_s, olsr_u16_t ansn,
546                     olsr_u8_t type, const unsigned char **curr)
547 {
548   struct tc_edge_entry *tc_edge;
549   double link_quality, neigh_link_quality;
550   union olsr_ip_addr neighbor;
551   int edge_change;
552
553   edge_change = 0;
554
555   /*
556    * Fetch the per-edge data
557    * LQ messages also contain LQ data.
558    */
559   pkt_get_ipaddress(curr, &neighbor);
560
561   if (type == LQ_TC_MESSAGE) {
562     pkt_get_lq(curr, &link_quality);
563     pkt_get_lq(curr, &neigh_link_quality);
564     pkt_ignore_u16(curr);
565   } else {
566     link_quality = 1.0;
567     neigh_link_quality = 1.0;
568   }
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     olsr_add_tc_edge_entry(tc, &neighbor, ansn, vtime_s,
584                            link_quality, neigh_link_quality);
585     edge_change = 1;
586
587   } else {
588
589     /*
590      * We know this edge - Update entry.
591      */
592     olsr_set_tc_edge_timer(tc_edge, vtime_s*1000);
593     tc_edge->T_seq = ansn;
594
595     /*
596      * Clear the (possibly set) down flag.
597      */
598     tc_edge->flags &= ~OLSR_TC_EDGE_DOWN;
599
600     /*
601      * Determine if the etx change is meaningful enough
602      * in order to trigger a SPF calculation.
603      */
604     if (olsr_etx_significant_change(tc_edge->link_quality,
605                                     neigh_link_quality)) {
606
607       if (tc->msg_hops <= olsr_cnf->lq_dlimit)
608         edge_change = 1;
609     }
610
611     /*
612      * Update link quality if configured. For hop-count only mode link quality
613      * remains at 1.0.
614      */
615     if (olsr_cnf->lq_level > 0) {
616       tc_edge->link_quality = neigh_link_quality;
617     }
618
619     if (olsr_etx_significant_change(tc_edge->inverse_link_quality,
620                                     link_quality)) {
621
622       if (tc->msg_hops <= olsr_cnf->lq_dlimit)
623         edge_change = 1;
624     }
625
626     /*
627      * Update inverse link quality if configured. For hop-count only mode
628      * inverse link quality remains at 1.0.
629      */
630     if (olsr_cnf->lq_level > 0) {
631       tc_edge->inverse_link_quality = link_quality;
632     }
633
634     /*
635      * Update the etx.
636      */
637     olsr_calc_tc_edge_entry_etx(tc_edge);
638
639 #if DEBUG
640     if (edge_change) {          
641       OLSR_PRINTF(1, "TC:   chg edge entry %s\n",
642                   olsr_tc_edge_to_string(tc_edge));
643     }
644 #endif
645
646   }
647
648   return edge_change;
649 }
650
651 /**
652  * Lookup an edge hanging off a TC entry.
653  *
654  * @param entry the entry to check
655  * @param dst_addr the destination address to check for
656  * @return a pointer to the tc_edge found - or NULL
657  */
658 struct tc_edge_entry *
659 olsr_lookup_tc_edge(struct tc_entry *tc, union olsr_ip_addr *edge_addr)
660 {
661   struct avl_node *edge_node;
662   
663 #if 0
664   OLSR_PRINTF(1, "TC: lookup dst\n");
665 #endif
666
667   edge_node = avl_find(&tc->edge_tree, edge_addr);
668
669   if (edge_node) {
670     return edge_node->data;
671   }
672
673   return NULL;
674 }
675
676 /**
677  * Walk the timers and time out entries.
678  *
679  * @return nada
680  */
681 void
682 olsr_time_out_tc_set(void)
683 {
684   struct tc_entry *tc;
685
686   OLSR_FOR_ALL_TC_ENTRIES(tc) {
687     struct tc_edge_entry *tc_edge;
688     OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
689       /*
690        * Delete outdated edges.
691        */
692       if(TIMED_OUT(tc_edge->T_time)) {
693         olsr_delete_tc_edge_entry(tc_edge);
694         changes_topology = OLSR_TRUE;
695       }
696     } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge);
697   } OLSR_FOR_ALL_TC_ENTRIES_END(tc)
698 }
699
700 /**
701  * Print the topology table to stdout
702  */
703 void
704 olsr_print_tc_table(void)
705 {
706 #ifndef NODEBUG
707   /* The whole function makes no sense without it. */
708   struct tc_entry *tc;
709   const int ipwidth = olsr_cnf->ip_version == AF_INET ? 15 : 30;
710
711   OLSR_PRINTF(1,
712               "\n--- %02d:%02d:%02d.%02d ------------------------------------------------- TOPOLOGY\n\n"
713               "%-*s %-*s %-5s  %-5s  %s\n",
714               nowtm->tm_hour, nowtm->tm_min, nowtm->tm_sec, (int)now.tv_usec / 10000,
715               ipwidth, "Source IP addr", ipwidth, "Dest IP addr", "LQ", "ILQ", "ETX");
716
717   OLSR_FOR_ALL_TC_ENTRIES(tc) {
718     struct tc_edge_entry *tc_edge;
719     OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
720       struct ipaddr_str addrbuf, dstaddrbuf;
721       OLSR_PRINTF(1, "%-*s %-*s  %5.3f  %5.3f  %.2f\n",
722                   ipwidth, olsr_ip_to_string(&addrbuf, &tc->addr),
723                   ipwidth, olsr_ip_to_string(&dstaddrbuf, &tc_edge->T_dest_addr),
724                   tc_edge->link_quality,
725                   tc_edge->inverse_link_quality,
726                   olsr_calc_tc_etx(tc_edge));
727     } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge);
728   } OLSR_FOR_ALL_TC_ENTRIES_END(tc);
729 #endif
730 }
731
732 float olsr_calc_tc_etx(const struct tc_edge_entry *tc_edge)
733 {
734   return tc_edge->link_quality < MIN_LINK_QUALITY ||
735          tc_edge->inverse_link_quality < MIN_LINK_QUALITY
736              ? 0.0
737              : 1.0 / (tc_edge->link_quality * tc_edge->inverse_link_quality);
738 }
739
740 /*
741  * Process an incoming TC or TC_LQ message.
742  *
743  * If the message is interesting enough, update our edges for it,
744  * trigger SPF and finally flood it to all our 2way neighbors.
745  *
746  * The order for extracting data off the message does matter, 
747  * as every call to pkt_get increases the packet offset and
748  * hence the spot we are looking at.
749  */
750 void
751 olsr_input_tc(union olsr_message *msg, struct interface *input_if,
752               union olsr_ip_addr *from_addr)
753 {
754 #ifndef NODEBUG 
755   struct ipaddr_str buf;
756 #endif
757   olsr_u16_t size, msg_seq, ansn;
758   olsr_u8_t type, ttl, msg_hops;
759   double vtime;
760   unsigned int vtime_s;
761   union olsr_ip_addr originator;
762   const unsigned char *limit, *curr;
763   struct tc_entry *tc;
764
765   curr = (void *)msg;
766   if (!msg) {
767     return;
768   }
769
770   /* We are only interested in TC message types. */
771   pkt_get_u8(&curr, &type);
772   if ((type != LQ_TC_MESSAGE) && (type != TC_MESSAGE)) {
773     return;
774   }
775
776   pkt_get_double(&curr, &vtime);
777   vtime_s = (unsigned int)vtime;
778   pkt_get_u16(&curr, &size);
779
780   pkt_get_ipaddress(&curr, &originator);
781
782   /* Copy header values */
783   pkt_get_u8(&curr, &ttl);
784   pkt_get_u8(&curr, &msg_hops);
785   pkt_get_u16(&curr, &msg_seq);
786   pkt_get_u16(&curr, &ansn);
787   pkt_ignore_u16(&curr);
788
789   tc = olsr_lookup_tc_entry(&originator);
790   
791   if (tc && 0 != tc->edge_tree.count) {
792     if (olsr_seq_inrange_high(
793           (int)tc->msg_seq - TC_SEQNO_WINDOW,
794           tc->msg_seq,
795           msg_seq) &&
796         olsr_seq_inrange_high(
797           (int)tc->ansn - TC_ANSN_WINDOW,
798           tc->ansn, ansn)) {
799
800       /*
801        * Ignore already seen seq/ansn values (small window for mesh memory)
802        */
803       if ((tc->msg_seq == msg_seq) || (tc->ignored++ < 32)) {
804         return;
805       }
806
807       OLSR_PRINTF(1, "Ignored to much LQTC's for %s, restarting\n",
808                   olsr_ip_to_string(&buf, &originator));
809
810     } else if (!olsr_seq_inrange_high(
811                  tc->msg_seq,
812                  (int)tc->msg_seq + TC_SEQNO_WINDOW * TC_SEQNO_WINDOW_MULT,
813                  msg_seq) ||
814                !olsr_seq_inrange_low(
815                  tc->ansn,
816                  (int)tc->ansn + TC_ANSN_WINDOW * TC_ANSN_WINDOW_MULT,
817                  ansn)) {
818
819       /*
820        * Only accept future seq/ansn values (large window for node reconnects).
821        * Restart in all other cases. Ignore a single stray message.
822        */
823       if (!tc->err_seq_valid) {
824         tc->err_seq = msg_seq;
825         tc->err_seq_valid = OLSR_TRUE;
826       }
827       if (tc->err_seq == msg_seq) {
828         return;
829       }
830
831       OLSR_PRINTF(2, "Detected node restart for %s\n",
832                   olsr_ip_to_string(&buf, &originator));
833     }
834   }
835
836   /*
837    * Generate a new tc_entry in the lsdb and store the sequence number.
838    */
839   if (!tc) {
840     tc = olsr_add_tc_entry(&originator);
841   }
842
843   /*
844    * Update the tc entry.
845    */
846   tc->msg_hops = msg_hops;
847   tc->msg_seq = msg_seq;
848   tc->ansn = ansn;
849   tc->ignored = 0;
850   tc->err_seq_valid = OLSR_FALSE;
851   
852   /*
853    * If the sender interface (NB: not originator) of this message
854    * is not in the symmetric 1-hop neighborhood of this node, the
855    * message MUST be discarded.
856    */
857   if (check_neighbor_link(from_addr) != SYM_LINK) {
858     OLSR_PRINTF(2, "Received TC from NON SYM neighbor %s\n",
859                 olsr_ip_to_string(&buf, from_addr));
860     return;
861   }
862
863   OLSR_PRINTF(1, "Processing TC from %s, seq 0x%04x\n",
864               olsr_ip_to_string(&buf, &originator), ansn);
865
866   /*
867    * Now walk the edge advertisements contained in the packet.
868    * Play some efficiency games here, like checking first
869    * if the edge exists in order to avoid address validation.
870    */
871   limit = (unsigned char *)msg + size;
872   while (curr < limit) {
873     if (olsr_tc_update_edge(tc, vtime_s, ansn, type, &curr)) {
874       changes_topology = OLSR_TRUE;
875     }
876   }
877
878   /*
879    * Do the edge garbage collection at the end in order
880    * to avoid malloc() churn.
881    */
882   if (olsr_delete_outdated_tc_edges(tc, ansn)) {
883     changes_topology = OLSR_TRUE;
884   }
885
886   /*
887    * Last, flood the message to our other neighbors.
888    */
889   olsr_forward_message(msg, &originator, msg_seq, input_if, from_addr);
890   return;
891 }
892
893 /*
894  * Local Variables:
895  * c-basic-offset: 2
896  * End:
897  */