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