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