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