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