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