c15cc1a8747632a3ac86939f13ce56ebe57907de
[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   avl_init(&tc_tree, avl_comp_default);
173
174   /*
175    * Add a TC entry for ourselves.
176    */
177   tc_myself = olsr_add_tc_entry(&olsr_cnf->main_addr);
178 }
179
180 /**
181  * The main ip address has changed.
182  * Do the needful.
183  */
184 void
185 olsr_change_myself_tc(void)
186 {
187   struct tc_edge_entry *tc_edge;
188
189   if (tc_myself) {
190
191     /*
192      * Check if there was a change.
193      */
194     if (ipequal(&tc_myself->addr, &olsr_cnf->main_addr)) {
195       return;
196     }
197
198     /*
199      * Flush all edges and our own tc_entry.
200      */
201     OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc_myself, tc_edge) {
202       olsr_delete_tc_edge_entry(tc_edge);
203     } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc_myself, tc_edge);
204     olsr_delete_tc_entry(tc_myself);
205   }
206
207   /*
208    * The old entry for ourselves is gone, generate a new one and trigger SPF.
209    */
210   tc_myself = olsr_add_tc_entry(&olsr_cnf->main_addr);
211   changes_topology = OLSR_TRUE;
212 }
213
214 /**
215  * Delete a TC entry.
216  *
217  * @param entry the TC entry to delete
218  *
219  */
220 void
221 olsr_delete_tc_entry(struct tc_entry *tc)
222 {
223 #if 0
224   struct ipaddr_str buf;
225   OLSR_PRINTF(1, "TC: del entry %s\n", olsr_ip_to_string(&buf, &tc->addr));
226 #endif
227
228   /*
229    * Delete the rt_path for ourselves.
230    */
231   olsr_delete_routing_table(&tc->addr, olsr_cnf->maxplen, &tc->addr);
232
233   /* The edgetree and prefix tree must be empty before */
234   assert(!tc->edge_tree.count && !tc->prefix_tree.count);
235
236   avl_delete(&tc_tree, &tc->vertex_node);
237   free(tc);
238 }
239
240 /**
241  * Look up a entry from the TC tree based on address
242  *
243  * @param adr the address to look for
244  * @return the entry found or NULL
245  */
246 struct tc_entry *
247 olsr_lookup_tc_entry(union olsr_ip_addr *adr)
248 {
249   struct avl_node *node;
250
251 #if 0
252   OLSR_PRINTF(1, "TC: lookup entry\n");
253 #endif
254
255   node = avl_find(&tc_tree, adr);
256
257   if (node) {
258     return node->data;
259   }
260
261   return NULL;
262 }
263
264 /*
265  * Lookup a tc entry. Creates one if it does not exist yet.
266  */
267 struct tc_entry *
268 olsr_locate_tc_entry(union olsr_ip_addr *adr)
269 {
270   struct tc_entry *tc;
271
272   if (!(tc = olsr_lookup_tc_entry(adr))) {
273     return olsr_add_tc_entry(adr);
274   }
275   return tc;
276 }
277
278 /**
279  * Format tc_edge contents into a buffer.
280  */
281 char *
282 olsr_tc_edge_to_string(struct tc_edge_entry *tc_edge)
283 {
284   static char buf[128];
285   struct ipaddr_str addrbuf, dstbuf;
286   struct tc_entry *tc = tc_edge->tc;
287
288   snprintf(buf, sizeof(buf),
289            "%s > %s, lq %s, inv-lq %s, etx %s",
290            olsr_ip_to_string(&addrbuf, &tc->addr),
291            olsr_ip_to_string(&dstbuf, &tc_edge->T_dest_addr),
292            fpmtoa(tc_edge->link_quality),
293            fpmtoa(tc_edge->inverse_link_quality),
294            etxtoa(tc_edge->etx));
295
296   return buf;
297 }
298
299 /**
300  * Wrapper for the timer callback.
301  */
302 static void
303 olsr_expire_tc_edge_entry(void *context)
304 {
305   struct tc_edge_entry *tc_edge;
306
307   tc_edge = (struct tc_edge_entry *)context;
308   tc_edge->edge_timer = NULL;
309
310   olsr_delete_tc_edge_entry(tc_edge);
311 }
312
313 /**
314  * Set the TC edge expiration timer.
315  *
316  * all timer setting shall be done using this function.
317  * The timer param is a relative timer expressed in milliseconds.
318  */
319 void
320 olsr_set_tc_edge_timer(struct tc_edge_entry *tc_edge, unsigned int rel_timer)
321 {
322   olsr_set_timer(&tc_edge->edge_timer, rel_timer, OLSR_TC_EDGE_JITTER,
323                  OLSR_TIMER_ONESHOT, &olsr_expire_tc_edge_entry, tc_edge, 0);
324 }
325
326 /*
327  * If the edge does not have a minimum acceptable link quality
328  * set the etx cost to infinity such that it gets ignored during
329  * SPF calculation.
330  */
331 void
332 olsr_calc_tc_edge_entry_etx(struct tc_edge_entry *tc_edge)
333 {
334
335   /*
336    * Some sanity check before recalculating the etx.
337    */
338   if (olsr_cnf->lq_level < 1) {
339     return;
340   }
341
342   if (tc_edge->link_quality < MIN_LINK_QUALITY ||
343       tc_edge->inverse_link_quality < MIN_LINK_QUALITY) {
344     tc_edge->etx = INFINITE_ETX;
345   } else {
346 #ifdef USE_FPM
347     tc_edge->etx = fpmdiv(itofpm(1), fpmmul(tc_edge->link_quality, tc_edge->inverse_link_quality));
348 #else
349     tc_edge->etx = 1.0 / (tc_edge->link_quality * tc_edge->inverse_link_quality);
350 #endif
351   }
352 }
353
354 /**
355  * Add a new tc_edge_entry to the tc_edge_tree
356  *
357  * @param (last)adr address of the entry
358  * @return a pointer to the created entry
359  */
360 struct tc_edge_entry *
361 olsr_add_tc_edge_entry(struct tc_entry *tc, union olsr_ip_addr *addr,
362                        olsr_u16_t ansn, unsigned int vtime,
363 #ifdef USE_FPM
364                        fpm link_quality, fpm neigh_link_quality
365 #else
366                        float link_quality, float neigh_link_quality
367 #endif
368                        )
369 {
370 #if !defined(NODEBUG) && defined(DEBUG)
371   struct ipaddr_str buf;
372 #endif
373   struct tc_entry *tc_neighbor;
374   struct tc_edge_entry *tc_edge, *tc_edge_inv;
375
376   tc_edge = olsr_malloc(sizeof(struct tc_edge_entry), "add TC edge");
377   if (!tc_edge) {
378     return NULL;
379   }
380   memset(tc_edge, 0, sizeof(struct tc_edge_entry));
381
382   /* Fill entry */
383   tc_edge->T_dest_addr = *addr;
384   olsr_set_tc_edge_timer(tc_edge, vtime*1000);
385   tc_edge->T_seq = ansn;
386   tc_edge->edge_node.data = tc_edge;
387   tc_edge->edge_node.key = &tc_edge->T_dest_addr;
388
389   if (olsr_cnf->lq_level > 0) {
390     tc_edge->link_quality = neigh_link_quality;
391     tc_edge->inverse_link_quality = link_quality;
392   } else {
393
394     /*
395      * Set the link quality to 1.0 to mimikry a hopcount alike
396      * behaviour for nodes not supporting the LQ extensions.
397      */
398 #ifdef USE_FPM
399     tc_edge->link_quality = itofpm(1);
400     tc_edge->inverse_link_quality = itofpm(1);
401 #else
402     tc_edge->link_quality = 1.0;
403     tc_edge->inverse_link_quality = 1.0;
404 #endif
405   }
406
407   /*
408    * Insert into the edge tree.
409    */
410   avl_insert(&tc->edge_tree, &tc_edge->edge_node, AVL_DUP_NO);
411
412   /*
413    * Connect backpointer.
414    */
415   tc_edge->tc = tc;
416
417   /*
418    * Check if the neighboring router and the inverse edge is in the lsdb.
419    * Create short cuts to the inverse edge for faster SPF execution.
420    */
421   tc_neighbor = olsr_lookup_tc_entry(&tc_edge->T_dest_addr);
422   if (tc_neighbor) {
423 #ifdef DEBUG
424     OLSR_PRINTF(1, "TC:   found neighbor tc_entry %s\n",
425                 olsr_ip_to_string(&buf, &tc_neighbor->addr));
426 #endif
427
428     tc_edge_inv = olsr_lookup_tc_edge(tc_neighbor, &tc->addr);
429     if (tc_edge_inv) {
430 #ifdef DEBUG
431       OLSR_PRINTF(1, "TC:   found inverse edge for %s\n",
432                   olsr_ip_to_string(&buf, &tc_edge_inv->T_dest_addr));
433 #endif
434
435       /*
436        * Connect the edges mutually.
437        */
438       tc_edge_inv->edge_inv = tc_edge;
439       tc_edge->edge_inv = tc_edge_inv;
440
441     }
442   }
443
444   /*
445    * Update the etx.
446    */
447   olsr_calc_tc_edge_entry_etx(tc_edge);
448
449 #ifdef DEBUG
450   OLSR_PRINTF(1, "TC: add edge entry %s\n", olsr_tc_edge_to_string(tc_edge));
451 #endif
452
453   return tc_edge;
454 }
455
456
457 /**
458  * Delete a TC edge entry.
459  *
460  * @param tc the TC entry
461  * @param tc_edge the TC edge entry
462  */
463 void
464 olsr_delete_tc_edge_entry(struct tc_edge_entry *tc_edge)
465 {
466   struct tc_entry *tc;
467   struct tc_edge_entry *tc_edge_inv;
468
469 #ifdef DEBUG
470   OLSR_PRINTF(1, "TC: del edge entry %s\n", olsr_tc_edge_to_string(tc_edge));
471 #endif
472
473   tc = tc_edge->tc;
474   avl_delete(&tc->edge_tree, &tc_edge->edge_node);
475
476   /*
477    * Kill running timers.
478    */
479   olsr_stop_timer(tc_edge->edge_timer);
480   tc_edge->edge_timer = NULL;
481
482   /*
483    * Clear the backpointer of our inverse edge.
484    */
485   tc_edge_inv = tc_edge->edge_inv;
486   if (tc_edge_inv) {
487     tc_edge_inv->edge_inv = NULL;
488   }
489
490   /*
491    * Delete the tc_entry if the last edge and last prefix is gone.
492    */
493   if (!tc_edge->tc->edge_tree.count &&
494       !tc_edge->tc->prefix_tree.count) {
495
496     /*
497      * Only remove remote tc entries.
498      */
499     if (tc_edge->tc != tc_myself) {
500       olsr_delete_tc_entry(tc_edge->tc);
501     }
502   }
503
504   free(tc_edge);
505 }
506
507
508 /**
509  * Delete all destinations that have a lower ANSN.
510  *
511  * @param tc the entry to delete edges from
512  * @param ansn the advertised neighbor set sequence number
513  * @return 1 if any destinations were deleted 0 if not
514  */
515 static int
516 olsr_delete_outdated_tc_edges(struct tc_entry *tc, olsr_u16_t ansn)
517 {
518   struct tc_edge_entry *tc_edge;
519   int retval = 0;
520
521 #if 0
522   OLSR_PRINTF(5, "TC: deleting MPRS\n");
523 #endif
524
525   OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
526     if (SEQNO_GREATER_THAN(ansn, tc_edge->T_seq)) {
527       /*
528        * Do not delete the edge now, just mark the edge as down.
529        * Downed edges will be ignored by the SPF computation.
530        * It could be that a TC message spans across multiple packets,
531        * which causes an edge delete followed by an edge add.
532        * If the edge gets refreshed in subsequent packets then we have
533        * avoided a two edge transistion.
534        * If the edge really went away then after the garbage collection
535        * timer has expired olsr_time_out_tc_set() will do the needful.
536        */
537       tc_edge->flags |= OLSR_TC_EDGE_DOWN;
538       olsr_set_tc_edge_timer(tc_edge, OLSR_TC_EDGE_GC_TIME);
539       retval = 1;
540     }
541   } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge);
542
543   return retval;
544 }
545
546 /*
547  * Determine if a etx change was more than 10%
548  * Need to know this for triggering a SPF calculation.
549  */
550 #ifdef USE_FPM
551 static olsr_bool
552 olsr_etx_significant_change(fpm etx1, fpm etx2)
553 {
554   fpm rel_lq;
555
556   if (etx1 == ZERO_ETX || etx2 == ZERO_ETX) {
557     return OLSR_TRUE;
558   }
559
560   rel_lq = fpmdiv(etx1, etx2);
561
562   if (rel_lq > CEIL_LQDIFF || rel_lq < FLOOR_LQDIFF) {
563     return OLSR_TRUE;
564   }
565
566   return OLSR_FALSE;
567 }
568 #else
569 static olsr_bool
570 olsr_etx_significant_change(float etx1, float etx2)
571 {
572   float rel_lq;
573
574   if (etx1 == ZERO_ETX || etx2 == ZERO_ETX) {
575     return OLSR_TRUE;
576   }
577
578   rel_lq = etx1 / etx2;
579
580   if (rel_lq > CEIL_LQDIFF || rel_lq < FLOOR_LQDIFF) {
581     return OLSR_TRUE;
582   }
583
584   return OLSR_FALSE;
585 }
586 #endif
587
588 /**
589  * Update an edge registered on an entry.
590  * Creates new edge-entries if not registered.
591  * Bases update on a received TC message
592  *
593  * @param entry the TC entry to check
594  * @pkt the TC edge entry in the packet
595  * @return 1 if entries are added 0 if not
596  */
597 static int
598 olsr_tc_update_edge(struct tc_entry *tc, unsigned int vtime_s, olsr_u16_t ansn,
599                     olsr_u8_t type, const unsigned char **curr)
600 {
601   struct tc_edge_entry *tc_edge;
602 #ifdef USE_FPM
603   fpm link_quality, neigh_link_quality;
604 #else
605   double link_quality, neigh_link_quality;
606 #endif
607   union olsr_ip_addr neighbor;
608   int edge_change;
609
610   edge_change = 0;
611
612   /*
613    * Fetch the per-edge data
614    * LQ messages also contain LQ data.
615    */
616   pkt_get_ipaddress(curr, &neighbor);
617
618   if (type == LQ_TC_MESSAGE) {
619     pkt_get_lq(curr, &link_quality);
620     pkt_get_lq(curr, &neigh_link_quality);
621     pkt_ignore_u16(curr);
622   } else {
623 #ifdef USE_FPM
624     link_quality = itofpm(1);
625     neigh_link_quality = itofpm(1);
626 #else
627     link_quality = 1.0;
628     neigh_link_quality = 1.0;
629 #endif
630   }
631
632   /* First check if we know this edge */
633   tc_edge = olsr_lookup_tc_edge(tc, &neighbor);
634
635   if(!tc_edge) {
636       
637     /*
638      * Yet unknown - create it.
639      * Check if the address is allowed.
640      */
641     if (!olsr_validate_address(&neighbor)) {
642       return 0;
643     }
644
645     olsr_add_tc_edge_entry(tc, &neighbor, ansn, vtime_s,
646                            link_quality, neigh_link_quality);
647     edge_change = 1;
648
649   } else {
650
651     /*
652      * We know this edge - Update entry.
653      */
654     olsr_set_tc_edge_timer(tc_edge, vtime_s*1000);
655     tc_edge->T_seq = ansn;
656
657     /*
658      * Clear the (possibly set) down flag.
659      */
660     tc_edge->flags &= ~OLSR_TC_EDGE_DOWN;
661
662     /*
663      * Determine if the etx change is meaningful enough
664      * in order to trigger a SPF calculation.
665      */
666     if (olsr_etx_significant_change(tc_edge->link_quality,
667                                     neigh_link_quality)) {
668
669       if (tc->msg_hops <= olsr_cnf->lq_dlimit)
670         edge_change = 1;
671     }
672
673     /*
674      * Update link quality if configured. For hop-count only mode link quality
675      * remains at 1.0.
676      */
677     if (olsr_cnf->lq_level > 0) {
678       tc_edge->link_quality = neigh_link_quality;
679     }
680
681     if (olsr_etx_significant_change(tc_edge->inverse_link_quality,
682                                     link_quality)) {
683
684       if (tc->msg_hops <= olsr_cnf->lq_dlimit)
685         edge_change = 1;
686     }
687
688     /*
689      * Update inverse link quality if configured. For hop-count only mode
690      * inverse link quality remains at 1.0.
691      */
692     if (olsr_cnf->lq_level > 0) {
693       tc_edge->inverse_link_quality = link_quality;
694     }
695
696     /*
697      * Update the etx.
698      */
699     olsr_calc_tc_edge_entry_etx(tc_edge);
700
701 #if DEBUG
702     if (edge_change) {          
703       OLSR_PRINTF(1, "TC:   chg edge entry %s\n",
704                   olsr_tc_edge_to_string(tc_edge));
705     }
706 #endif
707
708   }
709
710   return edge_change;
711 }
712
713 /**
714  * Lookup an edge hanging off a TC entry.
715  *
716  * @param entry the entry to check
717  * @param dst_addr the destination address to check for
718  * @return a pointer to the tc_edge found - or NULL
719  */
720 struct tc_edge_entry *
721 olsr_lookup_tc_edge(struct tc_entry *tc, union olsr_ip_addr *edge_addr)
722 {
723   struct avl_node *edge_node;
724   
725 #if 0
726   OLSR_PRINTF(1, "TC: lookup dst\n");
727 #endif
728
729   edge_node = avl_find(&tc->edge_tree, edge_addr);
730
731   if (edge_node) {
732     return edge_node->data;
733   }
734
735   return NULL;
736 }
737
738 /**
739  * Print the topology table to stdout
740  */
741 void
742 olsr_print_tc_table(void)
743 {
744 #ifndef NODEBUG
745   /* The whole function makes no sense without it. */
746   struct tc_entry *tc;
747   const int ipwidth = olsr_cnf->ip_version == AF_INET ? 15 : 30;
748
749   OLSR_PRINTF(1, "\n--- %s ------------------------------------------------- TOPOLOGY\n\n"
750               "%-*s %-*s %-5s  %-5s  %s %s\n",
751               olsr_wallclock_string(),
752               ipwidth, "Source IP addr", ipwidth, "Dest IP addr", "LQ", "ILQ", "ETX", "UP");
753
754   OLSR_FOR_ALL_TC_ENTRIES(tc) {
755     struct tc_edge_entry *tc_edge;
756     OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
757       struct ipaddr_str addrbuf, dstaddrbuf;
758       OLSR_PRINTF(1, "%-*s %-*s  %s  %s  %s  %s\n",
759                   ipwidth, olsr_ip_to_string(&addrbuf, &tc->addr),
760                   ipwidth, olsr_ip_to_string(&dstaddrbuf, &tc_edge->T_dest_addr),
761                   fpmtoa(tc_edge->link_quality),
762                   fpmtoa(tc_edge->inverse_link_quality),
763                   etxtoa(olsr_calc_tc_etx(tc_edge)),
764                   tc_edge->flags & OLSR_TC_EDGE_DOWN ? "DOWN" : "UP");
765     } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge);
766   } OLSR_FOR_ALL_TC_ENTRIES_END(tc);
767 #endif
768 }
769
770 #ifdef USE_FPM
771 fpm
772 #else
773 float
774 #endif
775 olsr_calc_tc_etx(const struct tc_edge_entry *tc_edge)
776 {
777   return tc_edge->link_quality < MIN_LINK_QUALITY ||
778          tc_edge->inverse_link_quality < MIN_LINK_QUALITY
779 #ifdef USE_FPM
780              ? itofpm(0)
781              : fpmdiv(itofpm(1), fpmmul(tc_edge->link_quality, tc_edge->inverse_link_quality));
782 #else
783              ? 0.0
784              : 1.0 / (tc_edge->link_quality * tc_edge->inverse_link_quality);
785 #endif
786 }
787
788 /*
789  * Process an incoming TC or TC_LQ message.
790  *
791  * If the message is interesting enough, update our edges for it,
792  * trigger SPF and finally flood it to all our 2way neighbors.
793  *
794  * The order for extracting data off the message does matter, 
795  * as every call to pkt_get increases the packet offset and
796  * hence the spot we are looking at.
797  */
798 void
799 olsr_input_tc(union olsr_message *msg, struct interface *input_if,
800               union olsr_ip_addr *from_addr)
801 {
802 #ifndef NODEBUG 
803   struct ipaddr_str buf;
804 #endif
805   olsr_u16_t size, msg_seq, ansn;
806   olsr_u8_t type, ttl, msg_hops;
807   double vtime;
808   unsigned int vtime_s;
809   union olsr_ip_addr originator;
810   const unsigned char *limit, *curr;
811   struct tc_entry *tc;
812
813   curr = (void *)msg;
814   if (!msg) {
815     return;
816   }
817
818   /* We are only interested in TC message types. */
819   pkt_get_u8(&curr, &type);
820   if ((type != LQ_TC_MESSAGE) && (type != TC_MESSAGE)) {
821     return;
822   }
823
824   pkt_get_double(&curr, &vtime);
825   vtime_s = (unsigned int)vtime;
826   pkt_get_u16(&curr, &size);
827
828   pkt_get_ipaddress(&curr, &originator);
829
830   /* Copy header values */
831   pkt_get_u8(&curr, &ttl);
832   pkt_get_u8(&curr, &msg_hops);
833   pkt_get_u16(&curr, &msg_seq);
834   pkt_get_u16(&curr, &ansn);
835   pkt_ignore_u16(&curr);
836
837   tc = olsr_lookup_tc_entry(&originator);
838   
839   if (tc && 0 != tc->edge_tree.count) {
840     if (olsr_seq_inrange_high(
841           (int)tc->msg_seq - TC_SEQNO_WINDOW,
842           tc->msg_seq,
843           msg_seq) &&
844         olsr_seq_inrange_high(
845           (int)tc->ansn - TC_ANSN_WINDOW,
846           tc->ansn, ansn)) {
847
848       /*
849        * Ignore already seen seq/ansn values (small window for mesh memory)
850        */
851       if ((tc->msg_seq == msg_seq) || (tc->ignored++ < 32)) {
852         return;
853       }
854
855       OLSR_PRINTF(1, "Ignored to much LQTC's for %s, restarting\n",
856                   olsr_ip_to_string(&buf, &originator));
857
858     } else if (!olsr_seq_inrange_high(
859                  tc->msg_seq,
860                  (int)tc->msg_seq + TC_SEQNO_WINDOW * TC_SEQNO_WINDOW_MULT,
861                  msg_seq) ||
862                !olsr_seq_inrange_low(
863                  tc->ansn,
864                  (int)tc->ansn + TC_ANSN_WINDOW * TC_ANSN_WINDOW_MULT,
865                  ansn)) {
866
867       /*
868        * Only accept future seq/ansn values (large window for node reconnects).
869        * Restart in all other cases. Ignore a single stray message.
870        */
871       if (!tc->err_seq_valid) {
872         tc->err_seq = msg_seq;
873         tc->err_seq_valid = OLSR_TRUE;
874       }
875       if (tc->err_seq == msg_seq) {
876         return;
877       }
878
879       OLSR_PRINTF(2, "Detected node restart for %s\n",
880                   olsr_ip_to_string(&buf, &originator));
881     }
882   }
883
884   /*
885    * Generate a new tc_entry in the lsdb and store the sequence number.
886    */
887   if (!tc) {
888     tc = olsr_add_tc_entry(&originator);
889   }
890
891   /*
892    * Update the tc entry.
893    */
894   tc->msg_hops = msg_hops;
895   tc->msg_seq = msg_seq;
896   tc->ansn = ansn;
897   tc->ignored = 0;
898   tc->err_seq_valid = OLSR_FALSE;
899   
900   /*
901    * If the sender interface (NB: not originator) of this message
902    * is not in the symmetric 1-hop neighborhood of this node, the
903    * message MUST be discarded.
904    */
905   if (check_neighbor_link(from_addr) != SYM_LINK) {
906     OLSR_PRINTF(2, "Received TC from NON SYM neighbor %s\n",
907                 olsr_ip_to_string(&buf, from_addr));
908     return;
909   }
910
911   OLSR_PRINTF(1, "Processing TC from %s, seq 0x%04x\n",
912               olsr_ip_to_string(&buf, &originator), ansn);
913
914   /*
915    * Now walk the edge advertisements contained in the packet.
916    * Play some efficiency games here, like checking first
917    * if the edge exists in order to avoid address validation.
918    */
919   limit = (unsigned char *)msg + size;
920   while (curr < limit) {
921     if (olsr_tc_update_edge(tc, vtime_s, ansn, type, &curr)) {
922       changes_topology = OLSR_TRUE;
923     }
924   }
925
926   /*
927    * Do the edge garbage collection at the end in order
928    * to avoid malloc() churn.
929    */
930   if (olsr_delete_outdated_tc_edges(tc, ansn)) {
931     changes_topology = OLSR_TRUE;
932   }
933
934   /*
935    * Last, flood the message to our other neighbors.
936    */
937   olsr_forward_message(msg, &originator, msg_seq, input_if, from_addr);
938   return;
939 }
940
941 /*
942  * Local Variables:
943  * c-basic-offset: 2
944  * End:
945  */