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