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