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