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