diff options
Diffstat (limited to 'babeld/message.c')
| -rw-r--r-- | babeld/message.c | 1948 |
1 files changed, 1948 insertions, 0 deletions
diff --git a/babeld/message.c b/babeld/message.c new file mode 100644 index 0000000..f854932 --- /dev/null +++ b/babeld/message.c @@ -0,0 +1,1948 @@ +// SPDX-License-Identifier: MIT +/* +Copyright (c) 2007, 2008 by Juliusz Chroboczek +*/ + +#include <zebra.h> +#include "if.h" + +#include "babeld.h" +#include "util.h" +#include "net.h" +#include "babel_interface.h" +#include "source.h" +#include "neighbour.h" +#include "route.h" +#include "xroute.h" +#include "resend.h" +#include "message.h" +#include "kernel.h" +#include "babel_main.h" +#include "babel_errors.h" + +static unsigned char packet_header[4] = {42, 2}; + +int split_horizon = 1; + +unsigned short myseqno = 0; + +#define UNICAST_BUFSIZE 1024 +static int unicast_buffered = 0; +static unsigned char *unicast_buffer = NULL; +struct neighbour *unicast_neighbour = NULL; +struct timeval unicast_flush_timeout = {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, +}; + +/* Checks whether an AE exists or must be silently ignored */ +static bool +known_ae(int ae) +{ + return ae <= 4; +} + +/* 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 int len, unsigned char *p_r) +{ + unsigned pb; + unsigned char prefix[16]; + int ret = -1; + + if(plen >= 0) + pb = (plen + 7) / 8; + else if(ae == 1) + pb = 4; + else + pb = 16; + + if(pb > 16) + return -1; + + memset(prefix, 0, 16); + + switch(ae) { + case 0: + ret = 0; + break; + case 1: + if(omitted > 4 || pb > 4 || (pb > omitted && len < pb - omitted)) + return -1; + memcpy(prefix, v4prefix, 12); + if(omitted) { + if (dp == NULL || !v4mapped(dp)) 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; + if(omitted) { + if (dp == NULL || v4mapped(dp)) 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 ret; +} + +static bool 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) { + flog_err(EC_BABEL_PACKET, "Received truncated attributes."); + return false; + } + len = a[i + 1]; + if(i + len + 2 > alen) { + flog_err(EC_BABEL_PACKET, "Received truncated attributes."); + return false; + } + + if (type & SUBTLV_MANDATORY) { + /* + * RFC 8966 - 4.4 + * If the mandatory bit is set, then the whole enclosing + * TLV MUST be silently ignored (except for updating the + * parser state by a Router-Id, Next Hop, or Update TLV, + * as described in the next section). + */ + debugf(BABEL_DEBUG_COMMON, + "Received Mandatory bit set but this FRR version is not prepared to handle it at this point"); + return true; + } else if (type == SUBTLV_PADN) { + /* Nothing. */ + } else if (type == SUBTLV_DIVERSITY) { + if (len > DIVERSITY_HOPS) { + flog_err( + EC_BABEL_PACKET, + "Received overlong channel information (%d > %d).n", + len, DIVERSITY_HOPS); + len = DIVERSITY_HOPS; + } + if (memchr(a + i + 2, 0, len) != NULL) { + /* 0 is reserved. */ + flog_err(EC_BABEL_PACKET, + "Channel information contains 0!"); + return false; + } + 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; + } + return false; +} + +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[i]; + if(type == SUBTLV_PAD1) { + i++; + continue; + } + + if(i + 1 >= alen) { + flog_err(EC_BABEL_PACKET, + "Received truncated sub-TLV on Hello message."); + return -1; + } + len = a[i + 1]; + if(i + len + 2 > alen) { + flog_err(EC_BABEL_PACKET, + "Received truncated sub-TLV on Hello message."); + return -1; + } + + if (type & SUBTLV_MANDATORY) { + /* + * RFC 8966 4.4 + * If the mandatory bit is set, then the whole enclosing + * TLV MUST be silently ignored (except for updating the + * parser state by a Router-Id, Next Hop, or Update TLV, as + * described in the next section). + */ + debugf(BABEL_DEBUG_COMMON, + "Received subtlv with Mandatory bit, this version of FRR is not prepared to handle this currently"); + return -2; + } else 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 { + flog_err( + EC_BABEL_PACKET, + "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[i]; + if(type == SUBTLV_PAD1) { + i++; + continue; + } + + if(i + 1 >= alen) { + flog_err(EC_BABEL_PACKET, + "Received truncated sub-TLV on IHU message."); + return -1; + } + len = a[i + 1]; + if(i + len + 2 > alen) { + flog_err(EC_BABEL_PACKET, + "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 { + flog_err(EC_BABEL_PACKET, + "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 +parse_request_subtlv(int ae, const unsigned char *a, int alen, + unsigned char *src_prefix, unsigned char *src_plen) +{ + int type, len, i = 0; + int have_src_prefix = 0; + + while(i < alen) { + type = a[0]; + if(type == SUBTLV_PAD1) { + i++; + continue; + } + + if(i + 2 > alen) + goto fail; + + len = a[i + 1]; + if(i + 2 + len > alen) + goto fail; + + if(type == SUBTLV_PADN) { + /* Nothing to do. */ + } else if(type == SUBTLV_SOURCE_PREFIX) { + int rc; + if(len < 1) + goto fail; + if(a[i + 2] == 0) + goto fail; + if(have_src_prefix != 0) + goto fail; + rc = network_prefix(ae, a[i + 2], 0, a + i + 3, NULL, + len - 1, src_prefix); + if(rc < 0) + goto fail; + if(ae==1) + *src_plen = a[i + 2] + 96; + else + *src_plen = a[i + 2]; + have_src_prefix = 1; + } else { + debugf(BABEL_DEBUG_COMMON,"Received unknown%s Route Request sub-TLV %d.", + ((type & 0x80) != 0) ? " mandatory" : "", type); + if((type & 0x80) != 0) + return -1; + } + + i += len + 2; + } + return 1; + + fail: + flog_err(EC_BABEL_PACKET, "Received truncated sub-TLV on Route Request."); + return -1; +} + +static int +network_address(int ae, const unsigned char *a, unsigned int len, + unsigned char *a_r) +{ + 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, int *blength) +{ + int 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); + if(bodylen + 4 > packetlen) { + debugf(BABEL_DEBUG_COMMON, "Received truncated packet (%d + 4 > %d).", + bodylen, packetlen); + return 1; + } + while (i < bodylen){ + message = packet + 4 + i; + type = message[0]; + if(type == MESSAGE_PAD1) { + i++; + continue; + } + if(i + 2 > bodylen) { + debugf(BABEL_DEBUG_COMMON,"Received truncated message."); + return 1; + } + len = message[1]; + if(i + len + 2 > 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; + } + + *blength = bodylen; + return 0; +} + +void +parse_packet(const unsigned char *from, struct interface *ifp, + const unsigned char *packet, int packetlen) +{ + int i; + const unsigned char *message; + unsigned char type, len; + int bodylen; + struct neighbour *neigh; + int have_router_id = 0, have_v4_prefix = 0, have_v6_prefix = 0, + 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(babel_ifp->flags & BABEL_IF_TIMESTAMPS) { + /* We want to track exactly when we received this packet. */ + gettime(&babel_now); + } + + if(!linklocal(from)) { + flog_err(EC_BABEL_PACKET, + "Received packet from non-local address %s.", + format_address(from)); + return; + } + + if (babel_packet_examin (packet, packetlen, &bodylen)) { + flog_err(EC_BABEL_PACKET, + "Received malformed packet on %s from %s.", + ifp->name, format_address(from)); + return; + } + + neigh = find_neighbour(from, ifp); + if(neigh == NULL) { + flog_err(EC_BABEL_PACKET, "Couldn't allocate neighbour."); + return; + } + + i = 0; + while(i < bodylen) { + message = packet + 4 + i; + type = message[0]; + if(type == MESSAGE_PAD1) { + debugf(BABEL_DEBUG_COMMON,"Received pad1 from %s on %s.", + format_address(from), ifp->name); + i++; + continue; + } + len = message[1]; + + 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; + DO_NTOHS(nonce, message + 4); + DO_NTOHS(interval, message + 6); + debugf(BABEL_DEBUG_COMMON,"Received ack-req (%04X %d) from %s on %s.", + nonce, interval, format_address(from), ifp->name); + send_ack(neigh, nonce, interval); + } else if(type == MESSAGE_ACK) { + debugf(BABEL_DEBUG_COMMON,"Received ack from %s on %s.", + format_address(from), ifp->name); + /* Nothing right now */ + } else if(type == MESSAGE_HELLO) { + unsigned short seqno, interval, flags; + int changed; + unsigned int timestamp = 0; + +#define BABEL_UNICAST_HELLO 0x8000 + DO_NTOHS(flags, message + 2); + + /* + * RFC 8966 Appendix F + * TL;DR -> Please ignore Unicast hellos until FRR's + * BABEL is brought up to date + */ + if (CHECK_FLAG(flags, BABEL_UNICAST_HELLO)) { + debugf(BABEL_DEBUG_COMMON, + "Received Unicast Hello from %s on %s that FRR is not prepared to understand yet", + format_address(from), ifp->name); + goto done; + } + + 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); + + /* + * RFC 8966 Appendix F + * TL;DR -> Please ignore any Hello packets with the interval + * field set to 0 + */ + if (interval == 0) { + debugf(BABEL_DEBUG_COMMON, + "Received hello from %s on %s should be ignored as that this version of FRR does not know how to properly handle interval == 0", + format_address(from), ifp->name); + goto done; + } + + changed = update_neighbour(neigh, seqno, interval); + update_neighbour_metric(neigh, changed); + if (interval > 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; + DO_NTOHS(txcost, message + 4); + DO_NTOHS(interval, message + 6); + rc = network_address(message[2], message + 8, len - 6, address); + if(rc < 0) goto fail; + debugf(BABEL_DEBUG_COMMON,"Received ihu %d (%d) from %s on %s for %s.", + txcost, interval, + format_address(from), ifp->name, + format_address(address)); + if(message[2] == 0 || is_interface_ll_address(ifp, address)) { + int changed = txcost != neigh->txcost; + neigh->txcost = txcost; + neigh->ihu_time = babel_now; + neigh->ihu_interval = interval; + update_neighbour_metric(neigh, changed); + if(interval > 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) { + memcpy(router_id, message + 4, 8); + have_router_id = 1; + debugf(BABEL_DEBUG_COMMON,"Received router-id %s from %s on %s.", + format_eui64(router_id), format_address(from), ifp->name); + } else if(type == MESSAGE_NH) { + unsigned char nh[16]; + int rc; + rc = network_address(message[2], message + 4, len - 2, + nh); + if(rc <= 0) { + have_v4_nh = 0; + have_v6_nh = 0; + goto fail; + } + debugf(BABEL_DEBUG_COMMON,"Received nh %s (%d) from %s on %s.", + format_address(nh), message[2], + format_address(from), ifp->name); + if(message[2] == 1) { + memcpy(v4_nh, nh, 16); + have_v4_nh = 1; + } else { + memcpy(v6_nh, nh, 16); + have_v6_nh = 1; + } + } 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, parsed_len; + bool ignore_update = false; + + DO_NTOHS(interval, message + 6); + DO_NTOHS(seqno, message + 8); + DO_NTOHS(metric, message + 10); + if(message[5] == 0 || + (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, + len - 10, prefix); + else + rc = -1; + if(rc < 0) { + if(message[3] & 0x80) + have_v4_prefix = have_v6_prefix = 0; + goto fail; + } + parsed_len = 10 + rc; + + plen = message[4] + (message[2] == 1 ? 96 : 0); + + if(message[3] & 0x80) { + if(message[2] == 1) { + memcpy(v4_prefix, prefix, 16); + have_v4_prefix = 1; + } else { + memcpy(v6_prefix, prefix, 16); + have_v6_prefix = 1; + } + } + if(message[3] & 0x40) { + if(message[2] == 1) { + memset(router_id, 0, 4); + memcpy(router_id + 4, prefix + 12, 4); + } else { + memcpy(router_id, prefix + 8, 8); + } + have_router_id = 1; + } + if(!have_router_id && message[2] != 0) { + flog_err(EC_BABEL_PACKET, + "Received prefix with no router id."); + goto fail; + } + debugf(BABEL_DEBUG_COMMON,"Received update%s%s for %s from %s on %s.", + (message[3] & 0x80) ? "/prefix" : "", + (message[3] & 0x40) ? "/id" : "", + format_prefix(prefix, plen), + format_address(from), ifp->name); + + if(message[2] == 0) { + if(metric < 0xFFFF) { + flog_err(EC_BABEL_PACKET, + "Received wildcard update with finite metric."); + goto done; + } + retract_neighbour_routes(neigh); + goto done; + } else if(message[2] == 1) { + if(!have_v4_nh) + goto fail; + nh = v4_nh; + } else if(have_v6_nh) { + nh = v6_nh; + } else { + nh = neigh->address; + } + + if(message[2] == 1) { + if(!babel_get_if_nfo(ifp)->ipv4) + 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) + ignore_update = + parse_update_subtlv(message + 2 + parsed_len, + len - parsed_len, channels); + } + + if (!ignore_update) + update_route(router_id, prefix, plen, seqno, metric, + interval, neigh, nh, channels, + channels_len(channels)); + } else if(type == MESSAGE_REQUEST) { + unsigned char prefix[16], src_prefix[16], plen, src_plen; + int rc, is_ss; + if(len < 2) goto fail; + if(!known_ae(message[2])) { + debugf(BABEL_DEBUG_COMMON,"Received request with unknown AE %d. Ignoring.", + message[2]); + goto done; + } + rc = network_prefix(message[2], message[3], 0, + message + 4, NULL, len - 2, prefix); + if(rc < 0) goto fail; + plen = message[3] + (message[2] == 1 ? 96 : 0); + debugf(BABEL_DEBUG_COMMON,"Received request for %s from %s on %s.", + message[2] == 0 ? "any" : format_prefix(prefix, plen), + format_address(from), ifp->name); + if(message[2] == 1) { + v4tov6(src_prefix, zeroes); + src_plen = 96; + } else { + memcpy(src_prefix, zeroes, 16); + src_plen = 0; + } + rc = parse_request_subtlv(message[2], message + 4 + rc, + len - 2 - rc, src_prefix, &src_plen); + if(rc < 0) + goto done; + is_ss = !is_default(src_prefix, src_plen); + if(message[2] == 0) { + struct babel_interface *neigh_ifp =babel_get_if_nfo(neigh->ifp); + if(is_ss) { + /* Wildcard requests don't carry a source prefix. */ + flog_err(EC_BABEL_PACKET, + "Received source-specific wildcard request."); + goto done; + } + /* If a neighbour is requesting a full route dump from us, + we might as well send it an IHU. */ + send_ihu(neigh, NULL); + /* 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); + } + } else if(type == MESSAGE_MH_REQUEST) { + unsigned char prefix[16], plen; + unsigned short seqno; + int rc; + DO_NTOHS(seqno, message + 4); + rc = network_prefix(message[2], message[3], 0, + message + 16, NULL, len - 14, prefix); + if(rc <= 0) goto fail; + plen = message[3] + (message[2] == 1 ? 96 : 0); + debugf(BABEL_DEBUG_COMMON,"Received request (%d) for %s from %s on %s (%s, %d).", + message[6], + format_prefix(prefix, plen), + format_address(from), ifp->name, + format_eui64(message + 8), seqno); + handle_request(neigh, prefix, plen, message[6], + seqno, message + 8); + } else { + debugf(BABEL_DEBUG_COMMON,"Received unknown packet type %d from %s on %s.", + type, format_address(from), ifp->name); + } + done: + i += len + 2; + continue; + + fail: + flog_err(EC_BABEL_PACKET, + "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.", + 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; +} + +/* Under normal circumstances, there are enough moderation mechanisms + elsewhere in the protocol to make sure that this last-ditch check + should never trigger. But I'm superstitious. */ + +static int +check_bucket(struct interface *ifp) +{ + babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp); + if(babel_ifp->bucket == 0) { + int seconds = babel_now.tv_sec - babel_ifp->bucket_time; + if(seconds > 0) { + babel_ifp->bucket = MIN(BUCKET_TOKENS_MAX, + seconds * BUCKET_TOKENS_PER_SEC); + } + /* Reset bucket time unconditionally, in case clock is stepped. */ + babel_ifp->bucket_time = babel_now.tv_sec; + } + + if(babel_ifp->bucket > 0) { + babel_ifp->bucket--; + return 1; + } else { + return 0; + } +} + +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 { + flog_err(EC_BABEL_PACKET, "No space left for timestamp sub-TLV (this shouldn't happen)"); + return -1; + } + } + return 0; +} + +void +flushbuf(struct interface *ifp) +{ + int rc; + struct sockaddr_in6 sin6; + babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp); + + assert(babel_ifp->buffered <= babel_ifp->bufsize); + + flushupdates(ifp); + + if(babel_ifp->buffered > 0) { + debugf(BABEL_DEBUG_COMMON," (flushing %d buffered bytes on %s)", + babel_ifp->buffered, ifp->name); + if(check_bucket(ifp)) { + memset(&sin6, 0, sizeof(sin6)); + sin6.sin6_family = AF_INET6; + memcpy(&sin6.sin6_addr, protocol_group, 16); + 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, + (struct sockaddr*)&sin6, sizeof(sin6)); + if(rc < 0) + flog_err(EC_BABEL_PACKET, "send: %s", safe_strerror(errno)); + } else { + flog_err(EC_BABEL_PACKET, "Bucket full, dropping packet to %s.", + ifp->name); + } + } + VALGRIND_MAKE_MEM_UNDEFINED(babel_ifp->sendbuf, babel_ifp->bufsize); + babel_ifp->buffered = 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->flush_timeout.tv_sec = 0; + babel_ifp->flush_timeout.tv_usec = 0; +} + +static void +schedule_flush(struct interface *ifp) +{ + babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp); + unsigned msecs = jitter(babel_ifp, 0); + if(babel_ifp->flush_timeout.tv_sec != 0 && + timeval_minus_msec(&babel_ifp->flush_timeout, &babel_now) < msecs) + return; + set_timeout(&babel_ifp->flush_timeout, msecs); +} + +static void +schedule_flush_now(struct interface *ifp) +{ + babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp); + /* Almost now */ + unsigned msecs = roughly(10); + if(babel_ifp->flush_timeout.tv_sec != 0 && + timeval_minus_msec(&babel_ifp->flush_timeout, &babel_now) < msecs) + return; + set_timeout(&babel_ifp->flush_timeout, msecs); +} + +static void +schedule_unicast_flush(unsigned msecs) +{ + if(!unicast_neighbour) + return; + if(unicast_flush_timeout.tv_sec != 0 && + timeval_minus_msec(&unicast_flush_timeout, &babel_now) < msecs) + return; + unicast_flush_timeout.tv_usec = (babel_now.tv_usec + msecs * 1000) %1000000; + unicast_flush_timeout.tv_sec = + babel_now.tv_sec + (babel_now.tv_usec / 1000 + msecs) / 1000; +} + +static void +ensure_space(struct interface *ifp, int space) +{ + babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp); + if(babel_ifp->bufsize - babel_ifp->buffered < space) + flushbuf(ifp); +} + +static void +start_message(struct interface *ifp, int type, int len) +{ + babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp); + if(babel_ifp->bufsize - babel_ifp->buffered < len + 2) + flushbuf(ifp); + babel_ifp->sendbuf[babel_ifp->buffered++] = type; + babel_ifp->sendbuf[babel_ifp->buffered++] = len; +} + +static void +end_message(struct interface *ifp, int type, int bytes) +{ + babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp); + assert(babel_ifp->buffered >= bytes + 2 && + babel_ifp->sendbuf[babel_ifp->buffered - bytes - 2] == type && + babel_ifp->sendbuf[babel_ifp->buffered - bytes - 1] == bytes); + schedule_flush(ifp); +} + +static void +accumulate_byte(struct interface *ifp, unsigned char value) +{ + babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp); + babel_ifp->sendbuf[babel_ifp->buffered++] = value; +} + +static void +accumulate_short(struct interface *ifp, unsigned short value) +{ + babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp); + DO_HTONS(babel_ifp->sendbuf + babel_ifp->buffered, value); + 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) +{ + babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp); + memcpy(babel_ifp->sendbuf + babel_ifp->buffered, value, len); + babel_ifp->buffered += len; +} + +static int +start_unicast_message(struct neighbour *neigh, int type, int len) +{ + if(unicast_neighbour) { + if(neigh != unicast_neighbour || + unicast_buffered + len + 2 >= + MIN(UNICAST_BUFSIZE, babel_get_if_nfo(neigh->ifp)->bufsize)) + flush_unicast(0); + } + if(!unicast_buffer) + unicast_buffer = malloc(UNICAST_BUFSIZE); + if(!unicast_buffer) { + flog_err(EC_BABEL_MEMORY, "malloc(unicast_buffer): %s", + safe_strerror(errno)); + return -1; + } + + unicast_neighbour = neigh; + + unicast_buffer[unicast_buffered++] = type; + unicast_buffer[unicast_buffered++] = len; + return 1; +} + +static void +end_unicast_message(struct neighbour *neigh, int type, int bytes) +{ + assert(unicast_neighbour == neigh && unicast_buffered >= bytes + 2 && + unicast_buffer[unicast_buffered - bytes - 2] == type && + unicast_buffer[unicast_buffered - bytes - 1] == bytes); + schedule_unicast_flush(jitter(babel_get_if_nfo(neigh->ifp), 0)); +} + +static void +accumulate_unicast_byte(struct neighbour *neigh, unsigned char value) +{ + unicast_buffer[unicast_buffered++] = value; +} + +static void +accumulate_unicast_short(struct neighbour *neigh, unsigned short value) +{ + DO_HTONS(unicast_buffer + unicast_buffered, value); + 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) +{ + memcpy(unicast_buffer + unicast_buffered, value, len); + unicast_buffered += len; +} + +void +send_ack(struct neighbour *neigh, unsigned short nonce, unsigned short interval) +{ + int rc; + debugf(BABEL_DEBUG_COMMON,"Sending ack (%04x) to %s on %s.", + nonce, format_address(neigh->address), neigh->ifp->name); + rc = start_unicast_message(neigh, MESSAGE_ACK, 2); if(rc < 0) return; + accumulate_unicast_short(neigh, nonce); + end_unicast_message(neigh, MESSAGE_ACK, 2); + /* Roughly yields a value no larger than 3/2, so this meets the deadline */ + schedule_unicast_flush(roughly(interval * 6)); +} + +void +send_hello_noupdate(struct interface *ifp, unsigned interval) +{ + 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->buffered_hello >= 0) + flushbuf(ifp); + + babel_ifp->hello_seqno = seqno_plus(babel_ifp->hello_seqno, 1); + set_timeout(&babel_ifp->hello_timeout, babel_ifp->hello_interval); + + if(!if_up(ifp)) + return; + + debugf(BABEL_DEBUG_COMMON,"Sending hello %d (%d) to %s.", + babel_ifp->hello_seqno, interval, ifp->name); + + 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); + 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 +send_hello(struct interface *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) + send_ihu(NULL, ifp); + else + send_marginal_ihu(ifp); +} + +void +flush_unicast(int dofree) +{ + struct sockaddr_in6 sin6; + int rc; + + if(unicast_buffered == 0) + goto done; + + if(!if_up(unicast_neighbour->ifp)) + goto done; + + /* Preserve ordering of messages */ + flushbuf(unicast_neighbour->ifp); + + if(check_bucket(unicast_neighbour->ifp)) { + memset(&sin6, 0, sizeof(sin6)); + sin6.sin6_family = AF_INET6; + memcpy(&sin6.sin6_addr, unicast_neighbour->address, 16); + 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, + (struct sockaddr*)&sin6, sizeof(sin6)); + if(rc < 0) + flog_err(EC_BABEL_PACKET, "send(unicast): %s", + safe_strerror(errno)); + } else { + flog_err(EC_BABEL_PACKET, + "Bucket full, dropping unicast packet to %s if %s.", + format_address(unicast_neighbour->address), + unicast_neighbour->ifp->name); + } + + done: + VALGRIND_MAKE_MEM_UNDEFINED(unicast_buffer, UNICAST_BUFSIZE); + unicast_buffered = 0; + if(dofree && unicast_buffer) { + free(unicast_buffer); + unicast_buffer = NULL; + } + unicast_neighbour = NULL; + unicast_flush_timeout.tv_sec = 0; + unicast_flush_timeout.tv_usec = 0; +} + +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 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; + + add_metric = output_filter(id, prefix, plen, ifp->ifindex); + if(add_metric >= INFINITY) + return; + + metric = MIN(metric + add_metric, INFINITY); + /* Worst case */ + ensure_space(ifp, 20 + 12 + 28); + + v4 = plen >= 96 && v4mapped(prefix); + + if(v4) { + if(!babel_ifp->ipv4) + return; + if(!babel_ifp->have_buffered_nh || + memcmp(babel_ifp->buffered_nh, babel_ifp->ipv4, 4) != 0) { + start_message(ifp, MESSAGE_NH, 6); + accumulate_byte(ifp, 1); + accumulate_byte(ifp, 0); + accumulate_bytes(ifp, babel_ifp->ipv4, 4); + end_message(ifp, MESSAGE_NH, 6); + memcpy(babel_ifp->buffered_nh, babel_ifp->ipv4, 4); + babel_ifp->have_buffered_nh = 1; + } + + real_prefix = prefix + 12; + real_plen = plen - 96; + } else { + if(babel_ifp->have_buffered_prefix) { + while(omit < plen / 8 && + babel_ifp->buffered_prefix[omit] == prefix[omit]) + omit++; + } + if(!babel_ifp->have_buffered_prefix || plen >= 48) + flags |= 0x80; + real_prefix = prefix; + real_plen = plen; + } + + if(!babel_ifp->have_buffered_id + || memcmp(id, babel_ifp->buffered_id, 8) != 0) { + if(real_plen == 128 && memcmp(real_prefix + 8, id, 8) == 0) { + flags |= 0x40; + } else { + start_message(ifp, MESSAGE_ROUTER_ID, 10); + accumulate_short(ifp, 0); + accumulate_bytes(ifp, id, 8); + end_message(ifp, MESSAGE_ROUTER_ID, 10); + } + memcpy(babel_ifp->buffered_id, id, sizeof(babel_ifp->buffered_id)); + babel_ifp->have_buffered_id = 1; + } + + 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_byte(ifp, omit); + accumulate_short(ifp, (babel_ifp->update_interval + 5) / 10); + accumulate_short(ifp, seqno); + accumulate_short(ifp, metric); + accumulate_bytes(ifp, real_prefix + omit, (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); + + if (channels && channels_len > 0) + 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_ifp->have_buffered_prefix = 1; + } +} + +static int +compare_buffered_updates(const void *av, const void *bv) +{ + const struct buffered_update *a = av, *b = bv; + int rc, v4a, v4b, ma, mb; + + rc = memcmp(a->id, b->id, 8); + if(rc != 0) + return rc; + + v4a = (a->plen >= 96 && v4mapped(a->prefix)); + v4b = (b->plen >= 96 && v4mapped(b->prefix)); + + if(v4a > v4b) + return 1; + else if(v4a < v4b) + return -1; + + ma = (!v4a && a->plen == 128 && memcmp(a->prefix + 8, a->id, 8) == 0); + mb = (!v4b && b->plen == 128 && memcmp(b->prefix + 8, b->id, 8) == 0); + + if(ma > mb) + return -1; + else if(mb > ma) + return 1; + + if(a->plen < b->plen) + return 1; + else if(a->plen > b->plen) + return -1; + + return memcmp(a->prefix, b->prefix, 16); +} + +void +flushupdates(struct interface *ifp) +{ + babel_interface_nfo *babel_ifp = NULL; + struct xroute *xroute; + struct babel_route *route; + const unsigned char *last_prefix = NULL; + unsigned char last_plen = 0xFF; + int i; + + if(ifp == NULL) { + struct vrf *vrf = vrf_lookup_by_id(VRF_DEFAULT); + struct interface *ifp_aux; + FOR_ALL_INTERFACES(vrf, ifp_aux) + flushupdates(ifp_aux); + return; + } + + babel_ifp = babel_get_if_nfo(ifp); + if(babel_ifp->num_buffered_updates > 0) { + struct buffered_update *b = babel_ifp->buffered_updates; + int n = babel_ifp->num_buffered_updates; + + babel_ifp->buffered_updates = NULL; + babel_ifp->update_bufsize = 0; + babel_ifp->num_buffered_updates = 0; + + if(!if_up(ifp)) + goto done; + + debugf(BABEL_DEBUG_COMMON," (flushing %d buffered updates on %s (%d))", + n, ifp->name, ifp->ifindex); + + /* In order to send fewer update messages, we want to send updates + with the same router-id together, with IPv6 going out before IPv4. */ + + for(i = 0; i < n; i++) { + route = find_installed_route(b[i].prefix, b[i].plen); + if(route) + memcpy(b[i].id, route->src->id, 8); + else + memcpy(b[i].id, myid, 8); + } + + qsort(b, n, sizeof(struct buffered_update), compare_buffered_updates); + + for(i = 0; i < n; i++) { + /* 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(last_prefix) { + if(b[i].plen == last_plen && + memcmp(b[i].prefix, last_prefix, 16) == 0) + continue; + } + + xroute = find_xroute(b[i].prefix, b[i].plen); + route = find_installed_route(b[i].prefix, b[i].plen); + + if(xroute && (!route || xroute->metric <= kernel_metric)) { + really_send_update(ifp, myid, + xroute->prefix, xroute->plen, + 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_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, + channels, chlen); + update_source(route->src, seqno, metric); + last_prefix = route->src->prefix; + last_plen = route->src->plen; + } else { + /* 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, NULL, -1); + } + } + schedule_flush_now(ifp); + done: + free(b); + } + babel_ifp->update_flush_timeout.tv_sec = 0; + babel_ifp->update_flush_timeout.tv_usec = 0; +} + +static void +schedule_update_flush(struct interface *ifp, int urgent) +{ + babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp); + unsigned msecs; + msecs = update_jitter(babel_ifp, urgent); + if(babel_ifp->update_flush_timeout.tv_sec != 0 && + timeval_minus_msec(&babel_ifp->update_flush_timeout, &babel_now) < msecs) + return; + set_timeout(&babel_ifp->update_flush_timeout, msecs); +} + +static void +buffer_update(struct interface *ifp, + const unsigned char *prefix, unsigned char plen) +{ + babel_interface_nfo *babel_ifp = babel_get_if_nfo(ifp); + if(babel_ifp->num_buffered_updates > 0 && + babel_ifp->num_buffered_updates >= babel_ifp->update_bufsize) + flushupdates(ifp); + + if(babel_ifp->update_bufsize == 0) { + int n; + assert(babel_ifp->buffered_updates == NULL); + /* 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) { + flog_err(EC_BABEL_MEMORY, "malloc(buffered_updates): %s", + safe_strerror(errno)); + if(n > 4) { + /* Try again with a tiny buffer. */ + n = 4; + goto again; + } + return; + } + babel_ifp->update_bufsize = n; + babel_ifp->num_buffered_updates = 0; + } + + memcpy(babel_ifp->buffered_updates[babel_ifp->num_buffered_updates].prefix, + prefix, 16); + babel_ifp->buffered_updates[babel_ifp->num_buffered_updates].plen = plen; + babel_ifp->num_buffered_updates++; +} + +void +send_update(struct interface *ifp, int urgent, + const unsigned char *prefix, unsigned char plen) +{ + babel_interface_nfo *babel_ifp = NULL; + + if(ifp == NULL) { + 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 + need to do this now. */ + route = find_installed_route(prefix, plen); + if(route && route_metric(route) < INFINITY) + satisfy_request(prefix, plen, route->src->seqno, route->src->id, + NULL); + } + return; + } + + if(!if_up(ifp)) + return; + + babel_ifp = babel_get_if_nfo(ifp); + if(prefix) { + debugf(BABEL_DEBUG_COMMON,"Sending update to %s for %s.", + ifp->name, format_prefix(prefix, plen)); + buffer_update(ifp, prefix, plen); + } else { + 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 { + flog_err(EC_BABEL_MEMORY, "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); +} + +void +send_update_resend(struct interface *ifp, + const unsigned char *prefix, unsigned char plen) +{ + assert(prefix != NULL); + + send_update(ifp, 1, prefix, plen); + record_resend(RESEND_UPDATE, prefix, plen, 0, NULL, NULL, resend_delay); +} + +void +send_wildcard_retraction(struct interface *ifp) +{ + babel_interface_nfo *babel_ifp = NULL; + if(ifp == NULL) { + 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; + } + + if(!if_up(ifp)) + return; + + babel_ifp = babel_get_if_nfo(ifp); + start_message(ifp, MESSAGE_UPDATE, 10); + accumulate_byte(ifp, 0); + accumulate_byte(ifp, 0x40); + accumulate_byte(ifp, 0); + accumulate_byte(ifp, 0); + accumulate_short(ifp, 0xFFFF); + accumulate_short(ifp, myseqno); + accumulate_short(ifp, 0xFFFF); + end_message(ifp, MESSAGE_UPDATE, 10); + + babel_ifp->have_buffered_id = 0; +} + +void +update_myseqno(void) +{ + myseqno = seqno_plus(myseqno, 1); +} + +void +send_self_update(struct interface *ifp) +{ + struct xroute_stream *xroutes; + if(ifp == NULL) { + 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; + } + + 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 { + flog_err(EC_BABEL_MEMORY, "Couldn't allocate xroute stream."); + } +} + +void +send_ihu(struct neighbour *neigh, struct interface *ifp) +{ + babel_interface_nfo *babel_ifp = NULL; + int rxcost, interval; + int ll; + int send_rtt_data; + int msglen; + + if(neigh == NULL && ifp == NULL) { + 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); + } + return; + } + + if(neigh == NULL) { + struct neighbour *ngh; + FOR_ALL_NEIGHBOURS(ngh) { + if(ngh->ifp == ifp) + send_ihu(ngh, ifp); + } + return; + } + + + if(ifp && neigh->ifp != ifp) + return; + + ifp = neigh->ifp; + babel_ifp = babel_get_if_nfo(ifp); + if(!if_up(ifp)) + return; + + rxcost = neighbour_rxcost(neigh); + interval = (babel_ifp->hello_interval * 3 + 9) / 10; + + /* Conceptually, an IHU is a unicast message. We usually send them as + multicast, since this allows aggregation into a single packet and + avoids an ARP exchange. If we already have a unicast message queued + for this neighbour, however, we might as well piggyback the IHU. */ + debugf(BABEL_DEBUG_COMMON,"Sending %sihu %d on %s to %s.", + unicast_neighbour == neigh ? "unicast " : "", + rxcost, + neigh->ifp->name, + format_address(neigh->address)); + + 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, msglen); + accumulate_byte(ifp, ll ? 3 : 2); + accumulate_byte(ifp, 0); + accumulate_short(ifp, rxcost); + accumulate_short(ifp, interval); + if(ll) + accumulate_bytes(ifp, neigh->address + 8, 8); + else + accumulate_bytes(ifp, neigh->address, 16); + 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, msglen); + if(rc < 0) return; + accumulate_unicast_byte(neigh, ll ? 3 : 2); + accumulate_unicast_byte(neigh, 0); + accumulate_unicast_short(neigh, rxcost); + accumulate_unicast_short(neigh, interval); + if(ll) + accumulate_unicast_bytes(neigh, neigh->address + 8, 8); + else + accumulate_unicast_bytes(neigh, neigh->address, 16); + 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 IHUs to all marginal neighbours */ +void +send_marginal_ihu(struct interface *ifp) +{ + struct neighbour *neigh; + FOR_ALL_NEIGHBOURS(neigh) { + if(ifp && neigh->ifp != ifp) + continue; + if(neigh->txcost >= 384 || (neigh->reach & 0xF000) != 0xF000) + send_ihu(neigh, ifp); + } +} + +void +send_request(struct interface *ifp, + const unsigned char *prefix, unsigned char plen) +{ + int v4, pb, len; + + if(ifp == NULL) { + 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); + } + return; + } + + /* make sure any buffered updates go out before this request. */ + flushupdates(ifp); + + if(!if_up(ifp)) + return; + + debugf(BABEL_DEBUG_COMMON,"sending request to %s for %s.", + ifp->name, prefix ? format_prefix(prefix, plen) : "any"); + v4 = plen >= 96 && v4mapped(prefix); + 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, pb); + else + accumulate_bytes(ifp, prefix, pb); + } + end_message(ifp, MESSAGE_REQUEST, len); +} + +void +send_unicast_request(struct neighbour *neigh, + const unsigned char *prefix, unsigned char plen) +{ + int rc, v4, pb, len; + + /* make sure any buffered updates go out before this request. */ + flushupdates(neigh->ifp); + + debugf(BABEL_DEBUG_COMMON,"sending unicast request to %s for %s.", + format_address(neigh->address), + prefix ? format_prefix(prefix, plen) : "any"); + v4 = plen >= 96 && v4mapped(prefix); + 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 ? 1 : 2); + accumulate_unicast_byte(neigh, !prefix ? 0 : v4 ? plen - 96 : plen); + if(prefix) { + if(v4) + accumulate_unicast_bytes(neigh, prefix + 12, pb); + else + accumulate_unicast_bytes(neigh, prefix, pb); + } + end_unicast_message(neigh, MESSAGE_REQUEST, len); +} + +void +send_multihop_request(struct interface *ifp, + const unsigned char *prefix, unsigned char plen, + unsigned short seqno, const unsigned char *id, + unsigned short hop_count) +{ + int v4, pb, len; + + /* Make sure any buffered updates go out before this request. */ + flushupdates(ifp); + + if(ifp == NULL) { + 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); + } + return; + } + + if(!if_up(ifp)) + return; + + debugf(BABEL_DEBUG_COMMON,"Sending request (%d) on %s for %s.", + hop_count, ifp->name, format_prefix(prefix, plen)); + v4 = plen >= 96 && v4mapped(prefix); + pb = v4 ? ((plen - 96) + 7) / 8 : (plen + 7) / 8; + len = 6 + 8 + pb; + + start_message(ifp, MESSAGE_MH_REQUEST, len); + accumulate_byte(ifp, v4 ? 1 : 2); + accumulate_byte(ifp, v4 ? plen - 96 : plen); + accumulate_short(ifp, seqno); + accumulate_byte(ifp, hop_count); + accumulate_byte(ifp, 0); + accumulate_bytes(ifp, id, 8); + if(prefix) { + if(v4) + accumulate_bytes(ifp, prefix + 12, pb); + else + accumulate_bytes(ifp, prefix, pb); + } + end_message(ifp, MESSAGE_MH_REQUEST, len); +} + +void +send_unicast_multihop_request(struct neighbour *neigh, + const unsigned char *prefix, unsigned char plen, + unsigned short seqno, const unsigned char *id, + unsigned short hop_count) +{ + int rc, v4, pb, len; + + /* Make sure any buffered updates go out before this request. */ + flushupdates(neigh->ifp); + + debugf(BABEL_DEBUG_COMMON,"Sending multi-hop request to %s for %s (%d hops).", + format_address(neigh->address), + format_prefix(prefix, plen), hop_count); + v4 = plen >= 96 && v4mapped(prefix); + pb = v4 ? ((plen - 96) + 7) / 8 : (plen + 7) / 8; + len = 6 + 8 + pb; + + rc = start_unicast_message(neigh, MESSAGE_MH_REQUEST, len); + if(rc < 0) return; + accumulate_unicast_byte(neigh, v4 ? 1 : 2); + accumulate_unicast_byte(neigh, v4 ? plen - 96 : plen); + accumulate_unicast_short(neigh, seqno); + accumulate_unicast_byte(neigh, hop_count); + accumulate_unicast_byte(neigh, 0); + accumulate_unicast_bytes(neigh, id, 8); + if(prefix) { + if(v4) + accumulate_unicast_bytes(neigh, prefix + 12, pb); + else + accumulate_unicast_bytes(neigh, prefix, pb); + } + end_unicast_message(neigh, MESSAGE_MH_REQUEST, len); +} + +void +send_request_resend(struct neighbour *neigh, + const unsigned char *prefix, unsigned char plen, + unsigned short seqno, unsigned char *id) +{ + if(neigh) + send_unicast_multihop_request(neigh, prefix, plen, seqno, id, 127); + else + send_multihop_request(NULL, prefix, plen, seqno, id, 127); + + record_resend(RESEND_REQUEST, prefix, plen, seqno, id, + neigh ? neigh->ifp : NULL, resend_delay); +} + +void +handle_request(struct neighbour *neigh, const unsigned char *prefix, + unsigned char plen, unsigned char hop_count, + unsigned short seqno, const unsigned char *id) +{ + struct xroute *xroute; + struct babel_route *route; + struct neighbour *successor = NULL; + + xroute = find_xroute(prefix, plen); + route = find_installed_route(prefix, plen); + + if(xroute && (!route || xroute->metric <= kernel_metric)) { + if(hop_count > 0 && memcmp(id, myid, 8) == 0) { + if(seqno_compare(seqno, myseqno) > 0) { + if(seqno_minus(seqno, myseqno) > 100) { + /* Hopelessly out-of-date request */ + return; + } + update_myseqno(); + } + } + send_update(neigh->ifp, 1, prefix, plen); + return; + } + + if(route && + (memcmp(id, route->src->id, 8) != 0 || + seqno_compare(seqno, route->seqno) <= 0)) { + send_update(neigh->ifp, 1, prefix, plen); + return; + } + + if(hop_count <= 1) + return; + + if(route && memcmp(id, route->src->id, 8) == 0 && + seqno_minus(seqno, route->seqno) > 100) { + /* Hopelessly out-of-date */ + return; + } + + if(request_redundant(neigh->ifp, prefix, plen, seqno, id)) + return; + + /* Let's try to forward this request. */ + if(route && route_metric(route) < INFINITY) + successor = route->neigh; + + 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 babel_route *other_route; + + other_route = find_best_route(prefix, plen, 0, neigh); + if(other_route && route_metric(other_route) < INFINITY) + successor = other_route->neigh; + } + + if(!successor || successor == neigh) + /* Give up */ + return; + + send_unicast_multihop_request(successor, prefix, plen, seqno, id, + hop_count - 1); + record_resend(RESEND_REQUEST, prefix, plen, seqno, id, + neigh->ifp, 0); +} |