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