db05ac9f18a629c9dde3ce828d34d82ead067f23
[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  * Delete a TC edge entry.
488  *
489  * @param tc the TC entry
490  * @param tc_edge the TC edge entry
491  */
492 void
493 olsr_delete_tc_edge_entry(struct tc_edge_entry *tc_edge)
494 {
495   struct tc_entry *tc;
496   struct tc_edge_entry *tc_edge_inv;
497
498 #ifdef DEBUG
499   OLSR_PRINTF(1, "TC: del edge entry %s\n", olsr_tc_edge_to_string(tc_edge));
500 #endif
501
502   tc = tc_edge->tc;
503   avl_delete(&tc->edge_tree, &tc_edge->edge_node);
504   olsr_unlock_tc_entry(tc);
505
506   /*
507    * Clear the backpointer of our inverse edge.
508    */
509   tc_edge_inv = tc_edge->edge_inv;
510   if (tc_edge_inv) {
511     tc_edge_inv->edge_inv = NULL;
512   }
513
514   olsr_cookie_free(tc_edge_mem_cookie, tc_edge);
515 }
516
517 /**
518  * Delete all destinations that have a lower ANSN.
519  *
520  * @param tc the entry to delete edges from
521  * @return TRUE if any destinations were deleted, FALSE if not
522  */
523 olsr_bool
524 olsr_delete_outdated_tc_edges(struct tc_entry *tc)
525 {
526   struct tc_edge_entry *tc_edge;
527   olsr_bool retval = OLSR_FALSE;
528
529 #if 0
530   OLSR_PRINTF(5, "TC: deleting outdated TC-edge entries\n");
531 #endif
532
533   OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
534     if (SEQNO_GREATER_THAN(tc->ansn, tc_edge->ansn)) {
535       olsr_delete_tc_edge_entry(tc_edge);
536       retval = OLSR_TRUE;
537     }
538   } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge);
539
540   return retval;
541 }
542
543 /**
544  * Delete all destinations that are inside the borders but
545  * not updated in the last tc.
546  *
547  * @param tc the entry to delete edges from
548  * @param ansn the advertised neighbor set sequence number
549  * @return 1 if any destinations were deleted 0 if not
550  */
551 static int
552 olsr_delete_revoked_tc_edges(struct tc_entry *tc, olsr_u16_t ansn,
553                               union olsr_ip_addr *lower_border,
554                               union olsr_ip_addr *upper_border)
555 {
556   struct tc_edge_entry *tc_edge;
557   int retval = 0;
558
559 #if 0
560   OLSR_PRINTF(5, "TC: deleting MPRS\n");
561 #endif
562
563   olsr_bool passedLowerBorder = OLSR_FALSE;
564   
565   OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
566     if (!passedLowerBorder) {
567       if (avl_comp_default(lower_border, &tc_edge->T_dest_addr) <= 0) {
568         passedLowerBorder = OLSR_TRUE;
569       }
570       else {
571         continue;
572       }
573     }
574     
575     if (passedLowerBorder) {
576       if (avl_comp_default(upper_border, &tc_edge->T_dest_addr) <= 0) {
577         break;
578       }
579     }
580
581     if (SEQNO_GREATER_THAN(ansn, tc_edge->ansn)) {
582       olsr_delete_tc_edge_entry(tc_edge);
583       retval = 1;
584     }
585   }OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge);
586
587   return retval;
588 }
589
590
591 /**
592  * Update an edge registered on an entry.
593  * Creates new edge-entries if not registered.
594  * Bases update on a received TC message
595  *
596  * @param entry the TC entry to check
597  * @pkt the TC edge entry in the packet
598  * @return 1 if entries are added 0 if not
599  */
600 static int
601 olsr_tc_update_edge(struct tc_entry *tc, olsr_u16_t ansn,
602                     const unsigned char **curr, union olsr_ip_addr *neighbor)
603 {
604   struct tc_edge_entry *tc_edge;
605   int edge_change;
606
607   edge_change = 0;
608
609   /*
610    * Fetch the per-edge data
611    */
612   pkt_get_ipaddress(curr, neighbor);
613
614   /* First check if we know this edge */
615   tc_edge = olsr_lookup_tc_edge(tc, neighbor);
616
617   if (!tc_edge) {
618
619     /*
620      * Yet unknown - create it.
621      * Check if the address is allowed.
622      */
623     if (!olsr_validate_address(neighbor)) {
624       return 0;
625     }
626
627     tc_edge = olsr_add_tc_edge_entry(tc, neighbor, ansn);
628     
629     olsr_deserialize_tc_lq_pair(curr, tc_edge);
630     edge_change = 1;
631
632   } else {
633
634     /*
635      * We know this edge - Update entry.
636      */
637     tc_edge->ansn = ansn;
638
639     /*
640      * Update link quality if configured.
641      */
642     if (olsr_cnf->lq_level > 0) {
643       olsr_deserialize_tc_lq_pair(curr, tc_edge);
644     }
645
646     /*
647      * Update the etx.
648      */
649     if (olsr_calc_tc_edge_entry_etx(tc_edge)) {
650       if (tc->msg_hops <= olsr_cnf->lq_dlimit) {
651         edge_change = 1;
652       }
653     }
654
655 #if DEBUG
656     if (edge_change) {
657       OLSR_PRINTF(1, "TC:   chg edge entry %s\n",
658           olsr_tc_edge_to_string(tc_edge));
659     }
660 #endif
661
662   }
663
664   return edge_change;
665 }
666
667 /**
668  * Lookup an edge hanging off a TC entry.
669  *
670  * @param entry the entry to check
671  * @param dst_addr the destination address to check for
672  * @return a pointer to the tc_edge found - or NULL
673  */
674 struct tc_edge_entry *
675 olsr_lookup_tc_edge(struct tc_entry *tc, union olsr_ip_addr *edge_addr)
676 {
677   struct avl_node *edge_node;
678
679 #if 0
680   OLSR_PRINTF(1, "TC: lookup dst\n");
681 #endif
682
683   edge_node = avl_find(&tc->edge_tree, edge_addr);
684
685   return (edge_node ? edge_tree2tc_edge(edge_node) : NULL);
686 }
687
688 /**
689  * Print the topology table to stdout
690  */
691 void
692 olsr_print_tc_table(void)
693 {
694 #ifndef NODEBUG
695   /* The whole function makes no sense without it. */
696   struct tc_entry *tc;
697   const int ipwidth = olsr_cnf->ip_version == AF_INET ? 15 : 30;
698
699   OLSR_PRINTF(1, "\n--- %s ------------------------------------------------- TOPOLOGY\n\n"
700       "%-*s %-*s %-14s  %s\n",
701       olsr_wallclock_string(),
702       ipwidth, "Source IP addr", ipwidth, "Dest IP addr", "      LQ      ", "ETX");
703
704   OLSR_FOR_ALL_TC_ENTRIES(tc) {
705     struct tc_edge_entry *tc_edge;
706     OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
707       struct ipaddr_str addrbuf, dstaddrbuf;
708       struct lqtextbuffer lqbuffer1, lqbuffer2;
709       
710       OLSR_PRINTF(1, "%-*s %-*s %-14s %s\n",
711                   ipwidth, olsr_ip_to_string(&addrbuf, &tc->addr),
712                   ipwidth, olsr_ip_to_string(&dstaddrbuf, &tc_edge->T_dest_addr),
713                   get_tc_edge_entry_text(tc_edge, &lqbuffer1),
714                   get_linkcost_text(tc_edge->cost, OLSR_FALSE, &lqbuffer2));
715       
716     } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge);
717   } OLSR_FOR_ALL_TC_ENTRIES_END(tc);
718 #endif
719 }
720
721 /*
722  * calculate the border IPs of a tc edge set according to the border flags
723  *
724  * @param lower border flag
725  * @param pointer to lower border ip
726  * @param upper border flag
727  * @param pointer to upper border ip
728  * @result 1 if lower/upper border ip have been set 
729  */
730 static int
731 olsr_calculate_tc_border(olsr_u8_t lower_border, union olsr_ip_addr *lower_border_ip,
732     olsr_u8_t upper_border, union olsr_ip_addr *upper_border_ip) {
733   if (lower_border == 0 && upper_border == 0) {
734     return 0;
735   } 
736   if (lower_border == 0xff) {
737     memset(&lower_border_ip, 0, sizeof(lower_border_ip));
738   } else {
739     int i;
740     
741     lower_border--;
742     for (i=0; i<lower_border/8; i++) {
743       lower_border_ip->v6.in6_u.u6_addr8[olsr_cnf->ipsize - i - 1] = 0;
744     }
745     lower_border_ip->v6.in6_u.u6_addr8[olsr_cnf->ipsize - lower_border/8 - 1] &= (0xff << (lower_border & 7));
746     lower_border_ip->v6.in6_u.u6_addr8[olsr_cnf->ipsize - lower_border/8 - 1] |= (1 << (lower_border & 7));
747   }
748
749   if (upper_border == 0xff) {
750     memset(&upper_border_ip, 0xff, sizeof(upper_border_ip));
751   } else {
752     int i;
753
754     upper_border--;
755
756     for (i=0; i<upper_border/8; i++) {
757       upper_border_ip->v6.in6_u.u6_addr8[olsr_cnf->ipsize - i - 1] = 0;
758     }
759     upper_border_ip->v6.in6_u.u6_addr8[olsr_cnf->ipsize - upper_border/8 - 1] &= (0xff << (upper_border & 7));
760     upper_border_ip->v6.in6_u.u6_addr8[olsr_cnf->ipsize - upper_border/8 - 1] |= (1 << (upper_border & 7));
761   }
762   return 1;
763 }
764
765 /*
766  * Process an incoming TC or TC_LQ message.
767  *
768  * If the message is interesting enough, update our edges for it,
769  * trigger SPF and finally flood it to all our 2way neighbors.
770  *
771  * The order for extracting data off the message does matter, 
772  * as every call to pkt_get increases the packet offset and
773  * hence the spot we are looking at.
774  */
775 void
776 olsr_input_tc(union olsr_message *msg,
777               struct interface *input_if __attribute__((unused)),
778               union olsr_ip_addr *from_addr)
779 {
780 #ifndef NODEBUG 
781   struct ipaddr_str buf;
782 #endif
783   olsr_u16_t size, msg_seq, ansn;
784   olsr_u8_t type, ttl, msg_hops, lower_border, upper_border;
785   double vtime;
786   unsigned int vtime_s;
787   union olsr_ip_addr originator;
788   const unsigned char *limit, *curr;
789   struct tc_entry *tc;
790
791   union olsr_ip_addr lower_border_ip, upper_border_ip;
792   int borderSet = 0;
793
794   curr = (void *)msg;
795   if (!msg) {
796     return;
797   }
798
799   /* We are only interested in TC message types. */
800   pkt_get_u8(&curr, &type);
801   if ((type != LQ_TC_MESSAGE) && (type != TC_MESSAGE)) {
802     return;
803   }
804
805   pkt_get_double(&curr, &vtime);
806   vtime_s = (unsigned int)vtime;
807   pkt_get_u16(&curr, &size);
808
809   pkt_get_ipaddress(&curr, &originator);
810
811   /* Copy header values */
812   pkt_get_u8(&curr, &ttl);
813   pkt_get_u8(&curr, &msg_hops);
814   pkt_get_u16(&curr, &msg_seq);
815   pkt_get_u16(&curr, &ansn);
816
817   /* get borders */
818   pkt_get_u8(&curr, &lower_border);
819   pkt_get_u8(&curr, &upper_border);
820
821   tc = olsr_lookup_tc_entry(&originator);
822
823   if (tc && 0 != tc->edge_tree.count) {
824     if (olsr_seq_inrange_high(
825           (int)tc->msg_seq - TC_SEQNO_WINDOW,
826           tc->msg_seq,
827           msg_seq) &&
828         olsr_seq_inrange_high(
829           (int)tc->ansn - TC_ANSN_WINDOW,
830           tc->ansn, ansn)) {
831
832       /*
833        * Ignore already seen seq/ansn values (small window for mesh memory)
834        */
835       if ((tc->msg_seq == msg_seq) || (tc->ignored++ < 32)) {
836         return;
837       }
838
839       OLSR_PRINTF(1, "Ignored to much LQTC's for %s, restarting\n",
840           olsr_ip_to_string(&buf, &originator));
841
842     } else if (!olsr_seq_inrange_high(tc->msg_seq, (int)tc->msg_seq + TC_SEQNO_WINDOW * TC_SEQNO_WINDOW_MULT, msg_seq)
843         || !olsr_seq_inrange_low(tc->ansn, (int)tc->ansn + TC_ANSN_WINDOW * TC_ANSN_WINDOW_MULT, ansn)) {
844
845       /*
846        * Only accept future seq/ansn values (large window for node reconnects).
847        * Restart in all other cases. Ignore a single stray message.
848        */
849       if (!tc->err_seq_valid) {
850         tc->err_seq = msg_seq;
851         tc->err_seq_valid = OLSR_TRUE;
852       }
853       if (tc->err_seq == msg_seq) {
854         return;
855       }
856
857       OLSR_PRINTF(2, "Detected node restart for %s\n",
858           olsr_ip_to_string(&buf, &originator));
859     }
860   }
861
862   /*
863    * Generate a new tc_entry in the lsdb and store the sequence number.
864    */
865   if (!tc) {
866     tc = olsr_add_tc_entry(&originator);
867   }
868
869   /*
870    * Update the tc entry.
871    */
872   tc->msg_hops = msg_hops;
873   tc->msg_seq = msg_seq;
874   tc->ansn = ansn;
875   tc->ignored = 0;
876   tc->err_seq_valid = OLSR_FALSE;
877
878   /*
879    * If the sender interface (NB: not originator) of this message
880    * is not in the symmetric 1-hop neighborhood of this node, the
881    * message MUST be discarded.
882    */
883   if (check_neighbor_link(from_addr) != SYM_LINK) {
884     OLSR_PRINTF(2, "Received TC from NON SYM neighbor %s\n",
885         olsr_ip_to_string(&buf, from_addr));
886     return;
887   }
888
889   OLSR_PRINTF(1, "Processing TC from %s, seq 0x%04x\n",
890       olsr_ip_to_string(&buf, &originator), ansn);
891
892   /*
893    * Now walk the edge advertisements contained in the packet.
894    */
895
896   limit = (unsigned char *)msg + size;
897   borderSet = 0;
898   while (curr < limit) {
899     if (olsr_tc_update_edge(tc, ansn, &curr, &upper_border_ip)) {
900       changes_topology = OLSR_TRUE;
901     }
902
903     if (!borderSet) {
904       borderSet = 1;
905       memcpy(&lower_border_ip, &upper_border_ip, sizeof(lower_border_ip));
906     }
907   }
908
909   /* calculate real border ips */
910   if (borderSet) {
911     borderSet = olsr_calculate_tc_border(lower_border, &lower_border_ip, upper_border, &upper_border_ip);
912   }
913   
914   /*
915    * Set or change the expiration timer accordingly.
916    */
917   olsr_set_timer(&tc->validity_timer, vtime_s * MSEC_PER_SEC,
918                  OLSR_TC_VTIME_JITTER, OLSR_TIMER_ONESHOT,
919                  &olsr_expire_tc_entry, tc, tc_validity_timer_cookie->ci_id);
920
921   if (borderSet) {
922     /*
923      * delete all old tc edges within borders
924      */
925     olsr_delete_revoked_tc_edges(tc, ansn, &lower_border_ip, &upper_border_ip);
926   }
927   else {
928     /*
929      * Kick the the edge garbage collection timer. In the meantime hopefully
930      * all edges belonging to a multipart neighbor set will arrive.
931      */
932     olsr_set_timer(&tc->edge_gc_timer, OLSR_TC_EDGE_GC_TIME,
933                  OLSR_TC_EDGE_GC_JITTER, OLSR_TIMER_ONESHOT,
934                  &olsr_expire_tc_edge_gc, tc, tc_edge_gc_timer_cookie->ci_id);
935   }
936   
937   /*
938    * Last, flood the message to our other neighbors.
939    */
940   olsr_forward_message(msg, from_addr);
941   return;
942 }
943
944 /*
945  * Local Variables:
946  * c-basic-offset: 2
947  * End:
948  */