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