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