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