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