// 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
#define RESERVED	0
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 <= 3;
}

static inline bool is_all_zero(const unsigned char *data, int len)
{
	for (int j = 0; j < len; j++) {
		if (data[j] != 0) {
			return false;
		}
	}
	return true;
}

/*
 * 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 (CHECK_FLAG(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) {
			if (!is_all_zero(a + i + 2, len)) {
				debugf(BABEL_DEBUG_COMMON,
				       "Received pad%d with non zero MBZ field.", len);
			}
		} 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 (CHECK_FLAG(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) {
			if (!is_all_zero(a + i + 2, len)) {
				debugf(BABEL_DEBUG_COMMON,
				       "Received pad%d with non zero MBZ field.", len);
			}
		} 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) {
			if (!is_all_zero(a + i + 2, len)) {
				debugf(BABEL_DEBUG_COMMON,
				       "Received pad%d with non zero MBZ field.", len);
			}
		} 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[i];
		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.",
			       (CHECK_FLAG(type, 0x80) != 0) ? " mandatory" : "", type);
			if (CHECK_FLAG(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 (CHECK_FLAG(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;
	}

	if (v4mapped(from)) {
		memcpy(v4_nh, from, 16);
		have_v4_nh = 1;
	} else {
		memcpy(v6_nh, from, 16);
		have_v6_nh = 1;
	}

	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) {
			if (!is_all_zero(message + 2, len)) {
				debugf(BABEL_DEBUG_COMMON,
				       "Received pad%d with non zero MBZ field.", len);
			}
			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, Reserved;
			DO_NTOHS(Reserved, message + 2);
			DO_NTOHS(nonce, message + 4);
			DO_NTOHS(interval, message + 6);
			if (Reserved != RESERVED) {
				debugf(BABEL_DEBUG_COMMON,
				       "Received ack-req (%04X %d) with non zero Reserved from %s on %s.",
				       nonce, interval, format_address(from), ifp->name);
				goto done;
			}
			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, &timestamp) > 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 Reserved;
			unsigned char address[16];
			int rc;
			Reserved = message[3];
			if (Reserved != RESERVED) {
				debugf(BABEL_DEBUG_COMMON,
				       "Received ihu with non zero Reserved from %s on %s.",
				       format_address(from), ifp->name);
				goto done;
			}
			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;
			if (message[2] != 1 && message[2] != 3) {
				debugf(BABEL_DEBUG_COMMON, "Received NH with incorrect AE %d.",
				       message[2]);
				have_v4_nh = 0;
				have_v6_nh = 0;
				goto fail;
			}
			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;

			// Basic sanity check on length
			if (len < 10) {
				if (len < 2 || (message[3] & 0x80)) {
					have_v4_prefix = have_v6_prefix = 0;
				}
				goto fail;
			}

			if (!known_ae(message[2])) {
				debugf(BABEL_DEBUG_COMMON,
				       "Received update with unknown AE %d. Ignoring.", message[2]);
				goto done;
			}

			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 (CHECK_FLAG(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 (CHECK_FLAG(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 (CHECK_FLAG(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 (metric < INFINITY && !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.",
			       ((CHECK_FLAG(message[3], 0x80)) ? "/prefix" : ""),
			       ((CHECK_FLAG(message[3], 0x40)) ? "/id" : ""),
			       format_prefix(prefix, plen), format_address(from), ifp->name);

			if (message[2] == 0) {
				if (metric < INFINITY) {
					flog_err(EC_BABEL_PACKET,
						 "Received wildcard update with finite metric.");
					goto done;
				}
				// Add check for Plen and Omitted
				if (message[4] != 0 || message[5] != 0) {
					flog_err(EC_BABEL_PACKET,
						 "Received wildcard retraction with non-zero Plen or Omitted.");
					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 (CHECK_FLAG(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;
			}
			if (message[6] == 0) {
				debugf(BABEL_DEBUG_COMMON,
				       "Received seqno request with invalid hop count 0");
				goto done;
			}
			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 (message[3] != 0) {
					flog_err(EC_BABEL_PACKET,
						 "Ignoring request with AE=0 and non-zero Plen");
					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, Reserved;
			unsigned short seqno;
			Reserved = message[7];
			if (Reserved != RESERVED) {
				debugf(BABEL_DEBUG_COMMON,
				       "Received request with non zero Reserved from %s on %s.",
				       format_address(from), ifp->name);
				goto done;
			}
			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);
			if (message[6] == 0) {
				debugf(BABEL_DEBUG_COMMON,
				       "Received request with invalid hop count 0");
				goto done;
			}
			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;
	}
}

/* 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 (CHECK_FLAG(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;
		}

		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,
		      (CHECK_FLAG(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 (CHECK_FLAG(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, CHECK_FLAG(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)
			SET_FLAG(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) {
			SET_FLAG(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 (CHECK_FLAG(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 (CHECK_FLAG(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 (CHECK_FLAG(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 || CHECK_FLAG(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;
		/* First try feasible routes as required by RFC */
		other_route = find_best_route(prefix, plen, 1, neigh);

		if (!other_route || route_metric(other_route) >= INFINITY) {
			/* If no feasible route found, try non-feasible routes */
			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);
}