git.tinc-vpn.org Git - tinc/blob - src/net_packet.c

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