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