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