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     if(ipv4) {
 410         dht_socket = socket(PF_INET, SOCK_DGRAM, 0);
 411         if(dht_socket < 0)
 412             perror("socket(IPv4)");
 413     }
 414
 415     if(ipv6) {
 416         dht_socket6 = socket(PF_INET6, SOCK_DGRAM, 0);
 417         if(dht_socket6 < 0)
 418             perror("socket(IPv6)");
 419     }
 420
 421     if(dht_socket < 0 && dht_socket6 < 0) {
 422         fprintf(stderr, "Eek!\n");
 423         exit(1);
 424     }
 425
 426     if(dht_socket >= 0) {
 427         struct sockaddr_in sin;
 428         int rc;
 429         memset(&sin, 0, sizeof(sin));
 430         sin.sin_family = AF_INET;
 431         sin.sin_port = htons(port);
 432         rc = bind(dht_socket, (struct sockaddr*)&sin, sizeof(sin));
 433         if(rc < 0) {
 434             perror("bind(IPv4)");
 435             exit(1);
 436         }
 437
 438         rc = fcntl(dht_socket, F_GETFL, 0);
 439         if(rc < 0) {
 440             perror("F_GETFL");
 441             exit(1);
 442         }
 443
 444         rc = fcntl(dht_socket, F_SETFL, (rc | O_NONBLOCK));
 445         if(rc < 0) {
 446             perror("F_SETFL");
 447             exit(1);
 448         }
 449     }
 450
 451     if(dht_socket6 >= 0) {
 452         struct sockaddr_in6 sin6;
 453         int rc;
 454         int val = 1;
 455
 456         rc = setsockopt(dht_socket6, IPPROTO_IPV6, IPV6_V6ONLY,
 457                         (char *)&val, sizeof(val));
 458         if(rc < 0) {
 459             perror("setsockopt(IPV6_V6ONLY)");
 460             exit(1);
 461         }
 462
 463         /* BEP-32 mandates that we should bind this socket to one of our
 464            global IPv6 addresses.  In this simple example, this only
 465            happens if the user used the -b flag. */
 466
 467         memset(&sin6, 0, sizeof(sin6));
 468         sin6.sin6_family = AF_INET6;
 469         sin6.sin6_port = htons(port);
 470         rc = bind(dht_socket6, (struct sockaddr*)&sin6, sizeof(sin6));
 471         if(rc < 0) {
 472             perror("bind(IPv6)");
 473             exit(1);
 474         }
 475
 476         rc = fcntl(dht_socket6, F_GETFL, 0);
 477         if(rc < 0) {
 478             perror("F_GETFL");
 479             exit(1);
 480         }
 481
 482         rc = fcntl(dht_socket6, F_SETFL, (rc | O_NONBLOCK));
 483         if(rc < 0) {
 484             perror("F_SETFL");
 485             exit(1);
 486         }
 487     }
 488
 489     {
 490         int fd;
 491         unsigned int seed;
 492
 493         fd = open("/dev/urandom", O_RDONLY);
 494         if(fd < 0) {
 495             perror("open(random)");
 496             exit(1);
 497         }
 498
 499         rc = read(fd, myid, 20);
 500         if(rc < 20) {
 501             perror("open(random)");
 502             exit(1);
 503         }
 504
 505         rc = read(fd, &seed, sizeof(seed));
 506         srandom(seed);
 507
 508         close(fd);
 509     }
 510
 511     memcpy(my_v, "1:v4:JB\0\0", 9);
 512     have_v = 1;
 513
 514     if(!quiet)
 515         dht_debug = stdout;
 516
 517     i = optind;
 518
 519     if(argc < i + 1)
 520         goto usage;
 521
 522     port = atoi(argv[i++]);
 523     if(port <= 0 || port >= 0x10000)
 524         goto usage;
 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, want4, want6;
 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             if(want > 0) {
 649                 want4 = (want & WANT4);
 650                 want6 = (want & WANT6);
 651             } else {
 652                 want4 = source->sa_family == AF_INET;
 653                 want6 = source->sa_family == AF_INET6;
 654             }
 655
 656             switch(message) {
 657             case REPLY:
 658                 if(tid_len != 4) {
 659                     debugf("Broken node truncates transaction ids.\n");
 660                     goto dontread;
 661                 }
 662                 if(tid_match(tid, "pn", NULL)) {
 663                     debugf("Pong!\n");
 664                     new_node(id, source, sourcelen, 2);
 665                 } else if(tid_match(tid, "fn", NULL)) {
 666                     debugf("Nodes found!\n");
 667                     if(nodes_len % 26 != 0 || nodes6_len % 38 != 0) {
 668                         debugf("Unexpected length for node info!\n");
 669                     } else {
 670                         new_node(id, source, sourcelen, 2);
 671                         for(i = 0; i < nodes_len / 26; i++) {
 672                             unsigned char *ni = nodes + i * 26;
 673                             struct sockaddr_in sin;
 674                             if(id_cmp(ni, myid) == 0)
 675                                 continue;
 676                             memset(&sin, 0, sizeof(sin));
 677                             sin.sin_family = AF_INET;
 678                             memcpy(&sin.sin_addr, ni + 20, 4);
 679                             memcpy(&sin.sin_port, ni + 24, 2);
 680                             new_node(ni, (struct sockaddr*)&sin, sizeof(sin),
 681                                      0);
 682                         }
 683                         for(i = 0; i < nodes6_len / 38; i++) {
 684                             unsigned char *ni = nodes6 + i * 38;
 685                             struct sockaddr_in6 sin6;
 686                             if(id_cmp(ni, myid) == 0)
 687                                 continue;
 688                             memset(&sin6, 0, sizeof(sin6));
 689                             sin6.sin6_family = AF_INET6;
 690                             memcpy(&sin6.sin6_addr, ni + 20, 16);
 691                             memcpy(&sin6.sin6_port, ni + 36, 2);
 692                             new_node(ni, (struct sockaddr*)&sin6, sizeof(sin6),
 693                                      0);
 694                         }
 695                     }
 696                 } else {
 697                     debugf("Unexpected reply!\n");
 698                     goto dontread;
 699                 }
 700                 break;
 701             case PING:
 702                 debugf("Ping (%d)!\n", tid_len);
 703                 new_node(id, source, sourcelen, 1);
 704                 debugf("Sending pong.\n");
 705                 send_pong(source, sourcelen, tid, tid_len);
 706                 break;
 707
 708             case FIND_NODE:
 709             case GET_PEERS:
 710                 if(message == FIND_NODE)
 711                     debugf("Find node!\n");
 712                 else
 713                     debugf("Get peers!\n");
 714                 new_node(id, source, sourcelen, 1);
 715                 debugf("Sending nodes (%d).\n", want);
 716                 send_random_nodes(source, sourcelen,
 717                                   tid, tid_len, target, want);
 718                 break;
 719             case ANNOUNCE_PEER:
 720                 debugf("Announce peer!\n");
 721                 send_error(source, sourcelen, tid, tid_len,
 722                            203, "This node doesn't accept announces");
 723                 break;
 724             }
 725         }
 726
 727     dontread:
 728
 729         /* We need to be careful to avoid a positive feedback loop.  Make
 730            sure we send at most one packet each time through the select
 731            loop. */
 732
 733         if(dht_socket6 < 0)
 734             send4 = 1;
 735         else if(dht_socket < 0)
 736             send4 = 0;
 737         else
 738             send4 = random() % 2;
 739
 740         if(send4) {
 741             int want =
 742                 dht_socket6 >= 0 && list_free(&v6_new) > 8 ?
 743                 (WANT4 | WANT6) : 0;
 744             if(!list_empty(&v4_new))
 745                 send_request(&v4_new, 1, list_free(&v4_new) < 8, want);
 746             else if(!list_empty(&v4_confirmed))
 747                 send_request(&v4_confirmed, 0, 0, want);
 748         } else {
 749             int want =
 750                 dht_socket >= 0 && list_free(&v4_new) > 8 ?
 751                 (WANT4 | WANT6) : 0;
 752             if(!list_empty(&v6_new))
 753                 send_request(&v6_new, 1, list_free(&v6_new) < 8, want);
 754             else if(!list_empty(&v6_confirmed))
 755                 send_request(&v6_confirmed, 0, 0, want);
 756         }
 757     }
 758
 759     return 0;
 760
 761  usage:
 762     fprintf(stderr, "dht-bootstrap [-q] [-4] [-6] port [node port...]\n");
 763     exit(1);
 764 }
 765
 766 /* We could use a proper bencoding printer and parser, but the format of
 767    DHT messages is fairly stylised, so this seemed simpler. */
 768
 769 #define CHECK(offset, delta, size)                      \
 770     if(delta < 0 || offset + delta > size) goto fail
 771
 772 #define INC(offset, delta, size)                        \
 773     CHECK(offset, delta, size);                         \
 774     offset += delta
 775
 776 #define COPY(buf, offset, src, delta, size)             \
 777     CHECK(offset, delta, size);                         \
 778     memcpy(buf + offset, src, delta);                   \
 779     offset += delta;
 780
 781 #define ADD_V(buf, offset, size)                        \
 782     if(have_v) {                                        \
 783         COPY(buf, offset, my_v, sizeof(my_v), size);    \
 784     }
 785
 786 static int
 787 dht_send(const void *buf, size_t len, int flags,
 788          const struct sockaddr *sa, int salen)
 789 {
 790     int s;
 791
 792     if(salen == 0)
 793         abort();
 794
 795     if(sa->sa_family == AF_INET)
 796         s = dht_socket;
 797     else if(sa->sa_family == AF_INET6)
 798         s = dht_socket6;
 799     else
 800         s = -1;
 801
 802     if(s < 0) {
 803         errno = EAFNOSUPPORT;
 804         return -1;
 805     }
 806
 807     return sendto(s, buf, len, flags, sa, salen);
 808 }
 809
 810 int
 811 send_ping(struct sockaddr *sa, int salen,
 812           const unsigned char *tid, int tid_len)
 813 {
 814     char buf[512];
 815     int i = 0, rc;
 816     rc = snprintf(buf + i, 512 - i, "d1:ad2:id20:"); INC(i, rc, 512);
 817     COPY(buf, i, myid, 20, 512);
 818     rc = snprintf(buf + i, 512 - i, "e1:q4:ping1:t%d:", tid_len);
 819     INC(i, rc, 512);
 820     COPY(buf, i, tid, tid_len, 512);
 821     ADD_V(buf, i, 512);
 822     rc = snprintf(buf + i, 512 - i, "1:y1:qe"); INC(i, rc, 512);
 823     return dht_send(buf, i, 0, sa, salen);
 824
 825  fail:
 826     errno = ENOSPC;
 827     return -1;
 828 }
 829
 830 int
 831 send_pong(struct sockaddr *sa, int salen,
 832           const unsigned char *tid, int tid_len)
 833 {
 834     char buf[512];
 835     int i = 0, rc;
 836     rc = snprintf(buf + i, 512 - i, "d1:rd2:id20:"); INC(i, rc, 512);
 837     COPY(buf, i, myid, 20, 512);
 838     rc = snprintf(buf + i, 512 - i, "e1:t%d:", tid_len); INC(i, rc, 512);
 839     COPY(buf, i, tid, tid_len, 512);
 840     ADD_V(buf, i, 512);
 841     rc = snprintf(buf + i, 512 - i, "1:y1:re"); INC(i, rc, 512);
 842     return dht_send(buf, i, 0, sa, salen);
 843
 844  fail:
 845     errno = ENOSPC;
 846     return -1;
 847 }
 848
 849 int
 850 send_find_node(struct sockaddr *sa, int salen,
 851                const unsigned char *tid, int tid_len,
 852                const unsigned char *target, int want, int confirm)
 853 {
 854     char buf[512];
 855     int i = 0, rc;
 856     rc = snprintf(buf + i, 512 - i, "d1:ad2:id20:"); INC(i, rc, 512);
 857     COPY(buf, i, myid, 20, 512);
 858     rc = snprintf(buf + i, 512 - i, "6:target20:"); INC(i, rc, 512);
 859     COPY(buf, i, target, 20, 512);
 860     if(want > 0) {
 861         rc = snprintf(buf + i, 512 - i, "4:wantl%s%se",
 862                       (want & WANT4) ? "2:n4" : "",
 863                       (want & WANT6) ? "2:n6" : "");
 864         INC(i, rc, 512);
 865     }
 866     rc = snprintf(buf + i, 512 - i, "e1:q9:find_node1:t%d:", tid_len);
 867     INC(i, rc, 512);
 868     COPY(buf, i, tid, tid_len, 512);
 869     ADD_V(buf, i, 512);
 870     rc = snprintf(buf + i, 512 - i, "1:y1:qe"); INC(i, rc, 512);
 871     return dht_send(buf, i, confirm ? MSG_CONFIRM : 0, sa, salen);
 872
 873  fail:
 874     errno = ENOSPC;
 875     return -1;
 876 }
 877
 878 int
 879 send_nodes(struct sockaddr *sa, int salen,
 880            const unsigned char *tid, int tid_len,
 881            const unsigned char *nodes, int nodes_len,
 882            const unsigned char *nodes6, int nodes6_len)
 883 {
 884     char buf[2048];
 885     int i = 0, rc;
 886
 887     rc = snprintf(buf + i, 2048 - i, "d1:rd2:id20:"); INC(i, rc, 2048);
 888     COPY(buf, i, myid, 20, 2048);
 889     if(nodes_len > 0) {
 890         rc = snprintf(buf + i, 2048 - i, "5:nodes%d:", nodes_len);
 891         INC(i, rc, 2048);
 892         COPY(buf, i, nodes, nodes_len, 2048);
 893     }
 894     if(nodes6_len > 0) {
 895          rc = snprintf(buf + i, 2048 - i, "6:nodes6%d:", nodes6_len);
 896          INC(i, rc, 2048);
 897          COPY(buf, i, nodes6, nodes6_len, 2048);
 898     }
 899
 900     rc = snprintf(buf + i, 2048 - i, "e1:t%d:", tid_len); INC(i, rc, 2048);
 901     COPY(buf, i, tid, tid_len, 2048);
 902     ADD_V(buf, i, 2048);
 903     rc = snprintf(buf + i, 2048 - i, "1:y1:re"); INC(i, rc, 2048);
 904
 905     return dht_send(buf, i, 0, sa, salen);
 906
 907  fail:
 908     errno = ENOSPC;
 909     return -1;
 910 }
 911
 912 static int
 913 buffer_random_nodes(int af, unsigned char *nodes)
 914 {
 915     struct circular_list *list;
 916     struct sockaddr_storage ss;
 917     socklen_t sslen;
 918     unsigned char id[20];
 919     int n;
 920     int rc;
 921
 922     switch(af) {
 923     case AF_INET: list = &v4_confirmed; break;
 924     case AF_INET6: list = &v6_confirmed; break;
 925     default: abort();
 926     }
 927
 928     n = 0;
 929     while(n < 8) {
 930         rc = list_random(list, id, &ss, &sslen);
 931         if(rc < 1)
 932             break;
 933         switch(af) {
 934         case AF_INET: {
 935             struct sockaddr_in *sin = (struct sockaddr_in*)&ss;
 936             memcpy(nodes + n * 26, id, 20);
 937             memcpy(nodes + n * 26 + 20, &sin->sin_addr, 4);
 938             memcpy(nodes + n * 26 + 24, &sin->sin_port, 2);
 939             n++;
 940             break;
 941         }
 942         case AF_INET6: {
 943             struct sockaddr_in6 *sin6 = (struct sockaddr_in6*)&ss;
 944             memcpy(nodes + n * 38, id, 20);
 945             memcpy(nodes + n * 38 + 20, &sin6->sin6_addr, 16);
 946             memcpy(nodes + n * 38 + 36, &sin6->sin6_port, 2);
 947             n++;
 948             break;
 949         }
 950         default:
 951             abort();
 952         }
 953     }
 954     return n;
 955 }
 956
 957 int
 958 send_random_nodes(struct sockaddr *sa, int salen,
 959                   const unsigned char *tid, int tid_len,
 960                   const unsigned char *id, int want)
 961 {
 962     unsigned char nodes[8 * 26];
 963     unsigned char nodes6[8 * 38];
 964     int numnodes = 0, numnodes6 = 0;
 965
 966     if(want < 0)
 967         want = sa->sa_family == AF_INET ? WANT4 : WANT6;
 968
 969     if((want & WANT4))
 970         numnodes = buffer_random_nodes(AF_INET, nodes);
 971
 972     if((want & WANT6))
 973         numnodes6 = buffer_random_nodes(AF_INET6, nodes6);
 974
 975     return send_nodes(sa, salen, tid, tid_len,
 976                       nodes, numnodes * 26,
 977                       nodes6, numnodes6 * 38);
 978 }
 979
 980 static int
 981 send_error(struct sockaddr *sa, int salen,
 982            unsigned char *tid, int tid_len,
 983            int code, const char *message)
 984 {
 985     char buf[512];
 986     int i = 0, rc;
 987
 988     rc = snprintf(buf + i, 512 - i, "d1:eli%de%d:",
 989                   code, (int)strlen(message));
 990     INC(i, rc, 512);
 991     COPY(buf, i, message, (int)strlen(message), 512);
 992     rc = snprintf(buf + i, 512 - i, "e1:t%d:", tid_len); INC(i, rc, 512);
 993     COPY(buf, i, tid, tid_len, 512);
 994     ADD_V(buf, i, 512);
 995     rc = snprintf(buf + i, 512 - i, "1:y1:ee"); INC(i, rc, 512);
 996     return dht_send(buf, i, 0, sa, salen);
 997
 998  fail:
 999     errno = ENOSPC;
1000     return -1;
1001 }
1002
1003 #undef CHECK
1004 #undef INC
1005 #undef COPY
1006 #undef ADD_V
1007
1008 #ifndef HAVE_MEMMEM
1009 static void *
1010 memmem(const void *haystack, size_t haystacklen,
1011        const void *needle, size_t needlelen)
1012 {
1013     const char *h = haystack;
1014     const char *n = needle;
1015     size_t i;
1016
1017     /* size_t is unsigned */
1018     if(needlelen > haystacklen)
1019         return NULL;
1020
1021     for(i = 0; i <= haystacklen - needlelen; i++) {
1022         if(memcmp(h + i, n, needlelen) == 0)
1023             return (void*)(h + i);
1024     }
1025     return NULL;
1026 }
1027 #endif
1028
1029 static int
1030 parse_message(const unsigned char *buf, int buflen,
1031               unsigned char *tid_return, int *tid_len,
1032               unsigned char *id_return, unsigned char *info_hash_return,
1033               unsigned char *target_return, unsigned short *port_return,
1034               unsigned char *token_return, int *token_len,
1035               unsigned char *nodes_return, int *nodes_len,
1036               unsigned char *nodes6_return, int *nodes6_len,
1037               unsigned char *values_return, int *values_len,
1038               unsigned char *values6_return, int *values6_len,
1039               int *want_return)
1040 {
1041     const unsigned char *p;
1042
1043     /* This code will happily crash if the buffer is not NUL-terminated. */
1044     if(buf[buflen] != '\0') {
1045         debugf("Eek!  parse_message with unterminated buffer.\n");
1046         return -1;
1047     }
1048
1049 #define CHECK(ptr, len)                                                 \
1050     if(((unsigned char*)ptr) + (len) > (buf) + (buflen)) goto overflow;
1051
1052     if(tid_return) {
1053         p = memmem(buf, buflen, "1:t", 3);
1054         if(p) {
1055             long l;
1056             char *q;
1057             l = strtol((char*)p + 3, &q, 10);
1058             if(q && *q == ':' && l > 0 && l < *tid_len) {
1059                 CHECK(q + 1, l);
1060                 memcpy(tid_return, q + 1, l);
1061                 *tid_len = l;
1062             } else
1063                 *tid_len = 0;
1064         }
1065     }
1066     if(id_return) {
1067         p = memmem(buf, buflen, "2:id20:", 7);
1068         if(p) {
1069             CHECK(p + 7, 20);
1070             memcpy(id_return, p + 7, 20);
1071         } else {
1072             memset(id_return, 0, 20);
1073         }
1074     }
1075     if(info_hash_return) {
1076         p = memmem(buf, buflen, "9:info_hash20:", 14);
1077         if(p) {
1078             CHECK(p + 14, 20);
1079             memcpy(info_hash_return, p + 14, 20);
1080         } else {
1081             memset(info_hash_return, 0, 20);
1082         }
1083     }
1084     if(port_return) {
1085         p = memmem(buf, buflen, "porti", 5);
1086         if(p) {
1087             long l;
1088             char *q;
1089             l = strtol((char*)p + 5, &q, 10);
1090             if(q && *q == 'e' && l > 0 && l < 0x10000)
1091                 *port_return = l;
1092             else
1093                 *port_return = 0;
1094         } else
1095             *port_return = 0;
1096     }
1097     if(target_return) {
1098         p = memmem(buf, buflen, "6:target20:", 11);
1099         if(p) {
1100             CHECK(p + 11, 20);
1101             memcpy(target_return, p + 11, 20);
1102         } else {
1103             memset(target_return, 0, 20);
1104         }
1105     }
1106     if(token_return) {
1107         p = memmem(buf, buflen, "5:token", 7);
1108         if(p) {
1109             long l;
1110             char *q;
1111             l = strtol((char*)p + 7, &q, 10);
1112             if(q && *q == ':' && l > 0 && l < *token_len) {
1113                 CHECK(q + 1, l);
1114                 memcpy(token_return, q + 1, l);
1115                 *token_len = l;
1116             } else
1117                 *token_len = 0;
1118         } else
1119             *token_len = 0;
1120     }
1121
1122     if(nodes_len) {
1123         p = memmem(buf, buflen, "5:nodes", 7);
1124         if(p) {
1125             long l;
1126             char *q;
1127             l = strtol((char*)p + 7, &q, 10);
1128             if(q && *q == ':' && l > 0 && l < *nodes_len) {
1129                 CHECK(q + 1, l);
1130                 memcpy(nodes_return, q + 1, l);
1131                 *nodes_len = l;
1132             } else
1133                 *nodes_len = 0;
1134         } else
1135             *nodes_len = 0;
1136     }
1137
1138     if(nodes6_len) {
1139         p = memmem(buf, buflen, "6:nodes6", 8);
1140         if(p) {
1141             long l;
1142             char *q;
1143             l = strtol((char*)p + 8, &q, 10);
1144             if(q && *q == ':' && l > 0 && l < *nodes6_len) {
1145                 CHECK(q + 1, l);
1146                 memcpy(nodes6_return, q + 1, l);
1147                 *nodes6_len = l;
1148             } else
1149                 *nodes6_len = 0;
1150         } else
1151             *nodes6_len = 0;
1152     }
1153
1154     if(values_len || values6_len) {
1155         p = memmem(buf, buflen, "6:valuesl", 9);
1156         if(p) {
1157             int i = p - buf + 9;
1158             int j = 0, j6 = 0;
1159             while(1) {
1160                 long l;
1161                 char *q;
1162                 l = strtol((char*)buf + i, &q, 10);
1163                 if(q && *q == ':' && l > 0) {
1164                     CHECK(q + 1, l);
1165                     if(l == 6) {
1166                         if(j + l > *values_len)
1167                             continue;
1168                         i = q + 1 + l - (char*)buf;
1169                         memcpy((char*)values_return + j, q + 1, l);
1170                         j += l;
1171                     } else if(l == 18) {
1172                         if(j6 + l > *values6_len)
1173                             continue;
1174                         i = q + 1 + l - (char*)buf;
1175                         memcpy((char*)values6_return + j6, q + 1, l);
1176                         j6 += l;
1177                     } else {
1178                         debugf("Received weird value -- %d bytes.\n", (int)l);
1179                         i = q + 1 + l - (char*)buf;
1180                     }
1181                 } else {
1182                     break;
1183                 }
1184             }
1185             if(i >= buflen || buf[i] != 'e')
1186                 debugf("eek... unexpected end for values.\n");
1187             if(values_len)
1188                 *values_len = j;
1189             if(values6_len)
1190                 *values6_len = j6;
1191         } else {
1192             *values_len = 0;
1193             *values6_len = 0;
1194         }
1195     }
1196
1197     if(want_return) {
1198         p = memmem(buf, buflen, "4:wantl", 7);
1199         if(p) {
1200             int i = p - buf + 7;
1201             *want_return = 0;
1202             while(buf[i] > '0' && buf[i] <= '9' && buf[i + 1] == ':' &&
1203                   i + 2 + buf[i] - '0' < buflen) {
1204                 CHECK(buf + i + 2, buf[i] - '0');
1205                 if(buf[i] == '2' && memcmp(buf + i + 2, "n4", 2) == 0)
1206                     *want_return |= WANT4;
1207                 else if(buf[i] == '2' && memcmp(buf + i + 2, "n6", 2) == 0)
1208                     *want_return |= WANT6;
1209                 else
1210                     debugf("eek... unexpected want flag (%c)\n", buf[i]);
1211                 i += 2 + buf[i] - '0';
1212             }
1213             if(i >= buflen || buf[i] != 'e')
1214                 debugf("eek... unexpected end for want.\n");
1215         } else {
1216             *want_return = -1;
1217         }
1218     }
1219
1220 #undef CHECK
1221
1222     if(memmem(buf, buflen, "1:y1:r", 6))
1223         return REPLY;
1224     if(memmem(buf, buflen, "1:y1:e", 6))
1225         return ERROR;
1226     if(!memmem(buf, buflen, "1:y1:q", 6))
1227         return -1;
1228     if(memmem(buf, buflen, "1:q4:ping", 9))
1229         return PING;
1230     if(memmem(buf, buflen, "1:q9:find_node", 14))
1231        return FIND_NODE;
1232     if(memmem(buf, buflen, "1:q9:get_peers", 14))
1233         return GET_PEERS;
1234     if(memmem(buf, buflen, "1:q13:announce_peer", 19))
1235        return ANNOUNCE_PEER;
1236     return -1;
1237
1238  overflow:
1239     debugf("Truncated message.\n");
1240     return -1;
1241 }