src/process_routes.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 "process_routes.h"
  43 #include "olsr_logging.h"
  44 #include "os_kernel_routes.h"
  45
  46 #include <errno.h>
  47
  48 static struct list_entity chg_kernel_list;
  49
  50 /*
  51  * Function hooks for plugins to intercept
  52  * adding / deleting routes from the kernel
  53  */
  54 export_route_function olsr_add_route_function;
  55 export_route_function olsr_del_route_function;
  56
  57 #define MAX_FAILURE_COUNT 10000 //should be FAILURE_LESS_NOISE_COUNT * (int)x
  58 #define FAILURE_LESS_NOISE_COUNT 100 //after x errors only every x errors this is written to log
  59
  60 void
  61 olsr_init_export_route(void)
  62 {
  63   OLSR_INFO(LOG_ROUTING, "Initialize route processing...\n");
  64
  65   /* the add/chg and del kernel queues */
  66   list_init_head(&chg_kernel_list);
  67
  68   olsr_add_route_function = os_route_add_rtentry;
  69   olsr_del_route_function = os_route_del_rtentry;
  70 }
  71
  72 /**
  73  * Delete all OLSR routes.
  74  *
  75  * This is extremely simple - Just increment the version of the
  76  * tree and then olsr_update_rib_routes() will see all routes in the tree
  77  * as outdated and olsr_update_kernel_routes() will finally flush it.
  78  *
  79  */
  80 void
  81 olsr_delete_all_kernel_routes(void)
  82 {
  83   OLSR_DEBUG(LOG_ROUTING, "Deleting all routes...\n");
  84
  85   olsr_bump_routingtree_version();
  86   olsr_update_rib_routes();
  87   olsr_update_kernel_routes();
  88 }
  89
  90 /**
  91  * Enqueue a route on a kernel chg/del queue.
  92  */
  93 static int
  94 olsr_enqueue_rt(struct list_entity *head_node, struct rt_entry *rt)
  95 {
  96   const struct rt_nexthop *nh;
  97
  98   /* if this node is already on some changelist we are done */
  99   if (list_node_added(&rt->rt_change_node)) {
 100     return -1;
 101   }
 102
 103   /*
 104    * For easier route dependency tracking we enqueue nexthop routes
 105    * at the head of the queue and non-nexthop routes at the tail of the queue.
 106    */
 107   nh = olsr_get_nh(rt);
 108
 109   if (olsr_ipcmp(&rt->rt_dst.prefix, &nh->gateway) == 0) {
 110     list_add_after(head_node, &rt->rt_change_node);
 111   } else {
 112     list_add_before(head_node, &rt->rt_change_node);
 113   }
 114
 115   return 0;
 116 }
 117
 118 /**
 119  * Process a route deletion
 120  *
 121  *@return actual error count
 122  */
 123 static int
 124 olsr_del_route(struct rt_entry *rt)
 125 {
 126   int16_t error;
 127   if (rt->rt_nexthop.interface == NULL) return 0;
 128
 129   error = olsr_del_route_function(rt, olsr_cnf->ip_version);
 130
 131   if (error != 0) {
 132     if (rt->failure_count>0) {
 133       /*ignore if we failed to delete a route we never successfully created*/
 134       OLSR_WARN(LOG_ROUTING, "KERN: SUCCESFULLY failed to delete unexisting %s: %s\n", olsr_rt_to_string(rt), strerror(errno));
 135       rt->failure_count=0;
 136     } else {
 137      rt->failure_count--;
 138
 139      /*rate limit error messages*/
 140      if ( (rt->failure_count >= -FAILURE_LESS_NOISE_COUNT ) || (rt->failure_count % FAILURE_LESS_NOISE_COUNT == 0) )
 141        OLSR_ERROR(LOG_ROUTING, "KERN: ERROR on %d attempt to delete %s: %s\n", rt->failure_count*(-1), olsr_rt_to_string(rt), strerror(errno));
 142
 143      /*stop trying it*/
 144      if (rt->failure_count <= -MAX_FAILURE_COUNT)  {
 145        OLSR_ERROR(LOG_ROUTING, " WILL NOT TRY AGAIN!!\n==============\n");
 146        rt->failure_count=0;
 147      }
 148     }
 149
 150   } else {
 151     if (rt->failure_count > 1)
 152       OLSR_WARN(LOG_ROUTING, "KERN: SUCCESS on %d attempt to delete %s: %s\n", rt->failure_count*(-1), olsr_rt_to_string(rt), strerror(errno));
 153
 154     rt->failure_count=0;
 155     /* release the interface. */
 156     unlock_interface(rt->rt_nexthop.interface);
 157   }
 158
 159   return rt->failure_count;
 160 }
 161
 162 /**
 163  * Process a route from the kernel addition list.
 164  *
 165  *@return nada
 166  */
 167 static void
 168 olsr_add_route(struct rt_entry *rt)
 169 {
 170   rt->failure_count++;
 171
 172   if (0 != olsr_add_route_function(rt, olsr_cnf->ip_version)) {
 173     /*rate limit error messages*/
 174     if ( (rt->failure_count <= FAILURE_LESS_NOISE_COUNT ) || (rt->failure_count % FAILURE_LESS_NOISE_COUNT == 0) )
 175       OLSR_ERROR(LOG_ROUTING, "KERN: ERROR on %d attempt to add %s: %s\n", rt->failure_count, olsr_rtp_to_string(rt->rt_best), strerror(errno));
 176
 177     /*stop trying it*/
 178     if (rt->failure_count >= MAX_FAILURE_COUNT)  {
 179        OLSR_ERROR(LOG_ROUTING, " WILL NOT TRY AGAIN!!\n==============\n");
 180        rt->failure_count=0;
 181      }
 182   } else {
 183     /* route addition has suceeded */
 184
 185     /* save the nexthop and metric in the route entry */
 186     rt->rt_nexthop = rt->rt_best->rtp_nexthop;
 187     rt->rt_metric = rt->rt_best->rtp_metric;
 188
 189     /* lock the interface such that it does not vanish underneath us */
 190     lock_interface(rt->rt_nexthop.interface);
 191
 192     /*reset failure_counter and print info if we needed more than once*/
 193     if (rt->failure_count > 1)
 194       OLSR_WARN(LOG_ROUTING, "KERN: SUCCESS on %d attmpt to add %s: %s\n", rt->failure_count, olsr_rtp_to_string(rt->rt_best), strerror(errno));
 195     rt->failure_count=0;
 196   }
 197 }
 198
 199 /**
 200  * process the kernel change list.
 201  * the routes are already ordered such that nexthop routes
 202  * are on the head of the queue.
 203  * non-nexthop routes need to be changed first and therefore
 204  * the queue needs to be traversed from tail to head.
 205  */
 206 static void
 207 olsr_chg_kernel_routes(struct list_entity *head_node)
 208 {
 209   struct rt_entry *rt;
 210   struct list_iterator iterator;
 211
 212   if (list_is_empty(head_node)) {
 213     return;
 214   }
 215
 216   /*
 217    * Traverse from the beginning to the end of the list,
 218    * such that nexthop routes are added first.
 219    */
 220   OLSR_FOR_ALL_RTLIST_ENTRIES(head_node, rt, iterator) {
 221
 222     /*if netlink and NLFM_REPLACE is available (ipv4 only?) and used in linux/kernel_*.c no delete would be necesarry here */
 223     if (rt->rt_nexthop.interface) olsr_del_route(rt); // fresh routes do not have an interface pointer
 224
 225     olsr_add_route(rt);
 226
 227     list_remove(&rt->rt_change_node);
 228   }
 229 }
 230
 231 /**
 232  * Check the version number of all route paths hanging off a route entry.
 233  * If a route does not match the current routing tree number, remove it
 234  * from the global originator tree for that rt_entry.
 235  * Reset the best route pointer.
 236  */
 237 static void
 238 olsr_delete_outdated_routes(struct rt_entry *rt)
 239 {
 240   struct rt_path *rtp;
 241   struct list_iterator iterator;
 242
 243   OLSR_FOR_ALL_RT_PATH_ENTRIES(rt, rtp, iterator) {
 244     /*
 245      * check the version number which gets incremented on every SPF run.
 246      * comparing for unequalness avoids handling version number wraps.
 247      */
 248     if (routingtree_version != rtp->rtp_version) {
 249
 250       /* remove from the originator tree */
 251       avl_delete(&rt->rt_path_tree, &rtp->rtp_tree_node);
 252       rtp->rtp_rt = NULL;
 253     }
 254   }
 255
 256   /* safety measure against dangling pointers */
 257   rt->rt_best = NULL;
 258 }
 259
 260 /**
 261  * Walk all the routes, remove outdated routes and run
 262  * best path selection on the remaining set.
 263  * Finally compare the nexthop of the route head and the best
 264  * path and enqueue an add/chg operation.
 265  */
 266 void
 267 olsr_update_rib_routes(void)
 268 {
 269   struct rt_entry *rt;
 270   struct list_iterator iterator;
 271
 272   OLSR_DEBUG(LOG_ROUTING, "Updating kernel routes...\n");
 273
 274   /* walk all routes in the RIB. */
 275
 276   OLSR_FOR_ALL_RT_ENTRIES(rt, iterator) {
 277
 278     /* eliminate first unused routes */
 279     olsr_delete_outdated_routes(rt);
 280
 281     if (!rt->rt_path_tree.count) {
 282       /* oops, all routes are gone - flush the route head */
 283       if (olsr_del_route(rt) == 0) avl_delete(&routingtree, &rt->rt_tree_node);
 284
 285       continue;
 286     }
 287
 288     /* run best route election */
 289     olsr_rt_best(rt);
 290
 291     /* nexthop or hopcount change ? */
 292     if (olsr_nh_change(&rt->rt_best->rtp_nexthop, &rt->rt_nexthop) ||
 293         (FIBM_CORRECT == olsr_cnf->fib_metric && olsr_hopcount_change(&rt->rt_best->rtp_metric, &rt->rt_metric))) {
 294
 295       olsr_enqueue_rt(&chg_kernel_list, rt);
 296
 297     }
 298   }
 299 }
 300
 301 /**
 302  * Propagate the accumulated changes from the last rib update to the kernel.
 303  */
 304 void
 305 olsr_update_kernel_routes(void)
 306 {
 307
 308   /* route changes and additions */
 309   olsr_chg_kernel_routes(&chg_kernel_list);
 310
 311 #ifdef DEBUG
 312   olsr_print_routing_table();
 313 #endif
 314 }
 315
 316 /*
 317  * Local Variables:
 318  * c-basic-offset: 2
 319  * indent-tabs-mode: nil
 320  * End:
 321  */