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