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