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