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