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