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