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