src/net_packet.c

   1 /*
   2     net_packet.c -- Handles in- and outgoing VPN packets
   3     Copyright (C) 1998-2005 Ivo Timmermans,
   4                   2000-2013 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 "graph.h"
  41 #include "logger.h"
  42 #include "net.h"
  43 #include "netutl.h"
  44 #include "protocol.h"
  45 #include "process.h"
  46 #include "route.h"
  47 #include "utils.h"
  48 #include "xalloc.h"
  49
  50 int keylifetime = 0;
  51 #ifdef HAVE_LZO
  52 static char lzo_wrkmem[LZO1X_999_MEM_COMPRESS > LZO1X_1_MEM_COMPRESS ? LZO1X_999_MEM_COMPRESS : LZO1X_1_MEM_COMPRESS];
  53 #endif
  54
  55 static void send_udppacket(node_t *, vpn_packet_t *);
  56
  57 unsigned replaywin = 16;
  58 bool localdiscovery = false;
  59 sockaddr_t localdiscovery_address;
  60
  61 #define MAX_SEQNO 1073741824
  62
  63 /* mtuprobes == 1..30: initial discovery, send bursts with 1 second interval
  64    mtuprobes ==    31: sleep pinginterval seconds
  65    mtuprobes ==    32: send 1 burst, sleep pingtimeout second
  66    mtuprobes ==    33: no response from other side, restart PMTU discovery process
  67
  68    Probes are sent in batches of at least three, with random sizes between the
  69    lower and upper boundaries for the MTU thus far discovered.
  70
  71    After the initial discovery, a fourth packet is added to each batch with a
  72    size larger than the currently known PMTU, to test if the PMTU has increased.
  73
  74    In case local discovery is enabled, another packet is added to each batch,
  75    which will be broadcast to the local network.
  76
  77 */
  78
  79 static void send_mtu_probe_handler(void *data) {
  80         node_t *n = data;
  81         int timeout = 1;
  82
  83         n->mtuprobes++;
  84
  85         if(!n->status.reachable || !n->status.validkey) {
  86                 logger(DEBUG_TRAFFIC, LOG_INFO, "Trying to send MTU probe to unreachable or rekeying node %s (%s)", n->name, n->hostname);
  87                 n->mtuprobes = 0;
  88                 return;
  89         }
  90
  91         if(n->mtuprobes > 32) {
  92                 if(!n->minmtu) {
  93                         n->mtuprobes = 31;
  94                         timeout = pinginterval;
  95                         goto end;
  96                 }
  97
  98                 logger(DEBUG_TRAFFIC, LOG_INFO, "%s (%s) did not respond to UDP ping, restarting PMTU discovery", n->name, n->hostname);
  99                 n->status.udp_confirmed = false;
 100                 n->mtuprobes = 1;
 101                 n->minmtu = 0;
 102                 n->maxmtu = MTU;
 103         }
 104
 105         if(n->mtuprobes >= 10 && n->mtuprobes < 32 && !n->minmtu) {
 106                 logger(DEBUG_TRAFFIC, LOG_INFO, "No response to MTU probes from %s (%s)", n->name, n->hostname);
 107                 n->mtuprobes = 31;
 108         }
 109
 110         if(n->mtuprobes == 30 || (n->mtuprobes < 30 && n->minmtu >= n->maxmtu)) {
 111                 if(n->minmtu > n->maxmtu)
 112                         n->minmtu = n->maxmtu;
 113                 else
 114                         n->maxmtu = n->minmtu;
 115                 n->mtu = n->minmtu;
 116                 logger(DEBUG_TRAFFIC, LOG_INFO, "Fixing MTU of %s (%s) to %d after %d probes", n->name, n->hostname, n->mtu, n->mtuprobes);
 117                 n->mtuprobes = 31;
 118         }
 119
 120         if(n->mtuprobes == 31) {
 121                 timeout = pinginterval;
 122                 goto end;
 123         } else if(n->mtuprobes == 32) {
 124                 timeout = pingtimeout;
 125         }
 126
 127         for(int i = 0; i < 4 + localdiscovery; i++) {
 128                 int len;
 129
 130                 if(i == 0) {
 131                         if(n->mtuprobes < 30 || n->maxmtu + 8 >= MTU)
 132                                 continue;
 133                         len = n->maxmtu + 8;
 134                 } else if(n->maxmtu <= n->minmtu) {
 135                         len = n->maxmtu;
 136                 } else {
 137                         len = n->minmtu + 1 + rand() % (n->maxmtu - n->minmtu);
 138                 }
 139
 140                 if(len < 64)
 141                         len = 64;
 142
 143                 vpn_packet_t packet;
 144                 memset(packet.data, 0, 14);
 145                 randomize(packet.data + 14, len - 14);
 146                 packet.len = len;
 147                 if(i >= 4 && n->mtuprobes <= 10)
 148                         packet.priority = -1;
 149                 else
 150                         packet.priority = 0;
 151
 152                 logger(DEBUG_TRAFFIC, LOG_INFO, "Sending MTU probe length %d to %s (%s)", len, n->name, n->hostname);
 153
 154                 send_udppacket(n, &packet);
 155         }
 156
 157         n->probe_counter = 0;
 158         gettimeofday(&n->probe_time, NULL);
 159
 160         /* Calculate the packet loss of incoming traffic by comparing the rate of
 161            packets received to the rate with which the sequence number has increased.
 162          */
 163
 164         if(n->received > n->prev_received)
 165                 n->packetloss = 1.0 - (n->received - n->prev_received) / (float)(n->received_seqno - n->prev_received_seqno);
 166         else
 167                 n->packetloss = n->received_seqno <= n->prev_received_seqno;
 168
 169         n->prev_received_seqno = n->received_seqno;
 170         n->prev_received = n->received;
 171
 172 end:
 173         timeout_set(&n->mtutimeout, &(struct timeval){timeout, rand() % 100000});
 174 }
 175
 176 void send_mtu_probe(node_t *n) {
 177         timeout_add(&n->mtutimeout, send_mtu_probe_handler, n, &(struct timeval){1, 0});
 178         send_mtu_probe_handler(n);
 179 }
 180
 181 static void mtu_probe_h(node_t *n, vpn_packet_t *packet, length_t len) {
 182         logger(DEBUG_TRAFFIC, LOG_INFO, "Got MTU probe length %d from %s (%s)", packet->len, n->name, n->hostname);
 183
 184         if(!packet->data[0]) {
 185                 /* It's a probe request, send back a reply */
 186
 187                 packet->data[0] = 1;
 188
 189                 /* Temporarily set udp_confirmed, so that the reply is sent
 190                    back exactly the way it came in. */
 191
 192                 bool udp_confirmed = n->status.udp_confirmed;
 193                 n->status.udp_confirmed = true;
 194                 send_udppacket(n, packet);
 195                 n->status.udp_confirmed = udp_confirmed;
 196         } else {
 197                 /* It's a valid reply: now we know bidirectional communication
 198                    is possible using the address and socket that the reply
 199                    packet used. */
 200
 201                 n->status.udp_confirmed = true;
 202
 203                 /* If we haven't established the PMTU yet, restart the discovery process. */
 204
 205                 if(n->mtuprobes > 30) {
 206                         if (len == n->maxmtu + 8) {
 207                                 logger(DEBUG_TRAFFIC, LOG_INFO, "Increase in PMTU to %s (%s) detected, restarting PMTU discovery", n->name, n->hostname);
 208                                 n->maxmtu = MTU;
 209                                 n->mtuprobes = 10;
 210                                 return;
 211                         }
 212
 213                         if(n->minmtu)
 214                                 n->mtuprobes = 30;
 215                         else
 216                                 n->mtuprobes = 1;
 217                 }
 218
 219                 /* If applicable, raise the minimum supported MTU */
 220
 221                 if(len > n->maxmtu)
 222                         len = n->maxmtu;
 223                 if(n->minmtu < len)
 224                         n->minmtu = len;
 225
 226                 /* Calculate RTT and bandwidth.
 227                    The RTT is the time between the MTU probe burst was sent and the first
 228                    reply is received. The bandwidth is measured using the time between the
 229                    arrival of the first and third probe reply.
 230                  */
 231
 232                 struct timeval now, diff;
 233                 gettimeofday(&now, NULL);
 234                 timersub(&now, &n->probe_time, &diff);
 235                 n->probe_counter++;
 236
 237                 if(n->probe_counter == 1) {
 238                         n->rtt = diff.tv_sec + diff.tv_usec * 1e-6;
 239                         n->probe_time = now;
 240                 } else if(n->probe_counter == 3) {
 241                         n->bandwidth = 2.0 * len / (diff.tv_sec + diff.tv_usec * 1e-6);
 242                         logger(DEBUG_TRAFFIC, LOG_DEBUG, "%s (%s) RTT %.2f ms, burst bandwidth %.3f Mbit/s, rx packet loss %.2f %%", n->name, n->hostname, n->rtt * 1e3, n->bandwidth * 8e-6, n->packetloss * 1e2);
 243                 }
 244         }
 245 }
 246
 247 static length_t compress_packet(uint8_t *dest, const uint8_t *source, length_t len, int level) {
 248         if(level == 0) {
 249                 memcpy(dest, source, len);
 250                 return len;
 251         } else if(level == 10) {
 252 #ifdef HAVE_LZO
 253                 lzo_uint lzolen = MAXSIZE;
 254                 lzo1x_1_compress(source, len, dest, &lzolen, lzo_wrkmem);
 255                 return lzolen;
 256 #else
 257                 return -1;
 258 #endif
 259         } else if(level < 10) {
 260 #ifdef HAVE_ZLIB
 261                 unsigned long destlen = MAXSIZE;
 262                 if(compress2(dest, &destlen, source, len, level) == Z_OK)
 263                         return destlen;
 264                 else
 265 #endif
 266                         return -1;
 267         } else {
 268 #ifdef HAVE_LZO
 269                 lzo_uint lzolen = MAXSIZE;
 270                 lzo1x_999_compress(source, len, dest, &lzolen, lzo_wrkmem);
 271                 return lzolen;
 272 #else
 273                 return -1;
 274 #endif
 275         }
 276
 277         return -1;
 278 }
 279
 280 static length_t uncompress_packet(uint8_t *dest, const uint8_t *source, length_t len, int level) {
 281         if(level == 0) {
 282                 memcpy(dest, source, len);
 283                 return len;
 284         } else if(level > 9) {
 285 #ifdef HAVE_LZO
 286                 lzo_uint lzolen = MAXSIZE;
 287                 if(lzo1x_decompress_safe(source, len, dest, &lzolen, NULL) == LZO_E_OK)
 288                         return lzolen;
 289                 else
 290 #endif
 291                         return -1;
 292         }
 293 #ifdef HAVE_ZLIB
 294         else {
 295                 unsigned long destlen = MAXSIZE;
 296                 if(uncompress(dest, &destlen, source, len) == Z_OK)
 297                         return destlen;
 298                 else
 299                         return -1;
 300         }
 301 #endif
 302
 303         return -1;
 304 }
 305
 306 /* VPN packet I/O */
 307
 308 static void receive_packet(node_t *n, vpn_packet_t *packet) {
 309         logger(DEBUG_TRAFFIC, LOG_DEBUG, "Received packet of %d bytes from %s (%s)",
 310                            packet->len, n->name, n->hostname);
 311
 312         n->in_packets++;
 313         n->in_bytes += packet->len;
 314
 315         route(n, packet);
 316 }
 317
 318 static bool try_mac(node_t *n, const vpn_packet_t *inpkt) {
 319         if(n->status.sptps)
 320                 return sptps_verify_datagram(&n->sptps, (char *)&inpkt->seqno, inpkt->len);
 321
 322         if(!digest_active(n->indigest) || inpkt->len < sizeof inpkt->seqno + digest_length(n->indigest))
 323                 return false;
 324
 325         return digest_verify(n->indigest, &inpkt->seqno, inpkt->len - digest_length(n->indigest), (const char *)&inpkt->seqno + inpkt->len - digest_length(n->indigest));
 326 }
 327
 328 static void receive_udppacket(node_t *n, vpn_packet_t *inpkt) {
 329         vpn_packet_t pkt1, pkt2;
 330         vpn_packet_t *pkt[] = { &pkt1, &pkt2, &pkt1, &pkt2 };
 331         int nextpkt = 0;
 332         vpn_packet_t *outpkt = pkt[0];
 333         size_t outlen;
 334
 335         if(n->status.sptps) {
 336                 if(!n->sptps.state) {
 337                         if(!n->status.waitingforkey) {
 338                                 logger(DEBUG_TRAFFIC, LOG_DEBUG, "Got packet from %s (%s) but we haven't exchanged keys yet", n->name, n->hostname);
 339                                 send_req_key(n);
 340                         } else {
 341                                 logger(DEBUG_TRAFFIC, LOG_DEBUG, "Got packet from %s (%s) but he hasn't got our key yet", n->name, n->hostname);
 342                         }
 343                         return;
 344                 }
 345                 sptps_receive_data(&n->sptps, (char *)&inpkt->seqno, inpkt->len);
 346                 return;
 347         }
 348
 349         if(!cipher_active(n->incipher)) {
 350                 logger(DEBUG_TRAFFIC, LOG_DEBUG, "Got packet from %s (%s) but he hasn't got our key yet", n->name, n->hostname);
 351                 return;
 352         }
 353
 354         /* Check packet length */
 355
 356         if(inpkt->len < sizeof inpkt->seqno + digest_length(n->indigest)) {
 357                 logger(DEBUG_TRAFFIC, LOG_DEBUG, "Got too short packet from %s (%s)",
 358                                         n->name, n->hostname);
 359                 return;
 360         }
 361
 362         /* Check the message authentication code */
 363
 364         if(digest_active(n->indigest)) {
 365                 inpkt->len -= digest_length(n->indigest);
 366                 if(!digest_verify(n->indigest, &inpkt->seqno, inpkt->len, (const char *)&inpkt->seqno + inpkt->len)) {
 367                         logger(DEBUG_TRAFFIC, LOG_DEBUG, "Got unauthenticated packet from %s (%s)", n->name, n->hostname);
 368                         return;
 369                 }
 370         }
 371         /* Decrypt the packet */
 372
 373         if(cipher_active(n->incipher)) {
 374                 outpkt = pkt[nextpkt++];
 375                 outlen = MAXSIZE;
 376
 377                 if(!cipher_decrypt(n->incipher, &inpkt->seqno, inpkt->len, &outpkt->seqno, &outlen, true)) {
 378                         logger(DEBUG_TRAFFIC, LOG_DEBUG, "Error decrypting packet from %s (%s)", n->name, n->hostname);
 379                         return;
 380                 }
 381
 382                 outpkt->len = outlen;
 383                 inpkt = outpkt;
 384         }
 385
 386         /* Check the sequence number */
 387
 388         inpkt->len -= sizeof inpkt->seqno;
 389         inpkt->seqno = ntohl(inpkt->seqno);
 390
 391         if(replaywin) {
 392                 if(inpkt->seqno != n->received_seqno + 1) {
 393                         if(inpkt->seqno >= n->received_seqno + replaywin * 8) {
 394                                 if(n->farfuture++ < replaywin >> 2) {
 395                                         logger(DEBUG_ALWAYS, LOG_WARNING, "Packet from %s (%s) is %d seqs in the future, dropped (%u)",
 396                                                 n->name, n->hostname, inpkt->seqno - n->received_seqno - 1, n->farfuture);
 397                                         return;
 398                                 }
 399                                 logger(DEBUG_ALWAYS, LOG_WARNING, "Lost %d packets from %s (%s)",
 400                                                 inpkt->seqno - n->received_seqno - 1, n->name, n->hostname);
 401                                 memset(n->late, 0, replaywin);
 402                         } else if (inpkt->seqno <= n->received_seqno) {
 403                                 if((n->received_seqno >= replaywin * 8 && inpkt->seqno <= n->received_seqno - replaywin * 8) || !(n->late[(inpkt->seqno / 8) % replaywin] & (1 << inpkt->seqno % 8))) {
 404                                         logger(DEBUG_ALWAYS, LOG_WARNING, "Got late or replayed packet from %s (%s), seqno %d, last received %d",
 405                                                 n->name, n->hostname, inpkt->seqno, n->received_seqno);
 406                                         return;
 407                                 }
 408                         } else {
 409                                 for(int i = n->received_seqno + 1; i < inpkt->seqno; i++)
 410                                         n->late[(i / 8) % replaywin] |= 1 << i % 8;
 411                         }
 412                 }
 413
 414                 n->farfuture = 0;
 415                 n->late[(inpkt->seqno / 8) % replaywin] &= ~(1 << inpkt->seqno % 8);
 416         }
 417
 418         if(inpkt->seqno > n->received_seqno)
 419                 n->received_seqno = inpkt->seqno;
 420
 421         n->received++;
 422
 423         if(n->received_seqno > MAX_SEQNO)
 424                 regenerate_key();
 425
 426         /* Decompress the packet */
 427
 428         length_t origlen = inpkt->len;
 429
 430         if(n->incompression) {
 431                 outpkt = pkt[nextpkt++];
 432
 433                 if((outpkt->len = uncompress_packet(outpkt->data, inpkt->data, inpkt->len, n->incompression)) < 0) {
 434                         logger(DEBUG_TRAFFIC, LOG_ERR, "Error while uncompressing packet from %s (%s)",
 435                                                  n->name, n->hostname);
 436                         return;
 437                 }
 438
 439                 inpkt = outpkt;
 440
 441                 origlen -= MTU/64 + 20;
 442         }
 443
 444         inpkt->priority = 0;
 445
 446         if(!inpkt->data[12] && !inpkt->data[13])
 447                 mtu_probe_h(n, inpkt, origlen);
 448         else
 449                 receive_packet(n, inpkt);
 450 }
 451
 452 void receive_tcppacket(connection_t *c, const char *buffer, int len) {
 453         vpn_packet_t outpkt;
 454
 455         if(len > sizeof outpkt.data)
 456                 return;
 457
 458         outpkt.len = len;
 459         if(c->options & OPTION_TCPONLY)
 460                 outpkt.priority = 0;
 461         else
 462                 outpkt.priority = -1;
 463         memcpy(outpkt.data, buffer, len);
 464
 465         receive_packet(c->node, &outpkt);
 466 }
 467
 468 static void send_sptps_packet(node_t *n, vpn_packet_t *origpkt) {
 469         if(!n->status.validkey) {
 470                 logger(DEBUG_TRAFFIC, LOG_INFO, "No valid key known yet for %s (%s)", n->name, n->hostname);
 471                 if(!n->status.waitingforkey)
 472                         send_req_key(n);
 473                 else if(n->last_req_key + 10 < now.tv_sec) {
 474                         logger(DEBUG_ALWAYS, LOG_DEBUG, "No key from %s after 10 seconds, restarting SPTPS", n->name);
 475                         sptps_stop(&n->sptps);
 476                         n->status.waitingforkey = false;
 477                         send_req_key(n);
 478                 }
 479                 return;
 480         }
 481
 482         uint8_t type = 0;
 483         int offset = 0;
 484
 485         if(!(origpkt->data[12] | origpkt->data[13])) {
 486                 sptps_send_record(&n->sptps, PKT_PROBE, (char *)origpkt->data, origpkt->len);
 487                 return;
 488         }
 489
 490         if(routing_mode == RMODE_ROUTER)
 491                 offset = 14;
 492         else
 493                 type = PKT_MAC;
 494
 495         if(origpkt->len < offset)
 496                 return;
 497
 498         vpn_packet_t outpkt;
 499
 500         if(n->outcompression) {
 501                 int len = compress_packet(outpkt.data + offset, origpkt->data + offset, origpkt->len - offset, n->outcompression);
 502                 if(len < 0) {
 503                         logger(DEBUG_TRAFFIC, LOG_ERR, "Error while compressing packet to %s (%s)", n->name, n->hostname);
 504                 } else if(len < origpkt->len - offset) {
 505                         outpkt.len = len + offset;
 506                         origpkt = &outpkt;
 507                         type |= PKT_COMPRESSED;
 508                 }
 509         }
 510
 511         sptps_send_record(&n->sptps, type, (char *)origpkt->data + offset, origpkt->len - offset);
 512         return;
 513 }
 514
 515 static void choose_udp_address(const node_t *n, const sockaddr_t **sa, int *sock) {
 516         /* Latest guess */
 517         *sa = &n->address;
 518         *sock = n->sock;
 519
 520         /* If the UDP address is confirmed, use it. */
 521         if(n->status.udp_confirmed)
 522                 return;
 523
 524         /* Send every third packet to n->address; that could be set
 525            to the node's reflexive UDP address discovered during key
 526            exchange. */
 527
 528         static int x = 0;
 529         if(++x >= 3) {
 530                 x = 0;
 531                 return;
 532         }
 533
 534         /* Otherwise, address are found in edges to this node.
 535            So we pick a random edge and a random socket. */
 536
 537         int i = 0;
 538         int j = rand() % n->edge_tree->count;
 539         edge_t *candidate = NULL;
 540
 541         for splay_each(edge_t, e, n->edge_tree) {
 542                 if(i++ == j) {
 543                         candidate = e->reverse;
 544                         break;
 545                 }
 546         }
 547
 548         if(candidate) {
 549                 *sa = &candidate->address;
 550                 *sock = rand() % listen_sockets;
 551         }
 552
 553         /* Make sure we have a suitable socket for the chosen address */
 554         if(listen_socket[*sock].sa.sa.sa_family != (*sa)->sa.sa_family) {
 555                 for(int i = 0; i < listen_sockets; i++) {
 556                         if(listen_socket[i].sa.sa.sa_family == (*sa)->sa.sa_family) {
 557                                 *sock = i;
 558                                 break;
 559                         }
 560                 }
 561         }
 562 }
 563
 564 static void choose_broadcast_address(const node_t *n, const sockaddr_t **sa, int *sock) {
 565         static sockaddr_t broadcast_ipv4 = {
 566                 .in = {
 567                         .sin_family = AF_INET,
 568                         .sin_addr.s_addr = -1,
 569                 }
 570         };
 571
 572         static sockaddr_t broadcast_ipv6 = {
 573                 .in6 = {
 574                         .sin6_family = AF_INET6,
 575                         .sin6_addr.s6_addr[0x0] = 0xff,
 576                         .sin6_addr.s6_addr[0x1] = 0x02,
 577                         .sin6_addr.s6_addr[0xf] = 0x01,
 578                 }
 579         };
 580
 581         *sock = rand() % listen_sockets;
 582
 583         if(listen_socket[*sock].sa.sa.sa_family == AF_INET6) {
 584                 if(localdiscovery_address.sa.sa_family == AF_INET6) {
 585                         localdiscovery_address.in6.sin6_port = n->prevedge->address.in.sin_port;
 586                         *sa = &localdiscovery_address;
 587                 } else {
 588                         broadcast_ipv6.in6.sin6_port = n->prevedge->address.in.sin_port;
 589                         broadcast_ipv6.in6.sin6_scope_id = listen_socket[*sock].sa.in6.sin6_scope_id;
 590                         *sa = &broadcast_ipv6;
 591                 }
 592         } else {
 593                 if(localdiscovery_address.sa.sa_family == AF_INET) {
 594                         localdiscovery_address.in.sin_port = n->prevedge->address.in.sin_port;
 595                         *sa = &localdiscovery_address;
 596                 } else {
 597                         broadcast_ipv4.in.sin_port = n->prevedge->address.in.sin_port;
 598                         *sa = &broadcast_ipv4;
 599                 }
 600         }
 601 }
 602
 603 static void send_udppacket(node_t *n, vpn_packet_t *origpkt) {
 604         vpn_packet_t pkt1, pkt2;
 605         vpn_packet_t *pkt[] = { &pkt1, &pkt2, &pkt1, &pkt2 };
 606         vpn_packet_t *inpkt = origpkt;
 607         int nextpkt = 0;
 608         vpn_packet_t *outpkt;
 609         int origlen = origpkt->len;
 610         size_t outlen;
 611 #if defined(SOL_IP) && defined(IP_TOS)
 612         static int priority = 0;
 613 #endif
 614         int origpriority = origpkt->priority;
 615
 616         if(!n->status.reachable) {
 617                 logger(DEBUG_TRAFFIC, LOG_INFO, "Trying to send UDP packet to unreachable node %s (%s)", n->name, n->hostname);
 618                 return;
 619         }
 620
 621         if(n->status.sptps)
 622                 return send_sptps_packet(n, origpkt);
 623
 624         /* Make sure we have a valid key */
 625
 626         if(!n->status.validkey) {
 627                 logger(DEBUG_TRAFFIC, LOG_INFO,
 628                                    "No valid key known yet for %s (%s), forwarding via TCP",
 629                                    n->name, n->hostname);
 630
 631                 if(n->last_req_key + 10 <= now.tv_sec) {
 632                         send_req_key(n);
 633                         n->last_req_key = now.tv_sec;
 634                 }
 635
 636                 send_tcppacket(n->nexthop->connection, origpkt);
 637
 638                 return;
 639         }
 640
 641         if(n->options & OPTION_PMTU_DISCOVERY && inpkt->len > n->minmtu && (inpkt->data[12] | inpkt->data[13])) {
 642                 logger(DEBUG_TRAFFIC, LOG_INFO,
 643                                 "Packet for %s (%s) larger than minimum MTU, forwarding via %s",
 644                                 n->name, n->hostname, n != n->nexthop ? n->nexthop->name : "TCP");
 645
 646                 if(n != n->nexthop)
 647                         send_packet(n->nexthop, origpkt);
 648                 else
 649                         send_tcppacket(n->nexthop->connection, origpkt);
 650
 651                 return;
 652         }
 653
 654         /* Compress the packet */
 655
 656         if(n->outcompression) {
 657                 outpkt = pkt[nextpkt++];
 658
 659                 if((outpkt->len = compress_packet(outpkt->data, inpkt->data, inpkt->len, n->outcompression)) < 0) {
 660                         logger(DEBUG_TRAFFIC, LOG_ERR, "Error while compressing packet to %s (%s)",
 661                                    n->name, n->hostname);
 662                         return;
 663                 }
 664
 665                 inpkt = outpkt;
 666         }
 667
 668         /* Add sequence number */
 669
 670         inpkt->seqno = htonl(++(n->sent_seqno));
 671         inpkt->len += sizeof inpkt->seqno;
 672
 673         /* Encrypt the packet */
 674
 675         if(cipher_active(n->outcipher)) {
 676                 outpkt = pkt[nextpkt++];
 677                 outlen = MAXSIZE;
 678
 679                 if(!cipher_encrypt(n->outcipher, &inpkt->seqno, inpkt->len, &outpkt->seqno, &outlen, true)) {
 680                         logger(DEBUG_TRAFFIC, LOG_ERR, "Error while encrypting packet to %s (%s)", n->name, n->hostname);
 681                         goto end;
 682                 }
 683
 684                 outpkt->len = outlen;
 685                 inpkt = outpkt;
 686         }
 687
 688         /* Add the message authentication code */
 689
 690         if(digest_active(n->outdigest)) {
 691                 if(!digest_create(n->outdigest, &inpkt->seqno, inpkt->len, (char *)&inpkt->seqno + inpkt->len)) {
 692                         logger(DEBUG_TRAFFIC, LOG_ERR, "Error while encrypting packet to %s (%s)", n->name, n->hostname);
 693                         goto end;
 694                 }
 695
 696                 inpkt->len += digest_length(n->outdigest);
 697         }
 698
 699         /* Send the packet */
 700
 701         const sockaddr_t *sa;
 702         int sock;
 703
 704         /* Overloaded use of priority field: -1 means local broadcast */
 705
 706         if(origpriority == -1 && n->prevedge)
 707                 choose_broadcast_address(n, &sa, &sock);
 708         else
 709                 choose_udp_address(n, &sa, &sock);
 710
 711 #if defined(SOL_IP) && defined(IP_TOS)
 712         if(priorityinheritance && origpriority != priority
 713            && listen_socket[n->sock].sa.sa.sa_family == AF_INET) {
 714                 priority = origpriority;
 715                 logger(DEBUG_TRAFFIC, LOG_DEBUG, "Setting outgoing packet priority to %d", priority);
 716                 if(setsockopt(listen_socket[n->sock].udp.fd, SOL_IP, IP_TOS, &priority, sizeof(priority))) /* SO_PRIORITY doesn't seem to work */
 717                         logger(DEBUG_ALWAYS, LOG_ERR, "System call `%s' failed: %s", "setsockopt", strerror(errno));
 718         }
 719 #endif
 720
 721         if(sendto(listen_socket[sock].udp.fd, (char *) &inpkt->seqno, inpkt->len, 0, &sa->sa, SALEN(sa->sa)) < 0 && !sockwouldblock(sockerrno)) {
 722                 if(sockmsgsize(sockerrno)) {
 723                         if(n->maxmtu >= origlen)
 724                                 n->maxmtu = origlen - 1;
 725                         if(n->mtu >= origlen)
 726                                 n->mtu = origlen - 1;
 727                 } else
 728                         logger(DEBUG_TRAFFIC, LOG_WARNING, "Error sending packet to %s (%s): %s", n->name, n->hostname, sockstrerror(sockerrno));
 729         }
 730
 731 end:
 732         origpkt->len = origlen;
 733 }
 734
 735 bool send_sptps_data(void *handle, uint8_t type, const char *data, size_t len) {
 736         node_t *to = handle;
 737
 738         /* Send it via TCP if it is a handshake packet, TCPOnly is in use, or this packet is larger than the MTU. */
 739
 740         if(type >= SPTPS_HANDSHAKE || ((myself->options | to->options) & OPTION_TCPONLY) || (type != PKT_PROBE && len > to->minmtu)) {
 741                 char buf[len * 4 / 3 + 5];
 742                 b64encode(data, buf, len);
 743                 /* If no valid key is known yet, send the packets using ANS_KEY requests,
 744                    to ensure we get to learn the reflexive UDP address. */
 745                 if(!to->status.validkey)
 746                         return send_request(to->nexthop->connection, "%d %s %s %s -1 -1 -1 %d", ANS_KEY, myself->name, to->name, buf, myself->incompression);
 747                 else
 748                         return send_request(to->nexthop->connection, "%d %s %s %d %s", REQ_KEY, myself->name, to->name, REQ_SPTPS, buf);
 749         }
 750
 751         /* Otherwise, send the packet via UDP */
 752
 753         const sockaddr_t *sa;
 754         int sock;
 755
 756         choose_udp_address(to, &sa, &sock);
 757
 758         if(sendto(listen_socket[sock].udp.fd, data, len, 0, &sa->sa, SALEN(sa->sa)) < 0 && !sockwouldblock(sockerrno)) {
 759                 if(sockmsgsize(sockerrno)) {
 760                         if(to->maxmtu >= len)
 761                                 to->maxmtu = len - 1;
 762                         if(to->mtu >= len)
 763                                 to->mtu = len - 1;
 764                 } else {
 765                         logger(DEBUG_TRAFFIC, LOG_WARNING, "Error sending UDP SPTPS packet to %s (%s): %s", to->name, to->hostname, sockstrerror(sockerrno));
 766                         return false;
 767                 }
 768         }
 769
 770         return true;
 771 }
 772
 773 bool receive_sptps_record(void *handle, uint8_t type, const char *data, uint16_t len) {
 774         node_t *from = handle;
 775
 776         if(type == SPTPS_HANDSHAKE) {
 777                 if(!from->status.validkey) {
 778                         from->status.validkey = true;
 779                         from->status.waitingforkey = false;
 780                         logger(DEBUG_META, LOG_INFO, "SPTPS key exchange with %s (%s) succesful", from->name, from->hostname);
 781                 }
 782                 return true;
 783         }
 784
 785         if(len > MTU) {
 786                 logger(DEBUG_ALWAYS, LOG_ERR, "Packet from %s (%s) larger than maximum supported size (%d > %d)", from->name, from->hostname, len, MTU);
 787                 return false;
 788         }
 789
 790         vpn_packet_t inpkt;
 791
 792         if(type == PKT_PROBE) {
 793                 inpkt.len = len;
 794                 memcpy(inpkt.data, data, len);
 795                 mtu_probe_h(from, &inpkt, len);
 796                 return true;
 797         }
 798
 799         if(type & ~(PKT_COMPRESSED | PKT_MAC)) {
 800                 logger(DEBUG_ALWAYS, LOG_ERR, "Unexpected SPTPS record type %d len %d from %s (%s)", type, len, from->name, from->hostname);
 801                 return false;
 802         }
 803
 804         /* Check if we have the headers we need */
 805         if(routing_mode != RMODE_ROUTER && !(type & PKT_MAC)) {
 806                 logger(DEBUG_TRAFFIC, LOG_ERR, "Received packet from %s (%s) without MAC header (maybe Mode is not set correctly)", from->name, from->hostname);
 807                 return false;
 808         } else if(routing_mode == RMODE_ROUTER && (type & PKT_MAC)) {
 809                 logger(DEBUG_TRAFFIC, LOG_WARNING, "Received packet from %s (%s) with MAC header (maybe Mode is not set correctly)", from->name, from->hostname);
 810         }
 811
 812         int offset = (type & PKT_MAC) ? 0 : 14;
 813         if(type & PKT_COMPRESSED) {
 814                 length_t ulen = uncompress_packet(inpkt.data + offset, (const uint8_t *)data, len, from->incompression);
 815                 if(ulen < 0) {
 816                         return false;
 817                 } else {
 818                         inpkt.len = ulen + offset;
 819                 }
 820                 if(inpkt.len > MAXSIZE)
 821                         abort();
 822         } else {
 823                 memcpy(inpkt.data + offset, data, len);
 824                 inpkt.len = len + offset;
 825         }
 826
 827         /* Generate the Ethernet packet type if necessary */
 828         if(offset) {
 829                 switch(inpkt.data[14] >> 4) {
 830                         case 4:
 831                                 inpkt.data[12] = 0x08;
 832                                 inpkt.data[13] = 0x00;
 833                                 break;
 834                         case 6:
 835                                 inpkt.data[12] = 0x86;
 836                                 inpkt.data[13] = 0xDD;
 837                                 break;
 838                         default:
 839                                 logger(DEBUG_TRAFFIC, LOG_ERR,
 840                                                    "Unknown IP version %d while reading packet from %s (%s)",
 841                                                    inpkt.data[14] >> 4, from->name, from->hostname);
 842                                 return false;
 843                 }
 844         }
 845
 846         receive_packet(from, &inpkt);
 847         return true;
 848 }
 849
 850 /*
 851   send a packet to the given vpn ip.
 852 */
 853 void send_packet(node_t *n, vpn_packet_t *packet) {
 854         node_t *via;
 855
 856         if(n == myself) {
 857                 if(overwrite_mac)
 858                          memcpy(packet->data, mymac.x, ETH_ALEN);
 859                 n->out_packets++;
 860                 n->out_bytes += packet->len;
 861                 devops.write(packet);
 862                 return;
 863         }
 864
 865         logger(DEBUG_TRAFFIC, LOG_ERR, "Sending packet of %d bytes to %s (%s)",
 866                            packet->len, n->name, n->hostname);
 867
 868         if(!n->status.reachable) {
 869                 logger(DEBUG_TRAFFIC, LOG_INFO, "Node %s (%s) is not reachable",
 870                                    n->name, n->hostname);
 871                 return;
 872         }
 873
 874         n->out_packets++;
 875         n->out_bytes += packet->len;
 876
 877         if(n->status.sptps) {
 878                 send_sptps_packet(n, packet);
 879                 return;
 880         }
 881
 882         via = (packet->priority == -1 || n->via == myself) ? n->nexthop : n->via;
 883
 884         if(via != n)
 885                 logger(DEBUG_TRAFFIC, LOG_INFO, "Sending packet to %s via %s (%s)",
 886                            n->name, via->name, n->via->hostname);
 887
 888         if(packet->priority == -1 || ((myself->options | via->options) & OPTION_TCPONLY)) {
 889                 if(!send_tcppacket(via->connection, packet))
 890                         terminate_connection(via->connection, true);
 891         } else
 892                 send_udppacket(via, packet);
 893 }
 894
 895 /* Broadcast a packet using the minimum spanning tree */
 896
 897 void broadcast_packet(const node_t *from, vpn_packet_t *packet) {
 898         // Always give ourself a copy of the packet.
 899         if(from != myself)
 900                 send_packet(myself, packet);
 901
 902         // In TunnelServer mode, do not forward broadcast packets.
 903         // The MST might not be valid and create loops.
 904         if(tunnelserver || broadcast_mode == BMODE_NONE)
 905                 return;
 906
 907         logger(DEBUG_TRAFFIC, LOG_INFO, "Broadcasting packet of %d bytes from %s (%s)",
 908                            packet->len, from->name, from->hostname);
 909
 910         switch(broadcast_mode) {
 911                 // In MST mode, broadcast packets travel via the Minimum Spanning Tree.
 912                 // This guarantees all nodes receive the broadcast packet, and
 913                 // usually distributes the sending of broadcast packets over all nodes.
 914                 case BMODE_MST:
 915                         for list_each(connection_t, c, connection_list)
 916                                 if(c->status.active && c->status.mst && c != from->nexthop->connection)
 917                                         send_packet(c->node, packet);
 918                         break;
 919
 920                 // In direct mode, we send copies to each node we know of.
 921                 // However, this only reaches nodes that can be reached in a single hop.
 922                 // We don't have enough information to forward broadcast packets in this case.
 923                 case BMODE_DIRECT:
 924                         if(from != myself)
 925                                 break;
 926
 927                         for splay_each(node_t, n, node_tree)
 928                                 if(n->status.reachable && ((n->via == myself && n->nexthop == n) || n->via == n))
 929                                         send_packet(n, packet);
 930                         break;
 931
 932                 default:
 933                         break;
 934         }
 935 }
 936
 937 static node_t *try_harder(const sockaddr_t *from, const vpn_packet_t *pkt) {
 938         node_t *n = NULL;
 939         bool hard = false;
 940         static time_t last_hard_try = 0;
 941
 942         for splay_each(edge_t, e, edge_weight_tree) {
 943                 if(!e->to->status.reachable || e->to == myself)
 944                         continue;
 945
 946                 if(sockaddrcmp_noport(from, &e->address)) {
 947                         if(last_hard_try == now.tv_sec)
 948                                 continue;
 949                         hard = true;
 950                 }
 951
 952                 if(!try_mac(e->to, pkt))
 953                         continue;
 954
 955                 n = e->to;
 956                 break;
 957         }
 958
 959         if(hard)
 960                 last_hard_try = now.tv_sec;
 961
 962         last_hard_try = now.tv_sec;
 963         return n;
 964 }
 965
 966 void handle_incoming_vpn_data(void *data, int flags) {
 967         listen_socket_t *ls = data;
 968         vpn_packet_t pkt;
 969         char *hostname;
 970         sockaddr_t from = {{0}};
 971         socklen_t fromlen = sizeof from;
 972         node_t *n;
 973         int len;
 974
 975         len = recvfrom(ls->udp.fd, (char *) &pkt.seqno, MAXSIZE, 0, &from.sa, &fromlen);
 976
 977         if(len <= 0 || len > MAXSIZE) {
 978                 if(!sockwouldblock(sockerrno))
 979                         logger(DEBUG_ALWAYS, LOG_ERR, "Receiving packet failed: %s", sockstrerror(sockerrno));
 980                 return;
 981         }
 982
 983         pkt.len = len;
 984
 985         sockaddrunmap(&from); /* Some braindead IPv6 implementations do stupid things. */
 986
 987         n = lookup_node_udp(&from);
 988
 989         if(!n) {
 990                 n = try_harder(&from, &pkt);
 991                 if(n)
 992                         update_node_udp(n, &from);
 993                 else if(debug_level >= DEBUG_PROTOCOL) {
 994                         hostname = sockaddr2hostname(&from);
 995                         logger(DEBUG_PROTOCOL, LOG_WARNING, "Received UDP packet from unknown source %s", hostname);
 996                         free(hostname);
 997                         return;
 998                 }
 999                 else
1000                         return;
1001         }
1002
1003         n->sock = ls - listen_socket;
1004
1005         receive_udppacket(n, &pkt);
1006 }
1007
1008 void handle_device_data(void *data, int flags) {
1009         vpn_packet_t packet;
1010
1011         packet.priority = 0;
1012
1013         if(devops.read(&packet)) {
1014                 myself->in_packets++;
1015                 myself->in_bytes += packet.len;
1016                 route(myself, &packet);
1017         }
1018 }