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