ca6176d4c84b279bed9696baabf9816559fe5b00
[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 /* the first 32 TCs are without Fisheye */
67 static int ttl_index = -32;
68
69 static uint16_t local_ansn_number = 0;
70
71 static void olsr_cleanup_tc_entry(struct tc_entry *tc);
72
73 /**
74  * Add a new tc_entry to the tc tree
75  *
76  * @param (last)adr address of the entry
77  * @return a pointer to the created entry
78  */
79 static struct tc_entry *
80 olsr_add_tc_entry(const union olsr_ip_addr *adr)
81 {
82 #if !defined REMOVE_LOG_DEBUG
83   struct ipaddr_str buf;
84 #endif
85   struct tc_entry *tc;
86
87   /*
88    * Safety net against loss of the last main IP address.
89    */
90   if (olsr_ipcmp(&olsr_cnf->router_id, &all_zero) == 0) {
91     return NULL;
92   }
93
94   OLSR_DEBUG(LOG_TC, "TC: add entry %s\n", olsr_ip_to_string(&buf, adr));
95
96   tc = olsr_cookie_malloc(tc_mem_cookie);
97   if (!tc) {
98     return NULL;
99   }
100
101   /* Fill entry */
102   tc->addr = *adr;
103   tc->vertex_node.key = &tc->addr;
104
105   tc->mid_seq = -1;
106   tc->hna_seq = -1;
107   tc->tc_seq = -1;
108   /*
109    * Insert into the global tc tree.
110    */
111   avl_insert(&tc_tree, &tc->vertex_node, false);
112   olsr_lock_tc_entry(tc);
113
114   /*
115    * Initialize subtrees for edges, prefixes, HNAs and MIDs.
116    */
117   avl_init(&tc->edge_tree, avl_comp_default);
118   avl_init(&tc->prefix_tree, avl_comp_prefix_origin_default);
119   avl_init(&tc->mid_tree, avl_comp_default);
120   avl_init(&tc->hna_tree, avl_comp_prefix_default);
121
122   /*
123    * Add a rt_path for ourselves.
124    */
125   olsr_insert_routing_table(adr, 8 * olsr_cnf->ipsize, adr, OLSR_RT_ORIGIN_TC);
126
127   return tc;
128 }
129
130 /**
131  * Initialize the topology set
132  *
133  */
134 void
135 olsr_init_tc(void)
136 {
137   OLSR_INFO(LOG_TC, "Initialize topology set...\n");
138
139   avl_init(&tc_tree, avl_comp_default);
140
141   /*
142    * Get some cookies for getting stats to ease troubleshooting.
143    */
144   tc_edge_gc_timer_cookie = olsr_alloc_cookie("TC edge GC", OLSR_COOKIE_TYPE_TIMER);
145   tc_validity_timer_cookie = olsr_alloc_cookie("TC validity", OLSR_COOKIE_TYPE_TIMER);
146   spf_backoff_timer_cookie = olsr_alloc_cookie("SPF backoff", OLSR_COOKIE_TYPE_TIMER);
147
148   tc_mem_cookie = olsr_alloc_cookie("tc_entry", OLSR_COOKIE_TYPE_MEMORY);
149   olsr_cookie_set_memory_size(tc_mem_cookie, sizeof(struct tc_entry));
150 }
151
152 /**
153  * The main ip address has changed.
154  * Do the needful.
155  */
156 void
157 olsr_change_myself_tc(void)
158 {
159   struct link_entry *entry;
160   bool main_ip_change = false;
161
162   if (tc_myself) {
163
164     /*
165      * Check if there was a change.
166      */
167     if (olsr_ipcmp(&tc_myself->addr, &olsr_cnf->router_id) == 0) {
168       return;
169     }
170
171     /*
172      * Flush our own tc_entry.
173      */
174     olsr_delete_tc_entry(tc_myself);
175
176     /*
177      * Clear the reference.
178      */
179     olsr_unlock_tc_entry(tc_myself);
180     tc_myself = NULL;
181
182     main_ip_change = true;
183   }
184
185   /*
186    * The old entry for ourselves is gone, generate a new one and trigger SPF.
187    */
188   tc_myself = olsr_add_tc_entry(&olsr_cnf->router_id);
189   olsr_lock_tc_entry(tc_myself);
190
191   OLSR_FOR_ALL_LINK_ENTRIES(entry) {
192
193     /**
194      * check if a main ip change destroyed our TC entries
195      */
196     if (main_ip_change || entry->link_tc_edge == NULL) {
197       struct nbr_entry *ne = entry->neighbor;
198       entry->link_tc_edge = olsr_add_tc_edge_entry(tc_myself, &ne->nbr_addr, 0);
199     }
200   } OLSR_FOR_ALL_LINK_ENTRIES_END(link);
201   changes_topology = true;
202 }
203
204 /**
205  * Attempts to delete a tc entry. This will work unless there are virtual edges left
206  * that cannot be removed
207  *
208  * @param entry the TC entry to delete
209  *
210  */
211 void
212 olsr_delete_tc_entry(struct tc_entry *tc)
213 {
214   struct tc_edge_entry *tc_edge;
215
216 #if !defined REMOVE_LOG_DEBUG
217   struct ipaddr_str buf;
218 #endif
219   OLSR_DEBUG(LOG_TC, "TC: del entry %s %u %s\n", olsr_ip_to_string(&buf, &tc->addr),
220       tc->edge_tree.count, tc->is_virtual ? "true" : "false");
221
222   /* we don't want to keep this node */
223   tc->is_virtual = true;
224
225   if (tc->edge_tree.count == 0) {
226     olsr_cleanup_tc_entry(tc);
227     return;
228   }
229   /* The delete all non-virtual edges, the last one will clean up the tc if possible */
230   OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
231     /* we don't need this edge for the tc, so let's try to remove it */
232     olsr_delete_tc_edge_entry(tc_edge);
233   } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END();
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 #if !defined(REMOVE_LOG_DEBUG)
245   struct ipaddr_str buf;
246 #endif
247   OLSR_DEBUG(LOG_TC, "TC: del entry %s %u\n", olsr_ip_to_string(&buf, &tc->addr), tc->refcount);
248   assert (tc->edge_tree.count == 0);
249
250   OLSR_FOR_ALL_PREFIX_ENTRIES(tc, rtp) {
251     olsr_delete_rt_path(rtp);
252   } OLSR_FOR_ALL_PREFIX_ENTRIES_END();
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, true);
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 (1 && 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  * @return true if the tc entry was deleted, false otherwise
462  */
463 void
464 olsr_delete_tc_edge_entry(struct tc_edge_entry *tc_edge)
465 {
466   struct tc_entry *tc;
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->is_virtual = 1;
473
474   tc_edge_inv = tc_edge->edge_inv;
475   if (tc_edge_inv != NULL && tc_edge_inv->is_virtual == 0) {
476     OLSR_DEBUG(LOG_TC, "TC: mark edge entry %s\n", olsr_tc_edge_to_string(tc_edge));
477     return;
478   }
479
480   OLSR_DEBUG(LOG_TC, "TC: del edge entry %s\n", olsr_tc_edge_to_string(tc_edge));
481
482   /*
483    * Clear the backpointer of our inverse edge.
484    */
485   if (tc_edge_inv) {
486     /* split the two edges */
487     tc_edge_inv->edge_inv = NULL;
488     tc_edge->edge_inv = NULL;
489
490     if (tc_edge_inv->is_virtual) {
491       /* remove the other side too because it's a virtual link */
492       olsr_delete_tc_edge_entry(tc_edge_inv);
493     }
494   }
495
496   tc = tc_edge->tc;
497
498   /* remove edge from tc FIRST */
499   avl_delete(&tc->edge_tree, &tc_edge->edge_node);
500   OLSR_DEBUG(LOG_TC, "TC: %s down to %d edges\n", olsr_ip_to_string(&buf, &tc->addr), tc->edge_tree.count);
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   olsr_unlock_tc_entry(tc);
508   olsr_free_tc_edge_entry(tc_edge);
509 }
510
511 /**
512  * Delete all destinations that have a lower ANSN.
513  *
514  * @param tc the entry to delete edges from
515  * @return TRUE if any destinations were deleted, FALSE if not
516  */
517 static bool
518 delete_outdated_tc_edges(struct tc_entry *tc)
519 {
520   struct tc_edge_entry *tc_edge;
521   bool retval = false;
522
523   OLSR_DEBUG(LOG_TC, "TC: deleting outdated TC-edge entries\n");
524
525   OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
526     if (SEQNO_GREATER_THAN(tc->ansn, tc_edge->ansn)) {
527       olsr_delete_tc_edge_entry(tc_edge);
528       retval = true;
529     }
530   }
531   OLSR_FOR_ALL_TC_EDGE_ENTRIES_END();
532
533   if (retval)
534     changes_topology = true;
535   return retval;
536 }
537
538 /**
539  * Delete all destinations that are inside the borders but
540  * not updated in the last tc.
541  *
542  * @param tc the entry to delete edges from
543  * @param ansn the advertised neighbor set sequence number
544  * @return 1 if any destinations were deleted 0 if not
545  */
546 static int
547 olsr_delete_revoked_tc_edges(struct tc_entry *tc, uint16_t ansn, union olsr_ip_addr *lower_border, union olsr_ip_addr *upper_border)
548 {
549   struct tc_edge_entry *tc_edge;
550   int retval = 0;
551   bool passedLowerBorder = false;
552
553   OLSR_DEBUG(LOG_TC, "TC: deleting revoked TCs\n");
554
555   OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
556     if (!passedLowerBorder) {
557       if (avl_comp_default(lower_border, &tc_edge->T_dest_addr) <= 0) {
558         passedLowerBorder = true;
559       } else {
560         continue;
561       }
562     }
563
564     if (passedLowerBorder) {
565       if (avl_comp_default(upper_border, &tc_edge->T_dest_addr) <= 0) {
566         break;
567       }
568     }
569
570     if (SEQNO_GREATER_THAN(ansn, tc_edge->ansn)) {
571       olsr_delete_tc_edge_entry(tc_edge);
572       retval = 1;
573     }
574   }
575   OLSR_FOR_ALL_TC_EDGE_ENTRIES_END();
576
577   if (retval)
578     changes_topology = true;
579   return retval;
580 }
581
582
583 /**
584  * Update an edge registered on an entry.
585  * Creates new edge-entries if not registered.
586  * Bases update on a received TC message
587  *
588  * @param entry the TC entry to check
589  * @pkt the TC edge entry in the packet
590  * @return 1 if entries are added 0 if not
591  */
592 static int
593 olsr_tc_update_edge(struct tc_entry *tc, uint16_t ansn, const unsigned char **curr, union olsr_ip_addr *neighbor)
594 {
595   struct tc_edge_entry *tc_edge;
596   int edge_change = 0;
597
598   /*
599    * Fetch the per-edge data
600    */
601   pkt_get_ipaddress(curr, neighbor);
602
603   /* First check if we know this edge */
604   tc_edge = olsr_lookup_tc_edge(tc, neighbor);
605   if (!tc_edge) {
606     /*
607      * Yet unknown - create it.
608      * Check if the address is allowed.
609      */
610     if (!olsr_validate_address(neighbor)) {
611       return 0;
612     }
613
614     tc_edge = olsr_add_tc_edge_entry(tc, neighbor, ansn);
615
616     olsr_deserialize_tc_lq_pair(curr, tc_edge);
617     edge_change = 1;
618   } else {
619     /*
620      * We know this edge - Update entry.
621      */
622     tc_edge->ansn = ansn;
623
624     /*
625      * Update link quality if configured.
626      */
627     olsr_deserialize_tc_lq_pair(curr, tc_edge);
628
629     /*
630      * Update the etx.
631      */
632     if (olsr_calc_tc_edge_entry_etx(tc_edge)) {
633       if (tc->msg_hops <= olsr_cnf->lq_dlimit) {
634         edge_change = 1;
635       }
636     }
637     if (edge_change) {
638       OLSR_DEBUG(LOG_TC, "TC:   chg edge entry %s\n", olsr_tc_edge_to_string(tc_edge));
639     }
640   }
641   tc_edge->is_virtual = 0;
642   tc->is_virtual = false;
643
644   return edge_change;
645 }
646
647 /**
648  * Lookup an edge hanging off a TC entry.
649  *
650  * @param entry the entry to check
651  * @param dst_addr the destination address to check for
652  * @return a pointer to the tc_edge found - or NULL
653  */
654 struct tc_edge_entry *
655 olsr_lookup_tc_edge(struct tc_entry *tc, union olsr_ip_addr *edge_addr)
656 {
657   struct avl_node *edge_node;
658
659   edge_node = avl_find(&tc->edge_tree, edge_addr);
660
661   return edge_node ? edge_tree2tc_edge(edge_node) : NULL;
662 }
663
664 /**
665  * Print the topology table to stdout
666  */
667 void
668 olsr_print_tc_table(void)
669 {
670 #if !defined REMOVE_LOG_INFO
671   /* The whole function makes no sense without it. */
672   struct tc_entry *tc;
673   const int ipwidth = olsr_cnf->ip_version == AF_INET ? 15 : 30;
674
675   OLSR_INFO(LOG_TC, "\n--- %s ------------------------------------------------- TOPOLOGY\n\n", olsr_wallclock_string());
676   OLSR_INFO_NH(LOG_TC, "%-*s %-*s             %8s %8s\n", ipwidth,
677                "Source IP addr", ipwidth, "Dest IP addr", olsr_get_linklabel(0), "(common)");
678
679   OLSR_FOR_ALL_TC_ENTRIES(tc) {
680     struct tc_edge_entry *tc_edge;
681     OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
682       struct ipaddr_str addrbuf, dstaddrbuf;
683       char lqbuffer1[LQTEXT_MAXLENGTH], lqbuffer2[LQTEXT_MAXLENGTH];
684
685       OLSR_INFO_NH(LOG_TC, "%-*s %-*s %-7s      %8s %8s\n",
686                    ipwidth, olsr_ip_to_string(&addrbuf, &tc->addr),
687                    ipwidth, olsr_ip_to_string(&dstaddrbuf,
688                                               &tc_edge->T_dest_addr),
689                    tc_edge->is_virtual ? "virtual" : "",
690                    olsr_get_linkcost_text(tc_edge->cost, false, lqbuffer1, sizeof(lqbuffer1)),
691                    olsr_get_linkcost_text(tc_edge->common_cost, false, lqbuffer2, sizeof(lqbuffer2)));
692
693     } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END();
694   } OLSR_FOR_ALL_TC_ENTRIES_END();
695 #endif
696 }
697
698 /*
699  * calculate the border IPs of a tc edge set according to the border flags
700  *
701  * @param lower border flag
702  * @param pointer to lower border ip
703  * @param upper border flag
704  * @param pointer to upper border ip
705  * @result 1 if lower/upper border ip have been set
706  */
707 static int
708 olsr_calculate_tc_border(uint8_t lower_border,
709                          union olsr_ip_addr *lower_border_ip, uint8_t upper_border, union olsr_ip_addr *upper_border_ip)
710 {
711   if (lower_border == 0 && upper_border == 0) {
712     return 0;
713   }
714   if (lower_border == 0xff) {
715     memset(lower_border_ip, 0, sizeof(lower_border_ip));
716   } else {
717     int i;
718
719     lower_border--;
720     for (i = 0; i < lower_border / 8; i++) {
721       lower_border_ip->v6.s6_addr[olsr_cnf->ipsize - i - 1] = 0;
722     }
723     lower_border_ip->v6.s6_addr[olsr_cnf->ipsize - lower_border / 8 - 1] &= (0xff << (lower_border & 7));
724     lower_border_ip->v6.s6_addr[olsr_cnf->ipsize - lower_border / 8 - 1] |= (1 << (lower_border & 7));
725   }
726
727   if (upper_border == 0xff) {
728     memset(upper_border_ip, 0xff, sizeof(upper_border_ip));
729   } else {
730     int i;
731
732     upper_border--;
733
734     for (i = 0; i < upper_border / 8; i++) {
735       upper_border_ip->v6.s6_addr[olsr_cnf->ipsize - i - 1] = 0;
736     }
737     upper_border_ip->v6.s6_addr[olsr_cnf->ipsize - upper_border / 8 - 1] &= (0xff << (upper_border & 7));
738     upper_border_ip->v6.s6_addr[olsr_cnf->ipsize - upper_border / 8 - 1] |= (1 << (upper_border & 7));
739   }
740   return 1;
741 }
742
743 /*
744  * Process an incoming TC or TC_LQ message.
745  *
746  * If the message is interesting enough, update our edges for it,
747  * trigger SPF and finally flood it to all our 2way neighbors.
748  *
749  * The order for extracting data off the message does matter,
750  * as every call to pkt_get increases the packet offset and
751  * hence the spot we are looking at.
752  */
753 void
754 olsr_input_tc(union olsr_message * msg, struct interface * input_if __attribute__ ((unused)),
755     union olsr_ip_addr * from_addr, enum duplicate_status status)
756 {
757   uint16_t size, msg_seq, ansn;
758   uint8_t type, ttl, msg_hops, lower_border, upper_border;
759   uint32_t vtime;
760   union olsr_ip_addr originator;
761   const unsigned char *limit, *curr;
762   struct tc_entry *tc;
763   bool relevantTc;
764 #if !defined REMOVE_LOG_DEBUG
765   struct ipaddr_str buf;
766 #endif
767   union olsr_ip_addr lower_border_ip, upper_border_ip;
768   int borderSet = 0;
769
770   curr = (void *)msg;
771
772   /* We are only interested in TC message types. */
773   pkt_get_u8(&curr, &type);
774   if (type != olsr_get_TC_MessageId()) {
775     return;
776   }
777
778   /*
779    * If the sender interface (NB: not originator) of this message
780    * is not in the symmetric 1-hop neighborhood of this node, the
781    * message MUST be discarded.
782    */
783   if (check_neighbor_link(from_addr) != SYM_LINK) {
784     OLSR_DEBUG(LOG_TC, "Received TC from NON SYM neighbor %s\n", olsr_ip_to_string(&buf, from_addr));
785     return;
786   }
787
788   pkt_get_reltime(&curr, &vtime);
789   pkt_get_u16(&curr, &size);
790
791   pkt_get_ipaddress(&curr, &originator);
792
793   /* Copy header values */
794   pkt_get_u8(&curr, &ttl);
795   pkt_get_u8(&curr, &msg_hops);
796   pkt_get_u16(&curr, &msg_seq);
797   pkt_get_u16(&curr, &ansn);
798
799   /* Get borders */
800   pkt_get_u8(&curr, &lower_border);
801   pkt_get_u8(&curr, &upper_border);
802
803   tc = olsr_lookup_tc_entry(&originator);
804
805   /* TCs can be splitted, so we are looking for ANSNs equal or higher */
806   if (tc && status != RESET_SEQNO_OLSR_MESSAGE && tc->tc_seq != -1 && olsr_seqno_diff(ansn, tc->ansn) < 0) {
807     /* this TC is too old, discard it */
808     return;
809   }
810
811   /*
812    * Generate a new tc_entry in the lsdb and store the sequence number.
813    */
814   if (!tc) {
815     tc = olsr_add_tc_entry(&originator);
816   }
817
818   /*
819    * Update the tc entry.
820    */
821   tc->msg_hops = msg_hops;
822   tc->tc_seq = msg_seq;
823   tc->ansn = ansn;
824   tc->ignored = 0;
825   tc->err_seq_valid = false;
826   tc->is_virtual = false;
827
828   OLSR_DEBUG(LOG_TC, "Processing TC from %s, seq 0x%04x\n", olsr_ip_to_string(&buf, &originator), tc->tc_seq);
829
830   /*
831    * Now walk the edge advertisements contained in the packet.
832    */
833
834   limit = (unsigned char *)msg + size;
835   borderSet = 0;
836   relevantTc = false;
837   while (curr + olsr_cnf->ipsize + olsr_sizeof_TCLQ() <= limit) {
838     if (olsr_tc_update_edge(tc, ansn, &curr, &upper_border_ip)) {
839       relevantTc = true;
840     }
841
842     if (!borderSet) {
843       borderSet = 1;
844       memcpy(&lower_border_ip, &upper_border_ip, sizeof(lower_border_ip));
845     }
846   }
847
848   if (relevantTc) {
849     relevantTcCount++;
850     changes_topology = true;
851   }
852
853   /*
854    * Calculate real border IPs.
855    */
856   if (borderSet) {
857     borderSet = olsr_calculate_tc_border(lower_border, &lower_border_ip, upper_border, &upper_border_ip);
858   }
859
860   /*
861    * Set or change the expiration timer accordingly.
862    */
863   olsr_set_timer(&tc->validity_timer, vtime,
864                  OLSR_TC_VTIME_JITTER, OLSR_TIMER_ONESHOT, &olsr_expire_tc_entry, tc, tc_validity_timer_cookie);
865
866   if (borderSet) {
867
868     /*
869      * Delete all old tc edges within borders.
870      */
871     olsr_delete_revoked_tc_edges(tc, ansn, &lower_border_ip, &upper_border_ip);
872   } else {
873
874     /*
875      * Kick the the edge garbage collection timer. In the meantime hopefully
876      * all edges belonging to a multipart neighbor set will arrive.
877      */
878     olsr_set_timer(&tc->edge_gc_timer, OLSR_TC_EDGE_GC_TIME,
879                    OLSR_TC_EDGE_GC_JITTER, OLSR_TIMER_ONESHOT, &olsr_expire_tc_edge_gc, tc, tc_edge_gc_timer_cookie);
880   }
881 }
882
883 uint32_t
884 getRelevantTcCount(void)
885 {
886   return relevantTcCount;
887 }
888
889 void
890 olsr_delete_all_tc_entries(void) {
891   struct tc_entry *tc;
892   struct link_entry *link;
893
894   /* then remove all tc entries */
895   OLSR_FOR_ALL_TC_ENTRIES(tc) {
896     tc->is_virtual = 0;
897   } OLSR_FOR_ALL_TC_ENTRIES_END(tc)
898
899   OLSR_FOR_ALL_TC_ENTRIES(tc) {
900     if (tc != tc_myself) {
901       olsr_delete_tc_entry(tc);
902     }
903   } OLSR_FOR_ALL_TC_ENTRIES_END(tc)
904
905   /* kill all references in link_set */
906   OLSR_FOR_ALL_LINK_ENTRIES(link) {
907     link->link_tc_edge = NULL;
908   } OLSR_FOR_ALL_LINK_ENTRIES_END(link)
909
910
911   /* kill tc_myself */
912   if (tc_myself) {
913     olsr_delete_tc_entry(tc_myself);
914     olsr_unlock_tc_entry(tc_myself);
915     tc_myself = NULL;
916   }
917 }
918
919 static uint8_t
920 calculate_border_flag(void *lower_border, void *higher_border)
921 {
922   uint8_t *lower = lower_border;
923   uint8_t *higher = higher_border;
924   uint8_t bitmask;
925   uint8_t part, bitpos;
926
927   for (part = 0; part < olsr_cnf->ipsize; part++) {
928     if (lower[part] != higher[part]) {
929       break;
930     }
931   }
932
933   if (part == olsr_cnf->ipsize) {       // same IPs ?
934     return 0;
935   }
936   // look for first bit of difference
937   bitmask = 0xfe;
938   for (bitpos = 0; bitpos < 8; bitpos++, bitmask <<= 1) {
939     if ((lower[part] & bitmask) == (higher[part] & bitmask)) {
940       break;
941     }
942   }
943
944   bitpos += 8 * (olsr_cnf->ipsize - part - 1);
945   return bitpos + 1;
946 }
947
948 uint16_t
949 get_local_ansn_number(void) {
950   return local_ansn_number;
951 }
952
953 void
954 increase_local_ansn_number(void) {
955   local_ansn_number++;
956 }
957
958 static bool
959 olsr_output_lq_tc_internal(void *ctx  __attribute__ ((unused)), union olsr_ip_addr *nextIp, bool skip)
960 {
961   static int ttl_list[] = { 2, 8, 2, 16, 2, 8, 2, MAX_TTL };
962   struct interface *ifp;
963   struct nbr_entry *nbr;
964   struct link_entry *link;
965   uint8_t msg_buffer[MAXMESSAGESIZE - OLSR_HEADERSIZE] __attribute__ ((aligned));
966   uint8_t *curr = msg_buffer;
967   uint8_t *length_field, *border_flags, *seqno, *last;
968   bool sendTC = false, nextFragment = false;
969   uint8_t ttl = 255;
970
971   OLSR_INFO(LOG_PACKET_CREATION, "Building TC\n-------------------\n");
972
973   pkt_put_u8(&curr, olsr_get_TC_MessageId());
974   pkt_put_reltime(&curr, olsr_cnf->tc_params.validity_time);
975
976   length_field = curr;
977   pkt_put_u16(&curr, 0); /* put in real messagesize later */
978
979   pkt_put_ipaddress(&curr, &olsr_cnf->router_id);
980
981   if (olsr_cnf->lq_fish > 0) {
982     /* handle fisheye */
983     ttl_index++;
984     if (ttl_index >= (int)ARRAYSIZE(ttl_list)) {
985       ttl_index = 0;
986     }
987     if (ttl_index >= 0) {
988       ttl = ttl_list[ttl_index];
989     }
990   }
991   pkt_put_u8(&curr, ttl);
992
993   /* hopcount */
994   pkt_put_u8(&curr, 0);
995
996   /* reserve sequence number lazy */
997   seqno = curr;
998   pkt_put_u16(&curr, 0);
999   pkt_put_u16(&curr, get_local_ansn_number());
1000
1001   /* border flags */
1002   border_flags = curr;
1003   pkt_put_u16(&curr, 0xffff);
1004
1005   last = msg_buffer + sizeof(msg_buffer) - olsr_cnf->ipsize - olsr_sizeof_TCLQ();
1006
1007   OLSR_FOR_ALL_NBR_ENTRIES(nbr) {
1008     /* allow fragmentation */
1009     if (skip) {
1010       struct nbr_entry *prevNbr;
1011       if (olsr_ipcmp(&nbr->nbr_addr, nextIp) != 0) {
1012         continue;
1013       }
1014       skip = false;
1015
1016       /* rewrite lower border flag */
1017       prevNbr = nbr_node_to_nbr(nbr->nbr_node.prev);
1018       *border_flags = calculate_border_flag(&prevNbr->nbr_addr, &nbr->nbr_addr);
1019     }
1020
1021     /* too long ? */
1022     if (curr > last) {
1023       /* rewrite upper border flag */
1024       struct nbr_entry *prevNbr = nbr_node_to_nbr(nbr->nbr_node.prev);
1025
1026       *(border_flags+1) = calculate_border_flag(&prevNbr->nbr_addr, &nbr->nbr_addr);
1027       *nextIp = nbr->nbr_addr;
1028       nextFragment = true;
1029       break;
1030     }
1031
1032     /*
1033      * TC redundancy 2
1034      *
1035      * Only consider symmetric neighbours.
1036      */
1037     if (!nbr->is_sym) {
1038       continue;
1039     }
1040
1041     /*
1042      * TC redundancy 1
1043      *
1044      * Only consider MPRs and MPR selectors
1045      */
1046     if (olsr_cnf->tc_redundancy == 1 && !nbr->is_mpr && nbr->mprs_count == 0) {
1047       continue;
1048     }
1049
1050     /*
1051      * TC redundancy 0
1052      *
1053      * Only consider MPR selectors
1054      */
1055     if (olsr_cnf->tc_redundancy == 0 && nbr->mprs_count == 0) {
1056       continue;
1057     }
1058
1059     /* Set the entry's link quality */
1060     link = get_best_link_to_neighbor(&nbr->nbr_addr);
1061     if (!link) {
1062       /* no link ? */
1063       continue;
1064     }
1065
1066     if (link->linkcost >= LINK_COST_BROKEN) {
1067       /* don't advertisebroken links */
1068       continue;
1069     }
1070
1071     pkt_put_ipaddress(&curr, &nbr->nbr_addr);
1072     olsr_serialize_tc_lq(&curr, link);
1073
1074     sendTC = true;
1075   } OLSR_FOR_ALL_NBR_ENTRIES_END()
1076
1077   if (!sendTC && skip) {
1078     OLSR_DEBUG(LOG_TC, "Nothing to send for this TC...\n");
1079     return false;
1080   }
1081
1082   /* late initialization of length and sequence number */
1083   pkt_put_u16(&seqno, get_msg_seqno());
1084   pkt_put_u16(&length_field, curr - msg_buffer);
1085
1086   /* send to all interfaces */
1087   OLSR_FOR_ALL_INTERFACES(ifp) {
1088     if (net_outbuffer_bytes_left(ifp) < curr - msg_buffer) {
1089       net_output(ifp);
1090       set_buffer_timer(ifp);
1091     }
1092     net_outbuffer_push(ifp, msg_buffer, curr - msg_buffer);
1093   } OLSR_FOR_ALL_INTERFACES_END(ifp)
1094   return nextFragment;
1095 }
1096
1097 void
1098 olsr_output_lq_tc(void *ctx) {
1099   union olsr_ip_addr next;
1100   bool skip = false;
1101
1102   memset(&next, 0, sizeof(next));
1103
1104   while ((skip = olsr_output_lq_tc_internal(ctx, &next, skip)));
1105 }
1106
1107 /*
1108  * Local Variables:
1109  * c-basic-offset: 2
1110  * indent-tabs-mode: nil
1111  * End:
1112  */