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