more inlining and a bug fix:
[olsrd.git] / src / routing_table.c
1 /*
2  * The olsr.org Optimized Link-State Routing daemon(olsrd)
3  * Copyright (c) 2004, Andreas T√łnnesen(andreto@olsr.org)
4  * RIB implementation (c) 2007, Hannes Gredler (hannes@gredler.at)
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
42 #include "routing_table.h"
43 #include "ipcalc.h"
44 #include "defs.h"
45 #include "two_hop_neighbor_table.h"
46 #include "tc_set.h"
47 #include "mid_set.h"
48 #include "neighbor_table.h"
49 #include "olsr.h"
50 #include "link_set.h"
51 #include "common/avl.h"
52 #include "lq_route.h"
53 #include "net_olsr.h"
54
55 #include <assert.h>
56
57 /*
58  * Sven-Ola: if the current internet gateway is switched, the
59  * NAT connection info is lost for any active TCP/UDP session.
60  * For this reason, we do not want to switch if the advantage
61  * is only minimal (cost of loosing all NATs is too high).
62  * The following rt_path keeps track of the current inet gw.
63  */
64 static struct rt_path *current_inetgw = NULL;
65
66 /* Root of our RIB */
67 struct avl_tree routingtree;
68
69 /*
70  * Keep a version number for detecting outdated elements
71  * in the per rt_entry rt_path subtree.
72  */
73 unsigned int routingtree_version;
74
75 /**
76  * avl_comp_ipv4_prefix
77  *
78  * compare two ipv4 prefixes.
79  * first compare the prefixes, then
80  *  then compare the prefix lengths.
81  *
82  * return 0 if there is an exact match and
83  * -1 / +1 depending on being smaller or bigger.
84  */
85 int
86 avl_comp_ipv4_prefix (const void *prefix1, const void *prefix2)
87 {       
88   const struct olsr_ip_prefix *pfx1 = prefix1;
89   const struct olsr_ip_prefix *pfx2 = prefix2;
90   const olsr_u32_t addr1 = ntohl(pfx1->prefix.v4.s_addr);
91   const olsr_u32_t addr2 = ntohl(pfx2->prefix.v4.s_addr);
92
93   /* prefix */
94   if (addr1 < addr2) {
95     return -1;
96   }
97   if (addr1 > addr2) {
98     return +1;
99   }
100
101   /* prefix length */
102   if (pfx1->prefix_len < pfx2->prefix_len) {
103     return -1;
104   }
105   if (pfx1->prefix_len > pfx2->prefix_len) {
106     return +1;
107   }
108
109   return 0;
110 }
111
112 /**
113  * avl_comp_ipv6_prefix
114  *
115  * compare two ipv6 prefixes.
116  * first compare the prefixes, then
117  *  then compare the prefix lengths.
118  *
119  * return 0 if there is an exact match and
120  * -1 / +1 depending on being smaller or bigger.
121  */
122 int
123 avl_comp_ipv6_prefix (const void *prefix1, const void *prefix2)
124 {       
125   int res;
126   const struct olsr_ip_prefix *pfx1 = prefix1;
127   const struct olsr_ip_prefix *pfx2 = prefix2;
128
129   /* prefix */
130   res = ip6equal(&pfx1->prefix.v6, &pfx2->prefix.v6);
131   if (res != 0) {
132     return res;
133   } 
134   /* prefix length */
135   if (pfx1->prefix_len < pfx2->prefix_len) {
136     return -1;
137   }
138   if (pfx1->prefix_len > pfx2->prefix_len) {
139     return +1;
140   }
141
142   return 0;
143 }
144
145 /**
146  * Initialize the routingtree and kernel change queues.
147  */
148 void
149 olsr_init_routing_table(void)
150 {
151   /* the routing tree */
152   avl_init(&routingtree, avl_comp_prefix_default);
153   routingtree_version = 0;
154 }
155
156 /**
157  * Look up a maxplen entry (= /32 or /128) in the routing table.
158  *
159  * @param dst the address of the entry
160  *
161  * @return a pointer to a rt_entry struct 
162  * representing the route entry.
163  */
164 struct rt_entry *
165 olsr_lookup_routing_table(const union olsr_ip_addr *dst)
166 {
167   struct avl_node *rt_tree_node;
168   struct olsr_ip_prefix prefix;
169
170   prefix.prefix = *dst;
171   prefix.prefix_len = olsr_cnf->maxplen;
172
173   rt_tree_node = avl_find(&routingtree, &prefix);
174
175   return rt_tree_node ? rt_tree2rt(rt_tree_node) : NULL;
176 }
177
178 /**
179  * Update gateway/interface/etx/hopcount and the version for a route path.
180  */
181 void
182 olsr_update_rt_path(struct rt_path *rtp, struct tc_entry *tc,
183                     struct link_entry *link)
184 {
185
186   rtp->rtp_version = routingtree_version;
187
188   /* gateway */
189   rtp->rtp_nexthop.gateway = link->neighbor_iface_addr;
190
191   /* interface */
192   rtp->rtp_nexthop.iif_index = link->inter->if_index;
193
194   /* metric/etx */
195   rtp->rtp_metric.hops = tc->hops;
196   rtp->rtp_metric.cost = tc->path_cost;
197 }
198
199 /**
200  * Alloc and key a new rt_entry.
201  */
202 static struct rt_entry *
203 olsr_alloc_rt_entry(struct olsr_ip_prefix *prefix)
204 {
205   struct rt_entry *rt = olsr_malloc(sizeof(struct rt_entry), __FUNCTION__);
206   if (!rt) {
207     return NULL;
208   }
209
210   memset(rt, 0, sizeof(*rt));
211   
212   /* Mark this entry as fresh (see process_routes.c:512) */
213   rt->rt_nexthop.iif_index = -1;
214
215   /* set key and backpointer prior to tree insertion */
216   rt->rt_dst = *prefix;
217
218   rt->rt_tree_node.key = &rt->rt_dst;
219   avl_insert(&routingtree, &rt->rt_tree_node, AVL_DUP_NO);
220
221   /* init the originator subtree */
222   avl_init(&rt->rt_path_tree, avl_comp_default);
223
224   return rt;
225 }
226
227 /**
228  * Alloc and key a new rt_path.
229  */
230 static struct rt_path *
231 olsr_alloc_rt_path(struct tc_entry *tc,
232                    struct olsr_ip_prefix *prefix, olsr_u8_t origin)
233 {
234   struct rt_path *rtp = olsr_malloc(sizeof(struct rt_path), __FUNCTION__);
235
236   if (!rtp) {
237     return NULL;
238   }
239
240   memset(rtp, 0, sizeof(*rtp));
241
242   rtp->rtp_dst = *prefix;
243
244   /* set key and backpointer prior to tree insertion */
245   rtp->rtp_prefix_tree_node.key = &rtp->rtp_dst;
246
247   /* insert to the tc prefix tree */
248   avl_insert(&tc->prefix_tree, &rtp->rtp_prefix_tree_node, AVL_DUP_NO);
249   olsr_lock_tc_entry(tc);
250
251   /* backlink to the owning tc entry */
252   rtp->rtp_tc = tc;
253
254   /* store the origin of the route */
255   rtp->rtp_origin = origin;
256
257   return rtp;
258 }
259
260 /**
261  * Create a route entry for a given rt_path and
262  * insert it into the global RIB tree.
263  */
264 void
265 olsr_insert_rt_path(struct rt_path *rtp, struct tc_entry *tc,
266                     struct link_entry *link)
267 {
268   struct rt_entry *rt;
269   struct avl_node *node;
270
271   /*
272    * no unreachable routes please.
273    */
274   if (tc->path_cost == ROUTE_COST_BROKEN) {
275     return;
276   }
277
278   /*
279    * No bogus prefix lengths.
280    */
281   if (rtp->rtp_dst.prefix_len > olsr_cnf->maxplen) {
282     return;
283   }
284
285   /*
286    * first check if there is a route_entry for the prefix.
287    */
288   node = avl_find(&routingtree, &rtp->rtp_dst);
289
290   if (!node) {
291
292     /* no route entry yet */
293     rt = olsr_alloc_rt_entry(&rtp->rtp_dst);
294
295     if (!rt) {
296       return;
297     }
298
299   } else {
300     rt = rt_tree2rt(node);
301   }
302
303
304   /* Now insert the rt_path to the owning rt_entry tree */
305   rtp->rtp_originator = tc->addr;
306
307   /* set key and backpointer prior to tree insertion */
308   rtp->rtp_tree_node.key = &rtp->rtp_originator;
309
310   /* insert to the route entry originator tree */
311   avl_insert(&rt->rt_path_tree, &rtp->rtp_tree_node, AVL_DUP_NO);
312
313   /* backlink to the owning route entry */
314   rtp->rtp_rt = rt;
315
316   /* update the version field and relevant parameters */
317   olsr_update_rt_path(rtp, tc, link);
318 }
319
320 /**
321  * Unlink and free a rt_path.
322  */
323 void
324 olsr_delete_rt_path(struct rt_path *rtp)
325 {
326
327   /* remove from the originator tree */
328   if (rtp->rtp_rt) {
329     avl_delete(&rtp->rtp_rt->rt_path_tree, &rtp->rtp_tree_node);
330     rtp->rtp_rt = NULL;
331   }
332
333   /* remove from the tc prefix tree */
334   if (rtp->rtp_tc) {
335     avl_delete(&rtp->rtp_tc->prefix_tree, &rtp->rtp_prefix_tree_node);
336     olsr_unlock_tc_entry(rtp->rtp_tc);
337     rtp->rtp_tc = NULL;
338   }
339
340   /* no current inet gw if the rt_path is removed */
341   if (current_inetgw == rtp) {
342     current_inetgw = NULL;
343   }
344
345   free(rtp);
346 }
347
348 #if 0
349 /**
350  * Depending if flat_metric is configured and the kernel fib operation
351  * return the hopcount metric of a route.
352  * For adds this is the metric of best rour after olsr_rt_best() election,
353  * for deletes this is the metric of the route that got stored in the rt_entry,
354  * during route installation.
355  */
356 olsr_u8_t
357 olsr_fib_metric(const struct rt_metric *met)
358 {
359   if (FIBM_CORRECT == olsr_cnf->fib_metric) {
360     return met->hops;
361   }
362   return RT_METRIC_DEFAULT;
363 }
364 #endif
365
366 /**
367  * compare two route paths.
368  *
369  * returns TRUE if the first path is better
370  * than the second one, FALSE otherwise.
371  */
372 static olsr_bool
373 olsr_cmp_rtp(const struct rt_path *rtp1, const struct rt_path *rtp2, const struct rt_path *inetgw)
374 {
375     olsr_linkcost etx1 = rtp1->rtp_metric.cost;
376     olsr_linkcost etx2 = rtp2->rtp_metric.cost;
377     if (inetgw == rtp1) etx1 *= olsr_cnf->lq_nat_thresh;
378     if (inetgw == rtp2) etx2 *= olsr_cnf->lq_nat_thresh;
379
380     /* etx comes first */
381     if (etx1 < etx2) {
382       return OLSR_TRUE;
383     }
384
385     /* hopcount is next tie breaker */
386     if ((etx1 == etx2) &&
387         (rtp1->rtp_metric.hops < rtp2->rtp_metric.hops)) {
388       return OLSR_TRUE;
389     }
390
391     /* originator (which is guaranteed to be unique) is final tie breaker */
392     if ((rtp1->rtp_metric.hops == rtp2->rtp_metric.hops) &&
393         (ipcmp(&rtp1->rtp_originator, &rtp2->rtp_originator) < 0)) {
394       return OLSR_TRUE;
395     }
396
397     return OLSR_FALSE;
398 }
399
400 /**
401  * compare the best path of two route entries.
402  *
403  * returns TRUE if the first entry is better
404  * than the second one, FALSE otherwise.
405  */
406 olsr_bool
407 olsr_cmp_rt(const struct rt_entry *rt1, const struct rt_entry *rt2)
408 {
409     return olsr_cmp_rtp(rt1->rt_best, rt2->rt_best, NULL);
410 }
411
412 /**
413  * run best route selection among a
414  * set of identical prefixes.
415  */
416 void
417 olsr_rt_best(struct rt_entry *rt)
418 {
419   /* grab the first entry */
420   struct avl_node *node = avl_walk_first(&rt->rt_path_tree);
421
422   assert(node != 0); /* should not happen */
423
424   rt->rt_best = rtp_tree2rtp(node);
425
426   /* walk all remaining originator entries */
427   while ((node = avl_walk_next(node))) {
428     struct rt_path *rtp = rtp_tree2rtp(node);
429
430     if (olsr_cmp_rtp(rtp, rt->rt_best, current_inetgw)) {
431       rt->rt_best = rtp;
432     }
433   }
434
435   if (0 == rt->rt_dst.prefix_len) {
436     current_inetgw = rt->rt_best;
437   }
438 }
439
440 /**
441  * Insert a prefix into the prefix tree hanging off a lsdb (tc) entry.
442  *
443  * Check if the candidate route (we call this a rt_path) is known,
444  * if not create it.
445  * Upon post-SPF processing (if the node is reachable) the prefix
446  * will be finally inserted into the global RIB.
447  *
448  *@param dst the destination
449  *@param plen the prefix length
450  *@param originator the originating router
451  *
452  *@return the new rt_path struct
453  */
454 struct rt_path *
455 olsr_insert_routing_table(union olsr_ip_addr *dst, int plen,
456                           union olsr_ip_addr *originator, int origin)
457 {
458 #if !defined(NODEBUG) && defined(DEBUG)
459   struct ipaddr_str dstbuf, origbuf;
460 #endif
461   struct tc_entry *tc;
462   struct rt_path *rtp;
463   struct avl_node *node;
464   struct olsr_ip_prefix prefix;
465
466   /*
467    * No bogus prefix lengths.
468    */
469   if (plen > olsr_cnf->maxplen) {
470     return NULL;
471   }
472
473 #ifdef DEBUG
474   OLSR_PRINTF(1, "RIB: add prefix %s/%u from %s\n",
475               olsr_ip_to_string(&dstbuf, dst), plen,
476               olsr_ip_to_string(&origbuf, originator));
477 #endif
478
479   /*
480    * For all routes we use the tc_entry as an hookup point.
481    * If the tc_entry is disconnected, i.e. has no edges it will not
482    * be explored during SPF run.
483    */
484   tc = olsr_locate_tc_entry(originator);
485   
486   /*
487    * first check if there is a rt_path for the prefix.
488    */
489   prefix.prefix = *dst;
490   prefix.prefix_len = plen;
491
492   node = avl_find(&tc->prefix_tree, &prefix);
493
494   if (!node) {
495
496     /* no rt_path for this prefix yet */
497     rtp = olsr_alloc_rt_path(tc, &prefix, origin);
498
499     if (!rtp) {
500       return NULL;
501     }
502
503     /* overload the hna change bit for flagging a prefix change */
504     changes_hna = OLSR_TRUE;
505
506   } else {
507     rtp = rtp_prefix_tree2rtp(node);
508   }
509
510   return rtp;
511 }
512
513 /**
514  * Delete a prefix from the prefix tree hanging off a lsdb (tc) entry.
515  */
516 void
517 olsr_delete_routing_table(union olsr_ip_addr *dst, int plen,
518                           union olsr_ip_addr *originator)
519 {
520 #if !defined(NODEBUG) && defined(DEBUG)
521   struct ipaddr_str buf;
522 #endif
523
524   struct tc_entry *tc;
525   struct rt_path *rtp;
526   struct avl_node *node;
527   struct olsr_ip_prefix prefix;
528
529   /*
530    * No bogus prefix lengths.
531    */
532   if (plen > olsr_cnf->maxplen) {
533     return;
534   }
535
536 #ifdef DEBUG
537   OLSR_PRINTF(1, "RIB: del prefix %s/%u from %s\n",
538               olsr_ip_to_string(&buf, dst), plen,
539               olsr_ip_to_string(&buf, originator));
540 #endif
541
542   tc = olsr_lookup_tc_entry(originator);
543   if (!tc) {
544     return;
545   }
546
547   /*
548    * Grab the rt_path for the prefix.
549    */
550   prefix.prefix = *dst;
551   prefix.prefix_len = plen;
552
553   node = avl_find(&tc->prefix_tree, &prefix);
554
555   if (node) {
556     rtp = rtp_prefix_tree2rtp(node);
557     olsr_delete_rt_path(rtp);
558
559     /* overload the hna change bit for flagging a prefix change */
560     changes_hna = OLSR_TRUE;
561   }
562 }
563
564 /**
565  * format a route entry into a buffer
566  */
567 char *
568 olsr_rt_to_string(const struct rt_entry *rt)
569 {
570   static char buff[128];
571   struct ipaddr_str prefixstr, gwstr;
572
573   snprintf(buff, sizeof(buff),
574            "%s/%u via %s",
575            olsr_ip_to_string(&prefixstr, &rt->rt_dst.prefix),
576            rt->rt_dst.prefix_len,
577            olsr_ip_to_string(&gwstr, &rt->rt_nexthop.gateway));
578
579   return buff;
580 }
581
582 /**
583  * format a route path into a buffer
584  */
585 char *
586 olsr_rtp_to_string(const struct rt_path *rtp)
587 {
588   static char buff[128];
589   struct ipaddr_str prefixstr, origstr, gwstr;
590   struct rt_entry *rt = rtp->rtp_rt;
591   struct lqtextbuffer lqbuffer;
592   
593   snprintf(buff, sizeof(buff),
594            "%s/%u from %s via %s, "
595            "cost %s, metric %u, v %u",
596            olsr_ip_to_string(&prefixstr, &rt->rt_dst.prefix),
597            rt->rt_dst.prefix_len,
598            olsr_ip_to_string(&origstr, &rtp->rtp_originator),
599            olsr_ip_to_string(&gwstr, &rtp->rtp_nexthop.gateway),
600            get_linkcost_text(rtp->rtp_metric.cost, OLSR_TRUE, &lqbuffer),
601            rtp->rtp_metric.hops,
602            rtp->rtp_version);
603
604   return buff;
605 }
606
607 /**
608  * Print the routingtree to STDOUT
609  *
610  */
611 void
612 olsr_print_routing_table(struct avl_tree *tree)
613 {
614 #ifndef NODEBUG
615   /* The whole function makes no sense without it. */
616   struct avl_node *rt_tree_node;
617   struct lqtextbuffer lqbuffer;
618   
619   OLSR_PRINTF(6, "ROUTING TABLE\n");
620
621   for (rt_tree_node = avl_walk_first(tree);
622        rt_tree_node != NULL;
623        rt_tree_node = avl_walk_next(rt_tree_node)) {
624     struct avl_node *rtp_tree_node;
625     struct ipaddr_str prefixstr, origstr, gwstr;
626     struct rt_entry *rt = rt_tree2rt(rt_tree_node);
627
628     /* first the route entry */
629     OLSR_PRINTF(6, "%s/%u, via %s, best-originator %s\n",
630            olsr_ip_to_string(&prefixstr, &rt->rt_dst.prefix),
631            rt->rt_dst.prefix_len,
632            olsr_ip_to_string(&origstr, &rt->rt_nexthop.gateway),
633            olsr_ip_to_string(&gwstr, &rt->rt_best->rtp_originator));
634
635     /* walk the per-originator path tree of routes */
636     for (rtp_tree_node = avl_walk_first(&rt->rt_path_tree);
637          rtp_tree_node != NULL;
638          rtp_tree_node = avl_walk_next(rtp_tree_node)) {
639       struct rt_path *rtp = rtp_tree2rtp(rtp_tree_node);
640       OLSR_PRINTF(6, "\tfrom %s, cost %s, metric %u, via %s, %s, v %u\n",
641              olsr_ip_to_string(&origstr, &rtp->rtp_originator),
642              get_linkcost_text(rtp->rtp_metric.cost, OLSR_TRUE, &lqbuffer),
643              rtp->rtp_metric.hops,
644              olsr_ip_to_string(&gwstr, &rtp->rtp_nexthop.gateway),
645              if_ifwithindex_name(rt->rt_nexthop.iif_index),
646              rtp->rtp_version);    
647     }
648   }
649 #endif
650   tree = NULL; /* squelch compiler warnings */
651 }
652
653 /*
654  * Local Variables:
655  * c-basic-offset: 2
656  * End:
657  */