1/* 2Copyright (c) 2009-2011 by Juliusz Chroboczek 3 4Permission is hereby granted, free of charge, to any person obtaining a copy 5of this software and associated documentation files (the "Software"), to deal 6in the Software without restriction, including without limitation the rights 7to use, copy, modify, merge, publish, distribute, sublicense, and/or sell 8copies of the Software, and to permit persons to whom the Software is 9furnished to do so, subject to the following conditions: 10 11The above copyright notice and this permission notice shall be included in 12all copies or substantial portions of the Software. 13 14THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 15IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 16FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 17AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 18LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 19OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 20THE SOFTWARE. 21*/ 22 23/* Please, please, please. 24 25 You are welcome to integrate this code in your favourite Bittorrent 26 client. Please remember, however, that it is meant to be usable by 27 others, including myself. This means no C++, no relicensing, and no 28 gratuitious changes to the coding style. And please send back any 29 improvements to the author. */ 30 31/* For memmem. */ 32#define _GNU_SOURCE 33 34#include <stdio.h> 35#include <stdlib.h> 36#include <errno.h> 37#include <string.h> 38#include <stdarg.h> 39#include <unistd.h> 40#include <fcntl.h> 41#include <sys/time.h> 42 43#ifndef WIN32 44#include <arpa/inet.h> 45#include <sys/types.h> 46#include <sys/socket.h> 47#include <netinet/in.h> 48#else 49#include <w32api.h> 50#define WINVER WindowsXP 51#include <ws2tcpip.h> 52#endif 53 54#include "dht.h" 55 56#ifndef HAVE_MEMMEM 57#ifdef __GLIBC__ 58#define HAVE_MEMMEM 59#endif 60#endif 61 62#ifndef MSG_CONFIRM 63#define MSG_CONFIRM 0 64#endif 65 66#ifdef WIN32 67 68#define EAFNOSUPPORT WSAEAFNOSUPPORT 69static int 70set_nonblocking(int fd, int nonblocking) 71{ 72 int rc; 73 74 unsigned long mode = !!nonblocking; 75 rc = ioctlsocket(fd, FIONBIO, &mode); 76 if(rc != 0) 77 errno = WSAGetLastError(); 78 return (rc == 0 ? 0 : -1); 79} 80 81static int 82random(void) 83{ 84 return rand(); 85} 86extern const char *inet_ntop(int, const void *, char *, socklen_t); 87 88#else 89 90static int 91set_nonblocking(int fd, int nonblocking) 92{ 93 int rc; 94 rc = fcntl(fd, F_GETFL, 0); 95 if(rc < 0) 96 return -1; 97 98 rc = fcntl(fd, F_SETFL, nonblocking?(rc | O_NONBLOCK):(rc & ~O_NONBLOCK)); 99 if(rc < 0) 100 return -1; 101 102 return 0; 103} 104 105#endif 106 107/* We set sin_family to 0 to mark unused slots. */ 108#if AF_INET == 0 || AF_INET6 == 0 109#error You lose 110#endif 111 112#if defined(__STDC_VERSION__) && __STDC_VERSION__ >= 199901L 113/* nothing */ 114#elif defined(__GNUC__) 115#define inline __inline 116#if (__GNUC__ >= 3) 117#define restrict __restrict 118#else 119#define restrict /**/ 120#endif 121#else 122#define inline /**/ 123#define restrict /**/ 124#endif 125 126#define MAX(x, y) ((x) >= (y) ? (x) : (y)) 127#define MIN(x, y) ((x) <= (y) ? (x) : (y)) 128 129struct node { 130 unsigned char id[20]; 131 struct sockaddr_storage ss; 132 int sslen; 133 time_t time; /* time of last message received */ 134 time_t reply_time; /* time of last correct reply received */ 135 time_t pinged_time; /* time of last request */ 136 int pinged; /* how many requests we sent since last reply */ 137 struct node *next; 138}; 139 140struct bucket { 141 int af; 142 unsigned char first[20]; 143 int count; /* number of nodes */ 144 int time; /* time of last reply in this bucket */ 145 struct node *nodes; 146 struct sockaddr_storage cached; /* the address of a likely candidate */ 147 int cachedlen; 148 struct bucket *next; 149}; 150 151struct search_node { 152 unsigned char id[20]; 153 struct sockaddr_storage ss; 154 int sslen; 155 time_t request_time; /* the time of the last unanswered request */ 156 time_t reply_time; /* the time of the last reply */ 157 int pinged; 158 unsigned char token[40]; 159 int token_len; 160 int replied; /* whether we have received a reply */ 161 int acked; /* whether they acked our announcement */ 162}; 163 164/* When performing a search, we search for up to SEARCH_NODES closest nodes 165 to the destination, and use the additional ones to backtrack if any of 166 the target 8 turn out to be dead. */ 167#define SEARCH_NODES 14 168 169struct search { 170 unsigned short tid; 171 int af; 172 time_t step_time; /* the time of the last search_step */ 173 unsigned char id[20]; 174 unsigned short port; /* 0 for pure searches */ 175 int done; 176 struct search_node nodes[SEARCH_NODES]; 177 int numnodes; 178 struct search *next; 179}; 180 181struct peer { 182 time_t time; 183 unsigned char ip[16]; 184 unsigned short len; 185 unsigned short port; 186}; 187 188/* The maximum number of peers we store for a given hash. */ 189#ifndef DHT_MAX_PEERS 190#define DHT_MAX_PEERS 2048 191#endif 192 193/* The maximum number of hashes we're willing to track. */ 194#ifndef DHT_MAX_HASHES 195#define DHT_MAX_HASHES 16384 196#endif 197 198/* The maximum number of searches we keep data about. */ 199#ifndef DHT_MAX_SEARCHES 200#define DHT_MAX_SEARCHES 1024 201#endif 202 203/* The time after which we consider a search to be expirable. */ 204#ifndef DHT_SEARCH_EXPIRE_TIME 205#define DHT_SEARCH_EXPIRE_TIME (62 * 60) 206#endif 207 208struct storage { 209 unsigned char id[20]; 210 int numpeers, maxpeers; 211 struct peer *peers; 212 struct storage *next; 213}; 214 215static void flush_search_node(struct search_node *n, struct search *sr); 216 217static int send_ping(const struct sockaddr *sa, int salen, 218 const unsigned char *tid, int tid_len); 219static int send_pong(const struct sockaddr *sa, int salen, 220 const unsigned char *tid, int tid_len); 221static int send_find_node(const struct sockaddr *sa, int salen, 222 const unsigned char *tid, int tid_len, 223 const unsigned char *target, int want, int confirm); 224static int send_nodes_peers(const struct sockaddr *sa, int salen, 225 const unsigned char *tid, int tid_len, 226 const unsigned char *nodes, int nodes_len, 227 const unsigned char *nodes6, int nodes6_len, 228 int af, struct storage *st, 229 const unsigned char *token, int token_len); 230static int send_closest_nodes(const struct sockaddr *sa, int salen, 231 const unsigned char *tid, int tid_len, 232 const unsigned char *id, int want, 233 int af, struct storage *st, 234 const unsigned char *token, int token_len); 235static int send_get_peers(const struct sockaddr *sa, int salen, 236 unsigned char *tid, int tid_len, 237 unsigned char *infohash, int want, int confirm); 238static int send_announce_peer(const struct sockaddr *sa, int salen, 239 unsigned char *tid, int tid_len, 240 unsigned char *infohas, unsigned short port, 241 unsigned char *token, int token_len, int confirm); 242static int send_peer_announced(const struct sockaddr *sa, int salen, 243 unsigned char *tid, int tid_len); 244static int send_error(const struct sockaddr *sa, int salen, 245 unsigned char *tid, int tid_len, 246 int code, const char *message); 247 248#define ERROR 0 249#define REPLY 1 250#define PING 2 251#define FIND_NODE 3 252#define GET_PEERS 4 253#define ANNOUNCE_PEER 5 254 255#define WANT4 1 256#define WANT6 2 257 258static int parse_message(const unsigned char *buf, int buflen, 259 unsigned char *tid_return, int *tid_len, 260 unsigned char *id_return, 261 unsigned char *info_hash_return, 262 unsigned char *target_return, 263 unsigned short *port_return, 264 unsigned char *token_return, int *token_len, 265 unsigned char *nodes_return, int *nodes_len, 266 unsigned char *nodes6_return, int *nodes6_len, 267 unsigned char *values_return, int *values_len, 268 unsigned char *values6_return, int *values6_len, 269 int *want_return); 270 271static const unsigned char zeroes[20] = {0}; 272static const unsigned char ones[20] = { 273 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 274 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 275 0xFF, 0xFF, 0xFF, 0xFF 276}; 277static const unsigned char v4prefix[16] = { 278 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0xFF, 0xFF, 0, 0, 0, 0 279}; 280 281static int dht_socket = -1; 282static int dht_socket6 = -1; 283 284static time_t search_time; 285static time_t confirm_nodes_time; 286static time_t rotate_secrets_time; 287 288static unsigned char myid[20]; 289static int have_v = 0; 290static unsigned char my_v[9]; 291static unsigned char secret[8]; 292static unsigned char oldsecret[8]; 293 294static struct bucket *buckets = NULL; 295static struct bucket *buckets6 = NULL; 296static struct storage *storage; 297static int numstorage; 298 299static struct search *searches = NULL; 300static int numsearches; 301static unsigned short search_id; 302 303/* The maximum number of nodes that we snub. There is probably little 304 reason to increase this value. */ 305#ifndef DHT_MAX_BLACKLISTED 306#define DHT_MAX_BLACKLISTED 10 307#endif 308static struct sockaddr_storage blacklist[DHT_MAX_BLACKLISTED]; 309int next_blacklisted; 310 311static struct timeval now; 312static time_t mybucket_grow_time, mybucket6_grow_time; 313static time_t expire_stuff_time; 314 315#define MAX_TOKEN_BUCKET_TOKENS 400 316static time_t token_bucket_time; 317static int token_bucket_tokens; 318 319FILE *dht_debug = NULL; 320 321#ifdef __GNUC__ 322 __attribute__ ((format (printf, 1, 2))) 323#endif 324static void 325debugf(const char *format, ...) 326{ 327 va_list args; 328 va_start(args, format); 329 if(dht_debug) 330 vfprintf(dht_debug, format, args); 331 va_end(args); 332 fflush(dht_debug); 333} 334 335static void 336debug_printable(const unsigned char *buf, int buflen) 337{ 338 int i; 339 if(dht_debug) { 340 for(i = 0; i < buflen; i++) 341 putc(buf[i] >= 32 && buf[i] <= 126 ? buf[i] : '.', dht_debug); 342 } 343} 344 345static void 346print_hex(FILE *f, const unsigned char *buf, int buflen) 347{ 348 int i; 349 for(i = 0; i < buflen; i++) 350 fprintf(f, "%02x", buf[i]); 351} 352 353static int 354is_martian(const struct sockaddr *sa) 355{ 356 switch(sa->sa_family) { 357 case AF_INET: { 358 struct sockaddr_in *sin = (struct sockaddr_in*)sa; 359 const unsigned char *address = (const unsigned char*)&sin->sin_addr; 360 return sin->sin_port == 0 || 361 (address[0] == 0) || 362 (address[0] == 127) || 363 ((address[0] & 0xE0) == 0xE0); 364 } 365 case AF_INET6: { 366 struct sockaddr_in6 *sin6 = (struct sockaddr_in6*)sa; 367 const unsigned char *address = (const unsigned char*)&sin6->sin6_addr; 368 return sin6->sin6_port == 0 || 369 (address[0] == 0xFF) || 370 (address[0] == 0xFE && (address[1] & 0xC0) == 0x80) || 371 (memcmp(address, zeroes, 15) == 0 && 372 (address[15] == 0 || address[15] == 1)) || 373 (memcmp(address, v4prefix, 12) == 0); 374 } 375 376 default: 377 return 0; 378 } 379} 380 381/* Forget about the ``XOR-metric''. An id is just a path from the 382 root of the tree, so bits are numbered from the start. */ 383 384static int 385id_cmp(const unsigned char *restrict id1, const unsigned char *restrict id2) 386{ 387 /* Memcmp is guaranteed to perform an unsigned comparison. */ 388 return memcmp(id1, id2, 20); 389} 390 391/* Find the lowest 1 bit in an id. */ 392static int 393lowbit(const unsigned char *id) 394{ 395 int i, j; 396 for(i = 19; i >= 0; i--) 397 if(id[i] != 0) 398 break; 399 400 if(i < 0) 401 return -1; 402 403 for(j = 7; j >= 0; j--) 404 if((id[i] & (0x80 >> j)) != 0) 405 break; 406 407 return 8 * i + j; 408} 409 410/* Find how many bits two ids have in common. */ 411static int 412common_bits(const unsigned char *id1, const unsigned char *id2) 413{ 414 int i, j; 415 unsigned char xor; 416 for(i = 0; i < 20; i++) { 417 if(id1[i] != id2[i]) 418 break; 419 } 420 421 if(i == 20) 422 return 160; 423 424 xor = id1[i] ^ id2[i]; 425 426 j = 0; 427 while((xor & 0x80) == 0) { 428 xor <<= 1; 429 j++; 430 } 431 432 return 8 * i + j; 433} 434 435/* Determine whether id1 or id2 is closer to ref */ 436static int 437xorcmp(const unsigned char *id1, const unsigned char *id2, 438 const unsigned char *ref) 439{ 440 int i; 441 for(i = 0; i < 20; i++) { 442 unsigned char xor1, xor2; 443 if(id1[i] == id2[i]) 444 continue; 445 xor1 = id1[i] ^ ref[i]; 446 xor2 = id2[i] ^ ref[i]; 447 if(xor1 < xor2) 448 return -1; 449 else 450 return 1; 451 } 452 return 0; 453} 454 455/* We keep buckets in a sorted linked list. A bucket b ranges from 456 b->first inclusive up to b->next->first exclusive. */ 457static int 458in_bucket(const unsigned char *id, struct bucket *b) 459{ 460 return id_cmp(b->first, id) <= 0 && 461 (b->next == NULL || id_cmp(id, b->next->first) < 0); 462} 463 464static struct bucket * 465find_bucket(unsigned const char *id, int af) 466{ 467 struct bucket *b = af == AF_INET ? buckets : buckets6; 468 469 if(b == NULL) 470 return NULL; 471 472 while(1) { 473 if(b->next == NULL) 474 return b; 475 if(id_cmp(id, b->next->first) < 0) 476 return b; 477 b = b->next; 478 } 479} 480 481static struct bucket * 482previous_bucket(struct bucket *b) 483{ 484 struct bucket *p = b->af == AF_INET ? buckets : buckets6; 485 486 if(b == p) 487 return NULL; 488 489 while(1) { 490 if(p->next == NULL) 491 return NULL; 492 if(p->next == b) 493 return p; 494 p = p->next; 495 } 496} 497 498/* Every bucket contains an unordered list of nodes. */ 499static struct node * 500find_node(const unsigned char *id, int af) 501{ 502 struct bucket *b = find_bucket(id, af); 503 struct node *n; 504 505 if(b == NULL) 506 return NULL; 507 508 n = b->nodes; 509 while(n) { 510 if(id_cmp(n->id, id) == 0) 511 return n; 512 n = n->next; 513 } 514 return NULL; 515} 516 517/* Return a random node in a bucket. */ 518static struct node * 519random_node(struct bucket *b) 520{ 521 struct node *n; 522 int nn; 523 524 if(b->count == 0) 525 return NULL; 526 527 nn = random() % b->count; 528 n = b->nodes; 529 while(nn > 0 && n) { 530 n = n->next; 531 nn--; 532 } 533 return n; 534} 535 536/* Return the middle id of a bucket. */ 537static int 538bucket_middle(struct bucket *b, unsigned char *id_return) 539{ 540 int bit1 = lowbit(b->first); 541 int bit2 = b->next ? lowbit(b->next->first) : -1; 542 int bit = MAX(bit1, bit2) + 1; 543 544 if(bit >= 160) 545 return -1; 546 547 memcpy(id_return, b->first, 20); 548 id_return[bit / 8] |= (0x80 >> (bit % 8)); 549 return 1; 550} 551 552/* Return a random id within a bucket. */ 553static int 554bucket_random(struct bucket *b, unsigned char *id_return) 555{ 556 int bit1 = lowbit(b->first); 557 int bit2 = b->next ? lowbit(b->next->first) : -1; 558 int bit = MAX(bit1, bit2) + 1; 559 int i; 560 561 if(bit >= 160) { 562 memcpy(id_return, b->first, 20); 563 return 1; 564 } 565 566 memcpy(id_return, b->first, bit / 8); 567 id_return[bit / 8] = b->first[bit / 8] & (0xFF00 >> (bit % 8)); 568 id_return[bit / 8] |= random() & 0xFF >> (bit % 8); 569 for(i = bit / 8 + 1; i < 20; i++) 570 id_return[i] = random() & 0xFF; 571 return 1; 572} 573 574/* Insert a new node into a bucket. */ 575static struct node * 576insert_node(struct node *node) 577{ 578 struct bucket *b = find_bucket(node->id, node->ss.ss_family); 579 580 if(b == NULL) 581 return NULL; 582 583 node->next = b->nodes; 584 b->nodes = node; 585 b->count++; 586 return node; 587} 588 589/* This is our definition of a known-good node. */ 590static int 591node_good(struct node *node) 592{ 593 return 594 node->pinged <= 2 && 595 node->reply_time >= now.tv_sec - 7200 && 596 node->time >= now.tv_sec - 900; 597} 598 599/* Our transaction-ids are 4-bytes long, with the first two bytes identi- 600 fying the kind of request, and the remaining two a sequence number in 601 host order. */ 602 603static void 604make_tid(unsigned char *tid_return, const char *prefix, unsigned short seqno) 605{ 606 tid_return[0] = prefix[0] & 0xFF; 607 tid_return[1] = prefix[1] & 0xFF; 608 memcpy(tid_return + 2, &seqno, 2); 609} 610 611static int 612tid_match(const unsigned char *tid, const char *prefix, 613 unsigned short *seqno_return) 614{ 615 if(tid[0] == (prefix[0] & 0xFF) && tid[1] == (prefix[1] & 0xFF)) { 616 if(seqno_return) 617 memcpy(seqno_return, tid + 2, 2); 618 return 1; 619 } else 620 return 0; 621} 622 623/* Every bucket caches the address of a likely node. Ping it. */ 624static int 625send_cached_ping(struct bucket *b) 626{ 627 unsigned char tid[4]; 628 int rc; 629 /* We set family to 0 when there's no cached node. */ 630 if(b->cached.ss_family == 0) 631 return 0; 632 633 debugf("Sending ping to cached node.\n"); 634 make_tid(tid, "pn", 0); 635 rc = send_ping((struct sockaddr*)&b->cached, b->cachedlen, tid, 4); 636 b->cached.ss_family = 0; 637 b->cachedlen = 0; 638 return rc; 639} 640 641/* Called whenever we send a request to a node, increases the ping count 642 and, if that reaches 3, sends a ping to a new candidate. */ 643static void 644pinged(struct node *n, struct bucket *b) 645{ 646 n->pinged++; 647 n->pinged_time = now.tv_sec; 648 if(n->pinged >= 3) 649 send_cached_ping(b ? b : find_bucket(n->id, n->ss.ss_family)); 650} 651 652/* The internal blacklist is an LRU cache of nodes that have sent 653 incorrect messages. */ 654static void 655blacklist_node(const unsigned char *id, const struct sockaddr *sa, int salen) 656{ 657 int i; 658 659 debugf("Blacklisting broken node.\n"); 660 661 if(id) { 662 struct node *n; 663 struct search *sr; 664 /* Make the node easy to discard. */ 665 n = find_node(id, sa->sa_family); 666 if(n) { 667 n->pinged = 3; 668 pinged(n, NULL); 669 } 670 /* Discard it from any searches in progress. */ 671 sr = searches; 672 while(sr) { 673 for(i = 0; i < sr->numnodes; i++) 674 if(id_cmp(sr->nodes[i].id, id) == 0) 675 flush_search_node(&sr->nodes[i], sr); 676 sr = sr->next; 677 } 678 } 679 /* And make sure we don't hear from it again. */ 680 memcpy(&blacklist[next_blacklisted], sa, salen); 681 next_blacklisted = (next_blacklisted + 1) % DHT_MAX_BLACKLISTED; 682} 683 684static int 685node_blacklisted(const struct sockaddr *sa, int salen) 686{ 687 int i; 688 689 if((unsigned)salen > sizeof(struct sockaddr_storage)) 690 abort(); 691 692 if(dht_blacklisted(sa, salen)) 693 return 1; 694 695 for(i = 0; i < DHT_MAX_BLACKLISTED; i++) { 696 if(memcmp(&blacklist[i], sa, salen) == 0) 697 return 1; 698 } 699 700 return 0; 701} 702 703/* Split a bucket into two equal parts. */ 704static struct bucket * 705split_bucket(struct bucket *b) 706{ 707 struct bucket *new; 708 struct node *nodes; 709 int rc; 710 unsigned char new_id[20]; 711 712 rc = bucket_middle(b, new_id); 713 if(rc < 0) 714 return NULL; 715 716 new = calloc(1, sizeof(struct bucket)); 717 if(new == NULL) 718 return NULL; 719 720 new->af = b->af; 721 722 send_cached_ping(b); 723 724 memcpy(new->first, new_id, 20); 725 new->time = b->time; 726 727 nodes = b->nodes; 728 b->nodes = NULL; 729 b->count = 0; 730 new->next = b->next; 731 b->next = new; 732 while(nodes) { 733 struct node *n; 734 n = nodes; 735 nodes = nodes->next; 736 insert_node(n); 737 } 738 return b; 739} 740 741/* We just learnt about a node, not necessarily a new one. Confirm is 1 if 742 the node sent a message, 2 if it sent us a reply. */ 743static struct node * 744new_node(const unsigned char *id, const struct sockaddr *sa, int salen, 745 int confirm) 746{ 747 struct bucket *b = find_bucket(id, sa->sa_family); 748 struct node *n; 749 int mybucket, split; 750 751 if(b == NULL) 752 return NULL; 753 754 if(id_cmp(id, myid) == 0) 755 return NULL; 756 757 if(is_martian(sa) || node_blacklisted(sa, salen)) 758 return NULL; 759 760 mybucket = in_bucket(myid, b); 761 762 if(confirm == 2) 763 b->time = now.tv_sec; 764 765 n = b->nodes; 766 while(n) { 767 if(id_cmp(n->id, id) == 0) { 768 if(confirm || n->time < now.tv_sec - 15 * 60) { 769 /* Known node. Update stuff. */ 770 memcpy((struct sockaddr*)&n->ss, sa, salen); 771 if(confirm) 772 n->time = now.tv_sec; 773 if(confirm >= 2) { 774 n->reply_time = now.tv_sec; 775 n->pinged = 0; 776 n->pinged_time = 0; 777 } 778 } 779 return n; 780 } 781 n = n->next; 782 } 783 784 /* New node. */ 785 786 if(mybucket) { 787 if(sa->sa_family == AF_INET) 788 mybucket_grow_time = now.tv_sec; 789 else 790 mybucket6_grow_time = now.tv_sec; 791 } 792 793 /* First, try to get rid of a known-bad node. */ 794 n = b->nodes; 795 while(n) { 796 if(n->pinged >= 3 && n->pinged_time < now.tv_sec - 15) { 797 memcpy(n->id, id, 20); 798 memcpy((struct sockaddr*)&n->ss, sa, salen); 799 n->time = confirm ? now.tv_sec : 0; 800 n->reply_time = confirm >= 2 ? now.tv_sec : 0; 801 n->pinged_time = 0; 802 n->pinged = 0; 803 return n; 804 } 805 n = n->next; 806 } 807 808 if(b->count >= 8) { 809 /* Bucket full. Ping a dubious node */ 810 int dubious = 0; 811 n = b->nodes; 812 while(n) { 813 /* Pick the first dubious node that we haven't pinged in the 814 last 15 seconds. This gives nodes the time to reply, but 815 tends to concentrate on the same nodes, so that we get rid 816 of bad nodes fast. */ 817 if(!node_good(n)) { 818 dubious = 1; 819 if(n->pinged_time < now.tv_sec - 15) { 820 unsigned char tid[4]; 821 debugf("Sending ping to dubious node.\n"); 822 make_tid(tid, "pn", 0); 823 send_ping((struct sockaddr*)&n->ss, n->sslen, 824 tid, 4); 825 n->pinged++; 826 n->pinged_time = now.tv_sec; 827 break; 828 } 829 } 830 n = n->next; 831 } 832 833 split = 0; 834 if(mybucket) { 835 if(!dubious) 836 split = 1; 837 /* If there's only one bucket, split eagerly. This is 838 incorrect unless there's more than 8 nodes in the DHT. */ 839 else if(b->af == AF_INET && buckets->next == NULL) 840 split = 1; 841 else if(b->af == AF_INET6 && buckets6->next == NULL) 842 split = 1; 843 } 844 845 if(split) { 846 debugf("Splitting.\n"); 847 b = split_bucket(b); 848 return new_node(id, sa, salen, confirm); 849 } 850 851 /* No space for this node. Cache it away for later. */ 852 if(confirm || b->cached.ss_family == 0) { 853 memcpy(&b->cached, sa, salen); 854 b->cachedlen = salen; 855 } 856 857 return NULL; 858 } 859 860 /* Create a new node. */ 861 n = calloc(1, sizeof(struct node)); 862 if(n == NULL) 863 return NULL; 864 memcpy(n->id, id, 20); 865 memcpy(&n->ss, sa, salen); 866 n->sslen = salen; 867 n->time = confirm ? now.tv_sec : 0; 868 n->reply_time = confirm >= 2 ? now.tv_sec : 0; 869 n->next = b->nodes; 870 b->nodes = n; 871 b->count++; 872 return n; 873} 874 875/* Called periodically to purge known-bad nodes. Note that we're very 876 conservative here: broken nodes in the table don't do much harm, we'll 877 recover as soon as we find better ones. */ 878static int 879expire_buckets(struct bucket *b) 880{ 881 while(b) { 882 struct node *n, *p; 883 int changed = 0; 884 885 while(b->nodes && b->nodes->pinged >= 4) { 886 n = b->nodes; 887 b->nodes = n->next; 888 b->count--; 889 changed = 1; 890 free(n); 891 } 892 893 p = b->nodes; 894 while(p) { 895 while(p->next && p->next->pinged >= 4) { 896 n = p->next; 897 p->next = n->next; 898 b->count--; 899 changed = 1; 900 free(n); 901 } 902 p = p->next; 903 } 904 905 if(changed) 906 send_cached_ping(b); 907 908 b = b->next; 909 } 910 expire_stuff_time = now.tv_sec + 120 + random() % 240; 911 return 1; 912} 913 914/* While a search is in progress, we don't necessarily keep the nodes being 915 walked in the main bucket table. A search in progress is identified by 916 a unique transaction id, a short (and hence small enough to fit in the 917 transaction id of the protocol packets). */ 918 919static struct search * 920find_search(unsigned short tid, int af) 921{ 922 struct search *sr = searches; 923 while(sr) { 924 if(sr->tid == tid && sr->af == af) 925 return sr; 926 sr = sr->next; 927 } 928 return NULL; 929} 930 931/* A search contains a list of nodes, sorted by decreasing distance to the 932 target. We just got a new candidate, insert it at the right spot or 933 discard it. */ 934 935static int 936insert_search_node(unsigned char *id, 937 const struct sockaddr *sa, int salen, 938 struct search *sr, int replied, 939 unsigned char *token, int token_len) 940{ 941 struct search_node *n; 942 int i, j; 943 944 if(sa->sa_family != sr->af) { 945 debugf("Attempted to insert node in the wrong family.\n"); 946 return 0; 947 } 948 949 for(i = 0; i < sr->numnodes; i++) { 950 if(id_cmp(id, sr->nodes[i].id) == 0) { 951 n = &sr->nodes[i]; 952 goto found; 953 } 954 if(xorcmp(id, sr->nodes[i].id, sr->id) < 0) 955 break; 956 } 957 958 if(i == SEARCH_NODES) 959 return 0; 960 961 if(sr->numnodes < SEARCH_NODES) 962 sr->numnodes++; 963 964 for(j = sr->numnodes - 1; j > i; j--) { 965 sr->nodes[j] = sr->nodes[j - 1]; 966 } 967 968 n = &sr->nodes[i]; 969 970 memset(n, 0, sizeof(struct search_node)); 971 memcpy(n->id, id, 20); 972 973found: 974 memcpy(&n->ss, sa, salen); 975 n->sslen = salen; 976 977 if(replied) { 978 n->replied = 1; 979 n->reply_time = now.tv_sec; 980 n->request_time = 0; 981 n->pinged = 0; 982 } 983 if(token) { 984 if(token_len >= 40) { 985 debugf("Eek! Overlong token.\n"); 986 } else { 987 memcpy(n->token, token, token_len); 988 n->token_len = token_len; 989 } 990 } 991 992 return 1; 993} 994 995static void 996flush_search_node(struct search_node *n, struct search *sr) 997{ 998 int i = n - sr->nodes, j; 999 for(j = i; j < sr->numnodes - 1; j++) 1000 sr->nodes[j] = sr->nodes[j + 1]; 1001 sr->numnodes--; 1002} 1003 1004static void 1005expire_searches(void) 1006{ 1007 struct search *sr = searches, *previous = NULL; 1008 1009 while(sr) { 1010 struct search *next = sr->next; 1011 if(sr->step_time < now.tv_sec - DHT_SEARCH_EXPIRE_TIME) { 1012 if(previous) 1013 previous->next = next; 1014 else 1015 searches = next; 1016 free(sr); 1017 numsearches--; 1018 } else { 1019 previous = sr; 1020 } 1021 sr = next; 1022 } 1023} 1024 1025/* This must always return 0 or 1, never -1, not even on failure (see below). */ 1026static int 1027search_send_get_peers(struct search *sr, struct search_node *n) 1028{ 1029 struct node *node; 1030 unsigned char tid[4]; 1031 1032 if(n == NULL) { 1033 int i; 1034 for(i = 0; i < sr->numnodes; i++) { 1035 if(sr->nodes[i].pinged < 3 && !sr->nodes[i].replied && 1036 sr->nodes[i].request_time < now.tv_sec - 15) 1037 n = &sr->nodes[i]; 1038 } 1039 } 1040 1041 if(!n || n->pinged >= 3 || n->replied || 1042 n->request_time >= now.tv_sec - 15) 1043 return 0; 1044 1045 debugf("Sending get_peers.\n"); 1046 make_tid(tid, "gp", sr->tid); 1047 send_get_peers((struct sockaddr*)&n->ss, n->sslen, tid, 4, sr->id, -1, 1048 n->reply_time >= now.tv_sec - 15); 1049 n->pinged++; 1050 n->request_time = now.tv_sec; 1051 /* If the node happens to be in our main routing table, mark it 1052 as pinged. */ 1053 node = find_node(n->id, n->ss.ss_family); 1054 if(node) pinged(node, NULL); 1055 return 1; 1056} 1057 1058/* When a search is in progress, we periodically call search_step to send 1059 further requests. */ 1060static void 1061search_step(struct search *sr, dht_callback *callback, void *closure) 1062{ 1063 int i, j; 1064 int all_done = 1; 1065 1066 /* Check if the first 8 live nodes have replied. */ 1067 j = 0; 1068 for(i = 0; i < sr->numnodes && j < 8; i++) { 1069 struct search_node *n = &sr->nodes[i]; 1070 if(n->pinged >= 3) 1071 continue; 1072 if(!n->replied) { 1073 all_done = 0; 1074 break; 1075 } 1076 j++; 1077 } 1078 1079 if(all_done) { 1080 if(sr->port == 0) { 1081 goto done; 1082 } else { 1083 int all_acked = 1; 1084 j = 0; 1085 for(i = 0; i < sr->numnodes && j < 8; i++) { 1086 struct search_node *n = &sr->nodes[i]; 1087 struct node *node; 1088 unsigned char tid[4]; 1089 if(n->pinged >= 3) 1090 continue; 1091 /* A proposed extension to the protocol consists in 1092 omitting the token when storage tables are full. While 1093 I don't think this makes a lot of sense -- just sending 1094 a positive reply is just as good --, let's deal with it. */ 1095 if(n->token_len == 0) 1096 n->acked = 1; 1097 if(!n->acked) { 1098 all_acked = 0; 1099 debugf("Sending announce_peer.\n"); 1100 make_tid(tid, "ap", sr->tid); 1101 send_announce_peer((struct sockaddr*)&n->ss, 1102 sizeof(struct sockaddr_storage), 1103 tid, 4, sr->id, sr->port, 1104 n->token, n->token_len, 1105 n->reply_time >= now.tv_sec - 15); 1106 n->pinged++; 1107 n->request_time = now.tv_sec; 1108 node = find_node(n->id, n->ss.ss_family); 1109 if(node) pinged(node, NULL); 1110 } 1111 j++; 1112 } 1113 if(all_acked) 1114 goto done; 1115 } 1116 sr->step_time = now.tv_sec; 1117 return; 1118 } 1119 1120 if(sr->step_time + 15 >= now.tv_sec) 1121 return; 1122 1123 j = 0; 1124 for(i = 0; i < sr->numnodes; i++) { 1125 j += search_send_get_peers(sr, &sr->nodes[i]); 1126 if(j >= 3) 1127 break; 1128 } 1129 sr->step_time = now.tv_sec; 1130 return; 1131 1132 done: 1133 sr->done = 1; 1134 if(callback) 1135 (*callback)(closure, 1136 sr->af == AF_INET ? 1137 DHT_EVENT_SEARCH_DONE : DHT_EVENT_SEARCH_DONE6, 1138 sr->id, NULL, 0); 1139 sr->step_time = now.tv_sec; 1140} 1141 1142static struct search * 1143new_search(void) 1144{ 1145 struct search *sr, *oldest = NULL; 1146 1147 /* Find the oldest done search */ 1148 sr = searches; 1149 while(sr) { 1150 if(sr->done && 1151 (oldest == NULL || oldest->step_time > sr->step_time)) 1152 oldest = sr; 1153 sr = sr->next; 1154 } 1155 1156 /* The oldest slot is expired. */ 1157 if(oldest && oldest->step_time < now.tv_sec - DHT_SEARCH_EXPIRE_TIME) 1158 return oldest; 1159 1160 /* Allocate a new slot. */ 1161 if(numsearches < DHT_MAX_SEARCHES) { 1162 sr = calloc(1, sizeof(struct search)); 1163 if(sr != NULL) { 1164 sr->next = searches; 1165 searches = sr; 1166 numsearches++; 1167 return sr; 1168 } 1169 } 1170 1171 /* Oh, well, never mind. Reuse the oldest slot. */ 1172 return oldest; 1173} 1174 1175/* Insert the contents of a bucket into a search structure. */ 1176static void 1177insert_search_bucket(struct bucket *b, struct search *sr) 1178{ 1179 struct node *n; 1180 n = b->nodes; 1181 while(n) { 1182 insert_search_node(n->id, (struct sockaddr*)&n->ss, n->sslen, 1183 sr, 0, NULL, 0); 1184 n = n->next; 1185 } 1186} 1187 1188/* Start a search. If port is non-zero, perform an announce when the 1189 search is complete. */ 1190int 1191dht_search(const unsigned char *id, int port, int af, 1192 dht_callback *callback, void *closure) 1193{ 1194 struct search *sr; 1195 struct bucket *b = find_bucket(id, af); 1196 1197 if(b == NULL) { 1198 errno = EAFNOSUPPORT; 1199 return -1; 1200 } 1201 1202 sr = searches; 1203 while(sr) { 1204 if(sr->af == af && id_cmp(sr->id, id) == 0) 1205 break; 1206 sr = sr->next; 1207 } 1208 1209 if(sr) { 1210 /* We're reusing data from an old search. Reusing the same tid 1211 means that we can merge replies for both searches. */ 1212 int i; 1213 sr->done = 0; 1214 again: 1215 for(i = 0; i < sr->numnodes; i++) { 1216 struct search_node *n; 1217 n = &sr->nodes[i]; 1218 /* Discard any doubtful nodes. */ 1219 if(n->pinged >= 3 || n->reply_time < now.tv_sec - 7200) { 1220 flush_search_node(n, sr); 1221 goto again; 1222 } 1223 n->pinged = 0; 1224 n->token_len = 0; 1225 n->replied = 0; 1226 n->acked = 0; 1227 } 1228 } else { 1229 sr = new_search(); 1230 if(sr == NULL) { 1231 errno = ENOSPC; 1232 return -1; 1233 } 1234 sr->af = af; 1235 sr->tid = search_id++; 1236 sr->step_time = 0; 1237 memcpy(sr->id, id, 20); 1238 sr->done = 0; 1239 sr->numnodes = 0; 1240 } 1241 1242 sr->port = port; 1243 1244 insert_search_bucket(b, sr); 1245 1246 if(sr->numnodes < SEARCH_NODES) { 1247 struct bucket *p = previous_bucket(b); 1248 if(b->next) 1249 insert_search_bucket(b->next, sr); 1250 if(p) 1251 insert_search_bucket(p, sr); 1252 } 1253 if(sr->numnodes < SEARCH_NODES) 1254 insert_search_bucket(find_bucket(myid, af), sr); 1255 1256 search_step(sr, callback, closure); 1257 search_time = now.tv_sec; 1258 return 1; 1259} 1260 1261/* A struct storage stores all the stored peer addresses for a given info 1262 hash. */ 1263 1264static struct storage * 1265find_storage(const unsigned char *id) 1266{ 1267 struct storage *st = storage; 1268 1269 while(st) { 1270 if(id_cmp(id, st->id) == 0) 1271 break; 1272 st = st->next; 1273 } 1274 return st; 1275} 1276 1277static int 1278storage_store(const unsigned char *id, 1279 const struct sockaddr *sa, unsigned short port) 1280{ 1281 int i, len; 1282 struct storage *st; 1283 unsigned char *ip; 1284 1285 if(sa->sa_family == AF_INET) { 1286 struct sockaddr_in *sin = (struct sockaddr_in*)sa; 1287 ip = (unsigned char*)&sin->sin_addr; 1288 len = 4; 1289 } else if(sa->sa_family == AF_INET6) { 1290 struct sockaddr_in6 *sin6 = (struct sockaddr_in6*)sa; 1291 ip = (unsigned char*)&sin6->sin6_addr; 1292 len = 16; 1293 } else { 1294 return -1; 1295 } 1296 1297 st = find_storage(id); 1298 1299 if(st == NULL) { 1300 if(numstorage >= DHT_MAX_HASHES) 1301 return -1; 1302 st = calloc(1, sizeof(struct storage)); 1303 if(st == NULL) return -1; 1304 memcpy(st->id, id, 20); 1305 st->next = storage; 1306 storage = st; 1307 numstorage++; 1308 } 1309 1310 for(i = 0; i < st->numpeers; i++) { 1311 if(st->peers[i].port == port && st->peers[i].len == len && 1312 memcmp(st->peers[i].ip, ip, len) == 0) 1313 break; 1314 } 1315 1316 if(i < st->numpeers) { 1317 /* Already there, only need to refresh */ 1318 st->peers[i].time = now.tv_sec; 1319 return 0; 1320 } else { 1321 struct peer *p; 1322 if(i >= st->maxpeers) { 1323 /* Need to expand the array. */ 1324 struct peer *new_peers; 1325 int n; 1326 if(st->maxpeers >= DHT_MAX_PEERS) 1327 return 0; 1328 n = st->maxpeers == 0 ? 2 : 2 * st->maxpeers; 1329 n = MIN(n, DHT_MAX_PEERS); 1330 new_peers = realloc(st->peers, n * sizeof(struct peer)); 1331 if(new_peers == NULL) 1332 return -1; 1333 st->peers = new_peers; 1334 st->maxpeers = n; 1335 } 1336 p = &st->peers[st->numpeers++]; 1337 p->time = now.tv_sec; 1338 p->len = len; 1339 memcpy(p->ip, ip, len); 1340 p->port = port; 1341 return 1; 1342 } 1343} 1344 1345static int 1346expire_storage(void) 1347{ 1348 struct storage *st = storage, *previous = NULL; 1349 while(st) { 1350 int i = 0; 1351 while(i < st->numpeers) { 1352 if(st->peers[i].time < now.tv_sec - 32 * 60) { 1353 if(i != st->numpeers - 1) 1354 st->peers[i] = st->peers[st->numpeers - 1]; 1355 st->numpeers--; 1356 } else { 1357 i++; 1358 } 1359 } 1360 1361 if(st->numpeers == 0) { 1362 free(st->peers); 1363 if(previous) 1364 previous->next = st->next; 1365 else 1366 storage = st->next; 1367 free(st); 1368 if(previous) 1369 st = previous->next; 1370 else 1371 st = storage; 1372 numstorage--; 1373 if(numstorage < 0) { 1374 debugf("Eek... numstorage became negative.\n"); 1375 numstorage = 0; 1376 } 1377 } else { 1378 previous = st; 1379 st = st->next; 1380 } 1381 } 1382 return 1; 1383} 1384 1385static int 1386rotate_secrets(void) 1387{ 1388 int rc; 1389 1390 rotate_secrets_time = now.tv_sec + 900 + random() % 1800; 1391 1392 memcpy(oldsecret, secret, sizeof(secret)); 1393 rc = dht_random_bytes(secret, sizeof(secret)); 1394 1395 if(rc < 0) 1396 return -1; 1397 1398 return 1; 1399} 1400 1401#ifndef TOKEN_SIZE 1402#define TOKEN_SIZE 8 1403#endif 1404 1405static void 1406make_token(const struct sockaddr *sa, int old, unsigned char *token_return) 1407{ 1408 void *ip; 1409 int iplen; 1410 unsigned short port; 1411 1412 if(sa->sa_family == AF_INET) { 1413 struct sockaddr_in *sin = (struct sockaddr_in*)sa; 1414 ip = &sin->sin_addr; 1415 iplen = 4; 1416 port = htons(sin->sin_port); 1417 } else if(sa->sa_family == AF_INET6) { 1418 struct sockaddr_in6 *sin6 = (struct sockaddr_in6*)sa; 1419 ip = &sin6->sin6_addr; 1420 iplen = 16; 1421 port = htons(sin6->sin6_port); 1422 } else { 1423 abort(); 1424 } 1425 1426 dht_hash(token_return, TOKEN_SIZE, 1427 old ? oldsecret : secret, sizeof(secret), 1428 ip, iplen, (unsigned char*)&port, 2); 1429} 1430static int 1431token_match(const unsigned char *token, int token_len, 1432 const struct sockaddr *sa) 1433{ 1434 unsigned char t[TOKEN_SIZE]; 1435 if(token_len != TOKEN_SIZE) 1436 return 0; 1437 make_token(sa, 0, t); 1438 if(memcmp(t, token, TOKEN_SIZE) == 0) 1439 return 1; 1440 make_token(sa, 1, t); 1441 if(memcmp(t, token, TOKEN_SIZE) == 0) 1442 return 1; 1443 return 0; 1444} 1445 1446int 1447dht_nodes(int af, int *good_return, int *dubious_return, int *cached_return, 1448 int *incoming_return) 1449{ 1450 int good = 0, dubious = 0, cached = 0, incoming = 0; 1451 struct bucket *b = af == AF_INET ? buckets : buckets6; 1452 1453 while(b) { 1454 struct node *n = b->nodes; 1455 while(n) { 1456 if(node_good(n)) { 1457 good++; 1458 if(n->time > n->reply_time) 1459 incoming++; 1460 } else { 1461 dubious++; 1462 } 1463 n = n->next; 1464 } 1465 if(b->cached.ss_family > 0) 1466 cached++; 1467 b = b->next; 1468 } 1469 if(good_return) 1470 *good_return = good; 1471 if(dubious_return) 1472 *dubious_return = dubious; 1473 if(cached_return) 1474 *cached_return = cached; 1475 if(incoming_return) 1476 *incoming_return = incoming; 1477 return good + dubious; 1478} 1479 1480static void 1481dump_bucket(FILE *f, struct bucket *b) 1482{ 1483 struct node *n = b->nodes; 1484 fprintf(f, "Bucket "); 1485 print_hex(f, b->first, 20); 1486 fprintf(f, " count %d age %d%s%s:\n", 1487 b->count, (int)(now.tv_sec - b->time), 1488 in_bucket(myid, b) ? " (mine)" : "", 1489 b->cached.ss_family ? " (cached)" : ""); 1490 while(n) { 1491 char buf[512]; 1492 unsigned short port; 1493 fprintf(f, " Node "); 1494 print_hex(f, n->id, 20); 1495 if(n->ss.ss_family == AF_INET) { 1496 struct sockaddr_in *sin = (struct sockaddr_in*)&n->ss; 1497 inet_ntop(AF_INET, &sin->sin_addr, buf, 512); 1498 port = ntohs(sin->sin_port); 1499 } else if(n->ss.ss_family == AF_INET6) { 1500 struct sockaddr_in6 *sin6 = (struct sockaddr_in6*)&n->ss; 1501 inet_ntop(AF_INET6, &sin6->sin6_addr, buf, 512); 1502 port = ntohs(sin6->sin6_port); 1503 } else { 1504 snprintf(buf, 512, "unknown(%d)", n->ss.ss_family); 1505 port = 0; 1506 } 1507 1508 if(n->ss.ss_family == AF_INET6) 1509 fprintf(f, " [%s]:%d ", buf, port); 1510 else 1511 fprintf(f, " %s:%d ", buf, port); 1512 if(n->time != n->reply_time) 1513 fprintf(f, "age %ld, %ld", 1514 (long)(now.tv_sec - n->time), 1515 (long)(now.tv_sec - n->reply_time)); 1516 else 1517 fprintf(f, "age %ld", (long)(now.tv_sec - n->time)); 1518 if(n->pinged) 1519 fprintf(f, " (%d)", n->pinged); 1520 if(node_good(n)) 1521 fprintf(f, " (good)"); 1522 fprintf(f, "\n"); 1523 n = n->next; 1524 } 1525 1526} 1527 1528void 1529dht_dump_tables(FILE *f) 1530{ 1531 int i; 1532 struct bucket *b; 1533 struct storage *st = storage; 1534 struct search *sr = searches; 1535 1536 fprintf(f, "My id "); 1537 print_hex(f, myid, 20); 1538 fprintf(f, "\n"); 1539 1540 b = buckets; 1541 while(b) { 1542 dump_bucket(f, b); 1543 b = b->next; 1544 } 1545 1546 fprintf(f, "\n"); 1547 1548 b = buckets6; 1549 while(b) { 1550 dump_bucket(f, b); 1551 b = b->next; 1552 } 1553 1554 while(sr) { 1555 fprintf(f, "\nSearch%s id ", sr->af == AF_INET6 ? " (IPv6)" : ""); 1556 print_hex(f, sr->id, 20); 1557 fprintf(f, " age %d%s\n", (int)(now.tv_sec - sr->step_time), 1558 sr->done ? " (done)" : ""); 1559 for(i = 0; i < sr->numnodes; i++) { 1560 struct search_node *n = &sr->nodes[i]; 1561 fprintf(f, "Node %d id ", i); 1562 print_hex(f, n->id, 20); 1563 fprintf(f, " bits %d age ", common_bits(sr->id, n->id)); 1564 if(n->request_time) 1565 fprintf(f, "%d, ", (int)(now.tv_sec - n->request_time)); 1566 fprintf(f, "%d", (int)(now.tv_sec - n->reply_time)); 1567 if(n->pinged) 1568 fprintf(f, " (%d)", n->pinged); 1569 fprintf(f, "%s%s.\n", 1570 find_node(n->id, AF_INET) ? " (known)" : "", 1571 n->replied ? " (replied)" : ""); 1572 } 1573 sr = sr->next; 1574 } 1575 1576 while(st) { 1577 fprintf(f, "\nStorage "); 1578 print_hex(f, st->id, 20); 1579 fprintf(f, " %d/%d nodes:", st->numpeers, st->maxpeers); 1580 for(i = 0; i < st->numpeers; i++) { 1581 char buf[100]; 1582 if(st->peers[i].len == 4) { 1583 inet_ntop(AF_INET, st->peers[i].ip, buf, 100); 1584 } else if(st->peers[i].len == 16) { 1585 buf[0] = '['; 1586 inet_ntop(AF_INET6, st->peers[i].ip, buf + 1, 98); 1587 strcat(buf, "]"); 1588 } else { 1589 strcpy(buf, "???"); 1590 } 1591 fprintf(f, " %s:%u (%ld)", 1592 buf, st->peers[i].port, 1593 (long)(now.tv_sec - st->peers[i].time)); 1594 } 1595 st = st->next; 1596 } 1597 1598 fprintf(f, "\n\n"); 1599 fflush(f); 1600} 1601 1602int 1603dht_init(int s, int s6, const unsigned char *id, const unsigned char *v) 1604{ 1605 int rc; 1606 1607 if(dht_socket >= 0 || dht_socket6 >= 0 || buckets || buckets6) { 1608 errno = EBUSY; 1609 return -1; 1610 } 1611 1612 searches = NULL; 1613 numsearches = 0; 1614 1615 storage = NULL; 1616 numstorage = 0; 1617 1618 if(s >= 0) { 1619 buckets = calloc(sizeof(struct bucket), 1); 1620 if(buckets == NULL) 1621 return -1; 1622 buckets->af = AF_INET; 1623 1624 rc = set_nonblocking(s, 1); 1625 if(rc < 0) 1626 goto fail; 1627 } 1628 1629 if(s6 >= 0) { 1630 buckets6 = calloc(sizeof(struct bucket), 1); 1631 if(buckets6 == NULL) 1632 return -1; 1633 buckets6->af = AF_INET6; 1634 1635 rc = set_nonblocking(s6, 1); 1636 if(rc < 0) 1637 goto fail; 1638 } 1639 1640 memcpy(myid, id, 20); 1641 if(v) { 1642 memcpy(my_v, "1:v4:", 5); 1643 memcpy(my_v + 5, v, 4); 1644 have_v = 1; 1645 } else { 1646 have_v = 0; 1647 } 1648 1649 gettimeofday(&now, NULL); 1650 1651 mybucket_grow_time = now.tv_sec; 1652 mybucket6_grow_time = now.tv_sec; 1653 confirm_nodes_time = now.tv_sec + random() % 3; 1654 1655 search_id = random() & 0xFFFF; 1656 search_time = 0; 1657 1658 next_blacklisted = 0; 1659 1660 token_bucket_time = now.tv_sec; 1661 token_bucket_tokens = MAX_TOKEN_BUCKET_TOKENS; 1662 1663 memset(secret, 0, sizeof(secret)); 1664 rc = rotate_secrets(); 1665 if(rc < 0) 1666 goto fail; 1667 1668 dht_socket = s; 1669 dht_socket6 = s6; 1670 1671 expire_buckets(buckets); 1672 expire_buckets(buckets6); 1673 1674 return 1; 1675 1676 fail: 1677 free(buckets); 1678 buckets = NULL; 1679 return -1; 1680} 1681 1682int 1683dht_uninit() 1684{ 1685 if(dht_socket < 0 && dht_socket6 < 0) { 1686 errno = EINVAL; 1687 return -1; 1688 } 1689 1690 dht_socket = -1; 1691 dht_socket6 = -1; 1692 1693 while(buckets) { 1694 struct bucket *b = buckets; 1695 buckets = b->next; 1696 while(b->nodes) { 1697 struct node *n = b->nodes; 1698 b->nodes = n->next; 1699 free(n); 1700 } 1701 free(b); 1702 } 1703 1704 while(buckets6) { 1705 struct bucket *b = buckets6; 1706 buckets6 = b->next; 1707 while(b->nodes) { 1708 struct node *n = b->nodes; 1709 b->nodes = n->next; 1710 free(n); 1711 } 1712 free(b); 1713 } 1714 1715 while(storage) { 1716 struct storage *st = storage; 1717 storage = storage->next; 1718 free(st->peers); 1719 free(st); 1720 } 1721 1722 while(searches) { 1723 struct search *sr = searches; 1724 searches = searches->next; 1725 free(sr); 1726 } 1727 1728 return 1; 1729} 1730 1731/* Rate control for requests we receive. */ 1732 1733static int 1734token_bucket(void) 1735{ 1736 if(token_bucket_tokens == 0) { 1737 token_bucket_tokens = MIN(MAX_TOKEN_BUCKET_TOKENS, 1738 100 * (now.tv_sec - token_bucket_time)); 1739 token_bucket_time = now.tv_sec; 1740 } 1741 1742 if(token_bucket_tokens == 0) 1743 return 0; 1744 1745 token_bucket_tokens--; 1746 return 1; 1747} 1748 1749static int 1750neighbourhood_maintenance(int af) 1751{ 1752 unsigned char id[20]; 1753 struct bucket *b = find_bucket(myid, af); 1754 struct bucket *q; 1755 struct node *n; 1756 1757 if(b == NULL) 1758 return 0; 1759 1760 memcpy(id, myid, 20); 1761 id[19] = random() & 0xFF; 1762 q = b; 1763 if(q->next && (q->count == 0 || (random() & 7) == 0)) 1764 q = b->next; 1765 if(q->count == 0 || (random() & 7) == 0) { 1766 struct bucket *r; 1767 r = previous_bucket(b); 1768 if(r && r->count > 0) 1769 q = r; 1770 } 1771 1772 if(q) { 1773 /* Since our node-id is the same in both DHTs, it's probably 1774 profitable to query both families. */ 1775 int want = dht_socket >= 0 && dht_socket6 >= 0 ? (WANT4 | WANT6) : -1; 1776 n = random_node(q); 1777 if(n) { 1778 unsigned char tid[4]; 1779 debugf("Sending find_node for%s neighborhood maintenance.\n", 1780 af == AF_INET6 ? " IPv6" : ""); 1781 make_tid(tid, "fn", 0); 1782 send_find_node((struct sockaddr*)&n->ss, n->sslen, 1783 tid, 4, id, want, 1784 n->reply_time >= now.tv_sec - 15); 1785 pinged(n, q); 1786 } 1787 return 1; 1788 } 1789 return 0; 1790} 1791 1792static int 1793bucket_maintenance(int af) 1794{ 1795 struct bucket *b; 1796 1797 b = af == AF_INET ? buckets : buckets6; 1798 1799 while(b) { 1800 struct bucket *q; 1801 if(b->time < now.tv_sec - 600) { 1802 /* This bucket hasn't seen any positive confirmation for a long 1803 time. Pick a random id in this bucket's range, and send 1804 a request to a random node. */ 1805 unsigned char id[20]; 1806 struct node *n; 1807 int rc; 1808 1809 rc = bucket_random(b, id); 1810 if(rc < 0) 1811 memcpy(id, b->first, 20); 1812 1813 q = b; 1814 /* If the bucket is empty, we try to fill it from a neighbour. 1815 We also sometimes do it gratuitiously to recover from 1816 buckets full of broken nodes. */ 1817 if(q->next && (q->count == 0 || (random() & 7) == 0)) 1818 q = b->next; 1819 if(q->count == 0 || (random() & 7) == 0) { 1820 struct bucket *r; 1821 r = previous_bucket(b); 1822 if(r && r->count > 0) 1823 q = r; 1824 } 1825 1826 if(q) { 1827 n = random_node(q); 1828 if(n) { 1829 unsigned char tid[4]; 1830 int want = -1; 1831 1832 if(dht_socket >= 0 && dht_socket6 >= 0) { 1833 struct bucket *otherbucket; 1834 otherbucket = 1835 find_bucket(id, af == AF_INET ? AF_INET6 : AF_INET); 1836 if(otherbucket && otherbucket->count < 8) 1837 /* The corresponding bucket in the other family 1838 is emptyish -- querying both is useful. */ 1839 want = WANT4 | WANT6; 1840 else if(random() % 37 == 0) 1841 /* Most of the time, this just adds overhead. 1842 However, it might help stitch back one of 1843 the DHTs after a network collapse, so query 1844 both, but only very occasionally. */ 1845 want = WANT4 | WANT6; 1846 } 1847 1848 debugf("Sending find_node for%s bucket maintenance.\n", 1849 af == AF_INET6 ? " IPv6" : ""); 1850 make_tid(tid, "fn", 0); 1851 send_find_node((struct sockaddr*)&n->ss, n->sslen, 1852 tid, 4, id, want, 1853 n->reply_time >= now.tv_sec - 15); 1854 pinged(n, q); 1855 /* In order to avoid sending queries back-to-back, 1856 give up for now and reschedule us soon. */ 1857 return 1; 1858 } 1859 } 1860 } 1861 b = b->next; 1862 } 1863 return 0; 1864} 1865 1866int 1867dht_periodic(const void *buf, size_t buflen, 1868 const struct sockaddr *from, int fromlen, 1869 time_t *tosleep, 1870 dht_callback *callback, void *closure) 1871{ 1872 gettimeofday(&now, NULL); 1873 1874 if(buflen > 0) { 1875 int message; 1876 unsigned char tid[16], id[20], info_hash[20], target[20]; 1877 unsigned char nodes[256], nodes6[1024], token[128]; 1878 int tid_len = 16, token_len = 128; 1879 int nodes_len = 256, nodes6_len = 1024; 1880 unsigned short port; 1881 unsigned char values[2048], values6[2048]; 1882 int values_len = 2048, values6_len = 2048; 1883 int want; 1884 unsigned short ttid; 1885 1886 if(is_martian(from)) 1887 goto dontread; 1888 1889 if(node_blacklisted(from, fromlen)) { 1890 debugf("Received packet from blacklisted node.\n"); 1891 goto dontread; 1892 } 1893 1894 if(((char*)buf)[buflen] != '\0') { 1895 debugf("Unterminated message.\n"); 1896 errno = EINVAL; 1897 return -1; 1898 } 1899 1900 message = parse_message(buf, buflen, tid, &tid_len, id, info_hash, 1901 target, &port, token, &token_len, 1902 nodes, &nodes_len, nodes6, &nodes6_len, 1903 values, &values_len, values6, &values6_len, 1904 &want); 1905 1906 if(message < 0 || message == ERROR || id_cmp(id, zeroes) == 0) { 1907 debugf("Unparseable message: "); 1908 debug_printable(buf, buflen); 1909 debugf("\n"); 1910 goto dontread; 1911 } 1912 1913 if(id_cmp(id, myid) == 0) { 1914 debugf("Received message from self.\n"); 1915 goto dontread; 1916 } 1917 1918 if(message > REPLY) { 1919 /* Rate limit requests. */ 1920 if(!token_bucket()) { 1921 debugf("Dropping request due to rate limiting.\n"); 1922 goto dontread; 1923 } 1924 } 1925 1926 switch(message) { 1927 case REPLY: 1928 if(tid_len != 4) { 1929 debugf("Broken node truncates transaction ids: "); 1930 debug_printable(buf, buflen); 1931 debugf("\n"); 1932 /* This is really annoying, as it means that we will 1933 time-out all our searches that go through this node. 1934 Kill it. */ 1935 blacklist_node(id, from, fromlen); 1936 goto dontread; 1937 } 1938 if(tid_match(tid, "pn", NULL)) { 1939 debugf("Pong!\n"); 1940 new_node(id, from, fromlen, 2); 1941 } else if(tid_match(tid, "fn", NULL) || 1942 tid_match(tid, "gp", NULL)) { 1943 int gp = 0; 1944 struct search *sr = NULL; 1945 if(tid_match(tid, "gp", &ttid)) { 1946 gp = 1; 1947 sr = find_search(ttid, from->sa_family); 1948 } 1949 debugf("Nodes found (%d+%d)%s!\n", nodes_len/26, nodes6_len/38, 1950 gp ? " for get_peers" : ""); 1951 if(nodes_len % 26 != 0 || nodes6_len % 38 != 0) { 1952 debugf("Unexpected length for node info!\n"); 1953 blacklist_node(id, from, fromlen); 1954 } else if(gp && sr == NULL) { 1955 debugf("Unknown search!\n"); 1956 new_node(id, from, fromlen, 1); 1957 } else { 1958 int i; 1959 new_node(id, from, fromlen, 2); 1960 for(i = 0; i < nodes_len / 26; i++) { 1961 unsigned char *ni = nodes + i * 26; 1962 struct sockaddr_in sin; 1963 if(id_cmp(ni, myid) == 0) 1964 continue; 1965 memset(&sin, 0, sizeof(sin)); 1966 sin.sin_family = AF_INET; 1967 memcpy(&sin.sin_addr, ni + 20, 4); 1968 memcpy(&sin.sin_port, ni + 24, 2); 1969 new_node(ni, (struct sockaddr*)&sin, sizeof(sin), 0); 1970 if(sr && sr->af == AF_INET) { 1971 insert_search_node(ni, 1972 (struct sockaddr*)&sin, 1973 sizeof(sin), 1974 sr, 0, NULL, 0); 1975 } 1976 } 1977 for(i = 0; i < nodes6_len / 38; i++) { 1978 unsigned char *ni = nodes6 + i * 38; 1979 struct sockaddr_in6 sin6; 1980 if(id_cmp(ni, myid) == 0) 1981 continue; 1982 memset(&sin6, 0, sizeof(sin6)); 1983 sin6.sin6_family = AF_INET6; 1984 memcpy(&sin6.sin6_addr, ni + 20, 16); 1985 memcpy(&sin6.sin6_port, ni + 36, 2); 1986 new_node(ni, (struct sockaddr*)&sin6, sizeof(sin6), 0); 1987 if(sr && sr->af == AF_INET6) { 1988 insert_search_node(ni, 1989 (struct sockaddr*)&sin6, 1990 sizeof(sin6), 1991 sr, 0, NULL, 0); 1992 } 1993 } 1994 if(sr) 1995 /* Since we received a reply, the number of 1996 requests in flight has decreased. Let's push 1997 another request. */ 1998 search_send_get_peers(sr, NULL); 1999 } 2000 if(sr) { 2001 insert_search_node(id, from, fromlen, sr, 2002 1, token, token_len); 2003 if(values_len > 0 || values6_len > 0) { 2004 debugf("Got values (%d+%d)!\n", 2005 values_len / 6, values6_len / 18); 2006 if(callback) { 2007 if(values_len > 0) 2008 (*callback)(closure, DHT_EVENT_VALUES, sr->id, 2009 (void*)values, values_len); 2010 2011 if(values6_len > 0) 2012 (*callback)(closure, DHT_EVENT_VALUES6, sr->id, 2013 (void*)values6, values6_len); 2014 } 2015 } 2016 } 2017 } else if(tid_match(tid, "ap", &ttid)) { 2018 struct search *sr; 2019 debugf("Got reply to announce_peer.\n"); 2020 sr = find_search(ttid, from->sa_family); 2021 if(!sr) { 2022 debugf("Unknown search!\n"); 2023 new_node(id, from, fromlen, 1); 2024 } else { 2025 int i; 2026 new_node(id, from, fromlen, 2); 2027 for(i = 0; i < sr->numnodes; i++) 2028 if(id_cmp(sr->nodes[i].id, id) == 0) { 2029 sr->nodes[i].request_time = 0; 2030 sr->nodes[i].reply_time = now.tv_sec; 2031 sr->nodes[i].acked = 1; 2032 sr->nodes[i].pinged = 0; 2033 break; 2034 } 2035 /* See comment for gp above. */ 2036 search_send_get_peers(sr, NULL); 2037 } 2038 } else { 2039 debugf("Unexpected reply: "); 2040 debug_printable(buf, buflen); 2041 debugf("\n"); 2042 } 2043 break; 2044 case PING: 2045 debugf("Ping (%d)!\n", tid_len); 2046 new_node(id, from, fromlen, 1); 2047 debugf("Sending pong.\n"); 2048 send_pong(from, fromlen, tid, tid_len); 2049 break; 2050 case FIND_NODE: 2051 debugf("Find node!\n"); 2052 new_node(id, from, fromlen, 1); 2053 debugf("Sending closest nodes (%d).\n", want); 2054 send_closest_nodes(from, fromlen, 2055 tid, tid_len, target, want, 2056 0, NULL, NULL, 0); 2057 break; 2058 case GET_PEERS: 2059 debugf("Get_peers!\n"); 2060 new_node(id, from, fromlen, 1); 2061 if(id_cmp(info_hash, zeroes) == 0) { 2062 debugf("Eek! Got get_peers with no info_hash.\n"); 2063 send_error(from, fromlen, tid, tid_len, 2064 203, "Get_peers with no info_hash"); 2065 break; 2066 } else { 2067 struct storage *st = find_storage(info_hash); 2068 unsigned char token[TOKEN_SIZE]; 2069 make_token(from, 0, token); 2070 if(st && st->numpeers > 0) { 2071 debugf("Sending found%s peers.\n", 2072 from->sa_family == AF_INET6 ? " IPv6" : ""); 2073 send_closest_nodes(from, fromlen, 2074 tid, tid_len, 2075 info_hash, want, 2076 from->sa_family, st, 2077 token, TOKEN_SIZE); 2078 } else { 2079 debugf("Sending nodes for get_peers.\n"); 2080 send_closest_nodes(from, fromlen, 2081 tid, tid_len, info_hash, want, 2082 0, NULL, token, TOKEN_SIZE); 2083 } 2084 } 2085 break; 2086 case ANNOUNCE_PEER: 2087 debugf("Announce peer!\n"); 2088 new_node(id, from, fromlen, 1); 2089 if(id_cmp(info_hash, zeroes) == 0) { 2090 debugf("Announce_peer with no info_hash.\n"); 2091 send_error(from, fromlen, tid, tid_len, 2092 203, "Announce_peer with no info_hash"); 2093 break; 2094 } 2095 if(!token_match(token, token_len, from)) { 2096 debugf("Incorrect token for announce_peer.\n"); 2097 send_error(from, fromlen, tid, tid_len, 2098 203, "Announce_peer with wrong token"); 2099 break; 2100 } 2101 if(port == 0) { 2102 debugf("Announce_peer with forbidden port %d.\n", port); 2103 send_error(from, fromlen, tid, tid_len, 2104 203, "Announce_peer with forbidden port number"); 2105 break; 2106 } 2107 storage_store(info_hash, from, port); 2108 /* Note that if storage_store failed, we lie to the requestor. 2109 This is to prevent them from backtracking, and hence 2110 polluting the DHT. */ 2111 debugf("Sending peer announced.\n"); 2112 send_peer_announced(from, fromlen, tid, tid_len); 2113 } 2114 } 2115 2116 dontread: 2117 if(now.tv_sec >= rotate_secrets_time) 2118 rotate_secrets(); 2119 2120 if(now.tv_sec >= expire_stuff_time) { 2121 expire_buckets(buckets); 2122 expire_buckets(buckets6); 2123 expire_storage(); 2124 expire_searches(); 2125 } 2126 2127 if(search_time > 0 && now.tv_sec >= search_time) { 2128 struct search *sr; 2129 sr = searches; 2130 while(sr) { 2131 if(!sr->done && sr->step_time + 5 <= now.tv_sec) { 2132 search_step(sr, callback, closure); 2133 } 2134 sr = sr->next; 2135 } 2136 2137 search_time = 0; 2138 2139 sr = searches; 2140 while(sr) { 2141 if(!sr->done) { 2142 time_t tm = sr->step_time + 15 + random() % 10; 2143 if(search_time == 0 || search_time > tm) 2144 search_time = tm; 2145 } 2146 sr = sr->next; 2147 } 2148 } 2149 2150 if(now.tv_sec >= confirm_nodes_time) { 2151 int soon = 0; 2152 2153 soon |= bucket_maintenance(AF_INET); 2154 soon |= bucket_maintenance(AF_INET6); 2155 2156 if(!soon) { 2157 if(mybucket_grow_time >= now.tv_sec - 150) 2158 soon |= neighbourhood_maintenance(AF_INET); 2159 if(mybucket6_grow_time >= now.tv_sec - 150) 2160 soon |= neighbourhood_maintenance(AF_INET6); 2161 } 2162 2163 /* In order to maintain all buckets' age within 600 seconds, worst 2164 case is roughly 27 seconds, assuming the table is 22 bits deep. 2165 We want to keep a margin for neighborhood maintenance, so keep 2166 this within 25 seconds. */ 2167 if(soon) 2168 confirm_nodes_time = now.tv_sec + 5 + random() % 20; 2169 else 2170 confirm_nodes_time = now.tv_sec + 60 + random() % 120; 2171 } 2172 2173 if(confirm_nodes_time > now.tv_sec) 2174 *tosleep = confirm_nodes_time - now.tv_sec; 2175 else 2176 *tosleep = 0; 2177 2178 if(search_time > 0) { 2179 if(search_time <= now.tv_sec) 2180 *tosleep = 0; 2181 else if(*tosleep > search_time - now.tv_sec) 2182 *tosleep = search_time - now.tv_sec; 2183 } 2184 2185 return 1; 2186} 2187 2188int 2189dht_get_nodes(struct sockaddr_in *sin, int *num, 2190 struct sockaddr_in6 *sin6, int *num6) 2191{ 2192 int i, j; 2193 struct bucket *b; 2194 struct node *n; 2195 2196 i = 0; 2197 2198 /* For restoring to work without discarding too many nodes, the list 2199 must start with the contents of our bucket. */ 2200 b = find_bucket(myid, AF_INET); 2201 if(b == NULL) 2202 goto no_ipv4; 2203 2204 n = b->nodes; 2205 while(n && i < *num) { 2206 if(node_good(n)) { 2207 sin[i] = *(struct sockaddr_in*)&n->ss; 2208 i++; 2209 } 2210 n = n->next; 2211 } 2212 2213 b = buckets; 2214 while(b && i < *num) { 2215 if(!in_bucket(myid, b)) { 2216 n = b->nodes; 2217 while(n && i < *num) { 2218 if(node_good(n)) { 2219 sin[i] = *(struct sockaddr_in*)&n->ss; 2220 i++; 2221 } 2222 n = n->next; 2223 } 2224 } 2225 b = b->next; 2226 } 2227 2228 no_ipv4: 2229 2230 j = 0; 2231 2232 b = find_bucket(myid, AF_INET6); 2233 if(b == NULL) 2234 goto no_ipv6; 2235 2236 n = b->nodes; 2237 while(n && j < *num6) { 2238 if(node_good(n)) { 2239 sin6[j] = *(struct sockaddr_in6*)&n->ss; 2240 j++; 2241 } 2242 n = n->next; 2243 } 2244 2245 b = buckets6; 2246 while(b && j < *num6) { 2247 if(!in_bucket(myid, b)) { 2248 n = b->nodes; 2249 while(n && j < *num6) { 2250 if(node_good(n)) { 2251 sin6[j] = *(struct sockaddr_in6*)&n->ss; 2252 j++; 2253 } 2254 n = n->next; 2255 } 2256 } 2257 b = b->next; 2258 } 2259 2260 no_ipv6: 2261 2262 *num = i; 2263 *num6 = j; 2264 return i + j; 2265} 2266 2267int 2268dht_insert_node(const unsigned char *id, struct sockaddr *sa, int salen) 2269{ 2270 struct node *n; 2271 2272 if(sa->sa_family != AF_INET) { 2273 errno = EAFNOSUPPORT; 2274 return -1; 2275 } 2276 2277 n = new_node(id, (struct sockaddr*)sa, salen, 0); 2278 return !!n; 2279} 2280 2281int 2282dht_ping_node(struct sockaddr *sa, int salen) 2283{ 2284 unsigned char tid[4]; 2285 2286 debugf("Sending ping.\n"); 2287 make_tid(tid, "pn", 0); 2288 return send_ping(sa, salen, tid, 4); 2289} 2290 2291/* We could use a proper bencoding printer and parser, but the format of 2292 DHT messages is fairly stylised, so this seemed simpler. */ 2293 2294#define CHECK(offset, delta, size) \ 2295 if(delta < 0 || offset + delta > size) goto fail 2296 2297#define INC(offset, delta, size) \ 2298 CHECK(offset, delta, size); \ 2299 offset += delta 2300 2301#define COPY(buf, offset, src, delta, size) \ 2302 CHECK(offset, delta, size); \ 2303 memcpy(buf + offset, src, delta); \ 2304 offset += delta; 2305 2306#define ADD_V(buf, offset, size) \ 2307 if(have_v) { \ 2308 COPY(buf, offset, my_v, sizeof(my_v), size); \ 2309 } 2310 2311static int 2312dht_send(const void *buf, size_t len, int flags, 2313 const struct sockaddr *sa, int salen) 2314{ 2315 int s; 2316 2317 if(salen == 0) 2318 abort(); 2319 2320 if(node_blacklisted(sa, salen)) { 2321 debugf("Attempting to send to blacklisted node.\n"); 2322 errno = EPERM; 2323 return -1; 2324 } 2325 2326 if(sa->sa_family == AF_INET) 2327 s = dht_socket; 2328 else if(sa->sa_family == AF_INET6) 2329 s = dht_socket6; 2330 else 2331 s = -1; 2332 2333 if(s < 0) { 2334 errno = EAFNOSUPPORT; 2335 return -1; 2336 } 2337 2338 return sendto(s, buf, len, flags, sa, salen); 2339} 2340 2341int 2342send_ping(const struct sockaddr *sa, int salen, 2343 const unsigned char *tid, int tid_len) 2344{ 2345 char buf[512]; 2346 int i = 0, rc; 2347 rc = snprintf(buf + i, 512 - i, "d1:ad2:id20:"); INC(i, rc, 512); 2348 COPY(buf, i, myid, 20, 512); 2349 rc = snprintf(buf + i, 512 - i, "e1:q4:ping1:t%d:", tid_len); 2350 INC(i, rc, 512); 2351 COPY(buf, i, tid, tid_len, 512); 2352 ADD_V(buf, i, 512); 2353 rc = snprintf(buf + i, 512 - i, "1:y1:qe"); INC(i, rc, 512); 2354 return dht_send(buf, i, 0, sa, salen); 2355 2356 fail: 2357 errno = ENOSPC; 2358 return -1; 2359} 2360 2361int 2362send_pong(const struct sockaddr *sa, int salen, 2363 const unsigned char *tid, int tid_len) 2364{ 2365 char buf[512]; 2366 int i = 0, rc; 2367 rc = snprintf(buf + i, 512 - i, "d1:rd2:id20:"); INC(i, rc, 512); 2368 COPY(buf, i, myid, 20, 512); 2369 rc = snprintf(buf + i, 512 - i, "e1:t%d:", tid_len); INC(i, rc, 512); 2370 COPY(buf, i, tid, tid_len, 512); 2371 ADD_V(buf, i, 512); 2372 rc = snprintf(buf + i, 512 - i, "1:y1:re"); INC(i, rc, 512); 2373 return dht_send(buf, i, 0, sa, salen); 2374 2375 fail: 2376 errno = ENOSPC; 2377 return -1; 2378} 2379 2380int 2381send_find_node(const struct sockaddr *sa, int salen, 2382 const unsigned char *tid, int tid_len, 2383 const unsigned char *target, int want, int confirm) 2384{ 2385 char buf[512]; 2386 int i = 0, rc; 2387 rc = snprintf(buf + i, 512 - i, "d1:ad2:id20:"); INC(i, rc, 512); 2388 COPY(buf, i, myid, 20, 512); 2389 rc = snprintf(buf + i, 512 - i, "6:target20:"); INC(i, rc, 512); 2390 COPY(buf, i, target, 20, 512); 2391 if(want > 0) { 2392 rc = snprintf(buf + i, 512 - i, "4:wantl%s%se", 2393 (want & WANT4) ? "2:n4" : "", 2394 (want & WANT6) ? "2:n6" : ""); 2395 INC(i, rc, 512); 2396 } 2397 rc = snprintf(buf + i, 512 - i, "e1:q9:find_node1:t%d:", tid_len); 2398 INC(i, rc, 512); 2399 COPY(buf, i, tid, tid_len, 512); 2400 ADD_V(buf, i, 512); 2401 rc = snprintf(buf + i, 512 - i, "1:y1:qe"); INC(i, rc, 512); 2402 return dht_send(buf, i, confirm ? MSG_CONFIRM : 0, sa, salen); 2403 2404 fail: 2405 errno = ENOSPC; 2406 return -1; 2407} 2408 2409int 2410send_nodes_peers(const struct sockaddr *sa, int salen, 2411 const unsigned char *tid, int tid_len, 2412 const unsigned char *nodes, int nodes_len, 2413 const unsigned char *nodes6, int nodes6_len, 2414 int af, struct storage *st, 2415 const unsigned char *token, int token_len) 2416{ 2417 char buf[2048]; 2418 int i = 0, rc, j0, j, k, len; 2419 2420 rc = snprintf(buf + i, 2048 - i, "d1:rd2:id20:"); INC(i, rc, 2048); 2421 COPY(buf, i, myid, 20, 2048); 2422 if(nodes_len > 0) { 2423 rc = snprintf(buf + i, 2048 - i, "5:nodes%d:", nodes_len); 2424 INC(i, rc, 2048); 2425 COPY(buf, i, nodes, nodes_len, 2048); 2426 } 2427 if(nodes6_len > 0) { 2428 rc = snprintf(buf + i, 2048 - i, "6:nodes6%d:", nodes6_len); 2429 INC(i, rc, 2048); 2430 COPY(buf, i, nodes6, nodes6_len, 2048); 2431 } 2432 if(token_len > 0) { 2433 rc = snprintf(buf + i, 2048 - i, "5:token%d:", token_len); 2434 INC(i, rc, 2048); 2435 COPY(buf, i, token, token_len, 2048); 2436 } 2437 2438 if(st && st->numpeers > 0) { 2439 /* We treat the storage as a circular list, and serve a randomly 2440 chosen slice. In order to make sure we fit within 1024 octets, 2441 we limit ourselves to 50 peers. */ 2442 2443 len = af == AF_INET ? 4 : 16; 2444 j0 = random() % st->numpeers; 2445 j = j0; 2446 k = 0; 2447 2448 rc = snprintf(buf + i, 2048 - i, "6:valuesl"); INC(i, rc, 2048); 2449 do { 2450 if(st->peers[j].len == len) { 2451 unsigned short swapped; 2452 swapped = htons(st->peers[j].port); 2453 rc = snprintf(buf + i, 2048 - i, "%d:", len + 2); 2454 INC(i, rc, 2048); 2455 COPY(buf, i, st->peers[j].ip, len, 2048); 2456 COPY(buf, i, &swapped, 2, 2048); 2457 k++; 2458 } 2459 j = (j + 1) % st->numpeers; 2460 } while(j != j0 && k < 50); 2461 rc = snprintf(buf + i, 2048 - i, "e"); INC(i, rc, 2048); 2462 } 2463 2464 rc = snprintf(buf + i, 2048 - i, "e1:t%d:", tid_len); INC(i, rc, 2048); 2465 COPY(buf, i, tid, tid_len, 2048); 2466 ADD_V(buf, i, 2048); 2467 rc = snprintf(buf + i, 2048 - i, "1:y1:re"); INC(i, rc, 2048); 2468 2469 return dht_send(buf, i, 0, sa, salen); 2470 2471 fail: 2472 errno = ENOSPC; 2473 return -1; 2474} 2475 2476static int 2477insert_closest_node(unsigned char *nodes, int numnodes, 2478 const unsigned char *id, struct node *n) 2479{ 2480 int i, size; 2481 2482 if(n->ss.ss_family == AF_INET) 2483 size = 26; 2484 else if(n->ss.ss_family == AF_INET6) 2485 size = 38; 2486 else 2487 abort(); 2488 2489 for(i = 0; i< numnodes; i++) { 2490 if(id_cmp(n->id, nodes + size * i) == 0) 2491 return numnodes; 2492 if(xorcmp(n->id, nodes + size * i, id) < 0) 2493 break; 2494 } 2495 2496 if(i == 8) 2497 return numnodes; 2498 2499 if(numnodes < 8) 2500 numnodes++; 2501 2502 if(i < numnodes - 1) 2503 memmove(nodes + size * (i + 1), nodes + size * i, 2504 size * (numnodes - i - 1)); 2505 2506 if(n->ss.ss_family == AF_INET) { 2507 struct sockaddr_in *sin = (struct sockaddr_in*)&n->ss; 2508 memcpy(nodes + size * i, n->id, 20); 2509 memcpy(nodes + size * i + 20, &sin->sin_addr, 4); 2510 memcpy(nodes + size * i + 24, &sin->sin_port, 2); 2511 } else if(n->ss.ss_family == AF_INET6) { 2512 struct sockaddr_in6 *sin6 = (struct sockaddr_in6*)&n->ss; 2513 memcpy(nodes + size * i, n->id, 20); 2514 memcpy(nodes + size * i + 20, &sin6->sin6_addr, 16); 2515 memcpy(nodes + size * i + 36, &sin6->sin6_port, 2); 2516 } else { 2517 abort(); 2518 } 2519 2520 return numnodes; 2521} 2522 2523static int 2524buffer_closest_nodes(unsigned char *nodes, int numnodes, 2525 const unsigned char *id, struct bucket *b) 2526{ 2527 struct node *n = b->nodes; 2528 while(n) { 2529 if(node_good(n)) 2530 numnodes = insert_closest_node(nodes, numnodes, id, n); 2531 n = n->next; 2532 } 2533 return numnodes; 2534} 2535 2536int 2537send_closest_nodes(const struct sockaddr *sa, int salen, 2538 const unsigned char *tid, int tid_len, 2539 const unsigned char *id, int want, 2540 int af, struct storage *st, 2541 const unsigned char *token, int token_len) 2542{ 2543 unsigned char nodes[8 * 26]; 2544 unsigned char nodes6[8 * 38]; 2545 int numnodes = 0, numnodes6 = 0; 2546 struct bucket *b; 2547 2548 if(want < 0) 2549 want = sa->sa_family == AF_INET ? WANT4 : WANT6; 2550 2551 if((want & WANT4)) { 2552 b = find_bucket(id, AF_INET); 2553 if(b) { 2554 numnodes = buffer_closest_nodes(nodes, numnodes, id, b); 2555 if(b->next) 2556 numnodes = buffer_closest_nodes(nodes, numnodes, id, b->next); 2557 b = previous_bucket(b); 2558 if(b) 2559 numnodes = buffer_closest_nodes(nodes, numnodes, id, b); 2560 } 2561 } 2562 2563 if((want & WANT6)) { 2564 b = find_bucket(id, AF_INET6); 2565 if(b) { 2566 numnodes6 = buffer_closest_nodes(nodes6, numnodes6, id, b); 2567 if(b->next) 2568 numnodes6 = 2569 buffer_closest_nodes(nodes6, numnodes6, id, b->next); 2570 b = previous_bucket(b); 2571 if(b) 2572 numnodes6 = buffer_closest_nodes(nodes6, numnodes6, id, b); 2573 } 2574 } 2575 debugf(" (%d+%d nodes.)\n", numnodes, numnodes6); 2576 2577 return send_nodes_peers(sa, salen, tid, tid_len, 2578 nodes, numnodes * 26, 2579 nodes6, numnodes6 * 38, 2580 af, st, token, token_len); 2581} 2582 2583int 2584send_get_peers(const struct sockaddr *sa, int salen, 2585 unsigned char *tid, int tid_len, unsigned char *infohash, 2586 int want, int confirm) 2587{ 2588 char buf[512]; 2589 int i = 0, rc; 2590 2591 rc = snprintf(buf + i, 512 - i, "d1:ad2:id20:"); INC(i, rc, 512); 2592 COPY(buf, i, myid, 20, 512); 2593 rc = snprintf(buf + i, 512 - i, "9:info_hash20:"); INC(i, rc, 512); 2594 COPY(buf, i, infohash, 20, 512); 2595 if(want > 0) { 2596 rc = snprintf(buf + i, 512 - i, "4:wantl%s%se", 2597 (want & WANT4) ? "2:n4" : "", 2598 (want & WANT6) ? "2:n6" : ""); 2599 INC(i, rc, 512); 2600 } 2601 rc = snprintf(buf + i, 512 - i, "e1:q9:get_peers1:t%d:", tid_len); 2602 INC(i, rc, 512); 2603 COPY(buf, i, tid, tid_len, 512); 2604 ADD_V(buf, i, 512); 2605 rc = snprintf(buf + i, 512 - i, "1:y1:qe"); INC(i, rc, 512); 2606 return dht_send(buf, i, confirm ? MSG_CONFIRM : 0, sa, salen); 2607 2608 fail: 2609 errno = ENOSPC; 2610 return -1; 2611} 2612 2613int 2614send_announce_peer(const struct sockaddr *sa, int salen, 2615 unsigned char *tid, int tid_len, 2616 unsigned char *infohash, unsigned short port, 2617 unsigned char *token, int token_len, int confirm) 2618{ 2619 char buf[512]; 2620 int i = 0, rc; 2621 2622 rc = snprintf(buf + i, 512 - i, "d1:ad2:id20:"); INC(i, rc, 512); 2623 COPY(buf, i, myid, 20, 512); 2624 rc = snprintf(buf + i, 512 - i, "9:info_hash20:"); INC(i, rc, 512); 2625 COPY(buf, i, infohash, 20, 512); 2626 rc = snprintf(buf + i, 512 - i, "4:porti%ue5:token%d:", (unsigned)port, 2627 token_len); 2628 INC(i, rc, 512); 2629 COPY(buf, i, token, token_len, 512); 2630 rc = snprintf(buf + i, 512 - i, "e1:q13:announce_peer1:t%d:", tid_len); 2631 INC(i, rc, 512); 2632 COPY(buf, i, tid, tid_len, 512); 2633 ADD_V(buf, i, 512); 2634 rc = snprintf(buf + i, 512 - i, "1:y1:qe"); INC(i, rc, 512); 2635 2636 return dht_send(buf, i, confirm ? 0 : MSG_CONFIRM, sa, salen); 2637 2638 fail: 2639 errno = ENOSPC; 2640 return -1; 2641} 2642 2643static int 2644send_peer_announced(const struct sockaddr *sa, int salen, 2645 unsigned char *tid, int tid_len) 2646{ 2647 char buf[512]; 2648 int i = 0, rc; 2649 2650 rc = snprintf(buf + i, 512 - i, "d1:rd2:id20:"); INC(i, rc, 512); 2651 COPY(buf, i, myid, 20, 512); 2652 rc = snprintf(buf + i, 512 - i, "e1:t%d:", tid_len); 2653 INC(i, rc, 512); 2654 COPY(buf, i, tid, tid_len, 512); 2655 ADD_V(buf, i, 512); 2656 rc = snprintf(buf + i, 512 - i, "1:y1:re"); INC(i, rc, 512); 2657 return dht_send(buf, i, 0, sa, salen); 2658 2659 fail: 2660 errno = ENOSPC; 2661 return -1; 2662} 2663 2664static int 2665send_error(const struct sockaddr *sa, int salen, 2666 unsigned char *tid, int tid_len, 2667 int code, const char *message) 2668{ 2669 char buf[512]; 2670 int i = 0, rc; 2671 2672 rc = snprintf(buf + i, 512 - i, "d1:eli%de%d:", 2673 code, (int)strlen(message)); 2674 INC(i, rc, 512); 2675 COPY(buf, i, message, (int)strlen(message), 512); 2676 rc = snprintf(buf + i, 512 - i, "e1:t%d:", tid_len); INC(i, rc, 512); 2677 COPY(buf, i, tid, tid_len, 512); 2678 ADD_V(buf, i, 512); 2679 rc = snprintf(buf + i, 512 - i, "1:y1:ee"); INC(i, rc, 512); 2680 return dht_send(buf, i, 0, sa, salen); 2681 2682 fail: 2683 errno = ENOSPC; 2684 return -1; 2685} 2686 2687#undef CHECK 2688#undef INC 2689#undef COPY 2690#undef ADD_V 2691 2692#ifdef HAVE_MEMMEM 2693 2694static void * 2695dht_memmem(const void *haystack, size_t haystacklen, 2696 const void *needle, size_t needlelen) 2697{ 2698 return memmem(haystack, haystacklen, needle, needlelen); 2699} 2700 2701#else 2702 2703static void * 2704dht_memmem(const void *haystack, size_t haystacklen, 2705 const void *needle, size_t needlelen) 2706{ 2707 const char *h = haystack; 2708 const char *n = needle; 2709 size_t i; 2710 2711 /* size_t is unsigned */ 2712 if(needlelen > haystacklen) 2713 return NULL; 2714 2715 for(i = 0; i <= haystacklen - needlelen; i++) { 2716 if(memcmp(h + i, n, needlelen) == 0) 2717 return (void*)(h + i); 2718 } 2719 return NULL; 2720} 2721 2722#endif 2723 2724static int 2725parse_message(const unsigned char *buf, int buflen, 2726 unsigned char *tid_return, int *tid_len, 2727 unsigned char *id_return, unsigned char *info_hash_return, 2728 unsigned char *target_return, unsigned short *port_return, 2729 unsigned char *token_return, int *token_len, 2730 unsigned char *nodes_return, int *nodes_len, 2731 unsigned char *nodes6_return, int *nodes6_len, 2732 unsigned char *values_return, int *values_len, 2733 unsigned char *values6_return, int *values6_len, 2734 int *want_return) 2735{ 2736 const unsigned char *p; 2737 2738 /* This code will happily crash if the buffer is not NUL-terminated. */ 2739 if(buf[buflen] != '\0') { 2740 debugf("Eek! parse_message with unterminated buffer.\n"); 2741 return -1; 2742 } 2743 2744#define CHECK(ptr, len) \ 2745 if(((unsigned char*)ptr) + (len) > (buf) + (buflen)) goto overflow; 2746 2747 if(tid_return) { 2748 p = dht_memmem(buf, buflen, "1:t", 3); 2749 if(p) { 2750 long l; 2751 char *q; 2752 l = strtol((char*)p + 3, &q, 10); 2753 if(q && *q == ':' && l > 0 && l < *tid_len) { 2754 CHECK(q + 1, l); 2755 memcpy(tid_return, q + 1, l); 2756 *tid_len = l; 2757 } else 2758 *tid_len = 0; 2759 } 2760 } 2761 if(id_return) { 2762 p = dht_memmem(buf, buflen, "2:id20:", 7); 2763 if(p) { 2764 CHECK(p + 7, 20); 2765 memcpy(id_return, p + 7, 20); 2766 } else { 2767 memset(id_return, 0, 20); 2768 } 2769 } 2770 if(info_hash_return) { 2771 p = dht_memmem(buf, buflen, "9:info_hash20:", 14); 2772 if(p) { 2773 CHECK(p + 14, 20); 2774 memcpy(info_hash_return, p + 14, 20); 2775 } else { 2776 memset(info_hash_return, 0, 20); 2777 } 2778 } 2779 if(port_return) { 2780 p = dht_memmem(buf, buflen, "porti", 5); 2781 if(p) { 2782 long l; 2783 char *q; 2784 l = strtol((char*)p + 5, &q, 10); 2785 if(q && *q == 'e' && l > 0 && l < 0x10000) 2786 *port_return = l; 2787 else 2788 *port_return = 0; 2789 } else 2790 *port_return = 0; 2791 } 2792 if(target_return) { 2793 p = dht_memmem(buf, buflen, "6:target20:", 11); 2794 if(p) { 2795 CHECK(p + 11, 20); 2796 memcpy(target_return, p + 11, 20); 2797 } else { 2798 memset(target_return, 0, 20); 2799 } 2800 } 2801 if(token_return) { 2802 p = dht_memmem(buf, buflen, "5:token", 7); 2803 if(p) { 2804 long l; 2805 char *q; 2806 l = strtol((char*)p + 7, &q, 10); 2807 if(q && *q == ':' && l > 0 && l < *token_len) { 2808 CHECK(q + 1, l); 2809 memcpy(token_return, q + 1, l); 2810 *token_len = l; 2811 } else 2812 *token_len = 0; 2813 } else 2814 *token_len = 0; 2815 } 2816 2817 if(nodes_len) { 2818 p = dht_memmem(buf, buflen, "5:nodes", 7); 2819 if(p) { 2820 long l; 2821 char *q; 2822 l = strtol((char*)p + 7, &q, 10); 2823 if(q && *q == ':' && l > 0 && l < *nodes_len) { 2824 CHECK(q + 1, l); 2825 memcpy(nodes_return, q + 1, l); 2826 *nodes_len = l; 2827 } else 2828 *nodes_len = 0; 2829 } else 2830 *nodes_len = 0; 2831 } 2832 2833 if(nodes6_len) { 2834 p = dht_memmem(buf, buflen, "6:nodes6", 8); 2835 if(p) { 2836 long l; 2837 char *q; 2838 l = strtol((char*)p + 8, &q, 10); 2839 if(q && *q == ':' && l > 0 && l < *nodes6_len) { 2840 CHECK(q + 1, l); 2841 memcpy(nodes6_return, q + 1, l); 2842 *nodes6_len = l; 2843 } else 2844 *nodes6_len = 0; 2845 } else 2846 *nodes6_len = 0; 2847 } 2848 2849 if(values_len || values6_len) { 2850 p = dht_memmem(buf, buflen, "6:valuesl", 9); 2851 if(p) { 2852 int i = p - buf + 9; 2853 int j = 0, j6 = 0; 2854 while(1) { 2855 long l; 2856 char *q; 2857 l = strtol((char*)buf + i, &q, 10); 2858 if(q && *q == ':' && l > 0) { 2859 CHECK(q + 1, l); 2860 i = q + 1 + l - (char*)buf; 2861 if(l == 6) { 2862 if(j + l > *values_len) 2863 continue; 2864 memcpy((char*)values_return + j, q + 1, l); 2865 j += l; 2866 } else if(l == 18) { 2867 if(j6 + l > *values6_len) 2868 continue; 2869 memcpy((char*)values6_return + j6, q + 1, l); 2870 j6 += l; 2871 } else { 2872 debugf("Received weird value -- %d bytes.\n", (int)l); 2873 } 2874 } else { 2875 break; 2876 } 2877 } 2878 if(i >= buflen || buf[i] != 'e') 2879 debugf("eek... unexpected end for values.\n"); 2880 if(values_len) 2881 *values_len = j; 2882 if(values6_len) 2883 *values6_len = j6; 2884 } else { 2885 if(values_len) 2886 *values_len = 0; 2887 if(values6_len) 2888 *values6_len = 0; 2889 } 2890 } 2891 2892 if(want_return) { 2893 p = dht_memmem(buf, buflen, "4:wantl", 7); 2894 if(p) { 2895 int i = p - buf + 7; 2896 *want_return = 0; 2897 while(buf[i] > '0' && buf[i] <= '9' && buf[i + 1] == ':' && 2898 i + 2 + buf[i] - '0' < buflen) { 2899 CHECK(buf + i + 2, buf[i] - '0'); 2900 if(buf[i] == '2' && memcmp(buf + i + 2, "n4", 2) == 0) 2901 *want_return |= WANT4; 2902 else if(buf[i] == '2' && memcmp(buf + i + 2, "n6", 2) == 0) 2903 *want_return |= WANT6; 2904 else 2905 debugf("eek... unexpected want flag (%c)\n", buf[i]); 2906 i += 2 + buf[i] - '0'; 2907 } 2908 if(i >= buflen || buf[i] != 'e') 2909 debugf("eek... unexpected end for want.\n"); 2910 } else { 2911 *want_return = -1; 2912 } 2913 } 2914 2915#undef CHECK 2916 2917 if(dht_memmem(buf, buflen, "1:y1:r", 6)) 2918 return REPLY; 2919 if(dht_memmem(buf, buflen, "1:y1:e", 6)) 2920 return ERROR; 2921 if(!dht_memmem(buf, buflen, "1:y1:q", 6)) 2922 return -1; 2923 if(dht_memmem(buf, buflen, "1:q4:ping", 9)) 2924 return PING; 2925 if(dht_memmem(buf, buflen, "1:q9:find_node", 14)) 2926 return FIND_NODE; 2927 if(dht_memmem(buf, buflen, "1:q9:get_peers", 14)) 2928 return GET_PEERS; 2929 if(dht_memmem(buf, buflen, "1:q13:announce_peer", 19)) 2930 return ANNOUNCE_PEER; 2931 return -1; 2932 2933 overflow: 2934 debugf("Truncated message.\n"); 2935 return -1; 2936} 2937