src/process_routes.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  * export_route_entry interface added by Immo 'FaUl Wehrenberg
   9  * <immo@chaostreff-dortmund.de> and reworked by sven-ola 2007
  10  *
  11  * Redistribution and use in source and binary forms, with or without
  12  * modification, are permitted provided that the following conditions
  13  * are met:
  14  *
  15  * * Redistributions of source code must retain the above copyright
  16  *   notice, this list of conditions and the following disclaimer.
  17  * * Redistributions in binary form must reproduce the above copyright
  18  *   notice, this list of conditions and the following disclaimer in
  19  *   the documentation and/or other materials provided with the
  20  *   distribution.
  21  * * Neither the name of olsr.org, olsrd nor the names of its
  22  *   contributors may be used to endorse or promote products derived
  23  *   from this software without specific prior written permission.
  24  *
  25  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  26  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  27  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS
  28  * FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE
  29  * COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT,
  30  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING,
  31  * BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  32  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  33  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  34  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
  35  * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
  36  * POSSIBILITY OF SUCH DAMAGE.
  37  *
  38  * Visit http://www.olsr.org for more information.
  39  *
  40  * If you find this software useful feel free to make a donation
  41  * to the project. For more information see the website or contact
  42  * the copyright holders.
  43  *
  44  */
  45
  46 #include "ipcalc.h"
  47 #include "defs.h"
  48 #include "olsr.h"
  49 #include "log.h"
  50 #include "kernel_routes.h"
  51 #include "common/avl.h"
  52 #include "net_olsr.h"
  53 #include "tc_set.h"
  54 #include "olsr_cookie.h"
  55 #include "olsr_niit.h"
  56
  57 #ifdef WIN32
  58 char *StrError(unsigned int ErrNo);
  59 #undef strerror
  60 #define strerror(x) StrError(x)
  61 #endif
  62
  63 static struct list_node chg_kernel_list;
  64
  65 /**
  66  *
  67  * Calculate the kernel route flags.
  68  * Called before enqueuing a change/delete operation
  69  *
  70  */
  71 uint8_t
  72 olsr_rt_flags(const struct rt_entry *rt)
  73 {
  74   const struct rt_nexthop *nh;
  75   uint8_t flags = RTF_UP;
  76
  77   /* destination is host */
  78   if (rt->rt_dst.prefix_len == olsr_cnf->maxplen) {
  79     flags |= RTF_HOST;
  80   }
  81
  82   nh = olsr_get_nh(rt);
  83
  84   if (!ipequal(&rt->rt_dst.prefix, &nh->gateway)) {
  85     flags |= RTF_GATEWAY;
  86   }
  87
  88   return flags;
  89 }
  90
  91 export_route_function olsr_addroute_function;
  92 export_route_function olsr_addroute6_function;
  93 export_route_function olsr_delroute_function;
  94 export_route_function olsr_delroute6_function;
  95
  96 void
  97 olsr_init_export_route(void)
  98 {
  99   /* the add/chg/del kernel queues */
 100   //list_head_init(&add_kernel_list);
 101   list_head_init(&chg_kernel_list);
 102
 103   olsr_addroute_function = olsr_ioctl_add_route;
 104   olsr_addroute6_function = olsr_ioctl_add_route6;
 105   olsr_delroute_function = olsr_ioctl_del_route;
 106   olsr_delroute6_function = olsr_ioctl_del_route6;
 107 }
 108
 109 /**
 110  * Delete all OLSR routes.
 111  *
 112  * This is extremely simple - Just increment the version of the
 113  * tree and then olsr_update_rib_routes() will see all routes in the tree
 114  * as outdated and olsr_update_kernel_routes() will finally flush it.
 115  *
 116  */
 117 void
 118 olsr_delete_all_kernel_routes(void)
 119 {
 120   OLSR_PRINTF(1, "Deleting all routes...\n");
 121
 122   olsr_bump_routingtree_version();
 123   olsr_update_rib_routes();
 124   olsr_update_kernel_routes();
 125 }
 126
 127 /**
 128  * Enqueue a route on a kernel add/chg/del queue.
 129  */
 130 static void
 131 olsr_enqueue_rt(struct list_node *head_node, struct rt_entry *rt)
 132 {
 133   const struct rt_nexthop *nh;
 134
 135   /* if this node is already on some changelist we are done */
 136   if (list_node_on_list(&rt->rt_change_node)) {
 137     return;
 138   }
 139
 140   /*
 141    * For easier route dependency tracking we enqueue nexthop routes
 142    * at the head of the queue and non-nexthop routes at the tail of the queue.
 143    */
 144   nh = olsr_get_nh(rt);
 145
 146   if (ipequal(&rt->rt_dst.prefix, &nh->gateway)) {
 147     list_add_after(head_node, &rt->rt_change_node);
 148   } else {
 149     list_add_before(head_node, &rt->rt_change_node);
 150   }
 151 }
 152
 153 /**
 154  * Process a route from the kernel deletion list.
 155  *
 156  *@return -1 on error, else 0
 157  */
 158 static int
 159 olsr_delete_kernel_route(struct rt_entry *rt)
 160 {
 161   if (rt->rt_metric.hops > 1) {
 162     /* multihop route */
 163     if (ip_is_linklocal(&rt->rt_dst.prefix)) {
 164       /* do not delete a route with a LL IP as a destination */
 165       return 0;
 166     }
 167   }
 168
 169   if (!olsr_cnf->host_emul) {
 170     int16_t error = olsr_cnf->ip_version == AF_INET ? olsr_delroute_function(rt) : olsr_delroute6_function(rt);
 171
 172     if (error != 0) {
 173       const char *const err_msg = strerror(errno);
 174       const char *const routestr = olsr_rt_to_string(rt);
 175       OLSR_PRINTF(1, "KERN: ERROR deleting %s: %s\n", routestr, err_msg);
 176
 177       olsr_syslog(OLSR_LOG_ERR, "Delete route %s: %s", routestr, err_msg);
 178       return -1;
 179     }
 180 #ifdef LINUX_NETLINK_ROUTING
 181     /* call NIIT handler (always)*/
 182     if (olsr_cnf->use_niit) {
 183       olsr_niit_handle_route(rt, false);
 184     }
 185 #endif
 186   }
 187   return 0;
 188 }
 189
 190 /**
 191  * Process a route from the kernel addition list.
 192  *
 193  *@return nada
 194  */
 195 static void
 196 olsr_add_kernel_route(struct rt_entry *rt)
 197 {
 198   if (rt->rt_best->rtp_metric.hops > 1) {
 199     /* multihop route */
 200     if (ip_is_linklocal(&rt->rt_best->rtp_dst.prefix)) {
 201       /* do not create a route with a LL IP as a destination */
 202       return;
 203     }
 204   }
 205   if (!olsr_cnf->host_emul) {
 206     int16_t error = (olsr_cnf->ip_version == AF_INET) ? olsr_addroute_function(rt) : olsr_addroute6_function(rt);
 207
 208     if (error != 0) {
 209       const char *const err_msg = strerror(errno);
 210       const char *const routestr = olsr_rtp_to_string(rt->rt_best);
 211       OLSR_PRINTF(1, "KERN: ERROR adding %s: %s\n", routestr, err_msg);
 212
 213       olsr_syslog(OLSR_LOG_ERR, "Add route %s: %s", routestr, err_msg);
 214     } else {
 215       /* route addition has suceeded */
 216
 217       /* save the nexthop and metric in the route entry */
 218       rt->rt_nexthop = rt->rt_best->rtp_nexthop;
 219       rt->rt_metric = rt->rt_best->rtp_metric;
 220
 221 #ifdef LINUX_NETLINK_ROUTING
 222       /* call NIIT handler */
 223       if (olsr_cnf->use_niit) {
 224         olsr_niit_handle_route(rt, true);
 225       }
 226 #endif
 227     }
 228   }
 229 }
 230
 231 /**
 232  * process the kernel change list.
 233  * the routes are already ordered such that nexthop routes
 234  * are on the head of the queue.
 235  * non-nexthop routes need to be changed first and therefore
 236  * the queue needs to be traversed from tail to head.
 237  */
 238 static void
 239 olsr_chg_kernel_routes(struct list_node *head_node)
 240 {
 241   struct rt_entry *rt;
 242
 243   if (list_is_empty(head_node)) {
 244     return;
 245   }
 246
 247   /*
 248    * Traverse from the beginning to the end of the list,
 249    * such that nexthop routes are added first.
 250    */
 251   while (!list_is_empty(head_node)) {
 252     rt = changelist2rt(head_node->next);
 253
 254 /*deleting routes should not be required anymore as we use (NLM_F_CREATE | NLM_F_REPLACE) in linux rtnetlink*/
 255 #ifdef LINUX_NETLINK_ROUTING
 256     /*delete routes with ipv6 only as it still doesn`t support NLM_F_REPLACE or with any fib_metric != flat*/
 257     if (((olsr_cnf->ip_version != AF_INET ) || (olsr_cnf->fib_metric != FIBM_FLAT)
 258          || (olsr_addroute_function != olsr_ioctl_add_route) || (olsr_addroute6_function != olsr_ioctl_add_route6)
 259          || (olsr_delroute_function != olsr_ioctl_del_route) || (olsr_delroute6_function != olsr_ioctl_del_route6))
 260         && (rt->rt_nexthop.iif_index > -1)) {
 261       olsr_delete_kernel_route(rt);
 262     }
 263 #else
 264     /*no rtnetlink we have to delete routes*/
 265     if (rt->rt_nexthop.iif_index > -1) olsr_delete_kernel_route(rt);
 266 #endif /*LINUX_NETLINK_ROUTING*/
 267
 268     olsr_add_kernel_route(rt);
 269
 270     list_remove(&rt->rt_change_node);
 271   }
 272 }
 273
 274 /**
 275  * Check the version number of all route paths hanging off a route entry.
 276  * If a route does not match the current routing tree number, remove it
 277  * from the global originator tree for that rt_entry.
 278  * Reset the best route pointer.
 279  */
 280 static void
 281 olsr_delete_outdated_routes(struct rt_entry *rt)
 282 {
 283   struct rt_path *rtp;
 284   struct avl_node *rtp_tree_node, *next_rtp_tree_node;
 285
 286   for (rtp_tree_node = avl_walk_first(&rt->rt_path_tree); rtp_tree_node != NULL; rtp_tree_node = next_rtp_tree_node) {
 287     /*
 288      * pre-fetch the next node before loosing context.
 289      */
 290     next_rtp_tree_node = avl_walk_next(rtp_tree_node);
 291
 292     rtp = rtp_tree2rtp(rtp_tree_node);
 293
 294     /*
 295      * check the version number which gets incremented on every SPF run.
 296      * comparing for unequalness avoids handling version number wraps.
 297      */
 298     if (routingtree_version != rtp->rtp_version) {
 299       /* remove from the originator tree */
 300       avl_delete(&rt->rt_path_tree, rtp_tree_node);
 301       rtp->rtp_rt = NULL;
 302
 303       if (rt->rt_best == rtp) {
 304         rt->rt_best = NULL;
 305       }
 306     }
 307   }
 308 }
 309
 310 /**
 311  * Walk all the routes, remove outdated routes and run
 312  * best path selection on the remaining set.
 313  * Finally compare the nexthop of the route head and the best
 314  * path and enqueue an add/chg operation.
 315  */
 316 void
 317 olsr_update_rib_routes(void)
 318 {
 319   struct rt_entry *rt;
 320
 321   OLSR_PRINTF(3, "Updating kernel routes...\n");
 322
 323   /* walk all routes in the RIB. */
 324
 325   OLSR_FOR_ALL_RT_ENTRIES(rt) {
 326
 327     /* eliminate first unused routes */
 328     olsr_delete_outdated_routes(rt);
 329
 330     if (!rt->rt_path_tree.count) {
 331
 332       /* oops, all routes are gone - flush the route head */
 333
 334       if (olsr_delete_kernel_route(rt) == 0) {
 335         /*only remove if deletion was successful*/
 336         avl_delete(&routingtree, &rt->rt_tree_node);
 337         olsr_cookie_free(rt_mem_cookie, rt);
 338       }
 339
 340       continue;
 341     }
 342
 343     /* run best route election */
 344     olsr_rt_best(rt);
 345
 346     /* nexthop or hopcount change ? */
 347     if (olsr_nh_change(&rt->rt_best->rtp_nexthop, &rt->rt_nexthop)
 348         || (FIBM_CORRECT == olsr_cnf->fib_metric && olsr_hopcount_change(&rt->rt_best->rtp_metric, &rt->rt_metric))) {
 349
 350         /* this is a route add or change. */
 351         olsr_enqueue_rt(&chg_kernel_list, rt);
 352     }
 353   }
 354   OLSR_FOR_ALL_RT_ENTRIES_END(rt);
 355 }
 356
 357 void
 358 olsr_delete_interface_routes(int if_index) {
 359   struct rt_entry *rt;
 360   bool triggerUpdate = false;
 361
 362   OLSR_FOR_ALL_RT_ENTRIES(rt) {
 363     bool mightTrigger = false;
 364     struct rt_path *rtp;
 365     struct avl_node *rtp_tree_node, *next_rtp_tree_node;
 366
 367     /* run through all routing paths of route */
 368     for (rtp_tree_node = avl_walk_first(&rt->rt_path_tree); rtp_tree_node != NULL; rtp_tree_node = next_rtp_tree_node) {
 369       /*
 370        * pre-fetch the next node before loosing context.
 371        */
 372       next_rtp_tree_node = avl_walk_next(rtp_tree_node);
 373
 374       rtp = rtp_tree2rtp(rtp_tree_node);
 375
 376       /* nexthop use lost interface ? */
 377       if (rtp->rtp_nexthop.iif_index == if_index) {
 378         /* remove from the originator tree */
 379         avl_delete(&rt->rt_path_tree, rtp_tree_node);
 380         rtp->rtp_rt = NULL;
 381
 382         if (rt->rt_best == rtp) {
 383           rt->rt_best = NULL;
 384           mightTrigger = true;
 385         }
 386       }
 387     }
 388
 389     if (mightTrigger) {
 390       if (!rt->rt_path_tree.count) {
 391         /* oops, all routes are gone - flush the route head */
 392         avl_delete(&routingtree, rt_tree_node);
 393
 394         /* do not dequeue route because they are already gone */
 395       }
 396       triggerUpdate = true;
 397     }
 398   } OLSR_FOR_ALL_RT_ENTRIES_END(rt)
 399
 400   /* trigger route update if necessary */
 401   if (triggerUpdate) {
 402     olsr_update_rib_routes();
 403     olsr_update_kernel_routes();
 404   }
 405 }
 406
 407 /**
 408  * Propagate the accumulated changes from the last rib update to the kernel.
 409  */
 410 void
 411 olsr_update_kernel_routes(void)
 412 {
 413   /* route changes */
 414   olsr_chg_kernel_routes(&chg_kernel_list);
 415
 416 #if DEBUG
 417   olsr_print_routing_table(&routingtree);
 418 #endif
 419 }
 420
 421 void
 422 olsr_force_kernelroutes_refresh(void) {
 423   struct rt_entry *rt;
 424
 425   /* enqueue all existing routes for a rewrite */
 426   OLSR_FOR_ALL_RT_ENTRIES(rt) {
 427     olsr_enqueue_rt(&chg_kernel_list, rt);
 428   } OLSR_FOR_ALL_RT_ENTRIES_END(rt)
 429
 430   /* trigger kernel route refresh */
 431   olsr_chg_kernel_routes(&chg_kernel_list);
 432 }
 433
 434 /*
 435  * Local Variables:
 436  * c-basic-offset: 2
 437  * indent-tabs-mode: nil
 438  * End:
 439  */