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