]> git.meshlink.io Git - meshlink/blob - src/net_packet.c
Move edge_weight_tree to mesh->edges.
[meshlink] / src / net_packet.c
1 /*
2     net_packet.c -- Handles in- and outgoing VPN packets
3     Copyright (C) 2014 Guus Sliepen <guus@meshlink.io>
4
5     This program is free software; you can redistribute it and/or modify
6     it under the terms of the GNU General Public License as published by
7     the Free Software Foundation; either version 2 of the License, or
8     (at your option) any later version.
9
10     This program is distributed in the hope that it will be useful,
11     but WITHOUT ANY WARRANTY; without even the implied warranty of
12     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13     GNU General Public License for more details.
14
15     You should have received a copy of the GNU General Public License along
16     with this program; if not, write to the Free Software Foundation, Inc.,
17     51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
18 */
19
20 #include "system.h"
21
22 #ifdef HAVE_ZLIB
23 #include <zlib.h>
24 #endif
25
26 #include "cipher.h"
27 #include "conf.h"
28 #include "connection.h"
29 #include "crypto.h"
30 #include "digest.h"
31 #include "graph.h"
32 #include "logger.h"
33 #include "meshlink_internal.h"
34 #include "net.h"
35 #include "netutl.h"
36 #include "protocol.h"
37 #include "route.h"
38 #include "utils.h"
39 #include "xalloc.h"
40
41 int keylifetime = 0;
42
43 static void send_udppacket(node_t *, vpn_packet_t *);
44
45 unsigned replaywin = 16;
46 bool localdiscovery = false;
47 sockaddr_t localdiscovery_address;
48
49 #define MAX_SEQNO 1073741824
50
51 /* mtuprobes == 1..30: initial discovery, send bursts with 1 second interval
52    mtuprobes ==    31: sleep pinginterval seconds
53    mtuprobes ==    32: send 1 burst, sleep pingtimeout second
54    mtuprobes ==    33: no response from other side, restart PMTU discovery process
55
56    Probes are sent in batches of at least three, with random sizes between the
57    lower and upper boundaries for the MTU thus far discovered.
58
59    After the initial discovery, a fourth packet is added to each batch with a
60    size larger than the currently known PMTU, to test if the PMTU has increased.
61
62    In case local discovery is enabled, another packet is added to each batch,
63    which will be broadcast to the local network.
64
65 */
66
67 static void send_mtu_probe_handler(void *data) {
68         node_t *n = data;
69         int timeout = 1;
70
71         n->mtuprobes++;
72
73         if(!n->status.reachable || !n->status.validkey) {
74                 logger(DEBUG_TRAFFIC, LOG_INFO, "Trying to send MTU probe to unreachable or rekeying node %s (%s)", n->name, n->hostname);
75                 n->mtuprobes = 0;
76                 return;
77         }
78
79         if(n->mtuprobes > 32) {
80                 if(!n->minmtu) {
81                         n->mtuprobes = 31;
82                         timeout = pinginterval;
83                         goto end;
84                 }
85
86                 logger(DEBUG_TRAFFIC, LOG_INFO, "%s (%s) did not respond to UDP ping, restarting PMTU discovery", n->name, n->hostname);
87                 n->status.udp_confirmed = false;
88                 n->mtuprobes = 1;
89                 n->minmtu = 0;
90                 n->maxmtu = MTU;
91         }
92
93         if(n->mtuprobes >= 10 && n->mtuprobes < 32 && !n->minmtu) {
94                 logger(DEBUG_TRAFFIC, LOG_INFO, "No response to MTU probes from %s (%s)", n->name, n->hostname);
95                 n->mtuprobes = 31;
96         }
97
98         if(n->mtuprobes == 30 || (n->mtuprobes < 30 && n->minmtu >= n->maxmtu)) {
99                 if(n->minmtu > n->maxmtu)
100                         n->minmtu = n->maxmtu;
101                 else
102                         n->maxmtu = n->minmtu;
103                 n->mtu = n->minmtu;
104                 logger(DEBUG_TRAFFIC, LOG_INFO, "Fixing MTU of %s (%s) to %d after %d probes", n->name, n->hostname, n->mtu, n->mtuprobes);
105                 n->mtuprobes = 31;
106         }
107
108         if(n->mtuprobes == 31) {
109                 timeout = pinginterval;
110                 goto end;
111         } else if(n->mtuprobes == 32) {
112                 timeout = pingtimeout;
113         }
114
115         for(int i = 0; i < 4 + localdiscovery; i++) {
116                 int len;
117
118                 if(i == 0) {
119                         if(n->mtuprobes < 30 || n->maxmtu + 8 >= MTU)
120                                 continue;
121                         len = n->maxmtu + 8;
122                 } else if(n->maxmtu <= n->minmtu) {
123                         len = n->maxmtu;
124                 } else {
125                         len = n->minmtu + 1 + rand() % (n->maxmtu - n->minmtu);
126                 }
127
128                 if(len < 64)
129                         len = 64;
130
131                 vpn_packet_t packet;
132                 memset(packet.data, 0, 14);
133                 randomize(packet.data + 14, len - 14);
134                 packet.len = len;
135                 n->status.broadcast = i >= 4 && n->mtuprobes <= 10 && n->prevedge;
136
137                 logger(DEBUG_TRAFFIC, LOG_INFO, "Sending MTU probe length %d to %s (%s)", len, n->name, n->hostname);
138
139                 send_udppacket(n, &packet);
140         }
141
142         n->status.broadcast = false;
143         n->probe_counter = 0;
144         gettimeofday(&n->probe_time, NULL);
145
146         /* Calculate the packet loss of incoming traffic by comparing the rate of
147            packets received to the rate with which the sequence number has increased.
148          */
149
150         if(n->received > n->prev_received)
151                 n->packetloss = 1.0 - (n->received - n->prev_received) / (float)(n->received_seqno - n->prev_received_seqno);
152         else
153                 n->packetloss = n->received_seqno <= n->prev_received_seqno;
154
155         n->prev_received_seqno = n->received_seqno;
156         n->prev_received = n->received;
157
158 end:
159         timeout_set(&n->mtutimeout, &(struct timeval){timeout, rand() % 100000});
160 }
161
162 void send_mtu_probe(node_t *n) {
163         timeout_add(&n->mtutimeout, send_mtu_probe_handler, n, &(struct timeval){1, 0});
164         send_mtu_probe_handler(n);
165 }
166
167 static void mtu_probe_h(node_t *n, vpn_packet_t *packet, uint16_t len) {
168         logger(DEBUG_TRAFFIC, LOG_INFO, "Got MTU probe length %d from %s (%s)", packet->len, n->name, n->hostname);
169
170         if(!packet->data[0]) {
171                 /* It's a probe request, send back a reply */
172
173                 packet->data[0] = 1;
174
175                 /* Temporarily set udp_confirmed, so that the reply is sent
176                    back exactly the way it came in. */
177
178                 bool udp_confirmed = n->status.udp_confirmed;
179                 n->status.udp_confirmed = true;
180                 send_udppacket(n, packet);
181                 n->status.udp_confirmed = udp_confirmed;
182         } else {
183                 /* It's a valid reply: now we know bidirectional communication
184                    is possible using the address and socket that the reply
185                    packet used. */
186
187                 n->status.udp_confirmed = true;
188
189                 /* If we haven't established the PMTU yet, restart the discovery process. */
190
191                 if(n->mtuprobes > 30) {
192                         if (len == n->maxmtu + 8) {
193                                 logger(DEBUG_TRAFFIC, LOG_INFO, "Increase in PMTU to %s (%s) detected, restarting PMTU discovery", n->name, n->hostname);
194                                 n->maxmtu = MTU;
195                                 n->mtuprobes = 10;
196                                 return;
197                         }
198
199                         if(n->minmtu)
200                                 n->mtuprobes = 30;
201                         else
202                                 n->mtuprobes = 1;
203                 }
204
205                 /* If applicable, raise the minimum supported MTU */
206
207                 if(len > n->maxmtu)
208                         len = n->maxmtu;
209                 if(n->minmtu < len)
210                         n->minmtu = len;
211
212                 /* Calculate RTT and bandwidth.
213                    The RTT is the time between the MTU probe burst was sent and the first
214                    reply is received. The bandwidth is measured using the time between the
215                    arrival of the first and third probe reply.
216                  */
217
218                 struct timeval now, diff;
219                 gettimeofday(&now, NULL);
220                 timersub(&now, &n->probe_time, &diff);
221                 
222                 n->probe_counter++;
223
224                 if(n->probe_counter == 1) {
225                         n->rtt = diff.tv_sec + diff.tv_usec * 1e-6;
226                         n->probe_time = now;
227                 } else if(n->probe_counter == 3) {
228                         n->bandwidth = 2.0 * len / (diff.tv_sec + diff.tv_usec * 1e-6);
229                         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);
230                 }
231         }
232 }
233
234 static uint16_t compress_packet(uint8_t *dest, const uint8_t *source, uint16_t len, int level) {
235         if(level == 0) {
236                 memcpy(dest, source, len);
237                 return len;
238         } else if(level == 10) {
239                 return -1;
240         } else if(level < 10) {
241 #ifdef HAVE_ZLIB
242                 unsigned long destlen = MAXSIZE;
243                 if(compress2(dest, &destlen, source, len, level) == Z_OK)
244                         return destlen;
245                 else
246 #endif
247                         return -1;
248         } else {
249                 return -1;
250         }
251
252         return -1;
253 }
254
255 static uint16_t uncompress_packet(uint8_t *dest, const uint8_t *source, uint16_t len, int level) {
256         if(level == 0) {
257                 memcpy(dest, source, len);
258                 return len;
259         } else if(level > 9) {
260                         return -1;
261         }
262 #ifdef HAVE_ZLIB
263         else {
264                 unsigned long destlen = MAXSIZE;
265                 if(uncompress(dest, &destlen, source, len) == Z_OK)
266                         return destlen;
267                 else
268                         return -1;
269         }
270 #endif
271
272         return -1;
273 }
274
275 /* VPN packet I/O */
276
277 static void receive_packet(node_t *n, vpn_packet_t *packet) {
278         logger(DEBUG_TRAFFIC, LOG_DEBUG, "Received packet of %d bytes from %s (%s)",
279                            packet->len, n->name, n->hostname);
280
281         n->in_packets++;
282         n->in_bytes += packet->len;
283
284         route(n, packet);
285 }
286
287 static bool try_mac(node_t *n, const vpn_packet_t *inpkt) {
288         return sptps_verify_datagram(&n->sptps, inpkt->data, inpkt->len);
289 }
290
291 static void receive_udppacket(node_t *n, vpn_packet_t *inpkt) {
292         if(!n->sptps.state) {
293                 if(!n->status.waitingforkey) {
294                         logger(DEBUG_TRAFFIC, LOG_DEBUG, "Got packet from %s (%s) but we haven't exchanged keys yet", n->name, n->hostname);
295                         send_req_key(n);
296                 } else {
297                         logger(DEBUG_TRAFFIC, LOG_DEBUG, "Got packet from %s (%s) but he hasn't got our key yet", n->name, n->hostname);
298                 }
299                 return;
300         }
301         sptps_receive_data(&n->sptps, inpkt->data, inpkt->len);
302 }
303
304 void receive_tcppacket(connection_t *c, const char *buffer, int len) {
305         vpn_packet_t outpkt;
306
307         if(len > sizeof outpkt.data)
308                 return;
309
310         outpkt.len = len;
311         outpkt.tcp = true;
312         memcpy(outpkt.data, buffer, len);
313
314         receive_packet(c->node, &outpkt);
315 }
316
317 static void send_sptps_packet(node_t *n, vpn_packet_t *origpkt) {
318         if(!n->status.validkey) {
319                 logger(DEBUG_TRAFFIC, LOG_INFO, "No valid key known yet for %s (%s)", n->name, n->hostname);
320                 if(!n->status.waitingforkey)
321                         send_req_key(n);
322                 else if(n->last_req_key + 10 < now.tv_sec) {
323                         logger(DEBUG_ALWAYS, LOG_DEBUG, "No key from %s after 10 seconds, restarting SPTPS", n->name);
324                         sptps_stop(&n->sptps);
325                         n->status.waitingforkey = false;
326                         send_req_key(n);
327                 }
328                 return;
329         }
330
331         uint8_t type = 0;
332
333         // If it's a probe, send it immediately without trying to compress it.
334         if(origpkt->probe) {
335                 sptps_send_record(&n->sptps, PKT_PROBE, origpkt->data, origpkt->len);
336                 return;
337         }
338
339         vpn_packet_t outpkt;
340
341         if(n->outcompression) {
342                 int len = compress_packet(outpkt.data, origpkt->data, origpkt->len, n->outcompression);
343                 if(len < 0) {
344                         logger(DEBUG_TRAFFIC, LOG_ERR, "Error while compressing packet to %s (%s)", n->name, n->hostname);
345                 } else if(len < origpkt->len) {
346                         outpkt.len = len;
347                         origpkt = &outpkt;
348                         type |= PKT_COMPRESSED;
349                 }
350         }
351
352         sptps_send_record(&n->sptps, type, origpkt->data, origpkt->len);
353         return;
354 }
355
356 static void choose_udp_address(const node_t *n, const sockaddr_t **sa, int *sock) {
357         /* Latest guess */
358         *sa = &n->address;
359         *sock = n->sock;
360
361         /* If the UDP address is confirmed, use it. */
362         if(n->status.udp_confirmed)
363                 return;
364
365         /* Send every third packet to n->address; that could be set
366            to the node's reflexive UDP address discovered during key
367            exchange. */
368
369         static int x = 0;
370         if(++x >= 3) {
371                 x = 0;
372                 return;
373         }
374
375         /* Otherwise, address are found in edges to this node.
376            So we pick a random edge and a random socket. */
377
378         int i = 0;
379         int j = rand() % n->edge_tree->count;
380         edge_t *candidate = NULL;
381
382         for splay_each(edge_t, e, n->edge_tree) {
383                 if(i++ == j) {
384                         candidate = e->reverse;
385                         break;
386                 }
387         }
388
389         if(candidate) {
390                 *sa = &candidate->address;
391                 *sock = rand() % listen_sockets;
392         }
393
394         /* Make sure we have a suitable socket for the chosen address */
395         if(listen_socket[*sock].sa.sa.sa_family != (*sa)->sa.sa_family) {
396                 for(int i = 0; i < listen_sockets; i++) {
397                         if(listen_socket[i].sa.sa.sa_family == (*sa)->sa.sa_family) {
398                                 *sock = i;
399                                 break;
400                         }
401                 }
402         }
403 }
404
405 static void choose_broadcast_address(const node_t *n, const sockaddr_t **sa, int *sock) {
406         static sockaddr_t broadcast_ipv4 = {
407                 .in = {
408                         .sin_family = AF_INET,
409                         .sin_addr.s_addr = -1,
410                 }
411         };
412
413         static sockaddr_t broadcast_ipv6 = {
414                 .in6 = {
415                         .sin6_family = AF_INET6,
416                         .sin6_addr.s6_addr[0x0] = 0xff,
417                         .sin6_addr.s6_addr[0x1] = 0x02,
418                         .sin6_addr.s6_addr[0xf] = 0x01,
419                 }
420         };
421
422         *sock = rand() % listen_sockets;
423
424         if(listen_socket[*sock].sa.sa.sa_family == AF_INET6) {
425                 if(localdiscovery_address.sa.sa_family == AF_INET6) {
426                         localdiscovery_address.in6.sin6_port = n->prevedge->address.in.sin_port;
427                         *sa = &localdiscovery_address;
428                 } else {
429                         broadcast_ipv6.in6.sin6_port = n->prevedge->address.in.sin_port;
430                         broadcast_ipv6.in6.sin6_scope_id = listen_socket[*sock].sa.in6.sin6_scope_id;
431                         *sa = &broadcast_ipv6;
432                 }
433         } else {
434                 if(localdiscovery_address.sa.sa_family == AF_INET) {
435                         localdiscovery_address.in.sin_port = n->prevedge->address.in.sin_port;
436                         *sa = &localdiscovery_address;
437                 } else {
438                         broadcast_ipv4.in.sin_port = n->prevedge->address.in.sin_port;
439                         *sa = &broadcast_ipv4;
440                 }
441         }
442 }
443
444 static void send_udppacket(node_t *n, vpn_packet_t *origpkt) {
445         vpn_packet_t pkt1, pkt2;
446         vpn_packet_t *pkt[] = { &pkt1, &pkt2, &pkt1, &pkt2 };
447         vpn_packet_t *inpkt = origpkt;
448         int nextpkt = 0;
449         vpn_packet_t *outpkt;
450         int origlen = origpkt->len;
451         size_t outlen;
452
453         if(!n->status.reachable) {
454                 logger(DEBUG_TRAFFIC, LOG_INFO, "Trying to send UDP packet to unreachable node %s (%s)", n->name, n->hostname);
455                 return;
456         }
457
458         return send_sptps_packet(n, origpkt);
459 }
460
461 bool send_sptps_data(void *handle, uint8_t type, const char *data, size_t len) {
462         node_t *to = handle;
463
464         /* Send it via TCP if it is a handshake packet, TCPOnly is in use, or this packet is larger than the MTU. */
465
466         if(type >= SPTPS_HANDSHAKE || ((mesh->self->options | to->options) & OPTION_TCPONLY) || (type != PKT_PROBE && len > to->minmtu)) {
467                 char buf[len * 4 / 3 + 5];
468                 b64encode(data, buf, len);
469                 /* If no valid key is known yet, send the packets using ANS_KEY requests,
470                    to ensure we get to learn the reflexive UDP address. */
471                 if(!to->status.validkey) {
472                         to->incompression = mesh->self->incompression;
473                         return send_request(to->nexthop->connection, "%d %s %s %s -1 -1 -1 %d", ANS_KEY, mesh->self->name, to->name, buf, to->incompression);
474                 } else {
475                         return send_request(to->nexthop->connection, "%d %s %s %d %s", REQ_KEY, mesh->self->name, to->name, REQ_SPTPS, buf);
476                 }
477         }
478
479         /* Otherwise, send the packet via UDP */
480
481         const sockaddr_t *sa;
482         int sock;
483
484         if(to->status.broadcast)
485                 choose_broadcast_address(to, &sa, &sock);
486         else
487                 choose_udp_address(to, &sa, &sock);
488
489         if(sendto(listen_socket[sock].udp.fd, data, len, 0, &sa->sa, SALEN(sa->sa)) < 0 && !sockwouldblock(sockerrno)) {
490                 if(sockmsgsize(sockerrno)) {
491                         if(to->maxmtu >= len)
492                                 to->maxmtu = len - 1;
493                         if(to->mtu >= len)
494                                 to->mtu = len - 1;
495                 } else {
496                         logger(DEBUG_TRAFFIC, LOG_WARNING, "Error sending UDP SPTPS packet to %s (%s): %s", to->name, to->hostname, sockstrerror(sockerrno));
497                         return false;
498                 }
499         }
500
501         return true;
502 }
503
504 bool receive_sptps_record(void *handle, uint8_t type, const char *data, uint16_t len) {
505         node_t *from = handle;
506
507         if(type == SPTPS_HANDSHAKE) {
508                 if(!from->status.validkey) {
509                         from->status.validkey = true;
510                         from->status.waitingforkey = false;
511                         logger(DEBUG_META, LOG_INFO, "SPTPS key exchange with %s (%s) succesful", from->name, from->hostname);
512                 }
513                 return true;
514         }
515
516         if(len > MTU) {
517                 logger(DEBUG_ALWAYS, LOG_ERR, "Packet from %s (%s) larger than maximum supported size (%d > %d)", from->name, from->hostname, len, MTU);
518                 return false;
519         }
520
521         vpn_packet_t inpkt;
522
523         if(type == PKT_PROBE) {
524                 inpkt.len = len;
525                 inpkt.probe = true;
526                 memcpy(inpkt.data, data, len);
527                 mtu_probe_h(from, &inpkt, len);
528                 return true;
529         } else {
530                 inpkt.probe = false;
531         }
532
533         if(type & ~(PKT_COMPRESSED)) {
534                 logger(DEBUG_ALWAYS, LOG_ERR, "Unexpected SPTPS record type %d len %d from %s (%s)", type, len, from->name, from->hostname);
535                 return false;
536         }
537
538         if(type & PKT_COMPRESSED) {
539                 uint16_t ulen = uncompress_packet(inpkt.data, (const uint8_t *)data, len, from->incompression);
540                 if(ulen < 0) {
541                         return false;
542                 } else {
543                         inpkt.len = ulen;
544                 }
545                 if(inpkt.len > MAXSIZE)
546                         abort();
547         } else {
548                 memcpy(inpkt.data, data, len);
549                 inpkt.len = len;
550         }
551
552         receive_packet(from, &inpkt);
553         return true;
554 }
555
556 /*
557   send a packet to the given vpn ip.
558 */
559 void send_packet(node_t *n, vpn_packet_t *packet) {
560         node_t *via;
561
562         if(n == mesh->self) {
563                 n->out_packets++;
564                 n->out_bytes += packet->len;
565                 // TODO: send to application
566                 return;
567         }
568
569         logger(DEBUG_TRAFFIC, LOG_ERR, "Sending packet of %d bytes to %s (%s)",
570                            packet->len, n->name, n->hostname);
571
572         if(!n->status.reachable) {
573                 logger(DEBUG_TRAFFIC, LOG_INFO, "Node %s (%s) is not reachable",
574                                    n->name, n->hostname);
575                 return;
576         }
577
578         n->out_packets++;
579         n->out_bytes += packet->len;
580
581         send_sptps_packet(n, packet);
582         return;
583 }
584
585 /* Broadcast a packet using the minimum spanning tree */
586
587 void broadcast_packet(const node_t *from, vpn_packet_t *packet) {
588         // Always give ourself a copy of the packet.
589         if(from != mesh->self)
590                 send_packet(mesh->self, packet);
591
592         logger(DEBUG_TRAFFIC, LOG_INFO, "Broadcasting packet of %d bytes from %s (%s)",
593                            packet->len, from->name, from->hostname);
594
595         for list_each(connection_t, c, connection_list)
596                 if(c->status.active && c->status.mst && c != from->nexthop->connection)
597                         send_packet(c->node, packet);
598 }
599
600 static node_t *try_harder(const sockaddr_t *from, const vpn_packet_t *pkt) {
601         node_t *n = NULL;
602         bool hard = false;
603         static time_t last_hard_try = 0;
604
605         for splay_each(edge_t, e, mesh->edges) {
606                 if(!e->to->status.reachable || e->to == mesh->self)
607                         continue;
608
609                 if(sockaddrcmp_noport(from, &e->address)) {
610                         if(last_hard_try == now.tv_sec)
611                                 continue;
612                         hard = true;
613                 }
614
615                 if(!try_mac(e->to, pkt))
616                         continue;
617
618                 n = e->to;
619                 break;
620         }
621
622         if(hard)
623                 last_hard_try = now.tv_sec;
624
625         last_hard_try = now.tv_sec;
626         return n;
627 }
628
629 void handle_incoming_vpn_data(void *data, int flags) {
630         listen_socket_t *ls = data;
631         vpn_packet_t pkt;
632         char *hostname;
633         sockaddr_t from = {{0}};
634         socklen_t fromlen = sizeof from;
635         node_t *n;
636         int len;
637
638         len = recvfrom(ls->udp.fd, pkt.data, MAXSIZE, 0, &from.sa, &fromlen);
639
640         if(len <= 0 || len > MAXSIZE) {
641                 if(!sockwouldblock(sockerrno))
642                         logger(DEBUG_ALWAYS, LOG_ERR, "Receiving packet failed: %s", sockstrerror(sockerrno));
643                 return;
644         }
645
646         pkt.len = len;
647
648         sockaddrunmap(&from); /* Some braindead IPv6 implementations do stupid things. */
649
650         n = lookup_node_udp(&from);
651
652         if(!n) {
653                 n = try_harder(&from, &pkt);
654                 if(n)
655                         update_node_udp(n, &from);
656                 else if(debug_level >= DEBUG_PROTOCOL) {
657                         hostname = sockaddr2hostname(&from);
658                         logger(DEBUG_PROTOCOL, LOG_WARNING, "Received UDP packet from unknown source %s", hostname);
659                         free(hostname);
660                         return;
661                 }
662                 else
663                         return;
664         }
665
666         n->sock = ls - listen_socket;
667
668         receive_udppacket(n, &pkt);
669 }