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/>.
20 * @file dht/gnunet-service-dht_neighbours.c
21 * @brief GNUnet DHT service's bucket and neighbour management code
22 * @author Christian Grothoff
23 * @author Nathan Evans
26 #include "gnunet_util_lib.h"
27 #include "gnunet_block_lib.h"
28 #include "gnunet_hello_lib.h"
29 #include "gnunet_constants.h"
30 #include "gnunet_protocols.h"
31 #include "gnunet_nse_service.h"
32 #include "gnunet_ats_service.h"
33 #include "gnunet_core_service.h"
34 #include "gnunet_datacache_lib.h"
35 #include "gnunet_transport_service.h"
36 #include "gnunet_hello_lib.h"
37 #include "gnunet_dht_service.h"
38 #include "gnunet_statistics_service.h"
39 #include "gnunet-service-dht.h"
40 #include "gnunet-service-dht_datacache.h"
41 #include "gnunet-service-dht_hello.h"
42 #include "gnunet-service-dht_neighbours.h"
43 #include "gnunet-service-dht_nse.h"
44 #include "gnunet-service-dht_routing.h"
47 #define LOG_TRAFFIC(kind,...) GNUNET_log_from (kind, "dht-traffic",__VA_ARGS__)
50 * Enable slow sanity checks to debug issues.
52 #define SANITY_CHECKS 1
55 * How many buckets will we allow total.
57 #define MAX_BUCKETS sizeof (struct GNUNET_HashCode) * 8
60 * What is the maximum number of peers in a given bucket.
62 #define DEFAULT_BUCKET_SIZE 8
65 * Desired replication level for FIND PEER requests
67 #define FIND_PEER_REPLICATION_LEVEL 4
70 * Maximum allowed replication level for all requests.
72 #define MAXIMUM_REPLICATION_LEVEL 16
75 * Maximum allowed number of pending messages per peer.
77 #define MAXIMUM_PENDING_PER_PEER 64
80 * How long at least to wait before sending another find peer request.
82 #define DHT_MINIMUM_FIND_PEER_INTERVAL GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_SECONDS, 30)
85 * How long at most to wait before sending another find peer request.
87 #define DHT_MAXIMUM_FIND_PEER_INTERVAL GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 10)
90 * How long at most to wait for transmission of a GET request to another peer?
92 #define GET_TIMEOUT GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 2)
95 * Hello address expiration
97 extern struct GNUNET_TIME_Relative hello_expiration;
100 GNUNET_NETWORK_STRUCT_BEGIN
105 struct PeerPutMessage
108 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_PUT
110 struct GNUNET_MessageHeader header;
115 uint32_t options GNUNET_PACKED;
120 uint32_t type GNUNET_PACKED;
125 uint32_t hop_count GNUNET_PACKED;
128 * Replication level for this message
130 uint32_t desired_replication_level GNUNET_PACKED;
133 * Length of the PUT path that follows (if tracked).
135 uint32_t put_path_length GNUNET_PACKED;
138 * When does the content expire?
140 struct GNUNET_TIME_AbsoluteNBO expiration_time;
143 * Bloomfilter (for peer identities) to stop circular routes
145 char bloomfilter[DHT_BLOOM_SIZE];
148 * The key we are storing under.
150 struct GNUNET_HashCode key;
152 /* put path (if tracked) */
162 struct PeerResultMessage
165 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_RESULT
167 struct GNUNET_MessageHeader header;
172 uint32_t type GNUNET_PACKED;
175 * Length of the PUT path that follows (if tracked).
177 uint32_t put_path_length GNUNET_PACKED;
180 * Length of the GET path that follows (if tracked).
182 uint32_t get_path_length GNUNET_PACKED;
185 * When does the content expire?
187 struct GNUNET_TIME_AbsoluteNBO expiration_time;
190 * The key of the corresponding GET request.
192 struct GNUNET_HashCode key;
194 /* put path (if tracked) */
196 /* get path (if tracked) */
206 struct PeerGetMessage
209 * Type: #GNUNET_MESSAGE_TYPE_DHT_P2P_GET
211 struct GNUNET_MessageHeader header;
216 uint32_t options GNUNET_PACKED;
219 * Desired content type.
221 uint32_t type GNUNET_PACKED;
226 uint32_t hop_count GNUNET_PACKED;
229 * Desired replication level for this request.
231 uint32_t desired_replication_level GNUNET_PACKED;
234 * Size of the extended query.
236 uint32_t xquery_size;
239 * Bloomfilter mutator.
244 * Bloomfilter (for peer identities) to stop circular routes
246 char bloomfilter[DHT_BLOOM_SIZE];
249 * The key we are looking for.
251 struct GNUNET_HashCode key;
255 /* result bloomfilter */
258 GNUNET_NETWORK_STRUCT_END
262 * Entry for a peer in a bucket.
267 * Next peer entry (DLL)
269 struct PeerInfo *next;
272 * Prev peer entry (DLL)
274 struct PeerInfo *prev;
277 * Handle for sending messages to this peer.
279 struct GNUNET_MQ_Handle *mq;
282 * What is the identity of the peer?
284 const struct GNUNET_PeerIdentity *id;
289 struct GNUNET_HashCode phash;
292 * Which bucket is this peer in?
300 * Peers are grouped into buckets.
307 struct PeerInfo *head;
312 struct PeerInfo *tail;
315 * Number of peers in the bucket.
317 unsigned int peers_size;
322 * 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 (GNUNET_CRYPTO_QUALITY_WEAK,
673 GNUNET_CONTAINER_multipeermap_iterate (all_connected_peers,
676 GNUNET_STATISTICS_update (GDS_stats,
677 gettext_noop ("# FIND PEER messages initiated"),
681 = GNUNET_CONTAINER_bloomfilter_init (NULL,
683 GNUNET_CONSTANTS_BLOOMFILTER_K);
684 // FIXME: pass priority!?
685 GDS_NEIGHBOURS_handle_get (GNUNET_BLOCK_TYPE_DHT_HELLO,
686 GNUNET_DHT_RO_FIND_PEER | GNUNET_DHT_RO_RECORD_ROUTE,
687 FIND_PEER_REPLICATION_LEVEL,
694 GNUNET_CONTAINER_bloomfilter_free (peer_bf);
695 GNUNET_BLOCK_group_destroy (bg);
696 /* schedule next round */
697 next_send_time.rel_value_us =
698 DHT_MINIMUM_FIND_PEER_INTERVAL.rel_value_us +
699 GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
700 DHT_MAXIMUM_FIND_PEER_INTERVAL.rel_value_us /
701 (newly_found_peers + 1));
702 newly_found_peers = 0;
703 GNUNET_assert (NULL == find_peer_task);
705 GNUNET_SCHEDULER_add_delayed (next_send_time,
706 &send_find_peer_message,
712 * Method called whenever a peer connects.
715 * @param peer peer identity this notification is about
716 * @param mq message queue for sending messages to @a peer
717 * @return our `struct PeerInfo` for @a peer
720 handle_core_connect (void *cls,
721 const struct GNUNET_PeerIdentity *peer,
722 struct GNUNET_MQ_Handle *mq)
727 /* Check for connect to self message */
728 if (0 == memcmp (&my_identity,
730 sizeof (struct GNUNET_PeerIdentity)))
732 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
735 GNUNET_assert (GNUNET_NO ==
736 GNUNET_CONTAINER_multipeermap_get (all_connected_peers,
738 GNUNET_STATISTICS_update (GDS_stats,
739 gettext_noop ("# peers connected"),
742 pi = GNUNET_new (struct PeerInfo);
745 GNUNET_CRYPTO_hash (peer,
746 sizeof (struct GNUNET_PeerIdentity),
748 pi->peer_bucket = find_bucket (&pi->phash);
749 GNUNET_assert ( (pi->peer_bucket >= 0) &&
750 ((unsigned int) pi->peer_bucket < MAX_BUCKETS) );
751 GNUNET_CONTAINER_DLL_insert_tail (k_buckets[pi->peer_bucket].head,
752 k_buckets[pi->peer_bucket].tail,
754 k_buckets[pi->peer_bucket].peers_size++;
755 closest_bucket = GNUNET_MAX (closest_bucket,
756 (unsigned int) pi->peer_bucket);
757 GNUNET_assert (GNUNET_OK ==
758 GNUNET_CONTAINER_multipeermap_put (all_connected_peers,
761 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
762 if ( (pi->peer_bucket > 0) &&
763 (k_buckets[pi->peer_bucket].peers_size <= bucket_size))
765 update_connect_preferences ();
768 if ( (1 == GNUNET_CONTAINER_multipeermap_size (all_connected_peers)) &&
769 (GNUNET_YES != disable_try_connect))
771 /* got a first connection, good time to start with FIND PEER requests... */
772 GNUNET_assert (NULL == find_peer_task);
773 find_peer_task = GNUNET_SCHEDULER_add_now (&send_find_peer_message,
781 * Method called whenever a peer disconnects.
784 * @param peer peer identity this notification is about
785 * @param internal_cls our `struct PeerInfo` for @a peer
788 handle_core_disconnect (void *cls,
789 const struct GNUNET_PeerIdentity *peer,
792 struct PeerInfo *to_remove = internal_cls;
795 /* Check for disconnect from self message */
796 if (NULL == to_remove)
798 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
801 GNUNET_STATISTICS_update (GDS_stats,
802 gettext_noop ("# peers connected"),
805 GNUNET_assert (GNUNET_YES ==
806 GNUNET_CONTAINER_multipeermap_remove (all_connected_peers,
809 if ( (0 == GNUNET_CONTAINER_multipeermap_size (all_connected_peers)) &&
810 (GNUNET_YES != disable_try_connect) )
812 GNUNET_SCHEDULER_cancel (find_peer_task);
813 find_peer_task = NULL;
815 GNUNET_assert (to_remove->peer_bucket >= 0);
816 GNUNET_CONTAINER_DLL_remove (k_buckets[to_remove->peer_bucket].head,
817 k_buckets[to_remove->peer_bucket].tail,
819 GNUNET_assert (k_buckets[to_remove->peer_bucket].peers_size > 0);
820 k_buckets[to_remove->peer_bucket].peers_size--;
821 while ( (closest_bucket > 0) &&
822 (0 == k_buckets[to_remove->peer_bucket].peers_size) )
824 if (k_buckets[to_remove->peer_bucket].peers_size < bucket_size)
825 update_connect_preferences ();
826 GNUNET_free (to_remove);
831 * To how many peers should we (on average) forward the request to
832 * obtain the desired target_replication count (on average).
834 * @param hop_count number of hops the message has traversed
835 * @param target_replication the number of total paths desired
836 * @return Some number of peers to forward the message to
839 get_forward_count (uint32_t hop_count,
840 uint32_t target_replication)
842 uint32_t random_value;
843 uint32_t forward_count;
846 if (hop_count > GDS_NSE_get () * 4.0)
848 /* forcefully terminate */
849 GNUNET_STATISTICS_update (GDS_stats,
850 gettext_noop ("# requests TTL-dropped"),
854 if (hop_count > GDS_NSE_get () * 2.0)
856 /* Once we have reached our ideal number of hops, only forward to 1 peer */
859 /* bound by system-wide maximum */
861 GNUNET_MIN (MAXIMUM_REPLICATION_LEVEL, target_replication);
863 1 + (target_replication - 1.0) / (GDS_NSE_get () +
864 ((float) (target_replication - 1.0) *
866 /* Set forward count to floor of target_value */
867 forward_count = (uint32_t) target_value;
868 /* Subtract forward_count (floor) from target_value (yields value between 0 and 1) */
869 target_value = target_value - forward_count;
871 GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, UINT32_MAX);
872 if (random_value < (target_value * UINT32_MAX))
874 return forward_count;
879 * Compute the distance between have and target as a 32-bit value.
880 * Differences in the lower bits must count stronger than differences
881 * in the higher bits.
885 * @return 0 if have==target, otherwise a number
886 * that is larger as the distance between
887 * the two hash codes increases
890 get_distance (const struct GNUNET_HashCode *target,
891 const struct GNUNET_HashCode *have)
898 /* We have to represent the distance between two 2^9 (=512)-bit
899 * numbers as a 2^5 (=32)-bit number with "0" being used for the
900 * two numbers being identical; furthermore, we need to
901 * guarantee that a difference in the number of matching
902 * bits is always represented in the result.
904 * We use 2^32/2^9 numerical values to distinguish between
905 * hash codes that have the same LSB bit distance and
906 * use the highest 2^9 bits of the result to signify the
907 * number of (mis)matching LSB bits; if we have 0 matching
908 * and hence 512 mismatching LSB bits we return -1 (since
909 * 512 itself cannot be represented with 9 bits) */
911 /* first, calculate the most significant 9 bits of our
912 * result, aka the number of LSBs */
913 bucket = GNUNET_CRYPTO_hash_matching_bits (target,
915 /* bucket is now a value between 0 and 512 */
917 return 0; /* perfect match */
919 return (unsigned int) -1; /* LSB differs; use max (if we did the bit-shifting
920 * below, we'd end up with max+1 (overflow)) */
922 /* calculate the most significant bits of the final result */
923 msb = (512 - bucket) << (32 - 9);
924 /* calculate the 32-9 least significant bits of the final result by
925 * looking at the differences in the 32-9 bits following the
926 * mismatching bit at 'bucket' */
929 (i < sizeof (struct GNUNET_HashCode) * 8) && (i < bucket + 1 + 32 - 9); i++)
931 if (GNUNET_CRYPTO_hash_get_bit (target, i) !=
932 GNUNET_CRYPTO_hash_get_bit (have, i))
933 lsb |= (1 << (bucket + 32 - 9 - i)); /* first bit set will be 10,
934 * last bit set will be 31 -- if
935 * i does not reach 512 first... */
942 * Check whether my identity is closer than any known peers. If a
943 * non-null bloomfilter is given, check if this is the closest peer
944 * that hasn't already been routed to.
946 * @param key hash code to check closeness to
947 * @param bloom bloomfilter, exclude these entries from the decision
948 * @return #GNUNET_YES if node location is closest,
949 * #GNUNET_NO otherwise.
952 GDS_am_closest_peer (const struct GNUNET_HashCode *key,
953 const struct GNUNET_CONTAINER_BloomFilter *bloom)
958 struct PeerInfo *pos;
960 if (0 == memcmp (&my_identity_hash,
962 sizeof (struct GNUNET_HashCode)))
964 bucket_num = find_bucket (key);
965 GNUNET_assert (bucket_num >= 0);
966 bits = GNUNET_CRYPTO_hash_matching_bits (&my_identity_hash,
968 pos = k_buckets[bucket_num].head;
971 if ( (NULL != bloom) &&
973 GNUNET_CONTAINER_bloomfilter_test (bloom,
977 continue; /* Skip already checked entries */
979 other_bits = GNUNET_CRYPTO_hash_matching_bits (&pos->phash,
981 if (other_bits > bits)
983 if (other_bits == bits) /* We match the same number of bits */
987 /* No peers closer, we are the closest! */
993 * Select a peer from the routing table that would be a good routing
994 * destination for sending a message for "key". The resulting peer
995 * must not be in the set of blocked peers.<p>
997 * Note that we should not ALWAYS select the closest peer to the
998 * target, peers further away from the target should be chosen with
999 * exponentially declining probability.
1001 * FIXME: double-check that this is fine
1004 * @param key the key we are selecting a peer to route to
1005 * @param bloom a bloomfilter containing entries this request has seen already
1006 * @param hops how many hops has this message traversed thus far
1007 * @return Peer to route to, or NULL on error
1009 static struct PeerInfo *
1010 select_peer (const struct GNUNET_HashCode *key,
1011 const struct GNUNET_CONTAINER_BloomFilter *bloom,
1016 unsigned int selected;
1017 struct PeerInfo *pos;
1019 unsigned int smallest_distance;
1020 struct PeerInfo *chosen;
1022 if (hops >= GDS_NSE_get ())
1024 /* greedy selection (closest peer that is not in bloomfilter) */
1025 smallest_distance = UINT_MAX;
1027 for (bc = 0; bc <= closest_bucket; bc++)
1029 pos = k_buckets[bc].head;
1031 while ((pos != NULL) && (count < bucket_size))
1033 if ( (NULL == bloom) ||
1035 GNUNET_CONTAINER_bloomfilter_test (bloom,
1038 dist = get_distance (key,
1040 if (dist < smallest_distance)
1043 smallest_distance = dist;
1048 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1049 "Excluded peer `%s' due to BF match in greedy routing for %s\n",
1050 GNUNET_i2s (pos->id),
1052 GNUNET_STATISTICS_update (GDS_stats,
1053 gettext_noop ("# Peers excluded from routing due to Bloomfilter"),
1056 dist = get_distance (key,
1058 if (dist < smallest_distance)
1061 smallest_distance = dist;
1069 GNUNET_STATISTICS_update (GDS_stats,
1070 gettext_noop ("# Peer selection failed"),
1074 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1075 "Selected peer `%s' in greedy routing for %s\n",
1076 GNUNET_i2s (chosen->id),
1081 /* select "random" peer */
1082 /* count number of peers that are available and not filtered */
1084 for (bc = 0; bc <= closest_bucket; bc++)
1086 pos = k_buckets[bc].head;
1087 while ( (NULL != pos) && (count < bucket_size) )
1089 if ( (NULL != bloom) &&
1091 GNUNET_CONTAINER_bloomfilter_test (bloom,
1094 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)); pos = pos->next)
1124 if ((bloom != NULL) &&
1126 GNUNET_CONTAINER_bloomfilter_test (bloom,
1129 continue; /* Ignore bloomfiltered peers */
1131 if (0 == selected--)
1133 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1134 "Selected peer `%s' in random routing for %s\n",
1135 GNUNET_i2s (pos->id),
1147 * Compute the set of peers that the given request should be
1150 * @param key routing key
1151 * @param bloom bloom filter excluding peers as targets, all selected
1152 * peers will be added to the bloom filter
1153 * @param hop_count number of hops the request has traversed so far
1154 * @param target_replication desired number of replicas
1155 * @param targets where to store an array of target peers (to be
1156 * free'd by the caller)
1157 * @return number of peers returned in 'targets'.
1160 get_target_peers (const struct GNUNET_HashCode *key,
1161 struct GNUNET_CONTAINER_BloomFilter *bloom,
1163 uint32_t target_replication,
1164 struct PeerInfo ***targets)
1168 struct PeerInfo **rtargets;
1169 struct PeerInfo *nxt;
1171 GNUNET_assert (NULL != bloom);
1172 ret = get_forward_count (hop_count,
1173 target_replication);
1179 rtargets = GNUNET_new_array (ret,
1181 for (off = 0; off < ret; off++)
1183 nxt = select_peer (key,
1188 rtargets[off] = nxt;
1189 GNUNET_break (GNUNET_NO ==
1190 GNUNET_CONTAINER_bloomfilter_test (bloom,
1192 GNUNET_CONTAINER_bloomfilter_add (bloom,
1195 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1196 "Selected %u/%u peers at hop %u for %s (target was %u)\n",
1198 GNUNET_CONTAINER_multipeermap_size (all_connected_peers),
1199 (unsigned int) hop_count,
1204 GNUNET_free (rtargets);
1208 *targets = rtargets;
1209 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1210 "Forwarding query `%s' to %u peers (goal was %u peers)\n",
1219 * Perform a PUT operation. Forwards the given request to other
1220 * peers. Does not store the data locally. Does not give the
1221 * data to local clients. May do nothing if this is the only
1222 * peer in the network (or if we are the closest peer in the
1225 * @param type type of the block
1226 * @param options routing options
1227 * @param desired_replication_level desired replication count
1228 * @param expiration_time when does the content expire
1229 * @param hop_count how many hops has this message traversed so far
1230 * @param bf Bloom filter of peers this PUT has already traversed
1231 * @param key key for the content
1232 * @param put_path_length number of entries in @a put_path
1233 * @param put_path peers this request has traversed so far (if tracked)
1234 * @param data payload to store
1235 * @param data_size number of bytes in @a data
1236 * @return #GNUNET_OK if the request was forwarded, #GNUNET_NO if not
1239 GDS_NEIGHBOURS_handle_put (enum GNUNET_BLOCK_Type type,
1240 enum GNUNET_DHT_RouteOption options,
1241 uint32_t desired_replication_level,
1242 struct GNUNET_TIME_Absolute expiration_time,
1244 struct GNUNET_CONTAINER_BloomFilter *bf,
1245 const struct GNUNET_HashCode *key,
1246 unsigned int put_path_length,
1247 struct GNUNET_PeerIdentity *put_path,
1251 unsigned int target_count;
1253 struct PeerInfo **targets;
1254 struct PeerInfo *target;
1256 struct GNUNET_MQ_Envelope *env;
1257 struct PeerPutMessage *ppm;
1258 struct GNUNET_PeerIdentity *pp;
1259 unsigned int skip_count;
1261 GNUNET_assert (NULL != bf);
1262 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1263 "Adding myself (%s) to PUT bloomfilter for %s\n",
1264 GNUNET_i2s (&my_identity),
1266 GNUNET_CONTAINER_bloomfilter_add (bf,
1268 GNUNET_STATISTICS_update (GDS_stats,
1269 gettext_noop ("# PUT requests routed"),
1273 = get_target_peers (key,
1276 desired_replication_level,
1278 if (0 == target_count)
1280 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1281 "Routing PUT for %s terminates after %u hops at %s\n",
1283 (unsigned int) hop_count,
1284 GNUNET_i2s (&my_identity));
1287 msize = put_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size;
1288 if (msize + sizeof (struct PeerPutMessage)
1289 >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1291 put_path_length = 0;
1294 if (msize + sizeof (struct PeerPutMessage)
1295 >= GNUNET_CONSTANTS_MAX_ENCRYPTED_MESSAGE_SIZE)
1298 GNUNET_free (targets);
1301 GNUNET_STATISTICS_update (GDS_stats,
1302 gettext_noop ("# PUT messages queued for transmission"),
1306 for (i = 0; i < target_count; i++)
1308 target = targets[i];
1309 if (GNUNET_MQ_get_length (target->mq) >= MAXIMUM_PENDING_PER_PEER)
1312 GNUNET_STATISTICS_update (GDS_stats,
1313 gettext_noop ("# P2P messages dropped due to full queue"),
1319 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1320 "Routing PUT for %s after %u hops to %s\n",
1322 (unsigned int) hop_count,
1323 GNUNET_i2s (target->id));
1324 env = GNUNET_MQ_msg_extra (ppm,
1326 GNUNET_MESSAGE_TYPE_DHT_P2P_PUT);
1327 ppm->options = htonl (options);
1328 ppm->type = htonl (type);
1329 ppm->hop_count = htonl (hop_count + 1);
1330 ppm->desired_replication_level = htonl (desired_replication_level);
1331 ppm->put_path_length = htonl (put_path_length);
1332 ppm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
1333 GNUNET_break (GNUNET_YES ==
1334 GNUNET_CONTAINER_bloomfilter_test (bf,
1336 GNUNET_assert (GNUNET_OK ==
1337 GNUNET_CONTAINER_bloomfilter_get_raw_data (bf,
1341 pp = (struct GNUNET_PeerIdentity *) &ppm[1];
1344 sizeof (struct GNUNET_PeerIdentity) * put_path_length);
1345 GNUNET_memcpy (&pp[put_path_length],
1348 GNUNET_MQ_send (target->mq,
1351 GNUNET_free (targets);
1352 return (skip_count < target_count) ? GNUNET_OK : GNUNET_NO;
1357 * Perform a GET operation. Forwards the given request to other
1358 * peers. Does not lookup the key locally. May do nothing if this is
1359 * the only peer in the network (or if we are the closest peer in the
1362 * @param type type of the block
1363 * @param options routing options
1364 * @param desired_replication_level desired replication count
1365 * @param hop_count how many hops did this request traverse so far?
1366 * @param key key for the content
1367 * @param xquery extended query
1368 * @param xquery_size number of bytes in @a xquery
1369 * @param bg group to use for filtering replies
1370 * @param peer_bf filter for peers not to select (again)
1371 * @return #GNUNET_OK if the request was forwarded, #GNUNET_NO if not
1374 GDS_NEIGHBOURS_handle_get (enum GNUNET_BLOCK_Type type,
1375 enum GNUNET_DHT_RouteOption options,
1376 uint32_t desired_replication_level,
1378 const struct GNUNET_HashCode *key,
1381 struct GNUNET_BLOCK_Group *bg,
1382 struct GNUNET_CONTAINER_BloomFilter *peer_bf)
1384 unsigned int target_count;
1385 struct PeerInfo **targets;
1386 struct PeerInfo *target;
1387 struct GNUNET_MQ_Envelope *env;
1389 struct PeerGetMessage *pgm;
1391 size_t reply_bf_size;
1393 unsigned int skip_count;
1396 GNUNET_assert (NULL != peer_bf);
1397 GNUNET_STATISTICS_update (GDS_stats,
1398 gettext_noop ("# GET requests routed"),
1401 target_count = get_target_peers (key,
1404 desired_replication_level,
1406 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1407 "Adding myself (%s) to GET bloomfilter for %s\n",
1408 GNUNET_i2s (&my_identity),
1410 GNUNET_CONTAINER_bloomfilter_add (peer_bf,
1412 if (0 == target_count)
1414 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1415 "Routing GET for %s terminates after %u hops at %s\n",
1417 (unsigned int) hop_count,
1418 GNUNET_i2s (&my_identity));
1422 GNUNET_BLOCK_group_serialize (bg,
1429 bf_nonce = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
1432 msize = xquery_size + reply_bf_size;
1433 if (msize + sizeof (struct PeerGetMessage) >= GNUNET_MAX_MESSAGE_SIZE)
1436 GNUNET_free_non_null (reply_bf);
1437 GNUNET_free (targets);
1440 GNUNET_STATISTICS_update (GDS_stats,
1441 gettext_noop ("# GET messages queued for transmission"),
1444 /* forward request */
1446 for (unsigned int i = 0; i < target_count; i++)
1448 target = targets[i];
1449 if (GNUNET_MQ_get_length (target->mq) >= MAXIMUM_PENDING_PER_PEER)
1452 GNUNET_STATISTICS_update (GDS_stats,
1453 gettext_noop ("# P2P messages dropped due to full queue"),
1458 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1459 "Routing GET for %s after %u hops to %s\n",
1461 (unsigned int) hop_count,
1462 GNUNET_i2s (target->id));
1463 env = GNUNET_MQ_msg_extra (pgm,
1465 GNUNET_MESSAGE_TYPE_DHT_P2P_GET);
1466 pgm->options = htonl (options);
1467 pgm->type = htonl (type);
1468 pgm->hop_count = htonl (hop_count + 1);
1469 pgm->desired_replication_level = htonl (desired_replication_level);
1470 pgm->xquery_size = htonl (xquery_size);
1471 pgm->bf_mutator = bf_nonce;
1472 GNUNET_break (GNUNET_YES ==
1473 GNUNET_CONTAINER_bloomfilter_test (peer_bf,
1475 GNUNET_assert (GNUNET_OK ==
1476 GNUNET_CONTAINER_bloomfilter_get_raw_data (peer_bf,
1480 xq = (char *) &pgm[1];
1484 GNUNET_memcpy (&xq[xquery_size],
1487 GNUNET_MQ_send (target->mq,
1490 GNUNET_free (targets);
1491 GNUNET_free_non_null (reply_bf);
1492 return (skip_count < target_count) ? GNUNET_OK : GNUNET_NO;
1497 * Handle a reply (route to origin). Only forwards the reply back to
1498 * the given peer. Does not do local caching or forwarding to local
1501 * @param target neighbour that should receive the block (if still connected)
1502 * @param type type of the block
1503 * @param expiration_time when does the content expire
1504 * @param key key for the content
1505 * @param put_path_length number of entries in @a put_path
1506 * @param put_path peers the original PUT traversed (if tracked)
1507 * @param get_path_length number of entries in @a get_path
1508 * @param get_path peers this reply has traversed so far (if tracked)
1509 * @param data payload of the reply
1510 * @param data_size number of bytes in @a data
1513 GDS_NEIGHBOURS_handle_reply (const struct GNUNET_PeerIdentity *target,
1514 enum GNUNET_BLOCK_Type type,
1515 struct GNUNET_TIME_Absolute expiration_time,
1516 const struct GNUNET_HashCode *key,
1517 unsigned int put_path_length,
1518 const struct GNUNET_PeerIdentity *put_path,
1519 unsigned int get_path_length,
1520 const struct GNUNET_PeerIdentity *get_path,
1524 struct PeerInfo *pi;
1525 struct GNUNET_MQ_Envelope *env;
1527 struct PeerResultMessage *prm;
1528 struct GNUNET_PeerIdentity *paths;
1530 msize = data_size + (get_path_length + put_path_length) *
1531 sizeof (struct GNUNET_PeerIdentity);
1532 if ((msize + sizeof (struct PeerResultMessage) >= GNUNET_MAX_MESSAGE_SIZE) ||
1534 GNUNET_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)) ||
1536 GNUNET_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)) ||
1537 (data_size > GNUNET_MAX_MESSAGE_SIZE))
1542 pi = GNUNET_CONTAINER_multipeermap_get (all_connected_peers,
1546 /* peer disconnected in the meantime, drop reply */
1547 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1548 "No matching peer for reply for key %s\n",
1552 if (GNUNET_MQ_get_length (pi->mq) >= MAXIMUM_PENDING_PER_PEER)
1555 GNUNET_STATISTICS_update (GDS_stats,
1556 gettext_noop ("# P2P messages dropped due to full queue"),
1559 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1560 "Peer queue full, ignoring reply for key %s\n",
1565 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1566 "Forwarding reply for key %s to peer %s\n",
1568 GNUNET_i2s (target));
1569 GNUNET_STATISTICS_update (GDS_stats,
1571 ("# RESULT messages queued for transmission"), 1,
1573 env = GNUNET_MQ_msg_extra (prm,
1575 GNUNET_MESSAGE_TYPE_DHT_P2P_RESULT);
1576 prm->type = htonl (type);
1577 prm->put_path_length = htonl (put_path_length);
1578 prm->get_path_length = htonl (get_path_length);
1579 prm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time);
1581 paths = (struct GNUNET_PeerIdentity *) &prm[1];
1582 GNUNET_memcpy (paths,
1584 put_path_length * sizeof (struct GNUNET_PeerIdentity));
1585 GNUNET_memcpy (&paths[put_path_length],
1587 get_path_length * sizeof (struct GNUNET_PeerIdentity));
1588 GNUNET_memcpy (&paths[put_path_length + get_path_length],
1591 GNUNET_MQ_send (pi->mq,
1597 * To be called on core init/fail.
1599 * @param cls service closure
1600 * @param identity the public identity of this peer
1603 core_init (void *cls,
1604 const struct GNUNET_PeerIdentity *identity)
1607 GNUNET_log (GNUNET_ERROR_TYPE_INFO,
1608 "CORE called, I am %s\n",
1609 GNUNET_i2s (identity));
1610 my_identity = *identity;
1611 GNUNET_CRYPTO_hash (identity,
1612 sizeof (struct GNUNET_PeerIdentity),
1614 GNUNET_SERVICE_resume (GDS_service);
1619 * Check validity of a p2p put request.
1621 * @param cls closure with the `struct PeerInfo` of the sender
1622 * @param message message
1623 * @return #GNUNET_OK if the message is valid
1626 check_dht_p2p_put (void *cls,
1627 const struct PeerPutMessage *put)
1633 msize = ntohs (put->header.size);
1634 putlen = ntohl (put->put_path_length);
1636 sizeof (struct PeerPutMessage) +
1637 putlen * sizeof (struct GNUNET_PeerIdentity)) ||
1639 GNUNET_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
1641 GNUNET_break_op (0);
1642 return GNUNET_SYSERR;
1649 * Core handler for p2p put requests.
1651 * @param cls closure with the `struct PeerInfo` of the sender
1652 * @param message message
1655 handle_dht_p2p_put (void *cls,
1656 const struct PeerPutMessage *put)
1658 struct PeerInfo *peer = cls;
1659 const struct GNUNET_PeerIdentity *put_path;
1660 const void *payload;
1663 size_t payload_size;
1664 enum GNUNET_DHT_RouteOption options;
1665 struct GNUNET_CONTAINER_BloomFilter *bf;
1666 struct GNUNET_HashCode test_key;
1668 struct GNUNET_TIME_Absolute exp_time;
1670 exp_time = GNUNET_TIME_absolute_ntoh (put->expiration_time);
1671 if (0 == GNUNET_TIME_absolute_get_remaining (exp_time).rel_value_us)
1673 GNUNET_STATISTICS_update (GDS_stats,
1674 gettext_noop ("# Expired PUTs discarded"),
1679 msize = ntohs (put->header.size);
1680 putlen = ntohl (put->put_path_length);
1681 GNUNET_STATISTICS_update (GDS_stats,
1682 gettext_noop ("# P2P PUT requests received"),
1685 GNUNET_STATISTICS_update (GDS_stats,
1686 gettext_noop ("# P2P PUT bytes received"),
1689 put_path = (const struct GNUNET_PeerIdentity *) &put[1];
1690 payload = &put_path[putlen];
1691 options = ntohl (put->options);
1692 payload_size = msize - (sizeof (struct PeerPutMessage) +
1693 putlen * sizeof (struct GNUNET_PeerIdentity));
1695 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1696 "PUT for `%s' from %s\n",
1697 GNUNET_h2s (&put->key),
1698 GNUNET_i2s (peer->id));
1699 if (GNUNET_YES == log_route_details_stderr)
1704 pp = GNUNET_STRINGS_pp2s (put_path,
1706 tmp = GNUNET_strdup (GNUNET_i2s (&my_identity));
1707 LOG_TRAFFIC (GNUNET_ERROR_TYPE_DEBUG,
1708 "R5N PUT %s: %s->%s (%u, %u=>%u, PP: %s)\n",
1709 GNUNET_h2s (&put->key),
1710 GNUNET_i2s (peer->id),
1712 ntohl(put->hop_count),
1713 GNUNET_CRYPTO_hash_matching_bits (&peer->phash,
1715 GNUNET_CRYPTO_hash_matching_bits (&my_identity_hash,
1721 switch (GNUNET_BLOCK_get_key
1729 if (0 != memcmp (&test_key,
1731 sizeof (struct GNUNET_HashCode)))
1733 char *put_s = GNUNET_strdup (GNUNET_h2s_full (&put->key));
1735 GNUNET_break_op (0);
1736 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
1737 "PUT with key `%s' for block with key %s\n",
1739 GNUNET_h2s_full (&test_key));
1740 GNUNET_free (put_s);
1745 GNUNET_break_op (0);
1748 /* cannot verify, good luck */
1751 if (ntohl (put->type) == GNUNET_BLOCK_TYPE_REGEX) /* FIXME: do for all tpyes */
1753 switch (GNUNET_BLOCK_evaluate (GDS_block_context,
1755 NULL, /* query group */
1756 GNUNET_BLOCK_EO_NONE,
1758 NULL, 0, /* xquery */
1762 case GNUNET_BLOCK_EVALUATION_OK_MORE:
1763 case GNUNET_BLOCK_EVALUATION_OK_LAST:
1766 case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
1767 case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
1768 case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT:
1769 case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
1770 case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
1771 case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
1773 GNUNET_break_op (0);
1778 bf = GNUNET_CONTAINER_bloomfilter_init (put->bloomfilter,
1780 GNUNET_CONSTANTS_BLOOMFILTER_K);
1781 GNUNET_break_op (GNUNET_YES ==
1782 GNUNET_CONTAINER_bloomfilter_test (bf,
1785 struct GNUNET_PeerIdentity pp[putlen + 1];
1787 /* extend 'put path' by sender */
1788 if (0 != (options & GNUNET_DHT_RO_RECORD_ROUTE))
1791 for (unsigned int i=0;i<=putlen;i++)
1793 for (unsigned int j=0;j<i;j++)
1795 GNUNET_break (0 != memcmp (&pp[i],
1797 sizeof (struct GNUNET_PeerIdentity)));
1799 GNUNET_break (0 != memcmp (&pp[i],
1801 sizeof (struct GNUNET_PeerIdentity)));
1806 putlen * sizeof (struct GNUNET_PeerIdentity));
1807 pp[putlen] = *peer->id;
1813 /* give to local clients */
1814 GDS_CLIENTS_handle_reply (exp_time,
1824 if ((0 != (options & GNUNET_DHT_RO_DEMULTIPLEX_EVERYWHERE)) ||
1825 (GDS_am_closest_peer (&put->key, bf)))
1826 GDS_DATACACHE_handle_put (exp_time,
1833 /* route to other peers */
1834 forwarded = GDS_NEIGHBOURS_handle_put (ntohl (put->type),
1836 ntohl (put->desired_replication_level),
1838 ntohl (put->hop_count),
1845 /* notify monitoring clients */
1846 GDS_CLIENTS_process_put (options
1847 | ( (GNUNET_OK == forwarded)
1848 ? GNUNET_DHT_RO_LAST_HOP
1851 ntohl (put->hop_count),
1852 ntohl (put->desired_replication_level),
1859 GNUNET_CONTAINER_bloomfilter_free (bf);
1864 * We have received a FIND PEER request. Send matching
1867 * @param sender sender of the FIND PEER request
1868 * @param key peers close to this key are desired
1869 * @param bg group for filtering peers
1872 handle_find_peer (const struct GNUNET_PeerIdentity *sender,
1873 const struct GNUNET_HashCode *key,
1874 struct GNUNET_BLOCK_Group *bg)
1877 struct PeerBucket *bucket;
1878 struct PeerInfo *peer;
1879 unsigned int choice;
1880 const struct GNUNET_HELLO_Message *hello;
1883 /* first, check about our own HELLO */
1884 if (NULL != GDS_my_hello)
1886 hello_size = GNUNET_HELLO_size ((const struct GNUNET_HELLO_Message *) GDS_my_hello);
1887 GNUNET_break (hello_size >= sizeof (struct GNUNET_MessageHeader));
1888 if (GNUNET_BLOCK_EVALUATION_OK_MORE ==
1889 GNUNET_BLOCK_evaluate (GDS_block_context,
1890 GNUNET_BLOCK_TYPE_DHT_HELLO,
1892 GNUNET_BLOCK_EO_LOCAL_SKIP_CRYPTO,
1898 GDS_NEIGHBOURS_handle_reply (sender,
1899 GNUNET_BLOCK_TYPE_DHT_HELLO,
1900 GNUNET_TIME_relative_to_absolute (hello_expiration),
1911 GNUNET_STATISTICS_update (GDS_stats,
1912 gettext_noop ("# FIND PEER requests ignored due to Bloomfilter"),
1919 GNUNET_STATISTICS_update (GDS_stats,
1920 gettext_noop ("# FIND PEER requests ignored due to lack of HELLO"),
1925 /* then, also consider sending a random HELLO from the closest bucket */
1926 if (0 == memcmp (&my_identity_hash,
1928 sizeof (struct GNUNET_HashCode)))
1929 bucket_idx = closest_bucket;
1931 bucket_idx = GNUNET_MIN ((int) closest_bucket,
1935 bucket = &k_buckets[bucket_idx];
1936 if (bucket->peers_size == 0)
1938 choice = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
1939 bucket->peers_size);
1940 peer = bucket->head;
1943 GNUNET_assert (NULL != peer);
1947 choice = bucket->peers_size;
1952 return; /* no non-masked peer available */
1954 peer = bucket->head;
1955 hello = GDS_HELLO_get (peer->id);
1956 } while ( (NULL == hello) ||
1957 (GNUNET_BLOCK_EVALUATION_OK_MORE !=
1958 GNUNET_BLOCK_evaluate (GDS_block_context,
1959 GNUNET_BLOCK_TYPE_DHT_HELLO,
1961 GNUNET_BLOCK_EO_LOCAL_SKIP_CRYPTO,
1965 (hello_size = GNUNET_HELLO_size (hello)))) );
1966 GDS_NEIGHBOURS_handle_reply (sender,
1967 GNUNET_BLOCK_TYPE_DHT_HELLO,
1968 GNUNET_TIME_relative_to_absolute
1969 (GNUNET_CONSTANTS_HELLO_ADDRESS_EXPIRATION),
1981 * Handle a result from local datacache for a GET operation.
1983 * @param cls the `struct PeerInfo` for which this is a reply
1984 * @param type type of the block
1985 * @param expiration_time when does the content expire
1986 * @param key key for the content
1987 * @param put_path_length number of entries in @a put_path
1988 * @param put_path peers the original PUT traversed (if tracked)
1989 * @param get_path_length number of entries in @a get_path
1990 * @param get_path peers this reply has traversed so far (if tracked)
1991 * @param data payload of the reply
1992 * @param data_size number of bytes in @a data
1995 handle_local_result (void *cls,
1996 enum GNUNET_BLOCK_Type type,
1997 struct GNUNET_TIME_Absolute expiration_time,
1998 const struct GNUNET_HashCode *key,
1999 unsigned int put_path_length,
2000 const struct GNUNET_PeerIdentity *put_path,
2001 unsigned int get_path_length,
2002 const struct GNUNET_PeerIdentity *get_path,
2006 struct PeerInfo *peer = cls;
2009 pp = GNUNET_STRINGS_pp2s (put_path,
2011 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2012 "Found local result for %s (PP: %s)\n",
2016 GDS_NEIGHBOURS_handle_reply (peer->id,
2020 put_path_length, put_path,
2021 get_path_length, get_path,
2027 * Check validity of p2p get request.
2029 * @param cls closure with the `struct PeerInfo` of the sender
2030 * @param get the message
2031 * @return #GNUNET_OK if the message is well-formed
2034 check_dht_p2p_get (void *cls,
2035 const struct PeerGetMessage *get)
2037 uint32_t xquery_size;
2041 msize = ntohs (get->header.size);
2042 xquery_size = ntohl (get->xquery_size);
2043 if (msize < sizeof (struct PeerGetMessage) + xquery_size)
2045 GNUNET_break_op (0);
2046 return GNUNET_SYSERR;
2053 * Core handler for p2p get requests.
2055 * @param cls closure with the `struct PeerInfo` of the sender
2056 * @param get the message
2059 handle_dht_p2p_get (void *cls,
2060 const struct PeerGetMessage *get)
2062 struct PeerInfo *peer = cls;
2063 uint32_t xquery_size;
2064 size_t reply_bf_size;
2066 enum GNUNET_BLOCK_Type type;
2067 enum GNUNET_DHT_RouteOption options;
2068 enum GNUNET_BLOCK_EvaluationResult eval;
2069 struct GNUNET_BLOCK_Group *bg;
2070 struct GNUNET_CONTAINER_BloomFilter *peer_bf;
2074 /* parse and validate message */
2075 msize = ntohs (get->header.size);
2076 xquery_size = ntohl (get->xquery_size);
2077 reply_bf_size = msize - (sizeof (struct PeerGetMessage) + xquery_size);
2078 type = ntohl (get->type);
2079 options = ntohl (get->options);
2080 xquery = (const char *) &get[1];
2081 GNUNET_STATISTICS_update (GDS_stats,
2082 gettext_noop ("# P2P GET requests received"),
2085 GNUNET_STATISTICS_update (GDS_stats,
2086 gettext_noop ("# P2P GET bytes received"),
2089 if (GNUNET_YES == log_route_details_stderr)
2093 tmp = GNUNET_strdup (GNUNET_i2s (&my_identity));
2094 LOG_TRAFFIC (GNUNET_ERROR_TYPE_DEBUG,
2095 "R5N GET %s: %s->%s (%u, %u=>%u) xq: %.*s\n",
2096 GNUNET_h2s (&get->key),
2097 GNUNET_i2s (peer->id),
2099 ntohl(get->hop_count),
2100 GNUNET_CRYPTO_hash_matching_bits (&peer->phash,
2102 GNUNET_CRYPTO_hash_matching_bits (&my_identity_hash,
2104 ntohl(get->xquery_size),
2109 = GNUNET_BLOCK_evaluate (GDS_block_context,
2112 GNUNET_BLOCK_EO_NONE,
2118 if (eval != GNUNET_BLOCK_EVALUATION_REQUEST_VALID)
2120 /* request invalid or block type not supported */
2121 GNUNET_break_op (eval == GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED);
2124 peer_bf = GNUNET_CONTAINER_bloomfilter_init (get->bloomfilter,
2126 GNUNET_CONSTANTS_BLOOMFILTER_K);
2127 GNUNET_break_op (GNUNET_YES ==
2128 GNUNET_CONTAINER_bloomfilter_test (peer_bf,
2130 bg = GNUNET_BLOCK_group_create (GDS_block_context,
2133 &xquery[xquery_size],
2138 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
2139 "GET for %s at %s after %u hops\n",
2140 GNUNET_h2s (&get->key),
2141 GNUNET_i2s (&my_identity),
2142 (unsigned int) ntohl (get->hop_count));
2143 /* local lookup (this may update the reply_bf) */
2144 if ((0 != (options & GNUNET_DHT_RO_DEMULTIPLEX_EVERYWHERE)) ||
2145 (GDS_am_closest_peer (&get->key,
2148 if ((0 != (options & GNUNET_DHT_RO_FIND_PEER)))
2150 GNUNET_STATISTICS_update (GDS_stats,
2151 gettext_noop ("# P2P FIND PEER requests processed"),
2154 handle_find_peer (peer->id,
2160 eval = GDS_DATACACHE_handle_get (&get->key,
2165 &handle_local_result,
2171 GNUNET_STATISTICS_update (GDS_stats,
2172 gettext_noop ("# P2P GET requests ONLY routed"),
2177 /* remember request for routing replies */
2178 GDS_ROUTING_add (peer->id,
2180 bg, /* bg now owned by routing, but valid at least until end of this function! */
2186 /* P2P forwarding */
2187 forwarded = GNUNET_NO;
2188 if (eval != GNUNET_BLOCK_EVALUATION_OK_LAST)
2189 forwarded = GDS_NEIGHBOURS_handle_get (type,
2191 ntohl (get->desired_replication_level),
2192 ntohl (get->hop_count),
2198 GDS_CLIENTS_process_get (options
2199 | (GNUNET_OK == forwarded)
2200 ? GNUNET_DHT_RO_LAST_HOP : 0,
2202 ntohl (get->hop_count),
2203 ntohl (get->desired_replication_level),
2208 /* clean up; note that 'bg' is owned by routing now! */
2209 GNUNET_CONTAINER_bloomfilter_free (peer_bf);
2214 * Check validity of p2p result message.
2216 * @param cls closure
2217 * @param message message
2218 * @return #GNUNET_YES if the message is well-formed
2221 check_dht_p2p_result (void *cls,
2222 const struct PeerResultMessage *prm)
2224 uint32_t get_path_length;
2225 uint32_t put_path_length;
2229 msize = ntohs (prm->header.size);
2230 put_path_length = ntohl (prm->put_path_length);
2231 get_path_length = ntohl (prm->get_path_length);
2233 sizeof (struct PeerResultMessage) + (get_path_length +
2235 sizeof (struct GNUNET_PeerIdentity)) ||
2237 GNUNET_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)) ||
2239 GNUNET_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity)))
2241 GNUNET_break_op (0);
2242 return GNUNET_SYSERR;
2249 * Process a reply, after the @a get_path has been updated.
2251 * @param expiration_time when does the reply expire
2252 * @param key key matching the query
2253 * @param get_path_length number of entries in @a get_path
2254 * @param get_path path the reply has taken
2255 * @param put_path_length number of entries in @a put_path
2256 * @param put_path path the PUT has taken
2257 * @param type type of the block
2258 * @param data_size number of bytes in @a data
2259 * @param data payload of the reply
2262 process_reply_with_path (struct GNUNET_TIME_Absolute expiration_time,
2263 const struct GNUNET_HashCode *key,
2264 unsigned int get_path_length,
2265 const struct GNUNET_PeerIdentity *get_path,
2266 unsigned int put_path_length,
2267 const struct GNUNET_PeerIdentity *put_path,
2268 enum GNUNET_BLOCK_Type type,
2272 /* forward to local clients */
2273 GDS_CLIENTS_handle_reply (expiration_time,
2282 GDS_CLIENTS_process_get_resp (type,
2291 if (GNUNET_YES == cache_results)
2293 struct GNUNET_PeerIdentity xput_path[get_path_length + 1 + put_path_length];
2295 GNUNET_memcpy (xput_path,
2297 put_path_length * sizeof (struct GNUNET_PeerIdentity));
2298 GNUNET_memcpy (&xput_path[put_path_length],
2300 get_path_length * sizeof (struct GNUNET_PeerIdentity));
2302 GDS_DATACACHE_handle_put (expiration_time,
2304 get_path_length + put_path_length,
2310 /* forward to other peers */
2311 GDS_ROUTING_process (type,
2324 * Core handler for p2p result messages.
2326 * @param cls closure
2327 * @param message message
2330 handle_dht_p2p_result (void *cls,
2331 const struct PeerResultMessage *prm)
2333 struct PeerInfo *peer = cls;
2334 const struct GNUNET_PeerIdentity *put_path;
2335 const struct GNUNET_PeerIdentity *get_path;
2337 uint32_t get_path_length;
2338 uint32_t put_path_length;
2341 enum GNUNET_BLOCK_Type type;
2342 struct GNUNET_TIME_Absolute exp_time;
2344 /* parse and validate message */
2345 exp_time = GNUNET_TIME_absolute_ntoh (prm->expiration_time);
2346 if (0 == GNUNET_TIME_absolute_get_remaining (exp_time).rel_value_us)
2348 GNUNET_STATISTICS_update (GDS_stats,
2349 gettext_noop ("# Expired results discarded"),
2354 msize = ntohs (prm->header.size);
2355 put_path_length = ntohl (prm->put_path_length);
2356 get_path_length = ntohl (prm->get_path_length);
2357 put_path = (const struct GNUNET_PeerIdentity *) &prm[1];
2358 get_path = &put_path[put_path_length];
2359 type = ntohl (prm->type);
2360 data = (const void *) &get_path[get_path_length];
2361 data_size = msize - (sizeof (struct PeerResultMessage) +
2363 put_path_length) * sizeof (struct GNUNET_PeerIdentity));
2364 GNUNET_STATISTICS_update (GDS_stats,
2365 gettext_noop ("# P2P RESULTS received"),
2368 GNUNET_STATISTICS_update (GDS_stats,
2369 gettext_noop ("# P2P RESULT bytes received"),
2372 if (GNUNET_YES == log_route_details_stderr)
2378 gp = GNUNET_STRINGS_pp2s (get_path,
2380 pp = GNUNET_STRINGS_pp2s (put_path,
2382 tmp = GNUNET_strdup (GNUNET_i2s (&my_identity));
2383 LOG_TRAFFIC (GNUNET_ERROR_TYPE_DEBUG,
2384 "R5N RESULT %s: %s->%s (GP: %s, PP: %s)\n",
2385 GNUNET_h2s (&prm->key),
2386 GNUNET_i2s (peer->id),
2394 /* if we got a HELLO, consider it for our own routing table */
2395 if (GNUNET_BLOCK_TYPE_DHT_HELLO == type)
2397 const struct GNUNET_MessageHeader *h;
2398 struct GNUNET_PeerIdentity pid;
2400 /* Should be a HELLO, validate and consider using it! */
2401 if (data_size < sizeof (struct GNUNET_HELLO_Message))
2403 GNUNET_break_op (0);
2407 if (data_size != ntohs (h->size))
2409 GNUNET_break_op (0);
2413 GNUNET_HELLO_get_id ((const struct GNUNET_HELLO_Message *) h,
2416 GNUNET_break_op (0);
2419 if ( (GNUNET_YES != disable_try_connect) &&
2420 (0 != memcmp (&my_identity,
2422 sizeof (struct GNUNET_PeerIdentity))) )
2427 /* First, check if 'peer' is already on the path, and if
2428 so, truncate it instead of expanding. */
2429 for (unsigned int i=0;i<=get_path_length;i++)
2430 if (0 == memcmp (&get_path[i],
2432 sizeof (struct GNUNET_PeerIdentity)))
2434 process_reply_with_path (exp_time,
2446 /* Need to append 'peer' to 'get_path' (normal case) */
2448 struct GNUNET_PeerIdentity xget_path[get_path_length + 1];
2450 GNUNET_memcpy (xget_path,
2452 get_path_length * sizeof (struct GNUNET_PeerIdentity));
2453 xget_path[get_path_length] = *peer->id;
2455 process_reply_with_path (exp_time,
2457 get_path_length + 1,
2469 * Initialize neighbours subsystem.
2471 * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
2474 GDS_NEIGHBOURS_init ()
2476 struct GNUNET_MQ_MessageHandler core_handlers[] = {
2477 GNUNET_MQ_hd_var_size (dht_p2p_get,
2478 GNUNET_MESSAGE_TYPE_DHT_P2P_GET,
2479 struct PeerGetMessage,
2481 GNUNET_MQ_hd_var_size (dht_p2p_put,
2482 GNUNET_MESSAGE_TYPE_DHT_P2P_PUT,
2483 struct PeerPutMessage,
2485 GNUNET_MQ_hd_var_size (dht_p2p_result,
2486 GNUNET_MESSAGE_TYPE_DHT_P2P_RESULT,
2487 struct PeerResultMessage,
2489 GNUNET_MQ_handler_end ()
2491 unsigned long long temp_config_num;
2494 = GNUNET_CONFIGURATION_get_value_yesno (GDS_cfg,
2496 "DISABLE_TRY_CONNECT");
2498 GNUNET_CONFIGURATION_get_value_number (GDS_cfg,
2502 bucket_size = (unsigned int) temp_config_num;
2504 = GNUNET_CONFIGURATION_get_value_yesno (GDS_cfg,
2508 log_route_details_stderr =
2509 (NULL != getenv("GNUNET_DHT_ROUTE_DEBUG")) ? GNUNET_YES : GNUNET_NO;
2510 ats_ch = GNUNET_ATS_connectivity_init (GDS_cfg);
2511 core_api = GNUNET_CORE_connect (GDS_cfg,
2514 &handle_core_connect,
2515 &handle_core_disconnect,
2517 if (NULL == core_api)
2518 return GNUNET_SYSERR;
2519 all_connected_peers = GNUNET_CONTAINER_multipeermap_create (256,
2521 all_desired_peers = GNUNET_CONTAINER_multipeermap_create (256,
2528 * Shutdown neighbours subsystem.
2531 GDS_NEIGHBOURS_done ()
2533 if (NULL == core_api)
2535 GNUNET_CORE_disconnect (core_api);
2538 GNUNET_CONTAINER_multipeermap_size (all_connected_peers));
2539 GNUNET_CONTAINER_multipeermap_destroy (all_connected_peers);
2540 all_connected_peers = NULL;
2541 GNUNET_CONTAINER_multipeermap_iterate (all_desired_peers,
2544 GNUNET_CONTAINER_multipeermap_destroy (all_desired_peers);
2545 all_desired_peers = NULL;
2546 GNUNET_ATS_connectivity_done (ats_ch);
2548 GNUNET_assert (NULL == find_peer_task);
2553 * Get the ID of the local node.
2555 * @return identity of the local node
2557 struct GNUNET_PeerIdentity *
2558 GDS_NEIGHBOURS_get_id ()
2560 return &my_identity;
2564 /* end of gnunet-service-dht_neighbours.c */