Lots of work, no result
[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 #if 0
708 static int
709 olsr_calculate_tc_border(uint8_t lower_border,
710                          union olsr_ip_addr *lower_border_ip, uint8_t upper_border, union olsr_ip_addr *upper_border_ip)
711 {
712   if (lower_border == 0 && upper_border == 0) {
713     return 0;
714   }
715   if (lower_border == 0xff) {
716     memset(lower_border_ip, 0, sizeof(*lower_border_ip));
717   } else {
718     int i;
719
720     lower_border--;
721     for (i = 0; i < lower_border / 8; i++) {
722       lower_border_ip->v6.s6_addr[olsr_cnf->ipsize - i - 1] = 0;
723     }
724     lower_border_ip->v6.s6_addr[olsr_cnf->ipsize - lower_border / 8 - 1] &= (0xff << (lower_border & 7));
725     lower_border_ip->v6.s6_addr[olsr_cnf->ipsize - lower_border / 8 - 1] |= (1 << (lower_border & 7));
726   }
727
728   if (upper_border == 0xff) {
729     memset(upper_border_ip, 0xff, sizeof(*upper_border_ip));
730   } else {
731     int i;
732
733     upper_border--;
734
735     for (i = 0; i < upper_border / 8; i++) {
736       upper_border_ip->v6.s6_addr[olsr_cnf->ipsize - i - 1] = 0;
737     }
738     upper_border_ip->v6.s6_addr[olsr_cnf->ipsize - upper_border / 8 - 1] &= (0xff << (upper_border & 7));
739     upper_border_ip->v6.s6_addr[olsr_cnf->ipsize - upper_border / 8 - 1] |= (1 << (upper_border & 7));
740   }
741   return 1;
742 }
743 #endif
744 /*
745  * Process an incoming TC or TC_LQ message.
746  *
747  * If the message is interesting enough, update our edges for it,
748  * trigger SPF and finally flood it to all our 2way neighbors.
749  *
750  * The order for extracting data off the message does matter,
751  * as every call to pkt_get increases the packet offset and
752  * hence the spot we are looking at.
753  */
754
755 void
756 olsr_input_tc(struct olsr_message * msg, const uint8_t *payload, const uint8_t *end,
757     struct interface * input_if __attribute__ ((unused)),
758     union olsr_ip_addr * from_addr, enum duplicate_status status)
759 {
760   uint16_t ansn;
761   uint8_t lower_border, upper_border;
762   const uint8_t *curr;
763   struct tc_entry *tc;
764   bool relevantTc;
765 #if !defined REMOVE_LOG_DEBUG
766   struct ipaddr_str buf;
767 #endif
768   union olsr_ip_addr lower_border_ip, upper_border_ip;
769   int borderSet = 0;
770
771   /* We are only interested in TC message types. */
772   if (msg->type != olsr_get_TC_MessageId()) {
773     return;
774   }
775
776   /*
777    * If the sender interface (NB: not originator) of this message
778    * is not in the symmetric 1-hop neighborhood of this node, the
779    * message MUST be discarded.
780    */
781   if (check_neighbor_link(from_addr) != SYM_LINK) {
782     OLSR_DEBUG(LOG_TC, "Received TC from NON SYM neighbor %s\n", olsr_ip_to_string(&buf, from_addr));
783     return;
784   }
785
786   curr = payload;
787   pkt_get_u16(&curr, &ansn);
788
789   /* Get borders */
790   pkt_get_u8(&curr, &lower_border);
791   pkt_get_u8(&curr, &upper_border);
792
793   tc = olsr_lookup_tc_entry(&msg->originator);
794
795   /* TCs can be splitted, so we are looking for ANSNs equal or higher */
796   if (tc && status != RESET_SEQNO_OLSR_MESSAGE && tc->tc_seq != -1 && olsr_seqno_diff(ansn, tc->ansn) < 0) {
797     /* this TC is too old, discard it */
798     return;
799   }
800
801   /*
802    * Generate a new tc_entry in the lsdb and store the sequence number.
803    */
804   if (!tc) {
805     tc = olsr_add_tc_entry(&msg->originator);
806   }
807
808   /*
809    * Update the tc entry.
810    */
811   tc->msg_hops = msg->hopcnt;
812   tc->tc_seq = msg->seqno;
813   tc->ansn = ansn;
814   tc->ignored = 0;
815   tc->err_seq_valid = false;
816   tc->is_virtual = false;
817
818   OLSR_DEBUG(LOG_TC, "Processing TC from %s, seq 0x%04x\n", olsr_ip_to_string(&buf, &msg->originator), tc->tc_seq);
819
820   /*
821    * Now walk the edge advertisements contained in the packet.
822    */
823
824   borderSet = 0;
825   relevantTc = false;
826   while (curr + olsr_cnf->ipsize + olsr_sizeof_TCLQ() <= end) {
827     if (olsr_tc_update_edge(tc, ansn, &curr, &upper_border_ip)) {
828       relevantTc = true;
829     }
830
831     if (!borderSet) {
832       borderSet = 1;
833       memcpy(&lower_border_ip, &upper_border_ip, sizeof(lower_border_ip));
834     }
835   }
836
837   if (relevantTc) {
838     relevantTcCount++;
839     changes_topology = true;
840   }
841
842   /*
843    * Calculate real border IPs.
844    */
845   assert(msg);
846   if (borderSet) {
847     // borderSet = olsr_calculate_tc_border(lower_border, &lower_border_ip, upper_border, &upper_border_ip);
848   }
849
850   /*
851    * Set or change the expiration timer accordingly.
852    */
853   assert(msg);
854   olsr_set_timer(&tc->validity_timer, msg->vtime,
855                  OLSR_TC_VTIME_JITTER, OLSR_TIMER_ONESHOT, &olsr_expire_tc_entry, tc, tc_validity_timer_cookie);
856
857   if (borderSet) {
858
859     /*
860      * Delete all old tc edges within borders.
861      */
862     olsr_delete_revoked_tc_edges(tc, ansn, &lower_border_ip, &upper_border_ip);
863   } else {
864
865     /*
866      * Kick the the edge garbage collection timer. In the meantime hopefully
867      * all edges belonging to a multipart neighbor set will arrive.
868      */
869     olsr_set_timer(&tc->edge_gc_timer, OLSR_TC_EDGE_GC_TIME,
870                    OLSR_TC_EDGE_GC_JITTER, OLSR_TIMER_ONESHOT, &olsr_expire_tc_edge_gc, tc, tc_edge_gc_timer_cookie);
871   }
872 }
873
874 uint32_t
875 getRelevantTcCount(void)
876 {
877   return relevantTcCount;
878 }
879
880 void
881 olsr_delete_all_tc_entries(void) {
882   struct tc_entry *tc;
883   struct link_entry *link;
884
885   /* then remove all tc entries */
886   OLSR_FOR_ALL_TC_ENTRIES(tc) {
887     tc->is_virtual = 0;
888   } OLSR_FOR_ALL_TC_ENTRIES_END(tc)
889
890   OLSR_FOR_ALL_TC_ENTRIES(tc) {
891     if (tc != tc_myself) {
892       olsr_delete_tc_entry(tc);
893     }
894   } OLSR_FOR_ALL_TC_ENTRIES_END(tc)
895
896   /* kill all references in link_set */
897   OLSR_FOR_ALL_LINK_ENTRIES(link) {
898     link->link_tc_edge = NULL;
899   } OLSR_FOR_ALL_LINK_ENTRIES_END(link)
900
901
902   /* kill tc_myself */
903   if (tc_myself) {
904     olsr_delete_tc_entry(tc_myself);
905     olsr_unlock_tc_entry(tc_myself);
906     tc_myself = NULL;
907   }
908 }
909
910 static uint8_t
911 calculate_border_flag(void *lower_border, void *higher_border)
912 {
913   uint8_t *lower = lower_border;
914   uint8_t *higher = higher_border;
915   uint8_t bitmask;
916   uint8_t part, bitpos;
917
918   for (part = 0; part < olsr_cnf->ipsize; part++) {
919     if (lower[part] != higher[part]) {
920       break;
921     }
922   }
923
924   if (part == olsr_cnf->ipsize) {       // same IPs ?
925     return 0;
926   }
927   // look for first bit of difference
928   bitmask = 0xfe;
929   for (bitpos = 0; bitpos < 8; bitpos++, bitmask <<= 1) {
930     if ((lower[part] & bitmask) == (higher[part] & bitmask)) {
931       break;
932     }
933   }
934
935   bitpos += 8 * (olsr_cnf->ipsize - part - 1);
936   return bitpos + 1;
937 }
938
939 uint16_t
940 get_local_ansn_number(void) {
941   return local_ansn_number;
942 }
943
944 void
945 increase_local_ansn_number(void) {
946   local_ansn_number++;
947 }
948
949 static bool
950 olsr_output_lq_tc_internal(void *ctx  __attribute__ ((unused)), union olsr_ip_addr *nextIp, bool skip)
951 {
952   static int ttl_list[] = { 2, 8, 2, 16, 2, 8, 2, MAX_TTL };
953   struct interface *ifp;
954   struct nbr_entry *nbr;
955   struct link_entry *link;
956   uint8_t msg_buffer[MAXMESSAGESIZE - OLSR_HEADERSIZE] __attribute__ ((aligned));
957   uint8_t *curr = msg_buffer;
958   uint8_t *length_field, *border_flags, *seqno, *last;
959   bool sendTC = false, nextFragment = false;
960   uint8_t ttl = 255;
961
962   OLSR_INFO(LOG_PACKET_CREATION, "Building TC\n-------------------\n");
963
964   pkt_put_u8(&curr, olsr_get_TC_MessageId());
965   pkt_put_reltime(&curr, olsr_cnf->tc_params.validity_time);
966
967   length_field = curr;
968   pkt_put_u16(&curr, 0); /* put in real messagesize later */
969
970   pkt_put_ipaddress(&curr, &olsr_cnf->router_id);
971
972   if (olsr_cnf->lq_fish > 0) {
973     /* handle fisheye */
974     ttl_index++;
975     if (ttl_index >= (int)ARRAYSIZE(ttl_list)) {
976       ttl_index = 0;
977     }
978     if (ttl_index >= 0) {
979       ttl = ttl_list[ttl_index];
980     }
981   }
982   pkt_put_u8(&curr, ttl);
983
984   /* hopcount */
985   pkt_put_u8(&curr, 0);
986
987   /* reserve sequence number lazy */
988   seqno = curr;
989   pkt_put_u16(&curr, 0);
990   pkt_put_u16(&curr, get_local_ansn_number());
991
992   /* border flags */
993   border_flags = curr;
994   pkt_put_u16(&curr, 0xffff);
995
996   last = msg_buffer + sizeof(msg_buffer) - olsr_cnf->ipsize - olsr_sizeof_TCLQ();
997
998   OLSR_FOR_ALL_NBR_ENTRIES(nbr) {
999     /* allow fragmentation */
1000     if (skip) {
1001       struct nbr_entry *prevNbr;
1002       if (olsr_ipcmp(&nbr->nbr_addr, nextIp) != 0) {
1003         continue;
1004       }
1005       skip = false;
1006
1007       /* rewrite lower border flag */
1008       prevNbr = nbr_node_to_nbr(nbr->nbr_node.prev);
1009       *border_flags = calculate_border_flag(&prevNbr->nbr_addr, &nbr->nbr_addr);
1010     }
1011
1012     /* too long ? */
1013     if (curr > last) {
1014       /* rewrite upper border flag */
1015       struct nbr_entry *prevNbr = nbr_node_to_nbr(nbr->nbr_node.prev);
1016
1017       *(border_flags+1) = calculate_border_flag(&prevNbr->nbr_addr, &nbr->nbr_addr);
1018       *nextIp = nbr->nbr_addr;
1019       nextFragment = true;
1020       break;
1021     }
1022
1023     /*
1024      * TC redundancy 2
1025      *
1026      * Only consider symmetric neighbours.
1027      */
1028     if (!nbr->is_sym) {
1029       continue;
1030     }
1031
1032     /*
1033      * TC redundancy 1
1034      *
1035      * Only consider MPRs and MPR selectors
1036      */
1037     if (olsr_cnf->tc_redundancy == 1 && !nbr->is_mpr && nbr->mprs_count == 0) {
1038       continue;
1039     }
1040
1041     /*
1042      * TC redundancy 0
1043      *
1044      * Only consider MPR selectors
1045      */
1046     if (olsr_cnf->tc_redundancy == 0 && nbr->mprs_count == 0) {
1047       continue;
1048     }
1049
1050     /* Set the entry's link quality */
1051     link = get_best_link_to_neighbor(&nbr->nbr_addr);
1052     if (!link) {
1053       /* no link ? */
1054       continue;
1055     }
1056
1057     if (link->linkcost >= LINK_COST_BROKEN) {
1058       /* don't advertisebroken links */
1059       continue;
1060     }
1061
1062     pkt_put_ipaddress(&curr, &nbr->nbr_addr);
1063     olsr_serialize_tc_lq(&curr, link);
1064
1065     sendTC = true;
1066   } OLSR_FOR_ALL_NBR_ENTRIES_END()
1067
1068   if (!sendTC && skip) {
1069     OLSR_DEBUG(LOG_TC, "Nothing to send for this TC...\n");
1070     return false;
1071   }
1072
1073   /* late initialization of length and sequence number */
1074   pkt_put_u16(&seqno, get_msg_seqno());
1075   pkt_put_u16(&length_field, curr - msg_buffer);
1076
1077   /* send to all interfaces */
1078   OLSR_FOR_ALL_INTERFACES(ifp) {
1079     if (net_outbuffer_bytes_left(ifp) < curr - msg_buffer) {
1080       net_output(ifp);
1081       set_buffer_timer(ifp);
1082     }
1083     net_outbuffer_push(ifp, msg_buffer, curr - msg_buffer);
1084   } OLSR_FOR_ALL_INTERFACES_END(ifp)
1085   return nextFragment;
1086 }
1087
1088 void
1089 olsr_output_lq_tc(void *ctx) {
1090   union olsr_ip_addr next;
1091   bool skip = false;
1092
1093   memset(&next, 0, sizeof(next));
1094
1095   while ((skip = olsr_output_lq_tc_internal(ctx, &next, skip)));
1096 }
1097
1098 /*
1099  * Local Variables:
1100  * c-basic-offset: 2
1101  * indent-tabs-mode: nil
1102  * End:
1103  */