gateway: introduce and use removeGatewayFromList function
[olsrd.git] / src / routing_table.c
1
2 /*
3  * The olsr.org Optimized Link-State Routing daemon(olsrd)
4  * Copyright (c) 2004, Andreas Tonnesen(andreto@olsr.org)
5  * RIB implementation (c) 2007, Hannes Gredler (hannes@gredler.at)
6  * All rights reserved.
7  *
8  * Redistribution and use in source and binary forms, with or without
9  * modification, are permitted provided that the following conditions
10  * are met:
11  *
12  * * Redistributions of source code must retain the above copyright
13  *   notice, this list of conditions and the following disclaimer.
14  * * Redistributions in binary form must reproduce the above copyright
15  *   notice, this list of conditions and the following disclaimer in
16  *   the documentation and/or other materials provided with the
17  *   distribution.
18  * * Neither the name of olsr.org, olsrd nor the names of its
19  *   contributors may be used to endorse or promote products derived
20  *   from this software without specific prior written permission.
21  *
22  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
23  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
24  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
25  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
26  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
27  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
28  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
29  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
30  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
31  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
32  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
33  * POSSIBILITY OF SUCH DAMAGE.
34  *
35  * Visit http://www.olsr.org for more information.
36  *
37  * If you find this software useful feel free to make a donation
38  * to the project. For more information see the website or contact
39  * the copyright holders.
40  *
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 "common/avl.h"
53 #include "olsr_spf.h"
54 #include "net_olsr.h"
55
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;
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  * Bump the version number of the routing tree.
82  *
83  * After route-insertion compare the version number of the routes
84  * against the version number of the table.
85  * This is a lightweight detection if a node or prefix went away,
86  * rather than brute force old vs. new rt_entry comparision.
87  */
88 unsigned int
89 olsr_bump_routingtree_version(void)
90 {
91   return routingtree_version++;
92 }
93
94 /**
95  * avl_comp_ipv4_prefix
96  *
97  * compare two ipv4 prefixes.
98  * first compare the prefixes, then
99  *  then compare the prefix lengths.
100  *
101  * return 0 if there is an exact match and
102  * -1 / +1 depending on being smaller or bigger.
103  */
104 int
105 avl_comp_ipv4_prefix(const void *prefix1, const void *prefix2)
106 {
107   const struct olsr_ip_prefix *pfx1 = prefix1;
108   const struct olsr_ip_prefix *pfx2 = prefix2;
109   const uint32_t addr1 = ntohl(pfx1->prefix.v4.s_addr);
110   const uint32_t addr2 = ntohl(pfx2->prefix.v4.s_addr);
111
112   /* prefix */
113   if (addr1 < addr2) {
114     return -1;
115   }
116   if (addr1 > addr2) {
117     return +1;
118   }
119
120   /* prefix length */
121   if (pfx1->prefix_len < pfx2->prefix_len) {
122     return -1;
123   }
124   if (pfx1->prefix_len > pfx2->prefix_len) {
125     return +1;
126   }
127
128   return 0;
129 }
130
131 /**
132  * avl_comp_ipv6_prefix
133  *
134  * compare two ipv6 prefixes.
135  * first compare the prefixes, then
136  *  then compare the prefix lengths.
137  *
138  * return 0 if there is an exact match and
139  * -1 / +1 depending on being smaller or bigger.
140  */
141 int
142 avl_comp_ipv6_prefix(const void *prefix1, const void *prefix2)
143 {
144   int res;
145   const struct olsr_ip_prefix *pfx1 = prefix1;
146   const struct olsr_ip_prefix *pfx2 = prefix2;
147
148   /* prefix */
149   res = memcmp(&pfx1->prefix.v6, &pfx2->prefix.v6, 16);
150   if (res != 0) {
151     return res;
152   }
153   /* prefix length */
154   if (pfx1->prefix_len < pfx2->prefix_len) {
155     return -1;
156   }
157   if (pfx1->prefix_len > pfx2->prefix_len) {
158     return +1;
159   }
160
161   return 0;
162 }
163
164 /**
165  * Initialize the routingtree and kernel change queues.
166  */
167 void
168 olsr_init_routing_table(void)
169 {
170   OLSR_PRINTF(5, "RIB: init routing tree\n");
171
172   /* the routing tree */
173   avl_init(&routingtree, avl_comp_prefix_default);
174   routingtree_version = 0;
175
176   /*
177    * Get some cookies for memory stats and memory recycling.
178    */
179   rt_mem_cookie = olsr_alloc_cookie("rt_entry", OLSR_COOKIE_TYPE_MEMORY);
180   olsr_cookie_set_memory_size(rt_mem_cookie, sizeof(struct rt_entry));
181
182   rtp_mem_cookie = olsr_alloc_cookie("rt_path", OLSR_COOKIE_TYPE_MEMORY);
183   olsr_cookie_set_memory_size(rtp_mem_cookie, sizeof(struct rt_path));
184 }
185
186 /**
187  * Look up a maxplen entry (= /32 or /128) in the routing table.
188  *
189  * @param dst the address of the entry
190  *
191  * @return a pointer to a rt_entry struct
192  * representing the route entry.
193  */
194 struct rt_entry *
195 olsr_lookup_routing_table(const union olsr_ip_addr *dst)
196 {
197   struct avl_node *rt_tree_node;
198   struct olsr_ip_prefix prefix;
199
200   prefix.prefix = *dst;
201   prefix.prefix_len = olsr_cnf->maxplen;
202
203   rt_tree_node = avl_find(&routingtree, &prefix);
204
205   return rt_tree_node ? rt_tree2rt(rt_tree_node) : NULL;
206 }
207
208 /**
209  * Update gateway/interface/etx/hopcount and the version for a route path.
210  */
211 void
212 olsr_update_rt_path(struct rt_path *rtp, struct tc_entry *tc, struct link_entry *link)
213 {
214
215   rtp->rtp_version = routingtree_version;
216
217   /* gateway */
218   rtp->rtp_nexthop.gateway = link->neighbor_iface_addr;
219
220   /* interface */
221   rtp->rtp_nexthop.iif_index = link->inter->if_index;
222
223   /* metric/etx */
224   rtp->rtp_metric.hops = tc->hops;
225   rtp->rtp_metric.cost = tc->path_cost;
226 }
227
228 /**
229  * Alloc and key a new rt_entry.
230  */
231 static struct rt_entry *
232 olsr_alloc_rt_entry(struct olsr_ip_prefix *prefix)
233 {
234   struct rt_entry *rt = olsr_cookie_malloc(rt_mem_cookie);
235   if (!rt) {
236     return NULL;
237   }
238
239   memset(rt, 0, sizeof(*rt));
240
241   /* Mark this entry as fresh (see process_routes.c:512) */
242   rt->rt_nexthop.iif_index = -1;
243
244   /* set key and backpointer prior to tree insertion */
245   rt->rt_dst = *prefix;
246
247   rt->rt_tree_node.key = &rt->rt_dst;
248   avl_insert(&routingtree, &rt->rt_tree_node, AVL_DUP_NO);
249
250   /* init the originator subtree */
251   avl_init(&rt->rt_path_tree, avl_comp_default);
252
253   return rt;
254 }
255
256 /**
257  * Alloc and key a new rt_path.
258  */
259 static struct rt_path *
260 olsr_alloc_rt_path(struct tc_entry *tc, struct olsr_ip_prefix *prefix, uint8_t origin)
261 {
262   struct rt_path *rtp = olsr_cookie_malloc(rtp_mem_cookie);
263
264   if (!rtp) {
265     return NULL;
266   }
267
268   memset(rtp, 0, sizeof(*rtp));
269
270   rtp->rtp_dst = *prefix;
271
272   /* set key and backpointer prior to tree insertion */
273   rtp->rtp_prefix_tree_node.key = &rtp->rtp_dst;
274
275   /* insert to the tc prefix tree */
276   avl_insert(&tc->prefix_tree, &rtp->rtp_prefix_tree_node, AVL_DUP_NO);
277   olsr_lock_tc_entry(tc);
278
279   /* backlink to the owning tc entry */
280   rtp->rtp_tc = tc;
281
282   /* store the origin of the route */
283   rtp->rtp_origin = origin;
284
285   return rtp;
286 }
287
288 /**
289  * Create a route entry for a given rt_path and
290  * insert it into the global RIB tree.
291  */
292 void
293 olsr_insert_rt_path(struct rt_path *rtp, struct tc_entry *tc, struct link_entry *link)
294 {
295   struct rt_entry *rt;
296   struct avl_node *node;
297
298   /*
299    * no unreachable routes please.
300    */
301   if (tc->path_cost == ROUTE_COST_BROKEN) {
302     return;
303   }
304
305   /*
306    * No bogus prefix lengths.
307    */
308   if (rtp->rtp_dst.prefix_len > olsr_cnf->maxplen) {
309     return;
310   }
311
312   /*
313    * first check if there is a route_entry for the prefix.
314    */
315   node = avl_find(&routingtree, &rtp->rtp_dst);
316
317   if (!node) {
318
319     /* no route entry yet */
320     rt = olsr_alloc_rt_entry(&rtp->rtp_dst);
321
322     if (!rt) {
323       return;
324     }
325
326   } else {
327     rt = rt_tree2rt(node);
328   }
329
330   /* Now insert the rt_path to the owning rt_entry tree */
331   rtp->rtp_originator = tc->addr;
332
333   /* set key and backpointer prior to tree insertion */
334   rtp->rtp_tree_node.key = &rtp->rtp_originator;
335
336   /* insert to the route entry originator tree */
337   avl_insert(&rt->rt_path_tree, &rtp->rtp_tree_node, AVL_DUP_NO);
338
339   /* backlink to the owning route entry */
340   rtp->rtp_rt = rt;
341
342   /* update the version field and relevant parameters */
343   olsr_update_rt_path(rtp, tc, link);
344 }
345
346 /**
347  * Unlink and free a rt_path.
348  */
349 void
350 olsr_delete_rt_path(struct rt_path *rtp)
351 {
352
353   /* remove from the originator tree */
354   if (rtp->rtp_rt) {
355     avl_delete(&rtp->rtp_rt->rt_path_tree, &rtp->rtp_tree_node);
356     rtp->rtp_rt = NULL;
357   }
358
359   /* remove from the tc prefix tree */
360   if (rtp->rtp_tc) {
361     avl_delete(&rtp->rtp_tc->prefix_tree, &rtp->rtp_prefix_tree_node);
362     olsr_unlock_tc_entry(rtp->rtp_tc);
363     rtp->rtp_tc = NULL;
364   }
365
366   /* no current inet gw if the rt_path is removed */
367   if (current_inetgw == rtp) {
368     current_inetgw = NULL;
369   }
370
371   olsr_cookie_free(rtp_mem_cookie, rtp);
372 }
373
374 /**
375  * Check if there is an interface or gateway change.
376  */
377 bool
378 olsr_nh_change(const struct rt_nexthop *nh1, const struct rt_nexthop *nh2)
379 {
380   if (!ipequal(&nh1->gateway, &nh2->gateway) || (nh1->iif_index != nh2->iif_index)) {
381     return true;
382   }
383   return false;
384 }
385
386 /**
387  * Check if there is a hopcount change.
388  */
389 bool
390 olsr_hopcount_change(const struct rt_metric * met1, const struct rt_metric * met2)
391 {
392   return (met1->hops != met2->hops);
393 }
394
395 /**
396  * Depending if flat_metric is configured and the kernel fib operation
397  * return the hopcount metric of a route.
398  * For adds this is the metric of best rour after olsr_rt_best() election,
399  * for deletes this is the metric of the route that got stored in the rt_entry,
400  * during route installation.
401  */
402 uint8_t
403 olsr_fib_metric(const struct rt_metric * met)
404 {
405   if (FIBM_CORRECT == olsr_cnf->fib_metric) {
406     return met->hops;
407   }
408   return RT_METRIC_DEFAULT;
409 }
410
411 /**
412  * depending on the operation (add/chg/del) the nexthop
413  * field from the route entry or best route path shall be used.
414  */
415 const struct rt_nexthop *
416 olsr_get_nh(const struct rt_entry *rt)
417 {
418
419   if (rt->rt_best) {
420
421     /* this is a route add/chg - grab nexthop from the best route. */
422     return &rt->rt_best->rtp_nexthop;
423   }
424
425   /* this is a route deletion - all routes are gone. */
426   return &rt->rt_nexthop;
427 }
428
429 /**
430  * compare two route paths.
431  *
432  * returns TRUE if the first path is better
433  * than the second one, FALSE otherwise.
434  */
435 static bool
436 olsr_cmp_rtp(const struct rt_path *rtp1, const struct rt_path *rtp2, const struct rt_path *inetgw)
437 {
438   olsr_linkcost etx1 = rtp1->rtp_metric.cost;
439   olsr_linkcost etx2 = rtp2->rtp_metric.cost;
440   if (inetgw == rtp1)
441     etx1 *= olsr_cnf->lq_nat_thresh;
442   if (inetgw == rtp2)
443     etx2 *= olsr_cnf->lq_nat_thresh;
444
445   /* etx comes first */
446   if (etx1 < etx2) {
447     return true;
448   }
449   if (etx1 > etx2) {
450     return false;
451   }
452
453   /* hopcount is next tie breaker */
454   if (rtp1->rtp_metric.hops < rtp2->rtp_metric.hops) {
455     return true;
456   }
457   if (rtp1->rtp_metric.hops > rtp2->rtp_metric.hops) {
458     return false;
459   }
460
461   /* originator (which is guaranteed to be unique) is final tie breaker */
462   if (memcmp(&rtp1->rtp_originator, &rtp2->rtp_originator, olsr_cnf->ipsize) < 0) {
463     return true;
464   }
465
466   return false;
467 }
468
469 /**
470  * compare the best path of two route entries.
471  *
472  * returns TRUE if the first entry is better
473  * than the second one, FALSE otherwise.
474  */
475 bool
476 olsr_cmp_rt(const struct rt_entry * rt1, const struct rt_entry * rt2)
477 {
478   return olsr_cmp_rtp(rt1->rt_best, rt2->rt_best, NULL);
479 }
480
481 /**
482  * run best route selection among a
483  * set of identical prefixes.
484  */
485 void
486 olsr_rt_best(struct rt_entry *rt)
487 {
488   /* grab the first entry */
489   struct avl_node *node = avl_walk_first(&rt->rt_path_tree);
490
491   assert(node != 0);            /* should not happen */
492
493   rt->rt_best = rtp_tree2rtp(node);
494
495   /* walk all remaining originator entries */
496   while ((node = avl_walk_next(node))) {
497     struct rt_path *rtp = rtp_tree2rtp(node);
498
499     if (olsr_cmp_rtp(rtp, rt->rt_best, current_inetgw)) {
500       rt->rt_best = rtp;
501     }
502   }
503
504   if (0 == rt->rt_dst.prefix_len) {
505     current_inetgw = rt->rt_best;
506   }
507 }
508
509 /**
510  * Insert a prefix into the prefix tree hanging off a lsdb (tc) entry.
511  *
512  * Check if the candidate route (we call this a rt_path) is known,
513  * if not create it.
514  * Upon post-SPF processing (if the node is reachable) the prefix
515  * will be finally inserted into the global RIB.
516  *
517  *@param dst the destination
518  *@param plen the prefix length
519  *@param originator the originating router
520  *@param origin the origin of the route
521  *
522  *@return the new rt_path struct
523  */
524 struct rt_path *
525 olsr_insert_routing_table(union olsr_ip_addr *dst, int plen, union olsr_ip_addr *originator, int origin)
526 {
527 #ifdef DEBUG
528   struct ipaddr_str dstbuf, origbuf;
529 #endif /* DEBUG */
530   struct tc_entry *tc;
531   struct rt_path *rtp;
532   struct avl_node *node;
533   struct olsr_ip_prefix prefix;
534
535   /*
536    * No bogus prefix lengths.
537    */
538   if (plen > olsr_cnf->maxplen) {
539     return NULL;
540   }
541
542   /*
543    * For all routes we use the tc_entry as an hookup point.
544    * If the tc_entry is disconnected, i.e. has no edges it will not
545    * be explored during SPF run.
546    */
547   tc = olsr_locate_tc_entry(originator);
548
549   /*
550    * first check if there is a rt_path for the prefix.
551    */
552   prefix.prefix = *dst;
553   prefix.prefix_len = plen;
554
555   node = avl_find(&tc->prefix_tree, &prefix);
556
557   if (!node) {
558
559     /* no rt_path for this prefix yet */
560     rtp = olsr_alloc_rt_path(tc, &prefix, origin);
561
562     if (!rtp) {
563       return NULL;
564     }
565 #ifdef DEBUG
566     OLSR_PRINTF(1, "RIB: add prefix %s/%u from %s\n", olsr_ip_to_string(&dstbuf, dst), plen,
567                 olsr_ip_to_string(&origbuf, originator));
568 #endif /* DEBUG */
569
570     /* overload the hna change bit for flagging a prefix change */
571     changes_hna = true;
572
573   } else {
574     rtp = rtp_prefix_tree2rtp(node);
575   }
576
577   return rtp;
578 }
579
580 /**
581  * Delete a prefix from the prefix tree hanging off a lsdb (tc) entry.
582  */
583 void
584 olsr_delete_routing_table(union olsr_ip_addr *dst, int plen, union olsr_ip_addr *originator)
585 {
586 #ifdef DEBUG
587   struct ipaddr_str dstbuf, origbuf;
588 #endif /* DEBUG */
589
590   struct tc_entry *tc;
591   struct rt_path *rtp;
592   struct avl_node *node;
593   struct olsr_ip_prefix prefix;
594
595   /*
596    * No bogus prefix lengths.
597    */
598   if (plen > olsr_cnf->maxplen) {
599     return;
600   }
601
602   tc = olsr_lookup_tc_entry(originator);
603   if (!tc) {
604     return;
605   }
606
607   /*
608    * Grab the rt_path for the prefix.
609    */
610   prefix.prefix = *dst;
611   prefix.prefix_len = plen;
612
613   node = avl_find(&tc->prefix_tree, &prefix);
614
615   if (node) {
616     rtp = rtp_prefix_tree2rtp(node);
617     olsr_delete_rt_path(rtp);
618
619 #ifdef DEBUG
620     OLSR_PRINTF(1, "RIB: del prefix %s/%u from %s\n", olsr_ip_to_string(&dstbuf, dst), plen,
621                 olsr_ip_to_string(&origbuf, originator));
622 #endif /* DEBUG */
623
624     /* overload the hna change bit for flagging a prefix change */
625     changes_hna = true;
626   }
627 }
628
629 /**
630  * format a route entry into a buffer
631  */
632 char *
633 olsr_rt_to_string(const struct rt_entry *rt)
634 {
635   static char buff[128];
636   struct ipaddr_str prefixstr, gwstr;
637
638   snprintf(buff, sizeof(buff), "%s/%u via %s", olsr_ip_to_string(&prefixstr, &rt->rt_dst.prefix), rt->rt_dst.prefix_len,
639            olsr_ip_to_string(&gwstr, &rt->rt_nexthop.gateway));
640
641   return buff;
642 }
643
644 /**
645  * format a route path into a buffer
646  */
647 char *
648 olsr_rtp_to_string(const struct rt_path *rtp)
649 {
650   static char buff[128];
651   struct ipaddr_str prefixstr, origstr, gwstr;
652   struct rt_entry *rt = rtp->rtp_rt;
653   struct lqtextbuffer lqbuffer;
654
655   snprintf(buff, sizeof(buff), "%s/%u from %s via %s, " "cost %s, metric %u, v %u",
656            olsr_ip_to_string(&prefixstr, &rt->rt_dst.prefix), rt->rt_dst.prefix_len, olsr_ip_to_string(&origstr,
657                                                                                                        &rtp->rtp_originator),
658            olsr_ip_to_string(&gwstr, &rtp->rtp_nexthop.gateway), get_linkcost_text(rtp->rtp_metric.cost, true, &lqbuffer),
659            rtp->rtp_metric.hops, rtp->rtp_version);
660
661   return buff;
662 }
663
664 /**
665  * Print the routingtree to STDOUT
666  *
667  */
668 #ifndef NODEBUG
669 void
670 olsr_print_routing_table(struct avl_tree *tree)
671 {
672   /* The whole function makes no sense without it. */
673   struct avl_node *rt_tree_node;
674   struct lqtextbuffer lqbuffer;
675
676   OLSR_PRINTF(6, "ROUTING TABLE\n");
677
678   for (rt_tree_node = avl_walk_first(tree); rt_tree_node != NULL; rt_tree_node = avl_walk_next(rt_tree_node)) {
679     struct avl_node *rtp_tree_node;
680     struct ipaddr_str prefixstr, origstr, gwstr;
681     struct rt_entry *rt = rt_tree2rt(rt_tree_node);
682
683     /* first the route entry */
684     OLSR_PRINTF(6, "%s/%u, via %s, best-originator %s\n", olsr_ip_to_string(&prefixstr, &rt->rt_dst.prefix), rt->rt_dst.prefix_len,
685                 olsr_ip_to_string(&origstr, &rt->rt_nexthop.gateway), olsr_ip_to_string(&gwstr, &rt->rt_best->rtp_originator));
686
687     /* walk the per-originator path tree of routes */
688     for (rtp_tree_node = avl_walk_first(&rt->rt_path_tree); rtp_tree_node != NULL; rtp_tree_node = avl_walk_next(rtp_tree_node)) {
689       struct rt_path *rtp = rtp_tree2rtp(rtp_tree_node);
690       OLSR_PRINTF(6, "\tfrom %s, cost %s, metric %u, via %s, %s, v %u\n", olsr_ip_to_string(&origstr, &rtp->rtp_originator),
691                   get_linkcost_text(rtp->rtp_metric.cost, true, &lqbuffer), rtp->rtp_metric.hops, olsr_ip_to_string(&gwstr,
692                                                                                                                     &rtp->
693                                                                                                                     rtp_nexthop.
694                                                                                                                     gateway),
695                   if_ifwithindex_name(rt->rt_nexthop.iif_index), rtp->rtp_version);
696     }
697   }
698   tree = NULL;                  /* squelch compiler warnings */
699 }
700 #endif /* NODEBUG */
701
702 /*
703  * Local Variables:
704  * c-basic-offset: 2
705  * indent-tabs-mode: nil
706  * End:
707  */