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