1a55c36373de7efbd5d040eebca84e9f7ad73280
[olsrd.git] / 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  */