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