2 Copyright (c) 2009-2011 by Juliusz Chroboczek
4 Permission is hereby granted, free of charge, to any person obtaining a copy
5 of this software and associated documentation files (the "Software"), to deal
6 in the Software without restriction, including without limitation the rights
7 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8 copies of the Software, and to permit persons to whom the Software is
9 furnished to do so, subject to the following conditions:
11 The above copyright notice and this permission notice shall be included in
12 all copies or substantial portions of the Software.
14 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
23 /* Please, please, please.
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. */
44 #include <arpa/inet.h>
45 #include <sys/types.h>
46 #include <sys/socket.h>
47 #include <netinet/in.h>
50 #define WINVER WindowsXP
68 #define EAFNOSUPPORT WSAEAFNOSUPPORT
70 set_nonblocking(int fd
, int nonblocking
)
74 unsigned long mode
= !!nonblocking
;
75 rc
= ioctlsocket(fd
, FIONBIO
, &mode
);
77 errno
= WSAGetLastError();
78 return (rc
== 0 ? 0 : -1);
86 extern const char *inet_ntop(int, const void *, char *, socklen_t
);
91 set_nonblocking(int fd
, int nonblocking
)
94 rc
= fcntl(fd
, F_GETFL
, 0);
98 rc
= fcntl(fd
, F_SETFL
, nonblocking
?(rc
| O_NONBLOCK
):(rc
& ~O_NONBLOCK
));
107 /* We set sin_family to 0 to mark unused slots. */
108 #if AF_INET == 0 || AF_INET6 == 0
112 #if defined(__STDC_VERSION__) && __STDC_VERSION__ >= 199901L
114 #elif defined(__GNUC__)
115 #define inline __inline
117 #define restrict __restrict
119 #define restrict /**/
123 #define restrict /**/
126 #define MAX(x, y) ((x) >= (y) ? (x) : (y))
127 #define MIN(x, y) ((x) <= (y) ? (x) : (y))
130 unsigned char id
[20];
131 struct sockaddr_storage ss
;
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 */
142 unsigned char first
[20];
143 int count
; /* number of nodes */
144 int time
; /* time of last reply in this bucket */
146 struct sockaddr_storage cached
; /* the address of a likely candidate */
152 unsigned char id
[20];
153 struct sockaddr_storage ss
;
155 time_t request_time
; /* the time of the last unanswered request */
156 time_t reply_time
; /* the time of the last reply */
158 unsigned char token
[40];
160 int replied
; /* whether we have received a reply */
161 int acked
; /* whether they acked our announcement */
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
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 */
176 struct search_node nodes
[SEARCH_NODES
];
183 unsigned char ip
[16];
188 /* The maximum number of peers we store for a given hash. */
189 #ifndef DHT_MAX_PEERS
190 #define DHT_MAX_PEERS 2048
193 /* The maximum number of hashes we're willing to track. */
194 #ifndef DHT_MAX_HASHES
195 #define DHT_MAX_HASHES 16384
198 /* The maximum number of searches we keep data about. */
199 #ifndef DHT_MAX_SEARCHES
200 #define DHT_MAX_SEARCHES 1024
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)
209 unsigned char id
[20];
210 int numpeers
, maxpeers
;
212 struct storage
*next
;
215 static int send_ping(const struct sockaddr
*sa
, int salen
,
216 const unsigned char *tid
, int tid_len
);
217 static int send_pong(const struct sockaddr
*sa
, int salen
,
218 const unsigned char *tid
, int tid_len
);
219 static int send_find_node(const struct sockaddr
*sa
, int salen
,
220 const unsigned char *tid
, int tid_len
,
221 const unsigned char *target
, int want
, int confirm
);
222 static int send_nodes_peers(const struct sockaddr
*sa
, int salen
,
223 const unsigned char *tid
, int tid_len
,
224 const unsigned char *nodes
, int nodes_len
,
225 const unsigned char *nodes6
, int nodes6_len
,
226 int af
, struct storage
*st
,
227 const unsigned char *token
, int token_len
);
228 static int send_closest_nodes(const struct sockaddr
*sa
, int salen
,
229 const unsigned char *tid
, int tid_len
,
230 const unsigned char *id
, int want
,
231 int af
, struct storage
*st
,
232 const unsigned char *token
, int token_len
);
233 static int send_get_peers(const struct sockaddr
*sa
, int salen
,
234 unsigned char *tid
, int tid_len
,
235 unsigned char *infohash
, int want
, int confirm
);
236 static int send_announce_peer(const struct sockaddr
*sa
, int salen
,
237 unsigned char *tid
, int tid_len
,
238 unsigned char *infohas
, unsigned short port
,
239 unsigned char *token
, int token_len
, int confirm
);
240 static int send_peer_announced(const struct sockaddr
*sa
, int salen
,
241 unsigned char *tid
, int tid_len
);
242 static int send_error(const struct sockaddr
*sa
, int salen
,
243 unsigned char *tid
, int tid_len
,
244 int code
, const char *message
);
251 #define ANNOUNCE_PEER 5
256 static int parse_message(const unsigned char *buf
, int buflen
,
257 unsigned char *tid_return
, int *tid_len
,
258 unsigned char *id_return
,
259 unsigned char *info_hash_return
,
260 unsigned char *target_return
,
261 unsigned short *port_return
,
262 unsigned char *token_return
, int *token_len
,
263 unsigned char *nodes_return
, int *nodes_len
,
264 unsigned char *nodes6_return
, int *nodes6_len
,
265 unsigned char *values_return
, int *values_len
,
266 unsigned char *values6_return
, int *values6_len
,
269 static const unsigned char zeroes
[20] = {0};
270 static const unsigned char ones
[20] = {
271 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
272 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,
273 0xFF, 0xFF, 0xFF, 0xFF
275 static const unsigned char v4prefix
[16] = {
276 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0xFF, 0xFF, 0, 0, 0, 0
279 static int dht_socket
= -1;
280 static int dht_socket6
= -1;
282 static time_t search_time
;
283 static time_t confirm_nodes_time
;
284 static time_t rotate_secrets_time
;
286 static unsigned char myid
[20];
287 static int have_v
= 0;
288 static unsigned char my_v
[9];
289 static unsigned char secret
[8];
290 static unsigned char oldsecret
[8];
292 static struct bucket
*buckets
= NULL
;
293 static struct bucket
*buckets6
= NULL
;
294 static struct storage
*storage
;
295 static int numstorage
;
297 static struct search
*searches
= NULL
;
298 static int numsearches
;
299 static unsigned short search_id
;
301 /* The maximum number of nodes that we snub. There is probably little
302 reason to increase this value. */
303 #ifndef DHT_MAX_BLACKLISTED
304 #define DHT_MAX_BLACKLISTED 10
306 static struct sockaddr_storage blacklist
[DHT_MAX_BLACKLISTED
];
307 int next_blacklisted
;
309 static struct timeval now
;
310 static time_t mybucket_grow_time
, mybucket6_grow_time
;
311 static time_t expire_stuff_time
;
313 #define MAX_TOKEN_BUCKET_TOKENS 400
314 static time_t token_bucket_time
;
315 static int token_bucket_tokens
;
317 FILE *dht_debug
= NULL
;
320 __attribute__ ((format (printf
, 1, 2)))
323 debugf(const char *format
, ...)
326 va_start(args
, format
);
328 vfprintf(dht_debug
, format
, args
);
334 debug_printable(const unsigned char *buf
, int buflen
)
338 for(i
= 0; i
< buflen
; i
++)
339 putc(buf
[i
] >= 32 && buf
[i
] <= 126 ? buf
[i
] : '.', dht_debug
);
344 print_hex(FILE *f
, const unsigned char *buf
, int buflen
)
347 for(i
= 0; i
< buflen
; i
++)
348 fprintf(f
, "%02x", buf
[i
]);
352 is_martian(const struct sockaddr
*sa
)
354 switch(sa
->sa_family
) {
356 struct sockaddr_in
*sin
= (struct sockaddr_in
*)sa
;
357 const unsigned char *address
= (const unsigned char*)&sin
->sin_addr
;
358 return sin
->sin_port
== 0 ||
360 (address
[0] == 127) ||
361 ((address
[0] & 0xE0) == 0xE0);
364 struct sockaddr_in6
*sin6
= (struct sockaddr_in6
*)sa
;
365 const unsigned char *address
= (const unsigned char*)&sin6
->sin6_addr
;
366 return sin6
->sin6_port
== 0 ||
367 (address
[0] == 0xFF) ||
368 (address
[0] == 0xFE && (address
[1] & 0xC0) == 0x80) ||
369 (memcmp(address
, zeroes
, 15) == 0 &&
370 (address
[15] == 0 || address
[15] == 1)) ||
371 (memcmp(address
, v4prefix
, 12) == 0);
379 /* Forget about the ``XOR-metric''. An id is just a path from the
380 root of the tree, so bits are numbered from the start. */
383 id_cmp(const unsigned char *restrict id1
, const unsigned char *restrict id2
)
385 /* Memcmp is guaranteed to perform an unsigned comparison. */
386 return memcmp(id1
, id2
, 20);
389 /* Find the lowest 1 bit in an id. */
391 lowbit(const unsigned char *id
)
394 for(i
= 19; i
>= 0; i
--)
401 for(j
= 7; j
>= 0; j
--)
402 if((id
[i
] & (0x80 >> j
)) != 0)
408 /* Find how many bits two ids have in common. */
410 common_bits(const unsigned char *id1
, const unsigned char *id2
)
414 for(i
= 0; i
< 20; i
++) {
422 xor = id1
[i
] ^ id2
[i
];
425 while((xor & 0x80) == 0) {
433 /* Determine whether id1 or id2 is closer to ref */
435 xorcmp(const unsigned char *id1
, const unsigned char *id2
,
436 const unsigned char *ref
)
439 for(i
= 0; i
< 20; i
++) {
440 unsigned char xor1
, xor2
;
443 xor1
= id1
[i
] ^ ref
[i
];
444 xor2
= id2
[i
] ^ ref
[i
];
453 /* We keep buckets in a sorted linked list. A bucket b ranges from
454 b->first inclusive up to b->next->first exclusive. */
456 in_bucket(const unsigned char *id
, struct bucket
*b
)
458 return id_cmp(b
->first
, id
) <= 0 &&
459 (b
->next
== NULL
|| id_cmp(id
, b
->next
->first
) < 0);
462 static struct bucket
*
463 find_bucket(unsigned const char *id
, int af
)
465 struct bucket
*b
= af
== AF_INET
? buckets
: buckets6
;
473 if(id_cmp(id
, b
->next
->first
) < 0)
479 static struct bucket
*
480 previous_bucket(struct bucket
*b
)
482 struct bucket
*p
= b
->af
== AF_INET
? buckets
: buckets6
;
496 /* Every bucket contains an unordered list of nodes. */
498 find_node(const unsigned char *id
, int af
)
500 struct bucket
*b
= find_bucket(id
, af
);
508 if(id_cmp(n
->id
, id
) == 0)
515 /* Return a random node in a bucket. */
517 random_node(struct bucket
*b
)
525 nn
= random() % b
->count
;
534 /* Return the middle id of a bucket. */
536 bucket_middle(struct bucket
*b
, unsigned char *id_return
)
538 int bit1
= lowbit(b
->first
);
539 int bit2
= b
->next
? lowbit(b
->next
->first
) : -1;
540 int bit
= MAX(bit1
, bit2
) + 1;
545 memcpy(id_return
, b
->first
, 20);
546 id_return
[bit
/ 8] |= (0x80 >> (bit
% 8));
550 /* Return a random id within a bucket. */
552 bucket_random(struct bucket
*b
, unsigned char *id_return
)
554 int bit1
= lowbit(b
->first
);
555 int bit2
= b
->next
? lowbit(b
->next
->first
) : -1;
556 int bit
= MAX(bit1
, bit2
) + 1;
560 memcpy(id_return
, b
->first
, 20);
564 memcpy(id_return
, b
->first
, bit
/ 8);
565 id_return
[bit
/ 8] = b
->first
[bit
/ 8] & (0xFF00 >> (bit
% 8));
566 id_return
[bit
/ 8] |= random() & 0xFF >> (bit
% 8);
567 for(i
= bit
/ 8 + 1; i
< 20; i
++)
568 id_return
[i
] = random() & 0xFF;
572 /* Insert a new node into a bucket. */
574 insert_node(struct node
*node
)
576 struct bucket
*b
= find_bucket(node
->id
, node
->ss
.ss_family
);
581 node
->next
= b
->nodes
;
587 /* This is our definition of a known-good node. */
589 node_good(struct node
*node
)
593 node
->reply_time
>= now
.tv_sec
- 7200 &&
594 node
->time
>= now
.tv_sec
- 900;
597 /* Our transaction-ids are 4-bytes long, with the first two bytes identi-
598 fying the kind of request, and the remaining two a sequence number in
602 make_tid(unsigned char *tid_return
, const char *prefix
, unsigned short seqno
)
604 tid_return
[0] = prefix
[0] & 0xFF;
605 tid_return
[1] = prefix
[1] & 0xFF;
606 memcpy(tid_return
+ 2, &seqno
, 2);
610 tid_match(const unsigned char *tid
, const char *prefix
,
611 unsigned short *seqno_return
)
613 if(tid
[0] == (prefix
[0] & 0xFF) && tid
[1] == (prefix
[1] & 0xFF)) {
615 memcpy(seqno_return
, tid
+ 2, 2);
621 /* Every bucket caches the address of a likely node. Ping it. */
623 send_cached_ping(struct bucket
*b
)
625 unsigned char tid
[4];
627 /* We set family to 0 when there's no cached node. */
628 if(b
->cached
.ss_family
== 0)
631 debugf("Sending ping to cached node.\n");
632 make_tid(tid
, "pn", 0);
633 rc
= send_ping((struct sockaddr
*)&b
->cached
, b
->cachedlen
, tid
, 4);
634 b
->cached
.ss_family
= 0;
639 /* Split a bucket into two equal parts. */
640 static struct bucket
*
641 split_bucket(struct bucket
*b
)
646 unsigned char new_id
[20];
648 rc
= bucket_middle(b
, new_id
);
652 new = calloc(1, sizeof(struct bucket
));
660 memcpy(new->first
, new_id
, 20);
677 /* Called whenever we send a request to a node. */
679 pinged(struct node
*n
, struct bucket
*b
)
682 n
->pinged_time
= now
.tv_sec
;
684 send_cached_ping(b
? b
: find_bucket(n
->id
, n
->ss
.ss_family
));
687 /* We just learnt about a node, not necessarily a new one. Confirm is 1 if
688 the node sent a message, 2 if it sent us a reply. */
690 new_node(const unsigned char *id
, const struct sockaddr
*sa
, int salen
,
693 struct bucket
*b
= find_bucket(id
, sa
->sa_family
);
700 if(id_cmp(id
, myid
) == 0)
706 mybucket
= in_bucket(myid
, b
);
709 b
->time
= now
.tv_sec
;
713 if(id_cmp(n
->id
, id
) == 0) {
714 if(confirm
|| n
->time
< now
.tv_sec
- 15 * 60) {
715 /* Known node. Update stuff. */
716 memcpy((struct sockaddr
*)&n
->ss
, sa
, salen
);
718 n
->time
= now
.tv_sec
;
720 n
->reply_time
= now
.tv_sec
;
733 if(sa
->sa_family
== AF_INET
)
734 mybucket_grow_time
= now
.tv_sec
;
736 mybucket6_grow_time
= now
.tv_sec
;
739 /* First, try to get rid of a known-bad node. */
742 if(n
->pinged
>= 3 && n
->pinged_time
< now
.tv_sec
- 15) {
743 memcpy(n
->id
, id
, 20);
744 memcpy((struct sockaddr
*)&n
->ss
, sa
, salen
);
745 n
->time
= confirm
? now
.tv_sec
: 0;
746 n
->reply_time
= confirm
>= 2 ? now
.tv_sec
: 0;
755 /* Bucket full. Ping a dubious node */
759 /* Pick the first dubious node that we haven't pinged in the
760 last 15 seconds. This gives nodes the time to reply, but
761 tends to concentrate on the same nodes, so that we get rid
762 of bad nodes fast. */
765 if(n
->pinged_time
< now
.tv_sec
- 15) {
766 unsigned char tid
[4];
767 debugf("Sending ping to dubious node.\n");
768 make_tid(tid
, "pn", 0);
769 send_ping((struct sockaddr
*)&n
->ss
, n
->sslen
,
772 n
->pinged_time
= now
.tv_sec
;
783 /* If there's only one bucket, split eagerly. This is
784 incorrect unless there's more than 8 nodes in the DHT. */
785 else if(b
->af
== AF_INET
&& buckets
->next
== NULL
)
787 else if(b
->af
== AF_INET6
&& buckets6
->next
== NULL
)
792 debugf("Splitting.\n");
794 return new_node(id
, sa
, salen
, confirm
);
797 /* No space for this node. Cache it away for later. */
798 if(confirm
|| b
->cached
.ss_family
== 0) {
799 memcpy(&b
->cached
, sa
, salen
);
800 b
->cachedlen
= salen
;
806 /* Create a new node. */
807 n
= calloc(1, sizeof(struct node
));
810 memcpy(n
->id
, id
, 20);
811 memcpy(&n
->ss
, sa
, salen
);
813 n
->time
= confirm
? now
.tv_sec
: 0;
814 n
->reply_time
= confirm
>= 2 ? now
.tv_sec
: 0;
821 /* Called periodically to purge known-bad nodes. Note that we're very
822 conservative here: broken nodes in the table don't do much harm, we'll
823 recover as soon as we find better ones. */
825 expire_buckets(struct bucket
*b
)
831 while(b
->nodes
&& b
->nodes
->pinged
>= 4) {
841 while(p
->next
&& p
->next
->pinged
>= 4) {
856 expire_stuff_time
= now
.tv_sec
+ 120 + random() % 240;
860 /* While a search is in progress, we don't necessarily keep the nodes being
861 walked in the main bucket table. A search in progress is identified by
862 a unique transaction id, a short (and hence small enough to fit in the
863 transaction id of the protocol packets). */
865 static struct search
*
866 find_search(unsigned short tid
, int af
)
868 struct search
*sr
= searches
;
870 if(sr
->tid
== tid
&& sr
->af
== af
)
877 /* A search contains a list of nodes, sorted by decreasing distance to the
878 target. We just got a new candidate, insert it at the right spot or
882 insert_search_node(unsigned char *id
,
883 const struct sockaddr
*sa
, int salen
,
884 struct search
*sr
, int replied
,
885 unsigned char *token
, int token_len
)
887 struct search_node
*n
;
890 if(sa
->sa_family
!= sr
->af
) {
891 debugf("Attempted to insert node in the wrong family.\n");
895 for(i
= 0; i
< sr
->numnodes
; i
++) {
896 if(id_cmp(id
, sr
->nodes
[i
].id
) == 0) {
900 if(xorcmp(id
, sr
->nodes
[i
].id
, sr
->id
) < 0)
904 if(i
== SEARCH_NODES
)
907 if(sr
->numnodes
< SEARCH_NODES
)
910 for(j
= sr
->numnodes
- 1; j
> i
; j
--) {
911 sr
->nodes
[j
] = sr
->nodes
[j
- 1];
916 memset(n
, 0, sizeof(struct search_node
));
917 memcpy(n
->id
, id
, 20);
920 memcpy(&n
->ss
, sa
, salen
);
925 n
->reply_time
= now
.tv_sec
;
930 if(token_len
>= 40) {
931 debugf("Eek! Overlong token.\n");
933 memcpy(n
->token
, token
, token_len
);
934 n
->token_len
= token_len
;
942 flush_search_node(struct search_node
*n
, struct search
*sr
)
944 int i
= n
- sr
->nodes
, j
;
945 for(j
= i
; j
< sr
->numnodes
- 1; j
++)
946 sr
->nodes
[j
] = sr
->nodes
[j
+ 1];
951 expire_searches(void)
953 struct search
*sr
= searches
, *previous
= NULL
;
956 struct search
*next
= sr
->next
;
957 if(sr
->step_time
< now
.tv_sec
- DHT_SEARCH_EXPIRE_TIME
) {
959 previous
->next
= next
;
971 /* This must always return 0 or 1, never -1, not even on failure (see below). */
973 search_send_get_peers(struct search
*sr
, struct search_node
*n
)
976 unsigned char tid
[4];
980 for(i
= 0; i
< sr
->numnodes
; i
++) {
981 if(sr
->nodes
[i
].pinged
< 3 && !sr
->nodes
[i
].replied
&&
982 sr
->nodes
[i
].request_time
< now
.tv_sec
- 15)
987 if(!n
|| n
->pinged
>= 3 || n
->replied
||
988 n
->request_time
>= now
.tv_sec
- 15)
991 debugf("Sending get_peers.\n");
992 make_tid(tid
, "gp", sr
->tid
);
993 send_get_peers((struct sockaddr
*)&n
->ss
, n
->sslen
, tid
, 4, sr
->id
, -1,
994 n
->reply_time
>= now
.tv_sec
- 15);
996 n
->request_time
= now
.tv_sec
;
997 /* If the node happens to be in our main routing table, mark it
999 node
= find_node(n
->id
, n
->ss
.ss_family
);
1000 if(node
) pinged(node
, NULL
);
1004 /* When a search is in progress, we periodically call search_step to send
1005 further requests. */
1007 search_step(struct search
*sr
, dht_callback
*callback
, void *closure
)
1012 /* Check if the first 8 live nodes have replied. */
1014 for(i
= 0; i
< sr
->numnodes
&& j
< 8; i
++) {
1015 struct search_node
*n
= &sr
->nodes
[i
];
1031 for(i
= 0; i
< sr
->numnodes
&& j
< 8; i
++) {
1032 struct search_node
*n
= &sr
->nodes
[i
];
1034 unsigned char tid
[4];
1037 /* A proposed extension to the protocol consists in
1038 omitting the token when storage tables are full. While
1039 I don't think this makes a lot of sense -- just sending
1040 a positive reply is just as good --, let's deal with it. */
1041 if(n
->token_len
== 0)
1045 debugf("Sending announce_peer.\n");
1046 make_tid(tid
, "ap", sr
->tid
);
1047 send_announce_peer((struct sockaddr
*)&n
->ss
,
1048 sizeof(struct sockaddr_storage
),
1049 tid
, 4, sr
->id
, sr
->port
,
1050 n
->token
, n
->token_len
,
1051 n
->reply_time
>= now
.tv_sec
- 15);
1053 n
->request_time
= now
.tv_sec
;
1054 node
= find_node(n
->id
, n
->ss
.ss_family
);
1055 if(node
) pinged(node
, NULL
);
1062 sr
->step_time
= now
.tv_sec
;
1066 if(sr
->step_time
+ 15 >= now
.tv_sec
)
1070 for(i
= 0; i
< sr
->numnodes
; i
++) {
1071 j
+= search_send_get_peers(sr
, &sr
->nodes
[i
]);
1075 sr
->step_time
= now
.tv_sec
;
1081 (*callback
)(closure
,
1083 DHT_EVENT_SEARCH_DONE
: DHT_EVENT_SEARCH_DONE6
,
1085 sr
->step_time
= now
.tv_sec
;
1088 static struct search
*
1091 struct search
*sr
, *oldest
= NULL
;
1093 /* Find the oldest done search */
1097 (oldest
== NULL
|| oldest
->step_time
> sr
->step_time
))
1102 /* The oldest slot is expired. */
1103 if(oldest
&& oldest
->step_time
< now
.tv_sec
- DHT_SEARCH_EXPIRE_TIME
)
1106 /* Allocate a new slot. */
1107 if(numsearches
< DHT_MAX_SEARCHES
) {
1108 sr
= calloc(1, sizeof(struct search
));
1110 sr
->next
= searches
;
1117 /* Oh, well, never mind. Reuse the oldest slot. */
1121 /* Insert the contents of a bucket into a search structure. */
1123 insert_search_bucket(struct bucket
*b
, struct search
*sr
)
1128 insert_search_node(n
->id
, (struct sockaddr
*)&n
->ss
, n
->sslen
,
1134 /* Start a search. If port is non-zero, perform an announce when the
1135 search is complete. */
1137 dht_search(const unsigned char *id
, int port
, int af
,
1138 dht_callback
*callback
, void *closure
)
1141 struct bucket
*b
= find_bucket(id
, af
);
1144 errno
= EAFNOSUPPORT
;
1150 if(sr
->af
== af
&& id_cmp(sr
->id
, id
) == 0)
1156 /* We're reusing data from an old search. Reusing the same tid
1157 means that we can merge replies for both searches. */
1161 for(i
= 0; i
< sr
->numnodes
; i
++) {
1162 struct search_node
*n
;
1164 /* Discard any doubtful nodes. */
1165 if(n
->pinged
>= 3 || n
->reply_time
< now
.tv_sec
- 7200) {
1166 flush_search_node(n
, sr
);
1181 sr
->tid
= search_id
++;
1183 memcpy(sr
->id
, id
, 20);
1190 insert_search_bucket(b
, sr
);
1192 if(sr
->numnodes
< SEARCH_NODES
) {
1193 struct bucket
*p
= previous_bucket(b
);
1195 insert_search_bucket(b
->next
, sr
);
1197 insert_search_bucket(p
, sr
);
1199 if(sr
->numnodes
< SEARCH_NODES
)
1200 insert_search_bucket(find_bucket(myid
, af
), sr
);
1202 search_step(sr
, callback
, closure
);
1203 search_time
= now
.tv_sec
;
1207 /* A struct storage stores all the stored peer addresses for a given info
1210 static struct storage
*
1211 find_storage(const unsigned char *id
)
1213 struct storage
*st
= storage
;
1216 if(id_cmp(id
, st
->id
) == 0)
1224 storage_store(const unsigned char *id
,
1225 const struct sockaddr
*sa
, unsigned short port
)
1231 if(sa
->sa_family
== AF_INET
) {
1232 struct sockaddr_in
*sin
= (struct sockaddr_in
*)sa
;
1233 ip
= (unsigned char*)&sin
->sin_addr
;
1235 } else if(sa
->sa_family
== AF_INET6
) {
1236 struct sockaddr_in6
*sin6
= (struct sockaddr_in6
*)sa
;
1237 ip
= (unsigned char*)&sin6
->sin6_addr
;
1243 st
= find_storage(id
);
1246 if(numstorage
>= DHT_MAX_HASHES
)
1248 st
= calloc(1, sizeof(struct storage
));
1249 if(st
== NULL
) return -1;
1250 memcpy(st
->id
, id
, 20);
1256 for(i
= 0; i
< st
->numpeers
; i
++) {
1257 if(st
->peers
[i
].port
== port
&& st
->peers
[i
].len
== len
&&
1258 memcmp(st
->peers
[i
].ip
, ip
, len
) == 0)
1262 if(i
< st
->numpeers
) {
1263 /* Already there, only need to refresh */
1264 st
->peers
[i
].time
= now
.tv_sec
;
1268 if(i
>= st
->maxpeers
) {
1269 /* Need to expand the array. */
1270 struct peer
*new_peers
;
1272 if(st
->maxpeers
>= DHT_MAX_PEERS
)
1274 n
= st
->maxpeers
== 0 ? 2 : 2 * st
->maxpeers
;
1275 n
= MIN(n
, DHT_MAX_PEERS
);
1276 new_peers
= realloc(st
->peers
, n
* sizeof(struct peer
));
1277 if(new_peers
== NULL
)
1279 st
->peers
= new_peers
;
1282 p
= &st
->peers
[st
->numpeers
++];
1283 p
->time
= now
.tv_sec
;
1285 memcpy(p
->ip
, ip
, len
);
1292 expire_storage(void)
1294 struct storage
*st
= storage
, *previous
= NULL
;
1297 while(i
< st
->numpeers
) {
1298 if(st
->peers
[i
].time
< now
.tv_sec
- 32 * 60) {
1299 if(i
!= st
->numpeers
- 1)
1300 st
->peers
[i
] = st
->peers
[st
->numpeers
- 1];
1307 if(st
->numpeers
== 0) {
1310 previous
->next
= st
->next
;
1315 st
= previous
->next
;
1319 if(numstorage
< 0) {
1320 debugf("Eek... numstorage became negative.\n");
1331 /* We've just found out that a node is buggy. */
1333 broken_node(const unsigned char *id
, const struct sockaddr
*sa
, int salen
)
1337 debugf("Blacklisting broken node.\n");
1342 /* Make the node easy to discard. */
1343 n
= find_node(id
, sa
->sa_family
);
1348 /* Discard it from any searches in progress. */
1351 for(i
= 0; i
< sr
->numnodes
; i
++)
1352 if(id_cmp(sr
->nodes
[i
].id
, id
) == 0)
1353 flush_search_node(&sr
->nodes
[i
], sr
);
1357 /* And make sure we don't hear from it again. */
1358 memcpy(&blacklist
[next_blacklisted
], sa
, salen
);
1359 next_blacklisted
= (next_blacklisted
+ 1) % DHT_MAX_BLACKLISTED
;
1363 rotate_secrets(void)
1367 rotate_secrets_time
= now
.tv_sec
+ 900 + random() % 1800;
1369 memcpy(oldsecret
, secret
, sizeof(secret
));
1370 rc
= dht_random_bytes(secret
, sizeof(secret
));
1379 #define TOKEN_SIZE 8
1383 make_token(const struct sockaddr
*sa
, int old
, unsigned char *token_return
)
1387 unsigned short port
;
1389 if(sa
->sa_family
== AF_INET
) {
1390 struct sockaddr_in
*sin
= (struct sockaddr_in
*)sa
;
1391 ip
= &sin
->sin_addr
;
1393 port
= htons(sin
->sin_port
);
1394 } else if(sa
->sa_family
== AF_INET6
) {
1395 struct sockaddr_in6
*sin6
= (struct sockaddr_in6
*)sa
;
1396 ip
= &sin6
->sin6_addr
;
1398 port
= htons(sin6
->sin6_port
);
1403 dht_hash(token_return
, TOKEN_SIZE
,
1404 old
? oldsecret
: secret
, sizeof(secret
),
1405 ip
, iplen
, (unsigned char*)&port
, 2);
1408 token_match(const unsigned char *token
, int token_len
,
1409 const struct sockaddr
*sa
)
1411 unsigned char t
[TOKEN_SIZE
];
1412 if(token_len
!= TOKEN_SIZE
)
1414 make_token(sa
, 0, t
);
1415 if(memcmp(t
, token
, TOKEN_SIZE
) == 0)
1417 make_token(sa
, 1, t
);
1418 if(memcmp(t
, token
, TOKEN_SIZE
) == 0)
1424 dht_nodes(int af
, int *good_return
, int *dubious_return
, int *cached_return
,
1425 int *incoming_return
)
1427 int good
= 0, dubious
= 0, cached
= 0, incoming
= 0;
1428 struct bucket
*b
= af
== AF_INET
? buckets
: buckets6
;
1431 struct node
*n
= b
->nodes
;
1435 if(n
->time
> n
->reply_time
)
1442 if(b
->cached
.ss_family
> 0)
1447 *good_return
= good
;
1449 *dubious_return
= dubious
;
1451 *cached_return
= cached
;
1453 *incoming_return
= incoming
;
1454 return good
+ dubious
;
1458 dump_bucket(FILE *f
, struct bucket
*b
)
1460 struct node
*n
= b
->nodes
;
1461 fprintf(f
, "Bucket ");
1462 print_hex(f
, b
->first
, 20);
1463 fprintf(f
, " count %d age %d%s%s:\n",
1464 b
->count
, (int)(now
.tv_sec
- b
->time
),
1465 in_bucket(myid
, b
) ? " (mine)" : "",
1466 b
->cached
.ss_family
? " (cached)" : "");
1469 unsigned short port
;
1470 fprintf(f
, " Node ");
1471 print_hex(f
, n
->id
, 20);
1472 if(n
->ss
.ss_family
== AF_INET
) {
1473 struct sockaddr_in
*sin
= (struct sockaddr_in
*)&n
->ss
;
1474 inet_ntop(AF_INET
, &sin
->sin_addr
, buf
, 512);
1475 port
= ntohs(sin
->sin_port
);
1476 } else if(n
->ss
.ss_family
== AF_INET6
) {
1477 struct sockaddr_in6
*sin6
= (struct sockaddr_in6
*)&n
->ss
;
1478 inet_ntop(AF_INET6
, &sin6
->sin6_addr
, buf
, 512);
1479 port
= ntohs(sin6
->sin6_port
);
1481 snprintf(buf
, 512, "unknown(%d)", n
->ss
.ss_family
);
1485 if(n
->ss
.ss_family
== AF_INET6
)
1486 fprintf(f
, " [%s]:%d ", buf
, port
);
1488 fprintf(f
, " %s:%d ", buf
, port
);
1489 if(n
->time
!= n
->reply_time
)
1490 fprintf(f
, "age %ld, %ld",
1491 (long)(now
.tv_sec
- n
->time
),
1492 (long)(now
.tv_sec
- n
->reply_time
));
1494 fprintf(f
, "age %ld", (long)(now
.tv_sec
- n
->time
));
1496 fprintf(f
, " (%d)", n
->pinged
);
1498 fprintf(f
, " (good)");
1506 dht_dump_tables(FILE *f
)
1510 struct storage
*st
= storage
;
1511 struct search
*sr
= searches
;
1513 fprintf(f
, "My id ");
1514 print_hex(f
, myid
, 20);
1532 fprintf(f
, "\nSearch%s id ", sr
->af
== AF_INET6
? " (IPv6)" : "");
1533 print_hex(f
, sr
->id
, 20);
1534 fprintf(f
, " age %d%s\n", (int)(now
.tv_sec
- sr
->step_time
),
1535 sr
->done
? " (done)" : "");
1536 for(i
= 0; i
< sr
->numnodes
; i
++) {
1537 struct search_node
*n
= &sr
->nodes
[i
];
1538 fprintf(f
, "Node %d id ", i
);
1539 print_hex(f
, n
->id
, 20);
1540 fprintf(f
, " bits %d age ", common_bits(sr
->id
, n
->id
));
1542 fprintf(f
, "%d, ", (int)(now
.tv_sec
- n
->request_time
));
1543 fprintf(f
, "%d", (int)(now
.tv_sec
- n
->reply_time
));
1545 fprintf(f
, " (%d)", n
->pinged
);
1546 fprintf(f
, "%s%s.\n",
1547 find_node(n
->id
, AF_INET
) ? " (known)" : "",
1548 n
->replied
? " (replied)" : "");
1554 fprintf(f
, "\nStorage ");
1555 print_hex(f
, st
->id
, 20);
1556 fprintf(f
, " %d/%d nodes:", st
->numpeers
, st
->maxpeers
);
1557 for(i
= 0; i
< st
->numpeers
; i
++) {
1559 if(st
->peers
[i
].len
== 4) {
1560 inet_ntop(AF_INET
, st
->peers
[i
].ip
, buf
, 100);
1561 } else if(st
->peers
[i
].len
== 16) {
1563 inet_ntop(AF_INET6
, st
->peers
[i
].ip
, buf
+ 1, 98);
1568 fprintf(f
, " %s:%u (%ld)",
1569 buf
, st
->peers
[i
].port
,
1570 (long)(now
.tv_sec
- st
->peers
[i
].time
));
1580 dht_init(int s
, int s6
, const unsigned char *id
, const unsigned char *v
)
1584 if(dht_socket
>= 0 || dht_socket6
>= 0 || buckets
|| buckets6
) {
1596 buckets
= calloc(sizeof(struct bucket
), 1);
1599 buckets
->af
= AF_INET
;
1601 rc
= set_nonblocking(s
, 1);
1607 buckets6
= calloc(sizeof(struct bucket
), 1);
1608 if(buckets6
== NULL
)
1610 buckets6
->af
= AF_INET6
;
1612 rc
= set_nonblocking(s6
, 1);
1617 memcpy(myid
, id
, 20);
1619 memcpy(my_v
, "1:v4:", 5);
1620 memcpy(my_v
+ 5, v
, 4);
1626 gettimeofday(&now
, NULL
);
1628 mybucket_grow_time
= now
.tv_sec
;
1629 mybucket6_grow_time
= now
.tv_sec
;
1630 confirm_nodes_time
= now
.tv_sec
+ random() % 3;
1632 search_id
= random() & 0xFFFF;
1635 next_blacklisted
= 0;
1637 token_bucket_time
= now
.tv_sec
;
1638 token_bucket_tokens
= MAX_TOKEN_BUCKET_TOKENS
;
1640 memset(secret
, 0, sizeof(secret
));
1641 rc
= rotate_secrets();
1648 expire_buckets(buckets
);
1649 expire_buckets(buckets6
);
1662 if(dht_socket
< 0 && dht_socket6
< 0) {
1671 struct bucket
*b
= buckets
;
1674 struct node
*n
= b
->nodes
;
1682 struct bucket
*b
= buckets6
;
1685 struct node
*n
= b
->nodes
;
1693 struct storage
*st
= storage
;
1694 storage
= storage
->next
;
1700 struct search
*sr
= searches
;
1701 searches
= searches
->next
;
1708 /* Rate control for requests we receive. */
1713 if(token_bucket_tokens
== 0) {
1714 token_bucket_tokens
= MIN(MAX_TOKEN_BUCKET_TOKENS
,
1715 100 * (now
.tv_sec
- token_bucket_time
));
1716 token_bucket_time
= now
.tv_sec
;
1719 if(token_bucket_tokens
== 0)
1722 token_bucket_tokens
--;
1727 neighbourhood_maintenance(int af
)
1729 unsigned char id
[20];
1730 struct bucket
*b
= find_bucket(myid
, af
);
1737 memcpy(id
, myid
, 20);
1738 id
[19] = random() & 0xFF;
1740 if(q
->next
&& (q
->count
== 0 || (random() & 7) == 0))
1742 if(q
->count
== 0 || (random() & 7) == 0) {
1744 r
= previous_bucket(b
);
1745 if(r
&& r
->count
> 0)
1750 /* Since our node-id is the same in both DHTs, it's probably
1751 profitable to query both families. */
1752 int want
= dht_socket
>= 0 && dht_socket6
>= 0 ? (WANT4
| WANT6
) : -1;
1755 unsigned char tid
[4];
1756 debugf("Sending find_node for%s neighborhood maintenance.\n",
1757 af
== AF_INET6
? " IPv6" : "");
1758 make_tid(tid
, "fn", 0);
1759 send_find_node((struct sockaddr
*)&n
->ss
, n
->sslen
,
1761 n
->reply_time
>= now
.tv_sec
- 15);
1770 bucket_maintenance(int af
)
1774 b
= af
== AF_INET
? buckets
: buckets6
;
1778 if(b
->time
< now
.tv_sec
- 600) {
1779 /* This bucket hasn't seen any positive confirmation for a long
1780 time. Pick a random id in this bucket's range, and send
1781 a request to a random node. */
1782 unsigned char id
[20];
1786 rc
= bucket_random(b
, id
);
1788 memcpy(id
, b
->first
, 20);
1791 /* If the bucket is empty, we try to fill it from a neighbour.
1792 We also sometimes do it gratuitiously to recover from
1793 buckets full of broken nodes. */
1794 if(q
->next
&& (q
->count
== 0 || (random() & 7) == 0))
1796 if(q
->count
== 0 || (random() & 7) == 0) {
1798 r
= previous_bucket(b
);
1799 if(r
&& r
->count
> 0)
1806 unsigned char tid
[4];
1809 if(dht_socket
>= 0 && dht_socket6
>= 0) {
1810 struct bucket
*otherbucket
;
1812 find_bucket(id
, af
== AF_INET
? AF_INET6
: AF_INET
);
1813 if(otherbucket
&& otherbucket
->count
< 8)
1814 /* The corresponding bucket in the other family
1815 is emptyish -- querying both is useful. */
1816 want
= WANT4
| WANT6
;
1817 else if(random() % 37 == 0)
1818 /* Most of the time, this just adds overhead.
1819 However, it might help stitch back one of
1820 the DHTs after a network collapse, so query
1821 both, but only very occasionally. */
1822 want
= WANT4
| WANT6
;
1825 debugf("Sending find_node for%s bucket maintenance.\n",
1826 af
== AF_INET6
? " IPv6" : "");
1827 make_tid(tid
, "fn", 0);
1828 send_find_node((struct sockaddr
*)&n
->ss
, n
->sslen
,
1830 n
->reply_time
>= now
.tv_sec
- 15);
1832 /* In order to avoid sending queries back-to-back,
1833 give up for now and reschedule us soon. */
1844 dht_periodic(const void *buf
, size_t buflen
,
1845 const struct sockaddr
*from
, int fromlen
,
1847 dht_callback
*callback
, void *closure
)
1851 gettimeofday(&now
, NULL
);
1855 unsigned char tid
[16], id
[20], info_hash
[20], target
[20];
1856 unsigned char nodes
[256], nodes6
[1024], token
[128];
1857 int tid_len
= 16, token_len
= 128;
1858 int nodes_len
= 256, nodes6_len
= 1024;
1859 unsigned short port
;
1860 unsigned char values
[2048], values6
[2048];
1861 int values_len
= 2048, values6_len
= 2048;
1863 unsigned short ttid
;
1865 if(is_martian(from
))
1868 for(i
= 0; i
< DHT_MAX_BLACKLISTED
; i
++) {
1869 if(memcmp(&blacklist
[i
], from
, fromlen
) == 0) {
1870 debugf("Received packet from blacklisted node.\n");
1875 /* See parse_message. */
1877 if(((char*)buf
)[buflen
] != '\0') {
1878 debugf("Unterminated message.\n");
1883 message
= parse_message(buf
, buflen
, tid
, &tid_len
, id
, info_hash
,
1884 target
, &port
, token
, &token_len
,
1885 nodes
, &nodes_len
, nodes6
, &nodes6_len
,
1886 values
, &values_len
, values6
, &values6_len
,
1889 if(message
< 0 || message
== ERROR
|| id_cmp(id
, zeroes
) == 0) {
1890 debugf("Unparseable message: ");
1891 debug_printable(buf
, buflen
);
1896 if(id_cmp(id
, myid
) == 0) {
1897 debugf("Received message from self.\n");
1901 if(message
> REPLY
) {
1902 /* Rate limit requests. */
1903 if(!token_bucket()) {
1904 debugf("Dropping request due to rate limiting.\n");
1912 debugf("Broken node truncates transaction ids: ");
1913 debug_printable(buf
, buflen
);
1915 /* This is really annoying, as it means that we will
1916 time-out all our searches that go through this node.
1918 broken_node(id
, from
, fromlen
);
1921 if(tid_match(tid
, "pn", NULL
)) {
1923 new_node(id
, from
, fromlen
, 2);
1924 } else if(tid_match(tid
, "fn", NULL
) ||
1925 tid_match(tid
, "gp", NULL
)) {
1927 struct search
*sr
= NULL
;
1928 if(tid_match(tid
, "gp", &ttid
)) {
1930 sr
= find_search(ttid
, from
->sa_family
);
1932 debugf("Nodes found (%d+%d)%s!\n", nodes_len
/26, nodes6_len
/38,
1933 gp
? " for get_peers" : "");
1934 if(nodes_len
% 26 != 0 || nodes6_len
% 38 != 0) {
1935 debugf("Unexpected length for node info!\n");
1936 broken_node(id
, from
, fromlen
);
1937 } else if(gp
&& sr
== NULL
) {
1938 debugf("Unknown search!\n");
1939 new_node(id
, from
, fromlen
, 1);
1942 new_node(id
, from
, fromlen
, 2);
1943 for(i
= 0; i
< nodes_len
/ 26; i
++) {
1944 unsigned char *ni
= nodes
+ i
* 26;
1945 struct sockaddr_in sin
;
1946 if(id_cmp(ni
, myid
) == 0)
1948 memset(&sin
, 0, sizeof(sin
));
1949 sin
.sin_family
= AF_INET
;
1950 memcpy(&sin
.sin_addr
, ni
+ 20, 4);
1951 memcpy(&sin
.sin_port
, ni
+ 24, 2);
1952 new_node(ni
, (struct sockaddr
*)&sin
, sizeof(sin
), 0);
1953 if(sr
&& sr
->af
== AF_INET
) {
1954 insert_search_node(ni
,
1955 (struct sockaddr
*)&sin
,
1960 for(i
= 0; i
< nodes6_len
/ 38; i
++) {
1961 unsigned char *ni
= nodes6
+ i
* 38;
1962 struct sockaddr_in6 sin6
;
1963 if(id_cmp(ni
, myid
) == 0)
1965 memset(&sin6
, 0, sizeof(sin6
));
1966 sin6
.sin6_family
= AF_INET6
;
1967 memcpy(&sin6
.sin6_addr
, ni
+ 20, 16);
1968 memcpy(&sin6
.sin6_port
, ni
+ 36, 2);
1969 new_node(ni
, (struct sockaddr
*)&sin6
, sizeof(sin6
), 0);
1970 if(sr
&& sr
->af
== AF_INET6
) {
1971 insert_search_node(ni
,
1972 (struct sockaddr
*)&sin6
,
1978 /* Since we received a reply, the number of
1979 requests in flight has decreased. Let's push
1981 search_send_get_peers(sr
, NULL
);
1984 insert_search_node(id
, from
, fromlen
, sr
,
1985 1, token
, token_len
);
1986 if(values_len
> 0 || values6_len
> 0) {
1987 debugf("Got values (%d+%d)!\n",
1988 values_len
/ 6, values6_len
/ 18);
1991 (*callback
)(closure
, DHT_EVENT_VALUES
, sr
->id
,
1992 (void*)values
, values_len
);
1995 (*callback
)(closure
, DHT_EVENT_VALUES6
, sr
->id
,
1996 (void*)values6
, values6_len
);
2000 } else if(tid_match(tid
, "ap", &ttid
)) {
2002 debugf("Got reply to announce_peer.\n");
2003 sr
= find_search(ttid
, from
->sa_family
);
2005 debugf("Unknown search!\n");
2006 new_node(id
, from
, fromlen
, 1);
2009 new_node(id
, from
, fromlen
, 2);
2010 for(i
= 0; i
< sr
->numnodes
; i
++)
2011 if(id_cmp(sr
->nodes
[i
].id
, id
) == 0) {
2012 sr
->nodes
[i
].request_time
= 0;
2013 sr
->nodes
[i
].reply_time
= now
.tv_sec
;
2014 sr
->nodes
[i
].acked
= 1;
2015 sr
->nodes
[i
].pinged
= 0;
2018 /* See comment for gp above. */
2019 search_send_get_peers(sr
, NULL
);
2022 debugf("Unexpected reply: ");
2023 debug_printable(buf
, buflen
);
2028 debugf("Ping (%d)!\n", tid_len
);
2029 new_node(id
, from
, fromlen
, 1);
2030 debugf("Sending pong.\n");
2031 send_pong(from
, fromlen
, tid
, tid_len
);
2034 debugf("Find node!\n");
2035 new_node(id
, from
, fromlen
, 1);
2036 debugf("Sending closest nodes (%d).\n", want
);
2037 send_closest_nodes(from
, fromlen
,
2038 tid
, tid_len
, target
, want
,
2042 debugf("Get_peers!\n");
2043 new_node(id
, from
, fromlen
, 1);
2044 if(id_cmp(info_hash
, zeroes
) == 0) {
2045 debugf("Eek! Got get_peers with no info_hash.\n");
2046 send_error(from
, fromlen
, tid
, tid_len
,
2047 203, "Get_peers with no info_hash");
2050 struct storage
*st
= find_storage(info_hash
);
2051 unsigned char token
[TOKEN_SIZE
];
2052 make_token(from
, 0, token
);
2053 if(st
&& st
->numpeers
> 0) {
2054 debugf("Sending found%s peers.\n",
2055 from
->sa_family
== AF_INET6
? " IPv6" : "");
2056 send_closest_nodes(from
, fromlen
,
2059 from
->sa_family
, st
,
2062 debugf("Sending nodes for get_peers.\n");
2063 send_closest_nodes(from
, fromlen
,
2064 tid
, tid_len
, info_hash
, want
,
2065 0, NULL
, token
, TOKEN_SIZE
);
2070 debugf("Announce peer!\n");
2071 new_node(id
, from
, fromlen
, 1);
2072 if(id_cmp(info_hash
, zeroes
) == 0) {
2073 debugf("Announce_peer with no info_hash.\n");
2074 send_error(from
, fromlen
, tid
, tid_len
,
2075 203, "Announce_peer with no info_hash");
2078 if(!token_match(token
, token_len
, from
)) {
2079 debugf("Incorrect token for announce_peer.\n");
2080 send_error(from
, fromlen
, tid
, tid_len
,
2081 203, "Announce_peer with wrong token");
2085 debugf("Announce_peer with forbidden port %d.\n", port
);
2086 send_error(from
, fromlen
, tid
, tid_len
,
2087 203, "Announce_peer with forbidden port number");
2090 storage_store(info_hash
, from
, port
);
2091 /* Note that if storage_store failed, we lie to the requestor.
2092 This is to prevent them from backtracking, and hence
2093 polluting the DHT. */
2094 debugf("Sending peer announced.\n");
2095 send_peer_announced(from
, fromlen
, tid
, tid_len
);
2100 if(now
.tv_sec
>= rotate_secrets_time
)
2103 if(now
.tv_sec
>= expire_stuff_time
) {
2104 expire_buckets(buckets
);
2105 expire_buckets(buckets6
);
2110 if(search_time
> 0 && now
.tv_sec
>= search_time
) {
2114 if(!sr
->done
&& sr
->step_time
+ 5 <= now
.tv_sec
) {
2115 search_step(sr
, callback
, closure
);
2125 time_t tm
= sr
->step_time
+ 15 + random() % 10;
2126 if(search_time
== 0 || search_time
> tm
)
2133 if(now
.tv_sec
>= confirm_nodes_time
) {
2136 soon
|= bucket_maintenance(AF_INET
);
2137 soon
|= bucket_maintenance(AF_INET6
);
2140 if(mybucket_grow_time
>= now
.tv_sec
- 150)
2141 soon
|= neighbourhood_maintenance(AF_INET
);
2142 if(mybucket6_grow_time
>= now
.tv_sec
- 150)
2143 soon
|= neighbourhood_maintenance(AF_INET6
);
2146 /* In order to maintain all buckets' age within 600 seconds, worst
2147 case is roughly 27 seconds, assuming the table is 22 bits deep.
2148 We want to keep a margin for neighborhood maintenance, so keep
2149 this within 25 seconds. */
2151 confirm_nodes_time
= now
.tv_sec
+ 5 + random() % 20;
2153 confirm_nodes_time
= now
.tv_sec
+ 60 + random() % 120;
2156 if(confirm_nodes_time
> now
.tv_sec
)
2157 *tosleep
= confirm_nodes_time
- now
.tv_sec
;
2161 if(search_time
> 0) {
2162 if(search_time
<= now
.tv_sec
)
2164 else if(*tosleep
> search_time
- now
.tv_sec
)
2165 *tosleep
= search_time
- now
.tv_sec
;
2172 dht_get_nodes(struct sockaddr_in
*sin
, int *num
,
2173 struct sockaddr_in6
*sin6
, int *num6
)
2181 /* For restoring to work without discarding too many nodes, the list
2182 must start with the contents of our bucket. */
2183 b
= find_bucket(myid
, AF_INET
);
2188 while(n
&& i
< *num
) {
2190 sin
[i
] = *(struct sockaddr_in
*)&n
->ss
;
2197 while(b
&& i
< *num
) {
2198 if(!in_bucket(myid
, b
)) {
2200 while(n
&& i
< *num
) {
2202 sin
[i
] = *(struct sockaddr_in
*)&n
->ss
;
2215 b
= find_bucket(myid
, AF_INET6
);
2220 while(n
&& j
< *num6
) {
2222 sin6
[j
] = *(struct sockaddr_in6
*)&n
->ss
;
2229 while(b
&& j
< *num6
) {
2230 if(!in_bucket(myid
, b
)) {
2232 while(n
&& j
< *num6
) {
2234 sin6
[j
] = *(struct sockaddr_in6
*)&n
->ss
;
2251 dht_insert_node(const unsigned char *id
, struct sockaddr
*sa
, int salen
)
2255 if(sa
->sa_family
!= AF_INET
) {
2256 errno
= EAFNOSUPPORT
;
2260 n
= new_node(id
, (struct sockaddr
*)sa
, salen
, 0);
2265 dht_ping_node(struct sockaddr
*sa
, int salen
)
2267 unsigned char tid
[4];
2269 debugf("Sending ping.\n");
2270 make_tid(tid
, "pn", 0);
2271 return send_ping(sa
, salen
, tid
, 4);
2274 /* We could use a proper bencoding printer and parser, but the format of
2275 DHT messages is fairly stylised, so this seemed simpler. */
2277 #define CHECK(offset, delta, size) \
2278 if(delta < 0 || offset + delta > size) goto fail
2280 #define INC(offset, delta, size) \
2281 CHECK(offset, delta, size); \
2284 #define COPY(buf, offset, src, delta, size) \
2285 CHECK(offset, delta, size); \
2286 memcpy(buf + offset, src, delta); \
2289 #define ADD_V(buf, offset, size) \
2291 COPY(buf, offset, my_v, sizeof(my_v), size); \
2295 dht_send(const void *buf
, size_t len
, int flags
,
2296 const struct sockaddr
*sa
, int salen
)
2303 if(sa
->sa_family
== AF_INET
)
2305 else if(sa
->sa_family
== AF_INET6
)
2311 errno
= EAFNOSUPPORT
;
2315 return sendto(s
, buf
, len
, flags
, sa
, salen
);
2319 send_ping(const struct sockaddr
*sa
, int salen
,
2320 const unsigned char *tid
, int tid_len
)
2324 rc
= snprintf(buf
+ i
, 512 - i
, "d1:ad2:id20:"); INC(i
, rc
, 512);
2325 COPY(buf
, i
, myid
, 20, 512);
2326 rc
= snprintf(buf
+ i
, 512 - i
, "e1:q4:ping1:t%d:", tid_len
);
2328 COPY(buf
, i
, tid
, tid_len
, 512);
2330 rc
= snprintf(buf
+ i
, 512 - i
, "1:y1:qe"); INC(i
, rc
, 512);
2331 return dht_send(buf
, i
, 0, sa
, salen
);
2339 send_pong(const struct sockaddr
*sa
, int salen
,
2340 const unsigned char *tid
, int tid_len
)
2344 rc
= snprintf(buf
+ i
, 512 - i
, "d1:rd2:id20:"); INC(i
, rc
, 512);
2345 COPY(buf
, i
, myid
, 20, 512);
2346 rc
= snprintf(buf
+ i
, 512 - i
, "e1:t%d:", tid_len
); INC(i
, rc
, 512);
2347 COPY(buf
, i
, tid
, tid_len
, 512);
2349 rc
= snprintf(buf
+ i
, 512 - i
, "1:y1:re"); INC(i
, rc
, 512);
2350 return dht_send(buf
, i
, 0, sa
, salen
);
2358 send_find_node(const struct sockaddr
*sa
, int salen
,
2359 const unsigned char *tid
, int tid_len
,
2360 const unsigned char *target
, int want
, int confirm
)
2364 rc
= snprintf(buf
+ i
, 512 - i
, "d1:ad2:id20:"); INC(i
, rc
, 512);
2365 COPY(buf
, i
, myid
, 20, 512);
2366 rc
= snprintf(buf
+ i
, 512 - i
, "6:target20:"); INC(i
, rc
, 512);
2367 COPY(buf
, i
, target
, 20, 512);
2369 rc
= snprintf(buf
+ i
, 512 - i
, "4:wantl%s%se",
2370 (want
& WANT4
) ? "2:n4" : "",
2371 (want
& WANT6
) ? "2:n6" : "");
2374 rc
= snprintf(buf
+ i
, 512 - i
, "e1:q9:find_node1:t%d:", tid_len
);
2376 COPY(buf
, i
, tid
, tid_len
, 512);
2378 rc
= snprintf(buf
+ i
, 512 - i
, "1:y1:qe"); INC(i
, rc
, 512);
2379 return dht_send(buf
, i
, confirm
? MSG_CONFIRM
: 0, sa
, salen
);
2387 send_nodes_peers(const struct sockaddr
*sa
, int salen
,
2388 const unsigned char *tid
, int tid_len
,
2389 const unsigned char *nodes
, int nodes_len
,
2390 const unsigned char *nodes6
, int nodes6_len
,
2391 int af
, struct storage
*st
,
2392 const unsigned char *token
, int token_len
)
2395 int i
= 0, rc
, j0
, j
, k
, len
;
2397 rc
= snprintf(buf
+ i
, 2048 - i
, "d1:rd2:id20:"); INC(i
, rc
, 2048);
2398 COPY(buf
, i
, myid
, 20, 2048);
2400 rc
= snprintf(buf
+ i
, 2048 - i
, "5:nodes%d:", nodes_len
);
2402 COPY(buf
, i
, nodes
, nodes_len
, 2048);
2404 if(nodes6_len
> 0) {
2405 rc
= snprintf(buf
+ i
, 2048 - i
, "6:nodes6%d:", nodes6_len
);
2407 COPY(buf
, i
, nodes6
, nodes6_len
, 2048);
2410 rc
= snprintf(buf
+ i
, 2048 - i
, "5:token%d:", token_len
);
2412 COPY(buf
, i
, token
, token_len
, 2048);
2415 if(st
&& st
->numpeers
> 0) {
2416 /* We treat the storage as a circular list, and serve a randomly
2417 chosen slice. In order to make sure we fit within 1024 octets,
2418 we limit ourselves to 50 peers. */
2420 len
= af
== AF_INET
? 4 : 16;
2421 j0
= random() % st
->numpeers
;
2425 rc
= snprintf(buf
+ i
, 2048 - i
, "6:valuesl"); INC(i
, rc
, 2048);
2427 if(st
->peers
[j
].len
== len
) {
2428 unsigned short swapped
;
2429 swapped
= htons(st
->peers
[j
].port
);
2430 rc
= snprintf(buf
+ i
, 2048 - i
, "%d:", len
+ 2);
2432 COPY(buf
, i
, st
->peers
[j
].ip
, len
, 2048);
2433 COPY(buf
, i
, &swapped
, 2, 2048);
2436 j
= (j
+ 1) % st
->numpeers
;
2437 } while(j
!= j0
&& k
< 50);
2438 rc
= snprintf(buf
+ i
, 2048 - i
, "e"); INC(i
, rc
, 2048);
2441 rc
= snprintf(buf
+ i
, 2048 - i
, "e1:t%d:", tid_len
); INC(i
, rc
, 2048);
2442 COPY(buf
, i
, tid
, tid_len
, 2048);
2443 ADD_V(buf
, i
, 2048);
2444 rc
= snprintf(buf
+ i
, 2048 - i
, "1:y1:re"); INC(i
, rc
, 2048);
2446 return dht_send(buf
, i
, 0, sa
, salen
);
2454 insert_closest_node(unsigned char *nodes
, int numnodes
,
2455 const unsigned char *id
, struct node
*n
)
2459 if(n
->ss
.ss_family
== AF_INET
)
2461 else if(n
->ss
.ss_family
== AF_INET6
)
2466 for(i
= 0; i
< numnodes
; i
++) {
2467 if(id_cmp(n
->id
, nodes
+ size
* i
) == 0)
2469 if(xorcmp(n
->id
, nodes
+ size
* i
, id
) < 0)
2479 if(i
< numnodes
- 1)
2480 memmove(nodes
+ size
* (i
+ 1), nodes
+ size
* i
,
2481 size
* (numnodes
- i
- 1));
2483 if(n
->ss
.ss_family
== AF_INET
) {
2484 struct sockaddr_in
*sin
= (struct sockaddr_in
*)&n
->ss
;
2485 memcpy(nodes
+ size
* i
, n
->id
, 20);
2486 memcpy(nodes
+ size
* i
+ 20, &sin
->sin_addr
, 4);
2487 memcpy(nodes
+ size
* i
+ 24, &sin
->sin_port
, 2);
2488 } else if(n
->ss
.ss_family
== AF_INET6
) {
2489 struct sockaddr_in6
*sin6
= (struct sockaddr_in6
*)&n
->ss
;
2490 memcpy(nodes
+ size
* i
, n
->id
, 20);
2491 memcpy(nodes
+ size
* i
+ 20, &sin6
->sin6_addr
, 16);
2492 memcpy(nodes
+ size
* i
+ 36, &sin6
->sin6_port
, 2);
2501 buffer_closest_nodes(unsigned char *nodes
, int numnodes
,
2502 const unsigned char *id
, struct bucket
*b
)
2504 struct node
*n
= b
->nodes
;
2507 numnodes
= insert_closest_node(nodes
, numnodes
, id
, n
);
2514 send_closest_nodes(const struct sockaddr
*sa
, int salen
,
2515 const unsigned char *tid
, int tid_len
,
2516 const unsigned char *id
, int want
,
2517 int af
, struct storage
*st
,
2518 const unsigned char *token
, int token_len
)
2520 unsigned char nodes
[8 * 26];
2521 unsigned char nodes6
[8 * 38];
2522 int numnodes
= 0, numnodes6
= 0;
2526 want
= sa
->sa_family
== AF_INET
? WANT4
: WANT6
;
2528 if((want
& WANT4
)) {
2529 b
= find_bucket(id
, AF_INET
);
2531 numnodes
= buffer_closest_nodes(nodes
, numnodes
, id
, b
);
2533 numnodes
= buffer_closest_nodes(nodes
, numnodes
, id
, b
->next
);
2534 b
= previous_bucket(b
);
2536 numnodes
= buffer_closest_nodes(nodes
, numnodes
, id
, b
);
2540 if((want
& WANT6
)) {
2541 b
= find_bucket(id
, AF_INET6
);
2543 numnodes6
= buffer_closest_nodes(nodes6
, numnodes6
, id
, b
);
2546 buffer_closest_nodes(nodes6
, numnodes6
, id
, b
->next
);
2547 b
= previous_bucket(b
);
2549 numnodes6
= buffer_closest_nodes(nodes6
, numnodes6
, id
, b
);
2552 debugf(" (%d+%d nodes.)\n", numnodes
, numnodes6
);
2554 return send_nodes_peers(sa
, salen
, tid
, tid_len
,
2555 nodes
, numnodes
* 26,
2556 nodes6
, numnodes6
* 38,
2557 af
, st
, token
, token_len
);
2561 send_get_peers(const struct sockaddr
*sa
, int salen
,
2562 unsigned char *tid
, int tid_len
, unsigned char *infohash
,
2563 int want
, int confirm
)
2568 rc
= snprintf(buf
+ i
, 512 - i
, "d1:ad2:id20:"); INC(i
, rc
, 512);
2569 COPY(buf
, i
, myid
, 20, 512);
2570 rc
= snprintf(buf
+ i
, 512 - i
, "9:info_hash20:"); INC(i
, rc
, 512);
2571 COPY(buf
, i
, infohash
, 20, 512);
2573 rc
= snprintf(buf
+ i
, 512 - i
, "4:wantl%s%se",
2574 (want
& WANT4
) ? "2:n4" : "",
2575 (want
& WANT6
) ? "2:n6" : "");
2578 rc
= snprintf(buf
+ i
, 512 - i
, "e1:q9:get_peers1:t%d:", tid_len
);
2580 COPY(buf
, i
, tid
, tid_len
, 512);
2582 rc
= snprintf(buf
+ i
, 512 - i
, "1:y1:qe"); INC(i
, rc
, 512);
2583 return dht_send(buf
, i
, confirm
? MSG_CONFIRM
: 0, sa
, salen
);
2591 send_announce_peer(const struct sockaddr
*sa
, int salen
,
2592 unsigned char *tid
, int tid_len
,
2593 unsigned char *infohash
, unsigned short port
,
2594 unsigned char *token
, int token_len
, int confirm
)
2599 rc
= snprintf(buf
+ i
, 512 - i
, "d1:ad2:id20:"); INC(i
, rc
, 512);
2600 COPY(buf
, i
, myid
, 20, 512);
2601 rc
= snprintf(buf
+ i
, 512 - i
, "9:info_hash20:"); INC(i
, rc
, 512);
2602 COPY(buf
, i
, infohash
, 20, 512);
2603 rc
= snprintf(buf
+ i
, 512 - i
, "4:porti%ue5:token%d:", (unsigned)port
,
2606 COPY(buf
, i
, token
, token_len
, 512);
2607 rc
= snprintf(buf
+ i
, 512 - i
, "e1:q13:announce_peer1:t%d:", tid_len
);
2609 COPY(buf
, i
, tid
, tid_len
, 512);
2611 rc
= snprintf(buf
+ i
, 512 - i
, "1:y1:qe"); INC(i
, rc
, 512);
2613 return dht_send(buf
, i
, confirm
? 0 : MSG_CONFIRM
, sa
, salen
);
2621 send_peer_announced(const struct sockaddr
*sa
, int salen
,
2622 unsigned char *tid
, int tid_len
)
2627 rc
= snprintf(buf
+ i
, 512 - i
, "d1:rd2:id20:"); INC(i
, rc
, 512);
2628 COPY(buf
, i
, myid
, 20, 512);
2629 rc
= snprintf(buf
+ i
, 512 - i
, "e1:t%d:", tid_len
);
2631 COPY(buf
, i
, tid
, tid_len
, 512);
2633 rc
= snprintf(buf
+ i
, 512 - i
, "1:y1:re"); INC(i
, rc
, 512);
2634 return dht_send(buf
, i
, 0, sa
, salen
);
2642 send_error(const struct sockaddr
*sa
, int salen
,
2643 unsigned char *tid
, int tid_len
,
2644 int code
, const char *message
)
2649 rc
= snprintf(buf
+ i
, 512 - i
, "d1:eli%de%d:",
2650 code
, (int)strlen(message
));
2652 COPY(buf
, i
, message
, (int)strlen(message
), 512);
2653 rc
= snprintf(buf
+ i
, 512 - i
, "e1:t%d:", tid_len
); INC(i
, rc
, 512);
2654 COPY(buf
, i
, tid
, tid_len
, 512);
2656 rc
= snprintf(buf
+ i
, 512 - i
, "1:y1:ee"); INC(i
, rc
, 512);
2657 return dht_send(buf
, i
, 0, sa
, salen
);
2672 dht_memmem(const void *haystack
, size_t haystacklen
,
2673 const void *needle
, size_t needlelen
)
2675 return memmem(haystack
, haystacklen
, needle
, needlelen
);
2681 dht_memmem(const void *haystack
, size_t haystacklen
,
2682 const void *needle
, size_t needlelen
)
2684 const char *h
= haystack
;
2685 const char *n
= needle
;
2688 /* size_t is unsigned */
2689 if(needlelen
> haystacklen
)
2692 for(i
= 0; i
<= haystacklen
- needlelen
; i
++) {
2693 if(memcmp(h
+ i
, n
, needlelen
) == 0)
2694 return (void*)(h
+ i
);
2702 parse_message(const unsigned char *buf
, int buflen
,
2703 unsigned char *tid_return
, int *tid_len
,
2704 unsigned char *id_return
, unsigned char *info_hash_return
,
2705 unsigned char *target_return
, unsigned short *port_return
,
2706 unsigned char *token_return
, int *token_len
,
2707 unsigned char *nodes_return
, int *nodes_len
,
2708 unsigned char *nodes6_return
, int *nodes6_len
,
2709 unsigned char *values_return
, int *values_len
,
2710 unsigned char *values6_return
, int *values6_len
,
2713 const unsigned char *p
;
2715 /* This code will happily crash if the buffer is not NUL-terminated. */
2716 if(buf
[buflen
] != '\0') {
2717 debugf("Eek! parse_message with unterminated buffer.\n");
2721 #define CHECK(ptr, len) \
2722 if(((unsigned char*)ptr) + (len) > (buf) + (buflen)) goto overflow;
2725 p
= dht_memmem(buf
, buflen
, "1:t", 3);
2729 l
= strtol((char*)p
+ 3, &q
, 10);
2730 if(q
&& *q
== ':' && l
> 0 && l
< *tid_len
) {
2732 memcpy(tid_return
, q
+ 1, l
);
2739 p
= dht_memmem(buf
, buflen
, "2:id20:", 7);
2742 memcpy(id_return
, p
+ 7, 20);
2744 memset(id_return
, 0, 20);
2747 if(info_hash_return
) {
2748 p
= dht_memmem(buf
, buflen
, "9:info_hash20:", 14);
2751 memcpy(info_hash_return
, p
+ 14, 20);
2753 memset(info_hash_return
, 0, 20);
2757 p
= dht_memmem(buf
, buflen
, "porti", 5);
2761 l
= strtol((char*)p
+ 5, &q
, 10);
2762 if(q
&& *q
== 'e' && l
> 0 && l
< 0x10000)
2770 p
= dht_memmem(buf
, buflen
, "6:target20:", 11);
2773 memcpy(target_return
, p
+ 11, 20);
2775 memset(target_return
, 0, 20);
2779 p
= dht_memmem(buf
, buflen
, "5:token", 7);
2783 l
= strtol((char*)p
+ 7, &q
, 10);
2784 if(q
&& *q
== ':' && l
> 0 && l
< *token_len
) {
2786 memcpy(token_return
, q
+ 1, l
);
2795 p
= dht_memmem(buf
, buflen
, "5:nodes", 7);
2799 l
= strtol((char*)p
+ 7, &q
, 10);
2800 if(q
&& *q
== ':' && l
> 0 && l
< *nodes_len
) {
2802 memcpy(nodes_return
, q
+ 1, l
);
2811 p
= dht_memmem(buf
, buflen
, "6:nodes6", 8);
2815 l
= strtol((char*)p
+ 8, &q
, 10);
2816 if(q
&& *q
== ':' && l
> 0 && l
< *nodes6_len
) {
2818 memcpy(nodes6_return
, q
+ 1, l
);
2826 if(values_len
|| values6_len
) {
2827 p
= dht_memmem(buf
, buflen
, "6:valuesl", 9);
2829 int i
= p
- buf
+ 9;
2834 l
= strtol((char*)buf
+ i
, &q
, 10);
2835 if(q
&& *q
== ':' && l
> 0) {
2837 i
= q
+ 1 + l
- (char*)buf
;
2839 if(j
+ l
> *values_len
)
2841 memcpy((char*)values_return
+ j
, q
+ 1, l
);
2843 } else if(l
== 18) {
2844 if(j6
+ l
> *values6_len
)
2846 memcpy((char*)values6_return
+ j6
, q
+ 1, l
);
2849 debugf("Received weird value -- %d bytes.\n", (int)l
);
2855 if(i
>= buflen
|| buf
[i
] != 'e')
2856 debugf("eek... unexpected end for values.\n");
2870 p
= dht_memmem(buf
, buflen
, "4:wantl", 7);
2872 int i
= p
- buf
+ 7;
2874 while(buf
[i
] > '0' && buf
[i
] <= '9' && buf
[i
+ 1] == ':' &&
2875 i
+ 2 + buf
[i
] - '0' < buflen
) {
2876 CHECK(buf
+ i
+ 2, buf
[i
] - '0');
2877 if(buf
[i
] == '2' && memcmp(buf
+ i
+ 2, "n4", 2) == 0)
2878 *want_return
|= WANT4
;
2879 else if(buf
[i
] == '2' && memcmp(buf
+ i
+ 2, "n6", 2) == 0)
2880 *want_return
|= WANT6
;
2882 debugf("eek... unexpected want flag (%c)\n", buf
[i
]);
2883 i
+= 2 + buf
[i
] - '0';
2885 if(i
>= buflen
|| buf
[i
] != 'e')
2886 debugf("eek... unexpected end for want.\n");
2894 if(dht_memmem(buf
, buflen
, "1:y1:r", 6))
2896 if(dht_memmem(buf
, buflen
, "1:y1:e", 6))
2898 if(!dht_memmem(buf
, buflen
, "1:y1:q", 6))
2900 if(dht_memmem(buf
, buflen
, "1:q4:ping", 9))
2902 if(dht_memmem(buf
, buflen
, "1:q9:find_node", 14))
2904 if(dht_memmem(buf
, buflen
, "1:q9:get_peers", 14))
2906 if(dht_memmem(buf
, buflen
, "1:q13:announce_peer", 19))
2907 return ANNOUNCE_PEER
;
2911 debugf("Truncated message.\n");