From 5734509c0545ebd95a5b8e3f22a911c1a39ffa1b Mon Sep 17 00:00:00 2001 From: Paul Jakma Date: Sun, 25 Dec 2011 17:52:09 +0100 Subject: babeld: Initial import, for Babel routing protocol. * Initial import of the Babel routing protocol, ported to Quagga. * LICENCE: Update the original LICENCE file to include all known potentially applicable copyright claims. Ask that any future contributors to babeld/ grant MIT/X11 licence to their work. * *.{c,h}: Add GPL headers, in according with the SFLC guidance on dealing with potentially mixed GPL/other licensed work, at: https://www.softwarefreedom.org/resources/2007/gpl-non-gpl-collaboration.html --- babeld/route.c | 756 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 756 insertions(+) create mode 100644 babeld/route.c (limited to 'babeld/route.c') diff --git a/babeld/route.c b/babeld/route.c new file mode 100644 index 00000000..e0c9d047 --- /dev/null +++ b/babeld/route.c @@ -0,0 +1,756 @@ +/* + * This file is free software: you may copy, redistribute and/or modify it + * under the terms of the GNU General Public License as published by the + * Free Software Foundation, either version 2 of the License, or (at your + * option) any later version. + * + * This file is distributed in the hope that it will be useful, but + * WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + * + * This file incorporates work covered by the following copyright and + * permission notice: + * +Copyright (c) 2007, 2008 by Juliusz Chroboczek +Copyright 2011 by Matthieu Boutier and Juliusz Chroboczek + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in +all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN +THE SOFTWARE. +*/ + +#include +#include +#include +#include +#include +#include + +#include +#include "if.h" + +#include "babeld.h" +#include "util.h" +#include "kernel.h" +#include "babel_interface.h" +#include "source.h" +#include "neighbour.h" +#include "route.h" +#include "xroute.h" +#include "message.h" +#include "resend.h" + +static void consider_route(struct route *route); + +struct route *routes = NULL; +int numroutes = 0, maxroutes = 0; +int kernel_metric = 0; +int allow_duplicates = -1; + +struct route * +find_route(const unsigned char *prefix, unsigned char plen, + struct neighbour *neigh, const unsigned char *nexthop) +{ + int i; + for(i = 0; i < numroutes; i++) { + if(routes[i].neigh == neigh && + memcmp(routes[i].nexthop, nexthop, 16) == 0 && + source_match(routes[i].src, prefix, plen)) + return &routes[i]; + } + return NULL; +} + +struct route * +find_installed_route(const unsigned char *prefix, unsigned char plen) +{ + int i; + for(i = 0; i < numroutes; i++) { + if(routes[i].installed && source_match(routes[i].src, prefix, plen)) + return &routes[i]; + } + return NULL; +} + +void +flush_route(struct route *route) +{ + int i; + struct source *src; + unsigned oldmetric; + int lost = 0; + + i = route - routes; + assert(i >= 0 && i < numroutes); + + oldmetric = route_metric(route); + + if(route->installed) { + uninstall_route(route); + lost = 1; + } + + src = route->src; + + if(i != numroutes - 1) + memcpy(routes + i, routes + numroutes - 1, sizeof(struct route)); + numroutes--; + VALGRIND_MAKE_MEM_UNDEFINED(routes + numroutes, sizeof(struct route)); + + if(numroutes == 0) { + free(routes); + routes = NULL; + maxroutes = 0; + } else if(maxroutes > 8 && numroutes < maxroutes / 4) { + struct route *new_routes; + int n = maxroutes / 2; + new_routes = realloc(routes, n * sizeof(struct route)); + if(new_routes != NULL) { + routes = new_routes; + maxroutes = n; + } + } + + if(lost) + route_lost(src, oldmetric); +} + +void +flush_neighbour_routes(struct neighbour *neigh) +{ + int i; + + i = 0; + while(i < numroutes) { + if(routes[i].neigh == neigh) { + flush_route(&routes[i]); + continue; + } + i++; + } +} + +void +flush_interface_routes(struct interface *ifp, int v4only) +{ + int i; + + i = 0; + while(i < numroutes) { + if(routes[i].neigh->ifp == ifp && + (!v4only || v4mapped(routes[i].nexthop))) { + flush_route(&routes[i]); + continue; + } + i++; + } +} + +static int +metric_to_kernel(int metric) +{ + return metric < INFINITY ? kernel_metric : KERNEL_INFINITY; +} + +void +install_route(struct route *route) +{ + int rc; + + if(route->installed) + return; + + if(!route_feasible(route)) + fprintf(stderr, "WARNING: installing unfeasible route " + "(this shouldn't happen)."); + + rc = kernel_route(ROUTE_ADD, route->src->prefix, route->src->plen, + route->nexthop, + route->neigh->ifp->ifindex, + metric_to_kernel(route_metric(route)), NULL, 0, 0); + if(rc < 0) { + int save = errno; + zlog_err("kernel_route(ADD): %s", safe_strerror(errno)); + if(save != EEXIST) + return; + } + route->installed = 1; +} + +void +uninstall_route(struct route *route) +{ + int rc; + + if(!route->installed) + return; + + rc = kernel_route(ROUTE_FLUSH, route->src->prefix, route->src->plen, + route->nexthop, + route->neigh->ifp->ifindex, + metric_to_kernel(route_metric(route)), NULL, 0, 0); + if(rc < 0) + zlog_err("kernel_route(FLUSH): %s", safe_strerror(errno)); + + route->installed = 0; +} + +/* This is equivalent to uninstall_route followed with install_route, + but without the race condition. The destination of both routes + must be the same. */ + +static void +switch_routes(struct route *old, struct route *new) +{ + int rc; + + if(!old) { + install_route(new); + return; + } + + if(!old->installed) + return; + + if(!route_feasible(new)) + fprintf(stderr, "WARNING: switching to unfeasible route " + "(this shouldn't happen)."); + + rc = kernel_route(ROUTE_MODIFY, old->src->prefix, old->src->plen, + old->nexthop, old->neigh->ifp->ifindex, + metric_to_kernel(route_metric(old)), + new->nexthop, new->neigh->ifp->ifindex, + metric_to_kernel(route_metric(new))); + if(rc < 0) { + zlog_err("kernel_route(MODIFY): %s", safe_strerror(errno)); + return; + } + + old->installed = 0; + new->installed = 1; +} + +static void +change_route_metric(struct route *route, unsigned newmetric) +{ + int old, new; + + if(route_metric(route) == newmetric) + return; + + old = metric_to_kernel(route_metric(route)); + new = metric_to_kernel(newmetric); + + if(route->installed && old != new) { + int rc; + rc = kernel_route(ROUTE_MODIFY, route->src->prefix, route->src->plen, + route->nexthop, route->neigh->ifp->ifindex, + old, + route->nexthop, route->neigh->ifp->ifindex, + new); + if(rc < 0) { + zlog_err("kernel_route(MODIFY metric): %s", safe_strerror(errno)); + return; + } + } + + route->metric = newmetric; +} + +static void +retract_route(struct route *route) +{ + route->refmetric = INFINITY; + change_route_metric(route, INFINITY); +} + +int +route_feasible(struct route *route) +{ + return update_feasible(route->src, route->seqno, route->refmetric); +} + +int +route_old(struct route *route) +{ + return route->time < babel_now.tv_sec - route->hold_time * 7 / 8; +} + +int +route_expired(struct route *route) +{ + return route->time < babel_now.tv_sec - route->hold_time; +} + +int +update_feasible(struct source *src, + unsigned short seqno, unsigned short refmetric) +{ + if(src == NULL) + return 1; + + if(src->time < babel_now.tv_sec - SOURCE_GC_TIME) + /* Never mind what is probably stale data */ + return 1; + + if(refmetric >= INFINITY) + /* Retractions are always feasible */ + return 1; + + return (seqno_compare(seqno, src->seqno) > 0 || + (src->seqno == seqno && refmetric < src->metric)); +} + +/* This returns the feasible route with the smallest metric. */ +struct route * +find_best_route(const unsigned char *prefix, unsigned char plen, int feasible, + struct neighbour *exclude) +{ + struct route *route = NULL; + int i; + + for(i = 0; i < numroutes; i++) { + if(!source_match(routes[i].src, prefix, plen)) + continue; + if(route_expired(&routes[i])) + continue; + if(feasible && !route_feasible(&routes[i])) + continue; + if(exclude && routes[i].neigh == exclude) + continue; + if(route && route_metric(route) <= route_metric(&routes[i])) + continue; + route = &routes[i]; + } + return route; +} + +void +update_route_metric(struct route *route) +{ + int oldmetric = route_metric(route); + + if(route_expired(route)) { + if(route->refmetric < INFINITY) { + route->seqno = seqno_plus(route->src->seqno, 1); + retract_route(route); + if(oldmetric < INFINITY) + route_changed(route, route->src, oldmetric); + } + } else { + struct neighbour *neigh = route->neigh; + int add_metric = input_filter(route->src->id, + route->src->prefix, route->src->plen, + neigh->address, + neigh->ifp->ifindex); + int newmetric = MIN(route->refmetric + + add_metric + + neighbour_cost(route->neigh), + INFINITY); + + if(newmetric != oldmetric) { + change_route_metric(route, newmetric); + route_changed(route, route->src, oldmetric); + } + } +} + +/* Called whenever a neighbour's cost changes, to update the metric of + all routes through that neighbour. */ +void +update_neighbour_metric(struct neighbour *neigh, int changed) +{ + if(changed) { + int i; + + i = 0; + while(i < numroutes) { + if(routes[i].neigh == neigh) + update_route_metric(&routes[i]); + i++; + } + } +} + +void +update_interface_metric(struct interface *ifp) +{ + int i; + + i = 0; + while(i < numroutes) { + if(routes[i].neigh->ifp == ifp) + update_route_metric(&routes[i]); + i++; + } +} + +/* This is called whenever we receive an update. */ +struct route * +update_route(const unsigned char *router_id, + const unsigned char *prefix, unsigned char plen, + unsigned short seqno, unsigned short refmetric, + unsigned short interval, + struct neighbour *neigh, const unsigned char *nexthop) +{ + struct route *route; + struct source *src; + int metric, feasible; + int add_metric; + int hold_time = MAX((4 * interval) / 100 + interval / 50, 15); + + if(memcmp(router_id, myid, 8) == 0) + return NULL; /* I have announced the route */ + + if(martian_prefix(prefix, plen)) { + fprintf(stderr, "Rejecting martian route to %s through %s.\n", + format_prefix(prefix, plen), format_address(router_id)); + return NULL; + } + + add_metric = input_filter(router_id, prefix, plen, + neigh->address, neigh->ifp->ifindex); + if(add_metric >= INFINITY) + return NULL; + + src = find_source(router_id, prefix, plen, 1, seqno); + if(src == NULL) + return NULL; + + feasible = update_feasible(src, seqno, refmetric); + route = find_route(prefix, plen, neigh, nexthop); + metric = MIN((int)refmetric + neighbour_cost(neigh) + add_metric, INFINITY); + + if(route) { + struct source *oldsrc; + unsigned short oldmetric; + int lost = 0; + + oldsrc = route->src; + oldmetric = route_metric(route); + + /* If a successor switches sources, we must accept his update even + if it makes a route unfeasible in order to break any routing loops + in a timely manner. If the source remains the same, we ignore + the update. */ + if(!feasible && route->installed) { + debugf(BABEL_DEBUG_COMMON,"Unfeasible update for installed route to %s " + "(%s %d %d -> %s %d %d).", + format_prefix(src->prefix, src->plen), + format_address(route->src->id), + route->seqno, route->refmetric, + format_address(src->id), seqno, refmetric); + if(src != route->src) { + uninstall_route(route); + lost = 1; + } + } + + route->src = src; + if(feasible && refmetric < INFINITY) + route->time = babel_now.tv_sec; + route->seqno = seqno; + route->refmetric = refmetric; + change_route_metric(route, metric); + route->hold_time = hold_time; + + route_changed(route, oldsrc, oldmetric); + if(lost) + route_lost(oldsrc, oldmetric); + + if(!feasible) + send_unfeasible_request(neigh, route->installed && route_old(route), + seqno, metric, src); + } else { + if(refmetric >= INFINITY) + /* Somebody's retracting a route we never saw. */ + return NULL; + if(!feasible) { + send_unfeasible_request(neigh, 0, seqno, metric, src); + return NULL; + } + if(numroutes >= maxroutes) { + struct route *new_routes; + int n = maxroutes < 1 ? 8 : 2 * maxroutes; + new_routes = routes == NULL ? + malloc(n * sizeof(struct route)) : + realloc(routes, n * sizeof(struct route)); + if(new_routes == NULL) + return NULL; + maxroutes = n; + routes = new_routes; + } + route = &routes[numroutes]; + route->src = src; + route->refmetric = refmetric; + route->seqno = seqno; + route->metric = metric; + route->neigh = neigh; + memcpy(route->nexthop, nexthop, 16); + route->time = babel_now.tv_sec; + route->hold_time = hold_time; + route->installed = 0; + numroutes++; + consider_route(route); + } + return route; +} + +/* We just received an unfeasible update. If it's any good, send + a request for a new seqno. */ +void +send_unfeasible_request(struct neighbour *neigh, int force, + unsigned short seqno, unsigned short metric, + struct source *src) +{ + struct route *route = find_installed_route(src->prefix, src->plen); + + if(seqno_minus(src->seqno, seqno) > 100) { + /* Probably a source that lost its seqno. Let it time-out. */ + return; + } + + if(force || !route || route_metric(route) >= metric + 512) { + send_unicast_multihop_request(neigh, src->prefix, src->plen, + src->metric >= INFINITY ? + src->seqno : + seqno_plus(src->seqno, 1), + src->id, 127); + } +} + +/* This takes a feasible route and decides whether to install it. */ +static void +consider_route(struct route *route) +{ + struct route *installed; + struct xroute *xroute; + + if(route->installed) + return; + + if(!route_feasible(route)) + return; + + xroute = find_xroute(route->src->prefix, route->src->plen); + if(xroute && (allow_duplicates < 0 || xroute->metric >= allow_duplicates)) + return; + + installed = find_installed_route(route->src->prefix, route->src->plen); + + if(installed == NULL) + goto install; + + if(route_metric(route) >= INFINITY) + return; + + if(route_metric(installed) >= INFINITY) + goto install; + + if(route_metric(installed) >= route_metric(route) + 192) + goto install; + + /* Avoid switching sources */ + if(installed->src != route->src) + return; + + if(route_metric(installed) >= route_metric(route) + 64) + goto install; + + return; + + install: + switch_routes(installed, route); + if(installed && route->installed) + send_triggered_update(route, installed->src, route_metric(installed)); + else + send_update(NULL, 1, route->src->prefix, route->src->plen); + return; +} + +void +retract_neighbour_routes(struct neighbour *neigh) +{ + int i; + + i = 0; + while(i < numroutes) { + if(routes[i].neigh == neigh) { + if(routes[i].refmetric != INFINITY) { + unsigned short oldmetric = route_metric(&routes[i]); + retract_route(&routes[i]); + if(oldmetric != INFINITY) + route_changed(&routes[i], routes[i].src, oldmetric); + } + } + i++; + } +} + +void +send_triggered_update(struct route *route, struct source *oldsrc, + unsigned oldmetric) +{ + unsigned newmetric, diff; + /* 1 means send speedily, 2 means resend */ + int urgent; + + if(!route->installed) + return; + + newmetric = route_metric(route); + diff = + newmetric >= oldmetric ? newmetric - oldmetric : oldmetric - newmetric; + + if(route->src != oldsrc || (oldmetric < INFINITY && newmetric >= INFINITY)) + /* Switching sources can cause transient routing loops. + Retractions can cause blackholes. */ + urgent = 2; + else if(newmetric > oldmetric && oldmetric < 6 * 256 && diff >= 512) + /* Route getting significantly worse */ + urgent = 1; + else if(unsatisfied_request(route->src->prefix, route->src->plen, + route->seqno, route->src->id)) + /* Make sure that requests are satisfied speedily */ + urgent = 1; + else if(oldmetric >= INFINITY && newmetric < INFINITY) + /* New route */ + urgent = 0; + else if(newmetric < oldmetric && diff < 1024) + /* Route getting better. This may be a transient fluctuation, so + don't advertise it to avoid making routes unfeasible later on. */ + return; + else if(diff < 384) + /* Don't fret about trivialities */ + return; + else + urgent = 0; + + if(urgent >= 2) + send_update_resend(NULL, route->src->prefix, route->src->plen); + else + send_update(NULL, urgent, route->src->prefix, route->src->plen); + + if(oldmetric < INFINITY) { + if(newmetric >= oldmetric + 512) { + send_request_resend(NULL, route->src->prefix, route->src->plen, + route->src->metric >= INFINITY ? + route->src->seqno : + seqno_plus(route->src->seqno, 1), + route->src->id); + } else if(newmetric >= oldmetric + 288) { + send_request(NULL, route->src->prefix, route->src->plen); + } + } +} + +/* A route has just changed. Decide whether to switch to a different route or + send an update. */ +void +route_changed(struct route *route, + struct source *oldsrc, unsigned short oldmetric) +{ + if(route->installed) { + if(route_metric(route) > oldmetric) { + struct route *better_route; + better_route = + find_best_route(route->src->prefix, route->src->plen, 1, NULL); + if(better_route && + route_metric(better_route) <= route_metric(route) - 96) + consider_route(better_route); + } + + if(route->installed) + /* We didn't change routes after all. */ + send_triggered_update(route, oldsrc, oldmetric); + } else { + /* Reconsider routes even when their metric didn't decrease, + they may not have been feasible before. */ + consider_route(route); + } +} + +/* We just lost the installed route to a given destination. */ +void +route_lost(struct source *src, unsigned oldmetric) +{ + struct route *new_route; + new_route = find_best_route(src->prefix, src->plen, 1, NULL); + if(new_route) { + consider_route(new_route); + } else if(oldmetric < INFINITY) { + /* Complain loudly. */ + send_update_resend(NULL, src->prefix, src->plen); + send_request_resend(NULL, src->prefix, src->plen, + src->metric >= INFINITY ? + src->seqno : seqno_plus(src->seqno, 1), + src->id); + } +} + +void +expire_routes(void) +{ + int i; + + debugf(BABEL_DEBUG_COMMON,"Expiring old routes."); + + i = 0; + while(i < numroutes) { + struct route *route = &routes[i]; + + if(route->time > babel_now.tv_sec || /* clock stepped */ + route_old(route)) { + flush_route(route); + continue; + } + + update_route_metric(route); + + if(route->installed && route->refmetric < INFINITY) { + if(route_old(route)) + send_unicast_request(route->neigh, + route->src->prefix, route->src->plen); + } + i++; + } +} + +void +babel_uninstall_all_routes(void) +{ + while(numroutes > 0) { + uninstall_route(&routes[0]); + /* We need to flush the route so network_up won't reinstall it */ + flush_route(&routes[0]); + } +} + +struct route * +babel_route_get_by_source(struct source *src) +{ + int i; + for(i = 0; i < numroutes; i++) { + if(routes[i].src == src) + return &routes[i]; + } + return NULL; +} -- cgit v1.2.1 From ef4de4d36c2dc10a68d41e518057d04b262ec867 Mon Sep 17 00:00:00 2001 From: Denis Ovsienko Date: Sun, 8 Jan 2012 15:29:19 +0400 Subject: babeld: address FreeBSD "struct route" issue FreeBSD system headers have their own "struct route", which made it impossible to compile babeld. Switching babeld to "struct babel_route". --- babeld/route.c | 68 +++++++++++++++++++++++++++++----------------------------- 1 file changed, 34 insertions(+), 34 deletions(-) (limited to 'babeld/route.c') diff --git a/babeld/route.c b/babeld/route.c index e0c9d047..a92018fd 100644 --- a/babeld/route.c +++ b/babeld/route.c @@ -58,14 +58,14 @@ THE SOFTWARE. #include "message.h" #include "resend.h" -static void consider_route(struct route *route); +static void consider_route(struct babel_route *route); -struct route *routes = NULL; +struct babel_route *routes = NULL; int numroutes = 0, maxroutes = 0; int kernel_metric = 0; int allow_duplicates = -1; -struct route * +struct babel_route * find_route(const unsigned char *prefix, unsigned char plen, struct neighbour *neigh, const unsigned char *nexthop) { @@ -79,7 +79,7 @@ find_route(const unsigned char *prefix, unsigned char plen, return NULL; } -struct route * +struct babel_route * find_installed_route(const unsigned char *prefix, unsigned char plen) { int i; @@ -91,7 +91,7 @@ find_installed_route(const unsigned char *prefix, unsigned char plen) } void -flush_route(struct route *route) +flush_route(struct babel_route *route) { int i; struct source *src; @@ -111,18 +111,18 @@ flush_route(struct route *route) src = route->src; if(i != numroutes - 1) - memcpy(routes + i, routes + numroutes - 1, sizeof(struct route)); + memcpy(routes + i, routes + numroutes - 1, sizeof(struct babel_route)); numroutes--; - VALGRIND_MAKE_MEM_UNDEFINED(routes + numroutes, sizeof(struct route)); + VALGRIND_MAKE_MEM_UNDEFINED(routes + numroutes, sizeof(struct babel_route)); if(numroutes == 0) { free(routes); routes = NULL; maxroutes = 0; } else if(maxroutes > 8 && numroutes < maxroutes / 4) { - struct route *new_routes; + struct babel_route *new_routes; int n = maxroutes / 2; - new_routes = realloc(routes, n * sizeof(struct route)); + new_routes = realloc(routes, n * sizeof(struct babel_route)); if(new_routes != NULL) { routes = new_routes; maxroutes = n; @@ -171,7 +171,7 @@ metric_to_kernel(int metric) } void -install_route(struct route *route) +install_route(struct babel_route *route) { int rc; @@ -196,7 +196,7 @@ install_route(struct route *route) } void -uninstall_route(struct route *route) +uninstall_route(struct babel_route *route) { int rc; @@ -218,7 +218,7 @@ uninstall_route(struct route *route) must be the same. */ static void -switch_routes(struct route *old, struct route *new) +switch_routes(struct babel_route *old, struct babel_route *new) { int rc; @@ -249,7 +249,7 @@ switch_routes(struct route *old, struct route *new) } static void -change_route_metric(struct route *route, unsigned newmetric) +change_route_metric(struct babel_route *route, unsigned newmetric) { int old, new; @@ -276,26 +276,26 @@ change_route_metric(struct route *route, unsigned newmetric) } static void -retract_route(struct route *route) +retract_route(struct babel_route *route) { route->refmetric = INFINITY; change_route_metric(route, INFINITY); } int -route_feasible(struct route *route) +route_feasible(struct babel_route *route) { return update_feasible(route->src, route->seqno, route->refmetric); } int -route_old(struct route *route) +route_old(struct babel_route *route) { return route->time < babel_now.tv_sec - route->hold_time * 7 / 8; } int -route_expired(struct route *route) +route_expired(struct babel_route *route) { return route->time < babel_now.tv_sec - route->hold_time; } @@ -320,11 +320,11 @@ update_feasible(struct source *src, } /* This returns the feasible route with the smallest metric. */ -struct route * +struct babel_route * find_best_route(const unsigned char *prefix, unsigned char plen, int feasible, struct neighbour *exclude) { - struct route *route = NULL; + struct babel_route *route = NULL; int i; for(i = 0; i < numroutes; i++) { @@ -344,7 +344,7 @@ find_best_route(const unsigned char *prefix, unsigned char plen, int feasible, } void -update_route_metric(struct route *route) +update_route_metric(struct babel_route *route) { int oldmetric = route_metric(route); @@ -404,14 +404,14 @@ update_interface_metric(struct interface *ifp) } /* This is called whenever we receive an update. */ -struct route * +struct babel_route * update_route(const unsigned char *router_id, const unsigned char *prefix, unsigned char plen, unsigned short seqno, unsigned short refmetric, unsigned short interval, struct neighbour *neigh, const unsigned char *nexthop) { - struct route *route; + struct babel_route *route; struct source *src; int metric, feasible; int add_metric; @@ -488,11 +488,11 @@ update_route(const unsigned char *router_id, return NULL; } if(numroutes >= maxroutes) { - struct route *new_routes; + struct babel_route *new_routes; int n = maxroutes < 1 ? 8 : 2 * maxroutes; new_routes = routes == NULL ? - malloc(n * sizeof(struct route)) : - realloc(routes, n * sizeof(struct route)); + malloc(n * sizeof(struct babel_route)) : + realloc(routes, n * sizeof(struct babel_route)); if(new_routes == NULL) return NULL; maxroutes = n; @@ -521,7 +521,7 @@ send_unfeasible_request(struct neighbour *neigh, int force, unsigned short seqno, unsigned short metric, struct source *src) { - struct route *route = find_installed_route(src->prefix, src->plen); + struct babel_route *route = find_installed_route(src->prefix, src->plen); if(seqno_minus(src->seqno, seqno) > 100) { /* Probably a source that lost its seqno. Let it time-out. */ @@ -539,9 +539,9 @@ send_unfeasible_request(struct neighbour *neigh, int force, /* This takes a feasible route and decides whether to install it. */ static void -consider_route(struct route *route) +consider_route(struct babel_route *route) { - struct route *installed; + struct babel_route *installed; struct xroute *xroute; if(route->installed) @@ -606,7 +606,7 @@ retract_neighbour_routes(struct neighbour *neigh) } void -send_triggered_update(struct route *route, struct source *oldsrc, +send_triggered_update(struct babel_route *route, struct source *oldsrc, unsigned oldmetric) { unsigned newmetric, diff; @@ -665,12 +665,12 @@ send_triggered_update(struct route *route, struct source *oldsrc, /* A route has just changed. Decide whether to switch to a different route or send an update. */ void -route_changed(struct route *route, +route_changed(struct babel_route *route, struct source *oldsrc, unsigned short oldmetric) { if(route->installed) { if(route_metric(route) > oldmetric) { - struct route *better_route; + struct babel_route *better_route; better_route = find_best_route(route->src->prefix, route->src->plen, 1, NULL); if(better_route && @@ -692,7 +692,7 @@ route_changed(struct route *route, void route_lost(struct source *src, unsigned oldmetric) { - struct route *new_route; + struct babel_route *new_route; new_route = find_best_route(src->prefix, src->plen, 1, NULL); if(new_route) { consider_route(new_route); @@ -715,7 +715,7 @@ expire_routes(void) i = 0; while(i < numroutes) { - struct route *route = &routes[i]; + struct babel_route *route = &routes[i]; if(route->time > babel_now.tv_sec || /* clock stepped */ route_old(route)) { @@ -744,7 +744,7 @@ babel_uninstall_all_routes(void) } } -struct route * +struct babel_route * babel_route_get_by_source(struct source *src) { int i; -- cgit v1.2.1 From 3dbda0ceebe369a1071600fe7d8d8ecf45f1027c Mon Sep 17 00:00:00 2001 From: Denis Ovsienko Date: Sun, 8 Jan 2012 16:52:36 +0400 Subject: babeld: address some compilation warnings Including system headers is not necessary with zebra.h included and sometimes results in "__ASSERT_FUNCTION redefined" compilation warning. * babeld.c * babel_distribute_update_interface(): make static * babel_interface.c * interface_config_write(): unused 'babel_ifp' * don't include system headers * message.c * send_request(): unused 'babel_ifp' * send_multihop_request(): idem * don't include system headers * route.c: don't include system headers * xroute.c: idem * source.h: newline at EOF * message.h: idem --- babeld/route.c | 7 ------- 1 file changed, 7 deletions(-) (limited to 'babeld/route.c') diff --git a/babeld/route.c b/babeld/route.c index a92018fd..aa181be7 100644 --- a/babeld/route.c +++ b/babeld/route.c @@ -37,13 +37,6 @@ OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. */ -#include -#include -#include -#include -#include -#include - #include #include "if.h" -- cgit v1.2.1 From 4eedea551290906fc76f3a0c908ae759e78bb68a Mon Sep 17 00:00:00 2001 From: Matthieu Boutier Date: Tue, 17 Jan 2012 22:46:21 +0100 Subject: babeld: change fprintf(stderr) in term of zlog_err. --- babeld/route.c | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-) (limited to 'babeld/route.c') diff --git a/babeld/route.c b/babeld/route.c index aa181be7..aadf80f2 100644 --- a/babeld/route.c +++ b/babeld/route.c @@ -172,8 +172,8 @@ install_route(struct babel_route *route) return; if(!route_feasible(route)) - fprintf(stderr, "WARNING: installing unfeasible route " - "(this shouldn't happen)."); + zlog_err("WARNING: installing unfeasible route " + "(this shouldn't happen)."); rc = kernel_route(ROUTE_ADD, route->src->prefix, route->src->plen, route->nexthop, @@ -224,8 +224,8 @@ switch_routes(struct babel_route *old, struct babel_route *new) return; if(!route_feasible(new)) - fprintf(stderr, "WARNING: switching to unfeasible route " - "(this shouldn't happen)."); + zlog_err("WARNING: switching to unfeasible route " + "(this shouldn't happen)."); rc = kernel_route(ROUTE_MODIFY, old->src->prefix, old->src->plen, old->nexthop, old->neigh->ifp->ifindex, @@ -414,8 +414,8 @@ update_route(const unsigned char *router_id, return NULL; /* I have announced the route */ if(martian_prefix(prefix, plen)) { - fprintf(stderr, "Rejecting martian route to %s through %s.\n", - format_prefix(prefix, plen), format_address(router_id)); + zlog_err("Rejecting martian route to %s through %s.", + format_prefix(prefix, plen), format_address(router_id)); return NULL; } -- cgit v1.2.1 From c35fafdf887aa32c5be6ad738d3a3b0140cea6e8 Mon Sep 17 00:00:00 2001 From: Matthieu Boutier Date: Mon, 23 Jan 2012 23:46:32 +0100 Subject: babeld: babelz merge. Babelz is the last version of the stand-alone babel daemon. In particular, it use multiple channels to diminuate interferences. Please refer to this one for more details. --- babeld/route.c | 574 ++++++++++++++++++++++++++++++++++++++++++--------------- 1 file changed, 422 insertions(+), 152 deletions(-) (limited to 'babeld/route.c') diff --git a/babeld/route.c b/babeld/route.c index aadf80f2..a9ffc5d9 100644 --- a/babeld/route.c +++ b/babeld/route.c @@ -53,36 +53,161 @@ THE SOFTWARE. static void consider_route(struct babel_route *route); -struct babel_route *routes = NULL; -int numroutes = 0, maxroutes = 0; +struct babel_route **routes = NULL; +static int route_slots = 0, max_route_slots = 0; int kernel_metric = 0; int allow_duplicates = -1; +int diversity_kind = DIVERSITY_NONE; +int diversity_factor = 256; /* in units of 1/256 */ +int keep_unfeasible = 0; + +/* We maintain a list of "slots", ordered by prefix. Every slot + contains a linked list of the routes to this prefix, with the + installed route, if any, at the head of the list. */ + +static int +route_compare(const unsigned char *prefix, unsigned char plen, + struct babel_route *route) +{ + int i = memcmp(prefix, route->src->prefix, 16); + if(i != 0) + return i; + + if(plen < route->src->plen) + return -1; + else if(plen > route->src->plen) + return 1; + else + return 0; +} + +/* Performs binary search, returns -1 in case of failure. In the latter + case, new_return is the place where to insert the new element. */ + +static int +find_route_slot(const unsigned char *prefix, unsigned char plen, + int *new_return) +{ + int p, m, g, c; + + if(route_slots < 1) { + if(new_return) + *new_return = 0; + return -1; + } + + p = 0; g = route_slots - 1; + + do { + m = (p + g) / 2; + c = route_compare(prefix, plen, routes[m]); + if(c == 0) + return m; + else if(c < 0) + g = m - 1; + else + p = m + 1; + } while(p <= g); + + if(new_return) + *new_return = p; + + return -1; +} struct babel_route * find_route(const unsigned char *prefix, unsigned char plen, struct neighbour *neigh, const unsigned char *nexthop) { - int i; - for(i = 0; i < numroutes; i++) { - if(routes[i].neigh == neigh && - memcmp(routes[i].nexthop, nexthop, 16) == 0 && - source_match(routes[i].src, prefix, plen)) - return &routes[i]; + struct babel_route *route; + int i = find_route_slot(prefix, plen, NULL); + + if(i < 0) + return NULL; + + route = routes[i]; + + while(route) { + if(route->neigh == neigh && memcmp(route->nexthop, nexthop, 16) == 0) + return route; + route = route->next; } + return NULL; } struct babel_route * find_installed_route(const unsigned char *prefix, unsigned char plen) { - int i; - for(i = 0; i < numroutes; i++) { - if(routes[i].installed && source_match(routes[i].src, prefix, plen)) - return &routes[i]; - } + int i = find_route_slot(prefix, plen, NULL); + + if(i >= 0 && routes[i]->installed) + return routes[i]; + return NULL; } +/* Returns an overestimate of the number of installed routes. */ +int +installed_routes_estimate(void) +{ + return route_slots; +} + +static int +resize_route_table(int new_slots) +{ + struct babel_route **new_routes; + assert(new_slots >= route_slots); + + if(new_slots == 0) { + new_routes = NULL; + free(routes); + } else { + new_routes = realloc(routes, new_slots * sizeof(struct babel_route*)); + if(new_routes == NULL) + return -1; + } + + max_route_slots = new_slots; + routes = new_routes; + return 1; +} + +/* Insert a route into the table. If successful, retains the route. + On failure, caller must free the route. */ +static struct babel_route * +insert_route(struct babel_route *route) +{ + int i, n; + + assert(!route->installed); + + i = find_route_slot(route->src->prefix, route->src->plen, &n); + + if(i < 0) { + if(route_slots >= max_route_slots) + resize_route_table(max_route_slots < 1 ? 8 : 2 * max_route_slots); + if(route_slots >= max_route_slots) + return NULL; + route->next = NULL; + if(n < route_slots) + memmove(routes + n + 1, routes + n, + (route_slots - n) * sizeof(struct babel_route*)); + route_slots++; + routes[n] = route; + } else { + struct babel_route *r; + r = routes[i]; + while(r->next) + r = r->next; + r->next = route; + route->next = NULL; + } + + return route; +} + void flush_route(struct babel_route *route) { @@ -91,39 +216,67 @@ flush_route(struct babel_route *route) unsigned oldmetric; int lost = 0; - i = route - routes; - assert(i >= 0 && i < numroutes); - oldmetric = route_metric(route); + src = route->src; if(route->installed) { uninstall_route(route); lost = 1; } - src = route->src; + i = find_route_slot(route->src->prefix, route->src->plen, NULL); + assert(i >= 0 && i < route_slots); - if(i != numroutes - 1) - memcpy(routes + i, routes + numroutes - 1, sizeof(struct babel_route)); - numroutes--; - VALGRIND_MAKE_MEM_UNDEFINED(routes + numroutes, sizeof(struct babel_route)); + if(route == routes[i]) { + routes[i] = route->next; + route->next = NULL; + free(route); - if(numroutes == 0) { - free(routes); - routes = NULL; - maxroutes = 0; - } else if(maxroutes > 8 && numroutes < maxroutes / 4) { - struct babel_route *new_routes; - int n = maxroutes / 2; - new_routes = realloc(routes, n * sizeof(struct babel_route)); - if(new_routes != NULL) { - routes = new_routes; - maxroutes = n; + if(routes[i] == NULL) { + if(i < route_slots - 1) + memmove(routes + i, routes + i + 1, + (route_slots - i - 1) * sizeof(struct babel_route*)); + routes[route_slots - 1] = NULL; + route_slots--; } + + if(route_slots == 0) + resize_route_table(0); + else if(max_route_slots > 8 && route_slots < max_route_slots / 4) + resize_route_table(max_route_slots / 2); + } else { + struct babel_route *r = routes[i]; + while(r->next != route) + r = r->next; + r->next = route->next; + route->next = NULL; + free(route); } if(lost) route_lost(src, oldmetric); + + release_source(src); +} + +void +flush_all_routes() +{ + int i; + + /* Start from the end, to avoid shifting the table. */ + i = route_slots - 1; + while(i >= 0) { + while(i < route_slots) { + /* Uninstall first, to avoid calling route_lost. */ + if(routes[i]->installed) + uninstall_route(routes[0]); + flush_route(routes[i]); + } + i--; + } + + check_sources_released(); } void @@ -132,12 +285,19 @@ flush_neighbour_routes(struct neighbour *neigh) int i; i = 0; - while(i < numroutes) { - if(routes[i].neigh == neigh) { - flush_route(&routes[i]); - continue; + while(i < route_slots) { + struct babel_route *r; + r = routes[i]; + while(r) { + if(r->neigh == neigh) { + flush_route(r); + goto again; + } + r = r->next; } i++; + again: + ; } } @@ -147,13 +307,46 @@ flush_interface_routes(struct interface *ifp, int v4only) int i; i = 0; - while(i < numroutes) { - if(routes[i].neigh->ifp == ifp && - (!v4only || v4mapped(routes[i].nexthop))) { - flush_route(&routes[i]); - continue; + while(i < route_slots) { + struct babel_route *r; + r = routes[i]; + while(r) { + if(r->neigh->ifp == ifp && + (!v4only || v4mapped(r->nexthop))) { + flush_route(r); + goto again; + } + r = r->next; } i++; + again: + ; + } +} + +/* Iterate a function over all routes. */ +void +for_all_routes(void (*f)(struct babel_route*, void*), void *closure) +{ + int i; + + for(i = 0; i < route_slots; i++) { + struct babel_route *r = routes[i]; + while(r) { + (*f)(r, closure); + r = r->next; + } + } +} + +void +for_all_installed_routes(void (*f)(struct babel_route*, void*), void *closure) +{ + int i; + + for(i = 0; i < route_slots; i++) { + if(routes[i]->installed) + (*f)(routes[i], closure); } } @@ -163,10 +356,28 @@ metric_to_kernel(int metric) return metric < INFINITY ? kernel_metric : KERNEL_INFINITY; } +/* This is used to maintain the invariant that the installed route is at + the head of the list. */ +static void +move_installed_route(struct babel_route *route, int i) +{ + assert(i >= 0 && i < route_slots); + assert(route->installed); + + if(route != routes[i]) { + struct babel_route *r = routes[i]; + while(r->next != route) + r = r->next; + r->next = route->next; + route->next = routes[i]; + routes[i] = route; + } +} + void install_route(struct babel_route *route) { - int rc; + int i, rc; if(route->installed) return; @@ -175,6 +386,15 @@ install_route(struct babel_route *route) zlog_err("WARNING: installing unfeasible route " "(this shouldn't happen)."); + i = find_route_slot(route->src->prefix, route->src->plen, NULL); + assert(i >= 0 && i < route_slots); + + if(routes[i] != route && routes[i]->installed) { + fprintf(stderr, "WARNING: attempting to install duplicate route " + "(this shouldn't happen)."); + return; + } + rc = kernel_route(ROUTE_ADD, route->src->prefix, route->src->plen, route->nexthop, route->neigh->ifp->ifindex, @@ -186,6 +406,8 @@ install_route(struct babel_route *route) return; } route->installed = 1; + move_installed_route(route, i); + } void @@ -239,15 +461,16 @@ switch_routes(struct babel_route *old, struct babel_route *new) old->installed = 0; new->installed = 1; + move_installed_route(new, find_route_slot(new->src->prefix, new->src->plen, + NULL)); } static void -change_route_metric(struct babel_route *route, unsigned newmetric) +change_route_metric(struct babel_route *route, + unsigned refmetric, unsigned cost, unsigned add) { int old, new; - - if(route_metric(route) == newmetric) - return; + int newmetric = MIN(refmetric + cost + add, INFINITY); old = metric_to_kernel(route_metric(route)); new = metric_to_kernel(newmetric); @@ -265,14 +488,15 @@ change_route_metric(struct babel_route *route, unsigned newmetric) } } - route->metric = newmetric; + route->refmetric = refmetric; + route->cost = cost; + route->add_metric = add; } static void retract_route(struct babel_route *route) { - route->refmetric = INFINITY; - change_route_metric(route, INFINITY); + change_route_metric(route, INFINITY, INFINITY, 0); } int @@ -293,6 +517,51 @@ route_expired(struct babel_route *route) return route->time < babel_now.tv_sec - route->hold_time; } +static int +channels_interfere(int ch1, int ch2) +{ + if(ch1 == BABEL_IF_CHANNEL_NONINTERFERING + || ch2 == BABEL_IF_CHANNEL_NONINTERFERING) + return 0; + if(ch1 == BABEL_IF_CHANNEL_INTERFERING + || ch2 == BABEL_IF_CHANNEL_INTERFERING) + return 1; + return ch1 == ch2; +} + +int +route_interferes(struct babel_route *route, struct interface *ifp) +{ + struct babel_interface *babel_ifp = NULL; + switch(diversity_kind) { + case DIVERSITY_NONE: + return 1; + case DIVERSITY_INTERFACE_1: + return route->neigh->ifp == ifp; + case DIVERSITY_CHANNEL_1: + case DIVERSITY_CHANNEL: + if(route->neigh->ifp == ifp) + return 1; + babel_ifp = babel_get_if_nfo(ifp); + if(channels_interfere(babel_ifp->channel, + babel_get_if_nfo(route->neigh->ifp)->channel)) + return 1; + if(diversity_kind == DIVERSITY_CHANNEL) { + int i; + for(i = 0; i < DIVERSITY_HOPS; i++) { + if(route->channels[i] == 0) + break; + if(channels_interfere(babel_ifp->channel, route->channels[i])) + return 1; + } + } + return 0; + default: + fprintf(stderr, "Unknown kind of diversity.\n"); + return 1; + } +} + int update_feasible(struct source *src, unsigned short seqno, unsigned short refmetric) @@ -317,21 +586,22 @@ struct babel_route * find_best_route(const unsigned char *prefix, unsigned char plen, int feasible, struct neighbour *exclude) { - struct babel_route *route = NULL; - int i; + struct babel_route *route = NULL, *r = NULL; + int i = find_route_slot(prefix, plen, NULL); + + if(i < 0) + return NULL; + + route = routes[i]; - for(i = 0; i < numroutes; i++) { - if(!source_match(routes[i].src, prefix, plen)) - continue; - if(route_expired(&routes[i])) - continue; - if(feasible && !route_feasible(&routes[i])) - continue; - if(exclude && routes[i].neigh == exclude) - continue; - if(route && route_metric(route) <= route_metric(&routes[i])) - continue; - route = &routes[i]; + r = route->next; + while(r) { + if(!route_expired(r) && + (!feasible || route_feasible(r)) && + (!exclude || r->neigh != exclude) && + (route_metric(r) < route_metric(route))) + route = r; + r = r->next; } return route; } @@ -354,31 +624,29 @@ update_route_metric(struct babel_route *route) route->src->prefix, route->src->plen, neigh->address, neigh->ifp->ifindex); - int newmetric = MIN(route->refmetric + - add_metric + - neighbour_cost(route->neigh), - INFINITY); - - if(newmetric != oldmetric) { - change_route_metric(route, newmetric); + change_route_metric(route, route->refmetric, + neighbour_cost(route->neigh), add_metric); + if(route_metric(route) != oldmetric) route_changed(route, route->src, oldmetric); - } } } /* Called whenever a neighbour's cost changes, to update the metric of - all routes through that neighbour. */ + all routes through that neighbour. Calls local_notify_neighbour. */ void update_neighbour_metric(struct neighbour *neigh, int changed) { + if(changed) { int i; - i = 0; - while(i < numroutes) { - if(routes[i].neigh == neigh) - update_route_metric(&routes[i]); - i++; + for(i = 0; i < route_slots; i++) { + struct babel_route *r = routes[i]; + while(r) { + if(r->neigh == neigh) + update_route_metric(r); + r = r->next; + } } } } @@ -388,11 +656,13 @@ update_interface_metric(struct interface *ifp) { int i; - i = 0; - while(i < numroutes) { - if(routes[i].neigh->ifp == ifp) - update_route_metric(&routes[i]); - i++; + for(i = 0; i < route_slots; i++) { + struct babel_route *r = routes[i]; + while(r) { + if(r->neigh->ifp == ifp) + update_route_metric(r); + r = r->next; + } } } @@ -402,7 +672,8 @@ update_route(const unsigned char *router_id, const unsigned char *prefix, unsigned char plen, unsigned short seqno, unsigned short refmetric, unsigned short interval, - struct neighbour *neigh, const unsigned char *nexthop) + struct neighbour *neigh, const unsigned char *nexthop, + const unsigned char *channels, int channels_len) { struct babel_route *route; struct source *src; @@ -424,12 +695,18 @@ update_route(const unsigned char *router_id, if(add_metric >= INFINITY) return NULL; - src = find_source(router_id, prefix, plen, 1, seqno); + route = find_route(prefix, plen, neigh, nexthop); + + if(route && memcmp(route->src->id, router_id, 8) == 0) + /* Avoid scanning the source table. */ + src = route->src; + else + src = find_source(router_id, prefix, plen, 1, seqno); + if(src == NULL) return NULL; feasible = update_feasible(src, seqno, refmetric); - route = find_route(prefix, plen, neigh, nexthop); metric = MIN((int)refmetric + neighbour_cost(neigh) + add_metric, INFINITY); if(route) { @@ -457,12 +734,12 @@ update_route(const unsigned char *router_id, } } - route->src = src; - if(feasible && refmetric < INFINITY) + route->src = retain_source(src); + if((feasible || keep_unfeasible) && refmetric < INFINITY) route->time = babel_now.tv_sec; route->seqno = seqno; - route->refmetric = refmetric; - change_route_metric(route, metric); + change_route_metric(route, + refmetric, neighbour_cost(neigh), add_metric); route->hold_time = hold_time; route_changed(route, oldsrc, oldmetric); @@ -472,36 +749,46 @@ update_route(const unsigned char *router_id, if(!feasible) send_unfeasible_request(neigh, route->installed && route_old(route), seqno, metric, src); + release_source(oldsrc); } else { + struct babel_route *new_route; + if(refmetric >= INFINITY) /* Somebody's retracting a route we never saw. */ return NULL; if(!feasible) { send_unfeasible_request(neigh, 0, seqno, metric, src); - return NULL; - } - if(numroutes >= maxroutes) { - struct babel_route *new_routes; - int n = maxroutes < 1 ? 8 : 2 * maxroutes; - new_routes = routes == NULL ? - malloc(n * sizeof(struct babel_route)) : - realloc(routes, n * sizeof(struct babel_route)); - if(new_routes == NULL) + if(!keep_unfeasible) return NULL; - maxroutes = n; - routes = new_routes; } - route = &routes[numroutes]; - route->src = src; + + route = malloc(sizeof(struct babel_route)); + if(route == NULL) { + perror("malloc(route)"); + return NULL; + } + + route->src = retain_source(src); route->refmetric = refmetric; + route->cost = neighbour_cost(neigh); + route->add_metric = add_metric; route->seqno = seqno; - route->metric = metric; route->neigh = neigh; memcpy(route->nexthop, nexthop, 16); route->time = babel_now.tv_sec; route->hold_time = hold_time; route->installed = 0; - numroutes++; + memset(&route->channels, 0, sizeof(route->channels)); + if(channels_len > 0) + memcpy(&route->channels, channels, + MIN(channels_len, DIVERSITY_HOPS)); + route->next = NULL; + new_route = insert_route(route); + if(new_route == NULL) { + fprintf(stderr, "Couldn't insert route.\n"); + free(route); + return NULL; + } consider_route(route); } return route; @@ -558,13 +845,6 @@ consider_route(struct babel_route *route) if(route_metric(installed) >= INFINITY) goto install; - if(route_metric(installed) >= route_metric(route) + 192) - goto install; - - /* Avoid switching sources */ - if(installed->src != route->src) - return; - if(route_metric(installed) >= route_metric(route) + 64) goto install; @@ -584,15 +864,18 @@ retract_neighbour_routes(struct neighbour *neigh) { int i; - i = 0; - while(i < numroutes) { - if(routes[i].neigh == neigh) { - if(routes[i].refmetric != INFINITY) { - unsigned short oldmetric = route_metric(&routes[i]); - retract_route(&routes[i]); + for(i = 0; i < route_slots; i++) { + struct babel_route *r = routes[i]; + while(r) { + if(r->neigh == neigh) { + if(r->refmetric != INFINITY) { + unsigned short oldmetric = route_metric(r); + retract_route(r); if(oldmetric != INFINITY) - route_changed(&routes[i], routes[i].src, oldmetric); + route_changed(r, r->src, oldmetric); + } } + r = r->next; } i++; } @@ -699,51 +982,38 @@ route_lost(struct source *src, unsigned oldmetric) } } +/* This is called periodically to flush old routes. It will also send + requests for routes that are about to expire. */ void expire_routes(void) { + struct babel_route *r; int i; debugf(BABEL_DEBUG_COMMON,"Expiring old routes."); i = 0; - while(i < numroutes) { - struct babel_route *route = &routes[i]; - - if(route->time > babel_now.tv_sec || /* clock stepped */ - route_old(route)) { - flush_route(route); - continue; - } + while(i < route_slots) { + r = routes[i]; + while(r) { + /* Protect against clock being stepped. */ + if(r->time > babel_now.tv_sec || route_old(r)) { + flush_route(r); + goto again; + } - update_route_metric(route); + update_route_metric(r); - if(route->installed && route->refmetric < INFINITY) { - if(route_old(route)) - send_unicast_request(route->neigh, - route->src->prefix, route->src->plen); + if(r->installed && r->refmetric < INFINITY) { + if(route_old(r)) + /* Route about to expire, send a request. */ + send_unicast_request(r->neigh, + r->src->prefix, r->src->plen); + } + r = r->next; } i++; + again: + ; } } - -void -babel_uninstall_all_routes(void) -{ - while(numroutes > 0) { - uninstall_route(&routes[0]); - /* We need to flush the route so network_up won't reinstall it */ - flush_route(&routes[0]); - } -} - -struct babel_route * -babel_route_get_by_source(struct source *src) -{ - int i; - for(i = 0; i < numroutes; i++) { - if(routes[i].src == src) - return &routes[i]; - } - return NULL; -} -- cgit v1.2.1 From 52d54422bdc0b70356d84a38a0ce15ba5dea03e0 Mon Sep 17 00:00:00 2001 From: Juliusz Chroboczek Date: Sat, 11 Feb 2012 13:08:00 +0100 Subject: Resynchronise with babeld-1.3.1. --- babeld/route.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'babeld/route.c') diff --git a/babeld/route.c b/babeld/route.c index a9ffc5d9..fe2b9ceb 100644 --- a/babeld/route.c +++ b/babeld/route.c @@ -682,7 +682,7 @@ update_route(const unsigned char *router_id, int hold_time = MAX((4 * interval) / 100 + interval / 50, 15); if(memcmp(router_id, myid, 8) == 0) - return NULL; /* I have announced the route */ + return NULL; if(martian_prefix(prefix, plen)) { zlog_err("Rejecting martian route to %s through %s.", -- cgit v1.2.1