-/*
- * 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 <http://www.gnu.org/licenses/>.
- *
- * 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
#include "xroute.h"
#include "message.h"
#include "resend.h"
+#include "babel_errors.h"
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;
+enum babel_diversity diversity_kind = DIVERSITY_NONE;
+int diversity_factor = BABEL_DEFAULT_DIVERSITY_FACTOR;
+int keep_unfeasible = 0;
+
+int smoothing_half_life = 0;
+static int two_to_the_one_over_hl = 0; /* 2^(1/hl) * 0x10000 */
+
+/* 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;
+ assert(routes);
+ 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)
{
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[i]);
+ flush_route(routes[i]);
+ }
+ i--;
+ }
+
+ check_sources_released();
}
void
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:
+ ;
}
}
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:
+ ;
}
}
+struct route_stream {
+ int installed;
+ int index;
+ struct babel_route *next;
+};
+
+
+struct route_stream *
+route_stream(int installed)
+{
+ struct route_stream *stream;
+
+ stream = malloc(sizeof(struct route_stream));
+ if(stream == NULL)
+ return NULL;
+
+ stream->installed = installed;
+ stream->index = installed ? 0 : -1;
+ stream->next = NULL;
+
+ return stream;
+}
+
+struct babel_route *
+route_stream_next(struct route_stream *stream)
+{
+ if(stream->installed) {
+ while(stream->index < route_slots && !routes[stream->index]->installed)
+ stream->index++;
+
+ if(stream->index < route_slots)
+ return routes[stream->index++];
+ else
+ return NULL;
+ } else {
+ struct babel_route *next;
+ if(!stream->next) {
+ stream->index++;
+ if(stream->index >= route_slots)
+ return NULL;
+ stream->next = routes[stream->index];
+ }
+ next = stream->next;
+ stream->next = next->next;
+ return next;
+ }
+}
+
+void
+route_stream_done(struct route_stream *stream)
+{
+ free(stream);
+}
+
static int
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;
if(!route_feasible(route))
- zlog_err("WARNING: installing unfeasible route "
- "(this shouldn't happen).");
+ flog_err(EC_BABEL_ROUTE, "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) {
+ flog_err(EC_BABEL_ROUTE,
+ "WARNING: attempting to install duplicate route "
+ "(this shouldn't happen).");
+ return;
+ }
rc = kernel_route(ROUTE_ADD, route->src->prefix, route->src->plen,
route->nexthop,
metric_to_kernel(route_metric(route)), NULL, 0, 0);
if(rc < 0) {
int save = errno;
- zlog_err("kernel_route(ADD): %s", safe_strerror(errno));
+ flog_err(EC_BABEL_ROUTE, "kernel_route(ADD): %s",
+ safe_strerror(errno));
if(save != EEXIST)
return;
}
route->installed = 1;
+ move_installed_route(route, i);
+
}
void
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));
+ flog_err(EC_BABEL_ROUTE, "kernel_route(FLUSH): %s",
+ safe_strerror(errno));
route->installed = 0;
}
return;
if(!route_feasible(new))
- zlog_err("WARNING: switching to unfeasible route "
- "(this shouldn't happen).");
+ flog_err(EC_BABEL_ROUTE, "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,
new->nexthop, new->neigh->ifp->ifindex,
metric_to_kernel(route_metric(new)));
if(rc < 0) {
- zlog_err("kernel_route(MODIFY): %s", safe_strerror(errno));
+ flog_err(EC_BABEL_ROUTE, "kernel_route(MODIFY): %s",
+ safe_strerror(errno));
return;
}
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);
route->nexthop, route->neigh->ifp->ifindex,
new);
if(rc < 0) {
- zlog_err("kernel_route(MODIFY metric): %s", safe_strerror(errno));
+ flog_err(EC_BABEL_ROUTE, "kernel_route(MODIFY metric): %s",
+ safe_strerror(errno));
return;
}
}
- route->metric = newmetric;
+ /* Update route->smoothed_metric using the old metric. */
+ route_smoothed_metric(route);
+
+ route->refmetric = refmetric;
+ route->cost = cost;
+ route->add_metric = add;
+
+ if(smoothing_half_life == 0) {
+ route->smoothed_metric = route_metric(route);
+ route->smoothed_metric_time = babel_now.tv_sec;
+ }
}
static void
retract_route(struct babel_route *route)
{
- route->refmetric = INFINITY;
- change_route_metric(route, INFINITY);
+ /* We cannot simply remove the route from the kernel, as that might
+ cause a routing loop -- see RFC 6126 Sections 2.8 and 3.5.5. */
+ change_route_metric(route, INFINITY, INFINITY, 0);
}
int
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;
+ }
+
+ return 1;
+}
+
int
update_feasible(struct source *src,
unsigned short seqno, unsigned short refmetric)
(src->seqno == seqno && refmetric < src->metric));
}
-/* This returns the feasible route with the smallest metric. */
+void
+change_smoothing_half_life(int half_life)
+{
+ if(half_life <= 0) {
+ smoothing_half_life = 0;
+ two_to_the_one_over_hl = 0;
+ return;
+ }
+
+ smoothing_half_life = half_life;
+ switch(smoothing_half_life) {
+ case 1: two_to_the_one_over_hl = 131072; break;
+ case 2: two_to_the_one_over_hl = 92682; break;
+ case 3: two_to_the_one_over_hl = 82570; break;
+ case 4: two_to_the_one_over_hl = 77935; break;
+ default:
+ /* 2^(1/x) is 1 + log(2)/x + O(1/x^2) at infinity. */
+ two_to_the_one_over_hl = 0x10000 + 45426 / half_life;
+ }
+}
+
+/* Update the smoothed metric, return the new value. */
+int
+route_smoothed_metric(struct babel_route *route)
+{
+ int metric = route_metric(route);
+
+ if(smoothing_half_life <= 0 || /* no smoothing */
+ metric >= INFINITY || /* route retracted */
+ route->smoothed_metric_time > babel_now.tv_sec || /* clock stepped */
+ route->smoothed_metric == metric) { /* already converged */
+ route->smoothed_metric = metric;
+ route->smoothed_metric_time = babel_now.tv_sec;
+ } else {
+ int diff;
+ /* We randomise the computation, to minimise global synchronisation
+ and hence oscillations. */
+ while(route->smoothed_metric_time <=
+ babel_now.tv_sec - smoothing_half_life) {
+ diff = metric - route->smoothed_metric;
+ route->smoothed_metric += roughly(diff) / 2;
+ route->smoothed_metric_time += smoothing_half_life;
+ }
+ while(route->smoothed_metric_time < babel_now.tv_sec) {
+ diff = metric - route->smoothed_metric;
+ route->smoothed_metric +=
+ roughly(diff) * (two_to_the_one_over_hl - 0x10000) / 0x10000;
+ route->smoothed_metric_time++;
+ }
+
+ diff = metric - route->smoothed_metric;
+ if(diff > -4 && diff < 4)
+ route->smoothed_metric = metric;
+ }
+
+ /* change_route_metric relies on this */
+ assert(route->smoothed_metric_time == babel_now.tv_sec);
+ return route->smoothed_metric;
+}
+
+static int
+route_acceptable(struct babel_route *route, int feasible,
+ struct neighbour *exclude)
+{
+ if(route_expired(route))
+ return 0;
+ if(feasible && !route_feasible(route))
+ return 0;
+ if(exclude && route->neigh == exclude)
+ return 0;
+ return 1;
+}
+
+/* Find the best route according to the weak ordering. Any
+ linearisation of the strong ordering (see consider_route) will do,
+ we use sm <= sm'. We could probably use a lexical ordering, but
+ that's probably overkill. */
+
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);
- 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];
+ if(i < 0)
+ return NULL;
+
+ route = routes[i];
+ while(route && !route_acceptable(route, feasible, exclude))
+ route = route->next;
+
+ if(!route)
+ return NULL;
+
+ r = route->next;
+ while(r) {
+ if(route_acceptable(r, feasible, exclude) &&
+ (route_smoothed_metric(r) < route_smoothed_metric(route)))
+ route = r;
+ r = r->next;
}
+
return route;
}
update_route_metric(struct babel_route *route)
{
int oldmetric = route_metric(route);
+ int old_smoothed_metric = route_smoothed_metric(route);
if(route_expired(route)) {
if(route->refmetric < INFINITY) {
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_smoothed_metric(route) != old_smoothed_metric)
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. */
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;
+ }
}
}
}
{
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;
+ }
}
}
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;
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.",
- format_prefix(prefix, plen), format_address(router_id));
+ flog_err(EC_BABEL_ROUTE, "Rejecting martian route to %s through %s.",
+ format_prefix(prefix, plen), format_address(nexthop));
return NULL;
}
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) {
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),
+ format_eui64(route->src->id),
route->seqno, route->refmetric,
- format_address(src->id), seqno, refmetric);
+ format_eui64(src->id), seqno, refmetric);
if(src != route->src) {
uninstall_route(route);
lost = 1;
}
}
- 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);
+
+ memset(&route->channels, 0, sizeof(route->channels));
+ if(channels_len > 0)
+ memcpy(&route->channels, channels,
+ MIN(channels_len, DIVERSITY_HOPS));
+
+ change_route_metric(route,
+ refmetric, neighbour_cost(neigh), add_metric);
route->hold_time = hold_time;
route_changed(route, oldsrc, oldmetric);
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->smoothed_metric = MAX(route_metric(route), INFINITY / 2);
+ route->smoothed_metric_time = babel_now.tv_sec;
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) {
+ flog_err(EC_BABEL_ROUTE, "Couldn't insert route.");
+ free(route);
+ return NULL;
+ }
consider_route(route);
}
return route;
}
}
-/* This takes a feasible route and decides whether to install it. */
+/* This takes a feasible route and decides whether to install it.
+ This uses the strong ordering, which is defined by sm <= sm' AND
+ m <= m'. This ordering is not total, which is what causes
+ hysteresis. */
+
static void
consider_route(struct babel_route *route)
{
return;
xroute = find_xroute(route->src->prefix, route->src->plen);
- if(xroute && (allow_duplicates < 0 || xroute->metric >= allow_duplicates))
+ if(xroute)
return;
installed = find_installed_route(route->src->prefix, route->src->plen);
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)
+ if(route_metric(installed) >= route_metric(route) &&
+ route_smoothed_metric(installed) > route_smoothed_metric(route))
goto install;
return;
{
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++;
}
}
struct source *oldsrc, unsigned short oldmetric)
{
if(route->installed) {
- if(route_metric(route) > oldmetric) {
- struct babel_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);
- }
+ struct babel_route *better_route;
+ /* Do this unconditionally -- microoptimisation is not worth it. */
+ better_route =
+ find_best_route(route->src->prefix, route->src->plen, 1, NULL);
+ if(better_route && route_metric(better_route) < route_metric(route))
+ consider_route(better_route);
+ }
- if(route->installed)
- /* We didn't change routes after all. */
- send_triggered_update(route, oldsrc, oldmetric);
+ 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. */
if(new_route) {
consider_route(new_route);
} else if(oldmetric < INFINITY) {
- /* Complain loudly. */
+ /* Avoid creating a blackhole. */
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);
+ /* If the route was usable enough, try to get an alternate one.
+ If it was not, we could be dealing with oscillations around
+ the value of INFINITY. */
+ if(oldmetric <= INFINITY / 2)
+ send_request_resend(NULL, src->prefix, src->plen,
+ src->metric >= INFINITY ?
+ src->seqno : seqno_plus(src->seqno, 1),
+ src->id);
}
}
+/* 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;
-}
projects / mirror_frr.git / blobdiff