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