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