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