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