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