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