3 * The olsr.org Optimized Link-State Routing daemon(olsrd)
4 * Copyright (c) 2004-2009, the olsr.org team - see HISTORY file
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
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
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.
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.
34 * Visit http://www.olsr.org for more information.
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.
42 #include "process_routes.h"
43 #include "olsr_logging.h"
44 #include "os_kernel_routes.h"
48 static struct list_entity chg_kernel_list;
51 * Function hooks for plugins to intercept
52 * adding / deleting routes from the kernel
54 export_route_function olsr_add_route_function;
55 export_route_function olsr_del_route_function;
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
61 olsr_init_export_route(void)
63 OLSR_INFO(LOG_ROUTING, "Initialize route processing...\n");
65 /* the add/chg and del kernel queues */
66 list_init_head(&chg_kernel_list);
68 olsr_add_route_function = os_route_add_rtentry;
69 olsr_del_route_function = os_route_del_rtentry;
73 * Delete all OLSR routes.
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.
81 olsr_delete_all_kernel_routes(void)
83 OLSR_DEBUG(LOG_ROUTING, "Deleting all routes...\n");
85 olsr_bump_routingtree_version();
86 olsr_update_rib_routes();
87 olsr_update_kernel_routes();
91 * Enqueue a route on a kernel chg/del queue.
94 olsr_enqueue_rt(struct list_entity *head_node, struct rt_entry *rt)
96 const struct rt_nexthop *nh;
98 /* if this node is already on some changelist we are done */
99 if (list_node_added(&rt->rt_change_node)) {
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.
107 nh = olsr_get_nh(rt);
109 if (olsr_ipcmp(&rt->rt_dst.prefix, &nh->gateway) == 0) {
110 list_add_after(head_node, &rt->rt_change_node);
112 list_add_before(head_node, &rt->rt_change_node);
119 * Process a route deletion
121 *@return actual error count
124 olsr_del_route(struct rt_entry *rt)
127 if (rt->rt_nexthop.interface == NULL) return 0;
129 error = olsr_del_route_function(rt, olsr_cnf->ip_version);
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));
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));
144 if (rt->failure_count <= -MAX_FAILURE_COUNT) {
145 OLSR_ERROR(LOG_ROUTING, " WILL NOT TRY AGAIN!!\n==============\n");
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));
155 /* release the interface. */
156 unlock_interface(rt->rt_nexthop.interface);
159 return rt->failure_count;
163 * Process a route from the kernel addition list.
168 olsr_add_route(struct rt_entry *rt)
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));
178 if (rt->failure_count >= MAX_FAILURE_COUNT) {
179 OLSR_ERROR(LOG_ROUTING, " WILL NOT TRY AGAIN!!\n==============\n");
183 /* route addition has suceeded */
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;
189 /* lock the interface such that it does not vanish underneath us */
190 lock_interface(rt->rt_nexthop.interface);
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));
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.
207 olsr_chg_kernel_routes(struct list_entity *head_node)
210 struct list_iterator iterator;
212 if (list_is_empty(head_node)) {
217 * Traverse from the beginning to the end of the list,
218 * such that nexthop routes are added first.
220 OLSR_FOR_ALL_RTLIST_ENTRIES(head_node, rt, iterator) {
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
227 list_remove(&rt->rt_change_node);
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.
238 olsr_delete_outdated_routes(struct rt_entry *rt)
241 struct list_iterator iterator;
243 OLSR_FOR_ALL_RT_PATH_ENTRIES(rt, rtp, iterator) {
245 * check the version number which gets incremented on every SPF run.
246 * comparing for unequalness avoids handling version number wraps.
248 if (routingtree_version != rtp->rtp_version) {
250 /* remove from the originator tree */
251 avl_delete(&rt->rt_path_tree, &rtp->rtp_tree_node);
256 /* safety measure against dangling pointers */
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.
267 olsr_update_rib_routes(void)
270 struct list_iterator iterator;
272 OLSR_DEBUG(LOG_ROUTING, "Updating kernel routes...\n");
274 /* walk all routes in the RIB. */
276 OLSR_FOR_ALL_RT_ENTRIES(rt, iterator) {
278 /* eliminate first unused routes */
279 olsr_delete_outdated_routes(rt);
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);
288 /* run best route election */
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))) {
295 olsr_enqueue_rt(&chg_kernel_list, rt);
302 * Propagate the accumulated changes from the last rib update to the kernel.
305 olsr_update_kernel_routes(void)
308 /* route changes and additions */
309 olsr_chg_kernel_routes(&chg_kernel_list);
312 olsr_print_routing_table();
319 * indent-tabs-mode: nil