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