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