86250ab0f38b07a0cd9a6329924880634ce1ad65
[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 "lq_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  * Bump the version number of the routing tree.
77  *
78  * After route-insertion compare the version number of the routes
79  * against the version number of the table.
80  * This is a lightweight detection if a node or prefix went away,
81  * rather than brute force old vs. new rt_entry comparision.
82  */
83 unsigned int
84 olsr_bump_routingtree_version(void)
85 {
86   return routingtree_version++;
87 }
88
89 /**
90  * avl_comp_ipv4_prefix
91  *
92  * compare two ipv4 prefixes.
93  * first compare the prefixes, then
94  *  then compare the prefix lengths.
95  *
96  * return 0 if there is an exact match and
97  * -1 / +1 depending on being smaller or bigger.
98  */
99 int
100 avl_comp_ipv4_prefix (const void *prefix1, const void *prefix2)
101 {       
102   const struct olsr_ip_prefix *pfx1 = prefix1;
103   const struct olsr_ip_prefix *pfx2 = prefix2;
104   const olsr_u32_t addr1 = ntohl(pfx1->prefix.v4.s_addr);
105   const olsr_u32_t addr2 = ntohl(pfx2->prefix.v4.s_addr);
106
107   /* prefix */
108   if (addr1 < addr2) {
109     return -1;
110   }
111   if (addr1 > addr2) {
112     return +1;
113   }
114
115   /* prefix length */
116   if (pfx1->prefix_len < pfx2->prefix_len) {
117     return -1;
118   }
119   if (pfx1->prefix_len > pfx2->prefix_len) {
120     return +1;
121   }
122
123   return 0;
124 }
125
126 /**
127  * avl_comp_ipv6_prefix
128  *
129  * compare two ipv6 prefixes.
130  * first compare the prefixes, then
131  *  then compare the prefix lengths.
132  *
133  * return 0 if there is an exact match and
134  * -1 / +1 depending on being smaller or bigger.
135  */
136 int
137 avl_comp_ipv6_prefix (const void *prefix1, const void *prefix2)
138 {       
139   int res;
140   const struct olsr_ip_prefix *pfx1 = prefix1;
141   const struct olsr_ip_prefix *pfx2 = prefix2;
142
143   /* prefix */
144   res = memcmp(&pfx1->prefix.v6, &pfx2->prefix.v6, 16);
145   if (res != 0) {
146     return res;
147   } 
148   /* prefix length */
149   if (pfx1->prefix_len < pfx2->prefix_len) {
150     return -1;
151   }
152   if (pfx1->prefix_len > pfx2->prefix_len) {
153     return +1;
154   }
155
156   return 0;
157 }
158
159 /**
160  * Initialize the routingtree and kernel change queues.
161  */
162 void
163 olsr_init_routing_table(void)
164 {
165   /* the routing tree */
166   avl_init(&routingtree, avl_comp_prefix_default);
167   routingtree_version = 0;
168 }
169
170 /**
171  * Look up a maxplen entry (= /32 or /128) in the routing table.
172  *
173  * @param dst the address of the entry
174  *
175  * @return a pointer to a rt_entry struct 
176  * representing the route entry.
177  */
178 struct rt_entry *
179 olsr_lookup_routing_table(const union olsr_ip_addr *dst)
180 {
181   struct avl_node *rt_tree_node;
182   struct olsr_ip_prefix prefix;
183
184   prefix.prefix = *dst;
185   prefix.prefix_len = olsr_cnf->maxplen;
186
187   rt_tree_node = avl_find(&routingtree, &prefix);
188
189   return rt_tree_node ? rt_tree_node->data : NULL;
190 }
191
192 /**
193  * Update gateway/interface/etx/hopcount and the version for a route path.
194  */
195 void
196 olsr_update_rt_path(struct rt_path *rtp, struct tc_entry *tc,
197                     struct link_entry *link)
198 {
199
200   rtp->rtp_version = routingtree_version;
201
202   /* gateway */
203   rtp->rtp_nexthop.gateway = link->neighbor_iface_addr;
204
205   /* interface */
206   rtp->rtp_nexthop.iif_index = link->inter->if_index;
207
208   /* metric/etx */
209   rtp->rtp_metric.hops = tc->hops;
210   rtp->rtp_metric.etx = tc->path_etx;
211 }
212
213 /**
214  * Alloc and key a new rt_entry.
215  */
216 static struct rt_entry *
217 olsr_alloc_rt_entry(struct olsr_ip_prefix *prefix)
218 {
219   struct rt_entry *rt = olsr_malloc(sizeof(struct rt_entry), __FUNCTION__);
220   if (!rt) {
221     return NULL;
222   }
223
224   memset(rt, 0, sizeof(*rt));
225   
226   /* Mark this entry as fresh (see process_routes.c:512) */
227   rt->rt_nexthop.iif_index = -1;
228
229   /* set key and backpointer prior to tree insertion */
230   rt->rt_dst = *prefix;
231
232   rt->rt_tree_node.key = &rt->rt_dst;
233   rt->rt_tree_node.data = rt;
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_malloc(sizeof(struct rt_path), __FUNCTION__);
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   rtp->rtp_prefix_tree_node.data = rtp;
262
263   /* insert to the tc prefix tree */
264   avl_insert(&tc->prefix_tree, &rtp->rtp_prefix_tree_node, AVL_DUP_NO);
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_etx >= INFINITE_ETX) {
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 = node->data;
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   rtp->rtp_tree_node.data = rtp;
325
326   /* insert to the route entry originator tree */
327   avl_insert(&rt->rt_path_tree, &rtp->rtp_tree_node, AVL_DUP_NO);
328
329   /* backlink to the owning route entry */
330   rtp->rtp_rt = rt;
331
332   /* update the version field and relevant parameters */
333   olsr_update_rt_path(rtp, tc, link);
334 }
335
336 /**
337  * Unlink and free a rt_path.
338  */
339 static void
340 olsr_free_rt_path(struct rt_path *rtp)
341 {
342
343   /* remove from the originator tree */
344   if (rtp->rtp_rt) {
345     avl_delete(&rtp->rtp_rt->rt_path_tree, &rtp->rtp_tree_node);
346     rtp->rtp_rt = NULL;
347   }
348
349   /* remove from the tc prefix tree */
350   if (rtp->rtp_tc) {
351     avl_delete(&rtp->rtp_tc->prefix_tree, &rtp->rtp_prefix_tree_node);
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   free(rtp);
361 }
362
363
364 /**
365  * Check if there is an interface or gateway change.
366  */
367 olsr_bool
368 olsr_nh_change(const struct rt_nexthop *nh1, const struct rt_nexthop *nh2)
369 {
370   if (!ipequal(&nh1->gateway, &nh2->gateway) ||
371       (nh1->iif_index != nh2->iif_index)) {
372     return OLSR_TRUE;
373   }
374   return OLSR_FALSE;
375 }
376
377 /**
378  * Check if there is a hopcount change.
379  */
380 olsr_bool
381 olsr_hopcount_change(const struct rt_metric *met1, const struct rt_metric *met2)
382 {
383   return (met1->hops != met2->hops);
384 }
385
386 /**
387  * Depending if flat_metric is configured and the kernel fib operation
388  * return the hopcount metric of a route.
389  * For adds this is the metric of best rour after olsr_rt_best() election,
390  * for deletes this is the metric of the route that got stored in the rt_entry,
391  * during route installation.
392  */
393 olsr_u8_t
394 olsr_fib_metric(const struct rt_metric *met)
395 {
396   if (FIBM_CORRECT == olsr_cnf->fib_metric) {
397     return met->hops;
398   }
399   return RT_METRIC_DEFAULT;
400 }
401
402 /**
403  * depending on the operation (add/chg/del) the nexthop
404  * field from the route entry or best route path shall be used.
405  */
406 const struct rt_nexthop *
407 olsr_get_nh(const struct rt_entry *rt)
408 {
409
410   if(rt->rt_best) {
411
412     /* this is a route add/chg - grab nexthop from the best route. */
413     return &rt->rt_best->rtp_nexthop;
414   } 
415   
416   /* this is a route deletion - all routes are gone. */
417   return &rt->rt_nexthop;
418 }
419
420 /**
421  * compare two route paths.
422  *
423  * returns TRUE if the first path is better
424  * than the second one, FALSE otherwise.
425  */
426 static olsr_bool
427 olsr_cmp_rtp(const struct rt_path *rtp1, const struct rt_path *rtp2, const struct rt_path *inetgw)
428 {
429 #ifdef USE_FPM
430     fpm etx1 = rtp1->rtp_metric.etx;
431     fpm etx2 = rtp2->rtp_metric.etx;
432     if (inetgw == rtp1) etx1 = fpmmul(etx1, ftofpm(olsr_cnf->lq_nat_thresh));
433     if (inetgw == rtp2) etx2 = fpmmul(etx2, ftofpm(olsr_cnf->lq_nat_thresh));
434 #else
435     float etx1 = rtp1->rtp_metric.etx;
436     float etx2 = rtp2->rtp_metric.etx;
437     if (inetgw == rtp1) etx1 *= olsr_cnf->lq_nat_thresh;
438     if (inetgw == rtp2) etx2 *= olsr_cnf->lq_nat_thresh;
439 #endif
440
441     /* etx comes first */
442     if (etx1 < etx2) {
443       return OLSR_TRUE;
444     }
445
446     /* hopcount is next tie breaker */
447     if ((etx1 == etx2) &&
448         (rtp1->rtp_metric.hops < rtp2->rtp_metric.hops)) {
449       return OLSR_TRUE;
450     }
451
452     /* originator (which is guaranteed to be unique) is final tie breaker */
453     if ((rtp1->rtp_metric.hops == rtp2->rtp_metric.hops) &&
454         (memcmp(&rtp1->rtp_originator, &rtp2->rtp_originator,
455                 olsr_cnf->ipsize) == -1)) {
456       return OLSR_TRUE;
457     }
458
459     return OLSR_FALSE;
460 }
461
462 /**
463  * compare the best path of two route entries.
464  *
465  * returns TRUE if the first entry is better
466  * than the second one, FALSE otherwise.
467  */
468 olsr_bool
469 olsr_cmp_rt(const struct rt_entry *rt1, const struct rt_entry *rt2)
470 {
471   return olsr_cmp_rtp(rt1->rt_best, rt2->rt_best, NULL);
472 }
473
474 /**
475  * run best route selection among a
476  * set of identical prefixes.
477  */
478 void
479 olsr_rt_best(struct rt_entry *rt)
480 {
481   /* grab the first entry */
482   struct avl_node *node = avl_walk_first(&rt->rt_path_tree);
483
484   assert(node != 0); /* should not happen */
485
486   rt->rt_best = node->data;
487
488   /* walk all remaining originator entries */
489   while ((node = avl_walk_next(node))) {
490     struct rt_path *rtp = node->data;
491
492     if (olsr_cmp_rtp(rtp, rt->rt_best, current_inetgw)) {
493       rt->rt_best = rtp;
494     }
495   }
496
497   if (0 == rt->rt_dst.prefix_len) {
498     current_inetgw = rt->rt_best;
499   }
500 }
501
502 /**
503  * Insert a prefix into the prefix tree hanging off a lsdb (tc) entry.
504  *
505  * Check if the candidate route (we call this a rt_path) is known,
506  * if not create it.
507  * Upon post-SPF processing (if the node is reachable) the prefix
508  * will be finally inserted into the global RIB.
509  *
510  *@param dst the destination
511  *@param plen the prefix length
512  *@param originator the originating router
513  *
514  *@return the new rt_path struct
515  */
516 struct rt_path *
517 olsr_insert_routing_table(union olsr_ip_addr *dst, int plen,
518                           union olsr_ip_addr *originator, int origin)
519 {
520 #if !defined(NODEBUG) && defined(DEBUG)
521   struct ipaddr_str dstbuf, origbuf;
522 #endif
523   struct tc_entry *tc;
524   struct rt_path *rtp;
525   struct avl_node *node;
526   struct olsr_ip_prefix prefix;
527
528   /*
529    * No bogus prefix lengths.
530    */
531   if (plen > olsr_cnf->maxplen) {
532     return NULL;
533   }
534
535 #ifdef DEBUG
536   OLSR_PRINTF(1, "RIB: add prefix %s/%u from %s\n",
537               olsr_ip_to_string(&dstbuf, dst), plen,
538               olsr_ip_to_string(&origbuf, originator));
539 #endif
540
541   /*
542    * For internal routes the tc_entry must already exist.
543    * For all other routes we may create it as an edgeless
544    * hookup point. If so he tc_entry has no edges it will not
545    * be explored during SPF run.
546    */
547   tc = olsr_locate_tc_entry(originator);
548   
549   /*
550    * first check if there is a rt_path for the prefix.
551    */
552   prefix.prefix = *dst;
553   prefix.prefix_len = plen;
554
555   node = avl_find(&tc->prefix_tree, &prefix);
556
557   if (!node) {
558
559     /* no rt_path for this prefix yet */
560     rtp = olsr_alloc_rt_path(tc, &prefix, origin);
561
562     if (!rtp) {
563       return NULL;
564     }
565
566     /* overload the hna change bit for flagging a prefix change */
567     changes_hna = OLSR_TRUE;
568
569   } else {
570     rtp = node->data;
571   }
572
573   return rtp;
574 }
575
576 /**
577  * Delete a prefix from the prefix tree hanging off a lsdb (tc) entry.
578  */
579 void
580 olsr_delete_routing_table(union olsr_ip_addr *dst, int plen,
581                           union olsr_ip_addr *originator)
582 {
583 #if !defined(NODEBUG) && defined(DEBUG)
584   struct ipaddr_str buf;
585 #endif
586
587   struct tc_entry *tc;
588   struct rt_path *rtp;
589   struct avl_node *node;
590   struct olsr_ip_prefix prefix;
591
592   /*
593    * No bogus prefix lengths.
594    */
595   if (plen > olsr_cnf->maxplen) {
596     return;
597   }
598
599 #ifdef DEBUG
600   OLSR_PRINTF(1, "RIB: del prefix %s/%u from %s\n",
601               olsr_ip_to_string(&buf, dst), plen,
602               olsr_ip_to_string(&buf, originator));
603 #endif
604
605   tc = olsr_lookup_tc_entry(originator);
606   if (!tc) {
607     return;
608   }
609
610   /*
611    * Grab the rt_path for the prefix.
612    */
613   prefix.prefix = *dst;
614   prefix.prefix_len = plen;
615
616   node = avl_find(&tc->prefix_tree, &prefix);
617
618   if (node) {
619     rtp = node->data;
620     olsr_free_rt_path(rtp);
621
622     /* overload the hna change bit for flagging a prefix change */
623     changes_hna = OLSR_TRUE;
624   }
625 }
626
627 /**
628  * format a route entry into a buffer
629  */
630 char *
631 olsr_rt_to_string(const struct rt_entry *rt)
632 {
633   static char buff[128];
634   struct ipaddr_str prefixstr, gwstr;
635
636   snprintf(buff, sizeof(buff),
637            "%s/%u via %s",
638            olsr_ip_to_string(&prefixstr, &rt->rt_dst.prefix),
639            rt->rt_dst.prefix_len,
640            olsr_ip_to_string(&gwstr, &rt->rt_nexthop.gateway));
641
642   return buff;
643 }
644
645 /**
646  * format a route path into a buffer
647  */
648 char *
649 olsr_rtp_to_string(const struct rt_path *rtp)
650 {
651   static char buff[128];
652   struct ipaddr_str prefixstr, origstr, gwstr;
653   struct rt_entry *rt = rtp->rtp_rt;
654
655   snprintf(buff, sizeof(buff),
656            "%s/%u from %s via %s, "
657            "etx %s, metric %u, v %u",
658            olsr_ip_to_string(&prefixstr, &rt->rt_dst.prefix),
659            rt->rt_dst.prefix_len,
660            olsr_ip_to_string(&origstr, &rtp->rtp_originator),
661            olsr_ip_to_string(&gwstr, &rtp->rtp_nexthop.gateway),
662            etxtoa(rtp->rtp_metric.etx),
663            rtp->rtp_metric.hops,
664            rtp->rtp_version);
665
666   return buff;
667 }
668
669 /**
670  * Print the routingtree to STDOUT
671  *
672  */
673 void
674 olsr_print_routing_table(const struct avl_tree *tree)
675 {
676 #ifndef NODEBUG
677   /* The whole function makes no sense without it. */
678   const struct avl_node *rt_tree_node;
679
680   OLSR_PRINTF(6, "ROUTING TABLE\n");
681
682   for (rt_tree_node = avl_walk_first_c(tree);
683        rt_tree_node != NULL;
684        rt_tree_node = avl_walk_next_c(rt_tree_node)) {
685     const struct avl_node *rtp_tree_node;
686     struct ipaddr_str prefixstr, origstr, gwstr;
687     const struct rt_entry * const rt = rt_tree_node->data;
688
689     /* first the route entry */
690     OLSR_PRINTF(6, "%s/%u, via %s, best-originator %s\n",
691            olsr_ip_to_string(&prefixstr, &rt->rt_dst.prefix),
692            rt->rt_dst.prefix_len,
693            olsr_ip_to_string(&origstr, &rt->rt_nexthop.gateway),
694            olsr_ip_to_string(&gwstr, &rt->rt_best->rtp_originator));
695
696     /* walk the per-originator path tree of routes */
697     for (rtp_tree_node = avl_walk_first_c(&rt->rt_path_tree);
698          rtp_tree_node != NULL;
699          rtp_tree_node = avl_walk_next_c(rtp_tree_node)) {
700       const struct rt_path * const rtp = rtp_tree_node->data;
701       OLSR_PRINTF(6, "\tfrom %s, etx %s, metric %u, via %s, %s, v %u\n",
702              olsr_ip_to_string(&origstr, &rtp->rtp_originator),
703              etxtoa(rtp->rtp_metric.etx),
704              rtp->rtp_metric.hops,
705              olsr_ip_to_string(&gwstr, &rtp->rtp_nexthop.gateway),
706              if_ifwithindex_name(rt->rt_nexthop.iif_index),
707              rtp->rtp_version);    
708     }
709   }
710 #endif
711   tree = NULL; /* squelch compiler warnings */
712 }
713
714 /*
715  * Local Variables:
716  * c-basic-offset: 2
717  * End:
718  */