summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--auto_tests/Makefile.inc11
-rw-r--r--auto_tests/assoc_test.c93
-rw-r--r--toxcore/DHT.c134
-rw-r--r--toxcore/DHT.h33
-rw-r--r--toxcore/Makefile.inc2
-rw-r--r--toxcore/Messenger.c17
-rw-r--r--toxcore/assoc.c886
-rw-r--r--toxcore/assoc.h87
-rw-r--r--toxcore/group_chats.c37
-rw-r--r--toxcore/group_chats.h8
-rw-r--r--toxcore/network.h2
-rw-r--r--toxcore/ping.c32
-rw-r--r--toxcore/ping.h4
13 files changed, 1286 insertions, 60 deletions
diff --git a/auto_tests/Makefile.inc b/auto_tests/Makefile.inc
index 9c06bc78..1831fc50 100644
--- a/auto_tests/Makefile.inc
+++ b/auto_tests/Makefile.inc
@@ -1,8 +1,8 @@
1if BUILD_TESTS 1if BUILD_TESTS
2 2
3TESTS = messenger_autotest crypto_test network_test 3TESTS = messenger_autotest crypto_test network_test assoc_test
4 4
5check_PROGRAMS = messenger_autotest crypto_test network_test 5check_PROGRAMS = messenger_autotest crypto_test network_test assoc_test
6 6
7AUTOTEST_CFLAGS = \ 7AUTOTEST_CFLAGS = \
8 $(LIBSODIUM_CFLAGS) \ 8 $(LIBSODIUM_CFLAGS) \
@@ -38,6 +38,13 @@ network_test_CFLAGS = $(AUTOTEST_CFLAGS)
38network_test_LDADD = $(AUTOTEST_LDADD) 38network_test_LDADD = $(AUTOTEST_LDADD)
39 39
40 40
41assoc_test_SOURCES = ../auto_tests/assoc_test.c
42
43assoc_test_CFLAGS = $(AUTOTEST_CFLAGS)
44
45assoc_test_LDADD = $(AUTOTEST_LDADD)
46
47
41endif 48endif
42 49
43EXTRA_DIST += $(top_srcdir)/auto_tests/friends_test.c 50EXTRA_DIST += $(top_srcdir)/auto_tests/friends_test.c
diff --git a/auto_tests/assoc_test.c b/auto_tests/assoc_test.c
new file mode 100644
index 00000000..79a0e778
--- /dev/null
+++ b/auto_tests/assoc_test.c
@@ -0,0 +1,93 @@
1
2#ifdef HAVE_CONFIG_H
3#include "config.h"
4#endif
5
6#define AUTO_TEST
7#include "../toxcore/DHT.h"
8#include "../toxcore/assoc.h"
9#include "../toxcore/util.h"
10
11#include <sys/types.h>
12#include <stdint.h>
13#include <string.h>
14
15#include <check.h>
16
17START_TEST(test_basics)
18{
19 /* TODO: real test */
20 uint8_t id[CLIENT_ID_SIZE];
21 Assoc *assoc = new_Assoc_default(id);
22 ck_assert_msg(assoc != NULL, "failed to create default assoc");
23
24 kill_Assoc(assoc);
25 assoc = new_Assoc(17, 4, id); /* results in an assoc of 16/3 */
26 ck_assert_msg(assoc != NULL, "failed to create customized assoc");
27
28 IP_Port ipp;
29 ipp.ip.family = AF_INET;
30 ipp.ip.ip4.uint8[0] = 1;
31 ipp.port = htons(12345);
32
33 IPPTs ippts_send;
34 ippts_send.ip_port = ipp;
35 ippts_send.timestamp = unix_time();
36 IP_Port ipp_recv = ipp;
37
38 uint8_t res = Assoc_add_entry(assoc, id, &ippts_send, &ipp_recv, 0);
39 ck_assert_msg(res == 0, "stored self as entry: expected %u, got %u", 0, res);
40
41 id[0]++;
42
43 res = Assoc_add_entry(assoc, id, &ippts_send, &ipp_recv, 0);
44 ck_assert_msg(res == 1, "failed to store entry: expected %u, got %u", 1, res);
45
46 Assoc_close_entries close_entries;
47 memset(&close_entries, 0, sizeof(close_entries));
48 close_entries.count = 4;
49 close_entries.count_good = 2;
50 close_entries.wanted_id = id;
51
52 Client_data *entries[close_entries.count];
53 close_entries.result = entries;
54
55 uint8_t found = Assoc_get_close_entries(assoc, &close_entries);
56 ck_assert_msg(found == 1, "get_close_entries(): expected %u, got %u", 1, found);
57}
58END_TEST
59
60
61#define DEFTESTCASE(NAME) \
62 TCase *tc_##NAME = tcase_create(#NAME); \
63 tcase_add_test(tc_##NAME, test_##NAME); \
64 suite_add_tcase(s, tc_##NAME);
65
66#define DEFTESTCASE_SLOW(NAME, TIMEOUT) \
67 DEFTESTCASE(NAME) \
68 tcase_set_timeout(tc_##NAME, TIMEOUT);
69
70Suite *Assoc_suite(void)
71{
72 Suite *s = suite_create("Assoc");
73
74 DEFTESTCASE(basics);
75
76 return s;
77}
78
79int main(int argc, char *argv[])
80{
81 Suite *Assoc = Assoc_suite();
82 SRunner *test_runner = srunner_create(Assoc);
83
84 srunner_set_fork_status(test_runner, CK_NOFORK);
85
86 srunner_run_all(test_runner, CK_NORMAL);
87
88 int number_failed = srunner_ntests_failed(test_runner);
89
90 srunner_free(test_runner);
91
92 return number_failed;
93}
diff --git a/toxcore/DHT.c b/toxcore/DHT.c
index 4076826a..f49858bc 100644
--- a/toxcore/DHT.c
+++ b/toxcore/DHT.c
@@ -28,27 +28,20 @@
28#endif 28#endif
29 29
30#include "DHT.h" 30#include "DHT.h"
31#include "network.h" 31#include "assoc.h"
32#include "ping.h" 32#include "ping.h"
33
34#include "network.h"
35#include "LAN_discovery.h"
33#include "misc_tools.h" 36#include "misc_tools.h"
34#include "util.h" 37#include "util.h"
35#include "LAN_discovery.h"
36
37/* The number of seconds for a non responsive node to become bad. */
38#define BAD_NODE_TIMEOUT 70
39 38
40/* The max number of nodes to send with send nodes. */ 39/* The max number of nodes to send with send nodes. */
41#define MAX_SENT_NODES 8 40#define MAX_SENT_NODES 8
42 41
43/* Ping timeout in seconds */
44#define PING_TIMEOUT 5
45
46/* The timeout after which a node is discarded completely. */ 42/* The timeout after which a node is discarded completely. */
47#define KILL_NODE_TIMEOUT 300 43#define KILL_NODE_TIMEOUT 300
48 44
49/* Ping interval in seconds for each node in our lists. */
50#define PING_INTERVAL 60
51
52/* Ping interval in seconds for each random sending of a get nodes request. */ 45/* Ping interval in seconds for each random sending of a get nodes request. */
53#define GET_NODE_INTERVAL 5 46#define GET_NODE_INTERVAL 5
54 47
@@ -427,7 +420,9 @@ static void sort_list(Client_data *list, uint32_t length, uint8_t *comp_client_i
427 list[i] = pairs[i].c2; 420 list[i] = pairs[i].c2;
428} 421}
429 422
430/* Replace the first good node that is further to the comp_client_id than that of the client_id in the list */ 423/* Replace the first good node that is further to the comp_client_id than that of the client_id in the list
424 *
425 * returns 0 when the item was stored, 1 otherwise */
431static int replace_good( Client_data *list, 426static int replace_good( Client_data *list,
432 uint32_t length, 427 uint32_t length,
433 uint8_t *client_id, 428 uint8_t *client_id,
@@ -488,10 +483,12 @@ static int replace_good( Client_data *list,
488 483
489/* Attempt to add client with ip_port and client_id to the friends client list 484/* Attempt to add client with ip_port and client_id to the friends client list
490 * and close_clientlist. 485 * and close_clientlist.
486 *
487 * returns 1+ if the item is used in any list, 0 else
491 */ 488 */
492void addto_lists(DHT *dht, IP_Port ip_port, uint8_t *client_id) 489int addto_lists(DHT *dht, IP_Port ip_port, uint8_t *client_id)
493{ 490{
494 uint32_t i; 491 uint32_t i, used = 0;
495 492
496 /* convert IPv4-in-IPv6 to IPv4 */ 493 /* convert IPv4-in-IPv6 to IPv4 */
497 if ((ip_port.ip.family == AF_INET6) && IN6_IS_ADDR_V4MAPPED(&ip_port.ip.ip6.in6_addr)) { 494 if ((ip_port.ip.family == AF_INET6) && IN6_IS_ADDR_V4MAPPED(&ip_port.ip.ip6.in6_addr)) {
@@ -505,10 +502,13 @@ void addto_lists(DHT *dht, IP_Port ip_port, uint8_t *client_id)
505 if (!client_or_ip_port_in_list(dht->close_clientlist, LCLIENT_LIST, client_id, ip_port)) { 502 if (!client_or_ip_port_in_list(dht->close_clientlist, LCLIENT_LIST, client_id, ip_port)) {
506 if (replace_bad(dht->close_clientlist, LCLIENT_LIST, client_id, ip_port)) { 503 if (replace_bad(dht->close_clientlist, LCLIENT_LIST, client_id, ip_port)) {
507 /* If we can't replace bad nodes we try replacing good ones. */ 504 /* If we can't replace bad nodes we try replacing good ones. */
508 replace_good(dht->close_clientlist, LCLIENT_LIST, client_id, ip_port, 505 if (!replace_good(dht->close_clientlist, LCLIENT_LIST, client_id, ip_port,
509 dht->c->self_public_key); 506 dht->c->self_public_key))
510 } 507 used++;
511 } 508 } else
509 used++;
510 } else
511 used++;
512 512
513 for (i = 0; i < dht->num_friends; ++i) { 513 for (i = 0; i < dht->num_friends; ++i) {
514 if (!client_or_ip_port_in_list(dht->friends_list[i].client_list, 514 if (!client_or_ip_port_in_list(dht->friends_list[i].client_list,
@@ -517,17 +517,22 @@ void addto_lists(DHT *dht, IP_Port ip_port, uint8_t *client_id)
517 if (replace_bad(dht->friends_list[i].client_list, MAX_FRIEND_CLIENTS, 517 if (replace_bad(dht->friends_list[i].client_list, MAX_FRIEND_CLIENTS,
518 client_id, ip_port)) { 518 client_id, ip_port)) {
519 /* If we can't replace bad nodes we try replacing good ones. */ 519 /* If we can't replace bad nodes we try replacing good ones. */
520 replace_good(dht->friends_list[i].client_list, MAX_FRIEND_CLIENTS, 520 if (!replace_good(dht->friends_list[i].client_list, MAX_FRIEND_CLIENTS,
521 client_id, ip_port, dht->friends_list[i].client_id); 521 client_id, ip_port, dht->friends_list[i].client_id))
522 } 522 used++;
523 } 523 } else
524 used++;
525 } else
526 used++;
524 } 527 }
528
529 return used;
525} 530}
526 531
527/* If client_id is a friend or us, update ret_ip_port 532/* If client_id is a friend or us, update ret_ip_port
528 * nodeclient_id is the id of the node that sent us this info. 533 * nodeclient_id is the id of the node that sent us this info.
529 */ 534 */
530static void returnedip_ports(DHT *dht, IP_Port ip_port, uint8_t *client_id, uint8_t *nodeclient_id) 535static int returnedip_ports(DHT *dht, IP_Port ip_port, uint8_t *client_id, uint8_t *nodeclient_id)
531{ 536{
532 uint32_t i, j; 537 uint32_t i, j;
533 uint64_t temp_time = unix_time(); 538 uint64_t temp_time = unix_time();
@@ -549,10 +554,9 @@ static void returnedip_ports(DHT *dht, IP_Port ip_port, uint8_t *client_id, uint
549 dht->close_clientlist[i].assoc6.ret_timestamp = temp_time; 554 dht->close_clientlist[i].assoc6.ret_timestamp = temp_time;
550 } 555 }
551 556
552 return; 557 return 1;
553 } 558 }
554 } 559 }
555
556 } else { 560 } else {
557 for (i = 0; i < dht->num_friends; ++i) { 561 for (i = 0; i < dht->num_friends; ++i) {
558 if (id_equal(client_id, dht->friends_list[i].client_id)) { 562 if (id_equal(client_id, dht->friends_list[i].client_id)) {
@@ -566,13 +570,14 @@ static void returnedip_ports(DHT *dht, IP_Port ip_port, uint8_t *client_id, uint
566 dht->friends_list[i].client_list[j].assoc6.ret_timestamp = temp_time; 570 dht->friends_list[i].client_list[j].assoc6.ret_timestamp = temp_time;
567 } 571 }
568 572
569 return; 573 return 1;
570 } 574 }
571 } 575 }
572 } 576 }
573 } 577 }
574
575 } 578 }
579
580 return 0;
576} 581}
577 582
578/* checks if ip/port or ping_id are already in the list to get nodes 583/* checks if ip/port or ping_id are already in the list to get nodes
@@ -851,7 +856,16 @@ static int handle_sendnodes_core(void *object, IP_Port source, uint8_t *packet,
851 return 1; 856 return 1;
852 857
853 /* store the address the *request* was sent to */ 858 /* store the address the *request* was sent to */
854 addto_lists(dht, dht->send_nodes[send_nodes_index - 1].ip_port, packet + 1); 859 int used = addto_lists(dht, dht->send_nodes[send_nodes_index - 1].ip_port, packet + 1);
860
861 if (dht->assoc) {
862 IPPTs ippts;
863
864 ippts.ip_port = dht->send_nodes[send_nodes_index - 1].ip_port;
865 ippts.timestamp = dht->send_nodes[send_nodes_index - 1].timestamp;
866
867 Assoc_add_entry(dht->assoc, packet + 1, &ippts, &source, used ? 1 : 0);
868 }
855 869
856 *num_nodes_out = num_nodes; 870 *num_nodes_out = num_nodes;
857 871
@@ -881,7 +895,15 @@ static int handle_sendnodes(void *object, IP_Port source, uint8_t *packet, uint3
881 ipp.port = nodes4_list[i].ip_port.port; 895 ipp.port = nodes4_list[i].ip_port.port;
882 896
883 send_ping_request(dht->ping, ipp, nodes4_list[i].client_id); 897 send_ping_request(dht->ping, ipp, nodes4_list[i].client_id);
884 returnedip_ports(dht, ipp, nodes4_list[i].client_id, packet + 1); 898 int used = returnedip_ports(dht, ipp, nodes4_list[i].client_id, packet + 1);
899
900 if (dht->assoc) {
901 IPPTs ippts;
902 ippts.ip_port = ipp;
903 ippts.timestamp = 0;
904
905 Assoc_add_entry(dht->assoc, nodes4_list[i].client_id, &ippts, NULL, used ? 1 : 0);
906 }
885 } 907 }
886 908
887 return 0; 909 return 0;
@@ -904,7 +926,15 @@ static int handle_sendnodes_ipv6(void *object, IP_Port source, uint8_t *packet,
904 for (i = 0; i < num_nodes; i++) 926 for (i = 0; i < num_nodes; i++)
905 if (ipport_isset(&nodes_list[i].ip_port)) { 927 if (ipport_isset(&nodes_list[i].ip_port)) {
906 send_ping_request(dht->ping, nodes_list[i].ip_port, nodes_list[i].client_id); 928 send_ping_request(dht->ping, nodes_list[i].ip_port, nodes_list[i].client_id);
907 returnedip_ports(dht, nodes_list[i].ip_port, nodes_list[i].client_id, packet + 1); 929 int used = returnedip_ports(dht, nodes_list[i].ip_port, nodes_list[i].client_id, packet + 1);
930
931 if (dht->assoc) {
932 IPPTs ippts;
933 ippts.ip_port = nodes_list[i].ip_port;
934 ippts.timestamp = 0;
935
936 Assoc_add_entry(dht->assoc, nodes_list[i].client_id, &ippts, NULL, used ? 1 : 0);
937 }
908 } 938 }
909 939
910 return 0; 940 return 0;
@@ -953,7 +983,38 @@ int DHT_addfriend(DHT *dht, uint8_t *client_id)
953 983
954 dht->friends_list[dht->num_friends].nat.NATping_id = ((uint64_t)random_int() << 32) + random_int(); 984 dht->friends_list[dht->num_friends].nat.NATping_id = ((uint64_t)random_int() << 32) + random_int();
955 ++dht->num_friends; 985 ++dht->num_friends;
956 get_bunchnodes(dht, dht->close_clientlist, LCLIENT_LIST, MAX_FRIEND_CLIENTS, client_id);/*TODO: make this better?*/ 986
987 if (dht->assoc) {
988 /* get up to MAX_FRIEND_CLIENTS connectable nodes */
989 DHT_Friend *friend = &dht->friends_list[dht->num_friends - 1];
990
991 Assoc_close_entries close_entries;
992 memset(&close_entries, 0, sizeof(close_entries));
993 close_entries.wanted_id = client_id;
994 close_entries.count_good = MAX_FRIEND_CLIENTS / 2;
995 close_entries.count = MAX_FRIEND_CLIENTS;
996 close_entries.result = calloc(MAX_FRIEND_CLIENTS, sizeof(*close_entries.result));
997
998 uint8_t i, found = Assoc_get_close_entries(dht->assoc, &close_entries);
999
1000 for (i = 0; i < found; i++)
1001 memcpy(&friend->client_list[i], close_entries.result[i], sizeof(*close_entries.result[i]));
1002
1003 if (found) {
1004 /* send getnodes to the "best" entry */
1005 Client_data *client = &friend->client_list[0];
1006
1007 if (ipport_isset(&client->assoc4.ip_port))
1008 getnodes(dht, client->assoc4.ip_port, client->client_id, friend->client_id);
1009
1010 if (ipport_isset(&client->assoc6.ip_port))
1011 getnodes(dht, client->assoc6.ip_port, client->client_id, friend->client_id);
1012 }
1013 }
1014
1015 /*TODO: make this better?*/
1016 get_bunchnodes(dht, dht->close_clientlist, LCLIENT_LIST, MAX_FRIEND_CLIENTS, client_id);
1017
957 return 0; 1018 return 0;
958} 1019}
959 1020
@@ -1114,6 +1175,14 @@ static void do_Close(DHT *dht)
1114 1175
1115void DHT_bootstrap(DHT *dht, IP_Port ip_port, uint8_t *public_key) 1176void DHT_bootstrap(DHT *dht, IP_Port ip_port, uint8_t *public_key)
1116{ 1177{
1178 if (dht->assoc) {
1179 IPPTs ippts;
1180 ippts.ip_port = ip_port;
1181 ippts.timestamp = 0;
1182
1183 Assoc_add_entry(dht->assoc, public_key, &ippts, NULL, 0);
1184 }
1185
1117 getnodes(dht, ip_port, public_key, dht->c->self_public_key); 1186 getnodes(dht, ip_port, public_key, dht->c->self_public_key);
1118} 1187}
1119int DHT_bootstrap_from_address(DHT *dht, const char *address, uint8_t ipv6enabled, 1188int DHT_bootstrap_from_address(DHT *dht, const char *address, uint8_t ipv6enabled,
@@ -1585,6 +1654,8 @@ DHT *new_DHT(Net_Crypto *c)
1585 init_cryptopackets(dht); 1654 init_cryptopackets(dht);
1586 cryptopacket_registerhandler(c, CRYPTO_PACKET_NAT_PING, &handle_NATping, dht); 1655 cryptopacket_registerhandler(c, CRYPTO_PACKET_NAT_PING, &handle_NATping, dht);
1587 1656
1657 dht->assoc = new_Assoc_default(dht->c->self_public_key);
1658
1588 return dht; 1659 return dht;
1589} 1660}
1590 1661
@@ -1599,6 +1670,7 @@ void do_DHT(DHT *dht)
1599} 1670}
1600void kill_DHT(DHT *dht) 1671void kill_DHT(DHT *dht)
1601{ 1672{
1673 kill_Assoc(dht->assoc);
1602 kill_ping(dht->ping); 1674 kill_ping(dht->ping);
1603 free(dht->friends_list); 1675 free(dht->friends_list);
1604 free(dht); 1676 free(dht);
diff --git a/toxcore/DHT.h b/toxcore/DHT.h
index 360773ff..2f6334ee 100644
--- a/toxcore/DHT.h
+++ b/toxcore/DHT.h
@@ -43,6 +43,22 @@
43/* Maximum newly announced nodes to ping per TIME_TOPING seconds. */ 43/* Maximum newly announced nodes to ping per TIME_TOPING seconds. */
44#define MAX_TOPING 16 44#define MAX_TOPING 16
45 45
46/* Ping timeout in seconds */
47#define PING_TIMEOUT 5
48
49/* Ping interval in seconds for each node in our lists. */
50#define PING_INTERVAL 60
51
52/* The number of seconds for a non responsive node to become bad. */
53#define PINGS_MISSED_NODE_GOES_BAD 3
54#define PING_ROUNDTRIP 2
55#define BAD_NODE_TIMEOUT (PING_INTERVAL + PINGS_MISSED_NODE_GOES_BAD * PING_INTERVAL + PING_ROUNDTRIP)
56
57typedef struct {
58 IP_Port ip_port;
59 uint64_t timestamp;
60} IPPTs;
61
46typedef struct { 62typedef struct {
47 IP_Port ip_port; 63 IP_Port ip_port;
48 uint64_t timestamp; 64 uint64_t timestamp;
@@ -117,22 +133,25 @@ typedef struct {
117 uint64_t timestamp; 133 uint64_t timestamp;
118} pinged_t; 134} pinged_t;
119 135
136typedef struct PING PING;
137typedef struct Assoc Assoc;
138
120typedef struct { 139typedef struct {
121 Net_Crypto *c; 140 Net_Crypto *c;
122 141
123 Client_data close_clientlist[LCLIENT_LIST]; 142 Client_data close_clientlist[LCLIENT_LIST];
143 uint64_t close_lastgetnodes;
144
124 DHT_Friend *friends_list; 145 DHT_Friend *friends_list;
125 uint16_t num_friends; 146 uint16_t num_friends;
126 uint64_t close_lastgetnodes;
127 147
128 pinged_t send_nodes[LSEND_NODES_ARRAY]; 148 pinged_t send_nodes[LSEND_NODES_ARRAY];
129 void *ping; 149 PING *ping;
150
151 Assoc *assoc;
130} DHT; 152} DHT;
131/*----------------------------------------------------------------------------------*/ 153/*----------------------------------------------------------------------------------*/
132 154
133
134Client_data *DHT_get_close_list(DHT *dht);
135
136/* Add a new friend to the friends list. 155/* Add a new friend to the friends list.
137 * client_id must be CLIENT_ID_SIZE bytes long. 156 * client_id must be CLIENT_ID_SIZE bytes long.
138 * 157 *
@@ -254,7 +273,7 @@ int DHT_load_new(DHT *dht, uint8_t *data, uint32_t size);
254 */ 273 */
255int DHT_isconnected(DHT *dht); 274int DHT_isconnected(DHT *dht);
256 275
257void addto_lists(DHT *dht, IP_Port ip_port, uint8_t *client_id); 276int addto_lists(DHT *dht, IP_Port ip_port, uint8_t *client_id);
258
259 277
260#endif 278#endif
279
diff --git a/toxcore/Makefile.inc b/toxcore/Makefile.inc
index 116a3e29..8208c548 100644
--- a/toxcore/Makefile.inc
+++ b/toxcore/Makefile.inc
@@ -27,6 +27,8 @@ libtoxcore_la_SOURCES = ../toxcore/DHT.h \
27 ../toxcore/util.c \ 27 ../toxcore/util.c \
28 ../toxcore/group_chats.h \ 28 ../toxcore/group_chats.h \
29 ../toxcore/group_chats.c \ 29 ../toxcore/group_chats.c \
30 ../toxcore/assoc.h \
31 ../toxcore/assoc.c \
30 ../toxcore/misc_tools.h 32 ../toxcore/misc_tools.h
31 33
32libtoxcore_la_CFLAGS = -I$(top_srcdir) \ 34libtoxcore_la_CFLAGS = -I$(top_srcdir) \
diff --git a/toxcore/Messenger.c b/toxcore/Messenger.c
index c2971a70..19bd7edf 100644
--- a/toxcore/Messenger.c
+++ b/toxcore/Messenger.c
@@ -26,9 +26,11 @@
26#endif 26#endif
27 27
28#include "Messenger.h" 28#include "Messenger.h"
29#include "assoc.h"
29#include "network.h" 30#include "network.h"
30#include "util.h" 31#include "util.h"
31 32
33
32#define MIN(a,b) (((a)<(b))?(a):(b)) 34#define MIN(a,b) (((a)<(b))?(a):(b))
33 35
34 36
@@ -1820,6 +1822,18 @@ void do_messenger(Messenger *m)
1820 1822
1821 if (unix_time() > lastdump + DUMPING_CLIENTS_FRIENDS_EVERY_N_SECONDS) { 1823 if (unix_time() > lastdump + DUMPING_CLIENTS_FRIENDS_EVERY_N_SECONDS) {
1822 loglog(" = = = = = = = = \n"); 1824 loglog(" = = = = = = = = \n");
1825 Assoc_status(m->dht->assoc);
1826
1827 if (m->numchats > 0) {
1828 size_t c;
1829
1830 for (c = 0; c < m->numchats; c++) {
1831 loglog("---------------- \n");
1832 Assoc_status(m->chats[c]->assoc);
1833 }
1834 }
1835
1836 loglog(" = = = = = = = = \n");
1823 1837
1824 lastdump = unix_time(); 1838 lastdump = unix_time();
1825 uint32_t client, last_pinged; 1839 uint32_t client, last_pinged;
@@ -2007,6 +2021,9 @@ static int messenger_load_state_callback(void *outer, uint8_t *data, uint32_t le
2007 if (length == crypto_box_PUBLICKEYBYTES + crypto_box_SECRETKEYBYTES + sizeof(uint32_t)) { 2021 if (length == crypto_box_PUBLICKEYBYTES + crypto_box_SECRETKEYBYTES + sizeof(uint32_t)) {
2008 set_nospam(&(m->fr), *(uint32_t *)data); 2022 set_nospam(&(m->fr), *(uint32_t *)data);
2009 load_keys(m->net_crypto, &data[sizeof(uint32_t)]); 2023 load_keys(m->net_crypto, &data[sizeof(uint32_t)]);
2024
2025 if (m->dht->assoc)
2026 Assoc_self_client_id_changed(m->dht->assoc, m->net_crypto->self_public_key);
2010 } else 2027 } else
2011 return -1; /* critical */ 2028 return -1; /* critical */
2012 2029
diff --git a/toxcore/assoc.c b/toxcore/assoc.c
new file mode 100644
index 00000000..fa44d0e3
--- /dev/null
+++ b/toxcore/assoc.c
@@ -0,0 +1,886 @@
1
2#include "DHT.h"
3#include "assoc.h"
4#include "ping.h"
5
6#include "LAN_discovery.h"
7
8#include <assert.h>
9#include "util.h"
10
11/*
12 * BASIC OVERVIEW:
13 *
14 * Hash: The client_id is hashed with a local hash function.
15 * Hashes are used in multiple places for searching.
16 * Bucket: The first n bits of the client_id are used to
17 * select a bucket. This speeds up sorting, but the more
18 * important reason is to enforce a spread in the space of
19 * client_ids available.
20 *
21 *
22 * Candidates:
23 *
24 * Candidates are kept in buckets of hash tables. The hash
25 * function is calculated from the client_id. Up to
26 * HASH_COLLIDE_COUNT alternative positions are tried if
27 * the inital position is already used by a different entry.
28 * The collision function is multiplicative, not additive.
29 *
30 * A new candidate can bump an existing candidate, if it is
31 * more "desirable": Seen beats Heard.
32 */
33
34/* candidates: alternative places for the same hash value */
35#define HASH_COLLIDE_COUNT 5
36
37/* bucket size shall be co-prime to this */
38#define HASH_COLLIDE_PRIME 101
39
40/* candidates: bump entries: timeout values for seen/heard to be considered of value */
41#define CANDIDATES_SEEN_TIMEOUT 1800
42#define CANDIDATES_HEARD_TIMEOUT 600
43
44/* distance/index: index size & access mask */
45#define DISTANCE_INDEX_INDEX_BITS (64 - DISTANCE_INDEX_DISTANCE_BITS)
46#define DISTANCE_INDEX_INDEX_MASK ((1 << DISTANCE_INDEX_INDEX_BITS) - 1)
47
48/* types to stay consistent */
49typedef uint16_t bucket_t;
50typedef uint32_t hash_t;
51typedef uint16_t usecnt_t;
52
53/* abbreviations ... */
54typedef Assoc_distance_relative_callback dist_rel_cb;
55typedef Assoc_distance_absolute_callback dist_abs_cb;
56
57/*
58 * Client_data wrapped with additional data
59 */
60typedef struct Client_entry {
61 hash_t hash;
62
63 /* shortcuts & rumors: timers and data */
64 uint64_t used_at;
65 uint64_t seen_at;
66 uint64_t heard_at;
67
68 uint16_t seen_family;
69 uint16_t heard_family;
70
71 IP_Port assoc_heard4;
72 IP_Port assoc_heard6;
73
74 Client_data client;
75} Client_entry;
76
77typedef struct candidates_bucket {
78 Client_entry *list; /* hashed list */
79} candidates_bucket;
80typedef struct Assoc {
81 hash_t self_hash; /* hash of self_client_id */
82 uint8_t self_client_id[CLIENT_ID_SIZE]; /* don't store entries for this */
83
84 /* association centralization: clients not in use */
85 size_t candidates_bucket_bits;
86 size_t candidates_bucket_count;
87 size_t candidates_bucket_size;
88 candidates_bucket *candidates;
89} Assoc;
90
91/*****************************************************************************/
92/* HELPER FUNCTIONS */
93/*****************************************************************************/
94
95/* the complete distance would be CLIENT_ID_SIZE long...
96 * returns DISTANCE_INDEX_DISTANCE_BITS valid bits */
97static uint64_t id_distance(Assoc *assoc, void *callback_data, uint8_t *id_ref, uint8_t *id_test)
98{
99 /* with BIG_ENDIAN, this would be a one-liner... */
100 uint64_t retval = 0;
101
102 uint8_t pos = 0, bits = DISTANCE_INDEX_DISTANCE_BITS;
103
104 while (bits > 8) {
105 uint8_t distance = abs((int8_t)id_ref[pos] ^ (int8_t)id_test[pos]);
106 retval = (retval << 8) | distance;
107 bits -= 8;
108 pos++;
109 }
110
111 return (retval << bits) | ((id_ref[pos] ^ id_test[pos]) >> (8 - bits));
112}
113
114/* qsort() callback for a sorting by id_distance() values */
115static int dist_index_comp(const void *a, const void *b)
116{
117 const uint64_t *_a = a;
118 const uint64_t *_b = b;
119
120 if (*_a < *_b)
121 return -1;
122
123 if (*_a > *_b)
124 return 1;
125
126 return 0;
127}
128
129/* get actual entry to a distance_index */
130static Client_entry *dist_index_entry(Assoc *assoc, uint64_t dist_ind)
131{
132 if ((dist_ind & DISTANCE_INDEX_INDEX_MASK) == DISTANCE_INDEX_INDEX_MASK)
133 return NULL;
134
135 size_t total = assoc->candidates_bucket_count * assoc->candidates_bucket_size;
136 uint32_t index = dist_ind & DISTANCE_INDEX_INDEX_MASK;
137
138 if (index < total) {
139 bucket_t b_id = index / assoc->candidates_bucket_size;
140 candidates_bucket *cnd_bckt = &assoc->candidates[b_id];
141 size_t b_ix = index % assoc->candidates_bucket_size;
142 Client_entry *entry = &cnd_bckt->list[b_ix];
143
144 if (entry->hash)
145 return entry;
146 }
147
148 return NULL;
149}
150
151/* get actual entry's client_id to a distance_index */
152static uint8_t *dist_index_id(Assoc *assoc, uint64_t dist_ind)
153{
154 Client_entry *entry = dist_index_entry(assoc, dist_ind);
155
156 if (entry)
157 return entry->client.client_id;
158
159 return NULL;
160}
161
162/* sorts first .. last, i.e. last is included */
163static void dist_index_bubble(Assoc *assoc, uint64_t *dist_list, size_t first, size_t last, uint8_t *id,
164 void *custom_data, Assoc_distance_relative_callback dist_rel_func)
165{
166 size_t i, k;
167
168 for (i = first; i <= last; i++) {
169 uint8_t *id1 = dist_index_id(assoc, dist_list[i]);
170
171 for (k = i + 1; k <= last; k++) {
172 uint8_t *id2 = dist_index_id(assoc, dist_list[k]);
173
174 if (id1 && id2)
175 if (dist_rel_func(assoc, custom_data, id, id1, id2) == 2) {
176 uint64_t swap = dist_list[i];
177 dist_list[i] = dist_list[k];
178 dist_list[k] = swap;
179 }
180 }
181 }
182}
183
184/* TODO: Check that there isn't a function like this elsewhere hidden.
185 * E.g. the one which creates a handshake_id isn't usable for this, it must
186 * always map the same ID to the same hash.
187 *
188 * Result is NOT MAPPED to CANDIDATES_TO_KEEP range, i.e. map before using
189 * it for list access. */
190static hash_t id_hash(Assoc *assoc, uint8_t *id)
191{
192 uint32_t i, res = 0x19a64e82;
193
194 for (i = 0; i < CLIENT_ID_SIZE; i++)
195 res = ((res << 1) ^ id[i]) + (res >> 31);
196
197 /* can't have zero as hash, a) marks an unused spot,
198 * b) collision function is multiplicative */
199 if (!(res % assoc->candidates_bucket_size))
200 res++;
201
202 return res;
203}
204
205/* up to HASH_COLLIDE_COUNT calls to different spots,
206 * result IS mapped to CANDIDATES_TO_KEEP range */
207static hash_t hash_collide(Assoc *assoc, hash_t hash)
208{
209 uint64_t hash64 = hash % assoc->candidates_bucket_size;
210 hash64 = (hash64 * HASH_COLLIDE_PRIME) % assoc->candidates_bucket_size;
211
212 hash_t retval = hash64;
213
214 /* this should never happen when CANDIDATES_TO_KEEP is prime and hash not a multiple
215 * (id_hash() checks for a multiple and returns a different hash in that case)
216 *
217 * ( 1 .. (prime - 1) is a group over multiplication and every number has its inverse
218 * in the group, so no multiplication should ever end on zero as long neither
219 * of the two factors was zero-equivalent )
220 *
221 * BUT: because the usage of the word "never" invokes Murphy's law, catch it */
222 if (!retval) {
223#ifdef DEBUG
224 fprintf(stderr, "assoc::hash_collide: hash %u, bucket size %u => %u!", hash, (uint)assoc->candidates_bucket_size,
225 retval);
226 assert(retval != 0);
227#endif
228 retval = 1;
229 }
230
231 return retval;
232}
233
234/* returns the "seen" assoc related to the ipp */
235static IPPTsPng *entry_assoc(Client_entry *cl_entry, IP_Port *ipp)
236{
237 if (!cl_entry)
238 return NULL;
239
240 if (ipp->ip.family == AF_INET)
241 return &cl_entry->client.assoc4;
242
243 if (ipp->ip.family == AF_INET6)
244 return &cl_entry->client.assoc6;
245
246 return NULL;
247}
248
249/* returns the "heard" assoc related to the ipp */
250static IP_Port *entry_heard_get(Client_entry *entry, IP_Port *ipp)
251{
252 if (ipp->ip.family == AF_INET)
253 return &entry->assoc_heard4;
254 else if (ipp->ip.family == AF_INET6)
255 return &entry->assoc_heard6;
256 else
257 return NULL;
258}
259
260/* store a "heard" entry
261 * overwrites empty entry, does NOT overwrite non-LAN ip with
262 * LAN ip
263 *
264 * returns 1 if the entry did change */
265static int entry_heard_store(Client_entry *entry, IPPTs *ippts)
266{
267 if (!entry || !ippts)
268 return 0;
269
270 if (!ipport_isset(&ippts->ip_port))
271 return 0;
272
273 IP_Port *heard, *ipp = &ippts->ip_port;
274
275 if (ipp->ip.family == AF_INET)
276 heard = &entry->assoc_heard4;
277 else if (ipp->ip.family == AF_INET6)
278 heard = &entry->assoc_heard6;
279 else
280 return 0;
281
282 if (ipport_equal(ipp, heard))
283 return 0;
284
285 if (!ipport_isset(heard)) {
286 *heard = *ipp;
287 entry->heard_at = ippts->timestamp;
288 entry->heard_family = ipp->ip.family;
289 return 1;
290 }
291
292 /* don't destroy a good address with a crappy one
293 * (unless we're very timed out) */
294 uint8_t LAN_ipp = LAN_ip(ipp->ip) == 0;
295 uint8_t LAN_entry = LAN_ip(heard->ip) == 0;
296
297 if (LAN_ipp && !LAN_entry && !is_timeout(entry->heard_at, CANDIDATES_HEARD_TIMEOUT))
298 return 0;
299
300 *heard = *ipp;
301 entry->heard_at = ippts->timestamp;
302 entry->heard_family = ipp->ip.family;
303
304 return 1;
305}
306
307/* maps Assoc callback signature to id_closest() */
308static int assoc_id_closest(Assoc *assoc, void *callback_data, uint8_t *client_id, uint8_t *client_id1,
309 uint8_t *client_id2)
310{
311 return id_closest(client_id, client_id1, client_id2);
312}
313
314static bucket_t id_bucket(uint8_t *id, uint8_t bits)
315{
316 /* return the first "bits" bits of id */
317 bucket_t retval = 0;
318
319 uint8_t pos = 0;
320
321 while (bits > 8) {
322 retval = (retval << 8) | id[pos++];
323 bits -= 8;
324 }
325
326 return (retval << bits) | (id[pos] >> (8 - bits));
327}
328
329/*****************************************************************************/
330/* CANDIDATES FUNCTIONS */
331/*****************************************************************************/
332
333
334static bucket_t candidates_id_bucket(Assoc *assoc, uint8_t *id)
335{
336 return id_bucket(id, assoc->candidates_bucket_bits);
337}
338
339static uint8_t candidates_search(Assoc *assoc, uint8_t *id, hash_t hash, Client_entry **entryptr)
340{
341 bucket_t bucket = candidates_id_bucket(assoc, id);
342 candidates_bucket *cnd_bckt = &assoc->candidates[bucket];
343 size_t coll, pos = hash % assoc->candidates_bucket_size;
344
345 for (coll = 0; coll < HASH_COLLIDE_COUNT; pos = hash_collide(assoc, pos) , coll++) {
346 Client_entry *entry = &cnd_bckt->list[pos];
347
348 if (entry->hash == hash)
349 if (id_equal(entry->client.client_id, id)) {
350 *entryptr = entry;
351 return 1;
352 }
353 }
354
355 *entryptr = NULL;
356 return 0;
357}
358
359static void candidates_update_assoc(Assoc *assoc, Client_entry *entry, uint8_t used, IPPTs *ippts_send,
360 IP_Port *ipp_recv)
361{
362 if (!assoc || !entry || !ippts_send)
363 return;
364
365 IPPTsPng *ipptsp = entry_assoc(entry, &ippts_send->ip_port);
366
367 if (!ipptsp)
368 return;
369
370 if (used)
371 entry->used_at = unix_time();
372
373 /* do NOT do anything related to wanted, that's handled outside,
374 * just update the assoc (in the most sensible way)
375 */
376 if (ipp_recv) {
377 ipptsp->ip_port = ippts_send->ip_port;
378 ipptsp->timestamp = ippts_send->timestamp;
379 ipptsp->ret_ip_port = *ipp_recv;
380 ipptsp->ret_timestamp = unix_time();
381
382 entry->seen_at = unix_time();
383 entry->seen_family = ippts_send->ip_port.ip.family;
384
385 return;
386 }
387
388 entry_heard_store(entry, ippts_send);
389}
390
391static uint8_t candidates_create_internal(Assoc *assoc, hash_t hash, uint8_t *id, uint8_t seen,
392 uint8_t used, bucket_t *bucketptr, size_t *posptr)
393{
394 if (!assoc || !id || !bucketptr || !posptr)
395 return 0;
396
397 bucket_t bucket = candidates_id_bucket(assoc, id);
398 candidates_bucket *cnd_bckt = &assoc->candidates[bucket];
399
400 size_t coll, pos = hash % assoc->candidates_bucket_size, check;
401 size_t pos_check[6];
402
403 memset(pos_check, 0, sizeof(pos_check));
404
405 for (coll = 0; coll < HASH_COLLIDE_COUNT; pos = hash_collide(assoc, pos) , coll++) {
406 Client_entry *entry = &cnd_bckt->list[pos];
407
408 /* unset */
409 if (!entry->hash) {
410 *bucketptr = bucket;
411 *posptr = pos;
412
413 return 1;
414 }
415
416 /* 0. bad
417 * 1. seen bad, heard good
418 * 2. seen good
419 * 3. used */
420 if (!is_timeout(entry->used_at, BAD_NODE_TIMEOUT))
421 check = 3;
422
423 if (!is_timeout(entry->seen_at, CANDIDATES_SEEN_TIMEOUT))
424 check = 2;
425 else if (!is_timeout(entry->heard_at, CANDIDATES_HEARD_TIMEOUT))
426 check = 1;
427 else
428 check = 0;
429
430 if (!pos_check[check])
431 pos_check[check] = pos + 1;
432 }
433
434 /* used > seen > heard > bad */
435 size_t i, pos_max = used ? 3 : (seen ? 2 : 1);
436
437 for (i = 0; i < pos_max; i++)
438 if (pos_check[i]) {
439 *bucketptr = bucket;
440 *posptr = pos_check[i] - 1;
441
442 return 1;
443 }
444
445 return 0;
446}
447
448static uint8_t candidates_create_new(Assoc *assoc, hash_t hash, uint8_t *id, uint8_t used,
449 IPPTs *ippts_send, IP_Port *ipp_recv)
450{
451 if (!assoc || !id || !ippts_send)
452 return 0;
453
454 bucket_t bucket;
455 size_t pos;
456
457 if (!candidates_create_internal(assoc, hash, id, ipp_recv != NULL, used, &bucket, &pos))
458 return 0;
459
460 candidates_bucket *cnd_bckt = &assoc->candidates[bucket];
461 Client_entry *entry = &cnd_bckt->list[pos];
462 memset(entry, 0, sizeof(*entry));
463 IPPTsPng *ipptsp = entry_assoc(entry, &ippts_send->ip_port);
464
465 if (!ipptsp)
466 return 0;
467
468 entry->hash = hash;
469 id_copy(entry->client.client_id, id);
470
471 if (used)
472 entry->used_at = unix_time();
473
474 if (ipp_recv && !ipport_isset(ipp_recv))
475 ipp_recv = NULL;
476
477 if (ipp_recv) {
478 entry->seen_at = unix_time();
479 entry->seen_family = ippts_send->ip_port.ip.family;
480
481 ipptsp->ip_port = ippts_send->ip_port;
482 ipptsp->timestamp = ippts_send->timestamp;
483 ipptsp->ret_ip_port = *ipp_recv;
484 ipptsp->ret_timestamp = unix_time();
485 } else {
486 IP_Port *heard = entry_heard_get(entry, &ippts_send->ip_port);
487
488 if (heard) {
489 entry->heard_at = ippts_send->timestamp;
490 entry->heard_family = ippts_send->ip_port.ip.family;
491
492 *heard = ippts_send->ip_port;
493 }
494 }
495
496 return 1;
497}
498
499/*****************************************************************************/
500
501static void client_id_self_update(Assoc *assoc)
502{
503 if (assoc->self_hash || !assoc->self_client_id)
504 return;
505
506 if (!assoc->self_hash) {
507 size_t i, sum = 0;
508
509 for (i = 0; i < crypto_box_PUBLICKEYBYTES; i++)
510 sum |= assoc->self_client_id[i];
511
512 if (!sum)
513 return;
514
515 assoc->self_hash = id_hash(assoc, assoc->self_client_id);
516 }
517
518#ifdef LOGGING
519 loglog("assoc: id is now set, purging cache of self-references...\n");
520#endif
521
522 /* if we already added some (or loaded some) entries,
523 * look and remove if we find a match
524 */
525 bucket_t b_id = candidates_id_bucket(assoc, assoc->self_client_id);
526 candidates_bucket *cnd_bckt = &assoc->candidates[b_id];
527 size_t i, pos = assoc->self_hash % assoc->candidates_bucket_size;
528
529 for (i = 0; i < HASH_COLLIDE_COUNT; pos = hash_collide(assoc, pos), i++) {
530 Client_entry *entry = &cnd_bckt->list[pos];
531
532 if (entry->hash == assoc->self_hash)
533 if (id_equal(entry->client.client_id, assoc->self_client_id))
534 entry->hash = 0;
535 }
536}
537
538/*****************************************************************************/
539/* TRIGGER FUNCTIONS */
540/*****************************************************************************/
541
542/* Central entry point for new associations: add a new candidate to the cache
543 * seen should be 0 (zero), if the candidate was announced by someone else,
544 * seen should be 1 (one), if there is confirmed connectivity (a definite response)
545 */
546uint8_t Assoc_add_entry(Assoc *assoc, uint8_t *id, IPPTs *ippts_send, IP_Port *ipp_recv, uint8_t used)
547{
548 if (!assoc || !id || !ippts_send)
549 return 0;
550
551 if (!assoc->self_hash) {
552 client_id_self_update(assoc);
553
554 if (!assoc->self_hash)
555 return 0;
556 }
557
558 if (!ipport_isset(&ippts_send->ip_port))
559 return 0;
560
561 if (ipp_recv && !ipport_isset(ipp_recv))
562 ipp_recv = NULL;
563
564 hash_t hash = id_hash(assoc, id);
565
566 if (hash == assoc->self_hash)
567 if (id_equal(id, assoc->self_client_id))
568 return 0;
569
570 /* if it's new:
571 * callback, if there's desire, add to clients, else to candidates
572 *
573 * if it's "old":
574 * if it's client: refresh
575 * if it's candidate:
576 * if !ipp_recv, refresh
577 * if ipp_recv: callback, if there's desire, move to candidates
578 */
579 Client_entry *cnd_entry;
580
581 if (!candidates_search(assoc, id, hash, &cnd_entry)) {
582 if (candidates_create_new(assoc, hash, id, used, ippts_send, ipp_recv))
583 return 1;
584 else
585 return 0;
586 } else {
587 candidates_update_assoc(assoc, cnd_entry, used, ippts_send, ipp_recv);
588 return 2;
589 }
590}
591
592/*****************************************************************************/
593/* MAIN USE */
594/*****************************************************************************/
595
596uint8_t Assoc_get_close_entries(Assoc *assoc, Assoc_close_entries *state)
597{
598 if (!assoc || !state || !state->wanted_id || !state->result)
599 return 0;
600
601 if (!assoc->self_hash) {
602 client_id_self_update(assoc);
603
604 if (!assoc->self_hash)
605 return 0;
606 }
607
608 if (!state->distance_relative_func)
609 state->distance_relative_func = assoc_id_closest;
610
611 if (!state->distance_absolute_func)
612 state->distance_absolute_func = id_distance;
613
614 size_t dist_list_len = assoc->candidates_bucket_count * assoc->candidates_bucket_size;
615 uint64_t dist_list[dist_list_len];
616 memset(dist_list, ~0, dist_list_len * sizeof(dist_list[0]));
617 bucket_t b;
618 size_t i;
619
620 for (b = 0; b < assoc->candidates_bucket_count; b++) {
621 candidates_bucket *cnd_bckt = &assoc->candidates[b];
622
623 for (i = 0; i < assoc->candidates_bucket_size; i++) {
624 Client_entry *entry = &cnd_bckt->list[i];
625
626 if (entry->hash) {
627 uint64_t dist = state->distance_absolute_func(assoc, state->custom_data, state->wanted_id, entry->client.client_id);
628 uint32_t index = b * assoc->candidates_bucket_size + i;
629 dist_list[index] = (dist << DISTANCE_INDEX_INDEX_BITS) | index;
630 }
631 }
632 }
633
634 qsort(dist_list, dist_list_len, sizeof(dist_list[0]), dist_index_comp);
635
636 /* ok, ok, it's not *perfectly* sorted, because we used an absolute distance
637 * go over the result and see if we need to "smoothen things out"
638 * because those should be only very few and short streaks, the worst regularly
639 * used sorting function aka bubble sort is used */
640 uint64_t dist_prev = ~0;
641 size_t ind_prev = ~0, ind_curr;
642 size_t len = 1;
643
644 for (ind_curr = 0; ind_curr < dist_list_len; ind_curr++) {
645 /* sorted increasingly, so an invalid entry marks the end */
646 if ((dist_list[ind_curr] & DISTANCE_INDEX_INDEX_MASK) == DISTANCE_INDEX_INDEX_MASK)
647 break;
648
649 uint64_t dist_curr = dist_list[ind_curr] >> DISTANCE_INDEX_INDEX_BITS;
650
651 if (dist_prev == dist_curr)
652 len++;
653 else {
654 if (len > 1)
655 dist_index_bubble(assoc, dist_list, ind_prev, ind_curr - 1, state->wanted_id, state->custom_data,
656 state->distance_relative_func);
657
658 dist_prev = dist_curr;
659 ind_prev = ind_curr;
660 len = 1;
661 }
662 }
663
664 if (len > 1)
665 dist_index_bubble(assoc, dist_list, ind_prev, ind_curr - 1, state->wanted_id, state->custom_data,
666 state->distance_relative_func);
667
668 /* ok, now dist_list is a strictly ascending sorted list of nodes
669 * a) extract CLOSE_QUOTA_USED clients, not timed out
670 * b) extract (1 - QUOTA) (better!) clients & candidates, not timed out
671 * c) save candidates which would be better, if contact can be established */
672 size_t client_quota_good = 0, pos = 0;
673 size_t client_quota_max = state->count_good;
674
675 ssize_t taken_last = - 1;
676
677 for (i = 0; (i < dist_list_len) && (pos < state->count); i++) {
678 Client_entry *entry = dist_index_entry(assoc, dist_list[i]);
679
680 if (entry && entry->hash) {
681 if (client_quota_good >= client_quota_max) {
682 state->result[pos++] = &entry->client;
683 taken_last = i;
684 } else if (!is_timeout(entry->seen_at, BAD_NODE_TIMEOUT)) {
685 state->result[pos++] = &entry->client;
686 client_quota_good++;
687 taken_last = i;
688 }
689 }
690 }
691
692 /* if we had not enough valid entries the list might still not be filled.
693 *
694 * start again from last taken client, but leave out any requirement
695 */
696 if (pos < state->count) {
697 for (i = taken_last + 1; (i < dist_list_len) && (pos < state->count); i++) {
698 Client_entry *entry = dist_index_entry(assoc, dist_list[i]);
699
700 if (entry && entry->hash)
701 state->result[pos++] = &entry->client;
702 }
703 }
704
705 return pos;
706}
707
708/*****************************************************************************/
709/* GLOBAL STRUCTURE FUNCTIONS */
710/*****************************************************************************/
711
712static uint8_t odd_min9_is_prime(size_t value)
713{
714 size_t i = 3;
715
716 while (i * i <= value) {
717 if (!(value % i))
718 return 0;
719
720 i += 2;
721 }
722
723 return 1;
724}
725
726static size_t prime_upto_min9(size_t limit)
727{
728 /* primes besides 2 are odd */
729 if (!(limit % 2))
730 limit--;
731
732 while (!odd_min9_is_prime(limit))
733 limit -= 2;
734
735 return limit;
736}
737
738/* create */
739Assoc *new_Assoc(size_t bits, size_t entries, uint8_t *public_id)
740{
741 if (!public_id)
742 return NULL;
743
744 Assoc *assoc = calloc(1, sizeof(*assoc));
745
746 if (!assoc)
747 return NULL;
748
749 /*
750 * bits must be in [ 2 .. 15 ]
751 * entries must be a prime
752 */
753 if (bits < 2)
754 bits = 2;
755 else if (bits > 15)
756 bits = 15;
757
758 assoc->candidates_bucket_bits = bits;
759 assoc->candidates_bucket_count = 1U << bits;
760
761 if (entries <= 8) {
762 if (entries <= 4)
763 entries = 3;
764 else if (!(entries % 2)) /* 6, 8 => 5, 7 */
765 entries--;
766 } else if (entries > ((1 << 17) - 1)) /* 130k+ */
767 entries = (1 << 17) - 1;
768 else {
769 /* 9+: test and find a prime less or equal */
770 size_t entries_test = prime_upto_min9(entries);
771
772 if (entries_test == HASH_COLLIDE_PRIME) /* disallowed */
773 entries_test = prime_upto_min9(entries_test - 1);
774
775 if (entries_test != entries) {
776#ifdef LOGGING
777 sprintf(logbuffer, "new_Assoc(): trimmed %i to %i.\n", (int)entries, (int)entries_test);
778 loglog(logbuffer);
779#endif
780 entries = (size_t)entries_test;
781 }
782 }
783
784 assoc->candidates_bucket_size = entries;
785
786 /* allocation: preferably few blobs */
787 size_t bckt, cix;
788 Client_entry *clients = malloc(sizeof(*clients) * assoc->candidates_bucket_count * assoc->candidates_bucket_size);
789 candidates_bucket *lists = malloc(sizeof(*lists) * assoc->candidates_bucket_count);
790
791 for (bckt = 0; bckt < assoc->candidates_bucket_count; bckt++) {
792 candidates_bucket *list = &lists[bckt];
793
794 list->list = &clients[bckt * assoc->candidates_bucket_size];
795
796 for (cix = 0; cix < assoc->candidates_bucket_size; cix++)
797 list->list[cix].hash = 0;
798 }
799
800 assoc->candidates = lists;
801
802 id_copy(assoc->self_client_id, public_id);
803 client_id_self_update(assoc);
804
805 return assoc;
806}
807
808Assoc *new_Assoc_default(uint8_t *public_id)
809{
810 /* original 8, 251 averages to ~32k entries... probably the whole DHT :D
811 * 320 entries is fine, hopefully */
812 return new_Assoc(6, 5, public_id);
813}
814
815/* own client_id, assocs for this have to be ignored */
816void Assoc_self_client_id_changed(Assoc *assoc, uint8_t *id)
817{
818 if (assoc && id) {
819 assoc->self_hash = 0;
820 id_copy(assoc->self_client_id, id);
821 client_id_self_update(assoc);
822 }
823}
824
825/* destroy */
826void kill_Assoc(Assoc *assoc)
827{
828 if (assoc) {
829 free(assoc->candidates->list);
830 free(assoc->candidates);
831 free(assoc);
832 }
833}
834
835#ifdef LOGGING
836
837static char buffer[CLIENT_ID_SIZE * 2 + 1];
838static char *idpart2str(uint8_t *id, size_t len)
839{
840 if (len > CLIENT_ID_SIZE)
841 len = CLIENT_ID_SIZE;
842
843 size_t i;
844
845 for (i = 0; i < len; i++)
846 sprintf(buffer + i * 2, "%02hhx", id[i]);
847
848 buffer[len * 2] = 0;
849 return buffer;
850}
851
852void Assoc_status(Assoc *assoc)
853{
854 if (!assoc) {
855 loglog("Assoc status: no assoc\n");
856 return;
857 }
858
859 size_t bid, cid, total = 0;
860
861 for (bid = 0; bid < assoc->candidates_bucket_count; bid++) {
862 candidates_bucket *bucket = &assoc->candidates[bid];
863
864 for (cid = 0; cid < assoc->candidates_bucket_size; cid++) {
865 Client_entry *entry = &bucket->list[cid];
866
867 if (entry->hash) {
868 sprintf(logbuffer, "[%3i:%3i] %x => [%s...] %i, %i, %i\n",
869 (int)bid, (int)cid, entry->hash, idpart2str(entry->client.client_id, 8),
870 entry->used_at ? (int)(unix_time() - entry->used_at) : 0,
871 entry->seen_at ? (int)(unix_time() - entry->seen_at) : 0,
872 entry->heard_at ? (int)(unix_time() - entry->heard_at) : 0);
873 loglog(logbuffer);
874 total++;
875 }
876 }
877 }
878
879 if (total) {
880 sprintf(logbuffer, "Total: %i entries, table usage %i%%.\n", (int)total,
881 (int)(total * 100 / (assoc->candidates_bucket_count * assoc->candidates_bucket_size)));
882 loglog(logbuffer);
883 }
884}
885
886#endif
diff --git a/toxcore/assoc.h b/toxcore/assoc.h
new file mode 100644
index 00000000..ee9e5e21
--- /dev/null
+++ b/toxcore/assoc.h
@@ -0,0 +1,87 @@
1
2#ifndef __ASSOC_H__
3#define __ASSOC_H__
4
5/* used by rendezvous */
6#define ASSOC_AVAILABLE
7
8/* For the legalese parts, see tox.h. */
9
10/*
11 * Module to store currently unused ID <=> IP associations
12 * for a potential future use
13 */
14
15typedef struct IP_Port IP_Port;
16typedef struct Assoc Assoc;
17
18/*****************************************************************************/
19
20/* custom distance handler, if it's not ID-distance based
21 * return values exactly like id_closest() */
22typedef int (*Assoc_distance_relative_callback)(Assoc *assoc, void *callback_data, uint8_t *client_id,
23 uint8_t *client_id1, uint8_t *client_id2);
24
25#define DISTANCE_INDEX_DISTANCE_BITS 44
26
27/* absolute distance: can be same for different client_id_check values
28 * return value should have DISTANCE_INDEX_DISTANCE_BITS valid bits */
29typedef uint64_t (*Assoc_distance_absolute_callback)(Assoc *assoc, void *callback_data,
30 uint8_t *client_id_ref, uint8_t *client_id_check);
31
32/*****************************************************************************/
33
34/* Central entry point for new associations: add a new candidate to the cache
35 * returns 1 if entry is stored, 2 if existing entry was updated, 0 else */
36uint8_t Assoc_add_entry(Assoc *assoc, uint8_t *id, IPPTs *ippts_send, IP_Port *ipp_recv, uint8_t used);
37
38/*****************************************************************************/
39
40typedef struct Assoc_close_entries {
41 uint8_t *wanted_id; /* the target client_id */
42 void *custom_data; /* given to distance functions */
43
44 Assoc_distance_relative_callback distance_relative_func;
45 Assoc_distance_absolute_callback distance_absolute_func;
46
47 uint8_t count_good; /* that many should be "good" w.r.t. timeout */
48 uint8_t count; /* allocated number of close_indices */
49 Client_data **result;
50} Assoc_close_entries;
51
52/* find up to close_count nodes to put into close_nodes_used of ID_Nodes
53 * the distance functions can be NULL, then standard distance functions will be used
54 * the caller is responsible for allocating close_indices of sufficient size
55 *
56 * returns 0 on error
57 * returns the number of found nodes and the list of indices usable by Assoc_client()
58 * the caller is assumed to be registered from Assoc_register_callback()
59 * if they aren't, they should copy the Client_data and call Assoc_client_drop()
60 */
61uint8_t Assoc_get_close_entries(Assoc *assoc, Assoc_close_entries *close_entries);
62
63/*****************************************************************************/
64
65/* create: default sizes (6, 5 => 320 entries) */
66Assoc *new_Assoc_default(uint8_t *public_id);
67
68/* create: customized sizes
69 * total is (2^bits) * entries
70 * bits should be between 2 and 15 (else it's trimmed)
71 * entries will be reduced to the closest prime smaller or equal
72 *
73 * preferably bits should be large and entries small to ensure spread
74 * in the search space (e. g. 5, 5 is preferable to 2, 41) */
75Assoc *new_Assoc(size_t bits, size_t entries, uint8_t *public_id);
76
77/* public_id changed (loaded), update which entry isn't stored */
78void Assoc_self_client_id_changed(Assoc *assoc, uint8_t *public_id);
79
80/* destroy */
81void kill_Assoc(Assoc *assoc);
82
83#ifdef LOGGING
84void Assoc_status(Assoc *assoc);
85#endif
86
87#endif /* !__ASSOC_H__ */
diff --git a/toxcore/group_chats.c b/toxcore/group_chats.c
index 5a68bc1a..b5e421a6 100644
--- a/toxcore/group_chats.c
+++ b/toxcore/group_chats.c
@@ -27,6 +27,8 @@
27#endif 27#endif
28 28
29#include "group_chats.h" 29#include "group_chats.h"
30#include "assoc.h"
31#include "LAN_discovery.h"
30#include "util.h" 32#include "util.h"
31 33
32#define GROUPCHAT_MAXDATA_LENGTH (MAX_DATA_SIZE - (1 + crypto_box_PUBLICKEYBYTES * 2 + crypto_box_NONCEBYTES)) 34#define GROUPCHAT_MAXDATA_LENGTH (MAX_DATA_SIZE - (1 + crypto_box_PUBLICKEYBYTES * 2 + crypto_box_NONCEBYTES))
@@ -306,6 +308,15 @@ static int send_getnodes(Group_Chat *chat, IP_Port ip_port, int peernum)
306 308
307 chat->group[peernum].last_pinged = unix_time(); 309 chat->group[peernum].last_pinged = unix_time();
308 chat->group[peernum].pingid = contents.pingid; 310 chat->group[peernum].pingid = contents.pingid;
311 chat->group[peernum].ping_via = ip_port;
312
313 if (chat->assoc) {
314 IPPTs ippts;
315 ippts.timestamp = unix_time();
316 ippts.ip_port = ip_port;
317
318 Assoc_add_entry(chat->assoc, chat->group[peernum].client_id, &ippts, NULL, 1);
319 }
309 320
310 return send_groupchatpacket(chat, ip_port, chat->group[peernum].client_id, (uint8_t *)&contents, sizeof(contents), 321 return send_groupchatpacket(chat, ip_port, chat->group[peernum].client_id, (uint8_t *)&contents, sizeof(contents),
311 CRYPTO_PACKET_GROUP_CHAT_GET_NODES); 322 CRYPTO_PACKET_GROUP_CHAT_GET_NODES);
@@ -373,6 +384,9 @@ static int handle_sendnodes(Group_Chat *chat, IP_Port source, int peernum, uint8
373 uint16_t numnodes = (len - sizeof(contents.pingid)) / sizeof(groupchat_nodes); 384 uint16_t numnodes = (len - sizeof(contents.pingid)) / sizeof(groupchat_nodes);
374 uint32_t i; 385 uint32_t i;
375 386
387 IPPTs ippts_send;
388 ippts_send.timestamp = unix_time();
389
376 for (i = 0; i < numnodes; ++i) { 390 for (i = 0; i < numnodes; ++i) {
377 if (peer_okping(chat, contents.nodes[i].client_id) > 0) { 391 if (peer_okping(chat, contents.nodes[i].client_id) > 0) {
378 int peern = peer_in_chat(chat, contents.nodes[i].client_id); 392 int peern = peer_in_chat(chat, contents.nodes[i].client_id);
@@ -385,10 +399,26 @@ static int handle_sendnodes(Group_Chat *chat, IP_Port source, int peernum, uint8
385 continue; 399 continue;
386 400
387 send_getnodes(chat, contents.nodes[i].ip_port, peern); 401 send_getnodes(chat, contents.nodes[i].ip_port, peern);
402
403 if (chat->assoc) {
404 ippts_send.ip_port = contents.nodes[i].ip_port;
405 Assoc_add_entry(chat->assoc, contents.nodes[i].client_id, &ippts_send, NULL, 0);
406 }
388 } 407 }
389 } 408 }
390 409
391 add_closepeer(chat, chat->group[peernum].client_id, source); 410 int ok = add_closepeer(chat, chat->group[peernum].client_id, source);
411
412 if (chat->assoc) {
413 ippts_send.ip_port = chat->group[peernum].ping_via;
414 ippts_send.timestamp = chat->group[peernum].last_pinged;
415
416 IP_Port ipp_recv;
417 ipp_recv = source;
418
419 Assoc_add_entry(chat->assoc, contents.nodes[i].client_id, &ippts_send, &ipp_recv, ok == 0 ? 1 : 0);
420 }
421
392 return 0; 422 return 0;
393} 423}
394 424
@@ -585,6 +615,7 @@ void callback_groupmessage(Group_Chat *chat, void (*function)(Group_Chat *chat,
585 chat->group_message_userdata = userdata; 615 chat->group_message_userdata = userdata;
586} 616}
587 617
618
588Group_Chat *new_groupchat(Networking_Core *net) 619Group_Chat *new_groupchat(Networking_Core *net)
589{ 620{
590 unix_time_update(); 621 unix_time_update();
@@ -595,6 +626,10 @@ Group_Chat *new_groupchat(Networking_Core *net)
595 Group_Chat *chat = calloc(1, sizeof(Group_Chat)); 626 Group_Chat *chat = calloc(1, sizeof(Group_Chat));
596 chat->net = net; 627 chat->net = net;
597 crypto_box_keypair(chat->self_public_key, chat->self_secret_key); 628 crypto_box_keypair(chat->self_public_key, chat->self_secret_key);
629
630 /* (2^4) * 5 = 80 entries seems to be a moderate size */
631 chat->assoc = new_Assoc(4, 5, chat->self_public_key);
632
598 return chat; 633 return chat;
599} 634}
600 635
diff --git a/toxcore/group_chats.h b/toxcore/group_chats.h
index 74e2f2d7..16e4e722 100644
--- a/toxcore/group_chats.h
+++ b/toxcore/group_chats.h
@@ -27,12 +27,15 @@
27 27
28#include "net_crypto.h" 28#include "net_crypto.h"
29 29
30typedef struct Assoc Assoc;
31
30#define MAX_NICK_BYTES 128 32#define MAX_NICK_BYTES 128
31 33
32typedef struct { 34typedef struct {
33 uint8_t client_id[crypto_box_PUBLICKEYBYTES]; 35 uint8_t client_id[crypto_box_PUBLICKEYBYTES];
34 uint64_t pingid; 36 uint64_t pingid;
35 uint64_t last_pinged; 37 uint64_t last_pinged;
38 IP_Port ping_via;
36 39
37 uint64_t last_recv; 40 uint64_t last_recv;
38 uint64_t last_recv_msgping; 41 uint64_t last_recv_msgping;
@@ -46,7 +49,6 @@ typedef struct {
46 uint8_t client_id[crypto_box_PUBLICKEYBYTES]; 49 uint8_t client_id[crypto_box_PUBLICKEYBYTES];
47 IP_Port ip_port; 50 IP_Port ip_port;
48 uint64_t last_recv; 51 uint64_t last_recv;
49
50} Group_Close; 52} Group_Close;
51 53
52#define GROUP_CLOSE_CONNECTIONS 6 54#define GROUP_CLOSE_CONNECTIONS 6
@@ -69,6 +71,8 @@ typedef struct Group_Chat {
69 uint8_t nick[MAX_NICK_BYTES]; 71 uint8_t nick[MAX_NICK_BYTES];
70 uint16_t nick_len; 72 uint16_t nick_len;
71 uint64_t last_sent_nick; 73 uint64_t last_sent_nick;
74
75 Assoc *assoc;
72} Group_Chat; 76} Group_Chat;
73 77
74#define GROUP_CHAT_PING 0 78#define GROUP_CHAT_PING 0
@@ -102,7 +106,7 @@ uint32_t group_sendmessage(Group_Chat *chat, uint8_t *message, uint32_t length);
102 106
103/* 107/*
104 * Set our nick for this group. 108 * Set our nick for this group.
105 * 109 *
106 * returns -1 on failure, 0 on success. 110 * returns -1 on failure, 0 on success.
107 */ 111 */
108int set_nick(Group_Chat *chat, uint8_t *nick, uint16_t nick_len); 112int set_nick(Group_Chat *chat, uint8_t *nick, uint16_t nick_len);
diff --git a/toxcore/network.h b/toxcore/network.h
index 504a12af..d9bc2bfe 100644
--- a/toxcore/network.h
+++ b/toxcore/network.h
@@ -141,7 +141,7 @@ typedef union {
141 uint8_t uint8[8]; 141 uint8_t uint8[8];
142} IP4_Port; 142} IP4_Port;
143 143
144typedef struct { 144typedef struct IP_Port {
145 IP ip; 145 IP ip;
146 uint16_t port; 146 uint16_t port;
147} IP_Port; 147} IP_Port;
diff --git a/toxcore/ping.c b/toxcore/ping.c
index bd754c53..9228649e 100644
--- a/toxcore/ping.c
+++ b/toxcore/ping.c
@@ -27,19 +27,24 @@
27#include "config.h" 27#include "config.h"
28#endif 28#endif
29 29
30#include <stdbool.h>
31#include <stdint.h> 30#include <stdint.h>
32 31
33#include "net_crypto.h"
34#include "DHT.h" 32#include "DHT.h"
33#include "assoc.h"
34#include "ping.h"
35
36#include "network.h"
37#include "util.h"
35 38
36#define PING_NUM_MAX 384 39#define PING_NUM_MAX 384
37#define PING_TIMEOUT 5 // 5s 40
41/* 5 seconds */
42#define PING_TIMEOUT 5
38 43
39/* Ping newly announced nodes to ping per TIME_TOPING seconds*/ 44/* Ping newly announced nodes to ping per TIME_TOPING seconds*/
40#define TIME_TOPING 5 45#define TIME_TOPING 5
41 46
42typedef struct { 47typedef struct PING {
43 Net_Crypto *c; 48 Net_Crypto *c;
44 49
45 pinged_t pings[PING_NUM_MAX]; 50 pinged_t pings[PING_NUM_MAX];
@@ -50,13 +55,7 @@ typedef struct {
50 uint64_t last_toping; 55 uint64_t last_toping;
51} PING; 56} PING;
52 57
53#define __PING_C__ 58static int is_ping_timeout(uint64_t time)
54
55#include "network.h"
56#include "util.h"
57#include "ping.h"
58
59static bool is_ping_timeout(uint64_t time)
60{ 59{
61 return is_timeout(time, PING_TIMEOUT); 60 return is_timeout(time, PING_TIMEOUT);
62} 61}
@@ -259,7 +258,16 @@ static int handle_ping_response(void *_dht, IP_Port source, uint8_t *packet, uin
259 return 1; 258 return 1;
260 259
261 /* Associate client_id with the ip the request was sent to */ 260 /* Associate client_id with the ip the request was sent to */
262 addto_lists(dht, ping->pings[ping_index - 1].ip_port, packet + 1); 261 int used = addto_lists(dht, ping->pings[ping_index - 1].ip_port, packet + 1);
262
263 if (dht->assoc) {
264 IPPTs ippts;
265 ippts.ip_port = ping->pings[ping_index - 1].ip_port;
266 ippts.timestamp = ping->pings[ping_index - 1].timestamp;
267
268 Assoc_add_entry(dht->assoc, packet + 1, &ippts, &source, used > 0 ? 1 : 0);
269 }
270
263 return 0; 271 return 0;
264} 272}
265 273
diff --git a/toxcore/ping.h b/toxcore/ping.h
index 32742401..361fd3ef 100644
--- a/toxcore/ping.h
+++ b/toxcore/ping.h
@@ -24,11 +24,7 @@
24#ifndef __PING_H__ 24#ifndef __PING_H__
25#define __PING_H__ 25#define __PING_H__
26 26
27#include <stdbool.h>
28
29#ifndef __PING_C__
30typedef struct PING PING; 27typedef struct PING PING;
31#endif
32 28
33/* Add nodes to the toping list. 29/* Add nodes to the toping list.
34 * All nodes in this list are pinged every TIME_TOPING seconds 30 * All nodes in this list are pinged every TIME_TOPING seconds
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-10 01:18:46 +0000