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