diff options
| -rw-r--r-- | babeld/babel_interface.c | 72 | ||||
| -rw-r--r-- | babeld/babel_interface.h | 19 | ||||
| -rw-r--r-- | babeld/babel_main.c | 2 | ||||
| -rw-r--r-- | babeld/babeld.c | 2 | ||||
| -rw-r--r-- | babeld/message.c | 202 | ||||
| -rw-r--r-- | babeld/neighbour.c | 5 | ||||
| -rw-r--r-- | babeld/net.c | 10 | ||||
| -rw-r--r-- | babeld/route.c | 574 | ||||
| -rw-r--r-- | babeld/route.h | 50 | ||||
| -rw-r--r-- | babeld/source.c | 59 | ||||
| -rw-r--r-- | babeld/source.h | 7 | ||||
| -rw-r--r-- | babeld/util.c | 68 | ||||
| -rw-r--r-- | babeld/util.h | 4 | ||||
| -rw-r--r-- | babeld/xroute.c | 27 | ||||
| -rw-r--r-- | babeld/xroute.h | 8 |
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); |