comment out freebsd build breaks
[olsrd.git] / src / tc_set.c
1
2 /*
3  * The olsr.org Optimized Link-State Routing daemon(olsrd)
4  * Copyright (c) 2004, Andreas T√łnnesen(andreto@olsr.org)
5  * LSDB rewrite (c) 2007, Hannes Gredler (hannes@gredler.at)
6  * All rights reserved.
7  *
8  * Redistribution and use in source and binary forms, with or without 
9  * modification, are permitted provided that the following conditions 
10  * are met:
11  *
12  * * Redistributions of source code must retain the above copyright 
13  *   notice, this list of conditions and the following disclaimer.
14  * * Redistributions in binary form must reproduce the above copyright 
15  *   notice, this list of conditions and the following disclaimer in 
16  *   the documentation and/or other materials provided with the 
17  *   distribution.
18  * * Neither the name of olsr.org, olsrd nor the names of its 
19  *   contributors may be used to endorse or promote products derived 
20  *   from this software without specific prior written permission.
21  *
22  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 
23  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 
24  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS 
25  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE 
26  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, 
27  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, 
28  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 
29  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 
30  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 
31  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN 
32  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 
33  * POSSIBILITY OF SUCH DAMAGE.
34  *
35  * Visit http://www.olsr.org for more information.
36  *
37  * If you find this software useful feel free to make a donation
38  * to the project. For more information see the website or contact
39  * the copyright holders.
40  *
41  */
42
43 #include "tc_set.h"
44 #include "ipcalc.h"
45 #include "mid_set.h"
46 #include "link_set.h"
47 #include "olsr.h"
48 #include "scheduler.h"
49 #include "olsr_spf.h"
50 #include "common/avl.h"
51 #include "lq_packet.h"
52 #include "net_olsr.h"
53 #include "lq_plugin.h"
54 #include "olsr_cookie.h"
55
56 #include <assert.h>
57
58 /* Root of the link state database */
59 struct avl_tree tc_tree;
60 struct tc_entry *tc_myself;            /* Shortcut to ourselves */
61
62 /* Some cookies for stats keeping */
63 struct olsr_cookie_info *tc_edge_gc_timer_cookie = NULL;
64 struct olsr_cookie_info *tc_validity_timer_cookie = NULL;
65 struct olsr_cookie_info *tc_edge_mem_cookie = NULL;
66 struct olsr_cookie_info *tc_mem_cookie = NULL;
67
68 /*
69  * Sven-Ola 2007-Dec: These four constants include an assumption
70  * on how long a typical olsrd mesh memorizes (TC) messages in the
71  * RAM of all nodes and how many neighbour changes between TC msgs.
72  * In Berlin, we encounter hop values up to 70 which means that
73  * messages may live up to ~15 minutes cycling between nodes and
74  * obviously breaking out of the timeout_dup() jail. It may be more
75  * correct to dynamically adapt those constants, e.g. by using the
76  * max hop number (denotes size-of-mesh) in some form or maybe
77  * a factor indicating how many (old) versions of olsrd are on.
78  */
79
80 /* Value window for ansn, identifies old messages to be ignored */
81 #define TC_ANSN_WINDOW 256
82
83 /* Value window for seqno, identifies old messages to be ignored */
84 #define TC_SEQNO_WINDOW 1024
85
86 /* Enlarges the value window for upcoming ansn/seqno to be accepted */
87 #define TC_ANSN_WINDOW_MULT 4
88
89 /* Enlarges the value window for upcoming ansn/seqno to be accepted */
90 #define TC_SEQNO_WINDOW_MULT 8
91
92 static olsr_bool
93 olsr_seq_inrange_low(int beg, int end, olsr_u16_t seq)
94 {
95   if (beg < 0) {
96     if (seq >= (olsr_u16_t) beg || seq < end) {
97       return OLSR_TRUE;
98     }
99   } else if (end >= 0x10000) {
100     if (seq >= beg || seq < (olsr_u16_t) end) {
101       return OLSR_TRUE;
102     }
103   } else if (seq >= beg && seq < end) {
104     return OLSR_TRUE;
105   }
106   return OLSR_FALSE;
107 }
108
109 static olsr_bool
110 olsr_seq_inrange_high(int beg, int end, olsr_u16_t seq)
111 {
112   if (beg < 0) {
113     if (seq > (olsr_u16_t) beg || seq <= end) {
114       return OLSR_TRUE;
115     }
116   } else if (end >= 0x10000) {
117     if (seq > beg || seq <= (olsr_u16_t) end) {
118       return OLSR_TRUE;
119     }
120   } else if (seq > beg && seq <= end) {
121     return OLSR_TRUE;
122   }
123   return OLSR_FALSE;
124 }
125
126 /**
127  * Add a new tc_entry to the tc tree
128  *
129  * @param (last)adr address of the entry
130  * @return a pointer to the created entry
131  */
132 static struct tc_entry *
133 olsr_add_tc_entry(union olsr_ip_addr *adr)
134 {
135 #if !defined(NODEBUG) && defined(DEBUG)
136   struct ipaddr_str buf;
137 #endif
138   struct tc_entry *tc;
139
140 #ifdef DEBUG
141   OLSR_PRINTF(1, "TC: add entry %s\n", olsr_ip_to_string(&buf, adr));
142 #endif
143
144   tc = olsr_cookie_malloc(tc_mem_cookie);
145   if (!tc) {
146     return NULL;
147   }
148
149   /* Fill entry */
150   tc->addr = *adr;
151   tc->vertex_node.key = &tc->addr;
152
153   /*
154    * Insert into the global tc tree.
155    */
156   avl_insert(&tc_tree, &tc->vertex_node, AVL_DUP_NO);
157   olsr_lock_tc_entry(tc);
158
159   /*
160    * Initialize subtrees for edges and prefixes.
161    */
162   avl_init(&tc->edge_tree, avl_comp_default);
163   avl_init(&tc->prefix_tree, avl_comp_prefix_default);
164
165   /*
166    * Add a rt_path for ourselves.
167    */
168   olsr_insert_routing_table(adr, olsr_cnf->maxplen, adr, OLSR_RT_ORIGIN_INT);
169
170   return tc;
171 }
172
173 /**
174  * Initialize the topology set
175  *
176  */
177 void
178 olsr_init_tc(void)
179 {
180   OLSR_PRINTF(5, "TC: init topo\n");
181
182   avl_init(&tc_tree, avl_comp_default);
183
184   /*
185    * Get some cookies for getting stats to ease troubleshooting.
186    */
187   tc_edge_gc_timer_cookie =
188     olsr_alloc_cookie("TC edge GC", OLSR_COOKIE_TYPE_TIMER);
189   tc_validity_timer_cookie =
190     olsr_alloc_cookie("TC validity", OLSR_COOKIE_TYPE_TIMER);
191
192   tc_edge_mem_cookie =
193     olsr_alloc_cookie("tc_edge_entry", OLSR_COOKIE_TYPE_MEMORY);
194   olsr_cookie_set_memory_size(tc_edge_mem_cookie,
195                               sizeof(struct tc_edge_entry) +
196                               active_lq_handler->tc_lq_size);
197
198   tc_mem_cookie = olsr_alloc_cookie("tc_entry", OLSR_COOKIE_TYPE_MEMORY);
199   olsr_cookie_set_memory_size(tc_mem_cookie, sizeof(struct tc_entry));
200
201   /*
202    * Add a TC entry for ourselves.
203    */
204   tc_myself = olsr_add_tc_entry(&olsr_cnf->main_addr);
205 }
206
207 /**
208  * The main ip address has changed.
209  * Do the needful.
210  */
211 void
212 olsr_change_myself_tc(void)
213 {
214   if (tc_myself) {
215
216     /*
217      * Check if there was a change.
218      */
219     if (ipequal(&tc_myself->addr, &olsr_cnf->main_addr)) {
220       return;
221     }
222
223     /*
224      * Flush our own tc_entry.
225      */
226     olsr_delete_tc_entry(tc_myself);
227   }
228
229   /*
230    * The old entry for ourselves is gone, generate a new one and trigger SPF.
231    */
232   tc_myself = olsr_add_tc_entry(&olsr_cnf->main_addr);
233   changes_topology = OLSR_TRUE;
234 }
235
236 /*
237  * Increment the reference counter.
238  */
239 void
240 olsr_lock_tc_entry(struct tc_entry *tc)
241 {
242   tc->refcount++;
243 }
244
245 /*
246  * Unlock and free a tc_entry once all references are gone.
247  */
248 void
249 olsr_unlock_tc_entry(struct tc_entry *tc)
250 {
251   if (--tc->refcount) {
252     return;
253   }
254
255   /*
256    * All references are gone.
257    */
258   olsr_cookie_free(tc_mem_cookie, tc);
259 }
260
261 /**
262  * Delete a TC entry.
263  *
264  * @param entry the TC entry to delete
265  *
266  */
267 void
268 olsr_delete_tc_entry(struct tc_entry *tc)
269 {
270   struct tc_edge_entry *tc_edge;
271   struct rt_path *rtp;
272 #if 0
273   struct ipaddr_str buf;
274   OLSR_PRINTF(1, "TC: del entry %s\n", olsr_ip_to_string(&buf, &tc->addr));
275 #endif
276
277   /*
278    * Delete the rt_path for ourselves.
279    */
280   olsr_delete_routing_table(&tc->addr, olsr_cnf->maxplen, &tc->addr);
281
282   /* The edgetree and prefix tree must be empty before */
283   OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
284     olsr_delete_tc_edge_entry(tc_edge);
285   } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge);
286
287   OLSR_FOR_ALL_PREFIX_ENTRIES(tc, rtp) {
288     olsr_delete_rt_path(rtp);
289   } OLSR_FOR_ALL_PREFIX_ENTRIES_END(tc, rtp);
290
291   /* Stop running timers */
292   olsr_stop_timer(tc->edge_gc_timer);
293   tc->edge_gc_timer = NULL;
294   olsr_stop_timer(tc->validity_timer);
295   tc->validity_timer = NULL;
296
297   avl_delete(&tc_tree, &tc->vertex_node);
298   olsr_unlock_tc_entry(tc);
299 }
300
301 /**
302  * Look up a entry from the TC tree based on address
303  *
304  * @param adr the address to look for
305  * @return the entry found or NULL
306  */
307 struct tc_entry *
308 olsr_lookup_tc_entry(union olsr_ip_addr *adr)
309 {
310   struct avl_node *node;
311
312 #if 0
313   OLSR_PRINTF(1, "TC: lookup entry\n");
314 #endif
315
316   node = avl_find(&tc_tree, adr);
317
318   return (node ? vertex_tree2tc(node) : NULL);
319 }
320
321 /*
322  * Lookup a tc entry. Creates one if it does not exist yet.
323  */
324 struct tc_entry *
325 olsr_locate_tc_entry(union olsr_ip_addr *adr)
326 {
327   struct tc_entry *tc;
328
329   if (!(tc = olsr_lookup_tc_entry(adr))) {
330     return olsr_add_tc_entry(adr);
331   }
332   return tc;
333 }
334
335 /**
336  * Format tc_edge contents into a buffer.
337  */
338 char *
339 olsr_tc_edge_to_string(struct tc_edge_entry *tc_edge)
340 {
341   static char buf[128];
342   struct ipaddr_str addrbuf, dstbuf;
343   struct tc_entry *tc = tc_edge->tc;
344   struct lqtextbuffer lqbuffer1, lqbuffer2;
345
346   snprintf(buf, sizeof(buf),
347            "%s > %s, cost (%6s) %s",
348            olsr_ip_to_string(&addrbuf, &tc->addr),
349            olsr_ip_to_string(&dstbuf, &tc_edge->T_dest_addr),
350            get_tc_edge_entry_text(tc_edge, &lqbuffer1),
351            get_linkcost_text(tc_edge->cost, OLSR_FALSE, &lqbuffer2));
352
353   return buf;
354 }
355
356 /**
357  * Wrapper for the timer callback.
358  * A TC entry has not been refreshed in time.
359  * Remove it from the link-state database.
360  */
361 static void
362 olsr_expire_tc_entry(void *context)
363 {
364   struct tc_entry *tc;
365
366   tc = (struct tc_entry *)context;
367   tc->validity_timer = NULL;
368
369   olsr_delete_tc_entry(tc);
370   changes_topology = OLSR_TRUE;
371 }
372
373 /**
374  * Wrapper for the timer callback.
375  * Does the garbage collection of older ansn entries after no edge addition to
376  * the TC entry has happened for OLSR_TC_EDGE_GC_TIME.
377  */
378 static void
379 olsr_expire_tc_edge_gc(void *context)
380 {
381   struct tc_entry *tc;
382
383   tc = (struct tc_entry *)context;
384   tc->edge_gc_timer = NULL;
385
386   if (olsr_delete_outdated_tc_edges(tc)) {
387     changes_topology = OLSR_TRUE;
388   }
389 }
390
391 /*
392  * If the edge does not have a minimum acceptable link quality
393  * set the etx cost to infinity such that it gets ignored during
394  * SPF calculation.
395  * 
396  * @return 1 if the change of the etx value was relevant
397  */
398 olsr_bool
399 olsr_calc_tc_edge_entry_etx(struct tc_edge_entry *tc_edge)
400 {
401   olsr_linkcost old;
402
403   /*
404    * Some sanity check before recalculating the etx.
405    */
406   if (olsr_cnf->lq_level < 1) {
407     return 0;
408   }
409
410   old = tc_edge->cost;
411   tc_edge->cost = olsr_calc_tc_cost(tc_edge);
412
413   return olsr_is_relevant_costchange(old, tc_edge->cost);
414 }
415
416 /**
417  * Add a new tc_edge_entry to the tc_edge_tree
418  *
419  * @param (last)adr address of the entry
420  * @return a pointer to the created entry
421  */
422 struct tc_edge_entry *
423 olsr_add_tc_edge_entry(struct tc_entry *tc, union olsr_ip_addr *addr,
424                        olsr_u16_t ansn)
425 {
426 #if !defined(NODEBUG) && defined(DEBUG)
427   struct ipaddr_str buf;
428 #endif
429   struct tc_entry *tc_neighbor;
430   struct tc_edge_entry *tc_edge, *tc_edge_inv;
431
432   tc_edge = olsr_cookie_malloc(tc_edge_mem_cookie);
433   if (!tc_edge) {
434     return NULL;
435   }
436
437   /* Fill entry */
438   tc_edge->T_dest_addr = *addr;
439   tc_edge->ansn = ansn;
440   tc_edge->edge_node.key = &tc_edge->T_dest_addr;
441
442   /*
443    * Insert into the edge tree.
444    */
445   avl_insert(&tc->edge_tree, &tc_edge->edge_node, AVL_DUP_NO);
446   olsr_lock_tc_entry(tc);
447
448   /*
449    * Connect backpointer.
450    */
451   tc_edge->tc = tc;
452
453   /*
454    * Check if the neighboring router and the inverse edge is in the lsdb.
455    * Create short cuts to the inverse edge for faster SPF execution.
456    */
457   tc_neighbor = olsr_lookup_tc_entry(&tc_edge->T_dest_addr);
458   if (tc_neighbor) {
459 #ifdef DEBUG
460     OLSR_PRINTF(1, "TC:   found neighbor tc_entry %s\n",
461                 olsr_ip_to_string(&buf, &tc_neighbor->addr));
462 #endif
463
464     tc_edge_inv = olsr_lookup_tc_edge(tc_neighbor, &tc->addr);
465     if (tc_edge_inv) {
466 #ifdef DEBUG
467       OLSR_PRINTF(1, "TC:   found inverse edge for %s\n",
468                   olsr_ip_to_string(&buf, &tc_edge_inv->T_dest_addr));
469 #endif
470
471       /*
472        * Connect the edges mutually.
473        */
474       tc_edge_inv->edge_inv = tc_edge;
475       tc_edge->edge_inv = tc_edge_inv;
476
477     }
478   }
479
480   /*
481    * Update the etx.
482    */
483   olsr_calc_tc_edge_entry_etx(tc_edge);
484
485 #ifdef DEBUG
486   OLSR_PRINTF(1, "TC: add edge entry %s\n", olsr_tc_edge_to_string(tc_edge));
487 #endif
488
489   return tc_edge;
490 }
491
492 /**
493  * Delete a TC edge entry.
494  *
495  * @param tc the TC entry
496  * @param tc_edge the TC edge entry
497  */
498 void
499 olsr_delete_tc_edge_entry(struct tc_edge_entry *tc_edge)
500 {
501   struct tc_entry *tc;
502   struct tc_edge_entry *tc_edge_inv;
503
504 #ifdef DEBUG
505   OLSR_PRINTF(1, "TC: del edge entry %s\n", olsr_tc_edge_to_string(tc_edge));
506 #endif
507
508   tc = tc_edge->tc;
509   avl_delete(&tc->edge_tree, &tc_edge->edge_node);
510   olsr_unlock_tc_entry(tc);
511
512   /*
513    * Clear the backpointer of our inverse edge.
514    */
515   tc_edge_inv = tc_edge->edge_inv;
516   if (tc_edge_inv) {
517     tc_edge_inv->edge_inv = NULL;
518   }
519
520   olsr_cookie_free(tc_edge_mem_cookie, tc_edge);
521 }
522
523 /**
524  * Delete all destinations that have a lower ANSN.
525  *
526  * @param tc the entry to delete edges from
527  * @return TRUE if any destinations were deleted, FALSE if not
528  */
529 olsr_bool
530 olsr_delete_outdated_tc_edges(struct tc_entry *tc)
531 {
532   struct tc_edge_entry *tc_edge;
533   olsr_bool retval = OLSR_FALSE;
534
535 #if 0
536   OLSR_PRINTF(5, "TC: deleting outdated TC-edge entries\n");
537 #endif
538
539   OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
540     if (SEQNO_GREATER_THAN(tc->ansn, tc_edge->ansn)) {
541       olsr_delete_tc_edge_entry(tc_edge);
542       retval = OLSR_TRUE;
543     }
544   } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge);
545
546   return retval;
547 }
548
549 /**
550  * Delete all destinations that are inside the borders but
551  * not updated in the last tc.
552  *
553  * @param tc the entry to delete edges from
554  * @param ansn the advertised neighbor set sequence number
555  * @return 1 if any destinations were deleted 0 if not
556  */
557 static int
558 olsr_delete_revoked_tc_edges(struct tc_entry *tc, olsr_u16_t ansn,
559                              union olsr_ip_addr *lower_border,
560                              union olsr_ip_addr *upper_border)
561 {
562   struct tc_edge_entry *tc_edge;
563   int retval = 0;
564
565 #if 0
566   OLSR_PRINTF(5, "TC: deleting MPRS\n");
567 #endif
568
569   olsr_bool passedLowerBorder = OLSR_FALSE;
570
571   OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
572     if (!passedLowerBorder) {
573       if (avl_comp_default(lower_border, &tc_edge->T_dest_addr) <= 0) {
574         passedLowerBorder = OLSR_TRUE;
575       } else {
576         continue;
577       }
578     }
579
580     if (passedLowerBorder) {
581       if (avl_comp_default(upper_border, &tc_edge->T_dest_addr) <= 0) {
582         break;
583       }
584     }
585
586     if (SEQNO_GREATER_THAN(ansn, tc_edge->ansn)) {
587       olsr_delete_tc_edge_entry(tc_edge);
588       retval = 1;
589     }
590   } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge);
591
592   return retval;
593 }
594
595
596 /**
597  * Update an edge registered on an entry.
598  * Creates new edge-entries if not registered.
599  * Bases update on a received TC message
600  *
601  * @param entry the TC entry to check
602  * @pkt the TC edge entry in the packet
603  * @return 1 if entries are added 0 if not
604  */
605 static int
606 olsr_tc_update_edge(struct tc_entry *tc, olsr_u16_t ansn,
607                     const unsigned char **curr, union olsr_ip_addr *neighbor)
608 {
609   struct tc_edge_entry *tc_edge;
610   int edge_change;
611
612   edge_change = 0;
613
614   /*
615    * Fetch the per-edge data
616    */
617   pkt_get_ipaddress(curr, neighbor);
618
619   /* First check if we know this edge */
620   tc_edge = olsr_lookup_tc_edge(tc, neighbor);
621
622   if (!tc_edge) {
623
624     /*
625      * Yet unknown - create it.
626      * Check if the address is allowed.
627      */
628     if (!olsr_validate_address(neighbor)) {
629       return 0;
630     }
631
632     tc_edge = olsr_add_tc_edge_entry(tc, neighbor, ansn);
633
634     olsr_deserialize_tc_lq_pair(curr, tc_edge);
635     edge_change = 1;
636
637   } else {
638
639     /*
640      * We know this edge - Update entry.
641      */
642     tc_edge->ansn = ansn;
643
644     /*
645      * Update link quality if configured.
646      */
647     if (olsr_cnf->lq_level > 0) {
648       olsr_deserialize_tc_lq_pair(curr, tc_edge);
649     }
650
651     /*
652      * Update the etx.
653      */
654     if (olsr_calc_tc_edge_entry_etx(tc_edge)) {
655       if (tc->msg_hops <= olsr_cnf->lq_dlimit) {
656         edge_change = 1;
657       }
658     }
659 #if DEBUG
660     if (edge_change) {
661       OLSR_PRINTF(1, "TC:   chg edge entry %s\n",
662                   olsr_tc_edge_to_string(tc_edge));
663     }
664 #endif
665
666   }
667
668   return edge_change;
669 }
670
671 /**
672  * Lookup an edge hanging off a TC entry.
673  *
674  * @param entry the entry to check
675  * @param dst_addr the destination address to check for
676  * @return a pointer to the tc_edge found - or NULL
677  */
678 struct tc_edge_entry *
679 olsr_lookup_tc_edge(struct tc_entry *tc, union olsr_ip_addr *edge_addr)
680 {
681   struct avl_node *edge_node;
682
683 #if 0
684   OLSR_PRINTF(1, "TC: lookup dst\n");
685 #endif
686
687   edge_node = avl_find(&tc->edge_tree, edge_addr);
688
689   return (edge_node ? edge_tree2tc_edge(edge_node) : NULL);
690 }
691
692 /**
693  * Print the topology table to stdout
694  */
695 void
696 olsr_print_tc_table(void)
697 {
698 #ifndef NODEBUG
699   /* The whole function makes no sense without it. */
700   struct tc_entry *tc;
701   const int ipwidth = olsr_cnf->ip_version == AF_INET ? 15 : 30;
702
703   OLSR_PRINTF(1,
704               "\n--- %s ------------------------------------------------- TOPOLOGY\n\n"
705               "%-*s %-*s %-14s  %s\n", olsr_wallclock_string(), ipwidth,
706               "Source IP addr", ipwidth, "Dest IP addr", "      LQ      ",
707               "ETX");
708
709   OLSR_FOR_ALL_TC_ENTRIES(tc) {
710     struct tc_edge_entry *tc_edge;
711     OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
712       struct ipaddr_str addrbuf, dstaddrbuf;
713       struct lqtextbuffer lqbuffer1, lqbuffer2;
714
715       OLSR_PRINTF(1, "%-*s %-*s %-14s %s\n",
716                   ipwidth, olsr_ip_to_string(&addrbuf, &tc->addr),
717                   ipwidth, olsr_ip_to_string(&dstaddrbuf,
718                                              &tc_edge->T_dest_addr),
719                   get_tc_edge_entry_text(tc_edge, &lqbuffer1),
720                   get_linkcost_text(tc_edge->cost, OLSR_FALSE, &lqbuffer2));
721
722     } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge);
723   } OLSR_FOR_ALL_TC_ENTRIES_END(tc);
724 #endif
725 }
726
727 #ifdef CODE_IS_FIXED_ON_FBSD
728 /*
729  * calculate the border IPs of a tc edge set according to the border flags
730  *
731  * @param lower border flag
732  * @param pointer to lower border ip
733  * @param upper border flag
734  * @param pointer to upper border ip
735  * @result 1 if lower/upper border ip have been set 
736  */
737 static int
738 olsr_calculate_tc_border(olsr_u8_t lower_border,
739                          union olsr_ip_addr *lower_border_ip,
740                          olsr_u8_t upper_border,
741                          union olsr_ip_addr *upper_border_ip)
742 {
743   if (lower_border == 0 && upper_border == 0) {
744     return 0;
745   }
746   if (lower_border == 0xff) {
747     memset(&lower_border_ip, 0, sizeof(lower_border_ip));
748   } else {
749     int i;
750
751     lower_border--;
752     for (i = 0; i < lower_border / 8; i++) {
753       lower_border_ip->v6.in6_u.u6_addr8[olsr_cnf->ipsize - i - 1] = 0;
754     }
755     lower_border_ip->v6.in6_u.u6_addr8[olsr_cnf->ipsize - lower_border / 8 -
756                                        1] &= (0xff << (lower_border & 7));
757     lower_border_ip->v6.in6_u.u6_addr8[olsr_cnf->ipsize - lower_border / 8 -
758                                        1] |= (1 << (lower_border & 7));
759   }
760
761   if (upper_border == 0xff) {
762     memset(&upper_border_ip, 0xff, sizeof(upper_border_ip));
763   } else {
764     int i;
765
766     upper_border--;
767
768     for (i = 0; i < upper_border / 8; i++) {
769       upper_border_ip->v6.in6_u.u6_addr8[olsr_cnf->ipsize - i - 1] = 0;
770     }
771     upper_border_ip->v6.in6_u.u6_addr8[olsr_cnf->ipsize - upper_border / 8 -
772                                        1] &= (0xff << (upper_border & 7));
773     upper_border_ip->v6.in6_u.u6_addr8[olsr_cnf->ipsize - upper_border / 8 -
774                                        1] |= (1 << (upper_border & 7));
775   }
776   return 1;
777 }
778 #endif
779
780 /*
781  * Process an incoming TC or TC_LQ message.
782  *
783  * If the message is interesting enough, update our edges for it,
784  * trigger SPF and finally flood it to all our 2way neighbors.
785  *
786  * The order for extracting data off the message does matter, 
787  * as every call to pkt_get increases the packet offset and
788  * hence the spot we are looking at.
789  */
790 void
791 olsr_input_tc(union olsr_message *msg,
792               struct interface *input_if __attribute__ ((unused)),
793               union olsr_ip_addr *from_addr)
794 {
795 #ifndef NODEBUG
796   struct ipaddr_str buf;
797 #endif
798   olsr_u16_t size, msg_seq, ansn;
799   olsr_u8_t type, ttl, msg_hops, lower_border, upper_border;
800   olsr_reltime vtime;
801   union olsr_ip_addr originator;
802   const unsigned char *limit, *curr;
803   struct tc_entry *tc;
804
805   union olsr_ip_addr lower_border_ip, upper_border_ip;
806   int borderSet = 0;
807
808   curr = (void *)msg;
809   if (!msg) {
810     return;
811   }
812
813   /* We are only interested in TC message types. */
814   pkt_get_u8(&curr, &type);
815   if ((type != LQ_TC_MESSAGE) && (type != TC_MESSAGE)) {
816     return;
817   }
818
819   pkt_get_reltime(&curr, &vtime);
820   pkt_get_u16(&curr, &size);
821
822   pkt_get_ipaddress(&curr, &originator);
823
824   /* Copy header values */
825   pkt_get_u8(&curr, &ttl);
826   pkt_get_u8(&curr, &msg_hops);
827   pkt_get_u16(&curr, &msg_seq);
828   pkt_get_u16(&curr, &ansn);
829
830   /* Get borders */
831   pkt_get_u8(&curr, &lower_border);
832   pkt_get_u8(&curr, &upper_border);
833
834   tc = olsr_lookup_tc_entry(&originator);
835
836   if (tc && 0 != tc->edge_tree.count) {
837     if (olsr_seq_inrange_high((int)tc->msg_seq - TC_SEQNO_WINDOW,
838                               tc->msg_seq,
839                               msg_seq) &&
840         olsr_seq_inrange_high((int)tc->ansn - TC_ANSN_WINDOW, tc->ansn, ansn)) {
841
842       /*
843        * Ignore already seen seq/ansn values (small window for mesh memory)
844        */
845       if ((tc->msg_seq == msg_seq) || (tc->ignored++ < 32)) {
846         return;
847       }
848
849       OLSR_PRINTF(1, "Ignored to much LQTC's for %s, restarting\n",
850                   olsr_ip_to_string(&buf, &originator));
851
852     } else
853       if (!olsr_seq_inrange_high
854           (tc->msg_seq,
855            (int)tc->msg_seq + TC_SEQNO_WINDOW * TC_SEQNO_WINDOW_MULT, msg_seq)
856           || !olsr_seq_inrange_low(tc->ansn,
857                                    (int)tc->ansn +
858                                    TC_ANSN_WINDOW * TC_ANSN_WINDOW_MULT,
859                                    ansn)) {
860
861       /*
862        * Only accept future seq/ansn values (large window for node reconnects).
863        * Restart in all other cases. Ignore a single stray message.
864        */
865       if (!tc->err_seq_valid) {
866         tc->err_seq = msg_seq;
867         tc->err_seq_valid = OLSR_TRUE;
868       }
869       if (tc->err_seq == msg_seq) {
870         return;
871       }
872
873       OLSR_PRINTF(2, "Detected node restart for %s\n",
874                   olsr_ip_to_string(&buf, &originator));
875     }
876   }
877
878   /*
879    * Generate a new tc_entry in the lsdb and store the sequence number.
880    */
881   if (!tc) {
882     tc = olsr_add_tc_entry(&originator);
883   }
884
885   /*
886    * Update the tc entry.
887    */
888   tc->msg_hops = msg_hops;
889   tc->msg_seq = msg_seq;
890   tc->ansn = ansn;
891   tc->ignored = 0;
892   tc->err_seq_valid = OLSR_FALSE;
893
894   /*
895    * If the sender interface (NB: not originator) of this message
896    * is not in the symmetric 1-hop neighborhood of this node, the
897    * message MUST be discarded.
898    */
899   if (check_neighbor_link(from_addr) != SYM_LINK) {
900     OLSR_PRINTF(2, "Received TC from NON SYM neighbor %s\n",
901                 olsr_ip_to_string(&buf, from_addr));
902     return;
903   }
904
905   OLSR_PRINTF(1, "Processing TC from %s, seq 0x%04x\n",
906               olsr_ip_to_string(&buf, &originator), ansn);
907
908   /*
909    * Now walk the edge advertisements contained in the packet.
910    */
911
912   limit = (unsigned char *)msg + size;
913   borderSet = 0;
914   while (curr < limit) {
915     if (olsr_tc_update_edge(tc, ansn, &curr, &upper_border_ip)) {
916       changes_topology = OLSR_TRUE;
917     }
918
919 #ifdef CODE_IS_FIXED_ON_FBSD
920     if (!borderSet) {
921       borderSet = 1;
922       memcpy(&lower_border_ip, &upper_border_ip, sizeof(lower_border_ip));
923     }
924 #endif
925   }
926
927 #ifdef CODE_IS_FIXED_ON_FBSD
928   /*
929    * Calculate real border IPs.
930    */
931   if (borderSet) {
932     borderSet = olsr_calculate_tc_border(lower_border, &lower_border_ip,
933                                          upper_border, &upper_border_ip);
934   }
935 #endif
936
937   /*
938    * Set or change the expiration timer accordingly.
939    */
940   olsr_set_timer(&tc->validity_timer, vtime,
941                  OLSR_TC_VTIME_JITTER, OLSR_TIMER_ONESHOT,
942                  &olsr_expire_tc_entry, tc, tc_validity_timer_cookie->ci_id);
943
944   if (borderSet) {
945
946     /*
947      * Delete all old tc edges within borders.
948      */
949     olsr_delete_revoked_tc_edges(tc, ansn, &lower_border_ip, &upper_border_ip);
950   } else {
951
952     /*
953      * Kick the the edge garbage collection timer. In the meantime hopefully
954      * all edges belonging to a multipart neighbor set will arrive.
955      */
956     olsr_set_timer(&tc->edge_gc_timer, OLSR_TC_EDGE_GC_TIME,
957                    OLSR_TC_EDGE_GC_JITTER, OLSR_TIMER_ONESHOT,
958                    &olsr_expire_tc_edge_gc, tc, tc_edge_gc_timer_cookie->ci_id);
959   }
960
961   /*
962    * Last, flood the message to our other neighbors.
963    */
964   olsr_forward_message(msg, from_addr);
965   return;
966 }
967
968 /*
969  * Local Variables:
970  * c-basic-offset: 2
971  * End:
972  */