summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--babeld/babel_interface.c72
-rw-r--r--babeld/babel_interface.h19
-rw-r--r--babeld/babel_main.c2
-rw-r--r--babeld/babeld.c2
-rw-r--r--babeld/message.c202
-rw-r--r--babeld/neighbour.c5
-rw-r--r--babeld/net.c10
-rw-r--r--babeld/route.c574
-rw-r--r--babeld/route.h50
-rw-r--r--babeld/source.c59
-rw-r--r--babeld/source.h7
-rw-r--r--babeld/util.c68
-rw-r--r--babeld/util.h4
-rw-r--r--babeld/xroute.c27
-rw-r--r--babeld/xroute.h8
15 files changed, 792 insertions, 317 deletions
diff --git a/babeld/babel_interface.c b/babeld/babel_interface.c
index e403cce0..1c8c8868 100644
--- a/babeld/babel_interface.c
+++ b/babeld/babel_interface.c
@@ -456,6 +456,30 @@ interface_idle(babel_interface_nfo *babel_ifp)
babel_ifp->activity_time < babel_now.tv_sec - idle_time);
}
+int
+update_hello_interval(struct interface *ifp)
+{
+ int rc = 0;
+ unsigned short interval;
+ struct babel_interface *babel_ifp = babel_get_if_nfo(ifp);
+
+ if(interface_idle(babel_ifp))
+ interval = idle_hello_interval;
+ else if(IF_CONF(ifp, hello_interval) > 0)
+ interval = IF_CONF(ifp, hello_interval);
+ else if((ifp->flags & BABEL_IF_WIRED))
+ interval = wired_hello_interval;
+ else
+ interval = wireless_hello_interval;
+
+ if(babel_ifp->hello_interval != interval) {
+ babel_ifp->hello_interval = interval;
+ rc = 1;
+ }
+
+ return rc;
+}
+
/* This should be no more than half the hello interval, so that hellos
aren't sent late. The result is in milliseconds. */
unsigned
@@ -560,10 +584,11 @@ interface_recalculate(struct interface *ifp)
update_interface_metric(ifp);
debugf(BABEL_DEBUG_COMMON,
- "Upped network %s (%s, cost=%d%s).",
+ "Upped interface %s (%s, cost=%d, channel=%d%s).",
ifp->name,
(babel_ifp->flags & BABEL_IF_WIRED) ? "wired" : "wireless",
babel_ifp->cost,
+ babel_ifp->channel,
babel_ifp->ipv4 ? ", IPv4" : "");
if(rc > 0)
@@ -777,19 +802,41 @@ DEFUN (show_babel_neighbour,
}
static void
-show_babel_routes_sub (struct vty *vty, struct babel_route *route)
+show_babel_routes_sub (struct babel_route *route, void *closure)
{
+ struct vty *vty = (struct vty*) closure;
const unsigned char *nexthop =
memcmp(route->nexthop, route->neigh->address, 16) == 0 ?
NULL : route->nexthop;
+ char channels[100];
+
+ if(route->channels[0] == 0)
+ channels[0] = '\0';
+ else {
+ int k, j = 0;
+ snprintf(channels, 100, " chan (");
+ j = strlen(channels);
+ for(k = 0; k < DIVERSITY_HOPS; k++) {
+ if(route->channels[k] == 0)
+ break;
+ if(k > 0)
+ channels[j++] = ',';
+ snprintf(channels + j, 100 - j, "%d", route->channels[k]);
+ j = strlen(channels);
+ }
+ snprintf(channels + j, 100 - j, ")");
+ if(k == 0)
+ channels[0] = '\0';
+ }
vty_out(vty,
- "%s metric %d refmetric %d id %s seqno %d age %d "
+ "%s metric %d refmetric %d id %s seqno %d%s age %d "
"via %s neigh %s%s%s%s%s",
format_prefix(route->src->prefix, route->src->plen),
route_metric(route), route->refmetric,
format_eui64(route->src->id),
(int)route->seqno,
+ channels,
(int)(babel_now.tv_sec - route->time),
route->neigh->ifp->name,
format_address(route->neigh->address),
@@ -801,11 +848,12 @@ show_babel_routes_sub (struct vty *vty, struct babel_route *route)
}
static void
-show_babel_xroutes_sub (struct vty *vty, struct xroute *xroute)
+show_babel_xroutes_sub (struct xroute *xroute, void *closure)
{
+ struct vty *vty = (struct vty *) closure;
vty_out(vty, "%s metric %d (exported)%s",
- format_prefix(xroutes->prefix, xroute->plen),
- xroutes->metric,
+ format_prefix(xroute->prefix, xroute->plen),
+ xroute->metric,
VTY_NEWLINE);
}
@@ -818,15 +866,8 @@ DEFUN (show_babel_database,
"Database information\n"
"No attributes\n")
{
- int i;
-
- for(i = 0; i < numroutes; i++) {
- show_babel_routes_sub(vty, &routes[i]);
- }
- for(i = 0; i < numxroutes; i++) {
- show_babel_xroutes_sub(vty, &xroutes[i]);
- }
-
+ for_all_routes(show_babel_routes_sub, vty);
+ for_all_xroutes(show_babel_xroutes_sub, vty);
return CMD_SUCCESS;
}
@@ -950,6 +991,7 @@ babel_interface_allocate (void)
babel_ifp->bucket = BUCKET_TOKENS_MAX;
babel_ifp->hello_seqno = (random() & 0xFFFF);
babel_ifp->hello_interval = BABELD_DEFAULT_HELLO_INTERVAL;
+ babel_ifp->channel = BABEL_IF_CHANNEL_INTERFERING;
return babel_ifp;
}
diff --git a/babeld/babel_interface.h b/babeld/babel_interface.h
index d9fb9a4a..5b551fbe 100644
--- a/babeld/babel_interface.h
+++ b/babeld/babel_interface.h
@@ -42,10 +42,15 @@ THE SOFTWARE.
#include <zebra.h>
#include "zclient.h"
+#define CONFIG_DEFAULT 0
+#define CONFIG_NO 1
+#define CONFIG_YES 2
+
/* babeld interface informations */
struct babel_interface {
unsigned short flags; /* see below */
unsigned short cost;
+ int channel;
struct timeval hello_timeout;
struct timeval update_timeout;
struct timeval flush_timeout;
@@ -67,6 +72,7 @@ struct babel_interface {
time_t bucket_time;
unsigned int bucket;
time_t activity_time;
+ time_t last_update_time;
unsigned short hello_seqno;
unsigned hello_interval;
unsigned update_interval;
@@ -85,12 +91,20 @@ static inline babel_interface_nfo* babel_get_if_nfo(struct interface *ifp)
return ((babel_interface_nfo*) ifp->info);
}
+#define IF_CONF(_ifp, _field) babel_get_if_nfo(_ifp)->_field
+
/* babel_interface_nfo flags */
+#define BABEL_IF_IS_UP (1 << 0)
#define BABEL_IF_WIRED (1 << 1)
#define BABEL_IF_SPLIT_HORIZON (1 << 2)
#define BABEL_IF_LQ (1 << 3)
-#define BABEL_IF_IS_ENABLE (1 << 4)
-#define BABEL_IF_IS_UP (1 << 5)
+#define BABEL_IF_FARAWAY (1 << 4)
+#define BABEL_IF_IS_ENABLE (1 << 7)
+
+/* Only INTERFERING can appear on the wire. */
+#define BABEL_IF_CHANNEL_UNKNOWN 0
+#define BABEL_IF_CHANNEL_INTERFERING 255
+#define BABEL_IF_CHANNEL_NONINTERFERING -2
static inline int
if_up(struct interface *ifp)
@@ -133,6 +147,7 @@ int babel_interface_address_delete (int, struct zclient *, zebra_size_t);
/* others functions */
int interface_idle(babel_interface_nfo *);
+int update_hello_interval(struct interface *ifp);
unsigned jitter(babel_interface_nfo *, int);
unsigned update_jitter(babel_interface_nfo *babel_ifp, int urgent);
/* return "true" if "address" is one of our ipv6 addresses */
diff --git a/babeld/babel_main.c b/babeld/babel_main.c
index 159ba656..4d6f60eb 100644
--- a/babeld/babel_main.c
+++ b/babeld/babel_main.c
@@ -482,7 +482,7 @@ babel_exit_properly(void)
/* Uninstall and flush all routes. */
debugf(BABEL_DEBUG_COMMON, "Uninstall routes.");
- babel_uninstall_all_routes();
+ flush_all_routes();
babel_interface_close_all();
babel_zebra_close_connexion();
babel_save_state_file();
diff --git a/babeld/babeld.c b/babeld/babeld.c
index 0cf8c8a1..d69662c0 100644
--- a/babeld/babeld.c
+++ b/babeld/babeld.c
@@ -269,7 +269,7 @@ babel_initial_noise(void)
static void
babel_clean_routing_process()
{
- babel_uninstall_all_routes();
+ flush_all_routes();
babel_interface_close_all();
/* cancel threads */
diff --git a/babeld/message.c b/babeld/message.c
index 92c416b9..8cd1db63 100644
--- a/babeld/message.c
+++ b/babeld/message.c
@@ -69,6 +69,8 @@ struct timeval unicast_flush_timeout = {0, 0};
static const unsigned char v4prefix[16] =
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0xFF, 0xFF, 0, 0, 0, 0 };
+/* Parse a network prefix, encoded in the somewhat baroque compressed
+ representation used by Babel. Return the number of bytes parsed. */
static int
network_prefix(int ae, int plen, unsigned int omitted,
const unsigned char *p, const unsigned char *dp,
@@ -76,6 +78,7 @@ network_prefix(int ae, int plen, unsigned int omitted,
{
unsigned pb;
unsigned char prefix[16];
+ int ret = -1;
if(plen >= 0)
pb = (plen + 7) / 8;
@@ -90,7 +93,9 @@ network_prefix(int ae, int plen, unsigned int omitted,
memset(prefix, 0, 16);
switch(ae) {
- case 0: break;
+ case 0:
+ ret = 0;
+ break;
case 1:
if(omitted > 4 || pb > 4 || (pb > omitted && len < pb - omitted))
return -1;
@@ -100,6 +105,7 @@ network_prefix(int ae, int plen, unsigned int omitted,
memcpy(prefix, dp, 12 + omitted);
}
if(pb > omitted) memcpy(prefix + 12 + omitted, p, pb - omitted);
+ ret = pb - omitted;
break;
case 2:
if(omitted > 16 || (pb > omitted && len < pb - omitted)) return -1;
@@ -108,19 +114,68 @@ network_prefix(int ae, int plen, unsigned int omitted,
memcpy(prefix, dp, omitted);
}
if(pb > omitted) memcpy(prefix + omitted, p, pb - omitted);
+ ret = pb - omitted;
break;
case 3:
if(pb > 8 && len < pb - 8) return -1;
prefix[0] = 0xfe;
prefix[1] = 0x80;
if(pb > 8) memcpy(prefix + 8, p, pb - 8);
+ ret = pb - 8;
break;
default:
return -1;
}
mask_prefix(p_r, prefix, plen < 0 ? 128 : ae == 1 ? plen + 96 : plen);
- return 1;
+ return ret;
+}
+
+static void
+parse_route_attributes(const unsigned char *a, int alen,
+ unsigned char *channels)
+{
+ int type, len, i = 0;
+
+ while(i < alen) {
+ type = a[i];
+ if(type == 0) {
+ i++;
+ continue;
+ }
+
+ if(i + 1 > alen) {
+ fprintf(stderr, "Received truncated attributes.\n");
+ return;
+ }
+ len = a[i + 1];
+ if(i + len > alen) {
+ fprintf(stderr, "Received truncated attributes.\n");
+ return;
+ }
+
+ if(type == 1) {
+ /* Nothing. */
+ } else if(type == 2) {
+ if(len > DIVERSITY_HOPS) {
+ fprintf(stderr,
+ "Received overlong channel information (%d > %d).\n",
+ len, DIVERSITY_HOPS);
+ len = DIVERSITY_HOPS;
+ }
+ if(memchr(a + i + 2, 0, len) != NULL) {
+ /* 0 is reserved. */
+ fprintf(stderr, "Channel information contains 0!");
+ return;
+ }
+ memset(channels, 0, DIVERSITY_HOPS);
+ memcpy(channels, a + i + 2, len);
+ } else {
+ fprintf(stderr, "Received unknown route attribute %d.\n", type);
+ }
+
+ i += len + 2;
+ }
}
static int
@@ -130,6 +185,13 @@ network_address(int ae, const unsigned char *a, unsigned int len,
return network_prefix(ae, -1, 0, a, NULL, len, a_r);
}
+static int
+channels_len(unsigned char *channels)
+{
+ unsigned char *p = memchr(channels, 0, DIVERSITY_HOPS);
+ return p ? (p - channels) : DIVERSITY_HOPS;
+}
+
void
parse_packet(const unsigned char *from, struct interface *ifp,
const unsigned char *packet, int packetlen)
@@ -284,8 +346,9 @@ parse_packet(const unsigned char *from, struct interface *ifp,
} else if(type == MESSAGE_UPDATE) {
unsigned char prefix[16], *nh;
unsigned char plen;
+ unsigned char channels[DIVERSITY_HOPS];
unsigned short interval, seqno, metric;
- int rc;
+ int rc, parsed_len;
if(len < 10) {
if(len < 2 || message[3] & 0x80)
have_v4_prefix = have_v6_prefix = 0;
@@ -307,6 +370,7 @@ parse_packet(const unsigned char *from, struct interface *ifp,
have_v4_prefix = have_v6_prefix = 0;
goto fail;
}
+ parsed_len = 10 + rc;
plen = message[4] + (message[2] == 1 ? 96 : 0);
@@ -360,8 +424,27 @@ parse_packet(const unsigned char *from, struct interface *ifp,
goto done;
}
+ if((ifp->flags & BABEL_IF_FARAWAY)) {
+ channels[0] = 0;
+ } else {
+ /* This will be overwritten by parse_route_attributes below. */
+ if(metric < 256) {
+ /* Assume non-interfering (wired) link. */
+ channels[0] = 0;
+ } else {
+ /* Assume interfering. */
+ channels[0] = BABEL_IF_CHANNEL_INTERFERING;
+ channels[1] = 0;
+ }
+
+ if(parsed_len < len)
+ parse_route_attributes(message + 2 + parsed_len,
+ len - parsed_len, channels);
+ }
+
update_route(router_id, prefix, plen, seqno, metric, interval,
- neigh, nh);
+ neigh, nh,
+ channels, channels_len(channels));
} else if(type == MESSAGE_REQUEST) {
unsigned char prefix[16], plen;
int rc;
@@ -374,10 +457,17 @@ parse_packet(const unsigned char *from, struct interface *ifp,
message[2] == 0 ? "any" : format_prefix(prefix, plen),
format_address(from), ifp->name);
if(message[2] == 0) {
+ struct babel_interface *babel_ifp =babel_get_if_nfo(neigh->ifp);
/* If a neighbour is requesting a full route dump from us,
we might as well send it an IHU. */
send_ihu(neigh, NULL);
- send_update(neigh->ifp, 0, NULL, 0);
+ /* Since nodes send wildcard requests on boot, booting
+ a large number of nodes at the same time may cause an
+ update storm. Ignore a wildcard request that happens
+ shortly after we sent a full update. */
+ if(babel_ifp->last_update_time <
+ babel_now.tv_sec - MAX(babel_ifp->hello_interval / 100, 1))
+ send_update(neigh->ifp, 0, NULL, 0);
} else {
send_update(neigh->ifp, 0, prefix, plen);
}
@@ -665,10 +755,12 @@ send_hello_noupdate(struct interface *ifp, unsigned interval)
void
send_hello(struct interface *ifp)
{
+ int changed;
+ changed = update_hello_interval(ifp);
babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
send_hello_noupdate(ifp, (babel_ifp->hello_interval + 9) / 10);
/* Send full IHU every 3 hellos, and marginal IHU each time */
- if(babel_ifp->hello_seqno % 3 == 0)
+ if(changed || babel_ifp->hello_seqno % 3 == 0)
send_ihu(NULL, ifp);
else
send_marginal_ihu(ifp);
@@ -724,12 +816,19 @@ static void
really_send_update(struct interface *ifp,
const unsigned char *id,
const unsigned char *prefix, unsigned char plen,
- unsigned short seqno, unsigned short metric)
+ unsigned short seqno, unsigned short metric,
+ unsigned char *channels, int channels_len)
{
babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
int add_metric, v4, real_plen, omit = 0;
const unsigned char *real_prefix;
unsigned short flags = 0;
+ int channels_size;
+
+ if(diversity_kind != DIVERSITY_CHANNEL)
+ channels_len = -1;
+
+ channels_size = channels_len >= 0 ? channels_len + 2 : 0;
if(!if_up(ifp))
return;
@@ -786,7 +885,8 @@ really_send_update(struct interface *ifp,
babel_ifp->have_buffered_id = 1;
}
- start_message(ifp, MESSAGE_UPDATE, 10 + (real_plen + 7) / 8 - omit);
+ start_message(ifp, MESSAGE_UPDATE, 10 + (real_plen + 7) / 8 - omit +
+ channels_size);
accumulate_byte(ifp, v4 ? 1 : 2);
accumulate_byte(ifp, flags);
accumulate_byte(ifp, real_plen);
@@ -795,7 +895,14 @@ really_send_update(struct interface *ifp,
accumulate_short(ifp, seqno);
accumulate_short(ifp, metric);
accumulate_bytes(ifp, real_prefix + omit, (real_plen + 7) / 8 - omit);
- end_message(ifp, MESSAGE_UPDATE, 10 + (real_plen + 7) / 8 - omit);
+ /* Note that an empty channels TLV is different from no such TLV. */
+ if(channels_len >= 0) {
+ accumulate_byte(ifp, 2);
+ accumulate_byte(ifp, channels_len);
+ accumulate_bytes(ifp, channels, channels_len);
+ }
+ end_message(ifp, MESSAGE_UPDATE, 10 + (real_plen + 7) / 8 - omit +
+ channels_size);
if(flags & 0x80) {
memcpy(babel_ifp->buffered_prefix, prefix, 16);
@@ -884,9 +991,6 @@ flushupdates(struct interface *ifp)
qsort(b, n, sizeof(struct buffered_update), compare_buffered_updates);
for(i = 0; i < n; i++) {
- unsigned short seqno;
- unsigned short metric;
-
/* The same update may be scheduled multiple times before it is
sent out. Since our buffer is now sorted, it is enough to
compare with the previous update. */
@@ -903,22 +1007,51 @@ flushupdates(struct interface *ifp)
if(xroute && (!route || xroute->metric <= kernel_metric)) {
really_send_update(ifp, myid,
xroute->prefix, xroute->plen,
- myseqno, xroute->metric);
+ myseqno, xroute->metric,
+ NULL, 0);
last_prefix = xroute->prefix;
last_plen = xroute->plen;
} else if(route) {
+ unsigned char channels[DIVERSITY_HOPS];
+ int chlen;
+ struct interface *route_ifp = route->neigh->ifp;
+ struct babel_interface *babel_route_ifp = NULL;
+ unsigned short metric;
+ unsigned short seqno;
+
seqno = route->seqno;
- metric = route_metric(route);
+ metric =
+ route_interferes(route, ifp) ?
+ route_metric(route) :
+ route_metric_noninterfering(route);
+
if(metric < INFINITY)
satisfy_request(route->src->prefix, route->src->plen,
seqno, route->src->id, ifp);
if((babel_ifp->flags & BABEL_IF_SPLIT_HORIZON) &&
route->neigh->ifp == ifp)
continue;
+
+ babel_route_ifp = babel_get_if_nfo(route_ifp);
+ if(babel_route_ifp->channel ==BABEL_IF_CHANNEL_NONINTERFERING) {
+ memcpy(channels, route->channels, DIVERSITY_HOPS);
+ } else {
+ if(babel_route_ifp->channel == BABEL_IF_CHANNEL_UNKNOWN)
+ channels[0] = BABEL_IF_CHANNEL_INTERFERING;
+ else {
+ assert(babel_route_ifp->channel > 0 &&
+ babel_route_ifp->channel <= 255);
+ channels[0] = babel_route_ifp->channel;
+ }
+ memcpy(channels + 1, route->channels, DIVERSITY_HOPS - 1);
+ }
+
+ chlen = channels_len(channels);
really_send_update(ifp, route->src->id,
route->src->prefix,
route->src->plen,
- seqno, metric);
+ seqno, metric,
+ channels, chlen);
update_source(route->src, seqno, metric);
last_prefix = route->src->prefix;
last_plen = route->src->plen;
@@ -926,7 +1059,7 @@ flushupdates(struct interface *ifp)
/* There's no route for this prefix. This can happen shortly
after an xroute has been retracted, so send a retraction. */
really_send_update(ifp, myid, b[i].prefix, b[i].plen,
- myseqno, INFINITY);
+ myseqno, INFINITY, NULL, -1);
}
}
schedule_flush_now(ifp);
@@ -961,12 +1094,17 @@ buffer_update(struct interface *ifp,
if(babel_ifp->update_bufsize == 0) {
int n;
assert(babel_ifp->buffered_updates == NULL);
- n = MAX(babel_ifp->bufsize / 16, 4);
+ /* Allocate enough space to hold a full update. Since the
+ number of installed routes will grow over time, make sure we
+ have enough space to send a full-ish frame. */
+ n = installed_routes_estimate() + xroutes_estimate() + 4;
+ n = MAX(n, babel_ifp->bufsize / 16);
again:
babel_ifp->buffered_updates = malloc(n *sizeof(struct buffered_update));
if(babel_ifp->buffered_updates == NULL) {
zlog_err("malloc(buffered_updates): %s", safe_strerror(errno));
if(n > 4) {
+ /* Try again with a tiny buffer. */
n = 4;
goto again;
}
@@ -982,12 +1120,18 @@ buffer_update(struct interface *ifp,
babel_ifp->num_buffered_updates++;
}
+static void
+buffer_update_callback(struct babel_route *route, void *closure)
+{
+ buffer_update((struct interface*)closure,
+ route->src->prefix, route->src->plen);
+}
+
void
send_update(struct interface *ifp, int urgent,
const unsigned char *prefix, unsigned char plen)
{
babel_interface_nfo *babel_ifp = NULL;
- int i;
if(ifp == NULL) {
struct interface *ifp_aux;
@@ -1020,15 +1164,13 @@ send_update(struct interface *ifp, int urgent,
if(!interface_idle(babel_ifp)) {
send_self_update(ifp);
if(!parasitic) {
- debugf(BABEL_DEBUG_COMMON,"Sending update to %s for any.", ifp->name);
- for(i = 0; i < numroutes; i++)
- if(routes[i].installed)
- buffer_update(ifp,
- routes[i].src->prefix,
- routes[i].src->plen);
+ debugf(BABEL_DEBUG_COMMON,"Sending update to %s for any.",
+ ifp->name);
+ for_all_installed_routes(buffer_update_callback, ifp);
}
}
set_timeout(&babel_ifp->update_timeout, babel_ifp->update_interval);
+ babel_ifp->last_update_time = babel_now.tv_sec;
}
schedule_update_flush(ifp, urgent);
}
@@ -1086,11 +1228,16 @@ update_myseqno()
seqno_time = babel_now;
}
+static void
+send_xroute_update_callback(struct xroute *xroute, void *closure)
+{
+ struct interface *ifp = (struct interface*)closure;
+ send_update(ifp, 0, xroute->prefix, xroute->plen);
+}
+
void
send_self_update(struct interface *ifp)
{
- int i;
-
if(ifp == NULL) {
struct interface *ifp_aux;
struct listnode *linklist_node = NULL;
@@ -1104,8 +1251,7 @@ send_self_update(struct interface *ifp)
if(!interface_idle(babel_get_if_nfo(ifp))) {
debugf(BABEL_DEBUG_COMMON,"Sending self update to %s.", ifp->name);
- for(i = 0; i < numxroutes; i++)
- send_update(ifp, 0, xroutes[i].prefix, xroutes[i].plen);
+ for_all_xroutes(send_xroute_update_callback, ifp);
}
}
diff --git a/babeld/neighbour.c b/babeld/neighbour.c
index f360b891..5a327dfe 100644
--- a/babeld/neighbour.c
+++ b/babeld/neighbour.c
@@ -122,7 +122,8 @@ find_neighbour(const unsigned char *address, struct interface *ifp)
return neigh;
}
-/* Recompute a neighbour's rxcost. Return true if anything changed. */
+/* Recompute a neighbour's rxcost. Return true if anything changed.
+ This does not call local_notify_neighbour, see update_neighbour_metric. */
int
update_neighbour(struct neighbour *neigh, int hello, int hello_interval)
{
@@ -327,7 +328,7 @@ neighbour_cost(struct neighbour *neigh)
return INFINITY;
if(!(babel_get_if_nfo(neigh->ifp)->flags & BABEL_IF_LQ)
- || (a <= 256 && b <= 256)) {
+ || (a < 256 && b < 256)) {
return a;
} else {
/* a = 256/alpha, b = 256/beta, where alpha and beta are the expected
diff --git a/babeld/net.c b/babeld/net.c
index eaed51d2..5e0200b0 100644
--- a/babeld/net.c
+++ b/babeld/net.c
@@ -58,6 +58,7 @@ babel_socket(int port)
int s, rc;
int saved_errno;
int one = 1, zero = 0;
+ const int ds = 0xc0; /* CS6 - Network Control */
s = socket(PF_INET6, SOCK_DGRAM, 0);
if(s < 0)
@@ -86,6 +87,15 @@ babel_socket(int port)
if(rc < 0)
goto fail;
+#ifdef IPV6_TCLASS
+ rc = setsockopt(s, IPPROTO_IPV6, IPV6_TCLASS, &ds, sizeof(ds));
+#else
+ rc = -1;
+ errno = ENOSYS;
+#endif
+ if(rc < 0)
+ perror("Couldn't set traffic class");
+
rc = fcntl(s, F_GETFL, 0);
if(rc < 0)
goto fail;
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;
-}
diff --git a/babeld/route.h b/babeld/route.h
index c08332a6..b6d2d294 100644
--- a/babeld/route.h
+++ b/babeld/route.h
@@ -43,41 +43,69 @@ THE SOFTWARE.
#include "babel_interface.h"
#include "source.h"
+#define DIVERSITY_NONE 0
+#define DIVERSITY_INTERFACE_1 1
+#define DIVERSITY_CHANNEL_1 2
+#define DIVERSITY_CHANNEL 3
+
+#define DIVERSITY_HOPS 8
+
struct babel_route {
struct source *src;
- unsigned short metric;
unsigned short refmetric;
+ unsigned short cost;
+ unsigned short add_metric;
unsigned short seqno;
struct neighbour *neigh;
unsigned char nexthop[16];
time_t time;
unsigned short hold_time; /* in seconds */
short installed;
+ unsigned char channels[DIVERSITY_HOPS];
+ struct babel_route *next;
};
-static inline unsigned short
+extern struct babel_route **routes;
+extern int kernel_metric, allow_duplicates;
+extern int diversity_kind, diversity_factor;
+extern int keep_unfeasible;
+
+static inline int
route_metric(const struct babel_route *route)
{
- return route->metric;
+ int m = (int)route->refmetric + route->cost + route->add_metric;
+ return MIN(m, INFINITY);
}
-extern struct babel_route *routes;
-extern int numroutes, maxroutes;
-extern int kernel_metric, allow_duplicates;
+static inline int
+route_metric_noninterfering(const struct babel_route *route)
+{
+ int m =
+ (int)route->refmetric +
+ (diversity_factor * route->cost + 128) / 256 +
+ route->add_metric;
+ m = MAX(m, route->refmetric + 1);
+ return MIN(m, INFINITY);
+}
struct babel_route *find_route(const unsigned char *prefix, unsigned char plen,
struct neighbour *neigh, const unsigned char *nexthop);
struct babel_route *find_installed_route(const unsigned char *prefix,
unsigned char plen);
+int installed_routes_estimate(void);
void flush_route(struct babel_route *route);
+void flush_all_routes(void);
void flush_neighbour_routes(struct neighbour *neigh);
void flush_interface_routes(struct interface *ifp, int v4only);
+void for_all_routes(void (*f)(struct babel_route*, void*), void *closure);
+void for_all_installed_routes(void (*f)(struct babel_route*, void*), void *closure);
void install_route(struct babel_route *route);
void uninstall_route(struct babel_route *route);
void switch_route(struct babel_route *old, struct babel_route *new);
int route_feasible(struct babel_route *route);
int route_old(struct babel_route *route);
int route_expired(struct babel_route *route);
+int route_interferes(struct babel_route *route, struct interface *ifp);
int update_feasible(struct source *src,
unsigned short seqno, unsigned short refmetric);
struct babel_route *find_best_route(const unsigned char *prefix, unsigned char plen,
@@ -87,11 +115,12 @@ struct babel_route *install_best_route(const unsigned char prefix[16],
void update_neighbour_metric(struct neighbour *neigh, int change);
void update_interface_metric(struct interface *ifp);
void update_route_metric(struct babel_route *route);
-struct babel_route *update_route(const unsigned char *a,
- const unsigned char *p, unsigned char plen,
+struct babel_route *update_route(const unsigned char *id,
+ const unsigned char *prefix, unsigned char plen,
unsigned short seqno, unsigned short refmetric,
unsigned short interval, struct neighbour *neigh,
- const unsigned char *nexthop);
+ const unsigned char *nexthop,
+ const unsigned char *channels, int channels_len);
void retract_neighbour_routes(struct neighbour *neigh);
void send_unfeasible_request(struct neighbour *neigh, int force,
unsigned short seqno, unsigned short metric,
@@ -103,7 +132,4 @@ void route_changed(struct babel_route *route,
void route_lost(struct source *src, unsigned oldmetric);
void expire_routes(void);
-void babel_uninstall_all_routes(void);
-struct babel_route *babel_route_get_by_source(struct source *src);
-
#endif
diff --git a/babeld/source.c b/babeld/source.c
index cc4ed445..772112d4 100644
--- a/babeld/source.c
+++ b/babeld/source.c
@@ -63,8 +63,10 @@ find_source(const unsigned char *id, const unsigned char *p, unsigned char plen,
continue;
if(memcmp(src->id, id, 8) != 0)
continue;
- if(source_match(src, p, plen))
- return src;
+ if(src->plen != plen)
+ continue;
+ if(memcmp(src->prefix, p, 16) == 0)
+ return src;
}
if(!create)
@@ -82,18 +84,32 @@ find_source(const unsigned char *id, const unsigned char *p, unsigned char plen,
src->seqno = seqno;
src->metric = INFINITY;
src->time = babel_now.tv_sec;
+ src->route_count = 0;
src->next = srcs;
srcs = src;
return src;
}
+struct source *
+retain_source(struct source *src)
+{
+ assert(src->route_count < 0xffff);
+ src->route_count++;
+ return src;
+}
+
+void
+release_source(struct source *src)
+{
+ assert(src->route_count > 0);
+ src->route_count--;
+}
+
int
flush_source(struct source *src)
{
- /* This is absolutely horrible -- it makes expire_sources quadratic.
- But it's not called very often. */
-
- if (babel_route_get_by_source(src) != NULL)
+ if(src->route_count > 0)
+ /* The source is in use by a route. */
return 0;
if(srcs == src) {
@@ -109,19 +125,6 @@ flush_source(struct source *src)
return 1;
}
-int
-source_match(struct source *src,
- const unsigned char *p, unsigned char plen)
-{
- if(src->plen != plen)
- return 0;
- if(src->prefix[15] != p[15])
- return 0;
- if(memcmp(src->prefix, p, 16) != 0)
- return 0;
- return 1;
-}
-
void
update_source(struct source *src,
unsigned short seqno, unsigned short metric)
@@ -129,6 +132,10 @@ update_source(struct source *src,
if(metric >= INFINITY)
return;
+ /* If a source is expired, pretend that it doesn't exist and update
+ it unconditionally. This makes ensures that old data will
+ eventually be overridden, and prevents us from getting stuck if
+ a router loses its sequence number. */
if(src->time < babel_now.tv_sec - SOURCE_GC_TIME ||
seqno_compare(src->seqno, seqno) < 0 ||
(src->seqno == seqno && src->metric > metric)) {
@@ -157,3 +164,17 @@ expire_sources()
src = src->next;
}
}
+
+void
+check_sources_released(void)
+{
+ struct source *src;
+
+ for(src = srcs; src; src = src->next) {
+ if(src->route_count != 0)
+ fprintf(stderr, "Warning: source %s %s has refcount %d.\n",
+ format_eui64(src->id),
+ format_prefix(src->prefix, src->plen),
+ (int)src->route_count);
+ }
+}
diff --git a/babeld/source.h b/babeld/source.h
index 38d3c004..62a7e1ee 100644
--- a/babeld/source.h
+++ b/babeld/source.h
@@ -48,19 +48,20 @@ struct source {
unsigned char plen;
unsigned short seqno;
unsigned short metric;
+ unsigned short route_count;
time_t time;
};
-int source_match(struct source *src,
- const unsigned char *p, unsigned char plen);
struct source *find_source(const unsigned char *id,
const unsigned char *p,
unsigned char plen,
int create, unsigned short seqno);
+struct source *retain_source(struct source *src);
+void release_source(struct source *src);
int flush_source(struct source *src);
void update_source(struct source *src,
unsigned short seqno, unsigned short metric);
void expire_sources(void);
-
+void check_sources_released(void);
#endif
diff --git a/babeld/util.c b/babeld/util.c
index 514e0ff3..011f3824 100644
--- a/babeld/util.c
+++ b/babeld/util.c
@@ -200,17 +200,6 @@ parse_msec(const char *string)
return -1;
}
-void
-do_debugf(const char *format, ...)
-{
- va_list args;
- va_start(args, format);
- vfprintf(stderr, format, args);
- fprintf(stderr, "\n");
- fflush(stderr);
- va_end(args);
-}
-
int
in_prefix(const unsigned char *restrict address,
const unsigned char *restrict prefix, unsigned char plen)
@@ -328,63 +317,6 @@ parse_address(const char *address, unsigned char *addr_r, int *af_r)
}
int
-parse_net(const char *net, unsigned char *prefix_r, unsigned char *plen_r,
- int *af_r)
-{
- char buf[INET6_ADDRSTRLEN];
- char *slash, *end;
- unsigned char prefix[16];
- long plen;
- int af;
- struct in_addr ina;
- struct in6_addr ina6;
- int rc;
-
- if(strcmp(net, "default") == 0) {
- memset(prefix, 0, 16);
- plen = 0;
- } else {
- slash = strchr(net, '/');
- if(slash == NULL) {
- rc = parse_address(net, prefix, &af);
- if(rc < 0)
- return rc;
- plen = 128;
- } else {
- if(slash - net >= INET6_ADDRSTRLEN)
- return -1;
- memcpy(buf, net, slash - net);
- buf[slash - net] = '\0';
- rc = inet_pton(AF_INET, buf, &ina);
- if(rc > 0) {
- memcpy(prefix, v4prefix, 12);
- memcpy(prefix + 12, &ina, 4);
- plen = strtol(slash + 1, &end, 0);
- if(*end != '\0' || plen < 0 || plen > 32)
- return -1;
- plen += 96;
- af = AF_INET;
- } else {
- rc = inet_pton(AF_INET6, buf, &ina6);
- if(rc > 0) {
- memcpy(prefix, &ina6, 16);
- plen = strtol(slash + 1, &end, 0);
- if(*end != '\0' || plen < 0 || plen > 128)
- return -1;
- af = AF_INET6;
- } else {
- return -1;
- }
- }
- }
- }
- mask_prefix(prefix_r, prefix, plen);
- *plen_r = plen;
- if(af_r) *af_r = af;
- return 0;
-}
-
-int
parse_eui64(const char *eui, unsigned char *eui_r)
{
int n;
diff --git a/babeld/util.h b/babeld/util.h
index 376b967f..5d9d2f5d 100644
--- a/babeld/util.h
+++ b/babeld/util.h
@@ -100,8 +100,6 @@ int timeval_compare(const struct timeval *s1, const struct timeval *s2)
void timeval_min(struct timeval *d, const struct timeval *s);
void timeval_min_sec(struct timeval *d, time_t secs);
int parse_msec(const char *string) ATTRIBUTE ((pure));
-void do_debugf(const char *format, ...)
- ATTRIBUTE ((format (printf, 1, 2))) COLD;
int in_prefix(const unsigned char *restrict address,
const unsigned char *restrict prefix, unsigned char plen)
ATTRIBUTE ((pure));
@@ -113,8 +111,6 @@ const char *format_prefix(const unsigned char *address, unsigned char prefix);
const char *format_eui64(const unsigned char *eui);
const char *format_bool(const int b);
int parse_address(const char *address, unsigned char *addr_r, int *af_r);
-int parse_net(const char *ifp, unsigned char *prefix_r, unsigned char *plen_r,
- int *af_r);
int parse_eui64(const char *eui, unsigned char *eui_r);
int wait_for_fd(int direction, int fd, int msecs);
int martian_prefix(const unsigned char *prefix, int plen) ATTRIBUTE ((pure));
diff --git a/babeld/xroute.c b/babeld/xroute.c
index 8330b492..80651671 100644
--- a/babeld/xroute.c
+++ b/babeld/xroute.c
@@ -50,9 +50,12 @@ THE SOFTWARE.
#include "util.h"
#include "babel_interface.h"
-struct xroute *xroutes;
-int numxroutes = 0;
-int maxxroutes = 0;
+static int xroute_add_new_route(unsigned char prefix[16], unsigned char plen,
+ unsigned short metric, unsigned int ifindex,
+ int proto, int send_updates);
+
+static struct xroute *xroutes;
+static int numxroutes = 0, maxxroutes = 0;
/* Add redistributed route to Babel table. */
int
@@ -189,8 +192,24 @@ add_xroute(unsigned char prefix[16], unsigned char plen,
return 1;
}
-/* add an xroute, verifying some conditions; return 0 if there is no changes */
+/* Returns an overestimate of the number of xroutes. */
int
+xroutes_estimate()
+{
+ return numxroutes;
+}
+
+void
+for_all_xroutes(void (*f)(struct xroute*, void*), void *closure)
+{
+ int i;
+
+ for(i = 0; i < numxroutes; i++)
+ (*f)(&xroutes[i], closure);
+}
+
+/* add an xroute, verifying some conditions; return 0 if there is no changes */
+static int
xroute_add_new_route(unsigned char prefix[16], unsigned char plen,
unsigned short metric, unsigned int ifindex,
int proto, int send_updates)
diff --git a/babeld/xroute.h b/babeld/xroute.h
index c9a4f85f..4d4ab99d 100644
--- a/babeld/xroute.h
+++ b/babeld/xroute.h
@@ -45,14 +45,8 @@ struct xroute {
int proto;
};
-extern struct xroute *xroutes;
-extern int numxroutes;
-
struct xroute *find_xroute(const unsigned char *prefix, unsigned char plen);
void flush_xroute(struct xroute *xroute);
-int xroute_add_new_route(unsigned char prefix[16], unsigned char plen,
- unsigned short metric, unsigned int ifindex,
- int proto, int send_updates);
int babel_ipv4_route_add (struct zapi_ipv4 *api, struct prefix_ipv4 *prefix,
unsigned int ifindex, struct in_addr *nexthop);
int babel_ipv4_route_delete (struct zapi_ipv4 *api, struct prefix_ipv4 *prefix,
@@ -61,3 +55,5 @@ int babel_ipv6_route_add (struct zapi_ipv6 *api, struct prefix_ipv6 *prefix,
unsigned int ifindex, struct in6_addr *nexthop);
int babel_ipv6_route_delete (struct zapi_ipv6 *api, struct prefix_ipv6 *prefix,
unsigned int ifindex);
+int xroutes_estimate(void);
+void for_all_xroutes(void (*f)(struct xroute*, void*), void *closure);