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