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