summaryrefslogtreecommitdiff
path: root/toxcore/assoc.c
diff options
context:
space:
mode:
Diffstat (limited to 'toxcore/assoc.c')
-rw-r--r--toxcore/assoc.c1109
1 files changed, 0 insertions, 1109 deletions
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}
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-18 13:06:38 +0000