d9fab3d3049e6b796f02521d110d50cb638657a3
[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;
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 /**
364  * compare two route paths.
365  *
366  * returns TRUE if the first path is better
367  * than the second one, FALSE otherwise.
368  */
369 static olsr_bool
370 olsr_cmp_rtp(const struct rt_path *rtp1, const struct rt_path *rtp2, const struct rt_path *inetgw)
371 {
372     olsr_linkcost etx1 = rtp1->rtp_metric.cost;
373     olsr_linkcost etx2 = rtp2->rtp_metric.cost;
374     if (inetgw == rtp1) etx1 *= olsr_cnf->lq_nat_thresh;
375     if (inetgw == rtp2) etx2 *= olsr_cnf->lq_nat_thresh;
376
377     /* etx comes first */
378     if (etx1 < etx2) {
379       return OLSR_TRUE;
380     }
381
382     /* hopcount is next tie breaker */
383     if ((etx1 == etx2) &&
384         (rtp1->rtp_metric.hops < rtp2->rtp_metric.hops)) {
385       return OLSR_TRUE;
386     }
387
388     /* originator (which is guaranteed to be unique) is final tie breaker */
389     if ((rtp1->rtp_metric.hops == rtp2->rtp_metric.hops) &&
390         (ipcmp(&rtp1->rtp_originator, &rtp2->rtp_originator) < 0)) {
391       return OLSR_TRUE;
392     }
393
394     return OLSR_FALSE;
395 }
396
397 /**
398  * compare the best path of two route entries.
399  *
400  * returns TRUE if the first entry is better
401  * than the second one, FALSE otherwise.
402  */
403 olsr_bool
404 olsr_cmp_rt(const struct rt_entry *rt1, const struct rt_entry *rt2)
405 {
406     return olsr_cmp_rtp(rt1->rt_best, rt2->rt_best, NULL);
407 }
408
409 /**
410  * run best route selection among a
411  * set of identical prefixes.
412  */
413 void
414 olsr_rt_best(struct rt_entry *rt)
415 {
416   /* grab the first entry */
417   struct avl_node *node = avl_walk_first(&rt->rt_path_tree);
418
419   assert(node != 0); /* should not happen */
420
421   rt->rt_best = rtp_tree2rtp(node);
422
423   /* walk all remaining originator entries */
424   while ((node = avl_walk_next(node))) {
425     struct rt_path *rtp = rtp_tree2rtp(node);
426
427     if (olsr_cmp_rtp(rtp, rt->rt_best, current_inetgw)) {
428       rt->rt_best = rtp;
429     }
430   }
431
432   if (0 == rt->rt_dst.prefix_len) {
433     current_inetgw = rt->rt_best;
434   }
435 }
436
437 /**
438  * Insert a prefix into the prefix tree hanging off a lsdb (tc) entry.
439  *
440  * Check if the candidate route (we call this a rt_path) is known,
441  * if not create it.
442  * Upon post-SPF processing (if the node is reachable) the prefix
443  * will be finally inserted into the global RIB.
444  *
445  *@param dst the destination
446  *@param plen the prefix length
447  *@param originator the originating router
448  *
449  *@return the new rt_path struct
450  */
451 struct rt_path *
452 olsr_insert_routing_table(const union olsr_ip_addr *dst, int plen,
453                           const union olsr_ip_addr *originator, int origin)
454 {
455 #ifdef DEBUG
456   struct ipaddr_str dstbuf, origbuf;
457 #endif
458   struct tc_entry *tc;
459   struct rt_path *rtp;
460   struct avl_node *node;
461   struct olsr_ip_prefix prefix;
462
463   /*
464    * No bogus prefix lengths.
465    */
466   if (plen > olsr_cnf->maxplen) {
467     return NULL;
468   }
469
470   /*
471    * For all routes we use the tc_entry as an hookup point.
472    * If the tc_entry is disconnected, i.e. has no edges it will not
473    * be explored during SPF run.
474    */
475   tc = olsr_locate_tc_entry(originator);
476   
477   /*
478    * first check if there is a rt_path for the prefix.
479    */
480   prefix.prefix = *dst;
481   prefix.prefix_len = plen;
482
483   node = avl_find(&tc->prefix_tree, &prefix);
484
485   if (!node) {
486
487     /* no rt_path for this prefix yet */
488     rtp = olsr_alloc_rt_path(tc, &prefix, origin);
489
490     if (!rtp) {
491       return NULL;
492     }
493
494 #ifdef DEBUG
495     OLSR_PRINTF(1, "RIB: add prefix %s/%u from %s\n",
496                 olsr_ip_to_string(&dstbuf, dst), plen,
497                 olsr_ip_to_string(&origbuf, originator));
498 #endif
499
500     /* overload the hna change bit for flagging a prefix change */
501     changes_hna = OLSR_TRUE;
502
503   } else {
504     rtp = rtp_prefix_tree2rtp(node);
505   }
506
507   return rtp;
508 }
509
510 /**
511  * Delete a prefix from the prefix tree hanging off a lsdb (tc) entry.
512  */
513 void
514 olsr_delete_routing_table(union olsr_ip_addr *dst, int plen,
515                           union olsr_ip_addr *originator)
516 {
517 #ifdef DEBUG
518   struct ipaddr_str dstbuf, origbuf;
519 #endif
520
521   struct tc_entry *tc;
522   struct rt_path *rtp;
523   struct avl_node *node;
524   struct olsr_ip_prefix prefix;
525
526   /*
527    * No bogus prefix lengths.
528    */
529   if (plen > olsr_cnf->maxplen) {
530     return;
531   }
532
533   tc = olsr_lookup_tc_entry(originator);
534   if (!tc) {
535     return;
536   }
537
538   /*
539    * Grab the rt_path for the prefix.
540    */
541   prefix.prefix = *dst;
542   prefix.prefix_len = plen;
543
544   node = avl_find(&tc->prefix_tree, &prefix);
545
546   if (node) {
547     rtp = rtp_prefix_tree2rtp(node);
548     olsr_delete_rt_path(rtp);
549
550 #ifdef DEBUG
551     OLSR_PRINTF(1, "RIB: del prefix %s/%u from %s\n",
552                 olsr_ip_to_string(&dstbuf, dst), plen,
553                 olsr_ip_to_string(&origbuf, originator));
554 #endif
555
556     /* overload the hna change bit for flagging a prefix change */
557     changes_hna = OLSR_TRUE;
558   }
559 }
560
561 /**
562  * format a route entry into a buffer
563  */
564 char *
565 olsr_rt_to_string(const struct rt_entry *rt)
566 {
567   static char buff[128];
568   struct ipaddr_str gwstr;
569   struct ipprefix_str prefixstr;
570
571   snprintf(buff, sizeof(buff),
572            "%s via %s",
573            olsr_ip_prefix_to_string(&prefixstr, &rt->rt_dst),
574            olsr_ip_to_string(&gwstr, &rt->rt_nexthop.gateway));
575
576   return buff;
577 }
578
579 /**
580  * format a route path into a buffer
581  */
582 char *
583 olsr_rtp_to_string(const struct rt_path *rtp)
584 {
585   static char buff[128];
586   struct ipaddr_str origstr, gwstr;
587   struct lqtextbuffer lqbuffer;
588   struct ipprefix_str prefixstr;
589
590   snprintf(buff, sizeof(buff),
591            "%s from %s via %s, "
592            "cost %s, metric %u, v %u",
593            olsr_ip_prefix_to_string(&prefixstr, &rtp->rtp_rt->rt_dst),
594            olsr_ip_to_string(&origstr, &rtp->rtp_originator),
595            olsr_ip_to_string(&gwstr, &rtp->rtp_nexthop.gateway),
596            get_linkcost_text(rtp->rtp_metric.cost, OLSR_TRUE, &lqbuffer),
597            rtp->rtp_metric.hops,
598            rtp->rtp_version);
599
600   return buff;
601 }
602
603 /**
604  * Print the routingtree to STDOUT
605  *
606  */
607 void
608 olsr_print_routing_table(struct avl_tree *tree USED_ONLY_FOR_DEBUG)
609 {
610   /* The whole function makes no sense without it. */
611 #ifndef NODEBUG
612   struct avl_node *rt_tree_node;
613   struct lqtextbuffer lqbuffer;
614   
615   OLSR_PRINTF(6, "ROUTING TABLE\n");
616
617   for (rt_tree_node = avl_walk_first(tree);
618        rt_tree_node != NULL;
619        rt_tree_node = avl_walk_next(rt_tree_node)) {
620     struct avl_node *rtp_tree_node;
621     struct ipaddr_str origstr, gwstr;
622     struct ipprefix_str prefixstr;
623     struct rt_entry *rt = rt_tree2rt(rt_tree_node);
624
625     /* first the route entry */
626     OLSR_PRINTF(6, "%s, via %s, best-originator %s\n",
627            olsr_ip_prefix_to_string(&prefixstr, &rt->rt_dst),
628            olsr_ip_to_string(&origstr, &rt->rt_nexthop.gateway),
629            olsr_ip_to_string(&gwstr, &rt->rt_best->rtp_originator));
630
631     /* walk the per-originator path tree of routes */
632     for (rtp_tree_node = avl_walk_first(&rt->rt_path_tree);
633          rtp_tree_node != NULL;
634          rtp_tree_node = avl_walk_next(rtp_tree_node)) {
635       struct rt_path *rtp = rtp_tree2rtp(rtp_tree_node);
636       OLSR_PRINTF(6, "\tfrom %s, cost %s, metric %u, via %s, %s, v %u\n",
637              olsr_ip_to_string(&origstr, &rtp->rtp_originator),
638              get_linkcost_text(rtp->rtp_metric.cost, OLSR_TRUE, &lqbuffer),
639              rtp->rtp_metric.hops,
640              olsr_ip_to_string(&gwstr, &rtp->rtp_nexthop.gateway),
641              if_ifwithindex_name(rt->rt_nexthop.iif_index),
642              rtp->rtp_version);    
643     }
644   }
645 #endif
646 }
647
648 /*
649  * Local Variables:
650  * c-basic-offset: 2
651  * indent-tabs-mode: nil
652  * End:
653  */