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