Commit MetaInfo

Revisionbeef8a621eb3d41d36dbfddb70431db99da9544c (tree)
Time2020-07-04 19:11:17
Authorsimphone
Commitersimphone

Log Message

dht 0.26

Change Summary

Incremental Difference

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