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. */
40 #if !defined(_WIN32) || defined(__MINGW32__)
48 #include <arpa/inet.h>
49 #include <sys/types.h>
50 #include <sys/socket.h>
51 #include <netinet/in.h>
54 #define _WIN32_WINNT 0x0501 /* Windows XP */
57 #define WINVER _WIN32_WINNT
75 #if !defined(_WIN32) || defined(__MINGW32__)
76 #define dht_gettimeofday(_ts, _tz) gettimeofday((_ts), (_tz))
78 extern int dht_gettimeofday(struct timeval
*tv
, struct timezone
*tz
);
84 #define EAFNOSUPPORT WSAEAFNOSUPPORT
92 /* Windows Vista and later already provide the implementation. */
93 #if _WIN32_WINNT < 0x0600
94 extern const char *inet_ntop(int, const void *, char *, socklen_t
);
98 /* There is no snprintf in MSVCRT. */
99 #define snprintf _snprintf
104 /* We set sin_family to 0 to mark unused slots. */
105 #if AF_INET == 0 || AF_INET6 == 0
109 #if defined(__STDC_VERSION__) && __STDC_VERSION__ >= 199901L
111 #elif defined(__GNUC__)
112 #define inline __inline
114 #define restrict __restrict
116 #define restrict /**/
120 #define restrict /**/
123 #define MAX(x, y) ((x) >= (y) ? (x) : (y))
124 #define MIN(x, y) ((x) <= (y) ? (x) : (y))
127 unsigned char id
[20];
128 struct sockaddr_storage ss
;
130 time_t time
; /* time of last message received */
131 time_t reply_time
; /* time of last correct reply received */
132 time_t pinged_time
; /* time of last request */
133 int pinged
; /* how many requests we sent since last reply */
139 unsigned char first
[20];
140 int count
; /* number of nodes */
141 int max_count
; /* max number of nodes for this bucket */
142 time_t time
; /* time of last reply in this bucket */
144 struct sockaddr_storage cached
; /* the address of a likely candidate */
150 unsigned char id
[20];
151 struct sockaddr_storage ss
;
153 time_t request_time
; /* the time of the last unanswered request */
154 time_t reply_time
; /* the time of the last reply */
156 unsigned char token
[40];
158 int replied
; /* whether we have received a reply */
159 int acked
; /* whether they acked our announcement */
162 /* When performing a search, we search for up to SEARCH_NODES closest nodes
163 to the destination, and use the additional ones to backtrack if any of
164 the target 8 turn out to be dead. */
165 #define SEARCH_NODES 14
170 time_t step_time
; /* the time of the last search_step */
171 unsigned char id
[20];
172 unsigned short port
; /* 0 for pure searches */
174 struct search_node nodes
[SEARCH_NODES
];
181 unsigned char ip
[16];
186 /* The maximum number of peers we store for a given hash. */
187 #ifndef DHT_MAX_PEERS
188 #define DHT_MAX_PEERS 2048
191 /* The maximum number of hashes we're willing to track. */
192 #ifndef DHT_MAX_HASHES
193 #define DHT_MAX_HASHES 16384
196 /* The maximum number of searches we keep data about. */
197 #ifndef DHT_MAX_SEARCHES
198 #define DHT_MAX_SEARCHES 1024
201 /* The time after which we consider a search to be expirable. */
202 #ifndef DHT_SEARCH_EXPIRE_TIME
203 #define DHT_SEARCH_EXPIRE_TIME (62 * 60)
206 /* The maximum number of in-flight queries per search. */
207 #ifndef DHT_INFLIGHT_QUERIES
208 #define DHT_INFLIGHT_QUERIES 4
211 /* The retransmit timeout when performing searches. */
212 #ifndef DHT_SEARCH_RETRANSMIT
213 #define DHT_SEARCH_RETRANSMIT 10
217 unsigned char id
[20];
218 int numpeers
, maxpeers
;
220 struct storage
*next
;
223 static struct storage
* find_storage(const unsigned char *id
);
224 static void flush_search_node(struct search_node
*n
, struct search
*sr
);
226 static int send_ping(const struct sockaddr
*sa
, int salen
,
227 const unsigned char *tid
, int tid_len
);
228 static int send_pong(const struct sockaddr
*sa
, int salen
,
229 const unsigned char *tid
, int tid_len
);
230 static int send_find_node(const struct sockaddr
*sa
, int salen
,
231 const unsigned char *tid
, int tid_len
,
232 const unsigned char *target
, int want
, int confirm
);
233 static int send_nodes_peers(const struct sockaddr
*sa
, int salen
,
234 const unsigned char *tid
, int tid_len
,
235 const unsigned char *nodes
, int nodes_len
,
236 const unsigned char *nodes6
, int nodes6_len
,
237 int af
, struct storage
*st
,
238 const unsigned char *token
, int token_len
);
239 static int send_closest_nodes(const struct sockaddr
*sa
, int salen
,
240 const unsigned char *tid
, int tid_len
,
241 const unsigned char *id
, int want
,
242 int af
, struct storage
*st
,
243 const unsigned char *token
, int token_len
);
244 static int send_get_peers(const struct sockaddr
*sa
, int salen
,
245 unsigned char *tid
, int tid_len
,
246 unsigned char *infohash
, int want
, int confirm
);
247 static int send_announce_peer(const struct sockaddr
*sa
, int salen
,
248 unsigned char *tid
, int tid_len
,
249 unsigned char *infohas
, unsigned short port
,
250 unsigned char *token
, int token_len
, int confirm
);
251 static int send_peer_announced(const struct sockaddr
*sa
, int salen
,
252 unsigned char *tid
, int tid_len
);
253 static int send_error(const struct sockaddr
*sa
, int salen
,
254 unsigned char *tid
, int tid_len
,
255 int code
, const char *message
);
258 add_search_node(const unsigned char *id
, const struct sockaddr
*sa
, int salen
);
265 #define ANNOUNCE_PEER 5
270 #define PARSE_TID_LEN 16
271 #define PARSE_TOKEN_LEN 128
272 #define PARSE_NODES_LEN (26 * 16)
273 #define PARSE_NODES6_LEN (38 * 16)
274 #define PARSE_VALUES_LEN 2048
275 #define PARSE_VALUES6_LEN 2048
277 struct parsed_message
{
278 unsigned char tid
[PARSE_TID_LEN
];
279 unsigned short tid_len
;
280 unsigned char id
[20];
281 unsigned char info_hash
[20];
282 unsigned char target
[20];
284 unsigned short implied_port
;
285 unsigned char token
[PARSE_TOKEN_LEN
];
286 unsigned short token_len
;
287 unsigned char nodes
[PARSE_NODES_LEN
];
288 unsigned short nodes_len
;
289 unsigned char nodes6
[PARSE_NODES6_LEN
];
290 unsigned short nodes6_len
;
291 unsigned char values
[PARSE_VALUES_LEN
];
292 unsigned short values_len
;
293 unsigned char values6
[PARSE_VALUES6_LEN
];
294 unsigned short values6_len
;
298 static int parse_message(const unsigned char *buf
, int buflen
,
299 struct parsed_message
*m
);
301 static const unsigned char zeroes
[20] = {0};
302 static const unsigned char v4prefix
[16] = {
303 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0xFF, 0xFF, 0, 0, 0, 0
306 static int dht_socket
= -1;
307 static int dht_socket6
= -1;
309 static time_t search_time
;
310 static time_t confirm_nodes_time
;
311 static time_t rotate_secrets_time
;
313 static unsigned char myid
[20];
314 static int have_v
= 0;
315 static unsigned char my_v
[9];
316 static unsigned char secret
[8];
317 static unsigned char oldsecret
[8];
319 static struct bucket
*buckets
= NULL
;
320 static struct bucket
*buckets6
= NULL
;
321 static struct storage
*storage
;
322 static int numstorage
;
324 static struct search
*searches
= NULL
;
325 static int numsearches
;
326 static unsigned short search_id
;
328 /* The maximum number of nodes that we snub. There is probably little
329 reason to increase this value. */
330 #ifndef DHT_MAX_BLACKLISTED
331 #define DHT_MAX_BLACKLISTED 10
333 static struct sockaddr_storage blacklist
[DHT_MAX_BLACKLISTED
];
334 int next_blacklisted
;
336 static struct timeval now
;
337 static time_t mybucket_grow_time
, mybucket6_grow_time
;
338 static time_t expire_stuff_time
;
340 #define MAX_TOKEN_BUCKET_TOKENS 400
341 static time_t token_bucket_time
;
342 static int token_bucket_tokens
;
344 FILE *dht_debug
= NULL
;
347 __attribute__ ((format (printf
, 1, 2)))
350 debugf(const char *format
, ...)
353 va_start(args
, format
);
355 vfprintf(dht_debug
, format
, args
);
362 debug_printable(const unsigned char *buf
, int buflen
)
366 for(i
= 0; i
< buflen
; i
++)
367 putc(buf
[i
] >= 32 && buf
[i
] <= 126 ? buf
[i
] : '.', dht_debug
);
372 print_hex(FILE *f
, const unsigned char *buf
, int buflen
)
375 for(i
= 0; i
< buflen
; i
++)
376 fprintf(f
, "%02x", buf
[i
]);
380 is_martian(const struct sockaddr
*sa
)
382 switch(sa
->sa_family
) {
384 struct sockaddr_in
*sin
= (struct sockaddr_in
*)sa
;
385 const unsigned char *address
= (const unsigned char*)&sin
->sin_addr
;
386 return sin
->sin_port
== 0 ||
388 (address
[0] == 127) ||
389 ((address
[0] & 0xE0) == 0xE0);
392 struct sockaddr_in6
*sin6
= (struct sockaddr_in6
*)sa
;
393 const unsigned char *address
= (const unsigned char*)&sin6
->sin6_addr
;
394 return sin6
->sin6_port
== 0 ||
395 (address
[0] == 0xFF) ||
396 (address
[0] == 0xFE && (address
[1] & 0xC0) == 0x80) ||
397 (memcmp(address
, zeroes
, 15) == 0 &&
398 (address
[15] == 0 || address
[15] == 1)) ||
399 (memcmp(address
, v4prefix
, 12) == 0);
407 /* Forget about the ``XOR-metric''. An id is just a path from the
408 root of the tree, so bits are numbered from the start. */
411 id_cmp(const unsigned char *restrict id1
, const unsigned char *restrict id2
)
413 /* Memcmp is guaranteed to perform an unsigned comparison. */
414 return memcmp(id1
, id2
, 20);
417 /* Find the lowest 1 bit in an id. */
419 lowbit(const unsigned char *id
)
422 for(i
= 19; i
>= 0; i
--)
429 for(j
= 7; j
>= 0; j
--)
430 if((id
[i
] & (0x80 >> j
)) != 0)
436 /* Find how many bits two ids have in common. */
438 common_bits(const unsigned char *id1
, const unsigned char *id2
)
442 for(i
= 0; i
< 20; i
++) {
450 xor = id1
[i
] ^ id2
[i
];
453 while((xor & 0x80) == 0) {
461 /* Determine whether id1 or id2 is closer to ref */
463 xorcmp(const unsigned char *id1
, const unsigned char *id2
,
464 const unsigned char *ref
)
467 for(i
= 0; i
< 20; i
++) {
468 unsigned char xor1
, xor2
;
471 xor1
= id1
[i
] ^ ref
[i
];
472 xor2
= id2
[i
] ^ ref
[i
];
481 /* We keep buckets in a sorted linked list. A bucket b ranges from
482 b->first inclusive up to b->next->first exclusive. */
484 in_bucket(const unsigned char *id
, struct bucket
*b
)
486 return id_cmp(b
->first
, id
) <= 0 &&
487 (b
->next
== NULL
|| id_cmp(id
, b
->next
->first
) < 0);
490 static struct bucket
*
491 find_bucket(unsigned const char *id
, int af
)
493 struct bucket
*b
= af
== AF_INET
? buckets
: buckets6
;
501 if(id_cmp(id
, b
->next
->first
) < 0)
507 static struct bucket
*
508 previous_bucket(struct bucket
*b
)
510 struct bucket
*p
= b
->af
== AF_INET
? buckets
: buckets6
;
524 /* Every bucket contains an unordered list of nodes. */
526 find_node(const unsigned char *id
, int af
)
528 struct bucket
*b
= find_bucket(id
, af
);
536 if(id_cmp(n
->id
, id
) == 0)
543 /* Return a random node in a bucket. */
545 random_node(struct bucket
*b
)
553 nn
= random() % b
->count
;
562 /* Return the middle id of a bucket. */
564 bucket_middle(struct bucket
*b
, unsigned char *id_return
)
566 int bit1
= lowbit(b
->first
);
567 int bit2
= b
->next
? lowbit(b
->next
->first
) : -1;
568 int bit
= MAX(bit1
, bit2
) + 1;
573 memcpy(id_return
, b
->first
, 20);
574 id_return
[bit
/ 8] |= (0x80 >> (bit
% 8));
578 /* Return a random id within a bucket. */
580 bucket_random(struct bucket
*b
, unsigned char *id_return
)
582 int bit1
= lowbit(b
->first
);
583 int bit2
= b
->next
? lowbit(b
->next
->first
) : -1;
584 int bit
= MAX(bit1
, bit2
) + 1;
588 memcpy(id_return
, b
->first
, 20);
592 memcpy(id_return
, b
->first
, bit
/ 8);
593 id_return
[bit
/ 8] = b
->first
[bit
/ 8] & (0xFF00 >> (bit
% 8));
594 id_return
[bit
/ 8] |= random() & 0xFF >> (bit
% 8);
595 for(i
= bit
/ 8 + 1; i
< 20; i
++)
596 id_return
[i
] = random() & 0xFF;
600 /* This is our definition of a known-good node. */
602 node_good(struct node
*node
)
606 node
->reply_time
>= now
.tv_sec
- 7200 &&
607 node
->time
>= now
.tv_sec
- 900;
610 /* Our transaction-ids are 4-bytes long, with the first two bytes identi-
611 fying the kind of request, and the remaining two a sequence number in
615 make_tid(unsigned char *tid_return
, const char *prefix
, unsigned short seqno
)
617 tid_return
[0] = prefix
[0] & 0xFF;
618 tid_return
[1] = prefix
[1] & 0xFF;
619 memcpy(tid_return
+ 2, &seqno
, 2);
623 tid_match(const unsigned char *tid
, const char *prefix
,
624 unsigned short *seqno_return
)
626 if(tid
[0] == (prefix
[0] & 0xFF) && tid
[1] == (prefix
[1] & 0xFF)) {
628 memcpy(seqno_return
, tid
+ 2, 2);
634 /* Every bucket caches the address of a likely node. Ping it. */
636 send_cached_ping(struct bucket
*b
)
638 unsigned char tid
[4];
640 /* We set family to 0 when there's no cached node. */
641 if(b
->cached
.ss_family
== 0)
644 debugf("Sending ping to cached node.\n");
645 make_tid(tid
, "pn", 0);
646 rc
= send_ping((struct sockaddr
*)&b
->cached
, b
->cachedlen
, tid
, 4);
647 b
->cached
.ss_family
= 0;
652 /* Called whenever we send a request to a node, increases the ping count
653 and, if that reaches 3, sends a ping to a new candidate. */
655 pinged(struct node
*n
, struct bucket
*b
)
658 n
->pinged_time
= now
.tv_sec
;
660 send_cached_ping(b
? b
: find_bucket(n
->id
, n
->ss
.ss_family
));
663 /* The internal blacklist is an LRU cache of nodes that have sent
664 incorrect messages. */
666 blacklist_node(const unsigned char *id
, const struct sockaddr
*sa
, int salen
)
670 debugf("Blacklisting broken node.\n");
675 /* Make the node easy to discard. */
676 n
= find_node(id
, sa
->sa_family
);
681 /* Discard it from any searches in progress. */
684 for(i
= 0; i
< sr
->numnodes
; i
++)
685 if(id_cmp(sr
->nodes
[i
].id
, id
) == 0)
686 flush_search_node(&sr
->nodes
[i
], sr
);
690 /* And make sure we don't hear from it again. */
691 memcpy(&blacklist
[next_blacklisted
], sa
, salen
);
692 next_blacklisted
= (next_blacklisted
+ 1) % DHT_MAX_BLACKLISTED
;
696 node_blacklisted(const struct sockaddr
*sa
, int salen
)
700 if((unsigned)salen
> sizeof(struct sockaddr_storage
))
703 if(dht_blacklisted(sa
, salen
))
706 for(i
= 0; i
< DHT_MAX_BLACKLISTED
; i
++) {
707 if(memcmp(&blacklist
[i
], sa
, salen
) == 0)
715 append_nodes(struct node
*n1
, struct node
*n2
)
726 while(n
->next
!= NULL
)
733 /* Insert a new node into a bucket, don't check for duplicates.
734 Returns 1 if the node was inserted, 0 if a bucket must be split. */
736 insert_node(struct node
*node
, struct bucket
**split_return
)
738 struct bucket
*b
= find_bucket(node
->id
, node
->ss
.ss_family
);
743 if(b
->count
>= b
->max_count
) {
747 node
->next
= b
->nodes
;
753 /* Splits a bucket, and returns the list of nodes that must be reinserted
754 into the routing table. */
756 split_bucket_helper(struct bucket
*b
, struct node
**nodes_return
)
760 unsigned char new_id
[20];
762 if(!in_bucket(myid
, b
)) {
763 debugf("Attempted to split wrong bucket.\n");
767 rc
= bucket_middle(b
, new_id
);
771 new = calloc(1, sizeof(struct bucket
));
778 memcpy(new->first
, new_id
, 20);
781 *nodes_return
= b
->nodes
;
787 if(in_bucket(myid
, b
)) {
788 new->max_count
= b
->max_count
;
789 b
->max_count
= MAX(b
->max_count
/ 2, 8);
791 new->max_count
= MAX(b
->max_count
/ 2, 8);
798 split_bucket(struct bucket
*b
)
801 struct node
*nodes
= NULL
;
802 struct node
*n
= NULL
;
804 debugf("Splitting.\n");
805 rc
= split_bucket_helper(b
, &nodes
);
807 debugf("Couldn't split bucket");
811 while(n
!= NULL
|| nodes
!= NULL
) {
812 struct bucket
*split
= NULL
;
818 rc
= insert_node(n
, &split
);
820 debugf("Couldn't insert node.\n");
825 } else if(!in_bucket(myid
, split
)) {
829 struct node
*insert
= NULL
;
830 debugf("Splitting (recursive).\n");
831 rc
= split_bucket_helper(split
, &insert
);
833 debugf("Couldn't split bucket.\n");
837 nodes
= append_nodes(nodes
, insert
);
844 /* We just learnt about a node, not necessarily a new one. Confirm is 1 if
845 the node sent a message, 2 if it sent us a reply. */
847 new_node(const unsigned char *id
, const struct sockaddr
*sa
, int salen
,
856 b
= find_bucket(id
, sa
->sa_family
);
860 if(id_cmp(id
, myid
) == 0)
863 if(is_martian(sa
) || node_blacklisted(sa
, salen
))
866 mybucket
= in_bucket(myid
, b
);
869 b
->time
= now
.tv_sec
;
873 if(id_cmp(n
->id
, id
) == 0) {
874 if(confirm
|| n
->time
< now
.tv_sec
- 15 * 60) {
875 /* Known node. Update stuff. */
876 memcpy((struct sockaddr
*)&n
->ss
, sa
, salen
);
878 n
->time
= now
.tv_sec
;
880 n
->reply_time
= now
.tv_sec
;
886 add_search_node(id
, sa
, salen
);
895 if(sa
->sa_family
== AF_INET
)
896 mybucket_grow_time
= now
.tv_sec
;
898 mybucket6_grow_time
= now
.tv_sec
;
901 /* First, try to get rid of a known-bad node. */
904 if(n
->pinged
>= 3 && n
->pinged_time
< now
.tv_sec
- 15) {
905 memcpy(n
->id
, id
, 20);
906 memcpy((struct sockaddr
*)&n
->ss
, sa
, salen
);
907 n
->time
= confirm
? now
.tv_sec
: 0;
908 n
->reply_time
= confirm
>= 2 ? now
.tv_sec
: 0;
912 add_search_node(id
, sa
, salen
);
918 if(b
->count
>= b
->max_count
) {
919 /* Bucket full. Ping a dubious node */
923 /* Pick the first dubious node that we haven't pinged in the
924 last 15 seconds. This gives nodes the time to reply, but
925 tends to concentrate on the same nodes, so that we get rid
926 of bad nodes fast. */
929 if(n
->pinged_time
< now
.tv_sec
- 15) {
930 unsigned char tid
[4];
931 debugf("Sending ping to dubious node.\n");
932 make_tid(tid
, "pn", 0);
933 send_ping((struct sockaddr
*)&n
->ss
, n
->sslen
,
936 n
->pinged_time
= now
.tv_sec
;
943 if(mybucket
&& !dubious
) {
945 rc
= split_bucket(b
);
951 /* No space for this node. Cache it away for later. */
952 if(confirm
|| b
->cached
.ss_family
== 0) {
953 memcpy(&b
->cached
, sa
, salen
);
954 b
->cachedlen
= salen
;
958 add_search_node(id
, sa
, salen
);
962 /* Create a new node. */
963 n
= calloc(1, sizeof(struct node
));
966 memcpy(n
->id
, id
, 20);
967 memcpy(&n
->ss
, sa
, salen
);
969 n
->time
= confirm
? now
.tv_sec
: 0;
970 n
->reply_time
= confirm
>= 2 ? now
.tv_sec
: 0;
975 add_search_node(id
, sa
, salen
);
979 /* Called periodically to purge known-bad nodes. Note that we're very
980 conservative here: broken nodes in the table don't do much harm, we'll
981 recover as soon as we find better ones. */
983 expire_buckets(struct bucket
*b
)
989 while(b
->nodes
&& b
->nodes
->pinged
>= 4) {
999 while(p
->next
&& p
->next
->pinged
>= 4) {
1010 send_cached_ping(b
);
1014 expire_stuff_time
= now
.tv_sec
+ 120 + random() % 240;
1018 /* While a search is in progress, we don't necessarily keep the nodes being
1019 walked in the main bucket table. A search in progress is identified by
1020 a unique transaction id, a short (and hence small enough to fit in the
1021 transaction id of the protocol packets). */
1023 static struct search
*
1024 find_search(unsigned short tid
, int af
)
1026 struct search
*sr
= searches
;
1028 if(sr
->tid
== tid
&& sr
->af
== af
)
1035 /* A search contains a list of nodes, sorted by decreasing distance to the
1036 target. We just got a new candidate, insert it at the right spot or
1039 static struct search_node
*
1040 insert_search_node(const unsigned char *id
,
1041 const struct sockaddr
*sa
, int salen
,
1042 struct search
*sr
, int replied
,
1043 unsigned char *token
, int token_len
)
1045 struct search_node
*n
;
1048 if(sa
->sa_family
!= sr
->af
) {
1049 debugf("Attempted to insert node in the wrong family.\n");
1053 for(i
= 0; i
< sr
->numnodes
; i
++) {
1054 if(id_cmp(id
, sr
->nodes
[i
].id
) == 0) {
1058 if(xorcmp(id
, sr
->nodes
[i
].id
, sr
->id
) < 0)
1062 if(i
== SEARCH_NODES
)
1065 if(sr
->numnodes
< SEARCH_NODES
)
1068 for(j
= sr
->numnodes
- 1; j
> i
; j
--) {
1069 sr
->nodes
[j
] = sr
->nodes
[j
- 1];
1074 memset(n
, 0, sizeof(struct search_node
));
1075 memcpy(n
->id
, id
, 20);
1078 memcpy(&n
->ss
, sa
, salen
);
1083 n
->reply_time
= now
.tv_sec
;
1084 n
->request_time
= 0;
1088 if(token_len
>= 40) {
1089 debugf("Eek! Overlong token.\n");
1091 memcpy(n
->token
, token
, token_len
);
1092 n
->token_len
= token_len
;
1100 flush_search_node(struct search_node
*n
, struct search
*sr
)
1102 int i
= n
- sr
->nodes
, j
;
1103 for(j
= i
; j
< sr
->numnodes
- 1; j
++)
1104 sr
->nodes
[j
] = sr
->nodes
[j
+ 1];
1109 expire_searches(dht_callback_t
*callback
, void *closure
)
1111 struct search
*sr
= searches
, *previous
= NULL
;
1114 struct search
*next
= sr
->next
;
1115 if(sr
->step_time
< now
.tv_sec
- DHT_SEARCH_EXPIRE_TIME
) {
1117 previous
->next
= next
;
1123 (*callback
)(closure
,
1125 DHT_EVENT_SEARCH_DONE
: DHT_EVENT_SEARCH_DONE6
,
1136 /* This must always return 0 or 1, never -1, not even on failure (see below). */
1138 search_send_get_peers(struct search
*sr
, struct search_node
*n
)
1141 unsigned char tid
[4];
1145 for(i
= 0; i
< sr
->numnodes
; i
++) {
1146 if(sr
->nodes
[i
].pinged
< 3 && !sr
->nodes
[i
].replied
&&
1147 sr
->nodes
[i
].request_time
< now
.tv_sec
- DHT_SEARCH_RETRANSMIT
)
1152 if(!n
|| n
->pinged
>= 3 || n
->replied
||
1153 n
->request_time
>= now
.tv_sec
- DHT_SEARCH_RETRANSMIT
)
1156 debugf("Sending get_peers.\n");
1157 make_tid(tid
, "gp", sr
->tid
);
1158 send_get_peers((struct sockaddr
*)&n
->ss
, n
->sslen
, tid
, 4, sr
->id
, -1,
1159 n
->reply_time
>= now
.tv_sec
- DHT_SEARCH_RETRANSMIT
);
1161 n
->request_time
= now
.tv_sec
;
1162 /* If the node happens to be in our main routing table, mark it
1164 node
= find_node(n
->id
, n
->ss
.ss_family
);
1165 if(node
) pinged(node
, NULL
);
1169 /* Insert a new node into any incomplete search. */
1171 add_search_node(const unsigned char *id
, const struct sockaddr
*sa
, int salen
)
1174 for(sr
= searches
; sr
; sr
= sr
->next
) {
1175 if(sr
->af
== sa
->sa_family
&& sr
->numnodes
< SEARCH_NODES
) {
1176 struct search_node
*n
=
1177 insert_search_node(id
, sa
, salen
, sr
, 0, NULL
, 0);
1179 search_send_get_peers(sr
, n
);
1184 /* When a search is in progress, we periodically call search_step to send
1185 further requests. */
1187 search_step(struct search
*sr
, dht_callback_t
*callback
, void *closure
)
1192 /* Check if the first 8 live nodes have replied. */
1194 for(i
= 0; i
< sr
->numnodes
&& j
< 8; i
++) {
1195 struct search_node
*n
= &sr
->nodes
[i
];
1211 for(i
= 0; i
< sr
->numnodes
&& j
< 8; i
++) {
1212 struct search_node
*n
= &sr
->nodes
[i
];
1214 unsigned char tid
[4];
1217 /* A proposed extension to the protocol consists in
1218 omitting the token when storage tables are full. While
1219 I don't think this makes a lot of sense -- just sending
1220 a positive reply is just as good --, let's deal with it. */
1221 if(n
->token_len
== 0)
1225 debugf("Sending announce_peer.\n");
1226 make_tid(tid
, "ap", sr
->tid
);
1227 send_announce_peer((struct sockaddr
*)&n
->ss
,
1228 sizeof(struct sockaddr_storage
),
1229 tid
, 4, sr
->id
, sr
->port
,
1230 n
->token
, n
->token_len
,
1231 n
->reply_time
>= now
.tv_sec
- 15);
1233 n
->request_time
= now
.tv_sec
;
1234 node
= find_node(n
->id
, n
->ss
.ss_family
);
1235 if(node
) pinged(node
, NULL
);
1242 sr
->step_time
= now
.tv_sec
;
1246 if(sr
->step_time
+ DHT_SEARCH_RETRANSMIT
>= now
.tv_sec
)
1250 for(i
= 0; i
< sr
->numnodes
; i
++) {
1251 j
+= search_send_get_peers(sr
, &sr
->nodes
[i
]);
1252 if(j
>= DHT_INFLIGHT_QUERIES
)
1255 sr
->step_time
= now
.tv_sec
;
1261 (*callback
)(closure
,
1263 DHT_EVENT_SEARCH_DONE
: DHT_EVENT_SEARCH_DONE6
,
1265 sr
->step_time
= now
.tv_sec
;
1268 static struct search
*
1271 struct search
*sr
, *oldest
= NULL
;
1273 /* Find the oldest done search */
1277 (oldest
== NULL
|| oldest
->step_time
> sr
->step_time
))
1282 /* The oldest slot is expired. */
1283 if(oldest
&& oldest
->step_time
< now
.tv_sec
- DHT_SEARCH_EXPIRE_TIME
)
1286 /* Allocate a new slot. */
1287 if(numsearches
< DHT_MAX_SEARCHES
) {
1288 sr
= calloc(1, sizeof(struct search
));
1290 sr
->next
= searches
;
1297 /* Return oldest slot if it's done. */
1298 if(oldest
&& oldest
->done
)
1301 /* No available slots found, return NULL. */
1305 /* Insert the contents of a bucket into a search structure. */
1307 insert_search_bucket(struct bucket
*b
, struct search
*sr
)
1312 insert_search_node(n
->id
, (struct sockaddr
*)&n
->ss
, n
->sslen
,
1318 /* Start a search. If port is non-zero, perform an announce when the
1319 search is complete. */
1321 dht_search(const unsigned char *id
, int port
, int af
,
1322 dht_callback_t
*callback
, void *closure
)
1326 struct bucket
*b
= find_bucket(id
, af
);
1329 errno
= EAFNOSUPPORT
;
1333 /* Try to answer this search locally. In a fully grown DHT this
1334 is very unlikely, but people are running modified versions of
1335 this code in private DHTs with very few nodes. What's wrong
1338 st
= find_storage(id
);
1340 unsigned short swapped
;
1341 unsigned char buf
[18];
1344 debugf("Found local data (%d peers).\n", st
->numpeers
);
1346 for(i
= 0; i
< st
->numpeers
; i
++) {
1347 swapped
= htons(st
->peers
[i
].port
);
1348 if(st
->peers
[i
].len
== 4) {
1349 memcpy(buf
, st
->peers
[i
].ip
, 4);
1350 memcpy(buf
+ 4, &swapped
, 2);
1351 (*callback
)(closure
, DHT_EVENT_VALUES
, id
,
1353 } else if(st
->peers
[i
].len
== 16) {
1354 memcpy(buf
, st
->peers
[i
].ip
, 16);
1355 memcpy(buf
+ 16, &swapped
, 2);
1356 (*callback
)(closure
, DHT_EVENT_VALUES6
, id
,
1365 if(sr
->af
== af
&& id_cmp(sr
->id
, id
) == 0)
1370 int sr_duplicate
= sr
&& !sr
->done
;
1373 /* We're reusing data from an old search. Reusing the same tid
1374 means that we can merge replies for both searches. */
1378 for(i
= 0; i
< sr
->numnodes
; i
++) {
1379 struct search_node
*n
;
1381 /* Discard any doubtful nodes. */
1382 if(n
->pinged
>= 3 || n
->reply_time
< now
.tv_sec
- 7200) {
1383 flush_search_node(n
, sr
);
1398 sr
->tid
= search_id
++;
1400 memcpy(sr
->id
, id
, 20);
1407 insert_search_bucket(b
, sr
);
1409 if(sr
->numnodes
< SEARCH_NODES
) {
1410 struct bucket
*p
= previous_bucket(b
);
1412 insert_search_bucket(b
->next
, sr
);
1414 insert_search_bucket(p
, sr
);
1416 if(sr
->numnodes
< SEARCH_NODES
)
1417 insert_search_bucket(find_bucket(myid
, af
), sr
);
1419 search_step(sr
, callback
, closure
);
1420 search_time
= now
.tv_sec
;
1428 /* A struct storage stores all the stored peer addresses for a given info
1431 static struct storage
*
1432 find_storage(const unsigned char *id
)
1434 struct storage
*st
= storage
;
1437 if(id_cmp(id
, st
->id
) == 0)
1445 storage_store(const unsigned char *id
,
1446 const struct sockaddr
*sa
, unsigned short port
)
1452 if(sa
->sa_family
== AF_INET
) {
1453 struct sockaddr_in
*sin
= (struct sockaddr_in
*)sa
;
1454 ip
= (unsigned char*)&sin
->sin_addr
;
1456 } else if(sa
->sa_family
== AF_INET6
) {
1457 struct sockaddr_in6
*sin6
= (struct sockaddr_in6
*)sa
;
1458 ip
= (unsigned char*)&sin6
->sin6_addr
;
1464 st
= find_storage(id
);
1467 if(numstorage
>= DHT_MAX_HASHES
)
1469 st
= calloc(1, sizeof(struct storage
));
1470 if(st
== NULL
) return -1;
1471 memcpy(st
->id
, id
, 20);
1477 for(i
= 0; i
< st
->numpeers
; i
++) {
1478 if(st
->peers
[i
].port
== port
&& st
->peers
[i
].len
== len
&&
1479 memcmp(st
->peers
[i
].ip
, ip
, len
) == 0)
1483 if(i
< st
->numpeers
) {
1484 /* Already there, only need to refresh */
1485 st
->peers
[i
].time
= now
.tv_sec
;
1489 if(i
>= st
->maxpeers
) {
1490 /* Need to expand the array. */
1491 struct peer
*new_peers
;
1493 if(st
->maxpeers
>= DHT_MAX_PEERS
)
1495 n
= st
->maxpeers
== 0 ? 2 : 2 * st
->maxpeers
;
1496 n
= MIN(n
, DHT_MAX_PEERS
);
1497 new_peers
= realloc(st
->peers
, n
* sizeof(struct peer
));
1498 if(new_peers
== NULL
)
1500 st
->peers
= new_peers
;
1503 p
= &st
->peers
[st
->numpeers
++];
1504 p
->time
= now
.tv_sec
;
1506 memcpy(p
->ip
, ip
, len
);
1513 expire_storage(void)
1515 struct storage
*st
= storage
, *previous
= NULL
;
1518 while(i
< st
->numpeers
) {
1519 if(st
->peers
[i
].time
< now
.tv_sec
- 32 * 60) {
1520 if(i
!= st
->numpeers
- 1)
1521 st
->peers
[i
] = st
->peers
[st
->numpeers
- 1];
1528 if(st
->numpeers
== 0) {
1531 previous
->next
= st
->next
;
1536 st
= previous
->next
;
1540 if(numstorage
< 0) {
1541 debugf("Eek... numstorage became negative.\n");
1553 rotate_secrets(void)
1557 rotate_secrets_time
= now
.tv_sec
+ 900 + random() % 1800;
1559 memcpy(oldsecret
, secret
, sizeof(secret
));
1560 rc
= dht_random_bytes(secret
, sizeof(secret
));
1569 #define TOKEN_SIZE 8
1573 make_token(const struct sockaddr
*sa
, int old
, unsigned char *token_return
)
1577 unsigned short port
;
1579 if(sa
->sa_family
== AF_INET
) {
1580 struct sockaddr_in
*sin
= (struct sockaddr_in
*)sa
;
1581 ip
= &sin
->sin_addr
;
1583 port
= htons(sin
->sin_port
);
1584 } else if(sa
->sa_family
== AF_INET6
) {
1585 struct sockaddr_in6
*sin6
= (struct sockaddr_in6
*)sa
;
1586 ip
= &sin6
->sin6_addr
;
1588 port
= htons(sin6
->sin6_port
);
1593 dht_hash(token_return
, TOKEN_SIZE
,
1594 old
? oldsecret
: secret
, sizeof(secret
),
1595 ip
, iplen
, (unsigned char*)&port
, 2);
1598 token_match(const unsigned char *token
, int token_len
,
1599 const struct sockaddr
*sa
)
1601 unsigned char t
[TOKEN_SIZE
];
1602 if(token_len
!= TOKEN_SIZE
)
1604 make_token(sa
, 0, t
);
1605 if(memcmp(t
, token
, TOKEN_SIZE
) == 0)
1607 make_token(sa
, 1, t
);
1608 if(memcmp(t
, token
, TOKEN_SIZE
) == 0)
1614 dht_nodes(int af
, int *good_return
, int *dubious_return
, int *cached_return
,
1615 int *incoming_return
)
1617 int good
= 0, dubious
= 0, cached
= 0, incoming
= 0;
1618 struct bucket
*b
= af
== AF_INET
? buckets
: buckets6
;
1621 struct node
*n
= b
->nodes
;
1625 if(n
->time
> n
->reply_time
)
1632 if(b
->cached
.ss_family
> 0)
1637 *good_return
= good
;
1639 *dubious_return
= dubious
;
1641 *cached_return
= cached
;
1643 *incoming_return
= incoming
;
1644 return good
+ dubious
;
1648 dump_bucket(FILE *f
, struct bucket
*b
)
1650 struct node
*n
= b
->nodes
;
1651 fprintf(f
, "Bucket ");
1652 print_hex(f
, b
->first
, 20);
1653 fprintf(f
, " count %d/%d age %d%s%s:\n",
1654 b
->count
, b
->max_count
, (int)(now
.tv_sec
- b
->time
),
1655 in_bucket(myid
, b
) ? " (mine)" : "",
1656 b
->cached
.ss_family
? " (cached)" : "");
1659 unsigned short port
;
1660 fprintf(f
, " Node ");
1661 print_hex(f
, n
->id
, 20);
1662 if(n
->ss
.ss_family
== AF_INET
) {
1663 struct sockaddr_in
*sin
= (struct sockaddr_in
*)&n
->ss
;
1664 inet_ntop(AF_INET
, &sin
->sin_addr
, buf
, 512);
1665 port
= ntohs(sin
->sin_port
);
1666 } else if(n
->ss
.ss_family
== AF_INET6
) {
1667 struct sockaddr_in6
*sin6
= (struct sockaddr_in6
*)&n
->ss
;
1668 inet_ntop(AF_INET6
, &sin6
->sin6_addr
, buf
, 512);
1669 port
= ntohs(sin6
->sin6_port
);
1671 snprintf(buf
, 512, "unknown(%d)", n
->ss
.ss_family
);
1675 if(n
->ss
.ss_family
== AF_INET6
)
1676 fprintf(f
, " [%s]:%d ", buf
, port
);
1678 fprintf(f
, " %s:%d ", buf
, port
);
1679 if(n
->time
!= n
->reply_time
)
1680 fprintf(f
, "age %ld, %ld",
1681 (long)(now
.tv_sec
- n
->time
),
1682 (long)(now
.tv_sec
- n
->reply_time
));
1684 fprintf(f
, "age %ld", (long)(now
.tv_sec
- n
->time
));
1686 fprintf(f
, " (%d)", n
->pinged
);
1688 fprintf(f
, " (good)");
1696 dht_dump_tables(FILE *f
)
1700 struct storage
*st
= storage
;
1701 struct search
*sr
= searches
;
1703 fprintf(f
, "My id ");
1704 print_hex(f
, myid
, 20);
1722 fprintf(f
, "\nSearch%s id ", sr
->af
== AF_INET6
? " (IPv6)" : "");
1723 print_hex(f
, sr
->id
, 20);
1724 fprintf(f
, " age %d%s\n", (int)(now
.tv_sec
- sr
->step_time
),
1725 sr
->done
? " (done)" : "");
1726 for(i
= 0; i
< sr
->numnodes
; i
++) {
1727 struct search_node
*n
= &sr
->nodes
[i
];
1728 fprintf(f
, "Node %d id ", i
);
1729 print_hex(f
, n
->id
, 20);
1730 fprintf(f
, " bits %d age ", common_bits(sr
->id
, n
->id
));
1732 fprintf(f
, "%d, ", (int)(now
.tv_sec
- n
->request_time
));
1733 fprintf(f
, "%d", (int)(now
.tv_sec
- n
->reply_time
));
1735 fprintf(f
, " (%d)", n
->pinged
);
1736 fprintf(f
, "%s%s.\n",
1737 find_node(n
->id
, sr
->af
) ? " (known)" : "",
1738 n
->replied
? " (replied)" : "");
1744 fprintf(f
, "\nStorage ");
1745 print_hex(f
, st
->id
, 20);
1746 fprintf(f
, " %d/%d nodes:", st
->numpeers
, st
->maxpeers
);
1747 for(i
= 0; i
< st
->numpeers
; i
++) {
1749 if(st
->peers
[i
].len
== 4) {
1750 inet_ntop(AF_INET
, st
->peers
[i
].ip
, buf
, 100);
1751 } else if(st
->peers
[i
].len
== 16) {
1753 inet_ntop(AF_INET6
, st
->peers
[i
].ip
, buf
+ 1, 98);
1758 fprintf(f
, " %s:%u (%ld)",
1759 buf
, st
->peers
[i
].port
,
1760 (long)(now
.tv_sec
- st
->peers
[i
].time
));
1770 dht_init(int s
, int s6
, const unsigned char *id
, const unsigned char *v
)
1774 if(dht_socket
>= 0 || dht_socket6
>= 0 || buckets
|| buckets6
) {
1786 buckets
= calloc(1, sizeof(struct bucket
));
1789 buckets
->max_count
= 128;
1790 buckets
->af
= AF_INET
;
1794 buckets6
= calloc(1, sizeof(struct bucket
));
1795 if(buckets6
== NULL
)
1797 buckets6
->max_count
= 128;
1798 buckets6
->af
= AF_INET6
;
1801 memcpy(myid
, id
, 20);
1803 memcpy(my_v
, "1:v4:", 5);
1804 memcpy(my_v
+ 5, v
, 4);
1810 dht_gettimeofday(&now
, NULL
);
1812 mybucket_grow_time
= now
.tv_sec
;
1813 mybucket6_grow_time
= now
.tv_sec
;
1814 confirm_nodes_time
= now
.tv_sec
+ random() % 3;
1816 search_id
= random() & 0xFFFF;
1819 next_blacklisted
= 0;
1821 token_bucket_time
= now
.tv_sec
;
1822 token_bucket_tokens
= MAX_TOKEN_BUCKET_TOKENS
;
1824 memset(secret
, 0, sizeof(secret
));
1825 rc
= rotate_secrets();
1832 expire_buckets(buckets
);
1833 expire_buckets(buckets6
);
1848 if(dht_socket
< 0 && dht_socket6
< 0) {
1857 struct bucket
*b
= buckets
;
1860 struct node
*n
= b
->nodes
;
1868 struct bucket
*b
= buckets6
;
1871 struct node
*n
= b
->nodes
;
1879 struct storage
*st
= storage
;
1880 storage
= storage
->next
;
1886 struct search
*sr
= searches
;
1887 searches
= searches
->next
;
1894 /* Rate control for requests we receive. */
1899 if(token_bucket_tokens
== 0) {
1900 token_bucket_tokens
= MIN(MAX_TOKEN_BUCKET_TOKENS
,
1901 100 * (now
.tv_sec
- token_bucket_time
));
1902 token_bucket_time
= now
.tv_sec
;
1905 if(token_bucket_tokens
== 0)
1908 token_bucket_tokens
--;
1913 neighbourhood_maintenance(int af
)
1915 unsigned char id
[20];
1916 struct bucket
*b
= find_bucket(myid
, af
);
1923 memcpy(id
, myid
, 20);
1924 id
[19] = random() & 0xFF;
1926 if(q
->next
&& (q
->count
== 0 || (random() & 7) == 0))
1928 if(q
->count
== 0 || (random() & 7) == 0) {
1930 r
= previous_bucket(b
);
1931 if(r
&& r
->count
> 0)
1936 /* Since our node-id is the same in both DHTs, it's probably
1937 profitable to query both families. */
1938 int want
= dht_socket
>= 0 && dht_socket6
>= 0 ? (WANT4
| WANT6
) : -1;
1941 unsigned char tid
[4];
1942 debugf("Sending find_node for%s neighborhood maintenance.\n",
1943 af
== AF_INET6
? " IPv6" : "");
1944 make_tid(tid
, "fn", 0);
1945 send_find_node((struct sockaddr
*)&n
->ss
, n
->sslen
,
1947 n
->reply_time
>= now
.tv_sec
- 15);
1956 bucket_maintenance(int af
)
1960 b
= af
== AF_INET
? buckets
: buckets6
;
1963 /* 10 minutes for an 8-node bucket */
1964 int to
= MAX(600 / (b
->max_count
/ 8), 30);
1966 if(b
->time
< now
.tv_sec
- to
) {
1967 /* This bucket hasn't seen any positive confirmation for a long
1968 time. Pick a random id in this bucket's range, and send
1969 a request to a random node. */
1970 unsigned char id
[20];
1974 rc
= bucket_random(b
, id
);
1976 memcpy(id
, b
->first
, 20);
1979 /* If the bucket is empty, we try to fill it from a neighbour.
1980 We also sometimes do it gratuitiously to recover from
1981 buckets full of broken nodes. */
1982 if(q
->next
&& (q
->count
== 0 || (random() & 7) == 0))
1984 if(q
->count
== 0 || (random() & 7) == 0) {
1986 r
= previous_bucket(b
);
1987 if(r
&& r
->count
> 0)
1994 unsigned char tid
[4];
1997 if(dht_socket
>= 0 && dht_socket6
>= 0) {
1998 struct bucket
*otherbucket
;
2000 find_bucket(id
, af
== AF_INET
? AF_INET6
: AF_INET
);
2002 otherbucket
->count
< otherbucket
->max_count
)
2003 /* The corresponding bucket in the other family
2004 is not full -- querying both is useful. */
2005 want
= WANT4
| WANT6
;
2006 else if(random() % 37 == 0)
2007 /* Most of the time, this just adds overhead.
2008 However, it might help stitch back one of
2009 the DHTs after a network collapse, so query
2010 both, but only very occasionally. */
2011 want
= WANT4
| WANT6
;
2014 debugf("Sending find_node for%s bucket maintenance.\n",
2015 af
== AF_INET6
? " IPv6" : "");
2016 make_tid(tid
, "fn", 0);
2017 send_find_node((struct sockaddr
*)&n
->ss
, n
->sslen
,
2019 n
->reply_time
>= now
.tv_sec
- 15);
2021 /* In order to avoid sending queries back-to-back,
2022 give up for now and reschedule us soon. */
2033 dht_periodic(const void *buf
, size_t buflen
,
2034 const struct sockaddr
*from
, int fromlen
,
2036 dht_callback_t
*callback
, void *closure
)
2038 dht_gettimeofday(&now
, NULL
);
2042 struct parsed_message m
;
2043 unsigned short ttid
;
2045 if(is_martian(from
))
2048 if(node_blacklisted(from
, fromlen
)) {
2049 debugf("Received packet from blacklisted node.\n");
2053 if(((char*)buf
)[buflen
] != '\0') {
2054 debugf("Unterminated message.\n");
2059 memset(&m
, 0, sizeof(m
));
2060 message
= parse_message(buf
, buflen
, &m
);
2062 if(message
< 0 || message
== ERROR
|| id_cmp(m
.id
, zeroes
) == 0) {
2063 debugf("Unparseable message: ");
2064 debug_printable(buf
, buflen
);
2069 if(id_cmp(m
.id
, myid
) == 0) {
2070 debugf("Received message from self.\n");
2074 if(message
> REPLY
) {
2075 /* Rate limit requests. */
2076 if(!token_bucket()) {
2077 debugf("Dropping request due to rate limiting.\n");
2084 if(m
.tid_len
!= 4) {
2085 debugf("Broken node truncates transaction ids: ");
2086 debug_printable(buf
, buflen
);
2088 /* This is really annoying, as it means that we will
2089 time-out all our searches that go through this node.
2091 blacklist_node(m
.id
, from
, fromlen
);
2094 if(tid_match(m
.tid
, "pn", NULL
)) {
2096 new_node(m
.id
, from
, fromlen
, 2);
2097 } else if(tid_match(m
.tid
, "fn", NULL
) ||
2098 tid_match(m
.tid
, "gp", NULL
)) {
2100 struct search
*sr
= NULL
;
2101 if(tid_match(m
.tid
, "gp", &ttid
)) {
2103 sr
= find_search(ttid
, from
->sa_family
);
2105 debugf("Nodes found (%d+%d)%s!\n",
2106 m
.nodes_len
/26, m
.nodes6_len
/38,
2107 gp
? " for get_peers" : "");
2108 if(m
.nodes_len
% 26 != 0 || m
.nodes6_len
% 38 != 0) {
2109 debugf("Unexpected length for node info!\n");
2110 blacklist_node(m
.id
, from
, fromlen
);
2111 } else if(gp
&& sr
== NULL
) {
2112 debugf("Unknown search!\n");
2113 new_node(m
.id
, from
, fromlen
, 1);
2116 new_node(m
.id
, from
, fromlen
, 2);
2117 for(i
= 0; i
< m
.nodes_len
/ 26; i
++) {
2118 unsigned char *ni
= m
.nodes
+ i
* 26;
2119 struct sockaddr_in sin
;
2120 if(id_cmp(ni
, myid
) == 0)
2122 memset(&sin
, 0, sizeof(sin
));
2123 sin
.sin_family
= AF_INET
;
2124 memcpy(&sin
.sin_addr
, ni
+ 20, 4);
2125 memcpy(&sin
.sin_port
, ni
+ 24, 2);
2126 new_node(ni
, (struct sockaddr
*)&sin
, sizeof(sin
), 0);
2127 if(sr
&& sr
->af
== AF_INET
) {
2128 insert_search_node(ni
,
2129 (struct sockaddr
*)&sin
,
2134 for(i
= 0; i
< m
.nodes6_len
/ 38; i
++) {
2135 unsigned char *ni
= m
.nodes6
+ i
* 38;
2136 struct sockaddr_in6 sin6
;
2137 if(id_cmp(ni
, myid
) == 0)
2139 memset(&sin6
, 0, sizeof(sin6
));
2140 sin6
.sin6_family
= AF_INET6
;
2141 memcpy(&sin6
.sin6_addr
, ni
+ 20, 16);
2142 memcpy(&sin6
.sin6_port
, ni
+ 36, 2);
2143 new_node(ni
, (struct sockaddr
*)&sin6
, sizeof(sin6
), 0);
2144 if(sr
&& sr
->af
== AF_INET6
) {
2145 insert_search_node(ni
,
2146 (struct sockaddr
*)&sin6
,
2152 /* Since we received a reply, the number of
2153 requests in flight has decreased. Let's push
2155 search_send_get_peers(sr
, NULL
);
2158 insert_search_node(m
.id
, from
, fromlen
, sr
,
2159 1, m
.token
, m
.token_len
);
2160 if(m
.values_len
> 0 || m
.values6_len
> 0) {
2161 debugf("Got values (%d+%d)!\n",
2162 m
.values_len
/ 6, m
.values6_len
/ 18);
2164 if(m
.values_len
> 0)
2165 (*callback
)(closure
, DHT_EVENT_VALUES
, sr
->id
,
2166 (void*)m
.values
, m
.values_len
);
2168 if(m
.values6_len
> 0)
2169 (*callback
)(closure
, DHT_EVENT_VALUES6
, sr
->id
,
2170 (void*)m
.values6
, m
.values6_len
);
2174 } else if(tid_match(m
.tid
, "ap", &ttid
)) {
2176 debugf("Got reply to announce_peer.\n");
2177 sr
= find_search(ttid
, from
->sa_family
);
2179 debugf("Unknown search!\n");
2180 new_node(m
.id
, from
, fromlen
, 1);
2183 new_node(m
.id
, from
, fromlen
, 2);
2184 for(i
= 0; i
< sr
->numnodes
; i
++)
2185 if(id_cmp(sr
->nodes
[i
].id
, m
.id
) == 0) {
2186 sr
->nodes
[i
].request_time
= 0;
2187 sr
->nodes
[i
].reply_time
= now
.tv_sec
;
2188 sr
->nodes
[i
].acked
= 1;
2189 sr
->nodes
[i
].pinged
= 0;
2192 /* See comment for gp above. */
2193 search_send_get_peers(sr
, NULL
);
2196 debugf("Unexpected reply: ");
2197 debug_printable(buf
, buflen
);
2202 debugf("Ping (%d)!\n", m
.tid_len
);
2203 new_node(m
.id
, from
, fromlen
, 1);
2204 debugf("Sending pong.\n");
2205 send_pong(from
, fromlen
, m
.tid
, m
.tid_len
);
2208 debugf("Find node!\n");
2209 new_node(m
.id
, from
, fromlen
, 1);
2210 debugf("Sending closest nodes (%d).\n", m
.want
);
2211 send_closest_nodes(from
, fromlen
,
2212 m
.tid
, m
.tid_len
, m
.target
, m
.want
,
2216 debugf("Get_peers!\n");
2217 new_node(m
.id
, from
, fromlen
, 1);
2218 if(id_cmp(m
.info_hash
, zeroes
) == 0) {
2219 debugf("Eek! Got get_peers with no info_hash.\n");
2220 send_error(from
, fromlen
, m
.tid
, m
.tid_len
,
2221 203, "Get_peers with no info_hash");
2224 struct storage
*st
= find_storage(m
.info_hash
);
2225 unsigned char token
[TOKEN_SIZE
];
2226 make_token(from
, 0, token
);
2227 if(st
&& st
->numpeers
> 0) {
2228 debugf("Sending found%s peers.\n",
2229 from
->sa_family
== AF_INET6
? " IPv6" : "");
2230 send_closest_nodes(from
, fromlen
,
2232 m
.info_hash
, m
.want
,
2233 from
->sa_family
, st
,
2236 debugf("Sending nodes for get_peers.\n");
2237 send_closest_nodes(from
, fromlen
,
2238 m
.tid
, m
.tid_len
, m
.info_hash
, m
.want
,
2239 0, NULL
, token
, TOKEN_SIZE
);
2244 debugf("Announce peer!\n");
2245 new_node(m
.id
, from
, fromlen
, 1);
2246 if(id_cmp(m
.info_hash
, zeroes
) == 0) {
2247 debugf("Announce_peer with no info_hash.\n");
2248 send_error(from
, fromlen
, m
.tid
, m
.tid_len
,
2249 203, "Announce_peer with no info_hash");
2252 if(!token_match(m
.token
, m
.token_len
, from
)) {
2253 debugf("Incorrect token for announce_peer.\n");
2254 send_error(from
, fromlen
, m
.tid
, m
.tid_len
,
2255 203, "Announce_peer with wrong token");
2258 if(m
.implied_port
!= 0) {
2259 /* Do this even if port > 0. That's what the spec says. */
2260 switch(from
->sa_family
) {
2262 m
.port
= htons(((struct sockaddr_in
*)from
)->sin_port
);
2265 m
.port
= htons(((struct sockaddr_in6
*)from
)->sin6_port
);
2270 debugf("Announce_peer with forbidden port %d.\n", m
.port
);
2271 send_error(from
, fromlen
, m
.tid
, m
.tid_len
,
2272 203, "Announce_peer with forbidden port number");
2275 storage_store(m
.info_hash
, from
, m
.port
);
2276 /* Note that if storage_store failed, we lie to the requestor.
2277 This is to prevent them from backtracking, and hence
2278 polluting the DHT. */
2279 debugf("Sending peer announced.\n");
2280 send_peer_announced(from
, fromlen
, m
.tid
, m
.tid_len
);
2285 if(now
.tv_sec
>= rotate_secrets_time
)
2288 if(now
.tv_sec
>= expire_stuff_time
) {
2289 expire_buckets(buckets
);
2290 expire_buckets(buckets6
);
2292 expire_searches(callback
, closure
);
2295 if(search_time
> 0 && now
.tv_sec
>= search_time
) {
2300 sr
->step_time
+ DHT_SEARCH_RETRANSMIT
/ 2 + 1 <= now
.tv_sec
) {
2301 search_step(sr
, callback
, closure
);
2311 time_t tm
= sr
->step_time
+
2312 DHT_SEARCH_RETRANSMIT
+ random() % DHT_SEARCH_RETRANSMIT
;
2313 if(search_time
== 0 || search_time
> tm
)
2320 if(now
.tv_sec
>= confirm_nodes_time
) {
2323 soon
|= bucket_maintenance(AF_INET
);
2324 soon
|= bucket_maintenance(AF_INET6
);
2327 if(mybucket_grow_time
>= now
.tv_sec
- 150)
2328 soon
|= neighbourhood_maintenance(AF_INET
);
2329 if(mybucket6_grow_time
>= now
.tv_sec
- 150)
2330 soon
|= neighbourhood_maintenance(AF_INET6
);
2333 /* Given the timeouts in bucket_maintenance, with a 22-bucket
2334 table, worst case is a ping every 18 seconds (22 buckets plus
2335 11 buckets overhead for the larger buckets). Keep the "soon"
2336 case within 15 seconds, which gives some margin for neighbourhood
2340 confirm_nodes_time
= now
.tv_sec
+ 5 + random() % 10;
2342 confirm_nodes_time
= now
.tv_sec
+ 60 + random() % 120;
2345 if(confirm_nodes_time
> now
.tv_sec
)
2346 *tosleep
= confirm_nodes_time
- now
.tv_sec
;
2350 if(search_time
> 0) {
2351 if(search_time
<= now
.tv_sec
)
2353 else if(*tosleep
> search_time
- now
.tv_sec
)
2354 *tosleep
= search_time
- now
.tv_sec
;
2361 dht_get_nodes(struct sockaddr_in
*sin
, int *num
,
2362 struct sockaddr_in6
*sin6
, int *num6
)
2370 /* For restoring to work without discarding too many nodes, the list
2371 must start with the contents of our bucket. */
2372 b
= find_bucket(myid
, AF_INET
);
2377 while(n
&& i
< *num
) {
2379 sin
[i
] = *(struct sockaddr_in
*)&n
->ss
;
2386 while(b
&& i
< *num
) {
2387 if(!in_bucket(myid
, b
)) {
2389 while(n
&& i
< *num
) {
2391 sin
[i
] = *(struct sockaddr_in
*)&n
->ss
;
2404 b
= find_bucket(myid
, AF_INET6
);
2409 while(n
&& j
< *num6
) {
2411 sin6
[j
] = *(struct sockaddr_in6
*)&n
->ss
;
2418 while(b
&& j
< *num6
) {
2419 if(!in_bucket(myid
, b
)) {
2421 while(n
&& j
< *num6
) {
2423 sin6
[j
] = *(struct sockaddr_in6
*)&n
->ss
;
2440 dht_insert_node(const unsigned char *id
, struct sockaddr
*sa
, int salen
)
2444 if(sa
->sa_family
!= AF_INET
&& sa
->sa_family
!= AF_INET6
) {
2445 errno
= EAFNOSUPPORT
;
2449 n
= new_node(id
, sa
, salen
, 0);
2454 dht_ping_node(const struct sockaddr
*sa
, int salen
)
2456 unsigned char tid
[4];
2458 debugf("Sending ping.\n");
2459 make_tid(tid
, "pn", 0);
2460 return send_ping(sa
, salen
, tid
, 4);
2463 /* We could use a proper bencoding printer and parser, but the format of
2464 DHT messages is fairly stylised, so this seemed simpler. */
2466 #define CHECK(offset, delta, size) \
2467 if(delta < 0 || offset + delta > size) goto fail
2469 #define INC(offset, delta, size) \
2470 CHECK(offset, delta, size); \
2473 #define COPY(buf, offset, src, delta, size) \
2474 CHECK(offset, delta, size); \
2475 memcpy(buf + offset, src, delta); \
2478 #define ADD_V(buf, offset, size) \
2480 COPY(buf, offset, my_v, sizeof(my_v), size); \
2484 dht_send(const void *buf
, size_t len
, int flags
,
2485 const struct sockaddr
*sa
, int salen
)
2492 if(node_blacklisted(sa
, salen
)) {
2493 debugf("Attempting to send to blacklisted node.\n");
2498 if(sa
->sa_family
== AF_INET
)
2500 else if(sa
->sa_family
== AF_INET6
)
2506 errno
= EAFNOSUPPORT
;
2510 return dht_sendto(s
, buf
, len
, flags
, sa
, salen
);
2514 send_ping(const struct sockaddr
*sa
, int salen
,
2515 const unsigned char *tid
, int tid_len
)
2519 rc
= snprintf(buf
+ i
, 512 - i
, "d1:ad2:id20:"); INC(i
, rc
, 512);
2520 COPY(buf
, i
, myid
, 20, 512);
2521 rc
= snprintf(buf
+ i
, 512 - i
, "e1:q4:ping1:t%d:", tid_len
);
2523 COPY(buf
, i
, tid
, tid_len
, 512);
2525 rc
= snprintf(buf
+ i
, 512 - i
, "1:y1:qe"); INC(i
, rc
, 512);
2526 return dht_send(buf
, i
, 0, sa
, salen
);
2534 send_pong(const struct sockaddr
*sa
, int salen
,
2535 const unsigned char *tid
, int tid_len
)
2539 rc
= snprintf(buf
+ i
, 512 - i
, "d1:rd2:id20:"); INC(i
, rc
, 512);
2540 COPY(buf
, i
, myid
, 20, 512);
2541 rc
= snprintf(buf
+ i
, 512 - i
, "e1:t%d:", tid_len
); INC(i
, rc
, 512);
2542 COPY(buf
, i
, tid
, tid_len
, 512);
2544 rc
= snprintf(buf
+ i
, 512 - i
, "1:y1:re"); INC(i
, rc
, 512);
2545 return dht_send(buf
, i
, 0, sa
, salen
);
2553 send_find_node(const struct sockaddr
*sa
, int salen
,
2554 const unsigned char *tid
, int tid_len
,
2555 const unsigned char *target
, int want
, int confirm
)
2559 rc
= snprintf(buf
+ i
, 512 - i
, "d1:ad2:id20:"); INC(i
, rc
, 512);
2560 COPY(buf
, i
, myid
, 20, 512);
2561 rc
= snprintf(buf
+ i
, 512 - i
, "6:target20:"); INC(i
, rc
, 512);
2562 COPY(buf
, i
, target
, 20, 512);
2564 rc
= snprintf(buf
+ i
, 512 - i
, "4:wantl%s%se",
2565 (want
& WANT4
) ? "2:n4" : "",
2566 (want
& WANT6
) ? "2:n6" : "");
2569 rc
= snprintf(buf
+ i
, 512 - i
, "e1:q9:find_node1:t%d:", tid_len
);
2571 COPY(buf
, i
, tid
, tid_len
, 512);
2573 rc
= snprintf(buf
+ i
, 512 - i
, "1:y1:qe"); INC(i
, rc
, 512);
2574 return dht_send(buf
, i
, confirm
? MSG_CONFIRM
: 0, sa
, salen
);
2582 send_nodes_peers(const struct sockaddr
*sa
, int salen
,
2583 const unsigned char *tid
, int tid_len
,
2584 const unsigned char *nodes
, int nodes_len
,
2585 const unsigned char *nodes6
, int nodes6_len
,
2586 int af
, struct storage
*st
,
2587 const unsigned char *token
, int token_len
)
2590 int i
= 0, rc
, j0
, j
, k
, len
;
2592 rc
= snprintf(buf
+ i
, 2048 - i
, "d1:rd2:id20:"); INC(i
, rc
, 2048);
2593 COPY(buf
, i
, myid
, 20, 2048);
2595 rc
= snprintf(buf
+ i
, 2048 - i
, "5:nodes%d:", nodes_len
);
2597 COPY(buf
, i
, nodes
, nodes_len
, 2048);
2599 if(nodes6_len
> 0) {
2600 rc
= snprintf(buf
+ i
, 2048 - i
, "6:nodes6%d:", nodes6_len
);
2602 COPY(buf
, i
, nodes6
, nodes6_len
, 2048);
2605 rc
= snprintf(buf
+ i
, 2048 - i
, "5:token%d:", token_len
);
2607 COPY(buf
, i
, token
, token_len
, 2048);
2610 if(st
&& st
->numpeers
> 0) {
2611 /* We treat the storage as a circular list, and serve a randomly
2612 chosen slice. In order to make sure we fit within 1024 octets,
2613 we limit ourselves to 50 peers. */
2615 len
= af
== AF_INET
? 4 : 16;
2616 j0
= random() % st
->numpeers
;
2620 rc
= snprintf(buf
+ i
, 2048 - i
, "6:valuesl"); INC(i
, rc
, 2048);
2622 if(st
->peers
[j
].len
== len
) {
2623 unsigned short swapped
;
2624 swapped
= htons(st
->peers
[j
].port
);
2625 rc
= snprintf(buf
+ i
, 2048 - i
, "%d:", len
+ 2);
2627 COPY(buf
, i
, st
->peers
[j
].ip
, len
, 2048);
2628 COPY(buf
, i
, &swapped
, 2, 2048);
2631 j
= (j
+ 1) % st
->numpeers
;
2632 } while(j
!= j0
&& k
< 50);
2633 rc
= snprintf(buf
+ i
, 2048 - i
, "e"); INC(i
, rc
, 2048);
2636 rc
= snprintf(buf
+ i
, 2048 - i
, "e1:t%d:", tid_len
); INC(i
, rc
, 2048);
2637 COPY(buf
, i
, tid
, tid_len
, 2048);
2638 ADD_V(buf
, i
, 2048);
2639 rc
= snprintf(buf
+ i
, 2048 - i
, "1:y1:re"); INC(i
, rc
, 2048);
2641 return dht_send(buf
, i
, 0, sa
, salen
);
2649 insert_closest_node(unsigned char *nodes
, int numnodes
,
2650 const unsigned char *id
, struct node
*n
)
2654 if(n
->ss
.ss_family
== AF_INET
)
2656 else if(n
->ss
.ss_family
== AF_INET6
)
2661 for(i
= 0; i
< numnodes
; i
++) {
2662 if(id_cmp(n
->id
, nodes
+ size
* i
) == 0)
2664 if(xorcmp(n
->id
, nodes
+ size
* i
, id
) < 0)
2674 if(i
< numnodes
- 1)
2675 memmove(nodes
+ size
* (i
+ 1), nodes
+ size
* i
,
2676 size
* (numnodes
- i
- 1));
2678 if(n
->ss
.ss_family
== AF_INET
) {
2679 struct sockaddr_in
*sin
= (struct sockaddr_in
*)&n
->ss
;
2680 memcpy(nodes
+ size
* i
, n
->id
, 20);
2681 memcpy(nodes
+ size
* i
+ 20, &sin
->sin_addr
, 4);
2682 memcpy(nodes
+ size
* i
+ 24, &sin
->sin_port
, 2);
2683 } else if(n
->ss
.ss_family
== AF_INET6
) {
2684 struct sockaddr_in6
*sin6
= (struct sockaddr_in6
*)&n
->ss
;
2685 memcpy(nodes
+ size
* i
, n
->id
, 20);
2686 memcpy(nodes
+ size
* i
+ 20, &sin6
->sin6_addr
, 16);
2687 memcpy(nodes
+ size
* i
+ 36, &sin6
->sin6_port
, 2);
2696 buffer_closest_nodes(unsigned char *nodes
, int numnodes
,
2697 const unsigned char *id
, struct bucket
*b
)
2699 struct node
*n
= b
->nodes
;
2702 numnodes
= insert_closest_node(nodes
, numnodes
, id
, n
);
2709 send_closest_nodes(const struct sockaddr
*sa
, int salen
,
2710 const unsigned char *tid
, int tid_len
,
2711 const unsigned char *id
, int want
,
2712 int af
, struct storage
*st
,
2713 const unsigned char *token
, int token_len
)
2715 unsigned char nodes
[8 * 26];
2716 unsigned char nodes6
[8 * 38];
2717 int numnodes
= 0, numnodes6
= 0;
2721 want
= sa
->sa_family
== AF_INET
? WANT4
: WANT6
;
2723 if((want
& WANT4
)) {
2724 b
= find_bucket(id
, AF_INET
);
2726 numnodes
= buffer_closest_nodes(nodes
, numnodes
, id
, b
);
2728 numnodes
= buffer_closest_nodes(nodes
, numnodes
, id
, b
->next
);
2729 b
= previous_bucket(b
);
2731 numnodes
= buffer_closest_nodes(nodes
, numnodes
, id
, b
);
2735 if((want
& WANT6
)) {
2736 b
= find_bucket(id
, AF_INET6
);
2738 numnodes6
= buffer_closest_nodes(nodes6
, numnodes6
, id
, b
);
2741 buffer_closest_nodes(nodes6
, numnodes6
, id
, b
->next
);
2742 b
= previous_bucket(b
);
2744 numnodes6
= buffer_closest_nodes(nodes6
, numnodes6
, id
, b
);
2747 debugf(" (%d+%d nodes.)\n", numnodes
, numnodes6
);
2749 return send_nodes_peers(sa
, salen
, tid
, tid_len
,
2750 nodes
, numnodes
* 26,
2751 nodes6
, numnodes6
* 38,
2752 af
, st
, token
, token_len
);
2756 send_get_peers(const struct sockaddr
*sa
, int salen
,
2757 unsigned char *tid
, int tid_len
, unsigned char *infohash
,
2758 int want
, int confirm
)
2763 rc
= snprintf(buf
+ i
, 512 - i
, "d1:ad2:id20:"); INC(i
, rc
, 512);
2764 COPY(buf
, i
, myid
, 20, 512);
2765 rc
= snprintf(buf
+ i
, 512 - i
, "9:info_hash20:"); INC(i
, rc
, 512);
2766 COPY(buf
, i
, infohash
, 20, 512);
2768 rc
= snprintf(buf
+ i
, 512 - i
, "4:wantl%s%se",
2769 (want
& WANT4
) ? "2:n4" : "",
2770 (want
& WANT6
) ? "2:n6" : "");
2773 rc
= snprintf(buf
+ i
, 512 - i
, "e1:q9:get_peers1:t%d:", tid_len
);
2775 COPY(buf
, i
, tid
, tid_len
, 512);
2777 rc
= snprintf(buf
+ i
, 512 - i
, "1:y1:qe"); INC(i
, rc
, 512);
2778 return dht_send(buf
, i
, confirm
? MSG_CONFIRM
: 0, sa
, salen
);
2786 send_announce_peer(const struct sockaddr
*sa
, int salen
,
2787 unsigned char *tid
, int tid_len
,
2788 unsigned char *infohash
, unsigned short port
,
2789 unsigned char *token
, int token_len
, int confirm
)
2794 rc
= snprintf(buf
+ i
, 512 - i
, "d1:ad2:id20:"); INC(i
, rc
, 512);
2795 COPY(buf
, i
, myid
, 20, 512);
2796 rc
= snprintf(buf
+ i
, 512 - i
, "12:implied_porti1e9:info_hash20:"); INC(i
, rc
, 512);
2797 COPY(buf
, i
, infohash
, 20, 512);
2798 rc
= snprintf(buf
+ i
, 512 - i
, "4:porti%ue5:token%d:", (unsigned)port
,
2801 COPY(buf
, i
, token
, token_len
, 512);
2802 rc
= snprintf(buf
+ i
, 512 - i
, "e1:q13:announce_peer1:t%d:", tid_len
);
2804 COPY(buf
, i
, tid
, tid_len
, 512);
2806 rc
= snprintf(buf
+ i
, 512 - i
, "1:y1:qe"); INC(i
, rc
, 512);
2808 return dht_send(buf
, i
, confirm
? 0 : MSG_CONFIRM
, sa
, salen
);
2816 send_peer_announced(const struct sockaddr
*sa
, int salen
,
2817 unsigned char *tid
, int tid_len
)
2822 rc
= snprintf(buf
+ i
, 512 - i
, "d1:rd2:id20:"); INC(i
, rc
, 512);
2823 COPY(buf
, i
, myid
, 20, 512);
2824 rc
= snprintf(buf
+ i
, 512 - i
, "e1:t%d:", tid_len
);
2826 COPY(buf
, i
, tid
, tid_len
, 512);
2828 rc
= snprintf(buf
+ i
, 512 - i
, "1:y1:re"); INC(i
, rc
, 512);
2829 return dht_send(buf
, i
, 0, sa
, salen
);
2837 send_error(const struct sockaddr
*sa
, int salen
,
2838 unsigned char *tid
, int tid_len
,
2839 int code
, const char *message
)
2842 int i
= 0, rc
, message_len
;
2844 message_len
= strlen(message
);
2845 rc
= snprintf(buf
+ i
, 512 - i
, "d1:eli%de%d:", code
, message_len
);
2847 COPY(buf
, i
, message
, message_len
, 512);
2848 rc
= snprintf(buf
+ i
, 512 - i
, "e1:t%d:", tid_len
); INC(i
, rc
, 512);
2849 COPY(buf
, i
, tid
, tid_len
, 512);
2851 rc
= snprintf(buf
+ i
, 512 - i
, "1:y1:ee"); INC(i
, rc
, 512);
2852 return dht_send(buf
, i
, 0, sa
, salen
);
2867 dht_memmem(const void *haystack
, size_t haystacklen
,
2868 const void *needle
, size_t needlelen
)
2870 return memmem(haystack
, haystacklen
, needle
, needlelen
);
2876 dht_memmem(const void *haystack
, size_t haystacklen
,
2877 const void *needle
, size_t needlelen
)
2879 const char *h
= haystack
;
2880 const char *n
= needle
;
2883 /* size_t is unsigned */
2884 if(needlelen
> haystacklen
)
2887 for(i
= 0; i
<= haystacklen
- needlelen
; i
++) {
2888 if(memcmp(h
+ i
, n
, needlelen
) == 0)
2889 return (void*)(h
+ i
);
2897 parse_message(const unsigned char *buf
, int buflen
,
2898 struct parsed_message
*m
)
2900 const unsigned char *p
;
2902 /* This code will happily crash if the buffer is not NUL-terminated. */
2903 if(buf
[buflen
] != '\0') {
2904 debugf("Eek! parse_message with unterminated buffer.\n");
2909 #define CHECK(ptr, len) \
2910 if(((unsigned char*)ptr) + (len) > (buf) + (buflen)) goto overflow;
2912 p
= dht_memmem(buf
, buflen
, "1:t", 3);
2916 l
= strtol((char*)p
+ 3, &q
, 10);
2917 if(q
&& *q
== ':' && l
> 0 && l
< PARSE_TID_LEN
) {
2919 memcpy(m
->tid
, q
+ 1, l
);
2924 p
= dht_memmem(buf
, buflen
, "2:id20:", 7);
2927 memcpy(m
->id
, p
+ 7, 20);
2930 p
= dht_memmem(buf
, buflen
, "9:info_hash20:", 14);
2933 memcpy(m
->info_hash
, p
+ 14, 20);
2936 p
= dht_memmem(buf
, buflen
, "4:porti", 7);
2940 l
= strtol((char*)p
+ 7, &q
, 10);
2941 if(q
&& *q
== 'e' && l
> 0 && l
< 0x10000)
2945 p
= dht_memmem(buf
, buflen
, "12:implied_porti", 16);
2949 l
= strtol((char*)p
+ 16, &q
, 10);
2950 if(q
&& *q
== 'e' && l
> 0 && l
< 0x10000)
2951 m
->implied_port
= l
;
2954 p
= dht_memmem(buf
, buflen
, "6:target20:", 11);
2957 memcpy(m
->target
, p
+ 11, 20);
2960 p
= dht_memmem(buf
, buflen
, "5:token", 7);
2964 l
= strtol((char*)p
+ 7, &q
, 10);
2965 if(q
&& *q
== ':' && l
> 0 && l
< PARSE_TOKEN_LEN
) {
2967 memcpy(m
->token
, q
+ 1, l
);
2972 p
= dht_memmem(buf
, buflen
, "5:nodes", 7);
2976 l
= strtol((char*)p
+ 7, &q
, 10);
2977 if(q
&& *q
== ':' && l
> 0 && l
<= PARSE_NODES_LEN
) {
2979 memcpy(m
->nodes
, q
+ 1, l
);
2984 p
= dht_memmem(buf
, buflen
, "6:nodes6", 8);
2988 l
= strtol((char*)p
+ 8, &q
, 10);
2989 if(q
&& *q
== ':' && l
> 0 && l
<= PARSE_NODES6_LEN
) {
2991 memcpy(m
->nodes6
, q
+ 1, l
);
2996 p
= dht_memmem(buf
, buflen
, "6:valuesl", 9);
2998 int i
= p
- buf
+ 9;
3003 l
= strtol((char*)buf
+ i
, &q
, 10);
3004 if(q
&& *q
== ':' && l
> 0) {
3006 i
= q
+ 1 + l
- (char*)buf
;
3008 if(j
+ l
> PARSE_VALUES_LEN
)
3010 memcpy((char*)m
->values
+ j
, q
+ 1, l
);
3012 } else if(l
== 18) {
3013 if(j6
+ l
> PARSE_VALUES6_LEN
)
3015 memcpy((char*)m
->values6
+ j6
, q
+ 1, l
);
3018 debugf("Received weird value -- %d bytes.\n", (int)l
);
3024 if(i
>= buflen
|| buf
[i
] != 'e')
3025 debugf("eek... unexpected end for values.\n");
3027 m
->values6_len
= j6
;
3030 p
= dht_memmem(buf
, buflen
, "4:wantl", 7);
3032 int i
= p
- buf
+ 7;
3034 while(buf
[i
] > '0' && buf
[i
] <= '9' && buf
[i
+ 1] == ':' &&
3035 i
+ 2 + buf
[i
] - '0' < buflen
) {
3036 CHECK(buf
+ i
+ 2, buf
[i
] - '0');
3037 if(buf
[i
] == '2' && memcmp(buf
+ i
+ 2, "n4", 2) == 0)
3039 else if(buf
[i
] == '2' && memcmp(buf
+ i
+ 2, "n6", 2) == 0)
3042 debugf("eek... unexpected want flag (%c)\n", buf
[i
]);
3043 i
+= 2 + buf
[i
] - '0';
3045 if(i
>= buflen
|| buf
[i
] != 'e')
3046 debugf("eek... unexpected end for want.\n");
3051 if(dht_memmem(buf
, buflen
, "1:y1:r", 6))
3053 if(dht_memmem(buf
, buflen
, "1:y1:e", 6))
3055 if(!dht_memmem(buf
, buflen
, "1:y1:q", 6))
3057 if(dht_memmem(buf
, buflen
, "1:q4:ping", 9))
3059 if(dht_memmem(buf
, buflen
, "1:q9:find_node", 14))
3061 if(dht_memmem(buf
, buflen
, "1:q9:get_peers", 14))
3063 if(dht_memmem(buf
, buflen
, "1:q13:announce_peer", 19))
3064 return ANNOUNCE_PEER
;
3068 debugf("Truncated message.\n");