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