dht-bootstrap.c

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