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