-/*
- * This file is free software: you may copy, redistribute and/or modify it
- * under the terms of the GNU General Public License as published by the
- * Free Software Foundation, either version 2 of the License, or (at your
- * option) any later version.
- *
- * This file is distributed in the hope that it will be useful, but
- * WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
- * General Public License for more details.
- *
- * You should have received a copy of the GNU General Public License
- * along with this program. If not, see <http://www.gnu.org/licenses/>.
- *
- * This file incorporates work covered by the following copyright and
- * permission notice:
- *
-
+/*
Copyright (c) 2007, 2008 by Juliusz Chroboczek
Permission is hereby granted, free of charge, to any person obtaining a copy
THE SOFTWARE.
*/
-#include <stdlib.h>
-#include <string.h>
-#include <stdio.h>
-#include <assert.h>
-#include <sys/time.h>
-#include <netinet/in.h>
-#include <arpa/inet.h>
-
#include <zebra.h>
#include "if.h"
#include "resend.h"
#include "message.h"
#include "kernel.h"
+#include "babel_main.h"
-unsigned char packet_header[4] = {42, 2};
+static unsigned char packet_header[4] = {42, 2};
-int parasitic = 0;
int split_horizon = 1;
unsigned short myseqno = 0;
-struct timeval seqno_time = {0, 0};
#define UNICAST_BUFSIZE 1024
-int unicast_buffered = 0;
-unsigned char *unicast_buffer = NULL;
+static int unicast_buffered = 0;
+static unsigned char *unicast_buffer = NULL;
struct neighbour *unicast_neighbour = NULL;
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 };
-
+/* Minimum TLV _body_ length for TLVs of particular types (0 = no limit). */
+static const unsigned char tlv_min_length[MESSAGE_MAX + 1] =
+{
+ [ MESSAGE_PAD1 ] = 0,
+ [ MESSAGE_PADN ] = 0,
+ [ MESSAGE_ACK_REQ ] = 6,
+ [ MESSAGE_ACK ] = 2,
+ [ MESSAGE_HELLO ] = 6,
+ [ MESSAGE_IHU ] = 6,
+ [ MESSAGE_ROUTER_ID ] = 10,
+ [ MESSAGE_NH ] = 2,
+ [ MESSAGE_UPDATE ] = 10,
+ [ MESSAGE_REQUEST ] = 2,
+ [ MESSAGE_MH_REQUEST ] = 14,
+};
+
+/* 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,
{
unsigned pb;
unsigned char prefix[16];
+ int ret = -1;
if(plen >= 0)
pb = (plen + 7) / 8;
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;
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;
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_update_subtlv(const unsigned char *a, int alen,
+ unsigned char *channels)
+{
+ int type, len, i = 0;
+
+ while(i < alen) {
+ type = a[i];
+ if(type == SUBTLV_PAD1) {
+ i++;
+ continue;
+ }
+
+ if(i + 1 > alen) {
+ zlog_err("Received truncated attributes.");
+ return;
+ }
+ len = a[i + 1];
+ if(i + len > alen) {
+ zlog_err("Received truncated attributes.");
+ return;
+ }
+
+ if(type == SUBTLV_PADN) {
+ /* Nothing. */
+ } else if(type == SUBTLV_DIVERSITY) {
+ if(len > DIVERSITY_HOPS) {
+ zlog_err("Received overlong channel information (%d > %d).n",
+ len, DIVERSITY_HOPS);
+ len = DIVERSITY_HOPS;
+ }
+ if(memchr(a + i + 2, 0, len) != NULL) {
+ /* 0 is reserved. */
+ zlog_err("Channel information contains 0!");
+ return;
+ }
+ memset(channels, 0, DIVERSITY_HOPS);
+ memcpy(channels, a + i + 2, len);
+ } else {
+ debugf(BABEL_DEBUG_COMMON,
+ "Received unknown route attribute %d.", type);
+ }
+
+ i += len + 2;
+ }
+}
+
+static int
+parse_hello_subtlv(const unsigned char *a, int alen,
+ unsigned int *hello_send_us)
+{
+ int type, len, i = 0, ret = 0;
+
+ while(i < alen) {
+ type = a[0];
+ if(type == SUBTLV_PAD1) {
+ i++;
+ continue;
+ }
+
+ if(i + 1 > alen) {
+ zlog_err("Received truncated sub-TLV on Hello message.");
+ return -1;
+ }
+ len = a[i + 1];
+ if(i + len > alen) {
+ zlog_err("Received truncated sub-TLV on Hello message.");
+ return -1;
+ }
+
+ if(type == SUBTLV_PADN) {
+ /* Nothing to do. */
+ } else if(type == SUBTLV_TIMESTAMP) {
+ if(len >= 4) {
+ DO_NTOHL(*hello_send_us, a + i + 2);
+ ret = 1;
+ } else {
+ zlog_err("Received incorrect RTT sub-TLV on Hello message.");
+ }
+ } else {
+ debugf(BABEL_DEBUG_COMMON,
+ "Received unknown Hello sub-TLV type %d.", type);
+ }
+
+ i += len + 2;
+ }
+ return ret;
+}
+
+static int
+parse_ihu_subtlv(const unsigned char *a, int alen,
+ unsigned int *hello_send_us,
+ unsigned int *hello_rtt_receive_time)
+{
+ int type, len, i = 0, ret = 0;
+
+ while(i < alen) {
+ type = a[0];
+ if(type == SUBTLV_PAD1) {
+ i++;
+ continue;
+ }
+
+ if(i + 1 > alen) {
+ zlog_err("Received truncated sub-TLV on IHU message.");
+ return -1;
+ }
+ len = a[i + 1];
+ if(i + len > alen) {
+ zlog_err("Received truncated sub-TLV on IHU message.");
+ return -1;
+ }
+
+ if(type == SUBTLV_PADN) {
+ /* Nothing to do. */
+ } else if(type == SUBTLV_TIMESTAMP) {
+ if(len >= 8) {
+ DO_NTOHL(*hello_send_us, a + i + 2);
+ DO_NTOHL(*hello_rtt_receive_time, a + i + 6);
+ ret = 1;
+ }
+ else {
+ zlog_err("Received incorrect RTT sub-TLV on IHU message.");
+ }
+ } else {
+ debugf(BABEL_DEBUG_COMMON,
+ "Received unknown IHU sub-TLV type %d.", type);
+ }
+
+ i += len + 2;
+ }
+ return ret;
}
static int
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;
+}
+
+/* Check, that the provided frame consists of a valid Babel packet header
+ followed by a sequence of TLVs. TLVs of known types are also checked to meet
+ minimum length constraints defined for each. Return 0 for no errors. */
+static int
+babel_packet_examin(const unsigned char *packet, int packetlen)
+{
+ unsigned i = 0, bodylen;
+ const unsigned char *message;
+ unsigned char type, len;
+
+ if(packetlen < 4 || packet[0] != 42 || packet[1] != 2)
+ return 1;
+ DO_NTOHS(bodylen, packet + 2);
+ while (i < bodylen){
+ message = packet + 4 + i;
+ type = message[0];
+ if(type == MESSAGE_PAD1) {
+ i++;
+ continue;
+ }
+ if(i + 1 > bodylen) {
+ debugf(BABEL_DEBUG_COMMON,"Received truncated message.");
+ return 1;
+ }
+ len = message[1];
+ if(i + len > bodylen) {
+ debugf(BABEL_DEBUG_COMMON,"Received truncated message.");
+ return 1;
+ }
+ /* not Pad1 */
+ if(type <= MESSAGE_MAX && tlv_min_length[type] && len < tlv_min_length[type]) {
+ debugf(BABEL_DEBUG_COMMON,"Undersized %u TLV", type);
+ return 1;
+ }
+ i += len + 2;
+ }
+ return 0;
+}
+
void
parse_packet(const unsigned char *from, struct interface *ifp,
const unsigned char *packet, int packetlen)
have_v4_nh = 0, have_v6_nh = 0;
unsigned char router_id[8], v4_prefix[16], v6_prefix[16],
v4_nh[16], v6_nh[16];
+ int have_hello_rtt = 0;
+ /* Content of the RTT sub-TLV on IHU messages. */
+ unsigned int hello_send_us = 0, hello_rtt_receive_time = 0;
+ babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
- if(!linklocal(from)) {
- fprintf(stderr, "Received packet from non-local address %s.\n",
- format_address(from));
- return;
+ if(babel_ifp->flags & BABEL_IF_TIMESTAMPS) {
+ /* We want to track exactly when we received this packet. */
+ gettime(&babel_now);
}
- if(packet[0] != 42) {
- fprintf(stderr, "Received malformed packet on %s from %s.\n",
- ifp->name, format_address(from));
+ if(!linklocal(from)) {
+ zlog_err("Received packet from non-local address %s.",
+ format_address(from));
return;
}
- if(packet[1] != 2) {
- fprintf(stderr,
- "Received packet with unknown version %d on %s from %s.\n",
- packet[1], ifp->name, format_address(from));
+ if (babel_packet_examin (packet, packetlen)) {
+ zlog_err("Received malformed packet on %s from %s.",
+ ifp->name, format_address(from));
return;
}
neigh = find_neighbour(from, ifp);
if(neigh == NULL) {
- fprintf(stderr, "Couldn't allocate neighbour.\n");
+ zlog_err("Couldn't allocate neighbour.");
return;
}
DO_NTOHS(bodylen, packet + 2);
if(bodylen + 4 > packetlen) {
- fprintf(stderr, "Received truncated packet (%d + 4 > %d).\n",
- bodylen, packetlen);
+ zlog_err("Received truncated packet (%d + 4 > %d).",
+ bodylen, packetlen);
bodylen = packetlen - 4;
}
i++;
continue;
}
- if(i + 1 > bodylen) {
- fprintf(stderr, "Received truncated message.\n");
- break;
- }
len = message[1];
- if(i + len > bodylen) {
- fprintf(stderr, "Received truncated message.\n");
- break;
- }
if(type == MESSAGE_PADN) {
debugf(BABEL_DEBUG_COMMON,"Received pad%d from %s on %s.",
len, format_address(from), ifp->name);
} else if(type == MESSAGE_ACK_REQ) {
unsigned short nonce, interval;
- if(len < 6) goto fail;
DO_NTOHS(nonce, message + 4);
DO_NTOHS(interval, message + 6);
debugf(BABEL_DEBUG_COMMON,"Received ack-req (%04X %d) from %s on %s.",
} else if(type == MESSAGE_HELLO) {
unsigned short seqno, interval;
int changed;
- if(len < 6) goto fail;
+ unsigned int timestamp = 0;
DO_NTOHS(seqno, message + 4);
DO_NTOHS(interval, message + 6);
debugf(BABEL_DEBUG_COMMON,"Received hello %d (%d) from %s on %s.",
seqno, interval,
format_address(from), ifp->name);
- babel_get_if_nfo(ifp)->activity_time = babel_now.tv_sec;
changed = update_neighbour(neigh, seqno, interval);
update_neighbour_metric(neigh, changed);
if(interval > 0)
- schedule_neighbours_check(interval * 10, 0);
+ /* Multiply by 3/2 to allow hellos to expire. */
+ schedule_neighbours_check(interval * 15, 0);
+ /* Sub-TLV handling. */
+ if(len > 8) {
+ if(parse_hello_subtlv(message + 8, len - 6, ×tamp) > 0) {
+ neigh->hello_send_us = timestamp;
+ neigh->hello_rtt_receive_time = babel_now;
+ have_hello_rtt = 1;
+ }
+ }
} else if(type == MESSAGE_IHU) {
unsigned short txcost, interval;
unsigned char address[16];
int rc;
- if(len < 6) goto fail;
DO_NTOHS(txcost, message + 4);
DO_NTOHS(interval, message + 6);
rc = network_address(message[2], message + 8, len - 6, address);
neigh->ihu_interval = interval;
update_neighbour_metric(neigh, changed);
if(interval > 0)
- schedule_neighbours_check(interval * 10 * 3, 0);
+ /* Multiply by 3/2 to allow neighbours to expire. */
+ schedule_neighbours_check(interval * 45, 0);
+ /* RTT sub-TLV. */
+ if(len > 10 + rc)
+ parse_ihu_subtlv(message + 8 + rc, len - 6 - rc,
+ &hello_send_us, &hello_rtt_receive_time);
}
} else if(type == MESSAGE_ROUTER_ID) {
- if(len < 10) {
- have_router_id = 0;
- goto fail;
- }
memcpy(router_id, message + 4, 8);
have_router_id = 1;
debugf(BABEL_DEBUG_COMMON,"Received router-id %s from %s on %s.",
} else if(type == MESSAGE_NH) {
unsigned char nh[16];
int rc;
- if(len < 2) {
- have_v4_nh = 0;
- have_v6_nh = 0;
- goto fail;
- }
rc = network_address(message[2], message + 4, len - 2,
nh);
if(rc < 0) {
} 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;
- if(len < 10) {
- if(len < 2 || message[3] & 0x80)
- have_v4_prefix = have_v6_prefix = 0;
- goto fail;
- }
+ int rc, parsed_len;
DO_NTOHS(interval, message + 6);
DO_NTOHS(seqno, message + 8);
DO_NTOHS(metric, message + 10);
if(message[5] == 0 ||
- (message[3] == 1 ? have_v4_prefix : have_v6_prefix))
+ (message[2] == 1 ? have_v4_prefix : have_v6_prefix))
rc = network_prefix(message[2], message[4], message[5],
message + 12,
message[2] == 1 ? v4_prefix : v6_prefix,
have_v4_prefix = have_v6_prefix = 0;
goto fail;
}
+ parsed_len = 10 + rc;
plen = message[4] + (message[2] == 1 ? 96 : 0);
have_router_id = 1;
}
if(!have_router_id && message[2] != 0) {
- fprintf(stderr, "Received prefix with no router id.\n");
+ zlog_err("Received prefix with no router id.");
goto fail;
}
debugf(BABEL_DEBUG_COMMON,"Received update%s%s for %s from %s on %s.",
if(message[2] == 0) {
if(metric < 0xFFFF) {
- fprintf(stderr,
- "Received wildcard update with finite metric.\n");
+ zlog_err("Received wildcard update with finite metric.");
goto done;
}
retract_neighbour_routes(neigh);
goto done;
}
+ if((babel_get_if_nfo(ifp)->flags & BABEL_IF_FARAWAY)) {
+ channels[0] = 0;
+ } else {
+ /* This will be overwritten by parse_update_subtlv 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_update_subtlv(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;
- if(len < 2) goto fail;
rc = network_prefix(message[2], message[3], 0,
message + 4, NULL, len - 2, prefix);
if(rc < 0) goto fail;
message[2] == 0 ? "any" : format_prefix(prefix, plen),
format_address(from), ifp->name);
if(message[2] == 0) {
+ struct babel_interface *neigh_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(neigh_ifp->last_update_time <
+ (time_t)(babel_now.tv_sec -
+ MAX(neigh_ifp->hello_interval / 100, 1)))
+ send_update(neigh->ifp, 0, NULL, 0);
} else {
send_update(neigh->ifp, 0, prefix, plen);
}
unsigned char prefix[16], plen;
unsigned short seqno;
int rc;
- if(len < 14) goto fail;
DO_NTOHS(seqno, message + 4);
rc = network_prefix(message[2], message[3], 0,
message + 16, NULL, len - 14, prefix);
continue;
fail:
- fprintf(stderr, "Couldn't parse packet (%d, %d) from %s on %s.\n",
- message[0], message[1], format_address(from), ifp->name);
+ zlog_err("Couldn't parse packet (%d, %d) from %s on %s.",
+ message[0], message[1], format_address(from), ifp->name);
goto done;
}
+
+ /* We can calculate the RTT to this neighbour. */
+ if(have_hello_rtt && hello_send_us && hello_rtt_receive_time) {
+ int remote_waiting_us, local_waiting_us;
+ unsigned int rtt, smoothed_rtt;
+ unsigned int old_rttcost;
+ int changed = 0;
+ remote_waiting_us = neigh->hello_send_us - hello_rtt_receive_time;
+ local_waiting_us = time_us(neigh->hello_rtt_receive_time) -
+ hello_send_us;
+
+ /* Sanity checks (validity window of 10 minutes). */
+ if(remote_waiting_us < 0 || local_waiting_us < 0 ||
+ remote_waiting_us > 600000000 || local_waiting_us > 600000000)
+ return;
+
+ rtt = MAX(0, local_waiting_us - remote_waiting_us);
+ debugf(BABEL_DEBUG_COMMON, "RTT to %s on %s sample result: %d us.\n",
+ format_address(from), ifp->name, rtt);
+
+ old_rttcost = neighbour_rttcost(neigh);
+ if (valid_rtt(neigh)) {
+ /* Running exponential average. */
+ smoothed_rtt = (babel_ifp->rtt_decay * rtt +
+ (256 - babel_ifp->rtt_decay) * neigh->rtt);
+ /* Rounding (up or down) to get closer to the sample. */
+ neigh->rtt = (neigh->rtt >= rtt) ? smoothed_rtt / 256 :
+ (smoothed_rtt + 255) / 256;
+ } else {
+ /* We prefer to be conservative with new neighbours
+ (higher RTT) */
+ assert(rtt <= 0x7FFFFFFF);
+ neigh->rtt = 2*rtt;
+ }
+ changed = (neighbour_rttcost(neigh) == old_rttcost ? 0 : 1);
+ update_neighbour_metric(neigh, changed);
+ neigh->rtt_time = babel_now;
+ }
return;
}
}
}
+static int
+fill_rtt_message(struct interface *ifp)
+{
+ babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
+ if((babel_ifp->flags & BABEL_IF_TIMESTAMPS) &&
+ (babel_ifp->buffered_hello >= 0)) {
+ if(babel_ifp->sendbuf[babel_ifp->buffered_hello + 8] == SUBTLV_PADN &&
+ babel_ifp->sendbuf[babel_ifp->buffered_hello + 9] == 4) {
+ unsigned int time;
+ /* Change the type of sub-TLV. */
+ babel_ifp->sendbuf[babel_ifp->buffered_hello + 8] =
+ SUBTLV_TIMESTAMP;
+ gettime(&babel_now);
+ time = time_us(babel_now);
+ DO_HTONL(babel_ifp->sendbuf + babel_ifp->buffered_hello + 10, time);
+ return 1;
+ } else {
+ zlog_err("No space left for timestamp sub-TLV "
+ "(this shouldn't happen)");
+ return -1;
+ }
+ }
+ return 0;
+}
+
void
flushbuf(struct interface *ifp)
{
sin6.sin6_port = htons(protocol_port);
sin6.sin6_scope_id = ifp->ifindex;
DO_HTONS(packet_header + 2, babel_ifp->buffered);
+ fill_rtt_message(ifp);
rc = babel_send(protocol_socket,
packet_header, sizeof(packet_header),
babel_ifp->sendbuf, babel_ifp->buffered,
if(rc < 0)
zlog_err("send: %s", safe_strerror(errno));
} else {
- fprintf(stderr, "Warning: bucket full, dropping packet to %s.\n",
- ifp->name);
+ zlog_err("Warning: bucket full, dropping packet to %s.",
+ ifp->name);
}
}
VALGRIND_MAKE_MEM_UNDEFINED(babel_ifp->sendbuf, babel_ifp->bufsize);
babel_ifp->buffered = 0;
- babel_ifp->have_buffered_hello = 0;
+ babel_ifp->buffered_hello = -1;
babel_ifp->have_buffered_id = 0;
babel_ifp->have_buffered_nh = 0;
babel_ifp->have_buffered_prefix = 0;
babel_ifp->buffered += 2;
}
+static void
+accumulate_int(struct interface *ifp, unsigned int value)
+{
+ babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
+ DO_HTONL(babel_ifp->sendbuf + babel_ifp->buffered, value);
+ babel_ifp->buffered += 4;
+}
+
static void
accumulate_bytes(struct interface *ifp,
const unsigned char *value, unsigned len)
unicast_buffered += 2;
}
+static void
+accumulate_unicast_int(struct neighbour *neigh, unsigned int value)
+{
+ DO_HTONL(unicast_buffer + unicast_buffered, value);
+ unicast_buffered += 4;
+}
+
static void
accumulate_unicast_bytes(struct neighbour *neigh,
const unsigned char *value, unsigned len)
babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp);
/* This avoids sending multiple hellos in a single packet, which breaks
link quality estimation. */
- if(babel_ifp->have_buffered_hello)
+ if(babel_ifp->buffered_hello >= 0)
flushbuf(ifp);
babel_ifp->hello_seqno = seqno_plus(babel_ifp->hello_seqno, 1);
debugf(BABEL_DEBUG_COMMON,"Sending hello %d (%d) to %s.",
babel_ifp->hello_seqno, interval, ifp->name);
- start_message(ifp, MESSAGE_HELLO, 6);
+ start_message(ifp, MESSAGE_HELLO,
+ (babel_ifp->flags & BABEL_IF_TIMESTAMPS) ? 12 : 6);
+ babel_ifp->buffered_hello = babel_ifp->buffered - 2;
accumulate_short(ifp, 0);
accumulate_short(ifp, babel_ifp->hello_seqno);
accumulate_short(ifp, interval > 0xFFFF ? 0xFFFF : interval);
- end_message(ifp, MESSAGE_HELLO, 6);
- babel_ifp->have_buffered_hello = 1;
+ if(babel_ifp->flags & BABEL_IF_TIMESTAMPS) {
+ /* Sub-TLV containing the local time of emission. We use a
+ Pad4 sub-TLV, which we'll fill just before sending. */
+ accumulate_byte(ifp, SUBTLV_PADN);
+ accumulate_byte(ifp, 4);
+ accumulate_int(ifp, 0);
+ }
+ end_message(ifp, MESSAGE_HELLO,
+ (babel_ifp->flags & BABEL_IF_TIMESTAMPS) ? 12 : 6);
}
void
sin6.sin6_port = htons(protocol_port);
sin6.sin6_scope_id = unicast_neighbour->ifp->ifindex;
DO_HTONS(packet_header + 2, unicast_buffered);
+ fill_rtt_message(unicast_neighbour->ifp);
rc = babel_send(protocol_socket,
packet_header, sizeof(packet_header),
unicast_buffer, unicast_buffered,
if(rc < 0)
zlog_err("send(unicast): %s", safe_strerror(errno));
} else {
- fprintf(stderr,
- "Warning: bucket full, dropping unicast packet"
- "to %s if %s.\n",
- format_address(unicast_neighbour->address),
- unicast_neighbour->ifp->name);
+ zlog_err("Warning: bucket full, dropping unicast packet to %s if %s.",
+ format_address(unicast_neighbour->address),
+ unicast_neighbour->ifp->name);
}
done:
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;
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);
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);
{
babel_interface_nfo *babel_ifp = NULL;
struct xroute *xroute;
- struct route *route;
+ struct babel_route *route;
const unsigned char *last_prefix = NULL;
unsigned char last_plen = 0xFF;
int i;
if(ifp == NULL) {
- struct interface *ifp_aux;
- struct listnode *linklist_node = NULL;
- FOR_ALL_INTERFACES(ifp_aux, linklist_node)
+ struct vrf *vrf = vrf_lookup_by_id(VRF_DEFAULT);
+ struct interface *ifp_aux;
+ FOR_ALL_INTERFACES(vrf, ifp_aux)
flushupdates(ifp_aux);
return;
}
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. */
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;
/* 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);
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;
}
const unsigned char *prefix, unsigned char plen)
{
babel_interface_nfo *babel_ifp = NULL;
- int i;
if(ifp == NULL) {
- struct interface *ifp_aux;
- struct listnode *linklist_node = NULL;
- struct route *route;
- FOR_ALL_INTERFACES(ifp_aux, linklist_node)
+ struct vrf *vrf = vrf_lookup_by_id(VRF_DEFAULT);
+ struct interface *ifp_aux;
+ struct babel_route *route;
+ FOR_ALL_INTERFACES(vrf, ifp_aux)
send_update(ifp_aux, urgent, prefix, plen);
if(prefix) {
/* Since flushupdates only deals with non-wildcard interfaces, we
babel_ifp = babel_get_if_nfo(ifp);
if(prefix) {
- if(!parasitic || find_xroute(prefix, plen)) {
- debugf(BABEL_DEBUG_COMMON,"Sending update to %s for %s.",
- ifp->name, format_prefix(prefix, plen));
- buffer_update(ifp, prefix, plen);
- }
+ debugf(BABEL_DEBUG_COMMON,"Sending update to %s for %s.",
+ ifp->name, format_prefix(prefix, plen));
+ buffer_update(ifp, prefix, plen);
} else {
- 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);
+ struct route_stream *routes = NULL;
+ send_self_update(ifp);
+ debugf(BABEL_DEBUG_COMMON,"Sending update to %s for any.", ifp->name);
+ routes = route_stream(1);
+ if(routes) {
+ while(1) {
+ struct babel_route *route = route_stream_next(routes);
+ if(route == NULL)
+ break;
+ buffer_update(ifp, route->src->prefix, route->src->plen);
}
+ route_stream_done(routes);
+ } else {
+ zlog_err("Couldn't allocate route stream.");
}
set_timeout(&babel_ifp->update_timeout, babel_ifp->update_interval);
+ babel_ifp->last_update_time = babel_now.tv_sec;
}
schedule_update_flush(ifp, urgent);
}
send_update_resend(struct interface *ifp,
const unsigned char *prefix, unsigned char plen)
{
- int delay;
-
assert(prefix != NULL);
send_update(ifp, 1, prefix, plen);
-
- delay = 2000;
- delay = MIN(delay, wireless_hello_interval / 2);
- delay = MIN(delay, wired_hello_interval / 2);
- delay = MAX(delay, 10);
- record_resend(RESEND_UPDATE, prefix, plen, 0, 0, NULL, delay);
+ record_resend(RESEND_UPDATE, prefix, plen, 0, NULL, NULL, resend_delay);
}
void
{
babel_interface_nfo *babel_ifp = NULL;
if(ifp == NULL) {
- struct interface *ifp_aux;
- struct listnode *linklist_node = NULL;
- FOR_ALL_INTERFACES(ifp_aux, linklist_node)
+ struct vrf *vrf = vrf_lookup_by_id(VRF_DEFAULT);
+ struct interface *ifp_aux;
+ FOR_ALL_INTERFACES(vrf, ifp_aux)
send_wildcard_retraction(ifp_aux);
return;
}
update_myseqno()
{
myseqno = seqno_plus(myseqno, 1);
- seqno_time = babel_now;
}
void
send_self_update(struct interface *ifp)
{
- int i;
-
+ struct xroute_stream *xroutes;
if(ifp == NULL) {
- struct interface *ifp_aux;
- struct listnode *linklist_node = NULL;
- FOR_ALL_INTERFACES(ifp_aux, linklist_node) {
+ struct vrf *vrf = vrf_lookup_by_id(VRF_DEFAULT);
+ struct interface *ifp_aux;
+ FOR_ALL_INTERFACES(vrf, ifp_aux) {
if(!if_up(ifp_aux))
continue;
send_self_update(ifp_aux);
return;
}
- 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);
+ debugf(BABEL_DEBUG_COMMON,"Sending self update to %s.", ifp->name);
+ xroutes = xroute_stream();
+ if(xroutes) {
+ while(1) {
+ struct xroute *xroute = xroute_stream_next(xroutes);
+ if(xroute == NULL) break;
+ send_update(ifp, 0, xroute->prefix, xroute->plen);
+ }
+ xroute_stream_done(xroutes);
+ } else {
+ zlog_err("Couldn't allocate xroute stream.");
}
}
babel_interface_nfo *babel_ifp = NULL;
int rxcost, interval;
int ll;
+ int send_rtt_data;
+ int msglen;
if(neigh == NULL && ifp == NULL) {
- struct interface *ifp_aux;
- struct listnode *linklist_node = NULL;
- FOR_ALL_INTERFACES(ifp_aux, linklist_node) {
+ struct vrf *vrf = vrf_lookup_by_id(VRF_DEFAULT);
+ struct interface *ifp_aux;
+ FOR_ALL_INTERFACES(vrf, ifp_aux) {
if(if_up(ifp_aux))
continue;
send_ihu(NULL, ifp_aux);
ll = linklocal(neigh->address);
+ if((babel_ifp->flags & BABEL_IF_TIMESTAMPS) && neigh->hello_send_us
+ /* Checks whether the RTT data is not too old to be sent. */
+ && timeval_minus_msec(&babel_now,
+ &neigh->hello_rtt_receive_time) < 1000000) {
+ send_rtt_data = 1;
+ } else {
+ neigh->hello_send_us = 0;
+ send_rtt_data = 0;
+ }
+
+ /* The length depends on the format of the address, and then an
+ optional 10-bytes sub-TLV for timestamps (used to compute a RTT). */
+ msglen = (ll ? 14 : 22) + (send_rtt_data ? 10 : 0);
+
if(unicast_neighbour != neigh) {
- start_message(ifp, MESSAGE_IHU, ll ? 14 : 22);
+ start_message(ifp, MESSAGE_IHU, msglen);
accumulate_byte(ifp, ll ? 3 : 2);
accumulate_byte(ifp, 0);
accumulate_short(ifp, rxcost);
accumulate_bytes(ifp, neigh->address + 8, 8);
else
accumulate_bytes(ifp, neigh->address, 16);
- end_message(ifp, MESSAGE_IHU, ll ? 14 : 22);
+ if (send_rtt_data) {
+ accumulate_byte(ifp, SUBTLV_TIMESTAMP);
+ accumulate_byte(ifp, 8);
+ accumulate_int(ifp, neigh->hello_send_us);
+ accumulate_int(ifp, time_us(neigh->hello_rtt_receive_time));
+ }
+ end_message(ifp, MESSAGE_IHU, msglen);
} else {
int rc;
- rc = start_unicast_message(neigh, MESSAGE_IHU, ll ? 14 : 22);
+ rc = start_unicast_message(neigh, MESSAGE_IHU, msglen);
if(rc < 0) return;
accumulate_unicast_byte(neigh, ll ? 3 : 2);
accumulate_unicast_byte(neigh, 0);
accumulate_unicast_bytes(neigh, neigh->address + 8, 8);
else
accumulate_unicast_bytes(neigh, neigh->address, 16);
- end_unicast_message(neigh, MESSAGE_IHU, ll ? 14 : 22);
+ if (send_rtt_data) {
+ accumulate_unicast_byte(neigh, SUBTLV_TIMESTAMP);
+ accumulate_unicast_byte(neigh, 8);
+ accumulate_unicast_int(neigh, neigh->hello_send_us);
+ accumulate_unicast_int(neigh,
+ time_us(neigh->hello_rtt_receive_time));
+ }
+ end_unicast_message(neigh, MESSAGE_IHU, msglen);
}
}
send_request(struct interface *ifp,
const unsigned char *prefix, unsigned char plen)
{
- babel_interface_nfo *babel_ifp = NULL;
- int v4, len;
+ int v4, pb, len;
if(ifp == NULL) {
- struct interface *ifp_aux;
- struct listnode *linklist_node = NULL;
- FOR_ALL_INTERFACES(ifp_aux, linklist_node) {
+ struct vrf *vrf = vrf_lookup_by_id(VRF_DEFAULT);
+ struct interface *ifp_aux;
+ FOR_ALL_INTERFACES(vrf, ifp_aux) {
if(if_up(ifp_aux))
continue;
send_request(ifp_aux, prefix, plen);
if(!if_up(ifp))
return;
- babel_ifp = babel_get_if_nfo(ifp);
debugf(BABEL_DEBUG_COMMON,"sending request to %s for %s.",
ifp->name, prefix ? format_prefix(prefix, plen) : "any");
v4 = plen >= 96 && v4mapped(prefix);
- len = !prefix ? 2 : v4 ? 6 : 18;
+ pb = v4 ? ((plen - 96) + 7) / 8 : (plen + 7) / 8;
+ len = !prefix ? 2 : 2 + pb;
start_message(ifp, MESSAGE_REQUEST, len);
accumulate_byte(ifp, !prefix ? 0 : v4 ? 1 : 2);
accumulate_byte(ifp, !prefix ? 0 : v4 ? plen - 96 : plen);
if(prefix) {
if(v4)
- accumulate_bytes(ifp, prefix + 12, 4);
+ accumulate_bytes(ifp, prefix + 12, pb);
else
- accumulate_bytes(ifp, prefix, 16);
+ accumulate_bytes(ifp, prefix, pb);
}
end_message(ifp, MESSAGE_REQUEST, len);
}
send_unicast_request(struct neighbour *neigh,
const unsigned char *prefix, unsigned char plen)
{
- int rc, v4, len;
+ int rc, v4, pb, len;
/* make sure any buffered updates go out before this request. */
flushupdates(neigh->ifp);
format_address(neigh->address),
prefix ? format_prefix(prefix, plen) : "any");
v4 = plen >= 96 && v4mapped(prefix);
- len = !prefix ? 2 : v4 ? 6 : 18;
+ pb = v4 ? ((plen - 96) + 7) / 8 : (plen + 7) / 8;
+ len = !prefix ? 2 : 2 + pb;
rc = start_unicast_message(neigh, MESSAGE_REQUEST, len);
if(rc < 0) return;
accumulate_unicast_byte(neigh, !prefix ? 0 : v4 ? plen - 96 : plen);
if(prefix) {
if(v4)
- accumulate_unicast_bytes(neigh, prefix + 12, 4);
+ accumulate_unicast_bytes(neigh, prefix + 12, pb);
else
- accumulate_unicast_bytes(neigh, prefix, 16);
+ accumulate_unicast_bytes(neigh, prefix, pb);
}
end_unicast_message(neigh, MESSAGE_REQUEST, len);
}
unsigned short seqno, const unsigned char *id,
unsigned short hop_count)
{
- babel_interface_nfo *babel_ifp = NULL;
int v4, pb, len;
/* Make sure any buffered updates go out before this request. */
flushupdates(ifp);
if(ifp == NULL) {
- struct interface *ifp_aux;
- struct listnode *linklist_node = NULL;
- FOR_ALL_INTERFACES(ifp_aux, linklist_node) {
+ struct vrf *vrf = vrf_lookup_by_id(VRF_DEFAULT);
+ struct interface *ifp_aux;
+ FOR_ALL_INTERFACES(vrf, ifp_aux) {
if(!if_up(ifp_aux))
continue;
send_multihop_request(ifp_aux, prefix, plen, seqno, id, hop_count);
if(!if_up(ifp))
return;
- babel_ifp = babel_get_if_nfo(ifp);
debugf(BABEL_DEBUG_COMMON,"Sending request (%d) on %s for %s.",
hop_count, ifp->name, format_prefix(prefix, plen));
v4 = plen >= 96 && v4mapped(prefix);
const unsigned char *prefix, unsigned char plen,
unsigned short seqno, unsigned char *id)
{
- int delay;
-
if(neigh)
send_unicast_multihop_request(neigh, prefix, plen, seqno, id, 127);
else
send_multihop_request(NULL, prefix, plen, seqno, id, 127);
- delay = 2000;
- delay = MIN(delay, wireless_hello_interval / 2);
- delay = MIN(delay, wired_hello_interval / 2);
- delay = MAX(delay, 10);
record_resend(RESEND_REQUEST, prefix, plen, seqno, id,
- neigh ? neigh->ifp : NULL, delay);
+ neigh ? neigh->ifp : NULL, resend_delay);
}
void
unsigned short seqno, const unsigned char *id)
{
struct xroute *xroute;
- struct route *route;
+ struct babel_route *route;
struct neighbour *successor = NULL;
xroute = find_xroute(prefix, plen);
if(!successor || successor == neigh) {
/* We were about to forward a request to its requestor. Try to
find a different neighbour to forward the request to. */
- struct route *other_route;
+ struct babel_route *other_route;
other_route = find_best_route(prefix, plen, 0, neigh);
if(other_route && route_metric(other_route) < INFINITY)
projects / mirror_frr.git / blobdiff