16dac43f2ab66ef971034eaac52383de6c89005f
[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-2014 Guus Sliepen <guus@tinc-vpn.org>
5                   2010      Timothy Redaelli <timothy@redaelli.eu>
6                   2010      Brandon Black <blblack@gmail.com>
7
8     This program is free software; you can redistribute it and/or modify
9     it under the terms of the GNU General Public License as published by
10     the Free Software Foundation; either version 2 of the License, or
11     (at your option) any later version.
12
13     This program is distributed in the hope that it will be useful,
14     but WITHOUT ANY WARRANTY; without even the implied warranty of
15     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16     GNU General Public License for more details.
17
18     You should have received a copy of the GNU General Public License along
19     with this program; if not, write to the Free Software Foundation, Inc.,
20     51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
21 */
22
23 #include "system.h"
24
25 #ifdef HAVE_ZLIB
26 #include <zlib.h>
27 #endif
28
29 #ifdef HAVE_LZO
30 #include LZO1X_H
31 #endif
32
33 #include "cipher.h"
34 #include "conf.h"
35 #include "connection.h"
36 #include "crypto.h"
37 #include "digest.h"
38 #include "device.h"
39 #include "ethernet.h"
40 #include "graph.h"
41 #include "logger.h"
42 #include "net.h"
43 #include "netutl.h"
44 #include "protocol.h"
45 #include "route.h"
46 #include "utils.h"
47 #include "xalloc.h"
48
49 int keylifetime = 0;
50 #ifdef HAVE_LZO
51 static char lzo_wrkmem[LZO1X_999_MEM_COMPRESS > LZO1X_1_MEM_COMPRESS ? LZO1X_999_MEM_COMPRESS : LZO1X_1_MEM_COMPRESS];
52 #endif
53
54 static void send_udppacket(node_t *, vpn_packet_t *);
55
56 unsigned replaywin = 16;
57 bool localdiscovery = true;
58
59 #define MAX_SEQNO 1073741824
60
61 /* mtuprobes == 1..30: initial discovery, send bursts with 1 second interval
62    mtuprobes ==    31: sleep pinginterval seconds
63    mtuprobes ==    32: send 1 burst, sleep pingtimeout second
64    mtuprobes ==    33: no response from other side, restart PMTU discovery process
65
66    Probes are sent in batches of at least three, with random sizes between the
67    lower and upper boundaries for the MTU thus far discovered.
68
69    After the initial discovery, a fourth packet is added to each batch with a
70    size larger than the currently known PMTU, to test if the PMTU has increased.
71
72    In case local discovery is enabled, another packet is added to each batch,
73    which will be broadcast to the local network.
74
75 */
76
77 static void send_mtu_probe_handler(void *data) {
78         node_t *n = data;
79         int timeout = 1;
80
81         n->mtuprobes++;
82
83         if(!n->status.reachable || !n->status.validkey) {
84                 logger(DEBUG_TRAFFIC, LOG_INFO, "Trying to send MTU probe to unreachable or rekeying node %s (%s)", n->name, n->hostname);
85                 n->mtuprobes = 0;
86                 return;
87         }
88
89         if(n->mtuprobes > 32) {
90                 if(!n->minmtu) {
91                         n->mtuprobes = 31;
92                         timeout = pinginterval;
93                         goto end;
94                 }
95
96                 logger(DEBUG_TRAFFIC, LOG_INFO, "%s (%s) did not respond to UDP ping, restarting PMTU discovery", n->name, n->hostname);
97                 n->status.udp_confirmed = false;
98                 n->mtuprobes = 1;
99                 n->minmtu = 0;
100                 n->maxmtu = MTU;
101         }
102
103         if(n->mtuprobes >= 10 && n->mtuprobes < 32 && !n->minmtu) {
104                 logger(DEBUG_TRAFFIC, LOG_INFO, "No response to MTU probes from %s (%s)", n->name, n->hostname);
105                 n->mtuprobes = 31;
106         }
107
108         if(n->mtuprobes == 30 || (n->mtuprobes < 30 && n->minmtu >= n->maxmtu)) {
109                 if(n->minmtu > n->maxmtu)
110                         n->minmtu = n->maxmtu;
111                 else
112                         n->maxmtu = n->minmtu;
113                 n->mtu = n->minmtu;
114                 logger(DEBUG_TRAFFIC, LOG_INFO, "Fixing MTU of %s (%s) to %d after %d probes", n->name, n->hostname, n->mtu, n->mtuprobes);
115                 n->mtuprobes = 31;
116         }
117
118         if(n->mtuprobes == 31) {
119                 timeout = pinginterval;
120                 goto end;
121         } else if(n->mtuprobes == 32) {
122                 timeout = pingtimeout;
123         }
124
125         for(int i = 0; i < 4 + localdiscovery; i++) {
126                 int len;
127
128                 if(i == 0) {
129                         if(n->mtuprobes < 30 || n->maxmtu + 8 >= MTU)
130                                 continue;
131                         len = n->maxmtu + 8;
132                 } else if(n->maxmtu <= n->minmtu) {
133                         len = n->maxmtu;
134                 } else {
135                         len = n->minmtu + 1 + rand() % (n->maxmtu - n->minmtu);
136                 }
137
138                 if(len < 64)
139                         len = 64;
140
141                 vpn_packet_t packet;
142                 packet.offset = DEFAULT_PACKET_OFFSET;
143                 memset(DATA(&packet), 0, 14);
144                 randomize(DATA(&packet) + 14, len - 14);
145                 packet.len = len;
146                 packet.priority = 0;
147                 n->status.send_locally = 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.send_locally = 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(!DATA(packet)[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 = DATA(packet);
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 -= 10;
195                 } else {
196                         /* Legacy protocol: n won't understand type 2 probe replies. */
197                         DATA(packet)[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 (DATA(packet)[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, DATA(packet) + 1, 2); probelen = ntohs(probelen16);
214                         }
215                 }
216                 logger(DEBUG_TRAFFIC, LOG_INFO, "Got type %d MTU probe reply %d from %s (%s)", DATA(packet)[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 (DATA(packet)[0] == 2 && packet->len >= 11) {
259                         uint32_t sec; memcpy(&sec, DATA(packet) + 3, 4);
260                         uint32_t usec; memcpy(&usec, DATA(packet) + 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, DATA(inpkt), inpkt->len);
353
354         if(!digest_active(n->indigest) || inpkt->len < sizeof(seqno_t) + digest_length(n->indigest))
355                 return false;
356
357         return digest_verify(n->indigest, SEQNO(inpkt), inpkt->len - digest_length(n->indigest), DATA(inpkt) + inpkt->len - digest_length(n->indigest));
358 }
359
360 static bool 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         size_t outlen;
365         pkt1.offset = DEFAULT_PACKET_OFFSET;
366         pkt2.offset = DEFAULT_PACKET_OFFSET;
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 false;
377                 }
378                 inpkt->offset += 2 * sizeof(node_id_t);
379                 if(!sptps_receive_data(&n->sptps, DATA(inpkt), inpkt->len - 2 * sizeof(node_id_t))) {
380                         logger(DEBUG_TRAFFIC, LOG_ERR, "Got bad packet from %s (%s)", n->name, n->hostname);
381                         return false;
382                 }
383                 return true;
384         }
385
386         if(!n->status.validkey) {
387                 logger(DEBUG_TRAFFIC, LOG_DEBUG, "Got packet from %s (%s) but he hasn't got our key yet", n->name, n->hostname);
388                 return false;
389         }
390
391         /* Check packet length */
392
393         if(inpkt->len < sizeof(seqno_t) + digest_length(n->indigest)) {
394                 logger(DEBUG_TRAFFIC, LOG_DEBUG, "Got too short packet from %s (%s)",
395                                         n->name, n->hostname);
396                 return false;
397         }
398
399         /* It's a legacy UDP packet, the data starts after the seqno */
400
401         inpkt->offset += sizeof(seqno_t);
402
403         /* Check the message authentication code */
404
405         if(digest_active(n->indigest)) {
406                 inpkt->len -= digest_length(n->indigest);
407                 if(!digest_verify(n->indigest, SEQNO(inpkt), inpkt->len, SEQNO(inpkt) + inpkt->len)) {
408                         logger(DEBUG_TRAFFIC, LOG_DEBUG, "Got unauthenticated packet from %s (%s)", n->name, n->hostname);
409                         return false;
410                 }
411         }
412         /* Decrypt the packet */
413
414         if(cipher_active(n->incipher)) {
415                 vpn_packet_t *outpkt = pkt[nextpkt++];
416                 outlen = MAXSIZE;
417
418                 if(!cipher_decrypt(n->incipher, SEQNO(inpkt), inpkt->len, SEQNO(outpkt), &outlen, true)) {
419                         logger(DEBUG_TRAFFIC, LOG_DEBUG, "Error decrypting packet from %s (%s)", n->name, n->hostname);
420                         return false;
421                 }
422
423                 outpkt->len = outlen;
424                 inpkt = outpkt;
425         }
426
427         /* Check the sequence number */
428
429         seqno_t seqno;
430         memcpy(&seqno, SEQNO(inpkt), sizeof seqno);
431         seqno = ntohl(seqno);
432         inpkt->len -= sizeof seqno;
433
434         if(replaywin) {
435                 if(seqno != n->received_seqno + 1) {
436                         if(seqno >= n->received_seqno + replaywin * 8) {
437                                 if(n->farfuture++ < replaywin >> 2) {
438                                         logger(DEBUG_ALWAYS, LOG_WARNING, "Packet from %s (%s) is %d seqs in the future, dropped (%u)",
439                                                 n->name, n->hostname, seqno - n->received_seqno - 1, n->farfuture);
440                                         return false;
441                                 }
442                                 logger(DEBUG_ALWAYS, LOG_WARNING, "Lost %d packets from %s (%s)",
443                                                 seqno - n->received_seqno - 1, n->name, n->hostname);
444                                 memset(n->late, 0, replaywin);
445                         } else if (seqno <= n->received_seqno) {
446                                 if((n->received_seqno >= replaywin * 8 && seqno <= n->received_seqno - replaywin * 8) || !(n->late[(seqno / 8) % replaywin] & (1 << seqno % 8))) {
447                                         logger(DEBUG_ALWAYS, LOG_WARNING, "Got late or replayed packet from %s (%s), seqno %d, last received %d",
448                                                 n->name, n->hostname, seqno, n->received_seqno);
449                                         return false;
450                                 }
451                         } else {
452                                 for(int i = n->received_seqno + 1; i < seqno; i++)
453                                         n->late[(i / 8) % replaywin] |= 1 << i % 8;
454                         }
455                 }
456
457                 n->farfuture = 0;
458                 n->late[(seqno / 8) % replaywin] &= ~(1 << seqno % 8);
459         }
460
461         if(seqno > n->received_seqno)
462                 n->received_seqno = seqno;
463
464         n->received++;
465
466         if(n->received_seqno > MAX_SEQNO)
467                 regenerate_key();
468
469         /* Decompress the packet */
470
471         length_t origlen = inpkt->len;
472
473         if(n->incompression) {
474                 vpn_packet_t *outpkt = pkt[nextpkt++];
475
476                 if((outpkt->len = uncompress_packet(DATA(outpkt), DATA(inpkt), inpkt->len, n->incompression)) < 0) {
477                         logger(DEBUG_TRAFFIC, LOG_ERR, "Error while uncompressing packet from %s (%s)",
478                                                  n->name, n->hostname);
479                         return false;
480                 }
481
482                 inpkt = outpkt;
483
484                 origlen -= MTU/64 + 20;
485         }
486
487         inpkt->priority = 0;
488
489         if(!DATA(inpkt)[12] && !DATA(inpkt)[13])
490                 mtu_probe_h(n, inpkt, origlen);
491         else
492                 receive_packet(n, inpkt);
493         return true;
494 }
495
496 void receive_tcppacket(connection_t *c, const char *buffer, int len) {
497         vpn_packet_t outpkt;
498         outpkt.offset = DEFAULT_PACKET_OFFSET;
499
500         if(len > sizeof outpkt.data - outpkt.offset)
501                 return;
502
503         outpkt.len = len;
504         if(c->options & OPTION_TCPONLY)
505                 outpkt.priority = 0;
506         else
507                 outpkt.priority = -1;
508         memcpy(DATA(&outpkt), buffer, len);
509
510         receive_packet(c->node, &outpkt);
511 }
512
513 static bool try_sptps(node_t *n) {
514         if(n->status.validkey)
515                 return true;
516
517         logger(DEBUG_TRAFFIC, LOG_INFO, "No valid key known yet for %s (%s)", n->name, n->hostname);
518
519         if(!n->status.waitingforkey)
520                 send_req_key(n);
521         else if(n->last_req_key + 10 < now.tv_sec) {
522                 logger(DEBUG_ALWAYS, LOG_DEBUG, "No key from %s after 10 seconds, restarting SPTPS", n->name);
523                 sptps_stop(&n->sptps);
524                 n->status.waitingforkey = false;
525                 send_req_key(n);
526         }
527
528         return false;
529 }
530
531 static void send_sptps_packet(node_t *n, vpn_packet_t *origpkt) {
532         if (!try_sptps(n))
533                 return;
534
535         uint8_t type = 0;
536         int offset = 0;
537
538         if(!(DATA(origpkt)[12] | DATA(origpkt)[13])) {
539                 sptps_send_record(&n->sptps, PKT_PROBE, (char *)DATA(origpkt), origpkt->len);
540                 return;
541         }
542
543         if(routing_mode == RMODE_ROUTER)
544                 offset = 14;
545         else
546                 type = PKT_MAC;
547
548         if(origpkt->len < offset)
549                 return;
550
551         vpn_packet_t outpkt;
552
553         if(n->outcompression) {
554                 outpkt.offset = 0;
555                 int len = compress_packet(DATA(&outpkt) + offset, DATA(origpkt) + offset, origpkt->len - offset, n->outcompression);
556                 if(len < 0) {
557                         logger(DEBUG_TRAFFIC, LOG_ERR, "Error while compressing packet to %s (%s)", n->name, n->hostname);
558                 } else if(len < origpkt->len - offset) {
559                         outpkt.len = len + offset;
560                         origpkt = &outpkt;
561                         type |= PKT_COMPRESSED;
562                 }
563         }
564
565         sptps_send_record(&n->sptps, type, DATA(origpkt) + offset, origpkt->len - offset);
566         return;
567 }
568
569 static void adapt_socket(const sockaddr_t *sa, int *sock) {
570         /* Make sure we have a suitable socket for the chosen address */
571         if(listen_socket[*sock].sa.sa.sa_family != sa->sa.sa_family) {
572                 for(int i = 0; i < listen_sockets; i++) {
573                         if(listen_socket[i].sa.sa.sa_family == sa->sa.sa_family) {
574                                 *sock = i;
575                                 break;
576                         }
577                 }
578         }
579 }
580
581 static void choose_udp_address(const node_t *n, const sockaddr_t **sa, int *sock) {
582         /* Latest guess */
583         *sa = &n->address;
584         *sock = n->sock;
585
586         /* If the UDP address is confirmed, use it. */
587         if(n->status.udp_confirmed)
588                 return;
589
590         /* Send every third packet to n->address; that could be set
591            to the node's reflexive UDP address discovered during key
592            exchange. */
593
594         static int x = 0;
595         if(++x >= 3) {
596                 x = 0;
597                 return;
598         }
599
600         /* Otherwise, address are found in edges to this node.
601            So we pick a random edge and a random socket. */
602
603         int i = 0;
604         int j = rand() % n->edge_tree->count;
605         edge_t *candidate = NULL;
606
607         for splay_each(edge_t, e, n->edge_tree) {
608                 if(i++ == j) {
609                         candidate = e->reverse;
610                         break;
611                 }
612         }
613
614         if(candidate) {
615                 *sa = &candidate->address;
616                 *sock = rand() % listen_sockets;
617         }
618
619         adapt_socket(*sa, sock);
620 }
621
622 static void choose_local_address(const node_t *n, const sockaddr_t **sa, int *sock) {
623         *sa = NULL;
624
625         /* Pick one of the edges from this node at random, then use its local address. */
626
627         int i = 0;
628         int j = rand() % n->edge_tree->count;
629         edge_t *candidate = NULL;
630
631         for splay_each(edge_t, e, n->edge_tree) {
632                 if(i++ == j) {
633                         candidate = e;
634                         break;
635                 }
636         }
637
638         if (candidate && candidate->local_address.sa.sa_family) {
639                 *sa = &candidate->local_address;
640                 *sock = rand() % listen_sockets;
641                 adapt_socket(*sa, sock);
642         }
643 }
644
645 static void send_udppacket(node_t *n, vpn_packet_t *origpkt) {
646         vpn_packet_t pkt1, pkt2;
647         vpn_packet_t *pkt[] = { &pkt1, &pkt2, &pkt1, &pkt2 };
648         vpn_packet_t *inpkt = origpkt;
649         int nextpkt = 0;
650         vpn_packet_t *outpkt;
651         int origlen = origpkt->len;
652         size_t outlen;
653 #if defined(SOL_IP) && defined(IP_TOS)
654         static int priority = 0;
655         int origpriority = origpkt->priority;
656 #endif
657
658         pkt1.offset = DEFAULT_PACKET_OFFSET;
659         pkt2.offset = DEFAULT_PACKET_OFFSET;
660
661         if(!n->status.reachable) {
662                 logger(DEBUG_TRAFFIC, LOG_INFO, "Trying to send UDP packet to unreachable node %s (%s)", n->name, n->hostname);
663                 return;
664         }
665
666         if(n->status.sptps)
667                 return send_sptps_packet(n, origpkt);
668
669         /* Make sure we have a valid key */
670
671         if(!n->status.validkey) {
672                 logger(DEBUG_TRAFFIC, LOG_INFO,
673                                    "No valid key known yet for %s (%s), forwarding via TCP",
674                                    n->name, n->hostname);
675
676                 if(n->last_req_key + 10 <= now.tv_sec) {
677                         send_req_key(n);
678                         n->last_req_key = now.tv_sec;
679                 }
680
681                 send_tcppacket(n->nexthop->connection, origpkt);
682
683                 return;
684         }
685
686         if(n->options & OPTION_PMTU_DISCOVERY && inpkt->len > n->minmtu && (DATA(inpkt)[12] | DATA(inpkt)[13])) {
687                 logger(DEBUG_TRAFFIC, LOG_INFO,
688                                 "Packet for %s (%s) larger than minimum MTU, forwarding via %s",
689                                 n->name, n->hostname, n != n->nexthop ? n->nexthop->name : "TCP");
690
691                 if(n != n->nexthop)
692                         send_packet(n->nexthop, origpkt);
693                 else
694                         send_tcppacket(n->nexthop->connection, origpkt);
695
696                 return;
697         }
698
699         /* Compress the packet */
700
701         if(n->outcompression) {
702                 outpkt = pkt[nextpkt++];
703
704                 if((outpkt->len = compress_packet(DATA(outpkt), DATA(inpkt), inpkt->len, n->outcompression)) < 0) {
705                         logger(DEBUG_TRAFFIC, LOG_ERR, "Error while compressing packet to %s (%s)",
706                                    n->name, n->hostname);
707                         return;
708                 }
709
710                 inpkt = outpkt;
711         }
712
713         /* Add sequence number */
714
715         seqno_t seqno = htonl(++(n->sent_seqno));
716         memcpy(SEQNO(inpkt), &seqno, sizeof seqno);
717         inpkt->len += sizeof seqno;
718
719         /* Encrypt the packet */
720
721         if(cipher_active(n->outcipher)) {
722                 outpkt = pkt[nextpkt++];
723                 outlen = MAXSIZE;
724
725                 if(!cipher_encrypt(n->outcipher, SEQNO(inpkt), inpkt->len, SEQNO(outpkt), &outlen, true)) {
726                         logger(DEBUG_TRAFFIC, LOG_ERR, "Error while encrypting packet to %s (%s)", n->name, n->hostname);
727                         goto end;
728                 }
729
730                 outpkt->len = outlen;
731                 inpkt = outpkt;
732         }
733
734         /* Add the message authentication code */
735
736         if(digest_active(n->outdigest)) {
737                 if(!digest_create(n->outdigest, SEQNO(inpkt), inpkt->len, SEQNO(inpkt) + inpkt->len)) {
738                         logger(DEBUG_TRAFFIC, LOG_ERR, "Error while encrypting packet to %s (%s)", n->name, n->hostname);
739                         goto end;
740                 }
741
742                 inpkt->len += digest_length(n->outdigest);
743         }
744
745         /* Send the packet */
746
747         const sockaddr_t *sa = NULL;
748         int sock;
749
750         if(n->status.send_locally)
751                 choose_local_address(n, &sa, &sock);
752         if(!sa)
753                 choose_udp_address(n, &sa, &sock);
754
755 #if defined(SOL_IP) && defined(IP_TOS)
756         if(priorityinheritance && origpriority != priority
757            && listen_socket[n->sock].sa.sa.sa_family == AF_INET) {
758                 priority = origpriority;
759                 logger(DEBUG_TRAFFIC, LOG_DEBUG, "Setting outgoing packet priority to %d", priority);
760                 if(setsockopt(listen_socket[n->sock].udp.fd, SOL_IP, IP_TOS, &priority, sizeof(priority))) /* SO_PRIORITY doesn't seem to work */
761                         logger(DEBUG_ALWAYS, LOG_ERR, "System call `%s' failed: %s", "setsockopt", sockstrerror(sockerrno));
762         }
763 #endif
764
765         if(sendto(listen_socket[sock].udp.fd, SEQNO(inpkt), inpkt->len, 0, &sa->sa, SALEN(sa->sa)) < 0 && !sockwouldblock(sockerrno)) {
766                 if(sockmsgsize(sockerrno)) {
767                         if(n->maxmtu >= origlen)
768                                 n->maxmtu = origlen - 1;
769                         if(n->mtu >= origlen)
770                                 n->mtu = origlen - 1;
771                 } else
772                         logger(DEBUG_TRAFFIC, LOG_WARNING, "Error sending packet to %s (%s): %s", n->name, n->hostname, sockstrerror(sockerrno));
773         }
774
775 end:
776         origpkt->len = origlen;
777 }
778
779 static bool send_sptps_data_priv(node_t *to, node_t *from, int type, const void *data, size_t len) {
780         node_t *relay = (to->via != myself && (type == PKT_PROBE || (len - SPTPS_DATAGRAM_OVERHEAD) <= to->via->minmtu)) ? to->via : to->nexthop;
781         bool direct = from == myself && to == relay;
782         bool relay_supported = (relay->options >> 24) >= 4;
783         bool tcponly = (myself->options | relay->options) & OPTION_TCPONLY;
784
785         /* We don't really need the relay's key, but we need to establish a UDP tunnel with it and discover its MTU. */
786         if (!direct && relay_supported && !tcponly)
787                 try_sptps(relay);
788
789         /* Send it via TCP if it is a handshake packet, TCPOnly is in use, this is a relay packet that the other node cannot understand, or this packet is larger than the MTU.
790            TODO: When relaying, the original sender does not know the end-to-end PMTU (it only knows the PMTU of the first hop).
791                  This can lead to scenarios where large packets are sent over UDP to relay, but then relay has no choice but fall back to TCP. */
792
793         if(type == SPTPS_HANDSHAKE || tcponly || (!direct && !relay_supported) || (type != PKT_PROBE && (len - SPTPS_DATAGRAM_OVERHEAD) > relay->minmtu)) {
794                 char buf[len * 4 / 3 + 5];
795                 b64encode(data, buf, len);
796                 /* If no valid key is known yet, send the packets using ANS_KEY requests,
797                    to ensure we get to learn the reflexive UDP address. */
798                 if(from == myself && !to->status.validkey) {
799                         to->incompression = myself->incompression;
800                         return send_request(to->nexthop->connection, "%d %s %s %s -1 -1 -1 %d", ANS_KEY, from->name, to->name, buf, to->incompression);
801                 } else {
802                         return send_request(to->nexthop->connection, "%d %s %s %d %s", REQ_KEY, from->name, to->name, REQ_SPTPS, buf);
803                 }
804         }
805
806         size_t overhead = 0;
807         if(relay_supported) overhead += sizeof to->id + sizeof from->id;
808         char buf[len + overhead]; char* buf_ptr = buf;
809         if(relay_supported) {
810                 if(direct) {
811                         /* Inform the recipient that this packet was sent directly. */
812                         node_id_t nullid = {};
813                         memcpy(buf_ptr, &nullid, sizeof nullid); buf_ptr += sizeof nullid;
814                 } else {
815                         memcpy(buf_ptr, &to->id, sizeof to->id); buf_ptr += sizeof to->id;
816                 }
817                 memcpy(buf_ptr, &from->id, sizeof from->id); buf_ptr += sizeof from->id;
818
819         }
820         /* TODO: if this copy turns out to be a performance concern, change sptps_send_record() to add some "pre-padding" to the buffer and use that instead */
821         memcpy(buf_ptr, data, len); buf_ptr += len;
822
823         const sockaddr_t *sa = NULL;
824         int sock;
825         if(relay->status.send_locally)
826                 choose_local_address(relay, &sa, &sock);
827         if(!sa)
828                 choose_udp_address(relay, &sa, &sock);
829         logger(DEBUG_TRAFFIC, LOG_INFO, "Sending packet from %s (%s) to %s (%s) via %s (%s)", from->name, from->hostname, to->name, to->hostname, relay->name, relay->hostname);
830         if(sendto(listen_socket[sock].udp.fd, buf, buf_ptr - buf, 0, &sa->sa, SALEN(sa->sa)) < 0 && !sockwouldblock(sockerrno)) {
831                 if(sockmsgsize(sockerrno)) {
832                         // Compensate for SPTPS overhead
833                         len -= SPTPS_DATAGRAM_OVERHEAD;
834                         if(relay->maxmtu >= len)
835                                 relay->maxmtu = len - 1;
836                         if(relay->mtu >= len)
837                                 relay->mtu = len - 1;
838                 } else {
839                         logger(DEBUG_TRAFFIC, LOG_WARNING, "Error sending UDP SPTPS packet to %s (%s): %s", relay->name, relay->hostname, sockstrerror(sockerrno));
840                         return false;
841                 }
842         }
843
844         return true;
845 }
846
847 bool send_sptps_data(void *handle, uint8_t type, const void *data, size_t len) {
848         return send_sptps_data_priv(handle, myself, type, data, len);
849 }
850
851 bool receive_sptps_record(void *handle, uint8_t type, const void *data, uint16_t len) {
852         node_t *from = handle;
853
854         if(type == SPTPS_HANDSHAKE) {
855                 if(!from->status.validkey) {
856                         from->status.validkey = true;
857                         from->status.waitingforkey = false;
858                         logger(DEBUG_META, LOG_INFO, "SPTPS key exchange with %s (%s) succesful", from->name, from->hostname);
859                 }
860                 return true;
861         }
862
863         if(len > MTU) {
864                 logger(DEBUG_ALWAYS, LOG_ERR, "Packet from %s (%s) larger than maximum supported size (%d > %d)", from->name, from->hostname, len, MTU);
865                 return false;
866         }
867
868         vpn_packet_t inpkt;
869         inpkt.offset = DEFAULT_PACKET_OFFSET;
870
871         if(type == PKT_PROBE) {
872                 inpkt.len = len;
873                 memcpy(DATA(&inpkt), data, len);
874                 mtu_probe_h(from, &inpkt, len);
875                 return true;
876         }
877
878         if(type & ~(PKT_COMPRESSED | PKT_MAC)) {
879                 logger(DEBUG_ALWAYS, LOG_ERR, "Unexpected SPTPS record type %d len %d from %s (%s)", type, len, from->name, from->hostname);
880                 return false;
881         }
882
883         /* Check if we have the headers we need */
884         if(routing_mode != RMODE_ROUTER && !(type & PKT_MAC)) {
885                 logger(DEBUG_TRAFFIC, LOG_ERR, "Received packet from %s (%s) without MAC header (maybe Mode is not set correctly)", from->name, from->hostname);
886                 return false;
887         } else if(routing_mode == RMODE_ROUTER && (type & PKT_MAC)) {
888                 logger(DEBUG_TRAFFIC, LOG_WARNING, "Received packet from %s (%s) with MAC header (maybe Mode is not set correctly)", from->name, from->hostname);
889         }
890
891         int offset = (type & PKT_MAC) ? 0 : 14;
892         if(type & PKT_COMPRESSED) {
893                 length_t ulen = uncompress_packet(DATA(&inpkt) + offset, (const uint8_t *)data, len, from->incompression);
894                 if(ulen < 0) {
895                         return false;
896                 } else {
897                         inpkt.len = ulen + offset;
898                 }
899                 if(inpkt.len > MAXSIZE)
900                         abort();
901         } else {
902                 memcpy(DATA(&inpkt) + offset, data, len);
903                 inpkt.len = len + offset;
904         }
905
906         /* Generate the Ethernet packet type if necessary */
907         if(offset) {
908                 switch(DATA(&inpkt)[14] >> 4) {
909                         case 4:
910                                 DATA(&inpkt)[12] = 0x08;
911                                 DATA(&inpkt)[13] = 0x00;
912                                 break;
913                         case 6:
914                                 DATA(&inpkt)[12] = 0x86;
915                                 DATA(&inpkt)[13] = 0xDD;
916                                 break;
917                         default:
918                                 logger(DEBUG_TRAFFIC, LOG_ERR,
919                                                    "Unknown IP version %d while reading packet from %s (%s)",
920                                                    DATA(&inpkt)[14] >> 4, from->name, from->hostname);
921                                 return false;
922                 }
923         }
924
925         receive_packet(from, &inpkt);
926         return true;
927 }
928
929 /*
930   send a packet to the given vpn ip.
931 */
932 void send_packet(node_t *n, vpn_packet_t *packet) {
933         node_t *via;
934
935         if(n == myself) {
936                 if(overwrite_mac)
937                          memcpy(DATA(packet), mymac.x, ETH_ALEN);
938                 n->out_packets++;
939                 n->out_bytes += packet->len;
940                 devops.write(packet);
941                 return;
942         }
943
944         logger(DEBUG_TRAFFIC, LOG_ERR, "Sending packet of %d bytes to %s (%s)",
945                            packet->len, n->name, n->hostname);
946
947         if(!n->status.reachable) {
948                 logger(DEBUG_TRAFFIC, LOG_INFO, "Node %s (%s) is not reachable",
949                                    n->name, n->hostname);
950                 return;
951         }
952
953         n->out_packets++;
954         n->out_bytes += packet->len;
955
956         if(n->status.sptps) {
957                 send_sptps_packet(n, packet);
958                 return;
959         }
960
961         via = (packet->priority == -1 || n->via == myself) ? n->nexthop : n->via;
962
963         if(via != n)
964                 logger(DEBUG_TRAFFIC, LOG_INFO, "Sending packet to %s via %s (%s)",
965                            n->name, via->name, n->via->hostname);
966
967         if(packet->priority == -1 || ((myself->options | via->options) & OPTION_TCPONLY)) {
968                 if(!send_tcppacket(via->connection, packet))
969                         terminate_connection(via->connection, true);
970         } else
971                 send_udppacket(via, packet);
972 }
973
974 /* Broadcast a packet using the minimum spanning tree */
975
976 void broadcast_packet(const node_t *from, vpn_packet_t *packet) {
977         // Always give ourself a copy of the packet.
978         if(from != myself)
979                 send_packet(myself, packet);
980
981         // In TunnelServer mode, do not forward broadcast packets.
982         // The MST might not be valid and create loops.
983         if(tunnelserver || broadcast_mode == BMODE_NONE)
984                 return;
985
986         logger(DEBUG_TRAFFIC, LOG_INFO, "Broadcasting packet of %d bytes from %s (%s)",
987                            packet->len, from->name, from->hostname);
988
989         switch(broadcast_mode) {
990                 // In MST mode, broadcast packets travel via the Minimum Spanning Tree.
991                 // This guarantees all nodes receive the broadcast packet, and
992                 // usually distributes the sending of broadcast packets over all nodes.
993                 case BMODE_MST:
994                         for list_each(connection_t, c, connection_list)
995                                 if(c->edge && c->status.mst && c != from->nexthop->connection)
996                                         send_packet(c->node, packet);
997                         break;
998
999                 // In direct mode, we send copies to each node we know of.
1000                 // However, this only reaches nodes that can be reached in a single hop.
1001                 // We don't have enough information to forward broadcast packets in this case.
1002                 case BMODE_DIRECT:
1003                         if(from != myself)
1004                                 break;
1005
1006                         for splay_each(node_t, n, node_tree)
1007                                 if(n->status.reachable && n != myself && ((n->via == myself && n->nexthop == n) || n->via == n))
1008                                         send_packet(n, packet);
1009                         break;
1010
1011                 default:
1012                         break;
1013         }
1014 }
1015
1016 static node_t *try_harder(const sockaddr_t *from, const vpn_packet_t *pkt) {
1017         node_t *n = NULL;
1018         bool hard = false;
1019         static time_t last_hard_try = 0;
1020
1021         for splay_each(edge_t, e, edge_weight_tree) {
1022                 if(!e->to->status.reachable || e->to == myself)
1023                         continue;
1024
1025                 if(sockaddrcmp_noport(from, &e->address)) {
1026                         if(last_hard_try == now.tv_sec)
1027                                 continue;
1028                         hard = true;
1029                 }
1030
1031                 if(!try_mac(e->to, pkt))
1032                         continue;
1033
1034                 n = e->to;
1035                 break;
1036         }
1037
1038         if(hard)
1039                 last_hard_try = now.tv_sec;
1040
1041         last_hard_try = now.tv_sec;
1042         return n;
1043 }
1044
1045 void handle_incoming_vpn_data(void *data, int flags) {
1046         listen_socket_t *ls = data;
1047         vpn_packet_t pkt;
1048         char *hostname;
1049         node_id_t nullid = {};
1050         sockaddr_t addr = {};
1051         socklen_t addrlen = sizeof addr;
1052         node_t *from, *to;
1053         bool direct = false;
1054
1055         pkt.offset = 0;
1056         int len = recvfrom(ls->udp.fd, DATA(&pkt), MAXSIZE, 0, &addr.sa, &addrlen);
1057
1058         if(len <= 0 || len > MAXSIZE) {
1059                 if(!sockwouldblock(sockerrno))
1060                         logger(DEBUG_ALWAYS, LOG_ERR, "Receiving packet failed: %s", sockstrerror(sockerrno));
1061                 return;
1062         }
1063
1064         pkt.len = len;
1065
1066         sockaddrunmap(&addr); /* Some braindead IPv6 implementations do stupid things. */
1067
1068         // Try to figure out who sent this packet.
1069
1070         node_t *n = lookup_node_udp(&addr);
1071
1072         if(!n) {
1073                 // It might be from a 1.1 node, which might have a source ID in the packet.
1074                 pkt.offset = 2 * sizeof(node_id_t);
1075                 from = lookup_node_id(SRCID(&pkt));
1076                 if(from && !memcmp(DSTID(&pkt), &nullid, sizeof nullid) && from->status.sptps) {
1077                         if(sptps_verify_datagram(&from->sptps, DATA(&pkt), pkt.len - 2 * sizeof(node_id_t)))
1078                                 n = from;
1079                         else
1080                                 goto skip_harder;
1081                 }
1082         }
1083
1084         if(!n) {
1085                 pkt.offset = 0;
1086                 n = try_harder(&addr, &pkt);
1087         }
1088
1089 skip_harder:
1090         if(!n) {
1091                 if(debug_level >= DEBUG_PROTOCOL) {
1092                         hostname = sockaddr2hostname(&addr);
1093                         logger(DEBUG_PROTOCOL, LOG_WARNING, "Received UDP packet from unknown source %s", hostname);
1094                         free(hostname);
1095                 }
1096                 return;
1097         }
1098
1099         if(n->status.sptps) {
1100                 pkt.offset = 2 * sizeof(node_id_t);
1101
1102                 if(!memcmp(DSTID(&pkt), &nullid, sizeof nullid)) {
1103                         direct = true;
1104                         from = n;
1105                         to = myself;
1106                 } else {
1107                         from = lookup_node_id(SRCID(&pkt));
1108                         to = lookup_node_id(DSTID(&pkt));
1109                 }
1110                 if(!from || !to) {
1111                         logger(DEBUG_PROTOCOL, LOG_WARNING, "Received UDP packet from %s (%s) with unknown source and/or destination ID", n->name, n->hostname);
1112                         return;
1113                 }
1114
1115                 if(to != myself) {
1116                         send_sptps_data_priv(to, n, 0, DATA(&pkt), pkt.len - 2 * sizeof(node_id_t));
1117                         return;
1118                 }
1119         } else {
1120                 direct = true;
1121                 from = n;
1122         }
1123
1124         pkt.offset = 0;
1125         if(!receive_udppacket(from, &pkt))
1126                 return;
1127
1128         n->sock = ls - listen_socket;
1129         if(direct && sockaddrcmp(&addr, &n->address))
1130                 update_node_udp(n, &addr);
1131 }
1132
1133 void handle_device_data(void *data, int flags) {
1134         vpn_packet_t packet;
1135         packet.offset = DEFAULT_PACKET_OFFSET;
1136         packet.priority = 0;
1137
1138         if(devops.read(&packet)) {
1139                 myself->in_packets++;
1140                 myself->in_bytes += packet.len;
1141                 route(myself, &packet);
1142         }
1143 }