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     if(ipv4) {
 410         dht_socket = socket(PF_INET, SOCK_DGRAM, 0);
 411         if(dht_socket < 0)
 412             perror("socket(IPv4)");
 413     }
 414
 415     if(ipv6) {
 416         dht_socket6 = socket(PF_INET6, SOCK_DGRAM, 0);
 417         if(dht_socket6 < 0)
 418             perror("socket(IPv6)");
 419     }
 420
 421     if(dht_socket < 0 && dht_socket6 < 0) {
 422         fprintf(stderr, "Eek!\n");
 423         exit(1);
 424     }
 425
 426     if(dht_socket >= 0) {
 427         struct sockaddr_in sin;
 428         int rc;
 429         memset(&sin, 0, sizeof(sin));
 430         sin.sin_port = htons(port);
 431         rc = bind(dht_socket, (struct sockaddr*)&sin, sizeof(sin));
 432         if(rc < 0) {
 433             perror("bind(IPv4)");
 434             exit(1);
 435         }
 436
 437         rc = fcntl(dht_socket, F_GETFL, 0);
 438         if(rc < 0) {
 439             perror("F_GETFL");
 440             exit(1);
 441         }
 442
 443         rc = fcntl(dht_socket, F_SETFL, (rc | O_NONBLOCK));
 444         if(rc < 0) {
 445             perror("F_SETFL");
 446             exit(1);
 447         }
 448     }
 449
 450     if(dht_socket6 >= 0) {
 451         struct sockaddr_in6 sin6;
 452         int rc;
 453         int val = 1;
 454
 455         rc = setsockopt(dht_socket6, IPPROTO_IPV6, IPV6_V6ONLY,
 456                         (char *)&val, sizeof(val));
 457         if(rc < 0) {
 458             perror("setsockopt(IPV6_V6ONLY)");
 459             exit(1);
 460         }
 461
 462         /* BEP-32 mandates that we should bind this socket to one of our
 463            global IPv6 addresses.  In this simple example, this only
 464            happens if the user used the -b flag. */
 465
 466         memset(&sin6, 0, sizeof(sin6));
 467         sin6.sin6_port = htons(port);
 468         rc = bind(dht_socket6, (struct sockaddr*)&sin6, sizeof(sin6));
 469         if(rc < 0) {
 470             perror("bind(IPv6)");
 471             exit(1);
 472         }
 473
 474         rc = fcntl(dht_socket6, F_GETFL, 0);
 475         if(rc < 0) {
 476             perror("F_GETFL");
 477             exit(1);
 478         }
 479
 480         rc = fcntl(dht_socket6, F_SETFL, (rc | O_NONBLOCK));
 481         if(rc < 0) {
 482             perror("F_SETFL");
 483             exit(1);
 484         }
 485     }
 486
 487     {
 488         int fd;
 489         unsigned int seed;
 490
 491         fd = open("/dev/urandom", O_RDONLY);
 492         if(fd < 0) {
 493             perror("open(random)");
 494             exit(1);
 495         }
 496
 497         rc = read(fd, myid, 20);
 498         if(rc < 20) {
 499             perror("open(random)");
 500             exit(1);
 501         }
 502
 503         rc = read(fd, &seed, sizeof(seed));
 504         srandom(seed);
 505
 506         close(fd);
 507     }
 508
 509     memcpy(my_v, "1:v4:JB\0\0", 9);
 510     have_v = 1;
 511
 512     if(!quiet)
 513         dht_debug = stdout;
 514
 515     i = optind;
 516
 517     if(argc < i + 1)
 518         goto usage;
 519
 520     port = atoi(argv[i++]);
 521     if(port <= 0 || port >= 0x10000)
 522         goto usage;
 523
 524     while(i < argc) {
 525         struct addrinfo hints, *info, *infop;
 526         memset(&hints, 0, sizeof(hints));
 527         hints.ai_socktype = SOCK_DGRAM;
 528         hints.ai_family = 0;
 529         if(dht_socket < 0)
 530             hints.ai_family = AF_INET6;
 531         else if(dht_socket6 < 0)
 532             hints.ai_family |= AF_INET;
 533         rc = getaddrinfo(argv[i], argv[i + 1], &hints, &info);
 534         if(rc != 0) {
 535             fprintf(stderr, "getaddrinfo: %s\n", gai_strerror(rc));
 536             exit(1);
 537         }
 538
 539         i++;
 540         if(i >= argc)
 541             goto usage;
 542
 543         infop = info;
 544         while(infop) {
 545             make_tid(ttid, "pn", 0);
 546             debugf("Sending ping.\n");
 547             send_ping(infop->ai_addr, infop->ai_addrlen, ttid, 4);
 548             infop = infop->ai_next;
 549         }
 550         freeaddrinfo(info);
 551
 552         i++;
 553     }
 554
 555     token_bucket_time = time(NULL);
 556     token_bucket_tokens = MAX_TOKEN_BUCKET_TOKENS;
 557
 558     while(1) {
 559         struct timeval tv;
 560         fd_set readfds;
 561         int rc;
 562
 563         if((dht_socket >= 0 && list_elements(&v4_confirmed) <= 16) ||
 564            (dht_socket6 >= 0 && list_elements(&v6_confirmed) <= 16))
 565             tv.tv_sec = 0;
 566         else
 567             tv.tv_sec = random() % 30;
 568         tv.tv_usec = random() % 1000000;
 569
 570         FD_ZERO(&readfds);
 571         if(dht_socket >= 0)
 572             FD_SET(dht_socket, &readfds);
 573         if(dht_socket6 >= 0)
 574             FD_SET(dht_socket6, &readfds);
 575
 576         if(dht_debug)
 577             debugf("%d+%d %d+%d\n",
 578                    list_elements(&v4_confirmed), list_elements(&v6_confirmed),
 579                    list_elements(&v4_new), list_elements(&v6_new));
 580
 581         rc = select(MAX(dht_socket, dht_socket6) + 1, &readfds, NULL, NULL,
 582                     &tv);
 583
 584         if(rc < 0) {
 585             if(errno != EINTR) {
 586                 perror("select");
 587                 sleep(1);
 588             }
 589         }
 590
 591         if(rc > 0) {
 592             int rc, message;
 593             unsigned char tid[16], id[20], info_hash[20], target[20];
 594             unsigned char buf[1536], nodes[256], nodes6[1024], token[128];
 595             int tid_len = 16, token_len = 128;
 596             int nodes_len = 256, nodes6_len = 1024;
 597             unsigned short port;
 598             unsigned char values[2048], values6[2048];
 599             int values_len = 2048, values6_len = 2048;
 600             int want, want4, want6;
 601             struct sockaddr_storage source_storage;
 602             struct sockaddr *source = (struct sockaddr*)&source_storage;
 603             socklen_t sourcelen = sizeof(source_storage);
 604             if(dht_socket >= 0 && FD_ISSET(dht_socket, &readfds)) {
 605                 rc = recvfrom(dht_socket, buf, 1536, 0, source, &sourcelen);
 606             } else if(dht_socket6 >= 0 && FD_ISSET(dht_socket6, &readfds)) {
 607                 rc = recvfrom(dht_socket6, buf, 1536, 0, source, &sourcelen);
 608             }
 609
 610             if(rc < 0 || sourcelen > sizeof(struct sockaddr_storage))
 611                 goto dontread;
 612
 613             if(is_martian(source))
 614                 goto dontread;
 615
 616             /* There's a bug in parse_message -- it will happily overflow the
 617                buffer if it's not NUL-terminated.  For now, put a NUL at the
 618                end of buffers. */
 619
 620             if(rc < 1536) {
 621                 buf[rc] = '\0';
 622             } else {
 623                 debugf("Overlong message.\n");
 624                 goto dontread;
 625             }
 626
 627             message = parse_message(buf, rc, tid, &tid_len, id, info_hash,
 628                                     target, &port, token, &token_len,
 629                                     nodes, &nodes_len, nodes6, &nodes6_len,
 630                                     values, &values_len, values6, &values6_len,
 631                                     &want);
 632
 633             if(id_cmp(id, myid) == 0) {
 634                 debugf("Received message from self.\n");
 635                 goto dontread;
 636             }
 637
 638             if(message > REPLY) {
 639                 /* Rate limit requests. */
 640                 if(!token_bucket()) {
 641                     debugf("Dropping request due to rate limiting.\n");
 642                     goto dontread;
 643                 }
 644             }
 645
 646             if(want > 0) {
 647                 want4 = (want & WANT4);
 648                 want6 = (want & WANT6);
 649             } else {
 650                 want4 = source->sa_family == AF_INET;
 651                 want6 = source->sa_family == AF_INET6;
 652             }
 653
 654             switch(message) {
 655             case REPLY:
 656                 if(tid_len != 4) {
 657                     debugf("Broken node truncates transaction ids.\n");
 658                     goto dontread;
 659                 }
 660                 if(tid_match(tid, "pn", NULL)) {
 661                     debugf("Pong!\n");
 662                     new_node(id, source, sourcelen, 2);
 663                 } else if(tid_match(tid, "fn", NULL)) {
 664                     debugf("Nodes found!\n");
 665                     if(nodes_len % 26 != 0 || nodes6_len % 38 != 0) {
 666                         debugf("Unexpected length for node info!\n");
 667                     } else {
 668                         new_node(id, source, sourcelen, 2);
 669                         for(i = 0; i < nodes_len / 26; i++) {
 670                             unsigned char *ni = nodes + i * 26;
 671                             struct sockaddr_in sin;
 672                             if(id_cmp(ni, myid) == 0)
 673                                 continue;
 674                             memset(&sin, 0, sizeof(sin));
 675                             sin.sin_family = AF_INET;
 676                             memcpy(&sin.sin_addr, ni + 20, 4);
 677                             memcpy(&sin.sin_port, ni + 24, 2);
 678                             new_node(ni, (struct sockaddr*)&sin, sizeof(sin),
 679                                      0);
 680                         }
 681                         for(i = 0; i < nodes6_len / 38; i++) {
 682                             unsigned char *ni = nodes6 + i * 38;
 683                             struct sockaddr_in6 sin6;
 684                             if(id_cmp(ni, myid) == 0)
 685                                 continue;
 686                             memset(&sin6, 0, sizeof(sin6));
 687                             sin6.sin6_family = AF_INET6;
 688                             memcpy(&sin6.sin6_addr, ni + 20, 16);
 689                             memcpy(&sin6.sin6_port, ni + 36, 2);
 690                             new_node(ni, (struct sockaddr*)&sin6, sizeof(sin6),
 691                                      0);
 692                         }
 693                     }
 694                 } else {
 695                     debugf("Unexpected reply!\n");
 696                     goto dontread;
 697                 }
 698                 break;
 699             case PING:
 700                 debugf("Ping (%d)!\n", tid_len);
 701                 new_node(id, source, sourcelen, 1);
 702                 debugf("Sending pong.\n");
 703                 send_pong(source, sourcelen, tid, tid_len);
 704                 break;
 705
 706             case FIND_NODE:
 707             case GET_PEERS:
 708                 if(message == FIND_NODE)
 709                     debugf("Find node!\n");
 710                 else
 711                     debugf("Get peers!\n");
 712                 new_node(id, source, sourcelen, 1);
 713                 debugf("Sending nodes (%d).\n", want);
 714                 send_random_nodes(source, sourcelen,
 715                                   tid, tid_len, target, want);
 716                 break;
 717             case ANNOUNCE_PEER:
 718                 debugf("Announce peer!\n");
 719                 send_error(source, sourcelen, tid, tid_len,
 720                            203, "This node doesn't accept announces");
 721                 break;
 722             }
 723         }
 724
 725     dontread:
 726
 727         /* We need to be careful to avoid a positive feedback loop.  Make
 728            sure we send at most one packet each time through the select
 729            loop. */
 730
 731         if(dht_socket6 < 0)
 732             send4 = 1;
 733         else if(dht_socket < 0)
 734             send4 = 0;
 735         else
 736             send4 = random() % 2;
 737
 738         if(send4) {
 739             int want =
 740                 dht_socket6 >= 0 && list_free(&v6_new) > 8 ?
 741                 (WANT4 | WANT6) : 0;
 742             if(!list_empty(&v4_new))
 743                 send_request(&v4_new, 1, list_free(&v4_new) < 8, want);
 744             else if(!list_empty(&v4_confirmed))
 745                 send_request(&v4_confirmed, 0, 0, want);
 746         } else {
 747             int want =
 748                 dht_socket >= 0 && list_free(&v4_new) > 8 ?
 749                 (WANT4 | WANT6) : 0;
 750             if(!list_empty(&v6_new))
 751                 send_request(&v6_new, 1, list_free(&v6_new) < 8, want);
 752             else if(!list_empty(&v6_confirmed))
 753                 send_request(&v6_confirmed, 0, 0, want);
 754         }
 755     }
 756
 757     return 0;
 758
 759  usage:
 760     fprintf(stderr, "dht-bootstrap [-q] [-4] [-6] port [node port...]\n");
 761     exit(1);
 762 }
 763
 764 /* We could use a proper bencoding printer and parser, but the format of
 765    DHT messages is fairly stylised, so this seemed simpler. */
 766
 767 #define CHECK(offset, delta, size)                      \
 768     if(delta < 0 || offset + delta > size) goto fail
 769
 770 #define INC(offset, delta, size)                        \
 771     CHECK(offset, delta, size);                         \
 772     offset += delta
 773
 774 #define COPY(buf, offset, src, delta, size)             \
 775     CHECK(offset, delta, size);                         \
 776     memcpy(buf + offset, src, delta);                   \
 777     offset += delta;
 778
 779 #define ADD_V(buf, offset, size)                        \
 780     if(have_v) {                                        \
 781         COPY(buf, offset, my_v, sizeof(my_v), size);    \
 782     }
 783
 784 static int
 785 dht_send(const void *buf, size_t len, int flags,
 786          const struct sockaddr *sa, int salen)
 787 {
 788     int s;
 789
 790     if(salen == 0)
 791         abort();
 792
 793     if(sa->sa_family == AF_INET)
 794         s = dht_socket;
 795     else if(sa->sa_family == AF_INET6)
 796         s = dht_socket6;
 797     else
 798         s = -1;
 799
 800     if(s < 0) {
 801         errno = EAFNOSUPPORT;
 802         return -1;
 803     }
 804
 805     return sendto(s, buf, len, flags, sa, salen);
 806 }
 807
 808 int
 809 send_ping(struct sockaddr *sa, int salen,
 810           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:"); INC(i, rc, 512);
 815     COPY(buf, i, myid, 20, 512);
 816     rc = snprintf(buf + i, 512 - i, "e1:q4:ping1:t%d:", tid_len);
 817     INC(i, rc, 512);
 818     COPY(buf, i, tid, tid_len, 512);
 819     ADD_V(buf, i, 512);
 820     rc = snprintf(buf + i, 512 - i, "1:y1:qe"); INC(i, rc, 512);
 821     return dht_send(buf, i, 0, sa, salen);
 822
 823  fail:
 824     errno = ENOSPC;
 825     return -1;
 826 }
 827
 828 int
 829 send_pong(struct sockaddr *sa, int salen,
 830           const unsigned char *tid, int tid_len)
 831 {
 832     char buf[512];
 833     int i = 0, rc;
 834     rc = snprintf(buf + i, 512 - i, "d1:rd2:id20:"); INC(i, rc, 512);
 835     COPY(buf, i, myid, 20, 512);
 836     rc = snprintf(buf + i, 512 - i, "e1:t%d:", tid_len); INC(i, rc, 512);
 837     COPY(buf, i, tid, tid_len, 512);
 838     ADD_V(buf, i, 512);
 839     rc = snprintf(buf + i, 512 - i, "1:y1:re"); INC(i, rc, 512);
 840     return dht_send(buf, i, 0, sa, salen);
 841
 842  fail:
 843     errno = ENOSPC;
 844     return -1;
 845 }
 846
 847 int
 848 send_find_node(struct sockaddr *sa, int salen,
 849                const unsigned char *tid, int tid_len,
 850                const unsigned char *target, int want, int confirm)
 851 {
 852     char buf[512];
 853     int i = 0, rc;
 854     rc = snprintf(buf + i, 512 - i, "d1:ad2:id20:"); INC(i, rc, 512);
 855     COPY(buf, i, myid, 20, 512);
 856     rc = snprintf(buf + i, 512 - i, "6:target20:"); INC(i, rc, 512);
 857     COPY(buf, i, target, 20, 512);
 858     if(want > 0) {
 859         rc = snprintf(buf + i, 512 - i, "4:wantl%s%se",
 860                       (want & WANT4) ? "2:n4" : "",
 861                       (want & WANT6) ? "2:n6" : "");
 862         INC(i, rc, 512);
 863     }
 864     rc = snprintf(buf + i, 512 - i, "e1:q9:find_node1:t%d:", tid_len);
 865     INC(i, rc, 512);
 866     COPY(buf, i, tid, tid_len, 512);
 867     ADD_V(buf, i, 512);
 868     rc = snprintf(buf + i, 512 - i, "1:y1:qe"); INC(i, rc, 512);
 869     return dht_send(buf, i, confirm ? MSG_CONFIRM : 0, sa, salen);
 870
 871  fail:
 872     errno = ENOSPC;
 873     return -1;
 874 }
 875
 876 int
 877 send_nodes(struct sockaddr *sa, int salen,
 878            const unsigned char *tid, int tid_len,
 879            const unsigned char *nodes, int nodes_len,
 880            const unsigned char *nodes6, int nodes6_len)
 881 {
 882     char buf[2048];
 883     int i = 0, rc;
 884
 885     rc = snprintf(buf + i, 2048 - i, "d1:rd2:id20:"); INC(i, rc, 2048);
 886     COPY(buf, i, myid, 20, 2048);
 887     if(nodes_len > 0) {
 888         rc = snprintf(buf + i, 2048 - i, "5:nodes%d:", nodes_len);
 889         INC(i, rc, 2048);
 890         COPY(buf, i, nodes, nodes_len, 2048);
 891     }
 892     if(nodes6_len > 0) {
 893          rc = snprintf(buf + i, 2048 - i, "6:nodes6%d:", nodes6_len);
 894          INC(i, rc, 2048);
 895          COPY(buf, i, nodes6, nodes6_len, 2048);
 896     }
 897
 898     rc = snprintf(buf + i, 2048 - i, "e1:t%d:", tid_len); INC(i, rc, 2048);
 899     COPY(buf, i, tid, tid_len, 2048);
 900     ADD_V(buf, i, 2048);
 901     rc = snprintf(buf + i, 2048 - i, "1:y1:re"); INC(i, rc, 2048);
 902
 903     return dht_send(buf, i, 0, sa, salen);
 904
 905  fail:
 906     errno = ENOSPC;
 907     return -1;
 908 }
 909
 910 static int
 911 buffer_random_nodes(int af, unsigned char *nodes)
 912 {
 913     struct circular_list *list;
 914     struct sockaddr_storage ss;
 915     socklen_t sslen;
 916     unsigned char id[20];
 917     int n;
 918     int rc;
 919
 920     switch(af) {
 921     case AF_INET: list = &v4_confirmed; break;
 922     case AF_INET6: list = &v6_confirmed; break;
 923     default: abort();
 924     }
 925
 926     n = 0;
 927     while(n < 8) {
 928         rc = list_random(list, id, &ss, &sslen);
 929         if(rc < 1)
 930             break;
 931         switch(af) {
 932         case AF_INET: {
 933             struct sockaddr_in *sin = (struct sockaddr_in*)&ss;
 934             memcpy(nodes + n * 26, id, 20);
 935             memcpy(nodes + n * 26 + 20, &sin->sin_addr, 4);
 936             memcpy(nodes + n * 26 + 24, &sin->sin_port, 2);
 937             n++;
 938             break;
 939         }
 940         case AF_INET6: {
 941             struct sockaddr_in6 *sin6 = (struct sockaddr_in6*)&ss;
 942             memcpy(nodes + n * 38, id, 20);
 943             memcpy(nodes + n * 38 + 20, &sin6->sin6_addr, 16);
 944             memcpy(nodes + n * 38 + 36, &sin6->sin6_port, 2);
 945             n++;
 946             break;
 947         }
 948         default:
 949             abort();
 950         }
 951     }
 952     return n;
 953 }
 954
 955 int
 956 send_random_nodes(struct sockaddr *sa, int salen,
 957                   const unsigned char *tid, int tid_len,
 958                   const unsigned char *id, int want)
 959 {
 960     unsigned char nodes[8 * 26];
 961     unsigned char nodes6[8 * 38];
 962     int numnodes = 0, numnodes6 = 0;
 963
 964     if(want < 0)
 965         want = sa->sa_family == AF_INET ? WANT4 : WANT6;
 966
 967     if((want & WANT4))
 968         numnodes = buffer_random_nodes(AF_INET, nodes);
 969
 970     if((want & WANT6))
 971         numnodes6 = buffer_random_nodes(AF_INET6, nodes6);
 972
 973     return send_nodes(sa, salen, tid, tid_len,
 974                       nodes, numnodes * 26,
 975                       nodes6, numnodes6 * 38);
 976 }
 977
 978 static int
 979 send_error(struct sockaddr *sa, int salen,
 980            unsigned char *tid, int tid_len,
 981            int code, const char *message)
 982 {
 983     char buf[512];
 984     int i = 0, rc;
 985
 986     rc = snprintf(buf + i, 512 - i, "d1:eli%de%d:",
 987                   code, (int)strlen(message));
 988     INC(i, rc, 512);
 989     COPY(buf, i, message, (int)strlen(message), 512);
 990     rc = snprintf(buf + i, 512 - i, "e1:t%d:", tid_len); INC(i, rc, 512);
 991     COPY(buf, i, tid, tid_len, 512);
 992     ADD_V(buf, i, 512);
 993     rc = snprintf(buf + i, 512 - i, "1:y1:ee"); INC(i, rc, 512);
 994     return dht_send(buf, i, 0, sa, salen);
 995
 996  fail:
 997     errno = ENOSPC;
 998     return -1;
 999 }
