]> Sergey Matveev's repositories - dht-bootstrap.git/blob - dht-bootstrap.c
Remove unused variables.
[dht-bootstrap.git] / dht-bootstrap.c
1 /*
2 Copyright (c) 2009-2011 by Juliusz Chroboczek
3
4 Permission is hereby granted, free of charge, to any person obtaining a copy
5 of this software and associated documentation files (the "Software"), to deal
6 in the Software without restriction, including without limitation the rights
7 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8 copies of the Software, and to permit persons to whom the Software is
9 furnished to do so, subject to the following conditions:
10
11 The above copyright notice and this permission notice shall be included in
12 all copies or substantial portions of the Software.
13
14 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL THE
17 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
20 THE SOFTWARE.
21 */
22
23 /* For memmem. */
24 #define _GNU_SOURCE
25
26 #include <stdio.h>
27 #include <stdlib.h>
28 #include <errno.h>
29 #include <string.h>
30 #include <stdarg.h>
31 #include <unistd.h>
32 #include <time.h>
33 #include <fcntl.h>
34 #include <sys/time.h>
35 #include <arpa/inet.h>
36 #include <sys/types.h>
37 #include <sys/socket.h>
38 #include <netinet/in.h>
39 #include <sys/types.h>
40 #include <sys/socket.h>
41 #include <netdb.h>
42
43 #ifndef HAVE_MEMMEM
44 #ifdef __GLIBC__
45 #define HAVE_MEMMEM
46 #endif
47 #endif
48
49 #ifndef MSG_CONFIRM
50 #define MSG_CONFIRM 0
51 #endif
52
53 /* We set sin_family to 0 to mark unused slots. */
54 #if AF_INET == 0 || AF_INET6 == 0
55 #error You lose
56 #endif
57
58 #if defined(__STDC_VERSION__) && __STDC_VERSION__ >= 199901L
59 /* nothing */
60 #elif defined(__GNUC__)
61 #define inline __inline
62 #if  (__GNUC__ >= 3)
63 #define restrict __restrict
64 #else
65 #define restrict /**/
66 #endif
67 #else
68 #define inline /**/
69 #define restrict /**/
70 #endif
71
72 #define MAX(x, y) ((x) >= (y) ? (x) : (y))
73 #define MIN(x, y) ((x) <= (y) ? (x) : (y))
74
75 static int send_ping(struct sockaddr *sa, int salen,
76                      const unsigned char *tid, int tid_len);
77 static int send_pong(struct sockaddr *sa, int salen,
78                      const unsigned char *tid, int tid_len);
79 static int send_find_node(struct sockaddr *sa, int salen,
80                           const unsigned char *tid, int tid_len,
81                           const unsigned char *target, int want, int confirm);
82 static int send_nodes(struct sockaddr *sa, int salen,
83                       const unsigned char *tid, int tid_len,
84                       const unsigned char *nodes, int nodes_len,
85                       const unsigned char *nodes6, int nodes6_len);
86 static int send_random_nodes(struct sockaddr *sa, int salen,
87                              const unsigned char *tid, int tid_len,
88                              const unsigned char *id, int want);
89 static int send_error(struct sockaddr *sa, int salen,
90                       unsigned char *tid, int tid_len,
91                       int code, const char *message);
92
93 #define ERROR 0
94 #define REPLY 1
95 #define PING 2
96 #define FIND_NODE 3
97 #define GET_PEERS 4
98 #define ANNOUNCE_PEER 5
99
100 #define WANT4 1
101 #define WANT6 2
102
103 static int parse_message(const unsigned char *buf, int buflen,
104                          unsigned char *tid_return, int *tid_len,
105                          unsigned char *id_return,
106                          unsigned char *info_hash_return,
107                          unsigned char *target_return,
108                          unsigned short *port_return,
109                          unsigned char *token_return, int *token_len,
110                          unsigned char *nodes_return, int *nodes_len,
111                          unsigned char *nodes6_return, int *nodes6_len,
112                          unsigned char *values_return, int *values_len,
113                          unsigned char *values6_return, int *values6_len,
114                          int *want_return);
115
116 static const unsigned char zeroes[20] = {0};
117 static const unsigned char ones[20] = {
118     0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
119     0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
120     0xFF, 0xFF, 0xFF, 0xFF
121 };
122 static const unsigned char v4prefix[16] = {
123     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0xFF, 0xFF, 0, 0, 0, 0
124 };
125
126 static unsigned char myid[20];
127 static int have_v = 0;
128 static unsigned char my_v[9];
129
130 static int dht_socket = -1;
131 static int dht_socket6 = -1;
132
133 struct node {
134     unsigned char id[160];
135     struct sockaddr_storage ss;
136     socklen_t sslen;
137 };
138     
139 #define CIRCULAR_LIST_SIZE 256
140
141 struct circular_list {
142     int head;
143     int tail;
144     struct node nodes[CIRCULAR_LIST_SIZE];
145 };
146
147 struct circular_list v4_new, v6_new, v4_confirmed, v6_confirmed;
148
149 #define MAX_TOKEN_BUCKET_TOKENS 40
150 static time_t token_bucket_time;
151 static int token_bucket_tokens;
152
153 FILE *dht_debug = NULL;
154
155 #ifdef __GNUC__
156     __attribute__ ((format (printf, 1, 2)))
157 #endif
158 static void
159 debugf(const char *format, ...)
160 {
161     va_list args;
162     va_start(args, format);
163     if(dht_debug)
164         vfprintf(dht_debug, format, args);
165     va_end(args);
166     fflush(dht_debug);
167 }
168
169 static int
170 is_martian(struct sockaddr *sa)
171 {
172     switch(sa->sa_family) {
173     case AF_INET: {
174         struct sockaddr_in *sin = (struct sockaddr_in*)sa;
175         const unsigned char *address = (const unsigned char*)&sin->sin_addr;
176         return sin->sin_port == 0 ||
177             (address[0] == 0) ||
178             (address[0] == 127) ||
179             ((address[0] & 0xE0) == 0xE0);
180     }
181     case AF_INET6: {
182         struct sockaddr_in6 *sin6 = (struct sockaddr_in6*)sa;
183         const unsigned char *address = (const unsigned char*)&sin6->sin6_addr;
184         return sin6->sin6_port == 0 ||
185             (address[0] == 0xFF) ||
186             (address[0] == 0xFE && (address[1] & 0xC0) == 0x80) ||
187             (memcmp(address, zeroes, 15) == 0 &&
188              (address[15] == 0 || address[15] == 1)) ||
189             (memcmp(address, v4prefix, 12) == 0);
190     }
191
192     default:
193         return 0;
194     }
195 }
196
197 /* Forget about the ``XOR-metric''.  An id is just a path from the
198    root of the tree, so bits are numbered from the start. */
199
200 static inline int
201 id_cmp(const unsigned char *restrict id1, const unsigned char *restrict id2)
202 {
203     /* Memcmp is guaranteed to perform an unsigned comparison. */
204     return memcmp(id1, id2, 20);
205 }
206
207 /* Our transaction-ids are 4-bytes long, with the first two bytes identi-
208    fying the kind of request, and the remaining two a sequence number in
209    host order. */
210
211 static void
212 make_tid(unsigned char *tid_return, const char *prefix, unsigned short seqno)
213 {
214     tid_return[0] = prefix[0] & 0xFF;
215     tid_return[1] = prefix[1] & 0xFF;
216     memcpy(tid_return + 2, &seqno, 2);
217 }
218
219 static int
220 tid_match(const unsigned char *tid, const char *prefix,
221           unsigned short *seqno_return)
222 {
223     if(tid[0] == (prefix[0] & 0xFF) && tid[1] == (prefix[1] & 0xFF)) {
224         if(seqno_return)
225             memcpy(seqno_return, tid + 2, 2);
226         return 1;
227     } else
228         return 0;
229 }
230
231 static inline int
232 circular(int from, int to)
233 {
234     int x = to - from;
235     if(x < 0)
236         return x + CIRCULAR_LIST_SIZE;
237     return x;
238 }
239
240 static int
241 list_elements(struct circular_list *list)
242 {
243     return circular(list->head, list->tail);
244 }
245
246 static int
247 list_empty(struct circular_list *list)
248 {
249     return list_elements(list) == 0;
250 }
251
252 static int
253 list_free(struct circular_list *list)
254 {
255     return circular(list->tail + 1, list->head);
256 }
257
258 static int
259 list_pop(struct circular_list *list,
260          struct sockaddr_storage *ss, socklen_t *sslen)
261 {
262     if(list->head == list->tail)
263         return 0;
264
265     memcpy(ss, &list->nodes[list->head].ss, list->nodes[list->head].sslen);
266     *sslen = list->nodes[list->head].sslen;
267     list->head = (list->head + 1) % CIRCULAR_LIST_SIZE;
268     return 1;
269 }
270
271 static int
272 list_random(struct circular_list *list, unsigned char *id,
273             struct sockaddr_storage *ss, socklen_t *sslen)
274 {
275     int n;
276     if(list->head == list->tail)
277         return 0;
278
279     n = random() % (list->tail - list->head);
280     n = (list->head + n) % CIRCULAR_LIST_SIZE;
281
282     if(id)
283         memcpy(id, &list->nodes[n].id, 20);
284     memcpy(ss, &list->nodes[n].ss, list->nodes[n].sslen);
285     *sslen = list->nodes[n].sslen;
286     return 1;
287 }
288
289 /* We just learnt about a node, not necessarily a new one.  Confirm is 1 if
290    the node sent a message, 2 if it sent us a reply. */
291
292 static int
293 new_node(unsigned char *id, struct sockaddr *sa, socklen_t salen, int confirm)
294 {
295     struct circular_list *list;
296     int i;
297
298     if(sa->sa_family == AF_INET)
299         list = confirm >= 2 ? &v4_confirmed : &v4_new;
300     else if(sa->sa_family == AF_INET6)
301         list = confirm >= 2 ? &v6_confirmed : &v6_new;
302     else
303         abort();
304
305     /* A node that sends us a request is most probably bootstrapping.
306        We want to avoid getting our tables full of very young nodes -- only
307        include such a node if we have plenty of space. */
308
309     if(confirm == 1 && list_free(list) < 32)
310         return 0;
311
312     for(i = list->head; i != list->tail; i = (i + 1) % CIRCULAR_LIST_SIZE) {
313         struct node *n = &list->nodes[i];
314         if(n->sslen == salen && memcmp(&n->ss, sa, salen) == 0)
315             return 0;
316     }
317
318     memcpy(&list->nodes[list->tail].id, id, 160);
319     memcpy(&list->nodes[list->tail].ss, sa, salen);
320     list->nodes[list->tail].sslen = salen;
321     list->tail = (list->tail + 1) % CIRCULAR_LIST_SIZE;
322     if(list->head == list->tail)
323         list->head = (list->head + 1) % CIRCULAR_LIST_SIZE;
324
325     return 1;
326 }
327
328 static int
329 token_bucket(void)
330 {
331     time_t now = time(NULL);
332     if(token_bucket_tokens == 0) {
333         token_bucket_tokens = MIN(MAX_TOKEN_BUCKET_TOKENS,
334                                   4 * (now - token_bucket_time));
335         token_bucket_time = now;
336     }
337
338     if(token_bucket_tokens == 0)
339         return 0;
340
341     token_bucket_tokens--;
342     return 1;
343 }
344
345 static int
346 send_request(struct circular_list *list, int dopop, int doping, int want)
347 {
348     unsigned char ttid[4];
349     struct sockaddr_storage ss;
350     socklen_t sslen;
351     int rc;
352
353     if(list_empty(list))
354         return 0;
355
356     if(dopop) {
357         rc = list_pop(list, &ss, &sslen);
358         if(rc == 0)
359             return 0;
360     } else {
361         rc = list_random(list, NULL, &ss, &sslen);
362         if(rc == 0)
363             return 0;
364     }
365
366     if(doping) {
367         make_tid(ttid, "pn", 0);
368         debugf("Sending ping.\n");
369         return send_ping((struct sockaddr*)&ss, sslen, ttid, 4);
370     } else {
371         unsigned char id[20];
372         int i;
373         for(i = 0; i < 20; i++)
374             id[i] = random() & 0xFF;
375         make_tid(ttid, "fn", 0);
376         debugf("Sending find_node.\n");
377         return send_find_node((struct sockaddr*)&ss, sslen, ttid, 4,
378                               id, want, 0);
379     }
380 }
381
382 int
383 main(int argc, char **argv)
384 {
385     int port = 6881, quiet = 0, ipv4 = 1, ipv6 = 1;
386     int opt, rc, i, send4;
387     unsigned char ttid[4];
388
389     while(1) {
390         opt = getopt(argc, argv, "q46");
391         if(opt < 0)
392             break;
393
394         switch(opt) {
395         case 'q':
396             quiet = 1;
397             break;
398         case '4':
399             ipv6 = 0;
400             break;
401         case '6':
402             ipv4 = 0;
403             break;
404         default:
405             goto usage;
406         }
407     }
408
409     i = optind;
410
411     if(argc < i + 1)
412         goto usage;
413
414     port = atoi(argv[i++]);
415     if(port <= 0 || port >= 0x10000)
416         goto usage;
417
418     if(ipv4) {
419         dht_socket = socket(PF_INET, SOCK_DGRAM, 0);
420         if(dht_socket < 0)
421             perror("socket(IPv4)");
422     }
423
424     if(ipv6) {
425         dht_socket6 = socket(PF_INET6, SOCK_DGRAM, 0);
426         if(dht_socket6 < 0)
427             perror("socket(IPv6)");
428     }
429
430     if(dht_socket < 0 && dht_socket6 < 0) {
431         fprintf(stderr, "Eek!\n");
432         exit(1);
433     }
434
435     if(dht_socket >= 0) {
436         struct sockaddr_in sin;
437         int rc;
438         memset(&sin, 0, sizeof(sin));
439         sin.sin_family = AF_INET;
440         sin.sin_port = htons(port);
441         rc = bind(dht_socket, (struct sockaddr*)&sin, sizeof(sin));
442         if(rc < 0) {
443             perror("bind(IPv4)");
444             exit(1);
445         }
446
447         rc = fcntl(dht_socket, F_GETFL, 0);
448         if(rc < 0) {
449             perror("F_GETFL");
450             exit(1);
451         }
452             
453         rc = fcntl(dht_socket, F_SETFL, (rc | O_NONBLOCK));
454         if(rc < 0) {
455             perror("F_SETFL");
456             exit(1);
457         }
458     }
459
460     if(dht_socket6 >= 0) {
461         struct sockaddr_in6 sin6;
462         int rc;
463         int val = 1;
464
465         rc = setsockopt(dht_socket6, IPPROTO_IPV6, IPV6_V6ONLY,
466                         (char *)&val, sizeof(val));
467         if(rc < 0) {
468             perror("setsockopt(IPV6_V6ONLY)");
469             exit(1);
470         }
471
472         /* BEP-32 mandates that we should bind this socket to one of our
473            global IPv6 addresses.  In this program, this only happens if
474            the user used the -b flag. */
475
476         memset(&sin6, 0, sizeof(sin6));
477         sin6.sin6_family = AF_INET6;
478         sin6.sin6_port = htons(port);
479         rc = bind(dht_socket6, (struct sockaddr*)&sin6, sizeof(sin6));
480         if(rc < 0) {
481             perror("bind(IPv6)");
482             exit(1);
483         }
484
485         rc = fcntl(dht_socket6, F_GETFL, 0);
486         if(rc < 0) {
487             perror("F_GETFL");
488             exit(1);
489         }
490             
491         rc = fcntl(dht_socket6, F_SETFL, (rc | O_NONBLOCK));
492         if(rc < 0) {
493             perror("F_SETFL");
494             exit(1);
495         }
496     }
497
498     {
499         int fd;
500         unsigned int seed;
501
502         fd = open("/dev/urandom", O_RDONLY);
503         if(fd < 0) {
504             perror("open(random)");
505             exit(1);
506         }
507
508         rc = read(fd, myid, 20);
509         if(rc < 20) {
510             perror("open(random)");
511             exit(1);
512         }
513
514         rc = read(fd, &seed, sizeof(seed));
515         srandom(seed);
516
517         close(fd);
518     }
519
520     memcpy(my_v, "1:v4:JB\0\0", 9);
521     have_v = 1;
522
523     if(!quiet)
524         dht_debug = stdout;
525     
526     while(i < argc) {
527         struct addrinfo hints, *info, *infop;
528         memset(&hints, 0, sizeof(hints));
529         hints.ai_socktype = SOCK_DGRAM;
530         hints.ai_family = 0;
531         if(dht_socket < 0)
532             hints.ai_family = AF_INET6;
533         else if(dht_socket6 < 0)
534             hints.ai_family |= AF_INET;
535         rc = getaddrinfo(argv[i], argv[i + 1], &hints, &info);
536         if(rc != 0) {
537             fprintf(stderr, "getaddrinfo: %s\n", gai_strerror(rc));
538             exit(1);
539         }
540
541         i++;
542         if(i >= argc)
543             goto usage;
544
545         infop = info;
546         while(infop) {
547             make_tid(ttid, "pn", 0);
548             debugf("Sending ping.\n");
549             send_ping(infop->ai_addr, infop->ai_addrlen, ttid, 4);
550             infop = infop->ai_next;
551         }
552         freeaddrinfo(info);
553
554         i++;
555     }
556
557     token_bucket_time = time(NULL);
558     token_bucket_tokens = MAX_TOKEN_BUCKET_TOKENS;
559
560     while(1) {
561         struct timeval tv;
562         fd_set readfds;
563         int rc;
564
565         if((dht_socket >= 0 && list_elements(&v4_confirmed) <= 16) ||
566            (dht_socket6 >= 0 && list_elements(&v6_confirmed) <= 16))
567             tv.tv_sec = 0;
568         else
569             tv.tv_sec = random() % 30;
570         tv.tv_usec = random() % 1000000;
571         
572         FD_ZERO(&readfds);
573         if(dht_socket >= 0)
574             FD_SET(dht_socket, &readfds);
575         if(dht_socket6 >= 0)
576             FD_SET(dht_socket6, &readfds);
577
578         if(dht_debug)
579             debugf("%d+%d %d+%d\n",
580                    list_elements(&v4_confirmed), list_elements(&v6_confirmed),
581                    list_elements(&v4_new), list_elements(&v6_new));
582
583         rc = select(MAX(dht_socket, dht_socket6) + 1, &readfds, NULL, NULL,
584                     &tv);
585
586         if(rc < 0) {
587             if(errno != EINTR) {
588                 perror("select");
589                 sleep(1);
590             }
591         }
592
593         if(rc > 0) {
594             int rc, message;
595             unsigned char tid[16], id[20], info_hash[20], target[20];
596             unsigned char buf[1536], nodes[256], nodes6[1024], token[128];
597             int tid_len = 16, token_len = 128;
598             int nodes_len = 256, nodes6_len = 1024;
599             unsigned short port;
600             unsigned char values[2048], values6[2048];
601             int values_len = 2048, values6_len = 2048;
602             int want;
603             struct sockaddr_storage source_storage;
604             struct sockaddr *source = (struct sockaddr*)&source_storage;
605             socklen_t sourcelen = sizeof(source_storage);
606             if(dht_socket >= 0 && FD_ISSET(dht_socket, &readfds)) {
607                 rc = recvfrom(dht_socket, buf, 1536, 0, source, &sourcelen);
608             } else if(dht_socket6 >= 0 && FD_ISSET(dht_socket6, &readfds)) {
609                 rc = recvfrom(dht_socket6, buf, 1536, 0, source, &sourcelen);
610             }
611
612             if(rc < 0 || sourcelen > sizeof(struct sockaddr_storage))
613                 goto dontread;
614
615             if(is_martian(source))
616                 goto dontread;
617
618             /* There's a bug in parse_message -- it will happily overflow the
619                buffer if it's not NUL-terminated.  For now, put a NUL at the
620                end of buffers. */
621
622             if(rc < 1536) {
623                 buf[rc] = '\0';
624             } else {
625                 debugf("Overlong message.\n");
626                 goto dontread;
627             }
628
629             message = parse_message(buf, rc, tid, &tid_len, id, info_hash,
630                                     target, &port, token, &token_len,
631                                     nodes, &nodes_len, nodes6, &nodes6_len,
632                                     values, &values_len, values6, &values6_len,
633                                     &want);
634
635             if(id_cmp(id, myid) == 0) {
636                 debugf("Received message from self.\n");
637                 goto dontread;
638             }
639
640             if(message > REPLY) {
641                 /* Rate limit requests. */
642                 if(!token_bucket()) {
643                     debugf("Dropping request due to rate limiting.\n");
644                     goto dontread;
645                 }
646             }
647
648             switch(message) {
649             case REPLY:
650                 if(tid_len != 4) {
651                     debugf("Broken node truncates transaction ids.\n");
652                     goto dontread;
653                 }
654                 if(tid_match(tid, "pn", NULL)) {
655                     debugf("Pong!\n");
656                     new_node(id, source, sourcelen, 2);
657                 } else if(tid_match(tid, "fn", NULL)) {
658                     debugf("Nodes found!\n");
659                     if(nodes_len % 26 != 0 || nodes6_len % 38 != 0) {
660                         debugf("Unexpected length for node info!\n");
661                     } else {
662                         new_node(id, source, sourcelen, 2);
663                         for(i = 0; i < nodes_len / 26; i++) {
664                             unsigned char *ni = nodes + i * 26;
665                             struct sockaddr_in sin;
666                             if(id_cmp(ni, myid) == 0)
667                                 continue;
668                             memset(&sin, 0, sizeof(sin));
669                             sin.sin_family = AF_INET;
670                             memcpy(&sin.sin_addr, ni + 20, 4);
671                             memcpy(&sin.sin_port, ni + 24, 2);
672                             new_node(ni, (struct sockaddr*)&sin, sizeof(sin),
673                                      0);
674                         }
675                         for(i = 0; i < nodes6_len / 38; i++) {
676                             unsigned char *ni = nodes6 + i * 38;
677                             struct sockaddr_in6 sin6;
678                             if(id_cmp(ni, myid) == 0)
679                                 continue;
680                             memset(&sin6, 0, sizeof(sin6));
681                             sin6.sin6_family = AF_INET6;
682                             memcpy(&sin6.sin6_addr, ni + 20, 16);
683                             memcpy(&sin6.sin6_port, ni + 36, 2);
684                             new_node(ni, (struct sockaddr*)&sin6, sizeof(sin6),
685                                      0);
686                         }
687                     }
688                 } else {
689                     debugf("Unexpected reply!\n");
690                     goto dontread;
691                 }
692                 break;
693             case PING:
694                 debugf("Ping (%d)!\n", tid_len);
695                 new_node(id, source, sourcelen, 1);
696                 debugf("Sending pong.\n");
697                 send_pong(source, sourcelen, tid, tid_len);
698                 break;
699
700             case FIND_NODE:
701             case GET_PEERS:
702                 if(message == FIND_NODE)
703                     debugf("Find node!\n");
704                 else
705                     debugf("Get peers!\n");
706                 new_node(id, source, sourcelen, 1);
707                 debugf("Sending nodes (%d).\n", want);
708                 send_random_nodes(source, sourcelen,
709                                   tid, tid_len, target, want);
710                 break;
711             case ANNOUNCE_PEER:
712                 debugf("Announce peer!\n");
713                 send_error(source, sourcelen, tid, tid_len,
714                            203, "This node doesn't accept announces");
715                 break;
716             }
717         }
718
719     dontread:
720
721         /* We need to be careful to avoid a positive feedback loop.  Make
722            sure we send at most one packet each time through the select
723            loop. */
724
725         if(dht_socket6 < 0)
726             send4 = 1;
727         else if(dht_socket < 0)
728             send4 = 0;
729         else
730             send4 = random() % 2;
731
732         if(send4) {
733             int want =
734                 dht_socket6 >= 0 && list_free(&v6_new) > 8 ?
735                 (WANT4 | WANT6) : 0;
736             if(!list_empty(&v4_new))
737                 send_request(&v4_new, 1, list_free(&v4_new) < 8, want);
738             else if(!list_empty(&v4_confirmed))
739                 send_request(&v4_confirmed, 0, 0, want);
740         } else {
741             int want =
742                 dht_socket >= 0 && list_free(&v4_new) > 8 ?
743                 (WANT4 | WANT6) : 0;
744             if(!list_empty(&v6_new))
745                 send_request(&v6_new, 1, list_free(&v6_new) < 8, want);
746             else if(!list_empty(&v6_confirmed))
747                 send_request(&v6_confirmed, 0, 0, want);
748         }
749     }
750
751     return 0;
752
753  usage:
754     fprintf(stderr, "dht-bootstrap [-q] [-4] [-6] port [node port...]\n");
755     exit(1);
756 }
757
758 /* We could use a proper bencoding printer and parser, but the format of
759    DHT messages is fairly stylised, so this seemed simpler. */
760
761 #define CHECK(offset, delta, size)                      \
762     if(delta < 0 || offset + delta > size) goto fail
763
764 #define INC(offset, delta, size)                        \
765     CHECK(offset, delta, size);                         \
766     offset += delta
767
768 #define COPY(buf, offset, src, delta, size)             \
769     CHECK(offset, delta, size);                         \
770     memcpy(buf + offset, src, delta);                   \
771     offset += delta;
772
773 #define ADD_V(buf, offset, size)                        \
774     if(have_v) {                                        \
775         COPY(buf, offset, my_v, sizeof(my_v), size);    \
776     }
777
778 static int
779 dht_send(const void *buf, size_t len, int flags,
780          const struct sockaddr *sa, int salen)
781 {
782     int s;
783
784     if(salen == 0)
785         abort();
786
787     if(sa->sa_family == AF_INET)
788         s = dht_socket;
789     else if(sa->sa_family == AF_INET6)
790         s = dht_socket6;
791     else
792         s = -1;
793
794     if(s < 0) {
795         errno = EAFNOSUPPORT;
796         return -1;
797     }
798
799     return sendto(s, buf, len, flags, sa, salen);
800 }
801
802 int
803 send_ping(struct sockaddr *sa, int salen,
804           const unsigned char *tid, int tid_len)
805 {
806     char buf[512];
807     int i = 0, rc;
808     rc = snprintf(buf + i, 512 - i, "d1:ad2:id20:"); INC(i, rc, 512);
809     COPY(buf, i, myid, 20, 512);
810     rc = snprintf(buf + i, 512 - i, "e1:q4:ping1:t%d:", tid_len);
811     INC(i, rc, 512);
812     COPY(buf, i, tid, tid_len, 512);
813     ADD_V(buf, i, 512);
814     rc = snprintf(buf + i, 512 - i, "1:y1:qe"); INC(i, rc, 512);
815     return dht_send(buf, i, 0, sa, salen);
816
817  fail:
818     errno = ENOSPC;
819     return -1;
820 }
821
822 int
823 send_pong(struct sockaddr *sa, int salen,
824           const unsigned char *tid, int tid_len)
825 {
826     char buf[512];
827     int i = 0, rc;
828     rc = snprintf(buf + i, 512 - i, "d1:rd2:id20:"); INC(i, rc, 512);
829     COPY(buf, i, myid, 20, 512);
830     rc = snprintf(buf + i, 512 - i, "e1:t%d:", tid_len); INC(i, rc, 512);
831     COPY(buf, i, tid, tid_len, 512);
832     ADD_V(buf, i, 512);
833     rc = snprintf(buf + i, 512 - i, "1:y1:re"); INC(i, rc, 512);
834     return dht_send(buf, i, 0, sa, salen);
835
836  fail:
837     errno = ENOSPC;
838     return -1;
839 }
840
841 int
842 send_find_node(struct sockaddr *sa, int salen,
843                const unsigned char *tid, int tid_len,
844                const unsigned char *target, int want, int confirm)
845 {
846     char buf[512];
847     int i = 0, rc;
848     rc = snprintf(buf + i, 512 - i, "d1:ad2:id20:"); INC(i, rc, 512);
849     COPY(buf, i, myid, 20, 512);
850     rc = snprintf(buf + i, 512 - i, "6:target20:"); INC(i, rc, 512);
851     COPY(buf, i, target, 20, 512);
852     if(want > 0) {
853         rc = snprintf(buf + i, 512 - i, "4:wantl%s%se",
854                       (want & WANT4) ? "2:n4" : "",
855                       (want & WANT6) ? "2:n6" : "");
856         INC(i, rc, 512);
857     }
858     rc = snprintf(buf + i, 512 - i, "e1:q9:find_node1:t%d:", tid_len);
859     INC(i, rc, 512);
860     COPY(buf, i, tid, tid_len, 512);
861     ADD_V(buf, i, 512);
862     rc = snprintf(buf + i, 512 - i, "1:y1:qe"); INC(i, rc, 512);
863     return dht_send(buf, i, confirm ? MSG_CONFIRM : 0, sa, salen);
864
865  fail:
866     errno = ENOSPC;
867     return -1;
868 }
869
870 int
871 send_nodes(struct sockaddr *sa, int salen,
872            const unsigned char *tid, int tid_len,
873            const unsigned char *nodes, int nodes_len,
874            const unsigned char *nodes6, int nodes6_len)
875 {
876     char buf[2048];
877     int i = 0, rc;
878
879     rc = snprintf(buf + i, 2048 - i, "d1:rd2:id20:"); INC(i, rc, 2048);
880     COPY(buf, i, myid, 20, 2048);
881     if(nodes_len > 0) {
882         rc = snprintf(buf + i, 2048 - i, "5:nodes%d:", nodes_len);
883         INC(i, rc, 2048);
884         COPY(buf, i, nodes, nodes_len, 2048);
885     }
886     if(nodes6_len > 0) {
887          rc = snprintf(buf + i, 2048 - i, "6:nodes6%d:", nodes6_len);
888          INC(i, rc, 2048);
889          COPY(buf, i, nodes6, nodes6_len, 2048);
890     }
891
892     rc = snprintf(buf + i, 2048 - i, "e1:t%d:", tid_len); INC(i, rc, 2048);
893     COPY(buf, i, tid, tid_len, 2048);
894     ADD_V(buf, i, 2048);
895     rc = snprintf(buf + i, 2048 - i, "1:y1:re"); INC(i, rc, 2048);
896
897     return dht_send(buf, i, 0, sa, salen);
898
899  fail:
900     errno = ENOSPC;
901     return -1;
902 }
903
904 static int
905 buffer_random_nodes(int af, unsigned char *nodes)
906 {
907     struct circular_list *list;
908     struct sockaddr_storage ss;
909     socklen_t sslen;
910     unsigned char id[20];
911     int n;
912     int rc;
913
914     switch(af) {
915     case AF_INET: list = &v4_confirmed; break;
916     case AF_INET6: list = &v6_confirmed; break;
917     default: abort();
918     }
919
920     n = 0;
921     while(n < 8) {
922         rc = list_random(list, id, &ss, &sslen);
923         if(rc < 1)
924             break;
925         switch(af) {
926         case AF_INET: {
927             struct sockaddr_in *sin = (struct sockaddr_in*)&ss;
928             memcpy(nodes + n * 26, id, 20);
929             memcpy(nodes + n * 26 + 20, &sin->sin_addr, 4);
930             memcpy(nodes + n * 26 + 24, &sin->sin_port, 2);
931             n++;
932             break;
933         }
934         case AF_INET6: {
935             struct sockaddr_in6 *sin6 = (struct sockaddr_in6*)&ss;
936             memcpy(nodes + n * 38, id, 20);
937             memcpy(nodes + n * 38 + 20, &sin6->sin6_addr, 16);
938             memcpy(nodes + n * 38 + 36, &sin6->sin6_port, 2);
939             n++;
940             break;
941         }
942         default:
943             abort();
944         }
945     }
946     return n;
947 }
948
949 int
950 send_random_nodes(struct sockaddr *sa, int salen,
951                   const unsigned char *tid, int tid_len,
952                   const unsigned char *id, int want)
953 {
954     unsigned char nodes[8 * 26];
955     unsigned char nodes6[8 * 38];
956     int numnodes = 0, numnodes6 = 0;
957
958     if(want < 0)
959         want = sa->sa_family == AF_INET ? WANT4 : WANT6;
960
961     if((want & WANT4))
962         numnodes = buffer_random_nodes(AF_INET, nodes);
963
964     if((want & WANT6))
965         numnodes6 = buffer_random_nodes(AF_INET6, nodes6);
966
967     return send_nodes(sa, salen, tid, tid_len,
968                       nodes, numnodes * 26,
969                       nodes6, numnodes6 * 38);
970 }
971
972 static int
973 send_error(struct sockaddr *sa, int salen,
974            unsigned char *tid, int tid_len,
975            int code, const char *message)
976 {
977     char buf[512];
978     int i = 0, rc;
979
980     rc = snprintf(buf + i, 512 - i, "d1:eli%de%d:",
981                   code, (int)strlen(message));
982     INC(i, rc, 512);
983     COPY(buf, i, message, (int)strlen(message), 512);
984     rc = snprintf(buf + i, 512 - i, "e1:t%d:", tid_len); INC(i, rc, 512);
985     COPY(buf, i, tid, tid_len, 512);
986     ADD_V(buf, i, 512);
987     rc = snprintf(buf + i, 512 - i, "1:y1:ee"); INC(i, rc, 512);
988     return dht_send(buf, i, 0, sa, salen);
989
990  fail:
991     errno = ENOSPC;
992     return -1;
993 }
994
995 #undef CHECK
996 #undef INC
997 #undef COPY
998 #undef ADD_V
999
1000 #ifndef HAVE_MEMMEM
1001 static void *
1002 memmem(const void *haystack, size_t haystacklen,
1003        const void *needle, size_t needlelen)
1004 {
1005     const char *h = haystack;
1006     const char *n = needle;
1007     size_t i;
1008
1009     /* size_t is unsigned */
1010     if(needlelen > haystacklen)
1011         return NULL;
1012
1013     for(i = 0; i <= haystacklen - needlelen; i++) {
1014         if(memcmp(h + i, n, needlelen) == 0)
1015             return (void*)(h + i);
1016     }
1017     return NULL;
1018 }
1019 #endif
1020
1021 static int
1022 parse_message(const unsigned char *buf, int buflen,
1023               unsigned char *tid_return, int *tid_len,
1024               unsigned char *id_return, unsigned char *info_hash_return,
1025               unsigned char *target_return, unsigned short *port_return,
1026               unsigned char *token_return, int *token_len,
1027               unsigned char *nodes_return, int *nodes_len,
1028               unsigned char *nodes6_return, int *nodes6_len,
1029               unsigned char *values_return, int *values_len,
1030               unsigned char *values6_return, int *values6_len,
1031               int *want_return)
1032 {
1033     const unsigned char *p;
1034
1035     /* This code will happily crash if the buffer is not NUL-terminated. */
1036     if(buf[buflen] != '\0') {
1037         debugf("Eek!  parse_message with unterminated buffer.\n");
1038         return -1;
1039     }
1040
1041 #define CHECK(ptr, len)                                                 \
1042     if(((unsigned char*)ptr) + (len) > (buf) + (buflen)) goto overflow;
1043
1044     if(tid_return) {
1045         p = memmem(buf, buflen, "1:t", 3);
1046         if(p) {
1047             long l;
1048             char *q;
1049             l = strtol((char*)p + 3, &q, 10);
1050             if(q && *q == ':' && l > 0 && l < *tid_len) {
1051                 CHECK(q + 1, l);
1052                 memcpy(tid_return, q + 1, l);
1053                 *tid_len = l;
1054             } else
1055                 *tid_len = 0;
1056         }
1057     }
1058     if(id_return) {
1059         p = memmem(buf, buflen, "2:id20:", 7);
1060         if(p) {
1061             CHECK(p + 7, 20);
1062             memcpy(id_return, p + 7, 20);
1063         } else {
1064             memset(id_return, 0, 20);
1065         }
1066     }
1067     if(info_hash_return) {
1068         p = memmem(buf, buflen, "9:info_hash20:", 14);
1069         if(p) {
1070             CHECK(p + 14, 20);
1071             memcpy(info_hash_return, p + 14, 20);
1072         } else {
1073             memset(info_hash_return, 0, 20);
1074         }
1075     }
1076     if(port_return) {
1077         p = memmem(buf, buflen, "porti", 5);
1078         if(p) {
1079             long l;
1080             char *q;
1081             l = strtol((char*)p + 5, &q, 10);
1082             if(q && *q == 'e' && l > 0 && l < 0x10000)
1083                 *port_return = l;
1084             else
1085                 *port_return = 0;
1086         } else
1087             *port_return = 0;
1088     }
1089     if(target_return) {
1090         p = memmem(buf, buflen, "6:target20:", 11);
1091         if(p) {
1092             CHECK(p + 11, 20);
1093             memcpy(target_return, p + 11, 20);
1094         } else {
1095             memset(target_return, 0, 20);
1096         }
1097     }
1098     if(token_return) {
1099         p = memmem(buf, buflen, "5:token", 7);
1100         if(p) {
1101             long l;
1102             char *q;
1103             l = strtol((char*)p + 7, &q, 10);
1104             if(q && *q == ':' && l > 0 && l < *token_len) {
1105                 CHECK(q + 1, l);
1106                 memcpy(token_return, q + 1, l);
1107                 *token_len = l;
1108             } else
1109                 *token_len = 0;
1110         } else
1111             *token_len = 0;
1112     }
1113
1114     if(nodes_len) {
1115         p = memmem(buf, buflen, "5:nodes", 7);
1116         if(p) {
1117             long l;
1118             char *q;
1119             l = strtol((char*)p + 7, &q, 10);
1120             if(q && *q == ':' && l > 0 && l < *nodes_len) {
1121                 CHECK(q + 1, l);
1122                 memcpy(nodes_return, q + 1, l);
1123                 *nodes_len = l;
1124             } else
1125                 *nodes_len = 0;
1126         } else
1127             *nodes_len = 0;
1128     }
1129
1130     if(nodes6_len) {
1131         p = memmem(buf, buflen, "6:nodes6", 8);
1132         if(p) {
1133             long l;
1134             char *q;
1135             l = strtol((char*)p + 8, &q, 10);
1136             if(q && *q == ':' && l > 0 && l < *nodes6_len) {
1137                 CHECK(q + 1, l);
1138                 memcpy(nodes6_return, q + 1, l);
1139                 *nodes6_len = l;
1140             } else
1141                 *nodes6_len = 0;
1142         } else
1143             *nodes6_len = 0;
1144     }
1145
1146     if(values_len || values6_len) {
1147         p = memmem(buf, buflen, "6:valuesl", 9);
1148         if(p) {
1149             int i = p - buf + 9;
1150             int j = 0, j6 = 0;
1151             while(1) {
1152                 long l;
1153                 char *q;
1154                 l = strtol((char*)buf + i, &q, 10);
1155                 if(q && *q == ':' && l > 0) {
1156                     CHECK(q + 1, l);
1157                     if(l == 6) {
1158                         if(j + l > *values_len)
1159                             continue;
1160                         i = q + 1 + l - (char*)buf;
1161                         memcpy((char*)values_return + j, q + 1, l);
1162                         j += l;
1163                     } else if(l == 18) {
1164                         if(j6 + l > *values6_len)
1165                             continue;
1166                         i = q + 1 + l - (char*)buf;
1167                         memcpy((char*)values6_return + j6, q + 1, l);
1168                         j6 += l;
1169                     } else {
1170                         debugf("Received weird value -- %d bytes.\n", (int)l);
1171                         i = q + 1 + l - (char*)buf;
1172                     }
1173                 } else {
1174                     break;
1175                 }
1176             }
1177             if(i >= buflen || buf[i] != 'e')
1178                 debugf("eek... unexpected end for values.\n");
1179             if(values_len)
1180                 *values_len = j;
1181             if(values6_len)
1182                 *values6_len = j6;
1183         } else {
1184             *values_len = 0;
1185             *values6_len = 0;
1186         }
1187     }
1188
1189     if(want_return) {
1190         p = memmem(buf, buflen, "4:wantl", 7);
1191         if(p) {
1192             int i = p - buf + 7;
1193             *want_return = 0;
1194             while(buf[i] > '0' && buf[i] <= '9' && buf[i + 1] == ':' &&
1195                   i + 2 + buf[i] - '0' < buflen) {
1196                 CHECK(buf + i + 2, buf[i] - '0');
1197                 if(buf[i] == '2' && memcmp(buf + i + 2, "n4", 2) == 0)
1198                     *want_return |= WANT4;
1199                 else if(buf[i] == '2' && memcmp(buf + i + 2, "n6", 2) == 0)
1200                     *want_return |= WANT6;
1201                 else
1202                     debugf("eek... unexpected want flag (%c)\n", buf[i]);
1203                 i += 2 + buf[i] - '0';
1204             }
1205             if(i >= buflen || buf[i] != 'e')
1206                 debugf("eek... unexpected end for want.\n");
1207         } else {
1208             *want_return = -1;
1209         }
1210     }
1211
1212 #undef CHECK
1213
1214     if(memmem(buf, buflen, "1:y1:r", 6))
1215         return REPLY;
1216     if(memmem(buf, buflen, "1:y1:e", 6))
1217         return ERROR;
1218     if(!memmem(buf, buflen, "1:y1:q", 6))
1219         return -1;
1220     if(memmem(buf, buflen, "1:q4:ping", 9))
1221         return PING;
1222     if(memmem(buf, buflen, "1:q9:find_node", 14))
1223        return FIND_NODE;
1224     if(memmem(buf, buflen, "1:q9:get_peers", 14))
1225         return GET_PEERS;
1226     if(memmem(buf, buflen, "1:q13:announce_peer", 19))
1227        return ANNOUNCE_PEER;
1228     return -1;
1229
1230  overflow:
1231     debugf("Truncated message.\n");
1232     return -1;
1233 }