Replace pointers to global splay trees with structs.
[tinc] / src / route.c
1 /*
2     route.c -- routing
3     Copyright (C) 2000-2005 Ivo Timmermans,
4                   2000-2018 Guus Sliepen <guus@tinc-vpn.org>
5
6     This program is free software; you can redistribute it and/or modify
7     it under the terms of the GNU General Public License as published by
8     the Free Software Foundation; either version 2 of the License, or
9     (at your option) any later version.
10
11     This program is distributed in the hope that it will be useful,
12     but WITHOUT ANY WARRANTY; without even the implied warranty of
13     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14     GNU General Public License for more details.
15
16     You should have received a copy of the GNU General Public License along
17     with this program; if not, write to the Free Software Foundation, Inc.,
18     51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
19 */
20
21 #include "system.h"
22
23 #include "connection.h"
24 #include "control_common.h"
25 #include "ethernet.h"
26 #include "ipv4.h"
27 #include "ipv6.h"
28 #include "logger.h"
29 #include "meta.h"
30 #include "net.h"
31 #include "protocol.h"
32 #include "route.h"
33 #include "subnet.h"
34
35 rmode_t routing_mode = RMODE_ROUTER;
36 fmode_t forwarding_mode = FMODE_INTERNAL;
37 bmode_t broadcast_mode = BMODE_MST;
38 bool decrement_ttl = false;
39 bool directonly = false;
40 bool priorityinheritance = false;
41 int macexpire = 600;
42 bool overwrite_mac = false;
43 mac_t mymac = {{0xFE, 0xFD, 0, 0, 0, 0}};
44 bool pcap = false;
45
46 /* Sizes of various headers */
47
48 static const size_t ether_size = sizeof(struct ether_header);
49 static const size_t arp_size = sizeof(struct ether_arp);
50 static const size_t ip_size = sizeof(struct ip);
51 static const size_t icmp_size = sizeof(struct icmp) - sizeof(struct ip);
52 static const size_t ip6_size = sizeof(struct ip6_hdr);
53 static const size_t icmp6_size = sizeof(struct icmp6_hdr);
54 static const size_t ns_size = sizeof(struct nd_neighbor_solicit);
55 static const size_t opt_size = sizeof(struct nd_opt_hdr);
56
57 #ifndef MAX
58 #define MAX(a, b) ((a) > (b) ? (a) : (b))
59 #endif
60
61 static timeout_t age_subnets_timeout;
62
63 /* RFC 1071 */
64
65 static uint16_t inet_checksum(void *vdata, size_t len, uint16_t prevsum) {
66         uint8_t *data = vdata;
67         uint16_t word;
68         uint32_t checksum = prevsum ^ 0xFFFF;
69
70         while(len >= 2) {
71                 memcpy(&word, data, sizeof(word));
72                 checksum += word;
73                 data += 2;
74                 len -= 2;
75         }
76
77         if(len) {
78                 checksum += *data;
79         }
80
81         while(checksum >> 16) {
82                 checksum = (checksum & 0xFFFF) + (checksum >> 16);
83         }
84
85         return (uint16_t) ~checksum;
86 }
87
88 static bool ratelimit(int frequency) {
89         static time_t lasttime = 0;
90         static int count = 0;
91
92         if(lasttime == now.tv_sec) {
93                 if(count >= frequency) {
94                         return true;
95                 }
96         } else {
97                 lasttime = now.tv_sec;
98                 count = 0;
99         }
100
101         count++;
102         return false;
103 }
104
105 static bool checklength(node_t *source, vpn_packet_t *packet, length_t length) {
106         if(packet->len < length) {
107                 logger(DEBUG_TRAFFIC, LOG_WARNING, "Got too short packet from %s (%s)", source->name, source->hostname);
108                 return false;
109         } else {
110                 return true;
111         }
112 }
113
114 static void swap_mac_addresses(vpn_packet_t *packet) {
115         mac_t tmp;
116         memcpy(&tmp, &DATA(packet)[0], sizeof(tmp));
117         memcpy(&DATA(packet)[0], &DATA(packet)[6], sizeof(tmp));
118         memcpy(&DATA(packet)[6], &tmp, sizeof(tmp));
119 }
120
121 /* RFC 792 */
122
123 static void route_ipv4_unreachable(node_t *source, vpn_packet_t *packet, length_t ether_size, uint8_t type, uint8_t code) {
124         struct ip ip = {0};
125         struct icmp icmp = {0};
126
127         struct in_addr ip_src;
128         struct in_addr ip_dst;
129         uint32_t oldlen;
130
131         if(ratelimit(3)) {
132                 return;
133         }
134
135         /* Swap Ethernet source and destination addresses */
136
137         swap_mac_addresses(packet);
138
139         /* Copy headers from packet into properly aligned structs on the stack */
140
141         memcpy(&ip, DATA(packet) + ether_size, ip_size);
142
143         /* Remember original source and destination */
144
145         ip_src = ip.ip_src;
146         ip_dst = ip.ip_dst;
147
148         /* Try to reply with an IP address assigned to the local machine */
149
150         if(type == ICMP_TIME_EXCEEDED && code == ICMP_EXC_TTL) {
151                 int sockfd = socket(AF_INET, SOCK_DGRAM, 0);
152
153                 if(sockfd != -1) {
154                         struct sockaddr_in addr;
155                         memset(&addr, 0, sizeof(addr));
156                         addr.sin_family = AF_INET;
157                         addr.sin_addr = ip.ip_src;
158
159                         if(!connect(sockfd, (const struct sockaddr *) &addr, sizeof(addr))) {
160                                 memset(&addr, 0, sizeof(addr));
161                                 addr.sin_family = AF_INET;
162                                 socklen_t addrlen = sizeof(addr);
163
164                                 if(!getsockname(sockfd, (struct sockaddr *) &addr, &addrlen) && (size_t)addrlen <= sizeof(addr)) {
165                                         ip_dst = addr.sin_addr;
166                                 }
167                         }
168
169                         close(sockfd);
170                 }
171         }
172
173         oldlen = packet->len - ether_size;
174
175         if(type == ICMP_DEST_UNREACH && code == ICMP_FRAG_NEEDED) {
176                 icmp.icmp_nextmtu = htons(packet->len - ether_size);
177         }
178
179         if(oldlen >= IP_MSS - ip_size - icmp_size) {
180                 oldlen = IP_MSS - ip_size - icmp_size;
181         }
182
183         /* Copy first part of original contents to ICMP message */
184
185         memmove(DATA(packet) + ether_size + ip_size + icmp_size, DATA(packet) + ether_size, oldlen);
186
187         /* Fill in IPv4 header */
188
189         ip.ip_v = 4;
190         ip.ip_hl = ip_size / 4;
191         ip.ip_tos = 0;
192         ip.ip_len = htons(ip_size + icmp_size + oldlen);
193         ip.ip_id = 0;
194         ip.ip_off = 0;
195         ip.ip_ttl = 255;
196         ip.ip_p = IPPROTO_ICMP;
197         ip.ip_sum = 0;
198         ip.ip_src = ip_dst;
199         ip.ip_dst = ip_src;
200
201         ip.ip_sum = inet_checksum(&ip, ip_size, 0xFFFF);
202
203         /* Fill in ICMP header */
204
205         icmp.icmp_type = type;
206         icmp.icmp_code = code;
207         icmp.icmp_cksum = 0;
208
209         icmp.icmp_cksum = inet_checksum(&icmp, icmp_size, 0xFFFF);
210         icmp.icmp_cksum = inet_checksum(DATA(packet) + ether_size + ip_size + icmp_size, oldlen, icmp.icmp_cksum);
211
212         /* Copy structs on stack back to packet */
213
214         memcpy(DATA(packet) + ether_size, &ip, ip_size);
215         memcpy(DATA(packet) + ether_size + ip_size, &icmp, icmp_size);
216
217         packet->len = ether_size + ip_size + icmp_size + oldlen;
218
219         send_packet(source, packet);
220 }
221
222 /* RFC 2463 */
223
224 static void route_ipv6_unreachable(node_t *source, vpn_packet_t *packet, length_t ether_size, uint8_t type, uint8_t code) {
225         struct ip6_hdr ip6;
226         struct icmp6_hdr icmp6 = {0};
227         uint16_t checksum;
228
229         struct {
230                 struct in6_addr ip6_src;        /* source address */
231                 struct in6_addr ip6_dst;        /* destination address */
232                 uint32_t length;
233                 uint32_t next;
234         } pseudo;
235
236         if(ratelimit(3)) {
237                 return;
238         }
239
240         /* Swap Ethernet source and destination addresses */
241
242         swap_mac_addresses(packet);
243
244         /* Copy headers from packet to structs on the stack */
245
246         memcpy(&ip6, DATA(packet) + ether_size, ip6_size);
247
248         /* Remember original source and destination */
249
250         pseudo.ip6_src = ip6.ip6_dst;
251         pseudo.ip6_dst = ip6.ip6_src;
252
253         /* Try to reply with an IP address assigned to the local machine */
254
255         if(type == ICMP6_TIME_EXCEEDED && code == ICMP6_TIME_EXCEED_TRANSIT) {
256                 int sockfd = socket(AF_INET6, SOCK_DGRAM, 0);
257
258                 if(sockfd != -1) {
259                         struct sockaddr_in6 addr;
260                         memset(&addr, 0, sizeof(addr));
261                         addr.sin6_family = AF_INET6;
262                         addr.sin6_addr = ip6.ip6_src;
263
264                         if(!connect(sockfd, (const struct sockaddr *) &addr, sizeof(addr))) {
265                                 memset(&addr, 0, sizeof(addr));
266                                 addr.sin6_family = AF_INET6;
267                                 socklen_t addrlen = sizeof(addr);
268
269                                 if(!getsockname(sockfd, (struct sockaddr *) &addr, &addrlen) && (size_t)addrlen <= sizeof(addr)) {
270                                         pseudo.ip6_src = addr.sin6_addr;
271                                 }
272                         }
273
274                         close(sockfd);
275                 }
276         }
277
278         pseudo.length = packet->len - ether_size;
279
280         if(type == ICMP6_PACKET_TOO_BIG) {
281                 icmp6.icmp6_mtu = htonl(pseudo.length);
282         }
283
284         if(pseudo.length >= IP_MSS - ip6_size - icmp6_size) {
285                 pseudo.length = IP_MSS - ip6_size - icmp6_size;
286         }
287
288         /* Copy first part of original contents to ICMP message */
289
290         memmove(DATA(packet) + ether_size + ip6_size + icmp6_size, DATA(packet) + ether_size, pseudo.length);
291
292         /* Fill in IPv6 header */
293
294         ip6.ip6_flow = htonl(0x60000000UL);
295         ip6.ip6_plen = htons(icmp6_size + pseudo.length);
296         ip6.ip6_nxt = IPPROTO_ICMPV6;
297         ip6.ip6_hlim = 255;
298         ip6.ip6_src = pseudo.ip6_src;
299         ip6.ip6_dst = pseudo.ip6_dst;
300
301         /* Fill in ICMP header */
302
303         icmp6.icmp6_type = type;
304         icmp6.icmp6_code = code;
305         icmp6.icmp6_cksum = 0;
306
307         /* Create pseudo header */
308
309         pseudo.length = htonl(icmp6_size + pseudo.length);
310         pseudo.next = htonl(IPPROTO_ICMPV6);
311
312         /* Generate checksum */
313
314         checksum = inet_checksum(&pseudo, sizeof(pseudo), 0xFFFF);
315         checksum = inet_checksum(&icmp6, icmp6_size, checksum);
316         checksum = inet_checksum(DATA(packet) + ether_size + ip6_size + icmp6_size, ntohl(pseudo.length) - icmp6_size, checksum);
317
318         icmp6.icmp6_cksum = checksum;
319
320         /* Copy structs on stack back to packet */
321
322         memcpy(DATA(packet) + ether_size, &ip6, ip6_size);
323         memcpy(DATA(packet) + ether_size + ip6_size, &icmp6, icmp6_size);
324
325         packet->len = ether_size + ip6_size + ntohl(pseudo.length);
326
327         send_packet(source, packet);
328 }
329
330 static bool do_decrement_ttl(node_t *source, vpn_packet_t *packet) {
331         uint16_t type = DATA(packet)[12] << 8 | DATA(packet)[13];
332         length_t ethlen = ether_size;
333
334         if(type == ETH_P_8021Q) {
335                 type = DATA(packet)[16] << 8 | DATA(packet)[17];
336                 ethlen += 4;
337         }
338
339         switch(type) {
340         case ETH_P_IP:
341                 if(!checklength(source, packet, ethlen + ip_size)) {
342                         return false;
343                 }
344
345                 if(DATA(packet)[ethlen + 8] <= 1) {
346                         if(DATA(packet)[ethlen + 11] != IPPROTO_ICMP || DATA(packet)[ethlen + 32] != ICMP_TIME_EXCEEDED) {
347                                 route_ipv4_unreachable(source, packet, ethlen, ICMP_TIME_EXCEEDED, ICMP_EXC_TTL);
348                         }
349
350                         return false;
351                 }
352
353                 uint16_t old = DATA(packet)[ethlen + 8] << 8 | DATA(packet)[ethlen + 9];
354                 DATA(packet)[ethlen + 8]--;
355                 uint16_t new = DATA(packet)[ethlen + 8] << 8 | DATA(packet)[ethlen + 9];
356
357                 uint32_t checksum = DATA(packet)[ethlen + 10] << 8 | DATA(packet)[ethlen + 11];
358                 checksum += old + (~new & 0xFFFF);
359
360                 while(checksum >> 16) {
361                         checksum = (checksum & 0xFFFF) + (checksum >> 16);
362                 }
363
364                 DATA(packet)[ethlen + 10] = checksum >> 8;
365                 DATA(packet)[ethlen + 11] = checksum & 0xff;
366
367                 return true;
368
369         case ETH_P_IPV6:
370                 if(!checklength(source, packet, ethlen + ip6_size)) {
371                         return false;
372                 }
373
374                 if(DATA(packet)[ethlen + 7] <= 1) {
375                         if(DATA(packet)[ethlen + 6] != IPPROTO_ICMPV6 || DATA(packet)[ethlen + 40] != ICMP6_TIME_EXCEEDED) {
376                                 route_ipv6_unreachable(source, packet, ethlen, ICMP6_TIME_EXCEEDED, ICMP6_TIME_EXCEED_TRANSIT);
377                         }
378
379                         return false;
380                 }
381
382                 DATA(packet)[ethlen + 7]--;
383
384                 return true;
385
386         default:
387                 return true;
388         }
389 }
390
391 static void clamp_mss(const node_t *source, const node_t *via, vpn_packet_t *packet) {
392         if(!source || !via || !(via->options & OPTION_CLAMP_MSS)) {
393                 return;
394         }
395
396         uint16_t mtu = source->mtu;
397
398         if(via != myself && via->mtu < mtu) {
399                 mtu = via->mtu;
400         }
401
402         /* Find TCP header */
403         size_t start = ether_size;
404         uint16_t type = DATA(packet)[12] << 8 | DATA(packet)[13];
405
406         if(type == ETH_P_8021Q) {
407                 start += 4;
408                 type = DATA(packet)[16] << 8 | DATA(packet)[17];
409         }
410
411         /* IP in IP (RFC 2003) packet */
412         if(type == ETH_P_IP && DATA(packet)[start + 9] == 4) {
413                 start += 20;
414         }
415
416         if(packet->len <= start + 20) {
417                 return;
418         }
419
420         if(type == ETH_P_IP && DATA(packet)[start + 9] == 6) {
421                 start += (DATA(packet)[start] & 0xf) * 4;
422         } else if(type == ETH_P_IPV6 && DATA(packet)[start + 6] == 6) {
423                 start += 40;
424         } else {
425                 return;
426         }
427
428         if(packet->len <= start + 20) {
429                 return;
430         }
431
432         /* Use data offset field to calculate length of options field */
433         int len = ((DATA(packet)[start + 12] >> 4) - 5) * 4;
434
435         if(packet->len < start + 20 + len) {
436                 return;
437         }
438
439         /* Search for MSS option header */
440         for(int i = 0; i < len;) {
441                 if(DATA(packet)[start + 20 + i] == 0) {
442                         break;
443                 }
444
445                 if(DATA(packet)[start + 20 + i] == 1) {
446                         i++;
447                         continue;
448                 }
449
450                 if(i > len - 2 || i > len - DATA(packet)[start + 21 + i]) {
451                         break;
452                 }
453
454                 if(DATA(packet)[start + 20 + i] != 2) {
455                         if(DATA(packet)[start + 21 + i] < 2) {
456                                 break;
457                         }
458
459                         i += DATA(packet)[start + 21 + i];
460                         continue;
461                 }
462
463                 if(DATA(packet)[start + 21] != 4) {
464                         break;
465                 }
466
467                 /* Found it */
468                 uint16_t oldmss = DATA(packet)[start + 22 + i] << 8 | DATA(packet)[start + 23 + i];
469                 uint16_t newmss = mtu - start - 20;
470                 uint32_t csum = DATA(packet)[start + 16] << 8 | DATA(packet)[start + 17];
471
472                 if(oldmss <= newmss) {
473                         break;
474                 }
475
476                 logger(DEBUG_TRAFFIC, LOG_INFO, "Clamping MSS of packet from %s to %s to %d", source->name, via->name, newmss);
477
478                 /* Update the MSS value and the checksum */
479                 DATA(packet)[start + 22 + i] = newmss >> 8;
480                 DATA(packet)[start + 23 + i] = newmss & 0xff;
481                 csum ^= 0xffff;
482                 csum += oldmss ^ 0xffff;
483                 csum += newmss;
484                 csum = (csum & 0xffff) + (csum >> 16);
485                 csum += csum >> 16;
486                 csum ^= 0xffff;
487                 DATA(packet)[start + 16] = csum >> 8;
488                 DATA(packet)[start + 17] = csum;
489                 break;
490         }
491 }
492
493 static void age_subnets(void *data) {
494         (void)data;
495         bool left = false;
496
497         for splay_each(subnet_t, s, myself->subnet_tree) {
498                 if(s->expires && s->expires < now.tv_sec) {
499                         if(debug_level >= DEBUG_TRAFFIC) {
500                                 char netstr[MAXNETSTR];
501
502                                 if(net2str(netstr, sizeof(netstr), s)) {
503                                         logger(DEBUG_TRAFFIC, LOG_INFO, "Subnet %s expired", netstr);
504                                 }
505                         }
506
507                         for list_each(connection_t, c, &connection_list)
508                                 if(c->edge) {
509                                         send_del_subnet(c, s);
510                                 }
511
512                         subnet_del(myself, s);
513                 } else {
514                         if(s->expires) {
515                                 left = true;
516                         }
517                 }
518         }
519
520         if(left)
521                 timeout_set(&age_subnets_timeout, &(struct timeval) {
522                 10, rand() % 100000
523         });
524 }
525
526 static void learn_mac(mac_t *address) {
527         subnet_t *subnet = lookup_subnet_mac(myself, address);
528
529         /* If we don't know this MAC address yet, store it */
530
531         if(!subnet) {
532                 logger(DEBUG_TRAFFIC, LOG_INFO, "Learned new MAC address %x:%x:%x:%x:%x:%x",
533                        address->x[0], address->x[1], address->x[2], address->x[3],
534                        address->x[4], address->x[5]);
535
536                 subnet = new_subnet();
537                 subnet->type = SUBNET_MAC;
538                 subnet->expires = now.tv_sec + macexpire;
539                 subnet->net.mac.address = *address;
540                 subnet->weight = 10;
541                 subnet_add(myself, subnet);
542                 subnet_update(myself, subnet, true);
543
544                 /* And tell all other tinc daemons it's our MAC */
545
546                 for list_each(connection_t, c, &connection_list)
547                         if(c->edge) {
548                                 send_add_subnet(c, subnet);
549                         }
550
551                 timeout_add(&age_subnets_timeout, age_subnets, NULL, &(struct timeval) {
552                         10, rand() % 100000
553                 });
554         } else {
555                 if(subnet->expires) {
556                         subnet->expires = now.tv_sec + macexpire;
557                 }
558         }
559 }
560
561 static void route_broadcast(node_t *source, vpn_packet_t *packet) {
562         if(decrement_ttl && source != myself)
563                 if(!do_decrement_ttl(source, packet)) {
564                         return;
565                 }
566
567         broadcast_packet(source, packet);
568 }
569
570 /* RFC 791 */
571
572 static void fragment_ipv4_packet(node_t *dest, vpn_packet_t *packet, length_t ether_size) {
573         struct ip ip;
574         vpn_packet_t fragment;
575         size_t maxlen, todo;
576         uint8_t *offset;
577         uint16_t ip_off, origf;
578
579         memcpy(&ip, DATA(packet) + ether_size, ip_size);
580         fragment.priority = packet->priority;
581         fragment.offset = DEFAULT_PACKET_OFFSET;
582
583         if(ip.ip_hl != ip_size / 4) {
584                 return;
585         }
586
587         todo = ntohs(ip.ip_len) - ip_size;
588
589         if(ether_size + ip_size + todo != packet->len) {
590                 logger(DEBUG_TRAFFIC, LOG_WARNING, "Length of packet (%d) doesn't match length in IPv4 header (%zu)", packet->len, ether_size + ip_size + todo);
591                 return;
592         }
593
594         logger(DEBUG_TRAFFIC, LOG_INFO, "Fragmenting packet of %d bytes to %s (%s)", packet->len, dest->name, dest->hostname);
595
596         offset = DATA(packet) + ether_size + ip_size;
597         maxlen = (MAX(dest->mtu, 590) - ether_size - ip_size) & ~0x7;
598         ip_off = ntohs(ip.ip_off);
599         origf = ip_off & ~IP_OFFMASK;
600         ip_off &= IP_OFFMASK;
601
602         while(todo) {
603                 size_t len = todo > maxlen ? maxlen : todo;
604                 memcpy(DATA(&fragment) + ether_size + ip_size, offset, len);
605                 todo -= len;
606                 offset += len;
607
608                 ip.ip_len = htons(ip_size + len);
609                 ip.ip_off = htons(ip_off | origf | (todo ? IP_MF : 0));
610                 ip.ip_sum = 0;
611                 ip.ip_sum = inet_checksum(&ip, ip_size, 0xFFFF);
612                 memcpy(DATA(&fragment), DATA(packet), ether_size);
613                 memcpy(DATA(&fragment) + ether_size, &ip, ip_size);
614                 fragment.len = ether_size + ip_size + len;
615
616                 send_packet(dest, &fragment);
617
618                 ip_off += len / 8;
619         }
620 }
621
622 static void route_ipv4(node_t *source, vpn_packet_t *packet) {
623         if(!checklength(source, packet, ether_size + ip_size)) {
624                 return;
625         }
626
627         subnet_t *subnet;
628         node_t *via;
629         ipv4_t dest;
630
631         memcpy(&dest, &DATA(packet)[30], sizeof(dest));
632         subnet = lookup_subnet_ipv4(&dest);
633
634         if(!subnet) {
635                 logger(DEBUG_TRAFFIC, LOG_WARNING, "Cannot route packet from %s (%s): unknown IPv4 destination address %d.%d.%d.%d",
636                        source->name, source->hostname,
637                        dest.x[0],
638                        dest.x[1],
639                        dest.x[2],
640                        dest.x[3]);
641
642                 route_ipv4_unreachable(source, packet, ether_size, ICMP_DEST_UNREACH, ICMP_NET_UNKNOWN);
643                 return;
644         }
645
646         if(!subnet->owner) {
647                 route_broadcast(source, packet);
648                 return;
649         }
650
651         if(subnet->owner == source) {
652                 logger(DEBUG_TRAFFIC, LOG_WARNING, "Packet looping back to %s (%s)!", source->name, source->hostname);
653                 return;
654         }
655
656         if(!subnet->owner->status.reachable) {
657                 route_ipv4_unreachable(source, packet, ether_size, ICMP_DEST_UNREACH, ICMP_NET_UNREACH);
658                 return;
659         }
660
661         if(forwarding_mode == FMODE_OFF && source != myself && subnet->owner != myself) {
662                 route_ipv4_unreachable(source, packet, ether_size, ICMP_DEST_UNREACH, ICMP_NET_ANO);
663                 return;
664         }
665
666         if(decrement_ttl && source != myself && subnet->owner != myself)
667                 if(!do_decrement_ttl(source, packet)) {
668                         return;
669                 }
670
671         if(priorityinheritance) {
672                 packet->priority = DATA(packet)[15];
673         }
674
675         via = (subnet->owner->via == myself) ? subnet->owner->nexthop : subnet->owner->via;
676
677         if(via == source) {
678                 logger(DEBUG_TRAFFIC, LOG_ERR, "Routing loop for packet from %s (%s)!", source->name, source->hostname);
679                 return;
680         }
681
682         if(directonly && subnet->owner != via) {
683                 route_ipv4_unreachable(source, packet, ether_size, ICMP_DEST_UNREACH, ICMP_NET_ANO);
684                 return;
685         }
686
687         if(via && packet->len > MAX(via->mtu, 590) && via != myself) {
688                 logger(DEBUG_TRAFFIC, LOG_INFO, "Packet for %s (%s) length %d larger than MTU %d", subnet->owner->name, subnet->owner->hostname, packet->len, via->mtu);
689
690                 if(DATA(packet)[20] & 0x40) {
691                         packet->len = MAX(via->mtu, 590);
692                         route_ipv4_unreachable(source, packet, ether_size, ICMP_DEST_UNREACH, ICMP_FRAG_NEEDED);
693                 } else {
694                         fragment_ipv4_packet(via, packet, ether_size);
695                 }
696
697                 return;
698         }
699
700         clamp_mss(source, via, packet);
701
702         send_packet(subnet->owner, packet);
703 }
704
705 static void route_neighborsol(node_t *source, vpn_packet_t *packet);
706
707 static void route_ipv6(node_t *source, vpn_packet_t *packet) {
708         if(!checklength(source, packet, ether_size + ip6_size)) {
709                 return;
710         }
711
712         if(DATA(packet)[20] == IPPROTO_ICMPV6 && checklength(source, packet, ether_size + ip6_size + icmp6_size) && DATA(packet)[54] == ND_NEIGHBOR_SOLICIT) {
713                 route_neighborsol(source, packet);
714                 return;
715         }
716
717         subnet_t *subnet;
718         node_t *via;
719         ipv6_t dest;
720
721         memcpy(&dest, &DATA(packet)[38], sizeof(dest));
722         subnet = lookup_subnet_ipv6(&dest);
723
724         if(!subnet) {
725                 logger(DEBUG_TRAFFIC, LOG_WARNING, "Cannot route packet from %s (%s): unknown IPv6 destination address %hx:%hx:%hx:%hx:%hx:%hx:%hx:%hx",
726                        source->name, source->hostname,
727                        ntohs(dest.x[0]),
728                        ntohs(dest.x[1]),
729                        ntohs(dest.x[2]),
730                        ntohs(dest.x[3]),
731                        ntohs(dest.x[4]),
732                        ntohs(dest.x[5]),
733                        ntohs(dest.x[6]),
734                        ntohs(dest.x[7]));
735
736                 route_ipv6_unreachable(source, packet, ether_size, ICMP6_DST_UNREACH, ICMP6_DST_UNREACH_ADDR);
737                 return;
738         }
739
740         if(!subnet->owner) {
741                 route_broadcast(source, packet);
742                 return;
743         }
744
745         if(subnet->owner == source) {
746                 logger(DEBUG_TRAFFIC, LOG_WARNING, "Packet looping back to %s (%s)!", source->name, source->hostname);
747                 return;
748         }
749
750         if(!subnet->owner->status.reachable) {
751                 route_ipv6_unreachable(source, packet, ether_size, ICMP6_DST_UNREACH, ICMP6_DST_UNREACH_NOROUTE);
752                 return;
753         }
754
755         if(forwarding_mode == FMODE_OFF && source != myself && subnet->owner != myself) {
756                 route_ipv6_unreachable(source, packet, ether_size, ICMP6_DST_UNREACH, ICMP6_DST_UNREACH_ADMIN);
757                 return;
758         }
759
760         if(decrement_ttl && source != myself && subnet->owner != myself)
761                 if(!do_decrement_ttl(source, packet)) {
762                         return;
763                 }
764
765         if(priorityinheritance) {
766                 packet->priority = ((DATA(packet)[14] & 0x0f) << 4) | (DATA(packet)[15] >> 4);
767         }
768
769         via = (subnet->owner->via == myself) ? subnet->owner->nexthop : subnet->owner->via;
770
771         if(via == source) {
772                 logger(DEBUG_TRAFFIC, LOG_ERR, "Routing loop for packet from %s (%s)!", source->name, source->hostname);
773                 return;
774         }
775
776         if(directonly && subnet->owner != via) {
777                 route_ipv6_unreachable(source, packet, ether_size, ICMP6_DST_UNREACH, ICMP6_DST_UNREACH_ADMIN);
778                 return;
779         }
780
781         if(via && packet->len > MAX(via->mtu, 1294) && via != myself) {
782                 logger(DEBUG_TRAFFIC, LOG_INFO, "Packet for %s (%s) length %d larger than MTU %d", subnet->owner->name, subnet->owner->hostname, packet->len, via->mtu);
783                 packet->len = MAX(via->mtu, 1294);
784                 route_ipv6_unreachable(source, packet, ether_size, ICMP6_PACKET_TOO_BIG, 0);
785                 return;
786         }
787
788         clamp_mss(source, via, packet);
789
790         send_packet(subnet->owner, packet);
791 }
792
793 /* RFC 2461 */
794
795 static void route_neighborsol(node_t *source, vpn_packet_t *packet) {
796         struct ip6_hdr ip6;
797         struct nd_neighbor_solicit ns;
798         struct nd_opt_hdr opt;
799         subnet_t *subnet;
800         uint16_t checksum;
801         bool has_opt;
802
803         struct {
804                 struct in6_addr ip6_src;
805                 struct in6_addr ip6_dst;
806                 uint32_t length;
807                 uint32_t next;
808         } pseudo;
809
810         if(!checklength(source, packet, ether_size + ip6_size + ns_size)) {
811                 return;
812         }
813
814         has_opt = packet->len >= ether_size + ip6_size + ns_size + opt_size + ETH_ALEN;
815
816         if(source != myself) {
817                 logger(DEBUG_TRAFFIC, LOG_WARNING, "Got neighbor solicitation request from %s (%s) while in router mode!", source->name, source->hostname);
818                 return;
819         }
820
821         /* Copy headers from packet to structs on the stack */
822
823         memcpy(&ip6, DATA(packet) + ether_size, ip6_size);
824         memcpy(&ns, DATA(packet) + ether_size + ip6_size, ns_size);
825
826         if(has_opt) {
827                 memcpy(&opt, DATA(packet) + ether_size + ip6_size + ns_size, opt_size);
828         }
829
830         /* First, snatch the source address from the neighbor solicitation packet */
831
832         if(overwrite_mac) {
833                 memcpy(mymac.x, DATA(packet) + ETH_ALEN, ETH_ALEN);
834         }
835
836         /* Check if this is a valid neighbor solicitation request */
837
838         if(ns.nd_ns_hdr.icmp6_type != ND_NEIGHBOR_SOLICIT ||
839                         (has_opt && opt.nd_opt_type != ND_OPT_SOURCE_LINKADDR)) {
840                 logger(DEBUG_TRAFFIC, LOG_WARNING, "Cannot route packet: received unknown type neighbor solicitation request");
841                 return;
842         }
843
844         /* Create pseudo header */
845
846         pseudo.ip6_src = ip6.ip6_src;
847         pseudo.ip6_dst = ip6.ip6_dst;
848
849         if(has_opt) {
850                 pseudo.length = htonl(ns_size + opt_size + ETH_ALEN);
851         } else {
852                 pseudo.length = htonl(ns_size);
853         }
854
855         pseudo.next = htonl(IPPROTO_ICMPV6);
856
857         /* Generate checksum */
858
859         checksum = inet_checksum(&pseudo, sizeof(pseudo), 0xFFFF);
860         checksum = inet_checksum(&ns, ns_size, checksum);
861
862         if(has_opt) {
863                 checksum = inet_checksum(&opt, opt_size, checksum);
864                 checksum = inet_checksum(DATA(packet) + ether_size + ip6_size + ns_size + opt_size, ETH_ALEN, checksum);
865         }
866
867         if(checksum) {
868                 logger(DEBUG_TRAFFIC, LOG_WARNING, "Cannot route packet: checksum error for neighbor solicitation request");
869                 return;
870         }
871
872         /* Check if the IPv6 address exists on the VPN */
873
874         subnet = lookup_subnet_ipv6((ipv6_t *) &ns.nd_ns_target);
875
876         if(!subnet) {
877                 logger(DEBUG_TRAFFIC, LOG_WARNING, "Cannot route packet: neighbor solicitation request for unknown address %hx:%hx:%hx:%hx:%hx:%hx:%hx:%hx",
878                        ntohs(((uint16_t *) &ns.nd_ns_target)[0]),
879                        ntohs(((uint16_t *) &ns.nd_ns_target)[1]),
880                        ntohs(((uint16_t *) &ns.nd_ns_target)[2]),
881                        ntohs(((uint16_t *) &ns.nd_ns_target)[3]),
882                        ntohs(((uint16_t *) &ns.nd_ns_target)[4]),
883                        ntohs(((uint16_t *) &ns.nd_ns_target)[5]),
884                        ntohs(((uint16_t *) &ns.nd_ns_target)[6]),
885                        ntohs(((uint16_t *) &ns.nd_ns_target)[7]));
886
887                 return;
888         }
889
890         /* Check if it is for our own subnet */
891
892         if(subnet->owner == myself) {
893                 return;        /* silently ignore */
894         }
895
896         if(decrement_ttl)
897                 if(!do_decrement_ttl(source, packet)) {
898                         return;
899                 }
900
901         /* Create neighbor advertation reply */
902
903         memcpy(DATA(packet), DATA(packet) + ETH_ALEN, ETH_ALEN); /* copy destination address */
904         DATA(packet)[ETH_ALEN * 2 - 1] ^= 0xFF;                  /* mangle source address so it looks like it's not from us */
905
906         ip6.ip6_dst = ip6.ip6_src;                               /* swap destination and source protocol address */
907         ip6.ip6_src = ns.nd_ns_target;
908
909         if(has_opt) {
910                 memcpy(DATA(packet) + ether_size + ip6_size + ns_size + opt_size, DATA(packet) + ETH_ALEN, ETH_ALEN);        /* add fake source hard addr */
911         }
912
913         ns.nd_ns_cksum = 0;
914         ns.nd_ns_type = ND_NEIGHBOR_ADVERT;
915         ns.nd_ns_reserved = htonl(0x40000000UL);                 /* Set solicited flag */
916         opt.nd_opt_type = ND_OPT_TARGET_LINKADDR;
917
918         /* Create pseudo header */
919
920         pseudo.ip6_src = ip6.ip6_src;
921         pseudo.ip6_dst = ip6.ip6_dst;
922
923         if(has_opt) {
924                 pseudo.length = htonl(ns_size + opt_size + ETH_ALEN);
925         } else {
926                 pseudo.length = htonl(ns_size);
927         }
928
929         pseudo.next = htonl(IPPROTO_ICMPV6);
930
931         /* Generate checksum */
932
933         checksum = inet_checksum(&pseudo, sizeof(pseudo), 0xFFFF);
934         checksum = inet_checksum(&ns, ns_size, checksum);
935
936         if(has_opt) {
937                 checksum = inet_checksum(&opt, opt_size, checksum);
938                 checksum = inet_checksum(DATA(packet) + ether_size + ip6_size + ns_size + opt_size, ETH_ALEN, checksum);
939         }
940
941         ns.nd_ns_hdr.icmp6_cksum = checksum;
942
943         /* Copy structs on stack back to packet */
944
945         memcpy(DATA(packet) + ether_size, &ip6, ip6_size);
946         memcpy(DATA(packet) + ether_size + ip6_size, &ns, ns_size);
947
948         if(has_opt) {
949                 memcpy(DATA(packet) + ether_size + ip6_size + ns_size, &opt, opt_size);
950         }
951
952         send_packet(source, packet);
953 }
954
955 /* RFC 826 */
956
957 static void route_arp(node_t *source, vpn_packet_t *packet) {
958         struct ether_arp arp;
959         subnet_t *subnet;
960         struct in_addr addr;
961
962         if(!checklength(source, packet, ether_size + arp_size)) {
963                 return;
964         }
965
966         if(source != myself) {
967                 logger(DEBUG_TRAFFIC, LOG_WARNING, "Got ARP request from %s (%s) while in router mode!", source->name, source->hostname);
968                 return;
969         }
970
971         /* First, snatch the source address from the ARP packet */
972
973         if(overwrite_mac) {
974                 memcpy(mymac.x, DATA(packet) + ETH_ALEN, ETH_ALEN);
975         }
976
977         /* Copy headers from packet to structs on the stack */
978
979         memcpy(&arp, DATA(packet) + ether_size, arp_size);
980
981         /* Check if this is a valid ARP request */
982
983         if(ntohs(arp.arp_hrd) != ARPHRD_ETHER || ntohs(arp.arp_pro) != ETH_P_IP ||
984                         arp.arp_hln != ETH_ALEN || arp.arp_pln != sizeof(addr) || ntohs(arp.arp_op) != ARPOP_REQUEST) {
985                 logger(DEBUG_TRAFFIC, LOG_WARNING, "Cannot route packet: received unknown type ARP request");
986                 return;
987         }
988
989         /* Check if the IPv4 address exists on the VPN */
990
991         subnet = lookup_subnet_ipv4((ipv4_t *) &arp.arp_tpa);
992
993         if(!subnet) {
994                 logger(DEBUG_TRAFFIC, LOG_WARNING, "Cannot route packet: ARP request for unknown address %d.%d.%d.%d",
995                        arp.arp_tpa[0], arp.arp_tpa[1], arp.arp_tpa[2],
996                        arp.arp_tpa[3]);
997                 return;
998         }
999
1000         /* Check if it is for our own subnet */
1001
1002         if(subnet->owner == myself) {
1003                 return;        /* silently ignore */
1004         }
1005
1006         if(decrement_ttl)
1007                 if(!do_decrement_ttl(source, packet)) {
1008                         return;
1009                 }
1010
1011         memcpy(&addr, arp.arp_tpa, sizeof(addr));                 /* save protocol addr */
1012         memcpy(arp.arp_tpa, arp.arp_spa, sizeof(addr));           /* swap destination and source protocol address */
1013         memcpy(arp.arp_spa, &addr, sizeof(addr));                 /* ... */
1014
1015         memcpy(arp.arp_tha, arp.arp_sha, ETH_ALEN);              /* set target hard/proto addr */
1016         memcpy(arp.arp_sha, DATA(packet) + ETH_ALEN, ETH_ALEN);  /* set source hard/proto addr */
1017         arp.arp_sha[ETH_ALEN - 1] ^= 0xFF;                       /* for consistency with route_packet() */
1018         arp.arp_op = htons(ARPOP_REPLY);
1019
1020         /* Copy structs on stack back to packet */
1021
1022         memcpy(DATA(packet) + ether_size, &arp, arp_size);
1023
1024         send_packet(source, packet);
1025 }
1026
1027 static void route_mac(node_t *source, vpn_packet_t *packet) {
1028         subnet_t *subnet;
1029         mac_t dest;
1030
1031         /* Learn source address */
1032
1033         if(source == myself) {
1034                 mac_t src;
1035                 memcpy(&src, &DATA(packet)[6], sizeof(src));
1036                 learn_mac(&src);
1037         }
1038
1039         /* Lookup destination address */
1040
1041         memcpy(&dest, &DATA(packet)[0], sizeof(dest));
1042         subnet = lookup_subnet_mac(NULL, &dest);
1043
1044         if(!subnet || !subnet->owner) {
1045                 route_broadcast(source, packet);
1046                 return;
1047         }
1048
1049         if(subnet->owner == source) {
1050                 logger(DEBUG_TRAFFIC, LOG_WARNING, "Packet looping back to %s (%s)!", source->name, source->hostname);
1051                 return;
1052         }
1053
1054         if(forwarding_mode == FMODE_OFF && source != myself && subnet->owner != myself) {
1055                 return;
1056         }
1057
1058         if(decrement_ttl && source != myself && subnet->owner != myself)
1059                 if(!do_decrement_ttl(source, packet)) {
1060                         return;
1061                 }
1062
1063         uint16_t type = DATA(packet)[12] << 8 | DATA(packet)[13];
1064
1065         if(priorityinheritance) {
1066                 if(type == ETH_P_IP && packet->len >= ether_size + ip_size) {
1067                         packet->priority = DATA(packet)[15];
1068                 } else if(type == ETH_P_IPV6 && packet->len >= ether_size + ip6_size) {
1069                         packet->priority = ((DATA(packet)[14] & 0x0f) << 4) | (DATA(packet)[15] >> 4);
1070                 }
1071         }
1072
1073         // Handle packets larger than PMTU
1074
1075         node_t *via = (subnet->owner->via == myself) ? subnet->owner->nexthop : subnet->owner->via;
1076
1077         if(directonly && subnet->owner != via) {
1078                 return;
1079         }
1080
1081         if(via && packet->len > via->mtu && via != myself) {
1082                 logger(DEBUG_TRAFFIC, LOG_INFO, "Packet for %s (%s) length %d larger than MTU %d", subnet->owner->name, subnet->owner->hostname, packet->len, via->mtu);
1083                 length_t ethlen = 14;
1084
1085                 if(type == ETH_P_8021Q) {
1086                         type = DATA(packet)[16] << 8 | DATA(packet)[17];
1087                         ethlen += 4;
1088                 }
1089
1090                 if(type == ETH_P_IP && packet->len > 576 + ethlen) {
1091                         if(DATA(packet)[6 + ethlen] & 0x40) {
1092                                 packet->len = via->mtu;
1093                                 route_ipv4_unreachable(source, packet, ethlen, ICMP_DEST_UNREACH, ICMP_FRAG_NEEDED);
1094                         } else {
1095                                 fragment_ipv4_packet(via, packet, ethlen);
1096                         }
1097
1098                         return;
1099                 } else if(type == ETH_P_IPV6 && packet->len > 1280 + ethlen) {
1100                         packet->len = via->mtu;
1101                         route_ipv6_unreachable(source, packet, ethlen, ICMP6_PACKET_TOO_BIG, 0);
1102                         return;
1103                 }
1104         }
1105
1106         clamp_mss(source, via, packet);
1107
1108         send_packet(subnet->owner, packet);
1109 }
1110
1111 static void send_pcap(vpn_packet_t *packet) {
1112         pcap = false;
1113
1114         for list_each(connection_t, c, &connection_list) {
1115                 if(!c->status.pcap) {
1116                         continue;
1117                 }
1118
1119                 pcap = true;
1120                 int len = packet->len;
1121
1122                 if(c->outmaclength && c->outmaclength < len) {
1123                         len = c->outmaclength;
1124                 }
1125
1126                 if(send_request(c, "%d %d %d", CONTROL, REQ_PCAP, len)) {
1127                         send_meta(c, DATA(packet), len);
1128                 }
1129         }
1130 }
1131
1132 void route(node_t *source, vpn_packet_t *packet) {
1133         if(pcap) {
1134                 send_pcap(packet);
1135         }
1136
1137         if(forwarding_mode == FMODE_KERNEL && source != myself) {
1138                 send_packet(myself, packet);
1139                 return;
1140         }
1141
1142         if(!checklength(source, packet, ether_size)) {
1143                 return;
1144         }
1145
1146         uint16_t type = DATA(packet)[12] << 8 | DATA(packet)[13];
1147
1148         switch(routing_mode) {
1149         case RMODE_ROUTER:
1150                 switch(type) {
1151                 case ETH_P_ARP:
1152                         route_arp(source, packet);
1153                         break;
1154
1155                 case ETH_P_IP:
1156                         route_ipv4(source, packet);
1157                         break;
1158
1159                 case ETH_P_IPV6:
1160                         route_ipv6(source, packet);
1161                         break;
1162
1163                 default:
1164                         logger(DEBUG_TRAFFIC, LOG_WARNING, "Cannot route packet from %s (%s): unknown type %hx", source->name, source->hostname, type);
1165                         break;
1166                 }
1167
1168                 break;
1169
1170         case RMODE_SWITCH:
1171                 route_mac(source, packet);
1172                 break;
1173
1174         case RMODE_HUB:
1175                 route_broadcast(source, packet);
1176                 break;
1177         }
1178 }