Added comments and unfold deep "if"-construct in timeout_handler
[tinc] / src / net_packet.c
1 /*
2     net_packet.c -- Handles in- and outgoing VPN packets
3     Copyright (C) 1998-2005 Ivo Timmermans,
4                   2000-2016 Guus Sliepen <guus@tinc-vpn.org>
5                   2010      Timothy Redaelli <timothy@redaelli.eu>
6                   2010      Brandon Black <blblack@gmail.com>
7
8     This program is free software; you can redistribute it and/or modify
9     it under the terms of the GNU General Public License as published by
10     the Free Software Foundation; either version 2 of the License, or
11     (at your option) any later version.
12
13     This program is distributed in the hope that it will be useful,
14     but WITHOUT ANY WARRANTY; without even the implied warranty of
15     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16     GNU General Public License for more details.
17
18     You should have received a copy of the GNU General Public License along
19     with this program; if not, write to the Free Software Foundation, Inc.,
20     51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
21 */
22
23 #include "system.h"
24
25 #ifdef HAVE_ZLIB
26 #include <zlib.h>
27 #endif
28
29 #ifdef HAVE_LZO
30 #include LZO1X_H
31 #endif
32
33 #include "cipher.h"
34 #include "conf.h"
35 #include "connection.h"
36 #include "crypto.h"
37 #include "digest.h"
38 #include "device.h"
39 #include "ethernet.h"
40 #include "ipv4.h"
41 #include "ipv6.h"
42 #include "graph.h"
43 #include "logger.h"
44 #include "net.h"
45 #include "netutl.h"
46 #include "protocol.h"
47 #include "route.h"
48 #include "utils.h"
49 #include "xalloc.h"
50
51 #ifndef MAX
52 #define MAX(a, b) ((a) > (b) ? (a) : (b))
53 #endif
54
55 /* The minimum size of a probe is 14 bytes, but since we normally use CBC mode
56    encryption, we can add a few extra random bytes without increasing the
57    resulting packet size. */
58 #define MIN_PROBE_SIZE 18
59
60 int keylifetime = 0;
61 #ifdef HAVE_LZO
62 static char lzo_wrkmem[LZO1X_999_MEM_COMPRESS > LZO1X_1_MEM_COMPRESS ? LZO1X_999_MEM_COMPRESS : LZO1X_1_MEM_COMPRESS];
63 #endif
64
65 static void send_udppacket(node_t *, vpn_packet_t *);
66
67 unsigned replaywin = 32;
68 bool localdiscovery = true;
69 bool udp_discovery = true;
70 int udp_discovery_keepalive_interval = 10;
71 int udp_discovery_interval = 2;
72 int udp_discovery_timeout = 30;
73
74 #define MAX_SEQNO 1073741824
75
76 static void try_fix_mtu(node_t *n) {
77         if(n->mtuprobes < 0)
78                 return;
79
80         if(n->mtuprobes == 20 || n->minmtu >= n->maxmtu) {
81                 if(n->minmtu > n->maxmtu)
82                         n->minmtu = n->maxmtu;
83                 else
84                         n->maxmtu = n->minmtu;
85                 n->mtu = n->minmtu;
86                 logger(DEBUG_TRAFFIC, LOG_INFO, "Fixing MTU of %s (%s) to %d after %d probes", n->name, n->hostname, n->mtu, n->mtuprobes);
87                 n->mtuprobes = -1;
88         }
89 }
90
91 static void udp_probe_timeout_handler(void *data) {
92         node_t *n = data;
93         if(!n->status.udp_confirmed)
94                 return;
95
96         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);
97         n->status.udp_confirmed = false;
98         n->maxrecentlen = 0;
99         n->mtuprobes = 0;
100         n->minmtu = 0;
101         n->maxmtu = MTU;
102 }
103
104 static void send_udp_probe_reply(node_t *n, vpn_packet_t *packet, length_t len) {
105         if(!n->status.sptps && !n->status.validkey) {
106                 logger(DEBUG_TRAFFIC, LOG_INFO, "Trying to send UDP probe reply to %s (%s) but we don't have his key yet", n->name, n->hostname);
107                 return;
108         }
109
110         /* Type 2 probe replies were introduced in protocol 17.3 */
111         if ((n->options >> 24) >= 3) {
112                 DATA(packet)[0] = 2;
113                 uint16_t len16 = htons(len);
114                 memcpy(DATA(packet) + 1, &len16, 2);
115                 packet->len = MIN_PROBE_SIZE;
116                 logger(DEBUG_TRAFFIC, LOG_INFO, "Sending type 2 probe reply length %u to %s (%s)", len, n->name, n->hostname);
117
118         } else {
119                 /* Legacy protocol: n won't understand type 2 probe replies. */
120                 DATA(packet)[0] = 1;
121                 logger(DEBUG_TRAFFIC, LOG_INFO, "Sending type 1 probe reply length %u to %s (%s)", len, n->name, n->hostname);
122         }
123
124         /* Temporarily set udp_confirmed, so that the reply is sent
125            back exactly the way it came in. */
126
127         bool udp_confirmed = n->status.udp_confirmed;
128         n->status.udp_confirmed = true;
129         send_udppacket(n, packet);
130         n->status.udp_confirmed = udp_confirmed;
131 }
132
133 static void udp_probe_h(node_t *n, vpn_packet_t *packet, length_t len) {
134         if(!DATA(packet)[0]) {
135                 logger(DEBUG_TRAFFIC, LOG_INFO, "Got UDP probe request %d from %s (%s)", packet->len, n->name, n->hostname);
136                 return send_udp_probe_reply(n, packet, len);
137         }
138
139         if (DATA(packet)[0] == 2) {
140                 // It's a type 2 probe reply, use the length field inside the packet
141                 uint16_t len16;
142                 memcpy(&len16, DATA(packet) + 1, 2);
143                 len = ntohs(len16);
144         }
145
146         logger(DEBUG_TRAFFIC, LOG_INFO, "Got type %d UDP probe reply %d from %s (%s)", DATA(packet)[0], len, n->name, n->hostname);
147
148         /* It's a valid reply: now we know bidirectional communication
149            is possible using the address and socket that the reply
150            packet used. */
151         n->status.udp_confirmed = true;
152
153         // Reset the UDP ping timer.
154         n->udp_ping_sent = now;
155
156         if(udp_discovery) {
157                 timeout_del(&n->udp_ping_timeout);
158                 timeout_add(&n->udp_ping_timeout, &udp_probe_timeout_handler, n, &(struct timeval){udp_discovery_timeout, 0});
159         }
160
161         if(len > n->maxmtu) {
162                 logger(DEBUG_TRAFFIC, LOG_INFO, "Increase in PMTU to %s (%s) detected, restarting PMTU discovery", n->name, n->hostname);
163                 n->minmtu = len;
164                 n->maxmtu = MTU;
165                 /* Set mtuprobes to 1 so that try_mtu() doesn't reset maxmtu */
166                 n->mtuprobes = 1;
167                 return;
168         } else if(n->mtuprobes < 0 && len == n->maxmtu) {
169                 /* We got a maxmtu sized packet, confirming the PMTU is still valid. */
170                 n->mtuprobes = -1;
171                 n->mtu_ping_sent = now;
172         }
173
174         /* If applicable, raise the minimum supported MTU */
175
176         if(n->minmtu < len) {
177                 n->minmtu = len;
178                 try_fix_mtu(n);
179         }
180 }
181
182 static length_t compress_packet(uint8_t *dest, const uint8_t *source, length_t len, int level) {
183         if(level == 0) {
184                 memcpy(dest, source, len);
185                 return len;
186         } else if(level == 10) {
187 #ifdef HAVE_LZO
188                 lzo_uint lzolen = MAXSIZE;
189                 lzo1x_1_compress(source, len, dest, &lzolen, lzo_wrkmem);
190                 return lzolen;
191 #else
192                 return -1;
193 #endif
194         } else if(level < 10) {
195 #ifdef HAVE_ZLIB
196                 unsigned long destlen = MAXSIZE;
197                 if(compress2(dest, &destlen, source, len, level) == Z_OK)
198                         return destlen;
199                 else
200 #endif
201                         return -1;
202         } else {
203 #ifdef HAVE_LZO
204                 lzo_uint lzolen = MAXSIZE;
205                 lzo1x_999_compress(source, len, dest, &lzolen, lzo_wrkmem);
206                 return lzolen;
207 #else
208                 return -1;
209 #endif
210         }
211
212         return -1;
213 }
214
215 static length_t uncompress_packet(uint8_t *dest, const uint8_t *source, length_t len, int level) {
216         if(level == 0) {
217                 memcpy(dest, source, len);
218                 return len;
219         } else if(level > 9) {
220 #ifdef HAVE_LZO
221                 lzo_uint lzolen = MAXSIZE;
222                 if(lzo1x_decompress_safe(source, len, dest, &lzolen, NULL) == LZO_E_OK)
223                         return lzolen;
224                 else
225 #endif
226                         return -1;
227         }
228 #ifdef HAVE_ZLIB
229         else {
230                 unsigned long destlen = MAXSIZE;
231                 if(uncompress(dest, &destlen, source, len) == Z_OK)
232                         return destlen;
233                 else
234                         return -1;
235         }
236 #endif
237
238         return -1;
239 }
240
241 /* VPN packet I/O */
242
243 static void receive_packet(node_t *n, vpn_packet_t *packet) {
244         logger(DEBUG_TRAFFIC, LOG_DEBUG, "Received packet of %d bytes from %s (%s)",
245                            packet->len, n->name, n->hostname);
246
247         n->in_packets++;
248         n->in_bytes += packet->len;
249
250         route(n, packet);
251 }
252
253 static bool try_mac(node_t *n, const vpn_packet_t *inpkt) {
254         if(n->status.sptps)
255                 return sptps_verify_datagram(&n->sptps, DATA(inpkt), inpkt->len);
256
257 #ifdef DISABLE_LEGACY
258         return false;
259 #else
260         if(!n->status.validkey_in || !digest_active(n->indigest) || inpkt->len < sizeof(seqno_t) + digest_length(n->indigest))
261                 return false;
262
263         return digest_verify(n->indigest, inpkt->data, inpkt->len - digest_length(n->indigest), inpkt->data + inpkt->len - digest_length(n->indigest));
264 #endif
265 }
266
267 static bool receive_udppacket(node_t *n, vpn_packet_t *inpkt) {
268         vpn_packet_t pkt1, pkt2;
269         vpn_packet_t *pkt[] = { &pkt1, &pkt2, &pkt1, &pkt2 };
270         int nextpkt = 0;
271         size_t outlen;
272         pkt1.offset = DEFAULT_PACKET_OFFSET;
273         pkt2.offset = DEFAULT_PACKET_OFFSET;
274
275         if(n->status.sptps) {
276                 if(!n->sptps.state) {
277                         if(!n->status.waitingforkey) {
278                                 logger(DEBUG_TRAFFIC, LOG_DEBUG, "Got packet from %s (%s) but we haven't exchanged keys yet", n->name, n->hostname);
279                                 send_req_key(n);
280                         } else {
281                                 logger(DEBUG_TRAFFIC, LOG_DEBUG, "Got packet from %s (%s) but he hasn't got our key yet", n->name, n->hostname);
282                         }
283                         return false;
284                 }
285                 n->status.udppacket = true;
286                 bool result = sptps_receive_data(&n->sptps, DATA(inpkt), inpkt->len);
287                 n->status.udppacket = false;
288
289                 if(!result) {
290                         /* Uh-oh. It might be that the tunnel is stuck in some corrupted state,
291                            so let's restart SPTPS in case that helps. But don't do that too often
292                            to prevent storms, and because that would make life a little too easy
293                            for external attackers trying to DoS us. */
294                         if(n->last_req_key < now.tv_sec - 10) {
295                                 logger(DEBUG_PROTOCOL, LOG_ERR, "Failed to decode raw TCP packet from %s (%s), restarting SPTPS", n->name, n->hostname);
296                                 send_req_key(n);
297                         }
298                         return false;
299                 }
300                 return true;
301         }
302
303 #ifdef DISABLE_LEGACY
304         return false;
305 #else
306         if(!n->status.validkey_in) {
307                 logger(DEBUG_TRAFFIC, LOG_DEBUG, "Got packet from %s (%s) but he hasn't got our key yet", n->name, n->hostname);
308                 return false;
309         }
310
311         /* Check packet length */
312
313         if(inpkt->len < sizeof(seqno_t) + digest_length(n->indigest)) {
314                 logger(DEBUG_TRAFFIC, LOG_DEBUG, "Got too short packet from %s (%s)",
315                                         n->name, n->hostname);
316                 return false;
317         }
318
319         /* It's a legacy UDP packet, the data starts after the seqno */
320
321         inpkt->offset += sizeof(seqno_t);
322
323         /* Check the message authentication code */
324
325         if(digest_active(n->indigest)) {
326                 inpkt->len -= digest_length(n->indigest);
327                 if(!digest_verify(n->indigest, SEQNO(inpkt), inpkt->len, SEQNO(inpkt) + inpkt->len)) {
328                         logger(DEBUG_TRAFFIC, LOG_DEBUG, "Got unauthenticated packet from %s (%s)", n->name, n->hostname);
329                         return false;
330                 }
331         }
332         /* Decrypt the packet */
333
334         if(cipher_active(n->incipher)) {
335                 vpn_packet_t *outpkt = pkt[nextpkt++];
336                 outlen = MAXSIZE;
337
338                 if(!cipher_decrypt(n->incipher, SEQNO(inpkt), inpkt->len, SEQNO(outpkt), &outlen, true)) {
339                         logger(DEBUG_TRAFFIC, LOG_DEBUG, "Error decrypting packet from %s (%s)", n->name, n->hostname);
340                         return false;
341                 }
342
343                 outpkt->len = outlen;
344                 inpkt = outpkt;
345         }
346
347         /* Check the sequence number */
348
349         seqno_t seqno;
350         memcpy(&seqno, SEQNO(inpkt), sizeof seqno);
351         seqno = ntohl(seqno);
352         inpkt->len -= sizeof seqno;
353
354         if(replaywin) {
355                 if(seqno != n->received_seqno + 1) {
356                         if(seqno >= n->received_seqno + replaywin * 8) {
357                                 if(n->farfuture++ < replaywin >> 2) {
358                                         logger(DEBUG_ALWAYS, LOG_WARNING, "Packet from %s (%s) is %d seqs in the future, dropped (%u)",
359                                                 n->name, n->hostname, seqno - n->received_seqno - 1, n->farfuture);
360                                         return false;
361                                 }
362                                 logger(DEBUG_ALWAYS, LOG_WARNING, "Lost %d packets from %s (%s)",
363                                                 seqno - n->received_seqno - 1, n->name, n->hostname);
364                                 memset(n->late, 0, replaywin);
365                         } else if (seqno <= n->received_seqno) {
366                                 if((n->received_seqno >= replaywin * 8 && seqno <= n->received_seqno - replaywin * 8) || !(n->late[(seqno / 8) % replaywin] & (1 << seqno % 8))) {
367                                         logger(DEBUG_ALWAYS, LOG_WARNING, "Got late or replayed packet from %s (%s), seqno %d, last received %d",
368                                                 n->name, n->hostname, seqno, n->received_seqno);
369                                         return false;
370                                 }
371                         } else {
372                                 for(int i = n->received_seqno + 1; i < seqno; i++)
373                                         n->late[(i / 8) % replaywin] |= 1 << i % 8;
374                         }
375                 }
376
377                 n->farfuture = 0;
378                 n->late[(seqno / 8) % replaywin] &= ~(1 << seqno % 8);
379         }
380
381         if(seqno > n->received_seqno)
382                 n->received_seqno = seqno;
383
384         n->received++;
385
386         if(n->received_seqno > MAX_SEQNO)
387                 regenerate_key();
388
389         /* Decompress the packet */
390
391         length_t origlen = inpkt->len;
392
393         if(n->incompression) {
394                 vpn_packet_t *outpkt = pkt[nextpkt++];
395
396                 if((outpkt->len = uncompress_packet(DATA(outpkt), DATA(inpkt), inpkt->len, n->incompression)) < 0) {
397                         logger(DEBUG_TRAFFIC, LOG_ERR, "Error while uncompressing packet from %s (%s)",
398                                                  n->name, n->hostname);
399                         return false;
400                 }
401
402                 inpkt = outpkt;
403
404                 origlen -= MTU/64 + 20;
405         }
406
407         if(inpkt->len > n->maxrecentlen)
408                 n->maxrecentlen = inpkt->len;
409
410         inpkt->priority = 0;
411
412         if(!DATA(inpkt)[12] && !DATA(inpkt)[13])
413                 udp_probe_h(n, inpkt, origlen);
414         else
415                 receive_packet(n, inpkt);
416         return true;
417 #endif
418 }
419
420 void receive_tcppacket(connection_t *c, const char *buffer, int len) {
421         vpn_packet_t outpkt;
422         outpkt.offset = DEFAULT_PACKET_OFFSET;
423
424         if(len > sizeof outpkt.data - outpkt.offset)
425                 return;
426
427         outpkt.len = len;
428         if(c->options & OPTION_TCPONLY)
429                 outpkt.priority = 0;
430         else
431                 outpkt.priority = -1;
432         memcpy(DATA(&outpkt), buffer, len);
433
434         receive_packet(c->node, &outpkt);
435 }
436
437 bool receive_tcppacket_sptps(connection_t *c, const char *data, int len) {
438         if (len < sizeof(node_id_t) + sizeof(node_id_t)) {
439                 logger(DEBUG_ALWAYS, LOG_ERR, "Got too short TCP SPTPS packet from %s (%s)", c->name, c->hostname);
440                 return false;
441         }
442
443         node_t *to = lookup_node_id((node_id_t *)data);
444         data += sizeof(node_id_t); len -= sizeof(node_id_t);
445         if(!to) {
446                 logger(DEBUG_PROTOCOL, LOG_ERR, "Got TCP SPTPS packet from %s (%s) with unknown destination ID", c->name, c->hostname);
447                 return true;
448         }
449
450         node_t *from = lookup_node_id((node_id_t *)data);
451         data += sizeof(node_id_t); len -= sizeof(node_id_t);
452         if(!from) {
453                 logger(DEBUG_PROTOCOL, LOG_ERR, "Got TCP SPTPS packet from %s (%s) with unknown source ID", c->name, c->hostname);
454                 return true;
455         }
456
457         if(!to->status.reachable) {
458                 /* This can happen in the form of a race condition
459                    if the node just became unreachable. */
460                 logger(DEBUG_TRAFFIC, LOG_WARNING, "Cannot relay TCP packet from %s (%s) because the destination, %s (%s), is unreachable", from->name, from->hostname, to->name, to->hostname);
461                 return true;
462         }
463
464         /* Help the sender reach us over UDP.
465            Note that we only do this if we're the destination or the static relay;
466            otherwise every hop would initiate its own UDP info message, resulting in elevated chatter. */
467         if(to->via == myself)
468                 send_udp_info(myself, from);
469
470         /* If we're not the final recipient, relay the packet. */
471
472         if(to != myself) {
473                 send_sptps_data(to, from, 0, data, len);
474                 try_tx(to, true);
475                 return true;
476         }
477
478         /* The packet is for us */
479
480         if(!sptps_receive_data(&from->sptps, data, len)) {
481                 /* Uh-oh. It might be that the tunnel is stuck in some corrupted state,
482                    so let's restart SPTPS in case that helps. But don't do that too often
483                    to prevent storms. */
484                 if(from->last_req_key < now.tv_sec - 10) {
485                         logger(DEBUG_PROTOCOL, LOG_ERR, "Failed to decode raw TCP packet from %s (%s), restarting SPTPS", from->name, from->hostname);
486                         send_req_key(from);
487                 }
488                 return true;
489         }
490
491         send_mtu_info(myself, from, MTU);
492         return true;
493 }
494
495 static void send_sptps_packet(node_t *n, vpn_packet_t *origpkt) {
496         if(!n->status.validkey && !n->connection)
497                 return;
498
499         uint8_t type = 0;
500         int offset = 0;
501
502         if((!(DATA(origpkt)[12] | DATA(origpkt)[13])) && (n->sptps.outstate))  {
503                 sptps_send_record(&n->sptps, PKT_PROBE, (char *)DATA(origpkt), origpkt->len);
504                 return;
505         }
506
507         if(routing_mode == RMODE_ROUTER)
508                 offset = 14;
509         else
510                 type = PKT_MAC;
511
512         if(origpkt->len < offset)
513                 return;
514
515         vpn_packet_t outpkt;
516
517         if(n->outcompression) {
518                 outpkt.offset = 0;
519                 int len = compress_packet(DATA(&outpkt) + offset, DATA(origpkt) + offset, origpkt->len - offset, n->outcompression);
520                 if(len < 0) {
521                         logger(DEBUG_TRAFFIC, LOG_ERR, "Error while compressing packet to %s (%s)", n->name, n->hostname);
522                 } else if(len < origpkt->len - offset) {
523                         outpkt.len = len + offset;
524                         origpkt = &outpkt;
525                         type |= PKT_COMPRESSED;
526                 }
527         }
528
529         /* If we have a direct metaconnection to n, and we can't use UDP, then
530            don't bother with SPTPS and just use a "plaintext" PACKET message.
531            We don't really care about end-to-end security since we're not
532            sending the message through any intermediate nodes. */
533         if(n->connection && origpkt->len > n->minmtu)
534                 send_tcppacket(n->connection, origpkt);
535         else
536                 sptps_send_record(&n->sptps, type, DATA(origpkt) + offset, origpkt->len - offset);
537         return;
538 }
539
540 static void adapt_socket(const sockaddr_t *sa, int *sock) {
541         /* Make sure we have a suitable socket for the chosen address */
542         if(listen_socket[*sock].sa.sa.sa_family != sa->sa.sa_family) {
543                 for(int i = 0; i < listen_sockets; i++) {
544                         if(listen_socket[i].sa.sa.sa_family == sa->sa.sa_family) {
545                                 *sock = i;
546                                 break;
547                         }
548                 }
549         }
550 }
551
552 static void choose_udp_address(const node_t *n, const sockaddr_t **sa, int *sock) {
553         /* Latest guess */
554         *sa = &n->address;
555         *sock = n->sock;
556
557         /* If the UDP address is confirmed, use it. */
558         if(n->status.udp_confirmed)
559                 return;
560
561         /* Send every third packet to n->address; that could be set
562            to the node's reflexive UDP address discovered during key
563            exchange. */
564
565         static int x = 0;
566         if(++x >= 3) {
567                 x = 0;
568                 return;
569         }
570
571         /* Otherwise, address are found in edges to this node.
572            So we pick a random edge and a random socket. */
573
574         int i = 0;
575         int j = rand() % n->edge_tree->count;
576         edge_t *candidate = NULL;
577
578         for splay_each(edge_t, e, n->edge_tree) {
579                 if(i++ == j) {
580                         candidate = e->reverse;
581                         break;
582                 }
583         }
584
585         if(candidate) {
586                 *sa = &candidate->address;
587                 *sock = rand() % listen_sockets;
588         }
589
590         adapt_socket(*sa, sock);
591 }
592
593 static void choose_local_address(const node_t *n, const sockaddr_t **sa, int *sock) {
594         *sa = NULL;
595
596         /* Pick one of the edges from this node at random, then use its local address. */
597
598         int i = 0;
599         int j = rand() % n->edge_tree->count;
600         edge_t *candidate = NULL;
601
602         for splay_each(edge_t, e, n->edge_tree) {
603                 if(i++ == j) {
604                         candidate = e;
605                         break;
606                 }
607         }
608
609         if (candidate && candidate->local_address.sa.sa_family) {
610                 *sa = &candidate->local_address;
611                 *sock = rand() % listen_sockets;
612                 adapt_socket(*sa, sock);
613         }
614 }
615
616 static void send_udppacket(node_t *n, vpn_packet_t *origpkt) {
617         vpn_packet_t pkt1, pkt2;
618         vpn_packet_t *pkt[] = { &pkt1, &pkt2, &pkt1, &pkt2 };
619         vpn_packet_t *inpkt = origpkt;
620         int nextpkt = 0;
621         vpn_packet_t *outpkt;
622         int origlen = origpkt->len;
623         size_t outlen;
624         int origpriority = origpkt->priority;
625
626         pkt1.offset = DEFAULT_PACKET_OFFSET;
627         pkt2.offset = DEFAULT_PACKET_OFFSET;
628
629         if(!n->status.reachable) {
630                 logger(DEBUG_TRAFFIC, LOG_INFO, "Trying to send UDP packet to unreachable node %s (%s)", n->name, n->hostname);
631                 return;
632         }
633
634         if(n->status.sptps)
635                 return send_sptps_packet(n, origpkt);
636
637 #ifdef DISABLE_LEGACY
638         return;
639 #else
640         /* Make sure we have a valid key */
641
642         if(!n->status.validkey) {
643                 logger(DEBUG_TRAFFIC, LOG_INFO,
644                                    "No valid key known yet for %s (%s), forwarding via TCP",
645                                    n->name, n->hostname);
646                 send_tcppacket(n->nexthop->connection, origpkt);
647                 return;
648         }
649
650         if(n->options & OPTION_PMTU_DISCOVERY && inpkt->len > n->minmtu && (DATA(inpkt)[12] | DATA(inpkt)[13])) {
651                 logger(DEBUG_TRAFFIC, LOG_INFO,
652                                 "Packet for %s (%s) larger than minimum MTU, forwarding via %s",
653                                 n->name, n->hostname, n != n->nexthop ? n->nexthop->name : "TCP");
654
655                 if(n != n->nexthop)
656                         send_packet(n->nexthop, origpkt);
657                 else
658                         send_tcppacket(n->nexthop->connection, origpkt);
659
660                 return;
661         }
662
663         /* Compress the packet */
664
665         if(n->outcompression) {
666                 outpkt = pkt[nextpkt++];
667
668                 if((outpkt->len = compress_packet(DATA(outpkt), DATA(inpkt), inpkt->len, n->outcompression)) < 0) {
669                         logger(DEBUG_TRAFFIC, LOG_ERR, "Error while compressing packet to %s (%s)",
670                                    n->name, n->hostname);
671                         return;
672                 }
673
674                 inpkt = outpkt;
675         }
676
677         /* Add sequence number */
678
679         seqno_t seqno = htonl(++(n->sent_seqno));
680         memcpy(SEQNO(inpkt), &seqno, sizeof seqno);
681         inpkt->len += sizeof seqno;
682
683         /* Encrypt the packet */
684
685         if(cipher_active(n->outcipher)) {
686                 outpkt = pkt[nextpkt++];
687                 outlen = MAXSIZE;
688
689                 if(!cipher_encrypt(n->outcipher, SEQNO(inpkt), inpkt->len, SEQNO(outpkt), &outlen, true)) {
690                         logger(DEBUG_TRAFFIC, LOG_ERR, "Error while encrypting packet to %s (%s)", n->name, n->hostname);
691                         goto end;
692                 }
693
694                 outpkt->len = outlen;
695                 inpkt = outpkt;
696         }
697
698         /* Add the message authentication code */
699
700         if(digest_active(n->outdigest)) {
701                 if(!digest_create(n->outdigest, SEQNO(inpkt), inpkt->len, SEQNO(inpkt) + inpkt->len)) {
702                         logger(DEBUG_TRAFFIC, LOG_ERR, "Error while encrypting packet to %s (%s)", n->name, n->hostname);
703                         goto end;
704                 }
705
706                 inpkt->len += digest_length(n->outdigest);
707         }
708
709         /* Send the packet */
710
711         const sockaddr_t *sa = NULL;
712         int sock;
713
714         if(n->status.send_locally)
715                 choose_local_address(n, &sa, &sock);
716         if(!sa)
717                 choose_udp_address(n, &sa, &sock);
718
719         if(priorityinheritance && origpriority != listen_socket[sock].priority) {
720                 listen_socket[sock].priority = origpriority;
721                 switch(sa->sa.sa_family) {
722 #if defined(IPPROTO_IP) && defined(IP_TOS)
723                 case AF_INET:
724                         logger(DEBUG_TRAFFIC, LOG_DEBUG, "Setting IPv4 outgoing packet priority to %d", origpriority);
725                         if(setsockopt(listen_socket[sock].udp.fd, IPPROTO_IP, IP_TOS, (void *)&origpriority, sizeof origpriority)) /* SO_PRIORITY doesn't seem to work */
726                                 logger(DEBUG_ALWAYS, LOG_ERR, "System call `%s' failed: %s", "setsockopt", sockstrerror(sockerrno));
727                         break;
728 #endif
729 #if defined(IPPROTO_IPV6) & defined(IPV6_TCLASS)
730                 case AF_INET6:
731                         logger(DEBUG_TRAFFIC, LOG_DEBUG, "Setting IPv6 outgoing packet priority to %d", origpriority);
732                         if(setsockopt(listen_socket[sock].udp.fd, IPPROTO_IPV6, IPV6_TCLASS, (void *)&origpriority, sizeof origpriority)) /* SO_PRIORITY doesn't seem to work */
733                                 logger(DEBUG_ALWAYS, LOG_ERR, "System call `%s' failed: %s", "setsockopt", sockstrerror(sockerrno));
734                         break;
735 #endif
736                 default:
737                         break;
738                 }
739         }
740
741         if(sendto(listen_socket[sock].udp.fd, (void *)SEQNO(inpkt), inpkt->len, 0, &sa->sa, SALEN(sa->sa)) < 0 && !sockwouldblock(sockerrno)) {
742                 if(sockmsgsize(sockerrno)) {
743                         if(n->maxmtu >= origlen)
744                                 n->maxmtu = origlen - 1;
745                         if(n->mtu >= origlen)
746                                 n->mtu = origlen - 1;
747                         try_fix_mtu(n);
748                 } else
749                         logger(DEBUG_TRAFFIC, LOG_WARNING, "Error sending packet to %s (%s): %s", n->name, n->hostname, sockstrerror(sockerrno));
750         }
751
752 end:
753         origpkt->len = origlen;
754 #endif
755 }
756
757 bool send_sptps_data(node_t *to, node_t *from, int type, const void *data, size_t len) {
758         node_t *relay = (to->via != myself && (type == PKT_PROBE || (len - SPTPS_DATAGRAM_OVERHEAD) <= to->via->minmtu)) ? to->via : to->nexthop;
759         bool direct = from == myself && to == relay;
760         bool relay_supported = (relay->options >> 24) >= 4;
761         bool tcponly = (myself->options | relay->options) & OPTION_TCPONLY;
762
763         /* 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. */
764
765         if(type == SPTPS_HANDSHAKE || tcponly || (!direct && !relay_supported) || (type != PKT_PROBE && (len - SPTPS_DATAGRAM_OVERHEAD) > relay->minmtu)) {
766                 if(type != SPTPS_HANDSHAKE && (to->nexthop->connection->options >> 24) >= 7) {
767                         char buf[len + sizeof to->id + sizeof from->id]; char* buf_ptr = buf;
768                         memcpy(buf_ptr, &to->id, sizeof to->id); buf_ptr += sizeof to->id;
769                         memcpy(buf_ptr, &from->id, sizeof from->id); buf_ptr += sizeof from->id;
770                         memcpy(buf_ptr, data, len); buf_ptr += len;
771                         logger(DEBUG_TRAFFIC, LOG_INFO, "Sending packet from %s (%s) to %s (%s) via %s (%s) (TCP)", from->name, from->hostname, to->name, to->hostname, to->nexthop->name, to->nexthop->hostname);
772                         return send_sptps_tcppacket(to->nexthop->connection, buf, sizeof buf);
773                 }
774
775                 char buf[len * 4 / 3 + 5];
776                 b64encode(data, buf, len);
777                 /* If this is a handshake packet, use ANS_KEY instead of REQ_KEY, for two reasons:
778                     - We don't want intermediate nodes to switch to UDP to relay these packets;
779                     - ANS_KEY allows us to learn the reflexive UDP address. */
780                 if(type == SPTPS_HANDSHAKE) {
781                         to->incompression = myself->incompression;
782                         return send_request(to->nexthop->connection, "%d %s %s %s -1 -1 -1 %d", ANS_KEY, from->name, to->name, buf, to->incompression);
783                 } else {
784                         return send_request(to->nexthop->connection, "%d %s %s %d %s", REQ_KEY, from->name, to->name, SPTPS_PACKET, buf);
785                 }
786         }
787
788         size_t overhead = 0;
789         if(relay_supported) overhead += sizeof to->id + sizeof from->id;
790         char buf[len + overhead]; char* buf_ptr = buf;
791         if(relay_supported) {
792                 if(direct) {
793                         /* Inform the recipient that this packet was sent directly. */
794                         node_id_t nullid = {};
795                         memcpy(buf_ptr, &nullid, sizeof nullid); buf_ptr += sizeof nullid;
796                 } else {
797                         memcpy(buf_ptr, &to->id, sizeof to->id); buf_ptr += sizeof to->id;
798                 }
799                 memcpy(buf_ptr, &from->id, sizeof from->id); buf_ptr += sizeof from->id;
800
801         }
802         /* TODO: if this copy turns out to be a performance concern, change sptps_send_record() to add some "pre-padding" to the buffer and use that instead */
803         memcpy(buf_ptr, data, len); buf_ptr += len;
804
805         const sockaddr_t *sa = NULL;
806         int sock;
807         if(relay->status.send_locally)
808                 choose_local_address(relay, &sa, &sock);
809         if(!sa)
810                 choose_udp_address(relay, &sa, &sock);
811         logger(DEBUG_TRAFFIC, LOG_INFO, "Sending packet from %s (%s) to %s (%s) via %s (%s) (UDP)", from->name, from->hostname, to->name, to->hostname, relay->name, relay->hostname);
812         if(sendto(listen_socket[sock].udp.fd, buf, buf_ptr - buf, 0, &sa->sa, SALEN(sa->sa)) < 0 && !sockwouldblock(sockerrno)) {
813                 if(sockmsgsize(sockerrno)) {
814                         // Compensate for SPTPS overhead
815                         len -= SPTPS_DATAGRAM_OVERHEAD;
816                         if(relay->maxmtu >= len)
817                                 relay->maxmtu = len - 1;
818                         if(relay->mtu >= len)
819                                 relay->mtu = len - 1;
820                         try_fix_mtu(relay);
821                 } else {
822                         logger(DEBUG_TRAFFIC, LOG_WARNING, "Error sending UDP SPTPS packet to %s (%s): %s", relay->name, relay->hostname, sockstrerror(sockerrno));
823                         return false;
824                 }
825         }
826
827         return true;
828 }
829
830 bool receive_sptps_record(void *handle, uint8_t type, const void *data, uint16_t len) {
831         node_t *from = handle;
832
833         if(type == SPTPS_HANDSHAKE) {
834                 if(!from->status.validkey) {
835                         from->status.validkey = true;
836                         from->status.waitingforkey = false;
837                         logger(DEBUG_META, LOG_INFO, "SPTPS key exchange with %s (%s) succesful", from->name, from->hostname);
838                 }
839                 return true;
840         }
841
842         if(len > MTU) {
843                 logger(DEBUG_ALWAYS, LOG_ERR, "Packet from %s (%s) larger than maximum supported size (%d > %d)", from->name, from->hostname, len, MTU);
844                 return false;
845         }
846
847         vpn_packet_t inpkt;
848         inpkt.offset = DEFAULT_PACKET_OFFSET;
849
850         if(type == PKT_PROBE) {
851                 if(!from->status.udppacket) {
852                         logger(DEBUG_ALWAYS, LOG_ERR, "Got SPTPS PROBE packet from %s (%s) via TCP", from->name, from->hostname);
853                         return false;
854                 }
855                 inpkt.len = len;
856                 memcpy(DATA(&inpkt), data, len);
857                 if(inpkt.len > from->maxrecentlen)
858                         from->maxrecentlen = inpkt.len;
859                 udp_probe_h(from, &inpkt, len);
860                 return true;
861         }
862
863         if(type & ~(PKT_COMPRESSED | PKT_MAC)) {
864                 logger(DEBUG_ALWAYS, LOG_ERR, "Unexpected SPTPS record type %d len %d from %s (%s)", type, len, from->name, from->hostname);
865                 return false;
866         }
867
868         /* Check if we have the headers we need */
869         if(routing_mode != RMODE_ROUTER && !(type & PKT_MAC)) {
870                 logger(DEBUG_TRAFFIC, LOG_ERR, "Received packet from %s (%s) without MAC header (maybe Mode is not set correctly)", from->name, from->hostname);
871                 return false;
872         } else if(routing_mode == RMODE_ROUTER && (type & PKT_MAC)) {
873                 logger(DEBUG_TRAFFIC, LOG_WARNING, "Received packet from %s (%s) with MAC header (maybe Mode is not set correctly)", from->name, from->hostname);
874         }
875
876         int offset = (type & PKT_MAC) ? 0 : 14;
877         if(type & PKT_COMPRESSED) {
878                 length_t ulen = uncompress_packet(DATA(&inpkt) + offset, (const uint8_t *)data, len, from->incompression);
879                 if(ulen < 0) {
880                         return false;
881                 } else {
882                         inpkt.len = ulen + offset;
883                 }
884                 if(inpkt.len > MAXSIZE)
885                         abort();
886         } else {
887                 memcpy(DATA(&inpkt) + offset, data, len);
888                 inpkt.len = len + offset;
889         }
890
891         /* Generate the Ethernet packet type if necessary */
892         if(offset) {
893                 switch(DATA(&inpkt)[14] >> 4) {
894                         case 4:
895                                 DATA(&inpkt)[12] = 0x08;
896                                 DATA(&inpkt)[13] = 0x00;
897                                 break;
898                         case 6:
899                                 DATA(&inpkt)[12] = 0x86;
900                                 DATA(&inpkt)[13] = 0xDD;
901                                 break;
902                         default:
903                                 logger(DEBUG_TRAFFIC, LOG_ERR,
904                                                    "Unknown IP version %d while reading packet from %s (%s)",
905                                                    DATA(&inpkt)[14] >> 4, from->name, from->hostname);
906                                 return false;
907                 }
908         }
909
910         if(from->status.udppacket && inpkt.len > from->maxrecentlen)
911                 from->maxrecentlen = inpkt.len;
912
913         receive_packet(from, &inpkt);
914         return true;
915 }
916
917 // This function tries to get SPTPS keys, if they aren't already known.
918 // 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.
919 static void try_sptps(node_t *n) {
920         if(n->status.validkey)
921                 return;
922
923         logger(DEBUG_TRAFFIC, LOG_INFO, "No valid key known yet for %s (%s)", n->name, n->hostname);
924
925         if(!n->status.waitingforkey)
926                 send_req_key(n);
927         else if(n->last_req_key + 10 < now.tv_sec) {
928                 logger(DEBUG_ALWAYS, LOG_DEBUG, "No key from %s after 10 seconds, restarting SPTPS", n->name);
929                 sptps_stop(&n->sptps);
930                 n->status.waitingforkey = false;
931                 send_req_key(n);
932         }
933
934         return;
935 }
936
937 static void send_udp_probe_packet(node_t *n, int len) {
938         vpn_packet_t packet;
939         packet.offset = DEFAULT_PACKET_OFFSET;
940         memset(DATA(&packet), 0, 14);
941         randomize(DATA(&packet) + 14, len - 14);
942         packet.len = len;
943         packet.priority = 0;
944
945         logger(DEBUG_TRAFFIC, LOG_INFO, "Sending UDP probe length %d to %s (%s)", len, n->name, n->hostname);
946
947         send_udppacket(n, &packet);
948 }
949
950 // This function tries to establish a UDP tunnel to a node so that packets can be sent.
951 // If a tunnel is already established, it makes sure it stays up.
952 // This function makes no guarantees - it is up to the caller to check the node's state to figure out if UDP is usable.
953 static void try_udp(node_t* n) {
954         if(!udp_discovery)
955                 return;
956
957         /* Send gratuitous probe replies to 1.1 nodes. */
958
959         if((n->options >> 24) >= 3 && n->status.udp_confirmed) {
960                 struct timeval ping_tx_elapsed;
961                 timersub(&now, &n->udp_reply_sent, &ping_tx_elapsed);
962
963                 if(ping_tx_elapsed.tv_sec >= udp_discovery_keepalive_interval - 1) {
964                         n->udp_reply_sent = now;
965                         if(n->maxrecentlen) {
966                                 vpn_packet_t pkt;
967                                 pkt.len = n->maxrecentlen;
968                                 pkt.offset = DEFAULT_PACKET_OFFSET;
969                                 memset(DATA(&pkt), 0, 14);
970                                 randomize(DATA(&pkt) + 14, MIN_PROBE_SIZE - 14);
971                                 send_udp_probe_reply(n, &pkt, pkt.len);
972                                 n->maxrecentlen = 0;
973                         }
974                 }
975         }
976
977         /* Probe request */
978
979         struct timeval ping_tx_elapsed;
980         timersub(&now, &n->udp_ping_sent, &ping_tx_elapsed);
981
982         int interval = n->status.udp_confirmed ? udp_discovery_keepalive_interval : udp_discovery_interval;
983
984         if(ping_tx_elapsed.tv_sec >= interval) {
985                 send_udp_probe_packet(n, MIN_PROBE_SIZE);
986                 n->udp_ping_sent = now;
987
988                 if(localdiscovery && !n->status.udp_confirmed && n->prevedge) {
989                         n->status.send_locally = true;
990                         send_udp_probe_packet(n, MIN_PROBE_SIZE);
991                         n->status.send_locally = false;
992                 }
993         }
994 }
995
996 static length_t choose_initial_maxmtu(node_t *n) {
997 #ifdef IP_MTU
998
999         int sock = -1;
1000
1001         const sockaddr_t *sa = NULL;
1002         int sockindex;
1003         choose_udp_address(n, &sa, &sockindex);
1004         if(!sa)
1005                 return MTU;
1006
1007         sock = socket(sa->sa.sa_family, SOCK_DGRAM, IPPROTO_UDP);
1008         if(sock < 0) {
1009                 logger(DEBUG_TRAFFIC, LOG_ERR, "Creating MTU assessment socket for %s (%s) failed: %s", n->name, n->hostname, sockstrerror(sockerrno));
1010                 return MTU;
1011         }
1012
1013         if(connect(sock, &sa->sa, SALEN(sa->sa))) {
1014                 logger(DEBUG_TRAFFIC, LOG_ERR, "Connecting MTU assessment socket for %s (%s) failed: %s", n->name, n->hostname, sockstrerror(sockerrno));
1015                 close(sock);
1016                 return MTU;
1017         }
1018
1019         int ip_mtu;
1020         socklen_t ip_mtu_len = sizeof ip_mtu;
1021         if(getsockopt(sock, IPPROTO_IP, IP_MTU, &ip_mtu, &ip_mtu_len)) {
1022                 logger(DEBUG_TRAFFIC, LOG_ERR, "getsockopt(IP_MTU) on %s (%s) failed: %s", n->name, n->hostname, sockstrerror(sockerrno));
1023                 close(sock);
1024                 return MTU;
1025         }
1026
1027         close(sock);
1028
1029         /* getsockopt(IP_MTU) returns the MTU of the physical interface.
1030            We need to remove various overheads to get to the tinc MTU. */
1031         length_t mtu = ip_mtu;
1032         mtu -= (sa->sa.sa_family == AF_INET6) ? sizeof(struct ip6_hdr) : sizeof(struct ip);
1033         mtu -= 8; /* UDP */
1034         if(n->status.sptps) {
1035                 mtu -= SPTPS_DATAGRAM_OVERHEAD;
1036                 if((n->options >> 24) >= 4)
1037                         mtu -= sizeof(node_id_t) + sizeof(node_id_t);
1038 #ifndef DISABLE_LEGACY
1039         } else {
1040                 mtu -= digest_length(n->outdigest);
1041
1042                 /* Now it's tricky. We use CBC mode, so the length of the
1043                    encrypted payload must be a multiple of the blocksize. The
1044                    sequence number is also part of the encrypted payload, so we
1045                    must account for it after correcting for the blocksize.
1046                    Furthermore, the padding in the last block must be at least
1047                    1 byte. */
1048
1049                 length_t blocksize = cipher_blocksize(n->outcipher);
1050
1051                 if(blocksize > 1) {
1052                         mtu /= blocksize;
1053                         mtu *= blocksize;
1054                         mtu--;
1055                 }
1056
1057                 mtu -= 4; // seqno
1058 #endif
1059         }
1060
1061         if (mtu < 512) {
1062                 logger(DEBUG_TRAFFIC, LOG_ERR, "getsockopt(IP_MTU) on %s (%s) returned absurdly small value: %d", n->name, n->hostname, ip_mtu);
1063                 return MTU;
1064         }
1065         if (mtu > MTU)
1066                 return MTU;
1067
1068         logger(DEBUG_TRAFFIC, LOG_INFO, "Using system-provided maximum tinc MTU for %s (%s): %hd", n->name, n->hostname, mtu);
1069         return mtu;
1070
1071 #else
1072
1073         return MTU;
1074
1075 #endif
1076 }
1077
1078 /* This function tries to determines the MTU of a node.
1079    By calling this function repeatedly, n->minmtu will be progressively
1080    increased, and at some point, n->mtu will be fixed to n->minmtu.  If the MTU
1081    is already fixed, this function checks if it can be increased.
1082 */
1083
1084 static void try_mtu(node_t *n) {
1085         if(!(n->options & OPTION_PMTU_DISCOVERY))
1086                 return;
1087
1088         if(udp_discovery && !n->status.udp_confirmed) {
1089                 n->maxrecentlen = 0;
1090                 n->mtuprobes = 0;
1091                 n->minmtu = 0;
1092                 n->maxmtu = MTU;
1093                 return;
1094         }
1095
1096         /* mtuprobes == 0..19: initial discovery, send bursts with 1 second interval, mtuprobes++
1097            mtuprobes ==    20: fix MTU, and go to -1
1098            mtuprobes ==    -1: send one maxmtu and one maxmtu+1 probe every pinginterval
1099            mtuprobes ==-2..-3: send one maxmtu probe every second
1100            mtuprobes ==    -4: maxmtu no longer valid, reset minmtu and maxmtu and go to 0 */
1101
1102         struct timeval elapsed;
1103         timersub(&now, &n->mtu_ping_sent, &elapsed);
1104         if(n->mtuprobes >= 0) {
1105                 if(n->mtuprobes != 0 && elapsed.tv_sec == 0 && elapsed.tv_usec < 333333)
1106                         return;
1107         } else {
1108                 if(n->mtuprobes < -1) {
1109                         if(elapsed.tv_sec < 1)
1110                                 return;
1111                 } else {
1112                         if(elapsed.tv_sec < pinginterval)
1113                                 return;
1114                 }
1115         }
1116
1117         n->mtu_ping_sent = now;
1118
1119         try_fix_mtu(n);
1120
1121         if(n->mtuprobes < -3) {
1122                 /* We lost three MTU probes, restart discovery */
1123                 logger(DEBUG_TRAFFIC, LOG_INFO, "Decrease in PMTU to %s (%s) detected, restarting PMTU discovery", n->name, n->hostname);
1124                 n->mtuprobes = 0;
1125                 n->minmtu = 0;
1126         }
1127
1128         if(n->mtuprobes < 0) {
1129                 /* After the initial discovery, we only send one maxmtu and one
1130                    maxmtu+1 probe to detect PMTU increases. */
1131                 send_udp_probe_packet(n, n->maxmtu);
1132                 if(n->mtuprobes == -1 && n->maxmtu + 1 < MTU)
1133                         send_udp_probe_packet(n, n->maxmtu + 1);
1134                 n->mtuprobes--;
1135         } else {
1136                 /* Before initial discovery begins, set maxmtu to the most likely value.
1137                    If it's underestimated, we will correct it after initial discovery. */
1138                 if(n->mtuprobes == 0)
1139                         n->maxmtu = choose_initial_maxmtu(n);
1140
1141                 for (;;) {
1142                         /* Decreasing the number of probes per cycle might make the algorithm react faster to lost packets,
1143                            but it will typically increase convergence time in the no-loss case. */
1144                         const length_t probes_per_cycle = 8;
1145
1146                         /* This magic value was determined using math simulations.
1147                            It will result in a 1329-byte first probe, followed (if there was a reply) by a 1407-byte probe.
1148                            Since 1407 is just below the range of tinc MTUs over typical networks,
1149                            this fine-tuning allows tinc to cover a lot of ground very quickly.
1150                            This fine-tuning is only valid for maxmtu = MTU; if maxmtu is smaller,
1151                            then it's better to use a multiplier of 1. Indeed, this leads to an interesting scenario
1152                            if choose_initial_maxmtu() returns the actual MTU value - it will get confirmed with one single probe. */
1153                         const float multiplier = (n->maxmtu == MTU) ? 0.97 : 1;
1154
1155                         const float cycle_position = probes_per_cycle - (n->mtuprobes % probes_per_cycle) - 1;
1156                         const length_t minmtu = MAX(n->minmtu, 512);
1157                         const float interval = n->maxmtu - minmtu;
1158
1159                         /* The core of the discovery algorithm is this exponential.
1160                            It produces very large probes early in the cycle, and then it very quickly decreases the probe size.
1161                            This reflects the fact that in the most difficult cases, we don't get any feedback for probes that
1162                            are too large, and therefore we need to concentrate on small offsets so that we can quickly converge
1163                            on the precise MTU as we are approaching it.
1164                            The last probe of the cycle is always 1 byte in size - this is to make sure we'll get at least one
1165                            reply per cycle so that we can make progress. */
1166                         const length_t offset = powf(interval, multiplier * cycle_position / (probes_per_cycle - 1));
1167
1168                         length_t maxmtu = n->maxmtu;
1169                         send_udp_probe_packet(n, minmtu + offset);
1170                         /* If maxmtu changed, it means the probe was rejected by the system because it was too large.
1171                            In that case, we recalculate with the new maxmtu and try again. */
1172                         if(n->mtuprobes < 0 || maxmtu == n->maxmtu)
1173                                 break;
1174                 }
1175
1176                 if(n->mtuprobes >= 0)
1177                         n->mtuprobes++;
1178         }
1179 }
1180
1181 /* These functions try to establish a tunnel to a node (or its relay) so that
1182    packets can be sent (e.g. exchange keys).
1183    If a tunnel is already established, it tries to improve it (e.g. by trying
1184    to establish a UDP tunnel instead of TCP).  This function makes no
1185    guarantees - it is up to the caller to check the node's state to figure out
1186    if TCP and/or UDP is usable.  By calling this function repeatedly, the
1187    tunnel is gradually improved until we hit the wall imposed by the underlying
1188    network environment.  It is recommended to call this function every time a
1189    packet is sent (or intended to be sent) to a node, so that the tunnel keeps
1190    improving as packets flow, and then gracefully downgrades itself as it goes
1191    idle.
1192 */
1193
1194 static void try_tx_sptps(node_t *n, bool mtu) {
1195         /* If n is a TCP-only neighbor, we'll only use "cleartext" PACKET
1196            messages anyway, so there's no need for SPTPS at all. */
1197
1198         if(n->connection && ((myself->options | n->options) & OPTION_TCPONLY))
1199                 return;
1200
1201         /* Otherwise, try to do SPTPS authentication with n if necessary. */
1202
1203         try_sptps(n);
1204
1205         /* Do we need to statically relay packets? */
1206
1207         node_t *via = (n->via == myself) ? n->nexthop : n->via;
1208
1209         /* If we do have a static relay, try everything with that one instead, if it supports relaying. */
1210
1211         if(via != n) {
1212                 if((via->options >> 24) < 4)
1213                         return;
1214                 return try_tx(via, mtu);
1215         }
1216
1217         /* Otherwise, try to establish UDP connectivity. */
1218
1219         try_udp(n);
1220         if(mtu)
1221                 try_mtu(n);
1222
1223         /* If we don't have UDP connectivity (yet), we need to use a dynamic relay (nexthop)
1224            while we try to establish direct connectivity. */
1225
1226         if(!n->status.udp_confirmed && n != n->nexthop && (n->nexthop->options >> 24) >= 4)
1227                 try_tx(n->nexthop, mtu);
1228 }
1229
1230 static void try_tx_legacy(node_t *n, bool mtu) {
1231         /* Does he have our key? If not, send one. */
1232
1233         if(!n->status.validkey_in)
1234                 send_ans_key(n);
1235
1236         /* Check if we already have a key, or request one. */
1237
1238         if(!n->status.validkey) {
1239                 if(n->last_req_key + 10 <= now.tv_sec) {
1240                         send_req_key(n);
1241                         n->last_req_key = now.tv_sec;
1242                 }
1243                 return;
1244         }
1245
1246         try_udp(n);
1247         if(mtu)
1248                 try_mtu(n);
1249 }
1250
1251 void try_tx(node_t *n, bool mtu) {
1252         if(!n->status.reachable)
1253                 return;
1254         if(n->status.sptps)
1255                 try_tx_sptps(n, mtu);
1256         else
1257                 try_tx_legacy(n, mtu);
1258 }
1259
1260 void send_packet(node_t *n, vpn_packet_t *packet) {
1261         // If it's for myself, write it to the tun/tap device.
1262
1263         if(n == myself) {
1264                 if(overwrite_mac) {
1265                          memcpy(DATA(packet), mymac.x, ETH_ALEN);
1266                          // Use an arbitrary fake source address.
1267                          memcpy(DATA(packet) + ETH_ALEN, DATA(packet), ETH_ALEN);
1268                          DATA(packet)[ETH_ALEN * 2 - 1] ^= 0xFF;
1269                 }
1270                 n->out_packets++;
1271                 n->out_bytes += packet->len;
1272                 devops.write(packet);
1273                 return;
1274         }
1275
1276         logger(DEBUG_TRAFFIC, LOG_ERR, "Sending packet of %d bytes to %s (%s)", packet->len, n->name, n->hostname);
1277
1278         // If the node is not reachable, drop it.
1279
1280         if(!n->status.reachable) {
1281                 logger(DEBUG_TRAFFIC, LOG_INFO, "Node %s (%s) is not reachable", n->name, n->hostname);
1282                 return;
1283         }
1284
1285         // Keep track of packet statistics.
1286
1287         n->out_packets++;
1288         n->out_bytes += packet->len;
1289
1290         // Check if it should be sent as an SPTPS packet.
1291
1292         if(n->status.sptps) {
1293                 send_sptps_packet(n, packet);
1294                 try_tx(n, true);
1295                 return;
1296         }
1297
1298         // Determine which node to actually send it to.
1299
1300         node_t *via = (packet->priority == -1 || n->via == myself) ? n->nexthop : n->via;
1301
1302         if(via != n)
1303                 logger(DEBUG_TRAFFIC, LOG_INFO, "Sending packet to %s via %s (%s)", n->name, via->name, n->via->hostname);
1304
1305         // Try to send via UDP, unless TCP is forced.
1306
1307         if(packet->priority == -1 || ((myself->options | via->options) & OPTION_TCPONLY)) {
1308                 if(!send_tcppacket(via->connection, packet))
1309                         terminate_connection(via->connection, true);
1310                 return;
1311         }
1312
1313         send_udppacket(via, packet);
1314         try_tx(via, true);
1315 }
1316
1317 void broadcast_packet(const node_t *from, vpn_packet_t *packet) {
1318         // Always give ourself a copy of the packet.
1319         if(from != myself)
1320                 send_packet(myself, packet);
1321
1322         // In TunnelServer mode, do not forward broadcast packets.
1323         // The MST might not be valid and create loops.
1324         if(tunnelserver || broadcast_mode == BMODE_NONE)
1325                 return;
1326
1327         logger(DEBUG_TRAFFIC, LOG_INFO, "Broadcasting packet of %d bytes from %s (%s)",
1328                            packet->len, from->name, from->hostname);
1329
1330         switch(broadcast_mode) {
1331                 // In MST mode, broadcast packets travel via the Minimum Spanning Tree.
1332                 // This guarantees all nodes receive the broadcast packet, and
1333                 // usually distributes the sending of broadcast packets over all nodes.
1334                 case BMODE_MST:
1335                         for list_each(connection_t, c, connection_list)
1336                                 if(c->edge && c->status.mst && c != from->nexthop->connection)
1337                                         send_packet(c->node, packet);
1338                         break;
1339
1340                 // In direct mode, we send copies to each node we know of.
1341                 // However, this only reaches nodes that can be reached in a single hop.
1342                 // We don't have enough information to forward broadcast packets in this case.
1343                 case BMODE_DIRECT:
1344                         if(from != myself)
1345                                 break;
1346
1347                         for splay_each(node_t, n, node_tree)
1348                                 if(n->status.reachable && n != myself && ((n->via == myself && n->nexthop == n) || n->via == n))
1349                                         send_packet(n, packet);
1350                         break;
1351
1352                 default:
1353                         break;
1354         }
1355 }
1356
1357 /* We got a packet from some IP address, but we don't know who sent it.  Try to
1358    verify the message authentication code against all active session keys.
1359    Since this is actually an expensive operation, we only do a full check once
1360    a minute, the rest of the time we only check against nodes for which we know
1361    an IP address that matches the one from the packet.  */
1362
1363 static node_t *try_harder(const sockaddr_t *from, const vpn_packet_t *pkt) {
1364         node_t *match = NULL;
1365         bool hard = false;
1366         static time_t last_hard_try = 0;
1367
1368         for splay_each(node_t, n, node_tree) {
1369                 if(!n->status.reachable || n == myself)
1370                         continue;
1371
1372                 if(!n->status.validkey_in && !(n->status.sptps && n->sptps.instate))
1373                         continue;
1374
1375                 bool soft = false;
1376
1377                 for splay_each(edge_t, e, n->edge_tree) {
1378                         if(!e->reverse)
1379                                 continue;
1380                         if(!sockaddrcmp_noport(from, &e->reverse->address)) {
1381                                 soft = true;
1382                                 break;
1383                         }
1384                 }
1385
1386                 if(!soft) {
1387                         if(last_hard_try == now.tv_sec)
1388                                 continue;
1389                         hard = true;
1390                 }
1391
1392                 if(!try_mac(n, pkt))
1393                         continue;
1394
1395                 match = n;
1396                 break;
1397         }
1398
1399         if(hard)
1400                 last_hard_try = now.tv_sec;
1401
1402         return match;
1403 }
1404
1405 static void handle_incoming_vpn_packet(listen_socket_t *ls, vpn_packet_t *pkt, sockaddr_t *addr) {
1406         char *hostname;
1407         node_id_t nullid = {};
1408         node_t *from, *to;
1409         bool direct = false;
1410
1411         sockaddrunmap(addr); /* Some braindead IPv6 implementations do stupid things. */
1412
1413         // Try to figure out who sent this packet.
1414
1415         node_t *n = lookup_node_udp(addr);
1416
1417         if(n && !n->status.udp_confirmed)
1418                 n = NULL; // Don't believe it if we don't have confirmation yet.
1419
1420         if(!n) {
1421                 // It might be from a 1.1 node, which might have a source ID in the packet.
1422                 pkt->offset = 2 * sizeof(node_id_t);
1423                 from = lookup_node_id(SRCID(pkt));
1424                 if(from && !memcmp(DSTID(pkt), &nullid, sizeof nullid) && from->status.sptps) {
1425                         if(sptps_verify_datagram(&from->sptps, DATA(pkt), pkt->len - 2 * sizeof(node_id_t)))
1426                                 n = from;
1427                         else
1428                                 goto skip_harder;
1429                 }
1430         }
1431
1432         if(!n) {
1433                 pkt->offset = 0;
1434                 n = try_harder(addr, pkt);
1435         }
1436
1437 skip_harder:
1438         if(!n) {
1439                 if(debug_level >= DEBUG_PROTOCOL) {
1440                         hostname = sockaddr2hostname(addr);
1441                         logger(DEBUG_PROTOCOL, LOG_WARNING, "Received UDP packet from unknown source %s", hostname);
1442                         free(hostname);
1443                 }
1444                 return;
1445         }
1446
1447         pkt->offset = 0;
1448
1449         if(n->status.sptps) {
1450                 bool relay_enabled = (n->options >> 24) >= 4;
1451                 if (relay_enabled) {
1452                         pkt->offset = 2 * sizeof(node_id_t);
1453                         pkt->len -= pkt->offset;
1454                 }
1455
1456                 if(!memcmp(DSTID(pkt), &nullid, sizeof nullid) || !relay_enabled) {
1457                         direct = true;
1458                         from = n;
1459                         to = myself;
1460                 } else {
1461                         from = lookup_node_id(SRCID(pkt));
1462                         to = lookup_node_id(DSTID(pkt));
1463                 }
1464                 if(!from || !to) {
1465                         logger(DEBUG_PROTOCOL, LOG_WARNING, "Received UDP packet from %s (%s) with unknown source and/or destination ID", n->name, n->hostname);
1466                         return;
1467                 }
1468
1469                 if(!to->status.reachable) {
1470                         /* This can happen in the form of a race condition
1471                            if the node just became unreachable. */
1472                         logger(DEBUG_TRAFFIC, LOG_WARNING, "Cannot relay packet from %s (%s) because the destination, %s (%s), is unreachable", from->name, from->hostname, to->name, to->hostname);
1473                         return;
1474                 }
1475
1476                 /* The packet is supposed to come from the originator or its static relay
1477                    (i.e. with no dynamic relays in between).
1478                    If it did not, "help" the static relay by sending it UDP info.
1479                    Note that we only do this if we're the destination or the static relay;
1480                    otherwise every hop would initiate its own UDP info message, resulting in elevated chatter. */
1481
1482                 if(n != from->via && to->via == myself)
1483                         send_udp_info(myself, from);
1484
1485                 /* If we're not the final recipient, relay the packet. */
1486
1487                 if(to != myself) {
1488                         send_sptps_data(to, from, 0, DATA(pkt), pkt->len);
1489                         try_tx(to, true);
1490                         return;
1491                 }
1492         } else {
1493                 direct = true;
1494                 from = n;
1495         }
1496
1497         if(!receive_udppacket(from, pkt))
1498                 return;
1499
1500         n->sock = ls - listen_socket;
1501         if(direct && sockaddrcmp(addr, &n->address))
1502                 update_node_udp(n, addr);
1503
1504         /* If the packet went through a relay, help the sender find the appropriate MTU
1505            through the relay path. */
1506
1507         if(!direct)
1508                 send_mtu_info(myself, n, MTU);
1509 }
1510
1511 void handle_incoming_vpn_data(void *data, int flags) {
1512         listen_socket_t *ls = data;
1513
1514 #ifdef HAVE_RECVMMSG
1515 #define MAX_MSG 64
1516         static int num = MAX_MSG;
1517         static vpn_packet_t pkt[MAX_MSG];
1518         static sockaddr_t addr[MAX_MSG];
1519         static struct mmsghdr msg[MAX_MSG];
1520         static struct iovec iov[MAX_MSG];
1521
1522         for(int i = 0; i < num; i++) {
1523                 pkt[i].offset = 0;
1524
1525                 iov[i] = (struct iovec){
1526                         .iov_base = DATA(&pkt[i]),
1527                         .iov_len = MAXSIZE,
1528                 };
1529
1530                 msg[i].msg_hdr = (struct msghdr){
1531                         .msg_name = &addr[i].sa,
1532                         .msg_namelen = sizeof addr[i],
1533                         .msg_iov = &iov[i],
1534                         .msg_iovlen = 1,
1535                 };
1536         }
1537
1538         num = recvmmsg(ls->udp.fd, msg, MAX_MSG, MSG_DONTWAIT, NULL);
1539
1540         if(num < 0) {
1541                 if(!sockwouldblock(sockerrno))
1542                         logger(DEBUG_ALWAYS, LOG_ERR, "Receiving packet failed: %s", sockstrerror(sockerrno));
1543                 return;
1544         }
1545
1546         for(int i = 0; i < num; i++) {
1547                 pkt[i].len = msg[i].msg_len;
1548                 if(pkt[i].len <= 0 || pkt[i].len > MAXSIZE)
1549                         continue;
1550                 handle_incoming_vpn_packet(ls, &pkt[i], &addr[i]);
1551         }
1552 #else
1553         vpn_packet_t pkt;
1554         sockaddr_t addr = {};
1555         socklen_t addrlen = sizeof addr;
1556
1557         pkt.offset = 0;
1558         int len = recvfrom(ls->udp.fd, (void *)DATA(&pkt), MAXSIZE, 0, &addr.sa, &addrlen);
1559
1560         if(len <= 0 || len > MAXSIZE) {
1561                 if(!sockwouldblock(sockerrno))
1562                         logger(DEBUG_ALWAYS, LOG_ERR, "Receiving packet failed: %s", sockstrerror(sockerrno));
1563                 return;
1564         }
1565
1566         pkt.len = len;
1567
1568         handle_incoming_vpn_packet(ls, &pkt, &addr);
1569 #endif
1570 }
1571
1572 void handle_device_data(void *data, int flags) {
1573         vpn_packet_t packet;
1574         packet.offset = DEFAULT_PACKET_OFFSET;
1575         packet.priority = 0;
1576
1577         if(devops.read(&packet)) {
1578                 myself->in_packets++;
1579                 myself->in_bytes += packet.len;
1580                 route(myself, &packet);
1581         }
1582 }