ViewVC Help
View File | Revision Log | Show Annotations | Download File
/cvs/gvpe/src/vpn_dns.C
(Generate patch)

Comparing gvpe/src/vpn_dns.C (file contents):
Revision 1.6 by pcg, Thu Mar 3 08:38:32 2005 UTC vs.
Revision 1.8 by pcg, Fri Mar 4 03:43:09 2005 UTC

1/* 1/*
2 vpn_dns.C -- handle the dns tunnel part of the protocol. 2 vpn_dns.C -- handle the dns tunnel part of the protocol.
3 Copyright (C) 2003-2004 Marc Lehmann <pcg@goof.com> 3 Copyright (C) 2003-2005 Marc Lehmann <gvpe@schmorp.de>
4 4
5 This file is part of GVPE.
6
5 This program is free software; you can redistribute it and/or modify 7 GVPE is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by 8 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation; either version 2 of the License, or 9 the Free Software Foundation; either version 2 of the License, or
8 (at your option) any later version. 10 (at your option) any later version.
9 11
10 This program is distributed in the hope that it will be useful, 12 This program is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of 13 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU General Public License for more details. 15 GNU General Public License for more details.
14 16
15 You should have received a copy of the GNU General Public License 17 You should have received a copy of the GNU General Public License
16 along with this program; if not, write to the Free Software 18 along with gvpe; if not, write to the Free Software
17 Foundation, Inc. 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA 19 Foundation, Inc. 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
18*/ 20*/
19 21
20#include "config.h" 22#include "config.h"
21 23
35#include <unistd.h> 37#include <unistd.h>
36#include <fcntl.h> 38#include <fcntl.h>
37 39
38#include <map> 40#include <map>
39 41
42#include <gmp.h>
43
40#include "netcompat.h" 44#include "netcompat.h"
41 45
42#include "vpn.h" 46#include "vpn.h"
43 47
44#define MIN_RETRY 1. 48#define MIN_RETRY 1.
45#define MAX_RETRY 60. 49#define MAX_RETRY 60.
46 50
47#define MAX_OUTSTANDING 40 // max. outstanding requests 51#define MAX_OUTSTANDING 400 // max. outstanding requests
48#define MAX_WINDOW 100 // max. for MAX_OUTSTANDING 52#define MAX_WINDOW 1000 // max. for MAX_OUTSTANDING
49#define MAX_RATE 1000 // requests/s 53#define MAX_RATE 10000 // requests/s
50#define MAX_BACKLOG (10*1024) // size of protocol backlog, must be > MAXSIZE 54#define MAX_BACKLOG (10*1024) // size of protocol backlog, must be > MAXSIZE
51 55
52#define MAX_DOMAIN_SIZE 220 // 255 is legal limit, but bind doesn't compress well 56#define MAX_DOMAIN_SIZE 220 // 255 is legal limit, but bind doesn't compress well
53// 240 leaves about 4 bytes of server reply data 57// 240 leaves about 4 bytes of server reply data
54// every two request byte sless give room for one reply byte 58// every two request byte sless give room for one reply byte
55 59
56// seqno has 12 bits, but the lower bit is always left as zero 60// seqno has 12 bits (3 bytes a 4 bits in the header)
57// as bind caches ttl=0 records and we have to generate
58// sequence numbers that always differ case-insensitively
59#define SEQNO_MASK 0x07ff 61#define SEQNO_MASK 0x7fff
60 62#define SEQNO_EQ(a,b) ( 0 == ( ((a) ^ (b)) & SEQNO_MASK) )
61/*
62
63protocol, in shorthand :)
64
65client -> server <req> ANY?
66server -> client <req> TXT <rep>
67
68<req> is dns64-encoded <client-id:12><recv-seqno:10>[<send-seqno:10><data>]
69<rep> is dns64-encoded <0:12><recv-seqno:10>[<send-seqno:10><data>]
70
71if <client-id> is zero, the connection will be configured:
72
73<0:12><0:4>client-id:12><default-ttl:8><max-size:16><flags:16>
74
75*/
76 63
77#define MAX_LBL_SIZE 63 64#define MAX_LBL_SIZE 63
78#define MAX_PKT_SIZE 512 65#define MAX_PKT_SIZE 512
79 66
80#define RR_TYPE_TXT 16 67#define RR_TYPE_TXT 16
81#define RR_TYPE_ANY 255 68#define RR_TYPE_ANY 255
82#define RR_CLASS_IN 1 69#define RR_CLASS_IN 1
83 70
84// the "_" is not valid but widely accepted (all octets should be supported, but let's be conservative) 71// works for cmaps up to 255 (not 256!)
85struct dns64 72struct charmap
86{ 73{
87 static const char encode_chars[64 + 1]; 74 enum { INVALID = (u8)255 };
88 static s8 decode_chars[256];
89 75
90 static int encode_len (int bytes) { return (bytes * 8 + 5) / 6; } 76 char encode [256]; // index => char
91 static int decode_len (int bytes) { return (bytes * 6) / 8; } 77 u8 decode [256]; // char => index
78 unsigned int size;
79
80 charmap (const char *cmap);
81};
82
83charmap::charmap (const char *cmap)
84{
85 char *enc = encode;
86 u8 *dec = decode;
87
88 memset (enc, (char) 0, 256);
89 memset (dec, (char)INVALID, 256);
90
91 for (size = 0; cmap [size]; size++)
92 {
93 enc [size] = cmap [size];
94 dec [(u8)enc [size]] = size;
95 }
96
97 assert (size < 256);
98}
99
100#define MAX_DEC_LEN 500
101#define MAX_ENC_LEN (MAX_DEC_LEN * 2)
102#define MAX_LIMBS ((MAX_DEC_LEN * 8 + GMP_NUMB_BITS - 1) / GMP_NUMB_BITS)
103
104// ugly. minimum base is 16(!)
105struct basecoder
106{
107 charmap cmap;
108 unsigned int enc_len [MAX_DEC_LEN];
109 unsigned int dec_len [MAX_ENC_LEN];
110
111 unsigned int encode_len (unsigned int len);
112 unsigned int decode_len (unsigned int len);
113
92 static int encode (char *dst, u8 *src, int len); 114 unsigned int encode (char *dst, u8 *src, unsigned int len);
93 static int decode (u8 *dst, char *src, int len); 115 unsigned int decode (u8 *dst, char *src, unsigned int len);
94 116
95 dns64 (); 117 basecoder (const char *cmap);
96} dns64; 118};
119
120basecoder::basecoder (const char *cmap)
121: cmap (cmap)
122{
123 for (unsigned int len = 0; len < MAX_DEC_LEN; ++len)
124 {
125 u8 src [MAX_DEC_LEN];
126 u8 dst [MAX_ENC_LEN];
127
128 memset (src, 255, len);
129
130 mp_limb_t m [MAX_LIMBS];
131 mp_size_t n;
132
133 n = mpn_set_str (m, src, len, 256);
134 n = mpn_get_str (dst, this->cmap.size, m, n);
135
136 for (int i = 0; !dst [i]; ++i)
137 n--;
138
139 enc_len [len] = n;
140 dec_len [n] = len;
141 }
142}
143
144unsigned int basecoder::encode_len (unsigned int len)
145{
146 return enc_len [len];
147}
148
149unsigned int basecoder::decode_len (unsigned int len)
150{
151 while (len && !dec_len [len])
152 --len;
153
154 return dec_len [len];
155}
156
157unsigned int basecoder::encode (char *dst, u8 *src, unsigned int len)
158{
159 if (!len)
160 return 0;
161
162 int elen = encode_len (len);
163
164 mp_limb_t m [MAX_LIMBS];
165 mp_size_t n;
166
167 u8 dst_ [MAX_ENC_LEN];
168
169 n = mpn_set_str (m, src, len, 256);
170 n = mpn_get_str (dst_, cmap.size, m, n);
171
172 int plen = elen; // for padding
173
174 while (n < plen)
175 {
176 *dst++ = cmap.encode [0];
177 plen--;
178 }
179
180 for (unsigned int i = n - plen; i < n; ++i)
181 *dst++ = cmap.encode [dst_ [i]];
182
183 return elen;
184}
185
186unsigned int basecoder::decode (u8 *dst, char *src, unsigned int len)
187{
188 if (!len)
189 return 0;
190
191 u8 src_ [MAX_ENC_LEN];
192 unsigned int elen = 0;
193
194 while (len--)
195 {
196 u8 val = cmap.decode [(u8)*src++];
197
198 if (val != charmap::INVALID)
199 src_ [elen++] = val;
200 }
201
202 int dlen = decode_len (elen);
203
204 mp_limb_t m [MAX_LIMBS];
205 mp_size_t n;
206
207 u8 dst_ [MAX_DEC_LEN];
208
209 n = mpn_set_str (m, src_, elen, cmap.size);
210 n = mpn_get_str (dst_, 256, m, n);
211
212 if (n < dlen)
213 {
214 memset (dst, 0, dlen - n);
215 memcpy (dst + dlen - n, dst_, n);
216 }
217 else
218 memcpy (dst, dst_ + n - dlen, dlen);
219
220 return dlen;
221}
222
223#if 0
224struct test { test (); } test;
225
226test::test ()
227{
228 basecoder cdc ("0123456789abcdefghijklmnopqrstuvwxyz");
229
230 u8 in[] = "0123456789abcdefghijklmnopqrstuvwxyz";
231 static char enc[200];
232 static u8 dec[200];
233
234 for (int i = 1; i < 20; i++)
235 {
236 int elen = cdc.encode (enc, in, i);
237 int dlen = cdc.decode (dec, enc, elen);
238
239 printf ("%d>%d>%d (%s>%s)\n", i, elen, dlen, enc, dec);
240 }
241 abort ();
242}
243#endif
97 244
98// the following sequence has been crafted to 245// the following sequence has been crafted to
99// a) look somewhat random 246// a) look somewhat random
100// b) the even (and odd) indices never share the same character as upper/lowercase 247// b) the even (and odd) indices never share the same character as upper/lowercase
248// the "_" is not valid but widely accepted (all octets should be supported, but let's be conservative)
249// the other sequences are obviously derived
250//static basecoder cdc63 ("_dDpPhHzZrR06QqMmjJkKBb34TtSsvVlL81xXaAeEFf92WwGgYyoO57UucCNniI");
101const char dns64::encode_chars[64 + 1] = "_-dDpPhHzZrR06QqMmjJkKBb34TtSsvVlL81xXaAeEFf92WwGgYyoO57UucCNniI"; 251static basecoder cdc62 ("dDpPhHzZrR06QqMmjJkKBb34TtSsvVlL81xXaAeEFf92WwGgYyoO57UucCNniI");
102s8 dns64::decode_chars[256]; 252//static basecoder cdc36 ("dphzr06qmjkb34tsvl81xaef92wgyo57ucni"); // unused as of yet
253static basecoder cdc26 ("dPhZrQmJkBtSvLxAeFwGyO");
103 254
104dns64::dns64 () 255/////////////////////////////////////////////////////////////////////////////
105{
106 for (int i = 0; i < 64; i++)
107 decode_chars [encode_chars [i]] = i + 1;
108}
109 256
110int dns64::encode (char *dst, u8 *src, int len) 257#define HDRSIZE 6
111{
112 // slow, but easy to debug
113 char *beg = dst;
114 unsigned int accum, bits = 0;
115 258
116 while (len--) 259inline void encode_header (char *data, int clientid, int seqno)
117 {
118 accum <<= 8;
119 accum |= *src++;
120 bits += 8;
121
122 while (bits >= 6)
123 {
124 *dst++ = encode_chars [(accum >> (bits - 6)) & 63];
125 bits -= 6;
126 }
127 }
128
129 if (bits)
130 *dst++ = encode_chars [(accum << (6 - bits)) & 63];
131
132 return dst - beg;
133}
134
135int dns64::decode (u8 *dst, char *src, int len)
136{ 260{
137 // slow, but easy to debug 261 u8 hdr[3] = { clientid, seqno >> 8, seqno };
138 u8 *beg = dst;
139 unsigned int accum, bits = 0;
140 262
141 while (len--) 263 assert (clientid < 256);
142 {
143 s8 chr = decode_chars [(u8)*src++];
144 264
145 if (!chr) 265 cdc26.encode (data, hdr, 3);
146 continue; 266}
147 267
148 accum <<= 6; 268inline void decode_header (char *data, int &clientid, int &seqno)
149 accum |= chr - 1; 269{
150 bits += 6; 270 u8 hdr[3];
151 271
152 while (bits >= 8) 272 cdc26.decode (hdr, data, HDRSIZE);
153 {
154 *dst++ = accum >> (bits - 8);
155 bits -= 8;
156 }
157 }
158 273
159 return dst - beg; 274 printf ("DEC %02x %02x %02x %02x\n", hdr[0], hdr[1], hdr[2], hdr[3]);
275
276 clientid = hdr[0];
277 seqno = (hdr[1] << 8) | hdr[2];
160} 278}
161 279
162///////////////////////////////////////////////////////////////////////////// 280/////////////////////////////////////////////////////////////////////////////
163 281
164struct byte_stream 282struct byte_stream
353 471
354 pkt->flags = htons (DEFAULT_CLIENT_FLAGS); 472 pkt->flags = htons (DEFAULT_CLIENT_FLAGS);
355 pkt->qdcount = htons (1); 473 pkt->qdcount = htons (1);
356 474
357 int offs = 6*2; 475 int offs = 6*2;
358 int dlen = MAX_DOMAIN_SIZE - strlen (THISNODE->domain) - 2; 476 int dlen = MAX_DOMAIN_SIZE - (strlen (THISNODE->domain) + 2);
359 // MAX_DOMAIN_SIZE is technically 255, but bind doesn't compress responses well, 477 // MAX_DOMAIN_SIZE is technically 255, but bind doesn't compress responses well,
360 // so we need to have space for 2*MAX_DOMAIN_SIZE + header + extra 478 // so we need to have space for 2*MAX_DOMAIN_SIZE + header + extra
361 479
362 u8 data[256]; //TODO 480 char enc[256], *encp = enc;
481 encode_header (enc, THISNODE->id, seqno);
363 482
364 data[0] = THISNODE->id; //TODO
365 data[1] = seqno >> 7; //TODO
366 data[2] = seqno << 1; //TODO
367
368 int datalen = dns64::decode_len (dlen - (dlen + MAX_LBL_SIZE - 1) / MAX_LBL_SIZE) - 3; 483 int datalen = cdc62.decode_len (dlen - (dlen + MAX_LBL_SIZE - 1) / MAX_LBL_SIZE - HDRSIZE);
369 484
370 if (datalen > stream->size ()) 485 if (datalen > stream->size ())
371 datalen = stream->size (); 486 datalen = stream->size ();
372 487
373 char enc[256], *encp = enc; 488 int enclen = cdc62.encode (enc + HDRSIZE, stream->begin (), datalen) + HDRSIZE;
489
490 printf ("cdc62.encode %d->%d:%02x %02x %02x %02x\n", datalen, enclen,
491 stream->begin ()[0],
492 stream->begin ()[1],
493 stream->begin ()[2],
494 stream->begin ()[3]);
374 495
375 memcpy (data + 3, stream->begin (), datalen);
376 int enclen = dns64::encode (enc, data, datalen + 3);
377 stream->remove (datalen); 496 stream->remove (datalen);
378 497
379 while (enclen) 498 while (enclen)
380 { 499 {
381 int lbllen = enclen < MAX_LBL_SIZE ? enclen : MAX_LBL_SIZE; 500 int lbllen = enclen < MAX_LBL_SIZE ? enclen : MAX_LBL_SIZE;
453 572
454void connection::dnsv4_receive_rep (struct dns_rcv *r) 573void connection::dnsv4_receive_rep (struct dns_rcv *r)
455{ 574{
456 dns_rcvpq.push_back (r); 575 dns_rcvpq.push_back (r);
457 576
577 printf ("%d got inketc %d (%02x %02x %02x %02x)\n", THISNODE->id, r->seqno
578 ,r->data[0]
579 ,r->data[1]
580 ,r->data[2]
581 ,r->data[3]
582 );
458 redo: 583 redo:
459 584
585 // find next packet
460 for (vector<dns_rcv *>::iterator i = dns_rcvpq.begin (); 586 for (vector<dns_rcv *>::iterator i = dns_rcvpq.end (); i-- != dns_rcvpq.begin (); )
461 i != dns_rcvpq.end ();
462 ++i)
463 if (dns_rcvseq == (*i)->seqno) 587 if (SEQNO_EQ (dns_rcvseq, (*i)->seqno))
464 { 588 {
589 // enter the packet into our input stream
465 dns_rcv *r = *i; 590 r = *i;
591
592 printf ("%d checking for older packet %d\n", THISNODE->id, dns_rcvseq);
593 // remove the oldest packet, look forward, as it's oldest first
594 for (vector<dns_rcv *>::iterator j = dns_rcvpq.begin (); j != dns_rcvpq.end (); ++j)
595 if (SEQNO_EQ ((*j)->seqno, dns_rcvseq - MAX_WINDOW))
596 {
597 printf ("%d removing %d\n", THISNODE->id, (*j)->seqno);
598 delete *j;
599 dns_rcvpq.erase (j);
600 break;
601 }
466 602
467 dns_rcvseq = (dns_rcvseq + 1) & SEQNO_MASK; 603 dns_rcvseq = (dns_rcvseq + 1) & SEQNO_MASK;
468 604
469 if (!dns_snddq && !dns_rcvdq) 605 if (!dns_snddq && !dns_rcvdq)
470 { 606 {
482 sockinfo si; 618 sockinfo si;
483 si.host = 0; si.port = 0; si.prot = PROT_DNSv4; 619 si.host = 0; si.port = 0; si.prot = PROT_DNSv4;
484 620
485 vpn->recv_vpn_packet (pkt, si); 621 vpn->recv_vpn_packet (pkt, si);
486 } 622 }
487 } 623
488 else if ((u32)(*i)->seqno - (u32)dns_rcvseq + MAX_WINDOW > MAX_WINDOW * 2) 624 // check for further packets
489 {
490 //D
491 //abort();
492 printf ("%d erasing %d (%d)\n", THISNODE->id, (u32)(*i)->seqno, dns_rcvseq);
493 dns_rcvpq.erase (i);
494 goto redo; 625 goto redo;
495 } 626 }
496} 627}
497 628
498dns_packet * 629dns_packet *
523 654
524 int dlen = strlen (THISNODE->domain); 655 int dlen = strlen (THISNODE->domain);
525 656
526 if (qclass == RR_CLASS_IN 657 if (qclass == RR_CLASS_IN
527 && (qtype == RR_TYPE_ANY || qtype == RR_TYPE_TXT) 658 && (qtype == RR_TYPE_ANY || qtype == RR_TYPE_TXT)
528 && qlen > dlen + 1 659 && qlen > dlen + 1 + HDRSIZE
529 && !memcmp (qname + qlen - dlen - 1, THISNODE->domain, dlen)) 660 && !memcmp (qname + qlen - dlen - 1, THISNODE->domain, dlen))
530 { 661 {
531 // correct class, domain: parse 662 // correct class, domain: parse
663 int client, seqno;
664 decode_header (qname, client, seqno);
665
532 u8 data[MAXSIZE]; 666 u8 data[MAXSIZE];
533 int datalen = dns64::decode (data, qname, qlen - dlen - 1); 667 int datalen = cdc62.decode (data, qname + HDRSIZE, qlen - (dlen + 1 + HDRSIZE));
534 668
535 int client = data[0]; 669 printf ("cdc62.decode %d(%d): %02x %02x %02x %02x\n",
536 int seqno = ((data[1] << 7) | (data[2] >> 1)) & SEQNO_MASK; 670 qlen - (dlen + 1 + HDRSIZE), datalen
671 ,data[0]
672 ,data[1]
673 ,data[2]
674 ,data[3]);
675
676 printf ("SRV got %d <%.*s>\n", seqno, qlen, qname + HDRSIZE);//D
677 printf ("SRV got %d <%.*s>\n", seqno, qlen - (dlen + 1 + HDRSIZE), qname + HDRSIZE);//D
537 678
538 if (0 < client && client <= conns.size ()) 679 if (0 < client && client <= conns.size ())
539 { 680 {
540 connection *c = conns [client - 1]; 681 connection *c = conns [client - 1];
541 682
542 redo:
543
544 for (vector<dns_rcv *>::iterator i = c->dns_rcvpq.begin (); 683 for (vector<dns_rcv *>::iterator i = c->dns_rcvpq.end (); i-- != c->dns_rcvpq.begin (); )
545 i != c->dns_rcvpq.end ();
546 ++i)
547 if ((*i)->seqno == seqno) 684 if (SEQNO_EQ ((*i)->seqno, seqno))
548 { 685 {
549 // already seen that request: simply reply with the cached reply 686 // already seen that request: simply reply with the cached reply
550 dns_rcv *r = *i; 687 dns_rcv *r = *i;
551 688
552 printf ("DUPLICATE %d\n", htons (r->pkt->id));//D 689 printf ("DUPLICATE %d\n", htons (r->pkt->id));//D
553 690
554 offs = r->pkt->len;
555 memcpy (pkt->at (0), r->pkt->at (0), offs); 691 memcpy (pkt->at (0), r->pkt->at (0), offs = r->pkt->len);
692 pkt->id = r->pkt->id;
556 goto duplicate_request; 693 goto duplicate_request;
557 } 694 }
558 695
559 // new packet, queue 696 // new packet, queue
560 dns_rcv *rcv = new dns_rcv (seqno, data + 3, datalen - 3); 697 dns_rcv *rcv = new dns_rcv (seqno, data, datalen);
561 c->dnsv4_receive_rep (rcv); 698 c->dnsv4_receive_rep (rcv);
562 699
563 // now generate reply 700 // now generate reply
564 pkt->ancount = htons (1); // one answer RR 701 pkt->ancount = htons (1); // one answer RR
565 pkt->flags = htons (DEFAULT_SERVER_FLAGS | FLAG_RCODE_OK); 702 pkt->flags = htons (DEFAULT_SERVER_FLAGS | FLAG_RCODE_OK);
654 offs += 4; // skip qtype, qclass 791 offs += 4; // skip qtype, qclass
655 } 792 }
656 793
657 while (pkt->ancount-- && offs < MAXSIZE - 10) 794 while (pkt->ancount-- && offs < MAXSIZE - 10)
658 { 795 {
796 int qlen = //D
659 pkt->decode_label ((char *)qname, MAXSIZE - offs, offs); 797 pkt->decode_label ((char *)qname, MAXSIZE - offs, offs);
798
799 printf ("got reply to <%.*s>\n", qlen, qname);//D
660 800
661 u16 qtype = (*pkt) [offs++] << 8; qtype |= (*pkt) [offs++]; 801 u16 qtype = (*pkt) [offs++] << 8; qtype |= (*pkt) [offs++];
662 u16 qclass = (*pkt) [offs++] << 8; qclass |= (*pkt) [offs++]; 802 u16 qclass = (*pkt) [offs++] << 8; qclass |= (*pkt) [offs++];
663 u32 ttl = (*pkt) [offs++] << 24; 803 u32 ttl = (*pkt) [offs++] << 24;
664 ttl |= (*pkt) [offs++] << 16; 804 ttl |= (*pkt) [offs++] << 16;
769 if (!send) 909 if (!send)
770 { 910 {
771 send = r; 911 send = r;
772 912
773 if (r->retry)//D 913 if (r->retry)//D
774 printf ("req %d, retry %d\n", r->pkt->id, r->retry); 914 printf ("req %d:%d, retry %d\n", r->seqno, r->pkt->id, r->retry);
775 r->retry++; 915 r->retry++;
776 r->next = NOW + r->retry; 916 r->next = NOW + r->retry;
777 } 917 }
778 } 918 }
779 919

Diff Legend

Removed lines
+ Added lines
< Changed lines
> Changed lines