aboutsummaryrefslogtreecommitdiff
path: root/src/dht/gnunet-service-dht_neighbours.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/dht/gnunet-service-dht_neighbours.c')
-rw-r--r--src/dht/gnunet-service-dht_neighbours.c2695
1 files changed, 0 insertions, 2695 deletions
diff --git a/src/dht/gnunet-service-dht_neighbours.c b/src/dht/gnunet-service-dht_neighbours.c
deleted file mode 100644
index fde25936f..000000000
--- a/src/dht/gnunet-service-dht_neighbours.c
+++ /dev/null
@@ -1,2695 +0,0 @@
1/*
2 This file is part of GNUnet.
3 Copyright (C) 2009-2017, 2021, 2022 GNUnet e.V.
4
5 GNUnet is free software: you can redistribute it and/or modify it
6 under the terms of the GNU Affero General Public License as published
7 by the Free Software Foundation, either version 3 of the License,
8 or (at your option) any later version.
9
10 GNUnet is distributed in the hope that it will be useful, but
11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 Affero General Public License for more details.
14
15 You should have received a copy of the GNU Affero General Public License
16 along with this program. If not, see <http://www.gnu.org/licenses/>.
17
18 SPDX-License-Identifier: AGPL3.0-or-later
19 */
20
21/**
22 * @file dht/gnunet-service-dht_neighbours.c
23 * @brief GNUnet DHT service's bucket and neighbour management code
24 * @author Christian Grothoff
25 * @author Nathan Evans
26 */
27#include "platform.h"
28#include "gnunet_constants.h"
29#include "gnunet_protocols.h"
30#include "gnunet_signatures.h"
31#include "gnunet_hello_lib.h"
32#include "gnunet_hello_uri_lib.h"
33#include "gnunet-service-dht.h"
34#include "gnunet-service-dht_neighbours.h"
35#include "gnunet-service-dht_routing.h"
36#include "dht.h"
37
38#define LOG_TRAFFIC(kind, ...) GNUNET_log_from (kind, "dht-traffic", \
39 __VA_ARGS__)
40
41/**
42 * Enable slow sanity checks to debug issues.
43 *
44 * TODO: might want to eventually implement probabilistic
45 * load-based path verification, but for now it is all or nothing
46 * based on this define.
47 *
48 * 0: do not check -- if signatures become performance critical
49 * 1: check all external inputs -- normal production for now
50 * 2: check internal computations as well -- for debugging
51 */
52#define SANITY_CHECKS 2
53
54/**
55 * How many buckets will we allow in total.
56 */
57#define MAX_BUCKETS sizeof(struct GNUNET_HashCode) * 8
58
59/**
60 * What is the maximum number of peers in a given bucket.
61 */
62#define DEFAULT_BUCKET_SIZE 8
63
64/**
65 * Desired replication level for FIND PEER requests
66 */
67#define FIND_PEER_REPLICATION_LEVEL 4
68
69/**
70 * Maximum allowed number of pending messages per peer.
71 */
72#define MAXIMUM_PENDING_PER_PEER 64
73
74/**
75 * How long at least to wait before sending another find peer request.
76 * This is basically the frequency at which we will usually send out
77 * requests when we are 'perfectly' connected.
78 */
79#define DHT_MINIMUM_FIND_PEER_INTERVAL GNUNET_TIME_relative_multiply ( \
80 GNUNET_TIME_UNIT_MINUTES, 2)
81
82
83/**
84 * How long to additionally wait on average per #bucket_size to send out the
85 * FIND PEER requests if we did successfully connect (!) to a a new peer and
86 * added it to a bucket (as counted in #newly_found_peers). This time is
87 * Multiplied by 100 * newly_found_peers / bucket_size to get the new delay
88 * for finding peers (the #DHT_MINIMUM_FIND_PEER_INTERVAL is still added on
89 * top). Also the range in which we randomize, so the effective value
90 * is half of the number given here.
91 */
92#define DHT_AVG_FIND_PEER_INTERVAL GNUNET_TIME_relative_multiply ( \
93 GNUNET_TIME_UNIT_SECONDS, 6)
94
95/**
96 * How long at most to wait for transmission of a GET request to another peer?
97 */
98#define GET_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 2)
99
100
101GNUNET_NETWORK_STRUCT_BEGIN
102
103/**
104 * P2P PUT message
105 */
106struct PeerPutMessage
107{
108 /**
109 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_PUT
110 */
111 struct GNUNET_MessageHeader header;
112
113 /**
114 * Content type.
115 */
116 uint32_t type GNUNET_PACKED;
117
118 /**
119 * Processing options
120 */
121 uint16_t options GNUNET_PACKED;
122
123 /**
124 * Hop count
125 */
126 uint16_t hop_count GNUNET_PACKED;
127
128 /**
129 * Replication level for this message
130 */
131 uint16_t desired_replication_level GNUNET_PACKED;
132
133 /**
134 * Length of the PUT path that follows (if tracked).
135 */
136 uint16_t put_path_length GNUNET_PACKED;
137
138 /**
139 * When does the content expire?
140 */
141 struct GNUNET_TIME_AbsoluteNBO expiration_time;
142
143 /**
144 * Bloomfilter (for peer identities) to stop circular routes
145 */
146 char bloomfilter[DHT_BLOOM_SIZE];
147
148 /**
149 * The key we are storing under.
150 */
151 struct GNUNET_HashCode key;
152
153 /* put path (if tracked) */
154
155 /* Payload */
156};
157
158
159/**
160 * P2P Result message
161 */
162struct PeerResultMessage
163{
164 /**
165 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_RESULT
166 */
167 struct GNUNET_MessageHeader header;
168
169 /**
170 * Content type.
171 */
172 uint32_t type GNUNET_PACKED;
173
174 /**
175 * Reserved.
176 */
177 uint32_t reserved GNUNET_PACKED;
178
179 /**
180 * Length of the PUT path that follows (if tracked).
181 */
182 uint16_t put_path_length GNUNET_PACKED;
183
184 /**
185 * Length of the GET path that follows (if tracked).
186 */
187 uint16_t get_path_length GNUNET_PACKED;
188
189 /**
190 * When does the content expire?
191 */
192 struct GNUNET_TIME_AbsoluteNBO expiration_time;
193
194 /**
195 * The key of the corresponding GET request.
196 */
197 struct GNUNET_HashCode key;
198
199 /* put path (if tracked) */
200
201 /* get path (if tracked) */
202
203 /* Payload */
204};
205
206
207/**
208 * P2P GET message
209 */
210struct PeerGetMessage
211{
212 /**
213 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_GET
214 */
215 struct GNUNET_MessageHeader header;
216
217 /**
218 * Desired content type.
219 */
220 uint32_t type GNUNET_PACKED;
221
222 /**
223 * Processing options
224 */
225 uint16_t options GNUNET_PACKED;
226
227 /**
228 * Hop count
229 */
230 uint16_t hop_count GNUNET_PACKED;
231
232 /**
233 * Desired replication level for this request.
234 */
235 uint16_t desired_replication_level GNUNET_PACKED;
236
237 /**
238 * Size of the result filter.
239 */
240 uint16_t result_filter_size GNUNET_PACKED;
241
242 /**
243 * Bloomfilter (for peer identities) to stop circular routes
244 */
245 char bloomfilter[DHT_BLOOM_SIZE];
246
247 /**
248 * The key we are looking for.
249 */
250 struct GNUNET_HashCode key;
251
252 /* result bloomfilter */
253
254 /* xquery */
255
256};
257GNUNET_NETWORK_STRUCT_END
258
259
260/**
261 * Entry for a peer in a bucket.
262 */
263struct PeerInfo;
264
265
266/**
267 * List of targets that we can use to reach this peer.
268 */
269struct Target
270{
271 /**
272 * Kept in a DLL.
273 */
274 struct Target *next;
275
276 /**
277 * Kept in a DLL.
278 */
279 struct Target *prev;
280
281 /**
282 * Handle for sending messages to this peer.
283 */
284 struct GNUNET_DHTU_Target *utarget;
285
286 /**
287 * Underlay providing this target.
288 */
289 struct GDS_Underlay *u;
290
291 /**
292 * Peer this is a target for.
293 */
294 struct PeerInfo *pi;
295
296 /**
297 * Handle used to 'hold' the connection to this peer.
298 */
299 struct GNUNET_DHTU_PreferenceHandle *ph;
300
301 /**
302 * Set to number of messages are waiting for the transmission to finish.
303 */
304 unsigned int load;
305
306 /**
307 * Set to @a true if the target was dropped, but we could not clean
308 * up yet because @e busy was also true.
309 */
310 bool dropped;
311
312};
313
314
315/**
316 * Entry for a peer in a bucket.
317 */
318struct PeerInfo
319{
320 /**
321 * What is the identity of the peer?
322 */
323 struct GNUNET_PeerIdentity id;
324
325 /**
326 * Hash of @e id.
327 */
328 struct GNUNET_HashCode phash;
329
330 /**
331 * When does our HELLO from this peer expire?
332 */
333 struct GNUNET_TIME_Absolute hello_expiration;
334
335 /**
336 * Next peer entry (DLL)
337 */
338 struct PeerInfo *next;
339
340 /**
341 * Prev peer entry (DLL)
342 */
343 struct PeerInfo *prev;
344
345 /**
346 * Head of DLL of targets for this peer.
347 */
348 struct Target *t_head;
349
350 /**
351 * Tail of DLL of targets for this peer.
352 */
353 struct Target *t_tail;
354
355 /**
356 * Block with a HELLO of this peer.
357 */
358 void *hello;
359
360 /**
361 * Number of bytes in @e hello.
362 */
363 size_t hello_size;
364
365 /**
366 * Which bucket is this peer in?
367 */
368 int peer_bucket;
369};
370
371
372/**
373 * Peers are grouped into buckets.
374 */
375struct PeerBucket
376{
377 /**
378 * Head of DLL
379 */
380 struct PeerInfo *head;
381
382 /**
383 * Tail of DLL
384 */
385 struct PeerInfo *tail;
386
387 /**
388 * Number of peers in the bucket.
389 */
390 unsigned int peers_size;
391};
392
393
394/**
395 * Do we cache all results that we are routing in the local datacache?
396 */
397static int cache_results;
398
399/**
400 * The lowest currently used bucket, initially 0 (for 0-bits matching bucket).
401 */
402static unsigned int closest_bucket;
403
404/**
405 * How many peers have we added since we sent out our last
406 * find peer request?
407 */
408static unsigned int newly_found_peers;
409
410/**
411 * Option for testing that disables the 'connect' function of the DHT.
412 */
413static int disable_try_connect;
414
415/**
416 * The buckets. Array of size #MAX_BUCKETS. Offset 0 means 0 bits matching.
417 */
418static struct PeerBucket k_buckets[MAX_BUCKETS];
419
420/**
421 * Hash map of all CORE-connected peers, for easy removal from
422 * #k_buckets on disconnect. Values are of type `struct PeerInfo`.
423 */
424static struct GNUNET_CONTAINER_MultiPeerMap *all_connected_peers;
425
426/**
427 * Maximum size for each bucket.
428 */
429static unsigned int bucket_size = DEFAULT_BUCKET_SIZE;
430
431/**
432 * Task that sends FIND PEER requests.
433 */
434static struct GNUNET_SCHEDULER_Task *find_peer_task;
435
436
437/**
438 * Function called whenever we finished sending to a target.
439 * Marks the transmission as finished (and the target as ready
440 * for the next message).
441 *
442 * @param cls a `struct Target *`
443 */
444static void
445send_done_cb (void *cls)
446{
447 struct Target *t = cls;
448 struct PeerInfo *pi = t->pi; /* NULL if t->dropped! */
449
450 GNUNET_assert (t->load > 0);
451 t->load--;
452 if (0 < t->load)
453 return;
454 if (t->dropped)
455 {
456 GNUNET_free (t);
457 return;
458 }
459 /* move target back to the front */
460 GNUNET_CONTAINER_DLL_remove (pi->t_head,
461 pi->t_tail,
462 t);
463 GNUNET_CONTAINER_DLL_insert (pi->t_head,
464 pi->t_tail,
465 t);
466}
467
468
469/**
470 * Send @a msg to @a pi.
471 *
472 * @param pi where to send the message
473 * @param msg message to send
474 */
475static void
476do_send (struct PeerInfo *pi,
477 const struct GNUNET_MessageHeader *msg)
478{
479 struct Target *t;
480
481 for (t = pi->t_head;
482 NULL != t;
483 t = t->next)
484 if (t->load < MAXIMUM_PENDING_PER_PEER)
485 break;
486 if (NULL == t)
487 {
488 /* all targets busy, drop message */
489 GNUNET_STATISTICS_update (GDS_stats,
490 "# messages dropped (underlays busy)",
491 1,
492 GNUNET_NO);
493 return;
494 }
495 t->load++;
496 /* rotate busy targets to the end */
497 if (MAXIMUM_PENDING_PER_PEER == t->load)
498 {
499 GNUNET_CONTAINER_DLL_remove (pi->t_head,
500 pi->t_tail,
501 t);
502 GNUNET_CONTAINER_DLL_insert_tail (pi->t_head,
503 pi->t_tail,
504 t);
505 }
506 GDS_u_send (t->u,
507 t->utarget,
508 msg,
509 ntohs (msg->size),
510 &send_done_cb,
511 t);
512}
513
514
515/**
516 * Sign that we are routing a message from @a pred to @a succ.
517 * (So the route is $PRED->us->$SUCC).
518 *
519 * @param key key of the data (not necessarily the query hash)
520 * @param data payload (the block)
521 * @param data_size number of bytes in @a data
522 * @param exp_time expiration time of @a data
523 * @param pred predecessor peer ID
524 * @param succ successor peer ID
525 * @param[out] sig where to write the signature
526 * (of purpose #GNUNET_SIGNATURE_PURPOSE_DHT_PUT_HOP)
527 */
528static void
529sign_path (const void *data,
530 size_t data_size,
531 struct GNUNET_TIME_Absolute exp_time,
532 const struct GNUNET_PeerIdentity *pred,
533 const struct GNUNET_PeerIdentity *succ,
534 struct GNUNET_CRYPTO_EddsaSignature *sig)
535{
536 struct GNUNET_DHT_HopSignature hs = {
537 .purpose.purpose = htonl (GNUNET_SIGNATURE_PURPOSE_DHT_HOP),
538 .purpose.size = htonl (sizeof (hs)),
539 .expiration_time = GNUNET_TIME_absolute_hton (exp_time),
540 .pred = *pred,
541 .succ = *succ
542 };
543
544 GNUNET_CRYPTO_hash (data,
545 data_size,
546 &hs.h_data);
547 GNUNET_CRYPTO_eddsa_sign (&GDS_my_private_key,
548 &hs,
549 sig);
550}
551
552
553/**
554 * Find the optimal bucket for this key.
555 *
556 * @param hc the hashcode to compare our identity to
557 * @return the proper bucket index, or -1
558 * on error (same hashcode)
559 */
560static int
561find_bucket (const struct GNUNET_HashCode *hc)
562{
563 struct GNUNET_HashCode xor;
564 unsigned int bits;
565
566 GNUNET_CRYPTO_hash_xor (hc,
567 &GDS_my_identity_hash,
568 &xor);
569 bits = GNUNET_CRYPTO_hash_count_leading_zeros (&xor);
570 if (bits == MAX_BUCKETS)
571 {
572 /* How can all bits match? Got my own ID? */
573 GNUNET_break (0);
574 return -1;
575 }
576 return MAX_BUCKETS - bits - 1;
577}
578
579
580/**
581 * Add each of the peers we already know to the Bloom filter of
582 * the request so that we don't get duplicate HELLOs.
583 *
584 * @param cls the `struct GNUNET_BLOCK_Group`
585 * @param key peer identity to add to the bloom filter
586 * @param value the peer information
587 * @return #GNUNET_YES (we should continue to iterate)
588 */
589static enum GNUNET_GenericReturnValue
590add_known_to_bloom (void *cls,
591 const struct GNUNET_PeerIdentity *key,
592 void *value)
593{
594 struct GNUNET_BLOCK_Group *bg = cls;
595 struct PeerInfo *pi = value;
596
597 GNUNET_BLOCK_group_set_seen (bg,
598 &pi->phash,
599 1);
600 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
601 "Adding known peer (%s) to Bloom filter for FIND PEER\n",
602 GNUNET_i2s (key));
603 return GNUNET_YES;
604}
605
606
607/**
608 * Task to send a find peer message for our own peer identifier
609 * so that we can find the closest peers in the network to ourselves
610 * and attempt to connect to them.
611 *
612 * @param cls closure for this task, NULL
613 */
614static void
615send_find_peer_message (void *cls)
616{
617 (void) cls;
618
619 /* Compute when to do this again (and if we should
620 even send a message right now) */
621 {
622 struct GNUNET_TIME_Relative next_send_time;
623 bool done_early;
624
625 find_peer_task = NULL;
626 done_early = (newly_found_peers > bucket_size);
627 /* schedule next round, taking longer if we found more peers
628 in the last round. */
629 next_send_time.rel_value_us =
630 DHT_MINIMUM_FIND_PEER_INTERVAL.rel_value_us
631 + GNUNET_CRYPTO_random_u64 (
632 GNUNET_CRYPTO_QUALITY_WEAK,
633 GNUNET_TIME_relative_multiply (
634 DHT_AVG_FIND_PEER_INTERVAL,
635 1 + 100 * (1 + newly_found_peers) / bucket_size).rel_value_us);
636 newly_found_peers = 0;
637 GNUNET_assert (NULL == find_peer_task);
638 find_peer_task =
639 GNUNET_SCHEDULER_add_delayed (next_send_time,
640 &send_find_peer_message,
641 NULL);
642 if (done_early)
643 return;
644 }
645
646 /* actually send 'find peer' request */
647 {
648 struct GNUNET_BLOCK_Group *bg;
649 struct GNUNET_CONTAINER_BloomFilter *peer_bf;
650
651 bg = GNUNET_BLOCK_group_create (GDS_block_context,
652 GNUNET_BLOCK_TYPE_DHT_URL_HELLO,
653 NULL,
654 0,
655 "filter-size",
656 DHT_BLOOM_SIZE,
657 NULL);
658 GNUNET_CONTAINER_multipeermap_iterate (all_connected_peers,
659 &add_known_to_bloom,
660 bg);
661 peer_bf
662 = GNUNET_CONTAINER_bloomfilter_init (NULL,
663 DHT_BLOOM_SIZE,
664 GNUNET_CONSTANTS_BLOOMFILTER_K);
665 if (GNUNET_OK !=
666 GDS_NEIGHBOURS_handle_get (GNUNET_BLOCK_TYPE_DHT_URL_HELLO,
667 GNUNET_DHT_RO_FIND_APPROXIMATE
668 | GNUNET_DHT_RO_RECORD_ROUTE,
669 FIND_PEER_REPLICATION_LEVEL,
670 0, /* hop count */
671 &GDS_my_identity_hash,
672 NULL, 0, /* xquery */
673 bg,
674 peer_bf))
675 {
676 GNUNET_STATISTICS_update (GDS_stats,
677 "# Failed to initiate FIND PEER lookup",
678 1,
679 GNUNET_NO);
680 }
681 else
682 {
683 GNUNET_STATISTICS_update (GDS_stats,
684 "# FIND PEER messages initiated",
685 1,
686 GNUNET_NO);
687 }
688 GNUNET_CONTAINER_bloomfilter_free (peer_bf);
689 GNUNET_BLOCK_group_destroy (bg);
690 }
691}
692
693
694/**
695 * The list of the first #bucket_size peers of @a bucket
696 * changed. We should thus make sure we have called 'hold'
697 * all of the first bucket_size peers!
698 *
699 * @param[in,out] bucket the bucket where the peer set changed
700 */
701static void
702update_hold (struct PeerBucket *bucket)
703{
704 unsigned int off = 0;
705
706 /* find the peer -- we just go over all of them, should
707 be hardly any more expensive than just finding the 'right'
708 one. */
709 for (struct PeerInfo *pos = bucket->head;
710 NULL != pos;
711 pos = pos->next)
712 {
713 if (off > bucket_size)
714 break; /* We only hold up to #bucket_size peers per bucket */
715 off++;
716 for (struct Target *tp = pos->t_head;
717 NULL != tp;
718 tp = tp->next)
719 if (NULL == tp->ph)
720 tp->ph = GDS_u_hold (tp->u,
721 tp->utarget);
722 }
723}
724
725
726void
727GDS_u_connect (void *cls,
728 struct GNUNET_DHTU_Target *target,
729 const struct GNUNET_PeerIdentity *pid,
730 void **ctx)
731{
732 struct GDS_Underlay *u = cls;
733 struct PeerInfo *pi;
734 struct PeerBucket *bucket;
735 bool do_hold = false;
736
737 /* Check for connect to self message */
738 if (0 == GNUNET_memcmp (&GDS_my_identity,
739 pid))
740 return;
741 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
742 "Connected to peer %s\n",
743 GNUNET_i2s (pid));
744 pi = GNUNET_CONTAINER_multipeermap_get (all_connected_peers,
745 pid);
746 if (NULL == pi)
747 {
748 GNUNET_STATISTICS_update (GDS_stats,
749 "# peers connected",
750 1,
751 GNUNET_NO);
752 pi = GNUNET_new (struct PeerInfo);
753 pi->id = *pid;
754 GNUNET_CRYPTO_hash (pid,
755 sizeof(*pid),
756 &pi->phash);
757 pi->peer_bucket = find_bucket (&pi->phash);
758 GNUNET_assert ( (pi->peer_bucket >= 0) &&
759 ((unsigned int) pi->peer_bucket < MAX_BUCKETS));
760 bucket = &k_buckets[pi->peer_bucket];
761 GNUNET_CONTAINER_DLL_insert_tail (bucket->head,
762 bucket->tail,
763 pi);
764 bucket->peers_size++;
765 closest_bucket = GNUNET_MAX (closest_bucket,
766 (unsigned int) pi->peer_bucket + 1);
767 GNUNET_assert (GNUNET_OK ==
768 GNUNET_CONTAINER_multipeermap_put (all_connected_peers,
769 &pi->id,
770 pi,
771 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
772 if (bucket->peers_size <= bucket_size)
773 {
774 newly_found_peers++;
775 do_hold = true;
776 }
777 if ( (1 == GNUNET_CONTAINER_multipeermap_size (all_connected_peers)) &&
778 (GNUNET_YES != disable_try_connect) )
779 {
780 /* got a first connection, good time to start with FIND PEER requests... */
781 GNUNET_assert (NULL == find_peer_task);
782 find_peer_task = GNUNET_SCHEDULER_add_now (&send_find_peer_message,
783 NULL);
784 }
785 }
786 {
787 struct Target *t;
788
789 t = GNUNET_new (struct Target);
790 t->u = u;
791 t->utarget = target;
792 t->pi = pi;
793 GNUNET_CONTAINER_DLL_insert (pi->t_head,
794 pi->t_tail,
795 t);
796 *ctx = t;
797
798 }
799 if (do_hold)
800 update_hold (bucket);
801}
802
803
804void
805GDS_u_disconnect (void *ctx)
806{
807 struct Target *t = ctx;
808 struct PeerInfo *pi;
809 struct PeerBucket *bucket;
810 bool was_held = false;
811
812 /* Check for disconnect from self message (on shutdown) */
813 if (NULL == t)
814 return;
815 pi = t->pi;
816 GNUNET_CONTAINER_DLL_remove (pi->t_head,
817 pi->t_tail,
818 t);
819 if (NULL != t->ph)
820 {
821 GDS_u_drop (t->u,
822 t->ph);
823 t->ph = NULL;
824 was_held = true;
825 }
826 if (t->load > 0)
827 {
828 t->dropped = true;
829 t->pi = NULL;
830 }
831 else
832 {
833 GNUNET_free (t);
834 }
835 if (NULL != pi->t_head)
836 return; /* got other connections still */
837 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
838 "Disconnected from peer %s\n",
839 GNUNET_i2s (&pi->id));
840 GNUNET_STATISTICS_update (GDS_stats,
841 "# peers connected",
842 -1,
843 GNUNET_NO);
844 GNUNET_assert (GNUNET_YES ==
845 GNUNET_CONTAINER_multipeermap_remove (all_connected_peers,
846 &pi->id,
847 pi));
848 if ( (0 == GNUNET_CONTAINER_multipeermap_size (all_connected_peers)) &&
849 (GNUNET_YES != disable_try_connect))
850 {
851 GNUNET_SCHEDULER_cancel (find_peer_task);
852 find_peer_task = NULL;
853 }
854 GNUNET_assert (pi->peer_bucket >= 0);
855 bucket = &k_buckets[pi->peer_bucket];
856 GNUNET_CONTAINER_DLL_remove (bucket->head,
857 bucket->tail,
858 pi);
859 GNUNET_assert (bucket->peers_size > 0);
860 bucket->peers_size--;
861 if ( (was_held) &&
862 (bucket->peers_size >= bucket_size - 1) )
863 update_hold (bucket);
864 while ( (closest_bucket > 0) &&
865 (0 == k_buckets[closest_bucket - 1].peers_size))
866 closest_bucket--;
867 GNUNET_free (pi->hello);
868 GNUNET_free (pi);
869}
870
871
872/**
873 * To how many peers should we (on average) forward the request to
874 * obtain the desired target_replication count (on average).
875 *
876 * @param hop_count number of hops the message has traversed
877 * @param target_replication the number of total paths desired
878 * @return Some number of peers to forward the message to
879 */
880static unsigned int
881get_forward_count (uint16_t hop_count,
882 uint16_t target_replication)
883{
884 uint32_t random_value;
885 uint32_t forward_count;
886 float target_value;
887 float rm1;
888
889 if (hop_count > GDS_NSE_get () * 4.0)
890 {
891 /* forcefully terminate */
892 GNUNET_STATISTICS_update (GDS_stats,
893 "# requests TTL-dropped",
894 1,
895 GNUNET_NO);
896 return 0;
897 }
898 if (hop_count > GDS_NSE_get () * 2.0)
899 {
900 /* Once we have reached our ideal number of hops, only forward to 1 peer */
901 return 1;
902 }
903 /* bound by system-wide maximum and minimum */
904 if (0 == target_replication)
905 target_replication = 1; /* 0 is verboten */
906 target_replication =
907 GNUNET_MIN (GNUNET_DHT_MAXIMUM_REPLICATION_LEVEL,
908 target_replication);
909 rm1 = target_replication - 1.0;
910 target_value =
911 1 + (rm1) / (GDS_NSE_get () + (rm1 * hop_count));
912
913 /* Set forward count to floor of target_value */
914 forward_count = (uint32_t) target_value;
915 /* Subtract forward_count (floor) from target_value (yields value between 0 and 1) */
916 target_value = target_value - forward_count;
917 random_value = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
918 UINT32_MAX);
919 if (random_value < (target_value * UINT32_MAX))
920 forward_count++;
921 return GNUNET_MIN (forward_count,
922 GNUNET_DHT_MAXIMUM_REPLICATION_LEVEL);
923}
924
925
926/**
927 * Check whether my identity is closer than any known peers. If a
928 * non-null bloomfilter is given, check if this is the closest peer
929 * that hasn't already been routed to.
930 *
931 * @param key hash code to check closeness to
932 * @param bloom bloomfilter, exclude these entries from the decision
933 * @return #GNUNET_YES if node location is closest,
934 * #GNUNET_NO otherwise.
935 */
936enum GNUNET_GenericReturnValue
937GDS_am_closest_peer (const struct GNUNET_HashCode *key,
938 const struct GNUNET_CONTAINER_BloomFilter *bloom)
939{
940 if (0 == GNUNET_memcmp (&GDS_my_identity_hash,
941 key))
942 return GNUNET_YES;
943 for (int bucket_num = find_bucket (key);
944 bucket_num < closest_bucket;
945 bucket_num++)
946 {
947 unsigned int count = 0;
948
949 GNUNET_assert (bucket_num >= 0);
950 for (struct PeerInfo *pos = k_buckets[bucket_num].head;
951 NULL != pos;
952 pos = pos->next)
953 {
954 if (count >= bucket_size)
955 break; /* we only consider first #bucket_size entries per bucket */
956 count++;
957 if ( (NULL != bloom) &&
958 (GNUNET_YES ==
959 GNUNET_CONTAINER_bloomfilter_test (bloom,
960 &pos->phash)) )
961 continue; /* Ignore filtered peers */
962 /* All peers in this bucket must be closer than us, as
963 they mismatch with our PID on the pivotal bit. So
964 because an unfiltered peer exists, we are not the
965 closest. */
966 int delta = GNUNET_CRYPTO_hash_xorcmp (&pos->phash,
967 &GDS_my_identity_hash,
968 key);
969 switch (delta)
970 {
971 case -1: /* pos closer */
972 return GNUNET_NO;
973 case 0: /* identical, impossible! */
974 GNUNET_assert (0);
975 break;
976 case 1: /* I am closer */
977 break;
978 }
979 }
980 }
981 /* No closer (unfiltered) peers found; we must be the closest! */
982 return GNUNET_YES;
983}
984
985
986/**
987 * Select a peer from the routing table that would be a good routing
988 * destination for sending a message for @a key. The resulting peer
989 * must not be in the set of @a bloom blocked peers.
990 *
991 * Note that we should not ALWAYS select the closest peer to the
992 * target, we do a "random" peer selection if the number of @a hops
993 * is below the logarithm of the network size estimate.
994 *
995 * In all cases, we only consider at most the first #bucket_size peers of any
996 * #k_buckets. The other peers in the bucket are there because GNUnet doesn't
997 * really allow the DHT to "reject" connections, but we only use the first
998 * #bucket_size, even if more exist. (The idea is to ensure that those
999 * connections are frequently used, and for others to be not used by the DHT,
1000 * and thus possibly dropped by transport due to disuse).
1001 *
1002 * @param key the key we are selecting a peer to route to
1003 * @param bloom a Bloom filter containing entries this request has seen already
1004 * @param hops how many hops has this message traversed thus far
1005 * @return Peer to route to, or NULL on error
1006 */
1007static struct PeerInfo *
1008select_peer (const struct GNUNET_HashCode *key,
1009 const struct GNUNET_CONTAINER_BloomFilter *bloom,
1010 uint32_t hops)
1011{
1012 if (0 == closest_bucket)
1013 {
1014 GNUNET_STATISTICS_update (GDS_stats,
1015 "# Peer selection failed",
1016 1,
1017 GNUNET_NO);
1018 return NULL; /* we have zero connections */
1019 }
1020 if (hops >= GDS_NSE_get ())
1021 {
1022 /* greedy selection (closest peer that is not in Bloom filter) */
1023 struct PeerInfo *chosen = NULL;
1024 int best_bucket;
1025 int bucket_offset;
1026
1027 {
1028 struct GNUNET_HashCode xor;
1029
1030 GNUNET_CRYPTO_hash_xor (key,
1031 &GDS_my_identity_hash,
1032 &xor);
1033 best_bucket = GNUNET_CRYPTO_hash_count_leading_zeros (&xor);
1034 }
1035 if (best_bucket >= closest_bucket)
1036 bucket_offset = closest_bucket - 1;
1037 else
1038 bucket_offset = best_bucket;
1039 while (-1 != bucket_offset)
1040 {
1041 struct PeerBucket *bucket = &k_buckets[bucket_offset];
1042 unsigned int count = 0;
1043
1044 for (struct PeerInfo *pos = bucket->head;
1045 NULL != pos;
1046 pos = pos->next)
1047 {
1048 if (count >= bucket_size)
1049 break; /* we only consider first #bucket_size entries per bucket */
1050 count++;
1051 if ( (NULL != bloom) &&
1052 (GNUNET_YES ==
1053 GNUNET_CONTAINER_bloomfilter_test (bloom,
1054 &pos->phash)) )
1055 {
1056 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1057 "Excluded peer `%s' due to BF match in greedy routing for %s\n",
1058 GNUNET_i2s (&pos->id),
1059 GNUNET_h2s (key));
1060 continue;
1061 }
1062 if (NULL == chosen)
1063 {
1064 /* First candidate */
1065 chosen = pos;
1066 }
1067 else
1068 {
1069 int delta = GNUNET_CRYPTO_hash_xorcmp (&pos->phash,
1070 &chosen->phash,
1071 key);
1072 switch (delta)
1073 {
1074 case -1: /* pos closer */
1075 chosen = pos;
1076 break;
1077 case 0: /* identical, impossible! */
1078 GNUNET_assert (0);
1079 break;
1080 case 1: /* chosen closer */
1081 break;
1082 }
1083 }
1084 count++;
1085 } /* for all (#bucket_size) peers in bucket */
1086 if (NULL != chosen)
1087 break;
1088
1089 /* If we chose nothing in first iteration, first go through deeper
1090 buckets (best chance to find a good match), and if we still found
1091 nothing, then to shallower buckets. Terminate on any match in the
1092 current bucket, as this search order guarantees that it can only get
1093 worse as we keep going. */
1094 if (bucket_offset > best_bucket)
1095 {
1096 /* Go through more deeper buckets */
1097 bucket_offset++;
1098 if (bucket_offset == closest_bucket)
1099 {
1100 /* Can't go any deeper, if nothing selected,
1101 go for shallower buckets */
1102 bucket_offset = best_bucket - 1;
1103 }
1104 }
1105 else
1106 {
1107 /* We're either at the 'best_bucket' or already moving
1108 on to shallower buckets. */
1109 if (bucket_offset == best_bucket)
1110 bucket_offset++; /* go for deeper buckets */
1111 else
1112 bucket_offset--; /* go for shallower buckets */
1113 }
1114 } /* for applicable buckets (starting at best match) */
1115 if (NULL == chosen)
1116 {
1117 GNUNET_STATISTICS_update (GDS_stats,
1118 "# Peer selection failed",
1119 1,
1120 GNUNET_NO);
1121 return NULL;
1122 }
1123 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1124 "Selected peer `%s' in greedy routing for %s\n",
1125 GNUNET_i2s (&chosen->id),
1126 GNUNET_h2s (key));
1127 return chosen;
1128 } /* end of 'greedy' peer selection */
1129
1130 /* select "random" peer */
1131 /* count number of peers that are available and not filtered,
1132 but limit to at most #bucket_size peers, starting with
1133 those 'furthest' from us. */
1134 {
1135 unsigned int total = 0;
1136 unsigned int selected;
1137
1138 for (unsigned int bc = 0; bc < closest_bucket; bc++)
1139 {
1140 struct PeerBucket *bucket = &k_buckets[bc];
1141 unsigned int count = 0;
1142
1143 for (struct PeerInfo *pos = bucket->head;
1144 NULL != pos;
1145 pos = pos->next)
1146 {
1147 count++;
1148 if (count > bucket_size)
1149 break; /* limits search to #bucket_size peers per bucket */
1150 if ( (NULL != bloom) &&
1151 (GNUNET_YES ==
1152 GNUNET_CONTAINER_bloomfilter_test (bloom,
1153 &pos->phash)) )
1154 {
1155 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1156 "Excluded peer `%s' due to BF match in random routing for %s\n",
1157 GNUNET_i2s (&pos->id),
1158 GNUNET_h2s (key));
1159 continue; /* Ignore filtered peers */
1160 }
1161 total++;
1162 } /* for all peers in bucket */
1163 } /* for all buckets */
1164 if (0 == total) /* No peers to select from! */
1165 {
1166 GNUNET_STATISTICS_update (GDS_stats,
1167 "# Peer selection failed",
1168 1,
1169 GNUNET_NO);
1170 return NULL;
1171 }
1172
1173 /* Now actually choose a peer */
1174 selected = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
1175 total);
1176 for (unsigned int bc = 0; bc < closest_bucket; bc++)
1177 {
1178 unsigned int count = 0;
1179
1180 for (struct PeerInfo *pos = k_buckets[bc].head;
1181 pos != NULL;
1182 pos = pos->next)
1183 {
1184 count++;
1185 if (count > bucket_size)
1186 break; /* limits search to #bucket_size peers per bucket */
1187
1188 if ( (NULL != bloom) &&
1189 (GNUNET_YES ==
1190 GNUNET_CONTAINER_bloomfilter_test (bloom,
1191 &pos->phash)) )
1192 continue; /* Ignore bloomfiltered peers */
1193 if (0 == selected--)
1194 {
1195 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1196 "Selected peer `%s' in random routing for %s\n",
1197 GNUNET_i2s (&pos->id),
1198 GNUNET_h2s (key));
1199 return pos;
1200 }
1201 } /* for peers in bucket */
1202 } /* for all buckets */
1203 } /* random peer selection scope */
1204 GNUNET_break (0);
1205 return NULL;
1206}
1207
1208
1209/**
1210 * Compute the set of peers that the given request should be
1211 * forwarded to.
1212 *
1213 * @param key routing key
1214 * @param[in,out] bloom Bloom filter excluding peers as targets,
1215 * all selected peers will be added to the Bloom filter
1216 * @param hop_count number of hops the request has traversed so far
1217 * @param target_replication desired number of replicas
1218 * @param[out] targets where to store an array of target peers (to be
1219 * free()ed by the caller)
1220 * @return number of peers returned in @a targets.
1221 */
1222static unsigned int
1223get_target_peers (const struct GNUNET_HashCode *key,
1224 struct GNUNET_CONTAINER_BloomFilter *bloom,
1225 uint16_t hop_count,
1226 uint16_t target_replication,
1227 struct PeerInfo ***targets)
1228{
1229 unsigned int target;
1230 unsigned int off;
1231 struct PeerInfo **rtargets;
1232
1233 GNUNET_assert (NULL != bloom);
1234 target = get_forward_count (hop_count,
1235 target_replication);
1236 if (0 == target)
1237 {
1238 *targets = NULL;
1239 return 0;
1240 }
1241 rtargets = GNUNET_new_array (target,
1242 struct PeerInfo *);
1243 for (off = 0; off < target; off++)
1244 {
1245 struct PeerInfo *nxt;
1246
1247 nxt = select_peer (key,
1248 bloom,
1249 hop_count);
1250 if (NULL == nxt)
1251 break;
1252 rtargets[off] = nxt;
1253 GNUNET_break (GNUNET_NO ==
1254 GNUNET_CONTAINER_bloomfilter_test (bloom,
1255 &nxt->phash));
1256 GNUNET_CONTAINER_bloomfilter_add (bloom,
1257 &nxt->phash);
1258 }
1259 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1260 "Selected %u/%u peers at hop %u for %s (target was %u)\n",
1261 off,
1262 GNUNET_CONTAINER_multipeermap_size (all_connected_peers),
1263 (unsigned int) hop_count,
1264 GNUNET_h2s (key),
1265 target);
1266 if (0 == off)
1267 {
1268 GNUNET_free (rtargets);
1269 *targets = NULL;
1270 return 0;
1271 }
1272 *targets = rtargets;
1273 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1274 "Forwarding query `%s' to %u peers (goal was %u peers)\n",
1275 GNUNET_h2s (key),
1276 off,
1277 target);
1278 return off;
1279}
1280
1281
1282/**
1283 * If we got a HELLO, consider it for our own routing table
1284 *
1285 * @param bd block data we got
1286 */
1287static void
1288hello_check (const struct GDS_DATACACHE_BlockData *bd)
1289{
1290 struct GNUNET_PeerIdentity pid;
1291 struct GNUNET_HELLO_Builder *b;
1292
1293 if (GNUNET_BLOCK_TYPE_DHT_URL_HELLO != bd->type)
1294 return;
1295
1296 b = GNUNET_HELLO_builder_from_block (bd->data,
1297 bd->data_size);
1298 if (GNUNET_YES != disable_try_connect)
1299 GNUNET_HELLO_builder_iterate (b,
1300 &pid,
1301 &GDS_try_connect,
1302 &pid);
1303 GNUNET_HELLO_builder_free (b);
1304}
1305
1306
1307enum GNUNET_GenericReturnValue
1308GDS_NEIGHBOURS_handle_put (const struct GDS_DATACACHE_BlockData *bd,
1309 enum GNUNET_DHT_RouteOption options,
1310 uint16_t desired_replication_level,
1311 uint16_t hop_count,
1312 struct GNUNET_CONTAINER_BloomFilter *bf)
1313{
1314 unsigned int target_count;
1315 struct PeerInfo **targets;
1316 size_t msize;
1317 unsigned int skip_count;
1318 unsigned int put_path_length = bd->put_path_length;
1319
1320 GNUNET_assert (NULL != bf);
1321#if SANITY_CHECKS > 1
1322 if (0 !=
1323 GNUNET_DHT_verify_path (bd->data,
1324 bd->data_size,
1325 bd->expiration_time,
1326 bd->put_path,
1327 bd->put_path_length,
1328 NULL, 0, /* get_path */
1329 &GDS_my_identity))
1330 {
1331 GNUNET_break_op (0);
1332 put_path_length = 0;
1333 }
1334#endif
1335 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1336 "Adding myself (%s) to PUT bloomfilter for %s with RO(%s/%s)\n",
1337 GNUNET_i2s (&GDS_my_identity),
1338 GNUNET_h2s (&bd->key),
1339 (options & GNUNET_DHT_RO_DEMULTIPLEX_EVERYWHERE) ? "x" : "-",
1340 (options & GNUNET_DHT_RO_RECORD_ROUTE) ? "R" : "-");
1341
1342 /* if we got a HELLO, consider it for our own routing table */
1343 hello_check (bd);
1344 GNUNET_CONTAINER_bloomfilter_add (bf,
1345 &GDS_my_identity_hash);
1346 GNUNET_STATISTICS_update (GDS_stats,
1347 "# PUT requests routed",
1348 1,
1349 GNUNET_NO);
1350 target_count
1351 = get_target_peers (&bd->key,
1352 bf,
1353 hop_count,
1354 desired_replication_level,
1355 &targets);
1356 if (0 == target_count)
1357 {
1358 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1359 "Routing PUT for %s terminates after %u hops at %s\n",
1360 GNUNET_h2s (&bd->key),
1361 (unsigned int) hop_count,
1362 GNUNET_i2s (&GDS_my_identity));
1363 return GNUNET_NO;
1364 }
1365 msize = bd->put_path_length * sizeof(struct GNUNET_DHT_PathElement)
1366 + bd->data_size;
1367 if (msize + sizeof(struct PeerPutMessage)
1368 >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1369 {
1370 put_path_length = 0;
1371 msize = bd->data_size;
1372 }
1373 if (msize + sizeof(struct PeerPutMessage)
1374 >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1375 {
1376 GNUNET_break (0);
1377 GNUNET_free (targets);
1378 return GNUNET_NO;
1379 }
1380 skip_count = 0;
1381 for (unsigned int i = 0; i < target_count; i++)
1382 {
1383 struct PeerInfo *target = targets[i];
1384 struct PeerPutMessage *ppm;
1385 char buf[sizeof (*ppm) + msize] GNUNET_ALIGN;
1386 struct GNUNET_DHT_PathElement *pp;
1387
1388 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1389 "Routing PUT for %s after %u hops to %s\n",
1390 GNUNET_h2s (&bd->key),
1391 (unsigned int) hop_count,
1392 GNUNET_i2s (&target->id));
1393 ppm = (struct PeerPutMessage *) buf;
1394 ppm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_PUT);
1395 ppm->header.size = htons (sizeof (buf));
1396 ppm->type = htonl (bd->type);
1397 ppm->options = htons (options);
1398 ppm->hop_count = htons (hop_count + 1);
1399 ppm->desired_replication_level = htons (desired_replication_level);
1400 ppm->put_path_length = htons (put_path_length);
1401 ppm->expiration_time = GNUNET_TIME_absolute_hton (bd->expiration_time);
1402 GNUNET_break (GNUNET_YES ==
1403 GNUNET_CONTAINER_bloomfilter_test (bf,
1404 &target->phash));
1405 GNUNET_assert (GNUNET_OK ==
1406 GNUNET_CONTAINER_bloomfilter_get_raw_data (bf,
1407 ppm->bloomfilter,
1408 DHT_BLOOM_SIZE));
1409 ppm->key = bd->key;
1410 pp = (struct GNUNET_DHT_PathElement *) &ppm[1];
1411 GNUNET_memcpy (pp,
1412 bd->put_path,
1413 sizeof (struct GNUNET_DHT_PathElement) * put_path_length);
1414 /* 0 == put_path_length means path is not being tracked */
1415 if (0 != put_path_length)
1416 {
1417 /* Note that the signature in 'put_path' was not initialized before,
1418 so this is crucial to avoid sending garbage. */
1419 sign_path (bd->data,
1420 bd->data_size,
1421 bd->expiration_time,
1422 &pp[put_path_length - 1].pred,
1423 &target->id,
1424 &pp[put_path_length - 1].sig);
1425 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1426 "Signing PUT PATH %u => %s\n",
1427 put_path_length,
1428 GNUNET_B2S (&pp[put_path_length - 1].sig));
1429 }
1430
1431 GNUNET_memcpy (&pp[put_path_length],
1432 bd->data,
1433 bd->data_size);
1434 do_send (target,
1435 &ppm->header);
1436 }
1437 GNUNET_free (targets);
1438 GNUNET_STATISTICS_update (GDS_stats,
1439 "# PUT messages queued for transmission",
1440 target_count - skip_count,
1441 GNUNET_NO);
1442 return (skip_count < target_count) ? GNUNET_OK : GNUNET_NO;
1443}
1444
1445
1446enum GNUNET_GenericReturnValue
1447GDS_NEIGHBOURS_handle_get (enum GNUNET_BLOCK_Type type,
1448 enum GNUNET_DHT_RouteOption options,
1449 uint16_t desired_replication_level,
1450 uint16_t hop_count,
1451 const struct GNUNET_HashCode *key,
1452 const void *xquery,
1453 size_t xquery_size,
1454 struct GNUNET_BLOCK_Group *bg,
1455 struct GNUNET_CONTAINER_BloomFilter *peer_bf)
1456{
1457 unsigned int target_count;
1458 struct PeerInfo **targets;
1459 size_t msize;
1460 size_t result_filter_size;
1461 void *result_filter;
1462 unsigned int skip_count;
1463
1464 GNUNET_assert (NULL != peer_bf);
1465 GNUNET_STATISTICS_update (GDS_stats,
1466 "# GET requests routed",
1467 1,
1468 GNUNET_NO);
1469 target_count = get_target_peers (key,
1470 peer_bf,
1471 hop_count,
1472 desired_replication_level,
1473 &targets);
1474 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1475 "Adding myself (%s) to GET bloomfilter for %s with RO(%s/%s)\n",
1476 GNUNET_i2s (&GDS_my_identity),
1477 GNUNET_h2s (key),
1478 (options & GNUNET_DHT_RO_DEMULTIPLEX_EVERYWHERE) ? "x" : "-",
1479 (options & GNUNET_DHT_RO_RECORD_ROUTE) ? "R" : "-");
1480
1481 GNUNET_CONTAINER_bloomfilter_add (peer_bf,
1482 &GDS_my_identity_hash);
1483 if (0 == target_count)
1484 {
1485 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1486 "Routing GET for %s terminates after %u hops at %s\n",
1487 GNUNET_h2s (key),
1488 (unsigned int) hop_count,
1489 GNUNET_i2s (&GDS_my_identity));
1490 return GNUNET_NO;
1491 }
1492 if (GNUNET_OK !=
1493 GNUNET_BLOCK_group_serialize (bg,
1494 &result_filter,
1495 &result_filter_size))
1496 {
1497 result_filter = NULL;
1498 result_filter_size = 0;
1499 }
1500 msize = xquery_size + result_filter_size;
1501 if (msize + sizeof(struct PeerGetMessage) >= GNUNET_MAX_MESSAGE_SIZE)
1502 {
1503 GNUNET_break (0);
1504 GNUNET_free (result_filter);
1505 GNUNET_free (targets);
1506 return GNUNET_NO;
1507 }
1508 /* forward request */
1509 skip_count = 0;
1510 for (unsigned int i = 0; i < target_count; i++)
1511 {
1512 struct PeerInfo *target = targets[i];
1513 struct PeerGetMessage *pgm;
1514 char buf[sizeof (*pgm) + msize] GNUNET_ALIGN;
1515 char *rf;
1516
1517 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1518 "Routing GET for %s after %u hops to %s\n",
1519 GNUNET_h2s (key),
1520 (unsigned int) hop_count,
1521 GNUNET_i2s (&target->id));
1522 pgm = (struct PeerGetMessage *) buf;
1523 pgm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_GET);
1524 pgm->header.size = htons (sizeof (buf));
1525 pgm->type = htonl (type);
1526 pgm->options = htons (options);
1527 pgm->hop_count = htons (hop_count + 1);
1528 pgm->desired_replication_level = htons (desired_replication_level);
1529 pgm->result_filter_size = htons ((uint16_t) result_filter_size);
1530 GNUNET_break (GNUNET_YES ==
1531 GNUNET_CONTAINER_bloomfilter_test (peer_bf,
1532 &target->phash));
1533 GNUNET_assert (GNUNET_OK ==
1534 GNUNET_CONTAINER_bloomfilter_get_raw_data (peer_bf,
1535 pgm->bloomfilter,
1536 DHT_BLOOM_SIZE));
1537 pgm->key = *key;
1538 rf = (char *) &pgm[1];
1539 GNUNET_memcpy (rf,
1540 result_filter,
1541 result_filter_size);
1542 GNUNET_memcpy (&rf[result_filter_size],
1543 xquery,
1544 xquery_size);
1545 do_send (target,
1546 &pgm->header);
1547 }
1548 GNUNET_STATISTICS_update (GDS_stats,
1549 "# GET messages queued for transmission",
1550 target_count - skip_count,
1551 GNUNET_NO);
1552 GNUNET_free (targets);
1553 GNUNET_free (result_filter);
1554 return (skip_count < target_count) ? GNUNET_OK : GNUNET_NO;
1555}
1556
1557
1558struct PeerInfo *
1559GDS_NEIGHBOURS_lookup_peer (const struct GNUNET_PeerIdentity *target)
1560{
1561 return GNUNET_CONTAINER_multipeermap_get (all_connected_peers,
1562 target);
1563}
1564
1565
1566bool
1567GDS_NEIGHBOURS_handle_reply (struct PeerInfo *pi,
1568 const struct GDS_DATACACHE_BlockData *bd,
1569 const struct GNUNET_HashCode *query_hash,
1570 unsigned int get_path_length,
1571 const struct GNUNET_DHT_PathElement *get_path)
1572{
1573 struct GNUNET_DHT_PathElement *paths;
1574 size_t msize;
1575 unsigned int ppl = bd->put_path_length;
1576
1577#if SANITY_CHECKS > 1
1578 if (0 !=
1579 GNUNET_DHT_verify_path (bd->data,
1580 bd->data_size,
1581 bd->expiration_time,
1582 bd->put_path,
1583 bd->put_path_length,
1584 get_path,
1585 get_path_length,
1586 &GDS_my_identity))
1587 {
1588 GNUNET_break_op (0);
1589 return false;
1590 }
1591#endif
1592 msize = bd->data_size + (get_path_length + ppl)
1593 * sizeof(struct GNUNET_DHT_PathElement);
1594 if ( (msize + sizeof(struct PeerResultMessage) >= GNUNET_MAX_MESSAGE_SIZE) ||
1595 (get_path_length >
1596 GNUNET_MAX_MESSAGE_SIZE / sizeof(struct GNUNET_DHT_PathElement)) ||
1597 (ppl >
1598 GNUNET_MAX_MESSAGE_SIZE / sizeof(struct GNUNET_DHT_PathElement)) ||
1599 (bd->data_size > GNUNET_MAX_MESSAGE_SIZE))
1600 {
1601 ppl = 0;
1602 get_path_length = 0;
1603 msize = bd->data_size + (get_path_length + ppl)
1604 * sizeof(struct GNUNET_DHT_PathElement);
1605 }
1606 if ( (msize + sizeof(struct PeerResultMessage) >= GNUNET_MAX_MESSAGE_SIZE) ||
1607 (get_path_length >
1608 GNUNET_MAX_MESSAGE_SIZE / sizeof(struct GNUNET_DHT_PathElement)) ||
1609 (ppl >
1610 GNUNET_MAX_MESSAGE_SIZE / sizeof(struct GNUNET_DHT_PathElement)) ||
1611 (bd->data_size > GNUNET_MAX_MESSAGE_SIZE))
1612 {
1613 GNUNET_break (0);
1614 return false;
1615 }
1616 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1617 "Forwarding reply for key %s to peer %s\n",
1618 GNUNET_h2s (query_hash),
1619 GNUNET_i2s (&pi->id));
1620 GNUNET_STATISTICS_update (GDS_stats,
1621 "# RESULT messages queued for transmission",
1622 1,
1623 GNUNET_NO);
1624 {
1625 struct PeerResultMessage *prm;
1626 char buf[sizeof (*prm) + msize] GNUNET_ALIGN;
1627
1628 prm = (struct PeerResultMessage *) buf;
1629 prm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_RESULT);
1630 prm->header.size = htons (sizeof (buf));
1631 prm->type = htonl (bd->type);
1632 prm->reserved = htonl (0);
1633 prm->put_path_length = htons (ppl);
1634 prm->get_path_length = htons (get_path_length);
1635 prm->expiration_time = GNUNET_TIME_absolute_hton (bd->expiration_time);
1636 prm->key = *query_hash;
1637 paths = (struct GNUNET_DHT_PathElement *) &prm[1];
1638 if (NULL != bd->put_path)
1639 {
1640 GNUNET_memcpy (paths,
1641 bd->put_path,
1642 ppl * sizeof(struct GNUNET_DHT_PathElement));
1643 }
1644 else
1645 {
1646 GNUNET_assert (0 == ppl);
1647 }
1648 if (NULL != get_path)
1649 {
1650 GNUNET_memcpy (&paths[ppl],
1651 get_path,
1652 get_path_length * sizeof(struct GNUNET_DHT_PathElement));
1653 }
1654 else
1655 {
1656 GNUNET_assert (0 == get_path_length);
1657 }
1658 /* 0 == get_path_length+ppl means path is not being tracked */
1659 if (0 != (get_path_length + ppl))
1660 {
1661 /* Note that the last signature in 'paths' was not initialized before,
1662 so this is crucial to avoid sending garbage. */
1663 sign_path (bd->data,
1664 bd->data_size,
1665 bd->expiration_time,
1666 &paths[ppl + get_path_length - 1].pred,
1667 &pi->id,
1668 &paths[ppl + get_path_length - 1].sig);
1669 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1670 "Signing GET PATH %u/%u of %s => %s\n",
1671 ppl,
1672 get_path_length,
1673 GNUNET_h2s (query_hash),
1674 GNUNET_B2S (&paths[ppl + get_path_length - 1].sig));
1675 }
1676 GNUNET_memcpy (&paths[ppl + get_path_length],
1677 bd->data,
1678 bd->data_size);
1679
1680#if SANITY_CHECKS > 1
1681 {
1682 struct GNUNET_DHT_PathElement xpaths[get_path_length + 1];
1683
1684 memcpy (xpaths,
1685 &paths[ppl],
1686 get_path_length * sizeof (struct GNUNET_DHT_PathElement));
1687 xpaths[get_path_length].pred = GDS_my_identity;
1688 if (0 !=
1689 GNUNET_DHT_verify_path (bd->data,
1690 bd->data_size,
1691 bd->expiration_time,
1692 paths,
1693 ppl,
1694 xpaths,
1695 get_path_length + 1,
1696 &pi->id))
1697 {
1698 GNUNET_break (0);
1699 return false;
1700 }
1701 }
1702#endif
1703 do_send (pi,
1704 &prm->header);
1705 }
1706 return true;
1707}
1708
1709
1710/**
1711 * Check validity of a p2p put request.
1712 *
1713 * @param cls closure with the `struct PeerInfo` of the sender
1714 * @param message message
1715 * @return #GNUNET_OK if the message is valid
1716 */
1717static enum GNUNET_GenericReturnValue
1718check_dht_p2p_put (void *cls,
1719 const struct PeerPutMessage *put)
1720{
1721 uint16_t msize = ntohs (put->header.size);
1722 uint16_t putlen = ntohs (put->put_path_length);
1723
1724 (void) cls;
1725 if ( (msize <
1726 sizeof(struct PeerPutMessage)
1727 + putlen * sizeof(struct GNUNET_DHT_PathElement)) ||
1728 (putlen >
1729 GNUNET_MAX_MESSAGE_SIZE / sizeof(struct GNUNET_DHT_PathElement)) )
1730 {
1731 GNUNET_break_op (0);
1732 return GNUNET_SYSERR;
1733 }
1734 return GNUNET_OK;
1735}
1736
1737
1738/**
1739 * Core handler for p2p put requests.
1740 *
1741 * @param cls closure with the `struct Target` of the sender
1742 * @param message message
1743 */
1744static void
1745handle_dht_p2p_put (void *cls,
1746 const struct PeerPutMessage *put)
1747{
1748 struct Target *t = cls;
1749 struct PeerInfo *peer = t->pi;
1750 uint16_t msize = ntohs (put->header.size);
1751 enum GNUNET_DHT_RouteOption options
1752 = (enum GNUNET_DHT_RouteOption) ntohs (put->options);
1753 const struct GNUNET_DHT_PathElement *put_path
1754 = (const struct GNUNET_DHT_PathElement *) &put[1];
1755 uint16_t putlen
1756 = ntohs (put->put_path_length);
1757 struct GDS_DATACACHE_BlockData bd = {
1758 .key = put->key,
1759 .expiration_time = GNUNET_TIME_absolute_ntoh (put->expiration_time),
1760 .type = ntohl (put->type),
1761 .data_size = msize - (sizeof(*put)
1762 + putlen * sizeof(struct GNUNET_DHT_PathElement)),
1763 .data = &put_path[putlen]
1764 };
1765
1766 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1767 "PUT for `%s' from %s with RO (%s/%s)\n",
1768 GNUNET_h2s (&put->key),
1769 GNUNET_i2s (&peer->id),
1770 (options & GNUNET_DHT_RO_DEMULTIPLEX_EVERYWHERE) ? "x" : "-",
1771 (options & GNUNET_DHT_RO_RECORD_ROUTE) ? "R" : "-");
1772 if (GNUNET_TIME_absolute_is_past (bd.expiration_time))
1773 {
1774 GNUNET_STATISTICS_update (GDS_stats,
1775 "# Expired PUTs discarded",
1776 1,
1777 GNUNET_NO);
1778 return;
1779 }
1780 if (GNUNET_NO ==
1781 GNUNET_BLOCK_check_block (GDS_block_context,
1782 bd.type,
1783 bd.data,
1784 bd.data_size))
1785 {
1786 GNUNET_break_op (0);
1787 return;
1788 }
1789 if (0 == (options & GNUNET_DHT_RO_RECORD_ROUTE))
1790 putlen = 0;
1791 GNUNET_STATISTICS_update (GDS_stats,
1792 "# P2P PUT requests received",
1793 1,
1794 GNUNET_NO);
1795 GNUNET_STATISTICS_update (GDS_stats,
1796 "# P2P PUT bytes received",
1797 msize,
1798 GNUNET_NO);
1799 {
1800 struct GNUNET_HashCode test_key;
1801 enum GNUNET_GenericReturnValue ret;
1802
1803 ret = GNUNET_BLOCK_get_key (GDS_block_context,
1804 bd.type,
1805 bd.data,
1806 bd.data_size,
1807 &test_key);
1808 switch (ret)
1809 {
1810 case GNUNET_YES:
1811 if (0 != GNUNET_memcmp (&test_key,
1812 &bd.key))
1813 {
1814 GNUNET_break_op (0);
1815 return;
1816 }
1817 break;
1818 case GNUNET_NO:
1819 /* cannot verify, good luck */
1820 break;
1821 case GNUNET_SYSERR:
1822 /* block type not supported, good luck */
1823 break;
1824 }
1825 }
1826
1827 {
1828 struct GNUNET_CONTAINER_BloomFilter *bf;
1829 struct GNUNET_DHT_PathElement pp[putlen + 1];
1830
1831 bf = GNUNET_CONTAINER_bloomfilter_init (put->bloomfilter,
1832 DHT_BLOOM_SIZE,
1833 GNUNET_CONSTANTS_BLOOMFILTER_K);
1834 GNUNET_break_op (GNUNET_YES ==
1835 GNUNET_CONTAINER_bloomfilter_test (bf,
1836 &peer->phash));
1837 /* extend 'put path' by sender */
1838 bd.put_path = (const struct GNUNET_DHT_PathElement *) pp;
1839 bd.put_path_length = putlen + 1;
1840 if (0 != (options & GNUNET_DHT_RO_RECORD_ROUTE))
1841 {
1842 unsigned int failure_offset;
1843
1844 GNUNET_memcpy (pp,
1845 put_path,
1846 putlen * sizeof(struct GNUNET_DHT_PathElement));
1847 pp[putlen].pred = peer->id;
1848 /* zero-out signature, not valid until we actually do forward! */
1849 memset (&pp[putlen].sig,
1850 0,
1851 sizeof (pp[putlen].sig));
1852#if SANITY_CHECKS
1853 /* TODO: might want to eventually implement probabilistic
1854 load-based path verification, but for now it is all or nothing */
1855 failure_offset
1856 = GNUNET_DHT_verify_path (bd.data,
1857 bd.data_size,
1858 bd.expiration_time,
1859 pp,
1860 putlen + 1,
1861 NULL, 0, /* get_path */
1862 &GDS_my_identity);
1863#else
1864 failure_offset = 0;
1865#endif
1866 if (0 != failure_offset)
1867 {
1868 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
1869 "Recorded put path invalid at offset %u, truncating\n",
1870 failure_offset);
1871 GNUNET_assert (failure_offset <= putlen);
1872 bd.put_path = &pp[failure_offset];
1873 bd.put_path_length = putlen - failure_offset;
1874 }
1875 }
1876 else
1877 {
1878 bd.put_path_length = 0;
1879 }
1880
1881 /* give to local clients */
1882 GNUNET_break (GDS_CLIENTS_handle_reply (&bd,
1883 &bd.key,
1884 0, NULL /* get path */));
1885
1886 /* store locally */
1887 if ( (0 != (options & GNUNET_DHT_RO_DEMULTIPLEX_EVERYWHERE)) ||
1888 (GDS_am_closest_peer (&put->key,
1889 bf)) )
1890 GDS_DATACACHE_handle_put (&bd);
1891 {
1892 enum GNUNET_GenericReturnValue forwarded;
1893
1894 /* route to other peers */
1895 forwarded
1896 = GDS_NEIGHBOURS_handle_put (&bd,
1897 options,
1898 ntohs (put->desired_replication_level),
1899 ntohs (put->hop_count),
1900 bf);
1901 /* notify monitoring clients */
1902 GDS_CLIENTS_process_put (options
1903 | ((GNUNET_OK == forwarded)
1904 ? GNUNET_DHT_RO_LAST_HOP
1905 : 0),
1906 &bd,
1907 ntohs (put->hop_count),
1908 ntohs (put->desired_replication_level));
1909 }
1910 GNUNET_CONTAINER_bloomfilter_free (bf);
1911 }
1912}
1913
1914
1915/**
1916 * We have received a request for a HELLO. Sends our
1917 * HELLO back.
1918 *
1919 * @param pi sender of the request
1920 * @param key peers close to this key are desired
1921 * @param bg group for filtering peers
1922 */
1923static void
1924handle_find_my_hello (struct PeerInfo *pi,
1925 const struct GNUNET_HashCode *query_hash,
1926 struct GNUNET_BLOCK_Group *bg)
1927{
1928 size_t block_size = 0;
1929
1930 /* TODO: consider caching our HELLO block for a bit, to
1931 avoid signing too often here... */
1932 GNUNET_break (GNUNET_NO ==
1933 GNUNET_HELLO_builder_to_block (GDS_my_hello,
1934 &GDS_my_private_key,
1935 NULL,
1936 &block_size));
1937 {
1938 char block[block_size];
1939
1940 if (GNUNET_OK !=
1941 GNUNET_HELLO_builder_to_block (GDS_my_hello,
1942 &GDS_my_private_key,
1943 block,
1944 &block_size))
1945 {
1946 GNUNET_STATISTICS_update (GDS_stats,
1947 "# FIND PEER requests ignored due to lack of HELLO",
1948 1,
1949 GNUNET_NO);
1950 }
1951 else if (GNUNET_BLOCK_REPLY_OK_MORE ==
1952 GNUNET_BLOCK_check_reply (GDS_block_context,
1953 GNUNET_BLOCK_TYPE_DHT_URL_HELLO,
1954 bg,
1955 &GDS_my_identity_hash,
1956 NULL, 0,
1957 block,
1958 block_size))
1959 {
1960 struct GDS_DATACACHE_BlockData bd = {
1961 .type = GNUNET_BLOCK_TYPE_DHT_URL_HELLO,
1962 .expiration_time
1963 = GNUNET_TIME_relative_to_absolute (
1964 GNUNET_HELLO_ADDRESS_EXPIRATION),
1965 .key = GDS_my_identity_hash,
1966 .data = block,
1967 .data_size = block_size
1968 };
1969
1970 GNUNET_break (GDS_NEIGHBOURS_handle_reply (pi,
1971 &bd,
1972 query_hash,
1973 0, NULL /* get path */));
1974 }
1975 else
1976 {
1977 GNUNET_STATISTICS_update (GDS_stats,
1978 "# FIND PEER requests ignored due to Bloomfilter",
1979 1,
1980 GNUNET_NO);
1981 }
1982 }
1983}
1984
1985
1986/**
1987 * We have received a request for nearby HELLOs. Sends matching
1988 * HELLOs back.
1989 *
1990 * @param pi sender of the request
1991 * @param key peers close to this key are desired
1992 * @param bg group for filtering peers
1993 */
1994static void
1995handle_find_local_hello (struct PeerInfo *pi,
1996 const struct GNUNET_HashCode *query_hash,
1997 struct GNUNET_BLOCK_Group *bg)
1998{
1999 /* Force non-random selection by hop count */
2000 struct PeerInfo *peer;
2001
2002 peer = select_peer (query_hash,
2003 NULL,
2004 GDS_NSE_get () + 1);
2005 if ( (NULL != peer->hello) &&
2006 (! GNUNET_TIME_absolute_is_past (peer->hello_expiration)) &&
2007 (GNUNET_BLOCK_REPLY_OK_MORE ==
2008 GNUNET_BLOCK_check_reply (
2009 GDS_block_context,
2010 GNUNET_BLOCK_TYPE_DHT_URL_HELLO,
2011 bg,
2012 &peer->phash,
2013 NULL, 0, /* xquery */
2014 peer->hello,
2015 peer->hello_size)) )
2016 {
2017 struct GDS_DATACACHE_BlockData bd = {
2018 .type = GNUNET_BLOCK_TYPE_DHT_URL_HELLO,
2019 .expiration_time = peer->hello_expiration,
2020 .key = peer->phash,
2021 .data = peer->hello,
2022 .data_size = peer->hello_size
2023 };
2024
2025 GNUNET_break (GDS_NEIGHBOURS_handle_reply (pi,
2026 &bd,
2027 query_hash,
2028 0, NULL /* get path */));
2029 }
2030}
2031
2032
2033/**
2034 * Handle an exact result from local datacache for a GET operation.
2035 *
2036 * @param cls the `struct PeerInfo` for which this is a reply
2037 * @param bd details about the block we found locally
2038 */
2039static void
2040handle_local_result (void *cls,
2041 const struct GDS_DATACACHE_BlockData *bd)
2042{
2043 struct PeerInfo *peer = cls;
2044
2045 GNUNET_break (GDS_NEIGHBOURS_handle_reply (peer,
2046 bd,
2047 &bd->key,
2048 0, NULL /* get path */));
2049}
2050
2051
2052/**
2053 * Check validity of p2p get request.
2054 *
2055 * @param cls closure with the `struct Target` of the sender
2056 * @param get the message
2057 * @return #GNUNET_OK if the message is well-formed
2058 */
2059static enum GNUNET_GenericReturnValue
2060check_dht_p2p_get (void *cls,
2061 const struct PeerGetMessage *get)
2062{
2063 uint16_t msize = ntohs (get->header.size);
2064 uint16_t result_filter_size = ntohs (get->result_filter_size);
2065
2066 (void) cls;
2067 if (msize < sizeof(*get) + result_filter_size)
2068 {
2069 GNUNET_break_op (0);
2070 return GNUNET_SYSERR;
2071 }
2072 return GNUNET_OK;
2073}
2074
2075
2076/**
2077 * Core handler for p2p get requests.
2078 *
2079 * @param cls closure with the `struct Target` of the sender
2080 * @param get the message
2081 */
2082static void
2083handle_dht_p2p_get (void *cls,
2084 const struct PeerGetMessage *get)
2085{
2086 struct Target *t = cls;
2087 struct PeerInfo *peer = t->pi;
2088 uint16_t msize = ntohs (get->header.size);
2089 uint16_t result_filter_size = ntohs (get->result_filter_size);
2090 uint16_t hop_count = ntohs (get->hop_count);
2091 enum GNUNET_BLOCK_Type type = (enum GNUNET_BLOCK_Type) ntohl (get->type);
2092 enum GNUNET_DHT_RouteOption options = (enum GNUNET_DHT_RouteOption) ntohs (
2093 get->options);
2094 enum GNUNET_BLOCK_ReplyEvaluationResult eval = GNUNET_BLOCK_REPLY_OK_MORE;
2095 const void *result_filter = (const void *) &get[1];
2096 const void *xquery = result_filter + result_filter_size;
2097 size_t xquery_size = msize - sizeof (*get) - result_filter_size;
2098
2099 /* parse and validate message */
2100 GNUNET_STATISTICS_update (GDS_stats,
2101 "# P2P GET requests received",
2102 1,
2103 GNUNET_NO);
2104 GNUNET_STATISTICS_update (GDS_stats,
2105 "# P2P GET bytes received",
2106 msize,
2107 GNUNET_NO);
2108 if (GNUNET_NO ==
2109 GNUNET_BLOCK_check_query (GDS_block_context,
2110 type,
2111 &get->key,
2112 xquery,
2113 xquery_size))
2114 {
2115 /* request invalid */
2116 GNUNET_break_op (0);
2117 return;
2118 }
2119
2120 {
2121 struct GNUNET_BLOCK_Group *bg;
2122 struct GNUNET_CONTAINER_BloomFilter *peer_bf;
2123
2124 peer_bf = GNUNET_CONTAINER_bloomfilter_init (get->bloomfilter,
2125 DHT_BLOOM_SIZE,
2126 GNUNET_CONSTANTS_BLOOMFILTER_K);
2127 GNUNET_break_op (GNUNET_YES ==
2128 GNUNET_CONTAINER_bloomfilter_test (peer_bf,
2129 &peer->phash));
2130 bg = GNUNET_BLOCK_group_create (GDS_block_context,
2131 type,
2132 result_filter,
2133 result_filter_size,
2134 "filter-size",
2135 result_filter_size,
2136 NULL);
2137 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2138 "GET for %s at %s after %u hops\n",
2139 GNUNET_h2s (&get->key),
2140 GNUNET_i2s (&GDS_my_identity),
2141 (unsigned int) hop_count);
2142 /* local lookup (this may update the bg) */
2143 if ( (0 != (options & GNUNET_DHT_RO_DEMULTIPLEX_EVERYWHERE)) ||
2144 (GDS_am_closest_peer (&get->key,
2145 peer_bf)) )
2146 {
2147 if (GNUNET_BLOCK_TYPE_DHT_URL_HELLO == type)
2148 {
2149 GNUNET_STATISTICS_update (GDS_stats,
2150 "# P2P HELLO lookup requests processed",
2151 1,
2152 GNUNET_NO);
2153 handle_find_my_hello (peer,
2154 &get->key,
2155 bg);
2156 if (0 != (options & GNUNET_DHT_RO_FIND_APPROXIMATE))
2157 handle_find_local_hello (peer,
2158 &get->key,
2159 bg);
2160 }
2161 else
2162 {
2163 if (0 != (options & GNUNET_DHT_RO_FIND_APPROXIMATE))
2164 eval = GDS_DATACACHE_get_closest (&get->key,
2165 type,
2166 xquery,
2167 xquery_size,
2168 bg,
2169 &handle_local_result,
2170 peer);
2171 else
2172 eval = GDS_DATACACHE_handle_get (&get->key,
2173 type,
2174 xquery,
2175 xquery_size,
2176 bg,
2177 &handle_local_result,
2178 peer);
2179 }
2180 }
2181 else
2182 {
2183 GNUNET_STATISTICS_update (GDS_stats,
2184 "# P2P GET requests ONLY routed",
2185 1,
2186 GNUNET_NO);
2187 }
2188
2189 /* remember request for routing replies
2190 TODO: why should we do this if GNUNET_BLOCK_REPLY_OK_LAST == eval?
2191 */
2192 GDS_ROUTING_add (&peer->id,
2193 type,
2194 bg, /* bg now owned by routing, but valid at least until end of this function! */
2195 options,
2196 &get->key,
2197 xquery,
2198 xquery_size);
2199
2200 /* P2P forwarding */
2201 {
2202 bool forwarded = false;
2203 uint16_t desired_replication_level = ntohs (
2204 get->desired_replication_level);
2205
2206 if (eval != GNUNET_BLOCK_REPLY_OK_LAST)
2207 forwarded = (GNUNET_OK ==
2208 GDS_NEIGHBOURS_handle_get (type,
2209 options,
2210 desired_replication_level,
2211 hop_count,
2212 &get->key,
2213 xquery,
2214 xquery_size,
2215 bg,
2216 peer_bf));
2217 GDS_CLIENTS_process_get (
2218 options
2219 | (forwarded
2220 ? 0
2221 : GNUNET_DHT_RO_LAST_HOP),
2222 type,
2223 hop_count,
2224 desired_replication_level,
2225 0,
2226 NULL,
2227 &get->key);
2228 }
2229 /* clean up; note that 'bg' is owned by routing now! */
2230 GNUNET_CONTAINER_bloomfilter_free (peer_bf);
2231 }
2232}
2233
2234
2235/**
2236 * Process a reply, after the @a get_path has been updated.
2237 *
2238 * @param bd block details
2239 * @param query_hash hash of the original query, might not match key in @a bd
2240 * @param get_path_length number of entries in @a get_path
2241 * @param get_path path the reply has taken
2242 * @return true on success
2243 */
2244static bool
2245process_reply_with_path (const struct GDS_DATACACHE_BlockData *bd,
2246 const struct GNUNET_HashCode *query_hash,
2247 unsigned int get_path_length,
2248 const struct GNUNET_DHT_PathElement *get_path)
2249{
2250 /* forward to local clients */
2251 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2252 "Forwarding reply to local clients\n");
2253 if (! GDS_CLIENTS_handle_reply (bd,
2254 query_hash,
2255 get_path_length,
2256 get_path))
2257 {
2258 GNUNET_break (0);
2259 return false;
2260 }
2261 GDS_CLIENTS_process_get_resp (bd,
2262 get_path,
2263 get_path_length);
2264 if (GNUNET_YES == cache_results)
2265 {
2266 struct GNUNET_DHT_PathElement xput_path[GNUNET_NZL (get_path_length
2267 + bd->put_path_length)];
2268 struct GDS_DATACACHE_BlockData bdx = *bd;
2269
2270 GNUNET_memcpy (xput_path,
2271 bd->put_path,
2272 bd->put_path_length * sizeof(struct GNUNET_DHT_PathElement));
2273 GNUNET_memcpy (&xput_path[bd->put_path_length],
2274 get_path,
2275 get_path_length * sizeof(struct GNUNET_DHT_PathElement));
2276 bdx.put_path = xput_path;
2277 bdx.put_path_length += get_path_length;
2278 GDS_DATACACHE_handle_put (&bdx);
2279 }
2280 /* forward to other peers */
2281 GDS_ROUTING_process (bd,
2282 query_hash,
2283 get_path_length,
2284 get_path);
2285 return true;
2286}
2287
2288
2289/**
2290 * Check validity of p2p result message.
2291 *
2292 * @param cls closure
2293 * @param message message
2294 * @return #GNUNET_YES if the message is well-formed
2295 */
2296static enum GNUNET_GenericReturnValue
2297check_dht_p2p_result (void *cls,
2298 const struct PeerResultMessage *prm)
2299{
2300 uint16_t get_path_length = ntohs (prm->get_path_length);
2301 uint16_t put_path_length = ntohs (prm->put_path_length);
2302 uint16_t msize = ntohs (prm->header.size);
2303
2304 (void) cls;
2305 if ( (msize <
2306 sizeof(struct PeerResultMessage)
2307 + (get_path_length + put_path_length)
2308 * sizeof(struct GNUNET_DHT_PathElement)) ||
2309 (get_path_length >
2310 GNUNET_MAX_MESSAGE_SIZE / sizeof(struct GNUNET_DHT_PathElement)) ||
2311 (put_path_length >
2312 GNUNET_MAX_MESSAGE_SIZE / sizeof(struct GNUNET_DHT_PathElement)) )
2313 {
2314 GNUNET_break_op (0);
2315 return GNUNET_SYSERR;
2316 }
2317 return GNUNET_OK;
2318}
2319
2320
2321/**
2322 * Core handler for p2p result messages.
2323 *
2324 * @param cls closure
2325 * @param message message
2326 */
2327static void
2328handle_dht_p2p_result (void *cls,
2329 const struct PeerResultMessage *prm)
2330{
2331 struct Target *t = cls;
2332 struct PeerInfo *peer = t->pi;
2333 uint16_t msize = ntohs (prm->header.size);
2334 uint16_t get_path_length = ntohs (prm->get_path_length);
2335 struct GDS_DATACACHE_BlockData bd = {
2336 .expiration_time = GNUNET_TIME_absolute_ntoh (prm->expiration_time),
2337 .put_path = (const struct GNUNET_DHT_PathElement *) &prm[1],
2338 .put_path_length = ntohs (prm->put_path_length),
2339 .key = prm->key,
2340 .type = ntohl (prm->type)
2341 };
2342 const struct GNUNET_DHT_PathElement *get_path
2343 = &bd.put_path[bd.put_path_length];
2344
2345 /* parse and validate message */
2346 if (GNUNET_TIME_absolute_is_past (bd.expiration_time))
2347 {
2348 GNUNET_STATISTICS_update (GDS_stats,
2349 "# Expired results discarded",
2350 1,
2351 GNUNET_NO);
2352 return;
2353 }
2354 get_path = &bd.put_path[bd.put_path_length];
2355 bd.data = (const void *) &get_path[get_path_length];
2356 bd.data_size = msize - (sizeof(struct PeerResultMessage)
2357 + (get_path_length + bd.put_path_length)
2358 * sizeof(struct GNUNET_DHT_PathElement));
2359 if (GNUNET_OK !=
2360 GNUNET_BLOCK_check_block (GDS_block_context,
2361 bd.type,
2362 bd.data,
2363 bd.data_size))
2364 {
2365 GNUNET_break_op (0);
2366 return;
2367 }
2368 GNUNET_STATISTICS_update (GDS_stats,
2369 "# P2P RESULTS received",
2370 1,
2371 GNUNET_NO);
2372 GNUNET_STATISTICS_update (GDS_stats,
2373 "# P2P RESULT bytes received",
2374 msize,
2375 GNUNET_NO);
2376 {
2377 enum GNUNET_GenericReturnValue ret;
2378
2379 ret = GNUNET_BLOCK_get_key (GDS_block_context,
2380 bd.type,
2381 bd.data,
2382 bd.data_size,
2383 &bd.key);
2384 if (GNUNET_NO == ret)
2385 bd.key = prm->key;
2386 }
2387
2388 /* if we got a HELLO, consider it for our own routing table */
2389 hello_check (&bd);
2390
2391 /* Need to append 'peer' to 'get_path' */
2392 {
2393 struct GNUNET_DHT_PathElement xget_path[get_path_length + 1];
2394 struct GNUNET_DHT_PathElement *gp = xget_path;
2395 unsigned int failure_offset;
2396
2397 GNUNET_memcpy (xget_path,
2398 get_path,
2399 get_path_length * sizeof(struct GNUNET_DHT_PathElement));
2400 xget_path[get_path_length].pred = peer->id;
2401 memset (&xget_path[get_path_length].sig,
2402 0,
2403 sizeof (xget_path[get_path_length].sig));
2404#if SANITY_CHECKS
2405 /* TODO: might want to eventually implement probabilistic
2406 load-based path verification, but for now it is all or nothing */
2407 failure_offset
2408 = GNUNET_DHT_verify_path (bd.data,
2409 bd.data_size,
2410 bd.expiration_time,
2411 bd.put_path,
2412 bd.put_path_length,
2413 xget_path,
2414 get_path_length + 1,
2415 &GDS_my_identity);
2416#else
2417 failure_offset = 0;
2418#endif
2419 if (0 != failure_offset)
2420 {
2421 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
2422 "Recorded path invalid at offset %u, truncating\n",
2423 failure_offset);
2424 GNUNET_assert (failure_offset <= bd.put_path_length + get_path_length);
2425 if (failure_offset >= bd.put_path_length)
2426 {
2427 /* failure on get path */
2428 get_path_length -= (failure_offset - bd.put_path_length);
2429 gp = &xget_path[failure_offset - bd.put_path_length];
2430 bd.put_path_length = 0;
2431 }
2432 else
2433 {
2434 /* failure on put path */
2435 bd.put_path = &bd.put_path[failure_offset];
2436 bd.put_path_length -= failure_offset;
2437 }
2438 }
2439 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2440 "Extending GET path of length %u with %s\n",
2441 get_path_length,
2442 GNUNET_i2s (&peer->id));
2443 GNUNET_break (process_reply_with_path (&bd,
2444 &prm->key,
2445 get_path_length + 1,
2446 gp));
2447 }
2448}
2449
2450
2451/**
2452 * Check validity of a p2p hello message.
2453 *
2454 * @param cls closure
2455 * @param hello message
2456 * @return #GNUNET_YES if the message is well-formed
2457 */
2458static enum GNUNET_GenericReturnValue
2459check_dht_p2p_hello (void *cls,
2460 const struct GNUNET_MessageHeader *hello)
2461{
2462 struct Target *t = cls;
2463 struct PeerInfo *peer = t->pi;
2464 enum GNUNET_GenericReturnValue ret;
2465 size_t hellob_size;
2466 void *hellob;
2467 struct GNUNET_TIME_Absolute expiration;
2468
2469 ret = GNUNET_HELLO_dht_msg_to_block (hello,
2470 &peer->id,
2471 &hellob,
2472 &hellob_size,
2473 &expiration);
2474 GNUNET_free (hellob);
2475 return ret;
2476}
2477
2478
2479/**
2480 * Core handler for p2p HELLO messages.
2481 *
2482 * @param cls closure
2483 * @param message message
2484 */
2485static void
2486handle_dht_p2p_hello (void *cls,
2487 const struct GNUNET_MessageHeader *hello)
2488{
2489 struct Target *t = cls;
2490 struct PeerInfo *peer = t->pi;
2491
2492 GNUNET_free (peer->hello);
2493 peer->hello_size = 0;
2494 GNUNET_break (GNUNET_OK ==
2495 GNUNET_HELLO_dht_msg_to_block (hello,
2496 &peer->id,
2497 &peer->hello,
2498 &peer->hello_size,
2499 &peer->hello_expiration));
2500}
2501
2502
2503void
2504GDS_u_receive (void *cls,
2505 void **tctx,
2506 void **sctx,
2507 const void *message,
2508 size_t message_size)
2509{
2510 struct Target *t = *tctx;
2511 struct GNUNET_MQ_MessageHandler core_handlers[] = {
2512 GNUNET_MQ_hd_var_size (dht_p2p_get,
2513 GNUNET_MESSAGE_TYPE_DHT_P2P_GET,
2514 struct PeerGetMessage,
2515 t),
2516 GNUNET_MQ_hd_var_size (dht_p2p_put,
2517 GNUNET_MESSAGE_TYPE_DHT_P2P_PUT,
2518 struct PeerPutMessage,
2519 t),
2520 GNUNET_MQ_hd_var_size (dht_p2p_result,
2521 GNUNET_MESSAGE_TYPE_DHT_P2P_RESULT,
2522 struct PeerResultMessage,
2523 t),
2524 GNUNET_MQ_hd_var_size (dht_p2p_hello,
2525 GNUNET_MESSAGE_TYPE_DHT_P2P_HELLO,
2526 struct GNUNET_MessageHeader,
2527 t),
2528 GNUNET_MQ_handler_end ()
2529 };
2530 const struct GNUNET_MessageHeader *mh = message;
2531
2532 (void) cls; /* the 'struct GDS_Underlay' */
2533 (void) sctx; /* our receiver address */
2534 if (NULL == t)
2535 {
2536 /* Received message claiming to originate from myself?
2537 Ignore! */
2538 GNUNET_break_op (0);
2539 return;
2540 }
2541 if (message_size < sizeof (*mh))
2542 {
2543 GNUNET_break_op (0);
2544 return;
2545 }
2546 if (message_size != ntohs (mh->size))
2547 {
2548 GNUNET_break_op (0);
2549 return;
2550 }
2551 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2552 "Handling message of type %u from peer %s\n",
2553 ntohs (mh->type),
2554 GNUNET_i2s (&t->pi->id));
2555 if (GNUNET_OK !=
2556 GNUNET_MQ_handle_message (core_handlers,
2557 mh))
2558 {
2559 GNUNET_break_op (0);
2560 return;
2561 }
2562}
2563
2564
2565/**
2566 * Callback function used to extract URIs from a builder.
2567 * Called when we should consider connecting to a peer.
2568 *
2569 * @param cls closure pointing to a `struct GNUNET_PeerIdentity *`
2570 * @param uri one of the URIs
2571 */
2572void
2573GDS_try_connect (void *cls,
2574 const char *uri)
2575{
2576 const struct GNUNET_PeerIdentity *pid = cls;
2577 struct GNUNET_HashCode phash;
2578 int peer_bucket;
2579 struct PeerBucket *bucket;
2580
2581 if (0 == GNUNET_memcmp (&GDS_my_identity,
2582 pid))
2583 {
2584 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2585 "Got a HELLO for my own PID, ignoring it\n");
2586 return; /* that's us! */
2587 }
2588 GNUNET_CRYPTO_hash (pid,
2589 sizeof(*pid),
2590 &phash);
2591 peer_bucket = find_bucket (&phash);
2592 GNUNET_assert ( (peer_bucket >= 0) &&
2593 ((unsigned int) peer_bucket < MAX_BUCKETS));
2594 bucket = &k_buckets[peer_bucket];
2595 if (bucket->peers_size >= bucket_size)
2596 return; /* do not care */
2597 for (struct PeerInfo *pi = bucket->head;
2598 NULL != pi;
2599 pi = pi->next)
2600 if (0 ==
2601 GNUNET_memcmp (&pi->id,
2602 pid))
2603 {
2604 /* already connected */
2605 /* TODO: maybe consider 'uri' anyway as an additional
2606 alternative address??? */
2607 return;
2608 }
2609 GNUNET_log (GNUNET_ERROR_TYPE_INFO,
2610 "Discovered peer %s at %s suitable for bucket %d (%u/%u), trying to connect\n",
2611 GNUNET_i2s (pid),
2612 uri,
2613 peer_bucket,
2614 bucket->peers_size,
2615 bucket_size);
2616 /* new peer that we like! */
2617 GDS_u_try_connect (pid,
2618 uri);
2619}
2620
2621
2622/**
2623 * Send @a msg to all peers in our buckets.
2624 *
2625 * @param msg message to broadcast
2626 */
2627void
2628GDS_NEIGHBOURS_broadcast (const struct GNUNET_MessageHeader *msg)
2629{
2630 for (unsigned int bc = 0; bc<closest_bucket; bc++)
2631 {
2632 struct PeerBucket *bucket = &k_buckets[bc];
2633 unsigned int count = 0;
2634
2635 for (struct PeerInfo *pos = bucket->head;
2636 NULL != pos;
2637 pos = pos->next)
2638 {
2639 if (count >= bucket_size)
2640 break; /* we only consider first #bucket_size entries per bucket */
2641 count++;
2642 do_send (pos,
2643 msg);
2644 }
2645 }
2646}
2647
2648
2649enum GNUNET_GenericReturnValue
2650GDS_NEIGHBOURS_init ()
2651{
2652
2653 unsigned long long temp_config_num;
2654
2655 disable_try_connect
2656 = GNUNET_CONFIGURATION_get_value_yesno (GDS_cfg,
2657 "DHT",
2658 "DISABLE_TRY_CONNECT");
2659 if (GNUNET_OK ==
2660 GNUNET_CONFIGURATION_get_value_number (GDS_cfg,
2661 "DHT",
2662 "bucket_size",
2663 &temp_config_num))
2664 bucket_size = (unsigned int) temp_config_num;
2665 cache_results
2666 = GNUNET_CONFIGURATION_get_value_yesno (GDS_cfg,
2667 "DHT",
2668 "CACHE_RESULTS");
2669 all_connected_peers = GNUNET_CONTAINER_multipeermap_create (256,
2670 GNUNET_YES);
2671 return GNUNET_OK;
2672}
2673
2674
2675void
2676GDS_NEIGHBOURS_done ()
2677{
2678 if (NULL == all_connected_peers)
2679 return;
2680 GNUNET_assert (0 ==
2681 GNUNET_CONTAINER_multipeermap_size (all_connected_peers));
2682 GNUNET_CONTAINER_multipeermap_destroy (all_connected_peers);
2683 all_connected_peers = NULL;
2684 GNUNET_assert (NULL == find_peer_task);
2685}
2686
2687
2688struct GNUNET_PeerIdentity *
2689GDS_NEIGHBOURS_get_id ()
2690{
2691 return &GDS_my_identity;
2692}
2693
2694
2695/* end of gnunet-service-dht_neighbours.c */
generated by cgit v1.2.3 (git 2.39.1) at 2024-04-18 14:55:36 +0000