summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--CMakeLists.txt8
-rw-r--r--auto_tests/Makefile.inc11
-rw-r--r--auto_tests/assoc_test.c161
-rwxr-xr-xother/travis/toxcore-script1
-rw-r--r--toxcore/DHT.c105
-rw-r--r--toxcore/DHT.h4
-rw-r--r--toxcore/Makefile.inc2
-rw-r--r--toxcore/Messenger.c6
-rw-r--r--toxcore/assoc.c1109
-rw-r--r--toxcore/assoc.h108
10 files changed, 3 insertions, 1512 deletions
diff --git a/CMakeLists.txt b/CMakeLists.txt
index 1585b8dc..add544ef 100644
--- a/CMakeLists.txt
+++ b/CMakeLists.txt
@@ -129,11 +129,6 @@ if(MIN_LOGGER_LEVEL)
129 add_definitions(-DMIN_LOGGER_LEVEL=LOG_${MIN_LOGGER_LEVEL}) 129 add_definitions(-DMIN_LOGGER_LEVEL=LOG_${MIN_LOGGER_LEVEL})
130endif() 130endif()
131 131
132option(ASSOC_DHT "Enable module to store currently unused ID <=> IP associations" OFF)
133if(ASSOC_DHT)
134 add_definitions(-DENABLE_ASSOC_DHT=1)
135endif()
136
137option(ASAN "Enable address-sanitizer to detect invalid memory accesses" OFF) 132option(ASAN "Enable address-sanitizer to detect invalid memory accesses" OFF)
138if(ASAN) 133if(ASAN)
139 set(SAFE_CMAKE_REQUIRED_LIBRARIES "${CMAKE_REQUIRED_LIBRARIES}") 134 set(SAFE_CMAKE_REQUIRED_LIBRARIES "${CMAKE_REQUIRED_LIBRARIES}")
@@ -231,8 +226,6 @@ add_module(toxdht
231 toxcore/DHT.h 226 toxcore/DHT.h
232 toxcore/LAN_discovery.c 227 toxcore/LAN_discovery.c
233 toxcore/LAN_discovery.h 228 toxcore/LAN_discovery.h
234 toxcore/assoc.c
235 toxcore/assoc.h
236 toxcore/ping.c 229 toxcore/ping.c
237 toxcore/ping.h 230 toxcore/ping.h
238 toxcore/ping_array.c 231 toxcore/ping_array.c
@@ -375,7 +368,6 @@ function(auto_test target)
375endfunction() 368endfunction()
376 369
377auto_test(TCP) 370auto_test(TCP)
378auto_test(assoc)
379auto_test(conference) 371auto_test(conference)
380auto_test(crypto) 372auto_test(crypto)
381auto_test(dht) 373auto_test(dht)
diff --git a/auto_tests/Makefile.inc b/auto_tests/Makefile.inc
index 6cb9d5f1..dc1dc9f7 100644
--- a/auto_tests/Makefile.inc
+++ b/auto_tests/Makefile.inc
@@ -1,7 +1,7 @@
1if BUILD_TESTS 1if BUILD_TESTS
2 2
3TESTS = encryptsave_test messenger_autotest crypto_test network_test assoc_test onion_test TCP_test tox_test dht_autotest 3TESTS = encryptsave_test messenger_autotest crypto_test network_test onion_test TCP_test tox_test dht_autotest
4check_PROGRAMS = encryptsave_test messenger_autotest crypto_test network_test assoc_test onion_test TCP_test tox_test dht_autotest 4check_PROGRAMS = encryptsave_test messenger_autotest crypto_test network_test onion_test TCP_test tox_test dht_autotest
5 5
6AUTOTEST_CFLAGS = \ 6AUTOTEST_CFLAGS = \
7 $(LIBSODIUM_CFLAGS) \ 7 $(LIBSODIUM_CFLAGS) \
@@ -47,13 +47,6 @@ network_test_CFLAGS = $(AUTOTEST_CFLAGS)
47network_test_LDADD = $(AUTOTEST_LDADD) 47network_test_LDADD = $(AUTOTEST_LDADD)
48 48
49 49
50assoc_test_SOURCES = ../auto_tests/assoc_test.c
51
52assoc_test_CFLAGS = $(AUTOTEST_CFLAGS)
53
54assoc_test_LDADD = $(AUTOTEST_LDADD)
55
56
57onion_test_SOURCES = ../auto_tests/onion_test.c 50onion_test_SOURCES = ../auto_tests/onion_test.c
58 51
59onion_test_CFLAGS = $(AUTOTEST_CFLAGS) 52onion_test_CFLAGS = $(AUTOTEST_CFLAGS)
diff --git a/auto_tests/assoc_test.c b/auto_tests/assoc_test.c
deleted file mode 100644
index 4814601c..00000000
--- a/auto_tests/assoc_test.c
+++ /dev/null
@@ -1,161 +0,0 @@
1#ifdef HAVE_CONFIG_H
2#include "config.h"
3#endif
4
5#define AUTO_TEST
6#include "../toxcore/DHT.h"
7#include "../toxcore/assoc.h"
8#include "../toxcore/util.h"
9
10#include <stdint.h>
11#include <string.h>
12#include <sys/types.h>
13
14#include <check.h>
15
16#include "helpers.h"
17
18START_TEST(test_basics)
19{
20 /* TODO(irungentoo): real test */
21 uint8_t id[crypto_box_PUBLICKEYBYTES] = {1};
22 Assoc *assoc = new_Assoc_default(NULL, id);
23 ck_assert_msg(assoc != NULL, "failed to create default assoc");
24
25 kill_Assoc(assoc);
26 assoc = new_Assoc(NULL, 17, 4, id); /* results in an assoc of 16/3 */
27 ck_assert_msg(assoc != NULL, "failed to create customized assoc");
28
29 IP_Port ipp;
30 ipp.ip.family = AF_INET;
31 ipp.ip.ip4.uint8[0] = 1;
32 ipp.port = htons(12345);
33
34 IPPTs ippts_send;
35 ippts_send.ip_port = ipp;
36 ippts_send.timestamp = unix_time();
37 IP_Port ipp_recv = ipp;
38
39 uint8_t res = Assoc_add_entry(assoc, id, &ippts_send, &ipp_recv, 0);
40 ck_assert_msg(res == 0, "stored self as entry: expected %u, got %u", 0, res);
41
42 id[0]++;
43
44 res = Assoc_add_entry(assoc, id, &ippts_send, &ipp_recv, 0);
45 ck_assert_msg(res == 1, "failed to store entry: expected %u, got %u", 1, res);
46
47 Assoc_close_entries close_entries;
48 memset(&close_entries, 0, sizeof(close_entries));
49 close_entries.count = 4;
50 close_entries.count_good = 2;
51 close_entries.wanted_id = id;
52
53 Client_data *entries[close_entries.count];
54 close_entries.result = entries;
55
56 uint8_t found = Assoc_get_close_entries(assoc, &close_entries);
57 ck_assert_msg(found == 1, "get_close_entries(): expected %u, got %u", 1, found);
58 kill_Assoc(assoc);
59}
60END_TEST
61
62START_TEST(test_fillup)
63{
64 /* TODO(irungentoo): real test */
65 int i, j;
66 uint8_t id[crypto_box_PUBLICKEYBYTES];
67 //uint32_t a = current_time();
68 uint32_t a = 2710106197;
69 srand(a);
70
71 for (i = 0; i < crypto_box_PUBLICKEYBYTES; ++i) {
72 id[i] = rand();
73 }
74
75 Assoc *assoc = new_Assoc(NULL, 6, 15, id);
76 ck_assert_msg(assoc != NULL, "failed to create default assoc");
77 struct entry {
78 uint8_t id[crypto_box_PUBLICKEYBYTES];
79 IPPTs ippts_send;
80 IP_Port ipp_recv;
81 };
82 struct entry entries[128];
83 struct entry closest[8];
84
85 for (j = 0; j < 128; ++j) {
86
87 for (i = 0; i < crypto_box_PUBLICKEYBYTES; ++i) {
88 entries[j].id[i] = rand();
89 }
90
91 IP_Port ipp;
92 ipp.ip.family = AF_INET;
93 ipp.ip.ip4.uint32 = rand();
94 ipp.port = rand();
95 entries[j].ippts_send.ip_port = ipp;
96 entries[j].ippts_send.timestamp = unix_time();
97 ipp.ip.ip4.uint32 = rand();
98 ipp.port = rand();
99 entries[j].ipp_recv = ipp;
100
101 if (j % 16 == 0) {
102 memcpy(entries[j].id, id, crypto_box_PUBLICKEYBYTES - 30);
103 memcpy(&closest[j / 16], &entries[j], sizeof(struct entry));
104 }
105
106 uint8_t res = Assoc_add_entry(assoc, entries[j].id, &entries[j].ippts_send, &entries[j].ipp_recv, 1);
107 ck_assert_msg(res == 1, "failed to store entry: expected %u, got %u, j = %u", 1, res, j);
108 }
109
110 int good = 0;
111 Assoc_close_entries close_entries;
112 memset(&close_entries, 0, sizeof(close_entries));
113 close_entries.count = 8;
114 close_entries.count_good = 8;
115 close_entries.wanted_id = id;
116
117 Client_data *entri[close_entries.count];
118 close_entries.result = entri;
119
120 uint8_t found = Assoc_get_close_entries(assoc, &close_entries);
121 ck_assert_msg(found == 8, "get_close_entries(): expected %u, got %u", 1, found);
122
123 for (i = 0; i < 8; ++i) {
124 for (j = 0; j < 8; ++j) {
125 if (id_equal(entri[j]->public_key, closest[i].id)) {
126 ++good;
127 }
128 }
129 }
130
131 ck_assert_msg(good == 8, "Entries found were not the closest ones. Only %u/8 were.", good);
132 //printf("good: %u %u %u\n", good, a, ((uint32_t)current_time() - a));
133 kill_Assoc(assoc);
134}
135END_TEST
136
137static Suite *Assoc_suite(void)
138{
139 Suite *s = suite_create("Assoc");
140
141 DEFTESTCASE(basics);
142 DEFTESTCASE(fillup);
143 return s;
144}
145
146int main(int argc, char *argv[])
147{
148 unix_time_update();
149 Suite *Assoc = Assoc_suite();
150 SRunner *test_runner = srunner_create(Assoc);
151
152 srunner_set_fork_status(test_runner, CK_NOFORK);
153
154 srunner_run_all(test_runner, CK_NORMAL);
155
156 int number_failed = srunner_ntests_failed(test_runner);
157
158 srunner_free(test_runner);
159
160 return number_failed;
161}
diff --git a/other/travis/toxcore-script b/other/travis/toxcore-script
index 06e76f12..d25dc135 100755
--- a/other/travis/toxcore-script
+++ b/other/travis/toxcore-script
@@ -11,7 +11,6 @@ RUN $CMAKE \
11 -H. \ 11 -H. \
12 -DCMAKE_INSTALL_PREFIX:PATH=$CURDIR/_install \ 12 -DCMAKE_INSTALL_PREFIX:PATH=$CURDIR/_install \
13 -DASAN=ON \ 13 -DASAN=ON \
14 -DASSOC_DHT=ON \
15 -DDEBUG=ON \ 14 -DDEBUG=ON \
16 -DSTRICT_ABI=ON \ 15 -DSTRICT_ABI=ON \
17 -DTEST_TIMEOUT_SECONDS=300 \ 16 -DTEST_TIMEOUT_SECONDS=300 \
diff --git a/toxcore/DHT.c b/toxcore/DHT.c
index b4ba3fd5..ca9c17ea 100644
--- a/toxcore/DHT.c
+++ b/toxcore/DHT.c
@@ -29,9 +29,6 @@
29 29
30#include "DHT.h" 30#include "DHT.h"
31 31
32#ifdef ENABLE_ASSOC_DHT
33#include "assoc.h"
34#endif
35#include "LAN_discovery.h" 32#include "LAN_discovery.h"
36#include "logger.h" 33#include "logger.h"
37#include "misc_tools.h" 34#include "misc_tools.h"
@@ -773,60 +770,7 @@ int get_close_nodes(const DHT *dht, const uint8_t *public_key, Node_format *node
773 uint8_t is_LAN, uint8_t want_good) 770 uint8_t is_LAN, uint8_t want_good)
774{ 771{
775 memset(nodes_list, 0, MAX_SENT_NODES * sizeof(Node_format)); 772 memset(nodes_list, 0, MAX_SENT_NODES * sizeof(Node_format));
776#ifdef ENABLE_ASSOC_DHT 773 return get_somewhat_close_nodes(dht, public_key, nodes_list, sa_family, is_LAN, want_good);
777
778 if (!dht->assoc)
779#endif
780 return get_somewhat_close_nodes(dht, public_key, nodes_list, sa_family, is_LAN, want_good);
781
782#ifdef ENABLE_ASSOC_DHT
783 // TODO(irungentoo): assoc, sa_family 0 (don't care if ipv4 or ipv6) support.
784 Client_data *result[MAX_SENT_NODES];
785
786 Assoc_close_entries request;
787 memset(&request, 0, sizeof(request));
788 request.count = MAX_SENT_NODES;
789 request.count_good = MAX_SENT_NODES - 2; /* allow 2 'indirect' nodes */
790 request.result = result;
791 request.wanted_id = public_key;
792 request.flags = (is_LAN ? LANOk : 0) + (sa_family == AF_INET ? ProtoIPv4 : ProtoIPv6);
793
794 uint8_t num_found = Assoc_get_close_entries(dht->assoc, &request);
795
796 if (!num_found) {
797 LOGGER_DEBUG(dht->log, "get_close_nodes(): Assoc_get_close_entries() returned zero nodes");
798 return get_somewhat_close_nodes(dht, public_key, nodes_list, sa_family, is_LAN, want_good);
799 }
800
801 LOGGER_DEBUG(dht->log, "get_close_nodes(): Assoc_get_close_entries() returned %i 'direct' and %i 'indirect' nodes",
802 request.count_good, num_found - request.count_good);
803
804 uint8_t i, num_returned = 0;
805
806 for (i = 0; i < num_found; i++) {
807 Client_data *client = result[i];
808
809 if (client) {
810 id_copy(nodes_list[num_returned].public_key, client->public_key);
811
812 if (sa_family == AF_INET)
813 if (ipport_isset(&client->assoc4.ip_port)) {
814 nodes_list[num_returned].ip_port = client->assoc4.ip_port;
815 num_returned++;
816 continue;
817 }
818
819 if (sa_family == AF_INET6)
820 if (ipport_isset(&client->assoc6.ip_port)) {
821 nodes_list[num_returned].ip_port = client->assoc6.ip_port;
822 num_returned++;
823 continue;
824 }
825 }
826 }
827
828 return num_returned;
829#endif
830} 774}
831 775
832static uint8_t cmp_public_key[crypto_box_PUBLICKEYBYTES]; 776static uint8_t cmp_public_key[crypto_box_PUBLICKEYBYTES];
@@ -1156,18 +1100,6 @@ int addto_lists(DHT *dht, IP_Port ip_port, const uint8_t *public_key)
1156 } 1100 }
1157 } 1101 }
1158 1102
1159#ifdef ENABLE_ASSOC_DHT
1160
1161 if (dht->assoc) {
1162 IPPTs ippts;
1163
1164 ippts.ip_port = ip_port;
1165 ippts.timestamp = unix_time();
1166
1167 Assoc_add_entry(dht->assoc, public_key, &ippts, NULL, used ? 1 : 0);
1168 }
1169
1170#endif
1171 return used; 1103 return used;
1172} 1104}
1173 1105
@@ -1224,18 +1156,6 @@ static int returnedip_ports(DHT *dht, IP_Port ip_port, const uint8_t *public_key
1224 } 1156 }
1225 1157
1226end: 1158end:
1227#ifdef ENABLE_ASSOC_DHT
1228
1229 if (dht->assoc) {
1230 IPPTs ippts;
1231 ippts.ip_port = ip_port;
1232 ippts.timestamp = temp_time;
1233 /* this is only a hear-say entry, so ret-ipp is NULL, but used is required
1234 * to decide how valuable it is ("used" may throw an "unused" entry out) */
1235 Assoc_add_entry(dht->assoc, public_key, &ippts, NULL, used ? 1 : 0);
1236 }
1237
1238#endif
1239 return 0; 1159 return 0;
1240} 1160}
1241 1161
@@ -1788,16 +1708,6 @@ void DHT_getnodes(DHT *dht, const IP_Port *from_ipp, const uint8_t *from_id, con
1788 1708
1789void DHT_bootstrap(DHT *dht, IP_Port ip_port, const uint8_t *public_key) 1709void DHT_bootstrap(DHT *dht, IP_Port ip_port, const uint8_t *public_key)
1790{ 1710{
1791 /*#ifdef ENABLE_ASSOC_DHT
1792 if (dht->assoc) {
1793 IPPTs ippts;
1794 ippts.ip_port = ip_port;
1795 ippts.timestamp = 0;
1796
1797 Assoc_add_entry(dht->assoc, public_key, &ippts, NULL, 0);
1798 }
1799 #endif*/
1800
1801 getnodes(dht, ip_port, public_key, dht->self_public_key, NULL); 1711 getnodes(dht, ip_port, public_key, dht->self_public_key, NULL);
1802} 1712}
1803int DHT_bootstrap_from_address(DHT *dht, const char *address, uint8_t ipv6enabled, 1713int DHT_bootstrap_from_address(DHT *dht, const char *address, uint8_t ipv6enabled,
@@ -2700,9 +2610,6 @@ DHT *new_DHT(Logger *log, Networking_Core *net)
2700 2610
2701 ping_array_init(&dht->dht_ping_array, DHT_PING_ARRAY_SIZE, PING_TIMEOUT); 2611 ping_array_init(&dht->dht_ping_array, DHT_PING_ARRAY_SIZE, PING_TIMEOUT);
2702 ping_array_init(&dht->dht_harden_ping_array, DHT_PING_ARRAY_SIZE, PING_TIMEOUT); 2612 ping_array_init(&dht->dht_harden_ping_array, DHT_PING_ARRAY_SIZE, PING_TIMEOUT);
2703#ifdef ENABLE_ASSOC_DHT
2704 dht->assoc = new_Assoc_default(dht->log, dht->self_public_key);
2705#endif
2706 uint32_t i; 2613 uint32_t i;
2707 2614
2708 for (i = 0; i < DHT_FAKE_FRIEND_NUMBER; ++i) { 2615 for (i = 0; i < DHT_FAKE_FRIEND_NUMBER; ++i) {
@@ -2738,20 +2645,10 @@ void do_DHT(DHT *dht)
2738#if DHT_HARDENING 2645#if DHT_HARDENING
2739 do_hardening(dht); 2646 do_hardening(dht);
2740#endif 2647#endif
2741#ifdef ENABLE_ASSOC_DHT
2742
2743 if (dht->assoc) {
2744 do_Assoc(dht->assoc, dht);
2745 }
2746
2747#endif
2748 dht->last_run = unix_time(); 2648 dht->last_run = unix_time();
2749} 2649}
2750void kill_DHT(DHT *dht) 2650void kill_DHT(DHT *dht)
2751{ 2651{
2752#ifdef ENABLE_ASSOC_DHT
2753 kill_Assoc(dht->assoc);
2754#endif
2755 networking_registerhandler(dht->net, NET_PACKET_GET_NODES, NULL, NULL); 2652 networking_registerhandler(dht->net, NET_PACKET_GET_NODES, NULL, NULL);
2756 networking_registerhandler(dht->net, NET_PACKET_SEND_NODES_IPV6, NULL, NULL); 2653 networking_registerhandler(dht->net, NET_PACKET_SEND_NODES_IPV6, NULL, NULL);
2757 cryptopacket_registerhandler(dht, CRYPTO_PACKET_NAT_PING, NULL, NULL); 2654 cryptopacket_registerhandler(dht, CRYPTO_PACKET_NAT_PING, NULL, NULL);
diff --git a/toxcore/DHT.h b/toxcore/DHT.h
index 0691a09e..54ab9121 100644
--- a/toxcore/DHT.h
+++ b/toxcore/DHT.h
@@ -261,9 +261,6 @@ typedef struct {
261 struct PING *ping; 261 struct PING *ping;
262 Ping_Array dht_ping_array; 262 Ping_Array dht_ping_array;
263 Ping_Array dht_harden_ping_array; 263 Ping_Array dht_harden_ping_array;
264#ifdef ENABLE_ASSOC_DHT
265 struct Assoc *assoc;
266#endif
267 uint64_t last_run; 264 uint64_t last_run;
268 265
269 Cryptopacket_Handles cryptopackethandlers[256]; 266 Cryptopacket_Handles cryptopackethandlers[256];
@@ -456,4 +453,3 @@ int DHT_non_lan_connected(const DHT *dht);
456int addto_lists(DHT *dht, IP_Port ip_port, const uint8_t *public_key); 453int addto_lists(DHT *dht, IP_Port ip_port, const uint8_t *public_key);
457 454
458#endif 455#endif
459
diff --git a/toxcore/Makefile.inc b/toxcore/Makefile.inc
index ff413a88..f8f6f9cf 100644
--- a/toxcore/Makefile.inc
+++ b/toxcore/Makefile.inc
@@ -31,8 +31,6 @@ libtoxcore_la_SOURCES = ../toxcore/DHT.h \
31 ../toxcore/util.c \ 31 ../toxcore/util.c \
32 ../toxcore/group.h \ 32 ../toxcore/group.h \
33 ../toxcore/group.c \ 33 ../toxcore/group.c \
34 ../toxcore/assoc.h \
35 ../toxcore/assoc.c \
36 ../toxcore/onion.h \ 34 ../toxcore/onion.h \
37 ../toxcore/onion.c \ 35 ../toxcore/onion.c \
38 ../toxcore/logger.h \ 36 ../toxcore/logger.h \
diff --git a/toxcore/Messenger.c b/toxcore/Messenger.c
index e26ea795..0a3c52ee 100644
--- a/toxcore/Messenger.c
+++ b/toxcore/Messenger.c
@@ -27,7 +27,6 @@
27 27
28#include "Messenger.h" 28#include "Messenger.h"
29 29
30#include "assoc.h"
31#include "logger.h" 30#include "logger.h"
32#include "network.h" 31#include "network.h"
33#include "util.h" 32#include "util.h"
@@ -2501,11 +2500,6 @@ void do_messenger(Messenger *m, void *userdata)
2501 connection_status_cb(m, userdata); 2500 connection_status_cb(m, userdata);
2502 2501
2503 if (unix_time() > lastdump + DUMPING_CLIENTS_FRIENDS_EVERY_N_SECONDS) { 2502 if (unix_time() > lastdump + DUMPING_CLIENTS_FRIENDS_EVERY_N_SECONDS) {
2504
2505#ifdef ENABLE_ASSOC_DHT
2506 Assoc_status(m->log, m->dht->assoc);
2507#endif
2508
2509 lastdump = unix_time(); 2503 lastdump = unix_time();
2510 uint32_t client, last_pinged; 2504 uint32_t client, last_pinged;
2511 2505
diff --git a/toxcore/assoc.c b/toxcore/assoc.c
deleted file mode 100644
index 74e4b0e0..00000000
--- a/toxcore/assoc.c
+++ /dev/null
@@ -1,1109 +0,0 @@
1#ifdef HAVE_CONFIG_H
2#include "config.h"
3#endif
4
5#include "assoc.h"
6
7#include "DHT.h"
8#include "LAN_discovery.h"
9#include "logger.h"
10#include "ping.h"
11#include "util.h"
12
13#include <assert.h>
14
15/*
16 * BASIC OVERVIEW:
17 *
18 * Hash: The client_id is hashed with a local hash function.
19 * Hashes are used in multiple places for searching.
20 * Bucket: The first n bits of the client_id are used to
21 * select a bucket. This speeds up sorting, but the more
22 * important reason is to enforce a spread in the space of
23 * client_ids available.
24 *
25 *
26 * Candidates:
27 *
28 * Candidates are kept in buckets of hash tables. The hash
29 * function is calculated from the client_id. Up to
30 * HASH_COLLIDE_COUNT alternative positions are tried if
31 * the initial position is already used by a different entry.
32 * The collision function is multiplicative, not additive.
33 *
34 * A new candidate can bump an existing candidate, if it is
35 * more "desirable": Seen beats Heard.
36 */
37
38/* candidates: alternative places for the same hash value */
39#define HASH_COLLIDE_COUNT 5
40
41/* bucket size shall be co-prime to this */
42#define HASH_COLLIDE_PRIME 101
43
44/* candidates: bump entries: timeout values for seen/heard to be considered of value */
45#define CANDIDATES_SEEN_TIMEOUT 1800
46#define CANDIDATES_HEARD_TIMEOUT 600
47
48/* distance/index: index size & access mask */
49#define DISTANCE_INDEX_INDEX_BITS (64 - DISTANCE_INDEX_DISTANCE_BITS)
50#define DISTANCE_INDEX_INDEX_MASK ((1 << DISTANCE_INDEX_INDEX_BITS) - 1)
51
52/* types to stay consistent */
53typedef uint16_t bucket_t;
54typedef uint32_t hash_t;
55typedef uint16_t usecnt_t;
56
57/* abbreviations ... */
58typedef Assoc_distance_relative_callback dist_rel_cb;
59typedef Assoc_distance_absolute_callback dist_abs_cb;
60
61/*
62 * Client_data wrapped with additional data
63 */
64typedef struct Client_entry {
65 hash_t hash;
66
67 /* shortcuts & rumors: timers and data */
68 uint64_t getnodes;
69 uint64_t used_at;
70
71 uint64_t seen_at;
72 uint64_t heard_at;
73
74 uint16_t seen_family;
75 uint16_t heard_family;
76
77 IP_Port assoc_heard4;
78 IP_Port assoc_heard6;
79
80 Client_data client;
81} Client_entry;
82
83typedef struct candidates_bucket {
84 Client_entry *list; /* hashed list */
85} candidates_bucket;
86
87struct Assoc {
88 Logger *log;
89 hash_t self_hash; /* hash of self_client_id */
90 uint8_t self_client_id[crypto_box_PUBLICKEYBYTES]; /* don't store entries for this */
91
92 /* association centralization: clients not in use */
93 size_t candidates_bucket_bits;
94 size_t candidates_bucket_count;
95 size_t candidates_bucket_size;
96 candidates_bucket *candidates;
97 uint64_t getnodes;
98};
99
100/*****************************************************************************/
101/* HELPER FUNCTIONS */
102/*****************************************************************************/
103
104/* the complete distance would be crypto_box_PUBLICKEYBYTES long...
105 * returns DISTANCE_INDEX_DISTANCE_BITS valid bits */
106static uint64_t id_distance(const Assoc *assoc, void *callback_data, const uint8_t *id_ref, const uint8_t *id_test)
107{
108 /* with BIG_ENDIAN, this would be a one-liner... */
109 uint64_t retval = 0;
110
111 uint8_t pos = 0, bits = DISTANCE_INDEX_DISTANCE_BITS;
112
113 while (bits > 8) {
114 uint8_t distance = abs((int8_t)id_ref[pos] ^ (int8_t)id_test[pos]);
115 retval = (retval << 8) | distance;
116 bits -= 8;
117 pos++;
118 }
119
120 return (retval << bits) | ((id_ref[pos] ^ id_test[pos]) >> (8 - bits));
121}
122
123/* qsort() callback for a sorting by id_distance() values */
124static int dist_index_comp(const void *a, const void *b)
125{
126 const uint64_t *_a = (const uint64_t *)a;
127 const uint64_t *_b = (const uint64_t *)b;
128
129 if (*_a < *_b) {
130 return -1;
131 }
132
133 if (*_a > *_b) {
134 return 1;
135 }
136
137 return 0;
138}
139
140/* get actual entry to a distance_index */
141static Client_entry *dist_index_entry(Assoc *assoc, uint64_t dist_ind)
142{
143 if ((dist_ind & DISTANCE_INDEX_INDEX_MASK) == DISTANCE_INDEX_INDEX_MASK) {
144 return NULL;
145 }
146
147 size_t total = assoc->candidates_bucket_count * assoc->candidates_bucket_size;
148 uint32_t index = dist_ind & DISTANCE_INDEX_INDEX_MASK;
149
150 if (index < total) {
151 bucket_t b_id = index / assoc->candidates_bucket_size;
152 candidates_bucket *cnd_bckt = &assoc->candidates[b_id];
153 size_t b_ix = index % assoc->candidates_bucket_size;
154 Client_entry *entry = &cnd_bckt->list[b_ix];
155
156 if (entry->hash) {
157 return entry;
158 }
159 }
160
161 return NULL;
162}
163
164/* get actual entry's public_key to a distance_index */
165static uint8_t *dist_index_id(Assoc *assoc, uint64_t dist_ind)
166{
167 Client_entry *entry = dist_index_entry(assoc, dist_ind);
168
169 if (entry) {
170 return entry->client.public_key;
171 }
172
173 return NULL;
174}
175
176/* sorts first .. last, i.e. last is included */
177static void dist_index_bubble(Assoc *assoc, uint64_t *dist_list, size_t first, size_t last, const uint8_t *id,
178 void *custom_data, Assoc_distance_relative_callback dist_rel_func)
179{
180 size_t i, k;
181
182 for (i = first; i <= last; i++) {
183 uint8_t *id1 = dist_index_id(assoc, dist_list[i]);
184
185 for (k = i + 1; k <= last; k++) {
186 uint8_t *id2 = dist_index_id(assoc, dist_list[k]);
187
188 if (id1 && id2) {
189 if (dist_rel_func(assoc, custom_data, id, id1, id2) == 2) {
190 uint64_t swap = dist_list[i];
191 dist_list[i] = dist_list[k];
192 dist_list[k] = swap;
193 }
194 }
195 }
196 }
197}
198
199/* TODO(irungentoo): Check that there isn't a function like this elsewhere hidden.
200 * E.g. the one which creates a handshake_id isn't usable for this, it must
201 * always map the same ID to the same hash.
202 *
203 * Result is NOT MAPPED to CANDIDATES_TO_KEEP range, i.e. map before using
204 * it for list access. */
205static hash_t id_hash(const Assoc *assoc, const uint8_t *id)
206{
207 uint32_t i, res = 0x19a64e82;
208
209 for (i = 0; i < crypto_box_PUBLICKEYBYTES; i++) {
210 res = ((res << 1) ^ id[i]) + (res >> 31);
211 }
212
213 /* can't have zero as hash, a) marks an unused spot,
214 * b) collision function is multiplicative */
215 if (!(res % assoc->candidates_bucket_size)) {
216 res++;
217 }
218
219 return res;
220}
221
222/* up to HASH_COLLIDE_COUNT calls to different spots,
223 * result IS mapped to CANDIDATES_TO_KEEP range */
224static hash_t hash_collide(const Assoc *assoc, hash_t hash)
225{
226 uint64_t hash64 = hash % assoc->candidates_bucket_size;
227 hash64 = (hash64 * HASH_COLLIDE_PRIME) % assoc->candidates_bucket_size;
228
229 hash_t retval = hash64;
230
231 /* this should never happen when CANDIDATES_TO_KEEP is prime and hash not a multiple
232 * (id_hash() checks for a multiple and returns a different hash in that case)
233 *
234 * ( 1 .. (prime - 1) is a group over multiplication and every number has its inverse
235 * in the group, so no multiplication should ever end on zero as long neither
236 * of the two factors was zero-equivalent )
237 *
238 * BUT: because the usage of the word "never" invokes Murphy's law, catch it */
239 if (!retval) {
240#ifdef TOX_DEBUG
241 fprintf(stderr, "assoc::hash_collide: hash %u, bucket size %u => %u!", hash,
242 (unsigned int)assoc->candidates_bucket_size, retval);
243 assert(retval != 0);
244#endif
245 retval = 1;
246 }
247
248 return retval;
249}
250
251/* returns the "seen" assoc related to the ipp */
252static IPPTsPng *entry_assoc(Client_entry *cl_entry, const IP_Port *ipp)
253{
254 if (!cl_entry) {
255 return NULL;
256 }
257
258 if (ipp->ip.family == AF_INET) {
259 return &cl_entry->client.assoc4;
260 }
261
262 if (ipp->ip.family == AF_INET6) {
263 return &cl_entry->client.assoc6;
264 }
265
266 return NULL;
267}
268
269/* returns the "heard" assoc related to the ipp */
270static IP_Port *entry_heard_get(Client_entry *entry, const IP_Port *ipp)
271{
272 if (ipp->ip.family == AF_INET) {
273 return &entry->assoc_heard4;
274 }
275
276 if (ipp->ip.family == AF_INET6) {
277 return &entry->assoc_heard6;
278 }
279
280 return NULL;
281}
282
283/* store a "heard" entry
284 * overwrites empty entry, does NOT overwrite non-LAN ip with
285 * LAN ip
286 *
287 * returns 1 if the entry did change */
288static int entry_heard_store(Client_entry *entry, const IPPTs *ippts)
289{
290 if (!entry || !ippts) {
291 return 0;
292 }
293
294 if (!ipport_isset(&ippts->ip_port)) {
295 return 0;
296 }
297
298 IP_Port *heard;
299 const IP_Port *ipp = &ippts->ip_port;
300
301 if (ipp->ip.family == AF_INET) {
302 heard = &entry->assoc_heard4;
303 } else if (ipp->ip.family == AF_INET6) {
304 heard = &entry->assoc_heard6;
305 } else {
306 return 0;
307 }
308
309 if (ipport_equal(ipp, heard)) {
310 return 0;
311 }
312
313 if (!ipport_isset(heard)) {
314 *heard = *ipp;
315 entry->heard_at = ippts->timestamp;
316 entry->heard_family = ipp->ip.family;
317 return 1;
318 }
319
320 /* don't destroy a good address with a crappy one
321 * (unless we're very timed out) */
322 uint8_t LAN_ipp = LAN_ip(ipp->ip) == 0;
323 uint8_t LAN_entry = LAN_ip(heard->ip) == 0;
324
325 if (LAN_ipp && !LAN_entry && !is_timeout(entry->heard_at, CANDIDATES_HEARD_TIMEOUT)) {
326 return 0;
327 }
328
329 *heard = *ipp;
330 entry->heard_at = ippts->timestamp;
331 entry->heard_family = ipp->ip.family;
332
333 return 1;
334}
335
336/* maps Assoc callback signature to id_closest() */
337static int assoc_id_closest(const Assoc *assoc, void *callback_data, const uint8_t *client_id,
338 const uint8_t *client_id1, const uint8_t *client_id2)
339{
340 return id_closest(client_id, client_id1, client_id2);
341}
342
343static bucket_t id_bucket(const uint8_t *id, uint8_t bits)
344{
345 /* return the first "bits" bits of id */
346 bucket_t retval = 0;
347
348 uint8_t pos = 0;
349
350 while (bits > 8) {
351 retval = (retval << 8) | id[pos++];
352 bits -= 8;
353 }
354
355 return (retval << bits) | (id[pos] >> (8 - bits));
356}
357
358/*****************************************************************************/
359/* CANDIDATES FUNCTIONS */
360/*****************************************************************************/
361
362
363static bucket_t candidates_id_bucket(const Assoc *assoc, const uint8_t *id)
364{
365 return id_bucket(id, assoc->candidates_bucket_bits);
366}
367
368static uint8_t candidates_search(const Assoc *assoc, const uint8_t *id, hash_t hash, Client_entry **entryptr)
369{
370 bucket_t bucket = candidates_id_bucket(assoc, id);
371 candidates_bucket *cnd_bckt = &assoc->candidates[bucket];
372 size_t coll, pos = hash % assoc->candidates_bucket_size;
373
374 for (coll = 0; coll < HASH_COLLIDE_COUNT; pos = hash_collide(assoc, pos) , coll++) {
375 Client_entry *entry = &cnd_bckt->list[pos];
376
377 if (entry->hash == hash) {
378 if (id_equal(entry->client.public_key, id)) {
379 *entryptr = entry;
380 return 1;
381 }
382 }
383 }
384
385 *entryptr = NULL;
386 return 0;
387}
388
389static void candidates_update_assoc(const Assoc *assoc, Client_entry *entry, uint8_t used, const IPPTs *ippts_send,
390 const IP_Port *ipp_recv)
391{
392 if (!assoc || !entry || !ippts_send) {
393 return;
394 }
395
396 IPPTsPng *ipptsp = entry_assoc(entry, &ippts_send->ip_port);
397
398 if (!ipptsp) {
399 return;
400 }
401
402 if (used) {
403 entry->used_at = unix_time();
404 }
405
406 /* do NOT do anything related to wanted, that's handled outside,
407 * just update the assoc (in the most sensible way)
408 */
409 if (ipp_recv) {
410 ipptsp->ip_port = ippts_send->ip_port;
411 ipptsp->timestamp = ippts_send->timestamp;
412 ipptsp->ret_ip_port = *ipp_recv;
413 ipptsp->ret_timestamp = unix_time();
414
415 entry->seen_at = unix_time();
416 entry->seen_family = ippts_send->ip_port.ip.family;
417
418 return;
419 }
420
421 entry_heard_store(entry, ippts_send);
422}
423
424static uint8_t candidates_create_internal(const Assoc *assoc, hash_t const hash, const uint8_t *id, uint8_t seen,
425 uint8_t used, bucket_t *bucketptr, size_t *posptr)
426{
427 if (!assoc || !id || !bucketptr || !posptr) {
428 return 0;
429 }
430
431 bucket_t bucket = candidates_id_bucket(assoc, id);
432 candidates_bucket *cnd_bckt = &assoc->candidates[bucket];
433
434 size_t coll, pos = hash % assoc->candidates_bucket_size, check;
435 size_t pos_check[6];
436
437 memset(pos_check, 0, sizeof(pos_check));
438
439 for (coll = 0; coll < HASH_COLLIDE_COUNT; pos = hash_collide(assoc, pos) , coll++) {
440 Client_entry *entry = &cnd_bckt->list[pos];
441
442 /* unset */
443 if (!entry->hash) {
444 *bucketptr = bucket;
445 *posptr = pos;
446
447 return 1;
448 }
449
450 /* 0. bad
451 * 1. seen bad, heard good
452 * 2. seen good
453 * 3. used */
454 // enumerated lists are superior to magic numbers
455 if (!is_timeout(entry->used_at, BAD_NODE_TIMEOUT)) {
456 check = USED;
457 } else if (!is_timeout(entry->seen_at, CANDIDATES_SEEN_TIMEOUT)) {
458 check = SEENG;
459 } else if (!is_timeout(entry->heard_at, CANDIDATES_HEARD_TIMEOUT)) {
460 check = SEENB_HEARDG;
461 } else {
462 check = BAD;
463 }
464
465 if (!pos_check[check]) {
466 pos_check[check] = pos + 1;
467 }
468 }
469
470 /* used > seen > heard > bad */
471 size_t i, pos_max = used ? USED : (seen ? SEENG : SEENB_HEARDG);
472
473 for (i = 0; i < pos_max; i++) {
474 if (pos_check[i]) {
475 *bucketptr = bucket;
476 *posptr = pos_check[i] - 1;
477
478 return 1;
479 }
480 }
481
482 return 0;
483}
484
485static uint8_t candidates_create_new(const Assoc *assoc, hash_t hash, const uint8_t *id, uint8_t used,
486 const IPPTs *ippts_send, const IP_Port *ipp_recv)
487{
488 if (!assoc || !id || !ippts_send) {
489 return 0;
490 }
491
492 bucket_t bucket;
493 size_t pos;
494
495 if (!candidates_create_internal(assoc, hash, id, ipp_recv != NULL, used, &bucket, &pos)) {
496 return 0;
497 }
498
499 candidates_bucket *cnd_bckt = &assoc->candidates[bucket];
500 Client_entry *entry = &cnd_bckt->list[pos];
501 memset(entry, 0, sizeof(*entry));
502 IPPTsPng *ipptsp = entry_assoc(entry, &ippts_send->ip_port);
503
504 if (!ipptsp) {
505 return 0;
506 }
507
508 entry->hash = hash;
509 id_copy(entry->client.public_key, id);
510
511 if (used) {
512 entry->used_at = unix_time();
513 }
514
515 if (ipp_recv && !ipport_isset(ipp_recv)) {
516 ipp_recv = NULL;
517 }
518
519 if (ipp_recv) {
520 entry->seen_at = ippts_send->timestamp;
521 entry->seen_family = ippts_send->ip_port.ip.family;
522
523 ipptsp->ip_port = ippts_send->ip_port;
524 ipptsp->timestamp = ippts_send->timestamp;
525 ipptsp->ret_ip_port = *ipp_recv;
526 ipptsp->ret_timestamp = unix_time();
527 } else {
528 IP_Port *heard = entry_heard_get(entry, &ippts_send->ip_port);
529
530 if (heard) {
531 entry->heard_at = ippts_send->timestamp;
532 entry->heard_family = ippts_send->ip_port.ip.family;
533
534 *heard = ippts_send->ip_port;
535 }
536 }
537
538 return 1;
539}
540
541/*****************************************************************************/
542
543static void client_id_self_update(Assoc *assoc)
544{
545 if (assoc->self_hash) {
546 return;
547 }
548
549 size_t i, sum = 0;
550
551 for (i = 0; i < crypto_box_PUBLICKEYBYTES; i++) {
552 sum |= assoc->self_client_id[i];
553 }
554
555 if (!sum) {
556 return;
557 }
558
559 assoc->self_hash = id_hash(assoc, assoc->self_client_id);
560
561 LOGGER_DEBUG(assoc->log, "id is now set, purging cache of self-references");
562
563 /* if we already added some (or loaded some) entries,
564 * look and remove if we find a match
565 */
566 bucket_t b_id = candidates_id_bucket(assoc, assoc->self_client_id);
567 candidates_bucket *cnd_bckt = &assoc->candidates[b_id];
568 size_t pos = assoc->self_hash % assoc->candidates_bucket_size;
569
570 for (i = 0; i < HASH_COLLIDE_COUNT; pos = hash_collide(assoc, pos), i++) {
571 Client_entry *entry = &cnd_bckt->list[pos];
572
573 if (entry->hash == assoc->self_hash) {
574 if (id_equal(entry->client.public_key, assoc->self_client_id)) {
575 entry->hash = 0;
576 }
577 }
578 }
579}
580
581/*****************************************************************************/
582/* TRIGGER FUNCTIONS */
583/*****************************************************************************/
584
585/* Central entry point for new associations: add a new candidate to the cache
586 * seen should be 0 (zero), if the candidate was announced by someone else,
587 * seen should be 1 (one), if there is confirmed connectivity (a definite response)
588 */
589uint8_t Assoc_add_entry(Assoc *assoc, const uint8_t *id, const IPPTs *ippts_send, const IP_Port *ipp_recv, uint8_t used)
590{
591 if (!assoc || !id || !ippts_send) {
592 return 0;
593 }
594
595 if (!assoc->self_hash) {
596 client_id_self_update(assoc);
597
598 if (!assoc->self_hash) {
599 return 0;
600 }
601 }
602
603 if (!ipport_isset(&ippts_send->ip_port)) {
604 return 0;
605 }
606
607 if (ipp_recv && !ipport_isset(ipp_recv)) {
608 ipp_recv = NULL;
609 }
610
611 hash_t hash = id_hash(assoc, id);
612
613 if (hash == assoc->self_hash) {
614 if (id_equal(id, assoc->self_client_id)) {
615 return 0;
616 }
617 }
618
619 /* if it's new:
620 * callback, if there's desire, add to clients, else to candidates
621 *
622 * if it's "old":
623 * if it's client: refresh
624 * if it's candidate:
625 * if !ipp_recv, refresh
626 * if ipp_recv: callback, if there's desire, move to candidates
627 */
628 Client_entry *cnd_entry;
629
630 if (!candidates_search(assoc, id, hash, &cnd_entry)) {
631 if (candidates_create_new(assoc, hash, id, used, ippts_send, ipp_recv)) {
632 return 1;
633 }
634
635 return 0;
636 }
637
638 candidates_update_assoc(assoc, cnd_entry, used, ippts_send, ipp_recv);
639 return 2;
640}
641
642/*****************************************************************************/
643/* MAIN USE */
644/*****************************************************************************/
645
646uint8_t Assoc_get_close_entries(Assoc *assoc, Assoc_close_entries *state)
647{
648 if (!assoc || !state || !state->wanted_id || !state->result) {
649 return 0;
650 }
651
652 if (!assoc->self_hash) {
653 client_id_self_update(assoc);
654
655 if (!assoc->self_hash) {
656 return 0;
657 }
658 }
659
660 if (!state->distance_relative_func) {
661 state->distance_relative_func = assoc_id_closest;
662 }
663
664 if (!state->distance_absolute_func) {
665 state->distance_absolute_func = id_distance;
666 }
667
668 size_t dist_list_len = assoc->candidates_bucket_count * assoc->candidates_bucket_size;
669 uint64_t dist_list[dist_list_len];
670 memset(dist_list, ~0, dist_list_len * sizeof(dist_list[0]));
671 bucket_t b;
672 size_t i;
673
674 for (b = 0; b < assoc->candidates_bucket_count; b++) {
675 candidates_bucket *cnd_bckt = &assoc->candidates[b];
676
677 for (i = 0; i < assoc->candidates_bucket_size; i++) {
678 Client_entry *entry = &cnd_bckt->list[i];
679
680 if (entry->hash) {
681 if (state->flags & ProtoIPv4) {
682 if (!ipport_isset(&entry->client.assoc4.ip_port)) {
683 continue;
684 }
685
686 if (!(state->flags & LANOk)) {
687 if (!LAN_ip(entry->client.assoc4.ip_port.ip)) {
688 continue;
689 }
690 }
691 }
692
693 if (state->flags & ProtoIPv6) {
694 if (!ipport_isset(&entry->client.assoc6.ip_port)) {
695 continue;
696 }
697
698 if (!(state->flags & LANOk)) {
699 if (!LAN_ip(entry->client.assoc6.ip_port.ip)) {
700 continue;
701 }
702 }
703 }
704
705 uint64_t dist = state->distance_absolute_func(assoc, state->custom_data, state->wanted_id, entry->client.public_key);
706 uint32_t index = b * assoc->candidates_bucket_size + i;
707 dist_list[index] = (dist << DISTANCE_INDEX_INDEX_BITS) | index;
708 }
709 }
710 }
711
712 qsort(dist_list, dist_list_len, sizeof(dist_list[0]), dist_index_comp);
713
714 /* ok, ok, it's not *perfectly* sorted, because we used an absolute distance
715 * go over the result and see if we need to "smoothen things out"
716 * because those should be only very few and short streaks, the worst regularly
717 * used sorting function aka bubble sort is used */
718 uint64_t dist_prev = ~0;
719 size_t ind_prev = ~0, ind_curr;
720 size_t len = 1;
721
722 for (ind_curr = 0; ind_curr < dist_list_len; ind_curr++) {
723 /* sorted increasingly, so an invalid entry marks the end */
724 if ((dist_list[ind_curr] & DISTANCE_INDEX_INDEX_MASK) == DISTANCE_INDEX_INDEX_MASK) {
725 break;
726 }
727
728 uint64_t dist_curr = dist_list[ind_curr] >> DISTANCE_INDEX_INDEX_BITS;
729
730 if (dist_prev == dist_curr) {
731 len++;
732 } else {
733 if (len > 1) {
734 dist_index_bubble(assoc, dist_list, ind_prev, ind_curr - 1, state->wanted_id, state->custom_data,
735 state->distance_relative_func);
736 }
737
738 dist_prev = dist_curr;
739 ind_prev = ind_curr;
740 len = 1;
741 }
742 }
743
744 if (len > 1) {
745 dist_index_bubble(assoc, dist_list, ind_prev, ind_curr - 1, state->wanted_id, state->custom_data,
746 state->distance_relative_func);
747 }
748
749 /* ok, now dist_list is a strictly ascending sorted list of nodes
750 * a) extract CLOSE_QUOTA_USED clients, not timed out
751 * b) extract (1 - QUOTA) (better!) clients & candidates, not timed out
752 * c) save candidates which would be better, if contact can be established */
753 size_t client_quota_good = 0, pos = 0;
754 size_t client_quota_max = state->count_good;
755
756 ssize_t taken_last = - 1;
757
758 for (i = 0; (i < dist_list_len) && (pos < state->count); i++) {
759 /* sorted increasingly, so an invalid entry marks the end */
760 if ((dist_list[i] & DISTANCE_INDEX_INDEX_MASK) == DISTANCE_INDEX_INDEX_MASK) {
761 break;
762 }
763
764 Client_entry *entry = dist_index_entry(assoc, dist_list[i]);
765
766 if (entry && entry->hash) {
767 if (client_quota_good >= client_quota_max) {
768 state->result[pos++] = &entry->client;
769 taken_last = i;
770 } else {
771 if (state->flags & (ProtoIPv4 | ProtoIPv6)) {
772 if ((state->flags & ProtoIPv4) && is_timeout(entry->client.assoc4.timestamp, BAD_NODE_TIMEOUT)) {
773 continue;
774 }
775
776 if ((state->flags & ProtoIPv6) && is_timeout(entry->client.assoc6.timestamp, BAD_NODE_TIMEOUT)) {
777 continue;
778 }
779 } else if (is_timeout(entry->seen_at, BAD_NODE_TIMEOUT)) {
780 continue;
781 }
782
783 state->result[pos++] = &entry->client;
784 client_quota_good++;
785 taken_last = i;
786 }
787 }
788 }
789
790 /* if we had not enough valid entries the list might still not be filled.
791 *
792 * start again from last taken client, but leave out any requirement
793 */
794 if (pos < state->count) {
795 for (i = taken_last + 1; (i < dist_list_len) && (pos < state->count); i++) {
796 /* sorted increasingly, so an invalid entry marks the end */
797 if ((dist_list[i] & DISTANCE_INDEX_INDEX_MASK) == DISTANCE_INDEX_INDEX_MASK) {
798 break;
799 }
800
801 Client_entry *entry = dist_index_entry(assoc, dist_list[i]);
802
803 if (entry && entry->hash) {
804 state->result[pos++] = &entry->client;
805 }
806 }
807 }
808
809 return pos;
810}
811
812/*****************************************************************************/
813/* GLOBAL STRUCTURE FUNCTIONS */
814/*****************************************************************************/
815
816static uint8_t odd_min9_is_prime(size_t value)
817{
818 size_t i = 3;
819
820 while (i * i <= value) {
821 if (!(value % i)) {
822 return 0;
823 }
824
825 i += 2;
826 }
827
828 return 1;
829}
830
831static size_t prime_upto_min9(size_t limit)
832{
833 /* even => odd */
834 limit = limit - (1 - (limit % 2));
835
836 while (!odd_min9_is_prime(limit)) {
837 limit -= 2;
838 }
839
840 return limit;
841}
842
843/* create */
844Assoc *new_Assoc(Logger *log, size_t bits, size_t entries, const uint8_t *public_id)
845{
846 if (!public_id) {
847 return NULL;
848 }
849
850 Assoc *assoc = (Assoc *)calloc(1, sizeof(*assoc));
851
852 if (!assoc) {
853 return NULL;
854 }
855
856 assoc->log = log;
857
858 /*
859 * bits must be in [ 2 .. 15 ]
860 * entries must be a prime
861 */
862 if (bits < 2) {
863 bits = 2;
864 } else if (bits > 15) {
865 bits = 15;
866 }
867
868 assoc->candidates_bucket_bits = bits;
869 assoc->candidates_bucket_count = 1U << bits;
870
871 if (entries < 25) {
872 if (entries <= 6) {
873 entries = 5;
874 } else {
875 entries = entries - (1 - (entries % 2)); /* even => odd */
876
877 /* 7..23: all odds but 9&15 are prime */
878 if (!(entries % 3)) { /* 9, 15 */
879 entries -= 2; /* 7, 13 */
880 }
881 }
882 } else if (entries > ((1 << 17) - 1)) { /* 130k+ */
883 entries = (1 << 17) - 1;
884 } else {
885 /* 9+: test and find a prime less or equal */
886 size_t entries_test = prime_upto_min9(entries);
887
888 if (entries_test == HASH_COLLIDE_PRIME) { /* disallowed */
889 entries_test = prime_upto_min9(entries_test - 1);
890 }
891
892 if (entries_test != entries) {
893
894 LOGGER_DEBUG(assoc->log, "trimmed %i to %i.\n", (int)entries, (int)entries_test);
895 entries = entries_test;
896 }
897 }
898
899 assoc->candidates_bucket_size = entries;
900
901 /* allocation: preferably few blobs */
902 size_t bckt, cix;
903 Client_entry *clients = (Client_entry *)malloc(sizeof(*clients) * assoc->candidates_bucket_count *
904 assoc->candidates_bucket_size);
905
906 if (!clients) {
907 free(assoc);
908 return NULL;
909 }
910
911 candidates_bucket *lists = (candidates_bucket *)malloc(sizeof(*lists) * assoc->candidates_bucket_count);
912
913 if (!lists) {
914 free(assoc);
915 free(clients);
916 return NULL;
917 }
918
919 for (bckt = 0; bckt < assoc->candidates_bucket_count; bckt++) {
920 candidates_bucket *list = &lists[bckt];
921
922 list->list = &clients[bckt * assoc->candidates_bucket_size];
923
924 for (cix = 0; cix < assoc->candidates_bucket_size; cix++) {
925 list->list[cix].hash = 0;
926 }
927 }
928
929 assoc->candidates = lists;
930 assoc->getnodes = unix_time();
931
932 id_copy(assoc->self_client_id, public_id);
933 client_id_self_update(assoc);
934
935 return assoc;
936}
937
938Assoc *new_Assoc_default(Logger *log, const uint8_t *public_id)
939{
940 /* original 8, 251 averages to ~32k entries... probably the whole DHT :D
941 * 320 entries is fine, hopefully */
942 return new_Assoc(log, 6, 15, public_id);
943}
944
945/* own client_id, assocs for this have to be ignored */
946void Assoc_self_client_id_changed(Assoc *assoc, const uint8_t *id)
947{
948 if (assoc && id) {
949 assoc->self_hash = 0;
950 id_copy(assoc->self_client_id, id);
951 client_id_self_update(assoc);
952 }
953}
954
955static char *idpart2str(uint8_t *id, size_t len);
956
957/* refresh buckets */
958void do_Assoc(Assoc *assoc, DHT *dht)
959{
960 if (is_timeout(assoc->getnodes, ASSOC_BUCKET_REFRESH)) {
961 assoc->getnodes = unix_time();
962
963 size_t candidate = (rand() % assoc->candidates_bucket_count) + assoc->candidates_bucket_count;
964
965 /* in that bucket or the buckets closest to it:
966 * find the best heard candidate
967 * find the best seen candidate
968 * send getnode() requests to both */
969 uint8_t *target_id = NULL;
970 Client_entry *heard = NULL, *seen = NULL;
971 size_t i, k, m;
972
973 for (i = 1; i < assoc->candidates_bucket_count; i++) {
974 if (i % 2) {
975 k = - (i >> 1);
976 } else {
977 k = i >> 1;
978 }
979
980 size_t bckt = (candidate + k) % assoc->candidates_bucket_count;
981
982 for (m = 0; m < assoc->candidates_bucket_size; m++) {
983 if (assoc->candidates[bckt].list[m].hash) {
984 Client_entry *entry = &assoc->candidates[bckt].list[m];
985
986 if (!is_timeout(entry->getnodes, CANDIDATES_SEEN_TIMEOUT)) {
987 continue;
988 }
989
990 if (!target_id) {
991 target_id = entry->client.public_key;
992 }
993
994 if (entry->seen_at) {
995 if (!seen) {
996 if (!is_timeout(entry->seen_at, CANDIDATES_SEEN_TIMEOUT)) {
997 seen = entry;
998 }
999 }
1000 }
1001
1002 if (entry->heard_at) {
1003 if (!heard) {
1004 if (!is_timeout(entry->heard_at, CANDIDATES_HEARD_TIMEOUT)) {
1005 heard = entry;
1006 }
1007 }
1008 }
1009
1010 if (seen && heard) {
1011 break;
1012 }
1013 }
1014 }
1015
1016 if (seen && heard) {
1017 break;
1018 }
1019 }
1020
1021 if (seen) {
1022 IPPTsPng *ippts = seen->seen_family == AF_INET ? &seen->client.assoc4 : &seen->client.assoc6;
1023
1024 LOGGER_DEBUG(assoc->log, "[%u] => S[%s...] %s:%u", (uint32_t)(candidate % assoc->candidates_bucket_count),
1025 idpart2str(seen->client.public_key, 8), ip_ntoa(&ippts->ip_port.ip), htons(ippts->ip_port.port));
1026
1027 DHT_getnodes(dht, &ippts->ip_port, seen->client.public_key, target_id);
1028 seen->getnodes = unix_time();
1029 }
1030
1031 if (heard && (heard != seen)) {
1032 IP_Port *ipp = heard->heard_family == AF_INET ? &heard->assoc_heard4 : &heard->assoc_heard6;
1033
1034 LOGGER_DEBUG(assoc->log, "[%u] => H[%s...] %s:%u", (uint32_t)(candidate % assoc->candidates_bucket_count),
1035 idpart2str(heard->client.public_key, 8), ip_ntoa(&ipp->ip), htons(ipp->port));
1036
1037 DHT_getnodes(dht, ipp, heard->client.public_key, target_id);
1038 heard->getnodes = unix_time();
1039 }
1040
1041 if (!heard && !seen) {
1042 LOGGER_DEBUG(assoc->log, "[%u] => no nodes to talk to??", (uint32_t)(candidate % assoc->candidates_bucket_count));
1043 }
1044 }
1045}
1046
1047/* destroy */
1048void kill_Assoc(Assoc *assoc)
1049{
1050 if (assoc) {
1051 free(assoc->candidates->list);
1052 free(assoc->candidates);
1053 free(assoc);
1054 }
1055}
1056
1057static char buffer[crypto_box_PUBLICKEYBYTES * 2 + 1];
1058static char *idpart2str(uint8_t *id, size_t len)
1059{
1060 if (len > crypto_box_PUBLICKEYBYTES) {
1061 len = crypto_box_PUBLICKEYBYTES;
1062 }
1063
1064 size_t i;
1065
1066 for (i = 0; i < len; i++) {
1067 sprintf(buffer + i * 2, "%02hhx", id[i]);
1068 }
1069
1070 buffer[len * 2] = 0;
1071 return buffer;
1072}
1073
1074void Assoc_status(Logger *log, const Assoc *assoc)
1075{
1076 if (!assoc) {
1077 LOGGER_TRACE(log, "Assoc status: no assoc");
1078 return;
1079 }
1080
1081 LOGGER_TRACE(log, "[b:p] hash => [id...] used, seen, heard");
1082
1083 size_t bid, cid, total = 0;
1084
1085 for (bid = 0; bid < assoc->candidates_bucket_count; bid++) {
1086 candidates_bucket *bucket = &assoc->candidates[bid];
1087
1088 for (cid = 0; cid < assoc->candidates_bucket_size; cid++) {
1089 Client_entry *entry = &bucket->list[cid];
1090
1091 if (entry->hash) {
1092 total++;
1093
1094 LOGGER_TRACE(log, "[%3i:%3i] %08x => [%s...] %i, %i(%c), %i(%c)\n",
1095 (int)bid, (int)cid, entry->hash, idpart2str(entry->client.public_key, 8),
1096 entry->used_at ? (int)(unix_time() - entry->used_at) : 0,
1097 entry->seen_at ? (int)(unix_time() - entry->seen_at) : 0,
1098 entry->seen_at ? (entry->seen_family == AF_INET ? '4' : (entry->seen_family == AF_INET6 ? '6' : '?')) : '?',
1099 entry->heard_at ? (int)(unix_time() - entry->heard_at) : 0,
1100 entry->heard_at ? (entry->heard_family == AF_INET ? '4' : (entry->heard_family == AF_INET6 ? '6' : '?')) : '?');
1101 }
1102 }
1103 }
1104
1105 if (total) {
1106 LOGGER_TRACE(log, "Total: %i entries, table usage %i%%.\n", (int)total,
1107 (int)(total * 100 / (assoc->candidates_bucket_count * assoc->candidates_bucket_size)));
1108 }
1109}
diff --git a/toxcore/assoc.h b/toxcore/assoc.h
deleted file mode 100644
index 1739d295..00000000
--- a/toxcore/assoc.h
+++ /dev/null
@@ -1,108 +0,0 @@
1#ifndef ASSOC_H
2#define ASSOC_H
3
4#include "DHT.h"
5#include "logger.h"
6#include "network.h"
7
8#include <stddef.h>
9#include <stdint.h>
10
11/* used by rendezvous */
12#define ASSOC_AVAILABLE
13
14/* For the legalese parts, see tox.h. */
15
16/* enumerated lists are superior to magic numbers */
17enum NODE_STATUS { BAD, SEENB_HEARDG, SEENG, USED };
18
19/*
20 * Module to store currently unused ID <=> IP associations
21 * for a potential future use
22 */
23
24typedef struct Assoc Assoc;
25
26/*****************************************************************************/
27
28/* custom distance handler, if it's not ID-distance based
29 * return values exactly like id_closest() */
30typedef int (*Assoc_distance_relative_callback)(const Assoc *assoc, void *callback_data, const uint8_t *client_id,
31 const uint8_t *client_id1, const uint8_t *client_id2);
32
33#define DISTANCE_INDEX_DISTANCE_BITS 44
34
35/* absolute distance: can be same for different client_id_check values
36 * return value should have DISTANCE_INDEX_DISTANCE_BITS valid bits */
37typedef uint64_t (*Assoc_distance_absolute_callback)(const Assoc *assoc, void *callback_data,
38 const uint8_t *client_id_ref, const uint8_t *client_id_check);
39
40/*****************************************************************************/
41
42/* Central entry point for new associations: add a new candidate to the cache
43 * returns 1 if entry is stored, 2 if existing entry was updated, 0 else */
44uint8_t Assoc_add_entry(Assoc *assoc, const uint8_t *id, const IPPTs *ippts_send, const IP_Port *ipp_recv,
45 uint8_t used);
46
47/*****************************************************************************/
48
49typedef enum AssocCloseEntriesFlags {
50 ProtoIPv4 = 1,
51 ProtoIPv6 = 2,
52 LANOk = 4,
53} AssocCloseEntriesFlags;
54
55typedef struct Assoc_close_entries {
56 void *custom_data; /* given to distance functions */
57 const uint8_t *wanted_id; /* the target client_id */
58 uint8_t flags; /* additional flags */
59
60 Assoc_distance_relative_callback distance_relative_func;
61 Assoc_distance_absolute_callback distance_absolute_func;
62
63 uint8_t count_good; /* that many should be "good" w.r.t. timeout */
64 uint8_t count; /* allocated number of close_indices */
65 Client_data **result;
66} Assoc_close_entries;
67
68/* find up to close_count nodes to put into close_nodes_used of ID_Nodes
69 * the distance functions can be NULL, then standard distance functions will be used
70 * the caller is responsible for allocating close_indices of sufficient size
71 *
72 * returns 0 on error
73 * returns the number of found nodes and the list of indices usable by Assoc_client()
74 * the caller is assumed to be registered from Assoc_register_callback()
75 * if they aren't, they should copy the Client_data and call Assoc_client_drop()
76 */
77uint8_t Assoc_get_close_entries(Assoc *assoc, Assoc_close_entries *state);
78
79/*****************************************************************************/
80
81/* create: default sizes (6, 5 => 320 entries) */
82Assoc *new_Assoc_default(Logger *log, const uint8_t *public_id);
83
84/* create: customized sizes
85 * total is (2^bits) * entries
86 * bits should be between 2 and 15 (else it's trimmed)
87 * entries will be reduced to the closest prime smaller or equal
88 *
89 * preferably bits should be large and entries small to ensure spread
90 * in the search space (e. g. 5, 5 is preferable to 2, 41) */
91Assoc *new_Assoc(Logger *log, size_t bits, size_t entries, const uint8_t *public_id);
92
93/* public_id changed (loaded), update which entry isn't stored */
94void Assoc_self_client_id_changed(Assoc *assoc, const uint8_t *id);
95
96/* every 45s send out a getnodes() for a "random" bucket */
97#define ASSOC_BUCKET_REFRESH 45
98
99/* refresh bucket's data from time to time
100 * this must be called only from DHT */
101void do_Assoc(Assoc *assoc, DHT *dht);
102
103/* destroy */
104void kill_Assoc(Assoc *assoc);
105
106void Assoc_status(Logger *log, const Assoc *assoc);
107
108#endif /* !ASSOC_H */
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-08 07:50:12 +0000