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