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