#include "utils.h"
#include "xalloc.h"
+#ifndef MAX
+#define MAX(a, b) ((a) > (b) ? (a) : (b))
+#endif
+
int keylifetime = 0;
#ifdef HAVE_LZO
static char lzo_wrkmem[LZO1X_999_MEM_COMPRESS > LZO1X_1_MEM_COMPRESS ? LZO1X_999_MEM_COMPRESS : LZO1X_1_MEM_COMPRESS];
unsigned replaywin = 16;
bool localdiscovery = true;
+bool udp_discovery = true;
+int udp_discovery_interval = 9;
+int udp_discovery_timeout = 30;
#define MAX_SEQNO 1073741824
-/* mtuprobes == 1..30: initial discovery, send bursts with 1 second interval
- mtuprobes == 31: sleep pinginterval seconds
- mtuprobes == 32: send 1 burst, sleep pingtimeout second
- mtuprobes == 33: no response from other side, restart PMTU discovery process
-
- Probes are sent in batches of at least three, with random sizes between the
- lower and upper boundaries for the MTU thus far discovered.
-
- After the initial discovery, a fourth packet is added to each batch with a
- size larger than the currently known PMTU, to test if the PMTU has increased.
-
- In case local discovery is enabled, another packet is added to each batch,
- which will be broadcast to the local network.
-
-*/
-
-static void send_mtu_probe_handler(void *data) {
- node_t *n = data;
- int timeout = 1;
-
- n->mtuprobes++;
-
- if(!n->status.reachable || !n->status.validkey) {
- logger(DEBUG_TRAFFIC, LOG_INFO, "Trying to send MTU probe to unreachable or rekeying node %s (%s)", n->name, n->hostname);
- n->mtuprobes = 0;
+static void try_fix_mtu(node_t *n) {
+ if(n->mtuprobes < 0)
return;
- }
-
- if(n->mtuprobes > 32) {
- if(!n->minmtu) {
- n->mtuprobes = 31;
- timeout = pinginterval;
- goto end;
- }
-
- logger(DEBUG_TRAFFIC, LOG_INFO, "%s (%s) did not respond to UDP ping, restarting PMTU discovery", n->name, n->hostname);
- n->status.udp_confirmed = false;
- n->mtuprobes = 1;
- n->minmtu = 0;
- n->maxmtu = MTU;
- }
-
- if(n->mtuprobes >= 10 && n->mtuprobes < 32 && !n->minmtu) {
- logger(DEBUG_TRAFFIC, LOG_INFO, "No response to MTU probes from %s (%s)", n->name, n->hostname);
- n->mtuprobes = 31;
- }
- if(n->mtuprobes == 30 || (n->mtuprobes < 30 && n->minmtu >= n->maxmtu)) {
+ if(n->mtuprobes == 20 || n->minmtu >= n->maxmtu) {
if(n->minmtu > n->maxmtu)
n->minmtu = n->maxmtu;
else
n->maxmtu = n->minmtu;
n->mtu = n->minmtu;
logger(DEBUG_TRAFFIC, LOG_INFO, "Fixing MTU of %s (%s) to %d after %d probes", n->name, n->hostname, n->mtu, n->mtuprobes);
- n->mtuprobes = 31;
+ n->mtuprobes = -1;
}
-
- if(n->mtuprobes == 31) {
- timeout = pinginterval;
- goto end;
- } else if(n->mtuprobes == 32) {
- timeout = pingtimeout;
- }
-
- for(int i = 0; i < 4 + localdiscovery; i++) {
- int len;
-
- if(i == 0) {
- if(n->mtuprobes < 30 || n->maxmtu + 8 >= MTU)
- continue;
- len = n->maxmtu + 8;
- } else if(n->maxmtu <= n->minmtu) {
- len = n->maxmtu;
- } else {
- len = n->minmtu + 1 + rand() % (n->maxmtu - n->minmtu);
- }
-
- if(len < 64)
- len = 64;
-
- vpn_packet_t packet;
- packet.offset = DEFAULT_PACKET_OFFSET;
- memset(DATA(&packet), 0, 14);
- randomize(DATA(&packet) + 14, len - 14);
- packet.len = len;
- packet.priority = 0;
- n->status.send_locally = i >= 4 && n->mtuprobes <= 10 && n->prevedge;
-
- logger(DEBUG_TRAFFIC, LOG_INFO, "Sending MTU probe length %d to %s (%s)", len, n->name, n->hostname);
-
- send_udppacket(n, &packet);
- }
-
- n->status.send_locally = false;
- n->probe_counter = 0;
- gettimeofday(&n->probe_time, NULL);
-
- /* Calculate the packet loss of incoming traffic by comparing the rate of
- packets received to the rate with which the sequence number has increased.
- */
-
- if(n->received > n->prev_received)
- n->packetloss = 1.0 - (n->received - n->prev_received) / (float)(n->received_seqno - n->prev_received_seqno);
- else
- n->packetloss = n->received_seqno <= n->prev_received_seqno;
-
- n->prev_received_seqno = n->received_seqno;
- n->prev_received = n->received;
-
-end:
- timeout_set(&n->mtutimeout, &(struct timeval){timeout, rand() % 100000});
}
-void send_mtu_probe(node_t *n) {
- timeout_add(&n->mtutimeout, send_mtu_probe_handler, n, &(struct timeval){1, 0});
- send_mtu_probe_handler(n);
+static void udp_probe_timeout_handler(void *data) {
+ node_t *n = data;
+ if(!n->status.udp_confirmed)
+ return;
+
+ logger(DEBUG_TRAFFIC, LOG_INFO, "Too much time has elapsed since last UDP ping response from %s (%s), stopping UDP communication", n->name, n->hostname);
+ n->status.udp_confirmed = false;
+ n->mtuprobes = 0;
+ n->minmtu = 0;
+ n->maxmtu = MTU;
}
-static void mtu_probe_h(node_t *n, vpn_packet_t *packet, length_t len) {
+static void udp_probe_h(node_t *n, vpn_packet_t *packet, length_t len) {
if(!DATA(packet)[0]) {
- logger(DEBUG_TRAFFIC, LOG_INFO, "Got MTU probe request %d from %s (%s)", packet->len, n->name, n->hostname);
+ logger(DEBUG_TRAFFIC, LOG_INFO, "Got UDP probe request %d from %s (%s)", packet->len, n->name, n->hostname);
/* It's a probe request, send back a reply */
length_t probelen = len;
if (DATA(packet)[0] == 2) {
if (len < 3)
- logger(DEBUG_TRAFFIC, LOG_WARNING, "Received invalid (too short) MTU probe reply from %s (%s)", n->name, n->hostname);
+ logger(DEBUG_TRAFFIC, LOG_WARNING, "Received invalid (too short) UDP probe reply from %s (%s)", n->name, n->hostname);
else {
uint16_t probelen16; memcpy(&probelen16, DATA(packet) + 1, 2); probelen = ntohs(probelen16);
}
}
- logger(DEBUG_TRAFFIC, LOG_INFO, "Got type %d MTU probe reply %d from %s (%s)", DATA(packet)[0], probelen, n->name, n->hostname);
+ logger(DEBUG_TRAFFIC, LOG_INFO, "Got type %d UDP probe reply %d from %s (%s)", DATA(packet)[0], probelen, n->name, n->hostname);
/* It's a valid reply: now we know bidirectional communication
is possible using the address and socket that the reply
packet used. */
-
n->status.udp_confirmed = true;
- /* If we haven't established the PMTU yet, restart the discovery process. */
-
- if(n->mtuprobes > 30) {
- if (probelen == n->maxmtu + 8) {
- logger(DEBUG_TRAFFIC, LOG_INFO, "Increase in PMTU to %s (%s) detected, restarting PMTU discovery", n->name, n->hostname);
- n->maxmtu = MTU;
- n->mtuprobes = 10;
- return;
- }
+ if(udp_discovery) {
+ timeout_del(&n->udp_ping_timeout);
+ timeout_add(&n->udp_ping_timeout, &udp_probe_timeout_handler, n, &(struct timeval){udp_discovery_timeout, 0});
+ }
- if(n->minmtu)
- n->mtuprobes = 30;
- else
- n->mtuprobes = 1;
+ if(probelen >= n->maxmtu + 1) {
+ logger(DEBUG_TRAFFIC, LOG_INFO, "Increase in PMTU to %s (%s) detected, restarting PMTU discovery", n->name, n->hostname);
+ n->maxmtu = MTU;
+ n->mtuprobes = 0;
+ return;
}
/* If applicable, raise the minimum supported MTU */
if(probelen > n->maxmtu)
probelen = n->maxmtu;
- if(n->minmtu < probelen)
+ if(n->minmtu < probelen) {
n->minmtu = probelen;
+ try_fix_mtu(n);
+ }
- /* Calculate RTT and bandwidth.
+ /* Calculate RTT.
The RTT is the time between the MTU probe burst was sent and the first
- reply is received. The bandwidth is measured using the time between the
- arrival of the first and third probe reply (or type 2 probe requests).
+ reply is received.
*/
struct timeval now, diff;
if(n->probe_counter == 1) {
n->rtt = diff.tv_sec + diff.tv_usec * 1e-6;
n->probe_time = probe_timestamp;
- } else if(n->probe_counter == 3) {
- struct timeval probe_timestamp_diff;
- timersub(&probe_timestamp, &n->probe_time, &probe_timestamp_diff);
- n->bandwidth = 2.0 * probelen / (probe_timestamp_diff.tv_sec + probe_timestamp_diff.tv_usec * 1e-6);
- logger(DEBUG_TRAFFIC, LOG_DEBUG, "%s (%s) RTT %.2f ms, burst bandwidth %.3f Mbit/s, rx packet loss %.2f %%", n->name, n->hostname, n->rtt * 1e3, n->bandwidth * 8e-6, n->packetloss * 1e2);
+ logger(DEBUG_TRAFFIC, LOG_DEBUG, "%s (%s) RTT %.2f ms, rx packet loss %.2f %%", n->name, n->hostname, n->rtt * 1e3, n->packetloss * 1e2);
}
}
}
if(n->status.sptps)
return sptps_verify_datagram(&n->sptps, DATA(inpkt), inpkt->len);
+#ifdef DISABLE_LEGACY
+ return false;
+#else
if(!digest_active(n->indigest) || inpkt->len < sizeof(seqno_t) + digest_length(n->indigest))
return false;
return digest_verify(n->indigest, SEQNO(inpkt), inpkt->len - digest_length(n->indigest), DATA(inpkt) + inpkt->len - digest_length(n->indigest));
+#endif
}
static bool receive_udppacket(node_t *n, vpn_packet_t *inpkt) {
return true;
}
+#ifdef DISABLE_LEGACY
+ return false;
+#else
if(!n->status.validkey) {
logger(DEBUG_TRAFFIC, LOG_DEBUG, "Got packet from %s (%s) but he hasn't got our key yet", n->name, n->hostname);
return false;
inpkt->priority = 0;
if(!DATA(inpkt)[12] && !DATA(inpkt)[13])
- mtu_probe_h(n, inpkt, origlen);
+ udp_probe_h(n, inpkt, origlen);
else
receive_packet(n, inpkt);
return true;
+#endif
}
void receive_tcppacket(connection_t *c, const char *buffer, int len) {
receive_packet(c->node, &outpkt);
}
-static bool try_sptps(node_t *n) {
- if(n->status.validkey)
- return true;
-
- logger(DEBUG_TRAFFIC, LOG_INFO, "No valid key known yet for %s (%s)", n->name, n->hostname);
-
- if(!n->status.waitingforkey)
- send_req_key(n);
- else if(n->last_req_key + 10 < now.tv_sec) {
- logger(DEBUG_ALWAYS, LOG_DEBUG, "No key from %s after 10 seconds, restarting SPTPS", n->name);
- sptps_stop(&n->sptps);
- n->status.waitingforkey = false;
- send_req_key(n);
- }
-
- return false;
-}
-
static void send_sptps_packet(node_t *n, vpn_packet_t *origpkt) {
- if (!try_sptps(n))
+ if(!n->status.validkey && !n->connection)
return;
uint8_t type = 0;
}
}
- sptps_send_record(&n->sptps, type, DATA(origpkt) + offset, origpkt->len - offset);
+ /* If we have a direct metaconnection to n, and we can't use UDP, then
+ don't bother with SPTPS and just use a "plaintext" PACKET message.
+ We don't really care about end-to-end security since we're not
+ sending the message through any intermediate nodes. */
+ if(n->connection && origpkt->len > n->minmtu)
+ send_tcppacket(n->connection, origpkt);
+ else
+ sptps_send_record(&n->sptps, type, DATA(origpkt) + offset, origpkt->len - offset);
return;
}
if(n->status.sptps)
return send_sptps_packet(n, origpkt);
+#ifdef DISABLE_LEGACY
+ return;
+#else
/* Make sure we have a valid key */
if(!n->status.validkey) {
logger(DEBUG_TRAFFIC, LOG_INFO,
"No valid key known yet for %s (%s), forwarding via TCP",
n->name, n->hostname);
-
- if(n->last_req_key + 10 <= now.tv_sec) {
- send_req_key(n);
- n->last_req_key = now.tv_sec;
- }
-
send_tcppacket(n->nexthop->connection, origpkt);
-
return;
}
n->maxmtu = origlen - 1;
if(n->mtu >= origlen)
n->mtu = origlen - 1;
+ try_fix_mtu(n);
} else
logger(DEBUG_TRAFFIC, LOG_WARNING, "Error sending packet to %s (%s): %s", n->name, n->hostname, sockstrerror(sockerrno));
}
end:
origpkt->len = origlen;
+#endif
}
static bool send_sptps_data_priv(node_t *to, node_t *from, int type, const void *data, size_t len) {
bool relay_supported = (relay->options >> 24) >= 4;
bool tcponly = (myself->options | relay->options) & OPTION_TCPONLY;
- /* We don't really need the relay's key, but we need to establish a UDP tunnel with it and discover its MTU. */
- if (!direct && relay_supported && !tcponly)
- try_sptps(relay);
-
/* Send it via TCP if it is a handshake packet, TCPOnly is in use, this is a relay packet that the other node cannot understand, or this packet is larger than the MTU.
TODO: When relaying, the original sender does not know the end-to-end PMTU (it only knows the PMTU of the first hop).
This can lead to scenarios where large packets are sent over UDP to relay, but then relay has no choice but fall back to TCP. */
relay->maxmtu = len - 1;
if(relay->mtu >= len)
relay->mtu = len - 1;
+ try_fix_mtu(relay);
} else {
logger(DEBUG_TRAFFIC, LOG_WARNING, "Error sending UDP SPTPS packet to %s (%s): %s", relay->name, relay->hostname, sockstrerror(sockerrno));
return false;
if(type == PKT_PROBE) {
inpkt.len = len;
memcpy(DATA(&inpkt), data, len);
- mtu_probe_h(from, &inpkt, len);
+ udp_probe_h(from, &inpkt, len);
return true;
}
return true;
}
+// This function tries to get SPTPS keys, if they aren't already known.
+// This function makes no guarantees - it is up to the caller to check the node's state to figure out if the keys are available.
+static void try_sptps(node_t *n) {
+ if(n->status.validkey)
+ return;
+
+ logger(DEBUG_TRAFFIC, LOG_INFO, "No valid key known yet for %s (%s)", n->name, n->hostname);
+
+ if(!n->status.waitingforkey)
+ send_req_key(n);
+ else if(n->last_req_key + 10 < now.tv_sec) {
+ logger(DEBUG_ALWAYS, LOG_DEBUG, "No key from %s after 10 seconds, restarting SPTPS", n->name);
+ sptps_stop(&n->sptps);
+ n->status.waitingforkey = false;
+ send_req_key(n);
+ }
+
+ return;
+}
+
+static void send_udp_probe_packet(node_t *n, int len) {
+ vpn_packet_t packet;
+ packet.offset = DEFAULT_PACKET_OFFSET;
+ memset(DATA(&packet), 0, 14);
+ randomize(DATA(&packet) + 14, len - 14);
+ packet.len = len;
+ packet.priority = 0;
+
+ logger(DEBUG_TRAFFIC, LOG_INFO, "Sending UDP probe length %d to %s (%s)", len, n->name, n->hostname);
+
+ send_udppacket(n, &packet);
+}
+
+// This function tries to establish a UDP tunnel to a node so that packets can be sent.
+// If a tunnel is already established, it makes sure it stays up.
+// This function makes no guarantees - it is up to the caller to check the node's state to figure out if UDP is usable.
+static void try_udp(node_t* n) {
+ if(!udp_discovery)
+ return;
+
+ struct timeval now;
+ gettimeofday(&now, NULL);
+ struct timeval ping_tx_elapsed;
+ timersub(&now, &n->udp_ping_sent, &ping_tx_elapsed);
+
+ if(ping_tx_elapsed.tv_sec >= udp_discovery_interval) {
+ send_udp_probe_packet(n, MAX(n->minmtu, 16));
+ n->udp_ping_sent = now;
+
+ if(localdiscovery && !n->status.udp_confirmed && n->prevedge) {
+ n->status.send_locally = true;
+ send_udp_probe_packet(n, 16);
+ n->status.send_locally = false;
+ }
+ }
+}
+
+// This function tries to determines the MTU of a node.
+// By calling this function repeatedly, n->minmtu will be progressively increased, and at some point, n->mtu will be fixed to n->minmtu.
+// If the MTU is already fixed, this function checks if it can be increased.
+static void try_mtu(node_t *n) {
+ if(!(n->options & OPTION_PMTU_DISCOVERY))
+ return;
+
+ if(udp_discovery && !n->status.udp_confirmed) {
+ n->mtuprobes = 0;
+ n->minmtu = 0;
+ n->maxmtu = MTU;
+ return;
+ }
+
+ /* mtuprobes == 0..19: initial discovery, send bursts with 1 second interval, mtuprobes++
+ mtuprobes == 20: fix MTU, and go to -1
+ mtuprobes == -1: send one >maxmtu probe every pingtimeout */
+
+ struct timeval now;
+ gettimeofday(&now, NULL);
+ struct timeval elapsed;
+ timersub(&now, &n->probe_sent_time, &elapsed);
+ if(n->mtuprobes >= 0) {
+ if(n->mtuprobes != 0 && elapsed.tv_sec == 0 && elapsed.tv_usec < 333333)
+ return;
+ } else {
+ if(elapsed.tv_sec < pingtimeout)
+ return;
+ }
+
+ try_fix_mtu(n);
+
+ int timeout;
+ if(n->mtuprobes < 0) {
+ /* After the initial discovery, we only send one >maxmtu probe
+ to detect PMTU increases. */
+ if(n->maxmtu + 1 < MTU)
+ send_udp_probe_packet(n, n->maxmtu + 1);
+ } else {
+ /* Decreasing the number of probes per cycle might make the algorithm react faster to lost packets,
+ but it will typically increase convergence time in the no-loss case. */
+ const length_t probes_per_cycle = 8;
+
+ /* This magic value was determined using math simulations.
+ It will result in a 1329-byte first probe, followed (if there was a reply) by a 1407-byte probe.
+ Since 1407 is just below the range of tinc MTUs over typical networks,
+ this fine-tuning allows tinc to cover a lot of ground very quickly. */
+ const float multiplier = 0.97;
+
+ const float cycle_position = probes_per_cycle - (n->mtuprobes % probes_per_cycle) - 1;
+ const length_t minmtu = MAX(n->minmtu, 512);
+ const float interval = n->maxmtu - minmtu;
+
+ /* The core of the discovery algorithm is this exponential.
+ It produces very large probes early in the cycle, and then it very quickly decreases the probe size.
+ This reflects the fact that in the most difficult cases, we don't get any feedback for probes that
+ are too large, and therefore we need to concentrate on small offsets so that we can quickly converge
+ on the precise MTU as we are approaching it.
+ The last probe of the cycle is always 1 byte in size - this is to make sure we'll get at least one
+ reply per cycle so that we can make progress. */
+ const length_t offset = powf(interval, multiplier * cycle_position / (probes_per_cycle - 1));
+
+ send_udp_probe_packet(n, minmtu + offset);
+ if(n->mtuprobes >= 0)
+ n->mtuprobes++;
+ }
+
+ n->probe_counter = 0;
+ n->probe_sent_time = now;
+ n->probe_time = now;
+
+ /* Calculate the packet loss of incoming traffic by comparing the rate of
+ packets received to the rate with which the sequence number has increased.
+ TODO: this is unrelated to PMTU discovery - it should be moved elsewhere.
+ */
+
+ if(n->received > n->prev_received)
+ n->packetloss = 1.0 - (n->received - n->prev_received) / (float)(n->received_seqno - n->prev_received_seqno);
+ else
+ n->packetloss = n->received_seqno <= n->prev_received_seqno;
+
+ n->prev_received_seqno = n->received_seqno;
+ n->prev_received = n->received;
+}
+
+// This function tries to establish a tunnel to a node (or its relay) so that packets can be sent (e.g. get SPTPS keys).
+// If a tunnel is already established, it tries to improve it (e.g. by trying to establish a UDP tunnel instead of TCP).
+// This function makes no guarantees - it is up to the caller to check the node's state to figure out if TCP and/or UDP is usable.
+// By calling this function repeatedly, the tunnel is gradually improved until we hit the wall imposed by the underlying network environment.
+// It is recommended to call this function every time a packet is sent (or intended to be sent) to a node,
+// so that the tunnel keeps improving as packets flow, and then gracefully downgrades itself as it goes idle.
+static void try_tx(node_t *n) {
+ /* If n is a TCP-only neighbor, we'll only use "cleartext" PACKET
+ messages anyway, so there's no need for SPTPS at all. Otherwise, get the keys. */
+ if(n->status.sptps && !(n->connection && ((myself->options | n->options) & OPTION_TCPONLY))) {
+ try_sptps(n);
+ if (!n->status.validkey)
+ return;
+ }
+
+ node_t *via = (n->via == myself) ? n->nexthop : n->via;
+
+ if((myself->options | via->options) & OPTION_TCPONLY)
+ return;
+
+ if(!n->status.sptps && !via->status.validkey && via->last_req_key + 10 <= now.tv_sec) {
+ send_req_key(via);
+ via->last_req_key = now.tv_sec;
+ } else if(via == n || !n->status.sptps || (via->options >> 24) >= 4) {
+ try_udp(via);
+ try_mtu(via);
+ }
+
+ /* If we don't know how to reach "via" yet, then try to reach it through a relay. */
+ if(n->status.sptps && !via->status.udp_confirmed && via->nexthop != via && (via->nexthop->options >> 24) >= 4)
+ try_tx(via->nexthop);
+}
+
/*
send a packet to the given vpn ip.
*/
if(n->status.sptps) {
send_sptps_packet(n, packet);
- return;
+ goto end;
}
via = (packet->priority == -1 || n->via == myself) ? n->nexthop : n->via;
terminate_connection(via->connection, true);
} else
send_udppacket(via, packet);
+
+end:
+ /* Try to improve the tunnel.
+ Note that we do this *after* we send the packet because sending actual packets take priority
+ with regard to the send buffer space and latency. */
+ try_tx(n);
}
/* Broadcast a packet using the minimum spanning tree */
projects / tinc / blobdiff