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