1000
1001 #undef CHECK
1002 #undef INC
1003 #undef COPY
1004 #undef ADD_V
1005
1006 #ifndef HAVE_MEMMEM
1007 static void *
1008 memmem(const void *haystack, size_t haystacklen,
1009        const void *needle, size_t needlelen)
1010 {
1011     const char *h = haystack;
1012     const char *n = needle;
1013     size_t i;
1014
1015     /* size_t is unsigned */
1016     if(needlelen > haystacklen)
1017         return NULL;
1018
1019     for(i = 0; i <= haystacklen - needlelen; i++) {
1020         if(memcmp(h + i, n, needlelen) == 0)
1021             return (void*)(h + i);
1022     }
1023     return NULL;
1024 }
1025 #endif
1026
1027 static int
1028 parse_message(const unsigned char *buf, int buflen,
1029               unsigned char *tid_return, int *tid_len,
1030               unsigned char *id_return, unsigned char *info_hash_return,
1031               unsigned char *target_return, unsigned short *port_return,
1032               unsigned char *token_return, int *token_len,
1033               unsigned char *nodes_return, int *nodes_len,
1034               unsigned char *nodes6_return, int *nodes6_len,
1035               unsigned char *values_return, int *values_len,
1036               unsigned char *values6_return, int *values6_len,
1037               int *want_return)
1038 {
1039     const unsigned char *p;
1040
1041     /* This code will happily crash if the buffer is not NUL-terminated. */
1042     if(buf[buflen] != '\0') {
1043         debugf("Eek!  parse_message with unterminated buffer.\n");
1044         return -1;
1045     }
1046
1047 #define CHECK(ptr, len)                                                 \
1048     if(((unsigned char*)ptr) + (len) > (buf) + (buflen)) goto overflow;
1049
1050     if(tid_return) {
1051         p = memmem(buf, buflen, "1:t", 3);
1052         if(p) {
1053             long l;
1054             char *q;
1055             l = strtol((char*)p + 3, &q, 10);
1056             if(q && *q == ':' && l > 0 && l < *tid_len) {
1057                 CHECK(q + 1, l);
1058                 memcpy(tid_return, q + 1, l);
1059                 *tid_len = l;
1060             } else
1061                 *tid_len = 0;
1062         }
1063     }
1064     if(id_return) {
1065         p = memmem(buf, buflen, "2:id20:", 7);
1066         if(p) {
1067             CHECK(p + 7, 20);
1068             memcpy(id_return, p + 7, 20);
1069         } else {
1070             memset(id_return, 0, 20);
1071         }
1072     }
1073     if(info_hash_return) {
1074         p = memmem(buf, buflen, "9:info_hash20:", 14);
1075         if(p) {
1076             CHECK(p + 14, 20);
1077             memcpy(info_hash_return, p + 14, 20);
1078         } else {
1079             memset(info_hash_return, 0, 20);
1080         }
1081     }
1082     if(port_return) {
1083         p = memmem(buf, buflen, "porti", 5);
1084         if(p) {
1085             long l;
1086             char *q;
1087             l = strtol((char*)p + 5, &q, 10);
1088             if(q && *q == 'e' && l > 0 && l < 0x10000)
1089                 *port_return = l;
1090             else
1091                 *port_return = 0;
1092         } else
1093             *port_return = 0;
1094     }
1095     if(target_return) {
1096         p = memmem(buf, buflen, "6:target20:", 11);
1097         if(p) {
1098             CHECK(p + 11, 20);
1099             memcpy(target_return, p + 11, 20);
1100         } else {
1101             memset(target_return, 0, 20);
1102         }
1103     }
1104     if(token_return) {
1105         p = memmem(buf, buflen, "5:token", 7);
1106         if(p) {
1107             long l;
1108             char *q;
1109             l = strtol((char*)p + 7, &q, 10);
1110             if(q && *q == ':' && l > 0 && l < *token_len) {
1111                 CHECK(q + 1, l);
1112                 memcpy(token_return, q + 1, l);
1113                 *token_len = l;
1114             } else
1115                 *token_len = 0;
1116         } else
1117             *token_len = 0;
1118     }
1119
1120     if(nodes_len) {
1121         p = memmem(buf, buflen, "5:nodes", 7);
1122         if(p) {
1123             long l;
1124             char *q;
1125             l = strtol((char*)p + 7, &q, 10);
1126             if(q && *q == ':' && l > 0 && l < *nodes_len) {
1127                 CHECK(q + 1, l);
1128                 memcpy(nodes_return, q + 1, l);
1129                 *nodes_len = l;
1130             } else
1131                 *nodes_len = 0;
1132         } else
1133             *nodes_len = 0;
1134     }
1135
1136     if(nodes6_len) {
1137         p = memmem(buf, buflen, "6:nodes6", 8);
1138         if(p) {
1139             long l;
1140             char *q;
1141             l = strtol((char*)p + 8, &q, 10);
1142             if(q && *q == ':' && l > 0 && l < *nodes6_len) {
1143                 CHECK(q + 1, l);
1144                 memcpy(nodes6_return, q + 1, l);
1145                 *nodes6_len = l;
1146             } else
1147                 *nodes6_len = 0;
1148         } else
1149             *nodes6_len = 0;
1150     }
1151
1152     if(values_len || values6_len) {
1153         p = memmem(buf, buflen, "6:valuesl", 9);
1154         if(p) {
1155             int i = p - buf + 9;
1156             int j = 0, j6 = 0;
1157             while(1) {
1158                 long l;
1159                 char *q;
1160                 l = strtol((char*)buf + i, &q, 10);
1161                 if(q && *q == ':' && l > 0) {
1162                     CHECK(q + 1, l);
1163                     if(l == 6) {
1164                         if(j + l > *values_len)
1165                             continue;
1166                         i = q + 1 + l - (char*)buf;
1167                         memcpy((char*)values_return + j, q + 1, l);
1168                         j += l;
1169                     } else if(l == 18) {
1170                         if(j6 + l > *values6_len)
1171                             continue;
1172                         i = q + 1 + l - (char*)buf;
1173                         memcpy((char*)values6_return + j6, q + 1, l);
1174                         j6 += l;
1175                     } else {
1176                         debugf("Received weird value -- %d bytes.\n", (int)l);
1177                         i = q + 1 + l - (char*)buf;
1178                     }
1179                 } else {
1180                     break;
1181                 }
1182             }
1183             if(i >= buflen || buf[i] != 'e')
1184                 debugf("eek... unexpected end for values.\n");
1185             if(values_len)
1186                 *values_len = j;
1187             if(values6_len)
1188                 *values6_len = j6;
1189         } else {
1190             *values_len = 0;
1191             *values6_len = 0;
1192         }
1193     }
1194
1195     if(want_return) {
1196         p = memmem(buf, buflen, "4:wantl", 7);
1197         if(p) {
1198             int i = p - buf + 7;
1199             *want_return = 0;
1200             while(buf[i] > '0' && buf[i] <= '9' && buf[i + 1] == ':' &&
1201                   i + 2 + buf[i] - '0' < buflen) {
1202                 CHECK(buf + i + 2, buf[i] - '0');
1203                 if(buf[i] == '2' && memcmp(buf + i + 2, "n4", 2) == 0)
1204                     *want_return |= WANT4;
1205                 else if(buf[i] == '2' && memcmp(buf + i + 2, "n6", 2) == 0)
1206                     *want_return |= WANT6;
1207                 else
1208                     debugf("eek... unexpected want flag (%c)\n", buf[i]);
1209                 i += 2 + buf[i] - '0';
1210             }
1211             if(i >= buflen || buf[i] != 'e')
1212                 debugf("eek... unexpected end for want.\n");
1213         } else {
1214             *want_return = -1;
1215         }
1216     }
1217
1218 #undef CHECK
1219
1220     if(memmem(buf, buflen, "1:y1:r", 6))
1221         return REPLY;
1222     if(memmem(buf, buflen, "1:y1:e", 6))
1223         return ERROR;
1224     if(!memmem(buf, buflen, "1:y1:q", 6))
1225         return -1;
1226     if(memmem(buf, buflen, "1:q4:ping", 9))
1227         return PING;
1228     if(memmem(buf, buflen, "1:q9:find_node", 14))
1229        return FIND_NODE;
1230     if(memmem(buf, buflen, "1:q9:get_peers", 14))
1231         return GET_PEERS;
1232     if(memmem(buf, buflen, "1:q13:announce_peer", 19))
1233        return ANNOUNCE_PEER;
1234     return -1;
1235
1236  overflow:
1237     debugf("Truncated message.\n");
1238     return -1;
1239 }