summaryrefslogtreecommitdiff
path: root/core/DHT.c
diff options
context:
space:
mode:
Diffstat (limited to 'core/DHT.c')
-rw-r--r--core/DHT.c1264
1 files changed, 0 insertions, 1264 deletions
diff --git a/core/DHT.c b/core/DHT.c
deleted file mode 100644
index 533425c4..00000000
--- a/core/DHT.c
+++ /dev/null
@@ -1,1264 +0,0 @@
1/* DHT.c
2 *
3 * An implementation of the DHT as seen in http://wiki.tox.im/index.php/DHT
4 *
5 * Copyright (C) 2013 Tox project All Rights Reserved.
6 *
7 * This file is part of Tox.
8 *
9 * Tox is free software: you can redistribute it and/or modify
10 * it under the terms of the GNU General Public License as published by
11 * the Free Software Foundation, either version 3 of the License, or
12 * (at your option) any later version.
13 *
14 * Tox is distributed in the hope that it will be useful,
15 * but WITHOUT ANY WARRANTY; without even the implied warranty of
16 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 * GNU General Public License for more details.
18 *
19 * You should have received a copy of the GNU General Public License
20 * along with Tox. If not, see <http://www.gnu.org/licenses/>.
21 *
22 */
23
24/*----------------------------------------------------------------------------------*/
25
26#include "DHT.h"
27#include "packets.h"
28#include "ping.h"
29
30/* the number of seconds for a non responsive node to become bad. */
31#define BAD_NODE_TIMEOUT 70
32
33/* the max number of nodes to send with send nodes. */
34#define MAX_SENT_NODES 8
35
36/* ping timeout in seconds */
37#define PING_TIMEOUT 5
38
39/* The timeout after which a node is discarded completely. */
40#define Kill_NODE_TIMEOUT 300
41
42/* ping interval in seconds for each node in our lists. */
43#define PING_INTERVAL 60
44
45/* ping interval in seconds for each random sending of a get nodes request. */
46#define GET_NODE_INTERVAL 10
47
48#define MAX_PUNCHING_PORTS 32
49
50/*Interval in seconds between punching attempts*/
51#define PUNCH_INTERVAL 10
52
53/*Ping newly announced nodes to ping per TIME_TOPING seconds*/
54#define TIME_TOPING 5
55
56#define NAT_PING_REQUEST 0
57#define NAT_PING_RESPONSE 1
58
59
60Client_data *DHT_get_close_list(DHT *dht)
61{
62 return dht->close_clientlist;
63}
64
65/* Compares client_id1 and client_id2 with client_id
66 * return 0 if both are same distance
67 * return 1 if client_id1 is closer
68 * return 2 if client_id2 is closer
69 */
70static int id_closest(uint8_t *id, uint8_t *id1, uint8_t *id2)
71{
72 size_t i;
73 uint8_t distance1, distance2;
74
75 for (i = 0; i < CLIENT_ID_SIZE; ++i) {
76
77 distance1 = abs(id[i] ^ id1[i]);
78 distance2 = abs(id[i] ^ id2[i]);
79
80 if (distance1 < distance2)
81 return 1;
82
83 if (distance1 > distance2)
84 return 2;
85 }
86
87 return 0;
88}
89
90static int ipport_equal(IP_Port a, IP_Port b)
91{
92 return (a.ip.i == b.ip.i) && (a.port == b.port);
93}
94
95static int id_equal(uint8_t *a, uint8_t *b)
96{
97 return memcmp(a, b, CLIENT_ID_SIZE) == 0;
98}
99
100static int is_timeout(uint64_t time_now, uint64_t timestamp, uint64_t timeout)
101{
102 return timestamp + timeout <= time_now;
103}
104
105/* check if client with client_id is already in list of length length.
106 * if it is then set its corresponding timestamp to current time.
107 * if the id is already in the list with a different ip_port, update it.
108 * return True(1) or False(0)
109 *
110 * TODO: maybe optimize this.
111 */
112static int client_in_list(Client_data *list, uint32_t length, uint8_t *client_id, IP_Port ip_port)
113{
114 uint32_t i;
115 uint64_t temp_time = unix_time();
116
117 for (i = 0; i < length; ++i) {
118 /*If ip_port is assigned to a different client_id replace it*/
119 if (ipport_equal(list[i].ip_port, ip_port)) {
120 memcpy(list[i].client_id, client_id, CLIENT_ID_SIZE);
121 }
122
123 if (id_equal(list[i].client_id, client_id)) {
124 /* Refresh the client timestamp. */
125 list[i].timestamp = temp_time;
126 list[i].ip_port.ip.i = ip_port.ip.i;
127 list[i].ip_port.port = ip_port.port;
128 return 1;
129 }
130 }
131
132 return 0;
133}
134
135/* check if client with client_id is already in node format list of length length.
136 * return True(1) or False(0)
137 */
138static int client_in_nodelist(Node_format *list, uint32_t length, uint8_t *client_id)
139{
140 uint32_t i;
141
142 for (i = 0; i < length; ++i) {
143 if (id_equal(list[i].client_id, client_id))
144 return 1;
145 }
146
147 return 0;
148}
149
150/* Returns the friend number from the client_id, or -1 if a failure occurs
151 */
152static int friend_number(DHT *dht, uint8_t *client_id)
153{
154 uint32_t i;
155
156 for (i = 0; i < dht->num_friends; ++i) {
157 if (id_equal(dht->friends_list[i].client_id, client_id))
158 return i;
159 }
160
161 return -1;
162}
163
164/* Find MAX_SENT_NODES nodes closest to the client_id for the send nodes request:
165 * put them in the nodes_list and return how many were found.
166 *
167 * TODO: For the love of based Allah make this function cleaner and much more efficient.
168 */
169static int get_close_nodes(DHT *dht, uint8_t *client_id, Node_format *nodes_list)
170{
171 uint32_t i, j, k;
172 uint64_t temp_time = unix_time();
173 int num_nodes = 0, closest, tout, inlist;
174
175 for (i = 0; i < LCLIENT_LIST; ++i) {
176 tout = is_timeout(temp_time, dht->close_clientlist[i].timestamp, BAD_NODE_TIMEOUT);
177 inlist = client_in_nodelist(nodes_list, MAX_SENT_NODES, dht->close_clientlist[i].client_id);
178
179 /* if node isn't good or is already in list. */
180 if (tout || inlist)
181 continue;
182
183 if (num_nodes < MAX_SENT_NODES) {
184
185 memcpy( nodes_list[num_nodes].client_id,
186 dht->close_clientlist[i].client_id,
187 CLIENT_ID_SIZE );
188
189 nodes_list[num_nodes].ip_port = dht->close_clientlist[i].ip_port;
190 num_nodes++;
191
192 } else {
193
194 for (j = 0; j < MAX_SENT_NODES; ++j) {
195 closest = id_closest( client_id,
196 nodes_list[j].client_id,
197 dht->close_clientlist[i].client_id );
198
199 if (closest == 2) {
200 memcpy( nodes_list[j].client_id,
201 dht->close_clientlist[i].client_id,
202 CLIENT_ID_SIZE);
203
204 nodes_list[j].ip_port = dht->close_clientlist[i].ip_port;
205 break;
206 }
207 }
208 }
209 }
210
211 for (i = 0; i < dht->num_friends; ++i) {
212 for (j = 0; j < MAX_FRIEND_CLIENTS; ++j) {
213
214 tout = is_timeout(temp_time, dht->friends_list[i].client_list[j].timestamp, BAD_NODE_TIMEOUT);
215 inlist = client_in_nodelist( nodes_list,
216 MAX_SENT_NODES,
217 dht->friends_list[i].client_list[j].client_id);
218
219 /* if node isn't good or is already in list. */
220 if (tout || inlist)
221 continue;
222
223 if (num_nodes < MAX_SENT_NODES) {
224
225 memcpy( nodes_list[num_nodes].client_id,
226 dht->friends_list[i].client_list[j].client_id,
227 CLIENT_ID_SIZE);
228
229 nodes_list[num_nodes].ip_port = dht->friends_list[i].client_list[j].ip_port;
230 num_nodes++;
231 } else {
232 for (k = 0; k < MAX_SENT_NODES; ++k) {
233
234 closest = id_closest( client_id,
235 nodes_list[k].client_id,
236 dht->friends_list[i].client_list[j].client_id );
237
238 if (closest == 2) {
239 memcpy( nodes_list[k].client_id,
240 dht->friends_list[i].client_list[j].client_id,
241 CLIENT_ID_SIZE );
242
243 nodes_list[k].ip_port = dht->friends_list[i].client_list[j].ip_port;
244 break;
245 }
246 }
247 }
248 }
249 }
250
251 return num_nodes;
252}
253
254/* replace first bad (or empty) node with this one
255 * return 0 if successful
256 * return 1 if not (list contains no bad nodes)
257 */
258static int replace_bad( Client_data *list,
259 uint32_t length,
260 uint8_t *client_id,
261 IP_Port ip_port )
262{
263 uint32_t i;
264 uint64_t temp_time = unix_time();
265
266 for (i = 0; i < length; ++i) {
267 /* if node is bad */
268 if (is_timeout(temp_time, list[i].timestamp, BAD_NODE_TIMEOUT)) {
269 memcpy(list[i].client_id, client_id, CLIENT_ID_SIZE);
270 list[i].ip_port = ip_port;
271 list[i].timestamp = temp_time;
272 list[i].ret_ip_port.ip.i = 0;
273 list[i].ret_ip_port.port = 0;
274 list[i].ret_timestamp = 0;
275 return 0;
276 }
277 }
278
279 return 1;
280}
281/*Sort the list. It will be sorted from furthest to closest.
282 TODO: this is innefficient and needs to be optimized.*/
283static void sort_list(Client_data *list, uint32_t length, uint8_t *comp_client_id)
284{
285 if (length == 0)
286 return;
287
288 uint32_t i, count;
289
290 while (1) {
291 count = 0;
292
293 for (i = 0; i < (length - 1); ++i) {
294 if (id_closest(comp_client_id, list[i].client_id, list[i + 1].client_id) == 1) {
295 Client_data temp = list[i + 1];
296 list[i + 1] = list[i];
297 list[i] = temp;
298 ++count;
299 }
300 }
301
302 if (count == 0)
303 return;
304 }
305}
306
307
308/* replace the first good node that is further to the comp_client_id than that of the client_id in the list */
309static int replace_good( Client_data *list,
310 uint32_t length,
311 uint8_t *client_id,
312 IP_Port ip_port,
313 uint8_t *comp_client_id )
314{
315 uint32_t i;
316 uint64_t temp_time = unix_time();
317 sort_list(list, length, comp_client_id);
318
319 for (i = 0; i < length; ++i)
320 if (id_closest(comp_client_id, list[i].client_id, client_id) == 2) {
321 memcpy(list[i].client_id, client_id, CLIENT_ID_SIZE);
322 list[i].ip_port = ip_port;
323 list[i].timestamp = temp_time;
324 list[i].ret_ip_port.ip.i = 0;
325 list[i].ret_ip_port.port = 0;
326 list[i].ret_timestamp = 0;
327 return 0;
328 }
329
330 return 1;
331}
332
333/* Attempt to add client with ip_port and client_id to the friends client list
334 * and close_clientlist
335 */
336void addto_lists(DHT *dht, IP_Port ip_port, uint8_t *client_id)
337{
338 uint32_t i;
339
340 /* NOTE: current behavior if there are two clients with the same id is
341 * to replace the first ip by the second.
342 */
343 if (!client_in_list(dht->close_clientlist, LCLIENT_LIST, client_id, ip_port)) {
344 if (replace_bad(dht->close_clientlist, LCLIENT_LIST, client_id, ip_port)) {
345 /* if we can't replace bad nodes we try replacing good ones */
346 replace_good( dht->close_clientlist,
347 LCLIENT_LIST,
348 client_id,
349 ip_port,
350 dht->c->self_public_key );
351 }
352 }
353
354 for (i = 0; i < dht->num_friends; ++i) {
355 if (!client_in_list( dht->friends_list[i].client_list,
356 MAX_FRIEND_CLIENTS,
357 client_id,
358 ip_port )) {
359
360 if (replace_bad( dht->friends_list[i].client_list,
361 MAX_FRIEND_CLIENTS,
362 client_id,
363 ip_port )) {
364 /* if we can't replace bad nodes we try replacing good ones. */
365 replace_good( dht->friends_list[i].client_list,
366 MAX_FRIEND_CLIENTS,
367 client_id,
368 ip_port,
369 dht->friends_list[i].client_id );
370 }
371 }
372 }
373}
374
375/* If client_id is a friend or us, update ret_ip_port
376 * nodeclient_id is the id of the node that sent us this info
377 */
378static void returnedip_ports(DHT *dht, IP_Port ip_port, uint8_t *client_id, uint8_t *nodeclient_id)
379{
380 uint32_t i, j;
381 uint64_t temp_time = unix_time();
382
383 if (id_equal(client_id, dht->c->self_public_key)) {
384
385 for (i = 0; i < LCLIENT_LIST; ++i) {
386 if (id_equal(nodeclient_id, dht->close_clientlist[i].client_id)) {
387 dht->close_clientlist[i].ret_ip_port = ip_port;
388 dht->close_clientlist[i].ret_timestamp = temp_time;
389 return;
390 }
391 }
392
393 } else {
394
395 for (i = 0; i < dht->num_friends; ++i) {
396 if (id_equal(client_id, dht->friends_list[i].client_id)) {
397
398 for (j = 0; j < MAX_FRIEND_CLIENTS; ++j) {
399 if (id_equal(nodeclient_id, dht->friends_list[i].client_list[j].client_id)) {
400 dht->friends_list[i].client_list[j].ret_ip_port = ip_port;
401 dht->friends_list[i].client_list[j].ret_timestamp = temp_time;
402 return;
403 }
404 }
405 }
406 }
407
408 }
409}
410
411/* Same as last function but for get_node requests. */
412static int is_gettingnodes(DHT *dht, IP_Port ip_port, uint64_t ping_id)
413{
414 uint32_t i;
415 uint8_t pinging;
416 uint64_t temp_time = unix_time();
417
418 for (i = 0; i < LSEND_NODES_ARRAY; ++i ) {
419 if (!is_timeout(temp_time, dht->send_nodes[i].timestamp, PING_TIMEOUT)) {
420 pinging = 0;
421
422 if (ip_port.ip.i != 0 && ipport_equal(dht->send_nodes[i].ip_port, ip_port))
423 ++pinging;
424
425 if (ping_id != 0 && dht->send_nodes[i].ping_id == ping_id)
426 ++pinging;
427
428 if (pinging == (ping_id != 0) + (ip_port.ip.i != 0))
429 return 1;
430 }
431 }
432
433 return 0;
434}
435
436/* Same but for get node requests */
437static uint64_t add_gettingnodes(DHT *dht, IP_Port ip_port)
438{
439 uint32_t i, j;
440 uint64_t ping_id = ((uint64_t)random_int() << 32) + random_int();
441 uint64_t temp_time = unix_time();
442
443 for (i = 0; i < PING_TIMEOUT; ++i ) {
444 for (j = 0; j < LSEND_NODES_ARRAY; ++j ) {
445 if (is_timeout(temp_time, dht->send_nodes[j].timestamp, PING_TIMEOUT - i)) {
446 dht->send_nodes[j].timestamp = temp_time;
447 dht->send_nodes[j].ip_port = ip_port;
448 dht->send_nodes[j].ping_id = ping_id;
449 return ping_id;
450 }
451 }
452 }
453
454 return 0;
455}
456
457/* send a getnodes request */
458static int getnodes(DHT *dht, IP_Port ip_port, uint8_t *public_key, uint8_t *client_id)
459{
460 /* check if packet is gonna be sent to ourself */
461 if (id_equal(public_key, dht->c->self_public_key) || is_gettingnodes(dht, ip_port, 0))
462 return 1;
463
464 uint64_t ping_id = add_gettingnodes(dht, ip_port);
465
466 if (ping_id == 0)
467 return 1;
468
469 uint8_t data[1 + CLIENT_ID_SIZE + crypto_box_NONCEBYTES + sizeof(ping_id) + CLIENT_ID_SIZE + ENCRYPTION_PADDING];
470 uint8_t plain[sizeof(ping_id) + CLIENT_ID_SIZE];
471 uint8_t encrypt[sizeof(ping_id) + CLIENT_ID_SIZE + ENCRYPTION_PADDING];
472 uint8_t nonce[crypto_box_NONCEBYTES];
473 random_nonce(nonce);
474
475 memcpy(plain, &ping_id, sizeof(ping_id));
476 memcpy(plain + sizeof(ping_id), client_id, CLIENT_ID_SIZE);
477
478 int len = encrypt_data( public_key,
479 dht->c->self_secret_key,
480 nonce,
481 plain,
482 sizeof(ping_id) + CLIENT_ID_SIZE,
483 encrypt );
484
485 if (len != sizeof(ping_id) + CLIENT_ID_SIZE + ENCRYPTION_PADDING)
486 return -1;
487
488 data[0] = NET_PACKET_GET_NODES;
489 memcpy(data + 1, dht->c->self_public_key, CLIENT_ID_SIZE);
490 memcpy(data + 1 + CLIENT_ID_SIZE, nonce, crypto_box_NONCEBYTES);
491 memcpy(data + 1 + CLIENT_ID_SIZE + crypto_box_NONCEBYTES, encrypt, len);
492
493 return sendpacket(dht->c->lossless_udp->net->sock, ip_port, data, sizeof(data));
494}
495
496/* send a send nodes response */
497static int sendnodes(DHT *dht, IP_Port ip_port, uint8_t *public_key, uint8_t *client_id, uint64_t ping_id)
498{
499 /* check if packet is gonna be sent to ourself */
500 if (id_equal(public_key, dht->c->self_public_key))
501 return 1;
502
503 uint8_t data[1 + CLIENT_ID_SIZE + crypto_box_NONCEBYTES + sizeof(ping_id)
504 + sizeof(Node_format) * MAX_SENT_NODES + ENCRYPTION_PADDING];
505
506 Node_format nodes_list[MAX_SENT_NODES];
507 int num_nodes = get_close_nodes(dht, client_id, nodes_list);
508
509 if (num_nodes == 0)
510 return 0;
511
512 uint8_t plain[sizeof(ping_id) + sizeof(Node_format) * MAX_SENT_NODES];
513 uint8_t encrypt[sizeof(ping_id) + sizeof(Node_format) * MAX_SENT_NODES + ENCRYPTION_PADDING];
514 uint8_t nonce[crypto_box_NONCEBYTES];
515 random_nonce(nonce);
516
517 memcpy(plain, &ping_id, sizeof(ping_id));
518 memcpy(plain + sizeof(ping_id), nodes_list, num_nodes * sizeof(Node_format));
519
520 int len = encrypt_data( public_key,
521 dht->c->self_secret_key,
522 nonce,
523 plain,
524 sizeof(ping_id) + num_nodes * sizeof(Node_format),
525 encrypt );
526
527 if (len != sizeof(ping_id) + num_nodes * sizeof(Node_format) + ENCRYPTION_PADDING)
528 return -1;
529
530 data[0] = NET_PACKET_SEND_NODES;
531 memcpy(data + 1, dht->c->self_public_key, CLIENT_ID_SIZE);
532 memcpy(data + 1 + CLIENT_ID_SIZE, nonce, crypto_box_NONCEBYTES);
533 memcpy(data + 1 + CLIENT_ID_SIZE + crypto_box_NONCEBYTES, encrypt, len);
534
535 return sendpacket(dht->c->lossless_udp->net->sock, ip_port, data, 1 + CLIENT_ID_SIZE + crypto_box_NONCEBYTES + len);
536}
537
538static int handle_getnodes(void *object, IP_Port source, uint8_t *packet, uint32_t length)
539{
540 DHT *dht = object;
541 uint64_t ping_id;
542
543 if (length != ( 1 + CLIENT_ID_SIZE + crypto_box_NONCEBYTES
544 + sizeof(ping_id) + CLIENT_ID_SIZE + ENCRYPTION_PADDING ))
545 return 1;
546
547 /* check if packet is from ourself. */
548 if (id_equal(packet + 1, dht->c->self_public_key))
549 return 1;
550
551 uint8_t plain[sizeof(ping_id) + CLIENT_ID_SIZE];
552
553 int len = decrypt_data( packet + 1,
554 dht->c->self_secret_key,
555 packet + 1 + CLIENT_ID_SIZE,
556 packet + 1 + CLIENT_ID_SIZE + crypto_box_NONCEBYTES,
557 sizeof(ping_id) + CLIENT_ID_SIZE + ENCRYPTION_PADDING,
558 plain );
559
560 if (len != sizeof(ping_id) + CLIENT_ID_SIZE)
561 return 1;
562
563 memcpy(&ping_id, plain, sizeof(ping_id));
564 sendnodes(dht, source, packet + 1, plain + sizeof(ping_id), ping_id);
565
566 //send_ping_request(dht, source, (clientid_t*) (packet + 1)); /* TODO: make this smarter? */
567
568 return 0;
569}
570
571static int handle_sendnodes(void *object, IP_Port source, uint8_t *packet, uint32_t length)
572{
573 DHT *dht = object;
574 uint64_t ping_id;
575 uint32_t cid_size = 1 + CLIENT_ID_SIZE;
576 cid_size += crypto_box_NONCEBYTES + sizeof(ping_id) + ENCRYPTION_PADDING;
577
578 if (length > (cid_size + sizeof(Node_format) * MAX_SENT_NODES) ||
579 ((length - cid_size) % sizeof(Node_format)) != 0 ||
580 (length < cid_size + sizeof(Node_format)))
581 return 1;
582
583 uint32_t num_nodes = (length - cid_size) / sizeof(Node_format);
584 uint8_t plain[sizeof(ping_id) + sizeof(Node_format) * MAX_SENT_NODES];
585
586 int len = decrypt_data(
587 packet + 1,
588 dht->c->self_secret_key,
589 packet + 1 + CLIENT_ID_SIZE,
590 packet + 1 + CLIENT_ID_SIZE + crypto_box_NONCEBYTES,
591 sizeof(ping_id) + num_nodes * sizeof(Node_format) + ENCRYPTION_PADDING, plain );
592
593 if (len != sizeof(ping_id) + num_nodes * sizeof(Node_format))
594 return 1;
595
596 memcpy(&ping_id, plain, sizeof(ping_id));
597
598 if (!is_gettingnodes(dht, source, ping_id))
599 return 1;
600
601 Node_format nodes_list[MAX_SENT_NODES];
602 memcpy(nodes_list, plain + sizeof(ping_id), num_nodes * sizeof(Node_format));
603
604 addto_lists(dht, source, packet + 1);
605
606 uint32_t i;
607
608 for (i = 0; i < num_nodes; ++i) {
609 send_ping_request(dht->ping, dht->c, nodes_list[i].ip_port, (clientid_t *) &nodes_list[i].client_id);
610 returnedip_ports(dht, nodes_list[i].ip_port, nodes_list[i].client_id, packet + 1);
611 }
612
613 return 0;
614}
615
616/*----------------------------------------------------------------------------------*/
617/*------------------------END of packet handling functions--------------------------*/
618
619int DHT_addfriend(DHT *dht, uint8_t *client_id)
620{
621 if (friend_number(dht, client_id) != -1) /*Is friend already in DHT?*/
622 return 1;
623
624 DHT_Friend *temp;
625 temp = realloc(dht->friends_list, sizeof(DHT_Friend) * (dht->num_friends + 1));
626
627 if (temp == NULL)
628 return 1;
629
630 dht->friends_list = temp;
631 memset(&dht->friends_list[dht->num_friends], 0, sizeof(DHT_Friend));
632 memcpy(dht->friends_list[dht->num_friends].client_id, client_id, CLIENT_ID_SIZE);
633
634 dht->friends_list[dht->num_friends].NATping_id = ((uint64_t)random_int() << 32) + random_int();
635 ++dht->num_friends;
636 return 0;
637}
638
639int DHT_delfriend(DHT *dht, uint8_t *client_id)
640{
641 uint32_t i;
642 DHT_Friend *temp;
643
644 for (i = 0; i < dht->num_friends; ++i) {
645 /* Equal */
646 if (id_equal(dht->friends_list[i].client_id, client_id)) {
647 --dht->num_friends;
648
649 if (dht->num_friends != i) {
650 memcpy( dht->friends_list[i].client_id,
651 dht->friends_list[dht->num_friends].client_id,
652 CLIENT_ID_SIZE );
653 }
654
655 if (dht->num_friends == 0) {
656 free(dht->friends_list);
657 dht->friends_list = NULL;
658 return 0;
659 }
660
661 temp = realloc(dht->friends_list, sizeof(DHT_Friend) * (dht->num_friends));
662
663 if (temp == NULL)
664 return 1;
665
666 dht->friends_list = temp;
667 return 0;
668 }
669 }
670
671 return 1;
672}
673
674/* TODO: Optimize this. */
675IP_Port DHT_getfriendip(DHT *dht, uint8_t *client_id)
676{
677 uint32_t i, j;
678 uint64_t temp_time = unix_time();
679 IP_Port empty = {{{0}}, 0};
680
681 for (i = 0; i < dht->num_friends; ++i) {
682 /* Equal */
683 if (id_equal(dht->friends_list[i].client_id, client_id)) {
684 for (j = 0; j < MAX_FRIEND_CLIENTS; ++j) {
685 if (id_equal(dht->friends_list[i].client_list[j].client_id, client_id)
686 && !is_timeout(temp_time, dht->friends_list[i].client_list[j].timestamp, BAD_NODE_TIMEOUT))
687 return dht->friends_list[i].client_list[j].ip_port;
688 }
689
690 return empty;
691 }
692 }
693
694 empty.ip.i = 1;
695 return empty;
696}
697
698/* Ping each client in the "friends" list every PING_INTERVAL seconds. Send a get nodes request
699 * every GET_NODE_INTERVAL seconds to a random good node for each "friend" in our "friends" list.
700 */
701static void do_DHT_friends(DHT *dht)
702{
703 uint32_t i, j;
704 uint64_t temp_time = unix_time();
705 uint32_t rand_node;
706 uint32_t index[MAX_FRIEND_CLIENTS];
707
708 for (i = 0; i < dht->num_friends; ++i) {
709 uint32_t num_nodes = 0;
710
711 for (j = 0; j < MAX_FRIEND_CLIENTS; ++j) {
712 /* if node is not dead. */
713 if (!is_timeout(temp_time, dht->friends_list[i].client_list[j].timestamp, Kill_NODE_TIMEOUT)) {
714 if ((dht->friends_list[i].client_list[j].last_pinged + PING_INTERVAL) <= temp_time) {
715 send_ping_request(dht->ping, dht->c, dht->friends_list[i].client_list[j].ip_port,
716 (clientid_t *) &dht->friends_list[i].client_list[j].client_id );
717 dht->friends_list[i].client_list[j].last_pinged = temp_time;
718 }
719
720 /* if node is good. */
721 if (!is_timeout(temp_time, dht->friends_list[i].client_list[j].timestamp, BAD_NODE_TIMEOUT)) {
722 index[num_nodes] = j;
723 ++num_nodes;
724 }
725 }
726 }
727
728 if (dht->friends_list[i].lastgetnode + GET_NODE_INTERVAL <= temp_time && num_nodes != 0) {
729 rand_node = rand() % num_nodes;
730 getnodes(dht, dht->friends_list[i].client_list[index[rand_node]].ip_port,
731 dht->friends_list[i].client_list[index[rand_node]].client_id,
732 dht->friends_list[i].client_id );
733 dht->friends_list[i].lastgetnode = temp_time;
734 }
735 }
736}
737
738/* Ping each client in the close nodes list every PING_INTERVAL seconds.
739 * Send a get nodes request every GET_NODE_INTERVAL seconds to a random good node in the list.
740 */
741static void do_Close(DHT *dht)
742{
743 uint32_t i;
744 uint64_t temp_time = unix_time();
745 uint32_t num_nodes = 0;
746 uint32_t rand_node;
747 uint32_t index[LCLIENT_LIST];
748
749 for (i = 0; i < LCLIENT_LIST; ++i) {
750 /* if node is not dead. */
751 if (!is_timeout(temp_time, dht->close_clientlist[i].timestamp, Kill_NODE_TIMEOUT)) {
752 if ((dht->close_clientlist[i].last_pinged + PING_INTERVAL) <= temp_time) {
753 send_ping_request(dht->ping, dht->c, dht->close_clientlist[i].ip_port,
754 (clientid_t *) &dht->close_clientlist[i].client_id );
755 dht->close_clientlist[i].last_pinged = temp_time;
756 }
757
758 /* if node is good. */
759 if (!is_timeout(temp_time, dht->close_clientlist[i].timestamp, BAD_NODE_TIMEOUT)) {
760 index[num_nodes] = i;
761 ++num_nodes;
762 }
763 }
764 }
765
766 if (dht->close_lastgetnodes + GET_NODE_INTERVAL <= temp_time && num_nodes != 0) {
767 rand_node = rand() % num_nodes;
768 getnodes(dht, dht->close_clientlist[index[rand_node]].ip_port,
769 dht->close_clientlist[index[rand_node]].client_id,
770 dht->c->self_public_key );
771 dht->close_lastgetnodes = temp_time;
772 }
773}
774
775void DHT_bootstrap(DHT *dht, IP_Port ip_port, uint8_t *public_key)
776{
777 getnodes(dht, ip_port, public_key, dht->c->self_public_key);
778 send_ping_request(dht->ping, dht->c, ip_port, (clientid_t *) public_key);
779}
780
781/* send the given packet to node with client_id
782 * returns -1 if failure
783 */
784int route_packet(DHT *dht, uint8_t *client_id, uint8_t *packet, uint32_t length)
785{
786 uint32_t i;
787
788 for (i = 0; i < LCLIENT_LIST; ++i) {
789 if (id_equal(client_id, dht->close_clientlist[i].client_id))
790 return sendpacket(dht->c->lossless_udp->net->sock, dht->close_clientlist[i].ip_port, packet, length);
791 }
792
793 return -1;
794}
795
796/* Puts all the different ips returned by the nodes for a friend_num into array ip_portlist
797 * ip_portlist must be at least MAX_FRIEND_CLIENTS big
798 * returns the number of ips returned
799 * return 0 if we are connected to friend or if no ips were found.
800 * returns -1 if no such friend
801 */
802static int friend_iplist(DHT *dht, IP_Port *ip_portlist, uint16_t friend_num)
803{
804 int num_ips = 0;
805 uint32_t i;
806 uint64_t temp_time = unix_time();
807
808 if (friend_num >= dht->num_friends)
809 return -1;
810
811 DHT_Friend *friend = &dht->friends_list[friend_num];
812 Client_data *client;
813
814 for (i = 0; i < MAX_FRIEND_CLIENTS; ++i) {
815 client = &friend->client_list[i];
816
817 /*If ip is not zero and node is good */
818 if (client->ret_ip_port.ip.i != 0 && !is_timeout(temp_time, client->ret_timestamp, BAD_NODE_TIMEOUT)) {
819
820 if (id_equal(client->client_id, friend->client_id))
821 return 0;
822
823 ip_portlist[num_ips] = client->ret_ip_port;
824 ++num_ips;
825 }
826 }
827
828 return num_ips;
829}
830
831
832/* Send the following packet to everyone who tells us they are connected to friend_id
833 * returns the number of nodes it sent the packet to
834 *
835 * Only works if more than (MAX_FRIEND_CLIENTS / 2) return an ip for friend.
836 */
837int route_tofriend(DHT *dht, uint8_t *friend_id, uint8_t *packet, uint32_t length)
838{
839 int num = friend_number(dht, friend_id);
840
841 if (num == -1)
842 return 0;
843
844 uint32_t i, sent = 0;
845
846 IP_Port ip_list[MAX_FRIEND_CLIENTS];
847 int ip_num = friend_iplist(dht, ip_list, num);
848
849 if (ip_num < (MAX_FRIEND_CLIENTS / 2))
850 return 0;
851
852 uint64_t temp_time = unix_time();
853 DHT_Friend *friend = &dht->friends_list[num];
854 Client_data *client;
855
856 for (i = 0; i < MAX_FRIEND_CLIENTS; ++i) {
857 client = &friend->client_list[i];
858
859 /*If ip is not zero and node is good */
860 if (client->ret_ip_port.ip.i != 0 && !is_timeout(temp_time, client->ret_timestamp, BAD_NODE_TIMEOUT)) {
861 if (sendpacket(dht->c->lossless_udp->net->sock, client->ip_port, packet, length) == length)
862 ++sent;
863 }
864 }
865
866 return sent;
867}
868
869/* Send the following packet to one random person who tells us they are connected to friend_id
870* returns the number of nodes it sent the packet to
871*/
872static int routeone_tofriend(DHT *dht, uint8_t *friend_id, uint8_t *packet, uint32_t length)
873{
874 int num = friend_number(dht, friend_id);
875
876 if (num == -1)
877 return 0;
878
879 DHT_Friend *friend = &dht->friends_list[num];
880 Client_data *client;
881
882 IP_Port ip_list[MAX_FRIEND_CLIENTS];
883 int n = 0;
884 uint32_t i;
885 uint64_t temp_time = unix_time();
886
887 for (i = 0; i < MAX_FRIEND_CLIENTS; ++i) {
888 client = &friend->client_list[i];
889
890 /*If ip is not zero and node is good */
891 if (client->ret_ip_port.ip.i != 0 && !is_timeout(temp_time, client->ret_timestamp, BAD_NODE_TIMEOUT)) {
892 ip_list[n] = client->ip_port;
893 ++n;
894 }
895 }
896
897 if (n < 1)
898 return 0;
899
900 if (sendpacket(dht->c->lossless_udp->net->sock, ip_list[rand() % n], packet, length) == length)
901 return 1;
902
903 return 0;
904}
905
906/* Puts all the different ips returned by the nodes for a friend_id into array ip_portlist
907 * ip_portlist must be at least MAX_FRIEND_CLIENTS big
908 * returns the number of ips returned
909 * return 0 if we are connected to friend or if no ips were found.
910 * returns -1 if no such friend
911 */
912int friend_ips(DHT *dht, IP_Port *ip_portlist, uint8_t *friend_id)
913{
914 uint32_t i;
915
916 for (i = 0; i < dht->num_friends; ++i) {
917 /* Equal */
918 if (id_equal(dht->friends_list[i].client_id, friend_id))
919 return friend_iplist(dht, ip_portlist, i);
920 }
921
922 return -1;
923}
924
925/*----------------------------------------------------------------------------------*/
926/*---------------------BEGINNING OF NAT PUNCHING FUNCTIONS--------------------------*/
927
928static int send_NATping(DHT *dht, uint8_t *public_key, uint64_t ping_id, uint8_t type)
929{
930 uint8_t data[sizeof(uint64_t) + 1];
931 uint8_t packet[MAX_DATA_SIZE];
932
933 int num = 0;
934
935 data[0] = type;
936 memcpy(data + 1, &ping_id, sizeof(uint64_t));
937 /* 254 is NAT ping request packet id */
938 int len = create_request(dht->c->self_public_key, dht->c->self_secret_key, packet, public_key, data,
939 sizeof(uint64_t) + 1, CRYPTO_PACKET_NAT_PING);
940
941 if (len == -1)
942 return -1;
943
944 if (type == 0) /*If packet is request use many people to route it*/
945 num = route_tofriend(dht, public_key, packet, len);
946 else if (type == 1) /*If packet is response use only one person to route it*/
947 num = routeone_tofriend(dht, public_key, packet, len);
948
949 if (num == 0)
950 return -1;
951
952 return num;
953}
954
955/* Handle a received ping request for */
956static int handle_NATping(void *object, IP_Port source, uint8_t *source_pubkey, uint8_t *packet, uint32_t length)
957{
958 DHT *dht = object;
959 uint64_t ping_id;
960 memcpy(&ping_id, packet + 1, sizeof(uint64_t));
961
962 int friendnumber = friend_number(dht, source_pubkey);
963
964 if (friendnumber == -1)
965 return 1;
966
967 DHT_Friend *friend = &dht->friends_list[friendnumber];
968
969 if (packet[0] == NAT_PING_REQUEST) {
970 /* 1 is reply */
971 send_NATping(dht, source_pubkey, ping_id, NAT_PING_RESPONSE);
972 friend->recvNATping_timestamp = unix_time();
973 return 0;
974 } else if (packet[0] == NAT_PING_RESPONSE) {
975 if (friend->NATping_id == ping_id) {
976 friend->NATping_id = ((uint64_t)random_int() << 32) + random_int();
977 friend->hole_punching = 1;
978 return 0;
979 }
980 }
981
982 return 1;
983}
984
985/* Get the most common ip in the ip_portlist
986 * Only return ip if it appears in list min_num or more
987 * len must not be bigger than MAX_FRIEND_CLIENTS
988 * return ip of 0 if failure
989 */
990static IP NAT_commonip(IP_Port *ip_portlist, uint16_t len, uint16_t min_num)
991{
992 IP zero = {{0}};
993
994 if (len > MAX_FRIEND_CLIENTS)
995 return zero;
996
997 uint32_t i, j;
998 uint16_t numbers[MAX_FRIEND_CLIENTS] = {0};
999
1000 for (i = 0; i < len; ++i) {
1001 for (j = 0; j < len; ++j) {
1002 if (ip_portlist[i].ip.i == ip_portlist[j].ip.i)
1003 ++numbers[i];
1004 }
1005
1006 if (numbers[i] >= min_num)
1007 return ip_portlist[i].ip;
1008 }
1009
1010 return zero;
1011}
1012
1013/* Return all the ports for one ip in a list
1014 * portlist must be at least len long
1015 * where len is the length of ip_portlist
1016 * returns the number of ports and puts the list of ports in portlist
1017 */
1018static uint16_t NAT_getports(uint16_t *portlist, IP_Port *ip_portlist, uint16_t len, IP ip)
1019{
1020 uint32_t i;
1021 uint16_t num = 0;
1022
1023 for (i = 0; i < len; ++i) {
1024 if (ip_portlist[i].ip.i == ip.i) {
1025 portlist[num] = ntohs(ip_portlist[i].port);
1026 ++num;
1027 }
1028 }
1029
1030 return num;
1031}
1032
1033static void punch_holes(DHT *dht, IP ip, uint16_t *port_list, uint16_t numports, uint16_t friend_num)
1034{
1035 if (numports > MAX_FRIEND_CLIENTS || numports == 0)
1036 return;
1037
1038 uint32_t i;
1039 uint32_t top = dht->friends_list[friend_num].punching_index + MAX_PUNCHING_PORTS;
1040
1041 for (i = dht->friends_list[friend_num].punching_index; i != top; i++) {
1042 /*TODO: improve port guessing algorithm*/
1043 uint16_t port = port_list[(i / 2) % numports] + (i / (2 * numports)) * ((i % 2) ? -1 : 1);
1044 IP_Port pinging = {ip, htons(port)};
1045 send_ping_request(dht->ping, dht->c, pinging, (clientid_t *) &dht->friends_list[friend_num].client_id);
1046 }
1047
1048 dht->friends_list[friend_num].punching_index = i;
1049}
1050
1051static void do_NAT(DHT *dht)
1052{
1053 uint32_t i;
1054 uint64_t temp_time = unix_time();
1055
1056 for (i = 0; i < dht->num_friends; ++i) {
1057 IP_Port ip_list[MAX_FRIEND_CLIENTS];
1058 int num = friend_iplist(dht, ip_list, i);
1059
1060 /*If already connected or friend is not online don't try to hole punch*/
1061 if (num < MAX_FRIEND_CLIENTS / 2)
1062 continue;
1063
1064 if (dht->friends_list[i].NATping_timestamp + PUNCH_INTERVAL < temp_time) {
1065 send_NATping(dht, dht->friends_list[i].client_id, dht->friends_list[i].NATping_id, NAT_PING_REQUEST);
1066 dht->friends_list[i].NATping_timestamp = temp_time;
1067 }
1068
1069 if (dht->friends_list[i].hole_punching == 1 &&
1070 dht->friends_list[i].punching_timestamp + PUNCH_INTERVAL < temp_time &&
1071 dht->friends_list[i].recvNATping_timestamp + PUNCH_INTERVAL * 2 >= temp_time) {
1072
1073 IP ip = NAT_commonip(ip_list, num, MAX_FRIEND_CLIENTS / 2);
1074
1075 if (ip.i == 0)
1076 continue;
1077
1078 uint16_t port_list[MAX_FRIEND_CLIENTS];
1079 uint16_t numports = NAT_getports(port_list, ip_list, num, ip);
1080 punch_holes(dht, ip, port_list, numports, i);
1081
1082 dht->friends_list[i].punching_timestamp = temp_time;
1083 dht->friends_list[i].hole_punching = 0;
1084 }
1085 }
1086}
1087
1088/*----------------------------------------------------------------------------------*/
1089/*-----------------------END OF NAT PUNCHING FUNCTIONS------------------------------*/
1090
1091
1092/* Add nodes to the toping list
1093 all nodes in this list are pinged every TIME_TOPING seconds
1094 and are then removed from the list.
1095 if the list is full the nodes farthest from our client_id are replaced
1096 the purpose of this list is to enable quick integration of new nodes into the
1097 network while preventing amplification attacks.
1098 return 0 if node was added
1099 return -1 if node was not added */
1100int add_toping(DHT *dht, uint8_t *client_id, IP_Port ip_port)
1101{
1102 if (ip_port.ip.i == 0)
1103 return -1;
1104
1105 uint32_t i;
1106
1107 for (i = 0; i < MAX_TOPING; ++i) {
1108 if (dht->toping[i].ip_port.ip.i == 0) {
1109 memcpy(dht->toping[i].client_id, client_id, CLIENT_ID_SIZE);
1110 dht->toping[i].ip_port.ip.i = ip_port.ip.i;
1111 dht->toping[i].ip_port.port = ip_port.port;
1112 return 0;
1113 }
1114 }
1115
1116 for (i = 0; i < MAX_TOPING; ++i) {
1117 if (id_closest(dht->c->self_public_key, dht->toping[i].client_id, client_id) == 2) {
1118 memcpy(dht->toping[i].client_id, client_id, CLIENT_ID_SIZE);
1119 dht->toping[i].ip_port.ip.i = ip_port.ip.i;
1120 dht->toping[i].ip_port.port = ip_port.port;
1121 return 0;
1122 }
1123 }
1124
1125 return -1;
1126}
1127
1128/*Ping all the valid nodes in the toping list every TIME_TOPING seconds
1129 this function must be run at least once every TIME_TOPING seconds*/
1130static void do_toping(DHT *dht)
1131{
1132 uint64_t temp_time = unix_time();
1133
1134 if (!is_timeout(temp_time, dht->last_toping, TIME_TOPING))
1135 return;
1136
1137 dht->last_toping = temp_time;
1138 uint32_t i;
1139
1140 for (i = 0; i < MAX_TOPING; ++i) {
1141 if (dht->toping[i].ip_port.ip.i == 0)
1142 return;
1143
1144 send_ping_request(dht->ping, dht->c, dht->toping[i].ip_port, (clientid_t *) dht->toping[i].client_id);
1145 dht->toping[i].ip_port.ip.i = 0;
1146 }
1147}
1148
1149
1150DHT *new_DHT(Net_Crypto *c)
1151{
1152 if (c == NULL)
1153 return NULL;
1154
1155 DHT *temp = calloc(1, sizeof(DHT));
1156
1157 if (temp == NULL)
1158 return NULL;
1159
1160 temp->ping = new_ping();
1161
1162 if (temp->ping == NULL) {
1163 kill_DHT(temp);
1164 return NULL;
1165 }
1166
1167 temp->c = c;
1168 networking_registerhandler(c->lossless_udp->net, NET_PACKET_PING_REQUEST, &handle_ping_request, temp);
1169 networking_registerhandler(c->lossless_udp->net, NET_PACKET_PING_RESPONSE, &handle_ping_response, temp);
1170 networking_registerhandler(c->lossless_udp->net, NET_PACKET_GET_NODES, &handle_getnodes, temp);
1171 networking_registerhandler(c->lossless_udp->net, NET_PACKET_SEND_NODES, &handle_sendnodes, temp);
1172 init_cryptopackets(temp);
1173 cryptopacket_registerhandler(c, CRYPTO_PACKET_NAT_PING, &handle_NATping, temp);
1174 return temp;
1175}
1176
1177void do_DHT(DHT *dht)
1178{
1179 do_Close(dht);
1180 do_DHT_friends(dht);
1181 do_NAT(dht);
1182 do_toping(dht);
1183}
1184void kill_DHT(DHT *dht)
1185{
1186 kill_ping(dht->ping);
1187 free(dht->friends_list);
1188 free(dht);
1189}
1190
1191/* get the size of the DHT (for saving) */
1192uint32_t DHT_size(DHT *dht)
1193{
1194 return sizeof(dht->close_clientlist) + sizeof(DHT_Friend) * dht->num_friends;
1195}
1196
1197/* save the DHT in data where data is an array of size DHT_size() */
1198void DHT_save(DHT *dht, uint8_t *data)
1199{
1200 memcpy(data, dht->close_clientlist, sizeof(dht->close_clientlist));
1201 memcpy(data + sizeof(dht->close_clientlist), dht->friends_list, sizeof(DHT_Friend) * dht->num_friends);
1202}
1203
1204/* load the DHT from data of size size;
1205 * return -1 if failure
1206 * return 0 if success
1207 */
1208int DHT_load(DHT *dht, uint8_t *data, uint32_t size)
1209{
1210 if (size < sizeof(dht->close_clientlist))
1211 return -1;
1212
1213 if ((size - sizeof(dht->close_clientlist)) % sizeof(DHT_Friend) != 0)
1214 return -1;
1215
1216 uint32_t i, j;
1217 uint16_t temp;
1218 /* uint64_t temp_time = unix_time(); */
1219
1220 Client_data *client;
1221
1222 temp = (size - sizeof(dht->close_clientlist)) / sizeof(DHT_Friend);
1223
1224 if (temp != 0) {
1225 DHT_Friend *tempfriends_list = (DHT_Friend *)(data + sizeof(dht->close_clientlist));
1226
1227 for (i = 0; i < temp; ++i) {
1228 DHT_addfriend(dht, tempfriends_list[i].client_id);
1229
1230 for (j = 0; j < MAX_FRIEND_CLIENTS; ++j) {
1231 client = &tempfriends_list[i].client_list[j];
1232
1233 if (client->timestamp != 0)
1234 getnodes(dht, client->ip_port, client->client_id, tempfriends_list[i].client_id);
1235 }
1236 }
1237 }
1238
1239 Client_data *tempclose_clientlist = (Client_data *)data;
1240
1241 for (i = 0; i < LCLIENT_LIST; ++i) {
1242 if (tempclose_clientlist[i].timestamp != 0)
1243 DHT_bootstrap(dht, tempclose_clientlist[i].ip_port,
1244 tempclose_clientlist[i].client_id );
1245 }
1246
1247 return 0;
1248}
1249
1250/* returns 0 if we are not connected to the DHT
1251 * returns 1 if we are
1252 */
1253int DHT_isconnected(DHT *dht)
1254{
1255 uint32_t i;
1256 uint64_t temp_time = unix_time();
1257
1258 for (i = 0; i < LCLIENT_LIST; ++i) {
1259 if (!is_timeout(temp_time, dht->close_clientlist[i].timestamp, BAD_NODE_TIMEOUT))
1260 return 1;
1261 }
1262
1263 return 0;
1264}
generated by cgit v1.2.3 (git 2.39.1) at 2024-10-31 22:32:29 +0000