Improved duplicate/sequencenumber handling. Small change in message handler callback...
[olsrd.git] / src / tc_set.c
1
2 /*
3  * The olsr.org Optimized Link-State Routing daemon(olsrd)
4  * Copyright (c) 2004-2009, the olsr.org team - see HISTORY file
5  * All rights reserved.
6  *
7  * Redistribution and use in source and binary forms, with or without
8  * modification, are permitted provided that the following conditions
9  * are met:
10  *
11  * * Redistributions of source code must retain the above copyright
12  *   notice, this list of conditions and the following disclaimer.
13  * * Redistributions in binary form must reproduce the above copyright
14  *   notice, this list of conditions and the following disclaimer in
15  *   the documentation and/or other materials provided with the
16  *   distribution.
17  * * Neither the name of olsr.org, olsrd nor the names of its
18  *   contributors may be used to endorse or promote products derived
19  *   from this software without specific prior written permission.
20  *
21  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
24  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
25  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
26  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
27  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
28  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
29  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
31  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
32  * POSSIBILITY OF SUCH DAMAGE.
33  *
34  * Visit http://www.olsr.org for more information.
35  *
36  * If you find this software useful feel free to make a donation
37  * to the project. For more information see the website or contact
38  * the copyright holders.
39  *
40  */
41 #include <assert.h>
42
43 #include "tc_set.h"
44 #include "olsr.h"
45 #include "lq_packet.h"
46 #include "net_olsr.h"
47 #include "link_set.h"
48 #include "mid_set.h"
49 #include "neighbor_table.h"
50 #include "olsr_logging.h"
51
52 static bool delete_outdated_tc_edges(struct tc_entry *);
53
54 /* Root of the link state database */
55 struct avl_tree tc_tree;
56 struct tc_entry *tc_myself = NULL;     /* Shortcut to ourselves */
57
58 /* Some cookies for stats keeping */
59 static struct olsr_cookie_info *tc_edge_gc_timer_cookie = NULL;
60 static struct olsr_cookie_info *tc_validity_timer_cookie = NULL;
61 struct olsr_cookie_info *spf_backoff_timer_cookie = NULL;
62 struct olsr_cookie_info *tc_mem_cookie = NULL;
63
64 static uint32_t relevantTcCount = 0;
65
66 static void olsr_cleanup_tc_entry(struct tc_entry *tc);
67
68 /**
69  * Add a new tc_entry to the tc tree
70  *
71  * @param (last)adr address of the entry
72  * @return a pointer to the created entry
73  */
74 static struct tc_entry *
75 olsr_add_tc_entry(const union olsr_ip_addr *adr)
76 {
77 #if !defined REMOVE_LOG_DEBUG
78   struct ipaddr_str buf;
79 #endif
80   struct tc_entry *tc;
81
82   /*
83    * Safety net against loss of the last main IP address.
84    */
85   if (olsr_ipcmp(&olsr_cnf->router_id, &all_zero) == 0) {
86     return NULL;
87   }
88
89   OLSR_DEBUG(LOG_TC, "TC: add entry %s\n", olsr_ip_to_string(&buf, adr));
90
91   tc = olsr_cookie_malloc(tc_mem_cookie);
92   if (!tc) {
93     return NULL;
94   }
95
96   /* Fill entry */
97   tc->addr = *adr;
98   tc->vertex_node.key = &tc->addr;
99
100   /*
101    * Insert into the global tc tree.
102    */
103   avl_insert(&tc_tree, &tc->vertex_node, AVL_DUP_NO);
104   olsr_lock_tc_entry(tc);
105
106   /*
107    * Initialize subtrees for edges, prefixes, HNAs and MIDs.
108    */
109   avl_init(&tc->edge_tree, avl_comp_default);
110   avl_init(&tc->prefix_tree, avl_comp_prefix_origin_default);
111   avl_init(&tc->mid_tree, avl_comp_default);
112   avl_init(&tc->hna_tree, avl_comp_prefix_default);
113
114   /*
115    * Add a rt_path for ourselves.
116    */
117   olsr_insert_routing_table(adr, 8 * olsr_cnf->ipsize, adr, OLSR_RT_ORIGIN_TC);
118
119   return tc;
120 }
121
122 /**
123  * Initialize the topology set
124  *
125  */
126 void
127 olsr_init_tc(void)
128 {
129   OLSR_INFO(LOG_TC, "Initialize topology set...\n");
130
131   avl_init(&tc_tree, avl_comp_default);
132
133   /*
134    * Get some cookies for getting stats to ease troubleshooting.
135    */
136   tc_edge_gc_timer_cookie = olsr_alloc_cookie("TC edge GC", OLSR_COOKIE_TYPE_TIMER);
137   tc_validity_timer_cookie = olsr_alloc_cookie("TC validity", OLSR_COOKIE_TYPE_TIMER);
138   spf_backoff_timer_cookie = olsr_alloc_cookie("SPF backoff", OLSR_COOKIE_TYPE_TIMER);
139
140   tc_mem_cookie = olsr_alloc_cookie("tc_entry", OLSR_COOKIE_TYPE_MEMORY);
141   olsr_cookie_set_memory_size(tc_mem_cookie, sizeof(struct tc_entry));
142 }
143
144 /**
145  * The main ip address has changed.
146  * Do the needful.
147  */
148 void
149 olsr_change_myself_tc(void)
150 {
151   struct link_entry *entry;
152   bool main_ip_change = false;
153
154   if (tc_myself) {
155
156     /*
157      * Check if there was a change.
158      */
159     if (olsr_ipcmp(&tc_myself->addr, &olsr_cnf->router_id) == 0) {
160       return;
161     }
162
163     /*
164      * Flush our own tc_entry.
165      */
166     olsr_delete_tc_entry(tc_myself);
167
168     /*
169      * Clear the reference.
170      */
171     olsr_unlock_tc_entry(tc_myself);
172     tc_myself = NULL;
173
174     main_ip_change = true;
175   }
176
177   /*
178    * The old entry for ourselves is gone, generate a new one and trigger SPF.
179    */
180   tc_myself = olsr_add_tc_entry(&olsr_cnf->router_id);
181   olsr_lock_tc_entry(tc_myself);
182
183   OLSR_FOR_ALL_LINK_ENTRIES(entry) {
184
185     /**
186      * check if a main ip change destroyed our TC entries
187      */
188     if (main_ip_change || entry->link_tc_edge == NULL) {
189       struct nbr_entry *ne = entry->neighbor;
190       entry->link_tc_edge = olsr_add_tc_edge_entry(tc_myself, &ne->nbr_addr, 0);
191
192       /*
193        * Mark the edge local such that it does not get deleted
194        * during cleanup functions.
195        */
196       entry->link_tc_edge->is_local = 1;
197     }
198   } OLSR_FOR_ALL_LINK_ENTRIES_END(link);
199   changes_topology = true;
200 }
201
202 /**
203  * Attempts to delete a tc entry. This will work unless there are virtual edges left
204  * that cannot be removed
205  *
206  * @param entry the TC entry to delete
207  *
208  */
209 void
210 olsr_delete_tc_entry(struct tc_entry *tc)
211 {
212   struct tc_edge_entry *tc_edge;
213 #if !defined REMOVE_LOG_DEBUG
214   struct ipaddr_str buf;
215 #endif
216   OLSR_DEBUG(LOG_TC, "TC: del entry %s\n", olsr_ip_to_string(&buf, &tc->addr));
217
218   /* we don't want to keep this node */
219   tc->is_virtual = true;
220
221   /* The delete all non-virtual edges, the last one will clean up the tc if possible */
222   OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
223     /* we don't need this edge for the tc, so mark it virtual for possible cleanup */
224
225     tc_edge->is_virtual = 1;
226     olsr_delete_tc_edge_entry(tc_edge);
227   } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge);
228 }
229
230 /**
231  * Delete a tc entry after all edges have been cleared.
232  *
233  * @param entry the TC entry to delete
234  */
235 static void
236 olsr_cleanup_tc_entry(struct tc_entry *tc) {
237   struct rt_path *rtp;
238
239   assert (tc->edge_tree.count == 0);
240
241   /*
242    * Delete the rt_path for ourselves.
243    */
244   olsr_delete_routing_table(&tc->addr, 8 * olsr_cnf->ipsize, &tc->addr, OLSR_RT_ORIGIN_TC);
245
246   OLSR_FOR_ALL_PREFIX_ENTRIES(tc, rtp) {
247     olsr_delete_rt_path(rtp);
248   } OLSR_FOR_ALL_PREFIX_ENTRIES_END(tc, rtp);
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   /* Stop running timers */
257   olsr_stop_timer(tc->edge_gc_timer);
258   tc->edge_gc_timer = NULL;
259   olsr_stop_timer(tc->validity_timer);
260   tc->validity_timer = NULL;
261
262   avl_delete(&tc_tree, &tc->vertex_node);
263   olsr_unlock_tc_entry(tc);
264 }
265
266 /**
267  * Look up a entry from the TC tree based on address
268  *
269  * @param adr the address to look for
270  * @return the entry found or NULL
271  */
272 struct tc_entry *
273 olsr_lookup_tc_entry(const union olsr_ip_addr *adr)
274 {
275   struct avl_node *node;
276
277   node = avl_find(&tc_tree, adr);
278   return node ? vertex_tree2tc(node) : NULL;
279 }
280
281 /*
282  * Lookup a tc entry. Creates one if it does not exist yet.
283  */
284 struct tc_entry *
285 olsr_locate_tc_entry(const union olsr_ip_addr *adr)
286 {
287   struct tc_entry *tc = olsr_lookup_tc_entry(adr);
288
289   return tc == NULL ? olsr_add_tc_entry(adr) : tc;
290 }
291
292 /**
293  * Format tc_edge contents into a buffer.
294  */
295 #if !defined REMOVE_LOG_DEBUG
296 static char *
297 olsr_tc_edge_to_string(struct tc_edge_entry *tc_edge)
298 {
299   static char buf[128];
300   struct ipaddr_str addrbuf, dstbuf;
301   struct lqtextbuffer lqbuffer1, lqbuffer2;
302
303   snprintf(buf, sizeof(buf),
304            "%s > %s, cost (%6s) %s",
305            olsr_ip_to_string(&addrbuf, &tc_edge->tc->addr),
306            olsr_ip_to_string(&dstbuf, &tc_edge->T_dest_addr),
307            get_tc_edge_entry_text(tc_edge, '/', &lqbuffer1), get_linkcost_text(tc_edge->cost, false, &lqbuffer2));
308   return buf;
309 }
310 #endif
311
312 /**
313  * Wrapper for the timer callback.
314  * A TC entry has not been refreshed in time.
315  * Remove it from the link-state database.
316  */
317 static void
318 olsr_expire_tc_entry(void *context)
319 {
320 #if !defined REMOVE_LOG_DEBUG
321   struct ipaddr_str buf;
322 #endif
323   struct tc_entry *tc = context;
324   tc->validity_timer = NULL;
325
326   OLSR_DEBUG(LOG_TC, "TC: expire node entry %s\n",
327              olsr_ip_to_string(&buf, &tc->addr));
328
329   olsr_delete_tc_entry(tc);
330   changes_topology = true;
331 }
332
333 /**
334  * Wrapper for the timer callback.
335  * Does the garbage collection of older ansn entries after no edge addition to
336  * the TC entry has happened for OLSR_TC_EDGE_GC_TIME.
337  */
338 static void
339 olsr_expire_tc_edge_gc(void *context)
340 {
341 #if !defined REMOVE_LOG_DEBUG
342   struct ipaddr_str buf;
343 #endif
344   struct tc_entry *tc = context;
345
346   OLSR_DEBUG(LOG_TC, "TC: expire edge GC for %s\n",
347              olsr_ip_to_string(&buf, &tc->addr));
348
349   tc->edge_gc_timer = NULL;
350
351   if (delete_outdated_tc_edges(tc)) {
352     changes_topology = true;
353   }
354 }
355
356 /*
357  * If the edge does not have a minimum acceptable link quality
358  * set the etx cost to infinity such that it gets ignored during
359  * SPF calculation.
360  *
361  * @return 1 if the change of the etx value was relevant
362  */
363 bool
364 olsr_calc_tc_edge_entry_etx(struct tc_edge_entry *tc_edge)
365 {
366   olsr_linkcost old = tc_edge->cost;
367   tc_edge->cost = olsr_calc_tc_cost(tc_edge);
368   tc_edge->common_cost = tc_edge->cost;
369   if (tc_edge->edge_inv) {
370     tc_edge->edge_inv->common_cost = tc_edge->cost;
371   }
372   return olsr_is_relevant_costchange(old, tc_edge->cost);
373 }
374
375 /**
376  * Add a new tc_edge_entry to the tc_edge_tree
377  *
378  * @param (last)adr address of the entry
379  * @return a pointer to the created entry
380  */
381 struct tc_edge_entry *
382 olsr_add_tc_edge_entry(struct tc_entry *tc, union olsr_ip_addr *addr, uint16_t ansn)
383 {
384   struct tc_entry *tc_neighbor;
385   struct tc_edge_entry *tc_edge;
386   struct tc_edge_entry *tc_edge_inv;
387 #if !defined REMOVE_LOG_DEBUG
388   struct ipaddr_str buf;
389 #endif
390   tc_edge = olsr_malloc_tc_edge_entry();
391   if (!tc_edge) {
392     return NULL;
393   }
394
395   /* Fill entry */
396   tc_edge->T_dest_addr = *addr;
397   tc_edge->ansn = ansn;
398   tc_edge->edge_node.key = &tc_edge->T_dest_addr;
399
400   /*
401    * Insert into the edge tree.
402    * Expectation is to have only one tc_edge per tc pair.
403    * However we need duplicate key support for the case of local
404    * parallel links where we add one tc_edge per link_entry.
405    */
406   avl_insert(&tc->edge_tree, &tc_edge->edge_node, AVL_DUP);
407   olsr_lock_tc_entry(tc);
408
409   /*
410    * Connect backpointer.
411    */
412   tc_edge->tc = tc;
413
414   /*
415    * Check if the neighboring router and the inverse edge is in the lsdb.
416    * Create short cuts to the inverse edge for faster SPF execution.
417    */
418   tc_neighbor = olsr_lookup_tc_entry(&tc_edge->T_dest_addr);
419   if (tc_neighbor == NULL) {
420     OLSR_DEBUG(LOG_TC, "TC:   creating neighbor tc_entry %s\n", olsr_ip_to_string(&buf, &tc_edge->T_dest_addr));
421     tc_neighbor = olsr_add_tc_entry(&tc_edge->T_dest_addr);
422     tc_neighbor->is_virtual = true;
423   }
424
425   /* don't create an inverse edge for a tc pointing to us ! */
426   if (tc_neighbor != tc_myself) {
427     tc_edge_inv = olsr_lookup_tc_edge(tc_neighbor, &tc->addr);
428     if (!tc_edge_inv ) {
429       OLSR_DEBUG(LOG_TC, "TC:   creating inverse edge for %s\n", olsr_ip_to_string(&buf, &tc->addr));
430       tc_edge_inv = olsr_add_tc_edge_entry(tc_neighbor, &tc->addr, 0);
431
432       tc_edge_inv->is_virtual = 1;
433     }
434
435     /*
436      * Connect the edges mutually.
437      */
438     tc_edge_inv->edge_inv = tc_edge;
439     tc_edge->edge_inv = tc_edge_inv;
440   }
441
442   /*
443    * Update the etx.
444    */
445   olsr_calc_tc_edge_entry_etx(tc_edge);
446
447   OLSR_DEBUG(LOG_TC, "TC: add edge entry %s\n", olsr_tc_edge_to_string(tc_edge));
448
449   return tc_edge;
450 }
451
452 /**
453  * Delete a TC edge entry.
454  *
455  * @param tc the TC entry
456  * @param tc_edge the TC edge entry
457  */
458 void
459 olsr_delete_tc_edge_entry(struct tc_edge_entry *tc_edge)
460 {
461   struct tc_entry *tc;
462   struct link_entry *link;
463   struct tc_edge_entry *tc_edge_inv;
464 #if !defined REMOVE_LOG_DEBUG
465   struct ipaddr_str buf;
466 #endif
467
468   tc_edge_inv = tc_edge->edge_inv;
469   if (tc_edge->is_local == 0 && tc_edge_inv != NULL
470       && tc_edge_inv->is_virtual == 0 && tc_edge_inv->is_local == 0) {
471     /* mark this a virtual edge instead of removing it */
472     OLSR_DEBUG(LOG_TC, "TC: mark edge entry %s\n", olsr_tc_edge_to_string(tc_edge));
473
474     tc_edge->is_virtual = 1;
475     return;
476   }
477
478   OLSR_DEBUG(LOG_TC, "TC: del edge entry %s\n", olsr_tc_edge_to_string(tc_edge));
479
480   /*
481    * Clear the backpointer of our inverse edge.
482    */
483   if (tc_edge_inv) {
484     /* split the two edges */
485     tc_edge_inv->edge_inv = NULL;
486     tc_edge->edge_inv = NULL;
487
488     if (tc_edge_inv->is_virtual) {
489       /* remove the other side too because it's a virtual link */
490       olsr_delete_tc_edge_entry(tc_edge_inv);
491     }
492   }
493
494   tc = tc_edge->tc;
495
496   /* remove edge from tc FIRST */
497   avl_delete(&tc->edge_tree, &tc_edge->edge_node);
498
499   /* now check if TC is virtual and has no edges left */
500   if (tc->is_virtual && tc->edge_tree.count == 0) {
501     /* cleanup virtual tc node */
502     olsr_cleanup_tc_entry(tc);
503   }
504
505   OLSR_DEBUG(LOG_TC, "TC: %s down to %d edges\n", olsr_ip_to_string(&buf, &tc->addr), tc->edge_tree.count);
506   olsr_unlock_tc_entry(tc);
507
508   /*
509    * If this is a local edge, delete all references to it.
510    */
511   if (tc_edge->is_local) {
512     OLSR_FOR_ALL_LINK_ENTRIES(link) {
513       if (link->link_tc_edge == tc_edge) {
514         link->link_tc_edge = NULL;
515         break;
516       }
517     }
518     OLSR_FOR_ALL_LINK_ENTRIES_END(link);
519   }
520
521   olsr_free_tc_edge_entry(tc_edge);
522 }
523
524 /**
525  * Delete all destinations that have a lower ANSN.
526  *
527  * @param tc the entry to delete edges from
528  * @return TRUE if any destinations were deleted, FALSE if not
529  */
530 static bool
531 delete_outdated_tc_edges(struct tc_entry *tc)
532 {
533   struct tc_edge_entry *tc_edge;
534   bool retval = false;
535
536   OLSR_DEBUG(LOG_TC, "TC: deleting outdated TC-edge entries\n");
537
538   OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
539     if (SEQNO_GREATER_THAN(tc->ansn, tc_edge->ansn) && !(tc_edge->is_local)) {
540       olsr_delete_tc_edge_entry(tc_edge);
541       retval = true;
542     }
543   }
544   OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge);
545
546   if (retval)
547     changes_topology = true;
548   return retval;
549 }
550
551 /**
552  * Delete all destinations that are inside the borders but
553  * not updated in the last tc.
554  *
555  * @param tc the entry to delete edges from
556  * @param ansn the advertised neighbor set sequence number
557  * @return 1 if any destinations were deleted 0 if not
558  */
559 static int
560 olsr_delete_revoked_tc_edges(struct tc_entry *tc, uint16_t ansn, union olsr_ip_addr *lower_border, union olsr_ip_addr *upper_border)
561 {
562   struct tc_edge_entry *tc_edge;
563   int retval = 0;
564   bool passedLowerBorder = false;
565
566   OLSR_DEBUG(LOG_TC, "TC: deleting revoked TCs\n");
567
568   OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
569     if (!passedLowerBorder) {
570       if (avl_comp_default(lower_border, &tc_edge->T_dest_addr) <= 0) {
571         passedLowerBorder = true;
572       } else {
573         continue;
574       }
575     }
576
577     if (passedLowerBorder) {
578       if (avl_comp_default(upper_border, &tc_edge->T_dest_addr) <= 0) {
579         break;
580       }
581     }
582
583     if (SEQNO_GREATER_THAN(ansn, tc_edge->ansn) && tc_edge->is_local == 0) {
584       olsr_delete_tc_edge_entry(tc_edge);
585       retval = 1;
586     }
587   }
588   OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge);
589
590   if (retval)
591     changes_topology = true;
592   return retval;
593 }
594
595
596 /**
597  * Update an edge registered on an entry.
598  * Creates new edge-entries if not registered.
599  * Bases update on a received TC message
600  *
601  * @param entry the TC entry to check
602  * @pkt the TC edge entry in the packet
603  * @return 1 if entries are added 0 if not
604  */
605 static int
606 olsr_tc_update_edge(struct tc_entry *tc, uint16_t ansn, const unsigned char **curr, union olsr_ip_addr *neighbor)
607 {
608   struct tc_edge_entry *tc_edge;
609   int edge_change = 0;
610
611   /*
612    * Fetch the per-edge data
613    */
614   pkt_get_ipaddress(curr, neighbor);
615
616   /* First check if we know this edge */
617   tc_edge = olsr_lookup_tc_edge(tc, neighbor);
618   if (!tc_edge) {
619     /*
620      * Yet unknown - create it.
621      * Check if the address is allowed.
622      */
623     if (!olsr_validate_address(neighbor)) {
624       return 0;
625     }
626
627     tc_edge = olsr_add_tc_edge_entry(tc, neighbor, ansn);
628
629     olsr_deserialize_tc_lq_pair(curr, tc_edge);
630     edge_change = 1;
631   } else {
632     /*
633      * We know this edge - Update entry.
634      */
635     tc_edge->ansn = ansn;
636
637     /*
638      * Update link quality if configured.
639      */
640     olsr_deserialize_tc_lq_pair(curr, tc_edge);
641
642     /*
643      * Update the etx.
644      */
645     if (olsr_calc_tc_edge_entry_etx(tc_edge)) {
646       if (tc->msg_hops <= olsr_cnf->lq_dlimit) {
647         edge_change = 1;
648       }
649     }
650     if (edge_change) {
651       OLSR_DEBUG(LOG_TC, "TC:   chg edge entry %s\n", olsr_tc_edge_to_string(tc_edge));
652     }
653   }
654   tc_edge->is_virtual = 0;
655   tc->is_virtual = false;
656
657   return edge_change;
658 }
659
660 /**
661  * Lookup an edge hanging off a TC entry.
662  *
663  * @param entry the entry to check
664  * @param dst_addr the destination address to check for
665  * @return a pointer to the tc_edge found - or NULL
666  */
667 struct tc_edge_entry *
668 olsr_lookup_tc_edge(struct tc_entry *tc, union olsr_ip_addr *edge_addr)
669 {
670   struct avl_node *edge_node;
671
672   edge_node = avl_find(&tc->edge_tree, edge_addr);
673
674   return edge_node ? edge_tree2tc_edge(edge_node) : NULL;
675 }
676
677 /**
678  * Print the topology table to stdout
679  */
680 void
681 olsr_print_tc_table(void)
682 {
683 #if !defined REMOVE_LOG_INFO
684   /* The whole function makes no sense without it. */
685   static char LOCAL[] = "local";
686   static char VIRTUAL[] = "virtual";
687   static char NORMAL[] = "";
688
689   struct tc_entry *tc;
690   const int ipwidth = olsr_cnf->ip_version == AF_INET ? 15 : 30;
691
692   OLSR_INFO(LOG_TC, "\n--- %s ------------------------------------------------- TOPOLOGY\n\n", olsr_wallclock_string());
693   OLSR_INFO_NH(LOG_TC, "%-*s %-*s             %-14s  %8s %8s\n", ipwidth,
694                "Source IP addr", ipwidth, "Dest IP addr", "      LQ      ", "ETX", "(common)");
695
696   OLSR_FOR_ALL_TC_ENTRIES(tc) {
697     struct tc_edge_entry *tc_edge;
698     OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, tc_edge) {
699       struct ipaddr_str addrbuf, dstaddrbuf;
700       struct lqtextbuffer lqbuffer1, lqbuffer2, lqbuffer3;
701       char *type = NORMAL;
702       /* there should be no local virtual edges ! */
703       if (tc_edge->is_local) {
704         type = LOCAL;
705       }
706       else if (tc_edge->is_virtual) {
707         type = VIRTUAL;
708       }
709
710       OLSR_INFO_NH(LOG_TC, "%-*s %-*s %-7s      %-14s %8s/%8s\n",
711                    ipwidth, olsr_ip_to_string(&addrbuf, &tc->addr),
712                    ipwidth, olsr_ip_to_string(&dstaddrbuf,
713                                               &tc_edge->T_dest_addr),
714                    type,
715                    get_tc_edge_entry_text(tc_edge, '/', &lqbuffer1),
716                    get_linkcost_text(tc_edge->cost, false, &lqbuffer2),
717                    get_linkcost_text(tc_edge->common_cost, false, &lqbuffer3));
718
719     } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, tc_edge);
720   } OLSR_FOR_ALL_TC_ENTRIES_END(tc);
721 #endif
722 }
723
724 /*
725  * calculate the border IPs of a tc edge set according to the border flags
726  *
727  * @param lower border flag
728  * @param pointer to lower border ip
729  * @param upper border flag
730  * @param pointer to upper border ip
731  * @result 1 if lower/upper border ip have been set
732  */
733 static int
734 olsr_calculate_tc_border(uint8_t lower_border,
735                          union olsr_ip_addr *lower_border_ip, uint8_t upper_border, union olsr_ip_addr *upper_border_ip)
736 {
737   if (lower_border == 0 && upper_border == 0) {
738     return 0;
739   }
740   if (lower_border == 0xff) {
741     memset(lower_border_ip, 0, sizeof(lower_border_ip));
742   } else {
743     int i;
744
745     lower_border--;
746     for (i = 0; i < lower_border / 8; i++) {
747       lower_border_ip->v6.s6_addr[olsr_cnf->ipsize - i - 1] = 0;
748     }
749     lower_border_ip->v6.s6_addr[olsr_cnf->ipsize - lower_border / 8 - 1] &= (0xff << (lower_border & 7));
750     lower_border_ip->v6.s6_addr[olsr_cnf->ipsize - lower_border / 8 - 1] |= (1 << (lower_border & 7));
751   }
752
753   if (upper_border == 0xff) {
754     memset(upper_border_ip, 0xff, sizeof(upper_border_ip));
755   } else {
756     int i;
757
758     upper_border--;
759
760     for (i = 0; i < upper_border / 8; i++) {
761       upper_border_ip->v6.s6_addr[olsr_cnf->ipsize - i - 1] = 0;
762     }
763     upper_border_ip->v6.s6_addr[olsr_cnf->ipsize - upper_border / 8 - 1] &= (0xff << (upper_border & 7));
764     upper_border_ip->v6.s6_addr[olsr_cnf->ipsize - upper_border / 8 - 1] |= (1 << (upper_border & 7));
765   }
766   return 1;
767 }
768
769 /*
770  * Process an incoming TC or TC_LQ message.
771  *
772  * If the message is interesting enough, update our edges for it,
773  * trigger SPF and finally flood it to all our 2way neighbors.
774  *
775  * The order for extracting data off the message does matter,
776  * as every call to pkt_get increases the packet offset and
777  * hence the spot we are looking at.
778  */
779 void
780 olsr_input_tc(union olsr_message * msg, struct interface * input_if __attribute__ ((unused)),
781     union olsr_ip_addr * from_addr, enum duplicate_status status)
782 {
783   uint16_t size, msg_seq, ansn;
784   uint8_t type, ttl, msg_hops, lower_border, upper_border;
785   uint32_t vtime;
786   union olsr_ip_addr originator;
787   const unsigned char *limit, *curr;
788   struct tc_entry *tc;
789   bool relevantTc;
790 #if !defined REMOVE_LOG_DEBUG
791   struct ipaddr_str buf;
792 #endif
793   union olsr_ip_addr lower_border_ip, upper_border_ip;
794   int borderSet = 0;
795
796   curr = (void *)msg;
797
798   /* We are only interested in TC message types. */
799   pkt_get_u8(&curr, &type);
800   if ((type != LQ_TC_MESSAGE) && (type != TC_MESSAGE)) {
801     return;
802   }
803
804   /*
805    * If the sender interface (NB: not originator) of this message
806    * is not in the symmetric 1-hop neighborhood of this node, the
807    * message MUST be discarded.
808    */
809   if (check_neighbor_link(from_addr) != SYM_LINK) {
810     OLSR_DEBUG(LOG_TC, "Received TC from NON SYM neighbor %s\n", olsr_ip_to_string(&buf, from_addr));
811     return;
812   }
813
814   pkt_get_reltime(&curr, &vtime);
815   pkt_get_u16(&curr, &size);
816
817   pkt_get_ipaddress(&curr, &originator);
818
819   /* Copy header values */
820   pkt_get_u8(&curr, &ttl);
821   pkt_get_u8(&curr, &msg_hops);
822   pkt_get_u16(&curr, &msg_seq);
823   pkt_get_u16(&curr, &ansn);
824
825   /* Get borders */
826   pkt_get_u8(&curr, &lower_border);
827   pkt_get_u8(&curr, &upper_border);
828
829   tc = olsr_lookup_tc_entry(&originator);
830
831   /* TCs can be splitted, so we are looking for ANSNs equal or higher */
832   if (tc && status != RESET_SEQNO_OLSR_MESSAGE && olsr_seqno_diff(ansn, tc->ansn) < 0) {
833     /* this TC is too old, discard it */
834     return;
835   }
836
837   /*
838    * Generate a new tc_entry in the lsdb and store the sequence number.
839    */
840   if (!tc) {
841     tc = olsr_add_tc_entry(&originator);
842   }
843
844   /*
845    * Update the tc entry.
846    */
847   tc->msg_hops = msg_hops;
848   tc->tc_seq = msg_seq;
849   tc->ansn = ansn;
850   tc->ignored = 0;
851   tc->err_seq_valid = false;
852   tc->is_virtual = false;
853
854   OLSR_DEBUG(LOG_TC, "Processing TC from %s, seq 0x%04x\n", olsr_ip_to_string(&buf, &originator), tc->tc_seq);
855
856   /*
857    * Now walk the edge advertisements contained in the packet.
858    */
859
860   limit = (unsigned char *)msg + size;
861   borderSet = 0;
862   relevantTc = false;
863   while (curr < limit) {
864     if (olsr_tc_update_edge(tc, ansn, &curr, &upper_border_ip)) {
865       relevantTc = true;
866     }
867
868     if (!borderSet) {
869       borderSet = 1;
870       memcpy(&lower_border_ip, &upper_border_ip, sizeof(lower_border_ip));
871     }
872   }
873
874   if (relevantTc) {
875     relevantTcCount++;
876     changes_topology = true;
877   }
878
879   /*
880    * Calculate real border IPs.
881    */
882   if (borderSet) {
883     borderSet = olsr_calculate_tc_border(lower_border, &lower_border_ip, upper_border, &upper_border_ip);
884   }
885
886   /*
887    * Set or change the expiration timer accordingly.
888    */
889   olsr_set_timer(&tc->validity_timer, vtime,
890                  OLSR_TC_VTIME_JITTER, OLSR_TIMER_ONESHOT, &olsr_expire_tc_entry, tc, tc_validity_timer_cookie);
891
892   if (borderSet) {
893
894     /*
895      * Delete all old tc edges within borders.
896      */
897     olsr_delete_revoked_tc_edges(tc, ansn, &lower_border_ip, &upper_border_ip);
898   } else {
899
900     /*
901      * Kick the the edge garbage collection timer. In the meantime hopefully
902      * all edges belonging to a multipart neighbor set will arrive.
903      */
904     olsr_set_timer(&tc->edge_gc_timer, OLSR_TC_EDGE_GC_TIME,
905                    OLSR_TC_EDGE_GC_JITTER, OLSR_TIMER_ONESHOT, &olsr_expire_tc_edge_gc, tc, tc_edge_gc_timer_cookie);
906   }
907 }
908
909 uint32_t
910 getRelevantTcCount(void)
911 {
912   return relevantTcCount;
913 }
914
915 void
916 olsr_delete_all_tc_entries(void) {
917   struct tc_entry *tc;
918   struct tc_edge_entry *edge;
919
920   /* first mark all nodes non-virtual and all edges virtual */
921   tc_myself->is_virtual = false;
922   OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc_myself, edge) {
923     edge->is_virtual = 1;
924   } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc_myself, edge)
925
926   OLSR_FOR_ALL_TC_ENTRIES(tc) {
927     tc->is_virtual = false;
928     OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, edge) {
929       edge->is_virtual = 1;
930     } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, edge)
931   }OLSR_FOR_ALL_TC_ENTRIES_END(tc)
932
933   /* erase all edges */
934   OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc_myself, edge) {
935     olsr_delete_tc_edge_entry(edge);
936   } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc_myself, edge)
937   OLSR_FOR_ALL_TC_ENTRIES(tc) {
938     OLSR_FOR_ALL_TC_EDGE_ENTRIES(tc, edge) {
939       olsr_delete_tc_edge_entry(edge);
940     } OLSR_FOR_ALL_TC_EDGE_ENTRIES_END(tc, edge)
941   }OLSR_FOR_ALL_TC_ENTRIES_END(tc)
942
943   /* then remove all tc entries */
944   tc_myself->is_virtual = true;
945   olsr_delete_tc_entry(tc_myself);
946   tc_myself = NULL;
947   OLSR_FOR_ALL_TC_ENTRIES(tc) {
948     tc->is_virtual = true;
949     olsr_delete_tc_entry(tc);
950   }OLSR_FOR_ALL_TC_ENTRIES_END(tc)
951 }
952
953 /*
954  * Local Variables:
955  * c-basic-offset: 2
956  * indent-tabs-mode: nil
957  * End:
958  */