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