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 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 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 *port = strdup(argv[i++]);
 435
 436     if (ipv4addr != NULL) {
 437         dht_socket = newSock(ipv4addr, port);
 438     }
 439     if (ipv6addr != NULL) {
 440         dht_socket6 = newSock(ipv6addr, port);
 441     }
 442
 443     arc4random_buf(myid, sizeof myid);
 444
 445     memcpy(my_v, "1:v4:JB\0\0", 9);
 446     have_v = 1;
 447
 448     if (!quiet)
 449         dht_debug = stdout;
 450
 451     int rc = 0;
 452     unsigned char ttid[4];
 453
 454     while (i < argc) {
 455         struct addrinfo hints, *info, *infop;
 456         memset(&hints, 0, sizeof(hints));
 457         hints.ai_socktype = SOCK_DGRAM;
 458         hints.ai_family = 0;
 459         if (dht_socket < 0)
 460             hints.ai_family = AF_INET6;
 461         else if (dht_socket6 < 0)
 462             hints.ai_family |= AF_INET;
 463         rc = getaddrinfo(argv[i], argv[i + 1], &hints, &info);
 464         if (rc != 0) {
 465             fprintf(stderr, "getaddrinfo: %s\n", gai_strerror(rc));
 466             exit(1);
 467         }
 468
 469         i++;
 470         if (i >= argc)
 471             goto usage;
 472
 473         infop = info;
 474         while (infop) {
 475             make_tid(ttid, "pn", 0);
 476             debugf("Sending ping.\n");
 477             send_ping(infop->ai_addr, infop->ai_addrlen, ttid, 4);
 478             infop = infop->ai_next;
 479         }
 480         freeaddrinfo(info);
 481
 482         i++;
 483     }
 484
 485     token_bucket_time = time(NULL);
 486     token_bucket_tokens = MAX_TOKEN_BUCKET_TOKENS;
 487     int send4 = 0;
 488     struct pollfd fds[2];
 489     fds[0].fd = dht_socket;
 490     fds[0].events = POLLIN;
 491     fds[1].fd = dht_socket6;
 492     fds[1].events = POLLIN;
 493
 494     while (1) {
 495         int tv_sec = 0;
 496         if ((dht_socket >= 0 && list_elements(&v4_confirmed) <= 16) ||
 497             (dht_socket6 >= 0 && list_elements(&v6_confirmed) <= 16))
 498             tv_sec = 0;
 499         else
 500             tv_sec = random() % 30;
 501         int tv_msec = random() % 1000;
 502
 503         if (dht_debug)
 504             debugf(
 505                 "%d+%d %d+%d\n",
 506                 list_elements(&v4_confirmed),
 507                 list_elements(&v6_confirmed),
 508                 list_elements(&v4_new),
 509                 list_elements(&v6_new));
 510
 511         int rc = poll(fds, 2, tv_sec * 1000 + tv_msec);
 512
 513         if (rc < 0) {
 514             perror("poll");
 515             sleep(1);
 516         }
 517
 518         if (rc > 0) {
 519             int rc = 0;
 520             int message;
 521             unsigned char tid[16], id[20], info_hash[20], target[20];
 522             unsigned char buf[1536], nodes[256], nodes6[1024], token[128];
 523             int tid_len = 16, token_len = 128;
 524             int nodes_len = 256, nodes6_len = 1024;
 525             unsigned short port;
 526             unsigned char values[2048], values6[2048];
 527             int values_len = 2048, values6_len = 2048;
 528             int want;
 529             struct sockaddr_storage source_storage;
 530             struct sockaddr *source = (struct sockaddr *)&source_storage;
 531             socklen_t sourcelen = sizeof(source_storage);
 532             if (fds[0].revents != 0) {
 533                 if ((fds[0].revents & (POLLERR | POLLNVAL)) > 0) {
 534                     fprintf(stderr, "error in fds[0]");
 535                     rc = -1;
 536                 } else {
 537                     rc = recvfrom(dht_socket, buf, 1536, 0, source, &sourcelen);
 538                 }
 539             } else if (fds[1].revents != 0) {
 540                 if ((fds[1].revents & (POLLERR | POLLNVAL)) > 0) {
 541                     fprintf(stderr, "error in fds[1]");
 542                     rc = -1;
 543                 } else {
 544                     rc = recvfrom(dht_socket6, buf, 1536, 0, source, &sourcelen);
 545                 };
 546             }
 547
 548             if (rc < 0 || sourcelen > sizeof(struct sockaddr_storage))
 549                 goto dontread;
 550
 551             if (is_martian(source))
 552                 goto dontread;
 553
 554             /* There's a bug in parse_message -- it will happily overflow the
 555                buffer if it's not NUL-terminated.  For now, put a NUL at the
 556                end of buffers. */
 557
 558             if (rc < 1536) {
 559                 buf[rc] = '\0';
 560             } else {
 561                 debugf("Overlong message.\n");
 562                 goto dontread;
 563             }
 564
 565             message = parse_message(
 566                 buf,
 567                 rc,
 568                 tid,
 569                 &tid_len,
 570                 id,
 571                 info_hash,
 572                 target,
 573                 &port,
 574                 token,
 575                 &token_len,
 576                 nodes,
 577                 &nodes_len,
 578                 nodes6,
 579                 &nodes6_len,
 580                 values,
 581                 &values_len,
 582                 values6,
 583                 &values6_len,
 584                 &want);
 585
 586             if (id_cmp(id, myid) == 0) {
 587                 debugf("Received message from self.\n");
 588                 goto dontread;
 589             }
 590
 591             if (message > REPLY) {
 592                 /* Rate limit requests. */
 593                 if (!token_bucket()) {
 594                     debugf("Dropping request due to rate limiting.\n");
 595                     goto dontread;
 596                 }
 597             }
 598
 599             switch (message) {
 600             case REPLY:
 601                 if (tid_len != 4) {
 602                     debugf("Broken node truncates transaction ids.\n");
 603                     goto dontread;
 604                 }
 605                 if (tid_match(tid, "pn", NULL)) {
 606                     debugf("Pong!\n");
 607                     new_node(id, source, sourcelen, 2);
 608                 } else if (tid_match(tid, "fn", NULL)) {
 609                     debugf("Nodes found!\n");
 610                     if (nodes_len % 26 != 0 || nodes6_len % 38 != 0) {
 611                         debugf("Unexpected length for node info!\n");
 612                     } else {
 613                         new_node(id, source, sourcelen, 2);
 614                         for (i = 0; i < nodes_len / 26; i++) {
 615                             unsigned char *ni = nodes + i * 26;
 616                             struct sockaddr_in sin;
 617                             if (id_cmp(ni, myid) == 0)
 618                                 continue;
 619                             memset(&sin, 0, sizeof(sin));
 620                             sin.sin_family = AF_INET;
 621                             memcpy(&sin.sin_addr, ni + 20, 4);
 622                             memcpy(&sin.sin_port, ni + 24, 2);
 623                             new_node(ni, (struct sockaddr *)&sin, sizeof(sin), 0);
 624                         }
 625                         for (i = 0; i < nodes6_len / 38; i++) {
 626                             unsigned char *ni = nodes6 + i * 38;
 627                             struct sockaddr_in6 sin6;
 628                             if (id_cmp(ni, myid) == 0)
 629                                 continue;
 630                             memset(&sin6, 0, sizeof(sin6));
 631                             sin6.sin6_family = AF_INET6;
 632                             memcpy(&sin6.sin6_addr, ni + 20, 16);
 633                             memcpy(&sin6.sin6_port, ni + 36, 2);
 634                             new_node(ni, (struct sockaddr *)&sin6, sizeof(sin6), 0);
 635                         }
 636                     }
 637                 } else {
 638                     debugf("Unexpected reply!\n");
 639                     goto dontread;
 640                 }
 641                 break;
 642             case PING:
 643                 debugf("Ping (%d)!\n", tid_len);
 644                 new_node(id, source, sourcelen, 1);
 645                 debugf("Sending pong.\n");
 646                 send_pong(source, sourcelen, tid, tid_len);
 647                 break;
 648
 649             case FIND_NODE:
 650             case GET_PEERS:
 651                 if (message == FIND_NODE)
 652                     debugf("Find node!\n");
 653                 else
 654                     debugf("Get peers!\n");
 655                 new_node(id, source, sourcelen, 1);
 656                 debugf("Sending nodes (%d).\n", want);
 657                 send_random_nodes(source, sourcelen, tid, tid_len, target, want);
 658                 break;
 659             case ANNOUNCE_PEER:
 660                 debugf("Announce peer!\n");
 661                 send_error(
 662                     source,
 663                     sourcelen,
 664                     tid,
 665                     tid_len,
 666                     203,
 667                     "This node doesn't accept announces");
 668                 break;
 669             }
 670         }
 671
 672     dontread:
 673
 674         /* We need to be careful to avoid a positive feedback loop.  Make
 675            sure we send at most one packet each time through the select
 676            loop. */
 677
 678         if (dht_socket6 < 0)
 679             send4 = 1;
 680         else if (dht_socket < 0)
 681             send4 = 0;
 682         else
 683             send4 = random() % 2;
 684
 685         if (send4) {
 686             int want = dht_socket6 >= 0 && list_free(&v6_new) > 8 ? (WANT4 | WANT6) : 0;
 687             if (!list_empty(&v4_new))
 688                 send_request(&v4_new, 1, list_free(&v4_new) < 8, want);
 689             else if (!list_empty(&v4_confirmed))
 690                 send_request(&v4_confirmed, 0, 0, want);
 691         } else {
 692             int want = dht_socket >= 0 && list_free(&v4_new) > 8 ? (WANT4 | WANT6) : 0;
 693             if (!list_empty(&v6_new))
 694                 send_request(&v6_new, 1, list_free(&v6_new) < 8, want);
 695             else if (!list_empty(&v6_confirmed))
 696                 send_request(&v6_confirmed, 0, 0, want);
 697         }
 698     }
 699
 700     return 0;
 701
 702 usage:
 703     fprintf(stderr, "dht-bootstrap [-q] [-4 ADDR4] [-6 ADDR6] port [node port...]\n");
 704     exit(1);
 705 }
 706
 707 /* We could use a proper bencoding printer and parser, but the format of
 708    DHT messages is fairly stylised, so this seemed simpler. */
 709
 710 #define CHECK(offset, delta, size)                                                     \
 711     if (delta < 0 || offset + delta > size)                                            \
 712     goto fail
 713
 714 #define INC(offset, delta, size)                                                       \
 715     CHECK(offset, delta, size);                                                        \
 716     offset += delta
 717
 718 #define COPY(buf, offset, src, delta, size)                                            \
 719     CHECK(offset, delta, size);                                                        \
 720     memcpy(buf + offset, src, delta);                                                  \
 721     offset += delta;
 722
 723 #define ADD_V(buf, offset, size)                                                       \
 724     if (have_v) {                                                                      \
 725         COPY(buf, offset, my_v, sizeof(my_v), size);                                   \
 726     }
 727
 728 static int
 729 dht_send(const void *buf, size_t len, int flags, const struct sockaddr *sa, int salen)
 730 {
 731     int s;
 732
 733     if (salen == 0)
 734         abort();
 735
 736     if (sa->sa_family == AF_INET)
 737         s = dht_socket;
 738     else if (sa->sa_family == AF_INET6)
 739         s = dht_socket6;
 740     else
 741         s = -1;
 742
 743     if (s < 0) {
 744         errno = EAFNOSUPPORT;
 745         return -1;
 746     }
 747
 748     return sendto(s, buf, len, flags, sa, salen);
 749 }
 750
 751 int
 752 send_ping(struct sockaddr *sa, int salen, const unsigned char *tid, int tid_len)
 753 {
 754     char buf[512];
 755     int i = 0, rc;
 756     rc = snprintf(buf + i, 512 - i, "d1:ad2:id20:");
 757     INC(i, rc, 512);
 758     COPY(buf, i, myid, 20, 512);
 759     rc = snprintf(buf + i, 512 - i, "e1:q4:ping1:t%d:", tid_len);
 760     INC(i, rc, 512);
 761     COPY(buf, i, tid, tid_len, 512);
 762     ADD_V(buf, i, 512);
 763     rc = snprintf(buf + i, 512 - i, "1:y1:qe");
 764     INC(i, rc, 512);
 765     return dht_send(buf, i, 0, sa, salen);
 766
 767 fail:
 768     errno = ENOSPC;
 769     return -1;
 770 }
 771
 772 int
 773 send_pong(struct sockaddr *sa, int salen, const unsigned char *tid, int tid_len)
 774 {
 775     char buf[512];
 776     int i = 0, rc;
 777     rc = snprintf(buf + i, 512 - i, "d1:rd2:id20:");
 778     INC(i, rc, 512);
 779     COPY(buf, i, myid, 20, 512);
 780     rc = snprintf(buf + i, 512 - i, "e1:t%d:", tid_len);
 781     INC(i, rc, 512);
 782     COPY(buf, i, tid, tid_len, 512);
 783     ADD_V(buf, i, 512);
 784     rc = snprintf(buf + i, 512 - i, "1:y1:re");
 785     INC(i, rc, 512);
 786     return dht_send(buf, i, 0, sa, salen);
 787
 788 fail:
 789     errno = ENOSPC;
 790     return -1;
 791 }
 792
 793 int
 794 send_find_node(
 795     struct sockaddr *sa,
 796     int salen,
 797     const unsigned char *tid,
 798     int tid_len,
 799     const unsigned char *target,
 800     int want)
 801 {
 802     char buf[512];
 803     int i = 0, rc;
 804     rc = snprintf(buf + i, 512 - i, "d1:ad2:id20:");
 805     INC(i, rc, 512);
 806     COPY(buf, i, myid, 20, 512);
 807     rc = snprintf(buf + i, 512 - i, "6:target20:");
 808     INC(i, rc, 512);
 809     COPY(buf, i, target, 20, 512);
 810     if (want > 0) {
 811         rc = snprintf(
 812             buf + i,
 813             512 - i,
 814             "4:wantl%s%se",
 815             (want & WANT4) ? "2:n4" : "",
 816             (want & WANT6) ? "2:n6" : "");
 817         INC(i, rc, 512);
 818     }
 819     rc = snprintf(buf + i, 512 - i, "e1:q9:find_node1:t%d:", tid_len);
 820     INC(i, rc, 512);
 821     COPY(buf, i, tid, tid_len, 512);
 822     ADD_V(buf, i, 512);
 823     rc = snprintf(buf + i, 512 - i, "1:y1:qe");
 824     INC(i, rc, 512);
 825     return dht_send(buf, i, 0, sa, salen);
 826
 827 fail:
 828     errno = ENOSPC;
 829     return -1;
 830 }
 831
 832 int
 833 send_nodes(
 834     struct sockaddr *sa,
 835     int salen,
 836     const unsigned char *tid,
 837     int tid_len,
 838     const unsigned char *nodes,
 839     int nodes_len,
 840     const unsigned char *nodes6,
 841     int nodes6_len)
 842 {
 843     char buf[2048];
 844     int i = 0, rc;
 845
 846     rc = snprintf(buf + i, 2048 - i, "d1:rd2:id20:");
 847     INC(i, rc, 2048);
 848     COPY(buf, i, myid, 20, 2048);
 849     if (nodes_len > 0) {
 850         rc = snprintf(buf + i, 2048 - i, "5:nodes%d:", nodes_len);
 851         INC(i, rc, 2048);
 852         COPY(buf, i, nodes, nodes_len, 2048);
 853     }
 854     if (nodes6_len > 0) {
 855         rc = snprintf(buf + i, 2048 - i, "6:nodes6%d:", nodes6_len);
 856         INC(i, rc, 2048);
 857         COPY(buf, i, nodes6, nodes6_len, 2048);
 858     }
 859
 860     rc = snprintf(buf + i, 2048 - i, "e1:t%d:", tid_len);
 861     INC(i, rc, 2048);
 862     COPY(buf, i, tid, tid_len, 2048);
 863     ADD_V(buf, i, 2048);
 864     rc = snprintf(buf + i, 2048 - i, "1:y1:re");
 865     INC(i, rc, 2048);
 866
 867     return dht_send(buf, i, 0, sa, salen);
 868
 869 fail:
 870     errno = ENOSPC;
 871     return -1;
 872 }
 873
 874 static int
 875 buffer_random_nodes(int af, unsigned char *nodes)
 876 {
 877     struct circular_list *list;
 878     struct sockaddr_storage ss;
 879     socklen_t sslen;
 880     unsigned char id[20];
 881     int n;
 882     int rc;
 883
 884     switch (af) {
 885     case AF_INET:
 886         list = &v4_confirmed;
 887         break;
 888     case AF_INET6:
 889         list = &v6_confirmed;
 890         break;
 891     default:
 892         abort();
 893     }
 894
 895     n = 0;
 896     while (n < 8) {
 897         rc = list_random(list, id, &ss, &sslen);
 898         if (rc < 1)
 899             break;
 900         switch (af) {
 901         case AF_INET: {
 902             struct sockaddr_in *sin = (struct sockaddr_in *)&ss;
 903             memcpy(nodes + n * 26, id, 20);
 904             memcpy(nodes + n * 26 + 20, &sin->sin_addr, 4);
 905             memcpy(nodes + n * 26 + 24, &sin->sin_port, 2);
 906             n++;
 907             break;
 908         }
 909         case AF_INET6: {
 910             struct sockaddr_in6 *sin6 = (struct sockaddr_in6 *)&ss;
 911             memcpy(nodes + n * 38, id, 20);
 912             memcpy(nodes + n * 38 + 20, &sin6->sin6_addr, 16);
 913             memcpy(nodes + n * 38 + 36, &sin6->sin6_port, 2);
 914             n++;
 915             break;
 916         }
 917         default:
 918             abort();
 919         }
 920     }
 921     return n;
 922 }
 923
 924 int
 925 send_random_nodes(
 926     struct sockaddr *sa,
 927     int salen,
 928     const unsigned char *tid,
 929     int tid_len,
 930     const unsigned char *id,
 931     int want)
 932 {
 933     unsigned char nodes[8 * 26];
 934     unsigned char nodes6[8 * 38];
 935     int numnodes = 0, numnodes6 = 0;
 936
 937     if (want < 0)
 938         want = sa->sa_family == AF_INET ? WANT4 : WANT6;
 939
 940     if ((want & WANT4))
 941         numnodes = buffer_random_nodes(AF_INET, nodes);
 942
 943     if ((want & WANT6))
 944         numnodes6 = buffer_random_nodes(AF_INET6, nodes6);
 945
 946     return send_nodes(
 947         sa, salen, tid, tid_len, nodes, numnodes * 26, nodes6, numnodes6 * 38);
 948 }
 949
 950 static int
 951 send_error(
 952     struct sockaddr *sa,
 953     int salen,
 954     unsigned char *tid,
 955     int tid_len,
 956     int code,
 957     const char *message)
 958 {
 959     char buf[512];
 960     int i = 0, rc;
 961
 962     rc = snprintf(buf + i, 512 - i, "d1:eli%de%d:", code, (int)strlen(message));
 963     INC(i, rc, 512);
 964     COPY(buf, i, message, (int)strlen(message), 512);
 965     rc = snprintf(buf + i, 512 - i, "e1:t%d:", tid_len);
 966     INC(i, rc, 512);
 967     COPY(buf, i, tid, tid_len, 512);
 968     ADD_V(buf, i, 512);
 969     rc = snprintf(buf + i, 512 - i, "1:y1:ee");
 970     INC(i, rc, 512);
 971     return dht_send(buf, i, 0, sa, salen);
 972
 973 fail:
 974     errno = ENOSPC;
 975     return -1;
 976 }
 977
 978 #undef CHECK
 979 #undef INC
 980 #undef COPY
 981 #undef ADD_V
 982
 983 static int
 984 parse_message(
 985     const unsigned char *buf,
 986     int buflen,
 987     unsigned char *tid_return,
 988     int *tid_len,
 989     unsigned char *id_return,
 990     unsigned char *info_hash_return,
 991     unsigned char *target_return,
 992     unsigned short *port_return,
 993     unsigned char *token_return,
 994     int *token_len,
 995     unsigned char *nodes_return,
 996     int *nodes_len,
 997     unsigned char *nodes6_return,
 998     int *nodes6_len,
 999     unsigned char *values_return,
1000     int *values_len,
1001     unsigned char *values6_return,
1002     int *values6_len,
1003     int *want_return)
1004 {
1005     const unsigned char *p;
1006
1007     /* This code will happily crash if the buffer is not NUL-terminated. */
1008     if (buf[buflen] != '\0') {
1009         debugf("Eek!  parse_message with unterminated buffer.\n");
1010         return -1;
1011     }
1012
1013 #define CHECK(ptr, len)                                                                \
1014     if (((unsigned char *)ptr) + (len) > (buf) + (buflen))                             \
1015         goto overflow;
1016
1017     if (tid_return) {
1018         p = memmem(buf, buflen, "1:t", 3);
1019         if (p) {
1020             long l;
1021             char *q;
1022             l = strtol((char *)p + 3, &q, 10);
1023             if (q && *q == ':' && l > 0 && l < *tid_len) {
1024                 CHECK(q + 1, l);
1025                 memcpy(tid_return, q + 1, l);
1026                 *tid_len = l;
1027             } else
1028                 *tid_len = 0;
1029         }
1030     }
1031     if (id_return) {
1032         p = memmem(buf, buflen, "2:id20:", 7);
1033         if (p) {
1034             CHECK(p + 7, 20);
1035             memcpy(id_return, p + 7, 20);
1036         } else {
1037             memset(id_return, 0, 20);
1038         }
1039     }
1040     if (info_hash_return) {
1041         p = memmem(buf, buflen, "9:info_hash20:", 14);
1042         if (p) {
1043             CHECK(p + 14, 20);
1044             memcpy(info_hash_return, p + 14, 20);
1045         } else {
1046             memset(info_hash_return, 0, 20);
1047         }
1048     }
1049     if (port_return) {
1050         p = memmem(buf, buflen, "porti", 5);
1051         if (p) {
1052             long l;
1053             char *q;
1054             l = strtol((char *)p + 5, &q, 10);
1055             if (q && *q == 'e' && l > 0 && l < 0x10000)
1056                 *port_return = l;
1057             else
1058                 *port_return = 0;
1059         } else
1060             *port_return = 0;
1061     }
1062     if (target_return) {
1063         p = memmem(buf, buflen, "6:target20:", 11);
1064         if (p) {
1065             CHECK(p + 11, 20);
1066             memcpy(target_return, p + 11, 20);
1067         } else {
1068             memset(target_return, 0, 20);
1069         }
1070     }
1071     if (token_return) {
1072         p = memmem(buf, buflen, "5:token", 7);
1073         if (p) {
1074             long l;
1075             char *q;
1076             l = strtol((char *)p + 7, &q, 10);
1077             if (q && *q == ':' && l > 0 && l < *token_len) {
1078                 CHECK(q + 1, l);
1079                 memcpy(token_return, q + 1, l);
1080                 *token_len = l;
1081             } else
1082                 *token_len = 0;
1083         } else
1084             *token_len = 0;
1085     }
1086
1087     if (nodes_len) {
1088         p = memmem(buf, buflen, "5:nodes", 7);
1089         if (p) {
1090             long l;
1091             char *q;
1092             l = strtol((char *)p + 7, &q, 10);
1093             if (q && *q == ':' && l > 0 && l < *nodes_len) {
1094                 CHECK(q + 1, l);
1095                 memcpy(nodes_return, q + 1, l);
1096                 *nodes_len = l;
1097             } else
1098                 *nodes_len = 0;
1099         } else
1100             *nodes_len = 0;
1101     }
1102
1103     if (nodes6_len) {
1104         p = memmem(buf, buflen, "6:nodes6", 8);
1105         if (p) {
1106             long l;
1107             char *q;
1108             l = strtol((char *)p + 8, &q, 10);
1109             if (q && *q == ':' && l > 0 && l < *nodes6_len) {
1110                 CHECK(q + 1, l);
1111                 memcpy(nodes6_return, q + 1, l);
1112                 *nodes6_len = l;
1113             } else
1114                 *nodes6_len = 0;
1115         } else
1116             *nodes6_len = 0;
1117     }
1118
1119     if (values_len || values6_len) {
1120         p = memmem(buf, buflen, "6:valuesl", 9);
1121         if (p) {
1122             int i = p - buf + 9;
1123             int j = 0, j6 = 0;
1124             while (1) {
1125                 long l;
1126                 char *q;
1127                 l = strtol((char *)buf + i, &q, 10);
1128                 if (q && *q == ':' && l > 0) {
1129                     CHECK(q + 1, l);
1130                     if (l == 6) {
1131                         if (j + l > *values_len)
1132                             continue;
1133                         i = q + 1 + l - (char *)buf;
1134                         memcpy((char *)values_return + j, q + 1, l);
1135                         j += l;
1136                     } else if (l == 18) {
1137                         if (j6 + l > *values6_len)
1138                             continue;
1139                         i = q + 1 + l - (char *)buf;
1140                         memcpy((char *)values6_return + j6, q + 1, l);
1141                         j6 += l;
1142                     } else {
1143                         debugf("Received weird value -- %d bytes.\n", (int)l);
1144                         i = q + 1 + l - (char *)buf;
1145                     }
1146                 } else {
1147                     break;
1148                 }
1149             }
1150             if (i >= buflen || buf[i] != 'e')
1151                 debugf("eek... unexpected end for values.\n");
1152             if (values_len)
1153                 *values_len = j;
1154             if (values6_len)
1155                 *values6_len = j6;
1156         } else {
1157             *values_len = 0;
1158             *values6_len = 0;
1159         }
1160     }
1161
1162     if (want_return) {
1163         p = memmem(buf, buflen, "4:wantl", 7);
1164         if (p) {
1165             int i = p - buf + 7;
1166             *want_return = 0;
1167             while (buf[i] > '0' && buf[i] <= '9' && buf[i + 1] == ':' &&
1168                    i + 2 + buf[i] - '0' < buflen) {
1169                 CHECK(buf + i + 2, buf[i] - '0');
1170                 if (buf[i] == '2' && memcmp(buf + i + 2, "n4", 2) == 0)
1171                     *want_return |= WANT4;
1172                 else if (buf[i] == '2' && memcmp(buf + i + 2, "n6", 2) == 0)
1173                     *want_return |= WANT6;
1174                 else
1175                     debugf("eek... unexpected want flag (%c)\n", buf[i]);
1176                 i += 2 + buf[i] - '0';
1177             }
1178             if (i >= buflen || buf[i] != 'e')
1179                 debugf("eek... unexpected end for want.\n");
1180         } else {
1181             *want_return = -1;
1182         }
1183     }
1184
1185 #undef CHECK
1186
1187     if (memmem(buf, buflen, "1:y1:r", 6))
1188         return REPLY;
1189     if (memmem(buf, buflen, "1:y1:e", 6))
1190         return ERROR;
1191     if (!memmem(buf, buflen, "1:y1:q", 6))
1192         return -1;
1193     if (memmem(buf, buflen, "1:q4:ping", 9))
1194         return PING;
1195     if (memmem(buf, buflen, "1:q9:find_node", 14))
1196         return FIND_NODE;
1197     if (memmem(buf, buflen, "1:q9:get_peers", 14))
1198         return GET_PEERS;
1199     if (memmem(buf, buflen, "1:q13:announce_peer", 19))
1200         return ANNOUNCE_PEER;
1201     return -1;
1202
1203 overflow:
1204     debugf("Truncated message.\n");
1205     return -1;
1206 }