a6f6e4636a5b7043b99070404ba301ac839f1420
[tinc] / src / route.c
1 /*
2     route.c -- routing
3     Copyright (C) 2000-2003 Ivo Timmermans <ivo@o2w.nl>,
4                   2000-2003 Guus Sliepen <guus@sliepen.eu.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
17     along with this program; if not, write to the Free Software
18     Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
19
20     $Id: route.c,v 1.1.2.60 2003/07/18 12:16:24 guus Exp $
21 */
22
23 #include "system.h"
24
25 #ifdef HAVE_NET_ETHERNET_H
26 #include <net/ethernet.h>
27 #endif
28 #ifdef HAVE_NET_IF_ARP_H
29 #include <net/if_arp.h>
30 #endif
31 #ifdef HAVE_NETINET_IP_ICMP_H
32 #include <netinet/ip_icmp.h>
33 #endif
34 #ifdef HAVE_NETINET_IP6_H
35 #include <netinet/ip6.h>
36 #endif
37 #ifdef HAVE_NETINET_ICMP6_H
38 #include <netinet/icmp6.h>
39 #endif
40 #ifdef HAVE_NETINET_IF_ETHER_H
41 #include <netinet/if_ether.h>
42 #endif
43
44 #include "avl_tree.h"
45 #include "connection.h"
46 #include "device.h"
47 #include "ethernet.h"
48 #include "ipv4.h"
49 #include "ipv6.h"
50 #include "logger.h"
51 #include "net.h"
52 #include "protocol.h"
53 #include "route.h"
54 #include "subnet.h"
55 #include "utils.h"
56
57 /* Missing definitions */
58
59 #ifndef ETHER_ADDR_LEN
60 #define ETHER_ADDR_LEN 6
61 #endif
62
63 #ifndef ICMP_DEST_UNREACH
64 #define ICMP_DEST_UNREACH 3
65 #endif
66
67 #ifndef ICMP_NET_UNKNOWN
68 #define ICMP_NET_UNKNOWN 6
69 #endif
70
71 #ifndef ICMP_NET_UNREACH
72 #define ICMP_NET_UNREACH 0
73 #endif
74
75 int routing_mode = RMODE_ROUTER;
76 int priorityinheritance = 0;
77 int macexpire = 600;
78 int overwrite_mac = 0;
79 mac_t mymac = {{0xFE, 0xFD, 0, 0, 0, 0}};
80
81 /* RFC 1071 */
82
83 static uint16_t inet_checksum(void *data, int len, uint16_t prevsum)
84 {
85         uint16_t *p = data;
86         uint32_t checksum = prevsum ^ 0xFFFF;
87
88         while(len >= 2) {
89                 checksum += *p++;
90                 len -= 2;
91         }
92         
93         if(len)
94                 checksum += *(unsigned char *)p;
95
96         while(checksum >> 16)
97                 checksum = (checksum & 0xFFFF) + (checksum >> 16);
98
99         return ~checksum;
100 }
101
102 static int ratelimit(void) {
103         static time_t lasttime = 0;
104         
105         if(lasttime == now)
106                 return 1;
107
108         lasttime = now;
109         return 0;
110 }
111         
112 static void learn_mac(mac_t *address)
113 {
114         subnet_t *subnet;
115         avl_node_t *node;
116         connection_t *c;
117
118         cp();
119
120         subnet = lookup_subnet_mac(address);
121
122         /* If we don't know this MAC address yet, store it */
123
124         if(!subnet || subnet->owner != myself) {
125                 ifdebug(TRAFFIC) logger(LOG_INFO, _("Learned new MAC address %hx:%hx:%hx:%hx:%hx:%hx"),
126                                    address->x[0], address->x[1], address->x[2], address->x[3],
127                                    address->x[4], address->x[5]);
128
129                 subnet = new_subnet();
130                 subnet->type = SUBNET_MAC;
131                 memcpy(&subnet->net.mac.address, address, sizeof(mac_t));
132                 subnet_add(myself, subnet);
133
134                 /* And tell all other tinc daemons it's our MAC */
135
136                 for(node = connection_tree->head; node; node = node->next) {
137                         c = (connection_t *) node->data;
138                         if(c->status.active)
139                                 send_add_subnet(c, subnet);
140                 }
141         }
142
143         subnet->net.mac.lastseen = now;
144 }
145
146 void age_mac(void)
147 {
148         subnet_t *s;
149         connection_t *c;
150         avl_node_t *node, *next, *node2;
151
152         cp();
153
154         for(node = myself->subnet_tree->head; node; node = next) {
155                 next = node->next;
156                 s = (subnet_t *) node->data;
157                 if(s->type == SUBNET_MAC && s->net.mac.lastseen && s->net.mac.lastseen + macexpire < now) {
158                         ifdebug(TRAFFIC) logger(LOG_INFO, _("MAC address %hx:%hx:%hx:%hx:%hx:%hx expired"),
159                                            s->net.mac.address.x[0], s->net.mac.address.x[1],
160                                            s->net.mac.address.x[2], s->net.mac.address.x[3],
161                                            s->net.mac.address.x[4], s->net.mac.address.x[5]);
162
163                         for(node2 = connection_tree->head; node2; node2 = node2->next) {
164                                 c = (connection_t *) node2->data;
165                                 if(c->status.active)
166                                         send_del_subnet(c, s);
167                         }
168
169                         subnet_del(myself, s);
170                 }
171         }
172 }
173
174 static node_t *route_mac(vpn_packet_t *packet)
175 {
176         subnet_t *subnet;
177
178         cp();
179
180         /* Learn source address */
181
182         learn_mac((mac_t *)(&packet->data[6]));
183
184         /* Lookup destination address */
185
186         subnet = lookup_subnet_mac((mac_t *)(&packet->data[0]));
187
188         if(subnet)
189                 return subnet->owner;
190         else
191                 return NULL;
192 }
193
194 /* RFC 792 */
195
196 static void route_ipv4_unreachable(vpn_packet_t *packet, uint8_t code)
197 {
198         struct ip *hdr;
199         struct icmp *icmp;
200         
201         struct in_addr ip_src;
202         struct in_addr ip_dst;
203         uint32_t oldlen;
204
205         if(ratelimit())
206                 return;
207         
208         cp();
209
210         hdr = (struct ip *)(packet->data + 14);
211         icmp = (struct icmp *)(packet->data + 14 + 20);
212
213         /* Remember original source and destination */
214                 
215         memcpy(&ip_src, &hdr->ip_src, 4);
216         memcpy(&ip_dst, &hdr->ip_dst, 4);
217         oldlen = packet->len - 14;
218         
219         if(oldlen >= IP_MSS - sizeof(*hdr) - sizeof(*icmp))
220                 oldlen = IP_MSS - sizeof(*hdr) - sizeof(*icmp);
221         
222         /* Copy first part of original contents to ICMP message */
223         
224         memmove(&icmp->icmp_ip, hdr, oldlen);
225
226         /* Fill in IPv4 header */
227         
228         hdr->ip_v = 4;
229         hdr->ip_hl = sizeof(*hdr) / 4;
230         hdr->ip_tos = 0;
231         hdr->ip_len = htons(20 + 8 + oldlen);
232         hdr->ip_id = 0;
233         hdr->ip_off = 0;
234         hdr->ip_ttl = 255;
235         hdr->ip_p = IPPROTO_ICMP;
236         hdr->ip_sum = 0;
237         memcpy(&hdr->ip_src, &ip_dst, 4);
238         memcpy(&hdr->ip_dst, &ip_src, 4);
239
240         hdr->ip_sum = inet_checksum(hdr, 20, ~0);
241         
242         /* Fill in ICMP header */
243         
244         icmp->icmp_type = ICMP_DEST_UNREACH;
245         icmp->icmp_code = code;
246         icmp->icmp_cksum = 0;
247         
248         icmp->icmp_cksum = inet_checksum(icmp, 8 + oldlen, ~0);
249         
250         packet->len = 14 + 20 + 8 + oldlen;
251         
252         write_packet(packet);
253 }
254
255 static node_t *route_ipv4(vpn_packet_t *packet)
256 {
257         subnet_t *subnet;
258
259         cp();
260
261         if(priorityinheritance)
262                 packet->priority = packet->data[15];
263
264         subnet = lookup_subnet_ipv4((ipv4_t *) & packet->data[30]);
265
266         if(!subnet) {
267                 ifdebug(TRAFFIC) logger(LOG_WARNING, _("Cannot route packet: unknown IPv4 destination address %d.%d.%d.%d"),
268                                    packet->data[30], packet->data[31], packet->data[32],
269                                    packet->data[33]);
270
271                 route_ipv4_unreachable(packet, ICMP_NET_UNKNOWN);
272                 return NULL;
273         }
274         
275         if(!subnet->owner->status.reachable)
276                 route_ipv4_unreachable(packet, ICMP_NET_UNREACH);
277
278         return subnet->owner;
279 }
280
281 /* RFC 2463 */
282
283 static void route_ipv6_unreachable(vpn_packet_t *packet, uint8_t code)
284 {
285         struct ip6_hdr *hdr;
286         struct icmp6_hdr *icmp;
287         uint16_t checksum;      
288
289         struct {
290                 struct in6_addr ip6_src;        /* source address */
291                 struct in6_addr ip6_dst;        /* destination address */
292                 uint32_t length;
293                 uint32_t next;
294         } pseudo;
295
296         if(ratelimit())
297                 return;
298         
299         cp();
300
301         hdr = (struct ip6_hdr *)(packet->data + 14);
302         icmp = (struct icmp6_hdr *)(packet->data + 14 + sizeof(*hdr));
303
304         /* Remember original source and destination */
305                 
306         memcpy(&pseudo.ip6_src, &hdr->ip6_dst, 16);
307         memcpy(&pseudo.ip6_dst, &hdr->ip6_src, 16);
308         pseudo.length = ntohs(hdr->ip6_plen) + sizeof(*hdr);
309         
310         if(pseudo.length >= IP_MSS - sizeof(*hdr) - sizeof(*icmp))
311                 pseudo.length = IP_MSS - sizeof(*hdr) - sizeof(*icmp);
312         
313         /* Copy first part of original contents to ICMP message */
314         
315         memmove(((char *)icmp) + sizeof(*icmp), hdr, pseudo.length);
316
317         /* Fill in IPv6 header */
318         
319         hdr->ip6_flow = htonl(0x60000000UL);
320         hdr->ip6_plen = htons(sizeof(*icmp) + pseudo.length);
321         hdr->ip6_nxt = IPPROTO_ICMPV6;
322         hdr->ip6_hlim = 255;
323         memcpy(&hdr->ip6_dst, &pseudo.ip6_dst, 16);
324         memcpy(&hdr->ip6_src, &pseudo.ip6_src, 16);
325
326         /* Fill in ICMP header */
327         
328         icmp->icmp6_type = ICMP6_DST_UNREACH;
329         icmp->icmp6_code = code;
330         icmp->icmp6_cksum = 0;
331
332         /* Create pseudo header */
333                 
334         pseudo.length = htonl(sizeof(*icmp) + pseudo.length);
335         pseudo.next = htonl(IPPROTO_ICMPV6);
336
337         /* Generate checksum */
338         
339         checksum = inet_checksum(&pseudo, sizeof(pseudo), ~0);
340         checksum = inet_checksum(icmp, ntohl(pseudo.length), checksum);
341
342         icmp->icmp6_cksum = checksum;
343         
344         packet->len = 14 + sizeof(*hdr) + ntohl(pseudo.length);
345         
346         write_packet(packet);
347 }
348
349 static node_t *route_ipv6(vpn_packet_t *packet)
350 {
351         subnet_t *subnet;
352
353         cp();
354
355         subnet = lookup_subnet_ipv6((ipv6_t *) & packet->data[38]);
356
357         if(!subnet) {
358                 ifdebug(TRAFFIC) logger(LOG_WARNING, _("Cannot route packet: unknown IPv6 destination address %hx:%hx:%hx:%hx:%hx:%hx:%hx:%hx"),
359                                    ntohs(*(uint16_t *) & packet->data[38]),
360                                    ntohs(*(uint16_t *) & packet->data[40]),
361                                    ntohs(*(uint16_t *) & packet->data[42]),
362                                    ntohs(*(uint16_t *) & packet->data[44]),
363                                    ntohs(*(uint16_t *) & packet->data[46]),
364                                    ntohs(*(uint16_t *) & packet->data[48]),
365                                    ntohs(*(uint16_t *) & packet->data[50]),
366                                    ntohs(*(uint16_t *) & packet->data[52]));
367                 route_ipv6_unreachable(packet, ICMP6_DST_UNREACH_ADDR);
368
369                 return NULL;
370         }
371
372         if(!subnet->owner->status.reachable)
373                 route_ipv6_unreachable(packet, ICMP6_DST_UNREACH_NOROUTE);
374         
375         return subnet->owner;
376 }
377
378 /* RFC 2461 */
379
380 static void route_neighborsol(vpn_packet_t *packet)
381 {
382         struct ip6_hdr *hdr;
383         struct nd_neighbor_solicit *ns;
384         struct nd_opt_hdr *opt;
385         subnet_t *subnet;
386         uint16_t checksum;
387
388         struct {
389                 struct in6_addr ip6_src;        /* source address */
390                 struct in6_addr ip6_dst;        /* destination address */
391                 uint32_t length;
392                 uint32_t next;
393         } pseudo;
394
395         cp();
396
397         hdr = (struct ip6_hdr *)(packet->data + 14);
398         ns = (struct nd_neighbor_solicit *)(packet->data + 14 + sizeof(*hdr));
399         opt = (struct nd_opt_hdr *)(packet->data + 14 + sizeof(*hdr) + sizeof(*ns));
400
401         /* First, snatch the source address from the neighbor solicitation packet */
402
403         if(overwrite_mac)
404                 memcpy(mymac.x, packet->data + 6, 6);
405
406         /* Check if this is a valid neighbor solicitation request */
407
408         if(ns->nd_ns_hdr.icmp6_type != ND_NEIGHBOR_SOLICIT ||
409            opt->nd_opt_type != ND_OPT_SOURCE_LINKADDR) {
410                 ifdebug(TRAFFIC) logger(LOG_WARNING, _("Cannot route packet: received unknown type neighbor solicitation request"));
411                 return;
412         }
413
414         /* Create pseudo header */
415
416         memcpy(&pseudo.ip6_src, &hdr->ip6_src, 16);
417         memcpy(&pseudo.ip6_dst, &hdr->ip6_dst, 16);
418         pseudo.length = htonl(sizeof(*ns) + sizeof(*opt) + 6);
419         pseudo.next = htonl(IPPROTO_ICMPV6);
420
421         /* Generate checksum */
422
423         checksum = inet_checksum(&pseudo, sizeof(pseudo), ~0);
424         checksum = inet_checksum(ns, sizeof(*ns) + 8, checksum);
425
426         if(checksum) {
427                 ifdebug(TRAFFIC) logger(LOG_WARNING, _("Cannot route packet: checksum error for neighbor solicitation request"));
428                 return;
429         }
430
431         /* Check if the IPv6 address exists on the VPN */
432
433         subnet = lookup_subnet_ipv6((ipv6_t *) & ns->nd_ns_target);
434
435         if(!subnet) {
436                 ifdebug(TRAFFIC) logger(LOG_WARNING, _("Cannot route packet: neighbor solicitation request for unknown address %hx:%hx:%hx:%hx:%hx:%hx:%hx:%hx"),
437                                    ntohs(((uint16_t *) & ns->nd_ns_target)[0]),
438                                    ntohs(((uint16_t *) & ns->nd_ns_target)[1]),
439                                    ntohs(((uint16_t *) & ns->nd_ns_target)[2]),
440                                    ntohs(((uint16_t *) & ns->nd_ns_target)[3]),
441                                    ntohs(((uint16_t *) & ns->nd_ns_target)[4]),
442                                    ntohs(((uint16_t *) & ns->nd_ns_target)[5]),
443                                    ntohs(((uint16_t *) & ns->nd_ns_target)[6]),
444                                    ntohs(((uint16_t *) & ns->nd_ns_target)[7]));
445
446                 return;
447         }
448
449         /* Check if it is for our own subnet */
450
451         if(subnet->owner == myself)
452                 return;                                 /* silently ignore */
453
454         /* Create neighbor advertation reply */
455
456         memcpy(packet->data, packet->data + ETHER_ADDR_LEN, ETHER_ADDR_LEN);    /* copy destination address */
457         packet->data[ETHER_ADDR_LEN * 2 - 1] ^= 0xFF;   /* mangle source address so it looks like it's not from us */
458
459         memcpy(&hdr->ip6_dst, &hdr->ip6_src, 16);       /* swap destination and source protocol address */
460         memcpy(&hdr->ip6_src, &ns->nd_ns_target, 16);   /* ... */
461
462         memcpy((char *) opt + sizeof(*opt), packet->data + ETHER_ADDR_LEN, 6);  /* add fake source hard addr */
463
464         ns->nd_ns_hdr.icmp6_cksum = 0;
465         ns->nd_ns_hdr.icmp6_type = ND_NEIGHBOR_ADVERT;
466         ns->nd_ns_hdr.icmp6_dataun.icmp6_un_data8[0] = 0x40;    /* Set solicited flag */
467         ns->nd_ns_hdr.icmp6_dataun.icmp6_un_data8[1] =
468                 ns->nd_ns_hdr.icmp6_dataun.icmp6_un_data8[2] =
469                 ns->nd_ns_hdr.icmp6_dataun.icmp6_un_data8[3] = 0;
470         opt->nd_opt_type = ND_OPT_TARGET_LINKADDR;
471
472         /* Create pseudo header */
473
474         memcpy(&pseudo.ip6_src, &hdr->ip6_src, 16);
475         memcpy(&pseudo.ip6_dst, &hdr->ip6_dst, 16);
476         pseudo.length = htonl(sizeof(*ns) + sizeof(*opt) + 6);
477         pseudo.next = htonl(IPPROTO_ICMPV6);
478
479         /* Generate checksum */
480
481         checksum = inet_checksum(&pseudo, sizeof(pseudo), ~0);
482         checksum = inet_checksum(ns, sizeof(*ns) + 8, checksum);
483
484         ns->nd_ns_hdr.icmp6_cksum = checksum;
485
486         write_packet(packet);
487 }
488
489 /* RFC 826 */
490
491 static void route_arp(vpn_packet_t *packet)
492 {
493         struct ether_arp *arp;
494         subnet_t *subnet;
495         uint8_t ipbuf[4];
496
497         cp();
498
499         /* First, snatch the source address from the ARP packet */
500
501         if(overwrite_mac)
502                 memcpy(mymac.x, packet->data + 6, 6);
503
504         /* This routine generates replies to ARP requests.
505            You don't need to set NOARP flag on the interface anymore (which is broken on FreeBSD).
506            Most of the code here is taken from choparp.c by Takamichi Tateoka (tree@mma.club.uec.ac.jp)
507          */
508
509         arp = (struct ether_arp *)(packet->data + 14);
510
511         /* Check if this is a valid ARP request */
512
513         if(ntohs(arp->arp_hrd) != ARPHRD_ETHER || ntohs(arp->arp_pro) != ETHERTYPE_IP ||
514            arp->arp_hln != ETHER_ADDR_LEN || arp->arp_pln != 4 || ntohs(arp->arp_op) != ARPOP_REQUEST) {
515                 ifdebug(TRAFFIC) logger(LOG_WARNING, _("Cannot route packet: received unknown type ARP request"));
516                 return;
517         }
518
519         /* Check if the IPv4 address exists on the VPN */
520
521         subnet = lookup_subnet_ipv4((ipv4_t *) arp->arp_tpa);
522
523         if(!subnet) {
524                 ifdebug(TRAFFIC) logger(LOG_WARNING, _("Cannot route packet: ARP request for unknown address %d.%d.%d.%d"),
525                                    arp->arp_tpa[0], arp->arp_tpa[1], arp->arp_tpa[2],
526                                    arp->arp_tpa[3]);
527                 return;
528         }
529
530         /* Check if it is for our own subnet */
531
532         if(subnet->owner == myself)
533                 return;                                 /* silently ignore */
534
535         memcpy(packet->data, packet->data + ETHER_ADDR_LEN, ETHER_ADDR_LEN);    /* copy destination address */
536         packet->data[ETHER_ADDR_LEN * 2 - 1] ^= 0xFF;   /* mangle source address so it looks like it's not from us */
537
538         memcpy(ipbuf, arp->arp_tpa, 4); /* save protocol addr */
539         memcpy(arp->arp_tpa, arp->arp_spa, 4);  /* swap destination and source protocol address */
540         memcpy(arp->arp_spa, ipbuf, 4); /* ... */
541
542         memcpy(arp->arp_tha, arp->arp_sha, 10); /* set target hard/proto addr */
543         memcpy(arp->arp_sha, packet->data + ETHER_ADDR_LEN, ETHER_ADDR_LEN);    /* add fake source hard addr */
544         arp->arp_op = htons(ARPOP_REPLY);
545
546         write_packet(packet);
547 }
548
549 void route_outgoing(vpn_packet_t *packet)
550 {
551         uint16_t type;
552         node_t *n = NULL;
553
554         cp();
555
556         /* FIXME: multicast? */
557
558         switch (routing_mode) {
559                 case RMODE_ROUTER:
560                         type = ntohs(*((uint16_t *)(&packet->data[12])));
561                         switch (type) {
562                                 case 0x0800:
563                                         n = route_ipv4(packet);
564                                         break;
565
566                                 case 0x86DD:
567                                         if(packet->data[20] == IPPROTO_ICMPV6 && packet->data[54] == ND_NEIGHBOR_SOLICIT) {
568                                                 route_neighborsol(packet);
569                                                 return;
570                                         }
571                                         n = route_ipv6(packet);
572                                         break;
573
574                                 case 0x0806:
575                                         route_arp(packet);
576                                         return;
577
578                                 default:
579                                         ifdebug(TRAFFIC) logger(LOG_WARNING, _("Cannot route packet: unknown type %hx"), type);
580                                         return;
581                         }
582                         if(n)
583                                 send_packet(n, packet);
584                         break;
585
586                 case RMODE_SWITCH:
587                         n = route_mac(packet);
588                         if(n)
589                                 send_packet(n, packet);
590                         else
591                                 broadcast_packet(myself, packet);
592                         break;
593
594                 case RMODE_HUB:
595                         broadcast_packet(myself, packet);
596                         break;
597         }
598 }
599
600 void route_incoming(node_t *source, vpn_packet_t *packet)
601 {
602         switch (routing_mode) {
603                 case RMODE_ROUTER:
604                         {
605                                 node_t *n = NULL;
606                                 uint16_t type;
607
608                                 type = ntohs(*((uint16_t *)(&packet->data[12])));
609                                 switch (type) {
610                                         case 0x0800:
611                                                 n = route_ipv4(packet);
612                                                 break;
613
614                                         case 0x86DD:
615                                                 n = route_ipv6(packet);
616                                                 break;
617
618                                         default:
619                                                 n = myself;
620                                                 break;
621                                 }
622
623                                 if(n) {
624                                         if(n == myself) {
625                                                 if(overwrite_mac)
626                                                         memcpy(packet->data, mymac.x, 6);
627                                                 write_packet(packet);
628                                         } else
629                                                 send_packet(n, packet);
630                                 }
631                         }
632                         break;
633
634                 case RMODE_SWITCH:
635                         {
636                                 subnet_t *subnet;
637
638                                 subnet = lookup_subnet_mac((mac_t *)(&packet->data[0]));
639
640                                 if(subnet) {
641                                         if(subnet->owner == myself)
642                                                 write_packet(packet);
643                                         else
644                                                 send_packet(subnet->owner, packet);
645                                 } else {
646                                         broadcast_packet(source, packet);
647                                         write_packet(packet);
648                                 }
649                         }
650                         break;
651
652                 case RMODE_HUB:
653                         broadcast_packet(source, packet);       /* Spread it on */
654                         write_packet(packet);
655                         break;
656         }
657 }