dht-bootstrap.c

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