Update to new avl/list iteration macros
[olsrd.git] / src / routing_table.c
1
2 /*
3  * The olsr.org Optimized Link-State Routing daemon(olsrd)
4  * Copyright (c) 2004-2009, the olsr.org team - see HISTORY file
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 "tc_set.h"
46 #include "mid_set.h"
47 #include "neighbor_table.h"
48 #include "olsr.h"
49 #include "link_set.h"
50 #include "common/avl.h"
51 #include "olsr_spf.h"
52 #include "net_olsr.h"
53 #include "olsr_logging.h"
54
55 #include <limits.h>
56 #include <assert.h>
57
58 /* Cookies */
59 struct olsr_cookie_info *rt_mem_cookie = NULL;
60 struct olsr_cookie_info *rtp_mem_cookie = NULL; /* Maybe static */
61
62 /*
63  * Sven-Ola: if the current internet gateway is switched, the
64  * NAT connection info is lost for any active TCP/UDP session.
65  * For this reason, we do not want to switch if the advantage
66  * is only minimal (cost of loosing all NATs is too high).
67  * The following rt_path keeps track of the current inet gw.
68  */
69 static struct rt_path *current_inetgw = NULL;
70
71 /* Root of our RIB */
72 struct avl_tree routingtree;
73
74 /*
75  * Keep a version number for detecting outdated elements
76  * in the per rt_entry rt_path subtree.
77  */
78 unsigned int routingtree_version;
79
80 /**
81  * Initialize the routingtree and kernel change queues.
82  */
83 void
84 olsr_init_routing_table(void)
85 {
86   OLSR_INFO(LOG_ROUTING, "RIB: initialize routing tree...\n");
87
88   /* the routing tree */
89   avl_init(&routingtree, avl_comp_prefix_default, false, NULL);
90   routingtree_version = 0;
91
92   /*
93    * Get some cookies for memory stats and memory recycling.
94    */
95   rt_mem_cookie = olsr_create_memcookie("rt_entry", sizeof(struct rt_entry));
96   rtp_mem_cookie = olsr_create_memcookie("rt_path", sizeof(struct rt_path));
97 }
98
99 /**
100  * Look up a max prefix entry (= /32 or /128) in the routing table.
101  *
102  * @param dst the address of the entry
103  *
104  * @return a pointer to a rt_entry struct
105  * representing the route entry.
106  */
107 struct rt_entry *
108 olsr_lookup_routing_table(const union olsr_ip_addr *dst)
109 {
110   struct rt_entry *rt;
111   struct olsr_ip_prefix prefix;
112
113   prefix.prefix = *dst;
114   prefix.prefix_len = 8 * olsr_cnf->ipsize;
115
116   rt = avl_find_element(&routingtree, &prefix, rt, rt_tree_node);
117   return rt;
118 }
119
120 /**
121  * Update gateway/interface/etx/hopcount and the version for a route path.
122  */
123 void
124 olsr_update_rt_path(struct rt_path *rtp, struct tc_entry *tc, struct link_entry *link)
125 {
126
127   rtp->rtp_version = routingtree_version;
128
129   /* gateway */
130   rtp->rtp_nexthop.gateway = link->neighbor_iface_addr;
131
132   /* interface */
133   if (rtp->rtp_nexthop.interface != link->inter) {
134     if (rtp->rtp_nexthop.interface) {
135       unlock_interface(rtp->rtp_nexthop.interface);
136     }
137     rtp->rtp_nexthop.interface = link->inter;
138     lock_interface(rtp->rtp_nexthop.interface);
139   }
140
141   /* metric/etx */
142   rtp->rtp_metric.hops = tc->hops;
143   rtp->rtp_metric.cost = tc->path_cost;
144 }
145
146 /**
147  * Alloc and key a new rt_entry.
148  */
149 static struct rt_entry *
150 olsr_alloc_rt_entry(struct olsr_ip_prefix *prefix)
151 {
152   struct rt_entry *rt = olsr_cookie_malloc(rt_mem_cookie);
153   if (!rt) {
154     return NULL;
155   }
156
157   /* Mark this entry as fresh - see olsr_update_rib_routes() */
158   rt->rt_nexthop.interface = NULL;
159
160   /* set key and backpointer prior to tree insertion */
161   rt->rt_dst = *prefix;
162
163   rt->rt_tree_node.key = &rt->rt_dst;
164   avl_insert(&routingtree, &rt->rt_tree_node);
165
166   /* init the originator subtree */
167   avl_init(&rt->rt_path_tree, avl_comp_addr_origin_default, false, NULL);
168
169   return rt;
170 }
171
172 /**
173  * Alloc and key a new rt_path.
174  */
175 static struct rt_path *
176 olsr_alloc_rt_path(struct tc_entry *tc, struct olsr_ip_prefix *prefix, uint8_t origin)
177 {
178   struct rt_path *rtp = olsr_cookie_malloc(rtp_mem_cookie);
179
180   if (!rtp) {
181     return NULL;
182   }
183
184   memset(rtp, 0, sizeof(*rtp));
185
186   rtp->rtp_dst = *prefix;
187   rtp->rtp_dst.prefix_origin = origin;
188
189   /* set key and backpointer prior to tree insertion */
190   rtp->rtp_prefix_tree_node.key = &rtp->rtp_dst;
191
192   /* insert to the tc prefix tree */
193   avl_insert(&tc->prefix_tree, &rtp->rtp_prefix_tree_node);
194
195   /* backlink to the owning tc entry */
196   rtp->rtp_tc = tc;
197
198   /*
199    * Initialize the key for the per-originator subtree.
200    * Note that the path will not yet be inserted into the routing tree.
201    * This will happen later using olsr_insert_rt_path()
202    * when the node becomes reachable post SPF calculation.
203    * In the originator subtree the prefix length will be set to
204    * max. we do not really need this in avl_comp_addr_origin, but since
205    * the datatype is olsr_ip_prefix lets keep the environment a tidy place.
206    */
207   rtp->rtp_originator.prefix = tc->addr;
208   rtp->rtp_originator.prefix_len = 8 * olsr_cnf->ipsize;
209   rtp->rtp_originator.prefix_origin = origin;
210   rtp->rtp_tree_node.key = &rtp->rtp_originator;
211
212   return rtp;
213 }
214
215 /**
216  * Create a route entry for a given rt_path and
217  * insert it into the global RIB tree.
218  */
219 void
220 olsr_insert_rt_path(struct rt_path *rtp, struct tc_entry *tc, struct link_entry *link)
221 {
222   struct rt_entry *rt;
223
224   /*
225    * no unreachable routes please.
226    */
227   if (tc->path_cost == ROUTE_COST_BROKEN) {
228     return;
229   }
230
231   /*
232    * No bogus prefix lengths.
233    */
234   if (rtp->rtp_dst.prefix_len > 8 * olsr_cnf->ipsize) {
235     return;
236   }
237
238   /*
239    * first check if there is a route_entry for the prefix.
240    */
241   rt = avl_find_element(&routingtree, &rtp->rtp_dst, rt, rt_tree_node);
242
243   if (!rt) {
244     /* no route entry yet */
245     rt = olsr_alloc_rt_entry(&rtp->rtp_dst);
246     if (!rt) {
247       return;
248     }
249   }
250
251   /*
252    * Insert to the route entry originator tree
253    * The key has been initialized in olsr_alloc_rt_path().
254    */
255   avl_insert(&rt->rt_path_tree, &rtp->rtp_tree_node);
256
257   /* backlink to the owning route entry */
258   rtp->rtp_rt = rt;
259
260   /* update the version field and relevant parameters */
261   olsr_update_rt_path(rtp, tc, link);
262 }
263
264 /**
265  * Unlink and free a rt_path.
266  */
267 void
268 olsr_delete_rt_path(struct rt_path *rtp)
269 {
270
271   /* remove from the originator tree */
272   if (rtp->rtp_rt) {
273     avl_delete(&rtp->rtp_rt->rt_path_tree, &rtp->rtp_tree_node);
274     /* clean up rt_best */
275     if (rtp->rtp_rt->rt_best == rtp) {
276       if (rtp->rtp_rt->rt_path_tree.count) {
277         olsr_rt_best(rtp->rtp_rt);
278       }
279       else {
280         rtp->rtp_rt->rt_best = NULL;
281       }
282     }
283     rtp->rtp_rt = NULL;
284   }
285
286   /* remove from the tc prefix tree */
287   if (rtp->rtp_tc) {
288     avl_delete(&rtp->rtp_tc->prefix_tree, &rtp->rtp_prefix_tree_node);
289     rtp->rtp_tc = NULL;
290   }
291
292   /* unlock underlying interface */
293   if (rtp->rtp_nexthop.interface) {
294     unlock_interface(rtp->rtp_nexthop.interface);
295   }
296
297   /* no current inet gw if the rt_path is removed */
298   if (current_inetgw == rtp) {
299     current_inetgw = NULL;
300   }
301
302   olsr_cookie_free(rtp_mem_cookie, rtp);
303 }
304
305 /**
306  * compare two route paths.
307  *
308  * returns TRUE if the first path is better
309  * than the second one, FALSE otherwise.
310  */
311 static bool
312 olsr_cmp_rtp(const struct rt_path *rtp1, const struct rt_path *rtp2, const struct rt_path *inetgw)
313 {
314   olsr_linkcost etx1, etx2;
315
316   if (rtp1 == NULL) {
317     return false;
318   }
319   if (rtp2 == NULL) {
320     return true;
321   }
322
323   etx1 = rtp1->rtp_metric.cost;
324   etx2 = rtp2->rtp_metric.cost;
325   if (inetgw == rtp1) {
326     if (etx1 < INT32_MAX/1000) {
327       etx1 = (etx1 * olsr_cnf->lq_nat_thresh) / 1000;
328     }
329     else {
330       etx1 = (etx1 / 1000) * olsr_cnf->lq_nat_thresh;
331     }
332   }
333   if (inetgw == rtp2) {
334     if (etx2 < INT32_MAX/1000) {
335       etx2 = (etx2 * olsr_cnf->lq_nat_thresh) / 1000;
336     }
337     else {
338       etx2 = (etx2 / 1000) * olsr_cnf->lq_nat_thresh;
339     }
340   }
341
342   /* etx comes first */
343   if (etx1 < etx2) {
344     return true;
345   }
346   if (etx1 > etx2) {
347     return false;
348   }
349
350   /* hopcount is next tie breaker */
351   if (rtp1->rtp_metric.hops < rtp2->rtp_metric.hops) {
352     return true;
353   }
354   if (rtp1->rtp_metric.hops > rtp2->rtp_metric.hops) {
355     return false;
356   }
357
358   /* originator type code is next tie breaker */
359   if (rtp1->rtp_originator.prefix_origin < rtp2->rtp_originator.prefix_origin) {
360     return true;
361   }
362   if (rtp1->rtp_originator.prefix_origin > rtp2->rtp_originator.prefix_origin) {
363     return false;
364   }
365
366   /* originator address is final breaker */
367   return (olsr_ipcmp(&rtp1->rtp_originator.prefix, &rtp2->rtp_originator.prefix));
368 }
369
370 /**
371  * compare the best path of two route entries.
372  *
373  * returns TRUE if the first entry is better
374  * than the second one, FALSE otherwise.
375  */
376 bool
377 olsr_cmp_rt(const struct rt_entry * rt1, const struct rt_entry * rt2)
378 {
379   return olsr_cmp_rtp(rt1->rt_best, rt2->rt_best, NULL);
380 }
381
382 /**
383  * run best route selection among a
384  * set of identical prefixes.
385  */
386 void
387 olsr_rt_best(struct rt_entry *rt)
388 {
389   /* grab the first entry */
390   struct rt_path *rtp, *iterator;
391
392   assert (!avl_is_empty(&rt->rt_path_tree));
393
394   OLSR_FOR_ALL_RT_PATH_ENTRIES(rt, rtp, iterator) {
395     if (olsr_cmp_rtp(rtp, rt->rt_best, current_inetgw)) {
396       rt->rt_best = rtp;
397     }
398   }
399
400   if (0 == rt->rt_dst.prefix_len) {
401     current_inetgw = rt->rt_best;
402   }
403 }
404
405 /**
406  * Insert a prefix into the prefix tree hanging off a lsdb (tc) entry.
407  *
408  * Check if the candidate route (we call this a rt_path) is known,
409  * if not create it.
410  * Upon post-SPF processing (if the node is reachable) the prefix
411  * will be finally inserted into the global RIB.
412  *
413  *@param dst the destination
414  *@param plen the prefix length
415  *@param originator the originating router
416  *
417  *@return the new rt_path struct
418  */
419 struct rt_path *
420 olsr_insert_routing_table(const union olsr_ip_addr *dst, int plen, const union olsr_ip_addr *originator, int origin)
421 {
422 #if !defined REMOVE_LOG_DEBUG
423   struct ipaddr_str dstbuf, origbuf;
424 #endif
425   struct tc_entry *tc;
426   struct rt_path *rtp;
427   struct olsr_ip_prefix prefix;
428
429   /*
430    * No bogus prefix lengths.
431    */
432   if (plen > 8 * (int)olsr_cnf->ipsize) {
433     return NULL;
434   }
435
436   /*
437    * For all routes we use the tc_entry as an hookup point.
438    * If the tc_entry is disconnected, i.e. has no edges it will not
439    * be explored during SPF run.
440    */
441   tc = olsr_locate_tc_entry(originator);
442
443   /*
444    * first check if there is a rt_path for the prefix.
445    */
446   prefix.prefix = *dst;
447   prefix.prefix_len = plen;
448   prefix.prefix_origin = origin;
449
450   rtp = avl_find_element(&tc->prefix_tree, &prefix, rtp, rtp_prefix_tree_node);
451
452   if (!rtp) {
453
454     /* no rt_path for this prefix yet */
455     rtp = olsr_alloc_rt_path(tc, &prefix, origin);
456
457     if (!rtp) {
458       return NULL;
459     }
460
461     OLSR_DEBUG(LOG_ROUTING, "RIB: add prefix %s/%d from %s\n",
462                olsr_ip_to_string(&dstbuf, dst), plen, olsr_ip_to_string(&origbuf, originator));
463
464     /* overload the hna change bit for flagging a prefix change */
465     changes_hna = true;
466   }
467
468   return rtp;
469 }
470
471 /**
472  * Delete a prefix from the prefix tree hanging off a lsdb (tc) entry.
473  */
474 void
475 olsr_delete_routing_table(union olsr_ip_addr *dst, int plen, union olsr_ip_addr *originator, int origin)
476 {
477 #if !defined REMOVE_LOG_DEBUG
478   struct ipaddr_str dstbuf, origbuf;
479 #endif
480
481   struct tc_entry *tc;
482   struct rt_path *rtp;
483   struct olsr_ip_prefix prefix;
484
485   /*
486    * No bogus prefix lengths.
487    */
488   if (plen > 8 * (int)olsr_cnf->ipsize) {
489     return;
490   }
491
492   tc = olsr_lookup_tc_entry(originator);
493   if (!tc) {
494     return;
495   }
496
497   /*
498    * Grab the rt_path for the prefix.
499    */
500   prefix.prefix = *dst;
501   prefix.prefix_len = plen;
502   prefix.prefix_origin = origin;
503
504   rtp = avl_find_element(&tc->prefix_tree, &prefix, rtp, rtp_prefix_tree_node);
505   if (rtp) {
506     olsr_delete_rt_path(rtp);
507
508     OLSR_DEBUG(LOG_ROUTING, "RIB: del prefix %s/%d from %s\n",
509                olsr_ip_to_string(&dstbuf, dst), plen, olsr_ip_to_string(&origbuf, originator));
510
511     /* overload the hna change bit for flagging a prefix change */
512     changes_hna = true;
513   }
514 }
515
516 /**
517  * format a route entry into a buffer
518  */
519 char *
520 olsr_rt_to_string(const struct rt_entry *rt)
521 {
522   static char buff[128];
523   struct ipaddr_str gwstr;
524   struct ipprefix_str prefixstr;
525
526   snprintf(buff, sizeof(buff),
527            "%s via %s dev %s",
528            olsr_ip_prefix_to_string(&prefixstr, &rt->rt_dst),
529            olsr_ip_to_string(&gwstr, &rt->rt_nexthop.gateway),
530            rt->rt_nexthop.interface ? rt->rt_nexthop.interface->int_name : "(null)");
531
532   return buff;
533 }
534
535 /**
536  * format a route path into a buffer
537  */
538 char *
539 olsr_rtp_to_string(const struct rt_path *rtp)
540 {
541   static char buff[128];
542   struct ipaddr_str origstr, gwstr;
543   char lqbuffer[LQTEXT_MAXLENGTH];
544   struct ipprefix_str prefixstr;
545
546   snprintf(buff, sizeof(buff),
547            "%s from %s via %s dev %s, "
548            "cost %s, metric %u, v %u",
549            olsr_ip_prefix_to_string(&prefixstr, &rtp->rtp_rt->rt_dst),
550            olsr_ip_to_string(&origstr, &rtp->rtp_originator.prefix),
551            olsr_ip_to_string(&gwstr, &rtp->rtp_nexthop.gateway),
552            rtp->rtp_nexthop.interface ? rtp->rtp_nexthop.interface->int_name : "(null)",
553            olsr_get_linkcost_text(rtp->rtp_metric.cost, true, lqbuffer, sizeof(lqbuffer)),
554            rtp->rtp_metric.hops, rtp->rtp_version);
555
556   return buff;
557 }
558
559 /**
560  * Print the routingtree to STDOUT
561  *
562  */
563 void
564 olsr_print_routing_table(void)
565 {
566   /* The whole function makes no sense without it. */
567 #if !defined REMOVE_LOG_INFO
568   struct rt_entry *rt, *rt_iterator;
569   struct rt_path *rtp, *rtp_iterator;
570
571   char lqbuffer[LQTEXT_MAXLENGTH];
572
573   OLSR_INFO(LOG_ROUTING, "ROUTING TABLE\n");
574
575   OLSR_FOR_ALL_RT_ENTRIES(rt, rt_iterator) {
576     struct ipaddr_str origstr, gwstr;
577     struct ipprefix_str prefixstr;
578
579     /* first the route entry */
580     OLSR_INFO_NH(LOG_ROUTING, "%s, via %s dev %s, best-originator %s\n",
581                  olsr_ip_prefix_to_string(&prefixstr, &rt->rt_dst),
582                  olsr_ip_to_string(&origstr, &rt->rt_nexthop.gateway),
583                  rt->rt_nexthop.interface ? rt->rt_nexthop.interface->int_name : "(null)",
584                  olsr_ip_to_string(&gwstr, &rt->rt_best->rtp_originator.prefix));
585
586     /* walk the per-originator path tree of routes */
587     OLSR_FOR_ALL_RT_PATH_ENTRIES(rt, rtp, rtp_iterator) {
588       OLSR_INFO_NH(LOG_ROUTING, "\tfrom %s, cost %s, metric %u, via %s, dev %s, v %u\n",
589                    olsr_ip_to_string(&origstr, &rtp->rtp_originator.prefix),
590                    olsr_get_linkcost_text(rtp->rtp_metric.cost, true, lqbuffer, sizeof(lqbuffer)),
591                    rtp->rtp_metric.hops,
592                    olsr_ip_to_string(&gwstr, &rtp->rtp_nexthop.gateway),
593                    rt->rt_nexthop.interface ? rt->rt_nexthop.interface->int_name : "(null)", rtp->rtp_version);
594     }
595   }
596 #endif
597 }
598
599 /*
600  * Local Variables:
601  * c-basic-offset: 2
602  * indent-tabs-mode: nil
603  * End:
604  */