diff options
Diffstat (limited to 'toxcore')
-rw-r--r-- | toxcore/DHT.c | 105 | ||||
-rw-r--r-- | toxcore/DHT.h | 4 | ||||
-rw-r--r-- | toxcore/Makefile.inc | 2 | ||||
-rw-r--r-- | toxcore/Messenger.c | 6 | ||||
-rw-r--r-- | toxcore/assoc.c | 1109 | ||||
-rw-r--r-- | toxcore/assoc.h | 108 |
6 files changed, 1 insertions, 1333 deletions
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 | ||
832 | static uint8_t cmp_public_key[crypto_box_PUBLICKEYBYTES]; | 776 | static 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 | ||
1226 | end: | 1158 | end: |
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 | ||
1789 | void DHT_bootstrap(DHT *dht, IP_Port ip_port, const uint8_t *public_key) | 1709 | void 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 | } |
1803 | int DHT_bootstrap_from_address(DHT *dht, const char *address, uint8_t ipv6enabled, | 1713 | int 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 | } |
2750 | void kill_DHT(DHT *dht) | 2650 | void 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); | |||
456 | int addto_lists(DHT *dht, IP_Port ip_port, const uint8_t *public_key); | 453 | int 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 */ | ||
53 | typedef uint16_t bucket_t; | ||
54 | typedef uint32_t hash_t; | ||
55 | typedef uint16_t usecnt_t; | ||
56 | |||
57 | /* abbreviations ... */ | ||
58 | typedef Assoc_distance_relative_callback dist_rel_cb; | ||
59 | typedef Assoc_distance_absolute_callback dist_abs_cb; | ||
60 | |||
61 | /* | ||
62 | * Client_data wrapped with additional data | ||
63 | */ | ||
64 | typedef 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 | |||
83 | typedef struct candidates_bucket { | ||
84 | Client_entry *list; /* hashed list */ | ||
85 | } candidates_bucket; | ||
86 | |||
87 | struct 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 */ | ||
106 | static 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 */ | ||
124 | static 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 */ | ||
141 | static 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 */ | ||
165 | static 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 */ | ||
177 | static 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. */ | ||
205 | static 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 */ | ||
224 | static 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 */ | ||
252 | static 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 */ | ||
270 | static 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 */ | ||
288 | static 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() */ | ||
337 | static 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 | |||
343 | static 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 | |||
363 | static bucket_t candidates_id_bucket(const Assoc *assoc, const uint8_t *id) | ||
364 | { | ||
365 | return id_bucket(id, assoc->candidates_bucket_bits); | ||
366 | } | ||
367 | |||
368 | static 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 | |||
389 | static 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 | |||
424 | static 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 | |||
485 | static 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 | |||
543 | static 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 | */ | ||
589 | uint8_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 | |||
646 | uint8_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 | |||
816 | static 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 | |||
831 | static 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 */ | ||
844 | Assoc *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 | |||
938 | Assoc *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 */ | ||
946 | void 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 | |||
955 | static char *idpart2str(uint8_t *id, size_t len); | ||
956 | |||
957 | /* refresh buckets */ | ||
958 | void 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 */ | ||
1048 | void kill_Assoc(Assoc *assoc) | ||
1049 | { | ||
1050 | if (assoc) { | ||
1051 | free(assoc->candidates->list); | ||
1052 | free(assoc->candidates); | ||
1053 | free(assoc); | ||
1054 | } | ||
1055 | } | ||
1056 | |||
1057 | static char buffer[crypto_box_PUBLICKEYBYTES * 2 + 1]; | ||
1058 | static 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 | |||
1074 | void 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 */ | ||
17 | enum 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 | |||
24 | typedef struct Assoc Assoc; | ||
25 | |||
26 | /*****************************************************************************/ | ||
27 | |||
28 | /* custom distance handler, if it's not ID-distance based | ||
29 | * return values exactly like id_closest() */ | ||
30 | typedef 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 */ | ||
37 | typedef 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 */ | ||
44 | uint8_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 | |||
49 | typedef enum AssocCloseEntriesFlags { | ||
50 | ProtoIPv4 = 1, | ||
51 | ProtoIPv6 = 2, | ||
52 | LANOk = 4, | ||
53 | } AssocCloseEntriesFlags; | ||
54 | |||
55 | typedef 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 | */ | ||
77 | uint8_t Assoc_get_close_entries(Assoc *assoc, Assoc_close_entries *state); | ||
78 | |||
79 | /*****************************************************************************/ | ||
80 | |||
81 | /* create: default sizes (6, 5 => 320 entries) */ | ||
82 | Assoc *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) */ | ||
91 | Assoc *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 */ | ||
94 | void 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 */ | ||
101 | void do_Assoc(Assoc *assoc, DHT *dht); | ||
102 | |||
103 | /* destroy */ | ||
104 | void kill_Assoc(Assoc *assoc); | ||
105 | |||
106 | void Assoc_status(Logger *log, const Assoc *assoc); | ||
107 | |||
108 | #endif /* !ASSOC_H */ | ||