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