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