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