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.
diff --git a/babeld/route.c b/babeld/route.c
index aadf80f..a9ffc5d 100644
--- a/babeld/route.c
+++ b/babeld/route.c
@@ -53,36 +53,161 @@
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 @@
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 @@
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 @@
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 @@
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 @@
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 @@
return;
}
route->installed = 1;
+ move_installed_route(route, i);
+
}
void
@@ -239,15 +461,16 @@
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 @@
}
}
- 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 @@
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 @@
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];
+
+ 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 @@
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 @@
{
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 @@
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 @@
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 @@
}
}
- 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 @@
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);
+ if(!keep_unfeasible)
+ return NULL;
+ }
+
+ route = malloc(sizeof(struct babel_route));
+ if(route == NULL) {
+ perror("malloc(route)");
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)
- return NULL;
- maxroutes = n;
- routes = new_routes;
- }
- route = &routes[numroutes];
- route->src = src;
+
+ 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 @@
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 @@
{
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 @@
}
}
+/* 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];
+ 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;
+ }
- if(route->time > babel_now.tv_sec || /* clock stepped */
- route_old(route)) {
- flush_route(route);
- continue;
- }
+ update_route_metric(r);
- 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);
+ 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;
-}