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