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