* creating builddata.c containing build time information as date+time,
[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.31 2007/09/16 21:20:17 bernd67 Exp $
41  */
42
43 #include "defs.h"
44 #include "two_hop_neighbor_table.h"
45 #include "tc_set.h"
46 #include "mid_set.h"
47 #include "neighbor_table.h"
48 #include "olsr.h"
49 #include "link_set.h"
50 #include "routing_table.h"
51 #include "lq_avl.h"
52 #include "lq_route.h"
53 #include "assert.h"
54
55 struct avl_tree routingtree;
56 unsigned int routingtree_version;
57
58 /**
59  * Bump the version number of the routing tree.
60  *
61  * After route-insertion compare the version number of the routes
62  * against the version number of the table.
63  * This is a lightweight detection if a node or prefix went away,
64  * rather than brute force old vs. new rt_entry comparision.
65  */
66 unsigned int
67 olsr_bump_routingtree_version(void)
68 {
69   return(routingtree_version++);
70 }
71
72 /**
73  * avl_comp_ipv4_prefix
74  *
75  * compare two ipv4 prefixes.
76  * first compare the prefixes, then
77  *  then compare the prefix lengths.
78  *
79  * return 0 if there is an exact match and
80  * -1 / +1 depending on being smaller or bigger.
81  */
82 int
83 avl_comp_ipv4_prefix (void *prefix1, void *prefix2)
84 {       
85   struct olsr_ip_prefix *pfx1, *pfx2;
86
87   pfx1 = prefix1;
88   pfx2 = prefix2;
89
90   /* prefix */
91   if (pfx1->prefix.v4 < pfx2->prefix.v4) {
92     return -1;
93   }
94   if (pfx1->prefix.v4 > pfx2->prefix.v4) {
95     return +1;
96   }
97
98   /* prefix length */
99   if (pfx1->prefix_len < pfx2->prefix_len) {
100     return -1;
101   }
102   if (pfx1->prefix_len > pfx2->prefix_len) {
103     return +1;
104   }
105
106   return 0;
107 }
108
109 /**
110  * avl_comp_ipv6_prefix
111  *
112  * compare two ipv6 prefixes.
113  * first compare the prefixes, then
114  *  then compare the prefix lengths.
115  *
116  * return 0 if there is an exact match and
117  * -1 / +1 depending on being smaller or bigger.
118  */
119 int
120 avl_comp_ipv6_prefix (void *prefix1, void *prefix2)
121 {       
122   struct olsr_ip_prefix *pfx1, *pfx2;
123   int res;
124
125   pfx1 = prefix1;
126   pfx2 = prefix2;
127
128   /* prefix */
129   res = memcmp(&pfx1->prefix.v6, &pfx2->prefix.v6, 16);
130   if (res != 0) {
131     return res;
132   } 
133   /* prefix length */
134   if (pfx1->prefix_len < pfx2->prefix_len) {
135     return -1;
136   }
137   if (pfx1->prefix_len > pfx2->prefix_len) {
138     return +1;
139   }
140
141   return 0;
142 }
143
144 /**
145  * Initialize the routingtree and kernel change queues.
146  */
147 int
148 olsr_init_routing_table(void)
149 {
150   /* the routing tree */
151   avl_init(&routingtree, avl_comp_prefix_default);
152   routingtree_version = 0;
153
154   /* the add/chg/del kernel queues */
155   list_head_init(&add_kernel_list);
156   list_head_init(&chg_kernel_list);
157   list_head_init(&del_kernel_list);
158
159   return 1;
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   COPY_IP(&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 the fields in an routing entry.
186  * Depending on the update mask update either the old,
187  * the new or both arrays for gateway/interface/etx/hopcount.
188  */
189 static void
190 olsr_update_routing_entry(struct rt_path *rtp, union olsr_ip_addr *gateway,
191                           int iif_index, int metric, float etx)
192 {
193
194   rtp->rtp_version = routingtree_version;
195
196   /* gateway */
197   rtp->rtp_nexthop.gateway = *gateway;
198
199   /* interface */
200   rtp->rtp_nexthop.iif_index = iif_index;
201
202   /* etx */
203   rtp->rtp_metric.hops = metric;
204   if (etx < 0.0) {
205     /* non-LQ case */
206     rtp->rtp_metric.etx = (float)metric;
207   } else {
208     /* LQ case */
209     rtp->rtp_metric.etx = etx;
210   }
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;
220
221   rt = olsr_malloc(sizeof(struct rt_entry), __FUNCTION__);
222
223   if (!rt) {
224     return NULL;
225   }
226
227   memset(rt, 0, sizeof(struct rt_entry));
228   
229   /* Mark this entry as fresh (see process_routes.c:512) */
230   rt->rt_nexthop.iif_index = -1;
231
232   /* set key and backpointer prior to tree insertion */
233   rt->rt_dst = *prefix;
234
235   rt->rt_tree_node.key = &rt->rt_dst;
236   rt->rt_tree_node.data = rt;
237   avl_insert(&routingtree, &rt->rt_tree_node, AVL_DUP_NO);
238
239   /* init the originator subtree */
240   avl_init(&rt->rt_path_tree, avl_comp_default);
241
242   return rt;
243 }
244
245
246 /**
247  * Alloc and key a new rt_path.
248  */
249 static struct rt_path *
250 olsr_alloc_rt_path(struct rt_entry *rt,
251                    union olsr_ip_addr *originator)
252 {
253   struct rt_path *rtp;
254
255   rtp = olsr_malloc(sizeof(struct rt_path), __FUNCTION__);
256
257   if (!rtp) {
258     return NULL;
259   }
260
261   memset(rtp, 0, sizeof(struct rt_path));
262
263   COPY_IP(&rtp->rtp_originator, originator);
264
265   /* set key and backpointer prior to tree insertion */
266   rtp->rtp_tree_node.key = &rtp->rtp_originator;
267   rtp->rtp_tree_node.data = rtp;
268
269   /* insert to the route entry originator tree */
270   avl_insert(&rt->rt_path_tree, &rtp->rtp_tree_node, AVL_DUP_NO);
271
272   /* backlink to the owning route entry */
273   rtp->rtp_rt = rt;
274
275   return rtp;
276 }
277
278 /**
279  * Check if there is an interface or gateway change.
280  */
281 olsr_bool
282 olsr_nh_change(struct rt_nexthop *nh1, struct rt_nexthop *nh2)
283 {
284   if ((!COMP_IP(&nh1->gateway, &nh2->gateway)) ||
285       (nh1->iif_index != nh2->iif_index)) {
286     return OLSR_TRUE;
287   }
288   return OLSR_FALSE;
289 }
290
291 /**
292  * depending on the operation (add/chg/del) the nexthop
293  * field from the route entry or best route path shall be used.
294  */
295 const struct rt_nexthop *
296 olsr_get_nh(const struct rt_entry *rt)
297 {
298
299   if(rt->rt_best) {
300
301     /* this is a route add/chg - grab nexthop from the best route. */
302     return &rt->rt_best->rtp_nexthop;
303   } 
304   
305   /* this is a route deletion - all routes are gone. */
306   return &rt->rt_nexthop;
307 }
308
309 /**
310  * compare two route paths.
311  *
312  * returns TRUE if the first path is better
313  * than the second one, FALSE otherwise.
314  */
315 static olsr_bool
316 olsr_cmp_rtp(struct rt_path *rtp1, struct rt_path *rtp2)
317 {
318    /* etx comes first */
319     if (rtp1->rtp_metric.etx < rtp2->rtp_metric.etx) {
320       return OLSR_TRUE;
321     }
322
323     /* hopcount is next tie breaker */
324     if ((rtp1->rtp_metric.etx == rtp2->rtp_metric.etx) &&
325         (rtp1->rtp_metric.hops < rtp2->rtp_metric.hops)) {
326       return OLSR_TRUE;
327     }
328
329     /* originator (which is guaranteed to be unique) is final tie breaker */
330     if ((rtp1->rtp_metric.hops == rtp2->rtp_metric.hops) &&
331         (memcmp(&rtp1->rtp_originator, &rtp2->rtp_originator,
332                 olsr_cnf->ipsize) == -1)) {
333       return OLSR_TRUE;
334     }
335
336     return OLSR_FALSE;
337 }
338
339 /**
340  * compare the best path of two route entries.
341  *
342  * returns TRUE if the first entry is better
343  * than the second one, FALSE otherwise.
344  */
345 olsr_bool
346 olsr_cmp_rt(struct rt_entry *rt1, struct rt_entry *rt2)
347 {
348   return(olsr_cmp_rtp(rt1->rt_best, rt2->rt_best));
349 }
350
351 /**
352  * run best route selection among a
353  * set of identical prefixes.
354  */
355 void
356 olsr_rt_best(struct rt_entry *rt)
357 {
358   struct rt_path *rtp;
359   struct avl_node *node;
360
361   /* grab the first entry */
362   node = avl_walk_first(&rt->rt_path_tree);
363
364   if (!node) {
365     assert(0); /* should not happen */
366   }
367
368   rt->rt_best = node->data;
369
370   /* walk all remaining originator entries */
371   while ((node = avl_walk_next(node))) {
372
373     rtp = node->data;
374
375     if (olsr_cmp_rtp(rtp, rt->rt_best)) {
376       rt->rt_best = rtp;
377     }
378   }
379 }
380
381 /**
382  * Insert/Update a route entry into the routing table.
383  *
384  * Check is the route exisits and depending if this is a
385  * new version of the RIB do a full inplace update.
386  * If there is already a route from this table version then 
387  * check if the new route is better.
388  *
389  * For exisiting routes only interface or gateway router changes
390  * do trigger a kernel change.
391  *
392  *@param dst the destination
393  *@param plen the prefix length
394  *@param gateway the next-hop router
395  *@param iface the next-hop interface
396  *@param metric the hopcount
397  *@param etx the LQ extension metric
398  *
399  *@return the new rt_entry struct
400  */
401 struct rt_path *
402 olsr_insert_routing_table(union olsr_ip_addr *dst, 
403                           int plen,
404                           union olsr_ip_addr *originator,
405                           union olsr_ip_addr *gateway,
406                           int iif_index,
407                           int metric,
408                           float etx)
409 {
410   struct rt_entry *rt;
411   struct rt_path *rtp;
412   struct avl_node *node;
413   struct olsr_ip_prefix prefix;
414
415   /*
416    * no unreachable routes please.
417    */
418   if (etx >= INFINITE_ETX) {
419     return NULL;
420   }
421
422   /*
423    * first check if there is a route_entry for the prefix.
424    */
425   prefix.prefix = *dst;
426   prefix.prefix_len = plen;
427
428   node = avl_find(&routingtree, &prefix);
429
430   if (!node) {
431
432     /* no route entry yet */
433     rt = olsr_alloc_rt_entry(&prefix);
434
435     if (!rt) {
436       return NULL;
437     }
438
439   } else {
440     rt = node->data;
441   }
442
443   /*
444    * next check if the route path from this originator is known
445    */
446   node = avl_find(&rt->rt_path_tree, originator);
447
448   if (!node) {
449
450     /* no route path from this originator yet */
451     rtp = olsr_alloc_rt_path(rt, originator);
452
453     if (!rtp) {
454       return NULL;
455     }
456
457   } else {
458     rtp = node->data;
459   }
460
461   /* update the version field and relevant parameters */
462   olsr_update_routing_entry(rtp, gateway, iif_index, metric, etx);
463
464   return rtp;
465 }
466
467 /**
468  * format a route entry into a buffer
469  */
470 char *
471 olsr_rt_to_string(struct rt_entry *rt)
472 {
473   static char buff[128];
474
475   snprintf(buff, sizeof(buff),
476            "%s/%u via %s",
477            olsr_ip_to_string(&rt->rt_dst.prefix),
478            rt->rt_dst.prefix_len,
479            olsr_ip_to_string(&rt->rt_nexthop.gateway));
480
481   return buff;
482 }
483
484 /**
485  * format a route path into a buffer
486  */
487 char *
488 olsr_rtp_to_string(struct rt_path *rtp)
489 {
490   struct rt_entry *rt;
491   static char buff[128];
492
493   rt = rtp->rtp_rt;
494
495   snprintf(buff, sizeof(buff),
496            "%s/%u from %s via %s, "
497            "etx %.3f, metric %u, v %u",
498            olsr_ip_to_string(&rt->rt_dst.prefix),
499            rt->rt_dst.prefix_len,
500            olsr_ip_to_string(&rtp->rtp_originator),
501            olsr_ip_to_string(&rtp->rtp_nexthop.gateway),
502            rtp->rtp_metric.etx,
503            rtp->rtp_metric.hops,
504            rtp->rtp_version);
505
506   return buff;
507 }
508
509 /**
510  *Insert all the one hop neighbors in the routing table.
511  *
512  *@return
513  */
514 int
515 olsr_fill_routing_table_with_neighbors(void)
516 {
517   int index;
518   float etx;
519
520 #ifdef DEBUG
521   OLSR_PRINTF(7, "FILL ROUTING TABLE WITH NEIGHBORS\n");
522 #endif
523
524   for (index=0;index<HASHSIZE;index++) {
525
526     struct neighbor_entry *neighbor;
527
528     for(neighbor = neighbortable[index].next;
529         neighbor != &neighbortable[index];
530         neighbor=neighbor->next) {
531
532       if (neighbor->status == SYM) {
533
534         static struct mid_address addrs;
535         struct mid_address *addrs2;
536
537         /*
538          * Insert all the neighbors addresses
539          */
540         COPY_IP(&addrs.alias, &neighbor->neighbor_main_addr);
541         addrs.next_alias = mid_lookup_aliases(&neighbor->neighbor_main_addr);
542
543         for (addrs2 = &addrs; addrs2; addrs2 = addrs2->next_alias) {
544
545           struct link_entry *link;
546
547           link = get_best_link_to_neighbor(&addrs2->alias);
548
549 #ifdef DEBUG
550           OLSR_PRINTF(7, "(ROUTE)Adding neighbor %s\n", olsr_ip_to_string(&addrs.alias));
551 #endif
552           if (link) {
553
554             struct interface *iface;
555
556             iface = link->if_name ? if_ifwithname(link->if_name) :
557               if_ifwithaddr(&link->local_iface_addr);
558
559             etx = 1.0 / (link->loss_link_quality2 * link->neigh_link_quality2);
560
561             if (iface) {
562
563               /* neighbor main IP address */
564               olsr_insert_routing_table(&link->neighbor_iface_addr, olsr_cnf->maxplen,
565                                         &link->neighbor->neighbor_main_addr,
566                                         &link->neighbor_iface_addr,
567                                         iface->if_index, 1, etx);
568
569               /* this is the nexthop route that all routes will be tracking */
570               olsr_insert_routing_table(&addrs2->alias, olsr_cnf->maxplen,
571                                         &link->neighbor->neighbor_main_addr,
572                                         &link->neighbor_iface_addr,
573                                         iface->if_index, 1, etx);
574             }
575           }
576         }
577       }
578     }
579   }
580   return 1;
581 }
582
583
584 /**
585  *Calculate the HNA routes
586  *
587  */
588 void
589 olsr_calculate_hna_routes(void)
590 {
591   int index, plen;
592   struct rt_entry *rt;
593
594 #ifdef DEBUG
595   OLSR_PRINTF(3, "Calculating HNA routes\n");
596 #endif
597
598   for(index=0;index<HASHSIZE;index++)
599   {
600     struct hna_entry *tmp_hna;
601     /* All entries */
602     for(tmp_hna = hna_set[index].next;
603         tmp_hna != &hna_set[index];
604         tmp_hna = tmp_hna->next)
605     {
606       struct hna_net *tmp_net;
607       /* All networks */
608       for(tmp_net = tmp_hna->networks.next;
609           tmp_net != &tmp_hna->networks;
610           tmp_net = tmp_net->next) {
611
612         /* If no route to gateway - skip */
613         if((rt = olsr_lookup_routing_table(&tmp_hna->A_gateway_addr)) == NULL)
614           continue;
615
616         /* update if better */
617         plen = olsr_get_hna_prefix_len(tmp_net);
618         olsr_insert_routing_table(&tmp_net->A_network_addr, plen,
619                                   &tmp_hna->A_gateway_addr,
620                                   &rt->rt_best->rtp_nexthop.gateway,
621                                   rt->rt_best->rtp_nexthop.iif_index,
622                                   rt->rt_best->rtp_metric.hops,
623                                   rt->rt_best->rtp_metric.etx);
624
625       }
626     }
627   }
628
629   /* Update kernel */
630   olsr_update_kernel_routes();
631 }
632
633 /**
634  * Print the routingtree to STDOUT
635  *
636  */
637 void
638 olsr_print_routing_table(struct avl_tree *tree)
639 {
640   struct rt_entry *rt;
641   struct rt_path *rtp;
642
643   struct avl_node *rt_tree_node, *rtp_tree_node;
644
645   printf("ROUTING TABLE\n");
646
647   for (rt_tree_node = avl_walk_first(tree);
648        rt_tree_node;
649        rt_tree_node = avl_walk_next(rt_tree_node)) {
650
651     rt = rt_tree_node->data;
652
653     /* first the route entry */
654     printf("%s/%u, via %s, best-originator %s\n",
655            olsr_ip_to_string(&rt->rt_dst.prefix),
656            rt->rt_dst.prefix_len,
657            olsr_ip_to_string(&rt->rt_nexthop.gateway),
658            olsr_ip_to_string(&rt->rt_best->rtp_originator));
659
660     /* walk the per-originator path tree of routes */
661     for (rtp_tree_node = avl_walk_first(&rt->rt_path_tree);
662          rtp_tree_node;
663          rtp_tree_node = avl_walk_next(rtp_tree_node)) {
664
665       rtp = rtp_tree_node->data;
666
667       printf("\tfrom %s, etx %.3f, metric %u, via %s, %s, v %u\n",
668              olsr_ip_to_string(&rtp->rtp_originator),
669              rtp->rtp_metric.etx,
670              rtp->rtp_metric.hops,
671              olsr_ip_to_string(&rtp->rtp_nexthop.gateway),
672              if_ifwithindex_name(rt->rt_nexthop.iif_index),
673              rtp->rtp_version);
674     
675     }
676   }
677 }
678
679 /*
680  * Local Variables:
681  * c-basic-offset: 2
682  * End:
683  */