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