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