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 = false;
  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         vpn_packet_t *outpkt = pkt[0];
 364         size_t outlen;
 365
 366         if(n->status.sptps) {
 367                 if(!n->sptps.state) {
 368                         if(!n->status.waitingforkey) {
 369                                 logger(DEBUG_TRAFFIC, LOG_DEBUG, "Got packet from %s (%s) but we haven't exchanged keys yet", n->name, n->hostname);
 370                                 send_req_key(n);
 371                         } else {
 372                                 logger(DEBUG_TRAFFIC, LOG_DEBUG, "Got packet from %s (%s) but he hasn't got our key yet", n->name, n->hostname);
 373                         }
 374                         return;
 375                 }
 376                 sptps_receive_data(&n->sptps, (char *)&inpkt->seqno, inpkt->len);
 377                 return;
 378         }
 379
 380         if(!n->status.validkey) {
 381                 logger(DEBUG_TRAFFIC, LOG_DEBUG, "Got packet from %s (%s) but he hasn't got our key yet", n->name, n->hostname);
 382                 return;
 383         }
 384
 385         /* Check packet length */
 386
 387         if(inpkt->len < sizeof inpkt->seqno + digest_length(n->indigest)) {
 388                 logger(DEBUG_TRAFFIC, LOG_DEBUG, "Got too short packet from %s (%s)",
 389                                         n->name, n->hostname);
 390                 return;
 391         }
 392
 393         /* Check the message authentication code */
 394
 395         if(digest_active(n->indigest)) {
 396                 inpkt->len -= digest_length(n->indigest);
 397                 if(!digest_verify(n->indigest, &inpkt->seqno, inpkt->len, (const char *)&inpkt->seqno + inpkt->len)) {
 398                         logger(DEBUG_TRAFFIC, LOG_DEBUG, "Got unauthenticated packet from %s (%s)", n->name, n->hostname);
 399                         return;
 400                 }
 401         }
 402         /* Decrypt the packet */
 403
 404         if(cipher_active(n->incipher)) {
 405                 outpkt = pkt[nextpkt++];
 406                 outlen = MAXSIZE;
 407
 408                 if(!cipher_decrypt(n->incipher, &inpkt->seqno, inpkt->len, &outpkt->seqno, &outlen, true)) {
 409                         logger(DEBUG_TRAFFIC, LOG_DEBUG, "Error decrypting packet from %s (%s)", n->name, n->hostname);
 410                         return;
 411                 }
 412
 413                 outpkt->len = outlen;
 414                 inpkt = outpkt;
 415         }
 416
 417         /* Check the sequence number */
 418
 419         inpkt->len -= sizeof inpkt->seqno;
 420         inpkt->seqno = ntohl(inpkt->seqno);
 421
 422         if(replaywin) {
 423                 if(inpkt->seqno != n->received_seqno + 1) {
 424                         if(inpkt->seqno >= n->received_seqno + replaywin * 8) {
 425                                 if(n->farfuture++ < replaywin >> 2) {
 426                                         logger(DEBUG_ALWAYS, LOG_WARNING, "Packet from %s (%s) is %d seqs in the future, dropped (%u)",
 427                                                 n->name, n->hostname, inpkt->seqno - n->received_seqno - 1, n->farfuture);
 428                                         return;
 429                                 }
 430                                 logger(DEBUG_ALWAYS, LOG_WARNING, "Lost %d packets from %s (%s)",
 431                                                 inpkt->seqno - n->received_seqno - 1, n->name, n->hostname);
 432                                 memset(n->late, 0, replaywin);
 433                         } else if (inpkt->seqno <= n->received_seqno) {
 434                                 if((n->received_seqno >= replaywin * 8 && inpkt->seqno <= n->received_seqno - replaywin * 8) || !(n->late[(inpkt->seqno / 8) % replaywin] & (1 << inpkt->seqno % 8))) {
 435                                         logger(DEBUG_ALWAYS, LOG_WARNING, "Got late or replayed packet from %s (%s), seqno %d, last received %d",
 436                                                 n->name, n->hostname, inpkt->seqno, n->received_seqno);
 437                                         return;
 438                                 }
 439                         } else {
 440                                 for(int i = n->received_seqno + 1; i < inpkt->seqno; i++)
 441                                         n->late[(i / 8) % replaywin] |= 1 << i % 8;
 442                         }
 443                 }
 444
 445                 n->farfuture = 0;
 446                 n->late[(inpkt->seqno / 8) % replaywin] &= ~(1 << inpkt->seqno % 8);
 447         }
 448
 449         if(inpkt->seqno > n->received_seqno)
 450                 n->received_seqno = inpkt->seqno;
 451
 452         n->received++;
 453
 454         if(n->received_seqno > MAX_SEQNO)
 455                 regenerate_key();
 456
 457         /* Decompress the packet */
 458
 459         length_t origlen = inpkt->len;
 460
 461         if(n->incompression) {
 462                 outpkt = pkt[nextpkt++];
 463
 464                 if((outpkt->len = uncompress_packet(outpkt->data, inpkt->data, inpkt->len, n->incompression)) < 0) {
 465                         logger(DEBUG_TRAFFIC, LOG_ERR, "Error while uncompressing packet from %s (%s)",
 466                                                  n->name, n->hostname);
 467                         return;
 468                 }
 469
 470                 inpkt = outpkt;
 471
 472                 origlen -= MTU/64 + 20;
 473         }
 474
 475         inpkt->priority = 0;
 476
 477         if(!inpkt->data[12] && !inpkt->data[13])
 478                 mtu_probe_h(n, inpkt, origlen);
 479         else
 480                 receive_packet(n, inpkt);
 481 }
 482
 483 void receive_tcppacket(connection_t *c, const char *buffer, int len) {
 484         vpn_packet_t outpkt;
 485
 486         if(len > sizeof outpkt.data)
 487                 return;
 488
 489         outpkt.len = len;
 490         if(c->options & OPTION_TCPONLY)
 491                 outpkt.priority = 0;
 492         else
 493                 outpkt.priority = -1;
 494         memcpy(outpkt.data, buffer, len);
 495
 496         receive_packet(c->node, &outpkt);
 497 }
 498
 499 static void send_sptps_packet(node_t *n, vpn_packet_t *origpkt) {
 500         if(!n->status.validkey) {
 501                 logger(DEBUG_TRAFFIC, LOG_INFO, "No valid key known yet for %s (%s)", n->name, n->hostname);
 502                 if(!n->status.waitingforkey)
 503                         send_req_key(n);
 504                 else if(n->last_req_key + 10 < now.tv_sec) {
 505                         logger(DEBUG_ALWAYS, LOG_DEBUG, "No key from %s after 10 seconds, restarting SPTPS", n->name);
 506                         sptps_stop(&n->sptps);
 507                         n->status.waitingforkey = false;
 508                         send_req_key(n);
 509                 }
 510                 return;
 511         }
 512
 513         uint8_t type = 0;
 514         int offset = 0;
 515
 516         if(!(origpkt->data[12] | origpkt->data[13])) {
 517                 sptps_send_record(&n->sptps, PKT_PROBE, (char *)origpkt->data, origpkt->len);
 518                 return;
 519         }
 520
 521         if(routing_mode == RMODE_ROUTER)
 522                 offset = 14;
 523         else
 524                 type = PKT_MAC;
 525
 526         if(origpkt->len < offset)
 527                 return;
 528
 529         vpn_packet_t outpkt;
 530
 531         if(n->outcompression) {
 532                 int len = compress_packet(outpkt.data + offset, origpkt->data + offset, origpkt->len - offset, n->outcompression);
 533                 if(len < 0) {
 534                         logger(DEBUG_TRAFFIC, LOG_ERR, "Error while compressing packet to %s (%s)", n->name, n->hostname);
 535                 } else if(len < origpkt->len - offset) {
 536                         outpkt.len = len + offset;
 537                         origpkt = &outpkt;
 538                         type |= PKT_COMPRESSED;
 539                 }
 540         }
 541
 542         sptps_send_record(&n->sptps, type, (char *)origpkt->data + offset, origpkt->len - offset);
 543         return;
 544 }
 545
 546 static void adapt_socket(const sockaddr_t *sa, int *sock) {
 547         /* Make sure we have a suitable socket for the chosen address */
 548         if(listen_socket[*sock].sa.sa.sa_family != sa->sa.sa_family) {
 549                 for(int i = 0; i < listen_sockets; i++) {
 550                         if(listen_socket[i].sa.sa.sa_family == sa->sa.sa_family) {
 551                                 *sock = i;
 552                                 break;
 553                         }
 554                 }
 555         }
 556 }
 557
 558 static void choose_udp_address(const node_t *n, const sockaddr_t **sa, int *sock) {
 559         /* Latest guess */
 560         *sa = &n->address;
 561         *sock = n->sock;
 562
 563         /* If the UDP address is confirmed, use it. */
 564         if(n->status.udp_confirmed)
 565                 return;
 566
 567         /* Send every third packet to n->address; that could be set
 568            to the node's reflexive UDP address discovered during key
 569            exchange. */
 570
 571         static int x = 0;
 572         if(++x >= 3) {
 573                 x = 0;
 574                 return;
 575         }
 576
 577         /* Otherwise, address are found in edges to this node.
 578            So we pick a random edge and a random socket. */
 579
 580         int i = 0;
 581         int j = rand() % n->edge_tree->count;
 582         edge_t *candidate = NULL;
 583
 584         for splay_each(edge_t, e, n->edge_tree) {
 585                 if(i++ == j) {
 586                         candidate = e->reverse;
 587                         break;
 588                 }
 589         }
 590
 591         if(candidate) {
 592                 *sa = &candidate->address;
 593                 *sock = rand() % listen_sockets;
 594         }
 595
 596         adapt_socket(*sa, sock);
 597 }
 598
 599 static void choose_local_address(const node_t *n, const sockaddr_t **sa, int *sock) {
 600         *sa = NULL;
 601
 602         /* Pick one of the edges from this node at random, then use its local address. */
 603
 604         int i = 0;
 605         int j = rand() % n->edge_tree->count;
 606         edge_t *candidate = NULL;
 607
 608         for splay_each(edge_t, e, n->edge_tree) {
 609                 if(i++ == j) {
 610                         candidate = e;
 611                         break;
 612                 }
 613         }
 614
 615         if (candidate && candidate->local_address.sa.sa_family) {
 616                 *sa = &candidate->local_address;
 617                 *sock = rand() % listen_sockets;
 618                 adapt_socket(*sa, sock);
 619         }
 620 }
 621
 622 static void send_udppacket(node_t *n, vpn_packet_t *origpkt) {
 623         vpn_packet_t pkt1, pkt2;
 624         vpn_packet_t *pkt[] = { &pkt1, &pkt2, &pkt1, &pkt2 };
 625         vpn_packet_t *inpkt = origpkt;
 626         int nextpkt = 0;
 627         vpn_packet_t *outpkt;
 628         int origlen = origpkt->len;
 629         size_t outlen;
 630 #if defined(SOL_IP) && defined(IP_TOS)
 631         static int priority = 0;
 632 #endif
 633         int origpriority = origpkt->priority;
 634
 635         if(!n->status.reachable) {
 636                 logger(DEBUG_TRAFFIC, LOG_INFO, "Trying to send UDP packet to unreachable node %s (%s)", n->name, n->hostname);
 637                 return;
 638         }
 639
 640         if(n->status.sptps)
 641                 return send_sptps_packet(n, origpkt);
 642
 643         /* Make sure we have a valid key */
 644
 645         if(!n->status.validkey) {
 646                 logger(DEBUG_TRAFFIC, LOG_INFO,
 647                                    "No valid key known yet for %s (%s), forwarding via TCP",
 648                                    n->name, n->hostname);
 649
 650                 if(n->last_req_key + 10 <= now.tv_sec) {
 651                         send_req_key(n);
 652                         n->last_req_key = now.tv_sec;
 653                 }
 654
 655                 send_tcppacket(n->nexthop->connection, origpkt);
 656
 657                 return;
 658         }
 659
 660         if(n->options & OPTION_PMTU_DISCOVERY && inpkt->len > n->minmtu && (inpkt->data[12] | inpkt->data[13])) {
 661                 logger(DEBUG_TRAFFIC, LOG_INFO,
 662                                 "Packet for %s (%s) larger than minimum MTU, forwarding via %s",
 663                                 n->name, n->hostname, n != n->nexthop ? n->nexthop->name : "TCP");
 664
 665                 if(n != n->nexthop)
 666                         send_packet(n->nexthop, origpkt);
 667                 else
 668                         send_tcppacket(n->nexthop->connection, origpkt);
 669
 670                 return;
 671         }
 672
 673         /* Compress the packet */
 674
 675         if(n->outcompression) {
 676                 outpkt = pkt[nextpkt++];
 677
 678                 if((outpkt->len = compress_packet(outpkt->data, inpkt->data, inpkt->len, n->outcompression)) < 0) {
 679                         logger(DEBUG_TRAFFIC, LOG_ERR, "Error while compressing packet to %s (%s)",
 680                                    n->name, n->hostname);
 681                         return;
 682                 }
 683
 684                 inpkt = outpkt;
 685         }
 686
 687         /* Add sequence number */
 688
 689         inpkt->seqno = htonl(++(n->sent_seqno));
 690         inpkt->len += sizeof inpkt->seqno;
 691
 692         /* Encrypt the packet */
 693
 694         if(cipher_active(n->outcipher)) {
 695                 outpkt = pkt[nextpkt++];
 696                 outlen = MAXSIZE;
 697
 698                 if(!cipher_encrypt(n->outcipher, &inpkt->seqno, inpkt->len, &outpkt->seqno, &outlen, true)) {
 699                         logger(DEBUG_TRAFFIC, LOG_ERR, "Error while encrypting packet to %s (%s)", n->name, n->hostname);
 700                         goto end;
 701                 }
 702
 703                 outpkt->len = outlen;
 704                 inpkt = outpkt;
 705         }
 706
 707         /* Add the message authentication code */
 708
 709         if(digest_active(n->outdigest)) {
 710                 if(!digest_create(n->outdigest, &inpkt->seqno, inpkt->len, (char *)&inpkt->seqno + inpkt->len)) {
 711                         logger(DEBUG_TRAFFIC, LOG_ERR, "Error while encrypting packet to %s (%s)", n->name, n->hostname);
 712                         goto end;
 713                 }
 714
 715                 inpkt->len += digest_length(n->outdigest);
 716         }
 717
 718         /* Send the packet */
 719
 720         const sockaddr_t *sa = NULL;
 721         int sock;
 722
 723         if(n->status.send_locally)
 724                 choose_local_address(n, &sa, &sock);
 725         if(!sa)
 726                 choose_udp_address(n, &sa, &sock);
 727
 728 #if defined(SOL_IP) && defined(IP_TOS)
 729         if(priorityinheritance && origpriority != priority
 730            && listen_socket[n->sock].sa.sa.sa_family == AF_INET) {
 731                 priority = origpriority;
 732                 logger(DEBUG_TRAFFIC, LOG_DEBUG, "Setting outgoing packet priority to %d", priority);
 733                 if(setsockopt(listen_socket[n->sock].udp.fd, SOL_IP, IP_TOS, &priority, sizeof(priority))) /* SO_PRIORITY doesn't seem to work */
 734                         logger(DEBUG_ALWAYS, LOG_ERR, "System call `%s' failed: %s", "setsockopt", sockstrerror(sockerrno));
 735         }
 736 #endif
 737
 738         if(sendto(listen_socket[sock].udp.fd, (char *) &inpkt->seqno, inpkt->len, 0, &sa->sa, SALEN(sa->sa)) < 0 && !sockwouldblock(sockerrno)) {
 739                 if(sockmsgsize(sockerrno)) {
 740                         if(n->maxmtu >= origlen)
 741                                 n->maxmtu = origlen - 1;
 742                         if(n->mtu >= origlen)
 743                                 n->mtu = origlen - 1;
 744                 } else
 745                         logger(DEBUG_TRAFFIC, LOG_WARNING, "Error sending packet to %s (%s): %s", n->name, n->hostname, sockstrerror(sockerrno));
 746         }
 747
 748 end:
 749         origpkt->len = origlen;
 750 }
 751
 752 bool send_sptps_data(void *handle, uint8_t type, const char *data, size_t len) {
 753         node_t *to = handle;
 754
 755         /* Send it via TCP if it is a handshake packet, TCPOnly is in use, or this packet is larger than the MTU. */
 756
 757         if(type >= SPTPS_HANDSHAKE || ((myself->options | to->options) & OPTION_TCPONLY) || (type != PKT_PROBE && (len - SPTPS_DATAGRAM_OVERHEAD) > to->minmtu)) {
 758                 char buf[len * 4 / 3 + 5];
 759                 b64encode(data, buf, len);
 760                 /* If no valid key is known yet, send the packets using ANS_KEY requests,
 761                    to ensure we get to learn the reflexive UDP address. */
 762                 if(!to->status.validkey) {
 763                         to->incompression = myself->incompression;
 764                         return send_request(to->nexthop->connection, "%d %s %s %s -1 -1 -1 %d", ANS_KEY, myself->name, to->name, buf, to->incompression);
 765                 } else {
 766                         return send_request(to->nexthop->connection, "%d %s %s %d %s", REQ_KEY, myself->name, to->name, REQ_SPTPS, buf);
 767                 }
 768         }
 769
 770         /* Otherwise, send the packet via UDP */
 771
 772         const sockaddr_t *sa;
 773         int sock;
 774
 775         if(to->status.send_locally)
 776                 choose_local_address(to, &sa, &sock);
 777         else
 778                 choose_udp_address(to, &sa, &sock);
 779
 780         if(sendto(listen_socket[sock].udp.fd, data, len, 0, &sa->sa, SALEN(sa->sa)) < 0 && !sockwouldblock(sockerrno)) {
 781                 if(sockmsgsize(sockerrno)) {
 782                         // Compensate for SPTPS overhead
 783                         len -= SPTPS_DATAGRAM_OVERHEAD;
 784                         if(to->maxmtu >= len)
 785                                 to->maxmtu = len - 1;
 786                         if(to->mtu >= len)
 787                                 to->mtu = len - 1;
 788                 } else {
 789                         logger(DEBUG_TRAFFIC, LOG_WARNING, "Error sending UDP SPTPS packet to %s (%s): %s", to->name, to->hostname, sockstrerror(sockerrno));
 790                         return false;
 791                 }
 792         }
 793
 794         return true;
 795 }
 796
 797 bool receive_sptps_record(void *handle, uint8_t type, const char *data, uint16_t len) {
 798         node_t *from = handle;
 799
 800         if(type == SPTPS_HANDSHAKE) {
 801                 if(!from->status.validkey) {
 802                         from->status.validkey = true;
 803                         from->status.waitingforkey = false;
 804                         logger(DEBUG_META, LOG_INFO, "SPTPS key exchange with %s (%s) succesful", from->name, from->hostname);
 805                 }
 806                 return true;
 807         }
 808
 809         if(len > MTU) {
 810                 logger(DEBUG_ALWAYS, LOG_ERR, "Packet from %s (%s) larger than maximum supported size (%d > %d)", from->name, from->hostname, len, MTU);
 811                 return false;
 812         }
 813
 814         vpn_packet_t inpkt;
 815
 816         if(type == PKT_PROBE) {
 817                 inpkt.len = len;
 818                 memcpy(inpkt.data, data, len);
 819                 mtu_probe_h(from, &inpkt, len);
 820                 return true;
 821         }
 822
 823         if(type & ~(PKT_COMPRESSED | PKT_MAC)) {
 824                 logger(DEBUG_ALWAYS, LOG_ERR, "Unexpected SPTPS record type %d len %d from %s (%s)", type, len, from->name, from->hostname);
 825                 return false;
 826         }
 827
 828         /* Check if we have the headers we need */
 829         if(routing_mode != RMODE_ROUTER && !(type & PKT_MAC)) {
 830                 logger(DEBUG_TRAFFIC, LOG_ERR, "Received packet from %s (%s) without MAC header (maybe Mode is not set correctly)", from->name, from->hostname);
 831                 return false;
 832         } else if(routing_mode == RMODE_ROUTER && (type & PKT_MAC)) {
 833                 logger(DEBUG_TRAFFIC, LOG_WARNING, "Received packet from %s (%s) with MAC header (maybe Mode is not set correctly)", from->name, from->hostname);
 834         }
 835
 836         int offset = (type & PKT_MAC) ? 0 : 14;
 837         if(type & PKT_COMPRESSED) {
 838                 length_t ulen = uncompress_packet(inpkt.data + offset, (const uint8_t *)data, len, from->incompression);
 839                 if(ulen < 0) {
 840                         return false;
 841                 } else {
 842                         inpkt.len = ulen + offset;
 843                 }
 844                 if(inpkt.len > MAXSIZE)
 845                         abort();
 846         } else {
 847                 memcpy(inpkt.data + offset, data, len);
 848                 inpkt.len = len + offset;
 849         }
 850
 851         /* Generate the Ethernet packet type if necessary */
 852         if(offset) {
 853                 switch(inpkt.data[14] >> 4) {
 854                         case 4:
 855                                 inpkt.data[12] = 0x08;
 856                                 inpkt.data[13] = 0x00;
 857                                 break;
 858                         case 6:
 859                                 inpkt.data[12] = 0x86;
 860                                 inpkt.data[13] = 0xDD;
 861                                 break;
 862                         default:
 863                                 logger(DEBUG_TRAFFIC, LOG_ERR,
 864                                                    "Unknown IP version %d while reading packet from %s (%s)",
 865                                                    inpkt.data[14] >> 4, from->name, from->hostname);
 866                                 return false;
 867                 }
 868         }
 869
 870         receive_packet(from, &inpkt);
 871         return true;
 872 }
 873
 874 /*
 875   send a packet to the given vpn ip.
 876 */
 877 void send_packet(node_t *n, vpn_packet_t *packet) {
 878         node_t *via;
 879
 880         if(n == myself) {
 881                 if(overwrite_mac)
 882                          memcpy(packet->data, mymac.x, ETH_ALEN);
 883                 n->out_packets++;
 884                 n->out_bytes += packet->len;
 885                 devops.write(packet);
 886                 return;
 887         }
 888
 889         logger(DEBUG_TRAFFIC, LOG_ERR, "Sending packet of %d bytes to %s (%s)",
 890                            packet->len, n->name, n->hostname);
 891
 892         if(!n->status.reachable) {
 893                 logger(DEBUG_TRAFFIC, LOG_INFO, "Node %s (%s) is not reachable",
 894                                    n->name, n->hostname);
 895                 return;
 896         }
 897
 898         n->out_packets++;
 899         n->out_bytes += packet->len;
 900
 901         if(n->status.sptps) {
 902                 send_sptps_packet(n, packet);
 903                 return;
 904         }
 905
 906         via = (packet->priority == -1 || n->via == myself) ? n->nexthop : n->via;
 907
 908         if(via != n)
 909                 logger(DEBUG_TRAFFIC, LOG_INFO, "Sending packet to %s via %s (%s)",
 910                            n->name, via->name, n->via->hostname);
 911
 912         if(packet->priority == -1 || ((myself->options | via->options) & OPTION_TCPONLY)) {
 913                 if(!send_tcppacket(via->connection, packet))
 914                         terminate_connection(via->connection, true);
 915         } else
 916                 send_udppacket(via, packet);
 917 }
 918
 919 /* Broadcast a packet using the minimum spanning tree */
 920
 921 void broadcast_packet(const node_t *from, vpn_packet_t *packet) {
 922         // Always give ourself a copy of the packet.
 923         if(from != myself)
 924                 send_packet(myself, packet);
 925
 926         // In TunnelServer mode, do not forward broadcast packets.
 927         // The MST might not be valid and create loops.
 928         if(tunnelserver || broadcast_mode == BMODE_NONE)
 929                 return;
 930
 931         logger(DEBUG_TRAFFIC, LOG_INFO, "Broadcasting packet of %d bytes from %s (%s)",
 932                            packet->len, from->name, from->hostname);
 933
 934         switch(broadcast_mode) {
 935                 // In MST mode, broadcast packets travel via the Minimum Spanning Tree.
 936                 // This guarantees all nodes receive the broadcast packet, and
 937                 // usually distributes the sending of broadcast packets over all nodes.
 938                 case BMODE_MST:
 939                         for list_each(connection_t, c, connection_list)
 940                                 if(c->status.active && c->status.mst && c != from->nexthop->connection)
 941                                         send_packet(c->node, packet);
 942                         break;
 943
 944                 // In direct mode, we send copies to each node we know of.
 945                 // However, this only reaches nodes that can be reached in a single hop.
 946                 // We don't have enough information to forward broadcast packets in this case.
 947                 case BMODE_DIRECT:
 948                         if(from != myself)
 949                                 break;
 950
 951                         for splay_each(node_t, n, node_tree)
 952                                 if(n->status.reachable && n != myself && ((n->via == myself && n->nexthop == n) || n->via == n))
 953                                         send_packet(n, packet);
 954                         break;
 955
 956                 default:
 957                         break;
 958         }
 959 }
 960
 961 static node_t *try_harder(const sockaddr_t *from, const vpn_packet_t *pkt) {
 962         node_t *n = NULL;
 963         bool hard = false;
 964         static time_t last_hard_try = 0;
 965
 966         for splay_each(edge_t, e, edge_weight_tree) {
 967                 if(!e->to->status.reachable || e->to == myself)
 968                         continue;
 969
 970                 if(sockaddrcmp_noport(from, &e->address)) {
 971                         if(last_hard_try == now.tv_sec)
 972                                 continue;
 973                         hard = true;
 974                 }
 975
 976                 if(!try_mac(e->to, pkt))
 977                         continue;
 978
 979                 n = e->to;
 980                 break;
 981         }
 982
 983         if(hard)
 984                 last_hard_try = now.tv_sec;
 985
 986         last_hard_try = now.tv_sec;
 987         return n;
 988 }
 989
 990 void handle_incoming_vpn_data(void *data, int flags) {
 991         listen_socket_t *ls = data;
 992         vpn_packet_t pkt;
 993         char *hostname;
 994         sockaddr_t from = {{0}};
 995         socklen_t fromlen = sizeof from;
 996         node_t *n;
 997         int len;
 998
 999         len = recvfrom(ls->udp.fd, (char *) &pkt.seqno, MAXSIZE, 0, &from.sa, &fromlen);
1000
1001         if(len <= 0 || len > MAXSIZE) {
1002                 if(!sockwouldblock(sockerrno))
1003                         logger(DEBUG_ALWAYS, LOG_ERR, "Receiving packet failed: %s", sockstrerror(sockerrno));
1004                 return;
1005         }
1006
1007         pkt.len = len;
1008
1009         sockaddrunmap(&from); /* Some braindead IPv6 implementations do stupid things. */
1010
1011         n = lookup_node_udp(&from);
1012
1013         if(!n) {
1014                 n = try_harder(&from, &pkt);
1015                 if(n)
1016                         update_node_udp(n, &from);
1017                 else if(debug_level >= DEBUG_PROTOCOL) {
1018                         hostname = sockaddr2hostname(&from);
1019                         logger(DEBUG_PROTOCOL, LOG_WARNING, "Received UDP packet from unknown source %s", hostname);
1020                         free(hostname);
1021                         return;
1022                 }
1023                 else
1024                         return;
1025         }
1026
1027         n->sock = ls - listen_socket;
1028
1029         receive_udppacket(n, &pkt);
1030 }
1031
1032 void handle_device_data(void *data, int flags) {
1033         vpn_packet_t packet;
1034
1035         packet.priority = 0;
1036
1037         if(devops.read(&packet)) {
1038                 myself->in_packets++;
1039                 myself->in_bytes += packet.len;
1040                 route(myself, &packet);
1041         }
1042 }