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