dht-bootstrap.c

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