54778ff4693e609969cfbebed38948cee4acc8bc
[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(const union olsr_ip_addr *adr)
134 {
135 #ifdef DEBUG
136   struct ipaddr_str buf;
137 #endif
138   struct tc_entry *tc;
139
140   /*
141    * Safety net against loss of the last main IP address.
142    */
143   if (ipequal(&olsr_cnf->main_addr, &all_zero)) {
144     return NULL;
145   }
146
147 #ifdef DEBUG
148   OLSR_PRINTF(1, "TC: add entry %s\n", olsr_ip_to_string(&buf, adr));
149 #endif
150
151   tc = olsr_cookie_malloc(tc_mem_cookie);
152   if (!tc) {
153     return NULL;
154   }
155
156   /* Fill entry */
157   tc->addr = *adr;
158   tc->vertex_node.key = &tc->addr;
159
160   /*
161    * Insert into the global tc tree.
162    */
163   avl_insert(&tc_tree, &tc->vertex_node, AVL_DUP_NO);
164   olsr_lock_tc_entry(tc);
165
166   /*
167    * Initialize subtrees for edges, prefixes and MIDs.
168    */
169   avl_init(&tc->edge_tree, avl_comp_default);
170   avl_init(&tc->prefix_tree, avl_comp_prefix_default);
171   avl_init(&tc->mid_tree, avl_comp_default);
172
173   /*
174    * Add a rt_path for ourselves.
175    */
176   olsr_insert_routing_table(adr, olsr_cnf->maxplen, adr, OLSR_RT_ORIGIN_INT);
177
178   return tc;
179 }
180
181 /**
182  * Initialize the topology set
183  *
184  */
185 void
186 olsr_init_tc(void)
187 {
188   OLSR_PRINTF(5, "TC: init topo\n");
189
190   avl_init(&tc_tree, avl_comp_default);
191
192   /*
193    * Get some cookies for getting stats to ease troubleshooting.
194    */
195   tc_edge_gc_timer_cookie =
196     olsr_alloc_cookie("TC edge GC", OLSR_COOKIE_TYPE_TIMER);
197   tc_validity_timer_cookie =
198     olsr_alloc_cookie("TC validity", OLSR_COOKIE_TYPE_TIMER);
199
200   tc_edge_mem_cookie =
201     olsr_alloc_cookie("tc_edge_entry", OLSR_COOKIE_TYPE_MEMORY);
202   olsr_cookie_set_memory_size(tc_edge_mem_cookie,
203                               sizeof(struct tc_edge_entry) +
204                               active_lq_handler->tc_lq_size);
205
206   tc_mem_cookie = olsr_alloc_cookie("tc_entry", OLSR_COOKIE_TYPE_MEMORY);
207   olsr_cookie_set_memory_size(tc_mem_cookie, sizeof(struct tc_entry));
208
209   /*
210    * Add a TC entry for ourselves.
211    */
212   tc_myself = olsr_add_tc_entry(&olsr_cnf->main_addr);
213 }
214
215 /**
216  * The main ip address has changed.
217  * Do the needful.
218  */
219 void
220 olsr_change_myself_tc(void)
221 {
222   if (tc_myself) {
223
224     /*
225      * Check if there was a change.
226      */
227     if (ipequal(&tc_myself->addr, &olsr_cnf->main_addr)) {
228       return;
229     }
230
231     /*
232      * Flush our own tc_entry.
233      */
234     olsr_delete_tc_entry(tc_myself);
235   }
236
237   /*
238    * The old entry for ourselves is gone, generate a new one and trigger SPF.
239    */
240   tc_myself = olsr_add_tc_entry(&olsr_cnf->main_addr);
241   changes_topology = OLSR_TRUE;
242 }
243
244 /*
245  * Increment the reference counter.
246  */
247 void
248 olsr_lock_tc_entry(struct tc_entry *tc)
249 {
250   tc->refcount++;
251 }
252
253 /*
254  * Unlock and free a tc_entry once all references are gone.
255  */
256 void
257 olsr_unlock_tc_entry(struct tc_entry *tc)
258 {
259   if (--tc->refcount) {
260     return;
261   }
262
263   /*
264    * All references are gone.
265    */
266   olsr_cookie_free(tc_mem_cookie, tc);
267 }
268
269 /**
270  * Delete a TC entry.
271  *
272  * @param entry the TC entry to delete
273  *
274  */
275 void
276 olsr_delete_tc_entry(struct tc_entry *tc)
277 {
278   struct tc_edge_entry *tc_edge;
279   struct rt_path *rtp;
280 #if 0
281   struct ipaddr_str buf;
282   OLSR_PRINTF(1, "TC: del entry %s\n", olsr_ip_to_string(&buf, &tc->addr));
283 #endif
284
285   /*
286    * Delete the rt_path for ourselves.
287    */
288   olsr_delete_routing_table(&tc->addr, olsr_cnf->maxplen, &tc->addr);
289
290   /* The edgetree and prefix tree must be empty before */
291   OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
292     olsr_delete_tc_edge_entry(tc_edge);
293   } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge);
294
295   OLSR_FOR_ALL_PREFIX_ENTRIES(tc, rtp) {
296     olsr_delete_rt_path(rtp);
297   } OLSR_FOR_ALL_PREFIX_ENTRIES_END(tc, rtp);
298
299   /* Stop running timers */
300   olsr_stop_timer(tc->edge_gc_timer);
301   tc->edge_gc_timer = NULL;
302   olsr_stop_timer(tc->validity_timer);
303   tc->validity_timer = NULL;
304
305   avl_delete(&tc_tree, &tc->vertex_node);
306   olsr_unlock_tc_entry(tc);
307 }
308
309 /**
310  * Look up a entry from the TC tree based on address
311  *
312  * @param adr the address to look for
313  * @return the entry found or NULL
314  */
315 struct tc_entry *
316 olsr_lookup_tc_entry(const union olsr_ip_addr *adr)
317 {
318   struct avl_node *node;
319
320 #if 0
321   OLSR_PRINTF(1, "TC: lookup entry\n");
322 #endif
323
324   node = avl_find(&tc_tree, adr);
325
326   return (node ? vertex_tree2tc(node) : NULL);
327 }
328
329 /*
330  * Lookup a tc entry. Creates one if it does not exist yet.
331  */
332 struct tc_entry *
333 olsr_locate_tc_entry(const union olsr_ip_addr *adr)
334 {
335   struct tc_entry *tc;
336
337   if (!(tc = olsr_lookup_tc_entry(adr))) {
338     return olsr_add_tc_entry(adr);
339   }
340   return tc;
341 }
342
343 /**
344  * Format tc_edge contents into a buffer.
345  */
346 char *
347 olsr_tc_edge_to_string(struct tc_edge_entry *tc_edge)
348 {
349   static char buf[128];
350   struct ipaddr_str addrbuf, dstbuf;
351   struct tc_entry *tc = tc_edge->tc;
352   struct lqtextbuffer lqbuffer1, lqbuffer2;
353
354   snprintf(buf, sizeof(buf),
355            "%s > %s, cost (%6s) %s",
356            olsr_ip_to_string(&addrbuf, &tc->addr),
357            olsr_ip_to_string(&dstbuf, &tc_edge->T_dest_addr),
358            get_tc_edge_entry_text(tc_edge, '/', &lqbuffer1),
359            get_linkcost_text(tc_edge->cost, OLSR_FALSE, &lqbuffer2));
360
361   return buf;
362 }
363
364 /**
365  * Wrapper for the timer callback.
366  * A TC entry has not been refreshed in time.
367  * Remove it from the link-state database.
368  */
369 static void
370 olsr_expire_tc_entry(void *context)
371 {
372   struct tc_entry *tc;
373
374   tc = (struct tc_entry *)context;
375   tc->validity_timer = NULL;
376
377   olsr_delete_tc_entry(tc);
378   changes_topology = OLSR_TRUE;
379 }
380
381 /**
382  * Wrapper for the timer callback.
383  * Does the garbage collection of older ansn entries after no edge addition to
384  * the TC entry has happened for OLSR_TC_EDGE_GC_TIME.
385  */
386 static void
387 olsr_expire_tc_edge_gc(void *context)
388 {
389   struct tc_entry *tc;
390
391   tc = (struct tc_entry *)context;
392   tc->edge_gc_timer = NULL;
393
394   if (olsr_delete_outdated_tc_edges(tc)) {
395     changes_topology = OLSR_TRUE;
396   }
397 }
398
399 /*
400  * If the edge does not have a minimum acceptable link quality
401  * set the etx cost to infinity such that it gets ignored during
402  * SPF calculation.
403  * 
404  * @return 1 if the change of the etx value was relevant
405  */
406 olsr_bool
407 olsr_calc_tc_edge_entry_etx(struct tc_edge_entry *tc_edge)
408 {
409   olsr_linkcost old;
410
411   /*
412    * Some sanity check before recalculating the etx.
413    */
414   if (olsr_cnf->lq_level < 1) {
415     return 0;
416   }
417
418   old = tc_edge->cost;
419   tc_edge->cost = olsr_calc_tc_cost(tc_edge);
420
421   return olsr_is_relevant_costchange(old, tc_edge->cost);
422 }
423
424 /**
425  * Add a new tc_edge_entry to the tc_edge_tree
426  *
427  * @param (last)adr address of the entry
428  * @return a pointer to the created entry
429  */
430 struct tc_edge_entry *
431 olsr_add_tc_edge_entry(struct tc_entry *tc, union olsr_ip_addr *addr,
432                        olsr_u16_t ansn)
433 {
434 #ifdef DEBUG
435   struct ipaddr_str buf;
436 #endif
437   struct tc_entry *tc_neighbor;
438   struct tc_edge_entry *tc_edge, *tc_edge_inv;
439
440   tc_edge = olsr_cookie_malloc(tc_edge_mem_cookie);
441   if (!tc_edge) {
442     return NULL;
443   }
444
445   /* Fill entry */
446   tc_edge->T_dest_addr = *addr;
447   tc_edge->ansn = ansn;
448   tc_edge->edge_node.key = &tc_edge->T_dest_addr;
449
450   /*
451    * Insert into the edge tree.
452    */
453   avl_insert(&tc->edge_tree, &tc_edge->edge_node, AVL_DUP_NO);
454   olsr_lock_tc_entry(tc);
455
456   /*
457    * Connect backpointer.
458    */
459   tc_edge->tc = tc;
460
461   /*
462    * Check if the neighboring router and the inverse edge is in the lsdb.
463    * Create short cuts to the inverse edge for faster SPF execution.
464    */
465   tc_neighbor = olsr_lookup_tc_entry(&tc_edge->T_dest_addr);
466   if (tc_neighbor) {
467 #ifdef DEBUG
468     OLSR_PRINTF(1, "TC:   found neighbor tc_entry %s\n",
469                 olsr_ip_to_string(&buf, &tc_neighbor->addr));
470 #endif
471
472     tc_edge_inv = olsr_lookup_tc_edge(tc_neighbor, &tc->addr);
473     if (tc_edge_inv) {
474 #ifdef DEBUG
475       OLSR_PRINTF(1, "TC:   found inverse edge for %s\n",
476                   olsr_ip_to_string(&buf, &tc_edge_inv->T_dest_addr));
477 #endif
478
479       /*
480        * Connect the edges mutually.
481        */
482       tc_edge_inv->edge_inv = tc_edge;
483       tc_edge->edge_inv = tc_edge_inv;
484
485     }
486   }
487
488   /*
489    * Update the etx.
490    */
491   olsr_calc_tc_edge_entry_etx(tc_edge);
492
493 #ifdef DEBUG
494   OLSR_PRINTF(1, "TC: add edge entry %s\n", olsr_tc_edge_to_string(tc_edge));
495 #endif
496
497   return tc_edge;
498 }
499
500 /**
501  * Delete a TC edge entry.
502  *
503  * @param tc the TC entry
504  * @param tc_edge the TC edge entry
505  */
506 void
507 olsr_delete_tc_edge_entry(struct tc_edge_entry *tc_edge)
508 {
509   struct tc_entry *tc;
510   struct tc_edge_entry *tc_edge_inv;
511
512 #ifdef DEBUG
513   OLSR_PRINTF(1, "TC: del edge entry %s\n", olsr_tc_edge_to_string(tc_edge));
514 #endif
515
516   tc = tc_edge->tc;
517   avl_delete(&tc->edge_tree, &tc_edge->edge_node);
518   olsr_unlock_tc_entry(tc);
519
520   /*
521    * Clear the backpointer of our inverse edge.
522    */
523   tc_edge_inv = tc_edge->edge_inv;
524   if (tc_edge_inv) {
525     tc_edge_inv->edge_inv = NULL;
526   }
527
528   olsr_cookie_free(tc_edge_mem_cookie, tc_edge);
529 }
530
531 /**
532  * Delete all destinations that have a lower ANSN.
533  *
534  * @param tc the entry to delete edges from
535  * @return TRUE if any destinations were deleted, FALSE if not
536  */
537 olsr_bool
538 olsr_delete_outdated_tc_edges(struct tc_entry *tc)
539 {
540   struct tc_edge_entry *tc_edge;
541   olsr_bool retval = OLSR_FALSE;
542
543 #if 0
544   OLSR_PRINTF(5, "TC: deleting outdated TC-edge entries\n");
545 #endif
546
547   OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
548     if (SEQNO_GREATER_THAN(tc->ansn, tc_edge->ansn)) {
549       olsr_delete_tc_edge_entry(tc_edge);
550       retval = OLSR_TRUE;
551     }
552   } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge);
553
554   return retval;
555 }
556
557 /**
558  * Delete all destinations that are inside the borders but
559  * not updated in the last tc.
560  *
561  * @param tc the entry to delete edges from
562  * @param ansn the advertised neighbor set sequence number
563  * @return 1 if any destinations were deleted 0 if not
564  */
565 static int
566 olsr_delete_revoked_tc_edges(struct tc_entry *tc, olsr_u16_t ansn,
567                              union olsr_ip_addr *lower_border,
568                              union olsr_ip_addr *upper_border)
569 {
570   struct tc_edge_entry *tc_edge;
571   int retval = 0;
572
573 #if 0
574   OLSR_PRINTF(5, "TC: deleting MPRS\n");
575 #endif
576
577   olsr_bool passedLowerBorder = OLSR_FALSE;
578
579   OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
580     if (!passedLowerBorder) {
581       if (avl_comp_default(lower_border, &tc_edge->T_dest_addr) <= 0) {
582         passedLowerBorder = OLSR_TRUE;
583       } else {
584         continue;
585       }
586     }
587
588     if (passedLowerBorder) {
589       if (avl_comp_default(upper_border, &tc_edge->T_dest_addr) <= 0) {
590         break;
591       }
592     }
593
594     if (SEQNO_GREATER_THAN(ansn, tc_edge->ansn)) {
595       olsr_delete_tc_edge_entry(tc_edge);
596       retval = 1;
597     }
598   } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge);
599
600   return retval;
601 }
602
603
604 /**
605  * Update an edge registered on an entry.
606  * Creates new edge-entries if not registered.
607  * Bases update on a received TC message
608  *
609  * @param entry the TC entry to check
610  * @pkt the TC edge entry in the packet
611  * @return 1 if entries are added 0 if not
612  */
613 static int
614 olsr_tc_update_edge(struct tc_entry *tc, olsr_u16_t ansn,
615                     const unsigned char **curr, union olsr_ip_addr *neighbor)
616 {
617   struct tc_edge_entry *tc_edge;
618   int edge_change;
619
620   edge_change = 0;
621
622   /*
623    * Fetch the per-edge data
624    */
625   pkt_get_ipaddress(curr, neighbor);
626
627   /* First check if we know this edge */
628   tc_edge = olsr_lookup_tc_edge(tc, neighbor);
629
630   if (!tc_edge) {
631
632     /*
633      * Yet unknown - create it.
634      * Check if the address is allowed.
635      */
636     if (!olsr_validate_address(neighbor)) {
637       return 0;
638     }
639
640     tc_edge = olsr_add_tc_edge_entry(tc, neighbor, ansn);
641
642     olsr_deserialize_tc_lq_pair(curr, tc_edge);
643     edge_change = 1;
644
645   } else {
646
647     /*
648      * We know this edge - Update entry.
649      */
650     tc_edge->ansn = ansn;
651
652     /*
653      * Update link quality if configured.
654      */
655     if (olsr_cnf->lq_level > 0) {
656       olsr_deserialize_tc_lq_pair(curr, tc_edge);
657     }
658
659     /*
660      * Update the etx.
661      */
662     if (olsr_calc_tc_edge_entry_etx(tc_edge)) {
663       if (tc->msg_hops <= olsr_cnf->lq_dlimit) {
664         edge_change = 1;
665       }
666     }
667 #if DEBUG
668     if (edge_change) {
669       OLSR_PRINTF(1, "TC:   chg edge entry %s\n",
670                   olsr_tc_edge_to_string(tc_edge));
671     }
672 #endif
673
674   }
675
676   return edge_change;
677 }
678
679 /**
680  * Lookup an edge hanging off a TC entry.
681  *
682  * @param entry the entry to check
683  * @param dst_addr the destination address to check for
684  * @return a pointer to the tc_edge found - or NULL
685  */
686 struct tc_edge_entry *
687 olsr_lookup_tc_edge(struct tc_entry *tc, union olsr_ip_addr *edge_addr)
688 {
689   struct avl_node *edge_node;
690
691 #if 0
692   OLSR_PRINTF(1, "TC: lookup dst\n");
693 #endif
694
695   edge_node = avl_find(&tc->edge_tree, edge_addr);
696
697   return (edge_node ? edge_tree2tc_edge(edge_node) : NULL);
698 }
699
700 /**
701  * Print the topology table to stdout
702  */
703 void
704 olsr_print_tc_table(void)
705 {
706 #ifndef NODEBUG
707   /* The whole function makes no sense without it. */
708   struct tc_entry *tc;
709   const int ipwidth = olsr_cnf->ip_version == AF_INET ? 15 : 30;
710
711   OLSR_PRINTF(1,
712               "\n--- %s ------------------------------------------------- TOPOLOGY\n\n"
713               "%-*s %-*s %-14s  %s\n", olsr_wallclock_string(), ipwidth,
714               "Source IP addr", ipwidth, "Dest IP addr", "      LQ      ",
715               "ETX");
716
717   OLSR_FOR_ALL_TC_ENTRIES(tc) {
718     struct tc_edge_entry *tc_edge;
719     OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
720       struct ipaddr_str addrbuf, dstaddrbuf;
721       struct lqtextbuffer lqbuffer1, lqbuffer2;
722
723       OLSR_PRINTF(1, "%-*s %-*s %-14s %s\n",
724                   ipwidth, olsr_ip_to_string(&addrbuf, &tc->addr),
725                   ipwidth, olsr_ip_to_string(&dstaddrbuf,
726                                              &tc_edge->T_dest_addr),
727                   get_tc_edge_entry_text(tc_edge, '/', &lqbuffer1),
728                   get_linkcost_text(tc_edge->cost, OLSR_FALSE, &lqbuffer2));
729
730     } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge);
731   } OLSR_FOR_ALL_TC_ENTRIES_END(tc);
732 #endif
733 }
734
735 /*
736  * calculate the border IPs of a tc edge set according to the border flags
737  *
738  * @param lower border flag
739  * @param pointer to lower border ip
740  * @param upper border flag
741  * @param pointer to upper border ip
742  * @result 1 if lower/upper border ip have been set 
743  */
744 static int
745 olsr_calculate_tc_border(olsr_u8_t lower_border,
746                          union olsr_ip_addr *lower_border_ip,
747                          olsr_u8_t upper_border,
748                          union olsr_ip_addr *upper_border_ip)
749 {
750   if (lower_border == 0 && upper_border == 0) {
751     return 0;
752   }
753   if (lower_border == 0xff) {
754     memset(&lower_border_ip, 0, sizeof(lower_border_ip));
755   } else {
756     int i;
757
758     lower_border--;
759     for (i = 0; i < lower_border / 8; i++) {
760                 lower_border_ip->v6.s6_addr[olsr_cnf->ipsize - i - 1] = 0;
761     }
762     lower_border_ip->v6.s6_addr[olsr_cnf->ipsize - lower_border / 8 -
763                                        1] &= (0xff << (lower_border & 7));
764     lower_border_ip->v6.s6_addr[olsr_cnf->ipsize - lower_border / 8 -
765                                        1] |= (1 << (lower_border & 7));
766   }
767
768   if (upper_border == 0xff) {
769     memset(&upper_border_ip, 0xff, sizeof(upper_border_ip));
770   } else {
771     int i;
772
773     upper_border--;
774
775     for (i = 0; i < upper_border / 8; i++) {
776                 upper_border_ip->v6.s6_addr[olsr_cnf->ipsize - i - 1] = 0;
777     }
778     upper_border_ip->v6.s6_addr[olsr_cnf->ipsize - upper_border / 8 -
779                                        1] &= (0xff << (upper_border & 7));
780     upper_border_ip->v6.s6_addr[olsr_cnf->ipsize - upper_border / 8 -
781                                        1] |= (1 << (upper_border & 7));
782   }
783   return 1;
784 }
785
786 /*
787  * Process an incoming TC or TC_LQ message.
788  *
789  * If the message is interesting enough, update our edges for it,
790  * trigger SPF and finally flood it to all our 2way neighbors.
791  *
792  * The order for extracting data off the message does matter, 
793  * as every call to pkt_get increases the packet offset and
794  * hence the spot we are looking at.
795  */
796 void
797 olsr_input_tc(union olsr_message *msg,
798               struct interface *input_if __attribute__ ((unused)),
799               union olsr_ip_addr *from_addr)
800 {
801   struct ipaddr_str buf;
802   olsr_u16_t size, msg_seq, ansn;
803   olsr_u8_t type, ttl, msg_hops, lower_border, upper_border;
804   olsr_reltime vtime;
805   union olsr_ip_addr originator;
806   const unsigned char *limit, *curr;
807   struct tc_entry *tc;
808
809   union olsr_ip_addr lower_border_ip, upper_border_ip;
810   int borderSet = 0;
811
812   curr = (void *)msg;
813   if (!msg) {
814     return;
815   }
816
817   /* We are only interested in TC message types. */
818   pkt_get_u8(&curr, &type);
819   if ((type != LQ_TC_MESSAGE) && (type != TC_MESSAGE)) {
820     return;
821   }
822
823   pkt_get_reltime(&curr, &vtime);
824   pkt_get_u16(&curr, &size);
825
826   pkt_get_ipaddress(&curr, &originator);
827
828   /* Copy header values */
829   pkt_get_u8(&curr, &ttl);
830   pkt_get_u8(&curr, &msg_hops);
831   pkt_get_u16(&curr, &msg_seq);
832   pkt_get_u16(&curr, &ansn);
833
834   /* Get borders */
835   pkt_get_u8(&curr, &lower_border);
836   pkt_get_u8(&curr, &upper_border);
837
838   tc = olsr_lookup_tc_entry(&originator);
839
840   if (tc && 0 != tc->edge_tree.count) {
841     if (olsr_seq_inrange_high((int)tc->msg_seq - TC_SEQNO_WINDOW,
842                               tc->msg_seq,
843                               msg_seq) &&
844         olsr_seq_inrange_high((int)tc->ansn - TC_ANSN_WINDOW, tc->ansn, ansn)) {
845
846       /*
847        * Ignore already seen seq/ansn values (small window for mesh memory)
848        */
849       if ((tc->msg_seq == msg_seq) || (tc->ignored++ < 32)) {
850         return;
851       }
852
853       OLSR_PRINTF(1, "Ignored to much LQTC's for %s, restarting\n",
854                   olsr_ip_to_string(&buf, &originator));
855
856     } else
857       if (!olsr_seq_inrange_high
858           (tc->msg_seq,
859            (int)tc->msg_seq + TC_SEQNO_WINDOW * TC_SEQNO_WINDOW_MULT, msg_seq)
860           || !olsr_seq_inrange_low(tc->ansn,
861                                    (int)tc->ansn +
862                                    TC_ANSN_WINDOW * TC_ANSN_WINDOW_MULT,
863                                    ansn)) {
864
865       /*
866        * Only accept future seq/ansn values (large window for node reconnects).
867        * Restart in all other cases. Ignore a single stray message.
868        */
869       if (!tc->err_seq_valid) {
870         tc->err_seq = msg_seq;
871         tc->err_seq_valid = OLSR_TRUE;
872       }
873       if (tc->err_seq == msg_seq) {
874         return;
875       }
876
877       OLSR_PRINTF(2, "Detected node restart for %s\n",
878                   olsr_ip_to_string(&buf, &originator));
879     }
880   }
881
882   /*
883    * Generate a new tc_entry in the lsdb and store the sequence number.
884    */
885   if (!tc) {
886     tc = olsr_add_tc_entry(&originator);
887   }
888
889   /*
890    * Update the tc entry.
891    */
892   tc->msg_hops = msg_hops;
893   tc->msg_seq = msg_seq;
894   tc->ansn = ansn;
895   tc->ignored = 0;
896   tc->err_seq_valid = OLSR_FALSE;
897
898   /*
899    * If the sender interface (NB: not originator) of this message
900    * is not in the symmetric 1-hop neighborhood of this node, the
901    * message MUST be discarded.
902    */
903   if (check_neighbor_link(from_addr) != SYM_LINK) {
904     OLSR_PRINTF(2, "Received TC from NON SYM neighbor %s\n",
905                 olsr_ip_to_string(&buf, from_addr));
906     return;
907   }
908
909   OLSR_PRINTF(1, "Processing TC from %s, seq 0x%04x\n",
910               olsr_ip_to_string(&buf, &originator), tc->msg_seq);
911
912   /*
913    * Now walk the edge advertisements contained in the packet.
914    */
915
916   limit = (unsigned char *)msg + size;
917   borderSet = 0;
918   while (curr < limit) {
919     if (olsr_tc_update_edge(tc, ansn, &curr, &upper_border_ip)) {
920       changes_topology = OLSR_TRUE;
921     }
922
923     if (!borderSet) {
924       borderSet = 1;
925       memcpy(&lower_border_ip, &upper_border_ip, sizeof(lower_border_ip));
926     }
927   }
928
929   /*
930    * Calculate real border IPs.
931    */
932   if (borderSet) {
933     borderSet = olsr_calculate_tc_border(lower_border, &lower_border_ip,
934                                          upper_border, &upper_border_ip);
935   }
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  */