* applied rt-refactoring-6.diff from Hannes Gredler <hannes@gredler.at>
[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.29 2007/09/05 16:11:11 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(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_host_rt_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                           struct interface *iface, 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.iface = iface;
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   /* set key and backpointer prior to tree insertion */
230   rt->rt_dst = *prefix;
231
232   rt->rt_tree_node.key = &rt->rt_dst;
233   rt->rt_tree_node.data = rt;
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 /**
244  * Alloc and key a new rt_path.
245  */
246 static struct rt_path *
247 olsr_alloc_rt_path(struct rt_entry *rt,
248                    union olsr_ip_addr *originator)
249 {
250   struct rt_path *rtp;
251
252   rtp = olsr_malloc(sizeof(struct rt_path), __FUNCTION__);
253
254   if (!rtp) {
255     return NULL;
256   }
257
258   memset(rtp, 0, sizeof(struct rt_path));
259
260   COPY_IP(&rtp->rtp_originator, originator);
261
262   /* set key and backpointer prior to tree insertion */
263   rtp->rtp_tree_node.key = &rtp->rtp_originator;
264   rtp->rtp_tree_node.data = rtp;
265
266   /* insert to the route entry originator tree */
267   avl_insert(&rt->rt_path_tree, &rtp->rtp_tree_node, AVL_DUP_NO);
268
269   /* backlink to the owning route entry */
270   rtp->rtp_rt = rt;
271
272   return rtp;
273 }
274
275 /**
276  * Check if there is an interface or gateway change.
277  */
278 olsr_bool
279 olsr_nh_change(struct rt_nexthop *nh1, struct rt_nexthop *nh2)
280 {
281   if ((!COMP_IP(&nh1->gateway, &nh2->gateway)) ||
282       (nh1->iface != nh2->iface)) {
283     return OLSR_TRUE;
284   }
285   return OLSR_FALSE;
286 }
287
288 /**
289  * depending on the operation (add/chg/del) the nexthop
290  * field from the route entry or best route path shall be used.
291  */
292 struct rt_nexthop *
293 olsr_get_nh(struct rt_entry *rt)
294 {
295
296   if(rt->rt_best) {
297
298     /* this is a route add/chg - grab nexthop from the best route. */
299     return &rt->rt_best->rtp_nexthop;
300   } 
301   
302   /* this is a route deletion - all routes are gone. */
303   return &rt->rt_nexthop;
304 }
305
306 /**
307  * compare two route paths.
308  *
309  * returns TRUE if the first path is better
310  * than the second one, FALSE otherwise.
311  */
312 static olsr_bool
313 olsr_cmp_rtp(struct rt_path *rtp1, struct rt_path *rtp2)
314 {
315    /* etx comes first */
316     if (rtp1->rtp_metric.etx < rtp2->rtp_metric.etx) {
317       return OLSR_TRUE;
318     }
319
320     /* hopcount is next tie breaker */
321     if ((rtp1->rtp_metric.etx == rtp2->rtp_metric.etx) &&
322         (rtp1->rtp_metric.hops < rtp2->rtp_metric.hops)) {
323       return OLSR_TRUE;
324     }
325
326     /* originator (which is guaranteed to be unique) is final tie breaker */
327     if ((rtp1->rtp_metric.hops == rtp2->rtp_metric.hops) &&
328         (memcmp(&rtp1->rtp_originator, &rtp2->rtp_originator,
329                 olsr_cnf->ipsize) == -1)) {
330       return OLSR_TRUE;
331     }
332
333     return OLSR_FALSE;
334 }
335
336 /**
337  * compare the best path of two route entries.
338  *
339  * returns TRUE if the first entry is better
340  * than the second one, FALSE otherwise.
341  */
342 olsr_bool
343 olsr_cmp_rt(struct rt_entry *rt1, struct rt_entry *rt2)
344 {
345   return(olsr_cmp_rtp(rt1->rt_best, rt2->rt_best));
346 }
347
348 /**
349  * run best route selection among a
350  * set of identical prefixes.
351  */
352 void
353 olsr_rt_best(struct rt_entry *rt)
354 {
355   struct rt_path *rtp;
356   struct avl_node *node;
357
358   /* grab the first entry */
359   node = avl_walk_first(&rt->rt_path_tree);
360
361   if (!node) {
362     assert(0); /* should not happen */
363   }
364
365   rt->rt_best = node->data;
366
367   /* walk all remaining originator entries */
368   while ((node = avl_walk_next(node))) {
369
370     rtp = node->data;
371
372     if (olsr_cmp_rtp(rtp, rt->rt_best)) {
373       rt->rt_best = rtp;
374     }
375   }
376 }
377
378 /**
379  * Insert/Update a route entry into the routing table.
380  *
381  * Check is the route exisits and depending if this is a
382  * new version of the RIB do a full inplace update.
383  * If there is already a route from this table version then 
384  * check if the new route is better.
385  *
386  * For exisiting routes only interface or gateway router changes
387  * do trigger a kernel change.
388  *
389  *@param dst the destination
390  *@param plen the prefix length
391  *@param gateway the next-hop router
392  *@param iface the next-hop interface
393  *@param metric the hopcount
394  *@param etx the LQ extension metric
395  *
396  *@return the new rt_entry struct
397  */
398 struct rt_path *
399 olsr_insert_routing_table(union olsr_ip_addr *dst, 
400                           int plen,
401                           union olsr_ip_addr *originator,
402                           union olsr_ip_addr *gateway,
403                           struct interface *iface, 
404                           int metric,
405                           float etx)
406 {
407   struct rt_entry *rt;
408   struct rt_path *rtp;
409   struct avl_node *node;
410   struct olsr_ip_prefix prefix;
411
412   /*
413    * no unreachable routes please.
414    */
415   if (etx >= INFINITE_ETX) {
416     return NULL;
417   }
418
419   /*
420    * first check if there is a route_entry for the prefix.
421    */
422   prefix.prefix = *dst;
423   prefix.prefix_len = plen;
424
425   node = avl_find(&routingtree, &prefix);
426
427   if (!node) {
428
429     /* no route entry yet */
430     rt = olsr_alloc_rt_entry(&prefix);
431
432     if (!rt) {
433       return NULL;
434     }
435
436   } else {
437     rt = node->data;
438   }
439
440   /*
441    * next check if the route path from this originator is known
442    */
443   node = avl_find(&rt->rt_path_tree, originator);
444
445   if (!node) {
446
447     /* no route path from this originator yet */
448     rtp = olsr_alloc_rt_path(rt, originator);
449
450     if (!rtp) {
451       return NULL;
452     }
453
454   } else {
455     rtp = node->data;
456   }
457
458   /* update the version field and relevant parameters */
459   olsr_update_routing_entry(rtp, gateway, iface, metric, etx);
460
461   return rtp;
462 }
463
464 /**
465  * format a route entry into a buffer
466  */
467 char *
468 olsr_rt_to_string(struct rt_entry *rt)
469 {
470   static char buff[128];
471
472   snprintf(buff, sizeof(buff),
473            "%s/%u via %s",
474            olsr_ip_to_string(&rt->rt_dst.prefix),
475            rt->rt_dst.prefix_len,
476            olsr_ip_to_string(&rt->rt_nexthop.gateway));
477
478   return buff;
479 }
480
481 /**
482  * format a route path into a buffer
483  */
484 char *
485 olsr_rtp_to_string(struct rt_path *rtp)
486 {
487   struct rt_entry *rt;
488   static char buff[128];
489
490   rt = rtp->rtp_rt;
491
492   snprintf(buff, sizeof(buff),
493            "%s/%u from %s via %s, "
494            "etx %.3f, metric %u, v %u",
495            olsr_ip_to_string(&rt->rt_dst.prefix),
496            rt->rt_dst.prefix_len,
497            olsr_ip_to_string(&rtp->rtp_originator),
498            olsr_ip_to_string(&rtp->rtp_nexthop.gateway),
499            rtp->rtp_metric.etx,
500            rtp->rtp_metric.hops,
501            rtp->rtp_version);
502
503   return buff;
504 }
505
506 /**
507  *Insert all the one hop neighbors in the routing table.
508  *
509  *@return
510  */
511 int
512 olsr_fill_routing_table_with_neighbors(void)
513 {
514   int index, max_host_plen;
515   float etx;
516
517 #ifdef DEBUG
518   OLSR_PRINTF(7, "FILL ROUTING TABLE WITH NEIGHBORS\n");
519 #endif
520
521   max_host_plen = olsr_host_rt_maxplen();
522
523   for (index=0;index<HASHSIZE;index++) {
524
525     struct neighbor_entry *neighbor;
526
527     for(neighbor = neighbortable[index].next;
528         neighbor != &neighbortable[index];
529         neighbor=neighbor->next) {
530
531       if (neighbor->status == SYM) {
532
533         static struct mid_address addrs;
534         struct mid_address *addrs2;
535
536         /*
537          * Insert all the neighbors addresses
538          */
539         COPY_IP(&addrs.alias, &neighbor->neighbor_main_addr);
540         addrs.next_alias = mid_lookup_aliases(&neighbor->neighbor_main_addr);
541
542         for (addrs2 = &addrs; addrs2; addrs2 = addrs2->next_alias) {
543
544           struct link_entry *link;
545
546           link = get_best_link_to_neighbor(&addrs2->alias);
547
548 #ifdef DEBUG
549           OLSR_PRINTF(7, "(ROUTE)Adding neighbor %s\n", olsr_ip_to_string(&addrs.alias));
550 #endif
551           if (link) {
552
553             struct interface *iface;
554
555             iface = link->if_name ? if_ifwithname(link->if_name) :
556               if_ifwithaddr(&link->local_iface_addr);
557
558             etx = 1.0 / (link->loss_link_quality2 * link->neigh_link_quality2);
559
560             if (iface) {
561
562               /* neighbor main IP address */
563               olsr_insert_routing_table(&link->neighbor_iface_addr, max_host_plen,
564                                         &link->neighbor->neighbor_main_addr,
565                                         &link->neighbor_iface_addr,
566                                         iface, 1, etx);
567
568               /* this is the nexthop route that all routes will be tracking */
569               olsr_insert_routing_table(&addrs2->alias, max_host_plen,
570                                         &link->neighbor->neighbor_main_addr,
571                                         &link->neighbor_iface_addr,
572                                         iface, 1, etx);
573             }
574           }
575         }
576       }
577     }
578   }
579   return 1;
580 }
581
582
583 /**
584  *Calculate the HNA routes
585  *
586  */
587 void
588 olsr_calculate_hna_routes(void)
589 {
590   int index, plen;
591   struct rt_entry *rt;
592
593 #ifdef DEBUG
594   OLSR_PRINTF(3, "Calculating HNA routes\n");
595 #endif
596
597   for(index=0;index<HASHSIZE;index++)
598   {
599     struct hna_entry *tmp_hna;
600     /* All entries */
601     for(tmp_hna = hna_set[index].next;
602         tmp_hna != &hna_set[index];
603         tmp_hna = tmp_hna->next)
604     {
605       struct hna_net *tmp_net;
606       /* All networks */
607       for(tmp_net = tmp_hna->networks.next;
608           tmp_net != &tmp_hna->networks;
609           tmp_net = tmp_net->next) {
610
611         /* If no route to gateway - skip */
612         if((rt = olsr_lookup_routing_table(&tmp_hna->A_gateway_addr)) == NULL)
613           continue;
614
615         /* update if better */
616         plen = olsr_get_hna_prefix_len(tmp_net);
617         olsr_insert_routing_table(&tmp_net->A_network_addr, plen,
618                                   &tmp_hna->A_gateway_addr,
619                                   &rt->rt_best->rtp_nexthop.gateway,
620                                   rt->rt_best->rtp_nexthop.iface,
621                                   rt->rt_best->rtp_metric.hops,
622                                   rt->rt_best->rtp_metric.etx);
623
624       }
625     }
626   }
627
628   /* Update kernel */
629   olsr_update_kernel_routes();
630 }
631
632 /**
633  * Print the routingtree to STDOUT
634  *
635  */
636 void
637 olsr_print_routing_table(struct avl_tree *tree)
638 {
639   struct rt_entry *rt;
640   struct rt_path *rtp;
641
642   struct avl_node *rt_tree_node, *rtp_tree_node;
643
644   printf("ROUTING TABLE\n");
645
646   for (rt_tree_node = avl_walk_first(tree);
647        rt_tree_node;
648        rt_tree_node = avl_walk_next(rt_tree_node)) {
649
650     rt = rt_tree_node->data;
651
652     /* first the route entry */
653     printf("%s/%u, via %s, best-originator %s\n",
654            olsr_ip_to_string(&rt->rt_dst.prefix),
655            rt->rt_dst.prefix_len,
656            olsr_ip_to_string(&rt->rt_nexthop.gateway),
657            olsr_ip_to_string(&rt->rt_best->rtp_originator));
658
659     /* walk the per-originator path tree of routes */
660     for (rtp_tree_node = avl_walk_first(&rt->rt_path_tree);
661          rtp_tree_node;
662          rtp_tree_node = avl_walk_next(rtp_tree_node)) {
663
664       rtp = rtp_tree_node->data;
665
666       printf("\tfrom %s, etx %.3f, metric %u, via %s, %s, v %u\n",
667              olsr_ip_to_string(&rtp->rtp_originator),
668              rtp->rtp_metric.etx,
669              rtp->rtp_metric.hops,
670              olsr_ip_to_string(&rtp->rtp_nexthop.gateway),
671              rtp->rtp_nexthop.iface->int_name,
672              rtp->rtp_version);
673     
674     }
675   }
676 }
677
678 /*
679  * Local Variables:
680  * c-basic-offset: 2
681  * End:
682  */