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 "process.h"
  46 #include "route.h"
  47 #include "utils.h"
  48 #include "xalloc.h"
  49
  50 int keylifetime = 0;
  51 #ifdef HAVE_LZO
  52 static char lzo_wrkmem[LZO1X_999_MEM_COMPRESS > LZO1X_1_MEM_COMPRESS ? LZO1X_999_MEM_COMPRESS : LZO1X_1_MEM_COMPRESS];
  53 #endif
  54
  55 static void send_udppacket(node_t *, vpn_packet_t *);
  56
  57 unsigned replaywin = 16;
  58 bool localdiscovery = false;
  59 sockaddr_t localdiscovery_address;
  60
  61 #define MAX_SEQNO 1073741824
  62
  63 /* mtuprobes == 1..30: initial discovery, send bursts with 1 second interval
  64    mtuprobes ==    31: sleep pinginterval seconds
  65    mtuprobes ==    32: send 1 burst, sleep pingtimeout second
  66    mtuprobes ==    33: no response from other side, restart PMTU discovery process
  67
  68    Probes are sent in batches of at least three, with random sizes between the
  69    lower and upper boundaries for the MTU thus far discovered.
  70
  71    After the initial discovery, a fourth packet is added to each batch with a
  72    size larger than the currently known PMTU, to test if the PMTU has increased.
  73
  74    In case local discovery is enabled, another packet is added to each batch,
  75    which will be broadcast to the local network.
  76
  77 */
  78
  79 static void send_mtu_probe_handler(void *data) {
  80         node_t *n = data;
  81         int timeout = 1;
  82
  83         n->mtuprobes++;
  84
  85         if(!n->status.reachable || !n->status.validkey) {
  86                 logger(DEBUG_TRAFFIC, LOG_INFO, "Trying to send MTU probe to unreachable or rekeying node %s (%s)", n->name, n->hostname);
  87                 n->mtuprobes = 0;
  88                 return;
  89         }
  90
  91         if(n->mtuprobes > 32) {
  92                 if(!n->minmtu) {
  93                         n->mtuprobes = 31;
  94                         timeout = pinginterval;
  95                         goto end;
  96                 }
  97
  98                 logger(DEBUG_TRAFFIC, LOG_INFO, "%s (%s) did not respond to UDP ping, restarting PMTU discovery", n->name, n->hostname);
  99                 n->status.udp_confirmed = false;
 100                 n->mtuprobes = 1;
 101                 n->minmtu = 0;
 102                 n->maxmtu = MTU;
 103         }
 104
 105         if(n->mtuprobes >= 10 && n->mtuprobes < 32 && !n->minmtu) {
 106                 logger(DEBUG_TRAFFIC, LOG_INFO, "No response to MTU probes from %s (%s)", n->name, n->hostname);
 107                 n->mtuprobes = 31;
 108         }
 109
 110         if(n->mtuprobes == 30 || (n->mtuprobes < 30 && n->minmtu >= n->maxmtu)) {
 111                 if(n->minmtu > n->maxmtu)
 112                         n->minmtu = n->maxmtu;
 113                 else
 114                         n->maxmtu = n->minmtu;
 115                 n->mtu = n->minmtu;
 116                 logger(DEBUG_TRAFFIC, LOG_INFO, "Fixing MTU of %s (%s) to %d after %d probes", n->name, n->hostname, n->mtu, n->mtuprobes);
 117                 n->mtuprobes = 31;
 118         }
 119
 120         if(n->mtuprobes == 31) {
 121                 timeout = pinginterval;
 122                 goto end;
 123         } else if(n->mtuprobes == 32) {
 124                 timeout = pingtimeout;
 125         }
 126
 127         for(int i = 0; i < 4 + localdiscovery; i++) {
 128                 int len;
 129
 130                 if(i == 0) {
 131                         if(n->mtuprobes < 30 || n->maxmtu + 8 >= MTU)
 132                                 continue;
 133                         len = n->maxmtu + 8;
 134                 } else if(n->maxmtu <= n->minmtu) {
 135                         len = n->maxmtu;
 136                 } else {
 137                         len = n->minmtu + 1 + rand() % (n->maxmtu - n->minmtu);
 138                 }
 139
 140                 if(len < 64)
 141                         len = 64;
 142
 143                 vpn_packet_t packet;
 144                 memset(packet.data, 0, 14);
 145                 randomize(packet.data + 14, len - 14);
 146                 packet.len = len;
 147                 if(i >= 4 && n->mtuprobes <= 10)
 148                         packet.priority = -1;
 149                 else
 150                         packet.priority = 0;
 151
 152                 logger(DEBUG_TRAFFIC, LOG_INFO, "Sending MTU probe length %d to %s (%s)", len, n->name, n->hostname);
 153
 154                 send_udppacket(n, &packet);
 155         }
 156
 157         n->probe_counter = 0;
 158         gettimeofday(&n->probe_time, NULL);
 159
 160         /* Calculate the packet loss of incoming traffic by comparing the rate of
 161            packets received to the rate with which the sequence number has increased.
 162          */
 163
 164         if(n->received > n->prev_received)
 165                 n->packetloss = 1.0 - (n->received - n->prev_received) / (float)(n->received_seqno - n->prev_received_seqno);
 166         else
 167                 n->packetloss = n->received_seqno <= n->prev_received_seqno;
 168
 169         n->prev_received_seqno = n->received_seqno;
 170         n->prev_received = n->received;
 171
 172 end:
 173         timeout_set(&n->mtutimeout, &(struct timeval){timeout, rand() % 100000});
 174 }
 175
 176 void send_mtu_probe(node_t *n) {
 177         timeout_add(&n->mtutimeout, send_mtu_probe_handler, n, &(struct timeval){1, 0});
 178         send_mtu_probe_handler(n);
 179 }
 180
 181 static void mtu_probe_h(node_t *n, vpn_packet_t *packet, length_t len) {
 182         if(!packet->data[0]) {
 183                 logger(DEBUG_TRAFFIC, LOG_INFO, "Got MTU probe request %d from %s (%s)", packet->len, n->name, n->hostname);
 184
 185                 /* It's a probe request, send back a reply */
 186
 187                 /* Type 2 probe replies were introduced in protocol 17.3 */
 188                 if ((n->options >> 24) == 3) {
 189                         uint8_t* data = packet->data;
 190                         *data++ = 2;
 191                         uint16_t len16 = htons(len); memcpy(data, &len16, 2); data += 2;
 192                         struct timeval now;
 193                         gettimeofday(&now, NULL);
 194                         uint32_t sec = htonl(now.tv_sec); memcpy(data, &sec, 4); data += 4;
 195                         uint32_t usec = htonl(now.tv_usec); memcpy(data, &usec, 4); data += 4;
 196                         packet->len = data - packet->data;
 197                 } else {
 198                         /* Legacy protocol: n won't understand type 2 probe replies. */
 199                         packet->data[0] = 1;
 200                 }
 201
 202                 /* Temporarily set udp_confirmed, so that the reply is sent
 203                    back exactly the way it came in. */
 204
 205                 bool udp_confirmed = n->status.udp_confirmed;
 206                 n->status.udp_confirmed = true;
 207                 send_udppacket(n, packet);
 208                 n->status.udp_confirmed = udp_confirmed;
 209         } else {
 210                 length_t probelen = len;
 211                 if (packet->data[0] == 2) {
 212                         if (len < 3)
 213                                 logger(DEBUG_TRAFFIC, LOG_WARNING, "Received invalid (too short) MTU probe reply from %s (%s)", n->name, n->hostname);
 214                         else {
 215                                 uint16_t probelen16; memcpy(&probelen16, packet->data + 1, 2); probelen = ntohs(probelen16);
 216                         }
 217                 }
 218                 logger(DEBUG_TRAFFIC, LOG_INFO, "Got type %d MTU probe reply %d from %s (%s)", packet->data[0], probelen, n->name, n->hostname);
 219
 220                 /* It's a valid reply: now we know bidirectional communication
 221                    is possible using the address and socket that the reply
 222                    packet used. */
 223
 224                 n->status.udp_confirmed = true;
 225
 226                 /* If we haven't established the PMTU yet, restart the discovery process. */
 227
 228                 if(n->mtuprobes > 30) {
 229                         if (probelen == n->maxmtu + 8) {
 230                                 logger(DEBUG_TRAFFIC, LOG_INFO, "Increase in PMTU to %s (%s) detected, restarting PMTU discovery", n->name, n->hostname);
 231                                 n->maxmtu = MTU;
 232                                 n->mtuprobes = 10;
 233                                 return;
 234                         }
 235
 236                         if(n->minmtu)
 237                                 n->mtuprobes = 30;
 238                         else
 239                                 n->mtuprobes = 1;
 240                 }
 241
 242                 /* If applicable, raise the minimum supported MTU */
 243
 244                 if(probelen > n->maxmtu)
 245                         probelen = n->maxmtu;
 246                 if(n->minmtu < probelen)
 247                         n->minmtu = probelen;
 248
 249                 /* Calculate RTT and bandwidth.
 250                    The RTT is the time between the MTU probe burst was sent and the first
 251                    reply is received. The bandwidth is measured using the time between the
 252                    arrival of the first and third probe reply (or type 2 probe requests).
 253                  */
 254
 255                 struct timeval now, diff;
 256                 gettimeofday(&now, NULL);
 257                 timersub(&now, &n->probe_time, &diff);
 258
 259                 struct timeval probe_timestamp = now;
 260                 if (packet->data[0] == 2 && packet->len >= 11) {
 261                         uint32_t sec; memcpy(&sec, packet->data + 3, 4);
 262                         uint32_t usec; memcpy(&usec, packet->data + 7, 4);
 263                         probe_timestamp.tv_sec = ntohl(sec);
 264                         probe_timestamp.tv_usec = ntohl(usec);
 265                 }
 266
 267                 n->probe_counter++;
 268
 269                 if(n->probe_counter == 1) {
 270                         n->rtt = diff.tv_sec + diff.tv_usec * 1e-6;
 271                         n->probe_time = probe_timestamp;
 272                 } else if(n->probe_counter == 3) {
 273                         struct timeval probe_timestamp_diff;
 274                         timersub(&probe_timestamp, &n->probe_time, &probe_timestamp_diff);
 275                         n->bandwidth = 2.0 * probelen / (probe_timestamp_diff.tv_sec + probe_timestamp_diff.tv_usec * 1e-6);
 276                         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);
 277                 }
 278         }
 279 }
 280
 281 static length_t compress_packet(uint8_t *dest, const uint8_t *source, length_t len, int level) {
 282         if(level == 0) {
 283                 memcpy(dest, source, len);
 284                 return len;
 285         } else if(level == 10) {
 286 #ifdef HAVE_LZO
 287                 lzo_uint lzolen = MAXSIZE;
 288                 lzo1x_1_compress(source, len, dest, &lzolen, lzo_wrkmem);
 289                 return lzolen;
 290 #else
 291                 return -1;
 292 #endif
 293         } else if(level < 10) {
 294 #ifdef HAVE_ZLIB
 295                 unsigned long destlen = MAXSIZE;
 296                 if(compress2(dest, &destlen, source, len, level) == Z_OK)
 297                         return destlen;
 298                 else
 299 #endif
 300                         return -1;
 301         } else {
 302 #ifdef HAVE_LZO
 303                 lzo_uint lzolen = MAXSIZE;
 304                 lzo1x_999_compress(source, len, dest, &lzolen, lzo_wrkmem);
 305                 return lzolen;
 306 #else
 307                 return -1;
 308 #endif
 309         }
 310
 311         return -1;
 312 }
 313
 314 static length_t uncompress_packet(uint8_t *dest, const uint8_t *source, length_t len, int level) {
 315         if(level == 0) {
 316                 memcpy(dest, source, len);
 317                 return len;
 318         } else if(level > 9) {
 319 #ifdef HAVE_LZO
 320                 lzo_uint lzolen = MAXSIZE;
 321                 if(lzo1x_decompress_safe(source, len, dest, &lzolen, NULL) == LZO_E_OK)
 322                         return lzolen;
 323                 else
 324 #endif
 325                         return -1;
 326         }
 327 #ifdef HAVE_ZLIB
 328         else {
 329                 unsigned long destlen = MAXSIZE;
 330                 if(uncompress(dest, &destlen, source, len) == Z_OK)
 331                         return destlen;
 332                 else
 333                         return -1;
 334         }
 335 #endif
 336
 337         return -1;
 338 }
 339
 340 /* VPN packet I/O */
 341
 342 static void receive_packet(node_t *n, vpn_packet_t *packet) {
 343         logger(DEBUG_TRAFFIC, LOG_DEBUG, "Received packet of %d bytes from %s (%s)",
 344                            packet->len, n->name, n->hostname);
 345
 346         n->in_packets++;
 347         n->in_bytes += packet->len;
 348
 349         route(n, packet);
 350 }
 351
 352 static bool try_mac(node_t *n, const vpn_packet_t *inpkt) {
 353         if(n->status.sptps)
 354                 return sptps_verify_datagram(&n->sptps, (char *)&inpkt->seqno, inpkt->len);
 355
 356         if(!digest_active(n->indigest) || inpkt->len < sizeof inpkt->seqno + digest_length(n->indigest))
 357                 return false;
 358
 359         return digest_verify(n->indigest, &inpkt->seqno, inpkt->len - digest_length(n->indigest), (const char *)&inpkt->seqno + inpkt->len - digest_length(n->indigest));
 360 }
 361
 362 static void receive_udppacket(node_t *n, vpn_packet_t *inpkt) {
 363         vpn_packet_t pkt1, pkt2;
 364         vpn_packet_t *pkt[] = { &pkt1, &pkt2, &pkt1, &pkt2 };
 365         int nextpkt = 0;
 366         vpn_packet_t *outpkt = pkt[0];
 367         size_t outlen;
 368
 369         if(n->status.sptps) {
 370                 if(!n->sptps.state) {
 371                         if(!n->status.waitingforkey) {
 372                                 logger(DEBUG_TRAFFIC, LOG_DEBUG, "Got packet from %s (%s) but we haven't exchanged keys yet", n->name, n->hostname);
 373                                 send_req_key(n);
 374                         } else {
 375                                 logger(DEBUG_TRAFFIC, LOG_DEBUG, "Got packet from %s (%s) but he hasn't got our key yet", n->name, n->hostname);
 376                         }
 377                         return;
 378                 }
 379                 sptps_receive_data(&n->sptps, (char *)&inpkt->seqno, inpkt->len);
 380                 return;
 381         }
 382
 383         if(!cipher_active(n->incipher)) {
 384                 logger(DEBUG_TRAFFIC, LOG_DEBUG, "Got packet from %s (%s) but he hasn't got our key yet", n->name, n->hostname);
 385                 return;
 386         }
 387
 388         /* Check packet length */
 389
 390         if(inpkt->len < sizeof inpkt->seqno + digest_length(n->indigest)) {
 391                 logger(DEBUG_TRAFFIC, LOG_DEBUG, "Got too short packet from %s (%s)",
 392                                         n->name, n->hostname);
 393                 return;
 394         }
 395
 396         /* Check the message authentication code */
 397
 398         if(digest_active(n->indigest)) {
 399                 inpkt->len -= digest_length(n->indigest);
 400                 if(!digest_verify(n->indigest, &inpkt->seqno, inpkt->len, (const char *)&inpkt->seqno + inpkt->len)) {
 401                         logger(DEBUG_TRAFFIC, LOG_DEBUG, "Got unauthenticated packet from %s (%s)", n->name, n->hostname);
 402                         return;
 403                 }
 404         }
 405         /* Decrypt the packet */
 406
 407         if(cipher_active(n->incipher)) {
 408                 outpkt = pkt[nextpkt++];
 409                 outlen = MAXSIZE;
 410
 411                 if(!cipher_decrypt(n->incipher, &inpkt->seqno, inpkt->len, &outpkt->seqno, &outlen, true)) {
 412                         logger(DEBUG_TRAFFIC, LOG_DEBUG, "Error decrypting packet from %s (%s)", n->name, n->hostname);
 413                         return;
 414                 }
 415
 416                 outpkt->len = outlen;
 417                 inpkt = outpkt;
 418         }
 419
 420         /* Check the sequence number */
 421
 422         inpkt->len -= sizeof inpkt->seqno;
 423         inpkt->seqno = ntohl(inpkt->seqno);
 424
 425         if(replaywin) {
 426                 if(inpkt->seqno != n->received_seqno + 1) {
 427                         if(inpkt->seqno >= n->received_seqno + replaywin * 8) {
 428                                 if(n->farfuture++ < replaywin >> 2) {
 429                                         logger(DEBUG_ALWAYS, LOG_WARNING, "Packet from %s (%s) is %d seqs in the future, dropped (%u)",
 430                                                 n->name, n->hostname, inpkt->seqno - n->received_seqno - 1, n->farfuture);
 431                                         return;
 432                                 }
 433                                 logger(DEBUG_ALWAYS, LOG_WARNING, "Lost %d packets from %s (%s)",
 434                                                 inpkt->seqno - n->received_seqno - 1, n->name, n->hostname);
 435                                 memset(n->late, 0, replaywin);
 436                         } else if (inpkt->seqno <= n->received_seqno) {
 437                                 if((n->received_seqno >= replaywin * 8 && inpkt->seqno <= n->received_seqno - replaywin * 8) || !(n->late[(inpkt->seqno / 8) % replaywin] & (1 << inpkt->seqno % 8))) {
 438                                         logger(DEBUG_ALWAYS, LOG_WARNING, "Got late or replayed packet from %s (%s), seqno %d, last received %d",
 439                                                 n->name, n->hostname, inpkt->seqno, n->received_seqno);
 440                                         return;
 441                                 }
 442                         } else {
 443                                 for(int i = n->received_seqno + 1; i < inpkt->seqno; i++)
 444                                         n->late[(i / 8) % replaywin] |= 1 << i % 8;
 445                         }
 446                 }
 447
 448                 n->farfuture = 0;
 449                 n->late[(inpkt->seqno / 8) % replaywin] &= ~(1 << inpkt->seqno % 8);
 450         }
 451
 452         if(inpkt->seqno > n->received_seqno)
 453                 n->received_seqno = inpkt->seqno;
 454
 455         n->received++;
 456
 457         if(n->received_seqno > MAX_SEQNO)
 458                 regenerate_key();
 459
 460         /* Decompress the packet */
 461
 462         length_t origlen = inpkt->len;
 463
 464         if(n->incompression) {
 465                 outpkt = pkt[nextpkt++];
 466
 467                 if((outpkt->len = uncompress_packet(outpkt->data, inpkt->data, inpkt->len, n->incompression)) < 0) {
 468                         logger(DEBUG_TRAFFIC, LOG_ERR, "Error while uncompressing packet from %s (%s)",
 469                                                  n->name, n->hostname);
 470                         return;
 471                 }
 472
 473                 inpkt = outpkt;
 474
 475                 origlen -= MTU/64 + 20;
 476         }
 477
 478         inpkt->priority = 0;
 479
 480         if(!inpkt->data[12] && !inpkt->data[13])
 481                 mtu_probe_h(n, inpkt, origlen);
 482         else
 483                 receive_packet(n, inpkt);
 484 }
 485
 486 void receive_tcppacket(connection_t *c, const char *buffer, int len) {
 487         vpn_packet_t outpkt;
 488
 489         if(len > sizeof outpkt.data)
 490                 return;
 491
 492         outpkt.len = len;
 493         if(c->options & OPTION_TCPONLY)
 494                 outpkt.priority = 0;
 495         else
 496                 outpkt.priority = -1;
 497         memcpy(outpkt.data, buffer, len);
 498
 499         receive_packet(c->node, &outpkt);
 500 }
 501
 502 static void send_sptps_packet(node_t *n, vpn_packet_t *origpkt) {
 503         if(!n->status.validkey) {
 504                 logger(DEBUG_TRAFFIC, LOG_INFO, "No valid key known yet for %s (%s)", n->name, n->hostname);
 505                 if(!n->status.waitingforkey)
 506                         send_req_key(n);
 507                 else if(n->last_req_key + 10 < now.tv_sec) {
 508                         logger(DEBUG_ALWAYS, LOG_DEBUG, "No key from %s after 10 seconds, restarting SPTPS", n->name);
 509                         sptps_stop(&n->sptps);
 510                         n->status.waitingforkey = false;
 511                         send_req_key(n);
 512                 }
 513                 return;
 514         }
 515
 516         uint8_t type = 0;
 517         int offset = 0;
 518
 519         if(!(origpkt->data[12] | origpkt->data[13])) {
 520                 sptps_send_record(&n->sptps, PKT_PROBE, (char *)origpkt->data, origpkt->len);
 521                 return;
 522         }
 523
 524         if(routing_mode == RMODE_ROUTER)
 525                 offset = 14;
 526         else
 527                 type = PKT_MAC;
 528
 529         if(origpkt->len < offset)
 530                 return;
 531
 532         vpn_packet_t outpkt;
 533
 534         if(n->outcompression) {
 535                 int len = compress_packet(outpkt.data + offset, origpkt->data + offset, origpkt->len - offset, n->outcompression);
 536                 if(len < 0) {
 537                         logger(DEBUG_TRAFFIC, LOG_ERR, "Error while compressing packet to %s (%s)", n->name, n->hostname);
 538                 } else if(len < origpkt->len - offset) {
 539                         outpkt.len = len + offset;
 540                         origpkt = &outpkt;
 541                         type |= PKT_COMPRESSED;
 542                 }
 543         }
 544
 545         sptps_send_record(&n->sptps, type, (char *)origpkt->data + offset, origpkt->len - offset);
 546         return;
 547 }
 548
 549 static void choose_udp_address(const node_t *n, const sockaddr_t **sa, int *sock) {
 550         /* Latest guess */
 551         *sa = &n->address;
 552         *sock = n->sock;
 553
 554         /* If the UDP address is confirmed, use it. */
 555         if(n->status.udp_confirmed)
 556                 return;
 557
 558         /* Send every third packet to n->address; that could be set
 559            to the node's reflexive UDP address discovered during key
 560            exchange. */
 561
 562         static int x = 0;
 563         if(++x >= 3) {
 564                 x = 0;
 565                 return;
 566         }
 567
 568         /* Otherwise, address are found in edges to this node.
 569            So we pick a random edge and a random socket. */
 570
 571         int i = 0;
 572         int j = rand() % n->edge_tree->count;
 573         edge_t *candidate = NULL;
 574
 575         for splay_each(edge_t, e, n->edge_tree) {
 576                 if(i++ == j) {
 577                         candidate = e->reverse;
 578                         break;
 579                 }
 580         }
 581
 582         if(candidate) {
 583                 *sa = &candidate->address;
 584                 *sock = rand() % listen_sockets;
 585         }
 586
 587         /* Make sure we have a suitable socket for the chosen address */
 588         if(listen_socket[*sock].sa.sa.sa_family != (*sa)->sa.sa_family) {
 589                 for(int i = 0; i < listen_sockets; i++) {
 590                         if(listen_socket[i].sa.sa.sa_family == (*sa)->sa.sa_family) {
 591                                 *sock = i;
 592                                 break;
 593                         }
 594                 }
 595         }
 596 }
 597
 598 static void choose_broadcast_address(const node_t *n, const sockaddr_t **sa, int *sock) {
 599         static sockaddr_t broadcast_ipv4 = {
 600                 .in = {
 601                         .sin_family = AF_INET,
 602                         .sin_addr.s_addr = -1,
 603                 }
 604         };
 605
 606         static sockaddr_t broadcast_ipv6 = {
 607                 .in6 = {
 608                         .sin6_family = AF_INET6,
 609                         .sin6_addr.s6_addr[0x0] = 0xff,
 610                         .sin6_addr.s6_addr[0x1] = 0x02,
 611                         .sin6_addr.s6_addr[0xf] = 0x01,
 612                 }
 613         };
 614
 615         *sock = rand() % listen_sockets;
 616
 617         if(listen_socket[*sock].sa.sa.sa_family == AF_INET6) {
 618                 if(localdiscovery_address.sa.sa_family == AF_INET6) {
 619                         localdiscovery_address.in6.sin6_port = n->prevedge->address.in.sin_port;
 620                         *sa = &localdiscovery_address;
 621                 } else {
 622                         broadcast_ipv6.in6.sin6_port = n->prevedge->address.in.sin_port;
 623                         broadcast_ipv6.in6.sin6_scope_id = listen_socket[*sock].sa.in6.sin6_scope_id;
 624                         *sa = &broadcast_ipv6;
 625                 }
 626         } else {
 627                 if(localdiscovery_address.sa.sa_family == AF_INET) {
 628                         localdiscovery_address.in.sin_port = n->prevedge->address.in.sin_port;
 629                         *sa = &localdiscovery_address;
 630                 } else {
 631                         broadcast_ipv4.in.sin_port = n->prevedge->address.in.sin_port;
 632                         *sa = &broadcast_ipv4;
 633                 }
 634         }
 635 }
 636
 637 static void send_udppacket(node_t *n, vpn_packet_t *origpkt) {
 638         vpn_packet_t pkt1, pkt2;
 639         vpn_packet_t *pkt[] = { &pkt1, &pkt2, &pkt1, &pkt2 };
 640         vpn_packet_t *inpkt = origpkt;
 641         int nextpkt = 0;
 642         vpn_packet_t *outpkt;
 643         int origlen = origpkt->len;
 644         size_t outlen;
 645 #if defined(SOL_IP) && defined(IP_TOS)
 646         static int priority = 0;
 647 #endif
 648         int origpriority = origpkt->priority;
 649
 650         if(!n->status.reachable) {
 651                 logger(DEBUG_TRAFFIC, LOG_INFO, "Trying to send UDP packet to unreachable node %s (%s)", n->name, n->hostname);
 652                 return;
 653         }
 654
 655         if(n->status.sptps)
 656                 return send_sptps_packet(n, origpkt);
 657
 658         /* Make sure we have a valid key */
 659
 660         if(!n->status.validkey) {
 661                 logger(DEBUG_TRAFFIC, LOG_INFO,
 662                                    "No valid key known yet for %s (%s), forwarding via TCP",
 663                                    n->name, n->hostname);
 664
 665                 if(n->last_req_key + 10 <= now.tv_sec) {
 666                         send_req_key(n);
 667                         n->last_req_key = now.tv_sec;
 668                 }
 669
 670                 send_tcppacket(n->nexthop->connection, origpkt);
 671
 672                 return;
 673         }
 674
 675         if(n->options & OPTION_PMTU_DISCOVERY && inpkt->len > n->minmtu && (inpkt->data[12] | inpkt->data[13])) {
 676                 logger(DEBUG_TRAFFIC, LOG_INFO,
 677                                 "Packet for %s (%s) larger than minimum MTU, forwarding via %s",
 678                                 n->name, n->hostname, n != n->nexthop ? n->nexthop->name : "TCP");
 679
 680                 if(n != n->nexthop)
 681                         send_packet(n->nexthop, origpkt);
 682                 else
 683                         send_tcppacket(n->nexthop->connection, origpkt);
 684
 685                 return;
 686         }
 687
 688         /* Compress the packet */
 689
 690         if(n->outcompression) {
 691                 outpkt = pkt[nextpkt++];
 692
 693                 if((outpkt->len = compress_packet(outpkt->data, inpkt->data, inpkt->len, n->outcompression)) < 0) {
 694                         logger(DEBUG_TRAFFIC, LOG_ERR, "Error while compressing packet to %s (%s)",
 695                                    n->name, n->hostname);
 696                         return;
 697                 }
 698
 699                 inpkt = outpkt;
 700         }
 701
 702         /* Add sequence number */
 703
 704         inpkt->seqno = htonl(++(n->sent_seqno));
 705         inpkt->len += sizeof inpkt->seqno;
 706
 707         /* Encrypt the packet */
 708
 709         if(cipher_active(n->outcipher)) {
 710                 outpkt = pkt[nextpkt++];
 711                 outlen = MAXSIZE;
 712
 713                 if(!cipher_encrypt(n->outcipher, &inpkt->seqno, inpkt->len, &outpkt->seqno, &outlen, true)) {
 714                         logger(DEBUG_TRAFFIC, LOG_ERR, "Error while encrypting packet to %s (%s)", n->name, n->hostname);
 715                         goto end;
 716                 }
 717
 718                 outpkt->len = outlen;
 719                 inpkt = outpkt;
 720         }
 721
 722         /* Add the message authentication code */
 723
 724         if(digest_active(n->outdigest)) {
 725                 if(!digest_create(n->outdigest, &inpkt->seqno, inpkt->len, (char *)&inpkt->seqno + inpkt->len)) {
 726                         logger(DEBUG_TRAFFIC, LOG_ERR, "Error while encrypting packet to %s (%s)", n->name, n->hostname);
 727                         goto end;
 728                 }
 729
 730                 inpkt->len += digest_length(n->outdigest);
 731         }
 732
 733         /* Send the packet */
 734
 735         const sockaddr_t *sa;
 736         int sock;
 737
 738         /* Overloaded use of priority field: -1 means local broadcast */
 739
 740         if(origpriority == -1 && n->prevedge)
 741                 choose_broadcast_address(n, &sa, &sock);
 742         else
 743                 choose_udp_address(n, &sa, &sock);
 744
 745 #if defined(SOL_IP) && defined(IP_TOS)
 746         if(priorityinheritance && origpriority != priority
 747            && listen_socket[n->sock].sa.sa.sa_family == AF_INET) {
 748                 priority = origpriority;
 749                 logger(DEBUG_TRAFFIC, LOG_DEBUG, "Setting outgoing packet priority to %d", priority);
 750                 if(setsockopt(listen_socket[n->sock].udp.fd, SOL_IP, IP_TOS, &priority, sizeof(priority))) /* SO_PRIORITY doesn't seem to work */
 751                         logger(DEBUG_ALWAYS, LOG_ERR, "System call `%s' failed: %s", "setsockopt", strerror(errno));
 752         }
 753 #endif
 754
 755         if(sendto(listen_socket[sock].udp.fd, (char *) &inpkt->seqno, inpkt->len, 0, &sa->sa, SALEN(sa->sa)) < 0 && !sockwouldblock(sockerrno)) {
 756                 if(sockmsgsize(sockerrno)) {
 757                         if(n->maxmtu >= origlen)
 758                                 n->maxmtu = origlen - 1;
 759                         if(n->mtu >= origlen)
 760                                 n->mtu = origlen - 1;
 761                 } else
 762                         logger(DEBUG_TRAFFIC, LOG_WARNING, "Error sending packet to %s (%s): %s", n->name, n->hostname, sockstrerror(sockerrno));
 763         }
 764
 765 end:
 766         origpkt->len = origlen;
 767 }
 768
 769 bool send_sptps_data(void *handle, uint8_t type, const char *data, size_t len) {
 770         node_t *to = handle;
 771
 772         /* Send it via TCP if it is a handshake packet, TCPOnly is in use, or this packet is larger than the MTU. */
 773
 774         if(type >= SPTPS_HANDSHAKE || ((myself->options | to->options) & OPTION_TCPONLY) || (type != PKT_PROBE && len > to->minmtu)) {
 775                 char buf[len * 4 / 3 + 5];
 776                 b64encode(data, buf, len);
 777                 /* If no valid key is known yet, send the packets using ANS_KEY requests,
 778                    to ensure we get to learn the reflexive UDP address. */
 779                 if(!to->status.validkey) {
 780                         to->incompression = myself->incompression;
 781                         return send_request(to->nexthop->connection, "%d %s %s %s -1 -1 -1 %d", ANS_KEY, myself->name, to->name, buf, to->incompression);
 782                 } else {
 783                         return send_request(to->nexthop->connection, "%d %s %s %d %s", REQ_KEY, myself->name, to->name, REQ_SPTPS, buf);
 784                 }
 785         }
 786
 787         /* Otherwise, send the packet via UDP */
 788
 789         const sockaddr_t *sa;
 790         int sock;
 791
 792         choose_udp_address(to, &sa, &sock);
 793
 794         if(sendto(listen_socket[sock].udp.fd, data, len, 0, &sa->sa, SALEN(sa->sa)) < 0 && !sockwouldblock(sockerrno)) {
 795                 if(sockmsgsize(sockerrno)) {
 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->status.active && 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;
1009         int len;
1010
1011         len = recvfrom(ls->udp.fd, (char *) &pkt.seqno, 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         n = lookup_node_udp(&from);
1024
1025         if(!n) {
1026                 n = try_harder(&from, &pkt);
1027                 if(n)
1028                         update_node_udp(n, &from);
1029                 else if(debug_level >= DEBUG_PROTOCOL) {
1030                         hostname = sockaddr2hostname(&from);
1031                         logger(DEBUG_PROTOCOL, LOG_WARNING, "Received UDP packet from unknown source %s", hostname);
1032                         free(hostname);
1033                         return;
1034                 }
1035                 else
1036                         return;
1037         }
1038
1039         n->sock = ls - listen_socket;
1040
1041         receive_udppacket(n, &pkt);
1042 }
1043
1044 void handle_device_data(void *data, int flags) {
1045         vpn_packet_t packet;
1046
1047         packet.priority = 0;
1048
1049         if(devops.read(&packet)) {
1050                 myself->in_packets++;
1051                 myself->in_bytes += packet.len;
1052                 route(myself, &packet);
1053         }
1054 }