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