2 This file is part of GNUnet.
3 Copyright (C) 2009-2017 GNUnet e.V.
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.
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.
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/>.
18 SPDX-License-Identifier: AGPL3.0-or-later
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
28 #include "gnunet_util_lib.h"
29 #include "gnunet_block_lib.h"
30 #include "gnunet_hello_lib.h"
31 #include "gnunet_constants.h"
32 #include "gnunet_protocols.h"
33 #include "gnunet_nse_service.h"
34 #include "gnunet_ats_service.h"
35 #include "gnunet_core_service.h"
36 #include "gnunet_datacache_lib.h"
37 #include "gnunet_transport_service.h"
38 #include "gnunet_hello_lib.h"
39 #include "gnunet_dht_service.h"
40 #include "gnunet_statistics_service.h"
41 #include "gnunet-service-dht.h"
42 #include "gnunet-service-dht_datacache.h"
43 #include "gnunet-service-dht_hello.h"
44 #include "gnunet-service-dht_neighbours.h"
45 #include "gnunet-service-dht_nse.h"
46 #include "gnunet-service-dht_routing.h"
49 #define LOG_TRAFFIC(kind, ...) GNUNET_log_from (kind, "dht-traffic", \
53 * Enable slow sanity checks to debug issues.
55 #define SANITY_CHECKS 1
58 * How many buckets will we allow total.
60 #define MAX_BUCKETS sizeof(struct GNUNET_HashCode) * 8
63 * What is the maximum number of peers in a given bucket.
65 #define DEFAULT_BUCKET_SIZE 8
68 * Desired replication level for FIND PEER requests
70 #define FIND_PEER_REPLICATION_LEVEL 4
73 * Maximum allowed replication level for all requests.
75 #define MAXIMUM_REPLICATION_LEVEL 16
78 * Maximum allowed number of pending messages per peer.
80 #define MAXIMUM_PENDING_PER_PEER 64
83 * How long at least to wait before sending another find peer request.
85 #define DHT_MINIMUM_FIND_PEER_INTERVAL GNUNET_TIME_relative_multiply ( \
86 GNUNET_TIME_UNIT_SECONDS, 30)
89 * How long at most to wait before sending another find peer request.
91 #define DHT_MAXIMUM_FIND_PEER_INTERVAL GNUNET_TIME_relative_multiply ( \
92 GNUNET_TIME_UNIT_MINUTES, 10)
95 * How long at most to wait for transmission of a GET request to another peer?
97 #define GET_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 2)
100 * Hello address expiration
102 extern struct GNUNET_TIME_Relative hello_expiration;
105 GNUNET_NETWORK_STRUCT_BEGIN
110 struct PeerPutMessage
113 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_PUT
115 struct GNUNET_MessageHeader header;
120 uint32_t options GNUNET_PACKED;
125 uint32_t type GNUNET_PACKED;
130 uint32_t hop_count GNUNET_PACKED;
133 * Replication level for this message
135 uint32_t desired_replication_level GNUNET_PACKED;
138 * Length of the PUT path that follows (if tracked).
140 uint32_t put_path_length GNUNET_PACKED;
143 * When does the content expire?
145 struct GNUNET_TIME_AbsoluteNBO expiration_time;
148 * Bloomfilter (for peer identities) to stop circular routes
150 char bloomfilter[DHT_BLOOM_SIZE];
153 * The key we are storing under.
155 struct GNUNET_HashCode key;
157 /* put path (if tracked) */
166 struct PeerResultMessage
169 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_RESULT
171 struct GNUNET_MessageHeader header;
176 uint32_t type GNUNET_PACKED;
179 * Length of the PUT path that follows (if tracked).
181 uint32_t put_path_length GNUNET_PACKED;
184 * Length of the GET path that follows (if tracked).
186 uint32_t get_path_length GNUNET_PACKED;
189 * When does the content expire?
191 struct GNUNET_TIME_AbsoluteNBO expiration_time;
194 * The key of the corresponding GET request.
196 struct GNUNET_HashCode key;
198 /* put path (if tracked) */
200 /* get path (if tracked) */
209 struct PeerGetMessage
212 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_GET
214 struct GNUNET_MessageHeader header;
219 uint32_t options GNUNET_PACKED;
222 * Desired content type.
224 uint32_t type GNUNET_PACKED;
229 uint32_t hop_count GNUNET_PACKED;
232 * Desired replication level for this request.
234 uint32_t desired_replication_level GNUNET_PACKED;
237 * Size of the extended query.
239 uint32_t xquery_size;
242 * Bloomfilter mutator.
247 * Bloomfilter (for peer identities) to stop circular routes
249 char bloomfilter[DHT_BLOOM_SIZE];
252 * The key we are looking for.
254 struct GNUNET_HashCode key;
258 /* result bloomfilter */
260 GNUNET_NETWORK_STRUCT_END
264 * Entry for a peer in a bucket.
269 * Next peer entry (DLL)
271 struct PeerInfo *next;
274 * Prev peer entry (DLL)
276 struct PeerInfo *prev;
279 * Handle for sending messages to this peer.
281 struct GNUNET_MQ_Handle *mq;
284 * What is the identity of the peer?
286 const struct GNUNET_PeerIdentity *id;
291 struct GNUNET_HashCode phash;
294 * Which bucket is this peer in?
301 * Peers are grouped into buckets.
308 struct PeerInfo *head;
313 struct PeerInfo *tail;
316 * Number of peers in the bucket.
318 unsigned int peers_size;
323 * Information about a peer that we would like to connect to.
328 * Handle to active HELLO offer operation, or NULL.
330 struct GNUNET_TRANSPORT_OfferHelloHandle *oh;
333 * Handle to active connectivity suggestion operation, or NULL.
335 struct GNUNET_ATS_ConnectivitySuggestHandle *sh;
338 * How much would we like to connect to this peer?
345 * Do we cache all results that we are routing in the local datacache?
347 static int cache_results;
350 * Should routing details be logged to stderr (for debugging)?
352 static int log_route_details_stderr;
355 * The lowest currently used bucket, initially 0 (for 0-bits matching bucket).
357 static unsigned int closest_bucket;
360 * How many peers have we added since we sent out our last
363 static unsigned int newly_found_peers;
366 * Option for testing that disables the 'connect' function of the DHT.
368 static int disable_try_connect;
371 * The buckets. Array of size #MAX_BUCKETS. Offset 0 means 0 bits matching.
373 static struct PeerBucket k_buckets[MAX_BUCKETS];
376 * Hash map of all CORE-connected peers, for easy removal from
377 * #k_buckets on disconnect. Values are of type `struct PeerInfo`.
379 static struct GNUNET_CONTAINER_MultiPeerMap *all_connected_peers;
382 * Hash map of all peers we would like to be connected to.
383 * Values are of type `struct ConnectInfo`.
385 static struct GNUNET_CONTAINER_MultiPeerMap *all_desired_peers;
388 * Maximum size for each bucket.
390 static unsigned int bucket_size = DEFAULT_BUCKET_SIZE;
393 * Task that sends FIND PEER requests.
395 static struct GNUNET_SCHEDULER_Task *find_peer_task;
398 * Identity of this peer.
400 static struct GNUNET_PeerIdentity my_identity;
403 * Hash of the identity of this peer.
405 struct GNUNET_HashCode my_identity_hash;
410 static struct GNUNET_CORE_Handle *core_api;
413 * Handle to ATS connectivity.
415 static struct GNUNET_ATS_ConnectivityHandle *ats_ch;
419 * Find the optimal bucket for this key.
421 * @param hc the hashcode to compare our identity to
422 * @return the proper bucket index, or #GNUNET_SYSERR
423 * on error (same hashcode)
426 find_bucket (const struct GNUNET_HashCode *hc)
430 bits = GNUNET_CRYPTO_hash_matching_bits (&my_identity_hash, hc);
431 if (bits == MAX_BUCKETS)
433 /* How can all bits match? Got my own ID? */
435 return GNUNET_SYSERR;
437 return MAX_BUCKETS - bits - 1;
442 * Function called when #GNUNET_TRANSPORT_offer_hello() is done.
443 * Clean up the "oh" field in the @a cls
445 * @param cls a `struct ConnectInfo`
448 offer_hello_done (void *cls)
450 struct ConnectInfo *ci = cls;
457 * Function called for all entries in #all_desired_peers to clean up.
460 * @param peer peer the entry is for
461 * @param value the value to remove
462 * @return #GNUNET_YES
465 free_connect_info (void *cls,
466 const struct GNUNET_PeerIdentity *peer,
469 struct ConnectInfo *ci = value;
472 GNUNET_assert (GNUNET_YES ==
473 GNUNET_CONTAINER_multipeermap_remove (all_desired_peers,
478 GNUNET_ATS_connectivity_suggest_cancel (ci->sh);
483 GNUNET_TRANSPORT_offer_hello_cancel (ci->oh);
492 * Consider if we want to connect to a given peer, and if so
493 * let ATS know. If applicable, the HELLO is offered to the
496 * @param pid peer to consider connectivity requirements for
497 * @param h a HELLO message, or NULL
500 try_connect (const struct GNUNET_PeerIdentity *pid,
501 const struct GNUNET_MessageHeader *h)
504 struct GNUNET_HashCode pid_hash;
505 struct ConnectInfo *ci;
508 GNUNET_CRYPTO_hash (pid,
509 sizeof(struct GNUNET_PeerIdentity),
511 bucket = find_bucket (&pid_hash);
514 ci = GNUNET_CONTAINER_multipeermap_get (all_desired_peers,
517 if (k_buckets[bucket].peers_size < bucket_size)
518 strength = (bucket_size - k_buckets[bucket].peers_size) * bucket;
520 strength = bucket; /* minimum value of connectivity */
522 GNUNET_CONTAINER_multipeermap_contains (all_connected_peers,
524 strength *= 2; /* double for connected peers */
525 else if (k_buckets[bucket].peers_size > bucket_size)
526 strength = 0; /* bucket full, we really do not care about more */
528 if ((0 == strength) &&
531 /* release request */
532 GNUNET_assert (GNUNET_YES ==
533 free_connect_info (NULL,
540 ci = GNUNET_new (struct ConnectInfo);
541 GNUNET_assert (GNUNET_OK ==
542 GNUNET_CONTAINER_multipeermap_put (all_desired_peers,
545 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
547 if ((NULL != ci->oh) &&
549 GNUNET_TRANSPORT_offer_hello_cancel (ci->oh);
551 ci->oh = GNUNET_TRANSPORT_offer_hello (GDS_cfg,
555 if ((NULL != ci->sh) &&
556 (ci->strength != strength))
557 GNUNET_ATS_connectivity_suggest_cancel (ci->sh);
558 if (ci->strength != strength)
559 ci->sh = GNUNET_ATS_connectivity_suggest (ats_ch,
562 ci->strength = strength;
567 * Function called for each peer in #all_desired_peers during
568 * #update_connect_preferences() if we have reason to adjust
569 * the strength of our desire to keep connections to certain
570 * peers. Calls #try_connect() to update the calculations for
574 * @param pid peer to update
575 * @param value unused
576 * @return #GNUNET_YES (continue to iterate)
579 update_desire_strength (void *cls,
580 const struct GNUNET_PeerIdentity *pid,
592 * Update our preferences for connectivity as given to ATS.
594 * @param cls the `struct PeerInfo` of the peer
595 * @param tc scheduler context.
598 update_connect_preferences ()
600 GNUNET_CONTAINER_multipeermap_iterate (all_desired_peers,
601 &update_desire_strength,
607 * Add each of the peers we already know to the bloom filter of
608 * the request so that we don't get duplicate HELLOs.
610 * @param cls the `struct GNUNET_BLOCK_Group`
611 * @param key peer identity to add to the bloom filter
612 * @param value value the peer information (unused)
613 * @return #GNUNET_YES (we should continue to iterate)
616 add_known_to_bloom (void *cls,
617 const struct GNUNET_PeerIdentity *key,
620 struct GNUNET_BLOCK_Group *bg = cls;
621 struct GNUNET_HashCode key_hash;
625 GNUNET_CRYPTO_hash (key,
626 sizeof(struct GNUNET_PeerIdentity),
628 GNUNET_BLOCK_group_set_seen (bg,
631 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
632 "Adding known peer (%s) to bloomfilter for FIND PEER\n",
639 * Task to send a find peer message for our own peer identifier
640 * so that we can find the closest peers in the network to ourselves
641 * and attempt to connect to them.
643 * @param cls closure for this task
646 send_find_peer_message (void *cls)
648 struct GNUNET_TIME_Relative next_send_time;
649 struct GNUNET_BLOCK_Group *bg;
650 struct GNUNET_CONTAINER_BloomFilter *peer_bf;
653 find_peer_task = NULL;
654 if (newly_found_peers > bucket_size)
656 /* If we are finding many peers already, no need to send out our request right now! */
658 GNUNET_SCHEDULER_add_delayed (GNUNET_TIME_UNIT_MINUTES,
659 &send_find_peer_message,
661 newly_found_peers = 0;
664 bg = GNUNET_BLOCK_group_create (GDS_block_context,
665 GNUNET_BLOCK_TYPE_DHT_HELLO,
666 GNUNET_CRYPTO_random_u32 (
667 GNUNET_CRYPTO_QUALITY_WEAK,
674 GNUNET_CONTAINER_multipeermap_iterate (all_connected_peers,
677 GNUNET_STATISTICS_update (GDS_stats,
678 gettext_noop ("# FIND PEER messages initiated"),
682 = GNUNET_CONTAINER_bloomfilter_init (NULL,
684 GNUNET_CONSTANTS_BLOOMFILTER_K);
685 // FIXME: pass priority!?
686 GDS_NEIGHBOURS_handle_get (GNUNET_BLOCK_TYPE_DHT_HELLO,
687 GNUNET_DHT_RO_FIND_PEER
688 | GNUNET_DHT_RO_RECORD_ROUTE,
689 FIND_PEER_REPLICATION_LEVEL,
696 GNUNET_CONTAINER_bloomfilter_free (peer_bf);
697 GNUNET_BLOCK_group_destroy (bg);
698 /* schedule next round */
699 next_send_time.rel_value_us =
700 DHT_MINIMUM_FIND_PEER_INTERVAL.rel_value_us
701 + GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
702 DHT_MAXIMUM_FIND_PEER_INTERVAL.rel_value_us
703 / (newly_found_peers + 1));
704 newly_found_peers = 0;
705 GNUNET_assert (NULL == find_peer_task);
707 GNUNET_SCHEDULER_add_delayed (next_send_time,
708 &send_find_peer_message,
714 * Method called whenever a peer connects.
717 * @param peer peer identity this notification is about
718 * @param mq message queue for sending messages to @a peer
719 * @return our `struct PeerInfo` for @a peer
722 handle_core_connect (void *cls,
723 const struct GNUNET_PeerIdentity *peer,
724 struct GNUNET_MQ_Handle *mq)
729 /* Check for connect to self message */
730 if (0 == GNUNET_memcmp (&my_identity,
733 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
736 GNUNET_assert (GNUNET_NO ==
737 GNUNET_CONTAINER_multipeermap_get (all_connected_peers,
739 GNUNET_STATISTICS_update (GDS_stats,
740 gettext_noop ("# peers connected"),
743 pi = GNUNET_new (struct PeerInfo);
746 GNUNET_CRYPTO_hash (peer,
747 sizeof(struct GNUNET_PeerIdentity),
749 pi->peer_bucket = find_bucket (&pi->phash);
750 GNUNET_assert ((pi->peer_bucket >= 0) &&
751 ((unsigned int) pi->peer_bucket < MAX_BUCKETS));
752 GNUNET_CONTAINER_DLL_insert_tail (k_buckets[pi->peer_bucket].head,
753 k_buckets[pi->peer_bucket].tail,
755 k_buckets[pi->peer_bucket].peers_size++;
756 closest_bucket = GNUNET_MAX (closest_bucket,
757 (unsigned int) pi->peer_bucket);
758 GNUNET_assert (GNUNET_OK ==
759 GNUNET_CONTAINER_multipeermap_put (all_connected_peers,
762 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
763 if ((pi->peer_bucket > 0) &&
764 (k_buckets[pi->peer_bucket].peers_size <= bucket_size))
766 update_connect_preferences ();
769 if ((1 == GNUNET_CONTAINER_multipeermap_size (all_connected_peers)) &&
770 (GNUNET_YES != disable_try_connect))
772 /* got a first connection, good time to start with FIND PEER requests... */
773 GNUNET_assert (NULL == find_peer_task);
774 find_peer_task = GNUNET_SCHEDULER_add_now (&send_find_peer_message,
782 * Method called whenever a peer disconnects.
785 * @param peer peer identity this notification is about
786 * @param internal_cls our `struct PeerInfo` for @a peer
789 handle_core_disconnect (void *cls,
790 const struct GNUNET_PeerIdentity *peer,
793 struct PeerInfo *to_remove = internal_cls;
796 /* Check for disconnect from self message */
797 if (NULL == to_remove)
799 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
802 GNUNET_STATISTICS_update (GDS_stats,
803 gettext_noop ("# peers connected"),
806 GNUNET_assert (GNUNET_YES ==
807 GNUNET_CONTAINER_multipeermap_remove (all_connected_peers,
810 if ((0 == GNUNET_CONTAINER_multipeermap_size (all_connected_peers)) &&
811 (GNUNET_YES != disable_try_connect))
813 GNUNET_SCHEDULER_cancel (find_peer_task);
814 find_peer_task = NULL;
816 GNUNET_assert (to_remove->peer_bucket >= 0);
817 GNUNET_CONTAINER_DLL_remove (k_buckets[to_remove->peer_bucket].head,
818 k_buckets[to_remove->peer_bucket].tail,
820 GNUNET_assert (k_buckets[to_remove->peer_bucket].peers_size > 0);
821 k_buckets[to_remove->peer_bucket].peers_size--;
822 while ((closest_bucket > 0) &&
823 (0 == k_buckets[to_remove->peer_bucket].peers_size))
825 if (k_buckets[to_remove->peer_bucket].peers_size < bucket_size)
826 update_connect_preferences ();
827 GNUNET_free (to_remove);
832 * To how many peers should we (on average) forward the request to
833 * obtain the desired target_replication count (on average).
835 * @param hop_count number of hops the message has traversed
836 * @param target_replication the number of total paths desired
837 * @return Some number of peers to forward the message to
840 get_forward_count (uint32_t hop_count,
841 uint32_t target_replication)
843 uint32_t random_value;
844 uint32_t forward_count;
847 if (hop_count > GDS_NSE_get () * 4.0)
849 /* forcefully terminate */
850 GNUNET_STATISTICS_update (GDS_stats,
851 gettext_noop ("# requests TTL-dropped"),
855 if (hop_count > GDS_NSE_get () * 2.0)
857 /* Once we have reached our ideal number of hops, only forward to 1 peer */
860 /* bound by system-wide maximum */
862 GNUNET_MIN (MAXIMUM_REPLICATION_LEVEL, target_replication);
864 1 + (target_replication - 1.0) / (GDS_NSE_get ()
865 + ((float) (target_replication - 1.0)
867 /* Set forward count to floor of target_value */
868 forward_count = (uint32_t) target_value;
869 /* Subtract forward_count (floor) from target_value (yields value between 0 and 1) */
870 target_value = target_value - forward_count;
872 GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, UINT32_MAX);
873 if (random_value < (target_value * UINT32_MAX))
875 return forward_count;
880 * Compute the distance between have and target as a 32-bit value.
881 * Differences in the lower bits must count stronger than differences
882 * in the higher bits.
886 * @return 0 if have==target, otherwise a number
887 * that is larger as the distance between
888 * the two hash codes increases
891 get_distance (const struct GNUNET_HashCode *target,
892 const struct GNUNET_HashCode *have)
899 /* We have to represent the distance between two 2^9 (=512)-bit
900 * numbers as a 2^5 (=32)-bit number with "0" being used for the
901 * two numbers being identical; furthermore, we need to
902 * guarantee that a difference in the number of matching
903 * bits is always represented in the result.
905 * We use 2^32/2^9 numerical values to distinguish between
906 * hash codes that have the same LSB bit distance and
907 * use the highest 2^9 bits of the result to signify the
908 * number of (mis)matching LSB bits; if we have 0 matching
909 * and hence 512 mismatching LSB bits we return -1 (since
910 * 512 itself cannot be represented with 9 bits) *//* first, calculate the most significant 9 bits of our
911 * result, aka the number of LSBs */bucket = GNUNET_CRYPTO_hash_matching_bits (target,
913 /* bucket is now a value between 0 and 512 */
915 return 0; /* perfect match */
917 return (unsigned int) -1; /* LSB differs; use max (if we did the bit-shifting
918 * below, we'd end up with max+1 (overflow)) */
920 /* calculate the most significant bits of the final result */
921 msb = (512 - bucket) << (32 - 9);
922 /* calculate the 32-9 least significant bits of the final result by
923 * looking at the differences in the 32-9 bits following the
924 * mismatching bit at 'bucket' */
927 (i < sizeof(struct GNUNET_HashCode) * 8) && (i < bucket + 1 + 32 - 9);
930 if (GNUNET_CRYPTO_hash_get_bit (target, i) !=
931 GNUNET_CRYPTO_hash_get_bit (have, i))
932 lsb |= (1 << (bucket + 32 - 9 - i)); /* first bit set will be 10,
933 * last bit set will be 31 -- if
934 * i does not reach 512 first... */
941 * Check whether my identity is closer than any known peers. If a
942 * non-null bloomfilter is given, check if this is the closest peer
943 * that hasn't already been routed to.
945 * @param key hash code to check closeness to
946 * @param bloom bloomfilter, exclude these entries from the decision
947 * @return #GNUNET_YES if node location is closest,
948 * #GNUNET_NO otherwise.
951 GDS_am_closest_peer (const struct GNUNET_HashCode *key,
952 const struct GNUNET_CONTAINER_BloomFilter *bloom)
957 struct PeerInfo *pos;
959 if (0 == GNUNET_memcmp (&my_identity_hash,
962 bucket_num = find_bucket (key);
963 GNUNET_assert (bucket_num >= 0);
964 bits = GNUNET_CRYPTO_hash_matching_bits (&my_identity_hash,
966 pos = k_buckets[bucket_num].head;
969 if ((NULL != bloom) &&
971 GNUNET_CONTAINER_bloomfilter_test (bloom,
975 continue; /* Skip already checked entries */
977 other_bits = GNUNET_CRYPTO_hash_matching_bits (&pos->phash,
979 if (other_bits > bits)
981 if (other_bits == bits) /* We match the same number of bits */
985 /* No peers closer, we are the closest! */
991 * Select a peer from the routing table that would be a good routing
992 * destination for sending a message for "key". The resulting peer
993 * must not be in the set of blocked peers.<p>
995 * Note that we should not ALWAYS select the closest peer to the
996 * target, peers further away from the target should be chosen with
997 * exponentially declining probability.
999 * FIXME: double-check that this is fine
1002 * @param key the key we are selecting a peer to route to
1003 * @param bloom a bloomfilter 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
1007 static struct PeerInfo *
1008 select_peer (const struct GNUNET_HashCode *key,
1009 const struct GNUNET_CONTAINER_BloomFilter *bloom,
1014 unsigned int selected;
1015 struct PeerInfo *pos;
1017 unsigned int smallest_distance;
1018 struct PeerInfo *chosen;
1020 if (hops >= GDS_NSE_get ())
1022 /* greedy selection (closest peer that is not in bloomfilter) */
1023 smallest_distance = UINT_MAX;
1025 for (bc = 0; bc <= closest_bucket; bc++)
1027 pos = k_buckets[bc].head;
1029 while ((pos != NULL) && (count < bucket_size))
1031 if ((NULL == bloom) ||
1033 GNUNET_CONTAINER_bloomfilter_test (bloom,
1036 dist = get_distance (key,
1038 if (dist < smallest_distance)
1041 smallest_distance = dist;
1046 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1047 "Excluded peer `%s' due to BF match in greedy routing for %s\n",
1048 GNUNET_i2s (pos->id),
1050 GNUNET_STATISTICS_update (GDS_stats,
1052 "# Peers excluded from routing due to Bloomfilter"),
1055 dist = get_distance (key,
1057 if (dist < smallest_distance)
1060 smallest_distance = dist;
1068 GNUNET_STATISTICS_update (GDS_stats,
1069 gettext_noop ("# Peer selection failed"),
1073 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1074 "Selected peer `%s' in greedy routing for %s\n",
1075 GNUNET_i2s (chosen->id),
1080 /* select "random" peer */
1081 /* count number of peers that are available and not filtered */
1083 for (bc = 0; bc <= closest_bucket; bc++)
1085 pos = k_buckets[bc].head;
1086 while ((NULL != pos) && (count < bucket_size))
1088 if ((NULL != bloom) &&
1090 GNUNET_CONTAINER_bloomfilter_test (bloom,
1093 GNUNET_STATISTICS_update (GDS_stats,
1096 "# Peers excluded from routing due to Bloomfilter"),
1098 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1099 "Excluded peer `%s' due to BF match in random routing for %s\n",
1100 GNUNET_i2s (pos->id),
1103 continue; /* Ignore bloomfiltered peers */
1109 if (0 == count) /* No peers to select from! */
1111 GNUNET_STATISTICS_update (GDS_stats,
1112 gettext_noop ("# Peer selection failed"), 1,
1116 /* Now actually choose a peer */
1117 selected = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
1120 for (bc = 0; bc <= closest_bucket; bc++)
1122 for (pos = k_buckets[bc].head; ((pos != NULL) && (count < bucket_size));
1125 if ((bloom != NULL) &&
1127 GNUNET_CONTAINER_bloomfilter_test (bloom,
1130 continue; /* Ignore bloomfiltered peers */
1132 if (0 == selected--)
1134 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1135 "Selected peer `%s' in random routing for %s\n",
1136 GNUNET_i2s (pos->id),
1148 * Compute the set of peers that the given request should be
1151 * @param key routing key
1152 * @param bloom bloom filter excluding peers as targets, all selected
1153 * peers will be added to the bloom filter
1154 * @param hop_count number of hops the request has traversed so far
1155 * @param target_replication desired number of replicas
1156 * @param targets where to store an array of target peers (to be
1157 * free'd by the caller)
1158 * @return number of peers returned in 'targets'.
1161 get_target_peers (const struct GNUNET_HashCode *key,
1162 struct GNUNET_CONTAINER_BloomFilter *bloom,
1164 uint32_t target_replication,
1165 struct PeerInfo ***targets)
1169 struct PeerInfo **rtargets;
1170 struct PeerInfo *nxt;
1172 GNUNET_assert (NULL != bloom);
1173 ret = get_forward_count (hop_count,
1174 target_replication);
1180 rtargets = GNUNET_new_array (ret,
1182 for (off = 0; off < ret; off++)
1184 nxt = select_peer (key,
1189 rtargets[off] = nxt;
1190 GNUNET_break (GNUNET_NO ==
1191 GNUNET_CONTAINER_bloomfilter_test (bloom,
1193 GNUNET_CONTAINER_bloomfilter_add (bloom,
1196 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1197 "Selected %u/%u peers at hop %u for %s (target was %u)\n",
1199 GNUNET_CONTAINER_multipeermap_size (all_connected_peers),
1200 (unsigned int) hop_count,
1205 GNUNET_free (rtargets);
1209 *targets = rtargets;
1210 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1211 "Forwarding query `%s' to %u peers (goal was %u peers)\n",
1220 * Perform a PUT operation. Forwards the given request to other
1221 * peers. Does not store the data locally. Does not give the
1222 * data to local clients. May do nothing if this is the only
1223 * peer in the network (or if we are the closest peer in the
1226 * @param type type of the block
1227 * @param options routing options
1228 * @param desired_replication_level desired replication count
1229 * @param expiration_time when does the content expire
1230 * @param hop_count how many hops has this message traversed so far
1231 * @param bf Bloom filter of peers this PUT has already traversed
1232 * @param key key for the content
1233 * @param put_path_length number of entries in @a put_path
1234 * @param put_path peers this request has traversed so far (if tracked)
1235 * @param data payload to store
1236 * @param data_size number of bytes in @a data
1237 * @return #GNUNET_OK if the request was forwarded, #GNUNET_NO if not
1240 GDS_NEIGHBOURS_handle_put (enum GNUNET_BLOCK_Type type,
1241 enum GNUNET_DHT_RouteOption options,
1242 uint32_t desired_replication_level,
1243 struct GNUNET_TIME_Absolute expiration_time,
1245 struct GNUNET_CONTAINER_BloomFilter *bf,
1246 const struct GNUNET_HashCode *key,
1247 unsigned int put_path_length,
1248 struct GNUNET_PeerIdentity *put_path,
1252 unsigned int target_count;
1254 struct PeerInfo **targets;
1255 struct PeerInfo *target;
1257 struct GNUNET_MQ_Envelope *env;
1258 struct PeerPutMessage *ppm;
1259 struct GNUNET_PeerIdentity *pp;
1260 unsigned int skip_count;
1262 GNUNET_assert (NULL != bf);
1263 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1264 "Adding myself (%s) to PUT bloomfilter for %s\n",
1265 GNUNET_i2s (&my_identity),
1267 GNUNET_CONTAINER_bloomfilter_add (bf,
1269 GNUNET_STATISTICS_update (GDS_stats,
1270 gettext_noop ("# PUT requests routed"),
1274 = get_target_peers (key,
1277 desired_replication_level,
1279 if (0 == target_count)
1281 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1282 "Routing PUT for %s terminates after %u hops at %s\n",
1284 (unsigned int) hop_count,
1285 GNUNET_i2s (&my_identity));
1288 msize = put_path_length * sizeof(struct GNUNET_PeerIdentity) + data_size;
1289 if (msize + sizeof(struct PeerPutMessage)
1290 >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1292 put_path_length = 0;
1295 if (msize + sizeof(struct PeerPutMessage)
1296 >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1299 GNUNET_free (targets);
1302 GNUNET_STATISTICS_update (GDS_stats,
1304 "# PUT messages queued for transmission"),
1308 for (i = 0; i < target_count; i++)
1310 target = targets[i];
1311 if (GNUNET_MQ_get_length (target->mq) >= MAXIMUM_PENDING_PER_PEER)
1314 GNUNET_STATISTICS_update (GDS_stats,
1316 "# P2P messages dropped due to full queue"),
1322 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1323 "Routing PUT for %s after %u hops to %s\n",
1325 (unsigned int) hop_count,
1326 GNUNET_i2s (target->id));
1327 env = GNUNET_MQ_msg_extra (ppm,
1329 GNUNET_MESSAGE_TYPE_DHT_P2P_PUT);
1330 ppm->options = htonl (options);
1331 ppm->type = htonl (type);
1332 ppm->hop_count = htonl (hop_count + 1);
1333 ppm->desired_replication_level = htonl (desired_replication_level);
1334 ppm->put_path_length = htonl (put_path_length);
1335 ppm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
1336 GNUNET_break (GNUNET_YES ==
1337 GNUNET_CONTAINER_bloomfilter_test (bf,
1339 GNUNET_assert (GNUNET_OK ==
1340 GNUNET_CONTAINER_bloomfilter_get_raw_data (bf,
1344 pp = (struct GNUNET_PeerIdentity *) &ppm[1];
1347 sizeof(struct GNUNET_PeerIdentity) * put_path_length);
1348 GNUNET_memcpy (&pp[put_path_length],
1351 GNUNET_MQ_send (target->mq,
1354 GNUNET_free (targets);
1355 return (skip_count < target_count) ? GNUNET_OK : GNUNET_NO;
1360 * Perform a GET operation. Forwards the given request to other
1361 * peers. Does not lookup the key locally. May do nothing if this is
1362 * the only peer in the network (or if we are the closest peer in the
1365 * @param type type of the block
1366 * @param options routing options
1367 * @param desired_replication_level desired replication count
1368 * @param hop_count how many hops did this request traverse so far?
1369 * @param key key for the content
1370 * @param xquery extended query
1371 * @param xquery_size number of bytes in @a xquery
1372 * @param bg group to use for filtering replies
1373 * @param peer_bf filter for peers not to select (again)
1374 * @return #GNUNET_OK if the request was forwarded, #GNUNET_NO if not
1377 GDS_NEIGHBOURS_handle_get (enum GNUNET_BLOCK_Type type,
1378 enum GNUNET_DHT_RouteOption options,
1379 uint32_t desired_replication_level,
1381 const struct GNUNET_HashCode *key,
1384 struct GNUNET_BLOCK_Group *bg,
1385 struct GNUNET_CONTAINER_BloomFilter *peer_bf)
1387 unsigned int target_count;
1388 struct PeerInfo **targets;
1389 struct PeerInfo *target;
1390 struct GNUNET_MQ_Envelope *env;
1392 struct PeerGetMessage *pgm;
1394 size_t reply_bf_size;
1396 unsigned int skip_count;
1399 GNUNET_assert (NULL != peer_bf);
1400 GNUNET_STATISTICS_update (GDS_stats,
1401 gettext_noop ("# GET requests routed"),
1404 target_count = get_target_peers (key,
1407 desired_replication_level,
1409 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1410 "Adding myself (%s) to GET bloomfilter for %s\n",
1411 GNUNET_i2s (&my_identity),
1413 GNUNET_CONTAINER_bloomfilter_add (peer_bf,
1415 if (0 == target_count)
1417 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1418 "Routing GET for %s terminates after %u hops at %s\n",
1420 (unsigned int) hop_count,
1421 GNUNET_i2s (&my_identity));
1425 GNUNET_BLOCK_group_serialize (bg,
1432 bf_nonce = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
1435 msize = xquery_size + reply_bf_size;
1436 if (msize + sizeof(struct PeerGetMessage) >= GNUNET_MAX_MESSAGE_SIZE)
1439 GNUNET_free_non_null (reply_bf);
1440 GNUNET_free (targets);
1443 GNUNET_STATISTICS_update (GDS_stats,
1445 "# GET messages queued for transmission"),
1448 /* forward request */
1450 for (unsigned int i = 0; i < target_count; i++)
1452 target = targets[i];
1453 if (GNUNET_MQ_get_length (target->mq) >= MAXIMUM_PENDING_PER_PEER)
1456 GNUNET_STATISTICS_update (GDS_stats,
1458 "# P2P messages dropped due to full queue"),
1463 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1464 "Routing GET for %s after %u hops to %s\n",
1466 (unsigned int) hop_count,
1467 GNUNET_i2s (target->id));
1468 env = GNUNET_MQ_msg_extra (pgm,
1470 GNUNET_MESSAGE_TYPE_DHT_P2P_GET);
1471 pgm->options = htonl (options);
1472 pgm->type = htonl (type);
1473 pgm->hop_count = htonl (hop_count + 1);
1474 pgm->desired_replication_level = htonl (desired_replication_level);
1475 pgm->xquery_size = htonl (xquery_size);
1476 pgm->bf_mutator = bf_nonce;
1477 GNUNET_break (GNUNET_YES ==
1478 GNUNET_CONTAINER_bloomfilter_test (peer_bf,
1480 GNUNET_assert (GNUNET_OK ==
1481 GNUNET_CONTAINER_bloomfilter_get_raw_data (peer_bf,
1485 xq = (char *) &pgm[1];
1489 GNUNET_memcpy (&xq[xquery_size],
1492 GNUNET_MQ_send (target->mq,
1495 GNUNET_free (targets);
1496 GNUNET_free_non_null (reply_bf);
1497 return (skip_count < target_count) ? GNUNET_OK : GNUNET_NO;
1502 * Handle a reply (route to origin). Only forwards the reply back to
1503 * the given peer. Does not do local caching or forwarding to local
1506 * @param target neighbour that should receive the block (if still connected)
1507 * @param type type of the block
1508 * @param expiration_time when does the content expire
1509 * @param key key for the content
1510 * @param put_path_length number of entries in @a put_path
1511 * @param put_path peers the original PUT traversed (if tracked)
1512 * @param get_path_length number of entries in @a get_path
1513 * @param get_path peers this reply has traversed so far (if tracked)
1514 * @param data payload of the reply
1515 * @param data_size number of bytes in @a data
1518 GDS_NEIGHBOURS_handle_reply (const struct GNUNET_PeerIdentity *target,
1519 enum GNUNET_BLOCK_Type type,
1520 struct GNUNET_TIME_Absolute expiration_time,
1521 const struct GNUNET_HashCode *key,
1522 unsigned int put_path_length,
1523 const struct GNUNET_PeerIdentity *put_path,
1524 unsigned int get_path_length,
1525 const struct GNUNET_PeerIdentity *get_path,
1529 struct PeerInfo *pi;
1530 struct GNUNET_MQ_Envelope *env;
1532 struct PeerResultMessage *prm;
1533 struct GNUNET_PeerIdentity *paths;
1535 msize = data_size + (get_path_length + put_path_length)
1536 * sizeof(struct GNUNET_PeerIdentity);
1537 if ((msize + sizeof(struct PeerResultMessage) >= GNUNET_MAX_MESSAGE_SIZE) ||
1539 GNUNET_MAX_MESSAGE_SIZE / sizeof(struct GNUNET_PeerIdentity)) ||
1541 GNUNET_MAX_MESSAGE_SIZE / sizeof(struct GNUNET_PeerIdentity)) ||
1542 (data_size > GNUNET_MAX_MESSAGE_SIZE))
1547 pi = GNUNET_CONTAINER_multipeermap_get (all_connected_peers,
1551 /* peer disconnected in the meantime, drop reply */
1552 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1553 "No matching peer for reply for key %s\n",
1557 if (GNUNET_MQ_get_length (pi->mq) >= MAXIMUM_PENDING_PER_PEER)
1560 GNUNET_STATISTICS_update (GDS_stats,
1562 "# P2P messages dropped due to full queue"),
1565 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1566 "Peer queue full, ignoring reply for key %s\n",
1571 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1572 "Forwarding reply for key %s to peer %s\n",
1574 GNUNET_i2s (target));
1575 GNUNET_STATISTICS_update (GDS_stats,
1577 ("# RESULT messages queued for transmission"), 1,
1579 env = GNUNET_MQ_msg_extra (prm,
1581 GNUNET_MESSAGE_TYPE_DHT_P2P_RESULT);
1582 prm->type = htonl (type);
1583 prm->put_path_length = htonl (put_path_length);
1584 prm->get_path_length = htonl (get_path_length);
1585 prm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
1587 paths = (struct GNUNET_PeerIdentity *) &prm[1];
1588 GNUNET_memcpy (paths,
1590 put_path_length * sizeof(struct GNUNET_PeerIdentity));
1591 GNUNET_memcpy (&paths[put_path_length],
1593 get_path_length * sizeof(struct GNUNET_PeerIdentity));
1594 GNUNET_memcpy (&paths[put_path_length + get_path_length],
1597 GNUNET_MQ_send (pi->mq,
1603 * To be called on core init/fail.
1605 * @param cls service closure
1606 * @param identity the public identity of this peer
1609 core_init (void *cls,
1610 const struct GNUNET_PeerIdentity *identity)
1613 GNUNET_log (GNUNET_ERROR_TYPE_INFO,
1614 "CORE called, I am %s\n",
1615 GNUNET_i2s (identity));
1616 my_identity = *identity;
1617 GNUNET_CRYPTO_hash (identity,
1618 sizeof(struct GNUNET_PeerIdentity),
1620 GNUNET_SERVICE_resume (GDS_service);
1625 * Check validity of a p2p put request.
1627 * @param cls closure with the `struct PeerInfo` of the sender
1628 * @param message message
1629 * @return #GNUNET_OK if the message is valid
1632 check_dht_p2p_put (void *cls,
1633 const struct PeerPutMessage *put)
1639 msize = ntohs (put->header.size);
1640 putlen = ntohl (put->put_path_length);
1642 sizeof(struct PeerPutMessage)
1643 + putlen * sizeof(struct GNUNET_PeerIdentity)) ||
1645 GNUNET_MAX_MESSAGE_SIZE / sizeof(struct GNUNET_PeerIdentity)))
1647 GNUNET_break_op (0);
1648 return GNUNET_SYSERR;
1655 * Core handler for p2p put requests.
1657 * @param cls closure with the `struct PeerInfo` of the sender
1658 * @param message message
1661 handle_dht_p2p_put (void *cls,
1662 const struct PeerPutMessage *put)
1664 struct PeerInfo *peer = cls;
1665 const struct GNUNET_PeerIdentity *put_path;
1666 const void *payload;
1669 size_t payload_size;
1670 enum GNUNET_DHT_RouteOption options;
1671 struct GNUNET_CONTAINER_BloomFilter *bf;
1672 struct GNUNET_HashCode test_key;
1674 struct GNUNET_TIME_Absolute exp_time;
1676 exp_time = GNUNET_TIME_absolute_ntoh (put->expiration_time);
1677 if (0 == GNUNET_TIME_absolute_get_remaining (exp_time).rel_value_us)
1679 GNUNET_STATISTICS_update (GDS_stats,
1680 gettext_noop ("# Expired PUTs discarded"),
1685 msize = ntohs (put->header.size);
1686 putlen = ntohl (put->put_path_length);
1687 GNUNET_STATISTICS_update (GDS_stats,
1688 gettext_noop ("# P2P PUT requests received"),
1691 GNUNET_STATISTICS_update (GDS_stats,
1692 gettext_noop ("# P2P PUT bytes received"),
1695 put_path = (const struct GNUNET_PeerIdentity *) &put[1];
1696 payload = &put_path[putlen];
1697 options = ntohl (put->options);
1698 payload_size = msize - (sizeof(struct PeerPutMessage)
1699 + putlen * sizeof(struct GNUNET_PeerIdentity));
1701 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1702 "PUT for `%s' from %s\n",
1703 GNUNET_h2s (&put->key),
1704 GNUNET_i2s (peer->id));
1705 if (GNUNET_YES == log_route_details_stderr)
1710 pp = GNUNET_STRINGS_pp2s (put_path,
1712 tmp = GNUNET_strdup (GNUNET_i2s (&my_identity));
1713 LOG_TRAFFIC (GNUNET_ERROR_TYPE_DEBUG,
1714 "R5N PUT %s: %s->%s (%u, %u=>%u, PP: %s)\n",
1715 GNUNET_h2s (&put->key),
1716 GNUNET_i2s (peer->id),
1718 ntohl (put->hop_count),
1719 GNUNET_CRYPTO_hash_matching_bits (&peer->phash,
1721 GNUNET_CRYPTO_hash_matching_bits (&my_identity_hash,
1727 switch (GNUNET_BLOCK_get_key
1735 if (0 != memcmp (&test_key,
1737 sizeof(struct GNUNET_HashCode)))
1739 char *put_s = GNUNET_strdup (GNUNET_h2s_full (&put->key));
1741 GNUNET_break_op (0);
1742 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
1743 "PUT with key `%s' for block with key %s\n",
1745 GNUNET_h2s_full (&test_key));
1746 GNUNET_free (put_s);
1752 GNUNET_break_op (0);
1756 /* cannot verify, good luck */
1759 if (ntohl (put->type) == GNUNET_BLOCK_TYPE_REGEX) /* FIXME: do for all tpyes */
1761 switch (GNUNET_BLOCK_evaluate (GDS_block_context,
1763 NULL, /* query group */
1764 GNUNET_BLOCK_EO_NONE,
1766 NULL, 0, /* xquery */
1770 case GNUNET_BLOCK_EVALUATION_OK_MORE:
1771 case GNUNET_BLOCK_EVALUATION_OK_LAST:
1774 case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
1775 case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
1776 case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT:
1777 case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
1778 case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
1779 case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
1781 GNUNET_break_op (0);
1786 bf = GNUNET_CONTAINER_bloomfilter_init (put->bloomfilter,
1788 GNUNET_CONSTANTS_BLOOMFILTER_K);
1789 GNUNET_break_op (GNUNET_YES ==
1790 GNUNET_CONTAINER_bloomfilter_test (bf,
1793 struct GNUNET_PeerIdentity pp[putlen + 1];
1795 /* extend 'put path' by sender */
1796 if (0 != (options & GNUNET_DHT_RO_RECORD_ROUTE))
1799 for (unsigned int i = 0; i <= putlen; i++)
1801 for (unsigned int j = 0; j < i; j++)
1803 GNUNET_break (0 != memcmp (&pp[i],
1805 sizeof(struct GNUNET_PeerIdentity)));
1807 GNUNET_break (0 != memcmp (&pp[i],
1809 sizeof(struct GNUNET_PeerIdentity)));
1814 putlen * sizeof(struct GNUNET_PeerIdentity));
1815 pp[putlen] = *peer->id;
1821 /* give to local clients */
1822 GDS_CLIENTS_handle_reply (exp_time,
1832 if ((0 != (options & GNUNET_DHT_RO_DEMULTIPLEX_EVERYWHERE)) ||
1833 (GDS_am_closest_peer (&put->key, bf)))
1834 GDS_DATACACHE_handle_put (exp_time,
1841 /* route to other peers */
1842 forwarded = GDS_NEIGHBOURS_handle_put (ntohl (put->type),
1845 put->desired_replication_level),
1847 ntohl (put->hop_count),
1854 /* notify monitoring clients */
1855 GDS_CLIENTS_process_put (options
1856 | ((GNUNET_OK == forwarded)
1857 ? GNUNET_DHT_RO_LAST_HOP
1860 ntohl (put->hop_count),
1861 ntohl (put->desired_replication_level),
1868 GNUNET_CONTAINER_bloomfilter_free (bf);
1873 * We have received a FIND PEER request. Send matching
1876 * @param sender sender of the FIND PEER request
1877 * @param key peers close to this key are desired
1878 * @param bg group for filtering peers
1881 handle_find_peer (const struct GNUNET_PeerIdentity *sender,
1882 const struct GNUNET_HashCode *key,
1883 struct GNUNET_BLOCK_Group *bg)
1886 struct PeerBucket *bucket;
1887 struct PeerInfo *peer;
1888 unsigned int choice;
1889 const struct GNUNET_HELLO_Message *hello;
1892 /* first, check about our own HELLO */
1893 if (NULL != GDS_my_hello)
1895 hello_size = GNUNET_HELLO_size ((const struct
1896 GNUNET_HELLO_Message *) GDS_my_hello);
1897 GNUNET_break (hello_size >= sizeof(struct GNUNET_MessageHeader));
1898 if (GNUNET_BLOCK_EVALUATION_OK_MORE ==
1899 GNUNET_BLOCK_evaluate (GDS_block_context,
1900 GNUNET_BLOCK_TYPE_DHT_HELLO,
1902 GNUNET_BLOCK_EO_LOCAL_SKIP_CRYPTO,
1908 GDS_NEIGHBOURS_handle_reply (sender,
1909 GNUNET_BLOCK_TYPE_DHT_HELLO,
1910 GNUNET_TIME_relative_to_absolute (
1922 GNUNET_STATISTICS_update (GDS_stats,
1924 "# FIND PEER requests ignored due to Bloomfilter"),
1931 GNUNET_STATISTICS_update (GDS_stats,
1933 "# FIND PEER requests ignored due to lack of HELLO"),
1938 /* then, also consider sending a random HELLO from the closest bucket */
1939 if (0 == memcmp (&my_identity_hash,
1941 sizeof(struct GNUNET_HashCode)))
1942 bucket_idx = closest_bucket;
1944 bucket_idx = GNUNET_MIN ((int) closest_bucket,
1948 bucket = &k_buckets[bucket_idx];
1949 if (bucket->peers_size == 0)
1951 choice = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
1952 bucket->peers_size);
1953 peer = bucket->head;
1956 GNUNET_assert (NULL != peer);
1960 choice = bucket->peers_size;
1965 return; /* no non-masked peer available */
1967 peer = bucket->head;
1968 hello = GDS_HELLO_get (peer->id);
1970 while ((NULL == hello) ||
1971 (GNUNET_BLOCK_EVALUATION_OK_MORE !=
1972 GNUNET_BLOCK_evaluate (GDS_block_context,
1973 GNUNET_BLOCK_TYPE_DHT_HELLO,
1975 GNUNET_BLOCK_EO_LOCAL_SKIP_CRYPTO,
1979 (hello_size = GNUNET_HELLO_size (hello)))));
1980 GDS_NEIGHBOURS_handle_reply (sender,
1981 GNUNET_BLOCK_TYPE_DHT_HELLO,
1982 GNUNET_TIME_relative_to_absolute
1983 (GNUNET_CONSTANTS_HELLO_ADDRESS_EXPIRATION),
1995 * Handle a result from local datacache for a GET operation.
1997 * @param cls the `struct PeerInfo` for which this is a reply
1998 * @param type type of the block
1999 * @param expiration_time when does the content expire
2000 * @param key key for the content
2001 * @param put_path_length number of entries in @a put_path
2002 * @param put_path peers the original PUT traversed (if tracked)
2003 * @param get_path_length number of entries in @a get_path
2004 * @param get_path peers this reply has traversed so far (if tracked)
2005 * @param data payload of the reply
2006 * @param data_size number of bytes in @a data
2009 handle_local_result (void *cls,
2010 enum GNUNET_BLOCK_Type type,
2011 struct GNUNET_TIME_Absolute expiration_time,
2012 const struct GNUNET_HashCode *key,
2013 unsigned int put_path_length,
2014 const struct GNUNET_PeerIdentity *put_path,
2015 unsigned int get_path_length,
2016 const struct GNUNET_PeerIdentity *get_path,
2020 struct PeerInfo *peer = cls;
2023 pp = GNUNET_STRINGS_pp2s (put_path,
2025 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2026 "Found local result for %s (PP: %s)\n",
2030 GDS_NEIGHBOURS_handle_reply (peer->id,
2034 put_path_length, put_path,
2035 get_path_length, get_path,
2041 * Check validity of p2p get request.
2043 * @param cls closure with the `struct PeerInfo` of the sender
2044 * @param get the message
2045 * @return #GNUNET_OK if the message is well-formed
2048 check_dht_p2p_get (void *cls,
2049 const struct PeerGetMessage *get)
2051 uint32_t xquery_size;
2055 msize = ntohs (get->header.size);
2056 xquery_size = ntohl (get->xquery_size);
2057 if (msize < sizeof(struct PeerGetMessage) + xquery_size)
2059 GNUNET_break_op (0);
2060 return GNUNET_SYSERR;
2067 * Core handler for p2p get requests.
2069 * @param cls closure with the `struct PeerInfo` of the sender
2070 * @param get the message
2073 handle_dht_p2p_get (void *cls,
2074 const struct PeerGetMessage *get)
2076 struct PeerInfo *peer = cls;
2077 uint32_t xquery_size;
2078 size_t reply_bf_size;
2080 enum GNUNET_BLOCK_Type type;
2081 enum GNUNET_DHT_RouteOption options;
2082 enum GNUNET_BLOCK_EvaluationResult eval;
2083 struct GNUNET_BLOCK_Group *bg;
2084 struct GNUNET_CONTAINER_BloomFilter *peer_bf;
2088 /* parse and validate message */
2089 msize = ntohs (get->header.size);
2090 xquery_size = ntohl (get->xquery_size);
2091 reply_bf_size = msize - (sizeof(struct PeerGetMessage) + xquery_size);
2092 type = ntohl (get->type);
2093 options = ntohl (get->options);
2094 xquery = (const char *) &get[1];
2095 GNUNET_STATISTICS_update (GDS_stats,
2096 gettext_noop ("# P2P GET requests received"),
2099 GNUNET_STATISTICS_update (GDS_stats,
2100 gettext_noop ("# P2P GET bytes received"),
2103 if (GNUNET_YES == log_route_details_stderr)
2107 tmp = GNUNET_strdup (GNUNET_i2s (&my_identity));
2108 LOG_TRAFFIC (GNUNET_ERROR_TYPE_DEBUG,
2109 "R5N GET %s: %s->%s (%u, %u=>%u) xq: %.*s\n",
2110 GNUNET_h2s (&get->key),
2111 GNUNET_i2s (peer->id),
2113 ntohl (get->hop_count),
2114 GNUNET_CRYPTO_hash_matching_bits (&peer->phash,
2116 GNUNET_CRYPTO_hash_matching_bits (&my_identity_hash,
2118 ntohl (get->xquery_size),
2123 = GNUNET_BLOCK_evaluate (GDS_block_context,
2126 GNUNET_BLOCK_EO_NONE,
2132 if (eval != GNUNET_BLOCK_EVALUATION_REQUEST_VALID)
2134 /* request invalid or block type not supported */
2135 GNUNET_break_op (eval == GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED);
2138 peer_bf = GNUNET_CONTAINER_bloomfilter_init (get->bloomfilter,
2140 GNUNET_CONSTANTS_BLOOMFILTER_K);
2141 GNUNET_break_op (GNUNET_YES ==
2142 GNUNET_CONTAINER_bloomfilter_test (peer_bf,
2144 bg = GNUNET_BLOCK_group_create (GDS_block_context,
2147 &xquery[xquery_size],
2152 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2153 "GET for %s at %s after %u hops\n",
2154 GNUNET_h2s (&get->key),
2155 GNUNET_i2s (&my_identity),
2156 (unsigned int) ntohl (get->hop_count));
2157 /* local lookup (this may update the reply_bf) */
2158 if ((0 != (options & GNUNET_DHT_RO_DEMULTIPLEX_EVERYWHERE)) ||
2159 (GDS_am_closest_peer (&get->key,
2162 if ((0 != (options & GNUNET_DHT_RO_FIND_PEER)))
2164 GNUNET_STATISTICS_update (GDS_stats,
2166 "# P2P FIND PEER requests processed"),
2169 handle_find_peer (peer->id,
2175 eval = GDS_DATACACHE_handle_get (&get->key,
2180 &handle_local_result,
2186 GNUNET_STATISTICS_update (GDS_stats,
2187 gettext_noop ("# P2P GET requests ONLY routed"),
2192 /* remember request for routing replies */
2193 GDS_ROUTING_add (peer->id,
2195 bg, /* bg now owned by routing, but valid at least until end of this function! */
2201 /* P2P forwarding */
2202 forwarded = GNUNET_NO;
2203 if (eval != GNUNET_BLOCK_EVALUATION_OK_LAST)
2204 forwarded = GDS_NEIGHBOURS_handle_get (type,
2207 get->desired_replication_level),
2208 ntohl (get->hop_count),
2214 GDS_CLIENTS_process_get (options
2215 | (GNUNET_OK == forwarded)
2216 ? GNUNET_DHT_RO_LAST_HOP : 0,
2218 ntohl (get->hop_count),
2219 ntohl (get->desired_replication_level),
2224 /* clean up; note that 'bg' is owned by routing now! */
2225 GNUNET_CONTAINER_bloomfilter_free (peer_bf);
2230 * Check validity of p2p result message.
2232 * @param cls closure
2233 * @param message message
2234 * @return #GNUNET_YES if the message is well-formed
2237 check_dht_p2p_result (void *cls,
2238 const struct PeerResultMessage *prm)
2240 uint32_t get_path_length;
2241 uint32_t put_path_length;
2245 msize = ntohs (prm->header.size);
2246 put_path_length = ntohl (prm->put_path_length);
2247 get_path_length = ntohl (prm->get_path_length);
2249 sizeof(struct PeerResultMessage) + (get_path_length
2251 * sizeof(struct GNUNET_PeerIdentity)) ||
2253 GNUNET_MAX_MESSAGE_SIZE / sizeof(struct GNUNET_PeerIdentity)) ||
2255 GNUNET_MAX_MESSAGE_SIZE / sizeof(struct GNUNET_PeerIdentity)))
2257 GNUNET_break_op (0);
2258 return GNUNET_SYSERR;
2265 * Process a reply, after the @a get_path has been updated.
2267 * @param expiration_time when does the reply expire
2268 * @param key key matching the query
2269 * @param get_path_length number of entries in @a get_path
2270 * @param get_path path the reply has taken
2271 * @param put_path_length number of entries in @a put_path
2272 * @param put_path path the PUT has taken
2273 * @param type type of the block
2274 * @param data_size number of bytes in @a data
2275 * @param data payload of the reply
2278 process_reply_with_path (struct GNUNET_TIME_Absolute expiration_time,
2279 const struct GNUNET_HashCode *key,
2280 unsigned int get_path_length,
2281 const struct GNUNET_PeerIdentity *get_path,
2282 unsigned int put_path_length,
2283 const struct GNUNET_PeerIdentity *put_path,
2284 enum GNUNET_BLOCK_Type type,
2288 /* forward to local clients */
2289 GDS_CLIENTS_handle_reply (expiration_time,
2298 GDS_CLIENTS_process_get_resp (type,
2307 if (GNUNET_YES == cache_results)
2309 struct GNUNET_PeerIdentity xput_path[get_path_length + 1 + put_path_length];
2311 GNUNET_memcpy (xput_path,
2313 put_path_length * sizeof(struct GNUNET_PeerIdentity));
2314 GNUNET_memcpy (&xput_path[put_path_length],
2316 get_path_length * sizeof(struct GNUNET_PeerIdentity));
2318 GDS_DATACACHE_handle_put (expiration_time,
2320 get_path_length + put_path_length,
2326 /* forward to other peers */
2327 GDS_ROUTING_process (type,
2340 * Core handler for p2p result messages.
2342 * @param cls closure
2343 * @param message message
2346 handle_dht_p2p_result (void *cls,
2347 const struct PeerResultMessage *prm)
2349 struct PeerInfo *peer = cls;
2350 const struct GNUNET_PeerIdentity *put_path;
2351 const struct GNUNET_PeerIdentity *get_path;
2353 uint32_t get_path_length;
2354 uint32_t put_path_length;
2357 enum GNUNET_BLOCK_Type type;
2358 struct GNUNET_TIME_Absolute exp_time;
2360 /* parse and validate message */
2361 exp_time = GNUNET_TIME_absolute_ntoh (prm->expiration_time);
2362 if (0 == GNUNET_TIME_absolute_get_remaining (exp_time).rel_value_us)
2364 GNUNET_STATISTICS_update (GDS_stats,
2365 gettext_noop ("# Expired results discarded"),
2370 msize = ntohs (prm->header.size);
2371 put_path_length = ntohl (prm->put_path_length);
2372 get_path_length = ntohl (prm->get_path_length);
2373 put_path = (const struct GNUNET_PeerIdentity *) &prm[1];
2374 get_path = &put_path[put_path_length];
2375 type = ntohl (prm->type);
2376 data = (const void *) &get_path[get_path_length];
2377 data_size = msize - (sizeof(struct PeerResultMessage)
2379 + put_path_length) * sizeof(struct
2380 GNUNET_PeerIdentity));
2381 GNUNET_STATISTICS_update (GDS_stats,
2382 gettext_noop ("# P2P RESULTS received"),
2385 GNUNET_STATISTICS_update (GDS_stats,
2386 gettext_noop ("# P2P RESULT bytes received"),
2389 if (GNUNET_YES == log_route_details_stderr)
2395 gp = GNUNET_STRINGS_pp2s (get_path,
2397 pp = GNUNET_STRINGS_pp2s (put_path,
2399 tmp = GNUNET_strdup (GNUNET_i2s (&my_identity));
2400 LOG_TRAFFIC (GNUNET_ERROR_TYPE_DEBUG,
2401 "R5N RESULT %s: %s->%s (GP: %s, PP: %s)\n",
2402 GNUNET_h2s (&prm->key),
2403 GNUNET_i2s (peer->id),
2411 /* if we got a HELLO, consider it for our own routing table */
2412 if (GNUNET_BLOCK_TYPE_DHT_HELLO == type)
2414 const struct GNUNET_MessageHeader *h;
2415 struct GNUNET_PeerIdentity pid;
2417 /* Should be a HELLO, validate and consider using it! */
2418 if (data_size < sizeof(struct GNUNET_HELLO_Message))
2420 GNUNET_break_op (0);
2424 if (data_size != ntohs (h->size))
2426 GNUNET_break_op (0);
2430 GNUNET_HELLO_get_id ((const struct GNUNET_HELLO_Message *) h,
2433 GNUNET_break_op (0);
2436 if ((GNUNET_YES != disable_try_connect) &&
2437 (0 != memcmp (&my_identity,
2439 sizeof(struct GNUNET_PeerIdentity))))
2444 /* First, check if 'peer' is already on the path, and if
2445 so, truncate it instead of expanding. */
2446 for (unsigned int i = 0; i <= get_path_length; i++)
2447 if (0 == memcmp (&get_path[i],
2449 sizeof(struct GNUNET_PeerIdentity)))
2451 process_reply_with_path (exp_time,
2463 /* Need to append 'peer' to 'get_path' (normal case) */
2465 struct GNUNET_PeerIdentity xget_path[get_path_length + 1];
2467 GNUNET_memcpy (xget_path,
2469 get_path_length * sizeof(struct GNUNET_PeerIdentity));
2470 xget_path[get_path_length] = *peer->id;
2472 process_reply_with_path (exp_time,
2474 get_path_length + 1,
2486 * Initialize neighbours subsystem.
2488 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
2491 GDS_NEIGHBOURS_init ()
2493 struct GNUNET_MQ_MessageHandler core_handlers[] = {
2494 GNUNET_MQ_hd_var_size (dht_p2p_get,
2495 GNUNET_MESSAGE_TYPE_DHT_P2P_GET,
2496 struct PeerGetMessage,
2498 GNUNET_MQ_hd_var_size (dht_p2p_put,
2499 GNUNET_MESSAGE_TYPE_DHT_P2P_PUT,
2500 struct PeerPutMessage,
2502 GNUNET_MQ_hd_var_size (dht_p2p_result,
2503 GNUNET_MESSAGE_TYPE_DHT_P2P_RESULT,
2504 struct PeerResultMessage,
2506 GNUNET_MQ_handler_end ()
2508 unsigned long long temp_config_num;
2511 = GNUNET_CONFIGURATION_get_value_yesno (GDS_cfg,
2513 "DISABLE_TRY_CONNECT");
2515 GNUNET_CONFIGURATION_get_value_number (GDS_cfg,
2519 bucket_size = (unsigned int) temp_config_num;
2521 = GNUNET_CONFIGURATION_get_value_yesno (GDS_cfg,
2525 log_route_details_stderr =
2526 (NULL != getenv ("GNUNET_DHT_ROUTE_DEBUG")) ? GNUNET_YES : GNUNET_NO;
2527 ats_ch = GNUNET_ATS_connectivity_init (GDS_cfg);
2528 core_api = GNUNET_CORE_connect (GDS_cfg,
2531 &handle_core_connect,
2532 &handle_core_disconnect,
2534 if (NULL == core_api)
2535 return GNUNET_SYSERR;
2536 all_connected_peers = GNUNET_CONTAINER_multipeermap_create (256,
2538 all_desired_peers = GNUNET_CONTAINER_multipeermap_create (256,
2545 * Shutdown neighbours subsystem.
2548 GDS_NEIGHBOURS_done ()
2550 if (NULL == core_api)
2552 GNUNET_CORE_disconnect (core_api);
2555 GNUNET_CONTAINER_multipeermap_size (all_connected_peers));
2556 GNUNET_CONTAINER_multipeermap_destroy (all_connected_peers);
2557 all_connected_peers = NULL;
2558 GNUNET_CONTAINER_multipeermap_iterate (all_desired_peers,
2561 GNUNET_CONTAINER_multipeermap_destroy (all_desired_peers);
2562 all_desired_peers = NULL;
2563 GNUNET_ATS_connectivity_done (ats_ch);
2565 GNUNET_assert (NULL == find_peer_task);
2570 * Get the ID of the local node.
2572 * @return identity of the local node
2574 struct GNUNET_PeerIdentity *
2575 GDS_NEIGHBOURS_get_id ()
2577 return &my_identity;
2581 /* end of gnunet-service-dht_neighbours.c */