summaryrefslogtreecommitdiff
path: root/toxcore/assoc.c
diff options
context:
space:
mode:
Diffstat (limited to 'toxcore/assoc.c')
-rw-r--r--toxcore/assoc.c926
1 files changed, 926 insertions, 0 deletions
diff --git a/toxcore/assoc.c b/toxcore/assoc.c
new file mode 100644
index 00000000..4dc91671
--- /dev/null
+++ b/toxcore/assoc.c
@@ -0,0 +1,926 @@
1
2#ifdef HAVE_CONFIG_H
3#include "config.h"
4#endif
5
6#include "DHT.h"
7#include "assoc.h"
8#include "ping.h"
9
10#include "LAN_discovery.h"
11
12#include <assert.h>
13#include "util.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 inital 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 used_at;
69 uint64_t seen_at;
70 uint64_t heard_at;
71
72 uint16_t seen_family;
73 uint16_t heard_family;
74
75 IP_Port assoc_heard4;
76 IP_Port assoc_heard6;
77
78 Client_data client;
79} Client_entry;
80
81typedef struct candidates_bucket {
82 Client_entry *list; /* hashed list */
83} candidates_bucket;
84
85struct Assoc {
86 hash_t self_hash; /* hash of self_client_id */
87 uint8_t self_client_id[CLIENT_ID_SIZE]; /* don't store entries for this */
88
89 /* association centralization: clients not in use */
90 size_t candidates_bucket_bits;
91 size_t candidates_bucket_count;
92 size_t candidates_bucket_size;
93 candidates_bucket *candidates;
94};
95
96/*****************************************************************************/
97/* HELPER FUNCTIONS */
98/*****************************************************************************/
99
100/* the complete distance would be CLIENT_ID_SIZE long...
101 * returns DISTANCE_INDEX_DISTANCE_BITS valid bits */
102static uint64_t id_distance(Assoc *assoc, void *callback_data, uint8_t *id_ref, uint8_t *id_test)
103{
104 /* with BIG_ENDIAN, this would be a one-liner... */
105 uint64_t retval = 0;
106
107 uint8_t pos = 0, bits = DISTANCE_INDEX_DISTANCE_BITS;
108
109 while (bits > 8) {
110 uint8_t distance = abs((int8_t)id_ref[pos] ^ (int8_t)id_test[pos]);
111 retval = (retval << 8) | distance;
112 bits -= 8;
113 pos++;
114 }
115
116 return (retval << bits) | ((id_ref[pos] ^ id_test[pos]) >> (8 - bits));
117}
118
119/* qsort() callback for a sorting by id_distance() values */
120static int dist_index_comp(const void *a, const void *b)
121{
122 const uint64_t *_a = a;
123 const uint64_t *_b = b;
124
125 if (*_a < *_b)
126 return -1;
127
128 if (*_a > *_b)
129 return 1;
130
131 return 0;
132}
133
134/* get actual entry to a distance_index */
135static Client_entry *dist_index_entry(Assoc *assoc, uint64_t dist_ind)
136{
137 if ((dist_ind & DISTANCE_INDEX_INDEX_MASK) == DISTANCE_INDEX_INDEX_MASK)
138 return NULL;
139
140 size_t total = assoc->candidates_bucket_count * assoc->candidates_bucket_size;
141 uint32_t index = dist_ind & DISTANCE_INDEX_INDEX_MASK;
142
143 if (index < total) {
144 bucket_t b_id = index / assoc->candidates_bucket_size;
145 candidates_bucket *cnd_bckt = &assoc->candidates[b_id];
146 size_t b_ix = index % assoc->candidates_bucket_size;
147 Client_entry *entry = &cnd_bckt->list[b_ix];
148
149 if (entry->hash)
150 return entry;
151 }
152
153 return NULL;
154}
155
156/* get actual entry's client_id to a distance_index */
157static uint8_t *dist_index_id(Assoc *assoc, uint64_t dist_ind)
158{
159 Client_entry *entry = dist_index_entry(assoc, dist_ind);
160
161 if (entry)
162 return entry->client.client_id;
163
164 return NULL;
165}
166
167/* sorts first .. last, i.e. last is included */
168static void dist_index_bubble(Assoc *assoc, uint64_t *dist_list, size_t first, size_t last, uint8_t *id,
169 void *custom_data, Assoc_distance_relative_callback dist_rel_func)
170{
171 size_t i, k;
172
173 for (i = first; i <= last; i++) {
174 uint8_t *id1 = dist_index_id(assoc, dist_list[i]);
175
176 for (k = i + 1; k <= last; k++) {
177 uint8_t *id2 = dist_index_id(assoc, dist_list[k]);
178
179 if (id1 && id2)
180 if (dist_rel_func(assoc, custom_data, id, id1, id2) == 2) {
181 uint64_t swap = dist_list[i];
182 dist_list[i] = dist_list[k];
183 dist_list[k] = swap;
184 }
185 }
186 }
187}
188
189/* TODO: Check that there isn't a function like this elsewhere hidden.
190 * E.g. the one which creates a handshake_id isn't usable for this, it must
191 * always map the same ID to the same hash.
192 *
193 * Result is NOT MAPPED to CANDIDATES_TO_KEEP range, i.e. map before using
194 * it for list access. */
195static hash_t id_hash(Assoc *assoc, uint8_t *id)
196{
197 uint32_t i, res = 0x19a64e82;
198
199 for (i = 0; i < CLIENT_ID_SIZE; i++)
200 res = ((res << 1) ^ id[i]) + (res >> 31);
201
202 /* can't have zero as hash, a) marks an unused spot,
203 * b) collision function is multiplicative */
204 if (!(res % assoc->candidates_bucket_size))
205 res++;
206
207 return res;
208}
209
210/* up to HASH_COLLIDE_COUNT calls to different spots,
211 * result IS mapped to CANDIDATES_TO_KEEP range */
212static hash_t hash_collide(Assoc *assoc, hash_t hash)
213{
214 uint64_t hash64 = hash % assoc->candidates_bucket_size;
215 hash64 = (hash64 * HASH_COLLIDE_PRIME) % assoc->candidates_bucket_size;
216
217 hash_t retval = hash64;
218
219 /* this should never happen when CANDIDATES_TO_KEEP is prime and hash not a multiple
220 * (id_hash() checks for a multiple and returns a different hash in that case)
221 *
222 * ( 1 .. (prime - 1) is a group over multiplication and every number has its inverse
223 * in the group, so no multiplication should ever end on zero as long neither
224 * of the two factors was zero-equivalent )
225 *
226 * BUT: because the usage of the word "never" invokes Murphy's law, catch it */
227 if (!retval) {
228#ifdef DEBUG
229 fprintf(stderr, "assoc::hash_collide: hash %u, bucket size %u => %u!", hash, (uint)assoc->candidates_bucket_size,
230 retval);
231 assert(retval != 0);
232#endif
233 retval = 1;
234 }
235
236 return retval;
237}
238
239/* returns the "seen" assoc related to the ipp */
240static IPPTsPng *entry_assoc(Client_entry *cl_entry, IP_Port *ipp)
241{
242 if (!cl_entry)
243 return NULL;
244
245 if (ipp->ip.family == AF_INET)
246 return &cl_entry->client.assoc4;
247
248 if (ipp->ip.family == AF_INET6)
249 return &cl_entry->client.assoc6;
250
251 return NULL;
252}
253
254/* returns the "heard" assoc related to the ipp */
255static IP_Port *entry_heard_get(Client_entry *entry, IP_Port *ipp)
256{
257 if (ipp->ip.family == AF_INET)
258 return &entry->assoc_heard4;
259 else if (ipp->ip.family == AF_INET6)
260 return &entry->assoc_heard6;
261 else
262 return NULL;
263}
264
265/* store a "heard" entry
266 * overwrites empty entry, does NOT overwrite non-LAN ip with
267 * LAN ip
268 *
269 * returns 1 if the entry did change */
270static int entry_heard_store(Client_entry *entry, IPPTs *ippts)
271{
272 if (!entry || !ippts)
273 return 0;
274
275 if (!ipport_isset(&ippts->ip_port))
276 return 0;
277
278 IP_Port *heard, *ipp = &ippts->ip_port;
279
280 if (ipp->ip.family == AF_INET)
281 heard = &entry->assoc_heard4;
282 else if (ipp->ip.family == AF_INET6)
283 heard = &entry->assoc_heard6;
284 else
285 return 0;
286
287 if (ipport_equal(ipp, heard))
288 return 0;
289
290 if (!ipport_isset(heard)) {
291 *heard = *ipp;
292 entry->heard_at = ippts->timestamp;
293 entry->heard_family = ipp->ip.family;
294 return 1;
295 }
296
297 /* don't destroy a good address with a crappy one
298 * (unless we're very timed out) */
299 uint8_t LAN_ipp = LAN_ip(ipp->ip) == 0;
300 uint8_t LAN_entry = LAN_ip(heard->ip) == 0;
301
302 if (LAN_ipp && !LAN_entry && !is_timeout(entry->heard_at, CANDIDATES_HEARD_TIMEOUT))
303 return 0;
304
305 *heard = *ipp;
306 entry->heard_at = ippts->timestamp;
307 entry->heard_family = ipp->ip.family;
308
309 return 1;
310}
311
312/* maps Assoc callback signature to id_closest() */
313static int assoc_id_closest(Assoc *assoc, void *callback_data, uint8_t *client_id, uint8_t *client_id1,
314 uint8_t *client_id2)
315{
316 return id_closest(client_id, client_id1, client_id2);
317}
318
319static bucket_t id_bucket(uint8_t *id, uint8_t bits)
320{
321 /* return the first "bits" bits of id */
322 bucket_t retval = 0;
323
324 uint8_t pos = 0;
325
326 while (bits > 8) {
327 retval = (retval << 8) | id[pos++];
328 bits -= 8;
329 }
330
331 return (retval << bits) | (id[pos] >> (8 - bits));
332}
333
334/*****************************************************************************/
335/* CANDIDATES FUNCTIONS */
336/*****************************************************************************/
337
338
339static bucket_t candidates_id_bucket(Assoc *assoc, uint8_t *id)
340{
341 return id_bucket(id, assoc->candidates_bucket_bits);
342}
343
344static uint8_t candidates_search(Assoc *assoc, uint8_t *id, hash_t hash, Client_entry **entryptr)
345{
346 bucket_t bucket = candidates_id_bucket(assoc, id);
347 candidates_bucket *cnd_bckt = &assoc->candidates[bucket];
348 size_t coll, pos = hash % assoc->candidates_bucket_size;
349
350 for (coll = 0; coll < HASH_COLLIDE_COUNT; pos = hash_collide(assoc, pos) , coll++) {
351 Client_entry *entry = &cnd_bckt->list[pos];
352
353 if (entry->hash == hash)
354 if (id_equal(entry->client.client_id, id)) {
355 *entryptr = entry;
356 return 1;
357 }
358 }
359
360 *entryptr = NULL;
361 return 0;
362}
363
364static void candidates_update_assoc(Assoc *assoc, Client_entry *entry, uint8_t used, IPPTs *ippts_send,
365 IP_Port *ipp_recv)
366{
367 if (!assoc || !entry || !ippts_send)
368 return;
369
370 IPPTsPng *ipptsp = entry_assoc(entry, &ippts_send->ip_port);
371
372 if (!ipptsp)
373 return;
374
375 if (used)
376 entry->used_at = unix_time();
377
378 /* do NOT do anything related to wanted, that's handled outside,
379 * just update the assoc (in the most sensible way)
380 */
381 if (ipp_recv) {
382 ipptsp->ip_port = ippts_send->ip_port;
383 ipptsp->timestamp = ippts_send->timestamp;
384 ipptsp->ret_ip_port = *ipp_recv;
385 ipptsp->ret_timestamp = unix_time();
386
387 entry->seen_at = unix_time();
388 entry->seen_family = ippts_send->ip_port.ip.family;
389
390 return;
391 }
392
393 entry_heard_store(entry, ippts_send);
394}
395
396static uint8_t candidates_create_internal(Assoc *assoc, hash_t hash, uint8_t *id, uint8_t seen,
397 uint8_t used, bucket_t *bucketptr, size_t *posptr)
398{
399 if (!assoc || !id || !bucketptr || !posptr)
400 return 0;
401
402 bucket_t bucket = candidates_id_bucket(assoc, id);
403 candidates_bucket *cnd_bckt = &assoc->candidates[bucket];
404
405 size_t coll, pos = hash % assoc->candidates_bucket_size, check;
406 size_t pos_check[6];
407
408 memset(pos_check, 0, sizeof(pos_check));
409
410 for (coll = 0; coll < HASH_COLLIDE_COUNT; pos = hash_collide(assoc, pos) , coll++) {
411 Client_entry *entry = &cnd_bckt->list[pos];
412
413 /* unset */
414 if (!entry->hash) {
415 *bucketptr = bucket;
416 *posptr = pos;
417
418 return 1;
419 }
420
421 /* 0. bad
422 * 1. seen bad, heard good
423 * 2. seen good
424 * 3. used */
425 if (!is_timeout(entry->used_at, BAD_NODE_TIMEOUT))
426 check = 3;
427
428 if (!is_timeout(entry->seen_at, CANDIDATES_SEEN_TIMEOUT))
429 check = 2;
430 else if (!is_timeout(entry->heard_at, CANDIDATES_HEARD_TIMEOUT))
431 check = 1;
432 else
433 check = 0;
434
435 if (!pos_check[check])
436 pos_check[check] = pos + 1;
437 }
438
439 /* used > seen > heard > bad */
440 size_t i, pos_max = used ? 3 : (seen ? 2 : 1);
441
442 for (i = 0; i < pos_max; i++)
443 if (pos_check[i]) {
444 *bucketptr = bucket;
445 *posptr = pos_check[i] - 1;
446
447 return 1;
448 }
449
450 return 0;
451}
452
453static uint8_t candidates_create_new(Assoc *assoc, hash_t hash, uint8_t *id, uint8_t used,
454 IPPTs *ippts_send, IP_Port *ipp_recv)
455{
456 if (!assoc || !id || !ippts_send)
457 return 0;
458
459 bucket_t bucket;
460 size_t pos;
461
462 if (!candidates_create_internal(assoc, hash, id, ipp_recv != NULL, used, &bucket, &pos))
463 return 0;
464
465 candidates_bucket *cnd_bckt = &assoc->candidates[bucket];
466 Client_entry *entry = &cnd_bckt->list[pos];
467 memset(entry, 0, sizeof(*entry));
468 IPPTsPng *ipptsp = entry_assoc(entry, &ippts_send->ip_port);
469
470 if (!ipptsp)
471 return 0;
472
473 entry->hash = hash;
474 id_copy(entry->client.client_id, id);
475
476 if (used)
477 entry->used_at = unix_time();
478
479 if (ipp_recv && !ipport_isset(ipp_recv))
480 ipp_recv = NULL;
481
482 if (ipp_recv) {
483 entry->seen_at = ippts_send->timestamp;
484 entry->seen_family = ippts_send->ip_port.ip.family;
485
486 ipptsp->ip_port = ippts_send->ip_port;
487 ipptsp->timestamp = ippts_send->timestamp;
488 ipptsp->ret_ip_port = *ipp_recv;
489 ipptsp->ret_timestamp = unix_time();
490 } else {
491 IP_Port *heard = entry_heard_get(entry, &ippts_send->ip_port);
492
493 if (heard) {
494 entry->heard_at = ippts_send->timestamp;
495 entry->heard_family = ippts_send->ip_port.ip.family;
496
497 *heard = ippts_send->ip_port;
498 }
499 }
500
501 return 1;
502}
503
504/*****************************************************************************/
505
506static void client_id_self_update(Assoc *assoc)
507{
508 if (assoc->self_hash || !assoc->self_client_id)
509 return;
510
511 if (!assoc->self_hash) {
512 size_t i, sum = 0;
513
514 for (i = 0; i < crypto_box_PUBLICKEYBYTES; i++)
515 sum |= assoc->self_client_id[i];
516
517 if (!sum)
518 return;
519
520 assoc->self_hash = id_hash(assoc, assoc->self_client_id);
521 }
522
523#ifdef LOGGING
524 loglog("assoc: id is now set, purging cache of self-references...\n");
525#endif
526
527 /* if we already added some (or loaded some) entries,
528 * look and remove if we find a match
529 */
530 bucket_t b_id = candidates_id_bucket(assoc, assoc->self_client_id);
531 candidates_bucket *cnd_bckt = &assoc->candidates[b_id];
532 size_t i, pos = assoc->self_hash % assoc->candidates_bucket_size;
533
534 for (i = 0; i < HASH_COLLIDE_COUNT; pos = hash_collide(assoc, pos), i++) {
535 Client_entry *entry = &cnd_bckt->list[pos];
536
537 if (entry->hash == assoc->self_hash)
538 if (id_equal(entry->client.client_id, assoc->self_client_id))
539 entry->hash = 0;
540 }
541}
542
543/*****************************************************************************/
544/* TRIGGER FUNCTIONS */
545/*****************************************************************************/
546
547/* Central entry point for new associations: add a new candidate to the cache
548 * seen should be 0 (zero), if the candidate was announced by someone else,
549 * seen should be 1 (one), if there is confirmed connectivity (a definite response)
550 */
551uint8_t Assoc_add_entry(Assoc *assoc, uint8_t *id, IPPTs *ippts_send, IP_Port *ipp_recv, uint8_t used)
552{
553 if (!assoc || !id || !ippts_send)
554 return 0;
555
556 if (!assoc->self_hash) {
557 client_id_self_update(assoc);
558
559 if (!assoc->self_hash)
560 return 0;
561 }
562
563 if (!ipport_isset(&ippts_send->ip_port))
564 return 0;
565
566 if (ipp_recv && !ipport_isset(ipp_recv))
567 ipp_recv = NULL;
568
569 hash_t hash = id_hash(assoc, id);
570
571 if (hash == assoc->self_hash)
572 if (id_equal(id, assoc->self_client_id))
573 return 0;
574
575 /* if it's new:
576 * callback, if there's desire, add to clients, else to candidates
577 *
578 * if it's "old":
579 * if it's client: refresh
580 * if it's candidate:
581 * if !ipp_recv, refresh
582 * if ipp_recv: callback, if there's desire, move to candidates
583 */
584 Client_entry *cnd_entry;
585
586 if (!candidates_search(assoc, id, hash, &cnd_entry)) {
587 if (candidates_create_new(assoc, hash, id, used, ippts_send, ipp_recv))
588 return 1;
589 else
590 return 0;
591 } else {
592 candidates_update_assoc(assoc, cnd_entry, used, ippts_send, ipp_recv);
593 return 2;
594 }
595}
596
597/*****************************************************************************/
598/* MAIN USE */
599/*****************************************************************************/
600
601uint8_t Assoc_get_close_entries(Assoc *assoc, Assoc_close_entries *state)
602{
603 if (!assoc || !state || !state->wanted_id || !state->result)
604 return 0;
605
606 if (!assoc->self_hash) {
607 client_id_self_update(assoc);
608
609 if (!assoc->self_hash)
610 return 0;
611 }
612
613 if (!state->distance_relative_func)
614 state->distance_relative_func = assoc_id_closest;
615
616 if (!state->distance_absolute_func)
617 state->distance_absolute_func = id_distance;
618
619 size_t dist_list_len = assoc->candidates_bucket_count * assoc->candidates_bucket_size;
620 uint64_t dist_list[dist_list_len];
621 memset(dist_list, ~0, dist_list_len * sizeof(dist_list[0]));
622 bucket_t b;
623 size_t i;
624
625 for (b = 0; b < assoc->candidates_bucket_count; b++) {
626 candidates_bucket *cnd_bckt = &assoc->candidates[b];
627
628 for (i = 0; i < assoc->candidates_bucket_size; i++) {
629 Client_entry *entry = &cnd_bckt->list[i];
630
631 if (entry->hash) {
632 if (state->flags & ProtoIPv4) {
633 if (!ipport_isset(&entry->client.assoc4.ip_port))
634 continue;
635
636 if (!(state->flags & LANOk))
637 if (!LAN_ip(entry->client.assoc4.ip_port.ip))
638 continue;
639 }
640
641 if (state->flags & ProtoIPv6) {
642 if (!ipport_isset(&entry->client.assoc6.ip_port))
643 continue;
644
645 if (!(state->flags & LANOk))
646 if (!LAN_ip(entry->client.assoc6.ip_port.ip))
647 continue;
648 }
649
650 uint64_t dist = state->distance_absolute_func(assoc, state->custom_data, state->wanted_id, entry->client.client_id);
651 uint32_t index = b * assoc->candidates_bucket_size + i;
652 dist_list[index] = (dist << DISTANCE_INDEX_INDEX_BITS) | index;
653 }
654 }
655 }
656
657 qsort(dist_list, dist_list_len, sizeof(dist_list[0]), dist_index_comp);
658
659 /* ok, ok, it's not *perfectly* sorted, because we used an absolute distance
660 * go over the result and see if we need to "smoothen things out"
661 * because those should be only very few and short streaks, the worst regularly
662 * used sorting function aka bubble sort is used */
663 uint64_t dist_prev = ~0;
664 size_t ind_prev = ~0, ind_curr;
665 size_t len = 1;
666
667 for (ind_curr = 0; ind_curr < dist_list_len; ind_curr++) {
668 /* sorted increasingly, so an invalid entry marks the end */
669 if ((dist_list[ind_curr] & DISTANCE_INDEX_INDEX_MASK) == DISTANCE_INDEX_INDEX_MASK)
670 break;
671
672 uint64_t dist_curr = dist_list[ind_curr] >> DISTANCE_INDEX_INDEX_BITS;
673
674 if (dist_prev == dist_curr)
675 len++;
676 else {
677 if (len > 1)
678 dist_index_bubble(assoc, dist_list, ind_prev, ind_curr - 1, state->wanted_id, state->custom_data,
679 state->distance_relative_func);
680
681 dist_prev = dist_curr;
682 ind_prev = ind_curr;
683 len = 1;
684 }
685 }
686
687 if (len > 1)
688 dist_index_bubble(assoc, dist_list, ind_prev, ind_curr - 1, state->wanted_id, state->custom_data,
689 state->distance_relative_func);
690
691 /* ok, now dist_list is a strictly ascending sorted list of nodes
692 * a) extract CLOSE_QUOTA_USED clients, not timed out
693 * b) extract (1 - QUOTA) (better!) clients & candidates, not timed out
694 * c) save candidates which would be better, if contact can be established */
695 size_t client_quota_good = 0, pos = 0;
696 size_t client_quota_max = state->count_good;
697
698 ssize_t taken_last = - 1;
699
700 for (i = 0; (i < dist_list_len) && (pos < state->count); i++) {
701 Client_entry *entry = dist_index_entry(assoc, dist_list[i]);
702
703 if (entry && entry->hash) {
704 if (client_quota_good >= client_quota_max) {
705 state->result[pos++] = &entry->client;
706 taken_last = i;
707 } else {
708 if (state->flags & (ProtoIPv4 | ProtoIPv6)) {
709 if ((state->flags & ProtoIPv4) && is_timeout(entry->client.assoc4.timestamp, BAD_NODE_TIMEOUT))
710 continue;
711
712 if ((state->flags & ProtoIPv6) && is_timeout(entry->client.assoc6.timestamp, BAD_NODE_TIMEOUT))
713 continue;
714 } else if (is_timeout(entry->seen_at, BAD_NODE_TIMEOUT))
715 continue;
716
717 state->result[pos++] = &entry->client;
718 client_quota_good++;
719 taken_last = i;
720 }
721 }
722 }
723
724 /* if we had not enough valid entries the list might still not be filled.
725 *
726 * start again from last taken client, but leave out any requirement
727 */
728 if (pos < state->count) {
729 for (i = taken_last + 1; (i < dist_list_len) && (pos < state->count); i++) {
730 Client_entry *entry = dist_index_entry(assoc, dist_list[i]);
731
732 if (entry && entry->hash)
733 state->result[pos++] = &entry->client;
734 }
735 }
736
737 return pos;
738}
739
740/*****************************************************************************/
741/* GLOBAL STRUCTURE FUNCTIONS */
742/*****************************************************************************/
743
744static uint8_t odd_min9_is_prime(size_t value)
745{
746 size_t i = 3;
747
748 while (i * i <= value) {
749 if (!(value % i))
750 return 0;
751
752 i += 2;
753 }
754
755 return 1;
756}
757
758static size_t prime_upto_min9(size_t limit)
759{
760 /* even => odd */
761 limit = limit - (1 - (limit % 2));
762
763 while (!odd_min9_is_prime(limit))
764 limit -= 2;
765
766 return limit;
767}
768
769/* create */
770Assoc *new_Assoc(size_t bits, size_t entries, uint8_t *public_id)
771{
772 if (!public_id)
773 return NULL;
774
775 Assoc *assoc = calloc(1, sizeof(*assoc));
776
777 if (!assoc)
778 return NULL;
779
780 /*
781 * bits must be in [ 2 .. 15 ]
782 * entries must be a prime
783 */
784 if (bits < 2)
785 bits = 2;
786 else if (bits > 15)
787 bits = 15;
788
789 assoc->candidates_bucket_bits = bits;
790 assoc->candidates_bucket_count = 1U << bits;
791
792 if (entries < 25) {
793 if (entries <= 6)
794 entries = 5;
795 else {
796 entries = entries - (1 - (entries % 2)); /* even => odd */
797
798 /* 7..23: all odds but 9&15 are prime */
799 if (!(entries % 3)) /* 9, 15 */
800 entries -= 2; /* 7, 13 */
801 }
802 } else if (entries > ((1 << 17) - 1)) /* 130k+ */
803 entries = (1 << 17) - 1;
804 else {
805 /* 9+: test and find a prime less or equal */
806 size_t entries_test = prime_upto_min9(entries);
807
808 if (entries_test == HASH_COLLIDE_PRIME) /* disallowed */
809 entries_test = prime_upto_min9(entries_test - 1);
810
811 if (entries_test != entries) {
812#ifdef LOGGING
813 sprintf(logbuffer, "new_Assoc(): trimmed %i to %i.\n", (int)entries, (int)entries_test);
814 loglog(logbuffer);
815#endif
816 entries = (size_t)entries_test;
817 }
818 }
819
820 assoc->candidates_bucket_size = entries;
821
822 /* allocation: preferably few blobs */
823 size_t bckt, cix;
824 Client_entry *clients = malloc(sizeof(*clients) * assoc->candidates_bucket_count * assoc->candidates_bucket_size);
825 candidates_bucket *lists = malloc(sizeof(*lists) * assoc->candidates_bucket_count);
826
827 for (bckt = 0; bckt < assoc->candidates_bucket_count; bckt++) {
828 candidates_bucket *list = &lists[bckt];
829
830 list->list = &clients[bckt * assoc->candidates_bucket_size];
831
832 for (cix = 0; cix < assoc->candidates_bucket_size; cix++)
833 list->list[cix].hash = 0;
834 }
835
836 assoc->candidates = lists;
837
838 id_copy(assoc->self_client_id, public_id);
839 client_id_self_update(assoc);
840
841 return assoc;
842}
843
844Assoc *new_Assoc_default(uint8_t *public_id)
845{
846 /* original 8, 251 averages to ~32k entries... probably the whole DHT :D
847 * 320 entries is fine, hopefully */
848 return new_Assoc(6, 15, public_id);
849}
850
851/* own client_id, assocs for this have to be ignored */
852void Assoc_self_client_id_changed(Assoc *assoc, uint8_t *id)
853{
854 if (assoc && id) {
855 assoc->self_hash = 0;
856 id_copy(assoc->self_client_id, id);
857 client_id_self_update(assoc);
858 }
859}
860
861/* destroy */
862void kill_Assoc(Assoc *assoc)
863{
864 if (assoc) {
865 free(assoc->candidates->list);
866 free(assoc->candidates);
867 free(assoc);
868 }
869}
870
871#ifdef LOGGING
872
873static char buffer[CLIENT_ID_SIZE * 2 + 1];
874static char *idpart2str(uint8_t *id, size_t len)
875{
876 if (len > CLIENT_ID_SIZE)
877 len = CLIENT_ID_SIZE;
878
879 size_t i;
880
881 for (i = 0; i < len; i++)
882 sprintf(buffer + i * 2, "%02hhx", id[i]);
883
884 buffer[len * 2] = 0;
885 return buffer;
886}
887
888void Assoc_status(Assoc *assoc)
889{
890 if (!assoc) {
891 loglog("Assoc status: no assoc\n");
892 return;
893 }
894
895 loglog("[b:p] hash => [id...] used, seen, heard\n");
896
897 size_t bid, cid, total = 0;
898
899 for (bid = 0; bid < assoc->candidates_bucket_count; bid++) {
900 candidates_bucket *bucket = &assoc->candidates[bid];
901
902 for (cid = 0; cid < assoc->candidates_bucket_size; cid++) {
903 Client_entry *entry = &bucket->list[cid];
904
905 if (entry->hash) {
906 sprintf(logbuffer, "[%3i:%3i] %08x => [%s...] %i, %i(%c), %i(%c)\n",
907 (int)bid, (int)cid, entry->hash, idpart2str(entry->client.client_id, 8),
908 entry->used_at ? (int)(unix_time() - entry->used_at) : 0,
909 entry->seen_at ? (int)(unix_time() - entry->seen_at) : 0,
910 entry->seen_at ? (entry->seen_family == AF_INET ? '4' : (entry->seen_family == AF_INET6 ? '6' : '?')) : '?',
911 entry->heard_at ? (int)(unix_time() - entry->heard_at) : 0,
912 entry->heard_at ? (entry->heard_family == AF_INET ? '4' : (entry->heard_family == AF_INET6 ? '6' : '?')) : '?');
913 loglog(logbuffer);
914 total++;
915 }
916 }
917 }
918
919 if (total) {
920 sprintf(logbuffer, "Total: %i entries, table usage %i%%.\n", (int)total,
921 (int)(total * 100 / (assoc->candidates_bucket_count * assoc->candidates_bucket_size)));
922 loglog(logbuffer);
923 }
924}
925
926#endif
generated by cgit v1.2.3 (git 2.39.1) at 2024-09-29 16:18:09 +0000