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