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